CFG.cpp revision abed169e087de5424b36d71838e1b2c3b1d3d0f8
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 "llvm/Support/GraphWriter.h" 21#include "llvm/Support/Allocator.h" 22#include "llvm/Support/Format.h" 23#include "llvm/ADT/DenseMap.h" 24#include "llvm/ADT/SmallPtrSet.h" 25#include "llvm/ADT/OwningPtr.h" 26 27using namespace clang; 28 29namespace { 30 31static SourceLocation GetEndLoc(Decl* D) { 32 if (VarDecl* VD = dyn_cast<VarDecl>(D)) 33 if (Expr* Ex = VD->getInit()) 34 return Ex->getSourceRange().getEnd(); 35 36 return D->getLocation(); 37} 38 39class AddStmtChoice { 40public: 41 enum Kind { NotAlwaysAdd = 0, 42 AlwaysAdd = 1, 43 AsLValueNotAlwaysAdd = 2, 44 AlwaysAddAsLValue = 3 }; 45 46 AddStmtChoice(Kind kind) : k(kind) {} 47 48 bool alwaysAdd() const { return (unsigned)k & 0x1; } 49 bool asLValue() const { return k >= AsLValueNotAlwaysAdd; } 50 51private: 52 Kind k; 53}; 54 55/// LocalScope - Node in tree of local scopes created for C++ implicit 56/// destructor calls generation. It contains list of automatic variables 57/// declared in the scope and link to position in previous scope this scope 58/// began in. 59/// 60/// The process of creating local scopes is as follows: 61/// - Init CFGBuilder::ScopePos with invalid position (equivalent for null), 62/// - Before processing statements in scope (e.g. CompoundStmt) create 63/// LocalScope object using CFGBuilder::ScopePos as link to previous scope 64/// and set CFGBuilder::ScopePos to the end of new scope, 65/// - On every occurrence of VarDecl increase CFGBuilder::ScopePos if it points 66/// at this VarDecl, 67/// - For every normal (without jump) end of scope add to CFGBlock destructors 68/// for objects in the current scope, 69/// - For every jump add to CFGBlock destructors for objects 70/// between CFGBuilder::ScopePos and local scope position saved for jump 71/// target. Thanks to C++ restrictions on goto jumps we can be sure that 72/// jump target position will be on the path to root from CFGBuilder::ScopePos 73/// (adding any variable that doesn't need constructor to be called to 74/// LocalScope can break this assumption), 75/// 76class LocalScope { 77public: 78 typedef llvm::SmallVector<VarDecl*, 4> AutomaticVarsTy; 79 80 /// const_iterator - Iterates local scope backwards and jumps to previous 81 /// scope on reaching the beginning of currently iterated scope. 82 class const_iterator { 83 const LocalScope* Scope; 84 85 /// VarIter is guaranteed to be greater then 0 for every valid iterator. 86 /// Invalid iterator (with null Scope) has VarIter equal to 0. 87 unsigned VarIter; 88 89 public: 90 /// Create invalid iterator. Dereferencing invalid iterator is not allowed. 91 /// Incrementing invalid iterator is allowed and will result in invalid 92 /// iterator. 93 const_iterator() 94 : Scope(NULL), VarIter(0) {} 95 96 /// Create valid iterator. In case when S.Prev is an invalid iterator and 97 /// I is equal to 0, this will create invalid iterator. 98 const_iterator(const LocalScope& S, unsigned I) 99 : Scope(&S), VarIter(I) { 100 // Iterator to "end" of scope is not allowed. Handle it by going up 101 // in scopes tree possibly up to invalid iterator in the root. 102 if (VarIter == 0 && Scope) 103 *this = Scope->Prev; 104 } 105 106 VarDecl* const* operator->() const { 107 assert (Scope && "Dereferencing invalid iterator is not allowed"); 108 assert (VarIter != 0 && "Iterator has invalid value of VarIter member"); 109 return &Scope->Vars[VarIter - 1]; 110 } 111 VarDecl* operator*() const { 112 return *this->operator->(); 113 } 114 115 const_iterator& operator++() { 116 if (!Scope) 117 return *this; 118 119 assert (VarIter != 0 && "Iterator has invalid value of VarIter member"); 120 --VarIter; 121 if (VarIter == 0) 122 *this = Scope->Prev; 123 return *this; 124 } 125 const_iterator operator++(int) { 126 const_iterator P = *this; 127 ++*this; 128 return P; 129 } 130 131 bool operator==(const const_iterator& rhs) const { 132 return Scope == rhs.Scope && VarIter == rhs.VarIter; 133 } 134 bool operator!=(const const_iterator& rhs) const { 135 return !(*this == rhs); 136 } 137 138 operator bool() const { 139 return *this != const_iterator(); 140 } 141 142 int distance(const_iterator L); 143 }; 144 145 friend class const_iterator; 146 147private: 148 /// Automatic variables in order of declaration. 149 AutomaticVarsTy Vars; 150 /// Iterator to variable in previous scope that was declared just before 151 /// begin of this scope. 152 const_iterator Prev; 153 154public: 155 /// Constructs empty scope linked to previous scope in specified place. 156 LocalScope(const_iterator P) 157 : Vars() 158 , Prev(P) {} 159 160 /// Begin of scope in direction of CFG building (backwards). 161 const_iterator begin() const { return const_iterator(*this, Vars.size()); } 162 163 void addVar(VarDecl* VD) { 164 Vars.push_back(VD); 165 } 166}; 167 168/// distance - Calculates distance from this to L. L must be reachable from this 169/// (with use of ++ operator). Cost of calculating the distance is linear w.r.t. 170/// number of scopes between this and L. 171int LocalScope::const_iterator::distance(LocalScope::const_iterator L) { 172 int D = 0; 173 const_iterator F = *this; 174 while (F.Scope != L.Scope) { 175 assert (F != const_iterator() 176 && "L iterator is not reachable from F iterator."); 177 D += F.VarIter; 178 F = F.Scope->Prev; 179 } 180 D += F.VarIter - L.VarIter; 181 return D; 182} 183 184/// BlockScopePosPair - Structure for specifying position in CFG during its 185/// build process. It consists of CFGBlock that specifies position in CFG graph 186/// and LocalScope::const_iterator that specifies position in LocalScope graph. 187struct BlockScopePosPair { 188 BlockScopePosPair() {} 189 BlockScopePosPair(CFGBlock* B, LocalScope::const_iterator S) 190 : Block(B), ScopePos(S) {} 191 192 CFGBlock* Block; 193 LocalScope::const_iterator ScopePos; 194}; 195 196/// CFGBuilder - This class implements CFG construction from an AST. 197/// The builder is stateful: an instance of the builder should be used to only 198/// construct a single CFG. 199/// 200/// Example usage: 201/// 202/// CFGBuilder builder; 203/// CFG* cfg = builder.BuildAST(stmt1); 204/// 205/// CFG construction is done via a recursive walk of an AST. We actually parse 206/// the AST in reverse order so that the successor of a basic block is 207/// constructed prior to its predecessor. This allows us to nicely capture 208/// implicit fall-throughs without extra basic blocks. 209/// 210class CFGBuilder { 211 typedef BlockScopePosPair JumpTarget; 212 typedef BlockScopePosPair JumpSource; 213 214 ASTContext *Context; 215 llvm::OwningPtr<CFG> cfg; 216 217 CFGBlock* Block; 218 CFGBlock* Succ; 219 JumpTarget ContinueJumpTarget; 220 JumpTarget BreakJumpTarget; 221 CFGBlock* SwitchTerminatedBlock; 222 CFGBlock* DefaultCaseBlock; 223 CFGBlock* TryTerminatedBlock; 224 225 // Current position in local scope. 226 LocalScope::const_iterator ScopePos; 227 228 // LabelMap records the mapping from Label expressions to their jump targets. 229 typedef llvm::DenseMap<LabelStmt*, JumpTarget> LabelMapTy; 230 LabelMapTy LabelMap; 231 232 // A list of blocks that end with a "goto" that must be backpatched to their 233 // resolved targets upon completion of CFG construction. 234 typedef std::vector<JumpSource> BackpatchBlocksTy; 235 BackpatchBlocksTy BackpatchBlocks; 236 237 // A list of labels whose address has been taken (for indirect gotos). 238 typedef llvm::SmallPtrSet<LabelStmt*,5> LabelSetTy; 239 LabelSetTy AddressTakenLabels; 240 241 bool badCFG; 242 CFG::BuildOptions BuildOpts; 243 244public: 245 explicit CFGBuilder() : cfg(new CFG()), // crew a new CFG 246 Block(NULL), Succ(NULL), 247 SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL), 248 TryTerminatedBlock(NULL), badCFG(false) {} 249 250 // buildCFG - Used by external clients to construct the CFG. 251 CFG* buildCFG(const Decl *D, Stmt *Statement, ASTContext *C, 252 CFG::BuildOptions BO); 253 254private: 255 // Visitors to walk an AST and construct the CFG. 256 CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc); 257 CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc); 258 CFGBlock *VisitBlockExpr(BlockExpr* E, AddStmtChoice asc); 259 CFGBlock *VisitBreakStmt(BreakStmt *B); 260 CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S); 261 CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T); 262 CFGBlock *VisitCXXTryStmt(CXXTryStmt *S); 263 CFGBlock *VisitCXXMemberCallExpr(CXXMemberCallExpr *C, AddStmtChoice asc); 264 CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc); 265 CFGBlock *VisitCaseStmt(CaseStmt *C); 266 CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc); 267 CFGBlock *VisitCompoundStmt(CompoundStmt *C); 268 CFGBlock *VisitConditionalOperator(ConditionalOperator *C, AddStmtChoice asc); 269 CFGBlock *VisitContinueStmt(ContinueStmt *C); 270 CFGBlock *VisitDeclStmt(DeclStmt *DS); 271 CFGBlock *VisitDeclSubExpr(Decl* D); 272 CFGBlock *VisitDefaultStmt(DefaultStmt *D); 273 CFGBlock *VisitDoStmt(DoStmt *D); 274 CFGBlock *VisitForStmt(ForStmt *F); 275 CFGBlock *VisitGotoStmt(GotoStmt* G); 276 CFGBlock *VisitIfStmt(IfStmt *I); 277 CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I); 278 CFGBlock *VisitLabelStmt(LabelStmt *L); 279 CFGBlock *VisitMemberExpr(MemberExpr *M, AddStmtChoice asc); 280 CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S); 281 CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S); 282 CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S); 283 CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S); 284 CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S); 285 CFGBlock *VisitReturnStmt(ReturnStmt* R); 286 CFGBlock *VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, AddStmtChoice asc); 287 CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc); 288 CFGBlock *VisitSwitchStmt(SwitchStmt *S); 289 CFGBlock *VisitWhileStmt(WhileStmt *W); 290 291 CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd); 292 CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc); 293 CFGBlock *VisitChildren(Stmt* S); 294 295 // NYS == Not Yet Supported 296 CFGBlock* NYS() { 297 badCFG = true; 298 return Block; 299 } 300 301 void autoCreateBlock() { if (!Block) Block = createBlock(); } 302 CFGBlock *createBlock(bool add_successor = true); 303 304 CFGBlock *addStmt(Stmt *S) { 305 return Visit(S, AddStmtChoice::AlwaysAdd); 306 } 307 308 void AppendStmt(CFGBlock *B, Stmt *S, 309 AddStmtChoice asc = AddStmtChoice::AlwaysAdd) { 310 B->appendStmt(S, cfg->getBumpVectorContext(), asc.asLValue()); 311 } 312 313 void AddSuccessor(CFGBlock *B, CFGBlock *S) { 314 B->addSuccessor(S, cfg->getBumpVectorContext()); 315 } 316 317 /// TryResult - a class representing a variant over the values 318 /// 'true', 'false', or 'unknown'. This is returned by TryEvaluateBool, 319 /// and is used by the CFGBuilder to decide if a branch condition 320 /// can be decided up front during CFG construction. 321 class TryResult { 322 int X; 323 public: 324 TryResult(bool b) : X(b ? 1 : 0) {} 325 TryResult() : X(-1) {} 326 327 bool isTrue() const { return X == 1; } 328 bool isFalse() const { return X == 0; } 329 bool isKnown() const { return X >= 0; } 330 void negate() { 331 assert(isKnown()); 332 X ^= 0x1; 333 } 334 }; 335 336 /// TryEvaluateBool - Try and evaluate the Stmt and return 0 or 1 337 /// if we can evaluate to a known value, otherwise return -1. 338 TryResult TryEvaluateBool(Expr *S) { 339 if (!BuildOpts.PruneTriviallyFalseEdges) 340 return TryResult(); 341 342 Expr::EvalResult Result; 343 if (!S->isTypeDependent() && !S->isValueDependent() && 344 S->Evaluate(Result, *Context) && Result.Val.isInt()) 345 return Result.Val.getInt().getBoolValue(); 346 347 return TryResult(); 348 } 349}; 350 351// FIXME: Add support for dependent-sized array types in C++? 352// Does it even make sense to build a CFG for an uninstantiated template? 353static VariableArrayType* FindVA(Type* t) { 354 while (ArrayType* vt = dyn_cast<ArrayType>(t)) { 355 if (VariableArrayType* vat = dyn_cast<VariableArrayType>(vt)) 356 if (vat->getSizeExpr()) 357 return vat; 358 359 t = vt->getElementType().getTypePtr(); 360 } 361 362 return 0; 363} 364 365/// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an 366/// arbitrary statement. Examples include a single expression or a function 367/// body (compound statement). The ownership of the returned CFG is 368/// transferred to the caller. If CFG construction fails, this method returns 369/// NULL. 370CFG* CFGBuilder::buildCFG(const Decl *D, Stmt* Statement, ASTContext* C, 371 CFG::BuildOptions BO) { 372 373 Context = C; 374 assert(cfg.get()); 375 if (!Statement) 376 return NULL; 377 378 BuildOpts = BO; 379 if (!C->getLangOptions().CPlusPlus) 380 BuildOpts.AddImplicitDtors = false; 381 382 // Create an empty block that will serve as the exit block for the CFG. Since 383 // this is the first block added to the CFG, it will be implicitly registered 384 // as the exit block. 385 Succ = createBlock(); 386 assert(Succ == &cfg->getExit()); 387 Block = NULL; // the EXIT block is empty. Create all other blocks lazily. 388 389 // Visit the statements and create the CFG. 390 CFGBlock *B = addStmt(Statement); 391 392 if (badCFG) 393 return NULL; 394 395 if (B) 396 Succ = B; 397 398 if (const CXXConstructorDecl *CD = dyn_cast_or_null<CXXConstructorDecl>(D)) { 399 // FIXME: Add code for base initializers and member initializers. 400 (void)CD; 401 } 402 403 // Backpatch the gotos whose label -> block mappings we didn't know when we 404 // encountered them. 405 for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(), 406 E = BackpatchBlocks.end(); I != E; ++I ) { 407 408 CFGBlock* B = I->Block; 409 GotoStmt* G = cast<GotoStmt>(B->getTerminator()); 410 LabelMapTy::iterator LI = LabelMap.find(G->getLabel()); 411 412 // If there is no target for the goto, then we are looking at an 413 // incomplete AST. Handle this by not registering a successor. 414 if (LI == LabelMap.end()) continue; 415 416 JumpTarget JT = LI->second; 417 AddSuccessor(B, JT.Block); 418 } 419 420 // Add successors to the Indirect Goto Dispatch block (if we have one). 421 if (CFGBlock* B = cfg->getIndirectGotoBlock()) 422 for (LabelSetTy::iterator I = AddressTakenLabels.begin(), 423 E = AddressTakenLabels.end(); I != E; ++I ) { 424 425 // Lookup the target block. 426 LabelMapTy::iterator LI = LabelMap.find(*I); 427 428 // If there is no target block that contains label, then we are looking 429 // at an incomplete AST. Handle this by not registering a successor. 430 if (LI == LabelMap.end()) continue; 431 432 AddSuccessor(B, LI->second.Block); 433 } 434 435 // Create an empty entry block that has no predecessors. 436 cfg->setEntry(createBlock()); 437 438 return cfg.take(); 439} 440 441/// createBlock - Used to lazily create blocks that are connected 442/// to the current (global) succcessor. 443CFGBlock* CFGBuilder::createBlock(bool add_successor) { 444 CFGBlock* B = cfg->createBlock(); 445 if (add_successor && Succ) 446 AddSuccessor(B, Succ); 447 return B; 448} 449 450/// Visit - Walk the subtree of a statement and add extra 451/// blocks for ternary operators, &&, and ||. We also process "," and 452/// DeclStmts (which may contain nested control-flow). 453CFGBlock* CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) { 454tryAgain: 455 if (!S) { 456 badCFG = true; 457 return 0; 458 } 459 switch (S->getStmtClass()) { 460 default: 461 return VisitStmt(S, asc); 462 463 case Stmt::AddrLabelExprClass: 464 return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc); 465 466 case Stmt::BinaryOperatorClass: 467 return VisitBinaryOperator(cast<BinaryOperator>(S), asc); 468 469 case Stmt::BlockExprClass: 470 return VisitBlockExpr(cast<BlockExpr>(S), asc); 471 472 case Stmt::BreakStmtClass: 473 return VisitBreakStmt(cast<BreakStmt>(S)); 474 475 case Stmt::CallExprClass: 476 case Stmt::CXXOperatorCallExprClass: 477 return VisitCallExpr(cast<CallExpr>(S), asc); 478 479 case Stmt::CaseStmtClass: 480 return VisitCaseStmt(cast<CaseStmt>(S)); 481 482 case Stmt::ChooseExprClass: 483 return VisitChooseExpr(cast<ChooseExpr>(S), asc); 484 485 case Stmt::CompoundStmtClass: 486 return VisitCompoundStmt(cast<CompoundStmt>(S)); 487 488 case Stmt::ConditionalOperatorClass: 489 return VisitConditionalOperator(cast<ConditionalOperator>(S), asc); 490 491 case Stmt::ContinueStmtClass: 492 return VisitContinueStmt(cast<ContinueStmt>(S)); 493 494 case Stmt::CXXCatchStmtClass: 495 return VisitCXXCatchStmt(cast<CXXCatchStmt>(S)); 496 497 case Stmt::CXXExprWithTemporariesClass: { 498 // FIXME: Handle temporaries. For now, just visit the subexpression 499 // so we don't artificially create extra blocks. 500 return Visit(cast<CXXExprWithTemporaries>(S)->getSubExpr(), asc); 501 } 502 503 case Stmt::CXXMemberCallExprClass: 504 return VisitCXXMemberCallExpr(cast<CXXMemberCallExpr>(S), asc); 505 506 case Stmt::CXXThrowExprClass: 507 return VisitCXXThrowExpr(cast<CXXThrowExpr>(S)); 508 509 case Stmt::CXXTryStmtClass: 510 return VisitCXXTryStmt(cast<CXXTryStmt>(S)); 511 512 case Stmt::DeclStmtClass: 513 return VisitDeclStmt(cast<DeclStmt>(S)); 514 515 case Stmt::DefaultStmtClass: 516 return VisitDefaultStmt(cast<DefaultStmt>(S)); 517 518 case Stmt::DoStmtClass: 519 return VisitDoStmt(cast<DoStmt>(S)); 520 521 case Stmt::ForStmtClass: 522 return VisitForStmt(cast<ForStmt>(S)); 523 524 case Stmt::GotoStmtClass: 525 return VisitGotoStmt(cast<GotoStmt>(S)); 526 527 case Stmt::IfStmtClass: 528 return VisitIfStmt(cast<IfStmt>(S)); 529 530 case Stmt::IndirectGotoStmtClass: 531 return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S)); 532 533 case Stmt::LabelStmtClass: 534 return VisitLabelStmt(cast<LabelStmt>(S)); 535 536 case Stmt::MemberExprClass: 537 return VisitMemberExpr(cast<MemberExpr>(S), asc); 538 539 case Stmt::ObjCAtCatchStmtClass: 540 return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S)); 541 542 case Stmt::ObjCAtSynchronizedStmtClass: 543 return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S)); 544 545 case Stmt::ObjCAtThrowStmtClass: 546 return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S)); 547 548 case Stmt::ObjCAtTryStmtClass: 549 return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S)); 550 551 case Stmt::ObjCForCollectionStmtClass: 552 return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S)); 553 554 case Stmt::ParenExprClass: 555 S = cast<ParenExpr>(S)->getSubExpr(); 556 goto tryAgain; 557 558 case Stmt::NullStmtClass: 559 return Block; 560 561 case Stmt::ReturnStmtClass: 562 return VisitReturnStmt(cast<ReturnStmt>(S)); 563 564 case Stmt::SizeOfAlignOfExprClass: 565 return VisitSizeOfAlignOfExpr(cast<SizeOfAlignOfExpr>(S), asc); 566 567 case Stmt::StmtExprClass: 568 return VisitStmtExpr(cast<StmtExpr>(S), asc); 569 570 case Stmt::SwitchStmtClass: 571 return VisitSwitchStmt(cast<SwitchStmt>(S)); 572 573 case Stmt::WhileStmtClass: 574 return VisitWhileStmt(cast<WhileStmt>(S)); 575 } 576} 577 578CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) { 579 if (asc.alwaysAdd()) { 580 autoCreateBlock(); 581 AppendStmt(Block, S, asc); 582 } 583 584 return VisitChildren(S); 585} 586 587/// VisitChildren - Visit the children of a Stmt. 588CFGBlock *CFGBuilder::VisitChildren(Stmt* Terminator) { 589 CFGBlock *B = Block; 590 for (Stmt::child_iterator I = Terminator->child_begin(), 591 E = Terminator->child_end(); I != E; ++I) { 592 if (*I) B = Visit(*I); 593 } 594 return B; 595} 596 597CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A, 598 AddStmtChoice asc) { 599 AddressTakenLabels.insert(A->getLabel()); 600 601 if (asc.alwaysAdd()) { 602 autoCreateBlock(); 603 AppendStmt(Block, A, asc); 604 } 605 606 return Block; 607} 608 609CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, 610 AddStmtChoice asc) { 611 if (B->isLogicalOp()) { // && or || 612 CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 613 AppendStmt(ConfluenceBlock, B, asc); 614 615 if (badCFG) 616 return 0; 617 618 // create the block evaluating the LHS 619 CFGBlock* LHSBlock = createBlock(false); 620 LHSBlock->setTerminator(B); 621 622 // create the block evaluating the RHS 623 Succ = ConfluenceBlock; 624 Block = NULL; 625 CFGBlock* RHSBlock = addStmt(B->getRHS()); 626 627 if (RHSBlock) { 628 if (badCFG) 629 return 0; 630 } 631 else { 632 // Create an empty block for cases where the RHS doesn't require 633 // any explicit statements in the CFG. 634 RHSBlock = createBlock(); 635 } 636 637 // See if this is a known constant. 638 TryResult KnownVal = TryEvaluateBool(B->getLHS()); 639 if (KnownVal.isKnown() && (B->getOpcode() == BO_LOr)) 640 KnownVal.negate(); 641 642 // Now link the LHSBlock with RHSBlock. 643 if (B->getOpcode() == BO_LOr) { 644 AddSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); 645 AddSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); 646 } else { 647 assert(B->getOpcode() == BO_LAnd); 648 AddSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); 649 AddSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); 650 } 651 652 // Generate the blocks for evaluating the LHS. 653 Block = LHSBlock; 654 return addStmt(B->getLHS()); 655 } 656 else if (B->getOpcode() == BO_Comma) { // , 657 autoCreateBlock(); 658 AppendStmt(Block, B, asc); 659 addStmt(B->getRHS()); 660 return addStmt(B->getLHS()); 661 } 662 else if (B->isAssignmentOp()) { 663 if (asc.alwaysAdd()) { 664 autoCreateBlock(); 665 AppendStmt(Block, B, asc); 666 } 667 668 // If visiting RHS causes us to finish 'Block' and the LHS doesn't 669 // create a new block, then we should return RBlock. Otherwise 670 // we'll incorrectly return NULL. 671 CFGBlock *RBlock = Visit(B->getRHS()); 672 CFGBlock *LBlock = Visit(B->getLHS(), AddStmtChoice::AsLValueNotAlwaysAdd); 673 return LBlock ? LBlock : RBlock; 674 } 675 676 return VisitStmt(B, asc); 677} 678 679CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) { 680 if (asc.alwaysAdd()) { 681 autoCreateBlock(); 682 AppendStmt(Block, E, asc); 683 } 684 return Block; 685} 686 687CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) { 688 // "break" is a control-flow statement. Thus we stop processing the current 689 // block. 690 if (badCFG) 691 return 0; 692 693 // Now create a new block that ends with the break statement. 694 Block = createBlock(false); 695 Block->setTerminator(B); 696 697 // If there is no target for the break, then we are looking at an incomplete 698 // AST. This means that the CFG cannot be constructed. 699 if (BreakJumpTarget.Block) { 700 AddSuccessor(Block, BreakJumpTarget.Block); 701 } else 702 badCFG = true; 703 704 705 return Block; 706} 707 708static bool CanThrow(Expr *E) { 709 QualType Ty = E->getType(); 710 if (Ty->isFunctionPointerType()) 711 Ty = Ty->getAs<PointerType>()->getPointeeType(); 712 else if (Ty->isBlockPointerType()) 713 Ty = Ty->getAs<BlockPointerType>()->getPointeeType(); 714 715 const FunctionType *FT = Ty->getAs<FunctionType>(); 716 if (FT) { 717 if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT)) 718 if (Proto->hasEmptyExceptionSpec()) 719 return false; 720 } 721 return true; 722} 723 724CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { 725 // If this is a call to a no-return function, this stops the block here. 726 bool NoReturn = false; 727 if (getFunctionExtInfo(*C->getCallee()->getType()).getNoReturn()) { 728 NoReturn = true; 729 } 730 731 bool AddEHEdge = false; 732 733 // Languages without exceptions are assumed to not throw. 734 if (Context->getLangOptions().Exceptions) { 735 if (BuildOpts.AddEHEdges) 736 AddEHEdge = true; 737 } 738 739 if (FunctionDecl *FD = C->getDirectCallee()) { 740 if (FD->hasAttr<NoReturnAttr>()) 741 NoReturn = true; 742 if (FD->hasAttr<NoThrowAttr>()) 743 AddEHEdge = false; 744 } 745 746 if (!CanThrow(C->getCallee())) 747 AddEHEdge = false; 748 749 if (!NoReturn && !AddEHEdge) { 750 if (asc.asLValue()) 751 return VisitStmt(C, AddStmtChoice::AlwaysAddAsLValue); 752 else 753 return VisitStmt(C, AddStmtChoice::AlwaysAdd); 754 } 755 756 if (Block) { 757 Succ = Block; 758 if (badCFG) 759 return 0; 760 } 761 762 Block = createBlock(!NoReturn); 763 AppendStmt(Block, C, asc); 764 765 if (NoReturn) { 766 // Wire this to the exit block directly. 767 AddSuccessor(Block, &cfg->getExit()); 768 } 769 if (AddEHEdge) { 770 // Add exceptional edges. 771 if (TryTerminatedBlock) 772 AddSuccessor(Block, TryTerminatedBlock); 773 else 774 AddSuccessor(Block, &cfg->getExit()); 775 } 776 777 return VisitChildren(C); 778} 779 780CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C, 781 AddStmtChoice asc) { 782 CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 783 AppendStmt(ConfluenceBlock, C, asc); 784 if (badCFG) 785 return 0; 786 787 asc = asc.asLValue() ? AddStmtChoice::AlwaysAddAsLValue 788 : AddStmtChoice::AlwaysAdd; 789 790 Succ = ConfluenceBlock; 791 Block = NULL; 792 CFGBlock* LHSBlock = Visit(C->getLHS(), asc); 793 if (badCFG) 794 return 0; 795 796 Succ = ConfluenceBlock; 797 Block = NULL; 798 CFGBlock* RHSBlock = Visit(C->getRHS(), asc); 799 if (badCFG) 800 return 0; 801 802 Block = createBlock(false); 803 // See if this is a known constant. 804 const TryResult& KnownVal = TryEvaluateBool(C->getCond()); 805 AddSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); 806 AddSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); 807 Block->setTerminator(C); 808 return addStmt(C->getCond()); 809} 810 811 812CFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) { 813 CFGBlock* LastBlock = Block; 814 815 for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); 816 I != E; ++I ) { 817 // If we hit a segment of code just containing ';' (NullStmts), we can 818 // get a null block back. In such cases, just use the LastBlock 819 if (CFGBlock *newBlock = addStmt(*I)) 820 LastBlock = newBlock; 821 822 if (badCFG) 823 return NULL; 824 } 825 826 return LastBlock; 827} 828 829CFGBlock *CFGBuilder::VisitConditionalOperator(ConditionalOperator *C, 830 AddStmtChoice asc) { 831 // Create the confluence block that will "merge" the results of the ternary 832 // expression. 833 CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 834 AppendStmt(ConfluenceBlock, C, asc); 835 if (badCFG) 836 return 0; 837 838 asc = asc.asLValue() ? AddStmtChoice::AlwaysAddAsLValue 839 : AddStmtChoice::AlwaysAdd; 840 841 // Create a block for the LHS expression if there is an LHS expression. A 842 // GCC extension allows LHS to be NULL, causing the condition to be the 843 // value that is returned instead. 844 // e.g: x ?: y is shorthand for: x ? x : y; 845 Succ = ConfluenceBlock; 846 Block = NULL; 847 CFGBlock* LHSBlock = NULL; 848 if (C->getLHS()) { 849 LHSBlock = Visit(C->getLHS(), asc); 850 if (badCFG) 851 return 0; 852 Block = NULL; 853 } 854 855 // Create the block for the RHS expression. 856 Succ = ConfluenceBlock; 857 CFGBlock* RHSBlock = Visit(C->getRHS(), asc); 858 if (badCFG) 859 return 0; 860 861 // Create the block that will contain the condition. 862 Block = createBlock(false); 863 864 // See if this is a known constant. 865 const TryResult& KnownVal = TryEvaluateBool(C->getCond()); 866 if (LHSBlock) { 867 AddSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); 868 } else { 869 if (KnownVal.isFalse()) { 870 // If we know the condition is false, add NULL as the successor for 871 // the block containing the condition. In this case, the confluence 872 // block will have just one predecessor. 873 AddSuccessor(Block, 0); 874 assert(ConfluenceBlock->pred_size() == 1); 875 } else { 876 // If we have no LHS expression, add the ConfluenceBlock as a direct 877 // successor for the block containing the condition. Moreover, we need to 878 // reverse the order of the predecessors in the ConfluenceBlock because 879 // the RHSBlock will have been added to the succcessors already, and we 880 // want the first predecessor to the the block containing the expression 881 // for the case when the ternary expression evaluates to true. 882 AddSuccessor(Block, ConfluenceBlock); 883 assert(ConfluenceBlock->pred_size() == 2); 884 std::reverse(ConfluenceBlock->pred_begin(), 885 ConfluenceBlock->pred_end()); 886 } 887 } 888 889 AddSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); 890 Block->setTerminator(C); 891 return addStmt(C->getCond()); 892} 893 894CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) { 895 autoCreateBlock(); 896 897 if (DS->isSingleDecl()) { 898 AppendStmt(Block, DS); 899 return VisitDeclSubExpr(DS->getSingleDecl()); 900 } 901 902 CFGBlock *B = 0; 903 904 // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy. 905 typedef llvm::SmallVector<Decl*,10> BufTy; 906 BufTy Buf(DS->decl_begin(), DS->decl_end()); 907 908 for (BufTy::reverse_iterator I = Buf.rbegin(), E = Buf.rend(); I != E; ++I) { 909 // Get the alignment of the new DeclStmt, padding out to >=8 bytes. 910 unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8 911 ? 8 : llvm::AlignOf<DeclStmt>::Alignment; 912 913 // Allocate the DeclStmt using the BumpPtrAllocator. It will get 914 // automatically freed with the CFG. 915 DeclGroupRef DG(*I); 916 Decl *D = *I; 917 void *Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A); 918 DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D)); 919 920 // Append the fake DeclStmt to block. 921 AppendStmt(Block, DSNew); 922 B = VisitDeclSubExpr(D); 923 } 924 925 return B; 926} 927 928/// VisitDeclSubExpr - Utility method to add block-level expressions for 929/// initializers in Decls. 930CFGBlock *CFGBuilder::VisitDeclSubExpr(Decl* D) { 931 assert(Block); 932 933 VarDecl *VD = dyn_cast<VarDecl>(D); 934 935 if (!VD) 936 return Block; 937 938 Expr *Init = VD->getInit(); 939 940 if (Init) { 941 AddStmtChoice::Kind k = 942 VD->getType()->isReferenceType() ? AddStmtChoice::AsLValueNotAlwaysAdd 943 : AddStmtChoice::NotAlwaysAdd; 944 Visit(Init, AddStmtChoice(k)); 945 } 946 947 // If the type of VD is a VLA, then we must process its size expressions. 948 for (VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); VA != 0; 949 VA = FindVA(VA->getElementType().getTypePtr())) 950 Block = addStmt(VA->getSizeExpr()); 951 952 return Block; 953} 954 955CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { 956 // We may see an if statement in the middle of a basic block, or it may be the 957 // first statement we are processing. In either case, we create a new basic 958 // block. First, we create the blocks for the then...else statements, and 959 // then we create the block containing the if statement. If we were in the 960 // middle of a block, we stop processing that block. That block is then the 961 // implicit successor for the "then" and "else" clauses. 962 963 // The block we were proccessing is now finished. Make it the successor 964 // block. 965 if (Block) { 966 Succ = Block; 967 if (badCFG) 968 return 0; 969 } 970 971 // Process the false branch. 972 CFGBlock* ElseBlock = Succ; 973 974 if (Stmt* Else = I->getElse()) { 975 SaveAndRestore<CFGBlock*> sv(Succ); 976 977 // NULL out Block so that the recursive call to Visit will 978 // create a new basic block. 979 Block = NULL; 980 ElseBlock = addStmt(Else); 981 982 if (!ElseBlock) // Can occur when the Else body has all NullStmts. 983 ElseBlock = sv.get(); 984 else if (Block) { 985 if (badCFG) 986 return 0; 987 } 988 } 989 990 // Process the true branch. 991 CFGBlock* ThenBlock; 992 { 993 Stmt* Then = I->getThen(); 994 assert(Then); 995 SaveAndRestore<CFGBlock*> sv(Succ); 996 Block = NULL; 997 ThenBlock = addStmt(Then); 998 999 if (!ThenBlock) { 1000 // We can reach here if the "then" body has all NullStmts. 1001 // Create an empty block so we can distinguish between true and false 1002 // branches in path-sensitive analyses. 1003 ThenBlock = createBlock(false); 1004 AddSuccessor(ThenBlock, sv.get()); 1005 } else if (Block) { 1006 if (badCFG) 1007 return 0; 1008 } 1009 } 1010 1011 // Now create a new block containing the if statement. 1012 Block = createBlock(false); 1013 1014 // Set the terminator of the new block to the If statement. 1015 Block->setTerminator(I); 1016 1017 // See if this is a known constant. 1018 const TryResult &KnownVal = TryEvaluateBool(I->getCond()); 1019 1020 // Now add the successors. 1021 AddSuccessor(Block, KnownVal.isFalse() ? NULL : ThenBlock); 1022 AddSuccessor(Block, KnownVal.isTrue()? NULL : ElseBlock); 1023 1024 // Add the condition as the last statement in the new block. This may create 1025 // new blocks as the condition may contain control-flow. Any newly created 1026 // blocks will be pointed to be "Block". 1027 Block = addStmt(I->getCond()); 1028 1029 // Finally, if the IfStmt contains a condition variable, add both the IfStmt 1030 // and the condition variable initialization to the CFG. 1031 if (VarDecl *VD = I->getConditionVariable()) { 1032 if (Expr *Init = VD->getInit()) { 1033 autoCreateBlock(); 1034 AppendStmt(Block, I, AddStmtChoice::AlwaysAdd); 1035 addStmt(Init); 1036 } 1037 } 1038 1039 return Block; 1040} 1041 1042 1043CFGBlock* CFGBuilder::VisitReturnStmt(ReturnStmt* R) { 1044 // If we were in the middle of a block we stop processing that block. 1045 // 1046 // NOTE: If a "return" appears in the middle of a block, this means that the 1047 // code afterwards is DEAD (unreachable). We still keep a basic block 1048 // for that code; a simple "mark-and-sweep" from the entry block will be 1049 // able to report such dead blocks. 1050 1051 // Create the new block. 1052 Block = createBlock(false); 1053 1054 // The Exit block is the only successor. 1055 AddSuccessor(Block, &cfg->getExit()); 1056 1057 // Add the return statement to the block. This may create new blocks if R 1058 // contains control-flow (short-circuit operations). 1059 return VisitStmt(R, AddStmtChoice::AlwaysAdd); 1060} 1061 1062CFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt* L) { 1063 // Get the block of the labeled statement. Add it to our map. 1064 addStmt(L->getSubStmt()); 1065 CFGBlock* LabelBlock = Block; 1066 1067 if (!LabelBlock) // This can happen when the body is empty, i.e. 1068 LabelBlock = createBlock(); // scopes that only contains NullStmts. 1069 1070 assert(LabelMap.find(L) == LabelMap.end() && "label already in map"); 1071 LabelMap[ L ] = JumpTarget(LabelBlock, ScopePos); 1072 1073 // Labels partition blocks, so this is the end of the basic block we were 1074 // processing (L is the block's label). Because this is label (and we have 1075 // already processed the substatement) there is no extra control-flow to worry 1076 // about. 1077 LabelBlock->setLabel(L); 1078 if (badCFG) 1079 return 0; 1080 1081 // We set Block to NULL to allow lazy creation of a new block (if necessary); 1082 Block = NULL; 1083 1084 // This block is now the implicit successor of other blocks. 1085 Succ = LabelBlock; 1086 1087 return LabelBlock; 1088} 1089 1090CFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) { 1091 // Goto is a control-flow statement. Thus we stop processing the current 1092 // block and create a new one. 1093 1094 Block = createBlock(false); 1095 Block->setTerminator(G); 1096 1097 // If we already know the mapping to the label block add the successor now. 1098 LabelMapTy::iterator I = LabelMap.find(G->getLabel()); 1099 1100 if (I == LabelMap.end()) 1101 // We will need to backpatch this block later. 1102 BackpatchBlocks.push_back(JumpSource(Block, ScopePos)); 1103 else { 1104 JumpTarget JT = I->second; 1105 AddSuccessor(Block, JT.Block); 1106 } 1107 1108 return Block; 1109} 1110 1111CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { 1112 CFGBlock* LoopSuccessor = NULL; 1113 1114 LocalScope::const_iterator LoopBeginScopePos = ScopePos; 1115 1116 // "for" is a control-flow statement. Thus we stop processing the current 1117 // block. 1118 if (Block) { 1119 if (badCFG) 1120 return 0; 1121 LoopSuccessor = Block; 1122 } else 1123 LoopSuccessor = Succ; 1124 1125 // Save the current value for the break targets. 1126 // All breaks should go to the code following the loop. 1127 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget); 1128 BreakJumpTarget = JumpTarget(LoopSuccessor, LoopBeginScopePos); 1129 1130 // Because of short-circuit evaluation, the condition of the loop can span 1131 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1132 // evaluate the condition. 1133 CFGBlock* ExitConditionBlock = createBlock(false); 1134 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1135 1136 // Set the terminator for the "exit" condition block. 1137 ExitConditionBlock->setTerminator(F); 1138 1139 // Now add the actual condition to the condition block. Because the condition 1140 // itself may contain control-flow, new blocks may be created. 1141 if (Stmt* C = F->getCond()) { 1142 Block = ExitConditionBlock; 1143 EntryConditionBlock = addStmt(C); 1144 assert(Block == EntryConditionBlock || 1145 (Block == 0 && EntryConditionBlock == Succ)); 1146 1147 // If this block contains a condition variable, add both the condition 1148 // variable and initializer to the CFG. 1149 if (VarDecl *VD = F->getConditionVariable()) { 1150 if (Expr *Init = VD->getInit()) { 1151 autoCreateBlock(); 1152 AppendStmt(Block, F, AddStmtChoice::AlwaysAdd); 1153 EntryConditionBlock = addStmt(Init); 1154 assert(Block == EntryConditionBlock); 1155 } 1156 } 1157 1158 if (Block) { 1159 if (badCFG) 1160 return 0; 1161 } 1162 } 1163 1164 // The condition block is the implicit successor for the loop body as well as 1165 // any code above the loop. 1166 Succ = EntryConditionBlock; 1167 1168 // See if this is a known constant. 1169 TryResult KnownVal(true); 1170 1171 if (F->getCond()) 1172 KnownVal = TryEvaluateBool(F->getCond()); 1173 1174 // Now create the loop body. 1175 { 1176 assert(F->getBody()); 1177 1178 // Save the current values for Block, Succ, and continue targets. 1179 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); 1180 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget); 1181 1182 // Create a new block to contain the (bottom) of the loop body. 1183 Block = NULL; 1184 1185 if (Stmt* I = F->getInc()) { 1186 // Generate increment code in its own basic block. This is the target of 1187 // continue statements. 1188 Succ = addStmt(I); 1189 } else { 1190 // No increment code. Create a special, empty, block that is used as the 1191 // target block for "looping back" to the start of the loop. 1192 assert(Succ == EntryConditionBlock); 1193 Succ = createBlock(); 1194 } 1195 1196 // Finish up the increment (or empty) block if it hasn't been already. 1197 if (Block) { 1198 assert(Block == Succ); 1199 if (badCFG) 1200 return 0; 1201 Block = 0; 1202 } 1203 1204 ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos); 1205 1206 // The starting block for the loop increment is the block that should 1207 // represent the 'loop target' for looping back to the start of the loop. 1208 ContinueJumpTarget.Block->setLoopTarget(F); 1209 1210 // Now populate the body block, and in the process create new blocks as we 1211 // walk the body of the loop. 1212 CFGBlock* BodyBlock = addStmt(F->getBody()); 1213 1214 if (!BodyBlock) 1215 BodyBlock = ContinueJumpTarget.Block;//can happen for "for (...;...;...);" 1216 else if (badCFG) 1217 return 0; 1218 1219 // This new body block is a successor to our "exit" condition block. 1220 AddSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); 1221 } 1222 1223 // Link up the condition block with the code that follows the loop. (the 1224 // false branch). 1225 AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 1226 1227 // If the loop contains initialization, create a new block for those 1228 // statements. This block can also contain statements that precede the loop. 1229 if (Stmt* I = F->getInit()) { 1230 Block = createBlock(); 1231 return addStmt(I); 1232 } else { 1233 // There is no loop initialization. We are thus basically a while loop. 1234 // NULL out Block to force lazy block construction. 1235 Block = NULL; 1236 Succ = EntryConditionBlock; 1237 return EntryConditionBlock; 1238 } 1239} 1240 1241CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) { 1242 if (asc.alwaysAdd()) { 1243 autoCreateBlock(); 1244 AppendStmt(Block, M, asc); 1245 } 1246 return Visit(M->getBase(), 1247 M->isArrow() ? AddStmtChoice::NotAlwaysAdd 1248 : AddStmtChoice::AsLValueNotAlwaysAdd); 1249} 1250 1251CFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { 1252 // Objective-C fast enumeration 'for' statements: 1253 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC 1254 // 1255 // for ( Type newVariable in collection_expression ) { statements } 1256 // 1257 // becomes: 1258 // 1259 // prologue: 1260 // 1. collection_expression 1261 // T. jump to loop_entry 1262 // loop_entry: 1263 // 1. side-effects of element expression 1264 // 1. ObjCForCollectionStmt [performs binding to newVariable] 1265 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil] 1266 // TB: 1267 // statements 1268 // T. jump to loop_entry 1269 // FB: 1270 // what comes after 1271 // 1272 // and 1273 // 1274 // Type existingItem; 1275 // for ( existingItem in expression ) { statements } 1276 // 1277 // becomes: 1278 // 1279 // the same with newVariable replaced with existingItem; the binding works 1280 // the same except that for one ObjCForCollectionStmt::getElement() returns 1281 // a DeclStmt and the other returns a DeclRefExpr. 1282 // 1283 1284 CFGBlock* LoopSuccessor = 0; 1285 1286 if (Block) { 1287 if (badCFG) 1288 return 0; 1289 LoopSuccessor = Block; 1290 Block = 0; 1291 } else 1292 LoopSuccessor = Succ; 1293 1294 // Build the condition blocks. 1295 CFGBlock* ExitConditionBlock = createBlock(false); 1296 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1297 1298 // Set the terminator for the "exit" condition block. 1299 ExitConditionBlock->setTerminator(S); 1300 1301 // The last statement in the block should be the ObjCForCollectionStmt, which 1302 // performs the actual binding to 'element' and determines if there are any 1303 // more items in the collection. 1304 AppendStmt(ExitConditionBlock, S); 1305 Block = ExitConditionBlock; 1306 1307 // Walk the 'element' expression to see if there are any side-effects. We 1308 // generate new blocks as necesary. We DON'T add the statement by default to 1309 // the CFG unless it contains control-flow. 1310 EntryConditionBlock = Visit(S->getElement(), AddStmtChoice::NotAlwaysAdd); 1311 if (Block) { 1312 if (badCFG) 1313 return 0; 1314 Block = 0; 1315 } 1316 1317 // The condition block is the implicit successor for the loop body as well as 1318 // any code above the loop. 1319 Succ = EntryConditionBlock; 1320 1321 // Now create the true branch. 1322 { 1323 // Save the current values for Succ, continue and break targets. 1324 SaveAndRestore<CFGBlock*> save_Succ(Succ); 1325 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), 1326 save_break(BreakJumpTarget); 1327 1328 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 1329 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos); 1330 1331 CFGBlock* BodyBlock = addStmt(S->getBody()); 1332 1333 if (!BodyBlock) 1334 BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;" 1335 else if (Block) { 1336 if (badCFG) 1337 return 0; 1338 } 1339 1340 // This new body block is a successor to our "exit" condition block. 1341 AddSuccessor(ExitConditionBlock, BodyBlock); 1342 } 1343 1344 // Link up the condition block with the code that follows the loop. 1345 // (the false branch). 1346 AddSuccessor(ExitConditionBlock, LoopSuccessor); 1347 1348 // Now create a prologue block to contain the collection expression. 1349 Block = createBlock(); 1350 return addStmt(S->getCollection()); 1351} 1352 1353CFGBlock* CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S) { 1354 // FIXME: Add locking 'primitives' to CFG for @synchronized. 1355 1356 // Inline the body. 1357 CFGBlock *SyncBlock = addStmt(S->getSynchBody()); 1358 1359 // The sync body starts its own basic block. This makes it a little easier 1360 // for diagnostic clients. 1361 if (SyncBlock) { 1362 if (badCFG) 1363 return 0; 1364 1365 Block = 0; 1366 Succ = SyncBlock; 1367 } 1368 1369 // Add the @synchronized to the CFG. 1370 autoCreateBlock(); 1371 AppendStmt(Block, S, AddStmtChoice::AlwaysAdd); 1372 1373 // Inline the sync expression. 1374 return addStmt(S->getSynchExpr()); 1375} 1376 1377CFGBlock* CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt* S) { 1378 // FIXME 1379 return NYS(); 1380} 1381 1382CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { 1383 CFGBlock* LoopSuccessor = NULL; 1384 1385 LocalScope::const_iterator LoopBeginScopePos = ScopePos; 1386 1387 // "while" is a control-flow statement. Thus we stop processing the current 1388 // block. 1389 if (Block) { 1390 if (badCFG) 1391 return 0; 1392 LoopSuccessor = Block; 1393 } else 1394 LoopSuccessor = Succ; 1395 1396 // Because of short-circuit evaluation, the condition of the loop can span 1397 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1398 // evaluate the condition. 1399 CFGBlock* ExitConditionBlock = createBlock(false); 1400 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1401 1402 // Set the terminator for the "exit" condition block. 1403 ExitConditionBlock->setTerminator(W); 1404 1405 // Now add the actual condition to the condition block. Because the condition 1406 // itself may contain control-flow, new blocks may be created. Thus we update 1407 // "Succ" after adding the condition. 1408 if (Stmt* C = W->getCond()) { 1409 Block = ExitConditionBlock; 1410 EntryConditionBlock = addStmt(C); 1411 assert(Block == EntryConditionBlock); 1412 1413 // If this block contains a condition variable, add both the condition 1414 // variable and initializer to the CFG. 1415 if (VarDecl *VD = W->getConditionVariable()) { 1416 if (Expr *Init = VD->getInit()) { 1417 autoCreateBlock(); 1418 AppendStmt(Block, W, AddStmtChoice::AlwaysAdd); 1419 EntryConditionBlock = addStmt(Init); 1420 assert(Block == EntryConditionBlock); 1421 } 1422 } 1423 1424 if (Block) { 1425 if (badCFG) 1426 return 0; 1427 } 1428 } 1429 1430 // The condition block is the implicit successor for the loop body as well as 1431 // any code above the loop. 1432 Succ = EntryConditionBlock; 1433 1434 // See if this is a known constant. 1435 const TryResult& KnownVal = TryEvaluateBool(W->getCond()); 1436 1437 // Process the loop body. 1438 { 1439 assert(W->getBody()); 1440 1441 // Save the current values for Block, Succ, and continue and break targets 1442 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); 1443 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), 1444 save_break(BreakJumpTarget); 1445 1446 // Create an empty block to represent the transition block for looping back 1447 // to the head of the loop. 1448 Block = 0; 1449 assert(Succ == EntryConditionBlock); 1450 Succ = createBlock(); 1451 Succ->setLoopTarget(W); 1452 ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos); 1453 1454 // All breaks should go to the code following the loop. 1455 BreakJumpTarget = JumpTarget(LoopSuccessor, LoopBeginScopePos); 1456 1457 // NULL out Block to force lazy instantiation of blocks for the body. 1458 Block = NULL; 1459 1460 // Create the body. The returned block is the entry to the loop body. 1461 CFGBlock* BodyBlock = addStmt(W->getBody()); 1462 1463 if (!BodyBlock) 1464 BodyBlock = ContinueJumpTarget.Block; // can happen for "while(...) ;" 1465 else if (Block) { 1466 if (badCFG) 1467 return 0; 1468 } 1469 1470 // Add the loop body entry as a successor to the condition. 1471 AddSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); 1472 } 1473 1474 // Link up the condition block with the code that follows the loop. (the 1475 // false branch). 1476 AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 1477 1478 // There can be no more statements in the condition block since we loop back 1479 // to this block. NULL out Block to force lazy creation of another block. 1480 Block = NULL; 1481 1482 // Return the condition block, which is the dominating block for the loop. 1483 Succ = EntryConditionBlock; 1484 return EntryConditionBlock; 1485} 1486 1487 1488CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt* S) { 1489 // FIXME: For now we pretend that @catch and the code it contains does not 1490 // exit. 1491 return Block; 1492} 1493 1494CFGBlock* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt* S) { 1495 // FIXME: This isn't complete. We basically treat @throw like a return 1496 // statement. 1497 1498 // If we were in the middle of a block we stop processing that block. 1499 if (badCFG) 1500 return 0; 1501 1502 // Create the new block. 1503 Block = createBlock(false); 1504 1505 // The Exit block is the only successor. 1506 AddSuccessor(Block, &cfg->getExit()); 1507 1508 // Add the statement to the block. This may create new blocks if S contains 1509 // control-flow (short-circuit operations). 1510 return VisitStmt(S, AddStmtChoice::AlwaysAdd); 1511} 1512 1513CFGBlock* CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr* T) { 1514 // If we were in the middle of a block we stop processing that block. 1515 if (badCFG) 1516 return 0; 1517 1518 // Create the new block. 1519 Block = createBlock(false); 1520 1521 if (TryTerminatedBlock) 1522 // The current try statement is the only successor. 1523 AddSuccessor(Block, TryTerminatedBlock); 1524 else 1525 // otherwise the Exit block is the only successor. 1526 AddSuccessor(Block, &cfg->getExit()); 1527 1528 // Add the statement to the block. This may create new blocks if S contains 1529 // control-flow (short-circuit operations). 1530 return VisitStmt(T, AddStmtChoice::AlwaysAdd); 1531} 1532 1533CFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) { 1534 CFGBlock* LoopSuccessor = NULL; 1535 1536 // "do...while" is a control-flow statement. Thus we stop processing the 1537 // current block. 1538 if (Block) { 1539 if (badCFG) 1540 return 0; 1541 LoopSuccessor = Block; 1542 } else 1543 LoopSuccessor = Succ; 1544 1545 // Because of short-circuit evaluation, the condition of the loop can span 1546 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1547 // evaluate the condition. 1548 CFGBlock* ExitConditionBlock = createBlock(false); 1549 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1550 1551 // Set the terminator for the "exit" condition block. 1552 ExitConditionBlock->setTerminator(D); 1553 1554 // Now add the actual condition to the condition block. Because the condition 1555 // itself may contain control-flow, new blocks may be created. 1556 if (Stmt* C = D->getCond()) { 1557 Block = ExitConditionBlock; 1558 EntryConditionBlock = addStmt(C); 1559 if (Block) { 1560 if (badCFG) 1561 return 0; 1562 } 1563 } 1564 1565 // The condition block is the implicit successor for the loop body. 1566 Succ = EntryConditionBlock; 1567 1568 // See if this is a known constant. 1569 const TryResult &KnownVal = TryEvaluateBool(D->getCond()); 1570 1571 // Process the loop body. 1572 CFGBlock* BodyBlock = NULL; 1573 { 1574 assert(D->getBody()); 1575 1576 // Save the current values for Block, Succ, and continue and break targets 1577 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); 1578 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), 1579 save_break(BreakJumpTarget); 1580 1581 // All continues within this loop should go to the condition block 1582 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos); 1583 1584 // All breaks should go to the code following the loop. 1585 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 1586 1587 // NULL out Block to force lazy instantiation of blocks for the body. 1588 Block = NULL; 1589 1590 // Create the body. The returned block is the entry to the loop body. 1591 BodyBlock = addStmt(D->getBody()); 1592 1593 if (!BodyBlock) 1594 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)" 1595 else if (Block) { 1596 if (badCFG) 1597 return 0; 1598 } 1599 1600 if (!KnownVal.isFalse()) { 1601 // Add an intermediate block between the BodyBlock and the 1602 // ExitConditionBlock to represent the "loop back" transition. Create an 1603 // empty block to represent the transition block for looping back to the 1604 // head of the loop. 1605 // FIXME: Can we do this more efficiently without adding another block? 1606 Block = NULL; 1607 Succ = BodyBlock; 1608 CFGBlock *LoopBackBlock = createBlock(); 1609 LoopBackBlock->setLoopTarget(D); 1610 1611 // Add the loop body entry as a successor to the condition. 1612 AddSuccessor(ExitConditionBlock, LoopBackBlock); 1613 } 1614 else 1615 AddSuccessor(ExitConditionBlock, NULL); 1616 } 1617 1618 // Link up the condition block with the code that follows the loop. 1619 // (the false branch). 1620 AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 1621 1622 // There can be no more statements in the body block(s) since we loop back to 1623 // the body. NULL out Block to force lazy creation of another block. 1624 Block = NULL; 1625 1626 // Return the loop body, which is the dominating block for the loop. 1627 Succ = BodyBlock; 1628 return BodyBlock; 1629} 1630 1631CFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) { 1632 // "continue" is a control-flow statement. Thus we stop processing the 1633 // current block. 1634 if (badCFG) 1635 return 0; 1636 1637 // Now create a new block that ends with the continue statement. 1638 Block = createBlock(false); 1639 Block->setTerminator(C); 1640 1641 // If there is no target for the continue, then we are looking at an 1642 // incomplete AST. This means the CFG cannot be constructed. 1643 if (ContinueJumpTarget.Block) { 1644 AddSuccessor(Block, ContinueJumpTarget.Block); 1645 } else 1646 badCFG = true; 1647 1648 return Block; 1649} 1650 1651CFGBlock *CFGBuilder::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, 1652 AddStmtChoice asc) { 1653 1654 if (asc.alwaysAdd()) { 1655 autoCreateBlock(); 1656 AppendStmt(Block, E); 1657 } 1658 1659 // VLA types have expressions that must be evaluated. 1660 if (E->isArgumentType()) { 1661 for (VariableArrayType* VA = FindVA(E->getArgumentType().getTypePtr()); 1662 VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) 1663 addStmt(VA->getSizeExpr()); 1664 } 1665 1666 return Block; 1667} 1668 1669/// VisitStmtExpr - Utility method to handle (nested) statement 1670/// expressions (a GCC extension). 1671CFGBlock* CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) { 1672 if (asc.alwaysAdd()) { 1673 autoCreateBlock(); 1674 AppendStmt(Block, SE); 1675 } 1676 return VisitCompoundStmt(SE->getSubStmt()); 1677} 1678 1679CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { 1680 // "switch" is a control-flow statement. Thus we stop processing the current 1681 // block. 1682 CFGBlock* SwitchSuccessor = NULL; 1683 1684 if (Block) { 1685 if (badCFG) 1686 return 0; 1687 SwitchSuccessor = Block; 1688 } else SwitchSuccessor = Succ; 1689 1690 // Save the current "switch" context. 1691 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock), 1692 save_default(DefaultCaseBlock); 1693 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget); 1694 1695 // Set the "default" case to be the block after the switch statement. If the 1696 // switch statement contains a "default:", this value will be overwritten with 1697 // the block for that code. 1698 DefaultCaseBlock = SwitchSuccessor; 1699 1700 // Create a new block that will contain the switch statement. 1701 SwitchTerminatedBlock = createBlock(false); 1702 1703 // Now process the switch body. The code after the switch is the implicit 1704 // successor. 1705 Succ = SwitchSuccessor; 1706 BreakJumpTarget = JumpTarget(SwitchSuccessor, ScopePos); 1707 1708 // When visiting the body, the case statements should automatically get linked 1709 // up to the switch. We also don't keep a pointer to the body, since all 1710 // control-flow from the switch goes to case/default statements. 1711 assert(Terminator->getBody() && "switch must contain a non-NULL body"); 1712 Block = NULL; 1713 addStmt(Terminator->getBody()); 1714 if (Block) { 1715 if (badCFG) 1716 return 0; 1717 } 1718 1719 // If we have no "default:" case, the default transition is to the code 1720 // following the switch body. 1721 AddSuccessor(SwitchTerminatedBlock, DefaultCaseBlock); 1722 1723 // Add the terminator and condition in the switch block. 1724 SwitchTerminatedBlock->setTerminator(Terminator); 1725 assert(Terminator->getCond() && "switch condition must be non-NULL"); 1726 Block = SwitchTerminatedBlock; 1727 Block = addStmt(Terminator->getCond()); 1728 1729 // Finally, if the SwitchStmt contains a condition variable, add both the 1730 // SwitchStmt and the condition variable initialization to the CFG. 1731 if (VarDecl *VD = Terminator->getConditionVariable()) { 1732 if (Expr *Init = VD->getInit()) { 1733 autoCreateBlock(); 1734 AppendStmt(Block, Terminator, AddStmtChoice::AlwaysAdd); 1735 addStmt(Init); 1736 } 1737 } 1738 1739 return Block; 1740} 1741 1742CFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* CS) { 1743 // CaseStmts are essentially labels, so they are the first statement in a 1744 // block. 1745 CFGBlock *TopBlock = 0, *LastBlock = 0; 1746 1747 if (Stmt *Sub = CS->getSubStmt()) { 1748 // For deeply nested chains of CaseStmts, instead of doing a recursion 1749 // (which can blow out the stack), manually unroll and create blocks 1750 // along the way. 1751 while (isa<CaseStmt>(Sub)) { 1752 CFGBlock *CurrentBlock = createBlock(false); 1753 CurrentBlock->setLabel(CS); 1754 1755 if (TopBlock) 1756 AddSuccessor(LastBlock, CurrentBlock); 1757 else 1758 TopBlock = CurrentBlock; 1759 1760 AddSuccessor(SwitchTerminatedBlock, CurrentBlock); 1761 LastBlock = CurrentBlock; 1762 1763 CS = cast<CaseStmt>(Sub); 1764 Sub = CS->getSubStmt(); 1765 } 1766 1767 addStmt(Sub); 1768 } 1769 1770 CFGBlock* CaseBlock = Block; 1771 if (!CaseBlock) 1772 CaseBlock = createBlock(); 1773 1774 // Cases statements partition blocks, so this is the top of the basic block we 1775 // were processing (the "case XXX:" is the label). 1776 CaseBlock->setLabel(CS); 1777 1778 if (badCFG) 1779 return 0; 1780 1781 // Add this block to the list of successors for the block with the switch 1782 // statement. 1783 assert(SwitchTerminatedBlock); 1784 AddSuccessor(SwitchTerminatedBlock, CaseBlock); 1785 1786 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1787 Block = NULL; 1788 1789 if (TopBlock) { 1790 AddSuccessor(LastBlock, CaseBlock); 1791 Succ = TopBlock; 1792 } 1793 else { 1794 // This block is now the implicit successor of other blocks. 1795 Succ = CaseBlock; 1796 } 1797 1798 return Succ; 1799} 1800 1801CFGBlock* CFGBuilder::VisitDefaultStmt(DefaultStmt* Terminator) { 1802 if (Terminator->getSubStmt()) 1803 addStmt(Terminator->getSubStmt()); 1804 1805 DefaultCaseBlock = Block; 1806 1807 if (!DefaultCaseBlock) 1808 DefaultCaseBlock = createBlock(); 1809 1810 // Default statements partition blocks, so this is the top of the basic block 1811 // we were processing (the "default:" is the label). 1812 DefaultCaseBlock->setLabel(Terminator); 1813 1814 if (badCFG) 1815 return 0; 1816 1817 // Unlike case statements, we don't add the default block to the successors 1818 // for the switch statement immediately. This is done when we finish 1819 // processing the switch statement. This allows for the default case 1820 // (including a fall-through to the code after the switch statement) to always 1821 // be the last successor of a switch-terminated block. 1822 1823 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1824 Block = NULL; 1825 1826 // This block is now the implicit successor of other blocks. 1827 Succ = DefaultCaseBlock; 1828 1829 return DefaultCaseBlock; 1830} 1831 1832CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) { 1833 // "try"/"catch" is a control-flow statement. Thus we stop processing the 1834 // current block. 1835 CFGBlock* TrySuccessor = NULL; 1836 1837 if (Block) { 1838 if (badCFG) 1839 return 0; 1840 TrySuccessor = Block; 1841 } else TrySuccessor = Succ; 1842 1843 CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock; 1844 1845 // Create a new block that will contain the try statement. 1846 CFGBlock *NewTryTerminatedBlock = createBlock(false); 1847 // Add the terminator in the try block. 1848 NewTryTerminatedBlock->setTerminator(Terminator); 1849 1850 bool HasCatchAll = false; 1851 for (unsigned h = 0; h <Terminator->getNumHandlers(); ++h) { 1852 // The code after the try is the implicit successor. 1853 Succ = TrySuccessor; 1854 CXXCatchStmt *CS = Terminator->getHandler(h); 1855 if (CS->getExceptionDecl() == 0) { 1856 HasCatchAll = true; 1857 } 1858 Block = NULL; 1859 CFGBlock *CatchBlock = VisitCXXCatchStmt(CS); 1860 if (CatchBlock == 0) 1861 return 0; 1862 // Add this block to the list of successors for the block with the try 1863 // statement. 1864 AddSuccessor(NewTryTerminatedBlock, CatchBlock); 1865 } 1866 if (!HasCatchAll) { 1867 if (PrevTryTerminatedBlock) 1868 AddSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock); 1869 else 1870 AddSuccessor(NewTryTerminatedBlock, &cfg->getExit()); 1871 } 1872 1873 // The code after the try is the implicit successor. 1874 Succ = TrySuccessor; 1875 1876 // Save the current "try" context. 1877 SaveAndRestore<CFGBlock*> save_try(TryTerminatedBlock); 1878 TryTerminatedBlock = NewTryTerminatedBlock; 1879 1880 assert(Terminator->getTryBlock() && "try must contain a non-NULL body"); 1881 Block = NULL; 1882 Block = addStmt(Terminator->getTryBlock()); 1883 return Block; 1884} 1885 1886CFGBlock* CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt* CS) { 1887 // CXXCatchStmt are treated like labels, so they are the first statement in a 1888 // block. 1889 1890 if (CS->getHandlerBlock()) 1891 addStmt(CS->getHandlerBlock()); 1892 1893 CFGBlock* CatchBlock = Block; 1894 if (!CatchBlock) 1895 CatchBlock = createBlock(); 1896 1897 CatchBlock->setLabel(CS); 1898 1899 if (badCFG) 1900 return 0; 1901 1902 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1903 Block = NULL; 1904 1905 return CatchBlock; 1906} 1907 1908CFGBlock *CFGBuilder::VisitCXXMemberCallExpr(CXXMemberCallExpr *C, 1909 AddStmtChoice asc) { 1910 AddStmtChoice::Kind K = asc.asLValue() ? AddStmtChoice::AlwaysAddAsLValue 1911 : AddStmtChoice::AlwaysAdd; 1912 autoCreateBlock(); 1913 AppendStmt(Block, C, AddStmtChoice(K)); 1914 return VisitChildren(C); 1915} 1916 1917CFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1918 // Lazily create the indirect-goto dispatch block if there isn't one already. 1919 CFGBlock* IBlock = cfg->getIndirectGotoBlock(); 1920 1921 if (!IBlock) { 1922 IBlock = createBlock(false); 1923 cfg->setIndirectGotoBlock(IBlock); 1924 } 1925 1926 // IndirectGoto is a control-flow statement. Thus we stop processing the 1927 // current block and create a new one. 1928 if (badCFG) 1929 return 0; 1930 1931 Block = createBlock(false); 1932 Block->setTerminator(I); 1933 AddSuccessor(Block, IBlock); 1934 return addStmt(I->getTarget()); 1935} 1936 1937} // end anonymous namespace 1938 1939/// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has 1940/// no successors or predecessors. If this is the first block created in the 1941/// CFG, it is automatically set to be the Entry and Exit of the CFG. 1942CFGBlock* CFG::createBlock() { 1943 bool first_block = begin() == end(); 1944 1945 // Create the block. 1946 CFGBlock *Mem = getAllocator().Allocate<CFGBlock>(); 1947 new (Mem) CFGBlock(NumBlockIDs++, BlkBVC); 1948 Blocks.push_back(Mem, BlkBVC); 1949 1950 // If this is the first block, set it as the Entry and Exit. 1951 if (first_block) 1952 Entry = Exit = &back(); 1953 1954 // Return the block. 1955 return &back(); 1956} 1957 1958/// buildCFG - Constructs a CFG from an AST. Ownership of the returned 1959/// CFG is returned to the caller. 1960CFG* CFG::buildCFG(const Decl *D, Stmt* Statement, ASTContext *C, 1961 BuildOptions BO) { 1962 CFGBuilder Builder; 1963 return Builder.buildCFG(D, Statement, C, BO); 1964} 1965 1966//===----------------------------------------------------------------------===// 1967// CFG: Queries for BlkExprs. 1968//===----------------------------------------------------------------------===// 1969 1970namespace { 1971 typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy; 1972} 1973 1974static void FindSubExprAssignments(Stmt *S, 1975 llvm::SmallPtrSet<Expr*,50>& Set) { 1976 if (!S) 1977 return; 1978 1979 for (Stmt::child_iterator I=S->child_begin(), E=S->child_end(); I!=E; ++I) { 1980 Stmt *child = *I; 1981 if (!child) 1982 continue; 1983 1984 if (BinaryOperator* B = dyn_cast<BinaryOperator>(child)) 1985 if (B->isAssignmentOp()) Set.insert(B); 1986 1987 FindSubExprAssignments(child, Set); 1988 } 1989} 1990 1991static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { 1992 BlkExprMapTy* M = new BlkExprMapTy(); 1993 1994 // Look for assignments that are used as subexpressions. These are the only 1995 // assignments that we want to *possibly* register as a block-level 1996 // expression. Basically, if an assignment occurs both in a subexpression and 1997 // at the block-level, it is a block-level expression. 1998 llvm::SmallPtrSet<Expr*,50> SubExprAssignments; 1999 2000 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) 2001 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) 2002 if (CFGStmt S = BI->getAs<CFGStmt>()) 2003 FindSubExprAssignments(S, SubExprAssignments); 2004 2005 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { 2006 2007 // Iterate over the statements again on identify the Expr* and Stmt* at the 2008 // block-level that are block-level expressions. 2009 2010 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) { 2011 CFGStmt CS = BI->getAs<CFGStmt>(); 2012 if (!CS.isValid()) 2013 continue; 2014 if (Expr* Exp = dyn_cast<Expr>(CS.getStmt())) { 2015 2016 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { 2017 // Assignment expressions that are not nested within another 2018 // expression are really "statements" whose value is never used by 2019 // another expression. 2020 if (B->isAssignmentOp() && !SubExprAssignments.count(Exp)) 2021 continue; 2022 } else if (const StmtExpr* Terminator = dyn_cast<StmtExpr>(Exp)) { 2023 // Special handling for statement expressions. The last statement in 2024 // the statement expression is also a block-level expr. 2025 const CompoundStmt* C = Terminator->getSubStmt(); 2026 if (!C->body_empty()) { 2027 unsigned x = M->size(); 2028 (*M)[C->body_back()] = x; 2029 } 2030 } 2031 2032 unsigned x = M->size(); 2033 (*M)[Exp] = x; 2034 } 2035 } 2036 2037 // Look at terminators. The condition is a block-level expression. 2038 2039 Stmt* S = (*I)->getTerminatorCondition(); 2040 2041 if (S && M->find(S) == M->end()) { 2042 unsigned x = M->size(); 2043 (*M)[S] = x; 2044 } 2045 } 2046 2047 return M; 2048} 2049 2050CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt* S) { 2051 assert(S != NULL); 2052 if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); } 2053 2054 BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap); 2055 BlkExprMapTy::iterator I = M->find(S); 2056 return (I == M->end()) ? CFG::BlkExprNumTy() : CFG::BlkExprNumTy(I->second); 2057} 2058 2059unsigned CFG::getNumBlkExprs() { 2060 if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap)) 2061 return M->size(); 2062 else { 2063 // We assume callers interested in the number of BlkExprs will want 2064 // the map constructed if it doesn't already exist. 2065 BlkExprMap = (void*) PopulateBlkExprMap(*this); 2066 return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); 2067 } 2068} 2069 2070//===----------------------------------------------------------------------===// 2071// Filtered walking of the CFG. 2072//===----------------------------------------------------------------------===// 2073 2074bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F, 2075 const CFGBlock *From, const CFGBlock *To) { 2076 2077 if (F.IgnoreDefaultsWithCoveredEnums) { 2078 // If the 'To' has no label or is labeled but the label isn't a 2079 // CaseStmt then filter this edge. 2080 if (const SwitchStmt *S = 2081 dyn_cast_or_null<SwitchStmt>(From->getTerminator())) { 2082 if (S->isAllEnumCasesCovered()) { 2083 const Stmt *L = To->getLabel(); 2084 if (!L || !isa<CaseStmt>(L)) 2085 return true; 2086 } 2087 } 2088 } 2089 2090 return false; 2091} 2092 2093//===----------------------------------------------------------------------===// 2094// Cleanup: CFG dstor. 2095//===----------------------------------------------------------------------===// 2096 2097CFG::~CFG() { 2098 delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap); 2099} 2100 2101//===----------------------------------------------------------------------===// 2102// CFG pretty printing 2103//===----------------------------------------------------------------------===// 2104 2105namespace { 2106 2107class StmtPrinterHelper : public PrinterHelper { 2108 typedef llvm::DenseMap<Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; 2109 typedef llvm::DenseMap<Decl*,std::pair<unsigned,unsigned> > DeclMapTy; 2110 StmtMapTy StmtMap; 2111 DeclMapTy DeclMap; 2112 signed CurrentBlock; 2113 unsigned CurrentStmt; 2114 const LangOptions &LangOpts; 2115public: 2116 2117 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) 2118 : CurrentBlock(0), CurrentStmt(0), LangOpts(LO) { 2119 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { 2120 unsigned j = 1; 2121 for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ; 2122 BI != BEnd; ++BI, ++j ) { 2123 if (CFGStmt SE = BI->getAs<CFGStmt>()) { 2124 std::pair<unsigned, unsigned> P((*I)->getBlockID(), j); 2125 StmtMap[SE] = P; 2126 2127 if (DeclStmt* DS = dyn_cast<DeclStmt>(SE.getStmt())) { 2128 DeclMap[DS->getSingleDecl()] = P; 2129 2130 } else if (IfStmt* IS = dyn_cast<IfStmt>(SE.getStmt())) { 2131 if (VarDecl* VD = IS->getConditionVariable()) 2132 DeclMap[VD] = P; 2133 2134 } else if (ForStmt* FS = dyn_cast<ForStmt>(SE.getStmt())) { 2135 if (VarDecl* VD = FS->getConditionVariable()) 2136 DeclMap[VD] = P; 2137 2138 } else if (WhileStmt* WS = dyn_cast<WhileStmt>(SE.getStmt())) { 2139 if (VarDecl* VD = WS->getConditionVariable()) 2140 DeclMap[VD] = P; 2141 2142 } else if (SwitchStmt* SS = dyn_cast<SwitchStmt>(SE.getStmt())) { 2143 if (VarDecl* VD = SS->getConditionVariable()) 2144 DeclMap[VD] = P; 2145 2146 } else if (CXXCatchStmt* CS = dyn_cast<CXXCatchStmt>(SE.getStmt())) { 2147 if (VarDecl* VD = CS->getExceptionDecl()) 2148 DeclMap[VD] = P; 2149 } 2150 } 2151 } 2152 } 2153 } 2154 2155 virtual ~StmtPrinterHelper() {} 2156 2157 const LangOptions &getLangOpts() const { return LangOpts; } 2158 void setBlockID(signed i) { CurrentBlock = i; } 2159 void setStmtID(unsigned i) { CurrentStmt = i; } 2160 2161 virtual bool handledStmt(Stmt* S, llvm::raw_ostream& OS) { 2162 StmtMapTy::iterator I = StmtMap.find(S); 2163 2164 if (I == StmtMap.end()) 2165 return false; 2166 2167 if (CurrentBlock >= 0 && I->second.first == (unsigned) CurrentBlock 2168 && I->second.second == CurrentStmt) { 2169 return false; 2170 } 2171 2172 OS << "[B" << I->second.first << "." << I->second.second << "]"; 2173 return true; 2174 } 2175 2176 bool handleDecl(Decl* D, llvm::raw_ostream& OS) { 2177 DeclMapTy::iterator I = DeclMap.find(D); 2178 2179 if (I == DeclMap.end()) 2180 return false; 2181 2182 if (CurrentBlock >= 0 && I->second.first == (unsigned) CurrentBlock 2183 && I->second.second == CurrentStmt) { 2184 return false; 2185 } 2186 2187 OS << "[B" << I->second.first << "." << I->second.second << "]"; 2188 return true; 2189 } 2190}; 2191} // end anonymous namespace 2192 2193 2194namespace { 2195class CFGBlockTerminatorPrint 2196 : public StmtVisitor<CFGBlockTerminatorPrint,void> { 2197 2198 llvm::raw_ostream& OS; 2199 StmtPrinterHelper* Helper; 2200 PrintingPolicy Policy; 2201public: 2202 CFGBlockTerminatorPrint(llvm::raw_ostream& os, StmtPrinterHelper* helper, 2203 const PrintingPolicy &Policy) 2204 : OS(os), Helper(helper), Policy(Policy) {} 2205 2206 void VisitIfStmt(IfStmt* I) { 2207 OS << "if "; 2208 I->getCond()->printPretty(OS,Helper,Policy); 2209 } 2210 2211 // Default case. 2212 void VisitStmt(Stmt* Terminator) { 2213 Terminator->printPretty(OS, Helper, Policy); 2214 } 2215 2216 void VisitForStmt(ForStmt* F) { 2217 OS << "for (" ; 2218 if (F->getInit()) 2219 OS << "..."; 2220 OS << "; "; 2221 if (Stmt* C = F->getCond()) 2222 C->printPretty(OS, Helper, Policy); 2223 OS << "; "; 2224 if (F->getInc()) 2225 OS << "..."; 2226 OS << ")"; 2227 } 2228 2229 void VisitWhileStmt(WhileStmt* W) { 2230 OS << "while " ; 2231 if (Stmt* C = W->getCond()) 2232 C->printPretty(OS, Helper, Policy); 2233 } 2234 2235 void VisitDoStmt(DoStmt* D) { 2236 OS << "do ... while "; 2237 if (Stmt* C = D->getCond()) 2238 C->printPretty(OS, Helper, Policy); 2239 } 2240 2241 void VisitSwitchStmt(SwitchStmt* Terminator) { 2242 OS << "switch "; 2243 Terminator->getCond()->printPretty(OS, Helper, Policy); 2244 } 2245 2246 void VisitCXXTryStmt(CXXTryStmt* CS) { 2247 OS << "try ..."; 2248 } 2249 2250 void VisitConditionalOperator(ConditionalOperator* C) { 2251 C->getCond()->printPretty(OS, Helper, Policy); 2252 OS << " ? ... : ..."; 2253 } 2254 2255 void VisitChooseExpr(ChooseExpr* C) { 2256 OS << "__builtin_choose_expr( "; 2257 C->getCond()->printPretty(OS, Helper, Policy); 2258 OS << " )"; 2259 } 2260 2261 void VisitIndirectGotoStmt(IndirectGotoStmt* I) { 2262 OS << "goto *"; 2263 I->getTarget()->printPretty(OS, Helper, Policy); 2264 } 2265 2266 void VisitBinaryOperator(BinaryOperator* B) { 2267 if (!B->isLogicalOp()) { 2268 VisitExpr(B); 2269 return; 2270 } 2271 2272 B->getLHS()->printPretty(OS, Helper, Policy); 2273 2274 switch (B->getOpcode()) { 2275 case BO_LOr: 2276 OS << " || ..."; 2277 return; 2278 case BO_LAnd: 2279 OS << " && ..."; 2280 return; 2281 default: 2282 assert(false && "Invalid logical operator."); 2283 } 2284 } 2285 2286 void VisitExpr(Expr* E) { 2287 E->printPretty(OS, Helper, Policy); 2288 } 2289}; 2290} // end anonymous namespace 2291 2292static void print_elem(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, 2293 const CFGElement &E) { 2294 if (CFGStmt CS = E.getAs<CFGStmt>()) { 2295 Stmt *S = CS; 2296 2297 if (Helper) { 2298 2299 // special printing for statement-expressions. 2300 if (StmtExpr* SE = dyn_cast<StmtExpr>(S)) { 2301 CompoundStmt* Sub = SE->getSubStmt(); 2302 2303 if (Sub->child_begin() != Sub->child_end()) { 2304 OS << "({ ... ; "; 2305 Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); 2306 OS << " })\n"; 2307 return; 2308 } 2309 } 2310 // special printing for comma expressions. 2311 if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { 2312 if (B->getOpcode() == BO_Comma) { 2313 OS << "... , "; 2314 Helper->handledStmt(B->getRHS(),OS); 2315 OS << '\n'; 2316 return; 2317 } 2318 } 2319 } 2320 S->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 2321 2322 if (isa<CXXOperatorCallExpr>(S)) { 2323 OS << " (OperatorCall)"; 2324 } 2325 else if (isa<CXXBindTemporaryExpr>(S)) { 2326 OS << " (BindTemporary)"; 2327 } 2328 2329 // Expressions need a newline. 2330 if (isa<Expr>(S)) 2331 OS << '\n'; 2332 2333 } else if (CFGInitializer IE = E.getAs<CFGInitializer>()) { 2334 CXXBaseOrMemberInitializer* I = IE; 2335 if (I->isBaseInitializer()) 2336 OS << I->getBaseClass()->getAsCXXRecordDecl()->getName(); 2337 else OS << I->getMember()->getName(); 2338 2339 OS << "("; 2340 if (Expr* IE = I->getInit()) 2341 IE->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 2342 OS << ")"; 2343 2344 if (I->isBaseInitializer()) 2345 OS << " (Base initializer)\n"; 2346 else OS << " (Member initializer)\n"; 2347 2348 } else if (CFGAutomaticObjDtor DE = E.getAs<CFGAutomaticObjDtor>()){ 2349 VarDecl* VD = DE.getVarDecl(); 2350 Helper->handleDecl(VD, OS); 2351 2352 Type* T = VD->getType().getTypePtr(); 2353 if (const ReferenceType* RT = T->getAs<ReferenceType>()) 2354 T = RT->getPointeeType().getTypePtr(); 2355 2356 OS << ".~" << T->getAsCXXRecordDecl()->getName().str() << "()"; 2357 OS << " (Implicit destructor)\n"; 2358 } 2359 } 2360 2361static void print_block(llvm::raw_ostream& OS, const CFG* cfg, 2362 const CFGBlock& B, 2363 StmtPrinterHelper* Helper, bool print_edges) { 2364 2365 if (Helper) Helper->setBlockID(B.getBlockID()); 2366 2367 // Print the header. 2368 OS << "\n [ B" << B.getBlockID(); 2369 2370 if (&B == &cfg->getEntry()) 2371 OS << " (ENTRY) ]\n"; 2372 else if (&B == &cfg->getExit()) 2373 OS << " (EXIT) ]\n"; 2374 else if (&B == cfg->getIndirectGotoBlock()) 2375 OS << " (INDIRECT GOTO DISPATCH) ]\n"; 2376 else 2377 OS << " ]\n"; 2378 2379 // Print the label of this block. 2380 if (Stmt* Label = const_cast<Stmt*>(B.getLabel())) { 2381 2382 if (print_edges) 2383 OS << " "; 2384 2385 if (LabelStmt* L = dyn_cast<LabelStmt>(Label)) 2386 OS << L->getName(); 2387 else if (CaseStmt* C = dyn_cast<CaseStmt>(Label)) { 2388 OS << "case "; 2389 C->getLHS()->printPretty(OS, Helper, 2390 PrintingPolicy(Helper->getLangOpts())); 2391 if (C->getRHS()) { 2392 OS << " ... "; 2393 C->getRHS()->printPretty(OS, Helper, 2394 PrintingPolicy(Helper->getLangOpts())); 2395 } 2396 } else if (isa<DefaultStmt>(Label)) 2397 OS << "default"; 2398 else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Label)) { 2399 OS << "catch ("; 2400 if (CS->getExceptionDecl()) 2401 CS->getExceptionDecl()->print(OS, PrintingPolicy(Helper->getLangOpts()), 2402 0); 2403 else 2404 OS << "..."; 2405 OS << ")"; 2406 2407 } else 2408 assert(false && "Invalid label statement in CFGBlock."); 2409 2410 OS << ":\n"; 2411 } 2412 2413 // Iterate through the statements in the block and print them. 2414 unsigned j = 1; 2415 2416 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; 2417 I != E ; ++I, ++j ) { 2418 2419 // Print the statement # in the basic block and the statement itself. 2420 if (print_edges) 2421 OS << " "; 2422 2423 OS << llvm::format("%3d", j) << ": "; 2424 2425 if (Helper) 2426 Helper->setStmtID(j); 2427 2428 print_elem(OS,Helper,*I); 2429 } 2430 2431 // Print the terminator of this block. 2432 if (B.getTerminator()) { 2433 if (print_edges) 2434 OS << " "; 2435 2436 OS << " T: "; 2437 2438 if (Helper) Helper->setBlockID(-1); 2439 2440 CFGBlockTerminatorPrint TPrinter(OS, Helper, 2441 PrintingPolicy(Helper->getLangOpts())); 2442 TPrinter.Visit(const_cast<Stmt*>(B.getTerminator())); 2443 OS << '\n'; 2444 } 2445 2446 if (print_edges) { 2447 // Print the predecessors of this block. 2448 OS << " Predecessors (" << B.pred_size() << "):"; 2449 unsigned i = 0; 2450 2451 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); 2452 I != E; ++I, ++i) { 2453 2454 if (i == 8 || (i-8) == 0) 2455 OS << "\n "; 2456 2457 OS << " B" << (*I)->getBlockID(); 2458 } 2459 2460 OS << '\n'; 2461 2462 // Print the successors of this block. 2463 OS << " Successors (" << B.succ_size() << "):"; 2464 i = 0; 2465 2466 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); 2467 I != E; ++I, ++i) { 2468 2469 if (i == 8 || (i-8) % 10 == 0) 2470 OS << "\n "; 2471 2472 if (*I) 2473 OS << " B" << (*I)->getBlockID(); 2474 else 2475 OS << " NULL"; 2476 } 2477 2478 OS << '\n'; 2479 } 2480} 2481 2482 2483/// dump - A simple pretty printer of a CFG that outputs to stderr. 2484void CFG::dump(const LangOptions &LO) const { print(llvm::errs(), LO); } 2485 2486/// print - A simple pretty printer of a CFG that outputs to an ostream. 2487void CFG::print(llvm::raw_ostream &OS, const LangOptions &LO) const { 2488 StmtPrinterHelper Helper(this, LO); 2489 2490 // Print the entry block. 2491 print_block(OS, this, getEntry(), &Helper, true); 2492 2493 // Iterate through the CFGBlocks and print them one by one. 2494 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { 2495 // Skip the entry block, because we already printed it. 2496 if (&(**I) == &getEntry() || &(**I) == &getExit()) 2497 continue; 2498 2499 print_block(OS, this, **I, &Helper, true); 2500 } 2501 2502 // Print the exit block. 2503 print_block(OS, this, getExit(), &Helper, true); 2504 OS.flush(); 2505} 2506 2507/// dump - A simply pretty printer of a CFGBlock that outputs to stderr. 2508void CFGBlock::dump(const CFG* cfg, const LangOptions &LO) const { 2509 print(llvm::errs(), cfg, LO); 2510} 2511 2512/// print - A simple pretty printer of a CFGBlock that outputs to an ostream. 2513/// Generally this will only be called from CFG::print. 2514void CFGBlock::print(llvm::raw_ostream& OS, const CFG* cfg, 2515 const LangOptions &LO) const { 2516 StmtPrinterHelper Helper(cfg, LO); 2517 print_block(OS, cfg, *this, &Helper, true); 2518} 2519 2520/// printTerminator - A simple pretty printer of the terminator of a CFGBlock. 2521void CFGBlock::printTerminator(llvm::raw_ostream &OS, 2522 const LangOptions &LO) const { 2523 CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO)); 2524 TPrinter.Visit(const_cast<Stmt*>(getTerminator())); 2525} 2526 2527Stmt* CFGBlock::getTerminatorCondition() { 2528 2529 if (!Terminator) 2530 return NULL; 2531 2532 Expr* E = NULL; 2533 2534 switch (Terminator->getStmtClass()) { 2535 default: 2536 break; 2537 2538 case Stmt::ForStmtClass: 2539 E = cast<ForStmt>(Terminator)->getCond(); 2540 break; 2541 2542 case Stmt::WhileStmtClass: 2543 E = cast<WhileStmt>(Terminator)->getCond(); 2544 break; 2545 2546 case Stmt::DoStmtClass: 2547 E = cast<DoStmt>(Terminator)->getCond(); 2548 break; 2549 2550 case Stmt::IfStmtClass: 2551 E = cast<IfStmt>(Terminator)->getCond(); 2552 break; 2553 2554 case Stmt::ChooseExprClass: 2555 E = cast<ChooseExpr>(Terminator)->getCond(); 2556 break; 2557 2558 case Stmt::IndirectGotoStmtClass: 2559 E = cast<IndirectGotoStmt>(Terminator)->getTarget(); 2560 break; 2561 2562 case Stmt::SwitchStmtClass: 2563 E = cast<SwitchStmt>(Terminator)->getCond(); 2564 break; 2565 2566 case Stmt::ConditionalOperatorClass: 2567 E = cast<ConditionalOperator>(Terminator)->getCond(); 2568 break; 2569 2570 case Stmt::BinaryOperatorClass: // '&&' and '||' 2571 E = cast<BinaryOperator>(Terminator)->getLHS(); 2572 break; 2573 2574 case Stmt::ObjCForCollectionStmtClass: 2575 return Terminator; 2576 } 2577 2578 return E ? E->IgnoreParens() : NULL; 2579} 2580 2581bool CFGBlock::hasBinaryBranchTerminator() const { 2582 2583 if (!Terminator) 2584 return false; 2585 2586 Expr* E = NULL; 2587 2588 switch (Terminator->getStmtClass()) { 2589 default: 2590 return false; 2591 2592 case Stmt::ForStmtClass: 2593 case Stmt::WhileStmtClass: 2594 case Stmt::DoStmtClass: 2595 case Stmt::IfStmtClass: 2596 case Stmt::ChooseExprClass: 2597 case Stmt::ConditionalOperatorClass: 2598 case Stmt::BinaryOperatorClass: 2599 return true; 2600 } 2601 2602 return E ? E->IgnoreParens() : NULL; 2603} 2604 2605 2606//===----------------------------------------------------------------------===// 2607// CFG Graphviz Visualization 2608//===----------------------------------------------------------------------===// 2609 2610 2611#ifndef NDEBUG 2612static StmtPrinterHelper* GraphHelper; 2613#endif 2614 2615void CFG::viewCFG(const LangOptions &LO) const { 2616#ifndef NDEBUG 2617 StmtPrinterHelper H(this, LO); 2618 GraphHelper = &H; 2619 llvm::ViewGraph(this,"CFG"); 2620 GraphHelper = NULL; 2621#endif 2622} 2623 2624namespace llvm { 2625template<> 2626struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { 2627 2628 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 2629 2630 static std::string getNodeLabel(const CFGBlock* Node, const CFG* Graph) { 2631 2632#ifndef NDEBUG 2633 std::string OutSStr; 2634 llvm::raw_string_ostream Out(OutSStr); 2635 print_block(Out,Graph, *Node, GraphHelper, false); 2636 std::string& OutStr = Out.str(); 2637 2638 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); 2639 2640 // Process string output to make it nicer... 2641 for (unsigned i = 0; i != OutStr.length(); ++i) 2642 if (OutStr[i] == '\n') { // Left justify 2643 OutStr[i] = '\\'; 2644 OutStr.insert(OutStr.begin()+i+1, 'l'); 2645 } 2646 2647 return OutStr; 2648#else 2649 return ""; 2650#endif 2651 } 2652}; 2653} // end namespace llvm 2654