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
42 namespace clang {
43
44 class AbstractConditionalOperator;
45 class ArraySubscriptExpr;
46 class BinaryOperator;
47 class CallExpr;
48 class CastExpr;
49 class CXXDestructorDecl;
50 class CXXMemberCallExpr;
51 class CXXOperatorCallExpr;
52 class CXXThisExpr;
53 class DeclRefExpr;
54 class DeclStmt;
55 class Expr;
56 class MemberExpr;
57 class Stmt;
58 class UnaryOperator;
59
60 namespace threadSafety {
61
62 // Various helper functions on til::SExpr
63 namespace sx {
64
equals(const til::SExpr * E1,const til::SExpr * E2)65 inline bool equals(const til::SExpr *E1, const til::SExpr *E2) {
66 return til::EqualsComparator::compareExprs(E1, E2);
67 }
68
matches(const til::SExpr * E1,const til::SExpr * E2)69 inline 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
partiallyMatches(const til::SExpr * E1,const til::SExpr * E2)81 inline 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
toString(const til::SExpr * E)91 inline 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.
102 class CFGVisitor {
103 // Enter the CFG for Decl D, and perform any initial setup operations.
enterCFG(CFG * Cfg,const NamedDecl * D,const CFGBlock * First)104 void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {}
105
106 // Enter a CFGBlock.
enterCFGBlock(const CFGBlock * B)107 void enterCFGBlock(const CFGBlock *B) {}
108
109 // Returns true if this visitor implements handlePredecessor
visitPredecessors()110 bool visitPredecessors() { return true; }
111
112 // Process a predecessor edge.
handlePredecessor(const CFGBlock * Pred)113 void handlePredecessor(const CFGBlock *Pred) {}
114
115 // Process a successor back edge to a previously visited block.
handlePredecessorBackEdge(const CFGBlock * Pred)116 void handlePredecessorBackEdge(const CFGBlock *Pred) {}
117
118 // Called just before processing statements.
enterCFGBlockBody(const CFGBlock * B)119 void enterCFGBlockBody(const CFGBlock *B) {}
120
121 // Process an ordinary statement.
handleStatement(const Stmt * S)122 void handleStatement(const Stmt *S) {}
123
124 // Process a destructor call
handleDestructorCall(const VarDecl * VD,const CXXDestructorDecl * DD)125 void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {}
126
127 // Called after all statements have been handled.
exitCFGBlockBody(const CFGBlock * B)128 void exitCFGBlockBody(const CFGBlock *B) {}
129
130 // Return true
visitSuccessors()131 bool visitSuccessors() { return true; }
132
133 // Process a successor edge.
handleSuccessor(const CFGBlock * Succ)134 void handleSuccessor(const CFGBlock *Succ) {}
135
136 // Process a successor back edge to a previously visited block.
handleSuccessorBackEdge(const CFGBlock * Succ)137 void handleSuccessorBackEdge(const CFGBlock *Succ) {}
138
139 // Leave a CFGBlock.
exitCFGBlock(const CFGBlock * B)140 void exitCFGBlock(const CFGBlock *B) {}
141
142 // Leave the CFG, and perform any final cleanup operations.
exitCFG(const CFGBlock * Last)143 void exitCFG(const CFGBlock *Last) {}
144 };
145
146 // Walks the clang CFG, and invokes methods on a given CFGVisitor.
147 class CFGWalker {
148 public:
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.
init(AnalysisDeclContext & AC)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>
walk(Visitor & V)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
getGraph()254 const CFG *getGraph() const { return CFGraph; }
getGraph()255 CFG *getGraph() { return CFGraph; }
256
getDecl()257 const NamedDecl *getDecl() const {
258 return dyn_cast<NamedDecl>(ACtx->getDecl());
259 }
260
getSortedGraph()261 const PostOrderCFGView *getSortedGraph() const { return SortedGraph; }
262
263 private:
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.
272 class CapabilityExpr {
273 private:
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
280 public:
CapabilityExpr()281 CapabilityExpr() : CapExpr(nullptr, false) {}
CapabilityExpr(const til::SExpr * E,StringRef Kind,bool Neg)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
sexpr()288 const til::SExpr *sexpr() const { return CapExpr.getPointer(); }
getKind()289 StringRef getKind() const { return CapKind; }
negative()290 bool negative() const { return CapExpr.getInt(); }
291
292 CapabilityExpr operator!() const {
293 return CapabilityExpr(CapExpr.getPointer(), CapKind, !CapExpr.getInt());
294 }
295
equals(const CapabilityExpr & other)296 bool equals(const CapabilityExpr &other) const {
297 return (negative() == other.negative()) &&
298 sx::equals(sexpr(), other.sexpr());
299 }
300
matches(const CapabilityExpr & other)301 bool matches(const CapabilityExpr &other) const {
302 return (negative() == other.negative()) &&
303 sx::matches(sexpr(), other.sexpr());
304 }
305
matchesUniv(const CapabilityExpr & CapE)306 bool matchesUniv(const CapabilityExpr &CapE) const {
307 return isUniversal() || matches(CapE);
308 }
309
partiallyMatches(const CapabilityExpr & other)310 bool partiallyMatches(const CapabilityExpr &other) const {
311 return (negative() == other.negative()) &&
312 sx::partiallyMatches(sexpr(), other.sexpr());
313 }
314
valueDecl()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
toString()325 std::string toString() const {
326 if (negative())
327 return "!" + sx::toString(sexpr());
328 return sx::toString(sexpr());
329 }
330
shouldIgnore()331 bool shouldIgnore() const { return sexpr() == nullptr; }
332
isInvalid()333 bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); }
334
isUniversal()335 bool isUniversal() const { return sexpr() && isa<til::Wildcard>(sexpr()); }
336 };
337
338 // Translate clang::Expr to til::SExpr.
339 class SExprBuilder {
340 public:
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)
PrevCallingContext370 : Prev(P), AttrDecl(D) {}
371 };
372
SExprBuilder(til::MemRegionRef A)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
lookupBlock(const CFGBlock * B)402 til::BasicBlock *lookupBlock(const CFGBlock *B) {
403 return BlockMap[B->getBlockID()];
404 }
405
getCFG()406 const til::SCFG *getCFG() const { return Scfg; }
getCFG()407 til::SCFG *getCFG() { return Scfg; }
408
409 private:
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);
visitPredecessors()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);
visitSuccessors()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
insertStmt(const Stmt * S,til::SExpr * E)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
498 private:
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().
531 void printSCFG(CFGWalker &Walker);
532
533 } // namespace threadSafety
534 } // namespace clang
535
536 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H
537