contrib/llvm-project/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h

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