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