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