您当前的位置:首页 > 计算机 > 编程开发 > 编译原理

编译原理之代码优化

时间:05-17来源:作者:点击数:

代码优化的目标、对象、范围和策略

代码优化的目标

  • 代码优化的目标,是优化程序对计算机资源的使用。我们平常最关心的就是 CPU 资源,最大效率地利用 CPU 资源可以提高程序的性能。代码优化有时候还会有其他目标,比如代码大小、内存占用大小、磁盘访问次数、网络通讯次数等等。

代码优化的对象

从代码优化的对象看,大多数的代码优化都是在 IR 上做的,而不是在前一阶段的 AST 和后一阶段汇编代码上进行的,为什么呢?

  • 其实,在 AST 上也能做一些优化,比如在讲前端内容的时候,我们曾经会把一些不必要的AST 层次削减掉(例如 add->mul->pri->Int,每个父节点只有一个子节点,可以直接简化为一个 Int 节点),但它抽象层次太高,含有的硬件架构信息太少,难以执行很多优化算法。 在汇编代码上进行优化会让算法跟机器相关,当换一个目标机器的时候,还要重新编写优化代码。所以,在 IR 上是最合适的,它能尽量做到机器独立,同时又暴露出很多的优化机会。

代码优化的范围

从优化的范围看,分为本地优化、全局优化和过程间优化。

  • 优化通常针对一组指令,最常用也是最重要的指令组,就是基本块。基本块的特点是:每个基本块只能从入口进入,从最后一条指令退出,每条指令都会被顺序执行。因着这个特点,我们在做某些优化时会比较方便。比如,针对下面的基本块,我们可以很安全地把第 3 行的“y:=t+x”改成“y:= 3 * x”,因为 t 的赋值一定是在 y 的前面:
BB1:
	t:=2 * x 
	y:=t + x 
	Goto BB2

  • 这种针对基本块的优化,我们叫做本地优化(Local Optimization)。
  • 超越基本块的范围进行分析,我们需要用到控制流图(Control Flow Graph,CFG)。CFG 是一种有向图,它体现了基本块之前的指令流转关系。如果从 BB1 的最后一条指令是跳转到 BB2,那么从 BB1 到 BB2 就有一条边。一个函数(或过程)里如果包含多个基本块,可以表达为一个 CFG
    在这里插入图片描述
  • 比全局优化更大范围的优化,叫做过程间优化(Inter-procedural Optimization),它能跨越函数的边界,对多个函数之间的关系进行优化,而不是仅针对一个函数做优化。

代码优化的策略

  • 最后,你不需要每次都把代码优化做彻底,因为做代码优化本身也需要消耗计算机的资源。所以,你需要权衡代码优化带来的好处和优化本身的开支这两个方面,然后确定做多少优化。比如,在浏览器里加载 JavaScript 的时候,JavaScript 引擎一定会对 JavaScript 做优化,但如果优化消耗的时间太长,界面的响应会变慢,反倒影响用户使用页面的体验,所以JavaScript 引擎做优化时要掌握合适的度或调整优化时机。

一些优化的场景

代数优化(Algebraic Optimazation)

  • 代数优化是最简单的一种优化,当操作符是代数运算的时候,你可以根据学过的数学知识进行优化。
  • 比如“x:=x+0 ”这行代码,操作前后 x 没有任何变化,所以这样的代码可以删掉;又比如“x:=x0” 可以简化成“x:=0”;对某些机器来说,移位运算的速度比乘法的快,那么“x:=x8”可以优化成“x:=x<<3”。

常数折叠(Constant Folding)

  • 它是指,对常数的运算可以在编译时计算,比如 “x:= 20 * 3 ”可以优化成“x:=60”。另外,在 if 条件中,如果条件是一个常量,那就可以确定地取某个分支。比如:“If 2>0Goto BB2” 可以简化成“Goto BB2”就好了。

删除不可达的基本块

  • 有些代码永远不可能被激活。比如在条件编译的场景中,我们会写这样的程序:“if(DEBUG) {…}”。如果编译时,DEBUG 是一个常量 false,那这个代码块就没必要编译了。

删除公共子表达式(Common Subexpression Elimination)

  • 下面这两行代码,x 和 y 右边的形式是一样的,如果这两行代码之间,a 和 b 的值没有发生变化(比如采用 SSA 形式),那么 x 和 y 的值一定是一样的。
x := a + b 
y := a + b
  • 那我们就可以让 y 等于 x,从而减少了一次“a+b”的计算,这种优化叫做删除公共子表达式
x := a + b 
y := x

拷贝传播(Copy Propagation)和常数传播(Constant Propagation)

  • 下面的示例代码中,第三行可以被替换成“z:= 2 * x”, 因为 y 的值就等于 x,这叫做拷贝传播
x := a + b
y := x
z := 2 * y
  • 如果 y := 10,常数 10 也可以传播下去,把最后一行替换成 z:= 2 * 10,这叫做常数传播。再做一次常数折叠,就变成 z:=20 了。

死代码删除(Ded code elimintation)

  • 在上面的拷贝传播中,如果没有其他地方使用 y 变量了,那么第二行就是死代码,就可以删除掉,这种优化叫做死代码删除。

一个优化可能导致另一个优化,比如,拷贝传播导致 y 不再被使用,我们又可以进行死代码删除的优化。所以,一般进行多次优化、多次扫描。

数据流分析

基于 CFG 做优化分析的方法框架,就叫做数据流分析

实例图示

  • 在做全局优化时,情况就要复杂一些:代码不是在一个基本块里简单地顺序执行,而可能经过控制流图(CFG)中的多条路径。我们来看一个例子(例子由 if 语句形成了两条分支语句):
    在这里插入图片描述

基于这个 CFG,我们可以做全局的活跃性分析。从最底下的基本块开始,倒着向前计算活跃变量的集合(也就是从基本块 5 倒着向基本块 1 计算)。

  • 需要注意,对基本块 1 进行计算的时候,它的输入是基本块 2 的输出,也就是{a, b,c},和基本块 3 的输出,也就是{a, c},计算结果是这两个集合的并集{a, b, c}。也就是说,基本块 1 的后序基本块,有可能用到这三个变量。这里就是与本地优化不同的地方,我们要基于多条路径来计算。
    在这里插入图片描述
  • 基于这个分析图,我们马上发现 y 变量可以被删掉(因为它前面的活变量集合{a}不包括y,也就是不被后面的代码所使用),并且影响到了活跃变量的集合。
    在这里插入图片描述
  • 删掉 y 变量以后,再继续优化一轮,会发现 d 也可以删掉。
    在这里插入图片描述
  • d 删掉以后,2 号基本块里面已经没有代码了,也可以被删掉,最后的 CFG 是下面这样:
    在这里插入图片描述
  • 到目前为止,我们发现:全局优化总体来说跟本地优化很相似,唯一的不同,就是要基于多个分支计算集合的内容(也就是 V 值)。在进入基本块 1 时,2 和 3 两个分支相遇(meet),我们取了 2 和 3V 值的并集。这就是数据流分析的基本特征

半格理论

  • 首先,半格是一种偏序集。偏序集就是集合中只有部分成员能够互相比较大小。举例来说会比较直观。在做全局活跃性分析的时候,{a, b, c}和{a, c}相遇,产生的新值是{a, b, c}。我们形式化地写成{a, b, c} Λ {a, c} = {a, b, c}。这时候我们说{a, b, c}是可以跟{a, c}比较大小的。那么哪个大哪个小呢?
    • 如果 XΛY=X,我们说 X<=Y。
  • 所以,{a, b, c}是比较小的,{a, c}是比较大的。
  • 当然,{a, b, c}也可以跟{a, b}比较大小,但它没有办法跟{c, d}比较大小。所以把包含了{{a,b, c}、{a, c}、{a, b}、{c, d}…}这样的一个集合,叫做偏序集,它们中只有部分成员之间可以比较大小。哪些成员可以比较呢?就是下面的半格图中,可以通过有方向的线连起来的。
  • 半格可以画成图形,理解起来更直观,假设我们的程序只有 a, b, c 三个变量,那么这个半格画成图形是这样的:
    在这里插入图片描述
  • 沿着上面图中的线,两个值是可以比较大小的,按箭头的方向依次减少:{}>{a}>{a, b}> {a,b, c}。如果两个值之间没有一条路径,那么它们之间就是不能比较大小的,就像{a}和{b}就不能比较大小。
  • 对于这个半格,我们把{}(空集)叫做 Top,Top 大于所有的其他的值。而{a, b, c}叫做Bottom,它是最小的值。
    • 如果一个偏序集中,任意两个元素都有最大下界,那么这个偏序集就叫做交半格(MeetSemilattice)。
    • 与此相对应的,如果集合中的每个元素都有最小上界(Least Upper Bound),那么这个偏序集叫做并半格(Join Semilattice)。
    • 如果一个偏序集既是交半格,又是并半格,我们说这个偏序集是一个格,示例的这个偏序集就是一个格。
方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门