第18章循环优化

用支配、循环不变量、归纳变量、边界检查和展开优化循环；用C编译流水线、状态轨迹和端到端验证门交付循环森林、支配、归纳关系、前后IR与边界反例

学习目标

能说明“第18章循环优化”如何用支配、循环不变量、归纳变量、边界检查和展开优化循环，并区分作者C/Java/ML轨道、中文C版与本站重写
能先预测“一项循环变换怎样证明在所有入口、退出和溢出条件下合法？”会改变哪一个C接口、树/图状态、AST/IR、汇编或运行结果，再操作三类交互证据
能只注入“把可能溢出的整数归纳表达式按数学整数规则强度削弱”，定位首个偏离“第18章循环优化的C模块接口、数据结构、状态变换、输出语义与测试始终一致”的状态，并从同一快照完成恢复

为什么从这个问题开始

“第18章循环优化”围绕“一项循环变换怎样证明在所有入口、退出和溢出条件下合法？”建立贯穿任务：在Tiger C实现轨道中复现“第18章循环优化”的输入、状态、变换与验证。先写下哪个C接口、树/图状态、AST/IR、汇编或运行结果会最先变化，再运行参考、故障和恢复路径；运行后补理由不算预测。只有守住“第18章循环优化的C模块接口、数据结构、状态变换、输出语义与测试始终一致”并交付循环森林、支配、归纳关系、前后IR与边界反例，单模块测试、编译成功或性能变化才构成机制证据。

原版书目、296个正式坐标与C轨道边界

“第18章循环优化”以Andrew W. Appel作者官方目录核对 Modern Compiler Implementation 的C、Java、ML三种实现轨道、2部分、21章和Tiger语言附录；以作者C版页面核对Andrew·W·Appel与Maia Ginsburg、Cambridge University Press、C实现轨道、平装ISBN 0-521-60765-5、软件/练习模块与勘误入口，再以Cambridge C版页面核对原版身份。

“第18章循环优化”以中文版修订版完整目录核对赵克佳、黄春、沈志宇译《现代编译原理：C语言描述（修订版）》，人民邮电出版社，2018年，385页，ISBN 9787115476883。“第18章循环优化”的正式分母为2个部分标题、21个章标题、1个附录标题、251个编号节/小节、附录4节和17个正式“程序设计”项目，合计296个核心层级；每章重复的推荐阅读与习题不另计。

作者页面可访问不等于允许复制书稿，“第18章循环优化”不复制、翻译或改写原文、图表、伪码与习题；所有中文讲解、C接口示意、状态轨迹、反例、交互、练习和答案均为独立教学重写。本页独立核对 1只用于核对本页C实现或现代IR边界，不能混入Java/ML轨道或反向证明原书采用本站表述。

原版目录层级与C项目机制

第18章循环优化

正式坐标 1/14。 原版目录键 第18章循环优化。在“第18章循环优化”的第1个正式坐标中，「第18章循环优化」通过求解数据流与支配关系并证明优化/SSA变换保语义推进循环结构、归纳与语义边界；复核者保存固定点、支配树、phi放置、重命名、循环森林与前后IR，出现别名、溢出、关键边或跨迭代依赖被忽略就撤回结论。

18·1 必经结点

正式坐标 2/14。 原版目录键 18.1 必经结点。围绕“一项循环变换怎样证明在所有入口、退出和溢出条件下合法？”，“第18章循环优化”在坐标2把「18·1 必经结点」落实为把“必经结点”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链；只有第18章循环优化的输入角色、中间状态、输出、反例与整合证据可重放且反例排除只复述“必经结点”名称而没有可观察状态、项目实现和恢复验证，本节点才算掌握。

18·1·1 寻找必经结点的算法

正式坐标 3/14。 原版目录键 18.1.1 寻找必经结点的算法。“第18章循环优化”的目录节点3「18·1·1 寻找必经结点的算法」不能停在术语或伪码：它要把“寻找必经结点的算法”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链，交付第18章循环优化的输入角色、中间状态、输出、反例与整合证据，并把只复述“寻找必经结点的算法”名称而没有可观察状态、项目实现和恢复验证设为单一反事实。

18·1·2 直接必经结点

正式坐标 4/14。 原版目录键 18.1.2 直接必经结点。对“第18章循环优化”而言，「18·1·2 直接必经结点」在第4次检查中改变可观察状态，因为它负责把“直接必经结点”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链；第18章循环优化的输入角色、中间状态、输出、反例与整合证据必须与“第18章循环优化的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受只复述“直接必经结点”名称而没有可观察状态、项目实现和恢复验证。

18·1·3 循环

正式坐标 5/14。 原版目录键 18.1.3 循环。在“第18章循环优化”的第5个正式坐标中，「18·1·3 循环」通过求解数据流与支配关系并证明优化/SSA变换保语义推进循环结构、归纳与语义边界；复核者保存固定点、支配树、phi放置、重命名、循环森林与前后IR，出现别名、溢出、关键边或跨迭代依赖被忽略就撤回结论。

18·1·4 循环前置结点

正式坐标 6/14。 原版目录键 18.1.4 循环前置结点。围绕“一项循环变换怎样证明在所有入口、退出和溢出条件下合法？”，“第18章循环优化”在坐标6把「18·1·4 循环前置结点」落实为求解数据流与支配关系并证明优化/SSA变换保语义；只有固定点、支配树、phi放置、重命名、循环森林与前后IR可重放且反例排除别名、溢出、关键边或跨迭代依赖被忽略，本节点才算掌握。

18·2 循环不变量计算

正式坐标 7/14。 原版目录键 18.2 循环不变量计算。“第18章循环优化”的目录节点7「18·2 循环不变量计算」不能停在术语或伪码：它要求解数据流与支配关系并证明优化/SSA变换保语义，交付固定点、支配树、phi放置、重命名、循环森林与前后IR，并把别名、溢出、关键边或跨迭代依赖被忽略设为单一反事实。

18·3 归纳变量

正式坐标 8/14。 原版目录键 18.3 归纳变量。对“第18章循环优化”而言，「18·3 归纳变量」在第8次检查中改变可观察状态，因为它负责求解数据流与支配关系并证明优化/SSA变换保语义；固定点、支配树、phi放置、重命名、循环森林与前后IR必须与“第18章循环优化的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受别名、溢出、关键边或跨迭代依赖被忽略。

18·3·1 发现归纳变量

正式坐标 9/14。 原版目录键 18.3.1 发现归纳变量。在“第18章循环优化”的第9个正式坐标中，「18·3·1 发现归纳变量」通过求解数据流与支配关系并证明优化/SSA变换保语义推进循环结构、归纳与语义边界；复核者保存固定点、支配树、phi放置、重命名、循环森林与前后IR，出现别名、溢出、关键边或跨迭代依赖被忽略就撤回结论。

18·3·2 强度削弱

正式坐标 10/14。 原版目录键 18.3.2 强度削弱。围绕“一项循环变换怎样证明在所有入口、退出和溢出条件下合法？”，“第18章循环优化”在坐标10把「18·3·2 强度削弱」落实为把“强度削弱”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链；只有第18章循环优化的输入角色、中间状态、输出、反例与整合证据可重放且反例排除只复述“强度削弱”名称而没有可观察状态、项目实现和恢复验证，本节点才算掌握。

18·3·3 删除

正式坐标 11/14。 原版目录键 18.3.3 删除。“第18章循环优化”的目录节点11「18·3·3 删除」不能停在术语或伪码：它要把“删除”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链，交付第18章循环优化的输入角色、中间状态、输出、反例与整合证据，并把只复述“删除”名称而没有可观察状态、项目实现和恢复验证设为单一反事实。

18·3·4 重写比较

正式坐标 12/14。 原版目录键 18.3.4 重写比较。对“第18章循环优化”而言，「18·3·4 重写比较」在第12次检查中改变可观察状态，因为它负责把“重写比较”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链；第18章循环优化的输入角色、中间状态、输出、反例与整合证据必须与“第18章循环优化的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受只复述“重写比较”名称而没有可观察状态、项目实现和恢复验证。

18·4 数组边界检查

正式坐标 13/14。 原版目录键 18.4 数组边界检查。在“第18章循环优化”的第13个正式坐标中，「18·4 数组边界检查」通过求解数据流与支配关系并证明优化/SSA变换保语义推进循环结构、归纳与语义边界；复核者保存固定点、支配树、phi放置、重命名、循环森林与前后IR，出现别名、溢出、关键边或跨迭代依赖被忽略就撤回结论。

18·5 循环展开

正式坐标 14/14。 原版目录键 18.5 循环展开。围绕“一项循环变换怎样证明在所有入口、退出和溢出条件下合法？”，“第18章循环优化”在坐标14把「18·5 循环展开」落实为求解数据流与支配关系并证明优化/SSA变换保语义；只有固定点、支配树、phi放置、重命名、循环森林与前后IR可重放且反例排除别名、溢出、关键边或跨迭代依赖被忽略，本节点才算掌握。

先预测，再操作三个C轨道实验

分步1 / 3

1. C模块、输入与翻译流水线

为“第18章循环优化”选择正式目录坐标，在参考流水线与单一故障间切换，逐阶段核对接口、状态、输出和不变量。

输入—表示—翻译流水线

第18章循环优化

选择正式目录坐标，再比较参考编译合同与单一故障的首个状态分岔。

正式目录坐标

阶段 1/4

第18章循环优化 · C模块与输入

输入: 在Tiger C实现轨道中复现“第18章循环优化”的输入、状态、变换与验证
变换: 冻结循环结构、归纳与语义边界所需的C接口、源程序、规则、数据结构和版本
输出证据: 第18章循环优化的模块合同、输入快照与所有权表
不变量检查: 第18章循环优化的类型、所有权、源位置、名字和接口布局没有错位

第18章循环优化的可重放协议

阶段	允许动作	必留证据	拒绝条件
第18章循环优化 · C模块与输入	冻结循环结构、归纳与语义边界所需的C接口、源程序、规则、数据结构和版本	第18章循环优化的模块合同、输入快照与所有权表	未满足“第18章循环优化的类型、所有权、源位置、名字和接口布局没有错位”
第18章循环优化 · 算法与状态	执行用支配、循环不变量、归纳变量、边界检查和展开优化循环的最小算法并保存每一步状态	第18章循环优化的参考轨迹、故障轨迹与首个状态分岔	未满足“第18章循环优化每一步可由同一C接口、输入、规则和执行顺序复算”
第18章循环优化 · 输出与整合	比较变换前后AST/IR/汇编/运行时状态和跨模块传递	第18章循环优化的前后差、接口谱系与恢复路径	未满足“第18章循环优化没有把单模块通过或单一样例正确当作端到端正确性”
第18章循环优化 · 独立验证	重放预测、单故障、恢复和不适用边界	第18章循环优化的接受、回退或拒绝理由	未满足“第18章循环优化满足“第18章循环优化的C模块接口、数据结构、状态变换、输出语义与测试始终一致””

unit: "tbc-unit-18"
question: "一项循环变换怎样证明在所有入口、退出和溢出条件下合法？"
scenario: "在Tiger C实现轨道中复现“第18章 循环优化”的输入、状态、变换与验证"
invariant: "第18章 循环优化的C模块接口、数据结构、状态变换、输出语义与测试始终一致"
fault: "把可能溢出的整数归纳表达式按数学整数规则强度削弱"
evidence: "循环森林、支配、归纳关系、前后IR与边界反例"
reset: restore_concept_mode_stage_trace_step_case_gates_and_artifact

“第18章循环优化”要求从同一C接口、源程序、规则、数据结构、目标机、预算和执行顺序重放参考、故障与恢复路径。重置后若目录选择、模式、阶段、轨迹步骤、案例、证据门或交付包没有回到基线，本次比较已经混入状态泄漏。

本页回顾

掌握“第18章循环优化”不是背术语、表格或伪码，而是围绕“一项循环变换怎样证明在所有入口、退出和溢出条件下合法？”重建C接口、输入、状态变换、输出、整合和端到端验证，并用“第18章循环优化的C模块接口、数据结构、状态变换、输出语义与测试始终一致”拒绝“把可能溢出的整数归纳表达式按数学整数规则强度削弱”。最终交付为循环森林、支配、归纳关系、前后IR与边界反例。

练习与答案

练习

问题 1：C实现合同。 “第18章循环优化”为什么必须先冻结C接口、源程序、规则、数据结构、目标机和验证口径？

问题 2：目录逐项覆盖。 怎样证明“第18章循环优化”的正式目录坐标已经进入机制、交互和程序设计项目？

“第18章循环优化”的目录项「第18章循环优化」：以“求解数据流与支配关系并证明优化/SSA变换保语义”解释作用，用“固定点、支配树、phi放置、重命名、循环森林与前后IR”提供复核。
“第18章循环优化”的目录项「18·1 必经结点」：以“把“必经结点”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链”解释作用，用“第18章循环优化的输入角色、中间状态、输出、反例与整合证据”提供复核。 3. “第18章循环优化”的目录项「18·1·1 寻找必经结点的算法」：以“把“寻找必经结点的算法”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链”解释作用，用“第18章循环优化的输入角色、中间状态、输出、反例与整合证据”提供复核。 4. “第18章循环优化”的目录项「18·1·2 直接必经结点」：以“把“直接必经结点”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链”解释作用，用“第18章循环优化的输入角色、中间状态、输出、反例与整合证据”提供复核。 5. “第18章循环优化”的目录项「18·1·3 循环」：以“求解数据流与支配关系并证明优化/SSA变换保语义”解释作用，用“固定点、支配树、phi放置、重命名、循环森林与前后IR”提供复核。
“第18章循环优化”的目录项「18·1·4 循环前置结点」：以“求解数据流与支配关系并证明优化/SSA变换保语义”解释作用，用“固定点、支配树、phi放置、重命名、循环森林与前后IR”提供复核。
“第18章循环优化”的目录项「18·2 循环不变量计算」：以“求解数据流与支配关系并证明优化/SSA变换保语义”解释作用，用“固定点、支配树、phi放置、重命名、循环森林与前后IR”提供复核。
“第18章循环优化”的目录项「18·3 归纳变量」：以“求解数据流与支配关系并证明优化/SSA变换保语义”解释作用，用“固定点、支配树、phi放置、重命名、循环森林与前后IR”提供复核。
“第18章循环优化”的目录项「18·3·1 发现归纳变量」：以“求解数据流与支配关系并证明优化/SSA变换保语义”解释作用，用“固定点、支配树、phi放置、重命名、循环森林与前后IR”提供复核。
“第18章循环优化”的目录项「18·3·2 强度削弱」：以“把“强度削弱”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链”解释作用，用“第18章循环优化的输入角色、中间状态、输出、反例与整合证据”提供复核。 11. “第18章循环优化”的目录项「18·3·3 删除」：以“把“删除”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链”解释作用，用“第18章循环优化的输入角色、中间状态、输出、反例与整合证据”提供复核。 12. “第18章循环优化”的目录项「18·3·4 重写比较」：以“把“重写比较”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链”解释作用，用“第18章循环优化的输入角色、中间状态、输出、反例与整合证据”提供复核。 13. “第18章循环优化”的目录项「18·4 数组边界检查」：以“求解数据流与支配关系并证明优化/SSA变换保语义”解释作用，用“固定点、支配树、phi放置、重命名、循环森林与前后IR”提供复核。
“第18章循环优化”的目录项「18·5 循环展开」：以“求解数据流与支配关系并证明优化/SSA变换保语义”解释作用，用“固定点、支配树、phi放置、重命名、循环森林与前后IR”提供复核。

问题 3：故障恢复。 怎样证明“把可能溢出的整数归纳表达式按数学整数规则强度削弱”已经被修正？

为“第18章循环优化”复用同一C接口、输入、规则、数据结构、目标机、预算和顺序，重放参考路径后只注入该故障；记录首个偏离，撤销故障再运行。只有流水线合同、状态轨迹、端到端验证门和循环森林、支配、归纳关系、前后IR与边界反例重新满足“第18章循环优化的C模块接口、数据结构、状态变换、输出语义与测试始终一致”，修正才可提交。

名词解释

本章出现的专业名词，用大白话再讲一遍。

循环优化: 检索键 tbc-A 对应正式目录坐标「第18章循环优化」；在“第18章循环优化”中用于求解数据流与支配关系并证明优化/SSA变换保语义，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
必经结点: 检索键 tbc-B 对应正式目录坐标「18·1 必经结点」；在“第18章循环优化”中用于把“必经结点”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
寻找必经结点的算法: 检索键 tbc-C 对应正式目录坐标「18·1·1 寻找必经结点的算法」；在“第18章循环优化”中用于把“寻找必经结点的算法”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
直接必经结点: 检索键 tbc-D 对应正式目录坐标「18·1·2 直接必经结点」；在“第18章循环优化”中用于把“直接必经结点”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
循环: 检索键 tbc-E 对应正式目录坐标「18·1·3 循环」；在“第18章循环优化”中用于求解数据流与支配关系并证明优化/SSA变换保语义，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
循环前置结点: 检索键 tbc-F 对应正式目录坐标「18·1·4 循环前置结点」；在“第18章循环优化”中用于求解数据流与支配关系并证明优化/SSA变换保语义，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
循环不变量计算: 检索键 tbc-G 对应正式目录坐标「18·2 循环不变量计算」；在“第18章循环优化”中用于求解数据流与支配关系并证明优化/SSA变换保语义，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
归纳变量: 检索键 tbc-H 对应正式目录坐标「18·3 归纳变量」；在“第18章循环优化”中用于求解数据流与支配关系并证明优化/SSA变换保语义，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
发现归纳变量: 检索键 tbc-I 对应正式目录坐标「18·3·1 发现归纳变量」；在“第18章循环优化”中用于求解数据流与支配关系并证明优化/SSA变换保语义，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
强度削弱: 检索键 tbc-J 对应正式目录坐标「18·3·2 强度削弱」；在“第18章循环优化”中用于把“强度削弱”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
删除: 检索键 tbc-K 对应正式目录坐标「18·3·3 删除」；在“第18章循环优化”中用于把“删除”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
重写比较: 检索键 tbc-L 对应正式目录坐标「18·3·4 重写比较」；在“第18章循环优化”中用于把“重写比较”放进循环结构、归纳与语义边界的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
数组边界检查: 检索键 tbc-M 对应正式目录坐标「18·4 数组边界检查」；在“第18章循环优化”中用于求解数据流与支配关系并证明优化/SSA变换保语义，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
循环展开: 检索键 tbc-N 对应正式目录坐标「18·5 循环展开」；在“第18章循环优化”中用于求解数据流与支配关系并证明优化/SSA变换保语义，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。

第18章 循环优化

学习目标

为什么从这个问题开始

原版书目、296个正式坐标与C轨道边界

原版目录层级与C项目机制

第18章 循环优化

18·1 必经结点

18·1·1 寻找必经结点的算法

18·1·2 直接必经结点

18·1·3 循环

18·1·4 循环前置结点

18·2 循环不变量计算

18·3 归纳变量

18·3·1 发现归纳变量

18·3·2 强度削弱

18·3·3 删除

18·3·4 重写比较

18·4 数组边界检查

18·5 循环展开

先预测，再操作三个C轨道实验

1. C模块、输入与翻译流水线

第18章 循环优化

第18章 循环优化 · C模块与输入

第18章 循环优化的可重放协议

本页回顾

练习与答案

练习

名词解释

名词解释

讨论

第18章循环优化

第18章循环优化

第18章循环优化

第18章循环优化 · C模块与输入

第18章循环优化的可重放协议