简单介绍一个编译器的结构（下）-Toy模板网

这篇具有很好参考价值的文章主要介绍了简单介绍一个编译器的结构（下）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

《编译器结构介绍（下）》主要是围绕编译器后端知识和技术展开的一个简单介绍，编译器前端技术的介绍在文章《编译器结构介绍（上）》中，如果对编译器整个技术栈不了解的话，先阅读上，再阅读下这篇文章，会更容易理解。

七、机器无关代码优化

经过中间代码生成过程产生的中间代码是正确的，但未必就是更“好”的，所以我们要对中间代码做一些优化，使其可以更“好”。这个“好”是个泛指，比如我们希望它生成的汇编代码量可以更小（GCC加-Os）、或者生成的汇编代码执行时的内存使用量更小、或者生成的汇编代码执行速度可以更快（GCC加-O[1/2/3]）。一般而言，最期望的“好”还是执行速度可以更快，我们接下来的介绍也是以这部分内容展开。

7.1 常见优化的案例

1）常数折叠

常量折叠（constant folding）指的是把常量表达式在编译时进行运算。譬如下面的 C 语言代码。

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

这里的 2* 1024 * 1024 是只含常量的表达式，因此可以在编译时进行计算。如果在编译时进行了运算，那么程序运行时就可以省略这次运算，因此可以获得更快的执行速度。这就是常量折叠。

2）代数简化

代数简化（algebraic simplification）指的是利用表达式的数学性质，对表达式进行简化。比如 x*1 这个表达式和 x 是一样的，可以直接替换成 x。同样地，x+0、x–0 等也可以替换成 x。而 x*0 恒等于 0，因此也可以直接用 0 来代替。

3）降低运算强度

降低运算强度（strength reduction）指的是用更高速的指令进行运算。
比如说 x*2 这个表达式，可以转换成加法运算 x+x。一般来说 CPU 计算加法比计算乘法效率更高，因此虽然两个式子效果相同，但 x+x 的运算速度更快。

把乘法转换成位移运算也是降低运算强度的一个例子。一般而言，求整数与 2 的阶乘的乘积可以用位移运算来优化。因为 x 乘以 4 和 x 左移 2 比特的效果是一样的，而后者速度更快。

4）削除共同子表达式

削除共同子表达式（common-subexpression elimination）指的是有重复运算的情况下，把多次运算压缩为一次运算的方法。譬如下面的 C 语言代码。

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

对 x 和 y 的计算中，a*b+c 这个部分的运算是一致的。这种情况下，因为 a*b+c 的值一样，所以不必要计算 2 次。只要把上述代码进行如下转换，这部分就可以只计算 1 次。

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

5）消除无效语句

消除无效语句（dead code elimination）指的是删除从程序逻辑上执行不到的指令。譬如下面的 C 语言代码毫无意义，完全可以删除掉。

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

6）函数内联

函数内联（function inlining）指的是把（小的）函数体直接嵌入到函数调用处，使得函数调用的作用域归零的方法。

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

假设在别的地方通过 region_size(2) 这个语句进行了函数调用，那么将其替换成2*1024 结果也是一样的。这就是函数内联。不过，因为 region_size 是全局作用域的函数，编译时的优化仅限于同一个文件中定义的函数调用。如果想对程序中所有的 region_size 函数调用都进行函数内联，那么链接时也需要进行代码优化。

另外，2*1024 又是只含常量的表达式，因此可以进一步用常量折叠的方法替换成 2048。这样组合运用多种优化方法可以获得更大的优化效果。以什么样的顺序组合各种优化方法，从而获取更好的优化效果，也是非常关键的一点。

7.2 优化的作用阶段

一般的编译器可以在以下几个时间节点上进行优化。

语义分析后（针对抽象语法树的优化）
生成中间代码后（针对中间代码的优化）
生成汇编代码后（针对汇编代码的优化）
链接后（针对程序整体的优化）

通常来说，越早进行，越能针对编程语言的结构、语义等进行优化。譬如在抽象语法树阶段，我们能简单地识别循环，因此在这个阶段能针对循环体进行优化。

在中间代码阶段可以进行语言无关的优化。该阶段可以使用从局部优化到全局优化的多种优化方法。此外，有时候还会根据情况把一段中间代码拆散，令其更容易进行优化。

一旦编译成了汇编代码，就很难对代码进行大范围的优化了。这个阶段的优化基本上集中在窥视孔优化这种方式上。

最后，链接后也可进行优化。链接后构成程序主体的各个处理流程（函数）已经固定，可以对程序整体进行大范围的解析优化。

【总结】与优化相关的内容很多，如果对这一块内容感兴趣，可以看我总结的文章，《编译器设计（九～十四）》全是优化相关的理论和技术。

八、汇编代码生成

当机器无关代码优化后，就会生成更“好”的、我们最终想要的中间代码。汇编代码生成就是将中间代码，编译成语义等价的汇编代码。这部分内容相比于优化，也不抽象，在实现起来要简单很多。

现在有以下C代码，文件名是main.c，定义了2个全局变量global_init_var和global_uninit_var，两个函数func1和main，静态变量static_var和static_var2，以及调用printf函数时使用到的字符串"%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;
}

现在用LLVM IR来表示上面C代码，文章来源地址https://www.toymoban.com/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