新闻详情

新闻详情

首页 / 资讯中心 / 详情

树覆盖算法

发布时间:2026/11/17 17:00:04来源:尧图网络
树覆盖算法
概述树覆盖Tree Covering是编译器后端做指令选择的经典算法。它的核心思想是把 IR 表示成一棵表达式树然后用机器指令对应的“瓦片tile”去覆盖这棵树每覆盖一块就生成一条指令。IR 表达式树 机器指令模式瓦片 → 覆盖整棵树 → 生成汇编代码表达式树把 IR 表示成树叶子是变量/常量内部节点是运算。瓦片Tile每条机器指令对应树上的一个模式小树。想象一棵树要用小瓷砖拼满。每块瓷砖覆盖树的一部分所有瓷砖合起来覆盖整棵树。每块瓷砖 一条机器指令。覆盖用瓦片去匹配大树覆盖所有节点每块瓦片生成一条指例子a[i] b结构化 IR低级 AST假设a和b是栈上的本地变量i在寄存器ri中。a[i] b的 IR 树节点含义节点含义store把值写入内存mem内存地址add加法mul乘法fp栈帧指针a, b栈上变量的偏移量ri寄存器 i 的值4常量每个元素 4 字节树的读法从下往上fp a 数组a的起始地址ri × 4 第i个元素的字节偏移(fp a) (ri × 4)a[i]的地址mem[fp b] 变量b的值store mem[fpb] → mem[a[i]的地址] 把b写入a[i]覆盖方式一细粒度瓦片瓦片划分 瓦片1: fp a → load M[fpa], r1 瓦片2: 4 → addi 4, r2 瓦片3: ri × 4 → mul ri, r2 瓦片4: r1 r2 → add r2, r1 瓦片5: fp b → load M[fpb], r2 瓦片6: store → store r2, M[r1]生成的汇编load M[fp a], r1 ; 取出数组开头的地址放入 r1 addi 4, r2 ; 把 4 加载到 r2 mul ri, r2 ; ri × 4 i * 4数组元素的偏移量 add r2, r1 ; r2 r1 a[i] 的地址 load M[fp b], r2 ; 把 b 的值加载到 r2 store r2, M[r1] ; 把 r2 写入地址为 r1 的内存6 条指令。覆盖方式二粗粒度瓦片瓦片划分 瓦片1: fp a → load M[fpa], r1 瓦片2: 4 → addi 4, r2 瓦片3: ri × 4 → mul ri, r2 瓦片4: r1 r2 → add r2, r1 瓦片5: fp b → addi fpb, r2 ← 合并了 load 和 fpb 瓦片6: store → movm M[r2], M[r1] ← 用内存到内存拷贝生成的汇编load M[fp a], r1 ; 取出数组开头的地址放入 r1 addi 4, r2 ; 把 4 加载到 r2 mul ri, r2 ; ri × 4 i * 4 add r2, r1 ; r2 r1 a[i] 的地址 addi fpb, r2 ; 把 fpb 的值加载到 r2不访存 movm M[r2], M[r1] ; 直接从 M[r2] 拷贝到 M[r1]5 条指令少了 1 条。两种覆盖的差别瓦片覆盖方式一覆盖方式二瓦片5 (fpb)当成load M[fpb], r2当成addi fpb, r2(不访存)瓦片6 (store)store r2, M[r1](寄存器到内存)movm M[r2], M[r1](内存到内存)方式二更优因为它用一条 movm 替代了 load store 两条指令。Maximal Munch 算法思想从树根开始每次挑一个能覆盖最多节点的瓦片。1. 从根节点开始 2. 找一个能覆盖当前节点及其尽可能多子节点的瓦片 3. 用这个瓦片覆盖形成若干子树 4. 对每棵子树递归执行步骤 2-3 5. 直到所有节点被覆盖具体例子根节点 store 可选瓦片 A. store r, M[addr] 覆盖 store mem 子节点 B. movm M[src], M[dst] 覆盖 store 两个 mem 子节点 瓦片 B 覆盖更多节点 → 选 B选了 B 之后store和它下面的两个mem节点都被覆盖剩下两棵子树子树1: add(add(fp,a), mul(ri,4)) → 计算 a[i] 地址 子树2: fp b → 计算 b 地址对子树1 的根add可选瓦片 A. add r1, r2 只覆盖 add 节点 B. load M[fpa], r1 覆盖 add mem fp a 瓦片 B 覆盖更多 → 选 B对mul(ri, 4)可选瓦片 A. mul ri, r2 只覆盖 mul B. mul ri, r2 addi 4, r2 两步合并一般不合并 选 A最终生成方式二的 5 条指令。特点优点简单、快通常能生成较少指令。缺点贪心策略可能不是全局最优Optimal 算法思想从叶子往树根走深度优先用动态规划找代价最小的覆盖。1. 后序遍历树先叶子后根 2. 对每个节点计算所有可能瓦片覆盖的代价 3. 选代价最小的瓦片 4. 从叶子到根逐步确定最优覆盖与 Maximal Munch 的区别算法方向策略结果Maximal Munch根 → 叶贪心每次选覆盖最多的通常较优但不保证Optimal叶 → 根动态规划选代价最小的局部最优Optimal 的局限Optimal 是局部最优相邻两个瓦片不能合并成代价更低的瓦片。Optimum 是全局最优整棵树的代码总代价最低。Optimal 算法不保证全局最优但通常足够好。代码defselect(self,ir_function:ir.SubRoutine,frame):Select instructions of function into a frameassertisinstance(ir_function,ir.SubRoutine)self.logger.debug(Creating selection dag for %s,ir_function.name)# Create a object that carries global function info:function_infoFunctionInfo(frame)prepare_function_info(self.arch,function_info,ir_function)# Create selection dag (directed acyclic graph):sgraphself.dag_builder.build(ir_function,function_info,frame.debug_db)ifself.verbose:# Graph drawing takes considerable time# only do this in verbose mode.self.reporter.dump_sgraph(sgraph)# Split the selection graph into a forest of trees:forestself.dag_splitter.split_into_trees(sgraph,ir_function,function_info,frame.debug_db)self.reporter.dump_trees(forest)# Create a context that can emit instructions:contextInstructionContext(frame,self.arch)argslist(zip(function_info.arg_types,function_info.arg_vregs))forinstructioninself.arch.gen_function_enter(args):context.emit(instruction)# Generate proper instructions:self.munch_trees(context,forest)# Generate function tail:ifisinstance(ir_function,ir.Function):rv(ir_function.return_ty,function_info.rv_vreg)else:rvNoneforinstructioninself.arch.gen_function_exit(rv):context.emit(instruction)# TODO!!!# Emit code between blocks:# for instruction in self.arch.between_blocks(frame):# frame.emit(instruction)入口函数defselect(self,ir_function:ir.SubRoutine,frame):Select instructions of function into a frameassertisinstance(ir_function,ir.SubRoutine)self.logger.debug(Creating selection dag for %s,ir_function.name)ir_function是 IR 子程序frame是栈帧存放生成的指令。创建 FunctionInfo# Create a object that carries global function info:function_infoFunctionInfo(frame)prepare_function_info(self.arch,function_info,ir_function)收集函数的全局信息参数类型、返回类型、虚拟寄存器等。把 IR 构建成选择 DAGSelection DAG# Create selection dag (directed acyclic graph):sgraphself.dag_builder.build(ir_function,function_info,frame.debug_db)DAG 是树的推广允许节点共享比树更紧凑。verbose 模式下打印 DAG 图ifself.verbose:self.reporter.dump_sgraph(sgraph)把 DAG 拆成森林多棵树# Split the selection graph into a forest of trees:forestself.dag_splitter.split_into_trees(sgraph,ir_function,function_info,frame.debug_db)self.reporter.dump_trees(forest)创建指令发射上下文# Create a context that can emit instructions:contextInstructionContext(frame,self.arch)负责把生成的指令追加到frame生成函数入口代码如保存寄存器、设置栈帧argslist(zip(function_info.arg_types,function_info.arg_vregs))forinstructioninself.arch.gen_function_enter(args):context.emit(instruction)树覆盖Munch# Generate proper instructions:self.munch_trees(context,forest)作用核心步骤。对森林中的每棵树执行树覆盖Munch生成指令。生成函数出口代码如恢复寄存器、返回# Generate function tail:ifisinstance(ir_function,ir.Function):rv(ir_function.return_ty,function_info.rv_vreg)else:rvNoneforinstructioninself.arch.gen_function_exit(rv):context.emit(instruction)流程总结IR 函数 │ ▼ 构建 Selection DAGDAG 形式 │ ▼ 拆分成森林多棵树 │ ▼ 对每棵树执行树覆盖Munch │ ├─ 从根开始选最大瓦片 ├─ 递归处理子树 └─ 每块瓦片生成一条指令 │ ▼ 生成函数入口/出口代码 │ ▼ 输出汇编带虚拟寄存器总结概念含义树覆盖用机器指令对应的瓦片去覆盖 IR 表达式树瓦片一条机器指令对应的树模式Maximal Munch从根开始每次选覆盖最多的瓦片Optimal从叶子往根动态规划选代价最小的瓦片Selection DAG树的推广允许节点共享比树更紧凑森林把 DAG 拆成多棵树因为树覆盖只能处理树Munch对树执行覆盖生成指令的核心步骤一句话树覆盖指令选择就是把 IR 表示成树用机器指令对应的瓦片去覆盖每块瓦片生成一条指令。Maximal Munch 从根开始贪心选最大瓦片Optimal 从叶子往根用动态规划选代价最小的瓦片。a[i] b 的例子展示了两种覆盖方式方式二用 movm 合并了 load store少了一条指令。
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/17 7:04:08

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/17 5:42:44

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/16 19:23:38

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/17 6:55:04

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/17 5:57:47

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/16 17:28:18

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉