/Users/buildslave/jenkins/workspace/coverage/llvm-project/clang/include/clang/Analysis/CFG.h
Line | Count | Source (jump to first uncovered line) |
1 | | //===- CFG.h - Classes for representing and building CFGs -------*- C++ -*-===// |
2 | | // |
3 | | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | | // See https://llvm.org/LICENSE.txt for license information. |
5 | | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | // |
9 | | // This file defines the CFG and CFGBuilder classes for representing and |
10 | | // building Control-Flow Graphs (CFGs) from ASTs. |
11 | | // |
12 | | //===----------------------------------------------------------------------===// |
13 | | |
14 | | #ifndef LLVM_CLANG_ANALYSIS_CFG_H |
15 | | #define LLVM_CLANG_ANALYSIS_CFG_H |
16 | | |
17 | | #include "clang/Analysis/Support/BumpVector.h" |
18 | | #include "clang/Analysis/ConstructionContext.h" |
19 | | #include "clang/AST/ExprCXX.h" |
20 | | #include "clang/AST/ExprObjC.h" |
21 | | #include "clang/Basic/LLVM.h" |
22 | | #include "llvm/ADT/DenseMap.h" |
23 | | #include "llvm/ADT/GraphTraits.h" |
24 | | #include "llvm/ADT/None.h" |
25 | | #include "llvm/ADT/Optional.h" |
26 | | #include "llvm/ADT/PointerIntPair.h" |
27 | | #include "llvm/ADT/iterator_range.h" |
28 | | #include "llvm/Support/Allocator.h" |
29 | | #include "llvm/Support/raw_ostream.h" |
30 | | #include <bitset> |
31 | | #include <cassert> |
32 | | #include <cstddef> |
33 | | #include <iterator> |
34 | | #include <memory> |
35 | | #include <vector> |
36 | | |
37 | | namespace clang { |
38 | | |
39 | | class ASTContext; |
40 | | class BinaryOperator; |
41 | | class CFG; |
42 | | class CXXBaseSpecifier; |
43 | | class CXXBindTemporaryExpr; |
44 | | class CXXCtorInitializer; |
45 | | class CXXDeleteExpr; |
46 | | class CXXDestructorDecl; |
47 | | class CXXNewExpr; |
48 | | class CXXRecordDecl; |
49 | | class Decl; |
50 | | class FieldDecl; |
51 | | class LangOptions; |
52 | | class VarDecl; |
53 | | |
54 | | /// Represents a top-level expression in a basic block. |
55 | | class CFGElement { |
56 | | public: |
57 | | enum Kind { |
58 | | // main kind |
59 | | Initializer, |
60 | | ScopeBegin, |
61 | | ScopeEnd, |
62 | | NewAllocator, |
63 | | LifetimeEnds, |
64 | | LoopExit, |
65 | | // stmt kind |
66 | | Statement, |
67 | | Constructor, |
68 | | CXXRecordTypedCall, |
69 | | STMT_BEGIN = Statement, |
70 | | STMT_END = CXXRecordTypedCall, |
71 | | // dtor kind |
72 | | AutomaticObjectDtor, |
73 | | DeleteDtor, |
74 | | BaseDtor, |
75 | | MemberDtor, |
76 | | TemporaryDtor, |
77 | | DTOR_BEGIN = AutomaticObjectDtor, |
78 | | DTOR_END = TemporaryDtor |
79 | | }; |
80 | | |
81 | | protected: |
82 | | // The int bits are used to mark the kind. |
83 | | llvm::PointerIntPair<void *, 2> Data1; |
84 | | llvm::PointerIntPair<void *, 2> Data2; |
85 | | |
86 | | CFGElement(Kind kind, const void *Ptr1, const void *Ptr2 = nullptr) |
87 | | : Data1(const_cast<void*>(Ptr1), ((unsigned) kind) & 0x3), |
88 | 4.29M | Data2(const_cast<void*>(Ptr2), (((unsigned) kind) >> 2) & 0x3) { |
89 | 4.29M | assert(getKind() == kind); |
90 | 4.29M | } |
91 | | |
92 | 5.27M | CFGElement() = default; |
93 | | |
94 | | public: |
95 | | /// Convert to the specified CFGElement type, asserting that this |
96 | | /// CFGElement is of the desired type. |
97 | | template<typename T> |
98 | 3.23M | T castAs() const { |
99 | 3.23M | assert(T::isKind(*this)); |
100 | 0 | T t; |
101 | 3.23M | CFGElement& e = t; |
102 | 3.23M | e = *this; |
103 | 3.23M | return t; |
104 | 3.23M | } clang::CFGInitializer clang::CFGElement::castAs<clang::CFGInitializer>() const Line | Count | Source | 98 | 11.9k | T castAs() const { | 99 | 11.9k | assert(T::isKind(*this)); | 100 | 0 | T t; | 101 | 11.9k | CFGElement& e = t; | 102 | 11.9k | e = *this; | 103 | 11.9k | return t; | 104 | 11.9k | } |
clang::CFGLifetimeEnds clang::CFGElement::castAs<clang::CFGLifetimeEnds>() const Line | Count | Source | 98 | 82 | T castAs() const { | 99 | 82 | assert(T::isKind(*this)); | 100 | 0 | T t; | 101 | 82 | CFGElement& e = t; | 102 | 82 | e = *this; | 103 | 82 | return t; | 104 | 82 | } |
clang::CFGLoopExit clang::CFGElement::castAs<clang::CFGLoopExit>() const Line | Count | Source | 98 | 161 | T castAs() const { | 99 | 161 | assert(T::isKind(*this)); | 100 | 0 | T t; | 101 | 161 | CFGElement& e = t; | 102 | 161 | e = *this; | 103 | 161 | return t; | 104 | 161 | } |
clang::CFGScopeBegin clang::CFGElement::castAs<clang::CFGScopeBegin>() const Line | Count | Source | 98 | 46 | T castAs() const { | 99 | 46 | assert(T::isKind(*this)); | 100 | 0 | T t; | 101 | 46 | CFGElement& e = t; | 102 | 46 | e = *this; | 103 | 46 | return t; | 104 | 46 | } |
clang::CFGScopeEnd clang::CFGElement::castAs<clang::CFGScopeEnd>() const Line | Count | Source | 98 | 78 | T castAs() const { | 99 | 78 | assert(T::isKind(*this)); | 100 | 0 | T t; | 101 | 78 | CFGElement& e = t; | 102 | 78 | e = *this; | 103 | 78 | return t; | 104 | 78 | } |
clang::CFGNewAllocator clang::CFGElement::castAs<clang::CFGNewAllocator>() const Line | Count | Source | 98 | 1.29k | T castAs() const { | 99 | 1.29k | assert(T::isKind(*this)); | 100 | 0 | T t; | 101 | 1.29k | CFGElement& e = t; | 102 | 1.29k | e = *this; | 103 | 1.29k | return t; | 104 | 1.29k | } |
clang::CFGBaseDtor clang::CFGElement::castAs<clang::CFGBaseDtor>() const Line | Count | Source | 98 | 134 | T castAs() const { | 99 | 134 | assert(T::isKind(*this)); | 100 | 0 | T t; | 101 | 134 | CFGElement& e = t; | 102 | 134 | e = *this; | 103 | 134 | return t; | 104 | 134 | } |
clang::CFGMemberDtor clang::CFGElement::castAs<clang::CFGMemberDtor>() const Line | Count | Source | 98 | 58 | T castAs() const { | 99 | 58 | assert(T::isKind(*this)); | 100 | 0 | T t; | 101 | 58 | CFGElement& e = t; | 102 | 58 | e = *this; | 103 | 58 | return t; | 104 | 58 | } |
clang::CFGDeleteDtor clang::CFGElement::castAs<clang::CFGDeleteDtor>() const Line | Count | Source | 98 | 126 | T castAs() const { | 99 | 126 | assert(T::isKind(*this)); | 100 | 0 | T t; | 101 | 126 | CFGElement& e = t; | 102 | 126 | e = *this; | 103 | 126 | return t; | 104 | 126 | } |
clang::CFGTemporaryDtor clang::CFGElement::castAs<clang::CFGTemporaryDtor>() const Line | Count | Source | 98 | 1.99k | T castAs() const { | 99 | 1.99k | assert(T::isKind(*this)); | 100 | 0 | T t; | 101 | 1.99k | CFGElement& e = t; | 102 | 1.99k | e = *this; | 103 | 1.99k | return t; | 104 | 1.99k | } |
clang::CFGStmt clang::CFGElement::castAs<clang::CFGStmt>() const Line | Count | Source | 98 | 3.21M | T castAs() const { | 99 | 3.21M | assert(T::isKind(*this)); | 100 | 0 | T t; | 101 | 3.21M | CFGElement& e = t; | 102 | 3.21M | e = *this; | 103 | 3.21M | return t; | 104 | 3.21M | } |
clang::CFGAutomaticObjDtor clang::CFGElement::castAs<clang::CFGAutomaticObjDtor>() const Line | Count | Source | 98 | 2.03k | T castAs() const { | 99 | 2.03k | assert(T::isKind(*this)); | 100 | 0 | T t; | 101 | 2.03k | CFGElement& e = t; | 102 | 2.03k | e = *this; | 103 | 2.03k | return t; | 104 | 2.03k | } |
clang::CFGImplicitDtor clang::CFGElement::castAs<clang::CFGImplicitDtor>() const Line | Count | Source | 98 | 1.99k | T castAs() const { | 99 | 1.99k | assert(T::isKind(*this)); | 100 | 0 | T t; | 101 | 1.99k | CFGElement& e = t; | 102 | 1.99k | e = *this; | 103 | 1.99k | return t; | 104 | 1.99k | } |
|
105 | | |
106 | | /// Convert to the specified CFGElement type, returning None if this |
107 | | /// CFGElement is not of the desired type. |
108 | | template<typename T> |
109 | 2.61M | Optional<T> getAs() const { |
110 | 2.61M | if (!T::isKind(*this)) |
111 | 566k | return None; |
112 | 2.04M | T t; |
113 | 2.04M | CFGElement& e = t; |
114 | 2.04M | e = *this; |
115 | 2.04M | return t; |
116 | 2.61M | } llvm::Optional<clang::CFGCXXRecordTypedCall> clang::CFGElement::getAs<clang::CFGCXXRecordTypedCall>() const Line | Count | Source | 109 | 45.2k | Optional<T> getAs() const { | 110 | 45.2k | if (!T::isKind(*this)) | 111 | 38.5k | return None; | 112 | 6.61k | T t; | 113 | 6.61k | CFGElement& e = t; | 114 | 6.61k | e = *this; | 115 | 6.61k | return t; | 116 | 45.2k | } |
llvm::Optional<clang::CFGConstructor> clang::CFGElement::getAs<clang::CFGConstructor>() const Line | Count | Source | 109 | 34.5k | Optional<T> getAs() const { | 110 | 34.5k | if (!T::isKind(*this)) | 111 | 1.07k | return None; | 112 | 33.4k | T t; | 113 | 33.4k | CFGElement& e = t; | 114 | 33.4k | e = *this; | 115 | 33.4k | return t; | 116 | 34.5k | } |
llvm::Optional<clang::CFGStmt> clang::CFGElement::getAs<clang::CFGStmt>() const Line | Count | Source | 109 | 2.01M | Optional<T> getAs() const { | 110 | 2.01M | if (!T::isKind(*this)) | 111 | 19.3k | return None; | 112 | 2.00M | T t; | 113 | 2.00M | CFGElement& e = t; | 114 | 2.00M | e = *this; | 115 | 2.00M | return t; | 116 | 2.01M | } |
llvm::Optional<clang::CFGImplicitDtor> clang::CFGElement::getAs<clang::CFGImplicitDtor>() const Line | Count | Source | 109 | 1.48k | Optional<T> getAs() const { | 110 | 1.48k | if (!T::isKind(*this)) | 111 | 0 | return None; | 112 | 1.48k | T t; | 113 | 1.48k | CFGElement& e = t; | 114 | 1.48k | e = *this; | 115 | 1.48k | return t; | 116 | 1.48k | } |
Unexecuted instantiation: llvm::Optional<clang::CFGTemporaryDtor> clang::CFGElement::getAs<clang::CFGTemporaryDtor>() const llvm::Optional<clang::CFGDeleteDtor> clang::CFGElement::getAs<clang::CFGDeleteDtor>() const Line | Count | Source | 109 | 610 | Optional<T> getAs() const { | 110 | 610 | if (!T::isKind(*this)) | 111 | 518 | return None; | 112 | 92 | T t; | 113 | 92 | CFGElement& e = t; | 114 | 92 | e = *this; | 115 | 92 | return t; | 116 | 610 | } |
llvm::Optional<clang::CFGBaseDtor> clang::CFGElement::getAs<clang::CFGBaseDtor>() const Line | Count | Source | 109 | 1.48k | Optional<T> getAs() const { | 110 | 1.48k | if (!T::isKind(*this)) | 111 | 1.30k | return None; | 112 | 182 | T t; | 113 | 182 | CFGElement& e = t; | 114 | 182 | e = *this; | 115 | 182 | return t; | 116 | 1.48k | } |
llvm::Optional<clang::CFGAutomaticObjDtor> clang::CFGElement::getAs<clang::CFGAutomaticObjDtor>() const Line | Count | Source | 109 | 507k | Optional<T> getAs() const { | 110 | 507k | if (!T::isKind(*this)) | 111 | 505k | return None; | 112 | 1.81k | T t; | 113 | 1.81k | CFGElement& e = t; | 114 | 1.81k | e = *this; | 115 | 1.81k | return t; | 116 | 507k | } |
llvm::Optional<clang::CFGNewAllocator> clang::CFGElement::getAs<clang::CFGNewAllocator>() const Line | Count | Source | 109 | 1 | Optional<T> getAs() const { | 110 | 1 | if (!T::isKind(*this)) | 111 | 0 | return None; | 112 | 1 | T t; | 113 | 1 | CFGElement& e = t; | 114 | 1 | e = *this; | 115 | 1 | return t; | 116 | 1 | } |
llvm::Optional<clang::CFGInitializer> clang::CFGElement::getAs<clang::CFGInitializer>() const Line | Count | Source | 109 | 12 | Optional<T> getAs() const { | 110 | 12 | if (!T::isKind(*this)) | 111 | 0 | return None; | 112 | 12 | T t; | 113 | 12 | CFGElement& e = t; | 114 | 12 | e = *this; | 115 | 12 | return t; | 116 | 12 | } |
|
117 | | |
118 | 26.9M | Kind getKind() const { |
119 | 26.9M | unsigned x = Data2.getInt(); |
120 | 26.9M | x <<= 2; |
121 | 26.9M | x |= Data1.getInt(); |
122 | 26.9M | return (Kind) x; |
123 | 26.9M | } |
124 | | |
125 | | void dumpToStream(llvm::raw_ostream &OS) const; |
126 | | |
127 | 0 | void dump() const { |
128 | 0 | dumpToStream(llvm::errs()); |
129 | 0 | } |
130 | | }; |
131 | | |
132 | | class CFGStmt : public CFGElement { |
133 | | public: |
134 | 4.26M | explicit CFGStmt(Stmt *S, Kind K = Statement) : CFGElement(K, S) { |
135 | 4.26M | assert(isKind(*this)); |
136 | 4.26M | } |
137 | | |
138 | 4.58M | const Stmt *getStmt() const { |
139 | 4.58M | return static_cast<const Stmt *>(Data1.getPointer()); |
140 | 4.58M | } |
141 | | |
142 | | private: |
143 | | friend class CFGElement; |
144 | | |
145 | 9.49M | static bool isKind(const CFGElement &E) { |
146 | 9.49M | return E.getKind() >= STMT_BEGIN && E.getKind() <= STMT_END9.48M ; |
147 | 9.49M | } |
148 | | |
149 | | protected: |
150 | 5.25M | CFGStmt() = default; |
151 | | }; |
152 | | |
153 | | /// Represents C++ constructor call. Maintains information necessary to figure |
154 | | /// out what memory is being initialized by the constructor expression. For now |
155 | | /// this is only used by the analyzer's CFG. |
156 | | class CFGConstructor : public CFGStmt { |
157 | | public: |
158 | | explicit CFGConstructor(CXXConstructExpr *CE, const ConstructionContext *C) |
159 | 24.4k | : CFGStmt(CE, Constructor) { |
160 | 24.4k | assert(C); |
161 | 0 | Data2.setPointer(const_cast<ConstructionContext *>(C)); |
162 | 24.4k | } |
163 | | |
164 | 33.4k | const ConstructionContext *getConstructionContext() const { |
165 | 33.4k | return static_cast<ConstructionContext *>(Data2.getPointer()); |
166 | 33.4k | } |
167 | | |
168 | | private: |
169 | | friend class CFGElement; |
170 | | |
171 | 33.4k | CFGConstructor() = default; |
172 | | |
173 | 34.5k | static bool isKind(const CFGElement &E) { |
174 | 34.5k | return E.getKind() == Constructor; |
175 | 34.5k | } |
176 | | }; |
177 | | |
178 | | /// Represents a function call that returns a C++ object by value. This, like |
179 | | /// constructor, requires a construction context in order to understand the |
180 | | /// storage of the returned object . In C such tracking is not necessary because |
181 | | /// no additional effort is required for destroying the object or modeling copy |
182 | | /// elision. Like CFGConstructor, this element is for now only used by the |
183 | | /// analyzer's CFG. |
184 | | class CFGCXXRecordTypedCall : public CFGStmt { |
185 | | public: |
186 | | /// Returns true when call expression \p CE needs to be represented |
187 | | /// by CFGCXXRecordTypedCall, as opposed to a regular CFGStmt. |
188 | 28.6k | static bool isCXXRecordTypedCall(Expr *E) { |
189 | 28.6k | assert(isa<CallExpr>(E) || isa<ObjCMessageExpr>(E)); |
190 | | // There is no such thing as reference-type expression. If the function |
191 | | // returns a reference, it'll return the respective lvalue or xvalue |
192 | | // instead, and we're only interested in objects. |
193 | 28.6k | return !E->isGLValue() && |
194 | 28.6k | E->getType().getCanonicalType()->getAsCXXRecordDecl()28.4k ; |
195 | 28.6k | } |
196 | | |
197 | | explicit CFGCXXRecordTypedCall(Expr *E, const ConstructionContext *C) |
198 | 8.03k | : CFGStmt(E, CXXRecordTypedCall) { |
199 | 8.03k | assert(isCXXRecordTypedCall(E)); |
200 | 0 | assert(C && (isa<TemporaryObjectConstructionContext>(C) || |
201 | | // These are possible in C++17 due to mandatory copy elision. |
202 | 8.03k | isa<ReturnedValueConstructionContext>(C) || |
203 | 8.03k | isa<VariableConstructionContext>(C) || |
204 | 8.03k | isa<ConstructorInitializerConstructionContext>(C) || |
205 | 8.03k | isa<ArgumentConstructionContext>(C))); |
206 | 0 | Data2.setPointer(const_cast<ConstructionContext *>(C)); |
207 | 8.03k | } |
208 | | |
209 | 6.61k | const ConstructionContext *getConstructionContext() const { |
210 | 6.61k | return static_cast<ConstructionContext *>(Data2.getPointer()); |
211 | 6.61k | } |
212 | | |
213 | | private: |
214 | | friend class CFGElement; |
215 | | |
216 | 6.61k | CFGCXXRecordTypedCall() = default; |
217 | | |
218 | 45.2k | static bool isKind(const CFGElement &E) { |
219 | 45.2k | return E.getKind() == CXXRecordTypedCall; |
220 | 45.2k | } |
221 | | }; |
222 | | |
223 | | /// Represents C++ base or member initializer from constructor's initialization |
224 | | /// list. |
225 | | class CFGInitializer : public CFGElement { |
226 | | public: |
227 | | explicit CFGInitializer(CXXCtorInitializer *initializer) |
228 | 15.3k | : CFGElement(Initializer, initializer) {} |
229 | | |
230 | 11.9k | CXXCtorInitializer* getInitializer() const { |
231 | 11.9k | return static_cast<CXXCtorInitializer*>(Data1.getPointer()); |
232 | 11.9k | } |
233 | | |
234 | | private: |
235 | | friend class CFGElement; |
236 | | |
237 | 11.9k | CFGInitializer() = default; |
238 | | |
239 | 11.9k | static bool isKind(const CFGElement &E) { |
240 | 11.9k | return E.getKind() == Initializer; |
241 | 11.9k | } |
242 | | }; |
243 | | |
244 | | /// Represents C++ allocator call. |
245 | | class CFGNewAllocator : public CFGElement { |
246 | | public: |
247 | | explicit CFGNewAllocator(const CXXNewExpr *S) |
248 | 1.90k | : CFGElement(NewAllocator, S) {} |
249 | | |
250 | | // Get the new expression. |
251 | 1.29k | const CXXNewExpr *getAllocatorExpr() const { |
252 | 1.29k | return static_cast<CXXNewExpr *>(Data1.getPointer()); |
253 | 1.29k | } |
254 | | |
255 | | private: |
256 | | friend class CFGElement; |
257 | | |
258 | 1.29k | CFGNewAllocator() = default; |
259 | | |
260 | 1.29k | static bool isKind(const CFGElement &elem) { |
261 | 1.29k | return elem.getKind() == NewAllocator; |
262 | 1.29k | } |
263 | | }; |
264 | | |
265 | | /// Represents the point where a loop ends. |
266 | | /// This element is is only produced when building the CFG for the static |
267 | | /// analyzer and hidden behind the 'cfg-loopexit' analyzer config flag. |
268 | | /// |
269 | | /// Note: a loop exit element can be reached even when the loop body was never |
270 | | /// entered. |
271 | | class CFGLoopExit : public CFGElement { |
272 | | public: |
273 | 254 | explicit CFGLoopExit(const Stmt *stmt) : CFGElement(LoopExit, stmt) {} |
274 | | |
275 | 161 | const Stmt *getLoopStmt() const { |
276 | 161 | return static_cast<Stmt *>(Data1.getPointer()); |
277 | 161 | } |
278 | | |
279 | | private: |
280 | | friend class CFGElement; |
281 | | |
282 | 161 | CFGLoopExit() = default; |
283 | | |
284 | 161 | static bool isKind(const CFGElement &elem) { |
285 | 161 | return elem.getKind() == LoopExit; |
286 | 161 | } |
287 | | }; |
288 | | |
289 | | /// Represents the point where the lifetime of an automatic object ends |
290 | | class CFGLifetimeEnds : public CFGElement { |
291 | | public: |
292 | | explicit CFGLifetimeEnds(const VarDecl *var, const Stmt *stmt) |
293 | 166 | : CFGElement(LifetimeEnds, var, stmt) {} |
294 | | |
295 | 82 | const VarDecl *getVarDecl() const { |
296 | 82 | return static_cast<VarDecl *>(Data1.getPointer()); |
297 | 82 | } |
298 | | |
299 | 0 | const Stmt *getTriggerStmt() const { |
300 | 0 | return static_cast<Stmt *>(Data2.getPointer()); |
301 | 0 | } |
302 | | |
303 | | private: |
304 | | friend class CFGElement; |
305 | | |
306 | 82 | CFGLifetimeEnds() = default; |
307 | | |
308 | 82 | static bool isKind(const CFGElement &elem) { |
309 | 82 | return elem.getKind() == LifetimeEnds; |
310 | 82 | } |
311 | | }; |
312 | | |
313 | | /// Represents beginning of a scope implicitly generated |
314 | | /// by the compiler on encountering a CompoundStmt |
315 | | class CFGScopeBegin : public CFGElement { |
316 | | public: |
317 | 46 | CFGScopeBegin() {} |
318 | | CFGScopeBegin(const VarDecl *VD, const Stmt *S) |
319 | 92 | : CFGElement(ScopeBegin, VD, S) {} |
320 | | |
321 | | // Get statement that triggered a new scope. |
322 | 0 | const Stmt *getTriggerStmt() const { |
323 | 0 | return static_cast<Stmt*>(Data2.getPointer()); |
324 | 0 | } |
325 | | |
326 | | // Get VD that triggered a new scope. |
327 | 46 | const VarDecl *getVarDecl() const { |
328 | 46 | return static_cast<VarDecl *>(Data1.getPointer()); |
329 | 46 | } |
330 | | |
331 | | private: |
332 | | friend class CFGElement; |
333 | 46 | static bool isKind(const CFGElement &E) { |
334 | 46 | Kind kind = E.getKind(); |
335 | 46 | return kind == ScopeBegin; |
336 | 46 | } |
337 | | }; |
338 | | |
339 | | /// Represents end of a scope implicitly generated by |
340 | | /// the compiler after the last Stmt in a CompoundStmt's body |
341 | | class CFGScopeEnd : public CFGElement { |
342 | | public: |
343 | 78 | CFGScopeEnd() {} |
344 | 158 | CFGScopeEnd(const VarDecl *VD, const Stmt *S) : CFGElement(ScopeEnd, VD, S) {} |
345 | | |
346 | 78 | const VarDecl *getVarDecl() const { |
347 | 78 | return static_cast<VarDecl *>(Data1.getPointer()); |
348 | 78 | } |
349 | | |
350 | 0 | const Stmt *getTriggerStmt() const { |
351 | 0 | return static_cast<Stmt *>(Data2.getPointer()); |
352 | 0 | } |
353 | | |
354 | | private: |
355 | | friend class CFGElement; |
356 | 78 | static bool isKind(const CFGElement &E) { |
357 | 78 | Kind kind = E.getKind(); |
358 | 78 | return kind == ScopeEnd; |
359 | 78 | } |
360 | | }; |
361 | | |
362 | | /// Represents C++ object destructor implicitly generated by compiler on various |
363 | | /// occasions. |
364 | | class CFGImplicitDtor : public CFGElement { |
365 | | protected: |
366 | 9.91k | CFGImplicitDtor() = default; |
367 | | |
368 | | CFGImplicitDtor(Kind kind, const void *data1, const void *data2 = nullptr) |
369 | 12.0k | : CFGElement(kind, data1, data2) { |
370 | 12.0k | assert(kind >= DTOR_BEGIN && kind <= DTOR_END); |
371 | 12.0k | } |
372 | | |
373 | | public: |
374 | | const CXXDestructorDecl *getDestructorDecl(ASTContext &astContext) const; |
375 | | bool isNoReturn(ASTContext &astContext) const; |
376 | | |
377 | | private: |
378 | | friend class CFGElement; |
379 | | |
380 | 3.48k | static bool isKind(const CFGElement &E) { |
381 | 3.48k | Kind kind = E.getKind(); |
382 | 3.48k | return kind >= DTOR_BEGIN && kind <= DTOR_END; |
383 | 3.48k | } |
384 | | }; |
385 | | |
386 | | /// Represents C++ object destructor implicitly generated for automatic object |
387 | | /// or temporary bound to const reference at the point of leaving its local |
388 | | /// scope. |
389 | | class CFGAutomaticObjDtor: public CFGImplicitDtor { |
390 | | public: |
391 | | CFGAutomaticObjDtor(const VarDecl *var, const Stmt *stmt) |
392 | 5.47k | : CFGImplicitDtor(AutomaticObjectDtor, var, stmt) {} |
393 | | |
394 | 2.62k | const VarDecl *getVarDecl() const { |
395 | 2.62k | return static_cast<VarDecl*>(Data1.getPointer()); |
396 | 2.62k | } |
397 | | |
398 | | // Get statement end of which triggered the destructor call. |
399 | 2.16k | const Stmt *getTriggerStmt() const { |
400 | 2.16k | return static_cast<Stmt*>(Data2.getPointer()); |
401 | 2.16k | } |
402 | | |
403 | | private: |
404 | | friend class CFGElement; |
405 | | |
406 | 3.84k | CFGAutomaticObjDtor() = default; |
407 | | |
408 | 509k | static bool isKind(const CFGElement &elem) { |
409 | 509k | return elem.getKind() == AutomaticObjectDtor; |
410 | 509k | } |
411 | | }; |
412 | | |
413 | | /// Represents C++ object destructor generated from a call to delete. |
414 | | class CFGDeleteDtor : public CFGImplicitDtor { |
415 | | public: |
416 | | CFGDeleteDtor(const CXXRecordDecl *RD, const CXXDeleteExpr *DE) |
417 | 234 | : CFGImplicitDtor(DeleteDtor, RD, DE) {} |
418 | | |
419 | 4 | const CXXRecordDecl *getCXXRecordDecl() const { |
420 | 4 | return static_cast<CXXRecordDecl*>(Data1.getPointer()); |
421 | 4 | } |
422 | | |
423 | | // Get Delete expression which triggered the destructor call. |
424 | 218 | const CXXDeleteExpr *getDeleteExpr() const { |
425 | 218 | return static_cast<CXXDeleteExpr *>(Data2.getPointer()); |
426 | 218 | } |
427 | | |
428 | | private: |
429 | | friend class CFGElement; |
430 | | |
431 | 218 | CFGDeleteDtor() = default; |
432 | | |
433 | 736 | static bool isKind(const CFGElement &elem) { |
434 | 736 | return elem.getKind() == DeleteDtor; |
435 | 736 | } |
436 | | }; |
437 | | |
438 | | /// Represents C++ object destructor implicitly generated for base object in |
439 | | /// destructor. |
440 | | class CFGBaseDtor : public CFGImplicitDtor { |
441 | | public: |
442 | | CFGBaseDtor(const CXXBaseSpecifier *base) |
443 | 530 | : CFGImplicitDtor(BaseDtor, base) {} |
444 | | |
445 | 134 | const CXXBaseSpecifier *getBaseSpecifier() const { |
446 | 134 | return static_cast<const CXXBaseSpecifier*>(Data1.getPointer()); |
447 | 134 | } |
448 | | |
449 | | private: |
450 | | friend class CFGElement; |
451 | | |
452 | 316 | CFGBaseDtor() = default; |
453 | | |
454 | 1.62k | static bool isKind(const CFGElement &E) { |
455 | 1.62k | return E.getKind() == BaseDtor; |
456 | 1.62k | } |
457 | | }; |
458 | | |
459 | | /// Represents C++ object destructor implicitly generated for member object in |
460 | | /// destructor. |
461 | | class CFGMemberDtor : public CFGImplicitDtor { |
462 | | public: |
463 | | CFGMemberDtor(const FieldDecl *field) |
464 | 135 | : CFGImplicitDtor(MemberDtor, field, nullptr) {} |
465 | | |
466 | 58 | const FieldDecl *getFieldDecl() const { |
467 | 58 | return static_cast<const FieldDecl*>(Data1.getPointer()); |
468 | 58 | } |
469 | | |
470 | | private: |
471 | | friend class CFGElement; |
472 | | |
473 | 58 | CFGMemberDtor() = default; |
474 | | |
475 | 58 | static bool isKind(const CFGElement &E) { |
476 | 58 | return E.getKind() == MemberDtor; |
477 | 58 | } |
478 | | }; |
479 | | |
480 | | /// Represents C++ object destructor implicitly generated at the end of full |
481 | | /// expression for temporary object. |
482 | | class CFGTemporaryDtor : public CFGImplicitDtor { |
483 | | public: |
484 | | CFGTemporaryDtor(CXXBindTemporaryExpr *expr) |
485 | 5.68k | : CFGImplicitDtor(TemporaryDtor, expr, nullptr) {} |
486 | | |
487 | 6.45k | const CXXBindTemporaryExpr *getBindTemporaryExpr() const { |
488 | 6.45k | return static_cast<const CXXBindTemporaryExpr *>(Data1.getPointer()); |
489 | 6.45k | } |
490 | | |
491 | | private: |
492 | | friend class CFGElement; |
493 | | |
494 | 1.99k | CFGTemporaryDtor() = default; |
495 | | |
496 | 1.99k | static bool isKind(const CFGElement &E) { |
497 | 1.99k | return E.getKind() == TemporaryDtor; |
498 | 1.99k | } |
499 | | }; |
500 | | |
501 | | /// Represents CFGBlock terminator statement. |
502 | | /// |
503 | | class CFGTerminator { |
504 | | public: |
505 | | enum Kind { |
506 | | /// A branch that corresponds to a statement in the code, |
507 | | /// such as an if-statement. |
508 | | StmtBranch, |
509 | | /// A branch in control flow of destructors of temporaries. In this case |
510 | | /// terminator statement is the same statement that branches control flow |
511 | | /// in evaluation of matching full expression. |
512 | | TemporaryDtorsBranch, |
513 | | /// A shortcut around virtual base initializers. It gets taken when |
514 | | /// virtual base classes have already been initialized by the constructor |
515 | | /// of the most derived class while we're in the base class. |
516 | | VirtualBaseBranch, |
517 | | |
518 | | /// Number of different kinds, for assertions. We subtract 1 so that |
519 | | /// to keep receiving compiler warnings when we don't cover all enum values |
520 | | /// in a switch. |
521 | | NumKindsMinusOne = VirtualBaseBranch |
522 | | }; |
523 | | |
524 | | private: |
525 | | static constexpr int KindBits = 2; |
526 | | static_assert((1 << KindBits) > NumKindsMinusOne, |
527 | | "Not enough room for kind!"); |
528 | | llvm::PointerIntPair<Stmt *, KindBits> Data; |
529 | | |
530 | | public: |
531 | 0 | CFGTerminator() { assert(!isValid()); } |
532 | 1.21M | CFGTerminator(Stmt *S, Kind K = StmtBranch) : Data(S, K) {} |
533 | | |
534 | 3.55k | bool isValid() const { return Data.getOpaqueValue() != nullptr; } |
535 | 44.8k | Stmt *getStmt() { return Data.getPointer(); } |
536 | 690k | const Stmt *getStmt() const { return Data.getPointer(); } |
537 | 331k | Kind getKind() const { return static_cast<Kind>(Data.getInt()); } |
538 | | |
539 | 10.1k | bool isStmtBranch() const { |
540 | 10.1k | return getKind() == StmtBranch; |
541 | 10.1k | } |
542 | 3.04k | bool isTemporaryDtorsBranch() const { |
543 | 3.04k | return getKind() == TemporaryDtorsBranch; |
544 | 3.04k | } |
545 | 316k | bool isVirtualBaseBranch() const { |
546 | 316k | return getKind() == VirtualBaseBranch; |
547 | 316k | } |
548 | | }; |
549 | | |
550 | | /// Represents a single basic block in a source-level CFG. |
551 | | /// It consists of: |
552 | | /// |
553 | | /// (1) A set of statements/expressions (which may contain subexpressions). |
554 | | /// (2) A "terminator" statement (not in the set of statements). |
555 | | /// (3) A list of successors and predecessors. |
556 | | /// |
557 | | /// Terminator: The terminator represents the type of control-flow that occurs |
558 | | /// at the end of the basic block. The terminator is a Stmt* referring to an |
559 | | /// AST node that has control-flow: if-statements, breaks, loops, etc. |
560 | | /// If the control-flow is conditional, the condition expression will appear |
561 | | /// within the set of statements in the block (usually the last statement). |
562 | | /// |
563 | | /// Predecessors: the order in the set of predecessors is arbitrary. |
564 | | /// |
565 | | /// Successors: the order in the set of successors is NOT arbitrary. We |
566 | | /// currently have the following orderings based on the terminator: |
567 | | /// |
568 | | /// Terminator | Successor Ordering |
569 | | /// ------------------|------------------------------------ |
570 | | /// if | Then Block; Else Block |
571 | | /// ? operator | LHS expression; RHS expression |
572 | | /// logical and/or | expression that consumes the op, RHS |
573 | | /// vbase inits | already handled by the most derived class; not yet |
574 | | /// |
575 | | /// But note that any of that may be NULL in case of optimized-out edges. |
576 | | class CFGBlock { |
577 | | class ElementList { |
578 | | using ImplTy = BumpVector<CFGElement>; |
579 | | |
580 | | ImplTy Impl; |
581 | | |
582 | | public: |
583 | 1.03M | ElementList(BumpVectorContext &C) : Impl(C, 4) {} |
584 | | |
585 | | using iterator = std::reverse_iterator<ImplTy::iterator>; |
586 | | using const_iterator = std::reverse_iterator<ImplTy::const_iterator>; |
587 | | using reverse_iterator = ImplTy::iterator; |
588 | | using const_reverse_iterator = ImplTy::const_iterator; |
589 | | using const_reference = ImplTy::const_reference; |
590 | | |
591 | 4.29M | void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); } |
592 | | |
593 | | reverse_iterator insert(reverse_iterator I, size_t Cnt, CFGElement E, |
594 | 74 | BumpVectorContext &C) { |
595 | 74 | return Impl.insert(I, Cnt, E, C); |
596 | 74 | } |
597 | | |
598 | 126k | const_reference front() const { return Impl.back(); } |
599 | 66.8k | const_reference back() const { return Impl.front(); } |
600 | | |
601 | 102k | iterator begin() { return Impl.rbegin(); } |
602 | 102k | iterator end() { return Impl.rend(); } |
603 | 71.7k | const_iterator begin() const { return Impl.rbegin(); } |
604 | 71.7k | const_iterator end() const { return Impl.rend(); } |
605 | | reverse_iterator rbegin() { return Impl.begin(); } |
606 | | reverse_iterator rend() { return Impl.end(); } |
607 | 270k | const_reverse_iterator rbegin() const { return Impl.begin(); } |
608 | 267k | const_reverse_iterator rend() const { return Impl.end(); } |
609 | | |
610 | 4.10M | CFGElement operator[](size_t i) const { |
611 | 4.10M | assert(i < Impl.size()); |
612 | 0 | return Impl[Impl.size() - 1 - i]; |
613 | 4.10M | } |
614 | | |
615 | 1.31M | size_t size() const { return Impl.size(); } |
616 | 1.60M | bool empty() const { return Impl.empty(); } |
617 | | }; |
618 | | |
619 | | /// A convenience class for comparing CFGElements, since methods of CFGBlock |
620 | | /// like operator[] return CFGElements by value. This is practically a wrapper |
621 | | /// around a (CFGBlock, Index) pair. |
622 | | template <bool IsConst> class ElementRefImpl { |
623 | | |
624 | | template <bool IsOtherConst> friend class ElementRefImpl; |
625 | | |
626 | | using CFGBlockPtr = |
627 | | std::conditional_t<IsConst, const CFGBlock *, CFGBlock *>; |
628 | | |
629 | | using CFGElementPtr = |
630 | | std::conditional_t<IsConst, const CFGElement *, CFGElement *>; |
631 | | |
632 | | protected: |
633 | | CFGBlockPtr Parent; |
634 | | size_t Index; |
635 | | |
636 | | public: |
637 | | ElementRefImpl(CFGBlockPtr Parent, size_t Index) |
638 | | : Parent(Parent), Index(Index) {} |
639 | | |
640 | | template <bool IsOtherConst> |
641 | | ElementRefImpl(ElementRefImpl<IsOtherConst> Other) |
642 | | : ElementRefImpl(Other.Parent, Other.Index) {} |
643 | | |
644 | | size_t getIndexInBlock() const { return Index; } |
645 | | |
646 | | CFGBlockPtr getParent() { return Parent; } |
647 | | CFGBlockPtr getParent() const { return Parent; } |
648 | | |
649 | | bool operator<(ElementRefImpl Other) const { |
650 | | return std::make_pair(Parent, Index) < |
651 | | std::make_pair(Other.Parent, Other.Index); |
652 | | } |
653 | | |
654 | | bool operator==(ElementRefImpl Other) const { |
655 | | return Parent == Other.Parent && Index == Other.Index; |
656 | | } |
657 | | |
658 | | bool operator!=(ElementRefImpl Other) const { return !(*this == Other); } |
659 | | CFGElement operator*() const { return (*Parent)[Index]; } |
660 | | CFGElementPtr operator->() const { return &*(Parent->begin() + Index); } |
661 | | |
662 | | void dumpToStream(llvm::raw_ostream &OS) const { |
663 | | OS << getIndexInBlock() + 1 << ": "; |
664 | | (*this)->dumpToStream(OS); |
665 | | } |
666 | | |
667 | | void dump() const { |
668 | | dumpToStream(llvm::errs()); |
669 | | } |
670 | | }; |
671 | | |
672 | | template <bool IsReverse, bool IsConst> class ElementRefIterator { |
673 | | |
674 | | template <bool IsOtherReverse, bool IsOtherConst> |
675 | | friend class ElementRefIterator; |
676 | | |
677 | | using CFGBlockRef = |
678 | | std::conditional_t<IsConst, const CFGBlock *, CFGBlock *>; |
679 | | |
680 | | using UnderlayingIteratorTy = std::conditional_t< |
681 | | IsConst, |
682 | | std::conditional_t<IsReverse, ElementList::const_reverse_iterator, |
683 | | ElementList::const_iterator>, |
684 | | std::conditional_t<IsReverse, ElementList::reverse_iterator, |
685 | | ElementList::iterator>>; |
686 | | |
687 | | using IteratorTraits = typename std::iterator_traits<UnderlayingIteratorTy>; |
688 | | using ElementRef = typename CFGBlock::ElementRefImpl<IsConst>; |
689 | | |
690 | | public: |
691 | | using difference_type = typename IteratorTraits::difference_type; |
692 | | using value_type = ElementRef; |
693 | | using pointer = ElementRef *; |
694 | | using iterator_category = typename IteratorTraits::iterator_category; |
695 | | |
696 | | private: |
697 | | CFGBlockRef Parent; |
698 | | UnderlayingIteratorTy Pos; |
699 | | |
700 | | public: |
701 | | ElementRefIterator(CFGBlockRef Parent, UnderlayingIteratorTy Pos) |
702 | | : Parent(Parent), Pos(Pos) {} |
703 | | |
704 | | template <bool IsOtherConst> |
705 | | ElementRefIterator(ElementRefIterator<false, IsOtherConst> E) |
706 | | : ElementRefIterator(E.Parent, E.Pos.base()) {} |
707 | | |
708 | | template <bool IsOtherConst> |
709 | | ElementRefIterator(ElementRefIterator<true, IsOtherConst> E) |
710 | | : ElementRefIterator(E.Parent, std::make_reverse_iterator(E.Pos)) {} |
711 | | |
712 | | bool operator<(ElementRefIterator Other) const { |
713 | | assert(Parent == Other.Parent); |
714 | | return Pos < Other.Pos; |
715 | | } |
716 | | |
717 | | bool operator==(ElementRefIterator Other) const { |
718 | | return Parent == Other.Parent && Pos == Other.Pos; |
719 | | } |
720 | | |
721 | | bool operator!=(ElementRefIterator Other) const { |
722 | | return !(*this == Other); |
723 | | } |
724 | | |
725 | | private: |
726 | | template <bool IsOtherConst> |
727 | | static size_t |
728 | | getIndexInBlock(CFGBlock::ElementRefIterator<true, IsOtherConst> E) { |
729 | | return E.Parent->size() - (E.Pos - E.Parent->rbegin()) - 1; |
730 | | } |
731 | | |
732 | | template <bool IsOtherConst> |
733 | | static size_t |
734 | | getIndexInBlock(CFGBlock::ElementRefIterator<false, IsOtherConst> E) { |
735 | | return E.Pos - E.Parent->begin(); |
736 | | } |
737 | | |
738 | | public: |
739 | | value_type operator*() { return {Parent, getIndexInBlock(*this)}; } |
740 | | |
741 | | difference_type operator-(ElementRefIterator Other) const { |
742 | | return Pos - Other.Pos; |
743 | | } |
744 | | |
745 | | ElementRefIterator operator++() { |
746 | | ++this->Pos; |
747 | | return *this; |
748 | | } |
749 | | ElementRefIterator operator++(int) { |
750 | | ElementRefIterator Ret = *this; |
751 | | ++*this; |
752 | | return Ret; |
753 | | } |
754 | | ElementRefIterator operator+(size_t count) { |
755 | | this->Pos += count; |
756 | | return *this; |
757 | | } |
758 | | ElementRefIterator operator-(size_t count) { |
759 | | this->Pos -= count; |
760 | | return *this; |
761 | | } |
762 | | }; |
763 | | |
764 | | public: |
765 | | /// The set of statements in the basic block. |
766 | | ElementList Elements; |
767 | | |
768 | | /// An (optional) label that prefixes the executable statements in the block. |
769 | | /// When this variable is non-NULL, it is either an instance of LabelStmt, |
770 | | /// SwitchCase or CXXCatchStmt. |
771 | | Stmt *Label = nullptr; |
772 | | |
773 | | /// The terminator for a basic block that indicates the type of control-flow |
774 | | /// that occurs between a block and its successors. |
775 | | CFGTerminator Terminator; |
776 | | |
777 | | /// Some blocks are used to represent the "loop edge" to the start of a loop |
778 | | /// from within the loop body. This Stmt* will be refer to the loop statement |
779 | | /// for such blocks (and be null otherwise). |
780 | | const Stmt *LoopTarget = nullptr; |
781 | | |
782 | | /// A numerical ID assigned to a CFGBlock during construction of the CFG. |
783 | | unsigned BlockID; |
784 | | |
785 | | public: |
786 | | /// This class represents a potential adjacent block in the CFG. It encodes |
787 | | /// whether or not the block is actually reachable, or can be proved to be |
788 | | /// trivially unreachable. For some cases it allows one to encode scenarios |
789 | | /// where a block was substituted because the original (now alternate) block |
790 | | /// is unreachable. |
791 | | class AdjacentBlock { |
792 | | enum Kind { |
793 | | AB_Normal, |
794 | | AB_Unreachable, |
795 | | AB_Alternate |
796 | | }; |
797 | | |
798 | | CFGBlock *ReachableBlock; |
799 | | llvm::PointerIntPair<CFGBlock *, 2> UnreachableBlock; |
800 | | |
801 | | public: |
802 | | /// Construct an AdjacentBlock with a possibly unreachable block. |
803 | | AdjacentBlock(CFGBlock *B, bool IsReachable); |
804 | | |
805 | | /// Construct an AdjacentBlock with a reachable block and an alternate |
806 | | /// unreachable block. |
807 | | AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock); |
808 | | |
809 | | /// Get the reachable block, if one exists. |
810 | 3.04M | CFGBlock *getReachableBlock() const { |
811 | 3.04M | return ReachableBlock; |
812 | 3.04M | } |
813 | | |
814 | | /// Get the potentially unreachable block. |
815 | 972k | CFGBlock *getPossiblyUnreachableBlock() const { |
816 | 972k | return UnreachableBlock.getPointer(); |
817 | 972k | } |
818 | | |
819 | | /// Provide an implicit conversion to CFGBlock* so that |
820 | | /// AdjacentBlock can be substituted for CFGBlock*. |
821 | 1.98M | operator CFGBlock*() const { |
822 | 1.98M | return getReachableBlock(); |
823 | 1.98M | } |
824 | | |
825 | 35.4k | CFGBlock& operator *() const { |
826 | 35.4k | return *getReachableBlock(); |
827 | 35.4k | } |
828 | | |
829 | 18.8k | CFGBlock* operator ->() const { |
830 | 18.8k | return getReachableBlock(); |
831 | 18.8k | } |
832 | | |
833 | 1.01M | bool isReachable() const { |
834 | 1.01M | Kind K = (Kind) UnreachableBlock.getInt(); |
835 | 1.01M | return K == AB_Normal || K == AB_Alternate936 ; |
836 | 1.01M | } |
837 | | }; |
838 | | |
839 | | private: |
840 | | /// Keep track of the predecessor / successor CFG blocks. |
841 | | using AdjacentBlocks = BumpVector<AdjacentBlock>; |
842 | | AdjacentBlocks Preds; |
843 | | AdjacentBlocks Succs; |
844 | | |
845 | | /// This bit is set when the basic block contains a function call |
846 | | /// or implicit destructor that is attributed as 'noreturn'. In that case, |
847 | | /// control cannot technically ever proceed past this block. All such blocks |
848 | | /// will have a single immediate successor: the exit block. This allows them |
849 | | /// to be easily reached from the exit block and using this bit quickly |
850 | | /// recognized without scanning the contents of the block. |
851 | | /// |
852 | | /// Optimization Note: This bit could be profitably folded with Terminator's |
853 | | /// storage if the memory usage of CFGBlock becomes an issue. |
854 | | unsigned HasNoReturnElement : 1; |
855 | | |
856 | | /// The parent CFG that owns this CFGBlock. |
857 | | CFG *Parent; |
858 | | |
859 | | public: |
860 | | explicit CFGBlock(unsigned blockid, BumpVectorContext &C, CFG *parent) |
861 | | : Elements(C), Terminator(nullptr), BlockID(blockid), Preds(C, 1), |
862 | 1.03M | Succs(C, 1), HasNoReturnElement(false), Parent(parent) {} |
863 | | |
864 | | // Statement iterators |
865 | | using iterator = ElementList::iterator; |
866 | | using const_iterator = ElementList::const_iterator; |
867 | | using reverse_iterator = ElementList::reverse_iterator; |
868 | | using const_reverse_iterator = ElementList::const_reverse_iterator; |
869 | | |
870 | | size_t getIndexInCFG() const; |
871 | | |
872 | 126k | CFGElement front() const { return Elements.front(); } |
873 | 66.8k | CFGElement back() const { return Elements.back(); } |
874 | | |
875 | 102k | iterator begin() { return Elements.begin(); } |
876 | 102k | iterator end() { return Elements.end(); } |
877 | 71.7k | const_iterator begin() const { return Elements.begin(); } |
878 | 71.7k | const_iterator end() const { return Elements.end(); } |
879 | | |
880 | | reverse_iterator rbegin() { return Elements.rbegin(); } |
881 | | reverse_iterator rend() { return Elements.rend(); } |
882 | 270k | const_reverse_iterator rbegin() const { return Elements.rbegin(); } |
883 | 267k | const_reverse_iterator rend() const { return Elements.rend(); } |
884 | | |
885 | | using CFGElementRef = ElementRefImpl<false>; |
886 | | using ConstCFGElementRef = ElementRefImpl<true>; |
887 | | |
888 | | using ref_iterator = ElementRefIterator<false, false>; |
889 | | using ref_iterator_range = llvm::iterator_range<ref_iterator>; |
890 | | using const_ref_iterator = ElementRefIterator<false, true>; |
891 | | using const_ref_iterator_range = llvm::iterator_range<const_ref_iterator>; |
892 | | |
893 | | using reverse_ref_iterator = ElementRefIterator<true, false>; |
894 | | using reverse_ref_iterator_range = llvm::iterator_range<reverse_ref_iterator>; |
895 | | |
896 | | using const_reverse_ref_iterator = ElementRefIterator<true, true>; |
897 | | using const_reverse_ref_iterator_range = |
898 | | llvm::iterator_range<const_reverse_ref_iterator>; |
899 | | |
900 | | ref_iterator ref_begin() { return {this, begin()}; } |
901 | | ref_iterator ref_end() { return {this, end()}; } |
902 | | const_ref_iterator ref_begin() const { return {this, begin()}; } |
903 | | const_ref_iterator ref_end() const { return {this, end()}; } |
904 | | |
905 | | reverse_ref_iterator rref_begin() { return {this, rbegin()}; } |
906 | | reverse_ref_iterator rref_end() { return {this, rend()}; } |
907 | | const_reverse_ref_iterator rref_begin() const { return {this, rbegin()}; } |
908 | | const_reverse_ref_iterator rref_end() const { return {this, rend()}; } |
909 | | |
910 | | ref_iterator_range refs() { return {ref_begin(), ref_end()}; } |
911 | | const_ref_iterator_range refs() const { return {ref_begin(), ref_end()}; } |
912 | | reverse_ref_iterator_range rrefs() { return {rref_begin(), rref_end()}; } |
913 | | const_reverse_ref_iterator_range rrefs() const { |
914 | | return {rref_begin(), rref_end()}; |
915 | | } |
916 | | |
917 | 1.31M | unsigned size() const { return Elements.size(); } |
918 | 1.60M | bool empty() const { return Elements.empty(); } |
919 | | |
920 | 4.10M | CFGElement operator[](size_t i) const { return Elements[i]; } |
921 | | |
922 | | // CFG iterators |
923 | | using pred_iterator = AdjacentBlocks::iterator; |
924 | | using const_pred_iterator = AdjacentBlocks::const_iterator; |
925 | | using pred_reverse_iterator = AdjacentBlocks::reverse_iterator; |
926 | | using const_pred_reverse_iterator = AdjacentBlocks::const_reverse_iterator; |
927 | | using pred_range = llvm::iterator_range<pred_iterator>; |
928 | | using pred_const_range = llvm::iterator_range<const_pred_iterator>; |
929 | | |
930 | | using succ_iterator = AdjacentBlocks::iterator; |
931 | | using const_succ_iterator = AdjacentBlocks::const_iterator; |
932 | | using succ_reverse_iterator = AdjacentBlocks::reverse_iterator; |
933 | | using const_succ_reverse_iterator = AdjacentBlocks::const_reverse_iterator; |
934 | | using succ_range = llvm::iterator_range<succ_iterator>; |
935 | | using succ_const_range = llvm::iterator_range<const_succ_iterator>; |
936 | | |
937 | 69.5k | pred_iterator pred_begin() { return Preds.begin(); } |
938 | 69.5k | pred_iterator pred_end() { return Preds.end(); } |
939 | 352k | const_pred_iterator pred_begin() const { return Preds.begin(); } |
940 | 350k | const_pred_iterator pred_end() const { return Preds.end(); } |
941 | | |
942 | 0 | pred_reverse_iterator pred_rbegin() { return Preds.rbegin(); } |
943 | 0 | pred_reverse_iterator pred_rend() { return Preds.rend(); } |
944 | 0 | const_pred_reverse_iterator pred_rbegin() const { return Preds.rbegin(); } |
945 | 0 | const_pred_reverse_iterator pred_rend() const { return Preds.rend(); } |
946 | | |
947 | 0 | pred_range preds() { |
948 | 0 | return pred_range(pred_begin(), pred_end()); |
949 | 0 | } |
950 | | |
951 | 100k | pred_const_range preds() const { |
952 | 100k | return pred_const_range(pred_begin(), pred_end()); |
953 | 100k | } |
954 | | |
955 | 112k | succ_iterator succ_begin() { return Succs.begin(); } |
956 | 112k | succ_iterator succ_end() { return Succs.end(); } |
957 | 1.31M | const_succ_iterator succ_begin() const { return Succs.begin(); } |
958 | 1.14M | const_succ_iterator succ_end() const { return Succs.end(); } |
959 | | |
960 | 0 | succ_reverse_iterator succ_rbegin() { return Succs.rbegin(); } |
961 | 0 | succ_reverse_iterator succ_rend() { return Succs.rend(); } |
962 | 578 | const_succ_reverse_iterator succ_rbegin() const { return Succs.rbegin(); } |
963 | 416 | const_succ_reverse_iterator succ_rend() const { return Succs.rend(); } |
964 | | |
965 | 138 | succ_range succs() { |
966 | 138 | return succ_range(succ_begin(), succ_end()); |
967 | 138 | } |
968 | | |
969 | 67.9k | succ_const_range succs() const { |
970 | 67.9k | return succ_const_range(succ_begin(), succ_end()); |
971 | 67.9k | } |
972 | | |
973 | 224k | unsigned succ_size() const { return Succs.size(); } |
974 | 3.57k | bool succ_empty() const { return Succs.empty(); } |
975 | | |
976 | 7.68k | unsigned pred_size() const { return Preds.size(); } |
977 | 53.8k | bool pred_empty() const { return Preds.empty(); } |
978 | | |
979 | | |
980 | | class FilterOptions { |
981 | | public: |
982 | | unsigned IgnoreNullPredecessors : 1; |
983 | | unsigned IgnoreDefaultsWithCoveredEnums : 1; |
984 | | |
985 | | FilterOptions() |
986 | 140k | : IgnoreNullPredecessors(1), IgnoreDefaultsWithCoveredEnums(0) {} |
987 | | }; |
988 | | |
989 | | static bool FilterEdge(const FilterOptions &F, const CFGBlock *Src, |
990 | | const CFGBlock *Dst); |
991 | | |
992 | | template <typename IMPL, bool IsPred> |
993 | | class FilteredCFGBlockIterator { |
994 | | private: |
995 | | IMPL I, E; |
996 | | const FilterOptions F; |
997 | | const CFGBlock *From; |
998 | | |
999 | | public: |
1000 | | explicit FilteredCFGBlockIterator(const IMPL &i, const IMPL &e, |
1001 | | const CFGBlock *from, |
1002 | | const FilterOptions &f) |
1003 | 140k | : I(i), E(e), F(f), From(from) { |
1004 | 140k | while (hasMore() && Filter(*I)140k ) |
1005 | 1 | ++I; |
1006 | 140k | } |
1007 | | |
1008 | 570k | bool hasMore() const { return I != E; } clang::CFGBlock::FilteredCFGBlockIterator<clang::CFGBlock::AdjacentBlock const*, true>::hasMore() const Line | Count | Source | 1008 | 570k | bool hasMore() const { return I != E; } |
Unexecuted instantiation: clang::CFGBlock::FilteredCFGBlockIterator<clang::CFGBlock::AdjacentBlock const*, false>::hasMore() const |
1009 | | |
1010 | 144k | FilteredCFGBlockIterator &operator++() { |
1011 | 144k | do { ++I; } while (hasMore() && Filter(*I)3.51k ); |
1012 | 144k | return *this; |
1013 | 144k | } |
1014 | | |
1015 | 144k | const CFGBlock *operator*() const { return *I; } |
1016 | | |
1017 | | private: |
1018 | 144k | bool Filter(const CFGBlock *To) { |
1019 | 144k | return IsPred ? FilterEdge(F, To, From) : FilterEdge(F, From, To)0 ; |
1020 | 144k | } clang::CFGBlock::FilteredCFGBlockIterator<clang::CFGBlock::AdjacentBlock const*, true>::Filter(clang::CFGBlock const*) Line | Count | Source | 1018 | 144k | bool Filter(const CFGBlock *To) { | 1019 | 144k | return IsPred ? FilterEdge(F, To, From) : FilterEdge(F, From, To)0 ; | 1020 | 144k | } |
Unexecuted instantiation: clang::CFGBlock::FilteredCFGBlockIterator<clang::CFGBlock::AdjacentBlock const*, false>::Filter(clang::CFGBlock const*) |
1021 | | }; |
1022 | | |
1023 | | using filtered_pred_iterator = |
1024 | | FilteredCFGBlockIterator<const_pred_iterator, true>; |
1025 | | |
1026 | | using filtered_succ_iterator = |
1027 | | FilteredCFGBlockIterator<const_succ_iterator, false>; |
1028 | | |
1029 | 140k | filtered_pred_iterator filtered_pred_start_end(const FilterOptions &f) const { |
1030 | 140k | return filtered_pred_iterator(pred_begin(), pred_end(), this, f); |
1031 | 140k | } |
1032 | | |
1033 | 0 | filtered_succ_iterator filtered_succ_start_end(const FilterOptions &f) const { |
1034 | 0 | return filtered_succ_iterator(succ_begin(), succ_end(), this, f); |
1035 | 0 | } |
1036 | | |
1037 | | // Manipulation of block contents |
1038 | | |
1039 | 180k | void setTerminator(CFGTerminator Term) { Terminator = Term; } |
1040 | 3.40k | void setLabel(Stmt *Statement) { Label = Statement; } |
1041 | 53.5k | void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; } |
1042 | 1.53k | void setHasNoReturnElement() { HasNoReturnElement = true; } |
1043 | | |
1044 | | /// Returns true if the block would eventually end with a sink (a noreturn |
1045 | | /// node). |
1046 | | bool isInevitablySinking() const; |
1047 | | |
1048 | 347k | CFGTerminator getTerminator() const { return Terminator; } |
1049 | | |
1050 | 29.9k | Stmt *getTerminatorStmt() { return Terminator.getStmt(); } |
1051 | 690k | const Stmt *getTerminatorStmt() const { return Terminator.getStmt(); } |
1052 | | |
1053 | | /// \returns the last (\c rbegin()) condition, e.g. observe the following code |
1054 | | /// snippet: |
1055 | | /// if (A && B && C) |
1056 | | /// A block would be created for \c A, \c B, and \c C. For the latter, |
1057 | | /// \c getTerminatorStmt() would retrieve the entire condition, rather than |
1058 | | /// C itself, while this method would only return C. |
1059 | | const Expr *getLastCondition() const; |
1060 | | |
1061 | | Stmt *getTerminatorCondition(bool StripParens = true); |
1062 | | |
1063 | 10.2k | const Stmt *getTerminatorCondition(bool StripParens = true) const { |
1064 | 10.2k | return const_cast<CFGBlock*>(this)->getTerminatorCondition(StripParens); |
1065 | 10.2k | } |
1066 | | |
1067 | 2.46k | const Stmt *getLoopTarget() const { return LoopTarget; } |
1068 | | |
1069 | 18.0k | Stmt *getLabel() { return Label; } |
1070 | 6.29k | const Stmt *getLabel() const { return Label; } |
1071 | | |
1072 | 353k | bool hasNoReturnElement() const { return HasNoReturnElement; } |
1073 | | |
1074 | 3.53M | unsigned getBlockID() const { return BlockID; } |
1075 | | |
1076 | 8.04k | CFG *getParent() const { return Parent; } |
1077 | | |
1078 | | void dump() const; |
1079 | | |
1080 | | void dump(const CFG *cfg, const LangOptions &LO, bool ShowColors = false) const; |
1081 | | void print(raw_ostream &OS, const CFG* cfg, const LangOptions &LO, |
1082 | | bool ShowColors) const; |
1083 | | |
1084 | | void printTerminator(raw_ostream &OS, const LangOptions &LO) const; |
1085 | | void printTerminatorJson(raw_ostream &Out, const LangOptions &LO, |
1086 | | bool AddQuotes) const; |
1087 | | |
1088 | 0 | void printAsOperand(raw_ostream &OS, bool /*PrintType*/) { |
1089 | 0 | OS << "BB#" << getBlockID(); |
1090 | 0 | } |
1091 | | |
1092 | | /// Adds a (potentially unreachable) successor block to the current block. |
1093 | | void addSuccessor(AdjacentBlock Succ, BumpVectorContext &C); |
1094 | | |
1095 | 4.23M | void appendStmt(Stmt *statement, BumpVectorContext &C) { |
1096 | 4.23M | Elements.push_back(CFGStmt(statement), C); |
1097 | 4.23M | } |
1098 | | |
1099 | | void appendConstructor(CXXConstructExpr *CE, const ConstructionContext *CC, |
1100 | 24.4k | BumpVectorContext &C) { |
1101 | 24.4k | Elements.push_back(CFGConstructor(CE, CC), C); |
1102 | 24.4k | } |
1103 | | |
1104 | | void appendCXXRecordTypedCall(Expr *E, |
1105 | | const ConstructionContext *CC, |
1106 | 8.03k | BumpVectorContext &C) { |
1107 | 8.03k | Elements.push_back(CFGCXXRecordTypedCall(E, CC), C); |
1108 | 8.03k | } |
1109 | | |
1110 | | void appendInitializer(CXXCtorInitializer *initializer, |
1111 | 15.3k | BumpVectorContext &C) { |
1112 | 15.3k | Elements.push_back(CFGInitializer(initializer), C); |
1113 | 15.3k | } |
1114 | | |
1115 | | void appendNewAllocator(CXXNewExpr *NE, |
1116 | 1.90k | BumpVectorContext &C) { |
1117 | 1.90k | Elements.push_back(CFGNewAllocator(NE), C); |
1118 | 1.90k | } |
1119 | | |
1120 | | void appendScopeBegin(const VarDecl *VD, const Stmt *S, |
1121 | 92 | BumpVectorContext &C) { |
1122 | 92 | Elements.push_back(CFGScopeBegin(VD, S), C); |
1123 | 92 | } |
1124 | | |
1125 | | void prependScopeBegin(const VarDecl *VD, const Stmt *S, |
1126 | 0 | BumpVectorContext &C) { |
1127 | 0 | Elements.insert(Elements.rbegin(), 1, CFGScopeBegin(VD, S), C); |
1128 | 0 | } |
1129 | | |
1130 | 154 | void appendScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) { |
1131 | 154 | Elements.push_back(CFGScopeEnd(VD, S), C); |
1132 | 154 | } |
1133 | | |
1134 | 0 | void prependScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) { |
1135 | 0 | Elements.insert(Elements.rbegin(), 1, CFGScopeEnd(VD, S), C); |
1136 | 0 | } |
1137 | | |
1138 | 530 | void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) { |
1139 | 530 | Elements.push_back(CFGBaseDtor(BS), C); |
1140 | 530 | } |
1141 | | |
1142 | 135 | void appendMemberDtor(FieldDecl *FD, BumpVectorContext &C) { |
1143 | 135 | Elements.push_back(CFGMemberDtor(FD), C); |
1144 | 135 | } |
1145 | | |
1146 | 5.68k | void appendTemporaryDtor(CXXBindTemporaryExpr *E, BumpVectorContext &C) { |
1147 | 5.68k | Elements.push_back(CFGTemporaryDtor(E), C); |
1148 | 5.68k | } |
1149 | | |
1150 | 5.37k | void appendAutomaticObjDtor(VarDecl *VD, Stmt *S, BumpVectorContext &C) { |
1151 | 5.37k | Elements.push_back(CFGAutomaticObjDtor(VD, S), C); |
1152 | 5.37k | } |
1153 | | |
1154 | 162 | void appendLifetimeEnds(VarDecl *VD, Stmt *S, BumpVectorContext &C) { |
1155 | 162 | Elements.push_back(CFGLifetimeEnds(VD, S), C); |
1156 | 162 | } |
1157 | | |
1158 | 254 | void appendLoopExit(const Stmt *LoopStmt, BumpVectorContext &C) { |
1159 | 254 | Elements.push_back(CFGLoopExit(LoopStmt), C); |
1160 | 254 | } |
1161 | | |
1162 | 234 | void appendDeleteDtor(CXXRecordDecl *RD, CXXDeleteExpr *DE, BumpVectorContext &C) { |
1163 | 234 | Elements.push_back(CFGDeleteDtor(RD, DE), C); |
1164 | 234 | } |
1165 | | |
1166 | | // Destructors must be inserted in reversed order. So insertion is in two |
1167 | | // steps. First we prepare space for some number of elements, then we insert |
1168 | | // the elements beginning at the last position in prepared space. |
1169 | | iterator beginAutomaticObjDtorsInsert(iterator I, size_t Cnt, |
1170 | 70 | BumpVectorContext &C) { |
1171 | 70 | return iterator(Elements.insert(I.base(), Cnt, |
1172 | 70 | CFGAutomaticObjDtor(nullptr, nullptr), C)); |
1173 | 70 | } |
1174 | 26 | iterator insertAutomaticObjDtor(iterator I, VarDecl *VD, Stmt *S) { |
1175 | 26 | *I = CFGAutomaticObjDtor(VD, S); |
1176 | 26 | return ++I; |
1177 | 26 | } |
1178 | | |
1179 | | // Scope leaving must be performed in reversed order. So insertion is in two |
1180 | | // steps. First we prepare space for some number of elements, then we insert |
1181 | | // the elements beginning at the last position in prepared space. |
1182 | | iterator beginLifetimeEndsInsert(iterator I, size_t Cnt, |
1183 | 2 | BumpVectorContext &C) { |
1184 | 2 | return iterator( |
1185 | 2 | Elements.insert(I.base(), Cnt, CFGLifetimeEnds(nullptr, nullptr), C)); |
1186 | 2 | } |
1187 | 2 | iterator insertLifetimeEnds(iterator I, VarDecl *VD, Stmt *S) { |
1188 | 2 | *I = CFGLifetimeEnds(VD, S); |
1189 | 2 | return ++I; |
1190 | 2 | } |
1191 | | |
1192 | | // Scope leaving must be performed in reversed order. So insertion is in two |
1193 | | // steps. First we prepare space for some number of elements, then we insert |
1194 | | // the elements beginning at the last position in prepared space. |
1195 | 2 | iterator beginScopeEndInsert(iterator I, size_t Cnt, BumpVectorContext &C) { |
1196 | 2 | return iterator( |
1197 | 2 | Elements.insert(I.base(), Cnt, CFGScopeEnd(nullptr, nullptr), C)); |
1198 | 2 | } |
1199 | 2 | iterator insertScopeEnd(iterator I, VarDecl *VD, Stmt *S) { |
1200 | 2 | *I = CFGScopeEnd(VD, S); |
1201 | 2 | return ++I; |
1202 | 2 | } |
1203 | | }; |
1204 | | |
1205 | | /// CFGCallback defines methods that should be called when a logical |
1206 | | /// operator error is found when building the CFG. |
1207 | | class CFGCallback { |
1208 | | public: |
1209 | 42.3k | CFGCallback() = default; |
1210 | 42.3k | virtual ~CFGCallback() = default; |
1211 | | |
1212 | 0 | virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {} |
1213 | | virtual void compareBitwiseEquality(const BinaryOperator *B, |
1214 | 0 | bool isAlwaysTrue) {} |
1215 | 0 | virtual void compareBitwiseOr(const BinaryOperator *B) {} |
1216 | | }; |
1217 | | |
1218 | | /// Represents a source-level, intra-procedural CFG that represents the |
1219 | | /// control-flow of a Stmt. The Stmt can represent an entire function body, |
1220 | | /// or a single expression. A CFG will always contain one empty block that |
1221 | | /// represents the Exit point of the CFG. A CFG will also contain a designated |
1222 | | /// Entry block. The CFG solely represents control-flow; it consists of |
1223 | | /// CFGBlocks which are simply containers of Stmt*'s in the AST the CFG |
1224 | | /// was constructed from. |
1225 | | class CFG { |
1226 | | public: |
1227 | | //===--------------------------------------------------------------------===// |
1228 | | // CFG Construction & Manipulation. |
1229 | | //===--------------------------------------------------------------------===// |
1230 | | |
1231 | | class BuildOptions { |
1232 | | std::bitset<Stmt::lastStmtConstant> alwaysAddMask; |
1233 | | |
1234 | | public: |
1235 | | using ForcedBlkExprs = llvm::DenseMap<const Stmt *, const CFGBlock *>; |
1236 | | |
1237 | | ForcedBlkExprs **forcedBlkExprs = nullptr; |
1238 | | CFGCallback *Observer = nullptr; |
1239 | | bool PruneTriviallyFalseEdges = true; |
1240 | | bool AddEHEdges = false; |
1241 | | bool AddInitializers = false; |
1242 | | bool AddImplicitDtors = false; |
1243 | | bool AddLifetime = false; |
1244 | | bool AddLoopExit = false; |
1245 | | bool AddTemporaryDtors = false; |
1246 | | bool AddScopes = false; |
1247 | | bool AddStaticInitBranches = false; |
1248 | | bool AddCXXNewAllocator = false; |
1249 | | bool AddCXXDefaultInitExprInCtors = false; |
1250 | | bool AddCXXDefaultInitExprInAggregates = false; |
1251 | | bool AddRichCXXConstructors = false; |
1252 | | bool MarkElidedCXXConstructors = false; |
1253 | | bool AddVirtualBaseBranches = false; |
1254 | | bool OmitImplicitValueInitializers = false; |
1255 | | |
1256 | 277k | BuildOptions() = default; |
1257 | | |
1258 | 8.23M | bool alwaysAdd(const Stmt *stmt) const { |
1259 | 8.23M | return alwaysAddMask[stmt->getStmtClass()]; |
1260 | 8.23M | } |
1261 | | |
1262 | 1.91M | BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) { |
1263 | 1.91M | alwaysAddMask[stmtClass] = val; |
1264 | 1.91M | return *this; |
1265 | 1.91M | } |
1266 | | |
1267 | 4.60k | BuildOptions &setAllAlwaysAdd() { |
1268 | 4.60k | alwaysAddMask.set(); |
1269 | 4.60k | return *this; |
1270 | 4.60k | } |
1271 | | }; |
1272 | | |
1273 | | /// Builds a CFG from an AST. |
1274 | | static std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *AST, ASTContext *C, |
1275 | | const BuildOptions &BO); |
1276 | | |
1277 | | /// Create a new block in the CFG. The CFG owns the block; the caller should |
1278 | | /// not directly free it. |
1279 | | CFGBlock *createBlock(); |
1280 | | |
1281 | | /// Set the entry block of the CFG. This is typically used only during CFG |
1282 | | /// construction. Most CFG clients expect that the entry block has no |
1283 | | /// predecessors and contains no statements. |
1284 | 229k | void setEntry(CFGBlock *B) { Entry = B; } |
1285 | | |
1286 | | /// Set the block used for indirect goto jumps. This is typically used only |
1287 | | /// during CFG construction. |
1288 | 21 | void setIndirectGotoBlock(CFGBlock *B) { IndirectGotoBlock = B; } |
1289 | | |
1290 | | //===--------------------------------------------------------------------===// |
1291 | | // Block Iterators |
1292 | | //===--------------------------------------------------------------------===// |
1293 | | |
1294 | | using CFGBlockListTy = BumpVector<CFGBlock *>; |
1295 | | using iterator = CFGBlockListTy::iterator; |
1296 | | using const_iterator = CFGBlockListTy::const_iterator; |
1297 | | using reverse_iterator = std::reverse_iterator<iterator>; |
1298 | | using const_reverse_iterator = std::reverse_iterator<const_iterator>; |
1299 | | |
1300 | 0 | CFGBlock & front() { return *Blocks.front(); } |
1301 | 1.26M | CFGBlock & back() { return *Blocks.back(); } |
1302 | | |
1303 | 1.07M | iterator begin() { return Blocks.begin(); } |
1304 | 1.07M | iterator end() { return Blocks.end(); } |
1305 | 5.43k | const_iterator begin() const { return Blocks.begin(); } |
1306 | 5.45k | const_iterator end() const { return Blocks.end(); } |
1307 | | |
1308 | 5.15k | iterator nodes_begin() { return iterator(Blocks.begin()); } |
1309 | 5.15k | iterator nodes_end() { return iterator(Blocks.end()); } |
1310 | | |
1311 | 27.1k | llvm::iterator_range<iterator> nodes() { return {begin(), end()}; } |
1312 | 0 | llvm::iterator_range<const_iterator> const_nodes() const { |
1313 | 0 | return {begin(), end()}; |
1314 | 0 | } |
1315 | | |
1316 | 0 | const_iterator nodes_begin() const { return const_iterator(Blocks.begin()); } |
1317 | 0 | const_iterator nodes_end() const { return const_iterator(Blocks.end()); } |
1318 | | |
1319 | 79 | reverse_iterator rbegin() { return Blocks.rbegin(); } |
1320 | 79 | reverse_iterator rend() { return Blocks.rend(); } |
1321 | 0 | const_reverse_iterator rbegin() const { return Blocks.rbegin(); } |
1322 | 0 | const_reverse_iterator rend() const { return Blocks.rend(); } |
1323 | | |
1324 | 0 | llvm::iterator_range<reverse_iterator> reverse_nodes() { |
1325 | 0 | return {rbegin(), rend()}; |
1326 | 0 | } |
1327 | 0 | llvm::iterator_range<const_reverse_iterator> const_reverse_nodes() const { |
1328 | 0 | return {rbegin(), rend()}; |
1329 | 0 | } |
1330 | | |
1331 | 227k | CFGBlock & getEntry() { return *Entry; } |
1332 | 116k | const CFGBlock & getEntry() const { return *Entry; } |
1333 | 926k | CFGBlock & getExit() { return *Exit; } |
1334 | 31.9k | const CFGBlock & getExit() const { return *Exit; } |
1335 | | |
1336 | 229k | CFGBlock * getIndirectGotoBlock() { return IndirectGotoBlock; } |
1337 | 1.98k | const CFGBlock * getIndirectGotoBlock() const { return IndirectGotoBlock; } |
1338 | | |
1339 | | using try_block_iterator = std::vector<const CFGBlock *>::const_iterator; |
1340 | | using try_block_range = llvm::iterator_range<try_block_iterator>; |
1341 | | |
1342 | 110 | try_block_iterator try_blocks_begin() const { |
1343 | 110 | return TryDispatchBlocks.begin(); |
1344 | 110 | } |
1345 | | |
1346 | 110 | try_block_iterator try_blocks_end() const { |
1347 | 110 | return TryDispatchBlocks.end(); |
1348 | 110 | } |
1349 | | |
1350 | 110 | try_block_range try_blocks() const { |
1351 | 110 | return try_block_range(try_blocks_begin(), try_blocks_end()); |
1352 | 110 | } |
1353 | | |
1354 | 378 | void addTryDispatchBlock(const CFGBlock *block) { |
1355 | 378 | TryDispatchBlocks.push_back(block); |
1356 | 378 | } |
1357 | | |
1358 | | /// Records a synthetic DeclStmt and the DeclStmt it was constructed from. |
1359 | | /// |
1360 | | /// The CFG uses synthetic DeclStmts when a single AST DeclStmt contains |
1361 | | /// multiple decls. |
1362 | | void addSyntheticDeclStmt(const DeclStmt *Synthetic, |
1363 | 10.7k | const DeclStmt *Source) { |
1364 | 10.7k | assert(Synthetic->isSingleDecl() && "Can handle single declarations only"); |
1365 | 0 | assert(Synthetic != Source && "Don't include original DeclStmts in map"); |
1366 | 0 | assert(!SyntheticDeclStmts.count(Synthetic) && "Already in map"); |
1367 | 0 | SyntheticDeclStmts[Synthetic] = Source; |
1368 | 10.7k | } |
1369 | | |
1370 | | using synthetic_stmt_iterator = |
1371 | | llvm::DenseMap<const DeclStmt *, const DeclStmt *>::const_iterator; |
1372 | | using synthetic_stmt_range = llvm::iterator_range<synthetic_stmt_iterator>; |
1373 | | |
1374 | | /// Iterates over synthetic DeclStmts in the CFG. |
1375 | | /// |
1376 | | /// Each element is a (synthetic statement, source statement) pair. |
1377 | | /// |
1378 | | /// \sa addSyntheticDeclStmt |
1379 | 25.7k | synthetic_stmt_iterator synthetic_stmt_begin() const { |
1380 | 25.7k | return SyntheticDeclStmts.begin(); |
1381 | 25.7k | } |
1382 | | |
1383 | | /// \sa synthetic_stmt_begin |
1384 | 25.7k | synthetic_stmt_iterator synthetic_stmt_end() const { |
1385 | 25.7k | return SyntheticDeclStmts.end(); |
1386 | 25.7k | } |
1387 | | |
1388 | | /// \sa synthetic_stmt_begin |
1389 | 0 | synthetic_stmt_range synthetic_stmts() const { |
1390 | 0 | return synthetic_stmt_range(synthetic_stmt_begin(), synthetic_stmt_end()); |
1391 | 0 | } |
1392 | | |
1393 | | //===--------------------------------------------------------------------===// |
1394 | | // Member templates useful for various batch operations over CFGs. |
1395 | | //===--------------------------------------------------------------------===// |
1396 | | |
1397 | 1.89k | template <typename Callback> void VisitBlockStmts(Callback &O) const { |
1398 | 13.6k | for (const_iterator I = begin(), E = end(); I != E; ++I11.7k ) |
1399 | 11.7k | for (CFGBlock::const_iterator BI = (*I)->begin(), BE = (*I)->end(); |
1400 | 46.8k | BI != BE; ++BI35.1k ) { |
1401 | 35.1k | if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>()) |
1402 | 35.0k | O(const_cast<Stmt *>(stmt->getStmt())); |
1403 | 35.1k | } |
1404 | 1.89k | } UninitializedValues.cpp:void clang::CFG::VisitBlockStmts<(anonymous namespace)::ClassifyRefs>((anonymous namespace)::ClassifyRefs&) const Line | Count | Source | 1397 | 1.37k | template <typename Callback> void VisitBlockStmts(Callback &O) const { | 1398 | 10.6k | for (const_iterator I = begin(), E = end(); I != E; ++I9.23k ) | 1399 | 9.23k | for (CFGBlock::const_iterator BI = (*I)->begin(), BE = (*I)->end(); | 1400 | 35.7k | BI != BE; ++BI26.5k ) { | 1401 | 26.5k | if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>()) | 1402 | 26.4k | O(const_cast<Stmt *>(stmt->getStmt())); | 1403 | 26.5k | } | 1404 | 1.37k | } |
DeadStoresChecker.cpp:void clang::CFG::VisitBlockStmts<(anonymous namespace)::FindEscaped>((anonymous namespace)::FindEscaped&) const Line | Count | Source | 1397 | 519 | template <typename Callback> void VisitBlockStmts(Callback &O) const { | 1398 | 3.01k | for (const_iterator I = begin(), E = end(); I != E; ++I2.49k ) | 1399 | 2.49k | for (CFGBlock::const_iterator BI = (*I)->begin(), BE = (*I)->end(); | 1400 | 11.1k | BI != BE; ++BI8.62k ) { | 1401 | 8.62k | if (Optional<CFGStmt> stmt = BI->getAs<CFGStmt>()) | 1402 | 8.59k | O(const_cast<Stmt *>(stmt->getStmt())); | 1403 | 8.62k | } | 1404 | 519 | } |
|
1405 | | |
1406 | | //===--------------------------------------------------------------------===// |
1407 | | // CFG Introspection. |
1408 | | //===--------------------------------------------------------------------===// |
1409 | | |
1410 | | /// Returns the total number of BlockIDs allocated (which start at 0). |
1411 | 760k | unsigned getNumBlockIDs() const { return NumBlockIDs; } |
1412 | | |
1413 | | /// Return the total number of CFGBlocks within the CFG This is simply a |
1414 | | /// renaming of the getNumBlockIDs(). This is necessary because the dominator |
1415 | | /// implementation needs such an interface. |
1416 | 113k | unsigned size() const { return NumBlockIDs; } |
1417 | | |
1418 | | /// Returns true if the CFG has no branches. Usually it boils down to the CFG |
1419 | | /// having exactly three blocks (entry, the actual code, exit), but sometimes |
1420 | | /// more blocks appear due to having control flow that can be fully |
1421 | | /// resolved in compile time. |
1422 | | bool isLinear() const; |
1423 | | |
1424 | | //===--------------------------------------------------------------------===// |
1425 | | // CFG Debugging: Pretty-Printing and Visualization. |
1426 | | //===--------------------------------------------------------------------===// |
1427 | | |
1428 | | void viewCFG(const LangOptions &LO) const; |
1429 | | void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const; |
1430 | | void dump(const LangOptions &LO, bool ShowColors) const; |
1431 | | |
1432 | | //===--------------------------------------------------------------------===// |
1433 | | // Internal: constructors and data. |
1434 | | //===--------------------------------------------------------------------===// |
1435 | | |
1436 | 230k | CFG() : Blocks(BlkBVC, 10) {} |
1437 | | |
1438 | 1.03M | llvm::BumpPtrAllocator& getAllocator() { |
1439 | 1.03M | return BlkBVC.getAllocator(); |
1440 | 1.03M | } |
1441 | | |
1442 | 5.71M | BumpVectorContext &getBumpVectorContext() { |
1443 | 5.71M | return BlkBVC; |
1444 | 5.71M | } |
1445 | | |
1446 | | private: |
1447 | | CFGBlock *Entry = nullptr; |
1448 | | CFGBlock *Exit = nullptr; |
1449 | | |
1450 | | // Special block to contain collective dispatch for indirect gotos |
1451 | | CFGBlock* IndirectGotoBlock = nullptr; |
1452 | | |
1453 | | unsigned NumBlockIDs = 0; |
1454 | | |
1455 | | BumpVectorContext BlkBVC; |
1456 | | |
1457 | | CFGBlockListTy Blocks; |
1458 | | |
1459 | | /// C++ 'try' statements are modeled with an indirect dispatch block. |
1460 | | /// This is the collection of such blocks present in the CFG. |
1461 | | std::vector<const CFGBlock *> TryDispatchBlocks; |
1462 | | |
1463 | | /// Collects DeclStmts synthesized for this CFG and maps each one back to its |
1464 | | /// source DeclStmt. |
1465 | | llvm::DenseMap<const DeclStmt *, const DeclStmt *> SyntheticDeclStmts; |
1466 | | }; |
1467 | | |
1468 | | } // namespace clang |
1469 | | |
1470 | | //===----------------------------------------------------------------------===// |
1471 | | // GraphTraits specializations for CFG basic block graphs (source-level CFGs) |
1472 | | //===----------------------------------------------------------------------===// |
1473 | | |
1474 | | namespace llvm { |
1475 | | |
1476 | | /// Implement simplify_type for CFGTerminator, so that we can dyn_cast from |
1477 | | /// CFGTerminator to a specific Stmt class. |
1478 | | template <> struct simplify_type< ::clang::CFGTerminator> { |
1479 | | using SimpleType = ::clang::Stmt *; |
1480 | | |
1481 | 628 | static SimpleType getSimplifiedValue(::clang::CFGTerminator Val) { |
1482 | 628 | return Val.getStmt(); |
1483 | 628 | } |
1484 | | }; |
1485 | | |
1486 | | // Traits for: CFGBlock |
1487 | | |
1488 | | template <> struct GraphTraits< ::clang::CFGBlock *> { |
1489 | | using NodeRef = ::clang::CFGBlock *; |
1490 | | using ChildIteratorType = ::clang::CFGBlock::succ_iterator; |
1491 | | |
1492 | 0 | static NodeRef getEntryNode(::clang::CFGBlock *BB) { return BB; } |
1493 | 26.9k | static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } |
1494 | 26.9k | static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } |
1495 | | }; |
1496 | | |
1497 | | template <> struct GraphTraits< const ::clang::CFGBlock *> { |
1498 | | using NodeRef = const ::clang::CFGBlock *; |
1499 | | using ChildIteratorType = ::clang::CFGBlock::const_succ_iterator; |
1500 | | |
1501 | 0 | static NodeRef getEntryNode(const clang::CFGBlock *BB) { return BB; } |
1502 | 116k | static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } |
1503 | 214k | static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } |
1504 | | }; |
1505 | | |
1506 | | template <> struct GraphTraits<Inverse< ::clang::CFGBlock *>> { |
1507 | | using NodeRef = ::clang::CFGBlock *; |
1508 | | using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator; |
1509 | | |
1510 | 0 | static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G) { |
1511 | 0 | return G.Graph; |
1512 | 0 | } |
1513 | | |
1514 | 69.5k | static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); } |
1515 | 69.5k | static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); } |
1516 | | }; |
1517 | | |
1518 | | template <> struct GraphTraits<Inverse<const ::clang::CFGBlock *>> { |
1519 | | using NodeRef = const ::clang::CFGBlock *; |
1520 | | using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator; |
1521 | | |
1522 | 0 | static NodeRef getEntryNode(Inverse<const ::clang::CFGBlock *> G) { |
1523 | 0 | return G.Graph; |
1524 | 0 | } |
1525 | | |
1526 | 0 | static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); } |
1527 | 0 | static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); } |
1528 | | }; |
1529 | | |
1530 | | // Traits for: CFG |
1531 | | |
1532 | | template <> struct GraphTraits< ::clang::CFG* > |
1533 | | : public GraphTraits< ::clang::CFGBlock *> { |
1534 | | using nodes_iterator = ::clang::CFG::iterator; |
1535 | | |
1536 | 10 | static NodeRef getEntryNode(::clang::CFG *F) { return &F->getEntry(); } |
1537 | 5.15k | static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();} |
1538 | 5.15k | static nodes_iterator nodes_end(::clang::CFG* F) { return F->nodes_end(); } |
1539 | 0 | static unsigned size(::clang::CFG* F) { return F->size(); } |
1540 | | }; |
1541 | | |
1542 | | template <> struct GraphTraits<const ::clang::CFG* > |
1543 | | : public GraphTraits<const ::clang::CFGBlock *> { |
1544 | | using nodes_iterator = ::clang::CFG::const_iterator; |
1545 | | |
1546 | 31.3k | static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getEntry(); } |
1547 | | |
1548 | 0 | static nodes_iterator nodes_begin( const ::clang::CFG* F) { |
1549 | 0 | return F->nodes_begin(); |
1550 | 0 | } |
1551 | | |
1552 | 0 | static nodes_iterator nodes_end( const ::clang::CFG* F) { |
1553 | 0 | return F->nodes_end(); |
1554 | 0 | } |
1555 | | |
1556 | 0 | static unsigned size(const ::clang::CFG* F) { |
1557 | 0 | return F->size(); |
1558 | 0 | } |
1559 | | }; |
1560 | | |
1561 | | template <> struct GraphTraits<Inverse< ::clang::CFG *>> |
1562 | | : public GraphTraits<Inverse< ::clang::CFGBlock *>> { |
1563 | | using nodes_iterator = ::clang::CFG::iterator; |
1564 | | |
1565 | 0 | static NodeRef getEntryNode(::clang::CFG *F) { return &F->getExit(); } |
1566 | 0 | static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();} |
1567 | 0 | static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); } |
1568 | | }; |
1569 | | |
1570 | | template <> struct GraphTraits<Inverse<const ::clang::CFG *>> |
1571 | | : public GraphTraits<Inverse<const ::clang::CFGBlock *>> { |
1572 | | using nodes_iterator = ::clang::CFG::const_iterator; |
1573 | | |
1574 | 0 | static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getExit(); } |
1575 | | |
1576 | 0 | static nodes_iterator nodes_begin(const ::clang::CFG* F) { |
1577 | 0 | return F->nodes_begin(); |
1578 | 0 | } |
1579 | | |
1580 | 0 | static nodes_iterator nodes_end(const ::clang::CFG* F) { |
1581 | 0 | return F->nodes_end(); |
1582 | 0 | } |
1583 | | }; |
1584 | | |
1585 | | } // namespace llvm |
1586 | | |
1587 | | #endif // LLVM_CLANG_ANALYSIS_CFG_H |