1 //===--- CFG.cpp - Classes for representing and building CFGs----*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file defines the CFG and CFGBuilder classes for representing and 11 // building Control-Flow Graphs (CFGs) from ASTs. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #include "clang/Analysis/CFG.h" 16 #include "clang/AST/ASTContext.h" 17 #include "clang/AST/Attr.h" 18 #include "clang/AST/CharUnits.h" 19 #include "clang/AST/DeclCXX.h" 20 #include "clang/AST/PrettyPrinter.h" 21 #include "clang/AST/StmtVisitor.h" 22 #include "clang/Basic/Builtins.h" 23 #include "llvm/ADT/DenseMap.h" 24 #include <memory> 25 #include "llvm/ADT/SmallPtrSet.h" 26 #include "llvm/Support/Allocator.h" 27 #include "llvm/Support/Format.h" 28 #include "llvm/Support/GraphWriter.h" 29 #include "llvm/Support/SaveAndRestore.h" 30 31 using namespace clang; 32 33 namespace { 34 35 static SourceLocation GetEndLoc(Decl *D) { 36 if (VarDecl *VD = dyn_cast<VarDecl>(D)) 37 if (Expr *Ex = VD->getInit()) 38 return Ex->getSourceRange().getEnd(); 39 return D->getLocation(); 40 } 41 42 class CFGBuilder; 43 44 /// The CFG builder uses a recursive algorithm to build the CFG. When 45 /// we process an expression, sometimes we know that we must add the 46 /// subexpressions as block-level expressions. For example: 47 /// 48 /// exp1 || exp2 49 /// 50 /// When processing the '||' expression, we know that exp1 and exp2 51 /// need to be added as block-level expressions, even though they 52 /// might not normally need to be. AddStmtChoice records this 53 /// contextual information. If AddStmtChoice is 'NotAlwaysAdd', then 54 /// the builder has an option not to add a subexpression as a 55 /// block-level expression. 56 /// 57 class AddStmtChoice { 58 public: 59 enum Kind { NotAlwaysAdd = 0, AlwaysAdd = 1 }; 60 61 AddStmtChoice(Kind a_kind = NotAlwaysAdd) : kind(a_kind) {} 62 63 bool alwaysAdd(CFGBuilder &builder, 64 const Stmt *stmt) const; 65 66 /// Return a copy of this object, except with the 'always-add' bit 67 /// set as specified. 68 AddStmtChoice withAlwaysAdd(bool alwaysAdd) const { 69 return AddStmtChoice(alwaysAdd ? AlwaysAdd : NotAlwaysAdd); 70 } 71 72 private: 73 Kind kind; 74 }; 75 76 /// LocalScope - Node in tree of local scopes created for C++ implicit 77 /// destructor calls generation. It contains list of automatic variables 78 /// declared in the scope and link to position in previous scope this scope 79 /// began in. 80 /// 81 /// The process of creating local scopes is as follows: 82 /// - Init CFGBuilder::ScopePos with invalid position (equivalent for null), 83 /// - Before processing statements in scope (e.g. CompoundStmt) create 84 /// LocalScope object using CFGBuilder::ScopePos as link to previous scope 85 /// and set CFGBuilder::ScopePos to the end of new scope, 86 /// - On every occurrence of VarDecl increase CFGBuilder::ScopePos if it points 87 /// at this VarDecl, 88 /// - For every normal (without jump) end of scope add to CFGBlock destructors 89 /// for objects in the current scope, 90 /// - For every jump add to CFGBlock destructors for objects 91 /// between CFGBuilder::ScopePos and local scope position saved for jump 92 /// target. Thanks to C++ restrictions on goto jumps we can be sure that 93 /// jump target position will be on the path to root from CFGBuilder::ScopePos 94 /// (adding any variable that doesn't need constructor to be called to 95 /// LocalScope can break this assumption), 96 /// 97 class LocalScope { 98 public: 99 typedef BumpVector<VarDecl*> AutomaticVarsTy; 100 101 /// const_iterator - Iterates local scope backwards and jumps to previous 102 /// scope on reaching the beginning of currently iterated scope. 103 class const_iterator { 104 const LocalScope* Scope; 105 106 /// VarIter is guaranteed to be greater then 0 for every valid iterator. 107 /// Invalid iterator (with null Scope) has VarIter equal to 0. 108 unsigned VarIter; 109 110 public: 111 /// Create invalid iterator. Dereferencing invalid iterator is not allowed. 112 /// Incrementing invalid iterator is allowed and will result in invalid 113 /// iterator. 114 const_iterator() 115 : Scope(nullptr), VarIter(0) {} 116 117 /// Create valid iterator. In case when S.Prev is an invalid iterator and 118 /// I is equal to 0, this will create invalid iterator. 119 const_iterator(const LocalScope& S, unsigned I) 120 : Scope(&S), VarIter(I) { 121 // Iterator to "end" of scope is not allowed. Handle it by going up 122 // in scopes tree possibly up to invalid iterator in the root. 123 if (VarIter == 0 && Scope) 124 *this = Scope->Prev; 125 } 126 127 VarDecl *const* operator->() const { 128 assert (Scope && "Dereferencing invalid iterator is not allowed"); 129 assert (VarIter != 0 && "Iterator has invalid value of VarIter member"); 130 return &Scope->Vars[VarIter - 1]; 131 } 132 VarDecl *operator*() const { 133 return *this->operator->(); 134 } 135 136 const_iterator &operator++() { 137 if (!Scope) 138 return *this; 139 140 assert (VarIter != 0 && "Iterator has invalid value of VarIter member"); 141 --VarIter; 142 if (VarIter == 0) 143 *this = Scope->Prev; 144 return *this; 145 } 146 const_iterator operator++(int) { 147 const_iterator P = *this; 148 ++*this; 149 return P; 150 } 151 152 bool operator==(const const_iterator &rhs) const { 153 return Scope == rhs.Scope && VarIter == rhs.VarIter; 154 } 155 bool operator!=(const const_iterator &rhs) const { 156 return !(*this == rhs); 157 } 158 159 explicit operator bool() const { 160 return *this != const_iterator(); 161 } 162 163 int distance(const_iterator L); 164 }; 165 166 friend class const_iterator; 167 168 private: 169 BumpVectorContext ctx; 170 171 /// Automatic variables in order of declaration. 172 AutomaticVarsTy Vars; 173 /// Iterator to variable in previous scope that was declared just before 174 /// begin of this scope. 175 const_iterator Prev; 176 177 public: 178 /// Constructs empty scope linked to previous scope in specified place. 179 LocalScope(BumpVectorContext &ctx, const_iterator P) 180 : ctx(ctx), Vars(ctx, 4), Prev(P) {} 181 182 /// Begin of scope in direction of CFG building (backwards). 183 const_iterator begin() const { return const_iterator(*this, Vars.size()); } 184 185 void addVar(VarDecl *VD) { 186 Vars.push_back(VD, ctx); 187 } 188 }; 189 190 /// distance - Calculates distance from this to L. L must be reachable from this 191 /// (with use of ++ operator). Cost of calculating the distance is linear w.r.t. 192 /// number of scopes between this and L. 193 int LocalScope::const_iterator::distance(LocalScope::const_iterator L) { 194 int D = 0; 195 const_iterator F = *this; 196 while (F.Scope != L.Scope) { 197 assert (F != const_iterator() 198 && "L iterator is not reachable from F iterator."); 199 D += F.VarIter; 200 F = F.Scope->Prev; 201 } 202 D += F.VarIter - L.VarIter; 203 return D; 204 } 205 206 /// BlockScopePosPair - Structure for specifying position in CFG during its 207 /// build process. It consists of CFGBlock that specifies position in CFG graph 208 /// and LocalScope::const_iterator that specifies position in LocalScope graph. 209 struct BlockScopePosPair { 210 BlockScopePosPair() : block(nullptr) {} 211 BlockScopePosPair(CFGBlock *b, LocalScope::const_iterator scopePos) 212 : block(b), scopePosition(scopePos) {} 213 214 CFGBlock *block; 215 LocalScope::const_iterator scopePosition; 216 }; 217 218 /// TryResult - a class representing a variant over the values 219 /// 'true', 'false', or 'unknown'. This is returned by tryEvaluateBool, 220 /// and is used by the CFGBuilder to decide if a branch condition 221 /// can be decided up front during CFG construction. 222 class TryResult { 223 int X; 224 public: 225 TryResult(bool b) : X(b ? 1 : 0) {} 226 TryResult() : X(-1) {} 227 228 bool isTrue() const { return X == 1; } 229 bool isFalse() const { return X == 0; } 230 bool isKnown() const { return X >= 0; } 231 void negate() { 232 assert(isKnown()); 233 X ^= 0x1; 234 } 235 }; 236 237 TryResult bothKnownTrue(TryResult R1, TryResult R2) { 238 if (!R1.isKnown() || !R2.isKnown()) 239 return TryResult(); 240 return TryResult(R1.isTrue() && R2.isTrue()); 241 } 242 243 class reverse_children { 244 llvm::SmallVector<Stmt *, 12> childrenBuf; 245 ArrayRef<Stmt*> children; 246 public: 247 reverse_children(Stmt *S); 248 249 typedef ArrayRef<Stmt*>::reverse_iterator iterator; 250 iterator begin() const { return children.rbegin(); } 251 iterator end() const { return children.rend(); } 252 }; 253 254 255 reverse_children::reverse_children(Stmt *S) { 256 if (CallExpr *CE = dyn_cast<CallExpr>(S)) { 257 children = CE->getRawSubExprs(); 258 return; 259 } 260 switch (S->getStmtClass()) { 261 // Note: Fill in this switch with more cases we want to optimize. 262 case Stmt::InitListExprClass: { 263 InitListExpr *IE = cast<InitListExpr>(S); 264 children = llvm::makeArrayRef(reinterpret_cast<Stmt**>(IE->getInits()), 265 IE->getNumInits()); 266 return; 267 } 268 default: 269 break; 270 } 271 272 // Default case for all other statements. 273 for (Stmt::child_range I = S->children(); I; ++I) { 274 childrenBuf.push_back(*I); 275 } 276 277 // This needs to be done *after* childrenBuf has been populated. 278 children = childrenBuf; 279 } 280 281 /// CFGBuilder - This class implements CFG construction from an AST. 282 /// The builder is stateful: an instance of the builder should be used to only 283 /// construct a single CFG. 284 /// 285 /// Example usage: 286 /// 287 /// CFGBuilder builder; 288 /// CFG* cfg = builder.BuildAST(stmt1); 289 /// 290 /// CFG construction is done via a recursive walk of an AST. We actually parse 291 /// the AST in reverse order so that the successor of a basic block is 292 /// constructed prior to its predecessor. This allows us to nicely capture 293 /// implicit fall-throughs without extra basic blocks. 294 /// 295 class CFGBuilder { 296 typedef BlockScopePosPair JumpTarget; 297 typedef BlockScopePosPair JumpSource; 298 299 ASTContext *Context; 300 std::unique_ptr<CFG> cfg; 301 302 CFGBlock *Block; 303 CFGBlock *Succ; 304 JumpTarget ContinueJumpTarget; 305 JumpTarget BreakJumpTarget; 306 CFGBlock *SwitchTerminatedBlock; 307 CFGBlock *DefaultCaseBlock; 308 CFGBlock *TryTerminatedBlock; 309 310 // Current position in local scope. 311 LocalScope::const_iterator ScopePos; 312 313 // LabelMap records the mapping from Label expressions to their jump targets. 314 typedef llvm::DenseMap<LabelDecl*, JumpTarget> LabelMapTy; 315 LabelMapTy LabelMap; 316 317 // A list of blocks that end with a "goto" that must be backpatched to their 318 // resolved targets upon completion of CFG construction. 319 typedef std::vector<JumpSource> BackpatchBlocksTy; 320 BackpatchBlocksTy BackpatchBlocks; 321 322 // A list of labels whose address has been taken (for indirect gotos). 323 typedef llvm::SmallPtrSet<LabelDecl*, 5> LabelSetTy; 324 LabelSetTy AddressTakenLabels; 325 326 bool badCFG; 327 const CFG::BuildOptions &BuildOpts; 328 329 // State to track for building switch statements. 330 bool switchExclusivelyCovered; 331 Expr::EvalResult *switchCond; 332 333 CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry; 334 const Stmt *lastLookup; 335 336 // Caches boolean evaluations of expressions to avoid multiple re-evaluations 337 // during construction of branches for chained logical operators. 338 typedef llvm::DenseMap<Expr *, TryResult> CachedBoolEvalsTy; 339 CachedBoolEvalsTy CachedBoolEvals; 340 341 public: 342 explicit CFGBuilder(ASTContext *astContext, 343 const CFG::BuildOptions &buildOpts) 344 : Context(astContext), cfg(new CFG()), // crew a new CFG 345 Block(nullptr), Succ(nullptr), 346 SwitchTerminatedBlock(nullptr), DefaultCaseBlock(nullptr), 347 TryTerminatedBlock(nullptr), badCFG(false), BuildOpts(buildOpts), 348 switchExclusivelyCovered(false), switchCond(nullptr), 349 cachedEntry(nullptr), lastLookup(nullptr) {} 350 351 // buildCFG - Used by external clients to construct the CFG. 352 std::unique_ptr<CFG> buildCFG(const Decl *D, Stmt *Statement); 353 354 bool alwaysAdd(const Stmt *stmt); 355 356 private: 357 // Visitors to walk an AST and construct the CFG. 358 CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc); 359 CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc); 360 CFGBlock *VisitBreakStmt(BreakStmt *B); 361 CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc); 362 CFGBlock *VisitCaseStmt(CaseStmt *C); 363 CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc); 364 CFGBlock *VisitCompoundStmt(CompoundStmt *C); 365 CFGBlock *VisitConditionalOperator(AbstractConditionalOperator *C, 366 AddStmtChoice asc); 367 CFGBlock *VisitContinueStmt(ContinueStmt *C); 368 CFGBlock *VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E, 369 AddStmtChoice asc); 370 CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S); 371 CFGBlock *VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc); 372 CFGBlock *VisitCXXNewExpr(CXXNewExpr *DE, AddStmtChoice asc); 373 CFGBlock *VisitCXXDeleteExpr(CXXDeleteExpr *DE, AddStmtChoice asc); 374 CFGBlock *VisitCXXForRangeStmt(CXXForRangeStmt *S); 375 CFGBlock *VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E, 376 AddStmtChoice asc); 377 CFGBlock *VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C, 378 AddStmtChoice asc); 379 CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T); 380 CFGBlock *VisitCXXTryStmt(CXXTryStmt *S); 381 CFGBlock *VisitDeclStmt(DeclStmt *DS); 382 CFGBlock *VisitDeclSubExpr(DeclStmt *DS); 383 CFGBlock *VisitDefaultStmt(DefaultStmt *D); 384 CFGBlock *VisitDoStmt(DoStmt *D); 385 CFGBlock *VisitExprWithCleanups(ExprWithCleanups *E, AddStmtChoice asc); 386 CFGBlock *VisitForStmt(ForStmt *F); 387 CFGBlock *VisitGotoStmt(GotoStmt *G); 388 CFGBlock *VisitIfStmt(IfStmt *I); 389 CFGBlock *VisitImplicitCastExpr(ImplicitCastExpr *E, AddStmtChoice asc); 390 CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I); 391 CFGBlock *VisitLabelStmt(LabelStmt *L); 392 CFGBlock *VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc); 393 CFGBlock *VisitLogicalOperator(BinaryOperator *B); 394 std::pair<CFGBlock *, CFGBlock *> VisitLogicalOperator(BinaryOperator *B, 395 Stmt *Term, 396 CFGBlock *TrueBlock, 397 CFGBlock *FalseBlock); 398 CFGBlock *VisitMemberExpr(MemberExpr *M, AddStmtChoice asc); 399 CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S); 400 CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S); 401 CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S); 402 CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S); 403 CFGBlock *VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S); 404 CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S); 405 CFGBlock *VisitPseudoObjectExpr(PseudoObjectExpr *E); 406 CFGBlock *VisitReturnStmt(ReturnStmt *R); 407 CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc); 408 CFGBlock *VisitSwitchStmt(SwitchStmt *S); 409 CFGBlock *VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E, 410 AddStmtChoice asc); 411 CFGBlock *VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc); 412 CFGBlock *VisitWhileStmt(WhileStmt *W); 413 414 CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd); 415 CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc); 416 CFGBlock *VisitChildren(Stmt *S); 417 CFGBlock *VisitNoRecurse(Expr *E, AddStmtChoice asc); 418 419 /// When creating the CFG for temporary destructors, we want to mirror the 420 /// branch structure of the corresponding constructor calls. 421 /// Thus, while visiting a statement for temporary destructors, we keep a 422 /// context to keep track of the following information: 423 /// - whether a subexpression is executed unconditionally 424 /// - if a subexpression is executed conditionally, the first 425 /// CXXBindTemporaryExpr we encounter in that subexpression (which 426 /// corresponds to the last temporary destructor we have to call for this 427 /// subexpression) and the CFG block at that point (which will become the 428 /// successor block when inserting the decision point). 429 /// 430 /// That way, we can build the branch structure for temporary destructors as 431 /// follows: 432 /// 1. If a subexpression is executed unconditionally, we add the temporary 433 /// destructor calls to the current block. 434 /// 2. If a subexpression is executed conditionally, when we encounter a 435 /// CXXBindTemporaryExpr: 436 /// a) If it is the first temporary destructor call in the subexpression, 437 /// we remember the CXXBindTemporaryExpr and the current block in the 438 /// TempDtorContext; we start a new block, and insert the temporary 439 /// destructor call. 440 /// b) Otherwise, add the temporary destructor call to the current block. 441 /// 3. When we finished visiting a conditionally executed subexpression, 442 /// and we found at least one temporary constructor during the visitation 443 /// (2.a has executed), we insert a decision block that uses the 444 /// CXXBindTemporaryExpr as terminator, and branches to the current block 445 /// if the CXXBindTemporaryExpr was marked executed, and otherwise 446 /// branches to the stored successor. 447 struct TempDtorContext { 448 TempDtorContext() 449 : IsConditional(false), KnownExecuted(true), Succ(nullptr), 450 TerminatorExpr(nullptr) {} 451 452 TempDtorContext(TryResult KnownExecuted) 453 : IsConditional(true), KnownExecuted(KnownExecuted), Succ(nullptr), 454 TerminatorExpr(nullptr) {} 455 456 /// Returns whether we need to start a new branch for a temporary destructor 457 /// call. This is the case when the the temporary destructor is 458 /// conditionally executed, and it is the first one we encounter while 459 /// visiting a subexpression - other temporary destructors at the same level 460 /// will be added to the same block and are executed under the same 461 /// condition. 462 bool needsTempDtorBranch() const { 463 return IsConditional && !TerminatorExpr; 464 } 465 466 /// Remember the successor S of a temporary destructor decision branch for 467 /// the corresponding CXXBindTemporaryExpr E. 468 void setDecisionPoint(CFGBlock *S, CXXBindTemporaryExpr *E) { 469 Succ = S; 470 TerminatorExpr = E; 471 } 472 473 const bool IsConditional; 474 const TryResult KnownExecuted; 475 CFGBlock *Succ; 476 CXXBindTemporaryExpr *TerminatorExpr; 477 }; 478 479 // Visitors to walk an AST and generate destructors of temporaries in 480 // full expression. 481 CFGBlock *VisitForTemporaryDtors(Stmt *E, bool BindToTemporary, 482 TempDtorContext &Context); 483 CFGBlock *VisitChildrenForTemporaryDtors(Stmt *E, TempDtorContext &Context); 484 CFGBlock *VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E, 485 TempDtorContext &Context); 486 CFGBlock *VisitCXXBindTemporaryExprForTemporaryDtors( 487 CXXBindTemporaryExpr *E, bool BindToTemporary, TempDtorContext &Context); 488 CFGBlock *VisitConditionalOperatorForTemporaryDtors( 489 AbstractConditionalOperator *E, bool BindToTemporary, 490 TempDtorContext &Context); 491 void InsertTempDtorDecisionBlock(const TempDtorContext &Context, 492 CFGBlock *FalseSucc = nullptr); 493 494 // NYS == Not Yet Supported 495 CFGBlock *NYS() { 496 badCFG = true; 497 return Block; 498 } 499 500 void autoCreateBlock() { if (!Block) Block = createBlock(); } 501 CFGBlock *createBlock(bool add_successor = true); 502 CFGBlock *createNoReturnBlock(); 503 504 CFGBlock *addStmt(Stmt *S) { 505 return Visit(S, AddStmtChoice::AlwaysAdd); 506 } 507 CFGBlock *addInitializer(CXXCtorInitializer *I); 508 void addAutomaticObjDtors(LocalScope::const_iterator B, 509 LocalScope::const_iterator E, Stmt *S); 510 void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD); 511 512 // Local scopes creation. 513 LocalScope* createOrReuseLocalScope(LocalScope* Scope); 514 515 void addLocalScopeForStmt(Stmt *S); 516 LocalScope* addLocalScopeForDeclStmt(DeclStmt *DS, 517 LocalScope* Scope = nullptr); 518 LocalScope* addLocalScopeForVarDecl(VarDecl *VD, LocalScope* Scope = nullptr); 519 520 void addLocalScopeAndDtors(Stmt *S); 521 522 // Interface to CFGBlock - adding CFGElements. 523 void appendStmt(CFGBlock *B, const Stmt *S) { 524 if (alwaysAdd(S) && cachedEntry) 525 cachedEntry->second = B; 526 527 // All block-level expressions should have already been IgnoreParens()ed. 528 assert(!isa<Expr>(S) || cast<Expr>(S)->IgnoreParens() == S); 529 B->appendStmt(const_cast<Stmt*>(S), cfg->getBumpVectorContext()); 530 } 531 void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) { 532 B->appendInitializer(I, cfg->getBumpVectorContext()); 533 } 534 void appendNewAllocator(CFGBlock *B, CXXNewExpr *NE) { 535 B->appendNewAllocator(NE, cfg->getBumpVectorContext()); 536 } 537 void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) { 538 B->appendBaseDtor(BS, cfg->getBumpVectorContext()); 539 } 540 void appendMemberDtor(CFGBlock *B, FieldDecl *FD) { 541 B->appendMemberDtor(FD, cfg->getBumpVectorContext()); 542 } 543 void appendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) { 544 B->appendTemporaryDtor(E, cfg->getBumpVectorContext()); 545 } 546 void appendAutomaticObjDtor(CFGBlock *B, VarDecl *VD, Stmt *S) { 547 B->appendAutomaticObjDtor(VD, S, cfg->getBumpVectorContext()); 548 } 549 550 void appendDeleteDtor(CFGBlock *B, CXXRecordDecl *RD, CXXDeleteExpr *DE) { 551 B->appendDeleteDtor(RD, DE, cfg->getBumpVectorContext()); 552 } 553 554 void prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk, 555 LocalScope::const_iterator B, LocalScope::const_iterator E); 556 557 void addSuccessor(CFGBlock *B, CFGBlock *S, bool IsReachable = true) { 558 B->addSuccessor(CFGBlock::AdjacentBlock(S, IsReachable), 559 cfg->getBumpVectorContext()); 560 } 561 562 /// Add a reachable successor to a block, with the alternate variant that is 563 /// unreachable. 564 void addSuccessor(CFGBlock *B, CFGBlock *ReachableBlock, CFGBlock *AltBlock) { 565 B->addSuccessor(CFGBlock::AdjacentBlock(ReachableBlock, AltBlock), 566 cfg->getBumpVectorContext()); 567 } 568 569 /// \brief Find a relational comparison with an expression evaluating to a 570 /// boolean and a constant other than 0 and 1. 571 /// e.g. if ((x < y) == 10) 572 TryResult checkIncorrectRelationalOperator(const BinaryOperator *B) { 573 const Expr *LHSExpr = B->getLHS()->IgnoreParens(); 574 const Expr *RHSExpr = B->getRHS()->IgnoreParens(); 575 576 const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(LHSExpr); 577 const Expr *BoolExpr = RHSExpr; 578 bool IntFirst = true; 579 if (!IntLiteral) { 580 IntLiteral = dyn_cast<IntegerLiteral>(RHSExpr); 581 BoolExpr = LHSExpr; 582 IntFirst = false; 583 } 584 585 if (!IntLiteral || !BoolExpr->isKnownToHaveBooleanValue()) 586 return TryResult(); 587 588 llvm::APInt IntValue = IntLiteral->getValue(); 589 if ((IntValue == 1) || (IntValue == 0)) 590 return TryResult(); 591 592 bool IntLarger = IntLiteral->getType()->isUnsignedIntegerType() || 593 !IntValue.isNegative(); 594 595 BinaryOperatorKind Bok = B->getOpcode(); 596 if (Bok == BO_GT || Bok == BO_GE) { 597 // Always true for 10 > bool and bool > -1 598 // Always false for -1 > bool and bool > 10 599 return TryResult(IntFirst == IntLarger); 600 } else { 601 // Always true for -1 < bool and bool < 10 602 // Always false for 10 < bool and bool < -1 603 return TryResult(IntFirst != IntLarger); 604 } 605 } 606 607 /// Find an incorrect equality comparison. Either with an expression 608 /// evaluating to a boolean and a constant other than 0 and 1. 609 /// e.g. if (!x == 10) or a bitwise and/or operation that always evaluates to 610 /// true/false e.q. (x & 8) == 4. 611 TryResult checkIncorrectEqualityOperator(const BinaryOperator *B) { 612 const Expr *LHSExpr = B->getLHS()->IgnoreParens(); 613 const Expr *RHSExpr = B->getRHS()->IgnoreParens(); 614 615 const IntegerLiteral *IntLiteral = dyn_cast<IntegerLiteral>(LHSExpr); 616 const Expr *BoolExpr = RHSExpr; 617 618 if (!IntLiteral) { 619 IntLiteral = dyn_cast<IntegerLiteral>(RHSExpr); 620 BoolExpr = LHSExpr; 621 } 622 623 if (!IntLiteral) 624 return TryResult(); 625 626 const BinaryOperator *BitOp = dyn_cast<BinaryOperator>(BoolExpr); 627 if (BitOp && (BitOp->getOpcode() == BO_And || 628 BitOp->getOpcode() == BO_Or)) { 629 const Expr *LHSExpr2 = BitOp->getLHS()->IgnoreParens(); 630 const Expr *RHSExpr2 = BitOp->getRHS()->IgnoreParens(); 631 632 const IntegerLiteral *IntLiteral2 = dyn_cast<IntegerLiteral>(LHSExpr2); 633 634 if (!IntLiteral2) 635 IntLiteral2 = dyn_cast<IntegerLiteral>(RHSExpr2); 636 637 if (!IntLiteral2) 638 return TryResult(); 639 640 llvm::APInt L1 = IntLiteral->getValue(); 641 llvm::APInt L2 = IntLiteral2->getValue(); 642 if ((BitOp->getOpcode() == BO_And && (L2 & L1) != L1) || 643 (BitOp->getOpcode() == BO_Or && (L2 | L1) != L1)) { 644 if (BuildOpts.Observer) 645 BuildOpts.Observer->compareBitwiseEquality(B, 646 B->getOpcode() != BO_EQ); 647 TryResult(B->getOpcode() != BO_EQ); 648 } 649 } else if (BoolExpr->isKnownToHaveBooleanValue()) { 650 llvm::APInt IntValue = IntLiteral->getValue(); 651 if ((IntValue == 1) || (IntValue == 0)) { 652 return TryResult(); 653 } 654 return TryResult(B->getOpcode() != BO_EQ); 655 } 656 657 return TryResult(); 658 } 659 660 TryResult analyzeLogicOperatorCondition(BinaryOperatorKind Relation, 661 const llvm::APSInt &Value1, 662 const llvm::APSInt &Value2) { 663 assert(Value1.isSigned() == Value2.isSigned()); 664 switch (Relation) { 665 default: 666 return TryResult(); 667 case BO_EQ: 668 return TryResult(Value1 == Value2); 669 case BO_NE: 670 return TryResult(Value1 != Value2); 671 case BO_LT: 672 return TryResult(Value1 < Value2); 673 case BO_LE: 674 return TryResult(Value1 <= Value2); 675 case BO_GT: 676 return TryResult(Value1 > Value2); 677 case BO_GE: 678 return TryResult(Value1 >= Value2); 679 } 680 } 681 682 /// \brief Find a pair of comparison expressions with or without parentheses 683 /// with a shared variable and constants and a logical operator between them 684 /// that always evaluates to either true or false. 685 /// e.g. if (x != 3 || x != 4) 686 TryResult checkIncorrectLogicOperator(const BinaryOperator *B) { 687 assert(B->isLogicalOp()); 688 const BinaryOperator *LHS = 689 dyn_cast<BinaryOperator>(B->getLHS()->IgnoreParens()); 690 const BinaryOperator *RHS = 691 dyn_cast<BinaryOperator>(B->getRHS()->IgnoreParens()); 692 if (!LHS || !RHS) 693 return TryResult(); 694 695 if (!LHS->isComparisonOp() || !RHS->isComparisonOp()) 696 return TryResult(); 697 698 BinaryOperatorKind BO1 = LHS->getOpcode(); 699 const DeclRefExpr *Decl1 = 700 dyn_cast<DeclRefExpr>(LHS->getLHS()->IgnoreParenImpCasts()); 701 const IntegerLiteral *Literal1 = 702 dyn_cast<IntegerLiteral>(LHS->getRHS()->IgnoreParens()); 703 if (!Decl1 && !Literal1) { 704 if (BO1 == BO_GT) 705 BO1 = BO_LT; 706 else if (BO1 == BO_GE) 707 BO1 = BO_LE; 708 else if (BO1 == BO_LT) 709 BO1 = BO_GT; 710 else if (BO1 == BO_LE) 711 BO1 = BO_GE; 712 Decl1 = dyn_cast<DeclRefExpr>(LHS->getRHS()->IgnoreParenImpCasts()); 713 Literal1 = dyn_cast<IntegerLiteral>(LHS->getLHS()->IgnoreParens()); 714 } 715 716 if (!Decl1 || !Literal1) 717 return TryResult(); 718 719 BinaryOperatorKind BO2 = RHS->getOpcode(); 720 const DeclRefExpr *Decl2 = 721 dyn_cast<DeclRefExpr>(RHS->getLHS()->IgnoreParenImpCasts()); 722 const IntegerLiteral *Literal2 = 723 dyn_cast<IntegerLiteral>(RHS->getRHS()->IgnoreParens()); 724 if (!Decl2 && !Literal2) { 725 if (BO2 == BO_GT) 726 BO2 = BO_LT; 727 else if (BO2 == BO_GE) 728 BO2 = BO_LE; 729 else if (BO2 == BO_LT) 730 BO2 = BO_GT; 731 else if (BO2 == BO_LE) 732 BO2 = BO_GE; 733 Decl2 = dyn_cast<DeclRefExpr>(RHS->getRHS()->IgnoreParenImpCasts()); 734 Literal2 = dyn_cast<IntegerLiteral>(RHS->getLHS()->IgnoreParens()); 735 } 736 737 if (!Decl2 || !Literal2) 738 return TryResult(); 739 740 // Check that it is the same variable on both sides. 741 if (Decl1->getDecl() != Decl2->getDecl()) 742 return TryResult(); 743 744 llvm::APSInt L1, L2; 745 746 if (!Literal1->EvaluateAsInt(L1, *Context) || 747 !Literal2->EvaluateAsInt(L2, *Context)) 748 return TryResult(); 749 750 // Can't compare signed with unsigned or with different bit width. 751 if (L1.isSigned() != L2.isSigned() || L1.getBitWidth() != L2.getBitWidth()) 752 return TryResult(); 753 754 // Values that will be used to determine if result of logical 755 // operator is always true/false 756 const llvm::APSInt Values[] = { 757 // Value less than both Value1 and Value2 758 llvm::APSInt::getMinValue(L1.getBitWidth(), L1.isUnsigned()), 759 // L1 760 L1, 761 // Value between Value1 and Value2 762 ((L1 < L2) ? L1 : L2) + llvm::APSInt(llvm::APInt(L1.getBitWidth(), 1), 763 L1.isUnsigned()), 764 // L2 765 L2, 766 // Value greater than both Value1 and Value2 767 llvm::APSInt::getMaxValue(L1.getBitWidth(), L1.isUnsigned()), 768 }; 769 770 // Check whether expression is always true/false by evaluating the following 771 // * variable x is less than the smallest literal. 772 // * variable x is equal to the smallest literal. 773 // * Variable x is between smallest and largest literal. 774 // * Variable x is equal to the largest literal. 775 // * Variable x is greater than largest literal. 776 bool AlwaysTrue = true, AlwaysFalse = true; 777 for (unsigned int ValueIndex = 0; 778 ValueIndex < sizeof(Values) / sizeof(Values[0]); 779 ++ValueIndex) { 780 llvm::APSInt Value = Values[ValueIndex]; 781 TryResult Res1, Res2; 782 Res1 = analyzeLogicOperatorCondition(BO1, Value, L1); 783 Res2 = analyzeLogicOperatorCondition(BO2, Value, L2); 784 785 if (!Res1.isKnown() || !Res2.isKnown()) 786 return TryResult(); 787 788 if (B->getOpcode() == BO_LAnd) { 789 AlwaysTrue &= (Res1.isTrue() && Res2.isTrue()); 790 AlwaysFalse &= !(Res1.isTrue() && Res2.isTrue()); 791 } else { 792 AlwaysTrue &= (Res1.isTrue() || Res2.isTrue()); 793 AlwaysFalse &= !(Res1.isTrue() || Res2.isTrue()); 794 } 795 } 796 797 if (AlwaysTrue || AlwaysFalse) { 798 if (BuildOpts.Observer) 799 BuildOpts.Observer->compareAlwaysTrue(B, AlwaysTrue); 800 return TryResult(AlwaysTrue); 801 } 802 return TryResult(); 803 } 804 805 /// Try and evaluate an expression to an integer constant. 806 bool tryEvaluate(Expr *S, Expr::EvalResult &outResult) { 807 if (!BuildOpts.PruneTriviallyFalseEdges) 808 return false; 809 return !S->isTypeDependent() && 810 !S->isValueDependent() && 811 S->EvaluateAsRValue(outResult, *Context); 812 } 813 814 /// tryEvaluateBool - Try and evaluate the Stmt and return 0 or 1 815 /// if we can evaluate to a known value, otherwise return -1. 816 TryResult tryEvaluateBool(Expr *S) { 817 if (!BuildOpts.PruneTriviallyFalseEdges || 818 S->isTypeDependent() || S->isValueDependent()) 819 return TryResult(); 820 821 if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(S)) { 822 if (Bop->isLogicalOp()) { 823 // Check the cache first. 824 CachedBoolEvalsTy::iterator I = CachedBoolEvals.find(S); 825 if (I != CachedBoolEvals.end()) 826 return I->second; // already in map; 827 828 // Retrieve result at first, or the map might be updated. 829 TryResult Result = evaluateAsBooleanConditionNoCache(S); 830 CachedBoolEvals[S] = Result; // update or insert 831 return Result; 832 } 833 else { 834 switch (Bop->getOpcode()) { 835 default: break; 836 // For 'x & 0' and 'x * 0', we can determine that 837 // the value is always false. 838 case BO_Mul: 839 case BO_And: { 840 // If either operand is zero, we know the value 841 // must be false. 842 llvm::APSInt IntVal; 843 if (Bop->getLHS()->EvaluateAsInt(IntVal, *Context)) { 844 if (!IntVal.getBoolValue()) { 845 return TryResult(false); 846 } 847 } 848 if (Bop->getRHS()->EvaluateAsInt(IntVal, *Context)) { 849 if (!IntVal.getBoolValue()) { 850 return TryResult(false); 851 } 852 } 853 } 854 break; 855 } 856 } 857 } 858 859 return evaluateAsBooleanConditionNoCache(S); 860 } 861 862 /// \brief Evaluate as boolean \param E without using the cache. 863 TryResult evaluateAsBooleanConditionNoCache(Expr *E) { 864 if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(E)) { 865 if (Bop->isLogicalOp()) { 866 TryResult LHS = tryEvaluateBool(Bop->getLHS()); 867 if (LHS.isKnown()) { 868 // We were able to evaluate the LHS, see if we can get away with not 869 // evaluating the RHS: 0 && X -> 0, 1 || X -> 1 870 if (LHS.isTrue() == (Bop->getOpcode() == BO_LOr)) 871 return LHS.isTrue(); 872 873 TryResult RHS = tryEvaluateBool(Bop->getRHS()); 874 if (RHS.isKnown()) { 875 if (Bop->getOpcode() == BO_LOr) 876 return LHS.isTrue() || RHS.isTrue(); 877 else 878 return LHS.isTrue() && RHS.isTrue(); 879 } 880 } else { 881 TryResult RHS = tryEvaluateBool(Bop->getRHS()); 882 if (RHS.isKnown()) { 883 // We can't evaluate the LHS; however, sometimes the result 884 // is determined by the RHS: X && 0 -> 0, X || 1 -> 1. 885 if (RHS.isTrue() == (Bop->getOpcode() == BO_LOr)) 886 return RHS.isTrue(); 887 } else { 888 TryResult BopRes = checkIncorrectLogicOperator(Bop); 889 if (BopRes.isKnown()) 890 return BopRes.isTrue(); 891 } 892 } 893 894 return TryResult(); 895 } else if (Bop->isEqualityOp()) { 896 TryResult BopRes = checkIncorrectEqualityOperator(Bop); 897 if (BopRes.isKnown()) 898 return BopRes.isTrue(); 899 } else if (Bop->isRelationalOp()) { 900 TryResult BopRes = checkIncorrectRelationalOperator(Bop); 901 if (BopRes.isKnown()) 902 return BopRes.isTrue(); 903 } 904 } 905 906 bool Result; 907 if (E->EvaluateAsBooleanCondition(Result, *Context)) 908 return Result; 909 910 return TryResult(); 911 } 912 913 }; 914 915 inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder, 916 const Stmt *stmt) const { 917 return builder.alwaysAdd(stmt) || kind == AlwaysAdd; 918 } 919 920 bool CFGBuilder::alwaysAdd(const Stmt *stmt) { 921 bool shouldAdd = BuildOpts.alwaysAdd(stmt); 922 923 if (!BuildOpts.forcedBlkExprs) 924 return shouldAdd; 925 926 if (lastLookup == stmt) { 927 if (cachedEntry) { 928 assert(cachedEntry->first == stmt); 929 return true; 930 } 931 return shouldAdd; 932 } 933 934 lastLookup = stmt; 935 936 // Perform the lookup! 937 CFG::BuildOptions::ForcedBlkExprs *fb = *BuildOpts.forcedBlkExprs; 938 939 if (!fb) { 940 // No need to update 'cachedEntry', since it will always be null. 941 assert(!cachedEntry); 942 return shouldAdd; 943 } 944 945 CFG::BuildOptions::ForcedBlkExprs::iterator itr = fb->find(stmt); 946 if (itr == fb->end()) { 947 cachedEntry = nullptr; 948 return shouldAdd; 949 } 950 951 cachedEntry = &*itr; 952 return true; 953 } 954 955 // FIXME: Add support for dependent-sized array types in C++? 956 // Does it even make sense to build a CFG for an uninstantiated template? 957 static const VariableArrayType *FindVA(const Type *t) { 958 while (const ArrayType *vt = dyn_cast<ArrayType>(t)) { 959 if (const VariableArrayType *vat = dyn_cast<VariableArrayType>(vt)) 960 if (vat->getSizeExpr()) 961 return vat; 962 963 t = vt->getElementType().getTypePtr(); 964 } 965 966 return nullptr; 967 } 968 969 /// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an 970 /// arbitrary statement. Examples include a single expression or a function 971 /// body (compound statement). The ownership of the returned CFG is 972 /// transferred to the caller. If CFG construction fails, this method returns 973 /// NULL. 974 std::unique_ptr<CFG> CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) { 975 assert(cfg.get()); 976 if (!Statement) 977 return nullptr; 978 979 // Create an empty block that will serve as the exit block for the CFG. Since 980 // this is the first block added to the CFG, it will be implicitly registered 981 // as the exit block. 982 Succ = createBlock(); 983 assert(Succ == &cfg->getExit()); 984 Block = nullptr; // the EXIT block is empty. Create all other blocks lazily. 985 986 if (BuildOpts.AddImplicitDtors) 987 if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(D)) 988 addImplicitDtorsForDestructor(DD); 989 990 // Visit the statements and create the CFG. 991 CFGBlock *B = addStmt(Statement); 992 993 if (badCFG) 994 return nullptr; 995 996 // For C++ constructor add initializers to CFG. 997 if (const CXXConstructorDecl *CD = dyn_cast_or_null<CXXConstructorDecl>(D)) { 998 for (CXXConstructorDecl::init_const_reverse_iterator I = CD->init_rbegin(), 999 E = CD->init_rend(); I != E; ++I) { 1000 B = addInitializer(*I); 1001 if (badCFG) 1002 return nullptr; 1003 } 1004 } 1005 1006 if (B) 1007 Succ = B; 1008 1009 // Backpatch the gotos whose label -> block mappings we didn't know when we 1010 // encountered them. 1011 for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(), 1012 E = BackpatchBlocks.end(); I != E; ++I ) { 1013 1014 CFGBlock *B = I->block; 1015 const GotoStmt *G = cast<GotoStmt>(B->getTerminator()); 1016 LabelMapTy::iterator LI = LabelMap.find(G->getLabel()); 1017 1018 // If there is no target for the goto, then we are looking at an 1019 // incomplete AST. Handle this by not registering a successor. 1020 if (LI == LabelMap.end()) continue; 1021 1022 JumpTarget JT = LI->second; 1023 prependAutomaticObjDtorsWithTerminator(B, I->scopePosition, 1024 JT.scopePosition); 1025 addSuccessor(B, JT.block); 1026 } 1027 1028 // Add successors to the Indirect Goto Dispatch block (if we have one). 1029 if (CFGBlock *B = cfg->getIndirectGotoBlock()) 1030 for (LabelSetTy::iterator I = AddressTakenLabels.begin(), 1031 E = AddressTakenLabels.end(); I != E; ++I ) { 1032 1033 // Lookup the target block. 1034 LabelMapTy::iterator LI = LabelMap.find(*I); 1035 1036 // If there is no target block that contains label, then we are looking 1037 // at an incomplete AST. Handle this by not registering a successor. 1038 if (LI == LabelMap.end()) continue; 1039 1040 addSuccessor(B, LI->second.block); 1041 } 1042 1043 // Create an empty entry block that has no predecessors. 1044 cfg->setEntry(createBlock()); 1045 1046 return std::move(cfg); 1047 } 1048 1049 /// createBlock - Used to lazily create blocks that are connected 1050 /// to the current (global) succcessor. 1051 CFGBlock *CFGBuilder::createBlock(bool add_successor) { 1052 CFGBlock *B = cfg->createBlock(); 1053 if (add_successor && Succ) 1054 addSuccessor(B, Succ); 1055 return B; 1056 } 1057 1058 /// createNoReturnBlock - Used to create a block is a 'noreturn' point in the 1059 /// CFG. It is *not* connected to the current (global) successor, and instead 1060 /// directly tied to the exit block in order to be reachable. 1061 CFGBlock *CFGBuilder::createNoReturnBlock() { 1062 CFGBlock *B = createBlock(false); 1063 B->setHasNoReturnElement(); 1064 addSuccessor(B, &cfg->getExit(), Succ); 1065 return B; 1066 } 1067 1068 /// addInitializer - Add C++ base or member initializer element to CFG. 1069 CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) { 1070 if (!BuildOpts.AddInitializers) 1071 return Block; 1072 1073 bool HasTemporaries = false; 1074 1075 // Destructors of temporaries in initialization expression should be called 1076 // after initialization finishes. 1077 Expr *Init = I->getInit(); 1078 if (Init) { 1079 HasTemporaries = isa<ExprWithCleanups>(Init); 1080 1081 if (BuildOpts.AddTemporaryDtors && HasTemporaries) { 1082 // Generate destructors for temporaries in initialization expression. 1083 TempDtorContext Context; 1084 VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(), 1085 /*BindToTemporary=*/false, Context); 1086 } 1087 } 1088 1089 autoCreateBlock(); 1090 appendInitializer(Block, I); 1091 1092 if (Init) { 1093 if (HasTemporaries) { 1094 // For expression with temporaries go directly to subexpression to omit 1095 // generating destructors for the second time. 1096 return Visit(cast<ExprWithCleanups>(Init)->getSubExpr()); 1097 } 1098 return Visit(Init); 1099 } 1100 1101 return Block; 1102 } 1103 1104 /// \brief Retrieve the type of the temporary object whose lifetime was 1105 /// extended by a local reference with the given initializer. 1106 static QualType getReferenceInitTemporaryType(ASTContext &Context, 1107 const Expr *Init) { 1108 while (true) { 1109 // Skip parentheses. 1110 Init = Init->IgnoreParens(); 1111 1112 // Skip through cleanups. 1113 if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Init)) { 1114 Init = EWC->getSubExpr(); 1115 continue; 1116 } 1117 1118 // Skip through the temporary-materialization expression. 1119 if (const MaterializeTemporaryExpr *MTE 1120 = dyn_cast<MaterializeTemporaryExpr>(Init)) { 1121 Init = MTE->GetTemporaryExpr(); 1122 continue; 1123 } 1124 1125 // Skip derived-to-base and no-op casts. 1126 if (const CastExpr *CE = dyn_cast<CastExpr>(Init)) { 1127 if ((CE->getCastKind() == CK_DerivedToBase || 1128 CE->getCastKind() == CK_UncheckedDerivedToBase || 1129 CE->getCastKind() == CK_NoOp) && 1130 Init->getType()->isRecordType()) { 1131 Init = CE->getSubExpr(); 1132 continue; 1133 } 1134 } 1135 1136 // Skip member accesses into rvalues. 1137 if (const MemberExpr *ME = dyn_cast<MemberExpr>(Init)) { 1138 if (!ME->isArrow() && ME->getBase()->isRValue()) { 1139 Init = ME->getBase(); 1140 continue; 1141 } 1142 } 1143 1144 break; 1145 } 1146 1147 return Init->getType(); 1148 } 1149 1150 /// addAutomaticObjDtors - Add to current block automatic objects destructors 1151 /// for objects in range of local scope positions. Use S as trigger statement 1152 /// for destructors. 1153 void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B, 1154 LocalScope::const_iterator E, Stmt *S) { 1155 if (!BuildOpts.AddImplicitDtors) 1156 return; 1157 1158 if (B == E) 1159 return; 1160 1161 // We need to append the destructors in reverse order, but any one of them 1162 // may be a no-return destructor which changes the CFG. As a result, buffer 1163 // this sequence up and replay them in reverse order when appending onto the 1164 // CFGBlock(s). 1165 SmallVector<VarDecl*, 10> Decls; 1166 Decls.reserve(B.distance(E)); 1167 for (LocalScope::const_iterator I = B; I != E; ++I) 1168 Decls.push_back(*I); 1169 1170 for (SmallVectorImpl<VarDecl*>::reverse_iterator I = Decls.rbegin(), 1171 E = Decls.rend(); 1172 I != E; ++I) { 1173 // If this destructor is marked as a no-return destructor, we need to 1174 // create a new block for the destructor which does not have as a successor 1175 // anything built thus far: control won't flow out of this block. 1176 QualType Ty = (*I)->getType(); 1177 if (Ty->isReferenceType()) { 1178 Ty = getReferenceInitTemporaryType(*Context, (*I)->getInit()); 1179 } 1180 Ty = Context->getBaseElementType(Ty); 1181 1182 const CXXDestructorDecl *Dtor = Ty->getAsCXXRecordDecl()->getDestructor(); 1183 if (Dtor->isNoReturn()) 1184 Block = createNoReturnBlock(); 1185 else 1186 autoCreateBlock(); 1187 1188 appendAutomaticObjDtor(Block, *I, S); 1189 } 1190 } 1191 1192 /// addImplicitDtorsForDestructor - Add implicit destructors generated for 1193 /// base and member objects in destructor. 1194 void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) { 1195 assert (BuildOpts.AddImplicitDtors 1196 && "Can be called only when dtors should be added"); 1197 const CXXRecordDecl *RD = DD->getParent(); 1198 1199 // At the end destroy virtual base objects. 1200 for (const auto &VI : RD->vbases()) { 1201 const CXXRecordDecl *CD = VI.getType()->getAsCXXRecordDecl(); 1202 if (!CD->hasTrivialDestructor()) { 1203 autoCreateBlock(); 1204 appendBaseDtor(Block, &VI); 1205 } 1206 } 1207 1208 // Before virtual bases destroy direct base objects. 1209 for (const auto &BI : RD->bases()) { 1210 if (!BI.isVirtual()) { 1211 const CXXRecordDecl *CD = BI.getType()->getAsCXXRecordDecl(); 1212 if (!CD->hasTrivialDestructor()) { 1213 autoCreateBlock(); 1214 appendBaseDtor(Block, &BI); 1215 } 1216 } 1217 } 1218 1219 // First destroy member objects. 1220 for (auto *FI : RD->fields()) { 1221 // Check for constant size array. Set type to array element type. 1222 QualType QT = FI->getType(); 1223 if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) { 1224 if (AT->getSize() == 0) 1225 continue; 1226 QT = AT->getElementType(); 1227 } 1228 1229 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl()) 1230 if (!CD->hasTrivialDestructor()) { 1231 autoCreateBlock(); 1232 appendMemberDtor(Block, FI); 1233 } 1234 } 1235 } 1236 1237 /// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either 1238 /// way return valid LocalScope object. 1239 LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) { 1240 if (!Scope) { 1241 llvm::BumpPtrAllocator &alloc = cfg->getAllocator(); 1242 Scope = alloc.Allocate<LocalScope>(); 1243 BumpVectorContext ctx(alloc); 1244 new (Scope) LocalScope(ctx, ScopePos); 1245 } 1246 return Scope; 1247 } 1248 1249 /// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement 1250 /// that should create implicit scope (e.g. if/else substatements). 1251 void CFGBuilder::addLocalScopeForStmt(Stmt *S) { 1252 if (!BuildOpts.AddImplicitDtors) 1253 return; 1254 1255 LocalScope *Scope = nullptr; 1256 1257 // For compound statement we will be creating explicit scope. 1258 if (CompoundStmt *CS = dyn_cast<CompoundStmt>(S)) { 1259 for (auto *BI : CS->body()) { 1260 Stmt *SI = BI->stripLabelLikeStatements(); 1261 if (DeclStmt *DS = dyn_cast<DeclStmt>(SI)) 1262 Scope = addLocalScopeForDeclStmt(DS, Scope); 1263 } 1264 return; 1265 } 1266 1267 // For any other statement scope will be implicit and as such will be 1268 // interesting only for DeclStmt. 1269 if (DeclStmt *DS = dyn_cast<DeclStmt>(S->stripLabelLikeStatements())) 1270 addLocalScopeForDeclStmt(DS); 1271 } 1272 1273 /// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will 1274 /// reuse Scope if not NULL. 1275 LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt *DS, 1276 LocalScope* Scope) { 1277 if (!BuildOpts.AddImplicitDtors) 1278 return Scope; 1279 1280 for (auto *DI : DS->decls()) 1281 if (VarDecl *VD = dyn_cast<VarDecl>(DI)) 1282 Scope = addLocalScopeForVarDecl(VD, Scope); 1283 return Scope; 1284 } 1285 1286 /// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will 1287 /// create add scope for automatic objects and temporary objects bound to 1288 /// const reference. Will reuse Scope if not NULL. 1289 LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD, 1290 LocalScope* Scope) { 1291 if (!BuildOpts.AddImplicitDtors) 1292 return Scope; 1293 1294 // Check if variable is local. 1295 switch (VD->getStorageClass()) { 1296 case SC_None: 1297 case SC_Auto: 1298 case SC_Register: 1299 break; 1300 default: return Scope; 1301 } 1302 1303 // Check for const references bound to temporary. Set type to pointee. 1304 QualType QT = VD->getType(); 1305 if (QT.getTypePtr()->isReferenceType()) { 1306 // Attempt to determine whether this declaration lifetime-extends a 1307 // temporary. 1308 // 1309 // FIXME: This is incorrect. Non-reference declarations can lifetime-extend 1310 // temporaries, and a single declaration can extend multiple temporaries. 1311 // We should look at the storage duration on each nested 1312 // MaterializeTemporaryExpr instead. 1313 const Expr *Init = VD->getInit(); 1314 if (!Init) 1315 return Scope; 1316 if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Init)) 1317 Init = EWC->getSubExpr(); 1318 if (!isa<MaterializeTemporaryExpr>(Init)) 1319 return Scope; 1320 1321 // Lifetime-extending a temporary. 1322 QT = getReferenceInitTemporaryType(*Context, Init); 1323 } 1324 1325 // Check for constant size array. Set type to array element type. 1326 while (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) { 1327 if (AT->getSize() == 0) 1328 return Scope; 1329 QT = AT->getElementType(); 1330 } 1331 1332 // Check if type is a C++ class with non-trivial destructor. 1333 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl()) 1334 if (!CD->hasTrivialDestructor()) { 1335 // Add the variable to scope 1336 Scope = createOrReuseLocalScope(Scope); 1337 Scope->addVar(VD); 1338 ScopePos = Scope->begin(); 1339 } 1340 return Scope; 1341 } 1342 1343 /// addLocalScopeAndDtors - For given statement add local scope for it and 1344 /// add destructors that will cleanup the scope. Will reuse Scope if not NULL. 1345 void CFGBuilder::addLocalScopeAndDtors(Stmt *S) { 1346 if (!BuildOpts.AddImplicitDtors) 1347 return; 1348 1349 LocalScope::const_iterator scopeBeginPos = ScopePos; 1350 addLocalScopeForStmt(S); 1351 addAutomaticObjDtors(ScopePos, scopeBeginPos, S); 1352 } 1353 1354 /// prependAutomaticObjDtorsWithTerminator - Prepend destructor CFGElements for 1355 /// variables with automatic storage duration to CFGBlock's elements vector. 1356 /// Elements will be prepended to physical beginning of the vector which 1357 /// happens to be logical end. Use blocks terminator as statement that specifies 1358 /// destructors call site. 1359 /// FIXME: This mechanism for adding automatic destructors doesn't handle 1360 /// no-return destructors properly. 1361 void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk, 1362 LocalScope::const_iterator B, LocalScope::const_iterator E) { 1363 BumpVectorContext &C = cfg->getBumpVectorContext(); 1364 CFGBlock::iterator InsertPos 1365 = Blk->beginAutomaticObjDtorsInsert(Blk->end(), B.distance(E), C); 1366 for (LocalScope::const_iterator I = B; I != E; ++I) 1367 InsertPos = Blk->insertAutomaticObjDtor(InsertPos, *I, 1368 Blk->getTerminator()); 1369 } 1370 1371 /// Visit - Walk the subtree of a statement and add extra 1372 /// blocks for ternary operators, &&, and ||. We also process "," and 1373 /// DeclStmts (which may contain nested control-flow). 1374 CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) { 1375 if (!S) { 1376 badCFG = true; 1377 return nullptr; 1378 } 1379 1380 if (Expr *E = dyn_cast<Expr>(S)) 1381 S = E->IgnoreParens(); 1382 1383 switch (S->getStmtClass()) { 1384 default: 1385 return VisitStmt(S, asc); 1386 1387 case Stmt::AddrLabelExprClass: 1388 return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc); 1389 1390 case Stmt::BinaryConditionalOperatorClass: 1391 return VisitConditionalOperator(cast<BinaryConditionalOperator>(S), asc); 1392 1393 case Stmt::BinaryOperatorClass: 1394 return VisitBinaryOperator(cast<BinaryOperator>(S), asc); 1395 1396 case Stmt::BlockExprClass: 1397 return VisitNoRecurse(cast<Expr>(S), asc); 1398 1399 case Stmt::BreakStmtClass: 1400 return VisitBreakStmt(cast<BreakStmt>(S)); 1401 1402 case Stmt::CallExprClass: 1403 case Stmt::CXXOperatorCallExprClass: 1404 case Stmt::CXXMemberCallExprClass: 1405 case Stmt::UserDefinedLiteralClass: 1406 return VisitCallExpr(cast<CallExpr>(S), asc); 1407 1408 case Stmt::CaseStmtClass: 1409 return VisitCaseStmt(cast<CaseStmt>(S)); 1410 1411 case Stmt::ChooseExprClass: 1412 return VisitChooseExpr(cast<ChooseExpr>(S), asc); 1413 1414 case Stmt::CompoundStmtClass: 1415 return VisitCompoundStmt(cast<CompoundStmt>(S)); 1416 1417 case Stmt::ConditionalOperatorClass: 1418 return VisitConditionalOperator(cast<ConditionalOperator>(S), asc); 1419 1420 case Stmt::ContinueStmtClass: 1421 return VisitContinueStmt(cast<ContinueStmt>(S)); 1422 1423 case Stmt::CXXCatchStmtClass: 1424 return VisitCXXCatchStmt(cast<CXXCatchStmt>(S)); 1425 1426 case Stmt::ExprWithCleanupsClass: 1427 return VisitExprWithCleanups(cast<ExprWithCleanups>(S), asc); 1428 1429 case Stmt::CXXDefaultArgExprClass: 1430 case Stmt::CXXDefaultInitExprClass: 1431 // FIXME: The expression inside a CXXDefaultArgExpr is owned by the 1432 // called function's declaration, not by the caller. If we simply add 1433 // this expression to the CFG, we could end up with the same Expr 1434 // appearing multiple times. 1435 // PR13385 / <rdar://problem/12156507> 1436 // 1437 // It's likewise possible for multiple CXXDefaultInitExprs for the same 1438 // expression to be used in the same function (through aggregate 1439 // initialization). 1440 return VisitStmt(S, asc); 1441 1442 case Stmt::CXXBindTemporaryExprClass: 1443 return VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), asc); 1444 1445 case Stmt::CXXConstructExprClass: 1446 return VisitCXXConstructExpr(cast<CXXConstructExpr>(S), asc); 1447 1448 case Stmt::CXXNewExprClass: 1449 return VisitCXXNewExpr(cast<CXXNewExpr>(S), asc); 1450 1451 case Stmt::CXXDeleteExprClass: 1452 return VisitCXXDeleteExpr(cast<CXXDeleteExpr>(S), asc); 1453 1454 case Stmt::CXXFunctionalCastExprClass: 1455 return VisitCXXFunctionalCastExpr(cast<CXXFunctionalCastExpr>(S), asc); 1456 1457 case Stmt::CXXTemporaryObjectExprClass: 1458 return VisitCXXTemporaryObjectExpr(cast<CXXTemporaryObjectExpr>(S), asc); 1459 1460 case Stmt::CXXThrowExprClass: 1461 return VisitCXXThrowExpr(cast<CXXThrowExpr>(S)); 1462 1463 case Stmt::CXXTryStmtClass: 1464 return VisitCXXTryStmt(cast<CXXTryStmt>(S)); 1465 1466 case Stmt::CXXForRangeStmtClass: 1467 return VisitCXXForRangeStmt(cast<CXXForRangeStmt>(S)); 1468 1469 case Stmt::DeclStmtClass: 1470 return VisitDeclStmt(cast<DeclStmt>(S)); 1471 1472 case Stmt::DefaultStmtClass: 1473 return VisitDefaultStmt(cast<DefaultStmt>(S)); 1474 1475 case Stmt::DoStmtClass: 1476 return VisitDoStmt(cast<DoStmt>(S)); 1477 1478 case Stmt::ForStmtClass: 1479 return VisitForStmt(cast<ForStmt>(S)); 1480 1481 case Stmt::GotoStmtClass: 1482 return VisitGotoStmt(cast<GotoStmt>(S)); 1483 1484 case Stmt::IfStmtClass: 1485 return VisitIfStmt(cast<IfStmt>(S)); 1486 1487 case Stmt::ImplicitCastExprClass: 1488 return VisitImplicitCastExpr(cast<ImplicitCastExpr>(S), asc); 1489 1490 case Stmt::IndirectGotoStmtClass: 1491 return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S)); 1492 1493 case Stmt::LabelStmtClass: 1494 return VisitLabelStmt(cast<LabelStmt>(S)); 1495 1496 case Stmt::LambdaExprClass: 1497 return VisitLambdaExpr(cast<LambdaExpr>(S), asc); 1498 1499 case Stmt::MemberExprClass: 1500 return VisitMemberExpr(cast<MemberExpr>(S), asc); 1501 1502 case Stmt::NullStmtClass: 1503 return Block; 1504 1505 case Stmt::ObjCAtCatchStmtClass: 1506 return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S)); 1507 1508 case Stmt::ObjCAutoreleasePoolStmtClass: 1509 return VisitObjCAutoreleasePoolStmt(cast<ObjCAutoreleasePoolStmt>(S)); 1510 1511 case Stmt::ObjCAtSynchronizedStmtClass: 1512 return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S)); 1513 1514 case Stmt::ObjCAtThrowStmtClass: 1515 return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S)); 1516 1517 case Stmt::ObjCAtTryStmtClass: 1518 return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S)); 1519 1520 case Stmt::ObjCForCollectionStmtClass: 1521 return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S)); 1522 1523 case Stmt::OpaqueValueExprClass: 1524 return Block; 1525 1526 case Stmt::PseudoObjectExprClass: 1527 return VisitPseudoObjectExpr(cast<PseudoObjectExpr>(S)); 1528 1529 case Stmt::ReturnStmtClass: 1530 return VisitReturnStmt(cast<ReturnStmt>(S)); 1531 1532 case Stmt::UnaryExprOrTypeTraitExprClass: 1533 return VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S), 1534 asc); 1535 1536 case Stmt::StmtExprClass: 1537 return VisitStmtExpr(cast<StmtExpr>(S), asc); 1538 1539 case Stmt::SwitchStmtClass: 1540 return VisitSwitchStmt(cast<SwitchStmt>(S)); 1541 1542 case Stmt::UnaryOperatorClass: 1543 return VisitUnaryOperator(cast<UnaryOperator>(S), asc); 1544 1545 case Stmt::WhileStmtClass: 1546 return VisitWhileStmt(cast<WhileStmt>(S)); 1547 } 1548 } 1549 1550 CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) { 1551 if (asc.alwaysAdd(*this, S)) { 1552 autoCreateBlock(); 1553 appendStmt(Block, S); 1554 } 1555 1556 return VisitChildren(S); 1557 } 1558 1559 /// VisitChildren - Visit the children of a Stmt. 1560 CFGBlock *CFGBuilder::VisitChildren(Stmt *S) { 1561 CFGBlock *B = Block; 1562 1563 // Visit the children in their reverse order so that they appear in 1564 // left-to-right (natural) order in the CFG. 1565 reverse_children RChildren(S); 1566 for (reverse_children::iterator I = RChildren.begin(), E = RChildren.end(); 1567 I != E; ++I) { 1568 if (Stmt *Child = *I) 1569 if (CFGBlock *R = Visit(Child)) 1570 B = R; 1571 } 1572 return B; 1573 } 1574 1575 CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A, 1576 AddStmtChoice asc) { 1577 AddressTakenLabels.insert(A->getLabel()); 1578 1579 if (asc.alwaysAdd(*this, A)) { 1580 autoCreateBlock(); 1581 appendStmt(Block, A); 1582 } 1583 1584 return Block; 1585 } 1586 1587 CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U, 1588 AddStmtChoice asc) { 1589 if (asc.alwaysAdd(*this, U)) { 1590 autoCreateBlock(); 1591 appendStmt(Block, U); 1592 } 1593 1594 return Visit(U->getSubExpr(), AddStmtChoice()); 1595 } 1596 1597 CFGBlock *CFGBuilder::VisitLogicalOperator(BinaryOperator *B) { 1598 CFGBlock *ConfluenceBlock = Block ? Block : createBlock(); 1599 appendStmt(ConfluenceBlock, B); 1600 1601 if (badCFG) 1602 return nullptr; 1603 1604 return VisitLogicalOperator(B, nullptr, ConfluenceBlock, 1605 ConfluenceBlock).first; 1606 } 1607 1608 std::pair<CFGBlock*, CFGBlock*> 1609 CFGBuilder::VisitLogicalOperator(BinaryOperator *B, 1610 Stmt *Term, 1611 CFGBlock *TrueBlock, 1612 CFGBlock *FalseBlock) { 1613 1614 // Introspect the RHS. If it is a nested logical operation, we recursively 1615 // build the CFG using this function. Otherwise, resort to default 1616 // CFG construction behavior. 1617 Expr *RHS = B->getRHS()->IgnoreParens(); 1618 CFGBlock *RHSBlock, *ExitBlock; 1619 1620 do { 1621 if (BinaryOperator *B_RHS = dyn_cast<BinaryOperator>(RHS)) 1622 if (B_RHS->isLogicalOp()) { 1623 std::tie(RHSBlock, ExitBlock) = 1624 VisitLogicalOperator(B_RHS, Term, TrueBlock, FalseBlock); 1625 break; 1626 } 1627 1628 // The RHS is not a nested logical operation. Don't push the terminator 1629 // down further, but instead visit RHS and construct the respective 1630 // pieces of the CFG, and link up the RHSBlock with the terminator 1631 // we have been provided. 1632 ExitBlock = RHSBlock = createBlock(false); 1633 1634 if (!Term) { 1635 assert(TrueBlock == FalseBlock); 1636 addSuccessor(RHSBlock, TrueBlock); 1637 } 1638 else { 1639 RHSBlock->setTerminator(Term); 1640 TryResult KnownVal = tryEvaluateBool(RHS); 1641 if (!KnownVal.isKnown()) 1642 KnownVal = tryEvaluateBool(B); 1643 addSuccessor(RHSBlock, TrueBlock, !KnownVal.isFalse()); 1644 addSuccessor(RHSBlock, FalseBlock, !KnownVal.isTrue()); 1645 } 1646 1647 Block = RHSBlock; 1648 RHSBlock = addStmt(RHS); 1649 } 1650 while (false); 1651 1652 if (badCFG) 1653 return std::make_pair(nullptr, nullptr); 1654 1655 // Generate the blocks for evaluating the LHS. 1656 Expr *LHS = B->getLHS()->IgnoreParens(); 1657 1658 if (BinaryOperator *B_LHS = dyn_cast<BinaryOperator>(LHS)) 1659 if (B_LHS->isLogicalOp()) { 1660 if (B->getOpcode() == BO_LOr) 1661 FalseBlock = RHSBlock; 1662 else 1663 TrueBlock = RHSBlock; 1664 1665 // For the LHS, treat 'B' as the terminator that we want to sink 1666 // into the nested branch. The RHS always gets the top-most 1667 // terminator. 1668 return VisitLogicalOperator(B_LHS, B, TrueBlock, FalseBlock); 1669 } 1670 1671 // Create the block evaluating the LHS. 1672 // This contains the '&&' or '||' as the terminator. 1673 CFGBlock *LHSBlock = createBlock(false); 1674 LHSBlock->setTerminator(B); 1675 1676 Block = LHSBlock; 1677 CFGBlock *EntryLHSBlock = addStmt(LHS); 1678 1679 if (badCFG) 1680 return std::make_pair(nullptr, nullptr); 1681 1682 // See if this is a known constant. 1683 TryResult KnownVal = tryEvaluateBool(LHS); 1684 1685 // Now link the LHSBlock with RHSBlock. 1686 if (B->getOpcode() == BO_LOr) { 1687 addSuccessor(LHSBlock, TrueBlock, !KnownVal.isFalse()); 1688 addSuccessor(LHSBlock, RHSBlock, !KnownVal.isTrue()); 1689 } else { 1690 assert(B->getOpcode() == BO_LAnd); 1691 addSuccessor(LHSBlock, RHSBlock, !KnownVal.isFalse()); 1692 addSuccessor(LHSBlock, FalseBlock, !KnownVal.isTrue()); 1693 } 1694 1695 return std::make_pair(EntryLHSBlock, ExitBlock); 1696 } 1697 1698 1699 CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, 1700 AddStmtChoice asc) { 1701 // && or || 1702 if (B->isLogicalOp()) 1703 return VisitLogicalOperator(B); 1704 1705 if (B->getOpcode() == BO_Comma) { // , 1706 autoCreateBlock(); 1707 appendStmt(Block, B); 1708 addStmt(B->getRHS()); 1709 return addStmt(B->getLHS()); 1710 } 1711 1712 if (B->isAssignmentOp()) { 1713 if (asc.alwaysAdd(*this, B)) { 1714 autoCreateBlock(); 1715 appendStmt(Block, B); 1716 } 1717 Visit(B->getLHS()); 1718 return Visit(B->getRHS()); 1719 } 1720 1721 if (asc.alwaysAdd(*this, B)) { 1722 autoCreateBlock(); 1723 appendStmt(Block, B); 1724 } 1725 1726 CFGBlock *RBlock = Visit(B->getRHS()); 1727 CFGBlock *LBlock = Visit(B->getLHS()); 1728 // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr 1729 // containing a DoStmt, and the LHS doesn't create a new block, then we should 1730 // return RBlock. Otherwise we'll incorrectly return NULL. 1731 return (LBlock ? LBlock : RBlock); 1732 } 1733 1734 CFGBlock *CFGBuilder::VisitNoRecurse(Expr *E, AddStmtChoice asc) { 1735 if (asc.alwaysAdd(*this, E)) { 1736 autoCreateBlock(); 1737 appendStmt(Block, E); 1738 } 1739 return Block; 1740 } 1741 1742 CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) { 1743 // "break" is a control-flow statement. Thus we stop processing the current 1744 // block. 1745 if (badCFG) 1746 return nullptr; 1747 1748 // Now create a new block that ends with the break statement. 1749 Block = createBlock(false); 1750 Block->setTerminator(B); 1751 1752 // If there is no target for the break, then we are looking at an incomplete 1753 // AST. This means that the CFG cannot be constructed. 1754 if (BreakJumpTarget.block) { 1755 addAutomaticObjDtors(ScopePos, BreakJumpTarget.scopePosition, B); 1756 addSuccessor(Block, BreakJumpTarget.block); 1757 } else 1758 badCFG = true; 1759 1760 1761 return Block; 1762 } 1763 1764 static bool CanThrow(Expr *E, ASTContext &Ctx) { 1765 QualType Ty = E->getType(); 1766 if (Ty->isFunctionPointerType()) 1767 Ty = Ty->getAs<PointerType>()->getPointeeType(); 1768 else if (Ty->isBlockPointerType()) 1769 Ty = Ty->getAs<BlockPointerType>()->getPointeeType(); 1770 1771 const FunctionType *FT = Ty->getAs<FunctionType>(); 1772 if (FT) { 1773 if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT)) 1774 if (!isUnresolvedExceptionSpec(Proto->getExceptionSpecType()) && 1775 Proto->isNothrow(Ctx)) 1776 return false; 1777 } 1778 return true; 1779 } 1780 1781 CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { 1782 // Compute the callee type. 1783 QualType calleeType = C->getCallee()->getType(); 1784 if (calleeType == Context->BoundMemberTy) { 1785 QualType boundType = Expr::findBoundMemberType(C->getCallee()); 1786 1787 // We should only get a null bound type if processing a dependent 1788 // CFG. Recover by assuming nothing. 1789 if (!boundType.isNull()) calleeType = boundType; 1790 } 1791 1792 // If this is a call to a no-return function, this stops the block here. 1793 bool NoReturn = getFunctionExtInfo(*calleeType).getNoReturn(); 1794 1795 bool AddEHEdge = false; 1796 1797 // Languages without exceptions are assumed to not throw. 1798 if (Context->getLangOpts().Exceptions) { 1799 if (BuildOpts.AddEHEdges) 1800 AddEHEdge = true; 1801 } 1802 1803 // If this is a call to a builtin function, it might not actually evaluate 1804 // its arguments. Don't add them to the CFG if this is the case. 1805 bool OmitArguments = false; 1806 1807 if (FunctionDecl *FD = C->getDirectCallee()) { 1808 if (FD->isNoReturn()) 1809 NoReturn = true; 1810 if (FD->hasAttr<NoThrowAttr>()) 1811 AddEHEdge = false; 1812 if (FD->getBuiltinID() == Builtin::BI__builtin_object_size) 1813 OmitArguments = true; 1814 } 1815 1816 if (!CanThrow(C->getCallee(), *Context)) 1817 AddEHEdge = false; 1818 1819 if (OmitArguments) { 1820 assert(!NoReturn && "noreturn calls with unevaluated args not implemented"); 1821 assert(!AddEHEdge && "EH calls with unevaluated args not implemented"); 1822 autoCreateBlock(); 1823 appendStmt(Block, C); 1824 return Visit(C->getCallee()); 1825 } 1826 1827 if (!NoReturn && !AddEHEdge) { 1828 return VisitStmt(C, asc.withAlwaysAdd(true)); 1829 } 1830 1831 if (Block) { 1832 Succ = Block; 1833 if (badCFG) 1834 return nullptr; 1835 } 1836 1837 if (NoReturn) 1838 Block = createNoReturnBlock(); 1839 else 1840 Block = createBlock(); 1841 1842 appendStmt(Block, C); 1843 1844 if (AddEHEdge) { 1845 // Add exceptional edges. 1846 if (TryTerminatedBlock) 1847 addSuccessor(Block, TryTerminatedBlock); 1848 else 1849 addSuccessor(Block, &cfg->getExit()); 1850 } 1851 1852 return VisitChildren(C); 1853 } 1854 1855 CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C, 1856 AddStmtChoice asc) { 1857 CFGBlock *ConfluenceBlock = Block ? Block : createBlock(); 1858 appendStmt(ConfluenceBlock, C); 1859 if (badCFG) 1860 return nullptr; 1861 1862 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true); 1863 Succ = ConfluenceBlock; 1864 Block = nullptr; 1865 CFGBlock *LHSBlock = Visit(C->getLHS(), alwaysAdd); 1866 if (badCFG) 1867 return nullptr; 1868 1869 Succ = ConfluenceBlock; 1870 Block = nullptr; 1871 CFGBlock *RHSBlock = Visit(C->getRHS(), alwaysAdd); 1872 if (badCFG) 1873 return nullptr; 1874 1875 Block = createBlock(false); 1876 // See if this is a known constant. 1877 const TryResult& KnownVal = tryEvaluateBool(C->getCond()); 1878 addSuccessor(Block, KnownVal.isFalse() ? nullptr : LHSBlock); 1879 addSuccessor(Block, KnownVal.isTrue() ? nullptr : RHSBlock); 1880 Block->setTerminator(C); 1881 return addStmt(C->getCond()); 1882 } 1883 1884 1885 CFGBlock *CFGBuilder::VisitCompoundStmt(CompoundStmt *C) { 1886 addLocalScopeAndDtors(C); 1887 CFGBlock *LastBlock = Block; 1888 1889 for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); 1890 I != E; ++I ) { 1891 // If we hit a segment of code just containing ';' (NullStmts), we can 1892 // get a null block back. In such cases, just use the LastBlock 1893 if (CFGBlock *newBlock = addStmt(*I)) 1894 LastBlock = newBlock; 1895 1896 if (badCFG) 1897 return nullptr; 1898 } 1899 1900 return LastBlock; 1901 } 1902 1903 CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C, 1904 AddStmtChoice asc) { 1905 const BinaryConditionalOperator *BCO = dyn_cast<BinaryConditionalOperator>(C); 1906 const OpaqueValueExpr *opaqueValue = (BCO ? BCO->getOpaqueValue() : nullptr); 1907 1908 // Create the confluence block that will "merge" the results of the ternary 1909 // expression. 1910 CFGBlock *ConfluenceBlock = Block ? Block : createBlock(); 1911 appendStmt(ConfluenceBlock, C); 1912 if (badCFG) 1913 return nullptr; 1914 1915 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true); 1916 1917 // Create a block for the LHS expression if there is an LHS expression. A 1918 // GCC extension allows LHS to be NULL, causing the condition to be the 1919 // value that is returned instead. 1920 // e.g: x ?: y is shorthand for: x ? x : y; 1921 Succ = ConfluenceBlock; 1922 Block = nullptr; 1923 CFGBlock *LHSBlock = nullptr; 1924 const Expr *trueExpr = C->getTrueExpr(); 1925 if (trueExpr != opaqueValue) { 1926 LHSBlock = Visit(C->getTrueExpr(), alwaysAdd); 1927 if (badCFG) 1928 return nullptr; 1929 Block = nullptr; 1930 } 1931 else 1932 LHSBlock = ConfluenceBlock; 1933 1934 // Create the block for the RHS expression. 1935 Succ = ConfluenceBlock; 1936 CFGBlock *RHSBlock = Visit(C->getFalseExpr(), alwaysAdd); 1937 if (badCFG) 1938 return nullptr; 1939 1940 // If the condition is a logical '&&' or '||', build a more accurate CFG. 1941 if (BinaryOperator *Cond = 1942 dyn_cast<BinaryOperator>(C->getCond()->IgnoreParens())) 1943 if (Cond->isLogicalOp()) 1944 return VisitLogicalOperator(Cond, C, LHSBlock, RHSBlock).first; 1945 1946 // Create the block that will contain the condition. 1947 Block = createBlock(false); 1948 1949 // See if this is a known constant. 1950 const TryResult& KnownVal = tryEvaluateBool(C->getCond()); 1951 addSuccessor(Block, LHSBlock, !KnownVal.isFalse()); 1952 addSuccessor(Block, RHSBlock, !KnownVal.isTrue()); 1953 Block->setTerminator(C); 1954 Expr *condExpr = C->getCond(); 1955 1956 if (opaqueValue) { 1957 // Run the condition expression if it's not trivially expressed in 1958 // terms of the opaque value (or if there is no opaque value). 1959 if (condExpr != opaqueValue) 1960 addStmt(condExpr); 1961 1962 // Before that, run the common subexpression if there was one. 1963 // At least one of this or the above will be run. 1964 return addStmt(BCO->getCommon()); 1965 } 1966 1967 return addStmt(condExpr); 1968 } 1969 1970 CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) { 1971 // Check if the Decl is for an __label__. If so, elide it from the 1972 // CFG entirely. 1973 if (isa<LabelDecl>(*DS->decl_begin())) 1974 return Block; 1975 1976 // This case also handles static_asserts. 1977 if (DS->isSingleDecl()) 1978 return VisitDeclSubExpr(DS); 1979 1980 CFGBlock *B = nullptr; 1981 1982 // Build an individual DeclStmt for each decl. 1983 for (DeclStmt::reverse_decl_iterator I = DS->decl_rbegin(), 1984 E = DS->decl_rend(); 1985 I != E; ++I) { 1986 // Get the alignment of the new DeclStmt, padding out to >=8 bytes. 1987 unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8 1988 ? 8 : llvm::AlignOf<DeclStmt>::Alignment; 1989 1990 // Allocate the DeclStmt using the BumpPtrAllocator. It will get 1991 // automatically freed with the CFG. 1992 DeclGroupRef DG(*I); 1993 Decl *D = *I; 1994 void *Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A); 1995 DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D)); 1996 cfg->addSyntheticDeclStmt(DSNew, DS); 1997 1998 // Append the fake DeclStmt to block. 1999 B = VisitDeclSubExpr(DSNew); 2000 } 2001 2002 return B; 2003 } 2004 2005 /// VisitDeclSubExpr - Utility method to add block-level expressions for 2006 /// DeclStmts and initializers in them. 2007 CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) { 2008 assert(DS->isSingleDecl() && "Can handle single declarations only."); 2009 VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl()); 2010 2011 if (!VD) { 2012 // Of everything that can be declared in a DeclStmt, only VarDecls impact 2013 // runtime semantics. 2014 return Block; 2015 } 2016 2017 bool HasTemporaries = false; 2018 2019 // Guard static initializers under a branch. 2020 CFGBlock *blockAfterStaticInit = nullptr; 2021 2022 if (BuildOpts.AddStaticInitBranches && VD->isStaticLocal()) { 2023 // For static variables, we need to create a branch to track 2024 // whether or not they are initialized. 2025 if (Block) { 2026 Succ = Block; 2027 Block = nullptr; 2028 if (badCFG) 2029 return nullptr; 2030 } 2031 blockAfterStaticInit = Succ; 2032 } 2033 2034 // Destructors of temporaries in initialization expression should be called 2035 // after initialization finishes. 2036 Expr *Init = VD->getInit(); 2037 if (Init) { 2038 HasTemporaries = isa<ExprWithCleanups>(Init); 2039 2040 if (BuildOpts.AddTemporaryDtors && HasTemporaries) { 2041 // Generate destructors for temporaries in initialization expression. 2042 TempDtorContext Context; 2043 VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(), 2044 /*BindToTemporary=*/false, Context); 2045 } 2046 } 2047 2048 autoCreateBlock(); 2049 appendStmt(Block, DS); 2050 2051 // Keep track of the last non-null block, as 'Block' can be nulled out 2052 // if the initializer expression is something like a 'while' in a 2053 // statement-expression. 2054 CFGBlock *LastBlock = Block; 2055 2056 if (Init) { 2057 if (HasTemporaries) { 2058 // For expression with temporaries go directly to subexpression to omit 2059 // generating destructors for the second time. 2060 ExprWithCleanups *EC = cast<ExprWithCleanups>(Init); 2061 if (CFGBlock *newBlock = Visit(EC->getSubExpr())) 2062 LastBlock = newBlock; 2063 } 2064 else { 2065 if (CFGBlock *newBlock = Visit(Init)) 2066 LastBlock = newBlock; 2067 } 2068 } 2069 2070 // If the type of VD is a VLA, then we must process its size expressions. 2071 for (const VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); 2072 VA != nullptr; VA = FindVA(VA->getElementType().getTypePtr())) { 2073 if (CFGBlock *newBlock = addStmt(VA->getSizeExpr())) 2074 LastBlock = newBlock; 2075 } 2076 2077 // Remove variable from local scope. 2078 if (ScopePos && VD == *ScopePos) 2079 ++ScopePos; 2080 2081 CFGBlock *B = LastBlock; 2082 if (blockAfterStaticInit) { 2083 Succ = B; 2084 Block = createBlock(false); 2085 Block->setTerminator(DS); 2086 addSuccessor(Block, blockAfterStaticInit); 2087 addSuccessor(Block, B); 2088 B = Block; 2089 } 2090 2091 return B; 2092 } 2093 2094 CFGBlock *CFGBuilder::VisitIfStmt(IfStmt *I) { 2095 // We may see an if statement in the middle of a basic block, or it may be the 2096 // first statement we are processing. In either case, we create a new basic 2097 // block. First, we create the blocks for the then...else statements, and 2098 // then we create the block containing the if statement. If we were in the 2099 // middle of a block, we stop processing that block. That block is then the 2100 // implicit successor for the "then" and "else" clauses. 2101 2102 // Save local scope position because in case of condition variable ScopePos 2103 // won't be restored when traversing AST. 2104 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 2105 2106 // Create local scope for possible condition variable. 2107 // Store scope position. Add implicit destructor. 2108 if (VarDecl *VD = I->getConditionVariable()) { 2109 LocalScope::const_iterator BeginScopePos = ScopePos; 2110 addLocalScopeForVarDecl(VD); 2111 addAutomaticObjDtors(ScopePos, BeginScopePos, I); 2112 } 2113 2114 // The block we were processing is now finished. Make it the successor 2115 // block. 2116 if (Block) { 2117 Succ = Block; 2118 if (badCFG) 2119 return nullptr; 2120 } 2121 2122 // Process the false branch. 2123 CFGBlock *ElseBlock = Succ; 2124 2125 if (Stmt *Else = I->getElse()) { 2126 SaveAndRestore<CFGBlock*> sv(Succ); 2127 2128 // NULL out Block so that the recursive call to Visit will 2129 // create a new basic block. 2130 Block = nullptr; 2131 2132 // If branch is not a compound statement create implicit scope 2133 // and add destructors. 2134 if (!isa<CompoundStmt>(Else)) 2135 addLocalScopeAndDtors(Else); 2136 2137 ElseBlock = addStmt(Else); 2138 2139 if (!ElseBlock) // Can occur when the Else body has all NullStmts. 2140 ElseBlock = sv.get(); 2141 else if (Block) { 2142 if (badCFG) 2143 return nullptr; 2144 } 2145 } 2146 2147 // Process the true branch. 2148 CFGBlock *ThenBlock; 2149 { 2150 Stmt *Then = I->getThen(); 2151 assert(Then); 2152 SaveAndRestore<CFGBlock*> sv(Succ); 2153 Block = nullptr; 2154 2155 // If branch is not a compound statement create implicit scope 2156 // and add destructors. 2157 if (!isa<CompoundStmt>(Then)) 2158 addLocalScopeAndDtors(Then); 2159 2160 ThenBlock = addStmt(Then); 2161 2162 if (!ThenBlock) { 2163 // We can reach here if the "then" body has all NullStmts. 2164 // Create an empty block so we can distinguish between true and false 2165 // branches in path-sensitive analyses. 2166 ThenBlock = createBlock(false); 2167 addSuccessor(ThenBlock, sv.get()); 2168 } else if (Block) { 2169 if (badCFG) 2170 return nullptr; 2171 } 2172 } 2173 2174 // Specially handle "if (expr1 || ...)" and "if (expr1 && ...)" by 2175 // having these handle the actual control-flow jump. Note that 2176 // if we introduce a condition variable, e.g. "if (int x = exp1 || exp2)" 2177 // we resort to the old control-flow behavior. This special handling 2178 // removes infeasible paths from the control-flow graph by having the 2179 // control-flow transfer of '&&' or '||' go directly into the then/else 2180 // blocks directly. 2181 if (!I->getConditionVariable()) 2182 if (BinaryOperator *Cond = 2183 dyn_cast<BinaryOperator>(I->getCond()->IgnoreParens())) 2184 if (Cond->isLogicalOp()) 2185 return VisitLogicalOperator(Cond, I, ThenBlock, ElseBlock).first; 2186 2187 // Now create a new block containing the if statement. 2188 Block = createBlock(false); 2189 2190 // Set the terminator of the new block to the If statement. 2191 Block->setTerminator(I); 2192 2193 // See if this is a known constant. 2194 const TryResult &KnownVal = tryEvaluateBool(I->getCond()); 2195 2196 // Add the successors. If we know that specific branches are 2197 // unreachable, inform addSuccessor() of that knowledge. 2198 addSuccessor(Block, ThenBlock, /* isReachable = */ !KnownVal.isFalse()); 2199 addSuccessor(Block, ElseBlock, /* isReachable = */ !KnownVal.isTrue()); 2200 2201 // Add the condition as the last statement in the new block. This may create 2202 // new blocks as the condition may contain control-flow. Any newly created 2203 // blocks will be pointed to be "Block". 2204 CFGBlock *LastBlock = addStmt(I->getCond()); 2205 2206 // Finally, if the IfStmt contains a condition variable, add it and its 2207 // initializer to the CFG. 2208 if (const DeclStmt* DS = I->getConditionVariableDeclStmt()) { 2209 autoCreateBlock(); 2210 LastBlock = addStmt(const_cast<DeclStmt *>(DS)); 2211 } 2212 2213 return LastBlock; 2214 } 2215 2216 2217 CFGBlock *CFGBuilder::VisitReturnStmt(ReturnStmt *R) { 2218 // If we were in the middle of a block we stop processing that block. 2219 // 2220 // NOTE: If a "return" appears in the middle of a block, this means that the 2221 // code afterwards is DEAD (unreachable). We still keep a basic block 2222 // for that code; a simple "mark-and-sweep" from the entry block will be 2223 // able to report such dead blocks. 2224 2225 // Create the new block. 2226 Block = createBlock(false); 2227 2228 addAutomaticObjDtors(ScopePos, LocalScope::const_iterator(), R); 2229 2230 // If the one of the destructors does not return, we already have the Exit 2231 // block as a successor. 2232 if (!Block->hasNoReturnElement()) 2233 addSuccessor(Block, &cfg->getExit()); 2234 2235 // Add the return statement to the block. This may create new blocks if R 2236 // contains control-flow (short-circuit operations). 2237 return VisitStmt(R, AddStmtChoice::AlwaysAdd); 2238 } 2239 2240 CFGBlock *CFGBuilder::VisitLabelStmt(LabelStmt *L) { 2241 // Get the block of the labeled statement. Add it to our map. 2242 addStmt(L->getSubStmt()); 2243 CFGBlock *LabelBlock = Block; 2244 2245 if (!LabelBlock) // This can happen when the body is empty, i.e. 2246 LabelBlock = createBlock(); // scopes that only contains NullStmts. 2247 2248 assert(LabelMap.find(L->getDecl()) == LabelMap.end() && 2249 "label already in map"); 2250 LabelMap[L->getDecl()] = JumpTarget(LabelBlock, ScopePos); 2251 2252 // Labels partition blocks, so this is the end of the basic block we were 2253 // processing (L is the block's label). Because this is label (and we have 2254 // already processed the substatement) there is no extra control-flow to worry 2255 // about. 2256 LabelBlock->setLabel(L); 2257 if (badCFG) 2258 return nullptr; 2259 2260 // We set Block to NULL to allow lazy creation of a new block (if necessary); 2261 Block = nullptr; 2262 2263 // This block is now the implicit successor of other blocks. 2264 Succ = LabelBlock; 2265 2266 return LabelBlock; 2267 } 2268 2269 CFGBlock *CFGBuilder::VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc) { 2270 CFGBlock *LastBlock = VisitNoRecurse(E, asc); 2271 for (LambdaExpr::capture_init_iterator it = E->capture_init_begin(), 2272 et = E->capture_init_end(); it != et; ++it) { 2273 if (Expr *Init = *it) { 2274 CFGBlock *Tmp = Visit(Init); 2275 if (Tmp) 2276 LastBlock = Tmp; 2277 } 2278 } 2279 return LastBlock; 2280 } 2281 2282 CFGBlock *CFGBuilder::VisitGotoStmt(GotoStmt *G) { 2283 // Goto is a control-flow statement. Thus we stop processing the current 2284 // block and create a new one. 2285 2286 Block = createBlock(false); 2287 Block->setTerminator(G); 2288 2289 // If we already know the mapping to the label block add the successor now. 2290 LabelMapTy::iterator I = LabelMap.find(G->getLabel()); 2291 2292 if (I == LabelMap.end()) 2293 // We will need to backpatch this block later. 2294 BackpatchBlocks.push_back(JumpSource(Block, ScopePos)); 2295 else { 2296 JumpTarget JT = I->second; 2297 addAutomaticObjDtors(ScopePos, JT.scopePosition, G); 2298 addSuccessor(Block, JT.block); 2299 } 2300 2301 return Block; 2302 } 2303 2304 CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) { 2305 CFGBlock *LoopSuccessor = nullptr; 2306 2307 // Save local scope position because in case of condition variable ScopePos 2308 // won't be restored when traversing AST. 2309 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 2310 2311 // Create local scope for init statement and possible condition variable. 2312 // Add destructor for init statement and condition variable. 2313 // Store scope position for continue statement. 2314 if (Stmt *Init = F->getInit()) 2315 addLocalScopeForStmt(Init); 2316 LocalScope::const_iterator LoopBeginScopePos = ScopePos; 2317 2318 if (VarDecl *VD = F->getConditionVariable()) 2319 addLocalScopeForVarDecl(VD); 2320 LocalScope::const_iterator ContinueScopePos = ScopePos; 2321 2322 addAutomaticObjDtors(ScopePos, save_scope_pos.get(), F); 2323 2324 // "for" is a control-flow statement. Thus we stop processing the current 2325 // block. 2326 if (Block) { 2327 if (badCFG) 2328 return nullptr; 2329 LoopSuccessor = Block; 2330 } else 2331 LoopSuccessor = Succ; 2332 2333 // Save the current value for the break targets. 2334 // All breaks should go to the code following the loop. 2335 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget); 2336 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 2337 2338 CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr; 2339 2340 // Now create the loop body. 2341 { 2342 assert(F->getBody()); 2343 2344 // Save the current values for Block, Succ, continue and break targets. 2345 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); 2346 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget); 2347 2348 // Create an empty block to represent the transition block for looping back 2349 // to the head of the loop. If we have increment code, it will 2350 // go in this block as well. 2351 Block = Succ = TransitionBlock = createBlock(false); 2352 TransitionBlock->setLoopTarget(F); 2353 2354 if (Stmt *I = F->getInc()) { 2355 // Generate increment code in its own basic block. This is the target of 2356 // continue statements. 2357 Succ = addStmt(I); 2358 } 2359 2360 // Finish up the increment (or empty) block if it hasn't been already. 2361 if (Block) { 2362 assert(Block == Succ); 2363 if (badCFG) 2364 return nullptr; 2365 Block = nullptr; 2366 } 2367 2368 // The starting block for the loop increment is the block that should 2369 // represent the 'loop target' for looping back to the start of the loop. 2370 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos); 2371 ContinueJumpTarget.block->setLoopTarget(F); 2372 2373 // Loop body should end with destructor of Condition variable (if any). 2374 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, F); 2375 2376 // If body is not a compound statement create implicit scope 2377 // and add destructors. 2378 if (!isa<CompoundStmt>(F->getBody())) 2379 addLocalScopeAndDtors(F->getBody()); 2380 2381 // Now populate the body block, and in the process create new blocks as we 2382 // walk the body of the loop. 2383 BodyBlock = addStmt(F->getBody()); 2384 2385 if (!BodyBlock) { 2386 // In the case of "for (...;...;...);" we can have a null BodyBlock. 2387 // Use the continue jump target as the proxy for the body. 2388 BodyBlock = ContinueJumpTarget.block; 2389 } 2390 else if (badCFG) 2391 return nullptr; 2392 } 2393 2394 // Because of short-circuit evaluation, the condition of the loop can span 2395 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 2396 // evaluate the condition. 2397 CFGBlock *EntryConditionBlock = nullptr, *ExitConditionBlock = nullptr; 2398 2399 do { 2400 Expr *C = F->getCond(); 2401 2402 // Specially handle logical operators, which have a slightly 2403 // more optimal CFG representation. 2404 if (BinaryOperator *Cond = 2405 dyn_cast_or_null<BinaryOperator>(C ? C->IgnoreParens() : nullptr)) 2406 if (Cond->isLogicalOp()) { 2407 std::tie(EntryConditionBlock, ExitConditionBlock) = 2408 VisitLogicalOperator(Cond, F, BodyBlock, LoopSuccessor); 2409 break; 2410 } 2411 2412 // The default case when not handling logical operators. 2413 EntryConditionBlock = ExitConditionBlock = createBlock(false); 2414 ExitConditionBlock->setTerminator(F); 2415 2416 // See if this is a known constant. 2417 TryResult KnownVal(true); 2418 2419 if (C) { 2420 // Now add the actual condition to the condition block. 2421 // Because the condition itself may contain control-flow, new blocks may 2422 // be created. Thus we update "Succ" after adding the condition. 2423 Block = ExitConditionBlock; 2424 EntryConditionBlock = addStmt(C); 2425 2426 // If this block contains a condition variable, add both the condition 2427 // variable and initializer to the CFG. 2428 if (VarDecl *VD = F->getConditionVariable()) { 2429 if (Expr *Init = VD->getInit()) { 2430 autoCreateBlock(); 2431 appendStmt(Block, F->getConditionVariableDeclStmt()); 2432 EntryConditionBlock = addStmt(Init); 2433 assert(Block == EntryConditionBlock); 2434 } 2435 } 2436 2437 if (Block && badCFG) 2438 return nullptr; 2439 2440 KnownVal = tryEvaluateBool(C); 2441 } 2442 2443 // Add the loop body entry as a successor to the condition. 2444 addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? nullptr : BodyBlock); 2445 // Link up the condition block with the code that follows the loop. (the 2446 // false branch). 2447 addSuccessor(ExitConditionBlock, 2448 KnownVal.isTrue() ? nullptr : LoopSuccessor); 2449 2450 } while (false); 2451 2452 // Link up the loop-back block to the entry condition block. 2453 addSuccessor(TransitionBlock, EntryConditionBlock); 2454 2455 // The condition block is the implicit successor for any code above the loop. 2456 Succ = EntryConditionBlock; 2457 2458 // If the loop contains initialization, create a new block for those 2459 // statements. This block can also contain statements that precede the loop. 2460 if (Stmt *I = F->getInit()) { 2461 Block = createBlock(); 2462 return addStmt(I); 2463 } 2464 2465 // There is no loop initialization. We are thus basically a while loop. 2466 // NULL out Block to force lazy block construction. 2467 Block = nullptr; 2468 Succ = EntryConditionBlock; 2469 return EntryConditionBlock; 2470 } 2471 2472 CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) { 2473 if (asc.alwaysAdd(*this, M)) { 2474 autoCreateBlock(); 2475 appendStmt(Block, M); 2476 } 2477 return Visit(M->getBase()); 2478 } 2479 2480 CFGBlock *CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt *S) { 2481 // Objective-C fast enumeration 'for' statements: 2482 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC 2483 // 2484 // for ( Type newVariable in collection_expression ) { statements } 2485 // 2486 // becomes: 2487 // 2488 // prologue: 2489 // 1. collection_expression 2490 // T. jump to loop_entry 2491 // loop_entry: 2492 // 1. side-effects of element expression 2493 // 1. ObjCForCollectionStmt [performs binding to newVariable] 2494 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil] 2495 // TB: 2496 // statements 2497 // T. jump to loop_entry 2498 // FB: 2499 // what comes after 2500 // 2501 // and 2502 // 2503 // Type existingItem; 2504 // for ( existingItem in expression ) { statements } 2505 // 2506 // becomes: 2507 // 2508 // the same with newVariable replaced with existingItem; the binding works 2509 // the same except that for one ObjCForCollectionStmt::getElement() returns 2510 // a DeclStmt and the other returns a DeclRefExpr. 2511 // 2512 2513 CFGBlock *LoopSuccessor = nullptr; 2514 2515 if (Block) { 2516 if (badCFG) 2517 return nullptr; 2518 LoopSuccessor = Block; 2519 Block = nullptr; 2520 } else 2521 LoopSuccessor = Succ; 2522 2523 // Build the condition blocks. 2524 CFGBlock *ExitConditionBlock = createBlock(false); 2525 2526 // Set the terminator for the "exit" condition block. 2527 ExitConditionBlock->setTerminator(S); 2528 2529 // The last statement in the block should be the ObjCForCollectionStmt, which 2530 // performs the actual binding to 'element' and determines if there are any 2531 // more items in the collection. 2532 appendStmt(ExitConditionBlock, S); 2533 Block = ExitConditionBlock; 2534 2535 // Walk the 'element' expression to see if there are any side-effects. We 2536 // generate new blocks as necessary. We DON'T add the statement by default to 2537 // the CFG unless it contains control-flow. 2538 CFGBlock *EntryConditionBlock = Visit(S->getElement(), 2539 AddStmtChoice::NotAlwaysAdd); 2540 if (Block) { 2541 if (badCFG) 2542 return nullptr; 2543 Block = nullptr; 2544 } 2545 2546 // The condition block is the implicit successor for the loop body as well as 2547 // any code above the loop. 2548 Succ = EntryConditionBlock; 2549 2550 // Now create the true branch. 2551 { 2552 // Save the current values for Succ, continue and break targets. 2553 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); 2554 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), 2555 save_break(BreakJumpTarget); 2556 2557 // Add an intermediate block between the BodyBlock and the 2558 // EntryConditionBlock to represent the "loop back" transition, for looping 2559 // back to the head of the loop. 2560 CFGBlock *LoopBackBlock = nullptr; 2561 Succ = LoopBackBlock = createBlock(); 2562 LoopBackBlock->setLoopTarget(S); 2563 2564 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 2565 ContinueJumpTarget = JumpTarget(Succ, ScopePos); 2566 2567 CFGBlock *BodyBlock = addStmt(S->getBody()); 2568 2569 if (!BodyBlock) 2570 BodyBlock = ContinueJumpTarget.block; // can happen for "for (X in Y) ;" 2571 else if (Block) { 2572 if (badCFG) 2573 return nullptr; 2574 } 2575 2576 // This new body block is a successor to our "exit" condition block. 2577 addSuccessor(ExitConditionBlock, BodyBlock); 2578 } 2579 2580 // Link up the condition block with the code that follows the loop. 2581 // (the false branch). 2582 addSuccessor(ExitConditionBlock, LoopSuccessor); 2583 2584 // Now create a prologue block to contain the collection expression. 2585 Block = createBlock(); 2586 return addStmt(S->getCollection()); 2587 } 2588 2589 CFGBlock *CFGBuilder::VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S) { 2590 // Inline the body. 2591 return addStmt(S->getSubStmt()); 2592 // TODO: consider adding cleanups for the end of @autoreleasepool scope. 2593 } 2594 2595 CFGBlock *CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S) { 2596 // FIXME: Add locking 'primitives' to CFG for @synchronized. 2597 2598 // Inline the body. 2599 CFGBlock *SyncBlock = addStmt(S->getSynchBody()); 2600 2601 // The sync body starts its own basic block. This makes it a little easier 2602 // for diagnostic clients. 2603 if (SyncBlock) { 2604 if (badCFG) 2605 return nullptr; 2606 2607 Block = nullptr; 2608 Succ = SyncBlock; 2609 } 2610 2611 // Add the @synchronized to the CFG. 2612 autoCreateBlock(); 2613 appendStmt(Block, S); 2614 2615 // Inline the sync expression. 2616 return addStmt(S->getSynchExpr()); 2617 } 2618 2619 CFGBlock *CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt *S) { 2620 // FIXME 2621 return NYS(); 2622 } 2623 2624 CFGBlock *CFGBuilder::VisitPseudoObjectExpr(PseudoObjectExpr *E) { 2625 autoCreateBlock(); 2626 2627 // Add the PseudoObject as the last thing. 2628 appendStmt(Block, E); 2629 2630 CFGBlock *lastBlock = Block; 2631 2632 // Before that, evaluate all of the semantics in order. In 2633 // CFG-land, that means appending them in reverse order. 2634 for (unsigned i = E->getNumSemanticExprs(); i != 0; ) { 2635 Expr *Semantic = E->getSemanticExpr(--i); 2636 2637 // If the semantic is an opaque value, we're being asked to bind 2638 // it to its source expression. 2639 if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic)) 2640 Semantic = OVE->getSourceExpr(); 2641 2642 if (CFGBlock *B = Visit(Semantic)) 2643 lastBlock = B; 2644 } 2645 2646 return lastBlock; 2647 } 2648 2649 CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) { 2650 CFGBlock *LoopSuccessor = nullptr; 2651 2652 // Save local scope position because in case of condition variable ScopePos 2653 // won't be restored when traversing AST. 2654 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 2655 2656 // Create local scope for possible condition variable. 2657 // Store scope position for continue statement. 2658 LocalScope::const_iterator LoopBeginScopePos = ScopePos; 2659 if (VarDecl *VD = W->getConditionVariable()) { 2660 addLocalScopeForVarDecl(VD); 2661 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W); 2662 } 2663 2664 // "while" is a control-flow statement. Thus we stop processing the current 2665 // block. 2666 if (Block) { 2667 if (badCFG) 2668 return nullptr; 2669 LoopSuccessor = Block; 2670 Block = nullptr; 2671 } else { 2672 LoopSuccessor = Succ; 2673 } 2674 2675 CFGBlock *BodyBlock = nullptr, *TransitionBlock = nullptr; 2676 2677 // Process the loop body. 2678 { 2679 assert(W->getBody()); 2680 2681 // Save the current values for Block, Succ, continue and break targets. 2682 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); 2683 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), 2684 save_break(BreakJumpTarget); 2685 2686 // Create an empty block to represent the transition block for looping back 2687 // to the head of the loop. 2688 Succ = TransitionBlock = createBlock(false); 2689 TransitionBlock->setLoopTarget(W); 2690 ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos); 2691 2692 // All breaks should go to the code following the loop. 2693 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 2694 2695 // Loop body should end with destructor of Condition variable (if any). 2696 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W); 2697 2698 // If body is not a compound statement create implicit scope 2699 // and add destructors. 2700 if (!isa<CompoundStmt>(W->getBody())) 2701 addLocalScopeAndDtors(W->getBody()); 2702 2703 // Create the body. The returned block is the entry to the loop body. 2704 BodyBlock = addStmt(W->getBody()); 2705 2706 if (!BodyBlock) 2707 BodyBlock = ContinueJumpTarget.block; // can happen for "while(...) ;" 2708 else if (Block && badCFG) 2709 return nullptr; 2710 } 2711 2712 // Because of short-circuit evaluation, the condition of the loop can span 2713 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 2714 // evaluate the condition. 2715 CFGBlock *EntryConditionBlock = nullptr, *ExitConditionBlock = nullptr; 2716 2717 do { 2718 Expr *C = W->getCond(); 2719 2720 // Specially handle logical operators, which have a slightly 2721 // more optimal CFG representation. 2722 if (BinaryOperator *Cond = dyn_cast<BinaryOperator>(C->IgnoreParens())) 2723 if (Cond->isLogicalOp()) { 2724 std::tie(EntryConditionBlock, ExitConditionBlock) = 2725 VisitLogicalOperator(Cond, W, BodyBlock, LoopSuccessor); 2726 break; 2727 } 2728 2729 // The default case when not handling logical operators. 2730 ExitConditionBlock = createBlock(false); 2731 ExitConditionBlock->setTerminator(W); 2732 2733 // Now add the actual condition to the condition block. 2734 // Because the condition itself may contain control-flow, new blocks may 2735 // be created. Thus we update "Succ" after adding the condition. 2736 Block = ExitConditionBlock; 2737 Block = EntryConditionBlock = addStmt(C); 2738 2739 // If this block contains a condition variable, add both the condition 2740 // variable and initializer to the CFG. 2741 if (VarDecl *VD = W->getConditionVariable()) { 2742 if (Expr *Init = VD->getInit()) { 2743 autoCreateBlock(); 2744 appendStmt(Block, W->getConditionVariableDeclStmt()); 2745 EntryConditionBlock = addStmt(Init); 2746 assert(Block == EntryConditionBlock); 2747 } 2748 } 2749 2750 if (Block && badCFG) 2751 return nullptr; 2752 2753 // See if this is a known constant. 2754 const TryResult& KnownVal = tryEvaluateBool(C); 2755 2756 // Add the loop body entry as a successor to the condition. 2757 addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? nullptr : BodyBlock); 2758 // Link up the condition block with the code that follows the loop. (the 2759 // false branch). 2760 addSuccessor(ExitConditionBlock, 2761 KnownVal.isTrue() ? nullptr : LoopSuccessor); 2762 2763 } while(false); 2764 2765 // Link up the loop-back block to the entry condition block. 2766 addSuccessor(TransitionBlock, EntryConditionBlock); 2767 2768 // There can be no more statements in the condition block since we loop back 2769 // to this block. NULL out Block to force lazy creation of another block. 2770 Block = nullptr; 2771 2772 // Return the condition block, which is the dominating block for the loop. 2773 Succ = EntryConditionBlock; 2774 return EntryConditionBlock; 2775 } 2776 2777 2778 CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt *S) { 2779 // FIXME: For now we pretend that @catch and the code it contains does not 2780 // exit. 2781 return Block; 2782 } 2783 2784 CFGBlock *CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt *S) { 2785 // FIXME: This isn't complete. We basically treat @throw like a return 2786 // statement. 2787 2788 // If we were in the middle of a block we stop processing that block. 2789 if (badCFG) 2790 return nullptr; 2791 2792 // Create the new block. 2793 Block = createBlock(false); 2794 2795 // The Exit block is the only successor. 2796 addSuccessor(Block, &cfg->getExit()); 2797 2798 // Add the statement to the block. This may create new blocks if S contains 2799 // control-flow (short-circuit operations). 2800 return VisitStmt(S, AddStmtChoice::AlwaysAdd); 2801 } 2802 2803 CFGBlock *CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr *T) { 2804 // If we were in the middle of a block we stop processing that block. 2805 if (badCFG) 2806 return nullptr; 2807 2808 // Create the new block. 2809 Block = createBlock(false); 2810 2811 if (TryTerminatedBlock) 2812 // The current try statement is the only successor. 2813 addSuccessor(Block, TryTerminatedBlock); 2814 else 2815 // otherwise the Exit block is the only successor. 2816 addSuccessor(Block, &cfg->getExit()); 2817 2818 // Add the statement to the block. This may create new blocks if S contains 2819 // control-flow (short-circuit operations). 2820 return VisitStmt(T, AddStmtChoice::AlwaysAdd); 2821 } 2822 2823 CFGBlock *CFGBuilder::VisitDoStmt(DoStmt *D) { 2824 CFGBlock *LoopSuccessor = nullptr; 2825 2826 // "do...while" is a control-flow statement. Thus we stop processing the 2827 // current block. 2828 if (Block) { 2829 if (badCFG) 2830 return nullptr; 2831 LoopSuccessor = Block; 2832 } else 2833 LoopSuccessor = Succ; 2834 2835 // Because of short-circuit evaluation, the condition of the loop can span 2836 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 2837 // evaluate the condition. 2838 CFGBlock *ExitConditionBlock = createBlock(false); 2839 CFGBlock *EntryConditionBlock = ExitConditionBlock; 2840 2841 // Set the terminator for the "exit" condition block. 2842 ExitConditionBlock->setTerminator(D); 2843 2844 // Now add the actual condition to the condition block. Because the condition 2845 // itself may contain control-flow, new blocks may be created. 2846 if (Stmt *C = D->getCond()) { 2847 Block = ExitConditionBlock; 2848 EntryConditionBlock = addStmt(C); 2849 if (Block) { 2850 if (badCFG) 2851 return nullptr; 2852 } 2853 } 2854 2855 // The condition block is the implicit successor for the loop body. 2856 Succ = EntryConditionBlock; 2857 2858 // See if this is a known constant. 2859 const TryResult &KnownVal = tryEvaluateBool(D->getCond()); 2860 2861 // Process the loop body. 2862 CFGBlock *BodyBlock = nullptr; 2863 { 2864 assert(D->getBody()); 2865 2866 // Save the current values for Block, Succ, and continue and break targets 2867 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); 2868 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), 2869 save_break(BreakJumpTarget); 2870 2871 // All continues within this loop should go to the condition block 2872 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos); 2873 2874 // All breaks should go to the code following the loop. 2875 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 2876 2877 // NULL out Block to force lazy instantiation of blocks for the body. 2878 Block = nullptr; 2879 2880 // If body is not a compound statement create implicit scope 2881 // and add destructors. 2882 if (!isa<CompoundStmt>(D->getBody())) 2883 addLocalScopeAndDtors(D->getBody()); 2884 2885 // Create the body. The returned block is the entry to the loop body. 2886 BodyBlock = addStmt(D->getBody()); 2887 2888 if (!BodyBlock) 2889 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)" 2890 else if (Block) { 2891 if (badCFG) 2892 return nullptr; 2893 } 2894 2895 if (!KnownVal.isFalse()) { 2896 // Add an intermediate block between the BodyBlock and the 2897 // ExitConditionBlock to represent the "loop back" transition. Create an 2898 // empty block to represent the transition block for looping back to the 2899 // head of the loop. 2900 // FIXME: Can we do this more efficiently without adding another block? 2901 Block = nullptr; 2902 Succ = BodyBlock; 2903 CFGBlock *LoopBackBlock = createBlock(); 2904 LoopBackBlock->setLoopTarget(D); 2905 2906 // Add the loop body entry as a successor to the condition. 2907 addSuccessor(ExitConditionBlock, LoopBackBlock); 2908 } 2909 else 2910 addSuccessor(ExitConditionBlock, nullptr); 2911 } 2912 2913 // Link up the condition block with the code that follows the loop. 2914 // (the false branch). 2915 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? nullptr : LoopSuccessor); 2916 2917 // There can be no more statements in the body block(s) since we loop back to 2918 // the body. NULL out Block to force lazy creation of another block. 2919 Block = nullptr; 2920 2921 // Return the loop body, which is the dominating block for the loop. 2922 Succ = BodyBlock; 2923 return BodyBlock; 2924 } 2925 2926 CFGBlock *CFGBuilder::VisitContinueStmt(ContinueStmt *C) { 2927 // "continue" is a control-flow statement. Thus we stop processing the 2928 // current block. 2929 if (badCFG) 2930 return nullptr; 2931 2932 // Now create a new block that ends with the continue statement. 2933 Block = createBlock(false); 2934 Block->setTerminator(C); 2935 2936 // If there is no target for the continue, then we are looking at an 2937 // incomplete AST. This means the CFG cannot be constructed. 2938 if (ContinueJumpTarget.block) { 2939 addAutomaticObjDtors(ScopePos, ContinueJumpTarget.scopePosition, C); 2940 addSuccessor(Block, ContinueJumpTarget.block); 2941 } else 2942 badCFG = true; 2943 2944 return Block; 2945 } 2946 2947 CFGBlock *CFGBuilder::VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E, 2948 AddStmtChoice asc) { 2949 2950 if (asc.alwaysAdd(*this, E)) { 2951 autoCreateBlock(); 2952 appendStmt(Block, E); 2953 } 2954 2955 // VLA types have expressions that must be evaluated. 2956 CFGBlock *lastBlock = Block; 2957 2958 if (E->isArgumentType()) { 2959 for (const VariableArrayType *VA =FindVA(E->getArgumentType().getTypePtr()); 2960 VA != nullptr; VA = FindVA(VA->getElementType().getTypePtr())) 2961 lastBlock = addStmt(VA->getSizeExpr()); 2962 } 2963 return lastBlock; 2964 } 2965 2966 /// VisitStmtExpr - Utility method to handle (nested) statement 2967 /// expressions (a GCC extension). 2968 CFGBlock *CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) { 2969 if (asc.alwaysAdd(*this, SE)) { 2970 autoCreateBlock(); 2971 appendStmt(Block, SE); 2972 } 2973 return VisitCompoundStmt(SE->getSubStmt()); 2974 } 2975 2976 CFGBlock *CFGBuilder::VisitSwitchStmt(SwitchStmt *Terminator) { 2977 // "switch" is a control-flow statement. Thus we stop processing the current 2978 // block. 2979 CFGBlock *SwitchSuccessor = nullptr; 2980 2981 // Save local scope position because in case of condition variable ScopePos 2982 // won't be restored when traversing AST. 2983 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 2984 2985 // Create local scope for possible condition variable. 2986 // Store scope position. Add implicit destructor. 2987 if (VarDecl *VD = Terminator->getConditionVariable()) { 2988 LocalScope::const_iterator SwitchBeginScopePos = ScopePos; 2989 addLocalScopeForVarDecl(VD); 2990 addAutomaticObjDtors(ScopePos, SwitchBeginScopePos, Terminator); 2991 } 2992 2993 if (Block) { 2994 if (badCFG) 2995 return nullptr; 2996 SwitchSuccessor = Block; 2997 } else SwitchSuccessor = Succ; 2998 2999 // Save the current "switch" context. 3000 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock), 3001 save_default(DefaultCaseBlock); 3002 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget); 3003 3004 // Set the "default" case to be the block after the switch statement. If the 3005 // switch statement contains a "default:", this value will be overwritten with 3006 // the block for that code. 3007 DefaultCaseBlock = SwitchSuccessor; 3008 3009 // Create a new block that will contain the switch statement. 3010 SwitchTerminatedBlock = createBlock(false); 3011 3012 // Now process the switch body. The code after the switch is the implicit 3013 // successor. 3014 Succ = SwitchSuccessor; 3015 BreakJumpTarget = JumpTarget(SwitchSuccessor, ScopePos); 3016 3017 // When visiting the body, the case statements should automatically get linked 3018 // up to the switch. We also don't keep a pointer to the body, since all 3019 // control-flow from the switch goes to case/default statements. 3020 assert(Terminator->getBody() && "switch must contain a non-NULL body"); 3021 Block = nullptr; 3022 3023 // For pruning unreachable case statements, save the current state 3024 // for tracking the condition value. 3025 SaveAndRestore<bool> save_switchExclusivelyCovered(switchExclusivelyCovered, 3026 false); 3027 3028 // Determine if the switch condition can be explicitly evaluated. 3029 assert(Terminator->getCond() && "switch condition must be non-NULL"); 3030 Expr::EvalResult result; 3031 bool b = tryEvaluate(Terminator->getCond(), result); 3032 SaveAndRestore<Expr::EvalResult*> save_switchCond(switchCond, 3033 b ? &result : nullptr); 3034 3035 // If body is not a compound statement create implicit scope 3036 // and add destructors. 3037 if (!isa<CompoundStmt>(Terminator->getBody())) 3038 addLocalScopeAndDtors(Terminator->getBody()); 3039 3040 addStmt(Terminator->getBody()); 3041 if (Block) { 3042 if (badCFG) 3043 return nullptr; 3044 } 3045 3046 // If we have no "default:" case, the default transition is to the code 3047 // following the switch body. Moreover, take into account if all the 3048 // cases of a switch are covered (e.g., switching on an enum value). 3049 // 3050 // Note: We add a successor to a switch that is considered covered yet has no 3051 // case statements if the enumeration has no enumerators. 3052 bool SwitchAlwaysHasSuccessor = false; 3053 SwitchAlwaysHasSuccessor |= switchExclusivelyCovered; 3054 SwitchAlwaysHasSuccessor |= Terminator->isAllEnumCasesCovered() && 3055 Terminator->getSwitchCaseList(); 3056 addSuccessor(SwitchTerminatedBlock, DefaultCaseBlock, 3057 !SwitchAlwaysHasSuccessor); 3058 3059 // Add the terminator and condition in the switch block. 3060 SwitchTerminatedBlock->setTerminator(Terminator); 3061 Block = SwitchTerminatedBlock; 3062 CFGBlock *LastBlock = addStmt(Terminator->getCond()); 3063 3064 // Finally, if the SwitchStmt contains a condition variable, add both the 3065 // SwitchStmt and the condition variable initialization to the CFG. 3066 if (VarDecl *VD = Terminator->getConditionVariable()) { 3067 if (Expr *Init = VD->getInit()) { 3068 autoCreateBlock(); 3069 appendStmt(Block, Terminator->getConditionVariableDeclStmt()); 3070 LastBlock = addStmt(Init); 3071 } 3072 } 3073 3074 return LastBlock; 3075 } 3076 3077 static bool shouldAddCase(bool &switchExclusivelyCovered, 3078 const Expr::EvalResult *switchCond, 3079 const CaseStmt *CS, 3080 ASTContext &Ctx) { 3081 if (!switchCond) 3082 return true; 3083 3084 bool addCase = false; 3085 3086 if (!switchExclusivelyCovered) { 3087 if (switchCond->Val.isInt()) { 3088 // Evaluate the LHS of the case value. 3089 const llvm::APSInt &lhsInt = CS->getLHS()->EvaluateKnownConstInt(Ctx); 3090 const llvm::APSInt &condInt = switchCond->Val.getInt(); 3091 3092 if (condInt == lhsInt) { 3093 addCase = true; 3094 switchExclusivelyCovered = true; 3095 } 3096 else if (condInt < lhsInt) { 3097 if (const Expr *RHS = CS->getRHS()) { 3098 // Evaluate the RHS of the case value. 3099 const llvm::APSInt &V2 = RHS->EvaluateKnownConstInt(Ctx); 3100 if (V2 <= condInt) { 3101 addCase = true; 3102 switchExclusivelyCovered = true; 3103 } 3104 } 3105 } 3106 } 3107 else 3108 addCase = true; 3109 } 3110 return addCase; 3111 } 3112 3113 CFGBlock *CFGBuilder::VisitCaseStmt(CaseStmt *CS) { 3114 // CaseStmts are essentially labels, so they are the first statement in a 3115 // block. 3116 CFGBlock *TopBlock = nullptr, *LastBlock = nullptr; 3117 3118 if (Stmt *Sub = CS->getSubStmt()) { 3119 // For deeply nested chains of CaseStmts, instead of doing a recursion 3120 // (which can blow out the stack), manually unroll and create blocks 3121 // along the way. 3122 while (isa<CaseStmt>(Sub)) { 3123 CFGBlock *currentBlock = createBlock(false); 3124 currentBlock->setLabel(CS); 3125 3126 if (TopBlock) 3127 addSuccessor(LastBlock, currentBlock); 3128 else 3129 TopBlock = currentBlock; 3130 3131 addSuccessor(SwitchTerminatedBlock, 3132 shouldAddCase(switchExclusivelyCovered, switchCond, 3133 CS, *Context) 3134 ? currentBlock : nullptr); 3135 3136 LastBlock = currentBlock; 3137 CS = cast<CaseStmt>(Sub); 3138 Sub = CS->getSubStmt(); 3139 } 3140 3141 addStmt(Sub); 3142 } 3143 3144 CFGBlock *CaseBlock = Block; 3145 if (!CaseBlock) 3146 CaseBlock = createBlock(); 3147 3148 // Cases statements partition blocks, so this is the top of the basic block we 3149 // were processing (the "case XXX:" is the label). 3150 CaseBlock->setLabel(CS); 3151 3152 if (badCFG) 3153 return nullptr; 3154 3155 // Add this block to the list of successors for the block with the switch 3156 // statement. 3157 assert(SwitchTerminatedBlock); 3158 addSuccessor(SwitchTerminatedBlock, CaseBlock, 3159 shouldAddCase(switchExclusivelyCovered, switchCond, 3160 CS, *Context)); 3161 3162 // We set Block to NULL to allow lazy creation of a new block (if necessary) 3163 Block = nullptr; 3164 3165 if (TopBlock) { 3166 addSuccessor(LastBlock, CaseBlock); 3167 Succ = TopBlock; 3168 } else { 3169 // This block is now the implicit successor of other blocks. 3170 Succ = CaseBlock; 3171 } 3172 3173 return Succ; 3174 } 3175 3176 CFGBlock *CFGBuilder::VisitDefaultStmt(DefaultStmt *Terminator) { 3177 if (Terminator->getSubStmt()) 3178 addStmt(Terminator->getSubStmt()); 3179 3180 DefaultCaseBlock = Block; 3181 3182 if (!DefaultCaseBlock) 3183 DefaultCaseBlock = createBlock(); 3184 3185 // Default statements partition blocks, so this is the top of the basic block 3186 // we were processing (the "default:" is the label). 3187 DefaultCaseBlock->setLabel(Terminator); 3188 3189 if (badCFG) 3190 return nullptr; 3191 3192 // Unlike case statements, we don't add the default block to the successors 3193 // for the switch statement immediately. This is done when we finish 3194 // processing the switch statement. This allows for the default case 3195 // (including a fall-through to the code after the switch statement) to always 3196 // be the last successor of a switch-terminated block. 3197 3198 // We set Block to NULL to allow lazy creation of a new block (if necessary) 3199 Block = nullptr; 3200 3201 // This block is now the implicit successor of other blocks. 3202 Succ = DefaultCaseBlock; 3203 3204 return DefaultCaseBlock; 3205 } 3206 3207 CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) { 3208 // "try"/"catch" is a control-flow statement. Thus we stop processing the 3209 // current block. 3210 CFGBlock *TrySuccessor = nullptr; 3211 3212 if (Block) { 3213 if (badCFG) 3214 return nullptr; 3215 TrySuccessor = Block; 3216 } else TrySuccessor = Succ; 3217 3218 CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock; 3219 3220 // Create a new block that will contain the try statement. 3221 CFGBlock *NewTryTerminatedBlock = createBlock(false); 3222 // Add the terminator in the try block. 3223 NewTryTerminatedBlock->setTerminator(Terminator); 3224 3225 bool HasCatchAll = false; 3226 for (unsigned h = 0; h <Terminator->getNumHandlers(); ++h) { 3227 // The code after the try is the implicit successor. 3228 Succ = TrySuccessor; 3229 CXXCatchStmt *CS = Terminator->getHandler(h); 3230 if (CS->getExceptionDecl() == nullptr) { 3231 HasCatchAll = true; 3232 } 3233 Block = nullptr; 3234 CFGBlock *CatchBlock = VisitCXXCatchStmt(CS); 3235 if (!CatchBlock) 3236 return nullptr; 3237 // Add this block to the list of successors for the block with the try 3238 // statement. 3239 addSuccessor(NewTryTerminatedBlock, CatchBlock); 3240 } 3241 if (!HasCatchAll) { 3242 if (PrevTryTerminatedBlock) 3243 addSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock); 3244 else 3245 addSuccessor(NewTryTerminatedBlock, &cfg->getExit()); 3246 } 3247 3248 // The code after the try is the implicit successor. 3249 Succ = TrySuccessor; 3250 3251 // Save the current "try" context. 3252 SaveAndRestore<CFGBlock*> save_try(TryTerminatedBlock, NewTryTerminatedBlock); 3253 cfg->addTryDispatchBlock(TryTerminatedBlock); 3254 3255 assert(Terminator->getTryBlock() && "try must contain a non-NULL body"); 3256 Block = nullptr; 3257 return addStmt(Terminator->getTryBlock()); 3258 } 3259 3260 CFGBlock *CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt *CS) { 3261 // CXXCatchStmt are treated like labels, so they are the first statement in a 3262 // block. 3263 3264 // Save local scope position because in case of exception variable ScopePos 3265 // won't be restored when traversing AST. 3266 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 3267 3268 // Create local scope for possible exception variable. 3269 // Store scope position. Add implicit destructor. 3270 if (VarDecl *VD = CS->getExceptionDecl()) { 3271 LocalScope::const_iterator BeginScopePos = ScopePos; 3272 addLocalScopeForVarDecl(VD); 3273 addAutomaticObjDtors(ScopePos, BeginScopePos, CS); 3274 } 3275 3276 if (CS->getHandlerBlock()) 3277 addStmt(CS->getHandlerBlock()); 3278 3279 CFGBlock *CatchBlock = Block; 3280 if (!CatchBlock) 3281 CatchBlock = createBlock(); 3282 3283 // CXXCatchStmt is more than just a label. They have semantic meaning 3284 // as well, as they implicitly "initialize" the catch variable. Add 3285 // it to the CFG as a CFGElement so that the control-flow of these 3286 // semantics gets captured. 3287 appendStmt(CatchBlock, CS); 3288 3289 // Also add the CXXCatchStmt as a label, to mirror handling of regular 3290 // labels. 3291 CatchBlock->setLabel(CS); 3292 3293 // Bail out if the CFG is bad. 3294 if (badCFG) 3295 return nullptr; 3296 3297 // We set Block to NULL to allow lazy creation of a new block (if necessary) 3298 Block = nullptr; 3299 3300 return CatchBlock; 3301 } 3302 3303 CFGBlock *CFGBuilder::VisitCXXForRangeStmt(CXXForRangeStmt *S) { 3304 // C++0x for-range statements are specified as [stmt.ranged]: 3305 // 3306 // { 3307 // auto && __range = range-init; 3308 // for ( auto __begin = begin-expr, 3309 // __end = end-expr; 3310 // __begin != __end; 3311 // ++__begin ) { 3312 // for-range-declaration = *__begin; 3313 // statement 3314 // } 3315 // } 3316 3317 // Save local scope position before the addition of the implicit variables. 3318 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 3319 3320 // Create local scopes and destructors for range, begin and end variables. 3321 if (Stmt *Range = S->getRangeStmt()) 3322 addLocalScopeForStmt(Range); 3323 if (Stmt *BeginEnd = S->getBeginEndStmt()) 3324 addLocalScopeForStmt(BeginEnd); 3325 addAutomaticObjDtors(ScopePos, save_scope_pos.get(), S); 3326 3327 LocalScope::const_iterator ContinueScopePos = ScopePos; 3328 3329 // "for" is a control-flow statement. Thus we stop processing the current 3330 // block. 3331 CFGBlock *LoopSuccessor = nullptr; 3332 if (Block) { 3333 if (badCFG) 3334 return nullptr; 3335 LoopSuccessor = Block; 3336 } else 3337 LoopSuccessor = Succ; 3338 3339 // Save the current value for the break targets. 3340 // All breaks should go to the code following the loop. 3341 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget); 3342 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 3343 3344 // The block for the __begin != __end expression. 3345 CFGBlock *ConditionBlock = createBlock(false); 3346 ConditionBlock->setTerminator(S); 3347 3348 // Now add the actual condition to the condition block. 3349 if (Expr *C = S->getCond()) { 3350 Block = ConditionBlock; 3351 CFGBlock *BeginConditionBlock = addStmt(C); 3352 if (badCFG) 3353 return nullptr; 3354 assert(BeginConditionBlock == ConditionBlock && 3355 "condition block in for-range was unexpectedly complex"); 3356 (void)BeginConditionBlock; 3357 } 3358 3359 // The condition block is the implicit successor for the loop body as well as 3360 // any code above the loop. 3361 Succ = ConditionBlock; 3362 3363 // See if this is a known constant. 3364 TryResult KnownVal(true); 3365 3366 if (S->getCond()) 3367 KnownVal = tryEvaluateBool(S->getCond()); 3368 3369 // Now create the loop body. 3370 { 3371 assert(S->getBody()); 3372 3373 // Save the current values for Block, Succ, and continue targets. 3374 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); 3375 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget); 3376 3377 // Generate increment code in its own basic block. This is the target of 3378 // continue statements. 3379 Block = nullptr; 3380 Succ = addStmt(S->getInc()); 3381 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos); 3382 3383 // The starting block for the loop increment is the block that should 3384 // represent the 'loop target' for looping back to the start of the loop. 3385 ContinueJumpTarget.block->setLoopTarget(S); 3386 3387 // Finish up the increment block and prepare to start the loop body. 3388 assert(Block); 3389 if (badCFG) 3390 return nullptr; 3391 Block = nullptr; 3392 3393 // Add implicit scope and dtors for loop variable. 3394 addLocalScopeAndDtors(S->getLoopVarStmt()); 3395 3396 // Populate a new block to contain the loop body and loop variable. 3397 addStmt(S->getBody()); 3398 if (badCFG) 3399 return nullptr; 3400 CFGBlock *LoopVarStmtBlock = addStmt(S->getLoopVarStmt()); 3401 if (badCFG) 3402 return nullptr; 3403 3404 // This new body block is a successor to our condition block. 3405 addSuccessor(ConditionBlock, 3406 KnownVal.isFalse() ? nullptr : LoopVarStmtBlock); 3407 } 3408 3409 // Link up the condition block with the code that follows the loop (the 3410 // false branch). 3411 addSuccessor(ConditionBlock, KnownVal.isTrue() ? nullptr : LoopSuccessor); 3412 3413 // Add the initialization statements. 3414 Block = createBlock(); 3415 addStmt(S->getBeginEndStmt()); 3416 return addStmt(S->getRangeStmt()); 3417 } 3418 3419 CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E, 3420 AddStmtChoice asc) { 3421 if (BuildOpts.AddTemporaryDtors) { 3422 // If adding implicit destructors visit the full expression for adding 3423 // destructors of temporaries. 3424 TempDtorContext Context; 3425 VisitForTemporaryDtors(E->getSubExpr(), false, Context); 3426 3427 // Full expression has to be added as CFGStmt so it will be sequenced 3428 // before destructors of it's temporaries. 3429 asc = asc.withAlwaysAdd(true); 3430 } 3431 return Visit(E->getSubExpr(), asc); 3432 } 3433 3434 CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E, 3435 AddStmtChoice asc) { 3436 if (asc.alwaysAdd(*this, E)) { 3437 autoCreateBlock(); 3438 appendStmt(Block, E); 3439 3440 // We do not want to propagate the AlwaysAdd property. 3441 asc = asc.withAlwaysAdd(false); 3442 } 3443 return Visit(E->getSubExpr(), asc); 3444 } 3445 3446 CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C, 3447 AddStmtChoice asc) { 3448 autoCreateBlock(); 3449 appendStmt(Block, C); 3450 3451 return VisitChildren(C); 3452 } 3453 3454 CFGBlock *CFGBuilder::VisitCXXNewExpr(CXXNewExpr *NE, 3455 AddStmtChoice asc) { 3456 3457 autoCreateBlock(); 3458 appendStmt(Block, NE); 3459 3460 if (NE->getInitializer()) 3461 Block = Visit(NE->getInitializer()); 3462 if (BuildOpts.AddCXXNewAllocator) 3463 appendNewAllocator(Block, NE); 3464 if (NE->isArray()) 3465 Block = Visit(NE->getArraySize()); 3466 for (CXXNewExpr::arg_iterator I = NE->placement_arg_begin(), 3467 E = NE->placement_arg_end(); I != E; ++I) 3468 Block = Visit(*I); 3469 return Block; 3470 } 3471 3472 CFGBlock *CFGBuilder::VisitCXXDeleteExpr(CXXDeleteExpr *DE, 3473 AddStmtChoice asc) { 3474 autoCreateBlock(); 3475 appendStmt(Block, DE); 3476 QualType DTy = DE->getDestroyedType(); 3477 DTy = DTy.getNonReferenceType(); 3478 CXXRecordDecl *RD = Context->getBaseElementType(DTy)->getAsCXXRecordDecl(); 3479 if (RD) { 3480 if (RD->isCompleteDefinition() && !RD->hasTrivialDestructor()) 3481 appendDeleteDtor(Block, RD, DE); 3482 } 3483 3484 return VisitChildren(DE); 3485 } 3486 3487 CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E, 3488 AddStmtChoice asc) { 3489 if (asc.alwaysAdd(*this, E)) { 3490 autoCreateBlock(); 3491 appendStmt(Block, E); 3492 // We do not want to propagate the AlwaysAdd property. 3493 asc = asc.withAlwaysAdd(false); 3494 } 3495 return Visit(E->getSubExpr(), asc); 3496 } 3497 3498 CFGBlock *CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C, 3499 AddStmtChoice asc) { 3500 autoCreateBlock(); 3501 appendStmt(Block, C); 3502 return VisitChildren(C); 3503 } 3504 3505 CFGBlock *CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr *E, 3506 AddStmtChoice asc) { 3507 if (asc.alwaysAdd(*this, E)) { 3508 autoCreateBlock(); 3509 appendStmt(Block, E); 3510 } 3511 return Visit(E->getSubExpr(), AddStmtChoice()); 3512 } 3513 3514 CFGBlock *CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt *I) { 3515 // Lazily create the indirect-goto dispatch block if there isn't one already. 3516 CFGBlock *IBlock = cfg->getIndirectGotoBlock(); 3517 3518 if (!IBlock) { 3519 IBlock = createBlock(false); 3520 cfg->setIndirectGotoBlock(IBlock); 3521 } 3522 3523 // IndirectGoto is a control-flow statement. Thus we stop processing the 3524 // current block and create a new one. 3525 if (badCFG) 3526 return nullptr; 3527 3528 Block = createBlock(false); 3529 Block->setTerminator(I); 3530 addSuccessor(Block, IBlock); 3531 return addStmt(I->getTarget()); 3532 } 3533 3534 CFGBlock *CFGBuilder::VisitForTemporaryDtors(Stmt *E, bool BindToTemporary, 3535 TempDtorContext &Context) { 3536 assert(BuildOpts.AddImplicitDtors && BuildOpts.AddTemporaryDtors); 3537 3538 tryAgain: 3539 if (!E) { 3540 badCFG = true; 3541 return nullptr; 3542 } 3543 switch (E->getStmtClass()) { 3544 default: 3545 return VisitChildrenForTemporaryDtors(E, Context); 3546 3547 case Stmt::BinaryOperatorClass: 3548 return VisitBinaryOperatorForTemporaryDtors(cast<BinaryOperator>(E), 3549 Context); 3550 3551 case Stmt::CXXBindTemporaryExprClass: 3552 return VisitCXXBindTemporaryExprForTemporaryDtors( 3553 cast<CXXBindTemporaryExpr>(E), BindToTemporary, Context); 3554 3555 case Stmt::BinaryConditionalOperatorClass: 3556 case Stmt::ConditionalOperatorClass: 3557 return VisitConditionalOperatorForTemporaryDtors( 3558 cast<AbstractConditionalOperator>(E), BindToTemporary, Context); 3559 3560 case Stmt::ImplicitCastExprClass: 3561 // For implicit cast we want BindToTemporary to be passed further. 3562 E = cast<CastExpr>(E)->getSubExpr(); 3563 goto tryAgain; 3564 3565 case Stmt::CXXFunctionalCastExprClass: 3566 // For functional cast we want BindToTemporary to be passed further. 3567 E = cast<CXXFunctionalCastExpr>(E)->getSubExpr(); 3568 goto tryAgain; 3569 3570 case Stmt::ParenExprClass: 3571 E = cast<ParenExpr>(E)->getSubExpr(); 3572 goto tryAgain; 3573 3574 case Stmt::MaterializeTemporaryExprClass: { 3575 const MaterializeTemporaryExpr* MTE = cast<MaterializeTemporaryExpr>(E); 3576 BindToTemporary = (MTE->getStorageDuration() != SD_FullExpression); 3577 SmallVector<const Expr *, 2> CommaLHSs; 3578 SmallVector<SubobjectAdjustment, 2> Adjustments; 3579 // Find the expression whose lifetime needs to be extended. 3580 E = const_cast<Expr *>( 3581 cast<MaterializeTemporaryExpr>(E) 3582 ->GetTemporaryExpr() 3583 ->skipRValueSubobjectAdjustments(CommaLHSs, Adjustments)); 3584 // Visit the skipped comma operator left-hand sides for other temporaries. 3585 for (const Expr *CommaLHS : CommaLHSs) { 3586 VisitForTemporaryDtors(const_cast<Expr *>(CommaLHS), 3587 /*BindToTemporary=*/false, Context); 3588 } 3589 goto tryAgain; 3590 } 3591 3592 case Stmt::BlockExprClass: 3593 // Don't recurse into blocks; their subexpressions don't get evaluated 3594 // here. 3595 return Block; 3596 3597 case Stmt::LambdaExprClass: { 3598 // For lambda expressions, only recurse into the capture initializers, 3599 // and not the body. 3600 auto *LE = cast<LambdaExpr>(E); 3601 CFGBlock *B = Block; 3602 for (Expr *Init : LE->capture_inits()) { 3603 if (CFGBlock *R = VisitForTemporaryDtors( 3604 Init, /*BindToTemporary=*/false, Context)) 3605 B = R; 3606 } 3607 return B; 3608 } 3609 3610 case Stmt::CXXDefaultArgExprClass: 3611 E = cast<CXXDefaultArgExpr>(E)->getExpr(); 3612 goto tryAgain; 3613 3614 case Stmt::CXXDefaultInitExprClass: 3615 E = cast<CXXDefaultInitExpr>(E)->getExpr(); 3616 goto tryAgain; 3617 } 3618 } 3619 3620 CFGBlock *CFGBuilder::VisitChildrenForTemporaryDtors(Stmt *E, 3621 TempDtorContext &Context) { 3622 if (isa<LambdaExpr>(E)) { 3623 // Do not visit the children of lambdas; they have their own CFGs. 3624 return Block; 3625 } 3626 3627 // When visiting children for destructors we want to visit them in reverse 3628 // order that they will appear in the CFG. Because the CFG is built 3629 // bottom-up, this means we visit them in their natural order, which 3630 // reverses them in the CFG. 3631 CFGBlock *B = Block; 3632 for (Stmt::child_range I = E->children(); I; ++I) { 3633 if (Stmt *Child = *I) 3634 if (CFGBlock *R = VisitForTemporaryDtors(Child, false, Context)) 3635 B = R; 3636 } 3637 return B; 3638 } 3639 3640 CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors( 3641 BinaryOperator *E, TempDtorContext &Context) { 3642 if (E->isLogicalOp()) { 3643 VisitForTemporaryDtors(E->getLHS(), false, Context); 3644 TryResult RHSExecuted = tryEvaluateBool(E->getLHS()); 3645 if (RHSExecuted.isKnown() && E->getOpcode() == BO_LOr) 3646 RHSExecuted.negate(); 3647 3648 // We do not know at CFG-construction time whether the right-hand-side was 3649 // executed, thus we add a branch node that depends on the temporary 3650 // constructor call. 3651 TempDtorContext RHSContext( 3652 bothKnownTrue(Context.KnownExecuted, RHSExecuted)); 3653 VisitForTemporaryDtors(E->getRHS(), false, RHSContext); 3654 InsertTempDtorDecisionBlock(RHSContext); 3655 3656 return Block; 3657 } 3658 3659 if (E->isAssignmentOp()) { 3660 // For assignment operator (=) LHS expression is visited 3661 // before RHS expression. For destructors visit them in reverse order. 3662 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS(), false, Context); 3663 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS(), false, Context); 3664 return LHSBlock ? LHSBlock : RHSBlock; 3665 } 3666 3667 // For any other binary operator RHS expression is visited before 3668 // LHS expression (order of children). For destructors visit them in reverse 3669 // order. 3670 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS(), false, Context); 3671 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS(), false, Context); 3672 return RHSBlock ? RHSBlock : LHSBlock; 3673 } 3674 3675 CFGBlock *CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors( 3676 CXXBindTemporaryExpr *E, bool BindToTemporary, TempDtorContext &Context) { 3677 // First add destructors for temporaries in subexpression. 3678 CFGBlock *B = VisitForTemporaryDtors(E->getSubExpr(), false, Context); 3679 if (!BindToTemporary) { 3680 // If lifetime of temporary is not prolonged (by assigning to constant 3681 // reference) add destructor for it. 3682 3683 const CXXDestructorDecl *Dtor = E->getTemporary()->getDestructor(); 3684 3685 if (Dtor->isNoReturn()) { 3686 // If the destructor is marked as a no-return destructor, we need to 3687 // create a new block for the destructor which does not have as a 3688 // successor anything built thus far. Control won't flow out of this 3689 // block. 3690 if (B) Succ = B; 3691 Block = createNoReturnBlock(); 3692 } else if (Context.needsTempDtorBranch()) { 3693 // If we need to introduce a branch, we add a new block that we will hook 3694 // up to a decision block later. 3695 if (B) Succ = B; 3696 Block = createBlock(); 3697 } else { 3698 autoCreateBlock(); 3699 } 3700 if (Context.needsTempDtorBranch()) { 3701 Context.setDecisionPoint(Succ, E); 3702 } 3703 appendTemporaryDtor(Block, E); 3704 3705 B = Block; 3706 } 3707 return B; 3708 } 3709 3710 void CFGBuilder::InsertTempDtorDecisionBlock(const TempDtorContext &Context, 3711 CFGBlock *FalseSucc) { 3712 if (!Context.TerminatorExpr) { 3713 // If no temporary was found, we do not need to insert a decision point. 3714 return; 3715 } 3716 assert(Context.TerminatorExpr); 3717 CFGBlock *Decision = createBlock(false); 3718 Decision->setTerminator(CFGTerminator(Context.TerminatorExpr, true)); 3719 addSuccessor(Decision, Block, !Context.KnownExecuted.isFalse()); 3720 addSuccessor(Decision, FalseSucc ? FalseSucc : Context.Succ, 3721 !Context.KnownExecuted.isTrue()); 3722 Block = Decision; 3723 } 3724 3725 CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaryDtors( 3726 AbstractConditionalOperator *E, bool BindToTemporary, 3727 TempDtorContext &Context) { 3728 VisitForTemporaryDtors(E->getCond(), false, Context); 3729 CFGBlock *ConditionBlock = Block; 3730 CFGBlock *ConditionSucc = Succ; 3731 TryResult ConditionVal = tryEvaluateBool(E->getCond()); 3732 TryResult NegatedVal = ConditionVal; 3733 if (NegatedVal.isKnown()) NegatedVal.negate(); 3734 3735 TempDtorContext TrueContext( 3736 bothKnownTrue(Context.KnownExecuted, ConditionVal)); 3737 VisitForTemporaryDtors(E->getTrueExpr(), BindToTemporary, TrueContext); 3738 CFGBlock *TrueBlock = Block; 3739 3740 Block = ConditionBlock; 3741 Succ = ConditionSucc; 3742 TempDtorContext FalseContext( 3743 bothKnownTrue(Context.KnownExecuted, NegatedVal)); 3744 VisitForTemporaryDtors(E->getFalseExpr(), BindToTemporary, FalseContext); 3745 3746 if (TrueContext.TerminatorExpr && FalseContext.TerminatorExpr) { 3747 InsertTempDtorDecisionBlock(FalseContext, TrueBlock); 3748 } else if (TrueContext.TerminatorExpr) { 3749 Block = TrueBlock; 3750 InsertTempDtorDecisionBlock(TrueContext); 3751 } else { 3752 InsertTempDtorDecisionBlock(FalseContext); 3753 } 3754 return Block; 3755 } 3756 3757 } // end anonymous namespace 3758 3759 /// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has 3760 /// no successors or predecessors. If this is the first block created in the 3761 /// CFG, it is automatically set to be the Entry and Exit of the CFG. 3762 CFGBlock *CFG::createBlock() { 3763 bool first_block = begin() == end(); 3764 3765 // Create the block. 3766 CFGBlock *Mem = getAllocator().Allocate<CFGBlock>(); 3767 new (Mem) CFGBlock(NumBlockIDs++, BlkBVC, this); 3768 Blocks.push_back(Mem, BlkBVC); 3769 3770 // If this is the first block, set it as the Entry and Exit. 3771 if (first_block) 3772 Entry = Exit = &back(); 3773 3774 // Return the block. 3775 return &back(); 3776 } 3777 3778 /// buildCFG - Constructs a CFG from an AST. 3779 std::unique_ptr<CFG> CFG::buildCFG(const Decl *D, Stmt *Statement, 3780 ASTContext *C, const BuildOptions &BO) { 3781 CFGBuilder Builder(C, BO); 3782 return Builder.buildCFG(D, Statement); 3783 } 3784 3785 const CXXDestructorDecl * 3786 CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const { 3787 switch (getKind()) { 3788 case CFGElement::Statement: 3789 case CFGElement::Initializer: 3790 case CFGElement::NewAllocator: 3791 llvm_unreachable("getDestructorDecl should only be used with " 3792 "ImplicitDtors"); 3793 case CFGElement::AutomaticObjectDtor: { 3794 const VarDecl *var = castAs<CFGAutomaticObjDtor>().getVarDecl(); 3795 QualType ty = var->getType(); 3796 ty = ty.getNonReferenceType(); 3797 while (const ArrayType *arrayType = astContext.getAsArrayType(ty)) { 3798 ty = arrayType->getElementType(); 3799 } 3800 const RecordType *recordType = ty->getAs<RecordType>(); 3801 const CXXRecordDecl *classDecl = 3802 cast<CXXRecordDecl>(recordType->getDecl()); 3803 return classDecl->getDestructor(); 3804 } 3805 case CFGElement::DeleteDtor: { 3806 const CXXDeleteExpr *DE = castAs<CFGDeleteDtor>().getDeleteExpr(); 3807 QualType DTy = DE->getDestroyedType(); 3808 DTy = DTy.getNonReferenceType(); 3809 const CXXRecordDecl *classDecl = 3810 astContext.getBaseElementType(DTy)->getAsCXXRecordDecl(); 3811 return classDecl->getDestructor(); 3812 } 3813 case CFGElement::TemporaryDtor: { 3814 const CXXBindTemporaryExpr *bindExpr = 3815 castAs<CFGTemporaryDtor>().getBindTemporaryExpr(); 3816 const CXXTemporary *temp = bindExpr->getTemporary(); 3817 return temp->getDestructor(); 3818 } 3819 case CFGElement::BaseDtor: 3820 case CFGElement::MemberDtor: 3821 3822 // Not yet supported. 3823 return nullptr; 3824 } 3825 llvm_unreachable("getKind() returned bogus value"); 3826 } 3827 3828 bool CFGImplicitDtor::isNoReturn(ASTContext &astContext) const { 3829 if (const CXXDestructorDecl *DD = getDestructorDecl(astContext)) 3830 return DD->isNoReturn(); 3831 return false; 3832 } 3833 3834 //===----------------------------------------------------------------------===// 3835 // CFGBlock operations. 3836 //===----------------------------------------------------------------------===// 3837 3838 CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, bool IsReachable) 3839 : ReachableBlock(IsReachable ? B : nullptr), 3840 UnreachableBlock(!IsReachable ? B : nullptr, 3841 B && IsReachable ? AB_Normal : AB_Unreachable) {} 3842 3843 CFGBlock::AdjacentBlock::AdjacentBlock(CFGBlock *B, CFGBlock *AlternateBlock) 3844 : ReachableBlock(B), 3845 UnreachableBlock(B == AlternateBlock ? nullptr : AlternateBlock, 3846 B == AlternateBlock ? AB_Alternate : AB_Normal) {} 3847 3848 void CFGBlock::addSuccessor(AdjacentBlock Succ, 3849 BumpVectorContext &C) { 3850 if (CFGBlock *B = Succ.getReachableBlock()) 3851 B->Preds.push_back(AdjacentBlock(this, Succ.isReachable()), C); 3852 3853 if (CFGBlock *UnreachableB = Succ.getPossiblyUnreachableBlock()) 3854 UnreachableB->Preds.push_back(AdjacentBlock(this, false), C); 3855 3856 Succs.push_back(Succ, C); 3857 } 3858 3859 bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F, 3860 const CFGBlock *From, const CFGBlock *To) { 3861 3862 if (F.IgnoreNullPredecessors && !From) 3863 return true; 3864 3865 if (To && From && F.IgnoreDefaultsWithCoveredEnums) { 3866 // If the 'To' has no label or is labeled but the label isn't a 3867 // CaseStmt then filter this edge. 3868 if (const SwitchStmt *S = 3869 dyn_cast_or_null<SwitchStmt>(From->getTerminator().getStmt())) { 3870 if (S->isAllEnumCasesCovered()) { 3871 const Stmt *L = To->getLabel(); 3872 if (!L || !isa<CaseStmt>(L)) 3873 return true; 3874 } 3875 } 3876 } 3877 3878 return false; 3879 } 3880 3881 //===----------------------------------------------------------------------===// 3882 // CFG pretty printing 3883 //===----------------------------------------------------------------------===// 3884 3885 namespace { 3886 3887 class StmtPrinterHelper : public PrinterHelper { 3888 typedef llvm::DenseMap<const Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; 3889 typedef llvm::DenseMap<const Decl*,std::pair<unsigned,unsigned> > DeclMapTy; 3890 StmtMapTy StmtMap; 3891 DeclMapTy DeclMap; 3892 signed currentBlock; 3893 unsigned currStmt; 3894 const LangOptions &LangOpts; 3895 public: 3896 3897 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) 3898 : currentBlock(0), currStmt(0), LangOpts(LO) 3899 { 3900 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { 3901 unsigned j = 1; 3902 for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ; 3903 BI != BEnd; ++BI, ++j ) { 3904 if (Optional<CFGStmt> SE = BI->getAs<CFGStmt>()) { 3905 const Stmt *stmt= SE->getStmt(); 3906 std::pair<unsigned, unsigned> P((*I)->getBlockID(), j); 3907 StmtMap[stmt] = P; 3908 3909 switch (stmt->getStmtClass()) { 3910 case Stmt::DeclStmtClass: 3911 DeclMap[cast<DeclStmt>(stmt)->getSingleDecl()] = P; 3912 break; 3913 case Stmt::IfStmtClass: { 3914 const VarDecl *var = cast<IfStmt>(stmt)->getConditionVariable(); 3915 if (var) 3916 DeclMap[var] = P; 3917 break; 3918 } 3919 case Stmt::ForStmtClass: { 3920 const VarDecl *var = cast<ForStmt>(stmt)->getConditionVariable(); 3921 if (var) 3922 DeclMap[var] = P; 3923 break; 3924 } 3925 case Stmt::WhileStmtClass: { 3926 const VarDecl *var = 3927 cast<WhileStmt>(stmt)->getConditionVariable(); 3928 if (var) 3929 DeclMap[var] = P; 3930 break; 3931 } 3932 case Stmt::SwitchStmtClass: { 3933 const VarDecl *var = 3934 cast<SwitchStmt>(stmt)->getConditionVariable(); 3935 if (var) 3936 DeclMap[var] = P; 3937 break; 3938 } 3939 case Stmt::CXXCatchStmtClass: { 3940 const VarDecl *var = 3941 cast<CXXCatchStmt>(stmt)->getExceptionDecl(); 3942 if (var) 3943 DeclMap[var] = P; 3944 break; 3945 } 3946 default: 3947 break; 3948 } 3949 } 3950 } 3951 } 3952 } 3953 3954 ~StmtPrinterHelper() override {} 3955 3956 const LangOptions &getLangOpts() const { return LangOpts; } 3957 void setBlockID(signed i) { currentBlock = i; } 3958 void setStmtID(unsigned i) { currStmt = i; } 3959 3960 bool handledStmt(Stmt *S, raw_ostream &OS) override { 3961 StmtMapTy::iterator I = StmtMap.find(S); 3962 3963 if (I == StmtMap.end()) 3964 return false; 3965 3966 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock 3967 && I->second.second == currStmt) { 3968 return false; 3969 } 3970 3971 OS << "[B" << I->second.first << "." << I->second.second << "]"; 3972 return true; 3973 } 3974 3975 bool handleDecl(const Decl *D, raw_ostream &OS) { 3976 DeclMapTy::iterator I = DeclMap.find(D); 3977 3978 if (I == DeclMap.end()) 3979 return false; 3980 3981 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock 3982 && I->second.second == currStmt) { 3983 return false; 3984 } 3985 3986 OS << "[B" << I->second.first << "." << I->second.second << "]"; 3987 return true; 3988 } 3989 }; 3990 } // end anonymous namespace 3991 3992 3993 namespace { 3994 class CFGBlockTerminatorPrint 3995 : public StmtVisitor<CFGBlockTerminatorPrint,void> { 3996 3997 raw_ostream &OS; 3998 StmtPrinterHelper* Helper; 3999 PrintingPolicy Policy; 4000 public: 4001 CFGBlockTerminatorPrint(raw_ostream &os, StmtPrinterHelper* helper, 4002 const PrintingPolicy &Policy) 4003 : OS(os), Helper(helper), Policy(Policy) { 4004 this->Policy.IncludeNewlines = false; 4005 } 4006 4007 void VisitIfStmt(IfStmt *I) { 4008 OS << "if "; 4009 if (Stmt *C = I->getCond()) 4010 C->printPretty(OS, Helper, Policy); 4011 } 4012 4013 // Default case. 4014 void VisitStmt(Stmt *Terminator) { 4015 Terminator->printPretty(OS, Helper, Policy); 4016 } 4017 4018 void VisitDeclStmt(DeclStmt *DS) { 4019 VarDecl *VD = cast<VarDecl>(DS->getSingleDecl()); 4020 OS << "static init " << VD->getName(); 4021 } 4022 4023 void VisitForStmt(ForStmt *F) { 4024 OS << "for (" ; 4025 if (F->getInit()) 4026 OS << "..."; 4027 OS << "; "; 4028 if (Stmt *C = F->getCond()) 4029 C->printPretty(OS, Helper, Policy); 4030 OS << "; "; 4031 if (F->getInc()) 4032 OS << "..."; 4033 OS << ")"; 4034 } 4035 4036 void VisitWhileStmt(WhileStmt *W) { 4037 OS << "while " ; 4038 if (Stmt *C = W->getCond()) 4039 C->printPretty(OS, Helper, Policy); 4040 } 4041 4042 void VisitDoStmt(DoStmt *D) { 4043 OS << "do ... while "; 4044 if (Stmt *C = D->getCond()) 4045 C->printPretty(OS, Helper, Policy); 4046 } 4047 4048 void VisitSwitchStmt(SwitchStmt *Terminator) { 4049 OS << "switch "; 4050 Terminator->getCond()->printPretty(OS, Helper, Policy); 4051 } 4052 4053 void VisitCXXTryStmt(CXXTryStmt *CS) { 4054 OS << "try ..."; 4055 } 4056 4057 void VisitAbstractConditionalOperator(AbstractConditionalOperator* C) { 4058 if (Stmt *Cond = C->getCond()) 4059 Cond->printPretty(OS, Helper, Policy); 4060 OS << " ? ... : ..."; 4061 } 4062 4063 void VisitChooseExpr(ChooseExpr *C) { 4064 OS << "__builtin_choose_expr( "; 4065 if (Stmt *Cond = C->getCond()) 4066 Cond->printPretty(OS, Helper, Policy); 4067 OS << " )"; 4068 } 4069 4070 void VisitIndirectGotoStmt(IndirectGotoStmt *I) { 4071 OS << "goto *"; 4072 if (Stmt *T = I->getTarget()) 4073 T->printPretty(OS, Helper, Policy); 4074 } 4075 4076 void VisitBinaryOperator(BinaryOperator* B) { 4077 if (!B->isLogicalOp()) { 4078 VisitExpr(B); 4079 return; 4080 } 4081 4082 if (B->getLHS()) 4083 B->getLHS()->printPretty(OS, Helper, Policy); 4084 4085 switch (B->getOpcode()) { 4086 case BO_LOr: 4087 OS << " || ..."; 4088 return; 4089 case BO_LAnd: 4090 OS << " && ..."; 4091 return; 4092 default: 4093 llvm_unreachable("Invalid logical operator."); 4094 } 4095 } 4096 4097 void VisitExpr(Expr *E) { 4098 E->printPretty(OS, Helper, Policy); 4099 } 4100 4101 public: 4102 void print(CFGTerminator T) { 4103 if (T.isTemporaryDtorsBranch()) 4104 OS << "(Temp Dtor) "; 4105 Visit(T.getStmt()); 4106 } 4107 }; 4108 } // end anonymous namespace 4109 4110 static void print_elem(raw_ostream &OS, StmtPrinterHelper &Helper, 4111 const CFGElement &E) { 4112 if (Optional<CFGStmt> CS = E.getAs<CFGStmt>()) { 4113 const Stmt *S = CS->getStmt(); 4114 assert(S != nullptr && "Expecting non-null Stmt"); 4115 4116 // special printing for statement-expressions. 4117 if (const StmtExpr *SE = dyn_cast<StmtExpr>(S)) { 4118 const CompoundStmt *Sub = SE->getSubStmt(); 4119 4120 if (Sub->children()) { 4121 OS << "({ ... ; "; 4122 Helper.handledStmt(*SE->getSubStmt()->body_rbegin(),OS); 4123 OS << " })\n"; 4124 return; 4125 } 4126 } 4127 // special printing for comma expressions. 4128 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { 4129 if (B->getOpcode() == BO_Comma) { 4130 OS << "... , "; 4131 Helper.handledStmt(B->getRHS(),OS); 4132 OS << '\n'; 4133 return; 4134 } 4135 } 4136 S->printPretty(OS, &Helper, PrintingPolicy(Helper.getLangOpts())); 4137 4138 if (isa<CXXOperatorCallExpr>(S)) { 4139 OS << " (OperatorCall)"; 4140 } 4141 else if (isa<CXXBindTemporaryExpr>(S)) { 4142 OS << " (BindTemporary)"; 4143 } 4144 else if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(S)) { 4145 OS << " (CXXConstructExpr, " << CCE->getType().getAsString() << ")"; 4146 } 4147 else if (const CastExpr *CE = dyn_cast<CastExpr>(S)) { 4148 OS << " (" << CE->getStmtClassName() << ", " 4149 << CE->getCastKindName() 4150 << ", " << CE->getType().getAsString() 4151 << ")"; 4152 } 4153 4154 // Expressions need a newline. 4155 if (isa<Expr>(S)) 4156 OS << '\n'; 4157 4158 } else if (Optional<CFGInitializer> IE = E.getAs<CFGInitializer>()) { 4159 const CXXCtorInitializer *I = IE->getInitializer(); 4160 if (I->isBaseInitializer()) 4161 OS << I->getBaseClass()->getAsCXXRecordDecl()->getName(); 4162 else if (I->isDelegatingInitializer()) 4163 OS << I->getTypeSourceInfo()->getType()->getAsCXXRecordDecl()->getName(); 4164 else OS << I->getAnyMember()->getName(); 4165 4166 OS << "("; 4167 if (Expr *IE = I->getInit()) 4168 IE->printPretty(OS, &Helper, PrintingPolicy(Helper.getLangOpts())); 4169 OS << ")"; 4170 4171 if (I->isBaseInitializer()) 4172 OS << " (Base initializer)\n"; 4173 else if (I->isDelegatingInitializer()) 4174 OS << " (Delegating initializer)\n"; 4175 else OS << " (Member initializer)\n"; 4176 4177 } else if (Optional<CFGAutomaticObjDtor> DE = 4178 E.getAs<CFGAutomaticObjDtor>()) { 4179 const VarDecl *VD = DE->getVarDecl(); 4180 Helper.handleDecl(VD, OS); 4181 4182 const Type* T = VD->getType().getTypePtr(); 4183 if (const ReferenceType* RT = T->getAs<ReferenceType>()) 4184 T = RT->getPointeeType().getTypePtr(); 4185 T = T->getBaseElementTypeUnsafe(); 4186 4187 OS << ".~" << T->getAsCXXRecordDecl()->getName().str() << "()"; 4188 OS << " (Implicit destructor)\n"; 4189 4190 } else if (Optional<CFGNewAllocator> NE = E.getAs<CFGNewAllocator>()) { 4191 OS << "CFGNewAllocator("; 4192 if (const CXXNewExpr *AllocExpr = NE->getAllocatorExpr()) 4193 AllocExpr->getType().print(OS, PrintingPolicy(Helper.getLangOpts())); 4194 OS << ")\n"; 4195 } else if (Optional<CFGDeleteDtor> DE = E.getAs<CFGDeleteDtor>()) { 4196 const CXXRecordDecl *RD = DE->getCXXRecordDecl(); 4197 if (!RD) 4198 return; 4199 CXXDeleteExpr *DelExpr = 4200 const_cast<CXXDeleteExpr*>(DE->getDeleteExpr()); 4201 Helper.handledStmt(cast<Stmt>(DelExpr->getArgument()), OS); 4202 OS << "->~" << RD->getName().str() << "()"; 4203 OS << " (Implicit destructor)\n"; 4204 } else if (Optional<CFGBaseDtor> BE = E.getAs<CFGBaseDtor>()) { 4205 const CXXBaseSpecifier *BS = BE->getBaseSpecifier(); 4206 OS << "~" << BS->getType()->getAsCXXRecordDecl()->getName() << "()"; 4207 OS << " (Base object destructor)\n"; 4208 4209 } else if (Optional<CFGMemberDtor> ME = E.getAs<CFGMemberDtor>()) { 4210 const FieldDecl *FD = ME->getFieldDecl(); 4211 const Type *T = FD->getType()->getBaseElementTypeUnsafe(); 4212 OS << "this->" << FD->getName(); 4213 OS << ".~" << T->getAsCXXRecordDecl()->getName() << "()"; 4214 OS << " (Member object destructor)\n"; 4215 4216 } else if (Optional<CFGTemporaryDtor> TE = E.getAs<CFGTemporaryDtor>()) { 4217 const CXXBindTemporaryExpr *BT = TE->getBindTemporaryExpr(); 4218 OS << "~"; 4219 BT->getType().print(OS, PrintingPolicy(Helper.getLangOpts())); 4220 OS << "() (Temporary object destructor)\n"; 4221 } 4222 } 4223 4224 static void print_block(raw_ostream &OS, const CFG* cfg, 4225 const CFGBlock &B, 4226 StmtPrinterHelper &Helper, bool print_edges, 4227 bool ShowColors) { 4228 4229 Helper.setBlockID(B.getBlockID()); 4230 4231 // Print the header. 4232 if (ShowColors) 4233 OS.changeColor(raw_ostream::YELLOW, true); 4234 4235 OS << "\n [B" << B.getBlockID(); 4236 4237 if (&B == &cfg->getEntry()) 4238 OS << " (ENTRY)]\n"; 4239 else if (&B == &cfg->getExit()) 4240 OS << " (EXIT)]\n"; 4241 else if (&B == cfg->getIndirectGotoBlock()) 4242 OS << " (INDIRECT GOTO DISPATCH)]\n"; 4243 else if (B.hasNoReturnElement()) 4244 OS << " (NORETURN)]\n"; 4245 else 4246 OS << "]\n"; 4247 4248 if (ShowColors) 4249 OS.resetColor(); 4250 4251 // Print the label of this block. 4252 if (Stmt *Label = const_cast<Stmt*>(B.getLabel())) { 4253 4254 if (print_edges) 4255 OS << " "; 4256 4257 if (LabelStmt *L = dyn_cast<LabelStmt>(Label)) 4258 OS << L->getName(); 4259 else if (CaseStmt *C = dyn_cast<CaseStmt>(Label)) { 4260 OS << "case "; 4261 if (C->getLHS()) 4262 C->getLHS()->printPretty(OS, &Helper, 4263 PrintingPolicy(Helper.getLangOpts())); 4264 if (C->getRHS()) { 4265 OS << " ... "; 4266 C->getRHS()->printPretty(OS, &Helper, 4267 PrintingPolicy(Helper.getLangOpts())); 4268 } 4269 } else if (isa<DefaultStmt>(Label)) 4270 OS << "default"; 4271 else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Label)) { 4272 OS << "catch ("; 4273 if (CS->getExceptionDecl()) 4274 CS->getExceptionDecl()->print(OS, PrintingPolicy(Helper.getLangOpts()), 4275 0); 4276 else 4277 OS << "..."; 4278 OS << ")"; 4279 4280 } else 4281 llvm_unreachable("Invalid label statement in CFGBlock."); 4282 4283 OS << ":\n"; 4284 } 4285 4286 // Iterate through the statements in the block and print them. 4287 unsigned j = 1; 4288 4289 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; 4290 I != E ; ++I, ++j ) { 4291 4292 // Print the statement # in the basic block and the statement itself. 4293 if (print_edges) 4294 OS << " "; 4295 4296 OS << llvm::format("%3d", j) << ": "; 4297 4298 Helper.setStmtID(j); 4299 4300 print_elem(OS, Helper, *I); 4301 } 4302 4303 // Print the terminator of this block. 4304 if (B.getTerminator()) { 4305 if (ShowColors) 4306 OS.changeColor(raw_ostream::GREEN); 4307 4308 OS << " T: "; 4309 4310 Helper.setBlockID(-1); 4311 4312 PrintingPolicy PP(Helper.getLangOpts()); 4313 CFGBlockTerminatorPrint TPrinter(OS, &Helper, PP); 4314 TPrinter.print(B.getTerminator()); 4315 OS << '\n'; 4316 4317 if (ShowColors) 4318 OS.resetColor(); 4319 } 4320 4321 if (print_edges) { 4322 // Print the predecessors of this block. 4323 if (!B.pred_empty()) { 4324 const raw_ostream::Colors Color = raw_ostream::BLUE; 4325 if (ShowColors) 4326 OS.changeColor(Color); 4327 OS << " Preds " ; 4328 if (ShowColors) 4329 OS.resetColor(); 4330 OS << '(' << B.pred_size() << "):"; 4331 unsigned i = 0; 4332 4333 if (ShowColors) 4334 OS.changeColor(Color); 4335 4336 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); 4337 I != E; ++I, ++i) { 4338 4339 if (i % 10 == 8) 4340 OS << "\n "; 4341 4342 CFGBlock *B = *I; 4343 bool Reachable = true; 4344 if (!B) { 4345 Reachable = false; 4346 B = I->getPossiblyUnreachableBlock(); 4347 } 4348 4349 OS << " B" << B->getBlockID(); 4350 if (!Reachable) 4351 OS << "(Unreachable)"; 4352 } 4353 4354 if (ShowColors) 4355 OS.resetColor(); 4356 4357 OS << '\n'; 4358 } 4359 4360 // Print the successors of this block. 4361 if (!B.succ_empty()) { 4362 const raw_ostream::Colors Color = raw_ostream::MAGENTA; 4363 if (ShowColors) 4364 OS.changeColor(Color); 4365 OS << " Succs "; 4366 if (ShowColors) 4367 OS.resetColor(); 4368 OS << '(' << B.succ_size() << "):"; 4369 unsigned i = 0; 4370 4371 if (ShowColors) 4372 OS.changeColor(Color); 4373 4374 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); 4375 I != E; ++I, ++i) { 4376 4377 if (i % 10 == 8) 4378 OS << "\n "; 4379 4380 CFGBlock *B = *I; 4381 4382 bool Reachable = true; 4383 if (!B) { 4384 Reachable = false; 4385 B = I->getPossiblyUnreachableBlock(); 4386 } 4387 4388 if (B) { 4389 OS << " B" << B->getBlockID(); 4390 if (!Reachable) 4391 OS << "(Unreachable)"; 4392 } 4393 else { 4394 OS << " NULL"; 4395 } 4396 } 4397 4398 if (ShowColors) 4399 OS.resetColor(); 4400 OS << '\n'; 4401 } 4402 } 4403 } 4404 4405 4406 /// dump - A simple pretty printer of a CFG that outputs to stderr. 4407 void CFG::dump(const LangOptions &LO, bool ShowColors) const { 4408 print(llvm::errs(), LO, ShowColors); 4409 } 4410 4411 /// print - A simple pretty printer of a CFG that outputs to an ostream. 4412 void CFG::print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const { 4413 StmtPrinterHelper Helper(this, LO); 4414 4415 // Print the entry block. 4416 print_block(OS, this, getEntry(), Helper, true, ShowColors); 4417 4418 // Iterate through the CFGBlocks and print them one by one. 4419 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { 4420 // Skip the entry block, because we already printed it. 4421 if (&(**I) == &getEntry() || &(**I) == &getExit()) 4422 continue; 4423 4424 print_block(OS, this, **I, Helper, true, ShowColors); 4425 } 4426 4427 // Print the exit block. 4428 print_block(OS, this, getExit(), Helper, true, ShowColors); 4429 OS << '\n'; 4430 OS.flush(); 4431 } 4432 4433 /// dump - A simply pretty printer of a CFGBlock that outputs to stderr. 4434 void CFGBlock::dump(const CFG* cfg, const LangOptions &LO, 4435 bool ShowColors) const { 4436 print(llvm::errs(), cfg, LO, ShowColors); 4437 } 4438 4439 void CFGBlock::dump() const { 4440 dump(getParent(), LangOptions(), false); 4441 } 4442 4443 /// print - A simple pretty printer of a CFGBlock that outputs to an ostream. 4444 /// Generally this will only be called from CFG::print. 4445 void CFGBlock::print(raw_ostream &OS, const CFG* cfg, 4446 const LangOptions &LO, bool ShowColors) const { 4447 StmtPrinterHelper Helper(cfg, LO); 4448 print_block(OS, cfg, *this, Helper, true, ShowColors); 4449 OS << '\n'; 4450 } 4451 4452 /// printTerminator - A simple pretty printer of the terminator of a CFGBlock. 4453 void CFGBlock::printTerminator(raw_ostream &OS, 4454 const LangOptions &LO) const { 4455 CFGBlockTerminatorPrint TPrinter(OS, nullptr, PrintingPolicy(LO)); 4456 TPrinter.print(getTerminator()); 4457 } 4458 4459 Stmt *CFGBlock::getTerminatorCondition(bool StripParens) { 4460 Stmt *Terminator = this->Terminator; 4461 if (!Terminator) 4462 return nullptr; 4463 4464 Expr *E = nullptr; 4465 4466 switch (Terminator->getStmtClass()) { 4467 default: 4468 break; 4469 4470 case Stmt::CXXForRangeStmtClass: 4471 E = cast<CXXForRangeStmt>(Terminator)->getCond(); 4472 break; 4473 4474 case Stmt::ForStmtClass: 4475 E = cast<ForStmt>(Terminator)->getCond(); 4476 break; 4477 4478 case Stmt::WhileStmtClass: 4479 E = cast<WhileStmt>(Terminator)->getCond(); 4480 break; 4481 4482 case Stmt::DoStmtClass: 4483 E = cast<DoStmt>(Terminator)->getCond(); 4484 break; 4485 4486 case Stmt::IfStmtClass: 4487 E = cast<IfStmt>(Terminator)->getCond(); 4488 break; 4489 4490 case Stmt::ChooseExprClass: 4491 E = cast<ChooseExpr>(Terminator)->getCond(); 4492 break; 4493 4494 case Stmt::IndirectGotoStmtClass: 4495 E = cast<IndirectGotoStmt>(Terminator)->getTarget(); 4496 break; 4497 4498 case Stmt::SwitchStmtClass: 4499 E = cast<SwitchStmt>(Terminator)->getCond(); 4500 break; 4501 4502 case Stmt::BinaryConditionalOperatorClass: 4503 E = cast<BinaryConditionalOperator>(Terminator)->getCond(); 4504 break; 4505 4506 case Stmt::ConditionalOperatorClass: 4507 E = cast<ConditionalOperator>(Terminator)->getCond(); 4508 break; 4509 4510 case Stmt::BinaryOperatorClass: // '&&' and '||' 4511 E = cast<BinaryOperator>(Terminator)->getLHS(); 4512 break; 4513 4514 case Stmt::ObjCForCollectionStmtClass: 4515 return Terminator; 4516 } 4517 4518 if (!StripParens) 4519 return E; 4520 4521 return E ? E->IgnoreParens() : nullptr; 4522 } 4523 4524 //===----------------------------------------------------------------------===// 4525 // CFG Graphviz Visualization 4526 //===----------------------------------------------------------------------===// 4527 4528 4529 #ifndef NDEBUG 4530 static StmtPrinterHelper* GraphHelper; 4531 #endif 4532 4533 void CFG::viewCFG(const LangOptions &LO) const { 4534 #ifndef NDEBUG 4535 StmtPrinterHelper H(this, LO); 4536 GraphHelper = &H; 4537 llvm::ViewGraph(this,"CFG"); 4538 GraphHelper = nullptr; 4539 #endif 4540 } 4541 4542 namespace llvm { 4543 template<> 4544 struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { 4545 4546 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 4547 4548 static std::string getNodeLabel(const CFGBlock *Node, const CFG* Graph) { 4549 4550 #ifndef NDEBUG 4551 std::string OutSStr; 4552 llvm::raw_string_ostream Out(OutSStr); 4553 print_block(Out,Graph, *Node, *GraphHelper, false, false); 4554 std::string& OutStr = Out.str(); 4555 4556 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); 4557 4558 // Process string output to make it nicer... 4559 for (unsigned i = 0; i != OutStr.length(); ++i) 4560 if (OutStr[i] == '\n') { // Left justify 4561 OutStr[i] = '\\'; 4562 OutStr.insert(OutStr.begin()+i+1, 'l'); 4563 } 4564 4565 return OutStr; 4566 #else 4567 return ""; 4568 #endif 4569 } 4570 }; 4571 } // end namespace llvm 4572