36 KiB
NUDT-SysY 编译器优化报告
一、IR层优化
1. 常量折叠（Constant Folding）
实现文件: src/ir/ConstantReplace.cpp
原理: 当指令的所有操作数在编译期都是已知常量时,直接在编译期计算结果,用常量值替换整条指令。支持 BinaryInst(加减乘除余、浮点运算)、UnaryInst(类型转换、取反)、ICmpInst/FCmpInst(整/浮点比较)和 PhiInst(当所有入边值相同时消去Phi)。
流程: 获取指令的左右操作数 → 若 recursive=true 则递归向上追溯操作数中的指令直到展开为常量 → 检查是否均为 ConstantValue,否则返回 nullptr → 根据操作类型(mValueId)执行实际算术运算 → 返回对应的 ConstantInteger 或 ConstantFloating。常量结果通过常量池自动去重,使后续比较简化为指针比较。
2. 常量池化（Constant Pooling / Interning）
实现文件: src/ir/ConstantValue.cpp
原理: 相同类型+相同值的常量在全局只保留唯一实例,节省内存且使常量比较简化为指针比较。使用 std::unordered_map<ConstantValueKey, ConstantValue*> 作为全局常量池,键为 (Type*, variant<intmax_t, float>) 组合。i1 类型的 true/false 使用静态单例模式(getTrue()/getFalse()),所有布尔常量共享同一对象。
流程: 构造 key = (type, val) → 查找 mConstantPool,命中则直接返回 → 未命中时通过 arena 分配器创建新实例 → 插入池中并返回。常量通过 arena allocator 分配,生命周期与编译过程一致,无需单独释放。
3. 指令复制基础设施（Instruction Copy/Clone）
实现文件: src/ir/InstCopy.cpp
原理: 为每种指令实现 copy(getValue) 和 clone() 两种复制方法。copy 在复制过程中对每个操作数应用回调函数进行映射转换,用于 SSA 重命名、基本块克隆、循环展开等场景;clone 精确复制操作数不变,用于需要完全相同副本的场景。采用回调映射模式(std::function<Value*(Value*)> getValue),使 copy 方法完全通用,适用于各种重映射场景。
流程: 根据不同指令类型,对需要映射的操作数(如 StoreInst 的 value/ptr、CallInst 的参数、BranchInst 的目标块、GEP 的索引)逐一应用 getValue 回调;AllocaInst 无数据流操作数,直接新建;PhiInst 返回空 Phi,由调用方手动填充入边。
二、MIR层优化
4. 窥孔优化（Peephole Optimization）
实现文件: src/mir/Peephole.cpp
原理: 在一个滑动窗口内识别特定指令模式并用更高效的指令序列替换。由 genericPeepholeOpt() 统一驱动10种子优化,在 lowering.cpp 的 stage4(post-ISel)和 stage9(post-RA)各调用一次,循环直到不动点。
包含的子优化:
| 优化名称 | 原理 |
|---|---|
| EliminateStackLoads | 将 LoadRegFromStack 转换为 Copy,利用之前已加载过的虚拟寄存器替换。维护 stack→(reg,version) 映射,栈槽版本匹配时转换 |
| EliminateIndirectCopy | Copy的dst本质上是src的别名,将使用dst的地方直接替换为原始src,消除中间变量。维护 copy_dst→(src,version) 映射 |
| EliminateUnusedCopy | 删除 x=x 形式的自拷贝指令 |
| EliminateUnusedInst | BFS标记活跃指令(从有副作用/物理寄存器定义的指令开始传播),删除未被标记且无副作用的死代码 |
| ApplySSAPropagation | SSA形式下,每个虚拟寄存器只定义一次。若某寄存器通过 LoadConstant 加载常量且唯一定义,后续Copy该寄存器的操作直接用原始常量寄存器替换 |
| EliminateConstantLoads | 同一常量在多个块重复加载时只保留第一次,后续替换为Copy。记录入口块常量加载映射,在其他块中查找替换 |
| ConstantHoist | 将高频块中的常量加载提升到入口块,减少重复加载。计算CFG频率,跳过低于阈值的块,按频率降序逐个提升到entry |
| DeadInstElimination | 基于版本号,若某指令的定义被完全覆盖(相同指令+相同操作数版本号),则前一条指令的产物为死代码 |
| EliminateRedundantInst | 两条相同opcode且操作数版本号一致的指令,后者冗余(部分实现) |
| EliminateInvisibleInsts | post-RA专用,删除块内物理寄存器赋值但从未被使用的指令 |
5. CFG简化（Simplify CFG）
实现文件: src/mir/SimplifyCFG.cpp
原理: 循环迭代三种子优化直到CFG不再变化,消除控制流中的冗余结构,为代码布局优化创造更好的条件。在 lowering.cpp 的 stage11(代码布局优化之后)调用。
包含的子优化:
| 优化名称 | 原理 |
|---|---|
| removeGotoNext | 若块A末尾无条件跳转到物理相邻的下一块B,则删除该跳转(程序自然fall-through到B) |
| removeEmptyBlocks | 空块(无指令)是中间跳板,将其所有前驱的跳转目标重定向到空块的第一个非空后继。收集连续空块栈,遇非空块时全部重定向 |
| removeConsecutiveJump | 若块A仅含一条无条件跳转到块B,而块B又跳转到块C,则直接将A的跳转目标改为C。收集所有单跳转块,遍历分支指令重定向到最终目标 |
6. 乘法常量折叠（Multiplication with Constant Folding）
实现位置: src/mir/lowering.cpp 的 lower(BinaryInst)
原理: 在 IR→MIR 降低阶段,对乘法/加法/除法中的特殊常量进行折叠,避免生成不必要的指令。包括 x*0=0, x*1=x, x+0=x, 0/x=0, x/1=x。同时利用交换律规范化:若 c op x 且 lhs 是常量、rhs 不是,则交换操作数确保常量始终在右侧,统一后续处理模式。
流程: 在 lower(ir::BinaryInst*) 中检查右操作数是否为常量 → 若为0: mul 返回0, add/sub 返回左操作数, sdiv 返回0 → 若为1: mul 返回左操作数, sdiv 返回左操作数 → 同时检查交换律情况确保常量在右侧。
7. GEP 常量索引优化（GetElementPtr Constant Index Optimization）
实现位置: src/mir/lowering.cpp 的 lower_GetElementPtr
原理: GetElementPtr 指令中,常量索引在编译时直接计算偏移量,无需生成运行时计算指令;变量索引使用 Shl(移位)替代 Mul 4 来计算字节偏移,因为移位比乘法更快。对于结构体字段访问,利用 DataLayout 在编译期确定字段偏移。
流程: 遍历 GEP 的每个索引 → 若为常量,编译期计算 offset += index * elementSize → 若为变量,生成 Shl index, 2 (对 i32 类型)得到字节偏移 → 最终用 ADD 累加基址与偏移得到目标地址。
三、指令调度优化
8. 指令依赖图构建（Dependency Graph Construction）
实现文件: src/mir/Scheduler/Schedule.cpp 的 celloctInfo
原理: 遍历块中每条指令的每个操作数,构建 DAG(有向无环图)作为后续拓扑排序调度的基础。区分三种依赖类型:RAW(Read After Write)——当前指令Use寄存器依赖最近Def该寄存器的指令;WAR(Write After Read)——当前指令Def寄存器依赖所有最近Use该寄存器的指令;副作用指令——链式依赖所有前置副作用指令。InOrder/Call/Terminator 指令依赖之前所有指令。
流程: 遍历每条指令的每个操作数 → 对 Use 操作数,查找 lastDef[reg] 建立 RAW 依赖边 → 对 Def 操作数,对 lastTouch[reg] 中所有指令建立 WAR 依赖边 → 副作用指令与之前所有副作用指令建链 → InOrder/Call 指令与之前所有指令建依赖 → 更新 lastDef/lastTouch → 计算每条指令的入度 degrees。使用 renameMap 处理寄存器重命名。
9. 块内指令调度（Intra-Block Instruction Scheduling）
实现文件: src/mir/Scheduler/IntraBlockScheduler.cpp
原理: 针对 RISC-V SiFive U74 双发射有序流水线(8级:F1/F2→D1/D2→AG→M1/M2→WB)进行周期精确的指令调度模拟。采用 Top-Down List Scheduling 算法,每个周期模拟 issueWidth=2 个槽位的发射,通过 ScheduleClass 验证指令能否发射。就绪队列按动态优先级排序:newRank = baseRank + waitTime × waitPenalty,等待越久优先级越高以防止饥饿。
Pre-RA vs Post-RA 差异:
| 阶段 | rank初始化 | waitPenalty | 策略 |
|---|---|---|---|
| Pre-RA | instIdx -= 20(原始程序序) |
2(防饥饿) | 推动长依赖链指令优先 |
| Post-RA | BFS拓扑最长路径:rank[v]=max(rank[u])+1 |
0(不需要) | 严格按最长路径调度 |
ScheduleClass 模型:
| 类别 | 可用Pipeline | 延迟 | 说明 |
|---|---|---|---|
IntegerArithmetic |
A|B | 1(early)/3(late) | 早期AG阶段或晚期M2阶段 |
LoadStore |
A | 3 | 要求地址在AG阶段就绪 |
Branch |
B | - | 操作数延迟≤2可发射 |
Multi |
B | 3 | 乘法指令 |
DivRem |
B | 68 | 除法,占用div pipeline 65周期 |
FP(1/2/4/5) |
B | 可变 | 浮点运算,延迟由模板参数指定 |
FPDiv |
B | 36 | 浮点除法,占用fp div pipeline 33周期 |
10. 基本块布局优化（Block Layout Optimization / Pettis-Hansen）
实现文件: src/mir/Scheduler/BlockLayoutOpt.cpp
原理: 将程序中频繁执行的路径(热路径)上的基本块紧密排列在一起,减少指令缓存未命中和分支预测错误。使用 Pettis-Hansen 算法,通过带频率的CFG和贪心策略构建最优块序列。在 lowering.cpp 的 stage11 调用。
两阶段流程:
Stage 1 - Chain Composition(链合成): 初始化每个块自成一链(并查集 fa[i]=i) → 计算边权重 weight= freq[src]×prob → 按权重降序排序所有边 → 遍历边贪心合并链,合并条件:src≠dst(非自环)、dst未被合并、src不是dst的祖先(防环)、src是其所在链尾部 → 合并操作:sonsSrc.splice 接上 sonsDst,fa[dst]=faSrc。
Stage 2 - Code Layout(代码布局): 从入口块所在链开始 → 用优先队列(min-heap on chain priority)管理待处理链 → 依次处理链中的块输出到序列 → 对已输出块的后续块,若其所在链未加入队列则加入 → 最终得到最优块排列。
Stage 3 - 应用变更: 按新序列重排 mfunc->blocks() → 修复 fall-through:对条件分支,若 fall-through 到的不是条件分支目标,插入无条件跳转 J。
四、寄存器分配优化
11. 图着色寄存器分配（Graph Coloring Register Allocation）
实现文件: src/mir/RegisterAllocator/GraphColoringRegisterAllocation.cpp
原理: 经典的 Briggs 图着色寄存器分配算法,采用简化-选择-溢出迭代框架。将寄存器分配建模为图着色问题:干涉图节点=虚拟寄存器,边=干涉关系(两寄存器不能分配同一物理寄存器),K=可用物理寄存器数。度数<K的节点可安全着色,否则需要spill到栈。
流程: calcLiveIntervals() 计算活跃区间 → collectVirtualRegs() 收集需分配的虚拟寄存器 → buildGraph() 构建干涉图 → computeRegWeight() 计算权重:Weight = Σ(区间长度×块频率) + 100×copyHint数 - 1(常数) → assignRegisters() 迭代:简化(选度数<K节点压栈)→选择(逆序弹栈着色)→溢出(无度数<K节点时选代价最低的spill)→若有spill则 spillRegisters() 后重新迭代。权重低的节点优先spill。
关键优化策略:
- Copy-free偏好分配:
calcCopyFreeProposal优先分配与虚拟寄存器有copy关系的物理寄存器,消除冗余copy - Rematerialization: 常数虚拟寄存器spill时重新插入
li指令而非load/store - Call干涉处理: 利用IPRA信息,仅与实际使用的被调用者寄存器建边
- fixHazard模式: Post-RA调度+无硬件寄存器重命名时,启用精细代价评估避免use-after-def冲突
12. 干涉图构建（Interference Graph Construction）
实现文件: src/mir/RegisterAllocator/InterferenceGraph.cpp
原理: 两个寄存器在同一时刻都活跃则它们干涉(不能分配同一物理寄存器)。干涉图使用邻接表 mAdj<RegNum→unordered_set<RegNum>> 和度数表 mDegree<RegNum→uint32_t> 表示。
流程: 逐块扫描指令,维护 liveVRegs 集合 → Use/Def时与活跃虚拟寄存器建边 → Call指令与被调用者使用的寄存器建边 → 物理寄存器(under-renamed/locked)与虚拟寄存器建边 → 虚拟寄存器之间:活跃区间相交则建边(intervalU.intersectWith(intervalV))。prepare_for_assign 将所有度数<K节点按权重排序入优先队列;pick_to_assign 取队列顶节点,移除并更新邻居度数;pick_to_spill 选择度数最大且权重最小(或度数≥K中权重最小)的节点spill。
13. 块内快速寄存器分配（Fast / Intra-Block Register Allocator）
实现文件: src/mir/RegisterAllocator/FastAllocator.cpp
原理: 不构建全局干涉图,仅在每个基本块内独立分配,时间复杂度远低于图着色。跨块存活的虚拟寄存器直接分配栈槽,在块内使用时临时load/store。使用LRU队列管理物理寄存器,驱逐时使用最久未用的寄存器。
流程: calcLiveIntervals() → collectUseDefInfo() 收集每个虚拟寄存器在哪些块def/use → collectStackMap() 为跨块存活虚拟寄存器分配栈槽 → 对每个块 allocateInBlock():逐条指令扫描 → use操作数若已在寄存器则保护,否则从栈load → def操作数分配空闲寄存器或驱逐现有寄存器 → 分支前将所有dirty跨块虚拟寄存器spill回栈 → Call前保存caller-saved寄存器。getFreeReg 优先分配ISA hint→找空闲→从LRU队列驱逐。
14. 混合寄存器分配器（Mixed Register Allocator）
实现文件: src/mir/RegisterAllocator/MixedRegisterAllocator.cpp
原理: 根据函数规模自动选择最优分配策略,在编译时间和代码质量之间取得平衡。图着色分配质量高但复杂度O(n²)级,适合小型函数;快速分配器复杂度低但可能产生更多load/store,适合大型函数。阈值3000是经验值。
流程: collectVregNumber() 统计函数虚拟寄存器数量 → 若 vregNum > 3000 调用 intraBlockAllocate(快速分配) → 若 vregNum ≤ 3000 调用 graphColoringAllocate(图着色分配)。
15. 寄存器协同/合并（Register Coalescing）
实现文件: src/mir/RegisterCoalescing.cpp
原理: 消除冗余的copy指令(如 mov x1,x2 当x1和x2可分配同一寄存器时)。不使用经典的George-Appel保守协同算法,而是通过一套窥孔优化达到等价效果。循环调用 genericPeepholeOpt() 直到收敛。
流程: RegisterCoalescing 入口 → 循环调用 genericPeepholeOpt() 包含 EliminateStackLoads(栈load转Copy)、EliminateIndirectCopy(用copy src直接替换dst使用)、EliminateUnusedCopy(删除x=x自拷贝)、ApplySSAPropagation(SSA形式传播常数消除中间copy)、EliminateConstantLoads(消除重复常量加载)、ConstantHoist(高频块常量提升到entry)、DeadInstElimination(基于版本号删除重复定义)、EliminateInvisibleInsts(post-RA删除不可见物理寄存器赋值) → 直到无修改则退出循环。
16. 过程间寄存器使用分析（Inter-Procedural Register Allocation Usage, IPRA）
实现文件: src/mir/RegisterAllocator/IPRAUsageInfo.cpp
原理: 传统上调用点保守地假设所有caller-saved寄存器都可能被破坏。IPRA通过跨函数分析,精确知道每个被调用函数实际使用了哪些寄存器,在图着色分配的 buildGraph 中仅与实际使用的寄存器建干涉边,减少不必要的干涉边,使图着色更容易成功,减少spill。
流程: IPRAUsageCache::add(func):扫描函数所有指令 → 收集使用的Caller-Saved物理寄存器加入IPRAInfo → 遇Call指令:若非递归调用,递归查询被调用者的IPRAInfo → 将被调用者使用的寄存器传播到当前函数 → 缓存结果 mCache.emplace(funcName, info)。非递归保护:递归调用时不查询自身,避免死循环。在图着色分配buildGraph中:有IPRA信息→仅与实际使用寄存器建边;无IPRA信息→与所有caller-saved寄存器建边(保守策略)。
五、循环优化
17. 循环结构分析（Loop Analysis）
实现文件: src/pass/analysis/loop.cpp
原理: 利用支配树信息识别循环结构。如果循环header支配其前驱(latch),则该边为回边,构成循环。从latch开始逆向BFS收集所有循环块直到header,同时识别嵌套循环关系(子循环header在当前循环内则为子循环)和循环出口(循环内块的后继不在循环内)。
流程: 获取支配树和循环信息 → 遍历所有BasicBlock,检查每个前驱:若 dom(bb, bbPre) 则为回边 → 调用 addLoopBlocks:创建/查找Loop对象,将latch加入latchs集合,栈式DFS从latch逆向遍历,将块加入loop.blocks并设置looplevel → 对每个循环调用 loopGetExits:确保header在blocks中,遍历blocks识别嵌套循环父子关系,检查next_blocks收集出口块。
18. 归纳变量分析（Induction Variable Analysis）
实现文件: src/pass/analysis/indvar.cpp
原理: 识别标准循环模式的归纳变量 for(i=begin; i<end; i+=step),对应IR模式:header中Phi节点从preheader取初始值、从latch取递增值;循环条件为icmp比较Phi与循环不变量;latch中为加法/减法/乘法递推。支持 ADD/FADD、SUB/FSUB、MUL/FMUL 三种递推模式。
流程: 遍历每个循环 → 前提检查:必须LoopSimplifyForm、header终结指令为条件分支、仅一个出口 → 提取循环条件(icmp):条件必须是icmp且一个操作数是header中的Phi → 识别关键Phi(keyPhiInst):icmp的LHS/RHS是header中Phi → 提取边界变量mEndVar:icmp另一操作数(循环不变量) → 提取初始值mBeginVar:keyPhiInst从preheader获取的值 → 提取步进操作iterInst:keyPhiInst从latch获取的值(必须ADD/SUB/MUL) → 提取步长mstepVar:二元指令另一操作数(循环不变量) → 创建IndVar对象。不变量检测:isSimplyLoopInvariant——指令所在块支配header则为不变量;常量是不变量;BinaryInst两操作数都不在循环内则为不变量;CallInst须为pure函数且参数为不变量。
19. 运行时循环并行调度（Adaptive Thread Selection Parallel For）
实现文件: src/runtime/LoopParallel/LoopParallel.cpp、src/runtime/LoopParallel/cmmcLoopParallel.cpp
原理: 三阶段自适应线程选择的并行运行时。阶段1(冷启动<100次):默认2线程;阶段2(采样100-160次):轮询采样1T/2/4T,记录累计时间;阶段3(稳定≥160次):选择历史最优线程配置。通过 clone() 系统调用预创建Worker线程池(4个线程),每线程绑定特定CPU核心,使用Linux futex实现轻量级用户态同步,比mutex性能更高。
流程: parallelFor(beg, end, func) → 范围<16则直接串行执行 → selectNumberOfThreads() 查询/采样缓存决定线程数 → spawnAndJoin(1<<threads):计算每个子任务范围(对齐到4),通过Futex唤醒Worker线程,Futex等待所有Worker完成。缓存结构:16槽位LFU淘汰策略,ParallelForEntry 包含func指针+size+hitCount+times[3]+bestThreads。线程创建标志:CLONE_VM|CLONE_FS|CLONE_FILES|CLONE_SIGHAND|CLONE_THREAD|CLONE_SYSVSEM(内核线程,共享地址空间)。
20. 简化多线程循环库（Loop Library）
实现文件: src/runtime/LoopLib/LoopLib.cpp
原理: 使用标准POSIX pthread API的简单并行循环库。每次创建新线程(无线程池),使用 hardware_concurrency() 自动匹配硬件线程数,固定使用全部可用线程,无自适应调度。相比cmmc版本实现简单但性能较低(无线程池、无CPU亲和性、无futex同步)。
流程: parallelFor(beg, end, func) → numThreads=hardware_concurrency() → chunkSize=(range+numThreads-1)/numThreads(向上取整) → 循环创建pthread:chunkBeg=beg+i*chunkSize,pthread_create(threadFunc, &threadData) → pthread_join 等待所有线程完成。
六、分析Pass(支撑优化的基础分析)
21. 控制流图分析（CFG Analysis）
实现文件: IR层:src/pass/analysis/CFGAnalysis.cpp;MIR层:src/mir/CFGAnalysis.cpp
IR层原理: 遍历所有基本块的终结指令(分支指令),建立显式CFG边。条件分支建立到iftrue和iffalse的两条边;无条件分支建立到dest的一条边。通过 bb->block_link(src,dst) 建立双向连接(pre_blocks和next_blocks集合)。
MIR层原理: 除构建CFG外,还进行基本块执行频率分析。构建线性方程组 (I-P^T)·f=1(P为转移概率矩阵),使用LUP分解求解(选主元确保数值稳定性,前代+回代求解,处理奇异矩阵)。将基本块执行频率建模为马尔可夫链稳态分布,提供类似PGO的静态估算能力。频率信息支撑常量提升(ConstantHoist)、寄存器分配(高频块变量优先分配)、代码布局(热路径连续放置)等优化。
22. 支配树分析（Dominator Tree Analysis）
实现文件: src/pass/analysis/dom.cpp
原理: 使用 Lengauer-Tarjan 算法计算立即支配者,理论复杂度 O(E·α(E,V)) 接近线性。核心创新:半支配者(sdom)——在DFS树中能通过非树边到达w的最浅祖先;路径压缩+按大小合并的eval/link操作维护等价类。四步串联:PreProcDom(删除不可达块)→IDomGen(Lengauer-Tarjan计算idom)→DomFrontierGen(计算支配边界)→DomInfoCheck(调试)。
流程: DFS遍历分配序号并建DFS树 → 逆向按DFS序号处理:对w的每个前驱用eval找到半支配者候选,将w放入bucket,link到parent,处理bucket中元素计算idom → 修正idom:若 idom[w]≠vertex[semi[w]] 则 idom[w]=idom[idom[w]] → 计算支配边界:对多前驱块,沿idom上溯路径上每个块的支配边界包含该块。支撑SSA构造(Phi节点放置)、死码消除、代码移动、循环识别。
23. 后支配树分析（Post-Dominator Tree Analysis）
实现文件: src/pass/analysis/pdom.cpp
原理: 在反向CFG上运行Lengauer-Tarjan算法。后支配定义:块B后支配块A ⇔ 从A到exit的所有路径都经过B。与支配树完全对称,关键差异:起点为exit而非entry;DFS方向为pre_blocks(前驱)而非next_blocks(后继);计算sdom查看next_blocks而非pre_blocks;预处理删除无后继的不可达块。支撑控制等价判断(两块互相支配且互相后支配可合并)、代码下沉、异常处理优化、循环出口确定。
24. 副作用分析（Side Effect Analysis）
实现文件: src/pass/analysis/SideEffectAnalysis.cpp
原理: 基于CallGraph的数据流不动点迭代分析。第一阶段逐函数扫描直接副作用:LoadInst追踪基址(GlobalVariable/Argument),StoreInst记录写入,CallInst特殊处理库函数(putarray/getarray等)。基址追踪 getBaseAddr() 沿GEP→Phi→Unary(inttoptr)链回溯到Alloca/GlobalVariable/Argument。第二阶段迭代传播:合并callee的全局变量读写到caller,callee是库函数或有潜在副作用则caller也标记,指针参数传播(callee读/写指针参数且caller传入全局变量则caller也读/写该全局变量)。hasSideEffect(func) 返回true条件:是库函数/调用库函数/写入全局变量/有潜在副作用/有指针参数被写入。支撑函数内联、死函数消除、循环外提、指令重排、并行化判断。
七、降低与代码生成优化
25. IR到MIR降低优化（Lowering Optimizations）
实现文件: src/mir/lowering.cpp
原理: 完整的13阶段编译管线,在降低过程中穿插多种优化。Stage1创建MIR Function → Stage2指令选择(通用MIR→目标特定MIR) → Stage3寄存器合并 → Stage4窥孔优化循环 → Stage5退出SSA → Stage6 Pre-RA调度(最小化寄存器使用) → Stage7寄存器分配 → Stage8栈空间分配 → Stage9再次窥孔优化 → Stage10 Post-RA调度(最小化执行周期) → Stage11代码布局优化 → Stage12 CFG简化 → Stage13后合法化。
关键优化:
- BitCast消除: 强类型后端无需生成实际指令,仅更新类型映射
- Phi值冲突处理:
emitJump()构建有向图→计算SCC→拓扑排序得到安全赋值顺序→对冲突值先emitCopy到临时虚拟寄存器→按拓扑序执行最终Copy - 全局变量处理: 已初始化→
.data段(MIRDataStorage),未初始化→.bss段(MIRZeroStorage),float通过memcpy转为uint32_t存储
八、2026test 样例的性能收益分类（预计）
说明: 本节基于 2026test 样例名与代表性源码结构做静态归类,目标是回答“针对每一个优化,哪些样例预计会有较好性能提升”。这不是实测结论,而是结构匹配上的预期收益。其中 performance/ 目录的判断置信度最高,functional/ 与 h_functional/ 主要用于补充“会触发该优化”的代表样例。
1. 样例簇定义
| 样例簇 | 代表样例 | 结构特征 |
|---|---|---|
| A. 常量/表达式折叠类 | functional/11_add2,12_addc,13_sub2,14_subc,15_mul,16_mulc,17_div,18_divc,19_mod,20_rem,35_op_priority1~41_unary_op2,46_hex_defn,47_hex_oct_add,64_calculator,69_expr_eval |
常量传播、常量算术、运算优先级、单目/比较表达式较多 |
| B. 矩阵/数组地址计算类 | functional/83_long_array,84_long_array2,94_nested_loops,96_matrix_add,97_matrix_sub,98_matrix_mul,99_matrix_tran; h_functional/07_arr_init_nd,22_matrix_multiply,30_many_dimensions,38_light2d; performance/01_mm1~01_mm3,matmul1~matmul3,many_mat_cal-1~many_mat_cal-3,transpose0~transpose2,conv2d-1~conv2d-3,fft0~fft2,shuffle0~shuffle2 |
多维数组、密集访存、GEP/索引计算、深层循环 |
| C. 分支/图搜索/控制流类 | functional/62_percolation,65_color,70_dijkstra,71_full_conn,72_hanoi,74_kmp,75_max_flow,76_n_queens; h_functional/09_BFS,10_DFS,11_BST,12_DSU,13_LCA,14_dp,15_graph_coloring,16_k_smallest,17_maximal_clique,18_prim,19_search,20_sort,21_union_find,33_multi_branch,34_multi_loop,35_math,36_rotate; performance/03_sort1~03_sort3,knapsack_naive-1~knapsack_naive-3,huffman-01~huffman-03,crc1~crc3,crypto-1~crypto-3,h-1-01~h-10-03 |
分支密集、循环内条件判断多、CFG复杂、热路径明显 |
| D. 调度/流水线敏感类 | performance/optimization_scheduling1~optimization_scheduling3,fft0~fft2,crypto-1~crypto-3,crc1~crc3,conv2d-1~conv2d-3,matmul1~matmul3,03_sort1~03_sort3 |
算术链长、可并行指令与相关指令混合、对 issue 顺序敏感 |
| E. 高寄存器压力/多参数类 | functional/82_long_func,85_long_code,86_long_code2,87_many_params,88_many_params2,90_many_locals,91_many_locals2,92_register_alloc,93_nested_calls,95_float; h_functional/29_long_line,31_many_indirections,32_many_params3,39_fp_params; performance/crypto-1~crypto-3,huffman-01~huffman-03 |
活跃变量多、参数多、临时值多、调用约定压力大 |
| F. 调用密集/过程间类 | functional/66_exgcd,72_hanoi,73_int_io,74_kmp,78_side_effect,93_nested_calls; h_functional/11_BST,13_LCA,21_union_find,35_math,39_fp_params; performance/huffman-01~huffman-03,crypto-1~crypto-3 |
函数调用频繁、递归/嵌套调用明显、适合观察 IPRA 与副作用分析收益 |
| G. 标准循环/归纳变量类 | functional/25_while_if,26_while_test1,27_while_test2,28_while_test3,31_while_if_test1,32_while_if_test2,33_while_if_test3,34_arr_expr_len,94_nested_loops; h_functional/34_multi_loop,36_rotate,37_dct,38_light2d; performance 目录中的大多数 kernel |
明确的 while(i=i+1) / for 风格递推、边界清晰,容易识别循环结构与归纳变量 |
| H. 并行循环候选类 | performance/matmul1~matmul3,conv2d-1~conv2d-3,fft0~fft2,transpose0~transpose2,many_mat_cal-1~many_mat_cal-3,03_sort1~03_sort3 |
计算量大且外层循环可切分,理论上最适合并行运行时 |
补充说明: 我在 2026test 下检索了 parallelFor、cmmc、pthread、clone( 等关键词,当前样例没有直接调用并行循环运行时。因此第 19、20 项优化在本测试集里更适合作为“若后续接入并行库,最可能受益的候选样例”来看待。
2. 按优化项分类
| 优化项 | 预计收益样例 | 预计收益级别 | 判断依据 |
|---|---|---|---|
| 1. 常量折叠 | A; 补充: B 中的 98_matrix_mul,22_matrix_multiply,conv2d-* 的部分常量尺寸/系数表达式 |
高 | 常量表达式越多,越能在 IR 层提前消掉算术与比较 |
| 2. 常量池化 | A, E 中的 82_long_func,85_long_code,86_long_code2,39_fp_params |
中 | 主要减少常量对象与比较成本,对运行时是间接收益,对大函数/常量密集代码更明显 |
| 3. 指令复制基础设施 | B,C,G 中的大循环/复杂 CFG 样例 |
间接 | 该项本身更像后续变换的基础设施,直接运行时收益弱,但对复杂函数变换能力有支撑 |
| 4. 窥孔优化 | D, E; 代表: optimization_scheduling*,92_register_alloc,39_fp_params,crypto-*,huffman-* |
高 | 能直接减少冗余 copy、重复常量加载、死代码与栈回读,在寄存器压力大或 lowering 后冗余较多的程序上收益明显 |
| 5. CFG简化 | C, F, G; 代表: 70_dijkstra,75_max_flow,76_n_queens,09_BFS,10_DFS,03_sort*,huffman-* |
中到高 | 分支多、空块/跳板块多的程序更容易受益,减少无效跳转并改善后续布局 |
| 6. 乘法常量折叠 | A; 补充: 03_sort* 中的 base=16, conv2d-* 中的 KSIZE=5, 98_matrix_mul,22_matrix_multiply |
中 | 对 x*0,x*1,x/1,x+0 这类模式收益直接,常量步长/常量维度代码容易命中 |
| 7. GEP 常量索引优化 | B, E; 代表: 96_matrix_add,98_matrix_mul,99_matrix_tran,22_matrix_multiply,38_light2d,39_fp_params,conv2d-*,transpose* |
高 | 多维数组与定长数组访问非常多时,常量索引和移位替代乘法能显著减少地址计算 |
| 8. 指令依赖图构建 | D; 代表: optimization_scheduling*,fft*,crypto-*,crc*,matmul* |
间接 | 这是调度的前置分析,本身不直接提速,但对后续块内调度质量决定性 |
| 9. 块内指令调度 | D, E 中的 95_float,39_fp_params |
高 | 对长算术链、乘除/浮点混合、存在 ILP 的热循环最有效,正是 optimization_scheduling* 这类样例的主战场 |
| 10. 基本块布局优化 | C, F; 代表: 70_dijkstra,75_max_flow,76_n_queens,09_BFS,10_DFS,11_BST,13_LCA,huffman-*,knapsack_naive-* |
中到高 | 热路径集中、分支预测压力大的程序更受益,可减少无谓跳转与 I-cache 扰动 |
| 11. 图着色寄存器分配 | E, D; 代表: 92_register_alloc,87_many_params,90_many_locals,39_fp_params,crypto-*,huffman-* |
高 | 活跃值多、调用约束强的程序最容易因更少 spill/reload 而提升 |
| 12. 干涉图构建 | E, D | 间接 | 这是图着色分配的支撑分析,收益通过第 11 项体现,高寄存器压力样例感知更强 |
| 13. 块内快速寄存器分配 | E 中的大函数; 代表: 85_long_code,86_long_code2,92_register_alloc,39_fp_params,crypto-* |
中 | 当函数很大、虚拟寄存器很多时,它更偏向缩短编译时间并避免全局分配过重,运行时收益取决于是否触发混合分配器切换 |
| 14. 混合寄存器分配器 | E, performance 中的大 benchmark; 代表: crypto-*,huffman-*,matmul*,conv2d-*,fft* |
中到高 | 能为小函数选高质量图着色,为大函数选快速分配,整体平衡编译时间与代码质量 |
| 15. 寄存器协同/合并 | E, D; 代表: 92_register_alloc,93_nested_calls,39_fp_params,optimization_scheduling*,crypto-* |
高 | copy 密集、SSA 退出后临时寄存器多的程序上通常有直接收益 |
| 16. IPRA | F, E; 代表: 93_nested_calls,72_hanoi,11_BST,13_LCA,21_union_find,39_fp_params,huffman-* |
中到高 | 调用点越多、callee 实际改写寄存器越少,IPRA 越能减少不必要干涉和保存恢复 |
| 17. 循环结构分析 | G, B, D | 间接 | 主要是循环优化和并行化的前置分析,在标准循环密集程序中最有价值 |
| 18. 归纳变量分析 | G, B, D; 代表: 94_nested_loops,36_rotate,37_dct,conv2d-*,matmul*,03_sort* |
中 | 典型递增索引与边界判断越清晰,越容易识别归纳变量并支撑后续优化 |
| 19. 运行时循环并行调度 | 当前 2026test 无直接命中样例; 若后续接入运行时,优先看 H |
暂无直接收益 | 测试集中没有直接调用并行运行时 API 的样例,因此不会自动体现该优化收益 |
| 20. 简化多线程循环库 | 当前 2026test 无直接命中样例; 若后续接入运行时,优先看 H |
暂无直接收益 | 同上,这些 benchmark 从结构上适合并行,但当前样例并未显式使用该库 |
| 21. CFG分析 | C, G, F | 间接 | 该分析为 CFG 简化、块布局、频率估计提供基础,对复杂控制流样例支撑最大 |
| 22. 支配树分析 | C, G, F | 间接 | 主要支撑 SSA、循环识别、代码移动与死码删除,复杂分支和循环程序最依赖它 |
| 23. 后支配树分析 | C, F; 代表: 76_n_queens,75_max_flow,11_BST,13_LCA,huffman-* |
间接 | 对复杂退出路径、控制等价与循环出口判断更重要,收益通过后续变换体现 |
| 24. 副作用分析 | F; 代表: 78_side_effect,93_nested_calls,11_BST,13_LCA,21_union_find,35_math,huffman-*,crypto-* |
中 | 调用密集且可证明纯函数/只读行为的代码,更容易触发内联、移动与删冗余调用 |
| 25. IR到MIR降低优化 | B, C, D, E; 代表: conv2d-*,matmul*,03_sort*,optimization_scheduling*,92_register_alloc,39_fp_params |
高 | 这是多个后端优化的总入口,几乎所有性能 benchmark 都会受益,尤其是数组、调度、寄存器压力大的程序 |
3. 如果只关注“最可能拉开性能差距”的样例
| 优化主题 | 最值得优先观察的样例 |
|---|---|
| 常量折叠/表达式化简 | functional/64_calculator,69_expr_eval,46_hex_defn,47_hex_oct_add,03_sort1~03_sort3 |
| 数组地址/GEP优化 | functional/98_matrix_mul,99_matrix_tran,h_functional/22_matrix_multiply,38_light2d,performance/conv2d-1~conv2d-3,transpose0~transpose2,matmul1~matmul3 |
| 指令调度 | performance/optimization_scheduling1~3,fft0~2,crypto-1~3,crc1~3,conv2d-1~3 |
| 寄存器分配/协同/IPRA | functional/92_register_alloc,87_many_params,90_many_locals,93_nested_calls,h_functional/39_fp_params,performance/crypto-1~3,huffman-01~03 |
| CFG/块布局 | functional/70_dijkstra,75_max_flow,76_n_queens,h_functional/09_BFS,10_DFS,15_graph_coloring,performance/knapsack_naive-1~3,huffman-01~03 |
| 循环识别/归纳变量 | functional/94_nested_loops,h_functional/34_multi_loop,36_rotate,37_dct,performance/03_sort1~3,matmul1~3,conv2d-1~3 |
4. 总结
- 若要验证 后端调度能力,优先跑
performance/optimization_scheduling1~3,fft*,crypto-*,crc*。 - 若要验证 寄存器分配与寄存器协同,优先跑
functional/92_register_alloc,87_many_params,90_many_locals,93_nested_calls,h_functional/39_fp_params。 - 若要验证 GEP/数组地址计算与循环优化,优先跑
functional/98_matrix_mul,99_matrix_tran,h_functional/22_matrix_multiply,performance/matmul*,conv2d-*,transpose*。 - 若要验证 CFG 简化与块布局,优先跑
functional/70_dijkstra,75_max_flow,76_n_queens,h_functional/09_BFS,10_DFS,performance/huffman-*,knapsack_naive-*。 - 第 19、20 项并行运行时优化在当前
2026test中没有直接对应调用样例,更适合作为后续扩展 benchmark 的方向。