• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
equals(const til::SExpr * E1,const til::SExpr * E2)43 inline bool equals(const til::SExpr *E1, const til::SExpr *E2) {
44   return til::EqualsComparator::compareExprs(E1, E2);
45 }
46 
matches(const til::SExpr * E1,const til::SExpr * E2)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 
partiallyMatches(const til::SExpr * E1,const til::SExpr * E2)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 
toString(const til::SExpr * E)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.
enterCFG(CFG * Cfg,const NamedDecl * D,const CFGBlock * First)84   void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {}
85 
86   // Enter a CFGBlock.
enterCFGBlock(const CFGBlock * B)87   void enterCFGBlock(const CFGBlock *B) {}
88 
89   // Returns true if this visitor implements handlePredecessor
visitPredecessors()90   bool visitPredecessors() { return true; }
91 
92   // Process a predecessor edge.
handlePredecessor(const CFGBlock * Pred)93   void handlePredecessor(const CFGBlock *Pred) {}
94 
95   // Process a successor back edge to a previously visited block.
handlePredecessorBackEdge(const CFGBlock * Pred)96   void handlePredecessorBackEdge(const CFGBlock *Pred) {}
97 
98   // Called just before processing statements.
enterCFGBlockBody(const CFGBlock * B)99   void enterCFGBlockBody(const CFGBlock *B) {}
100 
101   // Process an ordinary statement.
handleStatement(const Stmt * S)102   void handleStatement(const Stmt *S) {}
103 
104   // Process a destructor call
handleDestructorCall(const VarDecl * VD,const CXXDestructorDecl * DD)105   void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {}
106 
107   // Called after all statements have been handled.
exitCFGBlockBody(const CFGBlock * B)108   void exitCFGBlockBody(const CFGBlock *B) {}
109 
110   // Return true
visitSuccessors()111   bool visitSuccessors() { return true; }
112 
113   // Process a successor edge.
handleSuccessor(const CFGBlock * Succ)114   void handleSuccessor(const CFGBlock *Succ) {}
115 
116   // Process a successor back edge to a previously visited block.
handleSuccessorBackEdge(const CFGBlock * Succ)117   void handleSuccessorBackEdge(const CFGBlock *Succ) {}
118 
119   // Leave a CFGBlock.
exitCFGBlock(const CFGBlock * B)120   void exitCFGBlock(const CFGBlock *B) {}
121 
122   // Leave the CFG, and perform any final cleanup operations.
exitCFG(const CFGBlock * Last)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:
CFGWalker()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.
init(AnalysisDeclContext & AC)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>
walk(Visitor & V)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 
getGraph()235   const CFG *getGraph() const { return CFGraph; }
getGraph()236   CFG *getGraph() { return CFGraph; }
237 
getDecl()238   const NamedDecl *getDecl() const {
239     return dyn_cast<NamedDecl>(ACtx->getDecl());
240   }
241 
getSortedGraph()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:
CapabilityExpr(const til::SExpr * E,bool Neg)263   CapabilityExpr(const til::SExpr *E, bool Neg) : CapExpr(E), Negated(Neg) {}
264 
sexpr()265   const til::SExpr* sexpr()    const { return CapExpr; }
negative()266   bool              negative() const { return Negated; }
267 
268   CapabilityExpr operator!() const {
269     return CapabilityExpr(CapExpr, !Negated);
270   }
271 
equals(const CapabilityExpr & other)272   bool equals(const CapabilityExpr &other) const {
273     return (Negated == other.Negated) && sx::equals(CapExpr, other.CapExpr);
274   }
275 
matches(const CapabilityExpr & other)276   bool matches(const CapabilityExpr &other) const {
277     return (Negated == other.Negated) && sx::matches(CapExpr, other.CapExpr);
278   }
279 
matchesUniv(const CapabilityExpr & CapE)280   bool matchesUniv(const CapabilityExpr &CapE) const {
281     return isUniversal() || matches(CapE);
282   }
283 
partiallyMatches(const CapabilityExpr & other)284   bool partiallyMatches(const CapabilityExpr &other) const {
285     return (Negated == other.Negated) &&
286             sx::partiallyMatches(CapExpr, other.CapExpr);
287   }
288 
valueDecl()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 
toString()299   std::string toString() const {
300     if (Negated)
301       return "!" + sx::toString(CapExpr);
302     return sx::toString(CapExpr);
303   }
304 
shouldIgnore()305   bool shouldIgnore() const { return CapExpr == nullptr; }
306 
isInvalid()307   bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); }
308 
isUniversal()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)
PrevCallingContext335         : Prev(P), AttrDecl(D), SelfArg(nullptr),
336           NumArgs(0), FunArgs(nullptr), SelfArrow(false)
337     {}
338   };
339 
SExprBuilder(til::MemRegionRef A)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 
lookupBlock(const CFGBlock * B)363   til::BasicBlock *lookupBlock(const CFGBlock *B) {
364     return BlockMap[B->getBlockID()];
365   }
366 
getCFG()367   const til::SCFG *getCFG() const { return Scfg; }
getCFG()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 
BlockInfoBlockInfo415     BlockInfo()
416         : HasBackEdges(false), UnprocessedSuccessors(0),
417           ProcessedPredecessors(0) {}
BlockInfoBlockInfo418     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);
visitPredecessors()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);
visitSuccessors()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 
insertStmt(const Stmt * S,til::SExpr * E)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