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