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