mysysy/Pass_ID_List.md

记录中端遍的开发进度

名称	优化级别	开发进度
CFG优化	函数级	已完成
DCE	函数级	待正确性测试
Mem2Reg	函数级	待正确性测试
Reg2Mem	函数级	待正确性测试

部分优化遍的说明

Mem2Reg

Mem2Reg 遍的主要目标是将那些不必要的、只用于局部标量变量的内存分配 (alloca 指令) 消除，并将这些变量的值转换为 SSA 形式。这有助于减少内存访问，提高代码效率，并为后续的优化创造更好的条件。

通过Mem2Reg理解删除指令时对use关系的维护：

在 Mem2Reg 优化遍中，当 load 和 store 指令被删除时，其 use 关系（即它们作为操作数与其他 Value 对象之间的连接）的正确消除是一个关键问题，尤其涉及到 AllocaInst。

结合您提供的 Mem2RegContext::renameVariables 代码和我们之前讨论的 usedelete 逻辑，下面是 use 关系如何被正确消除的详细过程：

问题回顾：Use 关系的双向性

在您的 IR 设计中，Use 对象扮演着连接 User（使用者，如 LoadInst）和 Value（被使用者，如 AllocaInst）的双向角色：

• 一个 User 持有对其操作数 Value 的 Use 对象（通过 User::operands 列表）。
• 一个 Value 持有所有使用它的 User 的 Use 对象（通过 Value::uses 列表）。

原始问题是：当一个 LoadInst 或 StoreInst 被删除时，如果不对其作为操作数与 AllocaInst 之间的 Use 关系进行明确清理，AllocaInst 的 uses 列表中就会留下指向已删除 LoadInst / StoreInst 的 Use 对象，导致内部的 User* 指针悬空，在后续访问时引发 segmentation fault。

Mem2Reg 中 load/store 指令的删除行为

在 Mem2RegContext::renameVariables 函数中，load 和 store 指令被处理时，其行为如下：

1. 处理 LoadInst： 当找到一个指向可提升 AllocaInst 的 LoadInst 时，其用途会被 replaceAllUsesWith(allocaToValueStackMap[alloca].top()) 替换。这意味着任何原本使用 LoadInst 本身计算结果的指令，现在都直接使用 SSA 值栈顶部的 Value。 重点： 这一步处理的是 LoadInst 作为被使用的值 (Value) 时，其 uses 列表的清理。即，将 LoadInst 的所有使用者重定向到新的 SSA 值，并把这些 Use 对象从 LoadInst 的 uses 列表中移除。

2. 处理 StoreInst： 当找到一个指向可提升 AllocaInst 的 StoreInst 时，StoreInst 存储的值会被压入值栈。StoreInst 本身并不产生可被其他指令直接使用的值（其类型是 void），所以它没有 uses 列表需要替换。 重点： StoreInst 的主要作用是更新内存状态，在 SSA 形式下，它被移除后需要清理它作为使用者 (User) 时的操作数关系。

在这两种情况下，一旦 load 或 store 指令的 SSA 转换完成，它们都会通过 instIter = SysYIROptUtils::usedelete(instIter) 被显式删除。

SysYIROptUtils::usedelete 如何正确消除 Use 关系

关键在于对 SysYIROptUtils::usedelete 函数的修改，使其在删除指令时，同时处理该指令作为 User 和 Value 的两种 Use 关系：

1. 清理指令作为 Value 时的 uses 列表 (由 replaceAllUsesWith 完成)： 在 usedelete 函数中，inst->replaceAllUsesWith(UndefinedValue::get(inst->getType())) 的调用至关重要。这确保了：

   • 如果被删除的 Instruction（例如 LoadInst）产生了结果值并被其他指令使用，所有这些使用者都会被重定向到 UndefinedValue（或者 Mem2Reg 中具体的 SSA 值）。
   • 这个过程会遍历 LoadInst 的 uses 列表，并将这些 Use 对象从 LoadInst 的 uses 列表中移除。这意味着 LoadInst 自己不再被任何其他指令使用。

2. 清理指令作为 User 时其操作数的 uses 列表 (由 RemoveUserOperandUses 完成)： 这是您提出的、并已集成到 usedelete 中的关键改进点。对于一个被删除的 Instruction（它同时也是 User），我们需要清理它自己使用的操作数所维护的 use 关系。

   • 例如，LoadInst %op1 使用了 %op1（一个 AllocaInst）。当 LoadInst 被删除时，AllocaInst 的 uses 列表中有一个 Use 对象指向这个 LoadInst。
   • RemoveUserOperandUses 函数会遍历被删除 User（即 LoadInst 或 StoreInst）的 operands 列表。
   • 对于 operands 列表中的每个 std::shared_ptr<Use> use_ptr，它会获取 Use 对象内部指向的 Value（例如 AllocaInst*），然后调用 value->removeUse(use_ptr)。
   • 这个 removeUse 调用会负责将 use_ptr 从 AllocaInst 的 uses 列表中删除。

总结

通过在 SysYIROptUtils::usedelete 中同时执行这两个步骤：

• replaceAllUsesWith：处理被删除指令作为结果被使用时的 use 关系。
• RemoveUserOperandUses：处理被删除指令作为使用者（User）时，其操作数的 use 关系。

这就确保了当 Mem2Reg 遍历并删除 load 和 store 指令时，无论是它们作为 Value 的使用者，还是它们作为 User 的操作数，所有相关的 Use 对象都能被正确地从 Value 的 uses 列表中移除，从而避免了悬空指针和后续的 segmentation fault。

最后，当所有指向某个 AllocaInst 的 load 和 store 指令都被移除后，AllocaInst 的 uses 列表将变得干净（只包含 Phi 指令，如果它们在 SSA 转换中需要保留 Alloca 作为操作数），这时在 Mem2RegContext::cleanup() 阶段，SysYIROptUtils::usedelete(alloca) 就可以安全地删除 AllocaInst 本身了。

Reg2Mem

我们的Reg2Mem 遍的主要目标是作为 Mem2Reg 的一种逆操作，但更具体是解决后端无法识别 PhiInst 指令的问题。主要的速录是将函数参数和 PhiInst 指令的结果从 SSA 形式转换回内存形式，通过插入 alloca、load 和 store 指令来实现。其他非 Phi 的指令结果将保持 SSA 形式。

SCCP

SCCP（稀疏条件常量传播）是一种编译器优化技术，它结合了常量传播和死代码消除。其核心思想是在程序执行过程中，尝试识别并替换那些在编译时就能确定其值的变量（常量），同时移除那些永远不会被执行到的代码块（不可达代码）。

以下是 SCCP 的实现思路：

1. 核心数据结构与工作列表：

Lattice 值（Lattice Value）: SCCP 使用三值格（Three-Valued Lattice）来表示变量的状态：

Top (T): 初始状态，表示变量的值未知，但可能是一个常量。

Constant (C): 表示变量的值已经确定为一个具体的常量。

Bottom (⊥): 表示变量的值不确定或不是一个常量（例如，它可能在运行时有多个不同的值，或者从内存中加载）。一旦变量状态变为 Bottom，它就不能再变回 Constant 或 Top。

SSAPValue: 封装了 Lattice 值和常量具体值（如果状态是 Constant）。

valState (map<Value, SSAPValue>):* 存储程序中每个 Value（变量、指令结果等）的当前 SCCP Lattice 状态。

ExecutableBlocks (set):* 存储在分析过程中被确定为可执行的基本块。

工作列表 (Worklists):

cfgWorkList (queue<pair<BasicBlock, BasicBlock>>):** 存储待处理的控制流图（CFG）边。当一个块被标记为可执行时，它的后继边会被添加到这个列表。

ssaWorkList (queue):* 存储待处理的 SSA (Static Single Assignment) 指令。当一个指令的任何操作数的状态发生变化时，该指令就会被添加到这个列表，需要重新评估。

2. 初始化：

所有 Value 的状态都被初始化为 Top。

所有基本块都被初始化为不可执行。

函数的入口基本块被标记为可执行，并且该块中的所有指令被添加到 ssaWorkList。

3. 迭代过程 (Fixed-Point Iteration)：

SCCP 的核心是一个迭代过程，它交替处理 CFG 工作列表和 SSA 工作列表，直到达到一个不动点（即没有更多的状态变化）。

处理 cfgWorkList:

从 cfgWorkList 中取出一个边 (prev, next)。

如果 next 块之前是不可执行的，现在通过 prev 块可达，则将其标记为可执行 (markBlockExecutable)。

一旦 next 块变为可执行，其内部的所有指令（特别是 Phi 指令）都需要被重新评估，因此将它们添加到 ssaWorkList。

处理 ssaWorkList:

从 ssaWorkList 中取出一个指令 inst。

重要： 只有当 inst 所在的块是可执行的，才处理该指令。不可执行块中的指令不参与常量传播。

计算新的 Lattice 值 (computeLatticeValue): 根据指令类型和其操作数的当前 Lattice 状态，计算 inst 的新的 Lattice 状态。

常量折叠: 如果所有操作数都是常量，则可以直接执行运算并得到一个新的常量结果。

Bottom 传播: 如果任何操作数是 Bottom，或者运算规则导致不确定（例如除以零），则结果为 Bottom。

Phi 指令的特殊处理: Phi 指令的值取决于其所有可执行的前驱块传入的值。

如果所有可执行前驱都提供了相同的常量 C，则 Phi 结果为 C。

如果有任何可执行前驱提供了 Bottom，或者不同的可执行前驱提供了不同的常量，则 Phi 结果为 Bottom。

如果所有可执行前驱都提供了 Top，则 Phi 结果仍为 Top。

更新状态: 如果 inst 的新计算出的 Lattice 值与它当前存储的值不同，则更新 valState[inst]。

传播变化: 如果 inst 的状态发生变化，那么所有使用 inst 作为操作数的指令都可能受到影响，需要重新评估。因此，将 inst 的所有使用者添加到 ssaWorkList。

处理终结符指令 (BranchInst, ReturnInst):

对于条件分支 BranchInst，如果其条件操作数变为常量：

如果条件为真，则只有真分支的目标块是可达的，将该边添加到 cfgWorkList。

如果条件为假，则只有假分支的目标块是可达的，将该边添加到 cfgWorkList。

如果条件不是常量（Top 或 Bottom），则两个分支都可能被执行，将两边的边都添加到 cfgWorkList。

这会影响 CFG 的可达性分析，可能导致新的块被标记为可执行。

4. 应用优化 (Transformation)：

当两个工作列表都为空，达到不动点后，程序代码开始进行实际的修改：

常量替换:

遍历所有指令。如果指令的 valState 为 Constant，则用相应的 ConstantValue 替换该指令的所有用途 (replaceAllUsesWith)。

将该指令标记为待删除。

对于指令的操作数，如果其 valState 为 Constant，则直接将操作数替换为对应的 ConstantValue（常量折叠）。

删除死指令: 遍历所有标记为待删除的指令，并从其父基本块中删除它们。

删除不可达基本块: 遍历函数中的所有基本块。如果一个基本块没有被标记为可执行 (ExecutableBlocks 中不存在)，则将其从函数中删除。但入口块不能删除。

简化分支指令:

遍历所有可执行的基本块的终结符指令。

对于条件分支 BranchInst，如果其条件操作数在 valState 中是 Constant：

如果条件为真，则将该条件分支替换为一个无条件跳转到真分支目标块的指令。

如果条件为假，则将该条件分支替换为一个无条件跳转到假分支目标块的指令。

更新 CFG，移除不可达的分支边和其前驱信息。

computeLatticeValue 的具体逻辑：

这个函数是 SCCP 的核心逻辑，它定义了如何根据指令类型和操作数的当前 Lattice 状态来计算指令结果的 Lattice 状态。

二元运算 (Add, Sub, Mul, Div, Rem, ICmp, And, Or):

如果任何一个操作数是 Bottom，结果就是 Bottom。

如果任何一个操作数是 Top，结果就是 Top。

如果两个操作数都是 Constant，执行实际的常量运算，结果是一个新的 Constant。

一元运算 (Neg, Not):

如果操作数是 Bottom，结果就是 Bottom。

如果操作数是 Top，结果就是 Top。

如果操作数是 Constant，执行实际的常量运算，结果是一个新的 Constant。

Load 指令: 通常情况下，Load 的结果会被标记为 Bottom，因为内存内容通常在编译时无法确定。但如果加载的是已知的全局常量，可能可以确定。在提供的代码中，它通常返回 Bottom。

Store 指令: Store 不产生值，所以其 SSAPValue 保持 Top 或不关心。

Call 指令: 大多数 Call 指令（尤其是对外部或有副作用的函数）的结果都是 Bottom。对于纯函数，如果所有参数都是常量，理论上可以折叠，但这需要额外的分析。

GetElementPtr (GEP) 指令: GEP 计算内存地址。如果所有索引都是常量，地址本身是常量。但 SCCP 关注的是数据值，因此这里通常返回 Bottom，除非有特定的指针常量跟踪。

Phi 指令: 如上所述，基于所有可执行前驱的传入值进行聚合。

Alloc 指令: Alloc 分配内存，返回一个指针。其内容通常是 Bottom。

Branch 和 Return 指令: 这些是终结符指令，不产生一个可用于其他指令的值，通常 SSAPValue 保持 Top 或不关心。

类型转换 (ZExt, SExt, Trunc, FtoI, ItoF): 如果操作数是 Constant，则执行相应的类型转换，结果仍为 Constant。对于浮点数转换，由于 SSAPValue 的 constantVal 为 int 类型，所以对浮点数的操作会保守地返回 Bottom。

未处理的指令: 默认情况下，任何未明确处理的指令都被保守地假定为产生 Bottom 值。

浮点数处理的注意事项：

在提供的代码中，SSAPValue 的 constantVal 是 int 类型。这使得浮点数常量传播变得复杂。对于浮点数相关的指令（kFAdd, kFMul, kFCmp, kFNeg, kFNot, kItoF, kFtoI 等），如果不能将浮点值准确地存储在 int 中，或者不能可靠地执行浮点运算，那么通常会保守地将结果设置为 Bottom。一个更完善的 SCCP 实现会使用 std::variant<int, float> 或独立的浮点常量存储来处理浮点数。

LoopSR循环归纳变量强度削弱 关于魔数计算的说明

魔数除法的核心思想是：将除法转换为乘法和移位

数学原理：x / d ≈ (x * m) >> (32 + s)

m 是魔数 (magic number) s 是额外的移位量 (shift)

是算术右移

2^(32+s) / d ≤ m < 2^(32+s) / d + 2^s / d

cd /home/downright/Compiler_Opt/mysysy && python3 -c "

真正的迭代原因：精度要求

def explain_precision_requirement(): d = 10

print('魔数算法需要找到精确的边界值：')
print('目标：2^p > d * (2^31 - r)，其中r是余数')
print()

# 模拟我们算法的迭代过程
p = 31
two_p = 2**p
r = two_p % d  # 余数
m = two_p // d  # 商

print(f'初始状态 (p={p}):')
print(f'  2^{p} = {two_p:,}')
print(f'  2^{p} / {d} = {m:,} 余 {r}')
print(f'  需要检查: 2^{p} > {d} * (2^31 - {r}) = {d * (2**31 - r):,}')
print(f'  条件满足: {two_p > d * (2**31 - r)}')
print()

# 继续迭代直到条件满足
iteration = 0
while r != 0 and m < 2**31:
    iteration += 1
    p += 1
    two_p *= 2
    m *= 2
    r *= 2
    if r >= d:
        m += 1
        r -= d
        
    print(f'迭代 {iteration} (p={p}):')
    print(f'  m = {m:,}, r = {r}')
    print(f'  m < 2^31? {m < 2**31} (2^31 = {2**31:,})')
    
    if m >= 2**31:
        print(f'  ✗ 魔数 {m:,} 超出32位范围!')
        break
    elif r == 0:
        print(f'  ✓ 余数为0，找到精确解')
        break
    
    if iteration > 10:  # 防止无限循环
        print('  ... (限制迭代次数)')
        break

explain_precision_requirement() "

问题在于精度要求。理论魔数需要非常精确，不能简单地用 2^32 / d。让我展示真正的迭代原因：

cd /home/downright/Compiler_Opt/mysysy && python3 -c "

真正的迭代原因：精度要求

def explain_precision_requirement(): d = 10

print('魔数算法需要找到精确的边界值：')
print('目标：2^p > d * (2^31 - r)，其中r是余数')
print()

# 模拟我们算法的迭代过程
p = 31
two_p = 2**p
r = two_p % d  # 余数
m = two_p // d  # 商

print(f'初始状态 (p={p}):')
print(f'  2^{p} = {two_p:,}')
print(f'  2^{p} / {d} = {m:,} 余 {r}')
print(f'  需要检查: 2^{p} > {d} * (2^31 - {r}) = {d * (2**31 - r):,}')
print(f'  条件满足: {two_p > d * (2**31 - r)}')
print()

# 继续迭代直到条件满足
iteration = 0
while r != 0 and m < 2**31:
    iteration += 1
    p += 1
    two_p *= 2
    m *= 2
    r *= 2
    if r >= d:
        m += 1
        r -= d
        
    print(f'迭代 {iteration} (p={p}):')
    print(f'  m = {m:,}, r = {r}')
    print(f'  m < 2^31? {m < 2**31} (2^31 = {2**31:,})')
    
    if m >= 2**31:
        print(f'  ✗ 魔数 {m:,} 超出32位范围!')
        break
    elif r == 0:
        print(f'  ✓ 余数为0，找到精确解')
        break
    
    if iteration > 10:  # 防止无限循环
        print('  ... (限制迭代次数)')
        break

explain_precision_requirement() "

cd /home/downright/Compiler_Opt/mysysy && python3 -c "

检查初始状态是否会溢出

def check_initial_overflow(): int32_max = 2**31 - 1

print('检查不同除数的初始魔数是否会溢出:')
print(f'32位有符号整数最大值: {int32_max:,}')
print()

# 检查各种除数
divisors = [2, 3, 5, 7, 9, 10, 11, 13, 17, 25, 100, 1000]

for d in divisors:
    # 初始魔数 = 2^31 / d
    initial_magic = (2**31) // d
    
    overflow = initial_magic > int32_max
    status = \"溢出\" if overflow else \"安全\"
    
    print(f'd={d:4d}: 初始魔数 = 2^31/{d} = {initial_magic:10,} [{status}]')
    
print()
print('结论: 初始状态下魔数不会溢出，溢出发生在迭代过程中')

check_initial_overflow() "

总结 迭代的必要性：

不是为了避免初始溢出（初始状态安全） 是为了找到最精确的魔数，减少舍入误差 每次迭代提高一倍精度，但魔数也翻倍 溢出发生时机：

初始状态：2^31 / d 总是在32位范围内 迭代过程：2^32 / d, 2^33 / d, ... 逐渐超出32位范围 回退值的正确性：

回退值是基于数学理论和实践验证的标准值 来自LLVM、GCC等成熟编译器的实现 通过测试验证，对各种输入都能产生正确结果 算法设计哲学：

先尝试最优解：通过迭代寻找最精确的魔数 检测边界条件：当超出32位范围时及时发现 智能回退：使用已验证的标准值保证正确性 保持通用性：对于没有预设值的除数仍然可以工作

死归纳变量消除

整体架构和工作流程 当前的归纳变量消除优化分为三个清晰的阶段：

识别阶段：找出所有潜在的死归纳变量 安全性分析阶段：验证每个变量消除的安全性 消除执行阶段：实际删除安全的死归纳变量

逃逸点检测 (已修复的关键安全机制) 数组索引检测：GEP指令被正确识别为逃逸点 循环退出条件：用于比较和条件分支的归纳变量不会被消除 控制流指令：condBr、br、return等被特殊处理为逃逸点 内存操作：store/load指令经过别名分析检查

后续优化可能涉及的改动

1）将所有的alloca集中到entryblock中（已实现）

好处：优化友好性，方便mem2reg提升 目前没有实现这个机制，如果想要实现首先解决同一函数不同域的同名变量命名区分 需要保证符号表能正确维护域中的局部变量

关于中端优化提升编译器性能的TODO

usedelete_withinstdelte方法

这个方法删除了use关系并移除了指令，逻辑是根据Instruction* inst去find对应的迭代器并erase 有些情况下外部持有迭代器和inst,可以省略find过程