# 流图中的循环

## 概念、识别方法和应用

1. 标识循环并对循环专门处理的重要性
   - 程序执行的大部分时间消耗在循环上
   - 循环会影响程序分析的运行时间
   - 改进循环性能的优化会对程序执行产生显著影响

2. 循环展开
   - 通过将循环体内的代码复制多次，增加循环每一次迭代的步长
   - 减少循环分支指令执行的次数
   - 增大处理器指令调度的空间 (指令并行、流水线)
   - 增加寄存器的重用

3. 支配节点 (Dominators)
   - d 是 n 的支配节点，若从初始节点起，每条到达 n 的路径都要经过 d，写成 d dom n
   - 节点是它本身的支配节点
   - 循环的入口是循环中所有节点的支配节点
   - 直接支配节点是从入口节点到达 n 的所有路径上，节点 n 的最后一个支配节点

4. 支配节点计算的数据流分析
   - 正向数据流分析
   - 边界条件：OUT[Entry] = {Entry}
   - 初始化：OUT[B] = N
   - 约束方程：$OUT[B]=IN[B]\bigcup\{B\}$，$IN[B]=\bigcap_{P\in pred(B)}OUT[P]$

5. 深度优先排序与后序遍历相反

6. 深度优先生成树
   - 前进边
   - 后撤边
   - 交叉边

7. 回边：如果有 a dom b，则边 b->a 为回边
   - 流图可归约，则后撤边为回边
   - 可归约流图：如果把一个流图中所有回边删掉，剩下的图无环

8. 自然循环是一种适合优化的循环
   - 有唯一的入口节点，称首节点
   - 首节点支配循环中的所有节点
   - 至少存在一条回边进入该循环首节点

9. 回边 n->d 确定自然循环
   - d 加上不经过 d 能到达 n 的所有节点
   - 节点 d 是该循环的首节点

10. 流图中的循环
    - 内循环：若一个循环的节点集合是另一个循环的节点集合的子集
    - 两个循环有相同的首节点，但并非一个节点集是另一个的子集，看成一个循环