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