[codegen] Add generic functions to skip debug values.

[fhahn]

Summary

This commits moves skipDebugInstructionsForward and
skipDebugInstructionsBackward from lib/CodeGen/IfConversion.cpp
to include/llvm/CodeGen/MachineBasicBlock.h and updates
some codgen files to use them.

This refactoring was suggested in https://reviews.llvm.org/D27688
and I thought it's best to do the refactoring in a separate
review, but I could also put both changes in a single review
if that's preferred.

Also, the names for the functions aren't the snappiest and
I would be happy to rename them if anybody has suggestions.

[aprantl]

Small formatting nit, but otherwise this looks much better!

include/llvm/CodeGen/MachineBasicBlock.h

810

Nitpick: we use \param instead of @param

[aprantl]

lib/CodeGen/RegisterPressure.cpp

819

--CurrPos; ?

[MatzeB]

Thanks for doing the refactoring. I have some comments on the API:

include/llvm/CodeGen/MachineBasicBlock.h

814

• Iterators are usually small enough to be better passed by value (so IterT End instead of const IterT &End).
• APIs modifying their "parameters" through references are often unintuitive in C++. How about changing this to: IterT skipDebugInstructionsForward(IterT Begin, IterT End); that returns the new iterator position after skipping?
• Given the iterator type is a template that I guess is only intended to be used with MachineBasicBlock::{const_}?{instr_}?iterator maybe listing those 4 possibiltites would help understanding the function.

[iteratee]

include/llvm/CodeGen/MachineBasicBlock.h

830

This is subtly different from the code you're replacing. Specifically if, It == Begin, and Begin is not a debug value, this function returns false, where shrinkInclusiveRange returns true. You need to early return if It == Begin because the resulting range is now empty.

[MatzeB]

include/llvm/CodeGen/MachineBasicBlock.h

810

Not wanting to be too nitpicky or criticize for actually writing good documentation, but I can't stop thinking that some cases where a comment reads like \param It The iterator to use is not that far off from a comment like int i; // an integer variable, which doesn't really add much value. So I often simply leave out the \param stuff when things are sufficiently clearly explained in the description part.

[iteratee]

I have a counter CL to simplify the skipping in a different way. Can you look at that before you submit this?

[iteratee]

Please take a look at https://reviews.llvm.org/D27792 I think we can make this even more simple.

[fhahn]

Thank you for the helpful comments. I hope I addressed them all.

[fhahn]

@iteratee I think the review you posted indeed a nice simplification in IfConversion.cpp. I think it would make sense to get your change in after this one goes in. What do you think?

include/llvm/CodeGen/MachineBasicBlock.h

814

Done. Is the reference to the iterators in the comment along the lines you meant?

830

I've changed the function to return the new iterator and the calling functions must interpret the returned iterator.

[MatzeB]

LGTM.

lib/CodeGen/BranchFolding.cpp

1831–1836

extra space before the comma.

[fhahn]

style nitpick

include/llvm/CodeGen/MachineBasicBlock.h

MachineBasicBlock::iterator begin() {
     return B == MBB.end() ? MBB.begin() : std::next(B);
   }
   MachineBasicBlock::iterator end() { return E; }
   bool empty() { return begin() == end(); }
 
   MachineBasicBlock::iterator getInitial() { return I; }
 };
 
+/// Increment \p It until it points to a non-debug instruction or to \p End
+/// and return the resulting iterator. This function should only be used
+/// MachineBasicBlock::{iterator, const_iterator, instr_iterator,
+/// const_instr_iterator} and the respective reverse iterators.
+template<typename IterT>
+inline IterT skipDebugInstructionsForward(IterT It, IterT End) {
+  while (It != End && It->isDebugValue())
+    It++;
+  return It;
+}
+
+/// Decrement \p It until it points to a non-debug instruction or to \p Begin
+/// and return the resulting iterator. This function should only be used
+/// MachineBasicBlock::{iterator, const_iterator, instr_iterator,
+/// const_instr_iterator} and the respective reverse iterators.
+template<class IterT>
+inline IterT skipDebugInstructionsBackward(IterT It, IterT Begin) {
+  while (It != Begin && It->isDebugValue())
+    It--;
+  return It;
+}
+
 } // End llvm namespace
 
 #endif

lib/CodeGen/BranchFolding.cpp

MachineBasicBlock::iterator findHoistingInsertPosAndDeps(MachineBasicBlock *MBB,
 
   if (Uses.empty())
     return Loc;
   if (Loc == MBB->begin())
     return MBB->end();
 
   // The terminator is probably a conditional branch, try not to separate the
   // branch from condition setting instruction.
-  MachineBasicBlock::iterator PI = Loc;
-  --PI;
-  while (PI != MBB->begin() && PI->isDebugValue())
-    --PI;
+  MachineBasicBlock::iterator PI =
+    skipDebugInstructionsBackward(std::prev(Loc), MBB->begin());
 
   bool IsDef = false;
   for (const MachineOperand &MO : PI->operands()) {
     // If PI has a regmask operand, it is probably a call. Separate away.
     if (MO.isRegMask())
       return Loc;
     if (!MO.isReg() || MO.isUse())
       continue;
bool BranchFolder::HoistCommonCodeInSuccs(MachineBasicBlock *MBB) {
   SmallVector<unsigned, 4> LocalDefs;
   SmallSet<unsigned, 4> LocalDefsSet;
   MachineBasicBlock::iterator TIB = TBB->begin();
   MachineBasicBlock::iterator FIB = FBB->begin();
   MachineBasicBlock::iterator TIE = TBB->end();
   MachineBasicBlock::iterator FIE = FBB->end();
   while (TIB != TIE && FIB != FIE) {
     // Skip dbg_value instructions. These do not count.
-    if (TIB->isDebugValue()) {
-      while (TIB != TIE && TIB->isDebugValue())
-        ++TIB;
-      if (TIB == TIE)
-        break;
-    }
-    if (FIB->isDebugValue()) {
-      while (FIB != FIE && FIB->isDebugValue())
-        ++FIB;
-      if (FIB == FIE)
-        break;
-    }
+    TIB = skipDebugInstructionsForward(TIB, TIE);
+    FIB = skipDebugInstructionsForward(FIB, FIE);
+    if (TIB == TIE || FIB == FIE)
+
     if (!TIB->isIdenticalTo(*FIB, MachineInstr::CheckKillDead))
       break;
 
     if (TII->isPredicated(*TIB))
       // Hard to reason about register liveness with predicated instruction.
       break;
 
     bool IsSafe = true;
     for (MachineOperand &MO : TIB->operands()) {

lib/CodeGen/IfConversion.cpp

if (!TExit && blockAlwaysFallThrough(TrueBBI)) {
     MachineFunction::iterator I = TrueBBI.BB->getIterator();
     if (++I == TrueBBI.BB->getParent()->end())
       return false;
     TExit = &*I;
   }
   return TExit && TExit == FalseBBI.BB;
 }
 
-/// Increment \p It until it points to a non-debug instruction or to \p End.
-/// @param It Iterator to increment
-/// @param End Iterator that points to end. Will be compared to It
-/// @returns true if It == End, false otherwise.
-static inline bool skipDebugInstructionsForward(
-    MachineBasicBlock::iterator &It,
-    MachineBasicBlock::iterator &End) {
-  while (It != End && It->isDebugValue())
-    It++;
-  return It == End;
-}
-
 /// Shrink the provided inclusive range by one instruction.
 /// If the range was one instruction (\p It == \p Begin), It is not modified,
 /// but \p Empty is set to true.
 static inline void shrinkInclusiveRange(
     MachineBasicBlock::iterator &Begin,
     MachineBasicBlock::iterator &It,
     bool &Empty) {
   if (It == Begin)
     Empty = true;
   else
     It--;
 }
 
-/// Decrement \p It until it points to a non-debug instruction or the range is
-/// empty.
-/// @param It Iterator to decrement.
-/// @param Begin Iterator that points to beginning. Will be compared to It
-/// @param Empty Set to true if the resulting range is Empty
-/// @returns the value of Empty as a convenience.
-static inline bool skipDebugInstructionsBackward(
-    MachineBasicBlock::iterator &Begin,
-    MachineBasicBlock::iterator &It,
-    bool &Empty) {
-  while (!Empty && It->isDebugValue())
-    shrinkInclusiveRange(Begin, It, Empty);
-  return Empty;
-}
-
 /// Count duplicated instructions and move the iterators to show where they
 /// are.
 /// @param TIB True Iterator Begin
 /// @param FIB False Iterator Begin
 /// These two iterators initially point to the first instruction of the two
 /// blocks, and finally point to the first non-shared instruction.
 /// @param TIE True Iterator End
 /// @param FIE False Iterator End
bool IfConverter::CountDuplicatedInstructions(
     MachineBasicBlock::iterator &TIE,
     MachineBasicBlock::iterator &FIE,
     unsigned &Dups1, unsigned &Dups2,
     MachineBasicBlock &TBB, MachineBasicBlock &FBB,
     bool SkipUnconditionalBranches) const {
 
   while (TIB != TIE && FIB != FIE) {
     // Skip dbg_value instructions. These do not count.
-    if(skipDebugInstructionsForward(TIB, TIE))
+    TIB = skipDebugInstructionsForward(TIB, TIE);
+    if(TIB == TIE)
       break;
-    if(skipDebugInstructionsForward(FIB, FIE))
+    FIB = skipDebugInstructionsForward(FIB, FIE);
+    if(FIB == FIE)
       break;
     if (!TIB->isIdenticalTo(*FIB))
       break;
     // A pred-clobbering instruction in the shared portion prevents
     // if-conversion.
     std::vector<MachineOperand> PredDefs;
     if (TII->DefinesPredicate(*TIB, PredDefs))
       return false;
bool IfConverter::CountDuplicatedInstructions(
   // If Dups1 includes all of a block, then don't count duplicate
   // instructions at the end of the blocks.
   if (TEmpty || FEmpty)
     return true;
 
   // Count duplicate instructions at the ends of the blocks.
   while (!TEmpty && !FEmpty) {
     // Skip dbg_value instructions. These do not count.
-    if (skipDebugInstructionsBackward(TIB, TIE, TEmpty))
-      break;
-    if (skipDebugInstructionsBackward(FIB, FIE, FEmpty))
+    TIE = skipDebugInstructionsBackward(TIE, TIB);
+    FIE = skipDebugInstructionsBackward(FIE, FIB);
+    TEmpty = TIE == TIB && TIE->isDebugValue();
+    FEmpty = FIE == FIB && FIE->isDebugValue();
+    if (TEmpty || FEmpty)
       break;
     if (!TIE->isIdenticalTo(*FIE))
       break;
     // We have to verify that any branch instructions are the same, and then we
     // don't count them toward the # of duplicate instructions.
     if (!TIE->isBranch())
       ++Dups2;
     shrinkInclusiveRange(TIB, TIE, TEmpty);
static void verifySameBranchInstructions(
     MachineBasicBlock *MBB1,
     MachineBasicBlock *MBB2) {
   MachineBasicBlock::iterator B1 = MBB1->begin();
   MachineBasicBlock::iterator B2 = MBB2->begin();
   MachineBasicBlock::iterator E1 = std::prev(MBB1->end());
   MachineBasicBlock::iterator E2 = std::prev(MBB2->end());
   bool Empty1 = false, Empty2 = false;
   while (!Empty1 && !Empty2) {
-    skipDebugInstructionsBackward(B1, E1, Empty1);
-    skipDebugInstructionsBackward(B2, E2, Empty2);
+    E1 = skipDebugInstructionsBackward(E1, B1);
+    E2 = skipDebugInstructionsBackward(E2, B2);
+    Empty1 = E1 == B1 && E1->isDebugValue();
+    Empty2 = E2 == B2 && E2->isDebugValue();
+
     if (Empty1 && Empty2)
       break;
 
     if (Empty1) {
       assert(!E2->isBranch() && "Branch mis-match, one block is empty.");
       break;
     }
     if (Empty2) {

lib/CodeGen/MachineBasicBlock.cpp

while (I != B && ((--I)->isTerminator() || I->isDebugValue()))
     ; /*noop */
   while (I != E && !I->isTerminator())
     ++I;
   return I;
 }
 
 MachineBasicBlock::iterator MachineBasicBlock::getFirstNonDebugInstr() {
   // Skip over begin-of-block dbg_value instructions.
-  iterator I = begin(), E = end();
-  while (I != E && I->isDebugValue())
-    ++I;
-  return I;
+  return skipDebugInstructionsForward(begin(), end());
 }
 
 MachineBasicBlock::iterator MachineBasicBlock::getLastNonDebugInstr() {
   // Skip over end-of-block dbg_value instructions.
   instr_iterator B = instr_begin(), I = instr_end();
   while (I != B) {
     --I;
     // Return instruction that starts a bundle.
if (Changed)
     normalizeSuccProbs();
   return Changed;
 }
 
 /// Find the next valid DebugLoc starting at MBBI, skipping any DBG_VALUE
 /// instructions.  Return UnknownLoc if there is none.
 DebugLoc
 MachineBasicBlock::findDebugLoc(instr_iterator MBBI) {
-  DebugLoc DL;
-  instr_iterator E = instr_end();
-  if (MBBI == E)
-    return DL;
-
   // Skip debug declarations, we don't want a DebugLoc from them.
-  while (MBBI != E && MBBI->isDebugValue())
-    MBBI++;
-  if (MBBI != E)
-    DL = MBBI->getDebugLoc();
-  return DL;
+  MBBI = skipDebugInstructionsForward(MBBI, instr_end());
+  if (MBBI != instr_end())
+    return MBBI->getDebugLoc();
+  return {};
 }
 
 /// Return probability of the edge from this block to MBB.
 BranchProbability
 MachineBasicBlock::getSuccProbability(const_succ_iterator Succ) const {
   if (Probs.empty())
     return BranchProbability(1, succ_size());
 

lib/CodeGen/MachineCSE.cpp

 
 bool
 MachineCSE::isPhysDefTriviallyDead(unsigned Reg,
                                    MachineBasicBlock::const_iterator I,
                                    MachineBasicBlock::const_iterator E) const {
   unsigned LookAheadLeft = LookAheadLimit;
   while (LookAheadLeft) {
     // Skip over dbg_value's.
-    while (I != E && I->isDebugValue())
-      ++I;
+    I = skipDebugInstructionsForward(I, E);
 
     if (I == E)
       // Reached end of block, register is obviously dead.
       return true;
 
     bool SeenDef = false;
     for (const MachineOperand &MO : I->operands()) {
       if (MO.isRegMask() && MO.clobbersPhysReg(Reg))

lib/CodeGen/RegisterPressure.cpp

bool RegPressureTracker::isBottomClosed() const {
   if (RequireIntervals)
     return static_cast<IntervalPressure&>(P).BottomIdx.isValid();
   return (static_cast<RegionPressure&>(P).BottomPos ==
           MachineBasicBlock::const_iterator());
 }
 
 
 SlotIndex RegPressureTracker::getCurrSlot() const {
-  MachineBasicBlock::const_iterator IdxPos = CurrPos;
-  while (IdxPos != MBB->end() && IdxPos->isDebugValue())
-    ++IdxPos;
+  MachineBasicBlock::const_iterator IdxPos =
+    skipDebugInstructionsForward(CurrPos, MBB->end());
   if (IdxPos == MBB->end())
     return LIS->getMBBEndIdx(MBB);
   return LIS->getInstructionIndex(*IdxPos).getRegSlot();
 }
 
 /// Set the boundary for the top of the region and summarize live ins.
 void RegPressureTracker::closeTop() {
   if (RequireIntervals)
void RegPressureTracker::recedeSkipDebugValues() {
   if (!isBottomClosed())
     closeBottom();
 
   // Open the top of the region using block iterators.
   if (!RequireIntervals && isTopClosed())
     static_cast<RegionPressure&>(P).openTop(CurrPos);
 
   // Find the previous instruction.
-  do
-    --CurrPos;
-  while (CurrPos != MBB->begin() && CurrPos->isDebugValue());
+  CurrPos = skipDebugInstructionsBackward(std::prev(CurrPos), MBB->begin());
 
   SlotIndex SlotIdx;
   if (RequireIntervals)
     SlotIdx = LIS->getInstructionIndex(*CurrPos).getRegSlot();
 
   // Open the top of the region using slot indexes.
   if (RequireIntervals && isTopClosed())
     static_cast<IntervalPressure&>(P).openTop(SlotIdx);
for (const RegisterMaskPair &Def : RegOpers.Defs) {
     LaneBitmask NewMask = PreviousMask | Def.LaneMask;
     increaseRegPressure(Def.RegUnit, PreviousMask, NewMask);
   }
 
   // Boost pressure for all dead defs together.
   bumpDeadDefs(RegOpers.DeadDefs);
 
   // Find the next instruction.
-  do
-    ++CurrPos;
-  while (CurrPos != MBB->end() && CurrPos->isDebugValue());
+  CurrPos = skipDebugInstructionsForward(std::next(CurrPos), MBB->end());
 }
 
 void RegPressureTracker::advance() {
   const MachineInstr &MI = *CurrPos;
   RegisterOperands RegOpers;
   RegOpers.collect(MI, *TRI, *MRI, TrackLaneMasks, false);
   if (TrackLaneMasks) {
     SlotIndex SlotIdx = getCurrSlot();