ADT: Give ilist<T>::reverse_iterator a handle to the current node

[dexonsmith]

Summary

Reverse iterators to doubly-linked lists can be simpler (and cheaper)
than std::reverse_iterator. Make it so.

In particular, change ilist<T>::reverse_iterator so that it is *never*
invalidated unless the node it references is deleted. This matches the
guarantees of ilist<T>::iterator.

(Note: MachineBasicBlock::iterator is *not* an ilist iterator, but a
MachineInstrBundleIterator<MachineInstr>. This commit does not change
MachineBasicBlock::reverse_iterator, but it does update
MachineBasicBlock::reverse_instr_iterator. See note at end of commit
message for details on bundle iterators.)

Given the list (with the Sentinel showing twice for simplicity):

[Sentinel] <-> A <-> B <-> [Sentinel]

the following is now true:

1. begin() represents A.
2. begin() holds the pointer for A.
3. end() represents [Sentinel].
4. end() holds the poitner for [Sentinel].
5. rbegin() represents B.
6. rbegin() holds the pointer for B.
7. rend() represents [Sentinel].
8. rend() holds the pointer for [Sentinel].

The changes are #6 and #8. Here are some properties from the old
scheme (which used std::reverse_iterator):

• rbegin() held the pointer for [Sentinel] and rend() held the pointer for A;
• operator*() cost two dereferences instead of one;
• converting from a valid iterator to its valid reverse_iterator involved a confusing increment; and
• "RI++->erase()" left RI invalid. The unintuitive replacement was "RI->erase(), RE = end()".

With vector-like data structures these properties are hard to avoid
(since past-the-beginning is not a valid pointer), and don't impose a
real cost (since there's still only one dereference, and all iterators
are invalidated on erase). But with lists, this was a poor design.

Specifically, the following code (which obviously works with normal
iterators) now works with ilist::reverse_iterator as well:

for (auto RI = L.rbegin(), RE = L.rend(); RI != RE;)
  fooThatMightRemoveArgFromList(*RI++);

Converting between iterator and reverse_iterator for the same node uses
the getReverse() function.

reverse_iterator iterator::getReverse();
iterator reverse_iterator::getReverse();

Why doesn't iterator <=> reverse_iterator conversion use constructors?

In order to catch and update old code, reverse_iterator does not even
have an explicit conversion from iterator. It wouldn't be safe because
there would be no reasonable way to catch all the bugs from the changed
semantic (see the changes at call sites that are part of this patch).

Old code used this API:

std::reverse_iterator::reverse_iterator(iterator);
iterator std::reverse_iterator::base();

Here's how to update from old code to new (that incorporates the
semantic change), assuming I is an ilist<>::iterator and RI is an
ilist<>::reverse_iterator:

          [Old]         ==>          [New]
  reverse_iterator(I)         ++I.getReverse()
--reverse_iterator(I)           I.getReverse()
  reverse_iterator(++I)         I.getReverse()
        RI.base()            ++RI.getReverse()
      --RI.base()              RI.getReverse()
    (++RI).base()              RI.getReverse()
delete &*RI, RE = end()         delete &*RI++
RI->erase(), RE = end()         RI++->erase()

Note: bundle iterators are out of scope

MachineBasicBlock::iterator, also known as
MachineInstrBundleIterator<MachineInstr>, is a wrapper to represent
MachineInstr bundles. The idea is that each operator++ takes you to the
beginning of the next bundle. Implementing a sane reverse iterator for
this is harder than ilist. Here are the options:

• Use std::reverse_iterator<MBB::i>. Store a handle to the beginning of the next bundle. A call to operator*() runs a loop (usually operator--() will be called 1 time, for unbundled instructions). Increment/decrement just works. This is the status quo.
• Store a handle to the final node in the bundle. A call to operator*() still runs a loop, but it iterates one time fewer (usually operator--() will be called 0 times, for unbundled instructions). Increment/decrement just works.
• Store a handle to the first node in the bundle. A call to operator*() just works. However, reverse_iterator::operator++() (moving the handle back one in the list) requires checking against end() before incrementing (not too hard with MachineInstr::getParent).

I tried implementing this last option (and I may follow up with a patch
that finishes it). Updating iterator/reverse_iterator conversion call
sites was error-prone, though. With ilist::iterator/reverse_iterator,
++end().getReverse() (i.e., ++before_rbegin()) gets you rbegin(),
through the magic of circular lists. Symmetrically,
++rend().getReverse() (i.e., ++before_begin()) gives you begin(). With
MachineBasicBlock::iterator/reverse_iterator, ++before_begin() is not
safe, since we need MachineInstr::getParent to be valid to know whether
the handle is dereferenceable.

Another fix is a fourth option that is out-of-scope for this commit:

• Make the ilist_sentinel<MachineInstr> *always* store that it's the sentinel (instead of just in asserts mode). Then the bundle iterator can sniff the sentinel bit in operator++() so that ++before_rbegin() and ++before_begin() both work.

[dexonsmith]

Justin Bogner pointed out offline that my code update table was wrong (backwards) for reverse_iterator=>iterator conversions. I fixed the table both on Phab and in my local commit message to this table:

          [Old]         ==>          [New]
  reverse_iterator(I)         ++I.getReverse()
--reverse_iterator(I)           I.getReverse()
  reverse_iterator(++I)         I.getReverse()
        RI.base()            ++RI.getReverse()
      --RI.base()              RI.getReverse()
    (++RI).base()              RI.getReverse()
delete &*RI, RE = end()         delete &*RI++
RI->erase(), RE = end()         RI++->erase()

[dexonsmith]

Updated to fix four compile errors in Lanai after r279498 turned it non-experimental!

[dexonsmith]

Thanks for the review! Committed in r280032.

include/llvm/ADT/ilist.h

 #include <cassert>
 #include <cstddef>
 #include <iterator>
 #include <type_traits>
 
 namespace llvm {
 
 template<typename NodeTy, typename Traits> class iplist;
-template<typename NodeTy> class ilist_iterator;
+template <typename NodeTy, bool IsReverse> class ilist_iterator;
 
 /// An access class for ilist_node private API.
 ///
 /// This gives access to the private parts of ilist nodes.  Nodes for an ilist
 /// should friend this class if they inherit privately from ilist_node.
 ///
 /// It's strongly discouraged to *use* this class outside of the ilist
 /// implementation.

 
 namespace ilist_detail {
 template <class NodeTy> struct ConstCorrectNodeType {
   typedef ilist_node<NodeTy> type;
 };
 template <class NodeTy> struct ConstCorrectNodeType<const NodeTy> {
   typedef const ilist_node<NodeTy> type;
 };
+
+template <bool IsReverse = false> struct IteratorHelper {
+  template <class T> static void increment(T *&I) {
+    I = ilist_node_access::getNext(*I);
+  }
+  template <class T> static void decrement(T *&I) {
+    I = ilist_node_access::getPrev(*I);
+  }
+};
+template <> struct IteratorHelper<true> {
+  template <class T> static void increment(T *&I) {
+    IteratorHelper<false>::decrement(I);
+  }
+  template <class T> static void decrement(T *&I) {
+    IteratorHelper<false>::increment(I);
+  }
+};
+
 } // end namespace ilist_detail
 
 //===----------------------------------------------------------------------===//
 // Iterator for intrusive list.
 //
-template <typename NodeTy>
+template <typename NodeTy, bool IsReverse>
 class ilist_iterator
     : public std::iterator<std::bidirectional_iterator_tag, NodeTy, ptrdiff_t> {
 public:
   typedef std::iterator<std::bidirectional_iterator_tag, NodeTy, ptrdiff_t>
       super;
 
   typedef typename super::value_type value_type;
   typedef typename super::difference_type difference_type;
public:
   explicit ilist_iterator(pointer NP) : NodePtr(NP) {}
   explicit ilist_iterator(reference NR) : NodePtr(&NR) {}
   ilist_iterator() : NodePtr(nullptr) {}
 
   // This is templated so that we can allow constructing a const iterator from
   // a nonconst iterator...
   template <class node_ty>
   ilist_iterator(
-      const ilist_iterator<node_ty> &RHS,
+      const ilist_iterator<node_ty, IsReverse> &RHS,
       typename std::enable_if<std::is_convertible<node_ty *, NodeTy *>::value,
                               void *>::type = nullptr)
       : NodePtr(RHS.getNodePtr()) {}
 
   // This is templated so that we can allow assigning to a const iterator from
   // a nonconst iterator...
   template <class node_ty>
-  const ilist_iterator &operator=(const ilist_iterator<node_ty> &RHS) {
+  const ilist_iterator &
+  operator=(const ilist_iterator<node_ty, IsReverse> &RHS) {
     NodePtr = RHS.getNodePtr();
     return *this;
   }
 
+  /// 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.
+  ilist_iterator<NodeTy, !IsReverse> getReverse() const {
+    if (NodePtr)
+      return ilist_iterator<NodeTy, !IsReverse>(*NodePtr);
+    return ilist_iterator<NodeTy, !IsReverse>();
+  }
+
   void reset(pointer NP) { NodePtr = NP; }
 
   // Accessors...
   reference operator*() const {
     assert(!NodePtr->isKnownSentinel());
     return static_cast<NodeTy &>(*getNodePtr());
   }
   pointer operator->() const { return &operator*(); }
 
   // Comparison operators
   friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) {
     return LHS.NodePtr == RHS.NodePtr;
   }
   friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
     return LHS.NodePtr != RHS.NodePtr;
   }
 
   // Increment and decrement operators...
   ilist_iterator &operator--() {
-    NodePtr = ilist_node_access::getPrev(*NodePtr);
-    assert(NodePtr && "--'d off the beginning of an ilist!");
+    ilist_detail::IteratorHelper<IsReverse>::decrement(NodePtr);
     return *this;
   }
   ilist_iterator &operator++() {
-    NodePtr = ilist_node_access::getNext(*NodePtr);
+    ilist_detail::IteratorHelper<IsReverse>::increment(NodePtr);
     return *this;
   }
   ilist_iterator operator--(int) {
     ilist_iterator tmp = *this;
     --*this;
     return tmp;
   }
   ilist_iterator operator++(int) {
public:
   typedef const NodeTy *const_pointer;
   typedef NodeTy &reference;
   typedef const NodeTy &const_reference;
   typedef NodeTy value_type;
   typedef ilist_iterator<NodeTy> iterator;
   typedef ilist_iterator<const NodeTy> const_iterator;
   typedef size_t size_type;
   typedef ptrdiff_t difference_type;
-  typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
-  typedef std::reverse_iterator<iterator>  reverse_iterator;
+  typedef ilist_iterator<const NodeTy, true> const_reverse_iterator;
+  typedef ilist_iterator<NodeTy, true> reverse_iterator;
 
   iplist() = default;
   ~iplist() { clear(); }
 
   // Iterator creation methods.
   iterator begin() { return ++iterator(Sentinel); }
   const_iterator begin() const { return ++const_iterator(Sentinel); }
   iterator end() { return iterator(Sentinel); }
   const_iterator end() const { return const_iterator(Sentinel); }
 
   // reverse iterator creation methods.
-  reverse_iterator rbegin()            { return reverse_iterator(end()); }
-  const_reverse_iterator rbegin() const{ return const_reverse_iterator(end()); }
-  reverse_iterator rend()              { return reverse_iterator(begin()); }
-  const_reverse_iterator rend() const { return const_reverse_iterator(begin());}
-
+  reverse_iterator rbegin()            { return ++reverse_iterator(Sentinel); }
+  const_reverse_iterator rbegin() const{ return ++const_reverse_iterator(Sentinel); }
+  reverse_iterator rend()              { return reverse_iterator(Sentinel); }
+  const_reverse_iterator rend() const { return const_reverse_iterator(Sentinel); }
 
   // Miscellaneous inspection routines.
   size_type max_size() const { return size_type(-1); }
   bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return Sentinel.empty(); }
 
   // Front and back accessor functions...
   reference front() {
     assert(!empty() && "Called front() on empty list!");

include/llvm/ADT/ilist_node.h

#else
   void initializeSentinel() {}
 #endif
 
   void setNext(ilist_node_base *Next) { this->Next = Next; }
   ilist_node_base *getNext() const { return Next; }
 };
 
 struct ilist_node_access;
-template <typename NodeTy> class ilist_iterator;
+template <typename NodeTy, bool IsReverse = false> class ilist_iterator;
 template <typename NodeTy> class ilist_sentinel;
 
 /// Templated wrapper class.
 template <typename NodeTy> class ilist_node : ilist_node_base {
   friend class ilist_base;
   friend struct ilist_node_access;
   friend struct ilist_traits<NodeTy>;
-  friend class ilist_iterator<NodeTy>;
+  friend class ilist_iterator<NodeTy, false>;
+  friend class ilist_iterator<NodeTy, true>;
   friend class ilist_sentinel<NodeTy>;
 
 protected:
   ilist_node() = default;
 
 private:
   ilist_node *getPrev() {
     return static_cast<ilist_node *>(ilist_node_base::getPrev());

include/llvm/CodeGen/MachineBasicBlock.h

public:
   void setHasAddressTaken() { AddressTaken = true; }
 
   /// Return the MachineFunction containing this basic block.
   const MachineFunction *getParent() const { return xParent; }
   MachineFunction *getParent() { return xParent; }
 
   typedef Instructions::iterator                                 instr_iterator;
   typedef Instructions::const_iterator                     const_instr_iterator;
-  typedef std::reverse_iterator<instr_iterator>          reverse_instr_iterator;
-  typedef
-  std::reverse_iterator<const_instr_iterator>      const_reverse_instr_iterator;
+  typedef Instructions::reverse_iterator reverse_instr_iterator;
+  typedef Instructions::const_reverse_iterator const_reverse_instr_iterator;
 
   typedef MachineInstrBundleIterator<MachineInstr> iterator;
   typedef MachineInstrBundleIterator<const MachineInstr> const_iterator;
   typedef std::reverse_iterator<const_iterator>          const_reverse_iterator;
   typedef std::reverse_iterator<iterator>                      reverse_iterator;
 
 
   unsigned size() const { return (unsigned)Insts.size(); }
public:
   const_instr_range instrs() const {
     return const_instr_range(instr_begin(), instr_end());
   }
 
   iterator                begin()       { return instr_begin();  }
   const_iterator          begin() const { return instr_begin();  }
   iterator                end  ()       { return instr_end();    }
   const_iterator          end  () const { return instr_end();    }
-  reverse_iterator       rbegin()       { return instr_rbegin(); }
-  const_reverse_iterator rbegin() const { return instr_rbegin(); }
-  reverse_iterator       rend  ()       { return instr_rend();   }
-  const_reverse_iterator rend  () const { return instr_rend();   }
+  reverse_iterator rbegin() { return reverse_iterator(end()); }
+  const_reverse_iterator rbegin() const {
+    return const_reverse_iterator(end());
+  }
+  reverse_iterator rend() { return reverse_iterator(begin()); }
+  const_reverse_iterator rend() const {
+    return const_reverse_iterator(begin());
+  }
 
   /// Support for MachineInstr::getNextNode().
   static Instructions MachineBasicBlock::*getSublistAccess(MachineInstr *) {
     return &MachineBasicBlock::Insts;
   }
 
   inline iterator_range<iterator> terminators() {
     return make_range(getFirstTerminator(), end());

include/llvm/CodeGen/MachineFunction.h

public:
   /// for debugger use.
   /// \returns true if no problems were found.
   bool verify(Pass *p = nullptr, const char *Banner = nullptr,
               bool AbortOnError = true) const;
 
   // Provide accessors for the MachineBasicBlock list...
   typedef BasicBlockListType::iterator iterator;
   typedef BasicBlockListType::const_iterator const_iterator;
-  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
-  typedef std::reverse_iterator<iterator>             reverse_iterator;
+  typedef BasicBlockListType::const_reverse_iterator const_reverse_iterator;
+  typedef BasicBlockListType::reverse_iterator reverse_iterator;
 
   /// Support for MachineBasicBlock::getNextNode().
   static BasicBlockListType MachineFunction::*
   getSublistAccess(MachineBasicBlock *) {
     return &MachineFunction::BasicBlocks;
   }
 
   /// addLiveIn - Add the specified physical register as a live-in value and

include/llvm/IR/SymbolTableListTraits.h

 #ifndef LLVM_IR_SYMBOLTABLELISTTRAITS_H
 #define LLVM_IR_SYMBOLTABLELISTTRAITS_H
 
 #include "llvm/ADT/ilist.h"
 
 namespace llvm {
 class ValueSymbolTable;
 
-template <typename NodeTy> class ilist_iterator;
-template <typename NodeTy, typename Traits> class iplist;
-template <typename Ty> struct ilist_traits;
-
 /// Template metafunction to get the parent type for a symbol table list.
 ///
 /// Implementations create a typedef called \c type so that we only need a
 /// single template parameter for the list and traits.
 template <typename NodeTy> struct SymbolTableListParentType {};
 class Argument;
 class BasicBlock;
 class Function;

 template <typename NodeTy> class SymbolTableList;
 
 // ValueSubClass   - The type of objects that I hold, e.g. Instruction.
 // ItemParentClass - The type of object that owns the list, e.g. BasicBlock.
 //
 template <typename ValueSubClass>
 class SymbolTableListTraits : public ilist_node_traits<ValueSubClass> {
   typedef SymbolTableList<ValueSubClass> ListTy;
+  typedef ilist_iterator<ValueSubClass, false> iterator;
   typedef
       typename SymbolTableListParentType<ValueSubClass>::type ItemParentClass;
 
 public:
   SymbolTableListTraits() {}
 
 private:
   /// getListOwner - Return the object that owns this list.  If this is a list
private:
 
   static ValueSymbolTable *getSymTab(ItemParentClass *Par) {
     return Par ? toPtr(Par->getValueSymbolTable()) : nullptr;
   }
 
 public:
   void addNodeToList(ValueSubClass *V);
   void removeNodeFromList(ValueSubClass *V);
-  void transferNodesFromList(SymbolTableListTraits &L2,
-                             ilist_iterator<ValueSubClass> first,
-                             ilist_iterator<ValueSubClass> last);
-//private:
+  void transferNodesFromList(SymbolTableListTraits &L2, iterator first,
+                             iterator last);
+  // private:
   template<typename TPtr>
   void setSymTabObject(TPtr *, TPtr);
   static ValueSymbolTable *toPtr(ValueSymbolTable *P) { return P; }
   static ValueSymbolTable *toPtr(ValueSymbolTable &R) { return &R; }
 };
 
 /// List that automatically updates parent links and symbol tables.
 ///

lib/CodeGen/MachinePipeliner.cpp

for (MachineBasicBlock::reverse_instr_iterator MI = (*MBB)->instr_rbegin(),
             break;
           }
         }
         if (realUses > 0)
           break;
         used = false;
       }
       if (!used) {
-        MI->eraseFromParent();
-        ME = (*MBB)->instr_rend();
+        MI++->eraseFromParent();
         continue;
       }
       ++MI;
     }
   // In the kernel block, check if we can remove a Phi that generates a value
   // used in an instruction removed in the epilog block.
   for (MachineBasicBlock::iterator BBI = KernelBB->instr_begin(),
                                    BBE = KernelBB->getFirstNonPHI();

lib/Target/Lanai/LanaiDelaySlotFiller.cpp

if (I->getDesc().hasDelaySlot()) {
       MachineBasicBlock::instr_iterator J = I;
 
       // Treat RET specially as it is only instruction with 2 delay slots
       // generated while all others generated have 1 delay slot.
       if (I->getOpcode() == Lanai::RET) {
         // RET is generated as part of epilogue generation and hence we know
         // what the two instructions preceding it are and that it is safe to
         // insert RET above them.
-        MachineBasicBlock::reverse_instr_iterator RI(I);
+        MachineBasicBlock::reverse_instr_iterator RI = ++I.getReverse();
         assert(RI->getOpcode() == Lanai::LDW_RI && RI->getOperand(0).isReg() &&
                RI->getOperand(0).getReg() == Lanai::FP &&
                RI->getOperand(1).isReg() &&
                RI->getOperand(1).getReg() == Lanai::FP &&
                RI->getOperand(2).isImm() && RI->getOperand(2).getImm() == -8);
         ++RI;
         assert(RI->getOpcode() == Lanai::ADD_I_LO &&
                RI->getOperand(0).isReg() &&
                RI->getOperand(0).getReg() == Lanai::SP &&
                RI->getOperand(1).isReg() &&
                RI->getOperand(1).getReg() == Lanai::FP);
-        ++RI;
-        MachineBasicBlock::instr_iterator FI(RI.base());
+        MachineBasicBlock::instr_iterator FI = RI.getReverse();
         MBB.splice(std::next(I), &MBB, FI, I);
         FilledSlots += 2;
       } else {
         if (!NopDelaySlotFiller && findDelayInstr(MBB, I, J)) {
           MBB.splice(std::next(I), &MBB, J);
         } else {
           BuildMI(MBB, std::next(I), DebugLoc(), TII->get(Lanai::NOP));
         }
bool Filler::findDelayInstr(MachineBasicBlock &MBB,
   SmallSet<unsigned, 32> RegDefs;
   SmallSet<unsigned, 32> RegUses;
 
   insertDefsUses(Slot, RegDefs, RegUses);
 
   bool SawLoad = false;
   bool SawStore = false;
 
-  for (MachineBasicBlock::reverse_instr_iterator I(Slot); I != MBB.instr_rend();
-       ++I) {
+  for (MachineBasicBlock::reverse_instr_iterator I = ++Slot.getReverse();
+       I != MBB.instr_rend(); ++I) {
     // skip debug value
     if (I->isDebugValue())
       continue;
 
     // Convert to forward iterator.
-    MachineBasicBlock::instr_iterator FI(std::next(I).base());
+    MachineBasicBlock::instr_iterator FI = I.getReverse();
 
     if (I->hasUnmodeledSideEffects() || I->isInlineAsm() || I->isLabel() ||
         FI == LastFiller || I->isPseudo())
       break;
 
     if (delayHasHazard(FI, SawLoad, SawStore, RegDefs, RegUses)) {
       insertDefsUses(FI, RegDefs, RegUses);
       continue;

lib/Target/X86/X86FixupSetCC.cpp

 
 // We expect the instruction *immediately* before the setcc to imp-def
 // EFLAGS (because of scheduling glue). To make this less brittle w.r.t
 // scheduling, look backwards until we hit the beginning of the
 // basic-block, or a small bound (to avoid quadratic behavior).
 MachineInstr *
 X86FixupSetCCPass::findFlagsImpDef(MachineBasicBlock *MBB,
                                    MachineBasicBlock::reverse_iterator MI) {
-  auto MBBStart = MBB->instr_rend();
+  // FIXME: Should this be instr_rend(), and MI be reverse_instr_iterator?
+  auto MBBStart = MBB->rend();
   for (int i = 0; (i < SearchBound) && (MI != MBBStart); ++i, ++MI)
     for (auto &Op : MI->implicit_operands())
       if ((Op.getReg() == X86::EFLAGS) && (Op.isDef()))
         return &*MI;
 
   return nullptr;
 }
 

lib/Transforms/Scalar/LoopRerollPass.cpp

DEBUG(dbgs() << "LRR: Matched all iteration increments for " <<
                   *IV << "\n");
 
   return true;
 }
 
 void LoopReroll::DAGRootTracker::replace(const SCEV *IterCount) {
   BasicBlock *Header = L->getHeader();
   // Remove instructions associated with non-base iterations.
-  for (BasicBlock::reverse_iterator J = Header->rbegin();
-       J != Header->rend();) {
+  for (BasicBlock::reverse_iterator J = Header->rbegin(), JE = Header->rend();
+       J != JE;) {
     unsigned I = Uses[&*J].find_first();
     if (I > 0 && I < IL_All) {
-      Instruction *D = &*J;
-      DEBUG(dbgs() << "LRR: removing: " << *D << "\n");
-      D->eraseFromParent();
+      DEBUG(dbgs() << "LRR: removing: " << *J << "\n");
+      J++->eraseFromParent();
       continue;
     }
 
     ++J;
   }
 
   bool HasTwoIVs = LoopControlIV && LoopControlIV != IV;
 

lib/Transforms/Scalar/RewriteStatepointsForGC.cpp

static void findLiveSetAtInst(Instruction *Inst, GCPtrLivenessData &Data,
   // Note: The copy is intentional and required
   assert(Data.LiveOut.count(BB));
   SetVector<Value *> LiveOut = Data.LiveOut[BB];
 
   // We want to handle the statepoint itself oddly.  It's
   // call result is not live (normal), nor are it's arguments
   // (unless they're used again later).  This adjustment is
   // specifically what we need to relocate
-  BasicBlock::reverse_iterator rend(Inst->getIterator());
-  computeLiveInValues(BB->rbegin(), rend, LiveOut);
+  computeLiveInValues(BB->rbegin(), ++Inst->getIterator().getReverse(),
+                      LiveOut);
   LiveOut.remove(Inst);
   Out.insert(LiveOut.begin(), LiveOut.end());
 }
 
 static void recomputeLiveInValues(GCPtrLivenessData &RevisedLivenessData,
                                   CallSite CS,
                                   PartiallyConstructedSafepointRecord &Info) {
   Instruction *Inst = CS.getInstruction();

lib/Transforms/Vectorize/SLPVectorizer.cpp

DEBUG(
       dbgs() << "SLP: #LV: " << LiveValues.size();
       for (auto *X : LiveValues)
         dbgs() << " " << X->getName();
       dbgs() << ", Looking at ";
       Inst->dump();
       );
 
     // Now find the sequence of instructions between PrevInst and Inst.
-    BasicBlock::reverse_iterator InstIt(Inst->getIterator()),
-        PrevInstIt(PrevInst->getIterator());
-    --PrevInstIt;
+    BasicBlock::reverse_iterator InstIt = ++Inst->getIterator().getReverse(),
+                                 PrevInstIt =
+                                     PrevInst->getIterator().getReverse();
     while (InstIt != PrevInstIt) {
       if (PrevInstIt == PrevInst->getParent()->rend()) {
         PrevInstIt = Inst->getParent()->rbegin();
         continue;
       }
 
       if (isa<CallInst>(&*PrevInstIt) && &*PrevInstIt != PrevInst) {
         SmallVector<Type*, 4> V;
if (!ScheduleStart) {
     ScheduleStart = I;
     ScheduleEnd = I->getNextNode();
     assert(ScheduleEnd && "tried to vectorize a TerminatorInst?");
     DEBUG(dbgs() << "SLP:  initialize schedule region to " << *I << "\n");
     return true;
   }
   // Search up and down at the same time, because we don't know if the new
   // instruction is above or below the existing scheduling region.
-  BasicBlock::reverse_iterator UpIter(ScheduleStart->getIterator());
+  BasicBlock::reverse_iterator UpIter =
+      ++ScheduleStart->getIterator().getReverse();
   BasicBlock::reverse_iterator UpperEnd = BB->rend();
-  BasicBlock::iterator DownIter(ScheduleEnd);
+  BasicBlock::iterator DownIter = ScheduleEnd->getIterator();
   BasicBlock::iterator LowerEnd = BB->end();
   for (;;) {
     if (++ScheduleRegionSize > ScheduleRegionSizeLimit) {
       DEBUG(dbgs() << "SLP:  exceeded schedule region size limit\n");
       return false;
     }
 
     if (UpIter != UpperEnd) {

unittests/ADT/CMakeLists.txt

set(ADTSources
   DenseMapTest.cpp
   DenseSetTest.cpp
   DepthFirstIteratorTest.cpp
   FoldingSet.cpp
   FunctionRefTest.cpp
   HashingTest.cpp
   ilistTestTemp.cpp
   IListBaseTest.cpp
+  IListIteratorTest.cpp
   IListNodeBaseTest.cpp
   IListSentinelTest.cpp
   ImmutableMapTest.cpp
   ImmutableSetTest.cpp
   IntEqClassesTest.cpp
   IntervalMapTest.cpp
   IntrusiveRefCntPtrTest.cpp
   IteratorTest.cpp

unittests/ADT/IListIteratorTest.cpp

+//===- unittests/ADT/IListIteratorTest.cpp - ilist_iterator unit tests ----===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/ilist.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+struct Node : ilist_node<Node> {};
+
+TEST(IListIteratorTest, DefaultConstructor) {
+  iplist<Node>::iterator I;
+  iplist<Node>::reverse_iterator RI;
+  iplist<Node>::const_iterator CI;
+  iplist<Node>::const_reverse_iterator CRI;
+  EXPECT_EQ(nullptr, I.getNodePtr());
+  EXPECT_EQ(nullptr, CI.getNodePtr());
+  EXPECT_EQ(nullptr, RI.getNodePtr());
+  EXPECT_EQ(nullptr, CRI.getNodePtr());
+  EXPECT_EQ(I, I);
+  EXPECT_EQ(I, CI);
+  EXPECT_EQ(CI, I);
+  EXPECT_EQ(CI, CI);
+  EXPECT_EQ(RI, RI);
+  EXPECT_EQ(RI, CRI);
+  EXPECT_EQ(CRI, RI);
+  EXPECT_EQ(CRI, CRI);
+  EXPECT_EQ(I, RI.getReverse());
+  EXPECT_EQ(RI, I.getReverse());
+}
+
+TEST(IListIteratorTest, Empty) {
+  iplist<Node> L;
+
+  // Check iterators of L.
+  EXPECT_EQ(L.begin(), L.end());
+  EXPECT_EQ(L.rbegin(), L.rend());
+
+  // Reverse of end should be rend (since the sentinel sits on both sides).
+  EXPECT_EQ(L.end(), L.rend().getReverse());
+  EXPECT_EQ(L.rend(), L.end().getReverse());
+
+  // Iterators shouldn't match default constructors.
+  iplist<Node>::iterator I;
+  iplist<Node>::reverse_iterator RI;
+  EXPECT_NE(I, L.begin());
+  EXPECT_NE(I, L.end());
+  EXPECT_NE(RI, L.rbegin());
+  EXPECT_NE(RI, L.rend());
+
+  // Don't delete nodes.
+  L.clearAndLeakNodesUnsafely();
+}
+
+TEST(IListIteratorTest, OneNodeList) {
+  iplist<Node> L;
+  Node A;
+  L.insert(L.end(), &A);
+
+  // Check address of reference.
+  EXPECT_EQ(&A, &*L.begin());
+  EXPECT_EQ(&A, &*L.rbegin());
+
+  // Check that the handle matches.
+  EXPECT_EQ(L.rbegin().getNodePtr(), L.begin().getNodePtr());
+
+  // Check iteration.
+  EXPECT_EQ(L.end(), ++L.begin());
+  EXPECT_EQ(L.begin(), --L.end());
+  EXPECT_EQ(L.rend(), ++L.rbegin());
+  EXPECT_EQ(L.rbegin(), --L.rend());
+
+  // Check conversions.
+  EXPECT_EQ(L.rbegin(), L.begin().getReverse());
+  EXPECT_EQ(L.begin(), L.rbegin().getReverse());
+
+  // Don't delete nodes.
+  L.clearAndLeakNodesUnsafely();
+}
+
+TEST(IListIteratorTest, TwoNodeList) {
+  iplist<Node> L;
+  Node A, B;
+  L.insert(L.end(), &A);
+  L.insert(L.end(), &B);
+
+  // Check order.
+  EXPECT_EQ(&A, &*L.begin());
+  EXPECT_EQ(&B, &*++L.begin());
+  EXPECT_EQ(L.end(), ++++L.begin());
+  EXPECT_EQ(&B, &*L.rbegin());
+  EXPECT_EQ(&A, &*++L.rbegin());
+  EXPECT_EQ(L.rend(), ++++L.rbegin());
+
+  // Check conversions.
+  EXPECT_EQ(++L.rbegin(), L.begin().getReverse());
+  EXPECT_EQ(L.rbegin(), (++L.begin()).getReverse());
+  EXPECT_EQ(++L.begin(), L.rbegin().getReverse());
+  EXPECT_EQ(L.begin(), (++L.rbegin()).getReverse());
+
+  // Don't delete nodes.
+  L.clearAndLeakNodesUnsafely();
+}
+
+TEST(IListIteratorTest, CheckEraseForward) {
+  iplist<Node> L;
+  Node A, B;
+  L.insert(L.end(), &A);
+  L.insert(L.end(), &B);
+
+  // Erase nodes.
+  auto I = L.begin();
+  EXPECT_EQ(&A, &*I);
+  EXPECT_EQ(&A, L.remove(I++));
+  EXPECT_EQ(&B, &*I);
+  EXPECT_EQ(&B, L.remove(I++));
+  EXPECT_EQ(L.end(), I);
+
+  // Don't delete nodes.
+  L.clearAndLeakNodesUnsafely();
+}
+
+TEST(IListIteratorTest, CheckEraseReverse) {
+  iplist<Node> L;
+  Node A, B;
+  L.insert(L.end(), &A);
+  L.insert(L.end(), &B);
+
+  // Erase nodes.
+  auto RI = L.rbegin();
+  EXPECT_EQ(&B, &*RI);
+  EXPECT_EQ(&B, L.remove(&*RI++));
+  EXPECT_EQ(&A, &*RI);
+  EXPECT_EQ(&A, L.remove(&*RI++));
+  EXPECT_EQ(L.rend(), RI);
+
+  // Don't delete nodes.
+  L.clearAndLeakNodesUnsafely();
+}
+
+} // end namespace