From 299918ad4813ded5eb717c0c4898eb67205d880b Mon Sep 17 00:00:00 2001 From: Benjamin Kramer Date: Mon, 10 Feb 2014 14:17:42 +0000 Subject: Make succ_iterator a real random access iterator and clean up a couple of users. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@201088 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/Support/CFG.h | 52 +++++++++++++++++++++----------- lib/Analysis/CFG.cpp | 6 ++-- lib/Analysis/TargetTransformInfo.cpp | 7 +---- lib/Transforms/Scalar/GVN.cpp | 3 +- unittests/Analysis/CFGTest.cpp | 57 ++++++++++++++++++++++-------------- 5 files changed, 74 insertions(+), 51 deletions(-) diff --git a/include/llvm/Support/CFG.h b/include/llvm/Support/CFG.h index a9427793ac..c0733ca859 100644 --- a/include/llvm/Support/CFG.h +++ b/include/llvm/Support/CFG.h @@ -101,23 +101,45 @@ inline const_pred_iterator pred_end(const BasicBlock *BB) { //===----------------------------------------------------------------------===// template // Successor Iterator -class SuccIterator : public std::iterator { +class SuccIterator : public std::iterator { + typedef std::iterator + super; + +public: + typedef typename super::pointer pointer; + typedef typename super::reference reference; + +private: const Term_ Term; unsigned idx; - typedef std::iterator super; typedef SuccIterator Self; inline bool index_is_valid(int idx) { return idx >= 0 && (unsigned) idx < Term->getNumSuccessors(); } -public: - typedef typename super::pointer pointer; - typedef typename super::reference reference; - // TODO: This can be random access iterator, only operator[] missing. + /// \brief Proxy object to allow write access in operator[] + class SuccessorProxy { + Self it; + + public: + explicit SuccessorProxy(const Self &it) : it(it) {} + + SuccessorProxy &operator=(SuccessorProxy r) { + *this = reference(r); + return *this; + } + + SuccessorProxy &operator=(reference r) { + it.Term->setSuccessor(it.idx, r); + return *this; + } + operator reference() const { return *it; } + }; + +public: explicit inline SuccIterator(Term_ T) : Term(T), idx(0) {// begin iterator } inline SuccIterator(Term_ T, bool) // end iterator @@ -206,15 +228,11 @@ public: return distance; } - // This works for read access, however write access is difficult as changes - // to Term are only possible with Term->setSuccessor(idx). Pointers that can - // be modified are not available. - // - // inline pointer operator[](int offset) { - // Self tmp = *this; - // tmp += offset; - // return tmp.operator*(); - // } + inline SuccessorProxy operator[](int offset) { + Self tmp = *this; + tmp += offset; + return SuccessorProxy(tmp); + } /// Get the source BB of this iterator. inline BB_ *getSource() { diff --git a/lib/Analysis/CFG.cpp b/lib/Analysis/CFG.cpp index 050952fc44..9ebbb67849 100644 --- a/lib/Analysis/CFG.cpp +++ b/lib/Analysis/CFG.cpp @@ -168,8 +168,7 @@ static bool isPotentiallyReachableInner(SmallVectorImpl &Worklist, // ignoring any other blocks inside the loop body. Outer->getExitBlocks(Worklist); } else { - for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) - Worklist.push_back(*I); + Worklist.append(succ_begin(BB), succ_end(BB)); } } while (!Worklist.empty()); @@ -222,8 +221,7 @@ bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B, return false; // Otherwise, continue doing the normal per-BB CFG walk. - for (succ_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) - Worklist.push_back(*I); + Worklist.append(succ_begin(BB), succ_end(BB)); if (Worklist.empty()) { // We've proven that there's no path! diff --git a/lib/Analysis/TargetTransformInfo.cpp b/lib/Analysis/TargetTransformInfo.cpp index decb9aec4d..ac65437f0c 100644 --- a/lib/Analysis/TargetTransformInfo.cpp +++ b/lib/Analysis/TargetTransformInfo.cpp @@ -437,12 +437,7 @@ struct NoTTI LLVM_FINAL : ImmutablePass, TargetTransformInfo { return TopTTI->getCallCost(cast(FTy), CS.arg_size()); } - SmallVector Arguments; - for (ImmutableCallSite::arg_iterator AI = CS.arg_begin(), - AE = CS.arg_end(); - AI != AE; ++AI) - Arguments.push_back(*AI); - + SmallVector Arguments(CS.arg_begin(), CS.arg_end()); return TopTTI->getCallCost(F, Arguments); } diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp index 955ea1b7fe..3acf92b8e6 100644 --- a/lib/Transforms/Scalar/GVN.cpp +++ b/lib/Transforms/Scalar/GVN.cpp @@ -817,8 +817,7 @@ SpeculationFailure: // Mark as unavailable. EntryVal = 0; - for (succ_iterator I = succ_begin(Entry), E = succ_end(Entry); I != E; ++I) - BBWorklist.push_back(*I); + BBWorklist.append(succ_begin(Entry), succ_end(Entry)); } while (!BBWorklist.empty()); return false; diff --git a/unittests/Analysis/CFGTest.cpp b/unittests/Analysis/CFGTest.cpp index 76514f4d89..ab7e0a4ac0 100644 --- a/unittests/Analysis/CFGTest.cpp +++ b/unittests/Analysis/CFGTest.cpp @@ -115,7 +115,7 @@ protected: PM.add(P); PM.run(*M); } -private: + OwningPtr M; Instruction *A, *B; }; @@ -352,27 +352,40 @@ TEST_F(IsPotentiallyReachableTest, OneLoopAfterTheOtherInsideAThirdLoop) { ExpectPath(true); } +static const char *BranchInsideLoopIR = + "declare i1 @switch()\n" + "\n" + "define void @test() {\n" + "entry:\n" + " br label %loop\n" + "loop:\n" + " %x = call i1 @switch()\n" + " br i1 %x, label %nextloopblock, label %exit\n" + "nextloopblock:\n" + " %y = call i1 @switch()\n" + " br i1 %y, label %left, label %right\n" + "left:\n" + " %A = bitcast i8 undef to i8\n" + " br label %loop\n" + "right:\n" + " %B = bitcast i8 undef to i8\n" + " br label %loop\n" + "exit:\n" + " ret void\n" + "}"; + TEST_F(IsPotentiallyReachableTest, BranchInsideLoop) { - ParseAssembly( - "declare i1 @switch()\n" - "\n" - "define void @test() {\n" - "entry:\n" - " br label %loop\n" - "loop:\n" - " %x = call i1 @switch()\n" - " br i1 %x, label %nextloopblock, label %exit\n" - "nextloopblock:\n" - " %y = call i1 @switch()\n" - " br i1 %y, label %left, label %right\n" - "left:\n" - " %A = bitcast i8 undef to i8\n" - " br label %loop\n" - "right:\n" - " %B = bitcast i8 undef to i8\n" - " br label %loop\n" - "exit:\n" - " ret void\n" - "}"); + ParseAssembly(BranchInsideLoopIR); + ExpectPath(true); +} + +TEST_F(IsPotentiallyReachableTest, ModifyTest) { + ParseAssembly(BranchInsideLoopIR); + + succ_iterator S = succ_begin(++M->getFunction("test")->begin()); + BasicBlock *OldBB = S[0]; + S[0] = S[1]; + ExpectPath(false); + S[0] = OldBB; ExpectPath(true); } -- cgit v1.2.3