contrib/llvm/tools/clang/lib/Analysis/ThreadSafety.cpp

   1 //===- ThreadSafety.cpp ----------------------------------------*- C++ --*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // A intra-procedural analysis for thread safety (e.g. deadlocks and race
  11 // conditions), based off of an annotation system.
  12 //
  13 // See http://clang.llvm.org/docs/LanguageExtensions.html#threadsafety for more
  14 // information.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "clang/Analysis/Analyses/ThreadSafety.h"
  19 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
  20 #include "clang/Analysis/AnalysisContext.h"
  21 #include "clang/Analysis/CFG.h"
  22 #include "clang/Analysis/CFGStmtMap.h"
  23 #include "clang/AST/DeclCXX.h"
  24 #include "clang/AST/ExprCXX.h"
  25 #include "clang/AST/StmtCXX.h"
  26 #include "clang/AST/StmtVisitor.h"
  27 #include "clang/Basic/SourceManager.h"
  28 #include "clang/Basic/SourceLocation.h"
  29 #include "llvm/ADT/BitVector.h"
  30 #include "llvm/ADT/FoldingSet.h"
  31 #include "llvm/ADT/ImmutableMap.h"
  32 #include "llvm/ADT/PostOrderIterator.h"
  33 #include "llvm/ADT/SmallVector.h"
  34 #include "llvm/ADT/StringRef.h"
  35 #include "llvm/Support/raw_ostream.h"
  36 #include <algorithm>
  37 #include <utility>
  38 #include <vector>
  39
  40 using namespace clang;
  41 using namespace thread_safety;
  42
  43 // Key method definition
  44 ThreadSafetyHandler::~ThreadSafetyHandler() {}
  45
  46 namespace {
  47
  48 /// \brief A MutexID object uniquely identifies a particular mutex, and
  49 /// is built from an Expr* (i.e. calling a lock function).
  50 ///
  51 /// Thread-safety analysis works by comparing lock expressions.  Within the
  52 /// body of a function, an expression such as "x->foo->bar.mu" will resolve to
  53 /// a particular mutex object at run-time.  Subsequent occurrences of the same
  54 /// expression (where "same" means syntactic equality) will refer to the same
  55 /// run-time object if three conditions hold:
  56 /// (1) Local variables in the expression, such as "x" have not changed.
  57 /// (2) Values on the heap that affect the expression have not changed.
  58 /// (3) The expression involves only pure function calls.
  59 ///
  60 /// The current implementation assumes, but does not verify, that multiple uses
  61 /// of the same lock expression satisfies these criteria.
  62 ///
  63 /// Clang introduces an additional wrinkle, which is that it is difficult to
  64 /// derive canonical expressions, or compare expressions directly for equality.
  65 /// Thus, we identify a mutex not by an Expr, but by the list of named
  66 /// declarations that are referenced by the Expr.  In other words,
  67 /// x->foo->bar.mu will be a four element vector with the Decls for
  68 /// mu, bar, and foo, and x.  The vector will uniquely identify the expression
  69 /// for all practical purposes.  Null is used to denote 'this'.
  70 ///
  71 /// Note we will need to perform substitution on "this" and function parameter
  72 /// names when constructing a lock expression.
  73 ///
  74 /// For example:
  75 /// class C { Mutex Mu;  void lock() EXCLUSIVE_LOCK_FUNCTION(this->Mu); };
  76 /// void myFunc(C *X) { ... X->lock() ... }
  77 /// The original expression for the mutex acquired by myFunc is "this->Mu", but
  78 /// "X" is substituted for "this" so we get X->Mu();
  79 ///
  80 /// For another example:
  81 /// foo(MyList *L) EXCLUSIVE_LOCKS_REQUIRED(L->Mu) { ... }
  82 /// MyList *MyL;
  83 /// foo(MyL);  // requires lock MyL->Mu to be held
  84 class MutexID {
  85   SmallVector<NamedDecl*, 2> DeclSeq;
  86
  87   /// Build a Decl sequence representing the lock from the given expression.
  88   /// Recursive function that terminates on DeclRefExpr.
  89   /// Note: this function merely creates a MutexID; it does not check to
  90   /// ensure that the original expression is a valid mutex expression.
  91   void buildMutexID(Expr *Exp, const NamedDecl *D, Expr *Parent,
  92                     unsigned NumArgs, Expr **FunArgs) {
  93     if (!Exp) {
  94       DeclSeq.clear();
  95       return;
  96     }
  97
  98     if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Exp)) {
  99       NamedDecl *ND = cast<NamedDecl>(DRE->getDecl()->getCanonicalDecl());
 100       ParmVarDecl *PV = dyn_cast_or_null<ParmVarDecl>(ND);
 101       if (PV) {
 102         FunctionDecl *FD =
 103           cast<FunctionDecl>(PV->getDeclContext())->getCanonicalDecl();
 104         unsigned i = PV->getFunctionScopeIndex();
 105
 106         if (FunArgs && FD == D->getCanonicalDecl()) {
 107           // Substitute call arguments for references to function parameters
 108           assert(i < NumArgs);
 109           buildMutexID(FunArgs[i], D, 0, 0, 0);
 110           return;
 111         }
 112         // Map the param back to the param of the original function declaration.
 113         DeclSeq.push_back(FD->getParamDecl(i));
 114         return;
 115       }
 116       // Not a function parameter -- just store the reference.
 117       DeclSeq.push_back(ND);
 118     } else if (MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) {
 119       NamedDecl *ND = ME->getMemberDecl();
 120       DeclSeq.push_back(ND);
 121       buildMutexID(ME->getBase(), D, Parent, NumArgs, FunArgs);
 122     } else if (isa<CXXThisExpr>(Exp)) {
 123       if (Parent)
 124         buildMutexID(Parent, D, 0, 0, 0);
 125       else {
 126         DeclSeq.push_back(0);  // Use 0 to represent 'this'.
 127         return;  // mutexID is still valid in this case
 128       }
 129     } else if (CXXMemberCallExpr *CMCE = dyn_cast<CXXMemberCallExpr>(Exp)) {
 130       DeclSeq.push_back(CMCE->getMethodDecl()->getCanonicalDecl());
 131       buildMutexID(CMCE->getImplicitObjectArgument(),
 132                    D, Parent, NumArgs, FunArgs);
 133       unsigned NumCallArgs = CMCE->getNumArgs();
 134       Expr** CallArgs = CMCE->getArgs();
 135       for (unsigned i = 0; i < NumCallArgs; ++i) {
 136         buildMutexID(CallArgs[i], D, Parent, NumArgs, FunArgs);
 137       }
 138     } else if (CallExpr *CE = dyn_cast<CallExpr>(Exp)) {
 139       buildMutexID(CE->getCallee(), D, Parent, NumArgs, FunArgs);
 140       unsigned NumCallArgs = CE->getNumArgs();
 141       Expr** CallArgs = CE->getArgs();
 142       for (unsigned i = 0; i < NumCallArgs; ++i) {
 143         buildMutexID(CallArgs[i], D, Parent, NumArgs, FunArgs);
 144       }
 145     } else if (BinaryOperator *BOE = dyn_cast<BinaryOperator>(Exp)) {
 146       buildMutexID(BOE->getLHS(), D, Parent, NumArgs, FunArgs);
 147       buildMutexID(BOE->getRHS(), D, Parent, NumArgs, FunArgs);
 148     } else if (UnaryOperator *UOE = dyn_cast<UnaryOperator>(Exp)) {
 149       buildMutexID(UOE->getSubExpr(), D, Parent, NumArgs, FunArgs);
 150     } else if (ArraySubscriptExpr *ASE = dyn_cast<ArraySubscriptExpr>(Exp)) {
 151       buildMutexID(ASE->getBase(), D, Parent, NumArgs, FunArgs);
 152       buildMutexID(ASE->getIdx(), D, Parent, NumArgs, FunArgs);
 153     } else if (AbstractConditionalOperator *CE =
 154                  dyn_cast<AbstractConditionalOperator>(Exp)) {
 155       buildMutexID(CE->getCond(), D, Parent, NumArgs, FunArgs);
 156       buildMutexID(CE->getTrueExpr(), D, Parent, NumArgs, FunArgs);
 157       buildMutexID(CE->getFalseExpr(), D, Parent, NumArgs, FunArgs);
 158     } else if (ChooseExpr *CE = dyn_cast<ChooseExpr>(Exp)) {
 159       buildMutexID(CE->getCond(), D, Parent, NumArgs, FunArgs);
 160       buildMutexID(CE->getLHS(), D, Parent, NumArgs, FunArgs);
 161       buildMutexID(CE->getRHS(), D, Parent, NumArgs, FunArgs);
 162     } else if (CastExpr *CE = dyn_cast<CastExpr>(Exp)) {
 163       buildMutexID(CE->getSubExpr(), D, Parent, NumArgs, FunArgs);
 164     } else if (ParenExpr *PE = dyn_cast<ParenExpr>(Exp)) {
 165       buildMutexID(PE->getSubExpr(), D, Parent, NumArgs, FunArgs);
 166     } else if (isa<CharacterLiteral>(Exp) ||
 167              isa<CXXNullPtrLiteralExpr>(Exp) ||
 168              isa<GNUNullExpr>(Exp) ||
 169              isa<CXXBoolLiteralExpr>(Exp) ||
 170              isa<FloatingLiteral>(Exp) ||
 171              isa<ImaginaryLiteral>(Exp) ||
 172              isa<IntegerLiteral>(Exp) ||
 173              isa<StringLiteral>(Exp) ||
 174              isa<ObjCStringLiteral>(Exp)) {
 175       return;  // FIXME: Ignore literals for now
 176     } else {
 177       // Ignore.  FIXME: mark as invalid expression?
 178     }
 179   }
 180
 181   /// \brief Construct a MutexID from an expression.
 182   /// \param MutexExp The original mutex expression within an attribute
 183   /// \param DeclExp An expression involving the Decl on which the attribute
 184   ///        occurs.
 185   /// \param D  The declaration to which the lock/unlock attribute is attached.
 186   void buildMutexIDFromExp(Expr *MutexExp, Expr *DeclExp, const NamedDecl *D) {
 187     Expr *Parent = 0;
 188     unsigned NumArgs = 0;
 189     Expr **FunArgs = 0;
 190
 191     // If we are processing a raw attribute expression, with no substitutions.
 192     if (DeclExp == 0) {
 193       buildMutexID(MutexExp, D, 0, 0, 0);
 194       return;
 195     }
 196
 197     // Examine DeclExp to find Parent and FunArgs, which are used to substitute
 198     // for formal parameters when we call buildMutexID later.
 199     if (MemberExpr *ME = dyn_cast<MemberExpr>(DeclExp)) {
 200       Parent = ME->getBase();
 201     } else if (CXXMemberCallExpr *CE = dyn_cast<CXXMemberCallExpr>(DeclExp)) {
 202       Parent = CE->getImplicitObjectArgument();
 203       NumArgs = CE->getNumArgs();
 204       FunArgs = CE->getArgs();
 205     } else if (CallExpr *CE = dyn_cast<CallExpr>(DeclExp)) {
 206       NumArgs = CE->getNumArgs();
 207       FunArgs = CE->getArgs();
 208     } else if (CXXConstructExpr *CE = dyn_cast<CXXConstructExpr>(DeclExp)) {
 209       Parent = 0;  // FIXME -- get the parent from DeclStmt
 210       NumArgs = CE->getNumArgs();
 211       FunArgs = CE->getArgs();
 212     } else if (D && isa<CXXDestructorDecl>(D)) {
 213       // There's no such thing as a "destructor call" in the AST.
 214       Parent = DeclExp;
 215     }
 216
 217     // If the attribute has no arguments, then assume the argument is "this".
 218     if (MutexExp == 0) {
 219       buildMutexID(Parent, D, 0, 0, 0);
 220       return;
 221     }
 222
 223     buildMutexID(MutexExp, D, Parent, NumArgs, FunArgs);
 224   }
 225
 226 public:
 227   explicit MutexID(clang::Decl::EmptyShell e) {
 228     DeclSeq.clear();
 229   }
 230
 231   /// \param MutexExp The original mutex expression within an attribute
 232   /// \param DeclExp An expression involving the Decl on which the attribute
 233   ///        occurs.
 234   /// \param D  The declaration to which the lock/unlock attribute is attached.
 235   /// Caller must check isValid() after construction.
 236   MutexID(Expr* MutexExp, Expr *DeclExp, const NamedDecl* D) {
 237     buildMutexIDFromExp(MutexExp, DeclExp, D);
 238   }
 239
 240   /// Return true if this is a valid decl sequence.
 241   /// Caller must call this by hand after construction to handle errors.
 242   bool isValid() const {
 243     return !DeclSeq.empty();
 244   }
 245
 246   /// Issue a warning about an invalid lock expression
 247   static void warnInvalidLock(ThreadSafetyHandler &Handler, Expr* MutexExp,
 248                               Expr *DeclExp, const NamedDecl* D) {
 249     SourceLocation Loc;
 250     if (DeclExp)
 251       Loc = DeclExp->getExprLoc();
 252
 253     // FIXME: add a note about the attribute location in MutexExp or D
 254     if (Loc.isValid())
 255       Handler.handleInvalidLockExp(Loc);
 256   }
 257
 258   bool operator==(const MutexID &other) const {
 259     return DeclSeq == other.DeclSeq;
 260   }
 261
 262   bool operator!=(const MutexID &other) const {
 263     return !(*this == other);
 264   }
 265
 266   // SmallVector overloads Operator< to do lexicographic ordering. Note that
 267   // we use pointer equality (and <) to compare NamedDecls. This means the order
 268   // of MutexIDs in a lockset is nondeterministic. In order to output
 269   // diagnostics in a deterministic ordering, we must order all diagnostics to
 270   // output by SourceLocation when iterating through this lockset.
 271   bool operator<(const MutexID &other) const {
 272     return DeclSeq < other.DeclSeq;
 273   }
 274
 275   /// \brief Returns the name of the first Decl in the list for a given MutexID;
 276   /// e.g. the lock expression foo.bar() has name "bar".
 277   /// The caret will point unambiguously to the lock expression, so using this
 278   /// name in diagnostics is a way to get simple, and consistent, mutex names.
 279   /// We do not want to output the entire expression text for security reasons.
 280   std::string getName() const {
 281     assert(isValid());
 282     if (!DeclSeq.front())
 283       return "this";  // Use 0 to represent 'this'.
 284     return DeclSeq.front()->getNameAsString();
 285   }
 286
 287   void Profile(llvm::FoldingSetNodeID &ID) const {
 288     for (SmallVectorImpl<NamedDecl*>::const_iterator I = DeclSeq.begin(),
 289          E = DeclSeq.end(); I != E; ++I) {
 290       ID.AddPointer(*I);
 291     }
 292   }
 293 };
 294
 295
 296 /// \brief This is a helper class that stores info about the most recent
 297 /// accquire of a Lock.
 298 ///
 299 /// The main body of the analysis maps MutexIDs to LockDatas.
 300 struct LockData {
 301   SourceLocation AcquireLoc;
 302
 303   /// \brief LKind stores whether a lock is held shared or exclusively.
 304   /// Note that this analysis does not currently support either re-entrant
 305   /// locking or lock "upgrading" and "downgrading" between exclusive and
 306   /// shared.
 307   ///
 308   /// FIXME: add support for re-entrant locking and lock up/downgrading
 309   LockKind LKind;
 310   MutexID UnderlyingMutex;  // for ScopedLockable objects
 311
 312   LockData(SourceLocation AcquireLoc, LockKind LKind)
 313     : AcquireLoc(AcquireLoc), LKind(LKind), UnderlyingMutex(Decl::EmptyShell())
 314   {}
 315
 316   LockData(SourceLocation AcquireLoc, LockKind LKind, const MutexID &Mu)
 317     : AcquireLoc(AcquireLoc), LKind(LKind), UnderlyingMutex(Mu) {}
 318
 319   bool operator==(const LockData &other) const {
 320     return AcquireLoc == other.AcquireLoc && LKind == other.LKind;
 321   }
 322
 323   bool operator!=(const LockData &other) const {
 324     return !(*this == other);
 325   }
 326
 327   void Profile(llvm::FoldingSetNodeID &ID) const {
 328     ID.AddInteger(AcquireLoc.getRawEncoding());
 329     ID.AddInteger(LKind);
 330   }
 331 };
 332
 333
 334 /// A Lockset maps each MutexID (defined above) to information about how it has
 335 /// been locked.
 336 typedef llvm::ImmutableMap<MutexID, LockData> Lockset;
 337 typedef llvm::ImmutableMap<NamedDecl*, unsigned> LocalVarContext;
 338
 339 class LocalVariableMap;
 340
 341 /// A side (entry or exit) of a CFG node.
 342 enum CFGBlockSide { CBS_Entry, CBS_Exit };
 343
 344 /// CFGBlockInfo is a struct which contains all the information that is
 345 /// maintained for each block in the CFG.  See LocalVariableMap for more
 346 /// information about the contexts.
 347 struct CFGBlockInfo {
 348   Lockset EntrySet;             // Lockset held at entry to block
 349   Lockset ExitSet;              // Lockset held at exit from block
 350   LocalVarContext EntryContext; // Context held at entry to block
 351   LocalVarContext ExitContext;  // Context held at exit from block
 352   SourceLocation EntryLoc;      // Location of first statement in block
 353   SourceLocation ExitLoc;       // Location of last statement in block.
 354   unsigned EntryIndex;          // Used to replay contexts later
 355
 356   const Lockset &getSet(CFGBlockSide Side) const {
 357     return Side == CBS_Entry ? EntrySet : ExitSet;
 358   }
 359   SourceLocation getLocation(CFGBlockSide Side) const {
 360     return Side == CBS_Entry ? EntryLoc : ExitLoc;
 361   }
 362
 363 private:
 364   CFGBlockInfo(Lockset EmptySet, LocalVarContext EmptyCtx)
 365     : EntrySet(EmptySet), ExitSet(EmptySet),
 366       EntryContext(EmptyCtx), ExitContext(EmptyCtx)
 367   { }
 368
 369 public:
 370   static CFGBlockInfo getEmptyBlockInfo(Lockset::Factory &F,
 371                                         LocalVariableMap &M);
 372 };
 373
 374
 375
 376 // A LocalVariableMap maintains a map from local variables to their currently
 377 // valid definitions.  It provides SSA-like functionality when traversing the
 378 // CFG.  Like SSA, each definition or assignment to a variable is assigned a
 379 // unique name (an integer), which acts as the SSA name for that definition.
 380 // The total set of names is shared among all CFG basic blocks.
 381 // Unlike SSA, we do not rewrite expressions to replace local variables declrefs
 382 // with their SSA-names.  Instead, we compute a Context for each point in the
 383 // code, which maps local variables to the appropriate SSA-name.  This map
 384 // changes with each assignment.
 385 //
 386 // The map is computed in a single pass over the CFG.  Subsequent analyses can
 387 // then query the map to find the appropriate Context for a statement, and use
 388 // that Context to look up the definitions of variables.
 389 class LocalVariableMap {
 390 public:
 391   typedef LocalVarContext Context;
 392
 393   /// A VarDefinition consists of an expression, representing the value of the
 394   /// variable, along with the context in which that expression should be
 395   /// interpreted.  A reference VarDefinition does not itself contain this
 396   /// information, but instead contains a pointer to a previous VarDefinition.
 397   struct VarDefinition {
 398   public:
 399     friend class LocalVariableMap;
 400
 401     NamedDecl *Dec;       // The original declaration for this variable.
 402     Expr *Exp;            // The expression for this variable, OR
 403     unsigned Ref;         // Reference to another VarDefinition
 404     Context Ctx;          // The map with which Exp should be interpreted.
 405
 406     bool isReference() { return !Exp; }
 407
 408   private:
 409     // Create ordinary variable definition
 410     VarDefinition(NamedDecl *D, Expr *E, Context C)
 411       : Dec(D), Exp(E), Ref(0), Ctx(C)
 412     { }
 413
 414     // Create reference to previous definition
 415     VarDefinition(NamedDecl *D, unsigned R, Context C)
 416       : Dec(D), Exp(0), Ref(R), Ctx(C)
 417     { }
 418   };
 419
 420 private:
 421   Context::Factory ContextFactory;
 422   std::vector<VarDefinition> VarDefinitions;
 423   std::vector<unsigned> CtxIndices;
 424   std::vector<std::pair<Stmt*, Context> > SavedContexts;
 425
 426 public:
 427   LocalVariableMap() {
 428     // index 0 is a placeholder for undefined variables (aka phi-nodes).
 429     VarDefinitions.push_back(VarDefinition(0, 0u, getEmptyContext()));
 430   }
 431
 432   /// Look up a definition, within the given context.
 433   const VarDefinition* lookup(NamedDecl *D, Context Ctx) {
 434     const unsigned *i = Ctx.lookup(D);
 435     if (!i)
 436       return 0;
 437     assert(*i < VarDefinitions.size());
 438     return &VarDefinitions[*i];
 439   }
 440
 441   /// Look up the definition for D within the given context.  Returns
 442   /// NULL if the expression is not statically known.  If successful, also
 443   /// modifies Ctx to hold the context of the return Expr.
 444   Expr* lookupExpr(NamedDecl *D, Context &Ctx) {
 445     const unsigned *P = Ctx.lookup(D);
 446     if (!P)
 447       return 0;
 448
 449     unsigned i = *P;
 450     while (i > 0) {
 451       if (VarDefinitions[i].Exp) {
 452         Ctx = VarDefinitions[i].Ctx;
 453         return VarDefinitions[i].Exp;
 454       }
 455       i = VarDefinitions[i].Ref;
 456     }
 457     return 0;
 458   }
 459
 460   Context getEmptyContext() { return ContextFactory.getEmptyMap(); }
 461
 462   /// Return the next context after processing S.  This function is used by
 463   /// clients of the class to get the appropriate context when traversing the
 464   /// CFG.  It must be called for every assignment or DeclStmt.
 465   Context getNextContext(unsigned &CtxIndex, Stmt *S, Context C) {
 466     if (SavedContexts[CtxIndex+1].first == S) {
 467       CtxIndex++;
 468       Context Result = SavedContexts[CtxIndex].second;
 469       return Result;
 470     }
 471     return C;
 472   }
 473
 474   void dumpVarDefinitionName(unsigned i) {
 475     if (i == 0) {
 476       llvm::errs() << "Undefined";
 477       return;
 478     }
 479     NamedDecl *Dec = VarDefinitions[i].Dec;
 480     if (!Dec) {
 481       llvm::errs() << "<<NULL>>";
 482       return;
 483     }
 484     Dec->printName(llvm::errs());
 485     llvm::errs() << "." << i << " " << ((void*) Dec);
 486   }
 487
 488   /// Dumps an ASCII representation of the variable map to llvm::errs()
 489   void dump() {
 490     for (unsigned i = 1, e = VarDefinitions.size(); i < e; ++i) {
 491       Expr *Exp = VarDefinitions[i].Exp;
 492       unsigned Ref = VarDefinitions[i].Ref;
 493
 494       dumpVarDefinitionName(i);
 495       llvm::errs() << " = ";
 496       if (Exp) Exp->dump();
 497       else {
 498         dumpVarDefinitionName(Ref);
 499         llvm::errs() << "\n";
 500       }
 501     }
 502   }
 503
 504   /// Dumps an ASCII representation of a Context to llvm::errs()
 505   void dumpContext(Context C) {
 506     for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) {
 507       NamedDecl *D = I.getKey();
 508       D->printName(llvm::errs());
 509       const unsigned *i = C.lookup(D);
 510       llvm::errs() << " -> ";
 511       dumpVarDefinitionName(*i);
 512       llvm::errs() << "\n";
 513     }
 514   }
 515
 516   /// Builds the variable map.
 517   void traverseCFG(CFG *CFGraph, PostOrderCFGView *SortedGraph,
 518                      std::vector<CFGBlockInfo> &BlockInfo);
 519
 520 protected:
 521   // Get the current context index
 522   unsigned getContextIndex() { return SavedContexts.size()-1; }
 523
 524   // Save the current context for later replay
 525   void saveContext(Stmt *S, Context C) {
 526     SavedContexts.push_back(std::make_pair(S,C));
 527   }
 528
 529   // Adds a new definition to the given context, and returns a new context.
 530   // This method should be called when declaring a new variable.
 531   Context addDefinition(NamedDecl *D, Expr *Exp, Context Ctx) {
 532     assert(!Ctx.contains(D));
 533     unsigned newID = VarDefinitions.size();
 534     Context NewCtx = ContextFactory.add(Ctx, D, newID);
 535     VarDefinitions.push_back(VarDefinition(D, Exp, Ctx));
 536     return NewCtx;
 537   }
 538
 539   // Add a new reference to an existing definition.
 540   Context addReference(NamedDecl *D, unsigned i, Context Ctx) {
 541     unsigned newID = VarDefinitions.size();
 542     Context NewCtx = ContextFactory.add(Ctx, D, newID);
 543     VarDefinitions.push_back(VarDefinition(D, i, Ctx));
 544     return NewCtx;
 545   }
 546
 547   // Updates a definition only if that definition is already in the map.
 548   // This method should be called when assigning to an existing variable.
 549   Context updateDefinition(NamedDecl *D, Expr *Exp, Context Ctx) {
 550     if (Ctx.contains(D)) {
 551       unsigned newID = VarDefinitions.size();
 552       Context NewCtx = ContextFactory.remove(Ctx, D);
 553       NewCtx = ContextFactory.add(NewCtx, D, newID);
 554       VarDefinitions.push_back(VarDefinition(D, Exp, Ctx));
 555       return NewCtx;
 556     }
 557     return Ctx;
 558   }
 559
 560   // Removes a definition from the context, but keeps the variable name
 561   // as a valid variable.  The index 0 is a placeholder for cleared definitions.
 562   Context clearDefinition(NamedDecl *D, Context Ctx) {
 563     Context NewCtx = Ctx;
 564     if (NewCtx.contains(D)) {
 565       NewCtx = ContextFactory.remove(NewCtx, D);
 566       NewCtx = ContextFactory.add(NewCtx, D, 0);
 567     }
 568     return NewCtx;
 569   }
 570
 571   // Remove a definition entirely frmo the context.
 572   Context removeDefinition(NamedDecl *D, Context Ctx) {
 573     Context NewCtx = Ctx;
 574     if (NewCtx.contains(D)) {
 575       NewCtx = ContextFactory.remove(NewCtx, D);
 576     }
 577     return NewCtx;
 578   }
 579
 580   Context intersectContexts(Context C1, Context C2);
 581   Context createReferenceContext(Context C);
 582   void intersectBackEdge(Context C1, Context C2);
 583
 584   friend class VarMapBuilder;
 585 };
 586
 587
 588 // This has to be defined after LocalVariableMap.
 589 CFGBlockInfo CFGBlockInfo::getEmptyBlockInfo(Lockset::Factory &F,
 590                                              LocalVariableMap &M) {
 591   return CFGBlockInfo(F.getEmptyMap(), M.getEmptyContext());
 592 }
 593
 594
 595 /// Visitor which builds a LocalVariableMap
 596 class VarMapBuilder : public StmtVisitor<VarMapBuilder> {
 597 public:
 598   LocalVariableMap* VMap;
 599   LocalVariableMap::Context Ctx;
 600
 601   VarMapBuilder(LocalVariableMap *VM, LocalVariableMap::Context C)
 602     : VMap(VM), Ctx(C) {}
 603
 604   void VisitDeclStmt(DeclStmt *S);
 605   void VisitBinaryOperator(BinaryOperator *BO);
 606 };
 607
 608
 609 // Add new local variables to the variable map
 610 void VarMapBuilder::VisitDeclStmt(DeclStmt *S) {
 611   bool modifiedCtx = false;
 612   DeclGroupRef DGrp = S->getDeclGroup();
 613   for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) {
 614     if (VarDecl *VD = dyn_cast_or_null<VarDecl>(*I)) {
 615       Expr *E = VD->getInit();
 616
 617       // Add local variables with trivial type to the variable map
 618       QualType T = VD->getType();
 619       if (T.isTrivialType(VD->getASTContext())) {
 620         Ctx = VMap->addDefinition(VD, E, Ctx);
 621         modifiedCtx = true;
 622       }
 623     }
 624   }
 625   if (modifiedCtx)
 626     VMap->saveContext(S, Ctx);
 627 }
 628
 629 // Update local variable definitions in variable map
 630 void VarMapBuilder::VisitBinaryOperator(BinaryOperator *BO) {
 631   if (!BO->isAssignmentOp())
 632     return;
 633
 634   Expr *LHSExp = BO->getLHS()->IgnoreParenCasts();
 635
 636   // Update the variable map and current context.
 637   if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(LHSExp)) {
 638     ValueDecl *VDec = DRE->getDecl();
 639     if (Ctx.lookup(VDec)) {
 640       if (BO->getOpcode() == BO_Assign)
 641         Ctx = VMap->updateDefinition(VDec, BO->getRHS(), Ctx);
 642       else
 643         // FIXME -- handle compound assignment operators
 644         Ctx = VMap->clearDefinition(VDec, Ctx);
 645       VMap->saveContext(BO, Ctx);
 646     }
 647   }
 648 }
 649
 650
 651 // Computes the intersection of two contexts.  The intersection is the
 652 // set of variables which have the same definition in both contexts;
 653 // variables with different definitions are discarded.
 654 LocalVariableMap::Context
 655 LocalVariableMap::intersectContexts(Context C1, Context C2) {
 656   Context Result = C1;
 657   for (Context::iterator I = C1.begin(), E = C1.end(); I != E; ++I) {
 658     NamedDecl *Dec = I.getKey();
 659     unsigned i1 = I.getData();
 660     const unsigned *i2 = C2.lookup(Dec);
 661     if (!i2)             // variable doesn't exist on second path
 662       Result = removeDefinition(Dec, Result);
 663     else if (*i2 != i1)  // variable exists, but has different definition
 664       Result = clearDefinition(Dec, Result);
 665   }
 666   return Result;
 667 }
 668
 669 // For every variable in C, create a new variable that refers to the
 670 // definition in C.  Return a new context that contains these new variables.
 671 // (We use this for a naive implementation of SSA on loop back-edges.)
 672 LocalVariableMap::Context LocalVariableMap::createReferenceContext(Context C) {
 673   Context Result = getEmptyContext();
 674   for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) {
 675     NamedDecl *Dec = I.getKey();
 676     unsigned i = I.getData();
 677     Result = addReference(Dec, i, Result);
 678   }
 679   return Result;
 680 }
 681
 682 // This routine also takes the intersection of C1 and C2, but it does so by
 683 // altering the VarDefinitions.  C1 must be the result of an earlier call to
 684 // createReferenceContext.
 685 void LocalVariableMap::intersectBackEdge(Context C1, Context C2) {
 686   for (Context::iterator I = C1.begin(), E = C1.end(); I != E; ++I) {
 687     NamedDecl *Dec = I.getKey();
 688     unsigned i1 = I.getData();
 689     VarDefinition *VDef = &VarDefinitions[i1];
 690     assert(VDef->isReference());
 691
 692     const unsigned *i2 = C2.lookup(Dec);
 693     if (!i2 || (*i2 != i1))
 694       VDef->Ref = 0;    // Mark this variable as undefined
 695   }
 696 }
 697
 698
 699 // Traverse the CFG in topological order, so all predecessors of a block
 700 // (excluding back-edges) are visited before the block itself.  At
 701 // each point in the code, we calculate a Context, which holds the set of
 702 // variable definitions which are visible at that point in execution.
 703 // Visible variables are mapped to their definitions using an array that
 704 // contains all definitions.
 705 //
 706 // At join points in the CFG, the set is computed as the intersection of
 707 // the incoming sets along each edge, E.g.
 708 //
 709 //                       { Context                 | VarDefinitions }
 710 //   int x = 0;          { x -> x1                 | x1 = 0 }
 711 //   int y = 0;          { x -> x1, y -> y1        | y1 = 0, x1 = 0 }
 712 //   if (b) x = 1;       { x -> x2, y -> y1        | x2 = 1, y1 = 0, ... }
 713 //   else   x = 2;       { x -> x3, y -> y1        | x3 = 2, x2 = 1, ... }
 714 //   ...                 { y -> y1  (x is unknown) | x3 = 2, x2 = 1, ... }
 715 //
 716 // This is essentially a simpler and more naive version of the standard SSA
 717 // algorithm.  Those definitions that remain in the intersection are from blocks
 718 // that strictly dominate the current block.  We do not bother to insert proper
 719 // phi nodes, because they are not used in our analysis; instead, wherever
 720 // a phi node would be required, we simply remove that definition from the
 721 // context (E.g. x above).
 722 //
 723 // The initial traversal does not capture back-edges, so those need to be
 724 // handled on a separate pass.  Whenever the first pass encounters an
 725 // incoming back edge, it duplicates the context, creating new definitions
 726 // that refer back to the originals.  (These correspond to places where SSA
 727 // might have to insert a phi node.)  On the second pass, these definitions are
 728 // set to NULL if the the variable has changed on the back-edge (i.e. a phi
 729 // node was actually required.)  E.g.
 730 //
 731 //                       { Context           | VarDefinitions }
 732 //   int x = 0, y = 0;   { x -> x1, y -> y1  | y1 = 0, x1 = 0 }
 733 //   while (b)           { x -> x2, y -> y1  | [1st:] x2=x1; [2nd:] x2=NULL; }
 734 //     x = x+1;          { x -> x3, y -> y1  | x3 = x2 + 1, ... }
 735 //   ...                 { y -> y1           | x3 = 2, x2 = 1, ... }
 736 //
 737 void LocalVariableMap::traverseCFG(CFG *CFGraph,
 738                                    PostOrderCFGView *SortedGraph,
 739                                    std::vector<CFGBlockInfo> &BlockInfo) {
 740   PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph);
 741
 742   CtxIndices.resize(CFGraph->getNumBlockIDs());
 743
 744   for (PostOrderCFGView::iterator I = SortedGraph->begin(),
 745        E = SortedGraph->end(); I!= E; ++I) {
 746     const CFGBlock *CurrBlock = *I;
 747     int CurrBlockID = CurrBlock->getBlockID();
 748     CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID];
 749
 750     VisitedBlocks.insert(CurrBlock);
 751
 752     // Calculate the entry context for the current block
 753     bool HasBackEdges = false;
 754     bool CtxInit = true;
 755     for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(),
 756          PE  = CurrBlock->pred_end(); PI != PE; ++PI) {
 757       // if *PI -> CurrBlock is a back edge, so skip it
 758       if (*PI == 0 || !VisitedBlocks.alreadySet(*PI)) {
 759         HasBackEdges = true;
 760         continue;
 761       }
 762
 763       int PrevBlockID = (*PI)->getBlockID();
 764       CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID];
 765
 766       if (CtxInit) {
 767         CurrBlockInfo->EntryContext = PrevBlockInfo->ExitContext;
 768         CtxInit = false;
 769       }
 770       else {
 771         CurrBlockInfo->EntryContext =
 772           intersectContexts(CurrBlockInfo->EntryContext,
 773                             PrevBlockInfo->ExitContext);
 774       }
 775     }
 776
 777     // Duplicate the context if we have back-edges, so we can call
 778     // intersectBackEdges later.
 779     if (HasBackEdges)
 780       CurrBlockInfo->EntryContext =
 781         createReferenceContext(CurrBlockInfo->EntryContext);
 782
 783     // Create a starting context index for the current block
 784     saveContext(0, CurrBlockInfo->EntryContext);
 785     CurrBlockInfo->EntryIndex = getContextIndex();
 786
 787     // Visit all the statements in the basic block.
 788     VarMapBuilder VMapBuilder(this, CurrBlockInfo->EntryContext);
 789     for (CFGBlock::const_iterator BI = CurrBlock->begin(),
 790          BE = CurrBlock->end(); BI != BE; ++BI) {
 791       switch (BI->getKind()) {
 792         case CFGElement::Statement: {
 793           const CFGStmt *CS = cast<CFGStmt>(&*BI);
 794           VMapBuilder.Visit(const_cast<Stmt*>(CS->getStmt()));
 795           break;
 796         }
 797         default:
 798           break;
 799       }
 800     }
 801     CurrBlockInfo->ExitContext = VMapBuilder.Ctx;
 802
 803     // Mark variables on back edges as "unknown" if they've been changed.
 804     for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
 805          SE  = CurrBlock->succ_end(); SI != SE; ++SI) {
 806       // if CurrBlock -> *SI is *not* a back edge
 807       if (*SI == 0 || !VisitedBlocks.alreadySet(*SI))
 808         continue;
 809
 810       CFGBlock *FirstLoopBlock = *SI;
 811       Context LoopBegin = BlockInfo[FirstLoopBlock->getBlockID()].EntryContext;
 812       Context LoopEnd   = CurrBlockInfo->ExitContext;
 813       intersectBackEdge(LoopBegin, LoopEnd);
 814     }
 815   }
 816
 817   // Put an extra entry at the end of the indexed context array
 818   unsigned exitID = CFGraph->getExit().getBlockID();
 819   saveContext(0, BlockInfo[exitID].ExitContext);
 820 }
 821
 822 /// Find the appropriate source locations to use when producing diagnostics for
 823 /// each block in the CFG.
 824 static void findBlockLocations(CFG *CFGraph,
 825                                PostOrderCFGView *SortedGraph,
 826                                std::vector<CFGBlockInfo> &BlockInfo) {
 827   for (PostOrderCFGView::iterator I = SortedGraph->begin(),
 828        E = SortedGraph->end(); I!= E; ++I) {
 829     const CFGBlock *CurrBlock = *I;
 830     CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlock->getBlockID()];
 831
 832     // Find the source location of the last statement in the block, if the
 833     // block is not empty.
 834     if (const Stmt *S = CurrBlock->getTerminator()) {
 835       CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = S->getLocStart();
 836     } else {
 837       for (CFGBlock::const_reverse_iterator BI = CurrBlock->rbegin(),
 838            BE = CurrBlock->rend(); BI != BE; ++BI) {
 839         // FIXME: Handle other CFGElement kinds.
 840         if (const CFGStmt *CS = dyn_cast<CFGStmt>(&*BI)) {
 841           CurrBlockInfo->ExitLoc = CS->getStmt()->getLocStart();
 842           break;
 843         }
 844       }
 845     }
 846
 847     if (!CurrBlockInfo->ExitLoc.isInvalid()) {
 848       // This block contains at least one statement. Find the source location
 849       // of the first statement in the block.
 850       for (CFGBlock::const_iterator BI = CurrBlock->begin(),
 851            BE = CurrBlock->end(); BI != BE; ++BI) {
 852         // FIXME: Handle other CFGElement kinds.
 853         if (const CFGStmt *CS = dyn_cast<CFGStmt>(&*BI)) {
 854           CurrBlockInfo->EntryLoc = CS->getStmt()->getLocStart();
 855           break;
 856         }
 857       }
 858     } else if (CurrBlock->pred_size() == 1 && *CurrBlock->pred_begin() &&
 859                CurrBlock != &CFGraph->getExit()) {
 860       // The block is empty, and has a single predecessor. Use its exit
 861       // location.
 862       CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc =
 863           BlockInfo[(*CurrBlock->pred_begin())->getBlockID()].ExitLoc;
 864     }
 865   }
 866 }
 867
 868 /// \brief Class which implements the core thread safety analysis routines.
 869 class ThreadSafetyAnalyzer {
 870   friend class BuildLockset;
 871
 872   ThreadSafetyHandler &Handler;
 873   Lockset::Factory    LocksetFactory;
 874   LocalVariableMap    LocalVarMap;
 875
 876 public:
 877   ThreadSafetyAnalyzer(ThreadSafetyHandler &H) : Handler(H) {}
 878
 879   Lockset intersectAndWarn(const CFGBlockInfo &Block1, CFGBlockSide Side1,
 880                            const CFGBlockInfo &Block2, CFGBlockSide Side2,
 881                            LockErrorKind LEK);
 882
 883   Lockset addLock(Lockset &LSet, Expr *MutexExp, const NamedDecl *D,
 884                   LockKind LK, SourceLocation Loc);
 885
 886   void runAnalysis(AnalysisDeclContext &AC);
 887 };
 888
 889
 890 /// \brief We use this class to visit different types of expressions in
 891 /// CFGBlocks, and build up the lockset.
 892 /// An expression may cause us to add or remove locks from the lockset, or else
 893 /// output error messages related to missing locks.
 894 /// FIXME: In future, we may be able to not inherit from a visitor.
 895 class BuildLockset : public StmtVisitor<BuildLockset> {
 896   friend class ThreadSafetyAnalyzer;
 897
 898   ThreadSafetyHandler &Handler;
 899   Lockset::Factory &LocksetFactory;
 900   LocalVariableMap &LocalVarMap;
 901
 902   Lockset LSet;
 903   LocalVariableMap::Context LVarCtx;
 904   unsigned CtxIndex;
 905
 906   // Helper functions
 907   void addLock(const MutexID &Mutex, const LockData &LDat);
 908   void removeLock(const MutexID &Mutex, SourceLocation UnlockLoc);
 909
 910   template <class AttrType>
 911   void addLocksToSet(LockKind LK, AttrType *Attr,
 912                      Expr *Exp, NamedDecl *D, VarDecl *VD = 0);
 913   void removeLocksFromSet(UnlockFunctionAttr *Attr,
 914                           Expr *Exp, NamedDecl* FunDecl);
 915
 916   const ValueDecl *getValueDecl(Expr *Exp);
 917   void warnIfMutexNotHeld (const NamedDecl *D, Expr *Exp, AccessKind AK,
 918                            Expr *MutexExp, ProtectedOperationKind POK);
 919   void checkAccess(Expr *Exp, AccessKind AK);
 920   void checkDereference(Expr *Exp, AccessKind AK);
 921   void handleCall(Expr *Exp, NamedDecl *D, VarDecl *VD = 0);
 922
 923   template <class AttrType>
 924   void addTrylock(LockKind LK, AttrType *Attr, Expr *Exp, NamedDecl *FunDecl,
 925                   const CFGBlock* PredBlock, const CFGBlock *CurrBlock,
 926                   Expr *BrE, bool Neg);
 927   CallExpr* getTrylockCallExpr(Stmt *Cond, LocalVariableMap::Context C,
 928                                bool &Negate);
 929   void handleTrylock(Stmt *Cond, const CFGBlock* PredBlock,
 930                      const CFGBlock *CurrBlock);
 931
 932   /// \brief Returns true if the lockset contains a lock, regardless of whether
 933   /// the lock is held exclusively or shared.
 934   bool locksetContains(const MutexID &Lock) const {
 935     return LSet.lookup(Lock);
 936   }
 937
 938   /// \brief Returns true if the lockset contains a lock with the passed in
 939   /// locktype.
 940   bool locksetContains(const MutexID &Lock, LockKind KindRequested) const {
 941     const LockData *LockHeld = LSet.lookup(Lock);
 942     return (LockHeld && KindRequested == LockHeld->LKind);
 943   }
 944
 945   /// \brief Returns true if the lockset contains a lock with at least the
 946   /// passed in locktype. So for example, if we pass in LK_Shared, this function
 947   /// returns true if the lock is held LK_Shared or LK_Exclusive. If we pass in
 948   /// LK_Exclusive, this function returns true if the lock is held LK_Exclusive.
 949   bool locksetContainsAtLeast(const MutexID &Lock,
 950                               LockKind KindRequested) const {
 951     switch (KindRequested) {
 952       case LK_Shared:
 953         return locksetContains(Lock);
 954       case LK_Exclusive:
 955         return locksetContains(Lock, KindRequested);
 956     }
 957     llvm_unreachable("Unknown LockKind");
 958   }
 959
 960 public:
 961   BuildLockset(ThreadSafetyAnalyzer *analyzer, CFGBlockInfo &Info)
 962     : StmtVisitor<BuildLockset>(),
 963       Handler(analyzer->Handler),
 964       LocksetFactory(analyzer->LocksetFactory),
 965       LocalVarMap(analyzer->LocalVarMap),
 966       LSet(Info.EntrySet),
 967       LVarCtx(Info.EntryContext),
 968       CtxIndex(Info.EntryIndex)
 969   {}
 970
 971   void VisitUnaryOperator(UnaryOperator *UO);
 972   void VisitBinaryOperator(BinaryOperator *BO);
 973   void VisitCastExpr(CastExpr *CE);
 974   void VisitCallExpr(CallExpr *Exp);
 975   void VisitCXXConstructExpr(CXXConstructExpr *Exp);
 976   void VisitDeclStmt(DeclStmt *S);
 977 };
 978
 979 /// \brief Add a new lock to the lockset, warning if the lock is already there.
 980 /// \param Mutex -- the Mutex expression for the lock
 981 /// \param LDat  -- the LockData for the lock
 982 void BuildLockset::addLock(const MutexID &Mutex, const LockData& LDat) {
 983   // FIXME: deal with acquired before/after annotations.
 984   // FIXME: Don't always warn when we have support for reentrant locks.
 985   if (locksetContains(Mutex))
 986     Handler.handleDoubleLock(Mutex.getName(), LDat.AcquireLoc);
 987   else
 988     LSet = LocksetFactory.add(LSet, Mutex, LDat);
 989 }
 990
 991 /// \brief Remove a lock from the lockset, warning if the lock is not there.
 992 /// \param LockExp The lock expression corresponding to the lock to be removed
 993 /// \param UnlockLoc The source location of the unlock (only used in error msg)
 994 void BuildLockset::removeLock(const MutexID &Mutex, SourceLocation UnlockLoc) {
 995   const LockData *LDat = LSet.lookup(Mutex);
 996   if (!LDat)
 997     Handler.handleUnmatchedUnlock(Mutex.getName(), UnlockLoc);
 998   else {
 999     // For scoped-lockable vars, remove the mutex associated with this var.
1000     if (LDat->UnderlyingMutex.isValid())
1001       removeLock(LDat->UnderlyingMutex, UnlockLoc);
1002     LSet = LocksetFactory.remove(LSet, Mutex);
1003   }
1004 }
1005
1006 /// \brief This function, parameterized by an attribute type, is used to add a
1007 /// set of locks specified as attribute arguments to the lockset.
1008 template <typename AttrType>
1009 void BuildLockset::addLocksToSet(LockKind LK, AttrType *Attr,
1010                                  Expr *Exp, NamedDecl* FunDecl, VarDecl *VD) {
1011   typedef typename AttrType::args_iterator iterator_type;
1012
1013   SourceLocation ExpLocation = Exp->getExprLoc();
1014
1015   // Figure out if we're calling the constructor of scoped lockable class
1016   bool isScopedVar = false;
1017   if (VD) {
1018     if (CXXConstructorDecl *CD = dyn_cast<CXXConstructorDecl>(FunDecl)) {
1019       CXXRecordDecl* PD = CD->getParent();
1020       if (PD && PD->getAttr<ScopedLockableAttr>())
1021         isScopedVar = true;
1022     }
1023   }
1024
1025   if (Attr->args_size() == 0) {
1026     // The mutex held is the "this" object.
1027     MutexID Mutex(0, Exp, FunDecl);
1028     if (!Mutex.isValid())
1029       MutexID::warnInvalidLock(Handler, 0, Exp, FunDecl);
1030     else
1031       addLock(Mutex, LockData(ExpLocation, LK));
1032     return;
1033   }
1034
1035   for (iterator_type I=Attr->args_begin(), E=Attr->args_end(); I != E; ++I) {
1036     MutexID Mutex(*I, Exp, FunDecl);
1037     if (!Mutex.isValid())
1038       MutexID::warnInvalidLock(Handler, *I, Exp, FunDecl);
1039     else {
1040       addLock(Mutex, LockData(ExpLocation, LK));
1041       if (isScopedVar) {
1042         // For scoped lockable vars, map this var to its underlying mutex.
1043         DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, VD->getLocation());
1044         MutexID SMutex(&DRE, 0, 0);
1045         addLock(SMutex, LockData(VD->getLocation(), LK, Mutex));
1046       }
1047     }
1048   }
1049 }
1050
1051 /// \brief This function removes a set of locks specified as attribute
1052 /// arguments from the lockset.
1053 void BuildLockset::removeLocksFromSet(UnlockFunctionAttr *Attr,
1054                                       Expr *Exp, NamedDecl* FunDecl) {
1055   SourceLocation ExpLocation;
1056   if (Exp) ExpLocation = Exp->getExprLoc();
1057
1058   if (Attr->args_size() == 0) {
1059     // The mutex held is the "this" object.
1060     MutexID Mu(0, Exp, FunDecl);
1061     if (!Mu.isValid())
1062       MutexID::warnInvalidLock(Handler, 0, Exp, FunDecl);
1063     else
1064       removeLock(Mu, ExpLocation);
1065     return;
1066   }
1067
1068   for (UnlockFunctionAttr::args_iterator I = Attr->args_begin(),
1069        E = Attr->args_end(); I != E; ++I) {
1070     MutexID Mutex(*I, Exp, FunDecl);
1071     if (!Mutex.isValid())
1072       MutexID::warnInvalidLock(Handler, *I, Exp, FunDecl);
1073     else
1074       removeLock(Mutex, ExpLocation);
1075   }
1076 }
1077
1078 /// \brief Gets the value decl pointer from DeclRefExprs or MemberExprs
1079 const ValueDecl *BuildLockset::getValueDecl(Expr *Exp) {
1080   if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Exp))
1081     return DR->getDecl();
1082
1083   if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp))
1084     return ME->getMemberDecl();
1085
1086   return 0;
1087 }
1088
1089 /// \brief Warn if the LSet does not contain a lock sufficient to protect access
1090 /// of at least the passed in AccessKind.
1091 void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, Expr *Exp,
1092                                       AccessKind AK, Expr *MutexExp,
1093                                       ProtectedOperationKind POK) {
1094   LockKind LK = getLockKindFromAccessKind(AK);
1095
1096   MutexID Mutex(MutexExp, Exp, D);
1097   if (!Mutex.isValid())
1098     MutexID::warnInvalidLock(Handler, MutexExp, Exp, D);
1099   else if (!locksetContainsAtLeast(Mutex, LK))
1100     Handler.handleMutexNotHeld(D, POK, Mutex.getName(), LK, Exp->getExprLoc());
1101 }
1102
1103 /// \brief This method identifies variable dereferences and checks pt_guarded_by
1104 /// and pt_guarded_var annotations. Note that we only check these annotations
1105 /// at the time a pointer is dereferenced.
1106 /// FIXME: We need to check for other types of pointer dereferences
1107 /// (e.g. [], ->) and deal with them here.
1108 /// \param Exp An expression that has been read or written.
1109 void BuildLockset::checkDereference(Expr *Exp, AccessKind AK) {
1110   UnaryOperator *UO = dyn_cast<UnaryOperator>(Exp);
1111   if (!UO || UO->getOpcode() != clang::UO_Deref)
1112     return;
1113   Exp = UO->getSubExpr()->IgnoreParenCasts();
1114
1115   const ValueDecl *D = getValueDecl(Exp);
1116   if(!D || !D->hasAttrs())
1117     return;
1118
1119   if (D->getAttr<PtGuardedVarAttr>() && LSet.isEmpty())
1120     Handler.handleNoMutexHeld(D, POK_VarDereference, AK, Exp->getExprLoc());
1121
1122   const AttrVec &ArgAttrs = D->getAttrs();
1123   for(unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i)
1124     if (PtGuardedByAttr *PGBAttr = dyn_cast<PtGuardedByAttr>(ArgAttrs[i]))
1125       warnIfMutexNotHeld(D, Exp, AK, PGBAttr->getArg(), POK_VarDereference);
1126 }
1127
1128 /// \brief Checks guarded_by and guarded_var attributes.
1129 /// Whenever we identify an access (read or write) of a DeclRefExpr or
1130 /// MemberExpr, we need to check whether there are any guarded_by or
1131 /// guarded_var attributes, and make sure we hold the appropriate mutexes.
1132 void BuildLockset::checkAccess(Expr *Exp, AccessKind AK) {
1133   const ValueDecl *D = getValueDecl(Exp);
1134   if(!D || !D->hasAttrs())
1135     return;
1136
1137   if (D->getAttr<GuardedVarAttr>() && LSet.isEmpty())
1138     Handler.handleNoMutexHeld(D, POK_VarAccess, AK, Exp->getExprLoc());
1139
1140   const AttrVec &ArgAttrs = D->getAttrs();
1141   for(unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i)
1142     if (GuardedByAttr *GBAttr = dyn_cast<GuardedByAttr>(ArgAttrs[i]))
1143       warnIfMutexNotHeld(D, Exp, AK, GBAttr->getArg(), POK_VarAccess);
1144 }
1145
1146 /// \brief Process a function call, method call, constructor call,
1147 /// or destructor call.  This involves looking at the attributes on the
1148 /// corresponding function/method/constructor/destructor, issuing warnings,
1149 /// and updating the locksets accordingly.
1150 ///
1151 /// FIXME: For classes annotated with one of the guarded annotations, we need
1152 /// to treat const method calls as reads and non-const method calls as writes,
1153 /// and check that the appropriate locks are held. Non-const method calls with
1154 /// the same signature as const method calls can be also treated as reads.
1155 ///
1156 /// FIXME: We need to also visit CallExprs to catch/check global functions.
1157 ///
1158 /// FIXME: Do not flag an error for member variables accessed in constructors/
1159 /// destructors
1160 void BuildLockset::handleCall(Expr *Exp, NamedDecl *D, VarDecl *VD) {
1161   AttrVec &ArgAttrs = D->getAttrs();
1162   for(unsigned i = 0; i < ArgAttrs.size(); ++i) {
1163     Attr *Attr = ArgAttrs[i];
1164     switch (Attr->getKind()) {
1165       // When we encounter an exclusive lock function, we need to add the lock
1166       // to our lockset with kind exclusive.
1167       case attr::ExclusiveLockFunction: {
1168         ExclusiveLockFunctionAttr *A = cast<ExclusiveLockFunctionAttr>(Attr);
1169         addLocksToSet(LK_Exclusive, A, Exp, D, VD);
1170         break;
1171       }
1172
1173       // When we encounter a shared lock function, we need to add the lock
1174       // to our lockset with kind shared.
1175       case attr::SharedLockFunction: {
1176         SharedLockFunctionAttr *A = cast<SharedLockFunctionAttr>(Attr);
1177         addLocksToSet(LK_Shared, A, Exp, D, VD);
1178         break;
1179       }
1180
1181       // When we encounter an unlock function, we need to remove unlocked
1182       // mutexes from the lockset, and flag a warning if they are not there.
1183       case attr::UnlockFunction: {
1184         UnlockFunctionAttr *UFAttr = cast<UnlockFunctionAttr>(Attr);
1185         removeLocksFromSet(UFAttr, Exp, D);
1186         break;
1187       }
1188
1189       case attr::ExclusiveLocksRequired: {
1190         ExclusiveLocksRequiredAttr *ELRAttr =
1191             cast<ExclusiveLocksRequiredAttr>(Attr);
1192
1193         for (ExclusiveLocksRequiredAttr::args_iterator
1194              I = ELRAttr->args_begin(), E = ELRAttr->args_end(); I != E; ++I)
1195           warnIfMutexNotHeld(D, Exp, AK_Written, *I, POK_FunctionCall);
1196         break;
1197       }
1198
1199       case attr::SharedLocksRequired: {
1200         SharedLocksRequiredAttr *SLRAttr = cast<SharedLocksRequiredAttr>(Attr);
1201
1202         for (SharedLocksRequiredAttr::args_iterator I = SLRAttr->args_begin(),
1203              E = SLRAttr->args_end(); I != E; ++I)
1204           warnIfMutexNotHeld(D, Exp, AK_Read, *I, POK_FunctionCall);
1205         break;
1206       }
1207
1208       case attr::LocksExcluded: {
1209         LocksExcludedAttr *LEAttr = cast<LocksExcludedAttr>(Attr);
1210         for (LocksExcludedAttr::args_iterator I = LEAttr->args_begin(),
1211             E = LEAttr->args_end(); I != E; ++I) {
1212           MutexID Mutex(*I, Exp, D);
1213           if (!Mutex.isValid())
1214             MutexID::warnInvalidLock(Handler, *I, Exp, D);
1215           else if (locksetContains(Mutex))
1216             Handler.handleFunExcludesLock(D->getName(), Mutex.getName(),
1217                                           Exp->getExprLoc());
1218         }
1219         break;
1220       }
1221
1222       // Ignore other (non thread-safety) attributes
1223       default:
1224         break;
1225     }
1226   }
1227 }
1228
1229
1230 /// \brief Add lock to set, if the current block is in the taken branch of a
1231 /// trylock.
1232 template <class AttrType>
1233 void BuildLockset::addTrylock(LockKind LK, AttrType *Attr, Expr *Exp,
1234                               NamedDecl *FunDecl, const CFGBlock *PredBlock,
1235                               const CFGBlock *CurrBlock, Expr *BrE, bool Neg) {
1236   // Find out which branch has the lock
1237   bool branch = 0;
1238   if (CXXBoolLiteralExpr *BLE = dyn_cast_or_null<CXXBoolLiteralExpr>(BrE)) {
1239     branch = BLE->getValue();
1240   }
1241   else if (IntegerLiteral *ILE = dyn_cast_or_null<IntegerLiteral>(BrE)) {
1242     branch = ILE->getValue().getBoolValue();
1243   }
1244   int branchnum = branch ? 0 : 1;
1245   if (Neg) branchnum = !branchnum;
1246
1247   // If we've taken the trylock branch, then add the lock
1248   int i = 0;
1249   for (CFGBlock::const_succ_iterator SI = PredBlock->succ_begin(),
1250        SE = PredBlock->succ_end(); SI != SE && i < 2; ++SI, ++i) {
1251     if (*SI == CurrBlock && i == branchnum) {
1252       addLocksToSet(LK, Attr, Exp, FunDecl, 0);
1253     }
1254   }
1255 }
1256
1257
1258 // If Cond can be traced back to a function call, return the call expression.
1259 // The negate variable should be called with false, and will be set to true
1260 // if the function call is negated, e.g. if (!mu.tryLock(...))
1261 CallExpr* BuildLockset::getTrylockCallExpr(Stmt *Cond,
1262                                LocalVariableMap::Context C,
1263                                bool &Negate) {
1264   if (!Cond)
1265     return 0;
1266
1267   if (CallExpr *CallExp = dyn_cast<CallExpr>(Cond)) {
1268     return CallExp;
1269   }
1270   else if (ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(Cond)) {
1271     return getTrylockCallExpr(CE->getSubExpr(), C, Negate);
1272   }
1273   else if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Cond)) {
1274     Expr *E = LocalVarMap.lookupExpr(DRE->getDecl(), C);
1275     return getTrylockCallExpr(E, C, Negate);
1276   }
1277   else if (UnaryOperator *UOP = dyn_cast<UnaryOperator>(Cond)) {
1278     if (UOP->getOpcode() == UO_LNot) {
1279       Negate = !Negate;
1280       return getTrylockCallExpr(UOP->getSubExpr(), C, Negate);
1281     }
1282   }
1283   // FIXME -- handle && and || as well.
1284   return NULL;
1285 }
1286
1287
1288 /// \brief Process a conditional branch from a previous block to the current
1289 /// block, looking for trylock calls.
1290 void BuildLockset::handleTrylock(Stmt *Cond, const CFGBlock *PredBlock,
1291                                  const CFGBlock *CurrBlock) {
1292   bool Negate = false;
1293   CallExpr *Exp = getTrylockCallExpr(Cond, LVarCtx, Negate);
1294   if (!Exp)
1295     return;
1296
1297   NamedDecl *FunDecl = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl());
1298   if(!FunDecl || !FunDecl->hasAttrs())
1299     return;
1300
1301   // If the condition is a call to a Trylock function, then grab the attributes
1302   AttrVec &ArgAttrs = FunDecl->getAttrs();
1303   for (unsigned i = 0; i < ArgAttrs.size(); ++i) {
1304     Attr *Attr = ArgAttrs[i];
1305     switch (Attr->getKind()) {
1306       case attr::ExclusiveTrylockFunction: {
1307         ExclusiveTrylockFunctionAttr *A =
1308           cast<ExclusiveTrylockFunctionAttr>(Attr);
1309         addTrylock(LK_Exclusive, A, Exp, FunDecl, PredBlock, CurrBlock,
1310                    A->getSuccessValue(), Negate);
1311         break;
1312       }
1313       case attr::SharedTrylockFunction: {
1314         SharedTrylockFunctionAttr *A =
1315           cast<SharedTrylockFunctionAttr>(Attr);
1316         addTrylock(LK_Shared, A, Exp, FunDecl, PredBlock, CurrBlock,
1317                    A->getSuccessValue(), Negate);
1318         break;
1319       }
1320       default:
1321         break;
1322     }
1323   }
1324 }
1325
1326
1327 /// \brief For unary operations which read and write a variable, we need to
1328 /// check whether we hold any required mutexes. Reads are checked in
1329 /// VisitCastExpr.
1330 void BuildLockset::VisitUnaryOperator(UnaryOperator *UO) {
1331   switch (UO->getOpcode()) {
1332     case clang::UO_PostDec:
1333     case clang::UO_PostInc:
1334     case clang::UO_PreDec:
1335     case clang::UO_PreInc: {
1336       Expr *SubExp = UO->getSubExpr()->IgnoreParenCasts();
1337       checkAccess(SubExp, AK_Written);
1338       checkDereference(SubExp, AK_Written);
1339       break;
1340     }
1341     default:
1342       break;
1343   }
1344 }
1345
1346 /// For binary operations which assign to a variable (writes), we need to check
1347 /// whether we hold any required mutexes.
1348 /// FIXME: Deal with non-primitive types.
1349 void BuildLockset::VisitBinaryOperator(BinaryOperator *BO) {
1350   if (!BO->isAssignmentOp())
1351     return;
1352
1353   // adjust the context
1354   LVarCtx = LocalVarMap.getNextContext(CtxIndex, BO, LVarCtx);
1355
1356   Expr *LHSExp = BO->getLHS()->IgnoreParenCasts();
1357   checkAccess(LHSExp, AK_Written);
1358   checkDereference(LHSExp, AK_Written);
1359 }
1360
1361 /// Whenever we do an LValue to Rvalue cast, we are reading a variable and
1362 /// need to ensure we hold any required mutexes.
1363 /// FIXME: Deal with non-primitive types.
1364 void BuildLockset::VisitCastExpr(CastExpr *CE) {
1365   if (CE->getCastKind() != CK_LValueToRValue)
1366     return;
1367   Expr *SubExp = CE->getSubExpr()->IgnoreParenCasts();
1368   checkAccess(SubExp, AK_Read);
1369   checkDereference(SubExp, AK_Read);
1370 }
1371
1372
1373 void BuildLockset::VisitCallExpr(CallExpr *Exp) {
1374   NamedDecl *D = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl());
1375   if(!D || !D->hasAttrs())
1376     return;
1377   handleCall(Exp, D);
1378 }
1379
1380 void BuildLockset::VisitCXXConstructExpr(CXXConstructExpr *Exp) {
1381   // FIXME -- only handles constructors in DeclStmt below.
1382 }
1383
1384 void BuildLockset::VisitDeclStmt(DeclStmt *S) {
1385   // adjust the context
1386   LVarCtx = LocalVarMap.getNextContext(CtxIndex, S, LVarCtx);
1387
1388   DeclGroupRef DGrp = S->getDeclGroup();
1389   for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) {
1390     Decl *D = *I;
1391     if (VarDecl *VD = dyn_cast_or_null<VarDecl>(D)) {
1392       Expr *E = VD->getInit();
1393       if (CXXConstructExpr *CE = dyn_cast_or_null<CXXConstructExpr>(E)) {
1394         NamedDecl *CtorD = dyn_cast_or_null<NamedDecl>(CE->getConstructor());
1395         if (!CtorD || !CtorD->hasAttrs())
1396           return;
1397         handleCall(CE, CtorD, VD);
1398       }
1399     }
1400   }
1401 }
1402
1403
1404 /// \brief Compute the intersection of two locksets and issue warnings for any
1405 /// locks in the symmetric difference.
1406 ///
1407 /// This function is used at a merge point in the CFG when comparing the lockset
1408 /// of each branch being merged. For example, given the following sequence:
1409 /// A; if () then B; else C; D; we need to check that the lockset after B and C
1410 /// are the same. In the event of a difference, we use the intersection of these
1411 /// two locksets at the start of D.
1412 Lockset ThreadSafetyAnalyzer::intersectAndWarn(const CFGBlockInfo &Block1,
1413                                                CFGBlockSide Side1,
1414                                                const CFGBlockInfo &Block2,
1415                                                CFGBlockSide Side2,
1416                                                LockErrorKind LEK) {
1417   Lockset LSet1 = Block1.getSet(Side1);
1418   Lockset LSet2 = Block2.getSet(Side2);
1419
1420   Lockset Intersection = LSet1;
1421   for (Lockset::iterator I = LSet2.begin(), E = LSet2.end(); I != E; ++I) {
1422     const MutexID &LSet2Mutex = I.getKey();
1423     const LockData &LSet2LockData = I.getData();
1424     if (const LockData *LD = LSet1.lookup(LSet2Mutex)) {
1425       if (LD->LKind != LSet2LockData.LKind) {
1426         Handler.handleExclusiveAndShared(LSet2Mutex.getName(),
1427                                          LSet2LockData.AcquireLoc,
1428                                          LD->AcquireLoc);
1429         if (LD->LKind != LK_Exclusive)
1430           Intersection = LocksetFactory.add(Intersection, LSet2Mutex,
1431                                             LSet2LockData);
1432       }
1433     } else {
1434       Handler.handleMutexHeldEndOfScope(LSet2Mutex.getName(),
1435                                         LSet2LockData.AcquireLoc,
1436                                         Block1.getLocation(Side1), LEK);
1437     }
1438   }
1439
1440   for (Lockset::iterator I = LSet1.begin(), E = LSet1.end(); I != E; ++I) {
1441     if (!LSet2.contains(I.getKey())) {
1442       const MutexID &Mutex = I.getKey();
1443       const LockData &MissingLock = I.getData();
1444       Handler.handleMutexHeldEndOfScope(Mutex.getName(),
1445                                         MissingLock.AcquireLoc,
1446                                         Block2.getLocation(Side2), LEK);
1447       Intersection = LocksetFactory.remove(Intersection, Mutex);
1448     }
1449   }
1450   return Intersection;
1451 }
1452
1453 Lockset ThreadSafetyAnalyzer::addLock(Lockset &LSet, Expr *MutexExp,
1454                                       const NamedDecl *D,
1455                                       LockKind LK, SourceLocation Loc) {
1456   MutexID Mutex(MutexExp, 0, D);
1457   if (!Mutex.isValid()) {
1458     MutexID::warnInvalidLock(Handler, MutexExp, 0, D);
1459     return LSet;
1460   }
1461   LockData NewLock(Loc, LK);
1462   return LocksetFactory.add(LSet, Mutex, NewLock);
1463 }
1464
1465 /// \brief Check a function's CFG for thread-safety violations.
1466 ///
1467 /// We traverse the blocks in the CFG, compute the set of mutexes that are held
1468 /// at the end of each block, and issue warnings for thread safety violations.
1469 /// Each block in the CFG is traversed exactly once.
1470 void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) {
1471   CFG *CFGraph = AC.getCFG();
1472   if (!CFGraph) return;
1473   const NamedDecl *D = dyn_cast_or_null<NamedDecl>(AC.getDecl());
1474
1475   if (!D)
1476     return;  // Ignore anonymous functions for now.
1477   if (D->getAttr<NoThreadSafetyAnalysisAttr>())
1478     return;
1479   // FIXME: Do something a bit more intelligent inside constructor and
1480   // destructor code.  Constructors and destructors must assume unique access
1481   // to 'this', so checks on member variable access is disabled, but we should
1482   // still enable checks on other objects.
1483   if (isa<CXXConstructorDecl>(D))
1484     return;  // Don't check inside constructors.
1485   if (isa<CXXDestructorDecl>(D))
1486     return;  // Don't check inside destructors.
1487
1488   std::vector<CFGBlockInfo> BlockInfo(CFGraph->getNumBlockIDs(),
1489     CFGBlockInfo::getEmptyBlockInfo(LocksetFactory, LocalVarMap));
1490
1491   // We need to explore the CFG via a "topological" ordering.
1492   // That way, we will be guaranteed to have information about required
1493   // predecessor locksets when exploring a new block.
1494   PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>();
1495   PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph);
1496
1497   // Compute SSA names for local variables
1498   LocalVarMap.traverseCFG(CFGraph, SortedGraph, BlockInfo);
1499
1500   // Fill in source locations for all CFGBlocks.
1501   findBlockLocations(CFGraph, SortedGraph, BlockInfo);
1502
1503   // Add locks from exclusive_locks_required and shared_locks_required
1504   // to initial lockset. Also turn off checking for lock and unlock functions.
1505   // FIXME: is there a more intelligent way to check lock/unlock functions?
1506   if (!SortedGraph->empty() && D->hasAttrs()) {
1507     const CFGBlock *FirstBlock = *SortedGraph->begin();
1508     Lockset &InitialLockset = BlockInfo[FirstBlock->getBlockID()].EntrySet;
1509     const AttrVec &ArgAttrs = D->getAttrs();
1510     for (unsigned i = 0; i < ArgAttrs.size(); ++i) {
1511       Attr *Attr = ArgAttrs[i];
1512       SourceLocation AttrLoc = Attr->getLocation();
1513       if (SharedLocksRequiredAttr *SLRAttr
1514             = dyn_cast<SharedLocksRequiredAttr>(Attr)) {
1515         for (SharedLocksRequiredAttr::args_iterator
1516              SLRIter = SLRAttr->args_begin(),
1517              SLREnd = SLRAttr->args_end(); SLRIter != SLREnd; ++SLRIter)
1518           InitialLockset = addLock(InitialLockset,
1519                                    *SLRIter, D, LK_Shared,
1520                                    AttrLoc);
1521       } else if (ExclusiveLocksRequiredAttr *ELRAttr
1522                    = dyn_cast<ExclusiveLocksRequiredAttr>(Attr)) {
1523         for (ExclusiveLocksRequiredAttr::args_iterator
1524              ELRIter = ELRAttr->args_begin(),
1525              ELREnd = ELRAttr->args_end(); ELRIter != ELREnd; ++ELRIter)
1526           InitialLockset = addLock(InitialLockset,
1527                                    *ELRIter, D, LK_Exclusive,
1528                                    AttrLoc);
1529       } else if (isa<UnlockFunctionAttr>(Attr)) {
1530         // Don't try to check unlock functions for now
1531         return;
1532       } else if (isa<ExclusiveLockFunctionAttr>(Attr)) {
1533         // Don't try to check lock functions for now
1534         return;
1535       } else if (isa<SharedLockFunctionAttr>(Attr)) {
1536         // Don't try to check lock functions for now
1537         return;
1538       }
1539     }
1540   }
1541
1542   for (PostOrderCFGView::iterator I = SortedGraph->begin(),
1543        E = SortedGraph->end(); I!= E; ++I) {
1544     const CFGBlock *CurrBlock = *I;
1545     int CurrBlockID = CurrBlock->getBlockID();
1546     CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID];
1547
1548     // Use the default initial lockset in case there are no predecessors.
1549     VisitedBlocks.insert(CurrBlock);
1550
1551     // Iterate through the predecessor blocks and warn if the lockset for all
1552     // predecessors is not the same. We take the entry lockset of the current
1553     // block to be the intersection of all previous locksets.
1554     // FIXME: By keeping the intersection, we may output more errors in future
1555     // for a lock which is not in the intersection, but was in the union. We
1556     // may want to also keep the union in future. As an example, let's say
1557     // the intersection contains Mutex L, and the union contains L and M.
1558     // Later we unlock M. At this point, we would output an error because we
1559     // never locked M; although the real error is probably that we forgot to
1560     // lock M on all code paths. Conversely, let's say that later we lock M.
1561     // In this case, we should compare against the intersection instead of the
1562     // union because the real error is probably that we forgot to unlock M on
1563     // all code paths.
1564     bool LocksetInitialized = false;
1565     llvm::SmallVector<CFGBlock*, 8> SpecialBlocks;
1566     for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(),
1567          PE  = CurrBlock->pred_end(); PI != PE; ++PI) {
1568
1569       // if *PI -> CurrBlock is a back edge
1570       if (*PI == 0 || !VisitedBlocks.alreadySet(*PI))
1571         continue;
1572
1573       // Ignore edges from blocks that can't return.
1574       if ((*PI)->hasNoReturnElement())
1575         continue;
1576
1577       // If the previous block ended in a 'continue' or 'break' statement, then
1578       // a difference in locksets is probably due to a bug in that block, rather
1579       // than in some other predecessor. In that case, keep the other
1580       // predecessor's lockset.
1581       if (const Stmt *Terminator = (*PI)->getTerminator()) {
1582         if (isa<ContinueStmt>(Terminator) || isa<BreakStmt>(Terminator)) {
1583           SpecialBlocks.push_back(*PI);
1584           continue;
1585         }
1586       }
1587
1588       int PrevBlockID = (*PI)->getBlockID();
1589       CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID];
1590
1591       if (!LocksetInitialized) {
1592         CurrBlockInfo->EntrySet = PrevBlockInfo->ExitSet;
1593         LocksetInitialized = true;
1594       } else {
1595         CurrBlockInfo->EntrySet =
1596           intersectAndWarn(*CurrBlockInfo, CBS_Entry,
1597                            *PrevBlockInfo, CBS_Exit,
1598                            LEK_LockedSomePredecessors);
1599       }
1600     }
1601
1602     // Process continue and break blocks. Assume that the lockset for the
1603     // resulting block is unaffected by any discrepancies in them.
1604     for (unsigned SpecialI = 0, SpecialN = SpecialBlocks.size();
1605          SpecialI < SpecialN; ++SpecialI) {
1606       CFGBlock *PrevBlock = SpecialBlocks[SpecialI];
1607       int PrevBlockID = PrevBlock->getBlockID();
1608       CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID];
1609
1610       if (!LocksetInitialized) {
1611         CurrBlockInfo->EntrySet = PrevBlockInfo->ExitSet;
1612         LocksetInitialized = true;
1613       } else {
1614         // Determine whether this edge is a loop terminator for diagnostic
1615         // purposes. FIXME: A 'break' statement might be a loop terminator, but
1616         // it might also be part of a switch. Also, a subsequent destructor
1617         // might add to the lockset, in which case the real issue might be a
1618         // double lock on the other path.
1619         const Stmt *Terminator = PrevBlock->getTerminator();
1620         bool IsLoop = Terminator && isa<ContinueStmt>(Terminator);
1621
1622         // Do not update EntrySet.
1623         intersectAndWarn(*CurrBlockInfo, CBS_Entry, *PrevBlockInfo, CBS_Exit,
1624                          IsLoop ? LEK_LockedSomeLoopIterations
1625                                 : LEK_LockedSomePredecessors);
1626       }
1627     }
1628
1629     BuildLockset LocksetBuilder(this, *CurrBlockInfo);
1630     CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(),
1631                                   PE = CurrBlock->pred_end();
1632     if (PI != PE) {
1633       // If the predecessor ended in a branch, then process any trylocks.
1634       // FIXME -- check to make sure there's only one predecessor.
1635       if (Stmt *TCE = (*PI)->getTerminatorCondition()) {
1636         LocksetBuilder.handleTrylock(TCE, *PI, CurrBlock);
1637       }
1638     }
1639
1640     // Visit all the statements in the basic block.
1641     for (CFGBlock::const_iterator BI = CurrBlock->begin(),
1642          BE = CurrBlock->end(); BI != BE; ++BI) {
1643       switch (BI->getKind()) {
1644         case CFGElement::Statement: {
1645           const CFGStmt *CS = cast<CFGStmt>(&*BI);
1646           LocksetBuilder.Visit(const_cast<Stmt*>(CS->getStmt()));
1647           break;
1648         }
1649         // Ignore BaseDtor, MemberDtor, and TemporaryDtor for now.
1650         case CFGElement::AutomaticObjectDtor: {
1651           const CFGAutomaticObjDtor *AD = cast<CFGAutomaticObjDtor>(&*BI);
1652           CXXDestructorDecl *DD = const_cast<CXXDestructorDecl*>(
1653             AD->getDestructorDecl(AC.getASTContext()));
1654           if (!DD->hasAttrs())
1655             break;
1656
1657           // Create a dummy expression,
1658           VarDecl *VD = const_cast<VarDecl*>(AD->getVarDecl());
1659           DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue,
1660                           AD->getTriggerStmt()->getLocEnd());
1661           LocksetBuilder.handleCall(&DRE, DD);
1662           break;
1663         }
1664         default:
1665           break;
1666       }
1667     }
1668     CurrBlockInfo->ExitSet = LocksetBuilder.LSet;
1669
1670     // For every back edge from CurrBlock (the end of the loop) to another block
1671     // (FirstLoopBlock) we need to check that the Lockset of Block is equal to
1672     // the one held at the beginning of FirstLoopBlock. We can look up the
1673     // Lockset held at the beginning of FirstLoopBlock in the EntryLockSets map.
1674     for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
1675          SE  = CurrBlock->succ_end(); SI != SE; ++SI) {
1676
1677       // if CurrBlock -> *SI is *not* a back edge
1678       if (*SI == 0 || !VisitedBlocks.alreadySet(*SI))
1679         continue;
1680
1681       CFGBlock *FirstLoopBlock = *SI;
1682       CFGBlockInfo &PreLoop = BlockInfo[FirstLoopBlock->getBlockID()];
1683       CFGBlockInfo &LoopEnd = BlockInfo[CurrBlockID];
1684       intersectAndWarn(LoopEnd, CBS_Exit, PreLoop, CBS_Entry,
1685                        LEK_LockedSomeLoopIterations);
1686     }
1687   }
1688
1689   CFGBlockInfo &Initial = BlockInfo[CFGraph->getEntry().getBlockID()];
1690   CFGBlockInfo &Final = BlockInfo[CFGraph->getExit().getBlockID()];
1691
1692   // FIXME: Should we call this function for all blocks which exit the function?
1693   intersectAndWarn(Initial, CBS_Entry, Final, CBS_Exit,
1694                    LEK_LockedAtEndOfFunction);
1695 }
1696
1697 } // end anonymous namespace
1698
1699
1700 namespace clang {
1701 namespace thread_safety {
1702
1703 /// \brief Check a function's CFG for thread-safety violations.
1704 ///
1705 /// We traverse the blocks in the CFG, compute the set of mutexes that are held
1706 /// at the end of each block, and issue warnings for thread safety violations.
1707 /// Each block in the CFG is traversed exactly once.
1708 void runThreadSafetyAnalysis(AnalysisDeclContext &AC,
1709                              ThreadSafetyHandler &Handler) {
1710   ThreadSafetyAnalyzer Analyzer(Handler);
1711   Analyzer.runAnalysis(AC);
1712 }
1713
1714 /// \brief Helper function that returns a LockKind required for the given level
1715 /// of access.
1716 LockKind getLockKindFromAccessKind(AccessKind AK) {
1717   switch (AK) {
1718     case AK_Read :
1719       return LK_Shared;
1720     case AK_Written :
1721       return LK_Exclusive;
1722   }
1723   llvm_unreachable("Unknown AccessKind");
1724 }
1725
1726 }} // end namespace clang::thread_safety