控制流图

✍ dations ◷ 2025-09-10 03:19:32 #编译原理,建模语言

控制流图(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无关。

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

相关

  • 蛋白质水解剂蛋白酶解或蛋白水解(英语:Proteolysis)是指蛋白质降解为较小的多肽或氨基酸的过程。通常情况下,被水解的都是肽键,且在蛋白酶的作用下进行,因此常用蛋白酶解。但也可能发生分子内
  • 联邦通信委员会联邦通信委员会(英语:Federal Communications Commission,FCC)是一个独立的美国联邦政府机构,由美国国会法令所授权创立,并由国会领导。联邦通信委员会是由1934年通信法案所创立,取
  • 手表手表,或称为腕表,是指戴在手腕上、用以计时及显示时间的仪器。几乎是利用皮革、橡胶、尼龙布、不锈钢等材料,制成表带,将显示时间的“表头”束在手腕上。本来作为仪器的“錶”应
  • 爱德华·冯·柏姆-厄尔默利男爵爱德华·冯·柏姆-厄尔默利男爵(Eduard Freiherr von Böhm-Ermolli) (1856年2月12日 - 1941年12月9日) 第一次世界大战时意大利出生的奥地利军官,奥匈帝国中的一名陆军元帅
  • 西莱斯特·霍姆西莱斯特·霍姆(英语:Celeste Holm,1917年4月29日-2012年7月15日)出生于美国纽约州纽约市,为美国著名的舞台剧演员、电影演员和电视剧演员,她以《圣女歌声》和《彗星美人》、《君子
  • 草酸铵草酸铵是草酸的铵盐,分子式为(NH4)2C2O4。无色晶体,带有一分子结晶水,分子式亦可作为(NH4)2C2O4.H2O。遇热会分解成草酸并放出氨气,反应式如下:(NH4)2C2O4 + 热 → H2C2O4 + 2NH3
  • 柯琳·哈契柯琳·哈契(英语:Corinne Hatch,1985年-),本名碧妮·哈契(英语:Brittany Hatch);美国模特儿,来自美国乔治亚州的沙瓦纳市,是《全美超级模特儿新秀大赛》第八季五强。柯琳是一位酒保,居住
  • 宋士芳宋士芳(1942年-),京剧琴师,在中国黑龙江省哈尔滨市出生,著有《宋士芳京胡演奏艺术与琴谱集》等书。他师承汪本贞(裘盛戎的琴师)和何顺信(张君秋的琴师)学京剧音乐艺术,琴艺全面,并擅长创
  • 狄龙·弗朗西斯狄龙·哈特·弗朗西斯(英语:Dillon Hart Francis,1987年10月5日-),出生于加利福尼亚州洛杉矶,美国知名电子音乐人、唱片制作人兼DJ。
  • 中田翔中田翔(日语:中田 翔/なかた しょう ,1989年4月22日-)是日本广岛县广岛市中区,出身的职业棒球选手,司职一垒手,目前效力于北海道日本火腿斗士。中田自小学二年级时开始以捕手的身份