Dev

LLVM的SROA解析

LLVM的SROA（Scalar Replacement of Aggregates）的实现解析

FCA: First Class Aggregate（第一类聚合体，如结构体或数组）

总体思路

SROA是一个Function Pass，输入是单个函数。

  1. 提前promote简单alloca：首先遍历entry基本块内的alloca指令。如果某个Alloca指令可以直接被Promote（isAllocaPromotable），简单来说仅被load和store，则提前给promote掉，用Mem2Reg相关的SSA构建函数。否则就加入工作队列中依次分析处理。
  2. runOnAlloca：处理剩下的每个alloca指令
    • 维护了PromotableAllocas队列，存储可以被提升的Alloca指令。在循环结尾提升并清理。
    • 维护了DeadInsts，存储等待被删除的指令，由函数deleteDeadInstructions删除
    • 维护了DeletedAllocas，从DeletedAllocas里

处理每个alloca指令（runOnAlloca）

  1. 如果没有任何User，或者是Array形式的alloca指令，即alloca的第二个操作数不是1，则直接不处理。
  2. 使用AggLoadStoreRewriter处理带有extractvalue指令的复杂的结构体的load和store。将结构体的load和store拆分为每个成员的load和store，然后再用extractvalue/insertvalue分开或者拼在一起。
  3. 构建AllocaSlices，如果认定该alloca为escaped，则放弃
  4. 删掉没有User的一些地址的引用，比如bitcast（DeadUser）和DeadOp（即Alloca被Gep指令的使用，但是这个operand不可能被取到）
  5. 调用splitAlloca，基于计算得到的Alloca Slice分割。
    1. presplitLoadsAndStores将过大的批量内存复制给分割开。
    2. 如果某个Slice和别的Slice要么不相交，要么互为包含关系就还好，如果出现了交替重叠则标记为无法split。

对于一个很大的alloca，会尽量将内部标记为unsplittable的

AllocaSlices：Alloca能否被拆分的判断

AllocaSlices的构造函数里调用了用于构建的AllocaSlices::SliceBuilder，它继承了PtrUseVisitor，递归遍历指针的Use树，分析指针的escaped Flag和aborted Flag。如果遇到了指针难以处理的情况，指针会标记为escaped。

  • alloca可以被store和load读写。但是alloca自身的地址不能被store到别的地方。根据Load和Store的边界会分割Slice。
  • 可以被Gep指令计算，但是如果计算得到了未知偏移的地址，则放弃处理。
  • 遇到内存转移指令，memcpy/memmove，会根据复制点分割出Slice。

继承后拓展的逻辑里，，额外维护了alloca的分割点，并创建Slice，partition等数据结构：

  • Slice表示一个Alloca的位置中的一个部分[BeginOffset, EndOffset)同时有一个Use*成员和一个isSplittable Flag.
  • Partition是一种特殊的Slice数组的iterator，将相同范围内的Slice聚合起来一起返回。

AllocaSlices内的成员有： - vector<Slice> Slices： - vector<Instruction *> DeadUsers: - vector<Use *> DeadOperands: