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