MachineLoopInfo: add methods findLoopPreheader and getExitingBlock

[SjoerdMeijer]

Summary

This adds two new utility functions findLoopPreheader and getExitingBlock to MachineLoopInfo.
These functions are refactored and taken from the Hexagon target as they are target independent.

[kparzysz]

lib/CodeGen/MachineLoopInfo.cpp

84

This part is finding a block that can enter the loop header, but may also go somewhere else. On Hexagon we can use it to put the hardware loop setup here, since it can be safely speculated. Code that cannot be speculated cannot be placed here.
Maybe you could add a parameter to let the caller decide whether they want just the regular preheader, or a speculative one.

On a different note, have you checked how many potential users for this are there? Is there a demand for this?

lib/Target/Hexagon/HexagonHardwareLoops.cpp

1803–1804

The lines 1824-1825 must be present here. This function needs to return a regular preheader, and if the SpecPreheader is specified, the speculative one, if it can find it.

[SjoerdMeijer]

lib/CodeGen/MachineLoopInfo.cpp

84

Thanks for reviewing! I will start making these changes.

About users for this: what I actually want is to have the "getLoopTripCount" available on the MachineLoop level, and the refactoring in this patch is the first exercise or groundwork to achieve that. It looks like you have done most of the hard work already in the Hexagon backend; looking at the getLoopTripCount implementation, there is actually very little Hexagon specific, only one place checks for Hexagon add instruction opcodes (which I think is not hard to nicely hide in a target hook). I think these MachineLoop utility functions such as getLoopTripCount, findLoopPreheader, getExitBlocks, etc., are mostly target independent and really nice to have (and I would definitely like to use them). In fact, for implementing more loop transformations on Machine blocks, these functions are required...

[SjoerdMeijer]

I've added a second argument SpeculativePreheader to function findLoopPreheader. This allowed more refactoring in the Hexagon backend as we can don't need a local implementation of that function anymore, but just a call to the one in MachineLoopInfo.

[bcahoon]

I think it's a good idea to try to move some of the code in the Hexagon hardware loop pass so that it can be reused. The getExitingBlock() function in HexagonHardwareLoops.cpp is probably poorly named since it's doing something different than the existing function that is in MachineLoop. If the function is moved, it seems to fit better in the MachineLoop class vs the MachineLoopInfo class.

The code in the getExitingBlock() function in HexagonHardwareLoops.cpp is attempting to enable the hardware loop pass to work on two special types of loops. In one case, we would like to generate a hardware loop even if there are multiple exiting blocks. If that's the case, then we use the latch block as the exiting block (if the latch block is one of the exiting block). It's ok to exit early from a hardware loop. In the second case, we would like to generate a hardware loop if there is a single exit, but the latch is not the exit. This case occurs, for example, when a critical edge is added to the loop (see the hwloop-crit-edge.ll as an example).

I just wanted to provide a little background as to how the hardware loop pass uses the function. Initially, I believe we used the latch block in all the cases where getExitingBlock() is now called. But, that caused problems when attempting to generate a hardware loop for the critical edge case.

[SjoerdMeijer]

Hi, thanks a lot for the info, that is very useful, and I am glad you like the idea of moving some of the code! I really think it is going to be useful.

I will take your feedback on board and create a new patch early next week for factoring out these 2 functions (as a first exercise). Then I will see if can take a slightly bigger chunk in one go to get the LoopTripCount function factored out.

Cheers,
Sjoerd.

[SjoerdMeijer]

I've renamed getExitingBlocks to findLoopControlBlock and moved it from class MachineLoopInfo to MachineLoop.

[bcahoon]

The changes look good to me. The only nitpick is that you should run clang-format on your changes.

[SjoerdMeijer]

Thanks. I've run clang-format.

[SjoerdMeijer]

is it okay to commit?

[SjoerdMeijer]

Rereading your comment, I missed the LGTM, so I wil go ahead and commit.
Thanks a lot for reviewing!

include/llvm/CodeGen/MachineLoopInfo.h

public:
   /// contains the header.
   MachineBasicBlock *getTopBlock();
 
   /// Return the "bottom" block in the loop, which is the last block in the
   /// linear layout, ignoring any parts of the loop not contiguous with the part
   /// that contains the header.
   MachineBasicBlock *getBottomBlock();
 
+  /// \brief Find the block that contains the loop control variable and the
+  /// loop test. This will return the latch block if it's one of the exiting
+  /// blocks. Otherwise, return the exiting block. Return 'null' when
+  /// multiple exiting blocks are present.
+  MachineBasicBlock *findLoopControlBlock();
+
   void dump() const;
 
 private:
   friend class LoopInfoBase<MachineBasicBlock, MachineLoop>;
   explicit MachineLoop(MachineBasicBlock *MBB)
     : LoopBase<MachineBasicBlock, MachineLoop>(MBB) {}
 };
 
public:
   static char ID; // Pass identification, replacement for typeid
 
   MachineLoopInfo() : MachineFunctionPass(ID) {
     initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry());
   }
 
   LoopInfoBase<MachineBasicBlock, MachineLoop>& getBase() { return LI; }
 
+  /// \brief Find the block that either is the loop preheader, or could
+  /// speculatively be used as the preheader. This is e.g. useful to place
+  /// loop setup code. Code that cannot be speculated should not be placed
+  /// here. SpeculativePreheader is controlling whether it also tries to
+  /// find the speculative preheader if the regular preheader is not present.
+  MachineBasicBlock *findLoopPreheader(MachineLoop *L,
+                                       bool SpeculativePreheader = false) const;
+
   /// The iterator interface to the top-level loops in the current function.
   typedef LoopInfoBase<MachineBasicBlock, MachineLoop>::iterator iterator;
   inline iterator begin() const { return LI.begin(); }
   inline iterator end() const { return LI.end(); }
   bool empty() const { return LI.empty(); }
 
   /// Return the innermost loop that BB lives in. If a basic block is in no loop
   /// (for example the entry node), null is returned.

lib/CodeGen/MachineLoopInfo.cpp

while (contains(NextMBB)) {
       if (BotMBB == &*std::next(BotMBB->getIterator()))
         break;
       NextMBB = &*std::next(BotMBB->getIterator());
     }
   }
   return BotMBB;
 }
 
+MachineBasicBlock *MachineLoop::findLoopControlBlock() {
+  if (MachineBasicBlock *Latch = getLoopLatch()) {
+    if (isLoopExiting(Latch))
+      return Latch;
+    else
+      return getExitingBlock();
+  }
+  return nullptr;
+}
+
+MachineBasicBlock *
+MachineLoopInfo::findLoopPreheader(MachineLoop *L,
+                                   bool SpeculativePreheader) const {
+  if (MachineBasicBlock *PB = L->getLoopPreheader())
+    return PB;
+
+  if (!SpeculativePreheader)
+    return nullptr;
+
+  MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
+  if (HB->pred_size() != 2 || HB->hasAddressTaken())
+    return nullptr;
+  // Find the predecessor of the header that is not the latch block.
+  MachineBasicBlock *Preheader = nullptr;
+  for (MachineBasicBlock *P : HB->predecessors()) {
+    if (P == LB)
+      continue;
+    // Sanity.
+    if (Preheader)
+      return nullptr;
+    Preheader = P;
+  }
+
+  // Check if the preheader candidate is a successor of any other loop
+  // headers. We want to avoid having two loop setups in the same block.
+  for (MachineBasicBlock *S : Preheader->successors()) {
+    if (S == HB)
+      continue;
+    MachineLoop *T = getLoopFor(S);
+    if (T && T->getHeader() == S)
+      return nullptr;
+  }
+  return Preheader;
+}
+
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 LLVM_DUMP_METHOD void MachineLoop::dump() const {
   print(dbgs());
 }
 #endif

lib/Target/Hexagon/HexagonHardwareLoops.cpp

private:
     ///
     /// Return true if the loop's flow is the desired one (i.e. it's
     /// either been fixed, or no fixing was necessary).
     /// Otherwise, return false.  This can happen if the induction variable
     /// couldn't be identified, or if the value in the latch's comparison
     /// cannot be adjusted to reflect the post-bump value.
     bool fixupInductionVariable(MachineLoop *L);
 
-    /// \brief Find the block that either is the loop preheader, or could
-    /// speculatively be used as the preheader.
-    MachineBasicBlock *findLoopPreheader(MachineLoop *L) const;
-
     /// \brief Given a loop, if it does not have a preheader, create one.
     /// Return the block that is the preheader.
     MachineBasicBlock *createPreheaderForLoop(MachineLoop *L);
   };
 
   char HexagonHardwareLoops::ID = 0;
 #ifndef NDEBUG
   int HexagonHardwareLoops::Counter = 0;
if (!L->getParentLoop()) {
       bool L0Used = false;
       bool L1Used = false;
       Changed |= convertToHardwareLoop(L, L0Used, L1Used);
     }
 
   return Changed;
 }
 
-/// \brief Return the latch block if it's one of the exiting blocks. Otherwise,
-/// return the exiting block. Return 'null' when multiple exiting blocks are
-/// present.
-static MachineBasicBlock* getExitingBlock(MachineLoop *L) {
-  if (MachineBasicBlock *Latch = L->getLoopLatch()) {
-    if (L->isLoopExiting(Latch))
-      return Latch;
-    else
-      return L->getExitingBlock();
-  }
-  return nullptr;
-}
-
 bool HexagonHardwareLoops::findInductionRegister(MachineLoop *L,
                                                  unsigned &Reg,
                                                  int64_t &IVBump,
                                                  MachineInstr *&IVOp
                                                  ) const {
   MachineBasicBlock *Header = L->getHeader();
-  MachineBasicBlock *Preheader = findLoopPreheader(L);
+  MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
   MachineBasicBlock *Latch = L->getLoopLatch();
-  MachineBasicBlock *ExitingBlock = getExitingBlock(L);
+  MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
   if (!Header || !Preheader || !Latch || !ExitingBlock)
     return false;
 
   // This pair represents an induction register together with an immediate
   // value that will be added to it in each loop iteration.
   typedef std::pair<unsigned,int64_t> RegisterBump;
 
   // Mapping:  R.next -> (R, bump), where R, R.next and bump are derived
if (L->contains(Backedge))
       return nullptr;
     std::swap(Incoming, Backedge);
   } else if (!L->contains(Backedge))
     return nullptr;
 
   // Look for the cmp instruction to determine if we can get a useful trip
   // count.  The trip count can be either a register or an immediate.  The
   // location of the value depends upon the type (reg or imm).
-  MachineBasicBlock *ExitingBlock = getExitingBlock(L);
+  MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
   if (!ExitingBlock)
     return nullptr;
 
   unsigned IVReg = 0;
   int64_t IVBump = 0;
   MachineInstr *IVOp;
   bool FoundIV = findInductionRegister(L, IVReg, IVBump, IVOp);
   if (!FoundIV)
     return nullptr;
 
-  MachineBasicBlock *Preheader = findLoopPreheader(L);
+  MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
 
   MachineOperand *InitialValue = nullptr;
   MachineInstr *IV_Phi = MRI->getVRegDef(IVReg);
   MachineBasicBlock *Latch = L->getLoopLatch();
   for (unsigned i = 1, n = IV_Phi->getNumOperands(); i < n; i += 2) {
     MachineBasicBlock *MBB = IV_Phi->getOperand(i+1).getMBB();
     if (MBB == Preheader)
       InitialValue = &IV_Phi->getOperand(i);
CountValue *HexagonHardwareLoops::computeCount(MachineLoop *Loop,
   // iteration count may not be available.  If it is not, insert
   // a computation of it into the preheader.
 
   // If the induction variable bump is not a power of 2, quit.
   // Othwerise we'd need a general integer division.
   if (!isPowerOf2_64(std::abs(IVBump)))
     return nullptr;
 
-  MachineBasicBlock *PH = findLoopPreheader(Loop);
+  MachineBasicBlock *PH = MLI->findLoopPreheader(Loop, SpecPreheader);
   assert (PH && "Should have a preheader by now");
   MachineBasicBlock::iterator InsertPos = PH->getFirstTerminator();
   DebugLoc DL;
   if (InsertPos != PH->end())
     DL = InsertPos->getDebugLoc();
 
   // If Start is an immediate and End is a register, the trip count
   // will be "reg - imm".  Hexagon's "subtract immediate" instruction
if (Limit >= 0) {
     Counter++;
   }
 #endif
 
   // Does the loop contain any invalid instructions?
   if (containsInvalidInstruction(L, IsInnerHWLoop))
     return false;
 
-  MachineBasicBlock *LastMBB = getExitingBlock(L);
+  MachineBasicBlock *LastMBB = L->findLoopControlBlock();
   // Don't generate hw loop if the loop has more than one exit.
   if (!LastMBB)
     return false;
 
   MachineBasicBlock::iterator LastI = LastMBB->getFirstTerminator();
   if (LastI == LastMBB->end())
     return false;
 
   // Is the induction variable bump feeding the latch condition?
   if (!fixupInductionVariable(L))
     return false;
 
   // Ensure the loop has a preheader: the loop instruction will be
   // placed there.
-  MachineBasicBlock *Preheader = findLoopPreheader(L);
+  MachineBasicBlock *Preheader = MLI->findLoopPreheader(L, SpecPreheader);
   if (!Preheader) {
     Preheader = createPreheaderForLoop(L);
     if (!Preheader)
       return false;
   }
 
   MachineBasicBlock::iterator InsertPos = Preheader->getFirstTerminator();
 
if (TripCount->isReg()) {
     MachineInstr *TCDef = MRI->getVRegDef(TripCount->getReg());
     MachineBasicBlock *BBDef = TCDef->getParent();
     if (!MDT->dominates(BBDef, Preheader))
       return false;
   }
 
   // Determine the loop start.
   MachineBasicBlock *TopBlock = L->getTopBlock();
-  MachineBasicBlock *ExitingBlock = getExitingBlock(L);
+  MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
   MachineBasicBlock *LoopStart = 0;
   if (ExitingBlock !=  L->getLoopLatch()) {
     MachineBasicBlock *TB = 0, *FB = 0;
     SmallVector<MachineOperand, 2> Cond;
 
     if (TII->analyzeBranch(*ExitingBlock, TB, FB, Cond, false))
       return false;
 
if (CmpOpc == Hexagon::A4_cmpbgti)
     return isInt<8>(Imm);
   // The rest of the comparison-with-immediate instructions are extendable.
   return true;
 }
 
 bool HexagonHardwareLoops::fixupInductionVariable(MachineLoop *L) {
   MachineBasicBlock *Header = L->getHeader();
   MachineBasicBlock *Latch = L->getLoopLatch();
-  MachineBasicBlock *ExitingBlock = getExitingBlock(L);
+  MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
 
   if (!(Header && Latch && ExitingBlock))
     return false;
 
   // These data structures follow the same concept as the corresponding
   // ones in findInductionRegister (where some comments are).
   typedef std::pair<unsigned,int64_t> RegisterBump;
   typedef std::pair<unsigned,RegisterBump> RegisterInduction;
if (CmpRegs.count(RB.first)) {
           return true;
         }
       }
     }
   }
 
   return false;
 }
 
-/// Find a preaheader of the given loop.
-MachineBasicBlock *HexagonHardwareLoops::findLoopPreheader(MachineLoop *L)
-      const {
-  if (MachineBasicBlock *PB = L->getLoopPreheader())
-    return PB;
-  if (!SpecPreheader)
-    return nullptr;
-  MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
-  if (HB->pred_size() != 2 || HB->hasAddressTaken())
-    return nullptr;
-  // Find the predecessor of the header that is not the latch block.
-  MachineBasicBlock *Preheader = nullptr;
-  for (MachineBasicBlock *P : HB->predecessors()) {
-    if (P == LB)
-      continue;
-    // Sanity.
-    if (Preheader)
-      return nullptr;
-    Preheader = P;
-  }
-
-  // Check if the preheader candidate is a successor of any other loop
-  // headers. We want to avoid having two loop setups in the same block.
-  for (MachineBasicBlock *S : Preheader->successors()) {
-    if (S == HB)
-      continue;
-    MachineLoop *T = MLI->getLoopFor(S);
-    if (T && T->getHeader() == S)
-      return nullptr;
-  }
-  return Preheader;
-}
-
-
 /// createPreheaderForLoop - Create a preheader for a given loop.
 MachineBasicBlock *HexagonHardwareLoops::createPreheaderForLoop(
       MachineLoop *L) {
-  if (MachineBasicBlock *TmpPH = findLoopPreheader(L))
+  if (MachineBasicBlock *TmpPH = MLI->findLoopPreheader(L, SpecPreheader))
     return TmpPH;
   if (!HWCreatePreheader)
     return nullptr;
 
   MachineBasicBlock *Header = L->getHeader();
   MachineBasicBlock *Latch = L->getLoopLatch();
-  MachineBasicBlock *ExitingBlock = getExitingBlock(L);
+  MachineBasicBlock *ExitingBlock = L->findLoopControlBlock();
   MachineFunction *MF = Header->getParent();
   DebugLoc DL;
 
 #ifndef NDEBUG
   if ((PHFn != "") && (PHFn != MF->getName()))
     return nullptr;
 #endif