邏輯表達式的短路是如何實現的？

01-27

比如與運算時如果左值為假時不計算右值，或運算左值為真時不計算右值。

題主問的是諸如C語言的與 || 運算符的實現方式。

其實現代的編譯器在處理這種帶短路求值語義的條件表達式時，通常是採用「控制流」法來實現的。

與「控制流」法相對的的做法是「算術」法——實際用位運算來求出條件表達式的結果。這個在現代編譯器中偶爾會作為一種優化方式出現，但很少作為主要的、基礎的實現方式。

========================================

控制流法（control flow）

所謂「控制流」法，也叫做「跳轉法」（jumping code），顧名思義，就是通過條件跳轉來實現短路求值的語義。

例如說，這個C語言的例子：

if (a b c) { do_something(); }

實際讓編譯器看，它所看到的是：

if (a) { if (b) { if (c) { do_something(); } } }

通過嵌套的if語句，如果a、b、c按順序任意一個不為真值，則條件表達式就被短路了。就這麼簡單。

但使用「控制流」法的實現，不一定能直觀地用結構化的高級語言結構來表達，所以要用C的語法來演示會顯得略麻煩——但要注意，這只是演示起來有點麻煩而已，對編譯器內部實現來說並沒有任何麻煩之處。

例如說：

if ((a b c) || d) { do_something(); }

這個用控制流法會被實現為：

if (a) { if (b) { if (c) { goto then_label; } else { goto else_label; } } else { goto else_label; } } else { else_label: if (d) { then_label: do_something(); } }

用LLVM IR來演示這種情況就是：

br i1 %a, label %1, label %3


; &:1:                                      ; preds = %0

  br i1 %b, label %2, label %3
; &:2:                                      ; preds = %1

  br i1 %c, label %4, label %3
; &:3:                                      ; preds = %2, %1, %0

  br i1 %d, label %4, label %5
; &:4:                                      ; preds = %3, %2

  call void @_Z12do_somethingv()

  br label %5

; &:5: ; preds = %4, %3 ; ...

C的版本看起來那麼複雜主要是因為C如果不用goto/break/continue等跳轉語句的話，普通的結構化控制流結構（if / while / for等）都是要求「單入口單出口」的，很難表達多個條件跳轉共用同一個目標的邏輯。如果把上面的代碼展開成結構化的形式，就會是：

if (a) { if (b) { if (c) { do_something(); } else if (d) { do_something(); } } else if (d) { do_something(); } } else if (d) { do_something(); }

看到被重複的代碼塊了不？前面的goto就是把這些重複的塊合併在一起用的。

========================================

算術法（arithmetic）

前面說了「控制流」法，挺好理解的對不？但是如何能用「算術」法來實現帶短路求值語義的條件表達式呢？

之所以基礎做法要用控制流法，是因為條件表達式中可能帶有副作用，短路求值的語義如果沒有被正確實現——換句話說，如果無條件對條件表達式中的所有項都求值——就有可能會發生預期之外的副作用，從而破壞了程序的正確性。

但是！如果可以確定一串條件表達式中的所有項都沒有副作用，那麼就可以使用算術法來對這個條件表達式求值，反正外界也無法觀測到到底是不是真的短路求值的——沒有副作用嘛。

針對取值範圍只有0到1的C的bool類型（_Bool類型，聲明在stdint.h），按位算術運算正好就跟邏輯運算的意義一樣，這樣我們就可以用按位算術運算來實現邏輯運算了。並且，在沒有副作用的時候，編譯器也有足夠自由去調整求值順序，而不一定要跟原本的短路求值語義的求值順序一樣，只要結果一樣就行。

所以，還是用上面的例子，如果a、b、c、d都是簡單的bool類型（_Bool類型，取值範圍是0到1）變數，那麼，

if ((a b c) || d) { do_something(); }

就可以被優化為：

if ((a b c) | d) { do_something(); }

事實上LLVM就實現了這樣的優化。這個例子讓Clang+LLVM來編譯得到的IR是：

; Function Attrs: nounwind ssp uwtable define void @foo(i1 zeroext %a, i1 zeroext %b, i1 zeroext %c, i1 zeroext %d) #0 { %brmerge.demorgan = and i1 %a, %b %brmerge1.demorgan = and i1 %brmerge.demorgan, %c %brmerge2 = or i1 %brmerge1.demorgan, %d br i1 %brmerge2, label %1, label %2


; &:1                                       ; preds = %0

  tail call void (...)* @do_something() #2

  br label %2

; &:2 ; preds = %0, %1 ret void }

就跟上面用C演示的算術法版本一樣。

（"brmerge"來自SimpifyCFG中的SimplifyCondBranchToCondBranch()，".demorgan"來自InstCombine中的matchDeMorgansLaws。）

為啥不短路反而算是「優化」呢？這是因為條件跳轉在現代CPU上常常是比較高開銷的操作，即便有優秀的硬體分支預測，如果能減少無謂的條件分支還是好的。

========================================

算術法與「真值」

於是肯定就會有同學問了：但是C語言里的「真值」並不只有「true」（1）一個；所有非0的整數或者非NULL的指針都是真值。這些各種各樣的真值要如何應用算術法呢？畢竟，如果有int a，C語言層面的 (a 1) 跟 (a 1) 不是一回事啊。

而答案很簡單：只要先將所有真值都統一（canonicalize）到_Bool類型（0或1）即可。

讓我們看個例子。對下面這個函數，

_Bool foo(int a, _Bool b, _Bool c) { return a b c; }

GCC 6.2在Linux/x86-64上可以生成下面的代碼：

foo(int a, _Bool b, _Bool c): // edi: a // esi: b // edx: c movl %edx, %eax // eax = c andl %esi, %eax // eax = c b testl %edi, %edi // dl = setne %dl // a == 0 ? 0 : 1 andl %edx, %eax // eax = c b (a == 0 ? 0 : 1) ret // return eax

沒有任何控制流，只有算術運算，對不對？

有趣的點就是其中的test與setne指令。x86上，test指令會對輸入的兩個操作數做比較，並且設置條件碼（condition code）；setCC指令會把指定的條件（這裡CC是not equal）從條件碼中提取出來賦值到指定的寄存器中。這裡，通過這兩條指令，我們就把a的值從任意int統一到了_Bool類型的取值範圍內，從而可以使用算術法正確實現條件表達式的語義。

不同編譯器可能會採用不同的方式來實現canonicalization，例如說混合控制流法與算術法——通過控制流法來canonicalize，然後再通過算術法來計算統一後的值。

還是用這個例子，Clang 3.9在Linux/x86-64上生成的代碼是：

foo: testl %edi, %edi je .LBB0_2 andb %dl, %sil movl %esi, %eax retq .LBB0_2: xorl %eax, %eax retq

這對應的IR是：

; Function Attrs: nounwind readnone ssp uwtable define zeroext i1 @foo(i32 %a, i1 zeroext %b, i1 zeroext %c) #0 { %1 = icmp eq i32 %a, 0 br i1 %1, label %3, label %2


; &:2                                       ; preds = %0

  %c. = and i1 %b, %c

  ret i1 %c.

; &:3 ; preds = %0 ret i1 false }

可以看到它是先通過控制流法把a給canonicalize到_Bool範圍，然後再做算術運算的。用C來表達這個做法就是：

_Bool foo(int a, _Bool b, _Bool c) { if (a == 0) { return FALSE; } else { return b c; } }

而ICC 17.0用的做法又不一樣。它會選擇用條件傳送（conditional move）來實現對a的canonicalization。

foo: testl %edi, %edi #4.10 je ..B1.4 # Prob 50% #4.10 testb %sil, %sil #4.15 je ..B1.4 # Prob 50% #4.15 movzbl %dl, %edx #4.20 movl $1, %ecx #4.10 testl %edx, %edx #4.10 cmovne %ecx, %edx #4.10 jmp ..B1.5 # Prob 100% #4.10 ..B1.4: # Preds ..B1.2 ..B1.1 xorl %edx, %edx #4.10 ..B1.5: # Preds ..B1.3 ..B1.4 movl %edx, %eax #4.10 ret #4.10

（然而這版本代碼看起來好奇怪…感覺不夠優化。請參考評論區里 @Starve Jokes 大大的分析）

同學們可以大開腦洞想想還有什麼組合的辦法來實現這個例子～ &>_&<

在像ARM這樣的平台上，許多指令都可以條件執行，這就更有趣了。例如說

_Bool foo(int a, int b, int c) { return a b c; }

這個例子在ARM64上用GCC 5.4來編譯，得到的結果是：

foo: cmp w1, 0 ccmp w2, 0, 4, ne ccmp w0, 0, 4, ne cset w0, ne ret

可以看到它除了第一個cmp之外，後面的幾條指令都使用條件執行的版本，例如說這個ccmp指令：

CCMP Wn, #uimm5, #uimm4, cond
Conditional Compare (immediate):
NZCV = if cond then CMP(Wn,uimm5) else uimm4.

於是上一條條件執行的比較指令如果設置了條件碼，後面的條件執行指令就不執行了，很自然地就實現了短路求值的語義。

========================================

順帶放個傳送門讓題主感受一下JavaScript的條件表達式的短路求值又是怎樣的情況：JavaScript對表達式的優化？ - RednaxelaFX 的回答 - 知乎

如果有同學對這種層面的知識感興趣，但是不知道從哪裡入手學習的話，下面是一些提到了如何實現短路求值語義的條件表達式的書：

CS:APP2e（《Computer Systems: A Programmer"s Perspective》），第3.6.4小節（Translating Conditional Branches）、3.6.6小節（Conditional Move Instructions）
《Programming Language Pragmatics》第4版的第6.1.5小節（Short-Circuit Evaluation）、第6.4.1小節（Short-Circuited Conditions）
龍書第一版，第8.4小節，還有第12.5小節講到BLISS編譯器的地方：《編譯原理技術與工具》的筆記-第741頁
龍書第二版（《Compilers: Principles, Techniques, and Tools》），第6.6.4小節（Control-Flow Translation of Boolean Expressions），第6.6.6小節（Boolean Values and Jumping Code），附錄A的A.6小節（Jumping Code for Boolean Expressions）
虎書（《Modern Compiler Implementation in Java》），第7章（Translation to Intermediate Code）
鯨書（《Advanced Compiler Design and Implementation》），第12.3小節（Algebraic Simplification and Reassociation）中提到了一小點：

Algebraic simplifications may also apply to relational operators, depending on the architecture being compiled for. For example, on a machine with condition codes, testing i &< j when i - j has just been computed can be done by branching, based on whether the "negative" condition-code bit was set by the subtraction, if the subtraction sets the condition codes. Note that the subtraction may cause an overflow also, while the less-than relation will not, but this can usually simply be ignored.

《自製編譯器》，書中沒有專門的章節提到這點，但是cbc的實現里有涉及。請參考我以前寫的讀書筆記：《ふつうのコンパイラをつくろう》的筆記-第263頁
《編譯原理實踐與指導教程》，第3.2.5小節（翻譯模式（基本表達式））中提到translate_Cond()，然後第3.2.6小節（翻譯模式（語句））中講解了translate_Cond()，用的是典型的「控制流」法實現。
《Optimizing Compilers for Modern Architectures》，第7.2.7小節在If-conversion的上下文中講解了一個簡化boolean expression的演算法。挺有趣的。
…等

僅供參考～

說來，順手舉些個「反例」：

《自己動手寫編譯器、鏈接器》，這本書里的「SC語言」把C語言中的邏輯運算符、 || 、 !，以及按位運算符、 | 、 ^ 、 ! 都省略了沒有實現。所以這個問題所關注的內容，這本書一概沒有涉及。這麼有趣的小細節居然被忽略了（嘆氣）。要知道原版TCC可是好好地通過「控制流」法把（在expr_land()）和 || （在expr_lor()）都實現了…