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_THREAD_SAFETY_COMMON_H
23#define LLVM_CLANG_THREAD_SAFETY_COMMON_H
24
25#include "clang/Analysis/Analyses/PostOrderCFGView.h"
26#include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
27#include "clang/Analysis/AnalysisContext.h"
28#include "clang/Basic/OperatorKinds.h"
29
30#include <memory>
31#include <vector>
32
33
34namespace clang {
35namespace threadSafety {
36
37// This class defines the interface of a clang CFG Visitor.
38// CFGWalker will invoke the following methods.
39// Note that methods are not virtual; the visitor is templatized.
40class CFGVisitor {
41  // Enter the CFG for Decl D, and perform any initial setup operations.
42  void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {}
43
44  // Enter a CFGBlock.
45  void enterCFGBlock(const CFGBlock *B) {}
46
47  // Returns true if this visitor implements handlePredecessor
48  bool visitPredecessors() { return true; }
49
50  // Process a predecessor edge.
51  void handlePredecessor(const CFGBlock *Pred) {}
52
53  // Process a successor back edge to a previously visited block.
54  void handlePredecessorBackEdge(const CFGBlock *Pred) {}
55
56  // Called just before processing statements.
57  void enterCFGBlockBody(const CFGBlock *B) {}
58
59  // Process an ordinary statement.
60  void handleStatement(const Stmt *S) {}
61
62  // Process a destructor call
63  void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {}
64
65  // Called after all statements have been handled.
66  void exitCFGBlockBody(const CFGBlock *B) {}
67
68  // Return true
69  bool visitSuccessors() { return true; }
70
71  // Process a successor edge.
72  void handleSuccessor(const CFGBlock *Succ) {}
73
74  // Process a successor back edge to a previously visited block.
75  void handleSuccessorBackEdge(const CFGBlock *Succ) {}
76
77  // Leave a CFGBlock.
78  void exitCFGBlock(const CFGBlock *B) {}
79
80  // Leave the CFG, and perform any final cleanup operations.
81  void exitCFG(const CFGBlock *Last) {}
82};
83
84
85// Walks the clang CFG, and invokes methods on a given CFGVisitor.
86class CFGWalker {
87public:
88  CFGWalker() : CFGraph(nullptr), ACtx(nullptr), SortedGraph(nullptr) {}
89
90  // Initialize the CFGWalker.  This setup only needs to be done once, even
91  // if there are multiple passes over the CFG.
92  bool init(AnalysisDeclContext &AC) {
93    ACtx = &AC;
94    CFGraph = AC.getCFG();
95    if (!CFGraph)
96      return false;
97
98    // Ignore anonymous functions.
99    if (!dyn_cast_or_null<NamedDecl>(AC.getDecl()))
100      return false;
101
102    SortedGraph = AC.getAnalysis<PostOrderCFGView>();
103    if (!SortedGraph)
104      return false;
105
106    return true;
107  }
108
109  // Traverse the CFG, calling methods on V as appropriate.
110  template <class Visitor>
111  void walk(Visitor &V) {
112    PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph);
113
114    V.enterCFG(CFGraph, getDecl(), &CFGraph->getEntry());
115
116    for (const auto *CurrBlock : *SortedGraph) {
117      VisitedBlocks.insert(CurrBlock);
118
119      V.enterCFGBlock(CurrBlock);
120
121      // Process predecessors, handling back edges last
122      if (V.visitPredecessors()) {
123        SmallVector<CFGBlock*, 4> BackEdges;
124        // Process successors
125        for (CFGBlock::const_pred_iterator SI = CurrBlock->pred_begin(),
126                                           SE = CurrBlock->pred_end();
127             SI != SE; ++SI) {
128          if (*SI == nullptr)
129            continue;
130
131          if (!VisitedBlocks.alreadySet(*SI)) {
132            BackEdges.push_back(*SI);
133            continue;
134          }
135          V.handlePredecessor(*SI);
136        }
137
138        for (auto *Blk : BackEdges)
139          V.handlePredecessorBackEdge(Blk);
140      }
141
142      V.enterCFGBlockBody(CurrBlock);
143
144      // Process statements
145      for (const auto &BI : *CurrBlock) {
146        switch (BI.getKind()) {
147        case CFGElement::Statement: {
148          V.handleStatement(BI.castAs<CFGStmt>().getStmt());
149          break;
150        }
151        case CFGElement::AutomaticObjectDtor: {
152          CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>();
153          CXXDestructorDecl *DD = const_cast<CXXDestructorDecl*>(
154              AD.getDestructorDecl(ACtx->getASTContext()));
155          VarDecl *VD = const_cast<VarDecl*>(AD.getVarDecl());
156          V.handleDestructorCall(VD, DD);
157          break;
158        }
159        default:
160          break;
161        }
162      }
163
164      V.exitCFGBlockBody(CurrBlock);
165
166      // Process successors, handling back edges first.
167      if (V.visitSuccessors()) {
168        SmallVector<CFGBlock*, 8> ForwardEdges;
169
170        // Process successors
171        for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
172                                           SE = CurrBlock->succ_end();
173             SI != SE; ++SI) {
174          if (*SI == nullptr)
175            continue;
176
177          if (!VisitedBlocks.alreadySet(*SI)) {
178            ForwardEdges.push_back(*SI);
179            continue;
180          }
181          V.handleSuccessorBackEdge(*SI);
182        }
183
184        for (auto *Blk : ForwardEdges)
185          V.handleSuccessor(Blk);
186      }
187
188      V.exitCFGBlock(CurrBlock);
189    }
190    V.exitCFG(&CFGraph->getExit());
191  }
192
193  const CFG *getGraph() const { return CFGraph; }
194  CFG *getGraph() { return CFGraph; }
195
196  const NamedDecl *getDecl() const {
197    return dyn_cast<NamedDecl>(ACtx->getDecl());
198  }
199
200  const PostOrderCFGView *getSortedGraph() const { return SortedGraph; }
201
202private:
203  CFG *CFGraph;
204  AnalysisDeclContext *ACtx;
205  PostOrderCFGView *SortedGraph;
206};
207
208
209// Translate clang::Expr to til::SExpr.
210class SExprBuilder {
211public:
212  /// \brief Encapsulates the lexical context of a function call.  The lexical
213  /// context includes the arguments to the call, including the implicit object
214  /// argument.  When an attribute containing a mutex expression is attached to
215  /// a method, the expression may refer to formal parameters of the method.
216  /// Actual arguments must be substituted for formal parameters to derive
217  /// the appropriate mutex expression in the lexical context where the function
218  /// is called.  PrevCtx holds the context in which the arguments themselves
219  /// should be evaluated; multiple calling contexts can be chained together
220  /// by the lock_returned attribute.
221  struct CallingContext {
222    const NamedDecl *AttrDecl;  // The decl to which the attr is attached.
223    const Expr *SelfArg;        // Implicit object argument -- e.g. 'this'
224    unsigned NumArgs;           // Number of funArgs
225    const Expr *const *FunArgs; // Function arguments
226    CallingContext *Prev;       // The previous context; or 0 if none.
227    bool SelfArrow;             // is Self referred to with -> or .?
228
229    CallingContext(const NamedDecl *D = nullptr, const Expr *S = nullptr,
230                   unsigned N = 0, const Expr *const *A = nullptr,
231                   CallingContext *P = nullptr)
232        : AttrDecl(D), SelfArg(S), NumArgs(N), FunArgs(A), Prev(P),
233          SelfArrow(false)
234    {}
235  };
236
237  SExprBuilder(til::MemRegionRef A)
238      : Arena(A), SelfVar(nullptr), Scfg(nullptr), CurrentBB(nullptr),
239        CurrentBlockInfo(nullptr) {
240    // FIXME: we don't always have a self-variable.
241    SelfVar = new (Arena) til::Variable(nullptr);
242    SelfVar->setKind(til::Variable::VK_SFun);
243  }
244
245  // Translate a clang statement or expression to a TIL expression.
246  // Also performs substitution of variables; Ctx provides the context.
247  // Dispatches on the type of S.
248  til::SExpr *translate(const Stmt *S, CallingContext *Ctx);
249  til::SCFG  *buildCFG(CFGWalker &Walker);
250
251  til::SExpr *lookupStmt(const Stmt *S);
252
253  til::BasicBlock *lookupBlock(const CFGBlock *B) {
254    return BlockMap[B->getBlockID()];
255  }
256
257  const til::SCFG *getCFG() const { return Scfg; }
258  til::SCFG *getCFG() { return Scfg; }
259
260private:
261  til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE,
262                                   CallingContext *Ctx) ;
263  til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx);
264  til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx);
265  til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx);
266  til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME,
267                                         CallingContext *Ctx);
268  til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE,
269                                           CallingContext *Ctx);
270  til::SExpr *translateUnaryOperator(const UnaryOperator *UO,
271                                     CallingContext *Ctx);
272  til::SExpr *translateBinOp(til::TIL_BinaryOpcode Op,
273                             const BinaryOperator *BO,
274                             CallingContext *Ctx, bool Reverse = false);
275  til::SExpr *translateBinAssign(til::TIL_BinaryOpcode Op,
276                                 const BinaryOperator *BO,
277                                 CallingContext *Ctx, bool Assign = false);
278  til::SExpr *translateBinaryOperator(const BinaryOperator *BO,
279                                      CallingContext *Ctx);
280  til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx);
281  til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E,
282                                          CallingContext *Ctx);
283  til::SExpr *translateConditionalOperator(const ConditionalOperator *C,
284                                           CallingContext *Ctx);
285  til::SExpr *translateBinaryConditionalOperator(
286      const BinaryConditionalOperator *C, CallingContext *Ctx);
287
288  til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx);
289
290  // Map from statements in the clang CFG to SExprs in the til::SCFG.
291  typedef llvm::DenseMap<const Stmt*, til::SExpr*> StatementMap;
292
293  // Map from clang local variables to indices in a LVarDefinitionMap.
294  typedef llvm::DenseMap<const ValueDecl *, unsigned> LVarIndexMap;
295
296  // Map from local variable indices to SSA variables (or constants).
297  typedef std::pair<const ValueDecl *, til::SExpr *> NameVarPair;
298  typedef CopyOnWriteVector<NameVarPair> LVarDefinitionMap;
299
300  struct BlockInfo {
301    LVarDefinitionMap ExitMap;
302    bool HasBackEdges;
303    unsigned UnprocessedSuccessors;   // Successors yet to be processed
304    unsigned ProcessedPredecessors;   // Predecessors already processed
305
306    BlockInfo()
307        : HasBackEdges(false), UnprocessedSuccessors(0),
308          ProcessedPredecessors(0) {}
309    BlockInfo(BlockInfo &&RHS)
310        : ExitMap(std::move(RHS.ExitMap)),
311          HasBackEdges(RHS.HasBackEdges),
312          UnprocessedSuccessors(RHS.UnprocessedSuccessors),
313          ProcessedPredecessors(RHS.ProcessedPredecessors) {}
314
315    BlockInfo &operator=(BlockInfo &&RHS) {
316      if (this != &RHS) {
317        ExitMap = std::move(RHS.ExitMap);
318        HasBackEdges = RHS.HasBackEdges;
319        UnprocessedSuccessors = RHS.UnprocessedSuccessors;
320        ProcessedPredecessors = RHS.ProcessedPredecessors;
321      }
322      return *this;
323    }
324
325  private:
326    BlockInfo(const BlockInfo &) LLVM_DELETED_FUNCTION;
327    void operator=(const BlockInfo &) LLVM_DELETED_FUNCTION;
328  };
329
330  // We implement the CFGVisitor API
331  friend class CFGWalker;
332
333  void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First);
334  void enterCFGBlock(const CFGBlock *B);
335  bool visitPredecessors() { return true; }
336  void handlePredecessor(const CFGBlock *Pred);
337  void handlePredecessorBackEdge(const CFGBlock *Pred);
338  void enterCFGBlockBody(const CFGBlock *B);
339  void handleStatement(const Stmt *S);
340  void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD);
341  void exitCFGBlockBody(const CFGBlock *B);
342  bool visitSuccessors() { return true; }
343  void handleSuccessor(const CFGBlock *Succ);
344  void handleSuccessorBackEdge(const CFGBlock *Succ);
345  void exitCFGBlock(const CFGBlock *B);
346  void exitCFG(const CFGBlock *Last);
347
348  void insertStmt(const Stmt *S, til::SExpr *E) {
349    SMap.insert(std::make_pair(S, E));
350  }
351  til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD);
352
353  til::SExpr *addStatement(til::SExpr *E, const Stmt *S,
354                           const ValueDecl *VD = nullptr);
355  til::SExpr *lookupVarDecl(const ValueDecl *VD);
356  til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E);
357  til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E);
358
359  void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E);
360  void mergeEntryMap(LVarDefinitionMap Map);
361  void mergeEntryMapBackEdge();
362  void mergePhiNodesBackEdge(const CFGBlock *Blk);
363
364private:
365  til::MemRegionRef Arena;
366  til::Variable *SelfVar;       // Variable to use for 'this'.  May be null.
367  til::SCFG *Scfg;
368
369  StatementMap SMap;                       // Map from Stmt to TIL Variables
370  LVarIndexMap LVarIdxMap;                 // Indices of clang local vars.
371  std::vector<til::BasicBlock *> BlockMap; // Map from clang to til BBs.
372  std::vector<BlockInfo> BBInfo;           // Extra information per BB.
373                                           // Indexed by clang BlockID.
374  std::unique_ptr<SExprBuilder::CallingContext> CallCtx; // Root calling context
375
376  LVarDefinitionMap CurrentLVarMap;
377  std::vector<til::Variable*> CurrentArguments;
378  std::vector<til::Variable*> CurrentInstructions;
379  std::vector<til::Variable*> IncompleteArgs;
380  til::BasicBlock *CurrentBB;
381  BlockInfo *CurrentBlockInfo;
382};
383
384
385// Dump an SCFG to llvm::errs().
386void printSCFG(CFGWalker &Walker);
387
388
389} // end namespace threadSafety
390
391} // end namespace clang
392
393#endif  // LLVM_CLANG_THREAD_SAFETY_COMMON_H
394