Thread Safety Analysis: Replace the old and broken SExpr with the new

til::SExpr.  This is a large patch, with many small changes to pretty printing
and expression lowering to make the new SExpr representation equivalent in
functionality to the old.

llvm-svn: 214089

3 files changed, 419 insertions, 759 deletions

diff --git a/clang/lib/Analysis/ThreadSafety.cpp b/clang/lib/Analysis/ThreadSafety.cpp
index 11df61f8..f4f174d 100644
--- a/clang/lib/Analysis/ThreadSafety.cpp
+++ b/clang/lib/Analysis/ThreadSafety.cpp
@@ -40,682 +40,107 @@
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
+#include <ostream>
+#include <sstream>
 #include <utility>
 #include <vector>
 
-using namespace clang;
-using namespace thread_safety;
+
+namespace clang {
+namespace threadSafety {
 
 // Key method definition
 ThreadSafetyHandler::~ThreadSafetyHandler() {}
 
-namespace {
-
-/// 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
-/// a particular mutex object at run-time.  Subsequent occurrences of the same
-/// expression (where "same" means syntactic equality) will refer to the same
-/// run-time object if three conditions hold:
-/// (1) Local variables in the expression, such as "x" have not changed.
-/// (2) Values on the heap that affect the expression have not changed.
-/// (3) The expression involves only pure function calls.
-///
-/// The current implementation assumes, but does not verify, that multiple uses
-/// of the same lock expression satisfies these criteria.
-class SExpr {
-private:
-  enum ExprOp {
-    EOP_Nop,       ///< No-op
-    EOP_Wildcard,  ///< Matches anything.
-    EOP_Universal, ///< Universal lock.
-    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_Wildcard:  return 0;
-        case EOP_Universal: 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);
-    }
-
-    bool matches(const SExprNode& Other) const {
-      return (*this == Other) ||
-             (Op == EOP_Wildcard) ||
-             (Other.Op == EOP_Wildcard);
-    }
-  };
-
-
-  /// \brief Encapsulates the lexical context of a function call.  The lexical
-  /// context includes the arguments to the call, including the implicit object
-  /// argument.  When an attribute containing a mutex expression is attached to
-  /// a method, the expression may refer to formal parameters of the method.
-  /// Actual arguments must be substituted for formal parameters to derive
-  /// the appropriate mutex expression in the lexical context where the function
-  /// is called.  PrevCtx holds the context in which the arguments themselves
-  /// 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.
-    const Expr*        SelfArg;    // Implicit object argument -- e.g. 'this'
-    bool               SelfArrow;  // is Self referred to with -> or .?
-    unsigned           NumArgs;    // Number of funArgs
-    const Expr* const* FunArgs;    // Function arguments
-    CallingContext*    PrevCtx;    // The previous context; or 0 if none.
-
-    CallingContext(const NamedDecl *D)
-        : AttrDecl(D), SelfArg(nullptr), SelfArrow(false), NumArgs(0),
-          FunArgs(nullptr), PrevCtx(nullptr) {}
-  };
-
-  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 make(ExprOp O, unsigned F = 0, const void *D = nullptr) {
-    NodeVec.push_back(SExprNode(O, F, D));
-    return NodeVec.size() - 1;
-  }
-
-  unsigned makeNop() {
-    return make(EOP_Nop);
-  }
-
-  unsigned makeWildcard() {
-    return make(EOP_Wildcard);
-  }
-
-  unsigned makeUniversal() {
-    return make(EOP_Universal);
-  }
-
-  unsigned makeNamedVar(const NamedDecl *D) {
-    return make(EOP_NVar, 0, D);
-  }
-
-  unsigned makeLocalVar(const NamedDecl *D) {
-    return make(EOP_LVar, 0, D);
-  }
-
-  unsigned makeThis() {
-    return make(EOP_This);
-  }
-
-  unsigned makeDot(const NamedDecl *D, bool Arrow) {
-    return make(EOP_Dot, Arrow ? 1 : 0, D);
-  }
-
-  unsigned makeCall(unsigned NumArgs, const NamedDecl *D) {
-    return make(EOP_Call, NumArgs, D);
-  }
-
-  // Grab the very first declaration of virtual method D
-  const CXXMethodDecl* getFirstVirtualDecl(const CXXMethodDecl *D) {
-    while (true) {
-      D = D->getCanonicalDecl();
-      CXXMethodDecl::method_iterator I = D->begin_overridden_methods(),
-                                     E = D->end_overridden_methods();
-      if (I == E)
-        return D;  // Method does not override anything
-      D = *I;      // FIXME: this does not work with multiple inheritance.
-    }
-    return nullptr;
-  }
-
-  unsigned makeMCall(unsigned NumArgs, const CXXMethodDecl *D) {
-    return make(EOP_MCall, NumArgs, getFirstVirtualDecl(D));
-  }
-
-  unsigned makeIndex() {
-    return make(EOP_Index);
-  }
-
-  unsigned makeUnary() {
-    return make(EOP_Unary);
-  }
-
-  unsigned makeBinary() {
-    return make(EOP_Binary);
-  }
-
-  unsigned makeUnknown(unsigned Arity) {
-    return make(EOP_Unknown, Arity);
-  }
-
-  inline bool isCalleeArrow(const Expr *E) {
-    const MemberExpr *ME = dyn_cast<MemberExpr>(E->IgnoreParenCasts());
-    return ME ? ME->isArrow() : false;
-  }
-
-  /// Build an SExpr from the given C++ expression.
-  /// Recursive function that terminates on DeclRefExpr.
-  /// Note: this function merely creates a SExpr; it does not check to
-  /// ensure that the original expression is a valid mutex expression.
-  ///
-  /// NDeref returns the number of Derefence and AddressOf operations
-  /// preceding the Expr; this is used to decide whether to pretty-print
-  /// SExprs with . or ->.
-  unsigned buildSExpr(const Expr *Exp, CallingContext *CallCtx,
-                      int *NDeref = nullptr) {
-    if (!Exp)
-      return 0;
-
-    if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Exp)) {
-      const NamedDecl *ND = cast<NamedDecl>(DRE->getDecl()->getCanonicalDecl());
-      const ParmVarDecl *PV = dyn_cast_or_null<ParmVarDecl>(ND);
-      if (PV) {
-        const FunctionDecl *FD =
-          cast<FunctionDecl>(PV->getDeclContext())->getCanonicalDecl();
-        unsigned i = PV->getFunctionScopeIndex();
-
-        if (CallCtx && CallCtx->FunArgs &&
-            FD == CallCtx->AttrDecl->getCanonicalDecl()) {
-          // Substitute call arguments for references to function parameters
-          assert(i < CallCtx->NumArgs);
-          return buildSExpr(CallCtx->FunArgs[i], CallCtx->PrevCtx, NDeref);
-        }
-        // Map the param back to the param of the original function declaration.
-        makeNamedVar(FD->getParamDecl(i));
-        return 1;
-      }
-      // Not a function parameter -- just store the reference.
-      makeNamedVar(ND);
-      return 1;
-    } else if (isa<CXXThisExpr>(Exp)) {
-      // Substitute parent for 'this'
-      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 {
-        makeThis();
-        return 1;
-      }
-    } else if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) {
-      const NamedDecl *ND = ME->getMemberDecl();
-      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 (const 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.
-      const CXXMethodDecl *MD = CMCE->getMethodDecl()->getMostRecentDecl();
-      if (LockReturnedAttr* At = MD->getAttr<LockReturnedAttr>()) {
-        CallingContext LRCallCtx(CMCE->getMethodDecl());
-        LRCallCtx.SelfArg = CMCE->getImplicitObjectArgument();
-        LRCallCtx.SelfArrow = isCalleeArrow(CMCE->getCallee());
-        LRCallCtx.NumArgs = CMCE->getNumArgs();
-        LRCallCtx.FunArgs = CMCE->getArgs();
-        LRCallCtx.PrevCtx = CallCtx;
-        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) {
-        if (NDeref && isCalleeArrow(CMCE->getCallee()))
-          ++(*NDeref);
-        return buildSExpr(CMCE->getImplicitObjectArgument(), CallCtx, NDeref);
-      }
-      unsigned NumCallArgs = CMCE->getNumArgs();
-      unsigned Root = makeMCall(NumCallArgs, CMCE->getMethodDecl());
-      unsigned Sz = buildSExpr(CMCE->getImplicitObjectArgument(), CallCtx);
-      const Expr* const* CallArgs = CMCE->getArgs();
-      for (unsigned i = 0; i < NumCallArgs; ++i) {
-        Sz += buildSExpr(CallArgs[i], CallCtx);
-      }
-      NodeVec[Root].setSize(Sz + 1);
-      return Sz + 1;
-    } else if (const CallExpr *CE = dyn_cast<CallExpr>(Exp)) {
-      const FunctionDecl *FD = CE->getDirectCallee()->getMostRecentDecl();
-      if (LockReturnedAttr* At = FD->getAttr<LockReturnedAttr>()) {
-        CallingContext LRCallCtx(CE->getDirectCallee());
-        LRCallCtx.NumArgs = CE->getNumArgs();
-        LRCallCtx.FunArgs = CE->getArgs();
-        LRCallCtx.PrevCtx = CallCtx;
-        return buildSExpr(At->getArg(), &LRCallCtx);
-      }
-      // Treat smart pointers and iterators as pointers;
-      // ignore the * and -> operators.
-      if (const CXXOperatorCallExpr *OE = dyn_cast<CXXOperatorCallExpr>(CE)) {
-        OverloadedOperatorKind k = OE->getOperator();
-        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);
-        }
-      }
-      unsigned NumCallArgs = CE->getNumArgs();
-      unsigned Root = makeCall(NumCallArgs, nullptr);
-      unsigned Sz = buildSExpr(CE->getCallee(), CallCtx);
-      const Expr* const* CallArgs = CE->getArgs();
-      for (unsigned i = 0; i < NumCallArgs; ++i) {
-        Sz += buildSExpr(CallArgs[i], CallCtx);
-      }
-      NodeVec[Root].setSize(Sz+1);
-      return Sz+1;
-    } else if (const BinaryOperator *BOE = dyn_cast<BinaryOperator>(Exp)) {
-      unsigned Root = makeBinary();
-      unsigned Sz = buildSExpr(BOE->getLHS(), CallCtx);
-      Sz += buildSExpr(BOE->getRHS(), CallCtx);
-      NodeVec[Root].setSize(Sz);
-      return Sz;
-    } else if (const UnaryOperator *UOE = dyn_cast<UnaryOperator>(Exp)) {
-      // 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 (DeclRefExpr* DRE = dyn_cast<DeclRefExpr>(UOE->getSubExpr())) {
-          if (DRE->getDecl()->isCXXInstanceMember()) {
-            // This is a pointer-to-member expression, e.g. &MyClass::mu_.
-            // We interpret this syntax specially, as a wildcard.
-            unsigned Root = makeDot(DRE->getDecl(), false);
-            makeWildcard();
-            NodeVec[Root].setSize(2);
-            return 2;
-          }
-        }
-        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 (const ArraySubscriptExpr *ASE =
-               dyn_cast<ArraySubscriptExpr>(Exp)) {
-      unsigned Root = makeIndex();
-      unsigned Sz = buildSExpr(ASE->getBase(), CallCtx);
-      Sz += buildSExpr(ASE->getIdx(), CallCtx);
-      NodeVec[Root].setSize(Sz);
-      return Sz;
-    } else if (const AbstractConditionalOperator *CE =
-               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 (const ChooseExpr *CE = dyn_cast<ChooseExpr>(Exp)) {
-      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 (const CastExpr *CE = dyn_cast<CastExpr>(Exp)) {
-      return buildSExpr(CE->getSubExpr(), CallCtx, NDeref);
-    } else if (const ParenExpr *PE = dyn_cast<ParenExpr>(Exp)) {
-      return buildSExpr(PE->getSubExpr(), CallCtx, NDeref);
-    } else if (const ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Exp)) {
-      return buildSExpr(EWC->getSubExpr(), CallCtx, NDeref);
-    } else if (const CXXBindTemporaryExpr *E = dyn_cast<CXXBindTemporaryExpr>(Exp)) {
-      return buildSExpr(E->getSubExpr(), CallCtx, NDeref);
-    } else if (isa<CharacterLiteral>(Exp) ||
-               isa<CXXNullPtrLiteralExpr>(Exp) ||
-               isa<GNUNullExpr>(Exp) ||
-               isa<CXXBoolLiteralExpr>(Exp) ||
-               isa<FloatingLiteral>(Exp) ||
-               isa<ImaginaryLiteral>(Exp) ||
-               isa<IntegerLiteral>(Exp) ||
-               isa<StringLiteral>(Exp) ||
-               isa<ObjCStringLiteral>(Exp)) {
-      makeNop();
-      return 1;  // FIXME: Ignore literals for now
-    } else {
-      makeNop();
-      return 1;  // Ignore.  FIXME: mark as invalid 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 buildSExprFromExpr(const Expr *MutexExp, const Expr *DeclExp,
-                          const NamedDecl *D, VarDecl *SelfDecl = nullptr) {
-    CallingContext CallCtx(D);
-
-    if (MutexExp) {
-      if (const StringLiteral* SLit = dyn_cast<StringLiteral>(MutexExp)) {
-        if (SLit->getString() == StringRef("*"))
-          // The "*" expr is a universal lock, which essentially turns off
-          // checks until it is removed from the lockset.
-          makeUniversal();
-        else
-          // Ignore other string literals for now.
-          makeNop();
-        return;
-      }
-    }
-
-    // If we are processing a raw attribute expression, with no substitutions.
-    if (!DeclExp) {
-      buildSExpr(MutexExp, nullptr);
-      return;
-    }
-
-    // Examine DeclExp to find SelfArg and FunArgs, which are used to substitute
-    // for formal parameters when we call buildMutexID later.
-    if (const MemberExpr *ME = dyn_cast<MemberExpr>(DeclExp)) {
-      CallCtx.SelfArg   = ME->getBase();
-      CallCtx.SelfArrow = ME->isArrow();
-    } else if (const CXXMemberCallExpr *CE =
-               dyn_cast<CXXMemberCallExpr>(DeclExp)) {
-      CallCtx.SelfArg   = CE->getImplicitObjectArgument();
-      CallCtx.SelfArrow = isCalleeArrow(CE->getCallee());
-      CallCtx.NumArgs   = CE->getNumArgs();
-      CallCtx.FunArgs   = CE->getArgs();
-    } else if (const CallExpr *CE = dyn_cast<CallExpr>(DeclExp)) {
-      CallCtx.NumArgs = CE->getNumArgs();
-      CallCtx.FunArgs = CE->getArgs();
-    } else if (const CXXConstructExpr *CE =
-               dyn_cast<CXXConstructExpr>(DeclExp)) {
-      CallCtx.SelfArg = nullptr;  // Will be set below
-      CallCtx.NumArgs = CE->getNumArgs();
-      CallCtx.FunArgs = CE->getArgs();
-    } else if (D && isa<CXXDestructorDecl>(D)) {
-      // There's no such thing as a "destructor call" in the AST.
-      CallCtx.SelfArg = DeclExp;
-    }
+class TILPrinter :
+  public til::PrettyPrinter<TILPrinter, llvm::raw_ostream> {};
 
-    // Hack to handle constructors, where self cannot be recovered from
-    // the expression.
-    if (SelfDecl && !CallCtx.SelfArg) {
-      DeclRefExpr SelfDRE(SelfDecl, false, SelfDecl->getType(), VK_LValue,
-                          SelfDecl->getLocation());
-      CallCtx.SelfArg = &SelfDRE;
-
-      // If the attribute has no arguments, then assume the argument is "this".
-      if (!MutexExp)
-        buildSExpr(CallCtx.SelfArg, nullptr);
-      else  // For most attributes.
-        buildSExpr(MutexExp, &CallCtx);
-      return;
-    }
 
-    // If the attribute has no arguments, then assume the argument is "this".
-    if (!MutexExp)
-      buildSExpr(CallCtx.SelfArg, nullptr);
-    else  // For most attributes.
-      buildSExpr(MutexExp, &CallCtx);
-  }
+/// Issue a warning about an invalid lock expression
+static void warnInvalidLock(ThreadSafetyHandler &Handler,
+                            const Expr *MutexExp, const NamedDecl *D,
+                            const Expr *DeclExp, StringRef Kind) {
+  SourceLocation Loc;
+  if (DeclExp)
+    Loc = DeclExp->getExprLoc();
 
-  /// \brief Get index of next sibling of node i.
-  unsigned getNextSibling(unsigned i) const {
-    return i + NodeVec[i].size();
-  }
+  // FIXME: add a note about the attribute location in MutexExp or D
+  if (Loc.isValid())
+    Handler.handleInvalidLockExp(Kind, Loc);
+}
 
-public:
-  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.
-  SExpr(const Expr *MutexExp, const Expr *DeclExp, const NamedDecl *D,
-        VarDecl *SelfDecl = nullptr) {
-    buildSExprFromExpr(MutexExp, DeclExp, D, SelfDecl);
-  }
+// Various helper functions on til::SExpr
+namespace sx {
 
-  /// Return true if this is a valid decl sequence.
-  /// Caller must call this by hand after construction to handle errors.
-  bool isValid() const {
-    return !NodeVec.empty();
-  }
+bool isUniversal(const til::SExpr *E) {
+  return isa<til::Wildcard>(E);
+}
 
-  bool shouldIgnore() const {
-    // Nop is a mutex that we have decided to deliberately ignore.
-    assert(NodeVec.size() > 0 && "Invalid Mutex");
-    return NodeVec[0].kind() == EOP_Nop;
-  }
+bool equals(const til::SExpr *E1, const til::SExpr *E2) {
+  return til::EqualsComparator::compareExprs(E1, E2);
+}
 
-  bool isUniversal() const {
-    assert(NodeVec.size() > 0 && "Invalid Mutex");
-    return NodeVec[0].kind() == EOP_Universal;
+const til::SExpr* ignorePtrCasts(const til::SExpr *E) {
+  if (auto *CE = dyn_cast<til::Cast>(E)) {
+    if (CE->castOpcode() == til::CAST_objToPtr)
+      return CE->expr();
   }
+  return E;
+}
 
-  /// Issue a warning about an invalid lock expression
-  static void warnInvalidLock(ThreadSafetyHandler &Handler,
-                              const Expr *MutexExp, const Expr *DeclExp,
-                              const NamedDecl *D, StringRef Kind) {
-    SourceLocation Loc;
-    if (DeclExp)
-      Loc = DeclExp->getExprLoc();
+bool matches(const til::SExpr *E1, const til::SExpr *E2) {
+  // We treat a top-level wildcard as the "univsersal" lock.
+  // It matches everything for the purpose of checking locks, but not
+  // for unlocking them.
+  if (isa<til::Wildcard>(E1))
+    return isa<til::Wildcard>(E2);
+  if (isa<til::Wildcard>(E2))
+    return isa<til::Wildcard>(E1);
 
-    // FIXME: add a note about the attribute location in MutexExp or D
-    if (Loc.isValid())
-      Handler.handleInvalidLockExp(Kind, Loc);
-  }
+  return til::MatchComparator::compareExprs(E1, E2);
+}
 
-  bool operator==(const SExpr &other) const {
-    return NodeVec == other.NodeVec;
-  }
+bool partiallyMatches(const til::SExpr *E1, const til::SExpr *E2) {
+  auto *PE1 = dyn_cast_or_null<til::Project>(E1);
+  if (!PE1)
+    return false;
+  auto *PE2 = dyn_cast_or_null<til::Project>(E2);
+  if (!PE2)
+    return false;
+  return PE1->clangDecl() == PE2->clangDecl();
+}
 
-  bool operator!=(const SExpr &other) const {
-    return !(*this == other);
-  }
+std::string toString(const til::SExpr *E) {
+  std::stringstream ss;
+  til::StdPrinter::print(E, ss);
+  return ss.str();
+}
 
-  bool matches(const SExpr &Other, unsigned i = 0, unsigned j = 0) const {
-    if (NodeVec[i].matches(Other.NodeVec[j])) {
-      unsigned ni = NodeVec[i].arity();
-      unsigned nj = Other.NodeVec[j].arity();
-      unsigned n = (ni < nj) ? ni : nj;
-      bool Result = true;
-      unsigned ci = i+1;  // first child of i
-      unsigned cj = j+1;  // first child of j
-      for (unsigned k = 0; k < n;
-           ++k, ci=getNextSibling(ci), cj = Other.getNextSibling(cj)) {
-        Result = Result && matches(Other, ci, cj);
-      }
-      return Result;
-    }
-    return false;
-  }
+bool shouldIgnore(const til::SExpr *E) {
+  if (!E)
+    return true;
+  // Trap mutex expressions like nullptr, or 0.
+  // Any literal value is nonsense.
+  if (isa<til::Literal>(E))
+    return true;
+  return false;
+}
 
-  // A partial match between a.mu and b.mu returns true a and b have the same
-  // type (and thus mu refers to the same mutex declaration), regardless of
-  // whether a and b are different objects or not.
-  bool partiallyMatches(const SExpr &Other) const {
-    if (NodeVec[0].kind() == EOP_Dot)
-      return NodeVec[0].matches(Other.NodeVec[0]);
-    return false;
-  }
+}  // end namespace sx
 
-  /// \brief Pretty print a lock expression for use in error messages.
-  std::string toString(unsigned i = 0) const {
-    assert(isValid());
-    if (i >= NodeVec.size())
-      return "";
-
-    const SExprNode* N = &NodeVec[i];
-    switch (N->kind()) {
-      case EOP_Nop:
-        return "_";
-      case EOP_Wildcard:
-        return "(?)";
-      case EOP_Universal:
-        return "*";
-      case EOP_This:
-        return "this";
-      case EOP_NVar:
-      case EOP_LVar: {
-        return N->getNamedDecl()->getNameAsString();
-      }
-      case EOP_Dot: {
-        if (NodeVec[i+1].kind() == EOP_Wildcard) {
-          std::string S = "&";
-          S += N->getNamedDecl()->getQualifiedNameAsString();
-          return S;
-        }
-        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 = getNextSibling(i+1);
-        for (unsigned k=0; k<NumArgs; ++k, ci = getNextSibling(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 = getNextSibling(i+1);
-        for (unsigned k=0; k<NumArgs; ++k, ci = getNextSibling(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 = getNextSibling(ci)) {
-          S += toString(ci);
-          if (j+1 < NumChildren) S += "#";
-        }
-        S += ")";
-        return S;
-      }
-    }
-    return "";
-  }
-};
 
 /// \brief A short list of SExprs
-class MutexIDList : public SmallVector<SExpr, 3> {
+class MutexIDList : public SmallVector<const til::SExpr*, 3> {
 public:
   /// \brief Push M onto list, but discard duplicates.
-  void push_back_nodup(const SExpr& M) {
-    if (end() == std::find(begin(), end(), M))
-      push_back(M);
+  void push_back_nodup(const til::SExpr *E) {
+    iterator It = std::find_if(begin(), end(), [=](const til::SExpr *E2) {
+      return sx::equals(E, E2);
+    });
+    if (It == end())
+      push_back(E);
   }
 };
 
@@ -735,15 +160,15 @@ struct LockData {
   LockKind LKind;
   bool     Asserted;           // for asserted locks
   bool     Managed;            // for ScopedLockable objects
-  SExpr    UnderlyingMutex;    // for ScopedLockable objects
+  const til::SExpr* UnderlyingMutex;    // for ScopedLockable objects
 
   LockData(SourceLocation AcquireLoc, LockKind LKind, bool M=false,
            bool Asrt=false)
     : AcquireLoc(AcquireLoc), LKind(LKind), Asserted(Asrt), Managed(M),
-      UnderlyingMutex(Decl::EmptyShell())
+      UnderlyingMutex(nullptr)
   {}
 
-  LockData(SourceLocation AcquireLoc, LockKind LKind, const SExpr &Mu)
+  LockData(SourceLocation AcquireLoc, LockKind LKind, const til::SExpr *Mu)
     : AcquireLoc(AcquireLoc), LKind(LKind), Asserted(false), Managed(false),
       UnderlyingMutex(Mu)
   {}
@@ -771,10 +196,10 @@ struct LockData {
 /// in the program execution.  Currently, this is information regarding a lock
 /// that is held at that point.
 struct FactEntry {
-  SExpr    MutID;
+  const til::SExpr *MutID;
   LockData LDat;
 
-  FactEntry(const SExpr& M, const LockData& L)
+  FactEntry(const til::SExpr* M, const LockData& L)
     : MutID(M), LDat(L)
   { }
 };
@@ -789,8 +214,8 @@ private:
   std::vector<FactEntry> Facts;
 
 public:
-  FactID newLock(const SExpr& M, const LockData& L) {
-    Facts.push_back(FactEntry(M,L));
+  FactID newLock(const til::SExpr *M, const LockData& L) {
+    Facts.push_back(FactEntry(M, L));
     return static_cast<unsigned short>(Facts.size() - 1);
   }
 
@@ -824,66 +249,67 @@ public:
 
   bool isEmpty() const { return FactIDs.size() == 0; }
 
-  FactID addLock(FactManager& FM, const SExpr& M, const LockData& L) {
+  FactID addLock(FactManager& FM, const til::SExpr *M, const LockData& L) {
     FactID F = FM.newLock(M, L);
     FactIDs.push_back(F);
     return F;
   }
 
-  bool removeLock(FactManager& FM, const SExpr& M) {
+  bool removeLock(FactManager& FM, const til::SExpr *M) {
     unsigned n = FactIDs.size();
     if (n == 0)
       return false;
 
     for (unsigned i = 0; i < n-1; ++i) {
-      if (FM[FactIDs[i]].MutID.matches(M)) {
+      if (sx::matches(FM[FactIDs[i]].MutID, M)) {
         FactIDs[i] = FactIDs[n-1];
         FactIDs.pop_back();
         return true;
       }
     }
-    if (FM[FactIDs[n-1]].MutID.matches(M)) {
+    if (sx::matches(FM[FactIDs[n-1]].MutID, M)) {
       FactIDs.pop_back();
       return true;
     }
     return false;
   }
 
-  iterator findLockIter(FactManager &FM, const SExpr &M) {
+  iterator findLockIter(FactManager &FM, const til::SExpr *M) {
     return std::find_if(begin(), end(), [&](FactID ID) {
-      return FM[ID].MutID.matches(M);
+      return sx::matches(FM[ID].MutID, M);
     });
   }
 
-  LockData *findLock(FactManager &FM, const SExpr &M) const {
+  LockData *findLock(FactManager &FM, const til::SExpr *M) const {
     auto I = std::find_if(begin(), end(), [&](FactID ID) {
-      return FM[ID].MutID.matches(M);
+      return sx::matches(FM[ID].MutID, M);
     });
 
     return I != end() ? &FM[*I].LDat : nullptr;
   }
 
-  LockData *findLockUniv(FactManager &FM, const SExpr &M) const {
+  LockData *findLockUniv(FactManager &FM, const til::SExpr *M) const {
     auto I = std::find_if(begin(), end(), [&](FactID ID) -> bool {
-      const SExpr &Expr = FM[ID].MutID;
-      return Expr.isUniversal() || Expr.matches(M);
+      const til::SExpr *E = FM[ID].MutID;
+      return sx::isUniversal(E) || sx::matches(E, M);
     });
 
     return I != end() ? &FM[*I].LDat : nullptr;
   }
 
-  FactEntry *findPartialMatch(FactManager &FM, const SExpr &M) const {
+  FactEntry *findPartialMatch(FactManager &FM, const til::SExpr *M) const {
     auto I = std::find_if(begin(), end(), [&](FactID ID) {
-      return FM[ID].MutID.partiallyMatches(M);
+      return sx::partiallyMatches(FM[ID].MutID, M);
     });
 
     return I != end() ? &FM[*I] : nullptr;
   }
 };
 
+
 /// A Lockset maps each SExpr (defined above) to information about how it has
 /// been locked.
-typedef llvm::ImmutableMap<SExpr, LockData> Lockset;
+typedef llvm::ImmutableMap<til::SExpr*, LockData> Lockset;
 typedef llvm::ImmutableMap<const NamedDecl*, unsigned> LocalVarContext;
 
 class LocalVariableMap;
@@ -1408,18 +834,24 @@ static void findBlockLocations(CFG *CFGraph,
 class ThreadSafetyAnalyzer {
   friend class BuildLockset;
 
+  llvm::BumpPtrAllocator Bpa;
+  threadSafety::til::MemRegionRef Arena;
+  threadSafety::SExprBuilder SxBuilder;
+
   ThreadSafetyHandler       &Handler;
   LocalVariableMap          LocalVarMap;
   FactManager               FactMan;
   std::vector<CFGBlockInfo> BlockInfo;
 
 public:
-  ThreadSafetyAnalyzer(ThreadSafetyHandler &H) : Handler(H) {}
+  ThreadSafetyAnalyzer(ThreadSafetyHandler &H)
+     : Arena(&Bpa), SxBuilder(Arena), Handler(H) {}
 
-  void addLock(FactSet &FSet, const SExpr &Mutex, const LockData &LDat,
+  void addLock(FactSet &FSet, const til::SExpr *Mutex, const LockData &LDat,
                StringRef DiagKind);
-  void removeLock(FactSet &FSet, const SExpr &Mutex, SourceLocation UnlockLoc,
-                  bool FullyRemove, LockKind Kind, StringRef DiagKind);
+  void removeLock(FactSet &FSet, const til::SExpr *Mutex,
+                  SourceLocation UnlockLoc, bool FullyRemove, LockKind Kind,
+                  StringRef DiagKind);
 
   template <typename AttrType>
   void getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, Expr *Exp,
@@ -1533,16 +965,16 @@ ClassifyDiagnostic(const AttrTy *A) {
 /// \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 SExpr &Mutex,
+void ThreadSafetyAnalyzer::addLock(FactSet &FSet, const til::SExpr *Mutex,
                                    const LockData &LDat, StringRef DiagKind) {
   // FIXME: deal with acquired before/after annotations.
   // FIXME: Don't always warn when we have support for reentrant locks.
-  if (Mutex.shouldIgnore())
+  if (sx::shouldIgnore(Mutex))
     return;
 
   if (FSet.findLock(FactMan, Mutex)) {
     if (!LDat.Asserted)
-      Handler.handleDoubleLock(DiagKind, Mutex.toString(), LDat.AcquireLoc);
+      Handler.handleDoubleLock(DiagKind, sx::toString(Mutex), LDat.AcquireLoc);
   } else {
     FSet.addLock(FactMan, Mutex, LDat);
   }
@@ -1552,28 +984,28 @@ void ThreadSafetyAnalyzer::addLock(FactSet &FSet, const SExpr &Mutex,
 /// \brief Remove a lock from the lockset, warning if the lock is not there.
 /// \param Mutex 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 SExpr &Mutex,
+void ThreadSafetyAnalyzer::removeLock(FactSet &FSet, const til::SExpr *Mutex,
                                       SourceLocation UnlockLoc,
                                       bool FullyRemove, LockKind ReceivedKind,
                                       StringRef DiagKind) {
-  if (Mutex.shouldIgnore())
+  if (sx::shouldIgnore(Mutex))
     return;
 
   const LockData *LDat = FSet.findLock(FactMan, Mutex);
   if (!LDat) {
-    Handler.handleUnmatchedUnlock(DiagKind, Mutex.toString(), UnlockLoc);
+    Handler.handleUnmatchedUnlock(DiagKind, sx::toString(Mutex), UnlockLoc);
     return;
   }
 
   // Generic lock removal doesn't care about lock kind mismatches, but
   // otherwise diagnose when the lock kinds are mismatched.
   if (ReceivedKind != LK_Generic && LDat->LKind != ReceivedKind) {
-    Handler.handleIncorrectUnlockKind(DiagKind, Mutex.toString(), LDat->LKind,
-                                      ReceivedKind, UnlockLoc);
+    Handler.handleIncorrectUnlockKind(DiagKind, sx::toString(Mutex),
+                                      LDat->LKind, ReceivedKind, UnlockLoc);
     return;
   }
 
-  if (LDat->UnderlyingMutex.isValid()) {
+  if (LDat->UnderlyingMutex) {
     // This is scoped lockable object, which manages the real mutex.
     if (FullyRemove) {
       // We're destroying the managing object.
@@ -1585,7 +1017,7 @@ void ThreadSafetyAnalyzer::removeLock(FactSet &FSet, const SExpr &Mutex,
       // managing object.  Warn on dual release.
       if (!FSet.findLock(FactMan, LDat->UnderlyingMutex)) {
         Handler.handleUnmatchedUnlock(
-            DiagKind, LDat->UnderlyingMutex.toString(), UnlockLoc);
+            DiagKind, sx::toString(LDat->UnderlyingMutex), UnlockLoc);
       }
       FSet.removeLock(FactMan, LDat->UnderlyingMutex);
       return;
@@ -1603,20 +1035,25 @@ void ThreadSafetyAnalyzer::getMutexIDs(MutexIDList &Mtxs, AttrType *Attr,
                                        VarDecl *SelfDecl) {
   if (Attr->args_size() == 0) {
     // The mutex held is the "this" object.
-    SExpr Mu(nullptr, Exp, D, SelfDecl);
-    if (!Mu.isValid())
-      SExpr::warnInvalidLock(Handler, nullptr, Exp, D,
-                             ClassifyDiagnostic(Attr));
-    else
+    til::SExpr *Mu = SxBuilder.translateAttrExpr(nullptr, D, Exp, SelfDecl);
+    if (Mu && isa<til::Undefined>(Mu)) {
+       warnInvalidLock(Handler, nullptr, D, Exp, ClassifyDiagnostic(Attr));
+       return;
+    }
+    //else
+    if (Mu)
       Mtxs.push_back_nodup(Mu);
     return;
   }
 
   for (const auto *Arg : Attr->args()) {
-    SExpr Mu(Arg, Exp, D, SelfDecl);
-    if (!Mu.isValid())
-      SExpr::warnInvalidLock(Handler, Arg, Exp, D, ClassifyDiagnostic(Attr));
-    else
+    til::SExpr *Mu = SxBuilder.translateAttrExpr(Arg, D, Exp, SelfDecl);
+    if (Mu && isa<til::Undefined>(Mu)) {
+       warnInvalidLock(Handler, nullptr, D, Exp, ClassifyDiagnostic(Attr));
+       return;
+    }
+    //else
+    if (Mu)
       Mtxs.push_back_nodup(Mu);
   }
 }
@@ -1845,11 +1282,12 @@ void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, const Expr *Exp,
                                       StringRef DiagKind) {
   LockKind LK = getLockKindFromAccessKind(AK);
 
-  SExpr Mutex(MutexExp, Exp, D);
-  if (!Mutex.isValid()) {
-    SExpr::warnInvalidLock(Analyzer->Handler, MutexExp, Exp, D, DiagKind);
+  til::SExpr *Mutex = Analyzer->SxBuilder.translateAttrExpr(MutexExp, D, Exp);
+  if (!Mutex) {
+    // TODO: invalid locks?
+    // warnInvalidLock(Analyzer->Handler, MutexExp, D, Exp, DiagKind);
     return;
-  } else if (Mutex.shouldIgnore()) {
+  } else if (sx::shouldIgnore(Mutex)) {
     return;
   }
 
@@ -1861,38 +1299,42 @@ void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, const Expr *Exp,
     if (FEntry) {
       // Warn that there's no precise match.
       LDat = &FEntry->LDat;
-      std::string PartMatchStr = FEntry->MutID.toString();
+      std::string PartMatchStr = sx::toString(FEntry->MutID);
       StringRef   PartMatchName(PartMatchStr);
-      Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, Mutex.toString(),
+      Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK,
+                                           sx::toString(Mutex),
                                            LK, Exp->getExprLoc(),
                                            &PartMatchName);
     } else {
       // Warn that there's no match at all.
-      Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, Mutex.toString(),
+      Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK,
+                                           sx::toString(Mutex),
                                            LK, Exp->getExprLoc());
     }
     NoError = false;
   }
   // Make sure the mutex we found is the right kind.
   if (NoError && LDat && !LDat->isAtLeast(LK))
-    Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, Mutex.toString(), LK,
-                                         Exp->getExprLoc());
+    Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK,
+                                         sx::toString(Mutex),
+                                         LK, Exp->getExprLoc());
 }
 
 /// \brief Warn if the LSet contains the given lock.
 void BuildLockset::warnIfMutexHeld(const NamedDecl *D, const Expr *Exp,
                                    Expr *MutexExp,
                                    StringRef DiagKind) {
-  SExpr Mutex(MutexExp, Exp, D);
-  if (!Mutex.isValid()) {
-    SExpr::warnInvalidLock(Analyzer->Handler, MutexExp, Exp, D, DiagKind);
+  til::SExpr *Mutex = Analyzer->SxBuilder.translateAttrExpr(MutexExp, D, Exp);
+  if (!Mutex) {
+    // TODO: invalid locks?
+    // warnInvalidLock(Analyzer->Handler, MutexExp, D, Exp, DiagKind);
     return;
   }
 
   LockData* LDat = FSet.findLock(Analyzer->FactMan, Mutex);
   if (LDat)
     Analyzer->Handler.handleFunExcludesLock(
-        DiagKind, D->getNameAsString(), Mutex.toString(), Exp->getExprLoc());
+        DiagKind, D->getNameAsString(), sx::toString(Mutex), Exp->getExprLoc());
 }
 
 /// \brief Checks guarded_by and pt_guarded_by attributes.
@@ -2085,7 +1527,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());
-    SExpr SMutex(&DRE, nullptr, nullptr);
+    til::SExpr *SMutex = Analyzer->SxBuilder.translateAttrExpr(&DRE, nullptr);
 
     for (const auto &M : ExclusiveLocksToAdd)
       Analyzer->addLock(FSet, SMutex, LockData(MLoc, LK_Exclusive, M),
@@ -2093,6 +1535,12 @@ void BuildLockset::handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD) {
     for (const auto &M : SharedLocksToAdd)
       Analyzer->addLock(FSet, SMutex, LockData(MLoc, LK_Shared, M),
                         CapDiagKind);
+
+    // handle corner case where the underlying mutex is invalid
+    if (ExclusiveLocksToAdd.size() == 0 && SharedLocksToAdd.size() == 0) {
+      Analyzer->addLock(FSet, SMutex, LockData(MLoc, LK_Exclusive),
+                        CapDiagKind);
+    }
   }
 
   // Remove locks.
@@ -2254,14 +1702,14 @@ void ThreadSafetyAnalyzer::intersectAndWarn(FactSet &FSet1,
 
   // Find locks in FSet2 that conflict or are not in FSet1, and warn.
   for (const auto &Fact : FSet2) {
-    const SExpr &FSet2Mutex = FactMan[Fact].MutID;
+    const til::SExpr *FSet2Mutex = FactMan[Fact].MutID;
     const LockData &LDat2 = FactMan[Fact].LDat;
     FactSet::iterator I1 = FSet1.findLockIter(FactMan, FSet2Mutex);
 
     if (I1 != FSet1.end()) {
       const LockData* LDat1 = &FactMan[*I1].LDat;
       if (LDat1->LKind != LDat2.LKind) {
-        Handler.handleExclusiveAndShared("mutex", FSet2Mutex.toString(),
+        Handler.handleExclusiveAndShared("mutex", sx::toString(FSet2Mutex),
                                          LDat2.AcquireLoc, LDat1->AcquireLoc);
         if (Modify && LDat1->LKind != LK_Exclusive) {
           // Take the exclusive lock, which is the one in FSet2.
@@ -2273,40 +1721,42 @@ void ThreadSafetyAnalyzer::intersectAndWarn(FactSet &FSet1,
         *I1 = Fact;
       }
     } else {
-      if (LDat2.UnderlyingMutex.isValid()) {
+      if (LDat2.UnderlyingMutex) {
         if (FSet2.findLock(FactMan, LDat2.UnderlyingMutex)) {
           // 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("mutex",
-                                            LDat2.UnderlyingMutex.toString(),
+                                            sx::toString(LDat2.UnderlyingMutex),
                                             LDat2.AcquireLoc, JoinLoc, LEK1);
         }
       }
-      else if (!LDat2.Managed && !FSet2Mutex.isUniversal() && !LDat2.Asserted)
-        Handler.handleMutexHeldEndOfScope("mutex", FSet2Mutex.toString(),
+      else if (!LDat2.Managed && !sx::isUniversal(FSet2Mutex) &&
+               !LDat2.Asserted)
+        Handler.handleMutexHeldEndOfScope("mutex", sx::toString(FSet2Mutex),
                                           LDat2.AcquireLoc, JoinLoc, LEK1);
     }
   }
 
   // Find locks in FSet1 that are not in FSet2, and remove them.
   for (const auto &Fact : FSet1Orig) {
-    const SExpr &FSet1Mutex = FactMan[Fact].MutID;
+    const til::SExpr *FSet1Mutex = FactMan[Fact].MutID;
     const LockData &LDat1 = FactMan[Fact].LDat;
 
     if (!FSet2.findLock(FactMan, FSet1Mutex)) {
-      if (LDat1.UnderlyingMutex.isValid()) {
+      if (LDat1.UnderlyingMutex) {
         if (FSet1Orig.findLock(FactMan, LDat1.UnderlyingMutex)) {
           // 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("mutex",
-                                            LDat1.UnderlyingMutex.toString(),
+                                            sx::toString(LDat1.UnderlyingMutex),
                                             LDat1.AcquireLoc, JoinLoc, LEK1);
         }
       }
-      else if (!LDat1.Managed && !FSet1Mutex.isUniversal() && !LDat1.Asserted)
-        Handler.handleMutexHeldEndOfScope("mutex", FSet1Mutex.toString(),
+      else if (!LDat1.Managed && !sx::isUniversal(FSet1Mutex) &&
+               !LDat1.Asserted)
+        Handler.handleMutexHeldEndOfScope("mutex", sx::toString(FSet1Mutex),
                                           LDat1.AcquireLoc, JoinLoc, LEK2);
       if (Modify)
         FSet1.removeLock(FactMan, FSet1Mutex);
@@ -2618,11 +2068,6 @@ void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) {
                    false);
 }
 
-} // end anonymous namespace
-
-
-namespace clang {
-namespace thread_safety {
 
 /// \brief Check a function's CFG for thread-safety violations.
 ///
@@ -2647,4 +2092,4 @@ LockKind getLockKindFromAccessKind(AccessKind AK) {
   llvm_unreachable("Unknown AccessKind");
 }
 
-}} // end namespace clang::thread_safety
+}} // end namespace clang::threadSafety
diff --git a/clang/lib/Analysis/ThreadSafetyCommon.cpp b/clang/lib/Analysis/ThreadSafetyCommon.cpp
index da88b78..56feba7 100644
--- a/clang/lib/Analysis/ThreadSafetyCommon.cpp
+++ b/clang/lib/Analysis/ThreadSafetyCommon.cpp
@@ -91,6 +91,102 @@ til::SCFG *SExprBuilder::buildCFG(CFGWalker &Walker) {
 }
 
 
+
+inline bool isCalleeArrow(const Expr *E) {
+  const MemberExpr *ME = dyn_cast<MemberExpr>(E->IgnoreParenCasts());
+  return ME ? ME->isArrow() : false;
+}
+
+
+/// \brief Translate a clang expression in an attribute to a til::SExpr.
+/// Constructs the context from D, DeclExp, and SelfDecl.
+///
+/// \param AttrExp The expression to translate.
+/// \param D       The declaration to which the attribute is attached.
+/// \param DeclExp An expression involving the Decl to which the attribute
+///                is attached.  E.g. the call to a function.
+til::SExpr *SExprBuilder::translateAttrExpr(const Expr *AttrExp,
+                                            const NamedDecl *D,
+                                            const Expr *DeclExp,
+                                            VarDecl *SelfDecl) {
+  // If we are processing a raw attribute expression, with no substitutions.
+  if (!DeclExp)
+    return translateAttrExpr(AttrExp, nullptr);
+
+  CallingContext Ctx(nullptr, D);
+
+  // Examine DeclExp to find SelfArg and FunArgs, which are used to substitute
+  // for formal parameters when we call buildMutexID later.
+  if (const MemberExpr *ME = dyn_cast<MemberExpr>(DeclExp)) {
+    Ctx.SelfArg   = ME->getBase();
+    Ctx.SelfArrow = ME->isArrow();
+  } else if (const CXXMemberCallExpr *CE =
+             dyn_cast<CXXMemberCallExpr>(DeclExp)) {
+    Ctx.SelfArg   = CE->getImplicitObjectArgument();
+    Ctx.SelfArrow = isCalleeArrow(CE->getCallee());
+    Ctx.NumArgs   = CE->getNumArgs();
+    Ctx.FunArgs   = CE->getArgs();
+  } else if (const CallExpr *CE = dyn_cast<CallExpr>(DeclExp)) {
+    Ctx.NumArgs = CE->getNumArgs();
+    Ctx.FunArgs = CE->getArgs();
+  } else if (const CXXConstructExpr *CE =
+             dyn_cast<CXXConstructExpr>(DeclExp)) {
+    Ctx.SelfArg = nullptr;  // Will be set below
+    Ctx.NumArgs = CE->getNumArgs();
+    Ctx.FunArgs = CE->getArgs();
+  } else if (D && isa<CXXDestructorDecl>(D)) {
+    // There's no such thing as a "destructor call" in the AST.
+    Ctx.SelfArg = DeclExp;
+  }
+
+  // Hack to handle constructors, where self cannot be recovered from
+  // the expression.
+  if (SelfDecl && !Ctx.SelfArg) {
+    DeclRefExpr SelfDRE(SelfDecl, false, SelfDecl->getType(), VK_LValue,
+                        SelfDecl->getLocation());
+    Ctx.SelfArg = &SelfDRE;
+
+    // If the attribute has no arguments, then assume the argument is "this".
+    if (!AttrExp)
+      return translateAttrExpr(Ctx.SelfArg, nullptr);
+    else  // For most attributes.
+      return translateAttrExpr(AttrExp, &Ctx);
+  }
+
+  // If the attribute has no arguments, then assume the argument is "this".
+  if (!AttrExp)
+    return translateAttrExpr(Ctx.SelfArg, nullptr);
+  else  // For most attributes.
+    return translateAttrExpr(AttrExp, &Ctx);
+}
+
+
+/// \brief Translate a clang expression in an attribute to a til::SExpr.
+// This assumes a CallingContext has already been created.
+til::SExpr *SExprBuilder::translateAttrExpr(const Expr *AttrExp,
+                                            CallingContext *Ctx) {
+  if (const StringLiteral* SLit = dyn_cast_or_null<StringLiteral>(AttrExp)) {
+    if (SLit->getString() == StringRef("*"))
+      // The "*" expr is a universal lock, which essentially turns off
+      // checks until it is removed from the lockset.
+      return new (Arena) til::Wildcard();
+    else
+      // Ignore other string literals for now.
+      return nullptr;
+  }
+
+  til::SExpr *E = translate(AttrExp, Ctx);
+
+  // Hack to deal with smart pointers -- strip off top-level pointer casts.
+  if (auto *CE = dyn_cast_or_null<til::Cast>(E)) {
+    if (CE->castOpcode() == til::CAST_objToPtr)
+      return CE->expr();
+  }
+  return E;
+}
+
+
+
 // Translate a clang statement or expression to a TIL expression.
 // Also performs substitution of variables; Ctx provides the context.
 // Dispatches on the type of S.
@@ -125,9 +221,10 @@ til::SExpr *SExprBuilder::translate(const Stmt *S, CallingContext *Ctx) {
   case Stmt::ArraySubscriptExprClass:
     return translateArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Ctx);
   case Stmt::ConditionalOperatorClass:
-    return translateConditionalOperator(cast<ConditionalOperator>(S), Ctx);
+    return translateAbstractConditionalOperator(
+             cast<ConditionalOperator>(S), Ctx);
   case Stmt::BinaryConditionalOperatorClass:
-    return translateBinaryConditionalOperator(
+    return translateAbstractConditionalOperator(
              cast<BinaryConditionalOperator>(S), Ctx);
 
   // We treat these as no-ops
@@ -162,6 +259,7 @@ til::SExpr *SExprBuilder::translate(const Stmt *S, CallingContext *Ctx) {
 }
 
 
+
 til::SExpr *SExprBuilder::translateDeclRefExpr(const DeclRefExpr *DRE,
                                                CallingContext *Ctx) {
   const ValueDecl *VD = cast<ValueDecl>(DRE->getDecl()->getCanonicalDecl());
@@ -197,17 +295,72 @@ til::SExpr *SExprBuilder::translateCXXThisExpr(const CXXThisExpr *TE,
 }
 
 
+const ValueDecl *getValueDeclFromSExpr(const til::SExpr *E) {
+  if (auto *V = dyn_cast<til::Variable>(E))
+    return V->clangDecl();
+  if (auto *P = dyn_cast<til::Project>(E))
+    return P->clangDecl();
+  if (auto *L = dyn_cast<til::LiteralPtr>(E))
+    return L->clangDecl();
+  return 0;
+}
+
+bool hasCppPointerType(const til::SExpr *E) {
+  auto *VD = getValueDeclFromSExpr(E);
+  if (VD && VD->getType()->isPointerType())
+    return true;
+  if (auto *C = dyn_cast<til::Cast>(E))
+    return C->castOpcode() == til::CAST_objToPtr;
+
+  return false;
+}
+
+
+// Grab the very first declaration of virtual method D
+const CXXMethodDecl* getFirstVirtualDecl(const CXXMethodDecl *D) {
+  while (true) {
+    D = D->getCanonicalDecl();
+    CXXMethodDecl::method_iterator I = D->begin_overridden_methods(),
+                                   E = D->end_overridden_methods();
+    if (I == E)
+      return D;  // Method does not override anything
+    D = *I;      // FIXME: this does not work with multiple inheritance.
+  }
+  return nullptr;
+}
+
 til::SExpr *SExprBuilder::translateMemberExpr(const MemberExpr *ME,
                                               CallingContext *Ctx) {
-  til::SExpr *E = translate(ME->getBase(), Ctx);
-  E = new (Arena) til::SApply(E);
-  return new (Arena) til::Project(E, ME->getMemberDecl());
+  til::SExpr *BE = translate(ME->getBase(), Ctx);
+  til::SExpr *E  = new (Arena) til::SApply(BE);
+
+  const ValueDecl *D = ME->getMemberDecl();
+  if (auto *VD = dyn_cast<CXXMethodDecl>(D))
+    D = getFirstVirtualDecl(VD);
+
+  til::Project *P = new (Arena) til::Project(E, D);
+  if (hasCppPointerType(BE))
+    P->setArrow(true);
+  return P;
 }
 
 
 til::SExpr *SExprBuilder::translateCallExpr(const CallExpr *CE,
-                                            CallingContext *Ctx) {
-  // TODO -- Lock returned
+                                            CallingContext *Ctx,
+                                            const Expr *SelfE) {
+  if (CapabilityExprMode) {
+    // Handle LOCK_RETURNED
+    const FunctionDecl *FD = CE->getDirectCallee()->getMostRecentDecl();
+    if (LockReturnedAttr* At = FD->getAttr<LockReturnedAttr>()) {
+      CallingContext LRCallCtx(Ctx);
+      LRCallCtx.AttrDecl = CE->getDirectCallee();
+      LRCallCtx.SelfArg  = SelfE;
+      LRCallCtx.NumArgs  = CE->getNumArgs();
+      LRCallCtx.FunArgs  = CE->getArgs();
+      return translateAttrExpr(At->getArg(), &LRCallCtx);
+    }
+  }
+
   til::SExpr *E = translate(CE->getCallee(), Ctx);
   for (const auto *Arg : CE->arguments()) {
     til::SExpr *A = translate(Arg, Ctx);
@@ -219,12 +372,31 @@ til::SExpr *SExprBuilder::translateCallExpr(const CallExpr *CE,
 
 til::SExpr *SExprBuilder::translateCXXMemberCallExpr(
     const CXXMemberCallExpr *ME, CallingContext *Ctx) {
-  return translateCallExpr(cast<CallExpr>(ME), Ctx);
+  if (CapabilityExprMode) {
+    // Ignore calls to get() on smart pointers.
+    if (ME->getMethodDecl()->getNameAsString() == "get" &&
+        ME->getNumArgs() == 0) {
+      auto *E = translate(ME->getImplicitObjectArgument(), Ctx);
+      return new (Arena) til::Cast(til::CAST_objToPtr, E);
+      // return E;
+    }
+  }
+  return translateCallExpr(cast<CallExpr>(ME), Ctx,
+                           ME->getImplicitObjectArgument());
 }
 
 
 til::SExpr *SExprBuilder::translateCXXOperatorCallExpr(
     const CXXOperatorCallExpr *OCE, CallingContext *Ctx) {
+  if (CapabilityExprMode) {
+    // Ignore operator * and operator -> on smart pointers.
+    OverloadedOperatorKind k = OCE->getOperator();
+    if (k == OO_Star || k == OO_Arrow) {
+      auto *E = translate(OCE->getArg(0), Ctx);
+      return new (Arena) til::Cast(til::CAST_objToPtr, E);
+      // return E;
+    }
+  }
   return translateCallExpr(cast<CallExpr>(OCE), Ctx);
 }
 
@@ -238,8 +410,23 @@ til::SExpr *SExprBuilder::translateUnaryOperator(const UnaryOperator *UO,
   case UO_PreDec:
     return new (Arena) til::Undefined(UO);
 
+  case UO_AddrOf: {
+    if (CapabilityExprMode) {
+      // interpret &Graph::mu_ as an existential.
+      if (DeclRefExpr* DRE = dyn_cast<DeclRefExpr>(UO->getSubExpr())) {
+        if (DRE->getDecl()->isCXXInstanceMember()) {
+          // This is a pointer-to-member expression, e.g. &MyClass::mu_.
+          // We interpret this syntax specially, as a wildcard.
+          auto *W = new (Arena) til::Wildcard();
+          return new (Arena) til::Project(W, DRE->getDecl());
+        }
+      }
+    }
+    // otherwise, & is a no-op
+    return translate(UO->getSubExpr(), Ctx);
+  }
+
   // We treat these as no-ops
-  case UO_AddrOf:
   case UO_Deref:
   case UO_Plus:
     return translate(UO->getSubExpr(), Ctx);
@@ -360,7 +547,9 @@ til::SExpr *SExprBuilder::translateCastExpr(const CastExpr *CE,
         return E0;
     }
     til::SExpr *E0 = translate(CE->getSubExpr(), Ctx);
-    return new (Arena) til::Load(E0);
+    return E0;
+    // FIXME!! -- get Load working properly
+    // return new (Arena) til::Load(E0);
   }
   case CK_NoOp:
   case CK_DerivedToBase:
@@ -373,6 +562,8 @@ til::SExpr *SExprBuilder::translateCastExpr(const CastExpr *CE,
   default: {
     // FIXME: handle different kinds of casts.
     til::SExpr *E0 = translate(CE->getSubExpr(), Ctx);
+    if (CapabilityExprMode)
+      return E0;
     return new (Arena) til::Cast(til::CAST_none, E0);
   }
   }
@@ -389,15 +580,12 @@ SExprBuilder::translateArraySubscriptExpr(const ArraySubscriptExpr *E,
 
 
 til::SExpr *
-SExprBuilder::translateConditionalOperator(const ConditionalOperator *C,
-                                           CallingContext *Ctx) {
-  return new (Arena) til::Undefined(C);
-}
-
-
-til::SExpr *SExprBuilder::translateBinaryConditionalOperator(
-    const BinaryConditionalOperator *C, CallingContext *Ctx) {
-  return new (Arena) til::Undefined(C);
+SExprBuilder::translateAbstractConditionalOperator(
+    const AbstractConditionalOperator *CO, CallingContext *Ctx) {
+  auto *C = translate(CO->getCond(), Ctx);
+  auto *T = translate(CO->getTrueExpr(), Ctx);
+  auto *E = translate(CO->getFalseExpr(), Ctx);
+  return new (Arena) til::IfThenElse(C, T, E);
 }
 
 
@@ -430,9 +618,7 @@ SExprBuilder::translateDeclStmt(const DeclStmt *S, CallingContext *Ctx) {
 // If E is trivial returns E.
 til::SExpr *SExprBuilder::addStatement(til::SExpr* E, const Stmt *S,
                                        const ValueDecl *VD) {
-  if (!E)
-    return nullptr;
-  if (til::ThreadSafetyTIL::isTrivial(E))
+  if (!E || !CurrentBB || til::ThreadSafetyTIL::isTrivial(E))
     return E;
 
   til::Variable *V = new (Arena) til::Variable(E, VD);
@@ -631,7 +817,6 @@ void SExprBuilder::enterCFG(CFG *Cfg, const NamedDecl *D,
     BB->reserveInstructions(B->size());
     BlockMap[B->getBlockID()] = BB;
   }
-  CallCtx.reset(new SExprBuilder::CallingContext(D));
 
   CurrentBB = lookupBlock(&Cfg->getEntry());
   auto Parms = isa<ObjCMethodDecl>(D) ? cast<ObjCMethodDecl>(D)->parameters()
@@ -697,7 +882,7 @@ void SExprBuilder::enterCFGBlockBody(const CFGBlock *B) {
 
 
 void SExprBuilder::handleStatement(const Stmt *S) {
-  til::SExpr *E = translate(S, CallCtx.get());
+  til::SExpr *E = translate(S, nullptr);
   addStatement(E, S);
 }
 
@@ -730,7 +915,7 @@ void SExprBuilder::exitCFGBlockBody(const CFGBlock *B) {
     CurrentBB->setTerminator(Tm);
   }
   else if (N == 2) {
-    til::SExpr *C = translate(B->getTerminatorCondition(true), CallCtx.get());
+    til::SExpr *C = translate(B->getTerminatorCondition(true), nullptr);
     til::BasicBlock *BB1 = *It ? lookupBlock(*It) : nullptr;
     ++It;
     til::BasicBlock *BB2 = *It ? lookupBlock(*It) : nullptr;
@@ -775,18 +960,15 @@ void SExprBuilder::exitCFG(const CFGBlock *Last) {
 }
 
 
-
-class TILPrinter : public til::PrettyPrinter<TILPrinter, llvm::raw_ostream> {};
-
-
+/*
 void printSCFG(CFGWalker &Walker) {
   llvm::BumpPtrAllocator Bpa;
   til::MemRegionRef Arena(&Bpa);
-  SExprBuilder builder(Arena);
-  til::SCFG *Cfg = builder.buildCFG(Walker);
-  TILPrinter::print(Cfg, llvm::errs());
+  SExprBuilder SxBuilder(Arena);
+  til::SCFG *Scfg = SxBuilder.buildCFG(Walker);
+  TILPrinter::print(Scfg, llvm::errs());
 }
-
+*/
 
 
 } // end namespace threadSafety
diff --git a/clang/lib/Analysis/ThreadSafetyTIL.cpp b/clang/lib/Analysis/ThreadSafetyTIL.cpp
index f67cbb9..0bb7d4c 100644
--- a/clang/lib/Analysis/ThreadSafetyTIL.cpp
+++ b/clang/lib/Analysis/ThreadSafetyTIL.cpp
@@ -88,10 +88,42 @@ void SCFG::renumberVars() {
 
 
 
+// If E is a variable, then trace back through any aliases or redundant
+// Phi nodes to find the canonical definition.
+const SExpr *getCanonicalVal(const SExpr *E) {
+  while (auto *V = dyn_cast<Variable>(E)) {
+    const SExpr *D;
+    do {
+      if (V->kind() != Variable::VK_Let)
+        return V;
+      D = V->definition();
+      auto *V2 = dyn_cast<Variable>(D);
+      if (V2)
+        V = V2;
+      else
+        break;
+    } while (true);
+
+    if (ThreadSafetyTIL::isTrivial(D))
+      return D;
+
+    if (const Phi *Ph = dyn_cast<Phi>(D)) {
+      if (Ph->status() == Phi::PH_SingleVal) {
+        E = Ph->values()[0];
+        continue;
+      }
+    }
+    return V;
+  }
+  return E;
+}
+
+
 
 // If E is a variable, then trace back through any aliases or redundant
 // Phi nodes to find the canonical definition.
-SExpr *getCanonicalVal(SExpr *E) {
+// The non-const version will simplify incomplete Phi nodes.
+SExpr *simplifyToCanonicalVal(SExpr *E) {
   while (auto *V = dyn_cast<Variable>(E)) {
     SExpr *D;
     do {
@@ -123,6 +155,7 @@ SExpr *getCanonicalVal(SExpr *E) {
 }
 
 
+
 // Trace the arguments of an incomplete Phi node to see if they have the same
 // canonical definition.  If so, mark the Phi node as redundant.
 // getCanonicalVal() will recursively call simplifyIncompletePhi().
@@ -132,9 +165,9 @@ void simplifyIncompleteArg(Variable *V, til::Phi *Ph) {
   // eliminate infinite recursion -- assume that this node is not redundant.
   Ph->setStatus(Phi::PH_MultiVal);
 
-  SExpr *E0 = getCanonicalVal(Ph->values()[0]);
+  SExpr *E0 = simplifyToCanonicalVal(Ph->values()[0]);
   for (unsigned i=1, n=Ph->values().size(); i<n; ++i) {
-    SExpr *Ei = getCanonicalVal(Ph->values()[i]);
+    SExpr *Ei = simplifyToCanonicalVal(Ph->values()[i]);
     if (Ei == V)
       continue;  // Recursive reference to itself.  Don't count.
     if (Ei != E0) {