1. 代码优化基本元素#

1.1 程序基本块#

一个给定的程序，往往可以分为许多程序基本块，而且最好是极大程序基本块。

定义 $1.1.1$ 极大程序基本块是一个只有一个入口和出口的语句序列。

入口语句只能是：

程序的第一条语句。
跳转语句(包括条件跳转和无条件跳转)的目标语句。
条件跳转语句的下一条语句。

先确定程序的入口语句，接着对每一条入口语句查找最近的出口语句，出口语句是这样的语句：

下一个入口语句的上一条语句
跳转语句
停语句

入口语句和出口语句间(包括入口和出口)的语句就是一个程序基本块。

1.2 流图#

定义 $2.1.1$ 流图，也叫控制流图，是一张以程序基本块为节点的有向图。把包含程序第一条语句的的程序基本块叫做首节点。
为这张图连边：
如果节点 $i$ 和 $j$ 满足以下条件之一[基本块 $i$ 可以到基本块 $j$ ]：
  1.  节点$i$和$j$是顺序相邻的，并且**$i$基本块的出口不是无条件跳转、停语句、返回语句**
  1.  节点$i$的出口是跳转语句，并且跳转到$j$的入口语句上。

TIP
流图的首节点可以到达其他所有节点。

定义 $2.1.2$ 某一个基本块 $i$ 能够到达的所有基本块 $j$ 的集合叫做基本块 $i$ 的后继基本块。可以从基本块 $j$ 到达基本块 $i$ 的集合叫做基本块 $i$ 的前驱基本块。

::: tip

某个基本块 $j$ 可以既是基本块 $i$ 的前驱基本块也是后继基本块。

:::

1.3 循环#

定义 $3.1.1$ 流图中的首节点到每一个其他节点 $i$ 都有通路，这些通路都经过点 $j$ 的集合叫做节点 $i$ 的支配集，节点 $j$ 支配节点 $i$ (j DOM i)

TIP
首节点 $n_0$ 支配其他所有节点。
节点 $i$ 支配节点 $i$ 自己。

TIP
节点 $i$ 的支配集合 $S_i = (\mathop{\cap}\limits_{j\in B}S_j) \cup \{i\}$ ，其中集合 $B = \{j| \exists 边(j\to i)\}$ ，即节点 $j$ 有边直接到达 $i$ 。

定义 $3.1.2$ 如果边 $(i,j)$ 的节点 $j \ DOM \ i$ ，那么这条边就是一条回边。

经由回边可以得到回边的自然循环。

定义 $3.1.3$ 自然循环是一个由回边定义的子图。回边 $(n,d)$ 的自然循环的节点集合 $B = \{n,d\} \cup S，S = \{i|i有一条不经过d的通路到达n\}$ 。

定理 $3.1.1$ 可以证明，节点 $d$ 一定有到其他节点的通路。

反证法：
$\begin{align} &假设节点d没有一条通路到达循环中的其他节点x。\\ &根据流图的定义，首节点一定有路径到达节点x,但根据假设，这些路径都不经过d。\\ &根据自然循环的定义，x有一条不经过d的路径到达n。 \\ &于是首节点可以先经过x，再到达n，可以不经过d。因此d不支配n，矛盾。 \end{align}$

因此所有节点都能达到节点 $n$ ， $n$ 可以到达 $d$ [经过回边] => 所有节点可以到达节点 $d$ ， $d$ 又可以到达所有节点。自然循环子图是一个强连通分量。

定理 $3.1.2$ 自然循环子图是一个强连通分量，如果该子图仅有一个节点，则一定存在该节点的自环。

定理 $3.1.3$ 自然循环子图仅有一个入口节点，这个节点要么有一条从连通分量以外的节点指向的边，要么包含程序的第一条语句[是流图的首节点]。

2. 代码优化技术#

代码优化实际上可以在任何时候进行，只要不改变程序原来的功能。

一般来说很难将一个大程序作为一个整体进行优化，这太难了。一般都是局部的。

代码优化技术常见的有：窥孔优化、局部优化、循环优化和全局优化。

2.1 窥孔优化#

窥孔优化是指在语句/指令序列上滑动一个小窗口[只看几条语句/指令]，用另一段更有效率的语句序列替代它。

窥孔优化不一定针对的是中间代码，似乎其他层次也可以进行，比如AST层，TAC层等。

窥孔优化主要有：

2.1.1 删除无用存/取#

lw $t2,5($t3)		/*取5($t3)的内容到($t2)中去*/
sw $t2,5($t3)		/*把($t2)中的内容[一个word]放到5($t3)中去*/

显然把( $t2)中的内容放到5(\$ t3)去是多余的。可以删掉

2.1.2 常量合并#

a = 2*3 => a = 6

常量表达式可以直接计算得出。

2.1.3 常量传播#

r1 = 1
r2 = 2 + r1       => r2 = 2 + 1 => r2 = 3

被赋予常量的变量被引用的时候，都可以直接用常量替代掉。[说不定也可以让有些变量不再被引用，可以直接去掉这个变量]

2.1.4 代数化简#

x = x + 0
y = y * 1

实际上有些代数表达式是没有用处的，或者说本身就是多余的，比如+0,*1,/1等等，可以直接去掉这样的表达式。

2.1.5 控制流优化#

	goto p1
	...
p1:
	goto p2
	...
p2:
	...

有时候会经历很多次跳转，但实际上可以一步到位

	goto p2
	...
p1:
	goto p2
	...
p2:
	...

2.1.6 删除死代码#

a = false
if(a)
	...

可以直接删去一些不会被访问的代码部分，比如因为逻辑不可访问的代码，实际上上面的就可以直接删去if部分:

a = false

2.1.7 强度削弱#

有的运算可以替换为代价更小的运算，一般来说，除法/不如*乘法，*乘法不如+加法，说不定移位也会更好。

a = a * 2 	=> a = a + a
a = a / 2.0	=> a = a * 0.5

另外，似乎还有被称为霍纳计算方案的计算方式：

多项式 $\sum\limits_{i=0}^{n} (a_i*x^i) = (\cdots(((a_n *x + a_{n-1}) * x) + a_{n-2})*x\cdots) + a_0$ 可以去掉乘幂。

2.1.8 使用机器惯用指令#

有的机器会有特殊的指令，比如自加1指令，那么x = x + 1就可以不用加法，而是使用自加1指令。

有的机器有多核，对于多媒体计算(图像、音频)就可以采用并行化处理。

2.2 局部优化#

局部优化指的是在一个基本块范围内进行优化。