控制流图

✍ dations ◷ 2025-07-11 16:25:56 #编译原理,建模语言

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

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

相关

  • 印刷通用汉字字形表《印刷通用汉字字形表》,中国大陆于1965年出版字表,共收6196字,统一规定当时印刷宋体字形标准,以简化字为主(《简化字总表》1964年发布),附以对应之繁体字。所谓的“新字形”即由此
  • Beilstein拜耳斯坦数据库(Beilstein database,亦被译为“拜尔斯坦”)是重要的化学数据库之一,以有机化学资料见长。它分为拜耳斯坦文摘数据库和拜耳斯坦有机化学结构及数据两部分,涵盖自17
  • 谢普塞斯卡弗谢普塞斯卡弗(英语Shepseskaf)古埃及古王国时期第四王朝的国王(约公元前2503年—约公元前2498年在位)。作为儿子继承了父王的王位。他的名字意思是“灵魂高贵。”他打破传统,在萨
  • 番荔枝科番荔枝科(学名:Annonaceae)在生物分类学上是被子植物木兰目下的一科。约有129属,2120种,是木兰目中最大的科。有的果实可食,有的可材用,有些为观赏植物。大多分布在热带地区,少数分
  • 内阁总理大臣内阁总理大臣是清朝末期内阁的首长,设置于1911年5月,清廷将军机处与大学士内阁废除,不再以军机大臣执掌政事,效法明治维新的日本改设内阁总理大臣(首相),与诸大臣组织责任内阁。唯
  • 商业大厦高层建筑物,或称高层建筑,是建筑物依高度划分的分类之一,指具有较多层数、高度较高的建筑,具体划分标准不同国家、地区各不相同。超高层建筑又被称为摩天大楼。联合国经济事务部
  • 新西兰先驱报新西兰先驱报(英语:)是在新西兰奥克兰发行的日报,由New Zealand Media and Entertainment所有,是新西兰发行量最大的报纸,2006年达到20万份以上,到2014年12月平均下降到144,157份。
  • 历史哲学历史哲学是一个与历史学有关的哲学分支,旨在探讨历史的模式与意义、历史学的性质与方法、历史写作的结构与规律等问题。根据具体研究对象的不同,历史哲学大致可以分为三类:思辨
  • 爱尔莎·爱因斯坦爱尔莎·爱因斯坦(英语:Elsa Einstein,1876年1月18日-1936年12月20日),是著名物理学家阿尔伯特·爱因斯坦的第二任妻子。 爱尔莎的母亲和阿尔伯特·爱因斯坦的母亲是亲姐妹、爱尔
  • 黎贵惇四配 颜回 · 孟子 · 曾参 · 孔伋日本 藤原惺窝 · 林罗山 · 室鸠巢 新井白石 · 雨森芳洲朝鲜 薛聪 · 权近 · 吉再 · 安珦 · 李穑 李滉 · 王仁 · 李