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_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H
  23 #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H
  24
  25 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
  26 #include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
  27 #include "clang/Analysis/Analyses/ThreadSafetyTraverse.h"
  28 #include "clang/Analysis/AnalysisContext.h"
  29 #include "clang/Basic/OperatorKinds.h"
  30 #include <memory>
  31 #include <ostream>
  32 #include <sstream>
  33 #include <vector>
  34
  35
  36 namespace clang {
  37 namespace threadSafety {
  38
  39
  40 // Various helper functions on til::SExpr
  41 namespace sx {
  42
  43 inline bool equals(const til::SExpr *E1, const til::SExpr *E2) {
  44   return til::EqualsComparator::compareExprs(E1, E2);
  45 }
  46
  47 inline bool matches(const til::SExpr *E1, const til::SExpr *E2) {
  48   // We treat a top-level wildcard as the "univsersal" lock.
  49   // It matches everything for the purpose of checking locks, but not
  50   // for unlocking them.
  51   if (isa<til::Wildcard>(E1))
  52     return isa<til::Wildcard>(E2);
  53   if (isa<til::Wildcard>(E2))
  54     return isa<til::Wildcard>(E1);
  55
  56   return til::MatchComparator::compareExprs(E1, E2);
  57 }
  58
  59 inline bool partiallyMatches(const til::SExpr *E1, const til::SExpr *E2) {
  60   const auto *PE1 = dyn_cast_or_null<til::Project>(E1);
  61   if (!PE1)
  62     return false;
  63   const auto *PE2 = dyn_cast_or_null<til::Project>(E2);
  64   if (!PE2)
  65     return false;
  66   return PE1->clangDecl() == PE2->clangDecl();
  67 }
  68
  69 inline std::string toString(const til::SExpr *E) {
  70   std::stringstream ss;
  71   til::StdPrinter::print(E, ss);
  72   return ss.str();
  73 }
  74
  75 }  // end namespace sx
  76
  77
  78
  79 // This class defines the interface of a clang CFG Visitor.
  80 // CFGWalker will invoke the following methods.
  81 // Note that methods are not virtual; the visitor is templatized.
  82 class CFGVisitor {
  83   // Enter the CFG for Decl D, and perform any initial setup operations.
  84   void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {}
  85
  86   // Enter a CFGBlock.
  87   void enterCFGBlock(const CFGBlock *B) {}
  88
  89   // Returns true if this visitor implements handlePredecessor
  90   bool visitPredecessors() { return true; }
  91
  92   // Process a predecessor edge.
  93   void handlePredecessor(const CFGBlock *Pred) {}
  94
  95   // Process a successor back edge to a previously visited block.
  96   void handlePredecessorBackEdge(const CFGBlock *Pred) {}
  97
  98   // Called just before processing statements.
  99   void enterCFGBlockBody(const CFGBlock *B) {}
 100
 101   // Process an ordinary statement.
 102   void handleStatement(const Stmt *S) {}
 103
 104   // Process a destructor call
 105   void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {}
 106
 107   // Called after all statements have been handled.
 108   void exitCFGBlockBody(const CFGBlock *B) {}
 109
 110   // Return true
 111   bool visitSuccessors() { return true; }
 112
 113   // Process a successor edge.
 114   void handleSuccessor(const CFGBlock *Succ) {}
 115
 116   // Process a successor back edge to a previously visited block.
 117   void handleSuccessorBackEdge(const CFGBlock *Succ) {}
 118
 119   // Leave a CFGBlock.
 120   void exitCFGBlock(const CFGBlock *B) {}
 121
 122   // Leave the CFG, and perform any final cleanup operations.
 123   void exitCFG(const CFGBlock *Last) {}
 124 };
 125
 126
 127 // Walks the clang CFG, and invokes methods on a given CFGVisitor.
 128 class CFGWalker {
 129 public:
 130   CFGWalker() : CFGraph(nullptr), ACtx(nullptr), SortedGraph(nullptr) {}
 131
 132   // Initialize the CFGWalker.  This setup only needs to be done once, even
 133   // if there are multiple passes over the CFG.
 134   bool init(AnalysisDeclContext &AC) {
 135     ACtx = &AC;
 136     CFGraph = AC.getCFG();
 137     if (!CFGraph)
 138       return false;
 139
 140     // Ignore anonymous functions.
 141     if (!dyn_cast_or_null<NamedDecl>(AC.getDecl()))
 142       return false;
 143
 144     SortedGraph = AC.getAnalysis<PostOrderCFGView>();
 145     if (!SortedGraph)
 146       return false;
 147
 148     return true;
 149   }
 150
 151   // Traverse the CFG, calling methods on V as appropriate.
 152   template <class Visitor>
 153   void walk(Visitor &V) {
 154     PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph);
 155
 156     V.enterCFG(CFGraph, getDecl(), &CFGraph->getEntry());
 157
 158     for (const auto *CurrBlock : *SortedGraph) {
 159       VisitedBlocks.insert(CurrBlock);
 160
 161       V.enterCFGBlock(CurrBlock);
 162
 163       // Process predecessors, handling back edges last
 164       if (V.visitPredecessors()) {
 165         SmallVector<CFGBlock*, 4> BackEdges;
 166         // Process successors
 167         for (CFGBlock::const_pred_iterator SI = CurrBlock->pred_begin(),
 168                                            SE = CurrBlock->pred_end();
 169              SI != SE; ++SI) {
 170           if (*SI == nullptr)
 171             continue;
 172
 173           if (!VisitedBlocks.alreadySet(*SI)) {
 174             BackEdges.push_back(*SI);
 175             continue;
 176           }
 177           V.handlePredecessor(*SI);
 178         }
 179
 180         for (auto *Blk : BackEdges)
 181           V.handlePredecessorBackEdge(Blk);
 182       }
 183
 184       V.enterCFGBlockBody(CurrBlock);
 185
 186       // Process statements
 187       for (const auto &BI : *CurrBlock) {
 188         switch (BI.getKind()) {
 189         case CFGElement::Statement: {
 190           V.handleStatement(BI.castAs<CFGStmt>().getStmt());
 191           break;
 192         }
 193         case CFGElement::AutomaticObjectDtor: {
 194           CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>();
 195           CXXDestructorDecl *DD = const_cast<CXXDestructorDecl*>(
 196               AD.getDestructorDecl(ACtx->getASTContext()));
 197           VarDecl *VD = const_cast<VarDecl*>(AD.getVarDecl());
 198           V.handleDestructorCall(VD, DD);
 199           break;
 200         }
 201         default:
 202           break;
 203         }
 204       }
 205
 206       V.exitCFGBlockBody(CurrBlock);
 207
 208       // Process successors, handling back edges first.
 209       if (V.visitSuccessors()) {
 210         SmallVector<CFGBlock*, 8> ForwardEdges;
 211
 212         // Process successors
 213         for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
 214                                            SE = CurrBlock->succ_end();
 215              SI != SE; ++SI) {
 216           if (*SI == nullptr)
 217             continue;
 218
 219           if (!VisitedBlocks.alreadySet(*SI)) {
 220             ForwardEdges.push_back(*SI);
 221             continue;
 222           }
 223           V.handleSuccessorBackEdge(*SI);
 224         }
 225
 226         for (auto *Blk : ForwardEdges)
 227           V.handleSuccessor(Blk);
 228       }
 229
 230       V.exitCFGBlock(CurrBlock);
 231     }
 232     V.exitCFG(&CFGraph->getExit());
 233   }
 234
 235   const CFG *getGraph() const { return CFGraph; }
 236   CFG *getGraph() { return CFGraph; }
 237
 238   const NamedDecl *getDecl() const {
 239     return dyn_cast<NamedDecl>(ACtx->getDecl());
 240   }
 241
 242   const PostOrderCFGView *getSortedGraph() const { return SortedGraph; }
 243
 244 private:
 245   CFG *CFGraph;
 246   AnalysisDeclContext *ACtx;
 247   PostOrderCFGView *SortedGraph;
 248 };
 249
 250
 251
 252
 253 class CapabilityExpr {
 254   // TODO: move this back into ThreadSafety.cpp
 255   // This is specific to thread safety.  It is here because
 256   // translateAttrExpr needs it, but that should be moved too.
 257
 258 private:
 259   const til::SExpr* CapExpr;   ///< The capability expression.
 260   bool Negated;                ///< True if this is a negative capability
 261
 262 public:
 263   CapabilityExpr(const til::SExpr *E, bool Neg) : CapExpr(E), Negated(Neg) {}
 264
 265   const til::SExpr* sexpr()    const { return CapExpr; }
 266   bool              negative() const { return Negated; }
 267
 268   CapabilityExpr operator!() const {
 269     return CapabilityExpr(CapExpr, !Negated);
 270   }
 271
 272   bool equals(const CapabilityExpr &other) const {
 273     return (Negated == other.Negated) && sx::equals(CapExpr, other.CapExpr);
 274   }
 275
 276   bool matches(const CapabilityExpr &other) const {
 277     return (Negated == other.Negated) && sx::matches(CapExpr, other.CapExpr);
 278   }
 279
 280   bool matchesUniv(const CapabilityExpr &CapE) const {
 281     return isUniversal() || matches(CapE);
 282   }
 283
 284   bool partiallyMatches(const CapabilityExpr &other) const {
 285     return (Negated == other.Negated) &&
 286             sx::partiallyMatches(CapExpr, other.CapExpr);
 287   }
 288
 289   const ValueDecl* valueDecl() const {
 290     if (Negated || CapExpr == nullptr)
 291       return nullptr;
 292     if (auto *P = dyn_cast<til::Project>(CapExpr))
 293       return P->clangDecl();
 294     if (auto *P = dyn_cast<til::LiteralPtr>(CapExpr))
 295       return P->clangDecl();
 296     return nullptr;
 297   }
 298
 299   std::string toString() const {
 300     if (Negated)
 301       return "!" + sx::toString(CapExpr);
 302     return sx::toString(CapExpr);
 303   }
 304
 305   bool shouldIgnore() const { return CapExpr == nullptr; }
 306
 307   bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); }
 308
 309   bool isUniversal() const { return sexpr() && isa<til::Wildcard>(sexpr()); }
 310 };
 311
 312
 313
 314 // Translate clang::Expr to til::SExpr.
 315 class SExprBuilder {
 316 public:
 317   /// \brief Encapsulates the lexical context of a function call.  The lexical
 318   /// context includes the arguments to the call, including the implicit object
 319   /// argument.  When an attribute containing a mutex expression is attached to
 320   /// a method, the expression may refer to formal parameters of the method.
 321   /// Actual arguments must be substituted for formal parameters to derive
 322   /// the appropriate mutex expression in the lexical context where the function
 323   /// is called.  PrevCtx holds the context in which the arguments themselves
 324   /// should be evaluated; multiple calling contexts can be chained together
 325   /// by the lock_returned attribute.
 326   struct CallingContext {
 327     CallingContext  *Prev;      // The previous context; or 0 if none.
 328     const NamedDecl *AttrDecl;  // The decl to which the attr is attached.
 329     const Expr *SelfArg;        // Implicit object argument -- e.g. 'this'
 330     unsigned NumArgs;           // Number of funArgs
 331     const Expr *const *FunArgs; // Function arguments
 332     bool SelfArrow;             // is Self referred to with -> or .?
 333
 334     CallingContext(CallingContext *P, const NamedDecl *D = nullptr)
 335         : Prev(P), AttrDecl(D), SelfArg(nullptr),
 336           NumArgs(0), FunArgs(nullptr), SelfArrow(false)
 337     {}
 338   };
 339
 340   SExprBuilder(til::MemRegionRef A)
 341       : Arena(A), SelfVar(nullptr), Scfg(nullptr), CurrentBB(nullptr),
 342         CurrentBlockInfo(nullptr) {
 343     // FIXME: we don't always have a self-variable.
 344     SelfVar = new (Arena) til::Variable(nullptr);
 345     SelfVar->setKind(til::Variable::VK_SFun);
 346   }
 347
 348   // Translate a clang expression in an attribute to a til::SExpr.
 349   // Constructs the context from D, DeclExp, and SelfDecl.
 350   CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D,
 351                                    const Expr *DeclExp, VarDecl *SelfD=nullptr);
 352
 353   CapabilityExpr translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx);
 354
 355   // Translate a clang statement or expression to a TIL expression.
 356   // Also performs substitution of variables; Ctx provides the context.
 357   // Dispatches on the type of S.
 358   til::SExpr *translate(const Stmt *S, CallingContext *Ctx);
 359   til::SCFG  *buildCFG(CFGWalker &Walker);
 360
 361   til::SExpr *lookupStmt(const Stmt *S);
 362
 363   til::BasicBlock *lookupBlock(const CFGBlock *B) {
 364     return BlockMap[B->getBlockID()];
 365   }
 366
 367   const til::SCFG *getCFG() const { return Scfg; }
 368   til::SCFG *getCFG() { return Scfg; }
 369
 370 private:
 371   til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE,
 372                                    CallingContext *Ctx) ;
 373   til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx);
 374   til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx);
 375   til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx,
 376                                 const Expr *SelfE = nullptr);
 377   til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME,
 378                                          CallingContext *Ctx);
 379   til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE,
 380                                            CallingContext *Ctx);
 381   til::SExpr *translateUnaryOperator(const UnaryOperator *UO,
 382                                      CallingContext *Ctx);
 383   til::SExpr *translateBinOp(til::TIL_BinaryOpcode Op,
 384                              const BinaryOperator *BO,
 385                              CallingContext *Ctx, bool Reverse = false);
 386   til::SExpr *translateBinAssign(til::TIL_BinaryOpcode Op,
 387                                  const BinaryOperator *BO,
 388                                  CallingContext *Ctx, bool Assign = false);
 389   til::SExpr *translateBinaryOperator(const BinaryOperator *BO,
 390                                       CallingContext *Ctx);
 391   til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx);
 392   til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E,
 393                                           CallingContext *Ctx);
 394   til::SExpr *translateAbstractConditionalOperator(
 395       const AbstractConditionalOperator *C, CallingContext *Ctx);
 396
 397   til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx);
 398
 399   // Map from statements in the clang CFG to SExprs in the til::SCFG.
 400   typedef llvm::DenseMap<const Stmt*, til::SExpr*> StatementMap;
 401
 402   // Map from clang local variables to indices in a LVarDefinitionMap.
 403   typedef llvm::DenseMap<const ValueDecl *, unsigned> LVarIndexMap;
 404
 405   // Map from local variable indices to SSA variables (or constants).
 406   typedef std::pair<const ValueDecl *, til::SExpr *> NameVarPair;
 407   typedef CopyOnWriteVector<NameVarPair> LVarDefinitionMap;
 408
 409   struct BlockInfo {
 410     LVarDefinitionMap ExitMap;
 411     bool HasBackEdges;
 412     unsigned UnprocessedSuccessors;   // Successors yet to be processed
 413     unsigned ProcessedPredecessors;   // Predecessors already processed
 414
 415     BlockInfo()
 416         : HasBackEdges(false), UnprocessedSuccessors(0),
 417           ProcessedPredecessors(0) {}
 418     BlockInfo(BlockInfo &&RHS)
 419         : ExitMap(std::move(RHS.ExitMap)),
 420           HasBackEdges(RHS.HasBackEdges),
 421           UnprocessedSuccessors(RHS.UnprocessedSuccessors),
 422           ProcessedPredecessors(RHS.ProcessedPredecessors) {}
 423
 424     BlockInfo &operator=(BlockInfo &&RHS) {
 425       if (this != &RHS) {
 426         ExitMap = std::move(RHS.ExitMap);
 427         HasBackEdges = RHS.HasBackEdges;
 428         UnprocessedSuccessors = RHS.UnprocessedSuccessors;
 429         ProcessedPredecessors = RHS.ProcessedPredecessors;
 430       }
 431       return *this;
 432     }
 433
 434   private:
 435     BlockInfo(const BlockInfo &) = delete;
 436     void operator=(const BlockInfo &) = delete;
 437   };
 438
 439   // We implement the CFGVisitor API
 440   friend class CFGWalker;
 441
 442   void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First);
 443   void enterCFGBlock(const CFGBlock *B);
 444   bool visitPredecessors() { return true; }
 445   void handlePredecessor(const CFGBlock *Pred);
 446   void handlePredecessorBackEdge(const CFGBlock *Pred);
 447   void enterCFGBlockBody(const CFGBlock *B);
 448   void handleStatement(const Stmt *S);
 449   void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD);
 450   void exitCFGBlockBody(const CFGBlock *B);
 451   bool visitSuccessors() { return true; }
 452   void handleSuccessor(const CFGBlock *Succ);
 453   void handleSuccessorBackEdge(const CFGBlock *Succ);
 454   void exitCFGBlock(const CFGBlock *B);
 455   void exitCFG(const CFGBlock *Last);
 456
 457   void insertStmt(const Stmt *S, til::SExpr *E) {
 458     SMap.insert(std::make_pair(S, E));
 459   }
 460   til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD);
 461
 462   til::SExpr *addStatement(til::SExpr *E, const Stmt *S,
 463                            const ValueDecl *VD = nullptr);
 464   til::SExpr *lookupVarDecl(const ValueDecl *VD);
 465   til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E);
 466   til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E);
 467
 468   void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E);
 469   void mergeEntryMap(LVarDefinitionMap Map);
 470   void mergeEntryMapBackEdge();
 471   void mergePhiNodesBackEdge(const CFGBlock *Blk);
 472
 473 private:
 474   // Set to true when parsing capability expressions, which get translated
 475   // inaccurately in order to hack around smart pointers etc.
 476   static const bool CapabilityExprMode = true;
 477
 478   til::MemRegionRef Arena;
 479   til::Variable *SelfVar;       // Variable to use for 'this'.  May be null.
 480
 481   til::SCFG *Scfg;
 482   StatementMap SMap;                       // Map from Stmt to TIL Variables
 483   LVarIndexMap LVarIdxMap;                 // Indices of clang local vars.
 484   std::vector<til::BasicBlock *> BlockMap; // Map from clang to til BBs.
 485   std::vector<BlockInfo> BBInfo;           // Extra information per BB.
 486                                            // Indexed by clang BlockID.
 487
 488   LVarDefinitionMap CurrentLVarMap;
 489   std::vector<til::Phi*>   CurrentArguments;
 490   std::vector<til::SExpr*> CurrentInstructions;
 491   std::vector<til::Phi*>   IncompleteArgs;
 492   til::BasicBlock *CurrentBB;
 493   BlockInfo *CurrentBlockInfo;
 494 };
 495
 496
 497 // Dump an SCFG to llvm::errs().
 498 void printSCFG(CFGWalker &Walker);
 499
 500
 501 } // end namespace threadSafety
 502
 503 } // end namespace clang
 504
 505 #endif  // LLVM_CLANG_THREAD_SAFETY_COMMON_H