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