llvm sroa

[lfeng14]

疑问：

• sroa pass是在mem2reg之前执行，为什么不首先执行mem2reg？
  SROA 必须在 mem2reg 之前执行，因为 mem2reg 只能处理“标量 alloca”，而 SROA 的任务就是把复杂的 alloca 拆成标量。
• 整体流程：
  • 见评论
• 什么是sroa的slice ?
  • slice = alloca 的一个“可独立处理的内存片段”
  • slice 由访问偏移决定
  • slice 决定 alloca 如何被拆分
  • 每个 slice 最终变成一个标量 alloca → 再被 mem2reg 提升为 SSA

实操

• 17版本构建时打开assert；19版本貌似不识别选项后面证实是正常的；

  ./install/bin/opt -S --passes=sroa demo.ll -debug 
  opt: Unknown command line argument '-debug'.  Try: './install/bin/opt --help'
  opt: Did you mean '--debugify'?
  

  $cat > demo.ll
  define i32 @foo(i32 %0, i32 %1) {
  entry:
    %2 = alloca i32, align 4
    %3 = alloca i32, align 4
    store i32 %0, ptr %2, align 4
    store i32 %1, ptr %3, align 4
    %4 = load i32, ptr %2, align 4
    %5 = load i32, ptr %3, align 4
    %6 = mul i32 %4, %4
    %7 = mul i32 %5, %5
    %8 = add i32 %6, %7
    ret i32 %8
  }
  ^C
  $ opt -S --passes=sroa demo.ll -debug 
  Args: opt -S --passes=sroa demo.ll -debug 
  SROA function: foo
  SROA alloca:   %3 = alloca i32, align 4
  define i32 @foo(i32 %0, i32 %1) {
  entry:
    %2 = alloca i32, align 4
    %3 = alloca i32, align 4
    store i32 %0, ptr %2, align 4   # dele 先存后取，中间没有别名
    store i32 %1, ptr %3, align 4   # 同理
    %4 = load i32, ptr %2, align 4  # dele 先存后取，中间没有别名
    %5 = load i32, ptr %3, align 4  # 同理
    %6 = mul i32 %4, %4
    %7 = mul i32 %5, %5
    %8 = add i32 %6, %7
    ret i32 %8
  }
  
    Rewriting FCA loads and stores...
  Slices of alloca:   %3 = alloca i32, align 4
    [0,4) slice #0 (splittable)
      used by:   store i32 %1, ptr %3, align 4
    [0,4) slice #1 (splittable)
      used by:   %5 = load i32, ptr %3, align 4
  Pre-splitting loads and stores
    Searching for candidate loads and stores
  Rewriting alloca partition [0,4) to:   %3 = alloca i32, align 4
    rewriting [0,4) slice #0 (splittable)
     Begin:(0, 4) NewBegin:(0, 4) NewAllocaBegin:(0, 4)
      original:   store i32 %1, ptr %3, align 4
            to:   store i32 %1, ptr %3, align 4
    rewriting [0,4) slice #1 (splittable)
     Begin:(0, 4) NewBegin:(0, 4) NewAllocaBegin:(0, 4)
      original:   %5 = load i32, ptr %3, align 4
            to:   %.0.load = load i32, ptr %3, align 4
    Speculating PHIs
    Rewriting Selects
  Deleting dead instruction:   %5 = load i32, ptr %3, align 4
  Deleting dead instruction:   store i32 %1, ptr %3, align 4
  SROA alloca:   %2 = alloca i32, align 4
  define i32 @foo(i32 %0, i32 %1) {
  entry:
    %2 = alloca i32, align 4
    %3 = alloca i32, align 4
    store i32 %0, ptr %2, align 4
    store i32 %1, ptr %3, align 4
    %4 = load i32, ptr %2, align 4
    %.0.load = load i32, ptr %3, align 4
    %5 = mul i32 %4, %4
    %6 = mul i32 %.0.load, %.0.load
    %7 = add i32 %5, %6
    ret i32 %7
  }
  
    Rewriting FCA loads and stores...
  Slices of alloca:   %2 = alloca i32, align 4
    [0,4) slice #0 (splittable)
      used by:   store i32 %0, ptr %2, align 4
    [0,4) slice #1 (splittable)
      used by:   %4 = load i32, ptr %2, align 4
  Pre-splitting loads and stores
    Searching for candidate loads and stores
  Rewriting alloca partition [0,4) to:   %2 = alloca i32, align 4
    rewriting [0,4) slice #0 (splittable)
     Begin:(0, 4) NewBegin:(0, 4) NewAllocaBegin:(0, 4)
      original:   store i32 %0, ptr %2, align 4
            to:   store i32 %0, ptr %2, align 4
    rewriting [0,4) slice #1 (splittable)
     Begin:(0, 4) NewBegin:(0, 4) NewAllocaBegin:(0, 4)
      original:   %4 = load i32, ptr %2, align 4
            to:   %.0.load1 = load i32, ptr %2, align 4
    Speculating PHIs
    Rewriting Selects
  Deleting dead instruction:   %4 = load i32, ptr %2, align 4
  Deleting dead instruction:   store i32 %0, ptr %2, align 4
  Promoting allocas with mem2reg...
  ; ModuleID = 'demo.ll'
  source_filename = "demo.ll"
  
  define i32 @foo(i32 %0, i32 %1) {
  entry:
    %2 = mul i32 %0, %0
    %3 = mul i32 %1, %1
    %4 = add i32 %2, %3
    ret i32 %4
  }
  
  

参考

• https://www.ziyue.cafe/posts/sroa-llvm-pass-analysis/

[lfeng14]

你抓得非常准：
你前面提到的那段逻辑（single‑store alloca → rewrite → remove）确实只是 SROA 的一个“顺手清理”分支，属于“能直接删掉的就删掉”。

但 SROA 的核心能力不是删除冗余 alloca，而是“化整为零”——把复杂的 aggregate alloca 拆成多个标量 alloca。
这才是 SROA 的主体逻辑，也是它名字的真正含义：Scalar Replacement of Aggregates。

下面我把“化整为零”这一部分的核心流程讲清楚，让你看到 SROA 的真正主线。

---

🌟 SROA 的核心逻辑：化整为零（拆分 aggregate alloca）

SROA 的主流程可以概括为：

分析 aggregate alloca → 切片（slice） → 为每个 slice 创建新的标量 alloca → 重写所有访问 → 删除旧 alloca

下面是更细的工程级拆解。

---

1. 找到“复杂的” alloca（aggregate alloca）

SROA 会挑出这些 alloca：

• alloca { i32, i32 }（结构体）
• alloca [10 x i32]（数组）
• alloca i64 但存在 partial load/store（部分访问）
• alloca 被 memcpy/memset 访问
• alloca 被 bitcast/GEP 访问不同偏移

这些都是 mem2reg 无法直接处理的。

---

2. 对每个 alloca 做“切片分析”（slice analysis）

这是 SROA 的核心算法。

它会分析所有对这个 alloca 的访问：

• 每个 store/load 的偏移范围
• 每个 GEP 指向的字段
• memcpy/memset 的覆盖范围
• bitcast 后的访问范围

然后把整个 alloca 的内存空间切成多个 不重叠的 slice。

例如：

struct S { i32 a; i32 b; }
alloca %S
store i32 10 → offset [0,4)
store i32 20 → offset [4,8)

切成两个 slice：

• slice 0: [0,4)
• slice 1: [4,8)

每个 slice 都可能变成一个新的 alloca。

---

3. 判断每个 slice 是否可拆分（splittable）

SROA 会检查：

• 这个 slice 是否被完整访问（不是 partial）
• 是否没有 alias
• 是否没有跨 slice 的访问
• 是否没有奇怪的 bitcast

如果 slice 是“干净的”，就可以拆分。

如果 slice 很复杂（例如 union、奇怪的 bitcast），就保持原样。

---

4. 为每个 slice 创建新的标量 alloca

这是“化整为零”的关键一步。

例如：

%S = alloca { i32, i32 }

拆成：

%S.a = alloca i32
%S.b = alloca i32

如果是数组：

alloca [4 x i32]

可能拆成：

alloca i32   ; element 0
alloca i32   ; element 1
alloca i32   ; element 2
alloca i32   ; element 3

如果是部分访问：

store i64 %v → offset [0,8)
load i32 → offset [0,4)

可能拆成两个 32-bit alloca。

---

5. 重写所有 load/store/GEP，使它们指向新的 alloca

例如：

%p = getelementptr %S, 0, 1
store i32 20, %p

变成：

store i32 20, %S.b

所有访问都被重写到新的标量 alloca 上。

---

6. 删除旧 alloca

当所有访问都被重写后：

• 旧 alloca 不再被使用
• 可以安全删除

---

7. 最后一步：调用 mem2reg，把标量 alloca 提升为 SSA

这一步不是 SROA 的主体，但 SROA 会自动触发它。

最终：

alloca → 标量 alloca → SSA 值

---

🔥 总结：SROA 的两条主线

你前面看到的是 支线逻辑：

✔ 删除 trivial alloca（single-store alloca）

• 只写一次 → load 全替换 → store 删除 → alloca 删除

而 SROA 的 主线逻辑 是：

⭐ 化整为零（真正的 SROA）

• 分析 aggregate alloca
• 切片（slice）
• 拆成多个标量 alloca
• 重写所有访问
• 删除旧 alloca
• 交给 mem2reg 进入 SSA

---

如果你愿意，我可以继续帮你：

• 画一张 SROA 的完整流程图（非常直观）
• 用一段 IR 手工跑一遍 SROA 的拆分过程
• 讲讲 SROA 如何处理 union、bitcast、memcpy（最复杂的部分）
• 对比 SROA 和 mem2reg 的职责边界

你想继续深入哪一块？

[lfeng14]

你这段话其实已经抓住了核心，但可以拆得更精细一点，把每一步“为什么这样做”也说清楚。我们就按你提到的几个动作：遍历 alloca → 判断是否单次 store → rewriteSingleStoreAlloca → removeStore → 删除 alloca，一步步展开。

---

1. 遍历每一个 alloca 指令：在找“简单到可以直接替换”的变量

在 SROA 或类似 early-pass 里，run 函数会：

• 枚举函数中的每一个 AllocaInst，也就是每一个栈上局部变量。
• 对每个 alloca 做“使用分析”（use-def/use-chain），看它是怎么被用的：
  • 有多少次 store
  • 有多少次 load
  • 有没有被传给别的函数（逃逸）
  • 有没有被 GEP/bitcast 复杂访问

这里的目标是：找出那些“非常简单”的 alloca，尤其是——只被写入一次（single store）、然后被多次读取（load）的那种。

---

2. 分析是否“只有一次 store”：这是一个非常强的约束

当你发现一个 alloca：

• 只出现了一次 store
• 其他所有使用都是 load
• 没有被取地址传出去、没有 alias、没有奇怪的 GEP

这意味着什么？

这个 alloca 本质上就是一个“只赋值一次的局部变量”，而且值在整个生命周期内不变。

在这种情况下，你根本不需要这个内存位置——你完全可以用那次 store 的值，直接替换所有 load。

这就是你说的下一步：rewriteSingleStoreAlloca。

---

3. rewriteSingleStoreAlloca：把所有 load 直接替换成那次 store 的值

逻辑大致是：

1. 找到那条唯一的 store 指令：
   • 形如：store T %val, T* %alloca
2. 记录被存进去的那个 SSA 值 %val
3. 遍历所有对这个 alloca 的 load：
   • 每个 load T, T* %alloca 都可以被替换成 %val
4. 用 %val 替换所有这些 load 的使用（use-replacement）
5. 标记这些 load 指令为“可删除”

从语义上看，这一步做的是：

“你既然只给这个变量赋值了一次，那所有读取它的地方，读到的都是同一个值——那我就不去内存读了，直接用这个值。”

这其实就是一个极简版的“局部常量传播/值传播”，但只针对这种“单次 store”的 alloca。

---

4. removeStore：既然所有 load 都不用了，那这次 store 也没意义了

当所有 load 都被替换成 %val 之后：

• 原来的 store 变成了“写了一个没人再读的内存”
• 也就是 死 store（dead store）

removeStore 做的就是：

• 检查这条 store 是否还有必要存在
• 如果没有任何后续使用依赖它（比如没有通过指针别名被读），就可以安全删除

这一步的意义是：

“既然没人再从这个 alloca 读东西，那你当初写进去那次 store 也没用了——删。”

---

5. 尝试删除整个 alloca：这个变量从 IR 里“蒸发”了

当：

• 所有 load 都被替换掉了
• 那次唯一的 store 也被删除了
• 这个 alloca 不再有任何使用（use_empty()）

那么这个 alloca 就变成了一个 完全无用的栈变量。

于是：

• 直接删除这条 alloca 指令
• IR 中就不再有这个变量的任何痕迹

从效果上看：

这个局部变量从“栈上的内存槽”变成了“一个纯 SSA 值”，甚至连“变量”这个概念都消失了，只剩下值本身在流动。

---

6. 把这段逻辑串成一句更精确的话

你原话：

遍历每一个Alloca指令，分析它是否只有一次store，如果确实只有一次store，那么通过rewriteSingleStoreAlloca，把每一个load都给替换成这个原先store的这个值。然后尝试进行removeStore，最后再尝试去掉整个Alloca指令。

可以稍微精炼、技术味更足一点写成：

在 run 中遍历每个 alloca，如果发现它只有一次 store 且其余使用全是 load，则通过 rewriteSingleStoreAlloca 将所有 load 替换为该 store 的被存值；随后尝试删除这条已无用的 store，最后在该 alloca 不再被使用时将其本身一并移除。

---

如果你愿意，我们可以下一步拿一小段你自己的 IR，按这套逻辑手动“跑一遍”：标出 alloca → 找唯一 store → 替换 load → 删 store → 删 alloca，你会对这类优化的“手感”特别有直觉。