Linus Torvalds 教你分析 gcc 行為

[Naetw]

最近進行 Jserv 開設的 LInux 核心設計，第三週有一個小分享，是關於 Linux 核心的某個小 patch 遇到的神奇的 gcc 行為，覺得 Linus 推論、分析的過程很有趣，紀錄一下。

原始 email 內容
在 bugzilla 上的討論

SSA Form

推論的根本跟 SSA Form 有關，因此先簡單紀錄 SSA Form 的知識。

Intro

在編譯器設計中，static single assignment form 是一種建構 IR 的方式（或是說 IR 的特性），要求每個變數都只能被指派一次。原先在 IR 中的各個變數會被分成好幾個「版本」，來符合上述要求。SSA form 使得 Use-Def chains [1] 十分明確，有助於簡化某些最佳化行為。

一般的形式要轉換成 SSA 形式最困難且重要的部分就是插入 Φ (Phi) 函式，phi 函式並非真的一條機器指令，它像是一張標籤，代表著這邊的資料會是「眾多運算元的其中一個，但不確定是哪個」，真的要確定的話必須根據實際走的流程才能確定。一個很簡易的 phi 函式範例：

if (…)
  a_1 = 5;
else if (…)
  a_2 = 2;
else
  a_3 = 13;

# a_4 = PHI <a_1, a_2, a_3>
return a_4;

決定 phi 函式使用時機與對象是一個很複雜的問題，而 dominance frontiers 可以很有效率的解決這個問題。

Dominance Frontiers

首先介紹 dominator 的觀念。

在 CFG (Control-Flow Graph) 中一個節點 A strictly dominates 另一個不同的節點 B 代表著要到到 B 點前一定要得經過 A，換句話說就是從進入點 (entry node) 開始，到 B 的所有可能路徑上一定會經過 A。這是個很重要的觀念，在程式執行的流程圖中，有了 dominator 的概念，我們可以知道若 A dominates B，則在跑到 B 點時 A 點的指令一定跑過了。

接著來定義 dominance frontier。

當節點 A 沒有 strictly dominates 一個節點 B 但是 dominates 某個 B 的 immediate predecessor，則我們稱節點 B 是節點 A 的 dominance frontier（A 也可能是 B 的 immediate predecessor，在定義中，節點 dominates 自己，但沒有 strictly，因為 strictly 的定義是需要兩個不同的節點）。

上面文字可能有些複雜，開發 SSA 的作者之一 Kenneth Zadeck 在 GCC & GNU Toolchain Developers' Summit 2004 的 keynote 中，有介紹 SSA，他對於 dominance frontier 的描述是我目前看到最簡單直白的：

DF(n) contains the set of nodes that are immediately reachable in the CFG from Dom(n) but not in Dom(n) - Kenneth Zadeck

這裡的 Dom(n) 是一個 n 所 dominates 的所有點的集合，但是簡報中他的沒有定義的很清楚，依照他的圖示，他的 Dom() 應該是 dominates 而不是 strictly dominates。因此上圖的 Dom(n) 裡應該要有 n 自己，否則 Dom(7) 是無法推出 DF(7) = {9} 的。（因此我又找了幾篇，目前最符合我理解的是哈佛工學院的課程講義 p.23）

[1]: Use-Definition Chain: 對於每次使用某變數，所有可能的定義列表（在列表中的定義與使用之間不可以有其它定義；在這邊的定義通常是指指派 (assignment)）。換言之，就是在使用某變數的時候，當下該變數的資料所有可能的來源，像是在某個 if-else 後使用到變數 x，而 x 在 if-else 各自的區塊可能被指派（定義）不同的值。

正文

事情大意就是對於某個要修掉 uninitialized return value 的 patch，有人發現 gcc 並沒有任何警告，想說是不是 bug，然後 Linus 隨手做了個實驗並回覆，也到 gcc 的 bugzilla 上回報。

整段程式碼的可以大致簡化成下面的模樣：

int ret;  /* UNINITIALIZED */

if (somecondition) {
    ret = functioncall(x);
    if (ret)
        return ret;
}
// .. some more work ..
return ret;   /* Possibly uninitialized return value! */

針對上面這段程式碼，Linus 針對了 if (ret) return ret; 用一個巨集包裝起來：

int ret;  /* UNINITIALIZED */

if (somecondition) {
    ret = functioncall(x);
#ifndef HIDE_PROBLEM
    if (ret)
        return ret;
#endif
}
// .. some more work ..
return ret;   /* Possibly uninitialized return value! */

並用編譯指令的參數去控制，發現到如果把那段程式碼隱藏起來，那 gcc 就會如預期的提出警告，但是如果有那段程式碼，gcc 就十分安靜。

[torvalds@i7 ~]$ gcc -O2 -S -Wall test.c
[torvalds@i7 ~]$ gcc -O2 -S -Wall -DHIDE_PROBLEM test.c
   test.c: In function ‘shmem_link’:
   test.c:60:9: warning: ‘ret’ may be used uninitialized in this
function [-Wmaybe-uninitialized]
     return ret;
            ^~~

所以他做出了兩個推論：

• gcc 認為 "ret" 只有一個 assigment
• 在與 assigment 同一個程式區塊中，有一個針對 "ret" 是否為 nonzero 的測試

他認為第一點造成 gcc 認為那個 assignment 是一個 defining assignment 也就是像是宣告並給初始值一樣，而第二點讓 gcc 決定 "ret" 一定會是 0 如果他沒有通過那個 if 並直接 return 的話（後面 Linus 也呈現了編譯出來的機器碼轉換成組合語言，發現在最下面的 return 前有個指令特地將回傳值歸零）。

在對 SSA 有認識後就不難理解像第一點那樣的推論，至於跟第二點組合在一起後就會警告就會消失的原因：在 GCC 4 引進了 SSA 之後，CCP (Conditional Constant Propagation) 在適當的情況下會針對未初始化的變數去做假設，來進行更後續的最佳化（像是 DCE）。這邊討論的 CCP 技術細節不是很理解，但是看到這種像是對於未初始化的變數，編譯器假設一個方便的數值的行為（本文探討的例子也是 gcc 假設為 0 而造成的結果），算是稍稍對於之前看到的「Undefined Behavior 可以幫助編譯器最佳化」這件事有點感覺了。（另外，稍微翻了一下原始的 bug report，實際上它在 2004 年就被回報過了，且基本上每隔幾年就會被提出類似的 bug，後來也確定說決定不修了，原因看起來是影響不大且有點複雜不好修。）

Reference

• https://en.wikipedia.org/wiki/Static_single_assignment_form
• https://gcc.gnu.org/onlinedocs/gccint/SSA.html
• https://www.cs.cmu.edu/~fp/courses/15411-f08/lectures/09-ssa.pdf
• http://www.naturalbridge.com/GCC2004Summit.pdf

[Naetw]

SSA 的 dominance frontier 後續還有 IDF 以及計算 DF(n) 的演算法，有空的話應該會來撰寫部落格文。

[Naetw]

有時間可以讀讀看 CCP 的運作。