控制流分析之循环

最近做科研碰到了如何识别程序热对象的问题，解决这个问题的一般思路是做静态分析，主要是分支概率和基本块频率的分析。目前，LLVM 里已经添加了这两种分析。然而，直接看相关的代码效率很低，主要原因是缺乏控制流分析方面的基础，导致代码中出现的许多术语无法理解。这些术语大多和 CFG 中的循环有关，因此这篇文章主要介绍这方面的基础知识，方便以后复习。

循环

众所周知，程序运行的大部分时间都花费在循环上了。因此，在做代码优化时，针对循环的优化收益可能相当高。一般来说，主要存在两种类型的循环优化方法：第一类，把循环不变式的计算移到循环外部；第二类，消除额外的归纳变量（induction variable），也就是与循环索引成线性关系的变量。当然，也有一些其他的常见循环优化，比如把某些乘法计算替换成等价的加法运算，从而减少计算代价。

下述例子展示了循环不变量代码外移的过程：

	FOR index := 1 TO 10000 DO	          t := y * z
	BEGIN				                  FOR index := 1 TO 10000 DO
		x := y * z ;		              BEGIN
		j := index * 3 ;          -->		  x := t
	END					                      j := index * 3
	.				                      END

在这个例子里，循环的每次迭代都会导致 y * z 的重新计算。如果检测后发现在循环中 y、z 和 x 的值都不改变，那么事先计算好 y 和 z 的乘积 t，并用 t 替换循环中的 y * z 计算，这样做会更有效率（x可以直接消除掉）。

要说明的是，上述示例也可以同时进行其他优化。例如，可以做乘法强度削减的优化，也可以做归纳变量消除的优化。

定义循环

由于不是所有循环都可以做优化，那么为了找出适合做优化的循环，需要先给出循环的定义。虽然控制流图里出现的环都可以称作循环（loop），但为了方便优化，还需要给循环加上第二条性质，即：循环必须有