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