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