以 GNU Toolchain 為探討對象,簡述編譯器如何運作,以及如何落實最佳化
Copyright (慣C) 2015, 2016, 2017 宅色夫
a = b;
這樣陳述,依據 C 語言標準,編譯器可認定牽涉到的變數在 load 或 store 的同一時刻,沒有其他執行緒在存取它們,因此允許多種最佳化,而目前越來越強大的現代編譯器所做的程式碼最佳化已超出許多人預料。背景知識回顧: The C++ Build Process Explained
[ Page 5 ]
先想想以下程式的執行: (hello.c)
int main() { return 1; }
當你在 GNU/Linux 下編譯和執行後 (gcc -o hello hello.c ; ./hello
),可用 echo $?
來取得程式返回值,也就是 1
,可是這個返回值總有機制來處理吧?所以你需要一套小程式來作,這就是 C runtime (簡稱 crt)。此外,還有 atexit
一類的函式,也需要 C runtime 的介入才能實現。
C 語言和一般的程式語言有個很重要的差異,就是 C 語言設計來滿足系統程式的需求,首先是作業系統核心,再來是一系列的工具程式,像是 ls, find, grep 等等,而我們如果忽略指標操作這類幾乎可以直接對應於組合語言的指令的特色,C 語言之所以需要 runtime,有以下幾個地方:
int main() { return 1; }
也就是 main()
結束後,要將 exit code 傳遞給作業系統的程式,這部份會放在 crt0
setjmp
和 longjmp
函式來存取,這需要額外的函式庫 (如 libgcc) 來協助處理 stack[ Page 16 ]
[ Page 30 ]
切換到 Re-introduction to Compiler
code generation 那頁展示 ARMv8-A 組合語言輸出
[ Page 31 ]
下圖說明如果沒有 IR 這樣的中間表示法,每個前端 (source files; human readable programming language) 直接對應到後端 (machine code) 的話,有太多種組合,勢必會讓開發量爆增。但如果先讓前端輸出 IR,然後 IR 再接到後端,這樣整體的彈性就大多了。
[ Page 36 - 38 ]
void foo(int *i1, int *i2, int *res)
{
for (int i = 0; i < 10; i++) {
*res += *i1 + *i2;
}
}
void foo(int *i1, int *i2, int *res)
{
int tmp = *i1 + *i2;
for (int i = 0; i < 10; i++) {
*res += tmp;
}
}
foo(&var, &var, &var)
來呼叫 foo()
,那很明顯就會發生問題了,*res
值的改變影響 *i1
、*i2
。因此編譯器不會採取該最佳化手段,因為不知道 caller 會怎麼傳遞數值。[ Page 40 ]
return 0
)延伸閱讀:
[ Page 43 ] GCC 可輸出包含 Basic Block 的CFG
gcc -c -fdump-tree-cfg=out test.c
[ Page 62 ] GCC 後端: Register Transfer Language (RTL)
gcc -fdump-rtl-expand xxx.c
[ Page 67 ]
假設我們有兩個有號整數: <stdint.h>
int32_t a, b;
然後原本涉及到分支的陳述:
if (b < 0) a++;
可更換為沒有分支的版本:
a -= b >> 31;
針對 C 語言編譯最佳化的常見策略:
void f (int *p) {
if (p) g(1);
if (p) g(2);
return;
}
void f (int *p) {
if (p) {
g(1);
g(2);
}
return;
}
for (int i = 1; i < 100; i++) {
if (i) g();
}
i
必然是大於等於 1
的正整數,於是可刪去 if 敘述:
for (int i = 1; i < 100; i++) {
g();
}
goto L1;
// do something
L1:
goto L2 // L1 branch is unnecessary
for (int i = 0; i < N; i++) {
if (x) a[i] = 0;
else b[i] = 0;
if (x)
for (int i = 0; i < N; i++)
a[i] = 0
else
for (int i = 0; i < N; i++)
b[i] = 0;
int f(int i) {
if (i > 0) {
g(i);
return f(i - 1)
}
else {
return 0;
}
}
int f (int i) {
entry:
if (i > 0) {
g(i);
i--;
goto entry;
}
return 0;
}
for (int i = 0; i < 100; i++) {
g();
}
for (int i = 0; i < 100; i += 2) {
g();
g();
}
int a[100][300];
for (i = 0; i < 300; i++)
for (j = 0; j < 100; j++)
a[j][i] = 0;
int a[100][300];
int *p = &a[0][0];
for (i = 0; i < 30000; i++)
*p++ = 0;
for (i = 0; i < 300; i++)
a[i] = a[i] + 3;
for (i = 0; i < 300; i++)
b[i] = b[i] + 4;
for (i = 0; i < 300; i++) {
a[i] = a[i] + 3;
b[i] = b[i] + 4;
}
for (i = 0; i < 10; i++)
arr[i] = obj.i + volatile_var;
t = obj.i;
for (i = 0; i < 10; i++)
arr[i] = t + volatile_var;
int x = 3;
int y = 4 + x; // 可換為 y = 7;
return (x + y) // 可換為 return 10;
unsigned short int s;
(s >> 20) /* all bits of precision have been shifted out, thus 0 */
(s > 0x10000) /* 16 bit value can't be greater than 17 bit, thus 0 */
(s == -1) /* can't be negative, thus 0 */
int f (int x, int y) {
return x % y;
}
int f (int x, int y) {
int tmp = x & (y - 1);
return (x < 0) ? ((tmp == 0) ? 0 : (tmp | ~(y - 1))) : tmp;
}
int a, b;
void f(int x, int y) {
goto L1; /* basic block 1 */
L2: /* basic block 2 */
b = x + y;
goto L3;
L1: /* basic block 3 */
a = x + y;
goto L2;
L3: /* basic block 4 */
return;
}
int a, b;
void f(int x, int y) {
a = x + y; /* basic block 1 */
b = x + y;
return;
}
int a, b;
void f(int x, int y) {
int tmp = x + y
a = b = tmp;
return;
}
int add(int x, int y) {
return x + y;
}
int sub(int x, int y) {
return add (x, -y);
}
int sub (int x, int y) {
return x - y;
}
[ Page 69 ]
static
的用意![ Page 71 ]
gcc 會把特定的 printf()
悄悄換成 puts()
,這有什麼好處?
printf()
本身就是個解譯器,要處理一堆格式,執行時間和字串長度並未完全相符合。但 puts()
就不一樣,只跟何時找到 null terminator 有關,行為明確多了,當然整體執行時間也更短。
為何 GCC 算是個 Compiler Driver ? 在使用上,我們要進行 link 也是會另外使用 ld , gcc 也可以當 linker 嗎?
ld 是真正的 linker,而 gcc 作為 compiler driver,自然也可以呼叫到 ld 作 linking
在此範例中,最佳化CFG,為何是將 bb0
最後加一個 goto bb2
,而 bb2
搬移到 bb3
下方. 如果原本尚未搬移前多一個 goto bb2
的動作,這樣最佳化的目的為何?
減少 compare-n-branch 的總次數
右邊的是接近組合語言的寫法
[ Page 65 ] GCC後端 管線排程
Instruction scheduling 透過將 instruction 重排的方式以減少 pipeline hazard,已達到 ILP(instruction-level parallelism) 的目的
[ Page 66 ]
在資訊領域中,有個術語叫做 peephole optimization ,對應到漢語成語即是「以管窺天」,即逐步擬定策略,消除沒作用或者冗餘的程式碼。以編譯器最佳化來說,此策略就是反覆在已經產生的組合語言或機械碼中,針對目標處理器架構的特性,套用一系列可能會對效能帶來助益的轉換規則,或者透過整體的分析,進行指令轉換,進而提升程式碼效能或空間佔用效率。乍聽之下這樣的轉換很侷限,但累積起來仍有機會對整體帶來顯著效益。
這個 peephole 可看做是個滑動窗口,編譯器在實施 peephole optimization 時,就僅分析在該窗口內的指令列表。每次轉換後,可能還會展現出相鄰窗口之間的特定改善空間,因此該策略仍可反覆套用。peephole optimization 在編譯器最佳化可體現於四個面向:
sh $0,6($sp)
sh $0, 4($sp)
sh $0, 2($sp)
sh $0, 0($sp)
ldc1 $f1, 0($sp)
完全可用指令 xor $f1,$f1,$f1
取代,這樣可省掉 5 次暫存器存取操作,效能改善的幅度可非常明顯。其中 sh
是 store 16bit 到某個位址,ldc1
是 load 64bit 到某個暫存器。xor
是 bitwise XOR 指令。
但這種指令序列的轉換和合成有個前提,必須保證這些指令按照順序執行,即這些指令之間,不能有其他 label。也就是說,這些指令必須在一個 basic block 塊中。當然,你也可在編譯器較前面階段的最佳化,針對該操作進行變換。這樣到 peephole optimization 時,就不再會有這樣的程式碼。
x = x + 0
, x = x * 1
之類的操作,就能直接避免產生程式碼 (因為數值不變),而 x = x * 2
, x = x / 2
之類的操作可改用左移或右移來實作。至於 x2 之類的指數運算可削弱為 x * x
的乘法運算,浮點數除以常數的運算可轉換為浮點數乘以常數的倒數。這些都是最佳化策略。那麼,為何是 "peephole" 這個看起來不文雅的詞呢?
11 世紀的英格蘭城市 Coventry 裡,人民的生活苦不堪言,這時市長 Leofric the Dane 的妻子 Godiva 請求讓人民減税;市長有意刁難,就說:如果 Godiva 願意裸體騎馬遊街一圈,這樣才可不加税。
隔日,Godiva 真的付諸行動,且每戶人家都關窗關門,不偷看美麗又善良的女主人。但有一個叫 Tom 的裁縫師按耐不住,從家中的窗戶往外偷看,之後他就遭到天譴失明了。所以從此時開始,偷窺狂就叫 peeping Tom,門上可偷窺的小洞孔就叫 peephole。
後來 peephole 廣泛用於電腦科學的術語。
這頁列出的程式碼為 ARM 組合語言,可參照 手機裡頭的 ARM 處理器 系列講座中關於 conditional execution 的部分
[ Page 73 ]
LTO 帶來的提昇,可參考 gcc-5 的釋出說明 :(和 Firefox 有關)
During link-time optimization of Firefox, this pass unifies about 31000 functions, that is 14% overall.
About 50% of virtual calls in Firefox are now speculatively devirtualized during link-time optimization.
GCC 前端:
GCC 中端:
GCC 後端:
[ Page 78 ]
介紹完編譯工具後,來講點大概編譯的流程還有格式
先來看這張圖:
.c 和 .s 比較常見先略過,以下解釋 .coff 和 .elf:
GAS syntax (AT&T)
.file “test.s”
.text
.global main
.type main, %function
main:
MOV R0, #100
ADD R0, R0, R0
SWI #11
.end
由一個簡短的 code 來介紹,在程式的 section 會看到 .
,是定義一些 control information,如 .file
, .global
等
%function
: 是一種 type 的表示方式 .type
後面可以放 function 或者是 object 來定義之SWI #11
: 透過 software interrupt 去中斷現有程式的執行,通常會存取作業系統核心的服務 (system call).end
: 表示是 the end of the program注意,在後來的 ARM 中,一律以 "SVC" (Supervisor Call) 取代 "SWI",但指令編碼完全一致
以下簡介 ELF 中個別 section 的意義: (注意: ELF section 的命名都由 .
開頭)
.bss
: 表示未初始化的 data,依照定義,系統會賦予這些未初始化的值 0.data
: 表示有初始過的 data.dynamic
: 表示 dynamic linking information.text
: 表示 "text" 或者是 executable instructions釐清用語:
"argument" 和 "parameter" 在中文翻譯一般寫「參數」或「引數」,常常混淆
"argument" 的重點是「傳遞給函式的形式」,所以在 C 語言程式寫 int main(int argc, char *argv[])
時,我們稱 argc 是 argument count,而 argv 是 argument vector
"parameter" 的重點是「接受到的數值」,比方說 C++ 有 parameterized type,就是說某個型態可以當作另外一個型態的「參數」,換個角度說,「型態」變成像是數值一樣的參數了。
在撰寫程式常常會使用呼叫 ( call ),在上圖中高階語言直接將參數傳入即可,那麼在組語的時候是如何實作的呢?是透過暫存器? Stack ? memory ? In what order ?我們必須要有個 protocol 來規範
ARM Procedure Call Standard (AAPCS)
以下測試一個參數數量為 4 和 5 的程式:
int add4(int a, int b, int c , int d) {
return a + b + c + d;
}
int add5(int a, int b, int c , int d, int e) {
return a + b + c + d + e;
}
程式編譯後,用 objdump 組譯會得到類似以下:
紅框標注的是比左邊多出的程式碼,從這裡可以看到參數 1-4 是存在 R0-R3,而第 5個參數存在原本 sp + 4 的位置,隨著程式碼進行 R0-R3 存在 stack 中,圖下為 stack 恢復前的樣子:
因此若寫到需要輸入 5 個或以上的參數時,就必須存取外部記憶體,這也導致效能的損失。
下圖為 ARM C program 標準配置記憶體空間的概念圖:
通常 procedure 存取 operands 透過以下幾種方式:
用幾張圖來表現出存取 operands 時,stack 的變化:
圖下為 passed on a register:
圖下為存取 local variables:
在使用 Cross Compiler 時,gcc 前面總有一串術語,例如:
這樣 arm-none-linux-gnueabi-
稱為 target tripe,通常規則如下:
<target>[<endian>][-<vender>]-<os>[-<extra-info>]
none
先以常見 x86 的平台為例子:
gcc 搭配編譯參數 -v
可見以下:
Target: x86_64-redhat-linux
<target>-<vendor>-<os>
的形式
Android Toolchain:
Target: arm-linux-androideabi
<target>-<os>-<extra-info>
androideabi : 雖然 Android 本身是 Linux 但其 ABI 細節跟一般 linux 不同
Linaro ELF toolchain:
Target: arm-none-eabi
<target>-<vender>-<extra-info>
Linaro Linux toolchain:
Target: arm-linux-gnueabihf
<target><endian>-<os>-<extra-info>
Linaro big-endian Linux toolchain:
Target: armeb-linux-gnueabihf
<target><endian>-<vender>-<extra-info>
Buildroot 2015-02
Target: arm-buildroot-linux-uclibcgnueabi
<target>-<vender>-<os>-<extra-info>
由以上眾多 pattern 大概可以歸納出一些事情:
source: http://kitoslab.blogspot.tw/2015/08/target-triple.html
為何我們要理解編譯器?這是電腦科學最早的思想體系
[ Interpreter, Compiler, JIT from scratch ]
[ Virtual Machine Constructions for Dummies ]
[ Page 14 ]
getc()
返回型態是 int
,而非 char
呢?因為要處理 EOF
(詳情自行 man getc
)EOF
在 Brainf*ck 的 I/O 操作沒有具體定義TODO