第20章 流水和调度
在资源约束、循环依赖和分支预测下执行调度与软件流水；用C编译流水线、状态轨迹和端到端验证门交付依赖图、资源表、周期表、启动间隔与异常反例
学习目标
- 能说明“第20章 流水和调度”如何在资源约束、循环依赖和分支预测下执行调度与软件流水，并区分作者C/Java/ML轨道、中文C版与本站重写
- 能先预测“操作为何能安排到该周期且不破坏依赖和机器资源？”会改变哪一个C接口、树/图状态、AST/IR、汇编或运行结果，再操作三类交互证据
- 能只注入“推测调度把可能故障的加载移动到保护分支之前”，定位首个偏离“第20章 流水和调度的C模块接口、数据结构、状态变换、输出语义与测试始终一致”的状态，并从同一快照完成恢复
为什么从这个问题开始
“第20章 流水和调度”围绕“操作为何能安排到该周期且不破坏依赖和机器资源？”建立贯穿任务：在Tiger C实现轨道中复现“第20章 流水和调度”的输入、状态、变换与验证。先写下哪个C接口、树/图状态、AST/IR、汇编或运行结果会最先变化，再运行参考、故障和恢复路径；运行后补理由不算预测。只有守住“第20章 流水和调度的C模块接口、数据结构、状态变换、输出语义与测试始终一致”并交付依赖图、资源表、周期表、启动间隔与异常反例，单模块测试、编译成功或性能变化才构成机制证据。
原版书目、296个正式坐标与C轨道边界
“第20章 流水和调度”以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版页面核对原版身份。
“第20章 流水和调度”以中文版修订版完整目录核对赵克佳、黄春、沈志宇译《现代编译原理：C语言描述（修订版）》，人民邮电出版社，2018年，385页，ISBN 9787115476883。“第20章 流水和调度”的正式分母为2个部分标题、21个章标题、1个附录标题、251个编号节/小节、附录4节和17个正式“程序设计”项目，合计296个核心层级；每章重复的推荐阅读与习题不另计。
作者页面可访问不等于允许复制书稿，“第20章 流水和调度”不复制、翻译或改写原文、图表、伪码与习题；所有中文讲解、C接口示意、状态轨迹、反例、交互、练习和答案均为独立教学重写。本页独立核对 1只用于核对本页C实现或现代IR边界，不能混入Java/ML轨道或反向证明原书采用本站表述。
原版目录层级与C项目机制
第20章 流水和调度
↡流水和调度对应正式目录坐标“第20章 流水和调度”，在“第20章 流水和调度”中用于把依赖、资源、周期和内存访问映射到调度与局部性优化，并受C接口、内存所有权、状态、目标机与验证边界约束。正式坐标 1/10。 原版目录键 第20章 流水和调度。在“第20章 流水和调度”的第1个正式坐标中，「第20章 流水和调度」通过把依赖、资源、周期和内存访问映射到调度与局部性优化推进调度、流水线、资源与分支；复核者保存依赖图、周期表、地址轨迹、缓存映射、缺失与性能消融，出现非法推测、资源冲突或只对单一缓存参数调优就撤回结论。
20·1 没有资源约束时的循环调度
↡没有资源约束时的循环调度对应正式目录坐标“20.1 没有资源约束时的循环调度”，在“第20章 流水和调度”中用于求解数据流与支配关系并证明优化/SSA变换保语义，并受C接口、内存所有权、状态、目标机与验证边界约束。正式坐标 2/10。 原版目录键 20.1 没有资源约束时的循环调度。围绕“操作为何能安排到该周期且不破坏依赖和机器资源？”，“第20章 流水和调度”在坐标2把「20·1 没有资源约束时的循环调度」落实为求解数据流与支配关系并证明优化/SSA变换保语义；只有固定点、支配树、phi放置、重命名、循环森林与前后IR可重放且反例排除别名、溢出、关键边或跨迭代依赖被忽略，本节点才算掌握。
20·2 有资源约束的循环流水
↡有资源约束的循环流水对应正式目录坐标“20.2 有资源约束的循环流水”，在“第20章 流水和调度”中用于求解数据流与支配关系并证明优化/SSA变换保语义，并受C接口、内存所有权、状态、目标机与验证边界约束。正式坐标 3/10。 原版目录键 20.2 有资源约束的循环流水。“第20章 流水和调度”的目录节点3「20·2 有资源约束的循环流水」不能停在术语或伪码：它要求解数据流与支配关系并证明优化/SSA变换保语义，交付固定点、支配树、phi放置、重命名、循环森林与前后IR，并把别名、溢出、关键边或跨迭代依赖被忽略设为单一反事实。
20·2·1 模调度
↡模调度对应正式目录坐标“20.2.1 模调度”，在“第20章 流水和调度”中用于把依赖、资源、周期和内存访问映射到调度与局部性优化，并受C接口、内存所有权、状态、目标机与验证边界约束。正式坐标 4/10。 原版目录键 20.2.1 模调度。对“第20章 流水和调度”而言，「20·2·1 模调度」在第4次检查中改变可观察状态，因为它负责把依赖、资源、周期和内存访问映射到调度与局部性优化；依赖图、周期表、地址轨迹、缓存映射、缺失与性能消融必须与“第20章 流水和调度的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受非法推测、资源冲突或只对单一缓存参数调优。
20·2·2 寻找最小的启动间距
↡寻找最小的启动间距对应正式目录坐标“20.2.2 寻找最小的启动间距”，在“第20章 流水和调度”中用于把“寻找最小的启动间距”放进调度、流水线、资源与分支的C接口—状态—变换—验证链，并受C接口、内存所有权、状态、目标机与验证边界约束。正式坐标 5/10。 原版目录键 20.2.2 寻找最小的启动间距。在“第20章 流水和调度”的第5个正式坐标中，「20·2·2 寻找最小的启动间距」通过把“寻找最小的启动间距”放进调度、流水线、资源与分支的C接口—状态—变换—验证链推进调度、流水线、资源与分支；复核者保存第20章 流水和调度的输入角色、中间状态、输出、反例与整合证据，出现只复述“寻找最小的启动间距”名称而没有可观察状态、项目实现和恢复验证就撤回结论。
20·2·3 其他控制流
↡其他控制流对应正式目录坐标“20.2.3 其他控制流”，在“第20章 流水和调度”中用于把Tiger AST降到规范树IR、基本块和可调度控制流，并受C接口、内存所有权、状态、目标机与验证边界约束。正式坐标 6/10。 原版目录键 20.2.3 其他控制流。围绕“操作为何能安排到该周期且不破坏依赖和机器资源？”，“第20章 流水和调度”在坐标6把「20·2·3 其他控制流」落实为把Tiger AST降到规范树IR、基本块和可调度控制流；只有AST—IR映射、临时变量、标签、CFG、规范化与差分执行可重放且反例排除副作用重复、标签错连或轨迹调度破坏控制语义，本节点才算掌握。
20·2·4 编译器应该调度指令吗
↡编译器应该调度指令吗对应正式目录坐标“20.2.4 编译器应该调度指令吗”，在“第20章 流水和调度”中用于从树覆盖、活跃固定点和干涉图生成已分配目标指令，并受C接口、内存所有权、状态、目标机与验证边界约束。正式坐标 7/10。 原版目录键 20.2.4 编译器应该调度指令吗。“第20章 流水和调度”的目录节点7「20·2·4 编译器应该调度指令吗」不能停在术语或伪码：它要从树覆盖、活跃固定点和干涉图生成已分配目标指令，交付树模式、use/def、in/out、干涉图、着色、溢出与汇编，并把目标语义、活跃边、合并或溢出重写错误设为单一反事实。
20·3 分支预测
↡分支预测对应正式目录坐标“20.3 分支预测”，在“第20章 流水和调度”中用于把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，并受C接口、内存所有权、状态、目标机与验证边界约束。正式坐标 8/10。 原版目录键 20.3 分支预测。对“第20章 流水和调度”而言，「20·3 分支预测」在第8次检查中改变可观察状态，因为它负责把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹；正则—自动机、token流、项目集、分析表、栈轨迹与冲突必须与“第20章 流水和调度的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受最长匹配、展望符、冲突或恢复状态错误。
20·3·1 静态分支预测
↡静态分支预测对应正式目录坐标“20.3.1 静态分支预测”，在“第20章 流水和调度”中用于把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，并受C接口、内存所有权、状态、目标机与验证边界约束。正式坐标 9/10。 原版目录键 20.3.1 静态分支预测。在“第20章 流水和调度”的第9个正式坐标中，「20·3·1 静态分支预测」通过把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹推进调度、流水线、资源与分支；复核者保存正则—自动机、token流、项目集、分析表、栈轨迹与冲突，出现最长匹配、展望符、冲突或恢复状态错误就撤回结论。
20·3·2 编译器应该预测分支吗
↡编译器应该预测分支吗对应正式目录坐标“20.3.2 编译器应该预测分支吗”，在“第20章 流水和调度”中用于把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，并受C接口、内存所有权、状态、目标机与验证边界约束。正式坐标 10/10。 原版目录键 20.3.2 编译器应该预测分支吗。围绕“操作为何能安排到该周期且不破坏依赖和机器资源？”，“第20章 流水和调度”在坐标10把「20·3·2 编译器应该预测分支吗」落实为把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹；只有正则—自动机、token流、项目集、分析表、栈轨迹与冲突可重放且反例排除最长匹配、展望符、冲突或恢复状态错误，本节点才算掌握。
先预测，再操作三个C轨道实验
1. C模块、输入与翻译流水线
为“第20章 流水和调度”选择正式目录坐标，在参考流水线与单一故障间切换，逐阶段核对接口、状态、输出和不变量。
输入—表示—翻译流水线
第20章 流水和调度
选择正式目录坐标，再比较参考编译合同与单一故障的首个状态分岔。
阶段 1/4
第20章 流水和调度 · C模块与输入
- 输入
- 在Tiger C实现轨道中复现“第20章 流水和调度”的输入、状态、变换与验证
- 变换
- 冻结调度、流水线、资源与分支所需的C接口、源程序、规则、数据结构和版本
- 输出证据
- 第20章 流水和调度的模块合同、输入快照与所有权表
- 不变量检查
- 第20章 流水和调度的类型、所有权、源位置、名字和接口布局没有错位
第20章 流水和调度的可重放协议
| 阶段 | 允许动作 | 必留证据 | 拒绝条件 |
|---|---|---|---|
| 第20章 流水和调度 · C模块与输入 | 冻结调度、流水线、资源与分支所需的C接口、源程序、规则、数据结构和版本 | 第20章 流水和调度的模块合同、输入快照与所有权表 | 未满足“第20章 流水和调度的类型、所有权、源位置、名字和接口布局没有错位” |
| 第20章 流水和调度 · 算法与状态 | 执行在资源约束、循环依赖和分支预测下执行调度与软件流水的最小算法并保存每一步状态 | 第20章 流水和调度的参考轨迹、故障轨迹与首个状态分岔 | 未满足“第20章 流水和调度每一步可由同一C接口、输入、规则和执行顺序复算” |
| 第20章 流水和调度 · 输出与整合 | 比较变换前后AST/IR/汇编/运行时状态和跨模块传递 | 第20章 流水和调度的前后差、接口谱系与恢复路径 | 未满足“第20章 流水和调度没有把单模块通过或单一样例正确当作端到端正确性” |
| 第20章 流水和调度 · 独立验证 | 重放预测、单故障、恢复和不适用边界 | 第20章 流水和调度的接受、回退或拒绝理由 | 未满足“第20章 流水和调度满足“第20章 流水和调度的C模块接口、数据结构、状态变换、输出语义与测试始终一致”” |
unit: "tbc-unit-20"
question: "操作为何能安排到该周期且不破坏依赖和机器资源？"
scenario: "在Tiger C实现轨道中复现“第20章 流水和调度”的输入、状态、变换与验证"
invariant: "第20章 流水和调度的C模块接口、数据结构、状态变换、输出语义与测试始终一致"
fault: "推测调度把可能故障的加载移动到保护分支之前"
evidence: "依赖图、资源表、周期表、启动间隔与异常反例"
reset: restore_concept_mode_stage_trace_step_case_gates_and_artifact“第20章 流水和调度”要求从同一C接口、源程序、规则、数据结构、目标机、预算和执行顺序重放参考、故障与恢复路径。重置后若目录选择、模式、阶段、轨迹步骤、案例、证据门或交付包没有回到基线，本次比较已经混入状态泄漏。
本页回顾
掌握“第20章 流水和调度”不是背术语、表格或伪码，而是围绕“操作为何能安排到该周期且不破坏依赖和机器资源？”重建C接口、输入、状态变换、输出、整合和端到端验证，并用“第20章 流水和调度的C模块接口、数据结构、状态变换、输出语义与测试始终一致”拒绝“推测调度把可能故障的加载移动到保护分支之前”。最终交付为依赖图、资源表、周期表、启动间隔与异常反例。
练习与答案
练习
- 问题 1：C实现合同。 “第20章 流水和调度”为什么必须先冻结C接口、源程序、规则、数据结构、目标机和验证口径？
- 问题 2：目录逐项覆盖。 怎样证明“第20章 流水和调度”的正式目录坐标已经进入机制、交互和程序设计项目？
- 问题 3：故障恢复。 怎样证明“推测调度把可能故障的加载移动到保护分支之前”已经被修正？
名词解释
名词解释
本章出现的专业名词，用大白话再讲一遍。
- 流水和调度
检索键 tbc-A 对应正式目录坐标「第20章 流水和调度」；在“第20章 流水和调度”中用于把依赖、资源、周期和内存访问映射到调度与局部性优化，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
- 没有资源约束时的循环调度
检索键 tbc-B 对应正式目录坐标「20·1 没有资源约束时的循环调度」；在“第20章 流水和调度”中用于求解数据流与支配关系并证明优化/SSA变换保语义，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
- 有资源约束的循环流水
检索键 tbc-C 对应正式目录坐标「20·2 有资源约束的循环流水」；在“第20章 流水和调度”中用于求解数据流与支配关系并证明优化/SSA变换保语义，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
- 模调度
检索键 tbc-D 对应正式目录坐标「20·2·1 模调度」；在“第20章 流水和调度”中用于把依赖、资源、周期和内存访问映射到调度与局部性优化，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
- 寻找最小的启动间距
检索键 tbc-E 对应正式目录坐标「20·2·2 寻找最小的启动间距」；在“第20章 流水和调度”中用于把“寻找最小的启动间距”放进调度、流水线、资源与分支的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
- 其他控制流
检索键 tbc-F 对应正式目录坐标「20·2·3 其他控制流」；在“第20章 流水和调度”中用于把Tiger AST降到规范树IR、基本块和可调度控制流，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
- 编译器应该调度指令吗
检索键 tbc-G 对应正式目录坐标「20·2·4 编译器应该调度指令吗」；在“第20章 流水和调度”中用于从树覆盖、活跃固定点和干涉图生成已分配目标指令，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
- 分支预测
检索键 tbc-H 对应正式目录坐标「20·3 分支预测」；在“第20章 流水和调度”中用于把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
- 静态分支预测
检索键 tbc-I 对应正式目录坐标「20·3·1 静态分支预测」；在“第20章 流水和调度”中用于把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
- 编译器应该预测分支吗
检索键 tbc-J 对应正式目录坐标「20·3·2 编译器应该预测分支吗」；在“第20章 流水和调度”中用于把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。