contrib/llvm/tools/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h

   1 //===- ThreadSafetyCommon.h ------------------------------------*- C++ --*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Parts of thread safety analysis that are not specific to thread safety
  11 // itself have been factored into classes here, where they can be potentially
  12 // used by other analyses.  Currently these include:
  13 //
  14 // * Generalize clang CFG visitors.
  15 // * Conversion of the clang CFG to SSA form.
  16 // * Translation of clang Exprs to TIL SExprs
  17 //
  18 // UNDER CONSTRUCTION.  USE AT YOUR OWN RISK.
  19 //
  20 //===----------------------------------------------------------------------===//
  21
  22 #ifndef LLVM_CLANG_THREAD_SAFETY_COMMON_H
  23 #define LLVM_CLANG_THREAD_SAFETY_COMMON_H
  24
  25 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
  26 #include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
  27 #include "clang/Analysis/AnalysisContext.h"
  28 #include "clang/Basic/OperatorKinds.h"
  29
  30 #include <memory>
  31 #include <vector>
  32
  33
  34 namespace clang {
  35 namespace threadSafety {
  36
  37 // This class defines the interface of a clang CFG Visitor.
  38 // CFGWalker will invoke the following methods.
  39 // Note that methods are not virtual; the visitor is templatized.
  40 class CFGVisitor {
  41   // Enter the CFG for Decl D, and perform any initial setup operations.
  42   void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {}
  43
  44   // Enter a CFGBlock.
  45   void enterCFGBlock(const CFGBlock *B) {}
  46
  47   // Returns true if this visitor implements handlePredecessor
  48   bool visitPredecessors() { return true; }
  49
  50   // Process a predecessor edge.
  51   void handlePredecessor(const CFGBlock *Pred) {}
  52
  53   // Process a successor back edge to a previously visited block.
  54   void handlePredecessorBackEdge(const CFGBlock *Pred) {}
  55
  56   // Called just before processing statements.
  57   void enterCFGBlockBody(const CFGBlock *B) {}
  58
  59   // Process an ordinary statement.
  60   void handleStatement(const Stmt *S) {}
  61
  62   // Process a destructor call
  63   void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {}
  64
  65   // Called after all statements have been handled.
  66   void exitCFGBlockBody(const CFGBlock *B) {}
  67
  68   // Return true
  69   bool visitSuccessors() { return true; }
  70
  71   // Process a successor edge.
  72   void handleSuccessor(const CFGBlock *Succ) {}
  73
  74   // Process a successor back edge to a previously visited block.
  75   void handleSuccessorBackEdge(const CFGBlock *Succ) {}
  76
  77   // Leave a CFGBlock.
  78   void exitCFGBlock(const CFGBlock *B) {}
  79
  80   // Leave the CFG, and perform any final cleanup operations.
  81   void exitCFG(const CFGBlock *Last) {}
  82 };
  83
  84
  85 // Walks the clang CFG, and invokes methods on a given CFGVisitor.
  86 class CFGWalker {
  87 public:
  88   CFGWalker() : CFGraph(nullptr), ACtx(nullptr), SortedGraph(nullptr) {}
  89
  90   // Initialize the CFGWalker.  This setup only needs to be done once, even
  91   // if there are multiple passes over the CFG.
  92   bool init(AnalysisDeclContext &AC) {
  93     ACtx = &AC;
  94     CFGraph = AC.getCFG();
  95     if (!CFGraph)
  96       return false;
  97
  98     // Ignore anonymous functions.
  99     if (!dyn_cast_or_null<NamedDecl>(AC.getDecl()))
 100       return false;
 101
 102     SortedGraph = AC.getAnalysis<PostOrderCFGView>();
 103     if (!SortedGraph)
 104       return false;
 105
 106     return true;
 107   }
 108
 109   // Traverse the CFG, calling methods on V as appropriate.
 110   template <class Visitor>
 111   void walk(Visitor &V) {
 112     PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph);
 113
 114     V.enterCFG(CFGraph, getDecl(), &CFGraph->getEntry());
 115
 116     for (const auto *CurrBlock : *SortedGraph) {
 117       VisitedBlocks.insert(CurrBlock);
 118
 119       V.enterCFGBlock(CurrBlock);
 120
 121       // Process predecessors, handling back edges last
 122       if (V.visitPredecessors()) {
 123         SmallVector<CFGBlock*, 4> BackEdges;
 124         // Process successors
 125         for (CFGBlock::const_pred_iterator SI = CurrBlock->pred_begin(),
 126                                            SE = CurrBlock->pred_end();
 127              SI != SE; ++SI) {
 128           if (*SI == nullptr)
 129             continue;
 130
 131           if (!VisitedBlocks.alreadySet(*SI)) {
 132             BackEdges.push_back(*SI);
 133             continue;
 134           }
 135           V.handlePredecessor(*SI);
 136         }
 137
 138         for (auto *Blk : BackEdges)
 139           V.handlePredecessorBackEdge(Blk);
 140       }
 141
 142       V.enterCFGBlockBody(CurrBlock);
 143
 144       // Process statements
 145       for (const auto &BI : *CurrBlock) {
 146         switch (BI.getKind()) {
 147         case CFGElement::Statement: {
 148           V.handleStatement(BI.castAs<CFGStmt>().getStmt());
 149           break;
 150         }
 151         case CFGElement::AutomaticObjectDtor: {
 152           CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>();
 153           CXXDestructorDecl *DD = const_cast<CXXDestructorDecl*>(
 154               AD.getDestructorDecl(ACtx->getASTContext()));
 155           VarDecl *VD = const_cast<VarDecl*>(AD.getVarDecl());
 156           V.handleDestructorCall(VD, DD);
 157           break;
 158         }
 159         default:
 160           break;
 161         }
 162       }
 163
 164       V.exitCFGBlockBody(CurrBlock);
 165
 166       // Process successors, handling back edges first.
 167       if (V.visitSuccessors()) {
 168         SmallVector<CFGBlock*, 8> ForwardEdges;
 169
 170         // Process successors
 171         for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
 172                                            SE = CurrBlock->succ_end();
 173              SI != SE; ++SI) {
 174           if (*SI == nullptr)
 175             continue;
 176
 177           if (!VisitedBlocks.alreadySet(*SI)) {
 178             ForwardEdges.push_back(*SI);
 179             continue;
 180           }
 181           V.handleSuccessorBackEdge(*SI);
 182         }
 183
 184         for (auto *Blk : ForwardEdges)
 185           V.handleSuccessor(Blk);
 186       }
 187
 188       V.exitCFGBlock(CurrBlock);
 189     }
 190     V.exitCFG(&CFGraph->getExit());
 191   }
 192
 193   const CFG *getGraph() const { return CFGraph; }
 194   CFG *getGraph() { return CFGraph; }
 195
 196   const NamedDecl *getDecl() const {
 197     return dyn_cast<NamedDecl>(ACtx->getDecl());
 198   }
 199
 200   const PostOrderCFGView *getSortedGraph() const { return SortedGraph; }
 201
 202 private:
 203   CFG *CFGraph;
 204   AnalysisDeclContext *ACtx;
 205   PostOrderCFGView *SortedGraph;
 206 };
 207
 208
 209 // Translate clang::Expr to til::SExpr.
 210 class SExprBuilder {
 211 public:
 212   /// \brief Encapsulates the lexical context of a function call.  The lexical
 213   /// context includes the arguments to the call, including the implicit object
 214   /// argument.  When an attribute containing a mutex expression is attached to
 215   /// a method, the expression may refer to formal parameters of the method.
 216   /// Actual arguments must be substituted for formal parameters to derive
 217   /// the appropriate mutex expression in the lexical context where the function
 218   /// is called.  PrevCtx holds the context in which the arguments themselves
 219   /// should be evaluated; multiple calling contexts can be chained together
 220   /// by the lock_returned attribute.
 221   struct CallingContext {
 222     const NamedDecl *AttrDecl;  // The decl to which the attr is attached.
 223     const Expr *SelfArg;        // Implicit object argument -- e.g. 'this'
 224     unsigned NumArgs;           // Number of funArgs
 225     const Expr *const *FunArgs; // Function arguments
 226     CallingContext *Prev;       // The previous context; or 0 if none.
 227     bool SelfArrow;             // is Self referred to with -> or .?
 228
 229     CallingContext(const NamedDecl *D = nullptr, const Expr *S = nullptr,
 230                    unsigned N = 0, const Expr *const *A = nullptr,
 231                    CallingContext *P = nullptr)
 232         : AttrDecl(D), SelfArg(S), NumArgs(N), FunArgs(A), Prev(P),
 233           SelfArrow(false)
 234     {}
 235   };
 236
 237   SExprBuilder(til::MemRegionRef A)
 238       : Arena(A), SelfVar(nullptr), Scfg(nullptr), CurrentBB(nullptr),
 239         CurrentBlockInfo(nullptr) {
 240     // FIXME: we don't always have a self-variable.
 241     SelfVar = new (Arena) til::Variable(nullptr);
 242     SelfVar->setKind(til::Variable::VK_SFun);
 243   }
 244
 245   // Translate a clang statement or expression to a TIL expression.
 246   // Also performs substitution of variables; Ctx provides the context.
 247   // Dispatches on the type of S.
 248   til::SExpr *translate(const Stmt *S, CallingContext *Ctx);
 249   til::SCFG  *buildCFG(CFGWalker &Walker);
 250
 251   til::SExpr *lookupStmt(const Stmt *S);
 252
 253   til::BasicBlock *lookupBlock(const CFGBlock *B) {
 254     return BlockMap[B->getBlockID()];
 255   }
 256
 257   const til::SCFG *getCFG() const { return Scfg; }
 258   til::SCFG *getCFG() { return Scfg; }
 259
 260 private:
 261   til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE,
 262                                    CallingContext *Ctx) ;
 263   til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx);
 264   til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx);
 265   til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx);
 266   til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME,
 267                                          CallingContext *Ctx);
 268   til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE,
 269                                            CallingContext *Ctx);
 270   til::SExpr *translateUnaryOperator(const UnaryOperator *UO,
 271                                      CallingContext *Ctx);
 272   til::SExpr *translateBinOp(til::TIL_BinaryOpcode Op,
 273                              const BinaryOperator *BO,
 274                              CallingContext *Ctx, bool Reverse = false);
 275   til::SExpr *translateBinAssign(til::TIL_BinaryOpcode Op,
 276                                  const BinaryOperator *BO,
 277                                  CallingContext *Ctx, bool Assign = false);
 278   til::SExpr *translateBinaryOperator(const BinaryOperator *BO,
 279                                       CallingContext *Ctx);
 280   til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx);
 281   til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E,
 282                                           CallingContext *Ctx);
 283   til::SExpr *translateConditionalOperator(const ConditionalOperator *C,
 284                                            CallingContext *Ctx);
 285   til::SExpr *translateBinaryConditionalOperator(
 286       const BinaryConditionalOperator *C, CallingContext *Ctx);
 287
 288   til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx);
 289
 290   // Map from statements in the clang CFG to SExprs in the til::SCFG.
 291   typedef llvm::DenseMap<const Stmt*, til::SExpr*> StatementMap;
 292
 293   // Map from clang local variables to indices in a LVarDefinitionMap.
 294   typedef llvm::DenseMap<const ValueDecl *, unsigned> LVarIndexMap;
 295
 296   // Map from local variable indices to SSA variables (or constants).
 297   typedef std::pair<const ValueDecl *, til::SExpr *> NameVarPair;
 298   typedef CopyOnWriteVector<NameVarPair> LVarDefinitionMap;
 299
 300   struct BlockInfo {
 301     LVarDefinitionMap ExitMap;
 302     bool HasBackEdges;
 303     unsigned UnprocessedSuccessors;   // Successors yet to be processed
 304     unsigned ProcessedPredecessors;   // Predecessors already processed
 305
 306     BlockInfo()
 307         : HasBackEdges(false), UnprocessedSuccessors(0),
 308           ProcessedPredecessors(0) {}
 309     BlockInfo(BlockInfo &&RHS)
 310         : ExitMap(std::move(RHS.ExitMap)),
 311           HasBackEdges(RHS.HasBackEdges),
 312           UnprocessedSuccessors(RHS.UnprocessedSuccessors),
 313           ProcessedPredecessors(RHS.ProcessedPredecessors) {}
 314
 315     BlockInfo &operator=(BlockInfo &&RHS) {
 316       if (this != &RHS) {
 317         ExitMap = std::move(RHS.ExitMap);
 318         HasBackEdges = RHS.HasBackEdges;
 319         UnprocessedSuccessors = RHS.UnprocessedSuccessors;
 320         ProcessedPredecessors = RHS.ProcessedPredecessors;
 321       }
 322       return *this;
 323     }
 324
 325   private:
 326     BlockInfo(const BlockInfo &) LLVM_DELETED_FUNCTION;
 327     void operator=(const BlockInfo &) LLVM_DELETED_FUNCTION;
 328   };
 329
 330   // We implement the CFGVisitor API
 331   friend class CFGWalker;
 332
 333   void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First);
 334   void enterCFGBlock(const CFGBlock *B);
 335   bool visitPredecessors() { return true; }
 336   void handlePredecessor(const CFGBlock *Pred);
 337   void handlePredecessorBackEdge(const CFGBlock *Pred);
 338   void enterCFGBlockBody(const CFGBlock *B);
 339   void handleStatement(const Stmt *S);
 340   void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD);
 341   void exitCFGBlockBody(const CFGBlock *B);
 342   bool visitSuccessors() { return true; }
 343   void handleSuccessor(const CFGBlock *Succ);
 344   void handleSuccessorBackEdge(const CFGBlock *Succ);
 345   void exitCFGBlock(const CFGBlock *B);
 346   void exitCFG(const CFGBlock *Last);
 347
 348   void insertStmt(const Stmt *S, til::SExpr *E) {
 349     SMap.insert(std::make_pair(S, E));
 350   }
 351   til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD);
 352
 353   til::SExpr *addStatement(til::SExpr *E, const Stmt *S,
 354                            const ValueDecl *VD = nullptr);
 355   til::SExpr *lookupVarDecl(const ValueDecl *VD);
 356   til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E);
 357   til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E);
 358
 359   void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E);
 360   void mergeEntryMap(LVarDefinitionMap Map);
 361   void mergeEntryMapBackEdge();
 362   void mergePhiNodesBackEdge(const CFGBlock *Blk);
 363
 364 private:
 365   til::MemRegionRef Arena;
 366   til::Variable *SelfVar;       // Variable to use for 'this'.  May be null.
 367   til::SCFG *Scfg;
 368
 369   StatementMap SMap;                       // Map from Stmt to TIL Variables
 370   LVarIndexMap LVarIdxMap;                 // Indices of clang local vars.
 371   std::vector<til::BasicBlock *> BlockMap; // Map from clang to til BBs.
 372   std::vector<BlockInfo> BBInfo;           // Extra information per BB.
 373                                            // Indexed by clang BlockID.
 374   std::unique_ptr<SExprBuilder::CallingContext> CallCtx; // Root calling context
 375
 376   LVarDefinitionMap CurrentLVarMap;
 377   std::vector<til::Variable*> CurrentArguments;
 378   std::vector<til::Variable*> CurrentInstructions;
 379   std::vector<til::Variable*> IncompleteArgs;
 380   til::BasicBlock *CurrentBB;
 381   BlockInfo *CurrentBlockInfo;
 382 };
 383
 384
 385 // Dump an SCFG to llvm::errs().
 386 void printSCFG(CFGWalker &Walker);
 387
 388
 389 } // end namespace threadSafety
 390
 391 } // end namespace clang
 392
 393 #endif  // LLVM_CLANG_THREAD_SAFETY_COMMON_H