1 files changed, 520 insertions, 0 deletions
diff --git a/clang-r353983/include/clang/Analysis/Analyses/ThreadSafetyCommon.h b/clang-r353983/include/clang/Analysis/Analyses/ThreadSafetyCommon.h
new file mode 100644
index 00000000..4a58fe87
--- /dev/null
+++ b/clang-r353983/include/clang/Analysis/Analyses/ThreadSafetyCommon.h
@@ -0,0 +1,520 @@
+//===- ThreadSafetyCommon.h -------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// Parts of thread safety analysis that are not specific to thread safety
+// itself have been factored into classes here, where they can be potentially
+// used by other analyses.  Currently these include:
+//
+// * Generalize clang CFG visitors.
+// * Conversion of the clang CFG to SSA form.
+// * Translation of clang Exprs to TIL SExprs
+//
+// UNDER CONSTRUCTION.  USE AT YOUR OWN RISK.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H
+#define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H
+
+#include "clang/AST/Decl.h"
+#include "clang/Analysis/Analyses/PostOrderCFGView.h"
+#include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
+#include "clang/Analysis/Analyses/ThreadSafetyTraverse.h"
+#include "clang/Analysis/Analyses/ThreadSafetyUtil.h"
+#include "clang/Analysis/AnalysisDeclContext.h"
+#include "clang/Analysis/CFG.h"
+#include "clang/Basic/LLVM.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Casting.h"
+#include <sstream>
+#include <string>
+#include <utility>
+#include <vector>
+
+namespace clang {
+
+class AbstractConditionalOperator;
+class ArraySubscriptExpr;
+class BinaryOperator;
+class CallExpr;
+class CastExpr;
+class CXXDestructorDecl;
+class CXXMemberCallExpr;
+class CXXOperatorCallExpr;
+class CXXThisExpr;
+class DeclRefExpr;
+class DeclStmt;
+class Expr;
+class MemberExpr;
+class Stmt;
+class UnaryOperator;
+
+namespace threadSafety {
+
+// Various helper functions on til::SExpr
+namespace sx {
+
+inline bool equals(const til::SExpr *E1, const til::SExpr *E2) {
+  return til::EqualsComparator::compareExprs(E1, E2);
+}
+
+inline 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);
+
+  return til::MatchComparator::compareExprs(E1, E2);
+}
+
+inline bool partiallyMatches(const til::SExpr *E1, const til::SExpr *E2) {
+  const auto *PE1 = dyn_cast_or_null<til::Project>(E1);
+  if (!PE1)
+    return false;
+  const auto *PE2 = dyn_cast_or_null<til::Project>(E2);
+  if (!PE2)
+    return false;
+  return PE1->clangDecl() == PE2->clangDecl();
+}
+
+inline std::string toString(const til::SExpr *E) {
+  std::stringstream ss;
+  til::StdPrinter::print(E, ss);
+  return ss.str();
+}
+
+}  // namespace sx
+
+// This class defines the interface of a clang CFG Visitor.
+// CFGWalker will invoke the following methods.
+// Note that methods are not virtual; the visitor is templatized.
+class CFGVisitor {
+  // Enter the CFG for Decl D, and perform any initial setup operations.
+  void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {}
+
+  // Enter a CFGBlock.
+  void enterCFGBlock(const CFGBlock *B) {}
+
+  // Returns true if this visitor implements handlePredecessor
+  bool visitPredecessors() { return true; }
+
+  // Process a predecessor edge.
+  void handlePredecessor(const CFGBlock *Pred) {}
+
+  // Process a successor back edge to a previously visited block.
+  void handlePredecessorBackEdge(const CFGBlock *Pred) {}
+
+  // Called just before processing statements.
+  void enterCFGBlockBody(const CFGBlock *B) {}
+
+  // Process an ordinary statement.
+  void handleStatement(const Stmt *S) {}
+
+  // Process a destructor call
+  void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {}
+
+  // Called after all statements have been handled.
+  void exitCFGBlockBody(const CFGBlock *B) {}
+
+  // Return true
+  bool visitSuccessors() { return true; }
+
+  // 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) {}
+
+  // Leave the CFG, and perform any final cleanup operations.
+  void exitCFG(const CFGBlock *Last) {}
+};
+
+// Walks the clang CFG, and invokes methods on a given CFGVisitor.
+class CFGWalker {
+public:
+  CFGWalker() = default;
+
+  // Initialize the CFGWalker.  This setup only needs to be done once, even
+  // if there are multiple passes over the CFG.
+  bool init(AnalysisDeclContext &AC) {
+    ACtx = &AC;
+    CFGraph = AC.getCFG();
+    if (!CFGraph)
+      return false;
+
+    // Ignore anonymous functions.
+    if (!dyn_cast_or_null<NamedDecl>(AC.getDecl()))
+      return false;
+
+    SortedGraph = AC.getAnalysis<PostOrderCFGView>();
+    if (!SortedGraph)
+      return false;
+
+    return true;
+  }
+
+  // Traverse the CFG, calling methods on V as appropriate.
+  template <class Visitor>
+  void walk(Visitor &V) {
+    PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph);
+
+    V.enterCFG(CFGraph, getDecl(), &CFGraph->getEntry());
+
+    for (const auto *CurrBlock : *SortedGraph) {
+      VisitedBlocks.insert(CurrBlock);
+
+      V.enterCFGBlock(CurrBlock);
+
+      // Process predecessors, handling back edges last
+      if (V.visitPredecessors()) {
+        SmallVector<CFGBlock*, 4> BackEdges;
+        // Process successors
+        for (CFGBlock::const_pred_iterator SI = CurrBlock->pred_begin(),
+                                           SE = CurrBlock->pred_end();
+             SI != SE; ++SI) {
+          if (*SI == nullptr)
+            continue;
+
+          if (!VisitedBlocks.alreadySet(*SI)) {
+            BackEdges.push_back(*SI);
+            continue;
+          }
+          V.handlePredecessor(*SI);
+        }
+
+        for (auto *Blk : BackEdges)
+          V.handlePredecessorBackEdge(Blk);
+      }
+
+      V.enterCFGBlockBody(CurrBlock);
+
+      // Process statements
+      for (const auto &BI : *CurrBlock) {
+        switch (BI.getKind()) {
+        case CFGElement::Statement:
+          V.handleStatement(BI.castAs<CFGStmt>().getStmt());
+          break;
+
+        case CFGElement::AutomaticObjectDtor: {
+          CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>();
+          auto *DD = const_cast<CXXDestructorDecl *>(
+              AD.getDestructorDecl(ACtx->getASTContext()));
+          auto *VD = const_cast<VarDecl *>(AD.getVarDecl());
+          V.handleDestructorCall(VD, DD);
+          break;
+        }
+        default:
+          break;
+        }
+      }
+
+      V.exitCFGBlockBody(CurrBlock);
+
+      // Process successors, handling back edges first.
+      if (V.visitSuccessors()) {
+        SmallVector<CFGBlock*, 8> ForwardEdges;
+
+        // Process successors
+        for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
+                                           SE = CurrBlock->succ_end();
+             SI != SE; ++SI) {
+          if (*SI == nullptr)
+            continue;
+
+          if (!VisitedBlocks.alreadySet(*SI)) {
+            ForwardEdges.push_back(*SI);
+            continue;
+          }
+          V.handleSuccessorBackEdge(*SI);
+        }
+
+        for (auto *Blk : ForwardEdges)
+          V.handleSuccessor(Blk);
+      }
+
+      V.exitCFGBlock(CurrBlock);
+    }
+    V.exitCFG(&CFGraph->getExit());
+  }
+
+  const CFG *getGraph() const { return CFGraph; }
+  CFG *getGraph() { return CFGraph; }
+
+  const NamedDecl *getDecl() const {
+    return dyn_cast<NamedDecl>(ACtx->getDecl());
+  }
+
+  const PostOrderCFGView *getSortedGraph() const { return SortedGraph; }
+
+private:
+  CFG *CFGraph = nullptr;
+  AnalysisDeclContext *ACtx = nullptr;
+  PostOrderCFGView *SortedGraph = nullptr;
+};
+
+// TODO: move this back into ThreadSafety.cpp
+// This is specific to thread safety.  It is here because
+// translateAttrExpr needs it, but that should be moved too.
+class CapabilityExpr {
+private:
+  /// The capability expression.
+  const til::SExpr* CapExpr;
+
+  /// True if this is a negative capability.
+  bool Negated;
+
+public:
+  CapabilityExpr(const til::SExpr *E, bool Neg) : CapExpr(E), Negated(Neg) {}
+
+  const til::SExpr* sexpr() const { return CapExpr; }
+  bool negative() const { return Negated; }
+
+  CapabilityExpr operator!() const {
+    return CapabilityExpr(CapExpr, !Negated);
+  }
+
+  bool equals(const CapabilityExpr &other) const {
+    return (Negated == other.Negated) && sx::equals(CapExpr, other.CapExpr);
+  }
+
+  bool matches(const CapabilityExpr &other) const {
+    return (Negated == other.Negated) && sx::matches(CapExpr, other.CapExpr);
+  }
+
+  bool matchesUniv(const CapabilityExpr &CapE) const {
+    return isUniversal() || matches(CapE);
+  }
+
+  bool partiallyMatches(const CapabilityExpr &other) const {
+    return (Negated == other.Negated) &&
+            sx::partiallyMatches(CapExpr, other.CapExpr);
+  }
+
+  const ValueDecl* valueDecl() const {
+    if (Negated || CapExpr == nullptr)
+      return nullptr;
+    if (const auto *P = dyn_cast<til::Project>(CapExpr))
+      return P->clangDecl();
+    if (const auto *P = dyn_cast<til::LiteralPtr>(CapExpr))
+      return P->clangDecl();
+    return nullptr;
+  }
+
+  std::string toString() const {
+    if (Negated)
+      return "!" + sx::toString(CapExpr);
+    return sx::toString(CapExpr);
+  }
+
+  bool shouldIgnore() const { return CapExpr == nullptr; }
+
+  bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); }
+
+  bool isUniversal() const { return sexpr() && isa<til::Wildcard>(sexpr()); }
+};
+
+// Translate clang::Expr to til::SExpr.
+class SExprBuilder {
+public:
+  /// 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 {
+    // The previous context; or 0 if none.
+    CallingContext  *Prev;
+
+    // The decl to which the attr is attached.
+    const NamedDecl *AttrDecl;
+
+    // Implicit object argument -- e.g. 'this'
+    const Expr *SelfArg = nullptr;
+
+    // Number of funArgs
+    unsigned NumArgs = 0;
+
+    // Function arguments
+    const Expr *const *FunArgs = nullptr;
+
+    // is Self referred to with -> or .?
+    bool SelfArrow = false;
+
+    CallingContext(CallingContext *P, const NamedDecl *D = nullptr)
+        : Prev(P), AttrDecl(D) {}
+  };
+
+  SExprBuilder(til::MemRegionRef A) : Arena(A) {
+    // FIXME: we don't always have a self-variable.
+    SelfVar = new (Arena) til::Variable(nullptr);
+    SelfVar->setKind(til::Variable::VK_SFun);
+  }
+
+  // Translate a clang expression in an attribute to a til::SExpr.
+  // Constructs the context from D, DeclExp, and SelfDecl.
+  CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D,
+                                   const Expr *DeclExp, VarDecl *SelfD=nullptr);
+
+  CapabilityExpr translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx);
+
+  // 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 *translate(const Stmt *S, CallingContext *Ctx);
+  til::SCFG  *buildCFG(CFGWalker &Walker);
+
+  til::SExpr *lookupStmt(const Stmt *S);
+
+  til::BasicBlock *lookupBlock(const CFGBlock *B) {
+    return BlockMap[B->getBlockID()];
+  }
+
+  const til::SCFG *getCFG() const { return Scfg; }
+  til::SCFG *getCFG() { return Scfg; }
+
+private:
+  // We implement the CFGVisitor API
+  friend class CFGWalker;
+
+  til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE,
+                                   CallingContext *Ctx) ;
+  til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx);
+  til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx);
+  til::SExpr *translateObjCIVarRefExpr(const ObjCIvarRefExpr *IVRE,
+                                       CallingContext *Ctx);
+  til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx,
+                                const Expr *SelfE = nullptr);
+  til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME,
+                                         CallingContext *Ctx);
+  til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE,
+                                           CallingContext *Ctx);
+  til::SExpr *translateUnaryOperator(const UnaryOperator *UO,
+                                     CallingContext *Ctx);
+  til::SExpr *translateBinOp(til::TIL_BinaryOpcode Op,
+                             const BinaryOperator *BO,
+                             CallingContext *Ctx, bool Reverse = false);
+  til::SExpr *translateBinAssign(til::TIL_BinaryOpcode Op,
+                                 const BinaryOperator *BO,
+                                 CallingContext *Ctx, bool Assign = false);
+  til::SExpr *translateBinaryOperator(const BinaryOperator *BO,
+                                      CallingContext *Ctx);
+  til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx);
+  til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E,
+                                          CallingContext *Ctx);
+  til::SExpr *translateAbstractConditionalOperator(
+      const AbstractConditionalOperator *C, CallingContext *Ctx);
+
+  til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx);
+
+  // Map from statements in the clang CFG to SExprs in the til::SCFG.
+  using StatementMap = llvm::DenseMap<const Stmt *, til::SExpr *>;
+
+  // Map from clang local variables to indices in a LVarDefinitionMap.
+  using LVarIndexMap = llvm::DenseMap<const ValueDecl *, unsigned>;
+
+  // Map from local variable indices to SSA variables (or constants).
+  using NameVarPair = std::pair<const ValueDecl *, til::SExpr *>;
+  using LVarDefinitionMap = CopyOnWriteVector<NameVarPair>;
+
+  struct BlockInfo {
+    LVarDefinitionMap ExitMap;
+    bool HasBackEdges = false;
+
+    // Successors yet to be processed
+    unsigned UnprocessedSuccessors = 0;
+
+    // Predecessors already processed
+    unsigned ProcessedPredecessors = 0;
+
+    BlockInfo() = default;
+    BlockInfo(BlockInfo &&) = default;
+    BlockInfo &operator=(BlockInfo &&) = default;
+  };
+
+  void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First);
+  void enterCFGBlock(const CFGBlock *B);
+  bool visitPredecessors() { return true; }
+  void handlePredecessor(const CFGBlock *Pred);
+  void handlePredecessorBackEdge(const CFGBlock *Pred);
+  void enterCFGBlockBody(const CFGBlock *B);
+  void handleStatement(const Stmt *S);
+  void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD);
+  void exitCFGBlockBody(const CFGBlock *B);
+  bool visitSuccessors() { return true; }
+  void handleSuccessor(const CFGBlock *Succ);
+  void handleSuccessorBackEdge(const CFGBlock *Succ);
+  void exitCFGBlock(const CFGBlock *B);
+  void exitCFG(const CFGBlock *Last);
+
+  void insertStmt(const Stmt *S, til::SExpr *E) {
+    SMap.insert(std::make_pair(S, E));
+  }
+
+  til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD);
+
+  til::SExpr *addStatement(til::SExpr *E, const Stmt *S,
+                           const ValueDecl *VD = nullptr);
+  til::SExpr *lookupVarDecl(const ValueDecl *VD);
+  til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E);
+  til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E);
+
+  void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E);
+  void mergeEntryMap(LVarDefinitionMap Map);
+  void mergeEntryMapBackEdge();
+  void mergePhiNodesBackEdge(const CFGBlock *Blk);
+
+private:
+  // Set to true when parsing capability expressions, which get translated
+  // inaccurately in order to hack around smart pointers etc.
+  static const bool CapabilityExprMode = true;
+
+  til::MemRegionRef Arena;
+
+  // Variable to use for 'this'.  May be null.
+  til::Variable *SelfVar = nullptr;
+
+  til::SCFG *Scfg = nullptr;
+
+  // Map from Stmt to TIL Variables
+  StatementMap SMap;
+
+  // Indices of clang local vars.
+  LVarIndexMap LVarIdxMap;
+
+  // Map from clang to til BBs.
+  std::vector<til::BasicBlock *> BlockMap;
+
+  // Extra information per BB. Indexed by clang BlockID.
+  std::vector<BlockInfo> BBInfo;
+
+  LVarDefinitionMap CurrentLVarMap;
+  std::vector<til::Phi *> CurrentArguments;
+  std::vector<til::SExpr *> CurrentInstructions;
+  std::vector<til::Phi *> IncompleteArgs;
+  til::BasicBlock *CurrentBB = nullptr;
+  BlockInfo *CurrentBlockInfo = nullptr;
+};
+
+// Dump an SCFG to llvm::errs().
+void printSCFG(CFGWalker &Walker);
+
+} // namespace threadSafety
+} // namespace clang
+
+#endif // LLVM_CLANG_THREAD_SAFETY_COMMON_H