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

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

该优化过程并非旨在替代或完全替代 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 true
  MI.isSafeToMove(AA, SawStore); // MachineInstr.cpp:1259 !store !call !load !phi !inlineasm !positino ...
  MachineBasicBlock *SuccToSinkTo =
      FindSuccToSinkTo(MI, ParentBlock, BreakPHIEdge, AllSuccessors);
  // 不要破坏隐式空指针检查。这是一种性能启发，而非正确性所必需
  // 如果 MI 可能被隐式空指针检查优化用作内存操作，则返回 true
  SinkingPreventsImplicitNullCheck(...);
  // 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