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/AnalysisDeclContext.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 || 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.
315class SExprBuilder {
316public:
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
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
363  til::BasicBlock *lookupBlock(const CFGBlock *B) {
364    return BlockMap[B->getBlockID()];
365  }
366
367  const til::SCFG *getCFG() const { return Scfg; }
368  til::SCFG *getCFG() { return Scfg; }
369
370private:
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
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
456private:
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().
481void printSCFG(CFGWalker &Walker);
482
483
484} // end namespace threadSafety
485
486} // end namespace clang
487
488#endif  // LLVM_CLANG_THREAD_SAFETY_COMMON_H
489