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