diff options
Diffstat (limited to 'contrib/llvm/tools/clang/lib/Analysis/ThreadSafety.cpp')
| -rw-r--r-- | contrib/llvm/tools/clang/lib/Analysis/ThreadSafety.cpp | 1533 |
1 files changed, 1230 insertions, 303 deletions
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 |
