控制流图

✍ dations ◷ 2025-07-04 13:25:23 #编译原理,建模语言

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

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

相关

  • 遗传遗传(英语:Heredity),俗称随根,是指经由基因的传递,使后代获得亲代的特征。遗传学是研究此一现象的学科,目前已知地球上现存的生命主要是以DNA作为遗传物质。除了遗传之外,决定生物
  • KGB国家安全委员会(俄语:Комите́т госуда́рственной безопа́сности, 听 帮助·信息,俄文罗马化:Komitet gosudarstvennoy bezopasnosti),通称
  • 世俗性世俗国家(英文:Secular state)是指一些对于宗教事务持中立的国家,与之相对的是宗教国家。没有对任何一种个别的宗教习俗持赞成或反对的态度,也是没有类似国教的宗教。一个世俗国
  • 吴军吴军(1970年1月25日-),又名吴亥,湖南桃江人,中国男演员。吴军早年为花鼓戏演员,1993年考入中国中央戏剧学院导演专业在职学习,1995年毕业后进入北京军区战友文工团工作。吴军曾出演
  • 71<< 70717273747576777879>> 71是70与72之间的自然数。
  • 1962年冬季世界大学生运动会第二届冬季世界大学生运动会于1962年3月6日至12日在瑞士维拉尔河畔欧伦举行。这是瑞士首次主办冬季世界大学生运动会。该届比赛共设6个大项。
  • 浙江人民美术出版社浙江人民美术出版社,简称浙人美,是中华人民共和国国有的一个美术作品出版社。浙人美初成立于1958年,原属于《浙江日报》社,文化大革命时期停办。1980年1月18日,浙人美在原浙江人
  • 腰窝腰窝(lateral lumbar fossa),又称为维纳斯的酒窝或维纳斯之眼,是人体下背处纵分面(英语:sagittal)上二块对称的凹陷处,在股沟的上方。腰窝就在对应骶髀关节(英语:sacroiliac joint)的表
  • 三田文学《三田文学》,日本唯美主义文学主要刊物,1910年5月由庆应大学文学部教授、唯美主义文学代表作家永井荷风创办并任主编。早期主要作家有永并荷风、森鸥外、上田敏等,后又有久保
  • 黄秉湘黄秉湘,四川省重庆府永川县人,清朝政治人物、进士出身。光绪二十年(1894年),参加光绪甲午科殿试,登进士二甲35名。同年五月,改翰林院庶吉士。光绪二十一年四月,散馆,著以知县即用。