CFG.cpp revision 8f9893a2beeacd5149bd2d3d4c6e130516915068
1//===--- CFG.cpp - Classes for representing and building CFGs----*- C++ -*-===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file defines the CFG and CFGBuilder classes for representing and 11// building Control-Flow Graphs (CFGs) from ASTs. 12// 13//===----------------------------------------------------------------------===// 14 15#include "clang/Analysis/CFG.h" 16#include "clang/AST/StmtVisitor.h" 17#include "clang/AST/PrettyPrinter.h" 18#include "llvm/ADT/DenseMap.h" 19#include "llvm/ADT/SmallPtrSet.h" 20#include "llvm/Support/GraphWriter.h" 21#include "llvm/Support/Streams.h" 22#include "llvm/Support/Compiler.h" 23#include <llvm/Support/Allocator.h> 24#include <llvm/Support/Format.h> 25 26using namespace clang; 27 28namespace { 29 30// SaveAndRestore - A utility class that uses RIIA to save and restore 31// the value of a variable. 32template<typename T> 33struct VISIBILITY_HIDDEN SaveAndRestore { 34 SaveAndRestore(T& x) : X(x), old_value(x) {} 35 ~SaveAndRestore() { X = old_value; } 36 T get() { return old_value; } 37 38 T& X; 39 T old_value; 40}; 41 42static SourceLocation GetEndLoc(Decl* D) { 43 if (VarDecl* VD = dyn_cast<VarDecl>(D)) 44 if (Expr* Ex = VD->getInit()) 45 return Ex->getSourceRange().getEnd(); 46 47 return D->getLocation(); 48} 49 50/// CFGBuilder - This class implements CFG construction from an AST. 51/// The builder is stateful: an instance of the builder should be used to only 52/// construct a single CFG. 53/// 54/// Example usage: 55/// 56/// CFGBuilder builder; 57/// CFG* cfg = builder.BuildAST(stmt1); 58/// 59/// CFG construction is done via a recursive walk of an AST. We actually parse 60/// the AST in reverse order so that the successor of a basic block is 61/// constructed prior to its predecessor. This allows us to nicely capture 62/// implicit fall-throughs without extra basic blocks. 63/// 64class VISIBILITY_HIDDEN CFGBuilder { 65 ASTContext *Context; 66 CFG* cfg; 67 CFGBlock* Block; 68 CFGBlock* Succ; 69 CFGBlock* ContinueTargetBlock; 70 CFGBlock* BreakTargetBlock; 71 CFGBlock* SwitchTerminatedBlock; 72 CFGBlock* DefaultCaseBlock; 73 74 // LabelMap records the mapping from Label expressions to their blocks. 75 typedef llvm::DenseMap<LabelStmt*,CFGBlock*> LabelMapTy; 76 LabelMapTy LabelMap; 77 78 // A list of blocks that end with a "goto" that must be backpatched to their 79 // resolved targets upon completion of CFG construction. 80 typedef std::vector<CFGBlock*> BackpatchBlocksTy; 81 BackpatchBlocksTy BackpatchBlocks; 82 83 // A list of labels whose address has been taken (for indirect gotos). 84 typedef llvm::SmallPtrSet<LabelStmt*,5> LabelSetTy; 85 LabelSetTy AddressTakenLabels; 86 87public: 88 explicit CFGBuilder() : cfg(NULL), Block(NULL), Succ(NULL), 89 ContinueTargetBlock(NULL), BreakTargetBlock(NULL), 90 SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL) { 91 // Create an empty CFG. 92 cfg = new CFG(); 93 } 94 95 ~CFGBuilder() { delete cfg; } 96 97 // buildCFG - Used by external clients to construct the CFG. 98 CFG* buildCFG(Stmt *Statement, ASTContext *C); 99 100private: 101 // Visitors to walk an AST and construct the CFG. 102 CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, bool alwaysAdd); 103 CFGBlock *VisitBinaryOperator(BinaryOperator *B, bool alwaysAdd); 104 CFGBlock *VisitBlockExpr(BlockExpr* E, bool alwaysAdd); 105 CFGBlock *VisitBlockDeclRefExpr(BlockDeclRefExpr* E, bool alwaysAdd); 106 CFGBlock *VisitBreakStmt(BreakStmt *B); 107 CFGBlock *VisitCallExpr(CallExpr *C, bool alwaysAdd); 108 CFGBlock *VisitCaseStmt(CaseStmt *C); 109 CFGBlock *VisitChooseExpr(ChooseExpr *C); 110 CFGBlock *VisitCompoundStmt(CompoundStmt *C); 111 CFGBlock *VisitConditionalOperator(ConditionalOperator *C); 112 CFGBlock *VisitContinueStmt(ContinueStmt *C); 113 CFGBlock *VisitDeclStmt(DeclStmt *DS); 114 CFGBlock *VisitDeclSubExpr(Decl* D); 115 CFGBlock *VisitDefaultStmt(DefaultStmt *D); 116 CFGBlock *VisitDoStmt(DoStmt *D); 117 CFGBlock *VisitForStmt(ForStmt *F); 118 CFGBlock *VisitGotoStmt(GotoStmt* G); 119 CFGBlock *VisitIfStmt(IfStmt *I); 120 CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I); 121 CFGBlock *VisitLabelStmt(LabelStmt *L); 122 CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S); 123 CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S); 124 CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S); 125 CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S); 126 CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S); 127 CFGBlock *VisitReturnStmt(ReturnStmt* R); 128 CFGBlock *VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, bool alwaysAdd); 129 CFGBlock *VisitStmtExpr(StmtExpr *S, bool alwaysAdd); 130 CFGBlock *VisitSwitchStmt(SwitchStmt *S); 131 CFGBlock *VisitWhileStmt(WhileStmt *W); 132 133 CFGBlock *Visit(Stmt *S, bool alwaysAdd = false); 134 CFGBlock *VisitStmt(Stmt *S, bool alwaysAdd); 135 CFGBlock *VisitChildren(Stmt* S); 136 137 // NYS == Not Yet Supported 138 CFGBlock* NYS() { 139 badCFG = true; 140 return Block; 141 } 142 143 void autoCreateBlock() { if (!Block) Block = createBlock(); } 144 CFGBlock *createBlock(bool add_successor = true); 145 bool FinishBlock(CFGBlock* B); 146 CFGBlock *addStmt(Stmt *S) { return Visit(S, true); } 147 148 bool badCFG; 149}; 150 151// FIXME: Add support for dependent-sized array types in C++? 152// Does it even make sense to build a CFG for an uninstantiated template? 153static VariableArrayType* FindVA(Type* t) { 154 while (ArrayType* vt = dyn_cast<ArrayType>(t)) { 155 if (VariableArrayType* vat = dyn_cast<VariableArrayType>(vt)) 156 if (vat->getSizeExpr()) 157 return vat; 158 159 t = vt->getElementType().getTypePtr(); 160 } 161 162 return 0; 163} 164 165/// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an 166/// arbitrary statement. Examples include a single expression or a function 167/// body (compound statement). The ownership of the returned CFG is 168/// transferred to the caller. If CFG construction fails, this method returns 169/// NULL. 170CFG* CFGBuilder::buildCFG(Stmt* Statement, ASTContext* C) { 171 Context = C; 172 assert(cfg); 173 if (!Statement) 174 return NULL; 175 176 badCFG = false; 177 178 // Create an empty block that will serve as the exit block for the CFG. Since 179 // this is the first block added to the CFG, it will be implicitly registered 180 // as the exit block. 181 Succ = createBlock(); 182 assert (Succ == &cfg->getExit()); 183 Block = NULL; // the EXIT block is empty. Create all other blocks lazily. 184 185 // Visit the statements and create the CFG. 186 CFGBlock* B = addStmt(Statement); 187 if (!B) B = Succ; 188 189 if (B) { 190 // Finalize the last constructed block. This usually involves reversing the 191 // order of the statements in the block. 192 if (Block) FinishBlock(B); 193 194 // Backpatch the gotos whose label -> block mappings we didn't know when we 195 // encountered them. 196 for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(), 197 E = BackpatchBlocks.end(); I != E; ++I ) { 198 199 CFGBlock* B = *I; 200 GotoStmt* G = cast<GotoStmt>(B->getTerminator()); 201 LabelMapTy::iterator LI = LabelMap.find(G->getLabel()); 202 203 // If there is no target for the goto, then we are looking at an 204 // incomplete AST. Handle this by not registering a successor. 205 if (LI == LabelMap.end()) continue; 206 207 B->addSuccessor(LI->second); 208 } 209 210 // Add successors to the Indirect Goto Dispatch block (if we have one). 211 if (CFGBlock* B = cfg->getIndirectGotoBlock()) 212 for (LabelSetTy::iterator I = AddressTakenLabels.begin(), 213 E = AddressTakenLabels.end(); I != E; ++I ) { 214 215 // Lookup the target block. 216 LabelMapTy::iterator LI = LabelMap.find(*I); 217 218 // If there is no target block that contains label, then we are looking 219 // at an incomplete AST. Handle this by not registering a successor. 220 if (LI == LabelMap.end()) continue; 221 222 B->addSuccessor(LI->second); 223 } 224 225 Succ = B; 226 } 227 228 // Create an empty entry block that has no predecessors. 229 cfg->setEntry(createBlock()); 230 231 if (badCFG) { 232 delete cfg; 233 cfg = NULL; 234 return NULL; 235 } 236 237 // NULL out cfg so that repeated calls to the builder will fail and that the 238 // ownership of the constructed CFG is passed to the caller. 239 CFG* t = cfg; 240 cfg = NULL; 241 return t; 242} 243 244/// createBlock - Used to lazily create blocks that are connected 245/// to the current (global) succcessor. 246CFGBlock* CFGBuilder::createBlock(bool add_successor) { 247 CFGBlock* B = cfg->createBlock(); 248 if (add_successor && Succ) 249 B->addSuccessor(Succ); 250 return B; 251} 252 253/// FinishBlock - When the last statement has been added to the block, we must 254/// reverse the statements because they have been inserted in reverse order. 255bool CFGBuilder::FinishBlock(CFGBlock* B) { 256 if (badCFG) 257 return false; 258 259 assert(B); 260 B->reverseStmts(); 261 return true; 262} 263 264/// Visit - Walk the subtree of a statement and add extra 265/// blocks for ternary operators, &&, and ||. We also process "," and 266/// DeclStmts (which may contain nested control-flow). 267CFGBlock* CFGBuilder::Visit(Stmt * S, bool alwaysAdd) { 268tryAgain: 269 switch (S->getStmtClass()) { 270 default: 271 return VisitStmt(S, alwaysAdd); 272 273 case Stmt::AddrLabelExprClass: 274 return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), alwaysAdd); 275 276 case Stmt::BinaryOperatorClass: 277 return VisitBinaryOperator(cast<BinaryOperator>(S), alwaysAdd); 278 279 case Stmt::BlockExprClass: 280 return VisitBlockExpr(cast<BlockExpr>(S), alwaysAdd); 281 282 case Stmt::BlockDeclRefExprClass: 283 return VisitBlockDeclRefExpr(cast<BlockDeclRefExpr>(S), alwaysAdd); 284 285 case Stmt::BreakStmtClass: 286 return VisitBreakStmt(cast<BreakStmt>(S)); 287 288 case Stmt::CallExprClass: 289 return VisitCallExpr(cast<CallExpr>(S), alwaysAdd); 290 291 case Stmt::CaseStmtClass: 292 return VisitCaseStmt(cast<CaseStmt>(S)); 293 294 case Stmt::ChooseExprClass: 295 return VisitChooseExpr(cast<ChooseExpr>(S)); 296 297 case Stmt::CompoundStmtClass: 298 return VisitCompoundStmt(cast<CompoundStmt>(S)); 299 300 case Stmt::ConditionalOperatorClass: 301 return VisitConditionalOperator(cast<ConditionalOperator>(S)); 302 303 case Stmt::ContinueStmtClass: 304 return VisitContinueStmt(cast<ContinueStmt>(S)); 305 306 case Stmt::DeclStmtClass: 307 return VisitDeclStmt(cast<DeclStmt>(S)); 308 309 case Stmt::DefaultStmtClass: 310 return VisitDefaultStmt(cast<DefaultStmt>(S)); 311 312 case Stmt::DoStmtClass: 313 return VisitDoStmt(cast<DoStmt>(S)); 314 315 case Stmt::ForStmtClass: 316 return VisitForStmt(cast<ForStmt>(S)); 317 318 case Stmt::GotoStmtClass: 319 return VisitGotoStmt(cast<GotoStmt>(S)); 320 321 case Stmt::IfStmtClass: 322 return VisitIfStmt(cast<IfStmt>(S)); 323 324 case Stmt::IndirectGotoStmtClass: 325 return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S)); 326 327 case Stmt::LabelStmtClass: 328 return VisitLabelStmt(cast<LabelStmt>(S)); 329 330 case Stmt::ObjCAtCatchStmtClass: 331 return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S)); 332 333 case Stmt::ObjCAtSynchronizedStmtClass: 334 return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S)); 335 336 case Stmt::ObjCAtThrowStmtClass: 337 return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S)); 338 339 case Stmt::ObjCAtTryStmtClass: 340 return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S)); 341 342 case Stmt::ObjCForCollectionStmtClass: 343 return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S)); 344 345 case Stmt::ParenExprClass: 346 S = cast<ParenExpr>(S)->getSubExpr(); 347 goto tryAgain; 348 349 case Stmt::NullStmtClass: 350 return Block; 351 352 case Stmt::ReturnStmtClass: 353 return VisitReturnStmt(cast<ReturnStmt>(S)); 354 355 case Stmt::SizeOfAlignOfExprClass: 356 return VisitSizeOfAlignOfExpr(cast<SizeOfAlignOfExpr>(S), alwaysAdd); 357 358 case Stmt::StmtExprClass: 359 return VisitStmtExpr(cast<StmtExpr>(S), alwaysAdd); 360 361 case Stmt::SwitchStmtClass: 362 return VisitSwitchStmt(cast<SwitchStmt>(S)); 363 364 case Stmt::WhileStmtClass: 365 return VisitWhileStmt(cast<WhileStmt>(S)); 366 } 367} 368 369CFGBlock *CFGBuilder::VisitStmt(Stmt *S, bool alwaysAdd) { 370 if (alwaysAdd) { 371 autoCreateBlock(); 372 Block->appendStmt(S); 373 } 374 375 return VisitChildren(S); 376} 377 378/// VisitChildren - Visit the children of a Stmt. 379CFGBlock *CFGBuilder::VisitChildren(Stmt* Terminator) { 380 CFGBlock *B = Block; 381 for (Stmt::child_iterator I = Terminator->child_begin(), 382 E = Terminator->child_end(); I != E; ++I) { 383 if (*I) B = Visit(*I); 384 } 385 return B; 386} 387 388CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A, bool alwaysAdd) { 389 AddressTakenLabels.insert(A->getLabel()); 390 391 if (alwaysAdd) { 392 autoCreateBlock(); 393 Block->appendStmt(A); 394 } 395 396 return Block; 397} 398 399CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, bool alwaysAdd) { 400 if (B->isLogicalOp()) { // && or || 401 402 // See if this is a known constant. 403 bool KnownTrue = false; 404 bool KnownFalse = false; 405 Expr::EvalResult Result; 406 if (B->getLHS()->Evaluate(Result, *Context) 407 && Result.Val.isInt()) { 408 if ((B->getOpcode() == BinaryOperator::LAnd) 409 == Result.Val.getInt().getBoolValue()) 410 KnownTrue = true; 411 else 412 KnownFalse = true; 413 } 414 415 CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 416 ConfluenceBlock->appendStmt(B); 417 418 if (!FinishBlock(ConfluenceBlock)) 419 return 0; 420 421 // create the block evaluating the LHS 422 CFGBlock* LHSBlock = createBlock(false); 423 LHSBlock->setTerminator(B); 424 425 // create the block evaluating the RHS 426 Succ = ConfluenceBlock; 427 Block = NULL; 428 CFGBlock* RHSBlock = addStmt(B->getRHS()); 429 if (!FinishBlock(RHSBlock)) 430 return 0; 431 432 // Now link the LHSBlock with RHSBlock. 433 if (B->getOpcode() == BinaryOperator::LOr) { 434 if (KnownTrue) 435 LHSBlock->addSuccessor(0); 436 else 437 LHSBlock->addSuccessor(ConfluenceBlock); 438 if (KnownFalse) 439 LHSBlock->addSuccessor(0); 440 else 441 LHSBlock->addSuccessor(RHSBlock); 442 } else { 443 assert (B->getOpcode() == BinaryOperator::LAnd); 444 if (KnownFalse) 445 LHSBlock->addSuccessor(0); 446 else 447 LHSBlock->addSuccessor(RHSBlock); 448 if (KnownTrue) 449 LHSBlock->addSuccessor(0); 450 else 451 LHSBlock->addSuccessor(ConfluenceBlock); 452 } 453 454 // Generate the blocks for evaluating the LHS. 455 Block = LHSBlock; 456 return addStmt(B->getLHS()); 457 } 458 else if (B->getOpcode() == BinaryOperator::Comma) { // , 459 autoCreateBlock(); 460 Block->appendStmt(B); 461 addStmt(B->getRHS()); 462 return addStmt(B->getLHS()); 463 } 464 465 return VisitStmt(B, alwaysAdd); 466} 467 468CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr* E, bool alwaysAdd) { 469 // FIXME 470 return NYS(); 471} 472 473CFGBlock *CFGBuilder::VisitBlockDeclRefExpr(BlockDeclRefExpr* E, 474 bool alwaysAdd) { 475 // FIXME 476 return NYS(); 477} 478 479CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) { 480 // "break" is a control-flow statement. Thus we stop processing the current 481 // block. 482 if (Block && !FinishBlock(Block)) 483 return 0; 484 485 // Now create a new block that ends with the break statement. 486 Block = createBlock(false); 487 Block->setTerminator(B); 488 489 // If there is no target for the break, then we are looking at an incomplete 490 // AST. This means that the CFG cannot be constructed. 491 if (BreakTargetBlock) 492 Block->addSuccessor(BreakTargetBlock); 493 else 494 badCFG = true; 495 496 497 return Block; 498} 499 500CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, bool alwaysAdd) { 501 // If this is a call to a no-return function, this stops the block here. 502 if (FunctionDecl *FD = C->getDirectCallee()) { 503 504 if (!FD->hasAttr<NoReturnAttr>()) 505 return VisitStmt(C, alwaysAdd); 506 507 if (Block && !FinishBlock(Block)) 508 return 0; 509 510 // Create new block with no successor for the remaining pieces. 511 Block = createBlock(false); 512 Block->appendStmt(C); 513 514 // Wire this to the exit block directly. 515 Block->addSuccessor(&cfg->getExit()); 516 517 return VisitChildren(C); 518 } 519 520 return VisitStmt(C, alwaysAdd); 521} 522 523CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C) { 524 CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 525 ConfluenceBlock->appendStmt(C); 526 if (!FinishBlock(ConfluenceBlock)) 527 return 0; 528 529 Succ = ConfluenceBlock; 530 Block = NULL; 531 CFGBlock* LHSBlock = addStmt(C->getLHS()); 532 if (!FinishBlock(LHSBlock)) 533 return 0; 534 535 Succ = ConfluenceBlock; 536 Block = NULL; 537 CFGBlock* RHSBlock = addStmt(C->getRHS()); 538 if (!FinishBlock(RHSBlock)) 539 return 0; 540 541 Block = createBlock(false); 542 Block->addSuccessor(LHSBlock); 543 Block->addSuccessor(RHSBlock); 544 Block->setTerminator(C); 545 return addStmt(C->getCond()); 546} 547 548 549CFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) { 550 CFGBlock* LastBlock = Block; 551 552 for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); 553 I != E; ++I ) { 554 LastBlock = addStmt(*I); 555 } 556 return LastBlock; 557} 558 559CFGBlock *CFGBuilder::VisitConditionalOperator(ConditionalOperator *C) { 560 // See if this is a known constant. 561 bool KnownTrue = false; 562 bool KnownFalse = false; 563 Expr::EvalResult Result; 564 if (C->getCond()->Evaluate(Result, *Context) 565 && Result.Val.isInt()) { 566 if (Result.Val.getInt().getBoolValue()) 567 KnownTrue = true; 568 else 569 KnownFalse = true; 570 } 571 572 // Create the confluence block that will "merge" the results of the ternary 573 // expression. 574 CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 575 ConfluenceBlock->appendStmt(C); 576 if (!FinishBlock(ConfluenceBlock)) 577 return 0; 578 579 // Create a block for the LHS expression if there is an LHS expression. A 580 // GCC extension allows LHS to be NULL, causing the condition to be the 581 // value that is returned instead. 582 // e.g: x ?: y is shorthand for: x ? x : y; 583 Succ = ConfluenceBlock; 584 Block = NULL; 585 CFGBlock* LHSBlock = NULL; 586 if (C->getLHS()) { 587 LHSBlock = addStmt(C->getLHS()); 588 if (!FinishBlock(LHSBlock)) 589 return 0; 590 Block = NULL; 591 } 592 593 // Create the block for the RHS expression. 594 Succ = ConfluenceBlock; 595 CFGBlock* RHSBlock = addStmt(C->getRHS()); 596 if (!FinishBlock(RHSBlock)) 597 return 0; 598 599 // Create the block that will contain the condition. 600 Block = createBlock(false); 601 602 if (LHSBlock) { 603 if (KnownFalse) 604 Block->addSuccessor(0); 605 else 606 Block->addSuccessor(LHSBlock); 607 } else { 608 if (KnownFalse) { 609 // If we know the condition is false, add NULL as the successor for 610 // the block containing the condition. In this case, the confluence 611 // block will have just one predecessor. 612 Block->addSuccessor(0); 613 assert (ConfluenceBlock->pred_size() == 1); 614 } else { 615 // If we have no LHS expression, add the ConfluenceBlock as a direct 616 // successor for the block containing the condition. Moreover, we need to 617 // reverse the order of the predecessors in the ConfluenceBlock because 618 // the RHSBlock will have been added to the succcessors already, and we 619 // want the first predecessor to the the block containing the expression 620 // for the case when the ternary expression evaluates to true. 621 Block->addSuccessor(ConfluenceBlock); 622 assert (ConfluenceBlock->pred_size() == 2); 623 std::reverse(ConfluenceBlock->pred_begin(), 624 ConfluenceBlock->pred_end()); 625 } 626 } 627 628 if (KnownTrue) 629 Block->addSuccessor(0); 630 else 631 Block->addSuccessor(RHSBlock); 632 633 Block->setTerminator(C); 634 return addStmt(C->getCond()); 635} 636 637CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) { 638 autoCreateBlock(); 639 640 if (DS->isSingleDecl()) { 641 Block->appendStmt(DS); 642 return VisitDeclSubExpr(DS->getSingleDecl()); 643 } 644 645 CFGBlock *B = 0; 646 647 // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy. 648 typedef llvm::SmallVector<Decl*,10> BufTy; 649 BufTy Buf(DS->decl_begin(), DS->decl_end()); 650 651 for (BufTy::reverse_iterator I = Buf.rbegin(), E = Buf.rend(); I != E; ++I) { 652 // Get the alignment of the new DeclStmt, padding out to >=8 bytes. 653 unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8 654 ? 8 : llvm::AlignOf<DeclStmt>::Alignment; 655 656 // Allocate the DeclStmt using the BumpPtrAllocator. It will get 657 // automatically freed with the CFG. 658 DeclGroupRef DG(*I); 659 Decl *D = *I; 660 void *Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A); 661 DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D)); 662 663 // Append the fake DeclStmt to block. 664 Block->appendStmt(DSNew); 665 B = VisitDeclSubExpr(D); 666 } 667 668 return B; 669} 670 671/// VisitDeclSubExpr - Utility method to add block-level expressions for 672/// initializers in Decls. 673CFGBlock *CFGBuilder::VisitDeclSubExpr(Decl* D) { 674 assert(Block); 675 676 VarDecl *VD = dyn_cast<VarDecl>(D); 677 678 if (!VD) 679 return Block; 680 681 Expr *Init = VD->getInit(); 682 683 if (Init) { 684 // Optimization: Don't create separate block-level statements for literals. 685 switch (Init->getStmtClass()) { 686 case Stmt::IntegerLiteralClass: 687 case Stmt::CharacterLiteralClass: 688 case Stmt::StringLiteralClass: 689 break; 690 default: 691 Block = addStmt(Init); 692 } 693 } 694 695 // If the type of VD is a VLA, then we must process its size expressions. 696 for (VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); VA != 0; 697 VA = FindVA(VA->getElementType().getTypePtr())) 698 Block = addStmt(VA->getSizeExpr()); 699 700 return Block; 701} 702 703CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { 704 // See if this is a known constant. 705 bool KnownTrue = false; 706 bool KnownFalse = false; 707 Expr::EvalResult Result; 708 if (I->getCond()->Evaluate(Result, *Context) 709 && Result.Val.isInt()) { 710 if (Result.Val.getInt().getBoolValue()) 711 KnownTrue = true; 712 else 713 KnownFalse = true; 714 } 715 716 // We may see an if statement in the middle of a basic block, or it may be the 717 // first statement we are processing. In either case, we create a new basic 718 // block. First, we create the blocks for the then...else statements, and 719 // then we create the block containing the if statement. If we were in the 720 // middle of a block, we stop processing that block and reverse its 721 // statements. That block is then the implicit successor for the "then" and 722 // "else" clauses. 723 724 // The block we were proccessing is now finished. Make it the successor 725 // block. 726 if (Block) { 727 Succ = Block; 728 if (!FinishBlock(Block)) 729 return 0; 730 } 731 732 // Process the false branch. 733 CFGBlock* ElseBlock = Succ; 734 735 if (Stmt* Else = I->getElse()) { 736 SaveAndRestore<CFGBlock*> sv(Succ); 737 738 // NULL out Block so that the recursive call to Visit will 739 // create a new basic block. 740 Block = NULL; 741 ElseBlock = addStmt(Else); 742 743 if (!ElseBlock) // Can occur when the Else body has all NullStmts. 744 ElseBlock = sv.get(); 745 else if (Block) { 746 if (!FinishBlock(ElseBlock)) 747 return 0; 748 } 749 } 750 751 // Process the true branch. 752 CFGBlock* ThenBlock; 753 { 754 Stmt* Then = I->getThen(); 755 assert (Then); 756 SaveAndRestore<CFGBlock*> sv(Succ); 757 Block = NULL; 758 ThenBlock = addStmt(Then); 759 760 if (!ThenBlock) { 761 // We can reach here if the "then" body has all NullStmts. 762 // Create an empty block so we can distinguish between true and false 763 // branches in path-sensitive analyses. 764 ThenBlock = createBlock(false); 765 ThenBlock->addSuccessor(sv.get()); 766 } else if (Block) { 767 if (!FinishBlock(ThenBlock)) 768 return 0; 769 } 770 } 771 772 // Now create a new block containing the if statement. 773 Block = createBlock(false); 774 775 // Set the terminator of the new block to the If statement. 776 Block->setTerminator(I); 777 778 // Now add the successors. 779 if (KnownFalse) 780 Block->addSuccessor(0); 781 else 782 Block->addSuccessor(ThenBlock); 783 if (KnownTrue) 784 Block->addSuccessor(0); 785 else 786 Block->addSuccessor(ElseBlock); 787 788 // Add the condition as the last statement in the new block. This may create 789 // new blocks as the condition may contain control-flow. Any newly created 790 // blocks will be pointed to be "Block". 791 return addStmt(I->getCond()); 792} 793 794 795CFGBlock* CFGBuilder::VisitReturnStmt(ReturnStmt* R) { 796 // If we were in the middle of a block we stop processing that block and 797 // reverse its statements. 798 // 799 // NOTE: If a "return" appears in the middle of a block, this means that the 800 // code afterwards is DEAD (unreachable). We still keep a basic block 801 // for that code; a simple "mark-and-sweep" from the entry block will be 802 // able to report such dead blocks. 803 if (Block) FinishBlock(Block); 804 805 // Create the new block. 806 Block = createBlock(false); 807 808 // The Exit block is the only successor. 809 Block->addSuccessor(&cfg->getExit()); 810 811 // Add the return statement to the block. This may create new blocks if R 812 // contains control-flow (short-circuit operations). 813 return VisitStmt(R, true); 814} 815 816CFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt* L) { 817 // Get the block of the labeled statement. Add it to our map. 818 addStmt(L->getSubStmt()); 819 CFGBlock* LabelBlock = Block; 820 821 if (!LabelBlock) // This can happen when the body is empty, i.e. 822 LabelBlock = createBlock(); // scopes that only contains NullStmts. 823 824 assert(LabelMap.find(L) == LabelMap.end() && "label already in map"); 825 LabelMap[ L ] = LabelBlock; 826 827 // Labels partition blocks, so this is the end of the basic block we were 828 // processing (L is the block's label). Because this is label (and we have 829 // already processed the substatement) there is no extra control-flow to worry 830 // about. 831 LabelBlock->setLabel(L); 832 if (!FinishBlock(LabelBlock)) 833 return 0; 834 835 // We set Block to NULL to allow lazy creation of a new block (if necessary); 836 Block = NULL; 837 838 // This block is now the implicit successor of other blocks. 839 Succ = LabelBlock; 840 841 return LabelBlock; 842} 843 844CFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) { 845 // Goto is a control-flow statement. Thus we stop processing the current 846 // block and create a new one. 847 if (Block) 848 FinishBlock(Block); 849 850 Block = createBlock(false); 851 Block->setTerminator(G); 852 853 // If we already know the mapping to the label block add the successor now. 854 LabelMapTy::iterator I = LabelMap.find(G->getLabel()); 855 856 if (I == LabelMap.end()) 857 // We will need to backpatch this block later. 858 BackpatchBlocks.push_back(Block); 859 else 860 Block->addSuccessor(I->second); 861 862 return Block; 863} 864 865CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { 866 // See if this is a known constant. 867 bool KnownTrue = false; 868 bool KnownFalse = false; 869 Expr::EvalResult Result; 870 if (F->getCond() && F->getCond()->Evaluate(Result, *Context) 871 && Result.Val.isInt()) { 872 if (Result.Val.getInt().getBoolValue()) 873 KnownTrue = true; 874 else 875 KnownFalse = true; 876 } 877 if (F->getCond() == 0) 878 KnownTrue = true; 879 880 CFGBlock* LoopSuccessor = NULL; 881 882 // "for" is a control-flow statement. Thus we stop processing the current 883 // block. 884 if (Block) { 885 if (!FinishBlock(Block)) 886 return 0; 887 LoopSuccessor = Block; 888 } else 889 LoopSuccessor = Succ; 890 891 // Because of short-circuit evaluation, the condition of the loop can span 892 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 893 // evaluate the condition. 894 CFGBlock* ExitConditionBlock = createBlock(false); 895 CFGBlock* EntryConditionBlock = ExitConditionBlock; 896 897 // Set the terminator for the "exit" condition block. 898 ExitConditionBlock->setTerminator(F); 899 900 // Now add the actual condition to the condition block. Because the condition 901 // itself may contain control-flow, new blocks may be created. 902 if (Stmt* C = F->getCond()) { 903 Block = ExitConditionBlock; 904 EntryConditionBlock = addStmt(C); 905 if (Block) { 906 if (!FinishBlock(EntryConditionBlock)) 907 return 0; 908 } 909 } 910 911 // The condition block is the implicit successor for the loop body as well as 912 // any code above the loop. 913 Succ = EntryConditionBlock; 914 915 // Now create the loop body. 916 { 917 assert (F->getBody()); 918 919 // Save the current values for Block, Succ, and continue and break targets 920 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 921 save_continue(ContinueTargetBlock), 922 save_break(BreakTargetBlock); 923 924 // Create a new block to contain the (bottom) of the loop body. 925 Block = NULL; 926 927 if (Stmt* I = F->getInc()) { 928 // Generate increment code in its own basic block. This is the target of 929 // continue statements. 930 Succ = addStmt(I); 931 } else { 932 // No increment code. Create a special, empty, block that is used as the 933 // target block for "looping back" to the start of the loop. 934 assert(Succ == EntryConditionBlock); 935 Succ = createBlock(); 936 } 937 938 // Finish up the increment (or empty) block if it hasn't been already. 939 if (Block) { 940 assert(Block == Succ); 941 if (!FinishBlock(Block)) 942 return 0; 943 Block = 0; 944 } 945 946 ContinueTargetBlock = Succ; 947 948 // The starting block for the loop increment is the block that should 949 // represent the 'loop target' for looping back to the start of the loop. 950 ContinueTargetBlock->setLoopTarget(F); 951 952 // All breaks should go to the code following the loop. 953 BreakTargetBlock = LoopSuccessor; 954 955 // Now populate the body block, and in the process create new blocks as we 956 // walk the body of the loop. 957 CFGBlock* BodyBlock = addStmt(F->getBody()); 958 959 if (!BodyBlock) 960 BodyBlock = EntryConditionBlock; // can happen for "for (...;...; ) ;" 961 else if (Block) { 962 if (!FinishBlock(BodyBlock)) 963 return 0; 964 } 965 966 if (KnownFalse) 967 ExitConditionBlock->addSuccessor(0); 968 else { 969 // This new body block is a successor to our "exit" condition block. 970 ExitConditionBlock->addSuccessor(BodyBlock); 971 } 972 } 973 974 if (KnownTrue) 975 ExitConditionBlock->addSuccessor(0); 976 else { 977 // Link up the condition block with the code that follows the loop. (the 978 // false branch). 979 ExitConditionBlock->addSuccessor(LoopSuccessor); 980 } 981 982 // If the loop contains initialization, create a new block for those 983 // statements. This block can also contain statements that precede the loop. 984 if (Stmt* I = F->getInit()) { 985 Block = createBlock(); 986 return addStmt(I); 987 } else { 988 // There is no loop initialization. We are thus basically a while loop. 989 // NULL out Block to force lazy block construction. 990 Block = NULL; 991 Succ = EntryConditionBlock; 992 return EntryConditionBlock; 993 } 994} 995 996CFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { 997 // Objective-C fast enumeration 'for' statements: 998 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC 999 // 1000 // for ( Type newVariable in collection_expression ) { statements } 1001 // 1002 // becomes: 1003 // 1004 // prologue: 1005 // 1. collection_expression 1006 // T. jump to loop_entry 1007 // loop_entry: 1008 // 1. side-effects of element expression 1009 // 1. ObjCForCollectionStmt [performs binding to newVariable] 1010 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil] 1011 // TB: 1012 // statements 1013 // T. jump to loop_entry 1014 // FB: 1015 // what comes after 1016 // 1017 // and 1018 // 1019 // Type existingItem; 1020 // for ( existingItem in expression ) { statements } 1021 // 1022 // becomes: 1023 // 1024 // the same with newVariable replaced with existingItem; the binding works 1025 // the same except that for one ObjCForCollectionStmt::getElement() returns 1026 // a DeclStmt and the other returns a DeclRefExpr. 1027 // 1028 1029 CFGBlock* LoopSuccessor = 0; 1030 1031 if (Block) { 1032 if (!FinishBlock(Block)) 1033 return 0; 1034 LoopSuccessor = Block; 1035 Block = 0; 1036 } else 1037 LoopSuccessor = Succ; 1038 1039 // Build the condition blocks. 1040 CFGBlock* ExitConditionBlock = createBlock(false); 1041 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1042 1043 // Set the terminator for the "exit" condition block. 1044 ExitConditionBlock->setTerminator(S); 1045 1046 // The last statement in the block should be the ObjCForCollectionStmt, which 1047 // performs the actual binding to 'element' and determines if there are any 1048 // more items in the collection. 1049 ExitConditionBlock->appendStmt(S); 1050 Block = ExitConditionBlock; 1051 1052 // Walk the 'element' expression to see if there are any side-effects. We 1053 // generate new blocks as necesary. We DON'T add the statement by default to 1054 // the CFG unless it contains control-flow. 1055 EntryConditionBlock = Visit(S->getElement(), false); 1056 if (Block) { 1057 if (!FinishBlock(EntryConditionBlock)) 1058 return 0; 1059 Block = 0; 1060 } 1061 1062 // The condition block is the implicit successor for the loop body as well as 1063 // any code above the loop. 1064 Succ = EntryConditionBlock; 1065 1066 // Now create the true branch. 1067 { 1068 // Save the current values for Succ, continue and break targets. 1069 SaveAndRestore<CFGBlock*> save_Succ(Succ), 1070 save_continue(ContinueTargetBlock), save_break(BreakTargetBlock); 1071 1072 BreakTargetBlock = LoopSuccessor; 1073 ContinueTargetBlock = EntryConditionBlock; 1074 1075 CFGBlock* BodyBlock = addStmt(S->getBody()); 1076 1077 if (!BodyBlock) 1078 BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;" 1079 else if (Block) { 1080 if (!FinishBlock(BodyBlock)) 1081 return 0; 1082 } 1083 1084 // This new body block is a successor to our "exit" condition block. 1085 ExitConditionBlock->addSuccessor(BodyBlock); 1086 } 1087 1088 // Link up the condition block with the code that follows the loop. 1089 // (the false branch). 1090 ExitConditionBlock->addSuccessor(LoopSuccessor); 1091 1092 // Now create a prologue block to contain the collection expression. 1093 Block = createBlock(); 1094 return addStmt(S->getCollection()); 1095} 1096 1097CFGBlock* CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S) { 1098 // FIXME: Add locking 'primitives' to CFG for @synchronized. 1099 1100 // Inline the body. 1101 CFGBlock *SyncBlock = addStmt(S->getSynchBody()); 1102 1103 // The sync body starts its own basic block. This makes it a little easier 1104 // for diagnostic clients. 1105 if (SyncBlock) { 1106 if (!FinishBlock(SyncBlock)) 1107 return 0; 1108 1109 Block = 0; 1110 } 1111 1112 Succ = SyncBlock; 1113 1114 // Inline the sync expression. 1115 return addStmt(S->getSynchExpr()); 1116} 1117 1118CFGBlock* CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt* S) { 1119 // FIXME 1120 return NYS(); 1121} 1122 1123CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { 1124 // See if this is a known constant. 1125 bool KnownTrue = false; 1126 bool KnownFalse = false; 1127 Expr::EvalResult Result; 1128 if (W->getCond()->Evaluate(Result, *Context) 1129 && Result.Val.isInt()) { 1130 if (Result.Val.getInt().getBoolValue()) 1131 KnownTrue = true; 1132 else 1133 KnownFalse = true; 1134 } 1135 1136 CFGBlock* LoopSuccessor = NULL; 1137 1138 // "while" is a control-flow statement. Thus we stop processing the current 1139 // block. 1140 if (Block) { 1141 if (!FinishBlock(Block)) 1142 return 0; 1143 LoopSuccessor = Block; 1144 } else 1145 LoopSuccessor = Succ; 1146 1147 // Because of short-circuit evaluation, the condition of the loop can span 1148 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1149 // evaluate the condition. 1150 CFGBlock* ExitConditionBlock = createBlock(false); 1151 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1152 1153 // Set the terminator for the "exit" condition block. 1154 ExitConditionBlock->setTerminator(W); 1155 1156 // Now add the actual condition to the condition block. Because the condition 1157 // itself may contain control-flow, new blocks may be created. Thus we update 1158 // "Succ" after adding the condition. 1159 if (Stmt* C = W->getCond()) { 1160 Block = ExitConditionBlock; 1161 EntryConditionBlock = addStmt(C); 1162 assert(Block == EntryConditionBlock); 1163 if (Block) { 1164 if (!FinishBlock(EntryConditionBlock)) 1165 return 0; 1166 } 1167 } 1168 1169 // The condition block is the implicit successor for the loop body as well as 1170 // any code above the loop. 1171 Succ = EntryConditionBlock; 1172 1173 // Process the loop body. 1174 { 1175 assert(W->getBody()); 1176 1177 // Save the current values for Block, Succ, and continue and break targets 1178 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1179 save_continue(ContinueTargetBlock), 1180 save_break(BreakTargetBlock); 1181 1182 // Create an empty block to represent the transition block for looping back 1183 // to the head of the loop. 1184 Block = 0; 1185 assert(Succ == EntryConditionBlock); 1186 Succ = createBlock(); 1187 Succ->setLoopTarget(W); 1188 ContinueTargetBlock = Succ; 1189 1190 // All breaks should go to the code following the loop. 1191 BreakTargetBlock = LoopSuccessor; 1192 1193 // NULL out Block to force lazy instantiation of blocks for the body. 1194 Block = NULL; 1195 1196 // Create the body. The returned block is the entry to the loop body. 1197 CFGBlock* BodyBlock = addStmt(W->getBody()); 1198 1199 if (!BodyBlock) 1200 BodyBlock = EntryConditionBlock; // can happen for "while(...) ;" 1201 else if (Block) { 1202 if (!FinishBlock(BodyBlock)) 1203 return 0; 1204 } 1205 1206 if (KnownFalse) 1207 ExitConditionBlock->addSuccessor(0); 1208 else { 1209 // Add the loop body entry as a successor to the condition. 1210 ExitConditionBlock->addSuccessor(BodyBlock); 1211 } 1212 } 1213 1214 if (KnownTrue) 1215 ExitConditionBlock->addSuccessor(0); 1216 else { 1217 // Link up the condition block with the code that follows the loop. (the 1218 // false branch). 1219 ExitConditionBlock->addSuccessor(LoopSuccessor); 1220 } 1221 1222 // There can be no more statements in the condition block since we loop back 1223 // to this block. NULL out Block to force lazy creation of another block. 1224 Block = NULL; 1225 1226 // Return the condition block, which is the dominating block for the loop. 1227 Succ = EntryConditionBlock; 1228 return EntryConditionBlock; 1229} 1230 1231 1232CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt* S) { 1233 // FIXME: For now we pretend that @catch and the code it contains does not 1234 // exit. 1235 return Block; 1236} 1237 1238CFGBlock* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt* S) { 1239 // FIXME: This isn't complete. We basically treat @throw like a return 1240 // statement. 1241 1242 // If we were in the middle of a block we stop processing that block and 1243 // reverse its statements. 1244 if (Block && !FinishBlock(Block)) 1245 return 0; 1246 1247 // Create the new block. 1248 Block = createBlock(false); 1249 1250 // The Exit block is the only successor. 1251 Block->addSuccessor(&cfg->getExit()); 1252 1253 // Add the statement to the block. This may create new blocks if S contains 1254 // control-flow (short-circuit operations). 1255 return VisitStmt(S, true); 1256} 1257 1258CFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) { 1259 // See if this is a known constant. 1260 bool KnownTrue = false; 1261 bool KnownFalse = false; 1262 Expr::EvalResult Result; 1263 if (D->getCond()->Evaluate(Result, *Context) 1264 && Result.Val.isInt()) { 1265 if (Result.Val.getInt().getBoolValue()) 1266 KnownTrue = true; 1267 else 1268 KnownFalse = true; 1269 } 1270 1271 CFGBlock* LoopSuccessor = NULL; 1272 1273 // "do...while" is a control-flow statement. Thus we stop processing the 1274 // current block. 1275 if (Block) { 1276 if (!FinishBlock(Block)) 1277 return 0; 1278 LoopSuccessor = Block; 1279 } else 1280 LoopSuccessor = Succ; 1281 1282 // Because of short-circuit evaluation, the condition of the loop can span 1283 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1284 // evaluate the condition. 1285 CFGBlock* ExitConditionBlock = createBlock(false); 1286 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1287 1288 // Set the terminator for the "exit" condition block. 1289 ExitConditionBlock->setTerminator(D); 1290 1291 // Now add the actual condition to the condition block. Because the condition 1292 // itself may contain control-flow, new blocks may be created. 1293 if (Stmt* C = D->getCond()) { 1294 Block = ExitConditionBlock; 1295 EntryConditionBlock = addStmt(C); 1296 if (Block) { 1297 if (!FinishBlock(EntryConditionBlock)) 1298 return 0; 1299 } 1300 } 1301 1302 // The condition block is the implicit successor for the loop body. 1303 Succ = EntryConditionBlock; 1304 1305 // Process the loop body. 1306 CFGBlock* BodyBlock = NULL; 1307 { 1308 assert (D->getBody()); 1309 1310 // Save the current values for Block, Succ, and continue and break targets 1311 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1312 save_continue(ContinueTargetBlock), 1313 save_break(BreakTargetBlock); 1314 1315 // All continues within this loop should go to the condition block 1316 ContinueTargetBlock = EntryConditionBlock; 1317 1318 // All breaks should go to the code following the loop. 1319 BreakTargetBlock = LoopSuccessor; 1320 1321 // NULL out Block to force lazy instantiation of blocks for the body. 1322 Block = NULL; 1323 1324 // Create the body. The returned block is the entry to the loop body. 1325 BodyBlock = addStmt(D->getBody()); 1326 1327 if (!BodyBlock) 1328 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)" 1329 else if (Block) { 1330 if (!FinishBlock(BodyBlock)) 1331 return 0; 1332 } 1333 1334 // Add an intermediate block between the BodyBlock and the 1335 // ExitConditionBlock to represent the "loop back" transition. Create an 1336 // empty block to represent the transition block for looping back to the 1337 // head of the loop. 1338 // FIXME: Can we do this more efficiently without adding another block? 1339 Block = NULL; 1340 Succ = BodyBlock; 1341 CFGBlock *LoopBackBlock = createBlock(); 1342 LoopBackBlock->setLoopTarget(D); 1343 1344 if (KnownFalse) 1345 ExitConditionBlock->addSuccessor(0); 1346 else { 1347 // Add the loop body entry as a successor to the condition. 1348 ExitConditionBlock->addSuccessor(LoopBackBlock); 1349 } 1350 } 1351 1352 if (KnownTrue) 1353 ExitConditionBlock->addSuccessor(0); 1354 else { 1355 // Link up the condition block with the code that follows the loop. (the 1356 // false branch). 1357 ExitConditionBlock->addSuccessor(LoopSuccessor); 1358 } 1359 1360 // There can be no more statements in the body block(s) since we loop back to 1361 // the body. NULL out Block to force lazy creation of another block. 1362 Block = NULL; 1363 1364 // Return the loop body, which is the dominating block for the loop. 1365 Succ = BodyBlock; 1366 return BodyBlock; 1367} 1368 1369CFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) { 1370 // "continue" is a control-flow statement. Thus we stop processing the 1371 // current block. 1372 if (Block && !FinishBlock(Block)) 1373 return 0; 1374 1375 // Now create a new block that ends with the continue statement. 1376 Block = createBlock(false); 1377 Block->setTerminator(C); 1378 1379 // If there is no target for the continue, then we are looking at an 1380 // incomplete AST. This means the CFG cannot be constructed. 1381 if (ContinueTargetBlock) 1382 Block->addSuccessor(ContinueTargetBlock); 1383 else 1384 badCFG = true; 1385 1386 return Block; 1387} 1388 1389CFGBlock *CFGBuilder::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, 1390 bool alwaysAdd) { 1391 1392 if (alwaysAdd) { 1393 autoCreateBlock(); 1394 Block->appendStmt(E); 1395 } 1396 1397 // VLA types have expressions that must be evaluated. 1398 if (E->isArgumentType()) { 1399 for (VariableArrayType* VA = FindVA(E->getArgumentType().getTypePtr()); 1400 VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) 1401 addStmt(VA->getSizeExpr()); 1402 } 1403 1404 return Block; 1405} 1406 1407/// VisitStmtExpr - Utility method to handle (nested) statement 1408/// expressions (a GCC extension). 1409CFGBlock* CFGBuilder::VisitStmtExpr(StmtExpr *SE, bool alwaysAdd) { 1410 if (alwaysAdd) { 1411 autoCreateBlock(); 1412 Block->appendStmt(SE); 1413 } 1414 return VisitCompoundStmt(SE->getSubStmt()); 1415} 1416 1417CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { 1418 // "switch" is a control-flow statement. Thus we stop processing the current 1419 // block. 1420 CFGBlock* SwitchSuccessor = NULL; 1421 1422 if (Block) { 1423 if (!FinishBlock(Block)) 1424 return 0; 1425 SwitchSuccessor = Block; 1426 } else SwitchSuccessor = Succ; 1427 1428 // Save the current "switch" context. 1429 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock), 1430 save_break(BreakTargetBlock), 1431 save_default(DefaultCaseBlock); 1432 1433 // Set the "default" case to be the block after the switch statement. If the 1434 // switch statement contains a "default:", this value will be overwritten with 1435 // the block for that code. 1436 DefaultCaseBlock = SwitchSuccessor; 1437 1438 // Create a new block that will contain the switch statement. 1439 SwitchTerminatedBlock = createBlock(false); 1440 1441 // Now process the switch body. The code after the switch is the implicit 1442 // successor. 1443 Succ = SwitchSuccessor; 1444 BreakTargetBlock = SwitchSuccessor; 1445 1446 // When visiting the body, the case statements should automatically get linked 1447 // up to the switch. We also don't keep a pointer to the body, since all 1448 // control-flow from the switch goes to case/default statements. 1449 assert (Terminator->getBody() && "switch must contain a non-NULL body"); 1450 Block = NULL; 1451 CFGBlock *BodyBlock = addStmt(Terminator->getBody()); 1452 if (Block) { 1453 if (!FinishBlock(BodyBlock)) 1454 return 0; 1455 } 1456 1457 // If we have no "default:" case, the default transition is to the code 1458 // following the switch body. 1459 SwitchTerminatedBlock->addSuccessor(DefaultCaseBlock); 1460 1461 // Add the terminator and condition in the switch block. 1462 SwitchTerminatedBlock->setTerminator(Terminator); 1463 assert (Terminator->getCond() && "switch condition must be non-NULL"); 1464 Block = SwitchTerminatedBlock; 1465 1466 return addStmt(Terminator->getCond()); 1467} 1468 1469CFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* CS) { 1470 // CaseStmts are essentially labels, so they are the first statement in a 1471 // block. 1472 1473 if (CS->getSubStmt()) 1474 addStmt(CS->getSubStmt()); 1475 1476 CFGBlock* CaseBlock = Block; 1477 if (!CaseBlock) 1478 CaseBlock = createBlock(); 1479 1480 // Cases statements partition blocks, so this is the top of the basic block we 1481 // were processing (the "case XXX:" is the label). 1482 CaseBlock->setLabel(CS); 1483 1484 if (!FinishBlock(CaseBlock)) 1485 return 0; 1486 1487 // Add this block to the list of successors for the block with the switch 1488 // statement. 1489 assert(SwitchTerminatedBlock); 1490 SwitchTerminatedBlock->addSuccessor(CaseBlock); 1491 1492 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1493 Block = NULL; 1494 1495 // This block is now the implicit successor of other blocks. 1496 Succ = CaseBlock; 1497 1498 return CaseBlock; 1499} 1500 1501CFGBlock* CFGBuilder::VisitDefaultStmt(DefaultStmt* Terminator) { 1502 if (Terminator->getSubStmt()) 1503 addStmt(Terminator->getSubStmt()); 1504 1505 DefaultCaseBlock = Block; 1506 1507 if (!DefaultCaseBlock) 1508 DefaultCaseBlock = createBlock(); 1509 1510 // Default statements partition blocks, so this is the top of the basic block 1511 // we were processing (the "default:" is the label). 1512 DefaultCaseBlock->setLabel(Terminator); 1513 1514 if (!FinishBlock(DefaultCaseBlock)) 1515 return 0; 1516 1517 // Unlike case statements, we don't add the default block to the successors 1518 // for the switch statement immediately. This is done when we finish 1519 // processing the switch statement. This allows for the default case 1520 // (including a fall-through to the code after the switch statement) to always 1521 // be the last successor of a switch-terminated block. 1522 1523 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1524 Block = NULL; 1525 1526 // This block is now the implicit successor of other blocks. 1527 Succ = DefaultCaseBlock; 1528 1529 return DefaultCaseBlock; 1530} 1531 1532CFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1533 // Lazily create the indirect-goto dispatch block if there isn't one already. 1534 CFGBlock* IBlock = cfg->getIndirectGotoBlock(); 1535 1536 if (!IBlock) { 1537 IBlock = createBlock(false); 1538 cfg->setIndirectGotoBlock(IBlock); 1539 } 1540 1541 // IndirectGoto is a control-flow statement. Thus we stop processing the 1542 // current block and create a new one. 1543 if (Block && !FinishBlock(Block)) 1544 return 0; 1545 1546 Block = createBlock(false); 1547 Block->setTerminator(I); 1548 Block->addSuccessor(IBlock); 1549 return addStmt(I->getTarget()); 1550} 1551 1552} // end anonymous namespace 1553 1554/// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has 1555/// no successors or predecessors. If this is the first block created in the 1556/// CFG, it is automatically set to be the Entry and Exit of the CFG. 1557CFGBlock* CFG::createBlock() { 1558 bool first_block = begin() == end(); 1559 1560 // Create the block. 1561 Blocks.push_front(CFGBlock(NumBlockIDs++)); 1562 1563 // If this is the first block, set it as the Entry and Exit. 1564 if (first_block) Entry = Exit = &front(); 1565 1566 // Return the block. 1567 return &front(); 1568} 1569 1570/// buildCFG - Constructs a CFG from an AST. Ownership of the returned 1571/// CFG is returned to the caller. 1572CFG* CFG::buildCFG(Stmt* Statement, ASTContext *C) { 1573 CFGBuilder Builder; 1574 return Builder.buildCFG(Statement, C); 1575} 1576 1577/// reverseStmts - Reverses the orders of statements within a CFGBlock. 1578void CFGBlock::reverseStmts() { std::reverse(Stmts.begin(),Stmts.end()); } 1579 1580//===----------------------------------------------------------------------===// 1581// CFG: Queries for BlkExprs. 1582//===----------------------------------------------------------------------===// 1583 1584namespace { 1585 typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy; 1586} 1587 1588static void FindSubExprAssignments(Stmt* Terminator, llvm::SmallPtrSet<Expr*,50>& Set) { 1589 if (!Terminator) 1590 return; 1591 1592 for (Stmt::child_iterator I=Terminator->child_begin(), E=Terminator->child_end(); I!=E; ++I) { 1593 if (!*I) continue; 1594 1595 if (BinaryOperator* B = dyn_cast<BinaryOperator>(*I)) 1596 if (B->isAssignmentOp()) Set.insert(B); 1597 1598 FindSubExprAssignments(*I, Set); 1599 } 1600} 1601 1602static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { 1603 BlkExprMapTy* M = new BlkExprMapTy(); 1604 1605 // Look for assignments that are used as subexpressions. These are the only 1606 // assignments that we want to *possibly* register as a block-level 1607 // expression. Basically, if an assignment occurs both in a subexpression and 1608 // at the block-level, it is a block-level expression. 1609 llvm::SmallPtrSet<Expr*,50> SubExprAssignments; 1610 1611 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) 1612 for (CFGBlock::iterator BI=I->begin(), EI=I->end(); BI != EI; ++BI) 1613 FindSubExprAssignments(*BI, SubExprAssignments); 1614 1615 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { 1616 1617 // Iterate over the statements again on identify the Expr* and Stmt* at the 1618 // block-level that are block-level expressions. 1619 1620 for (CFGBlock::iterator BI=I->begin(), EI=I->end(); BI != EI; ++BI) 1621 if (Expr* Exp = dyn_cast<Expr>(*BI)) { 1622 1623 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { 1624 // Assignment expressions that are not nested within another 1625 // expression are really "statements" whose value is never used by 1626 // another expression. 1627 if (B->isAssignmentOp() && !SubExprAssignments.count(Exp)) 1628 continue; 1629 } else if (const StmtExpr* Terminator = dyn_cast<StmtExpr>(Exp)) { 1630 // Special handling for statement expressions. The last statement in 1631 // the statement expression is also a block-level expr. 1632 const CompoundStmt* C = Terminator->getSubStmt(); 1633 if (!C->body_empty()) { 1634 unsigned x = M->size(); 1635 (*M)[C->body_back()] = x; 1636 } 1637 } 1638 1639 unsigned x = M->size(); 1640 (*M)[Exp] = x; 1641 } 1642 1643 // Look at terminators. The condition is a block-level expression. 1644 1645 Stmt* S = I->getTerminatorCondition(); 1646 1647 if (S && M->find(S) == M->end()) { 1648 unsigned x = M->size(); 1649 (*M)[S] = x; 1650 } 1651 } 1652 1653 return M; 1654} 1655 1656CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt* S) { 1657 assert(S != NULL); 1658 if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); } 1659 1660 BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap); 1661 BlkExprMapTy::iterator I = M->find(S); 1662 1663 if (I == M->end()) return CFG::BlkExprNumTy(); 1664 else return CFG::BlkExprNumTy(I->second); 1665} 1666 1667unsigned CFG::getNumBlkExprs() { 1668 if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap)) 1669 return M->size(); 1670 else { 1671 // We assume callers interested in the number of BlkExprs will want 1672 // the map constructed if it doesn't already exist. 1673 BlkExprMap = (void*) PopulateBlkExprMap(*this); 1674 return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); 1675 } 1676} 1677 1678//===----------------------------------------------------------------------===// 1679// Cleanup: CFG dstor. 1680//===----------------------------------------------------------------------===// 1681 1682CFG::~CFG() { 1683 delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap); 1684} 1685 1686//===----------------------------------------------------------------------===// 1687// CFG pretty printing 1688//===----------------------------------------------------------------------===// 1689 1690namespace { 1691 1692class VISIBILITY_HIDDEN StmtPrinterHelper : public PrinterHelper { 1693 1694 typedef llvm::DenseMap<Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; 1695 StmtMapTy StmtMap; 1696 signed CurrentBlock; 1697 unsigned CurrentStmt; 1698 const LangOptions &LangOpts; 1699public: 1700 1701 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) 1702 : CurrentBlock(0), CurrentStmt(0), LangOpts(LO) { 1703 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { 1704 unsigned j = 1; 1705 for (CFGBlock::const_iterator BI = I->begin(), BEnd = I->end() ; 1706 BI != BEnd; ++BI, ++j ) 1707 StmtMap[*BI] = std::make_pair(I->getBlockID(),j); 1708 } 1709 } 1710 1711 virtual ~StmtPrinterHelper() {} 1712 1713 const LangOptions &getLangOpts() const { return LangOpts; } 1714 void setBlockID(signed i) { CurrentBlock = i; } 1715 void setStmtID(unsigned i) { CurrentStmt = i; } 1716 1717 virtual bool handledStmt(Stmt* Terminator, llvm::raw_ostream& OS) { 1718 1719 StmtMapTy::iterator I = StmtMap.find(Terminator); 1720 1721 if (I == StmtMap.end()) 1722 return false; 1723 1724 if (CurrentBlock >= 0 && I->second.first == (unsigned) CurrentBlock 1725 && I->second.second == CurrentStmt) 1726 return false; 1727 1728 OS << "[B" << I->second.first << "." << I->second.second << "]"; 1729 return true; 1730 } 1731}; 1732} // end anonymous namespace 1733 1734 1735namespace { 1736class VISIBILITY_HIDDEN CFGBlockTerminatorPrint 1737 : public StmtVisitor<CFGBlockTerminatorPrint,void> { 1738 1739 llvm::raw_ostream& OS; 1740 StmtPrinterHelper* Helper; 1741 PrintingPolicy Policy; 1742 1743public: 1744 CFGBlockTerminatorPrint(llvm::raw_ostream& os, StmtPrinterHelper* helper, 1745 const PrintingPolicy &Policy) 1746 : OS(os), Helper(helper), Policy(Policy) {} 1747 1748 void VisitIfStmt(IfStmt* I) { 1749 OS << "if "; 1750 I->getCond()->printPretty(OS,Helper,Policy); 1751 } 1752 1753 // Default case. 1754 void VisitStmt(Stmt* Terminator) { 1755 Terminator->printPretty(OS, Helper, Policy); 1756 } 1757 1758 void VisitForStmt(ForStmt* F) { 1759 OS << "for (" ; 1760 if (F->getInit()) OS << "..."; 1761 OS << "; "; 1762 if (Stmt* C = F->getCond()) C->printPretty(OS, Helper, Policy); 1763 OS << "; "; 1764 if (F->getInc()) OS << "..."; 1765 OS << ")"; 1766 } 1767 1768 void VisitWhileStmt(WhileStmt* W) { 1769 OS << "while " ; 1770 if (Stmt* C = W->getCond()) C->printPretty(OS, Helper, Policy); 1771 } 1772 1773 void VisitDoStmt(DoStmt* D) { 1774 OS << "do ... while "; 1775 if (Stmt* C = D->getCond()) C->printPretty(OS, Helper, Policy); 1776 } 1777 1778 void VisitSwitchStmt(SwitchStmt* Terminator) { 1779 OS << "switch "; 1780 Terminator->getCond()->printPretty(OS, Helper, Policy); 1781 } 1782 1783 void VisitConditionalOperator(ConditionalOperator* C) { 1784 C->getCond()->printPretty(OS, Helper, Policy); 1785 OS << " ? ... : ..."; 1786 } 1787 1788 void VisitChooseExpr(ChooseExpr* C) { 1789 OS << "__builtin_choose_expr( "; 1790 C->getCond()->printPretty(OS, Helper, Policy); 1791 OS << " )"; 1792 } 1793 1794 void VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1795 OS << "goto *"; 1796 I->getTarget()->printPretty(OS, Helper, Policy); 1797 } 1798 1799 void VisitBinaryOperator(BinaryOperator* B) { 1800 if (!B->isLogicalOp()) { 1801 VisitExpr(B); 1802 return; 1803 } 1804 1805 B->getLHS()->printPretty(OS, Helper, Policy); 1806 1807 switch (B->getOpcode()) { 1808 case BinaryOperator::LOr: 1809 OS << " || ..."; 1810 return; 1811 case BinaryOperator::LAnd: 1812 OS << " && ..."; 1813 return; 1814 default: 1815 assert(false && "Invalid logical operator."); 1816 } 1817 } 1818 1819 void VisitExpr(Expr* E) { 1820 E->printPretty(OS, Helper, Policy); 1821 } 1822}; 1823} // end anonymous namespace 1824 1825 1826static void print_stmt(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, 1827 Stmt* Terminator) { 1828 if (Helper) { 1829 // special printing for statement-expressions. 1830 if (StmtExpr* SE = dyn_cast<StmtExpr>(Terminator)) { 1831 CompoundStmt* Sub = SE->getSubStmt(); 1832 1833 if (Sub->child_begin() != Sub->child_end()) { 1834 OS << "({ ... ; "; 1835 Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); 1836 OS << " })\n"; 1837 return; 1838 } 1839 } 1840 1841 // special printing for comma expressions. 1842 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Terminator)) { 1843 if (B->getOpcode() == BinaryOperator::Comma) { 1844 OS << "... , "; 1845 Helper->handledStmt(B->getRHS(),OS); 1846 OS << '\n'; 1847 return; 1848 } 1849 } 1850 } 1851 1852 Terminator->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 1853 1854 // Expressions need a newline. 1855 if (isa<Expr>(Terminator)) OS << '\n'; 1856} 1857 1858static void print_block(llvm::raw_ostream& OS, const CFG* cfg, 1859 const CFGBlock& B, 1860 StmtPrinterHelper* Helper, bool print_edges) { 1861 1862 if (Helper) Helper->setBlockID(B.getBlockID()); 1863 1864 // Print the header. 1865 OS << "\n [ B" << B.getBlockID(); 1866 1867 if (&B == &cfg->getEntry()) 1868 OS << " (ENTRY) ]\n"; 1869 else if (&B == &cfg->getExit()) 1870 OS << " (EXIT) ]\n"; 1871 else if (&B == cfg->getIndirectGotoBlock()) 1872 OS << " (INDIRECT GOTO DISPATCH) ]\n"; 1873 else 1874 OS << " ]\n"; 1875 1876 // Print the label of this block. 1877 if (Stmt* Terminator = const_cast<Stmt*>(B.getLabel())) { 1878 1879 if (print_edges) 1880 OS << " "; 1881 1882 if (LabelStmt* L = dyn_cast<LabelStmt>(Terminator)) 1883 OS << L->getName(); 1884 else if (CaseStmt* C = dyn_cast<CaseStmt>(Terminator)) { 1885 OS << "case "; 1886 C->getLHS()->printPretty(OS, Helper, 1887 PrintingPolicy(Helper->getLangOpts())); 1888 if (C->getRHS()) { 1889 OS << " ... "; 1890 C->getRHS()->printPretty(OS, Helper, 1891 PrintingPolicy(Helper->getLangOpts())); 1892 } 1893 } else if (isa<DefaultStmt>(Terminator)) 1894 OS << "default"; 1895 else 1896 assert(false && "Invalid label statement in CFGBlock."); 1897 1898 OS << ":\n"; 1899 } 1900 1901 // Iterate through the statements in the block and print them. 1902 unsigned j = 1; 1903 1904 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; 1905 I != E ; ++I, ++j ) { 1906 1907 // Print the statement # in the basic block and the statement itself. 1908 if (print_edges) 1909 OS << " "; 1910 1911 OS << llvm::format("%3d", j) << ": "; 1912 1913 if (Helper) 1914 Helper->setStmtID(j); 1915 1916 print_stmt(OS,Helper,*I); 1917 } 1918 1919 // Print the terminator of this block. 1920 if (B.getTerminator()) { 1921 if (print_edges) 1922 OS << " "; 1923 1924 OS << " T: "; 1925 1926 if (Helper) Helper->setBlockID(-1); 1927 1928 CFGBlockTerminatorPrint TPrinter(OS, Helper, 1929 PrintingPolicy(Helper->getLangOpts())); 1930 TPrinter.Visit(const_cast<Stmt*>(B.getTerminator())); 1931 OS << '\n'; 1932 } 1933 1934 if (print_edges) { 1935 // Print the predecessors of this block. 1936 OS << " Predecessors (" << B.pred_size() << "):"; 1937 unsigned i = 0; 1938 1939 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); 1940 I != E; ++I, ++i) { 1941 1942 if (i == 8 || (i-8) == 0) 1943 OS << "\n "; 1944 1945 OS << " B" << (*I)->getBlockID(); 1946 } 1947 1948 OS << '\n'; 1949 1950 // Print the successors of this block. 1951 OS << " Successors (" << B.succ_size() << "):"; 1952 i = 0; 1953 1954 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); 1955 I != E; ++I, ++i) { 1956 1957 if (i == 8 || (i-8) % 10 == 0) 1958 OS << "\n "; 1959 1960 if (*I) 1961 OS << " B" << (*I)->getBlockID(); 1962 else 1963 OS << " NULL"; 1964 } 1965 1966 OS << '\n'; 1967 } 1968} 1969 1970 1971/// dump - A simple pretty printer of a CFG that outputs to stderr. 1972void CFG::dump(const LangOptions &LO) const { print(llvm::errs(), LO); } 1973 1974/// print - A simple pretty printer of a CFG that outputs to an ostream. 1975void CFG::print(llvm::raw_ostream &OS, const LangOptions &LO) const { 1976 StmtPrinterHelper Helper(this, LO); 1977 1978 // Print the entry block. 1979 print_block(OS, this, getEntry(), &Helper, true); 1980 1981 // Iterate through the CFGBlocks and print them one by one. 1982 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { 1983 // Skip the entry block, because we already printed it. 1984 if (&(*I) == &getEntry() || &(*I) == &getExit()) 1985 continue; 1986 1987 print_block(OS, this, *I, &Helper, true); 1988 } 1989 1990 // Print the exit block. 1991 print_block(OS, this, getExit(), &Helper, true); 1992 OS.flush(); 1993} 1994 1995/// dump - A simply pretty printer of a CFGBlock that outputs to stderr. 1996void CFGBlock::dump(const CFG* cfg, const LangOptions &LO) const { 1997 print(llvm::errs(), cfg, LO); 1998} 1999 2000/// print - A simple pretty printer of a CFGBlock that outputs to an ostream. 2001/// Generally this will only be called from CFG::print. 2002void CFGBlock::print(llvm::raw_ostream& OS, const CFG* cfg, 2003 const LangOptions &LO) const { 2004 StmtPrinterHelper Helper(cfg, LO); 2005 print_block(OS, cfg, *this, &Helper, true); 2006} 2007 2008/// printTerminator - A simple pretty printer of the terminator of a CFGBlock. 2009void CFGBlock::printTerminator(llvm::raw_ostream &OS, 2010 const LangOptions &LO) const { 2011 CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO)); 2012 TPrinter.Visit(const_cast<Stmt*>(getTerminator())); 2013} 2014 2015Stmt* CFGBlock::getTerminatorCondition() { 2016 2017 if (!Terminator) 2018 return NULL; 2019 2020 Expr* E = NULL; 2021 2022 switch (Terminator->getStmtClass()) { 2023 default: 2024 break; 2025 2026 case Stmt::ForStmtClass: 2027 E = cast<ForStmt>(Terminator)->getCond(); 2028 break; 2029 2030 case Stmt::WhileStmtClass: 2031 E = cast<WhileStmt>(Terminator)->getCond(); 2032 break; 2033 2034 case Stmt::DoStmtClass: 2035 E = cast<DoStmt>(Terminator)->getCond(); 2036 break; 2037 2038 case Stmt::IfStmtClass: 2039 E = cast<IfStmt>(Terminator)->getCond(); 2040 break; 2041 2042 case Stmt::ChooseExprClass: 2043 E = cast<ChooseExpr>(Terminator)->getCond(); 2044 break; 2045 2046 case Stmt::IndirectGotoStmtClass: 2047 E = cast<IndirectGotoStmt>(Terminator)->getTarget(); 2048 break; 2049 2050 case Stmt::SwitchStmtClass: 2051 E = cast<SwitchStmt>(Terminator)->getCond(); 2052 break; 2053 2054 case Stmt::ConditionalOperatorClass: 2055 E = cast<ConditionalOperator>(Terminator)->getCond(); 2056 break; 2057 2058 case Stmt::BinaryOperatorClass: // '&&' and '||' 2059 E = cast<BinaryOperator>(Terminator)->getLHS(); 2060 break; 2061 2062 case Stmt::ObjCForCollectionStmtClass: 2063 return Terminator; 2064 } 2065 2066 return E ? E->IgnoreParens() : NULL; 2067} 2068 2069bool CFGBlock::hasBinaryBranchTerminator() const { 2070 2071 if (!Terminator) 2072 return false; 2073 2074 Expr* E = NULL; 2075 2076 switch (Terminator->getStmtClass()) { 2077 default: 2078 return false; 2079 2080 case Stmt::ForStmtClass: 2081 case Stmt::WhileStmtClass: 2082 case Stmt::DoStmtClass: 2083 case Stmt::IfStmtClass: 2084 case Stmt::ChooseExprClass: 2085 case Stmt::ConditionalOperatorClass: 2086 case Stmt::BinaryOperatorClass: 2087 return true; 2088 } 2089 2090 return E ? E->IgnoreParens() : NULL; 2091} 2092 2093 2094//===----------------------------------------------------------------------===// 2095// CFG Graphviz Visualization 2096//===----------------------------------------------------------------------===// 2097 2098 2099#ifndef NDEBUG 2100static StmtPrinterHelper* GraphHelper; 2101#endif 2102 2103void CFG::viewCFG(const LangOptions &LO) const { 2104#ifndef NDEBUG 2105 StmtPrinterHelper H(this, LO); 2106 GraphHelper = &H; 2107 llvm::ViewGraph(this,"CFG"); 2108 GraphHelper = NULL; 2109#endif 2110} 2111 2112namespace llvm { 2113template<> 2114struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { 2115 static std::string getNodeLabel(const CFGBlock* Node, const CFG* Graph, 2116 bool ShortNames) { 2117 2118#ifndef NDEBUG 2119 std::string OutSStr; 2120 llvm::raw_string_ostream Out(OutSStr); 2121 print_block(Out,Graph, *Node, GraphHelper, false); 2122 std::string& OutStr = Out.str(); 2123 2124 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); 2125 2126 // Process string output to make it nicer... 2127 for (unsigned i = 0; i != OutStr.length(); ++i) 2128 if (OutStr[i] == '\n') { // Left justify 2129 OutStr[i] = '\\'; 2130 OutStr.insert(OutStr.begin()+i+1, 'l'); 2131 } 2132 2133 return OutStr; 2134#else 2135 return ""; 2136#endif 2137 } 2138}; 2139} // end namespace llvm 2140