brintos / llvm-project-archived public Read only

1//===- CFG.cpp - Classes for representing and building CFGs ---------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8//9//  This file defines the CFG and CFGBuilder classes for representing and10//  building Control-Flow Graphs (CFGs) from ASTs.11//12//===----------------------------------------------------------------------===//13 14#include "clang/Analysis/CFG.h"15#include "clang/AST/ASTContext.h"16#include "clang/AST/Attr.h"17#include "clang/AST/Decl.h"18#include "clang/AST/DeclBase.h"19#include "clang/AST/DeclCXX.h"20#include "clang/AST/DeclGroup.h"21#include "clang/AST/Expr.h"22#include "clang/AST/ExprCXX.h"23#include "clang/AST/OperationKinds.h"24#include "clang/AST/PrettyPrinter.h"25#include "clang/AST/Stmt.h"26#include "clang/AST/StmtCXX.h"27#include "clang/AST/StmtObjC.h"28#include "clang/AST/StmtVisitor.h"29#include "clang/AST/Type.h"30#include "clang/Analysis/ConstructionContext.h"31#include "clang/Analysis/Support/BumpVector.h"32#include "clang/Basic/Builtins.h"33#include "clang/Basic/ExceptionSpecificationType.h"34#include "clang/Basic/JsonSupport.h"35#include "clang/Basic/LLVM.h"36#include "clang/Basic/LangOptions.h"37#include "clang/Basic/SourceLocation.h"38#include "clang/Basic/Specifiers.h"39#include "llvm/ADT/APFloat.h"40#include "llvm/ADT/APInt.h"41#include "llvm/ADT/APSInt.h"42#include "llvm/ADT/ArrayRef.h"43#include "llvm/ADT/DenseMap.h"44#include "llvm/ADT/STLExtras.h"45#include "llvm/ADT/SetVector.h"46#include "llvm/ADT/SmallPtrSet.h"47#include "llvm/ADT/SmallVector.h"48#include "llvm/Support/Allocator.h"49#include "llvm/Support/Compiler.h"50#include "llvm/Support/DOTGraphTraits.h"51#include "llvm/Support/ErrorHandling.h"52#include "llvm/Support/Format.h"53#include "llvm/Support/GraphWriter.h"54#include "llvm/Support/SaveAndRestore.h"55#include "llvm/Support/raw_ostream.h"56#include <cassert>57#include <memory>58#include <optional>59#include <string>60#include <tuple>61#include <utility>62#include <vector>63 64using namespace clang;65 66static SourceLocation GetEndLoc(Decl *D) {67  if (VarDecl *VD = dyn_cast<VarDecl>(D))68    if (Expr *Ex = VD->getInit())69      return Ex->getSourceRange().getEnd();70  return D->getLocation();71}72 73/// Returns true on constant values based around a single IntegerLiteral,74/// CharacterLiteral, or FloatingLiteral. Allow for use of parentheses, integer75/// casts, and negative signs.76 77static bool IsLiteralConstantExpr(const Expr *E) {78  // Allow parentheses79  E = E->IgnoreParens();80 81  // Allow conversions to different integer kind, and integer to floating point82  // (to account for float comparing with int).83  if (const auto *CE = dyn_cast<CastExpr>(E)) {84    if (CE->getCastKind() != CK_IntegralCast &&85        CE->getCastKind() != CK_IntegralToFloating)86      return false;87    E = CE->getSubExpr();88  }89 90  // Allow negative numbers.91  if (const auto *UO = dyn_cast<UnaryOperator>(E)) {92    if (UO->getOpcode() != UO_Minus)93      return false;94    E = UO->getSubExpr();95  }96  return isa<IntegerLiteral, CharacterLiteral, FloatingLiteral>(E);97}98 99/// Helper for tryNormalizeBinaryOperator. Attempts to extract an IntegerLiteral100/// FloatingLiteral, CharacterLiteral or EnumConstantDecl from the given Expr.101/// If it fails, returns nullptr.102static const Expr *tryTransformToLiteralConstant(const Expr *E) {103  E = E->IgnoreParens();104  if (IsLiteralConstantExpr(E))105    return E;106  if (auto *DR = dyn_cast<DeclRefExpr>(E->IgnoreParenImpCasts()))107    return isa<EnumConstantDecl>(DR->getDecl()) ? DR : nullptr;108  return nullptr;109}110 111/// Tries to interpret a binary operator into `Expr Op NumExpr` form, if112/// NumExpr is an integer literal or an enum constant.113///114/// If this fails, at least one of the returned DeclRefExpr or Expr will be115/// null.116static std::tuple<const Expr *, BinaryOperatorKind, const Expr *>117tryNormalizeBinaryOperator(const BinaryOperator *B) {118  BinaryOperatorKind Op = B->getOpcode();119 120  const Expr *MaybeDecl = B->getLHS();121  const Expr *Constant = tryTransformToLiteralConstant(B->getRHS());122  // Expr looked like `0 == Foo` instead of `Foo == 0`123  if (Constant == nullptr) {124    // Flip the operator125    if (Op == BO_GT)126      Op = BO_LT;127    else if (Op == BO_GE)128      Op = BO_LE;129    else if (Op == BO_LT)130      Op = BO_GT;131    else if (Op == BO_LE)132      Op = BO_GE;133 134    MaybeDecl = B->getRHS();135    Constant = tryTransformToLiteralConstant(B->getLHS());136  }137 138  return std::make_tuple(MaybeDecl, Op, Constant);139}140 141/// For an expression `x == Foo && x == Bar`, this determines whether the142/// `Foo` and `Bar` are either of the same enumeration type, or both integer143/// literals.144///145/// It's an error to pass this arguments that are not either IntegerLiterals146/// or DeclRefExprs (that have decls of type EnumConstantDecl)147static bool areExprTypesCompatible(const Expr *E1, const Expr *E2) {148  // User intent isn't clear if they're mixing int literals with enum149  // constants.150  if (isa<DeclRefExpr>(E1) != isa<DeclRefExpr>(E2))151    return false;152 153  // Integer literal comparisons, regardless of literal type, are acceptable.154  if (!isa<DeclRefExpr>(E1))155    return true;156 157  // IntegerLiterals are handled above and only EnumConstantDecls are expected158  // beyond this point159  assert(isa<DeclRefExpr>(E1) && isa<DeclRefExpr>(E2));160  auto *Decl1 = cast<DeclRefExpr>(E1)->getDecl();161  auto *Decl2 = cast<DeclRefExpr>(E2)->getDecl();162 163  assert(isa<EnumConstantDecl>(Decl1) && isa<EnumConstantDecl>(Decl2));164  const DeclContext *DC1 = Decl1->getDeclContext();165  const DeclContext *DC2 = Decl2->getDeclContext();166 167  assert(isa<EnumDecl>(DC1) && isa<EnumDecl>(DC2));168  return DC1 == DC2;169}170 171namespace {172 173class CFGBuilder;174 175/// The CFG builder uses a recursive algorithm to build the CFG.  When176///  we process an expression, sometimes we know that we must add the177///  subexpressions as block-level expressions.  For example:178///179///    exp1 || exp2180///181///  When processing the '||' expression, we know that exp1 and exp2182///  need to be added as block-level expressions, even though they183///  might not normally need to be.  AddStmtChoice records this184///  contextual information.  If AddStmtChoice is 'NotAlwaysAdd', then185///  the builder has an option not to add a subexpression as a186///  block-level expression.187class AddStmtChoice {188public:189  enum Kind { NotAlwaysAdd = 0, AlwaysAdd = 1 };190 191  AddStmtChoice(Kind a_kind = NotAlwaysAdd) : kind(a_kind) {}192 193  bool alwaysAdd(CFGBuilder &builder,194                 const Stmt *stmt) const;195 196  /// Return a copy of this object, except with the 'always-add' bit197  ///  set as specified.198  AddStmtChoice withAlwaysAdd(bool alwaysAdd) const {199    return AddStmtChoice(alwaysAdd ? AlwaysAdd : NotAlwaysAdd);200  }201 202private:203  Kind kind;204};205 206/// LocalScope - Node in tree of local scopes created for C++ implicit207/// destructor calls generation. It contains list of automatic variables208/// declared in the scope and link to position in previous scope this scope209/// began in.210///211/// The process of creating local scopes is as follows:212/// - Init CFGBuilder::ScopePos with invalid position (equivalent for null),213/// - Before processing statements in scope (e.g. CompoundStmt) create214///   LocalScope object using CFGBuilder::ScopePos as link to previous scope215///   and set CFGBuilder::ScopePos to the end of new scope,216/// - On every occurrence of VarDecl increase CFGBuilder::ScopePos if it points217///   at this VarDecl,218/// - For every normal (without jump) end of scope add to CFGBlock destructors219///   for objects in the current scope,220/// - For every jump add to CFGBlock destructors for objects221///   between CFGBuilder::ScopePos and local scope position saved for jump222///   target. Thanks to C++ restrictions on goto jumps we can be sure that223///   jump target position will be on the path to root from CFGBuilder::ScopePos224///   (adding any variable that doesn't need constructor to be called to225///   LocalScope can break this assumption),226///227class LocalScope {228public:229  using AutomaticVarsTy = BumpVector<VarDecl *>;230 231  /// const_iterator - Iterates local scope backwards and jumps to previous232  /// scope on reaching the beginning of currently iterated scope.233  class const_iterator {234    const LocalScope* Scope = nullptr;235 236    /// VarIter is guaranteed to be greater then 0 for every valid iterator.237    /// Invalid iterator (with null Scope) has VarIter equal to 0.238    unsigned VarIter = 0;239 240  public:241    /// Create invalid iterator. Dereferencing invalid iterator is not allowed.242    /// Incrementing invalid iterator is allowed and will result in invalid243    /// iterator.244    const_iterator() = default;245 246    /// Create valid iterator. In case when S.Prev is an invalid iterator and247    /// I is equal to 0, this will create invalid iterator.248    const_iterator(const LocalScope& S, unsigned I)249        : Scope(&S), VarIter(I) {250      // Iterator to "end" of scope is not allowed. Handle it by going up251      // in scopes tree possibly up to invalid iterator in the root.252      if (VarIter == 0 && Scope)253        *this = Scope->Prev;254    }255 256    VarDecl *const* operator->() const {257      assert(Scope && "Dereferencing invalid iterator is not allowed");258      assert(VarIter != 0 && "Iterator has invalid value of VarIter member");259      return &Scope->Vars[VarIter - 1];260    }261 262    const VarDecl *getFirstVarInScope() const {263      assert(Scope && "Dereferencing invalid iterator is not allowed");264      assert(VarIter != 0 && "Iterator has invalid value of VarIter member");265      return Scope->Vars[0];266    }267 268    VarDecl *operator*() const {269      return *this->operator->();270    }271 272    const_iterator &operator++() {273      if (!Scope)274        return *this;275 276      assert(VarIter != 0 && "Iterator has invalid value of VarIter member");277      --VarIter;278      if (VarIter == 0)279        *this = Scope->Prev;280      return *this;281    }282    const_iterator operator++(int) {283      const_iterator P = *this;284      ++*this;285      return P;286    }287 288    bool operator==(const const_iterator &rhs) const {289      return Scope == rhs.Scope && VarIter == rhs.VarIter;290    }291    bool operator!=(const const_iterator &rhs) const {292      return !(*this == rhs);293    }294 295    explicit operator bool() const {296      return *this != const_iterator();297    }298 299    int distance(const_iterator L);300    const_iterator shared_parent(const_iterator L);301    bool pointsToFirstDeclaredVar() { return VarIter == 1; }302    bool inSameLocalScope(const_iterator rhs) { return Scope == rhs.Scope; }303  };304 305private:306  BumpVectorContext ctx;307 308  /// Automatic variables in order of declaration.309  AutomaticVarsTy Vars;310 311  /// Iterator to variable in previous scope that was declared just before312  /// begin of this scope.313  const_iterator Prev;314 315public:316  /// Constructs empty scope linked to previous scope in specified place.317  LocalScope(BumpVectorContext ctx, const_iterator P)318      : ctx(std::move(ctx)), Vars(this->ctx, 4), Prev(P) {}319 320  /// Begin of scope in direction of CFG building (backwards).321  const_iterator begin() const { return const_iterator(*this, Vars.size()); }322 323  void addVar(VarDecl *VD) {324    Vars.push_back(VD, ctx);325  }326};327 328} // namespace329 330/// distance - Calculates distance from this to L. L must be reachable from this331/// (with use of ++ operator). Cost of calculating the distance is linear w.r.t.332/// number of scopes between this and L.333int LocalScope::const_iterator::distance(LocalScope::const_iterator L) {334  int D = 0;335  const_iterator F = *this;336  while (F.Scope != L.Scope) {337    assert(F != const_iterator() &&338           "L iterator is not reachable from F iterator.");339    D += F.VarIter;340    F = F.Scope->Prev;341  }342  D += F.VarIter - L.VarIter;343  return D;344}345 346/// Calculates the closest parent of this iterator347/// that is in a scope reachable through the parents of L.348/// I.e. when using 'goto' from this to L, the lifetime of all variables349/// between this and shared_parent(L) end.350LocalScope::const_iterator351LocalScope::const_iterator::shared_parent(LocalScope::const_iterator L) {352  // one of iterators is not valid (we are not in scope), so common353  // parent is const_iterator() (i.e. sentinel).354  if ((*this == const_iterator()) || (L == const_iterator())) {355    return const_iterator();356  }357 358  const_iterator F = *this;359  if (F.inSameLocalScope(L)) {360    // Iterators are in the same scope, get common subset of variables.361    F.VarIter = std::min(F.VarIter, L.VarIter);362    return F;363  }364 365  llvm::SmallDenseMap<const LocalScope *, unsigned, 4> ScopesOfL;366  while (true) {367    ScopesOfL.try_emplace(L.Scope, L.VarIter);368    if (L == const_iterator())369      break;370    L = L.Scope->Prev;371  }372 373  while (true) {374    if (auto LIt = ScopesOfL.find(F.Scope); LIt != ScopesOfL.end()) {375      // Get common subset of variables in given scope376      F.VarIter = std::min(F.VarIter, LIt->getSecond());377      return F;378    }379    assert(F != const_iterator() &&380           "L iterator is not reachable from F iterator.");381    F = F.Scope->Prev;382  }383}384 385namespace {386 387/// Structure for specifying position in CFG during its build process. It388/// consists of CFGBlock that specifies position in CFG and389/// LocalScope::const_iterator that specifies position in LocalScope graph.390struct BlockScopePosPair {391  CFGBlock *block = nullptr;392  LocalScope::const_iterator scopePosition;393 394  BlockScopePosPair() = default;395  BlockScopePosPair(CFGBlock *b, LocalScope::const_iterator scopePos)396      : block(b), scopePosition(scopePos) {}397};398 399/// TryResult - a class representing a variant over the values400///  'true', 'false', or 'unknown'.  This is returned by tryEvaluateBool,401///  and is used by the CFGBuilder to decide if a branch condition402///  can be decided up front during CFG construction.403class TryResult {404  int X = -1;405 406public:407  TryResult() = default;408  TryResult(bool b) : X(b ? 1 : 0) {}409 410  bool isTrue() const { return X == 1; }411  bool isFalse() const { return X == 0; }412  bool isKnown() const { return X >= 0; }413 414  void negate() {415    assert(isKnown());416    X ^= 0x1;417  }418};419 420} // namespace421 422static TryResult bothKnownTrue(TryResult R1, TryResult R2) {423  if (!R1.isKnown() || !R2.isKnown())424    return TryResult();425  return TryResult(R1.isTrue() && R2.isTrue());426}427 428namespace {429 430class reverse_children {431  llvm::SmallVector<Stmt *, 12> childrenBuf;432  ArrayRef<Stmt *> children;433 434public:435  reverse_children(Stmt *S, ASTContext &Ctx);436 437  using iterator = ArrayRef<Stmt *>::reverse_iterator;438 439  iterator begin() const { return children.rbegin(); }440  iterator end() const { return children.rend(); }441};442 443} // namespace444 445reverse_children::reverse_children(Stmt *S, ASTContext &Ctx) {446  if (CallExpr *CE = dyn_cast<CallExpr>(S)) {447    children = CE->getRawSubExprs();448    return;449  }450 451  switch (S->getStmtClass()) {452  // Note: Fill in this switch with more cases we want to optimize.453  case Stmt::InitListExprClass: {454    InitListExpr *IE = cast<InitListExpr>(S);455    children = llvm::ArrayRef(reinterpret_cast<Stmt **>(IE->getInits()),456                              IE->getNumInits());457    return;458  }459 460  case Stmt::AttributedStmtClass: {461    // For an attributed stmt, the "children()" returns only the NullStmt462    // (;) but semantically the "children" are supposed to be the463    // expressions _within_ i.e. the two square brackets i.e. [[ HERE ]]464    // so we add the subexpressions first, _then_ add the "children"465    auto *AS = cast<AttributedStmt>(S);466    for (const auto *Attr : AS->getAttrs()) {467      if (const auto *AssumeAttr = dyn_cast<CXXAssumeAttr>(Attr)) {468        Expr *AssumeExpr = AssumeAttr->getAssumption();469        if (!AssumeExpr->HasSideEffects(Ctx)) {470          childrenBuf.push_back(AssumeExpr);471        }472      }473    }474 475    // Visit the actual children AST nodes.476    // For CXXAssumeAttrs, this is always a NullStmt.477    llvm::append_range(childrenBuf, AS->children());478    children = childrenBuf;479    return;480  }481  default:482    break;483  }484 485  // Default case for all other statements.486  llvm::append_range(childrenBuf, S->children());487 488  // This needs to be done *after* childrenBuf has been populated.489  children = childrenBuf;490}491 492namespace {493 494/// CFGBuilder - This class implements CFG construction from an AST.495///   The builder is stateful: an instance of the builder should be used to only496///   construct a single CFG.497///498///   Example usage:499///500///     CFGBuilder builder;501///     std::unique_ptr<CFG> cfg = builder.buildCFG(decl, stmt1);502///503///  CFG construction is done via a recursive walk of an AST.  We actually parse504///  the AST in reverse order so that the successor of a basic block is505///  constructed prior to its predecessor.  This allows us to nicely capture506///  implicit fall-throughs without extra basic blocks.507class CFGBuilder {508  using JumpTarget = BlockScopePosPair;509  using JumpSource = BlockScopePosPair;510 511  ASTContext *Context;512  std::unique_ptr<CFG> cfg;513 514  // Current block.515  CFGBlock *Block = nullptr;516 517  // Block after the current block.518  CFGBlock *Succ = nullptr;519 520  JumpTarget ContinueJumpTarget;521  JumpTarget BreakJumpTarget;522  JumpTarget SEHLeaveJumpTarget;523  CFGBlock *SwitchTerminatedBlock = nullptr;524  CFGBlock *DefaultCaseBlock = nullptr;525 526  // This can point to either a C++ try, an Objective-C @try, or an SEH __try.527  // try and @try can be mixed and generally work the same.528  // The frontend forbids mixing SEH __try with either try or @try.529  // So having one for all three is enough.530  CFGBlock *TryTerminatedBlock = nullptr;531 532  // Current position in local scope.533  LocalScope::const_iterator ScopePos;534 535  // LabelMap records the mapping from Label expressions to their jump targets.536  using LabelMapTy = llvm::DenseMap<LabelDecl *, JumpTarget>;537  LabelMapTy LabelMap;538 539  // A list of blocks that end with a "goto" that must be backpatched to their540  // resolved targets upon completion of CFG construction.541  using BackpatchBlocksTy = std::vector<JumpSource>;542  BackpatchBlocksTy BackpatchBlocks;543 544  // A list of labels whose address has been taken (for indirect gotos).545  using LabelSetTy = llvm::SmallSetVector<LabelDecl *, 8>;546  LabelSetTy AddressTakenLabels;547 548  // Information about the currently visited C++ object construction site.549  // This is set in the construction trigger and read when the constructor550  // or a function that returns an object by value is being visited.551  llvm::DenseMap<Expr *, const ConstructionContextLayer *>552      ConstructionContextMap;553 554  bool badCFG = false;555  const CFG::BuildOptions &BuildOpts;556 557  // State to track for building switch statements.558  bool switchExclusivelyCovered = false;559  Expr::EvalResult *switchCond = nullptr;560 561  CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry = nullptr;562  const Stmt *lastLookup = nullptr;563 564  // Caches boolean evaluations of expressions to avoid multiple re-evaluations565  // during construction of branches for chained logical operators.566  using CachedBoolEvalsTy = llvm::DenseMap<Expr *, TryResult>;567  CachedBoolEvalsTy CachedBoolEvals;568 569public:570  explicit CFGBuilder(ASTContext *astContext,571                      const CFG::BuildOptions &buildOpts)572      : Context(astContext), cfg(new CFG()), BuildOpts(buildOpts) {}573 574  // buildCFG - Used by external clients to construct the CFG.575  std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *Statement);576 577  bool alwaysAdd(const Stmt *stmt);578 579private:580  // Visitors to walk an AST and construct the CFG.581  CFGBlock *VisitInitListExpr(InitListExpr *ILE, AddStmtChoice asc);582  CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc);583  CFGBlock *VisitAttributedStmt(AttributedStmt *A, AddStmtChoice asc);584  CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc);585  CFGBlock *VisitBreakStmt(BreakStmt *B);586  CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc);587  CFGBlock *VisitCaseStmt(CaseStmt *C);588  CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc);589  CFGBlock *VisitCompoundStmt(CompoundStmt *C, bool ExternallyDestructed);590  CFGBlock *VisitConditionalOperator(AbstractConditionalOperator *C,591                                     AddStmtChoice asc);592  CFGBlock *VisitContinueStmt(ContinueStmt *C);593  CFGBlock *VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,594                                      AddStmtChoice asc);595  CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S);596  CFGBlock *VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc);597  CFGBlock *VisitCXXNewExpr(CXXNewExpr *DE, AddStmtChoice asc);598  CFGBlock *VisitCXXDeleteExpr(CXXDeleteExpr *DE, AddStmtChoice asc);599  CFGBlock *VisitCXXForRangeStmt(CXXForRangeStmt *S);600  CFGBlock *VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,601                                       AddStmtChoice asc);602  CFGBlock *VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C,603                                        AddStmtChoice asc);604  CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T);605  CFGBlock *VisitCXXTryStmt(CXXTryStmt *S);606  CFGBlock *VisitCXXTypeidExpr(CXXTypeidExpr *S, AddStmtChoice asc);607  CFGBlock *VisitDeclStmt(DeclStmt *DS);608  CFGBlock *VisitDeclSubExpr(DeclStmt *DS);609  CFGBlock *VisitDefaultStmt(DefaultStmt *D);610  CFGBlock *VisitDoStmt(DoStmt *D);611  CFGBlock *VisitExprWithCleanups(ExprWithCleanups *E,612                                  AddStmtChoice asc, bool ExternallyDestructed);613  CFGBlock *VisitForStmt(ForStmt *F);614  CFGBlock *VisitGotoStmt(GotoStmt *G);615  CFGBlock *VisitGCCAsmStmt(GCCAsmStmt *G, AddStmtChoice asc);616  CFGBlock *VisitIfStmt(IfStmt *I);617  CFGBlock *VisitImplicitCastExpr(ImplicitCastExpr *E, AddStmtChoice asc);618  CFGBlock *VisitConstantExpr(ConstantExpr *E, AddStmtChoice asc);619  CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I);620  CFGBlock *VisitLabelStmt(LabelStmt *L);621  CFGBlock *VisitBlockExpr(BlockExpr *E, AddStmtChoice asc);622  CFGBlock *VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc);623  CFGBlock *VisitLogicalOperator(BinaryOperator *B);624  std::pair<CFGBlock *, CFGBlock *> VisitLogicalOperator(BinaryOperator *B,625                                                         Stmt *Term,626                                                         CFGBlock *TrueBlock,627                                                         CFGBlock *FalseBlock);628  CFGBlock *VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE,629                                          AddStmtChoice asc);630  CFGBlock *VisitMemberExpr(MemberExpr *M, AddStmtChoice asc);631  CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S);632  CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S);633  CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S);634  CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S);635  CFGBlock *VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S);636  CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S);637  CFGBlock *VisitObjCMessageExpr(ObjCMessageExpr *E, AddStmtChoice asc);638  CFGBlock *VisitPseudoObjectExpr(PseudoObjectExpr *E);639  CFGBlock *VisitReturnStmt(Stmt *S);640  CFGBlock *VisitCoroutineSuspendExpr(CoroutineSuspendExpr *S,641                                      AddStmtChoice asc);642  CFGBlock *VisitSEHExceptStmt(SEHExceptStmt *S);643  CFGBlock *VisitSEHFinallyStmt(SEHFinallyStmt *S);644  CFGBlock *VisitSEHLeaveStmt(SEHLeaveStmt *S);645  CFGBlock *VisitSEHTryStmt(SEHTryStmt *S);646  CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc);647  CFGBlock *VisitSwitchStmt(SwitchStmt *S);648  CFGBlock *VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,649                                          AddStmtChoice asc);650  CFGBlock *VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc);651  CFGBlock *VisitWhileStmt(WhileStmt *W);652  CFGBlock *VisitArrayInitLoopExpr(ArrayInitLoopExpr *A, AddStmtChoice asc);653 654  CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd,655                  bool ExternallyDestructed = false);656  CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc);657  CFGBlock *VisitChildren(Stmt *S);658  CFGBlock *VisitNoRecurse(Expr *E, AddStmtChoice asc);659  CFGBlock *VisitOMPExecutableDirective(OMPExecutableDirective *D,660                                        AddStmtChoice asc);661 662  void maybeAddScopeBeginForVarDecl(CFGBlock *B, const VarDecl *VD,663                                    const Stmt *S) {664    if (ScopePos && (VD == ScopePos.getFirstVarInScope()))665      appendScopeBegin(B, VD, S);666  }667 668  /// When creating the CFG for temporary destructors, we want to mirror the669  /// branch structure of the corresponding constructor calls.670  /// Thus, while visiting a statement for temporary destructors, we keep a671  /// context to keep track of the following information:672  /// - whether a subexpression is executed unconditionally673  /// - if a subexpression is executed conditionally, the first674  ///   CXXBindTemporaryExpr we encounter in that subexpression (which675  ///   corresponds to the last temporary destructor we have to call for this676  ///   subexpression) and the CFG block at that point (which will become the677  ///   successor block when inserting the decision point).678  ///679  /// That way, we can build the branch structure for temporary destructors as680  /// follows:681  /// 1. If a subexpression is executed unconditionally, we add the temporary682  ///    destructor calls to the current block.683  /// 2. If a subexpression is executed conditionally, when we encounter a684  ///    CXXBindTemporaryExpr:685  ///    a) If it is the first temporary destructor call in the subexpression,686  ///       we remember the CXXBindTemporaryExpr and the current block in the687  ///       TempDtorContext; we start a new block, and insert the temporary688  ///       destructor call.689  ///    b) Otherwise, add the temporary destructor call to the current block.690  ///  3. When we finished visiting a conditionally executed subexpression,691  ///     and we found at least one temporary constructor during the visitation692  ///     (2.a has executed), we insert a decision block that uses the693  ///     CXXBindTemporaryExpr as terminator, and branches to the current block694  ///     if the CXXBindTemporaryExpr was marked executed, and otherwise695  ///     branches to the stored successor.696  struct TempDtorContext {697    TempDtorContext() = default;698    TempDtorContext(TryResult KnownExecuted)699        : IsConditional(true), KnownExecuted(KnownExecuted) {}700 701    /// Returns whether we need to start a new branch for a temporary destructor702    /// call. This is the case when the temporary destructor is703    /// conditionally executed, and it is the first one we encounter while704    /// visiting a subexpression - other temporary destructors at the same level705    /// will be added to the same block and are executed under the same706    /// condition.707    bool needsTempDtorBranch() const {708      return IsConditional && !TerminatorExpr;709    }710 711    /// Remember the successor S of a temporary destructor decision branch for712    /// the corresponding CXXBindTemporaryExpr E.713    void setDecisionPoint(CFGBlock *S, CXXBindTemporaryExpr *E) {714      Succ = S;715      TerminatorExpr = E;716    }717 718    const bool IsConditional = false;719    const TryResult KnownExecuted = true;720    CFGBlock *Succ = nullptr;721    CXXBindTemporaryExpr *TerminatorExpr = nullptr;722  };723 724  // Visitors to walk an AST and generate destructors of temporaries in725  // full expression.726  CFGBlock *VisitForTemporaryDtors(Stmt *E, bool ExternallyDestructed,727                                   TempDtorContext &Context);728  CFGBlock *VisitChildrenForTemporaryDtors(Stmt *E,  bool ExternallyDestructed,729                                           TempDtorContext &Context);730  CFGBlock *VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E,731                                                 bool ExternallyDestructed,732                                                 TempDtorContext &Context);733  CFGBlock *VisitCXXBindTemporaryExprForTemporaryDtors(734      CXXBindTemporaryExpr *E, bool ExternallyDestructed, TempDtorContext &Context);735  CFGBlock *VisitConditionalOperatorForTemporaryDtors(736      AbstractConditionalOperator *E, bool ExternallyDestructed,737      TempDtorContext &Context);738  void InsertTempDtorDecisionBlock(const TempDtorContext &Context,739                                   CFGBlock *FalseSucc = nullptr);740 741  // NYS == Not Yet Supported742  CFGBlock *NYS() {743    badCFG = true;744    return Block;745  }746 747  // Remember to apply the construction context based on the current \p Layer748  // when constructing the CFG element for \p CE.749  void consumeConstructionContext(const ConstructionContextLayer *Layer,750                                  Expr *E);751 752  // Scan \p Child statement to find constructors in it, while keeping in mind753  // that its parent statement is providing a partial construction context754  // described by \p Layer. If a constructor is found, it would be assigned755  // the context based on the layer. If an additional construction context layer756  // is found, the function recurses into that.757  void findConstructionContexts(const ConstructionContextLayer *Layer,758                                Stmt *Child);759 760  // Scan all arguments of a call expression for a construction context.761  // These sorts of call expressions don't have a common superclass,762  // hence strict duck-typing.763  template <typename CallLikeExpr,764            typename = std::enable_if_t<765                std::is_base_of_v<CallExpr, CallLikeExpr> ||766                std::is_base_of_v<CXXConstructExpr, CallLikeExpr> ||767                std::is_base_of_v<ObjCMessageExpr, CallLikeExpr>>>768  void findConstructionContextsForArguments(CallLikeExpr *E) {769    for (unsigned i = 0, e = E->getNumArgs(); i != e; ++i) {770      Expr *Arg = E->getArg(i);771      if (Arg->getType()->getAsCXXRecordDecl() && !Arg->isGLValue())772        findConstructionContexts(773            ConstructionContextLayer::create(cfg->getBumpVectorContext(),774                                             ConstructionContextItem(E, i)),775            Arg);776    }777  }778 779  // Unset the construction context after consuming it. This is done immediately780  // after adding the CFGConstructor or CFGCXXRecordTypedCall element, so781  // there's no need to do this manually in every Visit... function.782  void cleanupConstructionContext(Expr *E);783 784  void autoCreateBlock() { if (!Block) Block = createBlock(); }785 786  CFGBlock *createBlock(bool add_successor = true);787  CFGBlock *createNoReturnBlock();788 789  CFGBlock *addStmt(Stmt *S) {790    return Visit(S, AddStmtChoice::AlwaysAdd);791  }792 793  CFGBlock *addInitializer(CXXCtorInitializer *I);794  void addLoopExit(const Stmt *LoopStmt);795  void addAutomaticObjHandling(LocalScope::const_iterator B,796                               LocalScope::const_iterator E, Stmt *S);797  void addAutomaticObjDestruction(LocalScope::const_iterator B,798                                  LocalScope::const_iterator E, Stmt *S);799  void addScopeExitHandling(LocalScope::const_iterator B,800                            LocalScope::const_iterator E, Stmt *S);801  void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD);802  void addScopeChangesHandling(LocalScope::const_iterator SrcPos,803                               LocalScope::const_iterator DstPos,804                               Stmt *S);805  CFGBlock *createScopeChangesHandlingBlock(LocalScope::const_iterator SrcPos,806                                            CFGBlock *SrcBlk,807                                            LocalScope::const_iterator DstPost,808                                            CFGBlock *DstBlk);809 810  // Local scopes creation.811  LocalScope* createOrReuseLocalScope(LocalScope* Scope);812 813  void addLocalScopeForStmt(Stmt *S);814  LocalScope* addLocalScopeForDeclStmt(DeclStmt *DS,815                                       LocalScope* Scope = nullptr);816  LocalScope* addLocalScopeForVarDecl(VarDecl *VD, LocalScope* Scope = nullptr);817 818  void addLocalScopeAndDtors(Stmt *S);819 820  const ConstructionContext *retrieveAndCleanupConstructionContext(Expr *E) {821    if (!BuildOpts.AddRichCXXConstructors)822      return nullptr;823 824    const ConstructionContextLayer *Layer = ConstructionContextMap.lookup(E);825    if (!Layer)826      return nullptr;827 828    cleanupConstructionContext(E);829    return ConstructionContext::createFromLayers(cfg->getBumpVectorContext(),830                                                 Layer);831  }832 833  // Interface to CFGBlock - adding CFGElements.834 835  void appendStmt(CFGBlock *B, const Stmt *S) {836    if (alwaysAdd(S) && cachedEntry)837      cachedEntry->second = B;838 839    // All block-level expressions should have already been IgnoreParens()ed.840    assert(!isa<Expr>(S) || cast<Expr>(S)->IgnoreParens() == S);841    B->appendStmt(const_cast<Stmt*>(S), cfg->getBumpVectorContext());842  }843 844  void appendConstructor(CXXConstructExpr *CE) {845    CXXConstructorDecl *C = CE->getConstructor();846    if (C && C->isNoReturn())847      Block = createNoReturnBlock();848    else849      autoCreateBlock();850 851    if (const ConstructionContext *CC =852            retrieveAndCleanupConstructionContext(CE)) {853      Block->appendConstructor(CE, CC, cfg->getBumpVectorContext());854      return;855    }856 857    // No valid construction context found. Fall back to statement.858    Block->appendStmt(CE, cfg->getBumpVectorContext());859  }860 861  void appendCall(CFGBlock *B, CallExpr *CE) {862    if (alwaysAdd(CE) && cachedEntry)863      cachedEntry->second = B;864 865    if (const ConstructionContext *CC =866            retrieveAndCleanupConstructionContext(CE)) {867      B->appendCXXRecordTypedCall(CE, CC, cfg->getBumpVectorContext());868      return;869    }870 871    // No valid construction context found. Fall back to statement.872    B->appendStmt(CE, cfg->getBumpVectorContext());873  }874 875  void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) {876    B->appendInitializer(I, cfg->getBumpVectorContext());877  }878 879  void appendNewAllocator(CFGBlock *B, CXXNewExpr *NE) {880    B->appendNewAllocator(NE, cfg->getBumpVectorContext());881  }882 883  void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) {884    B->appendBaseDtor(BS, cfg->getBumpVectorContext());885  }886 887  void appendMemberDtor(CFGBlock *B, FieldDecl *FD) {888    B->appendMemberDtor(FD, cfg->getBumpVectorContext());889  }890 891  void appendObjCMessage(CFGBlock *B, ObjCMessageExpr *ME) {892    if (alwaysAdd(ME) && cachedEntry)893      cachedEntry->second = B;894 895    if (const ConstructionContext *CC =896            retrieveAndCleanupConstructionContext(ME)) {897      B->appendCXXRecordTypedCall(ME, CC, cfg->getBumpVectorContext());898      return;899    }900 901    B->appendStmt(ME, cfg->getBumpVectorContext());902  }903 904  void appendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) {905    B->appendTemporaryDtor(E, cfg->getBumpVectorContext());906  }907 908  void appendAutomaticObjDtor(CFGBlock *B, VarDecl *VD, Stmt *S) {909    B->appendAutomaticObjDtor(VD, S, cfg->getBumpVectorContext());910  }911 912  void appendCleanupFunction(CFGBlock *B, VarDecl *VD) {913    B->appendCleanupFunction(VD, cfg->getBumpVectorContext());914  }915 916  void appendLifetimeEnds(CFGBlock *B, VarDecl *VD, Stmt *S) {917    B->appendLifetimeEnds(VD, S, cfg->getBumpVectorContext());918  }919 920  void appendLoopExit(CFGBlock *B, const Stmt *LoopStmt) {921    B->appendLoopExit(LoopStmt, cfg->getBumpVectorContext());922  }923 924  void appendDeleteDtor(CFGBlock *B, CXXRecordDecl *RD, CXXDeleteExpr *DE) {925    B->appendDeleteDtor(RD, DE, cfg->getBumpVectorContext());926  }927 928  void addSuccessor(CFGBlock *B, CFGBlock *S, bool IsReachable = true) {929    B->addSuccessor(CFGBlock::AdjacentBlock(S, IsReachable),930                    cfg->getBumpVectorContext());931  }932 933  /// Add a reachable successor to a block, with the alternate variant that is934  /// unreachable.935  void addSuccessor(CFGBlock *B, CFGBlock *ReachableBlock, CFGBlock *AltBlock) {936    B->addSuccessor(CFGBlock::AdjacentBlock(ReachableBlock, AltBlock),937                    cfg->getBumpVectorContext());938  }939 940  void appendScopeBegin(CFGBlock *B, const VarDecl *VD, const Stmt *S) {941    if (BuildOpts.AddScopes)942      B->appendScopeBegin(VD, S, cfg->getBumpVectorContext());943  }944 945  void appendScopeEnd(CFGBlock *B, const VarDecl *VD, const Stmt *S) {946    if (BuildOpts.AddScopes)947      B->appendScopeEnd(VD, S, cfg->getBumpVectorContext());948  }949 950  /// Find a relational comparison with an expression evaluating to a951  /// boolean and a constant other than 0 and 1.952  /// e.g. if ((x < y) == 10)953  TryResult checkIncorrectRelationalOperator(const BinaryOperator *B) {954    const Expr *LHSExpr = B->getLHS()->IgnoreParens();955    const Expr *RHSExpr = B->getRHS()->IgnoreParens();956 957    const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(LHSExpr);958    const Expr *BoolExpr = RHSExpr;959    bool IntFirst = true;960    if (!IntLiteral) {961      IntLiteral = dyn_cast<IntegerLiteral>(RHSExpr);962      BoolExpr = LHSExpr;963      IntFirst = false;964    }965 966    if (!IntLiteral || !BoolExpr->isKnownToHaveBooleanValue())967      return TryResult();968 969    llvm::APInt IntValue = IntLiteral->getValue();970    if ((IntValue == 1) || (IntValue == 0))971      return TryResult();972 973    bool IntLarger = IntLiteral->getType()->isUnsignedIntegerType() ||974                     !IntValue.isNegative();975 976    BinaryOperatorKind Bok = B->getOpcode();977    if (Bok == BO_GT || Bok == BO_GE) {978      // Always true for 10 > bool and bool > -1979      // Always false for -1 > bool and bool > 10980      return TryResult(IntFirst == IntLarger);981    } else {982      // Always true for -1 < bool and bool < 10983      // Always false for 10 < bool and bool < -1984      return TryResult(IntFirst != IntLarger);985    }986  }987 988  /// Find an incorrect equality comparison. Either with an expression989  /// evaluating to a boolean and a constant other than 0 and 1.990  /// e.g. if (!x == 10) or a bitwise and/or operation that always evaluates to991  /// true/false e.q. (x & 8) == 4.992  TryResult checkIncorrectEqualityOperator(const BinaryOperator *B) {993    const Expr *LHSExpr = B->getLHS()->IgnoreParens();994    const Expr *RHSExpr = B->getRHS()->IgnoreParens();995 996    std::optional<llvm::APInt> IntLiteral1 =997        getIntegerLiteralSubexpressionValue(LHSExpr);998    const Expr *BoolExpr = RHSExpr;999 1000    if (!IntLiteral1) {1001      IntLiteral1 = getIntegerLiteralSubexpressionValue(RHSExpr);1002      BoolExpr = LHSExpr;1003    }1004 1005    if (!IntLiteral1)1006      return TryResult();1007 1008    const BinaryOperator *BitOp = dyn_cast<BinaryOperator>(BoolExpr);1009    if (BitOp && (BitOp->getOpcode() == BO_And ||1010                  BitOp->getOpcode() == BO_Or)) {1011      const Expr *LHSExpr2 = BitOp->getLHS()->IgnoreParens();1012      const Expr *RHSExpr2 = BitOp->getRHS()->IgnoreParens();1013 1014      std::optional<llvm::APInt> IntLiteral2 =1015          getIntegerLiteralSubexpressionValue(LHSExpr2);1016 1017      if (!IntLiteral2)1018        IntLiteral2 = getIntegerLiteralSubexpressionValue(RHSExpr2);1019 1020      if (!IntLiteral2)1021        return TryResult();1022 1023      if ((BitOp->getOpcode() == BO_And &&1024           (*IntLiteral2 & *IntLiteral1) != *IntLiteral1) ||1025          (BitOp->getOpcode() == BO_Or &&1026           (*IntLiteral2 | *IntLiteral1) != *IntLiteral1)) {1027        if (BuildOpts.Observer)1028          BuildOpts.Observer->compareBitwiseEquality(B,1029                                                     B->getOpcode() != BO_EQ);1030        return TryResult(B->getOpcode() != BO_EQ);1031      }1032    } else if (BoolExpr->isKnownToHaveBooleanValue()) {1033      if ((*IntLiteral1 == 1) || (*IntLiteral1 == 0)) {1034        return TryResult();1035      }1036      return TryResult(B->getOpcode() != BO_EQ);1037    }1038 1039    return TryResult();1040  }1041 1042  // Helper function to get an APInt from an expression. Supports expressions1043  // which are an IntegerLiteral or a UnaryOperator and returns the value with1044  // all operations performed on it.1045  // FIXME: it would be good to unify this function with1046  // IsIntegerLiteralConstantExpr at some point given the similarity between the1047  // functions.1048  std::optional<llvm::APInt>1049  getIntegerLiteralSubexpressionValue(const Expr *E) {1050 1051    // If unary.1052    if (const auto *UnOp = dyn_cast<UnaryOperator>(E->IgnoreParens())) {1053      // Get the sub expression of the unary expression and get the Integer1054      // Literal.1055      const Expr *SubExpr = UnOp->getSubExpr()->IgnoreParens();1056 1057      if (const auto *IntLiteral = dyn_cast<IntegerLiteral>(SubExpr)) {1058 1059        llvm::APInt Value = IntLiteral->getValue();1060 1061        // Perform the operation manually.1062        switch (UnOp->getOpcode()) {1063        case UO_Plus:1064          return Value;1065        case UO_Minus:1066          return -Value;1067        case UO_Not:1068          return ~Value;1069        case UO_LNot:1070          return llvm::APInt(Context->getTypeSize(Context->IntTy), !Value);1071        default:1072          assert(false && "Unexpected unary operator!");1073          return std::nullopt;1074        }1075      }1076    } else if (const auto *IntLiteral =1077                   dyn_cast<IntegerLiteral>(E->IgnoreParens()))1078      return IntLiteral->getValue();1079 1080    return std::nullopt;1081  }1082 1083  template <typename APFloatOrInt>1084  TryResult analyzeLogicOperatorCondition(BinaryOperatorKind Relation,1085                                          const APFloatOrInt &Value1,1086                                          const APFloatOrInt &Value2) {1087    switch (Relation) {1088      default:1089        return TryResult();1090      case BO_EQ:1091        return TryResult(Value1 == Value2);1092      case BO_NE:1093        return TryResult(Value1 != Value2);1094      case BO_LT:1095        return TryResult(Value1 <  Value2);1096      case BO_LE:1097        return TryResult(Value1 <= Value2);1098      case BO_GT:1099        return TryResult(Value1 >  Value2);1100      case BO_GE:1101        return TryResult(Value1 >= Value2);1102    }1103  }1104 1105  /// There are two checks handled by this function:1106  /// 1. Find a law-of-excluded-middle or law-of-noncontradiction expression1107  /// e.g. if (x || !x), if (x && !x)1108  /// 2. Find a pair of comparison expressions with or without parentheses1109  /// with a shared variable and constants and a logical operator between them1110  /// that always evaluates to either true or false.1111  /// e.g. if (x != 3 || x != 4)1112  TryResult checkIncorrectLogicOperator(const BinaryOperator *B) {1113    assert(B->isLogicalOp());1114    const Expr *LHSExpr = B->getLHS()->IgnoreParens();1115    const Expr *RHSExpr = B->getRHS()->IgnoreParens();1116 1117    auto CheckLogicalOpWithNegatedVariable = [this, B](const Expr *E1,1118                                                       const Expr *E2) {1119      if (const auto *Negate = dyn_cast<UnaryOperator>(E1)) {1120        if (Negate->getOpcode() == UO_LNot &&1121            Expr::isSameComparisonOperand(Negate->getSubExpr(), E2)) {1122          bool AlwaysTrue = B->getOpcode() == BO_LOr;1123          if (BuildOpts.Observer)1124            BuildOpts.Observer->logicAlwaysTrue(B, AlwaysTrue);1125          return TryResult(AlwaysTrue);1126        }1127      }1128      return TryResult();1129    };1130 1131    TryResult Result = CheckLogicalOpWithNegatedVariable(LHSExpr, RHSExpr);1132    if (Result.isKnown())1133        return Result;1134    Result = CheckLogicalOpWithNegatedVariable(RHSExpr, LHSExpr);1135    if (Result.isKnown())1136        return Result;1137 1138    const auto *LHS = dyn_cast<BinaryOperator>(LHSExpr);1139    const auto *RHS = dyn_cast<BinaryOperator>(RHSExpr);1140    if (!LHS || !RHS)1141      return {};1142 1143    if (!LHS->isComparisonOp() || !RHS->isComparisonOp())1144      return {};1145 1146    const Expr *DeclExpr1;1147    const Expr *NumExpr1;1148    BinaryOperatorKind BO1;1149    std::tie(DeclExpr1, BO1, NumExpr1) = tryNormalizeBinaryOperator(LHS);1150 1151    if (!DeclExpr1 || !NumExpr1)1152      return {};1153 1154    const Expr *DeclExpr2;1155    const Expr *NumExpr2;1156    BinaryOperatorKind BO2;1157    std::tie(DeclExpr2, BO2, NumExpr2) = tryNormalizeBinaryOperator(RHS);1158 1159    if (!DeclExpr2 || !NumExpr2)1160      return {};1161 1162    // Check that it is the same variable on both sides.1163    if (!Expr::isSameComparisonOperand(DeclExpr1, DeclExpr2))1164      return {};1165 1166    // Make sure the user's intent is clear (e.g. they're comparing against two1167    // int literals, or two things from the same enum)1168    if (!areExprTypesCompatible(NumExpr1, NumExpr2))1169      return {};1170 1171    // Check that the two expressions are of the same type.1172    Expr::EvalResult L1Result, L2Result;1173    if (!NumExpr1->EvaluateAsRValue(L1Result, *Context) ||1174        !NumExpr2->EvaluateAsRValue(L2Result, *Context))1175      return {};1176 1177    // Check whether expression is always true/false by evaluating the1178    // following1179    // * variable x is less than the smallest literal.1180    // * variable x is equal to the smallest literal.1181    // * Variable x is between smallest and largest literal.1182    // * Variable x is equal to the largest literal.1183    // * Variable x is greater than largest literal.1184    // This isn't technically correct, as it doesn't take into account the1185    // possibility that the variable could be NaN. However, this is a very rare1186    // case.1187    auto AnalyzeConditions = [&](const auto &Values,1188                                 const BinaryOperatorKind *BO1,1189                                 const BinaryOperatorKind *BO2) -> TryResult {1190      bool AlwaysTrue = true, AlwaysFalse = true;1191      // Track value of both subexpressions.  If either side is always1192      // true/false, another warning should have already been emitted.1193      bool LHSAlwaysTrue = true, LHSAlwaysFalse = true;1194      bool RHSAlwaysTrue = true, RHSAlwaysFalse = true;1195 1196      for (const auto &Value : Values) {1197        TryResult Res1 =1198            analyzeLogicOperatorCondition(*BO1, Value, Values[1] /* L1 */);1199        TryResult Res2 =1200            analyzeLogicOperatorCondition(*BO2, Value, Values[3] /* L2 */);1201 1202        if (!Res1.isKnown() || !Res2.isKnown())1203          return {};1204 1205        const bool IsAnd = B->getOpcode() == BO_LAnd;1206        const bool Combine = IsAnd ? (Res1.isTrue() && Res2.isTrue())1207                                   : (Res1.isTrue() || Res2.isTrue());1208 1209        AlwaysTrue &= Combine;1210        AlwaysFalse &= !Combine;1211 1212        LHSAlwaysTrue &= Res1.isTrue();1213        LHSAlwaysFalse &= Res1.isFalse();1214        RHSAlwaysTrue &= Res2.isTrue();1215        RHSAlwaysFalse &= Res2.isFalse();1216      }1217 1218      if (AlwaysTrue || AlwaysFalse) {1219        if (!LHSAlwaysTrue && !LHSAlwaysFalse && !RHSAlwaysTrue &&1220            !RHSAlwaysFalse && BuildOpts.Observer) {1221          BuildOpts.Observer->compareAlwaysTrue(B, AlwaysTrue);1222        }1223        return TryResult(AlwaysTrue);1224      }1225      return {};1226    };1227 1228    // Handle integer comparison.1229    if (L1Result.Val.getKind() == APValue::Int &&1230        L2Result.Val.getKind() == APValue::Int) {1231      llvm::APSInt L1 = L1Result.Val.getInt();1232      llvm::APSInt L2 = L2Result.Val.getInt();1233 1234      // Can't compare signed with unsigned or with different bit width.1235      if (L1.isSigned() != L2.isSigned() ||1236          L1.getBitWidth() != L2.getBitWidth())1237        return {};1238 1239      // Values that will be used to determine if result of logical1240      // operator is always true/false1241      const llvm::APSInt Values[] = {1242          // Value less than both Value1 and Value21243          llvm::APSInt::getMinValue(L1.getBitWidth(), L1.isUnsigned()),1244          // L11245          L1,1246          // Value between Value1 and Value21247          ((L1 < L2) ? L1 : L2) +1248              llvm::APSInt(llvm::APInt(L1.getBitWidth(), 1), L1.isUnsigned()),1249          // L21250          L2,1251          // Value greater than both Value1 and Value21252          llvm::APSInt::getMaxValue(L1.getBitWidth(), L1.isUnsigned()),1253      };1254 1255      return AnalyzeConditions(Values, &BO1, &BO2);1256    }1257 1258    // Handle float comparison.1259    if (L1Result.Val.getKind() == APValue::Float &&1260        L2Result.Val.getKind() == APValue::Float) {1261      llvm::APFloat L1 = L1Result.Val.getFloat();1262      llvm::APFloat L2 = L2Result.Val.getFloat();1263      // Note that L1 and L2 do not necessarily have the same type.  For example1264      // `x != 0 || x != 1.0`, if `x` is a float16, the two literals `0` and1265      // `1.0` are float16 and double respectively.  In this case, we should do1266      // a conversion before comparing L1 and L2.  Their types must be1267      // compatible since they are comparing with the same DRE.1268      int Order = Context->getFloatingTypeSemanticOrder(NumExpr1->getType(),1269                                                        NumExpr2->getType());1270      bool Ignored = false;1271 1272      if (Order > 0) {1273        // type rank L1 > L2:1274        if (llvm::APFloat::opOK !=1275            L2.convert(L1.getSemantics(), llvm::APFloat::rmNearestTiesToEven,1276                       &Ignored))1277          return {};1278      } else if (Order < 0)1279        // type rank L1 < L2:1280        if (llvm::APFloat::opOK !=1281            L1.convert(L2.getSemantics(), llvm::APFloat::rmNearestTiesToEven,1282                       &Ignored))1283          return {};1284 1285      llvm::APFloat MidValue = L1;1286      MidValue.add(L2, llvm::APFloat::rmNearestTiesToEven);1287      MidValue.divide(llvm::APFloat(MidValue.getSemantics(), "2.0"),1288                      llvm::APFloat::rmNearestTiesToEven);1289 1290      const llvm::APFloat Values[] = {1291          llvm::APFloat::getSmallest(L1.getSemantics(), true), L1, MidValue, L2,1292          llvm::APFloat::getLargest(L2.getSemantics(), false),1293      };1294 1295      return AnalyzeConditions(Values, &BO1, &BO2);1296    }1297 1298    return {};1299  }1300 1301  /// A bitwise-or with a non-zero constant always evaluates to true.1302  TryResult checkIncorrectBitwiseOrOperator(const BinaryOperator *B) {1303    const Expr *LHSConstant =1304        tryTransformToLiteralConstant(B->getLHS()->IgnoreParenImpCasts());1305    const Expr *RHSConstant =1306        tryTransformToLiteralConstant(B->getRHS()->IgnoreParenImpCasts());1307 1308    if ((LHSConstant && RHSConstant) || (!LHSConstant && !RHSConstant))1309      return {};1310 1311    const Expr *Constant = LHSConstant ? LHSConstant : RHSConstant;1312 1313    Expr::EvalResult Result;1314    if (!Constant->EvaluateAsInt(Result, *Context))1315      return {};1316 1317    if (Result.Val.getInt() == 0)1318      return {};1319 1320    if (BuildOpts.Observer)1321      BuildOpts.Observer->compareBitwiseOr(B);1322 1323    return TryResult(true);1324  }1325 1326  /// Try and evaluate an expression to an integer constant.1327  bool tryEvaluate(Expr *S, Expr::EvalResult &outResult) {1328    if (!BuildOpts.PruneTriviallyFalseEdges)1329      return false;1330    return !S->isTypeDependent() &&1331           !S->isValueDependent() &&1332           S->EvaluateAsRValue(outResult, *Context);1333  }1334 1335  /// tryEvaluateBool - Try and evaluate the Stmt and return 0 or 11336  /// if we can evaluate to a known value, otherwise return -1.1337  TryResult tryEvaluateBool(Expr *S) {1338    if (!BuildOpts.PruneTriviallyFalseEdges ||1339        S->isTypeDependent() || S->isValueDependent())1340      return {};1341 1342    if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(S)) {1343      if (Bop->isLogicalOp() || Bop->isEqualityOp()) {1344        // Check the cache first.1345        CachedBoolEvalsTy::iterator I = CachedBoolEvals.find(S);1346        if (I != CachedBoolEvals.end())1347          return I->second; // already in map;1348 1349        // Retrieve result at first, or the map might be updated.1350        TryResult Result = evaluateAsBooleanConditionNoCache(S);1351        CachedBoolEvals[S] = Result; // update or insert1352        return Result;1353      }1354      else {1355        switch (Bop->getOpcode()) {1356          default: break;1357          // For 'x & 0' and 'x * 0', we can determine that1358          // the value is always false.1359          case BO_Mul:1360          case BO_And: {1361            // If either operand is zero, we know the value1362            // must be false.1363            Expr::EvalResult LHSResult;1364            if (Bop->getLHS()->EvaluateAsInt(LHSResult, *Context)) {1365              llvm::APSInt IntVal = LHSResult.Val.getInt();1366              if (!IntVal.getBoolValue()) {1367                return TryResult(false);1368              }1369            }1370            Expr::EvalResult RHSResult;1371            if (Bop->getRHS()->EvaluateAsInt(RHSResult, *Context)) {1372              llvm::APSInt IntVal = RHSResult.Val.getInt();1373              if (!IntVal.getBoolValue()) {1374                return TryResult(false);1375              }1376            }1377          }1378          break;1379        }1380      }1381    }1382 1383    return evaluateAsBooleanConditionNoCache(S);1384  }1385 1386  /// Evaluate as boolean \param E without using the cache.1387  TryResult evaluateAsBooleanConditionNoCache(Expr *E) {1388    if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(E)) {1389      if (Bop->isLogicalOp()) {1390        TryResult LHS = tryEvaluateBool(Bop->getLHS());1391        if (LHS.isKnown()) {1392          // We were able to evaluate the LHS, see if we can get away with not1393          // evaluating the RHS: 0 && X -> 0, 1 || X -> 11394          if (LHS.isTrue() == (Bop->getOpcode() == BO_LOr))1395            return LHS.isTrue();1396 1397          TryResult RHS = tryEvaluateBool(Bop->getRHS());1398          if (RHS.isKnown()) {1399            if (Bop->getOpcode() == BO_LOr)1400              return LHS.isTrue() || RHS.isTrue();1401            else1402              return LHS.isTrue() && RHS.isTrue();1403          }1404        } else {1405          TryResult RHS = tryEvaluateBool(Bop->getRHS());1406          if (RHS.isKnown()) {1407            // We can't evaluate the LHS; however, sometimes the result1408            // is determined by the RHS: X && 0 -> 0, X || 1 -> 1.1409            if (RHS.isTrue() == (Bop->getOpcode() == BO_LOr))1410              return RHS.isTrue();1411          } else {1412            TryResult BopRes = checkIncorrectLogicOperator(Bop);1413            if (BopRes.isKnown())1414              return BopRes.isTrue();1415          }1416        }1417 1418        return {};1419      } else if (Bop->isEqualityOp()) {1420          TryResult BopRes = checkIncorrectEqualityOperator(Bop);1421          if (BopRes.isKnown())1422            return BopRes.isTrue();1423      } else if (Bop->isRelationalOp()) {1424        TryResult BopRes = checkIncorrectRelationalOperator(Bop);1425        if (BopRes.isKnown())1426          return BopRes.isTrue();1427      } else if (Bop->getOpcode() == BO_Or) {1428        TryResult BopRes = checkIncorrectBitwiseOrOperator(Bop);1429        if (BopRes.isKnown())1430          return BopRes.isTrue();1431      }1432    }1433 1434    bool Result;1435    if (E->EvaluateAsBooleanCondition(Result, *Context))1436      return Result;1437 1438    return {};1439  }1440 1441  bool hasTrivialDestructor(const VarDecl *VD) const;1442  bool needsAutomaticDestruction(const VarDecl *VD) const;1443};1444 1445} // namespace1446 1447Expr *1448clang::extractElementInitializerFromNestedAILE(const ArrayInitLoopExpr *AILE) {1449  if (!AILE)1450    return nullptr;1451 1452  Expr *AILEInit = AILE->getSubExpr();1453  while (const auto *E = dyn_cast<ArrayInitLoopExpr>(AILEInit))1454    AILEInit = E->getSubExpr();1455 1456  return AILEInit;1457}1458 1459inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder,1460                                     const Stmt *stmt) const {1461  return builder.alwaysAdd(stmt) || kind == AlwaysAdd;1462}1463 1464bool CFGBuilder::alwaysAdd(const Stmt *stmt) {1465  bool shouldAdd = BuildOpts.alwaysAdd(stmt);1466 1467  if (!BuildOpts.forcedBlkExprs)1468    return shouldAdd;1469 1470  if (lastLookup == stmt) {1471    if (cachedEntry) {1472      assert(cachedEntry->first == stmt);1473      return true;1474    }1475    return shouldAdd;1476  }1477 1478  lastLookup = stmt;1479 1480  // Perform the lookup!1481  CFG::BuildOptions::ForcedBlkExprs *fb = *BuildOpts.forcedBlkExprs;1482 1483  if (!fb) {1484    // No need to update 'cachedEntry', since it will always be null.1485    assert(!cachedEntry);1486    return shouldAdd;1487  }1488 1489  CFG::BuildOptions::ForcedBlkExprs::iterator itr = fb->find(stmt);1490  if (itr == fb->end()) {1491    cachedEntry = nullptr;1492    return shouldAdd;1493  }1494 1495  cachedEntry = &*itr;1496  return true;1497}1498 1499// FIXME: Add support for dependent-sized array types in C++?1500// Does it even make sense to build a CFG for an uninstantiated template?1501static const VariableArrayType *FindVA(const Type *t) {1502  while (const ArrayType *vt = dyn_cast<ArrayType>(t)) {1503    if (const VariableArrayType *vat = dyn_cast<VariableArrayType>(vt))1504      if (vat->getSizeExpr())1505        return vat;1506 1507    t = vt->getElementType().getTypePtr();1508  }1509 1510  return nullptr;1511}1512 1513void CFGBuilder::consumeConstructionContext(1514    const ConstructionContextLayer *Layer, Expr *E) {1515  assert((isa<CXXConstructExpr>(E) || isa<CallExpr>(E) ||1516          isa<ObjCMessageExpr>(E)) && "Expression cannot construct an object!");1517  if (const ConstructionContextLayer *PreviouslyStoredLayer =1518          ConstructionContextMap.lookup(E)) {1519    (void)PreviouslyStoredLayer;1520    // We might have visited this child when we were finding construction1521    // contexts within its parents.1522    assert(PreviouslyStoredLayer->isStrictlyMoreSpecificThan(Layer) &&1523           "Already within a different construction context!");1524  } else {1525    ConstructionContextMap[E] = Layer;1526  }1527}1528 1529void CFGBuilder::findConstructionContexts(1530    const ConstructionContextLayer *Layer, Stmt *Child) {1531  if (!BuildOpts.AddRichCXXConstructors)1532    return;1533 1534  if (!Child)1535    return;1536 1537  auto withExtraLayer = [this, Layer](const ConstructionContextItem &Item) {1538    return ConstructionContextLayer::create(cfg->getBumpVectorContext(), Item,1539                                            Layer);1540  };1541 1542  switch(Child->getStmtClass()) {1543  case Stmt::CXXConstructExprClass:1544  case Stmt::CXXTemporaryObjectExprClass: {1545    // Support pre-C++17 copy elision AST.1546    auto *CE = cast<CXXConstructExpr>(Child);1547    if (BuildOpts.MarkElidedCXXConstructors && CE->isElidable()) {1548      findConstructionContexts(withExtraLayer(CE), CE->getArg(0));1549    }1550 1551    consumeConstructionContext(Layer, CE);1552    break;1553  }1554  // FIXME: This, like the main visit, doesn't support CUDAKernelCallExpr.1555  // FIXME: An isa<> would look much better but this whole switch is a1556  // workaround for an internal compiler error in MSVC 2015 (see r326021).1557  case Stmt::CallExprClass:1558  case Stmt::CXXMemberCallExprClass:1559  case Stmt::CXXOperatorCallExprClass:1560  case Stmt::UserDefinedLiteralClass:1561  case Stmt::ObjCMessageExprClass: {1562    auto *E = cast<Expr>(Child);1563    if (CFGCXXRecordTypedCall::isCXXRecordTypedCall(E))1564      consumeConstructionContext(Layer, E);1565    break;1566  }1567  case Stmt::ExprWithCleanupsClass: {1568    auto *Cleanups = cast<ExprWithCleanups>(Child);1569    findConstructionContexts(Layer, Cleanups->getSubExpr());1570    break;1571  }1572  case Stmt::CXXFunctionalCastExprClass: {1573    auto *Cast = cast<CXXFunctionalCastExpr>(Child);1574    findConstructionContexts(Layer, Cast->getSubExpr());1575    break;1576  }1577  case Stmt::ImplicitCastExprClass: {1578    auto *Cast = cast<ImplicitCastExpr>(Child);1579    // Should we support other implicit cast kinds?1580    switch (Cast->getCastKind()) {1581    case CK_NoOp:1582    case CK_ConstructorConversion:1583      findConstructionContexts(Layer, Cast->getSubExpr());1584      break;1585    default:1586      break;1587    }1588    break;1589  }1590  case Stmt::CXXBindTemporaryExprClass: {1591    auto *BTE = cast<CXXBindTemporaryExpr>(Child);1592    findConstructionContexts(withExtraLayer(BTE), BTE->getSubExpr());1593    break;1594  }1595  case Stmt::MaterializeTemporaryExprClass: {1596    // Normally we don't want to search in MaterializeTemporaryExpr because1597    // it indicates the beginning of a temporary object construction context,1598    // so it shouldn't be found in the middle. However, if it is the beginning1599    // of an elidable copy or move construction context, we need to include it.1600    if (Layer->getItem().getKind() ==1601        ConstructionContextItem::ElidableConstructorKind) {1602      auto *MTE = cast<MaterializeTemporaryExpr>(Child);1603      findConstructionContexts(withExtraLayer(MTE), MTE->getSubExpr());1604    }1605    break;1606  }1607  case Stmt::ConditionalOperatorClass: {1608    auto *CO = cast<ConditionalOperator>(Child);1609    if (Layer->getItem().getKind() !=1610        ConstructionContextItem::MaterializationKind) {1611      // If the object returned by the conditional operator is not going to be a1612      // temporary object that needs to be immediately materialized, then1613      // it must be C++17 with its mandatory copy elision. Do not yet promise1614      // to support this case.1615      assert(!CO->getType()->getAsCXXRecordDecl() || CO->isGLValue() ||1616             Context->getLangOpts().CPlusPlus17);1617      break;1618    }1619    findConstructionContexts(Layer, CO->getLHS());1620    findConstructionContexts(Layer, CO->getRHS());1621    break;1622  }1623  case Stmt::InitListExprClass: {1624    auto *ILE = cast<InitListExpr>(Child);1625    if (ILE->isTransparent()) {1626      findConstructionContexts(Layer, ILE->getInit(0));1627      break;1628    }1629    // TODO: Handle other cases. For now, fail to find construction contexts.1630    break;1631  }1632  case Stmt::ParenExprClass: {1633    // If expression is placed into parenthesis we should propagate the parent1634    // construction context to subexpressions.1635    auto *PE = cast<ParenExpr>(Child);1636    findConstructionContexts(Layer, PE->getSubExpr());1637    break;1638  }1639  default:1640    break;1641  }1642}1643 1644void CFGBuilder::cleanupConstructionContext(Expr *E) {1645  assert(BuildOpts.AddRichCXXConstructors &&1646         "We should not be managing construction contexts!");1647  assert(ConstructionContextMap.count(E) &&1648         "Cannot exit construction context without the context!");1649  ConstructionContextMap.erase(E);1650}1651 1652/// BuildCFG - Constructs a CFG from an AST (a Stmt*).  The AST can represent an1653///  arbitrary statement.  Examples include a single expression or a function1654///  body (compound statement).  The ownership of the returned CFG is1655///  transferred to the caller.  If CFG construction fails, this method returns1656///  NULL.1657std::unique_ptr<CFG> CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) {1658  assert(cfg.get());1659  if (!Statement)1660    return nullptr;1661 1662  // Create an empty block that will serve as the exit block for the CFG.  Since1663  // this is the first block added to the CFG, it will be implicitly registered1664  // as the exit block.1665  Succ = createBlock();1666  assert(Succ == &cfg->getExit());1667  Block = nullptr;  // the EXIT block is empty.  Create all other blocks lazily.1668 1669  // Add parameters to the initial scope to handle their dtos and lifetime ends.1670  LocalScope *paramScope = nullptr;1671  if (const auto *FD = dyn_cast_or_null<FunctionDecl>(D))1672    for (ParmVarDecl *PD : FD->parameters())1673      paramScope = addLocalScopeForVarDecl(PD, paramScope);1674 1675  if (BuildOpts.AddImplicitDtors)1676    if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(D))1677      addImplicitDtorsForDestructor(DD);1678 1679  // Visit the statements and create the CFG.1680  CFGBlock *B = addStmt(Statement);1681 1682  if (badCFG)1683    return nullptr;1684 1685  // For C++ constructor add initializers to CFG. Constructors of virtual bases1686  // are ignored unless the object is of the most derived class.1687  //   class VBase { VBase() = default; VBase(int) {} };1688  //   class A : virtual public VBase { A() : VBase(0) {} };1689  //   class B : public A {};1690  //   B b; // Constructor calls in order: VBase(), A(), B().1691  //        // VBase(0) is ignored because A isn't the most derived class.1692  // This may result in the virtual base(s) being already initialized at this1693  // point, in which case we should jump right onto non-virtual bases and1694  // fields. To handle this, make a CFG branch. We only need to add one such1695  // branch per constructor, since the Standard states that all virtual bases1696  // shall be initialized before non-virtual bases and direct data members.1697  if (const auto *CD = dyn_cast_or_null<CXXConstructorDecl>(D)) {1698    CFGBlock *VBaseSucc = nullptr;1699    for (auto *I : llvm::reverse(CD->inits())) {1700      if (BuildOpts.AddVirtualBaseBranches && !VBaseSucc &&1701          I->isBaseInitializer() && I->isBaseVirtual()) {1702        // We've reached the first virtual base init while iterating in reverse1703        // order. Make a new block for virtual base initializers so that we1704        // could skip them.1705        VBaseSucc = Succ = B ? B : &cfg->getExit();1706        Block = createBlock();1707      }1708      B = addInitializer(I);1709      if (badCFG)1710        return nullptr;1711    }1712    if (VBaseSucc) {1713      // Make a branch block for potentially skipping virtual base initializers.1714      Succ = VBaseSucc;1715      B = createBlock();1716      B->setTerminator(1717          CFGTerminator(nullptr, CFGTerminator::VirtualBaseBranch));1718      addSuccessor(B, Block, true);1719    }1720  }1721 1722  if (B)1723    Succ = B;1724 1725  // Backpatch the gotos whose label -> block mappings we didn't know when we1726  // encountered them.1727  for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(),1728                                   E = BackpatchBlocks.end(); I != E; ++I ) {1729 1730    CFGBlock *B = I->block;1731    if (auto *G = dyn_cast<GotoStmt>(B->getTerminator())) {1732      LabelMapTy::iterator LI = LabelMap.find(G->getLabel());1733      // If there is no target for the goto, then we are looking at an1734      // incomplete AST.  Handle this by not registering a successor.1735      if (LI == LabelMap.end())1736        continue;1737      JumpTarget JT = LI->second;1738 1739      CFGBlock *SuccBlk = createScopeChangesHandlingBlock(1740          I->scopePosition, B, JT.scopePosition, JT.block);1741      addSuccessor(B, SuccBlk);1742    } else if (auto *G = dyn_cast<GCCAsmStmt>(B->getTerminator())) {1743      CFGBlock *Successor  = (I+1)->block;1744      for (auto *L : G->labels()) {1745        LabelMapTy::iterator LI = LabelMap.find(L->getLabel());1746        // If there is no target for the goto, then we are looking at an1747        // incomplete AST.  Handle this by not registering a successor.1748        if (LI == LabelMap.end())1749          continue;1750        JumpTarget JT = LI->second;1751        // Successor has been added, so skip it.1752        if (JT.block == Successor)1753          continue;1754        addSuccessor(B, JT.block);1755      }1756      I++;1757    }1758  }1759 1760  // Add successors to the Indirect Goto Dispatch block (if we have one).1761  if (CFGBlock *B = cfg->getIndirectGotoBlock())1762    for (LabelDecl *LD : AddressTakenLabels) {1763      // Lookup the target block.1764      LabelMapTy::iterator LI = LabelMap.find(LD);1765 1766      // If there is no target block that contains label, then we are looking1767      // at an incomplete AST.  Handle this by not registering a successor.1768      if (LI == LabelMap.end()) continue;1769 1770      addSuccessor(B, LI->second.block);1771    }1772 1773  // Create an empty entry block that has no predecessors.1774  cfg->setEntry(createBlock());1775 1776  if (BuildOpts.AddRichCXXConstructors)1777    assert(ConstructionContextMap.empty() &&1778           "Not all construction contexts were cleaned up!");1779 1780  return std::move(cfg);1781}1782 1783/// createBlock - Used to lazily create blocks that are connected1784///  to the current (global) successor.1785CFGBlock *CFGBuilder::createBlock(bool add_successor) {1786  CFGBlock *B = cfg->createBlock();1787  if (add_successor && Succ)1788    addSuccessor(B, Succ);1789  return B;1790}1791 1792/// createNoReturnBlock - Used to create a block is a 'noreturn' point in the1793/// CFG. It is *not* connected to the current (global) successor, and instead1794/// directly tied to the exit block in order to be reachable.1795CFGBlock *CFGBuilder::createNoReturnBlock() {1796  CFGBlock *B = createBlock(false);1797  B->setHasNoReturnElement();1798  addSuccessor(B, &cfg->getExit(), Succ);1799  return B;1800}1801 1802/// addInitializer - Add C++ base or member initializer element to CFG.1803CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) {1804  if (!BuildOpts.AddInitializers)1805    return Block;1806 1807  bool HasTemporaries = false;1808 1809  // Destructors of temporaries in initialization expression should be called1810  // after initialization finishes.1811  Expr *Init = I->getInit();1812  if (Init) {1813    HasTemporaries = isa<ExprWithCleanups>(Init);1814 1815    if (BuildOpts.AddTemporaryDtors && HasTemporaries) {1816      // Generate destructors for temporaries in initialization expression.1817      TempDtorContext Context;1818      VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),1819                             /*ExternallyDestructed=*/false, Context);1820    }1821  }1822 1823  autoCreateBlock();1824  appendInitializer(Block, I);1825 1826  if (Init) {1827    // If the initializer is an ArrayInitLoopExpr, we want to extract the1828    // initializer, that's used for each element.1829    auto *AILEInit = extractElementInitializerFromNestedAILE(1830        dyn_cast<ArrayInitLoopExpr>(Init));1831 1832    findConstructionContexts(1833        ConstructionContextLayer::create(cfg->getBumpVectorContext(), I),1834        AILEInit ? AILEInit : Init);1835 1836    if (HasTemporaries) {1837      // For expression with temporaries go directly to subexpression to omit1838      // generating destructors for the second time.1839      return Visit(cast<ExprWithCleanups>(Init)->getSubExpr());1840    }1841    if (BuildOpts.AddCXXDefaultInitExprInCtors) {1842      if (CXXDefaultInitExpr *Default = dyn_cast<CXXDefaultInitExpr>(Init)) {1843        // In general, appending the expression wrapped by a CXXDefaultInitExpr1844        // may cause the same Expr to appear more than once in the CFG. Doing it1845        // here is safe because there's only one initializer per field.1846        autoCreateBlock();1847        appendStmt(Block, Default);1848        if (Stmt *Child = Default->getExpr())1849          if (CFGBlock *R = Visit(Child))1850            Block = R;1851        return Block;1852      }1853    }1854    return Visit(Init);1855  }1856 1857  return Block;1858}1859 1860/// Retrieve the type of the temporary object whose lifetime was1861/// extended by a local reference with the given initializer.1862static QualType getReferenceInitTemporaryType(const Expr *Init,1863                                              bool *FoundMTE = nullptr) {1864  while (true) {1865    // Skip parentheses.1866    Init = Init->IgnoreParens();1867 1868    // Skip through cleanups.1869    if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Init)) {1870      Init = EWC->getSubExpr();1871      continue;1872    }1873 1874    // Skip through the temporary-materialization expression.1875    if (const MaterializeTemporaryExpr *MTE1876          = dyn_cast<MaterializeTemporaryExpr>(Init)) {1877      Init = MTE->getSubExpr();1878      if (FoundMTE)1879        *FoundMTE = true;1880      continue;1881    }1882 1883    // Skip sub-object accesses into rvalues.1884    const Expr *SkippedInit = Init->skipRValueSubobjectAdjustments();1885    if (SkippedInit != Init) {1886      Init = SkippedInit;1887      continue;1888    }1889 1890    break;1891  }1892 1893  return Init->getType();1894}1895 1896// TODO: Support adding LoopExit element to the CFG in case where the loop is1897// ended by ReturnStmt, GotoStmt or ThrowExpr.1898void CFGBuilder::addLoopExit(const Stmt *LoopStmt){1899  if(!BuildOpts.AddLoopExit)1900    return;1901  autoCreateBlock();1902  appendLoopExit(Block, LoopStmt);1903}1904 1905/// Adds the CFG elements for leaving the scope of automatic objects in1906/// range [B, E). This include following:1907///   * AutomaticObjectDtor for variables with non-trivial destructor1908///   * LifetimeEnds for all variables1909///   * ScopeEnd for each scope left1910void CFGBuilder::addAutomaticObjHandling(LocalScope::const_iterator B,1911                                         LocalScope::const_iterator E,1912                                         Stmt *S) {1913  if (!BuildOpts.AddScopes && !BuildOpts.AddImplicitDtors &&1914      !BuildOpts.AddLifetime)1915    return;1916 1917  if (B == E)1918    return;1919 1920  // Not leaving the scope, only need to handle destruction and lifetime1921  if (B.inSameLocalScope(E)) {1922    addAutomaticObjDestruction(B, E, S);1923    return;1924  }1925 1926  // Extract information about all local scopes that are left1927  SmallVector<LocalScope::const_iterator, 10> LocalScopeEndMarkers;1928  LocalScopeEndMarkers.push_back(B);1929  for (LocalScope::const_iterator I = B; I != E; ++I) {1930    if (!I.inSameLocalScope(LocalScopeEndMarkers.back()))1931      LocalScopeEndMarkers.push_back(I);1932  }1933  LocalScopeEndMarkers.push_back(E);1934 1935  // We need to leave the scope in reverse order, so we reverse the end1936  // markers1937  std::reverse(LocalScopeEndMarkers.begin(), LocalScopeEndMarkers.end());1938  auto Pairwise =1939      llvm::zip(LocalScopeEndMarkers, llvm::drop_begin(LocalScopeEndMarkers));1940  for (auto [E, B] : Pairwise) {1941    if (!B.inSameLocalScope(E))1942      addScopeExitHandling(B, E, S);1943    addAutomaticObjDestruction(B, E, S);1944  }1945}1946 1947/// Add CFG elements corresponding to call destructor and end of lifetime1948/// of all automatic variables with non-trivial destructor in range [B, E).1949/// This include AutomaticObjectDtor and LifetimeEnds elements.1950void CFGBuilder::addAutomaticObjDestruction(LocalScope::const_iterator B,1951                                            LocalScope::const_iterator E,1952                                            Stmt *S) {1953  if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime)1954    return;1955 1956  if (B == E)1957    return;1958 1959  SmallVector<VarDecl *, 10> DeclsNeedDestruction;1960  DeclsNeedDestruction.reserve(B.distance(E));1961 1962  for (VarDecl* D : llvm::make_range(B, E))1963    if (needsAutomaticDestruction(D))1964      DeclsNeedDestruction.push_back(D);1965 1966  for (VarDecl *VD : llvm::reverse(DeclsNeedDestruction)) {1967    if (BuildOpts.AddImplicitDtors) {1968      // If this destructor is marked as a no-return destructor, we need to1969      // create a new block for the destructor which does not have as a1970      // successor anything built thus far: control won't flow out of this1971      // block.1972      QualType Ty = VD->getType();1973      if (Ty->isReferenceType())1974        Ty = getReferenceInitTemporaryType(VD->getInit());1975      Ty = Context->getBaseElementType(Ty);1976 1977      const CXXRecordDecl *CRD = Ty->getAsCXXRecordDecl();1978      if (CRD && CRD->isAnyDestructorNoReturn())1979        Block = createNoReturnBlock();1980    }1981 1982    autoCreateBlock();1983 1984    // Add LifetimeEnd after automatic obj with non-trivial destructors,1985    // as they end their lifetime when the destructor returns. For trivial1986    // objects, we end lifetime with scope end.1987    if (BuildOpts.AddLifetime)1988      appendLifetimeEnds(Block, VD, S);1989    if (BuildOpts.AddImplicitDtors && !hasTrivialDestructor(VD))1990      appendAutomaticObjDtor(Block, VD, S);1991    if (VD->hasAttr<CleanupAttr>())1992      appendCleanupFunction(Block, VD);1993  }1994}1995 1996/// Add CFG elements corresponding to leaving a scope.1997/// Assumes that range [B, E) corresponds to single scope.1998/// This add following elements:1999///   * LifetimeEnds for all variables with non-trivial destructor2000///   * ScopeEnd for each scope left2001void CFGBuilder::addScopeExitHandling(LocalScope::const_iterator B,2002                                      LocalScope::const_iterator E, Stmt *S) {2003  assert(!B.inSameLocalScope(E));2004  if (!BuildOpts.AddLifetime && !BuildOpts.AddScopes)2005    return;2006 2007  if (BuildOpts.AddScopes) {2008    autoCreateBlock();2009    appendScopeEnd(Block, B.getFirstVarInScope(), S);2010  }2011 2012  if (!BuildOpts.AddLifetime)2013    return;2014 2015  // We need to perform the scope leaving in reverse order2016  SmallVector<VarDecl *, 10> DeclsTrivial;2017  DeclsTrivial.reserve(B.distance(E));2018 2019  // Objects with trivial destructor ends their lifetime when their storage2020  // is destroyed, for automatic variables, this happens when the end of the2021  // scope is added.2022  for (VarDecl* D : llvm::make_range(B, E))2023    if (!needsAutomaticDestruction(D))2024      DeclsTrivial.push_back(D);2025 2026  if (DeclsTrivial.empty())2027    return;2028 2029  autoCreateBlock();2030  for (VarDecl *VD : llvm::reverse(DeclsTrivial))2031    appendLifetimeEnds(Block, VD, S);2032}2033 2034/// addScopeChangesHandling - appends information about destruction, lifetime2035/// and cfgScopeEnd for variables in the scope that was left by the jump, and2036/// appends cfgScopeBegin for all scopes that where entered.2037/// We insert the cfgScopeBegin at the end of the jump node, as depending on2038/// the sourceBlock, each goto, may enter different amount of scopes.2039void CFGBuilder::addScopeChangesHandling(LocalScope::const_iterator SrcPos,2040                                         LocalScope::const_iterator DstPos,2041                                         Stmt *S) {2042  assert(Block && "Source block should be always crated");2043  if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&2044      !BuildOpts.AddScopes) {2045    return;2046  }2047 2048  if (SrcPos == DstPos)2049    return;2050 2051  // Get common scope, the jump leaves all scopes [SrcPos, BasePos), and2052  // enter all scopes between [DstPos, BasePos)2053  LocalScope::const_iterator BasePos = SrcPos.shared_parent(DstPos);2054 2055  // Append scope begins for scopes entered by goto2056  if (BuildOpts.AddScopes && !DstPos.inSameLocalScope(BasePos)) {2057    for (LocalScope::const_iterator I = DstPos; I != BasePos; ++I)2058      if (I.pointsToFirstDeclaredVar())2059        appendScopeBegin(Block, *I, S);2060  }2061 2062  // Append scopeEnds, destructor and lifetime with the terminator for2063  // block left by goto.2064  addAutomaticObjHandling(SrcPos, BasePos, S);2065}2066 2067/// createScopeChangesHandlingBlock - Creates a block with cfgElements2068/// corresponding to changing the scope from the source scope of the GotoStmt,2069/// to destination scope. Add destructor, lifetime and cfgScopeEnd2070/// CFGElements to newly created CFGBlock, that will have the CFG terminator2071/// transferred.2072CFGBlock *CFGBuilder::createScopeChangesHandlingBlock(2073    LocalScope::const_iterator SrcPos, CFGBlock *SrcBlk,2074    LocalScope::const_iterator DstPos, CFGBlock *DstBlk) {2075  if (SrcPos == DstPos)2076    return DstBlk;2077 2078  if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&2079      (!BuildOpts.AddScopes || SrcPos.inSameLocalScope(DstPos)))2080    return DstBlk;2081 2082  // We will update CFBBuilder when creating new block, restore the2083  // previous state at exit.2084  SaveAndRestore save_Block(Block), save_Succ(Succ);2085 2086  // Create a new block, and transfer terminator2087  Block = createBlock(false);2088  Block->setTerminator(SrcBlk->getTerminator());2089  SrcBlk->setTerminator(CFGTerminator());2090  addSuccessor(Block, DstBlk);2091 2092  // Fill the created Block with the required elements.2093  addScopeChangesHandling(SrcPos, DstPos, Block->getTerminatorStmt());2094 2095  assert(Block && "There should be at least one scope changing Block");2096  return Block;2097}2098 2099/// addImplicitDtorsForDestructor - Add implicit destructors generated for2100/// base and member objects in destructor.2101void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) {2102  assert(BuildOpts.AddImplicitDtors &&2103         "Can be called only when dtors should be added");2104  const CXXRecordDecl *RD = DD->getParent();2105 2106  // At the end destroy virtual base objects.2107  for (const auto &VI : RD->vbases()) {2108    // TODO: Add a VirtualBaseBranch to see if the most derived class2109    // (which is different from the current class) is responsible for2110    // destroying them.2111    const CXXRecordDecl *CD = VI.getType()->getAsCXXRecordDecl();2112    if (CD && !CD->hasTrivialDestructor()) {2113      autoCreateBlock();2114      appendBaseDtor(Block, &VI);2115    }2116  }2117 2118  // Before virtual bases destroy direct base objects.2119  for (const auto &BI : RD->bases()) {2120    if (!BI.isVirtual()) {2121      const CXXRecordDecl *CD = BI.getType()->getAsCXXRecordDecl();2122      if (CD && !CD->hasTrivialDestructor()) {2123        autoCreateBlock();2124        appendBaseDtor(Block, &BI);2125      }2126    }2127  }2128 2129  // First destroy member objects.2130  if (RD->isUnion())2131    return;2132  for (auto *FI : RD->fields()) {2133    // Check for constant size array. Set type to array element type.2134    QualType QT = FI->getType();2135    // It may be a multidimensional array.2136    while (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) {2137      if (AT->isZeroSize())2138        break;2139      QT = AT->getElementType();2140    }2141 2142    if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())2143      if (!CD->hasTrivialDestructor()) {2144        autoCreateBlock();2145        appendMemberDtor(Block, FI);2146      }2147  }2148}2149 2150/// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either2151/// way return valid LocalScope object.2152LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) {2153  if (Scope)2154    return Scope;2155  llvm::BumpPtrAllocator &alloc = cfg->getAllocator();2156  return new (alloc) LocalScope(BumpVectorContext(alloc), ScopePos);2157}2158 2159/// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement2160/// that should create implicit scope (e.g. if/else substatements).2161void CFGBuilder::addLocalScopeForStmt(Stmt *S) {2162  if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&2163      !BuildOpts.AddScopes)2164    return;2165 2166  LocalScope *Scope = nullptr;2167 2168  // For compound statement we will be creating explicit scope.2169  if (CompoundStmt *CS = dyn_cast<CompoundStmt>(S)) {2170    for (auto *BI : CS->body()) {2171      Stmt *SI = BI->stripLabelLikeStatements();2172      if (DeclStmt *DS = dyn_cast<DeclStmt>(SI))2173        Scope = addLocalScopeForDeclStmt(DS, Scope);2174    }2175    return;2176  }2177 2178  // For any other statement scope will be implicit and as such will be2179  // interesting only for DeclStmt.2180  if (DeclStmt *DS = dyn_cast<DeclStmt>(S->stripLabelLikeStatements()))2181    addLocalScopeForDeclStmt(DS);2182}2183 2184/// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will2185/// reuse Scope if not NULL.2186LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt *DS,2187                                                 LocalScope* Scope) {2188  if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&2189      !BuildOpts.AddScopes)2190    return Scope;2191 2192  for (auto *DI : DS->decls())2193    if (VarDecl *VD = dyn_cast<VarDecl>(DI))2194      Scope = addLocalScopeForVarDecl(VD, Scope);2195  return Scope;2196}2197 2198bool CFGBuilder::needsAutomaticDestruction(const VarDecl *VD) const {2199  return !hasTrivialDestructor(VD) || VD->hasAttr<CleanupAttr>();2200}2201 2202bool CFGBuilder::hasTrivialDestructor(const VarDecl *VD) const {2203  // Check for const references bound to temporary. Set type to pointee.2204  QualType QT = VD->getType();2205  if (QT->isReferenceType()) {2206    // Attempt to determine whether this declaration lifetime-extends a2207    // temporary.2208    //2209    // FIXME: This is incorrect. Non-reference declarations can lifetime-extend2210    // temporaries, and a single declaration can extend multiple temporaries.2211    // We should look at the storage duration on each nested2212    // MaterializeTemporaryExpr instead.2213 2214    const Expr *Init = VD->getInit();2215    if (!Init) {2216      // Probably an exception catch-by-reference variable.2217      // FIXME: It doesn't really mean that the object has a trivial destructor.2218      // Also are there other cases?2219      return true;2220    }2221 2222    // Lifetime-extending a temporary?2223    bool FoundMTE = false;2224    QT = getReferenceInitTemporaryType(Init, &FoundMTE);2225    if (!FoundMTE)2226      return true;2227  }2228 2229  // Check for constant size array. Set type to array element type.2230  while (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) {2231    if (AT->isZeroSize())2232      return true;2233    QT = AT->getElementType();2234  }2235 2236  // Check if type is a C++ class with non-trivial destructor.2237  if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl())2238    return !CD->hasDefinition() || CD->hasTrivialDestructor();2239  return true;2240}2241 2242/// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will2243/// create add scope for automatic objects and temporary objects bound to2244/// const reference. Will reuse Scope if not NULL.2245LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD,2246                                                LocalScope* Scope) {2247  if (!BuildOpts.AddImplicitDtors && !BuildOpts.AddLifetime &&2248      !BuildOpts.AddScopes)2249    return Scope;2250 2251  // Check if variable is local.2252  if (!VD->hasLocalStorage())2253    return Scope;2254 2255  // Reference parameters are aliases to objects that live elsewhere, so they2256  // don't require automatic destruction or lifetime tracking.2257  if (isa<ParmVarDecl>(VD) && VD->getType()->isReferenceType())2258    return Scope;2259 2260  if (!BuildOpts.AddLifetime && !BuildOpts.AddScopes &&2261      !needsAutomaticDestruction(VD)) {2262    assert(BuildOpts.AddImplicitDtors);2263    return Scope;2264  }2265 2266  // Add the variable to scope2267  Scope = createOrReuseLocalScope(Scope);2268  Scope->addVar(VD);2269  ScopePos = Scope->begin();2270  return Scope;2271}2272 2273/// addLocalScopeAndDtors - For given statement add local scope for it and2274/// add destructors that will cleanup the scope. Will reuse Scope if not NULL.2275void CFGBuilder::addLocalScopeAndDtors(Stmt *S) {2276  LocalScope::const_iterator scopeBeginPos = ScopePos;2277  addLocalScopeForStmt(S);2278  addAutomaticObjHandling(ScopePos, scopeBeginPos, S);2279}2280 2281/// Visit - Walk the subtree of a statement and add extra2282///   blocks for ternary operators, &&, and ||.  We also process "," and2283///   DeclStmts (which may contain nested control-flow).2284CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc,2285                            bool ExternallyDestructed) {2286  if (!S) {2287    badCFG = true;2288    return nullptr;2289  }2290 2291  if (Expr *E = dyn_cast<Expr>(S))2292    S = E->IgnoreParens();2293 2294  if (Context->getLangOpts().OpenMP)2295    if (auto *D = dyn_cast<OMPExecutableDirective>(S))2296      return VisitOMPExecutableDirective(D, asc);2297 2298  switch (S->getStmtClass()) {2299    default:2300      return VisitStmt(S, asc);2301 2302    case Stmt::ImplicitValueInitExprClass:2303      if (BuildOpts.OmitImplicitValueInitializers)2304        return Block;2305      return VisitStmt(S, asc);2306 2307    case Stmt::InitListExprClass:2308      return VisitInitListExpr(cast<InitListExpr>(S), asc);2309 2310    case Stmt::AttributedStmtClass:2311      return VisitAttributedStmt(cast<AttributedStmt>(S), asc);2312 2313    case Stmt::AddrLabelExprClass:2314      return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc);2315 2316    case Stmt::BinaryConditionalOperatorClass:2317      return VisitConditionalOperator(cast<BinaryConditionalOperator>(S), asc);2318 2319    case Stmt::BinaryOperatorClass:2320      return VisitBinaryOperator(cast<BinaryOperator>(S), asc);2321 2322    case Stmt::BlockExprClass:2323      return VisitBlockExpr(cast<BlockExpr>(S), asc);2324 2325    case Stmt::BreakStmtClass:2326      return VisitBreakStmt(cast<BreakStmt>(S));2327 2328    case Stmt::CallExprClass:2329    case Stmt::CXXOperatorCallExprClass:2330    case Stmt::CXXMemberCallExprClass:2331    case Stmt::UserDefinedLiteralClass:2332      return VisitCallExpr(cast<CallExpr>(S), asc);2333 2334    case Stmt::CaseStmtClass:2335      return VisitCaseStmt(cast<CaseStmt>(S));2336 2337    case Stmt::ChooseExprClass:2338      return VisitChooseExpr(cast<ChooseExpr>(S), asc);2339 2340    case Stmt::CompoundStmtClass:2341      return VisitCompoundStmt(cast<CompoundStmt>(S), ExternallyDestructed);2342 2343    case Stmt::ConditionalOperatorClass:2344      return VisitConditionalOperator(cast<ConditionalOperator>(S), asc);2345 2346    case Stmt::ContinueStmtClass:2347      return VisitContinueStmt(cast<ContinueStmt>(S));2348 2349    case Stmt::CXXCatchStmtClass:2350      return VisitCXXCatchStmt(cast<CXXCatchStmt>(S));2351 2352    case Stmt::ExprWithCleanupsClass:2353      return VisitExprWithCleanups(cast<ExprWithCleanups>(S),2354                                   asc, ExternallyDestructed);2355 2356    case Stmt::CXXDefaultArgExprClass:2357    case Stmt::CXXDefaultInitExprClass:2358      // FIXME: The expression inside a CXXDefaultArgExpr is owned by the2359      // called function's declaration, not by the caller. If we simply add2360      // this expression to the CFG, we could end up with the same Expr2361      // appearing multiple times (PR13385).2362      //2363      // It's likewise possible for multiple CXXDefaultInitExprs for the same2364      // expression to be used in the same function (through aggregate2365      // initialization).2366      return VisitStmt(S, asc);2367 2368    case Stmt::CXXBindTemporaryExprClass:2369      return VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), asc);2370 2371    case Stmt::CXXConstructExprClass:2372      return VisitCXXConstructExpr(cast<CXXConstructExpr>(S), asc);2373 2374    case Stmt::CXXNewExprClass:2375      return VisitCXXNewExpr(cast<CXXNewExpr>(S), asc);2376 2377    case Stmt::CXXDeleteExprClass:2378      return VisitCXXDeleteExpr(cast<CXXDeleteExpr>(S), asc);2379 2380    case Stmt::CXXFunctionalCastExprClass:2381      return VisitCXXFunctionalCastExpr(cast<CXXFunctionalCastExpr>(S), asc);2382 2383    case Stmt::CXXTemporaryObjectExprClass:2384      return VisitCXXTemporaryObjectExpr(cast<CXXTemporaryObjectExpr>(S), asc);2385 2386    case Stmt::CXXThrowExprClass:2387      return VisitCXXThrowExpr(cast<CXXThrowExpr>(S));2388 2389    case Stmt::CXXTryStmtClass:2390      return VisitCXXTryStmt(cast<CXXTryStmt>(S));2391 2392    case Stmt::CXXTypeidExprClass:2393      return VisitCXXTypeidExpr(cast<CXXTypeidExpr>(S), asc);2394 2395    case Stmt::CXXForRangeStmtClass:2396      return VisitCXXForRangeStmt(cast<CXXForRangeStmt>(S));2397 2398    case Stmt::DeclStmtClass:2399      return VisitDeclStmt(cast<DeclStmt>(S));2400 2401    case Stmt::DefaultStmtClass:2402      return VisitDefaultStmt(cast<DefaultStmt>(S));2403 2404    case Stmt::DoStmtClass:2405      return VisitDoStmt(cast<DoStmt>(S));2406 2407    case Stmt::ForStmtClass:2408      return VisitForStmt(cast<ForStmt>(S));2409 2410    case Stmt::GotoStmtClass:2411      return VisitGotoStmt(cast<GotoStmt>(S));2412 2413    case Stmt::GCCAsmStmtClass:2414      return VisitGCCAsmStmt(cast<GCCAsmStmt>(S), asc);2415 2416    case Stmt::IfStmtClass:2417      return VisitIfStmt(cast<IfStmt>(S));2418 2419    case Stmt::ImplicitCastExprClass:2420      return VisitImplicitCastExpr(cast<ImplicitCastExpr>(S), asc);2421 2422    case Stmt::ConstantExprClass:2423      return VisitConstantExpr(cast<ConstantExpr>(S), asc);2424 2425    case Stmt::IndirectGotoStmtClass:2426      return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S));2427 2428    case Stmt::LabelStmtClass:2429      return VisitLabelStmt(cast<LabelStmt>(S));2430 2431    case Stmt::LambdaExprClass:2432      return VisitLambdaExpr(cast<LambdaExpr>(S), asc);2433 2434    case Stmt::MaterializeTemporaryExprClass:2435      return VisitMaterializeTemporaryExpr(cast<MaterializeTemporaryExpr>(S),2436                                           asc);2437 2438    case Stmt::MemberExprClass:2439      return VisitMemberExpr(cast<MemberExpr>(S), asc);2440 2441    case Stmt::NullStmtClass:2442      return Block;2443 2444    case Stmt::ObjCAtCatchStmtClass:2445      return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S));2446 2447    case Stmt::ObjCAutoreleasePoolStmtClass:2448      return VisitObjCAutoreleasePoolStmt(cast<ObjCAutoreleasePoolStmt>(S));2449 2450    case Stmt::ObjCAtSynchronizedStmtClass:2451      return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S));2452 2453    case Stmt::ObjCAtThrowStmtClass:2454      return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S));2455 2456    case Stmt::ObjCAtTryStmtClass:2457      return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S));2458 2459    case Stmt::ObjCForCollectionStmtClass:2460      return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S));2461 2462    case Stmt::ObjCMessageExprClass:2463      return VisitObjCMessageExpr(cast<ObjCMessageExpr>(S), asc);2464 2465    case Stmt::OpaqueValueExprClass:2466      return Block;2467 2468    case Stmt::PseudoObjectExprClass:2469      return VisitPseudoObjectExpr(cast<PseudoObjectExpr>(S));2470 2471    case Stmt::ReturnStmtClass:2472    case Stmt::CoreturnStmtClass:2473      return VisitReturnStmt(S);2474 2475    case Stmt::CoyieldExprClass:2476    case Stmt::CoawaitExprClass:2477      return VisitCoroutineSuspendExpr(cast<CoroutineSuspendExpr>(S), asc);2478 2479    case Stmt::SEHExceptStmtClass:2480      return VisitSEHExceptStmt(cast<SEHExceptStmt>(S));2481 2482    case Stmt::SEHFinallyStmtClass:2483      return VisitSEHFinallyStmt(cast<SEHFinallyStmt>(S));2484 2485    case Stmt::SEHLeaveStmtClass:2486      return VisitSEHLeaveStmt(cast<SEHLeaveStmt>(S));2487 2488    case Stmt::SEHTryStmtClass:2489      return VisitSEHTryStmt(cast<SEHTryStmt>(S));2490 2491    case Stmt::UnaryExprOrTypeTraitExprClass:2492      return VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S),2493                                           asc);2494 2495    case Stmt::StmtExprClass:2496      return VisitStmtExpr(cast<StmtExpr>(S), asc);2497 2498    case Stmt::SwitchStmtClass:2499      return VisitSwitchStmt(cast<SwitchStmt>(S));2500 2501    case Stmt::UnaryOperatorClass:2502      return VisitUnaryOperator(cast<UnaryOperator>(S), asc);2503 2504    case Stmt::WhileStmtClass:2505      return VisitWhileStmt(cast<WhileStmt>(S));2506 2507    case Stmt::ArrayInitLoopExprClass:2508      return VisitArrayInitLoopExpr(cast<ArrayInitLoopExpr>(S), asc);2509  }2510}2511 2512CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) {2513  if (asc.alwaysAdd(*this, S)) {2514    autoCreateBlock();2515    appendStmt(Block, S);2516  }2517 2518  return VisitChildren(S);2519}2520 2521/// VisitChildren - Visit the children of a Stmt.2522CFGBlock *CFGBuilder::VisitChildren(Stmt *S) {2523  CFGBlock *B = Block;2524 2525  // Visit the children in their reverse order so that they appear in2526  // left-to-right (natural) order in the CFG.2527  reverse_children RChildren(S, *Context);2528  for (Stmt *Child : RChildren) {2529    if (Child)2530      if (CFGBlock *R = Visit(Child))2531        B = R;2532  }2533  return B;2534}2535 2536CFGBlock *CFGBuilder::VisitInitListExpr(InitListExpr *ILE, AddStmtChoice asc) {2537  if (asc.alwaysAdd(*this, ILE)) {2538    autoCreateBlock();2539    appendStmt(Block, ILE);2540  }2541  CFGBlock *B = Block;2542 2543  reverse_children RChildren(ILE, *Context);2544  for (Stmt *Child : RChildren) {2545    if (!Child)2546      continue;2547    if (CFGBlock *R = Visit(Child))2548      B = R;2549    if (BuildOpts.AddCXXDefaultInitExprInAggregates) {2550      if (auto *DIE = dyn_cast<CXXDefaultInitExpr>(Child))2551        if (Stmt *Child = DIE->getExpr())2552          if (CFGBlock *R = Visit(Child))2553            B = R;2554    }2555  }2556  return B;2557}2558 2559CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A,2560                                         AddStmtChoice asc) {2561  AddressTakenLabels.insert(A->getLabel());2562 2563  if (asc.alwaysAdd(*this, A)) {2564    autoCreateBlock();2565    appendStmt(Block, A);2566  }2567 2568  return Block;2569}2570 2571static bool isFallthroughStatement(const AttributedStmt *A) {2572  bool isFallthrough = hasSpecificAttr<FallThroughAttr>(A->getAttrs());2573  assert((!isFallthrough || isa<NullStmt>(A->getSubStmt())) &&2574         "expected fallthrough not to have children");2575  return isFallthrough;2576}2577 2578static bool isCXXAssumeAttr(const AttributedStmt *A) {2579  bool hasAssumeAttr = hasSpecificAttr<CXXAssumeAttr>(A->getAttrs());2580 2581  assert((!hasAssumeAttr || isa<NullStmt>(A->getSubStmt())) &&2582         "expected [[assume]] not to have children");2583  return hasAssumeAttr;2584}2585 2586CFGBlock *CFGBuilder::VisitAttributedStmt(AttributedStmt *A,2587                                          AddStmtChoice asc) {2588  // AttributedStmts for [[likely]] can have arbitrary statements as children,2589  // and the current visitation order here would add the AttributedStmts2590  // for [[likely]] after the child nodes, which is undesirable: For example,2591  // if the child contains an unconditional return, the [[likely]] would be2592  // considered unreachable.2593  // So only add the AttributedStmt for FallThrough, which has CFG effects and2594  // also no children, and omit the others. None of the other current StmtAttrs2595  // have semantic meaning for the CFG.2596  bool isInterestingAttribute = isFallthroughStatement(A) || isCXXAssumeAttr(A);2597  if (isInterestingAttribute && asc.alwaysAdd(*this, A)) {2598    autoCreateBlock();2599    appendStmt(Block, A);2600  }2601 2602  return VisitChildren(A);2603}2604 2605CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc) {2606  if (asc.alwaysAdd(*this, U)) {2607    autoCreateBlock();2608    appendStmt(Block, U);2609  }2610 2611  if (U->getOpcode() == UO_LNot)2612    tryEvaluateBool(U->getSubExpr()->IgnoreParens());2613 2614  return Visit(U->getSubExpr(), AddStmtChoice());2615}2616 2617CFGBlock *CFGBuilder::VisitLogicalOperator(BinaryOperator *B) {2618  CFGBlock *ConfluenceBlock = Block ? Block : createBlock();2619  appendStmt(ConfluenceBlock, B);2620 2621  if (badCFG)2622    return nullptr;2623 2624  return VisitLogicalOperator(B, nullptr, ConfluenceBlock,2625                              ConfluenceBlock).first;2626}2627 2628std::pair<CFGBlock*, CFGBlock*>2629CFGBuilder::VisitLogicalOperator(BinaryOperator *B,2630                                 Stmt *Term,2631                                 CFGBlock *TrueBlock,2632                                 CFGBlock *FalseBlock) {2633  // Introspect the RHS.  If it is a nested logical operation, we recursively2634  // build the CFG using this function.  Otherwise, resort to default2635  // CFG construction behavior.2636  Expr *RHS = B->getRHS()->IgnoreParens();2637  CFGBlock *RHSBlock, *ExitBlock;2638 2639  do {2640    if (BinaryOperator *B_RHS = dyn_cast<BinaryOperator>(RHS))2641      if (B_RHS->isLogicalOp()) {2642        std::tie(RHSBlock, ExitBlock) =2643          VisitLogicalOperator(B_RHS, Term, TrueBlock, FalseBlock);2644        break;2645      }2646 2647    // The RHS is not a nested logical operation.  Don't push the terminator2648    // down further, but instead visit RHS and construct the respective2649    // pieces of the CFG, and link up the RHSBlock with the terminator2650    // we have been provided.2651    ExitBlock = RHSBlock = createBlock(false);2652 2653    // Even though KnownVal is only used in the else branch of the next2654    // conditional, tryEvaluateBool performs additional checking on the2655    // Expr, so it should be called unconditionally.2656    TryResult KnownVal = tryEvaluateBool(RHS);2657    if (!KnownVal.isKnown())2658      KnownVal = tryEvaluateBool(B);2659 2660    if (!Term) {2661      assert(TrueBlock == FalseBlock);2662      addSuccessor(RHSBlock, TrueBlock);2663    }2664    else {2665      RHSBlock->setTerminator(Term);2666      addSuccessor(RHSBlock, TrueBlock, !KnownVal.isFalse());2667      addSuccessor(RHSBlock, FalseBlock, !KnownVal.isTrue());2668    }2669 2670    Block = RHSBlock;2671    RHSBlock = addStmt(RHS);2672  }2673  while (false);2674 2675  if (badCFG)2676    return std::make_pair(nullptr, nullptr);2677 2678  // Generate the blocks for evaluating the LHS.2679  Expr *LHS = B->getLHS()->IgnoreParens();2680 2681  if (BinaryOperator *B_LHS = dyn_cast<BinaryOperator>(LHS))2682    if (B_LHS->isLogicalOp()) {2683      if (B->getOpcode() == BO_LOr)2684        FalseBlock = RHSBlock;2685      else2686        TrueBlock = RHSBlock;2687 2688      // For the LHS, treat 'B' as the terminator that we want to sink2689      // into the nested branch.  The RHS always gets the top-most2690      // terminator.2691      return VisitLogicalOperator(B_LHS, B, TrueBlock, FalseBlock);2692    }2693 2694  // Create the block evaluating the LHS.2695  // This contains the '&&' or '||' as the terminator.2696  CFGBlock *LHSBlock = createBlock(false);2697  LHSBlock->setTerminator(B);2698 2699  Block = LHSBlock;2700  CFGBlock *EntryLHSBlock = addStmt(LHS);2701 2702  if (badCFG)2703    return std::make_pair(nullptr, nullptr);2704 2705  // See if this is a known constant.2706  TryResult KnownVal = tryEvaluateBool(LHS);2707 2708  // Now link the LHSBlock with RHSBlock.2709  if (B->getOpcode() == BO_LOr) {2710    addSuccessor(LHSBlock, TrueBlock, !KnownVal.isFalse());2711    addSuccessor(LHSBlock, RHSBlock, !KnownVal.isTrue());2712  } else {2713    assert(B->getOpcode() == BO_LAnd);2714    addSuccessor(LHSBlock, RHSBlock, !KnownVal.isFalse());2715    addSuccessor(LHSBlock, FalseBlock, !KnownVal.isTrue());2716  }2717 2718  return std::make_pair(EntryLHSBlock, ExitBlock);2719}2720 2721CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B,2722                                          AddStmtChoice asc) {2723   // && or ||2724  if (B->isLogicalOp())2725    return VisitLogicalOperator(B);2726 2727  if (B->getOpcode() == BO_Comma) { // ,2728    autoCreateBlock();2729    appendStmt(Block, B);2730    addStmt(B->getRHS());2731    return addStmt(B->getLHS());2732  }2733 2734  if (B->isAssignmentOp()) {2735    if (asc.alwaysAdd(*this, B)) {2736      autoCreateBlock();2737      appendStmt(Block, B);2738    }2739    Visit(B->getLHS());2740    return Visit(B->getRHS());2741  }2742 2743  if (asc.alwaysAdd(*this, B)) {2744    autoCreateBlock();2745    appendStmt(Block, B);2746  }2747 2748  if (B->isEqualityOp() || B->isRelationalOp())2749    tryEvaluateBool(B);2750 2751  CFGBlock *RBlock = Visit(B->getRHS());2752  CFGBlock *LBlock = Visit(B->getLHS());2753  // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr2754  // containing a DoStmt, and the LHS doesn't create a new block, then we should2755  // return RBlock.  Otherwise we'll incorrectly return NULL.2756  return (LBlock ? LBlock : RBlock);2757}2758 2759CFGBlock *CFGBuilder::VisitNoRecurse(Expr *E, AddStmtChoice asc) {2760  if (asc.alwaysAdd(*this, E)) {2761    autoCreateBlock();2762    appendStmt(Block, E);2763  }2764  return Block;2765}2766 2767CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) {2768  // "break" is a control-flow statement.  Thus we stop processing the current2769  // block.2770  if (badCFG)2771    return nullptr;2772 2773  // Now create a new block that ends with the break statement.2774  Block = createBlock(false);2775  Block->setTerminator(B);2776 2777  // If there is no target for the break, then we are looking at an incomplete2778  // AST.  This means that the CFG cannot be constructed.2779  if (BreakJumpTarget.block) {2780    addAutomaticObjHandling(ScopePos, BreakJumpTarget.scopePosition, B);2781    addSuccessor(Block, BreakJumpTarget.block);2782  } else2783    badCFG = true;2784 2785  return Block;2786}2787 2788static bool CanThrow(Expr *E, ASTContext &Ctx) {2789  QualType Ty = E->getType();2790  if (Ty->isFunctionPointerType() || Ty->isBlockPointerType())2791    Ty = Ty->getPointeeType();2792 2793  const FunctionType *FT = Ty->getAs<FunctionType>();2794  if (FT) {2795    if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT))2796      if (!isUnresolvedExceptionSpec(Proto->getExceptionSpecType()) &&2797          Proto->isNothrow())2798        return false;2799  }2800  return true;2801}2802 2803static bool isBuiltinAssumeWithSideEffects(const ASTContext &Ctx,2804                                           const CallExpr *CE) {2805  unsigned BuiltinID = CE->getBuiltinCallee();2806  if (BuiltinID != Builtin::BI__assume &&2807      BuiltinID != Builtin::BI__builtin_assume)2808    return false;2809 2810  return CE->getArg(0)->HasSideEffects(Ctx);2811}2812 2813CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) {2814  // Compute the callee type.2815  QualType calleeType = C->getCallee()->getType();2816  if (calleeType == Context->BoundMemberTy) {2817    QualType boundType = Expr::findBoundMemberType(C->getCallee());2818 2819    // We should only get a null bound type if processing a dependent2820    // CFG.  Recover by assuming nothing.2821    if (!boundType.isNull()) calleeType = boundType;2822  }2823 2824  // If this is a call to a no-return function, this stops the block here.2825  bool NoReturn = getFunctionExtInfo(*calleeType).getNoReturn();2826 2827  bool AddEHEdge = false;2828 2829  // Languages without exceptions are assumed to not throw.2830  if (Context->getLangOpts().Exceptions) {2831    if (BuildOpts.AddEHEdges)2832      AddEHEdge = true;2833  }2834 2835  // If this is a call to a builtin function, it might not actually evaluate2836  // its arguments. Don't add them to the CFG if this is the case.2837  bool OmitArguments = false;2838 2839  if (FunctionDecl *FD = C->getDirectCallee()) {2840    // TODO: Support construction contexts for variadic function arguments.2841    // These are a bit problematic and not very useful because passing2842    // C++ objects as C-style variadic arguments doesn't work in general2843    // (see [expr.call]).2844    if (!FD->isVariadic())2845      findConstructionContextsForArguments(C);2846 2847    if (FD->isNoReturn() || FD->isAnalyzerNoReturn() ||2848        C->isBuiltinAssumeFalse(*Context))2849      NoReturn = true;2850    if (FD->hasAttr<NoThrowAttr>())2851      AddEHEdge = false;2852    if (isBuiltinAssumeWithSideEffects(FD->getASTContext(), C) ||2853        FD->getBuiltinID() == Builtin::BI__builtin_object_size ||2854        FD->getBuiltinID() == Builtin::BI__builtin_dynamic_object_size)2855      OmitArguments = true;2856  }2857 2858  if (!CanThrow(C->getCallee(), *Context))2859    AddEHEdge = false;2860 2861  if (OmitArguments) {2862    assert(!NoReturn && "noreturn calls with unevaluated args not implemented");2863    assert(!AddEHEdge && "EH calls with unevaluated args not implemented");2864    autoCreateBlock();2865    appendStmt(Block, C);2866    return Visit(C->getCallee());2867  }2868 2869  if (!NoReturn && !AddEHEdge) {2870    autoCreateBlock();2871    appendCall(Block, C);2872 2873    return VisitChildren(C);2874  }2875 2876  if (Block) {2877    Succ = Block;2878    if (badCFG)2879      return nullptr;2880  }2881 2882  if (NoReturn)2883    Block = createNoReturnBlock();2884  else2885    Block = createBlock();2886 2887  appendCall(Block, C);2888 2889  if (AddEHEdge) {2890    // Add exceptional edges.2891    if (TryTerminatedBlock)2892      addSuccessor(Block, TryTerminatedBlock);2893    else2894      addSuccessor(Block, &cfg->getExit());2895  }2896 2897  return VisitChildren(C);2898}2899 2900CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C,2901                                      AddStmtChoice asc) {2902  CFGBlock *ConfluenceBlock = Block ? Block : createBlock();2903  appendStmt(ConfluenceBlock, C);2904  if (badCFG)2905    return nullptr;2906 2907  AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true);2908  Succ = ConfluenceBlock;2909  Block = nullptr;2910  CFGBlock *LHSBlock = Visit(C->getLHS(), alwaysAdd);2911  if (badCFG)2912    return nullptr;2913 2914  Succ = ConfluenceBlock;2915  Block = nullptr;2916  CFGBlock *RHSBlock = Visit(C->getRHS(), alwaysAdd);2917  if (badCFG)2918    return nullptr;2919 2920  Block = createBlock(false);2921  // See if this is a known constant.2922  const TryResult& KnownVal = tryEvaluateBool(C->getCond());2923  addSuccessor(Block, KnownVal.isFalse() ? nullptr : LHSBlock);2924  addSuccessor(Block, KnownVal.isTrue() ? nullptr : RHSBlock);2925  Block->setTerminator(C);2926  return addStmt(C->getCond());2927}2928 2929CFGBlock *CFGBuilder::VisitCompoundStmt(CompoundStmt *C,2930                                        bool ExternallyDestructed) {2931  LocalScope::const_iterator scopeBeginPos = ScopePos;2932  addLocalScopeForStmt(C);2933 2934  if (!C->body_empty() && !isa<ReturnStmt>(*C->body_rbegin())) {2935    // If the body ends with a ReturnStmt, the dtors will be added in2936    // VisitReturnStmt.2937    addAutomaticObjHandling(ScopePos, scopeBeginPos, C);2938  }2939 2940  CFGBlock *LastBlock = Block;2941 2942  for (Stmt *S : llvm::reverse(C->body())) {2943    // If we hit a segment of code just containing ';' (NullStmts), we can2944    // get a null block back.  In such cases, just use the LastBlock2945    CFGBlock *newBlock = Visit(S, AddStmtChoice::AlwaysAdd,2946                               ExternallyDestructed);2947 2948    if (newBlock)2949      LastBlock = newBlock;2950 2951    if (badCFG)2952      return nullptr;2953 2954    ExternallyDestructed = false;2955  }2956 2957  return LastBlock;2958}2959 2960CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C,2961                                               AddStmtChoice asc) {2962  const BinaryConditionalOperator *BCO = dyn_cast<BinaryConditionalOperator>(C);2963  const OpaqueValueExpr *opaqueValue = (BCO ? BCO->getOpaqueValue() : nullptr);2964 2965  // Create the confluence block that will "merge" the results of the ternary2966  // expression.2967  CFGBlock *ConfluenceBlock = Block ? Block : createBlock();2968  appendStmt(ConfluenceBlock, C);2969  if (badCFG)2970    return nullptr;2971 2972  AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true);2973 2974  // Create a block for the LHS expression if there is an LHS expression.  A2975  // GCC extension allows LHS to be NULL, causing the condition to be the2976  // value that is returned instead.2977  //  e.g: x ?: y is shorthand for: x ? x : y;2978  Succ = ConfluenceBlock;2979  Block = nullptr;2980  CFGBlock *LHSBlock = nullptr;2981  const Expr *trueExpr = C->getTrueExpr();2982  if (trueExpr != opaqueValue) {2983    LHSBlock = Visit(C->getTrueExpr(), alwaysAdd);2984    if (badCFG)2985      return nullptr;2986    Block = nullptr;2987  }2988  else2989    LHSBlock = ConfluenceBlock;2990 2991  // Create the block for the RHS expression.2992  Succ = ConfluenceBlock;2993  CFGBlock *RHSBlock = Visit(C->getFalseExpr(), alwaysAdd);2994  if (badCFG)2995    return nullptr;2996 2997  // If the condition is a logical '&&' or '||', build a more accurate CFG.2998  if (BinaryOperator *Cond =2999        dyn_cast<BinaryOperator>(C->getCond()->IgnoreParens()))3000    if (Cond->isLogicalOp())3001      return VisitLogicalOperator(Cond, C, LHSBlock, RHSBlock).first;3002 3003  // Create the block that will contain the condition.3004  Block = createBlock(false);3005 3006  // See if this is a known constant.3007  const TryResult& KnownVal = tryEvaluateBool(C->getCond());3008  addSuccessor(Block, LHSBlock, !KnownVal.isFalse());3009  addSuccessor(Block, RHSBlock, !KnownVal.isTrue());3010  Block->setTerminator(C);3011  Expr *condExpr = C->getCond();3012 3013  if (opaqueValue) {3014    // Run the condition expression if it's not trivially expressed in3015    // terms of the opaque value (or if there is no opaque value).3016    if (condExpr != opaqueValue)3017      addStmt(condExpr);3018 3019    // Before that, run the common subexpression if there was one.3020    // At least one of this or the above will be run.3021    return addStmt(BCO->getCommon());3022  }3023 3024  return addStmt(condExpr);3025}3026 3027CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) {3028  // Check if the Decl is for an __label__.  If so, elide it from the3029  // CFG entirely.3030  if (isa<LabelDecl>(*DS->decl_begin()))3031    return Block;3032 3033  // This case also handles static_asserts.3034  if (DS->isSingleDecl())3035    return VisitDeclSubExpr(DS);3036 3037  CFGBlock *B = nullptr;3038 3039  // Build an individual DeclStmt for each decl.3040  for (DeclStmt::reverse_decl_iterator I = DS->decl_rbegin(),3041                                       E = DS->decl_rend();3042       I != E; ++I) {3043 3044    // Allocate the DeclStmt using the BumpPtrAllocator.  It will get3045    // automatically freed with the CFG.3046    DeclGroupRef DG(*I);3047    Decl *D = *I;3048    DeclStmt *DSNew = new (Context) DeclStmt(DG, D->getLocation(), GetEndLoc(D));3049    cfg->addSyntheticDeclStmt(DSNew, DS);3050 3051    // Append the fake DeclStmt to block.3052    B = VisitDeclSubExpr(DSNew);3053  }3054 3055  return B;3056}3057 3058/// VisitDeclSubExpr - Utility method to add block-level expressions for3059/// DeclStmts and initializers in them.3060CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) {3061  assert(DS->isSingleDecl() && "Can handle single declarations only.");3062 3063  if (const auto *TND = dyn_cast<TypedefNameDecl>(DS->getSingleDecl())) {3064    // If we encounter a VLA, process its size expressions.3065    const Type *T = TND->getUnderlyingType().getTypePtr();3066    if (!T->isVariablyModifiedType())3067      return Block;3068 3069    autoCreateBlock();3070    appendStmt(Block, DS);3071 3072    CFGBlock *LastBlock = Block;3073    for (const VariableArrayType *VA = FindVA(T); VA != nullptr;3074         VA = FindVA(VA->getElementType().getTypePtr())) {3075      if (CFGBlock *NewBlock = addStmt(VA->getSizeExpr()))3076        LastBlock = NewBlock;3077    }3078    return LastBlock;3079  }3080 3081  VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl());3082 3083  if (!VD) {3084    // Of everything that can be declared in a DeclStmt, only VarDecls and the3085    // exceptions above impact runtime semantics.3086    return Block;3087  }3088 3089  bool HasTemporaries = false;3090 3091  // Guard static initializers under a branch.3092  CFGBlock *blockAfterStaticInit = nullptr;3093 3094  if (BuildOpts.AddStaticInitBranches && VD->isStaticLocal()) {3095    // For static variables, we need to create a branch to track3096    // whether or not they are initialized.3097    if (Block) {3098      Succ = Block;3099      Block = nullptr;3100      if (badCFG)3101        return nullptr;3102    }3103    blockAfterStaticInit = Succ;3104  }3105 3106  // Destructors of temporaries in initialization expression should be called3107  // after initialization finishes.3108  Expr *Init = VD->getInit();3109  if (Init) {3110    HasTemporaries = isa<ExprWithCleanups>(Init);3111 3112    if (BuildOpts.AddTemporaryDtors && HasTemporaries) {3113      // Generate destructors for temporaries in initialization expression.3114      TempDtorContext Context;3115      VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(),3116                             /*ExternallyDestructed=*/true, Context);3117    }3118  }3119 3120  // If we bind to a tuple-like type, we iterate over the HoldingVars, and3121  // create a DeclStmt for each of them.3122  if (const auto *DD = dyn_cast<DecompositionDecl>(VD)) {3123    for (auto *BD : llvm::reverse(DD->bindings())) {3124      if (auto *VD = BD->getHoldingVar()) {3125        DeclGroupRef DG(VD);3126        DeclStmt *DSNew =3127            new (Context) DeclStmt(DG, VD->getLocation(), GetEndLoc(VD));3128        cfg->addSyntheticDeclStmt(DSNew, DS);3129        Block = VisitDeclSubExpr(DSNew);3130      }3131    }3132  }3133 3134  autoCreateBlock();3135  appendStmt(Block, DS);3136 3137  // If the initializer is an ArrayInitLoopExpr, we want to extract the3138  // initializer, that's used for each element.3139  const auto *AILE = dyn_cast_or_null<ArrayInitLoopExpr>(Init);3140 3141  findConstructionContexts(3142      ConstructionContextLayer::create(cfg->getBumpVectorContext(), DS),3143      AILE ? AILE->getSubExpr() : Init);3144 3145  // Keep track of the last non-null block, as 'Block' can be nulled out3146  // if the initializer expression is something like a 'while' in a3147  // statement-expression.3148  CFGBlock *LastBlock = Block;3149 3150  if (Init) {3151    if (HasTemporaries) {3152      // For expression with temporaries go directly to subexpression to omit3153      // generating destructors for the second time.3154      ExprWithCleanups *EC = cast<ExprWithCleanups>(Init);3155      if (CFGBlock *newBlock = Visit(EC->getSubExpr()))3156        LastBlock = newBlock;3157    }3158    else {3159      if (CFGBlock *newBlock = Visit(Init))3160        LastBlock = newBlock;3161    }3162  }3163 3164  // If the type of VD is a VLA, then we must process its size expressions.3165  // FIXME: This does not find the VLA if it is embedded in other types,3166  // like here: `int (*p_vla)[x];`3167  for (const VariableArrayType* VA = FindVA(VD->getType().getTypePtr());3168       VA != nullptr; VA = FindVA(VA->getElementType().getTypePtr())) {3169    if (CFGBlock *newBlock = addStmt(VA->getSizeExpr()))3170      LastBlock = newBlock;3171  }3172 3173  maybeAddScopeBeginForVarDecl(Block, VD, DS);3174 3175  // Remove variable from local scope.3176  if (ScopePos && VD == *ScopePos)3177    ++ScopePos;3178 3179  CFGBlock *B = LastBlock;3180  if (blockAfterStaticInit) {3181    Succ = B;3182    Block = createBlock(false);3183    Block->setTerminator(DS);3184    addSuccessor(Block, blockAfterStaticInit);3185    addSuccessor(Block, B);3186    B = Block;3187  }3188 3189  return B;3190}3191 3192CFGBlock *CFGBuilder::VisitIfStmt(IfStmt *I) {3193  // We may see an if statement in the middle of a basic block, or it may be the3194  // first statement we are processing.  In either case, we create a new basic3195  // block.  First, we create the blocks for the then...else statements, and3196  // then we create the block containing the if statement.  If we were in the3197  // middle of a block, we stop processing that block.  That block is then the3198  // implicit successor for the "then" and "else" clauses.3199 3200  // Save local scope position because in case of condition variable ScopePos3201  // won't be restored when traversing AST.3202  SaveAndRestore save_scope_pos(ScopePos);3203 3204  // Create local scope for C++17 if init-stmt if one exists.3205  if (Stmt *Init = I->getInit())3206    addLocalScopeForStmt(Init);3207 3208  // Create local scope for possible condition variable.3209  // Store scope position. Add implicit destructor.3210  if (VarDecl *VD = I->getConditionVariable())3211    addLocalScopeForVarDecl(VD);3212 3213  addAutomaticObjHandling(ScopePos, save_scope_pos.get(), I);3214 3215  // The block we were processing is now finished.  Make it the successor3216  // block.3217  if (Block) {3218    Succ = Block;3219    if (badCFG)3220      return nullptr;3221  }3222 3223  // Process the false branch.3224  CFGBlock *ElseBlock = Succ;3225 3226  if (Stmt *Else = I->getElse()) {3227    SaveAndRestore sv(Succ);3228 3229    // NULL out Block so that the recursive call to Visit will3230    // create a new basic block.3231    Block = nullptr;3232 3233    // If branch is not a compound statement create implicit scope3234    // and add destructors.3235    if (!isa<CompoundStmt>(Else))3236      addLocalScopeAndDtors(Else);3237 3238    ElseBlock = addStmt(Else);3239 3240    if (!ElseBlock) // Can occur when the Else body has all NullStmts.3241      ElseBlock = sv.get();3242    else if (Block) {3243      if (badCFG)3244        return nullptr;3245    }3246  }3247 3248  // Process the true branch.3249  CFGBlock *ThenBlock;3250  {3251    Stmt *Then = I->getThen();3252    assert(Then);3253    SaveAndRestore sv(Succ);3254    Block = nullptr;3255 3256    // If branch is not a compound statement create implicit scope3257    // and add destructors.3258    if (!isa<CompoundStmt>(Then))3259      addLocalScopeAndDtors(Then);3260 3261    ThenBlock = addStmt(Then);3262 3263    if (!ThenBlock) {3264      // We can reach here if the "then" body has all NullStmts.3265      // Create an empty block so we can distinguish between true and false3266      // branches in path-sensitive analyses.3267      ThenBlock = createBlock(false);3268      addSuccessor(ThenBlock, sv.get());3269    } else if (Block) {3270      if (badCFG)3271        return nullptr;3272    }3273  }3274 3275  // Specially handle "if (expr1 || ...)" and "if (expr1 && ...)" by3276  // having these handle the actual control-flow jump.  Note that3277  // if we introduce a condition variable, e.g. "if (int x = exp1 || exp2)"3278  // we resort to the old control-flow behavior.  This special handling3279  // removes infeasible paths from the control-flow graph by having the3280  // control-flow transfer of '&&' or '||' go directly into the then/else3281  // blocks directly.3282  BinaryOperator *Cond =3283      (I->isConsteval() || I->getConditionVariable())3284          ? nullptr3285          : dyn_cast<BinaryOperator>(I->getCond()->IgnoreParens());3286  CFGBlock *LastBlock;3287  if (Cond && Cond->isLogicalOp())3288    LastBlock = VisitLogicalOperator(Cond, I, ThenBlock, ElseBlock).first;3289  else {3290    // Now create a new block containing the if statement.3291    Block = createBlock(false);3292 3293    // Set the terminator of the new block to the If statement.3294    Block->setTerminator(I);3295 3296    // See if this is a known constant.3297    TryResult KnownVal;3298    if (!I->isConsteval())3299      KnownVal = tryEvaluateBool(I->getCond());3300 3301    // Add the successors. If we know that specific branches are3302    // unreachable, inform addSuccessor() of that knowledge.3303    addSuccessor(Block, ThenBlock, /* IsReachable = */ !KnownVal.isFalse());3304    addSuccessor(Block, ElseBlock, /* IsReachable = */ !KnownVal.isTrue());3305 3306    if (I->isConsteval())3307      return Block;3308 3309    // Add the condition as the last statement in the new block.  This may3310    // create new blocks as the condition may contain control-flow.  Any newly3311    // created blocks will be pointed to be "Block".3312    LastBlock = addStmt(I->getCond());3313 3314    // If the IfStmt contains a condition variable, add it and its3315    // initializer to the CFG.3316    if (const DeclStmt* DS = I->getConditionVariableDeclStmt()) {3317      autoCreateBlock();3318      LastBlock = addStmt(const_cast<DeclStmt *>(DS));3319    }3320  }3321 3322  // Finally, if the IfStmt contains a C++17 init-stmt, add it to the CFG.3323  if (Stmt *Init = I->getInit()) {3324    autoCreateBlock();3325    LastBlock = addStmt(Init);3326  }3327 3328  return LastBlock;3329}3330 3331CFGBlock *CFGBuilder::VisitReturnStmt(Stmt *S) {3332  // If we were in the middle of a block we stop processing that block.3333  //3334  // NOTE: If a "return" or "co_return" appears in the middle of a block, this3335  //       means that the code afterwards is DEAD (unreachable).  We still keep3336  //       a basic block for that code; a simple "mark-and-sweep" from the entry3337  //       block will be able to report such dead blocks.3338  assert(isa<ReturnStmt>(S) || isa<CoreturnStmt>(S));3339 3340  // Create the new block.3341  Block = createBlock(false);3342 3343  addAutomaticObjHandling(ScopePos, LocalScope::const_iterator(), S);3344 3345  if (auto *R = dyn_cast<ReturnStmt>(S))3346    findConstructionContexts(3347        ConstructionContextLayer::create(cfg->getBumpVectorContext(), R),3348        R->getRetValue());3349 3350  // If the one of the destructors does not return, we already have the Exit3351  // block as a successor.3352  if (!Block->hasNoReturnElement())3353    addSuccessor(Block, &cfg->getExit());3354 3355  // Add the return statement to the block.3356  appendStmt(Block, S);3357 3358  // Visit children3359  if (ReturnStmt *RS = dyn_cast<ReturnStmt>(S)) {3360    if (Expr *O = RS->getRetValue())3361      return Visit(O, AddStmtChoice::AlwaysAdd, /*ExternallyDestructed=*/true);3362    return Block;3363  }3364 3365  CoreturnStmt *CRS = cast<CoreturnStmt>(S);3366  auto *B = Block;3367  if (CFGBlock *R = Visit(CRS->getPromiseCall()))3368    B = R;3369 3370  if (Expr *RV = CRS->getOperand())3371    if (RV->getType()->isVoidType() && !isa<InitListExpr>(RV))3372      // A non-initlist void expression.3373      if (CFGBlock *R = Visit(RV))3374        B = R;3375 3376  return B;3377}3378 3379CFGBlock *CFGBuilder::VisitCoroutineSuspendExpr(CoroutineSuspendExpr *E,3380                                                AddStmtChoice asc) {3381  // We're modelling the pre-coro-xform CFG. Thus just evalate the various3382  // active components of the co_await or co_yield. Note we do not model the3383  // edge from the builtin_suspend to the exit node.3384  if (asc.alwaysAdd(*this, E)) {3385    autoCreateBlock();3386    appendStmt(Block, E);3387  }3388  CFGBlock *B = Block;3389  if (auto *R = Visit(E->getResumeExpr()))3390    B = R;3391  if (auto *R = Visit(E->getSuspendExpr()))3392    B = R;3393  if (auto *R = Visit(E->getReadyExpr()))3394    B = R;3395  if (auto *R = Visit(E->getCommonExpr()))3396    B = R;3397  return B;3398}3399 3400CFGBlock *CFGBuilder::VisitSEHExceptStmt(SEHExceptStmt *ES) {3401  // SEHExceptStmt are treated like labels, so they are the first statement in a3402  // block.3403 3404  // Save local scope position because in case of exception variable ScopePos3405  // won't be restored when traversing AST.3406  SaveAndRestore save_scope_pos(ScopePos);3407 3408  addStmt(ES->getBlock());3409  CFGBlock *SEHExceptBlock = Block;3410  if (!SEHExceptBlock)3411    SEHExceptBlock = createBlock();3412 3413  appendStmt(SEHExceptBlock, ES);3414 3415  // Also add the SEHExceptBlock as a label, like with regular labels.3416  SEHExceptBlock->setLabel(ES);3417 3418  // Bail out if the CFG is bad.3419  if (badCFG)3420    return nullptr;3421 3422  // We set Block to NULL to allow lazy creation of a new block (if necessary).3423  Block = nullptr;3424 3425  return SEHExceptBlock;3426}3427 3428CFGBlock *CFGBuilder::VisitSEHFinallyStmt(SEHFinallyStmt *FS) {3429  return VisitCompoundStmt(FS->getBlock(), /*ExternallyDestructed=*/false);3430}3431 3432CFGBlock *CFGBuilder::VisitSEHLeaveStmt(SEHLeaveStmt *LS) {3433  // "__leave" is a control-flow statement.  Thus we stop processing the current3434  // block.3435  if (badCFG)3436    return nullptr;3437 3438  // Now create a new block that ends with the __leave statement.3439  Block = createBlock(false);3440  Block->setTerminator(LS);3441 3442  // If there is no target for the __leave, then we are looking at an incomplete3443  // AST.  This means that the CFG cannot be constructed.3444  if (SEHLeaveJumpTarget.block) {3445    addAutomaticObjHandling(ScopePos, SEHLeaveJumpTarget.scopePosition, LS);3446    addSuccessor(Block, SEHLeaveJumpTarget.block);3447  } else3448    badCFG = true;3449 3450  return Block;3451}3452 3453CFGBlock *CFGBuilder::VisitSEHTryStmt(SEHTryStmt *Terminator) {3454  // "__try"/"__except"/"__finally" is a control-flow statement.  Thus we stop3455  // processing the current block.3456  CFGBlock *SEHTrySuccessor = nullptr;3457 3458  if (Block) {3459    if (badCFG)3460      return nullptr;3461    SEHTrySuccessor = Block;3462  } else SEHTrySuccessor = Succ;3463 3464  // FIXME: Implement __finally support.3465  if (Terminator->getFinallyHandler())3466    return NYS();3467 3468  CFGBlock *PrevSEHTryTerminatedBlock = TryTerminatedBlock;3469 3470  // Create a new block that will contain the __try statement.3471  CFGBlock *NewTryTerminatedBlock = createBlock(false);3472 3473  // Add the terminator in the __try block.3474  NewTryTerminatedBlock->setTerminator(Terminator);3475 3476  if (SEHExceptStmt *Except = Terminator->getExceptHandler()) {3477    // The code after the try is the implicit successor if there's an __except.3478    Succ = SEHTrySuccessor;3479    Block = nullptr;3480    CFGBlock *ExceptBlock = VisitSEHExceptStmt(Except);3481    if (!ExceptBlock)3482      return nullptr;3483    // Add this block to the list of successors for the block with the try3484    // statement.3485    addSuccessor(NewTryTerminatedBlock, ExceptBlock);3486  }3487  if (PrevSEHTryTerminatedBlock)3488    addSuccessor(NewTryTerminatedBlock, PrevSEHTryTerminatedBlock);3489  else3490    addSuccessor(NewTryTerminatedBlock, &cfg->getExit());3491 3492  // The code after the try is the implicit successor.3493  Succ = SEHTrySuccessor;3494 3495  // Save the current "__try" context.3496  SaveAndRestore SaveTry(TryTerminatedBlock, NewTryTerminatedBlock);3497  cfg->addTryDispatchBlock(TryTerminatedBlock);3498 3499  // Save the current value for the __leave target.3500  // All __leaves should go to the code following the __try3501  // (FIXME: or if the __try has a __finally, to the __finally.)3502  SaveAndRestore save_break(SEHLeaveJumpTarget);3503  SEHLeaveJumpTarget = JumpTarget(SEHTrySuccessor, ScopePos);3504 3505  assert(Terminator->getTryBlock() && "__try must contain a non-NULL body");3506  Block = nullptr;3507  return addStmt(Terminator->getTryBlock());3508}3509 3510CFGBlock *CFGBuilder::VisitLabelStmt(LabelStmt *L) {3511  // Get the block of the labeled statement.  Add it to our map.3512  addStmt(L->getSubStmt());3513  CFGBlock *LabelBlock = Block;3514 3515  if (!LabelBlock)              // This can happen when the body is empty, i.e.3516    LabelBlock = createBlock(); // scopes that only contains NullStmts.3517 3518  assert(!LabelMap.contains(L->getDecl()) && "label already in map");3519  LabelMap[L->getDecl()] = JumpTarget(LabelBlock, ScopePos);3520 3521  // Labels partition blocks, so this is the end of the basic block we were3522  // processing (L is the block's label).  Because this is label (and we have3523  // already processed the substatement) there is no extra control-flow to worry3524  // about.3525  LabelBlock->setLabel(L);3526  if (badCFG)3527    return nullptr;3528 3529  // We set Block to NULL to allow lazy creation of a new block (if necessary).3530  Block = nullptr;3531 3532  // This block is now the implicit successor of other blocks.3533  Succ = LabelBlock;3534 3535  return LabelBlock;3536}3537 3538CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) {3539  CFGBlock *LastBlock = VisitNoRecurse(E, asc);3540  for (const BlockDecl::Capture &CI : E->getBlockDecl()->captures()) {3541    if (Expr *CopyExpr = CI.getCopyExpr()) {3542      CFGBlock *Tmp = Visit(CopyExpr);3543      if (Tmp)3544        LastBlock = Tmp;3545    }3546  }3547  return LastBlock;3548}3549 3550CFGBlock *CFGBuilder::VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc) {3551  CFGBlock *LastBlock = VisitNoRecurse(E, asc);3552 3553  unsigned Idx = 0;3554  for (LambdaExpr::capture_init_iterator it = E->capture_init_begin(),3555                                         et = E->capture_init_end();3556       it != et; ++it, ++Idx) {3557    if (Expr *Init = *it) {3558      // If the initializer is an ArrayInitLoopExpr, we want to extract the3559      // initializer, that's used for each element.3560      auto *AILEInit = extractElementInitializerFromNestedAILE(3561          dyn_cast<ArrayInitLoopExpr>(Init));3562 3563      findConstructionContexts(ConstructionContextLayer::create(3564                                   cfg->getBumpVectorContext(), {E, Idx}),3565                               AILEInit ? AILEInit : Init);3566 3567      CFGBlock *Tmp = Visit(Init);3568      if (Tmp)3569        LastBlock = Tmp;3570    }3571  }3572  return LastBlock;3573}3574 3575CFGBlock *CFGBuilder::VisitGotoStmt(GotoStmt *G) {3576  // Goto is a control-flow statement.  Thus we stop processing the current3577  // block and create a new one.3578 3579  Block = createBlock(false);3580  Block->setTerminator(G);3581 3582  // If we already know the mapping to the label block add the successor now.3583  LabelMapTy::iterator I = LabelMap.find(G->getLabel());3584 3585  if (I == LabelMap.end())3586    // We will need to backpatch this block later.3587    BackpatchBlocks.push_back(JumpSource(Block, ScopePos));3588  else {3589    JumpTarget JT = I->second;3590    addSuccessor(Block, JT.block);3591    addScopeChangesHandling(ScopePos, JT.scopePosition, G);3592  }3593 3594  return Block;3595}3596 3597CFGBlock *CFGBuilder::VisitGCCAsmStmt(GCCAsmStmt *G, AddStmtChoice asc) {3598  // Goto is a control-flow statement.  Thus we stop processing the current3599  // block and create a new one.3600 3601  if (!G->isAsmGoto())3602    return VisitStmt(G, asc);3603 3604  if (Block) {3605    Succ = Block;3606    if (badCFG)3607      return nullptr;3608  }3609  Block = createBlock();3610  Block->setTerminator(G);3611  // We will backpatch this block later for all the labels.3612  BackpatchBlocks.push_back(JumpSource(Block, ScopePos));3613  // Save "Succ" in BackpatchBlocks. In the backpatch processing, "Succ" is3614  // used to avoid adding "Succ" again.3615  BackpatchBlocks.push_back(JumpSource(Succ, ScopePos));3616  return VisitChildren(G);3617}3618 3619CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) {3620  CFGBlock *LoopSuccessor = nullptr;3621 3622  // Save local scope position because in case of condition variable ScopePos3623  // won't be restored when traversing AST.3624  SaveAndRestore save_scope_pos(ScopePos);3625 3626  // Create local scope for init statement and possible condition variable.3627  // Add destructor for init statement and condition variable.3628  // Store scope position for continue statement.3629  if (Stmt *Init = F->getInit())3630    addLocalScopeForStmt(Init);3631  LocalScope::const_iterator LoopBeginScopePos = ScopePos;3632 3633  if (VarDecl *VD = F->getConditionVariable())3634    addLocalScopeForVarDecl(VD);3635  LocalScope::const_iterator ContinueScopePos = ScopePos;3636 3637  addAutomaticObjHandling(ScopePos, save_scope_pos.get(), F);3638 3639  addLoopExit(F);3640 3641  // "for" is a control-flow statement.  Thus we stop processing the current3642  // block.3643  if (Block) {3644    if (badCFG)3645      return nullptr;3646    LoopSuccessor = Block;3647  } else3648    LoopSuccessor = Succ;3649 3650  // Save the current value for the break targets.3651  // All breaks should go to the code following the loop.3652  SaveAndRestore save_break(BreakJumpTarget);3653  BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);3654 3655  CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr;3656 3657  // Now create the loop body.3658  {3659    assert(F->getBody());3660 3661    // Save the current values for Block, Succ, continue and break targets.3662    SaveAndRestore save_Block(Block), save_Succ(Succ);3663    SaveAndRestore save_continue(ContinueJumpTarget);3664 3665    // Create an empty block to represent the transition block for looping back3666    // to the head of the loop.  If we have increment code, it will3667    // go in this block as well.3668    Block = Succ = TransitionBlock = createBlock(false);3669    TransitionBlock->setLoopTarget(F);3670 3671 3672    // Loop iteration (after increment) should end with destructor of Condition3673    // variable (if any).3674    addAutomaticObjHandling(ScopePos, LoopBeginScopePos, F);3675 3676    if (Stmt *I = F->getInc()) {3677      // Generate increment code in its own basic block.  This is the target of3678      // continue statements.3679      Succ = addStmt(I);3680    }3681 3682    // Finish up the increment (or empty) block if it hasn't been already.3683    if (Block) {3684      assert(Block == Succ);3685      if (badCFG)3686        return nullptr;3687      Block = nullptr;3688    }3689 3690   // The starting block for the loop increment is the block that should3691   // represent the 'loop target' for looping back to the start of the loop.3692   ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);3693   ContinueJumpTarget.block->setLoopTarget(F);3694 3695 3696    // If body is not a compound statement create implicit scope3697    // and add destructors.3698    if (!isa<CompoundStmt>(F->getBody()))3699      addLocalScopeAndDtors(F->getBody());3700 3701    // Now populate the body block, and in the process create new blocks as we3702    // walk the body of the loop.3703    BodyBlock = addStmt(F->getBody());3704 3705    if (!BodyBlock) {3706      // In the case of "for (...;...;...);" we can have a null BodyBlock.3707      // Use the continue jump target as the proxy for the body.3708      BodyBlock = ContinueJumpTarget.block;3709    }3710    else if (badCFG)3711      return nullptr;3712  }3713 3714  // Because of short-circuit evaluation, the condition of the loop can span3715  // multiple basic blocks.  Thus we need the "Entry" and "Exit" blocks that3716  // evaluate the condition.3717  CFGBlock *EntryConditionBlock = nullptr, *ExitConditionBlock = nullptr;3718 3719  do {3720    Expr *C = F->getCond();3721    SaveAndRestore save_scope_pos(ScopePos);3722 3723    // Specially handle logical operators, which have a slightly3724    // more optimal CFG representation.3725    if (BinaryOperator *Cond =3726            dyn_cast_or_null<BinaryOperator>(C ? C->IgnoreParens() : nullptr))3727      if (Cond->isLogicalOp()) {3728        std::tie(EntryConditionBlock, ExitConditionBlock) =3729          VisitLogicalOperator(Cond, F, BodyBlock, LoopSuccessor);3730        break;3731      }3732 3733    // The default case when not handling logical operators.3734    EntryConditionBlock = ExitConditionBlock = createBlock(false);3735    ExitConditionBlock->setTerminator(F);3736 3737    // See if this is a known constant.3738    TryResult KnownVal(true);3739 3740    if (C) {3741      // Now add the actual condition to the condition block.3742      // Because the condition itself may contain control-flow, new blocks may3743      // be created.  Thus we update "Succ" after adding the condition.3744      Block = ExitConditionBlock;3745      EntryConditionBlock = addStmt(C);3746 3747      // If this block contains a condition variable, add both the condition3748      // variable and initializer to the CFG.3749      if (VarDecl *VD = F->getConditionVariable()) {3750        if (Expr *Init = VD->getInit()) {3751          autoCreateBlock();3752          const DeclStmt *DS = F->getConditionVariableDeclStmt();3753          assert(DS->isSingleDecl());3754          findConstructionContexts(3755              ConstructionContextLayer::create(cfg->getBumpVectorContext(), DS),3756              Init);3757          appendStmt(Block, DS);3758          EntryConditionBlock = addStmt(Init);3759          assert(Block == EntryConditionBlock);3760          maybeAddScopeBeginForVarDecl(EntryConditionBlock, VD, C);3761        }3762      }3763 3764      if (Block && badCFG)3765        return nullptr;3766 3767      KnownVal = tryEvaluateBool(C);3768    }3769 3770    // Add the loop body entry as a successor to the condition.3771    addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? nullptr : BodyBlock);3772    // Link up the condition block with the code that follows the loop.  (the3773    // false branch).3774    addSuccessor(ExitConditionBlock,3775                 KnownVal.isTrue() ? nullptr : LoopSuccessor);3776  } while (false);3777 3778  // Link up the loop-back block to the entry condition block.3779  addSuccessor(TransitionBlock, EntryConditionBlock);3780 3781  // The condition block is the implicit successor for any code above the loop.3782  Succ = EntryConditionBlock;3783 3784  // If the loop contains initialization, create a new block for those3785  // statements.  This block can also contain statements that precede the loop.3786  if (Stmt *I = F->getInit()) {3787    SaveAndRestore save_scope_pos(ScopePos);3788    ScopePos = LoopBeginScopePos;3789    Block = createBlock();3790    return addStmt(I);3791  }3792 3793  // There is no loop initialization.  We are thus basically a while loop.3794  // NULL out Block to force lazy block construction.3795  Block = nullptr;3796  Succ = EntryConditionBlock;3797  return EntryConditionBlock;3798}3799 3800CFGBlock *3801CFGBuilder::VisitMaterializeTemporaryExpr(MaterializeTemporaryExpr *MTE,3802                                          AddStmtChoice asc) {3803  findConstructionContexts(3804      ConstructionContextLayer::create(cfg->getBumpVectorContext(), MTE),3805      MTE->getSubExpr());3806 3807  return VisitStmt(MTE, asc);3808}3809 3810CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) {3811  if (asc.alwaysAdd(*this, M)) {3812    autoCreateBlock();3813    appendStmt(Block, M);3814  }3815  return Visit(M->getBase());3816}3817 3818CFGBlock *CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt *S) {3819  // Objective-C fast enumeration 'for' statements:3820  //  http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC3821  //3822  //  for ( Type newVariable in collection_expression ) { statements }3823  //3824  //  becomes:3825  //3826  //   prologue:3827  //     1. collection_expression3828  //     T. jump to loop_entry3829  //   loop_entry:3830  //     1. side-effects of element expression3831  //     1. ObjCForCollectionStmt [performs binding to newVariable]3832  //     T. ObjCForCollectionStmt  TB, FB  [jumps to TB if newVariable != nil]3833  //   TB:3834  //     statements3835  //     T. jump to loop_entry3836  //   FB:3837  //     what comes after3838  //3839  //  and3840  //3841  //  Type existingItem;3842  //  for ( existingItem in expression ) { statements }3843  //3844  //  becomes:3845  //3846  //   the same with newVariable replaced with existingItem; the binding works3847  //   the same except that for one ObjCForCollectionStmt::getElement() returns3848  //   a DeclStmt and the other returns a DeclRefExpr.3849 3850  CFGBlock *LoopSuccessor = nullptr;3851 3852  if (Block) {3853    if (badCFG)3854      return nullptr;3855    LoopSuccessor = Block;3856    Block = nullptr;3857  } else3858    LoopSuccessor = Succ;3859 3860  // Build the condition blocks.3861  CFGBlock *ExitConditionBlock = createBlock(false);3862 3863  // Set the terminator for the "exit" condition block.3864  ExitConditionBlock->setTerminator(S);3865 3866  // The last statement in the block should be the ObjCForCollectionStmt, which3867  // performs the actual binding to 'element' and determines if there are any3868  // more items in the collection.3869  appendStmt(ExitConditionBlock, S);3870  Block = ExitConditionBlock;3871 3872  // Walk the 'element' expression to see if there are any side-effects.  We3873  // generate new blocks as necessary.  We DON'T add the statement by default to3874  // the CFG unless it contains control-flow.3875  CFGBlock *EntryConditionBlock = Visit(S->getElement(),3876                                        AddStmtChoice::NotAlwaysAdd);3877  if (Block) {3878    if (badCFG)3879      return nullptr;3880    Block = nullptr;3881  }3882 3883  // The condition block is the implicit successor for the loop body as well as3884  // any code above the loop.3885  Succ = EntryConditionBlock;3886 3887  // Now create the true branch.3888  {3889    // Save the current values for Succ, continue and break targets.3890    SaveAndRestore save_Block(Block), save_Succ(Succ);3891    SaveAndRestore save_continue(ContinueJumpTarget),3892        save_break(BreakJumpTarget);3893 3894    // Add an intermediate block between the BodyBlock and the3895    // EntryConditionBlock to represent the "loop back" transition, for looping3896    // back to the head of the loop.3897    CFGBlock *LoopBackBlock = nullptr;3898    Succ = LoopBackBlock = createBlock();3899    LoopBackBlock->setLoopTarget(S);3900 3901    BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);3902    ContinueJumpTarget = JumpTarget(Succ, ScopePos);3903 3904    CFGBlock *BodyBlock = addStmt(S->getBody());3905 3906    if (!BodyBlock)3907      BodyBlock = ContinueJumpTarget.block; // can happen for "for (X in Y) ;"3908    else if (Block) {3909      if (badCFG)3910        return nullptr;3911    }3912 3913    // This new body block is a successor to our "exit" condition block.3914    addSuccessor(ExitConditionBlock, BodyBlock);3915  }3916 3917  // Link up the condition block with the code that follows the loop.3918  // (the false branch).3919  addSuccessor(ExitConditionBlock, LoopSuccessor);3920 3921  // Now create a prologue block to contain the collection expression.3922  Block = createBlock();3923  return addStmt(S->getCollection());3924}3925 3926CFGBlock *CFGBuilder::VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S) {3927  // Inline the body.3928  return addStmt(S->getSubStmt());3929  // TODO: consider adding cleanups for the end of @autoreleasepool scope.3930}3931 3932CFGBlock *CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S) {3933  // FIXME: Add locking 'primitives' to CFG for @synchronized.3934 3935  // Inline the body.3936  CFGBlock *SyncBlock = addStmt(S->getSynchBody());3937 3938  // The sync body starts its own basic block.  This makes it a little easier3939  // for diagnostic clients.3940  if (SyncBlock) {3941    if (badCFG)3942      return nullptr;3943 3944    Block = nullptr;3945    Succ = SyncBlock;3946  }3947 3948  // Add the @synchronized to the CFG.3949  autoCreateBlock();3950  appendStmt(Block, S);3951 3952  // Inline the sync expression.3953  return addStmt(S->getSynchExpr());3954}3955 3956CFGBlock *CFGBuilder::VisitPseudoObjectExpr(PseudoObjectExpr *E) {3957  autoCreateBlock();3958 3959  // Add the PseudoObject as the last thing.3960  appendStmt(Block, E);3961 3962  CFGBlock *lastBlock = Block;3963 3964  // Before that, evaluate all of the semantics in order.  In3965  // CFG-land, that means appending them in reverse order.3966  for (unsigned i = E->getNumSemanticExprs(); i != 0; ) {3967    Expr *Semantic = E->getSemanticExpr(--i);3968 3969    // If the semantic is an opaque value, we're being asked to bind3970    // it to its source expression.3971    if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic))3972      Semantic = OVE->getSourceExpr();3973 3974    if (CFGBlock *B = Visit(Semantic))3975      lastBlock = B;3976  }3977 3978  return lastBlock;3979}3980 3981CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) {3982  CFGBlock *LoopSuccessor = nullptr;3983 3984  // Save local scope position because in case of condition variable ScopePos3985  // won't be restored when traversing AST.3986  SaveAndRestore save_scope_pos(ScopePos);3987 3988  // Create local scope for possible condition variable.3989  // Store scope position for continue statement.3990  LocalScope::const_iterator LoopBeginScopePos = ScopePos;3991  if (VarDecl *VD = W->getConditionVariable()) {3992    addLocalScopeForVarDecl(VD);3993    addAutomaticObjHandling(ScopePos, LoopBeginScopePos, W);3994  }3995  addLoopExit(W);3996 3997  // "while" is a control-flow statement.  Thus we stop processing the current3998  // block.3999  if (Block) {4000    if (badCFG)4001      return nullptr;4002    LoopSuccessor = Block;4003    Block = nullptr;4004  } else {4005    LoopSuccessor = Succ;4006  }4007 4008  CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr;4009 4010  // Process the loop body.4011  {4012    assert(W->getBody());4013 4014    // Save the current values for Block, Succ, continue and break targets.4015    SaveAndRestore save_Block(Block), save_Succ(Succ);4016    SaveAndRestore save_continue(ContinueJumpTarget),4017        save_break(BreakJumpTarget);4018 4019    // Create an empty block to represent the transition block for looping back4020    // to the head of the loop.4021    Succ = TransitionBlock = createBlock(false);4022    TransitionBlock->setLoopTarget(W);4023    ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos);4024 4025    // All breaks should go to the code following the loop.4026    BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);4027 4028    // Loop body should end with destructor of Condition variable (if any).4029    addAutomaticObjHandling(ScopePos, LoopBeginScopePos, W);4030 4031    // If body is not a compound statement create implicit scope4032    // and add destructors.4033    if (!isa<CompoundStmt>(W->getBody()))4034      addLocalScopeAndDtors(W->getBody());4035 4036    // Create the body.  The returned block is the entry to the loop body.4037    BodyBlock = addStmt(W->getBody());4038 4039    if (!BodyBlock)4040      BodyBlock = ContinueJumpTarget.block; // can happen for "while(...) ;"4041    else if (Block && badCFG)4042      return nullptr;4043  }4044 4045  // Because of short-circuit evaluation, the condition of the loop can span4046  // multiple basic blocks.  Thus we need the "Entry" and "Exit" blocks that4047  // evaluate the condition.4048  CFGBlock *EntryConditionBlock = nullptr, *ExitConditionBlock = nullptr;4049 4050  do {4051    Expr *C = W->getCond();4052 4053    // Specially handle logical operators, which have a slightly4054    // more optimal CFG representation.4055    if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(C->IgnoreParens()))4056      if (Cond->isLogicalOp()) {4057        std::tie(EntryConditionBlock, ExitConditionBlock) =4058            VisitLogicalOperator(Cond, W, BodyBlock, LoopSuccessor);4059        break;4060      }4061 4062    // The default case when not handling logical operators.4063    ExitConditionBlock = createBlock(false);4064    ExitConditionBlock->setTerminator(W);4065 4066    // Now add the actual condition to the condition block.4067    // Because the condition itself may contain control-flow, new blocks may4068    // be created.  Thus we update "Succ" after adding the condition.4069    Block = ExitConditionBlock;4070    Block = EntryConditionBlock = addStmt(C);4071 4072    // If this block contains a condition variable, add both the condition4073    // variable and initializer to the CFG.4074    if (VarDecl *VD = W->getConditionVariable()) {4075      if (Expr *Init = VD->getInit()) {4076        autoCreateBlock();4077        const DeclStmt *DS = W->getConditionVariableDeclStmt();4078        assert(DS->isSingleDecl());4079        findConstructionContexts(4080            ConstructionContextLayer::create(cfg->getBumpVectorContext(),4081                                             const_cast<DeclStmt *>(DS)),4082            Init);4083        appendStmt(Block, DS);4084        EntryConditionBlock = addStmt(Init);4085        assert(Block == EntryConditionBlock);4086        maybeAddScopeBeginForVarDecl(EntryConditionBlock, VD, C);4087      }4088    }4089 4090    if (Block && badCFG)4091      return nullptr;4092 4093    // See if this is a known constant.4094    const TryResult& KnownVal = tryEvaluateBool(C);4095 4096    // Add the loop body entry as a successor to the condition.4097    addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? nullptr : BodyBlock);4098    // Link up the condition block with the code that follows the loop.  (the4099    // false branch).4100    addSuccessor(ExitConditionBlock,4101                 KnownVal.isTrue() ? nullptr : LoopSuccessor);4102  } while(false);4103 4104  // Link up the loop-back block to the entry condition block.4105  addSuccessor(TransitionBlock, EntryConditionBlock);4106 4107  // There can be no more statements in the condition block since we loop back4108  // to this block.  NULL out Block to force lazy creation of another block.4109  Block = nullptr;4110 4111  // Return the condition block, which is the dominating block for the loop.4112  Succ = EntryConditionBlock;4113  return EntryConditionBlock;4114}4115 4116CFGBlock *CFGBuilder::VisitArrayInitLoopExpr(ArrayInitLoopExpr *A,4117                                             AddStmtChoice asc) {4118  if (asc.alwaysAdd(*this, A)) {4119    autoCreateBlock();4120    appendStmt(Block, A);4121  }4122 4123  CFGBlock *B = Block;4124 4125  if (CFGBlock *R = Visit(A->getSubExpr()))4126    B = R;4127 4128  auto *OVE = dyn_cast<OpaqueValueExpr>(A->getCommonExpr());4129  assert(OVE && "ArrayInitLoopExpr->getCommonExpr() should be wrapped in an "4130                "OpaqueValueExpr!");4131  if (CFGBlock *R = Visit(OVE->getSourceExpr()))4132    B = R;4133 4134  return B;4135}4136 4137CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt *CS) {4138  // ObjCAtCatchStmt are treated like labels, so they are the first statement4139  // in a block.4140 4141  // Save local scope position because in case of exception variable ScopePos4142  // won't be restored when traversing AST.4143  SaveAndRestore save_scope_pos(ScopePos);4144 4145  if (CS->getCatchBody())4146    addStmt(CS->getCatchBody());4147 4148  CFGBlock *CatchBlock = Block;4149  if (!CatchBlock)4150    CatchBlock = createBlock();4151 4152  appendStmt(CatchBlock, CS);4153 4154  // Also add the ObjCAtCatchStmt as a label, like with regular labels.4155  CatchBlock->setLabel(CS);4156 4157  // Bail out if the CFG is bad.4158  if (badCFG)4159    return nullptr;4160 4161  // We set Block to NULL to allow lazy creation of a new block (if necessary).4162  Block = nullptr;4163 4164  return CatchBlock;4165}4166 4167CFGBlock *CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt *S) {4168  // If we were in the middle of a block we stop processing that block.4169  if (badCFG)4170    return nullptr;4171 4172  // Create the new block.4173  Block = createBlock(false);4174 4175  if (TryTerminatedBlock)4176    // The current try statement is the only successor.4177    addSuccessor(Block, TryTerminatedBlock);4178  else4179    // otherwise the Exit block is the only successor.4180    addSuccessor(Block, &cfg->getExit());4181 4182  // Add the statement to the block.  This may create new blocks if S contains4183  // control-flow (short-circuit operations).4184  return VisitStmt(S, AddStmtChoice::AlwaysAdd);4185}4186 4187CFGBlock *CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt *Terminator) {4188  // "@try"/"@catch" is a control-flow statement.  Thus we stop processing the4189  // current block.4190  CFGBlock *TrySuccessor = nullptr;4191 4192  if (Block) {4193    if (badCFG)4194      return nullptr;4195    TrySuccessor = Block;4196  } else4197    TrySuccessor = Succ;4198 4199  // FIXME: Implement @finally support.4200  if (Terminator->getFinallyStmt())4201    return NYS();4202 4203  CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock;4204 4205  // Create a new block that will contain the try statement.4206  CFGBlock *NewTryTerminatedBlock = createBlock(false);4207  // Add the terminator in the try block.4208  NewTryTerminatedBlock->setTerminator(Terminator);4209 4210  bool HasCatchAll = false;4211  for (ObjCAtCatchStmt *CS : Terminator->catch_stmts()) {4212    // The code after the try is the implicit successor.4213    Succ = TrySuccessor;4214    if (CS->hasEllipsis()) {4215      HasCatchAll = true;4216    }4217    Block = nullptr;4218    CFGBlock *CatchBlock = VisitObjCAtCatchStmt(CS);4219    if (!CatchBlock)4220      return nullptr;4221    // Add this block to the list of successors for the block with the try4222    // statement.4223    addSuccessor(NewTryTerminatedBlock, CatchBlock);4224  }4225 4226  // FIXME: This needs updating when @finally support is added.4227  if (!HasCatchAll) {4228    if (PrevTryTerminatedBlock)4229      addSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock);4230    else4231      addSuccessor(NewTryTerminatedBlock, &cfg->getExit());4232  }4233 4234  // The code after the try is the implicit successor.4235  Succ = TrySuccessor;4236 4237  // Save the current "try" context.4238  SaveAndRestore SaveTry(TryTerminatedBlock, NewTryTerminatedBlock);4239  cfg->addTryDispatchBlock(TryTerminatedBlock);4240 4241  assert(Terminator->getTryBody() && "try must contain a non-NULL body");4242  Block = nullptr;4243  return addStmt(Terminator->getTryBody());4244}4245 4246CFGBlock *CFGBuilder::VisitObjCMessageExpr(ObjCMessageExpr *ME,4247                                           AddStmtChoice asc) {4248  findConstructionContextsForArguments(ME);4249 4250  autoCreateBlock();4251  appendObjCMessage(Block, ME);4252 4253  return VisitChildren(ME);4254}4255 4256CFGBlock *CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr *T) {4257  // If we were in the middle of a block we stop processing that block.4258  if (badCFG)4259    return nullptr;4260 4261  // Create the new block.4262  Block = createBlock(false);4263 4264  if (TryTerminatedBlock)4265    // The current try statement is the only successor.4266    addSuccessor(Block, TryTerminatedBlock);4267  else4268    // otherwise the Exit block is the only successor.4269    addSuccessor(Block, &cfg->getExit());4270 4271  // Add the statement to the block.  This may create new blocks if S contains4272  // control-flow (short-circuit operations).4273  return VisitStmt(T, AddStmtChoice::AlwaysAdd);4274}4275 4276CFGBlock *CFGBuilder::VisitCXXTypeidExpr(CXXTypeidExpr *S, AddStmtChoice asc) {4277  if (asc.alwaysAdd(*this, S)) {4278    autoCreateBlock();4279    appendStmt(Block, S);4280  }4281 4282  // C++ [expr.typeid]p3:4283  //   When typeid is applied to an expression other than an glvalue of a4284  //   polymorphic class type [...] [the] expression is an unevaluated4285  //   operand. [...]4286  // We add only potentially evaluated statements to the block to avoid4287  // CFG generation for unevaluated operands.4288  if (!S->isTypeDependent() && S->isPotentiallyEvaluated())4289    return VisitChildren(S);4290 4291  // Return block without CFG for unevaluated operands.4292  return Block;4293}4294 4295CFGBlock *CFGBuilder::VisitDoStmt(DoStmt *D) {4296  CFGBlock *LoopSuccessor = nullptr;4297 4298  addLoopExit(D);4299 4300  // "do...while" is a control-flow statement.  Thus we stop processing the4301  // current block.4302  if (Block) {4303    if (badCFG)4304      return nullptr;4305    LoopSuccessor = Block;4306  } else4307    LoopSuccessor = Succ;4308 4309  // Because of short-circuit evaluation, the condition of the loop can span4310  // multiple basic blocks.  Thus we need the "Entry" and "Exit" blocks that4311  // evaluate the condition.4312  CFGBlock *ExitConditionBlock = createBlock(false);4313  CFGBlock *EntryConditionBlock = ExitConditionBlock;4314 4315  // Set the terminator for the "exit" condition block.4316  ExitConditionBlock->setTerminator(D);4317 4318  // Now add the actual condition to the condition block.  Because the condition4319  // itself may contain control-flow, new blocks may be created.4320  if (Stmt *C = D->getCond()) {4321    Block = ExitConditionBlock;4322    EntryConditionBlock = addStmt(C);4323    if (Block) {4324      if (badCFG)4325        return nullptr;4326    }4327  }4328 4329  // The condition block is the implicit successor for the loop body.4330  Succ = EntryConditionBlock;4331 4332  // See if this is a known constant.4333  const TryResult &KnownVal = tryEvaluateBool(D->getCond());4334 4335  // Process the loop body.4336  CFGBlock *BodyBlock = nullptr;4337  {4338    assert(D->getBody());4339 4340    // Save the current values for Block, Succ, and continue and break targets4341    SaveAndRestore save_Block(Block), save_Succ(Succ);4342    SaveAndRestore save_continue(ContinueJumpTarget),4343        save_break(BreakJumpTarget);4344 4345    // All continues within this loop should go to the condition block4346    ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos);4347 4348    // All breaks should go to the code following the loop.4349    BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);4350 4351    // NULL out Block to force lazy instantiation of blocks for the body.4352    Block = nullptr;4353 4354    // If body is not a compound statement create implicit scope4355    // and add destructors.4356    if (!isa<CompoundStmt>(D->getBody()))4357      addLocalScopeAndDtors(D->getBody());4358 4359    // Create the body.  The returned block is the entry to the loop body.4360    BodyBlock = addStmt(D->getBody());4361 4362    if (!BodyBlock)4363      BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)"4364    else if (Block) {4365      if (badCFG)4366        return nullptr;4367    }4368 4369    // Add an intermediate block between the BodyBlock and the4370    // ExitConditionBlock to represent the "loop back" transition.  Create an4371    // empty block to represent the transition block for looping back to the4372    // head of the loop.4373    // FIXME: Can we do this more efficiently without adding another block?4374    Block = nullptr;4375    Succ = BodyBlock;4376    CFGBlock *LoopBackBlock = createBlock();4377    LoopBackBlock->setLoopTarget(D);4378 4379    if (!KnownVal.isFalse())4380      // Add the loop body entry as a successor to the condition.4381      addSuccessor(ExitConditionBlock, LoopBackBlock);4382    else4383      addSuccessor(ExitConditionBlock, nullptr);4384  }4385 4386  // Link up the condition block with the code that follows the loop.4387  // (the false branch).4388  addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? nullptr : LoopSuccessor);4389 4390  // There can be no more statements in the body block(s) since we loop back to4391  // the body.  NULL out Block to force lazy creation of another block.4392  Block = nullptr;4393 4394  // Return the loop body, which is the dominating block for the loop.4395  Succ = BodyBlock;4396  return BodyBlock;4397}4398 4399CFGBlock *CFGBuilder::VisitContinueStmt(ContinueStmt *C) {4400  // "continue" is a control-flow statement.  Thus we stop processing the4401  // current block.4402  if (badCFG)4403    return nullptr;4404 4405  // Now create a new block that ends with the continue statement.4406  Block = createBlock(false);4407  Block->setTerminator(C);4408 4409  // If there is no target for the continue, then we are looking at an4410  // incomplete AST.  This means the CFG cannot be constructed.4411  if (ContinueJumpTarget.block) {4412    addAutomaticObjHandling(ScopePos, ContinueJumpTarget.scopePosition, C);4413    addSuccessor(Block, ContinueJumpTarget.block);4414  } else4415    badCFG = true;4416 4417  return Block;4418}4419 4420CFGBlock *CFGBuilder::VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E,4421                                                    AddStmtChoice asc) {4422  if (asc.alwaysAdd(*this, E)) {4423    autoCreateBlock();4424    appendStmt(Block, E);4425  }4426 4427  // VLA types have expressions that must be evaluated.4428  // Evaluation is done only for `sizeof`.4429 4430  if (E->getKind() != UETT_SizeOf)4431    return Block;4432 4433  CFGBlock *lastBlock = Block;4434 4435  if (E->isArgumentType()) {4436    for (const VariableArrayType *VA =FindVA(E->getArgumentType().getTypePtr());4437         VA != nullptr; VA = FindVA(VA->getElementType().getTypePtr()))4438      lastBlock = addStmt(VA->getSizeExpr());4439  }4440  return lastBlock;4441}4442 4443/// VisitStmtExpr - Utility method to handle (nested) statement4444///  expressions (a GCC extension).4445CFGBlock *CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) {4446  if (asc.alwaysAdd(*this, SE)) {4447    autoCreateBlock();4448    appendStmt(Block, SE);4449  }4450  return VisitCompoundStmt(SE->getSubStmt(), /*ExternallyDestructed=*/true);4451}4452 4453CFGBlock *CFGBuilder::VisitSwitchStmt(SwitchStmt *Terminator) {4454  // "switch" is a control-flow statement.  Thus we stop processing the current4455  // block.4456  CFGBlock *SwitchSuccessor = nullptr;4457 4458  // Save local scope position because in case of condition variable ScopePos4459  // won't be restored when traversing AST.4460  SaveAndRestore save_scope_pos(ScopePos);4461 4462  // Create local scope for C++17 switch init-stmt if one exists.4463  if (Stmt *Init = Terminator->getInit())4464    addLocalScopeForStmt(Init);4465 4466  // Create local scope for possible condition variable.4467  // Store scope position. Add implicit destructor.4468  if (VarDecl *VD = Terminator->getConditionVariable())4469    addLocalScopeForVarDecl(VD);4470 4471  addAutomaticObjHandling(ScopePos, save_scope_pos.get(), Terminator);4472 4473  if (Block) {4474    if (badCFG)4475      return nullptr;4476    SwitchSuccessor = Block;4477  } else SwitchSuccessor = Succ;4478 4479  // Save the current "switch" context.4480  SaveAndRestore save_switch(SwitchTerminatedBlock),4481      save_default(DefaultCaseBlock);4482  SaveAndRestore save_break(BreakJumpTarget);4483 4484  // Set the "default" case to be the block after the switch statement.  If the4485  // switch statement contains a "default:", this value will be overwritten with4486  // the block for that code.4487  DefaultCaseBlock = SwitchSuccessor;4488 4489  // Create a new block that will contain the switch statement.4490  SwitchTerminatedBlock = createBlock(false);4491 4492  // Now process the switch body.  The code after the switch is the implicit4493  // successor.4494  Succ = SwitchSuccessor;4495  BreakJumpTarget = JumpTarget(SwitchSuccessor, ScopePos);4496 4497  // When visiting the body, the case statements should automatically get linked4498  // up to the switch.  We also don't keep a pointer to the body, since all4499  // control-flow from the switch goes to case/default statements.4500  assert(Terminator->getBody() && "switch must contain a non-NULL body");4501  Block = nullptr;4502 4503  // For pruning unreachable case statements, save the current state4504  // for tracking the condition value.4505  SaveAndRestore save_switchExclusivelyCovered(switchExclusivelyCovered, false);4506 4507  // Determine if the switch condition can be explicitly evaluated.4508  assert(Terminator->getCond() && "switch condition must be non-NULL");4509  Expr::EvalResult result;4510  bool b = tryEvaluate(Terminator->getCond(), result);4511  SaveAndRestore save_switchCond(switchCond, b ? &result : nullptr);4512 4513  // If body is not a compound statement create implicit scope4514  // and add destructors.4515  if (!isa<CompoundStmt>(Terminator->getBody()))4516    addLocalScopeAndDtors(Terminator->getBody());4517 4518  addStmt(Terminator->getBody());4519  if (Block) {4520    if (badCFG)4521      return nullptr;4522  }4523 4524  // If we have no "default:" case, the default transition is to the code4525  // following the switch body.  Moreover, take into account if all the4526  // cases of a switch are covered (e.g., switching on an enum value).4527  //4528  // Note: We add a successor to a switch that is considered covered yet has no4529  //       case statements if the enumeration has no enumerators.4530  //       We also consider this successor reachable if4531  //       BuildOpts.SwitchReqDefaultCoveredEnum is true.4532  bool SwitchAlwaysHasSuccessor = false;4533  SwitchAlwaysHasSuccessor |= switchExclusivelyCovered;4534  SwitchAlwaysHasSuccessor |=4535      !BuildOpts.AssumeReachableDefaultInSwitchStatements &&4536      Terminator->isAllEnumCasesCovered() && Terminator->getSwitchCaseList();4537  addSuccessor(SwitchTerminatedBlock, DefaultCaseBlock,4538               !SwitchAlwaysHasSuccessor);4539 4540  // Add the terminator and condition in the switch block.4541  SwitchTerminatedBlock->setTerminator(Terminator);4542  Block = SwitchTerminatedBlock;4543  CFGBlock *LastBlock = addStmt(Terminator->getCond());4544 4545  // If the SwitchStmt contains a condition variable, add both the4546  // SwitchStmt and the condition variable initialization to the CFG.4547  if (VarDecl *VD = Terminator->getConditionVariable()) {4548    if (Expr *Init = VD->getInit()) {4549      autoCreateBlock();4550      appendStmt(Block, Terminator->getConditionVariableDeclStmt());4551      LastBlock = addStmt(Init);4552      maybeAddScopeBeginForVarDecl(LastBlock, VD, Init);4553    }4554  }4555 4556  // Finally, if the SwitchStmt contains a C++17 init-stmt, add it to the CFG.4557  if (Stmt *Init = Terminator->getInit()) {4558    autoCreateBlock();4559    LastBlock = addStmt(Init);4560  }4561 4562  return LastBlock;4563}4564 4565static bool shouldAddCase(bool &switchExclusivelyCovered,4566                          const Expr::EvalResult *switchCond,4567                          const CaseStmt *CS,4568                          ASTContext &Ctx) {4569  if (!switchCond)4570    return true;4571 4572  bool addCase = false;4573 4574  if (!switchExclusivelyCovered) {4575    if (switchCond->Val.isInt()) {4576      // Evaluate the LHS of the case value.4577      const llvm::APSInt &lhsInt = CS->getLHS()->EvaluateKnownConstInt(Ctx);4578      const llvm::APSInt &condInt = switchCond->Val.getInt();4579 4580      if (condInt == lhsInt) {4581        addCase = true;4582        switchExclusivelyCovered = true;4583      }4584      else if (condInt > lhsInt) {4585        if (const Expr *RHS = CS->getRHS()) {4586          // Evaluate the RHS of the case value.4587          const llvm::APSInt &V2 = RHS->EvaluateKnownConstInt(Ctx);4588          if (V2 >= condInt) {4589            addCase = true;4590            switchExclusivelyCovered = true;4591          }4592        }4593      }4594    }4595    else4596      addCase = true;4597  }4598  return addCase;4599}4600 4601CFGBlock *CFGBuilder::VisitCaseStmt(CaseStmt *CS) {4602  // CaseStmts are essentially labels, so they are the first statement in a4603  // block.4604  CFGBlock *TopBlock = nullptr, *LastBlock = nullptr;4605 4606  if (Stmt *Sub = CS->getSubStmt()) {4607    // For deeply nested chains of CaseStmts, instead of doing a recursion4608    // (which can blow out the stack), manually unroll and create blocks4609    // along the way.4610    while (isa<CaseStmt>(Sub)) {4611      CFGBlock *currentBlock = createBlock(false);4612      currentBlock->setLabel(CS);4613 4614      if (TopBlock)4615        addSuccessor(LastBlock, currentBlock);4616      else4617        TopBlock = currentBlock;4618 4619      addSuccessor(SwitchTerminatedBlock,4620                   shouldAddCase(switchExclusivelyCovered, switchCond,4621                                 CS, *Context)4622                   ? currentBlock : nullptr);4623 4624      LastBlock = currentBlock;4625      CS = cast<CaseStmt>(Sub);4626      Sub = CS->getSubStmt();4627    }4628 4629    addStmt(Sub);4630  }4631 4632  CFGBlock *CaseBlock = Block;4633  if (!CaseBlock)4634    CaseBlock = createBlock();4635 4636  // Cases statements partition blocks, so this is the top of the basic block we4637  // were processing (the "case XXX:" is the label).4638  CaseBlock->setLabel(CS);4639 4640  if (badCFG)4641    return nullptr;4642 4643  // Add this block to the list of successors for the block with the switch4644  // statement.4645  assert(SwitchTerminatedBlock);4646  addSuccessor(SwitchTerminatedBlock, CaseBlock,4647               shouldAddCase(switchExclusivelyCovered, switchCond,4648                             CS, *Context));4649 4650  // We set Block to NULL to allow lazy creation of a new block (if necessary).4651  Block = nullptr;4652 4653  if (TopBlock) {4654    addSuccessor(LastBlock, CaseBlock);4655    Succ = TopBlock;4656  } else {4657    // This block is now the implicit successor of other blocks.4658    Succ = CaseBlock;4659  }4660 4661  return Succ;4662}4663 4664CFGBlock *CFGBuilder::VisitDefaultStmt(DefaultStmt *Terminator) {4665  if (Terminator->getSubStmt())4666    addStmt(Terminator->getSubStmt());4667 4668  DefaultCaseBlock = Block;4669 4670  if (!DefaultCaseBlock)4671    DefaultCaseBlock = createBlock();4672 4673  // Default statements partition blocks, so this is the top of the basic block4674  // we were processing (the "default:" is the label).4675  DefaultCaseBlock->setLabel(Terminator);4676 4677  if (badCFG)4678    return nullptr;4679 4680  // Unlike case statements, we don't add the default block to the successors4681  // for the switch statement immediately.  This is done when we finish4682  // processing the switch statement.  This allows for the default case4683  // (including a fall-through to the code after the switch statement) to always4684  // be the last successor of a switch-terminated block.4685 4686  // We set Block to NULL to allow lazy creation of a new block (if necessary).4687  Block = nullptr;4688 4689  // This block is now the implicit successor of other blocks.4690  Succ = DefaultCaseBlock;4691 4692  return DefaultCaseBlock;4693}4694 4695CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) {4696  // "try"/"catch" is a control-flow statement.  Thus we stop processing the4697  // current block.4698  CFGBlock *TrySuccessor = nullptr;4699 4700  if (Block) {4701    if (badCFG)4702      return nullptr;4703    TrySuccessor = Block;4704  } else4705    TrySuccessor = Succ;4706 4707  CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock;4708 4709  // Create a new block that will contain the try statement.4710  CFGBlock *NewTryTerminatedBlock = createBlock(false);4711  // Add the terminator in the try block.4712  NewTryTerminatedBlock->setTerminator(Terminator);4713 4714  bool HasCatchAll = false;4715  for (unsigned I = 0, E = Terminator->getNumHandlers(); I != E; ++I) {4716    // The code after the try is the implicit successor.4717    Succ = TrySuccessor;4718    CXXCatchStmt *CS = Terminator->getHandler(I);4719    if (CS->getExceptionDecl() == nullptr) {4720      HasCatchAll = true;4721    }4722    Block = nullptr;4723    CFGBlock *CatchBlock = VisitCXXCatchStmt(CS);4724    if (!CatchBlock)4725      return nullptr;4726    // Add this block to the list of successors for the block with the try4727    // statement.4728    addSuccessor(NewTryTerminatedBlock, CatchBlock);4729  }4730  if (!HasCatchAll) {4731    if (PrevTryTerminatedBlock)4732      addSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock);4733    else4734      addSuccessor(NewTryTerminatedBlock, &cfg->getExit());4735  }4736 4737  // The code after the try is the implicit successor.4738  Succ = TrySuccessor;4739 4740  // Save the current "try" context.4741  SaveAndRestore SaveTry(TryTerminatedBlock, NewTryTerminatedBlock);4742  cfg->addTryDispatchBlock(TryTerminatedBlock);4743 4744  assert(Terminator->getTryBlock() && "try must contain a non-NULL body");4745  Block = nullptr;4746  return addStmt(Terminator->getTryBlock());4747}4748 4749CFGBlock *CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt *CS) {4750  // CXXCatchStmt are treated like labels, so they are the first statement in a4751  // block.4752 4753  // Save local scope position because in case of exception variable ScopePos4754  // won't be restored when traversing AST.4755  SaveAndRestore save_scope_pos(ScopePos);4756 4757  // Create local scope for possible exception variable.4758  // Store scope position. Add implicit destructor.4759  if (VarDecl *VD = CS->getExceptionDecl()) {4760    LocalScope::const_iterator BeginScopePos = ScopePos;4761    addLocalScopeForVarDecl(VD);4762    addAutomaticObjHandling(ScopePos, BeginScopePos, CS);4763  }4764 4765  if (CS->getHandlerBlock())4766    addStmt(CS->getHandlerBlock());4767 4768  CFGBlock *CatchBlock = Block;4769  if (!CatchBlock)4770    CatchBlock = createBlock();4771 4772  // CXXCatchStmt is more than just a label.  They have semantic meaning4773  // as well, as they implicitly "initialize" the catch variable.  Add4774  // it to the CFG as a CFGElement so that the control-flow of these4775  // semantics gets captured.4776  appendStmt(CatchBlock, CS);4777 4778  // Also add the CXXCatchStmt as a label, to mirror handling of regular4779  // labels.4780  CatchBlock->setLabel(CS);4781 4782  // Bail out if the CFG is bad.4783  if (badCFG)4784    return nullptr;4785 4786  // We set Block to NULL to allow lazy creation of a new block (if necessary).4787  Block = nullptr;4788 4789  return CatchBlock;4790}4791 4792CFGBlock *CFGBuilder::VisitCXXForRangeStmt(CXXForRangeStmt *S) {4793  // C++0x for-range statements are specified as [stmt.ranged]:4794  //4795  // {4796  //   auto && __range = range-init;4797  //   for ( auto __begin = begin-expr,4798  //         __end = end-expr;4799  //         __begin != __end;4800  //         ++__begin ) {4801  //     for-range-declaration = *__begin;4802  //     statement4803  //   }4804  // }4805 4806  // Save local scope position before the addition of the implicit variables.4807  SaveAndRestore save_scope_pos(ScopePos);4808 4809  // Create local scopes and destructors for range, begin and end variables.4810  if (Stmt *Range = S->getRangeStmt())4811    addLocalScopeForStmt(Range);4812  if (Stmt *Begin = S->getBeginStmt())4813    addLocalScopeForStmt(Begin);4814  if (Stmt *End = S->getEndStmt())4815    addLocalScopeForStmt(End);4816  addAutomaticObjHandling(ScopePos, save_scope_pos.get(), S);4817 4818  LocalScope::const_iterator ContinueScopePos = ScopePos;4819 4820  // "for" is a control-flow statement.  Thus we stop processing the current4821  // block.4822  CFGBlock *LoopSuccessor = nullptr;4823  if (Block) {4824    if (badCFG)4825      return nullptr;4826    LoopSuccessor = Block;4827  } else4828    LoopSuccessor = Succ;4829 4830  // Save the current value for the break targets.4831  // All breaks should go to the code following the loop.4832  SaveAndRestore save_break(BreakJumpTarget);4833  BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos);4834 4835  // The block for the __begin != __end expression.4836  CFGBlock *ConditionBlock = createBlock(false);4837  ConditionBlock->setTerminator(S);4838 4839  // Now add the actual condition to the condition block.4840  if (Expr *C = S->getCond()) {4841    Block = ConditionBlock;4842    CFGBlock *BeginConditionBlock = addStmt(C);4843    if (badCFG)4844      return nullptr;4845    assert(BeginConditionBlock == ConditionBlock &&4846           "condition block in for-range was unexpectedly complex");4847    (void)BeginConditionBlock;4848  }4849 4850  // The condition block is the implicit successor for the loop body as well as4851  // any code above the loop.4852  Succ = ConditionBlock;4853 4854  // See if this is a known constant.4855  TryResult KnownVal(true);4856 4857  if (S->getCond())4858    KnownVal = tryEvaluateBool(S->getCond());4859 4860  // Now create the loop body.4861  {4862    assert(S->getBody());4863 4864    // Save the current values for Block, Succ, and continue targets.4865    SaveAndRestore save_Block(Block), save_Succ(Succ);4866    SaveAndRestore save_continue(ContinueJumpTarget);4867 4868    // Generate increment code in its own basic block.  This is the target of4869    // continue statements.4870    Block = nullptr;4871    Succ = addStmt(S->getInc());4872    if (badCFG)4873      return nullptr;4874    ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos);4875 4876    // The starting block for the loop increment is the block that should4877    // represent the 'loop target' for looping back to the start of the loop.4878    ContinueJumpTarget.block->setLoopTarget(S);4879 4880    // Finish up the increment block and prepare to start the loop body.4881    assert(Block);4882    if (badCFG)4883      return nullptr;4884    Block = nullptr;4885 4886    // Add implicit scope and dtors for loop variable.4887    addLocalScopeAndDtors(S->getLoopVarStmt());4888 4889    // If body is not a compound statement create implicit scope4890    // and add destructors.4891    if (!isa<CompoundStmt>(S->getBody()))4892      addLocalScopeAndDtors(S->getBody());4893 4894    // Populate a new block to contain the loop body and loop variable.4895    addStmt(S->getBody());4896 4897    if (badCFG)4898      return nullptr;4899    CFGBlock *LoopVarStmtBlock = addStmt(S->getLoopVarStmt());4900    if (badCFG)4901      return nullptr;4902 4903    // This new body block is a successor to our condition block.4904    addSuccessor(ConditionBlock,4905                 KnownVal.isFalse() ? nullptr : LoopVarStmtBlock);4906  }4907 4908  // Link up the condition block with the code that follows the loop (the4909  // false branch).4910  addSuccessor(ConditionBlock, KnownVal.isTrue() ? nullptr : LoopSuccessor);4911 4912  // Add the initialization statements.4913  Block = createBlock();4914  addStmt(S->getBeginStmt());4915  addStmt(S->getEndStmt());4916  CFGBlock *Head = addStmt(S->getRangeStmt());4917  if (S->getInit())4918    Head = addStmt(S->getInit());4919  return Head;4920}4921 4922CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E,4923    AddStmtChoice asc, bool ExternallyDestructed) {4924  if (BuildOpts.AddTemporaryDtors) {4925    // If adding implicit destructors visit the full expression for adding4926    // destructors of temporaries.4927    TempDtorContext Context;4928    VisitForTemporaryDtors(E->getSubExpr(), ExternallyDestructed, Context);4929 4930    // Full expression has to be added as CFGStmt so it will be sequenced4931    // before destructors of it's temporaries.4932    asc = asc.withAlwaysAdd(true);4933  }4934  return Visit(E->getSubExpr(), asc);4935}4936 4937CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E,4938                                                AddStmtChoice asc) {4939  if (asc.alwaysAdd(*this, E)) {4940    autoCreateBlock();4941    appendStmt(Block, E);4942 4943    findConstructionContexts(4944        ConstructionContextLayer::create(cfg->getBumpVectorContext(), E),4945        E->getSubExpr());4946 4947    // We do not want to propagate the AlwaysAdd property.4948    asc = asc.withAlwaysAdd(false);4949  }4950  return Visit(E->getSubExpr(), asc);4951}4952 4953CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C,4954                                            AddStmtChoice asc) {4955  // If the constructor takes objects as arguments by value, we need to properly4956  // construct these objects. Construction contexts we find here aren't for the4957  // constructor C, they're for its arguments only.4958  findConstructionContextsForArguments(C);4959  appendConstructor(C);4960 4961  return VisitChildren(C);4962}4963 4964CFGBlock *CFGBuilder::VisitCXXNewExpr(CXXNewExpr *NE,4965                                      AddStmtChoice asc) {4966  autoCreateBlock();4967  appendStmt(Block, NE);4968 4969  findConstructionContexts(4970      ConstructionContextLayer::create(cfg->getBumpVectorContext(), NE),4971      const_cast<CXXConstructExpr *>(NE->getConstructExpr()));4972 4973  if (NE->getInitializer())4974    Block = Visit(NE->getInitializer());4975 4976  if (BuildOpts.AddCXXNewAllocator)4977    appendNewAllocator(Block, NE);4978 4979  if (NE->isArray() && *NE->getArraySize())4980    Block = Visit(*NE->getArraySize());4981 4982  for (CXXNewExpr::arg_iterator I = NE->placement_arg_begin(),4983       E = NE->placement_arg_end(); I != E; ++I)4984    Block = Visit(*I);4985 4986  return Block;4987}4988 4989CFGBlock *CFGBuilder::VisitCXXDeleteExpr(CXXDeleteExpr *DE,4990                                         AddStmtChoice asc) {4991  autoCreateBlock();4992  appendStmt(Block, DE);4993  QualType DTy = DE->getDestroyedType();4994  if (!DTy.isNull()) {4995    DTy = DTy.getNonReferenceType();4996    CXXRecordDecl *RD = Context->getBaseElementType(DTy)->getAsCXXRecordDecl();4997    if (RD) {4998      if (RD->isCompleteDefinition() && !RD->hasTrivialDestructor())4999        appendDeleteDtor(Block, RD, DE);5000    }5001  }5002 5003  return VisitChildren(DE);5004}5005 5006CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E,5007                                                 AddStmtChoice asc) {5008  if (asc.alwaysAdd(*this, E)) {5009    autoCreateBlock();5010    appendStmt(Block, E);5011    // We do not want to propagate the AlwaysAdd property.5012    asc = asc.withAlwaysAdd(false);5013  }5014  return Visit(E->getSubExpr(), asc);5015}5016 5017CFGBlock *CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *E,5018                                                  AddStmtChoice asc) {5019  // If the constructor takes objects as arguments by value, we need to properly5020  // construct these objects. Construction contexts we find here aren't for the5021  // constructor C, they're for its arguments only.5022  findConstructionContextsForArguments(E);5023  appendConstructor(E);5024 5025  return VisitChildren(E);5026}5027 5028CFGBlock *CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr *E,5029                                            AddStmtChoice asc) {5030  if (asc.alwaysAdd(*this, E)) {5031    autoCreateBlock();5032    appendStmt(Block, E);5033  }5034 5035  if (E->getCastKind() == CK_IntegralToBoolean)5036    tryEvaluateBool(E->getSubExpr()->IgnoreParens());5037 5038  return Visit(E->getSubExpr(), AddStmtChoice());5039}5040 5041CFGBlock *CFGBuilder::VisitConstantExpr(ConstantExpr *E, AddStmtChoice asc) {5042  return Visit(E->getSubExpr(), AddStmtChoice());5043}5044 5045CFGBlock *CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt *I) {5046  // Lazily create the indirect-goto dispatch block if there isn't one already.5047  CFGBlock *IBlock = cfg->getIndirectGotoBlock();5048 5049  if (!IBlock) {5050    IBlock = createBlock(false);5051    cfg->setIndirectGotoBlock(IBlock);5052  }5053 5054  // IndirectGoto is a control-flow statement.  Thus we stop processing the5055  // current block and create a new one.5056  if (badCFG)5057    return nullptr;5058 5059  Block = createBlock(false);5060  Block->setTerminator(I);5061  addSuccessor(Block, IBlock);5062  return addStmt(I->getTarget());5063}5064 5065CFGBlock *CFGBuilder::VisitForTemporaryDtors(Stmt *E, bool ExternallyDestructed,5066                                             TempDtorContext &Context) {5067  assert(BuildOpts.AddImplicitDtors && BuildOpts.AddTemporaryDtors);5068 5069tryAgain:5070  if (!E) {5071    badCFG = true;5072    return nullptr;5073  }5074  switch (E->getStmtClass()) {5075    default:5076      return VisitChildrenForTemporaryDtors(E, false, Context);5077 5078    case Stmt::InitListExprClass:5079      return VisitChildrenForTemporaryDtors(E, ExternallyDestructed, Context);5080 5081    case Stmt::BinaryOperatorClass:5082      return VisitBinaryOperatorForTemporaryDtors(cast<BinaryOperator>(E),5083                                                  ExternallyDestructed,5084                                                  Context);5085 5086    case Stmt::CXXBindTemporaryExprClass:5087      return VisitCXXBindTemporaryExprForTemporaryDtors(5088          cast<CXXBindTemporaryExpr>(E), ExternallyDestructed, Context);5089 5090    case Stmt::BinaryConditionalOperatorClass:5091    case Stmt::ConditionalOperatorClass:5092      return VisitConditionalOperatorForTemporaryDtors(5093          cast<AbstractConditionalOperator>(E), ExternallyDestructed, Context);5094 5095    case Stmt::ImplicitCastExprClass:5096      // For implicit cast we want ExternallyDestructed to be passed further.5097      E = cast<CastExpr>(E)->getSubExpr();5098      goto tryAgain;5099 5100    case Stmt::CXXFunctionalCastExprClass:5101      // For functional cast we want ExternallyDestructed to be passed further.5102      E = cast<CXXFunctionalCastExpr>(E)->getSubExpr();5103      goto tryAgain;5104 5105    case Stmt::ConstantExprClass:5106      E = cast<ConstantExpr>(E)->getSubExpr();5107      goto tryAgain;5108 5109    case Stmt::ParenExprClass:5110      E = cast<ParenExpr>(E)->getSubExpr();5111      goto tryAgain;5112 5113    case Stmt::MaterializeTemporaryExprClass: {5114      const MaterializeTemporaryExpr* MTE = cast<MaterializeTemporaryExpr>(E);5115      ExternallyDestructed = (MTE->getStorageDuration() != SD_FullExpression);5116      SmallVector<const Expr *, 2> CommaLHSs;5117      SmallVector<SubobjectAdjustment, 2> Adjustments;5118      // Find the expression whose lifetime needs to be extended.5119      E = const_cast<Expr *>(5120          cast<MaterializeTemporaryExpr>(E)5121              ->getSubExpr()5122              ->skipRValueSubobjectAdjustments(CommaLHSs, Adjustments));5123      // Visit the skipped comma operator left-hand sides for other temporaries.5124      for (const Expr *CommaLHS : CommaLHSs) {5125        VisitForTemporaryDtors(const_cast<Expr *>(CommaLHS),5126                               /*ExternallyDestructed=*/false, Context);5127      }5128      goto tryAgain;5129    }5130 5131    case Stmt::BlockExprClass:5132      // Don't recurse into blocks; their subexpressions don't get evaluated5133      // here.5134      return Block;5135 5136    case Stmt::LambdaExprClass: {5137      // For lambda expressions, only recurse into the capture initializers,5138      // and not the body.5139      auto *LE = cast<LambdaExpr>(E);5140      CFGBlock *B = Block;5141      for (Expr *Init : LE->capture_inits()) {5142        if (Init) {5143          if (CFGBlock *R = VisitForTemporaryDtors(5144                  Init, /*ExternallyDestructed=*/true, Context))5145            B = R;5146        }5147      }5148      return B;5149    }5150 5151    case Stmt::StmtExprClass:5152      // Don't recurse into statement expressions; any cleanups inside them5153      // will be wrapped in their own ExprWithCleanups.5154      return Block;5155 5156    case Stmt::CXXDefaultArgExprClass:5157      E = cast<CXXDefaultArgExpr>(E)->getExpr();5158      goto tryAgain;5159 5160    case Stmt::CXXDefaultInitExprClass:5161      E = cast<CXXDefaultInitExpr>(E)->getExpr();5162      goto tryAgain;5163  }5164}5165 5166CFGBlock *CFGBuilder::VisitChildrenForTemporaryDtors(Stmt *E,5167                                                     bool ExternallyDestructed,5168                                                     TempDtorContext &Context) {5169  if (isa<LambdaExpr>(E)) {5170    // Do not visit the children of lambdas; they have their own CFGs.5171    return Block;5172  }5173 5174  // When visiting children for destructors we want to visit them in reverse5175  // order that they will appear in the CFG.  Because the CFG is built5176  // bottom-up, this means we visit them in their natural order, which5177  // reverses them in the CFG.5178  CFGBlock *B = Block;5179  for (Stmt *Child : E->children())5180    if (Child)5181      if (CFGBlock *R = VisitForTemporaryDtors(Child, ExternallyDestructed, Context))5182        B = R;5183 5184  return B;5185}5186 5187CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors(5188    BinaryOperator *E, bool ExternallyDestructed, TempDtorContext &Context) {5189  if (E->isCommaOp()) {5190    // For the comma operator, the LHS expression is evaluated before the RHS5191    // expression, so prepend temporary destructors for the LHS first.5192    CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS(), false, Context);5193    CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS(), ExternallyDestructed, Context);5194    return RHSBlock ? RHSBlock : LHSBlock;5195  }5196 5197  if (E->isLogicalOp()) {5198    VisitForTemporaryDtors(E->getLHS(), false, Context);5199    TryResult RHSExecuted = tryEvaluateBool(E->getLHS());5200    if (RHSExecuted.isKnown() && E->getOpcode() == BO_LOr)5201      RHSExecuted.negate();5202 5203    // We do not know at CFG-construction time whether the right-hand-side was5204    // executed, thus we add a branch node that depends on the temporary5205    // constructor call.5206    TempDtorContext RHSContext(5207        bothKnownTrue(Context.KnownExecuted, RHSExecuted));5208    VisitForTemporaryDtors(E->getRHS(), false, RHSContext);5209    InsertTempDtorDecisionBlock(RHSContext);5210 5211    return Block;5212  }5213 5214  if (E->isAssignmentOp()) {5215    // For assignment operators, the RHS expression is evaluated before the LHS5216    // expression, so prepend temporary destructors for the RHS first.5217    CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS(), false, Context);5218    CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS(), false, Context);5219    return LHSBlock ? LHSBlock : RHSBlock;5220  }5221 5222  // Any other operator is visited normally.5223  return VisitChildrenForTemporaryDtors(E, ExternallyDestructed, Context);5224}5225 5226CFGBlock *CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors(5227    CXXBindTemporaryExpr *E, bool ExternallyDestructed, TempDtorContext &Context) {5228  // First add destructors for temporaries in subexpression.5229  // Because VisitCXXBindTemporaryExpr calls setDestructed:5230  CFGBlock *B = VisitForTemporaryDtors(E->getSubExpr(), true, Context);5231  if (!ExternallyDestructed) {5232    // If lifetime of temporary is not prolonged (by assigning to constant5233    // reference) add destructor for it.5234 5235    const CXXDestructorDecl *Dtor = E->getTemporary()->getDestructor();5236 5237    if (Dtor->getParent()->isAnyDestructorNoReturn()) {5238      // If the destructor is marked as a no-return destructor, we need to5239      // create a new block for the destructor which does not have as a5240      // successor anything built thus far. Control won't flow out of this5241      // block.5242      if (B) Succ = B;5243      Block = createNoReturnBlock();5244    } else if (Context.needsTempDtorBranch()) {5245      // If we need to introduce a branch, we add a new block that we will hook5246      // up to a decision block later.5247      if (B) Succ = B;5248      Block = createBlock();5249    } else {5250      autoCreateBlock();5251    }5252    if (Context.needsTempDtorBranch()) {5253      Context.setDecisionPoint(Succ, E);5254    }5255    appendTemporaryDtor(Block, E);5256 5257    B = Block;5258  }5259  return B;5260}5261 5262void CFGBuilder::InsertTempDtorDecisionBlock(const TempDtorContext &Context,5263                                             CFGBlock *FalseSucc) {5264  if (!Context.TerminatorExpr) {5265    // If no temporary was found, we do not need to insert a decision point.5266    return;5267  }5268  assert(Context.TerminatorExpr);5269  CFGBlock *Decision = createBlock(false);5270  Decision->setTerminator(CFGTerminator(Context.TerminatorExpr,5271                                        CFGTerminator::TemporaryDtorsBranch));5272  addSuccessor(Decision, Block, !Context.KnownExecuted.isFalse());5273  addSuccessor(Decision, FalseSucc ? FalseSucc : Context.Succ,5274               !Context.KnownExecuted.isTrue());5275  Block = Decision;5276}5277 5278CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaryDtors(5279    AbstractConditionalOperator *E, bool ExternallyDestructed,5280    TempDtorContext &Context) {5281  VisitForTemporaryDtors(E->getCond(), false, Context);5282  CFGBlock *ConditionBlock = Block;5283  CFGBlock *ConditionSucc = Succ;5284  TryResult ConditionVal = tryEvaluateBool(E->getCond());5285  TryResult NegatedVal = ConditionVal;5286  if (NegatedVal.isKnown()) NegatedVal.negate();5287 5288  TempDtorContext TrueContext(5289      bothKnownTrue(Context.KnownExecuted, ConditionVal));5290  VisitForTemporaryDtors(E->getTrueExpr(), ExternallyDestructed, TrueContext);5291  CFGBlock *TrueBlock = Block;5292 5293  Block = ConditionBlock;5294  Succ = ConditionSucc;5295  TempDtorContext FalseContext(5296      bothKnownTrue(Context.KnownExecuted, NegatedVal));5297  VisitForTemporaryDtors(E->getFalseExpr(), ExternallyDestructed, FalseContext);5298 5299  if (TrueContext.TerminatorExpr && FalseContext.TerminatorExpr) {5300    InsertTempDtorDecisionBlock(FalseContext, TrueBlock);5301  } else if (TrueContext.TerminatorExpr) {5302    Block = TrueBlock;5303    InsertTempDtorDecisionBlock(TrueContext);5304  } else {5305    InsertTempDtorDecisionBlock(FalseContext);5306  }5307  return Block;5308}5309 5310CFGBlock *CFGBuilder::VisitOMPExecutableDirective(OMPExecutableDirective *D,5311                                                  AddStmtChoice asc) {5312  if (asc.alwaysAdd(*this, D)) {5313    autoCreateBlock();5314    appendStmt(Block, D);5315  }5316 5317  // Iterate over all used expression in clauses.5318  CFGBlock *B = Block;5319 5320  // Reverse the elements to process them in natural order. Iterators are not5321  // bidirectional, so we need to create temp vector.5322  SmallVector<Stmt *, 8> Used(5323      OMPExecutableDirective::used_clauses_children(D->clauses()));5324  for (Stmt *S : llvm::reverse(Used)) {5325    assert(S && "Expected non-null used-in-clause child.");5326    if (CFGBlock *R = Visit(S))5327      B = R;5328  }5329  // Visit associated structured block if any.5330  if (!D->isStandaloneDirective()) {5331    Stmt *S = D->getRawStmt();5332    if (!isa<CompoundStmt>(S))5333      addLocalScopeAndDtors(S);5334    if (CFGBlock *R = addStmt(S))5335      B = R;5336  }5337 5338  return B;5339}5340 5341/// createBlock - Constructs and adds a new CFGBlock to the CFG.  The block has5342///  no successors or predecessors.  If this is the first block created in the5343///  CFG, it is automatically set to be the Entry and Exit of the CFG.5344CFGBlock *CFG::createBlock() {5345  bool first_block = begin() == end();5346 5347  // Create the block.5348  CFGBlock *Mem = new (getAllocator()) CFGBlock(NumBlockIDs++, BlkBVC, this);5349  Blocks.push_back(Mem, BlkBVC);5350 5351  // If this is the first block, set it as the Entry and Exit.5352  if (first_block)5353    Entry = Exit = &back();5354 5355  // Return the block.5356  return &back();5357}5358 5359/// buildCFG - Constructs a CFG from an AST.5360std::unique_ptr<CFG> CFG::buildCFG(const Decl *D, Stmt *Statement,5361                                   ASTContext *C, const BuildOptions &BO) {5362  CFGBuilder Builder(C, BO);5363  return Builder.buildCFG(D, Statement);5364}5365 5366bool CFG::isLinear() const {5367  // Quick path: if we only have the ENTRY block, the EXIT block, and some code5368  // in between, then we have no room for control flow.5369  if (size() <= 3)5370    return true;5371 5372  // Traverse the CFG until we find a branch.5373  // TODO: While this should still be very fast,5374  // maybe we should cache the answer.5375  llvm::SmallPtrSet<const CFGBlock *, 4> Visited;5376  const CFGBlock *B = Entry;5377  while (B != Exit) {5378    auto IteratorAndFlag = Visited.insert(B);5379    if (!IteratorAndFlag.second) {5380      // We looped back to a block that we've already visited. Not linear.5381      return false;5382    }5383 5384    // Iterate over reachable successors.5385    const CFGBlock *FirstReachableB = nullptr;5386    for (const CFGBlock::AdjacentBlock &AB : B->succs()) {5387      if (!AB.isReachable())5388        continue;5389 5390      if (FirstReachableB == nullptr) {5391        FirstReachableB = &*AB;5392      } else {5393        // We've encountered a branch. It's not a linear CFG.5394        return false;5395      }5396    }5397 5398    if (!FirstReachableB) {5399      // We reached a dead end. EXIT is unreachable. This is linear enough.5400      return true;5401    }5402 5403    // There's only one way to move forward. Proceed.5404    B = FirstReachableB;5405  }5406 5407  // We reached EXIT and found no branches.5408  return true;5409}5410 5411const CXXDestructorDecl *5412CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const {5413  switch (getKind()) {5414    case CFGElement::Initializer:5415    case CFGElement::NewAllocator:5416    case CFGElement::LoopExit:5417    case CFGElement::LifetimeEnds:5418    case CFGElement::Statement:5419    case CFGElement::Constructor:5420    case CFGElement::CXXRecordTypedCall:5421    case CFGElement::ScopeBegin:5422    case CFGElement::ScopeEnd:5423    case CFGElement::CleanupFunction:5424      llvm_unreachable("getDestructorDecl should only be used with "5425                       "ImplicitDtors");5426    case CFGElement::AutomaticObjectDtor: {5427      const VarDecl *var = castAs<CFGAutomaticObjDtor>().getVarDecl();5428      QualType ty = var->getType();5429 5430      // FIXME: See CFGBuilder::addLocalScopeForVarDecl.5431      //5432      // Lifetime-extending constructs are handled here. This works for a single5433      // temporary in an initializer expression.5434      if (ty->isReferenceType()) {5435        if (const Expr *Init = var->getInit()) {5436          ty = getReferenceInitTemporaryType(Init);5437        }5438      }5439 5440      while (const ArrayType *arrayType = astContext.getAsArrayType(ty)) {5441        ty = arrayType->getElementType();5442      }5443 5444      // The situation when the type of the lifetime-extending reference5445      // does not correspond to the type of the object is supposed5446      // to be handled by now. In particular, 'ty' is now the unwrapped5447      // record type.5448      const CXXRecordDecl *classDecl = ty->getAsCXXRecordDecl();5449      assert(classDecl);5450      return classDecl->getDestructor();5451    }5452    case CFGElement::DeleteDtor: {5453      const CXXDeleteExpr *DE = castAs<CFGDeleteDtor>().getDeleteExpr();5454      QualType DTy = DE->getDestroyedType();5455      DTy = DTy.getNonReferenceType();5456      const CXXRecordDecl *classDecl =5457          astContext.getBaseElementType(DTy)->getAsCXXRecordDecl();5458      return classDecl->getDestructor();5459    }5460    case CFGElement::TemporaryDtor: {5461      const CXXBindTemporaryExpr *bindExpr =5462        castAs<CFGTemporaryDtor>().getBindTemporaryExpr();5463      const CXXTemporary *temp = bindExpr->getTemporary();5464      return temp->getDestructor();5465    }5466    case CFGElement::MemberDtor: {5467      const FieldDecl *field = castAs<CFGMemberDtor>().getFieldDecl();5468      QualType ty = field->getType();5469 5470      while (const ArrayType *arrayType = astContext.getAsArrayType(ty)) {5471        ty = arrayType->getElementType();5472      }5473 5474      const CXXRecordDecl *classDecl = ty->getAsCXXRecordDecl();5475      assert(classDecl);5476      return classDecl->getDestructor();5477    }5478    case CFGElement::BaseDtor:5479      // Not yet supported.5480      return nullptr;5481  }5482  llvm_unreachable("getKind() returned bogus value");5483}5484 5485//===----------------------------------------------------------------------===//5486// CFGBlock operations.5487//===----------------------------------------------------------------------===//5488 5489CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, bool IsReachable)5490    : ReachableBlock(IsReachable ? B : nullptr),5491      UnreachableBlock(!IsReachable ? B : nullptr,5492                       B && IsReachable ? AB_Normal : AB_Unreachable) {}5493 5494CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock)5495    : ReachableBlock(B),5496      UnreachableBlock(B == AlternateBlock ? nullptr : AlternateBlock,5497                       B == AlternateBlock ? AB_Alternate : AB_Normal) {}5498 5499void CFGBlock::addSuccessor(AdjacentBlock Succ,5500                            BumpVectorContext &C) {5501  if (CFGBlock *B = Succ.getReachableBlock())5502    B->Preds.push_back(AdjacentBlock(this, Succ.isReachable()), C);5503 5504  if (CFGBlock *UnreachableB = Succ.getPossiblyUnreachableBlock())5505    UnreachableB->Preds.push_back(AdjacentBlock(this, false), C);5506 5507  Succs.push_back(Succ, C);5508}5509 5510bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F,5511        const CFGBlock *From, const CFGBlock *To) {5512  if (F.IgnoreNullPredecessors && !From)5513    return true;5514 5515  if (To && From && F.IgnoreDefaultsWithCoveredEnums) {5516    // If the 'To' has no label or is labeled but the label isn't a5517    // CaseStmt then filter this edge.5518    if (const SwitchStmt *S =5519        dyn_cast_or_null<SwitchStmt>(From->getTerminatorStmt())) {5520      if (S->isAllEnumCasesCovered()) {5521        const Stmt *L = To->getLabel();5522        if (!L || !isa<CaseStmt>(L))5523          return true;5524      }5525    }5526  }5527 5528  return false;5529}5530 5531//===----------------------------------------------------------------------===//5532// CFG pretty printing5533//===----------------------------------------------------------------------===//5534 5535namespace {5536 5537class StmtPrinterHelper : public PrinterHelper  {5538  using StmtMapTy = llvm::DenseMap<const Stmt *, std::pair<unsigned, unsigned>>;5539  using DeclMapTy = llvm::DenseMap<const Decl *, std::pair<unsigned, unsigned>>;5540 5541  StmtMapTy StmtMap;5542  DeclMapTy DeclMap;5543  signed currentBlock = 0;5544  unsigned currStmt = 0;5545  const LangOptions &LangOpts;5546 5547public:5548  StmtPrinterHelper(const CFG* cfg, const LangOptions &LO)5549      : LangOpts(LO) {5550    if (!cfg)5551      return;5552    for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) {5553      unsigned j = 1;5554      for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ;5555           BI != BEnd; ++BI, ++j ) {5556        if (std::optional<CFGStmt> SE = BI->getAs<CFGStmt>()) {5557          const Stmt *stmt= SE->getStmt();5558          std::pair<unsigned, unsigned> P((*I)->getBlockID(), j);5559          StmtMap[stmt] = P;5560 5561          switch (stmt->getStmtClass()) {5562            case Stmt::DeclStmtClass:5563              DeclMap[cast<DeclStmt>(stmt)->getSingleDecl()] = P;5564              break;5565            case Stmt::IfStmtClass: {5566              const VarDecl *var = cast<IfStmt>(stmt)->getConditionVariable();5567              if (var)5568                DeclMap[var] = P;5569              break;5570            }5571            case Stmt::ForStmtClass: {5572              const VarDecl *var = cast<ForStmt>(stmt)->getConditionVariable();5573              if (var)5574                DeclMap[var] = P;5575              break;5576            }5577            case Stmt::WhileStmtClass: {5578              const VarDecl *var =5579                cast<WhileStmt>(stmt)->getConditionVariable();5580              if (var)5581                DeclMap[var] = P;5582              break;5583            }5584            case Stmt::SwitchStmtClass: {5585              const VarDecl *var =5586                cast<SwitchStmt>(stmt)->getConditionVariable();5587              if (var)5588                DeclMap[var] = P;5589              break;5590            }5591            case Stmt::CXXCatchStmtClass: {5592              const VarDecl *var =5593                cast<CXXCatchStmt>(stmt)->getExceptionDecl();5594              if (var)5595                DeclMap[var] = P;5596              break;5597            }5598            default:5599              break;5600          }5601        }5602      }5603    }5604  }5605 5606  ~StmtPrinterHelper() override = default;5607 5608  const LangOptions &getLangOpts() const { return LangOpts; }5609  void setBlockID(signed i) { currentBlock = i; }5610  void setStmtID(unsigned i) { currStmt = i; }5611 5612  bool handledStmt(Stmt *S, raw_ostream &OS) override {5613    StmtMapTy::iterator I = StmtMap.find(S);5614 5615    if (I == StmtMap.end())5616      return false;5617 5618    if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock5619                          && I->second.second == currStmt) {5620      return false;5621    }5622 5623    OS << "[B" << I->second.first << "." << I->second.second << "]";5624    return true;5625  }5626 5627  bool handleDecl(const Decl *D, raw_ostream &OS) {5628    DeclMapTy::iterator I = DeclMap.find(D);5629 5630    if (I == DeclMap.end()) {5631      // ParmVarDecls are not declared in the CFG itself, so they do not appear5632      // in DeclMap.5633      if (auto *PVD = dyn_cast_or_null<ParmVarDecl>(D)) {5634        OS << "[Parm: " << PVD->getNameAsString() << "]";5635        return true;5636      }5637      return false;5638    }5639 5640    if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock5641                          && I->second.second == currStmt) {5642      return false;5643    }5644 5645    OS << "[B" << I->second.first << "." << I->second.second << "]";5646    return true;5647  }5648};5649 5650class CFGBlockTerminatorPrint5651    : public StmtVisitor<CFGBlockTerminatorPrint,void> {5652  raw_ostream &OS;5653  StmtPrinterHelper* Helper;5654  PrintingPolicy Policy;5655 5656public:5657  CFGBlockTerminatorPrint(raw_ostream &os, StmtPrinterHelper* helper,5658                          const PrintingPolicy &Policy)5659      : OS(os), Helper(helper), Policy(Policy) {5660    this->Policy.IncludeNewlines = false;5661  }5662 5663  void VisitIfStmt(IfStmt *I) {5664    OS << "if ";5665    if (Stmt *C = I->getCond())5666      C->printPretty(OS, Helper, Policy);5667  }5668 5669  // Default case.5670  void VisitStmt(Stmt *Terminator) {5671    Terminator->printPretty(OS, Helper, Policy);5672  }5673 5674  void VisitDeclStmt(DeclStmt *DS) {5675    VarDecl *VD = cast<VarDecl>(DS->getSingleDecl());5676    OS << "static init " << VD->getName();5677  }5678 5679  void VisitForStmt(ForStmt *F) {5680    OS << "for (" ;5681    if (F->getInit())5682      OS << "...";5683    OS << "; ";5684    if (Stmt *C = F->getCond())5685      C->printPretty(OS, Helper, Policy);5686    OS << "; ";5687    if (F->getInc())5688      OS << "...";5689    OS << ")";5690  }5691 5692  void VisitWhileStmt(WhileStmt *W) {5693    OS << "while " ;5694    if (Stmt *C = W->getCond())5695      C->printPretty(OS, Helper, Policy);5696  }5697 5698  void VisitDoStmt(DoStmt *D) {5699    OS << "do ... while ";5700    if (Stmt *C = D->getCond())5701      C->printPretty(OS, Helper, Policy);5702  }5703 5704  void VisitSwitchStmt(SwitchStmt *Terminator) {5705    OS << "switch ";5706    Terminator->getCond()->printPretty(OS, Helper, Policy);5707  }5708 5709  void VisitCXXTryStmt(CXXTryStmt *) { OS << "try ..."; }5710 5711  void VisitObjCAtTryStmt(ObjCAtTryStmt *) { OS << "@try ..."; }5712 5713  void VisitSEHTryStmt(SEHTryStmt *CS) { OS << "__try ..."; }5714 5715  void VisitAbstractConditionalOperator(AbstractConditionalOperator* C) {5716    if (Stmt *Cond = C->getCond())5717      Cond->printPretty(OS, Helper, Policy);5718    OS << " ? ... : ...";5719  }5720 5721  void VisitChooseExpr(ChooseExpr *C) {5722    OS << "__builtin_choose_expr( ";5723    if (Stmt *Cond = C->getCond())5724      Cond->printPretty(OS, Helper, Policy);5725    OS << " )";5726  }5727 5728  void VisitIndirectGotoStmt(IndirectGotoStmt *I) {5729    OS << "goto *";5730    if (Stmt *T = I->getTarget())5731      T->printPretty(OS, Helper, Policy);5732  }5733 5734  void VisitBinaryOperator(BinaryOperator* B) {5735    if (!B->isLogicalOp()) {5736      VisitExpr(B);5737      return;5738    }5739 5740    if (B->getLHS())5741      B->getLHS()->printPretty(OS, Helper, Policy);5742 5743    switch (B->getOpcode()) {5744      case BO_LOr:5745        OS << " || ...";5746        return;5747      case BO_LAnd:5748        OS << " && ...";5749        return;5750      default:5751        llvm_unreachable("Invalid logical operator.");5752    }5753  }5754 5755  void VisitExpr(Expr *E) {5756    E->printPretty(OS, Helper, Policy);5757  }5758 5759public:5760  void print(CFGTerminator T) {5761    switch (T.getKind()) {5762    case CFGTerminator::StmtBranch:5763      Visit(T.getStmt());5764      break;5765    case CFGTerminator::TemporaryDtorsBranch:5766      OS << "(Temp Dtor) ";5767      Visit(T.getStmt());5768      break;5769    case CFGTerminator::VirtualBaseBranch:5770      OS << "(See if most derived ctor has already initialized vbases)";5771      break;5772    }5773  }5774};5775 5776} // namespace5777 5778static void print_initializer(raw_ostream &OS, StmtPrinterHelper &Helper,5779                              const CXXCtorInitializer *I) {5780  if (I->isBaseInitializer())5781    OS << I->getBaseClass()->getAsCXXRecordDecl()->getName();5782  else if (I->isDelegatingInitializer())5783    OS << I->getTypeSourceInfo()->getType()->getAsCXXRecordDecl()->getName();5784  else5785    OS << I->getAnyMember()->getName();5786  OS << "(";5787  if (Expr *IE = I->getInit())5788    IE->printPretty(OS, &Helper, PrintingPolicy(Helper.getLangOpts()));5789  OS << ")";5790 5791  if (I->isBaseInitializer())5792    OS << " (Base initializer)";5793  else if (I->isDelegatingInitializer())5794    OS << " (Delegating initializer)";5795  else5796    OS << " (Member initializer)";5797}5798 5799static void print_construction_context(raw_ostream &OS,5800                                       StmtPrinterHelper &Helper,5801                                       const ConstructionContext *CC) {5802  SmallVector<const Stmt *, 3> Stmts;5803  switch (CC->getKind()) {5804  case ConstructionContext::SimpleConstructorInitializerKind: {5805    OS << ", ";5806    const auto *SICC = cast<SimpleConstructorInitializerConstructionContext>(CC);5807    print_initializer(OS, Helper, SICC->getCXXCtorInitializer());5808    return;5809  }5810  case ConstructionContext::CXX17ElidedCopyConstructorInitializerKind: {5811    OS << ", ";5812    const auto *CICC =5813        cast<CXX17ElidedCopyConstructorInitializerConstructionContext>(CC);5814    print_initializer(OS, Helper, CICC->getCXXCtorInitializer());5815    Stmts.push_back(CICC->getCXXBindTemporaryExpr());5816    break;5817  }5818  case ConstructionContext::SimpleVariableKind: {5819    const auto *SDSCC = cast<SimpleVariableConstructionContext>(CC);5820    Stmts.push_back(SDSCC->getDeclStmt());5821    break;5822  }5823  case ConstructionContext::CXX17ElidedCopyVariableKind: {5824    const auto *CDSCC = cast<CXX17ElidedCopyVariableConstructionContext>(CC);5825    Stmts.push_back(CDSCC->getDeclStmt());5826    Stmts.push_back(CDSCC->getCXXBindTemporaryExpr());5827    break;5828  }5829  case ConstructionContext::NewAllocatedObjectKind: {5830    const auto *NECC = cast<NewAllocatedObjectConstructionContext>(CC);5831    Stmts.push_back(NECC->getCXXNewExpr());5832    break;5833  }5834  case ConstructionContext::SimpleReturnedValueKind: {5835    const auto *RSCC = cast<SimpleReturnedValueConstructionContext>(CC);5836    Stmts.push_back(RSCC->getReturnStmt());5837    break;5838  }5839  case ConstructionContext::CXX17ElidedCopyReturnedValueKind: {5840    const auto *RSCC =5841        cast<CXX17ElidedCopyReturnedValueConstructionContext>(CC);5842    Stmts.push_back(RSCC->getReturnStmt());5843    Stmts.push_back(RSCC->getCXXBindTemporaryExpr());5844    break;5845  }5846  case ConstructionContext::SimpleTemporaryObjectKind: {5847    const auto *TOCC = cast<SimpleTemporaryObjectConstructionContext>(CC);5848    Stmts.push_back(TOCC->getCXXBindTemporaryExpr());5849    Stmts.push_back(TOCC->getMaterializedTemporaryExpr());5850    break;5851  }5852  case ConstructionContext::ElidedTemporaryObjectKind: {5853    const auto *TOCC = cast<ElidedTemporaryObjectConstructionContext>(CC);5854    Stmts.push_back(TOCC->getCXXBindTemporaryExpr());5855    Stmts.push_back(TOCC->getMaterializedTemporaryExpr());5856    Stmts.push_back(TOCC->getConstructorAfterElision());5857    break;5858  }5859  case ConstructionContext::LambdaCaptureKind: {5860    const auto *LCC = cast<LambdaCaptureConstructionContext>(CC);5861    Helper.handledStmt(const_cast<LambdaExpr *>(LCC->getLambdaExpr()), OS);5862    OS << "+" << LCC->getIndex();5863    return;5864  }5865  case ConstructionContext::ArgumentKind: {5866    const auto *ACC = cast<ArgumentConstructionContext>(CC);5867    if (const Stmt *BTE = ACC->getCXXBindTemporaryExpr()) {5868      OS << ", ";5869      Helper.handledStmt(const_cast<Stmt *>(BTE), OS);5870    }5871    OS << ", ";5872    Helper.handledStmt(const_cast<Expr *>(ACC->getCallLikeExpr()), OS);5873    OS << "+" << ACC->getIndex();5874    return;5875  }5876  }5877  for (auto I: Stmts)5878    if (I) {5879      OS << ", ";5880      Helper.handledStmt(const_cast<Stmt *>(I), OS);5881    }5882}5883 5884static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper,5885                       const CFGElement &E, bool TerminateWithNewLine = true);5886 5887void CFGElement::dumpToStream(llvm::raw_ostream &OS,5888                              bool TerminateWithNewLine) const {5889  LangOptions LangOpts;5890  StmtPrinterHelper Helper(nullptr, LangOpts);5891  print_elem(OS, Helper, *this, TerminateWithNewLine);5892}5893 5894static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper,5895                       const CFGElement &E, bool TerminateWithNewLine) {5896  switch (E.getKind()) {5897  case CFGElement::Kind::Statement:5898  case CFGElement::Kind::CXXRecordTypedCall:5899  case CFGElement::Kind::Constructor: {5900    CFGStmt CS = E.castAs<CFGStmt>();5901    const Stmt *S = CS.getStmt();5902    assert(S != nullptr && "Expecting non-null Stmt");5903 5904    // special printing for statement-expressions.5905    if (const StmtExpr *SE = dyn_cast<StmtExpr>(S)) {5906      const CompoundStmt *Sub = SE->getSubStmt();5907 5908      auto Children = Sub->children();5909      if (Children.begin() != Children.end()) {5910        OS << "({ ... ; ";5911        Helper.handledStmt(*SE->getSubStmt()->body_rbegin(),OS);5912        OS << " })";5913        if (TerminateWithNewLine)5914          OS << '\n';5915        return;5916      }5917    }5918    // special printing for comma expressions.5919    if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) {5920      if (B->getOpcode() == BO_Comma) {5921        OS << "... , ";5922        Helper.handledStmt(B->getRHS(),OS);5923        if (TerminateWithNewLine)5924          OS << '\n';5925        return;5926      }5927    }5928    S->printPretty(OS, &Helper, PrintingPolicy(Helper.getLangOpts()));5929 5930    if (auto VTC = E.getAs<CFGCXXRecordTypedCall>()) {5931      if (isa<CXXOperatorCallExpr>(S))5932        OS << " (OperatorCall)";5933      OS << " (CXXRecordTypedCall";5934      print_construction_context(OS, Helper, VTC->getConstructionContext());5935      OS << ")";5936    } else if (isa<CXXOperatorCallExpr>(S)) {5937      OS << " (OperatorCall)";5938    } else if (isa<CXXBindTemporaryExpr>(S)) {5939      OS << " (BindTemporary)";5940    } else if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(S)) {5941      OS << " (CXXConstructExpr";5942      if (std::optional<CFGConstructor> CE = E.getAs<CFGConstructor>()) {5943        print_construction_context(OS, Helper, CE->getConstructionContext());5944      }5945      OS << ", " << CCE->getType() << ")";5946    } else if (const CastExpr *CE = dyn_cast<CastExpr>(S)) {5947      OS << " (" << CE->getStmtClassName() << ", " << CE->getCastKindName()5948         << ", " << CE->getType() << ")";5949    }5950 5951    // Expressions need a newline.5952    if (isa<Expr>(S) && TerminateWithNewLine)5953      OS << '\n';5954 5955    return;5956  }5957 5958  case CFGElement::Kind::Initializer:5959    print_initializer(OS, Helper, E.castAs<CFGInitializer>().getInitializer());5960    break;5961 5962  case CFGElement::Kind::AutomaticObjectDtor: {5963    CFGAutomaticObjDtor DE = E.castAs<CFGAutomaticObjDtor>();5964    const VarDecl *VD = DE.getVarDecl();5965    Helper.handleDecl(VD, OS);5966 5967    QualType T = VD->getType();5968    if (T->isReferenceType())5969      T = getReferenceInitTemporaryType(VD->getInit(), nullptr);5970 5971    OS << ".~";5972    T.getUnqualifiedType().print(OS, PrintingPolicy(Helper.getLangOpts()));5973    OS << "() (Implicit destructor)";5974    break;5975  }5976 5977  case CFGElement::Kind::CleanupFunction:5978    OS << "CleanupFunction ("5979       << E.castAs<CFGCleanupFunction>().getFunctionDecl()->getName() << ")";5980    break;5981 5982  case CFGElement::Kind::LifetimeEnds:5983    Helper.handleDecl(E.castAs<CFGLifetimeEnds>().getVarDecl(), OS);5984    OS << " (Lifetime ends)";5985    break;5986 5987  case CFGElement::Kind::LoopExit:5988    OS << E.castAs<CFGLoopExit>().getLoopStmt()->getStmtClassName()5989       << " (LoopExit)";5990    break;5991 5992  case CFGElement::Kind::ScopeBegin:5993    OS << "CFGScopeBegin(";5994    if (const VarDecl *VD = E.castAs<CFGScopeBegin>().getVarDecl())5995      OS << VD->getQualifiedNameAsString();5996    OS << ")";5997    break;5998 5999  case CFGElement::Kind::ScopeEnd:6000    OS << "CFGScopeEnd(";6001    if (const VarDecl *VD = E.castAs<CFGScopeEnd>().getVarDecl())6002      OS << VD->getQualifiedNameAsString();6003    OS << ")";6004    break;6005 6006  case CFGElement::Kind::NewAllocator:6007    OS << "CFGNewAllocator(";6008    if (const CXXNewExpr *AllocExpr = E.castAs<CFGNewAllocator>().getAllocatorExpr())6009      AllocExpr->getType().print(OS, PrintingPolicy(Helper.getLangOpts()));6010    OS << ")";6011    break;6012 6013  case CFGElement::Kind::DeleteDtor: {6014    CFGDeleteDtor DE = E.castAs<CFGDeleteDtor>();6015    const CXXRecordDecl *RD = DE.getCXXRecordDecl();6016    if (!RD)6017      return;6018    CXXDeleteExpr *DelExpr =6019        const_cast<CXXDeleteExpr*>(DE.getDeleteExpr());6020    Helper.handledStmt(cast<Stmt>(DelExpr->getArgument()), OS);6021    OS << "->~" << RD->getName().str() << "()";6022    OS << " (Implicit destructor)";6023    break;6024  }6025 6026  case CFGElement::Kind::BaseDtor: {6027    const CXXBaseSpecifier *BS = E.castAs<CFGBaseDtor>().getBaseSpecifier();6028    OS << "~" << BS->getType()->getAsCXXRecordDecl()->getName() << "()";6029    OS << " (Base object destructor)";6030    break;6031  }6032 6033  case CFGElement::Kind::MemberDtor: {6034    const FieldDecl *FD = E.castAs<CFGMemberDtor>().getFieldDecl();6035    const Type *T = FD->getType()->getBaseElementTypeUnsafe();6036    OS << "this->" << FD->getName();6037    OS << ".~" << T->getAsCXXRecordDecl()->getName() << "()";6038    OS << " (Member object destructor)";6039    break;6040  }6041 6042  case CFGElement::Kind::TemporaryDtor: {6043    const CXXBindTemporaryExpr *BT =6044        E.castAs<CFGTemporaryDtor>().getBindTemporaryExpr();6045    OS << "~";6046    BT->getType().print(OS, PrintingPolicy(Helper.getLangOpts()));6047    OS << "() (Temporary object destructor)";6048    break;6049  }6050  }6051  if (TerminateWithNewLine)6052    OS << '\n';6053}6054 6055static void print_block(raw_ostream &OS, const CFG* cfg,6056                        const CFGBlock &B,6057                        StmtPrinterHelper &Helper, bool print_edges,6058                        bool ShowColors) {6059  Helper.setBlockID(B.getBlockID());6060 6061  // Print the header.6062  if (ShowColors)6063    OS.changeColor(raw_ostream::YELLOW, true);6064 6065  OS << "\n [B" << B.getBlockID();6066 6067  if (&B == &cfg->getEntry())6068    OS << " (ENTRY)]\n";6069  else if (&B == &cfg->getExit())6070    OS << " (EXIT)]\n";6071  else if (&B == cfg->getIndirectGotoBlock())6072    OS << " (INDIRECT GOTO DISPATCH)]\n";6073  else if (B.hasNoReturnElement())6074    OS << " (NORETURN)]\n";6075  else6076    OS << "]\n";6077 6078  if (ShowColors)6079    OS.resetColor();6080 6081  // Print the label of this block.6082  if (Stmt *Label = const_cast<Stmt*>(B.getLabel())) {6083    if (print_edges)6084      OS << "  ";6085 6086    if (LabelStmt *L = dyn_cast<LabelStmt>(Label))6087      OS << L->getName();6088    else if (CaseStmt *C = dyn_cast<CaseStmt>(Label)) {6089      OS << "case ";6090      if (const Expr *LHS = C->getLHS())6091        LHS->printPretty(OS, &Helper, PrintingPolicy(Helper.getLangOpts()));6092      if (const Expr *RHS = C->getRHS()) {6093        OS << " ... ";6094        RHS->printPretty(OS, &Helper, PrintingPolicy(Helper.getLangOpts()));6095      }6096    } else if (isa<DefaultStmt>(Label))6097      OS << "default";6098    else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Label)) {6099      OS << "catch (";6100      if (const VarDecl *ED = CS->getExceptionDecl())6101        ED->print(OS, PrintingPolicy(Helper.getLangOpts()), 0);6102      else6103        OS << "...";6104      OS << ")";6105    } else if (ObjCAtCatchStmt *CS = dyn_cast<ObjCAtCatchStmt>(Label)) {6106      OS << "@catch (";6107      if (const VarDecl *PD = CS->getCatchParamDecl())6108        PD->print(OS, PrintingPolicy(Helper.getLangOpts()), 0);6109      else6110        OS << "...";6111      OS << ")";6112    } else if (SEHExceptStmt *ES = dyn_cast<SEHExceptStmt>(Label)) {6113      OS << "__except (";6114      ES->getFilterExpr()->printPretty(OS, &Helper,6115                                       PrintingPolicy(Helper.getLangOpts()), 0);6116      OS << ")";6117    } else6118      llvm_unreachable("Invalid label statement in CFGBlock.");6119 6120    OS << ":\n";6121  }6122 6123  // Iterate through the statements in the block and print them.6124  unsigned j = 1;6125 6126  for (CFGBlock::const_iterator I = B.begin(), E = B.end() ;6127       I != E ; ++I, ++j ) {6128    // Print the statement # in the basic block and the statement itself.6129    if (print_edges)6130      OS << " ";6131 6132    OS << llvm::format("%3d", j) << ": ";6133 6134    Helper.setStmtID(j);6135 6136    print_elem(OS, Helper, *I);6137  }6138 6139  // Print the terminator of this block.6140  if (B.getTerminator().isValid()) {6141    if (ShowColors)6142      OS.changeColor(raw_ostream::GREEN);6143 6144    OS << "   T: ";6145 6146    Helper.setBlockID(-1);6147 6148    PrintingPolicy PP(Helper.getLangOpts());6149    CFGBlockTerminatorPrint TPrinter(OS, &Helper, PP);6150    TPrinter.print(B.getTerminator());6151    OS << '\n';6152 6153    if (ShowColors)6154      OS.resetColor();6155  }6156 6157  if (print_edges) {6158    // Print the predecessors of this block.6159    if (!B.pred_empty()) {6160      const raw_ostream::Colors Color = raw_ostream::BLUE;6161      if (ShowColors)6162        OS.changeColor(Color);6163      OS << "   Preds " ;6164      if (ShowColors)6165        OS.resetColor();6166      OS << '(' << B.pred_size() << "):";6167      unsigned i = 0;6168 6169      if (ShowColors)6170        OS.changeColor(Color);6171 6172      for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end();6173           I != E; ++I, ++i) {6174        if (i % 10 == 8)6175          OS << "\n     ";6176 6177        CFGBlock *B = *I;6178        bool Reachable = true;6179        if (!B) {6180          Reachable = false;6181          B = I->getPossiblyUnreachableBlock();6182        }6183 6184        OS << " B" << B->getBlockID();6185        if (!Reachable)6186          OS << "(Unreachable)";6187      }6188 6189      if (ShowColors)6190        OS.resetColor();6191 6192      OS << '\n';6193    }6194 6195    // Print the successors of this block.6196    if (!B.succ_empty()) {6197      const raw_ostream::Colors Color = raw_ostream::MAGENTA;6198      if (ShowColors)6199        OS.changeColor(Color);6200      OS << "   Succs ";6201      if (ShowColors)6202        OS.resetColor();6203      OS << '(' << B.succ_size() << "):";6204      unsigned i = 0;6205 6206      if (ShowColors)6207        OS.changeColor(Color);6208 6209      for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end();6210           I != E; ++I, ++i) {6211        if (i % 10 == 8)6212          OS << "\n    ";6213 6214        CFGBlock *B = *I;6215 6216        bool Reachable = true;6217        if (!B) {6218          Reachable = false;6219          B = I->getPossiblyUnreachableBlock();6220        }6221 6222        if (B) {6223          OS << " B" << B->getBlockID();6224          if (!Reachable)6225            OS << "(Unreachable)";6226        }6227        else {6228          OS << " NULL";6229        }6230      }6231 6232      if (ShowColors)6233        OS.resetColor();6234      OS << '\n';6235    }6236  }6237}6238 6239/// dump - A simple pretty printer of a CFG that outputs to stderr.6240void CFG::dump(const LangOptions &LO, bool ShowColors) const {6241  print(llvm::errs(), LO, ShowColors);6242}6243 6244/// print - A simple pretty printer of a CFG that outputs to an ostream.6245void CFG::print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const {6246  StmtPrinterHelper Helper(this, LO);6247 6248  // Print the entry block.6249  print_block(OS, this, getEntry(), Helper, true, ShowColors);6250 6251  // Iterate through the CFGBlocks and print them one by one.6252  for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) {6253    // Skip the entry block, because we already printed it.6254    if (&(**I) == &getEntry() || &(**I) == &getExit())6255      continue;6256 6257    print_block(OS, this, **I, Helper, true, ShowColors);6258  }6259 6260  // Print the exit block.6261  print_block(OS, this, getExit(), Helper, true, ShowColors);6262  OS << '\n';6263  OS.flush();6264}6265 6266size_t CFGBlock::getIndexInCFG() const {6267  return llvm::find(*getParent(), this) - getParent()->begin();6268}6269 6270/// dump - A simply pretty printer of a CFGBlock that outputs to stderr.6271void CFGBlock::dump(const CFG* cfg, const LangOptions &LO,6272                    bool ShowColors) const {6273  print(llvm::errs(), cfg, LO, ShowColors);6274}6275 6276LLVM_DUMP_METHOD void CFGBlock::dump() const {6277  dump(getParent(), LangOptions(), false);6278}6279 6280/// print - A simple pretty printer of a CFGBlock that outputs to an ostream.6281///   Generally this will only be called from CFG::print.6282void CFGBlock::print(raw_ostream &OS, const CFG* cfg,6283                     const LangOptions &LO, bool ShowColors) const {6284  StmtPrinterHelper Helper(cfg, LO);6285  print_block(OS, cfg, *this, Helper, true, ShowColors);6286  OS << '\n';6287}6288 6289/// printTerminator - A simple pretty printer of the terminator of a CFGBlock.6290void CFGBlock::printTerminator(raw_ostream &OS,6291                               const LangOptions &LO) const {6292  CFGBlockTerminatorPrint TPrinter(OS, nullptr, PrintingPolicy(LO));6293  TPrinter.print(getTerminator());6294}6295 6296/// printTerminatorJson - Pretty-prints the terminator in JSON format.6297void CFGBlock::printTerminatorJson(raw_ostream &Out, const LangOptions &LO,6298                                   bool AddQuotes) const {6299  std::string Buf;6300  llvm::raw_string_ostream TempOut(Buf);6301 6302  printTerminator(TempOut, LO);6303 6304  Out << JsonFormat(Buf, AddQuotes);6305}6306 6307// Returns true if by simply looking at the block, we can be sure that it6308// results in a sink during analysis. This is useful to know when the analysis6309// was interrupted, and we try to figure out if it would sink eventually.6310// There may be many more reasons why a sink would appear during analysis6311// (eg. checkers may generate sinks arbitrarily), but here we only consider6312// sinks that would be obvious by looking at the CFG.6313static bool isImmediateSinkBlock(const CFGBlock *Blk) {6314  if (Blk->hasNoReturnElement())6315    return true;6316 6317  // FIXME: Throw-expressions are currently generating sinks during analysis:6318  // they're not supported yet, and also often used for actually terminating6319  // the program. So we should treat them as sinks in this analysis as well,6320  // at least for now, but once we have better support for exceptions,6321  // we'd need to carefully handle the case when the throw is being6322  // immediately caught.6323  if (llvm::any_of(*Blk, [](const CFGElement &Elm) {6324        if (std::optional<CFGStmt> StmtElm = Elm.getAs<CFGStmt>())6325          if (isa<CXXThrowExpr>(StmtElm->getStmt()))6326            return true;6327        return false;6328      }))6329    return true;6330 6331  return false;6332}6333 6334bool CFGBlock::isInevitablySinking() const {6335  const CFG &Cfg = *getParent();6336 6337  const CFGBlock *StartBlk = this;6338  if (isImmediateSinkBlock(StartBlk))6339    return true;6340 6341  llvm::SmallVector<const CFGBlock *, 32> DFSWorkList;6342  llvm::SmallPtrSet<const CFGBlock *, 32> Visited;6343 6344  DFSWorkList.push_back(StartBlk);6345  while (!DFSWorkList.empty()) {6346    const CFGBlock *Blk = DFSWorkList.pop_back_val();6347    Visited.insert(Blk);6348 6349    // If at least one path reaches the CFG exit, it means that control is6350    // returned to the caller. For now, say that we are not sure what6351    // happens next. If necessary, this can be improved to analyze6352    // the parent StackFrameContext's call site in a similar manner.6353    if (Blk == &Cfg.getExit())6354      return false;6355 6356    for (const auto &Succ : Blk->succs()) {6357      if (const CFGBlock *SuccBlk = Succ.getReachableBlock()) {6358        if (!isImmediateSinkBlock(SuccBlk) && !Visited.count(SuccBlk)) {6359          // If the block has reachable child blocks that aren't no-return,6360          // add them to the worklist.6361          DFSWorkList.push_back(SuccBlk);6362        }6363      }6364    }6365  }6366 6367  // Nothing reached the exit. It can only mean one thing: there's no return.6368  return true;6369}6370 6371const Expr *CFGBlock::getLastCondition() const {6372  // If the terminator is a temporary dtor or a virtual base, etc, we can't6373  // retrieve a meaningful condition, bail out.6374  if (Terminator.getKind() != CFGTerminator::StmtBranch)6375    return nullptr;6376 6377  // Also, if this method was called on a block that doesn't have 2 successors,6378  // this block doesn't have retrievable condition.6379  if (succ_size() < 2)6380    return nullptr;6381 6382  // FIXME: Is there a better condition expression we can return in this case?6383  if (size() == 0)6384    return nullptr;6385 6386  auto StmtElem = rbegin()->getAs<CFGStmt>();6387  if (!StmtElem)6388    return nullptr;6389 6390  const Stmt *Cond = StmtElem->getStmt();6391  if (isa<ObjCForCollectionStmt>(Cond) || isa<DeclStmt>(Cond))6392    return nullptr;6393 6394  // Only ObjCForCollectionStmt is known not to be a non-Expr terminator, hence6395  // the cast<>.6396  return cast<Expr>(Cond)->IgnoreParens();6397}6398 6399Stmt *CFGBlock::getTerminatorCondition(bool StripParens) {6400  Stmt *Terminator = getTerminatorStmt();6401  if (!Terminator)6402    return nullptr;6403 6404  Expr *E = nullptr;6405 6406  switch (Terminator->getStmtClass()) {6407    default:6408      break;6409 6410    case Stmt::CXXForRangeStmtClass:6411      E = cast<CXXForRangeStmt>(Terminator)->getCond();6412      break;6413 6414    case Stmt::ForStmtClass:6415      E = cast<ForStmt>(Terminator)->getCond();6416      break;6417 6418    case Stmt::WhileStmtClass:6419      E = cast<WhileStmt>(Terminator)->getCond();6420      break;6421 6422    case Stmt::DoStmtClass:6423      E = cast<DoStmt>(Terminator)->getCond();6424      break;6425 6426    case Stmt::IfStmtClass:6427      E = cast<IfStmt>(Terminator)->getCond();6428      break;6429 6430    case Stmt::ChooseExprClass:6431      E = cast<ChooseExpr>(Terminator)->getCond();6432      break;6433 6434    case Stmt::IndirectGotoStmtClass:6435      E = cast<IndirectGotoStmt>(Terminator)->getTarget();6436      break;6437 6438    case Stmt::SwitchStmtClass:6439      E = cast<SwitchStmt>(Terminator)->getCond();6440      break;6441 6442    case Stmt::BinaryConditionalOperatorClass:6443      E = cast<BinaryConditionalOperator>(Terminator)->getCond();6444      break;6445 6446    case Stmt::ConditionalOperatorClass:6447      E = cast<ConditionalOperator>(Terminator)->getCond();6448      break;6449 6450    case Stmt::BinaryOperatorClass: // '&&' and '||'6451      E = cast<BinaryOperator>(Terminator)->getLHS();6452      break;6453 6454    case Stmt::ObjCForCollectionStmtClass:6455      return Terminator;6456  }6457 6458  if (!StripParens)6459    return E;6460 6461  return E ? E->IgnoreParens() : nullptr;6462}6463 6464//===----------------------------------------------------------------------===//6465// CFG Graphviz Visualization6466//===----------------------------------------------------------------------===//6467 6468static StmtPrinterHelper *GraphHelper;6469 6470void CFG::viewCFG(const LangOptions &LO) const {6471  StmtPrinterHelper H(this, LO);6472  GraphHelper = &H;6473  llvm::ViewGraph(this,"CFG");6474  GraphHelper = nullptr;6475}6476 6477namespace llvm {6478 6479template<>6480struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits {6481  DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}6482 6483  static std::string getNodeLabel(const CFGBlock *Node, const CFG *Graph) {6484    std::string OutStr;6485    llvm::raw_string_ostream Out(OutStr);6486    print_block(Out,Graph, *Node, *GraphHelper, false, false);6487 6488    if (OutStr[0] == '\n') OutStr.erase(OutStr.begin());6489 6490    // Process string output to make it nicer...6491    for (unsigned i = 0; i != OutStr.length(); ++i)6492      if (OutStr[i] == '\n') {                            // Left justify6493        OutStr[i] = '\\';6494        OutStr.insert(OutStr.begin()+i+1, 'l');6495      }6496 6497    return OutStr;6498  }6499};6500 6501} // namespace llvm6502