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 | : Data1(const_cast<void*>(Ptr1), ((unsigned) kind) & 0x3), |
89 | Data2(const_cast<void*>(Ptr2), (((unsigned) kind) >> 2) & 0x3) { |
90 | assert(getKind() == kind); |
91 | } |
92 | |
93 | 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 | T castAs() const { |
100 | assert(T::isKind(*this)); |
101 | T t; |
102 | CFGElement& e = t; |
103 | e = *this; |
104 | return t; |
105 | } |
106 | |
107 | /// Convert to the specified CFGElement type, returning std::nullopt if this |
108 | /// CFGElement is not of the desired type. |
109 | template <typename T> std::optional<T> getAs() const { |
110 | if (!T::isKind(*this)) |
111 | return std::nullopt; |
112 | T t; |
113 | CFGElement& e = t; |
114 | e = *this; |
115 | return t; |
116 | } |
117 | |
118 | Kind getKind() const { |
119 | unsigned x = Data2.getInt(); |
120 | x <<= 2; |
121 | x |= Data1.getInt(); |
122 | return (Kind) x; |
123 | } |
124 | |
125 | void dumpToStream(llvm::raw_ostream &OS) const; |
126 | |
127 | void dump() const { |
128 | dumpToStream(OS&: llvm::errs()); |
129 | } |
130 | }; |
131 | |
132 | class CFGStmt : public CFGElement { |
133 | public: |
134 | explicit CFGStmt(const Stmt *S, Kind K = Statement) : CFGElement(K, S) { |
135 | assert(isKind(*this)); |
136 | } |
137 | |
138 | const Stmt *getStmt() const { |
139 | return static_cast<const Stmt *>(Data1.getPointer()); |
140 | } |
141 | |
142 | private: |
143 | friend class CFGElement; |
144 | |
145 | static bool isKind(const CFGElement &E) { |
146 | return E.getKind() >= STMT_BEGIN && E.getKind() <= STMT_END; |
147 | } |
148 | |
149 | protected: |
150 | 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 | : CFGStmt(CE, Constructor) { |
161 | assert(C); |
162 | Data2.setPointer(const_cast<ConstructionContext *>(C)); |
163 | } |
164 | |
165 | const ConstructionContext *getConstructionContext() const { |
166 | return static_cast<ConstructionContext *>(Data2.getPointer()); |
167 | } |
168 | |
169 | private: |
170 | friend class CFGElement; |
171 | |
172 | CFGConstructor() = default; |
173 | |
174 | static bool isKind(const CFGElement &E) { |
175 | return E.getKind() == Constructor; |
176 | } |
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 | static bool isCXXRecordTypedCall(const Expr *E) { |
190 | 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 | return !E->isGLValue() && |
195 | E->getType().getCanonicalType()->getAsCXXRecordDecl(); |
196 | } |
197 | |
198 | explicit CFGCXXRecordTypedCall(const Expr *E, const ConstructionContext *C) |
199 | : CFGStmt(E, CXXRecordTypedCall) { |
200 | assert(isCXXRecordTypedCall(E)); |
201 | assert(C && (isa<TemporaryObjectConstructionContext>(C) || |
202 | // These are possible in C++17 due to mandatory copy elision. |
203 | isa<ReturnedValueConstructionContext>(C) || |
204 | isa<VariableConstructionContext>(C) || |
205 | isa<ConstructorInitializerConstructionContext>(C) || |
206 | isa<ArgumentConstructionContext>(C) || |
207 | isa<LambdaCaptureConstructionContext>(C))); |
208 | Data2.setPointer(const_cast<ConstructionContext *>(C)); |
209 | } |
210 | |
211 | const ConstructionContext *getConstructionContext() const { |
212 | return static_cast<ConstructionContext *>(Data2.getPointer()); |
213 | } |
214 | |
215 | private: |
216 | friend class CFGElement; |
217 | |
218 | CFGCXXRecordTypedCall() = default; |
219 | |
220 | static bool isKind(const CFGElement &E) { |
221 | return E.getKind() == CXXRecordTypedCall; |
222 | } |
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 | : CFGElement(Initializer, initializer) {} |
231 | |
232 | CXXCtorInitializer* getInitializer() const { |
233 | return static_cast<CXXCtorInitializer*>(Data1.getPointer()); |
234 | } |
235 | |
236 | private: |
237 | friend class CFGElement; |
238 | |
239 | CFGInitializer() = default; |
240 | |
241 | static bool isKind(const CFGElement &E) { |
242 | return E.getKind() == Initializer; |
243 | } |
244 | }; |
245 | |
246 | /// Represents C++ allocator call. |
247 | class CFGNewAllocator : public CFGElement { |
248 | public: |
249 | explicit CFGNewAllocator(const CXXNewExpr *S) |
250 | : CFGElement(NewAllocator, S) {} |
251 | |
252 | // Get the new expression. |
253 | const CXXNewExpr *getAllocatorExpr() const { |
254 | return static_cast<CXXNewExpr *>(Data1.getPointer()); |
255 | } |
256 | |
257 | private: |
258 | friend class CFGElement; |
259 | |
260 | CFGNewAllocator() = default; |
261 | |
262 | static bool isKind(const CFGElement &elem) { |
263 | return elem.getKind() == NewAllocator; |
264 | } |
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 | explicit CFGLoopExit(const Stmt *stmt) : CFGElement(LoopExit, stmt) {} |
276 | |
277 | const Stmt *getLoopStmt() const { |
278 | return static_cast<Stmt *>(Data1.getPointer()); |
279 | } |
280 | |
281 | private: |
282 | friend class CFGElement; |
283 | |
284 | CFGLoopExit() = default; |
285 | |
286 | static bool isKind(const CFGElement &elem) { |
287 | return elem.getKind() == LoopExit; |
288 | } |
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 | : CFGElement(LifetimeEnds, var, stmt) {} |
296 | |
297 | const VarDecl *getVarDecl() const { |
298 | return static_cast<VarDecl *>(Data1.getPointer()); |
299 | } |
300 | |
301 | const Stmt *getTriggerStmt() const { |
302 | return static_cast<Stmt *>(Data2.getPointer()); |
303 | } |
304 | |
305 | private: |
306 | friend class CFGElement; |
307 | |
308 | CFGLifetimeEnds() = default; |
309 | |
310 | static bool isKind(const CFGElement &elem) { |
311 | return elem.getKind() == LifetimeEnds; |
312 | } |
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 | CFGScopeBegin() {} |
320 | CFGScopeBegin(const VarDecl *VD, const Stmt *S) |
321 | : CFGElement(ScopeBegin, VD, S) {} |
322 | |
323 | // Get statement that triggered a new scope. |
324 | const Stmt *getTriggerStmt() const { |
325 | return static_cast<Stmt*>(Data2.getPointer()); |
326 | } |
327 | |
328 | // Get VD that triggered a new scope. |
329 | const VarDecl *getVarDecl() const { |
330 | return static_cast<VarDecl *>(Data1.getPointer()); |
331 | } |
332 | |
333 | private: |
334 | friend class CFGElement; |
335 | static bool isKind(const CFGElement &E) { |
336 | Kind kind = E.getKind(); |
337 | return kind == ScopeBegin; |
338 | } |
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 | CFGScopeEnd() {} |
346 | CFGScopeEnd(const VarDecl *VD, const Stmt *S) : CFGElement(ScopeEnd, VD, S) {} |
347 | |
348 | const VarDecl *getVarDecl() const { |
349 | return static_cast<VarDecl *>(Data1.getPointer()); |
350 | } |
351 | |
352 | const Stmt *getTriggerStmt() const { |
353 | return static_cast<Stmt *>(Data2.getPointer()); |
354 | } |
355 | |
356 | private: |
357 | friend class CFGElement; |
358 | static bool isKind(const CFGElement &E) { |
359 | Kind kind = E.getKind(); |
360 | return kind == ScopeEnd; |
361 | } |
362 | }; |
363 | |
364 | /// Represents C++ object destructor implicitly generated by compiler on various |
365 | /// occasions. |
366 | class CFGImplicitDtor : public CFGElement { |
367 | protected: |
368 | CFGImplicitDtor() = default; |
369 | |
370 | CFGImplicitDtor(Kind kind, const void *data1, const void *data2 = nullptr) |
371 | : CFGElement(kind, data1, data2) { |
372 | assert(kind >= DTOR_BEGIN && kind <= DTOR_END); |
373 | } |
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 | static bool isKind(const CFGElement &E) { |
383 | Kind kind = E.getKind(); |
384 | return kind >= DTOR_BEGIN && kind <= DTOR_END; |
385 | } |
386 | }; |
387 | |
388 | class CFGCleanupFunction final : public CFGElement { |
389 | public: |
390 | CFGCleanupFunction() = default; |
391 | CFGCleanupFunction(const VarDecl *VD) |
392 | : CFGElement(Kind::CleanupFunction, VD) { |
393 | assert(VD->hasAttr<CleanupAttr>()); |
394 | } |
395 | |
396 | const VarDecl *getVarDecl() const { |
397 | return static_cast<VarDecl *>(Data1.getPointer()); |
398 | } |
399 | |
400 | /// Returns the function to be called when cleaning up the var decl. |
401 | const FunctionDecl *getFunctionDecl() const { |
402 | const CleanupAttr *A = getVarDecl()->getAttr<CleanupAttr>(); |
403 | return A->getFunctionDecl(); |
404 | } |
405 | |
406 | private: |
407 | friend class CFGElement; |
408 | |
409 | static bool isKind(const CFGElement E) { |
410 | return E.getKind() == Kind::CleanupFunction; |
411 | } |
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 | : CFGImplicitDtor(AutomaticObjectDtor, var, stmt) {} |
421 | |
422 | const VarDecl *getVarDecl() const { |
423 | return static_cast<VarDecl*>(Data1.getPointer()); |
424 | } |
425 | |
426 | // Get statement end of which triggered the destructor call. |
427 | const Stmt *getTriggerStmt() const { |
428 | return static_cast<Stmt*>(Data2.getPointer()); |
429 | } |
430 | |
431 | private: |
432 | friend class CFGElement; |
433 | |
434 | CFGAutomaticObjDtor() = default; |
435 | |
436 | static bool isKind(const CFGElement &elem) { |
437 | return elem.getKind() == AutomaticObjectDtor; |
438 | } |
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 | : CFGImplicitDtor(DeleteDtor, RD, DE) {} |
446 | |
447 | const CXXRecordDecl *getCXXRecordDecl() const { |
448 | return static_cast<CXXRecordDecl*>(Data1.getPointer()); |
449 | } |
450 | |
451 | // Get Delete expression which triggered the destructor call. |
452 | const CXXDeleteExpr *getDeleteExpr() const { |
453 | return static_cast<CXXDeleteExpr *>(Data2.getPointer()); |
454 | } |
455 | |
456 | private: |
457 | friend class CFGElement; |
458 | |
459 | CFGDeleteDtor() = default; |
460 | |
461 | static bool isKind(const CFGElement &elem) { |
462 | return elem.getKind() == DeleteDtor; |
463 | } |
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 | : CFGImplicitDtor(BaseDtor, base) {} |
472 | |
473 | const CXXBaseSpecifier *getBaseSpecifier() const { |
474 | return static_cast<const CXXBaseSpecifier*>(Data1.getPointer()); |
475 | } |
476 | |
477 | private: |
478 | friend class CFGElement; |
479 | |
480 | CFGBaseDtor() = default; |
481 | |
482 | static bool isKind(const CFGElement &E) { |
483 | return E.getKind() == BaseDtor; |
484 | } |
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 | : CFGImplicitDtor(MemberDtor, field, nullptr) {} |
493 | |
494 | const FieldDecl *getFieldDecl() const { |
495 | return static_cast<const FieldDecl*>(Data1.getPointer()); |
496 | } |
497 | |
498 | private: |
499 | friend class CFGElement; |
500 | |
501 | CFGMemberDtor() = default; |
502 | |
503 | static bool isKind(const CFGElement &E) { |
504 | return E.getKind() == MemberDtor; |
505 | } |
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 | : CFGImplicitDtor(TemporaryDtor, expr, nullptr) {} |
514 | |
515 | const CXXBindTemporaryExpr *getBindTemporaryExpr() const { |
516 | return static_cast<const CXXBindTemporaryExpr *>(Data1.getPointer()); |
517 | } |
518 | |
519 | private: |
520 | friend class CFGElement; |
521 | |
522 | CFGTemporaryDtor() = default; |
523 | |
524 | static bool isKind(const CFGElement &E) { |
525 | return E.getKind() == TemporaryDtor; |
526 | } |
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 | CFGTerminator() { assert(!isValid()); } |
560 | CFGTerminator(Stmt *S, Kind K = StmtBranch) : Data(S, K) {} |
561 | |
562 | bool isValid() const { return Data.getOpaqueValue() != nullptr; } |
563 | Stmt *getStmt() { return Data.getPointer(); } |
564 | const Stmt *getStmt() const { return Data.getPointer(); } |
565 | Kind getKind() const { return static_cast<Kind>(Data.getInt()); } |
566 | |
567 | bool isStmtBranch() const { |
568 | return getKind() == StmtBranch; |
569 | } |
570 | bool isTemporaryDtorsBranch() const { |
571 | return getKind() == TemporaryDtorsBranch; |
572 | } |
573 | bool isVirtualBaseBranch() const { |
574 | return getKind() == VirtualBaseBranch; |
575 | } |
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 | 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 | void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(Elt: e, C); } |
620 | |
621 | reverse_iterator insert(reverse_iterator I, size_t Cnt, CFGElement E, |
622 | BumpVectorContext &C) { |
623 | return Impl.insert(I, Cnt, E, C); |
624 | } |
625 | |
626 | const_reference front() const { return Impl.back(); } |
627 | const_reference back() const { return Impl.front(); } |
628 | |
629 | iterator begin() { return Impl.rbegin(); } |
630 | iterator end() { return Impl.rend(); } |
631 | const_iterator begin() const { return Impl.rbegin(); } |
632 | const_iterator end() const { return Impl.rend(); } |
633 | reverse_iterator rbegin() { return Impl.begin(); } |
634 | reverse_iterator rend() { return Impl.end(); } |
635 | const_reverse_iterator rbegin() const { return Impl.begin(); } |
636 | const_reverse_iterator rend() const { return Impl.end(); } |
637 | |
638 | CFGElement operator[](size_t i) const { |
639 | assert(i < Impl.size()); |
640 | return Impl[Impl.size() - 1 - i]; |
641 | } |
642 | |
643 | size_t size() const { return Impl.size(); } |
644 | 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 | : Parent(Parent), Index(Index) {} |
667 | |
668 | template <bool IsOtherConst> |
669 | ElementRefImpl(ElementRefImpl<IsOtherConst> Other) |
670 | : ElementRefImpl(Other.Parent, Other.Index) {} |
671 | |
672 | size_t getIndexInBlock() const { return Index; } |
673 | |
674 | CFGBlockPtr getParent() { return Parent; } |
675 | 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 | bool operator==(ElementRefImpl Other) const { |
683 | return Parent == Other.Parent && Index == Other.Index; |
684 | } |
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(OS&: 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 | CFGBlock *getReachableBlock() const { |
839 | return ReachableBlock; |
840 | } |
841 | |
842 | /// Get the potentially unreachable block. |
843 | CFGBlock *getPossiblyUnreachableBlock() const { |
844 | return UnreachableBlock.getPointer(); |
845 | } |
846 | |
847 | /// Provide an implicit conversion to CFGBlock* so that |
848 | /// AdjacentBlock can be substituted for CFGBlock*. |
849 | operator CFGBlock*() const { |
850 | return getReachableBlock(); |
851 | } |
852 | |
853 | CFGBlock& operator *() const { |
854 | return *getReachableBlock(); |
855 | } |
856 | |
857 | CFGBlock* operator ->() const { |
858 | return getReachableBlock(); |
859 | } |
860 | |
861 | bool isReachable() const { |
862 | Kind K = (Kind) UnreachableBlock.getInt(); |
863 | return K == AB_Normal || K == AB_Alternate; |
864 | } |
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 | LLVM_PREFERRED_TYPE(bool) |
883 | unsigned HasNoReturnElement : 1; |
884 | |
885 | /// The parent CFG that owns this CFGBlock. |
886 | CFG *Parent; |
887 | |
888 | public: |
889 | explicit CFGBlock(unsigned blockid, BumpVectorContext &C, CFG *parent) |
890 | : Elements(C), Terminator(nullptr), BlockID(blockid), Preds(C, 1), |
891 | Succs(C, 1), HasNoReturnElement(false), Parent(parent) {} |
892 | |
893 | // Statement iterators |
894 | using iterator = ElementList::iterator; |
895 | using const_iterator = ElementList::const_iterator; |
896 | using reverse_iterator = ElementList::reverse_iterator; |
897 | using const_reverse_iterator = ElementList::const_reverse_iterator; |
898 | |
899 | size_t getIndexInCFG() const; |
900 | |
901 | CFGElement front() const { return Elements.front(); } |
902 | CFGElement back() const { return Elements.back(); } |
903 | |
904 | iterator begin() { return Elements.begin(); } |
905 | iterator end() { return Elements.end(); } |
906 | const_iterator begin() const { return Elements.begin(); } |
907 | const_iterator end() const { return Elements.end(); } |
908 | |
909 | reverse_iterator rbegin() { return Elements.rbegin(); } |
910 | reverse_iterator rend() { return Elements.rend(); } |
911 | const_reverse_iterator rbegin() const { return Elements.rbegin(); } |
912 | const_reverse_iterator rend() const { return Elements.rend(); } |
913 | |
914 | using CFGElementRef = ElementRefImpl<false>; |
915 | using ConstCFGElementRef = ElementRefImpl<true>; |
916 | |
917 | using ref_iterator = ElementRefIterator<false, false>; |
918 | using ref_iterator_range = llvm::iterator_range<ref_iterator>; |
919 | using const_ref_iterator = ElementRefIterator<false, true>; |
920 | using const_ref_iterator_range = llvm::iterator_range<const_ref_iterator>; |
921 | |
922 | using reverse_ref_iterator = ElementRefIterator<true, false>; |
923 | using reverse_ref_iterator_range = llvm::iterator_range<reverse_ref_iterator>; |
924 | |
925 | using const_reverse_ref_iterator = ElementRefIterator<true, true>; |
926 | using const_reverse_ref_iterator_range = |
927 | llvm::iterator_range<const_reverse_ref_iterator>; |
928 | |
929 | ref_iterator ref_begin() { return {this, begin()}; } |
930 | ref_iterator ref_end() { return {this, end()}; } |
931 | const_ref_iterator ref_begin() const { return {this, begin()}; } |
932 | const_ref_iterator ref_end() const { return {this, end()}; } |
933 | |
934 | reverse_ref_iterator rref_begin() { return {this, rbegin()}; } |
935 | reverse_ref_iterator rref_end() { return {this, rend()}; } |
936 | const_reverse_ref_iterator rref_begin() const { return {this, rbegin()}; } |
937 | const_reverse_ref_iterator rref_end() const { return {this, rend()}; } |
938 | |
939 | ref_iterator_range refs() { return {ref_begin(), ref_end()}; } |
940 | const_ref_iterator_range refs() const { return {ref_begin(), ref_end()}; } |
941 | reverse_ref_iterator_range rrefs() { return {rref_begin(), rref_end()}; } |
942 | const_reverse_ref_iterator_range rrefs() const { |
943 | return {rref_begin(), rref_end()}; |
944 | } |
945 | |
946 | unsigned size() const { return Elements.size(); } |
947 | bool empty() const { return Elements.empty(); } |
948 | |
949 | CFGElement operator[](size_t i) const { return Elements[i]; } |
950 | |
951 | // CFG iterators |
952 | using pred_iterator = AdjacentBlocks::iterator; |
953 | using const_pred_iterator = AdjacentBlocks::const_iterator; |
954 | using pred_reverse_iterator = AdjacentBlocks::reverse_iterator; |
955 | using const_pred_reverse_iterator = AdjacentBlocks::const_reverse_iterator; |
956 | using pred_range = llvm::iterator_range<pred_iterator>; |
957 | using pred_const_range = llvm::iterator_range<const_pred_iterator>; |
958 | |
959 | using succ_iterator = AdjacentBlocks::iterator; |
960 | using const_succ_iterator = AdjacentBlocks::const_iterator; |
961 | using succ_reverse_iterator = AdjacentBlocks::reverse_iterator; |
962 | using const_succ_reverse_iterator = AdjacentBlocks::const_reverse_iterator; |
963 | using succ_range = llvm::iterator_range<succ_iterator>; |
964 | using succ_const_range = llvm::iterator_range<const_succ_iterator>; |
965 | |
966 | pred_iterator pred_begin() { return Preds.begin(); } |
967 | pred_iterator pred_end() { return Preds.end(); } |
968 | const_pred_iterator pred_begin() const { return Preds.begin(); } |
969 | const_pred_iterator pred_end() const { return Preds.end(); } |
970 | |
971 | pred_reverse_iterator pred_rbegin() { return Preds.rbegin(); } |
972 | pred_reverse_iterator pred_rend() { return Preds.rend(); } |
973 | const_pred_reverse_iterator pred_rbegin() const { return Preds.rbegin(); } |
974 | const_pred_reverse_iterator pred_rend() const { return Preds.rend(); } |
975 | |
976 | pred_range preds() { |
977 | return pred_range(pred_begin(), pred_end()); |
978 | } |
979 | |
980 | pred_const_range preds() const { |
981 | return pred_const_range(pred_begin(), pred_end()); |
982 | } |
983 | |
984 | succ_iterator succ_begin() { return Succs.begin(); } |
985 | succ_iterator succ_end() { return Succs.end(); } |
986 | const_succ_iterator succ_begin() const { return Succs.begin(); } |
987 | const_succ_iterator succ_end() const { return Succs.end(); } |
988 | |
989 | succ_reverse_iterator succ_rbegin() { return Succs.rbegin(); } |
990 | succ_reverse_iterator succ_rend() { return Succs.rend(); } |
991 | const_succ_reverse_iterator succ_rbegin() const { return Succs.rbegin(); } |
992 | const_succ_reverse_iterator succ_rend() const { return Succs.rend(); } |
993 | |
994 | succ_range succs() { |
995 | return succ_range(succ_begin(), succ_end()); |
996 | } |
997 | |
998 | succ_const_range succs() const { |
999 | return succ_const_range(succ_begin(), succ_end()); |
1000 | } |
1001 | |
1002 | unsigned succ_size() const { return Succs.size(); } |
1003 | bool succ_empty() const { return Succs.empty(); } |
1004 | |
1005 | unsigned pred_size() const { return Preds.size(); } |
1006 | bool pred_empty() const { return Preds.empty(); } |
1007 | |
1008 | |
1009 | class FilterOptions { |
1010 | public: |
1011 | LLVM_PREFERRED_TYPE(bool) |
1012 | unsigned IgnoreNullPredecessors : 1; |
1013 | LLVM_PREFERRED_TYPE(bool) |
1014 | unsigned IgnoreDefaultsWithCoveredEnums : 1; |
1015 | |
1016 | FilterOptions() |
1017 | : IgnoreNullPredecessors(1), IgnoreDefaultsWithCoveredEnums(0) {} |
1018 | }; |
1019 | |
1020 | static bool FilterEdge(const FilterOptions &F, const CFGBlock *Src, |
1021 | const CFGBlock *Dst); |
1022 | |
1023 | template <typename IMPL, bool IsPred> |
1024 | class FilteredCFGBlockIterator { |
1025 | private: |
1026 | IMPL I, E; |
1027 | const FilterOptions F; |
1028 | const CFGBlock *From; |
1029 | |
1030 | public: |
1031 | explicit FilteredCFGBlockIterator(const IMPL &i, const IMPL &e, |
1032 | const CFGBlock *from, |
1033 | const FilterOptions &f) |
1034 | : I(i), E(e), F(f), From(from) { |
1035 | while (hasMore() && Filter(To: *I)) |
1036 | ++I; |
1037 | } |
1038 | |
1039 | bool hasMore() const { return I != E; } |
1040 | |
1041 | FilteredCFGBlockIterator &operator++() { |
1042 | do { ++I; } while (hasMore() && Filter(To: *I)); |
1043 | return *this; |
1044 | } |
1045 | |
1046 | const CFGBlock *operator*() const { return *I; } |
1047 | |
1048 | private: |
1049 | bool Filter(const CFGBlock *To) { |
1050 | return IsPred ? FilterEdge(F, Src: To, Dst: From) : FilterEdge(F, Src: From, Dst: To); |
1051 | } |
1052 | }; |
1053 | |
1054 | using filtered_pred_iterator = |
1055 | FilteredCFGBlockIterator<const_pred_iterator, true>; |
1056 | |
1057 | using filtered_succ_iterator = |
1058 | FilteredCFGBlockIterator<const_succ_iterator, false>; |
1059 | |
1060 | filtered_pred_iterator filtered_pred_start_end(const FilterOptions &f) const { |
1061 | return filtered_pred_iterator(pred_begin(), pred_end(), this, f); |
1062 | } |
1063 | |
1064 | filtered_succ_iterator filtered_succ_start_end(const FilterOptions &f) const { |
1065 | return filtered_succ_iterator(succ_begin(), succ_end(), this, f); |
1066 | } |
1067 | |
1068 | // Manipulation of block contents |
1069 | |
1070 | void setTerminator(CFGTerminator Term) { Terminator = Term; } |
1071 | void setLabel(Stmt *Statement) { Label = Statement; } |
1072 | void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; } |
1073 | void setHasNoReturnElement() { HasNoReturnElement = true; } |
1074 | |
1075 | /// Returns true if the block would eventually end with a sink (a noreturn |
1076 | /// node). |
1077 | bool isInevitablySinking() const; |
1078 | |
1079 | CFGTerminator getTerminator() const { return Terminator; } |
1080 | |
1081 | Stmt *getTerminatorStmt() { return Terminator.getStmt(); } |
1082 | const Stmt *getTerminatorStmt() const { return Terminator.getStmt(); } |
1083 | |
1084 | /// \returns the last (\c rbegin()) condition, e.g. observe the following code |
1085 | /// snippet: |
1086 | /// if (A && B && C) |
1087 | /// A block would be created for \c A, \c B, and \c C. For the latter, |
1088 | /// \c getTerminatorStmt() would retrieve the entire condition, rather than |
1089 | /// C itself, while this method would only return C. |
1090 | const Expr *getLastCondition() const; |
1091 | |
1092 | Stmt *getTerminatorCondition(bool StripParens = true); |
1093 | |
1094 | const Stmt *getTerminatorCondition(bool StripParens = true) const { |
1095 | return const_cast<CFGBlock*>(this)->getTerminatorCondition(StripParens); |
1096 | } |
1097 | |
1098 | const Stmt *getLoopTarget() const { return LoopTarget; } |
1099 | |
1100 | Stmt *getLabel() { return Label; } |
1101 | const Stmt *getLabel() const { return Label; } |
1102 | |
1103 | bool hasNoReturnElement() const { return HasNoReturnElement; } |
1104 | |
1105 | unsigned getBlockID() const { return BlockID; } |
1106 | |
1107 | CFG *getParent() const { return Parent; } |
1108 | |
1109 | void dump() const; |
1110 | |
1111 | void dump(const CFG *cfg, const LangOptions &LO, bool ShowColors = false) const; |
1112 | void print(raw_ostream &OS, const CFG* cfg, const LangOptions &LO, |
1113 | bool ShowColors) const; |
1114 | |
1115 | void printTerminator(raw_ostream &OS, const LangOptions &LO) const; |
1116 | void printTerminatorJson(raw_ostream &Out, const LangOptions &LO, |
1117 | bool AddQuotes) const; |
1118 | |
1119 | void printAsOperand(raw_ostream &OS, bool /*PrintType*/) { |
1120 | OS << "BB#" << getBlockID(); |
1121 | } |
1122 | |
1123 | /// Adds a (potentially unreachable) successor block to the current block. |
1124 | void addSuccessor(AdjacentBlock Succ, BumpVectorContext &C); |
1125 | |
1126 | void appendStmt(Stmt *statement, BumpVectorContext &C) { |
1127 | Elements.push_back(e: CFGStmt(statement), C); |
1128 | } |
1129 | |
1130 | void appendConstructor(CXXConstructExpr *CE, const ConstructionContext *CC, |
1131 | BumpVectorContext &C) { |
1132 | Elements.push_back(e: CFGConstructor(CE, CC), C); |
1133 | } |
1134 | |
1135 | void appendCXXRecordTypedCall(Expr *E, |
1136 | const ConstructionContext *CC, |
1137 | BumpVectorContext &C) { |
1138 | Elements.push_back(e: CFGCXXRecordTypedCall(E, CC), C); |
1139 | } |
1140 | |
1141 | void appendInitializer(CXXCtorInitializer *initializer, |
1142 | BumpVectorContext &C) { |
1143 | Elements.push_back(e: CFGInitializer(initializer), C); |
1144 | } |
1145 | |
1146 | void appendNewAllocator(CXXNewExpr *NE, |
1147 | BumpVectorContext &C) { |
1148 | Elements.push_back(e: CFGNewAllocator(NE), C); |
1149 | } |
1150 | |
1151 | void appendScopeBegin(const VarDecl *VD, const Stmt *S, |
1152 | BumpVectorContext &C) { |
1153 | Elements.push_back(e: CFGScopeBegin(VD, S), C); |
1154 | } |
1155 | |
1156 | void appendScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) { |
1157 | Elements.push_back(e: CFGScopeEnd(VD, S), C); |
1158 | } |
1159 | |
1160 | void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) { |
1161 | Elements.push_back(e: CFGBaseDtor(BS), C); |
1162 | } |
1163 | |
1164 | void appendMemberDtor(FieldDecl *FD, BumpVectorContext &C) { |
1165 | Elements.push_back(e: CFGMemberDtor(FD), C); |
1166 | } |
1167 | |
1168 | void appendTemporaryDtor(CXXBindTemporaryExpr *E, BumpVectorContext &C) { |
1169 | Elements.push_back(e: CFGTemporaryDtor(E), C); |
1170 | } |
1171 | |
1172 | void appendAutomaticObjDtor(VarDecl *VD, Stmt *S, BumpVectorContext &C) { |
1173 | Elements.push_back(e: CFGAutomaticObjDtor(VD, S), C); |
1174 | } |
1175 | |
1176 | void appendCleanupFunction(const VarDecl *VD, BumpVectorContext &C) { |
1177 | Elements.push_back(e: CFGCleanupFunction(VD), C); |
1178 | } |
1179 | |
1180 | void appendLifetimeEnds(VarDecl *VD, Stmt *S, BumpVectorContext &C) { |
1181 | Elements.push_back(e: CFGLifetimeEnds(VD, S), C); |
1182 | } |
1183 | |
1184 | void appendLoopExit(const Stmt *LoopStmt, BumpVectorContext &C) { |
1185 | Elements.push_back(e: CFGLoopExit(LoopStmt), C); |
1186 | } |
1187 | |
1188 | void appendDeleteDtor(CXXRecordDecl *RD, CXXDeleteExpr *DE, BumpVectorContext &C) { |
1189 | Elements.push_back(e: CFGDeleteDtor(RD, DE), C); |
1190 | } |
1191 | }; |
1192 | |
1193 | /// CFGCallback defines methods that should be called when a logical |
1194 | /// operator error is found when building the CFG. |
1195 | class CFGCallback { |
1196 | public: |
1197 | CFGCallback() = default; |
1198 | virtual ~CFGCallback() = default; |
1199 | |
1200 | virtual void logicAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {} |
1201 | virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {} |
1202 | virtual void compareBitwiseEquality(const BinaryOperator *B, |
1203 | bool isAlwaysTrue) {} |
1204 | virtual void compareBitwiseOr(const BinaryOperator *B) {} |
1205 | }; |
1206 | |
1207 | /// Represents a source-level, intra-procedural CFG that represents the |
1208 | /// control-flow of a Stmt. The Stmt can represent an entire function body, |
1209 | /// or a single expression. A CFG will always contain one empty block that |
1210 | /// represents the Exit point of the CFG. A CFG will also contain a designated |
1211 | /// Entry block. The CFG solely represents control-flow; it consists of |
1212 | /// CFGBlocks which are simply containers of Stmt*'s in the AST the CFG |
1213 | /// was constructed from. |
1214 | class CFG { |
1215 | public: |
1216 | //===--------------------------------------------------------------------===// |
1217 | // CFG Construction & Manipulation. |
1218 | //===--------------------------------------------------------------------===// |
1219 | |
1220 | class BuildOptions { |
1221 | // Stmt::lastStmtConstant has the same value as the last Stmt kind, |
1222 | // so make sure we add one to account for this! |
1223 | std::bitset<Stmt::lastStmtConstant + 1> alwaysAddMask; |
1224 | |
1225 | public: |
1226 | using ForcedBlkExprs = llvm::DenseMap<const Stmt *, const CFGBlock *>; |
1227 | |
1228 | ForcedBlkExprs **forcedBlkExprs = nullptr; |
1229 | CFGCallback *Observer = nullptr; |
1230 | bool PruneTriviallyFalseEdges = true; |
1231 | bool AddEHEdges = false; |
1232 | bool AddInitializers = false; |
1233 | bool AddImplicitDtors = false; |
1234 | bool AddLifetime = false; |
1235 | bool AddLoopExit = false; |
1236 | bool AddTemporaryDtors = false; |
1237 | bool AddScopes = false; |
1238 | bool AddStaticInitBranches = false; |
1239 | bool AddCXXNewAllocator = false; |
1240 | bool AddCXXDefaultInitExprInCtors = false; |
1241 | bool AddCXXDefaultInitExprInAggregates = false; |
1242 | bool AddRichCXXConstructors = false; |
1243 | bool MarkElidedCXXConstructors = false; |
1244 | bool AddVirtualBaseBranches = false; |
1245 | bool OmitImplicitValueInitializers = false; |
1246 | |
1247 | BuildOptions() = default; |
1248 | |
1249 | bool alwaysAdd(const Stmt *stmt) const { |
1250 | return alwaysAddMask[stmt->getStmtClass()]; |
1251 | } |
1252 | |
1253 | BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) { |
1254 | alwaysAddMask[stmtClass] = val; |
1255 | return *this; |
1256 | } |
1257 | |
1258 | BuildOptions &setAllAlwaysAdd() { |
1259 | alwaysAddMask.set(); |
1260 | return *this; |
1261 | } |
1262 | }; |
1263 | |
1264 | /// Builds a CFG from an AST. |
1265 | static std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *AST, ASTContext *C, |
1266 | const BuildOptions &BO); |
1267 | |
1268 | /// Create a new block in the CFG. The CFG owns the block; the caller should |
1269 | /// not directly free it. |
1270 | CFGBlock *createBlock(); |
1271 | |
1272 | /// Set the entry block of the CFG. This is typically used only during CFG |
1273 | /// construction. Most CFG clients expect that the entry block has no |
1274 | /// predecessors and contains no statements. |
1275 | void setEntry(CFGBlock *B) { Entry = B; } |
1276 | |
1277 | /// Set the block used for indirect goto jumps. This is typically used only |
1278 | /// during CFG construction. |
1279 | void setIndirectGotoBlock(CFGBlock *B) { IndirectGotoBlock = B; } |
1280 | |
1281 | //===--------------------------------------------------------------------===// |
1282 | // Block Iterators |
1283 | //===--------------------------------------------------------------------===// |
1284 | |
1285 | using CFGBlockListTy = BumpVector<CFGBlock *>; |
1286 | using iterator = CFGBlockListTy::iterator; |
1287 | using const_iterator = CFGBlockListTy::const_iterator; |
1288 | using reverse_iterator = std::reverse_iterator<iterator>; |
1289 | using const_reverse_iterator = std::reverse_iterator<const_iterator>; |
1290 | |
1291 | CFGBlock & front() { return *Blocks.front(); } |
1292 | CFGBlock & back() { return *Blocks.back(); } |
1293 | |
1294 | iterator begin() { return Blocks.begin(); } |
1295 | iterator end() { return Blocks.end(); } |
1296 | const_iterator begin() const { return Blocks.begin(); } |
1297 | const_iterator end() const { return Blocks.end(); } |
1298 | |
1299 | iterator nodes_begin() { return iterator(Blocks.begin()); } |
1300 | iterator nodes_end() { return iterator(Blocks.end()); } |
1301 | |
1302 | llvm::iterator_range<iterator> nodes() { return {begin(), end()}; } |
1303 | llvm::iterator_range<const_iterator> const_nodes() const { |
1304 | return {begin(), end()}; |
1305 | } |
1306 | |
1307 | const_iterator nodes_begin() const { return const_iterator(Blocks.begin()); } |
1308 | const_iterator nodes_end() const { return const_iterator(Blocks.end()); } |
1309 | |
1310 | reverse_iterator rbegin() { return Blocks.rbegin(); } |
1311 | reverse_iterator rend() { return Blocks.rend(); } |
1312 | const_reverse_iterator rbegin() const { return Blocks.rbegin(); } |
1313 | const_reverse_iterator rend() const { return Blocks.rend(); } |
1314 | |
1315 | llvm::iterator_range<reverse_iterator> reverse_nodes() { |
1316 | return {rbegin(), rend()}; |
1317 | } |
1318 | llvm::iterator_range<const_reverse_iterator> const_reverse_nodes() const { |
1319 | return {rbegin(), rend()}; |
1320 | } |
1321 | |
1322 | CFGBlock & getEntry() { return *Entry; } |
1323 | const CFGBlock & getEntry() const { return *Entry; } |
1324 | CFGBlock & getExit() { return *Exit; } |
1325 | const CFGBlock & getExit() const { return *Exit; } |
1326 | |
1327 | CFGBlock * getIndirectGotoBlock() { return IndirectGotoBlock; } |
1328 | const CFGBlock * getIndirectGotoBlock() const { return IndirectGotoBlock; } |
1329 | |
1330 | using try_block_iterator = std::vector<const CFGBlock *>::const_iterator; |
1331 | using try_block_range = llvm::iterator_range<try_block_iterator>; |
1332 | |
1333 | try_block_iterator try_blocks_begin() const { |
1334 | return TryDispatchBlocks.begin(); |
1335 | } |
1336 | |
1337 | try_block_iterator try_blocks_end() const { |
1338 | return TryDispatchBlocks.end(); |
1339 | } |
1340 | |
1341 | try_block_range try_blocks() const { |
1342 | return try_block_range(try_blocks_begin(), try_blocks_end()); |
1343 | } |
1344 | |
1345 | void addTryDispatchBlock(const CFGBlock *block) { |
1346 | TryDispatchBlocks.push_back(x: block); |
1347 | } |
1348 | |
1349 | /// Records a synthetic DeclStmt and the DeclStmt it was constructed from. |
1350 | /// |
1351 | /// The CFG uses synthetic DeclStmts when a single AST DeclStmt contains |
1352 | /// multiple decls. |
1353 | void addSyntheticDeclStmt(const DeclStmt *Synthetic, |
1354 | const DeclStmt *Source) { |
1355 | assert(Synthetic->isSingleDecl() && "Can handle single declarations only" ); |
1356 | assert(Synthetic != Source && "Don't include original DeclStmts in map" ); |
1357 | assert(!SyntheticDeclStmts.count(Synthetic) && "Already in map" ); |
1358 | SyntheticDeclStmts[Synthetic] = Source; |
1359 | } |
1360 | |
1361 | using synthetic_stmt_iterator = |
1362 | llvm::DenseMap<const DeclStmt *, const DeclStmt *>::const_iterator; |
1363 | using synthetic_stmt_range = llvm::iterator_range<synthetic_stmt_iterator>; |
1364 | |
1365 | /// Iterates over synthetic DeclStmts in the CFG. |
1366 | /// |
1367 | /// Each element is a (synthetic statement, source statement) pair. |
1368 | /// |
1369 | /// \sa addSyntheticDeclStmt |
1370 | synthetic_stmt_iterator synthetic_stmt_begin() const { |
1371 | return SyntheticDeclStmts.begin(); |
1372 | } |
1373 | |
1374 | /// \sa synthetic_stmt_begin |
1375 | synthetic_stmt_iterator synthetic_stmt_end() const { |
1376 | return SyntheticDeclStmts.end(); |
1377 | } |
1378 | |
1379 | /// \sa synthetic_stmt_begin |
1380 | synthetic_stmt_range synthetic_stmts() const { |
1381 | return synthetic_stmt_range(synthetic_stmt_begin(), synthetic_stmt_end()); |
1382 | } |
1383 | |
1384 | //===--------------------------------------------------------------------===// |
1385 | // Member templates useful for various batch operations over CFGs. |
1386 | //===--------------------------------------------------------------------===// |
1387 | |
1388 | template <typename Callback> void VisitBlockStmts(Callback &O) const { |
1389 | for (const_iterator I = begin(), E = end(); I != E; ++I) |
1390 | for (CFGBlock::const_iterator BI = (*I)->begin(), BE = (*I)->end(); |
1391 | BI != BE; ++BI) { |
1392 | if (std::optional<CFGStmt> stmt = BI->getAs<CFGStmt>()) |
1393 | O(const_cast<Stmt *>(stmt->getStmt())); |
1394 | } |
1395 | } |
1396 | |
1397 | //===--------------------------------------------------------------------===// |
1398 | // CFG Introspection. |
1399 | //===--------------------------------------------------------------------===// |
1400 | |
1401 | /// Returns the total number of BlockIDs allocated (which start at 0). |
1402 | unsigned getNumBlockIDs() const { return NumBlockIDs; } |
1403 | |
1404 | /// Return the total number of CFGBlocks within the CFG This is simply a |
1405 | /// renaming of the getNumBlockIDs(). This is necessary because the dominator |
1406 | /// implementation needs such an interface. |
1407 | unsigned size() const { return NumBlockIDs; } |
1408 | |
1409 | /// Returns true if the CFG has no branches. Usually it boils down to the CFG |
1410 | /// having exactly three blocks (entry, the actual code, exit), but sometimes |
1411 | /// more blocks appear due to having control flow that can be fully |
1412 | /// resolved in compile time. |
1413 | bool isLinear() const; |
1414 | |
1415 | //===--------------------------------------------------------------------===// |
1416 | // CFG Debugging: Pretty-Printing and Visualization. |
1417 | //===--------------------------------------------------------------------===// |
1418 | |
1419 | void viewCFG(const LangOptions &LO) const; |
1420 | void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const; |
1421 | void dump(const LangOptions &LO, bool ShowColors) const; |
1422 | |
1423 | //===--------------------------------------------------------------------===// |
1424 | // Internal: constructors and data. |
1425 | //===--------------------------------------------------------------------===// |
1426 | |
1427 | CFG() : Blocks(BlkBVC, 10) {} |
1428 | |
1429 | llvm::BumpPtrAllocator& getAllocator() { |
1430 | return BlkBVC.getAllocator(); |
1431 | } |
1432 | |
1433 | BumpVectorContext &getBumpVectorContext() { |
1434 | return BlkBVC; |
1435 | } |
1436 | |
1437 | private: |
1438 | CFGBlock *Entry = nullptr; |
1439 | CFGBlock *Exit = nullptr; |
1440 | |
1441 | // Special block to contain collective dispatch for indirect gotos |
1442 | CFGBlock* IndirectGotoBlock = nullptr; |
1443 | |
1444 | unsigned NumBlockIDs = 0; |
1445 | |
1446 | BumpVectorContext BlkBVC; |
1447 | |
1448 | CFGBlockListTy Blocks; |
1449 | |
1450 | /// C++ 'try' statements are modeled with an indirect dispatch block. |
1451 | /// This is the collection of such blocks present in the CFG. |
1452 | std::vector<const CFGBlock *> TryDispatchBlocks; |
1453 | |
1454 | /// Collects DeclStmts synthesized for this CFG and maps each one back to its |
1455 | /// source DeclStmt. |
1456 | llvm::DenseMap<const DeclStmt *, const DeclStmt *> SyntheticDeclStmts; |
1457 | }; |
1458 | |
1459 | Expr *(const ArrayInitLoopExpr *AILE); |
1460 | |
1461 | } // namespace clang |
1462 | |
1463 | //===----------------------------------------------------------------------===// |
1464 | // GraphTraits specializations for CFG basic block graphs (source-level CFGs) |
1465 | //===----------------------------------------------------------------------===// |
1466 | |
1467 | namespace llvm { |
1468 | |
1469 | /// Implement simplify_type for CFGTerminator, so that we can dyn_cast from |
1470 | /// CFGTerminator to a specific Stmt class. |
1471 | template <> struct simplify_type< ::clang::CFGTerminator> { |
1472 | using SimpleType = ::clang::Stmt *; |
1473 | |
1474 | static SimpleType getSimplifiedValue(::clang::CFGTerminator Val) { |
1475 | return Val.getStmt(); |
1476 | } |
1477 | }; |
1478 | |
1479 | // Traits for: CFGBlock |
1480 | |
1481 | template <> struct GraphTraits< ::clang::CFGBlock *> { |
1482 | using NodeRef = ::clang::CFGBlock *; |
1483 | using ChildIteratorType = ::clang::CFGBlock::succ_iterator; |
1484 | |
1485 | static NodeRef getEntryNode(::clang::CFGBlock *BB) { return BB; } |
1486 | static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } |
1487 | static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } |
1488 | }; |
1489 | |
1490 | template <> struct GraphTraits< const ::clang::CFGBlock *> { |
1491 | using NodeRef = const ::clang::CFGBlock *; |
1492 | using ChildIteratorType = ::clang::CFGBlock::const_succ_iterator; |
1493 | |
1494 | static NodeRef getEntryNode(const clang::CFGBlock *BB) { return BB; } |
1495 | static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); } |
1496 | static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); } |
1497 | }; |
1498 | |
1499 | template <> struct GraphTraits<Inverse< ::clang::CFGBlock *>> { |
1500 | using NodeRef = ::clang::CFGBlock *; |
1501 | using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator; |
1502 | |
1503 | static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G) { |
1504 | return G.Graph; |
1505 | } |
1506 | |
1507 | static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); } |
1508 | static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); } |
1509 | }; |
1510 | |
1511 | template <> struct GraphTraits<Inverse<const ::clang::CFGBlock *>> { |
1512 | using NodeRef = const ::clang::CFGBlock *; |
1513 | using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator; |
1514 | |
1515 | static NodeRef getEntryNode(Inverse<const ::clang::CFGBlock *> G) { |
1516 | return G.Graph; |
1517 | } |
1518 | |
1519 | static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); } |
1520 | static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); } |
1521 | }; |
1522 | |
1523 | // Traits for: CFG |
1524 | |
1525 | template <> struct GraphTraits< ::clang::CFG* > |
1526 | : public GraphTraits< ::clang::CFGBlock *> { |
1527 | using nodes_iterator = ::clang::CFG::iterator; |
1528 | |
1529 | static NodeRef getEntryNode(::clang::CFG *F) { return &F->getEntry(); } |
1530 | static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();} |
1531 | static nodes_iterator nodes_end(::clang::CFG* F) { return F->nodes_end(); } |
1532 | static unsigned size(::clang::CFG* F) { return F->size(); } |
1533 | }; |
1534 | |
1535 | template <> struct GraphTraits<const ::clang::CFG* > |
1536 | : public GraphTraits<const ::clang::CFGBlock *> { |
1537 | using nodes_iterator = ::clang::CFG::const_iterator; |
1538 | |
1539 | static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getEntry(); } |
1540 | |
1541 | static nodes_iterator nodes_begin( const ::clang::CFG* F) { |
1542 | return F->nodes_begin(); |
1543 | } |
1544 | |
1545 | static nodes_iterator nodes_end( const ::clang::CFG* F) { |
1546 | return F->nodes_end(); |
1547 | } |
1548 | |
1549 | static unsigned size(const ::clang::CFG* F) { |
1550 | return F->size(); |
1551 | } |
1552 | }; |
1553 | |
1554 | template <> struct GraphTraits<Inverse< ::clang::CFG *>> |
1555 | : public GraphTraits<Inverse< ::clang::CFGBlock *>> { |
1556 | using nodes_iterator = ::clang::CFG::iterator; |
1557 | |
1558 | static NodeRef getEntryNode(::clang::CFG *F) { return &F->getExit(); } |
1559 | static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();} |
1560 | static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); } |
1561 | }; |
1562 | |
1563 | template <> struct GraphTraits<Inverse<const ::clang::CFG *>> |
1564 | : public GraphTraits<Inverse<const ::clang::CFGBlock *>> { |
1565 | using nodes_iterator = ::clang::CFG::const_iterator; |
1566 | |
1567 | static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getExit(); } |
1568 | |
1569 | static nodes_iterator nodes_begin(const ::clang::CFG* F) { |
1570 | return F->nodes_begin(); |
1571 | } |
1572 | |
1573 | static nodes_iterator nodes_end(const ::clang::CFG* F) { |
1574 | return F->nodes_end(); |
1575 | } |
1576 | }; |
1577 | |
1578 | } // namespace llvm |
1579 | |
1580 | #endif // LLVM_CLANG_ANALYSIS_CFG_H |
1581 | |