Chapter 63: Legalization and Target Constraints

上一章把 instruction selection 解释成“为同一段 IR 语义选择目标机器实现”。这一章继续向后端内部推进：在 selector 能选择指令之前，编译器还要判断当前 IR 操作、类型、寻址形式和目标特性是否落在目标机器可实现范围内。读完本章，读者应能追踪一个非法后端操作如何被改写成合法表示，并判断改写过程保留了什么语义、丢失了什么形态、引入了什么新约束。

本章贯穿一个小目标 T32-mini。它只有 32 位整数通用寄存器，原生整数算术只覆盖 i32，没有原生向量寄存器，没有原生 i64 除法，没有原生 i128 原子操作，内存指令只支持“基址寄存器加小立即数偏移”的寻址模式。这个目标故意很窄，用来观察 portable IR 落到非 portable 硬件时会发生哪些表示变化。

贯穿输入采用接近 LLVM IR 的伪 IR。这里的语法只用于表达操作和类型，不要求读者安装 LLVM，也不声称对应某个真实后端的完整行为。

%a = load i16, ptr %p
%b = add i16 %a, 1
%c = sdiv i64 %x, %y
%v = add <4 x i32> %lhs, %rhs
%old = atomic_cmpxchg i128, ptr %addr, %expected, %desired
%z = load i32, ptr %base_plus_large_offset

这段输入同时触发五类 target constraint：窄整数算术、宽整数除法、向量运算、宽原子操作和受限寻址模式。legalization 的任务是把这些对象改写到目标能处理的 legal set 内，同时保持源 IR 承诺的可观察语义。

63.1 Target-Legal IR Operations

Target-legal IR operation 指“当前目标在后端此阶段承认可继续处理的操作形态”。这个判断同时依赖 opcode、操作数类型、结果类型、内存访问属性、寻址形式和目标特性。一个操作在抽象 IR 中合法，只说明前端或优化器可以表达它；它在目标后端合法，才说明后续 selector、寄存器分配、汇编输出有能力继续处理它。

以贯穿输入里的 %b = add i16 %a, 1 为例，add 这个 opcode 本身很普通，i16 类型却让它落出 T32-mini 的原生算术集合。目标只有 i32 算术单元，后端不能把 add i16 直接交给 selector，因为 selector 只能选择 ADD32 这类目标指令。这里的非法性来自“操作和类型组合”，单独的 add opcode 仍然普通。

再看 %z = load i32, ptr %base_plus_large_offset。结果类型 i32 对 T32-mini 是合法的，load 这个操作也存在，问题在寻址模式。目标只支持“基址寄存器加小立即数偏移”，如果 IR 暗含的大偏移无法编码进目标 load 指令，后端需要先生成地址计算，再用合法 load 读取内存。这个例子说明 legality 的覆盖范围包含算术 opcode，也包含机器指令格式能直接承载的操作数形态。

可以把后端的 legal set 看成目标向编译器声明的一组承诺：哪些类型可以放入寄存器，哪些操作可以直接选择，哪些内存访问可以直接编码，哪些地址形式可以被指令承载。LLVM 的 SelectionDAG 文档把 type legalization 描述为把 DAG 转换为只使用目标原生支持的类型，把 operation legalization 描述为把 DAG 转换为只使用目标原生支持的操作；GlobalISel 的 Legalizer 文档则把 legal instruction 定义为后续目标能够选择并且虚拟寄存器操作数可加载、可存储的 generic machine instruction。可见不同框架的实现形态不同，核心问题都是把表示限制到目标后端承诺处理的范围内：LLVM Target-Independent Code Generator, SelectionDAG LegalizeTypes and Legalize，LLVM GlobalISel Legalizer。

用 T32-mini 表达 legal set，可以得到一个很小的表。这个表只作为当前章节的观察工具，并非完整架构说明。

维度	T32-mini 的合法集合	贯穿输入中的非法点
标量寄存器类型	i32	add i16、sdiv i64、atomic_cmpxchg i128
算术操作	i32 add/sub/and/or/xor	i64 sdiv
向量类型	无原生向量	add <4 x i32>
原子操作	只支持窄整数普通原子	i128 atomic_cmpxchg
寻址模式	基址寄存器加小立即数	大偏移 load

这个表的价值在于把“目标不支持”拆成可检查的事实。读者分析一个后端错误时，应先问非法性来自哪一维：类型宽度、opcode、操作类型组合、内存语义、地址形式，还是目标特性开关。只有定位到具体维度，后续才知道应做 promote、split、expand、libcall、custom lowering，还是直接报告 unsupported。

贯穿输入在 legalization 前后的信息关系可以用一张图表达。图里只展示本章关心的阶段边界，不展开寄存器分配和最终编码。

图中的关键边界是 legality query。它把一个 IR 节点放到目标约束里检查，输出的问题是“这个后端阶段是否承认该形态”，程序整体正确性仍由前后多个阶段共同保证。当 query 失败，legalizer 会选择让表示更接近 legal set 的动作；当所有节点都落入 legal set，selector 才有稳定输入。

63.2 Type Legalization and Operation Legalization

Type legalization 处理“值的类型无法被目标寄存器或操作承载”的问题。Operation legalization 处理“操作本身或操作与类型组合无法被目标指令实现”的问题。二者经常交织，但区分它们能让读者定位改写动作的依据：前者先问值应如何放入目标可管理的载体，后者再问同一语义应由哪些合法操作表达。

贯穿输入里的 add i16 主要触发 type legalization。T32-mini 只有 i32 算术，因此后端可以把 i16 操作提升到 i32 上执行，再截断回 i16 结果。对无符号加法或普通二进制模加法，关键不变量是低 16 位结果保持一致。一个可能的合法化表示如下。

%a16 = load i16, ptr %p
%a32 = zext i16 %a16 to i32
%sum32 = add i32 %a32, 1
%b = trunc i32 %sum32 to i16

这个改写保留了 i16 加法的低位结果，同时产生了新的扩展和截断节点。后端后续看到的是合法的 i32 add，但源码层面的“16 位操作直接发生”这个形态已经丢失。读汇编时，读者可能看到 32 位加法配合截断、掩码或窄存储，这不代表源程序语义变成了 32 位结果；它代表后端用 32 位硬件载体实现 16 位语义。

有符号比较、算术右移、溢出检查会改变扩展选择。若输入是 icmp slt i16 %a, 0，后端需要把符号位扩展到 i32，再用 i32 有符号比较，或用等价位操作构造同样结论。这里的不变量不再只是“低 16 位一致”，还包括符号解释一致。type legalization 的难点就在这里：类型形态可以改变，值在源类型下的语义解释要被保留下来。

贯穿输入里的 %c = sdiv i64 %x, %y 同时触发 type 和 operation 的问题。i64 超出 T32-mini 的寄存器算术宽度，sdiv 比普通加法更难用少量 i32 指令模拟。后端通常有三条路：用多条 32 位操作展开出长除法序列，调用运行时 helper，或在目标声明 unsupported。选择哪条路取决于目标 ABI、运行时库可用性、性能目标和后端实现成本。

%c = call i64 @__compiler_rt_sdiv_i64(i64 %x, i64 %y)

上面的伪 IR 表达 libcall lowering。它保留的语义是 i64 有符号除法的结果和异常边界由运行时 helper 承担；它引入的新约束是链接阶段必须能解析 helper 符号，调用约定必须正确传递 i64 参数和返回值，运行时库版本必须和目标 ABI 匹配。这个例子说明 operation legalization 可能把一个局部算术节点改写成跨越编译产物和运行时库的契约。

同一输入在不同后端框架中会有不同组织方式。SelectionDAG 传统上把 LegalizeTypes 和 Legalize 分成可观察阶段，先把类型推到目标支持集合，再把操作推到目标支持集合。GlobalISel 的 Legalizer 文档明确说明 type 与 operation legalization 在该框架中不分离，而是在 GMIR 中迭代改写。读者迁移理解时，应抓住稳定抽象：legalization 指一类“让当前表示进入目标合法集合”的改写过程，具体 pass 名称会随框架变化。

合法化结果还要满足结构不变量。新插入的扩展、截断、merge、unmerge、地址计算、helper 调用都要被后续阶段理解。若 legalizer 生成了 selector 不认识的节点，问题只是从一个非法节点转移到另一个非法节点。可靠的后端会让每次改写都朝 legal set 推进，并保证迭代能够终止。

63.3 Expand, Promote, Split, and Libcall Lowering

常见 legalization 策略可以按“表示如何变化”来区分：promote 把小类型提升到目标原生类型；expand 把一个非法操作展开成多个合法操作；split 把宽值或向量拆成多个目标能处理的部分；libcall lowering 把难以直接生成的操作交给运行时库函数。这些策略可以组合使用，真实后端常把几种策略应用到同一条输入上。

Promote 适合窄整数、窄布尔和部分浮点情况。贯穿输入的 i16 add 提升到 i32 add 后，只要扩展和截断位置正确，低位语义可以保持。Promote 的收益是复用目标原生 ALU 和寄存器，代价是可能增加截断、掩码、扩展指令，并可能改变寄存器压力。对读者来说，看到“源代码是短整数，汇编大量使用 32 位寄存器”时，应先判断这是否来自目标原生寄存器宽度带来的提升。

Expand 适合目标没有单条指令，但能由若干合法指令组合实现的操作。大偏移 load 是一个简单例子。源 IR 把地址看成一个抽象指针，目标 load 指令只能编码小偏移，后端就先计算地址，再执行合法 load。

%addr = add i32 %base, LARGE_OFFSET
%z = load i32, ptr %addr

这个 expand 保留的是最终读取地址一致。它丢失的是“一个 load 指令携带完整地址表达式”的形态。后续调度器和寄存器分配会看到额外地址计算，可能影响指令顺序、寄存器占用和延迟。地址 legalization 因此不仅是语法改写，也会改变机器级资源使用。

Split 适合宽整数和向量。贯穿输入里的 add <4 x i32> 在没有原生向量寄存器的 T32-mini 上可以被拆成四个标量加法。如果目标有 v2i32 向量，合法化也可能把 v4i32 拆成两个 v2i32。split 的核心不变量是每个 lane 的结果与原向量对应 lane 一致，同时保留向量操作规定的 lane 顺序和异常语义。

%lhs0 = extractelement <4 x i32> %lhs, 0
%lhs1 = extractelement <4 x i32> %lhs, 1
%lhs2 = extractelement <4 x i32> %lhs, 2
%lhs3 = extractelement <4 x i32> %lhs, 3
%rhs0 = extractelement <4 x i32> %rhs, 0
%rhs1 = extractelement <4 x i32> %rhs, 1
%rhs2 = extractelement <4 x i32> %rhs, 2
%rhs3 = extractelement <4 x i32> %rhs, 3
%s0 = add i32 %lhs0, %rhs0
%s1 = add i32 %lhs1, %rhs1
%s2 = add i32 %lhs2, %rhs2
%s3 = add i32 %lhs3, %rhs3
%v = buildvector %s0, %s1, %s2, %s3

这个示例故意写得直观，真实后端会使用更接近机器表示的 extract、unmerge、build 或 merge 节点。读者需要观察数据如何从一个向量值分解成多个标量值，又如何重新组成等价结果；节点名服务于这个数据流。split 之后，后端拥有更多独立标量操作，指令调度空间可能增加，代码体积也可能增加。

Libcall lowering 适合实现成本高、需要 ABI 协助或目标普遍依赖运行时的操作。i64 sdiv 是典型例子。宽整数除法、软浮点运算、部分内存 intrinsic、宽原子操作都可能走 helper。libcall 的关键边界是语义责任被移动到运行时库：编译器要生成正确调用，helper 要实现目标语义，链接器要找到符号，运行时要按 ABI 运行。

对于 atomic_cmpxchg i128，legalization 的选择更严格。普通 split 把 128 位原子拆成两个 64 位或四个 32 位访问，通常会破坏“整体原子性”这个语义。若目标没有 128 位原子指令，也没有运行时或内核辅助来提供同等原子语义，后端应把它判为 unsupported 或交给明确的 libcall/outline atomic 方案。这里的判断顺序是先检查语义要求，再检查目标能力，最后选择改写策略。只看位宽会得出错误策略。

四类策略可以压缩成一组迁移判断。遇到非法节点时，先问它缺的是合法载体、合法操作、合法组合，还是合法语义提供者。缺载体时考虑 promote 或 split；缺操作但可组合时考虑 expand；缺复杂语义实现时考虑 libcall 或 custom lowering；目标无法提供等价语义时报告 unsupported。这个顺序能帮助读者从错误信息、IR dump 或汇编变化中定位后端改写的原因。

63.4 Target Feature Flags and Conditional Legality

Target feature flags 让 legal set 从“架构名”变成“架构名加具体扩展集合”。同一 ISA 家族中，SIMD、crypto、floating-point、atomic、bit manipulation 等扩展会改变可直接选择的类型和操作。conditional legality 指某个操作在一组目标特性下合法，在另一组目标特性下需要改写或报告 unsupported。

把 T32-mini 扩展成两个变体：T32-mini 原始版本没有向量寄存器，T32-mini+simd128 支持 128 位向量寄存器和 v4i32 add。同一条输入 %v = add <4 x i32> %lhs, %rhs 在两个变体上的 legal set 不同。

目标变体	add <4 x i32> 的 legality	可能后续形态
T32-mini	非法	拆成四个 i32 add
T32-mini+simd128	合法	进入 selector，选择向量加法

这个差异会直接改变代码质量和后端路径。无 SIMD 目标需要 extract、标量 add、build；有 SIMD 目标可能保留单个向量操作。源码、前端 IR 和优化器结论可以完全相同，最终后端行为却因为 feature flags 改变。分析“为什么同一程序在两个编译选项下生成不同汇编”时，读者应把 feature flags 纳入第一轮检查。

conditional legality 还会影响 libcall 选择。假设某目标在启用硬浮点扩展时支持 f64 add，关闭硬浮点时需要 soft-float helper。源 IR 仍然是浮点加法，合法化策略却从“保留浮点操作并选择硬件指令”变成“lower 到运行时 helper”。如果开发者只看 IR 层，会看不到差异；要解释最终代码，必须检查 target triple、CPU 型号、feature flags、ABI 和后端合法集合。

原子操作的条件性更容易出错。某些目标可能支持普通 i32 原子 load/store，但对 compare-exchange、宽原子、特定 memory ordering 需要额外扩展或运行时方案。legalization 不能把“有原子扩展”粗略等同于“所有原子操作都合法”。正确查询应包含操作种类、位宽、对齐、地址空间和 ordering。贯穿输入的 atomic_cmpxchg i128 因此要被看作“宽度、原子性和目标特性共同决定的 legality 问题”。

LLVM GlobalISel 的 Legalizer 文档强调 legality query 中包含 opcode、类型、内存操作大小和 atomic ordering 等信息，并且规则会从上到下处理。这个设计提示读者：合法性判断应尽量建立在当前指令自身可观察的信息上，目标特性则作为构造规则集的上下文。把条件写清楚，后端才能稳定地决定一条指令是 legal、widen、narrow、lower、libcall、custom 还是 unsupported。

工程上，feature flags 还承担可复现性作用。一个 codegen bug 报告如果只提供源程序和错误汇编，缺少目标 triple、CPU、feature flags 和优化等级，后端维护者很难重现 legality 决策。最小复现材料应包含输入 IR、目标配置、触发的 pass pipeline 或等价命令，以及实际输出。这样才能判断问题发生在 legality 声明、legalization 动作、instruction selection，还是后续机器级优化。

63.5 Engineering Insight: Legalization Is Where Portable IR Meets Non-Portable Hardware Reality

Legalization 的工程意义在于把 portable IR 的表达能力压入具体硬件和 ABI 的可执行范围。Portable IR 可以表达 i16 add、i64 sdiv、向量加法、宽原子和抽象地址；目标机器提供的是有限寄存器宽度、有限指令格式、有限内存语义和有限扩展集合。legalizer 连接这两个世界，并为后续 selector 提供稳定输入。

这个阶段保留的核心对象是语义。i16 add 经过 promote 后，低 16 位结果要一致；有符号判断经过扩展后，符号解释要一致；向量 split 后，每个 lane 的结果要一致；i64 sdiv 走 libcall 后，除法结果和 ABI 边界要一致；宽原子无法拆分时，整体原子性要被尊重。形态可以变化，语义不变量必须被证明或由目标支持者承诺。

这个阶段丢失的对象是部分源码形态和抽象 IR 形态。源程序里的窄类型可能在机器级变成宽寄存器运算；一个抽象操作可能变成多条指令；一个向量可能变成多个标量；一个算术节点可能变成 helper 调用；一个地址表达式可能变成先算地址再访问内存。读汇编或 Machine IR 时，读者应把这些差异先解释为 legalization 的结果，再判断是否存在优化、调度或 ABI 问题。

这个阶段引入的新约束包括寄存器压力、代码体积、调用约定、运行时库依赖、feature flags 可复现性和 selector 覆盖范围。promote 可能增加扩展与截断，split 可能增加临时值数量，libcall 可能引入符号和 ABI 依赖，custom lowering 可能把语义责任交给目标专属代码。后端质量往往取决于这些约束的组合处理，单条目标指令是否存在只是其中一个输入事实。

分析 legalization 问题可以使用固定检查顺序。第一步，列出输入节点的 opcode、类型、内存属性、地址形式和目标配置。第二步，查询这些对象是否落在目标 legal set 内。第三步，把非法性归因到类型、操作、操作类型组合、寻址模式、内存语义或 feature flag。第四步，检查 legalizer 选择的是 promote、expand、split、libcall、custom 还是 unsupported。第五步，验证改写后的表示是否保留语义不变量，并且所有新节点都能继续被后续阶段处理。

回到贯穿输入，T32-mini 的合理 legalization 结论可以这样描述：i16 add 通过 promote 到 i32 保留低 16 位结果；i64 sdiv 倾向走 libcall 或目标专属长除法展开；add <4 x i32> 在无 SIMD 时 split 成标量操作，在有 SIMD 时可保留向量操作；atomic_cmpxchg i128 需要目标提供整体原子语义，否则报告 unsupported；大偏移 load 通过地址计算 expand 成合法寻址。每个结论都来自目标能力和语义不变量的交叉检查。

Legalization 因此是后端从“抽象程序意义”走向“真实机器约束”的第一个强制收敛点。它不追求把程序改得更快，而是先把程序改到目标机器能承认、能选择、能继续生成的形态。后续寄存器分配、调度和编码都建立在这个前提上。

最小自检任务

给定一个目标 U32-soft：它只有 i32 整数寄存器，支持 i32 add/sub/mul，不支持原生 i64 mul，没有向量寄存器，支持基址寄存器加小立即数寻址，运行时库提供 @__muldi3。判断下面三条伪 IR 分别适合哪种 legalization 策略，并说明每条策略保留的语义不变量。

%a = add i8 %x, %y
%b = mul i64 %m, %n
%c = add <2 x i32> %p, %q

答案要点

%a = add i8 %x, %y 适合 promote 到 i32 后再截断回 i8。关键判断是目标缺少 i8 算术载体，但有 i32 add。不变量是低 8 位结果与源 i8 add 一致；如果后续把结果用于有符号判断，还要检查符号扩展位置。

%b = mul i64 %m, %n 适合 libcall lowering 到 @__muldi3，也可能由目标专属长乘法 expand 实现。题目已经说明运行时库提供 helper，因此 libcall 是最直接策略。不变量是 i64 乘法结果按语言或 IR 规定保持一致，并且调用约定、返回值传递和链接符号满足目标 ABI。

%c = add <2 x i32> %p, %q 适合 split 或 scalarize 成两个 i32 add。关键判断是目标没有向量寄存器，但支持 i32 add。不变量是 lane 0 和 lane 1 的结果分别与源向量对应 lane 一致，并且重组后的向量顺序保持一致。

本章知识点总结

• Legal set：后端合法集合描述目标愿意继续处理的类型、操作、内存属性、地址形式和特性条件。
• 合法性来源：一个 IR 节点的非法性可能来自 opcode、类型、操作类型组合、寻址模式、内存语义或 feature flag。
• 类型合法化：type legalization 把值放入目标可管理的载体，同时保留源类型下的语义解释。
• 操作合法化：operation legalization 把目标无法直接实现的操作改写成合法操作序列、helper 调用或目标专属 lowering。
• Promote：promote 使用更大的目标原生类型执行窄操作，再通过截断、掩码或扩展保持源类型结果。
• Expand：expand 把单个非法操作拆成多个合法操作，常见于地址计算、复合操作和目标缺失的简单指令。
• Split：split 把宽值或向量拆成目标可处理的部分，并保留每个部分对应的结果关系。
• Libcall：libcall lowering 把复杂语义交给运行时 helper，同时引入 ABI、链接和运行时库依赖。
• 原子边界：宽原子操作只有在目标或运行时能提供整体原子语义时才能合法化成等价实现。
• 条件合法性：target feature flags 会改变同一 IR 节点的合法性，分析 codegen 差异必须记录目标配置。
• 语义不变量：legalization 可以改变表示形态，但必须保留源 IR 承诺的可观察语义。
• 排查顺序：先列输入节点和目标配置，再归因非法维度，最后验证改写策略和后续阶段可处理性。