CFG.cpp

//===- 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>

usingnamespaceclang;

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.
staticboolIsIntegerLiteralConstantExpr(const Expr *E) {
// Allow parentheses
 E = E->IgnoreParens();

// Allow conversions to different integer kind.
if (constauto *CE = dyn_cast<CastExpr>(E)) {
if (CE->getCastKind() != CK_IntegralCast)
returnfalse;
 E = CE->getSubExpr();
 }

// Allow negative numbers.
if (constauto *UO = dyn_cast<UnaryOperator>(E)) {
if (UO->getOpcode() != UO_Minus)
returnfalse;
 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.
staticconst 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;
returnnullptr;
}

/// 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;
elseif (Op == BO_GE)
 Op = BO_LE;
elseif (Op == BO_LT)
 Op = BO_GT;
elseif (Op == BO_LE)
 Op = BO_GE;

 MaybeDecl = B->getRHS();
 Constant = tryTransformToIntOrEnumConstant(B->getLHS());
 }

returnstd::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)
staticboolareExprTypesCompatible(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))
returnfalse;

// Integer literal comparisons, regardless of literal type, are acceptable.
if (!isa<DeclRefExpr>(E1))
returntrue;

// 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 {

classCFGBuilder;

/// 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.
classAddStmtChoice {
public:
enum Kind { NotAlwaysAdd = 0, AlwaysAdd = 1 };

AddStmtChoice(Kind a_kind = NotAlwaysAdd) : kind(a_kind) {}

boolalwaysAdd(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 {
returnAddStmtChoice(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),
///
classLocalScope {
public:
using AutomaticVarsTy = BumpVector<VarDecl *>;

/// const_iterator - Iterates local scope backwards and jumps to previous
/// scope on reaching the beginning of currently iterated scope.
classconst_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;
 }

booloperator==(const const_iterator &rhs) const {
return Scope == rhs.Scope && VarIter == rhs.VarIter;
 }
booloperator!=(const const_iterator &rhs) const {
return !(*this == rhs);
 }

explicitoperatorbool() const {
return *this != const_iterator();
 }

intdistance(const_iterator L);
 const_iterator shared_parent(const_iterator L);
boolpointsToFirstDeclaredVar() { 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 { returnconst_iterator(*this, Vars.size()); }

voidaddVar(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.
intLocalScope::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.
structBlockScopePosPair {
 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.
classTryResult {
int X = -1;

public:
TryResult() = default;
TryResult(bool b) : X(b ? 1 : 0) {}

boolisTrue() const { return X == 1; }
boolisFalse() const { return X == 0; }
boolisKnown() const { return X >= 0; }

voidnegate() {
assert(isKnown());
 X ^= 0x1;
 }
};

} // namespace

static TryResult bothKnownTrue(TryResult R1, TryResult R2) {
if (!R1.isKnown() || !R2.isKnown())
returnTryResult();
returnTryResult(R1.isTrue() && R2.isTrue());
}

namespace {

classreverse_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.
classCFGBuilder {
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:
explicitCFGBuilder(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);

boolalwaysAdd(const Stmt *stmt);

private:
// Visitors to walk an AST and construct the CFG.
 CFGBlock *VisitInitListExpr(InitListExpr *ILE, AddStmtChoice asc);
 CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc);
 CFGBlock *VisitAttributedStmt(AttributedStmt *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);

voidmaybeAddScopeBeginForVarDecl(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.
structTempDtorContext {
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.
boolneedsTempDtorBranch() const {
return IsConditional && !TerminatorExpr;
 }

/// Remember the successor S of a temporary destructor decision branch for
/// the corresponding CXXBindTemporaryExpr E.
voidsetDecisionPoint(CFGBlock *S, CXXBindTemporaryExpr *E) {
 Succ = S;
 TerminatorExpr = E;
 }

constbool 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);
voidInsertTempDtorDecisionBlock(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.
voidconsumeConstructionContext(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.
voidfindConstructionContexts(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 = std::enable_if_t<
 std::is_base_of<CallExpr, CallLikeExpr>::value ||
 std::is_base_of<CXXConstructExpr, CallLikeExpr>::value ||
 std::is_base_of<ObjCMessageExpr, CallLikeExpr>::value>>
voidfindConstructionContextsForArguments(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.
voidcleanupConstructionContext(Expr *E);

voidautoCreateBlock() { if (!Block) Block = createBlock(); }
 CFGBlock *createBlock(bool add_successor = true);
 CFGBlock *createNoReturnBlock();

 CFGBlock *addStmt(Stmt *S) {
returnVisit(S, AddStmtChoice::AlwaysAdd);
 }

 CFGBlock *addInitializer(CXXCtorInitializer *I);
voidaddLoopExit(const Stmt *LoopStmt);
voidaddAutomaticObjDtors(LocalScope::const_iterator B,
 LocalScope::const_iterator E, Stmt *S);
voidaddLifetimeEnds(LocalScope::const_iterator B,
 LocalScope::const_iterator E, Stmt *S);
voidaddAutomaticObjHandling(LocalScope::const_iterator B,
 LocalScope::const_iterator E, Stmt *S);
voidaddImplicitDtorsForDestructor(const CXXDestructorDecl *DD);
voidaddScopesEnd(LocalScope::const_iterator B, LocalScope::const_iterator E,
 Stmt *S);

voidgetDeclsWithEndedScope(LocalScope::const_iterator B,
 LocalScope::const_iterator E, Stmt *S);

// Local scopes creation.
 LocalScope* createOrReuseLocalScope(LocalScope* Scope);

voidaddLocalScopeForStmt(Stmt *S);
 LocalScope* addLocalScopeForDeclStmt(DeclStmt *DS,
 LocalScope* Scope = nullptr);
 LocalScope* addLocalScopeForVarDecl(VarDecl *VD, LocalScope* Scope = nullptr);

voidaddLocalScopeAndDtors(Stmt *S);

const ConstructionContext *retrieveAndCleanupConstructionContext(Expr *E) {
if (!BuildOpts.AddRichCXXConstructors)
returnnullptr;

const ConstructionContextLayer *Layer = ConstructionContextMap.lookup(E);
if (!Layer)
returnnullptr;

cleanupConstructionContext(E);
returnConstructionContext::createFromLayers(cfg->getBumpVectorContext(),
 Layer);
 }

// Interface to CFGBlock - adding CFGElements.

voidappendStmt(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());
 }

voidappendConstructor(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());
 }

voidappendCall(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());
 }

voidappendInitializer(CFGBlock *B, CXXCtorInitializer *I) {
 B->appendInitializer(I, cfg->getBumpVectorContext());
 }

voidappendNewAllocator(CFGBlock *B, CXXNewExpr *NE) {
 B->appendNewAllocator(NE, cfg->getBumpVectorContext());
 }

voidappendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) {
 B->appendBaseDtor(BS, cfg->getBumpVectorContext());
 }

voidappendMemberDtor(CFGBlock *B, FieldDecl *FD) {
 B->appendMemberDtor(FD, cfg->getBumpVectorContext());
 }

voidappendObjCMessage(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());
 }

voidappendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) {
 B->appendTemporaryDtor(E, cfg->getBumpVectorContext());
 }

voidappendAutomaticObjDtor(CFGBlock *B, VarDecl *VD, Stmt *S) {
 B->appendAutomaticObjDtor(VD, S, cfg->getBumpVectorContext());
 }

voidappendLifetimeEnds(CFGBlock *B, VarDecl *VD, Stmt *S) {
 B->appendLifetimeEnds(VD, S, cfg->getBumpVectorContext());
 }

voidappendLoopExit(CFGBlock *B, const Stmt *LoopStmt) {
 B->appendLoopExit(LoopStmt, cfg->getBumpVectorContext());
 }

voidappendDeleteDtor(CFGBlock *B, CXXRecordDecl *RD, CXXDeleteExpr *DE) {
 B->appendDeleteDtor(RD, DE, cfg->getBumpVectorContext());
 }

voidprependAutomaticObjDtorsWithTerminator(CFGBlock *Blk,
 LocalScope::const_iterator B, LocalScope::const_iterator E);

voidprependAutomaticObjLifetimeWithTerminator(CFGBlock *Blk,
 LocalScope::const_iterator B,
 LocalScope::const_iterator E);

const VarDecl *
prependAutomaticObjScopeEndWithTerminator(CFGBlock *Blk,
 LocalScope::const_iterator B,
 LocalScope::const_iterator E);

voidaddSuccessor(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.
voidaddSuccessor(CFGBlock *B, CFGBlock *ReachableBlock, CFGBlock *AltBlock) {
 B->addSuccessor(CFGBlock::AdjacentBlock(ReachableBlock, AltBlock),
 cfg->getBumpVectorContext());
 }

voidappendScopeBegin(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
if (BuildOpts.AddScopes)
 B->appendScopeBegin(VD, S, cfg->getBumpVectorContext());
 }

voidprependScopeBegin(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
if (BuildOpts.AddScopes)
 B->prependScopeBegin(VD, S, cfg->getBumpVectorContext());
 }

voidappendScopeEnd(CFGBlock *B, const VarDecl *VD, const Stmt *S) {
if (BuildOpts.AddScopes)
 B->appendScopeEnd(VD, S, cfg->getBumpVectorContext());
 }

voidprependScopeEnd(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())
returnTryResult();

 llvm::APInt IntValue = IntLiteral->getValue();
if ((IntValue == 1) || (IntValue == 0))
returnTryResult();

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
returnTryResult(IntFirst == IntLarger);
 } else {
// Always true for -1 < bool and bool < 10
// Always false for 10 < bool and bool < -1
returnTryResult(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)
returnTryResult();

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)
returnTryResult();

 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);
 }
 } elseif (BoolExpr->isKnownToHaveBooleanValue()) {
 llvm::APInt IntValue = IntLiteral->getValue();
if ((IntValue == 1) || (IntValue == 0)) {