第9章指令选择

用树模式、动态规划和目标机规则实现Tiger指令选择；用C编译流水线、状态轨迹和端到端验证门交付树模式、覆盖代价、目标指令、临时变量与执行对照

学习目标

能说明“第9章指令选择”如何用树模式、动态规划和目标机规则实现Tiger指令选择，并区分作者C/Java/ML轨道、中文C版与本站重写
能先预测“IR树怎样匹配代价最低且语义等价的目标指令序列？”会改变哪一个C接口、树/图状态、AST/IR、汇编或运行结果，再操作三类交互证据
能只注入“选择规则把有符号比较错误映射为无符号条件码”，定位首个偏离“第9章指令选择的C模块接口、数据结构、状态变换、输出语义与测试始终一致”的状态，并从同一快照完成恢复

为什么从这个问题开始

“第9章指令选择”围绕“IR树怎样匹配代价最低且语义等价的目标指令序列？”建立贯穿任务：在Tiger C实现轨道中复现“第9章指令选择”的输入、状态、变换与验证。先写下哪个C接口、树/图状态、AST/IR、汇编或运行结果会最先变化，再运行参考、故障和恢复路径；运行后补理由不算预测。只有守住“第9章指令选择的C模块接口、数据结构、状态变换、输出语义与测试始终一致”并交付树模式、覆盖代价、目标指令、临时变量与执行对照，单模块测试、编译成功或性能变化才构成机制证据。

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

“第9章指令选择”以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版页面核对原版身份。

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

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

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

第9章指令选择

正式坐标 1/14。 原版目录键 第9章指令选择。在“第9章指令选择”的第1个正式坐标中，「第9章指令选择」通过从树覆盖、活跃固定点和干涉图生成已分配目标指令推进树覆盖、指令规则与目标语义；复核者保存树模式、use/def、in/out、干涉图、着色、溢出与汇编，出现目标语义、活跃边、合并或溢出重写错误就撤回结论。

9·1 指令选择算法

正式坐标 2/14。 原版目录键 9.1 指令选择算法。围绕“IR树怎样匹配代价最低且语义等价的目标指令序列？”，“第9章指令选择”在坐标2把「9·1 指令选择算法」落实为从树覆盖、活跃固定点和干涉图生成已分配目标指令；只有树模式、use/def、in/out、干涉图、着色、溢出与汇编可重放且反例排除目标语义、活跃边、合并或溢出重写错误，本节点才算掌握。

9·1·1 Maximal Munch算法

正式坐标 3/14。 原版目录键 9.1.1 Maximal Munch算法。“第9章指令选择”的目录节点3「9·1·1 Maximal Munch算法」不能停在术语或伪码：它要把“Maximal Munch算法”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链，交付第9章指令选择的输入角色、中间状态、输出、反例与整合证据，并把只复述“Maximal Munch算法”名称而没有可观察状态、项目实现和恢复验证设为单一反事实。

9·1·2 动态规划

正式坐标 4/14。 原版目录键 9.1.2 动态规划。对“第9章指令选择”而言，「9·1·2 动态规划」在第4次检查中改变可观察状态，因为它负责把“动态规划”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链；第9章指令选择的输入角色、中间状态、输出、反例与整合证据必须与“第9章指令选择的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受只复述“动态规划”名称而没有可观察状态、项目实现和恢复验证。

9·1·3 树文法

正式坐标 5/14。 原版目录键 9.1.3 树文法。在“第9章指令选择”的第5个正式坐标中，「9·1·3 树文法」通过把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹推进树覆盖、指令规则与目标语义；复核者保存正则—自动机、token流、项目集、分析表、栈轨迹与冲突，出现最长匹配、展望符、冲突或恢复状态错误就撤回结论。

9·1·4 快速匹配

正式坐标 6/14。 原版目录键 9.1.4 快速匹配。围绕“IR树怎样匹配代价最低且语义等价的目标指令序列？”，“第9章指令选择”在坐标6把「9·1·4 快速匹配」落实为把“快速匹配”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链；只有第9章指令选择的输入角色、中间状态、输出、反例与整合证据可重放且反例排除只复述“快速匹配”名称而没有可观察状态、项目实现和恢复验证，本节点才算掌握。

9·1·5 覆盖算法的效率

正式坐标 7/14。 原版目录键 9.1.5 覆盖算法的效率。“第9章指令选择”的目录节点7「9·1·5 覆盖算法的效率」不能停在术语或伪码：它要把“覆盖算法的效率”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链，交付第9章指令选择的输入角色、中间状态、输出、反例与整合证据，并把只复述“覆盖算法的效率”名称而没有可观察状态、项目实现和恢复验证设为单一反事实。

9·2 CISC机器

正式坐标 8/14。 原版目录键 9.2 CISC机器。对“第9章指令选择”而言，「9·2 CISC机器」在第8次检查中改变可观察状态，因为它负责把“CISC机器”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链；第9章指令选择的输入角色、中间状态、输出、反例与整合证据必须与“第9章指令选择的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受只复述“CISC机器”名称而没有可观察状态、项目实现和恢复验证。

9·3 Tiger编译器的指令选择

正式坐标 9/14。 原版目录键 9.3 Tiger编译器的指令选择。在“第9章指令选择”的第9个正式坐标中，「9·3 Tiger编译器的指令选择」通过从树覆盖、活跃固定点和干涉图生成已分配目标指令推进树覆盖、指令规则与目标语义；复核者保存树模式、use/def、in/out、干涉图、着色、溢出与汇编，出现目标语义、活跃边、合并或溢出重写错误就撤回结论。

9·3·1 抽象的汇编语言指令

正式坐标 10/14。 原版目录键 9.3.1 抽象的汇编语言指令。围绕“IR树怎样匹配代价最低且语义等价的目标指令序列？”，“第9章指令选择”在坐标10把「9·3·1 抽象的汇编语言指令」落实为从树覆盖、活跃固定点和干涉图生成已分配目标指令；只有树模式、use/def、in/out、干涉图、着色、溢出与汇编可重放且反例排除目标语义、活跃边、合并或溢出重写错误，本节点才算掌握。

9·3·2 生成汇编指令

正式坐标 11/14。 原版目录键 9.3.2 生成汇编指令。“第9章指令选择”的目录节点11「9·3·2 生成汇编指令」不能停在术语或伪码：它要从树覆盖、活跃固定点和干涉图生成已分配目标指令，交付树模式、use/def、in/out、干涉图、着色、溢出与汇编，并把目标语义、活跃边、合并或溢出重写错误设为单一反事实。

9·3·3 过程调用

正式坐标 12/14。 原版目录键 9.3.3 过程调用。对“第9章指令选择”而言，「9·3·3 过程调用」在第12次检查中改变可观察状态，因为它负责把“过程调用”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链；第9章指令选择的输入角色、中间状态、输出、反例与整合证据必须与“第9章指令选择的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受只复述“过程调用”名称而没有可观察状态、项目实现和恢复验证。

9·3·4 无帧指针的情形

正式坐标 13/14。 原版目录键 9.3.4 无帧指针的情形。在“第9章指令选择”的第13个正式坐标中，「9·3·4 无帧指针的情形」通过把“无帧指针的情形”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链推进树覆盖、指令规则与目标语义；复核者保存第9章指令选择的输入角色、中间状态、输出、反例与整合证据，出现只复述“无帧指针的情形”名称而没有可观察状态、项目实现和恢复验证就撤回结论。

程序设计：指令选择

正式坐标 14/14。 原版目录键 程序设计：指令选择。围绕“IR树怎样匹配代价最低且语义等价的目标指令序列？”，“第9章指令选择”在坐标14把「程序设计：指令选择」落实为从树覆盖、活跃固定点和干涉图生成已分配目标指令；只有树模式、use/def、in/out、干涉图、着色、溢出与汇编可重放且反例排除目标语义、活跃边、合并或溢出重写错误，本节点才算掌握。

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

分步1 / 3

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

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

输入—表示—翻译流水线

第9章指令选择

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

正式目录坐标

阶段 1/4

第9章指令选择 · C模块与输入

输入: 在Tiger C实现轨道中复现“第9章指令选择”的输入、状态、变换与验证
变换: 冻结树覆盖、指令规则与目标语义所需的C接口、源程序、规则、数据结构和版本
输出证据: 第9章指令选择的模块合同、输入快照与所有权表
不变量检查: 第9章指令选择的类型、所有权、源位置、名字和接口布局没有错位

第9章指令选择的可重放协议

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

unit: "tbc-unit-09"
question: "IR树怎样匹配代价最低且语义等价的目标指令序列？"
scenario: "在Tiger C实现轨道中复现“第9章 指令选择”的输入、状态、变换与验证"
invariant: "第9章 指令选择的C模块接口、数据结构、状态变换、输出语义与测试始终一致"
fault: "选择规则把有符号比较错误映射为无符号条件码"
evidence: "树模式、覆盖代价、目标指令、临时变量与执行对照"
reset: restore_concept_mode_stage_trace_step_case_gates_and_artifact

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

本页回顾

掌握“第9章指令选择”不是背术语、表格或伪码，而是围绕“IR树怎样匹配代价最低且语义等价的目标指令序列？”重建C接口、输入、状态变换、输出、整合和端到端验证，并用“第9章指令选择的C模块接口、数据结构、状态变换、输出语义与测试始终一致”拒绝“选择规则把有符号比较错误映射为无符号条件码”。最终交付为树模式、覆盖代价、目标指令、临时变量与执行对照。

练习与答案

练习

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

问题 2：目录逐项覆盖。 怎样证明“第9章指令选择”的正式目录坐标已经进入机制、交互和程序设计项目？

“第9章指令选择”的目录项「第9章指令选择」：以“从树覆盖、活跃固定点和干涉图生成已分配目标指令”解释作用，用“树模式、use/def、in/out、干涉图、着色、溢出与汇编”提供复核。
“第9章指令选择”的目录项「9·1 指令选择算法」：以“从树覆盖、活跃固定点和干涉图生成已分配目标指令”解释作用，用“树模式、use/def、in/out、干涉图、着色、溢出与汇编”提供复核。
“第9章指令选择”的目录项「9·1·1 Maximal Munch算法」：以“把“Maximal Munch算法”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链”解释作用，用“第9章指令选择的输入角色、中间状态、输出、反例与整合证据”提供复核。 4. “第9章指令选择”的目录项「9·1·2 动态规划」：以“把“动态规划”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链”解释作用，用“第9章指令选择的输入角色、中间状态、输出、反例与整合证据”提供复核。 5. “第9章指令选择”的目录项「9·1·3 树文法」：以“把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹”解释作用，用“正则—自动机、token流、项目集、分析表、栈轨迹与冲突”提供复核。
“第9章指令选择”的目录项「9·1·4 快速匹配」：以“把“快速匹配”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链”解释作用，用“第9章指令选择的输入角色、中间状态、输出、反例与整合证据”提供复核。 7. “第9章指令选择”的目录项「9·1·5 覆盖算法的效率」：以“把“覆盖算法的效率”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链”解释作用，用“第9章指令选择的输入角色、中间状态、输出、反例与整合证据”提供复核。 8. “第9章指令选择”的目录项「9·2 CISC机器」：以“把“CISC机器”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链”解释作用，用“第9章指令选择的输入角色、中间状态、输出、反例与整合证据”提供复核。 9. “第9章指令选择”的目录项「9·3 Tiger编译器的指令选择」：以“从树覆盖、活跃固定点和干涉图生成已分配目标指令”解释作用，用“树模式、use/def、in/out、干涉图、着色、溢出与汇编”提供复核。
“第9章指令选择”的目录项「9·3·1 抽象的汇编语言指令」：以“从树覆盖、活跃固定点和干涉图生成已分配目标指令”解释作用，用“树模式、use/def、in/out、干涉图、着色、溢出与汇编”提供复核。
“第9章指令选择”的目录项「9·3·2 生成汇编指令」：以“从树覆盖、活跃固定点和干涉图生成已分配目标指令”解释作用，用“树模式、use/def、in/out、干涉图、着色、溢出与汇编”提供复核。
“第9章指令选择”的目录项「9·3·3 过程调用」：以“把“过程调用”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链”解释作用，用“第9章指令选择的输入角色、中间状态、输出、反例与整合证据”提供复核。 13. “第9章指令选择”的目录项「9·3·4 无帧指针的情形」：以“把“无帧指针的情形”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链”解释作用，用“第9章指令选择的输入角色、中间状态、输出、反例与整合证据”提供复核。 14. “第9章指令选择”的目录项「程序设计：指令选择」：以“从树覆盖、活跃固定点和干涉图生成已分配目标指令”解释作用，用“树模式、use/def、in/out、干涉图、着色、溢出与汇编”提供复核。

问题 3：故障恢复。 怎样证明“选择规则把有符号比较错误映射为无符号条件码”已经被修正？

为“第9章指令选择”复用同一C接口、输入、规则、数据结构、目标机、预算和顺序，重放参考路径后只注入该故障；记录首个偏离，撤销故障再运行。只有流水线合同、状态轨迹、端到端验证门和树模式、覆盖代价、目标指令、临时变量与执行对照重新满足“第9章指令选择的C模块接口、数据结构、状态变换、输出语义与测试始终一致”，修正才可提交。

名词解释

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

指令选择: 检索键 tbc-A 对应正式目录坐标「第9章指令选择」；在“第9章指令选择”中用于从树覆盖、活跃固定点和干涉图生成已分配目标指令，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
指令选择算法: 检索键 tbc-B 对应正式目录坐标「9·1 指令选择算法」；在“第9章指令选择”中用于从树覆盖、活跃固定点和干涉图生成已分配目标指令，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
Maximal Munch算法: 检索键 tbc-C 对应正式目录坐标「9·1·1 Maximal Munch算法」；在“第9章指令选择”中用于把“Maximal Munch算法”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
动态规划: 检索键 tbc-D 对应正式目录坐标「9·1·2 动态规划」；在“第9章指令选择”中用于把“动态规划”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
树文法: 检索键 tbc-E 对应正式目录坐标「9·1·3 树文法」；在“第9章指令选择”中用于把字符、token、文法、分析表、栈和错误恢复连接为前端轨迹，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
快速匹配: 检索键 tbc-F 对应正式目录坐标「9·1·4 快速匹配」；在“第9章指令选择”中用于把“快速匹配”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
覆盖算法的效率: 检索键 tbc-G 对应正式目录坐标「9·1·5 覆盖算法的效率」；在“第9章指令选择”中用于把“覆盖算法的效率”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
CISC机器: 检索键 tbc-H 对应正式目录坐标「9·2 CISC机器」；在“第9章指令选择”中用于把“CISC机器”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
Tiger编译器的指令选择: 检索键 tbc-I 对应正式目录坐标「9·3 Tiger编译器的指令选择」；在“第9章指令选择”中用于从树覆盖、活跃固定点和干涉图生成已分配目标指令，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
抽象的汇编语言指令: 检索键 tbc-J 对应正式目录坐标「9·3·1 抽象的汇编语言指令」；在“第9章指令选择”中用于从树覆盖、活跃固定点和干涉图生成已分配目标指令，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
生成汇编指令: 检索键 tbc-K 对应正式目录坐标「9·3·2 生成汇编指令」；在“第9章指令选择”中用于从树覆盖、活跃固定点和干涉图生成已分配目标指令，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
过程调用: 检索键 tbc-L 对应正式目录坐标「9·3·3 过程调用」；在“第9章指令选择”中用于把“过程调用”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
无帧指针的情形: 检索键 tbc-M 对应正式目录坐标「9·3·4 无帧指针的情形」；在“第9章指令选择”中用于把“无帧指针的情形”放进树覆盖、指令规则与目标语义的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
指令选择: 检索键 tbc-N 对应正式目录坐标「程序设计：指令选择」；在“第9章指令选择”中用于从树覆盖、活跃固定点和干涉图生成已分配目标指令，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。

第9章 指令选择

学习目标

为什么从这个问题开始

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

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

第9章 指令选择

9·1 指令选择算法

9·1·1 Maximal Munch算法

9·1·2 动态规划

9·1·3 树文法

9·1·4 快速匹配

9·1·5 覆盖算法的效率

9·2 CISC机器

9·3 Tiger编译器的指令选择

9·3·1 抽象的汇编语言指令

9·3·2 生成汇编指令

9·3·3 过程调用

9·3·4 无帧指针的情形

程序设计：指令选择

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

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

第9章 指令选择

第9章 指令选择 · C模块与输入

第9章 指令选择的可重放协议

本页回顾

练习与答案

练习

名词解释

名词解释

讨论

第9章指令选择

第9章指令选择

第9章指令选择

第9章指令选择 · C模块与输入

第9章指令选择的可重放协议