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