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
36namespace clang {
37namespace threadSafety {
38
39
40// Various helper functions on til::SExpr
41namespace sx {
42
43inline bool equals(const til::SExpr *E1, const til::SExpr *E2) {
44  return til::EqualsComparator::compareExprs(E1, E2);
45}
46
47inline 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
59inline 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
69inline 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.
82class 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.
128class CFGWalker {
129public:
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
244private:
245  CFG *CFGraph;
246  AnalysisDeclContext *ACtx;
247  PostOrderCFGView *SortedGraph;
248};
249
250
251
252
253class 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
258private:
259  const til::SExpr* CapExpr;   ///< The capability expression.
260  bool Negated;                ///< True if this is a negative capability
261
262public:
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)
291      return nullptr;
292    if (auto *P = dyn_cast<til::Project>(CapExpr))
293      return P->clangDecl();
294    return nullptr;
295  }
296
297  std::string toString() const {
298    if (Negated)
299      return "!" + sx::toString(CapExpr);
300    return sx::toString(CapExpr);
301  }
302
303  bool shouldIgnore() const { return CapExpr == nullptr; }
304
305  bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); }
306
307  bool isUniversal() const { return sexpr() && isa<til::Wildcard>(sexpr()); }
308};
309
310
311
312// Translate clang::Expr to til::SExpr.
313class SExprBuilder {
314public:
315  /// \brief Encapsulates the lexical context of a function call.  The lexical
316  /// context includes the arguments to the call, including the implicit object
317  /// argument.  When an attribute containing a mutex expression is attached to
318  /// a method, the expression may refer to formal parameters of the method.
319  /// Actual arguments must be substituted for formal parameters to derive
320  /// the appropriate mutex expression in the lexical context where the function
321  /// is called.  PrevCtx holds the context in which the arguments themselves
322  /// should be evaluated; multiple calling contexts can be chained together
323  /// by the lock_returned attribute.
324  struct CallingContext {
325    CallingContext  *Prev;      // The previous context; or 0 if none.
326    const NamedDecl *AttrDecl;  // The decl to which the attr is attached.
327    const Expr *SelfArg;        // Implicit object argument -- e.g. 'this'
328    unsigned NumArgs;           // Number of funArgs
329    const Expr *const *FunArgs; // Function arguments
330    bool SelfArrow;             // is Self referred to with -> or .?
331
332    CallingContext(CallingContext *P, const NamedDecl *D = nullptr)
333        : Prev(P), AttrDecl(D), SelfArg(nullptr),
334          NumArgs(0), FunArgs(nullptr), SelfArrow(false)
335    {}
336  };
337
338  SExprBuilder(til::MemRegionRef A)
339      : Arena(A), SelfVar(nullptr), Scfg(nullptr), CurrentBB(nullptr),
340        CurrentBlockInfo(nullptr) {
341    // FIXME: we don't always have a self-variable.
342    SelfVar = new (Arena) til::Variable(nullptr);
343    SelfVar->setKind(til::Variable::VK_SFun);
344  }
345
346  // Translate a clang expression in an attribute to a til::SExpr.
347  // Constructs the context from D, DeclExp, and SelfDecl.
348  CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D,
349                                   const Expr *DeclExp, VarDecl *SelfD=nullptr);
350
351  CapabilityExpr translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx);
352
353  // Translate a clang statement or expression to a TIL expression.
354  // Also performs substitution of variables; Ctx provides the context.
355  // Dispatches on the type of S.
356  til::SExpr *translate(const Stmt *S, CallingContext *Ctx);
357  til::SCFG  *buildCFG(CFGWalker &Walker);
358
359  til::SExpr *lookupStmt(const Stmt *S);
360
361  til::BasicBlock *lookupBlock(const CFGBlock *B) {
362    return BlockMap[B->getBlockID()];
363  }
364
365  const til::SCFG *getCFG() const { return Scfg; }
366  til::SCFG *getCFG() { return Scfg; }
367
368private:
369  til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE,
370                                   CallingContext *Ctx) ;
371  til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx);
372  til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx);
373  til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx,
374                                const Expr *SelfE = nullptr);
375  til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME,
376                                         CallingContext *Ctx);
377  til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE,
378                                           CallingContext *Ctx);
379  til::SExpr *translateUnaryOperator(const UnaryOperator *UO,
380                                     CallingContext *Ctx);
381  til::SExpr *translateBinOp(til::TIL_BinaryOpcode Op,
382                             const BinaryOperator *BO,
383                             CallingContext *Ctx, bool Reverse = false);
384  til::SExpr *translateBinAssign(til::TIL_BinaryOpcode Op,
385                                 const BinaryOperator *BO,
386                                 CallingContext *Ctx, bool Assign = false);
387  til::SExpr *translateBinaryOperator(const BinaryOperator *BO,
388                                      CallingContext *Ctx);
389  til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx);
390  til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E,
391                                          CallingContext *Ctx);
392  til::SExpr *translateAbstractConditionalOperator(
393      const AbstractConditionalOperator *C, CallingContext *Ctx);
394
395  til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx);
396
397  // Map from statements in the clang CFG to SExprs in the til::SCFG.
398  typedef llvm::DenseMap<const Stmt*, til::SExpr*> StatementMap;
399
400  // Map from clang local variables to indices in a LVarDefinitionMap.
401  typedef llvm::DenseMap<const ValueDecl *, unsigned> LVarIndexMap;
402
403  // Map from local variable indices to SSA variables (or constants).
404  typedef std::pair<const ValueDecl *, til::SExpr *> NameVarPair;
405  typedef CopyOnWriteVector<NameVarPair> LVarDefinitionMap;
406
407  struct BlockInfo {
408    LVarDefinitionMap ExitMap;
409    bool HasBackEdges;
410    unsigned UnprocessedSuccessors;   // Successors yet to be processed
411    unsigned ProcessedPredecessors;   // Predecessors already processed
412
413    BlockInfo()
414        : HasBackEdges(false), UnprocessedSuccessors(0),
415          ProcessedPredecessors(0) {}
416    BlockInfo(BlockInfo &&RHS)
417        : ExitMap(std::move(RHS.ExitMap)),
418          HasBackEdges(RHS.HasBackEdges),
419          UnprocessedSuccessors(RHS.UnprocessedSuccessors),
420          ProcessedPredecessors(RHS.ProcessedPredecessors) {}
421
422    BlockInfo &operator=(BlockInfo &&RHS) {
423      if (this != &RHS) {
424        ExitMap = std::move(RHS.ExitMap);
425        HasBackEdges = RHS.HasBackEdges;
426        UnprocessedSuccessors = RHS.UnprocessedSuccessors;
427        ProcessedPredecessors = RHS.ProcessedPredecessors;
428      }
429      return *this;
430    }
431
432  private:
433    BlockInfo(const BlockInfo &) = delete;
434    void operator=(const BlockInfo &) = delete;
435  };
436
437  // We implement the CFGVisitor API
438  friend class CFGWalker;
439
440  void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First);
441  void enterCFGBlock(const CFGBlock *B);
442  bool visitPredecessors() { return true; }
443  void handlePredecessor(const CFGBlock *Pred);
444  void handlePredecessorBackEdge(const CFGBlock *Pred);
445  void enterCFGBlockBody(const CFGBlock *B);
446  void handleStatement(const Stmt *S);
447  void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD);
448  void exitCFGBlockBody(const CFGBlock *B);
449  bool visitSuccessors() { return true; }
450  void handleSuccessor(const CFGBlock *Succ);
451  void handleSuccessorBackEdge(const CFGBlock *Succ);
452  void exitCFGBlock(const CFGBlock *B);
453  void exitCFG(const CFGBlock *Last);
454
455  void insertStmt(const Stmt *S, til::SExpr *E) {
456    SMap.insert(std::make_pair(S, E));
457  }
458  til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD);
459
460  til::SExpr *addStatement(til::SExpr *E, const Stmt *S,
461                           const ValueDecl *VD = nullptr);
462  til::SExpr *lookupVarDecl(const ValueDecl *VD);
463  til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E);
464  til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E);
465
466  void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E);
467  void mergeEntryMap(LVarDefinitionMap Map);
468  void mergeEntryMapBackEdge();
469  void mergePhiNodesBackEdge(const CFGBlock *Blk);
470
471private:
472  // Set to true when parsing capability expressions, which get translated
473  // inaccurately in order to hack around smart pointers etc.
474  static const bool CapabilityExprMode = true;
475
476  til::MemRegionRef Arena;
477  til::Variable *SelfVar;       // Variable to use for 'this'.  May be null.
478
479  til::SCFG *Scfg;
480  StatementMap SMap;                       // Map from Stmt to TIL Variables
481  LVarIndexMap LVarIdxMap;                 // Indices of clang local vars.
482  std::vector<til::BasicBlock *> BlockMap; // Map from clang to til BBs.
483  std::vector<BlockInfo> BBInfo;           // Extra information per BB.
484                                           // Indexed by clang BlockID.
485
486  LVarDefinitionMap CurrentLVarMap;
487  std::vector<til::Phi*>   CurrentArguments;
488  std::vector<til::SExpr*> CurrentInstructions;
489  std::vector<til::Phi*>   IncompleteArgs;
490  til::BasicBlock *CurrentBB;
491  BlockInfo *CurrentBlockInfo;
492};
493
494
495// Dump an SCFG to llvm::errs().
496void printSCFG(CFGWalker &Walker);
497
498
499} // end namespace threadSafety
500
501} // end namespace clang
502
503#endif  // LLVM_CLANG_THREAD_SAFETY_COMMON_H
504