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