编译器笔记53-代码优化-自然循环及其识别

自然循环(Natural Loops)

自然循环是一种适合于优化的循环

• 从程序分析的角度来看，循环在代码中以什么形式出现并不重要，重要的是它是否具有易于优化的性质。

• 自然循环是满足以下性质的循环

1. 有唯一的入口结点，称为首结点(header)。首结点支配循环中的所有结点，否则，它就不会成为循环的唯一入口。
2. 循环中至少有一条 返回首结点的路径，否则，控制就不可能从“循环”中直接回到循环头，也就无法构成循环。

• 非自然循环的例子

非自然循环的例子.png

自然循环的识别

自然循环的识别.png

算法：构造一条回边的自然循环

构造一条回边的自然循环.png

自然循环的一个重要性质：除非两个自然循环的首结点相同，否则，它们或者互不相交，或者一个完全包含(嵌入)在另外一个里面

例.png

如果两个循环具有相同的首结点，那么很难说哪个是最内循环。此时把两个循环合并

循环合并.png