| //===- CFG.cpp - Classes for representing and building CFGs ---------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file defines the CFG and CFGBuilder classes for representing and |
| // building Control-Flow Graphs (CFGs) from ASTs. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "clang/Analysis/CFG.h" |
| #include "clang/AST/ASTContext.h" |
| #include "clang/AST/Attr.h" |
| #include "clang/AST/Decl.h" |
| #include "clang/AST/DeclBase.h" |
| #include "clang/AST/DeclCXX.h" |
| #include "clang/AST/DeclGroup.h" |
| #include "clang/AST/Expr.h" |
| #include "clang/AST/ExprCXX.h" |
| #include "clang/AST/OperationKinds.h" |
| #include "clang/AST/PrettyPrinter.h" |
| #include "clang/AST/Stmt.h" |
| #include "clang/AST/StmtCXX.h" |
| #include "clang/AST/StmtObjC.h" |
| #include "clang/AST/StmtVisitor.h" |
| #include "clang/AST/Type.h" |
| #include "clang/Analysis/ConstructionContext.h" |
| #include "clang/Analysis/Support/BumpVector.h" |
| #include "clang/Basic/Builtins.h" |
| #include "clang/Basic/ExceptionSpecificationType.h" |
| #include "clang/Basic/JsonSupport.h" |
| #include "clang/Basic/LLVM.h" |
| #include "clang/Basic/LangOptions.h" |
| #include "clang/Basic/SourceLocation.h" |
| #include "clang/Basic/Specifiers.h" |
| #include "llvm/ADT/APInt.h" |
| #include "llvm/ADT/APSInt.h" |
| #include "llvm/ADT/ArrayRef.h" |
| #include "llvm/ADT/DenseMap.h" |
| #include "llvm/ADT/Optional.h" |
| #include "llvm/ADT/STLExtras.h" |
| #include "llvm/ADT/SetVector.h" |
| #include "llvm/ADT/SmallPtrSet.h" |
| #include "llvm/ADT/SmallVector.h" |
| #include "llvm/Support/Allocator.h" |
| #include "llvm/Support/Casting.h" |
| #include "llvm/Support/Compiler.h" |
| #include "llvm/Support/DOTGraphTraits.h" |
| #include "llvm/Support/ErrorHandling.h" |
| #include "llvm/Support/Format.h" |
| #include "llvm/Support/GraphWriter.h" |
| #include "llvm/Support/SaveAndRestore.h" |
| #include "llvm/Support/raw_ostream.h" |
| #include <cassert> |
| #include <memory> |
| #include <string> |
| #include <tuple> |
| #include <utility> |
| #include <vector> |
| |
| using namespace clang; |
| |
| static SourceLocation GetEndLoc(Decl *D) { |
| if (VarDecl *VD = dyn_cast<VarDecl>(D)) |
| if (Expr *Ex = VD->getInit()) |
| return Ex->getSourceRange().getEnd(); |
| return D->getLocation(); |
| } |
| |
| /// Returns true on constant values based around a single IntegerLiteral. |
| /// Allow for use of parentheses, integer casts, and negative signs. |
| static bool IsIntegerLiteralConstantExpr(const Expr *E) { |
| // Allow parentheses |
| E = E->IgnoreParens(); |
| |
| // Allow conversions to different integer kind. |
| if (const auto *CE = dyn_cast<CastExpr>(E)) { |
| if (CE->getCastKind() != CK_IntegralCast) |
| return false; |
| E = CE->getSubExpr(); |
| } |
| |
| // Allow negative numbers. |
| if (const auto *UO = dyn_cast<UnaryOperator>(E)) { |
| if (UO->getOpcode() != UO_Minus) |
| return false; |
| E = UO->getSubExpr(); |
| } |
| |
| return isa<IntegerLiteral>(E); |
| } |
| |
| /// Helper for tryNormalizeBinaryOperator. Attempts to extract an IntegerLiteral |
| /// constant expression or EnumConstantDecl from the given Expr. If it fails, |
| /// returns nullptr. |
| static const Expr *tryTransformToIntOrEnumConstant(const Expr *E) { |
| E = E->IgnoreParens(); |
| if (IsIntegerLiteralConstantExpr(E)) |
| return E; |
| if (auto *DR = dyn_cast<DeclRefExpr>(E->IgnoreParenImpCasts())) |
| return isa<EnumConstantDecl>(DR->getDecl()) ? DR : nullptr; |
| return nullptr; |
| } |
| |
| /// Tries to interpret a binary operator into `Expr Op NumExpr` form, if |
| /// NumExpr is an integer literal or an enum constant. |
| /// |
| /// If this fails, at least one of the returned DeclRefExpr or Expr will be |
| /// null. |
| static std::tuple<const Expr *, BinaryOperatorKind, const Expr *> |
| tryNormalizeBinaryOperator(const BinaryOperator *B) { |
| BinaryOperatorKind Op = B->getOpcode(); |
| |
| const Expr *MaybeDecl = B->getLHS(); |
| const Expr *Constant = tryTransformToIntOrEnumConstant(B->getRHS()); |
| // Expr looked like `0 == Foo` instead of `Foo == 0` |
| if (Constant == nullptr) { |
| // Flip the operator |
| if (Op == BO_GT) |
| Op = BO_LT; |
| else if (Op == BO_GE) |
| Op = BO_LE; |
| else if (Op == BO_LT) |
| Op = BO_GT; |
| else if (Op == BO_LE) |
| Op = BO_GE; |
| |
| MaybeDecl = B->getRHS(); |
| Constant = tryTransformToIntOrEnumConstant(B->getLHS()); |
| } |
| |
| return std::make_tuple(MaybeDecl, Op, Constant); |
| } |
| |
| /// For an expression `x == Foo && x == Bar`, this determines whether the |
| /// `Foo` and `Bar` are either of the same enumeration type, or both integer |
| /// literals. |
| /// |
| /// It's an error to pass this arguments that are not either IntegerLiterals |
| /// or DeclRefExprs (that have decls of type EnumConstantDecl) |
| static bool areExprTypesCompatible(const Expr *E1, const Expr *E2) { |
| // User intent isn't clear if they're mixing int literals with enum |
| // constants. |
| if (isa<DeclRefExpr>(E1) != isa<DeclRefExpr>(E2)) |
| return false; |
| |
| // Integer literal comparisons, regardless of literal type, are acceptable. |
| if (!isa<DeclRefExpr>(E1)) |
| return true; |
| |
| // IntegerLiterals are handled above and only EnumConstantDecls are expected |
| // beyond this point |
| assert(isa<DeclRefExpr>(E1) && isa<DeclRefExpr>(E2)); |
| auto *Decl1 = cast<DeclRefExpr>(E1)->getDecl(); |
| auto *Decl2 = cast<DeclRefExpr>(E2)->getDecl(); |
| |
| assert(isa<EnumConstantDecl>(Decl1) && isa<EnumConstantDecl>(Decl2)); |
| const DeclContext *DC1 = Decl1->getDeclContext(); |
| const DeclContext *DC2 = Decl2->getDeclContext(); |
| |
| assert(isa<EnumDecl>(DC1) && isa<EnumDecl>(DC2)); |
| return DC1 == DC2; |
| } |
| |
| namespace { |
| |
| class CFGBuilder; |
| |
| /// The CFG builder uses a recursive algorithm to build the CFG. When |
| /// we process an expression, sometimes we know that we must add the |
| /// subexpressions as block-level expressions. For example: |
| /// |
| /// exp1 || exp2 |
| /// |
| /// When processing the '||' expression, we know that exp1 and exp2 |
| /// need to be added as block-level expressions, even though they |
| /// might not normally need to be. AddStmtChoice records this |
| /// contextual information. If AddStmtChoice is 'NotAlwaysAdd', then |
| /// the builder has an option not to add a subexpression as a |
| /// block-level expression. |
| class AddStmtChoice { |
| public: |
| enum Kind { NotAlwaysAdd = 0, AlwaysAdd = 1 }; |
| |
| AddStmtChoice(Kind a_kind = NotAlwaysAdd) : kind(a_kind) {} |
| |
| bool alwaysAdd(CFGBuilder &builder, |
| const Stmt *stmt) const; |
| |
| /// Return a copy of this object, except with the 'always-add' bit |
| /// set as specified. |
| AddStmtChoice withAlwaysAdd(bool alwaysAdd) const { |
| return AddStmtChoice(alwaysAdd ? AlwaysAdd : NotAlwaysAdd); |
| } |
| |
| private: |
| Kind kind; |
| }; |
| |
| /// LocalScope - Node in tree of local scopes created for C++ implicit |
| /// destructor calls generation. It contains list of automatic variables |
| /// declared in the scope and link to position in previous scope this scope |
| /// began in. |
| /// |
| /// The process of creating local scopes is as follows: |
| /// - Init CFGBuilder::ScopePos with invalid position (equivalent for null), |
| /// - Before processing statements in scope (e.g. CompoundStmt) create |
| /// LocalScope object using CFGBuilder::ScopePos as link to previous scope |
| /// and set CFGBuilder::ScopePos to the end of new scope, |
| /// - On every occurrence of VarDecl increase CFGBuilder::ScopePos if it points |
| /// at this VarDecl, |
| /// - For every normal (without jump) end of scope add to CFGBlock destructors |
| /// for objects in the current scope, |
| /// - For every jump add to CFGBlock destructors for objects |
| /// between CFGBuilder::ScopePos and local scope position saved for jump |
| /// target. Thanks to C++ restrictions on goto jumps we can be sure that |
| /// jump target position will be on the path to root from CFGBuilder::ScopePos |
| /// (adding any variable that doesn't need constructor to be called to |
| /// LocalScope can break this assumption), |
| /// |
| class LocalScope { |
| public: |
| friend class const_iterator; |
| |
| using AutomaticVarsTy = BumpVector<VarDecl *>; |
| |
| /// const_iterator - Iterates local scope backwards and jumps to previous |
| /// scope on reaching the beginning of currently iterated scope. |
| class const_iterator { |
| const LocalScope* Scope = nullptr; |
| |
| /// VarIter is guaranteed to be greater then 0 for every valid iterator. |
| /// Invalid iterator (with null Scope) has VarIter equal to 0. |
| unsigned VarIter = 0; |
| |
| public: |
| /// Create invalid iterator. Dereferencing invalid iterator is not allowed. |
| /// Incrementing invalid iterator is allowed and will result in invalid |
| /// iterator. |
| const_iterator() = default; |
| |
| /// Create valid iterator. In case when S.Prev is an invalid iterator and |
| /// I is equal to 0, this will create invalid iterator. |
| const_iterator(const LocalScope& S, unsigned I) |
| : Scope(&S), VarIter(I) { |
| // Iterator to "end" of scope is not allowed. Handle it by going up |
| // in scopes tree possibly up to invalid iterator in the root. |
| if (VarIter == 0 && Scope) |
| *this = Scope->Prev; |
| } |
| |
| VarDecl *const* operator->() const { |
| assert(Scope && "Dereferencing invalid iterator is not allowed"); |
| assert(VarIter != 0 && "Iterator has invalid value of VarIter member"); |
| return &Scope->Vars[VarIter - 1]; |
| } |
| |
| const VarDecl *getFirstVarInScope() const { |
| assert(Scope && "Dereferencing invalid iterator is not allowed"); |
| assert(VarIter != 0 && "Iterator has invalid value of VarIter member"); |
| return Scope->Vars[0]; |
| } |
| |
| VarDecl *operator*() const { |
| return *this->operator->(); |
| } |
| |
| const_iterator &operator++() { |
| if (!Scope) |
| return *this; |
| |
| assert(VarIter != 0 && "Iterator has invalid value of VarIter member"); |
| --VarIter; |
| if (VarIter == 0) |
| *this = Scope->Prev; |
| return *this; |
| } |
| const_iterator operator++(int) { |
| const_iterator P = *this; |
| ++*this; |
| return P; |
| } |
| |
| bool operator==(const const_iterator &rhs) const { |
| return Scope == rhs.Scope && VarIter == rhs.VarIter; |
| } |
| bool operator!=(const const_iterator &rhs) const { |
| return !(*this == rhs); |
| } |
| |
| explicit operator bool() const { |
| return *this != const_iterator(); |
| } |
| |
| int distance(const_iterator L); |
| const_iterator shared_parent(const_iterator L); |
| bool pointsToFirstDeclaredVar() { return VarIter == 1; } |
| }; |
| |
| private: |
| BumpVectorContext ctx; |
| |
| /// Automatic variables in order of declaration. |
| AutomaticVarsTy Vars; |
| |
| /// Iterator to variable in previous scope that was declared just before |
| /// begin of this scope. |
| const_iterator Prev; |
| |
| public: |
| /// Constructs empty scope linked to previous scope in specified place. |
| LocalScope(BumpVectorContext ctx, const_iterator P) |
| : ctx(std::move(ctx)), Vars(this->ctx, 4), Prev(P) {} |
| |
| /// Begin of scope in direction of CFG building (backwards). |
| const_iterator begin() const { return const_iterator(*this, Vars.size()); } |
| |
| void addVar(VarDecl *VD) { |
| Vars.push_back(VD, ctx); |
| } |
| }; |
| |
| } // namespace |
| |
| /// distance - Calculates distance from this to L. L must be reachable from this |
| /// (with use of ++ operator). Cost of calculating the distance is linear w.r.t. |
| /// number of scopes between this and L. |
| int LocalScope::const_iterator::distance(LocalScope::const_iterator L) { |
| int D = 0; |
| const_iterator F = *this; |
| while (F.Scope != L.Scope) { |
| assert(F != const_iterator() && |
| "L iterator is not reachable from F iterator."); |
| D += F.VarIter; |
| F = F.Scope->Prev; |
| } |
| D += F.VarIter - L.VarIter; |
| return D; |
| } |
| |
| /// Calculates the closest parent of this iterator |
| /// that is in a scope reachable through the parents of L. |
| /// I.e. when using 'goto' from this to L, the lifetime of all variables |
| /// between this and shared_parent(L) end. |
| LocalScope::const_iterator |
| LocalScope::const_iterator::shared_parent(LocalScope::const_iterator L) { |
| llvm::SmallPtrSet<const LocalScope *, 4> ScopesOfL; |
| while (true) { |
| ScopesOfL.insert(L.Scope); |
| if (L == const_iterator()) |
| break; |
| L = L.Scope->Prev; |
| } |
| |
| const_iterator F = *this; |
| while (true) { |
| if (ScopesOfL.count(F.Scope)) |
| return F; |
| assert(F != const_iterator() && |
| "L iterator is not reachable from F iterator."); |
| F = F.Scope->Prev; |
| } |
| } |
| |
| namespace { |
| |
| /// Structure for specifying position in CFG during its build process. It |
| /// consists of CFGBlock that specifies position in CFG and |
| /// LocalScope::const_iterator that specifies position in LocalScope graph. |
| struct BlockScopePosPair { |
| CFGBlock *block = nullptr; |
| LocalScope::const_iterator scopePosition; |
| |
| BlockScopePosPair() = default; |
| BlockScopePosPair(CFGBlock *b, LocalScope::const_iterator scopePos) |
| : block(b), scopePosition(scopePos) {} |
| }; |
| |
| /// TryResult - a class representing a variant over the values |
| /// 'true', 'false', or 'unknown'. This is returned by tryEvaluateBool, |
| /// and is used by the CFGBuilder to decide if a branch condition |
| /// can be decided up front during CFG construction. |
| class TryResult { |
| int X = -1; |
| |
| public: |
| TryResult() = default; |
| TryResult(bool b) : X(b ? 1 : 0) {} |
| |
| bool isTrue() const { return X == 1; } |
| bool isFalse() const { return X == 0; } |
| bool isKnown() const { return X >= 0; } |
| |
| void negate() { |
| assert(isKnown()); |
| X ^= 0x1; |
| } |
| }; |
| |
| } // namespace |
| |
| static TryResult bothKnownTrue(TryResult R1, TryResult R2) { |
| if (!R1.isKnown() || !R2.isKnown()) |
| return TryResult(); |
| return TryResult(R1.isTrue() && R2.isTrue()); |
| } |
| |
| namespace { |
| |
| class reverse_children { |
| llvm::SmallVector<Stmt *, 12> childrenBuf; |
| ArrayRef<Stmt *> children; |
| |
| public: |
| reverse_children(Stmt *S); |
| |
| using iterator = ArrayRef<Stmt *>::reverse_iterator; |
| |
| iterator begin() const { return children.rbegin(); } |
| iterator end() const { return children.rend(); } |
| }; |
| |
| } // namespace |
| |
| reverse_children::reverse_children(Stmt *S) { |
| if (CallExpr *CE = dyn_cast<CallExpr>(S)) { |
| children = CE->getRawSubExprs(); |
| return; |
| } |
| switch (S->getStmtClass()) { |
| // Note: Fill in this switch with more cases we want to optimize. |
| case Stmt::InitListExprClass: { |
| InitListExpr *IE = cast<InitListExpr>(S); |
| children = llvm::makeArrayRef(reinterpret_cast<Stmt**>(IE->getInits()), |
| IE->getNumInits()); |
| return; |
| } |
| default: |
| break; |
| } |
| |
| // Default case for all other statements. |
| for (Stmt *SubStmt : S->children()) |
| childrenBuf.push_back(SubStmt); |
| |
| // This needs to be done *after* childrenBuf has been populated. |
| children = childrenBuf; |
| } |
| |
| namespace { |
| |
| /// CFGBuilder - This class implements CFG construction from an AST. |
| /// The builder is stateful: an instance of the builder should be used to only |
| /// construct a single CFG. |
| /// |
| /// Example usage: |
| /// |
| /// CFGBuilder builder; |
| /// std::unique_ptr<CFG> cfg = builder.buildCFG(decl, stmt1); |
| /// |
| /// CFG construction is done via a recursive walk of an AST. We actually parse |
| /// the AST in reverse order so that the successor of a basic block is |
| /// constructed prior to its predecessor. This allows us to nicely capture |
| /// implicit fall-throughs without extra basic blocks. |
| class CFGBuilder { |
| using JumpTarget = BlockScopePosPair; |
| using JumpSource = BlockScopePosPair; |
| |
| ASTContext *Context; |
| std::unique_ptr<CFG> cfg; |
| |
| // Current block. |
| CFGBlock *Block = nullptr; |
| |
| // Block after the current block. |
| CFGBlock *Succ = nullptr; |
| |
| JumpTarget ContinueJumpTarget; |
| JumpTarget BreakJumpTarget; |
| JumpTarget SEHLeaveJumpTarget; |
| CFGBlock *SwitchTerminatedBlock = nullptr; |
| CFGBlock *DefaultCaseBlock = nullptr; |
| |
| // This can point either to a try or a __try block. The frontend forbids |
| // mixing both kinds in one function, so having one for both is enough. |
| CFGBlock *TryTerminatedBlock = nullptr; |
| |
| // Current position in local scope. |
| LocalScope::const_iterator ScopePos; |
| |
| // LabelMap records the mapping from Label expressions to their jump targets. |
| using LabelMapTy = llvm::DenseMap<LabelDecl *, JumpTarget>; |
| LabelMapTy LabelMap; |
| |
| // A list of blocks that end with a "goto" that must be backpatched to their |
| // resolved targets upon completion of CFG construction. |
| using BackpatchBlocksTy = std::vector<JumpSource>; |
| BackpatchBlocksTy BackpatchBlocks; |
| |
| // A list of labels whose address has been taken (for indirect gotos). |
| using LabelSetTy = llvm::SmallSetVector<LabelDecl *, 8>; |
| LabelSetTy AddressTakenLabels; |
| |
| // Information about the currently visited C++ object construction site. |
| // This is set in the construction trigger and read when the constructor |
| // or a function that returns an object by value is being visited. |
| llvm::DenseMap<Expr *, const ConstructionContextLayer *> |
| ConstructionContextMap; |
| |
| using DeclsWithEndedScopeSetTy = llvm::SmallSetVector<VarDecl *, 16>; |
| DeclsWithEndedScopeSetTy DeclsWithEndedScope; |
| |
| bool badCFG = false; |
| const CFG::BuildOptions &BuildOpts; |
| |
| // State to track for building switch statements. |
| bool switchExclusivelyCovered = false; |
| Expr::EvalResult *switchCond = nullptr; |
| |
| CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry = nullptr; |
| const Stmt *lastLookup = nullptr; |
| |
| // Caches boolean evaluations of expressions to avoid multiple re-evaluations |
| // during construction of branches for chained logical operators. |
| using CachedBoolEvalsTy = llvm::DenseMap<Expr *, TryResult>; |
| CachedBoolEvalsTy CachedBoolEvals; |
| |
| public: |
| explicit CFGBuilder(ASTContext *astContext, |
| const CFG::BuildOptions &buildOpts) |
| : Context(astContext), cfg(new CFG()), // crew a new CFG |
| ConstructionContextMap(), BuildOpts(buildOpts) {} |
| |
| |
| // buildCFG - Used by external clients to construct the CFG. |
| std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *Statement); |
| |
| bool alwaysAdd(const Stmt *stmt); |
| |
| private: |
| // Visitors to walk an AST and construct the CFG. |
| CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc); |
| CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc); |
| CFGBlock *VisitBreakStmt(BreakStmt *B); |
| CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc); |
| CFGBlock *VisitCaseStmt(CaseStmt *C); |
| CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc); |
| CFGBlock *VisitCompoundStmt(CompoundStmt *C, bool ExternallyDestructed); |
| CFGBlock *VisitConditionalOperator(AbstractConditionalOperator *C, |
| AddStmtChoice asc); |
| CFGBlock *VisitContinueStmt(ContinueStmt *C); |
| CFGBlock *VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E, |
| AddStmtChoice asc); |
| CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S); |
| CFGBlock *VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc); |
| CFGBlock *VisitCXXNewExpr(CXXNewExpr *DE, AddStmtChoice asc); |
| CFGBlock *VisitCXXDeleteExpr(CXXDeleteExpr *DE, AddStmtChoice asc); |
| CFGBlock *VisitCXXForRangeStmt(CXXForRangeStmt *S); |
| CFGBlock *VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E, |
| AddStmtChoice asc); |
| CFGBlock *VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C, |
| AddStmtChoice asc); |
| CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T); |
| CFGBlock *VisitCXXTryStmt(CXXTryStmt *S); |
| CFGBlock *VisitDeclStmt(DeclStmt *DS); |
| CFGBlock *VisitDeclSubExpr(DeclStmt *DS); |
| CFGBlock *VisitDefaultStmt(DefaultStmt *D); |
| CFGBlock *VisitDoStmt(DoStmt *D); |
| CFGBlock *VisitExprWithCleanups(ExprWithCleanups *E, |
| AddStmtChoice asc, bool ExternallyDestructed); |
| CFGBlock *VisitForStmt(ForStmt *F); |
| CFGBlock *VisitGotoStmt(GotoStmt *G); |
| CFGBlock *VisitGCCAsmStmt(GCCAsmStmt *G, AddStmtChoice asc); |
| CFGBlock *VisitIfStmt(IfStmt *I); |
| CFGBlock *VisitImplicitCastExpr(ImplicitCastExpr *E, AddStmtChoice asc); |
| CFGBlock *VisitConstantExpr(ConstantExpr *E, AddStmtChoice asc); |
| CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I); |
| CFGBlock *VisitLabelStmt(LabelStmt *L); |
| CFGBlock *VisitBlockExpr(BlockExpr *E, AddStmtChoice asc); |
| CFGBlock *VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc); |
| CFGBlock *VisitLogicalOperator(BinaryOperator *B); |
| std::pair<CFGBlock *, CFGBlock *> VisitLogicalOperator(BinaryOperator *B, |
| Stmt *Term, |
| CFGBlock *TrueBlock, |
| CFGBlock *FalseBlock); |
| CFGBlock *VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE, |
| AddStmtChoice asc); |
| CFGBlock *VisitMemberExpr(MemberExpr *M, AddStmtChoice asc); |
| CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S); |
| CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S); |
| CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S); |
| CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S); |
| CFGBlock *VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S); |
| CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S); |
| CFGBlock *VisitObjCMessageExpr(ObjCMessageExpr *E, AddStmtChoice asc); |
| CFGBlock *VisitPseudoObjectExpr(PseudoObjectExpr *E); |
| CFGBlock *VisitReturnStmt(Stmt *S); |
| CFGBlock *VisitSEHExceptStmt(SEHExceptStmt *S); |
| CFGBlock *VisitSEHFinallyStmt(SEHFinallyStmt *S); |
| CFGBlock *VisitSEHLeaveStmt(SEHLeaveStmt *S); |
| CFGBlock *VisitSEHTryStmt(SEHTryStmt *S); |
| CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc); |
| CFGBlock *VisitSwitchStmt(SwitchStmt *S); |
| CFGBlock *VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E, |
| AddStmtChoice asc); |
| CFGBlock *VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc); |
| CFGBlock *VisitWhileStmt(WhileStmt *W); |
| |
| CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd, |
| bool ExternallyDestructed = false); |
| CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc); |
| CFGBlock *VisitChildren(Stmt *S); |
| CFGBlock *VisitNoRecurse(Expr *E, AddStmtChoice asc); |
| CFGBlock *VisitOMPExecutableDirective(OMPExecutableDirective *D, |
| AddStmtChoice asc); |
| |
| void maybeAddScopeBeginForVarDecl(CFGBlock *B, const VarDecl *VD, |
| const Stmt *S) { |
| if (ScopePos && (VD == ScopePos.getFirstVarInScope())) |
| appendScopeBegin(B, VD, S); |
| } |
| |
| /// When creating the CFG for temporary destructors, we want to mirror the |
| /// branch structure of the corresponding constructor calls. |
| /// Thus, while visiting a statement for temporary destructors, we keep a |
| /// context to keep track of the following information: |
| /// - whether a subexpression is executed unconditionally |
| /// - if a subexpression is executed conditionally, the first |
| /// CXXBindTemporaryExpr we encounter in that subexpression (which |
| /// corresponds to the last temporary destructor we have to call for this |
| /// subexpression) and the CFG block at that point (which will become the |
| /// successor block when inserting the decision point). |
| /// |
| /// That way, we can build the branch structure for temporary destructors as |
| /// follows: |
| /// 1. If a subexpression is executed unconditionally, we add the temporary |
| /// destructor calls to the current block. |
| /// 2. If a subexpression is executed conditionally, when we encounter a |
| /// CXXBindTemporaryExpr: |
| /// a) If it is the first temporary destructor call in the subexpression, |
| /// we remember the CXXBindTemporaryExpr and the current block in the |
| /// TempDtorContext; we start a new block, and insert the temporary |
| /// destructor call. |
| /// b) Otherwise, add the temporary destructor call to the current block. |
| /// 3. When we finished visiting a conditionally executed subexpression, |
| /// and we found at least one temporary constructor during the visitation |
| /// (2.a has executed), we insert a decision block that uses the |
| /// CXXBindTemporaryExpr as terminator, and branches to the current block |
| /// if the CXXBindTemporaryExpr was marked executed, and otherwise |
| /// branches to the stored successor. |
| struct TempDtorContext { |
| TempDtorContext() = default; |
| TempDtorContext(TryResult KnownExecuted) |
| : IsConditional(true), KnownExecuted(KnownExecuted) {} |
| |
| /// Returns whether we need to start a new branch for a temporary destructor |
| /// call. This is the case when the temporary destructor is |
| /// conditionally executed, and it is the first one we encounter while |
| /// visiting a subexpression - other temporary destructors at the same level |
| /// will be added to the same block and are executed under the same |
| /// condition. |
| bool needsTempDtorBranch() const { |
| return IsConditional && !TerminatorExpr; |
| } |
| |
| /// Remember the successor S of a temporary destructor decision branch for |
| /// the corresponding CXXBindTemporaryExpr E. |
| void setDecisionPoint(CFGBlock *S, CXXBindTemporaryExpr *E) { |
| Succ = S; |
| TerminatorExpr = E; |
| } |
| |
| const bool IsConditional = false; |
| const TryResult KnownExecuted = true; |
| CFGBlock *Succ = nullptr; |
| CXXBindTemporaryExpr *TerminatorExpr = nullptr; |
| }; |
| |
| // Visitors to walk an AST and generate destructors of temporaries in |
| // full expression. |
| CFGBlock *VisitForTemporaryDtors(Stmt *E, bool ExternallyDestructed, |
| TempDtorContext &Context); |
| CFGBlock *VisitChildrenForTemporaryDtors(Stmt *E, bool ExternallyDestructed, |
| TempDtorContext &Context); |
| CFGBlock *VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E, |
| bool ExternallyDestructed, |
| TempDtorContext &Context); |
| CFGBlock *VisitCXXBindTemporaryExprForTemporaryDtors( |
| CXXBindTemporaryExpr *E, bool ExternallyDestructed, TempDtorContext &Context); |
| CFGBlock *VisitConditionalOperatorForTemporaryDtors( |
| AbstractConditionalOperator *E, bool ExternallyDestructed, |
| TempDtorContext &Context); |
| void InsertTempDtorDecisionBlock(const TempDtorContext &Context, |
| CFGBlock *FalseSucc = nullptr); |
| |
| // NYS == Not Yet Supported |
| CFGBlock *NYS() { |
| badCFG = true; |
| return Block; |
| } |
| |
| // Remember to apply the construction context based on the current \p Layer |
| // when constructing the CFG element for \p CE. |
| void consumeConstructionContext(const ConstructionContextLayer *Layer, |
| Expr *E); |
| |
| // Scan \p Child statement to find constructors in it, while keeping in mind |
| // that its parent statement is providing a partial construction context |
| // described by \p Layer. If a constructor is found, it would be assigned |
| // the context based on the layer. If an additional construction context layer |
| // is found, the function recurses into that. |
| void findConstructionContexts(const ConstructionContextLayer *Layer, |
| Stmt *Child); |
| |
| // Scan all arguments of a call expression for a construction context. |
| // These sorts of call expressions don't have a common superclass, |
| // hence strict duck-typing. |
| template <typename CallLikeExpr, |
| typename = typename std::enable_if< |
| std::is_same<CallLikeExpr, CallExpr>::value || |
| std::is_same<CallLikeExpr, CXXConstructExpr>::value || |
| std::is_same<CallLikeExpr, ObjCMessageExpr>::value>> |
| void findConstructionContextsForArguments(CallLikeExpr *E) { |
| for (unsigned i = 0, e = E->getNumArgs(); i != e; ++i) { |
| Expr *Arg = E->getArg(i); |
| if (Arg->getType()->getAsCXXRecordDecl() && !Arg->isGLValue()) |
| findConstructionContexts( |
| ConstructionContextLayer::create(cfg->getBumpVectorContext(), |
| ConstructionContextItem(E, i)), |
| Arg); |
| } |
| } |
| |
| // Unset the construction context after consuming it. This is done immediately |
| // after adding the CFGConstructor or CFGCXXRecordTypedCall element, so |
| // there's no need to do this manually in every Visit... function. |
| void cleanupConstructionContext(Expr *E); |
| |
| void autoCreateBlock() { if (!Block) Block = createBlock(); } |
| CFGBlock *createBlock(bool add_successor = true); |
| CFGBlock *createNoReturnBlock(); |
| |
| CFGBlock *addStmt(Stmt *S) { |
| return Visit(S, AddStmtChoice::AlwaysAdd); |
| } |
| |
| CFGBlock *addInitializer(CXXCtorInitializer *I); |
| void addLoopExit(const Stmt *LoopStmt); |
| void addAutomaticObjDtors(LocalScope::const_iterator B, |
| LocalScope::const_iterator E, Stmt *S); |
| void addLifetimeEnds(LocalScope::const_iterator B, |
| LocalScope::const_iterator E, Stmt *S); |
| void addAutomaticObjHandling(LocalScope::const_iterator B, |
| LocalScope::const_iterator E, Stmt *S); |
| void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD); |
| void addScopesEnd(LocalScope::const_iterator B, LocalScope::const_iterator E, |
| Stmt *S); |
| |
| void getDeclsWithEndedScope(LocalScope::const_iterator B, |
| LocalScope::const_iterator E, Stmt *S); |
| |
| // Local scopes creation. |
| LocalScope* createOrReuseLocalScope(LocalScope* Scope); |
| |
| void addLocalScopeForStmt(Stmt *S); |
| LocalScope* addLocalScopeForDeclStmt(DeclStmt *DS, |
| LocalScope* Scope = nullptr); |
| LocalScope* addLocalScopeForVarDecl(VarDecl *VD, LocalScope* Scope = nullptr); |
| |
| void addLocalScopeAndDtors(Stmt *S); |
| |
| const ConstructionContext *retrieveAndCleanupConstructionContext(Expr *E) { |
| if (!BuildOpts.AddRichCXXConstructors) |
| return nullptr; |
| |
| const ConstructionContextLayer *Layer = ConstructionContextMap.lookup(E); |
| if (!Layer) |
| return nullptr; |
| |
| cleanupConstructionContext(E); |
| return ConstructionContext::createFromLayers(cfg->getBumpVectorContext(), |
| Layer); |
| } |
| |
| // Interface to CFGBlock - adding CFGElements. |
| |
| void appendStmt(CFGBlock *B, const Stmt *S) { |
| if (alwaysAdd(S) && cachedEntry) |
| cachedEntry->second = B; |
| |
| // All block-level expressions should have already been IgnoreParens()ed. |
| assert(!isa<Expr>(S) || cast<Expr>(S)->IgnoreParens() == S); |
| B->appendStmt(const_cast<Stmt*>(S), cfg->getBumpVectorContext()); |
| } |
| |
| void appendConstructor(CFGBlock *B, CXXConstructExpr *CE) { |
| if (const ConstructionContext *CC = |
| retrieveAndCleanupConstructionContext(CE)) { |
| B->appendConstructor(CE, CC, cfg->getBumpVectorContext()); |
| return; |
| } |
| |
| // No valid construction context found. Fall back to statement. |
| B->appendStmt(CE, cfg->getBumpVectorContext()); |
| } |
| |
| void appendCall(CFGBlock *B, CallExpr *CE) { |
| if (alwaysAdd(CE) && cachedEntry) |
| cachedEntry->second = B; |
| |
| if (const ConstructionContext *CC = |
| retrieveAndCleanupConstructionContext(CE)) { |
| B->appendCXXRecordTypedCall(CE, CC, cfg->getBumpVectorContext()); |
| return; |
| } |
| |
| // No valid construction context found. Fall back to statement. |
| B->appendStmt(CE, cfg->getBumpVectorContext()); |
| } |
| |
| void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) { |
| B->appendInitializer(I, cfg->getBumpVectorContext()); |
| } |
| |
| void appendNewAllocator(CFGBlock *B, CXXNewExpr *NE) { |
| B->appendNewAllocator(NE, cfg->getBumpVectorContext()); |
| } |
| |
| void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) { |
| B->appendBaseDtor(BS, cfg->getBumpVectorContext()); |
| } |
| |
| void appendMemberDtor(CFGBlock *B, FieldDecl *FD) { |
| B->appendMemberDtor(FD, cfg->getBumpVectorContext()); |
| } |
| |
| void appendObjCMessage(CFGBlock *B, ObjCMessageExpr *ME) { |
| if (alwaysAdd(ME) && cachedEntry) |
| cachedEntry->second = B; |
| |
| if (const ConstructionContext *CC = |
| retrieveAndCleanupConstructionContext(ME)) { |
| B->appendCXXRecordTypedCall(ME, CC, cfg->getBumpVectorContext()); |
| return; |
| } |
| |
| B->appendStmt(const_cast<ObjCMessageExpr *>(ME), |
| cfg->getBumpVectorContext()); |
| } |
| |
| void appendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) { |
| B->appendTemporaryDtor(E, cfg->getBumpVectorContext()); |
| } |
| |
| void appendAutomaticObjDtor(CFGBlock *B, VarDecl *VD, Stmt *S) { |
| B->appendAutomaticObjDtor(VD, S, cfg->getBumpVectorContext()); |
| } |
| |
| void appendLifetimeEnds(CFGBlock *B, VarDecl *VD, Stmt *S) { |
| B->appendLifetimeEnds(VD, S, cfg->getBumpVectorContext()); |
| } |
| |
| void appendLoopExit(CFGBlock *B, const Stmt *LoopStmt) { |
| B->appendLoopExit(LoopStmt, cfg->getBumpVectorContext()); |
| } |
| |
| void appendDeleteDtor(CFGBlock *B, CXXRecordDecl *RD, CXXDeleteExpr *DE) { |
| B->appendDeleteDtor(RD, DE, cfg->getBumpVectorContext()); |
| } |
| |
| void prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk, |
| LocalScope::const_iterator B, LocalScope::const_iterator E); |
| |
| void prependAutomaticObjLifetimeWithTerminator(CFGBlock *Blk, |
| LocalScope::const_iterator B, |
| LocalScope::const_iterator E); |
| |
| const VarDecl * |
| prependAutomaticObjScopeEndWithTerminator(CFGBlock *Blk, |
| LocalScope::const_iterator B, |
| LocalScope::const_iterator E); |
| |
| void addSuccessor(CFGBlock *B, CFGBlock *S, bool IsReachable = true) { |
| B->addSuccessor(CFGBlock::AdjacentBlock(S, IsReachable), |
| cfg->getBumpVectorContext()); |
| } |
| |
| /// Add a reachable successor to a block, with the alternate variant that is |
| /// unreachable. |
| void addSuccessor(CFGBlock *B, CFGBlock *ReachableBlock, CFGBlock *AltBlock) { |
| B->addSuccessor(CFGBlock::AdjacentBlock(ReachableBlock, AltBlock), |
| cfg->getBumpVectorContext()); |
| } |
| |
| void appendScopeBegin(CFGBlock *B, const VarDecl *VD, const Stmt *S) { |
| if (BuildOpts.AddScopes) |
| B->appendScopeBegin(VD, S, cfg->getBumpVectorContext()); |
| } |
| |
| void prependScopeBegin(CFGBlock *B, const VarDecl *VD, const Stmt *S) { |
| if (BuildOpts.AddScopes) |
| B->prependScopeBegin(VD, S, cfg->getBumpVectorContext()); |
| } |
| |
| void appendScopeEnd(CFGBlock *B, const VarDecl *VD, const Stmt *S) { |
| if (BuildOpts.AddScopes) |
| B->appendScopeEnd(VD, S, cfg->getBumpVectorContext()); |
| } |
| |
| void prependScopeEnd(CFGBlock *B, const VarDecl *VD, const Stmt *S) { |
| if (BuildOpts.AddScopes) |
| B->prependScopeEnd(VD, S, cfg->getBumpVectorContext()); |
| } |
| |
| /// Find a relational comparison with an expression evaluating to a |
| /// boolean and a constant other than 0 and 1. |
| /// e.g. if ((x < y) == 10) |
| TryResult checkIncorrectRelationalOperator(const BinaryOperator *B) { |
| const Expr *LHSExpr = B->getLHS()->IgnoreParens(); |
| const Expr *RHSExpr = B->getRHS()->IgnoreParens(); |
| |
| const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(LHSExpr); |
| const Expr *BoolExpr = RHSExpr; |
| bool IntFirst = true; |
| if (!IntLiteral) { |
| IntLiteral = dyn_cast<IntegerLiteral>(RHSExpr); |
| BoolExpr = LHSExpr; |
| IntFirst = false; |
| } |
| |
| if (!IntLiteral || !BoolExpr->isKnownToHaveBooleanValue()) |
| return TryResult(); |
| |
| llvm::APInt IntValue = IntLiteral->getValue(); |
| if ((IntValue == 1) || (IntValue == 0)) |
| return TryResult(); |
| |
| bool IntLarger = IntLiteral->getType()->isUnsignedIntegerType() || |
| !IntValue.isNegative(); |
| |
| BinaryOperatorKind Bok = B->getOpcode(); |
| if (Bok == BO_GT || Bok == BO_GE) { |
| // Always true for 10 > bool and bool > -1 |
| // Always false for -1 > bool and bool > 10 |
| return TryResult(IntFirst == IntLarger); |
| } else { |
| // Always true for -1 < bool and bool < 10 |
| // Always false for 10 < bool and bool < -1 |
| return TryResult(IntFirst != IntLarger); |
| } |
| } |
| |
| /// Find an incorrect equality comparison. Either with an expression |
| /// evaluating to a boolean and a constant other than 0 and 1. |
| /// e.g. if (!x == 10) or a bitwise and/or operation that always evaluates to |
| /// true/false e.q. (x & 8) == 4. |
| TryResult checkIncorrectEqualityOperator(const BinaryOperator *B) { |
| const Expr *LHSExpr = B->getLHS()->IgnoreParens(); |
| const Expr *RHSExpr = B->getRHS()->IgnoreParens(); |
| |
| const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(LHSExpr); |
| const Expr *BoolExpr = RHSExpr; |
| |
| if (!IntLiteral) { |
| IntLiteral = dyn_cast<IntegerLiteral>(RHSExpr); |
| BoolExpr = LHSExpr; |
| } |
| |
| if (!IntLiteral) |
| return TryResult(); |
| |
| const BinaryOperator *BitOp = dyn_cast<BinaryOperator>(BoolExpr); |
| if (BitOp && (BitOp->getOpcode() == BO_And || |
| BitOp->getOpcode() == BO_Or)) { |
| const Expr *LHSExpr2 = BitOp->getLHS()->IgnoreParens(); |
| const Expr *RHSExpr2 = BitOp->getRHS()->IgnoreParens(); |
| |
| const IntegerLiteral *IntLiteral2 = dyn_cast<IntegerLiteral>(LHSExpr2); |
| |
| if (!IntLiteral2) |
| IntLiteral2 = dyn_cast<IntegerLiteral>(RHSExpr2); |
| |
| if (!IntLiteral2) |
| return TryResult(); |
| |
| llvm::APInt L1 = IntLiteral->getValue(); |
| llvm::APInt L2 = IntLiteral2->getValue(); |
| if ((BitOp->getOpcode() == BO_And && (L2 & L1) != L1) || |
| (BitOp->getOpcode() == BO_Or && (L2 | L1) != L1)) { |
| if (BuildOpts.Observer) |
| BuildOpts.Observer->compareBitwiseEquality(B, |
| B->getOpcode() != BO_EQ); |
| TryResult(B->getOpcode() != BO_EQ); |
| } |
| } else if (BoolExpr->isKnownToHaveBooleanValue()) { |
| llvm::APInt IntValue = IntLiteral->getValue(); |
| if ((IntValue == 1) || (IntValue == 0)) { |
| return TryResult(); |
| } |
| return TryResult(B->getOpcode() != BO_EQ); |
| } |
| |
| return TryResult(); |
| } |
| |
| TryResult analyzeLogicOperatorCondition(BinaryOperatorKind Relation, |
| const llvm::APSInt &Value1, |
| const llvm::APSInt &Value2) { |
| assert(Value1.isSigned() == Value2.isSigned()); |
| switch (Relation) { |
| default: |
| return TryResult(); |
| case BO_EQ: |
| return TryResult(Value1 == Value2); |
| case BO_NE: |
| return TryResult(Value1 != Value2); |
| case BO_LT: |
| return TryResult(Value1 < Value2); |
| case BO_LE: |
| return TryResult(Value1 <= Value2); |
| case BO_GT: |
| return TryResult(Value1 > Value2); |
| case BO_GE: |
| return TryResult(Value1 >= Value2); |
| } |
| } |
| |
| /// Find a pair of comparison expressions with or without parentheses |
| /// with a shared variable and constants and a logical operator between them |
| /// that always evaluates to either true or false. |
| /// e.g. if (x != 3 || x != 4) |
| TryResult checkIncorrectLogicOperator(const BinaryOperator *B) { |
| assert(B->isLogicalOp()); |
| const BinaryOperator *LHS = |
| dyn_cast<BinaryOperator>(B->getLHS()->IgnoreParens()); |
| const BinaryOperator *RHS = |
| dyn_cast<BinaryOperator>(B->getRHS()->IgnoreParens()); |
| if (!LHS || !RHS) |
| return {}; |
| |
| if (!LHS->isComparisonOp() || !RHS->isComparisonOp()) |
| return {}; |
| |
| const Expr *DeclExpr1; |
| const Expr *NumExpr1; |
| BinaryOperatorKind BO1; |
| std::tie(DeclExpr1, BO1, NumExpr1) = tryNormalizeBinaryOperator(LHS); |
| |
| if (!DeclExpr1 || !NumExpr1) |
| return {}; |
| |
| const Expr *DeclExpr2; |
| const Expr *NumExpr2; |
| BinaryOperatorKind BO2; |
| std::tie(DeclExpr2, BO2, NumExpr2) = tryNormalizeBinaryOperator(RHS); |
| |
| if (!DeclExpr2 || !NumExpr2) |
| return {}; |
| |
| // Check that it is the same variable on both sides. |
| if (!Expr::isSameComparisonOperand(DeclExpr1, DeclExpr2)) |
| return {}; |
| |
| // Make sure the user's intent is clear (e.g. they're comparing against two |
| // int literals, or two things from the same enum) |
| if (!areExprTypesCompatible(NumExpr1, NumExpr2)) |
| return {}; |
| |
| Expr::EvalResult L1Result, L2Result; |
| if (!NumExpr1->EvaluateAsInt(L1Result, *Context) || |
| !NumExpr2->EvaluateAsInt(L2Result, *Context)) |
| return {}; |
| |
| llvm::APSInt L1 = L1Result.Val.getInt(); |
| llvm::APSInt L2 = L2Result.Val.getInt(); |
| |
| // Can't compare signed with unsigned or with different bit width. |
| if (L1.isSigned() != L2.isSigned() || L1.getBitWidth() != L2.getBitWidth()) |
| return {}; |
| |
| // Values that will be used to determine if result of logical |
| // operator is always true/false |
| const llvm::APSInt Values[] = { |
| // Value less than both Value1 and Value2 |
| llvm::APSInt::getMinValue(L1.getBitWidth(), L1.isUnsigned()), |
| // L1 |
| L1, |
| // Value between Value1 and Value2 |
| ((L1 < L2) ? L1 : L2) + llvm::APSInt(llvm::APInt(L1.getBitWidth(), 1), |
| L1.isUnsigned()), |
| // L2 |
| L2, |
| // Value greater than both Value1 and Value2 |
| llvm::APSInt::getMaxValue(L1.getBitWidth(), L1.isUnsigned()), |
| }; |
| |
| // Check whether expression is always true/false by evaluating the following |
| // * variable x is less than the smallest literal. |
| // * variable x is equal to the smallest literal. |
| // * Variable x is between smallest and largest literal. |
| // * Variable x is equal to the largest literal. |
| // * Variable x is greater than largest literal. |
| bool AlwaysTrue = true, AlwaysFalse = true; |
| // Track value of both subexpressions. If either side is always |
| // true/false, another warning should have already been emitted. |
| bool LHSAlwaysTrue = true, LHSAlwaysFalse = true; |
| bool RHSAlwaysTrue = true, RHSAlwaysFalse = true; |
| for (const llvm::APSInt &Value : Values) { |
| TryResult Res1, Res2; |
| Res1 = analyzeLogicOperatorCondition(BO1, Value, L1); |
| Res2 = analyzeLogicOperatorCondition(BO2, Value, L2); |
| |
| if (!Res1.isKnown() || !Res2.isKnown()) |
| return {}; |
| |
| if (B->getOpcode() == BO_LAnd) { |
| AlwaysTrue &= (Res1.isTrue() && Res2.isTrue()); |
| AlwaysFalse &= !(Res1.isTrue() && Res2.isTrue()); |
| } else { |
| AlwaysTrue &= (Res1.isTrue() || Res2.isTrue()); |
| AlwaysFalse &= !(Res1.isTrue() || Res2.isTrue()); |
| } |
| |
| LHSAlwaysTrue &= Res1.isTrue(); |
| LHSAlwaysFalse &= Res1.isFalse(); |
| RHSAlwaysTrue &= Res2.isTrue(); |
| RHSAlwaysFalse &= Res2.isFalse(); |
| } |
| |
| if (AlwaysTrue || AlwaysFalse) { |
| if (!LHSAlwaysTrue && !LHSAlwaysFalse && !RHSAlwaysTrue && |
| !RHSAlwaysFalse && BuildOpts.Observer) |
| BuildOpts.Observer->compareAlwaysTrue(B, AlwaysTrue); |
| return TryResult(AlwaysTrue); |
| } |
| return {}; |
| } |
| |
| /// Try and evaluate an expression to an integer constant. |
| bool tryEvaluate(Expr *S, Expr::EvalResult &outResult) { |
| if (!BuildOpts.PruneTriviallyFalseEdges) |
| return false; |
| return !S->isTypeDependent() && |
| !S->isValueDependent() && |
| S->EvaluateAsRValue(outResult, *Context); |
| } |
| |
| /// tryEvaluateBool - Try and evaluate the Stmt and return 0 or 1 |
| /// if we can evaluate to a known value, otherwise return -1. |
| TryResult tryEvaluateBool(Expr *S) { |
| if (!BuildOpts.PruneTriviallyFalseEdges || |
| S->isTypeDependent() || S->isValueDependent()) |
| return {}; |
| |
| if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(S)) { |
| if (Bop->isLogicalOp()) { |
| // Check the cache first. |
| CachedBoolEvalsTy::iterator I = CachedBoolEvals.find(S); |
| if (I != CachedBoolEvals.end()) |
| return I->second; // already in map; |
| |
| // Retrieve result at first, or the map might be updated. |
| TryResult Result = evaluateAsBooleanConditionNoCache(S); |
| CachedBoolEvals[S] = Result; // update or insert |
| return Result; |
| } |
| else { |
| switch (Bop->getOpcode()) { |
| default: break; |
| // For 'x & 0' and 'x * 0', we can determine that |
| // the value is always false. |
| case BO_Mul: |
| case BO_And: { |
| // If either operand is zero, we know the value |
| // must be false. |
| Expr::EvalResult LHSResult; |
| if (Bop->getLHS()->EvaluateAsInt(LHSResult, *Context)) { |
| llvm::APSInt IntVal = LHSResult.Val.getInt(); |
| if (!IntVal.getBoolValue()) { |
| return TryResult(false); |
| } |
| } |
| Expr::EvalResult RHSResult; |
| if (Bop->getRHS()->EvaluateAsInt(RHSResult, *Context)) { |
| llvm::APSInt IntVal = RHSResult.Val.getInt(); |
| if (!IntVal.getBoolValue()) { |
| return TryResult(false); |
| } |
| } |
| } |
| break; |
| } |
| } |
| } |
| |
| return evaluateAsBooleanConditionNoCache(S); |
| } |
| |
| /// Evaluate as boolean \param E without using the cache. |
| TryResult evaluateAsBooleanConditionNoCache(Expr *E) { |
| if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(E)) { |
| if (Bop->isLogicalOp()) { |
| TryResult LHS = tryEvaluateBool(Bop->getLHS()); |
| if (LHS.isKnown()) { |
| // We were able to evaluate the LHS, see if we can get away with not |
| // evaluating the RHS: 0 && X -> 0, 1 || X -> 1 |
| if (LHS.isTrue() == (Bop->getOpcode() == BO_LOr)) |
| return LHS.isTrue(); |
| |
| TryResult RHS = tryEvaluateBool(Bop->getRHS()); |
| if (RHS.isKnown()) { |
| if (Bop->getOpcode() == BO_LOr) |
| return LHS.isTrue() || RHS.isTrue(); |
| else |
| return LHS.isTrue() && RHS.isTrue(); |
| } |
| } else { |
| TryResult RHS = tryEvaluateBool(Bop->getRHS()); |
| if (RHS.isKnown()) { |
| // We can't evaluate the LHS; however, sometimes the result |
| // is determined by the RHS: X && 0 -> 0, X || 1 -> 1. |
| if (RHS.isTrue() == (Bop->getOpcode() == BO_LOr)) |
| return RHS.isTrue(); |
| } else { |
| TryResult BopRes = checkIncorrectLogicOperator(Bop); |
| if (BopRes.isKnown()) |
| return BopRes.isTrue(); |
| } |
| } |
| |
| return {}; |
| } else if (Bop->isEqualityOp()) { |
| TryResult BopRes = checkIncorrectEqualityOperator(Bop); |
| if (BopRes.isKnown()) |
| return BopRes.isTrue(); |
| } else if (Bop->isRelationalOp()) { |
| TryResult BopRes = checkIncorrectRelationalOperator(Bop); |
| if (BopRes.isKnown()) |
| return BopRes.isTrue(); |
| } |
| } |
| |
| bool Result; |
| if (E->EvaluateAsBooleanCondition(Result, *Context)) |
| return Result; |
| |
| return {}; |
| } |
| |
| bool hasTrivialDestructor(VarDecl *VD); |
| }; |
| |
| } // namespace |
| |
| inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder, |
| const Stmt *stmt) const { |
| return builder.alwaysAdd(stmt) || kind == AlwaysAdd; |
| } |
| |
| bool CFGBuilder::alwaysAdd(const Stmt *stmt) { |
| bool shouldAdd = BuildOpts.alwaysAdd(stmt); |
| |
| if (!BuildOpts.forcedBlkExprs) |
| return shouldAdd; |
| |
| if (lastLookup == stmt) { |
| if (cachedEntry) { |
| assert(cachedEntry->first == stmt); |
| return true; |
| } |
| return shouldAdd; |
| } |
| |
| lastLookup = stmt; |
| |
| // Perform the lookup! |
| CFG::BuildOptions::ForcedBlkExprs *fb = *BuildOpts.forcedBlkExprs; |
| |
| if (!fb) { |
| // No need to update 'cachedEntry', since it will always be null. |
| assert(!cachedEntry); |
| return shouldAdd; |
| } |
| |
| CFG::BuildOptions::ForcedBlkExprs::iterator itr = fb->find(stmt); |
| if (itr == fb->end()) { |
| cachedEntry = nullptr; |
| return shouldAdd; |
| } |
| |
| cachedEntry = &*itr; |
| return true; |
| } |
| |
| // FIXME: Add support for dependent-sized array types in C++? |
| // Does it even make sense to build a CFG for an uninstantiated template? |
| static const VariableArrayType *FindVA(const Type *t) { |
| while (const ArrayType *vt = dyn_cast<ArrayType>(t)) { |
| if (const VariableArrayType *vat = dyn_cast<VariableArrayType>(vt)) |
| if (vat->getSizeExpr()) |
| return vat; |
| |
| t = vt->getElementType().getTypePtr(); |
| } |
| |
| return nullptr; |
| } |
| |
| void CFGBuilder::consumeConstructionContext( |
| const ConstructionContextLayer *Layer, Expr *E) { |
| assert((isa<CXXConstructExpr>(E) || isa<CallExpr>(E) || |
| isa<ObjCMessageExpr>(E)) && "Expression cannot construct an object!"); |
| if (const ConstructionContextLayer *PreviouslyStoredLayer = |
| ConstructionContextMap.lookup(E)) { |
| (void)PreviouslyStoredLayer; |
| // We might have visited this child when we were finding construction |
| // contexts within its parents. |
| assert(PreviouslyStoredLayer->isStrictlyMoreSpecificThan(Layer) && |
| "Already within a different construction context!"); |
| } else { |
| ConstructionContextMap[E] = Layer; |
| } |
| } |
| |
| void CFGBuilder::findConstructionContexts( |
| const ConstructionContextLayer *Layer, Stmt *Child) { |
| if (!BuildOpts.AddRichCXXConstructors) |
| return; |
| |
| if (!Child) |
| return; |
| |
| auto withExtraLayer = [this, Layer](const ConstructionContextItem &Item) { |
| return ConstructionContextLayer::create(cfg->getBumpVectorContext(), Item, |
| Layer); |
| }; |
| |
| switch(Child->getStmtClass()) { |
| case Stmt::CXXConstructExprClass: |
| case Stmt::CXXTemporaryObjectExprClass: { |
| // Support pre-C++17 copy elision AST. |
| auto *CE = cast<CXXConstructExpr>(Child); |
| if (BuildOpts.MarkElidedCXXConstructors && CE->isElidable()) { |
| findConstructionContexts(withExtraLayer(CE), CE->getArg(0)); |
| } |
| |
| consumeConstructionContext(Layer, CE); |
| break; |
| } |
| // FIXME: This, like the main visit, doesn't support CUDAKernelCallExpr. |
| // FIXME: An isa<> would look much better but this whole switch is a |
| // workaround for an internal compiler error in MSVC 2015 (see r326021). |
| case Stmt::CallExprClass: |
| case Stmt::CXXMemberCallExprClass: |
| case Stmt::CXXOperatorCallExprClass: |
| case Stmt::UserDefinedLiteralClass: |
| case Stmt::ObjCMessageExprClass: { |
| auto *E = cast<Expr>(Child); |
| if (CFGCXXRecordTypedCall::isCXXRecordTypedCall(E)) |
| consumeConstructionContext(Layer, E); |
| break; |
| } |
| case Stmt::ExprWithCleanupsClass: { |
| auto *Cleanups = cast<ExprWithCleanups>(Child); |
| findConstructionContexts(Layer, Cleanups->getSubExpr()); |
| break; |
| } |
| case Stmt::CXXFunctionalCastExprClass: { |
| auto *Cast = cast<CXXFunctionalCastExpr>(Child); |
| findConstructionContexts(Layer, Cast->getSubExpr()); |
| break; |
| } |
| case Stmt::ImplicitCastExprClass: { |
| auto *Cast = cast<ImplicitCastExpr>(Child); |
| // Should we support other implicit cast kinds? |
| switch (Cast->getCastKind()) { |
| case CK_NoOp: |
| case CK_ConstructorConversion: |
| findConstructionContexts(Layer, Cast->getSubExpr()); |
| break; |
| default: |
| break; |
| } |
| break; |
| } |
| case Stmt::CXXBindTemporaryExprClass: { |
| auto *BTE = cast<CXXBindTemporaryExpr>(Child); |
| findConstructionContexts(withExtraLayer(BTE), BTE->getSubExpr()); |
| break; |
| } |
| case Stmt::MaterializeTemporaryExprClass: { |
| // Normally we don't want to search in MaterializeTemporaryExpr because |
| // it indicates the beginning of a temporary object construction context, |
| // so it shouldn't be found in the middle. However, if it is the beginning |
| // of an elidable copy or move construction context, we need to include it. |
| if (Layer->getItem().getKind() == |
| ConstructionContextItem::ElidableConstructorKind) { |
| auto *MTE = cast<MaterializeTemporaryExpr>(Child); |
| findConstructionContexts(withExtraLayer(MTE), MTE->GetTemporaryExpr()); |
| } |
| break; |
| } |
| case Stmt::ConditionalOperatorClass: { |
| auto *CO = cast<ConditionalOperator>(Child); |
| if (Layer->getItem().getKind() != |
| ConstructionContextItem::MaterializationKind) { |
| // If the object returned by the conditional operator is not going to be a |
| // temporary object that needs to be immediately materialized, then |
| // it must be C++17 with its mandatory copy elision. Do not yet promise |
| // to support this case. |
| assert(!CO->getType()->getAsCXXRecordDecl() || CO->isGLValue() || |
| Context->getLangOpts().CPlusPlus17); |
| break; |
| } |
| findConstructionContexts(Layer, CO->getLHS()); |
| findConstructionContexts(Layer, CO->getRHS()); |
| break; |
| } |
| case Stmt::InitListExprClass: { |
| auto *ILE = cast<InitListExpr>(Child); |
| if (ILE->isTransparent()) { |
| findConstructionContexts(Layer, ILE->getInit(0)); |
| break; |
| } |
| // TODO: Handle other cases. For now, fail to find construction contexts. |
| break; |
| } |
| default: |
| break; |
| } |
| } |
| |
| void CFGBuilder::cleanupConstructionContext(Expr *E) { |
| assert(BuildOpts.AddRichCXXConstructors && |
| "We should not be managing construction contexts!"); |
| assert(ConstructionContextMap.count(E) && |
| "Cannot exit construction context without the context!"); |
| ConstructionContextMap.erase(E); |
| } |
| |
| |
| /// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an |
| /// arbitrary statement. Examples include a single expression or a function |
| /// body (compound statement). The ownership of the returned CFG is |
| /// transferred to the caller. If CFG construction fails, this method returns |
| /// NULL. |
| std::unique_ptr<CFG> CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) { |
| assert(cfg.get()); |
| if (!Statement) |
| return nullptr; |
| |
| // Create an empty block that will serve as the exit block for the CFG. Since |
| // this is the first block added to the CFG, it will be implicitly registered |
| // as the exit block. |
| Succ = createBlock(); |
| assert(Succ == &cfg->getExit()); |
| Block = nullptr; // the EXIT block is empty. Create all other blocks lazily. |
| |
| assert(!(BuildOpts.AddImplicitDtors && BuildOpts.AddLifetime) && |
| "AddImplicitDtors and AddLifetime cannot be used at the same time"); |
| |
| if (BuildOpts.AddImplicitDtors) |
| if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(D)) |
| addImplicitDtorsForDestructor(DD); |
| |
| // Visit the statements and create the CFG. |
| CFGBlock *B = addStmt(Statement); |
| |
| if (badCFG) |
| return nullptr; |
| |
| // For C++ constructor add initializers to CFG. Constructors of virtual bases |
| // are ignored unless the object is of the most derived class. |
| // class VBase { VBase() = default; VBase(int) {} }; |
| // class A : virtual public VBase { A() : VBase(0) {} }; |
| // class B : public A {}; |
| // B b; // Constructor calls in order: VBase(), A(), B(). |
| // // VBase(0) is ignored because A isn't the most derived class. |
| // This may result in the virtual base(s) being already initialized at this |
| // point, in which case we should jump right onto non-virtual bases and |
| // fields. To handle this, make a CFG branch. We only need to add one such |
| // branch per constructor, since the Standard states that all virtual bases |
| // shall be initialized before non-virtual bases and direct data members. |
| if (const auto *CD = dyn_cast_or_null<CXXConstructorDecl>(D)) { |
| CFGBlock *VBaseSucc = nullptr; |
| for (auto *I : llvm::reverse(CD->inits())) { |
| if (BuildOpts.AddVirtualBaseBranches && !VBaseSucc && |
| I->isBaseInitializer() && I->isBaseVirtual()) { |
| // We've reached the first virtual base init while iterating in reverse |
| // order. Make a new block for virtual base initializers so that we |
| // could skip them. |
| VBaseSucc = Succ = B ? B : &cfg->getExit(); |
| Block = createBlock(); |
| } |
| B = addInitializer(I); |
| if (badCFG) |
| return nullptr; |
| } |
| if (VBaseSucc) { |
| // Make a branch block for potentially skipping virtual base initializers. |
| Succ = VBaseSucc; |
| B = createBlock(); |
| B->setTerminator( |
| CFGTerminator(nullptr, CFGTerminator::VirtualBaseBranch)); |
| addSuccessor(B, Block, true); |
| } |
| } |
| |
| if (B) |
| Succ = B; |
| |
| // Backpatch the gotos whose label -> block mappings we didn't know when we |
| // encountered them. |
| for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(), |
| E = BackpatchBlocks.end(); I != E; ++I ) { |
| |
| CFGBlock *B = I->block; |
| if (auto *G = dyn_cast<GotoStmt>(B->getTerminator())) { |
| LabelMapTy::iterator LI = LabelMap.find(G->getLabel()); |
| // If there is no target for the goto, then we are looking at an |
| // incomplete AST. Handle this by not registering a successor. |
| if (LI == LabelMap.end()) |
| continue; |
| JumpTarget JT = LI->second; |
| prependAutomaticObjLifetimeWithTerminator(B, I->scopePosition, |
| JT.scopePosition); |
| prependAutomaticObjDtorsWithTerminator(B, I->scopePosition, |
| JT.scopePosition); |
| const VarDecl *VD = prependAutomaticObjScopeEndWithTerminator( |
| B, I->scopePosition, JT.scopePosition); |
| appendScopeBegin(JT.block, VD, G); |
| addSuccessor(B, JT.block); |
| }; |
| if (auto *G = dyn_cast<GCCAsmStmt>(B->getTerminator())) { |
| CFGBlock *Successor = (I+1)->block; |
| for (auto *L : G->labels()) { |
| LabelMapTy::iterator LI = LabelMap.find(L->getLabel()); |
| // If there is no target for the goto, then we are looking at an |
| // incomplete AST. Handle this by not registering a successor. |
| if (LI == LabelMap.end()) |
| continue; |
| JumpTarget JT = LI->second; |
| // Successor has been added, so skip it. |
| if (JT.block == Successor) |
| continue; |
| addSuccessor(B, JT.block); |
| } |
| I++; |
| } |
| } |
| |
| // Add successors to the Indirect Goto Dispatch block (if we have one). |
| if (CFGBlock *B = cfg->getIndirectGotoBlock()) |
| for (LabelSetTy::iterator I = AddressTakenLabels.begin(), |
| E = AddressTakenLabels.end(); I != E; ++I ) { |
| // Lookup the target block. |
| LabelMapTy::iterator LI = LabelMap.find(*I); |
| |
| // If there is no target block that contains label, then we are looking |
| // at an incomplete AST. Handle this by not registering a successor. |
| if (LI == LabelMap.end()) continue; |
| |
| addSuccessor(B, LI->second.block); |
| } |
| |
| // Create an empty entry block that has no predecessors. |
| cfg->setEntry(createBlock()); |
| |
| if (BuildOpts.AddRichCXXConstructors) |
| assert(ConstructionContextMap.empty() && |
| "Not all construction contexts were cleaned up!"); |
| |
| return std::move(cfg); |
| } |
| |
| /// createBlock - Used to lazily create blocks that are connected |
| /// to the current (global) succcessor. |
| CFGBlock *CFGBuilder::createBlock(bool add_successor) { |
| CFGBlock *B = cfg->createBlock(); |
| if (add_successor && Succ) |
| addSuccessor(B, Succ); |
| return B; |
| } |
| |
| /// createNoReturnBlock - Used to create a block is a 'noreturn' point in the |
| /// CFG. It is *not* connected to the current (global) successor, and instead |
| /// directly tied to the exit block in order to be reachable. |
| CFGBlock *CFGBuilder::createNoReturnBlock() { |
| CFGBlock *B = createBlock(false); |
| B->setHasNoReturnElement(); |
| addSuccessor(B, &cfg->getExit(), Succ); |
| return B; |
| } |
| |
| /// addInitializer - Add C++ base or member initializer element to CFG. |
| CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) { |
| if (!BuildOpts.AddInitializers) |
| return Block; |
| |
| bool HasTemporaries = false; |
| |
| // Destructors of temporaries in initialization expression should be called |
| // after initialization finishes. |
| Expr *Init = I->getInit(); |
| if (Init) { |
| HasTemporaries = isa<ExprWithCleanups>(Init); |
| |
| if (BuildOpts.AddTemporaryDtors && HasTemporaries) { |
| // Generate destructors for temporaries in initialization expression. |
| TempDtorContext Context; |
| VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(), |
| /*ExternallyDestructed=*/false, Context); |
| } |
| } |
| |
| autoCreateBlock(); |
| appendInitializer(Block, I); |
| |
| if (Init) { |
| findConstructionContexts( |
| ConstructionContextLayer::create(cfg->getBumpVectorContext(), I), |
| Init); |
| |
| if (HasTemporaries) { |
| // For expression with temporaries go directly to subexpression to omit |
| // generating destructors for the second time. |
| return Visit(cast<ExprWithCleanups>(Init)->getSubExpr()); |
| } |
| if (BuildOpts.AddCXXDefaultInitExprInCtors) { |
| if (CXXDefaultInitExpr *Default = dyn_cast<CXXDefaultInitExpr>(Init)) { |
| // In general, appending the expression wrapped by a CXXDefaultInitExpr |
| // may cause the same Expr to appear more than once in the CFG. Doing it |
| // here is safe because there's only one initializer per field. |
| autoCreateBlock(); |
| appendStmt(Block, Default); |
| if (Stmt *Child = Default->getExpr()) |
| if (CFGBlock *R = Visit(Child)) |
| Block = R; |
| return Block; |
| } |
| } |
| return Visit(Init); |
| } |
| |
| return Block; |
| } |
| |
| /// Retrieve the type of the temporary object whose lifetime was |
| /// extended by a local reference with the given initializer. |
| static QualType getReferenceInitTemporaryType(const Expr *Init, |
| bool *FoundMTE = nullptr) { |
| while (true) { |
| // Skip parentheses. |
| Init = Init->IgnoreParens(); |
| |
| // Skip through cleanups. |
| if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Init)) { |
| Init = EWC->getSubExpr(); |
| continue; |
| } |
| |
| // Skip through the temporary-materialization expression. |
| if (const MaterializeTemporaryExpr *MTE |
| = dyn_cast<MaterializeTemporaryExpr>(Init)) { |
| Init = MTE->GetTemporaryExpr(); |
| if (FoundMTE) |
| *FoundMTE = true; |
| continue; |
| } |
| |
| // Skip sub-object accesses into rvalues. |
| SmallVector<const Expr *, 2> CommaLHSs; |
| SmallVector<SubobjectAdjustment, 2> Adjustments; |
| const Expr *SkippedInit = |
| Init->skipRValueSubobjectAdjustments(CommaLHSs, Adjustments); |
| if (SkippedInit != Init) { |
| Init = SkippedInit; |
| continue; |
| } |
| |
| break; |
| } |
| |
| return Init->getType(); |
| } |
| |
| // TODO: Support adding LoopExit element to the CFG in case where the loop is |
| // ended by ReturnStmt, GotoStmt or ThrowExpr. |
| void CFGBuilder::addLoopExit(const Stmt *LoopStmt){ |
| if(!BuildOpts.AddLoopExit) |
| return; |
| autoCreateBlock(); |
| appendLoopExit(Block, LoopStmt); |
| } |
| |
| void CFGBuilder::getDeclsWithEndedScope(LocalScope::const_iterator B, |
| LocalScope::const_iterator E, Stmt *S) { |
| if (!BuildOpts.AddScopes) |
| return; |
| |
| if (B == E) |
| return; |
| |
| // To go from B to E, one first goes up the scopes from B to P |
| // then sideways in one scope from P to P' and then down |
| // the scopes from P' to E. |
| // The lifetime of all objects between B and P end. |
| LocalScope::const_iterator P = B.shared_parent(E); |
| int Dist = B.distance(P); |
| if (Dist <= 0) |
| return; |
| |
| for (LocalScope::const_iterator I = B; I != P; ++I) |
| if (I.pointsToFirstDeclaredVar()) |
| DeclsWithEndedScope.insert(*I); |
| } |
| |
| void CFGBuilder::addAutomaticObjHandling(LocalScope::const_iterator B, |
| LocalScope::const_iterator E, |
| Stmt *S) { |
| getDeclsWithEndedScope(B, E, S); |
| if (BuildOpts.AddScopes) |
| addScopesEnd(B, E, S); |
| if (BuildOpts.AddImplicitDtors) |
| addAutomaticObjDtors(B, E, S); |
| if (BuildOpts.AddLifetime) |
| addLifetimeEnds(B, E, S); |
| } |
| |
| /// Add to current block automatic objects that leave the scope. |
| void CFGBuilder::addLifetimeEnds(LocalScope::const_iterator B, |
| LocalScope::const_iterator E, Stmt *S) { |
| if (!BuildOpts.AddLifetime) |
| return; |
| |
| if (B == E) |
| return; |
| |
| // To go from B to E, one first goes up the scopes from B to P |
| // then sideways in one scope from P to P' and then down |
| // the scopes from P' to E. |
| // The lifetime of all objects between B and P end. |
| LocalScope::const_iterator P = B.shared_parent(E); |
| int dist = B.distance(P); |
| if (dist <= 0) |
| return; |
| |
| // We need to perform the scope leaving in reverse order |
| SmallVector<VarDecl *, 10> DeclsTrivial; |
| SmallVector<VarDecl *, 10> DeclsNonTrivial; |
| DeclsTrivial.reserve(dist); |
| DeclsNonTrivial.reserve(dist); |
| |
| for (LocalScope::const_iterator I = B; I != P; ++I) |
| if (hasTrivialDestructor(*I)) |
| DeclsTrivial.push_back(*I); |
| else |
| DeclsNonTrivial.push_back(*I); |
| |
| autoCreateBlock(); |
| // object with trivial destructor end their lifetime last (when storage |
| // duration ends) |
| for (SmallVectorImpl<VarDecl *>::reverse_iterator I = DeclsTrivial.rbegin(), |
| E = DeclsTrivial.rend(); |
| I != E; ++I) |
| appendLifetimeEnds(Block, *I, S); |
| |
| for (SmallVectorImpl<VarDecl *>::reverse_iterator |
| I = DeclsNonTrivial.rbegin(), |
| E = DeclsNonTrivial.rend(); |
| I != E; ++I) |
| appendLifetimeEnds(Block, *I, S); |
| } |
| |
| /// Add to current block markers for ending scopes. |
| void CFGBuilder::addScopesEnd(LocalScope::const_iterator B, |
| LocalScope::const_iterator E, Stmt *S) { |
| // If implicit destructors are enabled, we'll add scope ends in |
| // addAutomaticObjDtors. |
| if (BuildOpts.AddImplicitDtors) |
| return; |
| |
| autoCreateBlock(); |
| |
| for (auto I = DeclsWithEndedScope.rbegin(), E = DeclsWithEndedScope.rend(); |
| I != E; ++I) |
| appendScopeEnd(Block, *I, S); |
| |
| return; |
| } |
| |
| /// addAutomaticObjDtors - Add to current block automatic objects destructors |
| /// for objects in range of local scope positions. Use S as trigger statement |
| /// for destructors. |
| void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B, |
| LocalScope::const_iterator E, Stmt *S) { |
| if (!BuildOpts.AddImplicitDtors) |
| return; |
| |
| if (B == E) |
| return; |
| |
| // We need to append the destructors in reverse order, but any one of them |
| // may be a no-return destructor which changes the CFG. As a result, buffer |
| // this sequence up and replay them in reverse order when appending onto the |
| // CFGBlock(s). |
| SmallVector<VarDecl*, 10> Decls; |
| Decls.reserve(B.distance(E)); |
| for (LocalScope::const_iterator I = B; I != E; ++I) |
| Decls.push_back(*I); |
| |
| for (SmallVectorImpl<VarDecl*>::reverse_iterator I = Decls.rbegin(), |
| E = Decls.rend(); |
| I != E; ++I) { |
| if (hasTrivialDestructor(*I)) { |
| // If AddScopes is enabled and *I is a first variable in a scope, add a |
| // ScopeEnd marker in a Block. |
| if (BuildOpts.AddScopes && DeclsWithEndedScope.count(*I)) { |
| autoCreateBlock(); |
| appendScopeEnd(Block, *I, S); |
| } |
| continue; |
| } |
| // If this destructor is marked as a no-return destructor, we need to |
| // create a new block for the destructor which does not have as a successor |
| // anything built thus far: control won't flow out of this block. |
| QualType Ty = (*I)->getType(); |
| if (Ty->isReferenceType()) { |
| Ty = getReferenceInitTemporaryType((*I)->getInit()); |
| } |
| Ty = Context->getBaseElementType(Ty); |
| |
| if (Ty->getAsCXXRecordDecl()->isAnyDestructorNoReturn()) |
| Block = createNoReturnBlock(); |
| else |
| autoCreateBlock(); |
| |
| // Add ScopeEnd just after automatic obj destructor. |
| if (BuildOpts.AddScopes && DeclsWithEndedScope.count(*I)) |
| appendScopeEnd(Block, *I, S); |
| appendAutomaticObjDtor(Block, *I, S); |
| } |
| } |
| |
| /// addImplicitDtorsForDestructor - Add implicit destructors generated for |
| /// base and member objects in destructor. |
| void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) { |
| assert(BuildOpts.AddImplicitDtors && |
| "Can be called only when dtors should be added"); |
| const CXXRecordDecl *RD = DD->getParent(); |
| |
| // At the end destroy virtual base objects. |
| for (const auto &VI : RD->vbases()) { |
| // TODO: Add a VirtualBaseBranch to see if the most derived class |
| // (which is different from the current class) is responsible for |
| // destroying them. |
| const CXXRecordDecl *CD = VI.getType()->getAsCXXRecordDecl(); |
| if (!CD->hasTrivialDestructor()) { |
| autoCreateBlock(); |
| appendBaseDtor(Block, &VI); |
| } |
| } |
| |
| // Before virtual bases destroy direct base objects. |
| for (const auto &BI : RD->bases()) { |
| if (!BI.isVirtual()) { |
| const CXXRecordDecl *CD = BI.getType()->getAsCXXRecordDecl(); |
| if (!CD->hasTrivialDestructor()) { |
| autoCreateBlock(); |
| appendBaseDtor(Block, &BI); |
| } |
| } |
| } |
| |
| // First destroy member objects. |
| for (auto *FI : RD->fields()) { |
| // Check for constant size array. Set type to array element type. |
| QualType QT = FI->getType(); |
| if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) { |
| if (AT->getSize() == 0) |
| continue; |
| QT = AT->getElementType(); |
| } |
| |
| if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl()) |
| if (!CD->hasTrivialDestructor()) { |
| autoCreateBlock(); |
| appendMemberDtor(Block, FI); |
| } |
| } |
| } |
| |
| /// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either |
| /// way return valid LocalScope object. |
| LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) { |
| if (Scope) |
| return Scope; |
| llvm::BumpPtrAllocator &alloc = cfg->getAllocator(); |
| return new (alloc.Allocate<LocalScope>()) |
| LocalScope(BumpVectorContext(alloc), ScopePos); |
| } |
| |
| /// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement |
| /// that should create implicit scope (e.g. if/else substatements). |
| void CFGBuilder::addLocalScopeForStmt(Stmt *S) { |
| if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime && |
| !BuildOpts.AddScopes) |
| return; |
| |
| LocalScope *Scope = nullptr; |
| |
| // For compound statement we will be creating explicit scope. |
| if (CompoundStmt *CS = dyn_cast<CompoundStmt>(S)) { |
| for (auto *BI : CS->body()) { |
| Stmt *SI = BI->stripLabelLikeStatements(); |
| if (DeclStmt *DS = dyn_cast<DeclStmt>(SI)) |
| Scope = addLocalScopeForDeclStmt(DS, Scope); |
| } |
| return; |
| } |
| |
| // For any other statement scope will be implicit and as such will be |
| // interesting only for DeclStmt. |
| if (DeclStmt *DS = dyn_cast<DeclStmt>(S->stripLabelLikeStatements())) |
| addLocalScopeForDeclStmt(DS); |
| } |
| |
| /// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will |
| /// reuse Scope if not NULL. |
| LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt *DS, |
| LocalScope* Scope) { |
| if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime && |
| !BuildOpts.AddScopes) |
| return Scope; |
| |
| for (auto *DI : DS->decls()) |
| if (VarDecl *VD = dyn_cast<VarDecl>(DI)) |
| Scope = addLocalScopeForVarDecl(VD, Scope); |
| return Scope; |
| } |
| |
| bool CFGBuilder::hasTrivialDestructor(VarDecl *VD) { |
| // Check for const references bound to temporary. Set type to pointee. |
| QualType QT = VD->getType(); |
| if (QT->isReferenceType()) { |
| // Attempt to determine whether this declaration lifetime-extends a |
| // temporary. |
| // |
| // FIXME: This is incorrect. Non-reference declarations can lifetime-extend |
| // temporaries, and a single declaration can extend multiple temporaries. |
| // We should look at the storage duration on each nested |
| // MaterializeTemporaryExpr instead. |
| |
| const Expr *Init = VD->getInit(); |
| if (!Init) { |
| // Probably an exception catch-by-reference variable. |
| // FIXME: It doesn't really mean that the object has a trivial destructor. |
| // Also are there other cases? |
| return true; |
| } |
| |
| // Lifetime-extending a temporary? |
| bool FoundMTE = false; |
| QT = getReferenceInitTemporaryType(Init, &FoundMTE); |
| if (!FoundMTE) |
| return true; |
| } |
| |
| // Check for constant size array. Set type to array element type. |
| while (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) { |
| if (AT->getSize() == 0) |
| return true; |
| QT = AT->getElementType(); |
| } |
| |
| // Check if type is a C++ class with non-trivial destructor. |
| if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl()) |
| return !CD->hasDefinition() || CD->hasTrivialDestructor(); |
| return true; |
| } |
| |
| /// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will |
| /// create add scope for automatic objects and temporary objects bound to |
| /// const reference. Will reuse Scope if not NULL. |
| LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD, |
| LocalScope* Scope) { |
| assert(!(BuildOpts.AddImplicitDtors && BuildOpts.AddLifetime) && |
| "AddImplicitDtors and AddLifetime cannot be used at the same time"); |
| if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime && |
| !BuildOpts.AddScopes) |
| return Scope; |
| |
| // Check if variable is local. |
| switch (VD->getStorageClass()) { |
| case SC_None: |
| case SC_Auto: |
| case SC_Register: |
| break; |
| default: return Scope; |
| } |
| |
| if (BuildOpts.AddImplicitDtors) { |
| if (!hasTrivialDestructor(VD) || BuildOpts.AddScopes) { |
| // Add the variable to scope |
| Scope = createOrReuseLocalScope(Scope); |
| Scope->addVar(VD); |
| ScopePos = Scope->begin(); |
| } |
| return Scope; |
| } |
| |
| assert(BuildOpts.AddLifetime); |
| // Add the variable to scope |
| Scope = createOrReuseLocalScope(Scope); |
| Scope->addVar(VD); |
| ScopePos = Scope->begin(); |
| return Scope; |
| } |
| |
| /// addLocalScopeAndDtors - For given statement add local scope for it and |
| /// add destructors that will cleanup the scope. Will reuse Scope if not NULL. |
| void CFGBuilder::addLocalScopeAndDtors(Stmt *S) { |
| LocalScope::const_iterator scopeBeginPos = ScopePos; |
| addLocalScopeForStmt(S); |
| addAutomaticObjHandling(ScopePos, scopeBeginPos, S); |
| } |
| |
| /// prependAutomaticObjDtorsWithTerminator - Prepend destructor CFGElements for |
| /// variables with automatic storage duration to CFGBlock's elements vector. |
| /// Elements will be prepended to physical beginning of the vector which |
| /// happens to be logical end. Use blocks terminator as statement that specifies |
| /// destructors call site. |
| /// FIXME: This mechanism for adding automatic destructors doesn't handle |
| /// no-return destructors properly. |
| void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk, |
| LocalScope::const_iterator B, LocalScope::const_iterator E) { |
| if (!BuildOpts.AddImplicitDtors) |
| return; |
| BumpVectorContext &C = cfg->getBumpVectorContext(); |
| CFGBlock::iterator InsertPos |
| = Blk->beginAutomaticObjDtorsInsert(Blk->end(), B.distance(E), C); |
| for (LocalScope::const_iterator I = B; I != E; ++I) |
| InsertPos = Blk->insertAutomaticObjDtor(InsertPos, *I, |
| Blk->getTerminatorStmt()); |
| } |
| |
| /// prependAutomaticObjLifetimeWithTerminator - Prepend lifetime CFGElements for |
| /// variables with automatic storage duration to CFGBlock's elements vector. |
| /// Elements will be prepended to physical beginning of the vector which |
| /// happens to be logical end. Use blocks terminator as statement that specifies |
| /// where lifetime ends. |
| void CFGBuilder::prependAutomaticObjLifetimeWithTerminator( |
| CFGBlock *Blk, LocalScope::const_iterator B, LocalScope::const_iterator E) { |
| if (!BuildOpts.AddLifetime) |
| return; |
| BumpVectorContext &C = cfg->getBumpVectorContext(); |
| CFGBlock::iterator InsertPos = |
| Blk->beginLifetimeEndsInsert(Blk->end(), B.distance(E), C); |
| for (LocalScope::const_iterator I = B; I != E; ++I) { |
| InsertPos = |
| Blk->insertLifetimeEnds(InsertPos, *I, Blk->getTerminatorStmt()); |
| } |
| } |
| |
| /// prependAutomaticObjScopeEndWithTerminator - Prepend scope end CFGElements for |
| /// variables with automatic storage duration to CFGBlock's elements vector. |
| /// Elements will be prepended to physical beginning of the vector which |
| /// happens to be logical end. Use blocks terminator as statement that specifies |
| /// where scope ends. |
| const VarDecl * |
| CFGBuilder::prependAutomaticObjScopeEndWithTerminator( |
| CFGBlock *Blk, LocalScope::const_iterator B, LocalScope::const_iterator E) { |
| if (!BuildOpts.AddScopes) |
| return nullptr; |
| BumpVectorContext &C = cfg->getBumpVectorContext(); |
| CFGBlock::iterator InsertPos = |
| Blk->beginScopeEndInsert(Blk->end(), 1, C); |
| LocalScope::const_iterator PlaceToInsert = B; |
| for (LocalScope::const_iterator I = B; I != E; ++I) |
| PlaceToInsert = I; |
| Blk->insertScopeEnd(InsertPos, *PlaceToInsert, Blk->getTerminatorStmt()); |
| return *PlaceToInsert; |
| } |
| |
| /// Visit - Walk the subtree of a statement and add extra |
| /// blocks for ternary operators, &&, and ||. We also process "," and |
| /// DeclStmts (which may contain nested control-flow). |
| CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc, |
| bool ExternallyDestructed) { |
| if (!S) { |
| badCFG = true; |
| return nullptr; |
| } |
| |
| if (Expr *E = dyn_cast<Expr>(S)) |
| S = E->IgnoreParens(); |
| |
| if (Context->getLangOpts().OpenMP) |
| if (auto *D = dyn_cast<OMPExecutableDirective>(S)) |
| return VisitOMPExecutableDirective(D, asc); |
| |
| switch (S->getStmtClass()) { |
| default: |
| return VisitStmt(S, asc); |
| |
| case Stmt::AddrLabelExprClass: |
| return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc); |
| |
| case Stmt::BinaryConditionalOperatorClass: |
| return VisitConditionalOperator(cast<BinaryConditionalOperator>(S), asc); |
| |
| case Stmt::BinaryOperatorClass: |
| return VisitBinaryOperator(cast<BinaryOperator>(S), asc); |
| |
| case Stmt::BlockExprClass: |
| return VisitBlockExpr(cast<BlockExpr>(S), asc); |
| |
| case Stmt::BreakStmtClass: |
| return VisitBreakStmt(cast<BreakStmt>(S)); |
| |
| case Stmt::CallExprClass: |
| case Stmt::CXXOperatorCallExprClass: |
| case Stmt::CXXMemberCallExprClass: |
| case Stmt::UserDefinedLiteralClass: |
| return VisitCallExpr(cast<CallExpr>(S), asc); |
| |
| case Stmt::CaseStmtClass: |
| return VisitCaseStmt(cast<CaseStmt>(S)); |
| |
| case Stmt::ChooseExprClass: |
| return VisitChooseExpr(cast<ChooseExpr>(S), asc); |
| |
| case Stmt::CompoundStmtClass: |
| return VisitCompoundStmt(cast<CompoundStmt>(S), ExternallyDestructed); |
| |
| case Stmt::ConditionalOperatorClass: |
| return VisitConditionalOperator(cast<ConditionalOperator>(S), asc); |
| |
| case Stmt::ContinueStmtClass: |
| return VisitContinueStmt(cast<ContinueStmt>(S)); |
| |
| case Stmt::CXXCatchStmtClass: |
| return VisitCXXCatchStmt(cast<CXXCatchStmt>(S)); |
| |
| case Stmt::ExprWithCleanupsClass: |
| return VisitExprWithCleanups(cast<ExprWithCleanups>(S), |
| asc, ExternallyDestructed); |
| |
| case Stmt::CXXDefaultArgExprClass: |
| case Stmt::CXXDefaultInitExprClass: |
| // FIXME: The expression inside a CXXDefaultArgExpr is owned by the |
| // called function's declaration, not by the caller. If we simply add |
| // this expression to the CFG, we could end up with the same Expr |
| // appearing multiple times. |
| // PR13385 / <rdar://problem/12156507> |
| // |
| // It's likewise possible for multiple CXXDefaultInitExprs for the same |
| // expression to be used in the same function (through aggregate |
| // initialization). |
| return VisitStmt(S, asc); |
| |
| case Stmt::CXXBindTemporaryExprClass: |
| return VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), asc); |
| |
| case Stmt::CXXConstructExprClass: |
| return VisitCXXConstructExpr(cast<CXXConstructExpr>(S), asc); |
| |
| case Stmt::CXXNewExprClass: |
| return VisitCXXNewExpr(cast<CXXNewExpr>(S), asc); |
| |
| case Stmt::CXXDeleteExprClass: |
| return VisitCXXDeleteExpr(cast<CXXDeleteExpr>(S), asc); |
| |
| case Stmt::CXXFunctionalCastExprClass: |
| return VisitCXXFunctionalCastExpr(cast<CXXFunctionalCastExpr>(S), asc); |
| |
| case Stmt::CXXTemporaryObjectExprClass: |
| return VisitCXXTemporaryObjectExpr(cast<CXXTemporaryObjectExpr>(S), asc); |
| |
| case Stmt::CXXThrowExprClass: |
| return VisitCXXThrowExpr(cast<CXXThrowExpr>(S)); |
| |
| case Stmt::CXXTryStmtClass: |
| return VisitCXXTryStmt(cast<CXXTryStmt>(S)); |
| |
| case Stmt::CXXForRangeStmtClass: |
| return VisitCXXForRangeStmt(cast<CXXForRangeStmt>(S)); |
| |
| case Stmt::DeclStmtClass: |
| return VisitDeclStmt(cast<DeclStmt>(S)); |
| |
| case Stmt::DefaultStmtClass: |
| return VisitDefaultStmt(cast<DefaultStmt>(S)); |
| |
| case Stmt::DoStmtClass: |
| return VisitDoStmt(cast<DoStmt>(S)); |
| |
| case Stmt::ForStmtClass: |
| return VisitForStmt(cast<ForStmt>(S)); |
| |
| case Stmt::GotoStmtClass: |
| return VisitGotoStmt(cast<GotoStmt>(S)); |
| |
| case Stmt::GCCAsmStmtClass: |
| return VisitGCCAsmStmt(cast<GCCAsmStmt>(S), asc); |
| |
| case Stmt::IfStmtClass: |
| return VisitIfStmt(cast<IfStmt>(S)); |
| |
| case Stmt::ImplicitCastExprClass: |
| return VisitImplicitCastExpr(cast<ImplicitCastExpr>(S), asc); |
| |
| case Stmt::ConstantExprClass: |
| return VisitConstantExpr(cast<ConstantExpr>(S), asc); |
| |
| case Stmt::IndirectGotoStmtClass: |
| return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S)); |
| |
| case Stmt::LabelStmtClass: |
| return VisitLabelStmt(cast<LabelStmt>(S)); |
| |
| case Stmt::LambdaExprClass: |
| return VisitLambdaExpr(cast<LambdaExpr>(S), asc); |
| |
| case Stmt::MaterializeTemporaryExprClass: |
| return VisitMaterializeTemporaryExpr(cast<MaterializeTemporaryExpr>(S), |
| asc); |
| |
| case Stmt::MemberExprClass: |
| return VisitMemberExpr(cast<MemberExpr>(S), asc); |
| |
| case Stmt::NullStmtClass: |
| return Block; |
| |
| case Stmt::ObjCAtCatchStmtClass: |
| return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S)); |
| |
| case Stmt::ObjCAutoreleasePoolStmtClass: |
| return VisitObjCAutoreleasePoolStmt(cast<ObjCAutoreleasePoolStmt>(S)); |
| |
| case Stmt::ObjCAtSynchronizedStmtClass: |
| return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S)); |
| |
| case Stmt::ObjCAtThrowStmtClass: |
| return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S)); |
| |
| case Stmt::ObjCAtTryStmtClass: |
| return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S)); |
| |
| case Stmt::ObjCForCollectionStmtClass: |
| return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S)); |
| |
| case Stmt::ObjCMessageExprClass: |
| return VisitObjCMessageExpr(cast<ObjCMessageExpr>(S), asc); |
| |
| case Stmt::OpaqueValueExprClass: |
| return Block; |
| |
| case Stmt::PseudoObjectExprClass: |
| return VisitPseudoObjectExpr(cast<PseudoObjectExpr>(S)); |
| |
| case Stmt::ReturnStmtClass: |
| case Stmt::CoreturnStmtClass: |
| return VisitReturnStmt(S); |
| |
| case Stmt::SEHExceptStmtClass: |
| return VisitSEHExceptStmt(cast<SEHExceptStmt>(S)); |
| |
| case Stmt::SEHFinallyStmtClass: |
| return VisitSEHFinallyStmt(cast<SEHFinallyStmt>(S)); |
| |
| case Stmt::SEHLeaveStmtClass: |
| return VisitSEHLeaveStmt(cast<SEHLeaveStmt>(S)); |
| |
| case Stmt::SEHTryStmtClass: |
| return VisitSEHTryStmt(cast<SEHTryStmt>(S)); |
| |
| case Stmt::UnaryExprOrTypeTraitExprClass: |
| return VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S), |
| asc); |
| |
| case Stmt::StmtExprClass: |
| return VisitStmtExpr(cast<StmtExpr>(S), asc); |
| |
| case Stmt::SwitchStmtClass: |
| return VisitSwitchStmt(cast<SwitchStmt>(S)); |
| |
| case Stmt::UnaryOperatorClass: |
| return VisitUnaryOperator(cast<UnaryOperator>(S), asc); |
| |
| case Stmt::WhileStmtClass: |
| return VisitWhileStmt(cast<WhileStmt>(S)); |
| } |
| } |
| |
| CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) { |
| if (asc.alwaysAdd(*this, S)) { |
| autoCreateBlock(); |
| appendStmt(Block, S); |
| } |
| |
| return VisitChildren(S); |
| } |
| |
| /// VisitChildren - Visit the children of a Stmt. |
| CFGBlock *CFGBuilder::VisitChildren(Stmt *S) { |
| CFGBlock *B = Block; |
| |
| // Visit the children in their reverse order so that they appear in |
| // left-to-right (natural) order in the CFG. |
| reverse_children RChildren(S); |
| for (reverse_children::iterator I = RChildren.begin(), E = RChildren.end(); |
| I != E; ++I) { |
| if (Stmt *Child = *I) |
| if (CFGBlock *R = Visit(Child)) |
| B = R; |
| } |
| return B; |
| } |
| |
| CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A, |
| AddStmtChoice asc) { |
| AddressTakenLabels.insert(A->getLabel()); |
| |
| if (asc.alwaysAdd(*this, A)) { |
| autoCreateBlock(); |
| appendStmt(Block, A); |
| } |
| |
| return Block; |
| } |
| |
| CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U, |
| AddStmtChoice asc) { |
| if (asc.alwaysAdd(*this, U)) { |
| autoCreateBlock(); |
| appendStmt(Block, U); |
| } |
| |
| return Visit(U->getSubExpr(), AddStmtChoice()); |
| } |
| |
| CFGBlock *CFGBuilder::VisitLogicalOperator(BinaryOperator *B) { |
| CFGBlock *ConfluenceBlock = Block ? Block : createBlock(); |
| appendStmt(ConfluenceBlock, B); |
| |
| if (badCFG) |
| return nullptr; |
| |
| return VisitLogicalOperator(B, nullptr, ConfluenceBlock, |
| ConfluenceBlock).first; |
| } |
| |
| std::pair<CFGBlock*, CFGBlock*> |
| CFGBuilder::VisitLogicalOperator(BinaryOperator *B, |
| Stmt *Term, |
| CFGBlock *TrueBlock, |
| CFGBlock *FalseBlock) { |
| // Introspect the RHS. If it is a nested logical operation, we recursively |
| // build the CFG using this function. Otherwise, resort to default |
| // CFG construction behavior. |
| Expr *RHS = B->getRHS()->IgnoreParens(); |
| CFGBlock *RHSBlock, *ExitBlock; |
| |
| do { |
| if (BinaryOperator *B_RHS = dyn_cast<BinaryOperator>(RHS)) |
| if (B_RHS->isLogicalOp()) { |
| std::tie(RHSBlock, ExitBlock) = |
| VisitLogicalOperator(B_RHS, Term, TrueBlock, FalseBlock); |
| break; |
| } |
| |
| // The RHS is not a nested logical operation. Don't push the terminator |
| // down further, but instead visit RHS and construct the respective |
| // pieces of the CFG, and link up the RHSBlock with the terminator |
| // we have been provided. |
| ExitBlock = RHSBlock = createBlock(false); |
| |
| // Even though KnownVal is only used in the else branch of the next |
| // conditional, tryEvaluateBool performs additional checking on the |
| // Expr, so it should be called unconditionally. |
| TryResult KnownVal = tryEvaluateBool(RHS); |
| if (!KnownVal.isKnown()) |
| KnownVal = tryEvaluateBool(B); |
| |
| if (!Term) { |
| assert(TrueBlock == FalseBlock); |
| addSuccessor(RHSBlock, TrueBlock); |
| } |
| else { |
| RHSBlock->setTerminator(Term); |
| addSuccessor(RHSBlock, TrueBlock, !KnownVal.isFalse()); |
| addSuccessor(RHSBlock, FalseBlock, !KnownVal.isTrue()); |
| } |
| |
| Block = RHSBlock; |
| RHSBlock = addStmt(RHS); |
| } |
| while (false); |
| |
| if (badCFG) |
| return std::make_pair(nullptr, nullptr); |
| |
| // Generate the blocks for evaluating the LHS. |
| Expr *LHS = B->getLHS()->IgnoreParens(); |
| |
| if (BinaryOperator *B_LHS = dyn_cast<BinaryOperator>(LHS)) |
| if (B_LHS->isLogicalOp()) { |
| if (B->getOpcode() == BO_LOr) |
| FalseBlock = RHSBlock; |
| else |
| TrueBlock = RHSBlock; |
| |
| // For the LHS, treat 'B' as the terminator that we want to sink |
| // into the nested branch. The RHS always gets the top-most |
| // terminator. |
| return VisitLogicalOperator(B_LHS, B, TrueBlock, FalseBlock); |
| } |
| |
| // Create the block evaluating the LHS. |
| // This contains the '&&' or '||' as the terminator. |
| CFGBlock *LHSBlock = createBlock(false); |
| LHSBlock->setTerminator(B); |
| |
| Block = LHSBlock; |
| CFGBlock *EntryLHSBlock = addStmt(LHS); |
| |
| if (badCFG) |
| return std::make_pair(nullptr, nullptr); |
| |
| // See if this is a known constant. |
| TryResult KnownVal = tryEvaluateBool(LHS); |
| |
| // Now link the LHSBlock with RHSBlock. |
| if (B->getOpcode() == BO_LOr) { |
| addSuccessor(LHSBlock, TrueBlock, !KnownVal.isFalse()); |
| addSuccessor(LHSBlock, RHSBlock, !KnownVal.isTrue()); |
| } else { |
| assert(B->getOpcode() == BO_LAnd); |
| addSuccessor(LHSBlock, RHSBlock, !KnownVal.isFalse()); |
| addSuccessor(LHSBlock, FalseBlock, !KnownVal.isTrue()); |
| } |
| |
| return std::make_pair(EntryLHSBlock, ExitBlock); |
| } |
| |
| CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, |
| AddStmtChoice asc) { |
| // && or || |
| if (B->isLogicalOp()) |
| return VisitLogicalOperator(B); |
| |
| if (B->getOpcode() == BO_Comma) { // , |
| autoCreateBlock(); |
| appendStmt(Block, B); |
| addStmt(B->getRHS()); |
| return addStmt(B->getLHS()); |
| } |
| |
| if (B->isAssignmentOp()) { |
| if (asc.alwaysAdd(*this, B)) { |
| autoCreateBlock(); |
| appendStmt(Block, B); |
| } |
| Visit(B->getLHS()); |
| return Visit(B->getRHS()); |
| } |
| |
| if (asc.alwaysAdd(*this, B)) { |
| autoCreateBlock(); |
| appendStmt(Block, B); |
| } |
| |
| CFGBlock *RBlock = Visit(B->getRHS()); |
| CFGBlock *LBlock = Visit(B->getLHS()); |
| // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr |
| // containing a DoStmt, and the LHS doesn't create a new block, then we should |
| // return RBlock. Otherwise we'll incorrectly return NULL. |
| return (LBlock ? LBlock : RBlock); |
| } |
| |
| CFGBlock *CFGBuilder::VisitNoRecurse(Expr *E, AddStmtChoice asc) { |
| if (asc.alwaysAdd(*this, E)) { |
| autoCreateBlock(); |
| appendStmt(Block, E); |
| } |
| return Block; |
| } |
| |
| CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) { |
| // "break" is a control-flow statement. Thus we stop processing the current |
| // block. |
| if (badCFG) |
| return nullptr; |
| |
| // Now create a new block that ends with the break statement. |
| Block = createBlock(false); |
| Block->setTerminator(B); |
| |
| // If there is no target for the break, then we are looking at an incomplete |
| // AST. This means that the CFG cannot be constructed. |
| if (BreakJumpTarget.block) { |
| addAutomaticObjHandling(ScopePos, BreakJumpTarget.scopePosition, B); |
| addSuccessor(Block, BreakJumpTarget.block); |
| } else |
| badCFG = true; |
| |
| return Block; |
| } |
| |
| static bool CanThrow(Expr *E, ASTContext &Ctx) { |
| QualType Ty = E->getType(); |
| if (Ty->isFunctionPointerType() || Ty->isBlockPointerType()) |
| Ty = Ty->getPointeeType(); |
| |
| const FunctionType *FT = Ty->getAs<FunctionType>(); |
| if (FT) { |
| if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT)) |
| if (!isUnresolvedExceptionSpec(Proto->getExceptionSpecType()) && |
| Proto->isNothrow()) |
| return false; |
| } |
| return true; |
| } |
| |
| CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { |
| // Compute the callee type. |
| QualType calleeType = C->getCallee()->getType(); |
| if (calleeType == Context->BoundMemberTy) { |
| QualType boundType = Expr::findBoundMemberType(C->getCallee()); |
| |
| // We should only get a null bound type if processing a dependent |
| // CFG. Recover by assuming nothing. |
| if (!boundType.isNull()) calleeType = boundType; |
| } |
| |
| // If this is a call to a no-return function, this stops the block here. |
| bool NoReturn = getFunctionExtInfo(*calleeType).getNoReturn(); |
| |
| bool AddEHEdge = false; |
| |
| // Languages without exceptions are assumed to not throw. |
| if (Context->getLangOpts().Exceptions) { |
| if (BuildOpts.AddEHEdges) |
| AddEHEdge = true; |
| } |
| |
| // If this is a call to a builtin function, it might not actually evaluate |
| // its arguments. Don't add them to the CFG if this is the case. |
| bool OmitArguments = false; |
| |
| if (FunctionDecl *FD = C->getDirectCallee()) { |
| // TODO: Support construction contexts for variadic function arguments. |
| // These are a bit problematic and not very useful because passing |
| // C++ objects as C-style variadic arguments doesn't work in general |
| // (see [expr.call]). |
| if (!FD->isVariadic()) |
| findConstructionContextsForArguments(C); |
| |
| if (FD->isNoReturn() || C->isBuiltinAssumeFalse(*Context)) |
| NoReturn = true; |
| if (FD->hasAttr<NoThrowAttr>()) |
| AddEHEdge = false; |
| if (FD->getBuiltinID() == Builtin::BI__builtin_object_size || |
| FD->getBuiltinID() == Builtin::BI__builtin_dynamic_object_size) |
| OmitArguments = true; |
| } |
| |
| if (!CanThrow(C->getCallee(), *Context)) |
| AddEHEdge = false; |
| |
| if (OmitArguments) { |
| assert(!NoReturn && "noreturn calls with unevaluated args not implemented"); |
| assert(!AddEHEdge && "EH calls with unevaluated args not implemented"); |
| autoCreateBlock(); |
| appendStmt(Block, C); |
| return Visit(C->getCallee()); |
| } |
| |
| if (!NoReturn && !AddEHEdge) { |
| autoCreateBlock(); |
| appendCall(Block, C); |
| |
| return VisitChildren(C); |
| } |
| |
| if (Block) { |
| Succ = Block; |
| if (badCFG) |
| return nullptr; |
| } |
| |
| if (NoReturn) |
| Block = createNoReturnBlock(); |
| else |
| Block = createBlock(); |
| |
| appendCall(Block, C); |
| |
| if (AddEHEdge) { |
| // Add exceptional edges. |
| if (TryTerminatedBlock) |
| addSuccessor(Block, TryTerminatedBlock); |
| else |
| addSuccessor(Block, &cfg->getExit()); |
| } |
| |
| return VisitChildren(C); |
| } |
| |
| CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C, |
| AddStmtChoice asc) { |
| CFGBlock *ConfluenceBlock = Block ? Block : createBlock(); |
| appendStmt(ConfluenceBlock, C); |
| if (badCFG) |
| return nullptr; |
| |
| AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true); |
| Succ = ConfluenceBlock; |
| Block = nullptr; |
| CFGBlock *LHSBlock = Visit(C->getLHS(), alwaysAdd); |
| if (badCFG) |
| return nullptr; |
| |
| Succ = ConfluenceBlock; |
| Block = nullptr; |
| CFGBlock *RHSBlock = Visit(C->getRHS(), alwaysAdd); |
| if (badCFG) |
| return nullptr; |
| |
| Block = createBlock(false); |
| // See if this is a known constant. |
| const TryResult& KnownVal = tryEvaluateBool(C->getCond()); |
| addSuccessor(Block, KnownVal.isFalse() ? nullptr : LHSBlock); |
| addSuccessor(Block, KnownVal.isTrue() ? nullptr : RHSBlock); |
| Block->setTerminator(C); |
| return addStmt(C->getCond()); |
| } |
| |
| CFGBlock *CFGBuilder::VisitCompoundStmt(CompoundStmt *C, bool ExternallyDestructed) { |
| LocalScope::const_iterator scopeBeginPos = ScopePos; |
| addLocalScopeForStmt(C); |
| |
| if (!C->body_empty() && !isa<ReturnStmt>(*C->body_rbegin())) { |
| // If the body ends with a ReturnStmt, the dtors will be added in |
| // VisitReturnStmt. |
| addAutomaticObjHandling(ScopePos, scopeBeginPos, C); |
| } |
| |
| CFGBlock *LastBlock = Block; |
| |
| for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); |
| I != E; ++I ) { |
| // If we hit a segment of code just containing ';' (NullStmts), we can |
| // get a null block back. In such cases, just use the LastBlock |
| CFGBlock *newBlock = Visit(*I, AddStmtChoice::AlwaysAdd, |
| ExternallyDestructed); |
| |
| if (newBlock) |
| LastBlock = newBlock; |
| |
| if (badCFG) |
| return nullptr; |
| |
| ExternallyDestructed = false; |
| } |
| |
| return LastBlock; |
| } |
| |
| CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C, |
| AddStmtChoice asc) { |
| const BinaryConditionalOperator *BCO = dyn_cast<BinaryConditionalOperator>(C); |
| const OpaqueValueExpr *opaqueValue = (BCO ? BCO->getOpaqueValue() : nullptr); |
| |
| // Create the confluence block that will "merge" the results of the ternary |
| // expression. |
| CFGBlock *ConfluenceBlock = Block ? Block : createBlock(); |
| appendStmt(ConfluenceBlock, C); |
| if (badCFG) |
| return nullptr; |
| |
| AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true); |
| |
| // Create a block for the LHS expression if there is an LHS expression. A |
| // GCC extension allows LHS to be NULL, causing the condition to be the |
| // value that is returned instead. |
| // e.g: x ?: y is shorthand for: x ? x : y; |
| Succ = ConfluenceBlock; |
| Block = nullptr; |
| CFGBlock *LHSBlock = nullptr; |
| const Expr *trueExpr = C->getTrueExpr(); |
| if (trueExpr != opaqueValue) { |
| LHSBlock = Visit(C->getTrueExpr(), alwaysAdd); |
| if (badCFG) |
| return nullptr; |
| Block = nullptr; |
| } |
| else |
| LHSBlock = ConfluenceBlock; |
| |
| // Create the block for the RHS expression. |
| Succ = ConfluenceBlock; |
| CFGBlock *RHSBlock = Visit(C->getFalseExpr(), alwaysAdd); |
| if (badCFG) |
| return nullptr; |
| |
| // If the condition is a logical '&&' or '||', build a more accurate CFG. |
| if (BinaryOperator *Cond = |
| dyn_cast<BinaryOperator>(C->getCond()->IgnoreParens())) |
| if (Cond->isLogicalOp()) |
| return VisitLogicalOperator(Cond, C, LHSBlock, RHSBlock).first; |
| |
| // Create the block that will contain the condition. |
| Block = createBlock(false); |
| |
| // See if this is a known constant. |
| const TryResult& KnownVal = tryEvaluateBool(C->getCond()); |
| addSuccessor(Block, LHSBlock, !KnownVal.isFalse()); |
| addSuccessor(Block, RHSBlock, !KnownVal.isTrue()); |
| Block->setTerminator(C); |
| Expr *condExpr = C->getCond(); |
| |
| if (opaqueValue) { |
| // Run the condition expression if it's not trivially expressed in |
| // terms of the opaque value (or if there is no opaque value). |
| if (condExpr != opaqueValue) |
| addStmt(condExpr); |
| |
| // Before that, run the common subexpression if there was one. |
| // At least one of this or the above will be run. |
| return addStmt(BCO->getCommon()); |
| } |
| |
| return addStmt(condExpr); |
| } |
| |
| CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) { |
| // Check if the Decl is for an __label__. If so, elide it from the |
| // CFG entirely. |
| if (isa<LabelDecl>(*DS->decl_begin())) |
| return Block; |
| |
| // This case also handles static_asserts. |
| if (DS->isSingleDecl()) |
| return VisitDeclSubExpr(DS); |
| |
| CFGBlock *B = nullptr; |
| |
| // Build an individual DeclStmt for each decl. |
| for (DeclStmt::reverse_decl_iterator I = DS->decl_rbegin(), |
| E = DS->decl_rend(); |
| I != E; ++I) { |
| |
| // Allocate the DeclStmt using the BumpPtrAllocator. It will get |
| // automatically freed with the CFG. |
| DeclGroupRef DG(*I); |
| Decl *D = *I; |
| DeclStmt *DSNew = new (Context) DeclStmt(DG, D->getLocation(), GetEndLoc(D)); |
| cfg->addSyntheticDeclStmt(DSNew, DS); |
| |
| // Append the fake DeclStmt to block. |
| B = VisitDeclSubExpr(DSNew); |
| } |
| |
| return B; |
| } |
| |
| /// VisitDeclSubExpr - Utility method to add block-level expressions for |
| /// DeclStmts and initializers in them. |
| CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) { |
| assert(DS->isSingleDecl() && "Can handle single declarations only."); |
| VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl()); |
| |
| if (!VD) { |
| // Of everything that can be declared in a DeclStmt, only VarDecls impact |
| // runtime semantics. |
| return Block; |
| } |
| |
| bool HasTemporaries = false; |
| |
| // Guard static initializers under a branch. |
| CFGBlock *blockAfterStaticInit = nullptr; |
| |
| if (BuildOpts.AddStaticInitBranches && VD->isStaticLocal()) { |
| // For static variables, we need to create a branch to track |
| // whether or not they are initialized. |
| if (Block) { |
| Succ = Block; |
| Block = nullptr; |
| if (badCFG) |
| return nullptr; |
| } |
| blockAfterStaticInit = Succ; |
| } |
| |
| // Destructors of temporaries in initialization expression should be called |
| // after initialization finishes. |
| Expr *Init = VD->getInit(); |
| if (Init) { |
| HasTemporaries = isa<ExprWithCleanups>(Init); |
| |
| if (BuildOpts.AddTemporaryDtors && HasTemporaries) { |
| // Generate destructors for temporaries in initialization expression. |
| TempDtorContext Context; |
| VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(), |
| /*ExternallyDestructed=*/true, Context); |
| } |
| } |
| |
| autoCreateBlock(); |
| appendStmt(Block, DS); |
| |
| findConstructionContexts( |
| ConstructionContextLayer::create(cfg->getBumpVectorContext(), DS), |
| |