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/Support/SaveAndRestore.h" 16 #include "clang/Analysis/CFG.h" 17 #include "clang/AST/DeclCXX.h" 18 #include "clang/AST/StmtVisitor.h" 19 #include "clang/AST/PrettyPrinter.h" 20 #include "clang/AST/CharUnits.h" 21 #include "llvm/Support/GraphWriter.h" 22 #include "llvm/Support/Allocator.h" 23 #include "llvm/Support/Format.h" 24 #include "llvm/ADT/DenseMap.h" 25 #include "llvm/ADT/SmallPtrSet.h" 26 #include "llvm/ADT/OwningPtr.h" 27 28 using namespace clang; 29 30 namespace { 31 32 static SourceLocation GetEndLoc(Decl *D) { 33 if (VarDecl *VD = dyn_cast<VarDecl>(D)) 34 if (Expr *Ex = VD->getInit()) 35 return Ex->getSourceRange().getEnd(); 36 return D->getLocation(); 37 } 38 39 class CFGBuilder; 40 41 /// The CFG builder uses a recursive algorithm to build the CFG. When 42 /// we process an expression, sometimes we know that we must add the 43 /// subexpressions as block-level expressions. For example: 44 /// 45 /// exp1 || exp2 46 /// 47 /// When processing the '||' expression, we know that exp1 and exp2 48 /// need to be added as block-level expressions, even though they 49 /// might not normally need to be. AddStmtChoice records this 50 /// contextual information. If AddStmtChoice is 'NotAlwaysAdd', then 51 /// the builder has an option not to add a subexpression as a 52 /// block-level expression. 53 /// 54 class AddStmtChoice { 55 public: 56 enum Kind { NotAlwaysAdd = 0, AlwaysAdd = 1 }; 57 58 AddStmtChoice(Kind a_kind = NotAlwaysAdd) : kind(a_kind) {} 59 60 bool alwaysAdd(CFGBuilder &builder, 61 const Stmt *stmt) const; 62 63 /// Return a copy of this object, except with the 'always-add' bit 64 /// set as specified. 65 AddStmtChoice withAlwaysAdd(bool alwaysAdd) const { 66 return AddStmtChoice(alwaysAdd ? AlwaysAdd : NotAlwaysAdd); 67 } 68 69 private: 70 Kind kind; 71 }; 72 73 /// LocalScope - Node in tree of local scopes created for C++ implicit 74 /// destructor calls generation. It contains list of automatic variables 75 /// declared in the scope and link to position in previous scope this scope 76 /// began in. 77 /// 78 /// The process of creating local scopes is as follows: 79 /// - Init CFGBuilder::ScopePos with invalid position (equivalent for null), 80 /// - Before processing statements in scope (e.g. CompoundStmt) create 81 /// LocalScope object using CFGBuilder::ScopePos as link to previous scope 82 /// and set CFGBuilder::ScopePos to the end of new scope, 83 /// - On every occurrence of VarDecl increase CFGBuilder::ScopePos if it points 84 /// at this VarDecl, 85 /// - For every normal (without jump) end of scope add to CFGBlock destructors 86 /// for objects in the current scope, 87 /// - For every jump add to CFGBlock destructors for objects 88 /// between CFGBuilder::ScopePos and local scope position saved for jump 89 /// target. Thanks to C++ restrictions on goto jumps we can be sure that 90 /// jump target position will be on the path to root from CFGBuilder::ScopePos 91 /// (adding any variable that doesn't need constructor to be called to 92 /// LocalScope can break this assumption), 93 /// 94 class LocalScope { 95 public: 96 typedef BumpVector<VarDecl*> AutomaticVarsTy; 97 98 /// const_iterator - Iterates local scope backwards and jumps to previous 99 /// scope on reaching the beginning of currently iterated scope. 100 class const_iterator { 101 const LocalScope* Scope; 102 103 /// VarIter is guaranteed to be greater then 0 for every valid iterator. 104 /// Invalid iterator (with null Scope) has VarIter equal to 0. 105 unsigned VarIter; 106 107 public: 108 /// Create invalid iterator. Dereferencing invalid iterator is not allowed. 109 /// Incrementing invalid iterator is allowed and will result in invalid 110 /// iterator. 111 const_iterator() 112 : Scope(NULL), VarIter(0) {} 113 114 /// Create valid iterator. In case when S.Prev is an invalid iterator and 115 /// I is equal to 0, this will create invalid iterator. 116 const_iterator(const LocalScope& S, unsigned I) 117 : Scope(&S), VarIter(I) { 118 // Iterator to "end" of scope is not allowed. Handle it by going up 119 // in scopes tree possibly up to invalid iterator in the root. 120 if (VarIter == 0 && Scope) 121 *this = Scope->Prev; 122 } 123 124 VarDecl *const* operator->() const { 125 assert (Scope && "Dereferencing invalid iterator is not allowed"); 126 assert (VarIter != 0 && "Iterator has invalid value of VarIter member"); 127 return &Scope->Vars[VarIter - 1]; 128 } 129 VarDecl *operator*() const { 130 return *this->operator->(); 131 } 132 133 const_iterator &operator++() { 134 if (!Scope) 135 return *this; 136 137 assert (VarIter != 0 && "Iterator has invalid value of VarIter member"); 138 --VarIter; 139 if (VarIter == 0) 140 *this = Scope->Prev; 141 return *this; 142 } 143 const_iterator operator++(int) { 144 const_iterator P = *this; 145 ++*this; 146 return P; 147 } 148 149 bool operator==(const const_iterator &rhs) const { 150 return Scope == rhs.Scope && VarIter == rhs.VarIter; 151 } 152 bool operator!=(const const_iterator &rhs) const { 153 return !(*this == rhs); 154 } 155 156 operator bool() const { 157 return *this != const_iterator(); 158 } 159 160 int distance(const_iterator L); 161 }; 162 163 friend class const_iterator; 164 165 private: 166 BumpVectorContext ctx; 167 168 /// Automatic variables in order of declaration. 169 AutomaticVarsTy Vars; 170 /// Iterator to variable in previous scope that was declared just before 171 /// begin of this scope. 172 const_iterator Prev; 173 174 public: 175 /// Constructs empty scope linked to previous scope in specified place. 176 LocalScope(BumpVectorContext &ctx, const_iterator P) 177 : ctx(ctx), Vars(ctx, 4), Prev(P) {} 178 179 /// Begin of scope in direction of CFG building (backwards). 180 const_iterator begin() const { return const_iterator(*this, Vars.size()); } 181 182 void addVar(VarDecl *VD) { 183 Vars.push_back(VD, ctx); 184 } 185 }; 186 187 /// distance - Calculates distance from this to L. L must be reachable from this 188 /// (with use of ++ operator). Cost of calculating the distance is linear w.r.t. 189 /// number of scopes between this and L. 190 int LocalScope::const_iterator::distance(LocalScope::const_iterator L) { 191 int D = 0; 192 const_iterator F = *this; 193 while (F.Scope != L.Scope) { 194 assert (F != const_iterator() 195 && "L iterator is not reachable from F iterator."); 196 D += F.VarIter; 197 F = F.Scope->Prev; 198 } 199 D += F.VarIter - L.VarIter; 200 return D; 201 } 202 203 /// BlockScopePosPair - Structure for specifying position in CFG during its 204 /// build process. It consists of CFGBlock that specifies position in CFG graph 205 /// and LocalScope::const_iterator that specifies position in LocalScope graph. 206 struct BlockScopePosPair { 207 BlockScopePosPair() : block(0) {} 208 BlockScopePosPair(CFGBlock *b, LocalScope::const_iterator scopePos) 209 : block(b), scopePosition(scopePos) {} 210 211 CFGBlock *block; 212 LocalScope::const_iterator scopePosition; 213 }; 214 215 /// TryResult - a class representing a variant over the values 216 /// 'true', 'false', or 'unknown'. This is returned by tryEvaluateBool, 217 /// and is used by the CFGBuilder to decide if a branch condition 218 /// can be decided up front during CFG construction. 219 class TryResult { 220 int X; 221 public: 222 TryResult(bool b) : X(b ? 1 : 0) {} 223 TryResult() : X(-1) {} 224 225 bool isTrue() const { return X == 1; } 226 bool isFalse() const { return X == 0; } 227 bool isKnown() const { return X >= 0; } 228 void negate() { 229 assert(isKnown()); 230 X ^= 0x1; 231 } 232 }; 233 234 /// CFGBuilder - This class implements CFG construction from an AST. 235 /// The builder is stateful: an instance of the builder should be used to only 236 /// construct a single CFG. 237 /// 238 /// Example usage: 239 /// 240 /// CFGBuilder builder; 241 /// CFG* cfg = builder.BuildAST(stmt1); 242 /// 243 /// CFG construction is done via a recursive walk of an AST. We actually parse 244 /// the AST in reverse order so that the successor of a basic block is 245 /// constructed prior to its predecessor. This allows us to nicely capture 246 /// implicit fall-throughs without extra basic blocks. 247 /// 248 class CFGBuilder { 249 typedef BlockScopePosPair JumpTarget; 250 typedef BlockScopePosPair JumpSource; 251 252 ASTContext *Context; 253 llvm::OwningPtr<CFG> cfg; 254 255 CFGBlock *Block; 256 CFGBlock *Succ; 257 JumpTarget ContinueJumpTarget; 258 JumpTarget BreakJumpTarget; 259 CFGBlock *SwitchTerminatedBlock; 260 CFGBlock *DefaultCaseBlock; 261 CFGBlock *TryTerminatedBlock; 262 263 // Current position in local scope. 264 LocalScope::const_iterator ScopePos; 265 266 // LabelMap records the mapping from Label expressions to their jump targets. 267 typedef llvm::DenseMap<LabelDecl*, JumpTarget> LabelMapTy; 268 LabelMapTy LabelMap; 269 270 // A list of blocks that end with a "goto" that must be backpatched to their 271 // resolved targets upon completion of CFG construction. 272 typedef std::vector<JumpSource> BackpatchBlocksTy; 273 BackpatchBlocksTy BackpatchBlocks; 274 275 // A list of labels whose address has been taken (for indirect gotos). 276 typedef llvm::SmallPtrSet<LabelDecl*, 5> LabelSetTy; 277 LabelSetTy AddressTakenLabels; 278 279 bool badCFG; 280 const CFG::BuildOptions &BuildOpts; 281 282 // State to track for building switch statements. 283 bool switchExclusivelyCovered; 284 Expr::EvalResult *switchCond; 285 286 CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry; 287 const Stmt *lastLookup; 288 289 public: 290 explicit CFGBuilder(ASTContext *astContext, 291 const CFG::BuildOptions &buildOpts) 292 : Context(astContext), cfg(new CFG()), // crew a new CFG 293 Block(NULL), Succ(NULL), 294 SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL), 295 TryTerminatedBlock(NULL), badCFG(false), BuildOpts(buildOpts), 296 switchExclusivelyCovered(false), switchCond(0), 297 cachedEntry(0), lastLookup(0) {} 298 299 // buildCFG - Used by external clients to construct the CFG. 300 CFG* buildCFG(const Decl *D, Stmt *Statement); 301 302 bool alwaysAdd(const Stmt *stmt); 303 304 private: 305 // Visitors to walk an AST and construct the CFG. 306 CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc); 307 CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc); 308 CFGBlock *VisitBlockExpr(BlockExpr *E, AddStmtChoice asc); 309 CFGBlock *VisitBreakStmt(BreakStmt *B); 310 CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S); 311 CFGBlock *VisitExprWithCleanups(ExprWithCleanups *E, 312 AddStmtChoice asc); 313 CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T); 314 CFGBlock *VisitCXXTryStmt(CXXTryStmt *S); 315 CFGBlock *VisitCXXForRangeStmt(CXXForRangeStmt *S); 316 CFGBlock *VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E, 317 AddStmtChoice asc); 318 CFGBlock *VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc); 319 CFGBlock *VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E, 320 AddStmtChoice asc); 321 CFGBlock *VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C, 322 AddStmtChoice asc); 323 CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc); 324 CFGBlock *VisitCaseStmt(CaseStmt *C); 325 CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc); 326 CFGBlock *VisitCompoundStmt(CompoundStmt *C); 327 CFGBlock *VisitConditionalOperator(AbstractConditionalOperator *C, 328 AddStmtChoice asc); 329 CFGBlock *VisitContinueStmt(ContinueStmt *C); 330 CFGBlock *VisitDeclStmt(DeclStmt *DS); 331 CFGBlock *VisitDeclSubExpr(DeclStmt *DS); 332 CFGBlock *VisitDefaultStmt(DefaultStmt *D); 333 CFGBlock *VisitDoStmt(DoStmt *D); 334 CFGBlock *VisitForStmt(ForStmt *F); 335 CFGBlock *VisitGotoStmt(GotoStmt *G); 336 CFGBlock *VisitIfStmt(IfStmt *I); 337 CFGBlock *VisitImplicitCastExpr(ImplicitCastExpr *E, AddStmtChoice asc); 338 CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I); 339 CFGBlock *VisitLabelStmt(LabelStmt *L); 340 CFGBlock *VisitMemberExpr(MemberExpr *M, AddStmtChoice asc); 341 CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S); 342 CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S); 343 CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S); 344 CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S); 345 CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S); 346 CFGBlock *VisitReturnStmt(ReturnStmt *R); 347 CFGBlock *VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E, 348 AddStmtChoice asc); 349 CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc); 350 CFGBlock *VisitSwitchStmt(SwitchStmt *S); 351 CFGBlock *VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc); 352 CFGBlock *VisitWhileStmt(WhileStmt *W); 353 354 CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd); 355 CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc); 356 CFGBlock *VisitChildren(Stmt *S); 357 358 // Visitors to walk an AST and generate destructors of temporaries in 359 // full expression. 360 CFGBlock *VisitForTemporaryDtors(Stmt *E, bool BindToTemporary = false); 361 CFGBlock *VisitChildrenForTemporaryDtors(Stmt *E); 362 CFGBlock *VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E); 363 CFGBlock *VisitCXXBindTemporaryExprForTemporaryDtors(CXXBindTemporaryExpr *E, 364 bool BindToTemporary); 365 CFGBlock * 366 VisitConditionalOperatorForTemporaryDtors(AbstractConditionalOperator *E, 367 bool BindToTemporary); 368 369 // NYS == Not Yet Supported 370 CFGBlock *NYS() { 371 badCFG = true; 372 return Block; 373 } 374 375 void autoCreateBlock() { if (!Block) Block = createBlock(); } 376 CFGBlock *createBlock(bool add_successor = true); 377 CFGBlock *createNoReturnBlock(); 378 379 CFGBlock *addStmt(Stmt *S) { 380 return Visit(S, AddStmtChoice::AlwaysAdd); 381 } 382 CFGBlock *addInitializer(CXXCtorInitializer *I); 383 void addAutomaticObjDtors(LocalScope::const_iterator B, 384 LocalScope::const_iterator E, Stmt *S); 385 void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD); 386 387 // Local scopes creation. 388 LocalScope* createOrReuseLocalScope(LocalScope* Scope); 389 390 void addLocalScopeForStmt(Stmt *S); 391 LocalScope* addLocalScopeForDeclStmt(DeclStmt *DS, LocalScope* Scope = NULL); 392 LocalScope* addLocalScopeForVarDecl(VarDecl *VD, LocalScope* Scope = NULL); 393 394 void addLocalScopeAndDtors(Stmt *S); 395 396 // Interface to CFGBlock - adding CFGElements. 397 void appendStmt(CFGBlock *B, const Stmt *S) { 398 if (alwaysAdd(S) && cachedEntry) 399 cachedEntry->second = B; 400 401 // All block-level expressions should have already been IgnoreParens()ed. 402 assert(!isa<Expr>(S) || cast<Expr>(S)->IgnoreParens() == S); 403 B->appendStmt(const_cast<Stmt*>(S), cfg->getBumpVectorContext()); 404 } 405 void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) { 406 B->appendInitializer(I, cfg->getBumpVectorContext()); 407 } 408 void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) { 409 B->appendBaseDtor(BS, cfg->getBumpVectorContext()); 410 } 411 void appendMemberDtor(CFGBlock *B, FieldDecl *FD) { 412 B->appendMemberDtor(FD, cfg->getBumpVectorContext()); 413 } 414 void appendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) { 415 B->appendTemporaryDtor(E, cfg->getBumpVectorContext()); 416 } 417 void appendAutomaticObjDtor(CFGBlock *B, VarDecl *VD, Stmt *S) { 418 B->appendAutomaticObjDtor(VD, S, cfg->getBumpVectorContext()); 419 } 420 421 void prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk, 422 LocalScope::const_iterator B, LocalScope::const_iterator E); 423 424 void addSuccessor(CFGBlock *B, CFGBlock *S) { 425 B->addSuccessor(S, cfg->getBumpVectorContext()); 426 } 427 428 /// Try and evaluate an expression to an integer constant. 429 bool tryEvaluate(Expr *S, Expr::EvalResult &outResult) { 430 if (!BuildOpts.PruneTriviallyFalseEdges) 431 return false; 432 return !S->isTypeDependent() && 433 !S->isValueDependent() && 434 S->Evaluate(outResult, *Context); 435 } 436 437 /// tryEvaluateBool - Try and evaluate the Stmt and return 0 or 1 438 /// if we can evaluate to a known value, otherwise return -1. 439 TryResult tryEvaluateBool(Expr *S) { 440 bool Result; 441 if (!BuildOpts.PruneTriviallyFalseEdges || 442 S->isTypeDependent() || S->isValueDependent() || 443 !S->EvaluateAsBooleanCondition(Result, *Context)) 444 return TryResult(); 445 return Result; 446 } 447 448 }; 449 450 inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder, 451 const Stmt *stmt) const { 452 return builder.alwaysAdd(stmt) || kind == AlwaysAdd; 453 } 454 455 bool CFGBuilder::alwaysAdd(const Stmt *stmt) { 456 bool shouldAdd = BuildOpts.alwaysAdd(stmt); 457 458 if (!BuildOpts.forcedBlkExprs) 459 return shouldAdd; 460 461 if (lastLookup == stmt) { 462 if (cachedEntry) { 463 assert(cachedEntry->first == stmt); 464 return true; 465 } 466 return shouldAdd; 467 } 468 469 lastLookup = stmt; 470 471 // Perform the lookup! 472 CFG::BuildOptions::ForcedBlkExprs *fb = *BuildOpts.forcedBlkExprs; 473 474 if (!fb) { 475 // No need to update 'cachedEntry', since it will always be null. 476 assert(cachedEntry == 0); 477 return shouldAdd; 478 } 479 480 CFG::BuildOptions::ForcedBlkExprs::iterator itr = fb->find(stmt); 481 if (itr == fb->end()) { 482 cachedEntry = 0; 483 return shouldAdd; 484 } 485 486 cachedEntry = &*itr; 487 return true; 488 } 489 490 // FIXME: Add support for dependent-sized array types in C++? 491 // Does it even make sense to build a CFG for an uninstantiated template? 492 static const VariableArrayType *FindVA(const Type *t) { 493 while (const ArrayType *vt = dyn_cast<ArrayType>(t)) { 494 if (const VariableArrayType *vat = dyn_cast<VariableArrayType>(vt)) 495 if (vat->getSizeExpr()) 496 return vat; 497 498 t = vt->getElementType().getTypePtr(); 499 } 500 501 return 0; 502 } 503 504 /// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an 505 /// arbitrary statement. Examples include a single expression or a function 506 /// body (compound statement). The ownership of the returned CFG is 507 /// transferred to the caller. If CFG construction fails, this method returns 508 /// NULL. 509 CFG* CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) { 510 assert(cfg.get()); 511 if (!Statement) 512 return NULL; 513 514 // Create an empty block that will serve as the exit block for the CFG. Since 515 // this is the first block added to the CFG, it will be implicitly registered 516 // as the exit block. 517 Succ = createBlock(); 518 assert(Succ == &cfg->getExit()); 519 Block = NULL; // the EXIT block is empty. Create all other blocks lazily. 520 521 if (BuildOpts.AddImplicitDtors) 522 if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(D)) 523 addImplicitDtorsForDestructor(DD); 524 525 // Visit the statements and create the CFG. 526 CFGBlock *B = addStmt(Statement); 527 528 if (badCFG) 529 return NULL; 530 531 // For C++ constructor add initializers to CFG. 532 if (const CXXConstructorDecl *CD = dyn_cast_or_null<CXXConstructorDecl>(D)) { 533 for (CXXConstructorDecl::init_const_reverse_iterator I = CD->init_rbegin(), 534 E = CD->init_rend(); I != E; ++I) { 535 B = addInitializer(*I); 536 if (badCFG) 537 return NULL; 538 } 539 } 540 541 if (B) 542 Succ = B; 543 544 // Backpatch the gotos whose label -> block mappings we didn't know when we 545 // encountered them. 546 for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(), 547 E = BackpatchBlocks.end(); I != E; ++I ) { 548 549 CFGBlock *B = I->block; 550 GotoStmt *G = cast<GotoStmt>(B->getTerminator()); 551 LabelMapTy::iterator LI = LabelMap.find(G->getLabel()); 552 553 // If there is no target for the goto, then we are looking at an 554 // incomplete AST. Handle this by not registering a successor. 555 if (LI == LabelMap.end()) continue; 556 557 JumpTarget JT = LI->second; 558 prependAutomaticObjDtorsWithTerminator(B, I->scopePosition, 559 JT.scopePosition); 560 addSuccessor(B, JT.block); 561 } 562 563 // Add successors to the Indirect Goto Dispatch block (if we have one). 564 if (CFGBlock *B = cfg->getIndirectGotoBlock()) 565 for (LabelSetTy::iterator I = AddressTakenLabels.begin(), 566 E = AddressTakenLabels.end(); I != E; ++I ) { 567 568 // Lookup the target block. 569 LabelMapTy::iterator LI = LabelMap.find(*I); 570 571 // If there is no target block that contains label, then we are looking 572 // at an incomplete AST. Handle this by not registering a successor. 573 if (LI == LabelMap.end()) continue; 574 575 addSuccessor(B, LI->second.block); 576 } 577 578 // Create an empty entry block that has no predecessors. 579 cfg->setEntry(createBlock()); 580 581 return cfg.take(); 582 } 583 584 /// createBlock - Used to lazily create blocks that are connected 585 /// to the current (global) succcessor. 586 CFGBlock *CFGBuilder::createBlock(bool add_successor) { 587 CFGBlock *B = cfg->createBlock(); 588 if (add_successor && Succ) 589 addSuccessor(B, Succ); 590 return B; 591 } 592 593 /// createNoReturnBlock - Used to create a block is a 'noreturn' point in the 594 /// CFG. It is *not* connected to the current (global) successor, and instead 595 /// directly tied to the exit block in order to be reachable. 596 CFGBlock *CFGBuilder::createNoReturnBlock() { 597 CFGBlock *B = createBlock(false); 598 B->setHasNoReturnElement(); 599 addSuccessor(B, &cfg->getExit()); 600 return B; 601 } 602 603 /// addInitializer - Add C++ base or member initializer element to CFG. 604 CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) { 605 if (!BuildOpts.AddInitializers) 606 return Block; 607 608 bool IsReference = false; 609 bool HasTemporaries = false; 610 611 // Destructors of temporaries in initialization expression should be called 612 // after initialization finishes. 613 Expr *Init = I->getInit(); 614 if (Init) { 615 if (FieldDecl *FD = I->getAnyMember()) 616 IsReference = FD->getType()->isReferenceType(); 617 HasTemporaries = isa<ExprWithCleanups>(Init); 618 619 if (BuildOpts.AddImplicitDtors && HasTemporaries) { 620 // Generate destructors for temporaries in initialization expression. 621 VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(), 622 IsReference); 623 } 624 } 625 626 autoCreateBlock(); 627 appendInitializer(Block, I); 628 629 if (Init) { 630 if (HasTemporaries) { 631 // For expression with temporaries go directly to subexpression to omit 632 // generating destructors for the second time. 633 return Visit(cast<ExprWithCleanups>(Init)->getSubExpr()); 634 } 635 return Visit(Init); 636 } 637 638 return Block; 639 } 640 641 /// addAutomaticObjDtors - Add to current block automatic objects destructors 642 /// for objects in range of local scope positions. Use S as trigger statement 643 /// for destructors. 644 void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B, 645 LocalScope::const_iterator E, Stmt *S) { 646 if (!BuildOpts.AddImplicitDtors) 647 return; 648 649 if (B == E) 650 return; 651 652 CFGBlock::iterator InsertPos; 653 654 // We need to append the destructors in reverse order, but any one of them 655 // may be a no-return destructor which changes the CFG. As a result, buffer 656 // this sequence up and replay them in reverse order when appending onto the 657 // CFGBlock(s). 658 SmallVector<VarDecl*, 10> Decls; 659 Decls.reserve(B.distance(E)); 660 for (LocalScope::const_iterator I = B; I != E; ++I) 661 Decls.push_back(*I); 662 663 for (SmallVectorImpl<VarDecl*>::reverse_iterator I = Decls.rbegin(), 664 E = Decls.rend(); 665 I != E; ++I) { 666 // If this destructor is marked as a no-return destructor, we need to 667 // create a new block for the destructor which does not have as a successor 668 // anything built thus far: control won't flow out of this block. 669 QualType Ty = (*I)->getType().getNonReferenceType(); 670 if (const ArrayType *AT = Context->getAsArrayType(Ty)) 671 Ty = AT->getElementType(); 672 const CXXDestructorDecl *Dtor = Ty->getAsCXXRecordDecl()->getDestructor(); 673 if (cast<FunctionType>(Dtor->getType())->getNoReturnAttr()) 674 Block = createNoReturnBlock(); 675 else 676 autoCreateBlock(); 677 678 appendAutomaticObjDtor(Block, *I, S); 679 } 680 } 681 682 /// addImplicitDtorsForDestructor - Add implicit destructors generated for 683 /// base and member objects in destructor. 684 void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) { 685 assert (BuildOpts.AddImplicitDtors 686 && "Can be called only when dtors should be added"); 687 const CXXRecordDecl *RD = DD->getParent(); 688 689 // At the end destroy virtual base objects. 690 for (CXXRecordDecl::base_class_const_iterator VI = RD->vbases_begin(), 691 VE = RD->vbases_end(); VI != VE; ++VI) { 692 const CXXRecordDecl *CD = VI->getType()->getAsCXXRecordDecl(); 693 if (!CD->hasTrivialDestructor()) { 694 autoCreateBlock(); 695 appendBaseDtor(Block, VI); 696 } 697 } 698 699 // Before virtual bases destroy direct base objects. 700 for (CXXRecordDecl::base_class_const_iterator BI = RD->bases_begin(), 701 BE = RD->bases_end(); BI != BE; ++BI) { 702 if (!BI->isVirtual()) { 703 const CXXRecordDecl *CD = BI->getType()->getAsCXXRecordDecl(); 704 if (!CD->hasTrivialDestructor()) { 705 autoCreateBlock(); 706 appendBaseDtor(Block, BI); 707 } 708 } 709 } 710 711 // First destroy member objects. 712 for (CXXRecordDecl::field_iterator FI = RD->field_begin(), 713 FE = RD->field_end(); FI != FE; ++FI) { 714 // Check for constant size array. Set type to array element type. 715 QualType QT = FI->getType(); 716 if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) { 717 if (AT->getSize() == 0) 718 continue; 719 QT = AT->getElementType(); 720 } 721 722 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl()) 723 if (!CD->hasTrivialDestructor()) { 724 autoCreateBlock(); 725 appendMemberDtor(Block, *FI); 726 } 727 } 728 } 729 730 /// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either 731 /// way return valid LocalScope object. 732 LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) { 733 if (!Scope) { 734 llvm::BumpPtrAllocator &alloc = cfg->getAllocator(); 735 Scope = alloc.Allocate<LocalScope>(); 736 BumpVectorContext ctx(alloc); 737 new (Scope) LocalScope(ctx, ScopePos); 738 } 739 return Scope; 740 } 741 742 /// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement 743 /// that should create implicit scope (e.g. if/else substatements). 744 void CFGBuilder::addLocalScopeForStmt(Stmt *S) { 745 if (!BuildOpts.AddImplicitDtors) 746 return; 747 748 LocalScope *Scope = 0; 749 750 // For compound statement we will be creating explicit scope. 751 if (CompoundStmt *CS = dyn_cast<CompoundStmt>(S)) { 752 for (CompoundStmt::body_iterator BI = CS->body_begin(), BE = CS->body_end() 753 ; BI != BE; ++BI) { 754 Stmt *SI = (*BI)->stripLabelLikeStatements(); 755 if (DeclStmt *DS = dyn_cast<DeclStmt>(SI)) 756 Scope = addLocalScopeForDeclStmt(DS, Scope); 757 } 758 return; 759 } 760 761 // For any other statement scope will be implicit and as such will be 762 // interesting only for DeclStmt. 763 if (DeclStmt *DS = dyn_cast<DeclStmt>(S->stripLabelLikeStatements())) 764 addLocalScopeForDeclStmt(DS); 765 } 766 767 /// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will 768 /// reuse Scope if not NULL. 769 LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt *DS, 770 LocalScope* Scope) { 771 if (!BuildOpts.AddImplicitDtors) 772 return Scope; 773 774 for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end() 775 ; DI != DE; ++DI) { 776 if (VarDecl *VD = dyn_cast<VarDecl>(*DI)) 777 Scope = addLocalScopeForVarDecl(VD, Scope); 778 } 779 return Scope; 780 } 781 782 /// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will 783 /// create add scope for automatic objects and temporary objects bound to 784 /// const reference. Will reuse Scope if not NULL. 785 LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD, 786 LocalScope* Scope) { 787 if (!BuildOpts.AddImplicitDtors) 788 return Scope; 789 790 // Check if variable is local. 791 switch (VD->getStorageClass()) { 792 case SC_None: 793 case SC_Auto: 794 case SC_Register: 795 break; 796 default: return Scope; 797 } 798 799 // Check for const references bound to temporary. Set type to pointee. 800 QualType QT = VD->getType(); 801 if (const ReferenceType* RT = QT.getTypePtr()->getAs<ReferenceType>()) { 802 QT = RT->getPointeeType(); 803 if (!QT.isConstQualified()) 804 return Scope; 805 if (!VD->extendsLifetimeOfTemporary()) 806 return Scope; 807 } 808 809 // Check for constant size array. Set type to array element type. 810 if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) { 811 if (AT->getSize() == 0) 812 return Scope; 813 QT = AT->getElementType(); 814 } 815 816 // Check if type is a C++ class with non-trivial destructor. 817 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl()) 818 if (!CD->hasTrivialDestructor()) { 819 // Add the variable to scope 820 Scope = createOrReuseLocalScope(Scope); 821 Scope->addVar(VD); 822 ScopePos = Scope->begin(); 823 } 824 return Scope; 825 } 826 827 /// addLocalScopeAndDtors - For given statement add local scope for it and 828 /// add destructors that will cleanup the scope. Will reuse Scope if not NULL. 829 void CFGBuilder::addLocalScopeAndDtors(Stmt *S) { 830 if (!BuildOpts.AddImplicitDtors) 831 return; 832 833 LocalScope::const_iterator scopeBeginPos = ScopePos; 834 addLocalScopeForStmt(S); 835 addAutomaticObjDtors(ScopePos, scopeBeginPos, S); 836 } 837 838 /// prependAutomaticObjDtorsWithTerminator - Prepend destructor CFGElements for 839 /// variables with automatic storage duration to CFGBlock's elements vector. 840 /// Elements will be prepended to physical beginning of the vector which 841 /// happens to be logical end. Use blocks terminator as statement that specifies 842 /// destructors call site. 843 /// FIXME: This mechanism for adding automatic destructors doesn't handle 844 /// no-return destructors properly. 845 void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk, 846 LocalScope::const_iterator B, LocalScope::const_iterator E) { 847 BumpVectorContext &C = cfg->getBumpVectorContext(); 848 CFGBlock::iterator InsertPos 849 = Blk->beginAutomaticObjDtorsInsert(Blk->end(), B.distance(E), C); 850 for (LocalScope::const_iterator I = B; I != E; ++I) 851 InsertPos = Blk->insertAutomaticObjDtor(InsertPos, *I, 852 Blk->getTerminator()); 853 } 854 855 /// Visit - Walk the subtree of a statement and add extra 856 /// blocks for ternary operators, &&, and ||. We also process "," and 857 /// DeclStmts (which may contain nested control-flow). 858 CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) { 859 if (!S) { 860 badCFG = true; 861 return 0; 862 } 863 864 if (Expr *E = dyn_cast<Expr>(S)) 865 S = E->IgnoreParens(); 866 867 switch (S->getStmtClass()) { 868 default: 869 return VisitStmt(S, asc); 870 871 case Stmt::AddrLabelExprClass: 872 return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc); 873 874 case Stmt::BinaryConditionalOperatorClass: 875 return VisitConditionalOperator(cast<BinaryConditionalOperator>(S), asc); 876 877 case Stmt::BinaryOperatorClass: 878 return VisitBinaryOperator(cast<BinaryOperator>(S), asc); 879 880 case Stmt::BlockExprClass: 881 return VisitBlockExpr(cast<BlockExpr>(S), asc); 882 883 case Stmt::BreakStmtClass: 884 return VisitBreakStmt(cast<BreakStmt>(S)); 885 886 case Stmt::CallExprClass: 887 case Stmt::CXXOperatorCallExprClass: 888 case Stmt::CXXMemberCallExprClass: 889 return VisitCallExpr(cast<CallExpr>(S), asc); 890 891 case Stmt::CaseStmtClass: 892 return VisitCaseStmt(cast<CaseStmt>(S)); 893 894 case Stmt::ChooseExprClass: 895 return VisitChooseExpr(cast<ChooseExpr>(S), asc); 896 897 case Stmt::CompoundStmtClass: 898 return VisitCompoundStmt(cast<CompoundStmt>(S)); 899 900 case Stmt::ConditionalOperatorClass: 901 return VisitConditionalOperator(cast<ConditionalOperator>(S), asc); 902 903 case Stmt::ContinueStmtClass: 904 return VisitContinueStmt(cast<ContinueStmt>(S)); 905 906 case Stmt::CXXCatchStmtClass: 907 return VisitCXXCatchStmt(cast<CXXCatchStmt>(S)); 908 909 case Stmt::ExprWithCleanupsClass: 910 return VisitExprWithCleanups(cast<ExprWithCleanups>(S), asc); 911 912 case Stmt::CXXBindTemporaryExprClass: 913 return VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), asc); 914 915 case Stmt::CXXConstructExprClass: 916 return VisitCXXConstructExpr(cast<CXXConstructExpr>(S), asc); 917 918 case Stmt::CXXFunctionalCastExprClass: 919 return VisitCXXFunctionalCastExpr(cast<CXXFunctionalCastExpr>(S), asc); 920 921 case Stmt::CXXTemporaryObjectExprClass: 922 return VisitCXXTemporaryObjectExpr(cast<CXXTemporaryObjectExpr>(S), asc); 923 924 case Stmt::CXXThrowExprClass: 925 return VisitCXXThrowExpr(cast<CXXThrowExpr>(S)); 926 927 case Stmt::CXXTryStmtClass: 928 return VisitCXXTryStmt(cast<CXXTryStmt>(S)); 929 930 case Stmt::CXXForRangeStmtClass: 931 return VisitCXXForRangeStmt(cast<CXXForRangeStmt>(S)); 932 933 case Stmt::DeclStmtClass: 934 return VisitDeclStmt(cast<DeclStmt>(S)); 935 936 case Stmt::DefaultStmtClass: 937 return VisitDefaultStmt(cast<DefaultStmt>(S)); 938 939 case Stmt::DoStmtClass: 940 return VisitDoStmt(cast<DoStmt>(S)); 941 942 case Stmt::ForStmtClass: 943 return VisitForStmt(cast<ForStmt>(S)); 944 945 case Stmt::GotoStmtClass: 946 return VisitGotoStmt(cast<GotoStmt>(S)); 947 948 case Stmt::IfStmtClass: 949 return VisitIfStmt(cast<IfStmt>(S)); 950 951 case Stmt::ImplicitCastExprClass: 952 return VisitImplicitCastExpr(cast<ImplicitCastExpr>(S), asc); 953 954 case Stmt::IndirectGotoStmtClass: 955 return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S)); 956 957 case Stmt::LabelStmtClass: 958 return VisitLabelStmt(cast<LabelStmt>(S)); 959 960 case Stmt::MemberExprClass: 961 return VisitMemberExpr(cast<MemberExpr>(S), asc); 962 963 case Stmt::ObjCAtCatchStmtClass: 964 return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S)); 965 966 case Stmt::ObjCAtSynchronizedStmtClass: 967 return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S)); 968 969 case Stmt::ObjCAtThrowStmtClass: 970 return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S)); 971 972 case Stmt::ObjCAtTryStmtClass: 973 return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S)); 974 975 case Stmt::ObjCForCollectionStmtClass: 976 return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S)); 977 978 case Stmt::NullStmtClass: 979 return Block; 980 981 case Stmt::ReturnStmtClass: 982 return VisitReturnStmt(cast<ReturnStmt>(S)); 983 984 case Stmt::UnaryExprOrTypeTraitExprClass: 985 return VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S), 986 asc); 987 988 case Stmt::StmtExprClass: 989 return VisitStmtExpr(cast<StmtExpr>(S), asc); 990 991 case Stmt::SwitchStmtClass: 992 return VisitSwitchStmt(cast<SwitchStmt>(S)); 993 994 case Stmt::UnaryOperatorClass: 995 return VisitUnaryOperator(cast<UnaryOperator>(S), asc); 996 997 case Stmt::WhileStmtClass: 998 return VisitWhileStmt(cast<WhileStmt>(S)); 999 } 1000 } 1001 1002 CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) { 1003 if (asc.alwaysAdd(*this, S)) { 1004 autoCreateBlock(); 1005 appendStmt(Block, S); 1006 } 1007 1008 return VisitChildren(S); 1009 } 1010 1011 /// VisitChildren - Visit the children of a Stmt. 1012 CFGBlock *CFGBuilder::VisitChildren(Stmt *Terminator) { 1013 CFGBlock *lastBlock = Block; 1014 for (Stmt::child_range I = Terminator->children(); I; ++I) 1015 if (Stmt *child = *I) 1016 if (CFGBlock *b = Visit(child)) 1017 lastBlock = b; 1018 1019 return lastBlock; 1020 } 1021 1022 CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A, 1023 AddStmtChoice asc) { 1024 AddressTakenLabels.insert(A->getLabel()); 1025 1026 if (asc.alwaysAdd(*this, A)) { 1027 autoCreateBlock(); 1028 appendStmt(Block, A); 1029 } 1030 1031 return Block; 1032 } 1033 1034 CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U, 1035 AddStmtChoice asc) { 1036 if (asc.alwaysAdd(*this, U)) { 1037 autoCreateBlock(); 1038 appendStmt(Block, U); 1039 } 1040 1041 return Visit(U->getSubExpr(), AddStmtChoice()); 1042 } 1043 1044 CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, 1045 AddStmtChoice asc) { 1046 if (B->isLogicalOp()) { // && or || 1047 CFGBlock *ConfluenceBlock = Block ? Block : createBlock(); 1048 appendStmt(ConfluenceBlock, B); 1049 1050 if (badCFG) 1051 return 0; 1052 1053 // create the block evaluating the LHS 1054 CFGBlock *LHSBlock = createBlock(false); 1055 LHSBlock->setTerminator(B); 1056 1057 // create the block evaluating the RHS 1058 Succ = ConfluenceBlock; 1059 Block = NULL; 1060 CFGBlock *RHSBlock = addStmt(B->getRHS()); 1061 1062 if (RHSBlock) { 1063 if (badCFG) 1064 return 0; 1065 } else { 1066 // Create an empty block for cases where the RHS doesn't require 1067 // any explicit statements in the CFG. 1068 RHSBlock = createBlock(); 1069 } 1070 1071 // See if this is a known constant. 1072 TryResult KnownVal = tryEvaluateBool(B->getLHS()); 1073 if (KnownVal.isKnown() && (B->getOpcode() == BO_LOr)) 1074 KnownVal.negate(); 1075 1076 // Now link the LHSBlock with RHSBlock. 1077 if (B->getOpcode() == BO_LOr) { 1078 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); 1079 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); 1080 } else { 1081 assert(B->getOpcode() == BO_LAnd); 1082 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); 1083 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); 1084 } 1085 1086 // Generate the blocks for evaluating the LHS. 1087 Block = LHSBlock; 1088 return addStmt(B->getLHS()); 1089 } 1090 1091 if (B->getOpcode() == BO_Comma) { // , 1092 autoCreateBlock(); 1093 appendStmt(Block, B); 1094 addStmt(B->getRHS()); 1095 return addStmt(B->getLHS()); 1096 } 1097 1098 if (B->isAssignmentOp()) { 1099 if (asc.alwaysAdd(*this, B)) { 1100 autoCreateBlock(); 1101 appendStmt(Block, B); 1102 } 1103 Visit(B->getLHS()); 1104 return Visit(B->getRHS()); 1105 } 1106 1107 if (asc.alwaysAdd(*this, B)) { 1108 autoCreateBlock(); 1109 appendStmt(Block, B); 1110 } 1111 1112 CFGBlock *RBlock = Visit(B->getRHS()); 1113 CFGBlock *LBlock = Visit(B->getLHS()); 1114 // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr 1115 // containing a DoStmt, and the LHS doesn't create a new block, then we should 1116 // return RBlock. Otherwise we'll incorrectly return NULL. 1117 return (LBlock ? LBlock : RBlock); 1118 } 1119 1120 CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) { 1121 if (asc.alwaysAdd(*this, E)) { 1122 autoCreateBlock(); 1123 appendStmt(Block, E); 1124 } 1125 return Block; 1126 } 1127 1128 CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) { 1129 // "break" is a control-flow statement. Thus we stop processing the current 1130 // block. 1131 if (badCFG) 1132 return 0; 1133 1134 // Now create a new block that ends with the break statement. 1135 Block = createBlock(false); 1136 Block->setTerminator(B); 1137 1138 // If there is no target for the break, then we are looking at an incomplete 1139 // AST. This means that the CFG cannot be constructed. 1140 if (BreakJumpTarget.block) { 1141 addAutomaticObjDtors(ScopePos, BreakJumpTarget.scopePosition, B); 1142 addSuccessor(Block, BreakJumpTarget.block); 1143 } else 1144 badCFG = true; 1145 1146 1147 return Block; 1148 } 1149 1150 static bool CanThrow(Expr *E, ASTContext &Ctx) { 1151 QualType Ty = E->getType(); 1152 if (Ty->isFunctionPointerType()) 1153 Ty = Ty->getAs<PointerType>()->getPointeeType(); 1154 else if (Ty->isBlockPointerType()) 1155 Ty = Ty->getAs<BlockPointerType>()->getPointeeType(); 1156 1157 const FunctionType *FT = Ty->getAs<FunctionType>(); 1158 if (FT) { 1159 if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT)) 1160 if (Proto->isNothrow(Ctx)) 1161 return false; 1162 } 1163 return true; 1164 } 1165 1166 CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { 1167 // Compute the callee type. 1168 QualType calleeType = C->getCallee()->getType(); 1169 if (calleeType == Context->BoundMemberTy) { 1170 QualType boundType = Expr::findBoundMemberType(C->getCallee()); 1171 1172 // We should only get a null bound type if processing a dependent 1173 // CFG. Recover by assuming nothing. 1174 if (!boundType.isNull()) calleeType = boundType; 1175 } 1176 1177 // If this is a call to a no-return function, this stops the block here. 1178 bool NoReturn = getFunctionExtInfo(*calleeType).getNoReturn(); 1179 1180 bool AddEHEdge = false; 1181 1182 // Languages without exceptions are assumed to not throw. 1183 if (Context->getLangOptions().Exceptions) { 1184 if (BuildOpts.AddEHEdges) 1185 AddEHEdge = true; 1186 } 1187 1188 if (FunctionDecl *FD = C->getDirectCallee()) { 1189 if (FD->hasAttr<NoReturnAttr>()) 1190 NoReturn = true; 1191 if (FD->hasAttr<NoThrowAttr>()) 1192 AddEHEdge = false; 1193 } 1194 1195 if (!CanThrow(C->getCallee(), *Context)) 1196 AddEHEdge = false; 1197 1198 if (!NoReturn && !AddEHEdge) 1199 return VisitStmt(C, asc.withAlwaysAdd(true)); 1200 1201 if (Block) { 1202 Succ = Block; 1203 if (badCFG) 1204 return 0; 1205 } 1206 1207 if (NoReturn) 1208 Block = createNoReturnBlock(); 1209 else 1210 Block = createBlock(); 1211 1212 appendStmt(Block, C); 1213 1214 if (AddEHEdge) { 1215 // Add exceptional edges. 1216 if (TryTerminatedBlock) 1217 addSuccessor(Block, TryTerminatedBlock); 1218 else 1219 addSuccessor(Block, &cfg->getExit()); 1220 } 1221 1222 return VisitChildren(C); 1223 } 1224 1225 CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C, 1226 AddStmtChoice asc) { 1227 CFGBlock *ConfluenceBlock = Block ? Block : createBlock(); 1228 appendStmt(ConfluenceBlock, C); 1229 if (badCFG) 1230 return 0; 1231 1232 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true); 1233 Succ = ConfluenceBlock; 1234 Block = NULL; 1235 CFGBlock *LHSBlock = Visit(C->getLHS(), alwaysAdd); 1236 if (badCFG) 1237 return 0; 1238 1239 Succ = ConfluenceBlock; 1240 Block = NULL; 1241 CFGBlock *RHSBlock = Visit(C->getRHS(), alwaysAdd); 1242 if (badCFG) 1243 return 0; 1244 1245 Block = createBlock(false); 1246 // See if this is a known constant. 1247 const TryResult& KnownVal = tryEvaluateBool(C->getCond()); 1248 addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); 1249 addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); 1250 Block->setTerminator(C); 1251 return addStmt(C->getCond()); 1252 } 1253 1254 1255 CFGBlock *CFGBuilder::VisitCompoundStmt(CompoundStmt *C) { 1256 addLocalScopeAndDtors(C); 1257 CFGBlock *LastBlock = Block; 1258 1259 for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); 1260 I != E; ++I ) { 1261 // If we hit a segment of code just containing ';' (NullStmts), we can 1262 // get a null block back. In such cases, just use the LastBlock 1263 if (CFGBlock *newBlock = addStmt(*I)) 1264 LastBlock = newBlock; 1265 1266 if (badCFG) 1267 return NULL; 1268 } 1269 1270 return LastBlock; 1271 } 1272 1273 CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C, 1274 AddStmtChoice asc) { 1275 const BinaryConditionalOperator *BCO = dyn_cast<BinaryConditionalOperator>(C); 1276 const OpaqueValueExpr *opaqueValue = (BCO ? BCO->getOpaqueValue() : NULL); 1277 1278 // Create the confluence block that will "merge" the results of the ternary 1279 // expression. 1280 CFGBlock *ConfluenceBlock = Block ? Block : createBlock(); 1281 appendStmt(ConfluenceBlock, C); 1282 if (badCFG) 1283 return 0; 1284 1285 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true); 1286 1287 // Create a block for the LHS expression if there is an LHS expression. A 1288 // GCC extension allows LHS to be NULL, causing the condition to be the 1289 // value that is returned instead. 1290 // e.g: x ?: y is shorthand for: x ? x : y; 1291 Succ = ConfluenceBlock; 1292 Block = NULL; 1293 CFGBlock *LHSBlock = 0; 1294 const Expr *trueExpr = C->getTrueExpr(); 1295 if (trueExpr != opaqueValue) { 1296 LHSBlock = Visit(C->getTrueExpr(), alwaysAdd); 1297 if (badCFG) 1298 return 0; 1299 Block = NULL; 1300 } 1301 else 1302 LHSBlock = ConfluenceBlock; 1303 1304 // Create the block for the RHS expression. 1305 Succ = ConfluenceBlock; 1306 CFGBlock *RHSBlock = Visit(C->getFalseExpr(), alwaysAdd); 1307 if (badCFG) 1308 return 0; 1309 1310 // Create the block that will contain the condition. 1311 Block = createBlock(false); 1312 1313 // See if this is a known constant. 1314 const TryResult& KnownVal = tryEvaluateBool(C->getCond()); 1315 addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); 1316 addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); 1317 Block->setTerminator(C); 1318 Expr *condExpr = C->getCond(); 1319 1320 if (opaqueValue) { 1321 // Run the condition expression if it's not trivially expressed in 1322 // terms of the opaque value (or if there is no opaque value). 1323 if (condExpr != opaqueValue) 1324 addStmt(condExpr); 1325 1326 // Before that, run the common subexpression if there was one. 1327 // At least one of this or the above will be run. 1328 return addStmt(BCO->getCommon()); 1329 } 1330 1331 return addStmt(condExpr); 1332 } 1333 1334 CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) { 1335 // Check if the Decl is for an __label__. If so, elide it from the 1336 // CFG entirely. 1337 if (isa<LabelDecl>(*DS->decl_begin())) 1338 return Block; 1339 1340 // This case also handles static_asserts. 1341 if (DS->isSingleDecl()) 1342 return VisitDeclSubExpr(DS); 1343 1344 CFGBlock *B = 0; 1345 1346 // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy. 1347 typedef SmallVector<Decl*,10> BufTy; 1348 BufTy Buf(DS->decl_begin(), DS->decl_end()); 1349 1350 for (BufTy::reverse_iterator I = Buf.rbegin(), E = Buf.rend(); I != E; ++I) { 1351 // Get the alignment of the new DeclStmt, padding out to >=8 bytes. 1352 unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8 1353 ? 8 : llvm::AlignOf<DeclStmt>::Alignment; 1354 1355 // Allocate the DeclStmt using the BumpPtrAllocator. It will get 1356 // automatically freed with the CFG. 1357 DeclGroupRef DG(*I); 1358 Decl *D = *I; 1359 void *Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A); 1360 DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D)); 1361 1362 // Append the fake DeclStmt to block. 1363 B = VisitDeclSubExpr(DSNew); 1364 } 1365 1366 return B; 1367 } 1368 1369 /// VisitDeclSubExpr - Utility method to add block-level expressions for 1370 /// DeclStmts and initializers in them. 1371 CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) { 1372 assert(DS->isSingleDecl() && "Can handle single declarations only."); 1373 Decl *D = DS->getSingleDecl(); 1374 1375 if (isa<StaticAssertDecl>(D)) { 1376 // static_asserts aren't added to the CFG because they do not impact 1377 // runtime semantics. 1378 return Block; 1379 } 1380 1381 VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl()); 1382 1383 if (!VD) { 1384 autoCreateBlock(); 1385 appendStmt(Block, DS); 1386 return Block; 1387 } 1388 1389 bool IsReference = false; 1390 bool HasTemporaries = false; 1391 1392 // Destructors of temporaries in initialization expression should be called 1393 // after initialization finishes. 1394 Expr *Init = VD->getInit(); 1395 if (Init) { 1396 IsReference = VD->getType()->isReferenceType(); 1397 HasTemporaries = isa<ExprWithCleanups>(Init); 1398 1399 if (BuildOpts.AddImplicitDtors && HasTemporaries) { 1400 // Generate destructors for temporaries in initialization expression. 1401 VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(), 1402 IsReference); 1403 } 1404 } 1405 1406 autoCreateBlock(); 1407 appendStmt(Block, DS); 1408 1409 if (Init) { 1410 if (HasTemporaries) 1411 // For expression with temporaries go directly to subexpression to omit 1412 // generating destructors for the second time. 1413 Visit(cast<ExprWithCleanups>(Init)->getSubExpr()); 1414 else 1415 Visit(Init); 1416 } 1417 1418 // If the type of VD is a VLA, then we must process its size expressions. 1419 for (const VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); 1420 VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) 1421 Block = addStmt(VA->getSizeExpr()); 1422 1423 // Remove variable from local scope. 1424 if (ScopePos && VD == *ScopePos) 1425 ++ScopePos; 1426 1427 return Block; 1428 } 1429 1430 CFGBlock *CFGBuilder::VisitIfStmt(IfStmt *I) { 1431 // We may see an if statement in the middle of a basic block, or it may be the 1432 // first statement we are processing. In either case, we create a new basic 1433 // block. First, we create the blocks for the then...else statements, and 1434 // then we create the block containing the if statement. If we were in the 1435 // middle of a block, we stop processing that block. That block is then the 1436 // implicit successor for the "then" and "else" clauses. 1437 1438 // Save local scope position because in case of condition variable ScopePos 1439 // won't be restored when traversing AST. 1440 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 1441 1442 // Create local scope for possible condition variable. 1443 // Store scope position. Add implicit destructor. 1444 if (VarDecl *VD = I->getConditionVariable()) { 1445 LocalScope::const_iterator BeginScopePos = ScopePos; 1446 addLocalScopeForVarDecl(VD); 1447 addAutomaticObjDtors(ScopePos, BeginScopePos, I); 1448 } 1449 1450 // The block we were processing is now finished. Make it the successor 1451 // block. 1452 if (Block) { 1453 Succ = Block; 1454 if (badCFG) 1455 return 0; 1456 } 1457 1458 // Process the false branch. 1459 CFGBlock *ElseBlock = Succ; 1460 1461 if (Stmt *Else = I->getElse()) { 1462 SaveAndRestore<CFGBlock*> sv(Succ); 1463 1464 // NULL out Block so that the recursive call to Visit will 1465 // create a new basic block. 1466 Block = NULL; 1467 1468 // If branch is not a compound statement create implicit scope 1469 // and add destructors. 1470 if (!isa<CompoundStmt>(Else)) 1471 addLocalScopeAndDtors(Else); 1472 1473 ElseBlock = addStmt(Else); 1474 1475 if (!ElseBlock) // Can occur when the Else body has all NullStmts. 1476 ElseBlock = sv.get(); 1477 else if (Block) { 1478 if (badCFG) 1479 return 0; 1480 } 1481 } 1482 1483 // Process the true branch. 1484 CFGBlock *ThenBlock; 1485 { 1486 Stmt *Then = I->getThen(); 1487 assert(Then); 1488 SaveAndRestore<CFGBlock*> sv(Succ); 1489 Block = NULL; 1490 1491 // If branch is not a compound statement create implicit scope 1492 // and add destructors. 1493 if (!isa<CompoundStmt>(Then)) 1494 addLocalScopeAndDtors(Then); 1495 1496 ThenBlock = addStmt(Then); 1497 1498 if (!ThenBlock) { 1499 // We can reach here if the "then" body has all NullStmts. 1500 // Create an empty block so we can distinguish between true and false 1501 // branches in path-sensitive analyses. 1502 ThenBlock = createBlock(false); 1503 addSuccessor(ThenBlock, sv.get()); 1504 } else if (Block) { 1505 if (badCFG) 1506 return 0; 1507 } 1508 } 1509 1510 // Now create a new block containing the if statement. 1511 Block = createBlock(false); 1512 1513 // Set the terminator of the new block to the If statement. 1514 Block->setTerminator(I); 1515 1516 // See if this is a known constant. 1517 const TryResult &KnownVal = tryEvaluateBool(I->getCond()); 1518 1519 // Now add the successors. 1520 addSuccessor(Block, KnownVal.isFalse() ? NULL : ThenBlock); 1521 addSuccessor(Block, KnownVal.isTrue()? NULL : ElseBlock); 1522 1523 // Add the condition as the last statement in the new block. This may create 1524 // new blocks as the condition may contain control-flow. Any newly created 1525 // blocks will be pointed to be "Block". 1526 Block = addStmt(I->getCond()); 1527 1528 // Finally, if the IfStmt contains a condition variable, add both the IfStmt 1529 // and the condition variable initialization to the CFG. 1530 if (VarDecl *VD = I->getConditionVariable()) { 1531 if (Expr *Init = VD->getInit()) { 1532 autoCreateBlock(); 1533 appendStmt(Block, I->getConditionVariableDeclStmt()); 1534 addStmt(Init); 1535 } 1536 } 1537 1538 return Block; 1539 } 1540 1541 1542 CFGBlock *CFGBuilder::VisitReturnStmt(ReturnStmt *R) { 1543 // If we were in the middle of a block we stop processing that block. 1544 // 1545 // NOTE: If a "return" appears in the middle of a block, this means that the 1546 // code afterwards is DEAD (unreachable). We still keep a basic block 1547 // for that code; a simple "mark-and-sweep" from the entry block will be 1548 // able to report such dead blocks. 1549 1550 // Create the new block. 1551 Block = createBlock(false); 1552 1553 // The Exit block is the only successor. 1554 addAutomaticObjDtors(ScopePos, LocalScope::const_iterator(), R); 1555 addSuccessor(Block, &cfg->getExit()); 1556 1557 // Add the return statement to the block. This may create new blocks if R 1558 // contains control-flow (short-circuit operations). 1559 return VisitStmt(R, AddStmtChoice::AlwaysAdd); 1560 } 1561 1562 CFGBlock *CFGBuilder::VisitLabelStmt(LabelStmt *L) { 1563 // Get the block of the labeled statement. Add it to our map. 1564 addStmt(L->getSubStmt()); 1565 CFGBlock *LabelBlock = Block; 1566 1567 if (!LabelBlock) // This can happen when the body is empty, i.e. 1568 LabelBlock = createBlock(); // scopes that only contains NullStmts. 1569 1570 assert(LabelMap.find(L->getDecl()) == LabelMap.end() && 1571 "label already in map"); 1572 LabelMap[L->getDecl()] = JumpTarget(LabelBlock, ScopePos); 1573 1574 // Labels partition blocks, so this is the end of the basic block we were 1575 // processing (L is the block's label). Because this is label (and we have 1576 // already processed the substatement) there is no extra control-flow to worry 1577 // about. 1578 LabelBlock->setLabel(L); 1579 if (badCFG) 1580 return 0; 1581 1582 // We set Block to NULL to allow lazy creation of a new block (if necessary); 1583 Block = NULL; 1584 1585 // This block is now the implicit successor of other blocks. 1586 Succ = LabelBlock; 1587 1588 return LabelBlock; 1589 } 1590 1591 CFGBlock *CFGBuilder::VisitGotoStmt(GotoStmt *G) { 1592 // Goto is a control-flow statement. Thus we stop processing the current 1593 // block and create a new one. 1594 1595 Block = createBlock(false); 1596 Block->setTerminator(G); 1597 1598 // If we already know the mapping to the label block add the successor now. 1599 LabelMapTy::iterator I = LabelMap.find(G->getLabel()); 1600 1601 if (I == LabelMap.end()) 1602 // We will need to backpatch this block later. 1603 BackpatchBlocks.push_back(JumpSource(Block, ScopePos)); 1604 else { 1605 JumpTarget JT = I->second; 1606 addAutomaticObjDtors(ScopePos, JT.scopePosition, G); 1607 addSuccessor(Block, JT.block); 1608 } 1609 1610 return Block; 1611 } 1612 1613 CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) { 1614 CFGBlock *LoopSuccessor = NULL; 1615 1616 // Save local scope position because in case of condition variable ScopePos 1617 // won't be restored when traversing AST. 1618 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 1619 1620 // Create local scope for init statement and possible condition variable. 1621 // Add destructor for init statement and condition variable. 1622 // Store scope position for continue statement. 1623 if (Stmt *Init = F->getInit()) 1624 addLocalScopeForStmt(Init); 1625 LocalScope::const_iterator LoopBeginScopePos = ScopePos; 1626 1627 if (VarDecl *VD = F->getConditionVariable()) 1628 addLocalScopeForVarDecl(VD); 1629 LocalScope::const_iterator ContinueScopePos = ScopePos; 1630 1631 addAutomaticObjDtors(ScopePos, save_scope_pos.get(), F); 1632 1633 // "for" is a control-flow statement. Thus we stop processing the current 1634 // block. 1635 if (Block) { 1636 if (badCFG) 1637 return 0; 1638 LoopSuccessor = Block; 1639 } else 1640 LoopSuccessor = Succ; 1641 1642 // Save the current value for the break targets. 1643 // All breaks should go to the code following the loop. 1644 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget); 1645 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 1646 1647 // Because of short-circuit evaluation, the condition of the loop can span 1648 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1649 // evaluate the condition. 1650 CFGBlock *ExitConditionBlock = createBlock(false); 1651 CFGBlock *EntryConditionBlock = ExitConditionBlock; 1652 1653 // Set the terminator for the "exit" condition block. 1654 ExitConditionBlock->setTerminator(F); 1655 1656 // Now add the actual condition to the condition block. Because the condition 1657 // itself may contain control-flow, new blocks may be created. 1658 if (Stmt *C = F->getCond()) { 1659 Block = ExitConditionBlock; 1660 EntryConditionBlock = addStmt(C); 1661 if (badCFG) 1662 return 0; 1663 assert(Block == EntryConditionBlock || 1664 (Block == 0 && EntryConditionBlock == Succ)); 1665 1666 // If this block contains a condition variable, add both the condition 1667 // variable and initializer to the CFG. 1668 if (VarDecl *VD = F->getConditionVariable()) { 1669 if (Expr *Init = VD->getInit()) { 1670 autoCreateBlock(); 1671 appendStmt(Block, F->getConditionVariableDeclStmt()); 1672 EntryConditionBlock = addStmt(Init); 1673 assert(Block == EntryConditionBlock); 1674 } 1675 } 1676 1677 if (Block) { 1678 if (badCFG) 1679 return 0; 1680 } 1681 } 1682 1683 // The condition block is the implicit successor for the loop body as well as 1684 // any code above the loop. 1685 Succ = EntryConditionBlock; 1686 1687 // See if this is a known constant. 1688 TryResult KnownVal(true); 1689 1690 if (F->getCond()) 1691 KnownVal = tryEvaluateBool(F->getCond()); 1692 1693 // Now create the loop body. 1694 { 1695 assert(F->getBody()); 1696 1697 // Save the current values for Block, Succ, and continue targets. 1698 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); 1699 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget); 1700 1701 // Create a new block to contain the (bottom) of the loop body. 1702 Block = NULL; 1703 1704 // Loop body should end with destructor of Condition variable (if any). 1705 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, F); 1706 1707 if (Stmt *I = F->getInc()) { 1708 // Generate increment code in its own basic block. This is the target of 1709 // continue statements. 1710 Succ = addStmt(I); 1711 } else { 1712 // No increment code. Create a special, empty, block that is used as the 1713 // target block for "looping back" to the start of the loop. 1714 assert(Succ == EntryConditionBlock); 1715 Succ = Block ? Block : createBlock(); 1716 } 1717 1718 // Finish up the increment (or empty) block if it hasn't been already. 1719 if (Block) { 1720 assert(Block == Succ); 1721 if (badCFG) 1722 return 0; 1723 Block = 0; 1724 } 1725 1726 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos); 1727 1728 // The starting block for the loop increment is the block that should 1729 // represent the 'loop target' for looping back to the start of the loop. 1730 ContinueJumpTarget.block->setLoopTarget(F); 1731 1732 // If body is not a compound statement create implicit scope 1733 // and add destructors. 1734 if (!isa<CompoundStmt>(F->getBody())) 1735 addLocalScopeAndDtors(F->getBody()); 1736 1737 // Now populate the body block, and in the process create new blocks as we 1738 // walk the body of the loop. 1739 CFGBlock *BodyBlock = addStmt(F->getBody()); 1740 1741 if (!BodyBlock) 1742 BodyBlock = ContinueJumpTarget.block;//can happen for "for (...;...;...);" 1743 else if (badCFG) 1744 return 0; 1745 1746 // This new body block is a successor to our "exit" condition block. 1747 addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); 1748 } 1749 1750 // Link up the condition block with the code that follows the loop. (the 1751 // false branch). 1752 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 1753 1754 // If the loop contains initialization, create a new block for those 1755 // statements. This block can also contain statements that precede the loop. 1756 if (Stmt *I = F->getInit()) { 1757 Block = createBlock(); 1758 return addStmt(I); 1759 } 1760 1761 // There is no loop initialization. We are thus basically a while loop. 1762 // NULL out Block to force lazy block construction. 1763 Block = NULL; 1764 Succ = EntryConditionBlock; 1765 return EntryConditionBlock; 1766 } 1767 1768 CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) { 1769 if (asc.alwaysAdd(*this, M)) { 1770 autoCreateBlock(); 1771 appendStmt(Block, M); 1772 } 1773 return Visit(M->getBase()); 1774 } 1775 1776 CFGBlock *CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt *S) { 1777 // Objective-C fast enumeration 'for' statements: 1778 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC 1779 // 1780 // for ( Type newVariable in collection_expression ) { statements } 1781 // 1782 // becomes: 1783 // 1784 // prologue: 1785 // 1. collection_expression 1786 // T. jump to loop_entry 1787 // loop_entry: 1788 // 1. side-effects of element expression 1789 // 1. ObjCForCollectionStmt [performs binding to newVariable] 1790 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil] 1791 // TB: 1792 // statements 1793 // T. jump to loop_entry 1794 // FB: 1795 // what comes after 1796 // 1797 // and 1798 // 1799 // Type existingItem; 1800 // for ( existingItem in expression ) { statements } 1801 // 1802 // becomes: 1803 // 1804 // the same with newVariable replaced with existingItem; the binding works 1805 // the same except that for one ObjCForCollectionStmt::getElement() returns 1806 // a DeclStmt and the other returns a DeclRefExpr. 1807 // 1808 1809 CFGBlock *LoopSuccessor = 0; 1810 1811 if (Block) { 1812 if (badCFG) 1813 return 0; 1814 LoopSuccessor = Block; 1815 Block = 0; 1816 } else 1817 LoopSuccessor = Succ; 1818 1819 // Build the condition blocks. 1820 CFGBlock *ExitConditionBlock = createBlock(false); 1821 1822 // Set the terminator for the "exit" condition block. 1823 ExitConditionBlock->setTerminator(S); 1824 1825 // The last statement in the block should be the ObjCForCollectionStmt, which 1826 // performs the actual binding to 'element' and determines if there are any 1827 // more items in the collection. 1828 appendStmt(ExitConditionBlock, S); 1829 Block = ExitConditionBlock; 1830 1831 // Walk the 'element' expression to see if there are any side-effects. We 1832 // generate new blocks as necessary. We DON'T add the statement by default to 1833 // the CFG unless it contains control-flow. 1834 CFGBlock *EntryConditionBlock = Visit(S->getElement(), 1835 AddStmtChoice::NotAlwaysAdd); 1836 if (Block) { 1837 if (badCFG) 1838 return 0; 1839 Block = 0; 1840 } 1841 1842 // The condition block is the implicit successor for the loop body as well as 1843 // any code above the loop. 1844 Succ = EntryConditionBlock; 1845 1846 // Now create the true branch. 1847 { 1848 // Save the current values for Succ, continue and break targets. 1849 SaveAndRestore<CFGBlock*> save_Succ(Succ); 1850 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), 1851 save_break(BreakJumpTarget); 1852 1853 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 1854 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos); 1855 1856 CFGBlock *BodyBlock = addStmt(S->getBody()); 1857 1858 if (!BodyBlock) 1859 BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;" 1860 else if (Block) { 1861 if (badCFG) 1862 return 0; 1863 } 1864 1865 // This new body block is a successor to our "exit" condition block. 1866 addSuccessor(ExitConditionBlock, BodyBlock); 1867 } 1868 1869 // Link up the condition block with the code that follows the loop. 1870 // (the false branch). 1871 addSuccessor(ExitConditionBlock, LoopSuccessor); 1872 1873 // Now create a prologue block to contain the collection expression. 1874 Block = createBlock(); 1875 return addStmt(S->getCollection()); 1876 } 1877 1878 CFGBlock *CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S) { 1879 // FIXME: Add locking 'primitives' to CFG for @synchronized. 1880 1881 // Inline the body. 1882 CFGBlock *SyncBlock = addStmt(S->getSynchBody()); 1883 1884 // The sync body starts its own basic block. This makes it a little easier 1885 // for diagnostic clients. 1886 if (SyncBlock) { 1887 if (badCFG) 1888 return 0; 1889 1890 Block = 0; 1891 Succ = SyncBlock; 1892 } 1893 1894 // Add the @synchronized to the CFG. 1895 autoCreateBlock(); 1896 appendStmt(Block, S); 1897 1898 // Inline the sync expression. 1899 return addStmt(S->getSynchExpr()); 1900 } 1901 1902 CFGBlock *CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt *S) { 1903 // FIXME 1904 return NYS(); 1905 } 1906 1907 CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) { 1908 CFGBlock *LoopSuccessor = NULL; 1909 1910 // Save local scope position because in case of condition variable ScopePos 1911 // won't be restored when traversing AST. 1912 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 1913 1914 // Create local scope for possible condition variable. 1915 // Store scope position for continue statement. 1916 LocalScope::const_iterator LoopBeginScopePos = ScopePos; 1917 if (VarDecl *VD = W->getConditionVariable()) { 1918 addLocalScopeForVarDecl(VD); 1919 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W); 1920 } 1921 1922 // "while" is a control-flow statement. Thus we stop processing the current 1923 // block. 1924 if (Block) { 1925 if (badCFG) 1926 return 0; 1927 LoopSuccessor = Block; 1928 Block = 0; 1929 } else 1930 LoopSuccessor = Succ; 1931 1932 // Because of short-circuit evaluation, the condition of the loop can span 1933 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1934 // evaluate the condition. 1935 CFGBlock *ExitConditionBlock = createBlock(false); 1936 CFGBlock *EntryConditionBlock = ExitConditionBlock; 1937 1938 // Set the terminator for the "exit" condition block. 1939 ExitConditionBlock->setTerminator(W); 1940 1941 // Now add the actual condition to the condition block. Because the condition 1942 // itself may contain control-flow, new blocks may be created. Thus we update 1943 // "Succ" after adding the condition. 1944 if (Stmt *C = W->getCond()) { 1945 Block = ExitConditionBlock; 1946 EntryConditionBlock = addStmt(C); 1947 // The condition might finish the current 'Block'. 1948 Block = EntryConditionBlock; 1949 1950 // If this block contains a condition variable, add both the condition 1951 // variable and initializer to the CFG. 1952 if (VarDecl *VD = W->getConditionVariable()) { 1953 if (Expr *Init = VD->getInit()) { 1954 autoCreateBlock(); 1955 appendStmt(Block, W->getConditionVariableDeclStmt()); 1956 EntryConditionBlock = addStmt(Init); 1957 assert(Block == EntryConditionBlock); 1958 } 1959 } 1960 1961 if (Block) { 1962 if (badCFG) 1963 return 0; 1964 } 1965 } 1966 1967 // The condition block is the implicit successor for the loop body as well as 1968 // any code above the loop. 1969 Succ = EntryConditionBlock; 1970 1971 // See if this is a known constant. 1972 const TryResult& KnownVal = tryEvaluateBool(W->getCond()); 1973 1974 // Process the loop body. 1975 { 1976 assert(W->getBody()); 1977 1978 // Save the current values for Block, Succ, and continue and break targets 1979 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); 1980 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), 1981 save_break(BreakJumpTarget); 1982 1983 // Create an empty block to represent the transition block for looping back 1984 // to the head of the loop. 1985 Block = 0; 1986 assert(Succ == EntryConditionBlock); 1987 Succ = createBlock(); 1988 Succ->setLoopTarget(W); 1989 ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos); 1990 1991 // All breaks should go to the code following the loop. 1992 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 1993 1994 // NULL out Block to force lazy instantiation of blocks for the body. 1995 Block = NULL; 1996 1997 // Loop body should end with destructor of Condition variable (if any). 1998 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W); 1999 2000 // If body is not a compound statement create implicit scope 2001 // and add destructors. 2002 if (!isa<CompoundStmt>(W->getBody())) 2003 addLocalScopeAndDtors(W->getBody()); 2004 2005 // Create the body. The returned block is the entry to the loop body. 2006 CFGBlock *BodyBlock = addStmt(W->getBody()); 2007 2008 if (!BodyBlock) 2009 BodyBlock = ContinueJumpTarget.block; // can happen for "while(...) ;" 2010 else if (Block) { 2011 if (badCFG) 2012 return 0; 2013 } 2014 2015 // Add the loop body entry as a successor to the condition. 2016 addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); 2017 } 2018 2019 // Link up the condition block with the code that follows the loop. (the 2020 // false branch). 2021 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 2022 2023 // There can be no more statements in the condition block since we loop back 2024 // to this block. NULL out Block to force lazy creation of another block. 2025 Block = NULL; 2026 2027 // Return the condition block, which is the dominating block for the loop. 2028 Succ = EntryConditionBlock; 2029 return EntryConditionBlock; 2030 } 2031 2032 2033 CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt *S) { 2034 // FIXME: For now we pretend that @catch and the code it contains does not 2035 // exit. 2036 return Block; 2037 } 2038 2039 CFGBlock *CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt *S) { 2040 // FIXME: This isn't complete. We basically treat @throw like a return 2041 // statement. 2042 2043 // If we were in the middle of a block we stop processing that block. 2044 if (badCFG) 2045 return 0; 2046 2047 // Create the new block. 2048 Block = createBlock(false); 2049 2050 // The Exit block is the only successor. 2051 addSuccessor(Block, &cfg->getExit()); 2052 2053 // Add the statement to the block. This may create new blocks if S contains 2054 // control-flow (short-circuit operations). 2055 return VisitStmt(S, AddStmtChoice::AlwaysAdd); 2056 } 2057 2058 CFGBlock *CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr *T) { 2059 // If we were in the middle of a block we stop processing that block. 2060 if (badCFG) 2061 return 0; 2062 2063 // Create the new block. 2064 Block = createBlock(false); 2065 2066 if (TryTerminatedBlock) 2067 // The current try statement is the only successor. 2068 addSuccessor(Block, TryTerminatedBlock); 2069 else 2070 // otherwise the Exit block is the only successor. 2071 addSuccessor(Block, &cfg->getExit()); 2072 2073 // Add the statement to the block. This may create new blocks if S contains 2074 // control-flow (short-circuit operations). 2075 return VisitStmt(T, AddStmtChoice::AlwaysAdd); 2076 } 2077 2078 CFGBlock *CFGBuilder::VisitDoStmt(DoStmt *D) { 2079 CFGBlock *LoopSuccessor = NULL; 2080 2081 // "do...while" is a control-flow statement. Thus we stop processing the 2082 // current block. 2083 if (Block) { 2084 if (badCFG) 2085 return 0; 2086 LoopSuccessor = Block; 2087 } else 2088 LoopSuccessor = Succ; 2089 2090 // Because of short-circuit evaluation, the condition of the loop can span 2091 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 2092 // evaluate the condition. 2093 CFGBlock *ExitConditionBlock = createBlock(false); 2094 CFGBlock *EntryConditionBlock = ExitConditionBlock; 2095 2096 // Set the terminator for the "exit" condition block. 2097 ExitConditionBlock->setTerminator(D); 2098 2099 // Now add the actual condition to the condition block. Because the condition 2100 // itself may contain control-flow, new blocks may be created. 2101 if (Stmt *C = D->getCond()) { 2102 Block = ExitConditionBlock; 2103 EntryConditionBlock = addStmt(C); 2104 if (Block) { 2105 if (badCFG) 2106 return 0; 2107 } 2108 } 2109 2110 // The condition block is the implicit successor for the loop body. 2111 Succ = EntryConditionBlock; 2112 2113 // See if this is a known constant. 2114 const TryResult &KnownVal = tryEvaluateBool(D->getCond()); 2115 2116 // Process the loop body. 2117 CFGBlock *BodyBlock = NULL; 2118 { 2119 assert(D->getBody()); 2120 2121 // Save the current values for Block, Succ, and continue and break targets 2122 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); 2123 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), 2124 save_break(BreakJumpTarget); 2125 2126 // All continues within this loop should go to the condition block 2127 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos); 2128 2129 // All breaks should go to the code following the loop. 2130 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 2131 2132 // NULL out Block to force lazy instantiation of blocks for the body. 2133 Block = NULL; 2134 2135 // If body is not a compound statement create implicit scope 2136 // and add destructors. 2137 if (!isa<CompoundStmt>(D->getBody())) 2138 addLocalScopeAndDtors(D->getBody()); 2139 2140 // Create the body. The returned block is the entry to the loop body. 2141 BodyBlock = addStmt(D->getBody()); 2142 2143 if (!BodyBlock) 2144 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)" 2145 else if (Block) { 2146 if (badCFG) 2147 return 0; 2148 } 2149 2150 if (!KnownVal.isFalse()) { 2151 // Add an intermediate block between the BodyBlock and the 2152 // ExitConditionBlock to represent the "loop back" transition. Create an 2153 // empty block to represent the transition block for looping back to the 2154 // head of the loop. 2155 // FIXME: Can we do this more efficiently without adding another block? 2156 Block = NULL; 2157 Succ = BodyBlock; 2158 CFGBlock *LoopBackBlock = createBlock(); 2159 LoopBackBlock->setLoopTarget(D); 2160 2161 // Add the loop body entry as a successor to the condition. 2162 addSuccessor(ExitConditionBlock, LoopBackBlock); 2163 } 2164 else 2165 addSuccessor(ExitConditionBlock, NULL); 2166 } 2167 2168 // Link up the condition block with the code that follows the loop. 2169 // (the false branch). 2170 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 2171 2172 // There can be no more statements in the body block(s) since we loop back to 2173 // the body. NULL out Block to force lazy creation of another block. 2174 Block = NULL; 2175 2176 // Return the loop body, which is the dominating block for the loop. 2177 Succ = BodyBlock; 2178 return BodyBlock; 2179 } 2180 2181 CFGBlock *CFGBuilder::VisitContinueStmt(ContinueStmt *C) { 2182 // "continue" is a control-flow statement. Thus we stop processing the 2183 // current block. 2184 if (badCFG) 2185 return 0; 2186 2187 // Now create a new block that ends with the continue statement. 2188 Block = createBlock(false); 2189 Block->setTerminator(C); 2190 2191 // If there is no target for the continue, then we are looking at an 2192 // incomplete AST. This means the CFG cannot be constructed. 2193 if (ContinueJumpTarget.block) { 2194 addAutomaticObjDtors(ScopePos, ContinueJumpTarget.scopePosition, C); 2195 addSuccessor(Block, ContinueJumpTarget.block); 2196 } else 2197 badCFG = true; 2198 2199 return Block; 2200 } 2201 2202 CFGBlock *CFGBuilder::VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E, 2203 AddStmtChoice asc) { 2204 2205 if (asc.alwaysAdd(*this, E)) { 2206 autoCreateBlock(); 2207 appendStmt(Block, E); 2208 } 2209 2210 // VLA types have expressions that must be evaluated. 2211 CFGBlock *lastBlock = Block; 2212 2213 if (E->isArgumentType()) { 2214 for (const VariableArrayType *VA =FindVA(E->getArgumentType().getTypePtr()); 2215 VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) 2216 lastBlock = addStmt(VA->getSizeExpr()); 2217 } 2218 return lastBlock; 2219 } 2220 2221 /// VisitStmtExpr - Utility method to handle (nested) statement 2222 /// expressions (a GCC extension). 2223 CFGBlock *CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) { 2224 if (asc.alwaysAdd(*this, SE)) { 2225 autoCreateBlock(); 2226 appendStmt(Block, SE); 2227 } 2228 return VisitCompoundStmt(SE->getSubStmt()); 2229 } 2230 2231 CFGBlock *CFGBuilder::VisitSwitchStmt(SwitchStmt *Terminator) { 2232 // "switch" is a control-flow statement. Thus we stop processing the current 2233 // block. 2234 CFGBlock *SwitchSuccessor = NULL; 2235 2236 // Save local scope position because in case of condition variable ScopePos 2237 // won't be restored when traversing AST. 2238 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 2239 2240 // Create local scope for possible condition variable. 2241 // Store scope position. Add implicit destructor. 2242 if (VarDecl *VD = Terminator->getConditionVariable()) { 2243 LocalScope::const_iterator SwitchBeginScopePos = ScopePos; 2244 addLocalScopeForVarDecl(VD); 2245 addAutomaticObjDtors(ScopePos, SwitchBeginScopePos, Terminator); 2246 } 2247 2248 if (Block) { 2249 if (badCFG) 2250 return 0; 2251 SwitchSuccessor = Block; 2252 } else SwitchSuccessor = Succ; 2253 2254 // Save the current "switch" context. 2255 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock), 2256 save_default(DefaultCaseBlock); 2257 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget); 2258 2259 // Set the "default" case to be the block after the switch statement. If the 2260 // switch statement contains a "default:", this value will be overwritten with 2261 // the block for that code. 2262 DefaultCaseBlock = SwitchSuccessor; 2263 2264 // Create a new block that will contain the switch statement. 2265 SwitchTerminatedBlock = createBlock(false); 2266 2267 // Now process the switch body. The code after the switch is the implicit 2268 // successor. 2269 Succ = SwitchSuccessor; 2270 BreakJumpTarget = JumpTarget(SwitchSuccessor, ScopePos); 2271 2272 // When visiting the body, the case statements should automatically get linked 2273 // up to the switch. We also don't keep a pointer to the body, since all 2274 // control-flow from the switch goes to case/default statements. 2275 assert(Terminator->getBody() && "switch must contain a non-NULL body"); 2276 Block = NULL; 2277 2278 // For pruning unreachable case statements, save the current state 2279 // for tracking the condition value. 2280 SaveAndRestore<bool> save_switchExclusivelyCovered(switchExclusivelyCovered, 2281 false); 2282 2283 // Determine if the switch condition can be explicitly evaluated. 2284 assert(Terminator->getCond() && "switch condition must be non-NULL"); 2285 Expr::EvalResult result; 2286 bool b = tryEvaluate(Terminator->getCond(), result); 2287 SaveAndRestore<Expr::EvalResult*> save_switchCond(switchCond, 2288 b ? &result : 0); 2289 2290 // If body is not a compound statement create implicit scope 2291 // and add destructors. 2292 if (!isa<CompoundStmt>(Terminator->getBody())) 2293 addLocalScopeAndDtors(Terminator->getBody()); 2294 2295 addStmt(Terminator->getBody()); 2296 if (Block) { 2297 if (badCFG) 2298 return 0; 2299 } 2300 2301 // If we have no "default:" case, the default transition is to the code 2302 // following the switch body. Moreover, take into account if all the 2303 // cases of a switch are covered (e.g., switching on an enum value). 2304 addSuccessor(SwitchTerminatedBlock, 2305 switchExclusivelyCovered || Terminator->isAllEnumCasesCovered() 2306 ? 0 : DefaultCaseBlock); 2307 2308 // Add the terminator and condition in the switch block. 2309 SwitchTerminatedBlock->setTerminator(Terminator); 2310 Block = SwitchTerminatedBlock; 2311 Block = addStmt(Terminator->getCond()); 2312 2313 // Finally, if the SwitchStmt contains a condition variable, add both the 2314 // SwitchStmt and the condition variable initialization to the CFG. 2315 if (VarDecl *VD = Terminator->getConditionVariable()) { 2316 if (Expr *Init = VD->getInit()) { 2317 autoCreateBlock(); 2318 appendStmt(Block, Terminator->getConditionVariableDeclStmt()); 2319 addStmt(Init); 2320 } 2321 } 2322 2323 return Block; 2324 } 2325 2326 static bool shouldAddCase(bool &switchExclusivelyCovered, 2327 const Expr::EvalResult *switchCond, 2328 const CaseStmt *CS, 2329 ASTContext &Ctx) { 2330 if (!switchCond) 2331 return true; 2332 2333 bool addCase = false; 2334 2335 if (!switchExclusivelyCovered) { 2336 if (switchCond->Val.isInt()) { 2337 // Evaluate the LHS of the case value. 2338 const llvm::APSInt &lhsInt = CS->getLHS()->EvaluateKnownConstInt(Ctx); 2339 const llvm::APSInt &condInt = switchCond->Val.getInt(); 2340 2341 if (condInt == lhsInt) { 2342 addCase = true; 2343 switchExclusivelyCovered = true; 2344 } 2345 else if (condInt < lhsInt) { 2346 if (const Expr *RHS = CS->getRHS()) { 2347 // Evaluate the RHS of the case value. 2348 const llvm::APSInt &V2 = RHS->EvaluateKnownConstInt(Ctx); 2349 if (V2 <= condInt) { 2350 addCase = true; 2351 switchExclusivelyCovered = true; 2352 } 2353 } 2354 } 2355 } 2356 else 2357 addCase = true; 2358 } 2359 return addCase; 2360 } 2361 2362 CFGBlock *CFGBuilder::VisitCaseStmt(CaseStmt *CS) { 2363 // CaseStmts are essentially labels, so they are the first statement in a 2364 // block. 2365 CFGBlock *TopBlock = 0, *LastBlock = 0; 2366 2367 if (Stmt *Sub = CS->getSubStmt()) { 2368 // For deeply nested chains of CaseStmts, instead of doing a recursion 2369 // (which can blow out the stack), manually unroll and create blocks 2370 // along the way. 2371 while (isa<CaseStmt>(Sub)) { 2372 CFGBlock *currentBlock = createBlock(false); 2373 currentBlock->setLabel(CS); 2374 2375 if (TopBlock) 2376 addSuccessor(LastBlock, currentBlock); 2377 else 2378 TopBlock = currentBlock; 2379 2380 addSuccessor(SwitchTerminatedBlock, 2381 shouldAddCase(switchExclusivelyCovered, switchCond, 2382 CS, *Context) 2383 ? currentBlock : 0); 2384 2385 LastBlock = currentBlock; 2386 CS = cast<CaseStmt>(Sub); 2387 Sub = CS->getSubStmt(); 2388 } 2389 2390 addStmt(Sub); 2391 } 2392 2393 CFGBlock *CaseBlock = Block; 2394 if (!CaseBlock) 2395 CaseBlock = createBlock(); 2396 2397 // Cases statements partition blocks, so this is the top of the basic block we 2398 // were processing (the "case XXX:" is the label). 2399 CaseBlock->setLabel(CS); 2400 2401 if (badCFG) 2402 return 0; 2403 2404 // Add this block to the list of successors for the block with the switch 2405 // statement. 2406 assert(SwitchTerminatedBlock); 2407 addSuccessor(SwitchTerminatedBlock, 2408 shouldAddCase(switchExclusivelyCovered, switchCond, 2409 CS, *Context) 2410 ? CaseBlock : 0); 2411 2412 // We set Block to NULL to allow lazy creation of a new block (if necessary) 2413 Block = NULL; 2414 2415 if (TopBlock) { 2416 addSuccessor(LastBlock, CaseBlock); 2417 Succ = TopBlock; 2418 } else { 2419 // This block is now the implicit successor of other blocks. 2420 Succ = CaseBlock; 2421 } 2422 2423 return Succ; 2424 } 2425 2426 CFGBlock *CFGBuilder::VisitDefaultStmt(DefaultStmt *Terminator) { 2427 if (Terminator->getSubStmt()) 2428 addStmt(Terminator->getSubStmt()); 2429 2430 DefaultCaseBlock = Block; 2431 2432 if (!DefaultCaseBlock) 2433 DefaultCaseBlock = createBlock(); 2434 2435 // Default statements partition blocks, so this is the top of the basic block 2436 // we were processing (the "default:" is the label). 2437 DefaultCaseBlock->setLabel(Terminator); 2438 2439 if (badCFG) 2440 return 0; 2441 2442 // Unlike case statements, we don't add the default block to the successors 2443 // for the switch statement immediately. This is done when we finish 2444 // processing the switch statement. This allows for the default case 2445 // (including a fall-through to the code after the switch statement) to always 2446 // be the last successor of a switch-terminated block. 2447 2448 // We set Block to NULL to allow lazy creation of a new block (if necessary) 2449 Block = NULL; 2450 2451 // This block is now the implicit successor of other blocks. 2452 Succ = DefaultCaseBlock; 2453 2454 return DefaultCaseBlock; 2455 } 2456 2457 CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) { 2458 // "try"/"catch" is a control-flow statement. Thus we stop processing the 2459 // current block. 2460 CFGBlock *TrySuccessor = NULL; 2461 2462 if (Block) { 2463 if (badCFG) 2464 return 0; 2465 TrySuccessor = Block; 2466 } else TrySuccessor = Succ; 2467 2468 CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock; 2469 2470 // Create a new block that will contain the try statement. 2471 CFGBlock *NewTryTerminatedBlock = createBlock(false); 2472 // Add the terminator in the try block. 2473 NewTryTerminatedBlock->setTerminator(Terminator); 2474 2475 bool HasCatchAll = false; 2476 for (unsigned h = 0; h <Terminator->getNumHandlers(); ++h) { 2477 // The code after the try is the implicit successor. 2478 Succ = TrySuccessor; 2479 CXXCatchStmt *CS = Terminator->getHandler(h); 2480 if (CS->getExceptionDecl() == 0) { 2481 HasCatchAll = true; 2482 } 2483 Block = NULL; 2484 CFGBlock *CatchBlock = VisitCXXCatchStmt(CS); 2485 if (CatchBlock == 0) 2486 return 0; 2487 // Add this block to the list of successors for the block with the try 2488 // statement. 2489 addSuccessor(NewTryTerminatedBlock, CatchBlock); 2490 } 2491 if (!HasCatchAll) { 2492 if (PrevTryTerminatedBlock) 2493 addSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock); 2494 else 2495 addSuccessor(NewTryTerminatedBlock, &cfg->getExit()); 2496 } 2497 2498 // The code after the try is the implicit successor. 2499 Succ = TrySuccessor; 2500 2501 // Save the current "try" context. 2502 SaveAndRestore<CFGBlock*> save_try(TryTerminatedBlock, NewTryTerminatedBlock); 2503 cfg->addTryDispatchBlock(TryTerminatedBlock); 2504 2505 assert(Terminator->getTryBlock() && "try must contain a non-NULL body"); 2506 Block = NULL; 2507 Block = addStmt(Terminator->getTryBlock()); 2508 return Block; 2509 } 2510 2511 CFGBlock *CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt *CS) { 2512 // CXXCatchStmt are treated like labels, so they are the first statement in a 2513 // block. 2514 2515 // Save local scope position because in case of exception variable ScopePos 2516 // won't be restored when traversing AST. 2517 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 2518 2519 // Create local scope for possible exception variable. 2520 // Store scope position. Add implicit destructor. 2521 if (VarDecl *VD = CS->getExceptionDecl()) { 2522 LocalScope::const_iterator BeginScopePos = ScopePos; 2523 addLocalScopeForVarDecl(VD); 2524 addAutomaticObjDtors(ScopePos, BeginScopePos, CS); 2525 } 2526 2527 if (CS->getHandlerBlock()) 2528 addStmt(CS->getHandlerBlock()); 2529 2530 CFGBlock *CatchBlock = Block; 2531 if (!CatchBlock) 2532 CatchBlock = createBlock(); 2533 2534 CatchBlock->setLabel(CS); 2535 2536 if (badCFG) 2537 return 0; 2538 2539 // We set Block to NULL to allow lazy creation of a new block (if necessary) 2540 Block = NULL; 2541 2542 return CatchBlock; 2543 } 2544 2545 CFGBlock *CFGBuilder::VisitCXXForRangeStmt(CXXForRangeStmt *S) { 2546 // C++0x for-range statements are specified as [stmt.ranged]: 2547 // 2548 // { 2549 // auto && __range = range-init; 2550 // for ( auto __begin = begin-expr, 2551 // __end = end-expr; 2552 // __begin != __end; 2553 // ++__begin ) { 2554 // for-range-declaration = *__begin; 2555 // statement 2556 // } 2557 // } 2558 2559 // Save local scope position before the addition of the implicit variables. 2560 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 2561 2562 // Create local scopes and destructors for range, begin and end variables. 2563 if (Stmt *Range = S->getRangeStmt()) 2564 addLocalScopeForStmt(Range); 2565 if (Stmt *BeginEnd = S->getBeginEndStmt()) 2566 addLocalScopeForStmt(BeginEnd); 2567 addAutomaticObjDtors(ScopePos, save_scope_pos.get(), S); 2568 2569 LocalScope::const_iterator ContinueScopePos = ScopePos; 2570 2571 // "for" is a control-flow statement. Thus we stop processing the current 2572 // block. 2573 CFGBlock *LoopSuccessor = NULL; 2574 if (Block) { 2575 if (badCFG) 2576 return 0; 2577 LoopSuccessor = Block; 2578 } else 2579 LoopSuccessor = Succ; 2580 2581 // Save the current value for the break targets. 2582 // All breaks should go to the code following the loop. 2583 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget); 2584 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 2585 2586 // The block for the __begin != __end expression. 2587 CFGBlock *ConditionBlock = createBlock(false); 2588 ConditionBlock->setTerminator(S); 2589 2590 // Now add the actual condition to the condition block. 2591 if (Expr *C = S->getCond()) { 2592 Block = ConditionBlock; 2593 CFGBlock *BeginConditionBlock = addStmt(C); 2594 if (badCFG) 2595 return 0; 2596 assert(BeginConditionBlock == ConditionBlock && 2597 "condition block in for-range was unexpectedly complex"); 2598 (void)BeginConditionBlock; 2599 } 2600 2601 // The condition block is the implicit successor for the loop body as well as 2602 // any code above the loop. 2603 Succ = ConditionBlock; 2604 2605 // See if this is a known constant. 2606 TryResult KnownVal(true); 2607 2608 if (S->getCond()) 2609 KnownVal = tryEvaluateBool(S->getCond()); 2610 2611 // Now create the loop body. 2612 { 2613 assert(S->getBody()); 2614 2615 // Save the current values for Block, Succ, and continue targets. 2616 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); 2617 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget); 2618 2619 // Generate increment code in its own basic block. This is the target of 2620 // continue statements. 2621 Block = 0; 2622 Succ = addStmt(S->getInc()); 2623 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos); 2624 2625 // The starting block for the loop increment is the block that should 2626 // represent the 'loop target' for looping back to the start of the loop. 2627 ContinueJumpTarget.block->setLoopTarget(S); 2628 2629 // Finish up the increment block and prepare to start the loop body. 2630 assert(Block); 2631 if (badCFG) 2632 return 0; 2633 Block = 0; 2634 2635 2636 // Add implicit scope and dtors for loop variable. 2637 addLocalScopeAndDtors(S->getLoopVarStmt()); 2638 2639 // Populate a new block to contain the loop body and loop variable. 2640 Block = addStmt(S->getBody()); 2641 if (badCFG) 2642 return 0; 2643 Block = addStmt(S->getLoopVarStmt()); 2644 if (badCFG) 2645 return 0; 2646 2647 // This new body block is a successor to our condition block. 2648 addSuccessor(ConditionBlock, KnownVal.isFalse() ? 0 : Block); 2649 } 2650 2651 // Link up the condition block with the code that follows the loop (the 2652 // false branch). 2653 addSuccessor(ConditionBlock, KnownVal.isTrue() ? 0 : LoopSuccessor); 2654 2655 // Add the initialization statements. 2656 Block = createBlock(); 2657 addStmt(S->getBeginEndStmt()); 2658 return addStmt(S->getRangeStmt()); 2659 } 2660 2661 CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E, 2662 AddStmtChoice asc) { 2663 if (BuildOpts.AddImplicitDtors) { 2664 // If adding implicit destructors visit the full expression for adding 2665 // destructors of temporaries. 2666 VisitForTemporaryDtors(E->getSubExpr()); 2667 2668 // Full expression has to be added as CFGStmt so it will be sequenced 2669 // before destructors of it's temporaries. 2670 asc = asc.withAlwaysAdd(true); 2671 } 2672 return Visit(E->getSubExpr(), asc); 2673 } 2674 2675 CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E, 2676 AddStmtChoice asc) { 2677 if (asc.alwaysAdd(*this, E)) { 2678 autoCreateBlock(); 2679 appendStmt(Block, E); 2680 2681 // We do not want to propagate the AlwaysAdd property. 2682 asc = asc.withAlwaysAdd(false); 2683 } 2684 return Visit(E->getSubExpr(), asc); 2685 } 2686 2687 CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C, 2688 AddStmtChoice asc) { 2689 autoCreateBlock(); 2690 if (!C->isElidable()) 2691 appendStmt(Block, C); 2692 2693 return VisitChildren(C); 2694 } 2695 2696 CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E, 2697 AddStmtChoice asc) { 2698 if (asc.alwaysAdd(*this, E)) { 2699 autoCreateBlock(); 2700 appendStmt(Block, E); 2701 // We do not want to propagate the AlwaysAdd property. 2702 asc = asc.withAlwaysAdd(false); 2703 } 2704 return Visit(E->getSubExpr(), asc); 2705 } 2706 2707 CFGBlock *CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C, 2708 AddStmtChoice asc) { 2709 autoCreateBlock(); 2710 appendStmt(Block, C); 2711 return VisitChildren(C); 2712 } 2713 2714 CFGBlock *CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr *E, 2715 AddStmtChoice asc) { 2716 if (asc.alwaysAdd(*this, E)) { 2717 autoCreateBlock(); 2718 appendStmt(Block, E); 2719 } 2720 return Visit(E->getSubExpr(), AddStmtChoice()); 2721 } 2722 2723 CFGBlock *CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt *I) { 2724 // Lazily create the indirect-goto dispatch block if there isn't one already. 2725 CFGBlock *IBlock = cfg->getIndirectGotoBlock(); 2726 2727 if (!IBlock) { 2728 IBlock = createBlock(false); 2729 cfg->setIndirectGotoBlock(IBlock); 2730 } 2731 2732 // IndirectGoto is a control-flow statement. Thus we stop processing the 2733 // current block and create a new one. 2734 if (badCFG) 2735 return 0; 2736 2737 Block = createBlock(false); 2738 Block->setTerminator(I); 2739 addSuccessor(Block, IBlock); 2740 return addStmt(I->getTarget()); 2741 } 2742 2743 CFGBlock *CFGBuilder::VisitForTemporaryDtors(Stmt *E, bool BindToTemporary) { 2744 tryAgain: 2745 if (!E) { 2746 badCFG = true; 2747 return NULL; 2748 } 2749 switch (E->getStmtClass()) { 2750 default: 2751 return VisitChildrenForTemporaryDtors(E); 2752 2753 case Stmt::BinaryOperatorClass: 2754 return VisitBinaryOperatorForTemporaryDtors(cast<BinaryOperator>(E)); 2755 2756 case Stmt::CXXBindTemporaryExprClass: 2757 return VisitCXXBindTemporaryExprForTemporaryDtors( 2758 cast<CXXBindTemporaryExpr>(E), BindToTemporary); 2759 2760 case Stmt::BinaryConditionalOperatorClass: 2761 case Stmt::ConditionalOperatorClass: 2762 return VisitConditionalOperatorForTemporaryDtors( 2763 cast<AbstractConditionalOperator>(E), BindToTemporary); 2764 2765 case Stmt::ImplicitCastExprClass: 2766 // For implicit cast we want BindToTemporary to be passed further. 2767 E = cast<CastExpr>(E)->getSubExpr(); 2768 goto tryAgain; 2769 2770 case Stmt::ParenExprClass: 2771 E = cast<ParenExpr>(E)->getSubExpr(); 2772 goto tryAgain; 2773 2774 case Stmt::MaterializeTemporaryExprClass: 2775 E = cast<MaterializeTemporaryExpr>(E)->GetTemporaryExpr(); 2776 goto tryAgain; 2777 } 2778 } 2779 2780 CFGBlock *CFGBuilder::VisitChildrenForTemporaryDtors(Stmt *E) { 2781 // When visiting children for destructors we want to visit them in reverse 2782 // order. Because there's no reverse iterator for children must to reverse 2783 // them in helper vector. 2784 typedef SmallVector<Stmt *, 4> ChildrenVect; 2785 ChildrenVect ChildrenRev; 2786 for (Stmt::child_range I = E->children(); I; ++I) { 2787 if (*I) ChildrenRev.push_back(*I); 2788 } 2789 2790 CFGBlock *B = Block; 2791 for (ChildrenVect::reverse_iterator I = ChildrenRev.rbegin(), 2792 L = ChildrenRev.rend(); I != L; ++I) { 2793 if (CFGBlock *R = VisitForTemporaryDtors(*I)) 2794 B = R; 2795 } 2796 return B; 2797 } 2798 2799 CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E) { 2800 if (E->isLogicalOp()) { 2801 // Destructors for temporaries in LHS expression should be called after 2802 // those for RHS expression. Even if this will unnecessarily create a block, 2803 // this block will be used at least by the full expression. 2804 autoCreateBlock(); 2805 CFGBlock *ConfluenceBlock = VisitForTemporaryDtors(E->getLHS()); 2806 if (badCFG) 2807 return NULL; 2808 2809 Succ = ConfluenceBlock; 2810 Block = NULL; 2811 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS()); 2812 2813 if (RHSBlock) { 2814 if (badCFG) 2815 return NULL; 2816 2817 // If RHS expression did produce destructors we need to connect created 2818 // blocks to CFG in same manner as for binary operator itself. 2819 CFGBlock *LHSBlock = createBlock(false); 2820 LHSBlock->setTerminator(CFGTerminator(E, true)); 2821 2822 // For binary operator LHS block is before RHS in list of predecessors 2823 // of ConfluenceBlock. 2824 std::reverse(ConfluenceBlock->pred_begin(), 2825 ConfluenceBlock->pred_end()); 2826 2827 // See if this is a known constant. 2828 TryResult KnownVal = tryEvaluateBool(E->getLHS()); 2829 if (KnownVal.isKnown() && (E->getOpcode() == BO_LOr)) 2830 KnownVal.negate(); 2831 2832 // Link LHSBlock with RHSBlock exactly the same way as for binary operator 2833 // itself. 2834 if (E->getOpcode() == BO_LOr) { 2835 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); 2836 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); 2837 } else { 2838 assert (E->getOpcode() == BO_LAnd); 2839 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); 2840 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); 2841 } 2842 2843 Block = LHSBlock; 2844 return LHSBlock; 2845 } 2846 2847 Block = ConfluenceBlock; 2848 return ConfluenceBlock; 2849 } 2850 2851 if (E->isAssignmentOp()) { 2852 // For assignment operator (=) LHS expression is visited 2853 // before RHS expression. For destructors visit them in reverse order. 2854 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS()); 2855 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS()); 2856 return LHSBlock ? LHSBlock : RHSBlock; 2857 } 2858 2859 // For any other binary operator RHS expression is visited before 2860 // LHS expression (order of children). For destructors visit them in reverse 2861 // order. 2862 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS()); 2863 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS()); 2864 return RHSBlock ? RHSBlock : LHSBlock; 2865 } 2866 2867 CFGBlock *CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors( 2868 CXXBindTemporaryExpr *E, bool BindToTemporary) { 2869 // First add destructors for temporaries in subexpression. 2870 CFGBlock *B = VisitForTemporaryDtors(E->getSubExpr()); 2871 if (!BindToTemporary) { 2872 // If lifetime of temporary is not prolonged (by assigning to constant 2873 // reference) add destructor for it. 2874 2875 // If the destructor is marked as a no-return destructor, we need to create 2876 // a new block for the destructor which does not have as a successor 2877 // anything built thus far. Control won't flow out of this block. 2878 const CXXDestructorDecl *Dtor = E->getTemporary()->getDestructor(); 2879 if (cast<FunctionType>(Dtor->getType())->getNoReturnAttr()) 2880 Block = createNoReturnBlock(); 2881 else 2882 autoCreateBlock(); 2883 2884 appendTemporaryDtor(Block, E); 2885 B = Block; 2886 } 2887 return B; 2888 } 2889 2890 CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaryDtors( 2891 AbstractConditionalOperator *E, bool BindToTemporary) { 2892 // First add destructors for condition expression. Even if this will 2893 // unnecessarily create a block, this block will be used at least by the full 2894 // expression. 2895 autoCreateBlock(); 2896 CFGBlock *ConfluenceBlock = VisitForTemporaryDtors(E->getCond()); 2897 if (badCFG) 2898 return NULL; 2899 if (BinaryConditionalOperator *BCO 2900 = dyn_cast<BinaryConditionalOperator>(E)) { 2901 ConfluenceBlock = VisitForTemporaryDtors(BCO->getCommon()); 2902 if (badCFG) 2903 return NULL; 2904 } 2905 2906 // Try to add block with destructors for LHS expression. 2907 CFGBlock *LHSBlock = NULL; 2908 Succ = ConfluenceBlock; 2909 Block = NULL; 2910 LHSBlock = VisitForTemporaryDtors(E->getTrueExpr(), BindToTemporary); 2911 if (badCFG) 2912 return NULL; 2913 2914 // Try to add block with destructors for RHS expression; 2915 Succ = ConfluenceBlock; 2916 Block = NULL; 2917 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getFalseExpr(), 2918 BindToTemporary); 2919 if (badCFG) 2920 return NULL; 2921 2922 if (!RHSBlock && !LHSBlock) { 2923 // If neither LHS nor RHS expression had temporaries to destroy don't create 2924 // more blocks. 2925 Block = ConfluenceBlock; 2926 return Block; 2927 } 2928 2929 Block = createBlock(false); 2930 Block->setTerminator(CFGTerminator(E, true)); 2931 2932 // See if this is a known constant. 2933 const TryResult &KnownVal = tryEvaluateBool(E->getCond()); 2934 2935 if (LHSBlock) { 2936 addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); 2937 } else if (KnownVal.isFalse()) { 2938 addSuccessor(Block, NULL); 2939 } else { 2940 addSuccessor(Block, ConfluenceBlock); 2941 std::reverse(ConfluenceBlock->pred_begin(), ConfluenceBlock->pred_end()); 2942 } 2943 2944 if (!RHSBlock) 2945 RHSBlock = ConfluenceBlock; 2946 addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); 2947 2948 return Block; 2949 } 2950 2951 } // end anonymous namespace 2952 2953 /// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has 2954 /// no successors or predecessors. If this is the first block created in the 2955 /// CFG, it is automatically set to be the Entry and Exit of the CFG. 2956 CFGBlock *CFG::createBlock() { 2957 bool first_block = begin() == end(); 2958 2959 // Create the block. 2960 CFGBlock *Mem = getAllocator().Allocate<CFGBlock>(); 2961 new (Mem) CFGBlock(NumBlockIDs++, BlkBVC); 2962 Blocks.push_back(Mem, BlkBVC); 2963 2964 // If this is the first block, set it as the Entry and Exit. 2965 if (first_block) 2966 Entry = Exit = &back(); 2967 2968 // Return the block. 2969 return &back(); 2970 } 2971 2972 /// buildCFG - Constructs a CFG from an AST. Ownership of the returned 2973 /// CFG is returned to the caller. 2974 CFG* CFG::buildCFG(const Decl *D, Stmt *Statement, ASTContext *C, 2975 const BuildOptions &BO) { 2976 CFGBuilder Builder(C, BO); 2977 return Builder.buildCFG(D, Statement); 2978 } 2979 2980 const CXXDestructorDecl * 2981 CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const { 2982 switch (getKind()) { 2983 case CFGElement::Invalid: 2984 case CFGElement::Statement: 2985 case CFGElement::Initializer: 2986 llvm_unreachable("getDestructorDecl should only be used with " 2987 "ImplicitDtors"); 2988 case CFGElement::AutomaticObjectDtor: { 2989 const VarDecl *var = cast<CFGAutomaticObjDtor>(this)->getVarDecl(); 2990 QualType ty = var->getType(); 2991 ty = ty.getNonReferenceType(); 2992 if (const ArrayType *arrayType = astContext.getAsArrayType(ty)) { 2993 ty = arrayType->getElementType(); 2994 } 2995 const RecordType *recordType = ty->getAs<RecordType>(); 2996 const CXXRecordDecl *classDecl = 2997 cast<CXXRecordDecl>(recordType->getDecl()); 2998 return classDecl->getDestructor(); 2999 } 3000 case CFGElement::TemporaryDtor: { 3001 const CXXBindTemporaryExpr *bindExpr = 3002 cast<CFGTemporaryDtor>(this)->getBindTemporaryExpr(); 3003 const CXXTemporary *temp = bindExpr->getTemporary(); 3004 return temp->getDestructor(); 3005 } 3006 case CFGElement::BaseDtor: 3007 case CFGElement::MemberDtor: 3008 3009 // Not yet supported. 3010 return 0; 3011 } 3012 llvm_unreachable("getKind() returned bogus value"); 3013 return 0; 3014 } 3015 3016 bool CFGImplicitDtor::isNoReturn(ASTContext &astContext) const { 3017 if (const CXXDestructorDecl *cdecl = getDestructorDecl(astContext)) { 3018 QualType ty = cdecl->getType(); 3019 return cast<FunctionType>(ty)->getNoReturnAttr(); 3020 } 3021 return false; 3022 } 3023 3024 //===----------------------------------------------------------------------===// 3025 // CFG: Queries for BlkExprs. 3026 //===----------------------------------------------------------------------===// 3027 3028 namespace { 3029 typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy; 3030 } 3031 3032 static void FindSubExprAssignments(const Stmt *S, 3033 llvm::SmallPtrSet<const Expr*,50>& Set) { 3034 if (!S) 3035 return; 3036 3037 for (Stmt::const_child_range I = S->children(); I; ++I) { 3038 const Stmt *child = *I; 3039 if (!child) 3040 continue; 3041 3042 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(child)) 3043 if (B->isAssignmentOp()) Set.insert(B); 3044 3045 FindSubExprAssignments(child, Set); 3046 } 3047 } 3048 3049 static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { 3050 BlkExprMapTy* M = new BlkExprMapTy(); 3051 3052 // Look for assignments that are used as subexpressions. These are the only 3053 // assignments that we want to *possibly* register as a block-level 3054 // expression. Basically, if an assignment occurs both in a subexpression and 3055 // at the block-level, it is a block-level expression. 3056 llvm::SmallPtrSet<const Expr*,50> SubExprAssignments; 3057 3058 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) 3059 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) 3060 if (const CFGStmt *S = BI->getAs<CFGStmt>()) 3061 FindSubExprAssignments(S->getStmt(), SubExprAssignments); 3062 3063 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { 3064 3065 // Iterate over the statements again on identify the Expr* and Stmt* at the 3066 // block-level that are block-level expressions. 3067 3068 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) { 3069 const CFGStmt *CS = BI->getAs<CFGStmt>(); 3070 if (!CS) 3071 continue; 3072 if (const Expr *Exp = dyn_cast<Expr>(CS->getStmt())) { 3073 assert((Exp->IgnoreParens() == Exp) && "No parens on block-level exps"); 3074 3075 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { 3076 // Assignment expressions that are not nested within another 3077 // expression are really "statements" whose value is never used by 3078 // another expression. 3079 if (B->isAssignmentOp() && !SubExprAssignments.count(Exp)) 3080 continue; 3081 } else if (const StmtExpr *SE = dyn_cast<StmtExpr>(Exp)) { 3082 // Special handling for statement expressions. The last statement in 3083 // the statement expression is also a block-level expr. 3084 const CompoundStmt *C = SE->getSubStmt(); 3085 if (!C->body_empty()) { 3086 const Stmt *Last = C->body_back(); 3087 if (const Expr *LastEx = dyn_cast<Expr>(Last)) 3088 Last = LastEx->IgnoreParens(); 3089 unsigned x = M->size(); 3090 (*M)[Last] = x; 3091 } 3092 } 3093 3094 unsigned x = M->size(); 3095 (*M)[Exp] = x; 3096 } 3097 } 3098 3099 // Look at terminators. The condition is a block-level expression. 3100 3101 Stmt *S = (*I)->getTerminatorCondition(); 3102 3103 if (S && M->find(S) == M->end()) { 3104 unsigned x = M->size(); 3105 (*M)[S] = x; 3106 } 3107 } 3108 3109 return M; 3110 } 3111 3112 CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt *S) { 3113 assert(S != NULL); 3114 if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); } 3115 3116 BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap); 3117 BlkExprMapTy::iterator I = M->find(S); 3118 return (I == M->end()) ? CFG::BlkExprNumTy() : CFG::BlkExprNumTy(I->second); 3119 } 3120 3121 unsigned CFG::getNumBlkExprs() { 3122 if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap)) 3123 return M->size(); 3124 3125 // We assume callers interested in the number of BlkExprs will want 3126 // the map constructed if it doesn't already exist. 3127 BlkExprMap = (void*) PopulateBlkExprMap(*this); 3128 return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); 3129 } 3130 3131 //===----------------------------------------------------------------------===// 3132 // Filtered walking of the CFG. 3133 //===----------------------------------------------------------------------===// 3134 3135 bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F, 3136 const CFGBlock *From, const CFGBlock *To) { 3137 3138 if (To && F.IgnoreDefaultsWithCoveredEnums) { 3139 // If the 'To' has no label or is labeled but the label isn't a 3140 // CaseStmt then filter this edge. 3141 if (const SwitchStmt *S = 3142 dyn_cast_or_null<SwitchStmt>(From->getTerminator().getStmt())) { 3143 if (S->isAllEnumCasesCovered()) { 3144 const Stmt *L = To->getLabel(); 3145 if (!L || !isa<CaseStmt>(L)) 3146 return true; 3147 } 3148 } 3149 } 3150 3151 return false; 3152 } 3153 3154 //===----------------------------------------------------------------------===// 3155 // Cleanup: CFG dstor. 3156 //===----------------------------------------------------------------------===// 3157 3158 CFG::~CFG() { 3159 delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap); 3160 } 3161 3162 //===----------------------------------------------------------------------===// 3163 // CFG pretty printing 3164 //===----------------------------------------------------------------------===// 3165 3166 namespace { 3167 3168 class StmtPrinterHelper : public PrinterHelper { 3169 typedef llvm::DenseMap<const Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; 3170 typedef llvm::DenseMap<const Decl*,std::pair<unsigned,unsigned> > DeclMapTy; 3171 StmtMapTy StmtMap; 3172 DeclMapTy DeclMap; 3173 signed currentBlock; 3174 unsigned currentStmt; 3175 const LangOptions &LangOpts; 3176 public: 3177 3178 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) 3179 : currentBlock(0), currentStmt(0), LangOpts(LO) 3180 { 3181 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { 3182 unsigned j = 1; 3183 for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ; 3184 BI != BEnd; ++BI, ++j ) { 3185 if (const CFGStmt *SE = BI->getAs<CFGStmt>()) { 3186 const Stmt *stmt= SE->getStmt(); 3187 std::pair<unsigned, unsigned> P((*I)->getBlockID(), j); 3188 StmtMap[stmt] = P; 3189 3190 switch (stmt->getStmtClass()) { 3191 case Stmt::DeclStmtClass: 3192 DeclMap[cast<DeclStmt>(stmt)->getSingleDecl()] = P; 3193 break; 3194 case Stmt::IfStmtClass: { 3195 const VarDecl *var = cast<IfStmt>(stmt)->getConditionVariable(); 3196 if (var) 3197 DeclMap[var] = P; 3198 break; 3199 } 3200 case Stmt::ForStmtClass: { 3201 const VarDecl *var = cast<ForStmt>(stmt)->getConditionVariable(); 3202 if (var) 3203 DeclMap[var] = P; 3204 break; 3205 } 3206 case Stmt::WhileStmtClass: { 3207 const VarDecl *var = 3208 cast<WhileStmt>(stmt)->getConditionVariable(); 3209 if (var) 3210 DeclMap[var] = P; 3211 break; 3212 } 3213 case Stmt::SwitchStmtClass: { 3214 const VarDecl *var = 3215 cast<SwitchStmt>(stmt)->getConditionVariable(); 3216 if (var) 3217 DeclMap[var] = P; 3218 break; 3219 } 3220 case Stmt::CXXCatchStmtClass: { 3221 const VarDecl *var = 3222 cast<CXXCatchStmt>(stmt)->getExceptionDecl(); 3223 if (var) 3224 DeclMap[var] = P; 3225 break; 3226 } 3227 default: 3228 break; 3229 } 3230 } 3231 } 3232 } 3233 } 3234 3235 3236 virtual ~StmtPrinterHelper() {} 3237 3238 const LangOptions &getLangOpts() const { return LangOpts; } 3239 void setBlockID(signed i) { currentBlock = i; } 3240 void setStmtID(unsigned i) { currentStmt = i; } 3241 3242 virtual bool handledStmt(Stmt *S, raw_ostream &OS) { 3243 StmtMapTy::iterator I = StmtMap.find(S); 3244 3245 if (I == StmtMap.end()) 3246 return false; 3247 3248 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock 3249 && I->second.second == currentStmt) { 3250 return false; 3251 } 3252 3253 OS << "[B" << I->second.first << "." << I->second.second << "]"; 3254 return true; 3255 } 3256 3257 bool handleDecl(const Decl *D, raw_ostream &OS) { 3258 DeclMapTy::iterator I = DeclMap.find(D); 3259 3260 if (I == DeclMap.end()) 3261 return false; 3262 3263 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock 3264 && I->second.second == currentStmt) { 3265 return false; 3266 } 3267 3268 OS << "[B" << I->second.first << "." << I->second.second << "]"; 3269 return true; 3270 } 3271 }; 3272 } // end anonymous namespace 3273 3274 3275 namespace { 3276 class CFGBlockTerminatorPrint 3277 : public StmtVisitor<CFGBlockTerminatorPrint,void> { 3278 3279 raw_ostream &OS; 3280 StmtPrinterHelper* Helper; 3281 PrintingPolicy Policy; 3282 public: 3283 CFGBlockTerminatorPrint(raw_ostream &os, StmtPrinterHelper* helper, 3284 const PrintingPolicy &Policy) 3285 : OS(os), Helper(helper), Policy(Policy) {} 3286 3287 void VisitIfStmt(IfStmt *I) { 3288 OS << "if "; 3289 I->getCond()->printPretty(OS,Helper,Policy); 3290 } 3291 3292 // Default case. 3293 void VisitStmt(Stmt *Terminator) { 3294 Terminator->printPretty(OS, Helper, Policy); 3295 } 3296 3297 void VisitForStmt(ForStmt *F) { 3298 OS << "for (" ; 3299 if (F->getInit()) 3300 OS << "..."; 3301 OS << "; "; 3302 if (Stmt *C = F->getCond()) 3303 C->printPretty(OS, Helper, Policy); 3304 OS << "; "; 3305 if (F->getInc()) 3306 OS << "..."; 3307 OS << ")"; 3308 } 3309 3310 void VisitWhileStmt(WhileStmt *W) { 3311 OS << "while " ; 3312 if (Stmt *C = W->getCond()) 3313 C->printPretty(OS, Helper, Policy); 3314 } 3315 3316 void VisitDoStmt(DoStmt *D) { 3317 OS << "do ... while "; 3318 if (Stmt *C = D->getCond()) 3319 C->printPretty(OS, Helper, Policy); 3320 } 3321 3322 void VisitSwitchStmt(SwitchStmt *Terminator) { 3323 OS << "switch "; 3324 Terminator->getCond()->printPretty(OS, Helper, Policy); 3325 } 3326 3327 void VisitCXXTryStmt(CXXTryStmt *CS) { 3328 OS << "try ..."; 3329 } 3330 3331 void VisitAbstractConditionalOperator(AbstractConditionalOperator* C) { 3332 C->getCond()->printPretty(OS, Helper, Policy); 3333 OS << " ? ... : ..."; 3334 } 3335 3336 void VisitChooseExpr(ChooseExpr *C) { 3337 OS << "__builtin_choose_expr( "; 3338 C->getCond()->printPretty(OS, Helper, Policy); 3339 OS << " )"; 3340 } 3341 3342 void VisitIndirectGotoStmt(IndirectGotoStmt *I) { 3343 OS << "goto *"; 3344 I->getTarget()->printPretty(OS, Helper, Policy); 3345 } 3346 3347 void VisitBinaryOperator(BinaryOperator* B) { 3348 if (!B->isLogicalOp()) { 3349 VisitExpr(B); 3350 return; 3351 } 3352 3353 B->getLHS()->printPretty(OS, Helper, Policy); 3354 3355 switch (B->getOpcode()) { 3356 case BO_LOr: 3357 OS << " || ..."; 3358 return; 3359 case BO_LAnd: 3360 OS << " && ..."; 3361 return; 3362 default: 3363 llvm_unreachable("Invalid logical operator."); 3364 } 3365 } 3366 3367 void VisitExpr(Expr *E) { 3368 E->printPretty(OS, Helper, Policy); 3369 } 3370 }; 3371 } // end anonymous namespace 3372 3373 static void print_elem(raw_ostream &OS, StmtPrinterHelper* Helper, 3374 const CFGElement &E) { 3375 if (const CFGStmt *CS = E.getAs<CFGStmt>()) { 3376 const Stmt *S = CS->getStmt(); 3377 3378 if (Helper) { 3379 3380 // special printing for statement-expressions. 3381 if (const StmtExpr *SE = dyn_cast<StmtExpr>(S)) { 3382 const CompoundStmt *Sub = SE->getSubStmt(); 3383 3384 if (Sub->children()) { 3385 OS << "({ ... ; "; 3386 Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); 3387 OS << " })\n"; 3388 return; 3389 } 3390 } 3391 // special printing for comma expressions. 3392 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { 3393 if (B->getOpcode() == BO_Comma) { 3394 OS << "... , "; 3395 Helper->handledStmt(B->getRHS(),OS); 3396 OS << '\n'; 3397 return; 3398 } 3399 } 3400 } 3401 S->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 3402 3403 if (isa<CXXOperatorCallExpr>(S)) { 3404 OS << " (OperatorCall)"; 3405 } else if (isa<CXXBindTemporaryExpr>(S)) { 3406 OS << " (BindTemporary)"; 3407 } 3408 3409 // Expressions need a newline. 3410 if (isa<Expr>(S)) 3411 OS << '\n'; 3412 3413 } else if (const CFGInitializer *IE = E.getAs<CFGInitializer>()) { 3414 const CXXCtorInitializer *I = IE->getInitializer(); 3415 if (I->isBaseInitializer()) 3416 OS << I->getBaseClass()->getAsCXXRecordDecl()->getName(); 3417 else OS << I->getAnyMember()->getName(); 3418 3419 OS << "("; 3420 if (Expr *IE = I->getInit()) 3421 IE->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 3422 OS << ")"; 3423 3424 if (I->isBaseInitializer()) 3425 OS << " (Base initializer)\n"; 3426 else OS << " (Member initializer)\n"; 3427 3428 } else if (const CFGAutomaticObjDtor *DE = E.getAs<CFGAutomaticObjDtor>()){ 3429 const VarDecl *VD = DE->getVarDecl(); 3430 Helper->handleDecl(VD, OS); 3431 3432 const Type* T = VD->getType().getTypePtr(); 3433 if (const ReferenceType* RT = T->getAs<ReferenceType>()) 3434 T = RT->getPointeeType().getTypePtr(); 3435 else if (const Type *ET = T->getArrayElementTypeNoTypeQual()) 3436 T = ET; 3437 3438 OS << ".~" << T->getAsCXXRecordDecl()->getName().str() << "()"; 3439 OS << " (Implicit destructor)\n"; 3440 3441 } else if (const CFGBaseDtor *BE = E.getAs<CFGBaseDtor>()) { 3442 const CXXBaseSpecifier *BS = BE->getBaseSpecifier(); 3443 OS << "~" << BS->getType()->getAsCXXRecordDecl()->getName() << "()"; 3444 OS << " (Base object destructor)\n"; 3445 3446 } else if (const CFGMemberDtor *ME = E.getAs<CFGMemberDtor>()) { 3447 const FieldDecl *FD = ME->getFieldDecl(); 3448 3449 const Type *T = FD->getType().getTypePtr(); 3450 if (const Type *ET = T->getArrayElementTypeNoTypeQual()) 3451 T = ET; 3452 3453 OS << "this->" << FD->getName(); 3454 OS << ".~" << T->getAsCXXRecordDecl()->getName() << "()"; 3455 OS << " (Member object destructor)\n"; 3456 3457 } else if (const CFGTemporaryDtor *TE = E.getAs<CFGTemporaryDtor>()) { 3458 const CXXBindTemporaryExpr *BT = TE->getBindTemporaryExpr(); 3459 OS << "~" << BT->getType()->getAsCXXRecordDecl()->getName() << "()"; 3460 OS << " (Temporary object destructor)\n"; 3461 } 3462 } 3463 3464 static void print_block(raw_ostream &OS, const CFG* cfg, 3465 const CFGBlock &B, 3466 StmtPrinterHelper* Helper, bool print_edges) { 3467 3468 if (Helper) Helper->setBlockID(B.getBlockID()); 3469 3470 // Print the header. 3471 OS << "\n [ B" << B.getBlockID(); 3472 3473 if (&B == &cfg->getEntry()) 3474 OS << " (ENTRY) ]\n"; 3475 else if (&B == &cfg->getExit()) 3476 OS << " (EXIT) ]\n"; 3477 else if (&B == cfg->getIndirectGotoBlock()) 3478 OS << " (INDIRECT GOTO DISPATCH) ]\n"; 3479 else 3480 OS << " ]\n"; 3481 3482 // Print the label of this block. 3483 if (Stmt *Label = const_cast<Stmt*>(B.getLabel())) { 3484 3485 if (print_edges) 3486 OS << " "; 3487 3488 if (LabelStmt *L = dyn_cast<LabelStmt>(Label)) 3489 OS << L->getName(); 3490 else if (CaseStmt *C = dyn_cast<CaseStmt>(Label)) { 3491 OS << "case "; 3492 C->getLHS()->printPretty(OS, Helper, 3493 PrintingPolicy(Helper->getLangOpts())); 3494 if (C->getRHS()) { 3495 OS << " ... "; 3496 C->getRHS()->printPretty(OS, Helper, 3497 PrintingPolicy(Helper->getLangOpts())); 3498 } 3499 } else if (isa<DefaultStmt>(Label)) 3500 OS << "default"; 3501 else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Label)) { 3502 OS << "catch ("; 3503 if (CS->getExceptionDecl()) 3504 CS->getExceptionDecl()->print(OS, PrintingPolicy(Helper->getLangOpts()), 3505 0); 3506 else 3507 OS << "..."; 3508 OS << ")"; 3509 3510 } else 3511 llvm_unreachable("Invalid label statement in CFGBlock."); 3512 3513 OS << ":\n"; 3514 } 3515 3516 // Iterate through the statements in the block and print them. 3517 unsigned j = 1; 3518 3519 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; 3520 I != E ; ++I, ++j ) { 3521 3522 // Print the statement # in the basic block and the statement itself. 3523 if (print_edges) 3524 OS << " "; 3525 3526 OS << llvm::format("%3d", j) << ": "; 3527 3528 if (Helper) 3529 Helper->setStmtID(j); 3530 3531 print_elem(OS,Helper,*I); 3532 } 3533 3534 // Print the terminator of this block. 3535 if (B.getTerminator()) { 3536 if (print_edges) 3537 OS << " "; 3538 3539 OS << " T: "; 3540 3541 if (Helper) Helper->setBlockID(-1); 3542 3543 CFGBlockTerminatorPrint TPrinter(OS, Helper, 3544 PrintingPolicy(Helper->getLangOpts())); 3545 TPrinter.Visit(const_cast<Stmt*>(B.getTerminator().getStmt())); 3546 OS << '\n'; 3547 } 3548 3549 if (print_edges) { 3550 // Print the predecessors of this block. 3551 OS << " Predecessors (" << B.pred_size() << "):"; 3552 unsigned i = 0; 3553 3554 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); 3555 I != E; ++I, ++i) { 3556 3557 if (i == 8 || (i-8) == 0) 3558 OS << "\n "; 3559 3560 OS << " B" << (*I)->getBlockID(); 3561 } 3562 3563 OS << '\n'; 3564 3565 // Print the successors of this block. 3566 OS << " Successors (" << B.succ_size() << "):"; 3567 i = 0; 3568 3569 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); 3570 I != E; ++I, ++i) { 3571 3572 if (i == 8 || (i-8) % 10 == 0) 3573 OS << "\n "; 3574 3575 if (*I) 3576 OS << " B" << (*I)->getBlockID(); 3577 else 3578 OS << " NULL"; 3579 } 3580 3581 OS << '\n'; 3582 } 3583 } 3584 3585 3586 /// dump - A simple pretty printer of a CFG that outputs to stderr. 3587 void CFG::dump(const LangOptions &LO) const { print(llvm::errs(), LO); } 3588 3589 /// print - A simple pretty printer of a CFG that outputs to an ostream. 3590 void CFG::print(raw_ostream &OS, const LangOptions &LO) const { 3591 StmtPrinterHelper Helper(this, LO); 3592 3593 // Print the entry block. 3594 print_block(OS, this, getEntry(), &Helper, true); 3595 3596 // Iterate through the CFGBlocks and print them one by one. 3597 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { 3598 // Skip the entry block, because we already printed it. 3599 if (&(**I) == &getEntry() || &(**I) == &getExit()) 3600 continue; 3601 3602 print_block(OS, this, **I, &Helper, true); 3603 } 3604 3605 // Print the exit block. 3606 print_block(OS, this, getExit(), &Helper, true); 3607 OS.flush(); 3608 } 3609 3610 /// dump - A simply pretty printer of a CFGBlock that outputs to stderr. 3611 void CFGBlock::dump(const CFG* cfg, const LangOptions &LO) const { 3612 print(llvm::errs(), cfg, LO); 3613 } 3614 3615 /// print - A simple pretty printer of a CFGBlock that outputs to an ostream. 3616 /// Generally this will only be called from CFG::print. 3617 void CFGBlock::print(raw_ostream &OS, const CFG* cfg, 3618 const LangOptions &LO) const { 3619 StmtPrinterHelper Helper(cfg, LO); 3620 print_block(OS, cfg, *this, &Helper, true); 3621 } 3622 3623 /// printTerminator - A simple pretty printer of the terminator of a CFGBlock. 3624 void CFGBlock::printTerminator(raw_ostream &OS, 3625 const LangOptions &LO) const { 3626 CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO)); 3627 TPrinter.Visit(const_cast<Stmt*>(getTerminator().getStmt())); 3628 } 3629 3630 Stmt *CFGBlock::getTerminatorCondition() { 3631 Stmt *Terminator = this->Terminator; 3632 if (!Terminator) 3633 return NULL; 3634 3635 Expr *E = NULL; 3636 3637 switch (Terminator->getStmtClass()) { 3638 default: 3639 break; 3640 3641 case Stmt::ForStmtClass: 3642 E = cast<ForStmt>(Terminator)->getCond(); 3643 break; 3644 3645 case Stmt::WhileStmtClass: 3646 E = cast<WhileStmt>(Terminator)->getCond(); 3647 break; 3648 3649 case Stmt::DoStmtClass: 3650 E = cast<DoStmt>(Terminator)->getCond(); 3651 break; 3652 3653 case Stmt::IfStmtClass: 3654 E = cast<IfStmt>(Terminator)->getCond(); 3655 break; 3656 3657 case Stmt::ChooseExprClass: 3658 E = cast<ChooseExpr>(Terminator)->getCond(); 3659 break; 3660 3661 case Stmt::IndirectGotoStmtClass: 3662 E = cast<IndirectGotoStmt>(Terminator)->getTarget(); 3663 break; 3664 3665 case Stmt::SwitchStmtClass: 3666 E = cast<SwitchStmt>(Terminator)->getCond(); 3667 break; 3668 3669 case Stmt::BinaryConditionalOperatorClass: 3670 E = cast<BinaryConditionalOperator>(Terminator)->getCond(); 3671 break; 3672 3673 case Stmt::ConditionalOperatorClass: 3674 E = cast<ConditionalOperator>(Terminator)->getCond(); 3675 break; 3676 3677 case Stmt::BinaryOperatorClass: // '&&' and '||' 3678 E = cast<BinaryOperator>(Terminator)->getLHS(); 3679 break; 3680 3681 case Stmt::ObjCForCollectionStmtClass: 3682 return Terminator; 3683 } 3684 3685 return E ? E->IgnoreParens() : NULL; 3686 } 3687 3688 //===----------------------------------------------------------------------===// 3689 // CFG Graphviz Visualization 3690 //===----------------------------------------------------------------------===// 3691 3692 3693 #ifndef NDEBUG 3694 static StmtPrinterHelper* GraphHelper; 3695 #endif 3696 3697 void CFG::viewCFG(const LangOptions &LO) const { 3698 #ifndef NDEBUG 3699 StmtPrinterHelper H(this, LO); 3700 GraphHelper = &H; 3701 llvm::ViewGraph(this,"CFG"); 3702 GraphHelper = NULL; 3703 #endif 3704 } 3705 3706 namespace llvm { 3707 template<> 3708 struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { 3709 3710 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 3711 3712 static std::string getNodeLabel(const CFGBlock *Node, const CFG* Graph) { 3713 3714 #ifndef NDEBUG 3715 std::string OutSStr; 3716 llvm::raw_string_ostream Out(OutSStr); 3717 print_block(Out,Graph, *Node, GraphHelper, false); 3718 std::string& OutStr = Out.str(); 3719 3720 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); 3721 3722 // Process string output to make it nicer... 3723 for (unsigned i = 0; i != OutStr.length(); ++i) 3724 if (OutStr[i] == '\n') { // Left justify 3725 OutStr[i] = '\\'; 3726 OutStr.insert(OutStr.begin()+i+1, 'l'); 3727 } 3728 3729 return OutStr; 3730 #else 3731 return ""; 3732 #endif 3733 } 3734 }; 3735 } // end namespace llvm 3736