MachineSink - 优化阅读笔记

注：该优化与全局子表达式消除刚好是相反的过程，具体该不该做这个优化得看代价模型算出来的结果(有采样文件指导算得会更准确)

该优化过程将指令移动到后继基本块中，以便它们不会在不需要其结果的路径上执行。

该优化过程并非旨在替代或完全替代 LLVM IR 级别的下沉优化。它仅设计用于下沉简单的结构，这些结构在 lowering 和指令选择之前不会显现.

测试用例:

grep "machine-sink" llvm/test/* -Rnw|grep X86|grep -v debug
./build4/bin/llvm-lit llvm/test/DebugInfo/MIR/X86/machinesink.mir -a
./build4/bin/llc -run-pass=dot-machine-cfg llvm/test/DebugInfo/MIR/X86/machinesink.mir
dot .Process.dot -T svg -o Process.dot.svg
dot .test2.dot -T svg -o test2.dot.svg
dot .test3.dot -T svg -o test3.dot.svg./build4/bin/llc -mtriple=x86_64-unknown-unknown -run-pass=machine-sink -o - ./llvm/test/DebugInfo/MIR/X86/machinesink.mir &> dd
./build4/bin/llc -mtriple=x86_64-unknown-unknown -run-pass=removeredundantdebugvalues -o - ./llvm/test/DebugInfo/MIR/X86/machinesink.mir &> ddd

效果:

几个重要的接口：

bool MachineSinking::runOnMachineFunction(MachineFunction &MF) {// 更新寄存器信息RegClassInfo.runOnMachineFunction(MF);// 遍历每个 BB, 寻找优化的场景for (auto &MBB: MF)MadeChange |= ProcessBlock(MBB);// 处理需要打破的临界边auto NewSucc = Pair.first->SplitCriticalEdge(Pair.second, *this);

void RegisterClassInfo::runOnMachineFunction(const MachineFunction &mf) {// 1. 检查 CSR 数组的每个元素是否与之前分析的相同const MCPhysReg *CSR = MRI.getCalleeSavedRegs();// 2. 如果有改变，记录每一个 CSR 及它的别名for (MCRegAliasIterator AI(*I, TRI, true); AI.isValid(); ++AI)CalleeSavedAliases[*AI] = *I;// 3. 更新每个 CSRs 的分配优先级if (IgnoreCSRForAllocOrder.size() != CSRHintsForAllocOrder.size() ||IgnoreCSRForAllocOrder != CSRHintsForAllocOrder) {// 4. 获取寄存器的成本RegCosts = TRI->getRegisterCosts(*MF);// 5. 更新保留寄存器const BitVector &RR = MF->getRegInfo().getReservedRegs();// 6. 更新寄存器压力unsigned NumPSets = TRI->getNumRegPressureSets();// build4/lib/Target/X86/X86GenRegisterInfo.inc:11902// build4/lib/Target/AArch64/AArch64GenRegisterInfo.inc:103840
}

bool MachineSinking::ProcessBlock(MachineBasicBlock &MBB) {// 待优化BB需要有多个后继，且不是死的基本块// 逆序遍历每条指令do {// 记录指令的 debug 信息// 执行琐碎的前向聚合, SRC=DRC的拷贝指令的替换bool Joined = PerformTrivialForwardCoalescing(MI, &MBB);// 尝试下沉指令if (SinkInstruction(MI, SawStore, AllSuccessors))} while (!ProcessedBegin);
}

bool MachineSinking::SinkInstruction(MachineInstr &MI, bool &SawStore,AllSuccsCache &AllSuccessors) {TII->shouldSink(MI); // X86 always trueMI.isSafeToMove(AA, SawStore); // MachineInstr.cpp:1259 !store !call !load !phi !inlineasm !positino ...MachineBasicBlock *SuccToSinkTo =FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);// 不要破坏隐式空指针检查。这是一种性能启发，而非正确性所必需// 如果 MI 可能被隐式空指针检查优化用作内存操作，则返回 trueSinkingPreventsImplicitNullCheck(...);// llvm/test/CodeGen/X86/implicit-null-check.ll// br i1 %c, label %is_null, label %not_null, !make.implicit !0// 这应该包括支持在当前块内下沉指令，以缩短其寄存器活跃范围。我们经常将指令下沉到大块的顶部，但最好在它们在块中第一次使用之前也将其下沉。但是，此变换必须小心，不要增加寄存器压力，例如，如果下沉 "x = y + z"，但它杀死了 y 和 z，那么会增加 y 和 z 的寄存器活跃范围，而只会减小 x 的寄存器活跃范围MachineBasicBlock *SuccToSinkTo = FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);// 检查是否会引入僵尸寄存器if (SuccToSinkTo->isLiveIn(Reg))// 如果需要打破危险边界, // 或 会破坏 PHI 边界if (SuccToSinkTo->pred_size() > 1) if (blockPrologueInterferes(SuccToSinkTo, InsertPos, MI, TRI, TII, MRI)) || if (BreakPHIEdge)// 延后打破危险边界，就记录一下bool Status = PostponeSplitCriticalEdge(MI, ParentBlock, SuccToSinkTo, BreakPHIEdge);// ToSplit.insert(std::make_pair(FromBB, ToBB));// 查找插入点, 跳过 phi和序幕指令SuccToSinkTo->SkipPHIsAndLabels(SuccToSinkTo->begin());// 收集需要一并下沉的debug指令DbgUsersToSink.push_back({DbgMI, SmallVector<unsigned, 2>(1, MO.getReg())});// 下沉指令及其相关调试指令performSink(MI, *SuccToSinkTo, InsertPos, DbgUsersToSink);// 移动指令：SuccToSinkTo.splice(InsertPos, ParentBlock, MI, ++MachineBasicBlock::iterator(MI));// 处理debug信息：attemptDebugCopyProp(MI, *DbgMI, Reg)// 清除 kill 标记RegsToClearKillFlags.insert(MO.getReg());
}

MachineBasicBlock *
MachineSinking::FindSuccToSinkTo(MachineInstr &MI, MachineBasicBlock *MBB,bool &BreakPHIEdge,AllSuccsCache &AllSuccessors) {// 检查要下沉的指令的每个操作数for (const MachineOperand &MO : MI.operands()) {// 对于虚拟寄存器// 需要能安全移动if (!TII->isSafeToMoveRegClassDefs(MRI->getRegClass(Reg)))// llvm/lib/Target/X86/X86InstrInfo.cpp:7534// 否则，我们应该查看所有的后继块并决定应该下沉到哪一个。如果我们有可靠的块频率信息（frequency != 0），则将具有较小频率的后继块优先级更高，否则优先考虑较小的循环深度for (MachineBasicBlock *SuccBlock :GetAllSortedSuccessors(MI, MBB, AllSuccessors)) {// 除了MBB的直接后继, 被 MBB 作为直接支配者的 DomTree 子节点也会被遍历/// AllUsesDominatedByBlock - 如果指定寄存器的所有使用都在指定块支配的块中发生，则返回 true, 如果任何使用在定义块中，则返回 false，因为在使用之后移动定义是不合法的。if (AllUsesDominatedByBlock(Reg, SuccBlock, MBB,BreakPHIEdge, LocalUse)) {}// 检查收益if (!isProfitableToSinkTo(Reg, MI, MBB, SuccToSinkTo, AllSuccessors))}
}bool MachineSinking::isProfitableToSinkTo(Register Reg, MachineInstr &MI,MachineBasicBlock *MBB,MachineBasicBlock *SuccToSinkTo,AllSuccsCache &AllSuccessors) {// 1. 不 反向支配 Def BB!PDT->dominates(SuccToSinkTo, MBB)// 2. 循环嵌套更浅if (CI->getCycleDepth(MBB) > CI->getCycleDepth(SuccToSinkTo))// 3. 寄存器压力不超限if (isRegisterPressureSetExceedLimit(MRI->getRegClass(Reg)))
}

遗留问题：

1. 与 llvm ir 中 sink 的区别
2. split critical edge 具体是怎么做的

---

LLVM IR 中搜索到其他三个 Sink 相关的pass:

# find llvm/lib/ -name "*.cpp"|grep "sink" -i
llvm/lib/Transforms/Scalar/Sink.cpp
llvm/lib/Transforms/Scalar/LoopSink.cpp
llvm/lib/Transforms/Scalar/GVNSink.cpp
llvm/lib/CodeGen/MachineSink.cpp