控制流图

✍ dations ◷ 2025-09-16 11:30:50 #编译原理,建模语言

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

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

相关

  • 马尔科姆四世1153年5月27日马尔科姆四世 (中世纪盖尔语:Máel Coluim mac Eanric;现代盖尔语:Maol Chaluim mac Eanraig;1141年4月23日和5月24日之间 – 1165年12月9日)是苏格兰国王(1153年
  • 理思必妥利培酮(英语:Risperidone),常见商品名Risperdal,为一种精神科药物。主要用于治疗精神分裂症、躁郁症,以及自闭症症状者的易怒情形。本品可口服或肌肉注射给药。注射剂型的药效可维
  • 刘之冰刘之冰(1963年3月30日-),黑龙江萝北,中国大陆男演员,刘之冰生于黑龙江省鹤岗市萝北县凤翔镇,1979年毕业于黑龙江省艺校,1982年2月调入长春电影制片厂演员剧团任演员,2008年3月通过特
  • 美国白宫白宫(英语:White House,也称白屋)是美国总统官邸与主要办公的地方,位于美国华盛顿哥伦比亚特区西北区,宾夕法尼亚大道1600号。自1800年美国第二任总统约翰·亚当斯入住以来,白宫就
  • 俄亥俄县 (西弗吉尼亚州)俄亥俄县(Ohio County, West Virginia)是美国西弗吉尼亚州的一个县,惠灵为其县治所在。根据美国人口调查局2000年统计,共有人口47,427人,其中白人占94.50%、非裔美国人占3.57%。
  • VR战士5街机*JPN 2006年7月12日PlayStation 3*JPN 2007年2月8日Xbox 360*NA 2007年8月《VR战士5》(Virtua Fighter 5)是SEGA《VR战士》系列游戏的最新作品。2006年7月12日VR战士5在日
  • 史蒂夫·汉克史蒂夫·汉克(英语:Steve H. Hanke,1942年12月29日-),是美国约翰·霍普金斯大学的应用经济学家,并且于华盛顿特区的卡托研究所,为Troubled Currencies Project担任高级研究员及主任
  • 米莱娜·杜奇科娃米莱娜·杜奇科娃(捷克语:Milena Duchková,1952年4月25日-),捷克女子跳水运动员;曾代表捷克斯洛伐克参加1968年奥运会,并赢得金牌。1968年,米莱娜·杜奇科娃代表捷克斯洛伐克参加墨
  • 山口真帆山口真帆(日语:山口 真帆/やまぐち まほ  */?,1995年9月17日-)是日本女艺人,曾为女子偶像组合NGT48成员。昵称“Mahohon”(まほほん)。青森县出身。所属经纪公司为研音。2015年2016
  • 工藤公康教练时期监督时期工藤公康(日语:工藤 公康/くどう きみやす ,1963年5月5日-)是日本爱知县丰明市选出身的职业棒球选手,司职一军监督,效力于日本职棒福冈软银鹰。曾经效力过埼玉西武