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