Home | History | Annotate | Download | only in Analyses 
      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)
    291       return nullptr;
    292     if (auto *P = dyn_cast<til::Project>(CapExpr))
    293       return P->clangDecl();
    294     return nullptr;
    295   }
    296 
    297   std::string toString() const {
    298     if (Negated)
    299       return "!" + sx::toString(CapExpr);
    300     return sx::toString(CapExpr);
    301   }
    302 
    303   bool shouldIgnore() const { return CapExpr == nullptr; }
    304 
    305   bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); }
    306 
    307   bool isUniversal() const { return sexpr() && isa<til::Wildcard>(sexpr()); }
    308 };
    309 
    310 
    311 
    312 // Translate clang::Expr to til::SExpr.
    313 class SExprBuilder {
    314 public:
    315   /// \brief Encapsulates the lexical context of a function call.  The lexical
    316   /// context includes the arguments to the call, including the implicit object
    317   /// argument.  When an attribute containing a mutex expression is attached to
    318   /// a method, the expression may refer to formal parameters of the method.
    319   /// Actual arguments must be substituted for formal parameters to derive
    320   /// the appropriate mutex expression in the lexical context where the function
    321   /// is called.  PrevCtx holds the context in which the arguments themselves
    322   /// should be evaluated; multiple calling contexts can be chained together
    323   /// by the lock_returned attribute.
    324   struct CallingContext {
    325     CallingContext  *Prev;      // The previous context; or 0 if none.
    326     const NamedDecl *AttrDecl;  // The decl to which the attr is attached.
    327     const Expr *SelfArg;        // Implicit object argument -- e.g. 'this'
    328     unsigned NumArgs;           // Number of funArgs
    329     const Expr *const *FunArgs; // Function arguments
    330     bool SelfArrow;             // is Self referred to with -> or .?
    331 
    332     CallingContext(CallingContext *P, const NamedDecl *D = nullptr)
    333         : Prev(P), AttrDecl(D), SelfArg(nullptr),
    334           NumArgs(0), FunArgs(nullptr), SelfArrow(false)
    335     {}
    336   };
    337 
    338   SExprBuilder(til::MemRegionRef A)
    339       : Arena(A), SelfVar(nullptr), Scfg(nullptr), CurrentBB(nullptr),
    340         CurrentBlockInfo(nullptr) {
    341     // FIXME: we don't always have a self-variable.
    342     SelfVar = new (Arena) til::Variable(nullptr);
    343     SelfVar->setKind(til::Variable::VK_SFun);
    344   }
    345 
    346   // Translate a clang expression in an attribute to a til::SExpr.
    347   // Constructs the context from D, DeclExp, and SelfDecl.
    348   CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D,
    349                                    const Expr *DeclExp, VarDecl *SelfD=nullptr);
    350 
    351   CapabilityExpr translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx);
    352 
    353   // Translate a clang statement or expression to a TIL expression.
    354   // Also performs substitution of variables; Ctx provides the context.
    355   // Dispatches on the type of S.
    356   til::SExpr *translate(const Stmt *S, CallingContext *Ctx);
    357   til::SCFG  *buildCFG(CFGWalker &Walker);
    358 
    359   til::SExpr *lookupStmt(const Stmt *S);
    360 
    361   til::BasicBlock *lookupBlock(const CFGBlock *B) {
    362     return BlockMap[B->getBlockID()];
    363   }
    364 
    365   const til::SCFG *getCFG() const { return Scfg; }
    366   til::SCFG *getCFG() { return Scfg; }
    367 
    368 private:
    369   til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE,
    370                                    CallingContext *Ctx) ;
    371   til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx);
    372   til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx);
    373   til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx,
    374                                 const Expr *SelfE = nullptr);
    375   til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME,
    376                                          CallingContext *Ctx);
    377   til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE,
    378                                            CallingContext *Ctx);
    379   til::SExpr *translateUnaryOperator(const UnaryOperator *UO,
    380                                      CallingContext *Ctx);
    381   til::SExpr *translateBinOp(til::TIL_BinaryOpcode Op,
    382                              const BinaryOperator *BO,
    383                              CallingContext *Ctx, bool Reverse = false);
    384   til::SExpr *translateBinAssign(til::TIL_BinaryOpcode Op,
    385                                  const BinaryOperator *BO,
    386                                  CallingContext *Ctx, bool Assign = false);
    387   til::SExpr *translateBinaryOperator(const BinaryOperator *BO,
    388                                       CallingContext *Ctx);
    389   til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx);
    390   til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E,
    391                                           CallingContext *Ctx);
    392   til::SExpr *translateAbstractConditionalOperator(
    393       const AbstractConditionalOperator *C, CallingContext *Ctx);
    394 
    395   til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx);
    396 
    397   // Map from statements in the clang CFG to SExprs in the til::SCFG.
    398   typedef llvm::DenseMap<const Stmt*, til::SExpr*> StatementMap;
    399 
    400   // Map from clang local variables to indices in a LVarDefinitionMap.
    401   typedef llvm::DenseMap<const ValueDecl *, unsigned> LVarIndexMap;
    402 
    403   // Map from local variable indices to SSA variables (or constants).
    404   typedef std::pair<const ValueDecl *, til::SExpr *> NameVarPair;
    405   typedef CopyOnWriteVector<NameVarPair> LVarDefinitionMap;
    406 
    407   struct BlockInfo {
    408     LVarDefinitionMap ExitMap;
    409     bool HasBackEdges;
    410     unsigned UnprocessedSuccessors;   // Successors yet to be processed
    411     unsigned ProcessedPredecessors;   // Predecessors already processed
    412 
    413     BlockInfo()
    414         : HasBackEdges(false), UnprocessedSuccessors(0),
    415           ProcessedPredecessors(0) {}
    416     BlockInfo(BlockInfo &&RHS)
    417         : ExitMap(std::move(RHS.ExitMap)),
    418           HasBackEdges(RHS.HasBackEdges),
    419           UnprocessedSuccessors(RHS.UnprocessedSuccessors),
    420           ProcessedPredecessors(RHS.ProcessedPredecessors) {}
    421 
    422     BlockInfo &operator=(BlockInfo &&RHS) {
    423       if (this != &RHS) {
    424         ExitMap = std::move(RHS.ExitMap);
    425         HasBackEdges = RHS.HasBackEdges;
    426         UnprocessedSuccessors = RHS.UnprocessedSuccessors;
    427         ProcessedPredecessors = RHS.ProcessedPredecessors;
    428       }
    429       return *this;
    430     }
    431 
    432   private:
    433     BlockInfo(const BlockInfo &) = delete;
    434     void operator=(const BlockInfo &) = delete;
    435   };
    436 
    437   // We implement the CFGVisitor API
    438   friend class CFGWalker;
    439 
    440   void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First);
    441   void enterCFGBlock(const CFGBlock *B);
    442   bool visitPredecessors() { return true; }
    443   void handlePredecessor(const CFGBlock *Pred);
    444   void handlePredecessorBackEdge(const CFGBlock *Pred);
    445   void enterCFGBlockBody(const CFGBlock *B);
    446   void handleStatement(const Stmt *S);
    447   void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD);
    448   void exitCFGBlockBody(const CFGBlock *B);
    449   bool visitSuccessors() { return true; }
    450   void handleSuccessor(const CFGBlock *Succ);
    451   void handleSuccessorBackEdge(const CFGBlock *Succ);
    452   void exitCFGBlock(const CFGBlock *B);
    453   void exitCFG(const CFGBlock *Last);
    454 
    455   void insertStmt(const Stmt *S, til::SExpr *E) {
    456     SMap.insert(std::make_pair(S, E));
    457   }
    458   til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD);
    459 
    460   til::SExpr *addStatement(til::SExpr *E, const Stmt *S,
    461                            const ValueDecl *VD = nullptr);
    462   til::SExpr *lookupVarDecl(const ValueDecl *VD);
    463   til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E);
    464   til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E);
    465 
    466   void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E);
    467   void mergeEntryMap(LVarDefinitionMap Map);
    468   void mergeEntryMapBackEdge();
    469   void mergePhiNodesBackEdge(const CFGBlock *Blk);
    470 
    471 private:
    472   // Set to true when parsing capability expressions, which get translated
    473   // inaccurately in order to hack around smart pointers etc.
    474   static const bool CapabilityExprMode = true;
    475 
    476   til::MemRegionRef Arena;
    477   til::Variable *SelfVar;       // Variable to use for 'this'.  May be null.
    478 
    479   til::SCFG *Scfg;
    480   StatementMap SMap;                       // Map from Stmt to TIL Variables
    481   LVarIndexMap LVarIdxMap;                 // Indices of clang local vars.
    482   std::vector<til::BasicBlock *> BlockMap; // Map from clang to til BBs.
    483   std::vector<BlockInfo> BBInfo;           // Extra information per BB.
    484                                            // Indexed by clang BlockID.
    485 
    486   LVarDefinitionMap CurrentLVarMap;
    487   std::vector<til::Phi*>   CurrentArguments;
    488   std::vector<til::SExpr*> CurrentInstructions;
    489   std::vector<til::Phi*>   IncompleteArgs;
    490   til::BasicBlock *CurrentBB;
    491   BlockInfo *CurrentBlockInfo;
    492 };
    493 
    494 
    495 // Dump an SCFG to llvm::errs().
    496 void printSCFG(CFGWalker &Walker);
    497 
    498 
    499 } // end namespace threadSafety
    500 
    501 } // end namespace clang
    502 
    503 #endif  // LLVM_CLANG_THREAD_SAFETY_COMMON_H
    504