Index: cfe/trunk/include/clang/Analysis/CFG.h =================================================================== --- cfe/trunk/include/clang/Analysis/CFG.h +++ cfe/trunk/include/clang/Analysis/CFG.h @@ -610,6 +610,144 @@ bool empty() const { return Impl.empty(); } }; + /// A convenience class for comparing CFGElements, since methods of CFGBlock + /// like operator[] return CFGElements by value. This is practically a wrapper + /// around a (CFGBlock, Index) pair. + template class ElementRefImpl { + + template friend class ElementRefImpl; + + using CFGBlockPtr = + typename std::conditional::type; + + using CFGElementPtr = typename std::conditional::type; + + protected: + CFGBlockPtr Parent; + size_t Index; + + public: + ElementRefImpl(CFGBlockPtr Parent, size_t Index) + : Parent(Parent), Index(Index) {} + + template + ElementRefImpl(ElementRefImpl Other) + : ElementRefImpl(Other.Parent, Other.Index) {} + + size_t getIndexInBlock() const { return Index; } + + CFGBlockPtr getParent() { return Parent; } + CFGBlockPtr getParent() const { return Parent; } + + bool operator<(ElementRefImpl Other) const { + return std::make_pair(Parent, Index) < + std::make_pair(Other.Parent, Other.Index); + } + + bool operator==(ElementRefImpl Other) const { + return Parent == Other.Parent && Index == Other.Index; + } + + bool operator!=(ElementRefImpl Other) const { return !(*this == Other); } + CFGElement operator*() { return (*Parent)[Index]; } + CFGElementPtr operator->() { return &*(Parent->begin() + Index); } + }; + + template class ElementRefIterator { + + template + friend class ElementRefIterator; + + using CFGBlockRef = + typename std::conditional::type; + + using UnderlayingIteratorTy = typename std::conditional< + IsConst, + typename std::conditional::type, + typename std::conditional::type>::type; + + using IteratorTraits = typename std::iterator_traits; + using ElementRef = typename CFGBlock::ElementRefImpl; + + public: + using difference_type = typename IteratorTraits::difference_type; + using value_type = ElementRef; + using pointer = ElementRef *; + using iterator_category = typename IteratorTraits::iterator_category; + + private: + CFGBlockRef Parent; + UnderlayingIteratorTy Pos; + + public: + ElementRefIterator(CFGBlockRef Parent, UnderlayingIteratorTy Pos) + : Parent(Parent), Pos(Pos) {} + + template + ElementRefIterator(ElementRefIterator E) + : ElementRefIterator(E.Parent, E.Pos.base()) {} + + template + ElementRefIterator(ElementRefIterator E) + : ElementRefIterator(E.Parent, llvm::make_reverse_iterator(E.Pos)) {} + + bool operator<(ElementRefIterator Other) const { + assert(Parent == Other.Parent); + return Pos < Other.Pos; + } + + bool operator==(ElementRefIterator Other) const { + return Parent == Other.Parent && Pos == Other.Pos; + } + + bool operator!=(ElementRefIterator Other) const { + return !(*this == Other); + } + + private: + template + static size_t + getIndexInBlock(CFGBlock::ElementRefIterator E) { + return E.Parent->size() - (E.Pos - E.Parent->rbegin()) - 1; + } + + template + static size_t + getIndexInBlock(CFGBlock::ElementRefIterator E) { + return E.Pos - E.Parent->begin(); + } + + public: + value_type operator*() { return {Parent, getIndexInBlock(*this)}; } + + difference_type operator-(ElementRefIterator Other) const { + return Pos - Other.Pos; + } + + ElementRefIterator operator++() { + ++this->Pos; + return *this; + } + ElementRefIterator operator++(int) { + ElementRefIterator Ret = *this; + ++*this; + return Ret; + } + ElementRefIterator operator+(size_t count) { + this->Pos += count; + return *this; + } + ElementRefIterator operator-(size_t count) { + this->Pos -= count; + return *this; + } + }; + +public: /// The set of statements in the basic block. ElementList Elements; @@ -715,6 +853,8 @@ using reverse_iterator = ElementList::reverse_iterator; using const_reverse_iterator = ElementList::const_reverse_iterator; + size_t getIndexInCFG() const; + CFGElement front() const { return Elements.front(); } CFGElement back() const { return Elements.back(); } @@ -728,6 +868,38 @@ const_reverse_iterator rbegin() const { return Elements.rbegin(); } const_reverse_iterator rend() const { return Elements.rend(); } + using CFGElementRef = ElementRefImpl; + using ConstCFGElementRef = ElementRefImpl; + + using ref_iterator = ElementRefIterator; + using ref_iterator_range = llvm::iterator_range; + using const_ref_iterator = ElementRefIterator; + using const_ref_iterator_range = llvm::iterator_range; + + using reverse_ref_iterator = ElementRefIterator; + using reverse_ref_iterator_range = llvm::iterator_range; + + using const_reverse_ref_iterator = ElementRefIterator; + using const_reverse_ref_iterator_range = + llvm::iterator_range; + + ref_iterator ref_begin() { return {this, begin()}; } + ref_iterator ref_end() { return {this, end()}; } + const_ref_iterator ref_begin() const { return {this, begin()}; } + const_ref_iterator ref_end() const { return {this, end()}; } + + reverse_ref_iterator rref_begin() { return {this, rbegin()}; } + reverse_ref_iterator rref_end() { return {this, rend()}; } + const_reverse_ref_iterator rref_begin() const { return {this, rbegin()}; } + const_reverse_ref_iterator rref_end() const { return {this, rend()}; } + + ref_iterator_range refs() { return {ref_begin(), ref_end()}; } + const_ref_iterator_range refs() const { return {ref_begin(), ref_end()}; } + reverse_ref_iterator_range rrefs() { return {rref_begin(), rref_end()}; } + const_reverse_ref_iterator_range rrefs() const { + return {rref_begin(), rref_end()}; + } + unsigned size() const { return Elements.size(); } bool empty() const { return Elements.empty(); } @@ -898,7 +1070,7 @@ void printTerminator(raw_ostream &OS, const LangOptions &LO) const; void printTerminatorJson(raw_ostream &Out, const LangOptions &LO, bool AddQuotes) const; - + void printAsOperand(raw_ostream &OS, bool /*PrintType*/) { OS << "BB#" << getBlockID(); } @@ -1014,7 +1186,6 @@ *I = CFGScopeEnd(VD, S); return ++I; } - }; /// CFGCallback defines methods that should be called when a logical Index: cfe/trunk/lib/Analysis/CFG.cpp =================================================================== --- cfe/trunk/lib/Analysis/CFG.cpp +++ cfe/trunk/lib/Analysis/CFG.cpp @@ -5615,6 +5615,10 @@ OS.flush(); } +size_t CFGBlock::getIndexInCFG() const { + return llvm::find(*getParent(), this) - getParent()->begin(); +} + /// dump - A simply pretty printer of a CFGBlock that outputs to stderr. void CFGBlock::dump(const CFG* cfg, const LangOptions &LO, bool ShowColors) const { Index: cfe/trunk/unittests/Analysis/CFGTest.cpp =================================================================== --- cfe/trunk/unittests/Analysis/CFGTest.cpp +++ cfe/trunk/unittests/Analysis/CFGTest.cpp @@ -67,6 +67,139 @@ expectLinear(true, "void foo() { foo(); }"); // Recursion is not our problem. } +TEST(CFG, ElementRefIterator) { + const char *Code = R"(void f() { + int i; + int j; + i = 5; + i = 6; + j = 7; + })"; + + BuildResult B = BuildCFG(Code); + EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus()); + CFG *Cfg = B.getCFG(); + + // [B2 (ENTRY)] + // Succs (1): B1 + + // [B1] + // 1: int i; + // 2: int j; + // 3: i = 5 + // 4: i = 6 + // 5: j = 7 + // Preds (1): B2 + // Succs (1): B0 + + // [B0 (EXIT)] + // Preds (1): B1 + CFGBlock *MainBlock = *(Cfg->begin() + 1); + + constexpr CFGBlock::ref_iterator::difference_type MainBlockSize = 4; + + // The rest of this test looks totally insane, but there iterators are + // templates under the hood, to it's important to instantiate everything for + // proper converage. + + // Non-reverse, non-const version + size_t Index = 0; + for (CFGBlock::CFGElementRef ElementRef : MainBlock->refs()) { + EXPECT_EQ(ElementRef.getParent(), MainBlock); + EXPECT_EQ(ElementRef.getIndexInBlock(), Index); + EXPECT_TRUE(ElementRef->getAs()); + EXPECT_TRUE((*ElementRef).getAs()); + EXPECT_EQ(ElementRef.getParent(), MainBlock); + ++Index; + } + EXPECT_TRUE(*MainBlock->ref_begin() < *(MainBlock->ref_begin() + 1)); + EXPECT_TRUE(*MainBlock->ref_begin() == *MainBlock->ref_begin()); + EXPECT_FALSE(*MainBlock->ref_begin() != *MainBlock->ref_begin()); + + EXPECT_TRUE(MainBlock->ref_begin() < MainBlock->ref_begin() + 1); + EXPECT_TRUE(MainBlock->ref_begin() == MainBlock->ref_begin()); + EXPECT_FALSE(MainBlock->ref_begin() != MainBlock->ref_begin()); + EXPECT_EQ(MainBlock->ref_end() - MainBlock->ref_begin(), MainBlockSize + 1); + EXPECT_EQ(MainBlock->ref_end() - MainBlockSize - 1, MainBlock->ref_begin()); + EXPECT_EQ(MainBlock->ref_begin() + MainBlockSize + 1, MainBlock->ref_end()); + EXPECT_EQ(MainBlock->ref_begin()++, MainBlock->ref_begin()); + EXPECT_EQ(++(MainBlock->ref_begin()), MainBlock->ref_begin() + 1); + + // Non-reverse, non-const version + const CFGBlock *CMainBlock = MainBlock; + Index = 0; + for (CFGBlock::ConstCFGElementRef ElementRef : CMainBlock->refs()) { + EXPECT_EQ(ElementRef.getParent(), CMainBlock); + EXPECT_EQ(ElementRef.getIndexInBlock(), Index); + EXPECT_TRUE(ElementRef->getAs()); + EXPECT_TRUE((*ElementRef).getAs()); + EXPECT_EQ(ElementRef.getParent(), MainBlock); + ++Index; + } + EXPECT_TRUE(*CMainBlock->ref_begin() < *(CMainBlock->ref_begin() + 1)); + EXPECT_TRUE(*CMainBlock->ref_begin() == *CMainBlock->ref_begin()); + EXPECT_FALSE(*CMainBlock->ref_begin() != *CMainBlock->ref_begin()); + + EXPECT_TRUE(CMainBlock->ref_begin() < CMainBlock->ref_begin() + 1); + EXPECT_TRUE(CMainBlock->ref_begin() == CMainBlock->ref_begin()); + EXPECT_FALSE(CMainBlock->ref_begin() != CMainBlock->ref_begin()); + EXPECT_EQ(CMainBlock->ref_end() - CMainBlock->ref_begin(), MainBlockSize + 1); + EXPECT_EQ(CMainBlock->ref_end() - MainBlockSize - 1, CMainBlock->ref_begin()); + EXPECT_EQ(CMainBlock->ref_begin() + MainBlockSize + 1, CMainBlock->ref_end()); + EXPECT_EQ(CMainBlock->ref_begin()++, CMainBlock->ref_begin()); + EXPECT_EQ(++(CMainBlock->ref_begin()), CMainBlock->ref_begin() + 1); + + // Reverse, non-const version + Index = MainBlockSize; + for (CFGBlock::CFGElementRef ElementRef : MainBlock->rrefs()) { + llvm::errs() << Index << '\n'; + EXPECT_EQ(ElementRef.getParent(), MainBlock); + EXPECT_EQ(ElementRef.getIndexInBlock(), Index); + EXPECT_TRUE(ElementRef->getAs()); + EXPECT_TRUE((*ElementRef).getAs()); + EXPECT_EQ(ElementRef.getParent(), MainBlock); + --Index; + } + EXPECT_FALSE(*MainBlock->rref_begin() < *(MainBlock->rref_begin() + 1)); + EXPECT_TRUE(*MainBlock->rref_begin() == *MainBlock->rref_begin()); + EXPECT_FALSE(*MainBlock->rref_begin() != *MainBlock->rref_begin()); + + EXPECT_TRUE(MainBlock->rref_begin() < MainBlock->rref_begin() + 1); + EXPECT_TRUE(MainBlock->rref_begin() == MainBlock->rref_begin()); + EXPECT_FALSE(MainBlock->rref_begin() != MainBlock->rref_begin()); + EXPECT_EQ(MainBlock->rref_end() - MainBlock->rref_begin(), MainBlockSize + 1); + EXPECT_EQ(MainBlock->rref_end() - MainBlockSize - 1, MainBlock->rref_begin()); + EXPECT_EQ(MainBlock->rref_begin() + MainBlockSize + 1, MainBlock->rref_end()); + EXPECT_EQ(MainBlock->rref_begin()++, MainBlock->rref_begin()); + EXPECT_EQ(++(MainBlock->rref_begin()), MainBlock->rref_begin() + 1); + + // Reverse, const version + Index = MainBlockSize; + for (CFGBlock::ConstCFGElementRef ElementRef : CMainBlock->rrefs()) { + EXPECT_EQ(ElementRef.getParent(), CMainBlock); + EXPECT_EQ(ElementRef.getIndexInBlock(), Index); + EXPECT_TRUE(ElementRef->getAs()); + EXPECT_TRUE((*ElementRef).getAs()); + EXPECT_EQ(ElementRef.getParent(), MainBlock); + --Index; + } + EXPECT_FALSE(*CMainBlock->rref_begin() < *(CMainBlock->rref_begin() + 1)); + EXPECT_TRUE(*CMainBlock->rref_begin() == *CMainBlock->rref_begin()); + EXPECT_FALSE(*CMainBlock->rref_begin() != *CMainBlock->rref_begin()); + + EXPECT_TRUE(CMainBlock->rref_begin() < CMainBlock->rref_begin() + 1); + EXPECT_TRUE(CMainBlock->rref_begin() == CMainBlock->rref_begin()); + EXPECT_FALSE(CMainBlock->rref_begin() != CMainBlock->rref_begin()); + EXPECT_EQ(CMainBlock->rref_end() - CMainBlock->rref_begin(), + MainBlockSize + 1); + EXPECT_EQ(CMainBlock->rref_end() - MainBlockSize - 1, + CMainBlock->rref_begin()); + EXPECT_EQ(CMainBlock->rref_begin() + MainBlockSize + 1, + CMainBlock->rref_end()); + EXPECT_EQ(CMainBlock->rref_begin()++, CMainBlock->rref_begin()); + EXPECT_EQ(++(CMainBlock->rref_begin()), CMainBlock->rref_begin() + 1); +} + } // namespace } // namespace analysis } // namespace clang