IfConversion: Use reverse_iterator to simplify. NFC

[iteratee]

Summary

This simplifies skipping debug instructions and shrinking ranges.

[fhahn]

Now that D27782 is merged, I think this would be a good simplification to get in, but the patch needs rebasing.

[iteratee]

Rebased as requested.

[dblaikie]

lib/CodeGen/IfConversion.cpp

646–652

Is this something we should be relying on? Does the spec say how reverse iterators can/should be constructed from non-reverse iterators in general? (and is MBB violating that contract?)

Should we be fixing MBB's reverse_iterators to do this accounting if it's the usual/expected/precedential (which is totally a word) thing?

648–651

Unnecessary ()

Also, if those functions return by value, I don't think you can reliably ++ an iterator value (works for user defined types/operator overloads, but not for primitive types like 'int*' for example).

Maybe std::next would be better on both counts?

716–724

auto?

[fhahn]

lib/CodeGen/IfConversion.cpp

682

If you are going to use std::next at line 648-651, it would be good to use it here as well to keep it consistent. I would prefer to use std::next personally.

[iteratee]

Changes from comments.

[iteratee]

I swear I need to teach git format-patch to warn if creating a patch from HEAD and a file in the patch is modified.

lib/CodeGen/IfConversion.cpp

646–652

See the comment in include/llvm/ADT/ilist_iterator.h:

/// Convert from an iterator to its reverse.
///
/// TODO: Roll this into the implicit constructor once we're sure that no one
/// is relying on the std::reverse_iterator off-by-one semantics.

I take that to mean that we are intentionally not supplying the std::reverse_iterator semantics.

The comment is aimed at a reader familiar with those semantics.

[iteratee]

Are there any other concerns with this patch?

lib/CodeGen/IfConversion.cpp

716–724

I'd rather not here.

[fhahn]

lib/CodeGen/IfConversion.cpp

625

I think we could first execute both TIB = skipDebugInstructionsForward(TIB, TIE); and FIB = skipDebugInstructionsForward(FIB, FIE); and then break from a single if. You already do that at line 722.

[iteratee]

Combine some end checks.

[iteratee]

Ping? Anything else on this?

[fhahn]

I think all comments have been addressed properly. @dblaikieCould you have another look?

[dblaikie]

Sure - not sure what Duncan's preference is here, or the ultimate end goal re: consistency, etc, is, though.

lib/CodeGen/IfConversion.cpp

649

This construct is used rather than this:

MachineBasicBlock::reverse_iterator RTIE = TIE;

to avoid depending on that conversion & it's subtle off-by-one jump?

[iteratee]

lib/CodeGen/IfConversion.cpp

649

Currently, there is no such conversion in ilist_iterator, only a getReverse() method, that doesn't perform an off-by-one jump.

[fhahn]

It looks

lib/CodeGen/IfConversion.cpp

649

That makes sense. @dblaikie do you think we should check with Duncan before committing this?

[iteratee]

Committed in rL293202

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;
 }
 
-/// 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--;
-}
-
 /// 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 &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.
     TIB = skipDebugInstructionsForward(TIB, TIE);
-    if(TIB == TIE)
+    if (TIB == TIE)
       break;
     FIB = skipDebugInstructionsForward(FIB, FIE);
-    if(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;
     // If we get all the way to the branch instructions, don't count them.
     if (!TIB->isBranch())
       ++Dups1;
     ++TIB;
     ++FIB;
   }
 
   // Check for already containing all of the block.
   if (TIB == TIE || FIB == FIE)
     return true;
   // Now, in preparation for counting duplicate instructions at the ends of the
-  // blocks, move the end iterators up past any branch instructions.
-  --TIE;
-  --FIE;
-
-  // After this point TIB and TIE define an inclusive range, which means that
-  // TIB == TIE is true when there is one more instruction to consider, not at
-  // the end. Because we may not be able to go before TIB, we need a flag to
-  // indicate a completely empty range.
-  bool TEmpty = false, FEmpty = false;
-
-  // Upon exit TIE and FIE will both point at the last non-shared instruction.
-  // They need to be moved forward to point past the last non-shared
-  // instruction if the range they delimit is non-empty.
-  auto IncrementEndIteratorsOnExit = make_scope_exit([&]() {
-    if (!TEmpty)
-      ++TIE;
-    if (!FEmpty)
-      ++FIE;
-  });
+  // blocks, switch to reverse_iterators. Note that these are NOT std
+  // reverse_iterators, so we have to manually do the off by one accounting.
+  MachineBasicBlock::reverse_iterator RTIE = std::next(TIE.getReverse());
+  MachineBasicBlock::reverse_iterator RFIE = std::next(FIE.getReverse());
+  const MachineBasicBlock::reverse_iterator RTIB = std::next(TIB.getReverse());
+  const MachineBasicBlock::reverse_iterator RFIB = std::next(FIB.getReverse());
 
   if (!TBB.succ_empty() || !FBB.succ_empty()) {
     if (SkipUnconditionalBranches) {
-      while (!TEmpty && TIE->isUnconditionalBranch())
-        shrinkInclusiveRange(TIB, TIE, TEmpty);
-      while (!FEmpty && FIE->isUnconditionalBranch())
-        shrinkInclusiveRange(FIB, FIE, FEmpty);
+      while (RTIE != RTIB && RTIE->isUnconditionalBranch())
+        ++RTIE;
+      while (RFIE != RFIB && RFIE->isUnconditionalBranch())
+        ++RFIE;
     }
   }
 
-  // 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) {
+  while (RTIE != RTIB && RFIE != RFIB) {
     // Skip dbg_value instructions. These do not count.
-    TIE = skipDebugInstructionsBackward(TIE, TIB);
-    FIE = skipDebugInstructionsBackward(FIE, FIB);
-    TEmpty = TIE == TIB && TIE->isDebugValue();
-    FEmpty = FIE == FIB && FIE->isDebugValue();
-    if (TEmpty || FEmpty)
+    // Note that these are reverse iterators going forward.
+    RTIE = skipDebugInstructionsForward(RTIE, RTIB);
+    if (RTIE == RTIB)
       break;
-    if (!TIE->isIdenticalTo(*FIE))
+    RFIE = skipDebugInstructionsForward(RFIE, RFIB);
+    if (RFIE == RFIB)
+      break;
+    if (!RTIE->isIdenticalTo(*RFIE))
       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())
+    if (!RTIE->isBranch())
       ++Dups2;
-    shrinkInclusiveRange(TIB, TIE, TEmpty);
-    shrinkInclusiveRange(FIB, FIE, FEmpty);
+    ++RTIE;
+    ++RFIE;
   }
+  TIE = std::next(RTIE.getReverse());
+  FIE = std::next(RFIE.getReverse());
   return true;
 }
 
 /// RescanInstructions - Run ScanInstructions on a pair of blocks.
 /// @param TIB - True Iterator Begin, points to first non-shared instruction
 /// @param FIB - False Iterator Begin, points to first non-shared instruction
 /// @param TIE - True Iterator End, points past last non-shared instruction
 /// @param FIE - False Iterator End, points past last non-shared instruction
if (TrueBBI.ClobbersPred && FalseBBI.ClobbersPred)
     return false;
   return true;
 }
 
 #ifndef NDEBUG
 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) {
-    E1 = skipDebugInstructionsBackward(E1, B1);
-    E2 = skipDebugInstructionsBackward(E2, B2);
-    Empty1 = E1 == B1 && E1->isDebugValue();
-    Empty2 = E2 == B2 && E2->isDebugValue();
-
-    if (Empty1 && Empty2)
+  const MachineBasicBlock::reverse_iterator B1 = MBB1->rend();
+  const MachineBasicBlock::reverse_iterator B2 = MBB2->rend();
+  MachineBasicBlock::reverse_iterator E1 = MBB1->rbegin();
+  MachineBasicBlock::reverse_iterator E2 = MBB2->rbegin();
+  while (E1 != B1 && E2 != B2) {
+    skipDebugInstructionsForward(E1, B1);
+    skipDebugInstructionsForward(E2, B2);
+    if (E1 == B1 && E2 == B2)
       break;
 
-    if (Empty1) {
+    if (E1 == B1) {
       assert(!E2->isBranch() && "Branch mis-match, one block is empty.");
       break;
     }
-    if (Empty2) {
+    if (E2 == B2) {
       assert(!E1->isBranch() && "Branch mis-match, one block is empty.");
       break;
     }
 
     if (E1->isBranch() || E2->isBranch())
       assert(E1->isIdenticalTo(*E2) &&
              "Branch mis-match, branch instructions don't match.");
     else
       break;
-    shrinkInclusiveRange(B1, E1, Empty1);
-    shrinkInclusiveRange(B2, E2, Empty2);
+    ++E1;
+    ++E2;
   }
 }
 #endif
 
 /// ValidForkedDiamond - Returns true if the 'true' and 'false' blocks (along
 /// with their common predecessor) form a diamond if a common tail block is
 /// extracted.
 /// While not strictly a diamond, this pattern would form a diamond if