1//===- ThreadSafety.cpp ---------------------------------------------------===//
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// A intra-procedural analysis for thread safety (e.g. deadlocks and race
10// conditions), based off of an annotation system.
11//
12// See http://clang.llvm.org/docs/ThreadSafetyAnalysis.html
13// for more information.
14//
15//===----------------------------------------------------------------------===//
16
17#include "clang/Analysis/Analyses/ThreadSafety.h"
18#include "clang/AST/Attr.h"
19#include "clang/AST/Decl.h"
20#include "clang/AST/DeclCXX.h"
21#include "clang/AST/DeclGroup.h"
22#include "clang/AST/Expr.h"
23#include "clang/AST/ExprCXX.h"
24#include "clang/AST/OperationKinds.h"
25#include "clang/AST/Stmt.h"
26#include "clang/AST/StmtVisitor.h"
27#include "clang/AST/Type.h"
28#include "clang/Analysis/Analyses/PostOrderCFGView.h"
29#include "clang/Analysis/Analyses/ThreadSafetyCommon.h"
30#include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
31#include "clang/Analysis/Analyses/ThreadSafetyUtil.h"
32#include "clang/Analysis/AnalysisDeclContext.h"
33#include "clang/Analysis/CFG.h"
34#include "clang/Basic/Builtins.h"
35#include "clang/Basic/LLVM.h"
36#include "clang/Basic/OperatorKinds.h"
37#include "clang/Basic/SourceLocation.h"
38#include "clang/Basic/Specifiers.h"
39#include "llvm/ADT/DenseMap.h"
40#include "llvm/ADT/ImmutableMap.h"
41#include "llvm/ADT/STLExtras.h"
42#include "llvm/ADT/ScopeExit.h"
43#include "llvm/ADT/SmallVector.h"
44#include "llvm/ADT/StringRef.h"
45#include "llvm/Support/Allocator.h"
46#include "llvm/Support/Casting.h"
47#include "llvm/Support/ErrorHandling.h"
48#include "llvm/Support/TrailingObjects.h"
49#include "llvm/Support/raw_ostream.h"
50#include <cassert>
51#include <functional>
52#include <iterator>
53#include <memory>
54#include <optional>
55#include <string>
56#include <utility>
57#include <vector>
58
59using namespace clang;
60using namespace threadSafety;
61
62// Key method definition
63ThreadSafetyHandler::~ThreadSafetyHandler() = default;
64
65/// True if capability attributes on \p Param describe the function reached
66/// through it rather than the argument bound to it.
67///
68/// Sema accepts capability attributes on a parameter for two unrelated
69/// purposes: a scoped-lockable parameter, where the attributes describe the
70/// locks the passed scope object holds, and a parameter naming a function to
71/// call -- a function pointer or a function reference -- where they describe
72/// the requirements of the function called through it.
73static bool isCallbackParam(const ParmVarDecl *Param) {
74 QualType T = Param->getType().getNonReferenceType();
75 return T->isFunctionPointerType() || T->isFunctionType();
76}
77
78/// Issue a warning about an invalid lock expression
79static void warnInvalidLock(ThreadSafetyHandler &Handler,
80 const Expr *MutexExp, const NamedDecl *D,
81 const Expr *DeclExp, StringRef Kind) {
82 SourceLocation Loc;
83 if (DeclExp)
84 Loc = DeclExp->getExprLoc();
85
86 // FIXME: add a note about the attribute location in MutexExp or D
87 if (Loc.isValid())
88 Handler.handleInvalidLockExp(Loc);
89}
90
91namespace {
92
93/// A set of CapabilityExpr objects, which are compiled from thread safety
94/// attributes on a function.
95class CapExprSet : public SmallVector<CapabilityExpr, 4> {
96public:
97 /// Push M onto list, but discard duplicates.
98 void push_back_nodup(const CapabilityExpr &CapE) {
99 if (llvm::none_of(Range&: *this, P: [=](const CapabilityExpr &CapE2) {
100 return CapE.equals(other: CapE2);
101 }))
102 push_back(Elt: CapE);
103 }
104};
105
106class FactManager;
107class FactSet;
108
109/// This is a helper class that stores a fact that is known at a
110/// particular point in program execution. Currently, a fact is a capability,
111/// along with additional information, such as where it was acquired, whether
112/// it is exclusive or shared, etc.
113class FactEntry : public CapabilityExpr {
114public:
115 enum FactEntryKind { Lockable, ScopedLockable };
116
117 /// Where a fact comes from.
118 enum SourceKind {
119 Acquired, ///< The fact has been directly acquired.
120 Asserted, ///< The fact has been asserted to be held.
121 Declared, ///< The fact is assumed to be held by callers.
122 Managed, ///< The fact has been acquired through a scoped capability.
123 };
124
125private:
126 const FactEntryKind Kind : 8;
127
128 /// Exclusive or shared.
129 LockKind LKind : 8;
130
131 /// How it was acquired.
132 SourceKind Source : 8;
133
134 /// Where it was acquired.
135 SourceLocation AcquireLoc;
136
137protected:
138 ~FactEntry() = default;
139
140public:
141 FactEntry(FactEntryKind FK, const CapabilityExpr &CE, LockKind LK,
142 SourceLocation Loc, SourceKind Src)
143 : CapabilityExpr(CE), Kind(FK), LKind(LK), Source(Src), AcquireLoc(Loc) {}
144
145 LockKind kind() const { return LKind; }
146 SourceLocation loc() const { return AcquireLoc; }
147 FactEntryKind getFactEntryKind() const { return Kind; }
148
149 bool asserted() const { return Source == Asserted; }
150 bool declared() const { return Source == Declared; }
151 bool managed() const { return Source == Managed; }
152
153 virtual void
154 handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan,
155 SourceLocation JoinLoc, LockErrorKind LEK,
156 ThreadSafetyHandler &Handler) const = 0;
157 virtual void handleLock(FactSet &FSet, FactManager &FactMan,
158 const FactEntry &entry,
159 ThreadSafetyHandler &Handler) const = 0;
160 virtual void handleUnlock(FactSet &FSet, FactManager &FactMan,
161 const CapabilityExpr &Cp, SourceLocation UnlockLoc,
162 bool FullyRemove,
163 ThreadSafetyHandler &Handler) const = 0;
164
165 // Return true if LKind >= LK, where exclusive > shared
166 bool isAtLeast(LockKind LK) const {
167 return (LKind == LK_Exclusive) || (LK == LK_Shared);
168 }
169};
170
171using FactID = unsigned short;
172
173/// FactManager manages the memory for all facts that are created during
174/// the analysis of a single routine.
175class FactManager {
176private:
177 llvm::BumpPtrAllocator &Alloc;
178 std::vector<const FactEntry *> Facts;
179
180public:
181 FactManager(llvm::BumpPtrAllocator &Alloc) : Alloc(Alloc) {}
182
183 template <typename T, typename... ArgTypes>
184 T *createFact(ArgTypes &&...Args) {
185 static_assert(std::is_trivially_destructible_v<T>);
186 return T::create(Alloc, std::forward<ArgTypes>(Args)...);
187 }
188
189 FactID newFact(const FactEntry *Entry) {
190 Facts.push_back(x: Entry);
191 assert(Facts.size() - 1 <= std::numeric_limits<FactID>::max() &&
192 "FactID space exhausted");
193 return static_cast<unsigned short>(Facts.size() - 1);
194 }
195
196 const FactEntry &operator[](FactID F) const { return *Facts[F]; }
197};
198
199/// A FactSet is the set of facts that are known to be true at a
200/// particular program point. FactSets must be small, because they are
201/// frequently copied, and are thus implemented as a set of indices into a
202/// table maintained by a FactManager. A typical FactSet only holds 1 or 2
203/// locks, so we can get away with doing a linear search for lookup. Note
204/// that a hashtable or map is inappropriate in this case, because lookups
205/// may involve partial pattern matches, rather than exact matches.
206class FactSet {
207private:
208 using FactVec = SmallVector<FactID, 4>;
209
210 FactVec FactIDs;
211
212public:
213 using iterator = FactVec::iterator;
214 using const_iterator = FactVec::const_iterator;
215
216 iterator begin() { return FactIDs.begin(); }
217 const_iterator begin() const { return FactIDs.begin(); }
218
219 iterator end() { return FactIDs.end(); }
220 const_iterator end() const { return FactIDs.end(); }
221
222 bool isEmpty() const { return FactIDs.size() == 0; }
223
224 // Return true if the set contains only negative facts
225 bool isEmpty(FactManager &FactMan) const {
226 for (const auto FID : *this) {
227 if (!FactMan[FID].negative())
228 return false;
229 }
230 return true;
231 }
232
233 void addLockByID(FactID ID) { FactIDs.push_back(Elt: ID); }
234
235 FactID addLock(FactManager &FM, const FactEntry *Entry) {
236 FactID F = FM.newFact(Entry);
237 FactIDs.push_back(Elt: F);
238 return F;
239 }
240
241 bool removeLock(FactManager& FM, const CapabilityExpr &CapE) {
242 unsigned n = FactIDs.size();
243 if (n == 0)
244 return false;
245
246 for (unsigned i = 0; i < n-1; ++i) {
247 if (FM[FactIDs[i]].matches(other: CapE)) {
248 FactIDs[i] = FactIDs[n-1];
249 FactIDs.pop_back();
250 return true;
251 }
252 }
253 if (FM[FactIDs[n-1]].matches(other: CapE)) {
254 FactIDs.pop_back();
255 return true;
256 }
257 return false;
258 }
259
260 std::optional<FactID> replaceLock(FactManager &FM, iterator It,
261 const FactEntry *Entry) {
262 if (It == end())
263 return std::nullopt;
264 FactID F = FM.newFact(Entry);
265 *It = F;
266 return F;
267 }
268
269 std::optional<FactID> replaceLock(FactManager &FM, const CapabilityExpr &CapE,
270 const FactEntry *Entry) {
271 return replaceLock(FM, It: findLockIter(FM, CapE), Entry);
272 }
273
274 iterator findLockIter(FactManager &FM, const CapabilityExpr &CapE) {
275 return llvm::find_if(Range&: *this,
276 P: [&](FactID ID) { return FM[ID].matches(other: CapE); });
277 }
278
279 const FactEntry *findLock(FactManager &FM, const CapabilityExpr &CapE) const {
280 auto I =
281 llvm::find_if(Range: *this, P: [&](FactID ID) { return FM[ID].matches(other: CapE); });
282 return I != end() ? &FM[*I] : nullptr;
283 }
284
285 const FactEntry *findLockUniv(FactManager &FM,
286 const CapabilityExpr &CapE) const {
287 auto I = llvm::find_if(
288 Range: *this, P: [&](FactID ID) -> bool { return FM[ID].matchesUniv(CapE); });
289 return I != end() ? &FM[*I] : nullptr;
290 }
291
292 const FactEntry *findPartialMatch(FactManager &FM,
293 const CapabilityExpr &CapE) const {
294 auto I = llvm::find_if(Range: *this, P: [&](FactID ID) -> bool {
295 return FM[ID].partiallyMatches(other: CapE);
296 });
297 return I != end() ? &FM[*I] : nullptr;
298 }
299
300 bool containsMutexDecl(FactManager &FM, const ValueDecl* Vd) const {
301 auto I = llvm::find_if(
302 Range: *this, P: [&](FactID ID) -> bool { return FM[ID].valueDecl() == Vd; });
303 return I != end();
304 }
305};
306
307class ThreadSafetyAnalyzer;
308
309} // namespace
310
311namespace clang {
312namespace threadSafety {
313
314class BeforeSet {
315private:
316 using BeforeVect = SmallVector<const ValueDecl *, 4>;
317
318 struct BeforeInfo {
319 BeforeVect Vect;
320 int Visited = 0;
321
322 BeforeInfo() = default;
323 BeforeInfo(BeforeInfo &&) = default;
324 };
325
326 using BeforeMap =
327 llvm::DenseMap<const ValueDecl *, std::unique_ptr<BeforeInfo>>;
328 using CycleMap = llvm::DenseMap<const ValueDecl *, bool>;
329
330public:
331 BeforeSet() = default;
332
333 BeforeInfo* insertAttrExprs(const ValueDecl* Vd,
334 ThreadSafetyAnalyzer& Analyzer);
335
336 BeforeInfo *getBeforeInfoForDecl(const ValueDecl *Vd,
337 ThreadSafetyAnalyzer &Analyzer);
338
339 void checkBeforeAfter(const ValueDecl* Vd,
340 const FactSet& FSet,
341 ThreadSafetyAnalyzer& Analyzer,
342 SourceLocation Loc, StringRef CapKind);
343
344private:
345 BeforeMap BMap;
346 CycleMap CycMap;
347};
348
349} // namespace threadSafety
350} // namespace clang
351
352namespace {
353
354class LocalVariableMap;
355
356using LocalVarContext = llvm::ImmutableMap<const NamedDecl *, unsigned>;
357
358/// A side (entry or exit) of a CFG node.
359enum CFGBlockSide { CBS_Entry, CBS_Exit };
360
361/// CFGBlockInfo is a struct which contains all the information that is
362/// maintained for each block in the CFG. See LocalVariableMap for more
363/// information about the contexts.
364struct CFGBlockInfo {
365 // Lockset held at entry to block
366 FactSet EntrySet;
367
368 // Lockset held at exit from block
369 FactSet ExitSet;
370
371 // Context held at entry to block
372 LocalVarContext EntryContext;
373
374 // Context held at exit from block
375 LocalVarContext ExitContext;
376
377 // Location of first statement in block
378 SourceLocation EntryLoc;
379
380 // Location of last statement in block.
381 SourceLocation ExitLoc;
382
383 // Used to replay contexts later
384 unsigned EntryIndex;
385
386 // Is this block reachable?
387 bool Reachable = false;
388
389 const FactSet &getSet(CFGBlockSide Side) const {
390 return Side == CBS_Entry ? EntrySet : ExitSet;
391 }
392
393 SourceLocation getLocation(CFGBlockSide Side) const {
394 return Side == CBS_Entry ? EntryLoc : ExitLoc;
395 }
396
397private:
398 CFGBlockInfo(LocalVarContext EmptyCtx)
399 : EntryContext(EmptyCtx), ExitContext(EmptyCtx) {}
400
401public:
402 static CFGBlockInfo getEmptyBlockInfo(LocalVariableMap &M);
403};
404
405// A LocalVariableMap maintains a map from local variables to their currently
406// valid definitions. It provides SSA-like functionality when traversing the
407// CFG. Like SSA, each definition or assignment to a variable is assigned a
408// unique name (an integer), which acts as the SSA name for that definition.
409// The total set of names is shared among all CFG basic blocks.
410// Unlike SSA, we do not rewrite expressions to replace local variables declrefs
411// with their SSA-names. Instead, we compute a Context for each point in the
412// code, which maps local variables to the appropriate SSA-name. This map
413// changes with each assignment.
414//
415// The map is computed in a single pass over the CFG. Subsequent analyses can
416// then query the map to find the appropriate Context for a statement, and use
417// that Context to look up the definitions of variables.
418class LocalVariableMap {
419public:
420 using Context = LocalVarContext;
421
422 /// A VarDefinition consists of an expression, representing the value of the
423 /// variable, along with the context in which that expression should be
424 /// interpreted. A reference VarDefinition does not itself contain this
425 /// information, but instead contains a pointer to a previous VarDefinition.
426 struct VarDefinition {
427 public:
428 friend class LocalVariableMap;
429
430 // The original declaration for this variable.
431 const NamedDecl *Dec;
432
433 // The expression for this variable, OR
434 const Expr *Exp = nullptr;
435
436 // Direct reference to another VarDefinition
437 unsigned DirectRef = 0;
438
439 // Reference to underlying canonical non-reference VarDefinition.
440 unsigned CanonicalRef = 0;
441
442 // The map with which Exp should be interpreted.
443 Context Ctx;
444
445 bool isReference() const { return !Exp; }
446
447 void invalidateRef() { DirectRef = CanonicalRef = 0; }
448
449 private:
450 // Create ordinary variable definition
451 VarDefinition(const NamedDecl *D, const Expr *E, Context C)
452 : Dec(D), Exp(E), Ctx(C) {}
453
454 // Create reference to previous definition
455 VarDefinition(const NamedDecl *D, unsigned DirectRef, unsigned CanonicalRef,
456 Context C)
457 : Dec(D), DirectRef(DirectRef), CanonicalRef(CanonicalRef), Ctx(C) {}
458 };
459
460private:
461 Context::Factory ContextFactory;
462 std::vector<VarDefinition> VarDefinitions;
463 std::vector<std::pair<const Stmt *, Context>> SavedContexts;
464
465public:
466 LocalVariableMap() {
467 // index 0 is a placeholder for undefined variables (aka phi-nodes).
468 VarDefinitions.push_back(x: VarDefinition(nullptr, 0, 0, getEmptyContext()));
469 }
470
471 /// Look up a definition, within the given context.
472 const VarDefinition* lookup(const NamedDecl *D, Context Ctx) {
473 const unsigned *i = Ctx.lookup(K: D);
474 if (!i)
475 return nullptr;
476 assert(*i < VarDefinitions.size());
477 return &VarDefinitions[*i];
478 }
479
480 /// Look up the definition for D within the given context. Returns
481 /// NULL if the expression is not statically known. If successful, also
482 /// modifies Ctx to hold the context of the return Expr.
483 const Expr* lookupExpr(const NamedDecl *D, Context &Ctx) {
484 const unsigned *P = Ctx.lookup(K: D);
485 if (!P)
486 return nullptr;
487
488 unsigned i = *P;
489 while (i > 0) {
490 if (VarDefinitions[i].Exp) {
491 Ctx = VarDefinitions[i].Ctx;
492 return VarDefinitions[i].Exp;
493 }
494 i = VarDefinitions[i].DirectRef;
495 }
496 return nullptr;
497 }
498
499 Context getEmptyContext() { return ContextFactory.getEmptyMap(); }
500
501 /// Return the next context after processing S. This function is used by
502 /// clients of the class to get the appropriate context when traversing the
503 /// CFG. It must be called for every assignment or DeclStmt.
504 const Context &getNextContext(unsigned &CtxIndex, const Stmt *S,
505 const Context &C) {
506 if (SavedContexts[CtxIndex + 1].first == S) {
507 CtxIndex++;
508 const Context &Result = SavedContexts[CtxIndex].second;
509 return Result;
510 }
511 return C;
512 }
513
514 void dumpVarDefinitionName(unsigned i) {
515 if (i == 0) {
516 llvm::errs() << "Undefined";
517 return;
518 }
519 const NamedDecl *Dec = VarDefinitions[i].Dec;
520 if (!Dec) {
521 llvm::errs() << "<<NULL>>";
522 return;
523 }
524 Dec->printName(OS&: llvm::errs());
525 llvm::errs() << "." << i << " " << ((const void*) Dec);
526 }
527
528 /// Dumps an ASCII representation of the variable map to llvm::errs()
529 void dump() {
530 for (unsigned i = 1, e = VarDefinitions.size(); i < e; ++i) {
531 const Expr *Exp = VarDefinitions[i].Exp;
532 unsigned Ref = VarDefinitions[i].DirectRef;
533
534 dumpVarDefinitionName(i);
535 llvm::errs() << " = ";
536 if (Exp) Exp->dump();
537 else {
538 dumpVarDefinitionName(i: Ref);
539 llvm::errs() << "\n";
540 }
541 }
542 }
543
544 /// Dumps an ASCII representation of a Context to llvm::errs()
545 void dumpContext(Context C) {
546 for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) {
547 const NamedDecl *D = I.getKey();
548 D->printName(OS&: llvm::errs());
549 llvm::errs() << " -> ";
550 dumpVarDefinitionName(i: I.getData());
551 llvm::errs() << "\n";
552 }
553 }
554
555 /// Builds the variable map.
556 void traverseCFG(CFG *CFGraph, const PostOrderCFGView *SortedGraph,
557 std::vector<CFGBlockInfo> &BlockInfo);
558
559protected:
560 friend class VarMapBuilder;
561
562 // Resolve any definition ID down to its non-reference base ID.
563 unsigned getCanonicalDefinitionID(unsigned ID) const {
564 while (ID > 0 && VarDefinitions[ID].isReference())
565 ID = VarDefinitions[ID].CanonicalRef;
566 return ID;
567 }
568
569 // Get the current context index
570 unsigned getContextIndex() { return SavedContexts.size()-1; }
571
572 // Save the current context for later replay
573 void saveContext(const Stmt *S, Context C) {
574 SavedContexts.push_back(x: std::make_pair(x&: S, y&: C));
575 }
576
577 // Adds a new definition to the given context, and returns a new context.
578 // This method should be called when declaring a new variable.
579 Context addDefinition(const NamedDecl *D, const Expr *Exp, Context Ctx) {
580 assert(!Ctx.contains(D));
581 unsigned newID = VarDefinitions.size();
582 Context NewCtx = ContextFactory.add(Old: Ctx, K: D, D: newID);
583 VarDefinitions.push_back(x: VarDefinition(D, Exp, Ctx));
584 return NewCtx;
585 }
586
587 // Add a new reference to an existing definition.
588 Context addReference(const NamedDecl *D, unsigned Ref, Context Ctx) {
589 unsigned newID = VarDefinitions.size();
590 Context NewCtx = ContextFactory.add(Old: Ctx, K: D, D: newID);
591 VarDefinitions.push_back(
592 x: VarDefinition(D, Ref, getCanonicalDefinitionID(ID: Ref), Ctx));
593 return NewCtx;
594 }
595
596 // Updates a definition only if that definition is already in the map.
597 // This method should be called when assigning to an existing variable.
598 Context updateDefinition(const NamedDecl *D, Expr *Exp, Context Ctx) {
599 if (Ctx.contains(K: D)) {
600 unsigned newID = VarDefinitions.size();
601 Context NewCtx = ContextFactory.remove(Old: Ctx, K: D);
602 NewCtx = ContextFactory.add(Old: NewCtx, K: D, D: newID);
603 VarDefinitions.push_back(x: VarDefinition(D, Exp, Ctx));
604 return NewCtx;
605 }
606 return Ctx;
607 }
608
609 // Removes a definition from the context, but keeps the variable name
610 // as a valid variable. The index 0 is a placeholder for cleared definitions.
611 Context clearDefinition(const NamedDecl *D, Context Ctx) {
612 Context NewCtx = Ctx;
613 if (NewCtx.contains(K: D)) {
614 NewCtx = ContextFactory.remove(Old: NewCtx, K: D);
615 NewCtx = ContextFactory.add(Old: NewCtx, K: D, D: 0);
616 }
617 return NewCtx;
618 }
619
620 // Remove a definition entirely frmo the context.
621 Context removeDefinition(const NamedDecl *D, Context Ctx) {
622 Context NewCtx = Ctx;
623 if (NewCtx.contains(K: D)) {
624 NewCtx = ContextFactory.remove(Old: NewCtx, K: D);
625 }
626 return NewCtx;
627 }
628
629 Context intersectContexts(Context C1, Context C2);
630 Context createReferenceContext(Context C);
631 void intersectBackEdge(Context C1, Context C2);
632};
633
634} // namespace
635
636// This has to be defined after LocalVariableMap.
637CFGBlockInfo CFGBlockInfo::getEmptyBlockInfo(LocalVariableMap &M) {
638 return CFGBlockInfo(M.getEmptyContext());
639}
640
641namespace {
642
643/// Visitor which builds a LocalVariableMap
644class VarMapBuilder : public ConstStmtVisitor<VarMapBuilder> {
645public:
646 LocalVariableMap* VMap;
647 LocalVariableMap::Context Ctx;
648
649 VarMapBuilder(LocalVariableMap *VM, LocalVariableMap::Context C)
650 : VMap(VM), Ctx(C) {}
651
652 void VisitDeclStmt(const DeclStmt *S);
653 void VisitBinaryOperator(const BinaryOperator *BO);
654 void VisitCallExpr(const CallExpr *CE);
655};
656
657} // namespace
658
659// Add new local variables to the variable map
660void VarMapBuilder::VisitDeclStmt(const DeclStmt *S) {
661 bool modifiedCtx = false;
662 const DeclGroupRef DGrp = S->getDeclGroup();
663 for (const auto *D : DGrp) {
664 if (const auto *VD = dyn_cast_or_null<VarDecl>(Val: D)) {
665 const Expr *E = VD->getInit();
666
667 // Add local variables with trivial type to the variable map
668 QualType T = VD->getType();
669 if (T.isTrivialType(Context: VD->getASTContext())) {
670 Ctx = VMap->addDefinition(D: VD, Exp: E, Ctx);
671 modifiedCtx = true;
672 }
673 }
674 }
675 if (modifiedCtx)
676 VMap->saveContext(S, C: Ctx);
677}
678
679// Update local variable definitions in variable map
680void VarMapBuilder::VisitBinaryOperator(const BinaryOperator *BO) {
681 if (!BO->isAssignmentOp())
682 return;
683
684 Expr *LHSExp = BO->getLHS()->IgnoreParenCasts();
685
686 // Update the variable map and current context.
687 if (const auto *DRE = dyn_cast<DeclRefExpr>(Val: LHSExp)) {
688 const ValueDecl *VDec = DRE->getDecl();
689 if (Ctx.lookup(K: VDec)) {
690 if (BO->getOpcode() == BO_Assign)
691 Ctx = VMap->updateDefinition(D: VDec, Exp: BO->getRHS(), Ctx);
692 else
693 // FIXME -- handle compound assignment operators
694 Ctx = VMap->clearDefinition(D: VDec, Ctx);
695 VMap->saveContext(S: BO, C: Ctx);
696 }
697 }
698}
699
700// Invalidates local variable definitions if variable escaped.
701void VarMapBuilder::VisitCallExpr(const CallExpr *CE) {
702 const FunctionDecl *FD = CE->getDirectCallee();
703 if (!FD)
704 return;
705
706 // Heuristic for likely-benign functions that pass by mutable reference. This
707 // is needed to avoid a slew of false positives due to mutable reference
708 // passing where the captured reference is usually passed on by-value.
709 if (const IdentifierInfo *II = FD->getIdentifier()) {
710 // Any kind of std::bind-like functions.
711 if (II->isStr(Str: "bind") || II->isStr(Str: "bind_front"))
712 return;
713 }
714
715 // Invalidate local variable definitions that are passed by non-const
716 // reference or non-const pointer.
717 for (unsigned Idx = 0; Idx < CE->getNumArgs(); ++Idx) {
718 if (Idx >= FD->getNumParams())
719 break;
720
721 const Expr *Arg = CE->getArg(Arg: Idx)->IgnoreParenImpCasts();
722 const ParmVarDecl *PVD = FD->getParamDecl(i: Idx);
723 QualType ParamType = PVD->getType();
724
725 // Potential reassignment if passed by non-const reference / pointer.
726 const ValueDecl *VDec = nullptr;
727 if (ParamType->isReferenceType() &&
728 !ParamType->getPointeeType().isConstQualified()) {
729 if (const auto *DRE = dyn_cast<DeclRefExpr>(Val: Arg))
730 VDec = DRE->getDecl();
731 } else if (ParamType->isPointerType() &&
732 !ParamType->getPointeeType().isConstQualified()) {
733 Arg = Arg->IgnoreParenCasts();
734 if (const auto *UO = dyn_cast<UnaryOperator>(Val: Arg)) {
735 if (UO->getOpcode() == UO_AddrOf) {
736 const Expr *SubE = UO->getSubExpr()->IgnoreParenCasts();
737 if (const auto *DRE = dyn_cast<DeclRefExpr>(Val: SubE))
738 VDec = DRE->getDecl();
739 }
740 }
741 }
742
743 if (VDec)
744 Ctx = VMap->clearDefinition(D: VDec, Ctx);
745 }
746 // Save the context after the call where escaped variables' definitions (if
747 // they exist) are cleared.
748 VMap->saveContext(S: CE, C: Ctx);
749}
750
751// Computes the intersection of two contexts. The intersection is the
752// set of variables which have the same definition in both contexts;
753// variables with different definitions are discarded.
754LocalVariableMap::Context
755LocalVariableMap::intersectContexts(Context C1, Context C2) {
756 Context Result = C1;
757 for (const auto &P : C1) {
758 const NamedDecl *Dec = P.first;
759 const unsigned *I2 = C2.lookup(K: Dec);
760 if (!I2) {
761 // The variable doesn't exist on second path.
762 Result = removeDefinition(D: Dec, Ctx: Result);
763 } else if (getCanonicalDefinitionID(ID: P.second) !=
764 getCanonicalDefinitionID(ID: *I2)) {
765 // If canonical definitions mismatch the underlying definitions are
766 // different, invalidate.
767 Result = clearDefinition(D: Dec, Ctx: Result);
768 }
769 }
770 return Result;
771}
772
773// For every variable in C, create a new variable that refers to the
774// definition in C. Return a new context that contains these new variables.
775// (We use this for a naive implementation of SSA on loop back-edges.)
776LocalVariableMap::Context LocalVariableMap::createReferenceContext(Context C) {
777 Context Result = getEmptyContext();
778 for (const auto &P : C)
779 Result = addReference(D: P.first, Ref: P.second, Ctx: Result);
780 return Result;
781}
782
783// This routine also takes the intersection of C1 and C2, but it does so by
784// altering the VarDefinitions. C1 must be the result of an earlier call to
785// createReferenceContext.
786void LocalVariableMap::intersectBackEdge(Context C1, Context C2) {
787 for (const auto &P : C1) {
788 const unsigned I1 = P.second;
789 VarDefinition *VDef = &VarDefinitions[I1];
790 assert(VDef->isReference());
791
792 const unsigned *I2 = C2.lookup(K: P.first);
793 if (!I2) {
794 // Variable does not exist at the end of the loop, invalidate.
795 VDef->invalidateRef();
796 continue;
797 }
798
799 // Compare the canonical IDs. This correctly handles chains of references
800 // and determines if the variable is truly loop-invariant.
801 if (VDef->CanonicalRef != getCanonicalDefinitionID(ID: *I2))
802 VDef->invalidateRef(); // Mark this variable as undefined
803 }
804}
805
806// Traverse the CFG in topological order, so all predecessors of a block
807// (excluding back-edges) are visited before the block itself. At
808// each point in the code, we calculate a Context, which holds the set of
809// variable definitions which are visible at that point in execution.
810// Visible variables are mapped to their definitions using an array that
811// contains all definitions.
812//
813// At join points in the CFG, the set is computed as the intersection of
814// the incoming sets along each edge, E.g.
815//
816// { Context | VarDefinitions }
817// int x = 0; { x -> x1 | x1 = 0 }
818// int y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 }
819// if (b) x = 1; { x -> x2, y -> y1 | x2 = 1, y1 = 0, ... }
820// else x = 2; { x -> x3, y -> y1 | x3 = 2, x2 = 1, ... }
821// ... { y -> y1 (x is unknown) | x3 = 2, x2 = 1, ... }
822//
823// This is essentially a simpler and more naive version of the standard SSA
824// algorithm. Those definitions that remain in the intersection are from blocks
825// that strictly dominate the current block. We do not bother to insert proper
826// phi nodes, because they are not used in our analysis; instead, wherever
827// a phi node would be required, we simply remove that definition from the
828// context (E.g. x above).
829//
830// The initial traversal does not capture back-edges, so those need to be
831// handled on a separate pass. Whenever the first pass encounters an
832// incoming back edge, it duplicates the context, creating new definitions
833// that refer back to the originals. (These correspond to places where SSA
834// might have to insert a phi node.) On the second pass, these definitions are
835// set to NULL if the variable has changed on the back-edge (i.e. a phi
836// node was actually required.) E.g.
837//
838// { Context | VarDefinitions }
839// int x = 0, y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 }
840// while (b) { x -> x2, y -> y1 | [1st:] x2=x1; [2nd:] x2=NULL; }
841// x = x+1; { x -> x3, y -> y1 | x3 = x2 + 1, ... }
842// ... { y -> y1 | x3 = 2, x2 = 1, ... }
843void LocalVariableMap::traverseCFG(CFG *CFGraph,
844 const PostOrderCFGView *SortedGraph,
845 std::vector<CFGBlockInfo> &BlockInfo) {
846 PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph);
847
848 for (const auto *CurrBlock : *SortedGraph) {
849 unsigned CurrBlockID = CurrBlock->getBlockID();
850 CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID];
851
852 VisitedBlocks.insert(Block: CurrBlock);
853
854 // Calculate the entry context for the current block
855 bool HasBackEdges = false;
856 bool CtxInit = true;
857 for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(),
858 PE = CurrBlock->pred_end(); PI != PE; ++PI) {
859 // if *PI -> CurrBlock is a back edge, so skip it
860 if (*PI == nullptr || !VisitedBlocks.alreadySet(Block: *PI)) {
861 HasBackEdges = true;
862 continue;
863 }
864
865 unsigned PrevBlockID = (*PI)->getBlockID();
866 CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID];
867
868 if (CtxInit) {
869 CurrBlockInfo->EntryContext = PrevBlockInfo->ExitContext;
870 CtxInit = false;
871 }
872 else {
873 CurrBlockInfo->EntryContext =
874 intersectContexts(C1: CurrBlockInfo->EntryContext,
875 C2: PrevBlockInfo->ExitContext);
876 }
877 }
878
879 // Duplicate the context if we have back-edges, so we can call
880 // intersectBackEdges later.
881 if (HasBackEdges)
882 CurrBlockInfo->EntryContext =
883 createReferenceContext(C: CurrBlockInfo->EntryContext);
884
885 // Create a starting context index for the current block
886 saveContext(S: nullptr, C: CurrBlockInfo->EntryContext);
887 CurrBlockInfo->EntryIndex = getContextIndex();
888
889 // Visit all the statements in the basic block.
890 VarMapBuilder VMapBuilder(this, CurrBlockInfo->EntryContext);
891 for (const auto &BI : *CurrBlock) {
892 switch (BI.getKind()) {
893 case CFGElement::Statement: {
894 CFGStmt CS = BI.castAs<CFGStmt>();
895 VMapBuilder.Visit(S: CS.getStmt());
896 break;
897 }
898 default:
899 break;
900 }
901 }
902 CurrBlockInfo->ExitContext = VMapBuilder.Ctx;
903
904 // Mark variables on back edges as "unknown" if they've been changed.
905 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
906 SE = CurrBlock->succ_end(); SI != SE; ++SI) {
907 // if CurrBlock -> *SI is *not* a back edge
908 if (*SI == nullptr || !VisitedBlocks.alreadySet(Block: *SI))
909 continue;
910
911 CFGBlock *FirstLoopBlock = *SI;
912 Context LoopBegin = BlockInfo[FirstLoopBlock->getBlockID()].EntryContext;
913 Context LoopEnd = CurrBlockInfo->ExitContext;
914 intersectBackEdge(C1: LoopBegin, C2: LoopEnd);
915 }
916 }
917
918 // Put an extra entry at the end of the indexed context array
919 unsigned exitID = CFGraph->getExit().getBlockID();
920 saveContext(S: nullptr, C: BlockInfo[exitID].ExitContext);
921}
922
923/// Find the appropriate source locations to use when producing diagnostics for
924/// each block in the CFG.
925static void findBlockLocations(CFG *CFGraph,
926 const PostOrderCFGView *SortedGraph,
927 std::vector<CFGBlockInfo> &BlockInfo) {
928 for (const auto *CurrBlock : *SortedGraph) {
929 CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlock->getBlockID()];
930
931 // Find the source location of the last statement in the block, if the
932 // block is not empty.
933 if (const Stmt *S = CurrBlock->getTerminatorStmt()) {
934 CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = S->getBeginLoc();
935 } else {
936 for (CFGBlock::const_reverse_iterator BI = CurrBlock->rbegin(),
937 BE = CurrBlock->rend(); BI != BE; ++BI) {
938 // FIXME: Handle other CFGElement kinds.
939 if (std::optional<CFGStmt> CS = BI->getAs<CFGStmt>()) {
940 CurrBlockInfo->ExitLoc = CS->getStmt()->getBeginLoc();
941 break;
942 }
943 }
944 }
945
946 if (CurrBlockInfo->ExitLoc.isValid()) {
947 // This block contains at least one statement. Find the source location
948 // of the first statement in the block.
949 for (const auto &BI : *CurrBlock) {
950 // FIXME: Handle other CFGElement kinds.
951 if (std::optional<CFGStmt> CS = BI.getAs<CFGStmt>()) {
952 CurrBlockInfo->EntryLoc = CS->getStmt()->getBeginLoc();
953 break;
954 }
955 }
956 } else if (CurrBlock->pred_size() == 1 && *CurrBlock->pred_begin() &&
957 CurrBlock != &CFGraph->getExit()) {
958 // The block is empty, and has a single predecessor. Use its exit
959 // location.
960 CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc =
961 BlockInfo[(*CurrBlock->pred_begin())->getBlockID()].ExitLoc;
962 } else if (CurrBlock->succ_size() == 1 && *CurrBlock->succ_begin()) {
963 // The block is empty, and has a single successor. Use its entry
964 // location.
965 CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc =
966 BlockInfo[(*CurrBlock->succ_begin())->getBlockID()].EntryLoc;
967 }
968 }
969}
970
971namespace {
972
973class LockableFactEntry final : public FactEntry {
974private:
975 /// Reentrancy depth: incremented when a capability has been acquired
976 /// reentrantly (after initial acquisition). Always 0 for non-reentrant
977 /// capabilities.
978 unsigned int ReentrancyDepth = 0;
979
980 LockableFactEntry(const CapabilityExpr &CE, LockKind LK, SourceLocation Loc,
981 SourceKind Src)
982 : FactEntry(Lockable, CE, LK, Loc, Src) {}
983
984public:
985 static LockableFactEntry *create(llvm::BumpPtrAllocator &Alloc,
986 const LockableFactEntry &Other) {
987 return new (Alloc) LockableFactEntry(Other);
988 }
989
990 static LockableFactEntry *create(llvm::BumpPtrAllocator &Alloc,
991 const CapabilityExpr &CE, LockKind LK,
992 SourceLocation Loc,
993 SourceKind Src = Acquired) {
994 return new (Alloc) LockableFactEntry(CE, LK, Loc, Src);
995 }
996
997 unsigned int getReentrancyDepth() const { return ReentrancyDepth; }
998
999 void
1000 handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan,
1001 SourceLocation JoinLoc, LockErrorKind LEK,
1002 ThreadSafetyHandler &Handler) const override {
1003 if (!asserted() && !negative() && !isUniversal()) {
1004 Handler.handleMutexHeldEndOfScope(Kind: getKind(), LockName: toString(), LocLocked: loc(), LocEndOfScope: JoinLoc,
1005 LEK);
1006 }
1007 }
1008
1009 void handleLock(FactSet &FSet, FactManager &FactMan, const FactEntry &entry,
1010 ThreadSafetyHandler &Handler) const override {
1011 if (const FactEntry *RFact = tryReenter(FactMan, ReenterKind: entry.kind())) {
1012 // This capability has been reentrantly acquired.
1013 FSet.replaceLock(FM&: FactMan, CapE: entry, Entry: RFact);
1014 } else {
1015 Handler.handleDoubleLock(Kind: entry.getKind(), LockName: entry.toString(), LocLocked: loc(),
1016 LocDoubleLock: entry.loc());
1017 }
1018 }
1019
1020 void handleUnlock(FactSet &FSet, FactManager &FactMan,
1021 const CapabilityExpr &Cp, SourceLocation UnlockLoc,
1022 bool FullyRemove,
1023 ThreadSafetyHandler &Handler) const override {
1024 FSet.removeLock(FM&: FactMan, CapE: Cp);
1025
1026 if (const FactEntry *RFact = leaveReentrant(FactMan)) {
1027 // This capability remains reentrantly acquired.
1028 FSet.addLock(FM&: FactMan, Entry: RFact);
1029 } else if (!Cp.negative()) {
1030 FSet.addLock(FM&: FactMan, Entry: FactMan.createFact<LockableFactEntry>(
1031 Args: !Cp, Args: LK_Exclusive, Args&: UnlockLoc));
1032 }
1033 }
1034
1035 // Return an updated FactEntry if we can acquire this capability reentrant,
1036 // nullptr otherwise.
1037 const FactEntry *tryReenter(FactManager &FactMan,
1038 LockKind ReenterKind) const {
1039 if (!reentrant())
1040 return nullptr;
1041 if (kind() != ReenterKind)
1042 return nullptr;
1043 auto *NewFact = FactMan.createFact<LockableFactEntry>(Args: *this);
1044 NewFact->ReentrancyDepth++;
1045 return NewFact;
1046 }
1047
1048 // Return an updated FactEntry if we are releasing a capability previously
1049 // acquired reentrant, nullptr otherwise.
1050 const FactEntry *leaveReentrant(FactManager &FactMan) const {
1051 if (!ReentrancyDepth)
1052 return nullptr;
1053 assert(reentrant());
1054 auto *NewFact = FactMan.createFact<LockableFactEntry>(Args: *this);
1055 NewFact->ReentrancyDepth--;
1056 return NewFact;
1057 }
1058
1059 static bool classof(const FactEntry *A) {
1060 return A->getFactEntryKind() == Lockable;
1061 }
1062};
1063
1064enum UnderlyingCapabilityKind {
1065 UCK_Acquired, ///< Any kind of acquired capability.
1066 UCK_ReleasedShared, ///< Shared capability that was released.
1067 UCK_ReleasedExclusive, ///< Exclusive capability that was released.
1068};
1069
1070struct UnderlyingCapability {
1071 CapabilityExpr Cap;
1072 UnderlyingCapabilityKind Kind;
1073};
1074
1075class ScopedLockableFactEntry final
1076 : public FactEntry,
1077 private llvm::TrailingObjects<ScopedLockableFactEntry,
1078 UnderlyingCapability> {
1079 friend TrailingObjects;
1080
1081private:
1082 const unsigned ManagedCapacity;
1083 unsigned ManagedSize = 0;
1084
1085 ScopedLockableFactEntry(const CapabilityExpr &CE, SourceLocation Loc,
1086 SourceKind Src, unsigned ManagedCapacity)
1087 : FactEntry(ScopedLockable, CE, LK_Exclusive, Loc, Src),
1088 ManagedCapacity(ManagedCapacity) {}
1089
1090 void addManaged(const CapabilityExpr &M, UnderlyingCapabilityKind UCK) {
1091 assert(ManagedSize < ManagedCapacity);
1092 new (getTrailingObjects() + ManagedSize) UnderlyingCapability{.Cap: M, .Kind: UCK};
1093 ++ManagedSize;
1094 }
1095
1096 ArrayRef<UnderlyingCapability> getManaged() const {
1097 return getTrailingObjects(N: ManagedSize);
1098 }
1099
1100public:
1101 static ScopedLockableFactEntry *create(llvm::BumpPtrAllocator &Alloc,
1102 const CapabilityExpr &CE,
1103 SourceLocation Loc, SourceKind Src,
1104 unsigned ManagedCapacity) {
1105 void *Storage =
1106 Alloc.Allocate(Size: totalSizeToAlloc<UnderlyingCapability>(Counts: ManagedCapacity),
1107 Alignment: alignof(ScopedLockableFactEntry));
1108 return new (Storage) ScopedLockableFactEntry(CE, Loc, Src, ManagedCapacity);
1109 }
1110
1111 CapExprSet getUnderlyingMutexes() const {
1112 CapExprSet UnderlyingMutexesSet;
1113 for (const UnderlyingCapability &UnderlyingMutex : getManaged())
1114 UnderlyingMutexesSet.push_back(Elt: UnderlyingMutex.Cap);
1115 return UnderlyingMutexesSet;
1116 }
1117
1118 /// \name Adding managed locks
1119 /// Capacity for managed locks must have been allocated via \ref create.
1120 /// There is no reallocation in case the capacity is exceeded!
1121 /// \{
1122 void addLock(const CapabilityExpr &M) { addManaged(M, UCK: UCK_Acquired); }
1123
1124 void addExclusiveUnlock(const CapabilityExpr &M) {
1125 addManaged(M, UCK: UCK_ReleasedExclusive);
1126 }
1127
1128 void addSharedUnlock(const CapabilityExpr &M) {
1129 addManaged(M, UCK: UCK_ReleasedShared);
1130 }
1131 /// \}
1132
1133 void
1134 handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan,
1135 SourceLocation JoinLoc, LockErrorKind LEK,
1136 ThreadSafetyHandler &Handler) const override {
1137 if (LEK == LEK_LockedAtEndOfFunction || LEK == LEK_NotLockedAtEndOfFunction)
1138 return;
1139
1140 for (const auto &UnderlyingMutex : getManaged()) {
1141 const auto *Entry = FSet.findLock(FM&: FactMan, CapE: UnderlyingMutex.Cap);
1142 if ((UnderlyingMutex.Kind == UCK_Acquired && Entry) ||
1143 (UnderlyingMutex.Kind != UCK_Acquired && !Entry)) {
1144 // If this scoped lock manages another mutex, and if the underlying
1145 // mutex is still/not held, then warn about the underlying mutex.
1146 Handler.handleMutexHeldEndOfScope(Kind: UnderlyingMutex.Cap.getKind(),
1147 LockName: UnderlyingMutex.Cap.toString(), LocLocked: loc(),
1148 LocEndOfScope: JoinLoc, LEK);
1149 }
1150 }
1151 }
1152
1153 void handleLock(FactSet &FSet, FactManager &FactMan, const FactEntry &entry,
1154 ThreadSafetyHandler &Handler) const override {
1155 for (const auto &UnderlyingMutex : getManaged()) {
1156 if (UnderlyingMutex.Kind == UCK_Acquired)
1157 lock(FSet, FactMan, Cp: UnderlyingMutex.Cap, kind: entry.kind(), loc: entry.loc(),
1158 Handler: &Handler);
1159 else
1160 unlock(FSet, FactMan, Cp: UnderlyingMutex.Cap, loc: entry.loc(), Handler: &Handler);
1161 }
1162 }
1163
1164 void handleUnlock(FactSet &FSet, FactManager &FactMan,
1165 const CapabilityExpr &Cp, SourceLocation UnlockLoc,
1166 bool FullyRemove,
1167 ThreadSafetyHandler &Handler) const override {
1168 assert(!Cp.negative() && "Managing object cannot be negative.");
1169 for (const auto &UnderlyingMutex : getManaged()) {
1170 // Remove/lock the underlying mutex if it exists/is still unlocked; warn
1171 // on double unlocking/locking if we're not destroying the scoped object.
1172 ThreadSafetyHandler *TSHandler = FullyRemove ? nullptr : &Handler;
1173 if (UnderlyingMutex.Kind == UCK_Acquired) {
1174 unlock(FSet, FactMan, Cp: UnderlyingMutex.Cap, loc: UnlockLoc, Handler: TSHandler);
1175 } else {
1176 LockKind kind = UnderlyingMutex.Kind == UCK_ReleasedShared
1177 ? LK_Shared
1178 : LK_Exclusive;
1179 lock(FSet, FactMan, Cp: UnderlyingMutex.Cap, kind, loc: UnlockLoc, Handler: TSHandler);
1180 }
1181 }
1182 if (FullyRemove)
1183 FSet.removeLock(FM&: FactMan, CapE: Cp);
1184 }
1185
1186 static bool classof(const FactEntry *A) {
1187 return A->getFactEntryKind() == ScopedLockable;
1188 }
1189
1190private:
1191 void lock(FactSet &FSet, FactManager &FactMan, const CapabilityExpr &Cp,
1192 LockKind kind, SourceLocation loc,
1193 ThreadSafetyHandler *Handler) const {
1194 if (const auto It = FSet.findLockIter(FM&: FactMan, CapE: Cp); It != FSet.end()) {
1195 const auto &Fact = cast<LockableFactEntry>(Val: FactMan[*It]);
1196 if (const FactEntry *RFact = Fact.tryReenter(FactMan, ReenterKind: kind)) {
1197 // This capability has been reentrantly acquired.
1198 FSet.replaceLock(FM&: FactMan, It, Entry: RFact);
1199 } else if (Handler) {
1200 Handler->handleDoubleLock(Kind: Cp.getKind(), LockName: Cp.toString(), LocLocked: Fact.loc(), LocDoubleLock: loc);
1201 }
1202 } else {
1203 FSet.removeLock(FM&: FactMan, CapE: !Cp);
1204 FSet.addLock(FM&: FactMan, Entry: FactMan.createFact<LockableFactEntry>(Args: Cp, Args&: kind, Args&: loc,
1205 Args: Managed));
1206 }
1207 }
1208
1209 void unlock(FactSet &FSet, FactManager &FactMan, const CapabilityExpr &Cp,
1210 SourceLocation loc, ThreadSafetyHandler *Handler) const {
1211 if (const auto It = FSet.findLockIter(FM&: FactMan, CapE: Cp); It != FSet.end()) {
1212 const auto &Fact = cast<LockableFactEntry>(Val: FactMan[*It]);
1213 if (const FactEntry *RFact = Fact.leaveReentrant(FactMan)) {
1214 // This capability remains reentrantly acquired.
1215 FSet.replaceLock(FM&: FactMan, It, Entry: RFact);
1216 return;
1217 }
1218
1219 FSet.replaceLock(
1220 FM&: FactMan, It,
1221 Entry: FactMan.createFact<LockableFactEntry>(Args: !Cp, Args: LK_Exclusive, Args&: loc));
1222 } else if (Handler) {
1223 SourceLocation PrevLoc;
1224 if (const FactEntry *Neg = FSet.findLock(FM&: FactMan, CapE: !Cp))
1225 PrevLoc = Neg->loc();
1226 Handler->handleUnmatchedUnlock(Kind: Cp.getKind(), LockName: Cp.toString(), Loc: loc, LocPreviousUnlock: PrevLoc);
1227 }
1228 }
1229};
1230
1231/// Class which implements the core thread safety analysis routines.
1232class ThreadSafetyAnalyzer {
1233 friend class BuildLockset;
1234 friend class threadSafety::BeforeSet;
1235
1236 llvm::BumpPtrAllocator Bpa;
1237 threadSafety::til::MemRegionRef Arena;
1238 threadSafety::SExprBuilder SxBuilder;
1239
1240 ThreadSafetyHandler &Handler;
1241 const FunctionDecl *CurrentFunction;
1242 LocalVariableMap LocalVarMap;
1243 // Maps constructed objects to `this` placeholder prior to initialization.
1244 llvm::SmallDenseMap<const Expr *, til::LiteralPtr *> ConstructedObjects;
1245 FactManager FactMan;
1246 std::vector<CFGBlockInfo> BlockInfo;
1247
1248 BeforeSet *GlobalBeforeSet;
1249
1250public:
1251 ThreadSafetyAnalyzer(ThreadSafetyHandler &H, BeforeSet *Bset)
1252 : Arena(&Bpa), SxBuilder(Arena), Handler(H), FactMan(Bpa),
1253 GlobalBeforeSet(Bset) {}
1254
1255 bool inCurrentScope(const CapabilityExpr &CapE);
1256
1257 void addLock(FactSet &FSet, const FactEntry *Entry, bool ReqAttr = false);
1258 void removeLock(FactSet &FSet, const CapabilityExpr &CapE,
1259 SourceLocation UnlockLoc, bool FullyRemove, LockKind Kind);
1260
1261 template <typename AttrType>
1262 void getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, const Expr *Exp,
1263 const NamedDecl *D, til::SExpr *Self = nullptr);
1264
1265 template <class AttrType>
1266 void getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, const Expr *Exp,
1267 const NamedDecl *D,
1268 const CFGBlock *PredBlock, const CFGBlock *CurrBlock,
1269 Expr *BrE, bool Neg);
1270
1271 const CallExpr* getTrylockCallExpr(const Stmt *Cond, LocalVarContext C,
1272 bool &Negate);
1273
1274 using TerminatorTrylockCall =
1275 std::tuple<const CallExpr *, const NamedDecl *,
1276 std::optional<llvm::scope_exit<std::function<void()>>>>;
1277
1278 TerminatorTrylockCall getTerminatorTrylockCall(const CFGBlock *Block,
1279 bool &Negate);
1280
1281 void getEdgeLockset(FactSet &Result, const FactSet &ExitSet,
1282 const CFGBlock* PredBlock,
1283 const CFGBlock *CurrBlock);
1284
1285 void getTerminatorTrylockCaps(const CFGBlock *Block, CapExprSet &Caps);
1286
1287 bool join(const FactEntry &A, const FactEntry &B, SourceLocation JoinLoc,
1288 LockErrorKind EntryLEK);
1289
1290 void intersectAndWarn(FactSet &EntrySet, const FactSet &ExitSet,
1291 SourceLocation JoinLoc, LockErrorKind EntryLEK,
1292 LockErrorKind ExitLEK,
1293 const CapExprSet *TrylockRebranchCaps = nullptr);
1294
1295 void intersectAndWarn(FactSet &EntrySet, const FactSet &ExitSet,
1296 SourceLocation JoinLoc, LockErrorKind LEK) {
1297 intersectAndWarn(EntrySet, ExitSet, JoinLoc, EntryLEK: LEK, ExitLEK: LEK);
1298 }
1299
1300 void runAnalysis(AnalysisDeclContext &AC);
1301
1302 void warnIfMutexNotHeld(const FactSet &FSet, const NamedDecl *D,
1303 const Expr *Exp, AccessKind AK, Expr *MutexExp,
1304 ProtectedOperationKind POK, til::SExpr *Self,
1305 SourceLocation Loc);
1306 void warnIfAnyMutexNotHeldForRead(const FactSet &FSet, const NamedDecl *D,
1307 const Expr *Exp,
1308 llvm::ArrayRef<Expr *> Args,
1309 ProtectedOperationKind POK,
1310 SourceLocation Loc);
1311 void warnIfMutexHeld(const FactSet &FSet, const NamedDecl *D, const Expr *Exp,
1312 Expr *MutexExp, til::SExpr *Self, SourceLocation Loc);
1313
1314 void checkAccess(const FactSet &FSet, const Expr *Exp, AccessKind AK,
1315 ProtectedOperationKind POK);
1316 void checkPtAccess(const FactSet &FSet, const Expr *Exp, AccessKind AK,
1317 ProtectedOperationKind POK);
1318};
1319
1320} // namespace
1321
1322/// Process acquired_before and acquired_after attributes on Vd.
1323BeforeSet::BeforeInfo* BeforeSet::insertAttrExprs(const ValueDecl* Vd,
1324 ThreadSafetyAnalyzer& Analyzer) {
1325 // Create a new entry for Vd.
1326 BeforeInfo *Info = nullptr;
1327 {
1328 // Keep InfoPtr in its own scope in case BMap is modified later and the
1329 // reference becomes invalid.
1330 std::unique_ptr<BeforeInfo> &InfoPtr = BMap[Vd];
1331 if (!InfoPtr)
1332 InfoPtr.reset(p: new BeforeInfo());
1333 Info = InfoPtr.get();
1334 }
1335
1336 for (const auto *At : Vd->attrs()) {
1337 switch (At->getKind()) {
1338 case attr::AcquiredBefore: {
1339 const auto *A = cast<AcquiredBeforeAttr>(Val: At);
1340
1341 // Read exprs from the attribute, and add them to BeforeVect.
1342 for (const auto *Arg : A->args()) {
1343 CapabilityExpr Cp =
1344 Analyzer.SxBuilder.translateAttrExpr(AttrExp: Arg, Ctx: nullptr);
1345 if (const ValueDecl *Cpvd = Cp.valueDecl()) {
1346 Info->Vect.push_back(Elt: Cpvd);
1347 const auto It = BMap.find(Val: Cpvd);
1348 if (It == BMap.end())
1349 insertAttrExprs(Vd: Cpvd, Analyzer);
1350 }
1351 }
1352 break;
1353 }
1354 case attr::AcquiredAfter: {
1355 const auto *A = cast<AcquiredAfterAttr>(Val: At);
1356
1357 // Read exprs from the attribute, and add them to BeforeVect.
1358 for (const auto *Arg : A->args()) {
1359 CapabilityExpr Cp =
1360 Analyzer.SxBuilder.translateAttrExpr(AttrExp: Arg, Ctx: nullptr);
1361 if (const ValueDecl *ArgVd = Cp.valueDecl()) {
1362 // Get entry for mutex listed in attribute
1363 BeforeInfo *ArgInfo = getBeforeInfoForDecl(Vd: ArgVd, Analyzer);
1364 ArgInfo->Vect.push_back(Elt: Vd);
1365 }
1366 }
1367 break;
1368 }
1369 default:
1370 break;
1371 }
1372 }
1373
1374 return Info;
1375}
1376
1377BeforeSet::BeforeInfo *
1378BeforeSet::getBeforeInfoForDecl(const ValueDecl *Vd,
1379 ThreadSafetyAnalyzer &Analyzer) {
1380 auto It = BMap.find(Val: Vd);
1381 BeforeInfo *Info = nullptr;
1382 if (It == BMap.end())
1383 Info = insertAttrExprs(Vd, Analyzer);
1384 else
1385 Info = It->second.get();
1386 assert(Info && "BMap contained nullptr?");
1387 return Info;
1388}
1389
1390/// Return true if any mutexes in FSet are in the acquired_before set of Vd.
1391void BeforeSet::checkBeforeAfter(const ValueDecl* StartVd,
1392 const FactSet& FSet,
1393 ThreadSafetyAnalyzer& Analyzer,
1394 SourceLocation Loc, StringRef CapKind) {
1395 SmallVector<BeforeInfo*, 8> InfoVect;
1396
1397 // Do a depth-first traversal of Vd.
1398 // Return true if there are cycles.
1399 std::function<bool (const ValueDecl*)> traverse = [&](const ValueDecl* Vd) {
1400 if (!Vd)
1401 return false;
1402
1403 BeforeSet::BeforeInfo *Info = getBeforeInfoForDecl(Vd, Analyzer);
1404
1405 if (Info->Visited == 1)
1406 return true;
1407
1408 if (Info->Visited == 2)
1409 return false;
1410
1411 if (Info->Vect.empty())
1412 return false;
1413
1414 InfoVect.push_back(Elt: Info);
1415 Info->Visited = 1;
1416 for (const auto *Vdb : Info->Vect) {
1417 // Exclude mutexes in our immediate before set.
1418 if (FSet.containsMutexDecl(FM&: Analyzer.FactMan, Vd: Vdb)) {
1419 StringRef L1 = StartVd->getName();
1420 StringRef L2 = Vdb->getName();
1421 Analyzer.Handler.handleLockAcquiredBefore(Kind: CapKind, L1Name: L1, L2Name: L2, Loc);
1422 }
1423 // Transitively search other before sets, and warn on cycles.
1424 if (traverse(Vdb)) {
1425 if (CycMap.try_emplace(Key: Vd, Args: true).second) {
1426 StringRef L1 = Vd->getName();
1427 Analyzer.Handler.handleBeforeAfterCycle(L1Name: L1, Loc: Vd->getLocation());
1428 }
1429 }
1430 }
1431 Info->Visited = 2;
1432 return false;
1433 };
1434
1435 traverse(StartVd);
1436
1437 for (auto *Info : InfoVect)
1438 Info->Visited = 0;
1439}
1440
1441/// Gets the value decl pointer from DeclRefExprs or MemberExprs.
1442static const ValueDecl *getValueDecl(const Expr *Exp) {
1443 if (const auto *CE = dyn_cast<ImplicitCastExpr>(Val: Exp))
1444 return getValueDecl(Exp: CE->getSubExpr());
1445
1446 if (const auto *DR = dyn_cast<DeclRefExpr>(Val: Exp))
1447 return DR->getDecl();
1448
1449 if (const auto *ME = dyn_cast<MemberExpr>(Val: Exp))
1450 return ME->getMemberDecl();
1451
1452 return nullptr;
1453}
1454
1455bool ThreadSafetyAnalyzer::inCurrentScope(const CapabilityExpr &CapE) {
1456 const threadSafety::til::SExpr *SExp = CapE.sexpr();
1457 assert(SExp && "Null expressions should be ignored");
1458
1459 if (const auto *LP = dyn_cast<til::LiteralPtr>(Val: SExp)) {
1460 const ValueDecl *VD = LP->clangDecl();
1461 // Variables defined in a function are always inaccessible.
1462 if (!VD || !VD->isDefinedOutsideFunctionOrMethod())
1463 return false;
1464 // For now we consider static class members to be inaccessible.
1465 if (isa<CXXRecordDecl>(Val: VD->getDeclContext()))
1466 return false;
1467 // Global variables are always in scope.
1468 return true;
1469 }
1470
1471 // Members are in scope from methods of the same class.
1472 if (const auto *P = dyn_cast<til::Project>(Val: SExp)) {
1473 if (!isa_and_nonnull<CXXMethodDecl>(Val: CurrentFunction))
1474 return false;
1475 const ValueDecl *VD = P->clangDecl();
1476 return VD->getDeclContext() == CurrentFunction->getDeclContext();
1477 }
1478
1479 return false;
1480}
1481
1482/// Add a new lock to the lockset, warning if the lock is already there.
1483/// \param ReqAttr -- true if this is part of an initial Requires attribute.
1484void ThreadSafetyAnalyzer::addLock(FactSet &FSet, const FactEntry *Entry,
1485 bool ReqAttr) {
1486 if (Entry->shouldIgnore())
1487 return;
1488
1489 if (!ReqAttr && !Entry->negative()) {
1490 // look for the negative capability, and remove it from the fact set.
1491 CapabilityExpr NegC = !*Entry;
1492 const FactEntry *Nen = FSet.findLock(FM&: FactMan, CapE: NegC);
1493 if (Nen) {
1494 FSet.removeLock(FM&: FactMan, CapE: NegC);
1495 }
1496 else {
1497 if (inCurrentScope(CapE: *Entry) && !Entry->asserted() && !Entry->reentrant())
1498 Handler.handleNegativeNotHeld(Kind: Entry->getKind(), LockName: Entry->toString(),
1499 Neg: NegC.toString(), Loc: Entry->loc());
1500 }
1501 }
1502
1503 // Check before/after constraints
1504 if (!Entry->asserted() && !Entry->declared()) {
1505 GlobalBeforeSet->checkBeforeAfter(StartVd: Entry->valueDecl(), FSet, Analyzer&: *this,
1506 Loc: Entry->loc(), CapKind: Entry->getKind());
1507 }
1508
1509 if (const FactEntry *Cp = FSet.findLock(FM&: FactMan, CapE: *Entry)) {
1510 if (!Entry->asserted())
1511 Cp->handleLock(FSet, FactMan, entry: *Entry, Handler);
1512 } else {
1513 FSet.addLock(FM&: FactMan, Entry);
1514 }
1515}
1516
1517/// Remove a lock from the lockset, warning if the lock is not there.
1518/// \param UnlockLoc The source location of the unlock (only used in error msg)
1519void ThreadSafetyAnalyzer::removeLock(FactSet &FSet, const CapabilityExpr &Cp,
1520 SourceLocation UnlockLoc,
1521 bool FullyRemove, LockKind ReceivedKind) {
1522 if (Cp.shouldIgnore())
1523 return;
1524
1525 const FactEntry *LDat = FSet.findLock(FM&: FactMan, CapE: Cp);
1526 if (!LDat) {
1527 SourceLocation PrevLoc;
1528 if (const FactEntry *Neg = FSet.findLock(FM&: FactMan, CapE: !Cp))
1529 PrevLoc = Neg->loc();
1530 Handler.handleUnmatchedUnlock(Kind: Cp.getKind(), LockName: Cp.toString(), Loc: UnlockLoc,
1531 LocPreviousUnlock: PrevLoc);
1532 return;
1533 }
1534
1535 // Generic lock removal doesn't care about lock kind mismatches, but
1536 // otherwise diagnose when the lock kinds are mismatched.
1537 if (ReceivedKind != LK_Generic && LDat->kind() != ReceivedKind) {
1538 Handler.handleIncorrectUnlockKind(Kind: Cp.getKind(), LockName: Cp.toString(), Expected: LDat->kind(),
1539 Received: ReceivedKind, LocLocked: LDat->loc(), LocUnlock: UnlockLoc);
1540 }
1541
1542 LDat->handleUnlock(FSet, FactMan, Cp, UnlockLoc, FullyRemove, Handler);
1543}
1544
1545/// Extract the list of mutexIDs from the attribute on an expression,
1546/// and push them onto Mtxs, discarding any duplicates.
1547template <typename AttrType>
1548void ThreadSafetyAnalyzer::getMutexIDs(CapExprSet &Mtxs, AttrType *Attr,
1549 const Expr *Exp, const NamedDecl *D,
1550 til::SExpr *Self) {
1551 if (Attr->args_size() == 0) {
1552 // The mutex held is the "this" object.
1553 CapabilityExpr Cp = SxBuilder.translateAttrExpr(AttrExp: nullptr, D, DeclExp: Exp, Self);
1554 if (Cp.isInvalid()) {
1555 warnInvalidLock(Handler, MutexExp: nullptr, D, DeclExp: Exp, Kind: Cp.getKind());
1556 return;
1557 }
1558 //else
1559 if (!Cp.shouldIgnore())
1560 Mtxs.push_back_nodup(CapE: Cp);
1561 return;
1562 }
1563
1564 for (const auto *Arg : Attr->args()) {
1565 CapabilityExpr Cp = SxBuilder.translateAttrExpr(Arg, D, Exp, Self);
1566 if (Cp.isInvalid()) {
1567 warnInvalidLock(Handler, MutexExp: nullptr, D, DeclExp: Exp, Kind: Cp.getKind());
1568 continue;
1569 }
1570 //else
1571 if (!Cp.shouldIgnore())
1572 Mtxs.push_back_nodup(CapE: Cp);
1573 }
1574}
1575
1576/// Extract the list of mutexIDs from a trylock attribute. If the
1577/// trylock applies to the given edge, then push them onto Mtxs, discarding
1578/// any duplicates.
1579template <class AttrType>
1580void ThreadSafetyAnalyzer::getMutexIDs(CapExprSet &Mtxs, AttrType *Attr,
1581 const Expr *Exp, const NamedDecl *D,
1582 const CFGBlock *PredBlock,
1583 const CFGBlock *CurrBlock,
1584 Expr *BrE, bool Neg) {
1585 // Find out which branch has the lock
1586 bool branch = false;
1587 if (const auto *BLE = dyn_cast_or_null<CXXBoolLiteralExpr>(Val: BrE))
1588 branch = BLE->getValue();
1589 else if (const auto *ILE = dyn_cast_or_null<IntegerLiteral>(Val: BrE))
1590 branch = ILE->getValue().getBoolValue();
1591
1592 int branchnum = branch ? 0 : 1;
1593 if (Neg)
1594 branchnum = !branchnum;
1595
1596 // If we've taken the trylock branch, then add the lock
1597 int i = 0;
1598 for (CFGBlock::const_succ_iterator SI = PredBlock->succ_begin(),
1599 SE = PredBlock->succ_end(); SI != SE && i < 2; ++SI, ++i) {
1600 if (*SI == CurrBlock && i == branchnum)
1601 getMutexIDs(Mtxs, Attr, Exp, D);
1602 }
1603}
1604
1605static bool getStaticBooleanValue(Expr *E, bool &TCond) {
1606 if (isa<CXXNullPtrLiteralExpr>(Val: E) || isa<GNUNullExpr>(Val: E)) {
1607 TCond = false;
1608 return true;
1609 } else if (const auto *BLE = dyn_cast<CXXBoolLiteralExpr>(Val: E)) {
1610 TCond = BLE->getValue();
1611 return true;
1612 } else if (const auto *ILE = dyn_cast<IntegerLiteral>(Val: E)) {
1613 TCond = ILE->getValue().getBoolValue();
1614 return true;
1615 } else if (auto *CE = dyn_cast<ImplicitCastExpr>(Val: E))
1616 return getStaticBooleanValue(E: CE->getSubExpr(), TCond);
1617 return false;
1618}
1619
1620// If Cond can be traced back to a function call, return the call expression.
1621// The negate variable should be called with false, and will be set to true
1622// if the function call is negated, e.g. if (!mu.tryLock(...))
1623const CallExpr* ThreadSafetyAnalyzer::getTrylockCallExpr(const Stmt *Cond,
1624 LocalVarContext C,
1625 bool &Negate) {
1626 if (!Cond)
1627 return nullptr;
1628
1629 if (const auto *CallExp = dyn_cast<CallExpr>(Val: Cond)) {
1630 if (CallExp->getBuiltinCallee() == Builtin::BI__builtin_expect)
1631 return getTrylockCallExpr(Cond: CallExp->getArg(Arg: 0), C, Negate);
1632 return CallExp;
1633 }
1634 else if (const auto *PE = dyn_cast<ParenExpr>(Val: Cond))
1635 return getTrylockCallExpr(Cond: PE->getSubExpr(), C, Negate);
1636 else if (const auto *CE = dyn_cast<ImplicitCastExpr>(Val: Cond))
1637 return getTrylockCallExpr(Cond: CE->getSubExpr(), C, Negate);
1638 else if (const auto *FE = dyn_cast<FullExpr>(Val: Cond))
1639 return getTrylockCallExpr(Cond: FE->getSubExpr(), C, Negate);
1640 else if (const auto *DRE = dyn_cast<DeclRefExpr>(Val: Cond)) {
1641 const Expr *E = LocalVarMap.lookupExpr(D: DRE->getDecl(), Ctx&: C);
1642 return getTrylockCallExpr(Cond: E, C, Negate);
1643 }
1644 else if (const auto *UOP = dyn_cast<UnaryOperator>(Val: Cond)) {
1645 if (UOP->getOpcode() == UO_LNot) {
1646 Negate = !Negate;
1647 return getTrylockCallExpr(Cond: UOP->getSubExpr(), C, Negate);
1648 }
1649 return nullptr;
1650 }
1651 else if (const auto *BOP = dyn_cast<BinaryOperator>(Val: Cond)) {
1652 if (BOP->getOpcode() == BO_EQ || BOP->getOpcode() == BO_NE) {
1653 if (BOP->getOpcode() == BO_NE)
1654 Negate = !Negate;
1655
1656 bool TCond = false;
1657 if (getStaticBooleanValue(E: BOP->getRHS(), TCond)) {
1658 if (!TCond) Negate = !Negate;
1659 return getTrylockCallExpr(Cond: BOP->getLHS(), C, Negate);
1660 }
1661 TCond = false;
1662 if (getStaticBooleanValue(E: BOP->getLHS(), TCond)) {
1663 if (!TCond) Negate = !Negate;
1664 return getTrylockCallExpr(Cond: BOP->getRHS(), C, Negate);
1665 }
1666 return nullptr;
1667 }
1668 if (BOP->getOpcode() == BO_LAnd) {
1669 // LHS must have been evaluated in a different block.
1670 return getTrylockCallExpr(Cond: BOP->getRHS(), C, Negate);
1671 }
1672 if (BOP->getOpcode() == BO_LOr)
1673 return getTrylockCallExpr(Cond: BOP->getRHS(), C, Negate);
1674 return nullptr;
1675 } else if (const auto *COP = dyn_cast<ConditionalOperator>(Val: Cond)) {
1676 bool TCond, FCond;
1677 if (getStaticBooleanValue(E: COP->getTrueExpr(), TCond) &&
1678 getStaticBooleanValue(E: COP->getFalseExpr(), TCond&: FCond)) {
1679 if (TCond && !FCond)
1680 return getTrylockCallExpr(Cond: COP->getCond(), C, Negate);
1681 if (!TCond && FCond) {
1682 Negate = !Negate;
1683 return getTrylockCallExpr(Cond: COP->getCond(), C, Negate);
1684 }
1685 }
1686 } else if (const auto *SE = dyn_cast<StmtExpr>(Val: Cond)) {
1687 if (const auto *CS = SE->getSubStmt(); CS && !CS->body_empty()) {
1688 if (const auto *E = dyn_cast<Expr>(Val: CS->body_back()))
1689 return getTrylockCallExpr(Cond: E, C, Negate);
1690 }
1691 }
1692 return nullptr;
1693}
1694
1695/// If the terminator of \p Block branches on the result of a call to a
1696/// function annotated with try_acquire_capability (possibly negated or stored
1697/// in a local variable), return that call and its callee. \p Negate is set if
1698/// the branch tests the negated result of the call. In beta mode, this leaves
1699/// the local variable lookup closure of SExprBuilder installed so that callers
1700/// can translate the callee's attribute expressions
1701ThreadSafetyAnalyzer::TerminatorTrylockCall
1702ThreadSafetyAnalyzer::getTerminatorTrylockCall(const CFGBlock *Block,
1703 bool &Negate) {
1704 assert(!Negate && "Must be called with Negate initialized to false");
1705
1706 const Stmt *Cond = Block->getTerminatorCondition();
1707 if (!Cond)
1708 return {};
1709
1710 // We don't acquire try-locks on ?: branches, except when its result is used.
1711 if (const auto *COp =
1712 dyn_cast_if_present<ConditionalOperator>(Val: Block->getTerminatorStmt()))
1713 if (!COp->getType()->isVoidType())
1714 return {};
1715
1716 const LocalVarContext &LVarCtx = BlockInfo[Block->getBlockID()].ExitContext;
1717
1718 std::optional<llvm::scope_exit<std::function<void()>>> Cleanup;
1719 if (Handler.issueBetaWarnings()) {
1720 // Temporarily set the lookup context for SExprBuilder.
1721 SxBuilder.setLookupLocalVarExpr(
1722 [this, Ctx = LVarCtx](const NamedDecl *D) mutable -> const Expr * {
1723 return LocalVarMap.lookupExpr(D, Ctx);
1724 });
1725 Cleanup.emplace(args: [this] { SxBuilder.setLookupLocalVarExpr(nullptr); });
1726 }
1727
1728 const auto *Exp = getTrylockCallExpr(Cond, C: LVarCtx, Negate);
1729 if (!Exp)
1730 return {};
1731
1732 auto *FunDecl = dyn_cast_or_null<NamedDecl>(Val: Exp->getCalleeDecl());
1733 if (!FunDecl || !FunDecl->hasAttr<TryAcquireCapabilityAttr>())
1734 return {};
1735
1736 return {Exp, FunDecl, std::move(Cleanup)};
1737}
1738
1739/// Find the lockset that holds on the edge between PredBlock
1740/// and CurrBlock. The edge set is the exit set of PredBlock (passed
1741/// as the ExitSet parameter) plus any trylocks, which are conditionally held.
1742void ThreadSafetyAnalyzer::getEdgeLockset(FactSet &Result,
1743 const FactSet &ExitSet,
1744 const CFGBlock *PredBlock,
1745 const CFGBlock *CurrBlock) {
1746 Result = ExitSet;
1747
1748 bool Negate = false;
1749 auto [Exp, FunDecl, Cleanup] = getTerminatorTrylockCall(Block: PredBlock, Negate);
1750 if (!Exp)
1751 return;
1752
1753 CapExprSet ExclusiveLocksToAdd;
1754 CapExprSet SharedLocksToAdd;
1755
1756 // If the condition is a call to a Trylock function, then grab the attributes
1757 for (const auto *Attr : FunDecl->specific_attrs<TryAcquireCapabilityAttr>())
1758 getMutexIDs(Mtxs&: Attr->isShared() ? SharedLocksToAdd : ExclusiveLocksToAdd, Attr,
1759 Exp, D: FunDecl, PredBlock, CurrBlock, BrE: Attr->getSuccessValue(),
1760 Neg: Negate);
1761
1762 // Add and remove locks.
1763 SourceLocation Loc = Exp->getExprLoc();
1764 for (const auto &ExclusiveLockToAdd : ExclusiveLocksToAdd)
1765 addLock(FSet&: Result, Entry: FactMan.createFact<LockableFactEntry>(Args: ExclusiveLockToAdd,
1766 Args: LK_Exclusive, Args&: Loc));
1767 for (const auto &SharedLockToAdd : SharedLocksToAdd)
1768 addLock(FSet&: Result, Entry: FactMan.createFact<LockableFactEntry>(Args: SharedLockToAdd,
1769 Args: LK_Shared, Args&: Loc));
1770}
1771
1772/// If the terminator of \p Block branches on the result of a try-lock call
1773/// (possibly stored in a local variable), add the capabilities acquired by
1774/// that call to \p Caps.
1775void ThreadSafetyAnalyzer::getTerminatorTrylockCaps(const CFGBlock *Block,
1776 CapExprSet &Caps) {
1777 bool Negate = false;
1778 auto [Exp, FunDecl, Cleanup] = getTerminatorTrylockCall(Block, Negate);
1779 if (!Exp)
1780 return;
1781
1782 for (const auto *Attr : FunDecl->specific_attrs<TryAcquireCapabilityAttr>())
1783 getMutexIDs(Mtxs&: Caps, Attr, Exp, D: FunDecl);
1784}
1785
1786namespace {
1787
1788/// We use this class to visit different types of expressions in
1789/// CFGBlocks, and build up the lockset.
1790/// An expression may cause us to add or remove locks from the lockset, or else
1791/// output error messages related to missing locks.
1792/// FIXME: In future, we may be able to not inherit from a visitor.
1793class BuildLockset : public ConstStmtVisitor<BuildLockset> {
1794 friend class ThreadSafetyAnalyzer;
1795
1796 ThreadSafetyAnalyzer *Analyzer;
1797 FactSet FSet;
1798 // The fact set for the function on exit.
1799 const FactSet &FunctionExitFSet;
1800
1801 /// A `LocalVariableMap::Context` wrapper that groups a context 'Q' with its
1802 /// immediate predecessor 'P' for a program point. If the program point is
1803 /// right after a Stmt 'S', 'P' is the pre-context of 'S' and 'Q' is the
1804 /// post-context of 'S'. Otherwise, 'P' == 'Q'.
1805 ///
1806 /// A DualLocalVarContext sets the global context for VarDefinition lookup to
1807 /// the post-context 'Q', once CREATED or UPDATED to the next program
1808 /// point. One can temporarily switch the global context to either 'P' or 'Q'
1809 /// using `switchToContextForScope`. The lifetime of the global context
1810 /// switching is bound to the enclosing scope. The global context will be set
1811 /// back to the prior state by the end of the scope. This is done by the
1812 /// returned ContextSwitchScope object.
1813 ///
1814 /// Note: The pre- and post-context of a Stmt are distinct only in Beta mode
1815 /// (i.e., `Analyzer.Handler.issueBetaWarnings()`) because of the
1816 /// out-parameter validation. If not in Beta mode, the global context for
1817 /// VarDefinition lookup is invisible, thus this wrapper has no impact on the
1818 /// analysis.
1819 class DualLocalVarContext {
1820 public:
1821 enum Point : char { Pre = 0, Post = 1 };
1822
1823 class ContextSwitchScope {
1824 DualLocalVarContext &DC;
1825 Point LastPoint;
1826
1827 public:
1828 ContextSwitchScope(DualLocalVarContext &DC, Point LastPoint)
1829 : DC(DC), LastPoint(LastPoint) {}
1830 ContextSwitchScope(const ContextSwitchScope &) = delete;
1831 ContextSwitchScope &operator=(const ContextSwitchScope &) = delete;
1832 ~ContextSwitchScope() { DC.switchContextTo(P: LastPoint); }
1833 };
1834
1835 /// Temporarily switch context to \p P as long as the returned object lives.
1836 [[nodiscard]] ContextSwitchScope switchToContextForScope(Point P) {
1837 Point PriorPoint = CurrPoint;
1838 switchContextTo(P);
1839 return ContextSwitchScope(*this, PriorPoint);
1840 }
1841
1842 /// Update the pre- and post-contexts to be associated with the next Stmt \p
1843 /// S. Set the global context to the post-context of \p S upon returning.
1844 ///
1845 /// If \p S is null, the behavior is as if the Stmt is a no-op--the
1846 /// post-context will shift to be the pre-context and the new post-context
1847 /// is the same as the old one, resulting in identical pre- and
1848 /// post-contexts.
1849 void moveToNextContext(const Stmt *S) {
1850 PrePost[Pre] = PrePost[Post];
1851
1852 const LocalVariableMap::Context &NewPostCtx =
1853 S ? Analyzer.LocalVarMap.getNextContext(CtxIndex, S, C: *PrePost[Post])
1854 : *PrePost[Pre];
1855
1856 PrePost[Post] = &NewPostCtx;
1857 switchContextTo(P: Post);
1858 }
1859
1860 /// Constructs a DualLocalVarContext for the entry program point, where pre-
1861 /// and post-contexts are both equal to the \p EntryContext.
1862 DualLocalVarContext(ThreadSafetyAnalyzer &Analyzer, unsigned EntryIdx,
1863 const LocalVariableMap::Context *EntryContext)
1864 : Analyzer(Analyzer), PrePost{EntryContext, EntryContext},
1865 CurrPoint(Post), CtxIndex(EntryIdx) {
1866 assert(EntryContext);
1867 switchContextTo(P: Post);
1868 }
1869
1870 private:
1871 ThreadSafetyAnalyzer &Analyzer;
1872 // PrePost[0] points to the pre-context and
1873 // PrePost[1] points to the post-context:
1874 std::array<const LocalVariableMap::Context *, 2> PrePost;
1875 Point CurrPoint;
1876 unsigned CtxIndex;
1877
1878 void switchContextTo(Point P) {
1879 if (!Analyzer.Handler.issueBetaWarnings())
1880 return;
1881 Analyzer.SxBuilder.setLookupLocalVarExpr(
1882 [Ctx = *PrePost[P],
1883 Analyzer = &Analyzer](const NamedDecl *D) mutable -> const Expr * {
1884 return Analyzer->LocalVarMap.lookupExpr(D, Ctx);
1885 });
1886 CurrPoint = P;
1887 }
1888 };
1889
1890 DualLocalVarContext LVarCtx;
1891
1892 // To update the context used in attr-expr translation. If `S` is non-null,
1893 // the context is updated to the program point right after 'S'.
1894 void updateLocalVarMapCtx(const Stmt *S) { LVarCtx.moveToNextContext(S); }
1895
1896 // helper functions
1897
1898 void checkAccess(const Expr *Exp, AccessKind AK,
1899 ProtectedOperationKind POK = POK_VarAccess) {
1900 Analyzer->checkAccess(FSet, Exp, AK, POK);
1901 }
1902 void checkPtAccess(const Expr *Exp, AccessKind AK,
1903 ProtectedOperationKind POK = POK_VarAccess) {
1904 Analyzer->checkPtAccess(FSet, Exp, AK, POK);
1905 }
1906
1907 void handleCall(const Expr *Exp, const NamedDecl *D,
1908 til::SExpr *Self = nullptr,
1909 SourceLocation Loc = SourceLocation());
1910 void examineArguments(const FunctionDecl *FD,
1911 CallExpr::const_arg_iterator ArgBegin,
1912 CallExpr::const_arg_iterator ArgEnd,
1913 bool SkipFirstParam = false);
1914
1915public:
1916 BuildLockset(ThreadSafetyAnalyzer *Anlzr, CFGBlockInfo &Info,
1917 const FactSet &FunctionExitFSet)
1918 : ConstStmtVisitor<BuildLockset>(), Analyzer(Anlzr), FSet(Info.EntrySet),
1919 FunctionExitFSet(FunctionExitFSet),
1920 LVarCtx(*Analyzer, Info.EntryIndex, &Info.EntryContext) {
1921 updateLocalVarMapCtx(S: nullptr);
1922 }
1923
1924 ~BuildLockset() { Analyzer->SxBuilder.setLookupLocalVarExpr(nullptr); }
1925 BuildLockset(const BuildLockset &) = delete;
1926 BuildLockset &operator=(const BuildLockset &) = delete;
1927
1928 void VisitUnaryOperator(const UnaryOperator *UO);
1929 void VisitBinaryOperator(const BinaryOperator *BO);
1930 void VisitCastExpr(const CastExpr *CE);
1931 void VisitCallExpr(const CallExpr *Exp);
1932 void VisitCXXConstructExpr(const CXXConstructExpr *Exp);
1933 void VisitDeclStmt(const DeclStmt *S);
1934 void VisitMaterializeTemporaryExpr(const MaterializeTemporaryExpr *Exp);
1935 void VisitReturnStmt(const ReturnStmt *S);
1936};
1937
1938} // namespace
1939
1940/// Warn if the LSet does not contain a lock sufficient to protect access
1941/// of at least the passed in AccessKind.
1942void ThreadSafetyAnalyzer::warnIfMutexNotHeld(
1943 const FactSet &FSet, const NamedDecl *D, const Expr *Exp, AccessKind AK,
1944 Expr *MutexExp, ProtectedOperationKind POK, til::SExpr *Self,
1945 SourceLocation Loc) {
1946 LockKind LK = getLockKindFromAccessKind(AK);
1947 CapabilityExpr Cp = SxBuilder.translateAttrExpr(AttrExp: MutexExp, D, DeclExp: Exp, Self);
1948 if (Cp.isInvalid()) {
1949 warnInvalidLock(Handler, MutexExp, D, DeclExp: Exp, Kind: Cp.getKind());
1950 return;
1951 } else if (Cp.shouldIgnore()) {
1952 return;
1953 }
1954
1955 if (Cp.negative()) {
1956 // Negative capabilities act like locks excluded
1957 const FactEntry *LDat = FSet.findLock(FM&: FactMan, CapE: !Cp);
1958 if (LDat) {
1959 Handler.handleFunExcludesLock(Kind: Cp.getKind(), FunName: D->getNameAsString(),
1960 LockName: (!Cp).toString(), Loc);
1961 return;
1962 }
1963
1964 // If this does not refer to a negative capability in the same class,
1965 // then stop here.
1966 if (!inCurrentScope(CapE: Cp))
1967 return;
1968
1969 // Otherwise the negative requirement must be propagated to the caller.
1970 LDat = FSet.findLock(FM&: FactMan, CapE: Cp);
1971 if (!LDat) {
1972 Handler.handleNegativeNotHeld(D, LockName: Cp.toString(), Loc);
1973 }
1974 return;
1975 }
1976
1977 const FactEntry *LDat = FSet.findLockUniv(FM&: FactMan, CapE: Cp);
1978 bool NoError = true;
1979 if (!LDat) {
1980 // No exact match found. Look for a partial match.
1981 LDat = FSet.findPartialMatch(FM&: FactMan, CapE: Cp);
1982 if (LDat) {
1983 // Warn that there's no precise match.
1984 std::string PartMatchStr = LDat->toString();
1985 StringRef PartMatchName(PartMatchStr);
1986 Handler.handleMutexNotHeld(Kind: Cp.getKind(), D, POK, LockName: Cp.toString(), LK, Loc,
1987 PossibleMatch: &PartMatchName);
1988 } else {
1989 // Warn that there's no match at all.
1990 Handler.handleMutexNotHeld(Kind: Cp.getKind(), D, POK, LockName: Cp.toString(), LK, Loc);
1991 }
1992 NoError = false;
1993 }
1994 // Make sure the mutex we found is the right kind.
1995 if (NoError && LDat && !LDat->isAtLeast(LK)) {
1996 Handler.handleMutexNotHeld(Kind: Cp.getKind(), D, POK, LockName: Cp.toString(), LK, Loc);
1997 }
1998}
1999
2000void ThreadSafetyAnalyzer::warnIfAnyMutexNotHeldForRead(
2001 const FactSet &FSet, const NamedDecl *D, const Expr *Exp,
2002 llvm::ArrayRef<Expr *> Args, ProtectedOperationKind POK,
2003 SourceLocation Loc) {
2004 SmallVector<CapabilityExpr, 2> Caps;
2005 for (auto *Arg : Args) {
2006 CapabilityExpr Cp = SxBuilder.translateAttrExpr(AttrExp: Arg, D, DeclExp: Exp, Self: nullptr);
2007 if (Cp.isInvalid()) {
2008 warnInvalidLock(Handler, MutexExp: Arg, D, DeclExp: Exp, Kind: Cp.getKind());
2009 continue;
2010 }
2011 if (Cp.shouldIgnore())
2012 continue;
2013 const FactEntry *LDat = FSet.findLockUniv(FM&: FactMan, CapE: Cp);
2014 if (LDat && LDat->isAtLeast(LK: LK_Shared))
2015 return; // At least one held — read access is safe.
2016 // FIXME: try findPartialMatch as a fallback to support
2017 // -Wno-thread-safety-precise, as warnIfMutexNotHeld does.
2018 Caps.push_back(Elt: Cp);
2019 }
2020 if (Caps.empty())
2021 return;
2022 // Materialize names only now that we know we are going to warn.
2023 SmallVector<std::string, 2> NameStorage;
2024 SmallVector<StringRef, 2> Names;
2025 for (const auto &Cp : Caps) {
2026 NameStorage.push_back(Elt: Cp.toString());
2027 Names.push_back(Elt: NameStorage.back());
2028 }
2029 Handler.handleGuardedByAnyReadNotHeld(D, POK, LockNames: Names, Loc);
2030}
2031
2032/// Warn if the LSet contains the given lock.
2033void ThreadSafetyAnalyzer::warnIfMutexHeld(const FactSet &FSet,
2034 const NamedDecl *D, const Expr *Exp,
2035 Expr *MutexExp, til::SExpr *Self,
2036 SourceLocation Loc) {
2037 CapabilityExpr Cp = SxBuilder.translateAttrExpr(AttrExp: MutexExp, D, DeclExp: Exp, Self);
2038 if (Cp.isInvalid()) {
2039 warnInvalidLock(Handler, MutexExp, D, DeclExp: Exp, Kind: Cp.getKind());
2040 return;
2041 } else if (Cp.shouldIgnore()) {
2042 return;
2043 }
2044
2045 const FactEntry *LDat = FSet.findLock(FM&: FactMan, CapE: Cp);
2046 if (LDat) {
2047 Handler.handleFunExcludesLock(Kind: Cp.getKind(), FunName: D->getNameAsString(),
2048 LockName: Cp.toString(), Loc);
2049 }
2050}
2051
2052/// Checks guarded_by and pt_guarded_by attributes.
2053/// Whenever we identify an access (read or write) to a DeclRefExpr that is
2054/// marked with guarded_by, we must ensure the appropriate mutexes are held.
2055/// Similarly, we check if the access is to an expression that dereferences
2056/// a pointer marked with pt_guarded_by.
2057void ThreadSafetyAnalyzer::checkAccess(const FactSet &FSet, const Expr *Exp,
2058 AccessKind AK,
2059 ProtectedOperationKind POK) {
2060 Exp = Exp->IgnoreImplicit()->IgnoreParenCasts();
2061
2062 SourceLocation Loc = Exp->getExprLoc();
2063
2064 // Local variables of reference type cannot be re-assigned;
2065 // map them to their initializer.
2066 while (const auto *DRE = dyn_cast<DeclRefExpr>(Val: Exp)) {
2067 const auto *VD = dyn_cast<VarDecl>(Val: DRE->getDecl()->getCanonicalDecl());
2068 if (VD && VD->isLocalVarDecl() && VD->getType()->isReferenceType()) {
2069 if (const auto *E = VD->getInit()) {
2070 // Guard against self-initialization. e.g., int &i = i;
2071 if (E == Exp)
2072 break;
2073 Exp = E->IgnoreImplicit()->IgnoreParenCasts();
2074 continue;
2075 }
2076 }
2077 break;
2078 }
2079
2080 if (const auto *UO = dyn_cast<UnaryOperator>(Val: Exp)) {
2081 // For dereferences
2082 if (UO->getOpcode() == UO_Deref)
2083 checkPtAccess(FSet, Exp: UO->getSubExpr(), AK, POK);
2084 return;
2085 }
2086
2087 if (const auto *BO = dyn_cast<BinaryOperator>(Val: Exp)) {
2088 switch (BO->getOpcode()) {
2089 case BO_PtrMemD: // .*
2090 return checkAccess(FSet, Exp: BO->getLHS(), AK, POK);
2091 case BO_PtrMemI: // ->*
2092 return checkPtAccess(FSet, Exp: BO->getLHS(), AK, POK);
2093 default:
2094 return;
2095 }
2096 }
2097
2098 if (const auto *AE = dyn_cast<ArraySubscriptExpr>(Val: Exp)) {
2099 checkPtAccess(FSet, Exp: AE->getLHS(), AK, POK);
2100 return;
2101 }
2102
2103 if (const auto *ME = dyn_cast<MemberExpr>(Val: Exp)) {
2104 if (ME->isArrow())
2105 checkPtAccess(FSet, Exp: ME->getBase(), AK, POK);
2106 else
2107 checkAccess(FSet, Exp: ME->getBase(), AK, POK);
2108 }
2109
2110 const ValueDecl *D = getValueDecl(Exp);
2111 if (!D || !D->hasAttrs())
2112 return;
2113
2114 if (D->hasAttr<GuardedVarAttr>() && FSet.isEmpty(FactMan)) {
2115 Handler.handleNoMutexHeld(D, POK, AK, Loc);
2116 }
2117
2118 for (const auto *I : D->specific_attrs<GuardedByAttr>()) {
2119 if (AK == AK_Written || I->args_size() == 1) {
2120 // Write requires all capabilities; single-arg read uses the normal
2121 // per-lock warning path.
2122 for (auto *Arg : I->args())
2123 warnIfMutexNotHeld(FSet, D, Exp, AK, MutexExp: Arg, POK, Self: nullptr, Loc);
2124 } else {
2125 // Multi-arg read: holding any one of the listed capabilities is
2126 // sufficient (a writer must hold all, so any one prevents writes).
2127 warnIfAnyMutexNotHeldForRead(FSet, D, Exp, Args: I->args(), POK, Loc);
2128 }
2129 }
2130}
2131
2132/// Checks pt_guarded_by and pt_guarded_var attributes.
2133/// POK is the same operationKind that was passed to checkAccess.
2134void ThreadSafetyAnalyzer::checkPtAccess(const FactSet &FSet, const Expr *Exp,
2135 AccessKind AK,
2136 ProtectedOperationKind POK) {
2137 // Strip off paren- and cast-expressions, checking if we encounter any other
2138 // operator that should be delegated to checkAccess() instead.
2139 while (true) {
2140 if (const auto *PE = dyn_cast<ParenExpr>(Val: Exp)) {
2141 Exp = PE->getSubExpr();
2142 continue;
2143 }
2144 if (const auto *CE = dyn_cast<CastExpr>(Val: Exp)) {
2145 if (CE->getCastKind() == CK_ArrayToPointerDecay) {
2146 // If it's an actual array, and not a pointer, then it's elements
2147 // are protected by GUARDED_BY, not PT_GUARDED_BY;
2148 checkAccess(FSet, Exp: CE->getSubExpr(), AK, POK);
2149 return;
2150 }
2151 Exp = CE->getSubExpr();
2152 continue;
2153 }
2154 break;
2155 }
2156
2157 if (const auto *UO = dyn_cast<UnaryOperator>(Val: Exp)) {
2158 if (UO->getOpcode() == UO_AddrOf) {
2159 // Pointer access via pointer taken of variable, so the dereferenced
2160 // variable is not actually a pointer.
2161 checkAccess(FSet, Exp: UO->getSubExpr(), AK, POK);
2162 return;
2163 }
2164 }
2165
2166 // Pass by reference/pointer warnings are under a different flag.
2167 ProtectedOperationKind PtPOK = POK_VarDereference;
2168 switch (POK) {
2169 case POK_PassByRef:
2170 PtPOK = POK_PtPassByRef;
2171 break;
2172 case POK_ReturnByRef:
2173 PtPOK = POK_PtReturnByRef;
2174 break;
2175 case POK_PassPointer:
2176 PtPOK = POK_PtPassPointer;
2177 break;
2178 case POK_ReturnPointer:
2179 PtPOK = POK_PtReturnPointer;
2180 break;
2181 default:
2182 break;
2183 }
2184
2185 const ValueDecl *D = getValueDecl(Exp);
2186 if (!D || !D->hasAttrs())
2187 return;
2188
2189 if (D->hasAttr<PtGuardedVarAttr>() && FSet.isEmpty(FactMan))
2190 Handler.handleNoMutexHeld(D, POK: PtPOK, AK, Loc: Exp->getExprLoc());
2191
2192 for (auto const *I : D->specific_attrs<PtGuardedByAttr>()) {
2193 if (AK == AK_Written || I->args_size() == 1) {
2194 // Write requires all capabilities; single-arg read uses the normal
2195 // per-lock warning path.
2196 for (auto *Arg : I->args())
2197 warnIfMutexNotHeld(FSet, D, Exp, AK, MutexExp: Arg, POK: PtPOK, Self: nullptr,
2198 Loc: Exp->getExprLoc());
2199 } else {
2200 // Multi-arg read: holding any one of the listed capabilities is
2201 // sufficient (a writer must hold all, so any one prevents writes).
2202 warnIfAnyMutexNotHeldForRead(FSet, D, Exp, Args: I->args(), POK: PtPOK,
2203 Loc: Exp->getExprLoc());
2204 }
2205 }
2206}
2207
2208/// Process a function call, method call, constructor call,
2209/// or destructor call. This involves looking at the attributes on the
2210/// corresponding function/method/constructor/destructor, issuing warnings,
2211/// and updating the locksets accordingly.
2212///
2213/// FIXME: For classes annotated with one of the guarded annotations, we need
2214/// to treat const method calls as reads and non-const method calls as writes,
2215/// and check that the appropriate locks are held. Non-const method calls with
2216/// the same signature as const method calls can be also treated as reads.
2217///
2218/// \param Exp The call expression.
2219/// \param D The callee declaration.
2220/// \param Self If \p Exp = nullptr, the implicit this argument or the argument
2221/// of an implicitly called cleanup function.
2222/// \param Loc If \p Exp = nullptr, the location.
2223void BuildLockset::handleCall(const Expr *Exp, const NamedDecl *D,
2224 til::SExpr *Self, SourceLocation Loc) {
2225 // Move to the call Stmt so that both pre- and post-context are available.
2226 updateLocalVarMapCtx(S: Exp);
2227
2228 // Most function attributes are associated with the pre-context. Exceptions
2229 // are AcquireCapability and AssertCapability, which ensure some locks are
2230 // held after the call, and thus are associated with the post-context. They
2231 // will require a temporary switch to the post-context during handling.
2232 //
2233 // Parameter attributes are restricted to scoped objects, and thus are NOT
2234 // context-sensitive.
2235 auto PreContextForThisScope =
2236 LVarCtx.switchToContextForScope(P: DualLocalVarContext::Pre);
2237 CapExprSet ExclusiveLocksToAdd, SharedLocksToAdd;
2238 CapExprSet ExclusiveLocksToRemove, SharedLocksToRemove, GenericLocksToRemove;
2239 CapExprSet ScopedReqsAndExcludes;
2240
2241 // Figure out if we're constructing an object of scoped lockable class
2242 CapabilityExpr Scp;
2243 if (Exp) {
2244 assert(!Self);
2245 const auto *TagT = Exp->getType()->getAs<TagType>();
2246 if (D->hasAttrs() && TagT && Exp->isPRValue()) {
2247 til::LiteralPtr *Placeholder =
2248 Analyzer->SxBuilder.createThisPlaceholder();
2249 [[maybe_unused]] auto inserted =
2250 Analyzer->ConstructedObjects.insert(KV: {Exp, Placeholder});
2251 assert(inserted.second && "Are we visiting the same expression again?");
2252 if (isa<CXXConstructExpr>(Val: Exp))
2253 Self = Placeholder;
2254 if (TagT->getDecl()->getMostRecentDecl()->hasAttr<ScopedLockableAttr>())
2255 Scp = CapabilityExpr(Placeholder, Exp->getType(), /*Neg=*/false);
2256 }
2257
2258 assert(Loc.isInvalid());
2259 Loc = Exp->getExprLoc();
2260 }
2261
2262 for(const Attr *At : D->attrs()) {
2263 switch (At->getKind()) {
2264 // When we encounter a lock function, we need to add the lock to our
2265 // lockset.
2266 case attr::AcquireCapability: {
2267 auto PostContextForThisScope =
2268 LVarCtx.switchToContextForScope(P: DualLocalVarContext::Post);
2269 const auto *A = cast<AcquireCapabilityAttr>(Val: At);
2270 Analyzer->getMutexIDs(Mtxs&: A->isShared() ? SharedLocksToAdd
2271 : ExclusiveLocksToAdd,
2272 Attr: A, Exp, D, Self);
2273 break;
2274 }
2275
2276 // An assert will add a lock to the lockset, but will not generate
2277 // a warning if it is already there, and will not generate a warning
2278 // if it is not removed.
2279 case attr::AssertCapability: {
2280 auto PostContextForThisScope =
2281 LVarCtx.switchToContextForScope(P: DualLocalVarContext::Post);
2282 const auto *A = cast<AssertCapabilityAttr>(Val: At);
2283 CapExprSet AssertLocks;
2284 Analyzer->getMutexIDs(Mtxs&: AssertLocks, Attr: A, Exp, D, Self);
2285 for (const auto &AssertLock : AssertLocks)
2286 Analyzer->addLock(
2287 FSet, Entry: Analyzer->FactMan.createFact<LockableFactEntry>(
2288 Args: AssertLock, Args: A->isShared() ? LK_Shared : LK_Exclusive,
2289 Args&: Loc, Args: FactEntry::Asserted));
2290 break;
2291 }
2292
2293 // When we encounter an unlock function, we need to remove unlocked
2294 // mutexes from the lockset, and flag a warning if they are not there.
2295 case attr::ReleaseCapability: {
2296 const auto *A = cast<ReleaseCapabilityAttr>(Val: At);
2297 if (A->isGeneric())
2298 Analyzer->getMutexIDs(Mtxs&: GenericLocksToRemove, Attr: A, Exp, D, Self);
2299 else if (A->isShared())
2300 Analyzer->getMutexIDs(Mtxs&: SharedLocksToRemove, Attr: A, Exp, D, Self);
2301 else
2302 Analyzer->getMutexIDs(Mtxs&: ExclusiveLocksToRemove, Attr: A, Exp, D, Self);
2303 break;
2304 }
2305
2306 case attr::RequiresCapability: {
2307 const auto *A = cast<RequiresCapabilityAttr>(Val: At);
2308 for (auto *Arg : A->args()) {
2309 Analyzer->warnIfMutexNotHeld(FSet, D, Exp,
2310 AK: A->isShared() ? AK_Read : AK_Written,
2311 MutexExp: Arg, POK: POK_FunctionCall, Self, Loc);
2312 // use for adopting a lock
2313 if (!Scp.shouldIgnore())
2314 Analyzer->getMutexIDs(Mtxs&: ScopedReqsAndExcludes, Attr: A, Exp, D, Self);
2315 }
2316 break;
2317 }
2318
2319 case attr::LocksExcluded: {
2320 const auto *A = cast<LocksExcludedAttr>(Val: At);
2321 for (auto *Arg : A->args()) {
2322 Analyzer->warnIfMutexHeld(FSet, D, Exp, MutexExp: Arg, Self, Loc);
2323 // use for deferring a lock
2324 if (!Scp.shouldIgnore())
2325 Analyzer->getMutexIDs(Mtxs&: ScopedReqsAndExcludes, Attr: A, Exp, D, Self);
2326 }
2327 break;
2328 }
2329
2330 // Ignore attributes unrelated to thread-safety
2331 default:
2332 break;
2333 }
2334 }
2335
2336 std::optional<CallExpr::const_arg_range> Args;
2337 if (Exp) {
2338 if (const auto *CE = dyn_cast<CallExpr>(Val: Exp))
2339 Args = CE->arguments();
2340 else if (const auto *CE = dyn_cast<CXXConstructExpr>(Val: Exp))
2341 Args = CE->arguments();
2342 else
2343 llvm_unreachable("Unknown call kind");
2344 }
2345 const auto *CalledFunction = dyn_cast<FunctionDecl>(Val: D);
2346 if (CalledFunction && Args.has_value()) {
2347 for (auto [Param, Arg] : zip(t: CalledFunction->parameters(), u&: *Args)) {
2348 if (isCallbackParam(Param))
2349 continue;
2350 CapExprSet DeclaredLocks;
2351 for (const Attr *At : Param->attrs()) {
2352 switch (At->getKind()) {
2353 case attr::AcquireCapability: {
2354 const auto *A = cast<AcquireCapabilityAttr>(Val: At);
2355 Analyzer->getMutexIDs(Mtxs&: A->isShared() ? SharedLocksToAdd
2356 : ExclusiveLocksToAdd,
2357 Attr: A, Exp, D, Self);
2358 Analyzer->getMutexIDs(Mtxs&: DeclaredLocks, Attr: A, Exp, D, Self);
2359 break;
2360 }
2361
2362 case attr::ReleaseCapability: {
2363 const auto *A = cast<ReleaseCapabilityAttr>(Val: At);
2364 if (A->isGeneric())
2365 Analyzer->getMutexIDs(Mtxs&: GenericLocksToRemove, Attr: A, Exp, D, Self);
2366 else if (A->isShared())
2367 Analyzer->getMutexIDs(Mtxs&: SharedLocksToRemove, Attr: A, Exp, D, Self);
2368 else
2369 Analyzer->getMutexIDs(Mtxs&: ExclusiveLocksToRemove, Attr: A, Exp, D, Self);
2370 Analyzer->getMutexIDs(Mtxs&: DeclaredLocks, Attr: A, Exp, D, Self);
2371 break;
2372 }
2373
2374 case attr::RequiresCapability: {
2375 const auto *A = cast<RequiresCapabilityAttr>(Val: At);
2376 for (auto *Arg : A->args())
2377 Analyzer->warnIfMutexNotHeld(FSet, D, Exp,
2378 AK: A->isShared() ? AK_Read : AK_Written,
2379 MutexExp: Arg, POK: POK_FunctionCall, Self, Loc);
2380 Analyzer->getMutexIDs(Mtxs&: DeclaredLocks, Attr: A, Exp, D, Self);
2381 break;
2382 }
2383
2384 case attr::LocksExcluded: {
2385 const auto *A = cast<LocksExcludedAttr>(Val: At);
2386 for (auto *Arg : A->args())
2387 Analyzer->warnIfMutexHeld(FSet, D, Exp, MutexExp: Arg, Self, Loc);
2388 Analyzer->getMutexIDs(Mtxs&: DeclaredLocks, Attr: A, Exp, D, Self);
2389 break;
2390 }
2391
2392 default:
2393 break;
2394 }
2395 }
2396 if (DeclaredLocks.empty())
2397 continue;
2398 CapabilityExpr Cp(Analyzer->SxBuilder.translate(S: Arg, Ctx: nullptr),
2399 StringRef("mutex"), /*Neg=*/false, /*Reentrant=*/false);
2400 if (const auto *CBTE = dyn_cast<CXXBindTemporaryExpr>(Val: Arg->IgnoreCasts());
2401 Cp.isInvalid() && CBTE) {
2402 if (auto Object = Analyzer->ConstructedObjects.find(Val: CBTE->getSubExpr());
2403 Object != Analyzer->ConstructedObjects.end())
2404 Cp = CapabilityExpr(Object->second, StringRef("mutex"), /*Neg=*/false,
2405 /*Reentrant=*/false);
2406 }
2407 const FactEntry *Fact = FSet.findLock(FM&: Analyzer->FactMan, CapE: Cp);
2408 if (!Fact) {
2409 Analyzer->Handler.handleMutexNotHeld(Kind: Cp.getKind(), D, POK: POK_FunctionCall,
2410 LockName: Cp.toString(), LK: LK_Exclusive,
2411 Loc: Exp->getExprLoc());
2412 continue;
2413 }
2414 const auto *Scope = cast<ScopedLockableFactEntry>(Val: Fact);
2415 for (const auto &[a, b] :
2416 zip_longest(t&: DeclaredLocks, u: Scope->getUnderlyingMutexes())) {
2417 if (!a.has_value()) {
2418 Analyzer->Handler.handleExpectFewerUnderlyingMutexes(
2419 Loc: Exp->getExprLoc(), DLoc: D->getLocation(), ScopeName: Scope->toString(),
2420 Kind: b.value().getKind(), Actual: b.value().toString());
2421 } else if (!b.has_value()) {
2422 Analyzer->Handler.handleExpectMoreUnderlyingMutexes(
2423 Loc: Exp->getExprLoc(), DLoc: D->getLocation(), ScopeName: Scope->toString(),
2424 Kind: a.value().getKind(), Expected: a.value().toString());
2425 } else if (!a.value().equals(other: b.value())) {
2426 Analyzer->Handler.handleUnmatchedUnderlyingMutexes(
2427 Loc: Exp->getExprLoc(), DLoc: D->getLocation(), ScopeName: Scope->toString(),
2428 Kind: a.value().getKind(), Expected: a.value().toString(), Actual: b.value().toString());
2429 break;
2430 }
2431 }
2432 }
2433 }
2434 // Remove locks first to allow lock upgrading/downgrading.
2435 // FIXME -- should only fully remove if the attribute refers to 'this'.
2436 bool Dtor = isa<CXXDestructorDecl>(Val: D);
2437 for (const auto &M : ExclusiveLocksToRemove)
2438 Analyzer->removeLock(FSet, Cp: M, UnlockLoc: Loc, FullyRemove: Dtor, ReceivedKind: LK_Exclusive);
2439 for (const auto &M : SharedLocksToRemove)
2440 Analyzer->removeLock(FSet, Cp: M, UnlockLoc: Loc, FullyRemove: Dtor, ReceivedKind: LK_Shared);
2441 for (const auto &M : GenericLocksToRemove)
2442 Analyzer->removeLock(FSet, Cp: M, UnlockLoc: Loc, FullyRemove: Dtor, ReceivedKind: LK_Generic);
2443
2444 // Add locks.
2445 FactEntry::SourceKind Source =
2446 !Scp.shouldIgnore() ? FactEntry::Managed : FactEntry::Acquired;
2447 for (const auto &M : ExclusiveLocksToAdd)
2448 Analyzer->addLock(FSet, Entry: Analyzer->FactMan.createFact<LockableFactEntry>(
2449 Args: M, Args: LK_Exclusive, Args&: Loc, Args&: Source));
2450 for (const auto &M : SharedLocksToAdd)
2451 Analyzer->addLock(FSet, Entry: Analyzer->FactMan.createFact<LockableFactEntry>(
2452 Args: M, Args: LK_Shared, Args&: Loc, Args&: Source));
2453
2454 if (!Scp.shouldIgnore()) {
2455 // Add the managing object as a dummy mutex, mapped to the underlying mutex.
2456 auto *ScopedEntry = Analyzer->FactMan.createFact<ScopedLockableFactEntry>(
2457 Args&: Scp, Args&: Loc, Args: FactEntry::Acquired,
2458 Args: ExclusiveLocksToAdd.size() + SharedLocksToAdd.size() +
2459 ScopedReqsAndExcludes.size() + ExclusiveLocksToRemove.size() +
2460 SharedLocksToRemove.size());
2461 for (const auto &M : ExclusiveLocksToAdd)
2462 ScopedEntry->addLock(M);
2463 for (const auto &M : SharedLocksToAdd)
2464 ScopedEntry->addLock(M);
2465 for (const auto &M : ScopedReqsAndExcludes)
2466 ScopedEntry->addLock(M);
2467 for (const auto &M : ExclusiveLocksToRemove)
2468 ScopedEntry->addExclusiveUnlock(M);
2469 for (const auto &M : SharedLocksToRemove)
2470 ScopedEntry->addSharedUnlock(M);
2471 Analyzer->addLock(FSet, Entry: ScopedEntry);
2472 }
2473}
2474
2475/// For unary operations which read and write a variable, we need to
2476/// check whether we hold any required mutexes. Reads are checked in
2477/// VisitCastExpr.
2478void BuildLockset::VisitUnaryOperator(const UnaryOperator *UO) {
2479 switch (UO->getOpcode()) {
2480 case UO_PostDec:
2481 case UO_PostInc:
2482 case UO_PreDec:
2483 case UO_PreInc:
2484 checkAccess(Exp: UO->getSubExpr(), AK: AK_Written);
2485 break;
2486 default:
2487 break;
2488 }
2489}
2490
2491/// For binary operations which assign to a variable (writes), we need to check
2492/// whether we hold any required mutexes.
2493/// FIXME: Deal with non-primitive types.
2494void BuildLockset::VisitBinaryOperator(const BinaryOperator *BO) {
2495 if (!BO->isAssignmentOp())
2496 return;
2497 checkAccess(Exp: BO->getLHS(), AK: AK_Written);
2498 updateLocalVarMapCtx(S: BO);
2499}
2500
2501/// Whenever we do an LValue to Rvalue cast, we are reading a variable and
2502/// need to ensure we hold any required mutexes.
2503/// FIXME: Deal with non-primitive types.
2504void BuildLockset::VisitCastExpr(const CastExpr *CE) {
2505 if (CE->getCastKind() != CK_LValueToRValue)
2506 return;
2507 checkAccess(Exp: CE->getSubExpr(), AK: AK_Read);
2508}
2509
2510void BuildLockset::examineArguments(const FunctionDecl *FD,
2511 CallExpr::const_arg_iterator ArgBegin,
2512 CallExpr::const_arg_iterator ArgEnd,
2513 bool SkipFirstParam) {
2514 // Currently we can't do anything if we don't know the function declaration.
2515 if (!FD)
2516 return;
2517
2518 // NO_THREAD_SAFETY_ANALYSIS does double duty here. Normally it
2519 // only turns off checking within the body of a function, but we also
2520 // use it to turn off checking in arguments to the function. This
2521 // could result in some false negatives, but the alternative is to
2522 // create yet another attribute.
2523 if (FD->hasAttr<NoThreadSafetyAnalysisAttr>())
2524 return;
2525
2526 const ArrayRef<ParmVarDecl *> Params = FD->parameters();
2527 auto Param = Params.begin();
2528 if (SkipFirstParam)
2529 ++Param;
2530
2531 // There can be default arguments, so we stop when one iterator is at end().
2532 for (auto Arg = ArgBegin; Param != Params.end() && Arg != ArgEnd;
2533 ++Param, ++Arg) {
2534 QualType Qt = (*Param)->getType();
2535 if (Qt->isReferenceType())
2536 checkAccess(Exp: *Arg, AK: AK_Read, POK: POK_PassByRef);
2537 else if (Qt->isPointerType())
2538 checkPtAccess(Exp: *Arg, AK: AK_Read, POK: POK_PassPointer);
2539 }
2540}
2541
2542void BuildLockset::VisitCallExpr(const CallExpr *Exp) {
2543 if (const auto *CE = dyn_cast<CXXMemberCallExpr>(Val: Exp)) {
2544 const auto *ME = dyn_cast<MemberExpr>(Val: CE->getCallee());
2545 // ME can be null when calling a method pointer
2546 const CXXMethodDecl *MD = CE->getMethodDecl();
2547
2548 if (ME && MD) {
2549 if (ME->isArrow()) {
2550 // Should perhaps be AK_Written if !MD->isConst().
2551 checkPtAccess(Exp: CE->getImplicitObjectArgument(), AK: AK_Read);
2552 } else {
2553 // Should perhaps be AK_Written if !MD->isConst().
2554 checkAccess(Exp: CE->getImplicitObjectArgument(), AK: AK_Read);
2555 }
2556 }
2557
2558 examineArguments(FD: CE->getDirectCallee(), ArgBegin: CE->arg_begin(), ArgEnd: CE->arg_end());
2559 } else if (const auto *OE = dyn_cast<CXXOperatorCallExpr>(Val: Exp)) {
2560 OverloadedOperatorKind OEop = OE->getOperator();
2561 switch (OEop) {
2562 case OO_Equal:
2563 case OO_PlusEqual:
2564 case OO_MinusEqual:
2565 case OO_StarEqual:
2566 case OO_SlashEqual:
2567 case OO_PercentEqual:
2568 case OO_CaretEqual:
2569 case OO_AmpEqual:
2570 case OO_PipeEqual:
2571 case OO_LessLessEqual:
2572 case OO_GreaterGreaterEqual:
2573 checkAccess(Exp: OE->getArg(Arg: 1), AK: AK_Read);
2574 [[fallthrough]];
2575 case OO_PlusPlus:
2576 case OO_MinusMinus:
2577 checkAccess(Exp: OE->getArg(Arg: 0), AK: AK_Written);
2578 break;
2579 case OO_Star:
2580 case OO_ArrowStar:
2581 case OO_Arrow:
2582 case OO_Subscript:
2583 if (!(OEop == OO_Star && OE->getNumArgs() > 1)) {
2584 // Grrr. operator* can be multiplication...
2585 checkPtAccess(Exp: OE->getArg(Arg: 0), AK: AK_Read);
2586 }
2587 [[fallthrough]];
2588 default: {
2589 // TODO: get rid of this, and rely on pass-by-ref instead.
2590 const Expr *Obj = OE->getArg(Arg: 0);
2591 checkAccess(Exp: Obj, AK: AK_Read);
2592 // Check the remaining arguments. For method operators, the first
2593 // argument is the implicit self argument, and doesn't appear in the
2594 // FunctionDecl, but for non-methods it does.
2595 const FunctionDecl *FD = OE->getDirectCallee();
2596 examineArguments(FD, ArgBegin: std::next(x: OE->arg_begin()), ArgEnd: OE->arg_end(),
2597 /*SkipFirstParam*/ !isa<CXXMethodDecl>(Val: FD));
2598 break;
2599 }
2600 }
2601 } else {
2602 examineArguments(FD: Exp->getDirectCallee(), ArgBegin: Exp->arg_begin(), ArgEnd: Exp->arg_end());
2603 }
2604
2605 auto *D = dyn_cast_or_null<NamedDecl>(Val: Exp->getCalleeDecl());
2606
2607 if (D)
2608 handleCall(Exp, D);
2609 else
2610 // Even if we cannot handle the call, we need to update the context for the
2611 // Stmt:
2612 updateLocalVarMapCtx(S: Exp);
2613}
2614
2615void BuildLockset::VisitCXXConstructExpr(const CXXConstructExpr *Exp) {
2616 const CXXConstructorDecl *D = Exp->getConstructor();
2617 if (D && D->isCopyConstructor()) {
2618 const Expr* Source = Exp->getArg(Arg: 0);
2619 checkAccess(Exp: Source, AK: AK_Read);
2620 } else {
2621 examineArguments(FD: D, ArgBegin: Exp->arg_begin(), ArgEnd: Exp->arg_end());
2622 }
2623 if (D && D->hasAttrs())
2624 handleCall(Exp, D);
2625}
2626
2627static const Expr *UnpackConstruction(const Expr *E) {
2628 if (auto *CE = dyn_cast<CastExpr>(Val: E))
2629 if (CE->getCastKind() == CK_NoOp)
2630 E = CE->getSubExpr()->IgnoreParens();
2631 if (auto *CE = dyn_cast<CastExpr>(Val: E))
2632 if (CE->getCastKind() == CK_ConstructorConversion ||
2633 CE->getCastKind() == CK_UserDefinedConversion)
2634 E = CE->getSubExpr();
2635 if (auto *BTE = dyn_cast<CXXBindTemporaryExpr>(Val: E))
2636 E = BTE->getSubExpr();
2637 return E;
2638}
2639
2640void BuildLockset::VisitDeclStmt(const DeclStmt *S) {
2641 for (auto *D : S->getDeclGroup()) {
2642 if (auto *VD = dyn_cast_or_null<VarDecl>(Val: D)) {
2643 const Expr *E = VD->getInit();
2644 if (!E)
2645 continue;
2646 E = E->IgnoreParens();
2647
2648 // handle constructors that involve temporaries
2649 if (auto *EWC = dyn_cast<ExprWithCleanups>(Val: E))
2650 E = EWC->getSubExpr()->IgnoreParens();
2651 E = UnpackConstruction(E);
2652
2653 if (auto Object = Analyzer->ConstructedObjects.find(Val: E);
2654 Object != Analyzer->ConstructedObjects.end()) {
2655 Object->second->setClangDecl(VD);
2656 Analyzer->ConstructedObjects.erase(I: Object);
2657 }
2658 }
2659 }
2660 updateLocalVarMapCtx(S);
2661}
2662
2663void BuildLockset::VisitMaterializeTemporaryExpr(
2664 const MaterializeTemporaryExpr *Exp) {
2665 if (const ValueDecl *ExtD = Exp->getExtendingDecl()) {
2666 if (auto Object = Analyzer->ConstructedObjects.find(
2667 Val: UnpackConstruction(E: Exp->getSubExpr()));
2668 Object != Analyzer->ConstructedObjects.end()) {
2669 Object->second->setClangDecl(ExtD);
2670 Analyzer->ConstructedObjects.erase(I: Object);
2671 }
2672 }
2673}
2674
2675void BuildLockset::VisitReturnStmt(const ReturnStmt *S) {
2676 if (Analyzer->CurrentFunction == nullptr)
2677 return;
2678 const Expr *RetVal = S->getRetValue();
2679 if (!RetVal)
2680 return;
2681
2682 // If returning by reference or pointer, check that the function requires the
2683 // appropriate capabilities.
2684 const QualType ReturnType =
2685 Analyzer->CurrentFunction->getReturnType().getCanonicalType();
2686 if (ReturnType->isLValueReferenceType()) {
2687 Analyzer->checkAccess(
2688 FSet: FunctionExitFSet, Exp: RetVal,
2689 AK: ReturnType->getPointeeType().isConstQualified() ? AK_Read : AK_Written,
2690 POK: POK_ReturnByRef);
2691 } else if (ReturnType->isPointerType()) {
2692 Analyzer->checkPtAccess(
2693 FSet: FunctionExitFSet, Exp: RetVal,
2694 AK: ReturnType->getPointeeType().isConstQualified() ? AK_Read : AK_Written,
2695 POK: POK_ReturnPointer);
2696 }
2697}
2698
2699/// Given two facts merging on a join point, possibly warn and decide whether to
2700/// keep or replace.
2701///
2702/// \return false if we should keep \p A, true if we should take \p B.
2703bool ThreadSafetyAnalyzer::join(const FactEntry &A, const FactEntry &B,
2704 SourceLocation JoinLoc,
2705 LockErrorKind EntryLEK) {
2706 // Whether we can replace \p A by \p B.
2707 const bool CanModify = EntryLEK != LEK_LockedSomeLoopIterations;
2708 unsigned int ReentrancyDepthA = 0;
2709 unsigned int ReentrancyDepthB = 0;
2710
2711 if (const auto *LFE = dyn_cast<LockableFactEntry>(Val: &A))
2712 ReentrancyDepthA = LFE->getReentrancyDepth();
2713 if (const auto *LFE = dyn_cast<LockableFactEntry>(Val: &B))
2714 ReentrancyDepthB = LFE->getReentrancyDepth();
2715
2716 if (ReentrancyDepthA != ReentrancyDepthB) {
2717 Handler.handleMutexHeldEndOfScope(Kind: B.getKind(), LockName: B.toString(), LocLocked: B.loc(),
2718 LocEndOfScope: JoinLoc, LEK: EntryLEK,
2719 /*ReentrancyMismatch=*/true);
2720 // Pick the FactEntry with the greater reentrancy depth as the "good"
2721 // fact to reduce potential later warnings.
2722 return CanModify && ReentrancyDepthA < ReentrancyDepthB;
2723 } else if (A.kind() != B.kind()) {
2724 // For managed capabilities, the destructor should unlock in the right mode
2725 // anyway. For asserted capabilities no unlocking is needed.
2726 if ((A.managed() || A.asserted()) && (B.managed() || B.asserted())) {
2727 // The shared capability subsumes the exclusive capability, if possible.
2728 bool ShouldTakeB = B.kind() == LK_Shared;
2729 if (CanModify || !ShouldTakeB)
2730 return ShouldTakeB;
2731 }
2732 Handler.handleExclusiveAndShared(Kind: B.getKind(), LockName: B.toString(), Loc1: B.loc(),
2733 Loc2: A.loc());
2734 // Take the exclusive capability to reduce further warnings.
2735 return CanModify && B.kind() == LK_Exclusive;
2736 } else {
2737 // The non-asserted capability is the one we want to track.
2738 return CanModify && A.asserted() && !B.asserted();
2739 }
2740}
2741
2742/// Compute the intersection of two locksets and issue warnings for any
2743/// locks in the symmetric difference.
2744///
2745/// This function is used at a merge point in the CFG when comparing the lockset
2746/// of each branch being merged. For example, given the following sequence:
2747/// A; if () then B; else C; D; we need to check that the lockset after B and C
2748/// are the same. In the event of a difference, we use the intersection of these
2749/// two locksets at the start of D.
2750///
2751/// \param EntrySet A lockset for entry into a (possibly new) block.
2752/// \param ExitSet The lockset on exiting a preceding block.
2753/// \param JoinLoc The location of the join point for error reporting
2754/// \param EntryLEK The warning if a mutex is missing from \p EntrySet.
2755/// \param ExitLEK The warning if a mutex is missing from \p ExitSet.
2756/// \param TrylockRebranchCaps Capabilities acquired by a try-lock whose result
2757/// the joining block's terminator branches on; differences in these are not
2758/// diagnosed because the paths re-diverge at the terminator (but they are
2759/// still removed from the intersection, and conditionally re-added on the
2760/// outgoing edges by getEdgeLockset()).
2761void ThreadSafetyAnalyzer::intersectAndWarn(
2762 FactSet &EntrySet, const FactSet &ExitSet, SourceLocation JoinLoc,
2763 LockErrorKind EntryLEK, LockErrorKind ExitLEK,
2764 const CapExprSet *TrylockRebranchCaps) {
2765 FactSet EntrySetOrig = EntrySet;
2766
2767 auto IsTrylockRebranched = [TrylockRebranchCaps](const FactEntry &FE) {
2768 return TrylockRebranchCaps &&
2769 llvm::any_of(Range: *TrylockRebranchCaps, P: [&FE](const CapabilityExpr &CE) {
2770 return !CE.shouldIgnore() && FE.matches(other: CE);
2771 });
2772 };
2773
2774 // Find locks in ExitSet that conflict or are not in EntrySet, and warn.
2775 for (const auto &Fact : ExitSet) {
2776 const FactEntry &ExitFact = FactMan[Fact];
2777
2778 FactSet::iterator EntryIt = EntrySet.findLockIter(FM&: FactMan, CapE: ExitFact);
2779 if (EntryIt != EntrySet.end()) {
2780 if (join(A: FactMan[*EntryIt], B: ExitFact, JoinLoc, EntryLEK))
2781 *EntryIt = Fact;
2782 } else if ((!ExitFact.managed() || EntryLEK == LEK_LockedAtEndOfFunction) &&
2783 !IsTrylockRebranched(ExitFact)) {
2784 ExitFact.handleRemovalFromIntersection(FSet: ExitSet, FactMan, JoinLoc,
2785 LEK: EntryLEK, Handler);
2786 }
2787 }
2788
2789 // Find locks in EntrySet that are not in ExitSet, and remove them.
2790 for (const auto &Fact : EntrySetOrig) {
2791 const FactEntry *EntryFact = &FactMan[Fact];
2792 const FactEntry *ExitFact = ExitSet.findLock(FM&: FactMan, CapE: *EntryFact);
2793
2794 if (!ExitFact) {
2795 if ((!EntryFact->managed() || ExitLEK == LEK_LockedSomeLoopIterations ||
2796 ExitLEK == LEK_NotLockedAtEndOfFunction) &&
2797 !IsTrylockRebranched(*EntryFact))
2798 EntryFact->handleRemovalFromIntersection(FSet: EntrySetOrig, FactMan, JoinLoc,
2799 LEK: ExitLEK, Handler);
2800 if (ExitLEK == LEK_LockedSomePredecessors)
2801 EntrySet.removeLock(FM&: FactMan, CapE: *EntryFact);
2802 }
2803 }
2804}
2805
2806// Return true if block B never continues to its successors.
2807static bool neverReturns(const CFGBlock *B) {
2808 if (B->hasNoReturnElement())
2809 return true;
2810 if (B->empty())
2811 return false;
2812
2813 CFGElement Last = B->back();
2814 if (std::optional<CFGStmt> S = Last.getAs<CFGStmt>()) {
2815 if (isa<CXXThrowExpr>(Val: S->getStmt()))
2816 return true;
2817 }
2818
2819 // If B constructed a temporary whose destructor is noreturn, control entering
2820 // the decision block will always branch to the non-returning destructor.
2821 if (B->succ_size() == 1) {
2822 if (const CFGBlock *Succ = *B->succ_begin()) {
2823 if (Succ->getTerminator().isTemporaryDtorsBranch() &&
2824 Succ->succ_size() == 2) {
2825 // The decision block's terminator is the CXXBindTemporaryExpr; if B
2826 // bound this temporary, entering Succ from B takes the true (dtor)
2827 // edge; otherwise it takes the false (alternative dtor / continuation)
2828 // edge.
2829 const Stmt *Term = Succ->getTerminatorStmt();
2830 bool Bound = llvm::any_of(Range: *B, P: [Term](const CFGElement &CE) {
2831 auto CS = CE.getAs<CFGStmt>();
2832 return CS && CS->getStmt() == Term;
2833 });
2834 if (const auto *Next =
2835 (Bound ? *Succ->succ_begin() : *(Succ->succ_begin() + 1))
2836 .getReachableBlock())
2837 return neverReturns(B: Next);
2838 }
2839 }
2840 }
2841
2842 return false;
2843}
2844
2845/// Check a function's CFG for thread-safety violations.
2846///
2847/// We traverse the blocks in the CFG, compute the set of mutexes that are held
2848/// at the end of each block, and issue warnings for thread safety violations.
2849/// Each block in the CFG is traversed exactly once.
2850void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) {
2851 // TODO: this whole function needs be rewritten as a visitor for CFGWalker.
2852 // For now, we just use the walker to set things up.
2853 threadSafety::CFGWalker walker;
2854 if (!walker.init(AC))
2855 return;
2856
2857 // AC.dumpCFG(true);
2858 // threadSafety::printSCFG(walker);
2859
2860 CFG *CFGraph = walker.getGraph();
2861 const NamedDecl *D = walker.getDecl();
2862 CurrentFunction = dyn_cast<FunctionDecl>(Val: D);
2863
2864 if (D->hasAttr<NoThreadSafetyAnalysisAttr>())
2865 return;
2866
2867 // FIXME: Do something a bit more intelligent inside constructor and
2868 // destructor code. Constructors and destructors must assume unique access
2869 // to 'this', so checks on member variable access is disabled, but we should
2870 // still enable checks on other objects.
2871 if (isa<CXXConstructorDecl>(Val: D))
2872 return; // Don't check inside constructors.
2873 if (isa<CXXDestructorDecl>(Val: D))
2874 return; // Don't check inside destructors.
2875
2876 Handler.enterFunction(FD: CurrentFunction);
2877
2878 BlockInfo.resize(new_size: CFGraph->getNumBlockIDs(),
2879 x: CFGBlockInfo::getEmptyBlockInfo(M&: LocalVarMap));
2880
2881 // We need to explore the CFG via a "topological" ordering.
2882 // That way, we will be guaranteed to have information about required
2883 // predecessor locksets when exploring a new block.
2884 const PostOrderCFGView *SortedGraph = walker.getSortedGraph();
2885 PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph);
2886
2887 CFGBlockInfo &Initial = BlockInfo[CFGraph->getEntry().getBlockID()];
2888 CFGBlockInfo &Final = BlockInfo[CFGraph->getExit().getBlockID()];
2889
2890 // Mark entry block as reachable
2891 Initial.Reachable = true;
2892
2893 // Compute SSA names for local variables
2894 LocalVarMap.traverseCFG(CFGraph, SortedGraph, BlockInfo);
2895
2896 // Fill in source locations for all CFGBlocks.
2897 findBlockLocations(CFGraph, SortedGraph, BlockInfo);
2898
2899 CapExprSet ExclusiveLocksAcquired;
2900 CapExprSet SharedLocksAcquired;
2901 CapExprSet LocksReleased;
2902
2903 // Add locks from exclusive_locks_required and shared_locks_required
2904 // to initial lockset. Also turn off checking for lock and unlock functions.
2905 // FIXME: is there a more intelligent way to check lock/unlock functions?
2906 if (!SortedGraph->empty()) {
2907 assert(*SortedGraph->begin() == &CFGraph->getEntry());
2908 FactSet &InitialLockset = Initial.EntrySet;
2909
2910 CapExprSet ExclusiveLocksToAdd;
2911 CapExprSet SharedLocksToAdd;
2912
2913 SourceLocation Loc = D->getLocation();
2914 for (const auto *Attr : D->attrs()) {
2915 Loc = Attr->getLocation();
2916 if (const auto *A = dyn_cast<RequiresCapabilityAttr>(Val: Attr)) {
2917 getMutexIDs(Mtxs&: A->isShared() ? SharedLocksToAdd : ExclusiveLocksToAdd, Attr: A,
2918 Exp: nullptr, D);
2919 } else if (const auto *A = dyn_cast<ReleaseCapabilityAttr>(Val: Attr)) {
2920 // UNLOCK_FUNCTION() is used to hide the underlying lock implementation.
2921 // We must ignore such methods.
2922 if (A->args_size() == 0)
2923 return;
2924 getMutexIDs(Mtxs&: A->isShared() ? SharedLocksToAdd : ExclusiveLocksToAdd, Attr: A,
2925 Exp: nullptr, D);
2926 getMutexIDs(Mtxs&: LocksReleased, Attr: A, Exp: nullptr, D);
2927 } else if (const auto *A = dyn_cast<AcquireCapabilityAttr>(Val: Attr)) {
2928 if (A->args_size() == 0)
2929 return;
2930 getMutexIDs(Mtxs&: A->isShared() ? SharedLocksAcquired
2931 : ExclusiveLocksAcquired,
2932 Attr: A, Exp: nullptr, D);
2933 } else if (isa<TryAcquireCapabilityAttr>(Val: Attr)) {
2934 // Don't try to check trylock functions for now.
2935 return;
2936 }
2937 }
2938 ArrayRef<ParmVarDecl *> Params;
2939 if (CurrentFunction)
2940 Params = CurrentFunction->getCanonicalDecl()->parameters();
2941 else if (auto CurrentMethod = dyn_cast<ObjCMethodDecl>(Val: D))
2942 Params = CurrentMethod->getCanonicalDecl()->parameters();
2943 else
2944 llvm_unreachable("Unknown function kind");
2945 for (const ParmVarDecl *Param : Params) {
2946 if (isCallbackParam(Param))
2947 continue;
2948 CapExprSet UnderlyingLocks;
2949 for (const auto *Attr : Param->attrs()) {
2950 Loc = Attr->getLocation();
2951 if (const auto *A = dyn_cast<ReleaseCapabilityAttr>(Val: Attr)) {
2952 getMutexIDs(Mtxs&: A->isShared() ? SharedLocksToAdd : ExclusiveLocksToAdd, Attr: A,
2953 Exp: nullptr, D: Param);
2954 getMutexIDs(Mtxs&: LocksReleased, Attr: A, Exp: nullptr, D: Param);
2955 getMutexIDs(Mtxs&: UnderlyingLocks, Attr: A, Exp: nullptr, D: Param);
2956 } else if (const auto *A = dyn_cast<RequiresCapabilityAttr>(Val: Attr)) {
2957 getMutexIDs(Mtxs&: A->isShared() ? SharedLocksToAdd : ExclusiveLocksToAdd, Attr: A,
2958 Exp: nullptr, D: Param);
2959 getMutexIDs(Mtxs&: UnderlyingLocks, Attr: A, Exp: nullptr, D: Param);
2960 } else if (const auto *A = dyn_cast<AcquireCapabilityAttr>(Val: Attr)) {
2961 getMutexIDs(Mtxs&: A->isShared() ? SharedLocksAcquired
2962 : ExclusiveLocksAcquired,
2963 Attr: A, Exp: nullptr, D: Param);
2964 getMutexIDs(Mtxs&: UnderlyingLocks, Attr: A, Exp: nullptr, D: Param);
2965 } else if (const auto *A = dyn_cast<LocksExcludedAttr>(Val: Attr)) {
2966 getMutexIDs(Mtxs&: UnderlyingLocks, Attr: A, Exp: nullptr, D: Param);
2967 }
2968 }
2969 if (UnderlyingLocks.empty())
2970 continue;
2971 CapabilityExpr Cp(SxBuilder.translateVariable(VD: Param, Ctx: nullptr),
2972 StringRef(),
2973 /*Neg=*/false, /*Reentrant=*/false);
2974 auto *ScopedEntry = FactMan.createFact<ScopedLockableFactEntry>(
2975 Args&: Cp, Args: Param->getLocation(), Args: FactEntry::Declared,
2976 Args: UnderlyingLocks.size());
2977 for (const CapabilityExpr &M : UnderlyingLocks)
2978 ScopedEntry->addLock(M);
2979 addLock(FSet&: InitialLockset, Entry: ScopedEntry, ReqAttr: true);
2980 }
2981
2982 // FIXME -- Loc can be wrong here.
2983 for (const auto &Mu : ExclusiveLocksToAdd) {
2984 const auto *Entry = FactMan.createFact<LockableFactEntry>(
2985 Args: Mu, Args: LK_Exclusive, Args&: Loc, Args: FactEntry::Declared);
2986 addLock(FSet&: InitialLockset, Entry, ReqAttr: true);
2987 }
2988 for (const auto &Mu : SharedLocksToAdd) {
2989 const auto *Entry = FactMan.createFact<LockableFactEntry>(
2990 Args: Mu, Args: LK_Shared, Args&: Loc, Args: FactEntry::Declared);
2991 addLock(FSet&: InitialLockset, Entry, ReqAttr: true);
2992 }
2993 }
2994
2995 // Compute the expected exit set.
2996 // By default, we expect all locks held on entry to be held on exit.
2997 FactSet ExpectedFunctionExitSet = Initial.EntrySet;
2998
2999 // Adjust the expected exit set by adding or removing locks, as declared
3000 // by *-LOCK_FUNCTION and UNLOCK_FUNCTION. The intersect below will then
3001 // issue the appropriate warning.
3002 // FIXME: the location here is not quite right.
3003 for (const auto &Lock : ExclusiveLocksAcquired)
3004 ExpectedFunctionExitSet.addLock(
3005 FM&: FactMan, Entry: FactMan.createFact<LockableFactEntry>(Args: Lock, Args: LK_Exclusive,
3006 Args: D->getLocation()));
3007 for (const auto &Lock : SharedLocksAcquired)
3008 ExpectedFunctionExitSet.addLock(
3009 FM&: FactMan, Entry: FactMan.createFact<LockableFactEntry>(Args: Lock, Args: LK_Shared,
3010 Args: D->getLocation()));
3011 for (const auto &Lock : LocksReleased)
3012 ExpectedFunctionExitSet.removeLock(FM&: FactMan, CapE: Lock);
3013
3014 for (const auto *CurrBlock : *SortedGraph) {
3015 unsigned CurrBlockID = CurrBlock->getBlockID();
3016 CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID];
3017
3018 // Use the default initial lockset in case there are no predecessors.
3019 VisitedBlocks.insert(Block: CurrBlock);
3020
3021 // Iterate through the predecessor blocks and warn if the lockset for all
3022 // predecessors is not the same. We take the entry lockset of the current
3023 // block to be the intersection of all previous locksets.
3024 // FIXME: By keeping the intersection, we may output more errors in future
3025 // for a lock which is not in the intersection, but was in the union. We
3026 // may want to also keep the union in future. As an example, let's say
3027 // the intersection contains Mutex L, and the union contains L and M.
3028 // Later we unlock M. At this point, we would output an error because we
3029 // never locked M; although the real error is probably that we forgot to
3030 // lock M on all code paths. Conversely, let's say that later we lock M.
3031 // In this case, we should compare against the intersection instead of the
3032 // union because the real error is probably that we forgot to unlock M on
3033 // all code paths.
3034 bool LocksetInitialized = false;
3035 // Capabilities acquired by a try-lock whose result this block's
3036 // terminator branches on. Computed lazily on the first join.
3037 CapExprSet TerminatorTrylockCaps;
3038 bool TerminatorTrylockCapsComputed = false;
3039 for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(),
3040 PE = CurrBlock->pred_end(); PI != PE; ++PI) {
3041 // if *PI -> CurrBlock is a back edge
3042 if (*PI == nullptr || !VisitedBlocks.alreadySet(Block: *PI))
3043 continue;
3044
3045 unsigned PrevBlockID = (*PI)->getBlockID();
3046 CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID];
3047
3048 // Ignore edges from blocks that can't return.
3049 if (neverReturns(B: *PI) || !PrevBlockInfo->Reachable)
3050 continue;
3051
3052 // Okay, we can reach this block from the entry.
3053 CurrBlockInfo->Reachable = true;
3054
3055 FactSet PrevLockset;
3056 getEdgeLockset(Result&: PrevLockset, ExitSet: PrevBlockInfo->ExitSet, PredBlock: *PI, CurrBlock);
3057
3058 if (!LocksetInitialized) {
3059 CurrBlockInfo->EntrySet = PrevLockset;
3060 LocksetInitialized = true;
3061 } else {
3062 // Surprisingly 'continue' doesn't always produce back edges, because
3063 // the CFG has empty "transition" blocks where they meet with the end
3064 // of the regular loop body. We still want to diagnose them as loop.
3065 if (isa_and_nonnull<ContinueStmt>(Val: (*PI)->getTerminatorStmt())) {
3066 // Loop join: warn on locks held for only some iterations.
3067 intersectAndWarn(EntrySet&: CurrBlockInfo->EntrySet, ExitSet: PrevLockset,
3068 JoinLoc: CurrBlockInfo->EntryLoc,
3069 EntryLEK: LEK_LockedSomeLoopIterations,
3070 ExitLEK: LEK_LockedSomeLoopIterations, TrylockRebranchCaps: nullptr);
3071 } else {
3072 // Branch join: a lockset difference is harmless if the terminator
3073 // re-branches on the try-lock result.
3074 if (!TerminatorTrylockCapsComputed) {
3075 // Compute once; the result depends only on CurrBlock, not on *PI.
3076 getTerminatorTrylockCaps(Block: CurrBlock, Caps&: TerminatorTrylockCaps);
3077 TerminatorTrylockCapsComputed = true;
3078 }
3079 intersectAndWarn(EntrySet&: CurrBlockInfo->EntrySet, ExitSet: PrevLockset,
3080 JoinLoc: CurrBlockInfo->EntryLoc, EntryLEK: LEK_LockedSomePredecessors,
3081 ExitLEK: LEK_LockedSomePredecessors, TrylockRebranchCaps: &TerminatorTrylockCaps);
3082 }
3083 }
3084 }
3085
3086 // Skip rest of block if it's not reachable.
3087 if (!CurrBlockInfo->Reachable)
3088 continue;
3089
3090 BuildLockset LocksetBuilder(this, *CurrBlockInfo, ExpectedFunctionExitSet);
3091
3092 // Visit all the statements in the basic block.
3093 for (const auto &BI : *CurrBlock) {
3094 switch (BI.getKind()) {
3095 case CFGElement::Statement: {
3096 CFGStmt CS = BI.castAs<CFGStmt>();
3097 LocksetBuilder.Visit(S: CS.getStmt());
3098 break;
3099 }
3100 // Ignore BaseDtor and MemberDtor for now.
3101 case CFGElement::AutomaticObjectDtor: {
3102 CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>();
3103 const auto *DD = AD.getDestructorDecl(astContext&: AC.getASTContext());
3104 // Function parameters as they are constructed in caller's context and
3105 // the CFG does not contain the ctors. Ignore them as their
3106 // capabilities cannot be analysed because of this missing
3107 // information.
3108 if (isa_and_nonnull<ParmVarDecl>(Val: AD.getVarDecl()))
3109 break;
3110 if (!DD || !DD->hasAttrs())
3111 break;
3112
3113 LocksetBuilder.handleCall(
3114 Exp: nullptr, D: DD,
3115 Self: SxBuilder.translateVariable(VD: AD.getVarDecl(), Ctx: nullptr),
3116 Loc: AD.getTriggerStmt()->getEndLoc());
3117 break;
3118 }
3119
3120 case CFGElement::CleanupFunction: {
3121 const CFGCleanupFunction &CF = BI.castAs<CFGCleanupFunction>();
3122 LocksetBuilder.handleCall(
3123 /*Exp=*/nullptr, D: CF.getFunctionDecl(),
3124 Self: SxBuilder.translateVariable(VD: CF.getVarDecl(), Ctx: nullptr),
3125 Loc: CF.getVarDecl()->getLocation());
3126 break;
3127 }
3128
3129 case CFGElement::TemporaryDtor: {
3130 auto TD = BI.castAs<CFGTemporaryDtor>();
3131
3132 // Clean up constructed object even if there are no attributes to
3133 // keep the number of objects in limbo as small as possible.
3134 if (auto Object = ConstructedObjects.find(
3135 Val: TD.getBindTemporaryExpr()->getSubExpr());
3136 Object != ConstructedObjects.end()) {
3137 const auto *DD = TD.getDestructorDecl(astContext&: AC.getASTContext());
3138 if (DD->hasAttrs())
3139 // TODO: the location here isn't quite correct.
3140 LocksetBuilder.handleCall(Exp: nullptr, D: DD, Self: Object->second,
3141 Loc: TD.getBindTemporaryExpr()->getEndLoc());
3142 ConstructedObjects.erase(I: Object);
3143 }
3144 break;
3145 }
3146 default:
3147 break;
3148 }
3149 }
3150 CurrBlockInfo->ExitSet = LocksetBuilder.FSet;
3151
3152 // For every back edge from CurrBlock (the end of the loop) to another block
3153 // (FirstLoopBlock) we need to check that the Lockset of Block is equal to
3154 // the one held at the beginning of FirstLoopBlock. We can look up the
3155 // Lockset held at the beginning of FirstLoopBlock in the EntryLockSets map.
3156 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
3157 SE = CurrBlock->succ_end(); SI != SE; ++SI) {
3158 // if CurrBlock -> *SI is *not* a back edge
3159 if (*SI == nullptr || !VisitedBlocks.alreadySet(Block: *SI))
3160 continue;
3161
3162 CFGBlock *FirstLoopBlock = *SI;
3163 CFGBlockInfo *PreLoop = &BlockInfo[FirstLoopBlock->getBlockID()];
3164 CFGBlockInfo *LoopEnd = &BlockInfo[CurrBlockID];
3165 intersectAndWarn(EntrySet&: PreLoop->EntrySet, ExitSet: LoopEnd->ExitSet, JoinLoc: PreLoop->EntryLoc,
3166 LEK: LEK_LockedSomeLoopIterations);
3167 }
3168 }
3169
3170 // Skip the final check if the exit block is unreachable.
3171 if (!Final.Reachable)
3172 return;
3173
3174 // FIXME: Should we call this function for all blocks which exit the function?
3175 intersectAndWarn(EntrySet&: ExpectedFunctionExitSet, ExitSet: Final.ExitSet, JoinLoc: Final.ExitLoc,
3176 EntryLEK: LEK_LockedAtEndOfFunction, ExitLEK: LEK_NotLockedAtEndOfFunction);
3177
3178 Handler.leaveFunction(FD: CurrentFunction);
3179}
3180
3181/// Check a function's CFG for thread-safety violations.
3182///
3183/// We traverse the blocks in the CFG, compute the set of mutexes that are held
3184/// at the end of each block, and issue warnings for thread safety violations.
3185/// Each block in the CFG is traversed exactly once.
3186void threadSafety::runThreadSafetyAnalysis(AnalysisDeclContext &AC,
3187 ThreadSafetyHandler &Handler,
3188 BeforeSet **BSet) {
3189 if (!*BSet)
3190 *BSet = new BeforeSet;
3191 ThreadSafetyAnalyzer Analyzer(Handler, *BSet);
3192 Analyzer.runAnalysis(AC);
3193}
3194
3195void threadSafety::threadSafetyCleanup(BeforeSet *Cache) { delete Cache; }
3196
3197/// Helper function that returns a LockKind required for the given level
3198/// of access.
3199LockKind threadSafety::getLockKindFromAccessKind(AccessKind AK) {
3200 switch (AK) {
3201 case AK_Read :
3202 return LK_Shared;
3203 case AK_Written :
3204 return LK_Exclusive;
3205 }
3206 llvm_unreachable("Unknown AccessKind");
3207}
3208