本文整理自 Justin M. Fargnoli 和 Alex E. MacLean 在 2024 LLVM Developers’ Meeting 的分享《A Beginner’s Guide to SelectionDAG》。原材料是一份 89 页的 PDF 幻灯片。1. 为什么要了解 SelectionDAG如果你写过 LLVM Pass大概率比较熟悉 LLVM IR。但当 IR 进入后端准备变成真正的机器指令时事情会变复杂不同 CPU/GPU 支持的类型不一样同一个操作在不同目标上可能需要不同降级方式有些目标架构有特殊指令比如把mul add合成一条mad最终生成代码的质量很大程度取决于后端这一段如何处理。SelectionDAG 就是 LLVM 后端中非常重要的一套指令选择框架。很多目标都使用它例如X86、NVPTX、MIPS、Hexagon等。一句话概括SelectionDAG 是 LLVM 后端里介于 LLVM IR 和机器指令之间的一种 DAG 表示用来完成类型合法化、操作合法化、DAG 优化、指令选择和调度等工作。注意LLVM 里还有另一个后端框架叫GlobalISel它可以看作 SelectionDAG 的替代方案之一但本文只讨论 SelectionDAG。2. SelectionDAG 在编译流程中的位置LLVM 常见编译流程可以粗略理解成Source Code | Frontend | LLVM IR | opt | LLVM IR | llc | Assembly / Machine CodeSelectionDAG 主要工作在llc阶段也就是 LLVM IR 被送进后端之后。在 SelectionDAG 视角里后端大致会经历LLVM IR | SelectionDAG Construction | Type Legalization | Operation Legalization | DAG Combiner | Instruction Selection | Instruction Scheduling | MachineIR / MachineInstr这里最核心的问题是LLVM IR 很通用但目标机器不通用。SelectionDAG 的工作就是把“通用表达”逐步变成“目标机器能接受的表达”。3. SelectionDAG 的数据结构SelectionDAG 不是一整份程序对应一个 DAG而是每个基本块通常对应一个 SelectionDAG。也就是说一个函数里的多个 basic block会被分别构造成多个 DAG。基本块是什么就是一段中间没有跳转分叉的直线代码。例如define i32 foo(i32%a,i32%b){entry:%xadd i32%a,1br label%next next:%ymul i32%x,%b ret i32%y}这里有两个 basic blockentry:%xadd i32%a,1br label%next next:%ymul i32%x,%b ret i32%ySelectionDAG 不会把整个 foo 函数一次性画成一个大图而是分别处理entry block-一个 SelectionDAG next block-另一个 SelectionDAG为什么要这样因为指令选择、合法化、调度这些工作大多数时候是在基本块内部完成的。比如 entry 里只需要考虑a 1然后跳转到 next它的 DAG 大概关心$a1|ADD|%x|BR next而 next 里只需要考虑%x * b然后返回它的 DAG 大概关心%x $b|MUL|RET那问题来了%x 是在 entry 里算出来的但在 next 里使用两个 DAG 怎么连起来答案是SelectionDAG 不直接用一条 DAG 边跨 basic block 连接它们而是通过寄存器/虚拟寄存器等机制传递。可以粗略理解成entry DAG:算出%x CopyToReg把%x 放到某个虚拟寄存器里 br next next DAG:CopyFromReg从虚拟寄存器里取出%x 用%x 参与 mul所以重点是不是 整个函数-一个巨大 SelectionDAG 而是 basic block1-DAG1basic block2-DAG2basic block3-DAG3跨 block 的值比如 %x不会靠“同一个 DAG 里的边”表达而是靠 CopyToReg、CopyFromReg、虚拟寄存器、PHI 等后端机制衔接。3.1 MVT 和 EVT理解 SelectionDAG首先要理解它的类型系统。MVT是Machine Value Type表示机器值类型。它是一组 SelectionDAG 后端能讨论的基础类型例如整数i1、i32、i128浮点f16、bf16、f80向量v2i32、v128bf16特殊类型Other、Glue但每个目标架构只支持其中一部分。比如某个目标可能支持i32但不支持i128。EVT是Extended Value Type可以理解为 MVT 的扩展版。它包含所有 MVTLLVM IR 中支持的整数、浮点、向量类型一些目标机器未必原生支持的奇怪类型比如i3、v99i99。但 EVT 并不包含 LLVM IR 的所有类型比如struct和array就不在 SelectionDAG 类型集合里。因此结构体相关操作在构建 DAG 时通常要被拆开。3.2 SDNodeDAG 的节点SDNode是 SelectionDAG 的基本节点。每个节点通常包含Opcode说明这个节点做什么例如ISD::ADD、ISD::MUL、ISD::Constant一个或多个结果零个或多个操作数其他附加信息例如常量值、flags、内存访问信息等。比如下面这段 IR%y add i32 %a, 5 %z mul i32 %y, 3 br label %join在 DAG 中可能会出现ISD::Constant 5ISD::ADDISD::Constant 3ISD::MULISD::BR3.3 SDValue节点的输出SDValue表示某个SDNode的一个输出结果。为什么不是一个节点只有一个输出因为 SelectionDAG 里的节点可以有多个结果。比如一个节点可能同时产生一个普通值一个 chain一个 glue。所以SDValue通常包含两件事它来自哪个SDNode它是这个节点的第几个结果。可以把 SDValue 的三类输出理解成类型表示什么典型用途普通值真正参与计算的数据i32、f32、v4i32chain非数据依赖主要保证副作用顺序load/store/call/branchglue很紧的“绑定关系”常用于 flags/carry/条件码compare branchadd-with-carrychain保证“有副作用的操作”顺序普通数据依赖只能表达这种关系ab 的结果|v 再乘以 c但有些操作之间没有普通数据依赖却不能乱序。例如store i321,ptr%p%vload i32,ptr%pstore 没有产生一个普通的 i32 给 load 用但 load 必须在 store 后面否则结果可能错。这时 SelectionDAG 用 chain 表示EntryToken|store|load|branch/return所以 chain 的作用是我不是一个普通计算值但我告诉调度器这些有副作用的节点必须按这个顺序执行。常见需要 chain 的节点LOADSTORECALLRETBRCopyToRegCopyFromReg可以把 chain 理解成“执行顺序许可证”或者“副作用顺序线”。glue把两个节点强绑定在一起glue 比 chain 更特殊。它通常表示一种机器级别的隐式依赖。最典型例子是条件跳转3.4 SDUse节点的输入SDUse表示某个节点使用了另一个节点产生的值也就是 DAG 边上的“输入关系”。它包含被使用的SDValue使用这个值的SDNode这是用户节点的第几个 operand。可以简单理解为SDNode 产生 SDValue SDUse 把 SDValue 接到另一个 SDNode 的输入上4. DAG 里不只是数据依赖还有 Chain 和 Glue普通 DAG 边可以表达数据依赖比如mul必须等add的结果。但编译器还需要表达一些“不是普通数据值”的依赖。4.1 跨基本块的数据流CopyFromReg / CopyToRegSelectionDAG 是按基本块构建的。那如果某个 SSA 值跨 basic block 使用怎么办SelectionDAG 使用CopyFromReg从寄存器读入一个在别处定义、当前块要用的值CopyToReg把当前块定义的值写到寄存器供别处使用。它们帮助 SelectionDAG 在基本块级别表示跨块数据流。4.2 Chain表达调度和副作用依赖有些操作没有普通数据依赖但顺序不能乱。例如store 必须在某些 load/store 前后保持顺序branch 通常要在基本块里的其他操作之后call、volatile load/store 等带副作用操作不能随便重排。这时 SelectionDAG 使用chain值来表示非数据依赖。每个 basic block 的 DAG 通常会有一个EntryToken表示进入这个基本块的起点依赖。DAG 还会有一个root通常对应终结指令例如 branch。对于多个 chain 需要汇合的情况会用ISD::TokenFactor把多个依赖合并起来。4.3 MemSDNode表达内存访问信息对于 load/storeDAG 中会使用MemSDNode记录内存相关信息比如访问大小对齐源 IR 指针是否 volatile读写关系。这些信息对合法化、优化和调度都很重要。5. 构建 SelectionDAGSelectionDAG 构建阶段的目标是把每个 basic block 的 LLVM IR 转成 DAG 表示。大多数 LLVM IR 指令和 SelectionDAG 节点之间有近似 1:1 的对应关系但也有例外。一个典型例外是结构体%l load {i32, i1}, ptr %p1, align 8 %v extractvalue {i32, i1} %l, 0SelectionDAG 不直接支持 struct 类型所以这类操作会被拆成元素级别的操作。例如一个结构体 load 可能变成两个 load一个读i32另一个读i1。还有一些操作目标相关性太强无法完全由通用逻辑处理例如函数调用约定。目标后端通常需要实现SDValueTargetLowering::LowerCall(...);SDValueTargetLowering::LowerFormalArgs(...);SDValueTargetLowering::LowerReturn(...);这些 hook 用来处理 call、函数参数和返回值。6. 类型合法化Type LegalizationLLVM IR 能表达很多类型但目标机器不一定支持。类型合法化的目标是把目标不支持的类型降级成目标支持的类型。例如目标支持i32但不支持i24目标支持i64但不支持i128目标支持v4i8但不支持v3i8。目标后端通过addRegisterClass(MVT)告诉 SelectionDAG哪些 MVT 对当前目标是合法的。之后 SelectionDAG 会为各种类型建立一张 action 表用不同策略处理非法类型。常见策略包括Action含义TypeLegal目标原生支持这个类型TypePromoteInteger把整数提升成更大的整数TypeExpandInteger把整数拆成两个更小的整数TypeSoftenFloat把浮点转换成同大小整数处理TypePromoteFloat把浮点提升成更大的浮点TypeScalarizeVector把单元素向量标量化TypeSplitVector把向量拆成两半TypeWidenVector把向量扩宽成更大的合法向量举几个例子。6.1i128加法拆成两个i64如果目标不支持i128但支持i64那么i128 add可能会被拆成low 64-bit add high 64-bit add with carrySelectionDAG 不只是“改类型”它会真的生成新的 DAG 节点。6.2i24提升到i32如果目标不支持i24但支持i32可以把i24操作提升成i32操作。但提升后要注意高位不能污染结果所以 SelectionDAG 会通过 mask 等操作保留低 24 位。6.3v3i8扩宽成v4i8某些目标更愿意用更宽的向量类型。例如 Hexagon 可以把v3i8扩宽成v4i8然后在合法向量类型上执行操作。目标后端可以重写LegalizeTypeActiongetPreferredVectorAction(MVT);来告诉 SelectionDAG 某个向量类型更适合怎么合法化。7. 操作合法化Operation Legalization类型合法了不代表操作也合法。比如目标支持f16类型但不一定支持f16上的除法。SelectionDAG 有 400 多个 opcode不同目标不可能全部支持。操作合法化的目标是把 SelectionDAG 中目标不支持的 opcode 或 opcode type 组合变成目标支持的操作。目标后端通过setOperationAction(Opcode,MVT,LegalizeAction);告诉 SelectionDAG 某个操作该怎么处理。常见LegalizeAction包括Action含义Legal目标原生支持Promote用更大的类型执行Expand用其他合法操作模拟Custom调用目标后端自定义 hook7.1 Promote用更大的类型做NVPTX 示例中ISD::FDIV对f32是合法的但对f16不合法。可以这样告诉 SelectionDAGsetOperationAction(ISD::FDIV,MVT::f16,Promote);于是f16除法可能会变成f16 - f32 f32 fdiv f32 - f167.2 Expand用其他操作模拟MIPS 示例中如果ISD::BSWAP对i32不合法可以setOperationAction(ISD::BSWAP,MVT::i32,Expand);然后用 shift、and、or 等合法操作模拟 byte swap。7.3 Custom交给目标后端自己降级有时通用 Expand 不够目标需要自定义逻辑。这时可以setOperationAction(Opcode,MVT,Custom);SelectionDAG 遇到对应操作时会调用LowerOperation()例如NVPTX 可以把某些VECTOR_SHUFFLE降成目标特定的NVPTXISD::PRMTX86 可以把ISD::ABS自定义降成目标特定节点。8. DAGCombinerSelectionDAG 里的 InstCombineLLVM IR 层已经有很多优化为什么 SelectionDAG 还要优化原因有两个构建 DAG 和合法化过程中会引入新的冗余有些优化只有在目标相关语境下才知道值不值得做。DAGCombiner可以理解为SelectionDAG 版本的 InstCombine。它会做通用 peephole也会询问TargetLoweringInfo判断某些变换对当前目标是否划算。例如// fold (fadd A, (fneg B)) - (fsub A, B)if(SDValue NegN1TLI.getCheaperNegatedExpression(N1,DAG))returnDAG.getNode(ISD::FSUB,VT,N0,NegN1);目标也可以注册自己的 DAG combinesetTargetDAGCombine(Opcode);然后实现PerformDAGCombine()典型用途包括减少寄存器压力利用目标特殊指令消除目标上代价较高的操作。9. 指令选择Instruction Selection经过构建、合法化和 combine 之后DAG 里很多节点仍然是通用节点例如ISD::ADDISD::MULISD::LOAD指令选择阶段的目标是把通用 SDNode 替换成目标机器节点。机器节点使用的是目标相关的MachineInstruction Opcode。由于这件事高度目标相关每个目标后端都要实现virtualvoidSelect(SDNode*N)0;但如果所有匹配逻辑都手写会非常痛苦。所以 LLVM 使用 TableGen 自动生成大量匹配代码。9.1 TableGen 需要三类东西TableGen 指令选择一般需要描述SDPatternOperator要在 DAG 里匹配什么Instruction要生成哪条机器指令Pattern从 DAG 模式到机器指令的映射。例如一个简化的add i32模式def add : SDNodeISD::ADD, SDTIntBinOp, [SDNPCommutative, SDNPAssociative]; def ADDi32rr : NVPTXInst (outs Int32Regs:$dst), (ins Int32Regs:$a, Int32Regs:$b), add.s32 \t$dst, $a, $b;; def : Pattern (set Int32Regs:$dst, (add (i32 Int32Regs:$a), (i32 Int32Regs:$b))), (ADDi32rr Int32Regs:$dst, Int32Regs:$a, Int32Regs:$b);含义是ISD::ADD(i32 a, i32 b) NVPTX::ADDi32rr目标后端也可以在 TableGen 匹配之前插入自定义逻辑voidNVPTXDAGToDAGISel::Select(SDNode*N){// Custom logic hereSelectCode(N);// TableGen based selection}SelectionDAG 指令选择会按拓扑顺序遍历 DAG。TableGen 模式之间也会按启发式排序例如优先匹配更复杂的模式、优先生成更少指令等。10. 指令调度Instruction Scheduling指令选择后DAG 里已经基本是机器节点。Instruction Scheduling 的输入是机器节点 DAG输出是一条线性的机器指令序列。也就是说它要决定DAG of machine nodes linear sequence of machine instructions本文重点不展开调度。实际深入时可以继续看 LLVM 的 scheduling model、machine scheduler 等内容。11. 示例为 PTX 支持mad指令最后用 PDF 里的例子把流程串起来。PTX 里有一条mad指令语义是mad(a, b, c) a * b c如果 LLVM IR 是define i32 foo(i32 %0, i32 %1, i32 %2) { %mul mul i32 %0, %1 %add add i32 %mul, %2 ret i32 %add }我们希望后端不要生成普通的mul add而是生成mad.lo.s32 %r4, %r1, %r2, %r3;为什么因为一条mad通常比两条指令延迟更低也能减少寄存器压力。11.1 先判断要改哪里这个例子里不需要改类型合法化也不需要改操作合法化因为mad支持的类型已经是合法类型ISD::ADD和ISD::MUL本身也是合法操作。真正需要做的是两件事DAG Combine把add(mul(a, b), c)折叠成目标特定节点NVPTXISD::IMADInstruction Selection把NVPTXISD::IMAD选成机器指令NVPTX::MAD32rrr。11.2 注册目标特定 DAG Combine因为我们想在看到ISD::ADD时检查它的第一个 operand 是不是ISD::MUL所以先注册NVPTXTargetLowering::NVPTXTargetLowering(){...setTargetDAGCombine(ISD::ADD);...}然后在PerformDAGCombine()里分发SDValueNVPTXTargetLowering::PerformDAGCombine(SDNode*N){switch(N-getOpcode()){caseISD::ADD:returnPerformADDCombine(N);...}}11.3 把add mul合成IMAD简化后的 combine 逻辑如下SDValuePerformADDCombine(SDNode*N){if(N-getOperand(0).getOpcode()!ISD::MUL)returnSDValue();if(N-getValueType()!MVT::i32)returnSDValue();returnDAG.getNode(NVPTXISD::IMAD,N-getValueType(),N-getOperand(0).getOperand(0),N-getOperand(0).getOperand(1),N-getOperand(1));}它做的事情是ISD::ADD(ISD::MUL(a, b), c) NVPTXISD::IMAD(a, b, c)11.4 在 TableGen 中声明节点和机器指令先声明目标特定 SDNodedef SDTIMAD : SDTypeProfile1, 3, [SDTCisSameAs0, 1, SDTCisSameAs0, 2, SDTCisSameAs0, 3, SDTCisInt0]; def imad : SDNodeNVPTXISD::IMAD, SDTIMAD;再声明机器指令def MAD32rrr : NVPTXInst (outs Int32Regs:$dst), (ins Int32Regs:$a, Int32Regs:$b, Int32Regs:$c), mad.lo.s32 \t$dst, $a, $b;;这里需要注意幻灯片里的 assembly string 展示为$dst, $a, $b但mad(a, b, c)和后面的 pattern 都是三个输入。阅读时应以三输入语义和 pattern 为准。11.5 建立 Selection Pattern最后写 pattern让 TableGen 知道如何从imad选到机器指令def : Pattern (set Int32Regs:$dst, (imad (i32 Int32Regs:$a), (i32 Int32Regs:$b), (i32 Int32Regs:$c))), (MAD32rrr Int32Regs:$dst, Int32Regs:$a, Int32Regs:$b, Int32Regs:$c);这样整个路径就是LLVM IR: add(mul(a, b), c) SelectionDAG: ISD::ADD(ISD::MUL(a, b), c) DAG Combine: NVPTXISD::IMAD(a, b, c) Instruction Selection: NVPTX::MAD32rrr PTX: mad.lo.s3212. 调试 SelectionDAG 的常用参数PDF 最后给了几个非常实用的 debug-only 参数-debug-onlyisel -debug-onlylegalize-types -debug-onlylegalizedag -debug-onlydagcombine如果你在调 LLVM 后端可以用这些参数观察指令选择发生了什么类型合法化做了什么操作合法化生成了哪些节点DAG combine 是否触发。13. 总结SelectionDAG 可以按下面这条主线理解把每个 basic block 的 LLVM IR 建成 DAG | 把目标不支持的类型变合法 | 把目标不支持的操作变合法 | 用 DAGCombiner 清理和做目标相关 peephole | 把通用 DAG 节点选择成机器节点 | 调度成线性机器指令序列它最难的地方不在某个单独 API而在于“通用逻辑”和“目标相关逻辑”之间的边界。遇到问题时建议先问自己三个问题这是类型不合法还是操作不合法这是通用 lowering 能解决还是必须目标自定义我需要的是 legalizationDAG combine还是 instruction selection如果能把问题放回这条流水线里SelectionDAG 就会清晰很多。参考Justin M. Fargnoli, Alex E. MacLean, NVIDIA,A Beginners Guide to SelectionDAG, 2024 LLVM Developers’ MeetingLLVM Target-Independent Code Generator 文档LLVM Instruction Selector 文档LLVM 后端 legalizations 相关文章