Loop Optimization
:material-circle-edit-outline: 约 362 个字 :material-clock-time-two-outline: 预计阅读时间 1 分钟
Dominators
必经节点，从入口节点到某节点所有路径都需要经过的节点，某节点自己就是自己的必经节点
找必经节点的方法，就是从前往后依次找，前继节点的必经节点之交加自己：
定理：必经节点是有序的，一个节点如果有两个必经节点，那这两个必经节点肯定是有一个是另一个的必经节点
idom(n) 即离 n 最近的非 n 必经节点，除 s0 外的节点都有且只有一个
Dominator Tree
画出所有控制流图的节点，以及所有从 idom(n) 到 n 的有向边即可
Natural Loops
back edge 指某节点到自己必经节点的 edge
对于一个 back edge，设其为 n-> h，则其 Natural Loops 为包含这个 back edge 以及 h-> n 的这么个循环，这个循环的所有点满足：
- h 是大家的必经节点
- 大家都有不经过 h 就能到 n 的路径
Loop-Nest Tree
Nest loop 即嵌套循环
循环嵌套图需要先画出 Dominator Tree，然后找出所有 Natural Loops 作为节点（记为多个控制流节点的集合）
如果有节点是多个 Natural Loops 的头节点，就将这些 Natural Loops 合并为一个循环，上下的非循环多的节点留在根节点
注意每个节点分两行，第一行是头节点
