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