CFG.cpp revision 079bd72439448b78629a28da6b1f8abe2cdeaf4d
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 // Save the current "try" context. 1602 SaveAndRestore<CFGBlock*> save_try(TryTerminatedBlock); 1603 1604 // Create a new block that will contain the try statement. 1605 TryTerminatedBlock = createBlock(false); 1606 // Add the terminator in the try block. 1607 TryTerminatedBlock->setTerminator(Terminator); 1608 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 Block = NULL; 1614 CFGBlock *CatchBlock = VisitCXXCatchStmt(CS); 1615 if (CatchBlock == 0) 1616 return 0; 1617 // Add this block to the list of successors for the block with the try 1618 // statement. 1619 AddSuccessor(TryTerminatedBlock, CatchBlock); 1620 } 1621 1622 // The code after the try is the implicit successor. 1623 Succ = TrySuccessor; 1624 1625 // When visiting the body, the case statements should automatically get linked 1626 // up to the try. 1627 assert(Terminator->getTryBlock() && "try must contain a non-NULL body"); 1628 Block = NULL; 1629 Block = addStmt(Terminator->getTryBlock()); 1630 return Block; 1631} 1632 1633CFGBlock* CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt* CS) { 1634 // CXXCatchStmt are treated like labels, so they are the first statement in a 1635 // block. 1636 1637 if (CS->getHandlerBlock()) 1638 addStmt(CS->getHandlerBlock()); 1639 1640 CFGBlock* CatchBlock = Block; 1641 if (!CatchBlock) 1642 CatchBlock = createBlock(); 1643 1644 CatchBlock->setLabel(CS); 1645 1646 if (!FinishBlock(CatchBlock)) 1647 return 0; 1648 1649 // We set Block to NULL to allow lazy creation of a new block (if necessary) 1650 Block = NULL; 1651 1652 return CatchBlock; 1653} 1654 1655CFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1656 // Lazily create the indirect-goto dispatch block if there isn't one already. 1657 CFGBlock* IBlock = cfg->getIndirectGotoBlock(); 1658 1659 if (!IBlock) { 1660 IBlock = createBlock(false); 1661 cfg->setIndirectGotoBlock(IBlock); 1662 } 1663 1664 // IndirectGoto is a control-flow statement. Thus we stop processing the 1665 // current block and create a new one. 1666 if (Block && !FinishBlock(Block)) 1667 return 0; 1668 1669 Block = createBlock(false); 1670 Block->setTerminator(I); 1671 AddSuccessor(Block, IBlock); 1672 return addStmt(I->getTarget()); 1673} 1674 1675} // end anonymous namespace 1676 1677/// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has 1678/// no successors or predecessors. If this is the first block created in the 1679/// CFG, it is automatically set to be the Entry and Exit of the CFG. 1680CFGBlock* CFG::createBlock() { 1681 bool first_block = begin() == end(); 1682 1683 // Create the block. 1684 CFGBlock *Mem = getAllocator().Allocate<CFGBlock>(); 1685 new (Mem) CFGBlock(NumBlockIDs++, BlkBVC); 1686 Blocks.push_back(Mem, BlkBVC); 1687 1688 // If this is the first block, set it as the Entry and Exit. 1689 if (first_block) 1690 Entry = Exit = &back(); 1691 1692 // Return the block. 1693 return &back(); 1694} 1695 1696/// buildCFG - Constructs a CFG from an AST. Ownership of the returned 1697/// CFG is returned to the caller. 1698CFG* CFG::buildCFG(Stmt* Statement, ASTContext *C, bool AddScopes) { 1699 CFGBuilder Builder; 1700 return Builder.buildCFG(Statement, C, AddScopes); 1701} 1702 1703//===----------------------------------------------------------------------===// 1704// CFG: Queries for BlkExprs. 1705//===----------------------------------------------------------------------===// 1706 1707namespace { 1708 typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy; 1709} 1710 1711static void FindSubExprAssignments(Stmt *S, 1712 llvm::SmallPtrSet<Expr*,50>& Set) { 1713 if (!S) 1714 return; 1715 1716 for (Stmt::child_iterator I=S->child_begin(), E=S->child_end(); I!=E; ++I) { 1717 Stmt *child = *I; 1718 if (!child) 1719 continue; 1720 1721 if (BinaryOperator* B = dyn_cast<BinaryOperator>(child)) 1722 if (B->isAssignmentOp()) Set.insert(B); 1723 1724 FindSubExprAssignments(child, Set); 1725 } 1726} 1727 1728static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { 1729 BlkExprMapTy* M = new BlkExprMapTy(); 1730 1731 // Look for assignments that are used as subexpressions. These are the only 1732 // assignments that we want to *possibly* register as a block-level 1733 // expression. Basically, if an assignment occurs both in a subexpression and 1734 // at the block-level, it is a block-level expression. 1735 llvm::SmallPtrSet<Expr*,50> SubExprAssignments; 1736 1737 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) 1738 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) 1739 FindSubExprAssignments(*BI, SubExprAssignments); 1740 1741 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { 1742 1743 // Iterate over the statements again on identify the Expr* and Stmt* at the 1744 // block-level that are block-level expressions. 1745 1746 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) 1747 if (Expr* Exp = dyn_cast<Expr>(*BI)) { 1748 1749 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { 1750 // Assignment expressions that are not nested within another 1751 // expression are really "statements" whose value is never used by 1752 // another expression. 1753 if (B->isAssignmentOp() && !SubExprAssignments.count(Exp)) 1754 continue; 1755 } else if (const StmtExpr* Terminator = dyn_cast<StmtExpr>(Exp)) { 1756 // Special handling for statement expressions. The last statement in 1757 // the statement expression is also a block-level expr. 1758 const CompoundStmt* C = Terminator->getSubStmt(); 1759 if (!C->body_empty()) { 1760 unsigned x = M->size(); 1761 (*M)[C->body_back()] = x; 1762 } 1763 } 1764 1765 unsigned x = M->size(); 1766 (*M)[Exp] = x; 1767 } 1768 1769 // Look at terminators. The condition is a block-level expression. 1770 1771 Stmt* S = (*I)->getTerminatorCondition(); 1772 1773 if (S && M->find(S) == M->end()) { 1774 unsigned x = M->size(); 1775 (*M)[S] = x; 1776 } 1777 } 1778 1779 return M; 1780} 1781 1782CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt* S) { 1783 assert(S != NULL); 1784 if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); } 1785 1786 BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap); 1787 BlkExprMapTy::iterator I = M->find(S); 1788 return (I == M->end()) ? CFG::BlkExprNumTy() : CFG::BlkExprNumTy(I->second); 1789} 1790 1791unsigned CFG::getNumBlkExprs() { 1792 if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap)) 1793 return M->size(); 1794 else { 1795 // We assume callers interested in the number of BlkExprs will want 1796 // the map constructed if it doesn't already exist. 1797 BlkExprMap = (void*) PopulateBlkExprMap(*this); 1798 return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); 1799 } 1800} 1801 1802//===----------------------------------------------------------------------===// 1803// Cleanup: CFG dstor. 1804//===----------------------------------------------------------------------===// 1805 1806CFG::~CFG() { 1807 delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap); 1808} 1809 1810//===----------------------------------------------------------------------===// 1811// CFG pretty printing 1812//===----------------------------------------------------------------------===// 1813 1814namespace { 1815 1816class StmtPrinterHelper : public PrinterHelper { 1817 typedef llvm::DenseMap<Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; 1818 StmtMapTy StmtMap; 1819 signed CurrentBlock; 1820 unsigned CurrentStmt; 1821 const LangOptions &LangOpts; 1822public: 1823 1824 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) 1825 : CurrentBlock(0), CurrentStmt(0), LangOpts(LO) { 1826 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { 1827 unsigned j = 1; 1828 for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ; 1829 BI != BEnd; ++BI, ++j ) 1830 StmtMap[*BI] = std::make_pair((*I)->getBlockID(),j); 1831 } 1832 } 1833 1834 virtual ~StmtPrinterHelper() {} 1835 1836 const LangOptions &getLangOpts() const { return LangOpts; } 1837 void setBlockID(signed i) { CurrentBlock = i; } 1838 void setStmtID(unsigned i) { CurrentStmt = i; } 1839 1840 virtual bool handledStmt(Stmt* Terminator, llvm::raw_ostream& OS) { 1841 1842 StmtMapTy::iterator I = StmtMap.find(Terminator); 1843 1844 if (I == StmtMap.end()) 1845 return false; 1846 1847 if (CurrentBlock >= 0 && I->second.first == (unsigned) CurrentBlock 1848 && I->second.second == CurrentStmt) { 1849 return false; 1850 } 1851 1852 OS << "[B" << I->second.first << "." << I->second.second << "]"; 1853 return true; 1854 } 1855}; 1856} // end anonymous namespace 1857 1858 1859namespace { 1860class CFGBlockTerminatorPrint 1861 : public StmtVisitor<CFGBlockTerminatorPrint,void> { 1862 1863 llvm::raw_ostream& OS; 1864 StmtPrinterHelper* Helper; 1865 PrintingPolicy Policy; 1866public: 1867 CFGBlockTerminatorPrint(llvm::raw_ostream& os, StmtPrinterHelper* helper, 1868 const PrintingPolicy &Policy) 1869 : OS(os), Helper(helper), Policy(Policy) {} 1870 1871 void VisitIfStmt(IfStmt* I) { 1872 OS << "if "; 1873 I->getCond()->printPretty(OS,Helper,Policy); 1874 } 1875 1876 // Default case. 1877 void VisitStmt(Stmt* Terminator) { 1878 Terminator->printPretty(OS, Helper, Policy); 1879 } 1880 1881 void VisitForStmt(ForStmt* F) { 1882 OS << "for (" ; 1883 if (F->getInit()) 1884 OS << "..."; 1885 OS << "; "; 1886 if (Stmt* C = F->getCond()) 1887 C->printPretty(OS, Helper, Policy); 1888 OS << "; "; 1889 if (F->getInc()) 1890 OS << "..."; 1891 OS << ")"; 1892 } 1893 1894 void VisitWhileStmt(WhileStmt* W) { 1895 OS << "while " ; 1896 if (Stmt* C = W->getCond()) 1897 C->printPretty(OS, Helper, Policy); 1898 } 1899 1900 void VisitDoStmt(DoStmt* D) { 1901 OS << "do ... while "; 1902 if (Stmt* C = D->getCond()) 1903 C->printPretty(OS, Helper, Policy); 1904 } 1905 1906 void VisitSwitchStmt(SwitchStmt* Terminator) { 1907 OS << "switch "; 1908 Terminator->getCond()->printPretty(OS, Helper, Policy); 1909 } 1910 1911 void VisitCXXTryStmt(CXXTryStmt* CS) { 1912 OS << "try ..."; 1913 } 1914 1915 void VisitConditionalOperator(ConditionalOperator* C) { 1916 C->getCond()->printPretty(OS, Helper, Policy); 1917 OS << " ? ... : ..."; 1918 } 1919 1920 void VisitChooseExpr(ChooseExpr* C) { 1921 OS << "__builtin_choose_expr( "; 1922 C->getCond()->printPretty(OS, Helper, Policy); 1923 OS << " )"; 1924 } 1925 1926 void VisitIndirectGotoStmt(IndirectGotoStmt* I) { 1927 OS << "goto *"; 1928 I->getTarget()->printPretty(OS, Helper, Policy); 1929 } 1930 1931 void VisitBinaryOperator(BinaryOperator* B) { 1932 if (!B->isLogicalOp()) { 1933 VisitExpr(B); 1934 return; 1935 } 1936 1937 B->getLHS()->printPretty(OS, Helper, Policy); 1938 1939 switch (B->getOpcode()) { 1940 case BinaryOperator::LOr: 1941 OS << " || ..."; 1942 return; 1943 case BinaryOperator::LAnd: 1944 OS << " && ..."; 1945 return; 1946 default: 1947 assert(false && "Invalid logical operator."); 1948 } 1949 } 1950 1951 void VisitExpr(Expr* E) { 1952 E->printPretty(OS, Helper, Policy); 1953 } 1954}; 1955} // end anonymous namespace 1956 1957 1958static void print_stmt(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, 1959 const CFGElement &E) { 1960 Stmt *Terminator = E; 1961 1962 if (E.asStartScope()) { 1963 OS << "start scope\n"; 1964 return; 1965 } 1966 if (E.asEndScope()) { 1967 OS << "end scope\n"; 1968 return; 1969 } 1970 1971 if (Helper) { 1972 // special printing for statement-expressions. 1973 if (StmtExpr* SE = dyn_cast<StmtExpr>(Terminator)) { 1974 CompoundStmt* Sub = SE->getSubStmt(); 1975 1976 if (Sub->child_begin() != Sub->child_end()) { 1977 OS << "({ ... ; "; 1978 Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); 1979 OS << " })\n"; 1980 return; 1981 } 1982 } 1983 1984 // special printing for comma expressions. 1985 if (BinaryOperator* B = dyn_cast<BinaryOperator>(Terminator)) { 1986 if (B->getOpcode() == BinaryOperator::Comma) { 1987 OS << "... , "; 1988 Helper->handledStmt(B->getRHS(),OS); 1989 OS << '\n'; 1990 return; 1991 } 1992 } 1993 } 1994 1995 Terminator->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 1996 1997 // Expressions need a newline. 1998 if (isa<Expr>(Terminator)) OS << '\n'; 1999} 2000 2001static void print_block(llvm::raw_ostream& OS, const CFG* cfg, 2002 const CFGBlock& B, 2003 StmtPrinterHelper* Helper, bool print_edges) { 2004 2005 if (Helper) Helper->setBlockID(B.getBlockID()); 2006 2007 // Print the header. 2008 OS << "\n [ B" << B.getBlockID(); 2009 2010 if (&B == &cfg->getEntry()) 2011 OS << " (ENTRY) ]\n"; 2012 else if (&B == &cfg->getExit()) 2013 OS << " (EXIT) ]\n"; 2014 else if (&B == cfg->getIndirectGotoBlock()) 2015 OS << " (INDIRECT GOTO DISPATCH) ]\n"; 2016 else 2017 OS << " ]\n"; 2018 2019 // Print the label of this block. 2020 if (Stmt* Label = const_cast<Stmt*>(B.getLabel())) { 2021 2022 if (print_edges) 2023 OS << " "; 2024 2025 if (LabelStmt* L = dyn_cast<LabelStmt>(Label)) 2026 OS << L->getName(); 2027 else if (CaseStmt* C = dyn_cast<CaseStmt>(Label)) { 2028 OS << "case "; 2029 C->getLHS()->printPretty(OS, Helper, 2030 PrintingPolicy(Helper->getLangOpts())); 2031 if (C->getRHS()) { 2032 OS << " ... "; 2033 C->getRHS()->printPretty(OS, Helper, 2034 PrintingPolicy(Helper->getLangOpts())); 2035 } 2036 } else if (isa<DefaultStmt>(Label)) 2037 OS << "default"; 2038 else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Label)) { 2039 OS << "catch ("; 2040 CS->getExceptionDecl()->print(OS, PrintingPolicy(Helper->getLangOpts()), 2041 0); 2042 OS << ")"; 2043 2044 } else 2045 assert(false && "Invalid label statement in CFGBlock."); 2046 2047 OS << ":\n"; 2048 } 2049 2050 // Iterate through the statements in the block and print them. 2051 unsigned j = 1; 2052 2053 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; 2054 I != E ; ++I, ++j ) { 2055 2056 // Print the statement # in the basic block and the statement itself. 2057 if (print_edges) 2058 OS << " "; 2059 2060 OS << llvm::format("%3d", j) << ": "; 2061 2062 if (Helper) 2063 Helper->setStmtID(j); 2064 2065 print_stmt(OS,Helper,*I); 2066 } 2067 2068 // Print the terminator of this block. 2069 if (B.getTerminator()) { 2070 if (print_edges) 2071 OS << " "; 2072 2073 OS << " T: "; 2074 2075 if (Helper) Helper->setBlockID(-1); 2076 2077 CFGBlockTerminatorPrint TPrinter(OS, Helper, 2078 PrintingPolicy(Helper->getLangOpts())); 2079 TPrinter.Visit(const_cast<Stmt*>(B.getTerminator())); 2080 OS << '\n'; 2081 } 2082 2083 if (print_edges) { 2084 // Print the predecessors of this block. 2085 OS << " Predecessors (" << B.pred_size() << "):"; 2086 unsigned i = 0; 2087 2088 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); 2089 I != E; ++I, ++i) { 2090 2091 if (i == 8 || (i-8) == 0) 2092 OS << "\n "; 2093 2094 OS << " B" << (*I)->getBlockID(); 2095 } 2096 2097 OS << '\n'; 2098 2099 // Print the successors of this block. 2100 OS << " Successors (" << B.succ_size() << "):"; 2101 i = 0; 2102 2103 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); 2104 I != E; ++I, ++i) { 2105 2106 if (i == 8 || (i-8) % 10 == 0) 2107 OS << "\n "; 2108 2109 if (*I) 2110 OS << " B" << (*I)->getBlockID(); 2111 else 2112 OS << " NULL"; 2113 } 2114 2115 OS << '\n'; 2116 } 2117} 2118 2119 2120/// dump - A simple pretty printer of a CFG that outputs to stderr. 2121void CFG::dump(const LangOptions &LO) const { print(llvm::errs(), LO); } 2122 2123/// print - A simple pretty printer of a CFG that outputs to an ostream. 2124void CFG::print(llvm::raw_ostream &OS, const LangOptions &LO) const { 2125 StmtPrinterHelper Helper(this, LO); 2126 2127 // Print the entry block. 2128 print_block(OS, this, getEntry(), &Helper, true); 2129 2130 // Iterate through the CFGBlocks and print them one by one. 2131 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { 2132 // Skip the entry block, because we already printed it. 2133 if (&(**I) == &getEntry() || &(**I) == &getExit()) 2134 continue; 2135 2136 print_block(OS, this, **I, &Helper, true); 2137 } 2138 2139 // Print the exit block. 2140 print_block(OS, this, getExit(), &Helper, true); 2141 OS.flush(); 2142} 2143 2144/// dump - A simply pretty printer of a CFGBlock that outputs to stderr. 2145void CFGBlock::dump(const CFG* cfg, const LangOptions &LO) const { 2146 print(llvm::errs(), cfg, LO); 2147} 2148 2149/// print - A simple pretty printer of a CFGBlock that outputs to an ostream. 2150/// Generally this will only be called from CFG::print. 2151void CFGBlock::print(llvm::raw_ostream& OS, const CFG* cfg, 2152 const LangOptions &LO) const { 2153 StmtPrinterHelper Helper(cfg, LO); 2154 print_block(OS, cfg, *this, &Helper, true); 2155} 2156 2157/// printTerminator - A simple pretty printer of the terminator of a CFGBlock. 2158void CFGBlock::printTerminator(llvm::raw_ostream &OS, 2159 const LangOptions &LO) const { 2160 CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO)); 2161 TPrinter.Visit(const_cast<Stmt*>(getTerminator())); 2162} 2163 2164Stmt* CFGBlock::getTerminatorCondition() { 2165 2166 if (!Terminator) 2167 return NULL; 2168 2169 Expr* E = NULL; 2170 2171 switch (Terminator->getStmtClass()) { 2172 default: 2173 break; 2174 2175 case Stmt::ForStmtClass: 2176 E = cast<ForStmt>(Terminator)->getCond(); 2177 break; 2178 2179 case Stmt::WhileStmtClass: 2180 E = cast<WhileStmt>(Terminator)->getCond(); 2181 break; 2182 2183 case Stmt::DoStmtClass: 2184 E = cast<DoStmt>(Terminator)->getCond(); 2185 break; 2186 2187 case Stmt::IfStmtClass: 2188 E = cast<IfStmt>(Terminator)->getCond(); 2189 break; 2190 2191 case Stmt::ChooseExprClass: 2192 E = cast<ChooseExpr>(Terminator)->getCond(); 2193 break; 2194 2195 case Stmt::IndirectGotoStmtClass: 2196 E = cast<IndirectGotoStmt>(Terminator)->getTarget(); 2197 break; 2198 2199 case Stmt::SwitchStmtClass: 2200 E = cast<SwitchStmt>(Terminator)->getCond(); 2201 break; 2202 2203 case Stmt::ConditionalOperatorClass: 2204 E = cast<ConditionalOperator>(Terminator)->getCond(); 2205 break; 2206 2207 case Stmt::BinaryOperatorClass: // '&&' and '||' 2208 E = cast<BinaryOperator>(Terminator)->getLHS(); 2209 break; 2210 2211 case Stmt::ObjCForCollectionStmtClass: 2212 return Terminator; 2213 } 2214 2215 return E ? E->IgnoreParens() : NULL; 2216} 2217 2218bool CFGBlock::hasBinaryBranchTerminator() const { 2219 2220 if (!Terminator) 2221 return false; 2222 2223 Expr* E = NULL; 2224 2225 switch (Terminator->getStmtClass()) { 2226 default: 2227 return false; 2228 2229 case Stmt::ForStmtClass: 2230 case Stmt::WhileStmtClass: 2231 case Stmt::DoStmtClass: 2232 case Stmt::IfStmtClass: 2233 case Stmt::ChooseExprClass: 2234 case Stmt::ConditionalOperatorClass: 2235 case Stmt::BinaryOperatorClass: 2236 return true; 2237 } 2238 2239 return E ? E->IgnoreParens() : NULL; 2240} 2241 2242 2243//===----------------------------------------------------------------------===// 2244// CFG Graphviz Visualization 2245//===----------------------------------------------------------------------===// 2246 2247 2248#ifndef NDEBUG 2249static StmtPrinterHelper* GraphHelper; 2250#endif 2251 2252void CFG::viewCFG(const LangOptions &LO) const { 2253#ifndef NDEBUG 2254 StmtPrinterHelper H(this, LO); 2255 GraphHelper = &H; 2256 llvm::ViewGraph(this,"CFG"); 2257 GraphHelper = NULL; 2258#endif 2259} 2260 2261namespace llvm { 2262template<> 2263struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { 2264 2265 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 2266 2267 static std::string getNodeLabel(const CFGBlock* Node, const CFG* Graph) { 2268 2269#ifndef NDEBUG 2270 std::string OutSStr; 2271 llvm::raw_string_ostream Out(OutSStr); 2272 print_block(Out,Graph, *Node, GraphHelper, false); 2273 std::string& OutStr = Out.str(); 2274 2275 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); 2276 2277 // Process string output to make it nicer... 2278 for (unsigned i = 0; i != OutStr.length(); ++i) 2279 if (OutStr[i] == '\n') { // Left justify 2280 OutStr[i] = '\\'; 2281 OutStr.insert(OutStr.begin()+i+1, 'l'); 2282 } 2283 2284 return OutStr; 2285#else 2286 return ""; 2287#endif 2288 } 2289}; 2290} // end namespace llvm 2291