控制流图
此条目需要补充更多来源。 (2020年9月) |
此条目具有many bad/unclear definitions and dubious claims.的问题，需要精通或熟悉计算机科学的编者参与及协助编辑。 (2020年9月) |
控制流图（control-flow graph）简称CFG，是计算机科学中的表示法，利用数学中图的表示方式，标示计算机程序执行过程中所经过的所有路径。控制流图是由法兰·艾伦所建立[1]，他提出Reese T. Prosser曾利用邻接矩阵用在流分析上[2]。
(a)if-then-else
(b)while回圈
(c)有二个离开点的自然回圈，例如：在中间有break指令的while回圈，非结构化，但是reducible
(d)irreducible的CFG：有二个进入点的回圈，例如用goto进入for回圈或while回圈内
定义
编辑控制流图中的每个顶点都对应一个程式基本块，也就是一段没有分支指令，也没有分支目的的程式码，基本块的开始是分支目的，而基本块会以分支为结束。控制流程中会用有向边来表示分支。在大部份的进行下，会有二个特殊指定的程式块：进入程式块（entry block）是指进入此控制流图时，第一个遇到的程式码，另一个是结束程式块（exit block）是所有流程在结束时都会执行的程式码[3]。
因为控制流图的生成方式，在控制流图中，每一个有向边A→B会有以下的性质：
- outdegree(A) > 1 或 indegree(B) > 1（也可能同时成立）[4]。
以概念上来看，控制流图可以由程式的完整流程图产生。先画出一个控制流图，其中每一个顶点对应程式中的一个指令。接著对每一个边进行边收缩，将不符合上述条件的边（就是outdegree(A) = 1 且 indegree(B) = 1的边）和相邻的边整合。这个收缩演算法在实务上没有什么重要性，但可以以视觉的方式说明控制流图的产生方式。而实务上产生控制流图的方式会更有效率的扫描程式中的基本块来达成[4]。
举例
编辑考虑以下的程式片段：
0: (A) t0 = read_num 1: (A) if t0 mod 2 == 0 2: (B) print t0 + " is even." 3: (B) goto 5 4: (C) print t0 + " is odd." 5: (D) end program
以上程式中，有四个基本块，第0行至第1行的A，第2行到第3行的B，第4行的C以及第5行的D。在此例中，A是进入程式块，D是结束程式块，第4行及第5行是分支目的。这段程式的控制流图有从A到B、从A到C、从B到D、从C到D。
可到达性
编辑可到达性是图论中的性质，会用在程式的最佳化中。
若某一个子图没有和包括进入程式块的子图相连接，在执行程式时不会执行到该子图的程式，因此是不可到达程式码，在一般情形下可以移除该程式，不会影响程式运作。
若从进入程式块无法连到结束程式块，则可能有无穷回圈。不过不是所有的无穷回圈都可以检测的到（参考停机问题）。
即使程式设计者没有刻意的写不可到达程式码或是无穷回圈，仍有可能会出现这些情形。像是常数折叠或常数传播等最佳化方式，若后面有跳转线程，可能会将数个基本块变成一个，因此移除了控制流图上的一些边，也可能因此出现不可到达程式码
支配关系
编辑若从进入程式块到达基本块N的所有路径，都会在到达基本块N之前先到达基本块M，则基本块M支配（dominates）基本块N。进入程式块支配自身之外，所有的基本块。
考虑相反的方向，若基本块N到达结束程式块的所有路径，都会在结束程式块之前先到达基本块M，则基本块M后置支配（postdominates）基本块N。结束程式块后置支配自身之外，所有的基本块。
若基本块M支配基本块N，且其中间没有任何基本块P，使得基本块M支配基本块P，且基本块P支配基本块N，则基本块M直接支配（immediately dominates）基本块N，也就是说，基本块M是基本块N的直接支配者中，最靠近基本块N的一个。每一个基本块都有唯一的直接支配者。
同样的，也有直接后置支配者（immediate postdominator）的概念。
支配树（dominator tree）是描述支配关系的辅助资料结构。若M直接支配N，基本块M到基本块N就会有弧线。因为每一个基本块都只有一个直接支配者，因此所形成的会是树。可以用Lengauer-Tarjan算法快速的计算支配树。
同样的，也可以绘制后置支配树（postdominator tree）。
特殊边
编辑倒退边（back edge）是指向的基本块是在图的深度优先搜索中，已经走过的基本块。倒退边多半表示有回圈。
异常边（abnormal edge）是目的不清的边。建构异常处理时常会产生这种边。此情形会不允许最佳化。
不可能边（impossible edge）也称为假边（fake edge），是为了让结束程式块后置支配所有节点而加入的边，其实不会执行到。
回圈管理
编辑回圈首标（loop header）也称为回圈的进入点。是指一个支配基本块，同时也是倒退边的目标。循环首标是回圈中其他基本块的支配者。基本块也可能是多个回圈的回圈首标。若回圈有多个进入点，就没有回圈首标。
假设基本块M是有数个进入点的支配基本块，其中有些是倒退边（因此M是回圈首标）,有一个有利于许多最佳化程序的作法，是将基本块M分为基本块Mpre和基本块Mloop。基本块M的内容以及倒退边移到Mloop，其馀的移到Mpre，建立一个从Mpre到Mloop的边（因此Mpre是Mloop的直接支配者。一开始时，Mpre可能是空的，但在经过循环不变代码运动，Mpre就会慢慢增加。Mpre称为回圈前首标（loop pre-header），而Mloop为新的回圈首标。
可规约性
编辑可规约控制流图（reducible CFG）是指边可以分为前进边及倒退边二个不交集，因此[5]：
结构化编程程式语言常会设计让产生的所有控制流图都是可规约控制流图，常见的流程控制指令 (例如IF、FOR、WHILE、BREAK、CONTINUE）都会产生可规约控制流图。若要让控制流图不可规约，需要加上Goto之类的指令。在一些编译器的最佳化过程中，可能会出现不可规约控制流图。
回圈连结度
编辑控制流图的回圈连结度（loop connectedness）是以控制流图的给定深度优先搜索树（DFST）为准。DFST需以启始节点为根，包括控制流图中的所有节点。
若控制流图中的边，是从一个节点到DFST中的祖先节点，此边为倒退边。
回圈连结度是指控制流图中没有回圈的路径中，可以找到倒退边的最大数量。若是可规约控制流图，回圈连结度和选择的DFST无关[6][7]。
相关条目
编辑参考资料
编辑- ^ Frances E. Allen. Control flow analysis. SIGPLAN Notices. July 1970, 5 (7): 1–19. doi:10.1145/390013.808479.
- ^ Reese T. Prosser. Applications of Boolean matrices to the analysis of flow diagrams. 1959: 133–138.
|booktitle=被忽略 (帮助) - ^ Yousefi, Javad. Masking wrong-successor Control Flow Errors employing data redundancy. IEEE: 201–205. 2015. doi:10.1109/ICCKE.2015.7365827.
- ^ 4.0 4.1 Peri L. Tarr; Alexander L. Wolf. Engineering of Software: The Continuing Contributions of Leon J. Osterweil. Springer Science & Business Media. 2011: 58. ISBN 978-3-642-19823-6.
- ^ 存档副本 (PDF). [2020-09-15]. （原始内容存档 (PDF)于2020-08-01）.
- ^ 6.0 6.1 Kam, John B.; Ullman, Jeffrey D. Global Data Flow Analysis and Iterative Algorithms. Journal of the ACM. 1976-01-01, 23 (1): 158–171. ISSN 0004-5411. doi:10.1145/321921.321938.
- ^ Offner, Carl. Notes on Graph Algorithms Used in Optimizing Compilers (PDF). [13 April 2018]. （原始内容存档 (PDF)于2021-02-02）.
外部链接
编辑
- The Machine-SUIF Control Flow Graph Library （页面存档备份，存于互联网档案馆）
- GNU Compiler Collection Internals （页面存档备份，存于互联网档案馆）
- Paper "Infrastructure for Profile Driven Optimizations in GCC Compiler （页面存档备份，存于互联网档案馆）" by Zdeněk Dvořák et al.
- 例子