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