控制流图

✍ dations ◷ 2025-07-19 06:41:22 #编译原理,建模语言

控制流图(control-flow graph)简称CFG,是计算机科学中的表示法,利用数学中图的表示方式,标示计算机程序执行(英语:execution (computing))过程中所经过的所有路径。控制流图是由法兰·艾伦所建立,他提出Reese T. Prosser(英语:Reese Prosser)曾利用邻接矩阵用在流分析上。

CFG是许多编译器最佳化(英语:compiler optimization)及静态程序分析工具中的核心技术。

控制流图中的每个顶点都对应一个程式基本块,也就是一段没有分支指令,也没有分支目的的程式码,基本块的开始是分支目的,而基本块会以分支为结束。控制流程中会用有向边来表示分支。在大部分的进行下,会有二个特殊指定的程式块:进入程式块(entry block)是指进入此控制流图时,第一个遇到的程式码,另一个是结束程式块(exit block)是所有流程在结束时都会执行的程式码。

因为控制流图的生成方式,在控制流图中,每一个有向边A→B会有以下的性质:

以概念上来看,控制流图可以由程式的完整流程图产生。先画出一个控制流图,其中每一个顶点对应程式中的一个指令。接着对每一个边进行边收缩,将不符合上述条件的边(就是outdegree(A) = 1 且 indegree(B) = 1的边)和相邻的边整合。这个收缩算法在实务上没有什么重要性,但可以以视觉的方式说明控制流图的产生方式。而实务上产生控制流图的方式会更有效率的扫描程式中的基本块来达成。

考虑以下的程式片段:

0: (A) t0 = read_num1: (A) if t0 mod 2 == 02: (B)   print t0 + " is even."3: (B)   goto 54: (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。

可到达性(英语:Reachability)是图论中的性质,会用在程式的最佳化中。

若某一个子图没有和包括进入程式块的子图相连接,在执行程式时不会执行到该子图的程式,因此是不可到达程式码(英语:unreachable code),在一般情形下可以移除该程式,不会影响程式运作。

若从进入程式块无法连到结束程式块,则可能有死循环。不过不是所有的死循环都可以检测的到(参考停机问题)。

即使程式设计者没有刻意的写不可到达程式码或是死循环,仍有可能会出现这些情形。像是常数折叠或常数传播等最佳化方式,若后面有跳转线程(英语:jump threading),可能会将数个基本块变成一个,因此移除了控制流图上的一些边,也可能因此出现不可到达程式码

若从进入程式块到达基本块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可能是空的,但在经过循环不变代码运动(英语:loop-invariant code motion),Mpre就会慢慢增加。Mpre称为循环前首标(loop pre-header),而Mloop为新的循环首标。

可规约控制流图(reducible CFG)是指边可以分为前进边及倒退边二个不交集,因此:

结构化编程编程语言常会设计让产生的所有控制流图都是可规约控制流图,常见的流程控制指令 (例如IF、FOR、WHILE、BREAK、CONTINUE)都会产生可规约控制流图。若要让控制流图不可规约,需要加上Goto之类的指令。在一些编译器的最佳化过程中,可能会出现不可规约控制流图。

控制流图的循环连结度(loop connectedness)是以控制流图的给定深度优先搜索树(DFST)为准。DFST需以启始节点为根,包括控制流图中的所有节点。

若控制流图中的边,是从一个节点到DFST中的祖先节点,此边为倒退边。

循环连结度是指控制流图中没有循环的路径中,可以找到倒退边的最大数量。若是可规约控制流图,循环连结度和选择的DFST无关。

循环连结度可以用来说明数据流分析的时间复杂度。

相关

  • 流鼻血鼻衄,俗称流鼻血、淌大寒,称鼻出血,是指由于鼻孔内的毛细血管脆弱,血管受到破坏后,血液从鼻孔里流出,是一种医学上的疑难病症。大多数是从一个鼻孔里出,但偶尔也会两个鼻孔一起出。
  • 超弦理论超弦理论(英语:Superstring Theory),属于弦理论的一种,有五个不同的超弦理论,也指狭义的弦理论。是一种引进了超对称的弦论,其中指物质的基石为十维时空中的弦。为了将玻色子和费米
  • 贝叶斯网络贝叶斯网络(Bayesian network),又称信念网络(belief network)或是有向无环图模型(directed acyclic graphical model),是一种概率图型模型,借由有向无环图(directed acyclic graphs, o
  • 占领并洗劫拜占庭:30,000人十字军:10,000人威尼斯人:10,000人1204年君士坦丁堡之围(也称为第四次十字军)发生在1204年,西欧和威尼斯十字军在占领拜占庭帝国首都君士坦丁堡之后,摧毁了部分城市
  • 复活节攻势南越军:742,000人 美军: 美国空军美国宣称:~10,000人阵亡、33,000人受伤、3,500人失踪美国等国正式介入之后美国撤出至南越灭亡复活节攻势(英语:Easter Offensive),在越南称作1972
  • 阿斯特丽德·基尔赫阿斯特丽德·基尔赫(德语:Astrid Kirchherr,1938年5月20日-2020年5月12日. ),德国女性摄影家、艺术家。她拍摄了大量披头士在汉堡时期的照片。1960年,她在汉堡的Kaiserkeller酒吧结
  • 北京文化艺术活动中心北京文化艺术活动中心,位于北京市海淀区上园村3号北京交通大学知行大厦5层,是北京市人民政府设立的专门开展群众文化艺术工作的公益性文化事业单位,隶属北京市文化局。北京文化
  • 尼奥斯湖灾难尼奥斯湖灾难(英语:Lake Nyos disaster)是1986年8月21日喀麦隆西北部的尼奥斯湖发生的一场湖底喷发。此次爆发释放出约100,000到300,000吨的二氧化碳(CO2)到大气内,之后聚集而成的
  • 我听说你漆房子《我听说你漆房子》(英语:),又译《听说你刷房子了》,是一本由前凶杀案检察官、调查员、辩护律师查尔斯·布朗特所写的2004年回忆录。该书记录了法兰克·“爱尔兰人”·希兰的生平
  • 伊藤遥香伊藤遥香(日语:伊藤 はるか,3月1日-),日本女性配音员。出身于北海道。身高159cm。O型血。专门学校札幌漫画动画学院、AIR AGENCY声优养成所毕业。※粗体字表示说明饰演的主要角色