CFG.cpp revision a08e7bc74b5635995fc50009f240dd3feb1999e2
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 "llvm/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 "clang/AST/CharUnits.h" 21#include "clang/Basic/AttrKinds.h" 22#include "llvm/Support/GraphWriter.h" 23#include "llvm/Support/Allocator.h" 24#include "llvm/Support/Format.h" 25#include "llvm/ADT/DenseMap.h" 26#include "llvm/ADT/SmallPtrSet.h" 27#include "llvm/ADT/OwningPtr.h" 28 29using namespace clang; 30 31namespace { 32 33static SourceLocation GetEndLoc(Decl *D) { 34 if (VarDecl *VD = dyn_cast<VarDecl>(D)) 35 if (Expr *Ex = VD->getInit()) 36 return Ex->getSourceRange().getEnd(); 37 return D->getLocation(); 38} 39 40class CFGBuilder; 41 42/// The CFG builder uses a recursive algorithm to build the CFG. When 43/// we process an expression, sometimes we know that we must add the 44/// subexpressions as block-level expressions. For example: 45/// 46/// exp1 || exp2 47/// 48/// When processing the '||' expression, we know that exp1 and exp2 49/// need to be added as block-level expressions, even though they 50/// might not normally need to be. AddStmtChoice records this 51/// contextual information. If AddStmtChoice is 'NotAlwaysAdd', then 52/// the builder has an option not to add a subexpression as a 53/// block-level expression. 54/// 55class AddStmtChoice { 56public: 57 enum Kind { NotAlwaysAdd = 0, AlwaysAdd = 1 }; 58 59 AddStmtChoice(Kind a_kind = NotAlwaysAdd) : kind(a_kind) {} 60 61 bool alwaysAdd(CFGBuilder &builder, 62 const Stmt *stmt) const; 63 64 /// Return a copy of this object, except with the 'always-add' bit 65 /// set as specified. 66 AddStmtChoice withAlwaysAdd(bool alwaysAdd) const { 67 return AddStmtChoice(alwaysAdd ? AlwaysAdd : NotAlwaysAdd); 68 } 69 70private: 71 Kind kind; 72}; 73 74/// LocalScope - Node in tree of local scopes created for C++ implicit 75/// destructor calls generation. It contains list of automatic variables 76/// declared in the scope and link to position in previous scope this scope 77/// began in. 78/// 79/// The process of creating local scopes is as follows: 80/// - Init CFGBuilder::ScopePos with invalid position (equivalent for null), 81/// - Before processing statements in scope (e.g. CompoundStmt) create 82/// LocalScope object using CFGBuilder::ScopePos as link to previous scope 83/// and set CFGBuilder::ScopePos to the end of new scope, 84/// - On every occurrence of VarDecl increase CFGBuilder::ScopePos if it points 85/// at this VarDecl, 86/// - For every normal (without jump) end of scope add to CFGBlock destructors 87/// for objects in the current scope, 88/// - For every jump add to CFGBlock destructors for objects 89/// between CFGBuilder::ScopePos and local scope position saved for jump 90/// target. Thanks to C++ restrictions on goto jumps we can be sure that 91/// jump target position will be on the path to root from CFGBuilder::ScopePos 92/// (adding any variable that doesn't need constructor to be called to 93/// LocalScope can break this assumption), 94/// 95class LocalScope { 96public: 97 typedef BumpVector<VarDecl*> AutomaticVarsTy; 98 99 /// const_iterator - Iterates local scope backwards and jumps to previous 100 /// scope on reaching the beginning of currently iterated scope. 101 class const_iterator { 102 const LocalScope* Scope; 103 104 /// VarIter is guaranteed to be greater then 0 for every valid iterator. 105 /// Invalid iterator (with null Scope) has VarIter equal to 0. 106 unsigned VarIter; 107 108 public: 109 /// Create invalid iterator. Dereferencing invalid iterator is not allowed. 110 /// Incrementing invalid iterator is allowed and will result in invalid 111 /// iterator. 112 const_iterator() 113 : Scope(NULL), VarIter(0) {} 114 115 /// Create valid iterator. In case when S.Prev is an invalid iterator and 116 /// I is equal to 0, this will create invalid iterator. 117 const_iterator(const LocalScope& S, unsigned I) 118 : Scope(&S), VarIter(I) { 119 // Iterator to "end" of scope is not allowed. Handle it by going up 120 // in scopes tree possibly up to invalid iterator in the root. 121 if (VarIter == 0 && Scope) 122 *this = Scope->Prev; 123 } 124 125 VarDecl *const* operator->() const { 126 assert (Scope && "Dereferencing invalid iterator is not allowed"); 127 assert (VarIter != 0 && "Iterator has invalid value of VarIter member"); 128 return &Scope->Vars[VarIter - 1]; 129 } 130 VarDecl *operator*() const { 131 return *this->operator->(); 132 } 133 134 const_iterator &operator++() { 135 if (!Scope) 136 return *this; 137 138 assert (VarIter != 0 && "Iterator has invalid value of VarIter member"); 139 --VarIter; 140 if (VarIter == 0) 141 *this = Scope->Prev; 142 return *this; 143 } 144 const_iterator operator++(int) { 145 const_iterator P = *this; 146 ++*this; 147 return P; 148 } 149 150 bool operator==(const const_iterator &rhs) const { 151 return Scope == rhs.Scope && VarIter == rhs.VarIter; 152 } 153 bool operator!=(const const_iterator &rhs) const { 154 return !(*this == rhs); 155 } 156 157 operator bool() const { 158 return *this != const_iterator(); 159 } 160 161 int distance(const_iterator L); 162 }; 163 164 friend class const_iterator; 165 166private: 167 BumpVectorContext ctx; 168 169 /// Automatic variables in order of declaration. 170 AutomaticVarsTy Vars; 171 /// Iterator to variable in previous scope that was declared just before 172 /// begin of this scope. 173 const_iterator Prev; 174 175public: 176 /// Constructs empty scope linked to previous scope in specified place. 177 LocalScope(BumpVectorContext &ctx, const_iterator P) 178 : ctx(ctx), Vars(ctx, 4), Prev(P) {} 179 180 /// Begin of scope in direction of CFG building (backwards). 181 const_iterator begin() const { return const_iterator(*this, Vars.size()); } 182 183 void addVar(VarDecl *VD) { 184 Vars.push_back(VD, ctx); 185 } 186}; 187 188/// distance - Calculates distance from this to L. L must be reachable from this 189/// (with use of ++ operator). Cost of calculating the distance is linear w.r.t. 190/// number of scopes between this and L. 191int LocalScope::const_iterator::distance(LocalScope::const_iterator L) { 192 int D = 0; 193 const_iterator F = *this; 194 while (F.Scope != L.Scope) { 195 assert (F != const_iterator() 196 && "L iterator is not reachable from F iterator."); 197 D += F.VarIter; 198 F = F.Scope->Prev; 199 } 200 D += F.VarIter - L.VarIter; 201 return D; 202} 203 204/// BlockScopePosPair - Structure for specifying position in CFG during its 205/// build process. It consists of CFGBlock that specifies position in CFG graph 206/// and LocalScope::const_iterator that specifies position in LocalScope graph. 207struct BlockScopePosPair { 208 BlockScopePosPair() : block(0) {} 209 BlockScopePosPair(CFGBlock *b, LocalScope::const_iterator scopePos) 210 : block(b), scopePosition(scopePos) {} 211 212 CFGBlock *block; 213 LocalScope::const_iterator scopePosition; 214}; 215 216/// TryResult - a class representing a variant over the values 217/// 'true', 'false', or 'unknown'. This is returned by tryEvaluateBool, 218/// and is used by the CFGBuilder to decide if a branch condition 219/// can be decided up front during CFG construction. 220class TryResult { 221 int X; 222public: 223 TryResult(bool b) : X(b ? 1 : 0) {} 224 TryResult() : X(-1) {} 225 226 bool isTrue() const { return X == 1; } 227 bool isFalse() const { return X == 0; } 228 bool isKnown() const { return X >= 0; } 229 void negate() { 230 assert(isKnown()); 231 X ^= 0x1; 232 } 233}; 234 235/// CFGBuilder - This class implements CFG construction from an AST. 236/// The builder is stateful: an instance of the builder should be used to only 237/// construct a single CFG. 238/// 239/// Example usage: 240/// 241/// CFGBuilder builder; 242/// CFG* cfg = builder.BuildAST(stmt1); 243/// 244/// CFG construction is done via a recursive walk of an AST. We actually parse 245/// the AST in reverse order so that the successor of a basic block is 246/// constructed prior to its predecessor. This allows us to nicely capture 247/// implicit fall-throughs without extra basic blocks. 248/// 249class CFGBuilder { 250 typedef BlockScopePosPair JumpTarget; 251 typedef BlockScopePosPair JumpSource; 252 253 ASTContext *Context; 254 OwningPtr<CFG> cfg; 255 256 CFGBlock *Block; 257 CFGBlock *Succ; 258 JumpTarget ContinueJumpTarget; 259 JumpTarget BreakJumpTarget; 260 CFGBlock *SwitchTerminatedBlock; 261 CFGBlock *DefaultCaseBlock; 262 CFGBlock *TryTerminatedBlock; 263 264 // Current position in local scope. 265 LocalScope::const_iterator ScopePos; 266 267 // LabelMap records the mapping from Label expressions to their jump targets. 268 typedef llvm::DenseMap<LabelDecl*, JumpTarget> LabelMapTy; 269 LabelMapTy LabelMap; 270 271 // A list of blocks that end with a "goto" that must be backpatched to their 272 // resolved targets upon completion of CFG construction. 273 typedef std::vector<JumpSource> BackpatchBlocksTy; 274 BackpatchBlocksTy BackpatchBlocks; 275 276 // A list of labels whose address has been taken (for indirect gotos). 277 typedef llvm::SmallPtrSet<LabelDecl*, 5> LabelSetTy; 278 LabelSetTy AddressTakenLabels; 279 280 bool badCFG; 281 const CFG::BuildOptions &BuildOpts; 282 283 // State to track for building switch statements. 284 bool switchExclusivelyCovered; 285 Expr::EvalResult *switchCond; 286 287 CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry; 288 const Stmt *lastLookup; 289 290 // Caches boolean evaluations of expressions to avoid multiple re-evaluations 291 // during construction of branches for chained logical operators. 292 typedef llvm::DenseMap<Expr *, TryResult> CachedBoolEvalsTy; 293 CachedBoolEvalsTy CachedBoolEvals; 294 295public: 296 explicit CFGBuilder(ASTContext *astContext, 297 const CFG::BuildOptions &buildOpts) 298 : Context(astContext), cfg(new CFG()), // crew a new CFG 299 Block(NULL), Succ(NULL), 300 SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL), 301 TryTerminatedBlock(NULL), badCFG(false), BuildOpts(buildOpts), 302 switchExclusivelyCovered(false), switchCond(0), 303 cachedEntry(0), lastLookup(0) {} 304 305 // buildCFG - Used by external clients to construct the CFG. 306 CFG* buildCFG(const Decl *D, Stmt *Statement); 307 308 bool alwaysAdd(const Stmt *stmt); 309 310private: 311 // Visitors to walk an AST and construct the CFG. 312 CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc); 313 CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc); 314 CFGBlock *VisitBreakStmt(BreakStmt *B); 315 CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S); 316 CFGBlock *VisitExprWithCleanups(ExprWithCleanups *E, 317 AddStmtChoice asc); 318 CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T); 319 CFGBlock *VisitCXXTryStmt(CXXTryStmt *S); 320 CFGBlock *VisitCXXForRangeStmt(CXXForRangeStmt *S); 321 CFGBlock *VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E, 322 AddStmtChoice asc); 323 CFGBlock *VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc); 324 CFGBlock *VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E, 325 AddStmtChoice asc); 326 CFGBlock *VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C, 327 AddStmtChoice asc); 328 CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc); 329 CFGBlock *VisitCaseStmt(CaseStmt *C); 330 CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc); 331 CFGBlock *VisitCompoundStmt(CompoundStmt *C); 332 CFGBlock *VisitConditionalOperator(AbstractConditionalOperator *C, 333 AddStmtChoice asc); 334 CFGBlock *VisitContinueStmt(ContinueStmt *C); 335 CFGBlock *VisitDeclStmt(DeclStmt *DS); 336 CFGBlock *VisitDeclSubExpr(DeclStmt *DS); 337 CFGBlock *VisitDefaultStmt(DefaultStmt *D); 338 CFGBlock *VisitDoStmt(DoStmt *D); 339 CFGBlock *VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc); 340 CFGBlock *VisitForStmt(ForStmt *F); 341 CFGBlock *VisitGotoStmt(GotoStmt *G); 342 CFGBlock *VisitIfStmt(IfStmt *I); 343 CFGBlock *VisitImplicitCastExpr(ImplicitCastExpr *E, AddStmtChoice asc); 344 CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I); 345 CFGBlock *VisitLabelStmt(LabelStmt *L); 346 CFGBlock *VisitLambdaExpr(LambdaExpr *L); 347 CFGBlock *VisitMemberExpr(MemberExpr *M, AddStmtChoice asc); 348 CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S); 349 CFGBlock *VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S); 350 CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S); 351 CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S); 352 CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S); 353 CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S); 354 CFGBlock *VisitReturnStmt(ReturnStmt *R); 355 CFGBlock *VisitPseudoObjectExpr(PseudoObjectExpr *E); 356 CFGBlock *VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E, 357 AddStmtChoice asc); 358 CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc); 359 CFGBlock *VisitSwitchStmt(SwitchStmt *S); 360 CFGBlock *VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc); 361 CFGBlock *VisitWhileStmt(WhileStmt *W); 362 363 CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd); 364 CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc); 365 CFGBlock *VisitChildren(Stmt *S); 366 CFGBlock *VisitNoRecurse(Expr *E, AddStmtChoice asc); 367 368 // Visitors to walk an AST and generate destructors of temporaries in 369 // full expression. 370 CFGBlock *VisitForTemporaryDtors(Stmt *E, bool BindToTemporary = false); 371 CFGBlock *VisitChildrenForTemporaryDtors(Stmt *E); 372 CFGBlock *VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E); 373 CFGBlock *VisitCXXBindTemporaryExprForTemporaryDtors(CXXBindTemporaryExpr *E, 374 bool BindToTemporary); 375 CFGBlock * 376 VisitConditionalOperatorForTemporaryDtors(AbstractConditionalOperator *E, 377 bool BindToTemporary); 378 379 // NYS == Not Yet Supported 380 CFGBlock *NYS() { 381 badCFG = true; 382 return Block; 383 } 384 385 void autoCreateBlock() { if (!Block) Block = createBlock(); } 386 CFGBlock *createBlock(bool add_successor = true); 387 CFGBlock *createNoReturnBlock(); 388 389 CFGBlock *addStmt(Stmt *S) { 390 return Visit(S, AddStmtChoice::AlwaysAdd); 391 } 392 CFGBlock *addInitializer(CXXCtorInitializer *I); 393 void addAutomaticObjDtors(LocalScope::const_iterator B, 394 LocalScope::const_iterator E, Stmt *S); 395 void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD); 396 397 // Local scopes creation. 398 LocalScope* createOrReuseLocalScope(LocalScope* Scope); 399 400 void addLocalScopeForStmt(Stmt *S); 401 LocalScope* addLocalScopeForDeclStmt(DeclStmt *DS, LocalScope* Scope = NULL); 402 LocalScope* addLocalScopeForVarDecl(VarDecl *VD, LocalScope* Scope = NULL); 403 404 void addLocalScopeAndDtors(Stmt *S); 405 406 // Interface to CFGBlock - adding CFGElements. 407 void appendStmt(CFGBlock *B, const Stmt *S) { 408 if (alwaysAdd(S) && cachedEntry) 409 cachedEntry->second = B; 410 411 // All block-level expressions should have already been IgnoreParens()ed. 412 assert(!isa<Expr>(S) || cast<Expr>(S)->IgnoreParens() == S); 413 B->appendStmt(const_cast<Stmt*>(S), cfg->getBumpVectorContext()); 414 } 415 void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) { 416 B->appendInitializer(I, cfg->getBumpVectorContext()); 417 } 418 void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) { 419 B->appendBaseDtor(BS, cfg->getBumpVectorContext()); 420 } 421 void appendMemberDtor(CFGBlock *B, FieldDecl *FD) { 422 B->appendMemberDtor(FD, cfg->getBumpVectorContext()); 423 } 424 void appendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) { 425 B->appendTemporaryDtor(E, cfg->getBumpVectorContext()); 426 } 427 void appendAutomaticObjDtor(CFGBlock *B, VarDecl *VD, Stmt *S) { 428 B->appendAutomaticObjDtor(VD, S, cfg->getBumpVectorContext()); 429 } 430 431 void prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk, 432 LocalScope::const_iterator B, LocalScope::const_iterator E); 433 434 void addSuccessor(CFGBlock *B, CFGBlock *S) { 435 B->addSuccessor(S, cfg->getBumpVectorContext()); 436 } 437 438 /// Try and evaluate an expression to an integer constant. 439 bool tryEvaluate(Expr *S, Expr::EvalResult &outResult) { 440 if (!BuildOpts.PruneTriviallyFalseEdges) 441 return false; 442 return !S->isTypeDependent() && 443 !S->isValueDependent() && 444 S->EvaluateAsRValue(outResult, *Context); 445 } 446 447 /// tryEvaluateBool - Try and evaluate the Stmt and return 0 or 1 448 /// if we can evaluate to a known value, otherwise return -1. 449 TryResult tryEvaluateBool(Expr *S) { 450 if (!BuildOpts.PruneTriviallyFalseEdges || 451 S->isTypeDependent() || S->isValueDependent()) 452 return TryResult(); 453 454 if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(S)) { 455 if (Bop->isLogicalOp()) { 456 // Check the cache first. 457 CachedBoolEvalsTy::iterator I = CachedBoolEvals.find(S); 458 if (I != CachedBoolEvals.end()) 459 return I->second; // already in map; 460 461 // Retrieve result at first, or the map might be updated. 462 TryResult Result = evaluateAsBooleanConditionNoCache(S); 463 CachedBoolEvals[S] = Result; // update or insert 464 return Result; 465 } 466 } 467 468 return evaluateAsBooleanConditionNoCache(S); 469 } 470 471 /// \brief Evaluate as boolean \param E without using the cache. 472 TryResult evaluateAsBooleanConditionNoCache(Expr *E) { 473 if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(E)) { 474 if (Bop->isLogicalOp()) { 475 TryResult LHS = tryEvaluateBool(Bop->getLHS()); 476 if (LHS.isKnown()) { 477 // We were able to evaluate the LHS, see if we can get away with not 478 // evaluating the RHS: 0 && X -> 0, 1 || X -> 1 479 if (LHS.isTrue() == (Bop->getOpcode() == BO_LOr)) 480 return LHS.isTrue(); 481 482 TryResult RHS = tryEvaluateBool(Bop->getRHS()); 483 if (RHS.isKnown()) { 484 if (Bop->getOpcode() == BO_LOr) 485 return LHS.isTrue() || RHS.isTrue(); 486 else 487 return LHS.isTrue() && RHS.isTrue(); 488 } 489 } else { 490 TryResult RHS = tryEvaluateBool(Bop->getRHS()); 491 if (RHS.isKnown()) { 492 // We can't evaluate the LHS; however, sometimes the result 493 // is determined by the RHS: X && 0 -> 0, X || 1 -> 1. 494 if (RHS.isTrue() == (Bop->getOpcode() == BO_LOr)) 495 return RHS.isTrue(); 496 } 497 } 498 499 return TryResult(); 500 } 501 } 502 503 bool Result; 504 if (E->EvaluateAsBooleanCondition(Result, *Context)) 505 return Result; 506 507 return TryResult(); 508 } 509 510}; 511 512inline bool AddStmtChoice::alwaysAdd(CFGBuilder &builder, 513 const Stmt *stmt) const { 514 return builder.alwaysAdd(stmt) || kind == AlwaysAdd; 515} 516 517bool CFGBuilder::alwaysAdd(const Stmt *stmt) { 518 bool shouldAdd = BuildOpts.alwaysAdd(stmt); 519 520 if (!BuildOpts.forcedBlkExprs) 521 return shouldAdd; 522 523 if (lastLookup == stmt) { 524 if (cachedEntry) { 525 assert(cachedEntry->first == stmt); 526 return true; 527 } 528 return shouldAdd; 529 } 530 531 lastLookup = stmt; 532 533 // Perform the lookup! 534 CFG::BuildOptions::ForcedBlkExprs *fb = *BuildOpts.forcedBlkExprs; 535 536 if (!fb) { 537 // No need to update 'cachedEntry', since it will always be null. 538 assert(cachedEntry == 0); 539 return shouldAdd; 540 } 541 542 CFG::BuildOptions::ForcedBlkExprs::iterator itr = fb->find(stmt); 543 if (itr == fb->end()) { 544 cachedEntry = 0; 545 return shouldAdd; 546 } 547 548 cachedEntry = &*itr; 549 return true; 550} 551 552// FIXME: Add support for dependent-sized array types in C++? 553// Does it even make sense to build a CFG for an uninstantiated template? 554static const VariableArrayType *FindVA(const Type *t) { 555 while (const ArrayType *vt = dyn_cast<ArrayType>(t)) { 556 if (const VariableArrayType *vat = dyn_cast<VariableArrayType>(vt)) 557 if (vat->getSizeExpr()) 558 return vat; 559 560 t = vt->getElementType().getTypePtr(); 561 } 562 563 return 0; 564} 565 566/// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an 567/// arbitrary statement. Examples include a single expression or a function 568/// body (compound statement). The ownership of the returned CFG is 569/// transferred to the caller. If CFG construction fails, this method returns 570/// NULL. 571CFG* CFGBuilder::buildCFG(const Decl *D, Stmt *Statement) { 572 assert(cfg.get()); 573 if (!Statement) 574 return NULL; 575 576 // Create an empty block that will serve as the exit block for the CFG. Since 577 // this is the first block added to the CFG, it will be implicitly registered 578 // as the exit block. 579 Succ = createBlock(); 580 assert(Succ == &cfg->getExit()); 581 Block = NULL; // the EXIT block is empty. Create all other blocks lazily. 582 583 if (BuildOpts.AddImplicitDtors) 584 if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(D)) 585 addImplicitDtorsForDestructor(DD); 586 587 // Visit the statements and create the CFG. 588 CFGBlock *B = addStmt(Statement); 589 590 if (badCFG) 591 return NULL; 592 593 // For C++ constructor add initializers to CFG. 594 if (const CXXConstructorDecl *CD = dyn_cast_or_null<CXXConstructorDecl>(D)) { 595 for (CXXConstructorDecl::init_const_reverse_iterator I = CD->init_rbegin(), 596 E = CD->init_rend(); I != E; ++I) { 597 B = addInitializer(*I); 598 if (badCFG) 599 return NULL; 600 } 601 } 602 603 if (B) 604 Succ = B; 605 606 // Backpatch the gotos whose label -> block mappings we didn't know when we 607 // encountered them. 608 for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(), 609 E = BackpatchBlocks.end(); I != E; ++I ) { 610 611 CFGBlock *B = I->block; 612 GotoStmt *G = cast<GotoStmt>(B->getTerminator()); 613 LabelMapTy::iterator LI = LabelMap.find(G->getLabel()); 614 615 // If there is no target for the goto, then we are looking at an 616 // incomplete AST. Handle this by not registering a successor. 617 if (LI == LabelMap.end()) continue; 618 619 JumpTarget JT = LI->second; 620 prependAutomaticObjDtorsWithTerminator(B, I->scopePosition, 621 JT.scopePosition); 622 addSuccessor(B, JT.block); 623 } 624 625 // Add successors to the Indirect Goto Dispatch block (if we have one). 626 if (CFGBlock *B = cfg->getIndirectGotoBlock()) 627 for (LabelSetTy::iterator I = AddressTakenLabels.begin(), 628 E = AddressTakenLabels.end(); I != E; ++I ) { 629 630 // Lookup the target block. 631 LabelMapTy::iterator LI = LabelMap.find(*I); 632 633 // If there is no target block that contains label, then we are looking 634 // at an incomplete AST. Handle this by not registering a successor. 635 if (LI == LabelMap.end()) continue; 636 637 addSuccessor(B, LI->second.block); 638 } 639 640 // Create an empty entry block that has no predecessors. 641 cfg->setEntry(createBlock()); 642 643 return cfg.take(); 644} 645 646/// createBlock - Used to lazily create blocks that are connected 647/// to the current (global) succcessor. 648CFGBlock *CFGBuilder::createBlock(bool add_successor) { 649 CFGBlock *B = cfg->createBlock(); 650 if (add_successor && Succ) 651 addSuccessor(B, Succ); 652 return B; 653} 654 655/// createNoReturnBlock - Used to create a block is a 'noreturn' point in the 656/// CFG. It is *not* connected to the current (global) successor, and instead 657/// directly tied to the exit block in order to be reachable. 658CFGBlock *CFGBuilder::createNoReturnBlock() { 659 CFGBlock *B = createBlock(false); 660 B->setHasNoReturnElement(); 661 addSuccessor(B, &cfg->getExit()); 662 return B; 663} 664 665/// addInitializer - Add C++ base or member initializer element to CFG. 666CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) { 667 if (!BuildOpts.AddInitializers) 668 return Block; 669 670 bool IsReference = false; 671 bool HasTemporaries = false; 672 673 // Destructors of temporaries in initialization expression should be called 674 // after initialization finishes. 675 Expr *Init = I->getInit(); 676 if (Init) { 677 if (FieldDecl *FD = I->getAnyMember()) 678 IsReference = FD->getType()->isReferenceType(); 679 HasTemporaries = isa<ExprWithCleanups>(Init); 680 681 if (BuildOpts.AddImplicitDtors && HasTemporaries) { 682 // Generate destructors for temporaries in initialization expression. 683 VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(), 684 IsReference); 685 } 686 } 687 688 autoCreateBlock(); 689 appendInitializer(Block, I); 690 691 if (Init) { 692 if (HasTemporaries) { 693 // For expression with temporaries go directly to subexpression to omit 694 // generating destructors for the second time. 695 return Visit(cast<ExprWithCleanups>(Init)->getSubExpr()); 696 } 697 return Visit(Init); 698 } 699 700 return Block; 701} 702 703/// \brief Retrieve the type of the temporary object whose lifetime was 704/// extended by a local reference with the given initializer. 705static QualType getReferenceInitTemporaryType(ASTContext &Context, 706 const Expr *Init) { 707 while (true) { 708 // Skip parentheses. 709 Init = Init->IgnoreParens(); 710 711 // Skip through cleanups. 712 if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Init)) { 713 Init = EWC->getSubExpr(); 714 continue; 715 } 716 717 // Skip through the temporary-materialization expression. 718 if (const MaterializeTemporaryExpr *MTE 719 = dyn_cast<MaterializeTemporaryExpr>(Init)) { 720 Init = MTE->GetTemporaryExpr(); 721 continue; 722 } 723 724 // Skip derived-to-base and no-op casts. 725 if (const CastExpr *CE = dyn_cast<CastExpr>(Init)) { 726 if ((CE->getCastKind() == CK_DerivedToBase || 727 CE->getCastKind() == CK_UncheckedDerivedToBase || 728 CE->getCastKind() == CK_NoOp) && 729 Init->getType()->isRecordType()) { 730 Init = CE->getSubExpr(); 731 continue; 732 } 733 } 734 735 // Skip member accesses into rvalues. 736 if (const MemberExpr *ME = dyn_cast<MemberExpr>(Init)) { 737 if (!ME->isArrow() && ME->getBase()->isRValue()) { 738 Init = ME->getBase(); 739 continue; 740 } 741 } 742 743 break; 744 } 745 746 return Init->getType(); 747} 748 749/// addAutomaticObjDtors - Add to current block automatic objects destructors 750/// for objects in range of local scope positions. Use S as trigger statement 751/// for destructors. 752void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B, 753 LocalScope::const_iterator E, Stmt *S) { 754 if (!BuildOpts.AddImplicitDtors) 755 return; 756 757 if (B == E) 758 return; 759 760 // We need to append the destructors in reverse order, but any one of them 761 // may be a no-return destructor which changes the CFG. As a result, buffer 762 // this sequence up and replay them in reverse order when appending onto the 763 // CFGBlock(s). 764 SmallVector<VarDecl*, 10> Decls; 765 Decls.reserve(B.distance(E)); 766 for (LocalScope::const_iterator I = B; I != E; ++I) 767 Decls.push_back(*I); 768 769 for (SmallVectorImpl<VarDecl*>::reverse_iterator I = Decls.rbegin(), 770 E = Decls.rend(); 771 I != E; ++I) { 772 // If this destructor is marked as a no-return destructor, we need to 773 // create a new block for the destructor which does not have as a successor 774 // anything built thus far: control won't flow out of this block. 775 QualType Ty; 776 if ((*I)->getType()->isReferenceType()) { 777 Ty = getReferenceInitTemporaryType(*Context, (*I)->getInit()); 778 } else { 779 Ty = Context->getBaseElementType((*I)->getType()); 780 } 781 782 const CXXDestructorDecl *Dtor = Ty->getAsCXXRecordDecl()->getDestructor(); 783 if (cast<FunctionType>(Dtor->getType())->getNoReturnAttr()) 784 Block = createNoReturnBlock(); 785 else 786 autoCreateBlock(); 787 788 appendAutomaticObjDtor(Block, *I, S); 789 } 790} 791 792/// addImplicitDtorsForDestructor - Add implicit destructors generated for 793/// base and member objects in destructor. 794void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) { 795 assert (BuildOpts.AddImplicitDtors 796 && "Can be called only when dtors should be added"); 797 const CXXRecordDecl *RD = DD->getParent(); 798 799 // At the end destroy virtual base objects. 800 for (CXXRecordDecl::base_class_const_iterator VI = RD->vbases_begin(), 801 VE = RD->vbases_end(); VI != VE; ++VI) { 802 const CXXRecordDecl *CD = VI->getType()->getAsCXXRecordDecl(); 803 if (!CD->hasTrivialDestructor()) { 804 autoCreateBlock(); 805 appendBaseDtor(Block, VI); 806 } 807 } 808 809 // Before virtual bases destroy direct base objects. 810 for (CXXRecordDecl::base_class_const_iterator BI = RD->bases_begin(), 811 BE = RD->bases_end(); BI != BE; ++BI) { 812 if (!BI->isVirtual()) { 813 const CXXRecordDecl *CD = BI->getType()->getAsCXXRecordDecl(); 814 if (!CD->hasTrivialDestructor()) { 815 autoCreateBlock(); 816 appendBaseDtor(Block, BI); 817 } 818 } 819 } 820 821 // First destroy member objects. 822 for (CXXRecordDecl::field_iterator FI = RD->field_begin(), 823 FE = RD->field_end(); FI != FE; ++FI) { 824 // Check for constant size array. Set type to array element type. 825 QualType QT = FI->getType(); 826 if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) { 827 if (AT->getSize() == 0) 828 continue; 829 QT = AT->getElementType(); 830 } 831 832 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl()) 833 if (!CD->hasTrivialDestructor()) { 834 autoCreateBlock(); 835 appendMemberDtor(Block, &*FI); 836 } 837 } 838} 839 840/// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either 841/// way return valid LocalScope object. 842LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) { 843 if (!Scope) { 844 llvm::BumpPtrAllocator &alloc = cfg->getAllocator(); 845 Scope = alloc.Allocate<LocalScope>(); 846 BumpVectorContext ctx(alloc); 847 new (Scope) LocalScope(ctx, ScopePos); 848 } 849 return Scope; 850} 851 852/// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement 853/// that should create implicit scope (e.g. if/else substatements). 854void CFGBuilder::addLocalScopeForStmt(Stmt *S) { 855 if (!BuildOpts.AddImplicitDtors) 856 return; 857 858 LocalScope *Scope = 0; 859 860 // For compound statement we will be creating explicit scope. 861 if (CompoundStmt *CS = dyn_cast<CompoundStmt>(S)) { 862 for (CompoundStmt::body_iterator BI = CS->body_begin(), BE = CS->body_end() 863 ; BI != BE; ++BI) { 864 Stmt *SI = (*BI)->stripLabelLikeStatements(); 865 if (DeclStmt *DS = dyn_cast<DeclStmt>(SI)) 866 Scope = addLocalScopeForDeclStmt(DS, Scope); 867 } 868 return; 869 } 870 871 // For any other statement scope will be implicit and as such will be 872 // interesting only for DeclStmt. 873 if (DeclStmt *DS = dyn_cast<DeclStmt>(S->stripLabelLikeStatements())) 874 addLocalScopeForDeclStmt(DS); 875} 876 877/// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will 878/// reuse Scope if not NULL. 879LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt *DS, 880 LocalScope* Scope) { 881 if (!BuildOpts.AddImplicitDtors) 882 return Scope; 883 884 for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end() 885 ; DI != DE; ++DI) { 886 if (VarDecl *VD = dyn_cast<VarDecl>(*DI)) 887 Scope = addLocalScopeForVarDecl(VD, Scope); 888 } 889 return Scope; 890} 891 892/// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will 893/// create add scope for automatic objects and temporary objects bound to 894/// const reference. Will reuse Scope if not NULL. 895LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD, 896 LocalScope* Scope) { 897 if (!BuildOpts.AddImplicitDtors) 898 return Scope; 899 900 // Check if variable is local. 901 switch (VD->getStorageClass()) { 902 case SC_None: 903 case SC_Auto: 904 case SC_Register: 905 break; 906 default: return Scope; 907 } 908 909 // Check for const references bound to temporary. Set type to pointee. 910 QualType QT = VD->getType(); 911 if (QT.getTypePtr()->isReferenceType()) { 912 if (!VD->extendsLifetimeOfTemporary()) 913 return Scope; 914 915 QT = getReferenceInitTemporaryType(*Context, VD->getInit()); 916 } 917 918 // Check for constant size array. Set type to array element type. 919 while (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) { 920 if (AT->getSize() == 0) 921 return Scope; 922 QT = AT->getElementType(); 923 } 924 925 // Check if type is a C++ class with non-trivial destructor. 926 if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl()) 927 if (!CD->hasTrivialDestructor()) { 928 // Add the variable to scope 929 Scope = createOrReuseLocalScope(Scope); 930 Scope->addVar(VD); 931 ScopePos = Scope->begin(); 932 } 933 return Scope; 934} 935 936/// addLocalScopeAndDtors - For given statement add local scope for it and 937/// add destructors that will cleanup the scope. Will reuse Scope if not NULL. 938void CFGBuilder::addLocalScopeAndDtors(Stmt *S) { 939 if (!BuildOpts.AddImplicitDtors) 940 return; 941 942 LocalScope::const_iterator scopeBeginPos = ScopePos; 943 addLocalScopeForStmt(S); 944 addAutomaticObjDtors(ScopePos, scopeBeginPos, S); 945} 946 947/// prependAutomaticObjDtorsWithTerminator - Prepend destructor CFGElements for 948/// variables with automatic storage duration to CFGBlock's elements vector. 949/// Elements will be prepended to physical beginning of the vector which 950/// happens to be logical end. Use blocks terminator as statement that specifies 951/// destructors call site. 952/// FIXME: This mechanism for adding automatic destructors doesn't handle 953/// no-return destructors properly. 954void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock *Blk, 955 LocalScope::const_iterator B, LocalScope::const_iterator E) { 956 BumpVectorContext &C = cfg->getBumpVectorContext(); 957 CFGBlock::iterator InsertPos 958 = Blk->beginAutomaticObjDtorsInsert(Blk->end(), B.distance(E), C); 959 for (LocalScope::const_iterator I = B; I != E; ++I) 960 InsertPos = Blk->insertAutomaticObjDtor(InsertPos, *I, 961 Blk->getTerminator()); 962} 963 964/// Visit - Walk the subtree of a statement and add extra 965/// blocks for ternary operators, &&, and ||. We also process "," and 966/// DeclStmts (which may contain nested control-flow). 967CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) { 968 if (!S) { 969 badCFG = true; 970 return 0; 971 } 972 973 if (Expr *E = dyn_cast<Expr>(S)) 974 S = E->IgnoreParens(); 975 976 switch (S->getStmtClass()) { 977 default: 978 return VisitStmt(S, asc); 979 980 case Stmt::AddrLabelExprClass: 981 return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc); 982 983 case Stmt::BinaryConditionalOperatorClass: 984 return VisitConditionalOperator(cast<BinaryConditionalOperator>(S), asc); 985 986 case Stmt::BinaryOperatorClass: 987 return VisitBinaryOperator(cast<BinaryOperator>(S), asc); 988 989 case Stmt::BlockExprClass: 990 return VisitNoRecurse(cast<Expr>(S), asc); 991 992 case Stmt::BreakStmtClass: 993 return VisitBreakStmt(cast<BreakStmt>(S)); 994 995 case Stmt::CallExprClass: 996 case Stmt::CXXOperatorCallExprClass: 997 case Stmt::CXXMemberCallExprClass: 998 case Stmt::UserDefinedLiteralClass: 999 return VisitCallExpr(cast<CallExpr>(S), asc); 1000 1001 case Stmt::CaseStmtClass: 1002 return VisitCaseStmt(cast<CaseStmt>(S)); 1003 1004 case Stmt::ChooseExprClass: 1005 return VisitChooseExpr(cast<ChooseExpr>(S), asc); 1006 1007 case Stmt::CompoundStmtClass: 1008 return VisitCompoundStmt(cast<CompoundStmt>(S)); 1009 1010 case Stmt::ConditionalOperatorClass: 1011 return VisitConditionalOperator(cast<ConditionalOperator>(S), asc); 1012 1013 case Stmt::ContinueStmtClass: 1014 return VisitContinueStmt(cast<ContinueStmt>(S)); 1015 1016 case Stmt::CXXCatchStmtClass: 1017 return VisitCXXCatchStmt(cast<CXXCatchStmt>(S)); 1018 1019 case Stmt::ExprWithCleanupsClass: 1020 return VisitExprWithCleanups(cast<ExprWithCleanups>(S), asc); 1021 1022 case Stmt::CXXBindTemporaryExprClass: 1023 return VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), asc); 1024 1025 case Stmt::CXXConstructExprClass: 1026 return VisitCXXConstructExpr(cast<CXXConstructExpr>(S), asc); 1027 1028 case Stmt::CXXFunctionalCastExprClass: 1029 return VisitCXXFunctionalCastExpr(cast<CXXFunctionalCastExpr>(S), asc); 1030 1031 case Stmt::CXXTemporaryObjectExprClass: 1032 return VisitCXXTemporaryObjectExpr(cast<CXXTemporaryObjectExpr>(S), asc); 1033 1034 case Stmt::CXXThrowExprClass: 1035 return VisitCXXThrowExpr(cast<CXXThrowExpr>(S)); 1036 1037 case Stmt::CXXTryStmtClass: 1038 return VisitCXXTryStmt(cast<CXXTryStmt>(S)); 1039 1040 case Stmt::CXXForRangeStmtClass: 1041 return VisitCXXForRangeStmt(cast<CXXForRangeStmt>(S)); 1042 1043 case Stmt::DeclStmtClass: 1044 return VisitDeclStmt(cast<DeclStmt>(S)); 1045 1046 case Stmt::DefaultStmtClass: 1047 return VisitDefaultStmt(cast<DefaultStmt>(S)); 1048 1049 case Stmt::DoStmtClass: 1050 return VisitDoStmt(cast<DoStmt>(S)); 1051 1052 case Stmt::ForStmtClass: 1053 return VisitForStmt(cast<ForStmt>(S)); 1054 1055 case Stmt::GotoStmtClass: 1056 return VisitGotoStmt(cast<GotoStmt>(S)); 1057 1058 case Stmt::IfStmtClass: 1059 return VisitIfStmt(cast<IfStmt>(S)); 1060 1061 case Stmt::ImplicitCastExprClass: 1062 return VisitImplicitCastExpr(cast<ImplicitCastExpr>(S), asc); 1063 1064 case Stmt::IndirectGotoStmtClass: 1065 return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S)); 1066 1067 case Stmt::LabelStmtClass: 1068 return VisitLabelStmt(cast<LabelStmt>(S)); 1069 1070 case Stmt::LambdaExprClass: 1071 return VisitLambdaExpr(cast<LambdaExpr>(S), asc); 1072 1073 case Stmt::MemberExprClass: 1074 return VisitMemberExpr(cast<MemberExpr>(S), asc); 1075 1076 case Stmt::NullStmtClass: 1077 return Block; 1078 1079 case Stmt::ObjCAtCatchStmtClass: 1080 return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S)); 1081 1082 case Stmt::ObjCAutoreleasePoolStmtClass: 1083 return VisitObjCAutoreleasePoolStmt(cast<ObjCAutoreleasePoolStmt>(S)); 1084 1085 case Stmt::ObjCAtSynchronizedStmtClass: 1086 return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S)); 1087 1088 case Stmt::ObjCAtThrowStmtClass: 1089 return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S)); 1090 1091 case Stmt::ObjCAtTryStmtClass: 1092 return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S)); 1093 1094 case Stmt::ObjCForCollectionStmtClass: 1095 return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S)); 1096 1097 case Stmt::OpaqueValueExprClass: 1098 return Block; 1099 1100 case Stmt::PseudoObjectExprClass: 1101 return VisitPseudoObjectExpr(cast<PseudoObjectExpr>(S)); 1102 1103 case Stmt::ReturnStmtClass: 1104 return VisitReturnStmt(cast<ReturnStmt>(S)); 1105 1106 case Stmt::UnaryExprOrTypeTraitExprClass: 1107 return VisitUnaryExprOrTypeTraitExpr(cast<UnaryExprOrTypeTraitExpr>(S), 1108 asc); 1109 1110 case Stmt::StmtExprClass: 1111 return VisitStmtExpr(cast<StmtExpr>(S), asc); 1112 1113 case Stmt::SwitchStmtClass: 1114 return VisitSwitchStmt(cast<SwitchStmt>(S)); 1115 1116 case Stmt::UnaryOperatorClass: 1117 return VisitUnaryOperator(cast<UnaryOperator>(S), asc); 1118 1119 case Stmt::WhileStmtClass: 1120 return VisitWhileStmt(cast<WhileStmt>(S)); 1121 } 1122} 1123 1124CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) { 1125 if (asc.alwaysAdd(*this, S)) { 1126 autoCreateBlock(); 1127 appendStmt(Block, S); 1128 } 1129 1130 return VisitChildren(S); 1131} 1132 1133/// VisitChildren - Visit the children of a Stmt. 1134CFGBlock *CFGBuilder::VisitChildren(Stmt *Terminator) { 1135 CFGBlock *lastBlock = Block; 1136 for (Stmt::child_range I = Terminator->children(); I; ++I) 1137 if (Stmt *child = *I) 1138 if (CFGBlock *b = Visit(child)) 1139 lastBlock = b; 1140 1141 return lastBlock; 1142} 1143 1144CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A, 1145 AddStmtChoice asc) { 1146 AddressTakenLabels.insert(A->getLabel()); 1147 1148 if (asc.alwaysAdd(*this, A)) { 1149 autoCreateBlock(); 1150 appendStmt(Block, A); 1151 } 1152 1153 return Block; 1154} 1155 1156CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U, 1157 AddStmtChoice asc) { 1158 if (asc.alwaysAdd(*this, U)) { 1159 autoCreateBlock(); 1160 appendStmt(Block, U); 1161 } 1162 1163 return Visit(U->getSubExpr(), AddStmtChoice()); 1164} 1165 1166CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, 1167 AddStmtChoice asc) { 1168 if (B->isLogicalOp()) { // && or || 1169 CFGBlock *ConfluenceBlock = Block ? Block : createBlock(); 1170 appendStmt(ConfluenceBlock, B); 1171 1172 if (badCFG) 1173 return 0; 1174 1175 // create the block evaluating the LHS 1176 CFGBlock *LHSBlock = createBlock(false); 1177 LHSBlock->setTerminator(B); 1178 1179 // create the block evaluating the RHS 1180 Succ = ConfluenceBlock; 1181 Block = NULL; 1182 CFGBlock *RHSBlock = addStmt(B->getRHS()); 1183 1184 if (RHSBlock) { 1185 if (badCFG) 1186 return 0; 1187 } else { 1188 // Create an empty block for cases where the RHS doesn't require 1189 // any explicit statements in the CFG. 1190 RHSBlock = createBlock(); 1191 } 1192 1193 // Generate the blocks for evaluating the LHS. 1194 Block = LHSBlock; 1195 CFGBlock *EntryLHSBlock = addStmt(B->getLHS()); 1196 1197 // See if this is a known constant. 1198 TryResult KnownVal = tryEvaluateBool(B->getLHS()); 1199 if (KnownVal.isKnown() && (B->getOpcode() == BO_LOr)) 1200 KnownVal.negate(); 1201 1202 // Now link the LHSBlock with RHSBlock. 1203 if (B->getOpcode() == BO_LOr) { 1204 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); 1205 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); 1206 } else { 1207 assert(B->getOpcode() == BO_LAnd); 1208 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); 1209 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); 1210 } 1211 1212 return EntryLHSBlock; 1213 } 1214 1215 if (B->getOpcode() == BO_Comma) { // , 1216 autoCreateBlock(); 1217 appendStmt(Block, B); 1218 addStmt(B->getRHS()); 1219 return addStmt(B->getLHS()); 1220 } 1221 1222 if (B->isAssignmentOp()) { 1223 if (asc.alwaysAdd(*this, B)) { 1224 autoCreateBlock(); 1225 appendStmt(Block, B); 1226 } 1227 Visit(B->getLHS()); 1228 return Visit(B->getRHS()); 1229 } 1230 1231 if (asc.alwaysAdd(*this, B)) { 1232 autoCreateBlock(); 1233 appendStmt(Block, B); 1234 } 1235 1236 CFGBlock *RBlock = Visit(B->getRHS()); 1237 CFGBlock *LBlock = Visit(B->getLHS()); 1238 // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr 1239 // containing a DoStmt, and the LHS doesn't create a new block, then we should 1240 // return RBlock. Otherwise we'll incorrectly return NULL. 1241 return (LBlock ? LBlock : RBlock); 1242} 1243 1244CFGBlock *CFGBuilder::VisitNoRecurse(Expr *E, AddStmtChoice asc) { 1245 if (asc.alwaysAdd(*this, E)) { 1246 autoCreateBlock(); 1247 appendStmt(Block, E); 1248 } 1249 return Block; 1250} 1251 1252CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) { 1253 // "break" is a control-flow statement. Thus we stop processing the current 1254 // block. 1255 if (badCFG) 1256 return 0; 1257 1258 // Now create a new block that ends with the break statement. 1259 Block = createBlock(false); 1260 Block->setTerminator(B); 1261 1262 // If there is no target for the break, then we are looking at an incomplete 1263 // AST. This means that the CFG cannot be constructed. 1264 if (BreakJumpTarget.block) { 1265 addAutomaticObjDtors(ScopePos, BreakJumpTarget.scopePosition, B); 1266 addSuccessor(Block, BreakJumpTarget.block); 1267 } else 1268 badCFG = true; 1269 1270 1271 return Block; 1272} 1273 1274static bool CanThrow(Expr *E, ASTContext &Ctx) { 1275 QualType Ty = E->getType(); 1276 if (Ty->isFunctionPointerType()) 1277 Ty = Ty->getAs<PointerType>()->getPointeeType(); 1278 else if (Ty->isBlockPointerType()) 1279 Ty = Ty->getAs<BlockPointerType>()->getPointeeType(); 1280 1281 const FunctionType *FT = Ty->getAs<FunctionType>(); 1282 if (FT) { 1283 if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT)) 1284 if (Proto->getExceptionSpecType() != EST_Uninstantiated && 1285 Proto->isNothrow(Ctx)) 1286 return false; 1287 } 1288 return true; 1289} 1290 1291CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { 1292 // Compute the callee type. 1293 QualType calleeType = C->getCallee()->getType(); 1294 if (calleeType == Context->BoundMemberTy) { 1295 QualType boundType = Expr::findBoundMemberType(C->getCallee()); 1296 1297 // We should only get a null bound type if processing a dependent 1298 // CFG. Recover by assuming nothing. 1299 if (!boundType.isNull()) calleeType = boundType; 1300 } 1301 1302 // If this is a call to a no-return function, this stops the block here. 1303 bool NoReturn = getFunctionExtInfo(*calleeType).getNoReturn(); 1304 1305 bool AddEHEdge = false; 1306 1307 // Languages without exceptions are assumed to not throw. 1308 if (Context->getLangOpts().Exceptions) { 1309 if (BuildOpts.AddEHEdges) 1310 AddEHEdge = true; 1311 } 1312 1313 if (FunctionDecl *FD = C->getDirectCallee()) { 1314 if (FD->hasAttr<NoReturnAttr>()) 1315 NoReturn = true; 1316 if (FD->hasAttr<NoThrowAttr>()) 1317 AddEHEdge = false; 1318 } 1319 1320 if (!CanThrow(C->getCallee(), *Context)) 1321 AddEHEdge = false; 1322 1323 if (!NoReturn && !AddEHEdge) 1324 return VisitStmt(C, asc.withAlwaysAdd(true)); 1325 1326 if (Block) { 1327 Succ = Block; 1328 if (badCFG) 1329 return 0; 1330 } 1331 1332 if (NoReturn) 1333 Block = createNoReturnBlock(); 1334 else 1335 Block = createBlock(); 1336 1337 appendStmt(Block, C); 1338 1339 if (AddEHEdge) { 1340 // Add exceptional edges. 1341 if (TryTerminatedBlock) 1342 addSuccessor(Block, TryTerminatedBlock); 1343 else 1344 addSuccessor(Block, &cfg->getExit()); 1345 } 1346 1347 return VisitChildren(C); 1348} 1349 1350CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C, 1351 AddStmtChoice asc) { 1352 CFGBlock *ConfluenceBlock = Block ? Block : createBlock(); 1353 appendStmt(ConfluenceBlock, C); 1354 if (badCFG) 1355 return 0; 1356 1357 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true); 1358 Succ = ConfluenceBlock; 1359 Block = NULL; 1360 CFGBlock *LHSBlock = Visit(C->getLHS(), alwaysAdd); 1361 if (badCFG) 1362 return 0; 1363 1364 Succ = ConfluenceBlock; 1365 Block = NULL; 1366 CFGBlock *RHSBlock = Visit(C->getRHS(), alwaysAdd); 1367 if (badCFG) 1368 return 0; 1369 1370 Block = createBlock(false); 1371 // See if this is a known constant. 1372 const TryResult& KnownVal = tryEvaluateBool(C->getCond()); 1373 addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); 1374 addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); 1375 Block->setTerminator(C); 1376 return addStmt(C->getCond()); 1377} 1378 1379 1380CFGBlock *CFGBuilder::VisitCompoundStmt(CompoundStmt *C) { 1381 addLocalScopeAndDtors(C); 1382 CFGBlock *LastBlock = Block; 1383 1384 for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); 1385 I != E; ++I ) { 1386 // If we hit a segment of code just containing ';' (NullStmts), we can 1387 // get a null block back. In such cases, just use the LastBlock 1388 if (CFGBlock *newBlock = addStmt(*I)) 1389 LastBlock = newBlock; 1390 1391 if (badCFG) 1392 return NULL; 1393 } 1394 1395 return LastBlock; 1396} 1397 1398CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C, 1399 AddStmtChoice asc) { 1400 const BinaryConditionalOperator *BCO = dyn_cast<BinaryConditionalOperator>(C); 1401 const OpaqueValueExpr *opaqueValue = (BCO ? BCO->getOpaqueValue() : NULL); 1402 1403 // Create the confluence block that will "merge" the results of the ternary 1404 // expression. 1405 CFGBlock *ConfluenceBlock = Block ? Block : createBlock(); 1406 appendStmt(ConfluenceBlock, C); 1407 if (badCFG) 1408 return 0; 1409 1410 AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true); 1411 1412 // Create a block for the LHS expression if there is an LHS expression. A 1413 // GCC extension allows LHS to be NULL, causing the condition to be the 1414 // value that is returned instead. 1415 // e.g: x ?: y is shorthand for: x ? x : y; 1416 Succ = ConfluenceBlock; 1417 Block = NULL; 1418 CFGBlock *LHSBlock = 0; 1419 const Expr *trueExpr = C->getTrueExpr(); 1420 if (trueExpr != opaqueValue) { 1421 LHSBlock = Visit(C->getTrueExpr(), alwaysAdd); 1422 if (badCFG) 1423 return 0; 1424 Block = NULL; 1425 } 1426 else 1427 LHSBlock = ConfluenceBlock; 1428 1429 // Create the block for the RHS expression. 1430 Succ = ConfluenceBlock; 1431 CFGBlock *RHSBlock = Visit(C->getFalseExpr(), alwaysAdd); 1432 if (badCFG) 1433 return 0; 1434 1435 // Create the block that will contain the condition. 1436 Block = createBlock(false); 1437 1438 // See if this is a known constant. 1439 const TryResult& KnownVal = tryEvaluateBool(C->getCond()); 1440 addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); 1441 addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); 1442 Block->setTerminator(C); 1443 Expr *condExpr = C->getCond(); 1444 1445 if (opaqueValue) { 1446 // Run the condition expression if it's not trivially expressed in 1447 // terms of the opaque value (or if there is no opaque value). 1448 if (condExpr != opaqueValue) 1449 addStmt(condExpr); 1450 1451 // Before that, run the common subexpression if there was one. 1452 // At least one of this or the above will be run. 1453 return addStmt(BCO->getCommon()); 1454 } 1455 1456 return addStmt(condExpr); 1457} 1458 1459CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) { 1460 // Check if the Decl is for an __label__. If so, elide it from the 1461 // CFG entirely. 1462 if (isa<LabelDecl>(*DS->decl_begin())) 1463 return Block; 1464 1465 // This case also handles static_asserts. 1466 if (DS->isSingleDecl()) 1467 return VisitDeclSubExpr(DS); 1468 1469 CFGBlock *B = 0; 1470 1471 // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy. 1472 typedef SmallVector<Decl*,10> BufTy; 1473 BufTy Buf(DS->decl_begin(), DS->decl_end()); 1474 1475 for (BufTy::reverse_iterator I = Buf.rbegin(), E = Buf.rend(); I != E; ++I) { 1476 // Get the alignment of the new DeclStmt, padding out to >=8 bytes. 1477 unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8 1478 ? 8 : llvm::AlignOf<DeclStmt>::Alignment; 1479 1480 // Allocate the DeclStmt using the BumpPtrAllocator. It will get 1481 // automatically freed with the CFG. 1482 DeclGroupRef DG(*I); 1483 Decl *D = *I; 1484 void *Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A); 1485 DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D)); 1486 1487 // Append the fake DeclStmt to block. 1488 B = VisitDeclSubExpr(DSNew); 1489 } 1490 1491 return B; 1492} 1493 1494/// VisitDeclSubExpr - Utility method to add block-level expressions for 1495/// DeclStmts and initializers in them. 1496CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) { 1497 assert(DS->isSingleDecl() && "Can handle single declarations only."); 1498 Decl *D = DS->getSingleDecl(); 1499 1500 if (isa<StaticAssertDecl>(D)) { 1501 // static_asserts aren't added to the CFG because they do not impact 1502 // runtime semantics. 1503 return Block; 1504 } 1505 1506 VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl()); 1507 1508 if (!VD) { 1509 autoCreateBlock(); 1510 appendStmt(Block, DS); 1511 return Block; 1512 } 1513 1514 bool IsReference = false; 1515 bool HasTemporaries = false; 1516 1517 // Destructors of temporaries in initialization expression should be called 1518 // after initialization finishes. 1519 Expr *Init = VD->getInit(); 1520 if (Init) { 1521 IsReference = VD->getType()->isReferenceType(); 1522 HasTemporaries = isa<ExprWithCleanups>(Init); 1523 1524 if (BuildOpts.AddImplicitDtors && HasTemporaries) { 1525 // Generate destructors for temporaries in initialization expression. 1526 VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(), 1527 IsReference); 1528 } 1529 } 1530 1531 autoCreateBlock(); 1532 appendStmt(Block, DS); 1533 1534 // Keep track of the last non-null block, as 'Block' can be nulled out 1535 // if the initializer expression is something like a 'while' in a 1536 // statement-expression. 1537 CFGBlock *LastBlock = Block; 1538 1539 if (Init) { 1540 if (HasTemporaries) { 1541 // For expression with temporaries go directly to subexpression to omit 1542 // generating destructors for the second time. 1543 ExprWithCleanups *EC = cast<ExprWithCleanups>(Init); 1544 if (CFGBlock *newBlock = Visit(EC->getSubExpr())) 1545 LastBlock = newBlock; 1546 } 1547 else { 1548 if (CFGBlock *newBlock = Visit(Init)) 1549 LastBlock = newBlock; 1550 } 1551 } 1552 1553 // If the type of VD is a VLA, then we must process its size expressions. 1554 for (const VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); 1555 VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) 1556 Block = addStmt(VA->getSizeExpr()); 1557 1558 // Remove variable from local scope. 1559 if (ScopePos && VD == *ScopePos) 1560 ++ScopePos; 1561 1562 return Block ? Block : LastBlock; 1563} 1564 1565CFGBlock *CFGBuilder::VisitIfStmt(IfStmt *I) { 1566 // We may see an if statement in the middle of a basic block, or it may be the 1567 // first statement we are processing. In either case, we create a new basic 1568 // block. First, we create the blocks for the then...else statements, and 1569 // then we create the block containing the if statement. If we were in the 1570 // middle of a block, we stop processing that block. That block is then the 1571 // implicit successor for the "then" and "else" clauses. 1572 1573 // Save local scope position because in case of condition variable ScopePos 1574 // won't be restored when traversing AST. 1575 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 1576 1577 // Create local scope for possible condition variable. 1578 // Store scope position. Add implicit destructor. 1579 if (VarDecl *VD = I->getConditionVariable()) { 1580 LocalScope::const_iterator BeginScopePos = ScopePos; 1581 addLocalScopeForVarDecl(VD); 1582 addAutomaticObjDtors(ScopePos, BeginScopePos, I); 1583 } 1584 1585 // The block we were processing is now finished. Make it the successor 1586 // block. 1587 if (Block) { 1588 Succ = Block; 1589 if (badCFG) 1590 return 0; 1591 } 1592 1593 // Process the false branch. 1594 CFGBlock *ElseBlock = Succ; 1595 1596 if (Stmt *Else = I->getElse()) { 1597 SaveAndRestore<CFGBlock*> sv(Succ); 1598 1599 // NULL out Block so that the recursive call to Visit will 1600 // create a new basic block. 1601 Block = NULL; 1602 1603 // If branch is not a compound statement create implicit scope 1604 // and add destructors. 1605 if (!isa<CompoundStmt>(Else)) 1606 addLocalScopeAndDtors(Else); 1607 1608 ElseBlock = addStmt(Else); 1609 1610 if (!ElseBlock) // Can occur when the Else body has all NullStmts. 1611 ElseBlock = sv.get(); 1612 else if (Block) { 1613 if (badCFG) 1614 return 0; 1615 } 1616 } 1617 1618 // Process the true branch. 1619 CFGBlock *ThenBlock; 1620 { 1621 Stmt *Then = I->getThen(); 1622 assert(Then); 1623 SaveAndRestore<CFGBlock*> sv(Succ); 1624 Block = NULL; 1625 1626 // If branch is not a compound statement create implicit scope 1627 // and add destructors. 1628 if (!isa<CompoundStmt>(Then)) 1629 addLocalScopeAndDtors(Then); 1630 1631 ThenBlock = addStmt(Then); 1632 1633 if (!ThenBlock) { 1634 // We can reach here if the "then" body has all NullStmts. 1635 // Create an empty block so we can distinguish between true and false 1636 // branches in path-sensitive analyses. 1637 ThenBlock = createBlock(false); 1638 addSuccessor(ThenBlock, sv.get()); 1639 } else if (Block) { 1640 if (badCFG) 1641 return 0; 1642 } 1643 } 1644 1645 // Now create a new block containing the if statement. 1646 Block = createBlock(false); 1647 1648 // Set the terminator of the new block to the If statement. 1649 Block->setTerminator(I); 1650 1651 // See if this is a known constant. 1652 const TryResult &KnownVal = tryEvaluateBool(I->getCond()); 1653 1654 // Now add the successors. 1655 addSuccessor(Block, KnownVal.isFalse() ? NULL : ThenBlock); 1656 addSuccessor(Block, KnownVal.isTrue()? NULL : ElseBlock); 1657 1658 // Add the condition as the last statement in the new block. This may create 1659 // new blocks as the condition may contain control-flow. Any newly created 1660 // blocks will be pointed to be "Block". 1661 Block = addStmt(I->getCond()); 1662 1663 // Finally, if the IfStmt contains a condition variable, add both the IfStmt 1664 // and the condition variable initialization to the CFG. 1665 if (VarDecl *VD = I->getConditionVariable()) { 1666 if (Expr *Init = VD->getInit()) { 1667 autoCreateBlock(); 1668 appendStmt(Block, I->getConditionVariableDeclStmt()); 1669 addStmt(Init); 1670 } 1671 } 1672 1673 return Block; 1674} 1675 1676 1677CFGBlock *CFGBuilder::VisitReturnStmt(ReturnStmt *R) { 1678 // If we were in the middle of a block we stop processing that block. 1679 // 1680 // NOTE: If a "return" appears in the middle of a block, this means that the 1681 // code afterwards is DEAD (unreachable). We still keep a basic block 1682 // for that code; a simple "mark-and-sweep" from the entry block will be 1683 // able to report such dead blocks. 1684 1685 // Create the new block. 1686 Block = createBlock(false); 1687 1688 // The Exit block is the only successor. 1689 addAutomaticObjDtors(ScopePos, LocalScope::const_iterator(), R); 1690 addSuccessor(Block, &cfg->getExit()); 1691 1692 // Add the return statement to the block. This may create new blocks if R 1693 // contains control-flow (short-circuit operations). 1694 return VisitStmt(R, AddStmtChoice::AlwaysAdd); 1695} 1696 1697CFGBlock *CFGBuilder::VisitLabelStmt(LabelStmt *L) { 1698 // Get the block of the labeled statement. Add it to our map. 1699 addStmt(L->getSubStmt()); 1700 CFGBlock *LabelBlock = Block; 1701 1702 if (!LabelBlock) // This can happen when the body is empty, i.e. 1703 LabelBlock = createBlock(); // scopes that only contains NullStmts. 1704 1705 assert(LabelMap.find(L->getDecl()) == LabelMap.end() && 1706 "label already in map"); 1707 LabelMap[L->getDecl()] = JumpTarget(LabelBlock, ScopePos); 1708 1709 // Labels partition blocks, so this is the end of the basic block we were 1710 // processing (L is the block's label). Because this is label (and we have 1711 // already processed the substatement) there is no extra control-flow to worry 1712 // about. 1713 LabelBlock->setLabel(L); 1714 if (badCFG) 1715 return 0; 1716 1717 // We set Block to NULL to allow lazy creation of a new block (if necessary); 1718 Block = NULL; 1719 1720 // This block is now the implicit successor of other blocks. 1721 Succ = LabelBlock; 1722 1723 return LabelBlock; 1724} 1725 1726CFGBlock *CFGBuilder::VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc) { 1727 CFGBlock *LastBlock = VisitNoRecurse(E, asc); 1728 for (LambdaExpr::capture_init_iterator it = E->capture_init_begin(), 1729 et = E->capture_init_end(); it != et; ++it) { 1730 if (Expr *Init = *it) { 1731 CFGBlock *Tmp = Visit(Init); 1732 if (Tmp != 0) 1733 LastBlock = Tmp; 1734 } 1735 } 1736 return LastBlock; 1737} 1738 1739CFGBlock *CFGBuilder::VisitGotoStmt(GotoStmt *G) { 1740 // Goto is a control-flow statement. Thus we stop processing the current 1741 // block and create a new one. 1742 1743 Block = createBlock(false); 1744 Block->setTerminator(G); 1745 1746 // If we already know the mapping to the label block add the successor now. 1747 LabelMapTy::iterator I = LabelMap.find(G->getLabel()); 1748 1749 if (I == LabelMap.end()) 1750 // We will need to backpatch this block later. 1751 BackpatchBlocks.push_back(JumpSource(Block, ScopePos)); 1752 else { 1753 JumpTarget JT = I->second; 1754 addAutomaticObjDtors(ScopePos, JT.scopePosition, G); 1755 addSuccessor(Block, JT.block); 1756 } 1757 1758 return Block; 1759} 1760 1761CFGBlock *CFGBuilder::VisitForStmt(ForStmt *F) { 1762 CFGBlock *LoopSuccessor = NULL; 1763 1764 // Save local scope position because in case of condition variable ScopePos 1765 // won't be restored when traversing AST. 1766 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 1767 1768 // Create local scope for init statement and possible condition variable. 1769 // Add destructor for init statement and condition variable. 1770 // Store scope position for continue statement. 1771 if (Stmt *Init = F->getInit()) 1772 addLocalScopeForStmt(Init); 1773 LocalScope::const_iterator LoopBeginScopePos = ScopePos; 1774 1775 if (VarDecl *VD = F->getConditionVariable()) 1776 addLocalScopeForVarDecl(VD); 1777 LocalScope::const_iterator ContinueScopePos = ScopePos; 1778 1779 addAutomaticObjDtors(ScopePos, save_scope_pos.get(), F); 1780 1781 // "for" is a control-flow statement. Thus we stop processing the current 1782 // block. 1783 if (Block) { 1784 if (badCFG) 1785 return 0; 1786 LoopSuccessor = Block; 1787 } else 1788 LoopSuccessor = Succ; 1789 1790 // Save the current value for the break targets. 1791 // All breaks should go to the code following the loop. 1792 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget); 1793 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 1794 1795 // Because of short-circuit evaluation, the condition of the loop can span 1796 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 1797 // evaluate the condition. 1798 CFGBlock *ExitConditionBlock = createBlock(false); 1799 CFGBlock *EntryConditionBlock = ExitConditionBlock; 1800 1801 // Set the terminator for the "exit" condition block. 1802 ExitConditionBlock->setTerminator(F); 1803 1804 // Now add the actual condition to the condition block. Because the condition 1805 // itself may contain control-flow, new blocks may be created. 1806 if (Stmt *C = F->getCond()) { 1807 Block = ExitConditionBlock; 1808 EntryConditionBlock = addStmt(C); 1809 if (badCFG) 1810 return 0; 1811 assert(Block == EntryConditionBlock || 1812 (Block == 0 && EntryConditionBlock == Succ)); 1813 1814 // If this block contains a condition variable, add both the condition 1815 // variable and initializer to the CFG. 1816 if (VarDecl *VD = F->getConditionVariable()) { 1817 if (Expr *Init = VD->getInit()) { 1818 autoCreateBlock(); 1819 appendStmt(Block, F->getConditionVariableDeclStmt()); 1820 EntryConditionBlock = addStmt(Init); 1821 assert(Block == EntryConditionBlock); 1822 } 1823 } 1824 1825 if (Block) { 1826 if (badCFG) 1827 return 0; 1828 } 1829 } 1830 1831 // The condition block is the implicit successor for the loop body as well as 1832 // any code above the loop. 1833 Succ = EntryConditionBlock; 1834 1835 // See if this is a known constant. 1836 TryResult KnownVal(true); 1837 1838 if (F->getCond()) 1839 KnownVal = tryEvaluateBool(F->getCond()); 1840 1841 // Now create the loop body. 1842 { 1843 assert(F->getBody()); 1844 1845 // Save the current values for Block, Succ, and continue targets. 1846 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); 1847 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget); 1848 1849 // Create a new block to contain the (bottom) of the loop body. 1850 Block = NULL; 1851 1852 // Loop body should end with destructor of Condition variable (if any). 1853 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, F); 1854 1855 if (Stmt *I = F->getInc()) { 1856 // Generate increment code in its own basic block. This is the target of 1857 // continue statements. 1858 Succ = addStmt(I); 1859 } else { 1860 // No increment code. Create a special, empty, block that is used as the 1861 // target block for "looping back" to the start of the loop. 1862 assert(Succ == EntryConditionBlock); 1863 Succ = Block ? Block : createBlock(); 1864 } 1865 1866 // Finish up the increment (or empty) block if it hasn't been already. 1867 if (Block) { 1868 assert(Block == Succ); 1869 if (badCFG) 1870 return 0; 1871 Block = 0; 1872 } 1873 1874 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos); 1875 1876 // The starting block for the loop increment is the block that should 1877 // represent the 'loop target' for looping back to the start of the loop. 1878 ContinueJumpTarget.block->setLoopTarget(F); 1879 1880 // If body is not a compound statement create implicit scope 1881 // and add destructors. 1882 if (!isa<CompoundStmt>(F->getBody())) 1883 addLocalScopeAndDtors(F->getBody()); 1884 1885 // Now populate the body block, and in the process create new blocks as we 1886 // walk the body of the loop. 1887 CFGBlock *BodyBlock = addStmt(F->getBody()); 1888 1889 if (!BodyBlock) 1890 BodyBlock = ContinueJumpTarget.block;//can happen for "for (...;...;...);" 1891 else if (badCFG) 1892 return 0; 1893 1894 // This new body block is a successor to our "exit" condition block. 1895 addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); 1896 } 1897 1898 // Link up the condition block with the code that follows the loop. (the 1899 // false branch). 1900 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 1901 1902 // If the loop contains initialization, create a new block for those 1903 // statements. This block can also contain statements that precede the loop. 1904 if (Stmt *I = F->getInit()) { 1905 Block = createBlock(); 1906 return addStmt(I); 1907 } 1908 1909 // There is no loop initialization. We are thus basically a while loop. 1910 // NULL out Block to force lazy block construction. 1911 Block = NULL; 1912 Succ = EntryConditionBlock; 1913 return EntryConditionBlock; 1914} 1915 1916CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) { 1917 if (asc.alwaysAdd(*this, M)) { 1918 autoCreateBlock(); 1919 appendStmt(Block, M); 1920 } 1921 return Visit(M->getBase()); 1922} 1923 1924CFGBlock *CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt *S) { 1925 // Objective-C fast enumeration 'for' statements: 1926 // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC 1927 // 1928 // for ( Type newVariable in collection_expression ) { statements } 1929 // 1930 // becomes: 1931 // 1932 // prologue: 1933 // 1. collection_expression 1934 // T. jump to loop_entry 1935 // loop_entry: 1936 // 1. side-effects of element expression 1937 // 1. ObjCForCollectionStmt [performs binding to newVariable] 1938 // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil] 1939 // TB: 1940 // statements 1941 // T. jump to loop_entry 1942 // FB: 1943 // what comes after 1944 // 1945 // and 1946 // 1947 // Type existingItem; 1948 // for ( existingItem in expression ) { statements } 1949 // 1950 // becomes: 1951 // 1952 // the same with newVariable replaced with existingItem; the binding works 1953 // the same except that for one ObjCForCollectionStmt::getElement() returns 1954 // a DeclStmt and the other returns a DeclRefExpr. 1955 // 1956 1957 CFGBlock *LoopSuccessor = 0; 1958 1959 if (Block) { 1960 if (badCFG) 1961 return 0; 1962 LoopSuccessor = Block; 1963 Block = 0; 1964 } else 1965 LoopSuccessor = Succ; 1966 1967 // Build the condition blocks. 1968 CFGBlock *ExitConditionBlock = createBlock(false); 1969 1970 // Set the terminator for the "exit" condition block. 1971 ExitConditionBlock->setTerminator(S); 1972 1973 // The last statement in the block should be the ObjCForCollectionStmt, which 1974 // performs the actual binding to 'element' and determines if there are any 1975 // more items in the collection. 1976 appendStmt(ExitConditionBlock, S); 1977 Block = ExitConditionBlock; 1978 1979 // Walk the 'element' expression to see if there are any side-effects. We 1980 // generate new blocks as necessary. We DON'T add the statement by default to 1981 // the CFG unless it contains control-flow. 1982 CFGBlock *EntryConditionBlock = Visit(S->getElement(), 1983 AddStmtChoice::NotAlwaysAdd); 1984 if (Block) { 1985 if (badCFG) 1986 return 0; 1987 Block = 0; 1988 } 1989 1990 // The condition block is the implicit successor for the loop body as well as 1991 // any code above the loop. 1992 Succ = EntryConditionBlock; 1993 1994 // Now create the true branch. 1995 { 1996 // Save the current values for Succ, continue and break targets. 1997 SaveAndRestore<CFGBlock*> save_Succ(Succ); 1998 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), 1999 save_break(BreakJumpTarget); 2000 2001 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 2002 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos); 2003 2004 CFGBlock *BodyBlock = addStmt(S->getBody()); 2005 2006 if (!BodyBlock) 2007 BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;" 2008 else if (Block) { 2009 if (badCFG) 2010 return 0; 2011 } 2012 2013 // This new body block is a successor to our "exit" condition block. 2014 addSuccessor(ExitConditionBlock, BodyBlock); 2015 } 2016 2017 // Link up the condition block with the code that follows the loop. 2018 // (the false branch). 2019 addSuccessor(ExitConditionBlock, LoopSuccessor); 2020 2021 // Now create a prologue block to contain the collection expression. 2022 Block = createBlock(); 2023 return addStmt(S->getCollection()); 2024} 2025 2026CFGBlock *CFGBuilder::VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S) { 2027 // Inline the body. 2028 return addStmt(S->getSubStmt()); 2029 // TODO: consider adding cleanups for the end of @autoreleasepool scope. 2030} 2031 2032CFGBlock *CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S) { 2033 // FIXME: Add locking 'primitives' to CFG for @synchronized. 2034 2035 // Inline the body. 2036 CFGBlock *SyncBlock = addStmt(S->getSynchBody()); 2037 2038 // The sync body starts its own basic block. This makes it a little easier 2039 // for diagnostic clients. 2040 if (SyncBlock) { 2041 if (badCFG) 2042 return 0; 2043 2044 Block = 0; 2045 Succ = SyncBlock; 2046 } 2047 2048 // Add the @synchronized to the CFG. 2049 autoCreateBlock(); 2050 appendStmt(Block, S); 2051 2052 // Inline the sync expression. 2053 return addStmt(S->getSynchExpr()); 2054} 2055 2056CFGBlock *CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt *S) { 2057 // FIXME 2058 return NYS(); 2059} 2060 2061CFGBlock *CFGBuilder::VisitPseudoObjectExpr(PseudoObjectExpr *E) { 2062 autoCreateBlock(); 2063 2064 // Add the PseudoObject as the last thing. 2065 appendStmt(Block, E); 2066 2067 CFGBlock *lastBlock = Block; 2068 2069 // Before that, evaluate all of the semantics in order. In 2070 // CFG-land, that means appending them in reverse order. 2071 for (unsigned i = E->getNumSemanticExprs(); i != 0; ) { 2072 Expr *Semantic = E->getSemanticExpr(--i); 2073 2074 // If the semantic is an opaque value, we're being asked to bind 2075 // it to its source expression. 2076 if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic)) 2077 Semantic = OVE->getSourceExpr(); 2078 2079 if (CFGBlock *B = Visit(Semantic)) 2080 lastBlock = B; 2081 } 2082 2083 return lastBlock; 2084} 2085 2086CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) { 2087 CFGBlock *LoopSuccessor = NULL; 2088 2089 // Save local scope position because in case of condition variable ScopePos 2090 // won't be restored when traversing AST. 2091 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 2092 2093 // Create local scope for possible condition variable. 2094 // Store scope position for continue statement. 2095 LocalScope::const_iterator LoopBeginScopePos = ScopePos; 2096 if (VarDecl *VD = W->getConditionVariable()) { 2097 addLocalScopeForVarDecl(VD); 2098 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W); 2099 } 2100 2101 // "while" is a control-flow statement. Thus we stop processing the current 2102 // block. 2103 if (Block) { 2104 if (badCFG) 2105 return 0; 2106 LoopSuccessor = Block; 2107 Block = 0; 2108 } else 2109 LoopSuccessor = Succ; 2110 2111 // Because of short-circuit evaluation, the condition of the loop can span 2112 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 2113 // evaluate the condition. 2114 CFGBlock *ExitConditionBlock = createBlock(false); 2115 CFGBlock *EntryConditionBlock = ExitConditionBlock; 2116 2117 // Set the terminator for the "exit" condition block. 2118 ExitConditionBlock->setTerminator(W); 2119 2120 // Now add the actual condition to the condition block. Because the condition 2121 // itself may contain control-flow, new blocks may be created. Thus we update 2122 // "Succ" after adding the condition. 2123 if (Stmt *C = W->getCond()) { 2124 Block = ExitConditionBlock; 2125 EntryConditionBlock = addStmt(C); 2126 // The condition might finish the current 'Block'. 2127 Block = EntryConditionBlock; 2128 2129 // If this block contains a condition variable, add both the condition 2130 // variable and initializer to the CFG. 2131 if (VarDecl *VD = W->getConditionVariable()) { 2132 if (Expr *Init = VD->getInit()) { 2133 autoCreateBlock(); 2134 appendStmt(Block, W->getConditionVariableDeclStmt()); 2135 EntryConditionBlock = addStmt(Init); 2136 assert(Block == EntryConditionBlock); 2137 } 2138 } 2139 2140 if (Block) { 2141 if (badCFG) 2142 return 0; 2143 } 2144 } 2145 2146 // The condition block is the implicit successor for the loop body as well as 2147 // any code above the loop. 2148 Succ = EntryConditionBlock; 2149 2150 // See if this is a known constant. 2151 const TryResult& KnownVal = tryEvaluateBool(W->getCond()); 2152 2153 // Process the loop body. 2154 { 2155 assert(W->getBody()); 2156 2157 // Save the current values for Block, Succ, and continue and break targets 2158 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); 2159 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), 2160 save_break(BreakJumpTarget); 2161 2162 // Create an empty block to represent the transition block for looping back 2163 // to the head of the loop. 2164 Block = 0; 2165 assert(Succ == EntryConditionBlock); 2166 Succ = createBlock(); 2167 Succ->setLoopTarget(W); 2168 ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos); 2169 2170 // All breaks should go to the code following the loop. 2171 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 2172 2173 // NULL out Block to force lazy instantiation of blocks for the body. 2174 Block = NULL; 2175 2176 // Loop body should end with destructor of Condition variable (if any). 2177 addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W); 2178 2179 // If body is not a compound statement create implicit scope 2180 // and add destructors. 2181 if (!isa<CompoundStmt>(W->getBody())) 2182 addLocalScopeAndDtors(W->getBody()); 2183 2184 // Create the body. The returned block is the entry to the loop body. 2185 CFGBlock *BodyBlock = addStmt(W->getBody()); 2186 2187 if (!BodyBlock) 2188 BodyBlock = ContinueJumpTarget.block; // can happen for "while(...) ;" 2189 else if (Block) { 2190 if (badCFG) 2191 return 0; 2192 } 2193 2194 // Add the loop body entry as a successor to the condition. 2195 addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); 2196 } 2197 2198 // Link up the condition block with the code that follows the loop. (the 2199 // false branch). 2200 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 2201 2202 // There can be no more statements in the condition block since we loop back 2203 // to this block. NULL out Block to force lazy creation of another block. 2204 Block = NULL; 2205 2206 // Return the condition block, which is the dominating block for the loop. 2207 Succ = EntryConditionBlock; 2208 return EntryConditionBlock; 2209} 2210 2211 2212CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt *S) { 2213 // FIXME: For now we pretend that @catch and the code it contains does not 2214 // exit. 2215 return Block; 2216} 2217 2218CFGBlock *CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt *S) { 2219 // FIXME: This isn't complete. We basically treat @throw like a return 2220 // statement. 2221 2222 // If we were in the middle of a block we stop processing that block. 2223 if (badCFG) 2224 return 0; 2225 2226 // Create the new block. 2227 Block = createBlock(false); 2228 2229 // The Exit block is the only successor. 2230 addSuccessor(Block, &cfg->getExit()); 2231 2232 // Add the statement to the block. This may create new blocks if S contains 2233 // control-flow (short-circuit operations). 2234 return VisitStmt(S, AddStmtChoice::AlwaysAdd); 2235} 2236 2237CFGBlock *CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr *T) { 2238 // If we were in the middle of a block we stop processing that block. 2239 if (badCFG) 2240 return 0; 2241 2242 // Create the new block. 2243 Block = createBlock(false); 2244 2245 if (TryTerminatedBlock) 2246 // The current try statement is the only successor. 2247 addSuccessor(Block, TryTerminatedBlock); 2248 else 2249 // otherwise the Exit block is the only successor. 2250 addSuccessor(Block, &cfg->getExit()); 2251 2252 // Add the statement to the block. This may create new blocks if S contains 2253 // control-flow (short-circuit operations). 2254 return VisitStmt(T, AddStmtChoice::AlwaysAdd); 2255} 2256 2257CFGBlock *CFGBuilder::VisitDoStmt(DoStmt *D) { 2258 CFGBlock *LoopSuccessor = NULL; 2259 2260 // "do...while" is a control-flow statement. Thus we stop processing the 2261 // current block. 2262 if (Block) { 2263 if (badCFG) 2264 return 0; 2265 LoopSuccessor = Block; 2266 } else 2267 LoopSuccessor = Succ; 2268 2269 // Because of short-circuit evaluation, the condition of the loop can span 2270 // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that 2271 // evaluate the condition. 2272 CFGBlock *ExitConditionBlock = createBlock(false); 2273 CFGBlock *EntryConditionBlock = ExitConditionBlock; 2274 2275 // Set the terminator for the "exit" condition block. 2276 ExitConditionBlock->setTerminator(D); 2277 2278 // Now add the actual condition to the condition block. Because the condition 2279 // itself may contain control-flow, new blocks may be created. 2280 if (Stmt *C = D->getCond()) { 2281 Block = ExitConditionBlock; 2282 EntryConditionBlock = addStmt(C); 2283 if (Block) { 2284 if (badCFG) 2285 return 0; 2286 } 2287 } 2288 2289 // The condition block is the implicit successor for the loop body. 2290 Succ = EntryConditionBlock; 2291 2292 // See if this is a known constant. 2293 const TryResult &KnownVal = tryEvaluateBool(D->getCond()); 2294 2295 // Process the loop body. 2296 CFGBlock *BodyBlock = NULL; 2297 { 2298 assert(D->getBody()); 2299 2300 // Save the current values for Block, Succ, and continue and break targets 2301 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); 2302 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), 2303 save_break(BreakJumpTarget); 2304 2305 // All continues within this loop should go to the condition block 2306 ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos); 2307 2308 // All breaks should go to the code following the loop. 2309 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 2310 2311 // NULL out Block to force lazy instantiation of blocks for the body. 2312 Block = NULL; 2313 2314 // If body is not a compound statement create implicit scope 2315 // and add destructors. 2316 if (!isa<CompoundStmt>(D->getBody())) 2317 addLocalScopeAndDtors(D->getBody()); 2318 2319 // Create the body. The returned block is the entry to the loop body. 2320 BodyBlock = addStmt(D->getBody()); 2321 2322 if (!BodyBlock) 2323 BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)" 2324 else if (Block) { 2325 if (badCFG) 2326 return 0; 2327 } 2328 2329 if (!KnownVal.isFalse()) { 2330 // Add an intermediate block between the BodyBlock and the 2331 // ExitConditionBlock to represent the "loop back" transition. Create an 2332 // empty block to represent the transition block for looping back to the 2333 // head of the loop. 2334 // FIXME: Can we do this more efficiently without adding another block? 2335 Block = NULL; 2336 Succ = BodyBlock; 2337 CFGBlock *LoopBackBlock = createBlock(); 2338 LoopBackBlock->setLoopTarget(D); 2339 2340 // Add the loop body entry as a successor to the condition. 2341 addSuccessor(ExitConditionBlock, LoopBackBlock); 2342 } 2343 else 2344 addSuccessor(ExitConditionBlock, NULL); 2345 } 2346 2347 // Link up the condition block with the code that follows the loop. 2348 // (the false branch). 2349 addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); 2350 2351 // There can be no more statements in the body block(s) since we loop back to 2352 // the body. NULL out Block to force lazy creation of another block. 2353 Block = NULL; 2354 2355 // Return the loop body, which is the dominating block for the loop. 2356 Succ = BodyBlock; 2357 return BodyBlock; 2358} 2359 2360CFGBlock *CFGBuilder::VisitContinueStmt(ContinueStmt *C) { 2361 // "continue" is a control-flow statement. Thus we stop processing the 2362 // current block. 2363 if (badCFG) 2364 return 0; 2365 2366 // Now create a new block that ends with the continue statement. 2367 Block = createBlock(false); 2368 Block->setTerminator(C); 2369 2370 // If there is no target for the continue, then we are looking at an 2371 // incomplete AST. This means the CFG cannot be constructed. 2372 if (ContinueJumpTarget.block) { 2373 addAutomaticObjDtors(ScopePos, ContinueJumpTarget.scopePosition, C); 2374 addSuccessor(Block, ContinueJumpTarget.block); 2375 } else 2376 badCFG = true; 2377 2378 return Block; 2379} 2380 2381CFGBlock *CFGBuilder::VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E, 2382 AddStmtChoice asc) { 2383 2384 if (asc.alwaysAdd(*this, E)) { 2385 autoCreateBlock(); 2386 appendStmt(Block, E); 2387 } 2388 2389 // VLA types have expressions that must be evaluated. 2390 CFGBlock *lastBlock = Block; 2391 2392 if (E->isArgumentType()) { 2393 for (const VariableArrayType *VA =FindVA(E->getArgumentType().getTypePtr()); 2394 VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) 2395 lastBlock = addStmt(VA->getSizeExpr()); 2396 } 2397 return lastBlock; 2398} 2399 2400/// VisitStmtExpr - Utility method to handle (nested) statement 2401/// expressions (a GCC extension). 2402CFGBlock *CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) { 2403 if (asc.alwaysAdd(*this, SE)) { 2404 autoCreateBlock(); 2405 appendStmt(Block, SE); 2406 } 2407 return VisitCompoundStmt(SE->getSubStmt()); 2408} 2409 2410CFGBlock *CFGBuilder::VisitSwitchStmt(SwitchStmt *Terminator) { 2411 // "switch" is a control-flow statement. Thus we stop processing the current 2412 // block. 2413 CFGBlock *SwitchSuccessor = NULL; 2414 2415 // Save local scope position because in case of condition variable ScopePos 2416 // won't be restored when traversing AST. 2417 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 2418 2419 // Create local scope for possible condition variable. 2420 // Store scope position. Add implicit destructor. 2421 if (VarDecl *VD = Terminator->getConditionVariable()) { 2422 LocalScope::const_iterator SwitchBeginScopePos = ScopePos; 2423 addLocalScopeForVarDecl(VD); 2424 addAutomaticObjDtors(ScopePos, SwitchBeginScopePos, Terminator); 2425 } 2426 2427 if (Block) { 2428 if (badCFG) 2429 return 0; 2430 SwitchSuccessor = Block; 2431 } else SwitchSuccessor = Succ; 2432 2433 // Save the current "switch" context. 2434 SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock), 2435 save_default(DefaultCaseBlock); 2436 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget); 2437 2438 // Set the "default" case to be the block after the switch statement. If the 2439 // switch statement contains a "default:", this value will be overwritten with 2440 // the block for that code. 2441 DefaultCaseBlock = SwitchSuccessor; 2442 2443 // Create a new block that will contain the switch statement. 2444 SwitchTerminatedBlock = createBlock(false); 2445 2446 // Now process the switch body. The code after the switch is the implicit 2447 // successor. 2448 Succ = SwitchSuccessor; 2449 BreakJumpTarget = JumpTarget(SwitchSuccessor, ScopePos); 2450 2451 // When visiting the body, the case statements should automatically get linked 2452 // up to the switch. We also don't keep a pointer to the body, since all 2453 // control-flow from the switch goes to case/default statements. 2454 assert(Terminator->getBody() && "switch must contain a non-NULL body"); 2455 Block = NULL; 2456 2457 // For pruning unreachable case statements, save the current state 2458 // for tracking the condition value. 2459 SaveAndRestore<bool> save_switchExclusivelyCovered(switchExclusivelyCovered, 2460 false); 2461 2462 // Determine if the switch condition can be explicitly evaluated. 2463 assert(Terminator->getCond() && "switch condition must be non-NULL"); 2464 Expr::EvalResult result; 2465 bool b = tryEvaluate(Terminator->getCond(), result); 2466 SaveAndRestore<Expr::EvalResult*> save_switchCond(switchCond, 2467 b ? &result : 0); 2468 2469 // If body is not a compound statement create implicit scope 2470 // and add destructors. 2471 if (!isa<CompoundStmt>(Terminator->getBody())) 2472 addLocalScopeAndDtors(Terminator->getBody()); 2473 2474 addStmt(Terminator->getBody()); 2475 if (Block) { 2476 if (badCFG) 2477 return 0; 2478 } 2479 2480 // If we have no "default:" case, the default transition is to the code 2481 // following the switch body. Moreover, take into account if all the 2482 // cases of a switch are covered (e.g., switching on an enum value). 2483 addSuccessor(SwitchTerminatedBlock, 2484 switchExclusivelyCovered || Terminator->isAllEnumCasesCovered() 2485 ? 0 : DefaultCaseBlock); 2486 2487 // Add the terminator and condition in the switch block. 2488 SwitchTerminatedBlock->setTerminator(Terminator); 2489 Block = SwitchTerminatedBlock; 2490 Block = addStmt(Terminator->getCond()); 2491 2492 // Finally, if the SwitchStmt contains a condition variable, add both the 2493 // SwitchStmt and the condition variable initialization to the CFG. 2494 if (VarDecl *VD = Terminator->getConditionVariable()) { 2495 if (Expr *Init = VD->getInit()) { 2496 autoCreateBlock(); 2497 appendStmt(Block, Terminator->getConditionVariableDeclStmt()); 2498 addStmt(Init); 2499 } 2500 } 2501 2502 return Block; 2503} 2504 2505static bool shouldAddCase(bool &switchExclusivelyCovered, 2506 const Expr::EvalResult *switchCond, 2507 const CaseStmt *CS, 2508 ASTContext &Ctx) { 2509 if (!switchCond) 2510 return true; 2511 2512 bool addCase = false; 2513 2514 if (!switchExclusivelyCovered) { 2515 if (switchCond->Val.isInt()) { 2516 // Evaluate the LHS of the case value. 2517 const llvm::APSInt &lhsInt = CS->getLHS()->EvaluateKnownConstInt(Ctx); 2518 const llvm::APSInt &condInt = switchCond->Val.getInt(); 2519 2520 if (condInt == lhsInt) { 2521 addCase = true; 2522 switchExclusivelyCovered = true; 2523 } 2524 else if (condInt < lhsInt) { 2525 if (const Expr *RHS = CS->getRHS()) { 2526 // Evaluate the RHS of the case value. 2527 const llvm::APSInt &V2 = RHS->EvaluateKnownConstInt(Ctx); 2528 if (V2 <= condInt) { 2529 addCase = true; 2530 switchExclusivelyCovered = true; 2531 } 2532 } 2533 } 2534 } 2535 else 2536 addCase = true; 2537 } 2538 return addCase; 2539} 2540 2541CFGBlock *CFGBuilder::VisitCaseStmt(CaseStmt *CS) { 2542 // CaseStmts are essentially labels, so they are the first statement in a 2543 // block. 2544 CFGBlock *TopBlock = 0, *LastBlock = 0; 2545 2546 if (Stmt *Sub = CS->getSubStmt()) { 2547 // For deeply nested chains of CaseStmts, instead of doing a recursion 2548 // (which can blow out the stack), manually unroll and create blocks 2549 // along the way. 2550 while (isa<CaseStmt>(Sub)) { 2551 CFGBlock *currentBlock = createBlock(false); 2552 currentBlock->setLabel(CS); 2553 2554 if (TopBlock) 2555 addSuccessor(LastBlock, currentBlock); 2556 else 2557 TopBlock = currentBlock; 2558 2559 addSuccessor(SwitchTerminatedBlock, 2560 shouldAddCase(switchExclusivelyCovered, switchCond, 2561 CS, *Context) 2562 ? currentBlock : 0); 2563 2564 LastBlock = currentBlock; 2565 CS = cast<CaseStmt>(Sub); 2566 Sub = CS->getSubStmt(); 2567 } 2568 2569 addStmt(Sub); 2570 } 2571 2572 CFGBlock *CaseBlock = Block; 2573 if (!CaseBlock) 2574 CaseBlock = createBlock(); 2575 2576 // Cases statements partition blocks, so this is the top of the basic block we 2577 // were processing (the "case XXX:" is the label). 2578 CaseBlock->setLabel(CS); 2579 2580 if (badCFG) 2581 return 0; 2582 2583 // Add this block to the list of successors for the block with the switch 2584 // statement. 2585 assert(SwitchTerminatedBlock); 2586 addSuccessor(SwitchTerminatedBlock, 2587 shouldAddCase(switchExclusivelyCovered, switchCond, 2588 CS, *Context) 2589 ? CaseBlock : 0); 2590 2591 // We set Block to NULL to allow lazy creation of a new block (if necessary) 2592 Block = NULL; 2593 2594 if (TopBlock) { 2595 addSuccessor(LastBlock, CaseBlock); 2596 Succ = TopBlock; 2597 } else { 2598 // This block is now the implicit successor of other blocks. 2599 Succ = CaseBlock; 2600 } 2601 2602 return Succ; 2603} 2604 2605CFGBlock *CFGBuilder::VisitDefaultStmt(DefaultStmt *Terminator) { 2606 if (Terminator->getSubStmt()) 2607 addStmt(Terminator->getSubStmt()); 2608 2609 DefaultCaseBlock = Block; 2610 2611 if (!DefaultCaseBlock) 2612 DefaultCaseBlock = createBlock(); 2613 2614 // Default statements partition blocks, so this is the top of the basic block 2615 // we were processing (the "default:" is the label). 2616 DefaultCaseBlock->setLabel(Terminator); 2617 2618 if (badCFG) 2619 return 0; 2620 2621 // Unlike case statements, we don't add the default block to the successors 2622 // for the switch statement immediately. This is done when we finish 2623 // processing the switch statement. This allows for the default case 2624 // (including a fall-through to the code after the switch statement) to always 2625 // be the last successor of a switch-terminated block. 2626 2627 // We set Block to NULL to allow lazy creation of a new block (if necessary) 2628 Block = NULL; 2629 2630 // This block is now the implicit successor of other blocks. 2631 Succ = DefaultCaseBlock; 2632 2633 return DefaultCaseBlock; 2634} 2635 2636CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) { 2637 // "try"/"catch" is a control-flow statement. Thus we stop processing the 2638 // current block. 2639 CFGBlock *TrySuccessor = NULL; 2640 2641 if (Block) { 2642 if (badCFG) 2643 return 0; 2644 TrySuccessor = Block; 2645 } else TrySuccessor = Succ; 2646 2647 CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock; 2648 2649 // Create a new block that will contain the try statement. 2650 CFGBlock *NewTryTerminatedBlock = createBlock(false); 2651 // Add the terminator in the try block. 2652 NewTryTerminatedBlock->setTerminator(Terminator); 2653 2654 bool HasCatchAll = false; 2655 for (unsigned h = 0; h <Terminator->getNumHandlers(); ++h) { 2656 // The code after the try is the implicit successor. 2657 Succ = TrySuccessor; 2658 CXXCatchStmt *CS = Terminator->getHandler(h); 2659 if (CS->getExceptionDecl() == 0) { 2660 HasCatchAll = true; 2661 } 2662 Block = NULL; 2663 CFGBlock *CatchBlock = VisitCXXCatchStmt(CS); 2664 if (CatchBlock == 0) 2665 return 0; 2666 // Add this block to the list of successors for the block with the try 2667 // statement. 2668 addSuccessor(NewTryTerminatedBlock, CatchBlock); 2669 } 2670 if (!HasCatchAll) { 2671 if (PrevTryTerminatedBlock) 2672 addSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock); 2673 else 2674 addSuccessor(NewTryTerminatedBlock, &cfg->getExit()); 2675 } 2676 2677 // The code after the try is the implicit successor. 2678 Succ = TrySuccessor; 2679 2680 // Save the current "try" context. 2681 SaveAndRestore<CFGBlock*> save_try(TryTerminatedBlock, NewTryTerminatedBlock); 2682 cfg->addTryDispatchBlock(TryTerminatedBlock); 2683 2684 assert(Terminator->getTryBlock() && "try must contain a non-NULL body"); 2685 Block = NULL; 2686 Block = addStmt(Terminator->getTryBlock()); 2687 return Block; 2688} 2689 2690CFGBlock *CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt *CS) { 2691 // CXXCatchStmt are treated like labels, so they are the first statement in a 2692 // block. 2693 2694 // Save local scope position because in case of exception variable ScopePos 2695 // won't be restored when traversing AST. 2696 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 2697 2698 // Create local scope for possible exception variable. 2699 // Store scope position. Add implicit destructor. 2700 if (VarDecl *VD = CS->getExceptionDecl()) { 2701 LocalScope::const_iterator BeginScopePos = ScopePos; 2702 addLocalScopeForVarDecl(VD); 2703 addAutomaticObjDtors(ScopePos, BeginScopePos, CS); 2704 } 2705 2706 if (CS->getHandlerBlock()) 2707 addStmt(CS->getHandlerBlock()); 2708 2709 CFGBlock *CatchBlock = Block; 2710 if (!CatchBlock) 2711 CatchBlock = createBlock(); 2712 2713 // CXXCatchStmt is more than just a label. They have semantic meaning 2714 // as well, as they implicitly "initialize" the catch variable. Add 2715 // it to the CFG as a CFGElement so that the control-flow of these 2716 // semantics gets captured. 2717 appendStmt(CatchBlock, CS); 2718 2719 // Also add the CXXCatchStmt as a label, to mirror handling of regular 2720 // labels. 2721 CatchBlock->setLabel(CS); 2722 2723 // Bail out if the CFG is bad. 2724 if (badCFG) 2725 return 0; 2726 2727 // We set Block to NULL to allow lazy creation of a new block (if necessary) 2728 Block = NULL; 2729 2730 return CatchBlock; 2731} 2732 2733CFGBlock *CFGBuilder::VisitCXXForRangeStmt(CXXForRangeStmt *S) { 2734 // C++0x for-range statements are specified as [stmt.ranged]: 2735 // 2736 // { 2737 // auto && __range = range-init; 2738 // for ( auto __begin = begin-expr, 2739 // __end = end-expr; 2740 // __begin != __end; 2741 // ++__begin ) { 2742 // for-range-declaration = *__begin; 2743 // statement 2744 // } 2745 // } 2746 2747 // Save local scope position before the addition of the implicit variables. 2748 SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); 2749 2750 // Create local scopes and destructors for range, begin and end variables. 2751 if (Stmt *Range = S->getRangeStmt()) 2752 addLocalScopeForStmt(Range); 2753 if (Stmt *BeginEnd = S->getBeginEndStmt()) 2754 addLocalScopeForStmt(BeginEnd); 2755 addAutomaticObjDtors(ScopePos, save_scope_pos.get(), S); 2756 2757 LocalScope::const_iterator ContinueScopePos = ScopePos; 2758 2759 // "for" is a control-flow statement. Thus we stop processing the current 2760 // block. 2761 CFGBlock *LoopSuccessor = NULL; 2762 if (Block) { 2763 if (badCFG) 2764 return 0; 2765 LoopSuccessor = Block; 2766 } else 2767 LoopSuccessor = Succ; 2768 2769 // Save the current value for the break targets. 2770 // All breaks should go to the code following the loop. 2771 SaveAndRestore<JumpTarget> save_break(BreakJumpTarget); 2772 BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); 2773 2774 // The block for the __begin != __end expression. 2775 CFGBlock *ConditionBlock = createBlock(false); 2776 ConditionBlock->setTerminator(S); 2777 2778 // Now add the actual condition to the condition block. 2779 if (Expr *C = S->getCond()) { 2780 Block = ConditionBlock; 2781 CFGBlock *BeginConditionBlock = addStmt(C); 2782 if (badCFG) 2783 return 0; 2784 assert(BeginConditionBlock == ConditionBlock && 2785 "condition block in for-range was unexpectedly complex"); 2786 (void)BeginConditionBlock; 2787 } 2788 2789 // The condition block is the implicit successor for the loop body as well as 2790 // any code above the loop. 2791 Succ = ConditionBlock; 2792 2793 // See if this is a known constant. 2794 TryResult KnownVal(true); 2795 2796 if (S->getCond()) 2797 KnownVal = tryEvaluateBool(S->getCond()); 2798 2799 // Now create the loop body. 2800 { 2801 assert(S->getBody()); 2802 2803 // Save the current values for Block, Succ, and continue targets. 2804 SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); 2805 SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget); 2806 2807 // Generate increment code in its own basic block. This is the target of 2808 // continue statements. 2809 Block = 0; 2810 Succ = addStmt(S->getInc()); 2811 ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos); 2812 2813 // The starting block for the loop increment is the block that should 2814 // represent the 'loop target' for looping back to the start of the loop. 2815 ContinueJumpTarget.block->setLoopTarget(S); 2816 2817 // Finish up the increment block and prepare to start the loop body. 2818 assert(Block); 2819 if (badCFG) 2820 return 0; 2821 Block = 0; 2822 2823 2824 // Add implicit scope and dtors for loop variable. 2825 addLocalScopeAndDtors(S->getLoopVarStmt()); 2826 2827 // Populate a new block to contain the loop body and loop variable. 2828 Block = addStmt(S->getBody()); 2829 if (badCFG) 2830 return 0; 2831 Block = addStmt(S->getLoopVarStmt()); 2832 if (badCFG) 2833 return 0; 2834 2835 // This new body block is a successor to our condition block. 2836 addSuccessor(ConditionBlock, KnownVal.isFalse() ? 0 : Block); 2837 } 2838 2839 // Link up the condition block with the code that follows the loop (the 2840 // false branch). 2841 addSuccessor(ConditionBlock, KnownVal.isTrue() ? 0 : LoopSuccessor); 2842 2843 // Add the initialization statements. 2844 Block = createBlock(); 2845 addStmt(S->getBeginEndStmt()); 2846 return addStmt(S->getRangeStmt()); 2847} 2848 2849CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E, 2850 AddStmtChoice asc) { 2851 if (BuildOpts.AddImplicitDtors) { 2852 // If adding implicit destructors visit the full expression for adding 2853 // destructors of temporaries. 2854 VisitForTemporaryDtors(E->getSubExpr()); 2855 2856 // Full expression has to be added as CFGStmt so it will be sequenced 2857 // before destructors of it's temporaries. 2858 asc = asc.withAlwaysAdd(true); 2859 } 2860 return Visit(E->getSubExpr(), asc); 2861} 2862 2863CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E, 2864 AddStmtChoice asc) { 2865 if (asc.alwaysAdd(*this, E)) { 2866 autoCreateBlock(); 2867 appendStmt(Block, E); 2868 2869 // We do not want to propagate the AlwaysAdd property. 2870 asc = asc.withAlwaysAdd(false); 2871 } 2872 return Visit(E->getSubExpr(), asc); 2873} 2874 2875CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C, 2876 AddStmtChoice asc) { 2877 autoCreateBlock(); 2878 appendStmt(Block, C); 2879 2880 return VisitChildren(C); 2881} 2882 2883CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E, 2884 AddStmtChoice asc) { 2885 if (asc.alwaysAdd(*this, E)) { 2886 autoCreateBlock(); 2887 appendStmt(Block, E); 2888 // We do not want to propagate the AlwaysAdd property. 2889 asc = asc.withAlwaysAdd(false); 2890 } 2891 return Visit(E->getSubExpr(), asc); 2892} 2893 2894CFGBlock *CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C, 2895 AddStmtChoice asc) { 2896 autoCreateBlock(); 2897 appendStmt(Block, C); 2898 return VisitChildren(C); 2899} 2900 2901CFGBlock *CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr *E, 2902 AddStmtChoice asc) { 2903 if (asc.alwaysAdd(*this, E)) { 2904 autoCreateBlock(); 2905 appendStmt(Block, E); 2906 } 2907 return Visit(E->getSubExpr(), AddStmtChoice()); 2908} 2909 2910CFGBlock *CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt *I) { 2911 // Lazily create the indirect-goto dispatch block if there isn't one already. 2912 CFGBlock *IBlock = cfg->getIndirectGotoBlock(); 2913 2914 if (!IBlock) { 2915 IBlock = createBlock(false); 2916 cfg->setIndirectGotoBlock(IBlock); 2917 } 2918 2919 // IndirectGoto is a control-flow statement. Thus we stop processing the 2920 // current block and create a new one. 2921 if (badCFG) 2922 return 0; 2923 2924 Block = createBlock(false); 2925 Block->setTerminator(I); 2926 addSuccessor(Block, IBlock); 2927 return addStmt(I->getTarget()); 2928} 2929 2930CFGBlock *CFGBuilder::VisitForTemporaryDtors(Stmt *E, bool BindToTemporary) { 2931tryAgain: 2932 if (!E) { 2933 badCFG = true; 2934 return NULL; 2935 } 2936 switch (E->getStmtClass()) { 2937 default: 2938 return VisitChildrenForTemporaryDtors(E); 2939 2940 case Stmt::BinaryOperatorClass: 2941 return VisitBinaryOperatorForTemporaryDtors(cast<BinaryOperator>(E)); 2942 2943 case Stmt::CXXBindTemporaryExprClass: 2944 return VisitCXXBindTemporaryExprForTemporaryDtors( 2945 cast<CXXBindTemporaryExpr>(E), BindToTemporary); 2946 2947 case Stmt::BinaryConditionalOperatorClass: 2948 case Stmt::ConditionalOperatorClass: 2949 return VisitConditionalOperatorForTemporaryDtors( 2950 cast<AbstractConditionalOperator>(E), BindToTemporary); 2951 2952 case Stmt::ImplicitCastExprClass: 2953 // For implicit cast we want BindToTemporary to be passed further. 2954 E = cast<CastExpr>(E)->getSubExpr(); 2955 goto tryAgain; 2956 2957 case Stmt::ParenExprClass: 2958 E = cast<ParenExpr>(E)->getSubExpr(); 2959 goto tryAgain; 2960 2961 case Stmt::MaterializeTemporaryExprClass: 2962 E = cast<MaterializeTemporaryExpr>(E)->GetTemporaryExpr(); 2963 goto tryAgain; 2964 } 2965} 2966 2967CFGBlock *CFGBuilder::VisitChildrenForTemporaryDtors(Stmt *E) { 2968 // When visiting children for destructors we want to visit them in reverse 2969 // order. Because there's no reverse iterator for children must to reverse 2970 // them in helper vector. 2971 typedef SmallVector<Stmt *, 4> ChildrenVect; 2972 ChildrenVect ChildrenRev; 2973 for (Stmt::child_range I = E->children(); I; ++I) { 2974 if (*I) ChildrenRev.push_back(*I); 2975 } 2976 2977 CFGBlock *B = Block; 2978 for (ChildrenVect::reverse_iterator I = ChildrenRev.rbegin(), 2979 L = ChildrenRev.rend(); I != L; ++I) { 2980 if (CFGBlock *R = VisitForTemporaryDtors(*I)) 2981 B = R; 2982 } 2983 return B; 2984} 2985 2986CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E) { 2987 if (E->isLogicalOp()) { 2988 // Destructors for temporaries in LHS expression should be called after 2989 // those for RHS expression. Even if this will unnecessarily create a block, 2990 // this block will be used at least by the full expression. 2991 autoCreateBlock(); 2992 CFGBlock *ConfluenceBlock = VisitForTemporaryDtors(E->getLHS()); 2993 if (badCFG) 2994 return NULL; 2995 2996 Succ = ConfluenceBlock; 2997 Block = NULL; 2998 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS()); 2999 3000 if (RHSBlock) { 3001 if (badCFG) 3002 return NULL; 3003 3004 // If RHS expression did produce destructors we need to connect created 3005 // blocks to CFG in same manner as for binary operator itself. 3006 CFGBlock *LHSBlock = createBlock(false); 3007 LHSBlock->setTerminator(CFGTerminator(E, true)); 3008 3009 // For binary operator LHS block is before RHS in list of predecessors 3010 // of ConfluenceBlock. 3011 std::reverse(ConfluenceBlock->pred_begin(), 3012 ConfluenceBlock->pred_end()); 3013 3014 // See if this is a known constant. 3015 TryResult KnownVal = tryEvaluateBool(E->getLHS()); 3016 if (KnownVal.isKnown() && (E->getOpcode() == BO_LOr)) 3017 KnownVal.negate(); 3018 3019 // Link LHSBlock with RHSBlock exactly the same way as for binary operator 3020 // itself. 3021 if (E->getOpcode() == BO_LOr) { 3022 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); 3023 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); 3024 } else { 3025 assert (E->getOpcode() == BO_LAnd); 3026 addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); 3027 addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); 3028 } 3029 3030 Block = LHSBlock; 3031 return LHSBlock; 3032 } 3033 3034 Block = ConfluenceBlock; 3035 return ConfluenceBlock; 3036 } 3037 3038 if (E->isAssignmentOp()) { 3039 // For assignment operator (=) LHS expression is visited 3040 // before RHS expression. For destructors visit them in reverse order. 3041 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS()); 3042 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS()); 3043 return LHSBlock ? LHSBlock : RHSBlock; 3044 } 3045 3046 // For any other binary operator RHS expression is visited before 3047 // LHS expression (order of children). For destructors visit them in reverse 3048 // order. 3049 CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS()); 3050 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS()); 3051 return RHSBlock ? RHSBlock : LHSBlock; 3052} 3053 3054CFGBlock *CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors( 3055 CXXBindTemporaryExpr *E, bool BindToTemporary) { 3056 // First add destructors for temporaries in subexpression. 3057 CFGBlock *B = VisitForTemporaryDtors(E->getSubExpr()); 3058 if (!BindToTemporary) { 3059 // If lifetime of temporary is not prolonged (by assigning to constant 3060 // reference) add destructor for it. 3061 3062 // If the destructor is marked as a no-return destructor, we need to create 3063 // a new block for the destructor which does not have as a successor 3064 // anything built thus far. Control won't flow out of this block. 3065 const CXXDestructorDecl *Dtor = E->getTemporary()->getDestructor(); 3066 if (cast<FunctionType>(Dtor->getType())->getNoReturnAttr()) 3067 Block = createNoReturnBlock(); 3068 else 3069 autoCreateBlock(); 3070 3071 appendTemporaryDtor(Block, E); 3072 B = Block; 3073 } 3074 return B; 3075} 3076 3077CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaryDtors( 3078 AbstractConditionalOperator *E, bool BindToTemporary) { 3079 // First add destructors for condition expression. Even if this will 3080 // unnecessarily create a block, this block will be used at least by the full 3081 // expression. 3082 autoCreateBlock(); 3083 CFGBlock *ConfluenceBlock = VisitForTemporaryDtors(E->getCond()); 3084 if (badCFG) 3085 return NULL; 3086 if (BinaryConditionalOperator *BCO 3087 = dyn_cast<BinaryConditionalOperator>(E)) { 3088 ConfluenceBlock = VisitForTemporaryDtors(BCO->getCommon()); 3089 if (badCFG) 3090 return NULL; 3091 } 3092 3093 // Try to add block with destructors for LHS expression. 3094 CFGBlock *LHSBlock = NULL; 3095 Succ = ConfluenceBlock; 3096 Block = NULL; 3097 LHSBlock = VisitForTemporaryDtors(E->getTrueExpr(), BindToTemporary); 3098 if (badCFG) 3099 return NULL; 3100 3101 // Try to add block with destructors for RHS expression; 3102 Succ = ConfluenceBlock; 3103 Block = NULL; 3104 CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getFalseExpr(), 3105 BindToTemporary); 3106 if (badCFG) 3107 return NULL; 3108 3109 if (!RHSBlock && !LHSBlock) { 3110 // If neither LHS nor RHS expression had temporaries to destroy don't create 3111 // more blocks. 3112 Block = ConfluenceBlock; 3113 return Block; 3114 } 3115 3116 Block = createBlock(false); 3117 Block->setTerminator(CFGTerminator(E, true)); 3118 3119 // See if this is a known constant. 3120 const TryResult &KnownVal = tryEvaluateBool(E->getCond()); 3121 3122 if (LHSBlock) { 3123 addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); 3124 } else if (KnownVal.isFalse()) { 3125 addSuccessor(Block, NULL); 3126 } else { 3127 addSuccessor(Block, ConfluenceBlock); 3128 std::reverse(ConfluenceBlock->pred_begin(), ConfluenceBlock->pred_end()); 3129 } 3130 3131 if (!RHSBlock) 3132 RHSBlock = ConfluenceBlock; 3133 addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); 3134 3135 return Block; 3136} 3137 3138} // end anonymous namespace 3139 3140/// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has 3141/// no successors or predecessors. If this is the first block created in the 3142/// CFG, it is automatically set to be the Entry and Exit of the CFG. 3143CFGBlock *CFG::createBlock() { 3144 bool first_block = begin() == end(); 3145 3146 // Create the block. 3147 CFGBlock *Mem = getAllocator().Allocate<CFGBlock>(); 3148 new (Mem) CFGBlock(NumBlockIDs++, BlkBVC, this); 3149 Blocks.push_back(Mem, BlkBVC); 3150 3151 // If this is the first block, set it as the Entry and Exit. 3152 if (first_block) 3153 Entry = Exit = &back(); 3154 3155 // Return the block. 3156 return &back(); 3157} 3158 3159/// buildCFG - Constructs a CFG from an AST. Ownership of the returned 3160/// CFG is returned to the caller. 3161CFG* CFG::buildCFG(const Decl *D, Stmt *Statement, ASTContext *C, 3162 const BuildOptions &BO) { 3163 CFGBuilder Builder(C, BO); 3164 return Builder.buildCFG(D, Statement); 3165} 3166 3167const CXXDestructorDecl * 3168CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const { 3169 switch (getKind()) { 3170 case CFGElement::Invalid: 3171 case CFGElement::Statement: 3172 case CFGElement::Initializer: 3173 llvm_unreachable("getDestructorDecl should only be used with " 3174 "ImplicitDtors"); 3175 case CFGElement::AutomaticObjectDtor: { 3176 const VarDecl *var = cast<CFGAutomaticObjDtor>(this)->getVarDecl(); 3177 QualType ty = var->getType(); 3178 ty = ty.getNonReferenceType(); 3179 while (const ArrayType *arrayType = astContext.getAsArrayType(ty)) { 3180 ty = arrayType->getElementType(); 3181 } 3182 const RecordType *recordType = ty->getAs<RecordType>(); 3183 const CXXRecordDecl *classDecl = 3184 cast<CXXRecordDecl>(recordType->getDecl()); 3185 return classDecl->getDestructor(); 3186 } 3187 case CFGElement::TemporaryDtor: { 3188 const CXXBindTemporaryExpr *bindExpr = 3189 cast<CFGTemporaryDtor>(this)->getBindTemporaryExpr(); 3190 const CXXTemporary *temp = bindExpr->getTemporary(); 3191 return temp->getDestructor(); 3192 } 3193 case CFGElement::BaseDtor: 3194 case CFGElement::MemberDtor: 3195 3196 // Not yet supported. 3197 return 0; 3198 } 3199 llvm_unreachable("getKind() returned bogus value"); 3200} 3201 3202bool CFGImplicitDtor::isNoReturn(ASTContext &astContext) const { 3203 if (const CXXDestructorDecl *decl = getDestructorDecl(astContext)) { 3204 QualType ty = decl->getType(); 3205 return cast<FunctionType>(ty)->getNoReturnAttr(); 3206 } 3207 return false; 3208} 3209 3210//===----------------------------------------------------------------------===// 3211// CFG: Queries for BlkExprs. 3212//===----------------------------------------------------------------------===// 3213 3214namespace { 3215 typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy; 3216} 3217 3218static void FindSubExprAssignments(const Stmt *S, 3219 llvm::SmallPtrSet<const Expr*,50>& Set) { 3220 if (!S) 3221 return; 3222 3223 for (Stmt::const_child_range I = S->children(); I; ++I) { 3224 const Stmt *child = *I; 3225 if (!child) 3226 continue; 3227 3228 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(child)) 3229 if (B->isAssignmentOp()) Set.insert(B); 3230 3231 FindSubExprAssignments(child, Set); 3232 } 3233} 3234 3235static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { 3236 BlkExprMapTy* M = new BlkExprMapTy(); 3237 3238 // Look for assignments that are used as subexpressions. These are the only 3239 // assignments that we want to *possibly* register as a block-level 3240 // expression. Basically, if an assignment occurs both in a subexpression and 3241 // at the block-level, it is a block-level expression. 3242 llvm::SmallPtrSet<const Expr*,50> SubExprAssignments; 3243 3244 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) 3245 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) 3246 if (const CFGStmt *S = BI->getAs<CFGStmt>()) 3247 FindSubExprAssignments(S->getStmt(), SubExprAssignments); 3248 3249 for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { 3250 3251 // Iterate over the statements again on identify the Expr* and Stmt* at the 3252 // block-level that are block-level expressions. 3253 3254 for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) { 3255 const CFGStmt *CS = BI->getAs<CFGStmt>(); 3256 if (!CS) 3257 continue; 3258 if (const Expr *Exp = dyn_cast<Expr>(CS->getStmt())) { 3259 assert((Exp->IgnoreParens() == Exp) && "No parens on block-level exps"); 3260 3261 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { 3262 // Assignment expressions that are not nested within another 3263 // expression are really "statements" whose value is never used by 3264 // another expression. 3265 if (B->isAssignmentOp() && !SubExprAssignments.count(Exp)) 3266 continue; 3267 } else if (const StmtExpr *SE = dyn_cast<StmtExpr>(Exp)) { 3268 // Special handling for statement expressions. The last statement in 3269 // the statement expression is also a block-level expr. 3270 const CompoundStmt *C = SE->getSubStmt(); 3271 if (!C->body_empty()) { 3272 const Stmt *Last = C->body_back(); 3273 if (const Expr *LastEx = dyn_cast<Expr>(Last)) 3274 Last = LastEx->IgnoreParens(); 3275 unsigned x = M->size(); 3276 (*M)[Last] = x; 3277 } 3278 } 3279 3280 unsigned x = M->size(); 3281 (*M)[Exp] = x; 3282 } 3283 } 3284 3285 // Look at terminators. The condition is a block-level expression. 3286 3287 Stmt *S = (*I)->getTerminatorCondition(); 3288 3289 if (S && M->find(S) == M->end()) { 3290 unsigned x = M->size(); 3291 (*M)[S] = x; 3292 } 3293 } 3294 3295 return M; 3296} 3297 3298CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt *S) { 3299 assert(S != NULL); 3300 if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); } 3301 3302 BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap); 3303 BlkExprMapTy::iterator I = M->find(S); 3304 return (I == M->end()) ? CFG::BlkExprNumTy() : CFG::BlkExprNumTy(I->second); 3305} 3306 3307unsigned CFG::getNumBlkExprs() { 3308 if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap)) 3309 return M->size(); 3310 3311 // We assume callers interested in the number of BlkExprs will want 3312 // the map constructed if it doesn't already exist. 3313 BlkExprMap = (void*) PopulateBlkExprMap(*this); 3314 return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); 3315} 3316 3317//===----------------------------------------------------------------------===// 3318// Filtered walking of the CFG. 3319//===----------------------------------------------------------------------===// 3320 3321bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F, 3322 const CFGBlock *From, const CFGBlock *To) { 3323 3324 if (To && F.IgnoreDefaultsWithCoveredEnums) { 3325 // If the 'To' has no label or is labeled but the label isn't a 3326 // CaseStmt then filter this edge. 3327 if (const SwitchStmt *S = 3328 dyn_cast_or_null<SwitchStmt>(From->getTerminator().getStmt())) { 3329 if (S->isAllEnumCasesCovered()) { 3330 const Stmt *L = To->getLabel(); 3331 if (!L || !isa<CaseStmt>(L)) 3332 return true; 3333 } 3334 } 3335 } 3336 3337 return false; 3338} 3339 3340//===----------------------------------------------------------------------===// 3341// Cleanup: CFG dstor. 3342//===----------------------------------------------------------------------===// 3343 3344CFG::~CFG() { 3345 delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap); 3346} 3347 3348//===----------------------------------------------------------------------===// 3349// CFG pretty printing 3350//===----------------------------------------------------------------------===// 3351 3352namespace { 3353 3354class StmtPrinterHelper : public PrinterHelper { 3355 typedef llvm::DenseMap<const Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; 3356 typedef llvm::DenseMap<const Decl*,std::pair<unsigned,unsigned> > DeclMapTy; 3357 StmtMapTy StmtMap; 3358 DeclMapTy DeclMap; 3359 signed currentBlock; 3360 unsigned currentStmt; 3361 const LangOptions &LangOpts; 3362public: 3363 3364 StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) 3365 : currentBlock(0), currentStmt(0), LangOpts(LO) 3366 { 3367 for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { 3368 unsigned j = 1; 3369 for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ; 3370 BI != BEnd; ++BI, ++j ) { 3371 if (const CFGStmt *SE = BI->getAs<CFGStmt>()) { 3372 const Stmt *stmt= SE->getStmt(); 3373 std::pair<unsigned, unsigned> P((*I)->getBlockID(), j); 3374 StmtMap[stmt] = P; 3375 3376 switch (stmt->getStmtClass()) { 3377 case Stmt::DeclStmtClass: 3378 DeclMap[cast<DeclStmt>(stmt)->getSingleDecl()] = P; 3379 break; 3380 case Stmt::IfStmtClass: { 3381 const VarDecl *var = cast<IfStmt>(stmt)->getConditionVariable(); 3382 if (var) 3383 DeclMap[var] = P; 3384 break; 3385 } 3386 case Stmt::ForStmtClass: { 3387 const VarDecl *var = cast<ForStmt>(stmt)->getConditionVariable(); 3388 if (var) 3389 DeclMap[var] = P; 3390 break; 3391 } 3392 case Stmt::WhileStmtClass: { 3393 const VarDecl *var = 3394 cast<WhileStmt>(stmt)->getConditionVariable(); 3395 if (var) 3396 DeclMap[var] = P; 3397 break; 3398 } 3399 case Stmt::SwitchStmtClass: { 3400 const VarDecl *var = 3401 cast<SwitchStmt>(stmt)->getConditionVariable(); 3402 if (var) 3403 DeclMap[var] = P; 3404 break; 3405 } 3406 case Stmt::CXXCatchStmtClass: { 3407 const VarDecl *var = 3408 cast<CXXCatchStmt>(stmt)->getExceptionDecl(); 3409 if (var) 3410 DeclMap[var] = P; 3411 break; 3412 } 3413 default: 3414 break; 3415 } 3416 } 3417 } 3418 } 3419 } 3420 3421 3422 virtual ~StmtPrinterHelper() {} 3423 3424 const LangOptions &getLangOpts() const { return LangOpts; } 3425 void setBlockID(signed i) { currentBlock = i; } 3426 void setStmtID(unsigned i) { currentStmt = i; } 3427 3428 virtual bool handledStmt(Stmt *S, raw_ostream &OS) { 3429 StmtMapTy::iterator I = StmtMap.find(S); 3430 3431 if (I == StmtMap.end()) 3432 return false; 3433 3434 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock 3435 && I->second.second == currentStmt) { 3436 return false; 3437 } 3438 3439 OS << "[B" << I->second.first << "." << I->second.second << "]"; 3440 return true; 3441 } 3442 3443 bool handleDecl(const Decl *D, raw_ostream &OS) { 3444 DeclMapTy::iterator I = DeclMap.find(D); 3445 3446 if (I == DeclMap.end()) 3447 return false; 3448 3449 if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock 3450 && I->second.second == currentStmt) { 3451 return false; 3452 } 3453 3454 OS << "[B" << I->second.first << "." << I->second.second << "]"; 3455 return true; 3456 } 3457}; 3458} // end anonymous namespace 3459 3460 3461namespace { 3462class CFGBlockTerminatorPrint 3463 : public StmtVisitor<CFGBlockTerminatorPrint,void> { 3464 3465 raw_ostream &OS; 3466 StmtPrinterHelper* Helper; 3467 PrintingPolicy Policy; 3468public: 3469 CFGBlockTerminatorPrint(raw_ostream &os, StmtPrinterHelper* helper, 3470 const PrintingPolicy &Policy) 3471 : OS(os), Helper(helper), Policy(Policy) {} 3472 3473 void VisitIfStmt(IfStmt *I) { 3474 OS << "if "; 3475 I->getCond()->printPretty(OS,Helper,Policy); 3476 } 3477 3478 // Default case. 3479 void VisitStmt(Stmt *Terminator) { 3480 Terminator->printPretty(OS, Helper, Policy); 3481 } 3482 3483 void VisitForStmt(ForStmt *F) { 3484 OS << "for (" ; 3485 if (F->getInit()) 3486 OS << "..."; 3487 OS << "; "; 3488 if (Stmt *C = F->getCond()) 3489 C->printPretty(OS, Helper, Policy); 3490 OS << "; "; 3491 if (F->getInc()) 3492 OS << "..."; 3493 OS << ")"; 3494 } 3495 3496 void VisitWhileStmt(WhileStmt *W) { 3497 OS << "while " ; 3498 if (Stmt *C = W->getCond()) 3499 C->printPretty(OS, Helper, Policy); 3500 } 3501 3502 void VisitDoStmt(DoStmt *D) { 3503 OS << "do ... while "; 3504 if (Stmt *C = D->getCond()) 3505 C->printPretty(OS, Helper, Policy); 3506 } 3507 3508 void VisitSwitchStmt(SwitchStmt *Terminator) { 3509 OS << "switch "; 3510 Terminator->getCond()->printPretty(OS, Helper, Policy); 3511 } 3512 3513 void VisitCXXTryStmt(CXXTryStmt *CS) { 3514 OS << "try ..."; 3515 } 3516 3517 void VisitAbstractConditionalOperator(AbstractConditionalOperator* C) { 3518 C->getCond()->printPretty(OS, Helper, Policy); 3519 OS << " ? ... : ..."; 3520 } 3521 3522 void VisitChooseExpr(ChooseExpr *C) { 3523 OS << "__builtin_choose_expr( "; 3524 C->getCond()->printPretty(OS, Helper, Policy); 3525 OS << " )"; 3526 } 3527 3528 void VisitIndirectGotoStmt(IndirectGotoStmt *I) { 3529 OS << "goto *"; 3530 I->getTarget()->printPretty(OS, Helper, Policy); 3531 } 3532 3533 void VisitBinaryOperator(BinaryOperator* B) { 3534 if (!B->isLogicalOp()) { 3535 VisitExpr(B); 3536 return; 3537 } 3538 3539 B->getLHS()->printPretty(OS, Helper, Policy); 3540 3541 switch (B->getOpcode()) { 3542 case BO_LOr: 3543 OS << " || ..."; 3544 return; 3545 case BO_LAnd: 3546 OS << " && ..."; 3547 return; 3548 default: 3549 llvm_unreachable("Invalid logical operator."); 3550 } 3551 } 3552 3553 void VisitExpr(Expr *E) { 3554 E->printPretty(OS, Helper, Policy); 3555 } 3556}; 3557} // end anonymous namespace 3558 3559static void print_elem(raw_ostream &OS, StmtPrinterHelper* Helper, 3560 const CFGElement &E) { 3561 if (const CFGStmt *CS = E.getAs<CFGStmt>()) { 3562 const Stmt *S = CS->getStmt(); 3563 3564 if (Helper) { 3565 3566 // special printing for statement-expressions. 3567 if (const StmtExpr *SE = dyn_cast<StmtExpr>(S)) { 3568 const CompoundStmt *Sub = SE->getSubStmt(); 3569 3570 if (Sub->children()) { 3571 OS << "({ ... ; "; 3572 Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); 3573 OS << " })\n"; 3574 return; 3575 } 3576 } 3577 // special printing for comma expressions. 3578 if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { 3579 if (B->getOpcode() == BO_Comma) { 3580 OS << "... , "; 3581 Helper->handledStmt(B->getRHS(),OS); 3582 OS << '\n'; 3583 return; 3584 } 3585 } 3586 } 3587 S->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 3588 3589 if (isa<CXXOperatorCallExpr>(S)) { 3590 OS << " (OperatorCall)"; 3591 } 3592 else if (isa<CXXBindTemporaryExpr>(S)) { 3593 OS << " (BindTemporary)"; 3594 } 3595 else if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(S)) { 3596 OS << " (CXXConstructExpr, " << CCE->getType().getAsString() << ")"; 3597 } 3598 else if (const CastExpr *CE = dyn_cast<CastExpr>(S)) { 3599 OS << " (" << CE->getStmtClassName() << ", " 3600 << CE->getCastKindName() 3601 << ", " << CE->getType().getAsString() 3602 << ")"; 3603 } 3604 3605 // Expressions need a newline. 3606 if (isa<Expr>(S)) 3607 OS << '\n'; 3608 3609 } else if (const CFGInitializer *IE = E.getAs<CFGInitializer>()) { 3610 const CXXCtorInitializer *I = IE->getInitializer(); 3611 if (I->isBaseInitializer()) 3612 OS << I->getBaseClass()->getAsCXXRecordDecl()->getName(); 3613 else OS << I->getAnyMember()->getName(); 3614 3615 OS << "("; 3616 if (Expr *IE = I->getInit()) 3617 IE->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); 3618 OS << ")"; 3619 3620 if (I->isBaseInitializer()) 3621 OS << " (Base initializer)\n"; 3622 else OS << " (Member initializer)\n"; 3623 3624 } else if (const CFGAutomaticObjDtor *DE = E.getAs<CFGAutomaticObjDtor>()){ 3625 const VarDecl *VD = DE->getVarDecl(); 3626 Helper->handleDecl(VD, OS); 3627 3628 const Type* T = VD->getType().getTypePtr(); 3629 if (const ReferenceType* RT = T->getAs<ReferenceType>()) 3630 T = RT->getPointeeType().getTypePtr(); 3631 else if (const Type *ET = T->getArrayElementTypeNoTypeQual()) 3632 T = ET; 3633 3634 OS << ".~" << T->getAsCXXRecordDecl()->getName().str() << "()"; 3635 OS << " (Implicit destructor)\n"; 3636 3637 } else if (const CFGBaseDtor *BE = E.getAs<CFGBaseDtor>()) { 3638 const CXXBaseSpecifier *BS = BE->getBaseSpecifier(); 3639 OS << "~" << BS->getType()->getAsCXXRecordDecl()->getName() << "()"; 3640 OS << " (Base object destructor)\n"; 3641 3642 } else if (const CFGMemberDtor *ME = E.getAs<CFGMemberDtor>()) { 3643 const FieldDecl *FD = ME->getFieldDecl(); 3644 3645 const Type *T = FD->getType().getTypePtr(); 3646 if (const Type *ET = T->getArrayElementTypeNoTypeQual()) 3647 T = ET; 3648 3649 OS << "this->" << FD->getName(); 3650 OS << ".~" << T->getAsCXXRecordDecl()->getName() << "()"; 3651 OS << " (Member object destructor)\n"; 3652 3653 } else if (const CFGTemporaryDtor *TE = E.getAs<CFGTemporaryDtor>()) { 3654 const CXXBindTemporaryExpr *BT = TE->getBindTemporaryExpr(); 3655 OS << "~" << BT->getType()->getAsCXXRecordDecl()->getName() << "()"; 3656 OS << " (Temporary object destructor)\n"; 3657 } 3658} 3659 3660static void print_block(raw_ostream &OS, const CFG* cfg, 3661 const CFGBlock &B, 3662 StmtPrinterHelper* Helper, bool print_edges, 3663 bool ShowColors) { 3664 3665 if (Helper) 3666 Helper->setBlockID(B.getBlockID()); 3667 3668 // Print the header. 3669 if (ShowColors) 3670 OS.changeColor(raw_ostream::YELLOW, true); 3671 3672 OS << "\n [B" << B.getBlockID(); 3673 3674 if (&B == &cfg->getEntry()) 3675 OS << " (ENTRY)]\n"; 3676 else if (&B == &cfg->getExit()) 3677 OS << " (EXIT)]\n"; 3678 else if (&B == cfg->getIndirectGotoBlock()) 3679 OS << " (INDIRECT GOTO DISPATCH)]\n"; 3680 else 3681 OS << "]\n"; 3682 3683 if (ShowColors) 3684 OS.resetColor(); 3685 3686 // Print the label of this block. 3687 if (Stmt *Label = const_cast<Stmt*>(B.getLabel())) { 3688 3689 if (print_edges) 3690 OS << " "; 3691 3692 if (LabelStmt *L = dyn_cast<LabelStmt>(Label)) 3693 OS << L->getName(); 3694 else if (CaseStmt *C = dyn_cast<CaseStmt>(Label)) { 3695 OS << "case "; 3696 C->getLHS()->printPretty(OS, Helper, 3697 PrintingPolicy(Helper->getLangOpts())); 3698 if (C->getRHS()) { 3699 OS << " ... "; 3700 C->getRHS()->printPretty(OS, Helper, 3701 PrintingPolicy(Helper->getLangOpts())); 3702 } 3703 } else if (isa<DefaultStmt>(Label)) 3704 OS << "default"; 3705 else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Label)) { 3706 OS << "catch ("; 3707 if (CS->getExceptionDecl()) 3708 CS->getExceptionDecl()->print(OS, PrintingPolicy(Helper->getLangOpts()), 3709 0); 3710 else 3711 OS << "..."; 3712 OS << ")"; 3713 3714 } else 3715 llvm_unreachable("Invalid label statement in CFGBlock."); 3716 3717 OS << ":\n"; 3718 } 3719 3720 // Iterate through the statements in the block and print them. 3721 unsigned j = 1; 3722 3723 for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; 3724 I != E ; ++I, ++j ) { 3725 3726 // Print the statement # in the basic block and the statement itself. 3727 if (print_edges) 3728 OS << " "; 3729 3730 OS << llvm::format("%3d", j) << ": "; 3731 3732 if (Helper) 3733 Helper->setStmtID(j); 3734 3735 print_elem(OS, Helper, *I); 3736 } 3737 3738 // Print the terminator of this block. 3739 if (B.getTerminator()) { 3740 if (ShowColors) 3741 OS.changeColor(raw_ostream::GREEN); 3742 3743 OS << " T: "; 3744 3745 if (Helper) Helper->setBlockID(-1); 3746 3747 CFGBlockTerminatorPrint TPrinter(OS, Helper, 3748 PrintingPolicy(Helper->getLangOpts())); 3749 TPrinter.Visit(const_cast<Stmt*>(B.getTerminator().getStmt())); 3750 OS << '\n'; 3751 3752 if (ShowColors) 3753 OS.resetColor(); 3754 } 3755 3756 if (print_edges) { 3757 // Print the predecessors of this block. 3758 if (!B.pred_empty()) { 3759 const raw_ostream::Colors Color = raw_ostream::BLUE; 3760 if (ShowColors) 3761 OS.changeColor(Color); 3762 OS << " Preds " ; 3763 if (ShowColors) 3764 OS.resetColor(); 3765 OS << '(' << B.pred_size() << "):"; 3766 unsigned i = 0; 3767 3768 if (ShowColors) 3769 OS.changeColor(Color); 3770 3771 for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); 3772 I != E; ++I, ++i) { 3773 3774 if (i == 8 || (i-8) == 0) 3775 OS << "\n "; 3776 3777 OS << " B" << (*I)->getBlockID(); 3778 } 3779 3780 if (ShowColors) 3781 OS.resetColor(); 3782 3783 OS << '\n'; 3784 } 3785 3786 // Print the successors of this block. 3787 if (!B.succ_empty()) { 3788 const raw_ostream::Colors Color = raw_ostream::MAGENTA; 3789 if (ShowColors) 3790 OS.changeColor(Color); 3791 OS << " Succs "; 3792 if (ShowColors) 3793 OS.resetColor(); 3794 OS << '(' << B.succ_size() << "):"; 3795 unsigned i = 0; 3796 3797 if (ShowColors) 3798 OS.changeColor(Color); 3799 3800 for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); 3801 I != E; ++I, ++i) { 3802 3803 if (i == 8 || (i-8) % 10 == 0) 3804 OS << "\n "; 3805 3806 if (*I) 3807 OS << " B" << (*I)->getBlockID(); 3808 else 3809 OS << " NULL"; 3810 } 3811 3812 if (ShowColors) 3813 OS.resetColor(); 3814 OS << '\n'; 3815 } 3816 } 3817} 3818 3819 3820/// dump - A simple pretty printer of a CFG that outputs to stderr. 3821void CFG::dump(const LangOptions &LO, bool ShowColors) const { 3822 print(llvm::errs(), LO, ShowColors); 3823} 3824 3825/// print - A simple pretty printer of a CFG that outputs to an ostream. 3826void CFG::print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const { 3827 StmtPrinterHelper Helper(this, LO); 3828 3829 // Print the entry block. 3830 print_block(OS, this, getEntry(), &Helper, true, ShowColors); 3831 3832 // Iterate through the CFGBlocks and print them one by one. 3833 for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { 3834 // Skip the entry block, because we already printed it. 3835 if (&(**I) == &getEntry() || &(**I) == &getExit()) 3836 continue; 3837 3838 print_block(OS, this, **I, &Helper, true, ShowColors); 3839 } 3840 3841 // Print the exit block. 3842 print_block(OS, this, getExit(), &Helper, true, ShowColors); 3843 OS << '\n'; 3844 OS.flush(); 3845} 3846 3847/// dump - A simply pretty printer of a CFGBlock that outputs to stderr. 3848void CFGBlock::dump(const CFG* cfg, const LangOptions &LO, 3849 bool ShowColors) const { 3850 print(llvm::errs(), cfg, LO, ShowColors); 3851} 3852 3853/// print - A simple pretty printer of a CFGBlock that outputs to an ostream. 3854/// Generally this will only be called from CFG::print. 3855void CFGBlock::print(raw_ostream &OS, const CFG* cfg, 3856 const LangOptions &LO, bool ShowColors) const { 3857 StmtPrinterHelper Helper(cfg, LO); 3858 print_block(OS, cfg, *this, &Helper, true, ShowColors); 3859 OS << '\n'; 3860} 3861 3862/// printTerminator - A simple pretty printer of the terminator of a CFGBlock. 3863void CFGBlock::printTerminator(raw_ostream &OS, 3864 const LangOptions &LO) const { 3865 CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO)); 3866 TPrinter.Visit(const_cast<Stmt*>(getTerminator().getStmt())); 3867} 3868 3869Stmt *CFGBlock::getTerminatorCondition() { 3870 Stmt *Terminator = this->Terminator; 3871 if (!Terminator) 3872 return NULL; 3873 3874 Expr *E = NULL; 3875 3876 switch (Terminator->getStmtClass()) { 3877 default: 3878 break; 3879 3880 case Stmt::ForStmtClass: 3881 E = cast<ForStmt>(Terminator)->getCond(); 3882 break; 3883 3884 case Stmt::WhileStmtClass: 3885 E = cast<WhileStmt>(Terminator)->getCond(); 3886 break; 3887 3888 case Stmt::DoStmtClass: 3889 E = cast<DoStmt>(Terminator)->getCond(); 3890 break; 3891 3892 case Stmt::IfStmtClass: 3893 E = cast<IfStmt>(Terminator)->getCond(); 3894 break; 3895 3896 case Stmt::ChooseExprClass: 3897 E = cast<ChooseExpr>(Terminator)->getCond(); 3898 break; 3899 3900 case Stmt::IndirectGotoStmtClass: 3901 E = cast<IndirectGotoStmt>(Terminator)->getTarget(); 3902 break; 3903 3904 case Stmt::SwitchStmtClass: 3905 E = cast<SwitchStmt>(Terminator)->getCond(); 3906 break; 3907 3908 case Stmt::BinaryConditionalOperatorClass: 3909 E = cast<BinaryConditionalOperator>(Terminator)->getCond(); 3910 break; 3911 3912 case Stmt::ConditionalOperatorClass: 3913 E = cast<ConditionalOperator>(Terminator)->getCond(); 3914 break; 3915 3916 case Stmt::BinaryOperatorClass: // '&&' and '||' 3917 E = cast<BinaryOperator>(Terminator)->getLHS(); 3918 break; 3919 3920 case Stmt::ObjCForCollectionStmtClass: 3921 return Terminator; 3922 } 3923 3924 return E ? E->IgnoreParens() : NULL; 3925} 3926 3927//===----------------------------------------------------------------------===// 3928// CFG Graphviz Visualization 3929//===----------------------------------------------------------------------===// 3930 3931 3932#ifndef NDEBUG 3933static StmtPrinterHelper* GraphHelper; 3934#endif 3935 3936void CFG::viewCFG(const LangOptions &LO) const { 3937#ifndef NDEBUG 3938 StmtPrinterHelper H(this, LO); 3939 GraphHelper = &H; 3940 llvm::ViewGraph(this,"CFG"); 3941 GraphHelper = NULL; 3942#endif 3943} 3944 3945namespace llvm { 3946template<> 3947struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { 3948 3949 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 3950 3951 static std::string getNodeLabel(const CFGBlock *Node, const CFG* Graph) { 3952 3953#ifndef NDEBUG 3954 std::string OutSStr; 3955 llvm::raw_string_ostream Out(OutSStr); 3956 print_block(Out,Graph, *Node, GraphHelper, false, false); 3957 std::string& OutStr = Out.str(); 3958 3959 if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); 3960 3961 // Process string output to make it nicer... 3962 for (unsigned i = 0; i != OutStr.length(); ++i) 3963 if (OutStr[i] == '\n') { // Left justify 3964 OutStr[i] = '\\'; 3965 OutStr.insert(OutStr.begin()+i+1, 'l'); 3966 } 3967 3968 return OutStr; 3969#else 3970 return ""; 3971#endif 3972 } 3973}; 3974} // end namespace llvm 3975