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