From 92541e359e4bdd2e9a149a2bb7d1519f77244655 Mon Sep 17 00:00:00 2001 From: Kristof Umann Date: Wed, 14 Aug 2019 17:05:55 +0000 Subject: [PATCH] [CFG] Introduce CFGElementRef, a wrapper that knows it's position in a CFGBlock Previously, collecting CFGElements in a set was practially impossible, because both CFGBlock::operator[] and both the iterators returned it by value. One workaround would be to collect the iterators instead, but they don't really capture the concept of an element, and elements from different iterator types are incomparable. This patch introduces CFGElementRef, a wrapper around a (CFGBlock, Index) pair, and a variety of new iterators and iterator ranges to solve this problem. I guess you could say that this patch took a couple iterations to get right :^) Differential Revision: https://reviews.llvm.org/D65196 llvm-svn: 368883 --- clang/include/clang/Analysis/CFG.h | 175 ++++++++++++++++++++++++++++++++++- clang/lib/Analysis/CFG.cpp | 4 + clang/unittests/Analysis/CFGTest.cpp | 133 ++++++++++++++++++++++++++ 3 files changed, 310 insertions(+), 2 deletions(-) diff --git a/clang/include/clang/Analysis/CFG.h b/clang/include/clang/Analysis/CFG.h index 2c38d51..4c375c7 100644 --- a/clang/include/clang/Analysis/CFG.h +++ b/clang/include/clang/Analysis/CFG.h @@ -610,6 +610,144 @@ class CFGBlock { 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 @@ public: 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 @@ public: 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 @@ public: 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 @@ public: *I = CFGScopeEnd(VD, S); return ++I; } - }; /// CFGCallback defines methods that should be called when a logical diff --git a/clang/lib/Analysis/CFG.cpp b/clang/lib/Analysis/CFG.cpp index b050347..fb64346 100644 --- a/clang/lib/Analysis/CFG.cpp +++ b/clang/lib/Analysis/CFG.cpp @@ -5615,6 +5615,10 @@ void CFG::print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const { 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 { diff --git a/clang/unittests/Analysis/CFGTest.cpp b/clang/unittests/Analysis/CFGTest.cpp index 7cd3da2..27071dc 100644 --- a/clang/unittests/Analysis/CFGTest.cpp +++ b/clang/unittests/Analysis/CFGTest.cpp @@ -67,6 +67,139 @@ TEST(CFG, IsLinear) { 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 -- 2.7.4