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
43namespace clang {
44
45class AbstractConditionalOperator;
46class ArraySubscriptExpr;
47class BinaryOperator;
48class CallExpr;
49class CastExpr;
50class CXXDestructorDecl;
51class CXXMemberCallExpr;
52class CXXOperatorCallExpr;
53class CXXThisExpr;
54class DeclRefExpr;
55class DeclStmt;
56class Expr;
57class MemberExpr;
58class Stmt;
59class UnaryOperator;
60
61namespace threadSafety {
62
63// Various helper functions on til::SExpr
64namespace sx {
65
66inline bool equals(const til::SExpr *E1, const til::SExpr *E2) {
67 return til::EqualsComparator::compareExprs(E1, E2);
68}
69
70inline 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>(Val: E1))
75 return isa<til::Wildcard>(Val: E2);
76 if (isa<til::Wildcard>(Val: E2))
77 return isa<til::Wildcard>(Val: E1);
78
79 return til::MatchComparator::compareExprs(E1, E2);
80}
81
82inline bool partiallyMatches(const til::SExpr *E1, const til::SExpr *E2) {
83 const auto *PE1 = dyn_cast_or_null<til::Project>(Val: E1);
84 if (!PE1)
85 return false;
86 const auto *PE2 = dyn_cast_or_null<til::Project>(Val: E2);
87 if (!PE2)
88 return false;
89 return PE1->clangDecl() == PE2->clangDecl();
90}
91
92inline std::string toString(const til::SExpr *E) {
93 std::stringstream ss;
94 til::StdPrinter::print(E, SS&: 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.
103class CFGVisitor {
104 // Enter the CFG for Decl D, and perform any initial setup operations.
105 void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {}
106
107 // Enter a CFGBlock.
108 void enterCFGBlock(const CFGBlock *B) {}
109
110 // Returns true if this visitor implements handlePredecessor
111 bool visitPredecessors() { return true; }
112
113 // Process a predecessor edge.
114 void handlePredecessor(const CFGBlock *Pred) {}
115
116 // Process a successor back edge to a previously visited block.
117 void handlePredecessorBackEdge(const CFGBlock *Pred) {}
118
119 // Called just before processing statements.
120 void enterCFGBlockBody(const CFGBlock *B) {}
121
122 // Process an ordinary statement.
123 void handleStatement(const Stmt *S) {}
124
125 // Process a destructor call
126 void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {}
127
128 // Called after all statements have been handled.
129 void exitCFGBlockBody(const CFGBlock *B) {}
130
131 // Return true
132 bool visitSuccessors() { return true; }
133
134 // Process a successor edge.
135 void handleSuccessor(const CFGBlock *Succ) {}
136
137 // Process a successor back edge to a previously visited block.
138 void handleSuccessorBackEdge(const CFGBlock *Succ) {}
139
140 // Leave a CFGBlock.
141 void exitCFGBlock(const CFGBlock *B) {}
142
143 // Leave the CFG, and perform any final cleanup operations.
144 void exitCFG(const CFGBlock *Last) {}
145};
146
147// Walks the clang CFG, and invokes methods on a given CFGVisitor.
148class CFGWalker {
149public:
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.
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>(Val: 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>
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(Block: 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(Block: *SI)) {
194 BackEdges.push_back(Elt: *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(astContext&: 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(Block: *SI)) {
240 ForwardEdges.push_back(Elt: *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
255 const CFG *getGraph() const { return CFGraph; }
256 CFG *getGraph() { return CFGraph; }
257
258 const NamedDecl *getDecl() const {
259 return dyn_cast<NamedDecl>(Val: ACtx->getDecl());
260 }
261
262 const PostOrderCFGView *getSortedGraph() const { return SortedGraph; }
263
264private:
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.
273class CapabilityExpr {
274private:
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
284public:
285 CapabilityExpr() : CapExpr(nullptr, 0) {}
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
296 const til::SExpr *sexpr() const { return CapExpr.getPointer(); }
297 StringRef getKind() const { return CapKind; }
298 bool negative() const { return CapExpr.getInt() & FlagNegative; }
299 bool reentrant() const { return CapExpr.getInt() & FlagReentrant; }
300
301 CapabilityExpr operator!() const {
302 return CapabilityExpr(CapExpr.getPointer(), CapKind, !negative(),
303 reentrant());
304 }
305
306 bool equals(const CapabilityExpr &other) const {
307 return (negative() == other.negative()) &&
308 sx::equals(E1: sexpr(), E2: other.sexpr());
309 }
310
311 bool matches(const CapabilityExpr &other) const {
312 return (negative() == other.negative()) &&
313 sx::matches(E1: sexpr(), E2: other.sexpr());
314 }
315
316 bool matchesUniv(const CapabilityExpr &CapE) const {
317 return isUniversal() || matches(other: CapE);
318 }
319
320 bool partiallyMatches(const CapabilityExpr &other) const {
321 return (negative() == other.negative()) &&
322 sx::partiallyMatches(E1: sexpr(), E2: other.sexpr());
323 }
324
325 const ValueDecl* valueDecl() const {
326 if (negative() || sexpr() == nullptr)
327 return nullptr;
328 if (const auto *P = dyn_cast<til::Project>(Val: sexpr()))
329 return P->clangDecl();
330 if (const auto *P = dyn_cast<til::LiteralPtr>(Val: sexpr()))
331 return P->clangDecl();
332 return nullptr;
333 }
334
335 std::string toString() const {
336 if (negative())
337 return "!" + sx::toString(E: sexpr());
338 return sx::toString(E: sexpr());
339 }
340
341 bool shouldIgnore() const { return sexpr() == nullptr; }
342
343 bool isInvalid() const { return isa_and_nonnull<til::Undefined>(Val: sexpr()); }
344
345 bool isUniversal() const { return isa_and_nonnull<til::Wildcard>(Val: sexpr()); }
346};
347
348// Translate clang::Expr to til::SExpr.
349class SExprBuilder {
350public:
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)
380 : Prev(P), AttrDecl(D) {}
381 };
382
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
408 til::BasicBlock *lookupBlock(const CFGBlock *B) {
409 return BlockMap[B->getBlockID()];
410 }
411
412 const til::SCFG *getCFG() const { return Scfg; }
413 til::SCFG *getCFG() { return Scfg; }
414
415private:
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);
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);
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
489 void insertStmt(const Stmt *S, til::SExpr *E) {
490 SMap.insert(KV: std::make_pair(x&: S, y&: 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
504private:
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().
538void printSCFG(CFGWalker &Walker);
539#endif // NDEBUG
540
541} // namespace threadSafety
542} // namespace clang
543
544#endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H
545

source code of clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h