nudt-compiler-cpp/compiler_optimization_report.md

# 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 的方向。