3 files changed, 423 insertions, 8 deletions

diff --git a/clang/lib/Analysis/CMakeLists.txt b/clang/lib/Analysis/CMakeLists.txt
index 9630bc0be0a..f3e4358974c 100644
--- a/clang/lib/Analysis/CMakeLists.txt
+++ b/clang/lib/Analysis/CMakeLists.txt
@@ -22,6 +22,7 @@ add_clang_library(clangAnalysis
   PseudoConstantAnalysis.cpp
   ReachableCode.cpp
   ScanfFormatString.cpp
+  ThreadSafetyCommon.cpp
   ThreadSafety.cpp
   UninitializedValues.cpp
 
diff --git a/clang/lib/Analysis/ThreadSafety.cpp b/clang/lib/Analysis/ThreadSafety.cpp
index fd804eba992..9cc2a55f0af 100644
--- a/clang/lib/Analysis/ThreadSafety.cpp
+++ b/clang/lib/Analysis/ThreadSafety.cpp
@@ -10,18 +10,20 @@
 // A intra-procedural analysis for thread safety (e.g. deadlocks and race
 // conditions), based off of an annotation system.
 //
-// See http://clang.llvm.org/docs/LanguageExtensions.html#thread-safety-annotation-checking
+// See http://clang.llvm.org/docs/ThreadSafetyAnalysis.html
 // for more information.
 //
 //===----------------------------------------------------------------------===//
 
-#include "clang/Analysis/Analyses/ThreadSafety.h"
 #include "clang/AST/Attr.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/ExprCXX.h"
 #include "clang/AST/StmtCXX.h"
 #include "clang/AST/StmtVisitor.h"
 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
+#include "clang/Analysis/Analyses/ThreadSafety.h"
+#include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
+#include "clang/Analysis/Analyses/ThreadSafetyCommon.h"
 #include "clang/Analysis/AnalysisContext.h"
 #include "clang/Analysis/CFG.h"
 #include "clang/Analysis/CFGStmtMap.h"
@@ -2362,16 +2364,21 @@ inline bool neverReturns(const CFGBlock* B) {
 /// at the end of each block, and issue warnings for thread safety violations.
 /// Each block in the CFG is traversed exactly once.
 void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) {
-  CFG *CFGraph = AC.getCFG();
-  if (!CFGraph) return;
-  const NamedDecl *D = dyn_cast_or_null<NamedDecl>(AC.getDecl());
+  // TODO: this whole function needs be rewritten as a visitor for CFGWalker.
+  // For now, we just use the walker to set things up.
+  threadSafety::CFGWalker walker;
+  if (!walker.init(AC))
+    return;
 
   // AC.dumpCFG(true);
+  // threadSafety::printSCFG(walker);
+
+  CFG *CFGraph = walker.CFGraph;
+  const NamedDecl *D = walker.FDecl;
 
-  if (!D)
-    return;  // Ignore anonymous functions for now.
   if (D->hasAttr<NoThreadSafetyAnalysisAttr>())
     return;
+
   // FIXME: Do something a bit more intelligent inside constructor and
   // destructor code.  Constructors and destructors must assume unique access
   // to 'this', so checks on member variable access is disabled, but we should
@@ -2387,7 +2394,7 @@ void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) {
   // We need to explore the CFG via a "topological" ordering.
   // That way, we will be guaranteed to have information about required
   // predecessor locksets when exploring a new block.
-  PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>();
+  PostOrderCFGView *SortedGraph = walker.SortedGraph;
   PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph);
 
   // Mark entry block as reachable
diff --git a/clang/lib/Analysis/ThreadSafetyCommon.cpp b/clang/lib/Analysis/ThreadSafetyCommon.cpp
new file mode 100644
index 00000000000..cd416e57c95
--- /dev/null
+++ b/clang/lib/Analysis/ThreadSafetyCommon.cpp
@@ -0,0 +1,407 @@
+//===- ThreadSafetyCommon.cpp ----------------------------------*- C++ --*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Implementation of the interfaces declared in ThreadSafetyCommon.h
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/AST/Attr.h"
+#include "clang/AST/DeclCXX.h"
+#include "clang/AST/ExprCXX.h"
+#include "clang/AST/StmtCXX.h"
+#include "clang/AST/StmtVisitor.h"
+#include "clang/Analysis/Analyses/PostOrderCFGView.h"
+#include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
+#include "clang/Analysis/Analyses/ThreadSafetyCommon.h"
+#include "clang/Analysis/AnalysisContext.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Analysis/CFGStmtMap.h"
+#include "clang/Basic/OperatorKinds.h"
+#include "clang/Basic/SourceLocation.h"
+#include "clang/Basic/SourceManager.h"
+#include "llvm/ADT/BitVector.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/ImmutableMap.h"
+#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/StringRef.h"
+#include <vector>
+
+
+namespace clang {
+namespace threadSafety {
+
+typedef SExprBuilder::CallingContext CallingContext;
+
+
+til::SExpr *SExprBuilder::lookupStmt(const Stmt *S) {
+  if (!SMap)
+    return 0;
+  auto It = SMap->find(S);
+  if (It != SMap->end())
+    return It->second;
+  return 0;
+}
+
+void SExprBuilder::insertStmt(const Stmt *S, til::Variable *V) {
+  SMap->insert(std::make_pair(S, V));
+}
+
+
+// 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.
+til::SExpr *SExprBuilder::translate(const Stmt *S, CallingContext *Ctx) {
+  // Check if S has already been translated and cached.
+  // This handles the lookup of SSA names for DeclRefExprs here.
+  if (til::SExpr *E = lookupStmt(S))
+    return E;
+
+  switch (S->getStmtClass()) {
+  case Stmt::DeclRefExprClass:
+    return translateDeclRefExpr(cast<DeclRefExpr>(S), Ctx);
+  case Stmt::CXXThisExprClass:
+    return translateCXXThisExpr(cast<CXXThisExpr>(S), Ctx);
+  case Stmt::MemberExprClass:
+    return translateMemberExpr(cast<MemberExpr>(S), Ctx);
+  case Stmt::CallExprClass:
+    return translateCallExpr(cast<CallExpr>(S), Ctx);
+  case Stmt::CXXMemberCallExprClass:
+    return translateCXXMemberCallExpr(cast<CXXMemberCallExpr>(S), Ctx);
+  case Stmt::CXXOperatorCallExprClass:
+    return translateCXXOperatorCallExpr(cast<CXXOperatorCallExpr>(S), Ctx);
+  case Stmt::UnaryOperatorClass:
+    return translateUnaryOperator(cast<UnaryOperator>(S), Ctx);
+  case Stmt::BinaryOperatorClass:
+    return translateBinaryOperator(cast<BinaryOperator>(S), Ctx);
+
+  case Stmt::ArraySubscriptExprClass:
+    return translateArraySubscriptExpr(cast<ArraySubscriptExpr>(S), Ctx);
+  case Stmt::ConditionalOperatorClass:
+    return translateConditionalOperator(cast<ConditionalOperator>(S), Ctx);
+  case Stmt::BinaryConditionalOperatorClass:
+    return translateBinaryConditionalOperator(
+             cast<BinaryConditionalOperator>(S), Ctx);
+
+  // We treat these as no-ops
+  case Stmt::ParenExprClass:
+    return translate(cast<ParenExpr>(S)->getSubExpr(), Ctx);
+  case Stmt::ExprWithCleanupsClass:
+    return translate(cast<ExprWithCleanups>(S)->getSubExpr(), Ctx);
+  case Stmt::CXXBindTemporaryExprClass:
+    return translate(cast<CXXBindTemporaryExpr>(S)->getSubExpr(), Ctx);
+
+  // Collect all literals
+  case Stmt::CharacterLiteralClass:
+  case Stmt::CXXNullPtrLiteralExprClass:
+  case Stmt::GNUNullExprClass:
+  case Stmt::CXXBoolLiteralExprClass:
+  case Stmt::FloatingLiteralClass:
+  case Stmt::ImaginaryLiteralClass:
+  case Stmt::IntegerLiteralClass:
+  case Stmt::StringLiteralClass:
+  case Stmt::ObjCStringLiteralClass:
+    return new (Arena) til::Literal(cast<Expr>(S));
+  default:
+    break;
+  }
+  if (const CastExpr *CE = dyn_cast<CastExpr>(S))
+    return translateCastExpr(CE, Ctx);
+
+  return new (Arena) til::Undefined(S);
+}
+
+
+til::SExpr *SExprBuilder::translateDeclRefExpr(const DeclRefExpr *DRE,
+                                               CallingContext *Ctx) {
+  const ValueDecl *VD = cast<ValueDecl>(DRE->getDecl()->getCanonicalDecl());
+
+  // Function parameters require substitution and/or renaming.
+  if (const ParmVarDecl *PV = dyn_cast_or_null<ParmVarDecl>(VD)) {
+    const FunctionDecl *FD =
+        cast<FunctionDecl>(PV->getDeclContext())->getCanonicalDecl();
+    unsigned I = PV->getFunctionScopeIndex();
+
+    if (Ctx && Ctx->FunArgs && FD == Ctx->AttrDecl->getCanonicalDecl()) {
+      // Substitute call arguments for references to function parameters
+      assert(I < Ctx->NumArgs);
+      return translate(Ctx->FunArgs[I], Ctx->Prev);
+    }
+    // Map the param back to the param of the original function declaration
+    // for consistent comparisons.
+    VD = FD->getParamDecl(I);
+  }
+
+  // For non-local variables, treat it as a referenced to a named object.
+  return new (Arena) til::LiteralPtr(VD);
+}
+
+
+til::SExpr *SExprBuilder::translateCXXThisExpr(const CXXThisExpr *TE,
+                                               CallingContext *Ctx) {
+  // Substitute for 'this'
+  if (Ctx && Ctx->SelfArg)
+    return translate(Ctx->SelfArg, Ctx->Prev);
+  assert(SelfVar && "We have no variable for 'this'!");
+  return SelfVar;
+}
+
+
+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 *SExprBuilder::translateCallExpr(const CallExpr *CE,
+                                            CallingContext *Ctx) {
+  // TODO -- Lock returned
+  til::SExpr *E = translate(CE->getCallee(), Ctx);
+  for (unsigned I = 0, N = CE->getNumArgs(); I < N; ++I) {
+    til::SExpr *A = translate(CE->getArg(I), Ctx);
+    E = new (Arena) til::Apply(E, A);
+  }
+  return new (Arena) til::Call(E, CE);
+}
+
+
+til::SExpr *SExprBuilder::translateCXXMemberCallExpr(
+    const CXXMemberCallExpr *ME, CallingContext *Ctx) {
+  return translateCallExpr(cast<CallExpr>(ME), Ctx);
+}
+
+
+til::SExpr *SExprBuilder::translateCXXOperatorCallExpr(
+    const CXXOperatorCallExpr *OCE, CallingContext *Ctx) {
+  return translateCallExpr(cast<CallExpr>(OCE), Ctx);
+}
+
+
+til::SExpr *SExprBuilder::translateUnaryOperator(const UnaryOperator *UO,
+                                                 CallingContext *Ctx) {
+  switch (UO->getOpcode()) {
+  case UO_PostInc:
+  case UO_PostDec:
+  case UO_PreInc:
+  case UO_PreDec:
+    return new (Arena) til::Undefined(UO);
+
+  // We treat these as no-ops
+  case UO_AddrOf:
+  case UO_Deref:
+  case UO_Plus:
+    return translate(UO->getSubExpr(), Ctx);
+
+  case UO_Minus:
+  case UO_Not:
+  case UO_LNot:
+  case UO_Real:
+  case UO_Imag:
+  case UO_Extension: {
+    til::SExpr *E0 = translate(UO->getSubExpr(), Ctx);
+    return new (Arena) til::UnaryOp(UO->getOpcode(), E0);
+  }
+  }
+  return new (Arena) til::Undefined(UO);
+}
+
+til::SExpr *SExprBuilder::translateBinaryOperator(const BinaryOperator *BO,
+                                                  CallingContext *Ctx) {
+  switch (BO->getOpcode()) {
+  case BO_PtrMemD:
+  case BO_PtrMemI:
+    return new (Arena) til::Undefined(BO);
+
+  case BO_Mul:
+  case BO_Div:
+  case BO_Rem:
+  case BO_Add:
+  case BO_Sub:
+  case BO_Shl:
+  case BO_Shr:
+  case BO_LT:
+  case BO_GT:
+  case BO_LE:
+  case BO_GE:
+  case BO_EQ:
+  case BO_NE:
+  case BO_And:
+  case BO_Xor:
+  case BO_Or:
+  case BO_LAnd:
+  case BO_LOr: {
+    til::SExpr *E0 = translate(BO->getLHS(), Ctx);
+    til::SExpr *E1 = translate(BO->getRHS(), Ctx);
+    return new (Arena) til::BinaryOp(BO->getOpcode(), E0, E1);
+  }
+  case BO_Assign: {
+    til::SExpr *E0 = translate(BO->getLHS(), Ctx);
+    til::SExpr *E1 = translate(BO->getRHS(), Ctx);
+    return new (Arena) til::Store(E0, E1);
+  }
+  case BO_MulAssign:
+  case BO_DivAssign:
+  case BO_RemAssign:
+  case BO_AddAssign:
+  case BO_SubAssign:
+  case BO_ShlAssign:
+  case BO_ShrAssign:
+  case BO_AndAssign:
+  case BO_XorAssign:
+  case BO_OrAssign:
+    return new (Arena) til::Undefined(BO);
+
+  case BO_Comma:
+    // TODO: handle LHS
+    return translate(BO->getRHS(), Ctx);
+  }
+
+  return new (Arena) til::Undefined(BO);
+}
+
+
+til::SExpr *SExprBuilder::translateCastExpr(const CastExpr *CE,
+                                            CallingContext *Ctx) {
+  til::SExpr *E0 = translate(CE->getSubExpr(), Ctx);
+
+  clang::CastKind K = CE->getCastKind();
+  switch (K) {
+  case CK_LValueToRValue:
+    return new (Arena) til::Load(E0);
+
+  case CK_NoOp:
+  case CK_DerivedToBase:
+  case CK_UncheckedDerivedToBase:
+  case CK_ArrayToPointerDecay:
+  case CK_FunctionToPointerDecay:
+    return E0;
+
+  default:
+    return new (Arena) til::Cast(K, E0);
+  }
+}
+
+
+til::SExpr *SExprBuilder::translateArraySubscriptExpr(
+    const ArraySubscriptExpr *E, CallingContext *Ctx) {
+  return new (Arena) til::Undefined(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);
+}
+
+
+// Build a complete SCFG from a clang CFG.
+class SCFGBuilder : public CFGVisitor {
+public:
+  // return true if E should be included in the SCFG
+  bool includeExpr(til::SExpr* E) {
+    if (!E)
+      return false;
+    if (E->opcode() == til::COP_Variable)
+      return false;
+    if (E->opcode() == til::COP_LiteralPtr)
+      return false;
+    return true;
+  }
+
+  // Enter the CFG for Decl D, and perform any initial setup operations.
+  void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {
+    Scfg = new til::SCFG(Arena, Cfg->getNumBlockIDs());
+    CallCtx = new SExprBuilder::CallingContext(D);
+  }
+
+  // Enter a CFGBlock.
+  void enterCFGBlock(const CFGBlock *B) {
+    CurrentBB = new til::BasicBlock(Arena, 0, B->size());
+    CurrentBB->setBlockID(CurrentBlockID);
+    CurrentVarID = 0;
+    Scfg->add(CurrentBB);
+  }
+
+  // Process an ordinary statement.
+  void handleStatement(const Stmt *S) {
+    til::SExpr *E = BuildEx.translate(S, CallCtx);
+    if (includeExpr(E)) {
+      til::Variable *V = new til::Variable(til::Variable::VK_Let, E);
+      V->setID(CurrentBlockID, CurrentVarID++);
+      CurrentBB->addInstr(V);
+      BuildEx.insertStmt(S, V);
+    }
+  }
+
+  // Process a destructor call
+  void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {}
+
+  // Process a successor edge.
+  void handleSuccessor(const CFGBlock *Succ) {}
+
+  // Process a successor back edge to a previously visited block.
+  void handleSuccessorBackEdge(const CFGBlock *Succ) {}
+
+  // Leave a CFGBlock.
+  void exitCFGBlock(const CFGBlock *B) {
+    CurrentBlockID++;
+    CurrentBB = 0;
+  }
+
+  // Leave the CFG, and perform any final cleanup operations.
+  void exitCFG(const CFGBlock *Last) {}
+
+  SCFGBuilder(til::MemRegionRef A)
+      : Arena(A), Scfg(0), CurrentBB(0), CurrentBlockID(0),
+        BuildEx(A, new SExprBuilder::StatementMap())
+  { }
+
+  til::SCFG *getCFG() const { return Scfg; }
+
+private:
+  til::MemRegionRef Arena;
+  til::SCFG *Scfg;
+  til::BasicBlock *CurrentBB;
+  unsigned CurrentBlockID;
+  unsigned CurrentVarID;
+
+  SExprBuilder BuildEx;
+  SExprBuilder::CallingContext *CallCtx;
+};
+
+
+
+class LLVMPrinter :
+    public til::TILPrettyPrinter<LLVMPrinter, llvm::raw_ostream> {
+};
+
+
+void printSCFG(CFGWalker &walker) {
+  llvm::BumpPtrAllocator Bpa;
+  til::MemRegionRef Arena(&Bpa);
+  SCFGBuilder builder(Arena);
+  // CFGVisitor visitor;
+  walker.walk(builder);
+  LLVMPrinter::print(builder.getCFG(), llvm::errs());
+}
+
+
+
+} // end namespace threadSafety
+
+} // end namespace clang