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