diff options
Diffstat (limited to 'contrib/llvm/tools/clang/lib/Analysis')
13 files changed, 7341 insertions, 0 deletions
diff --git a/contrib/llvm/tools/clang/lib/Analysis/AnalysisContext.cpp b/contrib/llvm/tools/clang/lib/Analysis/AnalysisContext.cpp new file mode 100644 index 0000000..5233d3b --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/AnalysisContext.cpp @@ -0,0 +1,377 @@ +//== AnalysisContext.cpp - Analysis context for Path Sens analysis -*- C++ -*-// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines AnalysisContext, a class that manages the analysis context +// data for path sensitive analysis. +// +//===----------------------------------------------------------------------===// + +#include "clang/AST/Decl.h" +#include "clang/AST/DeclObjC.h" +#include "clang/AST/DeclTemplate.h" +#include "clang/AST/ParentMap.h" +#include "clang/AST/StmtVisitor.h" +#include "clang/Analysis/Analyses/LiveVariables.h" +#include "clang/Analysis/Analyses/PseudoConstantAnalysis.h" +#include "clang/Analysis/AnalysisContext.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/Support/BumpVector.h" +#include "llvm/ADT/SmallSet.h" +#include "llvm/Support/ErrorHandling.h" + +using namespace clang; + +void AnalysisContextManager::clear() { + for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) + delete I->second; + Contexts.clear(); +} + +Stmt *AnalysisContext::getBody() { + if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) + return FD->getBody(); + else if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) + return MD->getBody(); + else if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) + return BD->getBody(); + else if (const FunctionTemplateDecl *FunTmpl + = dyn_cast_or_null<FunctionTemplateDecl>(D)) + return FunTmpl->getTemplatedDecl()->getBody(); + + llvm_unreachable("unknown code decl"); +} + +const ImplicitParamDecl *AnalysisContext::getSelfDecl() const { + if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) + return MD->getSelfDecl(); + + return NULL; +} + +CFG *AnalysisContext::getCFG() { + if (UseUnoptimizedCFG) + return getUnoptimizedCFG(); + + if (!builtCFG) { + CFG::BuildOptions B; + B.AddEHEdges = AddEHEdges; + B.AddImplicitDtors = AddImplicitDtors; + B.AddInitializers = AddInitializers; + cfg = CFG::buildCFG(D, getBody(), &D->getASTContext(), B); + // Even when the cfg is not successfully built, we don't + // want to try building it again. + builtCFG = true; + } + return cfg; +} + +CFG *AnalysisContext::getUnoptimizedCFG() { + if (!builtCompleteCFG) { + CFG::BuildOptions B; + B.PruneTriviallyFalseEdges = false; + B.AddEHEdges = AddEHEdges; + B.AddImplicitDtors = AddImplicitDtors; + B.AddInitializers = AddInitializers; + completeCFG = CFG::buildCFG(D, getBody(), &D->getASTContext(), B); + // Even when the cfg is not successfully built, we don't + // want to try building it again. + builtCompleteCFG = true; + } + return completeCFG; +} + +void AnalysisContext::dumpCFG() { + getCFG()->dump(getASTContext().getLangOptions()); +} + +ParentMap &AnalysisContext::getParentMap() { + if (!PM) + PM = new ParentMap(getBody()); + return *PM; +} + +PseudoConstantAnalysis *AnalysisContext::getPseudoConstantAnalysis() { + if (!PCA) + PCA = new PseudoConstantAnalysis(getBody()); + return PCA; +} + +LiveVariables *AnalysisContext::getLiveVariables() { + if (!liveness) { + CFG *c = getCFG(); + if (!c) + return 0; + + liveness = new LiveVariables(*this); + liveness->runOnCFG(*c); + liveness->runOnAllBlocks(*c, 0, true); + } + + return liveness; +} + +LiveVariables *AnalysisContext::getRelaxedLiveVariables() { + if (!relaxedLiveness) { + CFG *c = getCFG(); + if (!c) + return 0; + + relaxedLiveness = new LiveVariables(*this, false); + relaxedLiveness->runOnCFG(*c); + relaxedLiveness->runOnAllBlocks(*c, 0, true); + } + + return relaxedLiveness; +} + +AnalysisContext *AnalysisContextManager::getContext(const Decl *D, + idx::TranslationUnit *TU) { + AnalysisContext *&AC = Contexts[D]; + if (!AC) + AC = new AnalysisContext(D, TU, UseUnoptimizedCFG, false, + AddImplicitDtors, AddInitializers); + + return AC; +} + +//===----------------------------------------------------------------------===// +// FoldingSet profiling. +//===----------------------------------------------------------------------===// + +void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID, + ContextKind ck, + AnalysisContext *ctx, + const LocationContext *parent, + const void* data) { + ID.AddInteger(ck); + ID.AddPointer(ctx); + ID.AddPointer(parent); + ID.AddPointer(data); +} + +void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) { + Profile(ID, getAnalysisContext(), getParent(), CallSite, Block, Index); +} + +void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) { + Profile(ID, getAnalysisContext(), getParent(), Enter); +} + +void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) { + Profile(ID, getAnalysisContext(), getParent(), BD); +} + +//===----------------------------------------------------------------------===// +// LocationContext creation. +//===----------------------------------------------------------------------===// + +template <typename LOC, typename DATA> +const LOC* +LocationContextManager::getLocationContext(AnalysisContext *ctx, + const LocationContext *parent, + const DATA *d) { + llvm::FoldingSetNodeID ID; + LOC::Profile(ID, ctx, parent, d); + void *InsertPos; + + LOC *L = cast_or_null<LOC>(Contexts.FindNodeOrInsertPos(ID, InsertPos)); + + if (!L) { + L = new LOC(ctx, parent, d); + Contexts.InsertNode(L, InsertPos); + } + return L; +} + +const StackFrameContext* +LocationContextManager::getStackFrame(AnalysisContext *ctx, + const LocationContext *parent, + const Stmt *s, + const CFGBlock *blk, unsigned idx) { + llvm::FoldingSetNodeID ID; + StackFrameContext::Profile(ID, ctx, parent, s, blk, idx); + void *InsertPos; + StackFrameContext *L = + cast_or_null<StackFrameContext>(Contexts.FindNodeOrInsertPos(ID, InsertPos)); + if (!L) { + L = new StackFrameContext(ctx, parent, s, blk, idx); + Contexts.InsertNode(L, InsertPos); + } + return L; +} + +const ScopeContext * +LocationContextManager::getScope(AnalysisContext *ctx, + const LocationContext *parent, + const Stmt *s) { + return getLocationContext<ScopeContext, Stmt>(ctx, parent, s); +} + +//===----------------------------------------------------------------------===// +// LocationContext methods. +//===----------------------------------------------------------------------===// + +const StackFrameContext *LocationContext::getCurrentStackFrame() const { + const LocationContext *LC = this; + while (LC) { + if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) + return SFC; + LC = LC->getParent(); + } + return NULL; +} + +const StackFrameContext * +LocationContext::getStackFrameForDeclContext(const DeclContext *DC) const { + const LocationContext *LC = this; + while (LC) { + if (const StackFrameContext *SFC = dyn_cast<StackFrameContext>(LC)) { + if (cast<DeclContext>(SFC->getDecl()) == DC) + return SFC; + } + LC = LC->getParent(); + } + return NULL; +} + +bool LocationContext::isParentOf(const LocationContext *LC) const { + do { + const LocationContext *Parent = LC->getParent(); + if (Parent == this) + return true; + else + LC = Parent; + } while (LC); + + return false; +} + +//===----------------------------------------------------------------------===// +// Lazily generated map to query the external variables referenced by a Block. +//===----------------------------------------------------------------------===// + +namespace { +class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{ + BumpVector<const VarDecl*> &BEVals; + BumpVectorContext &BC; + llvm::DenseMap<const VarDecl*, unsigned> Visited; + llvm::SmallSet<const DeclContext*, 4> IgnoredContexts; +public: + FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals, + BumpVectorContext &bc) + : BEVals(bevals), BC(bc) {} + + bool IsTrackedDecl(const VarDecl *VD) { + const DeclContext *DC = VD->getDeclContext(); + return IgnoredContexts.count(DC) == 0; + } + + void VisitStmt(Stmt *S) { + for (Stmt::child_range I = S->children(); I; ++I) + if (Stmt *child = *I) + Visit(child); + } + + void VisitDeclRefExpr(const DeclRefExpr *DR) { + // Non-local variables are also directly modified. + if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) + if (!VD->hasLocalStorage()) { + unsigned &flag = Visited[VD]; + if (!flag) { + flag = 1; + BEVals.push_back(VD, BC); + } + } + } + + void VisitBlockDeclRefExpr(BlockDeclRefExpr *DR) { + if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { + unsigned &flag = Visited[VD]; + if (!flag) { + flag = 1; + if (IsTrackedDecl(VD)) + BEVals.push_back(VD, BC); + } + } + } + + void VisitBlockExpr(BlockExpr *BR) { + // Blocks containing blocks can transitively capture more variables. + IgnoredContexts.insert(BR->getBlockDecl()); + Visit(BR->getBlockDecl()->getBody()); + } +}; +} // end anonymous namespace + +typedef BumpVector<const VarDecl*> DeclVec; + +static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD, + void *&Vec, + llvm::BumpPtrAllocator &A) { + if (Vec) + return (DeclVec*) Vec; + + BumpVectorContext BC(A); + DeclVec *BV = (DeclVec*) A.Allocate<DeclVec>(); + new (BV) DeclVec(BC, 10); + + // Find the referenced variables. + FindBlockDeclRefExprsVals F(*BV, BC); + F.Visit(BD->getBody()); + + Vec = BV; + return BV; +} + +std::pair<AnalysisContext::referenced_decls_iterator, + AnalysisContext::referenced_decls_iterator> +AnalysisContext::getReferencedBlockVars(const BlockDecl *BD) { + if (!ReferencedBlockVars) + ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>(); + + DeclVec *V = LazyInitializeReferencedDecls(BD, (*ReferencedBlockVars)[BD], A); + return std::make_pair(V->begin(), V->end()); +} + +//===----------------------------------------------------------------------===// +// Cleanup. +//===----------------------------------------------------------------------===// + +AnalysisContext::~AnalysisContext() { + delete cfg; + delete completeCFG; + delete liveness; + delete relaxedLiveness; + delete PM; + delete PCA; + delete ReferencedBlockVars; +} + +AnalysisContextManager::~AnalysisContextManager() { + for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) + delete I->second; +} + +LocationContext::~LocationContext() {} + +LocationContextManager::~LocationContextManager() { + clear(); +} + +void LocationContextManager::clear() { + for (llvm::FoldingSet<LocationContext>::iterator I = Contexts.begin(), + E = Contexts.end(); I != E; ) { + LocationContext *LC = &*I; + ++I; + delete LC; + } + + Contexts.clear(); +} + diff --git a/contrib/llvm/tools/clang/lib/Analysis/CFG.cpp b/contrib/llvm/tools/clang/lib/Analysis/CFG.cpp new file mode 100644 index 0000000..a0ec5fe --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/CFG.cpp @@ -0,0 +1,3407 @@ +//===--- CFG.cpp - Classes for representing and building CFGs----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the CFG and CFGBuilder classes for representing and +// building Control-Flow Graphs (CFGs) from ASTs. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Support/SaveAndRestore.h" +#include "clang/Analysis/CFG.h" +#include "clang/AST/DeclCXX.h" +#include "clang/AST/StmtVisitor.h" +#include "clang/AST/PrettyPrinter.h" +#include "llvm/Support/GraphWriter.h" +#include "llvm/Support/Allocator.h" +#include "llvm/Support/Format.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/OwningPtr.h" + +using namespace clang; + +namespace { + +static SourceLocation GetEndLoc(Decl* D) { + if (VarDecl* VD = dyn_cast<VarDecl>(D)) + if (Expr* Ex = VD->getInit()) + return Ex->getSourceRange().getEnd(); + return D->getLocation(); +} + +/// The CFG builder uses a recursive algorithm to build the CFG. When +/// we process an expression, sometimes we know that we must add the +/// subexpressions as block-level expressions. For example: +/// +/// exp1 || exp2 +/// +/// When processing the '||' expression, we know that exp1 and exp2 +/// need to be added as block-level expressions, even though they +/// might not normally need to be. AddStmtChoice records this +/// contextual information. If AddStmtChoice is 'NotAlwaysAdd', then +/// the builder has an option not to add a subexpression as a +/// block-level expression. +/// +class AddStmtChoice { +public: + enum Kind { NotAlwaysAdd = 0, AlwaysAdd = 1 }; + + AddStmtChoice(Kind a_kind = NotAlwaysAdd) : kind(a_kind) {} + + bool alwaysAdd() const { return kind & AlwaysAdd; } + + /// Return a copy of this object, except with the 'always-add' bit + /// set as specified. + AddStmtChoice withAlwaysAdd(bool alwaysAdd) const { + return AddStmtChoice(alwaysAdd ? Kind(kind | AlwaysAdd) : + Kind(kind & ~AlwaysAdd)); + } + +private: + Kind kind; +}; + +/// LocalScope - Node in tree of local scopes created for C++ implicit +/// destructor calls generation. It contains list of automatic variables +/// declared in the scope and link to position in previous scope this scope +/// began in. +/// +/// The process of creating local scopes is as follows: +/// - Init CFGBuilder::ScopePos with invalid position (equivalent for null), +/// - Before processing statements in scope (e.g. CompoundStmt) create +/// LocalScope object using CFGBuilder::ScopePos as link to previous scope +/// and set CFGBuilder::ScopePos to the end of new scope, +/// - On every occurrence of VarDecl increase CFGBuilder::ScopePos if it points +/// at this VarDecl, +/// - For every normal (without jump) end of scope add to CFGBlock destructors +/// for objects in the current scope, +/// - For every jump add to CFGBlock destructors for objects +/// between CFGBuilder::ScopePos and local scope position saved for jump +/// target. Thanks to C++ restrictions on goto jumps we can be sure that +/// jump target position will be on the path to root from CFGBuilder::ScopePos +/// (adding any variable that doesn't need constructor to be called to +/// LocalScope can break this assumption), +/// +class LocalScope { +public: + typedef BumpVector<VarDecl*> AutomaticVarsTy; + + /// const_iterator - Iterates local scope backwards and jumps to previous + /// scope on reaching the beginning of currently iterated scope. + class const_iterator { + const LocalScope* Scope; + + /// VarIter is guaranteed to be greater then 0 for every valid iterator. + /// Invalid iterator (with null Scope) has VarIter equal to 0. + unsigned VarIter; + + public: + /// Create invalid iterator. Dereferencing invalid iterator is not allowed. + /// Incrementing invalid iterator is allowed and will result in invalid + /// iterator. + const_iterator() + : Scope(NULL), VarIter(0) {} + + /// Create valid iterator. In case when S.Prev is an invalid iterator and + /// I is equal to 0, this will create invalid iterator. + const_iterator(const LocalScope& S, unsigned I) + : Scope(&S), VarIter(I) { + // Iterator to "end" of scope is not allowed. Handle it by going up + // in scopes tree possibly up to invalid iterator in the root. + if (VarIter == 0 && Scope) + *this = Scope->Prev; + } + + VarDecl* const* operator->() const { + assert (Scope && "Dereferencing invalid iterator is not allowed"); + assert (VarIter != 0 && "Iterator has invalid value of VarIter member"); + return &Scope->Vars[VarIter - 1]; + } + VarDecl* operator*() const { + return *this->operator->(); + } + + const_iterator& operator++() { + if (!Scope) + return *this; + + assert (VarIter != 0 && "Iterator has invalid value of VarIter member"); + --VarIter; + if (VarIter == 0) + *this = Scope->Prev; + return *this; + } + const_iterator operator++(int) { + const_iterator P = *this; + ++*this; + return P; + } + + bool operator==(const const_iterator& rhs) const { + return Scope == rhs.Scope && VarIter == rhs.VarIter; + } + bool operator!=(const const_iterator& rhs) const { + return !(*this == rhs); + } + + operator bool() const { + return *this != const_iterator(); + } + + int distance(const_iterator L); + }; + + friend class const_iterator; + +private: + BumpVectorContext ctx; + + /// Automatic variables in order of declaration. + AutomaticVarsTy Vars; + /// Iterator to variable in previous scope that was declared just before + /// begin of this scope. + const_iterator Prev; + +public: + /// Constructs empty scope linked to previous scope in specified place. + LocalScope(BumpVectorContext &ctx, const_iterator P) + : ctx(ctx), Vars(ctx, 4), Prev(P) {} + + /// Begin of scope in direction of CFG building (backwards). + const_iterator begin() const { return const_iterator(*this, Vars.size()); } + + void addVar(VarDecl* VD) { + Vars.push_back(VD, ctx); + } +}; + +/// distance - Calculates distance from this to L. L must be reachable from this +/// (with use of ++ operator). Cost of calculating the distance is linear w.r.t. +/// number of scopes between this and L. +int LocalScope::const_iterator::distance(LocalScope::const_iterator L) { + int D = 0; + const_iterator F = *this; + while (F.Scope != L.Scope) { + assert (F != const_iterator() + && "L iterator is not reachable from F iterator."); + D += F.VarIter; + F = F.Scope->Prev; + } + D += F.VarIter - L.VarIter; + return D; +} + +/// BlockScopePosPair - Structure for specifying position in CFG during its +/// build process. It consists of CFGBlock that specifies position in CFG graph +/// and LocalScope::const_iterator that specifies position in LocalScope graph. +struct BlockScopePosPair { + BlockScopePosPair() : block(0) {} + BlockScopePosPair(CFGBlock* b, LocalScope::const_iterator scopePos) + : block(b), scopePosition(scopePos) {} + + CFGBlock *block; + LocalScope::const_iterator scopePosition; +}; + +/// CFGBuilder - This class implements CFG construction from an AST. +/// The builder is stateful: an instance of the builder should be used to only +/// construct a single CFG. +/// +/// Example usage: +/// +/// CFGBuilder builder; +/// CFG* cfg = builder.BuildAST(stmt1); +/// +/// CFG construction is done via a recursive walk of an AST. We actually parse +/// the AST in reverse order so that the successor of a basic block is +/// constructed prior to its predecessor. This allows us to nicely capture +/// implicit fall-throughs without extra basic blocks. +/// +class CFGBuilder { + typedef BlockScopePosPair JumpTarget; + typedef BlockScopePosPair JumpSource; + + ASTContext *Context; + llvm::OwningPtr<CFG> cfg; + + CFGBlock* Block; + CFGBlock* Succ; + JumpTarget ContinueJumpTarget; + JumpTarget BreakJumpTarget; + CFGBlock* SwitchTerminatedBlock; + CFGBlock* DefaultCaseBlock; + CFGBlock* TryTerminatedBlock; + + // Current position in local scope. + LocalScope::const_iterator ScopePos; + + // LabelMap records the mapping from Label expressions to their jump targets. + typedef llvm::DenseMap<LabelDecl*, JumpTarget> LabelMapTy; + LabelMapTy LabelMap; + + // A list of blocks that end with a "goto" that must be backpatched to their + // resolved targets upon completion of CFG construction. + typedef std::vector<JumpSource> BackpatchBlocksTy; + BackpatchBlocksTy BackpatchBlocks; + + // A list of labels whose address has been taken (for indirect gotos). + typedef llvm::SmallPtrSet<LabelDecl*, 5> LabelSetTy; + LabelSetTy AddressTakenLabels; + + bool badCFG; + CFG::BuildOptions BuildOpts; + +public: + explicit CFGBuilder() : cfg(new CFG()), // crew a new CFG + Block(NULL), Succ(NULL), + SwitchTerminatedBlock(NULL), DefaultCaseBlock(NULL), + TryTerminatedBlock(NULL), badCFG(false) {} + + // buildCFG - Used by external clients to construct the CFG. + CFG* buildCFG(const Decl *D, Stmt *Statement, ASTContext *C, + CFG::BuildOptions BO); + +private: + // Visitors to walk an AST and construct the CFG. + CFGBlock *VisitAddrLabelExpr(AddrLabelExpr *A, AddStmtChoice asc); + CFGBlock *VisitBinaryOperator(BinaryOperator *B, AddStmtChoice asc); + CFGBlock *VisitBlockExpr(BlockExpr* E, AddStmtChoice asc); + CFGBlock *VisitBreakStmt(BreakStmt *B); + CFGBlock *VisitCXXCatchStmt(CXXCatchStmt *S); + CFGBlock *VisitExprWithCleanups(ExprWithCleanups *E, + AddStmtChoice asc); + CFGBlock *VisitCXXThrowExpr(CXXThrowExpr *T); + CFGBlock *VisitCXXTryStmt(CXXTryStmt *S); + CFGBlock *VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E, + AddStmtChoice asc); + CFGBlock *VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc); + CFGBlock *VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E, + AddStmtChoice asc); + CFGBlock *VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C, + AddStmtChoice asc); + CFGBlock *VisitCXXMemberCallExpr(CXXMemberCallExpr *C, AddStmtChoice asc); + CFGBlock *VisitCallExpr(CallExpr *C, AddStmtChoice asc); + CFGBlock *VisitCaseStmt(CaseStmt *C); + CFGBlock *VisitChooseExpr(ChooseExpr *C, AddStmtChoice asc); + CFGBlock *VisitCompoundStmt(CompoundStmt *C); + CFGBlock *VisitConditionalOperator(AbstractConditionalOperator *C, + AddStmtChoice asc); + CFGBlock *VisitContinueStmt(ContinueStmt *C); + CFGBlock *VisitDeclStmt(DeclStmt *DS); + CFGBlock *VisitDeclSubExpr(DeclStmt* DS); + CFGBlock *VisitDefaultStmt(DefaultStmt *D); + CFGBlock *VisitDoStmt(DoStmt *D); + CFGBlock *VisitForStmt(ForStmt *F); + CFGBlock *VisitGotoStmt(GotoStmt* G); + CFGBlock *VisitIfStmt(IfStmt *I); + CFGBlock *VisitImplicitCastExpr(ImplicitCastExpr *E, AddStmtChoice asc); + CFGBlock *VisitIndirectGotoStmt(IndirectGotoStmt *I); + CFGBlock *VisitLabelStmt(LabelStmt *L); + CFGBlock *VisitMemberExpr(MemberExpr *M, AddStmtChoice asc); + CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S); + CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S); + CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S); + CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S); + CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S); + CFGBlock *VisitReturnStmt(ReturnStmt* R); + CFGBlock *VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, AddStmtChoice asc); + CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc); + CFGBlock *VisitSwitchStmt(SwitchStmt *S); + CFGBlock *VisitUnaryOperator(UnaryOperator *U, AddStmtChoice asc); + CFGBlock *VisitWhileStmt(WhileStmt *W); + + CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd); + CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc); + CFGBlock *VisitChildren(Stmt* S); + + // Visitors to walk an AST and generate destructors of temporaries in + // full expression. + CFGBlock *VisitForTemporaryDtors(Stmt *E, bool BindToTemporary = false); + CFGBlock *VisitChildrenForTemporaryDtors(Stmt *E); + CFGBlock *VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E); + CFGBlock *VisitCXXBindTemporaryExprForTemporaryDtors(CXXBindTemporaryExpr *E, + bool BindToTemporary); + CFGBlock * + VisitConditionalOperatorForTemporaryDtors(AbstractConditionalOperator *E, + bool BindToTemporary); + + // NYS == Not Yet Supported + CFGBlock* NYS() { + badCFG = true; + return Block; + } + + void autoCreateBlock() { if (!Block) Block = createBlock(); } + CFGBlock *createBlock(bool add_successor = true); + + CFGBlock *addStmt(Stmt *S) { + return Visit(S, AddStmtChoice::AlwaysAdd); + } + CFGBlock *addInitializer(CXXCtorInitializer *I); + void addAutomaticObjDtors(LocalScope::const_iterator B, + LocalScope::const_iterator E, Stmt* S); + void addImplicitDtorsForDestructor(const CXXDestructorDecl *DD); + + // Local scopes creation. + LocalScope* createOrReuseLocalScope(LocalScope* Scope); + + void addLocalScopeForStmt(Stmt* S); + LocalScope* addLocalScopeForDeclStmt(DeclStmt* DS, LocalScope* Scope = NULL); + LocalScope* addLocalScopeForVarDecl(VarDecl* VD, LocalScope* Scope = NULL); + + void addLocalScopeAndDtors(Stmt* S); + + // Interface to CFGBlock - adding CFGElements. + void appendStmt(CFGBlock *B, Stmt *S, + AddStmtChoice asc = AddStmtChoice::AlwaysAdd) { + B->appendStmt(S, cfg->getBumpVectorContext()); + } + void appendInitializer(CFGBlock *B, CXXCtorInitializer *I) { + B->appendInitializer(I, cfg->getBumpVectorContext()); + } + void appendBaseDtor(CFGBlock *B, const CXXBaseSpecifier *BS) { + B->appendBaseDtor(BS, cfg->getBumpVectorContext()); + } + void appendMemberDtor(CFGBlock *B, FieldDecl *FD) { + B->appendMemberDtor(FD, cfg->getBumpVectorContext()); + } + void appendTemporaryDtor(CFGBlock *B, CXXBindTemporaryExpr *E) { + B->appendTemporaryDtor(E, cfg->getBumpVectorContext()); + } + + void insertAutomaticObjDtors(CFGBlock* Blk, CFGBlock::iterator I, + LocalScope::const_iterator B, LocalScope::const_iterator E, Stmt* S); + void appendAutomaticObjDtors(CFGBlock* Blk, LocalScope::const_iterator B, + LocalScope::const_iterator E, Stmt* S); + void prependAutomaticObjDtorsWithTerminator(CFGBlock* Blk, + LocalScope::const_iterator B, LocalScope::const_iterator E); + + void addSuccessor(CFGBlock *B, CFGBlock *S) { + B->addSuccessor(S, cfg->getBumpVectorContext()); + } + + /// TryResult - a class representing a variant over the values + /// 'true', 'false', or 'unknown'. This is returned by tryEvaluateBool, + /// and is used by the CFGBuilder to decide if a branch condition + /// can be decided up front during CFG construction. + class TryResult { + int X; + public: + TryResult(bool b) : X(b ? 1 : 0) {} + TryResult() : X(-1) {} + + bool isTrue() const { return X == 1; } + bool isFalse() const { return X == 0; } + bool isKnown() const { return X >= 0; } + void negate() { + assert(isKnown()); + X ^= 0x1; + } + }; + + /// tryEvaluateBool - Try and evaluate the Stmt and return 0 or 1 + /// if we can evaluate to a known value, otherwise return -1. + TryResult tryEvaluateBool(Expr *S) { + if (!BuildOpts.PruneTriviallyFalseEdges) + return TryResult(); + + Expr::EvalResult Result; + if (!S->isTypeDependent() && !S->isValueDependent() && + S->Evaluate(Result, *Context) && Result.Val.isInt()) + return Result.Val.getInt().getBoolValue(); + + return TryResult(); + } +}; + +// FIXME: Add support for dependent-sized array types in C++? +// Does it even make sense to build a CFG for an uninstantiated template? +static const VariableArrayType *FindVA(const Type *t) { + while (const ArrayType *vt = dyn_cast<ArrayType>(t)) { + if (const VariableArrayType *vat = dyn_cast<VariableArrayType>(vt)) + if (vat->getSizeExpr()) + return vat; + + t = vt->getElementType().getTypePtr(); + } + + return 0; +} + +/// BuildCFG - Constructs a CFG from an AST (a Stmt*). The AST can represent an +/// arbitrary statement. Examples include a single expression or a function +/// body (compound statement). The ownership of the returned CFG is +/// transferred to the caller. If CFG construction fails, this method returns +/// NULL. +CFG* CFGBuilder::buildCFG(const Decl *D, Stmt* Statement, ASTContext* C, + CFG::BuildOptions BO) { + + Context = C; + assert(cfg.get()); + if (!Statement) + return NULL; + + BuildOpts = BO; + + // Create an empty block that will serve as the exit block for the CFG. Since + // this is the first block added to the CFG, it will be implicitly registered + // as the exit block. + Succ = createBlock(); + assert(Succ == &cfg->getExit()); + Block = NULL; // the EXIT block is empty. Create all other blocks lazily. + + if (BuildOpts.AddImplicitDtors) + if (const CXXDestructorDecl *DD = dyn_cast_or_null<CXXDestructorDecl>(D)) + addImplicitDtorsForDestructor(DD); + + // Visit the statements and create the CFG. + CFGBlock *B = addStmt(Statement); + + if (badCFG) + return NULL; + + // For C++ constructor add initializers to CFG. + if (const CXXConstructorDecl *CD = dyn_cast_or_null<CXXConstructorDecl>(D)) { + for (CXXConstructorDecl::init_const_reverse_iterator I = CD->init_rbegin(), + E = CD->init_rend(); I != E; ++I) { + B = addInitializer(*I); + if (badCFG) + return NULL; + } + } + + if (B) + Succ = B; + + // Backpatch the gotos whose label -> block mappings we didn't know when we + // encountered them. + for (BackpatchBlocksTy::iterator I = BackpatchBlocks.begin(), + E = BackpatchBlocks.end(); I != E; ++I ) { + + CFGBlock* B = I->block; + GotoStmt* G = cast<GotoStmt>(B->getTerminator()); + LabelMapTy::iterator LI = LabelMap.find(G->getLabel()); + + // If there is no target for the goto, then we are looking at an + // incomplete AST. Handle this by not registering a successor. + if (LI == LabelMap.end()) continue; + + JumpTarget JT = LI->second; + prependAutomaticObjDtorsWithTerminator(B, I->scopePosition, + JT.scopePosition); + addSuccessor(B, JT.block); + } + + // Add successors to the Indirect Goto Dispatch block (if we have one). + if (CFGBlock* B = cfg->getIndirectGotoBlock()) + for (LabelSetTy::iterator I = AddressTakenLabels.begin(), + E = AddressTakenLabels.end(); I != E; ++I ) { + + // Lookup the target block. + LabelMapTy::iterator LI = LabelMap.find(*I); + + // If there is no target block that contains label, then we are looking + // at an incomplete AST. Handle this by not registering a successor. + if (LI == LabelMap.end()) continue; + + addSuccessor(B, LI->second.block); + } + + // Create an empty entry block that has no predecessors. + cfg->setEntry(createBlock()); + + return cfg.take(); +} + +/// createBlock - Used to lazily create blocks that are connected +/// to the current (global) succcessor. +CFGBlock* CFGBuilder::createBlock(bool add_successor) { + CFGBlock* B = cfg->createBlock(); + if (add_successor && Succ) + addSuccessor(B, Succ); + return B; +} + +/// addInitializer - Add C++ base or member initializer element to CFG. +CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) { + if (!BuildOpts.AddInitializers) + return Block; + + bool IsReference = false; + bool HasTemporaries = false; + + // Destructors of temporaries in initialization expression should be called + // after initialization finishes. + Expr *Init = I->getInit(); + if (Init) { + if (FieldDecl *FD = I->getAnyMember()) + IsReference = FD->getType()->isReferenceType(); + HasTemporaries = isa<ExprWithCleanups>(Init); + + if (BuildOpts.AddImplicitDtors && HasTemporaries) { + // Generate destructors for temporaries in initialization expression. + VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(), + IsReference); + } + } + + autoCreateBlock(); + appendInitializer(Block, I); + + if (Init) { + if (HasTemporaries) { + // For expression with temporaries go directly to subexpression to omit + // generating destructors for the second time. + return Visit(cast<ExprWithCleanups>(Init)->getSubExpr()); + } + return Visit(Init); + } + + return Block; +} + +/// addAutomaticObjDtors - Add to current block automatic objects destructors +/// for objects in range of local scope positions. Use S as trigger statement +/// for destructors. +void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B, + LocalScope::const_iterator E, Stmt* S) { + if (!BuildOpts.AddImplicitDtors) + return; + + if (B == E) + return; + + autoCreateBlock(); + appendAutomaticObjDtors(Block, B, E, S); +} + +/// addImplicitDtorsForDestructor - Add implicit destructors generated for +/// base and member objects in destructor. +void CFGBuilder::addImplicitDtorsForDestructor(const CXXDestructorDecl *DD) { + assert (BuildOpts.AddImplicitDtors + && "Can be called only when dtors should be added"); + const CXXRecordDecl *RD = DD->getParent(); + + // At the end destroy virtual base objects. + for (CXXRecordDecl::base_class_const_iterator VI = RD->vbases_begin(), + VE = RD->vbases_end(); VI != VE; ++VI) { + const CXXRecordDecl *CD = VI->getType()->getAsCXXRecordDecl(); + if (!CD->hasTrivialDestructor()) { + autoCreateBlock(); + appendBaseDtor(Block, VI); + } + } + + // Before virtual bases destroy direct base objects. + for (CXXRecordDecl::base_class_const_iterator BI = RD->bases_begin(), + BE = RD->bases_end(); BI != BE; ++BI) { + if (!BI->isVirtual()) { + const CXXRecordDecl *CD = BI->getType()->getAsCXXRecordDecl(); + if (!CD->hasTrivialDestructor()) { + autoCreateBlock(); + appendBaseDtor(Block, BI); + } + } + } + + // First destroy member objects. + for (CXXRecordDecl::field_iterator FI = RD->field_begin(), + FE = RD->field_end(); FI != FE; ++FI) { + // Check for constant size array. Set type to array element type. + QualType QT = FI->getType(); + if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) { + if (AT->getSize() == 0) + continue; + QT = AT->getElementType(); + } + + if (const CXXRecordDecl *CD = QT->getAsCXXRecordDecl()) + if (!CD->hasTrivialDestructor()) { + autoCreateBlock(); + appendMemberDtor(Block, *FI); + } + } +} + +/// createOrReuseLocalScope - If Scope is NULL create new LocalScope. Either +/// way return valid LocalScope object. +LocalScope* CFGBuilder::createOrReuseLocalScope(LocalScope* Scope) { + if (!Scope) { + llvm::BumpPtrAllocator &alloc = cfg->getAllocator(); + Scope = alloc.Allocate<LocalScope>(); + BumpVectorContext ctx(alloc); + new (Scope) LocalScope(ctx, ScopePos); + } + return Scope; +} + +/// addLocalScopeForStmt - Add LocalScope to local scopes tree for statement +/// that should create implicit scope (e.g. if/else substatements). +void CFGBuilder::addLocalScopeForStmt(Stmt* S) { + if (!BuildOpts.AddImplicitDtors) + return; + + LocalScope *Scope = 0; + + // For compound statement we will be creating explicit scope. + if (CompoundStmt *CS = dyn_cast<CompoundStmt>(S)) { + for (CompoundStmt::body_iterator BI = CS->body_begin(), BE = CS->body_end() + ; BI != BE; ++BI) { + Stmt *SI = *BI; + if (LabelStmt *LS = dyn_cast<LabelStmt>(SI)) + SI = LS->getSubStmt(); + if (DeclStmt *DS = dyn_cast<DeclStmt>(SI)) + Scope = addLocalScopeForDeclStmt(DS, Scope); + } + return; + } + + // For any other statement scope will be implicit and as such will be + // interesting only for DeclStmt. + if (LabelStmt *LS = dyn_cast<LabelStmt>(S)) + S = LS->getSubStmt(); + if (DeclStmt *DS = dyn_cast<DeclStmt>(S)) + addLocalScopeForDeclStmt(DS); +} + +/// addLocalScopeForDeclStmt - Add LocalScope for declaration statement. Will +/// reuse Scope if not NULL. +LocalScope* CFGBuilder::addLocalScopeForDeclStmt(DeclStmt* DS, + LocalScope* Scope) { + if (!BuildOpts.AddImplicitDtors) + return Scope; + + for (DeclStmt::decl_iterator DI = DS->decl_begin(), DE = DS->decl_end() + ; DI != DE; ++DI) { + if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) + Scope = addLocalScopeForVarDecl(VD, Scope); + } + return Scope; +} + +/// addLocalScopeForVarDecl - Add LocalScope for variable declaration. It will +/// create add scope for automatic objects and temporary objects bound to +/// const reference. Will reuse Scope if not NULL. +LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl* VD, + LocalScope* Scope) { + if (!BuildOpts.AddImplicitDtors) + return Scope; + + // Check if variable is local. + switch (VD->getStorageClass()) { + case SC_None: + case SC_Auto: + case SC_Register: + break; + default: return Scope; + } + + // Check for const references bound to temporary. Set type to pointee. + QualType QT = VD->getType(); + if (const ReferenceType* RT = QT.getTypePtr()->getAs<ReferenceType>()) { + QT = RT->getPointeeType(); + if (!QT.isConstQualified()) + return Scope; + if (!VD->getInit() || !VD->getInit()->Classify(*Context).isRValue()) + return Scope; + } + + // Check for constant size array. Set type to array element type. + if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) { + if (AT->getSize() == 0) + return Scope; + QT = AT->getElementType(); + } + + // Check if type is a C++ class with non-trivial destructor. + if (const CXXRecordDecl* CD = QT->getAsCXXRecordDecl()) + if (!CD->hasTrivialDestructor()) { + // Add the variable to scope + Scope = createOrReuseLocalScope(Scope); + Scope->addVar(VD); + ScopePos = Scope->begin(); + } + return Scope; +} + +/// addLocalScopeAndDtors - For given statement add local scope for it and +/// add destructors that will cleanup the scope. Will reuse Scope if not NULL. +void CFGBuilder::addLocalScopeAndDtors(Stmt* S) { + if (!BuildOpts.AddImplicitDtors) + return; + + LocalScope::const_iterator scopeBeginPos = ScopePos; + addLocalScopeForStmt(S); + addAutomaticObjDtors(ScopePos, scopeBeginPos, S); +} + +/// insertAutomaticObjDtors - Insert destructor CFGElements for variables with +/// automatic storage duration to CFGBlock's elements vector. Insertion will be +/// performed in place specified with iterator. +void CFGBuilder::insertAutomaticObjDtors(CFGBlock* Blk, CFGBlock::iterator I, + LocalScope::const_iterator B, LocalScope::const_iterator E, Stmt* S) { + BumpVectorContext& C = cfg->getBumpVectorContext(); + I = Blk->beginAutomaticObjDtorsInsert(I, B.distance(E), C); + while (B != E) + I = Blk->insertAutomaticObjDtor(I, *B++, S); +} + +/// appendAutomaticObjDtors - Append destructor CFGElements for variables with +/// automatic storage duration to CFGBlock's elements vector. Elements will be +/// appended to physical end of the vector which happens to be logical +/// beginning. +void CFGBuilder::appendAutomaticObjDtors(CFGBlock* Blk, + LocalScope::const_iterator B, LocalScope::const_iterator E, Stmt* S) { + insertAutomaticObjDtors(Blk, Blk->begin(), B, E, S); +} + +/// prependAutomaticObjDtorsWithTerminator - Prepend destructor CFGElements for +/// variables with automatic storage duration to CFGBlock's elements vector. +/// Elements will be prepended to physical beginning of the vector which +/// happens to be logical end. Use blocks terminator as statement that specifies +/// destructors call site. +void CFGBuilder::prependAutomaticObjDtorsWithTerminator(CFGBlock* Blk, + LocalScope::const_iterator B, LocalScope::const_iterator E) { + insertAutomaticObjDtors(Blk, Blk->end(), B, E, Blk->getTerminator()); +} + +/// Visit - Walk the subtree of a statement and add extra +/// blocks for ternary operators, &&, and ||. We also process "," and +/// DeclStmts (which may contain nested control-flow). +CFGBlock* CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) { +tryAgain: + if (!S) { + badCFG = true; + return 0; + } + switch (S->getStmtClass()) { + default: + return VisitStmt(S, asc); + + case Stmt::AddrLabelExprClass: + return VisitAddrLabelExpr(cast<AddrLabelExpr>(S), asc); + + case Stmt::BinaryConditionalOperatorClass: + return VisitConditionalOperator(cast<BinaryConditionalOperator>(S), asc); + + case Stmt::BinaryOperatorClass: + return VisitBinaryOperator(cast<BinaryOperator>(S), asc); + + case Stmt::BlockExprClass: + return VisitBlockExpr(cast<BlockExpr>(S), asc); + + case Stmt::BreakStmtClass: + return VisitBreakStmt(cast<BreakStmt>(S)); + + case Stmt::CallExprClass: + case Stmt::CXXOperatorCallExprClass: + return VisitCallExpr(cast<CallExpr>(S), asc); + + case Stmt::CaseStmtClass: + return VisitCaseStmt(cast<CaseStmt>(S)); + + case Stmt::ChooseExprClass: + return VisitChooseExpr(cast<ChooseExpr>(S), asc); + + case Stmt::CompoundStmtClass: + return VisitCompoundStmt(cast<CompoundStmt>(S)); + + case Stmt::ConditionalOperatorClass: + return VisitConditionalOperator(cast<ConditionalOperator>(S), asc); + + case Stmt::ContinueStmtClass: + return VisitContinueStmt(cast<ContinueStmt>(S)); + + case Stmt::CXXCatchStmtClass: + return VisitCXXCatchStmt(cast<CXXCatchStmt>(S)); + + case Stmt::ExprWithCleanupsClass: + return VisitExprWithCleanups(cast<ExprWithCleanups>(S), asc); + + case Stmt::CXXBindTemporaryExprClass: + return VisitCXXBindTemporaryExpr(cast<CXXBindTemporaryExpr>(S), asc); + + case Stmt::CXXConstructExprClass: + return VisitCXXConstructExpr(cast<CXXConstructExpr>(S), asc); + + case Stmt::CXXFunctionalCastExprClass: + return VisitCXXFunctionalCastExpr(cast<CXXFunctionalCastExpr>(S), asc); + + case Stmt::CXXTemporaryObjectExprClass: + return VisitCXXTemporaryObjectExpr(cast<CXXTemporaryObjectExpr>(S), asc); + + case Stmt::CXXMemberCallExprClass: + return VisitCXXMemberCallExpr(cast<CXXMemberCallExpr>(S), asc); + + case Stmt::CXXThrowExprClass: + return VisitCXXThrowExpr(cast<CXXThrowExpr>(S)); + + case Stmt::CXXTryStmtClass: + return VisitCXXTryStmt(cast<CXXTryStmt>(S)); + + case Stmt::DeclStmtClass: + return VisitDeclStmt(cast<DeclStmt>(S)); + + case Stmt::DefaultStmtClass: + return VisitDefaultStmt(cast<DefaultStmt>(S)); + + case Stmt::DoStmtClass: + return VisitDoStmt(cast<DoStmt>(S)); + + case Stmt::ForStmtClass: + return VisitForStmt(cast<ForStmt>(S)); + + case Stmt::GotoStmtClass: + return VisitGotoStmt(cast<GotoStmt>(S)); + + case Stmt::IfStmtClass: + return VisitIfStmt(cast<IfStmt>(S)); + + case Stmt::ImplicitCastExprClass: + return VisitImplicitCastExpr(cast<ImplicitCastExpr>(S), asc); + + case Stmt::IndirectGotoStmtClass: + return VisitIndirectGotoStmt(cast<IndirectGotoStmt>(S)); + + case Stmt::LabelStmtClass: + return VisitLabelStmt(cast<LabelStmt>(S)); + + case Stmt::MemberExprClass: + return VisitMemberExpr(cast<MemberExpr>(S), asc); + + case Stmt::ObjCAtCatchStmtClass: + return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S)); + + case Stmt::ObjCAtSynchronizedStmtClass: + return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S)); + + case Stmt::ObjCAtThrowStmtClass: + return VisitObjCAtThrowStmt(cast<ObjCAtThrowStmt>(S)); + + case Stmt::ObjCAtTryStmtClass: + return VisitObjCAtTryStmt(cast<ObjCAtTryStmt>(S)); + + case Stmt::ObjCForCollectionStmtClass: + return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S)); + + case Stmt::ParenExprClass: + S = cast<ParenExpr>(S)->getSubExpr(); + goto tryAgain; + + case Stmt::NullStmtClass: + return Block; + + case Stmt::ReturnStmtClass: + return VisitReturnStmt(cast<ReturnStmt>(S)); + + case Stmt::SizeOfAlignOfExprClass: + return VisitSizeOfAlignOfExpr(cast<SizeOfAlignOfExpr>(S), asc); + + case Stmt::StmtExprClass: + return VisitStmtExpr(cast<StmtExpr>(S), asc); + + case Stmt::SwitchStmtClass: + return VisitSwitchStmt(cast<SwitchStmt>(S)); + + case Stmt::UnaryOperatorClass: + return VisitUnaryOperator(cast<UnaryOperator>(S), asc); + + case Stmt::WhileStmtClass: + return VisitWhileStmt(cast<WhileStmt>(S)); + } +} + +CFGBlock *CFGBuilder::VisitStmt(Stmt *S, AddStmtChoice asc) { + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, S, asc); + } + + return VisitChildren(S); +} + +/// VisitChildren - Visit the children of a Stmt. +CFGBlock *CFGBuilder::VisitChildren(Stmt* Terminator) { + CFGBlock *B = Block; + for (Stmt::child_range I = Terminator->children(); I; ++I) { + if (*I) B = Visit(*I); + } + return B; +} + +CFGBlock *CFGBuilder::VisitAddrLabelExpr(AddrLabelExpr *A, + AddStmtChoice asc) { + AddressTakenLabels.insert(A->getLabel()); + + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, A, asc); + } + + return Block; +} + +CFGBlock *CFGBuilder::VisitUnaryOperator(UnaryOperator *U, + AddStmtChoice asc) { + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, U, asc); + } + + return Visit(U->getSubExpr(), AddStmtChoice()); +} + +CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, + AddStmtChoice asc) { + if (B->isLogicalOp()) { // && or || + CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); + appendStmt(ConfluenceBlock, B, asc); + + if (badCFG) + return 0; + + // create the block evaluating the LHS + CFGBlock* LHSBlock = createBlock(false); + LHSBlock->setTerminator(B); + + // create the block evaluating the RHS + Succ = ConfluenceBlock; + Block = NULL; + CFGBlock* RHSBlock = addStmt(B->getRHS()); + + if (RHSBlock) { + if (badCFG) + return 0; + } else { + // Create an empty block for cases where the RHS doesn't require + // any explicit statements in the CFG. + RHSBlock = createBlock(); + } + + // See if this is a known constant. + TryResult KnownVal = tryEvaluateBool(B->getLHS()); + if (KnownVal.isKnown() && (B->getOpcode() == BO_LOr)) + KnownVal.negate(); + + // Now link the LHSBlock with RHSBlock. + if (B->getOpcode() == BO_LOr) { + addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); + addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); + } else { + assert(B->getOpcode() == BO_LAnd); + addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); + addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); + } + + // Generate the blocks for evaluating the LHS. + Block = LHSBlock; + return addStmt(B->getLHS()); + } + + if (B->getOpcode() == BO_Comma) { // , + autoCreateBlock(); + appendStmt(Block, B, asc); + addStmt(B->getRHS()); + return addStmt(B->getLHS()); + } + + if (B->isAssignmentOp()) { + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, B, asc); + } + Visit(B->getLHS()); + return Visit(B->getRHS()); + } + + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, B, asc); + } + + CFGBlock *RBlock = Visit(B->getRHS()); + CFGBlock *LBlock = Visit(B->getLHS()); + // If visiting RHS causes us to finish 'Block', e.g. the RHS is a StmtExpr + // containing a DoStmt, and the LHS doesn't create a new block, then we should + // return RBlock. Otherwise we'll incorrectly return NULL. + return (LBlock ? LBlock : RBlock); +} + +CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) { + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, E, asc); + } + return Block; +} + +CFGBlock *CFGBuilder::VisitBreakStmt(BreakStmt *B) { + // "break" is a control-flow statement. Thus we stop processing the current + // block. + if (badCFG) + return 0; + + // Now create a new block that ends with the break statement. + Block = createBlock(false); + Block->setTerminator(B); + + // If there is no target for the break, then we are looking at an incomplete + // AST. This means that the CFG cannot be constructed. + if (BreakJumpTarget.block) { + addAutomaticObjDtors(ScopePos, BreakJumpTarget.scopePosition, B); + addSuccessor(Block, BreakJumpTarget.block); + } else + badCFG = true; + + + return Block; +} + +static bool CanThrow(Expr *E) { + QualType Ty = E->getType(); + if (Ty->isFunctionPointerType()) + Ty = Ty->getAs<PointerType>()->getPointeeType(); + else if (Ty->isBlockPointerType()) + Ty = Ty->getAs<BlockPointerType>()->getPointeeType(); + + const FunctionType *FT = Ty->getAs<FunctionType>(); + if (FT) { + if (const FunctionProtoType *Proto = dyn_cast<FunctionProtoType>(FT)) + if (Proto->hasEmptyExceptionSpec()) + return false; + } + return true; +} + +CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { + // If this is a call to a no-return function, this stops the block here. + bool NoReturn = false; + if (getFunctionExtInfo(*C->getCallee()->getType()).getNoReturn()) { + NoReturn = true; + } + + bool AddEHEdge = false; + + // Languages without exceptions are assumed to not throw. + if (Context->getLangOptions().areExceptionsEnabled()) { + if (BuildOpts.AddEHEdges) + AddEHEdge = true; + } + + if (FunctionDecl *FD = C->getDirectCallee()) { + if (FD->hasAttr<NoReturnAttr>()) + NoReturn = true; + if (FD->hasAttr<NoThrowAttr>()) + AddEHEdge = false; + } + + if (!CanThrow(C->getCallee())) + AddEHEdge = false; + + if (!NoReturn && !AddEHEdge) + return VisitStmt(C, asc.withAlwaysAdd(true)); + + if (Block) { + Succ = Block; + if (badCFG) + return 0; + } + + Block = createBlock(!NoReturn); + appendStmt(Block, C, asc); + + if (NoReturn) { + // Wire this to the exit block directly. + addSuccessor(Block, &cfg->getExit()); + } + if (AddEHEdge) { + // Add exceptional edges. + if (TryTerminatedBlock) + addSuccessor(Block, TryTerminatedBlock); + else + addSuccessor(Block, &cfg->getExit()); + } + + return VisitChildren(C); +} + +CFGBlock *CFGBuilder::VisitChooseExpr(ChooseExpr *C, + AddStmtChoice asc) { + CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); + appendStmt(ConfluenceBlock, C, asc); + if (badCFG) + return 0; + + AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true); + Succ = ConfluenceBlock; + Block = NULL; + CFGBlock* LHSBlock = Visit(C->getLHS(), alwaysAdd); + if (badCFG) + return 0; + + Succ = ConfluenceBlock; + Block = NULL; + CFGBlock* RHSBlock = Visit(C->getRHS(), alwaysAdd); + if (badCFG) + return 0; + + Block = createBlock(false); + // See if this is a known constant. + const TryResult& KnownVal = tryEvaluateBool(C->getCond()); + addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); + addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); + Block->setTerminator(C); + return addStmt(C->getCond()); +} + + +CFGBlock* CFGBuilder::VisitCompoundStmt(CompoundStmt* C) { + addLocalScopeAndDtors(C); + CFGBlock* LastBlock = Block; + + for (CompoundStmt::reverse_body_iterator I=C->body_rbegin(), E=C->body_rend(); + I != E; ++I ) { + // If we hit a segment of code just containing ';' (NullStmts), we can + // get a null block back. In such cases, just use the LastBlock + if (CFGBlock *newBlock = addStmt(*I)) + LastBlock = newBlock; + + if (badCFG) + return NULL; + } + + return LastBlock; +} + +CFGBlock *CFGBuilder::VisitConditionalOperator(AbstractConditionalOperator *C, + AddStmtChoice asc) { + const BinaryConditionalOperator *BCO = dyn_cast<BinaryConditionalOperator>(C); + const OpaqueValueExpr *opaqueValue = (BCO ? BCO->getOpaqueValue() : NULL); + + // Create the confluence block that will "merge" the results of the ternary + // expression. + CFGBlock* ConfluenceBlock = Block ? Block : createBlock(); + appendStmt(ConfluenceBlock, C, asc); + if (badCFG) + return 0; + + AddStmtChoice alwaysAdd = asc.withAlwaysAdd(true); + + // Create a block for the LHS expression if there is an LHS expression. A + // GCC extension allows LHS to be NULL, causing the condition to be the + // value that is returned instead. + // e.g: x ?: y is shorthand for: x ? x : y; + Succ = ConfluenceBlock; + Block = NULL; + CFGBlock* LHSBlock = 0; + const Expr *trueExpr = C->getTrueExpr(); + if (trueExpr != opaqueValue) { + LHSBlock = Visit(C->getTrueExpr(), alwaysAdd); + if (badCFG) + return 0; + Block = NULL; + } + + // Create the block for the RHS expression. + Succ = ConfluenceBlock; + CFGBlock* RHSBlock = Visit(C->getFalseExpr(), alwaysAdd); + if (badCFG) + return 0; + + // Create the block that will contain the condition. + Block = createBlock(false); + + // See if this is a known constant. + const TryResult& KnownVal = tryEvaluateBool(C->getCond()); + if (LHSBlock) + addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); + addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); + Block->setTerminator(C); + Expr *condExpr = C->getCond(); + + CFGBlock *result = 0; + + // Run the condition expression if it's not trivially expressed in + // terms of the opaque value (or if there is no opaque value). + if (condExpr != opaqueValue) result = addStmt(condExpr); + + // Before that, run the common subexpression if there was one. + // At least one of this or the above will be run. + if (opaqueValue) result = addStmt(BCO->getCommon()); + + return result; +} + +CFGBlock *CFGBuilder::VisitDeclStmt(DeclStmt *DS) { + if (DS->isSingleDecl()) + return VisitDeclSubExpr(DS); + + CFGBlock *B = 0; + + // FIXME: Add a reverse iterator for DeclStmt to avoid this extra copy. + typedef llvm::SmallVector<Decl*,10> BufTy; + BufTy Buf(DS->decl_begin(), DS->decl_end()); + + for (BufTy::reverse_iterator I = Buf.rbegin(), E = Buf.rend(); I != E; ++I) { + // Get the alignment of the new DeclStmt, padding out to >=8 bytes. + unsigned A = llvm::AlignOf<DeclStmt>::Alignment < 8 + ? 8 : llvm::AlignOf<DeclStmt>::Alignment; + + // Allocate the DeclStmt using the BumpPtrAllocator. It will get + // automatically freed with the CFG. + DeclGroupRef DG(*I); + Decl *D = *I; + void *Mem = cfg->getAllocator().Allocate(sizeof(DeclStmt), A); + DeclStmt *DSNew = new (Mem) DeclStmt(DG, D->getLocation(), GetEndLoc(D)); + + // Append the fake DeclStmt to block. + B = VisitDeclSubExpr(DSNew); + } + + return B; +} + +/// VisitDeclSubExpr - Utility method to add block-level expressions for +/// DeclStmts and initializers in them. +CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt* DS) { + assert(DS->isSingleDecl() && "Can handle single declarations only."); + + VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl()); + + if (!VD) { + autoCreateBlock(); + appendStmt(Block, DS); + return Block; + } + + bool IsReference = false; + bool HasTemporaries = false; + + // Destructors of temporaries in initialization expression should be called + // after initialization finishes. + Expr *Init = VD->getInit(); + if (Init) { + IsReference = VD->getType()->isReferenceType(); + HasTemporaries = isa<ExprWithCleanups>(Init); + + if (BuildOpts.AddImplicitDtors && HasTemporaries) { + // Generate destructors for temporaries in initialization expression. + VisitForTemporaryDtors(cast<ExprWithCleanups>(Init)->getSubExpr(), + IsReference); + } + } + + autoCreateBlock(); + appendStmt(Block, DS); + + if (Init) { + if (HasTemporaries) + // For expression with temporaries go directly to subexpression to omit + // generating destructors for the second time. + Visit(cast<ExprWithCleanups>(Init)->getSubExpr()); + else + Visit(Init); + } + + // If the type of VD is a VLA, then we must process its size expressions. + for (const VariableArrayType* VA = FindVA(VD->getType().getTypePtr()); + VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) + Block = addStmt(VA->getSizeExpr()); + + // Remove variable from local scope. + if (ScopePos && VD == *ScopePos) + ++ScopePos; + + return Block; +} + +CFGBlock* CFGBuilder::VisitIfStmt(IfStmt* I) { + // We may see an if statement in the middle of a basic block, or it may be the + // first statement we are processing. In either case, we create a new basic + // block. First, we create the blocks for the then...else statements, and + // then we create the block containing the if statement. If we were in the + // middle of a block, we stop processing that block. That block is then the + // implicit successor for the "then" and "else" clauses. + + // Save local scope position because in case of condition variable ScopePos + // won't be restored when traversing AST. + SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); + + // Create local scope for possible condition variable. + // Store scope position. Add implicit destructor. + if (VarDecl* VD = I->getConditionVariable()) { + LocalScope::const_iterator BeginScopePos = ScopePos; + addLocalScopeForVarDecl(VD); + addAutomaticObjDtors(ScopePos, BeginScopePos, I); + } + + // The block we were proccessing is now finished. Make it the successor + // block. + if (Block) { + Succ = Block; + if (badCFG) + return 0; + } + + // Process the false branch. + CFGBlock* ElseBlock = Succ; + + if (Stmt* Else = I->getElse()) { + SaveAndRestore<CFGBlock*> sv(Succ); + + // NULL out Block so that the recursive call to Visit will + // create a new basic block. + Block = NULL; + + // If branch is not a compound statement create implicit scope + // and add destructors. + if (!isa<CompoundStmt>(Else)) + addLocalScopeAndDtors(Else); + + ElseBlock = addStmt(Else); + + if (!ElseBlock) // Can occur when the Else body has all NullStmts. + ElseBlock = sv.get(); + else if (Block) { + if (badCFG) + return 0; + } + } + + // Process the true branch. + CFGBlock* ThenBlock; + { + Stmt* Then = I->getThen(); + assert(Then); + SaveAndRestore<CFGBlock*> sv(Succ); + Block = NULL; + + // If branch is not a compound statement create implicit scope + // and add destructors. + if (!isa<CompoundStmt>(Then)) + addLocalScopeAndDtors(Then); + + ThenBlock = addStmt(Then); + + if (!ThenBlock) { + // We can reach here if the "then" body has all NullStmts. + // Create an empty block so we can distinguish between true and false + // branches in path-sensitive analyses. + ThenBlock = createBlock(false); + addSuccessor(ThenBlock, sv.get()); + } else if (Block) { + if (badCFG) + return 0; + } + } + + // Now create a new block containing the if statement. + Block = createBlock(false); + + // Set the terminator of the new block to the If statement. + Block->setTerminator(I); + + // See if this is a known constant. + const TryResult &KnownVal = tryEvaluateBool(I->getCond()); + + // Now add the successors. + addSuccessor(Block, KnownVal.isFalse() ? NULL : ThenBlock); + addSuccessor(Block, KnownVal.isTrue()? NULL : ElseBlock); + + // Add the condition as the last statement in the new block. This may create + // new blocks as the condition may contain control-flow. Any newly created + // blocks will be pointed to be "Block". + Block = addStmt(I->getCond()); + + // Finally, if the IfStmt contains a condition variable, add both the IfStmt + // and the condition variable initialization to the CFG. + if (VarDecl *VD = I->getConditionVariable()) { + if (Expr *Init = VD->getInit()) { + autoCreateBlock(); + appendStmt(Block, I, AddStmtChoice::AlwaysAdd); + addStmt(Init); + } + } + + return Block; +} + + +CFGBlock* CFGBuilder::VisitReturnStmt(ReturnStmt* R) { + // If we were in the middle of a block we stop processing that block. + // + // NOTE: If a "return" appears in the middle of a block, this means that the + // code afterwards is DEAD (unreachable). We still keep a basic block + // for that code; a simple "mark-and-sweep" from the entry block will be + // able to report such dead blocks. + + // Create the new block. + Block = createBlock(false); + + // The Exit block is the only successor. + addAutomaticObjDtors(ScopePos, LocalScope::const_iterator(), R); + addSuccessor(Block, &cfg->getExit()); + + // Add the return statement to the block. This may create new blocks if R + // contains control-flow (short-circuit operations). + return VisitStmt(R, AddStmtChoice::AlwaysAdd); +} + +CFGBlock* CFGBuilder::VisitLabelStmt(LabelStmt *L) { + // Get the block of the labeled statement. Add it to our map. + addStmt(L->getSubStmt()); + CFGBlock *LabelBlock = Block; + + if (!LabelBlock) // This can happen when the body is empty, i.e. + LabelBlock = createBlock(); // scopes that only contains NullStmts. + + assert(LabelMap.find(L->getDecl()) == LabelMap.end() && + "label already in map"); + LabelMap[L->getDecl()] = JumpTarget(LabelBlock, ScopePos); + + // Labels partition blocks, so this is the end of the basic block we were + // processing (L is the block's label). Because this is label (and we have + // already processed the substatement) there is no extra control-flow to worry + // about. + LabelBlock->setLabel(L); + if (badCFG) + return 0; + + // We set Block to NULL to allow lazy creation of a new block (if necessary); + Block = NULL; + + // This block is now the implicit successor of other blocks. + Succ = LabelBlock; + + return LabelBlock; +} + +CFGBlock* CFGBuilder::VisitGotoStmt(GotoStmt* G) { + // Goto is a control-flow statement. Thus we stop processing the current + // block and create a new one. + + Block = createBlock(false); + Block->setTerminator(G); + + // If we already know the mapping to the label block add the successor now. + LabelMapTy::iterator I = LabelMap.find(G->getLabel()); + + if (I == LabelMap.end()) + // We will need to backpatch this block later. + BackpatchBlocks.push_back(JumpSource(Block, ScopePos)); + else { + JumpTarget JT = I->second; + addAutomaticObjDtors(ScopePos, JT.scopePosition, G); + addSuccessor(Block, JT.block); + } + + return Block; +} + +CFGBlock* CFGBuilder::VisitForStmt(ForStmt* F) { + CFGBlock* LoopSuccessor = NULL; + + // Save local scope position because in case of condition variable ScopePos + // won't be restored when traversing AST. + SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); + + // Create local scope for init statement and possible condition variable. + // Add destructor for init statement and condition variable. + // Store scope position for continue statement. + if (Stmt* Init = F->getInit()) + addLocalScopeForStmt(Init); + LocalScope::const_iterator LoopBeginScopePos = ScopePos; + + if (VarDecl* VD = F->getConditionVariable()) + addLocalScopeForVarDecl(VD); + LocalScope::const_iterator ContinueScopePos = ScopePos; + + addAutomaticObjDtors(ScopePos, save_scope_pos.get(), F); + + // "for" is a control-flow statement. Thus we stop processing the current + // block. + if (Block) { + if (badCFG) + return 0; + LoopSuccessor = Block; + } else + LoopSuccessor = Succ; + + // Save the current value for the break targets. + // All breaks should go to the code following the loop. + SaveAndRestore<JumpTarget> save_break(BreakJumpTarget); + BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); + + // Because of short-circuit evaluation, the condition of the loop can span + // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that + // evaluate the condition. + CFGBlock* ExitConditionBlock = createBlock(false); + CFGBlock* EntryConditionBlock = ExitConditionBlock; + + // Set the terminator for the "exit" condition block. + ExitConditionBlock->setTerminator(F); + + // Now add the actual condition to the condition block. Because the condition + // itself may contain control-flow, new blocks may be created. + if (Stmt* C = F->getCond()) { + Block = ExitConditionBlock; + EntryConditionBlock = addStmt(C); + if (badCFG) + return 0; + assert(Block == EntryConditionBlock || + (Block == 0 && EntryConditionBlock == Succ)); + + // If this block contains a condition variable, add both the condition + // variable and initializer to the CFG. + if (VarDecl *VD = F->getConditionVariable()) { + if (Expr *Init = VD->getInit()) { + autoCreateBlock(); + appendStmt(Block, F, AddStmtChoice::AlwaysAdd); + EntryConditionBlock = addStmt(Init); + assert(Block == EntryConditionBlock); + } + } + + if (Block) { + if (badCFG) + return 0; + } + } + + // The condition block is the implicit successor for the loop body as well as + // any code above the loop. + Succ = EntryConditionBlock; + + // See if this is a known constant. + TryResult KnownVal(true); + + if (F->getCond()) + KnownVal = tryEvaluateBool(F->getCond()); + + // Now create the loop body. + { + assert(F->getBody()); + + // Save the current values for Block, Succ, and continue targets. + SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); + SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget); + + // Create a new block to contain the (bottom) of the loop body. + Block = NULL; + + // Loop body should end with destructor of Condition variable (if any). + addAutomaticObjDtors(ScopePos, LoopBeginScopePos, F); + + if (Stmt* I = F->getInc()) { + // Generate increment code in its own basic block. This is the target of + // continue statements. + Succ = addStmt(I); + } else { + // No increment code. Create a special, empty, block that is used as the + // target block for "looping back" to the start of the loop. + assert(Succ == EntryConditionBlock); + Succ = Block ? Block : createBlock(); + } + + // Finish up the increment (or empty) block if it hasn't been already. + if (Block) { + assert(Block == Succ); + if (badCFG) + return 0; + Block = 0; + } + + ContinueJumpTarget = JumpTarget(Succ, ContinueScopePos); + + // The starting block for the loop increment is the block that should + // represent the 'loop target' for looping back to the start of the loop. + ContinueJumpTarget.block->setLoopTarget(F); + + // If body is not a compound statement create implicit scope + // and add destructors. + if (!isa<CompoundStmt>(F->getBody())) + addLocalScopeAndDtors(F->getBody()); + + // Now populate the body block, and in the process create new blocks as we + // walk the body of the loop. + CFGBlock* BodyBlock = addStmt(F->getBody()); + + if (!BodyBlock) + BodyBlock = ContinueJumpTarget.block;//can happen for "for (...;...;...);" + else if (badCFG) + return 0; + + // This new body block is a successor to our "exit" condition block. + addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); + } + + // Link up the condition block with the code that follows the loop. (the + // false branch). + addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); + + // If the loop contains initialization, create a new block for those + // statements. This block can also contain statements that precede the loop. + if (Stmt* I = F->getInit()) { + Block = createBlock(); + return addStmt(I); + } + + // There is no loop initialization. We are thus basically a while loop. + // NULL out Block to force lazy block construction. + Block = NULL; + Succ = EntryConditionBlock; + return EntryConditionBlock; +} + +CFGBlock *CFGBuilder::VisitMemberExpr(MemberExpr *M, AddStmtChoice asc) { + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, M, asc); + } + return Visit(M->getBase()); +} + +CFGBlock* CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { + // Objective-C fast enumeration 'for' statements: + // http://developer.apple.com/documentation/Cocoa/Conceptual/ObjectiveC + // + // for ( Type newVariable in collection_expression ) { statements } + // + // becomes: + // + // prologue: + // 1. collection_expression + // T. jump to loop_entry + // loop_entry: + // 1. side-effects of element expression + // 1. ObjCForCollectionStmt [performs binding to newVariable] + // T. ObjCForCollectionStmt TB, FB [jumps to TB if newVariable != nil] + // TB: + // statements + // T. jump to loop_entry + // FB: + // what comes after + // + // and + // + // Type existingItem; + // for ( existingItem in expression ) { statements } + // + // becomes: + // + // the same with newVariable replaced with existingItem; the binding works + // the same except that for one ObjCForCollectionStmt::getElement() returns + // a DeclStmt and the other returns a DeclRefExpr. + // + + CFGBlock* LoopSuccessor = 0; + + if (Block) { + if (badCFG) + return 0; + LoopSuccessor = Block; + Block = 0; + } else + LoopSuccessor = Succ; + + // Build the condition blocks. + CFGBlock* ExitConditionBlock = createBlock(false); + CFGBlock* EntryConditionBlock = ExitConditionBlock; + + // Set the terminator for the "exit" condition block. + ExitConditionBlock->setTerminator(S); + + // The last statement in the block should be the ObjCForCollectionStmt, which + // performs the actual binding to 'element' and determines if there are any + // more items in the collection. + appendStmt(ExitConditionBlock, S); + Block = ExitConditionBlock; + + // Walk the 'element' expression to see if there are any side-effects. We + // generate new blocks as necesary. We DON'T add the statement by default to + // the CFG unless it contains control-flow. + EntryConditionBlock = Visit(S->getElement(), AddStmtChoice::NotAlwaysAdd); + if (Block) { + if (badCFG) + return 0; + Block = 0; + } + + // The condition block is the implicit successor for the loop body as well as + // any code above the loop. + Succ = EntryConditionBlock; + + // Now create the true branch. + { + // Save the current values for Succ, continue and break targets. + SaveAndRestore<CFGBlock*> save_Succ(Succ); + SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), + save_break(BreakJumpTarget); + + BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); + ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos); + + CFGBlock* BodyBlock = addStmt(S->getBody()); + + if (!BodyBlock) + BodyBlock = EntryConditionBlock; // can happen for "for (X in Y) ;" + else if (Block) { + if (badCFG) + return 0; + } + + // This new body block is a successor to our "exit" condition block. + addSuccessor(ExitConditionBlock, BodyBlock); + } + + // Link up the condition block with the code that follows the loop. + // (the false branch). + addSuccessor(ExitConditionBlock, LoopSuccessor); + + // Now create a prologue block to contain the collection expression. + Block = createBlock(); + return addStmt(S->getCollection()); +} + +CFGBlock* CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt* S) { + // FIXME: Add locking 'primitives' to CFG for @synchronized. + + // Inline the body. + CFGBlock *SyncBlock = addStmt(S->getSynchBody()); + + // The sync body starts its own basic block. This makes it a little easier + // for diagnostic clients. + if (SyncBlock) { + if (badCFG) + return 0; + + Block = 0; + Succ = SyncBlock; + } + + // Add the @synchronized to the CFG. + autoCreateBlock(); + appendStmt(Block, S, AddStmtChoice::AlwaysAdd); + + // Inline the sync expression. + return addStmt(S->getSynchExpr()); +} + +CFGBlock* CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt* S) { + // FIXME + return NYS(); +} + +CFGBlock* CFGBuilder::VisitWhileStmt(WhileStmt* W) { + CFGBlock* LoopSuccessor = NULL; + + // Save local scope position because in case of condition variable ScopePos + // won't be restored when traversing AST. + SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); + + // Create local scope for possible condition variable. + // Store scope position for continue statement. + LocalScope::const_iterator LoopBeginScopePos = ScopePos; + if (VarDecl* VD = W->getConditionVariable()) { + addLocalScopeForVarDecl(VD); + addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W); + } + + // "while" is a control-flow statement. Thus we stop processing the current + // block. + if (Block) { + if (badCFG) + return 0; + LoopSuccessor = Block; + } else + LoopSuccessor = Succ; + + // Because of short-circuit evaluation, the condition of the loop can span + // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that + // evaluate the condition. + CFGBlock* ExitConditionBlock = createBlock(false); + CFGBlock* EntryConditionBlock = ExitConditionBlock; + + // Set the terminator for the "exit" condition block. + ExitConditionBlock->setTerminator(W); + + // Now add the actual condition to the condition block. Because the condition + // itself may contain control-flow, new blocks may be created. Thus we update + // "Succ" after adding the condition. + if (Stmt* C = W->getCond()) { + Block = ExitConditionBlock; + EntryConditionBlock = addStmt(C); + // The condition might finish the current 'Block'. + Block = EntryConditionBlock; + + // If this block contains a condition variable, add both the condition + // variable and initializer to the CFG. + if (VarDecl *VD = W->getConditionVariable()) { + if (Expr *Init = VD->getInit()) { + autoCreateBlock(); + appendStmt(Block, W, AddStmtChoice::AlwaysAdd); + EntryConditionBlock = addStmt(Init); + assert(Block == EntryConditionBlock); + } + } + + if (Block) { + if (badCFG) + return 0; + } + } + + // The condition block is the implicit successor for the loop body as well as + // any code above the loop. + Succ = EntryConditionBlock; + + // See if this is a known constant. + const TryResult& KnownVal = tryEvaluateBool(W->getCond()); + + // Process the loop body. + { + assert(W->getBody()); + + // Save the current values for Block, Succ, and continue and break targets + SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); + SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), + save_break(BreakJumpTarget); + + // Create an empty block to represent the transition block for looping back + // to the head of the loop. + Block = 0; + assert(Succ == EntryConditionBlock); + Succ = createBlock(); + Succ->setLoopTarget(W); + ContinueJumpTarget = JumpTarget(Succ, LoopBeginScopePos); + + // All breaks should go to the code following the loop. + BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); + + // NULL out Block to force lazy instantiation of blocks for the body. + Block = NULL; + + // Loop body should end with destructor of Condition variable (if any). + addAutomaticObjDtors(ScopePos, LoopBeginScopePos, W); + + // If body is not a compound statement create implicit scope + // and add destructors. + if (!isa<CompoundStmt>(W->getBody())) + addLocalScopeAndDtors(W->getBody()); + + // Create the body. The returned block is the entry to the loop body. + CFGBlock* BodyBlock = addStmt(W->getBody()); + + if (!BodyBlock) + BodyBlock = ContinueJumpTarget.block; // can happen for "while(...) ;" + else if (Block) { + if (badCFG) + return 0; + } + + // Add the loop body entry as a successor to the condition. + addSuccessor(ExitConditionBlock, KnownVal.isFalse() ? NULL : BodyBlock); + } + + // Link up the condition block with the code that follows the loop. (the + // false branch). + addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); + + // There can be no more statements in the condition block since we loop back + // to this block. NULL out Block to force lazy creation of another block. + Block = NULL; + + // Return the condition block, which is the dominating block for the loop. + Succ = EntryConditionBlock; + return EntryConditionBlock; +} + + +CFGBlock *CFGBuilder::VisitObjCAtCatchStmt(ObjCAtCatchStmt* S) { + // FIXME: For now we pretend that @catch and the code it contains does not + // exit. + return Block; +} + +CFGBlock* CFGBuilder::VisitObjCAtThrowStmt(ObjCAtThrowStmt* S) { + // FIXME: This isn't complete. We basically treat @throw like a return + // statement. + + // If we were in the middle of a block we stop processing that block. + if (badCFG) + return 0; + + // Create the new block. + Block = createBlock(false); + + // The Exit block is the only successor. + addSuccessor(Block, &cfg->getExit()); + + // Add the statement to the block. This may create new blocks if S contains + // control-flow (short-circuit operations). + return VisitStmt(S, AddStmtChoice::AlwaysAdd); +} + +CFGBlock* CFGBuilder::VisitCXXThrowExpr(CXXThrowExpr* T) { + // If we were in the middle of a block we stop processing that block. + if (badCFG) + return 0; + + // Create the new block. + Block = createBlock(false); + + if (TryTerminatedBlock) + // The current try statement is the only successor. + addSuccessor(Block, TryTerminatedBlock); + else + // otherwise the Exit block is the only successor. + addSuccessor(Block, &cfg->getExit()); + + // Add the statement to the block. This may create new blocks if S contains + // control-flow (short-circuit operations). + return VisitStmt(T, AddStmtChoice::AlwaysAdd); +} + +CFGBlock *CFGBuilder::VisitDoStmt(DoStmt* D) { + CFGBlock* LoopSuccessor = NULL; + + // "do...while" is a control-flow statement. Thus we stop processing the + // current block. + if (Block) { + if (badCFG) + return 0; + LoopSuccessor = Block; + } else + LoopSuccessor = Succ; + + // Because of short-circuit evaluation, the condition of the loop can span + // multiple basic blocks. Thus we need the "Entry" and "Exit" blocks that + // evaluate the condition. + CFGBlock* ExitConditionBlock = createBlock(false); + CFGBlock* EntryConditionBlock = ExitConditionBlock; + + // Set the terminator for the "exit" condition block. + ExitConditionBlock->setTerminator(D); + + // Now add the actual condition to the condition block. Because the condition + // itself may contain control-flow, new blocks may be created. + if (Stmt* C = D->getCond()) { + Block = ExitConditionBlock; + EntryConditionBlock = addStmt(C); + if (Block) { + if (badCFG) + return 0; + } + } + + // The condition block is the implicit successor for the loop body. + Succ = EntryConditionBlock; + + // See if this is a known constant. + const TryResult &KnownVal = tryEvaluateBool(D->getCond()); + + // Process the loop body. + CFGBlock* BodyBlock = NULL; + { + assert(D->getBody()); + + // Save the current values for Block, Succ, and continue and break targets + SaveAndRestore<CFGBlock*> save_Block(Block), save_Succ(Succ); + SaveAndRestore<JumpTarget> save_continue(ContinueJumpTarget), + save_break(BreakJumpTarget); + + // All continues within this loop should go to the condition block + ContinueJumpTarget = JumpTarget(EntryConditionBlock, ScopePos); + + // All breaks should go to the code following the loop. + BreakJumpTarget = JumpTarget(LoopSuccessor, ScopePos); + + // NULL out Block to force lazy instantiation of blocks for the body. + Block = NULL; + + // If body is not a compound statement create implicit scope + // and add destructors. + if (!isa<CompoundStmt>(D->getBody())) + addLocalScopeAndDtors(D->getBody()); + + // Create the body. The returned block is the entry to the loop body. + BodyBlock = addStmt(D->getBody()); + + if (!BodyBlock) + BodyBlock = EntryConditionBlock; // can happen for "do ; while(...)" + else if (Block) { + if (badCFG) + return 0; + } + + if (!KnownVal.isFalse()) { + // Add an intermediate block between the BodyBlock and the + // ExitConditionBlock to represent the "loop back" transition. Create an + // empty block to represent the transition block for looping back to the + // head of the loop. + // FIXME: Can we do this more efficiently without adding another block? + Block = NULL; + Succ = BodyBlock; + CFGBlock *LoopBackBlock = createBlock(); + LoopBackBlock->setLoopTarget(D); + + // Add the loop body entry as a successor to the condition. + addSuccessor(ExitConditionBlock, LoopBackBlock); + } + else + addSuccessor(ExitConditionBlock, NULL); + } + + // Link up the condition block with the code that follows the loop. + // (the false branch). + addSuccessor(ExitConditionBlock, KnownVal.isTrue() ? NULL : LoopSuccessor); + + // There can be no more statements in the body block(s) since we loop back to + // the body. NULL out Block to force lazy creation of another block. + Block = NULL; + + // Return the loop body, which is the dominating block for the loop. + Succ = BodyBlock; + return BodyBlock; +} + +CFGBlock* CFGBuilder::VisitContinueStmt(ContinueStmt* C) { + // "continue" is a control-flow statement. Thus we stop processing the + // current block. + if (badCFG) + return 0; + + // Now create a new block that ends with the continue statement. + Block = createBlock(false); + Block->setTerminator(C); + + // If there is no target for the continue, then we are looking at an + // incomplete AST. This means the CFG cannot be constructed. + if (ContinueJumpTarget.block) { + addAutomaticObjDtors(ScopePos, ContinueJumpTarget.scopePosition, C); + addSuccessor(Block, ContinueJumpTarget.block); + } else + badCFG = true; + + return Block; +} + +CFGBlock *CFGBuilder::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *E, + AddStmtChoice asc) { + + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, E); + } + + // VLA types have expressions that must be evaluated. + if (E->isArgumentType()) { + for (const VariableArrayType *VA =FindVA(E->getArgumentType().getTypePtr()); + VA != 0; VA = FindVA(VA->getElementType().getTypePtr())) + addStmt(VA->getSizeExpr()); + } + + return Block; +} + +/// VisitStmtExpr - Utility method to handle (nested) statement +/// expressions (a GCC extension). +CFGBlock* CFGBuilder::VisitStmtExpr(StmtExpr *SE, AddStmtChoice asc) { + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, SE); + } + return VisitCompoundStmt(SE->getSubStmt()); +} + +CFGBlock* CFGBuilder::VisitSwitchStmt(SwitchStmt* Terminator) { + // "switch" is a control-flow statement. Thus we stop processing the current + // block. + CFGBlock* SwitchSuccessor = NULL; + + // Save local scope position because in case of condition variable ScopePos + // won't be restored when traversing AST. + SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); + + // Create local scope for possible condition variable. + // Store scope position. Add implicit destructor. + if (VarDecl* VD = Terminator->getConditionVariable()) { + LocalScope::const_iterator SwitchBeginScopePos = ScopePos; + addLocalScopeForVarDecl(VD); + addAutomaticObjDtors(ScopePos, SwitchBeginScopePos, Terminator); + } + + if (Block) { + if (badCFG) + return 0; + SwitchSuccessor = Block; + } else SwitchSuccessor = Succ; + + // Save the current "switch" context. + SaveAndRestore<CFGBlock*> save_switch(SwitchTerminatedBlock), + save_default(DefaultCaseBlock); + SaveAndRestore<JumpTarget> save_break(BreakJumpTarget); + + // Set the "default" case to be the block after the switch statement. If the + // switch statement contains a "default:", this value will be overwritten with + // the block for that code. + DefaultCaseBlock = SwitchSuccessor; + + // Create a new block that will contain the switch statement. + SwitchTerminatedBlock = createBlock(false); + + // Now process the switch body. The code after the switch is the implicit + // successor. + Succ = SwitchSuccessor; + BreakJumpTarget = JumpTarget(SwitchSuccessor, ScopePos); + + // When visiting the body, the case statements should automatically get linked + // up to the switch. We also don't keep a pointer to the body, since all + // control-flow from the switch goes to case/default statements. + assert(Terminator->getBody() && "switch must contain a non-NULL body"); + Block = NULL; + + // If body is not a compound statement create implicit scope + // and add destructors. + if (!isa<CompoundStmt>(Terminator->getBody())) + addLocalScopeAndDtors(Terminator->getBody()); + + addStmt(Terminator->getBody()); + if (Block) { + if (badCFG) + return 0; + } + + // If we have no "default:" case, the default transition is to the code + // following the switch body. + addSuccessor(SwitchTerminatedBlock, DefaultCaseBlock); + + // Add the terminator and condition in the switch block. + SwitchTerminatedBlock->setTerminator(Terminator); + assert(Terminator->getCond() && "switch condition must be non-NULL"); + Block = SwitchTerminatedBlock; + Block = addStmt(Terminator->getCond()); + + // Finally, if the SwitchStmt contains a condition variable, add both the + // SwitchStmt and the condition variable initialization to the CFG. + if (VarDecl *VD = Terminator->getConditionVariable()) { + if (Expr *Init = VD->getInit()) { + autoCreateBlock(); + appendStmt(Block, Terminator, AddStmtChoice::AlwaysAdd); + addStmt(Init); + } + } + + return Block; +} + +CFGBlock* CFGBuilder::VisitCaseStmt(CaseStmt* CS) { + // CaseStmts are essentially labels, so they are the first statement in a + // block. + CFGBlock *TopBlock = 0, *LastBlock = 0; + + if (Stmt *Sub = CS->getSubStmt()) { + // For deeply nested chains of CaseStmts, instead of doing a recursion + // (which can blow out the stack), manually unroll and create blocks + // along the way. + while (isa<CaseStmt>(Sub)) { + CFGBlock *currentBlock = createBlock(false); + currentBlock->setLabel(CS); + + if (TopBlock) + addSuccessor(LastBlock, currentBlock); + else + TopBlock = currentBlock; + + addSuccessor(SwitchTerminatedBlock, currentBlock); + LastBlock = currentBlock; + + CS = cast<CaseStmt>(Sub); + Sub = CS->getSubStmt(); + } + + addStmt(Sub); + } + + CFGBlock* CaseBlock = Block; + if (!CaseBlock) + CaseBlock = createBlock(); + + // Cases statements partition blocks, so this is the top of the basic block we + // were processing (the "case XXX:" is the label). + CaseBlock->setLabel(CS); + + if (badCFG) + return 0; + + // Add this block to the list of successors for the block with the switch + // statement. + assert(SwitchTerminatedBlock); + addSuccessor(SwitchTerminatedBlock, CaseBlock); + + // We set Block to NULL to allow lazy creation of a new block (if necessary) + Block = NULL; + + if (TopBlock) { + addSuccessor(LastBlock, CaseBlock); + Succ = TopBlock; + } else { + // This block is now the implicit successor of other blocks. + Succ = CaseBlock; + } + + return Succ; +} + +CFGBlock* CFGBuilder::VisitDefaultStmt(DefaultStmt* Terminator) { + if (Terminator->getSubStmt()) + addStmt(Terminator->getSubStmt()); + + DefaultCaseBlock = Block; + + if (!DefaultCaseBlock) + DefaultCaseBlock = createBlock(); + + // Default statements partition blocks, so this is the top of the basic block + // we were processing (the "default:" is the label). + DefaultCaseBlock->setLabel(Terminator); + + if (badCFG) + return 0; + + // Unlike case statements, we don't add the default block to the successors + // for the switch statement immediately. This is done when we finish + // processing the switch statement. This allows for the default case + // (including a fall-through to the code after the switch statement) to always + // be the last successor of a switch-terminated block. + + // We set Block to NULL to allow lazy creation of a new block (if necessary) + Block = NULL; + + // This block is now the implicit successor of other blocks. + Succ = DefaultCaseBlock; + + return DefaultCaseBlock; +} + +CFGBlock *CFGBuilder::VisitCXXTryStmt(CXXTryStmt *Terminator) { + // "try"/"catch" is a control-flow statement. Thus we stop processing the + // current block. + CFGBlock* TrySuccessor = NULL; + + if (Block) { + if (badCFG) + return 0; + TrySuccessor = Block; + } else TrySuccessor = Succ; + + CFGBlock *PrevTryTerminatedBlock = TryTerminatedBlock; + + // Create a new block that will contain the try statement. + CFGBlock *NewTryTerminatedBlock = createBlock(false); + // Add the terminator in the try block. + NewTryTerminatedBlock->setTerminator(Terminator); + + bool HasCatchAll = false; + for (unsigned h = 0; h <Terminator->getNumHandlers(); ++h) { + // The code after the try is the implicit successor. + Succ = TrySuccessor; + CXXCatchStmt *CS = Terminator->getHandler(h); + if (CS->getExceptionDecl() == 0) { + HasCatchAll = true; + } + Block = NULL; + CFGBlock *CatchBlock = VisitCXXCatchStmt(CS); + if (CatchBlock == 0) + return 0; + // Add this block to the list of successors for the block with the try + // statement. + addSuccessor(NewTryTerminatedBlock, CatchBlock); + } + if (!HasCatchAll) { + if (PrevTryTerminatedBlock) + addSuccessor(NewTryTerminatedBlock, PrevTryTerminatedBlock); + else + addSuccessor(NewTryTerminatedBlock, &cfg->getExit()); + } + + // The code after the try is the implicit successor. + Succ = TrySuccessor; + + // Save the current "try" context. + SaveAndRestore<CFGBlock*> save_try(TryTerminatedBlock); + TryTerminatedBlock = NewTryTerminatedBlock; + + assert(Terminator->getTryBlock() && "try must contain a non-NULL body"); + Block = NULL; + Block = addStmt(Terminator->getTryBlock()); + return Block; +} + +CFGBlock* CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt* CS) { + // CXXCatchStmt are treated like labels, so they are the first statement in a + // block. + + // Save local scope position because in case of exception variable ScopePos + // won't be restored when traversing AST. + SaveAndRestore<LocalScope::const_iterator> save_scope_pos(ScopePos); + + // Create local scope for possible exception variable. + // Store scope position. Add implicit destructor. + if (VarDecl* VD = CS->getExceptionDecl()) { + LocalScope::const_iterator BeginScopePos = ScopePos; + addLocalScopeForVarDecl(VD); + addAutomaticObjDtors(ScopePos, BeginScopePos, CS); + } + + if (CS->getHandlerBlock()) + addStmt(CS->getHandlerBlock()); + + CFGBlock* CatchBlock = Block; + if (!CatchBlock) + CatchBlock = createBlock(); + + CatchBlock->setLabel(CS); + + if (badCFG) + return 0; + + // We set Block to NULL to allow lazy creation of a new block (if necessary) + Block = NULL; + + return CatchBlock; +} + +CFGBlock *CFGBuilder::VisitExprWithCleanups(ExprWithCleanups *E, + AddStmtChoice asc) { + if (BuildOpts.AddImplicitDtors) { + // If adding implicit destructors visit the full expression for adding + // destructors of temporaries. + VisitForTemporaryDtors(E->getSubExpr()); + + // Full expression has to be added as CFGStmt so it will be sequenced + // before destructors of it's temporaries. + asc = asc.withAlwaysAdd(true); + } + return Visit(E->getSubExpr(), asc); +} + +CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E, + AddStmtChoice asc) { + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, E, asc); + + // We do not want to propagate the AlwaysAdd property. + asc = asc.withAlwaysAdd(false); + } + return Visit(E->getSubExpr(), asc); +} + +CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C, + AddStmtChoice asc) { + autoCreateBlock(); + if (!C->isElidable()) + appendStmt(Block, C, asc.withAlwaysAdd(true)); + + return VisitChildren(C); +} + +CFGBlock *CFGBuilder::VisitCXXFunctionalCastExpr(CXXFunctionalCastExpr *E, + AddStmtChoice asc) { + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, E, asc); + // We do not want to propagate the AlwaysAdd property. + asc = asc.withAlwaysAdd(false); + } + return Visit(E->getSubExpr(), asc); +} + +CFGBlock *CFGBuilder::VisitCXXTemporaryObjectExpr(CXXTemporaryObjectExpr *C, + AddStmtChoice asc) { + autoCreateBlock(); + appendStmt(Block, C, asc.withAlwaysAdd(true)); + return VisitChildren(C); +} + +CFGBlock *CFGBuilder::VisitCXXMemberCallExpr(CXXMemberCallExpr *C, + AddStmtChoice asc) { + autoCreateBlock(); + appendStmt(Block, C, asc.withAlwaysAdd(true)); + return VisitChildren(C); +} + +CFGBlock *CFGBuilder::VisitImplicitCastExpr(ImplicitCastExpr *E, + AddStmtChoice asc) { + if (asc.alwaysAdd()) { + autoCreateBlock(); + appendStmt(Block, E, asc); + } + return Visit(E->getSubExpr(), AddStmtChoice()); +} + +CFGBlock* CFGBuilder::VisitIndirectGotoStmt(IndirectGotoStmt* I) { + // Lazily create the indirect-goto dispatch block if there isn't one already. + CFGBlock* IBlock = cfg->getIndirectGotoBlock(); + + if (!IBlock) { + IBlock = createBlock(false); + cfg->setIndirectGotoBlock(IBlock); + } + + // IndirectGoto is a control-flow statement. Thus we stop processing the + // current block and create a new one. + if (badCFG) + return 0; + + Block = createBlock(false); + Block->setTerminator(I); + addSuccessor(Block, IBlock); + return addStmt(I->getTarget()); +} + +CFGBlock *CFGBuilder::VisitForTemporaryDtors(Stmt *E, bool BindToTemporary) { +tryAgain: + if (!E) { + badCFG = true; + return NULL; + } + switch (E->getStmtClass()) { + default: + return VisitChildrenForTemporaryDtors(E); + + case Stmt::BinaryOperatorClass: + return VisitBinaryOperatorForTemporaryDtors(cast<BinaryOperator>(E)); + + case Stmt::CXXBindTemporaryExprClass: + return VisitCXXBindTemporaryExprForTemporaryDtors( + cast<CXXBindTemporaryExpr>(E), BindToTemporary); + + case Stmt::BinaryConditionalOperatorClass: + case Stmt::ConditionalOperatorClass: + return VisitConditionalOperatorForTemporaryDtors( + cast<AbstractConditionalOperator>(E), BindToTemporary); + + case Stmt::ImplicitCastExprClass: + // For implicit cast we want BindToTemporary to be passed further. + E = cast<CastExpr>(E)->getSubExpr(); + goto tryAgain; + + case Stmt::ParenExprClass: + E = cast<ParenExpr>(E)->getSubExpr(); + goto tryAgain; + } +} + +CFGBlock *CFGBuilder::VisitChildrenForTemporaryDtors(Stmt *E) { + // When visiting children for destructors we want to visit them in reverse + // order. Because there's no reverse iterator for children must to reverse + // them in helper vector. + typedef llvm::SmallVector<Stmt *, 4> ChildrenVect; + ChildrenVect ChildrenRev; + for (Stmt::child_range I = E->children(); I; ++I) { + if (*I) ChildrenRev.push_back(*I); + } + + CFGBlock *B = Block; + for (ChildrenVect::reverse_iterator I = ChildrenRev.rbegin(), + L = ChildrenRev.rend(); I != L; ++I) { + if (CFGBlock *R = VisitForTemporaryDtors(*I)) + B = R; + } + return B; +} + +CFGBlock *CFGBuilder::VisitBinaryOperatorForTemporaryDtors(BinaryOperator *E) { + if (E->isLogicalOp()) { + // Destructors for temporaries in LHS expression should be called after + // those for RHS expression. Even if this will unnecessarily create a block, + // this block will be used at least by the full expression. + autoCreateBlock(); + CFGBlock *ConfluenceBlock = VisitForTemporaryDtors(E->getLHS()); + if (badCFG) + return NULL; + + Succ = ConfluenceBlock; + Block = NULL; + CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS()); + + if (RHSBlock) { + if (badCFG) + return NULL; + + // If RHS expression did produce destructors we need to connect created + // blocks to CFG in same manner as for binary operator itself. + CFGBlock *LHSBlock = createBlock(false); + LHSBlock->setTerminator(CFGTerminator(E, true)); + + // For binary operator LHS block is before RHS in list of predecessors + // of ConfluenceBlock. + std::reverse(ConfluenceBlock->pred_begin(), + ConfluenceBlock->pred_end()); + + // See if this is a known constant. + TryResult KnownVal = tryEvaluateBool(E->getLHS()); + if (KnownVal.isKnown() && (E->getOpcode() == BO_LOr)) + KnownVal.negate(); + + // Link LHSBlock with RHSBlock exactly the same way as for binary operator + // itself. + if (E->getOpcode() == BO_LOr) { + addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); + addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); + } else { + assert (E->getOpcode() == BO_LAnd); + addSuccessor(LHSBlock, KnownVal.isFalse() ? NULL : RHSBlock); + addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); + } + + Block = LHSBlock; + return LHSBlock; + } + + Block = ConfluenceBlock; + return ConfluenceBlock; + } + + if (E->isAssignmentOp()) { + // For assignment operator (=) LHS expression is visited + // before RHS expression. For destructors visit them in reverse order. + CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS()); + CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS()); + return LHSBlock ? LHSBlock : RHSBlock; + } + + // For any other binary operator RHS expression is visited before + // LHS expression (order of children). For destructors visit them in reverse + // order. + CFGBlock *LHSBlock = VisitForTemporaryDtors(E->getLHS()); + CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getRHS()); + return RHSBlock ? RHSBlock : LHSBlock; +} + +CFGBlock *CFGBuilder::VisitCXXBindTemporaryExprForTemporaryDtors( + CXXBindTemporaryExpr *E, bool BindToTemporary) { + // First add destructors for temporaries in subexpression. + CFGBlock *B = VisitForTemporaryDtors(E->getSubExpr()); + if (!BindToTemporary) { + // If lifetime of temporary is not prolonged (by assigning to constant + // reference) add destructor for it. + autoCreateBlock(); + appendTemporaryDtor(Block, E); + B = Block; + } + return B; +} + +CFGBlock *CFGBuilder::VisitConditionalOperatorForTemporaryDtors( + AbstractConditionalOperator *E, bool BindToTemporary) { + // First add destructors for condition expression. Even if this will + // unnecessarily create a block, this block will be used at least by the full + // expression. + autoCreateBlock(); + CFGBlock *ConfluenceBlock = VisitForTemporaryDtors(E->getCond()); + if (badCFG) + return NULL; + if (BinaryConditionalOperator *BCO + = dyn_cast<BinaryConditionalOperator>(E)) { + ConfluenceBlock = VisitForTemporaryDtors(BCO->getCommon()); + if (badCFG) + return NULL; + } + + // Try to add block with destructors for LHS expression. + CFGBlock *LHSBlock = NULL; + Succ = ConfluenceBlock; + Block = NULL; + LHSBlock = VisitForTemporaryDtors(E->getTrueExpr(), BindToTemporary); + if (badCFG) + return NULL; + + // Try to add block with destructors for RHS expression; + Succ = ConfluenceBlock; + Block = NULL; + CFGBlock *RHSBlock = VisitForTemporaryDtors(E->getFalseExpr(), + BindToTemporary); + if (badCFG) + return NULL; + + if (!RHSBlock && !LHSBlock) { + // If neither LHS nor RHS expression had temporaries to destroy don't create + // more blocks. + Block = ConfluenceBlock; + return Block; + } + + Block = createBlock(false); + Block->setTerminator(CFGTerminator(E, true)); + + // See if this is a known constant. + const TryResult &KnownVal = tryEvaluateBool(E->getCond()); + + if (LHSBlock) { + addSuccessor(Block, KnownVal.isFalse() ? NULL : LHSBlock); + } else if (KnownVal.isFalse()) { + addSuccessor(Block, NULL); + } else { + addSuccessor(Block, ConfluenceBlock); + std::reverse(ConfluenceBlock->pred_begin(), ConfluenceBlock->pred_end()); + } + + if (!RHSBlock) + RHSBlock = ConfluenceBlock; + addSuccessor(Block, KnownVal.isTrue() ? NULL : RHSBlock); + + return Block; +} + +} // end anonymous namespace + +/// createBlock - Constructs and adds a new CFGBlock to the CFG. The block has +/// no successors or predecessors. If this is the first block created in the +/// CFG, it is automatically set to be the Entry and Exit of the CFG. +CFGBlock* CFG::createBlock() { + bool first_block = begin() == end(); + + // Create the block. + CFGBlock *Mem = getAllocator().Allocate<CFGBlock>(); + new (Mem) CFGBlock(NumBlockIDs++, BlkBVC); + Blocks.push_back(Mem, BlkBVC); + + // If this is the first block, set it as the Entry and Exit. + if (first_block) + Entry = Exit = &back(); + + // Return the block. + return &back(); +} + +/// buildCFG - Constructs a CFG from an AST. Ownership of the returned +/// CFG is returned to the caller. +CFG* CFG::buildCFG(const Decl *D, Stmt* Statement, ASTContext *C, + BuildOptions BO) { + CFGBuilder Builder; + return Builder.buildCFG(D, Statement, C, BO); +} + +//===----------------------------------------------------------------------===// +// CFG: Queries for BlkExprs. +//===----------------------------------------------------------------------===// + +namespace { + typedef llvm::DenseMap<const Stmt*,unsigned> BlkExprMapTy; +} + +static void FindSubExprAssignments(Stmt *S, + llvm::SmallPtrSet<Expr*,50>& Set) { + if (!S) + return; + + for (Stmt::child_range I = S->children(); I; ++I) { + Stmt *child = *I; + if (!child) + continue; + + if (BinaryOperator* B = dyn_cast<BinaryOperator>(child)) + if (B->isAssignmentOp()) Set.insert(B); + + FindSubExprAssignments(child, Set); + } +} + +static BlkExprMapTy* PopulateBlkExprMap(CFG& cfg) { + BlkExprMapTy* M = new BlkExprMapTy(); + + // Look for assignments that are used as subexpressions. These are the only + // assignments that we want to *possibly* register as a block-level + // expression. Basically, if an assignment occurs both in a subexpression and + // at the block-level, it is a block-level expression. + llvm::SmallPtrSet<Expr*,50> SubExprAssignments; + + for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) + for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) + if (CFGStmt S = BI->getAs<CFGStmt>()) + FindSubExprAssignments(S, SubExprAssignments); + + for (CFG::iterator I=cfg.begin(), E=cfg.end(); I != E; ++I) { + + // Iterate over the statements again on identify the Expr* and Stmt* at the + // block-level that are block-level expressions. + + for (CFGBlock::iterator BI=(*I)->begin(), EI=(*I)->end(); BI != EI; ++BI) { + CFGStmt CS = BI->getAs<CFGStmt>(); + if (!CS.isValid()) + continue; + if (Expr* Exp = dyn_cast<Expr>(CS.getStmt())) { + + if (BinaryOperator* B = dyn_cast<BinaryOperator>(Exp)) { + // Assignment expressions that are not nested within another + // expression are really "statements" whose value is never used by + // another expression. + if (B->isAssignmentOp() && !SubExprAssignments.count(Exp)) + continue; + } else if (const StmtExpr* Terminator = dyn_cast<StmtExpr>(Exp)) { + // Special handling for statement expressions. The last statement in + // the statement expression is also a block-level expr. + const CompoundStmt* C = Terminator->getSubStmt(); + if (!C->body_empty()) { + unsigned x = M->size(); + (*M)[C->body_back()] = x; + } + } + + unsigned x = M->size(); + (*M)[Exp] = x; + } + } + + // Look at terminators. The condition is a block-level expression. + + Stmt* S = (*I)->getTerminatorCondition(); + + if (S && M->find(S) == M->end()) { + unsigned x = M->size(); + (*M)[S] = x; + } + } + + return M; +} + +CFG::BlkExprNumTy CFG::getBlkExprNum(const Stmt* S) { + assert(S != NULL); + if (!BlkExprMap) { BlkExprMap = (void*) PopulateBlkExprMap(*this); } + + BlkExprMapTy* M = reinterpret_cast<BlkExprMapTy*>(BlkExprMap); + BlkExprMapTy::iterator I = M->find(S); + return (I == M->end()) ? CFG::BlkExprNumTy() : CFG::BlkExprNumTy(I->second); +} + +unsigned CFG::getNumBlkExprs() { + if (const BlkExprMapTy* M = reinterpret_cast<const BlkExprMapTy*>(BlkExprMap)) + return M->size(); + + // We assume callers interested in the number of BlkExprs will want + // the map constructed if it doesn't already exist. + BlkExprMap = (void*) PopulateBlkExprMap(*this); + return reinterpret_cast<BlkExprMapTy*>(BlkExprMap)->size(); +} + +//===----------------------------------------------------------------------===// +// Filtered walking of the CFG. +//===----------------------------------------------------------------------===// + +bool CFGBlock::FilterEdge(const CFGBlock::FilterOptions &F, + const CFGBlock *From, const CFGBlock *To) { + + if (F.IgnoreDefaultsWithCoveredEnums) { + // If the 'To' has no label or is labeled but the label isn't a + // CaseStmt then filter this edge. + if (const SwitchStmt *S = + dyn_cast_or_null<SwitchStmt>(From->getTerminator().getStmt())) { + if (S->isAllEnumCasesCovered()) { + const Stmt *L = To->getLabel(); + if (!L || !isa<CaseStmt>(L)) + return true; + } + } + } + + return false; +} + +//===----------------------------------------------------------------------===// +// Cleanup: CFG dstor. +//===----------------------------------------------------------------------===// + +CFG::~CFG() { + delete reinterpret_cast<const BlkExprMapTy*>(BlkExprMap); +} + +//===----------------------------------------------------------------------===// +// CFG pretty printing +//===----------------------------------------------------------------------===// + +namespace { + +class StmtPrinterHelper : public PrinterHelper { + typedef llvm::DenseMap<Stmt*,std::pair<unsigned,unsigned> > StmtMapTy; + typedef llvm::DenseMap<Decl*,std::pair<unsigned,unsigned> > DeclMapTy; + StmtMapTy StmtMap; + DeclMapTy DeclMap; + signed currentBlock; + unsigned currentStmt; + const LangOptions &LangOpts; +public: + + StmtPrinterHelper(const CFG* cfg, const LangOptions &LO) + : currentBlock(0), currentStmt(0), LangOpts(LO) { + for (CFG::const_iterator I = cfg->begin(), E = cfg->end(); I != E; ++I ) { + unsigned j = 1; + for (CFGBlock::const_iterator BI = (*I)->begin(), BEnd = (*I)->end() ; + BI != BEnd; ++BI, ++j ) { + if (CFGStmt SE = BI->getAs<CFGStmt>()) { + std::pair<unsigned, unsigned> P((*I)->getBlockID(), j); + StmtMap[SE] = P; + + if (DeclStmt* DS = dyn_cast<DeclStmt>(SE.getStmt())) { + DeclMap[DS->getSingleDecl()] = P; + + } else if (IfStmt* IS = dyn_cast<IfStmt>(SE.getStmt())) { + if (VarDecl* VD = IS->getConditionVariable()) + DeclMap[VD] = P; + + } else if (ForStmt* FS = dyn_cast<ForStmt>(SE.getStmt())) { + if (VarDecl* VD = FS->getConditionVariable()) + DeclMap[VD] = P; + + } else if (WhileStmt* WS = dyn_cast<WhileStmt>(SE.getStmt())) { + if (VarDecl* VD = WS->getConditionVariable()) + DeclMap[VD] = P; + + } else if (SwitchStmt* SS = dyn_cast<SwitchStmt>(SE.getStmt())) { + if (VarDecl* VD = SS->getConditionVariable()) + DeclMap[VD] = P; + + } else if (CXXCatchStmt* CS = dyn_cast<CXXCatchStmt>(SE.getStmt())) { + if (VarDecl* VD = CS->getExceptionDecl()) + DeclMap[VD] = P; + } + } + } + } + } + + virtual ~StmtPrinterHelper() {} + + const LangOptions &getLangOpts() const { return LangOpts; } + void setBlockID(signed i) { currentBlock = i; } + void setStmtID(unsigned i) { currentStmt = i; } + + virtual bool handledStmt(Stmt* S, llvm::raw_ostream& OS) { + StmtMapTy::iterator I = StmtMap.find(S); + + if (I == StmtMap.end()) + return false; + + if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock + && I->second.second == currentStmt) { + return false; + } + + OS << "[B" << I->second.first << "." << I->second.second << "]"; + return true; + } + + bool handleDecl(Decl* D, llvm::raw_ostream& OS) { + DeclMapTy::iterator I = DeclMap.find(D); + + if (I == DeclMap.end()) + return false; + + if (currentBlock >= 0 && I->second.first == (unsigned) currentBlock + && I->second.second == currentStmt) { + return false; + } + + OS << "[B" << I->second.first << "." << I->second.second << "]"; + return true; + } +}; +} // end anonymous namespace + + +namespace { +class CFGBlockTerminatorPrint + : public StmtVisitor<CFGBlockTerminatorPrint,void> { + + llvm::raw_ostream& OS; + StmtPrinterHelper* Helper; + PrintingPolicy Policy; +public: + CFGBlockTerminatorPrint(llvm::raw_ostream& os, StmtPrinterHelper* helper, + const PrintingPolicy &Policy) + : OS(os), Helper(helper), Policy(Policy) {} + + void VisitIfStmt(IfStmt* I) { + OS << "if "; + I->getCond()->printPretty(OS,Helper,Policy); + } + + // Default case. + void VisitStmt(Stmt* Terminator) { + Terminator->printPretty(OS, Helper, Policy); + } + + void VisitForStmt(ForStmt* F) { + OS << "for (" ; + if (F->getInit()) + OS << "..."; + OS << "; "; + if (Stmt* C = F->getCond()) + C->printPretty(OS, Helper, Policy); + OS << "; "; + if (F->getInc()) + OS << "..."; + OS << ")"; + } + + void VisitWhileStmt(WhileStmt* W) { + OS << "while " ; + if (Stmt* C = W->getCond()) + C->printPretty(OS, Helper, Policy); + } + + void VisitDoStmt(DoStmt* D) { + OS << "do ... while "; + if (Stmt* C = D->getCond()) + C->printPretty(OS, Helper, Policy); + } + + void VisitSwitchStmt(SwitchStmt* Terminator) { + OS << "switch "; + Terminator->getCond()->printPretty(OS, Helper, Policy); + } + + void VisitCXXTryStmt(CXXTryStmt* CS) { + OS << "try ..."; + } + + void VisitAbstractConditionalOperator(AbstractConditionalOperator* C) { + C->getCond()->printPretty(OS, Helper, Policy); + OS << " ? ... : ..."; + } + + void VisitChooseExpr(ChooseExpr* C) { + OS << "__builtin_choose_expr( "; + C->getCond()->printPretty(OS, Helper, Policy); + OS << " )"; + } + + void VisitIndirectGotoStmt(IndirectGotoStmt* I) { + OS << "goto *"; + I->getTarget()->printPretty(OS, Helper, Policy); + } + + void VisitBinaryOperator(BinaryOperator* B) { + if (!B->isLogicalOp()) { + VisitExpr(B); + return; + } + + B->getLHS()->printPretty(OS, Helper, Policy); + + switch (B->getOpcode()) { + case BO_LOr: + OS << " || ..."; + return; + case BO_LAnd: + OS << " && ..."; + return; + default: + assert(false && "Invalid logical operator."); + } + } + + void VisitExpr(Expr* E) { + E->printPretty(OS, Helper, Policy); + } +}; +} // end anonymous namespace + +static void print_elem(llvm::raw_ostream &OS, StmtPrinterHelper* Helper, + const CFGElement &E) { + if (CFGStmt CS = E.getAs<CFGStmt>()) { + Stmt *S = CS; + + if (Helper) { + + // special printing for statement-expressions. + if (StmtExpr* SE = dyn_cast<StmtExpr>(S)) { + CompoundStmt* Sub = SE->getSubStmt(); + + if (Sub->children()) { + OS << "({ ... ; "; + Helper->handledStmt(*SE->getSubStmt()->body_rbegin(),OS); + OS << " })\n"; + return; + } + } + // special printing for comma expressions. + if (BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { + if (B->getOpcode() == BO_Comma) { + OS << "... , "; + Helper->handledStmt(B->getRHS(),OS); + OS << '\n'; + return; + } + } + } + S->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); + + if (isa<CXXOperatorCallExpr>(S)) { + OS << " (OperatorCall)"; + } else if (isa<CXXBindTemporaryExpr>(S)) { + OS << " (BindTemporary)"; + } + + // Expressions need a newline. + if (isa<Expr>(S)) + OS << '\n'; + + } else if (CFGInitializer IE = E.getAs<CFGInitializer>()) { + CXXCtorInitializer* I = IE; + if (I->isBaseInitializer()) + OS << I->getBaseClass()->getAsCXXRecordDecl()->getName(); + else OS << I->getAnyMember()->getName(); + + OS << "("; + if (Expr* IE = I->getInit()) + IE->printPretty(OS, Helper, PrintingPolicy(Helper->getLangOpts())); + OS << ")"; + + if (I->isBaseInitializer()) + OS << " (Base initializer)\n"; + else OS << " (Member initializer)\n"; + + } else if (CFGAutomaticObjDtor DE = E.getAs<CFGAutomaticObjDtor>()){ + VarDecl* VD = DE.getVarDecl(); + Helper->handleDecl(VD, OS); + + const Type* T = VD->getType().getTypePtr(); + if (const ReferenceType* RT = T->getAs<ReferenceType>()) + T = RT->getPointeeType().getTypePtr(); + else if (const Type *ET = T->getArrayElementTypeNoTypeQual()) + T = ET; + + OS << ".~" << T->getAsCXXRecordDecl()->getName().str() << "()"; + OS << " (Implicit destructor)\n"; + + } else if (CFGBaseDtor BE = E.getAs<CFGBaseDtor>()) { + const CXXBaseSpecifier *BS = BE.getBaseSpecifier(); + OS << "~" << BS->getType()->getAsCXXRecordDecl()->getName() << "()"; + OS << " (Base object destructor)\n"; + + } else if (CFGMemberDtor ME = E.getAs<CFGMemberDtor>()) { + FieldDecl *FD = ME.getFieldDecl(); + + const Type *T = FD->getType().getTypePtr(); + if (const Type *ET = T->getArrayElementTypeNoTypeQual()) + T = ET; + + OS << "this->" << FD->getName(); + OS << ".~" << T->getAsCXXRecordDecl()->getName() << "()"; + OS << " (Member object destructor)\n"; + + } else if (CFGTemporaryDtor TE = E.getAs<CFGTemporaryDtor>()) { + CXXBindTemporaryExpr *BT = TE.getBindTemporaryExpr(); + OS << "~" << BT->getType()->getAsCXXRecordDecl()->getName() << "()"; + OS << " (Temporary object destructor)\n"; + } +} + +static void print_block(llvm::raw_ostream& OS, const CFG* cfg, + const CFGBlock& B, + StmtPrinterHelper* Helper, bool print_edges) { + + if (Helper) Helper->setBlockID(B.getBlockID()); + + // Print the header. + OS << "\n [ B" << B.getBlockID(); + + if (&B == &cfg->getEntry()) + OS << " (ENTRY) ]\n"; + else if (&B == &cfg->getExit()) + OS << " (EXIT) ]\n"; + else if (&B == cfg->getIndirectGotoBlock()) + OS << " (INDIRECT GOTO DISPATCH) ]\n"; + else + OS << " ]\n"; + + // Print the label of this block. + if (Stmt* Label = const_cast<Stmt*>(B.getLabel())) { + + if (print_edges) + OS << " "; + + if (LabelStmt* L = dyn_cast<LabelStmt>(Label)) + OS << L->getName(); + else if (CaseStmt* C = dyn_cast<CaseStmt>(Label)) { + OS << "case "; + C->getLHS()->printPretty(OS, Helper, + PrintingPolicy(Helper->getLangOpts())); + if (C->getRHS()) { + OS << " ... "; + C->getRHS()->printPretty(OS, Helper, + PrintingPolicy(Helper->getLangOpts())); + } + } else if (isa<DefaultStmt>(Label)) + OS << "default"; + else if (CXXCatchStmt *CS = dyn_cast<CXXCatchStmt>(Label)) { + OS << "catch ("; + if (CS->getExceptionDecl()) + CS->getExceptionDecl()->print(OS, PrintingPolicy(Helper->getLangOpts()), + 0); + else + OS << "..."; + OS << ")"; + + } else + assert(false && "Invalid label statement in CFGBlock."); + + OS << ":\n"; + } + + // Iterate through the statements in the block and print them. + unsigned j = 1; + + for (CFGBlock::const_iterator I = B.begin(), E = B.end() ; + I != E ; ++I, ++j ) { + + // Print the statement # in the basic block and the statement itself. + if (print_edges) + OS << " "; + + OS << llvm::format("%3d", j) << ": "; + + if (Helper) + Helper->setStmtID(j); + + print_elem(OS,Helper,*I); + } + + // Print the terminator of this block. + if (B.getTerminator()) { + if (print_edges) + OS << " "; + + OS << " T: "; + + if (Helper) Helper->setBlockID(-1); + + CFGBlockTerminatorPrint TPrinter(OS, Helper, + PrintingPolicy(Helper->getLangOpts())); + TPrinter.Visit(const_cast<Stmt*>(B.getTerminator().getStmt())); + OS << '\n'; + } + + if (print_edges) { + // Print the predecessors of this block. + OS << " Predecessors (" << B.pred_size() << "):"; + unsigned i = 0; + + for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); + I != E; ++I, ++i) { + + if (i == 8 || (i-8) == 0) + OS << "\n "; + + OS << " B" << (*I)->getBlockID(); + } + + OS << '\n'; + + // Print the successors of this block. + OS << " Successors (" << B.succ_size() << "):"; + i = 0; + + for (CFGBlock::const_succ_iterator I = B.succ_begin(), E = B.succ_end(); + I != E; ++I, ++i) { + + if (i == 8 || (i-8) % 10 == 0) + OS << "\n "; + + if (*I) + OS << " B" << (*I)->getBlockID(); + else + OS << " NULL"; + } + + OS << '\n'; + } +} + + +/// dump - A simple pretty printer of a CFG that outputs to stderr. +void CFG::dump(const LangOptions &LO) const { print(llvm::errs(), LO); } + +/// print - A simple pretty printer of a CFG that outputs to an ostream. +void CFG::print(llvm::raw_ostream &OS, const LangOptions &LO) const { + StmtPrinterHelper Helper(this, LO); + + // Print the entry block. + print_block(OS, this, getEntry(), &Helper, true); + + // Iterate through the CFGBlocks and print them one by one. + for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { + // Skip the entry block, because we already printed it. + if (&(**I) == &getEntry() || &(**I) == &getExit()) + continue; + + print_block(OS, this, **I, &Helper, true); + } + + // Print the exit block. + print_block(OS, this, getExit(), &Helper, true); + OS.flush(); +} + +/// dump - A simply pretty printer of a CFGBlock that outputs to stderr. +void CFGBlock::dump(const CFG* cfg, const LangOptions &LO) const { + print(llvm::errs(), cfg, LO); +} + +/// print - A simple pretty printer of a CFGBlock that outputs to an ostream. +/// Generally this will only be called from CFG::print. +void CFGBlock::print(llvm::raw_ostream& OS, const CFG* cfg, + const LangOptions &LO) const { + StmtPrinterHelper Helper(cfg, LO); + print_block(OS, cfg, *this, &Helper, true); +} + +/// printTerminator - A simple pretty printer of the terminator of a CFGBlock. +void CFGBlock::printTerminator(llvm::raw_ostream &OS, + const LangOptions &LO) const { + CFGBlockTerminatorPrint TPrinter(OS, NULL, PrintingPolicy(LO)); + TPrinter.Visit(const_cast<Stmt*>(getTerminator().getStmt())); +} + +Stmt* CFGBlock::getTerminatorCondition() { + Stmt *Terminator = this->Terminator; + if (!Terminator) + return NULL; + + Expr* E = NULL; + + switch (Terminator->getStmtClass()) { + default: + break; + + case Stmt::ForStmtClass: + E = cast<ForStmt>(Terminator)->getCond(); + break; + + case Stmt::WhileStmtClass: + E = cast<WhileStmt>(Terminator)->getCond(); + break; + + case Stmt::DoStmtClass: + E = cast<DoStmt>(Terminator)->getCond(); + break; + + case Stmt::IfStmtClass: + E = cast<IfStmt>(Terminator)->getCond(); + break; + + case Stmt::ChooseExprClass: + E = cast<ChooseExpr>(Terminator)->getCond(); + break; + + case Stmt::IndirectGotoStmtClass: + E = cast<IndirectGotoStmt>(Terminator)->getTarget(); + break; + + case Stmt::SwitchStmtClass: + E = cast<SwitchStmt>(Terminator)->getCond(); + break; + + case Stmt::BinaryConditionalOperatorClass: + E = cast<BinaryConditionalOperator>(Terminator)->getCond(); + break; + + case Stmt::ConditionalOperatorClass: + E = cast<ConditionalOperator>(Terminator)->getCond(); + break; + + case Stmt::BinaryOperatorClass: // '&&' and '||' + E = cast<BinaryOperator>(Terminator)->getLHS(); + break; + + case Stmt::ObjCForCollectionStmtClass: + return Terminator; + } + + return E ? E->IgnoreParens() : NULL; +} + +bool CFGBlock::hasBinaryBranchTerminator() const { + const Stmt *Terminator = this->Terminator; + if (!Terminator) + return false; + + Expr* E = NULL; + + switch (Terminator->getStmtClass()) { + default: + return false; + + case Stmt::ForStmtClass: + case Stmt::WhileStmtClass: + case Stmt::DoStmtClass: + case Stmt::IfStmtClass: + case Stmt::ChooseExprClass: + case Stmt::BinaryConditionalOperatorClass: + case Stmt::ConditionalOperatorClass: + case Stmt::BinaryOperatorClass: + return true; + } + + return E ? E->IgnoreParens() : NULL; +} + + +//===----------------------------------------------------------------------===// +// CFG Graphviz Visualization +//===----------------------------------------------------------------------===// + + +#ifndef NDEBUG +static StmtPrinterHelper* GraphHelper; +#endif + +void CFG::viewCFG(const LangOptions &LO) const { +#ifndef NDEBUG + StmtPrinterHelper H(this, LO); + GraphHelper = &H; + llvm::ViewGraph(this,"CFG"); + GraphHelper = NULL; +#endif +} + +namespace llvm { +template<> +struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { + + DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} + + static std::string getNodeLabel(const CFGBlock* Node, const CFG* Graph) { + +#ifndef NDEBUG + std::string OutSStr; + llvm::raw_string_ostream Out(OutSStr); + print_block(Out,Graph, *Node, GraphHelper, false); + std::string& OutStr = Out.str(); + + if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); + + // Process string output to make it nicer... + for (unsigned i = 0; i != OutStr.length(); ++i) + if (OutStr[i] == '\n') { // Left justify + OutStr[i] = '\\'; + OutStr.insert(OutStr.begin()+i+1, 'l'); + } + + return OutStr; +#else + return ""; +#endif + } +}; +} // end namespace llvm diff --git a/contrib/llvm/tools/clang/lib/Analysis/CFGStmtMap.cpp b/contrib/llvm/tools/clang/lib/Analysis/CFGStmtMap.cpp new file mode 100644 index 0000000..3a030f9 --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/CFGStmtMap.cpp @@ -0,0 +1,91 @@ +//===--- CFGStmtMap.h - Map from Stmt* to CFGBlock* -----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the CFGStmtMap class, which defines a mapping from +// Stmt* to CFGBlock* +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/DenseMap.h" +#include "clang/AST/ParentMap.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/CFGStmtMap.h" + +using namespace clang; + +typedef llvm::DenseMap<Stmt*,CFGBlock*> SMap; +static SMap *AsMap(void *m) { return (SMap*) m; } + +CFGStmtMap::~CFGStmtMap() { delete AsMap(M); } + +CFGBlock *CFGStmtMap::getBlock(Stmt *S) { + SMap *SM = AsMap(M); + Stmt *X = S; + + // If 'S' isn't in the map, walk the ParentMap to see if one of its ancestors + // is in the map. + while (X) { + SMap::iterator I = SM->find(X); + if (I != SM->end()) { + CFGBlock *B = I->second; + // Memoize this lookup. + if (X != S) + (*SM)[X] = B; + return B; + } + + X = PM->getParentIgnoreParens(X); + } + + return 0; +} + +static void Accumulate(SMap &SM, CFGBlock *B) { + // First walk the block-level expressions. + for (CFGBlock::iterator I = B->begin(), E = B->end(); I != E; ++I) { + const CFGElement &CE = *I; + CFGStmt CS = CE.getAs<CFGStmt>(); + if (!CS.isValid()) + continue; + + CFGBlock *&Entry = SM[CS]; + // If 'Entry' is already initialized (e.g., a terminator was already), + // skip. + if (Entry) + continue; + + Entry = B; + + } + + // Look at the label of the block. + if (Stmt *Label = B->getLabel()) + SM[Label] = B; + + // Finally, look at the terminator. If the terminator was already added + // because it is a block-level expression in another block, overwrite + // that mapping. + if (Stmt *Term = B->getTerminator()) + SM[Term] = B; +} + +CFGStmtMap *CFGStmtMap::Build(CFG *C, ParentMap *PM) { + if (!C || !PM) + return 0; + + SMap *SM = new SMap(); + + // Walk all blocks, accumulating the block-level expressions, labels, + // and terminators. + for (CFG::iterator I = C->begin(), E = C->end(); I != E; ++I) + Accumulate(*SM, *I); + + return new CFGStmtMap(PM, SM); +} + diff --git a/contrib/llvm/tools/clang/lib/Analysis/CocoaConventions.cpp b/contrib/llvm/tools/clang/lib/Analysis/CocoaConventions.cpp new file mode 100644 index 0000000..22b6c1a --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/CocoaConventions.cpp @@ -0,0 +1,180 @@ +//===- CocoaConventions.h - Special handling of Cocoa conventions -*- C++ -*--// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/DomainSpecific/CocoaConventions.h" +#include "clang/AST/Type.h" +#include "clang/AST/Decl.h" +#include "clang/AST/DeclObjC.h" +#include "llvm/ADT/StringExtras.h" + +using namespace clang; +using namespace ento; + +using llvm::StringRef; + +// The "fundamental rule" for naming conventions of methods: +// (url broken into two lines) +// http://developer.apple.com/documentation/Cocoa/Conceptual/ +// MemoryMgmt/Tasks/MemoryManagementRules.html +// +// "You take ownership of an object if you create it using a method whose name +// begins with "alloc" or "new" or contains "copy" (for example, alloc, +// newObject, or mutableCopy), or if you send it a retain message. You are +// responsible for relinquishing ownership of objects you own using release +// or autorelease. Any other time you receive an object, you must +// not release it." +// + +static bool isWordEnd(char ch, char prev, char next) { + return ch == '\0' + || (islower(prev) && isupper(ch)) // xxxC + || (isupper(prev) && isupper(ch) && islower(next)) // XXCreate + || !isalpha(ch); +} + +static const char* parseWord(const char* s) { + char ch = *s, prev = '\0'; + assert(ch != '\0'); + char next = *(s+1); + while (!isWordEnd(ch, prev, next)) { + prev = ch; + ch = next; + next = *((++s)+1); + } + return s; +} + +cocoa::NamingConvention cocoa::deriveNamingConvention(Selector S, + bool ignorePrefix) { + IdentifierInfo *II = S.getIdentifierInfoForSlot(0); + + if (!II) + return NoConvention; + + const char *s = II->getNameStart(); + + const char *orig = s; + // A method/function name may contain a prefix. We don't know it is there, + // however, until we encounter the first '_'. + while (*s != '\0') { + // Skip '_', numbers, ':', etc. + if (*s == '_' || !isalpha(*s)) { + ++s; + continue; + } + break; + } + + if (!ignorePrefix && s != orig) + return NoConvention; + + // Parse the first word, and look for specific keywords. + const char *wordEnd = parseWord(s); + assert(wordEnd > s); + unsigned len = wordEnd - s; + + switch (len) { + default: + return NoConvention; + case 3: + // Methods starting with 'new' follow the create rule. + return (memcmp(s, "new", 3) == 0) ? CreateRule : NoConvention; + case 4: + // Methods starting with 'copy' follow the create rule. + if (memcmp(s, "copy", 4) == 0) + return CreateRule; + // Methods starting with 'init' follow the init rule. + if (memcmp(s, "init", 4) == 0) + return InitRule; + return NoConvention; + case 5: + return (memcmp(s, "alloc", 5) == 0) ? CreateRule : NoConvention; + case 7: + // Methods starting with 'mutableCopy' follow the create rule. + if (memcmp(s, "mutable", 7) == 0) { + // Look at the next word to see if it is "Copy". + s = wordEnd; + if (*s != '\0') { + wordEnd = parseWord(s); + len = wordEnd - s; + if (len == 4 && memcmp(s, "Copy", 4) == 0) + return CreateRule; + } + } + return NoConvention; + } +} + +bool cocoa::isRefType(QualType RetTy, llvm::StringRef Prefix, + llvm::StringRef Name) { + // Recursively walk the typedef stack, allowing typedefs of reference types. + while (const TypedefType *TD = dyn_cast<TypedefType>(RetTy.getTypePtr())) { + llvm::StringRef TDName = TD->getDecl()->getIdentifier()->getName(); + if (TDName.startswith(Prefix) && TDName.endswith("Ref")) + return true; + + RetTy = TD->getDecl()->getUnderlyingType(); + } + + if (Name.empty()) + return false; + + // Is the type void*? + const PointerType* PT = RetTy->getAs<PointerType>(); + if (!(PT->getPointeeType().getUnqualifiedType()->isVoidType())) + return false; + + // Does the name start with the prefix? + return Name.startswith(Prefix); +} + +bool cocoa::isCFObjectRef(QualType T) { + return isRefType(T, "CF") || // Core Foundation. + isRefType(T, "CG") || // Core Graphics. + isRefType(T, "DADisk") || // Disk Arbitration API. + isRefType(T, "DADissenter") || + isRefType(T, "DASessionRef"); +} + + +bool cocoa::isCocoaObjectRef(QualType Ty) { + if (!Ty->isObjCObjectPointerType()) + return false; + + const ObjCObjectPointerType *PT = Ty->getAs<ObjCObjectPointerType>(); + + // Can be true for objects with the 'NSObject' attribute. + if (!PT) + return true; + + // We assume that id<..>, id, Class, and Class<..> all represent tracked + // objects. + if (PT->isObjCIdType() || PT->isObjCQualifiedIdType() || + PT->isObjCClassType() || PT->isObjCQualifiedClassType()) + return true; + + // Does the interface subclass NSObject? + // FIXME: We can memoize here if this gets too expensive. + const ObjCInterfaceDecl *ID = PT->getInterfaceDecl(); + + // Assume that anything declared with a forward declaration and no + // @interface subclasses NSObject. + if (ID->isForwardDecl()) + return true; + + for ( ; ID ; ID = ID->getSuperClass()) + if (ID->getIdentifier()->getName() == "NSObject") + return true; + + return false; +} diff --git a/contrib/llvm/tools/clang/lib/Analysis/FormatString.cpp b/contrib/llvm/tools/clang/lib/Analysis/FormatString.cpp new file mode 100644 index 0000000..a6d6108 --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/FormatString.cpp @@ -0,0 +1,476 @@ +// FormatString.cpp - Common stuff for handling printf/scanf formats -*- C++ -*- +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Shared details for processing format strings of printf and scanf +// (and friends). +// +//===----------------------------------------------------------------------===// + +#include "FormatStringParsing.h" + +using clang::analyze_format_string::ArgTypeResult; +using clang::analyze_format_string::FormatStringHandler; +using clang::analyze_format_string::FormatSpecifier; +using clang::analyze_format_string::LengthModifier; +using clang::analyze_format_string::OptionalAmount; +using clang::analyze_format_string::PositionContext; +using clang::analyze_format_string::ConversionSpecifier; +using namespace clang; + +// Key function to FormatStringHandler. +FormatStringHandler::~FormatStringHandler() {} + +//===----------------------------------------------------------------------===// +// Functions for parsing format strings components in both printf and +// scanf format strings. +//===----------------------------------------------------------------------===// + +OptionalAmount +clang::analyze_format_string::ParseAmount(const char *&Beg, const char *E) { + const char *I = Beg; + UpdateOnReturn <const char*> UpdateBeg(Beg, I); + + unsigned accumulator = 0; + bool hasDigits = false; + + for ( ; I != E; ++I) { + char c = *I; + if (c >= '0' && c <= '9') { + hasDigits = true; + accumulator = (accumulator * 10) + (c - '0'); + continue; + } + + if (hasDigits) + return OptionalAmount(OptionalAmount::Constant, accumulator, Beg, I - Beg, + false); + + break; + } + + return OptionalAmount(); +} + +OptionalAmount +clang::analyze_format_string::ParseNonPositionAmount(const char *&Beg, + const char *E, + unsigned &argIndex) { + if (*Beg == '*') { + ++Beg; + return OptionalAmount(OptionalAmount::Arg, argIndex++, Beg, 0, false); + } + + return ParseAmount(Beg, E); +} + +OptionalAmount +clang::analyze_format_string::ParsePositionAmount(FormatStringHandler &H, + const char *Start, + const char *&Beg, + const char *E, + PositionContext p) { + if (*Beg == '*') { + const char *I = Beg + 1; + const OptionalAmount &Amt = ParseAmount(I, E); + + if (Amt.getHowSpecified() == OptionalAmount::NotSpecified) { + H.HandleInvalidPosition(Beg, I - Beg, p); + return OptionalAmount(false); + } + + if (I == E) { + // No more characters left? + H.HandleIncompleteSpecifier(Start, E - Start); + return OptionalAmount(false); + } + + assert(Amt.getHowSpecified() == OptionalAmount::Constant); + + if (*I == '$') { + // Handle positional arguments + + // Special case: '*0$', since this is an easy mistake. + if (Amt.getConstantAmount() == 0) { + H.HandleZeroPosition(Beg, I - Beg + 1); + return OptionalAmount(false); + } + + const char *Tmp = Beg; + Beg = ++I; + + return OptionalAmount(OptionalAmount::Arg, Amt.getConstantAmount() - 1, + Tmp, 0, true); + } + + H.HandleInvalidPosition(Beg, I - Beg, p); + return OptionalAmount(false); + } + + return ParseAmount(Beg, E); +} + + +bool +clang::analyze_format_string::ParseFieldWidth(FormatStringHandler &H, + FormatSpecifier &CS, + const char *Start, + const char *&Beg, const char *E, + unsigned *argIndex) { + // FIXME: Support negative field widths. + if (argIndex) { + CS.setFieldWidth(ParseNonPositionAmount(Beg, E, *argIndex)); + } + else { + const OptionalAmount Amt = + ParsePositionAmount(H, Start, Beg, E, + analyze_format_string::FieldWidthPos); + + if (Amt.isInvalid()) + return true; + CS.setFieldWidth(Amt); + } + return false; +} + +bool +clang::analyze_format_string::ParseArgPosition(FormatStringHandler &H, + FormatSpecifier &FS, + const char *Start, + const char *&Beg, + const char *E) { + const char *I = Beg; + + const OptionalAmount &Amt = ParseAmount(I, E); + + if (I == E) { + // No more characters left? + H.HandleIncompleteSpecifier(Start, E - Start); + return true; + } + + if (Amt.getHowSpecified() == OptionalAmount::Constant && *(I++) == '$') { + // Special case: '%0$', since this is an easy mistake. + if (Amt.getConstantAmount() == 0) { + H.HandleZeroPosition(Start, I - Start); + return true; + } + + FS.setArgIndex(Amt.getConstantAmount() - 1); + FS.setUsesPositionalArg(); + // Update the caller's pointer if we decided to consume + // these characters. + Beg = I; + return false; + } + + return false; +} + +bool +clang::analyze_format_string::ParseLengthModifier(FormatSpecifier &FS, + const char *&I, + const char *E) { + LengthModifier::Kind lmKind = LengthModifier::None; + const char *lmPosition = I; + switch (*I) { + default: + return false; + case 'h': + ++I; + lmKind = (I != E && *I == 'h') ? + ++I, LengthModifier::AsChar : LengthModifier::AsShort; + break; + case 'l': + ++I; + lmKind = (I != E && *I == 'l') ? + ++I, LengthModifier::AsLongLong : LengthModifier::AsLong; + break; + case 'j': lmKind = LengthModifier::AsIntMax; ++I; break; + case 'z': lmKind = LengthModifier::AsSizeT; ++I; break; + case 't': lmKind = LengthModifier::AsPtrDiff; ++I; break; + case 'L': lmKind = LengthModifier::AsLongDouble; ++I; break; + case 'q': lmKind = LengthModifier::AsLongLong; ++I; break; + } + LengthModifier lm(lmPosition, lmKind); + FS.setLengthModifier(lm); + return true; +} + +//===----------------------------------------------------------------------===// +// Methods on ArgTypeResult. +//===----------------------------------------------------------------------===// + +bool ArgTypeResult::matchesType(ASTContext &C, QualType argTy) const { + switch (K) { + case InvalidTy: + assert(false && "ArgTypeResult must be valid"); + return true; + + case UnknownTy: + return true; + + case SpecificTy: { + argTy = C.getCanonicalType(argTy).getUnqualifiedType(); + if (T == argTy) + return true; + if (const BuiltinType *BT = argTy->getAs<BuiltinType>()) + switch (BT->getKind()) { + default: + break; + case BuiltinType::Char_S: + case BuiltinType::SChar: + return T == C.UnsignedCharTy; + case BuiltinType::Char_U: + case BuiltinType::UChar: + return T == C.SignedCharTy; + case BuiltinType::Short: + return T == C.UnsignedShortTy; + case BuiltinType::UShort: + return T == C.ShortTy; + case BuiltinType::Int: + return T == C.UnsignedIntTy; + case BuiltinType::UInt: + return T == C.IntTy; + case BuiltinType::Long: + return T == C.UnsignedLongTy; + case BuiltinType::ULong: + return T == C.LongTy; + case BuiltinType::LongLong: + return T == C.UnsignedLongLongTy; + case BuiltinType::ULongLong: + return T == C.LongLongTy; + } + return false; + } + + case CStrTy: { + const PointerType *PT = argTy->getAs<PointerType>(); + if (!PT) + return false; + QualType pointeeTy = PT->getPointeeType(); + if (const BuiltinType *BT = pointeeTy->getAs<BuiltinType>()) + switch (BT->getKind()) { + case BuiltinType::Void: + case BuiltinType::Char_U: + case BuiltinType::UChar: + case BuiltinType::Char_S: + case BuiltinType::SChar: + return true; + default: + break; + } + + return false; + } + + case WCStrTy: { + const PointerType *PT = argTy->getAs<PointerType>(); + if (!PT) + return false; + QualType pointeeTy = + C.getCanonicalType(PT->getPointeeType()).getUnqualifiedType(); + return pointeeTy == C.getWCharType(); + } + + case WIntTy: { + // Instead of doing a lookup for the definition of 'wint_t' (which + // is defined by the system headers) instead see if wchar_t and + // the argument type promote to the same type. + QualType PromoWChar = + C.getWCharType()->isPromotableIntegerType() + ? C.getPromotedIntegerType(C.getWCharType()) : C.getWCharType(); + QualType PromoArg = + argTy->isPromotableIntegerType() + ? C.getPromotedIntegerType(argTy) : argTy; + + PromoWChar = C.getCanonicalType(PromoWChar).getUnqualifiedType(); + PromoArg = C.getCanonicalType(PromoArg).getUnqualifiedType(); + + return PromoWChar == PromoArg; + } + + case CPointerTy: + return argTy->isPointerType() || argTy->isObjCObjectPointerType() || + argTy->isNullPtrType(); + + case ObjCPointerTy: + return argTy->getAs<ObjCObjectPointerType>() != NULL; + } + + // FIXME: Should be unreachable, but Clang is currently emitting + // a warning. + return false; +} + +QualType ArgTypeResult::getRepresentativeType(ASTContext &C) const { + switch (K) { + case InvalidTy: + assert(false && "No representative type for Invalid ArgTypeResult"); + // Fall-through. + case UnknownTy: + return QualType(); + case SpecificTy: + return T; + case CStrTy: + return C.getPointerType(C.CharTy); + case WCStrTy: + return C.getPointerType(C.getWCharType()); + case ObjCPointerTy: + return C.ObjCBuiltinIdTy; + case CPointerTy: + return C.VoidPtrTy; + case WIntTy: { + QualType WC = C.getWCharType(); + return WC->isPromotableIntegerType() ? C.getPromotedIntegerType(WC) : WC; + } + } + + // FIXME: Should be unreachable, but Clang is currently emitting + // a warning. + return QualType(); +} + +//===----------------------------------------------------------------------===// +// Methods on OptionalAmount. +//===----------------------------------------------------------------------===// + +ArgTypeResult +analyze_format_string::OptionalAmount::getArgType(ASTContext &Ctx) const { + return Ctx.IntTy; +} + +//===----------------------------------------------------------------------===// +// Methods on LengthModifier. +//===----------------------------------------------------------------------===// + +const char * +analyze_format_string::LengthModifier::toString() const { + switch (kind) { + case AsChar: + return "hh"; + case AsShort: + return "h"; + case AsLong: // or AsWideChar + return "l"; + case AsLongLong: + return "ll"; + case AsIntMax: + return "j"; + case AsSizeT: + return "z"; + case AsPtrDiff: + return "t"; + case AsLongDouble: + return "L"; + case None: + return ""; + } + return NULL; +} + +//===----------------------------------------------------------------------===// +// Methods on OptionalAmount. +//===----------------------------------------------------------------------===// + +void OptionalAmount::toString(llvm::raw_ostream &os) const { + switch (hs) { + case Invalid: + case NotSpecified: + return; + case Arg: + if (UsesDotPrefix) + os << "."; + if (usesPositionalArg()) + os << "*" << getPositionalArgIndex() << "$"; + else + os << "*"; + break; + case Constant: + if (UsesDotPrefix) + os << "."; + os << amt; + break; + } +} + +//===----------------------------------------------------------------------===// +// Methods on ConversionSpecifier. +//===----------------------------------------------------------------------===// + +bool FormatSpecifier::hasValidLengthModifier() const { + switch (LM.getKind()) { + case LengthModifier::None: + return true; + + // Handle most integer flags + case LengthModifier::AsChar: + case LengthModifier::AsShort: + case LengthModifier::AsLongLong: + case LengthModifier::AsIntMax: + case LengthModifier::AsSizeT: + case LengthModifier::AsPtrDiff: + switch (CS.getKind()) { + case ConversionSpecifier::dArg: + case ConversionSpecifier::iArg: + case ConversionSpecifier::oArg: + case ConversionSpecifier::uArg: + case ConversionSpecifier::xArg: + case ConversionSpecifier::XArg: + case ConversionSpecifier::nArg: + case ConversionSpecifier::rArg: + return true; + default: + return false; + } + + // Handle 'l' flag + case LengthModifier::AsLong: + switch (CS.getKind()) { + case ConversionSpecifier::dArg: + case ConversionSpecifier::iArg: + case ConversionSpecifier::oArg: + case ConversionSpecifier::uArg: + case ConversionSpecifier::xArg: + case ConversionSpecifier::XArg: + case ConversionSpecifier::aArg: + case ConversionSpecifier::AArg: + case ConversionSpecifier::fArg: + case ConversionSpecifier::FArg: + case ConversionSpecifier::eArg: + case ConversionSpecifier::EArg: + case ConversionSpecifier::gArg: + case ConversionSpecifier::GArg: + case ConversionSpecifier::nArg: + case ConversionSpecifier::cArg: + case ConversionSpecifier::sArg: + case ConversionSpecifier::rArg: + return true; + default: + return false; + } + + case LengthModifier::AsLongDouble: + switch (CS.getKind()) { + case ConversionSpecifier::aArg: + case ConversionSpecifier::AArg: + case ConversionSpecifier::fArg: + case ConversionSpecifier::FArg: + case ConversionSpecifier::eArg: + case ConversionSpecifier::EArg: + case ConversionSpecifier::gArg: + case ConversionSpecifier::GArg: + return true; + default: + return false; + } + } + return false; +} + + diff --git a/contrib/llvm/tools/clang/lib/Analysis/FormatStringParsing.h b/contrib/llvm/tools/clang/lib/Analysis/FormatStringParsing.h new file mode 100644 index 0000000..607e99c --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/FormatStringParsing.h @@ -0,0 +1,72 @@ +#ifndef LLVM_CLANG_FORMAT_PARSING_H +#define LLVM_CLANG_FORMAT_PARSING_H + +#include "clang/Analysis/Analyses/FormatString.h" +#include "clang/AST/ASTContext.h" +#include "clang/AST/Type.h" +#include "llvm/Support/raw_ostream.h" + +namespace clang { + +template <typename T> +class UpdateOnReturn { + T &ValueToUpdate; + const T &ValueToCopy; +public: + UpdateOnReturn(T &valueToUpdate, const T &valueToCopy) + : ValueToUpdate(valueToUpdate), ValueToCopy(valueToCopy) {} + + ~UpdateOnReturn() { + ValueToUpdate = ValueToCopy; + } +}; + +namespace analyze_format_string { + +OptionalAmount ParseAmount(const char *&Beg, const char *E); +OptionalAmount ParseNonPositionAmount(const char *&Beg, const char *E, + unsigned &argIndex); + +OptionalAmount ParsePositionAmount(FormatStringHandler &H, + const char *Start, const char *&Beg, + const char *E, PositionContext p); + +bool ParseFieldWidth(FormatStringHandler &H, + FormatSpecifier &CS, + const char *Start, const char *&Beg, const char *E, + unsigned *argIndex); + +bool ParseArgPosition(FormatStringHandler &H, + FormatSpecifier &CS, const char *Start, + const char *&Beg, const char *E); + +/// Returns true if a LengthModifier was parsed and installed in the +/// FormatSpecifier& argument, and false otherwise. +bool ParseLengthModifier(FormatSpecifier &FS, const char *&Beg, const char *E); + +template <typename T> class SpecifierResult { + T FS; + const char *Start; + bool Stop; +public: + SpecifierResult(bool stop = false) + : Start(0), Stop(stop) {} + SpecifierResult(const char *start, + const T &fs) + : FS(fs), Start(start), Stop(false) {} + + const char *getStart() const { return Start; } + bool shouldStop() const { return Stop; } + bool hasValue() const { return Start != 0; } + const T &getValue() const { + assert(hasValue()); + return FS; + } + const T &getValue() { return FS; } +}; + +} // end analyze_format_string namespace +} // end clang namespace + +#endif + diff --git a/contrib/llvm/tools/clang/lib/Analysis/LiveVariables.cpp b/contrib/llvm/tools/clang/lib/Analysis/LiveVariables.cpp new file mode 100644 index 0000000..303dc0f --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/LiveVariables.cpp @@ -0,0 +1,392 @@ +//=- LiveVariables.cpp - Live Variable Analysis for Source CFGs -*- C++ --*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements Live Variables analysis for source-level CFGs. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Analyses/LiveVariables.h" +#include "clang/Basic/SourceManager.h" +#include "clang/AST/ASTContext.h" +#include "clang/AST/Expr.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" +#include "clang/Analysis/FlowSensitive/DataflowSolver.h" +#include "clang/Analysis/Support/SaveAndRestore.h" +#include "clang/Analysis/AnalysisContext.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/Support/raw_ostream.h" + +using namespace clang; + +//===----------------------------------------------------------------------===// +// Useful constants. +//===----------------------------------------------------------------------===// + +static const bool Alive = true; +static const bool Dead = false; + +//===----------------------------------------------------------------------===// +// Dataflow initialization logic. +//===----------------------------------------------------------------------===// + +namespace { +class RegisterDecls + : public CFGRecStmtDeclVisitor<RegisterDecls> { + + LiveVariables::AnalysisDataTy& AD; + + typedef llvm::SmallVector<VarDecl*, 20> AlwaysLiveTy; + AlwaysLiveTy AlwaysLive; + + +public: + RegisterDecls(LiveVariables::AnalysisDataTy& ad) : AD(ad) {} + + ~RegisterDecls() { + + AD.AlwaysLive.resetValues(AD); + + for (AlwaysLiveTy::iterator I = AlwaysLive.begin(), E = AlwaysLive.end(); + I != E; ++ I) + AD.AlwaysLive(*I, AD) = Alive; + } + + void VisitImplicitParamDecl(ImplicitParamDecl* IPD) { + // Register the VarDecl for tracking. + AD.Register(IPD); + } + + void VisitVarDecl(VarDecl* VD) { + // Register the VarDecl for tracking. + AD.Register(VD); + + // Does the variable have global storage? If so, it is always live. + if (VD->hasGlobalStorage()) + AlwaysLive.push_back(VD); + } + + CFG& getCFG() { return AD.getCFG(); } +}; +} // end anonymous namespace + +LiveVariables::LiveVariables(AnalysisContext &AC, bool killAtAssign) { + // Register all referenced VarDecls. + CFG &cfg = *AC.getCFG(); + getAnalysisData().setCFG(cfg); + getAnalysisData().setContext(AC.getASTContext()); + getAnalysisData().AC = &AC; + getAnalysisData().killAtAssign = killAtAssign; + + RegisterDecls R(getAnalysisData()); + cfg.VisitBlockStmts(R); + + // Register all parameters even if they didn't occur in the function body. + if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(AC.getDecl())) + for (FunctionDecl::param_const_iterator PI = FD->param_begin(), + PE = FD->param_end(); PI != PE; ++PI) + getAnalysisData().Register(*PI); +} + +//===----------------------------------------------------------------------===// +// Transfer functions. +//===----------------------------------------------------------------------===// + +namespace { + +class TransferFuncs : public CFGRecStmtVisitor<TransferFuncs>{ + LiveVariables::AnalysisDataTy& AD; + LiveVariables::ValTy LiveState; + const CFGBlock *currentBlock; +public: + TransferFuncs(LiveVariables::AnalysisDataTy& ad) : AD(ad), currentBlock(0) {} + + LiveVariables::ValTy& getVal() { return LiveState; } + CFG& getCFG() { return AD.getCFG(); } + + void VisitDeclRefExpr(DeclRefExpr* DR); + void VisitBinaryOperator(BinaryOperator* B); + void VisitBlockExpr(BlockExpr *B); + void VisitAssign(BinaryOperator* B); + void VisitDeclStmt(DeclStmt* DS); + void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S); + void VisitUnaryOperator(UnaryOperator* U); + void Visit(Stmt *S); + void VisitTerminator(CFGBlock* B); + + /// VisitConditionVariableInit - Handle the initialization of condition + /// variables at branches. Valid statements include IfStmt, ForStmt, + /// WhileStmt, and SwitchStmt. + void VisitConditionVariableInit(Stmt *S); + + void SetTopValue(LiveVariables::ValTy& V) { + V = AD.AlwaysLive; + } + + void setCurrentBlock(const CFGBlock *block) { + currentBlock = block; + } +}; + +void TransferFuncs::Visit(Stmt *S) { + + if (S == getCurrentBlkStmt()) { + + if (AD.Observer) + AD.Observer->ObserveStmt(S, currentBlock, AD, LiveState); + + if (getCFG().isBlkExpr(S)) + LiveState(S, AD) = Dead; + + StmtVisitor<TransferFuncs,void>::Visit(S); + } + else if (!getCFG().isBlkExpr(S)) { + + if (AD.Observer) + AD.Observer->ObserveStmt(S, currentBlock, AD, LiveState); + + StmtVisitor<TransferFuncs,void>::Visit(S); + + } + else { + // For block-level expressions, mark that they are live. + LiveState(S,AD) = Alive; + } +} + +void TransferFuncs::VisitConditionVariableInit(Stmt *S) { + assert(!getCFG().isBlkExpr(S)); + CFGRecStmtVisitor<TransferFuncs>::VisitConditionVariableInit(S); +} + +void TransferFuncs::VisitTerminator(CFGBlock* B) { + + const Stmt* E = B->getTerminatorCondition(); + + if (!E) + return; + + assert (getCFG().isBlkExpr(E)); + LiveState(E, AD) = Alive; +} + +void TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) { + if (VarDecl* V = dyn_cast<VarDecl>(DR->getDecl())) + LiveState(V, AD) = Alive; +} + +void TransferFuncs::VisitBlockExpr(BlockExpr *BE) { + AnalysisContext::referenced_decls_iterator I, E; + llvm::tie(I, E) = AD.AC->getReferencedBlockVars(BE->getBlockDecl()); + for ( ; I != E ; ++I) { + DeclBitVector_Types::Idx i = AD.getIdx(*I); + if (i.isValid()) + LiveState.getBit(i) = Alive; + } +} + +void TransferFuncs::VisitBinaryOperator(BinaryOperator* B) { + if (B->isAssignmentOp()) VisitAssign(B); + else VisitStmt(B); +} + +void +TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { + + // This is a block-level expression. Its value is 'dead' before this point. + LiveState(S, AD) = Dead; + + // This represents a 'use' of the collection. + Visit(S->getCollection()); + + // This represents a 'kill' for the variable. + Stmt* Element = S->getElement(); + DeclRefExpr* DR = 0; + VarDecl* VD = 0; + + if (DeclStmt* DS = dyn_cast<DeclStmt>(Element)) + VD = cast<VarDecl>(DS->getSingleDecl()); + else { + Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens(); + if ((DR = dyn_cast<DeclRefExpr>(ElemExpr))) + VD = cast<VarDecl>(DR->getDecl()); + else { + Visit(ElemExpr); + return; + } + } + + if (VD) { + LiveState(VD, AD) = Dead; + if (AD.Observer && DR) { AD.Observer->ObserverKill(DR); } + } +} + + +void TransferFuncs::VisitUnaryOperator(UnaryOperator* U) { + Expr *E = U->getSubExpr(); + + switch (U->getOpcode()) { + case UO_PostInc: + case UO_PostDec: + case UO_PreInc: + case UO_PreDec: + // Walk through the subexpressions, blasting through ParenExprs + // until we either find a DeclRefExpr or some non-DeclRefExpr + // expression. + if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParens())) + if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) { + // Treat the --/++ operator as a kill. + if (AD.Observer) { AD.Observer->ObserverKill(DR); } + LiveState(VD, AD) = Alive; + return VisitDeclRefExpr(DR); + } + + // Fall-through. + + default: + return Visit(E); + } +} + +void TransferFuncs::VisitAssign(BinaryOperator* B) { + Expr* LHS = B->getLHS(); + + // Assigning to a variable? + if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(LHS->IgnoreParens())) { + // Assignments to references don't kill the ref's address + if (DR->getDecl()->getType()->isReferenceType()) { + VisitDeclRefExpr(DR); + } else { + if (AD.killAtAssign) { + // Update liveness inforamtion. + unsigned bit = AD.getIdx(DR->getDecl()); + LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit); + + if (AD.Observer) { AD.Observer->ObserverKill(DR); } + } + // Handle things like +=, etc., which also generate "uses" + // of a variable. Do this just by visiting the subexpression. + if (B->getOpcode() != BO_Assign) + VisitDeclRefExpr(DR); + } + } + else // Not assigning to a variable. Process LHS as usual. + Visit(LHS); + + Visit(B->getRHS()); +} + +void TransferFuncs::VisitDeclStmt(DeclStmt* DS) { + // Declarations effectively "kill" a variable since they cannot + // possibly be live before they are declared. + for (DeclStmt::decl_iterator DI=DS->decl_begin(), DE = DS->decl_end(); + DI != DE; ++DI) + if (VarDecl* VD = dyn_cast<VarDecl>(*DI)) { + // Update liveness information by killing the VarDecl. + unsigned bit = AD.getIdx(VD); + LiveState.getDeclBit(bit) = Dead | AD.AlwaysLive.getDeclBit(bit); + + // The initializer is evaluated after the variable comes into scope, but + // before the DeclStmt (which binds the value to the variable). + // Since this is a reverse dataflow analysis, we must evaluate the + // transfer function for this expression after the DeclStmt. If the + // initializer references the variable (which is bad) then we extend + // its liveness. + if (Expr* Init = VD->getInit()) + Visit(Init); + + if (const VariableArrayType* VT = + AD.getContext().getAsVariableArrayType(VD->getType())) { + StmtIterator I(const_cast<VariableArrayType*>(VT)); + StmtIterator E; + for (; I != E; ++I) Visit(*I); + } + } +} + +} // end anonymous namespace + +//===----------------------------------------------------------------------===// +// Merge operator: if something is live on any successor block, it is live +// in the current block (a set union). +//===----------------------------------------------------------------------===// + +namespace { + typedef StmtDeclBitVector_Types::Union Merge; + typedef DataflowSolver<LiveVariables, TransferFuncs, Merge> Solver; +} // end anonymous namespace + +//===----------------------------------------------------------------------===// +// External interface to run Liveness analysis. +//===----------------------------------------------------------------------===// + +void LiveVariables::runOnCFG(CFG& cfg) { + Solver S(*this); + S.runOnCFG(cfg); +} + +void LiveVariables::runOnAllBlocks(const CFG& cfg, + LiveVariables::ObserverTy* Obs, + bool recordStmtValues) { + Solver S(*this); + SaveAndRestore<LiveVariables::ObserverTy*> SRObs(getAnalysisData().Observer, + Obs); + S.runOnAllBlocks(cfg, recordStmtValues); +} + +//===----------------------------------------------------------------------===// +// liveness queries +// + +bool LiveVariables::isLive(const CFGBlock* B, const VarDecl* D) const { + DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D); + return i.isValid() ? getBlockData(B).getBit(i) : false; +} + +bool LiveVariables::isLive(const ValTy& Live, const VarDecl* D) const { + DeclBitVector_Types::Idx i = getAnalysisData().getIdx(D); + return i.isValid() ? Live.getBit(i) : false; +} + +bool LiveVariables::isLive(const Stmt* Loc, const Stmt* StmtVal) const { + return getStmtData(Loc)(StmtVal,getAnalysisData()); +} + +bool LiveVariables::isLive(const Stmt* Loc, const VarDecl* D) const { + return getStmtData(Loc)(D,getAnalysisData()); +} + +//===----------------------------------------------------------------------===// +// printing liveness state for debugging +// + +void LiveVariables::dumpLiveness(const ValTy& V, const SourceManager& SM) const { + const AnalysisDataTy& AD = getAnalysisData(); + + for (AnalysisDataTy::decl_iterator I = AD.begin_decl(), + E = AD.end_decl(); I!=E; ++I) + if (V.getDeclBit(I->second)) { + llvm::errs() << " " << I->first->getIdentifier()->getName() << " <"; + I->first->getLocation().dump(SM); + llvm::errs() << ">\n"; + } +} + +void LiveVariables::dumpBlockLiveness(const SourceManager& M) const { + for (BlockDataMapTy::const_iterator I = getBlockDataMap().begin(), + E = getBlockDataMap().end(); I!=E; ++I) { + llvm::errs() << "\n[ B" << I->first->getBlockID() + << " (live variables at block exit) ]\n"; + dumpLiveness(I->second,M); + } + + llvm::errs() << "\n"; +} diff --git a/contrib/llvm/tools/clang/lib/Analysis/PrintfFormatString.cpp b/contrib/llvm/tools/clang/lib/Analysis/PrintfFormatString.cpp new file mode 100644 index 0000000..ef5c0fb --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/PrintfFormatString.cpp @@ -0,0 +1,668 @@ +//== PrintfFormatString.cpp - Analysis of printf format strings --*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Handling of format string in printf and friends. The structure of format +// strings for fprintf() are described in C99 7.19.6.1. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Analyses/FormatString.h" +#include "FormatStringParsing.h" + +using clang::analyze_format_string::ArgTypeResult; +using clang::analyze_format_string::FormatStringHandler; +using clang::analyze_format_string::LengthModifier; +using clang::analyze_format_string::OptionalAmount; +using clang::analyze_format_string::ConversionSpecifier; +using clang::analyze_printf::PrintfSpecifier; + +using namespace clang; + +typedef clang::analyze_format_string::SpecifierResult<PrintfSpecifier> + PrintfSpecifierResult; + +//===----------------------------------------------------------------------===// +// Methods for parsing format strings. +//===----------------------------------------------------------------------===// + +using analyze_format_string::ParseNonPositionAmount; + +static bool ParsePrecision(FormatStringHandler &H, PrintfSpecifier &FS, + const char *Start, const char *&Beg, const char *E, + unsigned *argIndex) { + if (argIndex) { + FS.setPrecision(ParseNonPositionAmount(Beg, E, *argIndex)); + } + else { + const OptionalAmount Amt = ParsePositionAmount(H, Start, Beg, E, + analyze_format_string::PrecisionPos); + if (Amt.isInvalid()) + return true; + FS.setPrecision(Amt); + } + return false; +} + +static PrintfSpecifierResult ParsePrintfSpecifier(FormatStringHandler &H, + const char *&Beg, + const char *E, + unsigned &argIndex, + bool FormatExtensions) { + + using namespace clang::analyze_format_string; + using namespace clang::analyze_printf; + + const char *I = Beg; + const char *Start = 0; + UpdateOnReturn <const char*> UpdateBeg(Beg, I); + + // Look for a '%' character that indicates the start of a format specifier. + for ( ; I != E ; ++I) { + char c = *I; + if (c == '\0') { + // Detect spurious null characters, which are likely errors. + H.HandleNullChar(I); + return true; + } + if (c == '%') { + Start = I++; // Record the start of the format specifier. + break; + } + } + + // No format specifier found? + if (!Start) + return false; + + if (I == E) { + // No more characters left? + H.HandleIncompleteSpecifier(Start, E - Start); + return true; + } + + PrintfSpecifier FS; + if (ParseArgPosition(H, FS, Start, I, E)) + return true; + + if (I == E) { + // No more characters left? + H.HandleIncompleteSpecifier(Start, E - Start); + return true; + } + + // Look for flags (if any). + bool hasMore = true; + for ( ; I != E; ++I) { + switch (*I) { + default: hasMore = false; break; + case '\'': + // FIXME: POSIX specific. Always accept? + FS.setHasThousandsGrouping(I); + break; + case '-': FS.setIsLeftJustified(I); break; + case '+': FS.setHasPlusPrefix(I); break; + case ' ': FS.setHasSpacePrefix(I); break; + case '#': FS.setHasAlternativeForm(I); break; + case '0': FS.setHasLeadingZeros(I); break; + } + if (!hasMore) + break; + } + + if (I == E) { + // No more characters left? + H.HandleIncompleteSpecifier(Start, E - Start); + return true; + } + + // Look for the field width (if any). + if (ParseFieldWidth(H, FS, Start, I, E, + FS.usesPositionalArg() ? 0 : &argIndex)) + return true; + + if (I == E) { + // No more characters left? + H.HandleIncompleteSpecifier(Start, E - Start); + return true; + } + + // Look for the precision (if any). + if (*I == '.') { + ++I; + if (I == E) { + H.HandleIncompleteSpecifier(Start, E - Start); + return true; + } + + if (ParsePrecision(H, FS, Start, I, E, + FS.usesPositionalArg() ? 0 : &argIndex)) + return true; + + if (I == E) { + // No more characters left? + H.HandleIncompleteSpecifier(Start, E - Start); + return true; + } + } + + // Look for the length modifier. + if (ParseLengthModifier(FS, I, E) && I == E) { + // No more characters left? + H.HandleIncompleteSpecifier(Start, E - Start); + return true; + } + + if (*I == '\0') { + // Detect spurious null characters, which are likely errors. + H.HandleNullChar(I); + return true; + } + + // Finally, look for the conversion specifier. + const char *conversionPosition = I++; + ConversionSpecifier::Kind k = ConversionSpecifier::InvalidSpecifier; + switch (*conversionPosition) { + default: + break; + // C99: 7.19.6.1 (section 8). + case '%': k = ConversionSpecifier::PercentArg; break; + case 'A': k = ConversionSpecifier::AArg; break; + case 'E': k = ConversionSpecifier::EArg; break; + case 'F': k = ConversionSpecifier::FArg; break; + case 'G': k = ConversionSpecifier::GArg; break; + case 'X': k = ConversionSpecifier::XArg; break; + case 'a': k = ConversionSpecifier::aArg; break; + case 'c': k = ConversionSpecifier::cArg; break; + case 'd': k = ConversionSpecifier::dArg; break; + case 'e': k = ConversionSpecifier::eArg; break; + case 'f': k = ConversionSpecifier::fArg; break; + case 'g': k = ConversionSpecifier::gArg; break; + case 'i': k = ConversionSpecifier::iArg; break; + case 'n': k = ConversionSpecifier::nArg; break; + case 'o': k = ConversionSpecifier::oArg; break; + case 'p': k = ConversionSpecifier::pArg; break; + case 's': k = ConversionSpecifier::sArg; break; + case 'u': k = ConversionSpecifier::uArg; break; + case 'x': k = ConversionSpecifier::xArg; break; + // POSIX specific. + case 'C': k = ConversionSpecifier::CArg; break; + case 'S': k = ConversionSpecifier::SArg; break; + // Objective-C. + case '@': k = ConversionSpecifier::ObjCObjArg; break; + // Glibc specific. + case 'm': k = ConversionSpecifier::PrintErrno; break; + // FreeBSD format extensions + case 'b': if (FormatExtensions) k = ConversionSpecifier::bArg; break; /* check for int and then char * */ + case 'r': if (FormatExtensions) k = ConversionSpecifier::rArg; break; + case 'y': if (FormatExtensions) k = ConversionSpecifier::iArg; break; + case 'D': if (FormatExtensions) k = ConversionSpecifier::DArg; break; /* check for u_char * pointer and a char * string */ + } + PrintfConversionSpecifier CS(conversionPosition, k); + FS.setConversionSpecifier(CS); + if (CS.consumesDataArgument() && !FS.usesPositionalArg()) + FS.setArgIndex(argIndex++); + // FreeBSD extension + if (k == ConversionSpecifier::bArg || k == ConversionSpecifier::DArg) + argIndex++; + + if (k == ConversionSpecifier::InvalidSpecifier) { + // Assume the conversion takes one argument. + return !H.HandleInvalidPrintfConversionSpecifier(FS, Start, I - Start); + } + return PrintfSpecifierResult(Start, FS); +} + +bool clang::analyze_format_string::ParsePrintfString(FormatStringHandler &H, + const char *I, + const char *E, + bool FormatExtensions) { + + unsigned argIndex = 0; + + // Keep looking for a format specifier until we have exhausted the string. + while (I != E) { + const PrintfSpecifierResult &FSR = ParsePrintfSpecifier(H, I, E, argIndex, + FormatExtensions); + // Did a fail-stop error of any kind occur when parsing the specifier? + // If so, don't do any more processing. + if (FSR.shouldStop()) + return true;; + // Did we exhaust the string or encounter an error that + // we can recover from? + if (!FSR.hasValue()) + continue; + // We have a format specifier. Pass it to the callback. + if (!H.HandlePrintfSpecifier(FSR.getValue(), FSR.getStart(), + I - FSR.getStart())) + return true; + } + assert(I == E && "Format string not exhausted"); + return false; +} + +//===----------------------------------------------------------------------===// +// Methods on ConversionSpecifier. +//===----------------------------------------------------------------------===// +const char *ConversionSpecifier::toString() const { + switch (kind) { + case dArg: return "d"; + case iArg: return "i"; + case oArg: return "o"; + case uArg: return "u"; + case xArg: return "x"; + case XArg: return "X"; + case fArg: return "f"; + case FArg: return "F"; + case eArg: return "e"; + case EArg: return "E"; + case gArg: return "g"; + case GArg: return "G"; + case aArg: return "a"; + case AArg: return "A"; + case cArg: return "c"; + case sArg: return "s"; + case pArg: return "p"; + case nArg: return "n"; + case PercentArg: return "%"; + case ScanListArg: return "["; + case InvalidSpecifier: return NULL; + + // MacOS X unicode extensions. + case CArg: return "C"; + case SArg: return "S"; + + // Objective-C specific specifiers. + case ObjCObjArg: return "@"; + + // FreeBSD specific specifiers. + case bArg: return "b"; + case DArg: return "D"; + case rArg: return "r"; + + // GlibC specific specifiers. + case PrintErrno: return "m"; + } + return NULL; +} + +//===----------------------------------------------------------------------===// +// Methods on PrintfSpecifier. +//===----------------------------------------------------------------------===// + +ArgTypeResult PrintfSpecifier::getArgType(ASTContext &Ctx) const { + const PrintfConversionSpecifier &CS = getConversionSpecifier(); + + if (!CS.consumesDataArgument()) + return ArgTypeResult::Invalid(); + + if (CS.getKind() == ConversionSpecifier::cArg) + switch (LM.getKind()) { + case LengthModifier::None: return Ctx.IntTy; + case LengthModifier::AsLong: return ArgTypeResult::WIntTy; + default: + return ArgTypeResult::Invalid(); + } + + if (CS.isIntArg()) + switch (LM.getKind()) { + case LengthModifier::AsLongDouble: + return ArgTypeResult::Invalid(); + case LengthModifier::None: return Ctx.IntTy; + case LengthModifier::AsChar: return Ctx.SignedCharTy; + case LengthModifier::AsShort: return Ctx.ShortTy; + case LengthModifier::AsLong: return Ctx.LongTy; + case LengthModifier::AsLongLong: return Ctx.LongLongTy; + case LengthModifier::AsIntMax: + // FIXME: Return unknown for now. + return ArgTypeResult(); + case LengthModifier::AsSizeT: return Ctx.getSizeType(); + case LengthModifier::AsPtrDiff: return Ctx.getPointerDiffType(); + } + + if (CS.isUIntArg()) + switch (LM.getKind()) { + case LengthModifier::AsLongDouble: + return ArgTypeResult::Invalid(); + case LengthModifier::None: return Ctx.UnsignedIntTy; + case LengthModifier::AsChar: return Ctx.UnsignedCharTy; + case LengthModifier::AsShort: return Ctx.UnsignedShortTy; + case LengthModifier::AsLong: return Ctx.UnsignedLongTy; + case LengthModifier::AsLongLong: return Ctx.UnsignedLongLongTy; + case LengthModifier::AsIntMax: + // FIXME: Return unknown for now. + return ArgTypeResult(); + case LengthModifier::AsSizeT: + // FIXME: How to get the corresponding unsigned + // version of size_t? + return ArgTypeResult(); + case LengthModifier::AsPtrDiff: + // FIXME: How to get the corresponding unsigned + // version of ptrdiff_t? + return ArgTypeResult(); + } + + if (CS.isDoubleArg()) { + if (LM.getKind() == LengthModifier::AsLongDouble) + return Ctx.LongDoubleTy; + return Ctx.DoubleTy; + } + + switch (CS.getKind()) { + case ConversionSpecifier::sArg: + return ArgTypeResult(LM.getKind() == LengthModifier::AsWideChar ? + ArgTypeResult::WCStrTy : ArgTypeResult::CStrTy); + case ConversionSpecifier::SArg: + // FIXME: This appears to be Mac OS X specific. + return ArgTypeResult::WCStrTy; + case ConversionSpecifier::CArg: + return Ctx.WCharTy; + case ConversionSpecifier::pArg: + return ArgTypeResult::CPointerTy; + default: + break; + } + + // FIXME: Handle other cases. + return ArgTypeResult(); +} + +bool PrintfSpecifier::fixType(QualType QT) { + // Handle strings first (char *, wchar_t *) + if (QT->isPointerType() && (QT->getPointeeType()->isAnyCharacterType())) { + CS.setKind(ConversionSpecifier::sArg); + + // Disable irrelevant flags + HasAlternativeForm = 0; + HasLeadingZeroes = 0; + + // Set the long length modifier for wide characters + if (QT->getPointeeType()->isWideCharType()) + LM.setKind(LengthModifier::AsWideChar); + + return true; + } + + // We can only work with builtin types. + if (!QT->isBuiltinType()) + return false; + + // Everything else should be a base type + const BuiltinType *BT = QT->getAs<BuiltinType>(); + + // Set length modifier + switch (BT->getKind()) { + default: + // The rest of the conversions are either optional or for non-builtin types + LM.setKind(LengthModifier::None); + break; + + case BuiltinType::Char_U: + case BuiltinType::UChar: + case BuiltinType::Char_S: + case BuiltinType::SChar: + LM.setKind(LengthModifier::AsChar); + break; + + case BuiltinType::Short: + case BuiltinType::UShort: + LM.setKind(LengthModifier::AsShort); + break; + + case BuiltinType::WChar_S: + case BuiltinType::WChar_U: + case BuiltinType::Long: + case BuiltinType::ULong: + LM.setKind(LengthModifier::AsLong); + break; + + case BuiltinType::LongLong: + case BuiltinType::ULongLong: + LM.setKind(LengthModifier::AsLongLong); + break; + + case BuiltinType::LongDouble: + LM.setKind(LengthModifier::AsLongDouble); + break; + } + + // Set conversion specifier and disable any flags which do not apply to it. + // Let typedefs to char fall through to int, as %c is silly for uint8_t. + if (isa<TypedefType>(QT) && QT->isAnyCharacterType()) { + CS.setKind(ConversionSpecifier::cArg); + LM.setKind(LengthModifier::None); + Precision.setHowSpecified(OptionalAmount::NotSpecified); + HasAlternativeForm = 0; + HasLeadingZeroes = 0; + HasPlusPrefix = 0; + } + // Test for Floating type first as LongDouble can pass isUnsignedIntegerType + else if (QT->isRealFloatingType()) { + CS.setKind(ConversionSpecifier::fArg); + } + else if (QT->isPointerType()) { + CS.setKind(ConversionSpecifier::pArg); + Precision.setHowSpecified(OptionalAmount::NotSpecified); + HasAlternativeForm = 0; + HasLeadingZeroes = 0; + HasPlusPrefix = 0; + } + else if (QT->isSignedIntegerType()) { + CS.setKind(ConversionSpecifier::dArg); + HasAlternativeForm = 0; + } + else if (QT->isUnsignedIntegerType()) { + CS.setKind(ConversionSpecifier::uArg); + HasAlternativeForm = 0; + HasPlusPrefix = 0; + } + else { + return false; + } + + return true; +} + +void PrintfSpecifier::toString(llvm::raw_ostream &os) const { + // Whilst some features have no defined order, we are using the order + // appearing in the C99 standard (ISO/IEC 9899:1999 (E) 7.19.6.1) + os << "%"; + + // Positional args + if (usesPositionalArg()) { + os << getPositionalArgIndex() << "$"; + } + + // Conversion flags + if (IsLeftJustified) os << "-"; + if (HasPlusPrefix) os << "+"; + if (HasSpacePrefix) os << " "; + if (HasAlternativeForm) os << "#"; + if (HasLeadingZeroes) os << "0"; + + // Minimum field width + FieldWidth.toString(os); + // Precision + Precision.toString(os); + // Length modifier + os << LM.toString(); + // Conversion specifier + os << CS.toString(); +} + +bool PrintfSpecifier::hasValidPlusPrefix() const { + if (!HasPlusPrefix) + return true; + + // The plus prefix only makes sense for signed conversions + switch (CS.getKind()) { + case ConversionSpecifier::dArg: + case ConversionSpecifier::iArg: + case ConversionSpecifier::fArg: + case ConversionSpecifier::FArg: + case ConversionSpecifier::eArg: + case ConversionSpecifier::EArg: + case ConversionSpecifier::gArg: + case ConversionSpecifier::GArg: + case ConversionSpecifier::aArg: + case ConversionSpecifier::AArg: + case ConversionSpecifier::rArg: + return true; + + default: + return false; + } +} + +bool PrintfSpecifier::hasValidAlternativeForm() const { + if (!HasAlternativeForm) + return true; + + // Alternate form flag only valid with the oxXaAeEfFgG conversions + switch (CS.getKind()) { + case ConversionSpecifier::oArg: + case ConversionSpecifier::xArg: + case ConversionSpecifier::XArg: + case ConversionSpecifier::aArg: + case ConversionSpecifier::AArg: + case ConversionSpecifier::eArg: + case ConversionSpecifier::EArg: + case ConversionSpecifier::fArg: + case ConversionSpecifier::FArg: + case ConversionSpecifier::gArg: + case ConversionSpecifier::GArg: + case ConversionSpecifier::rArg: + return true; + + default: + return false; + } +} + +bool PrintfSpecifier::hasValidLeadingZeros() const { + if (!HasLeadingZeroes) + return true; + + // Leading zeroes flag only valid with the diouxXaAeEfFgG conversions + switch (CS.getKind()) { + case ConversionSpecifier::dArg: + case ConversionSpecifier::iArg: + case ConversionSpecifier::oArg: + case ConversionSpecifier::uArg: + case ConversionSpecifier::xArg: + case ConversionSpecifier::XArg: + case ConversionSpecifier::aArg: + case ConversionSpecifier::AArg: + case ConversionSpecifier::eArg: + case ConversionSpecifier::EArg: + case ConversionSpecifier::fArg: + case ConversionSpecifier::FArg: + case ConversionSpecifier::gArg: + case ConversionSpecifier::GArg: + return true; + + default: + return false; + } +} + +bool PrintfSpecifier::hasValidSpacePrefix() const { + if (!HasSpacePrefix) + return true; + + // The space prefix only makes sense for signed conversions + switch (CS.getKind()) { + case ConversionSpecifier::dArg: + case ConversionSpecifier::iArg: + case ConversionSpecifier::fArg: + case ConversionSpecifier::FArg: + case ConversionSpecifier::eArg: + case ConversionSpecifier::EArg: + case ConversionSpecifier::gArg: + case ConversionSpecifier::GArg: + case ConversionSpecifier::aArg: + case ConversionSpecifier::AArg: + return true; + + default: + return false; + } +} + +bool PrintfSpecifier::hasValidLeftJustified() const { + if (!IsLeftJustified) + return true; + + // The left justified flag is valid for all conversions except n + switch (CS.getKind()) { + case ConversionSpecifier::nArg: + return false; + + default: + return true; + } +} + +bool PrintfSpecifier::hasValidThousandsGroupingPrefix() const { + if (!HasThousandsGrouping) + return true; + + switch (CS.getKind()) { + case ConversionSpecifier::dArg: + case ConversionSpecifier::iArg: + case ConversionSpecifier::uArg: + case ConversionSpecifier::fArg: + case ConversionSpecifier::FArg: + case ConversionSpecifier::gArg: + case ConversionSpecifier::GArg: + return true; + default: + return false; + } +} + +bool PrintfSpecifier::hasValidPrecision() const { + if (Precision.getHowSpecified() == OptionalAmount::NotSpecified) + return true; + + // Precision is only valid with the diouxXaAeEfFgGs conversions + switch (CS.getKind()) { + case ConversionSpecifier::dArg: + case ConversionSpecifier::iArg: + case ConversionSpecifier::oArg: + case ConversionSpecifier::uArg: + case ConversionSpecifier::xArg: + case ConversionSpecifier::XArg: + case ConversionSpecifier::aArg: + case ConversionSpecifier::AArg: + case ConversionSpecifier::eArg: + case ConversionSpecifier::EArg: + case ConversionSpecifier::fArg: + case ConversionSpecifier::FArg: + case ConversionSpecifier::gArg: + case ConversionSpecifier::GArg: + case ConversionSpecifier::sArg: + return true; + + default: + return false; + } +} +bool PrintfSpecifier::hasValidFieldWidth() const { + if (FieldWidth.getHowSpecified() == OptionalAmount::NotSpecified) + return true; + + // The field width is valid for all conversions except n + switch (CS.getKind()) { + case ConversionSpecifier::nArg: + return false; + + default: + return true; + } +} diff --git a/contrib/llvm/tools/clang/lib/Analysis/PseudoConstantAnalysis.cpp b/contrib/llvm/tools/clang/lib/Analysis/PseudoConstantAnalysis.cpp new file mode 100644 index 0000000..ff96eb4 --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/PseudoConstantAnalysis.cpp @@ -0,0 +1,240 @@ +//== PseudoConstantAnalysis.cpp - Find Pseudoconstants in the AST-*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file tracks the usage of variables in a Decl body to see if they are +// never written to, implying that they constant. This is useful in static +// analysis to see if a developer might have intended a variable to be const. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Analyses/PseudoConstantAnalysis.h" +#include "clang/AST/Decl.h" +#include "clang/AST/Expr.h" +#include "clang/AST/Stmt.h" +#include <deque> + +using namespace clang; + +// The number of ValueDecls we want to keep track of by default (per-function) +#define VARDECL_SET_SIZE 256 +typedef llvm::SmallPtrSet<const VarDecl*, VARDECL_SET_SIZE> VarDeclSet; + +PseudoConstantAnalysis::PseudoConstantAnalysis(const Stmt *DeclBody) : + DeclBody(DeclBody), Analyzed(false) { + NonConstantsImpl = new VarDeclSet; + UsedVarsImpl = new VarDeclSet; +} + +PseudoConstantAnalysis::~PseudoConstantAnalysis() { + delete (VarDeclSet*)NonConstantsImpl; + delete (VarDeclSet*)UsedVarsImpl; +} + +// Returns true if the given ValueDecl is never written to in the given DeclBody +bool PseudoConstantAnalysis::isPseudoConstant(const VarDecl *VD) { + // Only local and static variables can be pseudoconstants + if (!VD->hasLocalStorage() && !VD->isStaticLocal()) + return false; + + if (!Analyzed) { + RunAnalysis(); + Analyzed = true; + } + + VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl; + + return !NonConstants->count(VD); +} + +// Returns true if the variable was used (self assignments don't count) +bool PseudoConstantAnalysis::wasReferenced(const VarDecl *VD) { + if (!Analyzed) { + RunAnalysis(); + Analyzed = true; + } + + VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl; + + return UsedVars->count(VD); +} + +// Returns a Decl from a (Block)DeclRefExpr (if any) +const Decl *PseudoConstantAnalysis::getDecl(const Expr *E) { + if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) + return DR->getDecl(); + else if (const BlockDeclRefExpr *BDR = dyn_cast<BlockDeclRefExpr>(E)) + return BDR->getDecl(); + else + return 0; +} + +void PseudoConstantAnalysis::RunAnalysis() { + std::deque<const Stmt *> WorkList; + VarDeclSet *NonConstants = (VarDeclSet*)NonConstantsImpl; + VarDeclSet *UsedVars = (VarDeclSet*)UsedVarsImpl; + + // Start with the top level statement of the function + WorkList.push_back(DeclBody); + + while (!WorkList.empty()) { + const Stmt* Head = WorkList.front(); + WorkList.pop_front(); + + if (const Expr *Ex = dyn_cast<Expr>(Head)) + Head = Ex->IgnoreParenCasts(); + + switch (Head->getStmtClass()) { + // Case 1: Assignment operators modifying VarDecls + case Stmt::BinaryOperatorClass: { + const BinaryOperator *BO = cast<BinaryOperator>(Head); + // Look for a Decl on the LHS + const Decl *LHSDecl = getDecl(BO->getLHS()->IgnoreParenCasts()); + if (!LHSDecl) + break; + + // We found a binary operator with a DeclRefExpr on the LHS. We now check + // for any of the assignment operators, implying that this Decl is being + // written to. + switch (BO->getOpcode()) { + // Self-assignments don't count as use of a variable + case BO_Assign: { + // Look for a DeclRef on the RHS + const Decl *RHSDecl = getDecl(BO->getRHS()->IgnoreParenCasts()); + + // If the Decls match, we have self-assignment + if (LHSDecl == RHSDecl) + // Do not visit the children + continue; + + } + case BO_AddAssign: + case BO_SubAssign: + case BO_MulAssign: + case BO_DivAssign: + case BO_AndAssign: + case BO_OrAssign: + case BO_XorAssign: + case BO_ShlAssign: + case BO_ShrAssign: { + const VarDecl *VD = dyn_cast<VarDecl>(LHSDecl); + // The DeclRefExpr is being assigned to - mark it as non-constant + if (VD) + NonConstants->insert(VD); + break; + } + + default: + break; + } + break; + } + + // Case 2: Pre/post increment/decrement and address of + case Stmt::UnaryOperatorClass: { + const UnaryOperator *UO = cast<UnaryOperator>(Head); + + // Look for a DeclRef in the subexpression + const Decl *D = getDecl(UO->getSubExpr()->IgnoreParenCasts()); + if (!D) + break; + + // We found a unary operator with a DeclRef as a subexpression. We now + // check for any of the increment/decrement operators, as well as + // addressOf. + switch (UO->getOpcode()) { + case UO_PostDec: + case UO_PostInc: + case UO_PreDec: + case UO_PreInc: + // The DeclRef is being changed - mark it as non-constant + case UO_AddrOf: { + // If we are taking the address of the DeclRefExpr, assume it is + // non-constant. + const VarDecl *VD = dyn_cast<VarDecl>(D); + if (VD) + NonConstants->insert(VD); + break; + } + + default: + break; + } + break; + } + + // Case 3: Reference Declarations + case Stmt::DeclStmtClass: { + const DeclStmt *DS = cast<DeclStmt>(Head); + // Iterate over each decl and see if any of them contain reference decls + for (DeclStmt::const_decl_iterator I = DS->decl_begin(), + E = DS->decl_end(); I != E; ++I) { + // We only care about VarDecls + const VarDecl *VD = dyn_cast<VarDecl>(*I); + if (!VD) + continue; + + // We found a VarDecl; make sure it is a reference type + if (!VD->getType().getTypePtr()->isReferenceType()) + continue; + + // Try to find a Decl in the initializer + const Decl *D = getDecl(VD->getInit()->IgnoreParenCasts()); + if (!D) + break; + + // If the reference is to another var, add the var to the non-constant + // list + if (const VarDecl *RefVD = dyn_cast<VarDecl>(D)) { + NonConstants->insert(RefVD); + continue; + } + } + break; + } + + // Case 4: Block variable references + case Stmt::BlockDeclRefExprClass: { + const BlockDeclRefExpr *BDR = cast<BlockDeclRefExpr>(Head); + if (const VarDecl *VD = dyn_cast<VarDecl>(BDR->getDecl())) { + // Add the Decl to the used list + UsedVars->insert(VD); + continue; + } + break; + } + + // Case 5: Variable references + case Stmt::DeclRefExprClass: { + const DeclRefExpr *DR = cast<DeclRefExpr>(Head); + if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { + // Add the Decl to the used list + UsedVars->insert(VD); + continue; + } + break; + } + + // Case 6: Block expressions + case Stmt::BlockExprClass: { + const BlockExpr *B = cast<BlockExpr>(Head); + // Add the body of the block to the list + WorkList.push_back(B->getBody()); + continue; + } + + default: + break; + } // switch (head->getStmtClass()) + + // Add all substatements to the worklist + for (Stmt::const_child_range I = Head->children(); I; ++I) + if (*I) + WorkList.push_back(*I); + } // while (!WorkList.empty()) +} diff --git a/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp b/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp new file mode 100644 index 0000000..7afa586 --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp @@ -0,0 +1,290 @@ +//=- ReachableCodePathInsensitive.cpp ---------------------------*- C++ --*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements a flow-sensitive, path-insensitive analysis of +// determining reachable blocks within a CFG. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/SmallVector.h" +#include "clang/AST/Expr.h" +#include "clang/AST/ExprCXX.h" +#include "clang/AST/StmtCXX.h" +#include "clang/Analysis/Analyses/ReachableCode.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/AnalysisContext.h" +#include "clang/Basic/SourceManager.h" + +using namespace clang; + +static SourceLocation GetUnreachableLoc(const CFGBlock &b, SourceRange &R1, + SourceRange &R2) { + const Stmt *S = 0; + unsigned sn = 0; + R1 = R2 = SourceRange(); + + if (sn < b.size()) { + CFGStmt CS = b[sn].getAs<CFGStmt>(); + if (!CS) + return SourceLocation(); + + S = CS.getStmt(); + } else if (b.getTerminator()) + S = b.getTerminator(); + else + return SourceLocation(); + + if (const Expr *Ex = dyn_cast<Expr>(S)) + S = Ex->IgnoreParenImpCasts(); + + switch (S->getStmtClass()) { + case Expr::BinaryOperatorClass: { + const BinaryOperator *BO = cast<BinaryOperator>(S); + if (BO->getOpcode() == BO_Comma) { + if (sn+1 < b.size()) + return b[sn+1].getAs<CFGStmt>().getStmt()->getLocStart(); + const CFGBlock *n = &b; + while (1) { + if (n->getTerminator()) + return n->getTerminator()->getLocStart(); + if (n->succ_size() != 1) + return SourceLocation(); + n = n[0].succ_begin()[0]; + if (n->pred_size() != 1) + return SourceLocation(); + if (!n->empty()) + return n[0][0].getAs<CFGStmt>().getStmt()->getLocStart(); + } + } + R1 = BO->getLHS()->getSourceRange(); + R2 = BO->getRHS()->getSourceRange(); + return BO->getOperatorLoc(); + } + case Expr::UnaryOperatorClass: { + const UnaryOperator *UO = cast<UnaryOperator>(S); + R1 = UO->getSubExpr()->getSourceRange(); + return UO->getOperatorLoc(); + } + case Expr::CompoundAssignOperatorClass: { + const CompoundAssignOperator *CAO = cast<CompoundAssignOperator>(S); + R1 = CAO->getLHS()->getSourceRange(); + R2 = CAO->getRHS()->getSourceRange(); + return CAO->getOperatorLoc(); + } + case Expr::BinaryConditionalOperatorClass: + case Expr::ConditionalOperatorClass: { + const AbstractConditionalOperator *CO = + cast<AbstractConditionalOperator>(S); + return CO->getQuestionLoc(); + } + case Expr::MemberExprClass: { + const MemberExpr *ME = cast<MemberExpr>(S); + R1 = ME->getSourceRange(); + return ME->getMemberLoc(); + } + case Expr::ArraySubscriptExprClass: { + const ArraySubscriptExpr *ASE = cast<ArraySubscriptExpr>(S); + R1 = ASE->getLHS()->getSourceRange(); + R2 = ASE->getRHS()->getSourceRange(); + return ASE->getRBracketLoc(); + } + case Expr::CStyleCastExprClass: { + const CStyleCastExpr *CSC = cast<CStyleCastExpr>(S); + R1 = CSC->getSubExpr()->getSourceRange(); + return CSC->getLParenLoc(); + } + case Expr::CXXFunctionalCastExprClass: { + const CXXFunctionalCastExpr *CE = cast <CXXFunctionalCastExpr>(S); + R1 = CE->getSubExpr()->getSourceRange(); + return CE->getTypeBeginLoc(); + } + case Stmt::CXXTryStmtClass: { + return cast<CXXTryStmt>(S)->getHandler(0)->getCatchLoc(); + } + default: ; + } + R1 = S->getSourceRange(); + return S->getLocStart(); +} + +static SourceLocation MarkLiveTop(const CFGBlock *Start, + llvm::BitVector &reachable, + SourceManager &SM) { + + // Prep work worklist. + llvm::SmallVector<const CFGBlock*, 32> WL; + WL.push_back(Start); + + SourceRange R1, R2; + SourceLocation top = GetUnreachableLoc(*Start, R1, R2); + + bool FromMainFile = false; + bool FromSystemHeader = false; + bool TopValid = false; + + if (top.isValid()) { + FromMainFile = SM.isFromMainFile(top); + FromSystemHeader = SM.isInSystemHeader(top); + TopValid = true; + } + + // Solve + CFGBlock::FilterOptions FO; + FO.IgnoreDefaultsWithCoveredEnums = 1; + + while (!WL.empty()) { + const CFGBlock *item = WL.back(); + WL.pop_back(); + + SourceLocation c = GetUnreachableLoc(*item, R1, R2); + if (c.isValid() + && (!TopValid + || (SM.isFromMainFile(c) && !FromMainFile) + || (FromSystemHeader && !SM.isInSystemHeader(c)) + || SM.isBeforeInTranslationUnit(c, top))) { + top = c; + FromMainFile = SM.isFromMainFile(top); + FromSystemHeader = SM.isInSystemHeader(top); + } + + reachable.set(item->getBlockID()); + for (CFGBlock::filtered_succ_iterator I = + item->filtered_succ_start_end(FO); I.hasMore(); ++I) + if (const CFGBlock *B = *I) { + unsigned blockID = B->getBlockID(); + if (!reachable[blockID]) { + reachable.set(blockID); + WL.push_back(B); + } + } + } + + return top; +} + +static int LineCmp(const void *p1, const void *p2) { + SourceLocation *Line1 = (SourceLocation *)p1; + SourceLocation *Line2 = (SourceLocation *)p2; + return !(*Line1 < *Line2); +} + +namespace { +struct ErrLoc { + SourceLocation Loc; + SourceRange R1; + SourceRange R2; + ErrLoc(SourceLocation l, SourceRange r1, SourceRange r2) + : Loc(l), R1(r1), R2(r2) { } +}; +} +namespace clang { namespace reachable_code { + +/// ScanReachableFromBlock - Mark all blocks reachable from Start. +/// Returns the total number of blocks that were marked reachable. +unsigned ScanReachableFromBlock(const CFGBlock &Start, + llvm::BitVector &Reachable) { + unsigned count = 0; + llvm::SmallVector<const CFGBlock*, 32> WL; + + // Prep work queue + Reachable.set(Start.getBlockID()); + ++count; + WL.push_back(&Start); + + // Find the reachable blocks from 'Start'. + CFGBlock::FilterOptions FO; + FO.IgnoreDefaultsWithCoveredEnums = 1; + + while (!WL.empty()) { + const CFGBlock *item = WL.back(); + WL.pop_back(); + + // Look at the successors and mark then reachable. + for (CFGBlock::filtered_succ_iterator I= item->filtered_succ_start_end(FO); + I.hasMore(); ++I) + if (const CFGBlock *B = *I) { + unsigned blockID = B->getBlockID(); + if (!Reachable[blockID]) { + Reachable.set(blockID); + ++count; + WL.push_back(B); + } + } + } + return count; +} + +void FindUnreachableCode(AnalysisContext &AC, Callback &CB) { + CFG *cfg = AC.getCFG(); + if (!cfg) + return; + + // Scan for reachable blocks. + llvm::BitVector reachable(cfg->getNumBlockIDs()); + unsigned numReachable = ScanReachableFromBlock(cfg->getEntry(), reachable); + + // If there are no unreachable blocks, we're done. + if (numReachable == cfg->getNumBlockIDs()) + return; + + SourceRange R1, R2; + + llvm::SmallVector<ErrLoc, 24> lines; + bool AddEHEdges = AC.getAddEHEdges(); + + // First, give warnings for blocks with no predecessors, as they + // can't be part of a loop. + for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) { + CFGBlock &b = **I; + if (!reachable[b.getBlockID()]) { + if (b.pred_empty()) { + if (!AddEHEdges + && dyn_cast_or_null<CXXTryStmt>(b.getTerminator().getStmt())) { + // When not adding EH edges from calls, catch clauses + // can otherwise seem dead. Avoid noting them as dead. + numReachable += ScanReachableFromBlock(b, reachable); + continue; + } + SourceLocation c = GetUnreachableLoc(b, R1, R2); + if (!c.isValid()) { + // Blocks without a location can't produce a warning, so don't mark + // reachable blocks from here as live. + reachable.set(b.getBlockID()); + ++numReachable; + continue; + } + lines.push_back(ErrLoc(c, R1, R2)); + // Avoid excessive errors by marking everything reachable from here + numReachable += ScanReachableFromBlock(b, reachable); + } + } + } + + if (numReachable < cfg->getNumBlockIDs()) { + // And then give warnings for the tops of loops. + for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) { + CFGBlock &b = **I; + if (!reachable[b.getBlockID()]) + // Avoid excessive errors by marking everything reachable from here + lines.push_back(ErrLoc(MarkLiveTop(&b, reachable, + AC.getASTContext().getSourceManager()), + SourceRange(), SourceRange())); + } + } + + llvm::array_pod_sort(lines.begin(), lines.end(), LineCmp); + + for (llvm::SmallVectorImpl<ErrLoc>::iterator I=lines.begin(), E=lines.end(); + I != E; ++I) + if (I->Loc.isValid()) + CB.HandleUnreachable(I->Loc, I->R1, I->R2); +} + +}} // end namespace clang::reachable_code diff --git a/contrib/llvm/tools/clang/lib/Analysis/ScanfFormatString.cpp b/contrib/llvm/tools/clang/lib/Analysis/ScanfFormatString.cpp new file mode 100644 index 0000000..6a8673a --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/ScanfFormatString.cpp @@ -0,0 +1,221 @@ +//= ScanfFormatString.cpp - Analysis of printf format strings --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Handling of format string in scanf and friends. The structure of format +// strings for fscanf() are described in C99 7.19.6.2. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Analyses/FormatString.h" +#include "FormatStringParsing.h" + +using clang::analyze_format_string::ArgTypeResult; +using clang::analyze_format_string::FormatStringHandler; +using clang::analyze_format_string::LengthModifier; +using clang::analyze_format_string::OptionalAmount; +using clang::analyze_format_string::ConversionSpecifier; +using clang::analyze_scanf::ScanfConversionSpecifier; +using clang::analyze_scanf::ScanfSpecifier; +using clang::UpdateOnReturn; + +typedef clang::analyze_format_string::SpecifierResult<ScanfSpecifier> + ScanfSpecifierResult; + +static bool ParseScanList(FormatStringHandler &H, + ScanfConversionSpecifier &CS, + const char *&Beg, const char *E) { + const char *I = Beg; + const char *start = I - 1; + UpdateOnReturn <const char*> UpdateBeg(Beg, I); + + // No more characters? + if (I == E) { + H.HandleIncompleteScanList(start, I); + return true; + } + + // Special case: ']' is the first character. + if (*I == ']') { + if (++I == E) { + H.HandleIncompleteScanList(start, I - 1); + return true; + } + } + + // Look for a ']' character which denotes the end of the scan list. + while (*I != ']') { + if (++I == E) { + H.HandleIncompleteScanList(start, I - 1); + return true; + } + } + + CS.setEndScanList(I); + return false; +} + +// FIXME: Much of this is copy-paste from ParsePrintfSpecifier. +// We can possibly refactor. +static ScanfSpecifierResult ParseScanfSpecifier(FormatStringHandler &H, + const char *&Beg, + const char *E, + unsigned &argIndex) { + + using namespace clang::analyze_scanf; + const char *I = Beg; + const char *Start = 0; + UpdateOnReturn <const char*> UpdateBeg(Beg, I); + + // Look for a '%' character that indicates the start of a format specifier. + for ( ; I != E ; ++I) { + char c = *I; + if (c == '\0') { + // Detect spurious null characters, which are likely errors. + H.HandleNullChar(I); + return true; + } + if (c == '%') { + Start = I++; // Record the start of the format specifier. + break; + } + } + + // No format specifier found? + if (!Start) + return false; + + if (I == E) { + // No more characters left? + H.HandleIncompleteSpecifier(Start, E - Start); + return true; + } + + ScanfSpecifier FS; + if (ParseArgPosition(H, FS, Start, I, E)) + return true; + + if (I == E) { + // No more characters left? + H.HandleIncompleteSpecifier(Start, E - Start); + return true; + } + + // Look for '*' flag if it is present. + if (*I == '*') { + FS.setSuppressAssignment(I); + if (++I == E) { + H.HandleIncompleteSpecifier(Start, E - Start); + return true; + } + } + + // Look for the field width (if any). Unlike printf, this is either + // a fixed integer or isn't present. + const OptionalAmount &Amt = clang::analyze_format_string::ParseAmount(I, E); + if (Amt.getHowSpecified() != OptionalAmount::NotSpecified) { + assert(Amt.getHowSpecified() == OptionalAmount::Constant); + FS.setFieldWidth(Amt); + + if (I == E) { + // No more characters left? + H.HandleIncompleteSpecifier(Start, E - Start); + return true; + } + } + + // Look for the length modifier. + if (ParseLengthModifier(FS, I, E) && I == E) { + // No more characters left? + H.HandleIncompleteSpecifier(Start, E - Start); + return true; + } + + // Detect spurious null characters, which are likely errors. + if (*I == '\0') { + H.HandleNullChar(I); + return true; + } + + // Finally, look for the conversion specifier. + const char *conversionPosition = I++; + ScanfConversionSpecifier::Kind k = ScanfConversionSpecifier::InvalidSpecifier; + switch (*conversionPosition) { + default: + break; + case '%': k = ConversionSpecifier::PercentArg; break; + case 'A': k = ConversionSpecifier::AArg; break; + case 'E': k = ConversionSpecifier::EArg; break; + case 'F': k = ConversionSpecifier::FArg; break; + case 'G': k = ConversionSpecifier::GArg; break; + case 'X': k = ConversionSpecifier::XArg; break; + case 'a': k = ConversionSpecifier::aArg; break; + case 'd': k = ConversionSpecifier::dArg; break; + case 'e': k = ConversionSpecifier::eArg; break; + case 'f': k = ConversionSpecifier::fArg; break; + case 'g': k = ConversionSpecifier::gArg; break; + case 'i': k = ConversionSpecifier::iArg; break; + case 'n': k = ConversionSpecifier::nArg; break; + case 'c': k = ConversionSpecifier::cArg; break; + case 'C': k = ConversionSpecifier::CArg; break; + case 'S': k = ConversionSpecifier::SArg; break; + case '[': k = ConversionSpecifier::ScanListArg; break; + case 'u': k = ConversionSpecifier::uArg; break; + case 'x': k = ConversionSpecifier::xArg; break; + case 'o': k = ConversionSpecifier::oArg; break; + case 's': k = ConversionSpecifier::sArg; break; + case 'p': k = ConversionSpecifier::pArg; break; + } + ScanfConversionSpecifier CS(conversionPosition, k); + if (k == ScanfConversionSpecifier::ScanListArg) { + if (!ParseScanList(H, CS, I, E)) + return true; + } + FS.setConversionSpecifier(CS); + if (CS.consumesDataArgument() && !FS.getSuppressAssignment() + && !FS.usesPositionalArg()) + FS.setArgIndex(argIndex++); + + // FIXME: '%' and '*' doesn't make sense. Issue a warning. + // FIXME: 'ConsumedSoFar' and '*' doesn't make sense. + + if (k == ScanfConversionSpecifier::InvalidSpecifier) { + // Assume the conversion takes one argument. + return !H.HandleInvalidScanfConversionSpecifier(FS, Beg, I - Beg); + } + return ScanfSpecifierResult(Start, FS); +} + +bool clang::analyze_format_string::ParseScanfString(FormatStringHandler &H, + const char *I, + const char *E) { + + unsigned argIndex = 0; + + // Keep looking for a format specifier until we have exhausted the string. + while (I != E) { + const ScanfSpecifierResult &FSR = ParseScanfSpecifier(H, I, E, argIndex); + // Did a fail-stop error of any kind occur when parsing the specifier? + // If so, don't do any more processing. + if (FSR.shouldStop()) + return true;; + // Did we exhaust the string or encounter an error that + // we can recover from? + if (!FSR.hasValue()) + continue; + // We have a format specifier. Pass it to the callback. + if (!H.HandleScanfSpecifier(FSR.getValue(), FSR.getStart(), + I - FSR.getStart())) { + return true; + } + } + assert(I == E && "Format string not exhausted"); + return false; +} + + diff --git a/contrib/llvm/tools/clang/lib/Analysis/UninitializedValues.cpp b/contrib/llvm/tools/clang/lib/Analysis/UninitializedValues.cpp new file mode 100644 index 0000000..c08cbed --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/UninitializedValues.cpp @@ -0,0 +1,317 @@ +//==- UninitializedValues.cpp - Find Uninitialized Values -------*- C++ --*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements Uninitialized Values analysis for source-level CFGs. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Analyses/UninitializedValues.h" +#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" +#include "clang/Analysis/AnalysisDiagnostic.h" +#include "clang/AST/ASTContext.h" +#include "clang/Analysis/FlowSensitive/DataflowSolver.h" + +#include "llvm/ADT/SmallPtrSet.h" + +using namespace clang; + +//===----------------------------------------------------------------------===// +// Dataflow initialization logic. +//===----------------------------------------------------------------------===// + +namespace { + +class RegisterDecls + : public CFGRecStmtDeclVisitor<RegisterDecls> { + + UninitializedValues::AnalysisDataTy& AD; +public: + RegisterDecls(UninitializedValues::AnalysisDataTy& ad) : AD(ad) {} + + void VisitVarDecl(VarDecl* VD) { AD.Register(VD); } + CFG& getCFG() { return AD.getCFG(); } +}; + +} // end anonymous namespace + +void UninitializedValues::InitializeValues(const CFG& cfg) { + RegisterDecls R(getAnalysisData()); + cfg.VisitBlockStmts(R); +} + +//===----------------------------------------------------------------------===// +// Transfer functions. +//===----------------------------------------------------------------------===// + +namespace { +class TransferFuncs + : public CFGStmtVisitor<TransferFuncs,bool> { + + UninitializedValues::ValTy V; + UninitializedValues::AnalysisDataTy& AD; +public: + TransferFuncs(UninitializedValues::AnalysisDataTy& ad) : AD(ad) {} + + UninitializedValues::ValTy& getVal() { return V; } + CFG& getCFG() { return AD.getCFG(); } + + void SetTopValue(UninitializedValues::ValTy& X) { + X.setDeclValues(AD); + X.resetBlkExprValues(AD); + } + + bool VisitDeclRefExpr(DeclRefExpr* DR); + bool VisitBinaryOperator(BinaryOperator* B); + bool VisitUnaryOperator(UnaryOperator* U); + bool VisitStmt(Stmt* S); + bool VisitCallExpr(CallExpr* C); + bool VisitDeclStmt(DeclStmt* D); + bool VisitAbstractConditionalOperator(AbstractConditionalOperator* C); + bool BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S); + + bool Visit(Stmt *S); + bool BlockStmt_VisitExpr(Expr* E); + + void VisitTerminator(CFGBlock* B) { } + + void setCurrentBlock(const CFGBlock *block) {} +}; + +static const bool Initialized = false; +static const bool Uninitialized = true; + +bool TransferFuncs::VisitDeclRefExpr(DeclRefExpr* DR) { + + if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) + if (VD->isLocalVarDecl()) { + + if (AD.Observer) + AD.Observer->ObserveDeclRefExpr(V, AD, DR, VD); + + // Pseudo-hack to prevent cascade of warnings. If an accessed variable + // is uninitialized, then we are already going to flag a warning for + // this variable, which a "source" of uninitialized values. + // We can otherwise do a full "taint" of uninitialized values. The + // client has both options by toggling AD.FullUninitTaint. + + if (AD.FullUninitTaint) + return V(VD,AD); + } + + return Initialized; +} + +static VarDecl* FindBlockVarDecl(Expr* E) { + + // Blast through casts and parentheses to find any DeclRefExprs that + // refer to a block VarDecl. + + if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(E->IgnoreParenCasts())) + if (VarDecl* VD = dyn_cast<VarDecl>(DR->getDecl())) + if (VD->isLocalVarDecl()) return VD; + + return NULL; +} + +bool TransferFuncs::VisitBinaryOperator(BinaryOperator* B) { + + if (VarDecl* VD = FindBlockVarDecl(B->getLHS())) + if (B->isAssignmentOp()) { + if (B->getOpcode() == BO_Assign) + return V(VD,AD) = Visit(B->getRHS()); + else // Handle +=, -=, *=, etc. We do want '&', not '&&'. + return V(VD,AD) = Visit(B->getLHS()) & Visit(B->getRHS()); + } + + return VisitStmt(B); +} + +bool TransferFuncs::VisitDeclStmt(DeclStmt* S) { + for (DeclStmt::decl_iterator I=S->decl_begin(), E=S->decl_end(); I!=E; ++I) { + VarDecl *VD = dyn_cast<VarDecl>(*I); + if (VD && VD->isLocalVarDecl()) { + if (Stmt* I = VD->getInit()) { + // Visit the subexpression to check for uses of uninitialized values, + // even if we don't propagate that value. + bool isSubExprUninit = Visit(I); + V(VD,AD) = AD.FullUninitTaint ? isSubExprUninit : Initialized; + } + else { + // Special case for declarations of array types. For things like: + // + // char x[10]; + // + // we should treat "x" as being initialized, because the variable + // "x" really refers to the memory block. Clearly x[1] is + // uninitialized, but expressions like "(char *) x" really do refer to + // an initialized value. This simple dataflow analysis does not reason + // about the contents of arrays, although it could be potentially + // extended to do so if the array were of constant size. + if (VD->getType()->isArrayType()) + V(VD,AD) = Initialized; + else + V(VD,AD) = Uninitialized; + } + } + } + return Uninitialized; // Value is never consumed. +} + +bool TransferFuncs::VisitCallExpr(CallExpr* C) { + VisitChildren(C); + return Initialized; +} + +bool TransferFuncs::VisitUnaryOperator(UnaryOperator* U) { + switch (U->getOpcode()) { + case UO_AddrOf: { + VarDecl* VD = FindBlockVarDecl(U->getSubExpr()); + if (VD && VD->isLocalVarDecl()) + return V(VD,AD) = Initialized; + break; + } + + default: + break; + } + + return Visit(U->getSubExpr()); +} + +bool +TransferFuncs::BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt* S) { + // This represents a use of the 'collection' + bool x = Visit(S->getCollection()); + + if (x == Uninitialized) + return Uninitialized; + + // This represents an initialization of the 'element' value. + Stmt* Element = S->getElement(); + VarDecl* VD = 0; + + if (DeclStmt* DS = dyn_cast<DeclStmt>(Element)) + VD = cast<VarDecl>(DS->getSingleDecl()); + else { + Expr* ElemExpr = cast<Expr>(Element)->IgnoreParens(); + + // Initialize the value of the reference variable. + if (DeclRefExpr* DR = dyn_cast<DeclRefExpr>(ElemExpr)) + VD = cast<VarDecl>(DR->getDecl()); + else + return Visit(ElemExpr); + } + + V(VD,AD) = Initialized; + return Initialized; +} + + +bool TransferFuncs:: +VisitAbstractConditionalOperator(AbstractConditionalOperator* C) { + Visit(C->getCond()); + + bool rhsResult = Visit(C->getFalseExpr()); + // Handle the GNU extension for missing LHS. + if (isa<ConditionalOperator>(C)) + return Visit(C->getTrueExpr()) & rhsResult; // Yes: we want &, not &&. + else + return rhsResult; +} + +bool TransferFuncs::VisitStmt(Stmt* S) { + bool x = Initialized; + + // We don't stop at the first subexpression that is Uninitialized because + // evaluating some subexpressions may result in propogating "Uninitialized" + // or "Initialized" to variables referenced in the other subexpressions. + for (Stmt::child_range I = S->children(); I; ++I) + if (*I && Visit(*I) == Uninitialized) x = Uninitialized; + + return x; +} + +bool TransferFuncs::Visit(Stmt *S) { + if (AD.isTracked(static_cast<Expr*>(S))) return V(static_cast<Expr*>(S),AD); + else return static_cast<CFGStmtVisitor<TransferFuncs,bool>*>(this)->Visit(S); +} + +bool TransferFuncs::BlockStmt_VisitExpr(Expr* E) { + bool x = static_cast<CFGStmtVisitor<TransferFuncs,bool>*>(this)->Visit(E); + if (AD.isTracked(E)) V(E,AD) = x; + return x; +} + +} // end anonymous namespace + +//===----------------------------------------------------------------------===// +// Merge operator. +// +// In our transfer functions we take the approach that any +// combination of uninitialized values, e.g. +// Uninitialized + ___ = Uninitialized. +// +// Merges take the same approach, preferring soundness. At a confluence point, +// if any predecessor has a variable marked uninitialized, the value is +// uninitialized at the confluence point. +//===----------------------------------------------------------------------===// + +namespace { + typedef StmtDeclBitVector_Types::Union Merge; + typedef DataflowSolver<UninitializedValues,TransferFuncs,Merge> Solver; +} + +//===----------------------------------------------------------------------===// +// Uninitialized values checker. Scan an AST and flag variable uses +//===----------------------------------------------------------------------===// + +UninitializedValues_ValueTypes::ObserverTy::~ObserverTy() {} + +namespace { +class UninitializedValuesChecker + : public UninitializedValues::ObserverTy { + + ASTContext &Ctx; + Diagnostic &Diags; + llvm::SmallPtrSet<VarDecl*,10> AlreadyWarned; + +public: + UninitializedValuesChecker(ASTContext &ctx, Diagnostic &diags) + : Ctx(ctx), Diags(diags) {} + + virtual void ObserveDeclRefExpr(UninitializedValues::ValTy& V, + UninitializedValues::AnalysisDataTy& AD, + DeclRefExpr* DR, VarDecl* VD) { + + assert ( AD.isTracked(VD) && "Unknown VarDecl."); + + if (V(VD,AD) == Uninitialized) + if (AlreadyWarned.insert(VD)) + Diags.Report(Ctx.getFullLoc(DR->getSourceRange().getBegin()), + diag::warn_uninit_val); + } +}; +} // end anonymous namespace + +namespace clang { +void CheckUninitializedValues(CFG& cfg, ASTContext &Ctx, Diagnostic &Diags, + bool FullUninitTaint) { + + // Compute the uninitialized values information. + UninitializedValues U(cfg); + U.getAnalysisData().FullUninitTaint = FullUninitTaint; + Solver S(U); + S.runOnCFG(cfg); + + // Scan for DeclRefExprs that use uninitialized values. + UninitializedValuesChecker Observer(Ctx,Diags); + U.getAnalysisData().Observer = &Observer; + S.runOnAllBlocks(cfg); +} +} // end namespace clang diff --git a/contrib/llvm/tools/clang/lib/Analysis/UninitializedValuesV2.cpp b/contrib/llvm/tools/clang/lib/Analysis/UninitializedValuesV2.cpp new file mode 100644 index 0000000..75eccbf --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/UninitializedValuesV2.cpp @@ -0,0 +1,610 @@ +//==- UninitializedValuesV2.cpp - Find Uninitialized Values -----*- C++ --*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements uninitialized values analysis for source-level CFGs. +// +//===----------------------------------------------------------------------===// + +#include <utility> +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" +#include "clang/AST/Decl.h" +#include "clang/Analysis/CFG.h" +#include "clang/Analysis/AnalysisContext.h" +#include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" +#include "clang/Analysis/Analyses/UninitializedValuesV2.h" +#include "clang/Analysis/Support/SaveAndRestore.h" + +using namespace clang; + +static bool isTrackedVar(const VarDecl *vd, const DeclContext *dc) { + return vd->isLocalVarDecl() && !vd->hasGlobalStorage() && + vd->getType()->isScalarType() && + vd->getDeclContext() == dc; +} + +//------------------------------------------------------------------------====// +// DeclToBit: a mapping from Decls we track to bitvector indices. +//====------------------------------------------------------------------------// + +namespace { +class DeclToBit { + llvm::DenseMap<const VarDecl *, unsigned> map; +public: + DeclToBit() {} + + /// Compute the actual mapping from declarations to bits. + void computeMap(const DeclContext &dc); + + /// Return the number of declarations in the map. + unsigned size() const { return map.size(); } + + /// Returns the bit vector index for a given declaration. + llvm::Optional<unsigned> getBitVectorIndex(const VarDecl *d); +}; +} + +void DeclToBit::computeMap(const DeclContext &dc) { + unsigned count = 0; + DeclContext::specific_decl_iterator<VarDecl> I(dc.decls_begin()), + E(dc.decls_end()); + for ( ; I != E; ++I) { + const VarDecl *vd = *I; + if (isTrackedVar(vd, &dc)) + map[vd] = count++; + } +} + +llvm::Optional<unsigned> DeclToBit::getBitVectorIndex(const VarDecl *d) { + llvm::DenseMap<const VarDecl *, unsigned>::iterator I = map.find(d); + if (I == map.end()) + return llvm::Optional<unsigned>(); + return I->second; +} + +//------------------------------------------------------------------------====// +// CFGBlockValues: dataflow values for CFG blocks. +//====------------------------------------------------------------------------// + +typedef std::pair<llvm::BitVector *, llvm::BitVector *> BVPair; + +namespace { +class CFGBlockValues { + const CFG &cfg; + BVPair *vals; + llvm::BitVector scratch; + DeclToBit declToBit; + + llvm::BitVector &lazyCreate(llvm::BitVector *&bv); +public: + CFGBlockValues(const CFG &cfg); + ~CFGBlockValues(); + + void computeSetOfDeclarations(const DeclContext &dc); + llvm::BitVector &getBitVector(const CFGBlock *block, + const CFGBlock *dstBlock); + + BVPair &getBitVectors(const CFGBlock *block, bool shouldLazyCreate); + + void mergeIntoScratch(llvm::BitVector const &source, bool isFirst); + bool updateBitVectorWithScratch(const CFGBlock *block); + bool updateBitVectors(const CFGBlock *block, const BVPair &newVals); + + bool hasNoDeclarations() const { + return declToBit.size() == 0; + } + + void resetScratch(); + llvm::BitVector &getScratch() { return scratch; } + + llvm::BitVector::reference operator[](const VarDecl *vd); +}; +} + +CFGBlockValues::CFGBlockValues(const CFG &c) : cfg(c), vals(0) { + unsigned n = cfg.getNumBlockIDs(); + if (!n) + return; + vals = new std::pair<llvm::BitVector*, llvm::BitVector*>[n]; + memset(vals, 0, sizeof(*vals) * n); +} + +CFGBlockValues::~CFGBlockValues() { + unsigned n = cfg.getNumBlockIDs(); + if (n == 0) + return; + for (unsigned i = 0; i < n; ++i) { + delete vals[i].first; + delete vals[i].second; + } + delete [] vals; +} + +void CFGBlockValues::computeSetOfDeclarations(const DeclContext &dc) { + declToBit.computeMap(dc); + scratch.resize(declToBit.size()); +} + +llvm::BitVector &CFGBlockValues::lazyCreate(llvm::BitVector *&bv) { + if (!bv) + bv = new llvm::BitVector(declToBit.size()); + return *bv; +} + +/// This function pattern matches for a '&&' or '||' that appears at +/// the beginning of a CFGBlock that also (1) has a terminator and +/// (2) has no other elements. If such an expression is found, it is returned. +static BinaryOperator *getLogicalOperatorInChain(const CFGBlock *block) { + if (block->empty()) + return 0; + + CFGStmt cstmt = block->front().getAs<CFGStmt>(); + BinaryOperator *b = llvm::dyn_cast_or_null<BinaryOperator>(cstmt.getStmt()); + + if (!b || !b->isLogicalOp()) + return 0; + + if (block->pred_size() == 2 && + ((block->succ_size() == 2 && block->getTerminatorCondition() == b) || + block->size() == 1)) + return b; + + return 0; +} + +llvm::BitVector &CFGBlockValues::getBitVector(const CFGBlock *block, + const CFGBlock *dstBlock) { + unsigned idx = block->getBlockID(); + if (dstBlock && getLogicalOperatorInChain(block)) { + if (*block->succ_begin() == dstBlock) + return lazyCreate(vals[idx].first); + assert(*(block->succ_begin()+1) == dstBlock); + return lazyCreate(vals[idx].second); + } + + assert(vals[idx].second == 0); + return lazyCreate(vals[idx].first); +} + +BVPair &CFGBlockValues::getBitVectors(const clang::CFGBlock *block, + bool shouldLazyCreate) { + unsigned idx = block->getBlockID(); + lazyCreate(vals[idx].first); + if (shouldLazyCreate) + lazyCreate(vals[idx].second); + return vals[idx]; +} + +void CFGBlockValues::mergeIntoScratch(llvm::BitVector const &source, + bool isFirst) { + if (isFirst) + scratch = source; + else + scratch |= source; +} +#if 0 +static void printVector(const CFGBlock *block, llvm::BitVector &bv, + unsigned num) { + + llvm::errs() << block->getBlockID() << " :"; + for (unsigned i = 0; i < bv.size(); ++i) { + llvm::errs() << ' ' << bv[i]; + } + llvm::errs() << " : " << num << '\n'; +} +#endif + +bool CFGBlockValues::updateBitVectorWithScratch(const CFGBlock *block) { + llvm::BitVector &dst = getBitVector(block, 0); + bool changed = (dst != scratch); + if (changed) + dst = scratch; +#if 0 + printVector(block, scratch, 0); +#endif + return changed; +} + +bool CFGBlockValues::updateBitVectors(const CFGBlock *block, + const BVPair &newVals) { + BVPair &vals = getBitVectors(block, true); + bool changed = *newVals.first != *vals.first || + *newVals.second != *vals.second; + *vals.first = *newVals.first; + *vals.second = *newVals.second; +#if 0 + printVector(block, *vals.first, 1); + printVector(block, *vals.second, 2); +#endif + return changed; +} + +void CFGBlockValues::resetScratch() { + scratch.reset(); +} + +llvm::BitVector::reference CFGBlockValues::operator[](const VarDecl *vd) { + const llvm::Optional<unsigned> &idx = declToBit.getBitVectorIndex(vd); + assert(idx.hasValue()); + return scratch[idx.getValue()]; +} + +//------------------------------------------------------------------------====// +// Worklist: worklist for dataflow analysis. +//====------------------------------------------------------------------------// + +namespace { +class DataflowWorklist { + llvm::SmallVector<const CFGBlock *, 20> worklist; + llvm::BitVector enqueuedBlocks; +public: + DataflowWorklist(const CFG &cfg) : enqueuedBlocks(cfg.getNumBlockIDs()) {} + + void enqueue(const CFGBlock *block); + void enqueueSuccessors(const CFGBlock *block); + const CFGBlock *dequeue(); + +}; +} + +void DataflowWorklist::enqueue(const CFGBlock *block) { + if (!block) + return; + unsigned idx = block->getBlockID(); + if (enqueuedBlocks[idx]) + return; + worklist.push_back(block); + enqueuedBlocks[idx] = true; +} + +void DataflowWorklist::enqueueSuccessors(const clang::CFGBlock *block) { + for (CFGBlock::const_succ_iterator I = block->succ_begin(), + E = block->succ_end(); I != E; ++I) { + enqueue(*I); + } +} + +const CFGBlock *DataflowWorklist::dequeue() { + if (worklist.empty()) + return 0; + const CFGBlock *b = worklist.back(); + worklist.pop_back(); + enqueuedBlocks[b->getBlockID()] = false; + return b; +} + +//------------------------------------------------------------------------====// +// Transfer function for uninitialized values analysis. +//====------------------------------------------------------------------------// + +static const bool Initialized = false; +static const bool Uninitialized = true; + +namespace { +class FindVarResult { + const VarDecl *vd; + const DeclRefExpr *dr; +public: + FindVarResult(VarDecl *vd, DeclRefExpr *dr) : vd(vd), dr(dr) {} + + const DeclRefExpr *getDeclRefExpr() const { return dr; } + const VarDecl *getDecl() const { return vd; } +}; + +class TransferFunctions : public CFGRecStmtVisitor<TransferFunctions> { + CFGBlockValues &vals; + const CFG &cfg; + AnalysisContext ∾ + UninitVariablesHandler *handler; + const DeclRefExpr *currentDR; + const Expr *currentVoidCast; + const bool flagBlockUses; +public: + TransferFunctions(CFGBlockValues &vals, const CFG &cfg, + AnalysisContext &ac, + UninitVariablesHandler *handler, + bool flagBlockUses) + : vals(vals), cfg(cfg), ac(ac), handler(handler), currentDR(0), + currentVoidCast(0), flagBlockUses(flagBlockUses) {} + + const CFG &getCFG() { return cfg; } + void reportUninit(const DeclRefExpr *ex, const VarDecl *vd); + + void VisitBlockExpr(BlockExpr *be); + void VisitDeclStmt(DeclStmt *ds); + void VisitDeclRefExpr(DeclRefExpr *dr); + void VisitUnaryOperator(UnaryOperator *uo); + void VisitBinaryOperator(BinaryOperator *bo); + void VisitCastExpr(CastExpr *ce); + void VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *se); + void BlockStmt_VisitObjCForCollectionStmt(ObjCForCollectionStmt *fs); + + bool isTrackedVar(const VarDecl *vd) { + return ::isTrackedVar(vd, cast<DeclContext>(ac.getDecl())); + } + + FindVarResult findBlockVarDecl(Expr *ex); +}; +} + +void TransferFunctions::reportUninit(const DeclRefExpr *ex, + const VarDecl *vd) { + if (handler) handler->handleUseOfUninitVariable(ex, vd); +} + +FindVarResult TransferFunctions::findBlockVarDecl(Expr* ex) { + if (DeclRefExpr* dr = dyn_cast<DeclRefExpr>(ex->IgnoreParenCasts())) + if (VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl())) + if (isTrackedVar(vd)) + return FindVarResult(vd, dr); + return FindVarResult(0, 0); +} + +void TransferFunctions::BlockStmt_VisitObjCForCollectionStmt( + ObjCForCollectionStmt *fs) { + + Visit(fs->getCollection()); + + // This represents an initialization of the 'element' value. + Stmt *element = fs->getElement(); + const VarDecl* vd = 0; + + if (DeclStmt* ds = dyn_cast<DeclStmt>(element)) { + vd = cast<VarDecl>(ds->getSingleDecl()); + if (!isTrackedVar(vd)) + vd = 0; + } + else { + // Initialize the value of the reference variable. + const FindVarResult &res = findBlockVarDecl(cast<Expr>(element)); + vd = res.getDecl(); + if (!vd) { + Visit(element); + return; + } + } + + if (vd) + vals[vd] = Initialized; +} + +void TransferFunctions::VisitBlockExpr(BlockExpr *be) { + if (!flagBlockUses || !handler) + return; + AnalysisContext::referenced_decls_iterator i, e; + llvm::tie(i, e) = ac.getReferencedBlockVars(be->getBlockDecl()); + for ( ; i != e; ++i) { + const VarDecl *vd = *i; + if (vd->getAttr<BlocksAttr>() || !vd->hasLocalStorage() || + !isTrackedVar(vd)) + continue; + if (vals[vd] == Uninitialized) + handler->handleUseOfUninitVariable(be, vd); + } +} + +void TransferFunctions::VisitDeclStmt(DeclStmt *ds) { + for (DeclStmt::decl_iterator DI = ds->decl_begin(), DE = ds->decl_end(); + DI != DE; ++DI) { + if (VarDecl *vd = dyn_cast<VarDecl>(*DI)) { + if (isTrackedVar(vd)) { + vals[vd] = Uninitialized; + if (Stmt *init = vd->getInit()) { + Visit(init); + vals[vd] = Initialized; + } + } + else if (Stmt *init = vd->getInit()) { + Visit(init); + } + } + } +} + +void TransferFunctions::VisitDeclRefExpr(DeclRefExpr *dr) { + // We assume that DeclRefExprs wrapped in an lvalue-to-rvalue cast + // cannot be block-level expressions. Therefore, we determine if + // a DeclRefExpr is involved in a "load" by comparing it to the current + // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr. + // If a DeclRefExpr is not involved in a load, we are essentially computing + // its address, either for assignment to a reference or via the '&' operator. + // In such cases, treat the variable as being initialized, since this + // analysis isn't powerful enough to do alias tracking. + if (dr != currentDR) + if (const VarDecl *vd = dyn_cast<VarDecl>(dr->getDecl())) + if (isTrackedVar(vd)) + vals[vd] = Initialized; +} + +void TransferFunctions::VisitBinaryOperator(clang::BinaryOperator *bo) { + if (bo->isAssignmentOp()) { + const FindVarResult &res = findBlockVarDecl(bo->getLHS()); + if (const VarDecl* vd = res.getDecl()) { + // We assume that DeclRefExprs wrapped in a BinaryOperator "assignment" + // cannot be block-level expressions. Therefore, we determine if + // a DeclRefExpr is involved in a "load" by comparing it to the current + // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr. + SaveAndRestore<const DeclRefExpr*> lastDR(currentDR, + res.getDeclRefExpr()); + Visit(bo->getRHS()); + Visit(bo->getLHS()); + + llvm::BitVector::reference bit = vals[vd]; + if (bit == Uninitialized) { + if (bo->getOpcode() != BO_Assign) + reportUninit(res.getDeclRefExpr(), vd); + bit = Initialized; + } + return; + } + } + Visit(bo->getRHS()); + Visit(bo->getLHS()); +} + +void TransferFunctions::VisitUnaryOperator(clang::UnaryOperator *uo) { + switch (uo->getOpcode()) { + case clang::UO_PostDec: + case clang::UO_PostInc: + case clang::UO_PreDec: + case clang::UO_PreInc: { + const FindVarResult &res = findBlockVarDecl(uo->getSubExpr()); + if (const VarDecl *vd = res.getDecl()) { + // We assume that DeclRefExprs wrapped in a unary operator ++/-- + // cannot be block-level expressions. Therefore, we determine if + // a DeclRefExpr is involved in a "load" by comparing it to the current + // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr. + SaveAndRestore<const DeclRefExpr*> lastDR(currentDR, + res.getDeclRefExpr()); + Visit(uo->getSubExpr()); + + llvm::BitVector::reference bit = vals[vd]; + if (bit == Uninitialized) { + reportUninit(res.getDeclRefExpr(), vd); + bit = Initialized; + } + return; + } + break; + } + default: + break; + } + Visit(uo->getSubExpr()); +} + +void TransferFunctions::VisitCastExpr(clang::CastExpr *ce) { + if (ce->getCastKind() == CK_LValueToRValue) { + const FindVarResult &res = findBlockVarDecl(ce->getSubExpr()); + if (const VarDecl *vd = res.getDecl()) { + // We assume that DeclRefExprs wrapped in an lvalue-to-rvalue cast + // cannot be block-level expressions. Therefore, we determine if + // a DeclRefExpr is involved in a "load" by comparing it to the current + // DeclRefExpr found when analyzing the last lvalue-to-rvalue CastExpr. + // Here we update 'currentDR' to be the one associated with this + // lvalue-to-rvalue cast. Then, when we analyze the DeclRefExpr, we + // will know that we are not computing its lvalue for other purposes + // than to perform a load. + SaveAndRestore<const DeclRefExpr*> lastDR(currentDR, + res.getDeclRefExpr()); + Visit(ce->getSubExpr()); + if (currentVoidCast != ce && vals[vd] == Uninitialized) { + reportUninit(res.getDeclRefExpr(), vd); + // Don't cascade warnings. + vals[vd] = Initialized; + } + return; + } + } + else if (CStyleCastExpr *cse = dyn_cast<CStyleCastExpr>(ce)) { + if (cse->getType()->isVoidType()) { + // e.g. (void) x; + SaveAndRestore<const Expr *> + lastVoidCast(currentVoidCast, cse->getSubExpr()->IgnoreParens()); + Visit(cse->getSubExpr()); + return; + } + } + Visit(ce->getSubExpr()); +} + +void TransferFunctions::VisitSizeOfAlignOfExpr(SizeOfAlignOfExpr *se) { + if (se->isSizeOf()) { + if (se->getType()->isConstantSizeType()) + return; + // Handle VLAs. + Visit(se->getArgumentExpr()); + } +} + +//------------------------------------------------------------------------====// +// High-level "driver" logic for uninitialized values analysis. +//====------------------------------------------------------------------------// + +static bool runOnBlock(const CFGBlock *block, const CFG &cfg, + AnalysisContext &ac, CFGBlockValues &vals, + UninitVariablesHandler *handler = 0, + bool flagBlockUses = false) { + + if (const BinaryOperator *b = getLogicalOperatorInChain(block)) { + CFGBlock::const_pred_iterator itr = block->pred_begin(); + BVPair vA = vals.getBitVectors(*itr, false); + ++itr; + BVPair vB = vals.getBitVectors(*itr, false); + + BVPair valsAB; + + if (b->getOpcode() == BO_LAnd) { + // Merge the 'F' bits from the first and second. + vals.mergeIntoScratch(*(vA.second ? vA.second : vA.first), true); + vals.mergeIntoScratch(*(vB.second ? vB.second : vB.first), false); + valsAB.first = vA.first; + valsAB.second = &vals.getScratch(); + } + else { + // Merge the 'T' bits from the first and second. + assert(b->getOpcode() == BO_LOr); + vals.mergeIntoScratch(*vA.first, true); + vals.mergeIntoScratch(*vB.first, false); + valsAB.first = &vals.getScratch(); + valsAB.second = vA.second ? vA.second : vA.first; + } + return vals.updateBitVectors(block, valsAB); + } + + // Default behavior: merge in values of predecessor blocks. + vals.resetScratch(); + bool isFirst = true; + for (CFGBlock::const_pred_iterator I = block->pred_begin(), + E = block->pred_end(); I != E; ++I) { + vals.mergeIntoScratch(vals.getBitVector(*I, block), isFirst); + isFirst = false; + } + // Apply the transfer function. + TransferFunctions tf(vals, cfg, ac, handler, flagBlockUses); + for (CFGBlock::const_iterator I = block->begin(), E = block->end(); + I != E; ++I) { + if (const CFGStmt *cs = dyn_cast<CFGStmt>(&*I)) { + tf.BlockStmt_Visit(cs->getStmt()); + } + } + return vals.updateBitVectorWithScratch(block); +} + +void clang::runUninitializedVariablesAnalysis(const DeclContext &dc, + const CFG &cfg, + AnalysisContext &ac, + UninitVariablesHandler &handler) { + CFGBlockValues vals(cfg); + vals.computeSetOfDeclarations(dc); + if (vals.hasNoDeclarations()) + return; + DataflowWorklist worklist(cfg); + llvm::BitVector previouslyVisited(cfg.getNumBlockIDs()); + + worklist.enqueueSuccessors(&cfg.getEntry()); + + while (const CFGBlock *block = worklist.dequeue()) { + // Did the block change? + bool changed = runOnBlock(block, cfg, ac, vals); + if (changed || !previouslyVisited[block->getBlockID()]) + worklist.enqueueSuccessors(block); + previouslyVisited[block->getBlockID()] = true; + } + + // Run through the blocks one more time, and report uninitialized variabes. + for (CFG::const_iterator BI = cfg.begin(), BE = cfg.end(); BI != BE; ++BI) { + runOnBlock(*BI, cfg, ac, vals, &handler, /* flagBlockUses */ true); + } +} + +UninitVariablesHandler::~UninitVariablesHandler() {} + |
