七、機(jī)器無關(guān)代碼優(yōu)化

經(jīng)過中間代碼生成過程產(chǎn)生的中間代碼是正確的，但未必就是更“好”的，所以我們要對(duì)中間代碼做一些優(yōu)化，使其可以更“好”。這個(gè)“好”是個(gè)泛指，比如我們希望它生成的匯編代碼量可以更小（GCC加-Os）、或者生成的匯編代碼執(zhí)行時(shí)的內(nèi)存使用量更小、或者生成的匯編代碼執(zhí)行速度可以更快（GCC加-O[1/2/3]）。一般而言，最期望的“好”還是執(zhí)行速度可以更快，我們接下來的介紹也是以這部分內(nèi)容展開。

7.1 常見優(yōu)化的案例

1）常數(shù)折疊

常量折疊（constant folding）指的是把常量表達(dá)式在編譯時(shí)進(jìn)行運(yùn)算。譬如下面的 C 語言代碼。

int max_size = 2 * 1024 * 1024; /* 2MB */

這里的 2* 1024 * 1024 是只含常量的表達(dá)式，因此可以在編譯時(shí)進(jìn)行計(jì)算。如果在編譯時(shí)進(jìn)行了運(yùn)算，那么程序運(yùn)行時(shí)就可以省略這次運(yùn)算，因此可以獲得更快的執(zhí)行速度。這就是常量折疊。

2）代數(shù)簡化

代數(shù)簡化（algebraic simplification）指的是利用表達(dá)式的數(shù)學(xué)性質(zhì)，對(duì)表達(dá)式進(jìn)行簡化。比如 x*1 這個(gè)表達(dá)式和 x 是一樣的，可以直接替換成 x。同樣地，x+0、x–0 等也可以替換成 x。而 x*0 恒等于 0，因此也可以直接用 0 來代替。

3）降低運(yùn)算強(qiáng)度

降低運(yùn)算強(qiáng)度（strength reduction）指的是用更高速的指令進(jìn)行運(yùn)算。
比如說 x*2 這個(gè)表達(dá)式，可以轉(zhuǎn)換成加法運(yùn)算 x+x。一般來說 CPU 計(jì)算加法比計(jì)算乘法效率更高，因此雖然兩個(gè)式子效果相同，但 x+x 的運(yùn)算速度更快。

把乘法轉(zhuǎn)換成位移運(yùn)算也是降低運(yùn)算強(qiáng)度的一個(gè)例子。一般而言，求整數(shù)與 2 的階乘的乘積可以用位移運(yùn)算來優(yōu)化。因?yàn)?x 乘以 4 和 x 左移 2 比特的效果是一樣的，而后者速度更快。

4）削除共同子表達(dá)式

削除共同子表達(dá)式（common-subexpression elimination）指的是有重復(fù)運(yùn)算的情況下，把多次運(yùn)算壓縮為一次運(yùn)算的方法。譬如下面的 C 語言代碼。

int x = a * b + c + 1;
int y = 2 + a * b + c;

對(duì) x 和 y 的計(jì)算中，a*b+c 這個(gè)部分的運(yùn)算是一致的。這種情況下，因?yàn)?a*b+c 的值一樣，所以不必要計(jì)算 2 次。只要把上述代碼進(jìn)行如下轉(zhuǎn)換，這部分就可以只計(jì)算 1 次。

int tmp = a * b + c;
int x = tmp + 1;
int y = 2 + tmp;

5）消除無效語句

消除無效語句（dead code elimination）指的是刪除從程序邏輯上執(zhí)行不到的指令。譬如下面的 C 語言代碼毫無意義，完全可以刪除掉。

if (0) {
 fprintf(stderr, "program started\n");
}

6）函數(shù)內(nèi)聯(lián)

函數(shù)內(nèi)聯(lián)（function inlining）指的是把（小的）函數(shù)體直接嵌入到函數(shù)調(diào)用處，使得函數(shù)調(diào)用的作用域歸零的方法。

int region_size(int n_block) {
 return n_block * 1024;
}

假設(shè)在別的地方通過 region_size(2) 這個(gè)語句進(jìn)行了函數(shù)調(diào)用，那么將其替換成2*1024 結(jié)果也是一樣的。這就是函數(shù)內(nèi)聯(lián)。不過，因?yàn)?region_size 是全局作用域的函數(shù)，編譯時(shí)的優(yōu)化僅限于同一個(gè)文件中定義的函數(shù)調(diào)用。如果想對(duì)程序中所有的 region_size 函數(shù)調(diào)用都進(jìn)行函數(shù)內(nèi)聯(lián)，那么鏈接時(shí)也需要進(jìn)行代碼優(yōu)化。

另外，2*1024 又是只含常量的表達(dá)式，因此可以進(jìn)一步用常量折疊的方法替換成 2048。這樣組合運(yùn)用多種優(yōu)化方法可以獲得更大的優(yōu)化效果。以什么樣的順序組合各種優(yōu)化方法，從而獲取更好的優(yōu)化效果，也是非常關(guān)鍵的一點(diǎn)。

7.2 優(yōu)化的作用階段

一般的編譯器可以在以下幾個(gè)時(shí)間節(jié)點(diǎn)上進(jìn)行優(yōu)化。

1. 語義分析后（針對(duì)抽象語法樹的優(yōu)化）
2. 生成中間代碼后（針對(duì)中間代碼的優(yōu)化）
3. 生成匯編代碼后（針對(duì)匯編代碼的優(yōu)化）
4. 鏈接后（針對(duì)程序整體的優(yōu)化）

通常來說，越早進(jìn)行，越能針對(duì)編程語言的結(jié)構(gòu)、語義等進(jìn)行優(yōu)化。譬如在抽象語法樹階段，我們能簡單地識(shí)別循環(huán)，因此在這個(gè)階段能針對(duì)循環(huán)體進(jìn)行優(yōu)化。

在中間代碼階段可以進(jìn)行語言無關(guān)的優(yōu)化。該階段可以使用從局部優(yōu)化到全局優(yōu)化的多種優(yōu)化方法。此外，有時(shí)候還會(huì)根據(jù)情況把一段中間代碼拆散，令其更容易進(jìn)行優(yōu)化。

一旦編譯成了匯編代碼，就很難對(duì)代碼進(jìn)行大范圍的優(yōu)化了。這個(gè)階段的優(yōu)化基本上集中在窺視孔優(yōu)化這種方式上。

最后，鏈接后也可進(jìn)行優(yōu)化。鏈接后構(gòu)成程序主體的各個(gè)處理流程（函數(shù)）已經(jīng)固定，可以對(duì)程序整體進(jìn)行大范圍的解析優(yōu)化。

【總結(jié)】與優(yōu)化相關(guān)的內(nèi)容很多，如果對(duì)這一塊內(nèi)容感興趣，可以看我總結(jié)的文章，《編譯器設(shè)計(jì)（九～十四）》全是優(yōu)化相關(guān)的理論和技術(shù)。

八、匯編代碼生成

當(dāng)機(jī)器無關(guān)代碼優(yōu)化后，就會(huì)生成更“好”的、我們最終想要的中間代碼。匯編代碼生成就是將中間代碼，編譯成語義等價(jià)的匯編代碼。這部分內(nèi)容相比于優(yōu)化，也不抽象，在實(shí)現(xiàn)起來要簡單很多。

現(xiàn)在有以下C代碼，文件名是main.c，定義了2個(gè)全局變量global_init_var和global_uninit_var，兩個(gè)函數(shù)func1和main，靜態(tài)變量static_var和static_var2，以及調(diào)用printf函數(shù)時(shí)使用到的字符串"%d\n"。

int global_init_var = 84;
int global_uninit_var;
 
void func1(int i){
	printf("%d\n", i);
}
 
int main(void){
	static int static_var = 85;
	static int static_var2;
 
	int a = 1;
	int b;
 
	func1(static_var + static_var2 + a + b);
 
	return a;
}

現(xiàn)在用LLVM IR來表示上面C代碼，文章來源地址http://www.zghlxwxcb.cn/news/detail-485555.html

source_filename = "main.c"

@global_init_var = dso_local global i32 84, align 4
@.str = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1
@main.static_var = internal global i32 85, align 4
@main.static_var2 = internal global i32 0, align 4
@global_uninit_var = dso_local global i32 0, align 4

define dso_local void @func1(i32 noundef %0) {
  %2 = alloca i32, align 4
  store i32 %0, i32* %2, align 4
	...
  ret void
}

declare i32 @printf(i8* noundef, ...)

define dso_local i32 @main() {
  %1 = alloca i32, align 4
  %2 = alloca i32, align 4
 	...
  ret i32 %11 
}

.file   "main.c"
        .data
.globl global_init_var
        .align  4
        .type   global_init_var,@object
        .size   global_init_var,4
global_init_var:
.long   84  
        .align  4
        .type   static_var.0,@object
        .size   static_var.0,4
static_var.0:
.long   85  
        .section        .rodata
.LC0:
        .string "%d\n"
        .text
.globl func1
        .type   func1,@function
func1:
        pushl   %ebp
        movl    %esp, %ebp
        movl    8(%ebp), %eax
        pushl   %eax
        movl    $.LC0, %eax
        pushl   %eax
        call    printf
        addl    $8, %esp
.L0:
        movl    %ebp, %esp
        popl    %ebp
        ret
        .size   func1,.-func1
.globl main
        .type   main,@function
main:
        pushl   %ebp
        movl    %esp, %ebp
        subl    $8, %esp
        movl    $1, %eax
        movl    %eax, -4(%ebp)
        movl    static_var.0, %eax
        movl    static_var2.0, %ecx
        addl    %ecx, %eax
        movl    -4(%ebp), %ecx
        addl    %ecx, %eax
        movl    -8(%ebp), %ecx
        addl    %ecx, %eax
        pushl   %eax
        call    func1
        addl    $4, %esp
        movl    -4(%ebp), %eax
        jmp     .L1
.L1:
        movl    %ebp, %esp
        popl    %ebp
        ret
        .size   main,.-main
        .comm   global_uninit_var,4,4
.local static_var2.0
        .comm   static_var2.0,4,4 

九、目標(biāo)代碼生成

十、可執(zhí)行文件生成

十一、加載可執(zhí)行文件

到了這里，關(guān)于簡單介紹一個(gè)編譯器的結(jié)構(gòu)（下）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！