DAG 是什么DAG Directed Acyclic Graph有向无环图在编译器后端Selection DAG 是一种中间表示用来描述单个基本块内的计算逻辑。要素含义节点Node一个操作add、mul、load、store 等边Edge数据依赖一个节点的结果流向另一个节点有向数据从生产者流向消费者无环没有循环单个基本块内天然无环DAG 与树的区别树每个节点只有一个父节点公共子表达式必须复制。DAG一个节点可以有多个父节点公共子表达式只出现一次。DAG 更紧凑且天然暴露了公共子表达式。为什么要建 Selection DAG指令选择之前要先建 Selection DAG原因有三个统一表示把 IR 转换成一种便于匹配的图结构。暴露依赖边直接表示数据依赖便于分析。便于拆树DAG 可以拆分成树的森林每棵树独立匹配指令模式。怎么把 IR 翻译成 DAG步骤① 遍历基本块中的每条 IR 指令 ② 为每条指令创建一个节点操作类型 结果类型 ③ 为每个操作数创建边从操作数节点指向当前节点 ④ 如果操作数已经存在SSA 值直接复用节点不重复创建 ⑤ 处理内存操作load/store时额外建立内存依赖边详细例子原始 IR单个基本块%1 add i32 %a, %b %2 mul i32 %1, %c %3 sub i32 %1, %d %4 mul i32 %2, %3 ret i32 %4逐步构建 DAG第 1 步处理%1 add i32 %a, %b创建节点add(%a, %b) 创建叶子%a, %b 创建边%a → add, %b → add %1 指向 add 节点第 2 步处理%2 mul i32 %1, %c创建节点mul(%1, %c) %1 已经存在 → 复用节点 创建叶子%c 创建边%1 → mul, %c → mul %2 指向 mul 节点处理%3 sub i32 %1, %d创建节点sub(%1, %d) %1 已经存在 → 复用节点 创建叶子%d 创建边%1 → sub, %d → sub %3 指向 sub 节点第 4 步处理%4 mul i32 %2, %3创建节点mul(%2, %3) %2 和 %3 已经存在 → 复用节点 创建边%2 → mul, %3 → mul %4 指向 mul 节点关键观察%1 add(%a, %b) 只出现一次但被 mul 和 sub 同时使用。如果用树表示%1 会被复制两份。DAG 的边直接表示%1 的结果流向两个消费者。为什么 DAG 要拆分成树的森林原因树匹配算法如 BURG、Maximal Munch只能处理树不能直接处理 DAG。因为 DAG 中一个节点有多个父节点树匹配算法不知道该从哪里开始匹配。所以需要把 DAG拆分成一系列树森林每棵树独立匹配。拆分规则共享节点有多个父节点的节点成为拆分点。拆分时共享节点的结果被“复制”到每棵消费树中但只计算一次。具体例子上面的 DAG拆分点%1 add(%a, %b) 有 2 个父节点mul 和 sub所以它是拆分点。拆分成 4 棵树树 1add(%a, %b) → %1 根%1叶子%a, %b 树 2mul(%1, %c) → %2 根%2叶子%1, %c 树 3sub(%1, %d) → %3 根%3叶子%1, %d 树 4mul(%2, %3) → %4 根%4叶子%2, %3按拓扑顺序匹配① 匹配树 1 → 生成 add 指令 → %1 存入寄存器 r1 ② 匹配树 2 → 生成 mul 指令 → %2 存入寄存器 r2 ③ 匹配树 3 → 生成 sub 指令 → %3 存入寄存器 r3 ④ 匹配树 4 → 生成 mul 指令 → %4 存入寄存器 r4生成的汇编假设每条指令代价为 1ADD r1, %a, %b ; 树 1 MUL r2, r1, %c ; 树 2 SUB r3, r1, %d ; 树 3 MUL r4, r2, r3 ; 树 4注意%1 只计算一次树 1结果 r1 被树 2 和树 3 复用。如果不用 DAG 而用树表示%1 会被计算两次每棵树各算一次浪费指令完整流程总结原始 IR基本块 │ ▼ ① 构建 Selection DAG │ 遍历 IR创建节点和边 │ 共享 SSA 值 → 复用节点 ▼ ② 拆分成树的森林 │ 在共享节点处拆分 │ 每棵树独立匹配 ▼ ③ 树匹配BURG / Maximal Munch │ 用机器指令模式覆盖每棵树 │ 动态规划选最小代价 ▼ ④ 生成汇编指令总结问题答案DAG 是什么有向无环图描述单个基本块的计算逻辑节点操作add、mul、load、store边数据依赖生产者 → 消费者与树的区别DAG 允许共享节点树必须复制怎么从 IR 建 DAG遍历 IR创建节点和边共享 SSA 值为什么要拆成树树匹配算法只能处理树不能处理 DAG怎么拆在共享节点有多个父节点处拆分拆分后怎么用每棵树独立匹配指令模式按拓扑顺序生成汇编一句话Selection DAG 是把 IR 转成有向无环图节点是操作边是数据依赖。DAG 允许共享公共子表达式比树更紧凑。为了用树匹配做指令选择DAG 在共享节点处拆分成树的森林每棵树独立匹配最终生成汇编指令。