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