Index: include/llvm/ADT/ilist.h =================================================================== --- include/llvm/ADT/ilist.h +++ include/llvm/ADT/ilist.h @@ -35,7 +35,7 @@ namespace llvm { template class iplist; -template class ilist_iterator; +template class ilist_iterator; /// An access class for ilist_node private API. /// @@ -146,12 +146,30 @@ template struct ConstCorrectNodeType { typedef const ilist_node type; }; + +template struct IteratorHelper { + template static void increment(T *&I) { + I = ilist_node_access::getNext(*I); + } + template static void decrement(T *&I) { + I = ilist_node_access::getPrev(*I); + } +}; +template <> struct IteratorHelper { + template static void increment(T *&I) { + IteratorHelper::decrement(I); + } + template static void decrement(T *&I) { + IteratorHelper::increment(I); + } +}; + } // end namespace ilist_detail //===----------------------------------------------------------------------===// // Iterator for intrusive list. // -template +template class ilist_iterator : public std::iterator { public: @@ -185,7 +203,7 @@ // a nonconst iterator... template ilist_iterator( - const ilist_iterator &RHS, + const ilist_iterator &RHS, typename std::enable_if::value, void *>::type = nullptr) : NodePtr(RHS.getNodePtr()) {} @@ -193,11 +211,22 @@ // This is templated so that we can allow assigning to a const iterator from // a nonconst iterator... template - const ilist_iterator &operator=(const ilist_iterator &RHS) { + const ilist_iterator & + operator=(const ilist_iterator &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 getReverse() const { + if (NodePtr) + return ilist_iterator(*NodePtr); + return ilist_iterator(); + } + void reset(pointer NP) { NodePtr = NP; } // Accessors... @@ -217,12 +246,11 @@ // 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::decrement(NodePtr); return *this; } ilist_iterator &operator++() { - NodePtr = ilist_node_access::getNext(*NodePtr); + ilist_detail::IteratorHelper::increment(NodePtr); return *this; } ilist_iterator operator--(int) { @@ -356,8 +384,8 @@ typedef ilist_iterator const_iterator; typedef size_t size_type; typedef ptrdiff_t difference_type; - typedef std::reverse_iterator const_reverse_iterator; - typedef std::reverse_iterator reverse_iterator; + typedef ilist_iterator const_reverse_iterator; + typedef ilist_iterator reverse_iterator; iplist() = default; ~iplist() { clear(); } @@ -369,11 +397,10 @@ 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); } Index: include/llvm/ADT/ilist_node.h =================================================================== --- include/llvm/ADT/ilist_node.h +++ include/llvm/ADT/ilist_node.h @@ -51,7 +51,7 @@ }; struct ilist_node_access; -template class ilist_iterator; +template class ilist_iterator; template class ilist_sentinel; /// Templated wrapper class. @@ -59,7 +59,8 @@ friend class ilist_base; friend struct ilist_node_access; friend struct ilist_traits; - friend class ilist_iterator; + friend class ilist_iterator; + friend class ilist_iterator; friend class ilist_sentinel; protected: Index: include/llvm/CodeGen/MachineBasicBlock.h =================================================================== --- include/llvm/CodeGen/MachineBasicBlock.h +++ include/llvm/CodeGen/MachineBasicBlock.h @@ -150,9 +150,8 @@ typedef Instructions::iterator instr_iterator; typedef Instructions::const_iterator const_instr_iterator; - typedef std::reverse_iterator reverse_instr_iterator; - typedef - std::reverse_iterator const_reverse_instr_iterator; + typedef Instructions::reverse_iterator reverse_instr_iterator; + typedef Instructions::const_reverse_iterator const_reverse_instr_iterator; typedef MachineInstrBundleIterator iterator; typedef MachineInstrBundleIterator const_iterator; @@ -193,10 +192,14 @@ 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 *) { Index: include/llvm/CodeGen/MachineFunction.h =================================================================== --- include/llvm/CodeGen/MachineFunction.h +++ include/llvm/CodeGen/MachineFunction.h @@ -422,8 +422,8 @@ // Provide accessors for the MachineBasicBlock list... typedef BasicBlockListType::iterator iterator; typedef BasicBlockListType::const_iterator const_iterator; - typedef std::reverse_iterator const_reverse_iterator; - typedef std::reverse_iterator reverse_iterator; + typedef BasicBlockListType::const_reverse_iterator const_reverse_iterator; + typedef BasicBlockListType::reverse_iterator reverse_iterator; /// Support for MachineBasicBlock::getNextNode(). static BasicBlockListType MachineFunction::* Index: include/llvm/IR/SymbolTableListTraits.h =================================================================== --- include/llvm/IR/SymbolTableListTraits.h +++ include/llvm/IR/SymbolTableListTraits.h @@ -30,10 +30,6 @@ namespace llvm { class ValueSymbolTable; -template class ilist_iterator; -template class iplist; -template 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 @@ -66,6 +62,7 @@ template class SymbolTableListTraits : public ilist_node_traits { typedef SymbolTableList ListTy; + typedef ilist_iterator iterator; typedef typename SymbolTableListParentType::type ItemParentClass; @@ -94,10 +91,9 @@ public: void addNodeToList(ValueSubClass *V); void removeNodeFromList(ValueSubClass *V); - void transferNodesFromList(SymbolTableListTraits &L2, - ilist_iterator first, - ilist_iterator last); -//private: + void transferNodesFromList(SymbolTableListTraits &L2, iterator first, + iterator last); + // private: template void setSymTabObject(TPtr *, TPtr); static ValueSymbolTable *toPtr(ValueSymbolTable *P) { return P; } Index: lib/CodeGen/MachinePipeliner.cpp =================================================================== --- lib/CodeGen/MachinePipeliner.cpp +++ lib/CodeGen/MachinePipeliner.cpp @@ -2880,8 +2880,7 @@ used = false; } if (!used) { - MI->eraseFromParent(); - ME = (*MBB)->instr_rend(); + MI++->eraseFromParent(); continue; } ++MI; Index: lib/Target/Lanai/LanaiDelaySlotFiller.cpp =================================================================== --- lib/Target/Lanai/LanaiDelaySlotFiller.cpp +++ lib/Target/Lanai/LanaiDelaySlotFiller.cpp @@ -105,7 +105,7 @@ // 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() && @@ -117,8 +117,7 @@ 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 { @@ -154,14 +153,14 @@ 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()) Index: lib/Target/X86/X86FixupSetCC.cpp =================================================================== --- lib/Target/X86/X86FixupSetCC.cpp +++ lib/Target/X86/X86FixupSetCC.cpp @@ -99,7 +99,8 @@ 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())) Index: lib/Transforms/Scalar/LoopRerollPass.cpp =================================================================== --- lib/Transforms/Scalar/LoopRerollPass.cpp +++ lib/Transforms/Scalar/LoopRerollPass.cpp @@ -1412,13 +1412,12 @@ 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; } Index: lib/Transforms/Scalar/RewriteStatepointsForGC.cpp =================================================================== --- lib/Transforms/Scalar/RewriteStatepointsForGC.cpp +++ lib/Transforms/Scalar/RewriteStatepointsForGC.cpp @@ -2543,8 +2543,8 @@ // 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()); } Index: lib/Transforms/Vectorize/SLPVectorizer.cpp =================================================================== --- lib/Transforms/Vectorize/SLPVectorizer.cpp +++ lib/Transforms/Vectorize/SLPVectorizer.cpp @@ -1844,9 +1844,9 @@ ); // 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(); @@ -3020,9 +3020,10 @@ } // 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) { Index: unittests/ADT/CMakeLists.txt =================================================================== --- unittests/ADT/CMakeLists.txt +++ unittests/ADT/CMakeLists.txt @@ -19,6 +19,7 @@ HashingTest.cpp ilistTestTemp.cpp IListBaseTest.cpp + IListIteratorTest.cpp IListNodeBaseTest.cpp IListSentinelTest.cpp ImmutableMapTest.cpp Index: unittests/ADT/IListIteratorTest.cpp =================================================================== --- /dev/null +++ unittests/ADT/IListIteratorTest.cpp @@ -0,0 +1,149 @@ +//===- 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 {}; + +TEST(IListIteratorTest, DefaultConstructor) { + iplist::iterator I; + iplist::reverse_iterator RI; + iplist::const_iterator CI; + iplist::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 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::iterator I; + iplist::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 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 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 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 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