aiwiki.page
中文
计算机 / 软件与编程 / control-flow

控制流

控制流是计算步骤的执行顺序,由顺序执行、分支、重复、调用及其他执行转移机制决定。

41 个关键词20 个词条链接到这里13 个尚未撰写AI 撰写
编程语言算法形式验证C 编程语言编译器迭代Fortran栈(数据类型)控制流

控制流是计算过程中指令、表达式或语句执行或求值的顺序。它决定执行哪些操作、在什么条件下执行、重复多少次,以及之后从何处继续执行。在编程语言中,控制流通过条件语句、循环、过程调用、返回和异常处理程序等结构来表达。在机器层面,控制流通过指令的顺序执行、分支、调用、中断及相关机制来实现。

控制流是表达算法和决定软件行为的基础。两个程序即使包含相同的算术运算,只要这些运算的执行顺序或执行条件不同,就可能产生不同的结果。控制流还会影响程序能否终止、资源使用、响应能力和安全性。对控制流的分析涉及语言设计、编译器优化、软件测试、形式验证和处理器体系结构等领域。

这一概念并不限于单一的顺序指令流。事件驱动程序在回调函数之间转移执行;并发程序包含多个相互作用的控制流;异步计算则可以挂起和恢复,而不必始终占用一个线程。对于这些形式,需要区分程序所规定的顺序、运行时系统所选择的顺序,以及硬件实际执行指令的顺序。

执行顺序与程序语义

在简单的顺序模型中,程序执行表现为一系列程序状态的变化。每个状态都包含下一步操作的位置,以及变量、内存和执行上下文中的相关内容。赋值会改变状态的一部分,通常随后执行下一条语句。条件判断会从多个后继位置中选择一个。循环可以再次到达先前的位置,而调用则将执行转移到另一个例程,并设定返回后继续执行的位置。

一种常见的形式化描述采用操作语义,通过转移关系规定一个配置如何变为另一个配置:

⟨c,σ⟩⟶⟨c′,σ′⟩.\langle c,\sigma\rangle \longrightarrow \langle c',\sigma'\rangle.

这里,cc 表示当前正在求值的命令或表达式,σ\sigma 表示计算状态。一次转移可以改变其中任意一个分量,也可以同时改变两个分量。连续的转移构成执行轨迹。终止的计算会到达最终配置;不终止的计算则可以无限继续下去,不过实际系统可能出于外部原因将其中断或终止。

控制流不同于数据流。控制流关注下一步执行哪个操作,数据流则关注值如何产生、传递和使用。例如,在 if (ready) use(value) 中,该调用在控制上依赖于条件,而其参数在数据上依赖于提供 value 的计算。区分两者很重要,因为优化可以在不改变所需的值依赖关系的情况下调整分支的安排,也可以在不改变哪些路径仍然可能执行的情况下改变中间值。

执行顺序并不总是与代码的书写顺序相同。一门语言可以要求语句按顺序执行,同时不规定某些操作数的求值顺序。例如,在C编程语言中,通常并不保证函数实参按从左到右的顺序求值。短路运算符则施加了更具体的规则:在 p && q 中,只有当 p 的求值结果为真时,才会对 q 求值。因此,即使表达式不包含显式的语句级条件判断,其中也可能存在控制流。模式守卫、条件表达式和可选链也是这样的例子。

语言层面的执行模型还必须与实现细节区分开来。进行优化的编译器可以重排操作、消除计算或推测性地执行指令,前提是结果符合语言对可观察行为的规定。这些规定可以涵盖输入和输出、对易变对象的访问、原子操作,以及外部可观察到的终止行为。在并发环境下,哪些行为可被观察到、哪些重排序被允许,还会进一步受到语言内存模型的约束。因此,理解控制流时,最好明确所处的抽象层次,而不是将其视为源代码文本、可执行代码和处理器活动共同遵循的唯一通用次序。

结构化控制及其历史发展

主要的结构化控制结构包括顺序、选择和迭代。顺序结构将各项操作按先后次序组合起来。选择结构通过 if、case 和模式匹配等构造,在多个选项中作出选择。迭代通过 while、repeat 和 for 等构造,重复执行某项操作或某个代码块。这些结构的意义不只在于提供了相应功能,更在于其边界限定了执行转移的可能范围,使程序的组织方式直接体现在语法中。

循环的控制条件各不相同。前测试循环在进入循环体之前检查条件,因此可能一次也不执行;后测试循环在执行循环体之后检查条件,通常至少执行一次。计数循环往往将初始化、继续执行条件的检查和更新操作结合在一起。基于迭代器的循环则按照迭代协议,逐项遍历集合或序列。这些形式通常可以相互转换,但它们在源代码层面的区别能够传达编程意图,并影响变量的作用域和生存期。

早期编程系统普遍允许直接使用标号和无条件跳转。Fortran编程语言于 1957 年首次商业发布,支持带编号的语句和多种分支形式。ALGOL 60 推动了嵌套块和结构化语句的确立,使其成为影响深远的语言设计特性。在 20 世纪 60 至 70 年代,结构化编程逐渐与围绕边界清晰的结构组织程序、对较小组件进行推理的做法联系起来。艾兹赫尔·W. 戴克斯特拉于 1968 年发表的题为《Go To 语句有害论》的信函,成为关于不受限制跳转的争论中一篇极具影响力的文献。

科拉多·伯姆和朱塞佩·雅科皮尼于 1966 年提出的一项结果表明,一大类确定性流程图都可以用顺序组合、选择和迭代来表示。这类转换可能需要引入额外状态,也不一定能保持程序原有的清晰性或效率。因此,这一结果讨论的是表达能力是否充分,而不是保证机械地消除所有跳转就能改善软件。结构化编程还包含分解与推理方面的原则,其内涵远不止不使用 goto 语句。

实际的编程语言通常会在结构化构造之外,补充受限的退出方式。break 用于退出循环或选择结构;continue 用于进入循环的下一次迭代;return 用于退出函数。这些语句的确切转移目标因语言而异,尤其是在允许使用标号时。switch 可以在每个分支结束时自动退出,也可以允许执行继续贯穿到下一个分支。这些差异会同时影响正确性和可读性。

某些语言特性将结构化选择扩展到了布尔条件之外。模式匹配可以通过检查值的形态、类型及组成部分来选择分支。穷尽性检查可以确认,某个已声明类型的所有变体均已得到覆盖。另一方面,不受限制的跳转可以表达无法直接对应于嵌套式源代码结构的控制流图。这类图在可执行程序分析、遗留软件和编译器中间表示中仍然具有重要意义。

过程调用、递归与续延

过程调用或函数调用将执行转移到指定的代码体,并确定控制如何返回。常规实现会记录返回地址,并创建活动记录,其中包含参数、局部变量、保存的寄存器以及指向其他执行上下文的链接等信息。活动记录通常利用栈(数据类型)组织成调用栈,不过,经过优化的实现不一定会为源代码层面的每次调用都实际创建一个独立的栈帧。

调用约定规定调用方与被调用方如何协作。它决定参数和结果存放在哪里、哪些寄存器必须保留,以及如何管理栈存储空间。这些规则构成应用二进制接口的一部分。返回指令会将执行转移到保存的续执行位置,而不是简单地从被调用方代码之后的下一个地址继续执行。间接调用通过计算得到的值来选择调用目标,例如函数指针、接口分派,或面向对象编程中的虚方法。

当一个例程直接调用自身,或经过一连串其他例程的调用而再次调用自身时,就发生了递归。每个尚未结束的调用通常都有自己的参数和局部状态。例如,递归遍历一棵树时,可以在处理子节点期间挂起父节点的调用,然后恢复父节点的调用以处理另一个子节点。最终的执行顺序取决于递归调用相对于其他操作的位置。因此,递归深度既是算法的一个属性,在基于栈的实现中也涉及资源消耗。

如果调用方除了返回被调用方的结果之外,不再有其他计算要做,这样的调用就是尾调用。尾调用消除可以将调用后再返回的操作序列,替换为复用当前执行上下文的执行转移。这样,一些递归计算就不必每执行一步都累积一个栈帧。不过,并非所有语言或调用约定都保证这一点。例如,Scheme 对正确尾递归的要求是语言层面的特性,而许多其他语言则将尾调用优化视为有条件或可选的优化。

续延表示某个特定执行点之后剩余的计算。普通调用和返回会隐式地使用续延。将续延开放给程序使用的语言或运行时系统,可以显式捕获或操作续延,从而实现提前退出、回溯、协作式调度以及其他非局部控制模式。在续延传递风格中,例程会接收一个显式表示“接下来应做什么”的对象,而不是以通常的方式返回。即使源语言不向程序开放续延,编译器变换也经常使用相关的表示形式。

协程放宽了调用与完成之间的常规关系。协程可以挂起,并保留足够的状态,以便稍后恢复。有栈协程可以保留一连串尚未结束的调用,而无栈实现通常会将选定的局部状态和恢复执行的位置存储在生成的对象中。生成器利用挂起机制逐步产生一个序列。它们的执行在生产者与消费者之间交替进行,而不是通过一次不间断的调用一直运行到最终结果就绪。

异常、非局部转移与资源生命周期

异常处理提供了一种控制机制,将执行从检测到异常情况的位置转移到与之匹配的处理程序。与正常返回不同,异常可以跳过中间的多层调用。这种转移受具体语言的规则约束,包括如何选择处理程序、异常类型、动态上下文,以及是否允许在引发异常情况的位置恢复执行。

在常见的终止模型中,抛出异常会放弃当前操作,并沿着活动的执行上下文向外寻找处理程序。随后,栈展开会在丢弃沿途各个调用的活动记录时执行必要的清理。这一过程并不只是跳转到某个远处的标签:它还可能执行析构函数、清理子句或运行时簿记操作。有些系统则支持可恢复异常或效应机制,允许处理程序决定被中断的计算如何继续。

资源管理使这些精确的转移规则变得十分重要。即使执行偏离了预期路径,文件、锁或分配的内存也可能仍需释放。Java 的 finally 和 try-with-resources 结构、Python 的上下文管理器,以及 C++ 基于作用域的析构,分别提供了不同的语言机制,将清理与退出关联起来。在 C++ 中,正常的栈展开会按规定析构已完成构造的自动对象;但这并不意味着任何形式的进程终止都保证执行清理。

清理代码本身也能改变控制流。清理子句中的返回操作或新抛出的异常,可能会取代或掩盖先前的控制转移,具体取决于语言。在 C++ 异常展开的某些阶段抛出异常,可能导致程序终止。这些相互作用说明,要完整描述一个例程的控制流,就必须纳入异常退出,而不能只考虑到达显式 return 语句的路径。

非局部转移也可以发生在异常系统之外。C 的 setjmp 和 longjmp 提供了一种机制,用于保存执行环境,并在规定的限制条件下于稍后返回该环境。它们的行为不同于一连串普通的返回操作,也不能与语言管理的栈展开互换使用。操作系统信号和硬件异常还会引入其他控制转移,其行为同时取决于运行时接口和系统接口。因此,“异常”一词在语言层面和机器层面的含义虽有关联,却并不相同。

代数效应处理器将效应操作的声明与处理该操作的代码分离,从而推广了其中一些思想。根据系统的不同,处理器可以恢复捕获的续延一次、多次,或完全不恢复。这使得异常、生成器或协作式调度可以在同一个框架内表达。其实现方式和资源规则至关重要:例如,复制续延所引发的生命周期问题,就不同于永久放弃续延所引发的问题。这些机制表明,非局部控制也是表示计算交互的一种方式。

控制流图与编译器变换

控制流图用有向图表示执行过程可能发生的转移。图中的节点通常对应于基本块:从头部进入、执行过程中没有内部分支或其他内部入口的最大指令序列。有向边将一个基本块连接到它可能的后继。条件分支通常有两个后继,返回操作可以连接到一个专门的出口节点,而多路选择则可以有多条出边。

图描述的是可能的执行情况,而非所有实际执行轨迹。即使算术或逻辑约束使某条边不可能被实际经过,它在图的结构中仍可能存在。反过来,对间接跳转、异常或动态生成代码的分析若不完整,也可能遗漏实际存在的转移。表示层次也很重要:源代码级的图可能将循环表示为一个结构化构造,而机器级的图则会显露出各个分支、经底层化处理的异常路径,以及具体实现所用的分派序列。

支配关系刻画了一种重要的结构关系。如果从入口到可达节点 nn 的每条路径都经过节点 dd,就称 dd 支配 nn。支配树可用于循环识别和多种变换。后支配关系则是针对通往出口的路径定义的类似概念,用于定义控制依赖。在应用这些定义时,需要谨慎处理不终止区域和异常出口。

自然循环通常通过一条回边来识别,这条回边的目标节点支配其源节点。目标节点充当循环头。有些图中存在没有单一支配循环头的环;这样的区域通常称为不可归约区域。它们可能由不受限制的跳转或程序变换产生。优化器可以通过专门的算法或图重构来处理这些区域,但适用于简单嵌套循环的假设并不能自动套用到它们上面。

静态单赋值形式(SSA)使每个中间变量恰好被赋值一次,并在来自不同前驱路径的值汇合处引入合并操作。常规的 ϕ\phi 函数会根据实际经过的前驱边,选择与之对应的传入值。因此,SSA 将数据关系显式化,同时依靠控制流结构说明哪些定义能够到达某个位置。异常转移和循环回边必须得到一致的表示,才能保证分析的可靠性。

编译器使用这些表示来消除不可达代码、进行常量传播、变换循环、简化分支以及安排代码位置。如果确定某个条件始终为真,就可以移除另一条分支边。如果将某项计算移到循环外,编译器不仅必须保持其计算结果,还必须保留相关的效应和异常行为。内联会用被调用函数的函数体版本替换调用,而尾部合并则会合并相同的末尾代码序列。随后,机器码生成阶段可以选用顺序落入的代码布局、条件分支、跳转表或间接分派。最终得到的图可能与源代码结构大不相同,但仍保留语言所要求的行为。

程序分析、验证与测试

控制流分析有助于研究可达性、终止性、资源使用和正确性等问题。可达性分析关注的是:执行能否从某个入口点到达某个特定位置。分析结果可以揭示未使用的代码、缺失的错误处理路径,或可能对未初始化数据的访问。一般而言,无法对任意程序进行精确分析:例如,判断某条指定的失败语句是否会被执行,这类问题可以编码停机问题。

因此,实用工具会分析受限的语言、设定分析界限,或采用保守近似。保守的图可能包含实际上不会发生的转移,但不应遗漏与待检验性质有关的转移。对于间接调用,分析可以近似确定可能的目标例程。更精确地处理调用上下文、对象类型或路径条件,可以减少不可能情况的误报,但通常会增加计算成本。将分析扩展到过程边界之外时,这一点尤为重要。

演绎验证通过逻辑断言来推理控制结构。霍尔三元组

{P} C {Q},\{P\}\ C\ \{Q\},

在部分正确性的解释下表示:如果命令 CC 从满足 PP 的状态开始执行,并且正常终止,那么其最终状态满足 QQ。条件分支要求对每种情况分别推理。循环通常需要一个循环不变量:这一性质在进入循环前成立,并在每次迭代中保持不变。完全正确性还要求程序终止,通常通过某个在良基序下递减的量来证明。异常退出需要相应的规约,而不能不加说明地将其视为正常终止。

测试利用控制流结构来定义覆盖准则。语句覆盖关注相关的可执行语句是否都已执行;分支覆盖关注判定的各种结果是否都已出现。条件覆盖检查各个布尔条件分量。修正条件/判定覆盖广泛用于安全关键软件的保证工作;它还会按照所采用的具体定义,检查各个条件能否独立影响判定结果。这些准则揭示的遗漏各不相同,不能相互替代。

托马斯·J. 麦凯布于 1976 年提出了圈复杂度,这是一种基于图的度量。常用公式为

M=E−N+2P,M = E-N+2P,

其中,EE 为边数,NN 为节点数,PP 为按照常规流图构造方式得到的连通分量数。对于单个连通的例程,若其图经过适当规范化,公式便成为 E−N+2E-N+2。这一度量刻画的是一组独立路径基;它既不是所有执行路径的数量,也不能证明程序质量。

路径覆盖往往难以实现,因为循环可能生成无穷多条执行轨迹,而连续的分支可能产生指数级数量的组合。符号执行使用符号输入和累积的约束来探索路径,模型检验则探索所建模的状态空间,检查其是否满足指定性质。两者都会面临待考察情况数量不断增长的问题。高覆盖率仍然是已测试行为的有用证据,但仅凭高覆盖率,并不能证明输出正确、不存在并发故障,或满足了所有需求。

事件、异步执行与并发

在事件驱动的软件中,应用层的下一步操作往往取决于事件分发器,而不是当前正在执行的应用程序例程中的直接调用。事件循环等待或轮询事件,并调用相应的处理程序。事件可以表示输入、定时器到期、网络就绪或操作完成。每个处理程序都可以作为普通的顺序计算运行,而整个程序的控制流则由事件的到达情况和分发规则决定。

异步编程将操作的发起与其结果的可用性分离开来。例如,异步读取可以启动输入操作,并允许其他工作在数据到达之前继续进行。回调描述了操作完成时应执行的动作。期值(future)或承诺(promise)表示一个可能在稍后可用的结果。await 等语法使代码看起来像顺序代码,尽管例程可能会挂起,随后再恢复执行。

await 不一定会创建新的操作系统线程,也不意味着执行会并行进行。编译器可以将异步例程转换为有限状态机,其状态对应于各个挂起点。挂起后仍需使用的局部值会存储在一个持续存在的执行对象中。被等待的操作完成后,运行时会按照自身的调度规则安排状态机恢复执行。如果结果已经可用,某些语言或运行时可能完全不必挂起。

并发计算关注多个计算过程在时间上交叠推进;并行计算关注同时执行。多个线程可以各自拥有独立的控制流和调用栈,同时共享内存。这样的程序并不总能用一个预先确定的全序来描述。相反,执行顺序受到程序顺序、同步、通信以及所适用的内存模型的约束。调度器从可运行的任务中选择执行对象,但通常不会建立应用层为保证正确性而需要的执行顺序。

同步在不同控制流之间建立约束。锁可以防止同时访问受保护区域;屏障可以让参与者等待,直到所有参与者均已到达;消息接收可以依赖于相应的发送操作。对这些关系作出错误假设,可能导致竞态条件或死锁。即使没有指令同时执行,如果异步例程所依据的假设在其挂起期间失效,它也可能遭遇逻辑上的竞态。

取消为异步计算增加了另一条执行路径。取消通常采用协作方式:任务在指定位置检查取消请求,而不是能够在任意一条指令处被安全地停止。因此,必须明确规定清理工作、子任务的生存期以及异常传播的行为。结构化并发通过将并发工作绑定到词法作用域或动态作用域来处理这些问题,使完成与失败之间的关系更加明确。在分布式系统中,超时会进一步增加判断的难度:调用方未能收到结果,并不能证明远程计算从未执行或已经停止。

处理器执行与性能

在硬件层面,控制流与选中执行的指令地址有关。处理器维护着用于标明指令处理应从何处继续的架构状态。大多数普通指令执行后会继续执行下一条指令,而分支、调用、返回、陷阱和中断则会转向其他位置。这些细节由指令集架构规定;不同机器的实现各不相同,不能仅凭源语言的语法来推断。

条件分支通常检查寄存器的值,或先前操作所设置的条件。无条件分支则直接转移到目标位置。调用和返回还需要管理返回位置,具体可以通过链接寄存器、内存栈或其他约定来实现。间接分支从计算得出的值中获取目标地址,从而支持函数指针、虚分派、跳转表和解释器分派。这些机制既能实现常规的结构化控制结构,也能实现更具动态性的执行转移。

现代处理器通常以流水线方式处理指令,并让多个操作重叠执行。分支会使接下来应取哪些指令变得不确定。分支预测利用从简单规则到基于历史信息的预测器等各种机制,估计分支的结果和目标。预测正确时,流水线便可沿预期路径继续运行。预测错误则需要恢复,并丢弃那些无法成为架构层面实际执行一部分的工作;其代价取决于处理器及分支前后的指令流。

推测执行不止于取指,还允许在预测得到验证之前执行预测路径上的操作。乱序处理器也可以按不同于架构规定顺序的次序执行指令,同时在结果提交时保持所要求的行为。因此,即使一条指令不在程序最终的架构执行路径上,它也可能已在处理器内部执行过。这一区别对性能分析和安全性都很重要。

编译器有时会将短分支替换为条件选择或谓词化操作。这样可以避开难以预测的分支,但也可能执行更多操作,或延长依赖链。同时求值两个备选表达式并不总是安全:未被选中的源代码表达式可能访问无效内存、执行输入输出操作,或引发异常。代码布局和基于性能剖析的优化提供了另一种方法:通过安排经常执行的路径,提高取指效率,并使执行能够顺序落入后续代码。

在图形处理器上,一组执行通道通常会共享指令发射的某些环节。如果各通道选择了不同的分支,具体实现可能会在不同的活动通道掩码下分别执行各条路径。这种分支发散可能减少有效的并行工作量,不过其确切影响取决于架构和工作负载。相反,各通道走向一致的分支可能开销很低。因此,性能不仅取决于源代码中出现了多少分支,还取决于分支的可预测性、路径执行频率、数据依赖、指令布局,以及执行资源的共享方式。

控制流安全与完整性

控制流是网络安全中的一个重要问题,因为能够重定向执行的攻击者可能使程序执行偏离其预期行为的操作。内存破坏可能覆盖返回地址、函数指针或其他影响控制流的值。例如,当程序写入的数据超出已分配对象的边界时,缓冲区溢出就可能破坏相邻的存储区域。这种破坏是否能导致控制转移,取决于程序、内存布局、运行时检查以及已有的防御措施。

对内存可执行权限的限制,可以阻碍将指令注入可写数据区并随后执行这些指令的攻击。但仅靠这类限制,无法阻止攻击者复用可执行内存中已有的指令。霍瓦夫·沙赫姆(Hovav Shacham)在 2007 年的研究中系统阐述了面向返回编程:这种技术通过操纵返回行为,将若干短指令序列串联起来。相关技术则使用间接跳转或间接调用。这些攻击利用了两者之间的差距:代码可以执行,并不意味着向该代码进行的某次特定转移就是合法的。

控制流完整性通常缩写为 CFI,它依据描述允许转移目标的策略来限制控制转移。马丁·阿巴迪(Martín Abadi)及其同事于 2005 年以这一名称将该方法形式化。前向边策略可以约束间接调用和跳转,后向边策略则可以保护返回。其实际防护能力取决于策略的精确程度、覆盖范围、抗篡改能力,以及对程序其余部分所作的假设。

影子栈通过单独保存一份预期返回地址记录,并将普通返回操作所使用的地址与之核对,来保护返回行为。其他机制则对影响控制流的指针进行认证或验证。这些保护措施针对问题的不同方面,可以组合使用。例如,允许将所有类型兼容的函数作为调用目标的策略,可以阻止某些任意重定向,但仍可能允许在应用程序的特定状态下无效的转移。

控制流保护并不等同于保证程序完全正确,也不意味着能够防止所有攻击。攻击者可能破坏非控制数据、滥用获准使用的接口,或者安排一系列恶意转移,而其中每次转移都符合某个粗粒度策略。即使不违反允许的控制流图,类型错误、授权失效和不安全的输入处理仍可能被利用。反过来,对于具有动态加载、运行时代码生成、异常、回调和混合语言组件的软件,构建高度精确的策略可能十分困难。

推测执行还引入了体系结构层面控制流与瞬态控制流之间的区别。2018 年公开披露的 Spectre 类攻击表明,即使沿某条路径进行的推测执行最终未在体系结构层面提交,它仍可能影响微体系结构状态,包括 CPU 缓存。这些影响可能通过计时观测泄露信息。体系结构层面的 CFI 并不会自动消除这些泄露通道。因此,安全分析必须明确:某种防御约束的是哪个执行层面,哪些状态仍可被观测,以及哪些转移或推测行为不在其保障范围内。