Skip to content

Commit 92541e3

Browse files
SzelethusSzelethus
committedAug 14, 2019
[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
·
llvmorg-21-initllvmorg-10.0.0-rc1
1 parent 619172a commit 92541e3

File tree

3 files changed

+310
-2
lines changed

3 files changed

+310
-2
lines changed
 

Diff for: ‎clang/include/clang/Analysis/CFG.h

+173-2
Original file line numberDiff line numberDiff line change
@@ -610,6 +610,144 @@ class CFGBlock {
610610
bool empty() const { return Impl.empty(); }
611611
};
612612

613+
/// A convenience class for comparing CFGElements, since methods of CFGBlock
614+
/// like operator[] return CFGElements by value. This is practically a wrapper
615+
/// around a (CFGBlock, Index) pair.
616+
template <bool IsConst> class ElementRefImpl {
617+
618+
template <bool IsOtherConst> friend class ElementRefImpl;
619+
620+
using CFGBlockPtr =
621+
typename std::conditional<IsConst, const CFGBlock *, CFGBlock *>::type;
622+
623+
using CFGElementPtr = typename std::conditional<IsConst, const CFGElement *,
624+
CFGElement *>::type;
625+
626+
protected:
627+
CFGBlockPtr Parent;
628+
size_t Index;
629+
630+
public:
631+
ElementRefImpl(CFGBlockPtr Parent, size_t Index)
632+
: Parent(Parent), Index(Index) {}
633+
634+
template <bool IsOtherConst>
635+
ElementRefImpl(ElementRefImpl<IsOtherConst> Other)
636+
: ElementRefImpl(Other.Parent, Other.Index) {}
637+
638+
size_t getIndexInBlock() const { return Index; }
639+
640+
CFGBlockPtr getParent() { return Parent; }
641+
CFGBlockPtr getParent() const { return Parent; }
642+
643+
bool operator<(ElementRefImpl Other) const {
644+
return std::make_pair(Parent, Index) <
645+
std::make_pair(Other.Parent, Other.Index);
646+
}
647+
648+
bool operator==(ElementRefImpl Other) const {
649+
return Parent == Other.Parent && Index == Other.Index;
650+
}
651+
652+
bool operator!=(ElementRefImpl Other) const { return !(*this == Other); }
653+
CFGElement operator*() { return (*Parent)[Index]; }
654+
CFGElementPtr operator->() { return &*(Parent->begin() + Index); }
655+
};
656+
657+
template <bool IsReverse, bool IsConst> class ElementRefIterator {
658+
659+
template <bool IsOtherReverse, bool IsOtherConst>
660+
friend class ElementRefIterator;
661+
662+
using CFGBlockRef =
663+
typename std::conditional<IsConst, const CFGBlock *, CFGBlock *>::type;
664+
665+
using UnderlayingIteratorTy = typename std::conditional<
666+
IsConst,
667+
typename std::conditional<IsReverse,
668+
ElementList::const_reverse_iterator,
669+
ElementList::const_iterator>::type,
670+
typename std::conditional<IsReverse, ElementList::reverse_iterator,
671+
ElementList::iterator>::type>::type;
672+
673+
using IteratorTraits = typename std::iterator_traits<UnderlayingIteratorTy>;
674+
using ElementRef = typename CFGBlock::ElementRefImpl<IsConst>;
675+
676+
public:
677+
using difference_type = typename IteratorTraits::difference_type;
678+
using value_type = ElementRef;
679+
using pointer = ElementRef *;
680+
using iterator_category = typename IteratorTraits::iterator_category;
681+
682+
private:
683+
CFGBlockRef Parent;
684+
UnderlayingIteratorTy Pos;
685+
686+
public:
687+
ElementRefIterator(CFGBlockRef Parent, UnderlayingIteratorTy Pos)
688+
: Parent(Parent), Pos(Pos) {}
689+
690+
template <bool IsOtherConst>
691+
ElementRefIterator(ElementRefIterator<false, IsOtherConst> E)
692+
: ElementRefIterator(E.Parent, E.Pos.base()) {}
693+
694+
template <bool IsOtherConst>
695+
ElementRefIterator(ElementRefIterator<true, IsOtherConst> E)
696+
: ElementRefIterator(E.Parent, llvm::make_reverse_iterator(E.Pos)) {}
697+
698+
bool operator<(ElementRefIterator Other) const {
699+
assert(Parent == Other.Parent);
700+
return Pos < Other.Pos;
701+
}
702+
703+
bool operator==(ElementRefIterator Other) const {
704+
return Parent == Other.Parent && Pos == Other.Pos;
705+
}
706+
707+
bool operator!=(ElementRefIterator Other) const {
708+
return !(*this == Other);
709+
}
710+
711+
private:
712+
template <bool IsOtherConst>
713+
static size_t
714+
getIndexInBlock(CFGBlock::ElementRefIterator<true, IsOtherConst> E) {
715+
return E.Parent->size() - (E.Pos - E.Parent->rbegin()) - 1;
716+
}
717+
718+
template <bool IsOtherConst>
719+
static size_t
720+
getIndexInBlock(CFGBlock::ElementRefIterator<false, IsOtherConst> E) {
721+
return E.Pos - E.Parent->begin();
722+
}
723+
724+
public:
725+
value_type operator*() { return {Parent, getIndexInBlock(*this)}; }
726+
727+
difference_type operator-(ElementRefIterator Other) const {
728+
return Pos - Other.Pos;
729+
}
730+
731+
ElementRefIterator operator++() {
732+
++this->Pos;
733+
return *this;
734+
}
735+
ElementRefIterator operator++(int) {
736+
ElementRefIterator Ret = *this;
737+
++*this;
738+
return Ret;
739+
}
740+
ElementRefIterator operator+(size_t count) {
741+
this->Pos += count;
742+
return *this;
743+
}
744+
ElementRefIterator operator-(size_t count) {
745+
this->Pos -= count;
746+
return *this;
747+
}
748+
};
749+
750+
public:
613751
/// The set of statements in the basic block.
614752
ElementList Elements;
615753

@@ -715,6 +853,8 @@ class CFGBlock {
715853
using reverse_iterator = ElementList::reverse_iterator;
716854
using const_reverse_iterator = ElementList::const_reverse_iterator;
717855

856+
size_t getIndexInCFG() const;
857+
718858
CFGElement front() const { return Elements.front(); }
719859
CFGElement back() const { return Elements.back(); }
720860

@@ -728,6 +868,38 @@ class CFGBlock {
728868
const_reverse_iterator rbegin() const { return Elements.rbegin(); }
729869
const_reverse_iterator rend() const { return Elements.rend(); }
730870

871+
using CFGElementRef = ElementRefImpl<false>;
872+
using ConstCFGElementRef = ElementRefImpl<true>;
873+
874+
using ref_iterator = ElementRefIterator<false, false>;
875+
using ref_iterator_range = llvm::iterator_range<ref_iterator>;
876+
using const_ref_iterator = ElementRefIterator<false, true>;
877+
using const_ref_iterator_range = llvm::iterator_range<const_ref_iterator>;
878+
879+
using reverse_ref_iterator = ElementRefIterator<true, false>;
880+
using reverse_ref_iterator_range = llvm::iterator_range<reverse_ref_iterator>;
881+
882+
using const_reverse_ref_iterator = ElementRefIterator<true, true>;
883+
using const_reverse_ref_iterator_range =
884+
llvm::iterator_range<const_reverse_ref_iterator>;
885+
886+
ref_iterator ref_begin() { return {this, begin()}; }
887+
ref_iterator ref_end() { return {this, end()}; }
888+
const_ref_iterator ref_begin() const { return {this, begin()}; }
889+
const_ref_iterator ref_end() const { return {this, end()}; }
890+
891+
reverse_ref_iterator rref_begin() { return {this, rbegin()}; }
892+
reverse_ref_iterator rref_end() { return {this, rend()}; }
893+
const_reverse_ref_iterator rref_begin() const { return {this, rbegin()}; }
894+
const_reverse_ref_iterator rref_end() const { return {this, rend()}; }
895+
896+
ref_iterator_range refs() { return {ref_begin(), ref_end()}; }
897+
const_ref_iterator_range refs() const { return {ref_begin(), ref_end()}; }
898+
reverse_ref_iterator_range rrefs() { return {rref_begin(), rref_end()}; }
899+
const_reverse_ref_iterator_range rrefs() const {
900+
return {rref_begin(), rref_end()};
901+
}
902+
731903
unsigned size() const { return Elements.size(); }
732904
bool empty() const { return Elements.empty(); }
733905

@@ -898,7 +1070,7 @@ class CFGBlock {
8981070
void printTerminator(raw_ostream &OS, const LangOptions &LO) const;
8991071
void printTerminatorJson(raw_ostream &Out, const LangOptions &LO,
9001072
bool AddQuotes) const;
901-
1073+
9021074
void printAsOperand(raw_ostream &OS, bool /*PrintType*/) {
9031075
OS << "BB#" << getBlockID();
9041076
}
@@ -1014,7 +1186,6 @@ class CFGBlock {
10141186
*I = CFGScopeEnd(VD, S);
10151187
return ++I;
10161188
}
1017-
10181189
};
10191190

10201191
/// CFGCallback defines methods that should be called when a logical

Diff for: ‎clang/lib/Analysis/CFG.cpp

+4
Original file line numberDiff line numberDiff line change
@@ -5615,6 +5615,10 @@ void CFG::print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const {
56155615
OS.flush();
56165616
}
56175617

5618+
size_t CFGBlock::getIndexInCFG() const {
5619+
return llvm::find(*getParent(), this) - getParent()->begin();
5620+
}
5621+
56185622
/// dump - A simply pretty printer of a CFGBlock that outputs to stderr.
56195623
void CFGBlock::dump(const CFG* cfg, const LangOptions &LO,
56205624
bool ShowColors) const {

Diff for: ‎clang/unittests/Analysis/CFGTest.cpp

+133
Original file line numberDiff line numberDiff line change
@@ -67,6 +67,139 @@ TEST(CFG, IsLinear) {
6767
expectLinear(true, "void foo() { foo(); }"); // Recursion is not our problem.
6868
}
6969

70+
TEST(CFG, ElementRefIterator) {
71+
const char *Code = R"(void f() {
72+
int i;
73+
int j;
74+
i = 5;
75+
i = 6;
76+
j = 7;
77+
})";
78+
79+
BuildResult B = BuildCFG(Code);
80+
EXPECT_EQ(BuildResult::BuiltCFG, B.getStatus());
81+
CFG *Cfg = B.getCFG();
82+
83+
// [B2 (ENTRY)]
84+
// Succs (1): B1
85+
86+
// [B1]
87+
// 1: int i;
88+
// 2: int j;
89+
// 3: i = 5
90+
// 4: i = 6
91+
// 5: j = 7
92+
// Preds (1): B2
93+
// Succs (1): B0
94+
95+
// [B0 (EXIT)]
96+
// Preds (1): B1
97+
CFGBlock *MainBlock = *(Cfg->begin() + 1);
98+
99+
constexpr CFGBlock::ref_iterator::difference_type MainBlockSize = 4;
100+
101+
// The rest of this test looks totally insane, but there iterators are
102+
// templates under the hood, to it's important to instantiate everything for
103+
// proper converage.
104+
105+
// Non-reverse, non-const version
106+
size_t Index = 0;
107+
for (CFGBlock::CFGElementRef ElementRef : MainBlock->refs()) {
108+
EXPECT_EQ(ElementRef.getParent(), MainBlock);
109+
EXPECT_EQ(ElementRef.getIndexInBlock(), Index);
110+
EXPECT_TRUE(ElementRef->getAs<CFGStmt>());
111+
EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());
112+
EXPECT_EQ(ElementRef.getParent(), MainBlock);
113+
++Index;
114+
}
115+
EXPECT_TRUE(*MainBlock->ref_begin() < *(MainBlock->ref_begin() + 1));
116+
EXPECT_TRUE(*MainBlock->ref_begin() == *MainBlock->ref_begin());
117+
EXPECT_FALSE(*MainBlock->ref_begin() != *MainBlock->ref_begin());
118+
119+
EXPECT_TRUE(MainBlock->ref_begin() < MainBlock->ref_begin() + 1);
120+
EXPECT_TRUE(MainBlock->ref_begin() == MainBlock->ref_begin());
121+
EXPECT_FALSE(MainBlock->ref_begin() != MainBlock->ref_begin());
122+
EXPECT_EQ(MainBlock->ref_end() - MainBlock->ref_begin(), MainBlockSize + 1);
123+
EXPECT_EQ(MainBlock->ref_end() - MainBlockSize - 1, MainBlock->ref_begin());
124+
EXPECT_EQ(MainBlock->ref_begin() + MainBlockSize + 1, MainBlock->ref_end());
125+
EXPECT_EQ(MainBlock->ref_begin()++, MainBlock->ref_begin());
126+
EXPECT_EQ(++(MainBlock->ref_begin()), MainBlock->ref_begin() + 1);
127+
128+
// Non-reverse, non-const version
129+
const CFGBlock *CMainBlock = MainBlock;
130+
Index = 0;
131+
for (CFGBlock::ConstCFGElementRef ElementRef : CMainBlock->refs()) {
132+
EXPECT_EQ(ElementRef.getParent(), CMainBlock);
133+
EXPECT_EQ(ElementRef.getIndexInBlock(), Index);
134+
EXPECT_TRUE(ElementRef->getAs<CFGStmt>());
135+
EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());
136+
EXPECT_EQ(ElementRef.getParent(), MainBlock);
137+
++Index;
138+
}
139+
EXPECT_TRUE(*CMainBlock->ref_begin() < *(CMainBlock->ref_begin() + 1));
140+
EXPECT_TRUE(*CMainBlock->ref_begin() == *CMainBlock->ref_begin());
141+
EXPECT_FALSE(*CMainBlock->ref_begin() != *CMainBlock->ref_begin());
142+
143+
EXPECT_TRUE(CMainBlock->ref_begin() < CMainBlock->ref_begin() + 1);
144+
EXPECT_TRUE(CMainBlock->ref_begin() == CMainBlock->ref_begin());
145+
EXPECT_FALSE(CMainBlock->ref_begin() != CMainBlock->ref_begin());
146+
EXPECT_EQ(CMainBlock->ref_end() - CMainBlock->ref_begin(), MainBlockSize + 1);
147+
EXPECT_EQ(CMainBlock->ref_end() - MainBlockSize - 1, CMainBlock->ref_begin());
148+
EXPECT_EQ(CMainBlock->ref_begin() + MainBlockSize + 1, CMainBlock->ref_end());
149+
EXPECT_EQ(CMainBlock->ref_begin()++, CMainBlock->ref_begin());
150+
EXPECT_EQ(++(CMainBlock->ref_begin()), CMainBlock->ref_begin() + 1);
151+
152+
// Reverse, non-const version
153+
Index = MainBlockSize;
154+
for (CFGBlock::CFGElementRef ElementRef : MainBlock->rrefs()) {
155+
llvm::errs() << Index << '\n';
156+
EXPECT_EQ(ElementRef.getParent(), MainBlock);
157+
EXPECT_EQ(ElementRef.getIndexInBlock(), Index);
158+
EXPECT_TRUE(ElementRef->getAs<CFGStmt>());
159+
EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());
160+
EXPECT_EQ(ElementRef.getParent(), MainBlock);
161+
--Index;
162+
}
163+
EXPECT_FALSE(*MainBlock->rref_begin() < *(MainBlock->rref_begin() + 1));
164+
EXPECT_TRUE(*MainBlock->rref_begin() == *MainBlock->rref_begin());
165+
EXPECT_FALSE(*MainBlock->rref_begin() != *MainBlock->rref_begin());
166+
167+
EXPECT_TRUE(MainBlock->rref_begin() < MainBlock->rref_begin() + 1);
168+
EXPECT_TRUE(MainBlock->rref_begin() == MainBlock->rref_begin());
169+
EXPECT_FALSE(MainBlock->rref_begin() != MainBlock->rref_begin());
170+
EXPECT_EQ(MainBlock->rref_end() - MainBlock->rref_begin(), MainBlockSize + 1);
171+
EXPECT_EQ(MainBlock->rref_end() - MainBlockSize - 1, MainBlock->rref_begin());
172+
EXPECT_EQ(MainBlock->rref_begin() + MainBlockSize + 1, MainBlock->rref_end());
173+
EXPECT_EQ(MainBlock->rref_begin()++, MainBlock->rref_begin());
174+
EXPECT_EQ(++(MainBlock->rref_begin()), MainBlock->rref_begin() + 1);
175+
176+
// Reverse, const version
177+
Index = MainBlockSize;
178+
for (CFGBlock::ConstCFGElementRef ElementRef : CMainBlock->rrefs()) {
179+
EXPECT_EQ(ElementRef.getParent(), CMainBlock);
180+
EXPECT_EQ(ElementRef.getIndexInBlock(), Index);
181+
EXPECT_TRUE(ElementRef->getAs<CFGStmt>());
182+
EXPECT_TRUE((*ElementRef).getAs<CFGStmt>());
183+
EXPECT_EQ(ElementRef.getParent(), MainBlock);
184+
--Index;
185+
}
186+
EXPECT_FALSE(*CMainBlock->rref_begin() < *(CMainBlock->rref_begin() + 1));
187+
EXPECT_TRUE(*CMainBlock->rref_begin() == *CMainBlock->rref_begin());
188+
EXPECT_FALSE(*CMainBlock->rref_begin() != *CMainBlock->rref_begin());
189+
190+
EXPECT_TRUE(CMainBlock->rref_begin() < CMainBlock->rref_begin() + 1);
191+
EXPECT_TRUE(CMainBlock->rref_begin() == CMainBlock->rref_begin());
192+
EXPECT_FALSE(CMainBlock->rref_begin() != CMainBlock->rref_begin());
193+
EXPECT_EQ(CMainBlock->rref_end() - CMainBlock->rref_begin(),
194+
MainBlockSize + 1);
195+
EXPECT_EQ(CMainBlock->rref_end() - MainBlockSize - 1,
196+
CMainBlock->rref_begin());
197+
EXPECT_EQ(CMainBlock->rref_begin() + MainBlockSize + 1,
198+
CMainBlock->rref_end());
199+
EXPECT_EQ(CMainBlock->rref_begin()++, CMainBlock->rref_begin());
200+
EXPECT_EQ(++(CMainBlock->rref_begin()), CMainBlock->rref_begin() + 1);
201+
}
202+
70203
} // namespace
71204
} // namespace analysis
72205
} // namespace clang

0 commit comments

Comments
 (0)
Please sign in to comment.