CFG.cpp revision 6b501ebaf172b28d6d7e1737db27f915175ad3c8
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 Block = addStmt(I->getCond()); 780 781 // Finally, if the IfStmt contains a condition variable, add both the IfStmt 782 // and the condition variable initialization to the CFG. 783 if (VarDecl *VD = I->getConditionVariable()) { 784 if (Expr *Init = VD->getInit()) { 785 autoCreateBlock(); 786 AppendStmt(Block, I, AddStmtChoice::AlwaysAdd); 787 addStmt(Init); 788 } 789 } 790 791 return Block; 792} 793 794 795CFGBlock* CFGBuilder::VisitReturnStmt(ReturnStmt* R) { 796 // If we were in the middle of a block we stop processing that block. 797 // 798 // NOTE: If a "return" appears in the middle of a block, this means that the 799 // code afterwards is DEAD (unreachable). We still keep a basic block 800 // for that code; a simple "mark-and-sweep" from the entry block will be 801 // able to report such dead blocks. 802 if (Block) 803 FinishBlock(Block); 804 805 // Create the new block. 806 Block = createBlock(false); 807 808 // The Exit block is the only successor. 809 AddSuccessor(Block, &cfg->getExit()); 810 811 // Add the return statement to the block. This may create new blocks if R 812 // contains control-flow (short-circuit operations). 813 return VisitStmt(R, AddStmtChoice::AlwaysAdd); 814} 815 816CFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt* L) { 817 // Get the block of the labeled statement. Add it to our map. 818 addStmt(L->getSubStmt()); 819 CFGBlock* LabelBlock = Block; 820 821 if (!LabelBlock) // This can happen when the body is empty, i.e. 822 LabelBlock = createBlock(); // scopes that only contains NullStmts. 823 824 assert(LabelMap.find(L) == LabelMap.end() && "label already in map"); 825 LabelMap[ L ] = LabelBlock; 826 827 // Labels partition blocks, so this is the end of the basic block we were 828 // processing (L is the block's label). Because this is label (and we have 829 // already processed the substatement) there is no extra control-flow to worry 830 // about. 831 LabelBlock->setLabel(L); 832 if (!FinishBlock(LabelBlock)) 833 return 0; 834 835 // We set Block to NULL to allow lazy creation of a new block (if necessary); 836 Block = NULL; 837 838 // This block is now the implicit successor of other blocks. 839 Succ = LabelBlock; 840 841 return LabelBlock; 842} 843 844CFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) { 845 // Goto is a control-flow statement. Thus we stop processing the current 846 // block and create a new one. 847 if (Block) 848 FinishBlock(Block); 849 850 Block = createBlock(false); 851 Block->setTerminator(G); 852 853 // If we already know the mapping to the label block add the successor now. 854 LabelMapTy::iterator I = LabelMap.find(G->getLabel()); 855 856 if (I == LabelMap.end()) 857 // We will need to backpatch this block later. 858 BackpatchBlocks.push_back(Block); 859 else 860 AddSuccessor(Block, I->second); 861 862 return Block; 863} 864 865CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { 866 CFGBlock* LoopSuccessor = NULL; 867 868 // "for" is a control-flow statement. Thus we stop processing the current 869 // block. 870 if (Block) { 871 if (!FinishBlock(Block)) 872 return 0; 873 LoopSuccessor = Block; 874 } else 875 LoopSuccessor = Succ; 876 877 // Because of short-circuit evaluation, the condition of the loop can span 878 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 879 // evaluate the condition. 880 CFGBlock* ExitConditionBlock = createBlock(false); 881 CFGBlock* EntryConditionBlock = ExitConditionBlock; 882 883 // Set the terminator for the "exit" condition block. 884 ExitConditionBlock->setTerminator(F); 885 886 // Now add the actual condition to the condition block. Because the condition 887 // itself may contain control-flow, new blocks may be created. 888 if (Stmt* C = F->getCond()) { 889 Block = ExitConditionBlock; 890 EntryConditionBlock = addStmt(C); 891 if (Block) { 892 if (!FinishBlock(EntryConditionBlock)) 893 return 0; 894 } 895 } 896 897 // The condition block is the implicit successor for the loop body as well as 898 // any code above the loop. 899 Succ = EntryConditionBlock; 900 901 // See if this is a known constant. 902 TryResult KnownVal(true); 903 904 if (F->getCond()) 905 KnownVal = TryEvaluateBool(F->getCond()); 906 907 // Now create the loop body. 908 { 909 assert (F->getBody()); 910 911 // Save the current values for Block, Succ, and continue and break targets 912 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 913 save_continue(ContinueTargetBlock), 914 save_break(BreakTargetBlock); 915 916 // Create a new block to contain the (bottom) of the loop body. 917 Block = NULL; 918 919 if (Stmt* I = F->getInc()) { 920 // Generate increment code in its own basic block. This is the target of 921 // continue statements. 922 Succ = addStmt(I); 923 } else { 924 // No increment code. Create a special, empty, block that is used as the 925 // target block for "looping back" to the start of the loop. 926 assert(Succ == EntryConditionBlock); 927 Succ = createBlock(); 928 } 929 930 // Finish up the increment (or empty) block if it hasn't been already. 931 if (Block) { 932 assert(Block == Succ); 933 if (!FinishBlock(Block)) 934 return 0; 935 Block = 0; 936 } 937 938 ContinueTargetBlock = Succ; 939 940 // The starting block for the loop increment is the block that should 941 // represent the 'loop target' for looping back to the start of the loop. 942 ContinueTargetBlock->setLoopTarget(F); 943 944 // All breaks should go to the code following the loop. 945 BreakTargetBlock = LoopSuccessor; 946 947 // Now populate the body block, and in the process create new blocks as we 948 // walk the body of the loop. 949 CFGBlock* BodyBlock = addStmt(F->getBody()); 950 951 if (!BodyBlock) 952 BodyBlock = ContinueTargetBlock; // can happen for "for (...;...;...) ;" 953 else if (Block && !FinishBlock(BodyBlock)) 954 return 0; 955 956 // This new body block is a successor to our "exit" condition block. 957 AddSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); 958 } 959 960 // Link up the condition block with the code that follows the loop. (the 961 // false branch). 962 AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 963 964 // If the loop contains initialization, create a new block for those 965 // statements. This block can also contain statements that precede the loop. 966 if (Stmt* I = F->getInit()) { 967 Block = createBlock(); 968 return addStmt(I); 969 } else { 970 // There is no loop initialization. We are thus basically a while loop. 971 // NULL out Block to force lazy block construction. 972 Block = NULL; 973 Succ = EntryConditionBlock; 974 return EntryConditionBlock; 975 } 976} 977 978CFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { 979 // Objective-C fast enumeration 'for' statements: 980 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC 981 // 982 // for ( Type newVariable in collection_expression ) { statements } 983 // 984 // becomes: 985 // 986 // prologue: 987 // 1. collection_expression 988 // T. jump to loop_entry 989 // loop_entry: 990 // 1. side-effects of element expression 991 // 1. ObjCForCollectionStmt [performs binding to newVariable] 992 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil] 993 // TB: 994 // statements 995 // T. jump to loop_entry 996 // FB: 997 // what comes after 998 // 999 // and 1000 // 1001 // Type existingItem; 1002 // for ( existingItem in expression ) { statements } 1003 // 1004 // becomes: 1005 // 1006 // the same with newVariable replaced with existingItem; the binding works 1007 // the same except that for one ObjCForCollectionStmt::getElement() returns 1008 // a DeclStmt and the other returns a DeclRefExpr. 1009 // 1010 1011 CFGBlock* LoopSuccessor = 0; 1012 1013 if (Block) { 1014 if (!FinishBlock(Block)) 1015 return 0; 1016 LoopSuccessor = Block; 1017 Block = 0; 1018 } else 1019 LoopSuccessor = Succ; 1020 1021 // Build the condition blocks. 1022 CFGBlock* ExitConditionBlock = createBlock(false); 1023 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1024 1025 // Set the terminator for the "exit" condition block. 1026 ExitConditionBlock->setTerminator(S); 1027 1028 // The last statement in the block should be the ObjCForCollectionStmt, which 1029 // performs the actual binding to 'element' and determines if there are any 1030 // more items in the collection. 1031 AppendStmt(ExitConditionBlock, S); 1032 Block = ExitConditionBlock; 1033 1034 // Walk the 'element' expression to see if there are any side-effects. We 1035 // generate new blocks as necesary. We DON'T add the statement by default to 1036 // the CFG unless it contains control-flow. 1037 EntryConditionBlock = Visit(S->getElement(), AddStmtChoice::NotAlwaysAdd); 1038 if (Block) { 1039 if (!FinishBlock(EntryConditionBlock)) 1040 return 0; 1041 Block = 0; 1042 } 1043 1044 // The condition block is the implicit successor for the loop body as well as 1045 // any code above the loop. 1046 Succ = EntryConditionBlock; 1047 1048 // Now create the true branch. 1049 { 1050 // Save the current values for Succ, continue and break targets. 1051 SaveAndRestore<CFGBlock*> save_Succ(Succ), 1052 save_continue(ContinueTargetBlock), save_break(BreakTargetBlock); 1053 1054 BreakTargetBlock = LoopSuccessor; 1055 ContinueTargetBlock = EntryConditionBlock; 1056 1057 CFGBlock* BodyBlock = addStmt(S->getBody()); 1058 1059 if (!BodyBlock) 1060 BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;" 1061 else if (Block) { 1062 if (!FinishBlock(BodyBlock)) 1063 return 0; 1064 } 1065 1066 // This new body block is a successor to our "exit" condition block. 1067 AddSuccessor(ExitConditionBlock, BodyBlock); 1068 } 1069 1070 // Link up the condition block with the code that follows the loop. 1071 // (the false branch). 1072 AddSuccessor(ExitConditionBlock, LoopSuccessor); 1073 1074 // Now create a prologue block to contain the collection expression. 1075 Block = createBlock(); 1076 return addStmt(S->getCollection()); 1077} 1078 1079CFGBlock* CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S) { 1080 // FIXME: Add locking 'primitives' to CFG for @synchronized. 1081 1082 // Inline the body. 1083 CFGBlock *SyncBlock = addStmt(S->getSynchBody()); 1084 1085 // The sync body starts its own basic block. This makes it a little easier 1086 // for diagnostic clients. 1087 if (SyncBlock) { 1088 if (!FinishBlock(SyncBlock)) 1089 return 0; 1090 1091 Block = 0; 1092 } 1093 1094 Succ = SyncBlock; 1095 1096 // Inline the sync expression. 1097 return addStmt(S->getSynchExpr()); 1098} 1099 1100CFGBlock* CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt* S) { 1101 // FIXME 1102 return NYS(); 1103} 1104 1105CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { 1106 CFGBlock* LoopSuccessor = NULL; 1107 1108 // "while" is a control-flow statement. Thus we stop processing the current 1109 // block. 1110 if (Block) { 1111 if (!FinishBlock(Block)) 1112 return 0; 1113 LoopSuccessor = Block; 1114 } else 1115 LoopSuccessor = Succ; 1116 1117 // Because of short-circuit evaluation, the condition of the loop can span 1118 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1119 // evaluate the condition. 1120 CFGBlock* ExitConditionBlock = createBlock(false); 1121 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1122 1123 // Set the terminator for the "exit" condition block. 1124 ExitConditionBlock->setTerminator(W); 1125 1126 // Now add the actual condition to the condition block. Because the condition 1127 // itself may contain control-flow, new blocks may be created. Thus we update 1128 // "Succ" after adding the condition. 1129 if (Stmt* C = W->getCond()) { 1130 Block = ExitConditionBlock; 1131 EntryConditionBlock = addStmt(C); 1132 assert(Block == EntryConditionBlock); 1133 if (Block) { 1134 if (!FinishBlock(EntryConditionBlock)) 1135 return 0; 1136 } 1137 } 1138 1139 // The condition block is the implicit successor for the loop body as well as 1140 // any code above the loop. 1141 Succ = EntryConditionBlock; 1142 1143 // See if this is a known constant. 1144 const TryResult& KnownVal = TryEvaluateBool(W->getCond()); 1145 1146 // Process the loop body. 1147 { 1148 assert(W->getBody()); 1149 1150 // Save the current values for Block, Succ, and continue and break targets 1151 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1152 save_continue(ContinueTargetBlock), 1153 save_break(BreakTargetBlock); 1154 1155 // Create an empty block to represent the transition block for looping back 1156 // to the head of the loop. 1157 Block = 0; 1158 assert(Succ == EntryConditionBlock); 1159 Succ = createBlock(); 1160 Succ->setLoopTarget(W); 1161 ContinueTargetBlock = Succ; 1162 1163 // All breaks should go to the code following the loop. 1164 BreakTargetBlock = LoopSuccessor; 1165 1166 // NULL out Block to force lazy instantiation of blocks for the body. 1167 Block = NULL; 1168 1169 // Create the body. The returned block is the entry to the loop body. 1170 CFGBlock* BodyBlock = addStmt(W->getBody()); 1171 1172 if (!BodyBlock) 1173 BodyBlock = ContinueTargetBlock; // can happen for "while(...) ;" 1174 else if (Block) { 1175 if (!FinishBlock(BodyBlock)) 1176 return 0; 1177 } 1178 1179 // Add the loop body entry as a successor to the condition. 1180 AddSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); 1181 } 1182 1183 // Link up the condition block with the code that follows the loop. (the 1184 // false branch). 1185 AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 1186 1187 // There can be no more statements in the condition block since we loop back 1188 // to this block. NULL out Block to force lazy creation of another block. 1189 Block = NULL; 1190 1191 // Return the condition block, which is the dominating block for the loop. 1192 Succ = EntryConditionBlock; 1193 return EntryConditionBlock; 1194} 1195 1196 1197CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt* S) { 1198 // FIXME: For now we pretend that @catch and the code it contains does not 1199 // exit. 1200 return Block; 1201} 1202 1203CFGBlock* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt* S) { 1204 // FIXME: This isn't complete. We basically treat @throw like a return 1205 // statement. 1206 1207 // If we were in the middle of a block we stop processing that block. 1208 if (Block && !FinishBlock(Block)) 1209 return 0; 1210 1211 // Create the new block. 1212 Block = createBlock(false); 1213 1214 // The Exit block is the only successor. 1215 AddSuccessor(Block, &cfg->getExit()); 1216 1217 // Add the statement to the block. This may create new blocks if S contains 1218 // control-flow (short-circuit operations). 1219 return VisitStmt(S, AddStmtChoice::AlwaysAdd); 1220} 1221 1222CFGBlock* CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr* T) { 1223 // If we were in the middle of a block we stop processing that block. 1224 if (Block && !FinishBlock(Block)) 1225 return 0; 1226 1227 // Create the new block. 1228 Block = createBlock(false); 1229 1230 // The Exit block is the only successor. 1231 AddSuccessor(Block, &cfg->getExit()); 1232 1233 // Add the statement to the block. This may create new blocks if S contains 1234 // control-flow (short-circuit operations). 1235 return VisitStmt(T, AddStmtChoice::AlwaysAdd); 1236} 1237 1238CFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) { 1239 CFGBlock* LoopSuccessor = NULL; 1240 1241 // "do...while" is a control-flow statement. Thus we stop processing the 1242 // current block. 1243 if (Block) { 1244 if (!FinishBlock(Block)) 1245 return 0; 1246 LoopSuccessor = Block; 1247 } else 1248 LoopSuccessor = Succ; 1249 1250 // Because of short-circuit evaluation, the condition of the loop can span 1251 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1252 // evaluate the condition. 1253 CFGBlock* ExitConditionBlock = createBlock(false); 1254 CFGBlock* EntryConditionBlock = ExitConditionBlock; 1255 1256 // Set the terminator for the "exit" condition block. 1257 ExitConditionBlock->setTerminator(D); 1258 1259 // Now add the actual condition to the condition block. Because the condition 1260 // itself may contain control-flow, new blocks may be created. 1261 if (Stmt* C = D->getCond()) { 1262 Block = ExitConditionBlock; 1263 EntryConditionBlock = addStmt(C); 1264 if (Block) { 1265 if (!FinishBlock(EntryConditionBlock)) 1266 return 0; 1267 } 1268 } 1269 1270 // The condition block is the implicit successor for the loop body. 1271 Succ = EntryConditionBlock; 1272 1273 // See if this is a known constant. 1274 const TryResult &KnownVal = TryEvaluateBool(D->getCond()); 1275 1276 // Process the loop body. 1277 CFGBlock* BodyBlock = NULL; 1278 { 1279 assert (D->getBody()); 1280 1281 // Save the current values for Block, Succ, and continue and break targets 1282 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ), 1283 save_continue(ContinueTargetBlock), 1284 save_break(BreakTargetBlock); 1285 1286 // All continues within this loop should go to the condition block 1287 ContinueTargetBlock = EntryConditionBlock; 1288 1289 // All breaks should go to the code following the loop. 1290 BreakTargetBlock = LoopSuccessor; 1291 1292 // NULL out Block to force lazy instantiation of blocks for the body. 1293 Block = NULL; 1294 1295 // Create the body. The returned block is the entry to the loop body. 1296 BodyBlock = addStmt(D->getBody()); 1297 1298 if (!BodyBlock) 1299 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)" 1300 else if (Block) { 1301 if (!FinishBlock(BodyBlock)) 1302 return 0; 1303 } 1304 1305 // Add an intermediate block between the BodyBlock and the 1306 // ExitConditionBlock to represent the "loop back" transition. Create an 1307 // empty block to represent the transition block for looping back to the 1308 // head of the loop. 1309 // FIXME: Can we do this more efficiently without adding another block? 1310 Block = NULL; 1311 Succ = BodyBlock; 1312 CFGBlock *LoopBackBlock = createBlock(); 1313 LoopBackBlock->setLoopTarget(D); 1314 1315 // Add the loop body entry as a successor to the condition. 1316 AddSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : LoopBackBlock); 1317 } 1318 1319 // Link up the condition block with the code that follows the loop. 1320 // (the false branch). 1321 AddSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 1322 1323 // There can be no more statements in the body block(s) since we loop back to 1324 // the body. NULL out Block to force lazy creation of another block. 1325 Block = NULL; 1326 1327 // Return the loop body, which is the dominating block for the loop. 1328 Succ = BodyBlock; 1329 return BodyBlock; 1330} 1331 1332CFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) { 1333 // "continue" is a control-flow statement. Thus we stop processing the 1334 // current block. 1335 if (Block && !FinishBlock(Block)) 1336 return 0; 1337 1338 // Now create a new block that ends with the continue statement. 1339 Block = createBlock(false); 1340 Block->setTerminator(C); 1341 1342 // If there is no target for the continue, then we are looking at an 1343 // incomplete AST. This means the CFG cannot be constructed. 1344 if (ContinueTargetBlock) 1345 AddSuccessor(Block, ContinueTargetBlock); 1346 else 1347 badCFG = true; 1348 1349 return Block; 1350} 1351 1352CFGBlock *CFGBuilder::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, 1353 AddStmtChoice asc) { 1354 1355 if (asc.alwaysAdd()) { 1356 autoCreateBlock(); 1357 AppendStmt(Block, E); 1358 } 1359 1360 // VLA types have expressions that must be evaluated. 1361 if (E->isArgumentType()) { 1362 for (VariableArrayType* VA = FindVA(E->getArgumentType().getTypePtr()); 1363 VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) 1364 addStmt(VA->getSizeExpr()); 1365 } 1366 1367 return Block; 1368} 1369 1370/// VisitStmtExpr - Utility method to handle (nested) statement 1371/// expressions (a GCC extension). 1372CFGBlock* CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) { 1373 if (asc.alwaysAdd()) { 1374 autoCreateBlock(); 1375 AppendStmt(Block, SE); 1376 } 1377 return VisitCompoundStmt(SE->getSubStmt()); 1378} 1379 1380CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { 1381 // "switch" is a control-flow statement. Thus we stop processing the current 1382 // block. 1383 CFGBlock* SwitchSuccessor = NULL; 1384 1385 if (Block) { 1386 if (!FinishBlock(Block)) 1387 return 0; 1388 SwitchSuccessor = Block; 1389 } else SwitchSuccessor = Succ; 1390 1391 // Save the current "switch" context. 1392 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock), 1393 save_break(BreakTargetBlock), 1394 save_default(DefaultCaseBlock); 1395 1396 // Set the "default" case to be the block after the switch statement. If the 1397 // switch statement contains a "default:", this value will be overwritten with 1398 // the block for that code. 1399 DefaultCaseBlock = SwitchSuccessor; 1400 1401 // Create a new block that will contain the switch statement. 1402 SwitchTerminatedBlock = createBlock(false); 1403 1404 // Now process the switch body. The code after the switch is the implicit 1405 // successor. 1406 Succ = SwitchSuccessor; 1407 BreakTargetBlock = SwitchSuccessor; 1408 1409 // When visiting the body, the case statements should automatically get linked 1410 // up to the switch. We also don't keep a pointer to the body, since all 1411 // control-flow from the switch goes to case/default statements. 1412 assert (Terminator->getBody() && "switch must contain a non-NULL body"); 1413 Block = NULL; 1414 CFGBlock *BodyBlock = addStmt(Terminator->getBody()); 1415 if (Block) { 1416 if (!FinishBlock(BodyBlock)) 1417 return 0; 1418 } 1419 1420 // If we have no "default:" case, the default transition is to the code 1421 // following the switch body. 1422 AddSuccessor(SwitchTerminatedBlock, DefaultCaseBlock); 1423 1424 // Add the terminator and condition in the switch block. 1425 SwitchTerminatedBlock->setTerminator(Terminator); 1426 assert (Terminator->getCond() && "switch condition must be non-NULL"); 1427 Block = SwitchTerminatedBlock; 1428 Block = addStmt(Terminator->getCond()); 1429 1430 // Finally, if the SwitchStmt contains a condition variable, add both the 1431 // SwitchStmt and the condition variable initialization to the CFG. 1432 if (VarDecl *VD = Terminator->getConditionVariable()) { 1433 if (Expr *Init = VD->getInit()) { 1434 autoCreateBlock(); 1435 AppendStmt(Block, Terminator, AddStmtChoice::AlwaysAdd); 1436 addStmt(Init); 1437 } 1438 } 1439 1440 return Block; 1441} 1442 1443CFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* CS) { 1444 // CaseStmts are essentially labels, so they are the first statement in a 1445 // block. 1446 1447 if (CS->getSubStmt()) 1448 addStmt(CS->getSubStmt()); 1449 1450 CFGBlock* CaseBlock = Block; 1451 if (!CaseBlock) 1452 CaseBlock = createBlock(); 1453 1454 // Cases statements partition blocks, so this is the top of the basic block we 1455 // were processing (the "case XXX:" is the label). 1456 CaseBlock->setLabel(CS); 1457 1458 if (!FinishBlock(CaseBlock)) 1459 return 0; 1460 1461 // Add this block to the list of successors for the block with the switch 1462 // statement. 1463 assert(SwitchTerminatedBlock); 1464 AddSuccessor(SwitchTerminatedBlock, CaseBlock); 1465 1466 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1467 Block = NULL; 1468 1469 // This block is now the implicit successor of other blocks. 1470 Succ = CaseBlock; 1471 1472 return CaseBlock; 1473} 1474 1475CFGBlock* CFGBuilder::VisitDefaultStmt(DefaultStmt* Terminator) { 1476 if (Terminator->getSubStmt()) 1477 addStmt(Terminator->getSubStmt()); 1478 1479 DefaultCaseBlock = Block; 1480 1481 if (!DefaultCaseBlock) 1482 DefaultCaseBlock = createBlock(); 1483 1484 // Default statements partition blocks, so this is the top of the basic block 1485 // we were processing (the "default:" is the label). 1486 DefaultCaseBlock->setLabel(Terminator); 1487 1488 if (!FinishBlock(DefaultCaseBlock)) 1489 return 0; 1490 1491 // Unlike case statements, we don't add the default block to the successors 1492 // for the switch statement immediately. This is done when we finish 1493 // processing the switch statement. This allows for the default case 1494 // (including a fall-through to the code after the switch statement) to always 1495 // be the last successor of a switch-terminated block. 1496 1497 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1498 Block = NULL; 1499 1500 // This block is now the implicit successor of other blocks. 1501 Succ = DefaultCaseBlock; 1502 1503 return DefaultCaseBlock; 1504} 1505 1506CFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1507 // Lazily create the indirect-goto dispatch block if there isn't one already. 1508 CFGBlock* IBlock = cfg->getIndirectGotoBlock(); 1509 1510 if (!IBlock) { 1511 IBlock = createBlock(false); 1512 cfg->setIndirectGotoBlock(IBlock); 1513 } 1514 1515 // IndirectGoto is a control-flow statement. Thus we stop processing the 1516 // current block and create a new one. 1517 if (Block && !FinishBlock(Block)) 1518 return 0; 1519 1520 Block = createBlock(false); 1521 Block->setTerminator(I); 1522 AddSuccessor(Block, IBlock); 1523 return addStmt(I->getTarget()); 1524} 1525 1526} // end anonymous namespace 1527 1528/// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has 1529/// no successors or predecessors. If this is the first block created in the 1530/// CFG, it is automatically set to be the Entry and Exit of the CFG. 1531CFGBlock* CFG::createBlock() { 1532 bool first_block = begin() == end(); 1533 1534 // Create the block. 1535 CFGBlock *Mem = getAllocator().Allocate<CFGBlock>(); 1536 new (Mem) CFGBlock(NumBlockIDs++, BlkBVC); 1537 Blocks.push_back(Mem, BlkBVC); 1538 1539 // If this is the first block, set it as the Entry and Exit. 1540 if (first_block) 1541 Entry = Exit = &back(); 1542 1543 // Return the block. 1544 return &back(); 1545} 1546 1547/// buildCFG - Constructs a CFG from an AST. Ownership of the returned 1548/// CFG is returned to the caller. 1549CFG* CFG::buildCFG(Stmt* Statement, ASTContext *C) { 1550 CFGBuilder Builder; 1551 return Builder.buildCFG(Statement, C); 1552} 1553 1554//===----------------------------------------------------------------------===// 1555// CFG: Queries for BlkExprs. 1556//===----------------------------------------------------------------------===// 1557 1558namespace { 1559 typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy; 1560} 1561 1562static void FindSubExprAssignments(Stmt *S, 1563 llvm::SmallPtrSet<Expr*,50>& Set) { 1564 if (!S) 1565 return; 1566 1567 for (Stmt::child_iterator I=S->child_begin(), E=S->child_end(); I!=E; ++I) { 1568 Stmt *child = *I; 1569 if (!child) 1570 continue; 1571 1572 if (BinaryOperator* B = dyn_cast<BinaryOperator>(child)) 1573 if (B->isAssignmentOp()) Set.insert(B); 1574 1575 FindSubExprAssignments(child, Set); 1576 } 1577} 1578 1579static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { 1580 BlkExprMapTy* M = new BlkExprMapTy(); 1581 1582 // Look for assignments that are used as subexpressions. These are the only 1583 // assignments that we want to *possibly* register as a block-level 1584 // expression. Basically, if an assignment occurs both in a subexpression and 1585 // at the block-level, it is a block-level expression. 1586 llvm::SmallPtrSet<Expr*,50> SubExprAssignments; 1587 1588 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) 1589 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) 1590 FindSubExprAssignments(*BI, SubExprAssignments); 1591 1592 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { 1593 1594 // Iterate over the statements again on identify the Expr* and Stmt* at the 1595 // block-level that are block-level expressions. 1596 1597 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) 1598 if (Expr* Exp = dyn_cast<Expr>(*BI)) { 1599 1600 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { 1601 // Assignment expressions that are not nested within another 1602 // expression are really "statements" whose value is never used by 1603 // another expression. 1604 if (B->isAssignmentOp() && !SubExprAssignments.count(Exp)) 1605 continue; 1606 } else if (const StmtExpr* Terminator = dyn_cast<StmtExpr>(Exp)) { 1607 // Special handling for statement expressions. The last statement in 1608 // the statement expression is also a block-level expr. 1609 const CompoundStmt* C = Terminator->getSubStmt(); 1610 if (!C->body_empty()) { 1611 unsigned x = M->size(); 1612 (*M)[C->body_back()] = x; 1613 } 1614 } 1615 1616 unsigned x = M->size(); 1617 (*M)[Exp] = x; 1618 } 1619 1620 // Look at terminators. The condition is a block-level expression. 1621 1622 Stmt* S = (*I)->getTerminatorCondition(); 1623 1624 if (S && M->find(S) == M->end()) { 1625 unsigned x = M->size(); 1626 (*M)[S] = x; 1627 } 1628 } 1629 1630 return M; 1631} 1632 1633CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt* S) { 1634 assert(S != NULL); 1635 if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); } 1636 1637 BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap); 1638 BlkExprMapTy::iterator I = M->find(S); 1639 1640 if (I == M->end()) return CFG::BlkExprNumTy(); 1641 else return CFG::BlkExprNumTy(I->second); 1642} 1643 1644unsigned CFG::getNumBlkExprs() { 1645 if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap)) 1646 return M->size(); 1647 else { 1648 // We assume callers interested in the number of BlkExprs will want 1649 // the map constructed if it doesn't already exist. 1650 BlkExprMap = (void*) PopulateBlkExprMap(*this); 1651 return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); 1652 } 1653} 1654 1655//===----------------------------------------------------------------------===// 1656// Cleanup: CFG dstor. 1657//===----------------------------------------------------------------------===// 1658 1659CFG::~CFG() { 1660 delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap); 1661} 1662 1663//===----------------------------------------------------------------------===// 1664// CFG pretty printing 1665//===----------------------------------------------------------------------===// 1666 1667namespace { 1668 1669class StmtPrinterHelper : public PrinterHelper { 1670 1671 typedef llvm::DenseMap<Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; 1672 StmtMapTy StmtMap; 1673 signed CurrentBlock; 1674 unsigned CurrentStmt; 1675 const LangOptions &LangOpts; 1676public: 1677 1678 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) 1679 : CurrentBlock(0), CurrentStmt(0), LangOpts(LO) { 1680 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { 1681 unsigned j = 1; 1682 for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ; 1683 BI != BEnd; ++BI, ++j ) 1684 StmtMap[*BI] = std::make_pair((*I)->getBlockID(),j); 1685 } 1686 } 1687 1688 virtual ~StmtPrinterHelper() {} 1689 1690 const LangOptions &getLangOpts() const { return LangOpts; } 1691 void setBlockID(signed i) { CurrentBlock = i; } 1692 void setStmtID(unsigned i) { CurrentStmt = i; } 1693 1694 virtual bool handledStmt(Stmt* Terminator, llvm::raw_ostream& OS) { 1695 1696 StmtMapTy::iterator I = StmtMap.find(Terminator); 1697 1698 if (I == StmtMap.end()) 1699 return false; 1700 1701 if (CurrentBlock >= 0 && I->second.first == (unsigned) CurrentBlock 1702 && I->second.second == CurrentStmt) 1703 return false; 1704 1705 OS << "[B" << I->second.first << "." << I->second.second << "]"; 1706 return true; 1707 } 1708}; 1709} // end anonymous namespace 1710 1711 1712namespace { 1713class CFGBlockTerminatorPrint 1714 : public StmtVisitor<CFGBlockTerminatorPrint,void> { 1715 1716 llvm::raw_ostream& OS; 1717 StmtPrinterHelper* Helper; 1718 PrintingPolicy Policy; 1719 1720public: 1721 CFGBlockTerminatorPrint(llvm::raw_ostream& os, StmtPrinterHelper* helper, 1722 const PrintingPolicy &Policy) 1723 : OS(os), Helper(helper), Policy(Policy) {} 1724 1725 void VisitIfStmt(IfStmt* I) { 1726 OS << "if "; 1727 I->getCond()->printPretty(OS,Helper,Policy); 1728 } 1729 1730 // Default case. 1731 void VisitStmt(Stmt* Terminator) { 1732 Terminator->printPretty(OS, Helper, Policy); 1733 } 1734 1735 void VisitForStmt(ForStmt* F) { 1736 OS << "for (" ; 1737 if (F->getInit()) OS << "..."; 1738 OS << "; "; 1739 if (Stmt* C = F->getCond()) C->printPretty(OS, Helper, Policy); 1740 OS << "; "; 1741 if (F->getInc()) OS << "..."; 1742 OS << ")"; 1743 } 1744 1745 void VisitWhileStmt(WhileStmt* W) { 1746 OS << "while " ; 1747 if (Stmt* C = W->getCond()) C->printPretty(OS, Helper, Policy); 1748 } 1749 1750 void VisitDoStmt(DoStmt* D) { 1751 OS << "do ... while "; 1752 if (Stmt* C = D->getCond()) C->printPretty(OS, Helper, Policy); 1753 } 1754 1755 void VisitSwitchStmt(SwitchStmt* Terminator) { 1756 OS << "switch "; 1757 Terminator->getCond()->printPretty(OS, Helper, Policy); 1758 } 1759 1760 void VisitConditionalOperator(ConditionalOperator* C) { 1761 C->getCond()->printPretty(OS, Helper, Policy); 1762 OS << " ? ... : ..."; 1763 } 1764 1765 void VisitChooseExpr(ChooseExpr* C) { 1766 OS << "__builtin_choose_expr( "; 1767 C->getCond()->printPretty(OS, Helper, Policy); 1768 OS << " )"; 1769 } 1770 1771 void VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1772 OS << "goto *"; 1773 I->getTarget()->printPretty(OS, Helper, Policy); 1774 } 1775 1776 void VisitBinaryOperator(BinaryOperator* B) { 1777 if (!B->isLogicalOp()) { 1778 VisitExpr(B); 1779 return; 1780 } 1781 1782 B->getLHS()->printPretty(OS, Helper, Policy); 1783 1784 switch (B->getOpcode()) { 1785 case BinaryOperator::LOr: 1786 OS << " || ..."; 1787 return; 1788 case BinaryOperator::LAnd: 1789 OS << " && ..."; 1790 return; 1791 default: 1792 assert(false && "Invalid logical operator."); 1793 } 1794 } 1795 1796 void VisitExpr(Expr* E) { 1797 E->printPretty(OS, Helper, Policy); 1798 } 1799}; 1800} // end anonymous namespace 1801 1802 1803static void print_stmt(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, 1804 Stmt* Terminator) { 1805 if (Helper) { 1806 // special printing for statement-expressions. 1807 if (StmtExpr* SE = dyn_cast<StmtExpr>(Terminator)) { 1808 CompoundStmt* Sub = SE->getSubStmt(); 1809 1810 if (Sub->child_begin() != Sub->child_end()) { 1811 OS << "({ ... ; "; 1812 Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); 1813 OS << " })\n"; 1814 return; 1815 } 1816 } 1817 1818 // special printing for comma expressions. 1819 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Terminator)) { 1820 if (B->getOpcode() == BinaryOperator::Comma) { 1821 OS << "... , "; 1822 Helper->handledStmt(B->getRHS(),OS); 1823 OS << '\n'; 1824 return; 1825 } 1826 } 1827 } 1828 1829 Terminator->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 1830 1831 // Expressions need a newline. 1832 if (isa<Expr>(Terminator)) OS << '\n'; 1833} 1834 1835static void print_block(llvm::raw_ostream& OS, const CFG* cfg, 1836 const CFGBlock& B, 1837 StmtPrinterHelper* Helper, bool print_edges) { 1838 1839 if (Helper) Helper->setBlockID(B.getBlockID()); 1840 1841 // Print the header. 1842 OS << "\n [ B" << B.getBlockID(); 1843 1844 if (&B == &cfg->getEntry()) 1845 OS << " (ENTRY) ]\n"; 1846 else if (&B == &cfg->getExit()) 1847 OS << " (EXIT) ]\n"; 1848 else if (&B == cfg->getIndirectGotoBlock()) 1849 OS << " (INDIRECT GOTO DISPATCH) ]\n"; 1850 else 1851 OS << " ]\n"; 1852 1853 // Print the label of this block. 1854 if (Stmt* Terminator = const_cast<Stmt*>(B.getLabel())) { 1855 1856 if (print_edges) 1857 OS << " "; 1858 1859 if (LabelStmt* L = dyn_cast<LabelStmt>(Terminator)) 1860 OS << L->getName(); 1861 else if (CaseStmt* C = dyn_cast<CaseStmt>(Terminator)) { 1862 OS << "case "; 1863 C->getLHS()->printPretty(OS, Helper, 1864 PrintingPolicy(Helper->getLangOpts())); 1865 if (C->getRHS()) { 1866 OS << " ... "; 1867 C->getRHS()->printPretty(OS, Helper, 1868 PrintingPolicy(Helper->getLangOpts())); 1869 } 1870 } else if (isa<DefaultStmt>(Terminator)) 1871 OS << "default"; 1872 else 1873 assert(false && "Invalid label statement in CFGBlock."); 1874 1875 OS << ":\n"; 1876 } 1877 1878 // Iterate through the statements in the block and print them. 1879 unsigned j = 1; 1880 1881 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; 1882 I != E ; ++I, ++j ) { 1883 1884 // Print the statement # in the basic block and the statement itself. 1885 if (print_edges) 1886 OS << " "; 1887 1888 OS << llvm::format("%3d", j) << ": "; 1889 1890 if (Helper) 1891 Helper->setStmtID(j); 1892 1893 print_stmt(OS,Helper,*I); 1894 } 1895 1896 // Print the terminator of this block. 1897 if (B.getTerminator()) { 1898 if (print_edges) 1899 OS << " "; 1900 1901 OS << " T: "; 1902 1903 if (Helper) Helper->setBlockID(-1); 1904 1905 CFGBlockTerminatorPrint TPrinter(OS, Helper, 1906 PrintingPolicy(Helper->getLangOpts())); 1907 TPrinter.Visit(const_cast<Stmt*>(B.getTerminator())); 1908 OS << '\n'; 1909 } 1910 1911 if (print_edges) { 1912 // Print the predecessors of this block. 1913 OS << " Predecessors (" << B.pred_size() << "):"; 1914 unsigned i = 0; 1915 1916 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); 1917 I != E; ++I, ++i) { 1918 1919 if (i == 8 || (i-8) == 0) 1920 OS << "\n "; 1921 1922 OS << " B" << (*I)->getBlockID(); 1923 } 1924 1925 OS << '\n'; 1926 1927 // Print the successors of this block. 1928 OS << " Successors (" << B.succ_size() << "):"; 1929 i = 0; 1930 1931 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); 1932 I != E; ++I, ++i) { 1933 1934 if (i == 8 || (i-8) % 10 == 0) 1935 OS << "\n "; 1936 1937 if (*I) 1938 OS << " B" << (*I)->getBlockID(); 1939 else 1940 OS << " NULL"; 1941 } 1942 1943 OS << '\n'; 1944 } 1945} 1946 1947 1948/// dump - A simple pretty printer of a CFG that outputs to stderr. 1949void CFG::dump(const LangOptions &LO) const { print(llvm::errs(), LO); } 1950 1951/// print - A simple pretty printer of a CFG that outputs to an ostream. 1952void CFG::print(llvm::raw_ostream &OS, const LangOptions &LO) const { 1953 StmtPrinterHelper Helper(this, LO); 1954 1955 // Print the entry block. 1956 print_block(OS, this, getEntry(), &Helper, true); 1957 1958 // Iterate through the CFGBlocks and print them one by one. 1959 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { 1960 // Skip the entry block, because we already printed it. 1961 if (&(**I) == &getEntry() || &(**I) == &getExit()) 1962 continue; 1963 1964 print_block(OS, this, **I, &Helper, true); 1965 } 1966 1967 // Print the exit block. 1968 print_block(OS, this, getExit(), &Helper, true); 1969 OS.flush(); 1970} 1971 1972/// dump - A simply pretty printer of a CFGBlock that outputs to stderr. 1973void CFGBlock::dump(const CFG* cfg, const LangOptions &LO) const { 1974 print(llvm::errs(), cfg, LO); 1975} 1976 1977/// print - A simple pretty printer of a CFGBlock that outputs to an ostream. 1978/// Generally this will only be called from CFG::print. 1979void CFGBlock::print(llvm::raw_ostream& OS, const CFG* cfg, 1980 const LangOptions &LO) const { 1981 StmtPrinterHelper Helper(cfg, LO); 1982 print_block(OS, cfg, *this, &Helper, true); 1983} 1984 1985/// printTerminator - A simple pretty printer of the terminator of a CFGBlock. 1986void CFGBlock::printTerminator(llvm::raw_ostream &OS, 1987 const LangOptions &LO) const { 1988 CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO)); 1989 TPrinter.Visit(const_cast<Stmt*>(getTerminator())); 1990} 1991 1992Stmt* CFGBlock::getTerminatorCondition() { 1993 1994 if (!Terminator) 1995 return NULL; 1996 1997 Expr* E = NULL; 1998 1999 switch (Terminator->getStmtClass()) { 2000 default: 2001 break; 2002 2003 case Stmt::ForStmtClass: 2004 E = cast<ForStmt>(Terminator)->getCond(); 2005 break; 2006 2007 case Stmt::WhileStmtClass: 2008 E = cast<WhileStmt>(Terminator)->getCond(); 2009 break; 2010 2011 case Stmt::DoStmtClass: 2012 E = cast<DoStmt>(Terminator)->getCond(); 2013 break; 2014 2015 case Stmt::IfStmtClass: 2016 E = cast<IfStmt>(Terminator)->getCond(); 2017 break; 2018 2019 case Stmt::ChooseExprClass: 2020 E = cast<ChooseExpr>(Terminator)->getCond(); 2021 break; 2022 2023 case Stmt::IndirectGotoStmtClass: 2024 E = cast<IndirectGotoStmt>(Terminator)->getTarget(); 2025 break; 2026 2027 case Stmt::SwitchStmtClass: 2028 E = cast<SwitchStmt>(Terminator)->getCond(); 2029 break; 2030 2031 case Stmt::ConditionalOperatorClass: 2032 E = cast<ConditionalOperator>(Terminator)->getCond(); 2033 break; 2034 2035 case Stmt::BinaryOperatorClass: // '&&' and '||' 2036 E = cast<BinaryOperator>(Terminator)->getLHS(); 2037 break; 2038 2039 case Stmt::ObjCForCollectionStmtClass: 2040 return Terminator; 2041 } 2042 2043 return E ? E->IgnoreParens() : NULL; 2044} 2045 2046bool CFGBlock::hasBinaryBranchTerminator() const { 2047 2048 if (!Terminator) 2049 return false; 2050 2051 Expr* E = NULL; 2052 2053 switch (Terminator->getStmtClass()) { 2054 default: 2055 return false; 2056 2057 case Stmt::ForStmtClass: 2058 case Stmt::WhileStmtClass: 2059 case Stmt::DoStmtClass: 2060 case Stmt::IfStmtClass: 2061 case Stmt::ChooseExprClass: 2062 case Stmt::ConditionalOperatorClass: 2063 case Stmt::BinaryOperatorClass: 2064 return true; 2065 } 2066 2067 return E ? E->IgnoreParens() : NULL; 2068} 2069 2070 2071//===----------------------------------------------------------------------===// 2072// CFG Graphviz Visualization 2073//===----------------------------------------------------------------------===// 2074 2075 2076#ifndef NDEBUG 2077static StmtPrinterHelper* GraphHelper; 2078#endif 2079 2080void CFG::viewCFG(const LangOptions &LO) const { 2081#ifndef NDEBUG 2082 StmtPrinterHelper H(this, LO); 2083 GraphHelper = &H; 2084 llvm::ViewGraph(this,"CFG"); 2085 GraphHelper = NULL; 2086#endif 2087} 2088 2089namespace llvm { 2090template<> 2091struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { 2092 2093 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 2094 2095 static std::string getNodeLabel(const CFGBlock* Node, const CFG* Graph) { 2096 2097#ifndef NDEBUG 2098 std::string OutSStr; 2099 llvm::raw_string_ostream Out(OutSStr); 2100 print_block(Out,Graph, *Node, GraphHelper, false); 2101 std::string& OutStr = Out.str(); 2102 2103 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); 2104 2105 // Process string output to make it nicer... 2106 for (unsigned i = 0; i != OutStr.length(); ++i) 2107 if (OutStr[i] == '\n') { // Left justify 2108 OutStr[i] = '\\'; 2109 OutStr.insert(OutStr.begin()+i+1, 'l'); 2110 } 2111 2112 return OutStr; 2113#else 2114 return ""; 2115#endif 2116 } 2117}; 2118} // end namespace llvm 2119