第11章寄存器分配

用简化、合并、冻结、溢出和图着色实现Tiger寄存器分配；用C编译流水线、状态轨迹和端到端验证门交付工作表状态、着色栈、合并日志、溢出重写与目标码

学习目标

能说明“第11章寄存器分配”如何用简化、合并、冻结、溢出和图着色实现Tiger寄存器分配，并区分作者C/Java/ML轨道、中文C版与本站重写
能先预测“合并移动与选择溢出怎样在可着色性和内存代价间取舍？”会改变哪一个C接口、树/图状态、AST/IR、汇编或运行结果，再操作三类交互证据
能只注入“过度乐观合并产生不可着色节点却未正确回退和重写”，定位首个偏离“第11章寄存器分配的C模块接口、数据结构、状态变换、输出语义与测试始终一致”的状态，并从同一快照完成恢复

为什么从这个问题开始

“第11章寄存器分配”围绕“合并移动与选择溢出怎样在可着色性和内存代价间取舍？”建立贯穿任务：在Tiger C实现轨道中复现“第11章寄存器分配”的输入、状态、变换与验证。先写下哪个C接口、树/图状态、AST/IR、汇编或运行结果会最先变化，再运行参考、故障和恢复路径；运行后补理由不算预测。只有守住“第11章寄存器分配的C模块接口、数据结构、状态变换、输出语义与测试始终一致”并交付工作表状态、着色栈、合并日志、溢出重写与目标码，单模块测试、编译成功或性能变化才构成机制证据。

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

“第11章寄存器分配”以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版页面核对原版身份。

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

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

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

第11章寄存器分配

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

11·1 通过简化进行着色

正式坐标 2/13。 原版目录键 11.1 通过简化进行着色。围绕“合并移动与选择溢出怎样在可着色性和内存代价间取舍？”，“第11章寄存器分配”在坐标2把「11·1 通过简化进行着色」落实为把“通过简化进行着色”放进干涉图、合并、着色与溢出的C接口—状态—变换—验证链；只有第11章寄存器分配的输入角色、中间状态、输出、反例与整合证据可重放且反例排除只复述“通过简化进行着色”名称而没有可观察状态、项目实现和恢复验证，本节点才算掌握。

11·2 合并

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

11·3 预着色的结点

正式坐标 4/13。 原版目录键 11.3 预着色的结点。对“第11章寄存器分配”而言，「11·3 预着色的结点」在第4次检查中改变可观察状态，因为它负责把“预着色的结点”放进干涉图、合并、着色与溢出的C接口—状态—变换—验证链；第11章寄存器分配的输入角色、中间状态、输出、反例与整合证据必须与“第11章寄存器分配的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受只复述“预着色的结点”名称而没有可观察状态、项目实现和恢复验证。

11·3·1 机器寄存器的临时副本

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

11·3·2 调用者保护的寄存器和被调用者保护的寄存器

正式坐标 6/13。 原版目录键 11.3.2 调用者保护的寄存器和被调用者保护的寄存器。围绕“合并移动与选择溢出怎样在可着色性和内存代价间取舍？”，“第11章寄存器分配”在坐标6把「11·3·2 调用者保护的寄存器和被调用者保护的寄存器」落实为从树覆盖、活跃固定点和干涉图生成已分配目标指令；只有树模式、use/def、in/out、干涉图、着色、溢出与汇编可重放且反例排除目标语义、活跃边、合并或溢出重写错误，本节点才算掌握。

11·3·3 含预着色结点的例子

正式坐标 7/13。 原版目录键 11.3.3 含预着色结点的例子。“第11章寄存器分配”的目录节点7「11·3·3 含预着色结点的例子」不能停在术语或伪码：它要把“含预着色结点的例子”放进干涉图、合并、着色与溢出的C接口—状态—变换—验证链，交付第11章寄存器分配的输入角色、中间状态、输出、反例与整合证据，并把只复述“含预着色结点的例子”名称而没有可观察状态、项目实现和恢复验证设为单一反事实。

11·4 图着色的实现

正式坐标 8/13。 原版目录键 11.4 图着色的实现。对“第11章寄存器分配”而言，「11·4 图着色的实现」在第8次检查中改变可观察状态，因为它负责从树覆盖、活跃固定点和干涉图生成已分配目标指令；树模式、use/def、in/out、干涉图、着色、溢出与汇编必须与“第11章寄存器分配的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受目标语义、活跃边、合并或溢出重写错误。

11·4·1 传送指令工作表的管理

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

11·4·2 数据结构

正式坐标 10/13。 原版目录键 11.4.2 数据结构。围绕“合并移动与选择溢出怎样在可着色性和内存代价间取舍？”，“第11章寄存器分配”在坐标10把「11·4·2 数据结构」落实为把“数据结构”放进干涉图、合并、着色与溢出的C接口—状态—变换—验证链；只有第11章寄存器分配的输入角色、中间状态、输出、反例与整合证据可重放且反例排除只复述“数据结构”名称而没有可观察状态、项目实现和恢复验证，本节点才算掌握。

11·4·3 程序代码

正式坐标 11/13。 原版目录键 11.4.3 程序代码。“第11章寄存器分配”的目录节点11「11·4·3 程序代码」不能停在术语或伪码：它要把“程序代码”放进干涉图、合并、着色与溢出的C接口—状态—变换—验证链，交付第11章寄存器分配的输入角色、中间状态、输出、反例与整合证据，并把只复述“程序代码”名称而没有可观察状态、项目实现和恢复验证设为单一反事实。

11·5 针对树的寄存器分配

正式坐标 12/13。 原版目录键 11.5 针对树的寄存器分配。对“第11章寄存器分配”而言，「11·5 针对树的寄存器分配」在第12次检查中改变可观察状态，因为它负责把Tiger AST降到规范树IR、基本块和可调度控制流；AST—IR映射、临时变量、标签、CFG、规范化与差分执行必须与“第11章寄存器分配的C模块接口、数据结构、状态变换、输出语义与测试始终一致”对齐，不能接受副作用重复、标签错连或轨迹调度破坏控制语义。

程序设计：图着色

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

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

分步1 / 3

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

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

输入—表示—翻译流水线

第11章寄存器分配

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

正式目录坐标

阶段 1/4

第11章寄存器分配 · C模块与输入

输入: 在Tiger C实现轨道中复现“第11章寄存器分配”的输入、状态、变换与验证
变换: 冻结干涉图、合并、着色与溢出所需的C接口、源程序、规则、数据结构和版本
输出证据: 第11章寄存器分配的模块合同、输入快照与所有权表
不变量检查: 第11章寄存器分配的类型、所有权、源位置、名字和接口布局没有错位

第11章寄存器分配的可重放协议

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

unit: "tbc-unit-11"
question: "合并移动与选择溢出怎样在可着色性和内存代价间取舍？"
scenario: "在Tiger C实现轨道中复现“第11章 寄存器分配”的输入、状态、变换与验证"
invariant: "第11章 寄存器分配的C模块接口、数据结构、状态变换、输出语义与测试始终一致"
fault: "过度乐观合并产生不可着色节点却未正确回退和重写"
evidence: "工作表状态、着色栈、合并日志、溢出重写与目标码"
reset: restore_concept_mode_stage_trace_step_case_gates_and_artifact

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

本页回顾

掌握“第11章寄存器分配”不是背术语、表格或伪码，而是围绕“合并移动与选择溢出怎样在可着色性和内存代价间取舍？”重建C接口、输入、状态变换、输出、整合和端到端验证，并用“第11章寄存器分配的C模块接口、数据结构、状态变换、输出语义与测试始终一致”拒绝“过度乐观合并产生不可着色节点却未正确回退和重写”。最终交付为工作表状态、着色栈、合并日志、溢出重写与目标码。

练习与答案

练习

问题 1：C实现合同。 “第11章寄存器分配”为什么必须先冻结C接口、源程序、规则、数据结构、目标机和验证口径？

问题 2：目录逐项覆盖。 怎样证明“第11章寄存器分配”的正式目录坐标已经进入机制、交互和程序设计项目？

“第11章寄存器分配”的目录项「第11章寄存器分配」：以“从树覆盖、活跃固定点和干涉图生成已分配目标指令”解释作用，用“树模式、use/def、in/out、干涉图、着色、溢出与汇编”提供复核。
“第11章寄存器分配”的目录项「11·1 通过简化进行着色」：以“把“通过简化进行着色”放进干涉图、合并、着色与溢出的C接口—状态—变换—验证链”解释作用，用“第11章寄存器分配的输入角色、中间状态、输出、反例与整合证据”提供复核。 3. “第11章寄存器分配”的目录项「11·2 合并」：以“从树覆盖、活跃固定点和干涉图生成已分配目标指令”解释作用，用“树模式、use/def、in/out、干涉图、着色、溢出与汇编”提供复核。
“第11章寄存器分配”的目录项「11·3 预着色的结点」：以“把“预着色的结点”放进干涉图、合并、着色与溢出的C接口—状态—变换—验证链”解释作用，用“第11章寄存器分配的输入角色、中间状态、输出、反例与整合证据”提供复核。 5. “第11章寄存器分配”的目录项「11·3·1 机器寄存器的临时副本」：以“从树覆盖、活跃固定点和干涉图生成已分配目标指令”解释作用，用“树模式、use/def、in/out、干涉图、着色、溢出与汇编”提供复核。
“第11章寄存器分配”的目录项「11·3·2 调用者保护的寄存器和被调用者保护的寄存器」：以“从树覆盖、活跃固定点和干涉图生成已分配目标指令”解释作用，用“树模式、use/def、in/out、干涉图、着色、溢出与汇编”提供复核。
“第11章寄存器分配”的目录项「11·3·3 含预着色结点的例子」：以“把“含预着色结点的例子”放进干涉图、合并、着色与溢出的C接口—状态—变换—验证链”解释作用，用“第11章寄存器分配的输入角色、中间状态、输出、反例与整合证据”提供复核。 8. “第11章寄存器分配”的目录项「11·4 图着色的实现」：以“从树覆盖、活跃固定点和干涉图生成已分配目标指令”解释作用，用“树模式、use/def、in/out、干涉图、着色、溢出与汇编”提供复核。
“第11章寄存器分配”的目录项「11·4·1 传送指令工作表的管理」：以“从树覆盖、活跃固定点和干涉图生成已分配目标指令”解释作用，用“树模式、use/def、in/out、干涉图、着色、溢出与汇编”提供复核。
“第11章寄存器分配”的目录项「11·4·2 数据结构」：以“把“数据结构”放进干涉图、合并、着色与溢出的C接口—状态—变换—验证链”解释作用，用“第11章寄存器分配的输入角色、中间状态、输出、反例与整合证据”提供复核。 11. “第11章寄存器分配”的目录项「11·4·3 程序代码」：以“把“程序代码”放进干涉图、合并、着色与溢出的C接口—状态—变换—验证链”解释作用，用“第11章寄存器分配的输入角色、中间状态、输出、反例与整合证据”提供复核。 12. “第11章寄存器分配”的目录项「11·5 针对树的寄存器分配」：以“把Tiger AST降到规范树IR、基本块和可调度控制流”解释作用，用“AST—IR映射、临时变量、标签、CFG、规范化与差分执行”提供复核。
“第11章寄存器分配”的目录项「程序设计：图着色」：以“从树覆盖、活跃固定点和干涉图生成已分配目标指令”解释作用，用“树模式、use/def、in/out、干涉图、着色、溢出与汇编”提供复核。

问题 3：故障恢复。 怎样证明“过度乐观合并产生不可着色节点却未正确回退和重写”已经被修正？

为“第11章寄存器分配”复用同一C接口、输入、规则、数据结构、目标机、预算和顺序，重放参考路径后只注入该故障；记录首个偏离，撤销故障再运行。只有流水线合同、状态轨迹、端到端验证门和工作表状态、着色栈、合并日志、溢出重写与目标码重新满足“第11章寄存器分配的C模块接口、数据结构、状态变换、输出语义与测试始终一致”，修正才可提交。

名词解释

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

寄存器分配: 检索键 tbc-A 对应正式目录坐标「第11章寄存器分配」；在“第11章寄存器分配”中用于从树覆盖、活跃固定点和干涉图生成已分配目标指令，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
通过简化进行着色: 检索键 tbc-B 对应正式目录坐标「11·1 通过简化进行着色」；在“第11章寄存器分配”中用于把“通过简化进行着色”放进干涉图、合并、着色与溢出的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
合并: 检索键 tbc-C 对应正式目录坐标「11·2 合并」；在“第11章寄存器分配”中用于从树覆盖、活跃固定点和干涉图生成已分配目标指令，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
预着色的结点: 检索键 tbc-D 对应正式目录坐标「11·3 预着色的结点」；在“第11章寄存器分配”中用于把“预着色的结点”放进干涉图、合并、着色与溢出的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
机器寄存器的临时副本: 检索键 tbc-E 对应正式目录坐标「11·3·1 机器寄存器的临时副本」；在“第11章寄存器分配”中用于从树覆盖、活跃固定点和干涉图生成已分配目标指令，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
调用者保护的寄存器和被调用者保护的寄存器: 检索键 tbc-F 对应正式目录坐标「11·3·2 调用者保护的寄存器和被调用者保护的寄存器」；在“第11章寄存器分配”中用于从树覆盖、活跃固定点和干涉图生成已分配目标指令，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
含预着色结点的例子: 检索键 tbc-G 对应正式目录坐标「11·3·3 含预着色结点的例子」；在“第11章寄存器分配”中用于把“含预着色结点的例子”放进干涉图、合并、着色与溢出的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
图着色的实现: 检索键 tbc-H 对应正式目录坐标「11·4 图着色的实现」；在“第11章寄存器分配”中用于从树覆盖、活跃固定点和干涉图生成已分配目标指令，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
传送指令工作表的管理: 检索键 tbc-I 对应正式目录坐标「11·4·1 传送指令工作表的管理」；在“第11章寄存器分配”中用于从树覆盖、活跃固定点和干涉图生成已分配目标指令，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
数据结构: 检索键 tbc-J 对应正式目录坐标「11·4·2 数据结构」；在“第11章寄存器分配”中用于把“数据结构”放进干涉图、合并、着色与溢出的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
程序代码: 检索键 tbc-K 对应正式目录坐标「11·4·3 程序代码」；在“第11章寄存器分配”中用于把“程序代码”放进干涉图、合并、着色与溢出的C接口—状态—变换—验证链，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
针对树的寄存器分配: 检索键 tbc-L 对应正式目录坐标「11·5 针对树的寄存器分配」；在“第11章寄存器分配”中用于把Tiger AST降到规范树IR、基本块和可调度控制流，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。
图着色: 检索键 tbc-M 对应正式目录坐标「程序设计：图着色」；在“第11章寄存器分配”中用于从树覆盖、活跃固定点和干涉图生成已分配目标指令，需要连接C轨道范围、状态轨迹、整合证据和不适用边界。

第11章 寄存器分配

学习目标

为什么从这个问题开始

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

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

第11章 寄存器分配

11·1 通过简化进行着色

11·2 合并

11·3 预着色的结点

11·3·1 机器寄存器的临时副本

11·3·2 调用者保护的寄存器和被调用者保护的寄存器

11·3·3 含预着色结点的例子

11·4 图着色的实现

11·4·1 传送指令工作表的管理

11·4·2 数据结构

11·4·3 程序代码

11·5 针对树的寄存器分配

程序设计：图着色

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

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

第11章 寄存器分配

第11章 寄存器分配 · C模块与输入

第11章 寄存器分配的可重放协议

本页回顾

练习与答案

练习

名词解释

名词解释

讨论

第11章寄存器分配

第11章寄存器分配

第11章寄存器分配

第11章寄存器分配 · C模块与输入

第11章寄存器分配的可重放协议