编译优化

对于编译器来说， 优化是必须要经历的一个阶段， 经过优化的代码可以拥有更小的体积和更高效的执行， 具体的内容可以参考龙书编译原理。对于clang这个编译器前端而言， 代码的优化程度有一下的几个等级：

1
2
3
4
5
6
7
8
9
10
11
12
Specify which optimization level to use:
	
	-O0 Means “no optimization”: this level compiles the fastest and generates the most debuggable code.
	-O1 Somewhere between -O0 and -O2.
	-O2 Moderate level of optimization which enables most optimizations.
	-O3 Like -O2, except that it enables optimizations that take longer to perform or that may generate larger code (in an attempt to make the program run faster).
	-O fast Enables all the optimizations from -O3 along with other aggressive optimizations that may violate strict compliance with language standards.
	-Os Like -O2 with extra optimizations to reduce code size.
	-Oz Like -Os (and thus -O2), but reduces code size further.
	-O Equivalent to -O2.
	-O4 and higher
	Currently equivalent to -O3

对于一个Hello world的C语言而言， 编译器对它的优化所占用的时间如下：
Syntax highlighting example

从整个编译的时间来看， 其所花的时间并不算太多（大概1%）。但却是很重要的一环。

编译器优化实现

在llvm中， 有一类被称为Pass的编程组件， 被用作实现优化。Pass的优化单位有以下几种：

1
2
3
4
1. Module
2. Basic Block
3. Function
4. instruction

针对不同的优化单元， 只要继承不同单元的Pass就好了。比如， 目前想对Module进行优化，
那么在代码中只要写如下的类就可以完成：

1
class MyPass : public ModulePass

其他的以此类推。

编译器自带一系列的优化组件， 根据我们在编译代码时候制定的不同的优化等级， 动态的增加对应的优化组件。

下面将介绍一个简单的编译器优化单元， ADCE(Aggressive Dead Code Elimination).

##ADCE (Aggressive Dead Code Elimination)

简介

优化准则中给出了如下的定义:

1
2
3
4
Dead Code is code whose result are never used in any useful
statement. "Useful statements", at first approximation, 
are simply output statements since those are the only ones 
that perform any action directly seen by the outside world

简单的来说， ADCE主要做的事情是删减那些没有运行过的指令。

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
procedure eliminateDeadCode(P)	
		//P is the procedure in which constants are to be propagated
		//Assume the availability of def-use chains for all the statements in P
		let worklist := {absolutely useful statements}
		
		while worklist ≠ Ø do begin
			x:= an arbitrary element of worklist
			make x useful
			worklist := worklist - {x}
			for all (y, x) ∈ defuse do
				if y is not marked useful then
					worklist := worklist ∪ {y};
				end
			end
		end
		delete every statement that is not marked useful
end eliminateDeadCode

简单的描述一下算法：

  1. 假设存在这样一个集合worklist， 这个集合里面的所有的指令都是一定会被使用的；
  2. 那么我们遍历这个指令， 并将这个集合中的所有的指令标为有效。
  3. 假设当前遍历出来的指令为X， 那么检查当前有哪些其他的指令使用了这条指令， 并将使这些指令标记为有效， 最后吧这些指令加入worklist；
  4. 循环执行1， 如果worklist为空， 那么停止循环。
  5. 最后遍历所有的指令， 删除没有被标记为有效的指令。

###LLVM中的实现

组件

LLVM中实现上述优化算法的组件被称作“ADCE”(Aggressive Dead Code Elimination).当用户在编译代码的时候制定了O0以上的优化选项， 就会调用该优化。

代码实现

  1. 数据准备方面:

    ADCE中使用了两个变长数组alive和worklist， worklist主要包含待扫描的指令， alive中的指令表示当前这些指令是有效的， 不用被删除的。
  2. worklist初始数据：

    扫描一遍全部指令， 如果当前的指令是TerminatorInst， DbgInfoIntrinsic， LandingPadInst 或者 当前指令有写内存的操作， 会抛出异常，call指令的返回值没有return（最后三种被统称为可能会导致副作用的指令集）。
  3. 最后扫面全部的指令， 如果当前的指令不在alive中， 直接删除。

Happy Hacking

Best Regards
Axis