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 || 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
    506