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/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 
equals(const til::SExpr * E1,const til::SExpr * E2)63 inline bool equals(const til::SExpr *E1, const til::SExpr *E2) {
64   return til::EqualsComparator::compareExprs(E1, E2);
65 }
66 
matches(const til::SExpr * E1,const til::SExpr * E2)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 
76   return til::MatchComparator::compareExprs(E1, E2);
77 }
78 
partiallyMatches(const til::SExpr * E1,const til::SExpr * E2)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 
toString(const til::SExpr * E)89 inline std::string toString(const til::SExpr *E) {
90   std::stringstream ss;
91   til::StdPrinter::print(E, 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.
enterCFG(CFG * Cfg,const NamedDecl * D,const CFGBlock * First)102   void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {}
103 
104   // Enter a CFGBlock.
enterCFGBlock(const CFGBlock * B)105   void enterCFGBlock(const CFGBlock *B) {}
106 
107   // Returns true if this visitor implements handlePredecessor
visitPredecessors()108   bool visitPredecessors() { return true; }
109 
110   // Process a predecessor edge.
handlePredecessor(const CFGBlock * Pred)111   void handlePredecessor(const CFGBlock *Pred) {}
112 
113   // Process a successor back edge to a previously visited block.
handlePredecessorBackEdge(const CFGBlock * Pred)114   void handlePredecessorBackEdge(const CFGBlock *Pred) {}
115 
116   // Called just before processing statements.
enterCFGBlockBody(const CFGBlock * B)117   void enterCFGBlockBody(const CFGBlock *B) {}
118 
119   // Process an ordinary statement.
handleStatement(const Stmt * S)120   void handleStatement(const Stmt *S) {}
121 
122   // Process a destructor call
handleDestructorCall(const VarDecl * VD,const CXXDestructorDecl * DD)123   void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {}
124 
125   // Called after all statements have been handled.
exitCFGBlockBody(const CFGBlock * B)126   void exitCFGBlockBody(const CFGBlock *B) {}
127 
128   // Return true
visitSuccessors()129   bool visitSuccessors() { return true; }
130 
131   // Process a successor edge.
handleSuccessor(const CFGBlock * Succ)132   void handleSuccessor(const CFGBlock *Succ) {}
133 
134   // Process a successor back edge to a previously visited block.
handleSuccessorBackEdge(const CFGBlock * Succ)135   void handleSuccessorBackEdge(const CFGBlock *Succ) {}
136 
137   // Leave a CFGBlock.
exitCFGBlock(const CFGBlock * B)138   void exitCFGBlock(const CFGBlock *B) {}
139 
140   // Leave the CFG, and perform any final cleanup operations.
exitCFG(const CFGBlock * Last)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.
init(AnalysisDeclContext & AC)151   bool init(AnalysisDeclContext &AC) {
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>
walk(Visitor & V)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()) {
206         case CFGElement::Statement:
207           V.handleStatement(BI.castAs<CFGStmt>().getStmt());
208           break;
209 
210         case CFGElement::AutomaticObjectDtor: {
211           CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>();
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 
getGraph()252   const CFG *getGraph() const { return CFGraph; }
getGraph()253   CFG *getGraph() { return CFGraph; }
254 
getDecl()255   const NamedDecl *getDecl() const {
256     return dyn_cast<NamedDecl>(ACtx->getDecl());
257   }
258 
getSortedGraph()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.
270 class CapabilityExpr {
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:
CapabilityExpr(const til::SExpr * E,bool Neg)279   CapabilityExpr(const til::SExpr *E, bool Neg) : CapExpr(E), Negated(Neg) {}
280 
sexpr()281   const til::SExpr* sexpr() const { return CapExpr; }
negative()282   bool negative() const { return Negated; }
283 
284   CapabilityExpr operator!() const {
285     return CapabilityExpr(CapExpr, !Negated);
286   }
287 
equals(const CapabilityExpr & other)288   bool equals(const CapabilityExpr &other) const {
289     return (Negated == other.Negated) && sx::equals(CapExpr, other.CapExpr);
290   }
291 
matches(const CapabilityExpr & other)292   bool matches(const CapabilityExpr &other) const {
293     return (Negated == other.Negated) && sx::matches(CapExpr, other.CapExpr);
294   }
295 
matchesUniv(const CapabilityExpr & CapE)296   bool matchesUniv(const CapabilityExpr &CapE) const {
297     return isUniversal() || matches(CapE);
298   }
299 
partiallyMatches(const CapabilityExpr & other)300   bool partiallyMatches(const CapabilityExpr &other) const {
301     return (Negated == other.Negated) &&
302             sx::partiallyMatches(CapExpr, other.CapExpr);
303   }
304 
valueDecl()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 
toString()315   std::string toString() const {
316     if (Negated)
317       return "!" + sx::toString(CapExpr);
318     return sx::toString(CapExpr);
319   }
320 
shouldIgnore()321   bool shouldIgnore() const { return CapExpr == nullptr; }
322 
isInvalid()323   bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); }
324 
isUniversal()325   bool isUniversal() const { return sexpr() && isa<til::Wildcard>(sexpr()); }
326 };
327 
328 // Translate clang::Expr to til::SExpr.
329 class SExprBuilder {
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.
342     CallingContext  *Prev;
343 
344     // The decl to which the attr is attached.
345     const NamedDecl *AttrDecl;
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)
PrevCallingContext360         : Prev(P), AttrDecl(D) {}
361   };
362 
SExprBuilder(til::MemRegionRef A)363   SExprBuilder(til::MemRegionRef A) : Arena(A) {
364     // FIXME: we don't always have a self-variable.
365     SelfVar = new (Arena) til::Variable(nullptr);
366     SelfVar->setKind(til::Variable::VK_SFun);
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 
lookupBlock(const CFGBlock * B)384   til::BasicBlock *lookupBlock(const CFGBlock *B) {
385     return BlockMap[B->getBlockID()];
386   }
387 
getCFG()388   const til::SCFG *getCFG() const { return Scfg; }
getCFG()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(
421       const AbstractConditionalOperator *C, CallingContext *Ctx);
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 *>;
433   using LVarDefinitionMap = CopyOnWriteVector<NameVarPair>;
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);
visitPredecessors()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);
visitSuccessors()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 
insertStmt(const Stmt * S,til::SExpr * E)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
521