后端Pass简介——IfConversion.cpp

If conversion

这是一个很重要的大型 pass，代码量达到了 2300 余行。

他实现的是 LLVM 后端 MachineInstr 级别的 If Conversion Pass（即 if-converter）：
此 Pass 的主要目标是将条件分支（br）转换为带谓词或条件执行的指令，借助目标架构对条件执行（predication）或条件移动（e.g. ARM 的 IT 指令组、x86 的 CMOVcc）支持，减少分支指令，降低分支错判开销。
适用场景如下：

• Diamond 结构：针对以下基本块布局进行转换：

   [Entry]
      |
    Branch
   /      \
TrueBB   FalseBB
   \      /
  MergeBB

核心处理函数如下：

bool IfConverter::runOnMachineFunction(MachineFunction &MF) {  
  if (skipFunction(MF.getFunction()) || (PredicateFtor && !PredicateFtor(MF)))  
    return false;  
  
  const TargetSubtargetInfo &ST = MF.getSubtarget();  
  TLI = ST.getTargetLowering();  
  TII = ST.getInstrInfo();  
  TRI = ST.getRegisterInfo();  
  MBFIWrapper MBFI(  
      getAnalysis<MachineBlockFrequencyInfoWrapperPass>().getMBFI());  
  MBPI = &getAnalysis<MachineBranchProbabilityInfoWrapperPass>().getMBPI();  
  ProfileSummaryInfo *PSI =  
      &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();  
  MRI = &MF.getRegInfo();  
  SchedModel.init(&ST);  
  
  if (!TII) return false;  
  
  PreRegAlloc = MRI->isSSA();  
  
  bool BFChange = false;  
  if (!PreRegAlloc) {  
    // Tail merge tend to expose more if-conversion opportunities.  
    BranchFolder BF(true, false, MBFI, *MBPI, PSI);  
    BFChange = BF.OptimizeFunction(MF, TII, ST.getRegisterInfo());  
  }  
  
  LLVM_DEBUG(dbgs() << "\nIfcvt: function (" << ++FnNum << ") \'"  
                    << MF.getName() << "\'");  
  
  if (FnNum < IfCvtFnStart || (IfCvtFnStop != -1 && FnNum > IfCvtFnStop)) {  
    LLVM_DEBUG(dbgs() << " skipped\n");  
    return false;  
  }  
  LLVM_DEBUG(dbgs() << "\n");  
  
  MF.RenumberBlocks();  
  BBAnalysis.resize(MF.getNumBlockIDs());  
  
  std::vector<std::unique_ptr<IfcvtToken>> Tokens;  
  MadeChange = false;  
  unsigned NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle +  
    NumTriangleRev + NumTriangleFalse + NumTriangleFRev + NumDiamonds;  
  while (IfCvtLimit == -1 || (int)NumIfCvts < IfCvtLimit) {  
    // Do an initial analysis for each basic block and find all the potential  
    // candidates to perform if-conversion.    bool Change = false;  
    AnalyzeBlocks(MF, Tokens);  
    while (!Tokens.empty()) {  
      std::unique_ptr<IfcvtToken> Token = std::move(Tokens.back());  
      Tokens.pop_back();  
      BBInfo &BBI = Token->BBI;  
      IfcvtKind Kind = Token->Kind;  
      unsigned NumDups = Token->NumDups;  
      unsigned NumDups2 = Token->NumDups2;  
  
      // If the block has been evicted out of the queue or it has already been  
      // marked dead (due to it being predicated), then skip it.      if (BBI.IsDone)  
        BBI.IsEnqueued = false;  
      if (!BBI.IsEnqueued)  
        continue;  
  
      BBI.IsEnqueued = false;  
  
      bool RetVal = false;  
      switch (Kind) {  
      default: llvm_unreachable("Unexpected!");  
      case ICSimple:  
      case ICSimpleFalse: {  
        bool isFalse = Kind == ICSimpleFalse;  
        if ((isFalse && DisableSimpleF) || (!isFalse && DisableSimple)) break;  
        LLVM_DEBUG(dbgs() << "Ifcvt (Simple"  
                          << (Kind == ICSimpleFalse ? " false" : "")  
                          << "): " << printMBBReference(*BBI.BB) << " ("  
                          << ((Kind == ICSimpleFalse) ? BBI.FalseBB->getNumber()  
                                                      : BBI.TrueBB->getNumber())  
                          << ") ");  
        RetVal = IfConvertSimple(BBI, Kind);  
        LLVM_DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");  
        if (RetVal) {  
          if (isFalse) ++NumSimpleFalse;  
          else         ++NumSimple;  
        }  
       break;  
      }  
      case ICTriangle:  
      case ICTriangleRev:  
      case ICTriangleFalse:  
      case ICTriangleFRev: {  
        bool isFalse = Kind == ICTriangleFalse;  
        bool isRev   = (Kind == ICTriangleRev || Kind == ICTriangleFRev);  
        if (DisableTriangle && !isFalse && !isRev) break;  
        if (DisableTriangleR && !isFalse && isRev) break;  
        if (DisableTriangleF && isFalse && !isRev) break;  
        LLVM_DEBUG(dbgs() << "Ifcvt (Triangle");  
        if (isFalse)  
          LLVM_DEBUG(dbgs() << " false");  
        if (isRev)  
          LLVM_DEBUG(dbgs() << " rev");  
        LLVM_DEBUG(dbgs() << "): " << printMBBReference(*BBI.BB)  
                          << " (T:" << BBI.TrueBB->getNumber()  
                          << ",F:" << BBI.FalseBB->getNumber() << ") ");  
        RetVal = IfConvertTriangle(BBI, Kind);  
        LLVM_DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");  
        if (RetVal) {  
          if (isFalse)  
            ++NumTriangleFalse;  
          else if (isRev)  
            ++NumTriangleRev;  
          else  
            ++NumTriangle;  
        }  
        break;  
      }  
      case ICDiamond:  
        if (DisableDiamond) break;  
        LLVM_DEBUG(dbgs() << "Ifcvt (Diamond): " << printMBBReference(*BBI.BB)  
                          << " (T:" << BBI.TrueBB->getNumber()  
                          << ",F:" << BBI.FalseBB->getNumber() << ") ");  
        RetVal = IfConvertDiamond(BBI, Kind, NumDups, NumDups2,  
                                  Token->TClobbersPred,  
                                  Token->FClobbersPred);  
        LLVM_DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");  
        if (RetVal) ++NumDiamonds;  
        break;  
      case ICForkedDiamond:  
        if (DisableForkedDiamond) break;  
        LLVM_DEBUG(dbgs() << "Ifcvt (Forked Diamond): "  
                          << printMBBReference(*BBI.BB)  
                          << " (T:" << BBI.TrueBB->getNumber()  
                          << ",F:" << BBI.FalseBB->getNumber() << ") ");  
        RetVal = IfConvertForkedDiamond(BBI, Kind, NumDups, NumDups2,  
                                      Token->TClobbersPred,  
                                      Token->FClobbersPred);  
        LLVM_DEBUG(dbgs() << (RetVal ? "succeeded!" : "failed!") << "\n");  
        if (RetVal) ++NumForkedDiamonds;  
        break;  
      }  
  
      if (RetVal && MRI->tracksLiveness())  
        recomputeLivenessFlags(*BBI.BB);  
  
      Change |= RetVal;  
  
      NumIfCvts = NumSimple + NumSimpleFalse + NumTriangle + NumTriangleRev +  
        NumTriangleFalse + NumTriangleFRev + NumDiamonds;  
      if (IfCvtLimit != -1 && (int)NumIfCvts >= IfCvtLimit)  
        break;  
    }  
  
    if (!Change)  
      break;  
    MadeChange |= Change;  
  }  
  
  Tokens.clear();  
  BBAnalysis.clear();  
  
  if (MadeChange && IfCvtBranchFold) {  
    BranchFolder BF(false, false, MBFI, *MBPI, PSI);  
    BF.OptimizeFunction(MF, TII, MF.getSubtarget().getRegisterInfo());  
  }  
  
  MadeChange |= BFChange;  
  return MadeChange;  
}

• 在寄存器分配后阶段（PreRegAlloc==false），先尝试做一次尾合并（tail merging），暴露更多简单的 if-conversion 机会。
• FnNum 全局计数：只在编号在 [IfCvtFnStart, IfCvtFnStop] 区间内的函数上执行转换，方便按命令行参数限制。
• 遍历每个 MachineBasicBlock，检测它是否符合 Simple、Triangle、Diamond、ForkedDiamond 等各种形状的 if-conversion 模式，将所有候选 push 到 Tokens 中。