Selection DAG-北京尧图网络

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 在共享节点处拆分成树的森林每棵树独立匹配最终生成汇编指令。

Selection DAG

相关推荐

让我看看你是谁：Trae CN、TRAE-AI编程、TraeCode、TraeWork、TRAE SOLO CN、Trae APP

ABAP CDS 注解传播机制详解，从继承、覆盖到截断与稳定性控制

SAP ABAP CDS Metadata Extensions 深度解析，从 Annotation 解耦到 Clean Core 的元数据扩展机制

更多资讯

MySQL日期与时间戳转换全攻略：从类型原理到踩坑排查

MySQL日期时间转换全攻略：DATE与TIMESTAMP互转及避坑指南

从影刀RPA到MySQL：内置包、Xpath与数据入库实战解析

Superpowers：基于Web的多人协作游戏开发平台实战解析

Agent-Reach 实战：CLI AI Agent 从环境搭建到并发部署

OpenShell深度体验：跨平台终端统一与插件开发实战

今日更新

Multisim仿真NE555 PWM控制器：从搭电路到调占空比全流程

S32K312 AUTOSAR BSW开发实战：从配置踩坑到烧录交付

双目视觉三维人脸重建：从视差图到点云粗配准全流程解析

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？