diff options
Diffstat (limited to 'contrib/llvm/tools/clang/lib/Analysis')
16 files changed, 2557 insertions, 752 deletions
diff --git a/contrib/llvm/tools/clang/lib/Analysis/AnalysisContext.cpp b/contrib/llvm/tools/clang/lib/Analysis/AnalysisDeclContext.cpp index 3dd194b..659cc6d 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/AnalysisContext.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/AnalysisDeclContext.cpp @@ -1,4 +1,4 @@ -//== AnalysisContext.cpp - Analysis context for Path Sens analysis -*- C++ -*-// +//== AnalysisDeclContext.cpp - Analysis context for Path Sens analysis -*- C++ -*-// // // The LLVM Compiler Infrastructure // @@ -7,7 +7,7 @@ // //===----------------------------------------------------------------------===// // -// This file defines AnalysisContext, a class that manages the analysis context +// This file defines AnalysisDeclContext, a class that manages the analysis context // data for path sensitive analysis. // //===----------------------------------------------------------------------===// @@ -24,18 +24,21 @@ #include "clang/Analysis/CFG.h" #include "clang/Analysis/CFGStmtMap.h" #include "clang/Analysis/Support/BumpVector.h" -#include "clang/Analysis/Support/SaveAndRestore.h" -#include "llvm/ADT/SmallSet.h" +#include "llvm/Support/SaveAndRestore.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/Support/ErrorHandling.h" using namespace clang; typedef llvm::DenseMap<const void *, ManagedAnalysis *> ManagedAnalysisMap; -AnalysisContext::AnalysisContext(const Decl *d, +AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr, + const Decl *d, idx::TranslationUnit *tu, const CFG::BuildOptions &buildOptions) - : D(d), TU(tu), + : Manager(Mgr), + D(d), + TU(tu), cfgBuildOptions(buildOptions), forcedBlkExprs(0), builtCFG(false), @@ -46,9 +49,12 @@ AnalysisContext::AnalysisContext(const Decl *d, cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs; } -AnalysisContext::AnalysisContext(const Decl *d, +AnalysisDeclContext::AnalysisDeclContext(AnalysisDeclContextManager *Mgr, + const Decl *d, idx::TranslationUnit *tu) -: D(d), TU(tu), +: Manager(Mgr), + D(d), + TU(tu), forcedBlkExprs(0), builtCFG(false), builtCompleteCFG(false), @@ -58,7 +64,7 @@ AnalysisContext::AnalysisContext(const Decl *d, cfgBuildOptions.forcedBlkExprs = &forcedBlkExprs; } -AnalysisContextManager::AnalysisContextManager(bool useUnoptimizedCFG, +AnalysisDeclContextManager::AnalysisDeclContextManager(bool useUnoptimizedCFG, bool addImplicitDtors, bool addInitializers) { cfgBuildOptions.PruneTriviallyFalseEdges = !useUnoptimizedCFG; @@ -66,13 +72,13 @@ AnalysisContextManager::AnalysisContextManager(bool useUnoptimizedCFG, cfgBuildOptions.AddInitializers = addInitializers; } -void AnalysisContextManager::clear() { +void AnalysisDeclContextManager::clear() { for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) delete I->second; Contexts.clear(); } -Stmt *AnalysisContext::getBody() const { +Stmt *AnalysisDeclContext::getBody() const { if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) return FD->getBody(); else if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) @@ -86,14 +92,23 @@ Stmt *AnalysisContext::getBody() const { llvm_unreachable("unknown code decl"); } -const ImplicitParamDecl *AnalysisContext::getSelfDecl() const { +const ImplicitParamDecl *AnalysisDeclContext::getSelfDecl() const { if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) return MD->getSelfDecl(); + if (const BlockDecl *BD = dyn_cast<BlockDecl>(D)) { + // See if 'self' was captured by the block. + for (BlockDecl::capture_const_iterator it = BD->capture_begin(), + et = BD->capture_end(); it != et; ++it) { + const VarDecl *VD = it->getVariable(); + if (VD->getName() == "self") + return dyn_cast<ImplicitParamDecl>(VD); + } + } return NULL; } -void AnalysisContext::registerForcedBlockExpression(const Stmt *stmt) { +void AnalysisDeclContext::registerForcedBlockExpression(const Stmt *stmt) { if (!forcedBlkExprs) forcedBlkExprs = new CFG::BuildOptions::ForcedBlkExprs(); // Default construct an entry for 'stmt'. @@ -103,7 +118,7 @@ void AnalysisContext::registerForcedBlockExpression(const Stmt *stmt) { } const CFGBlock * -AnalysisContext::getBlockForRegisteredExpression(const Stmt *stmt) { +AnalysisDeclContext::getBlockForRegisteredExpression(const Stmt *stmt) { assert(forcedBlkExprs); if (const Expr *e = dyn_cast<Expr>(stmt)) stmt = e->IgnoreParens(); @@ -113,7 +128,7 @@ AnalysisContext::getBlockForRegisteredExpression(const Stmt *stmt) { return itr->second; } -CFG *AnalysisContext::getCFG() { +CFG *AnalysisDeclContext::getCFG() { if (!cfgBuildOptions.PruneTriviallyFalseEdges) return getUnoptimizedCFG(); @@ -127,7 +142,7 @@ CFG *AnalysisContext::getCFG() { return cfg.get(); } -CFG *AnalysisContext::getUnoptimizedCFG() { +CFG *AnalysisDeclContext::getUnoptimizedCFG() { if (!builtCompleteCFG) { SaveAndRestore<bool> NotPrune(cfgBuildOptions.PruneTriviallyFalseEdges, false); @@ -140,7 +155,7 @@ CFG *AnalysisContext::getUnoptimizedCFG() { return completeCFG.get(); } -CFGStmtMap *AnalysisContext::getCFGStmtMap() { +CFGStmtMap *AnalysisDeclContext::getCFGStmtMap() { if (cfgStmtMap) return cfgStmtMap.get(); @@ -152,7 +167,7 @@ CFGStmtMap *AnalysisContext::getCFGStmtMap() { return 0; } -CFGReverseBlockReachabilityAnalysis *AnalysisContext::getCFGReachablityAnalysis() { +CFGReverseBlockReachabilityAnalysis *AnalysisDeclContext::getCFGReachablityAnalysis() { if (CFA) return CFA.get(); @@ -164,37 +179,49 @@ CFGReverseBlockReachabilityAnalysis *AnalysisContext::getCFGReachablityAnalysis( return 0; } -void AnalysisContext::dumpCFG() { - getCFG()->dump(getASTContext().getLangOptions()); +void AnalysisDeclContext::dumpCFG(bool ShowColors) { + getCFG()->dump(getASTContext().getLangOpts(), ShowColors); } -ParentMap &AnalysisContext::getParentMap() { +ParentMap &AnalysisDeclContext::getParentMap() { if (!PM) PM.reset(new ParentMap(getBody())); return *PM; } -PseudoConstantAnalysis *AnalysisContext::getPseudoConstantAnalysis() { +PseudoConstantAnalysis *AnalysisDeclContext::getPseudoConstantAnalysis() { if (!PCA) PCA.reset(new PseudoConstantAnalysis(getBody())); return PCA.get(); } -AnalysisContext *AnalysisContextManager::getContext(const Decl *D, +AnalysisDeclContext *AnalysisDeclContextManager::getContext(const Decl *D, idx::TranslationUnit *TU) { - AnalysisContext *&AC = Contexts[D]; + AnalysisDeclContext *&AC = Contexts[D]; if (!AC) - AC = new AnalysisContext(D, TU, cfgBuildOptions); + AC = new AnalysisDeclContext(this, D, TU, cfgBuildOptions); return AC; } +const StackFrameContext * +AnalysisDeclContext::getStackFrame(LocationContext const *Parent, const Stmt *S, + const CFGBlock *Blk, unsigned Idx) { + return getLocationContextManager().getStackFrame(this, Parent, S, Blk, Idx); +} + +LocationContextManager & AnalysisDeclContext::getLocationContextManager() { + assert(Manager && + "Cannot create LocationContexts without an AnalysisDeclContextManager!"); + return Manager->getLocationContextManager(); +} + //===----------------------------------------------------------------------===// // FoldingSet profiling. //===----------------------------------------------------------------------===// void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID, ContextKind ck, - AnalysisContext *ctx, + AnalysisDeclContext *ctx, const LocationContext *parent, const void *data) { ID.AddInteger(ck); @@ -204,15 +231,15 @@ void LocationContext::ProfileCommon(llvm::FoldingSetNodeID &ID, } void StackFrameContext::Profile(llvm::FoldingSetNodeID &ID) { - Profile(ID, getAnalysisContext(), getParent(), CallSite, Block, Index); + Profile(ID, getAnalysisDeclContext(), getParent(), CallSite, Block, Index); } void ScopeContext::Profile(llvm::FoldingSetNodeID &ID) { - Profile(ID, getAnalysisContext(), getParent(), Enter); + Profile(ID, getAnalysisDeclContext(), getParent(), Enter); } void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) { - Profile(ID, getAnalysisContext(), getParent(), BD); + Profile(ID, getAnalysisDeclContext(), getParent(), BD); } //===----------------------------------------------------------------------===// @@ -221,7 +248,7 @@ void BlockInvocationContext::Profile(llvm::FoldingSetNodeID &ID) { template <typename LOC, typename DATA> const LOC* -LocationContextManager::getLocationContext(AnalysisContext *ctx, +LocationContextManager::getLocationContext(AnalysisDeclContext *ctx, const LocationContext *parent, const DATA *d) { llvm::FoldingSetNodeID ID; @@ -238,7 +265,7 @@ LocationContextManager::getLocationContext(AnalysisContext *ctx, } const StackFrameContext* -LocationContextManager::getStackFrame(AnalysisContext *ctx, +LocationContextManager::getStackFrame(AnalysisDeclContext *ctx, const LocationContext *parent, const Stmt *s, const CFGBlock *blk, unsigned idx) { @@ -255,7 +282,7 @@ LocationContextManager::getStackFrame(AnalysisContext *ctx, } const ScopeContext * -LocationContextManager::getScope(AnalysisContext *ctx, +LocationContextManager::getScope(AnalysisDeclContext *ctx, const LocationContext *parent, const Stmt *s) { return getLocationContext<ScopeContext, Stmt>(ctx, parent, s); @@ -308,8 +335,8 @@ namespace { class FindBlockDeclRefExprsVals : public StmtVisitor<FindBlockDeclRefExprsVals>{ BumpVector<const VarDecl*> &BEVals; BumpVectorContext &BC; - llvm::DenseMap<const VarDecl*, unsigned> Visited; - llvm::SmallSet<const DeclContext*, 4> IgnoredContexts; + llvm::SmallPtrSet<const VarDecl*, 4> Visited; + llvm::SmallPtrSet<const DeclContext*, 4> IgnoredContexts; public: FindBlockDeclRefExprsVals(BumpVector<const VarDecl*> &bevals, BumpVectorContext &bc) @@ -326,24 +353,14 @@ public: Visit(child); } - void VisitDeclRefExpr(const DeclRefExpr *DR) { + void VisitDeclRefExpr(DeclRefExpr *DR) { // Non-local variables are also directly modified. - if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) + if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { if (!VD->hasLocalStorage()) { - unsigned &flag = Visited[VD]; - if (!flag) { - flag = 1; + if (Visited.insert(VD)) 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)) + } else if (DR->refersToEnclosingLocal()) { + if (Visited.insert(VD) && IsTrackedDecl(VD)) BEVals.push_back(VD, BC); } } @@ -354,6 +371,16 @@ public: IgnoredContexts.insert(BR->getBlockDecl()); Visit(BR->getBlockDecl()->getBody()); } + + void VisitPseudoObjectExpr(PseudoObjectExpr *PE) { + for (PseudoObjectExpr::semantics_iterator it = PE->semantics_begin(), + et = PE->semantics_end(); it != et; ++it) { + Expr *Semantic = *it; + if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic)) + Semantic = OVE->getSourceExpr(); + Visit(Semantic); + } + } }; } // end anonymous namespace @@ -377,9 +404,9 @@ static DeclVec* LazyInitializeReferencedDecls(const BlockDecl *BD, return BV; } -std::pair<AnalysisContext::referenced_decls_iterator, - AnalysisContext::referenced_decls_iterator> -AnalysisContext::getReferencedBlockVars(const BlockDecl *BD) { +std::pair<AnalysisDeclContext::referenced_decls_iterator, + AnalysisDeclContext::referenced_decls_iterator> +AnalysisDeclContext::getReferencedBlockVars(const BlockDecl *BD) { if (!ReferencedBlockVars) ReferencedBlockVars = new llvm::DenseMap<const BlockDecl*,void*>(); @@ -387,7 +414,7 @@ AnalysisContext::getReferencedBlockVars(const BlockDecl *BD) { return std::make_pair(V->begin(), V->end()); } -ManagedAnalysis *&AnalysisContext::getAnalysisImpl(const void *tag) { +ManagedAnalysis *&AnalysisDeclContext::getAnalysisImpl(const void *tag) { if (!ManagedAnalyses) ManagedAnalyses = new ManagedAnalysisMap(); ManagedAnalysisMap *M = (ManagedAnalysisMap*) ManagedAnalyses; @@ -400,7 +427,7 @@ ManagedAnalysis *&AnalysisContext::getAnalysisImpl(const void *tag) { ManagedAnalysis::~ManagedAnalysis() {} -AnalysisContext::~AnalysisContext() { +AnalysisDeclContext::~AnalysisDeclContext() { delete forcedBlkExprs; delete ReferencedBlockVars; // Release the managed analyses. @@ -412,7 +439,7 @@ AnalysisContext::~AnalysisContext() { } } -AnalysisContextManager::~AnalysisContextManager() { +AnalysisDeclContextManager::~AnalysisDeclContextManager() { for (ContextMap::iterator I = Contexts.begin(), E = Contexts.end(); I!=E; ++I) delete I->second; } diff --git a/contrib/llvm/tools/clang/lib/Analysis/CFG.cpp b/contrib/llvm/tools/clang/lib/Analysis/CFG.cpp index 83c7384..d1334a5 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/CFG.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/CFG.cpp @@ -12,7 +12,7 @@ // //===----------------------------------------------------------------------===// -#include "clang/Analysis/Support/SaveAndRestore.h" +#include "llvm/Support/SaveAndRestore.h" #include "clang/Analysis/CFG.h" #include "clang/AST/DeclCXX.h" #include "clang/AST/StmtVisitor.h" @@ -250,7 +250,7 @@ class CFGBuilder { typedef BlockScopePosPair JumpSource; ASTContext *Context; - llvm::OwningPtr<CFG> cfg; + OwningPtr<CFG> cfg; CFGBlock *Block; CFGBlock *Succ; @@ -286,6 +286,11 @@ class CFGBuilder { CFG::BuildOptions::ForcedBlkExprs::value_type *cachedEntry; const Stmt *lastLookup; + // Caches boolean evaluations of expressions to avoid multiple re-evaluations + // during construction of branches for chained logical operators. + typedef llvm::DenseMap<Expr *, TryResult> CachedBoolEvalsTy; + CachedBoolEvalsTy CachedBoolEvals; + public: explicit CFGBuilder(ASTContext *astContext, const CFG::BuildOptions &buildOpts) @@ -305,7 +310,6 @@ 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, @@ -331,19 +335,23 @@ private: CFGBlock *VisitDeclSubExpr(DeclStmt *DS); CFGBlock *VisitDefaultStmt(DefaultStmt *D); CFGBlock *VisitDoStmt(DoStmt *D); + CFGBlock *VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc); 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 *VisitLambdaExpr(LambdaExpr *L); CFGBlock *VisitMemberExpr(MemberExpr *M, AddStmtChoice asc); CFGBlock *VisitObjCAtCatchStmt(ObjCAtCatchStmt *S); + CFGBlock *VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S); CFGBlock *VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S); CFGBlock *VisitObjCAtThrowStmt(ObjCAtThrowStmt *S); CFGBlock *VisitObjCAtTryStmt(ObjCAtTryStmt *S); CFGBlock *VisitObjCForCollectionStmt(ObjCForCollectionStmt *S); CFGBlock *VisitReturnStmt(ReturnStmt *R); + CFGBlock *VisitPseudoObjectExpr(PseudoObjectExpr *E); CFGBlock *VisitUnaryExprOrTypeTraitExpr(UnaryExprOrTypeTraitExpr *E, AddStmtChoice asc); CFGBlock *VisitStmtExpr(StmtExpr *S, AddStmtChoice asc); @@ -354,6 +362,7 @@ private: CFGBlock *Visit(Stmt *S, AddStmtChoice asc = AddStmtChoice::NotAlwaysAdd); CFGBlock *VisitStmt(Stmt *S, AddStmtChoice asc); CFGBlock *VisitChildren(Stmt *S); + CFGBlock *VisitNoRecurse(Expr *E, AddStmtChoice asc); // Visitors to walk an AST and generate destructors of temporaries in // full expression. @@ -431,18 +440,70 @@ private: return false; return !S->isTypeDependent() && !S->isValueDependent() && - S->Evaluate(outResult, *Context); + S->EvaluateAsRValue(outResult, *Context); } /// 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) { - bool Result; if (!BuildOpts.PruneTriviallyFalseEdges || - S->isTypeDependent() || S->isValueDependent() || - !S->EvaluateAsBooleanCondition(Result, *Context)) + S->isTypeDependent() || S->isValueDependent()) return TryResult(); - return Result; + + if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(S)) { + if (Bop->isLogicalOp()) { + // Check the cache first. + CachedBoolEvalsTy::iterator I = CachedBoolEvals.find(S); + if (I != CachedBoolEvals.end()) + return I->second; // already in map; + + // Retrieve result at first, or the map might be updated. + TryResult Result = evaluateAsBooleanConditionNoCache(S); + CachedBoolEvals[S] = Result; // update or insert + return Result; + } + } + + return evaluateAsBooleanConditionNoCache(S); + } + + /// \brief Evaluate as boolean \param E without using the cache. + TryResult evaluateAsBooleanConditionNoCache(Expr *E) { + if (BinaryOperator *Bop = dyn_cast<BinaryOperator>(E)) { + if (Bop->isLogicalOp()) { + TryResult LHS = tryEvaluateBool(Bop->getLHS()); + if (LHS.isKnown()) { + // We were able to evaluate the LHS, see if we can get away with not + // evaluating the RHS: 0 && X -> 0, 1 || X -> 1 + if (LHS.isTrue() == (Bop->getOpcode() == BO_LOr)) + return LHS.isTrue(); + + TryResult RHS = tryEvaluateBool(Bop->getRHS()); + if (RHS.isKnown()) { + if (Bop->getOpcode() == BO_LOr) + return LHS.isTrue() || RHS.isTrue(); + else + return LHS.isTrue() && RHS.isTrue(); + } + } else { + TryResult RHS = tryEvaluateBool(Bop->getRHS()); + if (RHS.isKnown()) { + // We can't evaluate the LHS; however, sometimes the result + // is determined by the RHS: X && 0 -> 0, X || 1 -> 1. + if (RHS.isTrue() == (Bop->getOpcode() == BO_LOr)) + return RHS.isTrue(); + } + } + + return TryResult(); + } + } + + bool Result; + if (E->EvaluateAsBooleanCondition(Result, *Context)) + return Result; + + return TryResult(); } }; @@ -638,6 +699,52 @@ CFGBlock *CFGBuilder::addInitializer(CXXCtorInitializer *I) { return Block; } +/// \brief Retrieve the type of the temporary object whose lifetime was +/// extended by a local reference with the given initializer. +static QualType getReferenceInitTemporaryType(ASTContext &Context, + const Expr *Init) { + while (true) { + // Skip parentheses. + Init = Init->IgnoreParens(); + + // Skip through cleanups. + if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Init)) { + Init = EWC->getSubExpr(); + continue; + } + + // Skip through the temporary-materialization expression. + if (const MaterializeTemporaryExpr *MTE + = dyn_cast<MaterializeTemporaryExpr>(Init)) { + Init = MTE->GetTemporaryExpr(); + continue; + } + + // Skip derived-to-base and no-op casts. + if (const CastExpr *CE = dyn_cast<CastExpr>(Init)) { + if ((CE->getCastKind() == CK_DerivedToBase || + CE->getCastKind() == CK_UncheckedDerivedToBase || + CE->getCastKind() == CK_NoOp) && + Init->getType()->isRecordType()) { + Init = CE->getSubExpr(); + continue; + } + } + + // Skip member accesses into rvalues. + if (const MemberExpr *ME = dyn_cast<MemberExpr>(Init)) { + if (!ME->isArrow() && ME->getBase()->isRValue()) { + Init = ME->getBase(); + continue; + } + } + + break; + } + + return Init->getType(); +} + /// addAutomaticObjDtors - Add to current block automatic objects destructors /// for objects in range of local scope positions. Use S as trigger statement /// for destructors. @@ -649,8 +756,6 @@ void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B, if (B == E) return; - CFGBlock::iterator InsertPos; - // We need to append the destructors in reverse order, but any one of them // may be a no-return destructor which changes the CFG. As a result, buffer // this sequence up and replay them in reverse order when appending onto the @@ -666,9 +771,13 @@ void CFGBuilder::addAutomaticObjDtors(LocalScope::const_iterator B, // If this destructor is marked as a no-return destructor, we need to // create a new block for the destructor which does not have as a successor // anything built thus far: control won't flow out of this block. - QualType Ty = (*I)->getType().getNonReferenceType(); - if (const ArrayType *AT = Context->getAsArrayType(Ty)) - Ty = AT->getElementType(); + QualType Ty; + if ((*I)->getType()->isReferenceType()) { + Ty = getReferenceInitTemporaryType(*Context, (*I)->getInit()); + } else { + Ty = Context->getBaseElementType((*I)->getType()); + } + const CXXDestructorDecl *Dtor = Ty->getAsCXXRecordDecl()->getDestructor(); if (cast<FunctionType>(Dtor->getType())->getNoReturnAttr()) Block = createNoReturnBlock(); @@ -798,16 +907,15 @@ LocalScope* CFGBuilder::addLocalScopeForVarDecl(VarDecl *VD, // 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 (QT.getTypePtr()->isReferenceType()) { if (!VD->extendsLifetimeOfTemporary()) return Scope; + + QT = getReferenceInitTemporaryType(*Context, VD->getInit()); } // Check for constant size array. Set type to array element type. - if (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) { + while (const ConstantArrayType *AT = Context->getAsConstantArrayType(QT)) { if (AT->getSize() == 0) return Scope; QT = AT->getElementType(); @@ -878,7 +986,7 @@ CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) { return VisitBinaryOperator(cast<BinaryOperator>(S), asc); case Stmt::BlockExprClass: - return VisitBlockExpr(cast<BlockExpr>(S), asc); + return VisitNoRecurse(cast<Expr>(S), asc); case Stmt::BreakStmtClass: return VisitBreakStmt(cast<BreakStmt>(S)); @@ -886,6 +994,7 @@ CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) { case Stmt::CallExprClass: case Stmt::CXXOperatorCallExprClass: case Stmt::CXXMemberCallExprClass: + case Stmt::UserDefinedLiteralClass: return VisitCallExpr(cast<CallExpr>(S), asc); case Stmt::CaseStmtClass: @@ -957,12 +1066,21 @@ CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) { case Stmt::LabelStmtClass: return VisitLabelStmt(cast<LabelStmt>(S)); + case Stmt::LambdaExprClass: + return VisitLambdaExpr(cast<LambdaExpr>(S), asc); + case Stmt::MemberExprClass: return VisitMemberExpr(cast<MemberExpr>(S), asc); + case Stmt::NullStmtClass: + return Block; + case Stmt::ObjCAtCatchStmtClass: return VisitObjCAtCatchStmt(cast<ObjCAtCatchStmt>(S)); + case Stmt::ObjCAutoreleasePoolStmtClass: + return VisitObjCAutoreleasePoolStmt(cast<ObjCAutoreleasePoolStmt>(S)); + case Stmt::ObjCAtSynchronizedStmtClass: return VisitObjCAtSynchronizedStmt(cast<ObjCAtSynchronizedStmt>(S)); @@ -975,9 +1093,12 @@ CFGBlock *CFGBuilder::Visit(Stmt * S, AddStmtChoice asc) { case Stmt::ObjCForCollectionStmtClass: return VisitObjCForCollectionStmt(cast<ObjCForCollectionStmt>(S)); - case Stmt::NullStmtClass: + case Stmt::OpaqueValueExprClass: return Block; + case Stmt::PseudoObjectExprClass: + return VisitPseudoObjectExpr(cast<PseudoObjectExpr>(S)); + case Stmt::ReturnStmtClass: return VisitReturnStmt(cast<ReturnStmt>(S)); @@ -1068,6 +1189,10 @@ CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, RHSBlock = createBlock(); } + // Generate the blocks for evaluating the LHS. + Block = LHSBlock; + CFGBlock *EntryLHSBlock = addStmt(B->getLHS()); + // See if this is a known constant. TryResult KnownVal = tryEvaluateBool(B->getLHS()); if (KnownVal.isKnown() && (B->getOpcode() == BO_LOr)) @@ -1083,9 +1208,7 @@ CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, addSuccessor(LHSBlock, KnownVal.isTrue() ? NULL : ConfluenceBlock); } - // Generate the blocks for evaluating the LHS. - Block = LHSBlock; - return addStmt(B->getLHS()); + return EntryLHSBlock; } if (B->getOpcode() == BO_Comma) { // , @@ -1117,7 +1240,7 @@ CFGBlock *CFGBuilder::VisitBinaryOperator(BinaryOperator *B, return (LBlock ? LBlock : RBlock); } -CFGBlock *CFGBuilder::VisitBlockExpr(BlockExpr *E, AddStmtChoice asc) { +CFGBlock *CFGBuilder::VisitNoRecurse(Expr *E, AddStmtChoice asc) { if (asc.alwaysAdd(*this, E)) { autoCreateBlock(); appendStmt(Block, E); @@ -1180,7 +1303,7 @@ CFGBlock *CFGBuilder::VisitCallExpr(CallExpr *C, AddStmtChoice asc) { bool AddEHEdge = false; // Languages without exceptions are assumed to not throw. - if (Context->getLangOptions().Exceptions) { + if (Context->getLangOpts().Exceptions) { if (BuildOpts.AddEHEdges) AddEHEdge = true; } @@ -1405,14 +1528,24 @@ CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) { autoCreateBlock(); appendStmt(Block, DS); + + // Keep track of the last non-null block, as 'Block' can be nulled out + // if the initializer expression is something like a 'while' in a + // statement-expression. + CFGBlock *LastBlock = Block; if (Init) { - if (HasTemporaries) + 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); + ExprWithCleanups *EC = cast<ExprWithCleanups>(Init); + if (CFGBlock *newBlock = Visit(EC->getSubExpr())) + LastBlock = newBlock; + } + else { + if (CFGBlock *newBlock = Visit(Init)) + LastBlock = newBlock; + } } // If the type of VD is a VLA, then we must process its size expressions. @@ -1424,7 +1557,7 @@ CFGBlock *CFGBuilder::VisitDeclSubExpr(DeclStmt *DS) { if (ScopePos && VD == *ScopePos) ++ScopePos; - return Block; + return Block ? Block : LastBlock; } CFGBlock *CFGBuilder::VisitIfStmt(IfStmt *I) { @@ -1588,6 +1721,19 @@ CFGBlock *CFGBuilder::VisitLabelStmt(LabelStmt *L) { return LabelBlock; } +CFGBlock *CFGBuilder::VisitLambdaExpr(LambdaExpr *E, AddStmtChoice asc) { + CFGBlock *LastBlock = VisitNoRecurse(E, asc); + for (LambdaExpr::capture_init_iterator it = E->capture_init_begin(), + et = E->capture_init_end(); it != et; ++it) { + if (Expr *Init = *it) { + CFGBlock *Tmp = Visit(Init); + if (Tmp != 0) + LastBlock = Tmp; + } + } + return LastBlock; +} + CFGBlock *CFGBuilder::VisitGotoStmt(GotoStmt *G) { // Goto is a control-flow statement. Thus we stop processing the current // block and create a new one. @@ -1875,6 +2021,12 @@ CFGBlock *CFGBuilder::VisitObjCForCollectionStmt(ObjCForCollectionStmt *S) { return addStmt(S->getCollection()); } +CFGBlock *CFGBuilder::VisitObjCAutoreleasePoolStmt(ObjCAutoreleasePoolStmt *S) { + // Inline the body. + return addStmt(S->getSubStmt()); + // TODO: consider adding cleanups for the end of @autoreleasepool scope. +} + CFGBlock *CFGBuilder::VisitObjCAtSynchronizedStmt(ObjCAtSynchronizedStmt *S) { // FIXME: Add locking 'primitives' to CFG for @synchronized. @@ -1904,6 +2056,31 @@ CFGBlock *CFGBuilder::VisitObjCAtTryStmt(ObjCAtTryStmt *S) { return NYS(); } +CFGBlock *CFGBuilder::VisitPseudoObjectExpr(PseudoObjectExpr *E) { + autoCreateBlock(); + + // Add the PseudoObject as the last thing. + appendStmt(Block, E); + + CFGBlock *lastBlock = Block; + + // Before that, evaluate all of the semantics in order. In + // CFG-land, that means appending them in reverse order. + for (unsigned i = E->getNumSemanticExprs(); i != 0; ) { + Expr *Semantic = E->getSemanticExpr(--i); + + // If the semantic is an opaque value, we're being asked to bind + // it to its source expression. + if (OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(Semantic)) + Semantic = OVE->getSourceExpr(); + + if (CFGBlock *B = Visit(Semantic)) + lastBlock = B; + } + + return lastBlock; +} + CFGBlock *CFGBuilder::VisitWhileStmt(WhileStmt *W) { CFGBlock *LoopSuccessor = NULL; @@ -2530,9 +2707,18 @@ CFGBlock *CFGBuilder::VisitCXXCatchStmt(CXXCatchStmt *CS) { CFGBlock *CatchBlock = Block; if (!CatchBlock) CatchBlock = createBlock(); - + + // CXXCatchStmt is more than just a label. They have semantic meaning + // as well, as they implicitly "initialize" the catch variable. Add + // it to the CFG as a CFGElement so that the control-flow of these + // semantics gets captured. + appendStmt(CatchBlock, CS); + + // Also add the CXXCatchStmt as a label, to mirror handling of regular + // labels. CatchBlock->setLabel(CS); + // Bail out if the CFG is bad. if (badCFG) return 0; @@ -2687,8 +2873,7 @@ CFGBlock *CFGBuilder::VisitCXXBindTemporaryExpr(CXXBindTemporaryExpr *E, CFGBlock *CFGBuilder::VisitCXXConstructExpr(CXXConstructExpr *C, AddStmtChoice asc) { autoCreateBlock(); - if (!C->isElidable()) - appendStmt(Block, C); + appendStmt(Block, C); return VisitChildren(C); } @@ -2958,7 +3143,7 @@ CFGBlock *CFG::createBlock() { // Create the block. CFGBlock *Mem = getAllocator().Allocate<CFGBlock>(); - new (Mem) CFGBlock(NumBlockIDs++, BlkBVC); + new (Mem) CFGBlock(NumBlockIDs++, BlkBVC, this); Blocks.push_back(Mem, BlkBVC); // If this is the first block, set it as the Entry and Exit. @@ -2989,7 +3174,7 @@ CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const { const VarDecl *var = cast<CFGAutomaticObjDtor>(this)->getVarDecl(); QualType ty = var->getType(); ty = ty.getNonReferenceType(); - if (const ArrayType *arrayType = astContext.getAsArrayType(ty)) { + while (const ArrayType *arrayType = astContext.getAsArrayType(ty)) { ty = arrayType->getElementType(); } const RecordType *recordType = ty->getAs<RecordType>(); @@ -3010,7 +3195,6 @@ CFGImplicitDtor::getDestructorDecl(ASTContext &astContext) const { return 0; } llvm_unreachable("getKind() returned bogus value"); - return 0; } bool CFGImplicitDtor::isNoReturn(ASTContext &astContext) const { @@ -3402,9 +3586,19 @@ static void print_elem(raw_ostream &OS, StmtPrinterHelper* Helper, if (isa<CXXOperatorCallExpr>(S)) { OS << " (OperatorCall)"; - } else if (isa<CXXBindTemporaryExpr>(S)) { + } + else if (isa<CXXBindTemporaryExpr>(S)) { OS << " (BindTemporary)"; } + else if (const CXXConstructExpr *CCE = dyn_cast<CXXConstructExpr>(S)) { + OS << " (CXXConstructExpr, " << CCE->getType().getAsString() << ")"; + } + else if (const CastExpr *CE = dyn_cast<CastExpr>(S)) { + OS << " (" << CE->getStmtClassName() << ", " + << CE->getCastKindName() + << ", " << CE->getType().getAsString() + << ")"; + } // Expressions need a newline. if (isa<Expr>(S)) @@ -3463,27 +3657,35 @@ static void print_elem(raw_ostream &OS, StmtPrinterHelper* Helper, static void print_block(raw_ostream &OS, const CFG* cfg, const CFGBlock &B, - StmtPrinterHelper* Helper, bool print_edges) { + StmtPrinterHelper* Helper, bool print_edges, + bool ShowColors) { - if (Helper) Helper->setBlockID(B.getBlockID()); + if (Helper) + Helper->setBlockID(B.getBlockID()); // Print the header. - OS << "\n [ B" << B.getBlockID(); + if (ShowColors) + OS.changeColor(raw_ostream::YELLOW, true); + + OS << "\n [B" << B.getBlockID(); if (&B == &cfg->getEntry()) - OS << " (ENTRY) ]\n"; + OS << " (ENTRY)]\n"; else if (&B == &cfg->getExit()) - OS << " (EXIT) ]\n"; + OS << " (EXIT)]\n"; else if (&B == cfg->getIndirectGotoBlock()) - OS << " (INDIRECT GOTO DISPATCH) ]\n"; + OS << " (INDIRECT GOTO DISPATCH)]\n"; else - OS << " ]\n"; + OS << "]\n"; + + if (ShowColors) + OS.resetColor(); // Print the label of this block. if (Stmt *Label = const_cast<Stmt*>(B.getLabel())) { if (print_edges) - OS << " "; + OS << " "; if (LabelStmt *L = dyn_cast<LabelStmt>(Label)) OS << L->getName(); @@ -3521,22 +3723,22 @@ static void print_block(raw_ostream &OS, const CFG* cfg, // Print the statement # in the basic block and the statement itself. if (print_edges) - OS << " "; + OS << " "; OS << llvm::format("%3d", j) << ": "; if (Helper) Helper->setStmtID(j); - print_elem(OS,Helper,*I); + print_elem(OS, Helper, *I); } // Print the terminator of this block. if (B.getTerminator()) { - if (print_edges) - OS << " "; + if (ShowColors) + OS.changeColor(raw_ostream::GREEN); - OS << " T: "; + OS << " T: "; if (Helper) Helper->setBlockID(-1); @@ -3544,54 +3746,86 @@ static void print_block(raw_ostream &OS, const CFG* cfg, PrintingPolicy(Helper->getLangOpts())); TPrinter.Visit(const_cast<Stmt*>(B.getTerminator().getStmt())); OS << '\n'; + + if (ShowColors) + OS.resetColor(); } if (print_edges) { // Print the predecessors of this block. - OS << " Predecessors (" << B.pred_size() << "):"; - unsigned i = 0; + if (!B.pred_empty()) { + const raw_ostream::Colors Color = raw_ostream::BLUE; + if (ShowColors) + OS.changeColor(Color); + OS << " Preds " ; + if (ShowColors) + OS.resetColor(); + OS << '(' << B.pred_size() << "):"; + unsigned i = 0; + + if (ShowColors) + OS.changeColor(Color); + + for (CFGBlock::const_pred_iterator I = B.pred_begin(), E = B.pred_end(); + I != E; ++I, ++i) { - 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 "; - if (i == 8 || (i-8) == 0) - OS << "\n "; + OS << " B" << (*I)->getBlockID(); + } + + if (ShowColors) + OS.resetColor(); - OS << " B" << (*I)->getBlockID(); + OS << '\n'; } - 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"; + if (!B.succ_empty()) { + const raw_ostream::Colors Color = raw_ostream::MAGENTA; + if (ShowColors) + OS.changeColor(Color); + OS << " Succs "; + if (ShowColors) + OS.resetColor(); + OS << '(' << B.succ_size() << "):"; + unsigned i = 0; + + if (ShowColors) + OS.changeColor(Color); + + 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"; + } + + if (ShowColors) + OS.resetColor(); + OS << '\n'; } - - 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); } +void CFG::dump(const LangOptions &LO, bool ShowColors) const { + print(llvm::errs(), LO, ShowColors); +} /// print - A simple pretty printer of a CFG that outputs to an ostream. -void CFG::print(raw_ostream &OS, const LangOptions &LO) const { +void CFG::print(raw_ostream &OS, const LangOptions &LO, bool ShowColors) const { StmtPrinterHelper Helper(this, LO); // Print the entry block. - print_block(OS, this, getEntry(), &Helper, true); + print_block(OS, this, getEntry(), &Helper, true, ShowColors); // Iterate through the CFGBlocks and print them one by one. for (const_iterator I = Blocks.begin(), E = Blocks.end() ; I != E ; ++I) { @@ -3599,25 +3833,28 @@ void CFG::print(raw_ostream &OS, const LangOptions &LO) const { if (&(**I) == &getEntry() || &(**I) == &getExit()) continue; - print_block(OS, this, **I, &Helper, true); + print_block(OS, this, **I, &Helper, true, ShowColors); } // Print the exit block. - print_block(OS, this, getExit(), &Helper, true); + print_block(OS, this, getExit(), &Helper, true, ShowColors); + OS << '\n'; 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); +void CFGBlock::dump(const CFG* cfg, const LangOptions &LO, + bool ShowColors) const { + print(llvm::errs(), cfg, LO, ShowColors); } /// 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(raw_ostream &OS, const CFG* cfg, - const LangOptions &LO) const { + const LangOptions &LO, bool ShowColors) const { StmtPrinterHelper Helper(cfg, LO); - print_block(OS, cfg, *this, &Helper, true); + print_block(OS, cfg, *this, &Helper, true, ShowColors); + OS << '\n'; } /// printTerminator - A simple pretty printer of the terminator of a CFGBlock. @@ -3714,7 +3951,7 @@ struct DOTGraphTraits<const CFG*> : public DefaultDOTGraphTraits { #ifndef NDEBUG std::string OutSStr; llvm::raw_string_ostream Out(OutSStr); - print_block(Out,Graph, *Node, GraphHelper, false); + print_block(Out,Graph, *Node, GraphHelper, false, false); std::string& OutStr = Out.str(); if (OutStr[0] == '\n') OutStr.erase(OutStr.begin()); diff --git a/contrib/llvm/tools/clang/lib/Analysis/CallGraph.cpp b/contrib/llvm/tools/clang/lib/Analysis/CallGraph.cpp new file mode 100644 index 0000000..96a16c3 --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/CallGraph.cpp @@ -0,0 +1,184 @@ +//== CallGraph.cpp - AST-based Call graph ----------------------*- 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 AST-based CallGraph. +// +//===----------------------------------------------------------------------===// +#include "clang/Analysis/CallGraph.h" + +#include "clang/AST/ASTContext.h" +#include "clang/AST/Decl.h" +#include "clang/AST/StmtVisitor.h" + +#include "llvm/Support/GraphWriter.h" + +using namespace clang; + +namespace { +/// A helper class, which walks the AST and locates all the call sites in the +/// given function body. +class CGBuilder : public StmtVisitor<CGBuilder> { + CallGraph *G; + const Decl *FD; + CallGraphNode *CallerNode; + +public: + CGBuilder(CallGraph *g, const Decl *D, CallGraphNode *N) + : G(g), FD(D), CallerNode(N) {} + + void VisitStmt(Stmt *S) { VisitChildren(S); } + + void VisitCallExpr(CallExpr *CE) { + // TODO: We need to handle ObjC method calls as well. + if (FunctionDecl *CalleeDecl = CE->getDirectCallee()) + if (G->includeInGraph(CalleeDecl)) { + CallGraphNode *CalleeNode = G->getOrInsertNode(CalleeDecl); + CallerNode->addCallee(CalleeNode, G); + } + } + + void VisitChildren(Stmt *S) { + for (Stmt::child_range I = S->children(); I; ++I) + if (*I) + static_cast<CGBuilder*>(this)->Visit(*I); + } +}; + +} // end anonymous namespace + +CallGraph::CallGraph() { + Root = getOrInsertNode(0); +} + +CallGraph::~CallGraph() { + if (!FunctionMap.empty()) { + for (FunctionMapTy::iterator I = FunctionMap.begin(), E = FunctionMap.end(); + I != E; ++I) + delete I->second; + FunctionMap.clear(); + } +} + +bool CallGraph::includeInGraph(const Decl *D) { + if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { + // We skip function template definitions, as their semantics is + // only determined when they are instantiated. + if (!FD->isThisDeclarationADefinition() || + FD->isDependentContext()) + return false; + + IdentifierInfo *II = FD->getIdentifier(); + if (II && II->getName().startswith("__inline")) + return false; + } + + if (const ObjCMethodDecl *ID = dyn_cast<ObjCMethodDecl>(D)) { + if (!ID->isThisDeclarationADefinition()) + return false; + } + + return true; +} + +void CallGraph::addNodeForDecl(Decl* D, bool IsGlobal) { + assert(D); + + // Do nothing if the node already exists. + if (FunctionMap.find(D) != FunctionMap.end()) + return; + + // Allocate a new node, mark it as root, and process it's calls. + CallGraphNode *Node = getOrInsertNode(D); + if (IsGlobal) + Root->addCallee(Node, this); + + // Process all the calls by this function as well. + CGBuilder builder(this, D, Node); + if (Stmt *Body = D->getBody()) + builder.Visit(Body); +} + +CallGraphNode *CallGraph::getNode(const Decl *F) const { + FunctionMapTy::const_iterator I = FunctionMap.find(F); + if (I == FunctionMap.end()) return 0; + return I->second; +} + +CallGraphNode *CallGraph::getOrInsertNode(Decl *F) { + CallGraphNode *&Node = FunctionMap[F]; + if (Node) + return Node; + + Node = new CallGraphNode(F); + // If not root, add to the parentless list. + if (F != 0) + ParentlessNodes.insert(Node); + return Node; +} + +void CallGraph::print(raw_ostream &OS) const { + OS << " --- Call graph Dump --- \n"; + for (const_iterator I = begin(), E = end(); I != E; ++I) { + OS << " Function: "; + if (I->second == Root) + OS << "< root >"; + else + I->second->print(OS); + OS << " calls: "; + for (CallGraphNode::iterator CI = I->second->begin(), + CE = I->second->end(); CI != CE; ++CI) { + assert(*CI != Root && "No one can call the root node."); + (*CI)->print(OS); + OS << " "; + } + OS << '\n'; + } + OS.flush(); +} + +void CallGraph::dump() const { + print(llvm::errs()); +} + +void CallGraph::viewGraph() const { + llvm::ViewGraph(this, "CallGraph"); +} + +StringRef CallGraphNode::getName() const { + if (const FunctionDecl *D = dyn_cast_or_null<FunctionDecl>(FD)) + if (const IdentifierInfo *II = D->getIdentifier()) + return II->getName(); + return "< >"; +} + +void CallGraphNode::print(raw_ostream &os) const { + os << getName(); +} + +void CallGraphNode::dump() const { + print(llvm::errs()); +} + +namespace llvm { + +template <> +struct DOTGraphTraits<const CallGraph*> : public DefaultDOTGraphTraits { + + DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} + + static std::string getNodeLabel(const CallGraphNode *Node, + const CallGraph *CG) { + if (CG->getRoot() == Node) { + return "< root >"; + } + return Node->getName(); + } + +}; +} diff --git a/contrib/llvm/tools/clang/lib/Analysis/CocoaConventions.cpp b/contrib/llvm/tools/clang/lib/Analysis/CocoaConventions.cpp index 8acd189..7e9e38f 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/CocoaConventions.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/CocoaConventions.cpp @@ -20,47 +20,6 @@ using namespace clang; using namespace ento; -// 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." -// - -cocoa::NamingConvention cocoa::deriveNamingConvention(Selector S, - const ObjCMethodDecl *MD) { - switch (MD && MD->hasAttr<ObjCMethodFamilyAttr>()? MD->getMethodFamily() - : S.getMethodFamily()) { - case OMF_None: - case OMF_autorelease: - case OMF_dealloc: - case OMF_finalize: - case OMF_release: - case OMF_retain: - case OMF_retainCount: - case OMF_self: - case OMF_performSelector: - return NoConvention; - - case OMF_init: - return InitRule; - - case OMF_alloc: - case OMF_copy: - case OMF_mutableCopy: - case OMF_new: - return CreateRule; - } - llvm_unreachable("unexpected naming convention"); - return NoConvention; -} - bool cocoa::isRefType(QualType RetTy, StringRef Prefix, StringRef Name) { // Recursively walk the typedef stack, allowing typedefs of reference types. @@ -68,7 +27,9 @@ bool cocoa::isRefType(QualType RetTy, StringRef Prefix, StringRef TDName = TD->getDecl()->getIdentifier()->getName(); if (TDName.startswith(Prefix) && TDName.endswith("Ref")) return true; - + // XPC unfortunately uses CF-style function names, but aren't CF types. + if (TDName.startswith("xpc_")) + return false; RetTy = TD->getDecl()->getUnderlyingType(); } @@ -115,7 +76,7 @@ bool cocoa::isCocoaObjectRef(QualType Ty) { // Assume that anything declared with a forward declaration and no // @interface subclasses NSObject. - if (ID->isForwardDecl()) + if (!ID->hasDefinition()) return true; for ( ; ID ; ID = ID->getSuperClass()) @@ -174,6 +135,4 @@ bool coreFoundation::followsCreateRule(const FunctionDecl *fn) { // If we matched a lowercase character, it isn't the end of the // word. Keep scanning. } - - return false; } diff --git a/contrib/llvm/tools/clang/lib/Analysis/Dominators.cpp b/contrib/llvm/tools/clang/lib/Analysis/Dominators.cpp new file mode 100644 index 0000000..0e02c6d --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/Dominators.cpp @@ -0,0 +1,14 @@ +//=- Dominators.cpp - Implementation of dominators tree for Clang CFG C++ -*-=// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Analyses/Dominators.h" + +using namespace clang; + +void DominatorTree::anchor() { } diff --git a/contrib/llvm/tools/clang/lib/Analysis/FormatString.cpp b/contrib/llvm/tools/clang/lib/Analysis/FormatString.cpp index a26f0ad..51fac49 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/FormatString.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/FormatString.cpp @@ -13,6 +13,7 @@ //===----------------------------------------------------------------------===// #include "FormatStringParsing.h" +#include "clang/Basic/LangOptions.h" using clang::analyze_format_string::ArgTypeResult; using clang::analyze_format_string::FormatStringHandler; @@ -155,6 +156,9 @@ clang::analyze_format_string::ParseArgPosition(FormatStringHandler &H, } if (Amt.getHowSpecified() == OptionalAmount::Constant && *(I++) == '$') { + // Warn that positional arguments are non-standard. + H.HandlePosition(Start, I - Start); + // Special case: '%0$', since this is an easy mistake. if (Amt.getConstantAmount() == 0) { H.HandleZeroPosition(Start, I - Start); @@ -175,7 +179,9 @@ clang::analyze_format_string::ParseArgPosition(FormatStringHandler &H, bool clang::analyze_format_string::ParseLengthModifier(FormatSpecifier &FS, const char *&I, - const char *E) { + const char *E, + const LangOptions &LO, + bool IsScanf) { LengthModifier::Kind lmKind = LengthModifier::None; const char *lmPosition = I; switch (*I) { @@ -183,19 +189,39 @@ clang::analyze_format_string::ParseLengthModifier(FormatSpecifier &FS, return false; case 'h': ++I; - lmKind = (I != E && *I == 'h') ? - ++I, LengthModifier::AsChar : LengthModifier::AsShort; + lmKind = (I != E && *I == 'h') ? (++I, LengthModifier::AsChar) + : LengthModifier::AsShort; break; case 'l': ++I; - lmKind = (I != E && *I == 'l') ? - ++I, LengthModifier::AsLongLong : LengthModifier::AsLong; + 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; + case 'q': lmKind = LengthModifier::AsQuad; ++I; break; + case 'a': + if (IsScanf && !LO.C99 && !LO.CPlusPlus0x) { + // For scanf in C90, look at the next character to see if this should + // be parsed as the GNU extension 'a' length modifier. If not, this + // will be parsed as a conversion specifier. + ++I; + if (I != E && (*I == 's' || *I == 'S' || *I == '[')) { + lmKind = LengthModifier::AsAllocate; + break; + } + --I; + } + return false; + case 'm': + if (IsScanf) { + lmKind = LengthModifier::AsMAllocate; + ++I; + break; + } + return false; } LengthModifier lm(lmPosition, lmKind); FS.setLengthModifier(lm); @@ -213,7 +239,21 @@ bool ArgTypeResult::matchesType(ASTContext &C, QualType argTy) const { case UnknownTy: return true; - + + case AnyCharTy: { + if (const BuiltinType *BT = argTy->getAs<BuiltinType>()) + switch (BT->getKind()) { + default: + break; + case BuiltinType::Char_S: + case BuiltinType::SChar: + case BuiltinType::UChar: + case BuiltinType::Char_U: + return true; + } + return false; + } + case SpecificTy: { argTy = C.getCanonicalType(argTy).getUnqualifiedType(); if (T == argTy) @@ -297,15 +337,28 @@ bool ArgTypeResult::matchesType(ASTContext &C, QualType argTy) const { case CPointerTy: return argTy->isPointerType() || argTy->isObjCObjectPointerType() || - argTy->isNullPtrType(); + argTy->isBlockPointerType() || argTy->isNullPtrType(); - case ObjCPointerTy: - return argTy->getAs<ObjCObjectPointerType>() != NULL; + case ObjCPointerTy: { + if (argTy->getAs<ObjCObjectPointerType>() || + argTy->getAs<BlockPointerType>()) + return true; + + // Handle implicit toll-free bridging. + if (const PointerType *PT = argTy->getAs<PointerType>()) { + // Things such as CFTypeRef are really just opaque pointers + // to C structs representing CF types that can often be bridged + // to Objective-C objects. Since the compiler doesn't know which + // structs can be toll-free bridged, we just accept them all. + QualType pointee = PT->getPointeeType(); + if (pointee->getAsStructureType() || pointee->isVoidType()) + return true; + } + return false; + } } - // FIXME: Should be unreachable, but Clang is currently emitting - // a warning. - return false; + llvm_unreachable("Invalid ArgTypeResult Kind!"); } QualType ArgTypeResult::getRepresentativeType(ASTContext &C) const { @@ -314,6 +367,8 @@ QualType ArgTypeResult::getRepresentativeType(ASTContext &C) const { llvm_unreachable("No representative type for Invalid ArgTypeResult"); case UnknownTy: return QualType(); + case AnyCharTy: + return C.CharTy; case SpecificTy: return T; case CStrTy: @@ -330,11 +385,17 @@ QualType ArgTypeResult::getRepresentativeType(ASTContext &C) const { } } - // FIXME: Should be unreachable, but Clang is currently emitting - // a warning. - return QualType(); + llvm_unreachable("Invalid ArgTypeResult Kind!"); } +std::string ArgTypeResult::getRepresentativeTypeName(ASTContext &C) const { + std::string S = getRepresentativeType(C).getAsString(); + if (Name && S != Name) + return std::string("'") + Name + "' (aka '" + S + "')"; + return std::string("'") + S + "'"; +} + + //===----------------------------------------------------------------------===// // Methods on OptionalAmount. //===----------------------------------------------------------------------===// @@ -359,6 +420,8 @@ analyze_format_string::LengthModifier::toString() const { return "l"; case AsLongLong: return "ll"; + case AsQuad: + return "q"; case AsIntMax: return "j"; case AsSizeT: @@ -367,6 +430,10 @@ analyze_format_string::LengthModifier::toString() const { return "t"; case AsLongDouble: return "L"; + case AsAllocate: + return "a"; + case AsMAllocate: + return "m"; case None: return ""; } @@ -374,6 +441,52 @@ analyze_format_string::LengthModifier::toString() const { } //===----------------------------------------------------------------------===// +// 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 OptionalAmount. //===----------------------------------------------------------------------===// @@ -398,19 +511,16 @@ void OptionalAmount::toString(raw_ostream &os) const { } } -//===----------------------------------------------------------------------===// -// Methods on ConversionSpecifier. -//===----------------------------------------------------------------------===// - bool FormatSpecifier::hasValidLengthModifier() const { switch (LM.getKind()) { case LengthModifier::None: return true; - // Handle most integer flags + // Handle most integer flags case LengthModifier::AsChar: case LengthModifier::AsShort: case LengthModifier::AsLongLong: + case LengthModifier::AsQuad: case LengthModifier::AsIntMax: case LengthModifier::AsSizeT: case LengthModifier::AsPtrDiff: @@ -428,7 +538,7 @@ bool FormatSpecifier::hasValidLengthModifier() const { return false; } - // Handle 'l' flag + // Handle 'l' flag case LengthModifier::AsLong: switch (CS.getKind()) { case ConversionSpecifier::dArg: @@ -449,6 +559,7 @@ bool FormatSpecifier::hasValidLengthModifier() const { case ConversionSpecifier::cArg: case ConversionSpecifier::sArg: case ConversionSpecifier::rArg: + case ConversionSpecifier::ScanListArg: return true; default: return false; @@ -465,11 +576,113 @@ bool FormatSpecifier::hasValidLengthModifier() const { case ConversionSpecifier::gArg: case ConversionSpecifier::GArg: return true; + // GNU extension. + case ConversionSpecifier::dArg: + case ConversionSpecifier::iArg: + case ConversionSpecifier::oArg: + case ConversionSpecifier::uArg: + case ConversionSpecifier::xArg: + case ConversionSpecifier::XArg: + return true; + default: + return false; + } + + case LengthModifier::AsAllocate: + switch (CS.getKind()) { + case ConversionSpecifier::sArg: + case ConversionSpecifier::SArg: + case ConversionSpecifier::ScanListArg: + return true; + default: + return false; + } + + case LengthModifier::AsMAllocate: + switch (CS.getKind()) { + case ConversionSpecifier::cArg: + case ConversionSpecifier::CArg: + case ConversionSpecifier::sArg: + case ConversionSpecifier::SArg: + case ConversionSpecifier::ScanListArg: + return true; default: return false; } } - return false; + llvm_unreachable("Invalid LengthModifier Kind!"); } +bool FormatSpecifier::hasStandardLengthModifier() const { + switch (LM.getKind()) { + case LengthModifier::None: + case LengthModifier::AsChar: + case LengthModifier::AsShort: + case LengthModifier::AsLong: + case LengthModifier::AsLongLong: + case LengthModifier::AsIntMax: + case LengthModifier::AsSizeT: + case LengthModifier::AsPtrDiff: + case LengthModifier::AsLongDouble: + return true; + case LengthModifier::AsAllocate: + case LengthModifier::AsMAllocate: + case LengthModifier::AsQuad: + return false; + } + llvm_unreachable("Invalid LengthModifier Kind!"); +} +bool FormatSpecifier::hasStandardConversionSpecifier(const LangOptions &LangOpt) const { + switch (CS.getKind()) { + case ConversionSpecifier::cArg: + case ConversionSpecifier::dArg: + case ConversionSpecifier::iArg: + case ConversionSpecifier::oArg: + case ConversionSpecifier::uArg: + case ConversionSpecifier::xArg: + case ConversionSpecifier::XArg: + 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::sArg: + case ConversionSpecifier::pArg: + case ConversionSpecifier::nArg: + case ConversionSpecifier::ObjCObjArg: + case ConversionSpecifier::ScanListArg: + case ConversionSpecifier::PercentArg: + return true; + case ConversionSpecifier::CArg: + case ConversionSpecifier::SArg: + return LangOpt.ObjC1 || LangOpt.ObjC2; + case ConversionSpecifier::InvalidSpecifier: + case ConversionSpecifier::bArg: + case ConversionSpecifier::DArg: + case ConversionSpecifier::rArg: + case ConversionSpecifier::PrintErrno: + return false; + } + llvm_unreachable("Invalid ConversionSpecifier Kind!"); +} + +bool FormatSpecifier::hasStandardLengthConversionCombination() const { + if (LM.getKind() == LengthModifier::AsLongDouble) { + switch(CS.getKind()) { + case ConversionSpecifier::dArg: + case ConversionSpecifier::iArg: + case ConversionSpecifier::oArg: + case ConversionSpecifier::uArg: + case ConversionSpecifier::xArg: + case ConversionSpecifier::XArg: + return false; + default: + return true; + } + } + return true; +} diff --git a/contrib/llvm/tools/clang/lib/Analysis/FormatStringParsing.h b/contrib/llvm/tools/clang/lib/Analysis/FormatStringParsing.h index 607e99c..f483ec6 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/FormatStringParsing.h +++ b/contrib/llvm/tools/clang/lib/Analysis/FormatStringParsing.h @@ -8,6 +8,8 @@ namespace clang { +class LangOptions; + template <typename T> class UpdateOnReturn { T &ValueToUpdate; @@ -42,7 +44,8 @@ bool ParseArgPosition(FormatStringHandler &H, /// 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); +bool ParseLengthModifier(FormatSpecifier &FS, const char *&Beg, const char *E, + const LangOptions &LO, bool IsScanf = false); template <typename T> class SpecifierResult { T FS; @@ -69,4 +72,3 @@ public: } // end clang namespace #endif - diff --git a/contrib/llvm/tools/clang/lib/Analysis/LiveVariables.cpp b/contrib/llvm/tools/clang/lib/Analysis/LiveVariables.cpp index 62c5455..ff6607d 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/LiveVariables.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/LiveVariables.cpp @@ -1,4 +1,6 @@ #include "clang/Analysis/Analyses/LiveVariables.h" +#include "clang/Analysis/Analyses/PostOrderCFGView.h" + #include "clang/AST/Stmt.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/AnalysisContext.h" @@ -15,113 +17,14 @@ using namespace clang; namespace { -// FIXME: This is copy-pasted from ThreadSafety.c. I wanted a patch that -// contained working code before refactoring the implementation of both -// files. -class CFGBlockSet { - llvm::BitVector VisitedBlockIDs; - -public: - // po_iterator requires this iterator, but the only interface needed is the - // value_type typedef. - struct iterator { - typedef const CFGBlock *value_type; - }; - - CFGBlockSet() {} - CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {} - - /// \brief Set the bit associated with a particular CFGBlock. - /// This is the important method for the SetType template parameter. - bool insert(const CFGBlock *Block) { - // Note that insert() is called by po_iterator, which doesn't check to make - // sure that Block is non-null. Moreover, the CFGBlock iterator will - // occasionally hand out null pointers for pruned edges, so we catch those - // here. - if (Block == 0) - return false; // if an edge is trivially false. - if (VisitedBlockIDs.test(Block->getBlockID())) - return false; - VisitedBlockIDs.set(Block->getBlockID()); - return true; - } - - /// \brief Check if the bit for a CFGBlock has been already set. - /// This method is for tracking visited blocks in the main threadsafety loop. - /// Block must not be null. - bool alreadySet(const CFGBlock *Block) { - return VisitedBlockIDs.test(Block->getBlockID()); - } -}; - -/// \brief We create a helper class which we use to iterate through CFGBlocks in -/// the topological order. -class TopologicallySortedCFG { - typedef llvm::po_iterator<const CFG*, CFGBlockSet, true> po_iterator; - - std::vector<const CFGBlock*> Blocks; - - typedef llvm::DenseMap<const CFGBlock *, unsigned> BlockOrderTy; - BlockOrderTy BlockOrder; - - -public: - typedef std::vector<const CFGBlock*>::reverse_iterator iterator; - - TopologicallySortedCFG(const CFG *CFGraph) { - Blocks.reserve(CFGraph->getNumBlockIDs()); - CFGBlockSet BSet(CFGraph); - - for (po_iterator I = po_iterator::begin(CFGraph, BSet), - E = po_iterator::end(CFGraph, BSet); I != E; ++I) { - BlockOrder[*I] = Blocks.size() + 1; - Blocks.push_back(*I); - } - } - - iterator begin() { - return Blocks.rbegin(); - } - - iterator end() { - return Blocks.rend(); - } - - bool empty() { - return begin() == end(); - } - - struct BlockOrderCompare; - friend struct BlockOrderCompare; - - struct BlockOrderCompare { - const TopologicallySortedCFG &TSC; - public: - BlockOrderCompare(const TopologicallySortedCFG &tsc) : TSC(tsc) {} - - bool operator()(const CFGBlock *b1, const CFGBlock *b2) const { - TopologicallySortedCFG::BlockOrderTy::const_iterator b1It = TSC.BlockOrder.find(b1); - TopologicallySortedCFG::BlockOrderTy::const_iterator b2It = TSC.BlockOrder.find(b2); - - unsigned b1V = (b1It == TSC.BlockOrder.end()) ? 0 : b1It->second; - unsigned b2V = (b2It == TSC.BlockOrder.end()) ? 0 : b2It->second; - return b1V > b2V; - } - }; - - BlockOrderCompare getComparator() const { - return BlockOrderCompare(*this); - } -}; - class DataflowWorklist { SmallVector<const CFGBlock *, 20> worklist; llvm::BitVector enqueuedBlocks; - TopologicallySortedCFG TSC; + PostOrderCFGView *POV; public: - DataflowWorklist(const CFG &cfg) + DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx) : enqueuedBlocks(cfg.getNumBlockIDs()), - TSC(&cfg) {} + POV(Ctx.getAnalysis<PostOrderCFGView>()) {} void enqueueBlock(const CFGBlock *block); void enqueueSuccessors(const CFGBlock *block); @@ -168,10 +71,9 @@ void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) { } void DataflowWorklist::sortWorklist() { - std::sort(worklist.begin(), worklist.end(), TSC.getComparator()); + std::sort(worklist.begin(), worklist.end(), POV->getComparator()); } - const CFGBlock *DataflowWorklist::dequeue() { if (worklist.empty()) return 0; @@ -184,7 +86,7 @@ const CFGBlock *DataflowWorklist::dequeue() { namespace { class LiveVariablesImpl { public: - AnalysisContext &analysisContext; + AnalysisDeclContext &analysisContext; std::vector<LiveVariables::LivenessValues> cfgBlockValues; llvm::ImmutableSet<const Stmt *>::Factory SSetFact; llvm::ImmutableSet<const VarDecl *>::Factory DSetFact; @@ -204,7 +106,7 @@ public: void dumpBlockLiveness(const SourceManager& M); - LiveVariablesImpl(AnalysisContext &ac, bool KillAtAssign) + LiveVariablesImpl(AnalysisDeclContext &ac, bool KillAtAssign) : analysisContext(ac), SSetFact(false), // Do not canonicalize ImmutableSets by default. DSetFact(false), // This is a *major* performance win. @@ -241,6 +143,8 @@ namespace { } } +void LiveVariables::Observer::anchor() { } + LiveVariables::LivenessValues LiveVariablesImpl::merge(LiveVariables::LivenessValues valsA, LiveVariables::LivenessValues valsB) { @@ -329,6 +233,29 @@ static const VariableArrayType *FindVA(QualType Ty) { return 0; } +static const Stmt *LookThroughStmt(const Stmt *S) { + while (S) { + if (const Expr *Ex = dyn_cast<Expr>(S)) + S = Ex->IgnoreParens(); + if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(S)) { + S = EWC->getSubExpr(); + continue; + } + if (const OpaqueValueExpr *OVE = dyn_cast<OpaqueValueExpr>(S)) { + S = OVE->getSourceExpr(); + continue; + } + break; + } + return S; +} + +static void AddLiveStmt(llvm::ImmutableSet<const Stmt *> &Set, + llvm::ImmutableSet<const Stmt *>::Factory &F, + const Stmt *S) { + Set = F.add(Set, LookThroughStmt(S)); +} + void TransferFunctions::Visit(Stmt *S) { if (observer) observer->observeStmt(S, currentBlock, val); @@ -353,8 +280,7 @@ void TransferFunctions::Visit(Stmt *S) { // Include the implicit "this" pointer as being live. CXXMemberCallExpr *CE = cast<CXXMemberCallExpr>(S); if (Expr *ImplicitObj = CE->getImplicitObjectArgument()) { - ImplicitObj = ImplicitObj->IgnoreParens(); - val.liveStmts = LV.SSetFact.add(val.liveStmts, ImplicitObj); + AddLiveStmt(val.liveStmts, LV.SSetFact, ImplicitObj); } break; } @@ -363,12 +289,23 @@ void TransferFunctions::Visit(Stmt *S) { if (const VarDecl *VD = dyn_cast<VarDecl>(DS->getSingleDecl())) { for (const VariableArrayType* VA = FindVA(VD->getType()); VA != 0; VA = FindVA(VA->getElementType())) { - val.liveStmts = LV.SSetFact.add(val.liveStmts, - VA->getSizeExpr()->IgnoreParens()); + AddLiveStmt(val.liveStmts, LV.SSetFact, VA->getSizeExpr()); } } break; } + case Stmt::PseudoObjectExprClass: { + // A pseudo-object operation only directly consumes its result + // expression. + Expr *child = cast<PseudoObjectExpr>(S)->getResultExpr(); + if (!child) return; + if (OpaqueValueExpr *OV = dyn_cast<OpaqueValueExpr>(child)) + child = OV->getSourceExpr(); + child = child->IgnoreParens(); + val.liveStmts = LV.SSetFact.add(val.liveStmts, child); + return; + } + // FIXME: These cases eventually shouldn't be needed. case Stmt::ExprWithCleanupsClass: { S = cast<ExprWithCleanups>(S)->getSubExpr(); @@ -386,12 +323,8 @@ void TransferFunctions::Visit(Stmt *S) { for (Stmt::child_iterator it = S->child_begin(), ei = S->child_end(); it != ei; ++it) { - if (Stmt *child = *it) { - if (Expr *Ex = dyn_cast<Expr>(child)) - child = Ex->IgnoreParens(); - - val.liveStmts = LV.SSetFact.add(val.liveStmts, child); - } + if (Stmt *child = *it) + AddLiveStmt(val.liveStmts, LV.SSetFact, child); } } @@ -421,7 +354,7 @@ void TransferFunctions::VisitBinaryOperator(BinaryOperator *B) { } void TransferFunctions::VisitBlockExpr(BlockExpr *BE) { - AnalysisContext::referenced_decls_iterator I, E; + AnalysisDeclContext::referenced_decls_iterator I, E; llvm::tie(I, E) = LV.analysisContext.getReferencedBlockVars(BE->getBlockDecl()); for ( ; I != E ; ++I) { @@ -545,7 +478,7 @@ LiveVariables::~LiveVariables() { } LiveVariables * -LiveVariables::computeLiveness(AnalysisContext &AC, +LiveVariables::computeLiveness(AnalysisDeclContext &AC, bool killAtAssign) { // No CFG? Bail out. @@ -557,7 +490,7 @@ LiveVariables::computeLiveness(AnalysisContext &AC, // Construct the dataflow worklist. Enqueue the exit block as the // start of the analysis. - DataflowWorklist worklist(*cfg); + DataflowWorklist worklist(*cfg, AC); llvm::BitVector everAnalyzedBlock(cfg->getNumBlockIDs()); // FIXME: we should enqueue using post order. diff --git a/contrib/llvm/tools/clang/lib/Analysis/PostOrderCFGView.cpp b/contrib/llvm/tools/clang/lib/Analysis/PostOrderCFGView.cpp new file mode 100644 index 0000000..cfd66f7 --- /dev/null +++ b/contrib/llvm/tools/clang/lib/Analysis/PostOrderCFGView.cpp @@ -0,0 +1,49 @@ +//===- PostOrderCFGView.cpp - Post order view of CFG blocks -------*- 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 post order view of the blocks in a CFG. +// +//===----------------------------------------------------------------------===// + +#include "clang/Analysis/Analyses/PostOrderCFGView.h" + +using namespace clang; + +void PostOrderCFGView::anchor() { } + +PostOrderCFGView::PostOrderCFGView(const CFG *cfg) { + Blocks.reserve(cfg->getNumBlockIDs()); + CFGBlockSet BSet(cfg); + + for (po_iterator I = po_iterator::begin(cfg, BSet), + E = po_iterator::end(cfg, BSet); I != E; ++I) { + BlockOrder[*I] = Blocks.size() + 1; + Blocks.push_back(*I); + } +} + +PostOrderCFGView *PostOrderCFGView::create(AnalysisDeclContext &ctx) { + const CFG *cfg = ctx.getCFG(); + if (!cfg) + return 0; + return new PostOrderCFGView(cfg); +} + +const void *PostOrderCFGView::getTag() { static int x; return &x; } + +bool PostOrderCFGView::BlockOrderCompare::operator()(const CFGBlock *b1, + const CFGBlock *b2) const { + PostOrderCFGView::BlockOrderTy::const_iterator b1It = POV.BlockOrder.find(b1); + PostOrderCFGView::BlockOrderTy::const_iterator b2It = POV.BlockOrder.find(b2); + + unsigned b1V = (b1It == POV.BlockOrder.end()) ? 0 : b1It->second; + unsigned b2V = (b2It == POV.BlockOrder.end()) ? 0 : b2It->second; + return b1V > b2V; +} + diff --git a/contrib/llvm/tools/clang/lib/Analysis/PrintfFormatString.cpp b/contrib/llvm/tools/clang/lib/Analysis/PrintfFormatString.cpp index 2bb39cf..4b2a19e 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/PrintfFormatString.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/PrintfFormatString.cpp @@ -52,7 +52,7 @@ static PrintfSpecifierResult ParsePrintfSpecifier(FormatStringHandler &H, const char *&Beg, const char *E, unsigned &argIndex, - bool FormatExtensions) { + const LangOptions &LO) { using namespace clang::analyze_format_string; using namespace clang::analyze_printf; @@ -151,7 +151,7 @@ static PrintfSpecifierResult ParsePrintfSpecifier(FormatStringHandler &H, } // Look for the length modifier. - if (ParseLengthModifier(FS, I, E) && I == E) { + if (ParseLengthModifier(FS, I, E, LO) && I == E) { // No more characters left? H.HandleIncompleteSpecifier(Start, E - Start); return true; @@ -197,10 +197,10 @@ static PrintfSpecifierResult ParsePrintfSpecifier(FormatStringHandler &H, // 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 */ + case 'b': if (LO.FormatExtensions) k = ConversionSpecifier::bArg; break; /* check for int and then char * */ + case 'r': if (LO.FormatExtensions) k = ConversionSpecifier::rArg; break; + case 'y': if (LO.FormatExtensions) k = ConversionSpecifier::iArg; break; + case 'D': if (LO.FormatExtensions) k = ConversionSpecifier::DArg; break; /* check for u_char * pointer and a char * string */ } PrintfConversionSpecifier CS(conversionPosition, k); FS.setConversionSpecifier(CS); @@ -220,14 +220,14 @@ static PrintfSpecifierResult ParsePrintfSpecifier(FormatStringHandler &H, bool clang::analyze_format_string::ParsePrintfString(FormatStringHandler &H, const char *I, const char *E, - bool FormatExtensions) { + const LangOptions &LO) { 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); + LO); // Did a fail-stop error of any kind occur when parsing the specifier? // If so, don't do any more processing. if (FSR.shouldStop()) @@ -246,55 +246,11 @@ bool clang::analyze_format_string::ParsePrintfString(FormatStringHandler &H, } //===----------------------------------------------------------------------===// -// 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 { +ArgTypeResult PrintfSpecifier::getArgType(ASTContext &Ctx, + bool IsObjCLiteral) const { const PrintfConversionSpecifier &CS = getConversionSpecifier(); if (!CS.consumesDataArgument()) @@ -303,7 +259,8 @@ ArgTypeResult PrintfSpecifier::getArgType(ASTContext &Ctx) const { if (CS.getKind() == ConversionSpecifier::cArg) switch (LM.getKind()) { case LengthModifier::None: return Ctx.IntTy; - case LengthModifier::AsLong: return ArgTypeResult::WIntTy; + case LengthModifier::AsLong: + return ArgTypeResult(ArgTypeResult::WIntTy, "wint_t"); default: return ArgTypeResult::Invalid(); } @@ -311,39 +268,50 @@ ArgTypeResult PrintfSpecifier::getArgType(ASTContext &Ctx) const { if (CS.isIntArg()) switch (LM.getKind()) { case LengthModifier::AsLongDouble: - return ArgTypeResult::Invalid(); + // GNU extension. + return Ctx.LongLongTy; case LengthModifier::None: return Ctx.IntTy; - case LengthModifier::AsChar: return Ctx.SignedCharTy; + case LengthModifier::AsChar: return ArgTypeResult::AnyCharTy; case LengthModifier::AsShort: return Ctx.ShortTy; case LengthModifier::AsLong: return Ctx.LongTy; - case LengthModifier::AsLongLong: return Ctx.LongLongTy; + case LengthModifier::AsLongLong: + case LengthModifier::AsQuad: + return Ctx.LongLongTy; case LengthModifier::AsIntMax: - // FIXME: Return unknown for now. + return ArgTypeResult(Ctx.getIntMaxType(), "intmax_t"); + case LengthModifier::AsSizeT: + // FIXME: How to get the corresponding signed version of size_t? return ArgTypeResult(); - case LengthModifier::AsSizeT: return Ctx.getSizeType(); - case LengthModifier::AsPtrDiff: return Ctx.getPointerDiffType(); + case LengthModifier::AsPtrDiff: + return ArgTypeResult(Ctx.getPointerDiffType(), "ptrdiff_t"); + case LengthModifier::AsAllocate: + case LengthModifier::AsMAllocate: + return ArgTypeResult::Invalid(); } if (CS.isUIntArg()) switch (LM.getKind()) { case LengthModifier::AsLongDouble: - return ArgTypeResult::Invalid(); + // GNU extension. + return Ctx.UnsignedLongLongTy; 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::AsLongLong: + case LengthModifier::AsQuad: + return Ctx.UnsignedLongLongTy; case LengthModifier::AsIntMax: - // FIXME: Return unknown for now. - return ArgTypeResult(); + return ArgTypeResult(Ctx.getUIntMaxType(), "uintmax_t"); case LengthModifier::AsSizeT: - // FIXME: How to get the corresponding unsigned - // version of size_t? - return ArgTypeResult(); + return ArgTypeResult(Ctx.getSizeType(), "size_t"); case LengthModifier::AsPtrDiff: // FIXME: How to get the corresponding unsigned // version of ptrdiff_t? return ArgTypeResult(); + case LengthModifier::AsAllocate: + case LengthModifier::AsMAllocate: + return ArgTypeResult::Invalid(); } if (CS.isDoubleArg()) { @@ -354,15 +322,24 @@ ArgTypeResult PrintfSpecifier::getArgType(ASTContext &Ctx) const { switch (CS.getKind()) { case ConversionSpecifier::sArg: - return ArgTypeResult(LM.getKind() == LengthModifier::AsWideChar ? - ArgTypeResult::WCStrTy : ArgTypeResult::CStrTy); + if (LM.getKind() == LengthModifier::AsWideChar) { + if (IsObjCLiteral) + return Ctx.getPointerType(Ctx.UnsignedShortTy.withConst()); + return ArgTypeResult(ArgTypeResult::WCStrTy, "wchar_t *"); + } + return ArgTypeResult::CStrTy; case ConversionSpecifier::SArg: - // FIXME: This appears to be Mac OS X specific. - return ArgTypeResult::WCStrTy; + if (IsObjCLiteral) + return Ctx.getPointerType(Ctx.UnsignedShortTy.withConst()); + return ArgTypeResult(ArgTypeResult::WCStrTy, "wchar_t *"); case ConversionSpecifier::CArg: - return Ctx.WCharTy; + if (IsObjCLiteral) + return Ctx.UnsignedShortTy; + return ArgTypeResult(Ctx.WCharTy, "wchar_t"); case ConversionSpecifier::pArg: return ArgTypeResult::CPointerTy; + case ConversionSpecifier::ObjCObjArg: + return ArgTypeResult::ObjCPointerTy; default: break; } @@ -371,7 +348,8 @@ ArgTypeResult PrintfSpecifier::getArgType(ASTContext &Ctx) const { return ArgTypeResult(); } -bool PrintfSpecifier::fixType(QualType QT) { +bool PrintfSpecifier::fixType(QualType QT, const LangOptions &LangOpt, + ASTContext &Ctx, bool IsObjCLiteral) { // Handle strings first (char *, wchar_t *) if (QT->isPointerType() && (QT->getPointeeType()->isAnyCharacterType())) { CS.setKind(ConversionSpecifier::sArg); @@ -383,16 +361,16 @@ bool PrintfSpecifier::fixType(QualType QT) { // Set the long length modifier for wide characters if (QT->getPointeeType()->isWideCharType()) LM.setKind(LengthModifier::AsWideChar); + else + LM.setKind(LengthModifier::None); 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>(); + if (!BT) + return false; // Set length modifier switch (BT->getKind()) { @@ -404,18 +382,15 @@ bool PrintfSpecifier::fixType(QualType QT) { case BuiltinType::UInt128: case BuiltinType::Int128: case BuiltinType::Half: - // Integral types which are non-trivial to correct. + // Various types which are non-trivial to correct. return false; - case BuiltinType::Void: - case BuiltinType::NullPtr: - case BuiltinType::ObjCId: - case BuiltinType::ObjCClass: - case BuiltinType::ObjCSel: - case BuiltinType::Dependent: - case BuiltinType::Overload: - case BuiltinType::BoundMember: - case BuiltinType::UnknownAny: +#define SIGNED_TYPE(Id, SingletonId) +#define UNSIGNED_TYPE(Id, SingletonId) +#define FLOATING_TYPE(Id, SingletonId) +#define BUILTIN_TYPE(Id, SingletonId) \ + case BuiltinType::Id: +#include "clang/AST/BuiltinTypes.def" // Misc other stuff which doesn't make sense here. return false; @@ -453,6 +428,28 @@ bool PrintfSpecifier::fixType(QualType QT) { break; } + // Handle size_t, ptrdiff_t, etc. that have dedicated length modifiers in C99. + if (isa<TypedefType>(QT) && (LangOpt.C99 || LangOpt.CPlusPlus0x)) { + const IdentifierInfo *Identifier = QT.getBaseTypeIdentifier(); + if (Identifier->getName() == "size_t") { + LM.setKind(LengthModifier::AsSizeT); + } else if (Identifier->getName() == "ssize_t") { + // Not C99, but common in Unix. + LM.setKind(LengthModifier::AsSizeT); + } else if (Identifier->getName() == "intmax_t") { + LM.setKind(LengthModifier::AsIntMax); + } else if (Identifier->getName() == "uintmax_t") { + LM.setKind(LengthModifier::AsIntMax); + } else if (Identifier->getName() == "ptrdiff_t") { + LM.setKind(LengthModifier::AsPtrDiff); + } + } + + // If fixing the length modifier was enough, we are done. + const analyze_printf::ArgTypeResult &ATR = getArgType(Ctx, IsObjCLiteral); + if (hasValidLengthModifier() && ATR.isValid() && ATR.matchesType(Ctx, QT)) + return true; + // 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()) { @@ -472,9 +469,7 @@ bool PrintfSpecifier::fixType(QualType QT) { HasAlternativeForm = 0; } else if (QT->isUnsignedIntegerType()) { - // Preserve the original formatting, e.g. 'X', 'o'. - if (!cast<PrintfConversionSpecifier>(CS).isUIntArg()) - CS.setKind(ConversionSpecifier::uArg); + CS.setKind(ConversionSpecifier::uArg); HasAlternativeForm = 0; HasPlusPrefix = 0; } else { diff --git a/contrib/llvm/tools/clang/lib/Analysis/ProgramPoint.cpp b/contrib/llvm/tools/clang/lib/Analysis/ProgramPoint.cpp index 3a0bbd5..3f711b4 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/ProgramPoint.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/ProgramPoint.cpp @@ -34,8 +34,6 @@ ProgramPoint ProgramPoint::getProgramPoint(const Stmt *S, ProgramPoint::Kind K, return PostLoad(S, LC, tag); case ProgramPoint::PreStoreKind: return PreStore(S, LC, tag); - case ProgramPoint::PostStoreKind: - return PostStore(S, LC, tag); case ProgramPoint::PostLValueKind: return PostLValue(S, LC, tag); case ProgramPoint::PostPurgeDeadSymbolsKind: diff --git a/contrib/llvm/tools/clang/lib/Analysis/PseudoConstantAnalysis.cpp b/contrib/llvm/tools/clang/lib/Analysis/PseudoConstantAnalysis.cpp index 8f24c43..c8b491a 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/PseudoConstantAnalysis.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/PseudoConstantAnalysis.cpp @@ -68,8 +68,6 @@ bool PseudoConstantAnalysis::wasReferenced(const VarDecl *VD) { 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; } @@ -198,18 +196,7 @@ void PseudoConstantAnalysis::RunAnalysis() { 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 4: Variable references case Stmt::DeclRefExprClass: { const DeclRefExpr *DR = cast<DeclRefExpr>(Head); if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { @@ -220,7 +207,7 @@ void PseudoConstantAnalysis::RunAnalysis() { break; } - // Case 6: Block expressions + // Case 5: Block expressions case Stmt::BlockExprClass: { const BlockExpr *B = cast<BlockExpr>(Head); // Add the body of the block to the list diff --git a/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp b/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp index 4931771..bb63e2c 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/ReachableCode.cpp @@ -251,7 +251,9 @@ void DeadCodeScan::reportDeadCode(const Stmt *S, } namespace clang { namespace reachable_code { - + +void Callback::anchor() { } + unsigned ScanReachableFromBlock(const CFGBlock *Start, llvm::BitVector &Reachable) { unsigned count = 0; @@ -287,7 +289,7 @@ unsigned ScanReachableFromBlock(const CFGBlock *Start, return count; } -void FindUnreachableCode(AnalysisContext &AC, Callback &CB) { +void FindUnreachableCode(AnalysisDeclContext &AC, Callback &CB) { CFG *cfg = AC.getCFG(); if (!cfg) return; diff --git a/contrib/llvm/tools/clang/lib/Analysis/ScanfFormatString.cpp b/contrib/llvm/tools/clang/lib/Analysis/ScanfFormatString.cpp index 6a8673a..6bc4adb 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/ScanfFormatString.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/ScanfFormatString.cpp @@ -20,9 +20,11 @@ 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::ScanfArgTypeResult; using clang::analyze_scanf::ScanfConversionSpecifier; using clang::analyze_scanf::ScanfSpecifier; using clang::UpdateOnReturn; +using namespace clang; typedef clang::analyze_format_string::SpecifierResult<ScanfSpecifier> ScanfSpecifierResult; @@ -65,7 +67,8 @@ static bool ParseScanList(FormatStringHandler &H, static ScanfSpecifierResult ParseScanfSpecifier(FormatStringHandler &H, const char *&Beg, const char *E, - unsigned &argIndex) { + unsigned &argIndex, + const LangOptions &LO) { using namespace clang::analyze_scanf; const char *I = Beg; @@ -130,7 +133,7 @@ static ScanfSpecifierResult ParseScanfSpecifier(FormatStringHandler &H, } // Look for the length modifier. - if (ParseLengthModifier(FS, I, E) && I == E) { + if (ParseLengthModifier(FS, I, E, LO, /*scanf=*/true) && I == E) { // No more characters left? H.HandleIncompleteSpecifier(Start, E - Start); return true; @@ -173,7 +176,7 @@ static ScanfSpecifierResult ParseScanfSpecifier(FormatStringHandler &H, } ScanfConversionSpecifier CS(conversionPosition, k); if (k == ScanfConversionSpecifier::ScanListArg) { - if (!ParseScanList(H, CS, I, E)) + if (ParseScanList(H, CS, I, E)) return true; } FS.setConversionSpecifier(CS); @@ -190,16 +193,248 @@ static ScanfSpecifierResult ParseScanfSpecifier(FormatStringHandler &H, } return ScanfSpecifierResult(Start, FS); } - + +ScanfArgTypeResult ScanfSpecifier::getArgType(ASTContext &Ctx) const { + const ScanfConversionSpecifier &CS = getConversionSpecifier(); + + if (!CS.consumesDataArgument()) + return ScanfArgTypeResult::Invalid(); + + switch(CS.getKind()) { + // Signed int. + case ConversionSpecifier::dArg: + case ConversionSpecifier::iArg: + switch (LM.getKind()) { + case LengthModifier::None: return ArgTypeResult(Ctx.IntTy); + case LengthModifier::AsChar: + return ArgTypeResult(ArgTypeResult::AnyCharTy); + case LengthModifier::AsShort: return ArgTypeResult(Ctx.ShortTy); + case LengthModifier::AsLong: return ArgTypeResult(Ctx.LongTy); + case LengthModifier::AsLongLong: + case LengthModifier::AsQuad: + return ArgTypeResult(Ctx.LongLongTy); + case LengthModifier::AsIntMax: + return ScanfArgTypeResult(Ctx.getIntMaxType(), "intmax_t *"); + case LengthModifier::AsSizeT: + // FIXME: ssize_t. + return ScanfArgTypeResult(); + case LengthModifier::AsPtrDiff: + return ScanfArgTypeResult(Ctx.getPointerDiffType(), "ptrdiff_t *"); + case LengthModifier::AsLongDouble: + // GNU extension. + return ArgTypeResult(Ctx.LongLongTy); + case LengthModifier::AsAllocate: return ScanfArgTypeResult::Invalid(); + case LengthModifier::AsMAllocate: return ScanfArgTypeResult::Invalid(); + } + + // Unsigned int. + case ConversionSpecifier::oArg: + case ConversionSpecifier::uArg: + case ConversionSpecifier::xArg: + case ConversionSpecifier::XArg: + switch (LM.getKind()) { + case LengthModifier::None: return ArgTypeResult(Ctx.UnsignedIntTy); + case LengthModifier::AsChar: return ArgTypeResult(Ctx.UnsignedCharTy); + case LengthModifier::AsShort: return ArgTypeResult(Ctx.UnsignedShortTy); + case LengthModifier::AsLong: return ArgTypeResult(Ctx.UnsignedLongTy); + case LengthModifier::AsLongLong: + case LengthModifier::AsQuad: + return ArgTypeResult(Ctx.UnsignedLongLongTy); + case LengthModifier::AsIntMax: + return ScanfArgTypeResult(Ctx.getUIntMaxType(), "uintmax_t *"); + case LengthModifier::AsSizeT: + return ScanfArgTypeResult(Ctx.getSizeType(), "size_t *"); + case LengthModifier::AsPtrDiff: + // FIXME: Unsigned version of ptrdiff_t? + return ScanfArgTypeResult(); + case LengthModifier::AsLongDouble: + // GNU extension. + return ArgTypeResult(Ctx.UnsignedLongLongTy); + case LengthModifier::AsAllocate: return ScanfArgTypeResult::Invalid(); + case LengthModifier::AsMAllocate: return ScanfArgTypeResult::Invalid(); + } + + // Float. + case ConversionSpecifier::aArg: + case ConversionSpecifier::AArg: + case ConversionSpecifier::eArg: + case ConversionSpecifier::EArg: + case ConversionSpecifier::fArg: + case ConversionSpecifier::FArg: + case ConversionSpecifier::gArg: + case ConversionSpecifier::GArg: + switch (LM.getKind()) { + case LengthModifier::None: return ArgTypeResult(Ctx.FloatTy); + case LengthModifier::AsLong: return ArgTypeResult(Ctx.DoubleTy); + case LengthModifier::AsLongDouble: + return ArgTypeResult(Ctx.LongDoubleTy); + default: + return ScanfArgTypeResult::Invalid(); + } + + // Char, string and scanlist. + case ConversionSpecifier::cArg: + case ConversionSpecifier::sArg: + case ConversionSpecifier::ScanListArg: + switch (LM.getKind()) { + case LengthModifier::None: return ScanfArgTypeResult::CStrTy; + case LengthModifier::AsLong: + return ScanfArgTypeResult(ScanfArgTypeResult::WCStrTy, "wchar_t *"); + case LengthModifier::AsAllocate: + case LengthModifier::AsMAllocate: + return ScanfArgTypeResult(ArgTypeResult::CStrTy); + default: + return ScanfArgTypeResult::Invalid(); + } + case ConversionSpecifier::CArg: + case ConversionSpecifier::SArg: + // FIXME: Mac OS X specific? + switch (LM.getKind()) { + case LengthModifier::None: + return ScanfArgTypeResult(ScanfArgTypeResult::WCStrTy, "wchar_t *"); + case LengthModifier::AsAllocate: + case LengthModifier::AsMAllocate: + return ScanfArgTypeResult(ArgTypeResult::WCStrTy, "wchar_t **"); + default: + return ScanfArgTypeResult::Invalid(); + } + + // Pointer. + case ConversionSpecifier::pArg: + return ScanfArgTypeResult(ArgTypeResult(ArgTypeResult::CPointerTy)); + + default: + break; + } + + return ScanfArgTypeResult(); +} + +bool ScanfSpecifier::fixType(QualType QT, const LangOptions &LangOpt, + ASTContext &Ctx) { + if (!QT->isPointerType()) + return false; + + QualType PT = QT->getPointeeType(); + const BuiltinType *BT = PT->getAs<BuiltinType>(); + if (!BT) + return false; + + // Pointer to a character. + if (PT->isAnyCharacterType()) { + CS.setKind(ConversionSpecifier::sArg); + if (PT->isWideCharType()) + LM.setKind(LengthModifier::AsWideChar); + else + LM.setKind(LengthModifier::None); + return true; + } + + // Figure out the length modifier. + switch (BT->getKind()) { + // no modifier + case BuiltinType::UInt: + case BuiltinType::Int: + case BuiltinType::Float: + LM.setKind(LengthModifier::None); + break; + + // hh + case BuiltinType::Char_U: + case BuiltinType::UChar: + case BuiltinType::Char_S: + case BuiltinType::SChar: + LM.setKind(LengthModifier::AsChar); + break; + + // h + case BuiltinType::Short: + case BuiltinType::UShort: + LM.setKind(LengthModifier::AsShort); + break; + + // l + case BuiltinType::Long: + case BuiltinType::ULong: + case BuiltinType::Double: + LM.setKind(LengthModifier::AsLong); + break; + + // ll + case BuiltinType::LongLong: + case BuiltinType::ULongLong: + LM.setKind(LengthModifier::AsLongLong); + break; + + // L + case BuiltinType::LongDouble: + LM.setKind(LengthModifier::AsLongDouble); + break; + + // Don't know. + default: + return false; + } + + // Handle size_t, ptrdiff_t, etc. that have dedicated length modifiers in C99. + if (isa<TypedefType>(PT) && (LangOpt.C99 || LangOpt.CPlusPlus0x)) { + const IdentifierInfo *Identifier = QT.getBaseTypeIdentifier(); + if (Identifier->getName() == "size_t") { + LM.setKind(LengthModifier::AsSizeT); + } else if (Identifier->getName() == "ssize_t") { + // Not C99, but common in Unix. + LM.setKind(LengthModifier::AsSizeT); + } else if (Identifier->getName() == "intmax_t") { + LM.setKind(LengthModifier::AsIntMax); + } else if (Identifier->getName() == "uintmax_t") { + LM.setKind(LengthModifier::AsIntMax); + } else if (Identifier->getName() == "ptrdiff_t") { + LM.setKind(LengthModifier::AsPtrDiff); + } + } + + // If fixing the length modifier was enough, we are done. + const analyze_scanf::ScanfArgTypeResult &ATR = getArgType(Ctx); + if (hasValidLengthModifier() && ATR.isValid() && ATR.matchesType(Ctx, QT)) + return true; + + // Figure out the conversion specifier. + if (PT->isRealFloatingType()) + CS.setKind(ConversionSpecifier::fArg); + else if (PT->isSignedIntegerType()) + CS.setKind(ConversionSpecifier::dArg); + else if (PT->isUnsignedIntegerType()) + CS.setKind(ConversionSpecifier::uArg); + else + llvm_unreachable("Unexpected type"); + + return true; +} + +void ScanfSpecifier::toString(raw_ostream &os) const { + os << "%"; + + if (usesPositionalArg()) + os << getPositionalArgIndex() << "$"; + if (SuppressAssignment) + os << "*"; + + FieldWidth.toString(os); + os << LM.toString(); + os << CS.toString(); +} + bool clang::analyze_format_string::ParseScanfString(FormatStringHandler &H, const char *I, - const char *E) { + const char *E, + const LangOptions &LO) { 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); + const ScanfSpecifierResult &FSR = ParseScanfSpecifier(H, I, E, argIndex, + LO); // Did a fail-stop error of any kind occur when parsing the specifier? // If so, don't do any more processing. if (FSR.shouldStop()) @@ -218,4 +453,47 @@ bool clang::analyze_format_string::ParseScanfString(FormatStringHandler &H, return false; } +bool ScanfArgTypeResult::matchesType(ASTContext& C, QualType argTy) const { + switch (K) { + case InvalidTy: + llvm_unreachable("ArgTypeResult must be valid"); + case UnknownTy: + return true; + case CStrTy: + return ArgTypeResult(ArgTypeResult::CStrTy).matchesType(C, argTy); + case WCStrTy: + return ArgTypeResult(ArgTypeResult::WCStrTy).matchesType(C, argTy); + case PtrToArgTypeResultTy: { + const PointerType *PT = argTy->getAs<PointerType>(); + if (!PT) + return false; + return A.matchesType(C, PT->getPointeeType()); + } + } + + llvm_unreachable("Invalid ScanfArgTypeResult Kind!"); +} + +QualType ScanfArgTypeResult::getRepresentativeType(ASTContext &C) const { + switch (K) { + case InvalidTy: + llvm_unreachable("No representative type for Invalid ArgTypeResult"); + case UnknownTy: + return QualType(); + case CStrTy: + return C.getPointerType(C.CharTy); + case WCStrTy: + return C.getPointerType(C.getWCharType()); + case PtrToArgTypeResultTy: + return C.getPointerType(A.getRepresentativeType(C)); + } + llvm_unreachable("Invalid ScanfArgTypeResult Kind!"); +} + +std::string ScanfArgTypeResult::getRepresentativeTypeName(ASTContext& C) const { + std::string S = getRepresentativeType(C).getAsString(); + if (!Name) + return std::string("'") + S + "'"; + return std::string("'") + Name + "' (aka '" + S + "')"; +} diff --git a/contrib/llvm/tools/clang/lib/Analysis/ThreadSafety.cpp b/contrib/llvm/tools/clang/lib/Analysis/ThreadSafety.cpp index 5a12913..2f7e794 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/ThreadSafety.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/ThreadSafety.cpp @@ -16,6 +16,7 @@ //===----------------------------------------------------------------------===// #include "clang/Analysis/Analyses/ThreadSafety.h" +#include "clang/Analysis/Analyses/PostOrderCFGView.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/CFGStmtMap.h" @@ -31,7 +32,9 @@ #include "llvm/ADT/PostOrderIterator.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" +#include "llvm/Support/raw_ostream.h" #include <algorithm> +#include <utility> #include <vector> using namespace clang; @@ -40,90 +43,7 @@ using namespace thread_safety; // Key method definition ThreadSafetyHandler::~ThreadSafetyHandler() {} -// Helper function -static Expr *getParent(Expr *Exp) { - if (MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) - return ME->getBase(); - if (CXXMemberCallExpr *CE = dyn_cast<CXXMemberCallExpr>(Exp)) - return CE->getImplicitObjectArgument(); - return 0; -} - namespace { -/// \brief Implements a set of CFGBlocks using a BitVector. -/// -/// This class contains a minimal interface, primarily dictated by the SetType -/// template parameter of the llvm::po_iterator template, as used with external -/// storage. We also use this set to keep track of which CFGBlocks we visit -/// during the analysis. -class CFGBlockSet { - llvm::BitVector VisitedBlockIDs; - -public: - // po_iterator requires this iterator, but the only interface needed is the - // value_type typedef. - struct iterator { - typedef const CFGBlock *value_type; - }; - - CFGBlockSet() {} - CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {} - - /// \brief Set the bit associated with a particular CFGBlock. - /// This is the important method for the SetType template parameter. - bool insert(const CFGBlock *Block) { - // Note that insert() is called by po_iterator, which doesn't check to make - // sure that Block is non-null. Moreover, the CFGBlock iterator will - // occasionally hand out null pointers for pruned edges, so we catch those - // here. - if (Block == 0) - return false; // if an edge is trivially false. - if (VisitedBlockIDs.test(Block->getBlockID())) - return false; - VisitedBlockIDs.set(Block->getBlockID()); - return true; - } - - /// \brief Check if the bit for a CFGBlock has been already set. - /// This method is for tracking visited blocks in the main threadsafety loop. - /// Block must not be null. - bool alreadySet(const CFGBlock *Block) { - return VisitedBlockIDs.test(Block->getBlockID()); - } -}; - -/// \brief We create a helper class which we use to iterate through CFGBlocks in -/// the topological order. -class TopologicallySortedCFG { - typedef llvm::po_iterator<const CFG*, CFGBlockSet, true> po_iterator; - - std::vector<const CFGBlock*> Blocks; - -public: - typedef std::vector<const CFGBlock*>::reverse_iterator iterator; - - TopologicallySortedCFG(const CFG *CFGraph) { - Blocks.reserve(CFGraph->getNumBlockIDs()); - CFGBlockSet BSet(CFGraph); - - for (po_iterator I = po_iterator::begin(CFGraph, BSet), - E = po_iterator::end(CFGraph, BSet); I != E; ++I) { - Blocks.push_back(*I); - } - } - - iterator begin() { - return Blocks.rbegin(); - } - - iterator end() { - return Blocks.rend(); - } - - bool empty() { - return begin() == end(); - } -}; /// \brief A MutexID object uniquely identifies a particular mutex, and /// is built from an Expr* (i.e. calling a lock function). @@ -136,16 +56,17 @@ public: /// (1) Local variables in the expression, such as "x" have not changed. /// (2) Values on the heap that affect the expression have not changed. /// (3) The expression involves only pure function calls. +/// /// The current implementation assumes, but does not verify, that multiple uses /// of the same lock expression satisfies these criteria. /// /// Clang introduces an additional wrinkle, which is that it is difficult to /// derive canonical expressions, or compare expressions directly for equality. -/// Thus, we identify a mutex not by an Expr, but by the set of named +/// Thus, we identify a mutex not by an Expr, but by the list of named /// declarations that are referenced by the Expr. In other words, /// x->foo->bar.mu will be a four element vector with the Decls for /// mu, bar, and foo, and x. The vector will uniquely identify the expression -/// for all practical purposes. +/// for all practical purposes. Null is used to denote 'this'. /// /// Note we will need to perform substitution on "this" and function parameter /// names when constructing a lock expression. @@ -164,38 +85,176 @@ class MutexID { SmallVector<NamedDecl*, 2> DeclSeq; /// Build a Decl sequence representing the lock from the given expression. - /// Recursive function that bottoms out when the final DeclRefExpr is reached. - // FIXME: Lock expressions that involve array indices or function calls. - // FIXME: Deal with LockReturned attribute. - void buildMutexID(Expr *Exp, Expr *Parent) { + /// Recursive function that terminates on DeclRefExpr. + /// Note: this function merely creates a MutexID; it does not check to + /// ensure that the original expression is a valid mutex expression. + void buildMutexID(Expr *Exp, const NamedDecl *D, Expr *Parent, + unsigned NumArgs, Expr **FunArgs) { + if (!Exp) { + DeclSeq.clear(); + return; + } + if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Exp)) { NamedDecl *ND = cast<NamedDecl>(DRE->getDecl()->getCanonicalDecl()); + ParmVarDecl *PV = dyn_cast_or_null<ParmVarDecl>(ND); + if (PV) { + FunctionDecl *FD = + cast<FunctionDecl>(PV->getDeclContext())->getCanonicalDecl(); + unsigned i = PV->getFunctionScopeIndex(); + + if (FunArgs && FD == D->getCanonicalDecl()) { + // Substitute call arguments for references to function parameters + assert(i < NumArgs); + buildMutexID(FunArgs[i], D, 0, 0, 0); + return; + } + // Map the param back to the param of the original function declaration. + DeclSeq.push_back(FD->getParamDecl(i)); + return; + } + // Not a function parameter -- just store the reference. DeclSeq.push_back(ND); } else if (MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) { NamedDecl *ND = ME->getMemberDecl(); DeclSeq.push_back(ND); - buildMutexID(ME->getBase(), Parent); + buildMutexID(ME->getBase(), D, Parent, NumArgs, FunArgs); } else if (isa<CXXThisExpr>(Exp)) { if (Parent) - buildMutexID(Parent, 0); - else - return; // mutexID is still valid in this case - } else if (CastExpr *CE = dyn_cast<CastExpr>(Exp)) - buildMutexID(CE->getSubExpr(), Parent); - else - DeclSeq.clear(); // invalid lock expression + buildMutexID(Parent, D, 0, 0, 0); + else { + DeclSeq.push_back(0); // Use 0 to represent 'this'. + return; // mutexID is still valid in this case + } + } else if (CXXMemberCallExpr *CMCE = dyn_cast<CXXMemberCallExpr>(Exp)) { + DeclSeq.push_back(CMCE->getMethodDecl()->getCanonicalDecl()); + buildMutexID(CMCE->getImplicitObjectArgument(), + D, Parent, NumArgs, FunArgs); + unsigned NumCallArgs = CMCE->getNumArgs(); + Expr** CallArgs = CMCE->getArgs(); + for (unsigned i = 0; i < NumCallArgs; ++i) { + buildMutexID(CallArgs[i], D, Parent, NumArgs, FunArgs); + } + } else if (CallExpr *CE = dyn_cast<CallExpr>(Exp)) { + buildMutexID(CE->getCallee(), D, Parent, NumArgs, FunArgs); + unsigned NumCallArgs = CE->getNumArgs(); + Expr** CallArgs = CE->getArgs(); + for (unsigned i = 0; i < NumCallArgs; ++i) { + buildMutexID(CallArgs[i], D, Parent, NumArgs, FunArgs); + } + } else if (BinaryOperator *BOE = dyn_cast<BinaryOperator>(Exp)) { + buildMutexID(BOE->getLHS(), D, Parent, NumArgs, FunArgs); + buildMutexID(BOE->getRHS(), D, Parent, NumArgs, FunArgs); + } else if (UnaryOperator *UOE = dyn_cast<UnaryOperator>(Exp)) { + buildMutexID(UOE->getSubExpr(), D, Parent, NumArgs, FunArgs); + } else if (ArraySubscriptExpr *ASE = dyn_cast<ArraySubscriptExpr>(Exp)) { + buildMutexID(ASE->getBase(), D, Parent, NumArgs, FunArgs); + buildMutexID(ASE->getIdx(), D, Parent, NumArgs, FunArgs); + } else if (AbstractConditionalOperator *CE = + dyn_cast<AbstractConditionalOperator>(Exp)) { + buildMutexID(CE->getCond(), D, Parent, NumArgs, FunArgs); + buildMutexID(CE->getTrueExpr(), D, Parent, NumArgs, FunArgs); + buildMutexID(CE->getFalseExpr(), D, Parent, NumArgs, FunArgs); + } else if (ChooseExpr *CE = dyn_cast<ChooseExpr>(Exp)) { + buildMutexID(CE->getCond(), D, Parent, NumArgs, FunArgs); + buildMutexID(CE->getLHS(), D, Parent, NumArgs, FunArgs); + buildMutexID(CE->getRHS(), D, Parent, NumArgs, FunArgs); + } else if (CastExpr *CE = dyn_cast<CastExpr>(Exp)) { + buildMutexID(CE->getSubExpr(), D, Parent, NumArgs, FunArgs); + } else if (ParenExpr *PE = dyn_cast<ParenExpr>(Exp)) { + buildMutexID(PE->getSubExpr(), D, Parent, NumArgs, FunArgs); + } else if (isa<CharacterLiteral>(Exp) || + isa<CXXNullPtrLiteralExpr>(Exp) || + isa<GNUNullExpr>(Exp) || + isa<CXXBoolLiteralExpr>(Exp) || + isa<FloatingLiteral>(Exp) || + isa<ImaginaryLiteral>(Exp) || + isa<IntegerLiteral>(Exp) || + isa<StringLiteral>(Exp) || + isa<ObjCStringLiteral>(Exp)) { + return; // FIXME: Ignore literals for now + } else { + // Ignore. FIXME: mark as invalid expression? + } + } + + /// \brief Construct a MutexID from an expression. + /// \param MutexExp The original mutex expression within an attribute + /// \param DeclExp An expression involving the Decl on which the attribute + /// occurs. + /// \param D The declaration to which the lock/unlock attribute is attached. + void buildMutexIDFromExp(Expr *MutexExp, Expr *DeclExp, const NamedDecl *D) { + Expr *Parent = 0; + unsigned NumArgs = 0; + Expr **FunArgs = 0; + + // If we are processing a raw attribute expression, with no substitutions. + if (DeclExp == 0) { + buildMutexID(MutexExp, D, 0, 0, 0); + return; + } + + // Examine DeclExp to find Parent and FunArgs, which are used to substitute + // for formal parameters when we call buildMutexID later. + if (MemberExpr *ME = dyn_cast<MemberExpr>(DeclExp)) { + Parent = ME->getBase(); + } else if (CXXMemberCallExpr *CE = dyn_cast<CXXMemberCallExpr>(DeclExp)) { + Parent = CE->getImplicitObjectArgument(); + NumArgs = CE->getNumArgs(); + FunArgs = CE->getArgs(); + } else if (CallExpr *CE = dyn_cast<CallExpr>(DeclExp)) { + NumArgs = CE->getNumArgs(); + FunArgs = CE->getArgs(); + } else if (CXXConstructExpr *CE = dyn_cast<CXXConstructExpr>(DeclExp)) { + Parent = 0; // FIXME -- get the parent from DeclStmt + NumArgs = CE->getNumArgs(); + FunArgs = CE->getArgs(); + } else if (D && isa<CXXDestructorDecl>(D)) { + // There's no such thing as a "destructor call" in the AST. + Parent = DeclExp; + } + + // If the attribute has no arguments, then assume the argument is "this". + if (MutexExp == 0) { + buildMutexID(Parent, D, 0, 0, 0); + return; + } + + buildMutexID(MutexExp, D, Parent, NumArgs, FunArgs); } public: - MutexID(Expr *LExpr, Expr *ParentExpr) { - buildMutexID(LExpr, ParentExpr); + explicit MutexID(clang::Decl::EmptyShell e) { + DeclSeq.clear(); } - /// If we encounter part of a lock expression we cannot parse + /// \param MutexExp The original mutex expression within an attribute + /// \param DeclExp An expression involving the Decl on which the attribute + /// occurs. + /// \param D The declaration to which the lock/unlock attribute is attached. + /// Caller must check isValid() after construction. + MutexID(Expr* MutexExp, Expr *DeclExp, const NamedDecl* D) { + buildMutexIDFromExp(MutexExp, DeclExp, D); + } + + /// Return true if this is a valid decl sequence. + /// Caller must call this by hand after construction to handle errors. bool isValid() const { return !DeclSeq.empty(); } + /// Issue a warning about an invalid lock expression + static void warnInvalidLock(ThreadSafetyHandler &Handler, Expr* MutexExp, + Expr *DeclExp, const NamedDecl* D) { + SourceLocation Loc; + if (DeclExp) + Loc = DeclExp->getExprLoc(); + + // FIXME: add a note about the attribute location in MutexExp or D + if (Loc.isValid()) + Handler.handleInvalidLockExp(Loc); + } + bool operator==(const MutexID &other) const { return DeclSeq == other.DeclSeq; } @@ -218,9 +277,11 @@ public: /// The caret will point unambiguously to the lock expression, so using this /// name in diagnostics is a way to get simple, and consistent, mutex names. /// We do not want to output the entire expression text for security reasons. - StringRef getName() const { + std::string getName() const { assert(isValid()); - return DeclSeq.front()->getName(); + if (!DeclSeq.front()) + return "this"; // Use 0 to represent 'this'. + return DeclSeq.front()->getNameAsString(); } void Profile(llvm::FoldingSetNodeID &ID) const { @@ -231,6 +292,7 @@ public: } }; + /// \brief This is a helper class that stores info about the most recent /// accquire of a Lock. /// @@ -245,9 +307,14 @@ struct LockData { /// /// FIXME: add support for re-entrant locking and lock up/downgrading LockKind LKind; + MutexID UnderlyingMutex; // for ScopedLockable objects LockData(SourceLocation AcquireLoc, LockKind LKind) - : AcquireLoc(AcquireLoc), LKind(LKind) {} + : AcquireLoc(AcquireLoc), LKind(LKind), UnderlyingMutex(Decl::EmptyShell()) + {} + + LockData(SourceLocation AcquireLoc, LockKind LKind, const MutexID &Mu) + : AcquireLoc(AcquireLoc), LKind(LKind), UnderlyingMutex(Mu) {} bool operator==(const LockData &other) const { return AcquireLoc == other.AcquireLoc && LKind == other.LKind; @@ -258,14 +325,567 @@ struct LockData { } void Profile(llvm::FoldingSetNodeID &ID) const { - ID.AddInteger(AcquireLoc.getRawEncoding()); - ID.AddInteger(LKind); - } + ID.AddInteger(AcquireLoc.getRawEncoding()); + ID.AddInteger(LKind); + } }; + /// A Lockset maps each MutexID (defined above) to information about how it has /// been locked. typedef llvm::ImmutableMap<MutexID, LockData> Lockset; +typedef llvm::ImmutableMap<NamedDecl*, unsigned> LocalVarContext; + +class LocalVariableMap; + +/// A side (entry or exit) of a CFG node. +enum CFGBlockSide { CBS_Entry, CBS_Exit }; + +/// CFGBlockInfo is a struct which contains all the information that is +/// maintained for each block in the CFG. See LocalVariableMap for more +/// information about the contexts. +struct CFGBlockInfo { + Lockset EntrySet; // Lockset held at entry to block + Lockset ExitSet; // Lockset held at exit from block + LocalVarContext EntryContext; // Context held at entry to block + LocalVarContext ExitContext; // Context held at exit from block + SourceLocation EntryLoc; // Location of first statement in block + SourceLocation ExitLoc; // Location of last statement in block. + unsigned EntryIndex; // Used to replay contexts later + + const Lockset &getSet(CFGBlockSide Side) const { + return Side == CBS_Entry ? EntrySet : ExitSet; + } + SourceLocation getLocation(CFGBlockSide Side) const { + return Side == CBS_Entry ? EntryLoc : ExitLoc; + } + +private: + CFGBlockInfo(Lockset EmptySet, LocalVarContext EmptyCtx) + : EntrySet(EmptySet), ExitSet(EmptySet), + EntryContext(EmptyCtx), ExitContext(EmptyCtx) + { } + +public: + static CFGBlockInfo getEmptyBlockInfo(Lockset::Factory &F, + LocalVariableMap &M); +}; + + + +// A LocalVariableMap maintains a map from local variables to their currently +// valid definitions. It provides SSA-like functionality when traversing the +// CFG. Like SSA, each definition or assignment to a variable is assigned a +// unique name (an integer), which acts as the SSA name for that definition. +// The total set of names is shared among all CFG basic blocks. +// Unlike SSA, we do not rewrite expressions to replace local variables declrefs +// with their SSA-names. Instead, we compute a Context for each point in the +// code, which maps local variables to the appropriate SSA-name. This map +// changes with each assignment. +// +// The map is computed in a single pass over the CFG. Subsequent analyses can +// then query the map to find the appropriate Context for a statement, and use +// that Context to look up the definitions of variables. +class LocalVariableMap { +public: + typedef LocalVarContext Context; + + /// A VarDefinition consists of an expression, representing the value of the + /// variable, along with the context in which that expression should be + /// interpreted. A reference VarDefinition does not itself contain this + /// information, but instead contains a pointer to a previous VarDefinition. + struct VarDefinition { + public: + friend class LocalVariableMap; + + NamedDecl *Dec; // The original declaration for this variable. + Expr *Exp; // The expression for this variable, OR + unsigned Ref; // Reference to another VarDefinition + Context Ctx; // The map with which Exp should be interpreted. + + bool isReference() { return !Exp; } + + private: + // Create ordinary variable definition + VarDefinition(NamedDecl *D, Expr *E, Context C) + : Dec(D), Exp(E), Ref(0), Ctx(C) + { } + + // Create reference to previous definition + VarDefinition(NamedDecl *D, unsigned R, Context C) + : Dec(D), Exp(0), Ref(R), Ctx(C) + { } + }; + +private: + Context::Factory ContextFactory; + std::vector<VarDefinition> VarDefinitions; + std::vector<unsigned> CtxIndices; + std::vector<std::pair<Stmt*, Context> > SavedContexts; + +public: + LocalVariableMap() { + // index 0 is a placeholder for undefined variables (aka phi-nodes). + VarDefinitions.push_back(VarDefinition(0, 0u, getEmptyContext())); + } + + /// Look up a definition, within the given context. + const VarDefinition* lookup(NamedDecl *D, Context Ctx) { + const unsigned *i = Ctx.lookup(D); + if (!i) + return 0; + assert(*i < VarDefinitions.size()); + return &VarDefinitions[*i]; + } + + /// Look up the definition for D within the given context. Returns + /// NULL if the expression is not statically known. If successful, also + /// modifies Ctx to hold the context of the return Expr. + Expr* lookupExpr(NamedDecl *D, Context &Ctx) { + const unsigned *P = Ctx.lookup(D); + if (!P) + return 0; + + unsigned i = *P; + while (i > 0) { + if (VarDefinitions[i].Exp) { + Ctx = VarDefinitions[i].Ctx; + return VarDefinitions[i].Exp; + } + i = VarDefinitions[i].Ref; + } + return 0; + } + + Context getEmptyContext() { return ContextFactory.getEmptyMap(); } + + /// Return the next context after processing S. This function is used by + /// clients of the class to get the appropriate context when traversing the + /// CFG. It must be called for every assignment or DeclStmt. + Context getNextContext(unsigned &CtxIndex, Stmt *S, Context C) { + if (SavedContexts[CtxIndex+1].first == S) { + CtxIndex++; + Context Result = SavedContexts[CtxIndex].second; + return Result; + } + return C; + } + + void dumpVarDefinitionName(unsigned i) { + if (i == 0) { + llvm::errs() << "Undefined"; + return; + } + NamedDecl *Dec = VarDefinitions[i].Dec; + if (!Dec) { + llvm::errs() << "<<NULL>>"; + return; + } + Dec->printName(llvm::errs()); + llvm::errs() << "." << i << " " << ((void*) Dec); + } + + /// Dumps an ASCII representation of the variable map to llvm::errs() + void dump() { + for (unsigned i = 1, e = VarDefinitions.size(); i < e; ++i) { + Expr *Exp = VarDefinitions[i].Exp; + unsigned Ref = VarDefinitions[i].Ref; + + dumpVarDefinitionName(i); + llvm::errs() << " = "; + if (Exp) Exp->dump(); + else { + dumpVarDefinitionName(Ref); + llvm::errs() << "\n"; + } + } + } + + /// Dumps an ASCII representation of a Context to llvm::errs() + void dumpContext(Context C) { + for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) { + NamedDecl *D = I.getKey(); + D->printName(llvm::errs()); + const unsigned *i = C.lookup(D); + llvm::errs() << " -> "; + dumpVarDefinitionName(*i); + llvm::errs() << "\n"; + } + } + + /// Builds the variable map. + void traverseCFG(CFG *CFGraph, PostOrderCFGView *SortedGraph, + std::vector<CFGBlockInfo> &BlockInfo); + +protected: + // Get the current context index + unsigned getContextIndex() { return SavedContexts.size()-1; } + + // Save the current context for later replay + void saveContext(Stmt *S, Context C) { + SavedContexts.push_back(std::make_pair(S,C)); + } + + // Adds a new definition to the given context, and returns a new context. + // This method should be called when declaring a new variable. + Context addDefinition(NamedDecl *D, Expr *Exp, Context Ctx) { + assert(!Ctx.contains(D)); + unsigned newID = VarDefinitions.size(); + Context NewCtx = ContextFactory.add(Ctx, D, newID); + VarDefinitions.push_back(VarDefinition(D, Exp, Ctx)); + return NewCtx; + } + + // Add a new reference to an existing definition. + Context addReference(NamedDecl *D, unsigned i, Context Ctx) { + unsigned newID = VarDefinitions.size(); + Context NewCtx = ContextFactory.add(Ctx, D, newID); + VarDefinitions.push_back(VarDefinition(D, i, Ctx)); + return NewCtx; + } + + // Updates a definition only if that definition is already in the map. + // This method should be called when assigning to an existing variable. + Context updateDefinition(NamedDecl *D, Expr *Exp, Context Ctx) { + if (Ctx.contains(D)) { + unsigned newID = VarDefinitions.size(); + Context NewCtx = ContextFactory.remove(Ctx, D); + NewCtx = ContextFactory.add(NewCtx, D, newID); + VarDefinitions.push_back(VarDefinition(D, Exp, Ctx)); + return NewCtx; + } + return Ctx; + } + + // Removes a definition from the context, but keeps the variable name + // as a valid variable. The index 0 is a placeholder for cleared definitions. + Context clearDefinition(NamedDecl *D, Context Ctx) { + Context NewCtx = Ctx; + if (NewCtx.contains(D)) { + NewCtx = ContextFactory.remove(NewCtx, D); + NewCtx = ContextFactory.add(NewCtx, D, 0); + } + return NewCtx; + } + + // Remove a definition entirely frmo the context. + Context removeDefinition(NamedDecl *D, Context Ctx) { + Context NewCtx = Ctx; + if (NewCtx.contains(D)) { + NewCtx = ContextFactory.remove(NewCtx, D); + } + return NewCtx; + } + + Context intersectContexts(Context C1, Context C2); + Context createReferenceContext(Context C); + void intersectBackEdge(Context C1, Context C2); + + friend class VarMapBuilder; +}; + + +// This has to be defined after LocalVariableMap. +CFGBlockInfo CFGBlockInfo::getEmptyBlockInfo(Lockset::Factory &F, + LocalVariableMap &M) { + return CFGBlockInfo(F.getEmptyMap(), M.getEmptyContext()); +} + + +/// Visitor which builds a LocalVariableMap +class VarMapBuilder : public StmtVisitor<VarMapBuilder> { +public: + LocalVariableMap* VMap; + LocalVariableMap::Context Ctx; + + VarMapBuilder(LocalVariableMap *VM, LocalVariableMap::Context C) + : VMap(VM), Ctx(C) {} + + void VisitDeclStmt(DeclStmt *S); + void VisitBinaryOperator(BinaryOperator *BO); +}; + + +// Add new local variables to the variable map +void VarMapBuilder::VisitDeclStmt(DeclStmt *S) { + bool modifiedCtx = false; + DeclGroupRef DGrp = S->getDeclGroup(); + for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) { + if (VarDecl *VD = dyn_cast_or_null<VarDecl>(*I)) { + Expr *E = VD->getInit(); + + // Add local variables with trivial type to the variable map + QualType T = VD->getType(); + if (T.isTrivialType(VD->getASTContext())) { + Ctx = VMap->addDefinition(VD, E, Ctx); + modifiedCtx = true; + } + } + } + if (modifiedCtx) + VMap->saveContext(S, Ctx); +} + +// Update local variable definitions in variable map +void VarMapBuilder::VisitBinaryOperator(BinaryOperator *BO) { + if (!BO->isAssignmentOp()) + return; + + Expr *LHSExp = BO->getLHS()->IgnoreParenCasts(); + + // Update the variable map and current context. + if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(LHSExp)) { + ValueDecl *VDec = DRE->getDecl(); + if (Ctx.lookup(VDec)) { + if (BO->getOpcode() == BO_Assign) + Ctx = VMap->updateDefinition(VDec, BO->getRHS(), Ctx); + else + // FIXME -- handle compound assignment operators + Ctx = VMap->clearDefinition(VDec, Ctx); + VMap->saveContext(BO, Ctx); + } + } +} + + +// Computes the intersection of two contexts. The intersection is the +// set of variables which have the same definition in both contexts; +// variables with different definitions are discarded. +LocalVariableMap::Context +LocalVariableMap::intersectContexts(Context C1, Context C2) { + Context Result = C1; + for (Context::iterator I = C1.begin(), E = C1.end(); I != E; ++I) { + NamedDecl *Dec = I.getKey(); + unsigned i1 = I.getData(); + const unsigned *i2 = C2.lookup(Dec); + if (!i2) // variable doesn't exist on second path + Result = removeDefinition(Dec, Result); + else if (*i2 != i1) // variable exists, but has different definition + Result = clearDefinition(Dec, Result); + } + return Result; +} + +// For every variable in C, create a new variable that refers to the +// definition in C. Return a new context that contains these new variables. +// (We use this for a naive implementation of SSA on loop back-edges.) +LocalVariableMap::Context LocalVariableMap::createReferenceContext(Context C) { + Context Result = getEmptyContext(); + for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) { + NamedDecl *Dec = I.getKey(); + unsigned i = I.getData(); + Result = addReference(Dec, i, Result); + } + return Result; +} + +// This routine also takes the intersection of C1 and C2, but it does so by +// altering the VarDefinitions. C1 must be the result of an earlier call to +// createReferenceContext. +void LocalVariableMap::intersectBackEdge(Context C1, Context C2) { + for (Context::iterator I = C1.begin(), E = C1.end(); I != E; ++I) { + NamedDecl *Dec = I.getKey(); + unsigned i1 = I.getData(); + VarDefinition *VDef = &VarDefinitions[i1]; + assert(VDef->isReference()); + + const unsigned *i2 = C2.lookup(Dec); + if (!i2 || (*i2 != i1)) + VDef->Ref = 0; // Mark this variable as undefined + } +} + + +// Traverse the CFG in topological order, so all predecessors of a block +// (excluding back-edges) are visited before the block itself. At +// each point in the code, we calculate a Context, which holds the set of +// variable definitions which are visible at that point in execution. +// Visible variables are mapped to their definitions using an array that +// contains all definitions. +// +// At join points in the CFG, the set is computed as the intersection of +// the incoming sets along each edge, E.g. +// +// { Context | VarDefinitions } +// int x = 0; { x -> x1 | x1 = 0 } +// int y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 } +// if (b) x = 1; { x -> x2, y -> y1 | x2 = 1, y1 = 0, ... } +// else x = 2; { x -> x3, y -> y1 | x3 = 2, x2 = 1, ... } +// ... { y -> y1 (x is unknown) | x3 = 2, x2 = 1, ... } +// +// This is essentially a simpler and more naive version of the standard SSA +// algorithm. Those definitions that remain in the intersection are from blocks +// that strictly dominate the current block. We do not bother to insert proper +// phi nodes, because they are not used in our analysis; instead, wherever +// a phi node would be required, we simply remove that definition from the +// context (E.g. x above). +// +// The initial traversal does not capture back-edges, so those need to be +// handled on a separate pass. Whenever the first pass encounters an +// incoming back edge, it duplicates the context, creating new definitions +// that refer back to the originals. (These correspond to places where SSA +// might have to insert a phi node.) On the second pass, these definitions are +// set to NULL if the the variable has changed on the back-edge (i.e. a phi +// node was actually required.) E.g. +// +// { Context | VarDefinitions } +// int x = 0, y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 } +// while (b) { x -> x2, y -> y1 | [1st:] x2=x1; [2nd:] x2=NULL; } +// x = x+1; { x -> x3, y -> y1 | x3 = x2 + 1, ... } +// ... { y -> y1 | x3 = 2, x2 = 1, ... } +// +void LocalVariableMap::traverseCFG(CFG *CFGraph, + PostOrderCFGView *SortedGraph, + std::vector<CFGBlockInfo> &BlockInfo) { + PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); + + CtxIndices.resize(CFGraph->getNumBlockIDs()); + + for (PostOrderCFGView::iterator I = SortedGraph->begin(), + E = SortedGraph->end(); I!= E; ++I) { + const CFGBlock *CurrBlock = *I; + int CurrBlockID = CurrBlock->getBlockID(); + CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; + + VisitedBlocks.insert(CurrBlock); + + // Calculate the entry context for the current block + bool HasBackEdges = false; + bool CtxInit = true; + for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), + PE = CurrBlock->pred_end(); PI != PE; ++PI) { + // if *PI -> CurrBlock is a back edge, so skip it + if (*PI == 0 || !VisitedBlocks.alreadySet(*PI)) { + HasBackEdges = true; + continue; + } + + int PrevBlockID = (*PI)->getBlockID(); + CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; + + if (CtxInit) { + CurrBlockInfo->EntryContext = PrevBlockInfo->ExitContext; + CtxInit = false; + } + else { + CurrBlockInfo->EntryContext = + intersectContexts(CurrBlockInfo->EntryContext, + PrevBlockInfo->ExitContext); + } + } + + // Duplicate the context if we have back-edges, so we can call + // intersectBackEdges later. + if (HasBackEdges) + CurrBlockInfo->EntryContext = + createReferenceContext(CurrBlockInfo->EntryContext); + + // Create a starting context index for the current block + saveContext(0, CurrBlockInfo->EntryContext); + CurrBlockInfo->EntryIndex = getContextIndex(); + + // Visit all the statements in the basic block. + VarMapBuilder VMapBuilder(this, CurrBlockInfo->EntryContext); + for (CFGBlock::const_iterator BI = CurrBlock->begin(), + BE = CurrBlock->end(); BI != BE; ++BI) { + switch (BI->getKind()) { + case CFGElement::Statement: { + const CFGStmt *CS = cast<CFGStmt>(&*BI); + VMapBuilder.Visit(const_cast<Stmt*>(CS->getStmt())); + break; + } + default: + break; + } + } + CurrBlockInfo->ExitContext = VMapBuilder.Ctx; + + // Mark variables on back edges as "unknown" if they've been changed. + for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), + SE = CurrBlock->succ_end(); SI != SE; ++SI) { + // if CurrBlock -> *SI is *not* a back edge + if (*SI == 0 || !VisitedBlocks.alreadySet(*SI)) + continue; + + CFGBlock *FirstLoopBlock = *SI; + Context LoopBegin = BlockInfo[FirstLoopBlock->getBlockID()].EntryContext; + Context LoopEnd = CurrBlockInfo->ExitContext; + intersectBackEdge(LoopBegin, LoopEnd); + } + } + + // Put an extra entry at the end of the indexed context array + unsigned exitID = CFGraph->getExit().getBlockID(); + saveContext(0, BlockInfo[exitID].ExitContext); +} + +/// Find the appropriate source locations to use when producing diagnostics for +/// each block in the CFG. +static void findBlockLocations(CFG *CFGraph, + PostOrderCFGView *SortedGraph, + std::vector<CFGBlockInfo> &BlockInfo) { + for (PostOrderCFGView::iterator I = SortedGraph->begin(), + E = SortedGraph->end(); I!= E; ++I) { + const CFGBlock *CurrBlock = *I; + CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlock->getBlockID()]; + + // Find the source location of the last statement in the block, if the + // block is not empty. + if (const Stmt *S = CurrBlock->getTerminator()) { + CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = S->getLocStart(); + } else { + for (CFGBlock::const_reverse_iterator BI = CurrBlock->rbegin(), + BE = CurrBlock->rend(); BI != BE; ++BI) { + // FIXME: Handle other CFGElement kinds. + if (const CFGStmt *CS = dyn_cast<CFGStmt>(&*BI)) { + CurrBlockInfo->ExitLoc = CS->getStmt()->getLocStart(); + break; + } + } + } + + if (!CurrBlockInfo->ExitLoc.isInvalid()) { + // This block contains at least one statement. Find the source location + // of the first statement in the block. + for (CFGBlock::const_iterator BI = CurrBlock->begin(), + BE = CurrBlock->end(); BI != BE; ++BI) { + // FIXME: Handle other CFGElement kinds. + if (const CFGStmt *CS = dyn_cast<CFGStmt>(&*BI)) { + CurrBlockInfo->EntryLoc = CS->getStmt()->getLocStart(); + break; + } + } + } else if (CurrBlock->pred_size() == 1 && *CurrBlock->pred_begin() && + CurrBlock != &CFGraph->getExit()) { + // The block is empty, and has a single predecessor. Use its exit + // location. + CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = + BlockInfo[(*CurrBlock->pred_begin())->getBlockID()].ExitLoc; + } + } +} + +/// \brief Class which implements the core thread safety analysis routines. +class ThreadSafetyAnalyzer { + friend class BuildLockset; + + ThreadSafetyHandler &Handler; + Lockset::Factory LocksetFactory; + LocalVariableMap LocalVarMap; + +public: + ThreadSafetyAnalyzer(ThreadSafetyHandler &H) : Handler(H) {} + + Lockset intersectAndWarn(const CFGBlockInfo &Block1, CFGBlockSide Side1, + const CFGBlockInfo &Block2, CFGBlockSide Side2, + LockErrorKind LEK); + + Lockset addLock(Lockset &LSet, Expr *MutexExp, const NamedDecl *D, + LockKind LK, SourceLocation Loc); + + void runAnalysis(AnalysisDeclContext &AC); +}; + /// \brief We use this class to visit different types of expressions in /// CFGBlocks, and build up the lockset. @@ -273,32 +893,51 @@ typedef llvm::ImmutableMap<MutexID, LockData> Lockset; /// output error messages related to missing locks. /// FIXME: In future, we may be able to not inherit from a visitor. class BuildLockset : public StmtVisitor<BuildLockset> { + friend class ThreadSafetyAnalyzer; + ThreadSafetyHandler &Handler; - Lockset LSet; Lockset::Factory &LocksetFactory; + LocalVariableMap &LocalVarMap; + + Lockset LSet; + LocalVariableMap::Context LVarCtx; + unsigned CtxIndex; // Helper functions - void removeLock(SourceLocation UnlockLoc, Expr *LockExp, Expr *Parent); - void addLock(SourceLocation LockLoc, Expr *LockExp, Expr *Parent, - LockKind LK); + void addLock(const MutexID &Mutex, const LockData &LDat); + void removeLock(const MutexID &Mutex, SourceLocation UnlockLoc); + + template <class AttrType> + void addLocksToSet(LockKind LK, AttrType *Attr, + Expr *Exp, NamedDecl *D, VarDecl *VD = 0); + void removeLocksFromSet(UnlockFunctionAttr *Attr, + Expr *Exp, NamedDecl* FunDecl); + const ValueDecl *getValueDecl(Expr *Exp); void warnIfMutexNotHeld (const NamedDecl *D, Expr *Exp, AccessKind AK, Expr *MutexExp, ProtectedOperationKind POK); void checkAccess(Expr *Exp, AccessKind AK); void checkDereference(Expr *Exp, AccessKind AK); + void handleCall(Expr *Exp, NamedDecl *D, VarDecl *VD = 0); template <class AttrType> - void addLocksToSet(LockKind LK, Attr *Attr, CXXMemberCallExpr *Exp); + void addTrylock(LockKind LK, AttrType *Attr, Expr *Exp, NamedDecl *FunDecl, + const CFGBlock* PredBlock, const CFGBlock *CurrBlock, + Expr *BrE, bool Neg); + CallExpr* getTrylockCallExpr(Stmt *Cond, LocalVariableMap::Context C, + bool &Negate); + void handleTrylock(Stmt *Cond, const CFGBlock* PredBlock, + const CFGBlock *CurrBlock); /// \brief Returns true if the lockset contains a lock, regardless of whether /// the lock is held exclusively or shared. - bool locksetContains(MutexID Lock) const { + bool locksetContains(const MutexID &Lock) const { return LSet.lookup(Lock); } /// \brief Returns true if the lockset contains a lock with the passed in /// locktype. - bool locksetContains(MutexID Lock, LockKind KindRequested) const { + bool locksetContains(const MutexID &Lock, LockKind KindRequested) const { const LockData *LockHeld = LSet.lookup(Lock); return (LockHeld && KindRequested == LockHeld->LKind); } @@ -307,7 +946,8 @@ class BuildLockset : public StmtVisitor<BuildLockset> { /// passed in locktype. So for example, if we pass in LK_Shared, this function /// returns true if the lock is held LK_Shared or LK_Exclusive. If we pass in /// LK_Exclusive, this function returns true if the lock is held LK_Exclusive. - bool locksetContainsAtLeast(MutexID Lock, LockKind KindRequested) const { + bool locksetContainsAtLeast(const MutexID &Lock, + LockKind KindRequested) const { switch (KindRequested) { case LK_Shared: return locksetContains(Lock); @@ -318,57 +958,121 @@ class BuildLockset : public StmtVisitor<BuildLockset> { } public: - BuildLockset(ThreadSafetyHandler &Handler, Lockset LS, Lockset::Factory &F) - : StmtVisitor<BuildLockset>(), Handler(Handler), LSet(LS), - LocksetFactory(F) {} - - Lockset getLockset() { - return LSet; - } + BuildLockset(ThreadSafetyAnalyzer *analyzer, CFGBlockInfo &Info) + : StmtVisitor<BuildLockset>(), + Handler(analyzer->Handler), + LocksetFactory(analyzer->LocksetFactory), + LocalVarMap(analyzer->LocalVarMap), + LSet(Info.EntrySet), + LVarCtx(Info.EntryContext), + CtxIndex(Info.EntryIndex) + {} void VisitUnaryOperator(UnaryOperator *UO); void VisitBinaryOperator(BinaryOperator *BO); void VisitCastExpr(CastExpr *CE); - void VisitCXXMemberCallExpr(CXXMemberCallExpr *Exp); + void VisitCallExpr(CallExpr *Exp); + void VisitCXXConstructExpr(CXXConstructExpr *Exp); + void VisitDeclStmt(DeclStmt *S); }; /// \brief Add a new lock to the lockset, warning if the lock is already there. -/// \param LockLoc The source location of the acquire -/// \param LockExp The lock expression corresponding to the lock to be added -void BuildLockset::addLock(SourceLocation LockLoc, Expr *LockExp, Expr *Parent, - LockKind LK) { - // FIXME: deal with acquired before/after annotations. We can write a first - // pass that does the transitive lookup lazily, and refine afterwards. - MutexID Mutex(LockExp, Parent); - if (!Mutex.isValid()) { - Handler.handleInvalidLockExp(LockExp->getExprLoc()); - return; - } - - LockData NewLock(LockLoc, LK); - +/// \param Mutex -- the Mutex expression for the lock +/// \param LDat -- the LockData for the lock +void BuildLockset::addLock(const MutexID &Mutex, const LockData& LDat) { + // FIXME: deal with acquired before/after annotations. // FIXME: Don't always warn when we have support for reentrant locks. if (locksetContains(Mutex)) - Handler.handleDoubleLock(Mutex.getName(), LockLoc); - LSet = LocksetFactory.add(LSet, Mutex, NewLock); + Handler.handleDoubleLock(Mutex.getName(), LDat.AcquireLoc); + else + LSet = LocksetFactory.add(LSet, Mutex, LDat); } /// \brief Remove a lock from the lockset, warning if the lock is not there. /// \param LockExp The lock expression corresponding to the lock to be removed /// \param UnlockLoc The source location of the unlock (only used in error msg) -void BuildLockset::removeLock(SourceLocation UnlockLoc, Expr *LockExp, - Expr *Parent) { - MutexID Mutex(LockExp, Parent); - if (!Mutex.isValid()) { - Handler.handleInvalidLockExp(LockExp->getExprLoc()); +void BuildLockset::removeLock(const MutexID &Mutex, SourceLocation UnlockLoc) { + const LockData *LDat = LSet.lookup(Mutex); + if (!LDat) + Handler.handleUnmatchedUnlock(Mutex.getName(), UnlockLoc); + else { + // For scoped-lockable vars, remove the mutex associated with this var. + if (LDat->UnderlyingMutex.isValid()) + removeLock(LDat->UnderlyingMutex, UnlockLoc); + LSet = LocksetFactory.remove(LSet, Mutex); + } +} + +/// \brief This function, parameterized by an attribute type, is used to add a +/// set of locks specified as attribute arguments to the lockset. +template <typename AttrType> +void BuildLockset::addLocksToSet(LockKind LK, AttrType *Attr, + Expr *Exp, NamedDecl* FunDecl, VarDecl *VD) { + typedef typename AttrType::args_iterator iterator_type; + + SourceLocation ExpLocation = Exp->getExprLoc(); + + // Figure out if we're calling the constructor of scoped lockable class + bool isScopedVar = false; + if (VD) { + if (CXXConstructorDecl *CD = dyn_cast<CXXConstructorDecl>(FunDecl)) { + CXXRecordDecl* PD = CD->getParent(); + if (PD && PD->getAttr<ScopedLockableAttr>()) + isScopedVar = true; + } + } + + if (Attr->args_size() == 0) { + // The mutex held is the "this" object. + MutexID Mutex(0, Exp, FunDecl); + if (!Mutex.isValid()) + MutexID::warnInvalidLock(Handler, 0, Exp, FunDecl); + else + addLock(Mutex, LockData(ExpLocation, LK)); return; } - Lockset NewLSet = LocksetFactory.remove(LSet, Mutex); - if(NewLSet == LSet) - Handler.handleUnmatchedUnlock(Mutex.getName(), UnlockLoc); + for (iterator_type I=Attr->args_begin(), E=Attr->args_end(); I != E; ++I) { + MutexID Mutex(*I, Exp, FunDecl); + if (!Mutex.isValid()) + MutexID::warnInvalidLock(Handler, *I, Exp, FunDecl); + else { + addLock(Mutex, LockData(ExpLocation, LK)); + if (isScopedVar) { + // For scoped lockable vars, map this var to its underlying mutex. + DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, VD->getLocation()); + MutexID SMutex(&DRE, 0, 0); + addLock(SMutex, LockData(VD->getLocation(), LK, Mutex)); + } + } + } +} - LSet = NewLSet; +/// \brief This function removes a set of locks specified as attribute +/// arguments from the lockset. +void BuildLockset::removeLocksFromSet(UnlockFunctionAttr *Attr, + Expr *Exp, NamedDecl* FunDecl) { + SourceLocation ExpLocation; + if (Exp) ExpLocation = Exp->getExprLoc(); + + if (Attr->args_size() == 0) { + // The mutex held is the "this" object. + MutexID Mu(0, Exp, FunDecl); + if (!Mu.isValid()) + MutexID::warnInvalidLock(Handler, 0, Exp, FunDecl); + else + removeLock(Mu, ExpLocation); + return; + } + + for (UnlockFunctionAttr::args_iterator I = Attr->args_begin(), + E = Attr->args_end(); I != E; ++I) { + MutexID Mutex(*I, Exp, FunDecl); + if (!Mutex.isValid()) + MutexID::warnInvalidLock(Handler, *I, Exp, FunDecl); + else + removeLock(Mutex, ExpLocation); + } } /// \brief Gets the value decl pointer from DeclRefExprs or MemberExprs @@ -383,20 +1087,19 @@ const ValueDecl *BuildLockset::getValueDecl(Expr *Exp) { } /// \brief Warn if the LSet does not contain a lock sufficient to protect access -/// of at least the passed in AccessType. +/// of at least the passed in AccessKind. void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, Expr *Exp, AccessKind AK, Expr *MutexExp, ProtectedOperationKind POK) { LockKind LK = getLockKindFromAccessKind(AK); - Expr *Parent = getParent(Exp); - MutexID Mutex(MutexExp, Parent); + + MutexID Mutex(MutexExp, Exp, D); if (!Mutex.isValid()) - Handler.handleInvalidLockExp(MutexExp->getExprLoc()); + MutexID::warnInvalidLock(Handler, MutexExp, Exp, D); else if (!locksetContainsAtLeast(Mutex, LK)) Handler.handleMutexNotHeld(D, POK, Mutex.getName(), LK, Exp->getExprLoc()); } - /// \brief This method identifies variable dereferences and checks pt_guarded_by /// and pt_guarded_var annotations. Note that we only check these annotations /// at the time a pointer is dereferenced. @@ -440,71 +1143,10 @@ void BuildLockset::checkAccess(Expr *Exp, AccessKind AK) { warnIfMutexNotHeld(D, Exp, AK, GBAttr->getArg(), POK_VarAccess); } -/// \brief For unary operations which read and write a variable, we need to -/// check whether we hold any required mutexes. Reads are checked in -/// VisitCastExpr. -void BuildLockset::VisitUnaryOperator(UnaryOperator *UO) { - switch (UO->getOpcode()) { - case clang::UO_PostDec: - case clang::UO_PostInc: - case clang::UO_PreDec: - case clang::UO_PreInc: { - Expr *SubExp = UO->getSubExpr()->IgnoreParenCasts(); - checkAccess(SubExp, AK_Written); - checkDereference(SubExp, AK_Written); - break; - } - default: - break; - } -} - -/// For binary operations which assign to a variable (writes), we need to check -/// whether we hold any required mutexes. -/// FIXME: Deal with non-primitive types. -void BuildLockset::VisitBinaryOperator(BinaryOperator *BO) { - if (!BO->isAssignmentOp()) - return; - Expr *LHSExp = BO->getLHS()->IgnoreParenCasts(); - checkAccess(LHSExp, AK_Written); - checkDereference(LHSExp, AK_Written); -} - -/// Whenever we do an LValue to Rvalue cast, we are reading a variable and -/// need to ensure we hold any required mutexes. -/// FIXME: Deal with non-primitive types. -void BuildLockset::VisitCastExpr(CastExpr *CE) { - if (CE->getCastKind() != CK_LValueToRValue) - return; - Expr *SubExp = CE->getSubExpr()->IgnoreParenCasts(); - checkAccess(SubExp, AK_Read); - checkDereference(SubExp, AK_Read); -} - -/// \brief This function, parameterized by an attribute type, is used to add a -/// set of locks specified as attribute arguments to the lockset. -template <typename AttrType> -void BuildLockset::addLocksToSet(LockKind LK, Attr *Attr, - CXXMemberCallExpr *Exp) { - typedef typename AttrType::args_iterator iterator_type; - SourceLocation ExpLocation = Exp->getExprLoc(); - Expr *Parent = Exp->getImplicitObjectArgument(); - AttrType *SpecificAttr = cast<AttrType>(Attr); - - if (SpecificAttr->args_size() == 0) { - // The mutex held is the "this" object. - addLock(ExpLocation, Parent, 0, LK); - return; - } - - for (iterator_type I = SpecificAttr->args_begin(), - E = SpecificAttr->args_end(); I != E; ++I) - addLock(ExpLocation, *I, Parent, LK); -} - -/// \brief When visiting CXXMemberCallExprs we need to examine the attributes on -/// the method that is being called and add, remove or check locks in the -/// lockset accordingly. +/// \brief Process a function call, method call, constructor call, +/// or destructor call. This involves looking at the attributes on the +/// corresponding function/method/constructor/destructor, issuing warnings, +/// and updating the locksets accordingly. /// /// FIXME: For classes annotated with one of the guarded annotations, we need /// to treat const method calls as reads and non-const method calls as writes, @@ -515,44 +1157,32 @@ void BuildLockset::addLocksToSet(LockKind LK, Attr *Attr, /// /// FIXME: Do not flag an error for member variables accessed in constructors/ /// destructors -void BuildLockset::VisitCXXMemberCallExpr(CXXMemberCallExpr *Exp) { - NamedDecl *D = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); - - SourceLocation ExpLocation = Exp->getExprLoc(); - Expr *Parent = Exp->getImplicitObjectArgument(); - - if(!D || !D->hasAttrs()) - return; - +void BuildLockset::handleCall(Expr *Exp, NamedDecl *D, VarDecl *VD) { AttrVec &ArgAttrs = D->getAttrs(); for(unsigned i = 0; i < ArgAttrs.size(); ++i) { Attr *Attr = ArgAttrs[i]; switch (Attr->getKind()) { // When we encounter an exclusive lock function, we need to add the lock // to our lockset with kind exclusive. - case attr::ExclusiveLockFunction: - addLocksToSet<ExclusiveLockFunctionAttr>(LK_Exclusive, Attr, Exp); + case attr::ExclusiveLockFunction: { + ExclusiveLockFunctionAttr *A = cast<ExclusiveLockFunctionAttr>(Attr); + addLocksToSet(LK_Exclusive, A, Exp, D, VD); break; + } // When we encounter a shared lock function, we need to add the lock // to our lockset with kind shared. - case attr::SharedLockFunction: - addLocksToSet<SharedLockFunctionAttr>(LK_Shared, Attr, Exp); + case attr::SharedLockFunction: { + SharedLockFunctionAttr *A = cast<SharedLockFunctionAttr>(Attr); + addLocksToSet(LK_Shared, A, Exp, D, VD); break; + } // When we encounter an unlock function, we need to remove unlocked // mutexes from the lockset, and flag a warning if they are not there. case attr::UnlockFunction: { UnlockFunctionAttr *UFAttr = cast<UnlockFunctionAttr>(Attr); - - if (UFAttr->args_size() == 0) { // The lock held is the "this" object. - removeLock(ExpLocation, Parent, 0); - break; - } - - for (UnlockFunctionAttr::args_iterator I = UFAttr->args_begin(), - E = UFAttr->args_end(); I != E; ++I) - removeLock(ExpLocation, *I, Parent); + removeLocksFromSet(UFAttr, Exp, D); break; } @@ -579,12 +1209,12 @@ void BuildLockset::VisitCXXMemberCallExpr(CXXMemberCallExpr *Exp) { LocksExcludedAttr *LEAttr = cast<LocksExcludedAttr>(Attr); for (LocksExcludedAttr::args_iterator I = LEAttr->args_begin(), E = LEAttr->args_end(); I != E; ++I) { - MutexID Mutex(*I, Parent); + MutexID Mutex(*I, Exp, D); if (!Mutex.isValid()) - Handler.handleInvalidLockExp((*I)->getExprLoc()); + MutexID::warnInvalidLock(Handler, *I, Exp, D); else if (locksetContains(Mutex)) Handler.handleFunExcludesLock(D->getName(), Mutex.getName(), - ExpLocation); + Exp->getExprLoc()); } break; } @@ -596,7 +1226,180 @@ void BuildLockset::VisitCXXMemberCallExpr(CXXMemberCallExpr *Exp) { } } -} // end anonymous namespace + +/// \brief Add lock to set, if the current block is in the taken branch of a +/// trylock. +template <class AttrType> +void BuildLockset::addTrylock(LockKind LK, AttrType *Attr, Expr *Exp, + NamedDecl *FunDecl, const CFGBlock *PredBlock, + const CFGBlock *CurrBlock, Expr *BrE, bool Neg) { + // Find out which branch has the lock + bool branch = 0; + if (CXXBoolLiteralExpr *BLE = dyn_cast_or_null<CXXBoolLiteralExpr>(BrE)) { + branch = BLE->getValue(); + } + else if (IntegerLiteral *ILE = dyn_cast_or_null<IntegerLiteral>(BrE)) { + branch = ILE->getValue().getBoolValue(); + } + int branchnum = branch ? 0 : 1; + if (Neg) branchnum = !branchnum; + + // If we've taken the trylock branch, then add the lock + int i = 0; + for (CFGBlock::const_succ_iterator SI = PredBlock->succ_begin(), + SE = PredBlock->succ_end(); SI != SE && i < 2; ++SI, ++i) { + if (*SI == CurrBlock && i == branchnum) { + addLocksToSet(LK, Attr, Exp, FunDecl, 0); + } + } +} + + +// If Cond can be traced back to a function call, return the call expression. +// The negate variable should be called with false, and will be set to true +// if the function call is negated, e.g. if (!mu.tryLock(...)) +CallExpr* BuildLockset::getTrylockCallExpr(Stmt *Cond, + LocalVariableMap::Context C, + bool &Negate) { + if (!Cond) + return 0; + + if (CallExpr *CallExp = dyn_cast<CallExpr>(Cond)) { + return CallExp; + } + else if (ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(Cond)) { + return getTrylockCallExpr(CE->getSubExpr(), C, Negate); + } + else if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Cond)) { + Expr *E = LocalVarMap.lookupExpr(DRE->getDecl(), C); + return getTrylockCallExpr(E, C, Negate); + } + else if (UnaryOperator *UOP = dyn_cast<UnaryOperator>(Cond)) { + if (UOP->getOpcode() == UO_LNot) { + Negate = !Negate; + return getTrylockCallExpr(UOP->getSubExpr(), C, Negate); + } + } + // FIXME -- handle && and || as well. + return NULL; +} + + +/// \brief Process a conditional branch from a previous block to the current +/// block, looking for trylock calls. +void BuildLockset::handleTrylock(Stmt *Cond, const CFGBlock *PredBlock, + const CFGBlock *CurrBlock) { + bool Negate = false; + CallExpr *Exp = getTrylockCallExpr(Cond, LVarCtx, Negate); + if (!Exp) + return; + + NamedDecl *FunDecl = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); + if(!FunDecl || !FunDecl->hasAttrs()) + return; + + // If the condition is a call to a Trylock function, then grab the attributes + AttrVec &ArgAttrs = FunDecl->getAttrs(); + for (unsigned i = 0; i < ArgAttrs.size(); ++i) { + Attr *Attr = ArgAttrs[i]; + switch (Attr->getKind()) { + case attr::ExclusiveTrylockFunction: { + ExclusiveTrylockFunctionAttr *A = + cast<ExclusiveTrylockFunctionAttr>(Attr); + addTrylock(LK_Exclusive, A, Exp, FunDecl, PredBlock, CurrBlock, + A->getSuccessValue(), Negate); + break; + } + case attr::SharedTrylockFunction: { + SharedTrylockFunctionAttr *A = + cast<SharedTrylockFunctionAttr>(Attr); + addTrylock(LK_Shared, A, Exp, FunDecl, PredBlock, CurrBlock, + A->getSuccessValue(), Negate); + break; + } + default: + break; + } + } +} + + +/// \brief For unary operations which read and write a variable, we need to +/// check whether we hold any required mutexes. Reads are checked in +/// VisitCastExpr. +void BuildLockset::VisitUnaryOperator(UnaryOperator *UO) { + switch (UO->getOpcode()) { + case clang::UO_PostDec: + case clang::UO_PostInc: + case clang::UO_PreDec: + case clang::UO_PreInc: { + Expr *SubExp = UO->getSubExpr()->IgnoreParenCasts(); + checkAccess(SubExp, AK_Written); + checkDereference(SubExp, AK_Written); + break; + } + default: + break; + } +} + +/// For binary operations which assign to a variable (writes), we need to check +/// whether we hold any required mutexes. +/// FIXME: Deal with non-primitive types. +void BuildLockset::VisitBinaryOperator(BinaryOperator *BO) { + if (!BO->isAssignmentOp()) + return; + + // adjust the context + LVarCtx = LocalVarMap.getNextContext(CtxIndex, BO, LVarCtx); + + Expr *LHSExp = BO->getLHS()->IgnoreParenCasts(); + checkAccess(LHSExp, AK_Written); + checkDereference(LHSExp, AK_Written); +} + +/// Whenever we do an LValue to Rvalue cast, we are reading a variable and +/// need to ensure we hold any required mutexes. +/// FIXME: Deal with non-primitive types. +void BuildLockset::VisitCastExpr(CastExpr *CE) { + if (CE->getCastKind() != CK_LValueToRValue) + return; + Expr *SubExp = CE->getSubExpr()->IgnoreParenCasts(); + checkAccess(SubExp, AK_Read); + checkDereference(SubExp, AK_Read); +} + + +void BuildLockset::VisitCallExpr(CallExpr *Exp) { + NamedDecl *D = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); + if(!D || !D->hasAttrs()) + return; + handleCall(Exp, D); +} + +void BuildLockset::VisitCXXConstructExpr(CXXConstructExpr *Exp) { + // FIXME -- only handles constructors in DeclStmt below. +} + +void BuildLockset::VisitDeclStmt(DeclStmt *S) { + // adjust the context + LVarCtx = LocalVarMap.getNextContext(CtxIndex, S, LVarCtx); + + DeclGroupRef DGrp = S->getDeclGroup(); + for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) { + Decl *D = *I; + if (VarDecl *VD = dyn_cast_or_null<VarDecl>(D)) { + Expr *E = VD->getInit(); + if (CXXConstructExpr *CE = dyn_cast_or_null<CXXConstructExpr>(E)) { + NamedDecl *CtorD = dyn_cast_or_null<NamedDecl>(CE->getConstructor()); + if (!CtorD || !CtorD->hasAttrs()) + return; + handleCall(CE, CtorD, VD); + } + } + } +} + /// \brief Compute the intersection of two locksets and issue warnings for any /// locks in the symmetric difference. @@ -606,9 +1409,14 @@ void BuildLockset::VisitCXXMemberCallExpr(CXXMemberCallExpr *Exp) { /// A; if () then B; else C; D; we need to check that the lockset after B and C /// are the same. In the event of a difference, we use the intersection of these /// two locksets at the start of D. -static Lockset intersectAndWarn(ThreadSafetyHandler &Handler, - const Lockset LSet1, const Lockset LSet2, - Lockset::Factory &Fact, LockErrorKind LEK) { +Lockset ThreadSafetyAnalyzer::intersectAndWarn(const CFGBlockInfo &Block1, + CFGBlockSide Side1, + const CFGBlockInfo &Block2, + CFGBlockSide Side2, + LockErrorKind LEK) { + Lockset LSet1 = Block1.getSet(Side1); + Lockset LSet2 = Block2.getSet(Side2); + Lockset Intersection = LSet1; for (Lockset::iterator I = LSet2.begin(), E = LSet2.end(); I != E; ++I) { const MutexID &LSet2Mutex = I.getKey(); @@ -619,11 +1427,13 @@ static Lockset intersectAndWarn(ThreadSafetyHandler &Handler, LSet2LockData.AcquireLoc, LD->AcquireLoc); if (LD->LKind != LK_Exclusive) - Intersection = Fact.add(Intersection, LSet2Mutex, LSet2LockData); + Intersection = LocksetFactory.add(Intersection, LSet2Mutex, + LSet2LockData); } } else { Handler.handleMutexHeldEndOfScope(LSet2Mutex.getName(), - LSet2LockData.AcquireLoc, LEK); + LSet2LockData.AcquireLoc, + Block1.getLocation(Side1), LEK); } } @@ -632,91 +1442,111 @@ static Lockset intersectAndWarn(ThreadSafetyHandler &Handler, const MutexID &Mutex = I.getKey(); const LockData &MissingLock = I.getData(); Handler.handleMutexHeldEndOfScope(Mutex.getName(), - MissingLock.AcquireLoc, LEK); - Intersection = Fact.remove(Intersection, Mutex); + MissingLock.AcquireLoc, + Block2.getLocation(Side2), LEK); + Intersection = LocksetFactory.remove(Intersection, Mutex); } } return Intersection; } -static Lockset addLock(ThreadSafetyHandler &Handler, - Lockset::Factory &LocksetFactory, - Lockset &LSet, Expr *LockExp, LockKind LK, - SourceLocation Loc) { - MutexID Mutex(LockExp, 0); +Lockset ThreadSafetyAnalyzer::addLock(Lockset &LSet, Expr *MutexExp, + const NamedDecl *D, + LockKind LK, SourceLocation Loc) { + MutexID Mutex(MutexExp, 0, D); if (!Mutex.isValid()) { - Handler.handleInvalidLockExp(LockExp->getExprLoc()); + MutexID::warnInvalidLock(Handler, MutexExp, 0, D); return LSet; } LockData NewLock(Loc, LK); return LocksetFactory.add(LSet, Mutex, NewLock); } -namespace clang { -namespace thread_safety { /// \brief Check a function's CFG for thread-safety violations. /// /// We traverse the blocks in the CFG, compute the set of mutexes that are held /// at the end of each block, and issue warnings for thread safety violations. /// Each block in the CFG is traversed exactly once. -void runThreadSafetyAnalysis(AnalysisContext &AC, - ThreadSafetyHandler &Handler) { +void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { CFG *CFGraph = AC.getCFG(); if (!CFGraph) return; - const Decl *D = AC.getDecl(); - if (D && D->getAttr<NoThreadSafetyAnalysisAttr>()) return; + const NamedDecl *D = dyn_cast_or_null<NamedDecl>(AC.getDecl()); - Lockset::Factory LocksetFactory; - - // FIXME: Swith to SmallVector? Otherwise improve performance impact? - std::vector<Lockset> EntryLocksets(CFGraph->getNumBlockIDs(), - LocksetFactory.getEmptyMap()); - std::vector<Lockset> ExitLocksets(CFGraph->getNumBlockIDs(), - LocksetFactory.getEmptyMap()); + if (!D) + return; // Ignore anonymous functions for now. + if (D->getAttr<NoThreadSafetyAnalysisAttr>()) + return; + // FIXME: Do something a bit more intelligent inside constructor and + // destructor code. Constructors and destructors must assume unique access + // to 'this', so checks on member variable access is disabled, but we should + // still enable checks on other objects. + if (isa<CXXConstructorDecl>(D)) + return; // Don't check inside constructors. + if (isa<CXXDestructorDecl>(D)) + return; // Don't check inside destructors. + + std::vector<CFGBlockInfo> BlockInfo(CFGraph->getNumBlockIDs(), + CFGBlockInfo::getEmptyBlockInfo(LocksetFactory, LocalVarMap)); // We need to explore the CFG via a "topological" ordering. // That way, we will be guaranteed to have information about required // predecessor locksets when exploring a new block. - TopologicallySortedCFG SortedGraph(CFGraph); - CFGBlockSet VisitedBlocks(CFGraph); + PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>(); + PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); + + // Compute SSA names for local variables + LocalVarMap.traverseCFG(CFGraph, SortedGraph, BlockInfo); + + // Fill in source locations for all CFGBlocks. + findBlockLocations(CFGraph, SortedGraph, BlockInfo); - if (!SortedGraph.empty() && D->hasAttrs()) { - const CFGBlock *FirstBlock = *SortedGraph.begin(); - Lockset &InitialLockset = EntryLocksets[FirstBlock->getBlockID()]; + // Add locks from exclusive_locks_required and shared_locks_required + // to initial lockset. Also turn off checking for lock and unlock functions. + // FIXME: is there a more intelligent way to check lock/unlock functions? + if (!SortedGraph->empty() && D->hasAttrs()) { + const CFGBlock *FirstBlock = *SortedGraph->begin(); + Lockset &InitialLockset = BlockInfo[FirstBlock->getBlockID()].EntrySet; const AttrVec &ArgAttrs = D->getAttrs(); - for(unsigned i = 0; i < ArgAttrs.size(); ++i) { + for (unsigned i = 0; i < ArgAttrs.size(); ++i) { Attr *Attr = ArgAttrs[i]; SourceLocation AttrLoc = Attr->getLocation(); if (SharedLocksRequiredAttr *SLRAttr = dyn_cast<SharedLocksRequiredAttr>(Attr)) { for (SharedLocksRequiredAttr::args_iterator - SLRIter = SLRAttr->args_begin(), - SLREnd = SLRAttr->args_end(); SLRIter != SLREnd; ++SLRIter) - InitialLockset = addLock(Handler, LocksetFactory, InitialLockset, - *SLRIter, LK_Shared, + SLRIter = SLRAttr->args_begin(), + SLREnd = SLRAttr->args_end(); SLRIter != SLREnd; ++SLRIter) + InitialLockset = addLock(InitialLockset, + *SLRIter, D, LK_Shared, AttrLoc); } else if (ExclusiveLocksRequiredAttr *ELRAttr = dyn_cast<ExclusiveLocksRequiredAttr>(Attr)) { for (ExclusiveLocksRequiredAttr::args_iterator - ELRIter = ELRAttr->args_begin(), - ELREnd = ELRAttr->args_end(); ELRIter != ELREnd; ++ELRIter) - InitialLockset = addLock(Handler, LocksetFactory, InitialLockset, - *ELRIter, LK_Exclusive, + ELRIter = ELRAttr->args_begin(), + ELREnd = ELRAttr->args_end(); ELRIter != ELREnd; ++ELRIter) + InitialLockset = addLock(InitialLockset, + *ELRIter, D, LK_Exclusive, AttrLoc); + } else if (isa<UnlockFunctionAttr>(Attr)) { + // Don't try to check unlock functions for now + return; + } else if (isa<ExclusiveLockFunctionAttr>(Attr)) { + // Don't try to check lock functions for now + return; + } else if (isa<SharedLockFunctionAttr>(Attr)) { + // Don't try to check lock functions for now + return; } } } - for (TopologicallySortedCFG::iterator I = SortedGraph.begin(), - E = SortedGraph.end(); I!= E; ++I) { + for (PostOrderCFGView::iterator I = SortedGraph->begin(), + E = SortedGraph->end(); I!= E; ++I) { const CFGBlock *CurrBlock = *I; int CurrBlockID = CurrBlock->getBlockID(); - - VisitedBlocks.insert(CurrBlock); + CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; // Use the default initial lockset in case there are no predecessors. - Lockset &Entryset = EntryLocksets[CurrBlockID]; - Lockset &Exitset = ExitLocksets[CurrBlockID]; + VisitedBlocks.insert(CurrBlock); // Iterate through the predecessor blocks and warn if the lockset for all // predecessors is not the same. We take the entry lockset of the current @@ -732,6 +1562,7 @@ void runThreadSafetyAnalysis(AnalysisContext &AC, // union because the real error is probably that we forgot to unlock M on // all code paths. bool LocksetInitialized = false; + llvm::SmallVector<CFGBlock*, 8> SpecialBlocks; for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), PE = CurrBlock->pred_end(); PI != PE; ++PI) { @@ -739,24 +1570,102 @@ void runThreadSafetyAnalysis(AnalysisContext &AC, if (*PI == 0 || !VisitedBlocks.alreadySet(*PI)) continue; + // Ignore edges from blocks that can't return. + if ((*PI)->hasNoReturnElement()) + continue; + + // If the previous block ended in a 'continue' or 'break' statement, then + // a difference in locksets is probably due to a bug in that block, rather + // than in some other predecessor. In that case, keep the other + // predecessor's lockset. + if (const Stmt *Terminator = (*PI)->getTerminator()) { + if (isa<ContinueStmt>(Terminator) || isa<BreakStmt>(Terminator)) { + SpecialBlocks.push_back(*PI); + continue; + } + } + int PrevBlockID = (*PI)->getBlockID(); + CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; + if (!LocksetInitialized) { - Entryset = ExitLocksets[PrevBlockID]; + CurrBlockInfo->EntrySet = PrevBlockInfo->ExitSet; LocksetInitialized = true; } else { - Entryset = intersectAndWarn(Handler, Entryset, - ExitLocksets[PrevBlockID], LocksetFactory, - LEK_LockedSomePredecessors); + CurrBlockInfo->EntrySet = + intersectAndWarn(*CurrBlockInfo, CBS_Entry, + *PrevBlockInfo, CBS_Exit, + LEK_LockedSomePredecessors); } } - BuildLockset LocksetBuilder(Handler, Entryset, LocksetFactory); + // Process continue and break blocks. Assume that the lockset for the + // resulting block is unaffected by any discrepancies in them. + for (unsigned SpecialI = 0, SpecialN = SpecialBlocks.size(); + SpecialI < SpecialN; ++SpecialI) { + CFGBlock *PrevBlock = SpecialBlocks[SpecialI]; + int PrevBlockID = PrevBlock->getBlockID(); + CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; + + if (!LocksetInitialized) { + CurrBlockInfo->EntrySet = PrevBlockInfo->ExitSet; + LocksetInitialized = true; + } else { + // Determine whether this edge is a loop terminator for diagnostic + // purposes. FIXME: A 'break' statement might be a loop terminator, but + // it might also be part of a switch. Also, a subsequent destructor + // might add to the lockset, in which case the real issue might be a + // double lock on the other path. + const Stmt *Terminator = PrevBlock->getTerminator(); + bool IsLoop = Terminator && isa<ContinueStmt>(Terminator); + + // Do not update EntrySet. + intersectAndWarn(*CurrBlockInfo, CBS_Entry, *PrevBlockInfo, CBS_Exit, + IsLoop ? LEK_LockedSomeLoopIterations + : LEK_LockedSomePredecessors); + } + } + + BuildLockset LocksetBuilder(this, *CurrBlockInfo); + CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), + PE = CurrBlock->pred_end(); + if (PI != PE) { + // If the predecessor ended in a branch, then process any trylocks. + // FIXME -- check to make sure there's only one predecessor. + if (Stmt *TCE = (*PI)->getTerminatorCondition()) { + LocksetBuilder.handleTrylock(TCE, *PI, CurrBlock); + } + } + + // Visit all the statements in the basic block. for (CFGBlock::const_iterator BI = CurrBlock->begin(), BE = CurrBlock->end(); BI != BE; ++BI) { - if (const CFGStmt *CfgStmt = dyn_cast<CFGStmt>(&*BI)) - LocksetBuilder.Visit(const_cast<Stmt*>(CfgStmt->getStmt())); + switch (BI->getKind()) { + case CFGElement::Statement: { + const CFGStmt *CS = cast<CFGStmt>(&*BI); + LocksetBuilder.Visit(const_cast<Stmt*>(CS->getStmt())); + break; + } + // Ignore BaseDtor, MemberDtor, and TemporaryDtor for now. + case CFGElement::AutomaticObjectDtor: { + const CFGAutomaticObjDtor *AD = cast<CFGAutomaticObjDtor>(&*BI); + CXXDestructorDecl *DD = const_cast<CXXDestructorDecl*>( + AD->getDestructorDecl(AC.getASTContext())); + if (!DD->hasAttrs()) + break; + + // Create a dummy expression, + VarDecl *VD = const_cast<VarDecl*>(AD->getVarDecl()); + DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, + AD->getTriggerStmt()->getLocEnd()); + LocksetBuilder.handleCall(&DRE, DD); + break; + } + default: + break; + } } - Exitset = LocksetBuilder.getLockset(); + CurrBlockInfo->ExitSet = LocksetBuilder.LSet; // For every back edge from CurrBlock (the end of the loop) to another block // (FirstLoopBlock) we need to check that the Lockset of Block is equal to @@ -770,21 +1679,38 @@ void runThreadSafetyAnalysis(AnalysisContext &AC, continue; CFGBlock *FirstLoopBlock = *SI; - Lockset PreLoop = EntryLocksets[FirstLoopBlock->getBlockID()]; - Lockset LoopEnd = ExitLocksets[CurrBlockID]; - intersectAndWarn(Handler, LoopEnd, PreLoop, LocksetFactory, + CFGBlockInfo &PreLoop = BlockInfo[FirstLoopBlock->getBlockID()]; + CFGBlockInfo &LoopEnd = BlockInfo[CurrBlockID]; + intersectAndWarn(LoopEnd, CBS_Exit, PreLoop, CBS_Entry, LEK_LockedSomeLoopIterations); } } - Lockset InitialLockset = EntryLocksets[CFGraph->getEntry().getBlockID()]; - Lockset FinalLockset = ExitLocksets[CFGraph->getExit().getBlockID()]; + CFGBlockInfo &Initial = BlockInfo[CFGraph->getEntry().getBlockID()]; + CFGBlockInfo &Final = BlockInfo[CFGraph->getExit().getBlockID()]; // FIXME: Should we call this function for all blocks which exit the function? - intersectAndWarn(Handler, InitialLockset, FinalLockset, LocksetFactory, + intersectAndWarn(Initial, CBS_Entry, Final, CBS_Exit, LEK_LockedAtEndOfFunction); } +} // end anonymous namespace + + +namespace clang { +namespace thread_safety { + +/// \brief Check a function's CFG for thread-safety violations. +/// +/// We traverse the blocks in the CFG, compute the set of mutexes that are held +/// at the end of each block, and issue warnings for thread safety violations. +/// Each block in the CFG is traversed exactly once. +void runThreadSafetyAnalysis(AnalysisDeclContext &AC, + ThreadSafetyHandler &Handler) { + ThreadSafetyAnalyzer Analyzer(Handler); + Analyzer.runAnalysis(AC); +} + /// \brief Helper function that returns a LockKind required for the given level /// of access. LockKind getLockKindFromAccessKind(AccessKind AK) { @@ -796,4 +1722,5 @@ LockKind getLockKindFromAccessKind(AccessKind AK) { } llvm_unreachable("Unknown AccessKind"); } + }} // end namespace clang::thread_safety diff --git a/contrib/llvm/tools/clang/lib/Analysis/UninitializedValues.cpp b/contrib/llvm/tools/clang/lib/Analysis/UninitializedValues.cpp index 9e98560..6e5da25 100644 --- a/contrib/llvm/tools/clang/lib/Analysis/UninitializedValues.cpp +++ b/contrib/llvm/tools/clang/lib/Analysis/UninitializedValues.cpp @@ -21,7 +21,7 @@ #include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" #include "clang/Analysis/Analyses/UninitializedValues.h" -#include "clang/Analysis/Support/SaveAndRestore.h" +#include "llvm/Support/SaveAndRestore.h" using namespace clang; @@ -337,7 +337,7 @@ public: class TransferFunctions : public StmtVisitor<TransferFunctions> { CFGBlockValues &vals; const CFG &cfg; - AnalysisContext ∾ + AnalysisDeclContext ∾ UninitVariablesHandler *handler; /// The last DeclRefExpr seen when analyzing a block. Used to @@ -356,7 +356,7 @@ class TransferFunctions : public StmtVisitor<TransferFunctions> { public: TransferFunctions(CFGBlockValues &vals, const CFG &cfg, - AnalysisContext &ac, + AnalysisDeclContext &ac, UninitVariablesHandler *handler) : vals(vals), cfg(cfg), ac(ac), handler(handler), lastDR(0), lastLoad(0), @@ -615,7 +615,7 @@ void TransferFunctions::ProcessUses(Stmt *s) { //====------------------------------------------------------------------------// static bool runOnBlock(const CFGBlock *block, const CFG &cfg, - AnalysisContext &ac, CFGBlockValues &vals, + AnalysisDeclContext &ac, CFGBlockValues &vals, llvm::BitVector &wasAnalyzed, UninitVariablesHandler *handler = 0) { @@ -672,7 +672,7 @@ static bool runOnBlock(const CFGBlock *block, const CFG &cfg, void clang::runUninitializedVariablesAnalysis( const DeclContext &dc, const CFG &cfg, - AnalysisContext &ac, + AnalysisDeclContext &ac, UninitVariablesHandler &handler, UninitVariablesAnalysisStats &stats) { CFGBlockValues vals(cfg); |
