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