10b57cec5SDimitry Andric //===- CFG.h - Classes for representing and building CFGs -------*- C++ -*-===//
20b57cec5SDimitry Andric //
30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
60b57cec5SDimitry Andric //
70b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
80b57cec5SDimitry Andric //
90b57cec5SDimitry Andric //  This file defines the CFG and CFGBuilder classes for representing and
100b57cec5SDimitry Andric //  building Control-Flow Graphs (CFGs) from ASTs.
110b57cec5SDimitry Andric //
120b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
130b57cec5SDimitry Andric 
140b57cec5SDimitry Andric #ifndef LLVM_CLANG_ANALYSIS_CFG_H
150b57cec5SDimitry Andric #define LLVM_CLANG_ANALYSIS_CFG_H
160b57cec5SDimitry Andric 
175f757f3fSDimitry Andric #include "clang/AST/Attr.h"
180b57cec5SDimitry Andric #include "clang/AST/ExprCXX.h"
190b57cec5SDimitry Andric #include "clang/AST/ExprObjC.h"
205f757f3fSDimitry Andric #include "clang/Analysis/ConstructionContext.h"
215f757f3fSDimitry Andric #include "clang/Analysis/Support/BumpVector.h"
220b57cec5SDimitry Andric #include "clang/Basic/LLVM.h"
230b57cec5SDimitry Andric #include "llvm/ADT/DenseMap.h"
240b57cec5SDimitry Andric #include "llvm/ADT/GraphTraits.h"
250b57cec5SDimitry Andric #include "llvm/ADT/PointerIntPair.h"
260b57cec5SDimitry Andric #include "llvm/ADT/iterator_range.h"
270b57cec5SDimitry Andric #include "llvm/Support/Allocator.h"
280b57cec5SDimitry Andric #include "llvm/Support/raw_ostream.h"
290b57cec5SDimitry Andric #include <bitset>
300b57cec5SDimitry Andric #include <cassert>
310b57cec5SDimitry Andric #include <cstddef>
320b57cec5SDimitry Andric #include <iterator>
330b57cec5SDimitry Andric #include <memory>
34bdd1243dSDimitry Andric #include <optional>
350b57cec5SDimitry Andric #include <vector>
360b57cec5SDimitry Andric 
370b57cec5SDimitry Andric namespace clang {
380b57cec5SDimitry Andric 
390b57cec5SDimitry Andric class ASTContext;
400b57cec5SDimitry Andric class BinaryOperator;
410b57cec5SDimitry Andric class CFG;
420b57cec5SDimitry Andric class CXXBaseSpecifier;
430b57cec5SDimitry Andric class CXXBindTemporaryExpr;
440b57cec5SDimitry Andric class CXXCtorInitializer;
450b57cec5SDimitry Andric class CXXDeleteExpr;
460b57cec5SDimitry Andric class CXXDestructorDecl;
470b57cec5SDimitry Andric class CXXNewExpr;
480b57cec5SDimitry Andric class CXXRecordDecl;
490b57cec5SDimitry Andric class Decl;
500b57cec5SDimitry Andric class FieldDecl;
510b57cec5SDimitry Andric class LangOptions;
520b57cec5SDimitry Andric class VarDecl;
530b57cec5SDimitry Andric 
540b57cec5SDimitry Andric /// Represents a top-level expression in a basic block.
550b57cec5SDimitry Andric class CFGElement {
560b57cec5SDimitry Andric public:
570b57cec5SDimitry Andric   enum Kind {
580b57cec5SDimitry Andric     // main kind
590b57cec5SDimitry Andric     Initializer,
600b57cec5SDimitry Andric     ScopeBegin,
610b57cec5SDimitry Andric     ScopeEnd,
620b57cec5SDimitry Andric     NewAllocator,
630b57cec5SDimitry Andric     LifetimeEnds,
640b57cec5SDimitry Andric     LoopExit,
650b57cec5SDimitry Andric     // stmt kind
660b57cec5SDimitry Andric     Statement,
670b57cec5SDimitry Andric     Constructor,
680b57cec5SDimitry Andric     CXXRecordTypedCall,
690b57cec5SDimitry Andric     STMT_BEGIN = Statement,
700b57cec5SDimitry Andric     STMT_END = CXXRecordTypedCall,
710b57cec5SDimitry Andric     // dtor kind
720b57cec5SDimitry Andric     AutomaticObjectDtor,
730b57cec5SDimitry Andric     DeleteDtor,
740b57cec5SDimitry Andric     BaseDtor,
750b57cec5SDimitry Andric     MemberDtor,
760b57cec5SDimitry Andric     TemporaryDtor,
770b57cec5SDimitry Andric     DTOR_BEGIN = AutomaticObjectDtor,
785f757f3fSDimitry Andric     DTOR_END = TemporaryDtor,
795f757f3fSDimitry Andric     CleanupFunction,
800b57cec5SDimitry Andric   };
810b57cec5SDimitry Andric 
820b57cec5SDimitry Andric protected:
830b57cec5SDimitry Andric   // The int bits are used to mark the kind.
840b57cec5SDimitry Andric   llvm::PointerIntPair<void *, 2> Data1;
850b57cec5SDimitry Andric   llvm::PointerIntPair<void *, 2> Data2;
860b57cec5SDimitry Andric 
870b57cec5SDimitry Andric   CFGElement(Kind kind, const void *Ptr1, const void *Ptr2 = nullptr)
880b57cec5SDimitry Andric       : Data1(const_cast<void*>(Ptr1), ((unsigned) kind) & 0x3),
890b57cec5SDimitry Andric         Data2(const_cast<void*>(Ptr2), (((unsigned) kind) >> 2) & 0x3) {
900b57cec5SDimitry Andric     assert(getKind() == kind);
910b57cec5SDimitry Andric   }
920b57cec5SDimitry Andric 
930b57cec5SDimitry Andric   CFGElement() = default;
940b57cec5SDimitry Andric 
950b57cec5SDimitry Andric public:
960b57cec5SDimitry Andric   /// Convert to the specified CFGElement type, asserting that this
970b57cec5SDimitry Andric   /// CFGElement is of the desired type.
980b57cec5SDimitry Andric   template<typename T>
castAs()990b57cec5SDimitry Andric   T castAs() const {
1000b57cec5SDimitry Andric     assert(T::isKind(*this));
1010b57cec5SDimitry Andric     T t;
1020b57cec5SDimitry Andric     CFGElement& e = t;
1030b57cec5SDimitry Andric     e = *this;
1040b57cec5SDimitry Andric     return t;
1050b57cec5SDimitry Andric   }
1060b57cec5SDimitry Andric 
107bdd1243dSDimitry Andric   /// Convert to the specified CFGElement type, returning std::nullopt if this
1080b57cec5SDimitry Andric   /// CFGElement is not of the desired type.
getAs()109bdd1243dSDimitry Andric   template <typename T> std::optional<T> getAs() const {
1100b57cec5SDimitry Andric     if (!T::isKind(*this))
111bdd1243dSDimitry Andric       return std::nullopt;
1120b57cec5SDimitry Andric     T t;
1130b57cec5SDimitry Andric     CFGElement& e = t;
1140b57cec5SDimitry Andric     e = *this;
1150b57cec5SDimitry Andric     return t;
1160b57cec5SDimitry Andric   }
1170b57cec5SDimitry Andric 
getKind()1180b57cec5SDimitry Andric   Kind getKind() const {
1190b57cec5SDimitry Andric     unsigned x = Data2.getInt();
1200b57cec5SDimitry Andric     x <<= 2;
1210b57cec5SDimitry Andric     x |= Data1.getInt();
1220b57cec5SDimitry Andric     return (Kind) x;
1230b57cec5SDimitry Andric   }
124a7dea167SDimitry Andric 
125a7dea167SDimitry Andric   void dumpToStream(llvm::raw_ostream &OS) const;
126a7dea167SDimitry Andric 
dump()127a7dea167SDimitry Andric   void dump() const {
128a7dea167SDimitry Andric     dumpToStream(llvm::errs());
129a7dea167SDimitry Andric   }
1300b57cec5SDimitry Andric };
1310b57cec5SDimitry Andric 
1320b57cec5SDimitry Andric class CFGStmt : public CFGElement {
1330b57cec5SDimitry Andric public:
CFGElement(K,S)134bdd1243dSDimitry Andric   explicit CFGStmt(const Stmt *S, Kind K = Statement) : CFGElement(K, S) {
1350b57cec5SDimitry Andric     assert(isKind(*this));
1360b57cec5SDimitry Andric   }
1370b57cec5SDimitry Andric 
getStmt()1380b57cec5SDimitry Andric   const Stmt *getStmt() const {
1390b57cec5SDimitry Andric     return static_cast<const Stmt *>(Data1.getPointer());
1400b57cec5SDimitry Andric   }
1410b57cec5SDimitry Andric 
1420b57cec5SDimitry Andric private:
1430b57cec5SDimitry Andric   friend class CFGElement;
1440b57cec5SDimitry Andric 
isKind(const CFGElement & E)1450b57cec5SDimitry Andric   static bool isKind(const CFGElement &E) {
1460b57cec5SDimitry Andric     return E.getKind() >= STMT_BEGIN && E.getKind() <= STMT_END;
1470b57cec5SDimitry Andric   }
1480b57cec5SDimitry Andric 
1490b57cec5SDimitry Andric protected:
1500b57cec5SDimitry Andric   CFGStmt() = default;
1510b57cec5SDimitry Andric };
1520b57cec5SDimitry Andric 
1530b57cec5SDimitry Andric /// Represents C++ constructor call. Maintains information necessary to figure
1540b57cec5SDimitry Andric /// out what memory is being initialized by the constructor expression. For now
1550b57cec5SDimitry Andric /// this is only used by the analyzer's CFG.
1560b57cec5SDimitry Andric class CFGConstructor : public CFGStmt {
1570b57cec5SDimitry Andric public:
CFGConstructor(const CXXConstructExpr * CE,const ConstructionContext * C)158bdd1243dSDimitry Andric   explicit CFGConstructor(const CXXConstructExpr *CE,
159bdd1243dSDimitry Andric                           const ConstructionContext *C)
1600b57cec5SDimitry Andric       : CFGStmt(CE, Constructor) {
1610b57cec5SDimitry Andric     assert(C);
1620b57cec5SDimitry Andric     Data2.setPointer(const_cast<ConstructionContext *>(C));
1630b57cec5SDimitry Andric   }
1640b57cec5SDimitry Andric 
getConstructionContext()1650b57cec5SDimitry Andric   const ConstructionContext *getConstructionContext() const {
1660b57cec5SDimitry Andric     return static_cast<ConstructionContext *>(Data2.getPointer());
1670b57cec5SDimitry Andric   }
1680b57cec5SDimitry Andric 
1690b57cec5SDimitry Andric private:
1700b57cec5SDimitry Andric   friend class CFGElement;
1710b57cec5SDimitry Andric 
1720b57cec5SDimitry Andric   CFGConstructor() = default;
1730b57cec5SDimitry Andric 
isKind(const CFGElement & E)1740b57cec5SDimitry Andric   static bool isKind(const CFGElement &E) {
1750b57cec5SDimitry Andric     return E.getKind() == Constructor;
1760b57cec5SDimitry Andric   }
1770b57cec5SDimitry Andric };
1780b57cec5SDimitry Andric 
1790b57cec5SDimitry Andric /// Represents a function call that returns a C++ object by value. This, like
1800b57cec5SDimitry Andric /// constructor, requires a construction context in order to understand the
1810b57cec5SDimitry Andric /// storage of the returned object . In C such tracking is not necessary because
1820b57cec5SDimitry Andric /// no additional effort is required for destroying the object or modeling copy
1830b57cec5SDimitry Andric /// elision. Like CFGConstructor, this element is for now only used by the
1840b57cec5SDimitry Andric /// analyzer's CFG.
1850b57cec5SDimitry Andric class CFGCXXRecordTypedCall : public CFGStmt {
1860b57cec5SDimitry Andric public:
1870b57cec5SDimitry Andric   /// Returns true when call expression \p CE needs to be represented
1880b57cec5SDimitry Andric   /// by CFGCXXRecordTypedCall, as opposed to a regular CFGStmt.
isCXXRecordTypedCall(const Expr * E)189bdd1243dSDimitry Andric   static bool isCXXRecordTypedCall(const Expr *E) {
1900b57cec5SDimitry Andric     assert(isa<CallExpr>(E) || isa<ObjCMessageExpr>(E));
1910b57cec5SDimitry Andric     // There is no such thing as reference-type expression. If the function
1920b57cec5SDimitry Andric     // returns a reference, it'll return the respective lvalue or xvalue
1930b57cec5SDimitry Andric     // instead, and we're only interested in objects.
1940b57cec5SDimitry Andric     return !E->isGLValue() &&
1950b57cec5SDimitry Andric            E->getType().getCanonicalType()->getAsCXXRecordDecl();
1960b57cec5SDimitry Andric   }
1970b57cec5SDimitry Andric 
CFGCXXRecordTypedCall(const Expr * E,const ConstructionContext * C)198bdd1243dSDimitry Andric   explicit CFGCXXRecordTypedCall(const Expr *E, const ConstructionContext *C)
1990b57cec5SDimitry Andric       : CFGStmt(E, CXXRecordTypedCall) {
2000b57cec5SDimitry Andric     assert(isCXXRecordTypedCall(E));
2010b57cec5SDimitry Andric     assert(C && (isa<TemporaryObjectConstructionContext>(C) ||
2020b57cec5SDimitry Andric                  // These are possible in C++17 due to mandatory copy elision.
2030b57cec5SDimitry Andric                  isa<ReturnedValueConstructionContext>(C) ||
2040b57cec5SDimitry Andric                  isa<VariableConstructionContext>(C) ||
2050b57cec5SDimitry Andric                  isa<ConstructorInitializerConstructionContext>(C) ||
206972a253aSDimitry Andric                  isa<ArgumentConstructionContext>(C) ||
207972a253aSDimitry Andric                  isa<LambdaCaptureConstructionContext>(C)));
2080b57cec5SDimitry Andric     Data2.setPointer(const_cast<ConstructionContext *>(C));
2090b57cec5SDimitry Andric   }
2100b57cec5SDimitry Andric 
getConstructionContext()2110b57cec5SDimitry Andric   const ConstructionContext *getConstructionContext() const {
2120b57cec5SDimitry Andric     return static_cast<ConstructionContext *>(Data2.getPointer());
2130b57cec5SDimitry Andric   }
2140b57cec5SDimitry Andric 
2150b57cec5SDimitry Andric private:
2160b57cec5SDimitry Andric   friend class CFGElement;
2170b57cec5SDimitry Andric 
2180b57cec5SDimitry Andric   CFGCXXRecordTypedCall() = default;
2190b57cec5SDimitry Andric 
isKind(const CFGElement & E)2200b57cec5SDimitry Andric   static bool isKind(const CFGElement &E) {
2210b57cec5SDimitry Andric     return E.getKind() == CXXRecordTypedCall;
2220b57cec5SDimitry Andric   }
2230b57cec5SDimitry Andric };
2240b57cec5SDimitry Andric 
2250b57cec5SDimitry Andric /// Represents C++ base or member initializer from constructor's initialization
2260b57cec5SDimitry Andric /// list.
2270b57cec5SDimitry Andric class CFGInitializer : public CFGElement {
2280b57cec5SDimitry Andric public:
CFGInitializer(const CXXCtorInitializer * initializer)229bdd1243dSDimitry Andric   explicit CFGInitializer(const CXXCtorInitializer *initializer)
2300b57cec5SDimitry Andric       : CFGElement(Initializer, initializer) {}
2310b57cec5SDimitry Andric 
getInitializer()2320b57cec5SDimitry Andric   CXXCtorInitializer* getInitializer() const {
2330b57cec5SDimitry Andric     return static_cast<CXXCtorInitializer*>(Data1.getPointer());
2340b57cec5SDimitry Andric   }
2350b57cec5SDimitry Andric 
2360b57cec5SDimitry Andric private:
2370b57cec5SDimitry Andric   friend class CFGElement;
2380b57cec5SDimitry Andric 
2390b57cec5SDimitry Andric   CFGInitializer() = default;
2400b57cec5SDimitry Andric 
isKind(const CFGElement & E)2410b57cec5SDimitry Andric   static bool isKind(const CFGElement &E) {
2420b57cec5SDimitry Andric     return E.getKind() == Initializer;
2430b57cec5SDimitry Andric   }
2440b57cec5SDimitry Andric };
2450b57cec5SDimitry Andric 
2460b57cec5SDimitry Andric /// Represents C++ allocator call.
2470b57cec5SDimitry Andric class CFGNewAllocator : public CFGElement {
2480b57cec5SDimitry Andric public:
CFGNewAllocator(const CXXNewExpr * S)2490b57cec5SDimitry Andric   explicit CFGNewAllocator(const CXXNewExpr *S)
2500b57cec5SDimitry Andric     : CFGElement(NewAllocator, S) {}
2510b57cec5SDimitry Andric 
2520b57cec5SDimitry Andric   // Get the new expression.
getAllocatorExpr()2530b57cec5SDimitry Andric   const CXXNewExpr *getAllocatorExpr() const {
2540b57cec5SDimitry Andric     return static_cast<CXXNewExpr *>(Data1.getPointer());
2550b57cec5SDimitry Andric   }
2560b57cec5SDimitry Andric 
2570b57cec5SDimitry Andric private:
2580b57cec5SDimitry Andric   friend class CFGElement;
2590b57cec5SDimitry Andric 
2600b57cec5SDimitry Andric   CFGNewAllocator() = default;
2610b57cec5SDimitry Andric 
isKind(const CFGElement & elem)2620b57cec5SDimitry Andric   static bool isKind(const CFGElement &elem) {
2630b57cec5SDimitry Andric     return elem.getKind() == NewAllocator;
2640b57cec5SDimitry Andric   }
2650b57cec5SDimitry Andric };
2660b57cec5SDimitry Andric 
2670b57cec5SDimitry Andric /// Represents the point where a loop ends.
268bdd1243dSDimitry Andric /// This element is only produced when building the CFG for the static
2690b57cec5SDimitry Andric /// analyzer and hidden behind the 'cfg-loopexit' analyzer config flag.
2700b57cec5SDimitry Andric ///
2710b57cec5SDimitry Andric /// Note: a loop exit element can be reached even when the loop body was never
2720b57cec5SDimitry Andric /// entered.
2730b57cec5SDimitry Andric class CFGLoopExit : public CFGElement {
2740b57cec5SDimitry Andric public:
CFGLoopExit(const Stmt * stmt)2750b57cec5SDimitry Andric   explicit CFGLoopExit(const Stmt *stmt) : CFGElement(LoopExit, stmt) {}
2760b57cec5SDimitry Andric 
getLoopStmt()2770b57cec5SDimitry Andric   const Stmt *getLoopStmt() const {
2780b57cec5SDimitry Andric     return static_cast<Stmt *>(Data1.getPointer());
2790b57cec5SDimitry Andric   }
2800b57cec5SDimitry Andric 
2810b57cec5SDimitry Andric private:
2820b57cec5SDimitry Andric   friend class CFGElement;
2830b57cec5SDimitry Andric 
2840b57cec5SDimitry Andric   CFGLoopExit() = default;
2850b57cec5SDimitry Andric 
isKind(const CFGElement & elem)2860b57cec5SDimitry Andric   static bool isKind(const CFGElement &elem) {
2870b57cec5SDimitry Andric     return elem.getKind() == LoopExit;
2880b57cec5SDimitry Andric   }
2890b57cec5SDimitry Andric };
2900b57cec5SDimitry Andric 
2910b57cec5SDimitry Andric /// Represents the point where the lifetime of an automatic object ends
2920b57cec5SDimitry Andric class CFGLifetimeEnds : public CFGElement {
2930b57cec5SDimitry Andric public:
CFGLifetimeEnds(const VarDecl * var,const Stmt * stmt)2940b57cec5SDimitry Andric   explicit CFGLifetimeEnds(const VarDecl *var, const Stmt *stmt)
2950b57cec5SDimitry Andric       : CFGElement(LifetimeEnds, var, stmt) {}
2960b57cec5SDimitry Andric 
getVarDecl()2970b57cec5SDimitry Andric   const VarDecl *getVarDecl() const {
2980b57cec5SDimitry Andric     return static_cast<VarDecl *>(Data1.getPointer());
2990b57cec5SDimitry Andric   }
3000b57cec5SDimitry Andric 
getTriggerStmt()3010b57cec5SDimitry Andric   const Stmt *getTriggerStmt() const {
3020b57cec5SDimitry Andric     return static_cast<Stmt *>(Data2.getPointer());
3030b57cec5SDimitry Andric   }
3040b57cec5SDimitry Andric 
3050b57cec5SDimitry Andric private:
3060b57cec5SDimitry Andric   friend class CFGElement;
3070b57cec5SDimitry Andric 
3080b57cec5SDimitry Andric   CFGLifetimeEnds() = default;
3090b57cec5SDimitry Andric 
isKind(const CFGElement & elem)3100b57cec5SDimitry Andric   static bool isKind(const CFGElement &elem) {
3110b57cec5SDimitry Andric     return elem.getKind() == LifetimeEnds;
3120b57cec5SDimitry Andric   }
3130b57cec5SDimitry Andric };
3140b57cec5SDimitry Andric 
3150b57cec5SDimitry Andric /// Represents beginning of a scope implicitly generated
3160b57cec5SDimitry Andric /// by the compiler on encountering a CompoundStmt
3170b57cec5SDimitry Andric class CFGScopeBegin : public CFGElement {
3180b57cec5SDimitry Andric public:
CFGScopeBegin()3190b57cec5SDimitry Andric   CFGScopeBegin() {}
CFGScopeBegin(const VarDecl * VD,const Stmt * S)3200b57cec5SDimitry Andric   CFGScopeBegin(const VarDecl *VD, const Stmt *S)
3210b57cec5SDimitry Andric       : CFGElement(ScopeBegin, VD, S) {}
3220b57cec5SDimitry Andric 
3230b57cec5SDimitry Andric   // Get statement that triggered a new scope.
getTriggerStmt()3240b57cec5SDimitry Andric   const Stmt *getTriggerStmt() const {
3250b57cec5SDimitry Andric     return static_cast<Stmt*>(Data2.getPointer());
3260b57cec5SDimitry Andric   }
3270b57cec5SDimitry Andric 
3280b57cec5SDimitry Andric   // Get VD that triggered a new scope.
getVarDecl()3290b57cec5SDimitry Andric   const VarDecl *getVarDecl() const {
3300b57cec5SDimitry Andric     return static_cast<VarDecl *>(Data1.getPointer());
3310b57cec5SDimitry Andric   }
3320b57cec5SDimitry Andric 
3330b57cec5SDimitry Andric private:
3340b57cec5SDimitry Andric   friend class CFGElement;
isKind(const CFGElement & E)3350b57cec5SDimitry Andric   static bool isKind(const CFGElement &E) {
3360b57cec5SDimitry Andric     Kind kind = E.getKind();
3370b57cec5SDimitry Andric     return kind == ScopeBegin;
3380b57cec5SDimitry Andric   }
3390b57cec5SDimitry Andric };
3400b57cec5SDimitry Andric 
3410b57cec5SDimitry Andric /// Represents end of a scope implicitly generated by
3420b57cec5SDimitry Andric /// the compiler after the last Stmt in a CompoundStmt's body
3430b57cec5SDimitry Andric class CFGScopeEnd : public CFGElement {
3440b57cec5SDimitry Andric public:
CFGScopeEnd()3450b57cec5SDimitry Andric   CFGScopeEnd() {}
CFGScopeEnd(const VarDecl * VD,const Stmt * S)3460b57cec5SDimitry Andric   CFGScopeEnd(const VarDecl *VD, const Stmt *S) : CFGElement(ScopeEnd, VD, S) {}
3470b57cec5SDimitry Andric 
getVarDecl()3480b57cec5SDimitry Andric   const VarDecl *getVarDecl() const {
3490b57cec5SDimitry Andric     return static_cast<VarDecl *>(Data1.getPointer());
3500b57cec5SDimitry Andric   }
3510b57cec5SDimitry Andric 
getTriggerStmt()3520b57cec5SDimitry Andric   const Stmt *getTriggerStmt() const {
3530b57cec5SDimitry Andric     return static_cast<Stmt *>(Data2.getPointer());
3540b57cec5SDimitry Andric   }
3550b57cec5SDimitry Andric 
3560b57cec5SDimitry Andric private:
3570b57cec5SDimitry Andric   friend class CFGElement;
isKind(const CFGElement & E)3580b57cec5SDimitry Andric   static bool isKind(const CFGElement &E) {
3590b57cec5SDimitry Andric     Kind kind = E.getKind();
3600b57cec5SDimitry Andric     return kind == ScopeEnd;
3610b57cec5SDimitry Andric   }
3620b57cec5SDimitry Andric };
3630b57cec5SDimitry Andric 
3640b57cec5SDimitry Andric /// Represents C++ object destructor implicitly generated by compiler on various
3650b57cec5SDimitry Andric /// occasions.
3660b57cec5SDimitry Andric class CFGImplicitDtor : public CFGElement {
3670b57cec5SDimitry Andric protected:
3680b57cec5SDimitry Andric   CFGImplicitDtor() = default;
3690b57cec5SDimitry Andric 
3700b57cec5SDimitry Andric   CFGImplicitDtor(Kind kind, const void *data1, const void *data2 = nullptr)
CFGElement(kind,data1,data2)3710b57cec5SDimitry Andric     : CFGElement(kind, data1, data2) {
3720b57cec5SDimitry Andric     assert(kind >= DTOR_BEGIN && kind <= DTOR_END);
3730b57cec5SDimitry Andric   }
3740b57cec5SDimitry Andric 
3750b57cec5SDimitry Andric public:
3760b57cec5SDimitry Andric   const CXXDestructorDecl *getDestructorDecl(ASTContext &astContext) const;
3770b57cec5SDimitry Andric   bool isNoReturn(ASTContext &astContext) const;
3780b57cec5SDimitry Andric 
3790b57cec5SDimitry Andric private:
3800b57cec5SDimitry Andric   friend class CFGElement;
3810b57cec5SDimitry Andric 
isKind(const CFGElement & E)3820b57cec5SDimitry Andric   static bool isKind(const CFGElement &E) {
3830b57cec5SDimitry Andric     Kind kind = E.getKind();
3840b57cec5SDimitry Andric     return kind >= DTOR_BEGIN && kind <= DTOR_END;
3850b57cec5SDimitry Andric   }
3860b57cec5SDimitry Andric };
3870b57cec5SDimitry Andric 
3885f757f3fSDimitry Andric class CFGCleanupFunction final : public CFGElement {
3895f757f3fSDimitry Andric public:
3905f757f3fSDimitry Andric   CFGCleanupFunction() = default;
CFGCleanupFunction(const VarDecl * VD)3915f757f3fSDimitry Andric   CFGCleanupFunction(const VarDecl *VD)
3925f757f3fSDimitry Andric       : CFGElement(Kind::CleanupFunction, VD) {
3935f757f3fSDimitry Andric     assert(VD->hasAttr<CleanupAttr>());
3945f757f3fSDimitry Andric   }
3955f757f3fSDimitry Andric 
getVarDecl()3965f757f3fSDimitry Andric   const VarDecl *getVarDecl() const {
3975f757f3fSDimitry Andric     return static_cast<VarDecl *>(Data1.getPointer());
3985f757f3fSDimitry Andric   }
3995f757f3fSDimitry Andric 
4005f757f3fSDimitry Andric   /// Returns the function to be called when cleaning up the var decl.
getFunctionDecl()4015f757f3fSDimitry Andric   const FunctionDecl *getFunctionDecl() const {
4025f757f3fSDimitry Andric     const CleanupAttr *A = getVarDecl()->getAttr<CleanupAttr>();
4035f757f3fSDimitry Andric     return A->getFunctionDecl();
4045f757f3fSDimitry Andric   }
4055f757f3fSDimitry Andric 
4065f757f3fSDimitry Andric private:
4075f757f3fSDimitry Andric   friend class CFGElement;
4085f757f3fSDimitry Andric 
isKind(const CFGElement E)4095f757f3fSDimitry Andric   static bool isKind(const CFGElement E) {
4105f757f3fSDimitry Andric     return E.getKind() == Kind::CleanupFunction;
4115f757f3fSDimitry Andric   }
4125f757f3fSDimitry Andric };
4135f757f3fSDimitry Andric 
4140b57cec5SDimitry Andric /// Represents C++ object destructor implicitly generated for automatic object
4150b57cec5SDimitry Andric /// or temporary bound to const reference at the point of leaving its local
4160b57cec5SDimitry Andric /// scope.
4170b57cec5SDimitry Andric class CFGAutomaticObjDtor: public CFGImplicitDtor {
4180b57cec5SDimitry Andric public:
CFGAutomaticObjDtor(const VarDecl * var,const Stmt * stmt)4190b57cec5SDimitry Andric   CFGAutomaticObjDtor(const VarDecl *var, const Stmt *stmt)
4200b57cec5SDimitry Andric       : CFGImplicitDtor(AutomaticObjectDtor, var, stmt) {}
4210b57cec5SDimitry Andric 
getVarDecl()4220b57cec5SDimitry Andric   const VarDecl *getVarDecl() const {
4230b57cec5SDimitry Andric     return static_cast<VarDecl*>(Data1.getPointer());
4240b57cec5SDimitry Andric   }
4250b57cec5SDimitry Andric 
4260b57cec5SDimitry Andric   // Get statement end of which triggered the destructor call.
getTriggerStmt()4270b57cec5SDimitry Andric   const Stmt *getTriggerStmt() const {
4280b57cec5SDimitry Andric     return static_cast<Stmt*>(Data2.getPointer());
4290b57cec5SDimitry Andric   }
4300b57cec5SDimitry Andric 
4310b57cec5SDimitry Andric private:
4320b57cec5SDimitry Andric   friend class CFGElement;
4330b57cec5SDimitry Andric 
4340b57cec5SDimitry Andric   CFGAutomaticObjDtor() = default;
4350b57cec5SDimitry Andric 
isKind(const CFGElement & elem)4360b57cec5SDimitry Andric   static bool isKind(const CFGElement &elem) {
4370b57cec5SDimitry Andric     return elem.getKind() == AutomaticObjectDtor;
4380b57cec5SDimitry Andric   }
4390b57cec5SDimitry Andric };
4400b57cec5SDimitry Andric 
4410b57cec5SDimitry Andric /// Represents C++ object destructor generated from a call to delete.
4420b57cec5SDimitry Andric class CFGDeleteDtor : public CFGImplicitDtor {
4430b57cec5SDimitry Andric public:
CFGDeleteDtor(const CXXRecordDecl * RD,const CXXDeleteExpr * DE)4440b57cec5SDimitry Andric   CFGDeleteDtor(const CXXRecordDecl *RD, const CXXDeleteExpr *DE)
4450b57cec5SDimitry Andric       : CFGImplicitDtor(DeleteDtor, RD, DE) {}
4460b57cec5SDimitry Andric 
getCXXRecordDecl()4470b57cec5SDimitry Andric   const CXXRecordDecl *getCXXRecordDecl() const {
4480b57cec5SDimitry Andric     return static_cast<CXXRecordDecl*>(Data1.getPointer());
4490b57cec5SDimitry Andric   }
4500b57cec5SDimitry Andric 
4510b57cec5SDimitry Andric   // Get Delete expression which triggered the destructor call.
getDeleteExpr()4520b57cec5SDimitry Andric   const CXXDeleteExpr *getDeleteExpr() const {
4530b57cec5SDimitry Andric     return static_cast<CXXDeleteExpr *>(Data2.getPointer());
4540b57cec5SDimitry Andric   }
4550b57cec5SDimitry Andric 
4560b57cec5SDimitry Andric private:
4570b57cec5SDimitry Andric   friend class CFGElement;
4580b57cec5SDimitry Andric 
4590b57cec5SDimitry Andric   CFGDeleteDtor() = default;
4600b57cec5SDimitry Andric 
isKind(const CFGElement & elem)4610b57cec5SDimitry Andric   static bool isKind(const CFGElement &elem) {
4620b57cec5SDimitry Andric     return elem.getKind() == DeleteDtor;
4630b57cec5SDimitry Andric   }
4640b57cec5SDimitry Andric };
4650b57cec5SDimitry Andric 
4660b57cec5SDimitry Andric /// Represents C++ object destructor implicitly generated for base object in
4670b57cec5SDimitry Andric /// destructor.
4680b57cec5SDimitry Andric class CFGBaseDtor : public CFGImplicitDtor {
4690b57cec5SDimitry Andric public:
CFGBaseDtor(const CXXBaseSpecifier * base)4700b57cec5SDimitry Andric   CFGBaseDtor(const CXXBaseSpecifier *base)
4710b57cec5SDimitry Andric       : CFGImplicitDtor(BaseDtor, base) {}
4720b57cec5SDimitry Andric 
getBaseSpecifier()4730b57cec5SDimitry Andric   const CXXBaseSpecifier *getBaseSpecifier() const {
4740b57cec5SDimitry Andric     return static_cast<const CXXBaseSpecifier*>(Data1.getPointer());
4750b57cec5SDimitry Andric   }
4760b57cec5SDimitry Andric 
4770b57cec5SDimitry Andric private:
4780b57cec5SDimitry Andric   friend class CFGElement;
4790b57cec5SDimitry Andric 
4800b57cec5SDimitry Andric   CFGBaseDtor() = default;
4810b57cec5SDimitry Andric 
isKind(const CFGElement & E)4820b57cec5SDimitry Andric   static bool isKind(const CFGElement &E) {
4830b57cec5SDimitry Andric     return E.getKind() == BaseDtor;
4840b57cec5SDimitry Andric   }
4850b57cec5SDimitry Andric };
4860b57cec5SDimitry Andric 
4870b57cec5SDimitry Andric /// Represents C++ object destructor implicitly generated for member object in
4880b57cec5SDimitry Andric /// destructor.
4890b57cec5SDimitry Andric class CFGMemberDtor : public CFGImplicitDtor {
4900b57cec5SDimitry Andric public:
CFGMemberDtor(const FieldDecl * field)4910b57cec5SDimitry Andric   CFGMemberDtor(const FieldDecl *field)
4920b57cec5SDimitry Andric       : CFGImplicitDtor(MemberDtor, field, nullptr) {}
4930b57cec5SDimitry Andric 
getFieldDecl()4940b57cec5SDimitry Andric   const FieldDecl *getFieldDecl() const {
4950b57cec5SDimitry Andric     return static_cast<const FieldDecl*>(Data1.getPointer());
4960b57cec5SDimitry Andric   }
4970b57cec5SDimitry Andric 
4980b57cec5SDimitry Andric private:
4990b57cec5SDimitry Andric   friend class CFGElement;
5000b57cec5SDimitry Andric 
5010b57cec5SDimitry Andric   CFGMemberDtor() = default;
5020b57cec5SDimitry Andric 
isKind(const CFGElement & E)5030b57cec5SDimitry Andric   static bool isKind(const CFGElement &E) {
5040b57cec5SDimitry Andric     return E.getKind() == MemberDtor;
5050b57cec5SDimitry Andric   }
5060b57cec5SDimitry Andric };
5070b57cec5SDimitry Andric 
5080b57cec5SDimitry Andric /// Represents C++ object destructor implicitly generated at the end of full
5090b57cec5SDimitry Andric /// expression for temporary object.
5100b57cec5SDimitry Andric class CFGTemporaryDtor : public CFGImplicitDtor {
5110b57cec5SDimitry Andric public:
CFGTemporaryDtor(const CXXBindTemporaryExpr * expr)512bdd1243dSDimitry Andric   CFGTemporaryDtor(const CXXBindTemporaryExpr *expr)
5130b57cec5SDimitry Andric       : CFGImplicitDtor(TemporaryDtor, expr, nullptr) {}
5140b57cec5SDimitry Andric 
getBindTemporaryExpr()5150b57cec5SDimitry Andric   const CXXBindTemporaryExpr *getBindTemporaryExpr() const {
5160b57cec5SDimitry Andric     return static_cast<const CXXBindTemporaryExpr *>(Data1.getPointer());
5170b57cec5SDimitry Andric   }
5180b57cec5SDimitry Andric 
5190b57cec5SDimitry Andric private:
5200b57cec5SDimitry Andric   friend class CFGElement;
5210b57cec5SDimitry Andric 
5220b57cec5SDimitry Andric   CFGTemporaryDtor() = default;
5230b57cec5SDimitry Andric 
isKind(const CFGElement & E)5240b57cec5SDimitry Andric   static bool isKind(const CFGElement &E) {
5250b57cec5SDimitry Andric     return E.getKind() == TemporaryDtor;
5260b57cec5SDimitry Andric   }
5270b57cec5SDimitry Andric };
5280b57cec5SDimitry Andric 
5290b57cec5SDimitry Andric /// Represents CFGBlock terminator statement.
5300b57cec5SDimitry Andric ///
5310b57cec5SDimitry Andric class CFGTerminator {
5320b57cec5SDimitry Andric public:
5330b57cec5SDimitry Andric   enum Kind {
5340b57cec5SDimitry Andric     /// A branch that corresponds to a statement in the code,
5350b57cec5SDimitry Andric     /// such as an if-statement.
5360b57cec5SDimitry Andric     StmtBranch,
5370b57cec5SDimitry Andric     /// A branch in control flow of destructors of temporaries. In this case
5380b57cec5SDimitry Andric     /// terminator statement is the same statement that branches control flow
5390b57cec5SDimitry Andric     /// in evaluation of matching full expression.
5400b57cec5SDimitry Andric     TemporaryDtorsBranch,
5410b57cec5SDimitry Andric     /// A shortcut around virtual base initializers. It gets taken when
5420b57cec5SDimitry Andric     /// virtual base classes have already been initialized by the constructor
5430b57cec5SDimitry Andric     /// of the most derived class while we're in the base class.
5440b57cec5SDimitry Andric     VirtualBaseBranch,
5450b57cec5SDimitry Andric 
5464824e7fdSDimitry Andric     /// Number of different kinds, for assertions. We subtract 1 so that
5470b57cec5SDimitry Andric     /// to keep receiving compiler warnings when we don't cover all enum values
5480b57cec5SDimitry Andric     /// in a switch.
5490b57cec5SDimitry Andric     NumKindsMinusOne = VirtualBaseBranch
5500b57cec5SDimitry Andric   };
5510b57cec5SDimitry Andric 
5520b57cec5SDimitry Andric private:
5530b57cec5SDimitry Andric   static constexpr int KindBits = 2;
5540b57cec5SDimitry Andric   static_assert((1 << KindBits) > NumKindsMinusOne,
5550b57cec5SDimitry Andric                 "Not enough room for kind!");
5560b57cec5SDimitry Andric   llvm::PointerIntPair<Stmt *, KindBits> Data;
5570b57cec5SDimitry Andric 
5580b57cec5SDimitry Andric public:
CFGTerminator()5590b57cec5SDimitry Andric   CFGTerminator() { assert(!isValid()); }
Data(S,K)5600b57cec5SDimitry Andric   CFGTerminator(Stmt *S, Kind K = StmtBranch) : Data(S, K) {}
5610b57cec5SDimitry Andric 
isValid()5620b57cec5SDimitry Andric   bool isValid() const { return Data.getOpaqueValue() != nullptr; }
getStmt()5630b57cec5SDimitry Andric   Stmt *getStmt() { return Data.getPointer(); }
getStmt()5640b57cec5SDimitry Andric   const Stmt *getStmt() const { return Data.getPointer(); }
getKind()5650b57cec5SDimitry Andric   Kind getKind() const { return static_cast<Kind>(Data.getInt()); }
5660b57cec5SDimitry Andric 
isStmtBranch()5670b57cec5SDimitry Andric   bool isStmtBranch() const {
5680b57cec5SDimitry Andric     return getKind() == StmtBranch;
5690b57cec5SDimitry Andric   }
isTemporaryDtorsBranch()5700b57cec5SDimitry Andric   bool isTemporaryDtorsBranch() const {
5710b57cec5SDimitry Andric     return getKind() == TemporaryDtorsBranch;
5720b57cec5SDimitry Andric   }
isVirtualBaseBranch()5730b57cec5SDimitry Andric   bool isVirtualBaseBranch() const {
5740b57cec5SDimitry Andric     return getKind() == VirtualBaseBranch;
5750b57cec5SDimitry Andric   }
5760b57cec5SDimitry Andric };
5770b57cec5SDimitry Andric 
5780b57cec5SDimitry Andric /// Represents a single basic block in a source-level CFG.
5790b57cec5SDimitry Andric ///  It consists of:
5800b57cec5SDimitry Andric ///
5810b57cec5SDimitry Andric ///  (1) A set of statements/expressions (which may contain subexpressions).
5820b57cec5SDimitry Andric ///  (2) A "terminator" statement (not in the set of statements).
5830b57cec5SDimitry Andric ///  (3) A list of successors and predecessors.
5840b57cec5SDimitry Andric ///
5850b57cec5SDimitry Andric /// Terminator: The terminator represents the type of control-flow that occurs
5860b57cec5SDimitry Andric /// at the end of the basic block.  The terminator is a Stmt* referring to an
5870b57cec5SDimitry Andric /// AST node that has control-flow: if-statements, breaks, loops, etc.
5880b57cec5SDimitry Andric /// If the control-flow is conditional, the condition expression will appear
5890b57cec5SDimitry Andric /// within the set of statements in the block (usually the last statement).
5900b57cec5SDimitry Andric ///
5910b57cec5SDimitry Andric /// Predecessors: the order in the set of predecessors is arbitrary.
5920b57cec5SDimitry Andric ///
5930b57cec5SDimitry Andric /// Successors: the order in the set of successors is NOT arbitrary.  We
5940b57cec5SDimitry Andric ///  currently have the following orderings based on the terminator:
5950b57cec5SDimitry Andric ///
5960b57cec5SDimitry Andric ///     Terminator     |   Successor Ordering
5970b57cec5SDimitry Andric ///  ------------------|------------------------------------
5980b57cec5SDimitry Andric ///       if           |  Then Block;  Else Block
5990b57cec5SDimitry Andric ///     ? operator     |  LHS expression;  RHS expression
6000b57cec5SDimitry Andric ///     logical and/or |  expression that consumes the op, RHS
6010b57cec5SDimitry Andric ///     vbase inits    |  already handled by the most derived class; not yet
6020b57cec5SDimitry Andric ///
6030b57cec5SDimitry Andric /// But note that any of that may be NULL in case of optimized-out edges.
6040b57cec5SDimitry Andric class CFGBlock {
6050b57cec5SDimitry Andric   class ElementList {
6060b57cec5SDimitry Andric     using ImplTy = BumpVector<CFGElement>;
6070b57cec5SDimitry Andric 
6080b57cec5SDimitry Andric     ImplTy Impl;
6090b57cec5SDimitry Andric 
6100b57cec5SDimitry Andric   public:
ElementList(BumpVectorContext & C)6110b57cec5SDimitry Andric     ElementList(BumpVectorContext &C) : Impl(C, 4) {}
6120b57cec5SDimitry Andric 
6130b57cec5SDimitry Andric     using iterator = std::reverse_iterator<ImplTy::iterator>;
6140b57cec5SDimitry Andric     using const_iterator = std::reverse_iterator<ImplTy::const_iterator>;
6150b57cec5SDimitry Andric     using reverse_iterator = ImplTy::iterator;
6160b57cec5SDimitry Andric     using const_reverse_iterator = ImplTy::const_iterator;
6170b57cec5SDimitry Andric     using const_reference = ImplTy::const_reference;
6180b57cec5SDimitry Andric 
push_back(CFGElement e,BumpVectorContext & C)6190b57cec5SDimitry Andric     void push_back(CFGElement e, BumpVectorContext &C) { Impl.push_back(e, C); }
6200b57cec5SDimitry Andric 
insert(reverse_iterator I,size_t Cnt,CFGElement E,BumpVectorContext & C)6210b57cec5SDimitry Andric     reverse_iterator insert(reverse_iterator I, size_t Cnt, CFGElement E,
6220b57cec5SDimitry Andric         BumpVectorContext &C) {
6230b57cec5SDimitry Andric       return Impl.insert(I, Cnt, E, C);
6240b57cec5SDimitry Andric     }
6250b57cec5SDimitry Andric 
front()6260b57cec5SDimitry Andric     const_reference front() const { return Impl.back(); }
back()6270b57cec5SDimitry Andric     const_reference back() const { return Impl.front(); }
6280b57cec5SDimitry Andric 
begin()6290b57cec5SDimitry Andric     iterator begin() { return Impl.rbegin(); }
end()6300b57cec5SDimitry Andric     iterator end() { return Impl.rend(); }
begin()6310b57cec5SDimitry Andric     const_iterator begin() const { return Impl.rbegin(); }
end()6320b57cec5SDimitry Andric     const_iterator end() const { return Impl.rend(); }
rbegin()6330b57cec5SDimitry Andric     reverse_iterator rbegin() { return Impl.begin(); }
rend()6340b57cec5SDimitry Andric     reverse_iterator rend() { return Impl.end(); }
rbegin()6350b57cec5SDimitry Andric     const_reverse_iterator rbegin() const { return Impl.begin(); }
rend()6360b57cec5SDimitry Andric     const_reverse_iterator rend() const { return Impl.end(); }
6370b57cec5SDimitry Andric 
6380b57cec5SDimitry Andric     CFGElement operator[](size_t i) const  {
6390b57cec5SDimitry Andric       assert(i < Impl.size());
6400b57cec5SDimitry Andric       return Impl[Impl.size() - 1 - i];
6410b57cec5SDimitry Andric     }
6420b57cec5SDimitry Andric 
size()6430b57cec5SDimitry Andric     size_t size() const { return Impl.size(); }
empty()6440b57cec5SDimitry Andric     bool empty() const { return Impl.empty(); }
6450b57cec5SDimitry Andric   };
6460b57cec5SDimitry Andric 
647a7dea167SDimitry Andric   /// A convenience class for comparing CFGElements, since methods of CFGBlock
648a7dea167SDimitry Andric   /// like operator[] return CFGElements by value. This is practically a wrapper
649a7dea167SDimitry Andric   /// around a (CFGBlock, Index) pair.
650a7dea167SDimitry Andric   template <bool IsConst> class ElementRefImpl {
651a7dea167SDimitry Andric 
652a7dea167SDimitry Andric     template <bool IsOtherConst> friend class ElementRefImpl;
653a7dea167SDimitry Andric 
654a7dea167SDimitry Andric     using CFGBlockPtr =
6555ffd83dbSDimitry Andric         std::conditional_t<IsConst, const CFGBlock *, CFGBlock *>;
656a7dea167SDimitry Andric 
6575ffd83dbSDimitry Andric     using CFGElementPtr =
6585ffd83dbSDimitry Andric         std::conditional_t<IsConst, const CFGElement *, CFGElement *>;
659a7dea167SDimitry Andric 
660a7dea167SDimitry Andric   protected:
661a7dea167SDimitry Andric     CFGBlockPtr Parent;
662a7dea167SDimitry Andric     size_t Index;
663a7dea167SDimitry Andric 
664a7dea167SDimitry Andric   public:
ElementRefImpl(CFGBlockPtr Parent,size_t Index)665a7dea167SDimitry Andric     ElementRefImpl(CFGBlockPtr Parent, size_t Index)
666a7dea167SDimitry Andric         : Parent(Parent), Index(Index) {}
667a7dea167SDimitry Andric 
668a7dea167SDimitry Andric     template <bool IsOtherConst>
ElementRefImpl(ElementRefImpl<IsOtherConst> Other)669a7dea167SDimitry Andric     ElementRefImpl(ElementRefImpl<IsOtherConst> Other)
670a7dea167SDimitry Andric         : ElementRefImpl(Other.Parent, Other.Index) {}
671a7dea167SDimitry Andric 
getIndexInBlock()672a7dea167SDimitry Andric     size_t getIndexInBlock() const { return Index; }
673a7dea167SDimitry Andric 
getParent()674a7dea167SDimitry Andric     CFGBlockPtr getParent() { return Parent; }
getParent()675a7dea167SDimitry Andric     CFGBlockPtr getParent() const { return Parent; }
676a7dea167SDimitry Andric 
677a7dea167SDimitry Andric     bool operator<(ElementRefImpl Other) const {
678a7dea167SDimitry Andric       return std::make_pair(Parent, Index) <
679a7dea167SDimitry Andric              std::make_pair(Other.Parent, Other.Index);
680a7dea167SDimitry Andric     }
681a7dea167SDimitry Andric 
682a7dea167SDimitry Andric     bool operator==(ElementRefImpl Other) const {
683a7dea167SDimitry Andric       return Parent == Other.Parent && Index == Other.Index;
684a7dea167SDimitry Andric     }
685a7dea167SDimitry Andric 
686a7dea167SDimitry Andric     bool operator!=(ElementRefImpl Other) const { return !(*this == Other); }
687a7dea167SDimitry Andric     CFGElement operator*() const { return (*Parent)[Index]; }
688a7dea167SDimitry Andric     CFGElementPtr operator->() const { return &*(Parent->begin() + Index); }
689a7dea167SDimitry Andric 
dumpToStream(llvm::raw_ostream & OS)690a7dea167SDimitry Andric     void dumpToStream(llvm::raw_ostream &OS) const {
691a7dea167SDimitry Andric       OS << getIndexInBlock() + 1 << ": ";
692a7dea167SDimitry Andric       (*this)->dumpToStream(OS);
693a7dea167SDimitry Andric     }
694a7dea167SDimitry Andric 
dump()695a7dea167SDimitry Andric     void dump() const {
696a7dea167SDimitry Andric       dumpToStream(llvm::errs());
697a7dea167SDimitry Andric     }
698a7dea167SDimitry Andric   };
699a7dea167SDimitry Andric 
700a7dea167SDimitry Andric   template <bool IsReverse, bool IsConst> class ElementRefIterator {
701a7dea167SDimitry Andric 
702a7dea167SDimitry Andric     template <bool IsOtherReverse, bool IsOtherConst>
703a7dea167SDimitry Andric     friend class ElementRefIterator;
704a7dea167SDimitry Andric 
705a7dea167SDimitry Andric     using CFGBlockRef =
7065ffd83dbSDimitry Andric         std::conditional_t<IsConst, const CFGBlock *, CFGBlock *>;
707a7dea167SDimitry Andric 
7085ffd83dbSDimitry Andric     using UnderlayingIteratorTy = std::conditional_t<
709a7dea167SDimitry Andric         IsConst,
7105ffd83dbSDimitry Andric         std::conditional_t<IsReverse, ElementList::const_reverse_iterator,
7115ffd83dbSDimitry Andric                            ElementList::const_iterator>,
7125ffd83dbSDimitry Andric         std::conditional_t<IsReverse, ElementList::reverse_iterator,
7135ffd83dbSDimitry Andric                            ElementList::iterator>>;
714a7dea167SDimitry Andric 
715a7dea167SDimitry Andric     using IteratorTraits = typename std::iterator_traits<UnderlayingIteratorTy>;
716a7dea167SDimitry Andric     using ElementRef = typename CFGBlock::ElementRefImpl<IsConst>;
717a7dea167SDimitry Andric 
718a7dea167SDimitry Andric   public:
719a7dea167SDimitry Andric     using difference_type = typename IteratorTraits::difference_type;
720a7dea167SDimitry Andric     using value_type = ElementRef;
721a7dea167SDimitry Andric     using pointer = ElementRef *;
722a7dea167SDimitry Andric     using iterator_category = typename IteratorTraits::iterator_category;
723a7dea167SDimitry Andric 
724a7dea167SDimitry Andric   private:
725a7dea167SDimitry Andric     CFGBlockRef Parent;
726a7dea167SDimitry Andric     UnderlayingIteratorTy Pos;
727a7dea167SDimitry Andric 
728a7dea167SDimitry Andric   public:
ElementRefIterator(CFGBlockRef Parent,UnderlayingIteratorTy Pos)729a7dea167SDimitry Andric     ElementRefIterator(CFGBlockRef Parent, UnderlayingIteratorTy Pos)
730a7dea167SDimitry Andric         : Parent(Parent), Pos(Pos) {}
731a7dea167SDimitry Andric 
732a7dea167SDimitry Andric     template <bool IsOtherConst>
ElementRefIterator(ElementRefIterator<false,IsOtherConst> E)733a7dea167SDimitry Andric     ElementRefIterator(ElementRefIterator<false, IsOtherConst> E)
734a7dea167SDimitry Andric         : ElementRefIterator(E.Parent, E.Pos.base()) {}
735a7dea167SDimitry Andric 
736a7dea167SDimitry Andric     template <bool IsOtherConst>
ElementRefIterator(ElementRefIterator<true,IsOtherConst> E)737a7dea167SDimitry Andric     ElementRefIterator(ElementRefIterator<true, IsOtherConst> E)
73804eeddc0SDimitry Andric         : ElementRefIterator(E.Parent, std::make_reverse_iterator(E.Pos)) {}
739a7dea167SDimitry Andric 
740a7dea167SDimitry Andric     bool operator<(ElementRefIterator Other) const {
741a7dea167SDimitry Andric       assert(Parent == Other.Parent);
742a7dea167SDimitry Andric       return Pos < Other.Pos;
743a7dea167SDimitry Andric     }
744a7dea167SDimitry Andric 
745a7dea167SDimitry Andric     bool operator==(ElementRefIterator Other) const {
746a7dea167SDimitry Andric       return Parent == Other.Parent && Pos == Other.Pos;
747a7dea167SDimitry Andric     }
748a7dea167SDimitry Andric 
749a7dea167SDimitry Andric     bool operator!=(ElementRefIterator Other) const {
750a7dea167SDimitry Andric       return !(*this == Other);
751a7dea167SDimitry Andric     }
752a7dea167SDimitry Andric 
753a7dea167SDimitry Andric   private:
754a7dea167SDimitry Andric     template <bool IsOtherConst>
755a7dea167SDimitry Andric     static size_t
getIndexInBlock(CFGBlock::ElementRefIterator<true,IsOtherConst> E)756a7dea167SDimitry Andric     getIndexInBlock(CFGBlock::ElementRefIterator<true, IsOtherConst> E) {
757a7dea167SDimitry Andric       return E.Parent->size() - (E.Pos - E.Parent->rbegin()) - 1;
758a7dea167SDimitry Andric     }
759a7dea167SDimitry Andric 
760a7dea167SDimitry Andric     template <bool IsOtherConst>
761a7dea167SDimitry Andric     static size_t
getIndexInBlock(CFGBlock::ElementRefIterator<false,IsOtherConst> E)762a7dea167SDimitry Andric     getIndexInBlock(CFGBlock::ElementRefIterator<false, IsOtherConst> E) {
763a7dea167SDimitry Andric       return E.Pos - E.Parent->begin();
764a7dea167SDimitry Andric     }
765a7dea167SDimitry Andric 
766a7dea167SDimitry Andric   public:
767a7dea167SDimitry Andric     value_type operator*() { return {Parent, getIndexInBlock(*this)}; }
768a7dea167SDimitry Andric 
769a7dea167SDimitry Andric     difference_type operator-(ElementRefIterator Other) const {
770a7dea167SDimitry Andric       return Pos - Other.Pos;
771a7dea167SDimitry Andric     }
772a7dea167SDimitry Andric 
773a7dea167SDimitry Andric     ElementRefIterator operator++() {
774a7dea167SDimitry Andric       ++this->Pos;
775a7dea167SDimitry Andric       return *this;
776a7dea167SDimitry Andric     }
777a7dea167SDimitry Andric     ElementRefIterator operator++(int) {
778a7dea167SDimitry Andric       ElementRefIterator Ret = *this;
779a7dea167SDimitry Andric       ++*this;
780a7dea167SDimitry Andric       return Ret;
781a7dea167SDimitry Andric     }
782a7dea167SDimitry Andric     ElementRefIterator operator+(size_t count) {
783a7dea167SDimitry Andric       this->Pos += count;
784a7dea167SDimitry Andric       return *this;
785a7dea167SDimitry Andric     }
786a7dea167SDimitry Andric     ElementRefIterator operator-(size_t count) {
787a7dea167SDimitry Andric       this->Pos -= count;
788a7dea167SDimitry Andric       return *this;
789a7dea167SDimitry Andric     }
790a7dea167SDimitry Andric   };
791a7dea167SDimitry Andric 
792a7dea167SDimitry Andric public:
7930b57cec5SDimitry Andric   /// The set of statements in the basic block.
7940b57cec5SDimitry Andric   ElementList Elements;
7950b57cec5SDimitry Andric 
7960b57cec5SDimitry Andric   /// An (optional) label that prefixes the executable statements in the block.
7970b57cec5SDimitry Andric   /// When this variable is non-NULL, it is either an instance of LabelStmt,
7980b57cec5SDimitry Andric   /// SwitchCase or CXXCatchStmt.
7990b57cec5SDimitry Andric   Stmt *Label = nullptr;
8000b57cec5SDimitry Andric 
8010b57cec5SDimitry Andric   /// The terminator for a basic block that indicates the type of control-flow
8020b57cec5SDimitry Andric   /// that occurs between a block and its successors.
8030b57cec5SDimitry Andric   CFGTerminator Terminator;
8040b57cec5SDimitry Andric 
8050b57cec5SDimitry Andric   /// Some blocks are used to represent the "loop edge" to the start of a loop
8060b57cec5SDimitry Andric   /// from within the loop body. This Stmt* will be refer to the loop statement
8070b57cec5SDimitry Andric   /// for such blocks (and be null otherwise).
8080b57cec5SDimitry Andric   const Stmt *LoopTarget = nullptr;
8090b57cec5SDimitry Andric 
8100b57cec5SDimitry Andric   /// A numerical ID assigned to a CFGBlock during construction of the CFG.
8110b57cec5SDimitry Andric   unsigned BlockID;
8120b57cec5SDimitry Andric 
8130b57cec5SDimitry Andric public:
8140b57cec5SDimitry Andric   /// This class represents a potential adjacent block in the CFG.  It encodes
8150b57cec5SDimitry Andric   /// whether or not the block is actually reachable, or can be proved to be
8160b57cec5SDimitry Andric   /// trivially unreachable.  For some cases it allows one to encode scenarios
8170b57cec5SDimitry Andric   /// where a block was substituted because the original (now alternate) block
8180b57cec5SDimitry Andric   /// is unreachable.
8190b57cec5SDimitry Andric   class AdjacentBlock {
8200b57cec5SDimitry Andric     enum Kind {
8210b57cec5SDimitry Andric       AB_Normal,
8220b57cec5SDimitry Andric       AB_Unreachable,
8230b57cec5SDimitry Andric       AB_Alternate
8240b57cec5SDimitry Andric     };
8250b57cec5SDimitry Andric 
8260b57cec5SDimitry Andric     CFGBlock *ReachableBlock;
8270b57cec5SDimitry Andric     llvm::PointerIntPair<CFGBlock *, 2> UnreachableBlock;
8280b57cec5SDimitry Andric 
8290b57cec5SDimitry Andric   public:
8300b57cec5SDimitry Andric     /// Construct an AdjacentBlock with a possibly unreachable block.
8310b57cec5SDimitry Andric     AdjacentBlock(CFGBlock *B, bool IsReachable);
8320b57cec5SDimitry Andric 
8330b57cec5SDimitry Andric     /// Construct an AdjacentBlock with a reachable block and an alternate
8340b57cec5SDimitry Andric     /// unreachable block.
8350b57cec5SDimitry Andric     AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock);
8360b57cec5SDimitry Andric 
8370b57cec5SDimitry Andric     /// Get the reachable block, if one exists.
getReachableBlock()8380b57cec5SDimitry Andric     CFGBlock *getReachableBlock() const {
8390b57cec5SDimitry Andric       return ReachableBlock;
8400b57cec5SDimitry Andric     }
8410b57cec5SDimitry Andric 
8420b57cec5SDimitry Andric     /// Get the potentially unreachable block.
getPossiblyUnreachableBlock()8430b57cec5SDimitry Andric     CFGBlock *getPossiblyUnreachableBlock() const {
8440b57cec5SDimitry Andric       return UnreachableBlock.getPointer();
8450b57cec5SDimitry Andric     }
8460b57cec5SDimitry Andric 
8470b57cec5SDimitry Andric     /// Provide an implicit conversion to CFGBlock* so that
8480b57cec5SDimitry Andric     /// AdjacentBlock can be substituted for CFGBlock*.
8490b57cec5SDimitry Andric     operator CFGBlock*() const {
8500b57cec5SDimitry Andric       return getReachableBlock();
8510b57cec5SDimitry Andric     }
8520b57cec5SDimitry Andric 
8530b57cec5SDimitry Andric     CFGBlock& operator *() const {
8540b57cec5SDimitry Andric       return *getReachableBlock();
8550b57cec5SDimitry Andric     }
8560b57cec5SDimitry Andric 
8570b57cec5SDimitry Andric     CFGBlock* operator ->() const {
8580b57cec5SDimitry Andric       return getReachableBlock();
8590b57cec5SDimitry Andric     }
8600b57cec5SDimitry Andric 
isReachable()8610b57cec5SDimitry Andric     bool isReachable() const {
8620b57cec5SDimitry Andric       Kind K = (Kind) UnreachableBlock.getInt();
8630b57cec5SDimitry Andric       return K == AB_Normal || K == AB_Alternate;
8640b57cec5SDimitry Andric     }
8650b57cec5SDimitry Andric   };
8660b57cec5SDimitry Andric 
8670b57cec5SDimitry Andric private:
8680b57cec5SDimitry Andric   /// Keep track of the predecessor / successor CFG blocks.
8690b57cec5SDimitry Andric   using AdjacentBlocks = BumpVector<AdjacentBlock>;
8700b57cec5SDimitry Andric   AdjacentBlocks Preds;
8710b57cec5SDimitry Andric   AdjacentBlocks Succs;
8720b57cec5SDimitry Andric 
8730b57cec5SDimitry Andric   /// This bit is set when the basic block contains a function call
8740b57cec5SDimitry Andric   /// or implicit destructor that is attributed as 'noreturn'. In that case,
8750b57cec5SDimitry Andric   /// control cannot technically ever proceed past this block. All such blocks
8760b57cec5SDimitry Andric   /// will have a single immediate successor: the exit block. This allows them
8770b57cec5SDimitry Andric   /// to be easily reached from the exit block and using this bit quickly
8780b57cec5SDimitry Andric   /// recognized without scanning the contents of the block.
8790b57cec5SDimitry Andric   ///
8800b57cec5SDimitry Andric   /// Optimization Note: This bit could be profitably folded with Terminator's
8810b57cec5SDimitry Andric   /// storage if the memory usage of CFGBlock becomes an issue.
8820b57cec5SDimitry Andric   unsigned HasNoReturnElement : 1;
8830b57cec5SDimitry Andric 
8840b57cec5SDimitry Andric   /// The parent CFG that owns this CFGBlock.
8850b57cec5SDimitry Andric   CFG *Parent;
8860b57cec5SDimitry Andric 
8870b57cec5SDimitry Andric public:
CFGBlock(unsigned blockid,BumpVectorContext & C,CFG * parent)8880b57cec5SDimitry Andric   explicit CFGBlock(unsigned blockid, BumpVectorContext &C, CFG *parent)
8890b57cec5SDimitry Andric       : Elements(C), Terminator(nullptr), BlockID(blockid), Preds(C, 1),
8900b57cec5SDimitry Andric         Succs(C, 1), HasNoReturnElement(false), Parent(parent) {}
8910b57cec5SDimitry Andric 
8920b57cec5SDimitry Andric   // Statement iterators
8930b57cec5SDimitry Andric   using iterator = ElementList::iterator;
8940b57cec5SDimitry Andric   using const_iterator = ElementList::const_iterator;
8950b57cec5SDimitry Andric   using reverse_iterator = ElementList::reverse_iterator;
8960b57cec5SDimitry Andric   using const_reverse_iterator = ElementList::const_reverse_iterator;
8970b57cec5SDimitry Andric 
898a7dea167SDimitry Andric   size_t getIndexInCFG() const;
899a7dea167SDimitry Andric 
front()9000b57cec5SDimitry Andric   CFGElement                 front()       const { return Elements.front();   }
back()9010b57cec5SDimitry Andric   CFGElement                 back()        const { return Elements.back();    }
9020b57cec5SDimitry Andric 
begin()9030b57cec5SDimitry Andric   iterator                   begin()             { return Elements.begin();   }
end()9040b57cec5SDimitry Andric   iterator                   end()               { return Elements.end();     }
begin()9050b57cec5SDimitry Andric   const_iterator             begin()       const { return Elements.begin();   }
end()9060b57cec5SDimitry Andric   const_iterator             end()         const { return Elements.end();     }
9070b57cec5SDimitry Andric 
rbegin()9080b57cec5SDimitry Andric   reverse_iterator           rbegin()            { return Elements.rbegin();  }
rend()9090b57cec5SDimitry Andric   reverse_iterator           rend()              { return Elements.rend();    }
rbegin()9100b57cec5SDimitry Andric   const_reverse_iterator     rbegin()      const { return Elements.rbegin();  }
rend()9110b57cec5SDimitry Andric   const_reverse_iterator     rend()        const { return Elements.rend();    }
9120b57cec5SDimitry Andric 
913a7dea167SDimitry Andric   using CFGElementRef = ElementRefImpl<false>;
914a7dea167SDimitry Andric   using ConstCFGElementRef = ElementRefImpl<true>;
915a7dea167SDimitry Andric 
916a7dea167SDimitry Andric   using ref_iterator = ElementRefIterator<false, false>;
917a7dea167SDimitry Andric   using ref_iterator_range = llvm::iterator_range<ref_iterator>;
918a7dea167SDimitry Andric   using const_ref_iterator = ElementRefIterator<false, true>;
919a7dea167SDimitry Andric   using const_ref_iterator_range = llvm::iterator_range<const_ref_iterator>;
920a7dea167SDimitry Andric 
921a7dea167SDimitry Andric   using reverse_ref_iterator = ElementRefIterator<true, false>;
922a7dea167SDimitry Andric   using reverse_ref_iterator_range = llvm::iterator_range<reverse_ref_iterator>;
923a7dea167SDimitry Andric 
924a7dea167SDimitry Andric   using const_reverse_ref_iterator = ElementRefIterator<true, true>;
925a7dea167SDimitry Andric   using const_reverse_ref_iterator_range =
926a7dea167SDimitry Andric       llvm::iterator_range<const_reverse_ref_iterator>;
927a7dea167SDimitry Andric 
ref_begin()928a7dea167SDimitry Andric   ref_iterator ref_begin() { return {this, begin()}; }
ref_end()929a7dea167SDimitry Andric   ref_iterator ref_end() { return {this, end()}; }
ref_begin()930a7dea167SDimitry Andric   const_ref_iterator ref_begin() const { return {this, begin()}; }
ref_end()931a7dea167SDimitry Andric   const_ref_iterator ref_end() const { return {this, end()}; }
932a7dea167SDimitry Andric 
rref_begin()933a7dea167SDimitry Andric   reverse_ref_iterator rref_begin() { return {this, rbegin()}; }
rref_end()934a7dea167SDimitry Andric   reverse_ref_iterator rref_end() { return {this, rend()}; }
rref_begin()935a7dea167SDimitry Andric   const_reverse_ref_iterator rref_begin() const { return {this, rbegin()}; }
rref_end()936a7dea167SDimitry Andric   const_reverse_ref_iterator rref_end() const { return {this, rend()}; }
937a7dea167SDimitry Andric 
refs()938a7dea167SDimitry Andric   ref_iterator_range refs() { return {ref_begin(), ref_end()}; }
refs()939a7dea167SDimitry Andric   const_ref_iterator_range refs() const { return {ref_begin(), ref_end()}; }
rrefs()940a7dea167SDimitry Andric   reverse_ref_iterator_range rrefs() { return {rref_begin(), rref_end()}; }
rrefs()941a7dea167SDimitry Andric   const_reverse_ref_iterator_range rrefs() const {
942a7dea167SDimitry Andric     return {rref_begin(), rref_end()};
943a7dea167SDimitry Andric   }
944a7dea167SDimitry Andric 
size()9450b57cec5SDimitry Andric   unsigned                   size()        const { return Elements.size();    }
empty()9460b57cec5SDimitry Andric   bool                       empty()       const { return Elements.empty();   }
9470b57cec5SDimitry Andric 
9480b57cec5SDimitry Andric   CFGElement operator[](size_t i) const  { return Elements[i]; }
9490b57cec5SDimitry Andric 
9500b57cec5SDimitry Andric   // CFG iterators
9510b57cec5SDimitry Andric   using pred_iterator = AdjacentBlocks::iterator;
9520b57cec5SDimitry Andric   using const_pred_iterator = AdjacentBlocks::const_iterator;
9530b57cec5SDimitry Andric   using pred_reverse_iterator = AdjacentBlocks::reverse_iterator;
9540b57cec5SDimitry Andric   using const_pred_reverse_iterator = AdjacentBlocks::const_reverse_iterator;
9550b57cec5SDimitry Andric   using pred_range = llvm::iterator_range<pred_iterator>;
9560b57cec5SDimitry Andric   using pred_const_range = llvm::iterator_range<const_pred_iterator>;
9570b57cec5SDimitry Andric 
9580b57cec5SDimitry Andric   using succ_iterator = AdjacentBlocks::iterator;
9590b57cec5SDimitry Andric   using const_succ_iterator = AdjacentBlocks::const_iterator;
9600b57cec5SDimitry Andric   using succ_reverse_iterator = AdjacentBlocks::reverse_iterator;
9610b57cec5SDimitry Andric   using const_succ_reverse_iterator = AdjacentBlocks::const_reverse_iterator;
9620b57cec5SDimitry Andric   using succ_range = llvm::iterator_range<succ_iterator>;
9630b57cec5SDimitry Andric   using succ_const_range = llvm::iterator_range<const_succ_iterator>;
9640b57cec5SDimitry Andric 
pred_begin()9650b57cec5SDimitry Andric   pred_iterator                pred_begin()        { return Preds.begin();   }
pred_end()9660b57cec5SDimitry Andric   pred_iterator                pred_end()          { return Preds.end();     }
pred_begin()9670b57cec5SDimitry Andric   const_pred_iterator          pred_begin()  const { return Preds.begin();   }
pred_end()9680b57cec5SDimitry Andric   const_pred_iterator          pred_end()    const { return Preds.end();     }
9690b57cec5SDimitry Andric 
pred_rbegin()9700b57cec5SDimitry Andric   pred_reverse_iterator        pred_rbegin()       { return Preds.rbegin();  }
pred_rend()9710b57cec5SDimitry Andric   pred_reverse_iterator        pred_rend()         { return Preds.rend();    }
pred_rbegin()9720b57cec5SDimitry Andric   const_pred_reverse_iterator  pred_rbegin() const { return Preds.rbegin();  }
pred_rend()9730b57cec5SDimitry Andric   const_pred_reverse_iterator  pred_rend()   const { return Preds.rend();    }
9740b57cec5SDimitry Andric 
preds()9750b57cec5SDimitry Andric   pred_range preds() {
9760b57cec5SDimitry Andric     return pred_range(pred_begin(), pred_end());
9770b57cec5SDimitry Andric   }
9780b57cec5SDimitry Andric 
preds()9790b57cec5SDimitry Andric   pred_const_range preds() const {
9800b57cec5SDimitry Andric     return pred_const_range(pred_begin(), pred_end());
9810b57cec5SDimitry Andric   }
9820b57cec5SDimitry Andric 
succ_begin()9830b57cec5SDimitry Andric   succ_iterator                succ_begin()        { return Succs.begin();   }
succ_end()9840b57cec5SDimitry Andric   succ_iterator                succ_end()          { return Succs.end();     }
succ_begin()9850b57cec5SDimitry Andric   const_succ_iterator          succ_begin()  const { return Succs.begin();   }
succ_end()9860b57cec5SDimitry Andric   const_succ_iterator          succ_end()    const { return Succs.end();     }
9870b57cec5SDimitry Andric 
succ_rbegin()9880b57cec5SDimitry Andric   succ_reverse_iterator        succ_rbegin()       { return Succs.rbegin();  }
succ_rend()9890b57cec5SDimitry Andric   succ_reverse_iterator        succ_rend()         { return Succs.rend();    }
succ_rbegin()9900b57cec5SDimitry Andric   const_succ_reverse_iterator  succ_rbegin() const { return Succs.rbegin();  }
succ_rend()9910b57cec5SDimitry Andric   const_succ_reverse_iterator  succ_rend()   const { return Succs.rend();    }
9920b57cec5SDimitry Andric 
succs()9930b57cec5SDimitry Andric   succ_range succs() {
9940b57cec5SDimitry Andric     return succ_range(succ_begin(), succ_end());
9950b57cec5SDimitry Andric   }
9960b57cec5SDimitry Andric 
succs()9970b57cec5SDimitry Andric   succ_const_range succs() const {
9980b57cec5SDimitry Andric     return succ_const_range(succ_begin(), succ_end());
9990b57cec5SDimitry Andric   }
10000b57cec5SDimitry Andric 
succ_size()10010b57cec5SDimitry Andric   unsigned                     succ_size()   const { return Succs.size();    }
succ_empty()10020b57cec5SDimitry Andric   bool                         succ_empty()  const { return Succs.empty();   }
10030b57cec5SDimitry Andric 
pred_size()10040b57cec5SDimitry Andric   unsigned                     pred_size()   const { return Preds.size();    }
pred_empty()10050b57cec5SDimitry Andric   bool                         pred_empty()  const { return Preds.empty();   }
10060b57cec5SDimitry Andric 
10070b57cec5SDimitry Andric 
10080b57cec5SDimitry Andric   class FilterOptions {
10090b57cec5SDimitry Andric   public:
10100b57cec5SDimitry Andric     unsigned IgnoreNullPredecessors : 1;
10110b57cec5SDimitry Andric     unsigned IgnoreDefaultsWithCoveredEnums : 1;
10120b57cec5SDimitry Andric 
FilterOptions()10130b57cec5SDimitry Andric     FilterOptions()
10140b57cec5SDimitry Andric         : IgnoreNullPredecessors(1), IgnoreDefaultsWithCoveredEnums(0) {}
10150b57cec5SDimitry Andric   };
10160b57cec5SDimitry Andric 
10170b57cec5SDimitry Andric   static bool FilterEdge(const FilterOptions &F, const CFGBlock *Src,
10180b57cec5SDimitry Andric        const CFGBlock *Dst);
10190b57cec5SDimitry Andric 
10200b57cec5SDimitry Andric   template <typename IMPL, bool IsPred>
10210b57cec5SDimitry Andric   class FilteredCFGBlockIterator {
10220b57cec5SDimitry Andric   private:
10230b57cec5SDimitry Andric     IMPL I, E;
10240b57cec5SDimitry Andric     const FilterOptions F;
10250b57cec5SDimitry Andric     const CFGBlock *From;
10260b57cec5SDimitry Andric 
10270b57cec5SDimitry Andric   public:
FilteredCFGBlockIterator(const IMPL & i,const IMPL & e,const CFGBlock * from,const FilterOptions & f)10280b57cec5SDimitry Andric     explicit FilteredCFGBlockIterator(const IMPL &i, const IMPL &e,
10290b57cec5SDimitry Andric                                       const CFGBlock *from,
10300b57cec5SDimitry Andric                                       const FilterOptions &f)
10310b57cec5SDimitry Andric         : I(i), E(e), F(f), From(from) {
10320b57cec5SDimitry Andric       while (hasMore() && Filter(*I))
10330b57cec5SDimitry Andric         ++I;
10340b57cec5SDimitry Andric     }
10350b57cec5SDimitry Andric 
hasMore()10360b57cec5SDimitry Andric     bool hasMore() const { return I != E; }
10370b57cec5SDimitry Andric 
10380b57cec5SDimitry Andric     FilteredCFGBlockIterator &operator++() {
10390b57cec5SDimitry Andric       do { ++I; } while (hasMore() && Filter(*I));
10400b57cec5SDimitry Andric       return *this;
10410b57cec5SDimitry Andric     }
10420b57cec5SDimitry Andric 
10430b57cec5SDimitry Andric     const CFGBlock *operator*() const { return *I; }
10440b57cec5SDimitry Andric 
10450b57cec5SDimitry Andric   private:
Filter(const CFGBlock * To)10460b57cec5SDimitry Andric     bool Filter(const CFGBlock *To) {
10470b57cec5SDimitry Andric       return IsPred ? FilterEdge(F, To, From) : FilterEdge(F, From, To);
10480b57cec5SDimitry Andric     }
10490b57cec5SDimitry Andric   };
10500b57cec5SDimitry Andric 
10510b57cec5SDimitry Andric   using filtered_pred_iterator =
10520b57cec5SDimitry Andric       FilteredCFGBlockIterator<const_pred_iterator, true>;
10530b57cec5SDimitry Andric 
10540b57cec5SDimitry Andric   using filtered_succ_iterator =
10550b57cec5SDimitry Andric       FilteredCFGBlockIterator<const_succ_iterator, false>;
10560b57cec5SDimitry Andric 
filtered_pred_start_end(const FilterOptions & f)10570b57cec5SDimitry Andric   filtered_pred_iterator filtered_pred_start_end(const FilterOptions &f) const {
10580b57cec5SDimitry Andric     return filtered_pred_iterator(pred_begin(), pred_end(), this, f);
10590b57cec5SDimitry Andric   }
10600b57cec5SDimitry Andric 
filtered_succ_start_end(const FilterOptions & f)10610b57cec5SDimitry Andric   filtered_succ_iterator filtered_succ_start_end(const FilterOptions &f) const {
10620b57cec5SDimitry Andric     return filtered_succ_iterator(succ_begin(), succ_end(), this, f);
10630b57cec5SDimitry Andric   }
10640b57cec5SDimitry Andric 
10650b57cec5SDimitry Andric   // Manipulation of block contents
10660b57cec5SDimitry Andric 
setTerminator(CFGTerminator Term)10670b57cec5SDimitry Andric   void setTerminator(CFGTerminator Term) { Terminator = Term; }
setLabel(Stmt * Statement)10680b57cec5SDimitry Andric   void setLabel(Stmt *Statement) { Label = Statement; }
setLoopTarget(const Stmt * loopTarget)10690b57cec5SDimitry Andric   void setLoopTarget(const Stmt *loopTarget) { LoopTarget = loopTarget; }
setHasNoReturnElement()10700b57cec5SDimitry Andric   void setHasNoReturnElement() { HasNoReturnElement = true; }
10710b57cec5SDimitry Andric 
1072a7dea167SDimitry Andric   /// Returns true if the block would eventually end with a sink (a noreturn
1073a7dea167SDimitry Andric   /// node).
1074a7dea167SDimitry Andric   bool isInevitablySinking() const;
1075a7dea167SDimitry Andric 
getTerminator()10760b57cec5SDimitry Andric   CFGTerminator getTerminator() const { return Terminator; }
10770b57cec5SDimitry Andric 
getTerminatorStmt()10780b57cec5SDimitry Andric   Stmt *getTerminatorStmt() { return Terminator.getStmt(); }
getTerminatorStmt()10790b57cec5SDimitry Andric   const Stmt *getTerminatorStmt() const { return Terminator.getStmt(); }
10800b57cec5SDimitry Andric 
10810b57cec5SDimitry Andric   /// \returns the last (\c rbegin()) condition, e.g. observe the following code
10820b57cec5SDimitry Andric   /// snippet:
10830b57cec5SDimitry Andric   ///   if (A && B && C)
10840b57cec5SDimitry Andric   /// A block would be created for \c A, \c B, and \c C. For the latter,
10850b57cec5SDimitry Andric   /// \c getTerminatorStmt() would retrieve the entire condition, rather than
10860b57cec5SDimitry Andric   /// C itself, while this method would only return C.
10870b57cec5SDimitry Andric   const Expr *getLastCondition() const;
10880b57cec5SDimitry Andric 
10890b57cec5SDimitry Andric   Stmt *getTerminatorCondition(bool StripParens = true);
10900b57cec5SDimitry Andric 
10910b57cec5SDimitry Andric   const Stmt *getTerminatorCondition(bool StripParens = true) const {
10920b57cec5SDimitry Andric     return const_cast<CFGBlock*>(this)->getTerminatorCondition(StripParens);
10930b57cec5SDimitry Andric   }
10940b57cec5SDimitry Andric 
getLoopTarget()10950b57cec5SDimitry Andric   const Stmt *getLoopTarget() const { return LoopTarget; }
10960b57cec5SDimitry Andric 
getLabel()10970b57cec5SDimitry Andric   Stmt *getLabel() { return Label; }
getLabel()10980b57cec5SDimitry Andric   const Stmt *getLabel() const { return Label; }
10990b57cec5SDimitry Andric 
hasNoReturnElement()11000b57cec5SDimitry Andric   bool hasNoReturnElement() const { return HasNoReturnElement; }
11010b57cec5SDimitry Andric 
getBlockID()11020b57cec5SDimitry Andric   unsigned getBlockID() const { return BlockID; }
11030b57cec5SDimitry Andric 
getParent()11040b57cec5SDimitry Andric   CFG *getParent() const { return Parent; }
11050b57cec5SDimitry Andric 
11060b57cec5SDimitry Andric   void dump() const;
11070b57cec5SDimitry Andric 
11080b57cec5SDimitry Andric   void dump(const CFG *cfg, const LangOptions &LO, bool ShowColors = false) const;
11090b57cec5SDimitry Andric   void print(raw_ostream &OS, const CFG* cfg, const LangOptions &LO,
11100b57cec5SDimitry Andric              bool ShowColors) const;
11110b57cec5SDimitry Andric 
11120b57cec5SDimitry Andric   void printTerminator(raw_ostream &OS, const LangOptions &LO) const;
11130b57cec5SDimitry Andric   void printTerminatorJson(raw_ostream &Out, const LangOptions &LO,
11140b57cec5SDimitry Andric                            bool AddQuotes) const;
11150b57cec5SDimitry Andric 
printAsOperand(raw_ostream & OS,bool)11160b57cec5SDimitry Andric   void printAsOperand(raw_ostream &OS, bool /*PrintType*/) {
11170b57cec5SDimitry Andric     OS << "BB#" << getBlockID();
11180b57cec5SDimitry Andric   }
11190b57cec5SDimitry Andric 
11200b57cec5SDimitry Andric   /// Adds a (potentially unreachable) successor block to the current block.
11210b57cec5SDimitry Andric   void addSuccessor(AdjacentBlock Succ, BumpVectorContext &C);
11220b57cec5SDimitry Andric 
appendStmt(Stmt * statement,BumpVectorContext & C)11230b57cec5SDimitry Andric   void appendStmt(Stmt *statement, BumpVectorContext &C) {
11240b57cec5SDimitry Andric     Elements.push_back(CFGStmt(statement), C);
11250b57cec5SDimitry Andric   }
11260b57cec5SDimitry Andric 
appendConstructor(CXXConstructExpr * CE,const ConstructionContext * CC,BumpVectorContext & C)11270b57cec5SDimitry Andric   void appendConstructor(CXXConstructExpr *CE, const ConstructionContext *CC,
11280b57cec5SDimitry Andric                          BumpVectorContext &C) {
11290b57cec5SDimitry Andric     Elements.push_back(CFGConstructor(CE, CC), C);
11300b57cec5SDimitry Andric   }
11310b57cec5SDimitry Andric 
appendCXXRecordTypedCall(Expr * E,const ConstructionContext * CC,BumpVectorContext & C)11320b57cec5SDimitry Andric   void appendCXXRecordTypedCall(Expr *E,
11330b57cec5SDimitry Andric                                 const ConstructionContext *CC,
11340b57cec5SDimitry Andric                                 BumpVectorContext &C) {
11350b57cec5SDimitry Andric     Elements.push_back(CFGCXXRecordTypedCall(E, CC), C);
11360b57cec5SDimitry Andric   }
11370b57cec5SDimitry Andric 
appendInitializer(CXXCtorInitializer * initializer,BumpVectorContext & C)11380b57cec5SDimitry Andric   void appendInitializer(CXXCtorInitializer *initializer,
11390b57cec5SDimitry Andric                         BumpVectorContext &C) {
11400b57cec5SDimitry Andric     Elements.push_back(CFGInitializer(initializer), C);
11410b57cec5SDimitry Andric   }
11420b57cec5SDimitry Andric 
appendNewAllocator(CXXNewExpr * NE,BumpVectorContext & C)11430b57cec5SDimitry Andric   void appendNewAllocator(CXXNewExpr *NE,
11440b57cec5SDimitry Andric                           BumpVectorContext &C) {
11450b57cec5SDimitry Andric     Elements.push_back(CFGNewAllocator(NE), C);
11460b57cec5SDimitry Andric   }
11470b57cec5SDimitry Andric 
appendScopeBegin(const VarDecl * VD,const Stmt * S,BumpVectorContext & C)11480b57cec5SDimitry Andric   void appendScopeBegin(const VarDecl *VD, const Stmt *S,
11490b57cec5SDimitry Andric                         BumpVectorContext &C) {
11500b57cec5SDimitry Andric     Elements.push_back(CFGScopeBegin(VD, S), C);
11510b57cec5SDimitry Andric   }
11520b57cec5SDimitry Andric 
appendScopeEnd(const VarDecl * VD,const Stmt * S,BumpVectorContext & C)11530b57cec5SDimitry Andric   void appendScopeEnd(const VarDecl *VD, const Stmt *S, BumpVectorContext &C) {
11540b57cec5SDimitry Andric     Elements.push_back(CFGScopeEnd(VD, S), C);
11550b57cec5SDimitry Andric   }
11560b57cec5SDimitry Andric 
appendBaseDtor(const CXXBaseSpecifier * BS,BumpVectorContext & C)11570b57cec5SDimitry Andric   void appendBaseDtor(const CXXBaseSpecifier *BS, BumpVectorContext &C) {
11580b57cec5SDimitry Andric     Elements.push_back(CFGBaseDtor(BS), C);
11590b57cec5SDimitry Andric   }
11600b57cec5SDimitry Andric 
appendMemberDtor(FieldDecl * FD,BumpVectorContext & C)11610b57cec5SDimitry Andric   void appendMemberDtor(FieldDecl *FD, BumpVectorContext &C) {
11620b57cec5SDimitry Andric     Elements.push_back(CFGMemberDtor(FD), C);
11630b57cec5SDimitry Andric   }
11640b57cec5SDimitry Andric 
appendTemporaryDtor(CXXBindTemporaryExpr * E,BumpVectorContext & C)11650b57cec5SDimitry Andric   void appendTemporaryDtor(CXXBindTemporaryExpr *E, BumpVectorContext &C) {
11660b57cec5SDimitry Andric     Elements.push_back(CFGTemporaryDtor(E), C);
11670b57cec5SDimitry Andric   }
11680b57cec5SDimitry Andric 
appendAutomaticObjDtor(VarDecl * VD,Stmt * S,BumpVectorContext & C)11690b57cec5SDimitry Andric   void appendAutomaticObjDtor(VarDecl *VD, Stmt *S, BumpVectorContext &C) {
11700b57cec5SDimitry Andric     Elements.push_back(CFGAutomaticObjDtor(VD, S), C);
11710b57cec5SDimitry Andric   }
11720b57cec5SDimitry Andric 
appendCleanupFunction(const VarDecl * VD,BumpVectorContext & C)11735f757f3fSDimitry Andric   void appendCleanupFunction(const VarDecl *VD, BumpVectorContext &C) {
11745f757f3fSDimitry Andric     Elements.push_back(CFGCleanupFunction(VD), C);
11755f757f3fSDimitry Andric   }
11765f757f3fSDimitry Andric 
appendLifetimeEnds(VarDecl * VD,Stmt * S,BumpVectorContext & C)11770b57cec5SDimitry Andric   void appendLifetimeEnds(VarDecl *VD, Stmt *S, BumpVectorContext &C) {
11780b57cec5SDimitry Andric     Elements.push_back(CFGLifetimeEnds(VD, S), C);
11790b57cec5SDimitry Andric   }
11800b57cec5SDimitry Andric 
appendLoopExit(const Stmt * LoopStmt,BumpVectorContext & C)11810b57cec5SDimitry Andric   void appendLoopExit(const Stmt *LoopStmt, BumpVectorContext &C) {
11820b57cec5SDimitry Andric     Elements.push_back(CFGLoopExit(LoopStmt), C);
11830b57cec5SDimitry Andric   }
11840b57cec5SDimitry Andric 
appendDeleteDtor(CXXRecordDecl * RD,CXXDeleteExpr * DE,BumpVectorContext & C)11850b57cec5SDimitry Andric   void appendDeleteDtor(CXXRecordDecl *RD, CXXDeleteExpr *DE, BumpVectorContext &C) {
11860b57cec5SDimitry Andric     Elements.push_back(CFGDeleteDtor(RD, DE), C);
11870b57cec5SDimitry Andric   }
11880b57cec5SDimitry Andric };
11890b57cec5SDimitry Andric 
11900b57cec5SDimitry Andric /// CFGCallback defines methods that should be called when a logical
11910b57cec5SDimitry Andric /// operator error is found when building the CFG.
11920b57cec5SDimitry Andric class CFGCallback {
11930b57cec5SDimitry Andric public:
11940b57cec5SDimitry Andric   CFGCallback() = default;
11950b57cec5SDimitry Andric   virtual ~CFGCallback() = default;
11960b57cec5SDimitry Andric 
logicAlwaysTrue(const BinaryOperator * B,bool isAlwaysTrue)11975f757f3fSDimitry Andric   virtual void logicAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {}
compareAlwaysTrue(const BinaryOperator * B,bool isAlwaysTrue)11980b57cec5SDimitry Andric   virtual void compareAlwaysTrue(const BinaryOperator *B, bool isAlwaysTrue) {}
compareBitwiseEquality(const BinaryOperator * B,bool isAlwaysTrue)11990b57cec5SDimitry Andric   virtual void compareBitwiseEquality(const BinaryOperator *B,
12000b57cec5SDimitry Andric                                       bool isAlwaysTrue) {}
compareBitwiseOr(const BinaryOperator * B)1201a7dea167SDimitry Andric   virtual void compareBitwiseOr(const BinaryOperator *B) {}
12020b57cec5SDimitry Andric };
12030b57cec5SDimitry Andric 
12040b57cec5SDimitry Andric /// Represents a source-level, intra-procedural CFG that represents the
12050b57cec5SDimitry Andric ///  control-flow of a Stmt.  The Stmt can represent an entire function body,
12060b57cec5SDimitry Andric ///  or a single expression.  A CFG will always contain one empty block that
12070b57cec5SDimitry Andric ///  represents the Exit point of the CFG.  A CFG will also contain a designated
12080b57cec5SDimitry Andric ///  Entry block.  The CFG solely represents control-flow; it consists of
12090b57cec5SDimitry Andric ///  CFGBlocks which are simply containers of Stmt*'s in the AST the CFG
12100b57cec5SDimitry Andric ///  was constructed from.
12110b57cec5SDimitry Andric class CFG {
12120b57cec5SDimitry Andric public:
12130b57cec5SDimitry Andric   //===--------------------------------------------------------------------===//
12140b57cec5SDimitry Andric   // CFG Construction & Manipulation.
12150b57cec5SDimitry Andric   //===--------------------------------------------------------------------===//
12160b57cec5SDimitry Andric 
12170b57cec5SDimitry Andric   class BuildOptions {
12181db9f3b2SDimitry Andric     // Stmt::lastStmtConstant has the same value as the last Stmt kind,
12191db9f3b2SDimitry Andric     // so make sure we add one to account for this!
12201db9f3b2SDimitry Andric     std::bitset<Stmt::lastStmtConstant + 1> alwaysAddMask;
12210b57cec5SDimitry Andric 
12220b57cec5SDimitry Andric   public:
12230b57cec5SDimitry Andric     using ForcedBlkExprs = llvm::DenseMap<const Stmt *, const CFGBlock *>;
12240b57cec5SDimitry Andric 
12250b57cec5SDimitry Andric     ForcedBlkExprs **forcedBlkExprs = nullptr;
12260b57cec5SDimitry Andric     CFGCallback *Observer = nullptr;
12270b57cec5SDimitry Andric     bool PruneTriviallyFalseEdges = true;
12280b57cec5SDimitry Andric     bool AddEHEdges = false;
12290b57cec5SDimitry Andric     bool AddInitializers = false;
12300b57cec5SDimitry Andric     bool AddImplicitDtors = false;
12310b57cec5SDimitry Andric     bool AddLifetime = false;
12320b57cec5SDimitry Andric     bool AddLoopExit = false;
12330b57cec5SDimitry Andric     bool AddTemporaryDtors = false;
12340b57cec5SDimitry Andric     bool AddScopes = false;
12350b57cec5SDimitry Andric     bool AddStaticInitBranches = false;
12360b57cec5SDimitry Andric     bool AddCXXNewAllocator = false;
12370b57cec5SDimitry Andric     bool AddCXXDefaultInitExprInCtors = false;
1238480093f4SDimitry Andric     bool AddCXXDefaultInitExprInAggregates = false;
12390b57cec5SDimitry Andric     bool AddRichCXXConstructors = false;
12400b57cec5SDimitry Andric     bool MarkElidedCXXConstructors = false;
12410b57cec5SDimitry Andric     bool AddVirtualBaseBranches = false;
1242480093f4SDimitry Andric     bool OmitImplicitValueInitializers = false;
12430b57cec5SDimitry Andric 
12440b57cec5SDimitry Andric     BuildOptions() = default;
12450b57cec5SDimitry Andric 
alwaysAdd(const Stmt * stmt)12460b57cec5SDimitry Andric     bool alwaysAdd(const Stmt *stmt) const {
12470b57cec5SDimitry Andric       return alwaysAddMask[stmt->getStmtClass()];
12480b57cec5SDimitry Andric     }
12490b57cec5SDimitry Andric 
12500b57cec5SDimitry Andric     BuildOptions &setAlwaysAdd(Stmt::StmtClass stmtClass, bool val = true) {
12510b57cec5SDimitry Andric       alwaysAddMask[stmtClass] = val;
12520b57cec5SDimitry Andric       return *this;
12530b57cec5SDimitry Andric     }
12540b57cec5SDimitry Andric 
setAllAlwaysAdd()12550b57cec5SDimitry Andric     BuildOptions &setAllAlwaysAdd() {
12560b57cec5SDimitry Andric       alwaysAddMask.set();
12570b57cec5SDimitry Andric       return *this;
12580b57cec5SDimitry Andric     }
12590b57cec5SDimitry Andric   };
12600b57cec5SDimitry Andric 
12610b57cec5SDimitry Andric   /// Builds a CFG from an AST.
12620b57cec5SDimitry Andric   static std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *AST, ASTContext *C,
12630b57cec5SDimitry Andric                                        const BuildOptions &BO);
12640b57cec5SDimitry Andric 
12650b57cec5SDimitry Andric   /// Create a new block in the CFG. The CFG owns the block; the caller should
12660b57cec5SDimitry Andric   /// not directly free it.
12670b57cec5SDimitry Andric   CFGBlock *createBlock();
12680b57cec5SDimitry Andric 
12690b57cec5SDimitry Andric   /// Set the entry block of the CFG. This is typically used only during CFG
12700b57cec5SDimitry Andric   /// construction. Most CFG clients expect that the entry block has no
12710b57cec5SDimitry Andric   /// predecessors and contains no statements.
setEntry(CFGBlock * B)12720b57cec5SDimitry Andric   void setEntry(CFGBlock *B) { Entry = B; }
12730b57cec5SDimitry Andric 
12740b57cec5SDimitry Andric   /// Set the block used for indirect goto jumps. This is typically used only
12750b57cec5SDimitry Andric   /// during CFG construction.
setIndirectGotoBlock(CFGBlock * B)12760b57cec5SDimitry Andric   void setIndirectGotoBlock(CFGBlock *B) { IndirectGotoBlock = B; }
12770b57cec5SDimitry Andric 
12780b57cec5SDimitry Andric   //===--------------------------------------------------------------------===//
12790b57cec5SDimitry Andric   // Block Iterators
12800b57cec5SDimitry Andric   //===--------------------------------------------------------------------===//
12810b57cec5SDimitry Andric 
12820b57cec5SDimitry Andric   using CFGBlockListTy = BumpVector<CFGBlock *>;
12830b57cec5SDimitry Andric   using iterator = CFGBlockListTy::iterator;
12840b57cec5SDimitry Andric   using const_iterator = CFGBlockListTy::const_iterator;
12850b57cec5SDimitry Andric   using reverse_iterator = std::reverse_iterator<iterator>;
12860b57cec5SDimitry Andric   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
12870b57cec5SDimitry Andric 
front()12880b57cec5SDimitry Andric   CFGBlock &                front()                { return *Blocks.front(); }
back()12890b57cec5SDimitry Andric   CFGBlock &                back()                 { return *Blocks.back(); }
12900b57cec5SDimitry Andric 
begin()12910b57cec5SDimitry Andric   iterator                  begin()                { return Blocks.begin(); }
end()12920b57cec5SDimitry Andric   iterator                  end()                  { return Blocks.end(); }
begin()12930b57cec5SDimitry Andric   const_iterator            begin()       const    { return Blocks.begin(); }
end()12940b57cec5SDimitry Andric   const_iterator            end()         const    { return Blocks.end(); }
12950b57cec5SDimitry Andric 
nodes_begin()12960b57cec5SDimitry Andric   iterator nodes_begin() { return iterator(Blocks.begin()); }
nodes_end()12970b57cec5SDimitry Andric   iterator nodes_end() { return iterator(Blocks.end()); }
1298fe6060f1SDimitry Andric 
nodes()1299fe6060f1SDimitry Andric   llvm::iterator_range<iterator> nodes() { return {begin(), end()}; }
const_nodes()1300fe6060f1SDimitry Andric   llvm::iterator_range<const_iterator> const_nodes() const {
1301fe6060f1SDimitry Andric     return {begin(), end()};
1302fe6060f1SDimitry Andric   }
1303fe6060f1SDimitry Andric 
nodes_begin()13040b57cec5SDimitry Andric   const_iterator nodes_begin() const { return const_iterator(Blocks.begin()); }
nodes_end()13050b57cec5SDimitry Andric   const_iterator nodes_end() const { return const_iterator(Blocks.end()); }
13060b57cec5SDimitry Andric 
rbegin()13070b57cec5SDimitry Andric   reverse_iterator          rbegin()               { return Blocks.rbegin(); }
rend()13080b57cec5SDimitry Andric   reverse_iterator          rend()                 { return Blocks.rend(); }
rbegin()13090b57cec5SDimitry Andric   const_reverse_iterator    rbegin()      const    { return Blocks.rbegin(); }
rend()13100b57cec5SDimitry Andric   const_reverse_iterator    rend()        const    { return Blocks.rend(); }
13110b57cec5SDimitry Andric 
reverse_nodes()1312fe6060f1SDimitry Andric   llvm::iterator_range<reverse_iterator> reverse_nodes() {
1313fe6060f1SDimitry Andric     return {rbegin(), rend()};
1314fe6060f1SDimitry Andric   }
const_reverse_nodes()1315fe6060f1SDimitry Andric   llvm::iterator_range<const_reverse_iterator> const_reverse_nodes() const {
1316fe6060f1SDimitry Andric     return {rbegin(), rend()};
1317fe6060f1SDimitry Andric   }
1318fe6060f1SDimitry Andric 
getEntry()13190b57cec5SDimitry Andric   CFGBlock &                getEntry()             { return *Entry; }
getEntry()13200b57cec5SDimitry Andric   const CFGBlock &          getEntry()    const    { return *Entry; }
getExit()13210b57cec5SDimitry Andric   CFGBlock &                getExit()              { return *Exit; }
getExit()13220b57cec5SDimitry Andric   const CFGBlock &          getExit()     const    { return *Exit; }
13230b57cec5SDimitry Andric 
getIndirectGotoBlock()13240b57cec5SDimitry Andric   CFGBlock *       getIndirectGotoBlock() { return IndirectGotoBlock; }
getIndirectGotoBlock()13250b57cec5SDimitry Andric   const CFGBlock * getIndirectGotoBlock() const { return IndirectGotoBlock; }
13260b57cec5SDimitry Andric 
13270b57cec5SDimitry Andric   using try_block_iterator = std::vector<const CFGBlock *>::const_iterator;
1328349cc55cSDimitry Andric   using try_block_range = llvm::iterator_range<try_block_iterator>;
13290b57cec5SDimitry Andric 
try_blocks_begin()13300b57cec5SDimitry Andric   try_block_iterator try_blocks_begin() const {
13310b57cec5SDimitry Andric     return TryDispatchBlocks.begin();
13320b57cec5SDimitry Andric   }
13330b57cec5SDimitry Andric 
try_blocks_end()13340b57cec5SDimitry Andric   try_block_iterator try_blocks_end() const {
13350b57cec5SDimitry Andric     return TryDispatchBlocks.end();
13360b57cec5SDimitry Andric   }
13370b57cec5SDimitry Andric 
try_blocks()1338349cc55cSDimitry Andric   try_block_range try_blocks() const {
1339349cc55cSDimitry Andric     return try_block_range(try_blocks_begin(), try_blocks_end());
1340349cc55cSDimitry Andric   }
1341349cc55cSDimitry Andric 
addTryDispatchBlock(const CFGBlock * block)13420b57cec5SDimitry Andric   void addTryDispatchBlock(const CFGBlock *block) {
13430b57cec5SDimitry Andric     TryDispatchBlocks.push_back(block);
13440b57cec5SDimitry Andric   }
13450b57cec5SDimitry Andric 
13460b57cec5SDimitry Andric   /// Records a synthetic DeclStmt and the DeclStmt it was constructed from.
13470b57cec5SDimitry Andric   ///
13480b57cec5SDimitry Andric   /// The CFG uses synthetic DeclStmts when a single AST DeclStmt contains
13490b57cec5SDimitry Andric   /// multiple decls.
addSyntheticDeclStmt(const DeclStmt * Synthetic,const DeclStmt * Source)13500b57cec5SDimitry Andric   void addSyntheticDeclStmt(const DeclStmt *Synthetic,
13510b57cec5SDimitry Andric                             const DeclStmt *Source) {
13520b57cec5SDimitry Andric     assert(Synthetic->isSingleDecl() && "Can handle single declarations only");
13530b57cec5SDimitry Andric     assert(Synthetic != Source && "Don't include original DeclStmts in map");
13540b57cec5SDimitry Andric     assert(!SyntheticDeclStmts.count(Synthetic) && "Already in map");
13550b57cec5SDimitry Andric     SyntheticDeclStmts[Synthetic] = Source;
13560b57cec5SDimitry Andric   }
13570b57cec5SDimitry Andric 
13580b57cec5SDimitry Andric   using synthetic_stmt_iterator =
13590b57cec5SDimitry Andric       llvm::DenseMap<const DeclStmt *, const DeclStmt *>::const_iterator;
13600b57cec5SDimitry Andric   using synthetic_stmt_range = llvm::iterator_range<synthetic_stmt_iterator>;
13610b57cec5SDimitry Andric 
13620b57cec5SDimitry Andric   /// Iterates over synthetic DeclStmts in the CFG.
13630b57cec5SDimitry Andric   ///
13640b57cec5SDimitry Andric   /// Each element is a (synthetic statement, source statement) pair.
13650b57cec5SDimitry Andric   ///
13660b57cec5SDimitry Andric   /// \sa addSyntheticDeclStmt
synthetic_stmt_begin()13670b57cec5SDimitry Andric   synthetic_stmt_iterator synthetic_stmt_begin() const {
13680b57cec5SDimitry Andric     return SyntheticDeclStmts.begin();
13690b57cec5SDimitry Andric   }
13700b57cec5SDimitry Andric 
13710b57cec5SDimitry Andric   /// \sa synthetic_stmt_begin
synthetic_stmt_end()13720b57cec5SDimitry Andric   synthetic_stmt_iterator synthetic_stmt_end() const {
13730b57cec5SDimitry Andric     return SyntheticDeclStmts.end();
13740b57cec5SDimitry Andric   }
13750b57cec5SDimitry Andric 
13760b57cec5SDimitry Andric   /// \sa synthetic_stmt_begin
synthetic_stmts()13770b57cec5SDimitry Andric   synthetic_stmt_range synthetic_stmts() const {
13780b57cec5SDimitry Andric     return synthetic_stmt_range(synthetic_stmt_begin(), synthetic_stmt_end());
13790b57cec5SDimitry Andric   }
13800b57cec5SDimitry Andric 
13810b57cec5SDimitry Andric   //===--------------------------------------------------------------------===//
13820b57cec5SDimitry Andric   // Member templates useful for various batch operations over CFGs.
13830b57cec5SDimitry Andric   //===--------------------------------------------------------------------===//
13840b57cec5SDimitry Andric 
VisitBlockStmts(Callback & O)1385fe6060f1SDimitry Andric   template <typename Callback> void VisitBlockStmts(Callback &O) const {
13860b57cec5SDimitry Andric     for (const_iterator I = begin(), E = end(); I != E; ++I)
13870b57cec5SDimitry Andric       for (CFGBlock::const_iterator BI = (*I)->begin(), BE = (*I)->end();
13880b57cec5SDimitry Andric            BI != BE; ++BI) {
1389bdd1243dSDimitry Andric         if (std::optional<CFGStmt> stmt = BI->getAs<CFGStmt>())
13900b57cec5SDimitry Andric           O(const_cast<Stmt *>(stmt->getStmt()));
13910b57cec5SDimitry Andric       }
13920b57cec5SDimitry Andric   }
13930b57cec5SDimitry Andric 
13940b57cec5SDimitry Andric   //===--------------------------------------------------------------------===//
13950b57cec5SDimitry Andric   // CFG Introspection.
13960b57cec5SDimitry Andric   //===--------------------------------------------------------------------===//
13970b57cec5SDimitry Andric 
13980b57cec5SDimitry Andric   /// Returns the total number of BlockIDs allocated (which start at 0).
getNumBlockIDs()13990b57cec5SDimitry Andric   unsigned getNumBlockIDs() const { return NumBlockIDs; }
14000b57cec5SDimitry Andric 
14010b57cec5SDimitry Andric   /// Return the total number of CFGBlocks within the CFG This is simply a
14020b57cec5SDimitry Andric   /// renaming of the getNumBlockIDs(). This is necessary because the dominator
14030b57cec5SDimitry Andric   /// implementation needs such an interface.
size()14040b57cec5SDimitry Andric   unsigned size() const { return NumBlockIDs; }
14050b57cec5SDimitry Andric 
14060b57cec5SDimitry Andric   /// Returns true if the CFG has no branches. Usually it boils down to the CFG
14070b57cec5SDimitry Andric   /// having exactly three blocks (entry, the actual code, exit), but sometimes
14080b57cec5SDimitry Andric   /// more blocks appear due to having control flow that can be fully
14090b57cec5SDimitry Andric   /// resolved in compile time.
14100b57cec5SDimitry Andric   bool isLinear() const;
14110b57cec5SDimitry Andric 
14120b57cec5SDimitry Andric   //===--------------------------------------------------------------------===//
14130b57cec5SDimitry Andric   // CFG Debugging: Pretty-Printing and Visualization.
14140b57cec5SDimitry Andric   //===--------------------------------------------------------------------===//
14150b57cec5SDimitry Andric 
14160b57cec5SDimitry Andric   void viewCFG(const LangOptions &LO) const;
14170b57cec5SDimitry Andric   void print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const;
14180b57cec5SDimitry Andric   void dump(const LangOptions &LO, bool ShowColors) const;
14190b57cec5SDimitry Andric 
14200b57cec5SDimitry Andric   //===--------------------------------------------------------------------===//
14210b57cec5SDimitry Andric   // Internal: constructors and data.
14220b57cec5SDimitry Andric   //===--------------------------------------------------------------------===//
14230b57cec5SDimitry Andric 
CFG()14240b57cec5SDimitry Andric   CFG() : Blocks(BlkBVC, 10) {}
14250b57cec5SDimitry Andric 
getAllocator()14260b57cec5SDimitry Andric   llvm::BumpPtrAllocator& getAllocator() {
14270b57cec5SDimitry Andric     return BlkBVC.getAllocator();
14280b57cec5SDimitry Andric   }
14290b57cec5SDimitry Andric 
getBumpVectorContext()14300b57cec5SDimitry Andric   BumpVectorContext &getBumpVectorContext() {
14310b57cec5SDimitry Andric     return BlkBVC;
14320b57cec5SDimitry Andric   }
14330b57cec5SDimitry Andric 
14340b57cec5SDimitry Andric private:
14350b57cec5SDimitry Andric   CFGBlock *Entry = nullptr;
14360b57cec5SDimitry Andric   CFGBlock *Exit = nullptr;
14370b57cec5SDimitry Andric 
14380b57cec5SDimitry Andric   // Special block to contain collective dispatch for indirect gotos
14390b57cec5SDimitry Andric   CFGBlock* IndirectGotoBlock = nullptr;
14400b57cec5SDimitry Andric 
14410b57cec5SDimitry Andric   unsigned  NumBlockIDs = 0;
14420b57cec5SDimitry Andric 
14430b57cec5SDimitry Andric   BumpVectorContext BlkBVC;
14440b57cec5SDimitry Andric 
14450b57cec5SDimitry Andric   CFGBlockListTy Blocks;
14460b57cec5SDimitry Andric 
14470b57cec5SDimitry Andric   /// C++ 'try' statements are modeled with an indirect dispatch block.
14480b57cec5SDimitry Andric   /// This is the collection of such blocks present in the CFG.
14490b57cec5SDimitry Andric   std::vector<const CFGBlock *> TryDispatchBlocks;
14500b57cec5SDimitry Andric 
14510b57cec5SDimitry Andric   /// Collects DeclStmts synthesized for this CFG and maps each one back to its
14520b57cec5SDimitry Andric   /// source DeclStmt.
14530b57cec5SDimitry Andric   llvm::DenseMap<const DeclStmt *, const DeclStmt *> SyntheticDeclStmts;
14540b57cec5SDimitry Andric };
14550b57cec5SDimitry Andric 
1456bdd1243dSDimitry Andric Expr *extractElementInitializerFromNestedAILE(const ArrayInitLoopExpr *AILE);
1457bdd1243dSDimitry Andric 
14580b57cec5SDimitry Andric } // namespace clang
14590b57cec5SDimitry Andric 
14600b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
14610b57cec5SDimitry Andric // GraphTraits specializations for CFG basic block graphs (source-level CFGs)
14620b57cec5SDimitry Andric //===----------------------------------------------------------------------===//
14630b57cec5SDimitry Andric 
14640b57cec5SDimitry Andric namespace llvm {
14650b57cec5SDimitry Andric 
14660b57cec5SDimitry Andric /// Implement simplify_type for CFGTerminator, so that we can dyn_cast from
14670b57cec5SDimitry Andric /// CFGTerminator to a specific Stmt class.
14680b57cec5SDimitry Andric template <> struct simplify_type< ::clang::CFGTerminator> {
14690b57cec5SDimitry Andric   using SimpleType = ::clang::Stmt *;
14700b57cec5SDimitry Andric 
14710b57cec5SDimitry Andric   static SimpleType getSimplifiedValue(::clang::CFGTerminator Val) {
14720b57cec5SDimitry Andric     return Val.getStmt();
14730b57cec5SDimitry Andric   }
14740b57cec5SDimitry Andric };
14750b57cec5SDimitry Andric 
14760b57cec5SDimitry Andric // Traits for: CFGBlock
14770b57cec5SDimitry Andric 
14780b57cec5SDimitry Andric template <> struct GraphTraits< ::clang::CFGBlock *> {
14790b57cec5SDimitry Andric   using NodeRef = ::clang::CFGBlock *;
14800b57cec5SDimitry Andric   using ChildIteratorType = ::clang::CFGBlock::succ_iterator;
14810b57cec5SDimitry Andric 
14820b57cec5SDimitry Andric   static NodeRef getEntryNode(::clang::CFGBlock *BB) { return BB; }
14830b57cec5SDimitry Andric   static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
14840b57cec5SDimitry Andric   static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
14850b57cec5SDimitry Andric };
14860b57cec5SDimitry Andric 
14870b57cec5SDimitry Andric template <> struct GraphTraits< const ::clang::CFGBlock *> {
14880b57cec5SDimitry Andric   using NodeRef = const ::clang::CFGBlock *;
14890b57cec5SDimitry Andric   using ChildIteratorType = ::clang::CFGBlock::const_succ_iterator;
14900b57cec5SDimitry Andric 
14910b57cec5SDimitry Andric   static NodeRef getEntryNode(const clang::CFGBlock *BB) { return BB; }
14920b57cec5SDimitry Andric   static ChildIteratorType child_begin(NodeRef N) { return N->succ_begin(); }
14930b57cec5SDimitry Andric   static ChildIteratorType child_end(NodeRef N) { return N->succ_end(); }
14940b57cec5SDimitry Andric };
14950b57cec5SDimitry Andric 
14960b57cec5SDimitry Andric template <> struct GraphTraits<Inverse< ::clang::CFGBlock *>> {
14970b57cec5SDimitry Andric   using NodeRef = ::clang::CFGBlock *;
14980b57cec5SDimitry Andric   using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator;
14990b57cec5SDimitry Andric 
15000b57cec5SDimitry Andric   static NodeRef getEntryNode(Inverse<::clang::CFGBlock *> G) {
15010b57cec5SDimitry Andric     return G.Graph;
15020b57cec5SDimitry Andric   }
15030b57cec5SDimitry Andric 
15040b57cec5SDimitry Andric   static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
15050b57cec5SDimitry Andric   static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
15060b57cec5SDimitry Andric };
15070b57cec5SDimitry Andric 
15080b57cec5SDimitry Andric template <> struct GraphTraits<Inverse<const ::clang::CFGBlock *>> {
15090b57cec5SDimitry Andric   using NodeRef = const ::clang::CFGBlock *;
15100b57cec5SDimitry Andric   using ChildIteratorType = ::clang::CFGBlock::const_pred_iterator;
15110b57cec5SDimitry Andric 
15120b57cec5SDimitry Andric   static NodeRef getEntryNode(Inverse<const ::clang::CFGBlock *> G) {
15130b57cec5SDimitry Andric     return G.Graph;
15140b57cec5SDimitry Andric   }
15150b57cec5SDimitry Andric 
15160b57cec5SDimitry Andric   static ChildIteratorType child_begin(NodeRef N) { return N->pred_begin(); }
15170b57cec5SDimitry Andric   static ChildIteratorType child_end(NodeRef N) { return N->pred_end(); }
15180b57cec5SDimitry Andric };
15190b57cec5SDimitry Andric 
15200b57cec5SDimitry Andric // Traits for: CFG
15210b57cec5SDimitry Andric 
15220b57cec5SDimitry Andric template <> struct GraphTraits< ::clang::CFG* >
15230b57cec5SDimitry Andric     : public GraphTraits< ::clang::CFGBlock *>  {
15240b57cec5SDimitry Andric   using nodes_iterator = ::clang::CFG::iterator;
15250b57cec5SDimitry Andric 
15260b57cec5SDimitry Andric   static NodeRef getEntryNode(::clang::CFG *F) { return &F->getEntry(); }
15270b57cec5SDimitry Andric   static nodes_iterator nodes_begin(::clang::CFG* F) { return F->nodes_begin();}
15280b57cec5SDimitry Andric   static nodes_iterator   nodes_end(::clang::CFG* F) { return F->nodes_end(); }
15290b57cec5SDimitry Andric   static unsigned              size(::clang::CFG* F) { return F->size(); }
15300b57cec5SDimitry Andric };
15310b57cec5SDimitry Andric 
15320b57cec5SDimitry Andric template <> struct GraphTraits<const ::clang::CFG* >
15330b57cec5SDimitry Andric     : public GraphTraits<const ::clang::CFGBlock *>  {
15340b57cec5SDimitry Andric   using nodes_iterator = ::clang::CFG::const_iterator;
15350b57cec5SDimitry Andric 
15360b57cec5SDimitry Andric   static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getEntry(); }
15370b57cec5SDimitry Andric 
15380b57cec5SDimitry Andric   static nodes_iterator nodes_begin( const ::clang::CFG* F) {
15390b57cec5SDimitry Andric     return F->nodes_begin();
15400b57cec5SDimitry Andric   }
15410b57cec5SDimitry Andric 
15420b57cec5SDimitry Andric   static nodes_iterator nodes_end( const ::clang::CFG* F) {
15430b57cec5SDimitry Andric     return F->nodes_end();
15440b57cec5SDimitry Andric   }
15450b57cec5SDimitry Andric 
15460b57cec5SDimitry Andric   static unsigned size(const ::clang::CFG* F) {
15470b57cec5SDimitry Andric     return F->size();
15480b57cec5SDimitry Andric   }
15490b57cec5SDimitry Andric };
15500b57cec5SDimitry Andric 
15510b57cec5SDimitry Andric template <> struct GraphTraits<Inverse< ::clang::CFG *>>
15520b57cec5SDimitry Andric   : public GraphTraits<Inverse< ::clang::CFGBlock *>> {
15530b57cec5SDimitry Andric   using nodes_iterator = ::clang::CFG::iterator;
15540b57cec5SDimitry Andric 
15550b57cec5SDimitry Andric   static NodeRef getEntryNode(::clang::CFG *F) { return &F->getExit(); }
15560b57cec5SDimitry Andric   static nodes_iterator nodes_begin( ::clang::CFG* F) {return F->nodes_begin();}
15570b57cec5SDimitry Andric   static nodes_iterator nodes_end( ::clang::CFG* F) { return F->nodes_end(); }
15580b57cec5SDimitry Andric };
15590b57cec5SDimitry Andric 
15600b57cec5SDimitry Andric template <> struct GraphTraits<Inverse<const ::clang::CFG *>>
15610b57cec5SDimitry Andric   : public GraphTraits<Inverse<const ::clang::CFGBlock *>> {
15620b57cec5SDimitry Andric   using nodes_iterator = ::clang::CFG::const_iterator;
15630b57cec5SDimitry Andric 
15640b57cec5SDimitry Andric   static NodeRef getEntryNode(const ::clang::CFG *F) { return &F->getExit(); }
15650b57cec5SDimitry Andric 
15660b57cec5SDimitry Andric   static nodes_iterator nodes_begin(const ::clang::CFG* F) {
15670b57cec5SDimitry Andric     return F->nodes_begin();
15680b57cec5SDimitry Andric   }
15690b57cec5SDimitry Andric 
15700b57cec5SDimitry Andric   static nodes_iterator nodes_end(const ::clang::CFG* F) {
15710b57cec5SDimitry Andric     return F->nodes_end();
15720b57cec5SDimitry Andric   }
15730b57cec5SDimitry Andric };
15740b57cec5SDimitry Andric 
15750b57cec5SDimitry Andric } // namespace llvm
15760b57cec5SDimitry Andric 
15770b57cec5SDimitry Andric #endif // LLVM_CLANG_ANALYSIS_CFG_H
1578