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