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