clang  6.0.0svn
ThreadSafetyCommon.h
Go to the documentation of this file.
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 
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) {
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 
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;
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.
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  }
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 
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 
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.
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 
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);
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 
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(
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;
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 &&) = default;
419  BlockInfo &operator=(BlockInfo &&) = default;
420  };
421 
422  // We implement the CFGVisitor API
423  friend class CFGWalker;
424 
425  void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First);
426  void enterCFGBlock(const CFGBlock *B);
427  bool visitPredecessors() { return true; }
428  void handlePredecessor(const CFGBlock *Pred);
429  void handlePredecessorBackEdge(const CFGBlock *Pred);
430  void enterCFGBlockBody(const CFGBlock *B);
431  void handleStatement(const Stmt *S);
432  void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD);
433  void exitCFGBlockBody(const CFGBlock *B);
434  bool visitSuccessors() { return true; }
435  void handleSuccessor(const CFGBlock *Succ);
436  void handleSuccessorBackEdge(const CFGBlock *Succ);
437  void exitCFGBlock(const CFGBlock *B);
438  void exitCFG(const CFGBlock *Last);
439 
440  void insertStmt(const Stmt *S, til::SExpr *E) {
441  SMap.insert(std::make_pair(S, E));
442  }
443  til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD);
444 
445  til::SExpr *addStatement(til::SExpr *E, const Stmt *S,
446  const ValueDecl *VD = nullptr);
447  til::SExpr *lookupVarDecl(const ValueDecl *VD);
448  til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E);
449  til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E);
450 
451  void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E);
452  void mergeEntryMap(LVarDefinitionMap Map);
453  void mergeEntryMapBackEdge();
454  void mergePhiNodesBackEdge(const CFGBlock *Blk);
455 
456 private:
457  // Set to true when parsing capability expressions, which get translated
458  // inaccurately in order to hack around smart pointers etc.
459  static const bool CapabilityExprMode = true;
460 
461  til::MemRegionRef Arena;
462  til::Variable *SelfVar; // Variable to use for 'this'. May be null.
463 
464  til::SCFG *Scfg;
465  StatementMap SMap; // Map from Stmt to TIL Variables
466  LVarIndexMap LVarIdxMap; // Indices of clang local vars.
467  std::vector<til::BasicBlock *> BlockMap; // Map from clang to til BBs.
468  std::vector<BlockInfo> BBInfo; // Extra information per BB.
469  // Indexed by clang BlockID.
470 
471  LVarDefinitionMap CurrentLVarMap;
472  std::vector<til::Phi*> CurrentArguments;
473  std::vector<til::SExpr*> CurrentInstructions;
474  std::vector<til::Phi*> IncompleteArgs;
475  til::BasicBlock *CurrentBB;
476  BlockInfo *CurrentBlockInfo;
477 };
478 
479 
480 // Dump an SCFG to llvm::errs().
481 void printSCFG(CFGWalker &Walker);
482 
483 
484 } // end namespace threadSafety
485 
486 } // end namespace clang
487 
488 #endif // LLVM_CLANG_THREAD_SAFETY_COMMON_H
A call to an overloaded operator written using operator syntax.
Definition: ExprCXX.h:78
const PostOrderCFGView * getSortedGraph() const
bool equals(const CapabilityExpr &other) const
AdjacentBlocks::const_iterator const_pred_iterator
Definition: CFG.h:593
const Stmt * getStmt() const
Definition: CFG.h:122
Stmt - This represents one statement.
Definition: Stmt.h:66
bool partiallyMatches(const CapabilityExpr &other) const
unsigned getBlockID() const
Definition: CFG.h:729
StringRef P
T castAs() const
Convert to the specified CFGElement type, asserting that this CFGElement is of the desired type...
Definition: CFG.h:90
const CXXDestructorDecl * getDestructorDecl(ASTContext &astContext) const
Definition: CFG.cpp:4211
VarDecl - An instance of this class is created to represent a variable declaration or definition...
Definition: Decl.h:806
const til::SCFG * getCFG() const
const til::SExpr * sexpr() const
AnalysisDeclContext contains the context data for the function or method under analysis.
CFGAutomaticObjDtor - Represents C++ object destructor implicitly generated for automatic object or t...
Definition: CFG.h:253
AdjacentBlocks::const_iterator const_succ_iterator
Definition: CFG.h:600
bool alreadySet(const CFGBlock *Block)
Check if the bit for a CFGBlock has been already set.
Implements a set of CFGBlocks using a BitVector.
T * getAnalysis()
Return the specified analysis object, lazily running the analysis if necessary.
A builtin binary operation expression such as "x + y" or "x <= y".
Definition: Expr.h:2985
A basic block is part of an SCFG.
const VarDecl * getVarDecl() const
Definition: CFG.h:258
CastExpr - Base class for type casts, including both implicit casts (ImplicitCastExpr) and explicit c...
Definition: Expr.h:2710
Represents the this expression in C++.
Definition: ExprCXX.h:945
An SCFG is a control-flow graph.
bool init(AnalysisDeclContext &AC)
CFGBlock - Represents a single basic block in a source-level CFG.
Definition: CFG.h:422
bool equals(const til::SExpr *E1, const til::SExpr *E2)
ValueDecl - Represent the declaration of a variable (in which case it is an lvalue) a function (in wh...
Definition: Decl.h:627
Expr - This represents one expression.
Definition: Expr.h:106
CFG - Represents a source-level, intra-procedural CFG that represents the control-flow of a Stmt...
Definition: CFG.h:834
Represents a C++ destructor within a class.
Definition: DeclCXX.h:2620
Defines an enumeration for C++ overloaded operators.
void printSCFG(CFGWalker &Walker)
UnaryOperator - This represents the unary-expression&#39;s (except sizeof and alignof), the postinc/postdec operators from postfix-expression, and various extensions.
Definition: Expr.h:1717
bool matches(const CapabilityExpr &other) const
static bool compareExprs(const SExpr *E1, const SExpr *E2)
bool matchesUniv(const CapabilityExpr &CapE) const
TIL_BinaryOpcode
Opcode for binary arithmetic operations.
#define false
Definition: stdbool.h:33
std::pair< llvm::NoneType, bool > insert(const CFGBlock *Block)
Set the bit associated with a particular CFGBlock.
bool partiallyMatches(const til::SExpr *E1, const til::SExpr *E2)
Represents a call to a member function that may be written either with member call syntax (e...
Definition: ExprCXX.h:164
DeclStmt - Adaptor class for mixing declarations with statements and expressions. ...
Definition: Stmt.h:487
const Decl * getDecl() const
Encapsulates the lexical context of a function call.
CapabilityExpr(const til::SExpr *E, bool Neg)
Dataflow Directional Tag Classes.
til::BasicBlock * lookupBlock(const CFGBlock *B)
std::string toString(const til::SExpr *E)
ArraySubscriptExpr - [C99 6.5.2.1] Array Subscripting.
Definition: Expr.h:2121
AbstractConditionalOperator - An abstract base class for ConditionalOperator and BinaryConditionalOpe...
Definition: Expr.h:3227
const NamedDecl * getDecl() const
MemberExpr - [C99 6.5.2.3] Structure and Union Members.
Definition: Expr.h:2387
CallingContext(CallingContext *P, const NamedDecl *D=nullptr)
CallExpr - Represents a function call (C99 6.5.2.2, C++ [expr.call]).
Definition: Expr.h:2209
A reference to a declared variable, function, enum, etc.
Definition: Expr.h:956
const ValueDecl * valueDecl() const
Base class for AST nodes in the typed intermediate language.
bool matches(const til::SExpr *E1, const til::SExpr *E2)
static bool compareExprs(const SExpr *E1, const SExpr *E2)
NamedDecl - This represents a decl with a name.
Definition: Decl.h:245
llvm::DenseMap< const Stmt *, CFGBlock * > SMap
Definition: CFGStmtMap.cpp:22