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