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