[CodeGen] Add a pass to do block predication on SSA machine IR

[ThomasRaoux]

Summary

For targets requiring aggressive scheduling and/or software pipeline we need to apply predication before preRA scheduling. This adds a pass re-using the early if-cvt infrastructure but generating predicated instructions instead of speculatively executing instructions. It allows doing if conversion on blocks containing instructions with side-effects. The pass re-use the target hook from postRA if-conversion to let the target decide on the heuristic to apply.

[lebedev.ri]

Tests missing; please upload all patches with full context (-U99999)

[ThomasRaoux]

In D66190#1628712, @lebedev.ri wrote:

Tests missing; please upload all patches with full context (-U99999)

Updated the patch to have full context. Sorry about that. As mentioned in the description there are currently no target in LLVM trunk supporting both predicate and select instructions hooks and this is needed for this pass to work. So I'm not able to add tests at the moment and the target I'm working in cannot be up-streamed right now. If this is not acceptable I'll keep this in my target for now.

[lebedev.ri]

One more question - i can't recall if there's precedent for bundling more than one pass
into the same source file, that does not look ideal.

Can the pass not be run standalone, does it really require some specific target?
Perhaps that can be short-circuited via some cl::opt just for testing purposes?

I'm not sure it's a great idea to add dead code with no upstream test coverage.
At best, it will silently regress, at worst it can simply be dropped as dead code.

llvm/lib/CodeGen/EarlyIfConversion.cpp

930–932

I'd think you want to not jam it next to existing pass, but put it into it's own place

[ThomasRaoux]

In D66190#1628864, @lebedev.ri wrote:

One more question - i can't recall if there's precedent for bundling more than one pass
into the same source file, that does not look ideal.

Looking quickly at it, I see few cases (ex: https://github.com/llvm/llvm-project/blob/master/llvm/lib/CodeGen/MachineInstrBundle.cpp) but doesn't mean it is a great idea.
The alternative would be to move the SSAIfConv helper class in a header file. Do you think this is a better solution?

Can the pass not be run standalone, does it really require some specific target?
Perhaps that can be short-circuited via some cl::opt just for testing purposes?

It can be ran standalone but unless the target has support for predicate and implements the canInsertSelect hook it won't do anything. It needs both features to do the transformation.

I'm not sure it's a great idea to add dead code with no upstream test coverage.
At best, it will silently regress, at worst it can simply be dropped as dead code.

I agree. If moving the SSAIfConv as a helper that can be reused is an acceptable solution, then I can do that and then it is easy to move the pass as is. Otherwise I'll probably copy this code for now until we have a target supporting the required features.

[ThomasRaoux]

I figured the functionality can be tested with Hexagon backend, so I added a test in Hexagon target to test the predication.

[majnemer]

llvm/lib/CodeGen/EarlyIfConversion.cpp

472–473

Update this comment for the new logic.

987

Range based for loop?

1004–1005

Ditto.

[ThomasRaoux]

llvm/lib/CodeGen/EarlyIfConversion.cpp

930–932

Do you mean move it into its own file? This reuses SSAIfConv infrastructure so unless we move it into a header file those two passes have to be in the same file.

[lebedev.ri]

llvm/lib/CodeGen/EarlyIfConversion.cpp

930–932

Yes

[ThomasRaoux]

llvm/lib/CodeGen/EarlyIfConversion.cpp

930–932

So you are suggesting moving SSAIfConv into a common header? I don't have a strong opinion about it but there are several cases of passes sharing a file and I suppose limiting exposure of the helper has its advantage.

[lebedev.ri]

llvm/lib/CodeGen/EarlyIfConversion.cpp

930–932

So you are suggesting moving SSAIfConv into a common header?

Yes.
I'm also wondering what would be the best structure for that class,
should it do both things, or should it be generalized somehow,
and have two classes that inherit form it (to cmov, to branches)
that do the actual work.

[jmolloy]

llvm/lib/CodeGen/EarlyIfConversion.cpp

296

I'm not sure we should be so concerned with this case for predication, but it's sensible to keep this in for now. Erring on the side of caution is good.

323

s/predicatable/predicable/

339

nit: General LLVM style is to elide braces around single statements.

637

nit: /*ReversePredicate=*/false (add =, remove space, for standard comment style that clang-tidy can pick up).

930–932

FWIW I don't think this should be a concern. Moving code for the sake of moving code doesn't sound particularly useful to me. I see this as analogous to MachineScheduler and PostMachineScheduler which share common infrastructure and also the same file.

I'm also wondering what would be the best structure for that class

This current structure looks fine to me. Roman, if you have suggestions for how you'd like the code to look, perhaps you could mention them explicitly? your current comment doesn't feel particularly actionable.

972

typo.

1057

For my own gratification, could you please comment (in the review, not the code) why this is required for predication but not for speculation?

[ThomasRaoux]

llvm/lib/CodeGen/EarlyIfConversion.cpp

296

Agree.

1057

It is required for both. Those pass preserve the dominator and loop analysis.

[jmolloy]

Hi Thomas,

Thanks for this! one comment but overall LGTM.

James

llvm/lib/CodeGen/EarlyIfConversion.cpp

982

This looks stateless with respect to DomTree and Removed; we should share this between the two implementations.

[ThomasRaoux]

llvm/lib/CodeGen/EarlyIfConversion.cpp

982

Fixed it by moving it to functions.

llvm/include/llvm/CodeGen/Passes.h

   /// inserting cmov instructions.
   extern char &EarlyIfConverterID;
 
+  /// EarlyIfPredicator - This pass performs if-conversion on SSA form by
+  /// predicating if/else block and insert select at the join point.
+  extern char &EarlyIfPredicatorID;
+
   /// This pass performs instruction combining using trace metrics to estimate
   /// critical-path and resource depth.
   extern char &MachineCombinerID;

llvm/include/llvm/InitializePasses.h

 void initializeEarlyCSELegacyPassPass(PassRegistry&);
 void initializeEarlyCSEMemSSALegacyPassPass(PassRegistry&);
 void initializeEarlyIfConverterPass(PassRegistry&);
+void initializeEarlyIfPredicatorPass(PassRegistry &);
 void initializeEarlyMachineLICMPass(PassRegistry&);
 void initializeEarlyTailDuplicatePass(PassRegistry&);
 void initializeEdgeBundlesPass(PassRegistry&);

llvm/lib/CodeGen/CodeGen.cpp

   initializeDetectDeadLanesPass(Registry);
   initializeDwarfEHPreparePass(Registry);
   initializeEarlyIfConverterPass(Registry);
+  initializeEarlyIfPredicatorPass(Registry);
   initializeEarlyMachineLICMPass(Registry);
   initializeEarlyTailDuplicatePass(Registry);
   initializeExpandMemCmpPassPass(Registry);

llvm/lib/CodeGen/EarlyIfConversion.cpp

 #include "llvm/CodeGen/MachineDominators.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineInstr.h"
 #include "llvm/CodeGen/MachineLoopInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/MachineTraceMetrics.h"

   /// speculated.
   bool canSpeculateInstrs(MachineBasicBlock *MBB);
 
+  /// Return true if all non-terminator instructions in MBB can be safely
+  /// predicated.
+  bool canPredicateInstrs(MachineBasicBlock *MBB);
+
+  /// Scan through instruction dependencies and update InsertAfter array.
+  /// Return false if any dependency is incompatible with if conversion.
+  bool InstrDependenciesAllowIfConv(MachineInstr *I);
+
+  /// Predicate all instructions of the basic block with current condition
+  /// except for terminators. Reverse the condition if ReversePredicate is set.
+  void PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate);
+
   /// Find a valid insertion point in Head.
   bool findInsertionPoint();
 

 
   /// canConvertIf - If the sub-CFG headed by MBB can be if-converted,
   /// initialize the internal state, and return true.
-  bool canConvertIf(MachineBasicBlock *MBB);
+  /// If predicate is set try to predicate the block otherwise try to
+  /// speculatively execute it.
+  bool canConvertIf(MachineBasicBlock *MBB, bool Predicate = false);
 
   /// convertIf - If-convert the last block passed to canConvertIf(), assuming
   /// it is possible. Add any erased blocks to RemovedBlocks.
-  void convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks);
+  void convertIf(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks,
+                 bool Predicate = false);
 };
 } // end anonymous namespace
 

     }
 
     // Check for any dependencies on Head instructions.
-    for (const MachineOperand &MO : I->operands()) {
-      if (MO.isRegMask()) {
-        LLVM_DEBUG(dbgs() << "Won't speculate regmask: " << *I);
-        return false;
-      }
-      if (!MO.isReg())
-        continue;
-      unsigned Reg = MO.getReg();
+    if (!InstrDependenciesAllowIfConv(&(*I)))
+      return false;
+  }
+  return true;
 
-      // Remember clobbered regunits.
-      if (MO.isDef() && Register::isPhysicalRegister(Reg))
-        for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
-          ClobberedRegUnits.set(*Units);
+/// Check that there is no dependencies preventing if conversion.
+///
+/// If instruction uses any values that are defined in the head basic block,
+/// the defining instructions are added to InsertAfter.
+bool SSAIfConv::InstrDependenciesAllowIfConv(MachineInstr *I) {
+  for (const MachineOperand &MO : I->operands()) {
+    if (MO.isRegMask()) {
+      LLVM_DEBUG(dbgs() << "Won't speculate regmask: " << *I);
+      return false;
+    }
+    if (!MO.isReg())
+      continue;
+    unsigned Reg = MO.getReg();
 
-      if (!MO.readsReg() || !Register::isVirtualRegister(Reg))
-        continue;
-      MachineInstr *DefMI = MRI->getVRegDef(Reg);
-      if (!DefMI || DefMI->getParent() != Head)
-        continue;
-      if (InsertAfter.insert(DefMI).second)
-        LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " depends on "
-                          << *DefMI);
-      if (DefMI->isTerminator()) {
-        LLVM_DEBUG(dbgs() << "Can't insert instructions below terminator.\n");
-        return false;
-      }
+    // Remember clobbered regunits.
+    if (MO.isDef() && Register::isPhysicalRegister(Reg))
+      for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
+        ClobberedRegUnits.set(*Units);
+
+    if (!MO.readsReg() || !Register::isVirtualRegister(Reg))
+      continue;
+    MachineInstr *DefMI = MRI->getVRegDef(Reg);
+    if (!DefMI || DefMI->getParent() != Head)
+      continue;
+    if (InsertAfter.insert(DefMI).second)
+      LLVM_DEBUG(dbgs() << printMBBReference(*I->getParent()) << " depends on "
+                        << *DefMI);
+    if (DefMI->isTerminator()) {
+      LLVM_DEBUG(dbgs() << "Can't insert instructions below terminator.\n");
+      return false;
+    }
+  }
+  return true;
+}
+
+/// canPredicateInstrs - Returns true if all the instructions in MBB can safely
+/// be predicates. The terminators are not considered.
+///
+/// If instructions use any values that are defined in the head basic block,
+/// the defining instructions are added to InsertAfter.
+///
+/// Any clobbered regunits are added to ClobberedRegUnits.
+///
+bool SSAIfConv::canPredicateInstrs(MachineBasicBlock *MBB) {
+  // Reject any live-in physregs. It's probably CPSR/EFLAGS, and very hard to
+  // get right.
+  if (!MBB->livein_empty()) {
+    LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has live-ins.\n");
+    return false;
+  }
+
+  unsigned InstrCount = 0;
+
+  // Check all instructions, except the terminators. It is assumed that
+  // terminators never have side effects or define any used register values.
+  for (MachineBasicBlock::iterator I = MBB->begin(),
+                                   E = MBB->getFirstTerminator();
+       I != E; ++I) {
+    if (I->isDebugInstr())
+      continue;
+
+    if (++InstrCount > BlockInstrLimit && !Stress) {
+      LLVM_DEBUG(dbgs() << printMBBReference(*MBB) << " has more than "
+                        << BlockInstrLimit << " instructions.\n");
+      return false;
+    }
+
+    // There shouldn't normally be any phis in a single-predecessor block.
+    if (I->isPHI()) {
+      LLVM_DEBUG(dbgs() << "Can't predicate: " << *I);
+      return false;
+    }
+
+    // Check that instruction is predicatable and that it is not already
+    // predicated.
+    if (!TII->isPredicable(*I) || TII->isPredicated(*I)) {
+      return false;
     }
+
+    // Check for any dependencies on Head instructions.
+    if (!InstrDependenciesAllowIfConv(&(*I)))
+      return false;
   }
   return true;
 }
 
+// Apply predicate to all instructions in the machine block.
+void SSAIfConv::PredicateBlock(MachineBasicBlock *MBB, bool ReversePredicate) {
+  auto Condition = Cond;
+  if (ReversePredicate) {
+    TII->reverseBranchCondition(Condition);
+  }
+  // Terminators don't need to be predicated as they will be removed.
+  for (MachineBasicBlock::iterator I = MBB->begin(),
+                                   E = MBB->getFirstTerminator();
+       I != E; ++I) {
+    if (I->isDebugInstr())
+      continue;
+    TII->PredicateInstruction(*I, Condition);
+  }
+}
 
 /// Find an insertion point in Head for the speculated instructions. The
 /// insertion point must be:

 /// canConvertIf - analyze the sub-cfg rooted in MBB, and return true if it is
 /// a potential candidate for if-conversion. Fill out the internal state.
 ///
-bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB) {
+bool SSAIfConv::canConvertIf(MachineBasicBlock *MBB, bool Predicate) {
   Head = MBB;
   TBB = FBB = Tail = nullptr;
 

 
   // This is a triangle or a diamond.
   // If Tail doesn't have any phis, there must be side effects.
-  if (Tail->empty() || !Tail->front().isPHI()) {
+  if (!Predicate && (Tail->empty() || !Tail->front().isPHI())) {
     LLVM_DEBUG(dbgs() << "No phis in tail.\n");
     return false;
   }

   // Check that the conditional instructions can be speculated.
   InsertAfter.clear();
   ClobberedRegUnits.reset();
-  if (TBB != Tail && !canSpeculateInstrs(TBB))
-    return false;
-  if (FBB != Tail && !canSpeculateInstrs(FBB))
-    return false;
+  if (Predicate) {
+    if (TBB != Tail && !canPredicateInstrs(TBB))
+      return false;
+    if (FBB != Tail && !canPredicateInstrs(FBB))
+      return false;
+  } else {
+    if (TBB != Tail && !canSpeculateInstrs(TBB))
+      return false;
+    if (FBB != Tail && !canSpeculateInstrs(FBB))
+      return false;
+  }
 
   // Try to find a valid insertion point for the speculated instructions in the
   // head basic block.

 ///
 /// Any basic blocks erased will be added to RemovedBlocks.
 ///
-void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock*> &RemovedBlocks) {
+void SSAIfConv::convertIf(SmallVectorImpl<MachineBasicBlock *> &RemovedBlocks,
+                          bool Predicate) {
   assert(Head && Tail && TBB && FBB && "Call canConvertIf first.");
 
   // Update statistics.

     ++NumDiamondsConv;
 
   // Move all instructions into Head, except for the terminators.
-  if (TBB != Tail)
+  if (TBB != Tail) {
+    if (Predicate)
+      PredicateBlock(TBB, /*ReversePredicate*/ false);
     Head->splice(InsertionPoint, TBB, TBB->begin(), TBB->getFirstTerminator());
-  if (FBB != Tail)
+  }
+  if (FBB != Tail) {
+    if (Predicate)
+      PredicateBlock(FBB, /*ReversePredicate*/ true);
     Head->splice(InsertionPoint, FBB, FBB->begin(), FBB->getFirstTerminator());
-
+  }
   // Are there extra Tail predecessors?
   bool ExtraPreds = Tail->pred_size() != 2;
   if (ExtraPreds)

   LLVM_DEBUG(dbgs() << *Head);
 }
 
-
 //===----------------------------------------------------------------------===//
 //                           EarlyIfConverter Pass
 //===----------------------------------------------------------------------===//

 
   return Changed;
 }
+
+//===----------------------------------------------------------------------===//
+//                           EarlyIfPredicator Pass
+//===----------------------------------------------------------------------===//
+
+namespace {
+class EarlyIfPredicator : public MachineFunctionPass {
+  const TargetInstrInfo *TII;
+  const TargetRegisterInfo *TRI;
+  TargetSchedModel SchedModel;
+  MachineRegisterInfo *MRI;
+  MachineDominatorTree *DomTree;
+  MachineLoopInfo *Loops;
+  SSAIfConv IfConv;
+
+public:
+  static char ID;
+  EarlyIfPredicator() : MachineFunctionPass(ID) {}
+  void getAnalysisUsage(AnalysisUsage &AU) const override;
+  bool runOnMachineFunction(MachineFunction &MF) override;
+  StringRef getPassName() const override {
+    return "Early If-predicator";
+  }
+
+protected:
+  bool tryConvertIf(MachineBasicBlock *);
+  void updateDomTree(ArrayRef<MachineBasicBlock *> Removed);
+  void updateLoops(ArrayRef<MachineBasicBlock *> Removed);
+  bool shouldConvertIf();
+};
+} // end anonymous namespace
+
+#undef DEBUG_TYPE
+#define DEBUG_TYPE "early-if-predicator"
+
+char EarlyIfPredicator::ID = 0;
+char &llvm::EarlyIfPredicatorID = EarlyIfPredicator::ID;
+
+INITIALIZE_PASS_BEGIN(EarlyIfPredicator, DEBUG_TYPE,
+                      "Early If Predicator", false, false)
+INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
+INITIALIZE_PASS_END(EarlyIfPredicator, DEBUG_TYPE,
+                    "Early If Predicatir", false, false)
+
+void EarlyIfPredicator::getAnalysisUsage(AnalysisUsage &AU) const {
+  AU.addRequired<MachineDominatorTree>();
+  AU.addPreserved<MachineDominatorTree>();
+  AU.addRequired<MachineLoopInfo>();
+  AU.addPreserved<MachineLoopInfo>();
+  MachineFunctionPass::getAnalysisUsage(AU);
+}
+
+/// Update the dominator tree after if-conversion erased some blocks.
+void EarlyIfPredicator::updateDomTree(ArrayRef<MachineBasicBlock *> Removed) {
+  // convertIf can remove TBB, FBB, and Tail can be merged into Head.
+  // TBB and FBB should not dominate any blocks.
+  // Tail children should be transferred to Head.
+  MachineDomTreeNode *HeadNode = DomTree->getNode(IfConv.Head);
+  for (unsigned i = 0, e = Removed.size(); i != e; ++i) {
+    MachineDomTreeNode *Node = DomTree->getNode(Removed[i]);
+    assert(Node != HeadNode && "Cannot erase the head node");
+    while (Node->getNumChildren()) {
+      assert(Node->getBlock() == IfConv.Tail && "Unexpected children");
+      DomTree->changeImmediateDominator(Node->getChildren().back(), HeadNode);
+    }
+    DomTree->eraseNode(Removed[i]);
+  }
+}
+
+/// Update LoopInfo after if-conversion.
+void EarlyIfPredicator::updateLoops(ArrayRef<MachineBasicBlock *> Removed) {
+  if (!Loops)
+    return;
+  // If-conversion doesn't change loop structure, and it doesn't mess with back
+  // edges, so updating LoopInfo is simply removing the dead blocks.
+  for (unsigned i = 0, e = Removed.size(); i != e; ++i)
+    Loops->removeBlock(Removed[i]);
+}
+
+/// Apply the target heuristic to decide if the transformation is profitable.
+bool EarlyIfPredicator::shouldConvertIf() {
+  if (IfConv.isTriangle()) {
+    MachineBasicBlock &IfBlock =
+        (IfConv.TBB == IfConv.Tail) ? *IfConv.FBB : *IfConv.TBB;
+
+    unsigned ExtraPredCost = 0;
+    unsigned Cycles = 0;
+    for (MachineInstr &I : IfBlock) {
+      unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
+      if (NumCycles > 1)
+        Cycles += NumCycles - 1;
+      ExtraPredCost += TII->getPredicationCost(I);
+    }
+
+    return TII->isProfitableToIfCvt(IfBlock, Cycles, ExtraPredCost,
+                                    BranchProbability::getUnknown());
+  }
+  unsigned TExtra = 0;
+  unsigned FExtra = 0;
+  unsigned TCycle = 0;
+  unsigned FCycle = 0;
+  for (MachineInstr &I : *IfConv.TBB) {
+    unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
+    if (NumCycles > 1)
+      TCycle += NumCycles - 1;
+    TExtra += TII->getPredicationCost(I);
+  }
+  for (MachineInstr &I : *IfConv.FBB) {
+    unsigned NumCycles = SchedModel.computeInstrLatency(&I, false);
+    if (NumCycles > 1)
+      FCycle += NumCycles - 1;
+    FExtra += TII->getPredicationCost(I);
+  }
+  return TII->isProfitableToIfCvt(*IfConv.TBB, TCycle, TExtra, *IfConv.FBB,
+                                  FCycle, FExtra,
+                                  BranchProbability::getUnknown());
+}
+
+/// Attempt repeated if-conversion on MBB, return true if successful.
+///
+bool EarlyIfPredicator::tryConvertIf(MachineBasicBlock *MBB) {
+  bool Changed = false;
+  while (IfConv.canConvertIf(MBB, /*Predicate*/ true) && shouldConvertIf()) {
+    // If-convert MBB and update analyses.
+    SmallVector<MachineBasicBlock *, 4> RemovedBlocks;
+    IfConv.convertIf(RemovedBlocks, /*Predicate*/ true);
+    Changed = true;
+    updateDomTree(RemovedBlocks);
+    updateLoops(RemovedBlocks);
+  }
+  return Changed;
+}
+
+bool EarlyIfPredicator::runOnMachineFunction(MachineFunction &MF) {
+  LLVM_DEBUG(dbgs() << "********** EARLY IF-PREDICATOR **********\n"
+                    << "********** Function: " << MF.getName() << '\n');
+  if (skipFunction(MF.getFunction()))
+    return false;
+
+  const TargetSubtargetInfo &STI = MF.getSubtarget();
+  TII = STI.getInstrInfo();
+  TRI = STI.getRegisterInfo();
+  MRI = &MF.getRegInfo();
+  SchedModel.init(&STI);
+  DomTree = &getAnalysis<MachineDominatorTree>();
+  Loops = getAnalysisIfAvailable<MachineLoopInfo>();
+
+  bool Changed = false;
+  IfConv.runOnMachineFunction(MF);
+
+  // Visit blocks in dominator tree post-order. The post-order enables nested
+  // if-conversion in a single pass. The tryConvertIf() function may erase
+  // blocks, but only blocks dominated by the head block. This makes it safe to
+  // update the dominator tree while the post-order iterator is still active.
+  for (auto DomNode : post_order(DomTree))
+    if (tryConvertIf(DomNode->getBlock()))
+      Changed = true;
+
+  return Changed;
+}