Thread safety analysis: refactor to support more sophisticated handling

of expressions, and better error messages.

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@161690 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 404 insertions, 170 deletions

diff --git a/lib/Analysis/ThreadSafety.cpp b/lib/Analysis/ThreadSafety.cpp
index 23394155e7..d359f4f93d 100644
--- a/lib/Analysis/ThreadSafety.cpp
+++ b/lib/Analysis/ThreadSafety.cpp
@@ -46,8 +46,15 @@ ThreadSafetyHandler::~ThreadSafetyHandler() {}
 
 namespace {
 
-/// \brief A MutexID object uniquely identifies a particular mutex, and
-/// is built from an Expr* (i.e. calling a lock function).
+/// SExpr implements a simple expression language that is used to store,
+/// compare, and pretty-print C++ expressions.  Unlike a clang Expr, a SExpr
+/// does not capture surface syntax, and it does not distinguish between
+/// C++ concepts, like pointers and references, that have no real semantic
+/// differences.  This simplicity allows SExprs to be meaningfully compared,
+/// e.g.
+///        (x)          =  x
+///        (*this).foo  =  this->foo
+///        *&a          =  a
 ///
 /// Thread-safety analysis works by comparing lock expressions.  Within the
 /// body of a function, an expression such as "x->foo->bar.mu" will resolve to
@@ -60,30 +67,82 @@ namespace {
 ///
 /// 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 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.  Null is used to denote 'this'.
-///
-/// Note we will need to perform substitution on "this" and function parameter
-/// names when constructing a lock expression.
-///
-/// For example:
-/// class C { Mutex Mu;  void lock() EXCLUSIVE_LOCK_FUNCTION(this->Mu); };
-/// void myFunc(C *X) { ... X->lock() ... }
-/// The original expression for the mutex acquired by myFunc is "this->Mu", but
-/// "X" is substituted for "this" so we get X->Mu();
-///
-/// For another example:
-/// foo(MyList *L) EXCLUSIVE_LOCKS_REQUIRED(L->Mu) { ... }
-/// MyList *MyL;
-/// foo(MyL);  // requires lock MyL->Mu to be held
-class MutexID {
-  SmallVector<NamedDecl*, 2> DeclSeq;
+class SExpr {
+private:
+  enum ExprOp {
+    EOP_Nop,      //< No-op
+    EOP_This,     //< This keyword.
+    EOP_NVar,     //< Named variable.
+    EOP_LVar,     //< Local variable.
+    EOP_Dot,      //< Field access
+    EOP_Call,     //< Function call
+    EOP_MCall,    //< Method call
+    EOP_Index,    //< Array index
+    EOP_Unary,    //< Unary operation
+    EOP_Binary,   //< Binary operation
+    EOP_Unknown   //< Catchall for everything else
+  };
+
+
+  class SExprNode {
+   private:
+    unsigned char  Op;     //< Opcode of the root node
+    unsigned char  Flags;  //< Additional opcode-specific data
+    unsigned short Sz;     //< Number of child nodes
+    const void*    Data;   //< Additional opcode-specific data
+
+   public:
+    SExprNode(ExprOp O, unsigned F, const void* D)
+      : Op(static_cast<unsigned char>(O)),
+        Flags(static_cast<unsigned char>(F)), Sz(1), Data(D)
+    { }
+
+    unsigned size() const        { return Sz; }
+    void     setSize(unsigned S) { Sz = S;    }
+
+    ExprOp   kind() const { return static_cast<ExprOp>(Op); }
+
+    const NamedDecl* getNamedDecl() const {
+      assert(Op == EOP_NVar || Op == EOP_LVar || Op == EOP_Dot);
+      return reinterpret_cast<const NamedDecl*>(Data);
+    }
+
+    const NamedDecl* getFunctionDecl() const {
+      assert(Op == EOP_Call || Op == EOP_MCall);
+      return reinterpret_cast<const NamedDecl*>(Data);
+    }
+
+    bool isArrow() const { return Op == EOP_Dot && Flags == 1; }
+    void setArrow(bool A) { Flags = A ? 1 : 0; }
+
+    unsigned arity() const {
+      switch (Op) {
+        case EOP_Nop:      return 0;
+        case EOP_NVar:     return 0;
+        case EOP_LVar:     return 0;
+        case EOP_This:     return 0;
+        case EOP_Dot:      return 1;
+        case EOP_Call:     return Flags+1;  // First arg is function.
+        case EOP_MCall:    return Flags+1;  // First arg is implicit obj.
+        case EOP_Index:    return 2;
+        case EOP_Unary:    return 1;
+        case EOP_Binary:   return 2;
+        case EOP_Unknown:  return Flags;
+      }
+      return 0;
+    }
+
+    bool operator==(const SExprNode& Other) const {
+      // Ignore flags and size -- they don't matter.
+      return Op == Other.Op &&
+             Data == Other.Data;
+    }
+
+    bool operator!=(const SExprNode& Other) const {
+      return !(*this == Other);
+    }
+  };
+
 
   /// \brief Encapsulates the lexical context of a function call.  The lexical
   /// context includes the arguments to the call, including the implicit object
@@ -95,27 +154,98 @@ class MutexID {
   /// should be evaluated; multiple calling contexts can be chained together
   /// by the lock_returned attribute.
   struct CallingContext {
-    const NamedDecl* AttrDecl;  // The decl to which the attribute is attached.
-    Expr*            SelfArg;   // Implicit object argument -- e.g. 'this'
-    unsigned         NumArgs;   // Number of funArgs
-    Expr**           FunArgs;   // Function arguments
-    CallingContext*  PrevCtx;   // The previous context; or 0 if none.
-
-    CallingContext(const NamedDecl* D = 0, Expr* S = 0,
-                   unsigned N = 0, Expr** A = 0, CallingContext* P = 0)
-      : AttrDecl(D), SelfArg(S), NumArgs(N), FunArgs(A), PrevCtx(P)
+    const NamedDecl* AttrDecl;   // The decl to which the attribute is attached.
+    Expr*            SelfArg;    // Implicit object argument -- e.g. 'this'
+    bool             SelfArrow;  // is Self referred to with -> or .?
+    unsigned         NumArgs;    // Number of funArgs
+    Expr**           FunArgs;    // Function arguments
+    CallingContext*  PrevCtx;    // The previous context; or 0 if none.
+
+    CallingContext(const NamedDecl *D = 0, Expr *S = 0,
+                   unsigned N = 0, Expr **A = 0, CallingContext *P = 0)
+      : AttrDecl(D), SelfArg(S), SelfArrow(false),
+        NumArgs(N), FunArgs(A), PrevCtx(P)
     { }
   };
 
-  /// Build a Decl sequence representing the lock from the given expression.
+  typedef SmallVector<SExprNode, 4> NodeVector;
+
+private:
+  // A SExpr is a list of SExprNodes in prefix order.  The Size field allows
+  // the list to be traversed as a tree.
+  NodeVector NodeVec;
+
+private:
+  unsigned getNextIndex(unsigned i) const {
+    return i + NodeVec[i].size();
+  }
+
+  unsigned makeNop() {
+    NodeVec.push_back(SExprNode(EOP_Nop, 0, 0));
+    return NodeVec.size()-1;
+  }
+
+  unsigned makeNamedVar(const NamedDecl *D) {
+    NodeVec.push_back(SExprNode(EOP_NVar, 0, D));
+    return NodeVec.size()-1;
+  }
+
+  unsigned makeLocalVar(const NamedDecl *D) {
+    NodeVec.push_back(SExprNode(EOP_LVar, 0, D));
+    return NodeVec.size()-1;
+  }
+
+  unsigned makeThis() {
+    NodeVec.push_back(SExprNode(EOP_This, 0, 0));
+    return NodeVec.size()-1;
+  }
+
+  unsigned makeDot(const NamedDecl *D, bool Arrow) {
+    NodeVec.push_back(SExprNode(EOP_Dot, Arrow ? 1 : 0, D));
+    return NodeVec.size()-1;
+  }
+
+  unsigned makeCall(unsigned NumArgs, const NamedDecl *D) {
+    NodeVec.push_back(SExprNode(EOP_Call, NumArgs, D));
+    return NodeVec.size()-1;
+  }
+
+  unsigned makeMCall(unsigned NumArgs, const NamedDecl *D) {
+    NodeVec.push_back(SExprNode(EOP_MCall, NumArgs, D));
+    return NodeVec.size()-1;
+  }
+
+  unsigned makeIndex() {
+    NodeVec.push_back(SExprNode(EOP_Index, 0, 0));
+    return NodeVec.size()-1;
+  }
+
+  unsigned makeUnary() {
+    NodeVec.push_back(SExprNode(EOP_Unary, 0, 0));
+    return NodeVec.size()-1;
+  }
+
+  unsigned makeBinary() {
+    NodeVec.push_back(SExprNode(EOP_Binary, 0, 0));
+    return NodeVec.size()-1;
+  }
+
+  unsigned makeUnknown(unsigned Arity) {
+    NodeVec.push_back(SExprNode(EOP_Unknown, Arity, 0));
+    return NodeVec.size()-1;
+  }
+
+  /// Build an SExpr from the given C++ expression.
   /// Recursive function that terminates on DeclRefExpr.
-  /// Note: this function merely creates a MutexID; it does not check to
+  /// Note: this function merely creates a SExpr; it does not check to
   /// ensure that the original expression is a valid mutex expression.
-  void buildMutexID(Expr *Exp, CallingContext* CallCtx) {
-    if (!Exp) {
-      DeclSeq.clear();
-      return;
-    }
+  ///
+  /// NDeref returns the number of Derefence and AddressOf operations
+  /// preceeding the Expr; this is used to decide whether to pretty-print
+  /// SExprs with . or ->.
+  unsigned buildSExpr(Expr *Exp, CallingContext* CallCtx, int* NDeref = 0) {
+    if (!Exp)
+      return 0;
 
     if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Exp)) {
       NamedDecl *ND = cast<NamedDecl>(DRE->getDecl()->getCanonicalDecl());
@@ -129,27 +259,35 @@ class MutexID {
             FD == CallCtx->AttrDecl->getCanonicalDecl()) {
           // Substitute call arguments for references to function parameters
           assert(i < CallCtx->NumArgs);
-          buildMutexID(CallCtx->FunArgs[i], CallCtx->PrevCtx);
-          return;
+          return buildSExpr(CallCtx->FunArgs[i], CallCtx->PrevCtx, NDeref);
         }
         // Map the param back to the param of the original function declaration.
-        DeclSeq.push_back(FD->getParamDecl(i));
-        return;
+        makeNamedVar(FD->getParamDecl(i));
+        return 1;
       }
       // Not a function parameter -- just store the reference.
-      DeclSeq.push_back(ND);
+      makeNamedVar(ND);
+      return 1;
     } else if (isa<CXXThisExpr>(Exp)) {
       // Substitute parent for 'this'
-      if (CallCtx && CallCtx->SelfArg)
-        buildMutexID(CallCtx->SelfArg, CallCtx->PrevCtx);
+      if (CallCtx && CallCtx->SelfArg) {
+        if (!CallCtx->SelfArrow && NDeref)
+          // 'this' is a pointer, but self is not, so need to take address.
+          --(*NDeref);
+        return buildSExpr(CallCtx->SelfArg, CallCtx->PrevCtx, NDeref);
+      }
       else {
-        DeclSeq.push_back(0);  // Use 0 to represent 'this'.
-        return;  // mutexID is still valid in this case
+        makeThis();
+        return 1;
       }
     } else if (MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) {
       NamedDecl *ND = ME->getMemberDecl();
-      DeclSeq.push_back(ND);
-      buildMutexID(ME->getBase(), CallCtx);
+      int ImplicitDeref = ME->isArrow() ? 1 : 0;
+      unsigned Root = makeDot(ND, false);
+      unsigned Sz = buildSExpr(ME->getBase(), CallCtx, &ImplicitDeref);
+      NodeVec[Root].setArrow(ImplicitDeref > 0);
+      NodeVec[Root].setSize(Sz + 1);
+      return Sz + 1;
     } else if (CXXMemberCallExpr *CMCE = dyn_cast<CXXMemberCallExpr>(Exp)) {
       // When calling a function with a lock_returned attribute, replace
       // the function call with the expression in lock_returned.
@@ -157,26 +295,31 @@ class MutexID {
             CMCE->getMethodDecl()->getAttr<LockReturnedAttr>()) {
         CallingContext LRCallCtx(CMCE->getMethodDecl());
         LRCallCtx.SelfArg = CMCE->getImplicitObjectArgument();
+        LRCallCtx.SelfArrow =
+          dyn_cast<MemberExpr>(CMCE->getCallee())->isArrow();
         LRCallCtx.NumArgs = CMCE->getNumArgs();
         LRCallCtx.FunArgs = CMCE->getArgs();
         LRCallCtx.PrevCtx = CallCtx;
-        buildMutexID(At->getArg(), &LRCallCtx);
-        return;
+        return buildSExpr(At->getArg(), &LRCallCtx);
       }
       // Hack to treat smart pointers and iterators as pointers;
       // ignore any method named get().
       if (CMCE->getMethodDecl()->getNameAsString() == "get" &&
           CMCE->getNumArgs() == 0) {
-        buildMutexID(CMCE->getImplicitObjectArgument(), CallCtx);
-        return;
+        if (NDeref && dyn_cast<MemberExpr>(CMCE->getCallee())->isArrow())
+          ++(*NDeref);
+        return buildSExpr(CMCE->getImplicitObjectArgument(), CallCtx, NDeref);
       }
-      DeclSeq.push_back(CMCE->getMethodDecl()->getCanonicalDecl());
-      buildMutexID(CMCE->getImplicitObjectArgument(), CallCtx);
       unsigned NumCallArgs = CMCE->getNumArgs();
+      unsigned Root =
+        makeMCall(NumCallArgs, CMCE->getMethodDecl()->getCanonicalDecl());
+      unsigned Sz = buildSExpr(CMCE->getImplicitObjectArgument(), CallCtx);
       Expr** CallArgs = CMCE->getArgs();
       for (unsigned i = 0; i < NumCallArgs; ++i) {
-        buildMutexID(CallArgs[i], CallCtx);
+        Sz += buildSExpr(CallArgs[i], CallCtx);
       }
+      NodeVec[Root].setSize(Sz + 1);
+      return Sz + 1;
     } else if (CallExpr *CE = dyn_cast<CallExpr>(Exp)) {
       if (LockReturnedAttr* At =
             CE->getDirectCallee()->getAttr<LockReturnedAttr>()) {
@@ -184,49 +327,80 @@ class MutexID {
         LRCallCtx.NumArgs = CE->getNumArgs();
         LRCallCtx.FunArgs = CE->getArgs();
         LRCallCtx.PrevCtx = CallCtx;
-        buildMutexID(At->getArg(), &LRCallCtx);
-        return;
+        return buildSExpr(At->getArg(), &LRCallCtx);
       }
       // Treat smart pointers and iterators as pointers;
       // ignore the * and -> operators.
       if (CXXOperatorCallExpr *OE = dyn_cast<CXXOperatorCallExpr>(CE)) {
         OverloadedOperatorKind k = OE->getOperator();
-        if (k == OO_Arrow || k == OO_Star) {
-          buildMutexID(OE->getArg(0), CallCtx);
-          return;
+        if (k == OO_Star) {
+          if (NDeref) ++(*NDeref);
+          return buildSExpr(OE->getArg(0), CallCtx, NDeref);
+        }
+        else if (k == OO_Arrow) {
+          return buildSExpr(OE->getArg(0), CallCtx, NDeref);
         }
       }
-      buildMutexID(CE->getCallee(), CallCtx);
       unsigned NumCallArgs = CE->getNumArgs();
+      unsigned Root = makeCall(NumCallArgs, 0);
+      unsigned Sz = buildSExpr(CE->getCallee(), CallCtx);
       Expr** CallArgs = CE->getArgs();
       for (unsigned i = 0; i < NumCallArgs; ++i) {
-        buildMutexID(CallArgs[i], CallCtx);
+        Sz += buildSExpr(CallArgs[i], CallCtx);
       }
+      NodeVec[Root].setSize(Sz+1);
+      return Sz+1;
     } else if (BinaryOperator *BOE = dyn_cast<BinaryOperator>(Exp)) {
-      buildMutexID(BOE->getLHS(), CallCtx);
-      buildMutexID(BOE->getRHS(), CallCtx);
+      unsigned Root = makeBinary();
+      unsigned Sz = buildSExpr(BOE->getLHS(), CallCtx);
+      Sz += buildSExpr(BOE->getRHS(), CallCtx);
+      NodeVec[Root].setSize(Sz);
+      return Sz;
     } else if (UnaryOperator *UOE = dyn_cast<UnaryOperator>(Exp)) {
-      buildMutexID(UOE->getSubExpr(), CallCtx);
+      // Ignore & and * operators -- they're no-ops.
+      // However, we try to figure out whether the expression is a pointer,
+      // so we can use . and -> appropriately in error messages.
+      if (UOE->getOpcode() == UO_Deref) {
+        if (NDeref) ++(*NDeref);
+        return buildSExpr(UOE->getSubExpr(), CallCtx, NDeref);
+      }
+      if (UOE->getOpcode() == UO_AddrOf) {
+        if (NDeref) --(*NDeref);
+        return buildSExpr(UOE->getSubExpr(), CallCtx, NDeref);
+      }
+      unsigned Root = makeUnary();
+      unsigned Sz = buildSExpr(UOE->getSubExpr(), CallCtx);
+      NodeVec[Root].setSize(Sz);
+      return Sz;
     } else if (ArraySubscriptExpr *ASE = dyn_cast<ArraySubscriptExpr>(Exp)) {
-      buildMutexID(ASE->getBase(), CallCtx);
-      buildMutexID(ASE->getIdx(), CallCtx);
+      unsigned Root = makeIndex();
+      unsigned Sz = buildSExpr(ASE->getBase(), CallCtx);
+      Sz += buildSExpr(ASE->getIdx(), CallCtx);
+      NodeVec[Root].setSize(Sz);
+      return Sz;
     } else if (AbstractConditionalOperator *CE =
-                 dyn_cast<AbstractConditionalOperator>(Exp)) {
-      buildMutexID(CE->getCond(), CallCtx);
-      buildMutexID(CE->getTrueExpr(), CallCtx);
-      buildMutexID(CE->getFalseExpr(), CallCtx);
+               dyn_cast<AbstractConditionalOperator>(Exp)) {
+      unsigned Root = makeUnknown(3);
+      unsigned Sz = buildSExpr(CE->getCond(), CallCtx);
+      Sz += buildSExpr(CE->getTrueExpr(), CallCtx);
+      Sz += buildSExpr(CE->getFalseExpr(), CallCtx);
+      NodeVec[Root].setSize(Sz);
+      return Sz;
     } else if (ChooseExpr *CE = dyn_cast<ChooseExpr>(Exp)) {
-      buildMutexID(CE->getCond(), CallCtx);
-      buildMutexID(CE->getLHS(), CallCtx);
-      buildMutexID(CE->getRHS(), CallCtx);
+      unsigned Root = makeUnknown(3);
+      unsigned Sz = buildSExpr(CE->getCond(), CallCtx);
+      Sz += buildSExpr(CE->getLHS(), CallCtx);
+      Sz += buildSExpr(CE->getRHS(), CallCtx);
+      NodeVec[Root].setSize(Sz);
+      return Sz;
     } else if (CastExpr *CE = dyn_cast<CastExpr>(Exp)) {
-      buildMutexID(CE->getSubExpr(), CallCtx);
+      return buildSExpr(CE->getSubExpr(), CallCtx, NDeref);
     } else if (ParenExpr *PE = dyn_cast<ParenExpr>(Exp)) {
-      buildMutexID(PE->getSubExpr(), CallCtx);
+      return buildSExpr(PE->getSubExpr(), CallCtx, NDeref);
     } else if (ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Exp)) {
-      buildMutexID(EWC->getSubExpr(), CallCtx);
+      return buildSExpr(EWC->getSubExpr(), CallCtx, NDeref);
     } else if (CXXBindTemporaryExpr *E = dyn_cast<CXXBindTemporaryExpr>(Exp)) {
-      buildMutexID(E->getSubExpr(), CallCtx);
+      return buildSExpr(E->getSubExpr(), CallCtx, NDeref);
     } else if (isa<CharacterLiteral>(Exp) ||
                isa<CXXNullPtrLiteralExpr>(Exp) ||
                isa<GNUNullExpr>(Exp) ||
@@ -236,34 +410,38 @@ class MutexID {
                isa<IntegerLiteral>(Exp) ||
                isa<StringLiteral>(Exp) ||
                isa<ObjCStringLiteral>(Exp)) {
-      return;  // FIXME: Ignore literals for now
+      makeNop();
+      return 1;  // FIXME: Ignore literals for now
     } else {
-      // Ignore.  FIXME: mark as invalid expression?
+      makeNop();
+      return 1;  // Ignore.  FIXME: mark as invalid expression?
     }
   }
 
-  /// \brief Construct a MutexID from an expression.
+  /// \brief Construct a SExpr 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) {
+  void buildSExprFromExpr(Expr *MutexExp, Expr *DeclExp, const NamedDecl *D) {
     CallingContext CallCtx(D);
 
     // If we are processing a raw attribute expression, with no substitutions.
     if (DeclExp == 0) {
-      buildMutexID(MutexExp, 0);
+      buildSExpr(MutexExp, 0);
       return;
     }
 
     // Examine DeclExp to find SelfArg and FunArgs, which are used to substitute
     // for formal parameters when we call buildMutexID later.
     if (MemberExpr *ME = dyn_cast<MemberExpr>(DeclExp)) {
-      CallCtx.SelfArg = ME->getBase();
+      CallCtx.SelfArg   = ME->getBase();
+      CallCtx.SelfArrow = ME->isArrow();
     } else if (CXXMemberCallExpr *CE = dyn_cast<CXXMemberCallExpr>(DeclExp)) {
-      CallCtx.SelfArg = CE->getImplicitObjectArgument();
-      CallCtx.NumArgs = CE->getNumArgs();
-      CallCtx.FunArgs = CE->getArgs();
+      CallCtx.SelfArg   = CE->getImplicitObjectArgument();
+      CallCtx.SelfArrow = dyn_cast<MemberExpr>(CE->getCallee())->isArrow();
+      CallCtx.NumArgs   = CE->getNumArgs();
+      CallCtx.FunArgs   = CE->getArgs();
     } else if (CallExpr *CE = dyn_cast<CallExpr>(DeclExp)) {
       CallCtx.NumArgs = CE->getNumArgs();
       CallCtx.FunArgs = CE->getArgs();
@@ -278,32 +456,30 @@ class MutexID {
 
     // If the attribute has no arguments, then assume the argument is "this".
     if (MutexExp == 0) {
-      buildMutexID(CallCtx.SelfArg, 0);
+      buildSExpr(CallCtx.SelfArg, 0);
       return;
     }
 
     // For most attributes.
-    buildMutexID(MutexExp, &CallCtx);
+    buildSExpr(MutexExp, &CallCtx);
   }
 
 public:
-  explicit MutexID(clang::Decl::EmptyShell e) {
-    DeclSeq.clear();
-  }
+  explicit SExpr(clang::Decl::EmptyShell e) { NodeVec.clear(); }
 
   /// \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);
+  SExpr(Expr* MutexExp, Expr *DeclExp, const NamedDecl* D) {
+    buildSExprFromExpr(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();
+    return !NodeVec.empty();
   }
 
   /// Issue a warning about an invalid lock expression
@@ -318,57 +494,115 @@ public:
       Handler.handleInvalidLockExp(Loc);
   }
 
-  bool operator==(const MutexID &other) const {
-    return DeclSeq == other.DeclSeq;
+  bool operator==(const SExpr &other) const {
+    return NodeVec == other.NodeVec;
   }
 
-  bool operator!=(const MutexID &other) const {
+  bool operator!=(const SExpr &other) const {
     return !(*this == other);
   }
 
-  // SmallVector overloads Operator< to do lexicographic ordering. Note that
-  // we use pointer equality (and <) to compare NamedDecls. This means the order
-  // of MutexIDs in a lockset is nondeterministic. In order to output
-  // diagnostics in a deterministic ordering, we must order all diagnostics to
-  // output by SourceLocation when iterating through this lockset.
-  bool operator<(const MutexID &other) const {
-    return DeclSeq < other.DeclSeq;
-  }
-
-  /// \brief Returns the name of the first Decl in the list for a given MutexID;
-  /// e.g. the lock expression foo.bar() has name "bar".
-  /// 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.
-  std::string getName() const {
+  /// \brief Pretty print a lock expression for use in error messages.
+  std::string toString(unsigned i = 0) const {
     assert(isValid());
-    if (!DeclSeq.front())
-      return "this";  // Use 0 to represent 'this'.
-    return DeclSeq.front()->getNameAsString();
-  }
-
-  void Profile(llvm::FoldingSetNodeID &ID) const {
-    for (SmallVectorImpl<NamedDecl*>::const_iterator I = DeclSeq.begin(),
-         E = DeclSeq.end(); I != E; ++I) {
-      ID.AddPointer(*I);
+    if (i >= NodeVec.size())
+      return "";
+
+    const SExprNode* N = &NodeVec[i];
+    switch (N->kind()) {
+      case EOP_Nop:
+        return "_";
+      case EOP_This:
+        return "this";
+      case EOP_NVar:
+      case EOP_LVar: {
+        return N->getNamedDecl()->getNameAsString();
+      }
+      case EOP_Dot: {
+        std::string FieldName = N->getNamedDecl()->getNameAsString();
+        if (NodeVec[i+1].kind() == EOP_This)
+          return FieldName;
+        std::string S = toString(i+1);
+        if (N->isArrow())
+          return S + "->" + FieldName;
+        else
+          return S + "." + FieldName;
+      }
+      case EOP_Call: {
+        std::string S = toString(i+1) + "(";
+        unsigned NumArgs = N->arity()-1;
+        unsigned ci = getNextIndex(i+1);
+        for (unsigned k=0; k<NumArgs; ++k, ci = getNextIndex(ci)) {
+          S += toString(ci);
+          if (k+1 < NumArgs) S += ",";
+        }
+        S += ")";
+        return S;
+      }
+      case EOP_MCall: {
+        std::string S = "";
+        if (NodeVec[i+1].kind() != EOP_This)
+          S = toString(i+1) + ".";
+        if (const NamedDecl *D = N->getFunctionDecl())
+          S += D->getNameAsString() + "(";
+        else
+          S += "#(";
+        unsigned NumArgs = N->arity()-1;
+        unsigned ci = getNextIndex(i+1);
+        for (unsigned k=0; k<NumArgs; ++k, ci = getNextIndex(ci)) {
+          S += toString(ci);
+          if (k+1 < NumArgs) S += ",";
+        }
+        S += ")";
+        return S;
+      }
+      case EOP_Index: {
+        std::string S1 = toString(i+1);
+        std::string S2 = toString(i+1 + NodeVec[i+1].size());
+        return S1 + "[" + S2 + "]";
+      }
+      case EOP_Unary: {
+        std::string S = toString(i+1);
+        return "#" + S;
+      }
+      case EOP_Binary: {
+        std::string S1 = toString(i+1);
+        std::string S2 = toString(i+1 + NodeVec[i+1].size());
+        return "(" + S1 + "#" + S2 + ")";
+      }
+      case EOP_Unknown: {
+        unsigned NumChildren = N->arity();
+        if (NumChildren == 0)
+          return "(...)";
+        std::string S = "(";
+        unsigned ci = i+1;
+        for (unsigned j = 0; j < NumChildren; ++j, ci = getNextIndex(ci)) {
+          S += toString(ci);
+          if (j+1 < NumChildren) S += "#";
+        }
+        S += ")";
+        return S;
+      }
     }
+    return "";
   }
 };
 
 
-/// \brief A short list of MutexIDs
-class MutexIDList : public SmallVector<MutexID, 3> {
+
+/// \brief A short list of SExprs
+class MutexIDList : public SmallVector<SExpr, 3> {
 public:
-  /// \brief Return true if the list contains the specified MutexID
+  /// \brief Return true if the list contains the specified SExpr
   /// Performs a linear search, because these lists are almost always very small.
-  bool contains(const MutexID& M) {
+  bool contains(const SExpr& M) {
     for (iterator I=begin(),E=end(); I != E; ++I)
       if ((*I) == M) return true;
     return false;
   }
 
   /// \brief Push M onto list, bud discard duplicates
-  void push_back_nodup(const MutexID& M) {
+  void push_back_nodup(const SExpr& M) {
     if (!contains(M)) push_back(M);
   }
 };
@@ -390,14 +624,14 @@ struct LockData {
   /// FIXME: add support for re-entrant locking and lock up/downgrading
   LockKind LKind;
   bool     Managed;            // for ScopedLockable objects
-  MutexID  UnderlyingMutex;    // for ScopedLockable objects
+  SExpr    UnderlyingMutex;    // for ScopedLockable objects
 
   LockData(SourceLocation AcquireLoc, LockKind LKind, bool M = false)
     : AcquireLoc(AcquireLoc), LKind(LKind), Managed(M),
       UnderlyingMutex(Decl::EmptyShell())
   {}
 
-  LockData(SourceLocation AcquireLoc, LockKind LKind, const MutexID &Mu)
+  LockData(SourceLocation AcquireLoc, LockKind LKind, const SExpr &Mu)
     : AcquireLoc(AcquireLoc), LKind(LKind), Managed(false),
       UnderlyingMutex(Mu)
   {}
@@ -421,10 +655,10 @@ struct LockData {
 /// in the program execution.  Currently, this is information regarding a lock
 /// that is held at that point.  
 struct FactEntry {
-  MutexID  MutID;
+  SExpr    MutID;
   LockData LDat;
 
-  FactEntry(const MutexID& M, const LockData& L)
+  FactEntry(const SExpr& M, const LockData& L)
     : MutID(M), LDat(L)
   { }
 };
@@ -439,7 +673,7 @@ private:
   std::vector<FactEntry> Facts;
 
 public:
-  FactID newLock(const MutexID& M, const LockData& L) {
+  FactID newLock(const SExpr& M, const LockData& L) {
     Facts.push_back(FactEntry(M,L));
     return static_cast<unsigned short>(Facts.size() - 1);
   }
@@ -474,13 +708,13 @@ public:
 
   bool isEmpty() const { return FactIDs.size() == 0; }
 
-  FactID addLock(FactManager& FM, const MutexID& M, const LockData& L) {
+  FactID addLock(FactManager& FM, const SExpr& M, const LockData& L) {
     FactID F = FM.newLock(M, L);
     FactIDs.push_back(F);
     return F;
   }
 
-  bool removeLock(FactManager& FM, const MutexID& M) {
+  bool removeLock(FactManager& FM, const SExpr& M) {
     unsigned n = FactIDs.size();
     if (n == 0)
       return false;
@@ -499,7 +733,7 @@ public:
     return false;
   }
 
-  LockData* findLock(FactManager& FM, const MutexID& M) const {
+  LockData* findLock(FactManager& FM, const SExpr& M) const {
     for (const_iterator I=begin(), E=end(); I != E; ++I) {
       if (FM[*I].MutID == M) return &FM[*I].LDat;
     }
@@ -509,9 +743,9 @@ public:
 
 
 
-/// A Lockset maps each MutexID (defined above) to information about how it has
+/// A Lockset maps each SExpr (defined above) to information about how it has
 /// been locked.
-typedef llvm::ImmutableMap<MutexID, LockData> Lockset;
+typedef llvm::ImmutableMap<SExpr, LockData> Lockset;
 typedef llvm::ImmutableMap<const NamedDecl*, unsigned> LocalVarContext;
 
 class LocalVariableMap;
@@ -1052,8 +1286,8 @@ class ThreadSafetyAnalyzer {
 public:
   ThreadSafetyAnalyzer(ThreadSafetyHandler &H) : Handler(H) {}
 
-  void addLock(FactSet &FSet, const MutexID &Mutex, const LockData &LDat);
-  void removeLock(FactSet &FSet, const MutexID &Mutex,
+  void addLock(FactSet &FSet, const SExpr &Mutex, const LockData &LDat);
+  void removeLock(FactSet &FSet, const SExpr &Mutex,
                   SourceLocation UnlockLoc, bool FullyRemove=false);
 
   template <typename AttrType>
@@ -1091,12 +1325,12 @@ public:
 /// \brief Add a new lock to the lockset, warning if the lock is already there.
 /// \param Mutex -- the Mutex expression for the lock
 /// \param LDat  -- the LockData for the lock
-void ThreadSafetyAnalyzer::addLock(FactSet &FSet, const MutexID &Mutex,
+void ThreadSafetyAnalyzer::addLock(FactSet &FSet, const SExpr &Mutex,
                                    const LockData &LDat) {
   // FIXME: deal with acquired before/after annotations.
   // FIXME: Don't always warn when we have support for reentrant locks.
   if (FSet.findLock(FactMan, Mutex)) {
-    Handler.handleDoubleLock(Mutex.getName(), LDat.AcquireLoc);
+    Handler.handleDoubleLock(Mutex.toString(), LDat.AcquireLoc);
   } else {
     FSet.addLock(FactMan, Mutex, LDat);
   }
@@ -1107,12 +1341,12 @@ void ThreadSafetyAnalyzer::addLock(FactSet &FSet, const MutexID &Mutex,
 /// \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 ThreadSafetyAnalyzer::removeLock(FactSet &FSet,
-                                      const MutexID &Mutex,
+                                      const SExpr &Mutex,
                                       SourceLocation UnlockLoc,
                                       bool FullyRemove) {
   const LockData *LDat = FSet.findLock(FactMan, Mutex);
   if (!LDat) {
-    Handler.handleUnmatchedUnlock(Mutex.getName(), UnlockLoc);
+    Handler.handleUnmatchedUnlock(Mutex.toString(), UnlockLoc);
     return;
   }
 
@@ -1127,7 +1361,7 @@ void ThreadSafetyAnalyzer::removeLock(FactSet &FSet,
       // We're releasing the underlying mutex, but not destroying the
       // managing object.  Warn on dual release.
       if (!FSet.findLock(FactMan, LDat->UnderlyingMutex)) {
-        Handler.handleUnmatchedUnlock(LDat->UnderlyingMutex.getName(),
+        Handler.handleUnmatchedUnlock(LDat->UnderlyingMutex.toString(),
                                       UnlockLoc);
       }
       FSet.removeLock(FactMan, LDat->UnderlyingMutex);
@@ -1147,18 +1381,18 @@ void ThreadSafetyAnalyzer::getMutexIDs(MutexIDList &Mtxs, AttrType *Attr,
 
   if (Attr->args_size() == 0) {
     // The mutex held is the "this" object.
-    MutexID Mu(0, Exp, D);
+    SExpr Mu(0, Exp, D);
     if (!Mu.isValid())
-      MutexID::warnInvalidLock(Handler, 0, Exp, D);
+      SExpr::warnInvalidLock(Handler, 0, Exp, D);
     else
       Mtxs.push_back_nodup(Mu);
     return;
   }
 
   for (iterator_type I=Attr->args_begin(), E=Attr->args_end(); I != E; ++I) {
-    MutexID Mu(*I, Exp, D);
+    SExpr Mu(*I, Exp, D);
     if (!Mu.isValid())
-      MutexID::warnInvalidLock(Handler, *I, Exp, D);
+      SExpr::warnInvalidLock(Handler, *I, Exp, D);
     else
       Mtxs.push_back_nodup(Mu);
   }
@@ -1357,13 +1591,13 @@ class BuildLockset : public StmtVisitor<BuildLockset> {
 
   /// \brief Returns true if the lockset contains a lock, regardless of whether
   /// the lock is held exclusively or shared.
-  bool locksetContains(const MutexID &Mu) const {
+  bool locksetContains(const SExpr &Mu) const {
     return FSet.findLock(Analyzer->FactMan, Mu);
   }
 
   /// \brief Returns true if the lockset contains a lock with the passed in
   /// locktype.
-  bool locksetContains(const MutexID &Mu, LockKind KindRequested) const {
+  bool locksetContains(const SExpr &Mu, LockKind KindRequested) const {
     const LockData *LockHeld = FSet.findLock(Analyzer->FactMan, Mu);
     return (LockHeld && KindRequested == LockHeld->LKind);
   }
@@ -1372,7 +1606,7 @@ 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(const MutexID &Lock,
+  bool locksetContainsAtLeast(const SExpr &Lock,
                               LockKind KindRequested) const {
     switch (KindRequested) {
       case LK_Shared:
@@ -1419,11 +1653,11 @@ void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, Expr *Exp,
                                       ProtectedOperationKind POK) {
   LockKind LK = getLockKindFromAccessKind(AK);
 
-  MutexID Mutex(MutexExp, Exp, D);
+  SExpr Mutex(MutexExp, Exp, D);
   if (!Mutex.isValid())
-    MutexID::warnInvalidLock(Analyzer->Handler, MutexExp, Exp, D);
+    SExpr::warnInvalidLock(Analyzer->Handler, MutexExp, Exp, D);
   else if (!locksetContainsAtLeast(Mutex, LK))
-    Analyzer->Handler.handleMutexNotHeld(D, POK, Mutex.getName(), LK,
+    Analyzer->Handler.handleMutexNotHeld(D, POK, Mutex.toString(), LK,
                                          Exp->getExprLoc());
 }
 
@@ -1537,12 +1771,12 @@ void BuildLockset::handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD) {
         LocksExcludedAttr *A = cast<LocksExcludedAttr>(At);
         for (LocksExcludedAttr::args_iterator I = A->args_begin(),
             E = A->args_end(); I != E; ++I) {
-          MutexID Mutex(*I, Exp, D);
+          SExpr Mutex(*I, Exp, D);
           if (!Mutex.isValid())
-            MutexID::warnInvalidLock(Analyzer->Handler, *I, Exp, D);
+            SExpr::warnInvalidLock(Analyzer->Handler, *I, Exp, D);
           else if (locksetContains(Mutex))
             Analyzer->Handler.handleFunExcludesLock(D->getName(),
-                                                    Mutex.getName(),
+                                                    Mutex.toString(),
                                                     Exp->getExprLoc());
         }
         break;
@@ -1580,7 +1814,7 @@ void BuildLockset::handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD) {
   if (isScopedVar) {
     SourceLocation MLoc = VD->getLocation();
     DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, VD->getLocation());
-    MutexID SMutex(&DRE, 0, 0);
+    SExpr SMutex(&DRE, 0, 0);
 
     for (unsigned i=0,n=ExclusiveLocksToAdd.size(); i<n; ++i) {
       Analyzer->addLock(FSet, SMutex, LockData(MLoc, LK_Exclusive,
@@ -1707,12 +1941,12 @@ void ThreadSafetyAnalyzer::intersectAndWarn(FactSet &FSet1,
 
   for (FactSet::const_iterator I = FSet2.begin(), E = FSet2.end();
        I != E; ++I) {
-    const MutexID &FSet2Mutex = FactMan[*I].MutID;
+    const SExpr &FSet2Mutex = FactMan[*I].MutID;
     const LockData &LDat2 = FactMan[*I].LDat;
 
     if (const LockData *LDat1 = FSet1.findLock(FactMan, FSet2Mutex)) {
       if (LDat1->LKind != LDat2.LKind) {
-        Handler.handleExclusiveAndShared(FSet2Mutex.getName(),
+        Handler.handleExclusiveAndShared(FSet2Mutex.toString(),
                                          LDat2.AcquireLoc,
                                          LDat1->AcquireLoc);
         if (Modify && LDat1->LKind != LK_Exclusive) {
@@ -1726,13 +1960,13 @@ void ThreadSafetyAnalyzer::intersectAndWarn(FactSet &FSet1,
           // If this is a scoped lock that manages another mutex, and if the
           // underlying mutex is still held, then warn about the underlying
           // mutex.
-          Handler.handleMutexHeldEndOfScope(LDat2.UnderlyingMutex.getName(),
+          Handler.handleMutexHeldEndOfScope(LDat2.UnderlyingMutex.toString(),
                                             LDat2.AcquireLoc,
                                             JoinLoc, LEK1);
         }
       }
       else if (!LDat2.Managed)
-        Handler.handleMutexHeldEndOfScope(FSet2Mutex.getName(),
+        Handler.handleMutexHeldEndOfScope(FSet2Mutex.toString(),
                                           LDat2.AcquireLoc,
                                           JoinLoc, LEK1);
     }
@@ -1740,7 +1974,7 @@ void ThreadSafetyAnalyzer::intersectAndWarn(FactSet &FSet1,