CFG.cpp revision 22cd6581188bbbc6bedaca64ab171b1187a1c06a
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 // See if this is a known constant. 525 bool KnownTrue = false; 526 bool KnownFalse = false; 527 Expr::EvalResult Result; 528 if (C->getCond()->Evaluate(Result, *Context) 529 && Result.Val.isInt()) { 530 if (Result.Val.getInt().getBoolValue()) 531 KnownTrue = true; 532 else 533 KnownFalse = true; 534 } 535 536 CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 537 ConfluenceBlock->appendStmt(C); 538 if (!FinishBlock(ConfluenceBlock)) 539 return 0; 540 541 Succ = ConfluenceBlock; 542 Block = NULL; 543 CFGBlock* LHSBlock = addStmt(C->getLHS()); 544 if (!FinishBlock(LHSBlock)) 545 return 0; 546 547 Succ = ConfluenceBlock; 548 Block = NULL; 549 CFGBlock* RHSBlock = addStmt(C->getRHS()); 550 if (!FinishBlock(RHSBlock)) 551 return 0; 552 553 Block = createBlock(false); 554 if (KnownFalse) 555 Block->addSuccessor(0); 556 else 557 Block->addSuccessor(LHSBlock); 558 if (KnownTrue) 559 Block->addSuccessor(0); 560 else 561 Block->addSuccessor(RHSBlock); 562 Block->setTerminator(C); 563 return addStmt(C->getCond()); 564} 565 566 567CFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) { 568 CFGBlock* LastBlock = Block; 569 570 for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); 571 I != E; ++I ) { 572 LastBlock = addStmt(*I); 573 } 574 return LastBlock; 575} 576 577CFGBlock *CFGBuilder::VisitConditionalOperator(ConditionalOperator *C) { 578 // See if this is a known constant. 579 bool KnownTrue = false; 580 bool KnownFalse = false; 581 Expr::EvalResult Result; 582 if (C->getCond()->Evaluate(Result, *Context) 583 && Result.Val.isInt()) { 584 if (Result.Val.getInt().getBoolValue()) 585 KnownTrue = true; 586 else 587 KnownFalse = true; 588 } 589 590 // Create the confluence block that will "merge" the results of the ternary 591 // expression. 592 CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); 593 ConfluenceBlock->appendStmt(C); 594 if (!FinishBlock(ConfluenceBlock)) 595 return 0; 596 597 // Create a block for the LHS expression if there is an LHS expression. A 598 // GCC extension allows LHS to be NULL, causing the condition to be the 599 // value that is returned instead. 600 // e.g: x ?: y is shorthand for: x ? x : y; 601 Succ = ConfluenceBlock; 602 Block = NULL; 603 CFGBlock* LHSBlock = NULL; 604 if (C->getLHS()) { 605 LHSBlock = addStmt(C->getLHS()); 606 if (!FinishBlock(LHSBlock)) 607 return 0; 608 Block = NULL; 609 } 610 611 // Create the block for the RHS expression. 612 Succ = ConfluenceBlock; 613 CFGBlock* RHSBlock = addStmt(C->getRHS()); 614 if (!FinishBlock(RHSBlock)) 615 return 0; 616 617 // Create the block that will contain the condition. 618 Block = createBlock(false); 619 620 if (LHSBlock) { 621 if (KnownFalse) 622 Block->addSuccessor(0); 623 else 624 Block->addSuccessor(LHSBlock); 625 } else { 626 if (KnownFalse) { 627 // If we know the condition is false, add NULL as the successor for 628 // the block containing the condition. In this case, the confluence 629 // block will have just one predecessor. 630 Block->addSuccessor(0); 631 assert (ConfluenceBlock->pred_size() == 1); 632 } else { 633 // If we have no LHS expression, add the ConfluenceBlock as a direct 634 // successor for the block containing the condition. Moreover, we need to 635 // reverse the order of the predecessors in the ConfluenceBlock because 636 // the RHSBlock will have been added to the succcessors already, and we 637 // want the first predecessor to the the block containing the expression 638 // for the case when the ternary expression evaluates to true. 639 Block->addSuccessor(ConfluenceBlock); 640 assert (ConfluenceBlock->pred_size() == 2); 641 std::reverse(ConfluenceBlock->pred_begin(), 642 ConfluenceBlock->pred_end()); 643 } 644 } 645 646 if (KnownTrue) 647 Block->addSuccessor(0); 648 else 649 Block->addSuccessor(RHSBlock); 650 651 Block->setTerminator(C); 652 return addStmt(C->getCond()); 653} 654 655CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) { 656 autoCreateBlock(); 657 658 if (DS->isSingleDecl()) { 659 Block->appendStmt(DS); 660 return VisitDeclSubExpr(DS->getSingleDecl()); 661 } 662 663 CFGBlock *B = 0; 664 665 // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy. 666 typedef llvm::SmallVector<Decl*,10> BufTy; 667 BufTy Buf(DS->decl_begin(), DS->decl_end()); 668 669 for (BufTy::reverse_iterator I = Buf.rbegin(), E = Buf.rend(); I != E; ++I) { 670 // Get the alignment of the new DeclStmt, padding out to >=8 bytes. 671 unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8 672 ? 8 : llvm::AlignOf<DeclStmt>::Alignment; 673 674 // Allocate the DeclStmt using the BumpPtrAllocator. It will get 675 // automatically freed with the CFG. 676 DeclGroupRef DG(*I); 677 Decl *D = *I; 678 void *Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A); 679 DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D)); 680 681 // Append the fake DeclStmt to block. 682 Block->appendStmt(DSNew); 683 B = VisitDeclSubExpr(D); 684 } 685 686 return B; 687} 688 689/// VisitDeclSubExpr - Utility method to add block-level expressions for 690/// initializers in Decls. 691CFGBlock *CFGBuilder::VisitDeclSubExpr(Decl* D) { 692 assert(Block); 693 694 VarDecl *VD = dyn_cast<VarDecl>(D); 695 696 if (!VD) 697 return Block; 698 699 Expr *Init = VD->getInit(); 700 701 if (Init) { 702 // Optimization: Don't create separate block-level statements for literals. 703 switch (Init->getStmtClass()) { 704 case Stmt::IntegerLiteralClass: 705 case Stmt::CharacterLiteralClass: 706 case Stmt::StringLiteralClass: 707 break; 708 default: 709 Block = addStmt(Init); 710 } 711 } 712 713 // If the type of VD is a VLA, then we must process its size expressions. 714 for (VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); VA != 0; 715 VA = FindVA(VA->getElementType().getTypePtr())) 716 Block = addStmt(VA->getSizeExpr()); 717 718 return Block; 719} 720 721CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { 722 // See if this is a known constant. 723 bool KnownTrue = false; 724 bool KnownFalse = false; 725 Expr::EvalResult Result; 726 if (I->getCond()->Evaluate(Result, *Context) 727 && Result.Val.isInt()) { 728 if (Result.Val.getInt().getBoolValue()) 729 KnownTrue = true; 730 else 731 KnownFalse = true; 732 } 733 734 // We may see an if statement in the middle of a basic block, or it may be the 735 // first statement we are processing. In either case, we create a new basic 736 // block. First, we create the blocks for the then...else statements, and 737 // then we create the block containing the if statement. If we were in the 738 // middle of a block, we stop processing that block and reverse its 739 // statements. That block is then the implicit successor for the "then" and 740 // "else" clauses. 741 742 // The block we were proccessing is now finished. Make it the successor 743 // block. 744 if (Block) { 745 Succ = Block; 746 if (!FinishBlock(Block)) 747 return 0; 748 } 749 750 // Process the false branch. 751 CFGBlock* ElseBlock = Succ; 752 753 if (Stmt* Else = I->getElse()) { 754 SaveAndRestore<CFGBlock*> sv(Succ); 755 756 // NULL out Block so that the recursive call to Visit will 757 // create a new basic block. 758 Block = NULL; 759 ElseBlock = addStmt(Else); 760 761 if (!ElseBlock) // Can occur when the Else body has all NullStmts. 762 ElseBlock = sv.get(); 763 else if (Block) { 764 if (!FinishBlock(ElseBlock)) 765 return 0; 766 } 767 } 768 769 // Process the true branch. 770 CFGBlock* ThenBlock; 771 { 772 Stmt* Then = I->getThen(); 773 assert (Then); 774 SaveAndRestore<CFGBlock*> sv(Succ); 775 Block = NULL; 776 ThenBlock = addStmt(Then); 777 778 if (!ThenBlock) { 779 // We can reach here if the "then" body has all NullStmts. 780 // Create an empty block so we can distinguish between true and false 781 // branches in path-sensitive analyses. 782 ThenBlock = createBlock(false); 783 ThenBlock->addSuccessor(sv.get()); 784 } else if (Block) { 785 if (!FinishBlock(ThenBlock)) 786 return 0; 787 } 788 } 789 790 // Now create a new block containing the if statement. 791 Block = createBlock(false); 792 793 // Set the terminator of the new block to the If statement. 794 Block->setTerminator(I); 795 796 // Now add the successors. 797 if (KnownFalse) 798 Block->addSuccessor(0); 799 else 800 Block->addSuccessor(ThenBlock); 801 if (KnownTrue) 802 Block->addSuccessor(0); 803 else 804 Block->addSuccessor(ElseBlock); 805 806 // Add the condition as the last statement in the new block. This may create 807 // new blocks as the condition may contain control-flow. Any newly created 808 // blocks will be pointed to be "Block". 809 return addStmt(I->getCond()); 810} 811 812 813CFGBlock* CFGBuilder::VisitReturnStmt(ReturnStmt* R) { 814 // If we were in the middle of a block we stop processing that block and 815 // reverse its statements. 816 // 817 // NOTE: If a "return" appears in the middle of a block, this means that the 818 // code afterwards is DEAD (unreachable). We still keep a basic block 819 // for that code; a simple "mark-and-sweep" from the entry block will be 820 // able to report such dead blocks. 821 if (Block) FinishBlock(Block); 822 823 // Create the new block. 824 Block = createBlock(false); 825 826 // The Exit block is the only successor. 827 Block->addSuccessor(&cfg->getExit()); 828 829 // Add the return statement to the block. This may create new blocks if R 830 // contains control-flow (short-circuit operations). 831 return VisitStmt(R, true); 832} 833 834CFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt* L) { 835 // Get the block of the labeled statement. Add it to our map. 836 addStmt(L->getSubStmt()); 837 CFGBlock* LabelBlock = Block; 838 839 if (!LabelBlock) // This can happen when the body is empty, i.e. 840 LabelBlock = createBlock(); // scopes that only contains NullStmts. 841 842 assert(LabelMap.find(L) == LabelMap.end() && "label already in map"); 843 LabelMap[ L ] = LabelBlock; 844 845 // Labels partition blocks, so this is the end of the basic block we were 846 // processing (L is the block's label). Because this is label (and we have 847 // already processed the substatement) there is no extra control-flow to worry 848 // about. 849 LabelBlock->setLabel(L); 850 if (!FinishBlock(LabelBlock)) 851 return 0; 852 853 // We set Block to NULL to allow lazy creation of a new block (if necessary); 854 Block = NULL; 855 856 // This block is now the implicit successor of other blocks. 857 Succ = LabelBlock; 858 859 return LabelBlock; 860} 861 862CFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) { 863 // Goto is a control-flow statement. Thus we stop processing the current 864 // block and create a new one. 865 if (Block) 866 FinishBlock(Block); 867 868 Block = createBlock(false); 869 Block->setTerminator(G); 870 871 // If we already know the mapping to the label block add the successor now. 872 LabelMapTy::iterator I = LabelMap.find(G->getLabel()); 873 874 if (I == LabelMap.end()) 875 // We will need to backpatch this block later. 876 BackpatchBlocks.push_back(Block); 877 else 878 Block->addSuccessor(I->second); 879 880 return Block; 881} 882 883CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { 884 // See if this is a known constant. 885 bool KnownTrue = false; 886 bool KnownFalse = false; 887 Expr::EvalResult Result; 888 if (F->getCond() && F->getCond()->Evaluate(Result, *Context) 889 && Result.Val.isInt()) { 890 if (Result.Val.getInt().getBoolValue()) 891 KnownTrue = true; 892 else 893 KnownFalse = true; 894 } 895 if (F->getCond() == 0) 896 KnownTrue = true; 897 898 CFGBlock* LoopSuccessor = NULL; 899 900 // "for" is a control-flow statement. Thus we stop processing the current 901 // block. 902 if (Block) { 903 if (!FinishBlock(Block)) 904 return 0; 905 LoopSuccessor = Block; 906 } else 907 LoopSuccessor = Succ; 908 909 // Because of short-circuit evaluation, the condition of the loop can span 910 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 911 // evaluate the condition. 912 CFGBlock* ExitConditionBlock = createBlock(false); 913 CFGBlock* EntryConditionBlock = ExitConditionBlock; 914 915 // Set the terminator for the "exit" condition block. 916 ExitConditionBlock->setTerminator(F); 917 918 // Now add the actual condition to the condition block. Because the condition 919 // itself may contain control-flow, new blocks may be created. 920 if (Stmt* C = F->getCond()) { 921 Block = ExitConditionBlock; 922 EntryConditionBlock = addStmt(C); 923 if (Block) { 924 if (!FinishBlock(EntryConditionBlock)) 925 return 0; 926 } 927 } 928 929 // The condition block is the implicit successor for the loop body as well as 930 // any code above the loop. 931 Succ = EntryConditionBlock; 932 933 // Now create the loop body. 934 { 935 assert (F->getBody()); 936 937 // Save the current values for Block, Succ, and continue and break targets 938 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 939 save_continue(ContinueTargetBlock), 940 save_break(BreakTargetBlock); 941 942 // Create a new block to contain the (bottom) of the loop body. 943 Block = NULL; 944 945 if (Stmt* I = F->getInc()) { 946 // Generate increment code in its own basic block. This is the target of 947 // continue statements. 948 Succ = addStmt(I); 949 } else { 950 // No increment code. Create a special, empty, block that is used as the 951 // target block for "looping back" to the start of the loop. 952 assert(Succ == EntryConditionBlock); 953 Succ = createBlock(); 954 } 955 956 // Finish up the increment (or empty) block if it hasn't been already. 957 if (Block) { 958 assert(Block == Succ); 959 if (!FinishBlock(Block)) 960 return 0; 961 Block = 0; 962 } 963 964 ContinueTargetBlock = Succ; 965 966 // The starting block for the loop increment is the block that should 967 // represent the 'loop target' for looping back to the start of the loop. 968 ContinueTargetBlock->setLoopTarget(F); 969 970 // All breaks should go to the code following the loop. 971 BreakTargetBlock = LoopSuccessor; 972 973 // Now populate the body block, and in the process create new blocks as we 974 // walk the body of the loop. 975 CFGBlock* BodyBlock = addStmt(F->getBody()); 976 977 if (!BodyBlock) 978 BodyBlock = EntryConditionBlock; // can happen for "for (...;...; ) ;" 979 else if (Block) { 980 if (!FinishBlock(BodyBlock)) 981 return 0; 982 } 983 984 if (KnownFalse) 985 ExitConditionBlock->addSuccessor(0); 986 else { 987 // This new body block is a successor to our "exit" condition block. 988 ExitConditionBlock->addSuccessor(BodyBlock); 989 } 990 } 991 992 if (KnownTrue) 993 ExitConditionBlock->addSuccessor(0); 994 else { 995 // Link up the condition block with the code that follows the loop. (the 996 // false branch). 997 ExitConditionBlock->addSuccessor(LoopSuccessor); 998 } 999 1000 // If the loop contains initialization, create a new block for those 1001 // statements. This block can also contain statements that precede the loop. 1002 if (Stmt* I = F->getInit()) { 1003 Block = createBlock(); 1004 return addStmt(I); 1005 } else { 1006 // There is no loop initialization. We are thus basically a while loop. 1007 // NULL out Block to force lazy block construction. 1008 Block = NULL; 1009 Succ = EntryConditionBlock; 1010 return EntryConditionBlock; 1011 } 1012} 1013 1014CFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { 1015 // Objective-C fast enumeration 'for' statements: 1016 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC 1017 // 1018 // for ( Type newVariable in collection_expression ) { statements } 1019 // 1020 // becomes: 1021 // 1022 // prologue: 1023 // 1. collection_expression 1024 // T. jump to loop_entry 1025 // loop_entry: 1026 // 1. side-effects of element expression 1027 // 1. ObjCForCollectionStmt [performs binding to newVariable] 1028 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil] 1029 // TB: 1030 // statements 1031 // T. jump to loop_entry 1032 // FB: 1033 // what comes after 1034 // 1035 // and 1036 // 1037 // Type existingItem; 1038 // for ( existingItem in expression ) { statements } 1039 // 1040 // becomes: 1041 // 1042 // the same with newVariable replaced with existingItem; the binding works 1043 // the same except that for one ObjCForCollectionStmt::getElement() returns 1044 // a DeclStmt and the other returns a DeclRefExpr. 1045 // 1046 1047 CFGBlock* LoopSuccessor = 0; 1048 1049 if (Block) { 1050 if (!FinishBlock(Block)) 1051 return 0; 1052 LoopSuccessor = Block; 1053 Block = 0; 1054 } else 1055 LoopSuccessor = Succ; 1056 1057 // Build the condition blocks. 1058 CFGBlock* ExitConditionBlock = createBlock(false); 1059 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1060 1061 // Set the terminator for the "exit" condition block. 1062 ExitConditionBlock->setTerminator(S); 1063 1064 // The last statement in the block should be the ObjCForCollectionStmt, which 1065 // performs the actual binding to 'element' and determines if there are any 1066 // more items in the collection. 1067 ExitConditionBlock->appendStmt(S); 1068 Block = ExitConditionBlock; 1069 1070 // Walk the 'element' expression to see if there are any side-effects. We 1071 // generate new blocks as necesary. We DON'T add the statement by default to 1072 // the CFG unless it contains control-flow. 1073 EntryConditionBlock = Visit(S->getElement(), false); 1074 if (Block) { 1075 if (!FinishBlock(EntryConditionBlock)) 1076 return 0; 1077 Block = 0; 1078 } 1079 1080 // The condition block is the implicit successor for the loop body as well as 1081 // any code above the loop. 1082 Succ = EntryConditionBlock; 1083 1084 // Now create the true branch. 1085 { 1086 // Save the current values for Succ, continue and break targets. 1087 SaveAndRestore<CFGBlock*> save_Succ(Succ), 1088 save_continue(ContinueTargetBlock), save_break(BreakTargetBlock); 1089 1090 BreakTargetBlock = LoopSuccessor; 1091 ContinueTargetBlock = EntryConditionBlock; 1092 1093 CFGBlock* BodyBlock = addStmt(S->getBody()); 1094 1095 if (!BodyBlock) 1096 BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;" 1097 else if (Block) { 1098 if (!FinishBlock(BodyBlock)) 1099 return 0; 1100 } 1101 1102 // This new body block is a successor to our "exit" condition block. 1103 ExitConditionBlock->addSuccessor(BodyBlock); 1104 } 1105 1106 // Link up the condition block with the code that follows the loop. 1107 // (the false branch). 1108 ExitConditionBlock->addSuccessor(LoopSuccessor); 1109 1110 // Now create a prologue block to contain the collection expression. 1111 Block = createBlock(); 1112 return addStmt(S->getCollection()); 1113} 1114 1115CFGBlock* CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S) { 1116 // FIXME: Add locking 'primitives' to CFG for @synchronized. 1117 1118 // Inline the body. 1119 CFGBlock *SyncBlock = addStmt(S->getSynchBody()); 1120 1121 // The sync body starts its own basic block. This makes it a little easier 1122 // for diagnostic clients. 1123 if (SyncBlock) { 1124 if (!FinishBlock(SyncBlock)) 1125 return 0; 1126 1127 Block = 0; 1128 } 1129 1130 Succ = SyncBlock; 1131 1132 // Inline the sync expression. 1133 return addStmt(S->getSynchExpr()); 1134} 1135 1136CFGBlock* CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt* S) { 1137 // FIXME 1138 return NYS(); 1139} 1140 1141CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { 1142 // See if this is a known constant. 1143 bool KnownTrue = false; 1144 bool KnownFalse = false; 1145 Expr::EvalResult Result; 1146 if (W->getCond()->Evaluate(Result, *Context) 1147 && Result.Val.isInt()) { 1148 if (Result.Val.getInt().getBoolValue()) 1149 KnownTrue = true; 1150 else 1151 KnownFalse = true; 1152 } 1153 1154 CFGBlock* LoopSuccessor = NULL; 1155 1156 // "while" is a control-flow statement. Thus we stop processing the current 1157 // block. 1158 if (Block) { 1159 if (!FinishBlock(Block)) 1160 return 0; 1161 LoopSuccessor = Block; 1162 } else 1163 LoopSuccessor = Succ; 1164 1165 // Because of short-circuit evaluation, the condition of the loop can span 1166 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1167 // evaluate the condition. 1168 CFGBlock* ExitConditionBlock = createBlock(false); 1169 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1170 1171 // Set the terminator for the "exit" condition block. 1172 ExitConditionBlock->setTerminator(W); 1173 1174 // Now add the actual condition to the condition block. Because the condition 1175 // itself may contain control-flow, new blocks may be created. Thus we update 1176 // "Succ" after adding the condition. 1177 if (Stmt* C = W->getCond()) { 1178 Block = ExitConditionBlock; 1179 EntryConditionBlock = addStmt(C); 1180 assert(Block == EntryConditionBlock); 1181 if (Block) { 1182 if (!FinishBlock(EntryConditionBlock)) 1183 return 0; 1184 } 1185 } 1186 1187 // The condition block is the implicit successor for the loop body as well as 1188 // any code above the loop. 1189 Succ = EntryConditionBlock; 1190 1191 // Process the loop body. 1192 { 1193 assert(W->getBody()); 1194 1195 // Save the current values for Block, Succ, and continue and break targets 1196 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1197 save_continue(ContinueTargetBlock), 1198 save_break(BreakTargetBlock); 1199 1200 // Create an empty block to represent the transition block for looping back 1201 // to the head of the loop. 1202 Block = 0; 1203 assert(Succ == EntryConditionBlock); 1204 Succ = createBlock(); 1205 Succ->setLoopTarget(W); 1206 ContinueTargetBlock = Succ; 1207 1208 // All breaks should go to the code following the loop. 1209 BreakTargetBlock = LoopSuccessor; 1210 1211 // NULL out Block to force lazy instantiation of blocks for the body. 1212 Block = NULL; 1213 1214 // Create the body. The returned block is the entry to the loop body. 1215 CFGBlock* BodyBlock = addStmt(W->getBody()); 1216 1217 if (!BodyBlock) 1218 BodyBlock = EntryConditionBlock; // can happen for "while(...) ;" 1219 else if (Block) { 1220 if (!FinishBlock(BodyBlock)) 1221 return 0; 1222 } 1223 1224 if (KnownFalse) 1225 ExitConditionBlock->addSuccessor(0); 1226 else { 1227 // Add the loop body entry as a successor to the condition. 1228 ExitConditionBlock->addSuccessor(BodyBlock); 1229 } 1230 } 1231 1232 if (KnownTrue) 1233 ExitConditionBlock->addSuccessor(0); 1234 else { 1235 // Link up the condition block with the code that follows the loop. (the 1236 // false branch). 1237 ExitConditionBlock->addSuccessor(LoopSuccessor); 1238 } 1239 1240 // There can be no more statements in the condition block since we loop back 1241 // to this block. NULL out Block to force lazy creation of another block. 1242 Block = NULL; 1243 1244 // Return the condition block, which is the dominating block for the loop. 1245 Succ = EntryConditionBlock; 1246 return EntryConditionBlock; 1247} 1248 1249 1250CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt* S) { 1251 // FIXME: For now we pretend that @catch and the code it contains does not 1252 // exit. 1253 return Block; 1254} 1255 1256CFGBlock* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt* S) { 1257 // FIXME: This isn't complete. We basically treat @throw like a return 1258 // statement. 1259 1260 // If we were in the middle of a block we stop processing that block and 1261 // reverse its statements. 1262 if (Block && !FinishBlock(Block)) 1263 return 0; 1264 1265 // Create the new block. 1266 Block = createBlock(false); 1267 1268 // The Exit block is the only successor. 1269 Block->addSuccessor(&cfg->getExit()); 1270 1271 // Add the statement to the block. This may create new blocks if S contains 1272 // control-flow (short-circuit operations). 1273 return VisitStmt(S, true); 1274} 1275 1276CFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) { 1277 // See if this is a known constant. 1278 bool KnownTrue = false; 1279 bool KnownFalse = false; 1280 Expr::EvalResult Result; 1281 if (D->getCond()->Evaluate(Result, *Context) 1282 && Result.Val.isInt()) { 1283 if (Result.Val.getInt().getBoolValue()) 1284 KnownTrue = true; 1285 else 1286 KnownFalse = true; 1287 } 1288 1289 CFGBlock* LoopSuccessor = NULL; 1290 1291 // "do...while" is a control-flow statement. Thus we stop processing the 1292 // current block. 1293 if (Block) { 1294 if (!FinishBlock(Block)) 1295 return 0; 1296 LoopSuccessor = Block; 1297 } else 1298 LoopSuccessor = Succ; 1299 1300 // Because of short-circuit evaluation, the condition of the loop can span 1301 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1302 // evaluate the condition. 1303 CFGBlock* ExitConditionBlock = createBlock(false); 1304 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1305 1306 // Set the terminator for the "exit" condition block. 1307 ExitConditionBlock->setTerminator(D); 1308 1309 // Now add the actual condition to the condition block. Because the condition 1310 // itself may contain control-flow, new blocks may be created. 1311 if (Stmt* C = D->getCond()) { 1312 Block = ExitConditionBlock; 1313 EntryConditionBlock = addStmt(C); 1314 if (Block) { 1315 if (!FinishBlock(EntryConditionBlock)) 1316 return 0; 1317 } 1318 } 1319 1320 // The condition block is the implicit successor for the loop body. 1321 Succ = EntryConditionBlock; 1322 1323 // Process the loop body. 1324 CFGBlock* BodyBlock = NULL; 1325 { 1326 assert (D->getBody()); 1327 1328 // Save the current values for Block, Succ, and continue and break targets 1329 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1330 save_continue(ContinueTargetBlock), 1331 save_break(BreakTargetBlock); 1332 1333 // All continues within this loop should go to the condition block 1334 ContinueTargetBlock = EntryConditionBlock; 1335 1336 // All breaks should go to the code following the loop. 1337 BreakTargetBlock = LoopSuccessor; 1338 1339 // NULL out Block to force lazy instantiation of blocks for the body. 1340 Block = NULL; 1341 1342 // Create the body. The returned block is the entry to the loop body. 1343 BodyBlock = addStmt(D->getBody()); 1344 1345 if (!BodyBlock) 1346 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)" 1347 else if (Block) { 1348 if (!FinishBlock(BodyBlock)) 1349 return 0; 1350 } 1351 1352 // Add an intermediate block between the BodyBlock and the 1353 // ExitConditionBlock to represent the "loop back" transition. Create an 1354 // empty block to represent the transition block for looping back to the 1355 // head of the loop. 1356 // FIXME: Can we do this more efficiently without adding another block? 1357 Block = NULL; 1358 Succ = BodyBlock; 1359 CFGBlock *LoopBackBlock = createBlock(); 1360 LoopBackBlock->setLoopTarget(D); 1361 1362 if (KnownFalse) 1363 ExitConditionBlock->addSuccessor(0); 1364 else { 1365 // Add the loop body entry as a successor to the condition. 1366 ExitConditionBlock->addSuccessor(LoopBackBlock); 1367 } 1368 } 1369 1370 if (KnownTrue) 1371 ExitConditionBlock->addSuccessor(0); 1372 else { 1373 // Link up the condition block with the code that follows the loop. (the 1374 // false branch). 1375 ExitConditionBlock->addSuccessor(LoopSuccessor); 1376 } 1377 1378 // There can be no more statements in the body block(s) since we loop back to 1379 // the body. NULL out Block to force lazy creation of another block. 1380 Block = NULL; 1381 1382 // Return the loop body, which is the dominating block for the loop. 1383 Succ = BodyBlock; 1384 return BodyBlock; 1385} 1386 1387CFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) { 1388 // "continue" is a control-flow statement. Thus we stop processing the 1389 // current block. 1390 if (Block && !FinishBlock(Block)) 1391 return 0; 1392 1393 // Now create a new block that ends with the continue statement. 1394 Block = createBlock(false); 1395 Block->setTerminator(C); 1396 1397 // If there is no target for the continue, then we are looking at an 1398 // incomplete AST. This means the CFG cannot be constructed. 1399 if (ContinueTargetBlock) 1400 Block->addSuccessor(ContinueTargetBlock); 1401 else 1402 badCFG = true; 1403 1404 return Block; 1405} 1406 1407CFGBlock *CFGBuilder::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, 1408 bool alwaysAdd) { 1409 1410 if (alwaysAdd) { 1411 autoCreateBlock(); 1412 Block->appendStmt(E); 1413 } 1414 1415 // VLA types have expressions that must be evaluated. 1416 if (E->isArgumentType()) { 1417 for (VariableArrayType* VA = FindVA(E->getArgumentType().getTypePtr()); 1418 VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) 1419 addStmt(VA->getSizeExpr()); 1420 } 1421 1422 return Block; 1423} 1424 1425/// VisitStmtExpr - Utility method to handle (nested) statement 1426/// expressions (a GCC extension). 1427CFGBlock* CFGBuilder::VisitStmtExpr(StmtExpr *SE, bool alwaysAdd) { 1428 if (alwaysAdd) { 1429 autoCreateBlock(); 1430 Block->appendStmt(SE); 1431 } 1432 return VisitCompoundStmt(SE->getSubStmt()); 1433} 1434 1435CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { 1436 // "switch" is a control-flow statement. Thus we stop processing the current 1437 // block. 1438 CFGBlock* SwitchSuccessor = NULL; 1439 1440 if (Block) { 1441 if (!FinishBlock(Block)) 1442 return 0; 1443 SwitchSuccessor = Block; 1444 } else SwitchSuccessor = Succ; 1445 1446 // Save the current "switch" context. 1447 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock), 1448 save_break(BreakTargetBlock), 1449 save_default(DefaultCaseBlock); 1450 1451 // Set the "default" case to be the block after the switch statement. If the 1452 // switch statement contains a "default:", this value will be overwritten with 1453 // the block for that code. 1454 DefaultCaseBlock = SwitchSuccessor; 1455 1456 // Create a new block that will contain the switch statement. 1457 SwitchTerminatedBlock = createBlock(false); 1458 1459 // Now process the switch body. The code after the switch is the implicit 1460 // successor. 1461 Succ = SwitchSuccessor; 1462 BreakTargetBlock = SwitchSuccessor; 1463 1464 // When visiting the body, the case statements should automatically get linked 1465 // up to the switch. We also don't keep a pointer to the body, since all 1466 // control-flow from the switch goes to case/default statements. 1467 assert (Terminator->getBody() && "switch must contain a non-NULL body"); 1468 Block = NULL; 1469 CFGBlock *BodyBlock = addStmt(Terminator->getBody()); 1470 if (Block) { 1471 if (!FinishBlock(BodyBlock)) 1472 return 0; 1473 } 1474 1475 // If we have no "default:" case, the default transition is to the code 1476 // following the switch body. 1477 SwitchTerminatedBlock->addSuccessor(DefaultCaseBlock); 1478 1479 // Add the terminator and condition in the switch block. 1480 SwitchTerminatedBlock->setTerminator(Terminator); 1481 assert (Terminator->getCond() && "switch condition must be non-NULL"); 1482 Block = SwitchTerminatedBlock; 1483 1484 return addStmt(Terminator->getCond()); 1485} 1486 1487CFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* CS) { 1488 // CaseStmts are essentially labels, so they are the first statement in a 1489 // block. 1490 1491 if (CS->getSubStmt()) 1492 addStmt(CS->getSubStmt()); 1493 1494 CFGBlock* CaseBlock = Block; 1495 if (!CaseBlock) 1496 CaseBlock = createBlock(); 1497 1498 // Cases statements partition blocks, so this is the top of the basic block we 1499 // were processing (the "case XXX:" is the label). 1500 CaseBlock->setLabel(CS); 1501 1502 if (!FinishBlock(CaseBlock)) 1503 return 0; 1504 1505 // Add this block to the list of successors for the block with the switch 1506 // statement. 1507 assert(SwitchTerminatedBlock); 1508 SwitchTerminatedBlock->addSuccessor(CaseBlock); 1509 1510 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1511 Block = NULL; 1512 1513 // This block is now the implicit successor of other blocks. 1514 Succ = CaseBlock; 1515 1516 return CaseBlock; 1517} 1518 1519CFGBlock* CFGBuilder::VisitDefaultStmt(DefaultStmt* Terminator) { 1520 if (Terminator->getSubStmt()) 1521 addStmt(Terminator->getSubStmt()); 1522 1523 DefaultCaseBlock = Block; 1524 1525 if (!DefaultCaseBlock) 1526 DefaultCaseBlock = createBlock(); 1527 1528 // Default statements partition blocks, so this is the top of the basic block 1529 // we were processing (the "default:" is the label). 1530 DefaultCaseBlock->setLabel(Terminator); 1531 1532 if (!FinishBlock(DefaultCaseBlock)) 1533 return 0; 1534 1535 // Unlike case statements, we don't add the default block to the successors 1536 // for the switch statement immediately. This is done when we finish 1537 // processing the switch statement. This allows for the default case 1538 // (including a fall-through to the code after the switch statement) to always 1539 // be the last successor of a switch-terminated block. 1540 1541 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1542 Block = NULL; 1543 1544 // This block is now the implicit successor of other blocks. 1545 Succ = DefaultCaseBlock; 1546 1547 return DefaultCaseBlock; 1548} 1549 1550CFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1551 // Lazily create the indirect-goto dispatch block if there isn't one already. 1552 CFGBlock* IBlock = cfg->getIndirectGotoBlock(); 1553 1554 if (!IBlock) { 1555 IBlock = createBlock(false); 1556 cfg->setIndirectGotoBlock(IBlock); 1557 } 1558 1559 // IndirectGoto is a control-flow statement. Thus we stop processing the 1560 // current block and create a new one. 1561 if (Block && !FinishBlock(Block)) 1562 return 0; 1563 1564 Block = createBlock(false); 1565 Block->setTerminator(I); 1566 Block->addSuccessor(IBlock); 1567 return addStmt(I->getTarget()); 1568} 1569 1570} // end anonymous namespace 1571 1572/// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has 1573/// no successors or predecessors. If this is the first block created in the 1574/// CFG, it is automatically set to be the Entry and Exit of the CFG. 1575CFGBlock* CFG::createBlock() { 1576 bool first_block = begin() == end(); 1577 1578 // Create the block. 1579 Blocks.push_front(CFGBlock(NumBlockIDs++)); 1580 1581 // If this is the first block, set it as the Entry and Exit. 1582 if (first_block) Entry = Exit = &front(); 1583 1584 // Return the block. 1585 return &front(); 1586} 1587 1588/// buildCFG - Constructs a CFG from an AST. Ownership of the returned 1589/// CFG is returned to the caller. 1590CFG* CFG::buildCFG(Stmt* Statement, ASTContext *C) { 1591 CFGBuilder Builder; 1592 return Builder.buildCFG(Statement, C); 1593} 1594 1595/// reverseStmts - Reverses the orders of statements within a CFGBlock. 1596void CFGBlock::reverseStmts() { std::reverse(Stmts.begin(),Stmts.end()); } 1597 1598//===----------------------------------------------------------------------===// 1599// CFG: Queries for BlkExprs. 1600//===----------------------------------------------------------------------===// 1601 1602namespace { 1603 typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy; 1604} 1605 1606static void FindSubExprAssignments(Stmt* Terminator, llvm::SmallPtrSet<Expr*,50>& Set) { 1607 if (!Terminator) 1608 return; 1609 1610 for (Stmt::child_iterator I=Terminator->child_begin(), E=Terminator->child_end(); I!=E; ++I) { 1611 if (!*I) continue; 1612 1613 if (BinaryOperator* B = dyn_cast<BinaryOperator>(*I)) 1614 if (B->isAssignmentOp()) Set.insert(B); 1615 1616 FindSubExprAssignments(*I, Set); 1617 } 1618} 1619 1620static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { 1621 BlkExprMapTy* M = new BlkExprMapTy(); 1622 1623 // Look for assignments that are used as subexpressions. These are the only 1624 // assignments that we want to *possibly* register as a block-level 1625 // expression. Basically, if an assignment occurs both in a subexpression and 1626 // at the block-level, it is a block-level expression. 1627 llvm::SmallPtrSet<Expr*,50> SubExprAssignments; 1628 1629 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) 1630 for (CFGBlock::iterator BI=I->begin(), EI=I->end(); BI != EI; ++BI) 1631 FindSubExprAssignments(*BI, SubExprAssignments); 1632 1633 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { 1634 1635 // Iterate over the statements again on identify the Expr* and Stmt* at the 1636 // block-level that are block-level expressions. 1637 1638 for (CFGBlock::iterator BI=I->begin(), EI=I->end(); BI != EI; ++BI) 1639 if (Expr* Exp = dyn_cast<Expr>(*BI)) { 1640 1641 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { 1642 // Assignment expressions that are not nested within another 1643 // expression are really "statements" whose value is never used by 1644 // another expression. 1645 if (B->isAssignmentOp() && !SubExprAssignments.count(Exp)) 1646 continue; 1647 } else if (const StmtExpr* Terminator = dyn_cast<StmtExpr>(Exp)) { 1648 // Special handling for statement expressions. The last statement in 1649 // the statement expression is also a block-level expr. 1650 const CompoundStmt* C = Terminator->getSubStmt(); 1651 if (!C->body_empty()) { 1652 unsigned x = M->size(); 1653 (*M)[C->body_back()] = x; 1654 } 1655 } 1656 1657 unsigned x = M->size(); 1658 (*M)[Exp] = x; 1659 } 1660 1661 // Look at terminators. The condition is a block-level expression. 1662 1663 Stmt* S = I->getTerminatorCondition(); 1664 1665 if (S && M->find(S) == M->end()) { 1666 unsigned x = M->size(); 1667 (*M)[S] = x; 1668 } 1669 } 1670 1671 return M; 1672} 1673 1674CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt* S) { 1675 assert(S != NULL); 1676 if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); } 1677 1678 BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap); 1679 BlkExprMapTy::iterator I = M->find(S); 1680 1681 if (I == M->end()) return CFG::BlkExprNumTy(); 1682 else return CFG::BlkExprNumTy(I->second); 1683} 1684 1685unsigned CFG::getNumBlkExprs() { 1686 if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap)) 1687 return M->size(); 1688 else { 1689 // We assume callers interested in the number of BlkExprs will want 1690 // the map constructed if it doesn't already exist. 1691 BlkExprMap = (void*) PopulateBlkExprMap(*this); 1692 return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); 1693 } 1694} 1695 1696//===----------------------------------------------------------------------===// 1697// Cleanup: CFG dstor. 1698//===----------------------------------------------------------------------===// 1699 1700CFG::~CFG() { 1701 delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap); 1702} 1703 1704//===----------------------------------------------------------------------===// 1705// CFG pretty printing 1706//===----------------------------------------------------------------------===// 1707 1708namespace { 1709 1710class VISIBILITY_HIDDEN StmtPrinterHelper : public PrinterHelper { 1711 1712 typedef llvm::DenseMap<Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; 1713 StmtMapTy StmtMap; 1714 signed CurrentBlock; 1715 unsigned CurrentStmt; 1716 const LangOptions &LangOpts; 1717public: 1718 1719 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) 1720 : CurrentBlock(0), CurrentStmt(0), LangOpts(LO) { 1721 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { 1722 unsigned j = 1; 1723 for (CFGBlock::const_iterator BI = I->begin(), BEnd = I->end() ; 1724 BI != BEnd; ++BI, ++j ) 1725 StmtMap[*BI] = std::make_pair(I->getBlockID(),j); 1726 } 1727 } 1728 1729 virtual ~StmtPrinterHelper() {} 1730 1731 const LangOptions &getLangOpts() const { return LangOpts; } 1732 void setBlockID(signed i) { CurrentBlock = i; } 1733 void setStmtID(unsigned i) { CurrentStmt = i; } 1734 1735 virtual bool handledStmt(Stmt* Terminator, llvm::raw_ostream& OS) { 1736 1737 StmtMapTy::iterator I = StmtMap.find(Terminator); 1738 1739 if (I == StmtMap.end()) 1740 return false; 1741 1742 if (CurrentBlock >= 0 && I->second.first == (unsigned) CurrentBlock 1743 && I->second.second == CurrentStmt) 1744 return false; 1745 1746 OS << "[B" << I->second.first << "." << I->second.second << "]"; 1747 return true; 1748 } 1749}; 1750} // end anonymous namespace 1751 1752 1753namespace { 1754class VISIBILITY_HIDDEN CFGBlockTerminatorPrint 1755 : public StmtVisitor<CFGBlockTerminatorPrint,void> { 1756 1757 llvm::raw_ostream& OS; 1758 StmtPrinterHelper* Helper; 1759 PrintingPolicy Policy; 1760 1761public: 1762 CFGBlockTerminatorPrint(llvm::raw_ostream& os, StmtPrinterHelper* helper, 1763 const PrintingPolicy &Policy) 1764 : OS(os), Helper(helper), Policy(Policy) {} 1765 1766 void VisitIfStmt(IfStmt* I) { 1767 OS << "if "; 1768 I->getCond()->printPretty(OS,Helper,Policy); 1769 } 1770 1771 // Default case. 1772 void VisitStmt(Stmt* Terminator) { 1773 Terminator->printPretty(OS, Helper, Policy); 1774 } 1775 1776 void VisitForStmt(ForStmt* F) { 1777 OS << "for (" ; 1778 if (F->getInit()) OS << "..."; 1779 OS << "; "; 1780 if (Stmt* C = F->getCond()) C->printPretty(OS, Helper, Policy); 1781 OS << "; "; 1782 if (F->getInc()) OS << "..."; 1783 OS << ")"; 1784 } 1785 1786 void VisitWhileStmt(WhileStmt* W) { 1787 OS << "while " ; 1788 if (Stmt* C = W->getCond()) C->printPretty(OS, Helper, Policy); 1789 } 1790 1791 void VisitDoStmt(DoStmt* D) { 1792 OS << "do ... while "; 1793 if (Stmt* C = D->getCond()) C->printPretty(OS, Helper, Policy); 1794 } 1795 1796 void VisitSwitchStmt(SwitchStmt* Terminator) { 1797 OS << "switch "; 1798 Terminator->getCond()->printPretty(OS, Helper, Policy); 1799 } 1800 1801 void VisitConditionalOperator(ConditionalOperator* C) { 1802 C->getCond()->printPretty(OS, Helper, Policy); 1803 OS << " ? ... : ..."; 1804 } 1805 1806 void VisitChooseExpr(ChooseExpr* C) { 1807 OS << "__builtin_choose_expr( "; 1808 C->getCond()->printPretty(OS, Helper, Policy); 1809 OS << " )"; 1810 } 1811 1812 void VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1813 OS << "goto *"; 1814 I->getTarget()->printPretty(OS, Helper, Policy); 1815 } 1816 1817 void VisitBinaryOperator(BinaryOperator* B) { 1818 if (!B->isLogicalOp()) { 1819 VisitExpr(B); 1820 return; 1821 } 1822 1823 B->getLHS()->printPretty(OS, Helper, Policy); 1824 1825 switch (B->getOpcode()) { 1826 case BinaryOperator::LOr: 1827 OS << " || ..."; 1828 return; 1829 case BinaryOperator::LAnd: 1830 OS << " && ..."; 1831 return; 1832 default: 1833 assert(false && "Invalid logical operator."); 1834 } 1835 } 1836 1837 void VisitExpr(Expr* E) { 1838 E->printPretty(OS, Helper, Policy); 1839 } 1840}; 1841} // end anonymous namespace 1842 1843 1844static void print_stmt(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, 1845 Stmt* Terminator) { 1846 if (Helper) { 1847 // special printing for statement-expressions. 1848 if (StmtExpr* SE = dyn_cast<StmtExpr>(Terminator)) { 1849 CompoundStmt* Sub = SE->getSubStmt(); 1850 1851 if (Sub->child_begin() != Sub->child_end()) { 1852 OS << "({ ... ; "; 1853 Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); 1854 OS << " })\n"; 1855 return; 1856 } 1857 } 1858 1859 // special printing for comma expressions. 1860 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Terminator)) { 1861 if (B->getOpcode() == BinaryOperator::Comma) { 1862 OS << "... , "; 1863 Helper->handledStmt(B->getRHS(),OS); 1864 OS << '\n'; 1865 return; 1866 } 1867 } 1868 } 1869 1870 Terminator->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 1871 1872 // Expressions need a newline. 1873 if (isa<Expr>(Terminator)) OS << '\n'; 1874} 1875 1876static void print_block(llvm::raw_ostream& OS, const CFG* cfg, 1877 const CFGBlock& B, 1878 StmtPrinterHelper* Helper, bool print_edges) { 1879 1880 if (Helper) Helper->setBlockID(B.getBlockID()); 1881 1882 // Print the header. 1883 OS << "\n [ B" << B.getBlockID(); 1884 1885 if (&B == &cfg->getEntry()) 1886 OS << " (ENTRY) ]\n"; 1887 else if (&B == &cfg->getExit()) 1888 OS << " (EXIT) ]\n"; 1889 else if (&B == cfg->getIndirectGotoBlock()) 1890 OS << " (INDIRECT GOTO DISPATCH) ]\n"; 1891 else 1892 OS << " ]\n"; 1893 1894 // Print the label of this block. 1895 if (Stmt* Terminator = const_cast<Stmt*>(B.getLabel())) { 1896 1897 if (print_edges) 1898 OS << " "; 1899 1900 if (LabelStmt* L = dyn_cast<LabelStmt>(Terminator)) 1901 OS << L->getName(); 1902 else if (CaseStmt* C = dyn_cast<CaseStmt>(Terminator)) { 1903 OS << "case "; 1904 C->getLHS()->printPretty(OS, Helper, 1905 PrintingPolicy(Helper->getLangOpts())); 1906 if (C->getRHS()) { 1907 OS << " ... "; 1908 C->getRHS()->printPretty(OS, Helper, 1909 PrintingPolicy(Helper->getLangOpts())); 1910 } 1911 } else if (isa<DefaultStmt>(Terminator)) 1912 OS << "default"; 1913 else 1914 assert(false && "Invalid label statement in CFGBlock."); 1915 1916 OS << ":\n"; 1917 } 1918 1919 // Iterate through the statements in the block and print them. 1920 unsigned j = 1; 1921 1922 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; 1923 I != E ; ++I, ++j ) { 1924 1925 // Print the statement # in the basic block and the statement itself. 1926 if (print_edges) 1927 OS << " "; 1928 1929 OS << llvm::format("%3d", j) << ": "; 1930 1931 if (Helper) 1932 Helper->setStmtID(j); 1933 1934 print_stmt(OS,Helper,*I); 1935 } 1936 1937 // Print the terminator of this block. 1938 if (B.getTerminator()) { 1939 if (print_edges) 1940 OS << " "; 1941 1942 OS << " T: "; 1943 1944 if (Helper) Helper->setBlockID(-1); 1945 1946 CFGBlockTerminatorPrint TPrinter(OS, Helper, 1947 PrintingPolicy(Helper->getLangOpts())); 1948 TPrinter.Visit(const_cast<Stmt*>(B.getTerminator())); 1949 OS << '\n'; 1950 } 1951 1952 if (print_edges) { 1953 // Print the predecessors of this block. 1954 OS << " Predecessors (" << B.pred_size() << "):"; 1955 unsigned i = 0; 1956 1957 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); 1958 I != E; ++I, ++i) { 1959 1960 if (i == 8 || (i-8) == 0) 1961 OS << "\n "; 1962 1963 OS << " B" << (*I)->getBlockID(); 1964 } 1965 1966 OS << '\n'; 1967 1968 // Print the successors of this block. 1969 OS << " Successors (" << B.succ_size() << "):"; 1970 i = 0; 1971 1972 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); 1973 I != E; ++I, ++i) { 1974 1975 if (i == 8 || (i-8) % 10 == 0) 1976 OS << "\n "; 1977 1978 if (*I) 1979 OS << " B" << (*I)->getBlockID(); 1980 else 1981 OS << " NULL"; 1982 } 1983 1984 OS << '\n'; 1985 } 1986} 1987 1988 1989/// dump - A simple pretty printer of a CFG that outputs to stderr. 1990void CFG::dump(const LangOptions &LO) const { print(llvm::errs(), LO); } 1991 1992/// print - A simple pretty printer of a CFG that outputs to an ostream. 1993void CFG::print(llvm::raw_ostream &OS, const LangOptions &LO) const { 1994 StmtPrinterHelper Helper(this, LO); 1995 1996 // Print the entry block. 1997 print_block(OS, this, getEntry(), &Helper, true); 1998 1999 // Iterate through the CFGBlocks and print them one by one. 2000 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { 2001 // Skip the entry block, because we already printed it. 2002 if (&(*I) == &getEntry() || &(*I) == &getExit()) 2003 continue; 2004 2005 print_block(OS, this, *I, &Helper, true); 2006 } 2007 2008 // Print the exit block. 2009 print_block(OS, this, getExit(), &Helper, true); 2010 OS.flush(); 2011} 2012 2013/// dump - A simply pretty printer of a CFGBlock that outputs to stderr. 2014void CFGBlock::dump(const CFG* cfg, const LangOptions &LO) const { 2015 print(llvm::errs(), cfg, LO); 2016} 2017 2018/// print - A simple pretty printer of a CFGBlock that outputs to an ostream. 2019/// Generally this will only be called from CFG::print. 2020void CFGBlock::print(llvm::raw_ostream& OS, const CFG* cfg, 2021 const LangOptions &LO) const { 2022 StmtPrinterHelper Helper(cfg, LO); 2023 print_block(OS, cfg, *this, &Helper, true); 2024} 2025 2026/// printTerminator - A simple pretty printer of the terminator of a CFGBlock. 2027void CFGBlock::printTerminator(llvm::raw_ostream &OS, 2028 const LangOptions &LO) const { 2029 CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO)); 2030 TPrinter.Visit(const_cast<Stmt*>(getTerminator())); 2031} 2032 2033Stmt* CFGBlock::getTerminatorCondition() { 2034 2035 if (!Terminator) 2036 return NULL; 2037 2038 Expr* E = NULL; 2039 2040 switch (Terminator->getStmtClass()) { 2041 default: 2042 break; 2043 2044 case Stmt::ForStmtClass: 2045 E = cast<ForStmt>(Terminator)->getCond(); 2046 break; 2047 2048 case Stmt::WhileStmtClass: 2049 E = cast<WhileStmt>(Terminator)->getCond(); 2050 break; 2051 2052 case Stmt::DoStmtClass: 2053 E = cast<DoStmt>(Terminator)->getCond(); 2054 break; 2055 2056 case Stmt::IfStmtClass: 2057 E = cast<IfStmt>(Terminator)->getCond(); 2058 break; 2059 2060 case Stmt::ChooseExprClass: 2061 E = cast<ChooseExpr>(Terminator)->getCond(); 2062 break; 2063 2064 case Stmt::IndirectGotoStmtClass: 2065 E = cast<IndirectGotoStmt>(Terminator)->getTarget(); 2066 break; 2067 2068 case Stmt::SwitchStmtClass: 2069 E = cast<SwitchStmt>(Terminator)->getCond(); 2070 break; 2071 2072 case Stmt::ConditionalOperatorClass: 2073 E = cast<ConditionalOperator>(Terminator)->getCond(); 2074 break; 2075 2076 case Stmt::BinaryOperatorClass: // '&&' and '||' 2077 E = cast<BinaryOperator>(Terminator)->getLHS(); 2078 break; 2079 2080 case Stmt::ObjCForCollectionStmtClass: 2081 return Terminator; 2082 } 2083 2084 return E ? E->IgnoreParens() : NULL; 2085} 2086 2087bool CFGBlock::hasBinaryBranchTerminator() const { 2088 2089 if (!Terminator) 2090 return false; 2091 2092 Expr* E = NULL; 2093 2094 switch (Terminator->getStmtClass()) { 2095 default: 2096 return false; 2097 2098 case Stmt::ForStmtClass: 2099 case Stmt::WhileStmtClass: 2100 case Stmt::DoStmtClass: 2101 case Stmt::IfStmtClass: 2102 case Stmt::ChooseExprClass: 2103 case Stmt::ConditionalOperatorClass: 2104 case Stmt::BinaryOperatorClass: 2105 return true; 2106 } 2107 2108 return E ? E->IgnoreParens() : NULL; 2109} 2110 2111 2112//===----------------------------------------------------------------------===// 2113// CFG Graphviz Visualization 2114//===----------------------------------------------------------------------===// 2115 2116 2117#ifndef NDEBUG 2118static StmtPrinterHelper* GraphHelper; 2119#endif 2120 2121void CFG::viewCFG(const LangOptions &LO) const { 2122#ifndef NDEBUG 2123 StmtPrinterHelper H(this, LO); 2124 GraphHelper = &H; 2125 llvm::ViewGraph(this,"CFG"); 2126 GraphHelper = NULL; 2127#endif 2128} 2129 2130namespace llvm { 2131template<> 2132struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { 2133 static std::string getNodeLabel(const CFGBlock* Node, const CFG* Graph, 2134 bool ShortNames) { 2135 2136#ifndef NDEBUG 2137 std::string OutSStr; 2138 llvm::raw_string_ostream Out(OutSStr); 2139 print_block(Out,Graph, *Node, GraphHelper, false); 2140 std::string& OutStr = Out.str(); 2141 2142 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); 2143 2144 // Process string output to make it nicer... 2145 for (unsigned i = 0; i != OutStr.length(); ++i) 2146 if (OutStr[i] == '\n') { // Left justify 2147 OutStr[i] = '\\'; 2148 OutStr.insert(OutStr.begin()+i+1, 'l'); 2149 } 2150 2151 return OutStr; 2152#else 2153 return ""; 2154#endif 2155 } 2156}; 2157} // end namespace llvm 2158