编译原理与实践：找出循环的方法

只有找出循环，才能进行循环的优化工作。为了找到循环，需要先找到必经结点。每个控制流图里面有一个起始结点，记作S0，如图8-4所展示的流图中的结点1。起始结点到达某结点Sn的所有有向边路径都经过某结点Sd，结点Sd就是结点Sn的必经结点。如果Se也是结点Sn的必经结点，那么结点Sd就是结点Se的必经结点或者结点Se就是结点Sd的必经结点。

图8-4　某代码片段的流图

由此可知，每个结点Sn都有不超过一个的直接必经结点，记作Sid（n）。Sid（n）和Sn是不同的结点，Sid（n）是Sn的必经结点并且不是Sn的其他必经结点的必经结点。起始结点S0没有除自身以外的必经结点，其他结点都至少有一个除自身以外的必经结点，而且都恰好有一个直接必经结点。

流图中，从一个结点Sn到它的某必经结点Sd的边叫作回边。对应每条回边存在一个循环子图。图8-4的回边有：结点10至结点5、结点9至结点8、结点3至结点2、结点4至结点2。

一个流图中去除回边后，构成一个无环路流图，该流图称为可归约流图。常见的控制流，如条件语句和循环语句都只能够生成可规约流图。给定一个流图，可以画出一棵必经结点树，包含流图的每个结点Sn，并且含有从Sid（n）到Sn的边。如图8-4所展示的流图，可以画出其必经结点树如图8-5所示。(www.xing528.com)

图8-5　流图8-4的必经结点树

对于一个回边从一个结点Sn到它的某必经结点Sd，对应的自然循环包含这样的节点Sx：Sx的必经结点是Sd，并且有一条从Sx到Sn的路径不包含Sd。这个自然循环的头结点是Sd。图8-4对应的自然循环有：结点5、8、9、10组成的循环，结点8、9组成的循环，结点3、2组成的循环，结点4-2组成的循环

如果出现循环的嵌套，就有内层循环和外层循环，如图8-4中结点5、8、9、10组成的循环内部包含结点8、9组成的循环。内层循环占用了大量的执行时间，需要首先优化。