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