File: | tools/clang/include/clang/Analysis/Analyses/ThreadSafetyCommon.h |
Warning: | line 366, column 5 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
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/ThreadSafetyTraverse.h" | |||
32 | #include "clang/Analysis/Analyses/ThreadSafetyUtil.h" | |||
33 | #include "clang/Analysis/AnalysisDeclContext.h" | |||
34 | #include "clang/Analysis/CFG.h" | |||
35 | #include "clang/Basic/Builtins.h" | |||
36 | #include "clang/Basic/LLVM.h" | |||
37 | #include "clang/Basic/OperatorKinds.h" | |||
38 | #include "clang/Basic/SourceLocation.h" | |||
39 | #include "clang/Basic/Specifiers.h" | |||
40 | #include "llvm/ADT/ArrayRef.h" | |||
41 | #include "llvm/ADT/DenseMap.h" | |||
42 | #include "llvm/ADT/ImmutableMap.h" | |||
43 | #include "llvm/ADT/Optional.h" | |||
44 | #include "llvm/ADT/PointerIntPair.h" | |||
45 | #include "llvm/ADT/STLExtras.h" | |||
46 | #include "llvm/ADT/SmallVector.h" | |||
47 | #include "llvm/ADT/StringRef.h" | |||
48 | #include "llvm/Support/Allocator.h" | |||
49 | #include "llvm/Support/Casting.h" | |||
50 | #include "llvm/Support/ErrorHandling.h" | |||
51 | #include "llvm/Support/raw_ostream.h" | |||
52 | #include <algorithm> | |||
53 | #include <cassert> | |||
54 | #include <functional> | |||
55 | #include <iterator> | |||
56 | #include <memory> | |||
57 | #include <string> | |||
58 | #include <type_traits> | |||
59 | #include <utility> | |||
60 | #include <vector> | |||
61 | ||||
62 | using namespace clang; | |||
63 | using namespace threadSafety; | |||
64 | ||||
65 | // Key method definition | |||
66 | ThreadSafetyHandler::~ThreadSafetyHandler() = default; | |||
67 | ||||
68 | /// Issue a warning about an invalid lock expression | |||
69 | static void warnInvalidLock(ThreadSafetyHandler &Handler, | |||
70 | const Expr *MutexExp, const NamedDecl *D, | |||
71 | const Expr *DeclExp, StringRef Kind) { | |||
72 | SourceLocation Loc; | |||
73 | if (DeclExp) | |||
74 | Loc = DeclExp->getExprLoc(); | |||
75 | ||||
76 | // FIXME: add a note about the attribute location in MutexExp or D | |||
77 | if (Loc.isValid()) | |||
78 | Handler.handleInvalidLockExp(Kind, Loc); | |||
79 | } | |||
80 | ||||
81 | namespace { | |||
82 | ||||
83 | /// A set of CapabilityExpr objects, which are compiled from thread safety | |||
84 | /// attributes on a function. | |||
85 | class CapExprSet : public SmallVector<CapabilityExpr, 4> { | |||
86 | public: | |||
87 | /// Push M onto list, but discard duplicates. | |||
88 | void push_back_nodup(const CapabilityExpr &CapE) { | |||
89 | iterator It = std::find_if(begin(), end(), | |||
90 | [=](const CapabilityExpr &CapE2) { | |||
91 | return CapE.equals(CapE2); | |||
92 | }); | |||
93 | if (It == end()) | |||
94 | push_back(CapE); | |||
95 | } | |||
96 | }; | |||
97 | ||||
98 | class FactManager; | |||
99 | class FactSet; | |||
100 | ||||
101 | /// This is a helper class that stores a fact that is known at a | |||
102 | /// particular point in program execution. Currently, a fact is a capability, | |||
103 | /// along with additional information, such as where it was acquired, whether | |||
104 | /// it is exclusive or shared, etc. | |||
105 | /// | |||
106 | /// FIXME: this analysis does not currently support re-entrant locking. | |||
107 | class FactEntry : public CapabilityExpr { | |||
108 | private: | |||
109 | /// Exclusive or shared. | |||
110 | LockKind LKind; | |||
111 | ||||
112 | /// Where it was acquired. | |||
113 | SourceLocation AcquireLoc; | |||
114 | ||||
115 | /// True if the lock was asserted. | |||
116 | bool Asserted; | |||
117 | ||||
118 | /// True if the lock was declared. | |||
119 | bool Declared; | |||
120 | ||||
121 | public: | |||
122 | FactEntry(const CapabilityExpr &CE, LockKind LK, SourceLocation Loc, | |||
123 | bool Asrt, bool Declrd = false) | |||
124 | : CapabilityExpr(CE), LKind(LK), AcquireLoc(Loc), Asserted(Asrt), | |||
125 | Declared(Declrd) {} | |||
126 | virtual ~FactEntry() = default; | |||
127 | ||||
128 | LockKind kind() const { return LKind; } | |||
129 | SourceLocation loc() const { return AcquireLoc; } | |||
130 | bool asserted() const { return Asserted; } | |||
131 | bool declared() const { return Declared; } | |||
132 | ||||
133 | void setDeclared(bool D) { Declared = D; } | |||
134 | ||||
135 | virtual void | |||
136 | handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan, | |||
137 | SourceLocation JoinLoc, LockErrorKind LEK, | |||
138 | ThreadSafetyHandler &Handler) const = 0; | |||
139 | virtual void handleLock(FactSet &FSet, FactManager &FactMan, | |||
140 | const FactEntry &entry, ThreadSafetyHandler &Handler, | |||
141 | StringRef DiagKind) const = 0; | |||
142 | virtual void handleUnlock(FactSet &FSet, FactManager &FactMan, | |||
143 | const CapabilityExpr &Cp, SourceLocation UnlockLoc, | |||
144 | bool FullyRemove, ThreadSafetyHandler &Handler, | |||
145 | StringRef DiagKind) const = 0; | |||
146 | ||||
147 | // Return true if LKind >= LK, where exclusive > shared | |||
148 | bool isAtLeast(LockKind LK) const { | |||
149 | return (LKind == LK_Exclusive) || (LK == LK_Shared); | |||
150 | } | |||
151 | }; | |||
152 | ||||
153 | using FactID = unsigned short; | |||
154 | ||||
155 | /// FactManager manages the memory for all facts that are created during | |||
156 | /// the analysis of a single routine. | |||
157 | class FactManager { | |||
158 | private: | |||
159 | std::vector<std::unique_ptr<const FactEntry>> Facts; | |||
160 | ||||
161 | public: | |||
162 | FactID newFact(std::unique_ptr<FactEntry> Entry) { | |||
163 | Facts.push_back(std::move(Entry)); | |||
164 | return static_cast<unsigned short>(Facts.size() - 1); | |||
165 | } | |||
166 | ||||
167 | const FactEntry &operator[](FactID F) const { return *Facts[F]; } | |||
168 | }; | |||
169 | ||||
170 | /// A FactSet is the set of facts that are known to be true at a | |||
171 | /// particular program point. FactSets must be small, because they are | |||
172 | /// frequently copied, and are thus implemented as a set of indices into a | |||
173 | /// table maintained by a FactManager. A typical FactSet only holds 1 or 2 | |||
174 | /// locks, so we can get away with doing a linear search for lookup. Note | |||
175 | /// that a hashtable or map is inappropriate in this case, because lookups | |||
176 | /// may involve partial pattern matches, rather than exact matches. | |||
177 | class FactSet { | |||
178 | private: | |||
179 | using FactVec = SmallVector<FactID, 4>; | |||
180 | ||||
181 | FactVec FactIDs; | |||
182 | ||||
183 | public: | |||
184 | using iterator = FactVec::iterator; | |||
185 | using const_iterator = FactVec::const_iterator; | |||
186 | ||||
187 | iterator begin() { return FactIDs.begin(); } | |||
188 | const_iterator begin() const { return FactIDs.begin(); } | |||
189 | ||||
190 | iterator end() { return FactIDs.end(); } | |||
191 | const_iterator end() const { return FactIDs.end(); } | |||
192 | ||||
193 | bool isEmpty() const { return FactIDs.size() == 0; } | |||
194 | ||||
195 | // Return true if the set contains only negative facts | |||
196 | bool isEmpty(FactManager &FactMan) const { | |||
197 | for (const auto FID : *this) { | |||
198 | if (!FactMan[FID].negative()) | |||
199 | return false; | |||
200 | } | |||
201 | return true; | |||
202 | } | |||
203 | ||||
204 | void addLockByID(FactID ID) { FactIDs.push_back(ID); } | |||
205 | ||||
206 | FactID addLock(FactManager &FM, std::unique_ptr<FactEntry> Entry) { | |||
207 | FactID F = FM.newFact(std::move(Entry)); | |||
208 | FactIDs.push_back(F); | |||
209 | return F; | |||
210 | } | |||
211 | ||||
212 | bool removeLock(FactManager& FM, const CapabilityExpr &CapE) { | |||
213 | unsigned n = FactIDs.size(); | |||
214 | if (n == 0) | |||
215 | return false; | |||
216 | ||||
217 | for (unsigned i = 0; i < n-1; ++i) { | |||
218 | if (FM[FactIDs[i]].matches(CapE)) { | |||
219 | FactIDs[i] = FactIDs[n-1]; | |||
220 | FactIDs.pop_back(); | |||
221 | return true; | |||
222 | } | |||
223 | } | |||
224 | if (FM[FactIDs[n-1]].matches(CapE)) { | |||
225 | FactIDs.pop_back(); | |||
226 | return true; | |||
227 | } | |||
228 | return false; | |||
229 | } | |||
230 | ||||
231 | iterator findLockIter(FactManager &FM, const CapabilityExpr &CapE) { | |||
232 | return std::find_if(begin(), end(), [&](FactID ID) { | |||
233 | return FM[ID].matches(CapE); | |||
234 | }); | |||
235 | } | |||
236 | ||||
237 | const FactEntry *findLock(FactManager &FM, const CapabilityExpr &CapE) const { | |||
238 | auto I = std::find_if(begin(), end(), [&](FactID ID) { | |||
239 | return FM[ID].matches(CapE); | |||
240 | }); | |||
241 | return I != end() ? &FM[*I] : nullptr; | |||
242 | } | |||
243 | ||||
244 | const FactEntry *findLockUniv(FactManager &FM, | |||
245 | const CapabilityExpr &CapE) const { | |||
246 | auto I = std::find_if(begin(), end(), [&](FactID ID) -> bool { | |||
247 | return FM[ID].matchesUniv(CapE); | |||
248 | }); | |||
249 | return I != end() ? &FM[*I] : nullptr; | |||
250 | } | |||
251 | ||||
252 | const FactEntry *findPartialMatch(FactManager &FM, | |||
253 | const CapabilityExpr &CapE) const { | |||
254 | auto I = std::find_if(begin(), end(), [&](FactID ID) -> bool { | |||
255 | return FM[ID].partiallyMatches(CapE); | |||
256 | }); | |||
257 | return I != end() ? &FM[*I] : nullptr; | |||
258 | } | |||
259 | ||||
260 | bool containsMutexDecl(FactManager &FM, const ValueDecl* Vd) const { | |||
261 | auto I = std::find_if(begin(), end(), [&](FactID ID) -> bool { | |||
262 | return FM[ID].valueDecl() == Vd; | |||
263 | }); | |||
264 | return I != end(); | |||
265 | } | |||
266 | }; | |||
267 | ||||
268 | class ThreadSafetyAnalyzer; | |||
269 | ||||
270 | } // namespace | |||
271 | ||||
272 | namespace clang { | |||
273 | namespace threadSafety { | |||
274 | ||||
275 | class BeforeSet { | |||
276 | private: | |||
277 | using BeforeVect = SmallVector<const ValueDecl *, 4>; | |||
278 | ||||
279 | struct BeforeInfo { | |||
280 | BeforeVect Vect; | |||
281 | int Visited = 0; | |||
282 | ||||
283 | BeforeInfo() = default; | |||
284 | BeforeInfo(BeforeInfo &&) = default; | |||
285 | }; | |||
286 | ||||
287 | using BeforeMap = | |||
288 | llvm::DenseMap<const ValueDecl *, std::unique_ptr<BeforeInfo>>; | |||
289 | using CycleMap = llvm::DenseMap<const ValueDecl *, bool>; | |||
290 | ||||
291 | public: | |||
292 | BeforeSet() = default; | |||
293 | ||||
294 | BeforeInfo* insertAttrExprs(const ValueDecl* Vd, | |||
295 | ThreadSafetyAnalyzer& Analyzer); | |||
296 | ||||
297 | BeforeInfo *getBeforeInfoForDecl(const ValueDecl *Vd, | |||
298 | ThreadSafetyAnalyzer &Analyzer); | |||
299 | ||||
300 | void checkBeforeAfter(const ValueDecl* Vd, | |||
301 | const FactSet& FSet, | |||
302 | ThreadSafetyAnalyzer& Analyzer, | |||
303 | SourceLocation Loc, StringRef CapKind); | |||
304 | ||||
305 | private: | |||
306 | BeforeMap BMap; | |||
307 | CycleMap CycMap; | |||
308 | }; | |||
309 | ||||
310 | } // namespace threadSafety | |||
311 | } // namespace clang | |||
312 | ||||
313 | namespace { | |||
314 | ||||
315 | class LocalVariableMap; | |||
316 | ||||
317 | using LocalVarContext = llvm::ImmutableMap<const NamedDecl *, unsigned>; | |||
318 | ||||
319 | /// A side (entry or exit) of a CFG node. | |||
320 | enum CFGBlockSide { CBS_Entry, CBS_Exit }; | |||
321 | ||||
322 | /// CFGBlockInfo is a struct which contains all the information that is | |||
323 | /// maintained for each block in the CFG. See LocalVariableMap for more | |||
324 | /// information about the contexts. | |||
325 | struct CFGBlockInfo { | |||
326 | // Lockset held at entry to block | |||
327 | FactSet EntrySet; | |||
328 | ||||
329 | // Lockset held at exit from block | |||
330 | FactSet ExitSet; | |||
331 | ||||
332 | // Context held at entry to block | |||
333 | LocalVarContext EntryContext; | |||
334 | ||||
335 | // Context held at exit from block | |||
336 | LocalVarContext ExitContext; | |||
337 | ||||
338 | // Location of first statement in block | |||
339 | SourceLocation EntryLoc; | |||
340 | ||||
341 | // Location of last statement in block. | |||
342 | SourceLocation ExitLoc; | |||
343 | ||||
344 | // Used to replay contexts later | |||
345 | unsigned EntryIndex; | |||
346 | ||||
347 | // Is this block reachable? | |||
348 | bool Reachable = false; | |||
349 | ||||
350 | const FactSet &getSet(CFGBlockSide Side) const { | |||
351 | return Side == CBS_Entry ? EntrySet : ExitSet; | |||
352 | } | |||
353 | ||||
354 | SourceLocation getLocation(CFGBlockSide Side) const { | |||
355 | return Side == CBS_Entry ? EntryLoc : ExitLoc; | |||
356 | } | |||
357 | ||||
358 | private: | |||
359 | CFGBlockInfo(LocalVarContext EmptyCtx) | |||
360 | : EntryContext(EmptyCtx), ExitContext(EmptyCtx) {} | |||
361 | ||||
362 | public: | |||
363 | static CFGBlockInfo getEmptyBlockInfo(LocalVariableMap &M); | |||
364 | }; | |||
365 | ||||
366 | // A LocalVariableMap maintains a map from local variables to their currently | |||
367 | // valid definitions. It provides SSA-like functionality when traversing the | |||
368 | // CFG. Like SSA, each definition or assignment to a variable is assigned a | |||
369 | // unique name (an integer), which acts as the SSA name for that definition. | |||
370 | // The total set of names is shared among all CFG basic blocks. | |||
371 | // Unlike SSA, we do not rewrite expressions to replace local variables declrefs | |||
372 | // with their SSA-names. Instead, we compute a Context for each point in the | |||
373 | // code, which maps local variables to the appropriate SSA-name. This map | |||
374 | // changes with each assignment. | |||
375 | // | |||
376 | // The map is computed in a single pass over the CFG. Subsequent analyses can | |||
377 | // then query the map to find the appropriate Context for a statement, and use | |||
378 | // that Context to look up the definitions of variables. | |||
379 | class LocalVariableMap { | |||
380 | public: | |||
381 | using Context = LocalVarContext; | |||
382 | ||||
383 | /// A VarDefinition consists of an expression, representing the value of the | |||
384 | /// variable, along with the context in which that expression should be | |||
385 | /// interpreted. A reference VarDefinition does not itself contain this | |||
386 | /// information, but instead contains a pointer to a previous VarDefinition. | |||
387 | struct VarDefinition { | |||
388 | public: | |||
389 | friend class LocalVariableMap; | |||
390 | ||||
391 | // The original declaration for this variable. | |||
392 | const NamedDecl *Dec; | |||
393 | ||||
394 | // The expression for this variable, OR | |||
395 | const Expr *Exp = nullptr; | |||
396 | ||||
397 | // Reference to another VarDefinition | |||
398 | unsigned Ref = 0; | |||
399 | ||||
400 | // The map with which Exp should be interpreted. | |||
401 | Context Ctx; | |||
402 | ||||
403 | bool isReference() { return !Exp; } | |||
404 | ||||
405 | private: | |||
406 | // Create ordinary variable definition | |||
407 | VarDefinition(const NamedDecl *D, const Expr *E, Context C) | |||
408 | : Dec(D), Exp(E), Ctx(C) {} | |||
409 | ||||
410 | // Create reference to previous definition | |||
411 | VarDefinition(const NamedDecl *D, unsigned R, Context C) | |||
412 | : Dec(D), Ref(R), Ctx(C) {} | |||
413 | }; | |||
414 | ||||
415 | private: | |||
416 | Context::Factory ContextFactory; | |||
417 | std::vector<VarDefinition> VarDefinitions; | |||
418 | std::vector<unsigned> CtxIndices; | |||
419 | std::vector<std::pair<const Stmt *, Context>> SavedContexts; | |||
420 | ||||
421 | public: | |||
422 | LocalVariableMap() { | |||
423 | // index 0 is a placeholder for undefined variables (aka phi-nodes). | |||
424 | VarDefinitions.push_back(VarDefinition(nullptr, 0u, getEmptyContext())); | |||
425 | } | |||
426 | ||||
427 | /// Look up a definition, within the given context. | |||
428 | const VarDefinition* lookup(const NamedDecl *D, Context Ctx) { | |||
429 | const unsigned *i = Ctx.lookup(D); | |||
430 | if (!i) | |||
431 | return nullptr; | |||
432 | assert(*i < VarDefinitions.size())((*i < VarDefinitions.size()) ? static_cast<void> (0 ) : __assert_fail ("*i < VarDefinitions.size()", "/build/llvm-toolchain-snapshot-9~svn362543/tools/clang/lib/Analysis/ThreadSafety.cpp" , 432, __PRETTY_FUNCTION__)); | |||
433 | return &VarDefinitions[*i]; | |||
434 | } | |||
435 | ||||
436 | /// Look up the definition for D within the given context. Returns | |||
437 | /// NULL if the expression is not statically known. If successful, also | |||
438 | /// modifies Ctx to hold the context of the return Expr. | |||
439 | const Expr* lookupExpr(const NamedDecl *D, Context &Ctx) { | |||
440 | const unsigned *P = Ctx.lookup(D); | |||
441 | if (!P) | |||
442 | return nullptr; | |||
443 | ||||
444 | unsigned i = *P; | |||
445 | while (i > 0) { | |||
446 | if (VarDefinitions[i].Exp) { | |||
447 | Ctx = VarDefinitions[i].Ctx; | |||
448 | return VarDefinitions[i].Exp; | |||
449 | } | |||
450 | i = VarDefinitions[i].Ref; | |||
451 | } | |||
452 | return nullptr; | |||
453 | } | |||
454 | ||||
455 | Context getEmptyContext() { return ContextFactory.getEmptyMap(); } | |||
456 | ||||
457 | /// Return the next context after processing S. This function is used by | |||
458 | /// clients of the class to get the appropriate context when traversing the | |||
459 | /// CFG. It must be called for every assignment or DeclStmt. | |||
460 | Context getNextContext(unsigned &CtxIndex, const Stmt *S, Context C) { | |||
461 | if (SavedContexts[CtxIndex+1].first == S) { | |||
462 | CtxIndex++; | |||
463 | Context Result = SavedContexts[CtxIndex].second; | |||
464 | return Result; | |||
465 | } | |||
466 | return C; | |||
467 | } | |||
468 | ||||
469 | void dumpVarDefinitionName(unsigned i) { | |||
470 | if (i == 0) { | |||
471 | llvm::errs() << "Undefined"; | |||
472 | return; | |||
473 | } | |||
474 | const NamedDecl *Dec = VarDefinitions[i].Dec; | |||
475 | if (!Dec) { | |||
476 | llvm::errs() << "<<NULL>>"; | |||
477 | return; | |||
478 | } | |||
479 | Dec->printName(llvm::errs()); | |||
480 | llvm::errs() << "." << i << " " << ((const void*) Dec); | |||
481 | } | |||
482 | ||||
483 | /// Dumps an ASCII representation of the variable map to llvm::errs() | |||
484 | void dump() { | |||
485 | for (unsigned i = 1, e = VarDefinitions.size(); i < e; ++i) { | |||
486 | const Expr *Exp = VarDefinitions[i].Exp; | |||
487 | unsigned Ref = VarDefinitions[i].Ref; | |||
488 | ||||
489 | dumpVarDefinitionName(i); | |||
490 | llvm::errs() << " = "; | |||
491 | if (Exp) Exp->dump(); | |||
492 | else { | |||
493 | dumpVarDefinitionName(Ref); | |||
494 | llvm::errs() << "\n"; | |||
495 | } | |||
496 | } | |||
497 | } | |||
498 | ||||
499 | /// Dumps an ASCII representation of a Context to llvm::errs() | |||
500 | void dumpContext(Context C) { | |||
501 | for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) { | |||
502 | const NamedDecl *D = I.getKey(); | |||
503 | D->printName(llvm::errs()); | |||
504 | const unsigned *i = C.lookup(D); | |||
505 | llvm::errs() << " -> "; | |||
506 | dumpVarDefinitionName(*i); | |||
507 | llvm::errs() << "\n"; | |||
508 | } | |||
509 | } | |||
510 | ||||
511 | /// Builds the variable map. | |||
512 | void traverseCFG(CFG *CFGraph, const PostOrderCFGView *SortedGraph, | |||
513 | std::vector<CFGBlockInfo> &BlockInfo); | |||
514 | ||||
515 | protected: | |||
516 | friend class VarMapBuilder; | |||
517 | ||||
518 | // Get the current context index | |||
519 | unsigned getContextIndex() { return SavedContexts.size()-1; } | |||
520 | ||||
521 | // Save the current context for later replay | |||
522 | void saveContext(const Stmt *S, Context C) { | |||
523 | SavedContexts.push_back(std::make_pair(S, C)); | |||
524 | } | |||
525 | ||||
526 | // Adds a new definition to the given context, and returns a new context. | |||
527 | // This method should be called when declaring a new variable. | |||
528 | Context addDefinition(const NamedDecl *D, const Expr *Exp, Context Ctx) { | |||
529 | assert(!Ctx.contains(D))((!Ctx.contains(D)) ? static_cast<void> (0) : __assert_fail ("!Ctx.contains(D)", "/build/llvm-toolchain-snapshot-9~svn362543/tools/clang/lib/Analysis/ThreadSafety.cpp" , 529, __PRETTY_FUNCTION__)); | |||
530 | unsigned newID = VarDefinitions.size(); | |||
531 | Context NewCtx = ContextFactory.add(Ctx, D, newID); | |||
532 | VarDefinitions.push_back(VarDefinition(D, Exp, Ctx)); | |||
533 | return NewCtx; | |||
534 | } | |||
535 | ||||
536 | // Add a new reference to an existing definition. | |||
537 | Context addReference(const NamedDecl *D, unsigned i, Context Ctx) { | |||
538 | unsigned newID = VarDefinitions.size(); | |||
539 | Context NewCtx = ContextFactory.add(Ctx, D, newID); | |||
540 | VarDefinitions.push_back(VarDefinition(D, i, Ctx)); | |||
541 | return NewCtx; | |||
542 | } | |||
543 | ||||
544 | // Updates a definition only if that definition is already in the map. | |||
545 | // This method should be called when assigning to an existing variable. | |||
546 | Context updateDefinition(const NamedDecl *D, Expr *Exp, Context Ctx) { | |||
547 | if (Ctx.contains(D)) { | |||
548 | unsigned newID = VarDefinitions.size(); | |||
549 | Context NewCtx = ContextFactory.remove(Ctx, D); | |||
550 | NewCtx = ContextFactory.add(NewCtx, D, newID); | |||
551 | VarDefinitions.push_back(VarDefinition(D, Exp, Ctx)); | |||
552 | return NewCtx; | |||
553 | } | |||
554 | return Ctx; | |||
555 | } | |||
556 | ||||
557 | // Removes a definition from the context, but keeps the variable name | |||
558 | // as a valid variable. The index 0 is a placeholder for cleared definitions. | |||
559 | Context clearDefinition(const NamedDecl *D, Context Ctx) { | |||
560 | Context NewCtx = Ctx; | |||
561 | if (NewCtx.contains(D)) { | |||
562 | NewCtx = ContextFactory.remove(NewCtx, D); | |||
563 | NewCtx = ContextFactory.add(NewCtx, D, 0); | |||
564 | } | |||
565 | return NewCtx; | |||
566 | } | |||
567 | ||||
568 | // Remove a definition entirely frmo the context. | |||
569 | Context removeDefinition(const NamedDecl *D, Context Ctx) { | |||
570 | Context NewCtx = Ctx; | |||
571 | if (NewCtx.contains(D)) { | |||
572 | NewCtx = ContextFactory.remove(NewCtx, D); | |||
573 | } | |||
574 | return NewCtx; | |||
575 | } | |||
576 | ||||
577 | Context intersectContexts(Context C1, Context C2); | |||
578 | Context createReferenceContext(Context C); | |||
579 | void intersectBackEdge(Context C1, Context C2); | |||
580 | }; | |||
581 | ||||
582 | } // namespace | |||
583 | ||||
584 | // This has to be defined after LocalVariableMap. | |||
585 | CFGBlockInfo CFGBlockInfo::getEmptyBlockInfo(LocalVariableMap &M) { | |||
586 | return CFGBlockInfo(M.getEmptyContext()); | |||
587 | } | |||
588 | ||||
589 | namespace { | |||
590 | ||||
591 | /// Visitor which builds a LocalVariableMap | |||
592 | class VarMapBuilder : public ConstStmtVisitor<VarMapBuilder> { | |||
593 | public: | |||
594 | LocalVariableMap* VMap; | |||
595 | LocalVariableMap::Context Ctx; | |||
596 | ||||
597 | VarMapBuilder(LocalVariableMap *VM, LocalVariableMap::Context C) | |||
598 | : VMap(VM), Ctx(C) {} | |||
599 | ||||
600 | void VisitDeclStmt(const DeclStmt *S); | |||
601 | void VisitBinaryOperator(const BinaryOperator *BO); | |||
602 | }; | |||
603 | ||||
604 | } // namespace | |||
605 | ||||
606 | // Add new local variables to the variable map | |||
607 | void VarMapBuilder::VisitDeclStmt(const DeclStmt *S) { | |||
608 | bool modifiedCtx = false; | |||
609 | const DeclGroupRef DGrp = S->getDeclGroup(); | |||
610 | for (const auto *D : DGrp) { | |||
611 | if (const auto *VD = dyn_cast_or_null<VarDecl>(D)) { | |||
612 | const Expr *E = VD->getInit(); | |||
613 | ||||
614 | // Add local variables with trivial type to the variable map | |||
615 | QualType T = VD->getType(); | |||
616 | if (T.isTrivialType(VD->getASTContext())) { | |||
617 | Ctx = VMap->addDefinition(VD, E, Ctx); | |||
618 | modifiedCtx = true; | |||
619 | } | |||
620 | } | |||
621 | } | |||
622 | if (modifiedCtx) | |||
623 | VMap->saveContext(S, Ctx); | |||
624 | } | |||
625 | ||||
626 | // Update local variable definitions in variable map | |||
627 | void VarMapBuilder::VisitBinaryOperator(const BinaryOperator *BO) { | |||
628 | if (!BO->isAssignmentOp()) | |||
629 | return; | |||
630 | ||||
631 | Expr *LHSExp = BO->getLHS()->IgnoreParenCasts(); | |||
632 | ||||
633 | // Update the variable map and current context. | |||
634 | if (const auto *DRE = dyn_cast<DeclRefExpr>(LHSExp)) { | |||
635 | const ValueDecl *VDec = DRE->getDecl(); | |||
636 | if (Ctx.lookup(VDec)) { | |||
637 | if (BO->getOpcode() == BO_Assign) | |||
638 | Ctx = VMap->updateDefinition(VDec, BO->getRHS(), Ctx); | |||
639 | else | |||
640 | // FIXME -- handle compound assignment operators | |||
641 | Ctx = VMap->clearDefinition(VDec, Ctx); | |||
642 | VMap->saveContext(BO, Ctx); | |||
643 | } | |||
644 | } | |||
645 | } | |||
646 | ||||
647 | // Computes the intersection of two contexts. The intersection is the | |||
648 | // set of variables which have the same definition in both contexts; | |||
649 | // variables with different definitions are discarded. | |||
650 | LocalVariableMap::Context | |||
651 | LocalVariableMap::intersectContexts(Context C1, Context C2) { | |||
652 | Context Result = C1; | |||
653 | for (const auto &P : C1) { | |||
654 | const NamedDecl *Dec = P.first; | |||
655 | const unsigned *i2 = C2.lookup(Dec); | |||
656 | if (!i2) // variable doesn't exist on second path | |||
657 | Result = removeDefinition(Dec, Result); | |||
658 | else if (*i2 != P.second) // variable exists, but has different definition | |||
659 | Result = clearDefinition(Dec, Result); | |||
660 | } | |||
661 | return Result; | |||
662 | } | |||
663 | ||||
664 | // For every variable in C, create a new variable that refers to the | |||
665 | // definition in C. Return a new context that contains these new variables. | |||
666 | // (We use this for a naive implementation of SSA on loop back-edges.) | |||
667 | LocalVariableMap::Context LocalVariableMap::createReferenceContext(Context C) { | |||
668 | Context Result = getEmptyContext(); | |||
669 | for (const auto &P : C) | |||
670 | Result = addReference(P.first, P.second, Result); | |||
671 | return Result; | |||
672 | } | |||
673 | ||||
674 | // This routine also takes the intersection of C1 and C2, but it does so by | |||
675 | // altering the VarDefinitions. C1 must be the result of an earlier call to | |||
676 | // createReferenceContext. | |||
677 | void LocalVariableMap::intersectBackEdge(Context C1, Context C2) { | |||
678 | for (const auto &P : C1) { | |||
679 | unsigned i1 = P.second; | |||
680 | VarDefinition *VDef = &VarDefinitions[i1]; | |||
681 | assert(VDef->isReference())((VDef->isReference()) ? static_cast<void> (0) : __assert_fail ("VDef->isReference()", "/build/llvm-toolchain-snapshot-9~svn362543/tools/clang/lib/Analysis/ThreadSafety.cpp" , 681, __PRETTY_FUNCTION__)); | |||
682 | ||||
683 | const unsigned *i2 = C2.lookup(P.first); | |||
684 | if (!i2 || (*i2 != i1)) | |||
685 | VDef->Ref = 0; // Mark this variable as undefined | |||
686 | } | |||
687 | } | |||
688 | ||||
689 | // Traverse the CFG in topological order, so all predecessors of a block | |||
690 | // (excluding back-edges) are visited before the block itself. At | |||
691 | // each point in the code, we calculate a Context, which holds the set of | |||
692 | // variable definitions which are visible at that point in execution. | |||
693 | // Visible variables are mapped to their definitions using an array that | |||
694 | // contains all definitions. | |||
695 | // | |||
696 | // At join points in the CFG, the set is computed as the intersection of | |||
697 | // the incoming sets along each edge, E.g. | |||
698 | // | |||
699 | // { Context | VarDefinitions } | |||
700 | // int x = 0; { x -> x1 | x1 = 0 } | |||
701 | // int y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 } | |||
702 | // if (b) x = 1; { x -> x2, y -> y1 | x2 = 1, y1 = 0, ... } | |||
703 | // else x = 2; { x -> x3, y -> y1 | x3 = 2, x2 = 1, ... } | |||
704 | // ... { y -> y1 (x is unknown) | x3 = 2, x2 = 1, ... } | |||
705 | // | |||
706 | // This is essentially a simpler and more naive version of the standard SSA | |||
707 | // algorithm. Those definitions that remain in the intersection are from blocks | |||
708 | // that strictly dominate the current block. We do not bother to insert proper | |||
709 | // phi nodes, because they are not used in our analysis; instead, wherever | |||
710 | // a phi node would be required, we simply remove that definition from the | |||
711 | // context (E.g. x above). | |||
712 | // | |||
713 | // The initial traversal does not capture back-edges, so those need to be | |||
714 | // handled on a separate pass. Whenever the first pass encounters an | |||
715 | // incoming back edge, it duplicates the context, creating new definitions | |||
716 | // that refer back to the originals. (These correspond to places where SSA | |||
717 | // might have to insert a phi node.) On the second pass, these definitions are | |||
718 | // set to NULL if the variable has changed on the back-edge (i.e. a phi | |||
719 | // node was actually required.) E.g. | |||
720 | // | |||
721 | // { Context | VarDefinitions } | |||
722 | // int x = 0, y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 } | |||
723 | // while (b) { x -> x2, y -> y1 | [1st:] x2=x1; [2nd:] x2=NULL; } | |||
724 | // x = x+1; { x -> x3, y -> y1 | x3 = x2 + 1, ... } | |||
725 | // ... { y -> y1 | x3 = 2, x2 = 1, ... } | |||
726 | void LocalVariableMap::traverseCFG(CFG *CFGraph, | |||
727 | const PostOrderCFGView *SortedGraph, | |||
728 | std::vector<CFGBlockInfo> &BlockInfo) { | |||
729 | PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); | |||
730 | ||||
731 | CtxIndices.resize(CFGraph->getNumBlockIDs()); | |||
732 | ||||
733 | for (const auto *CurrBlock : *SortedGraph) { | |||
734 | unsigned CurrBlockID = CurrBlock->getBlockID(); | |||
735 | CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; | |||
736 | ||||
737 | VisitedBlocks.insert(CurrBlock); | |||
738 | ||||
739 | // Calculate the entry context for the current block | |||
740 | bool HasBackEdges = false; | |||
741 | bool CtxInit = true; | |||
742 | for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), | |||
743 | PE = CurrBlock->pred_end(); PI != PE; ++PI) { | |||
744 | // if *PI -> CurrBlock is a back edge, so skip it | |||
745 | if (*PI == nullptr || !VisitedBlocks.alreadySet(*PI)) { | |||
746 | HasBackEdges = true; | |||
747 | continue; | |||
748 | } | |||
749 | ||||
750 | unsigned PrevBlockID = (*PI)->getBlockID(); | |||
751 | CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; | |||
752 | ||||
753 | if (CtxInit) { | |||
754 | CurrBlockInfo->EntryContext = PrevBlockInfo->ExitContext; | |||
755 | CtxInit = false; | |||
756 | } | |||
757 | else { | |||
758 | CurrBlockInfo->EntryContext = | |||
759 | intersectContexts(CurrBlockInfo->EntryContext, | |||
760 | PrevBlockInfo->ExitContext); | |||
761 | } | |||
762 | } | |||
763 | ||||
764 | // Duplicate the context if we have back-edges, so we can call | |||
765 | // intersectBackEdges later. | |||
766 | if (HasBackEdges) | |||
767 | CurrBlockInfo->EntryContext = | |||
768 | createReferenceContext(CurrBlockInfo->EntryContext); | |||
769 | ||||
770 | // Create a starting context index for the current block | |||
771 | saveContext(nullptr, CurrBlockInfo->EntryContext); | |||
772 | CurrBlockInfo->EntryIndex = getContextIndex(); | |||
773 | ||||
774 | // Visit all the statements in the basic block. | |||
775 | VarMapBuilder VMapBuilder(this, CurrBlockInfo->EntryContext); | |||
776 | for (const auto &BI : *CurrBlock) { | |||
777 | switch (BI.getKind()) { | |||
778 | case CFGElement::Statement: { | |||
779 | CFGStmt CS = BI.castAs<CFGStmt>(); | |||
780 | VMapBuilder.Visit(CS.getStmt()); | |||
781 | break; | |||
782 | } | |||
783 | default: | |||
784 | break; | |||
785 | } | |||
786 | } | |||
787 | CurrBlockInfo->ExitContext = VMapBuilder.Ctx; | |||
788 | ||||
789 | // Mark variables on back edges as "unknown" if they've been changed. | |||
790 | for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), | |||
791 | SE = CurrBlock->succ_end(); SI != SE; ++SI) { | |||
792 | // if CurrBlock -> *SI is *not* a back edge | |||
793 | if (*SI == nullptr || !VisitedBlocks.alreadySet(*SI)) | |||
794 | continue; | |||
795 | ||||
796 | CFGBlock *FirstLoopBlock = *SI; | |||
797 | Context LoopBegin = BlockInfo[FirstLoopBlock->getBlockID()].EntryContext; | |||
798 | Context LoopEnd = CurrBlockInfo->ExitContext; | |||
799 | intersectBackEdge(LoopBegin, LoopEnd); | |||
800 | } | |||
801 | } | |||
802 | ||||
803 | // Put an extra entry at the end of the indexed context array | |||
804 | unsigned exitID = CFGraph->getExit().getBlockID(); | |||
805 | saveContext(nullptr, BlockInfo[exitID].ExitContext); | |||
806 | } | |||
807 | ||||
808 | /// Find the appropriate source locations to use when producing diagnostics for | |||
809 | /// each block in the CFG. | |||
810 | static void findBlockLocations(CFG *CFGraph, | |||
811 | const PostOrderCFGView *SortedGraph, | |||
812 | std::vector<CFGBlockInfo> &BlockInfo) { | |||
813 | for (const auto *CurrBlock : *SortedGraph) { | |||
814 | CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlock->getBlockID()]; | |||
815 | ||||
816 | // Find the source location of the last statement in the block, if the | |||
817 | // block is not empty. | |||
818 | if (const Stmt *S = CurrBlock->getTerminatorStmt()) { | |||
819 | CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = S->getBeginLoc(); | |||
820 | } else { | |||
821 | for (CFGBlock::const_reverse_iterator BI = CurrBlock->rbegin(), | |||
822 | BE = CurrBlock->rend(); BI != BE; ++BI) { | |||
823 | // FIXME: Handle other CFGElement kinds. | |||
824 | if (Optional<CFGStmt> CS = BI->getAs<CFGStmt>()) { | |||
825 | CurrBlockInfo->ExitLoc = CS->getStmt()->getBeginLoc(); | |||
826 | break; | |||
827 | } | |||
828 | } | |||
829 | } | |||
830 | ||||
831 | if (CurrBlockInfo->ExitLoc.isValid()) { | |||
832 | // This block contains at least one statement. Find the source location | |||
833 | // of the first statement in the block. | |||
834 | for (const auto &BI : *CurrBlock) { | |||
835 | // FIXME: Handle other CFGElement kinds. | |||
836 | if (Optional<CFGStmt> CS = BI.getAs<CFGStmt>()) { | |||
837 | CurrBlockInfo->EntryLoc = CS->getStmt()->getBeginLoc(); | |||
838 | break; | |||
839 | } | |||
840 | } | |||
841 | } else if (CurrBlock->pred_size() == 1 && *CurrBlock->pred_begin() && | |||
842 | CurrBlock != &CFGraph->getExit()) { | |||
843 | // The block is empty, and has a single predecessor. Use its exit | |||
844 | // location. | |||
845 | CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = | |||
846 | BlockInfo[(*CurrBlock->pred_begin())->getBlockID()].ExitLoc; | |||
847 | } | |||
848 | } | |||
849 | } | |||
850 | ||||
851 | namespace { | |||
852 | ||||
853 | class LockableFactEntry : public FactEntry { | |||
854 | private: | |||
855 | /// managed by ScopedLockable object | |||
856 | bool Managed; | |||
857 | ||||
858 | public: | |||
859 | LockableFactEntry(const CapabilityExpr &CE, LockKind LK, SourceLocation Loc, | |||
860 | bool Mng = false, bool Asrt = false) | |||
861 | : FactEntry(CE, LK, Loc, Asrt), Managed(Mng) {} | |||
862 | ||||
863 | void | |||
864 | handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan, | |||
865 | SourceLocation JoinLoc, LockErrorKind LEK, | |||
866 | ThreadSafetyHandler &Handler) const override { | |||
867 | if (!Managed && !asserted() && !negative() && !isUniversal()) { | |||
868 | Handler.handleMutexHeldEndOfScope("mutex", toString(), loc(), JoinLoc, | |||
869 | LEK); | |||
870 | } | |||
871 | } | |||
872 | ||||
873 | void handleLock(FactSet &FSet, FactManager &FactMan, const FactEntry &entry, | |||
874 | ThreadSafetyHandler &Handler, | |||
875 | StringRef DiagKind) const override { | |||
876 | Handler.handleDoubleLock(DiagKind, entry.toString(), loc(), entry.loc()); | |||
877 | } | |||
878 | ||||
879 | void handleUnlock(FactSet &FSet, FactManager &FactMan, | |||
880 | const CapabilityExpr &Cp, SourceLocation UnlockLoc, | |||
881 | bool FullyRemove, ThreadSafetyHandler &Handler, | |||
882 | StringRef DiagKind) const override { | |||
883 | FSet.removeLock(FactMan, Cp); | |||
884 | if (!Cp.negative()) { | |||
885 | FSet.addLock(FactMan, llvm::make_unique<LockableFactEntry>( | |||
886 | !Cp, LK_Exclusive, UnlockLoc)); | |||
887 | } | |||
888 | } | |||
889 | }; | |||
890 | ||||
891 | class ScopedLockableFactEntry : public FactEntry { | |||
892 | private: | |||
893 | enum UnderlyingCapabilityKind { | |||
894 | UCK_Acquired, ///< Any kind of acquired capability. | |||
895 | UCK_ReleasedShared, ///< Shared capability that was released. | |||
896 | UCK_ReleasedExclusive, ///< Exclusive capability that was released. | |||
897 | }; | |||
898 | ||||
899 | using UnderlyingCapability = | |||
900 | llvm::PointerIntPair<const til::SExpr *, 2, UnderlyingCapabilityKind>; | |||
901 | ||||
902 | SmallVector<UnderlyingCapability, 4> UnderlyingMutexes; | |||
903 | ||||
904 | public: | |||
905 | ScopedLockableFactEntry(const CapabilityExpr &CE, SourceLocation Loc) | |||
906 | : FactEntry(CE, LK_Exclusive, Loc, false) {} | |||
907 | ||||
908 | void addExclusiveLock(const CapabilityExpr &M) { | |||
909 | UnderlyingMutexes.emplace_back(M.sexpr(), UCK_Acquired); | |||
910 | } | |||
911 | ||||
912 | void addSharedLock(const CapabilityExpr &M) { | |||
913 | UnderlyingMutexes.emplace_back(M.sexpr(), UCK_Acquired); | |||
914 | } | |||
915 | ||||
916 | void addExclusiveUnlock(const CapabilityExpr &M) { | |||
917 | UnderlyingMutexes.emplace_back(M.sexpr(), UCK_ReleasedExclusive); | |||
918 | } | |||
919 | ||||
920 | void addSharedUnlock(const CapabilityExpr &M) { | |||
921 | UnderlyingMutexes.emplace_back(M.sexpr(), UCK_ReleasedShared); | |||
922 | } | |||
923 | ||||
924 | void | |||
925 | handleRemovalFromIntersection(const FactSet &FSet, FactManager &FactMan, | |||
926 | SourceLocation JoinLoc, LockErrorKind LEK, | |||
927 | ThreadSafetyHandler &Handler) const override { | |||
928 | for (const auto &UnderlyingMutex : UnderlyingMutexes) { | |||
929 | const auto *Entry = FSet.findLock( | |||
930 | FactMan, CapabilityExpr(UnderlyingMutex.getPointer(), false)); | |||
931 | if ((UnderlyingMutex.getInt() == UCK_Acquired && Entry) || | |||
932 | (UnderlyingMutex.getInt() != UCK_Acquired && !Entry)) { | |||
933 | // If this scoped lock manages another mutex, and if the underlying | |||
934 | // mutex is still/not held, then warn about the underlying mutex. | |||
935 | Handler.handleMutexHeldEndOfScope( | |||
936 | "mutex", sx::toString(UnderlyingMutex.getPointer()), loc(), JoinLoc, | |||
937 | LEK); | |||
938 | } | |||
939 | } | |||
940 | } | |||
941 | ||||
942 | void handleLock(FactSet &FSet, FactManager &FactMan, const FactEntry &entry, | |||
943 | ThreadSafetyHandler &Handler, | |||
944 | StringRef DiagKind) const override { | |||
945 | for (const auto &UnderlyingMutex : UnderlyingMutexes) { | |||
946 | CapabilityExpr UnderCp(UnderlyingMutex.getPointer(), false); | |||
947 | ||||
948 | if (UnderlyingMutex.getInt() == UCK_Acquired) | |||
949 | lock(FSet, FactMan, UnderCp, entry.kind(), entry.loc(), &Handler, | |||
950 | DiagKind); | |||
951 | else | |||
952 | unlock(FSet, FactMan, UnderCp, entry.loc(), &Handler, DiagKind); | |||
953 | } | |||
954 | } | |||
955 | ||||
956 | void handleUnlock(FactSet &FSet, FactManager &FactMan, | |||
957 | const CapabilityExpr &Cp, SourceLocation UnlockLoc, | |||
958 | bool FullyRemove, ThreadSafetyHandler &Handler, | |||
959 | StringRef DiagKind) const override { | |||
960 | assert(!Cp.negative() && "Managing object cannot be negative.")((!Cp.negative() && "Managing object cannot be negative." ) ? static_cast<void> (0) : __assert_fail ("!Cp.negative() && \"Managing object cannot be negative.\"" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/clang/lib/Analysis/ThreadSafety.cpp" , 960, __PRETTY_FUNCTION__)); | |||
961 | for (const auto &UnderlyingMutex : UnderlyingMutexes) { | |||
962 | CapabilityExpr UnderCp(UnderlyingMutex.getPointer(), false); | |||
963 | ||||
964 | // Remove/lock the underlying mutex if it exists/is still unlocked; warn | |||
965 | // on double unlocking/locking if we're not destroying the scoped object. | |||
966 | ThreadSafetyHandler *TSHandler = FullyRemove ? nullptr : &Handler; | |||
967 | if (UnderlyingMutex.getInt() == UCK_Acquired) { | |||
968 | unlock(FSet, FactMan, UnderCp, UnlockLoc, TSHandler, DiagKind); | |||
969 | } else { | |||
970 | LockKind kind = UnderlyingMutex.getInt() == UCK_ReleasedShared | |||
971 | ? LK_Shared | |||
972 | : LK_Exclusive; | |||
973 | lock(FSet, FactMan, UnderCp, kind, UnlockLoc, TSHandler, DiagKind); | |||
974 | } | |||
975 | } | |||
976 | if (FullyRemove) | |||
977 | FSet.removeLock(FactMan, Cp); | |||
978 | } | |||
979 | ||||
980 | private: | |||
981 | void lock(FactSet &FSet, FactManager &FactMan, const CapabilityExpr &Cp, | |||
982 | LockKind kind, SourceLocation loc, ThreadSafetyHandler *Handler, | |||
983 | StringRef DiagKind) const { | |||
984 | if (const FactEntry *Fact = FSet.findLock(FactMan, Cp)) { | |||
985 | if (Handler) | |||
986 | Handler->handleDoubleLock(DiagKind, Cp.toString(), Fact->loc(), loc); | |||
987 | } else { | |||
988 | FSet.removeLock(FactMan, !Cp); | |||
989 | FSet.addLock(FactMan, | |||
990 | llvm::make_unique<LockableFactEntry>(Cp, kind, loc)); | |||
991 | } | |||
992 | } | |||
993 | ||||
994 | void unlock(FactSet &FSet, FactManager &FactMan, const CapabilityExpr &Cp, | |||
995 | SourceLocation loc, ThreadSafetyHandler *Handler, | |||
996 | StringRef DiagKind) const { | |||
997 | if (FSet.findLock(FactMan, Cp)) { | |||
998 | FSet.removeLock(FactMan, Cp); | |||
999 | FSet.addLock(FactMan, llvm::make_unique<LockableFactEntry>( | |||
1000 | !Cp, LK_Exclusive, loc)); | |||
1001 | } else if (Handler) { | |||
1002 | Handler->handleUnmatchedUnlock(DiagKind, Cp.toString(), loc); | |||
1003 | } | |||
1004 | } | |||
1005 | }; | |||
1006 | ||||
1007 | /// Class which implements the core thread safety analysis routines. | |||
1008 | class ThreadSafetyAnalyzer { | |||
1009 | friend class BuildLockset; | |||
1010 | friend class threadSafety::BeforeSet; | |||
1011 | ||||
1012 | llvm::BumpPtrAllocator Bpa; | |||
1013 | threadSafety::til::MemRegionRef Arena; | |||
1014 | threadSafety::SExprBuilder SxBuilder; | |||
1015 | ||||
1016 | ThreadSafetyHandler &Handler; | |||
1017 | const CXXMethodDecl *CurrentMethod; | |||
1018 | LocalVariableMap LocalVarMap; | |||
1019 | FactManager FactMan; | |||
1020 | std::vector<CFGBlockInfo> BlockInfo; | |||
1021 | ||||
1022 | BeforeSet *GlobalBeforeSet; | |||
1023 | ||||
1024 | public: | |||
1025 | ThreadSafetyAnalyzer(ThreadSafetyHandler &H, BeforeSet* Bset) | |||
1026 | : Arena(&Bpa), SxBuilder(Arena), Handler(H), GlobalBeforeSet(Bset) {} | |||
1027 | ||||
1028 | bool inCurrentScope(const CapabilityExpr &CapE); | |||
1029 | ||||
1030 | void addLock(FactSet &FSet, std::unique_ptr<FactEntry> Entry, | |||
1031 | StringRef DiagKind, bool ReqAttr = false); | |||
1032 | void removeLock(FactSet &FSet, const CapabilityExpr &CapE, | |||
1033 | SourceLocation UnlockLoc, bool FullyRemove, LockKind Kind, | |||
1034 | StringRef DiagKind); | |||
1035 | ||||
1036 | template <typename AttrType> | |||
1037 | void getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, const Expr *Exp, | |||
1038 | const NamedDecl *D, VarDecl *SelfDecl = nullptr); | |||
1039 | ||||
1040 | template <class AttrType> | |||
1041 | void getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, const Expr *Exp, | |||
1042 | const NamedDecl *D, | |||
1043 | const CFGBlock *PredBlock, const CFGBlock *CurrBlock, | |||
1044 | Expr *BrE, bool Neg); | |||
1045 | ||||
1046 | const CallExpr* getTrylockCallExpr(const Stmt *Cond, LocalVarContext C, | |||
1047 | bool &Negate); | |||
1048 | ||||
1049 | void getEdgeLockset(FactSet &Result, const FactSet &ExitSet, | |||
1050 | const CFGBlock* PredBlock, | |||
1051 | const CFGBlock *CurrBlock); | |||
1052 | ||||
1053 | void intersectAndWarn(FactSet &FSet1, const FactSet &FSet2, | |||
1054 | SourceLocation JoinLoc, | |||
1055 | LockErrorKind LEK1, LockErrorKind LEK2, | |||
1056 | bool Modify=true); | |||
1057 | ||||
1058 | void intersectAndWarn(FactSet &FSet1, const FactSet &FSet2, | |||
1059 | SourceLocation JoinLoc, LockErrorKind LEK1, | |||
1060 | bool Modify=true) { | |||
1061 | intersectAndWarn(FSet1, FSet2, JoinLoc, LEK1, LEK1, Modify); | |||
1062 | } | |||
1063 | ||||
1064 | void runAnalysis(AnalysisDeclContext &AC); | |||
1065 | }; | |||
1066 | ||||
1067 | } // namespace | |||
1068 | ||||
1069 | /// Process acquired_before and acquired_after attributes on Vd. | |||
1070 | BeforeSet::BeforeInfo* BeforeSet::insertAttrExprs(const ValueDecl* Vd, | |||
1071 | ThreadSafetyAnalyzer& Analyzer) { | |||
1072 | // Create a new entry for Vd. | |||
1073 | BeforeInfo *Info = nullptr; | |||
1074 | { | |||
1075 | // Keep InfoPtr in its own scope in case BMap is modified later and the | |||
1076 | // reference becomes invalid. | |||
1077 | std::unique_ptr<BeforeInfo> &InfoPtr = BMap[Vd]; | |||
1078 | if (!InfoPtr) | |||
1079 | InfoPtr.reset(new BeforeInfo()); | |||
1080 | Info = InfoPtr.get(); | |||
1081 | } | |||
1082 | ||||
1083 | for (const auto *At : Vd->attrs()) { | |||
1084 | switch (At->getKind()) { | |||
1085 | case attr::AcquiredBefore: { | |||
1086 | const auto *A = cast<AcquiredBeforeAttr>(At); | |||
1087 | ||||
1088 | // Read exprs from the attribute, and add them to BeforeVect. | |||
1089 | for (const auto *Arg : A->args()) { | |||
1090 | CapabilityExpr Cp = | |||
1091 | Analyzer.SxBuilder.translateAttrExpr(Arg, nullptr); | |||
1092 | if (const ValueDecl *Cpvd = Cp.valueDecl()) { | |||
1093 | Info->Vect.push_back(Cpvd); | |||
1094 | const auto It = BMap.find(Cpvd); | |||
1095 | if (It == BMap.end()) | |||
1096 | insertAttrExprs(Cpvd, Analyzer); | |||
1097 | } | |||
1098 | } | |||
1099 | break; | |||
1100 | } | |||
1101 | case attr::AcquiredAfter: { | |||
1102 | const auto *A = cast<AcquiredAfterAttr>(At); | |||
1103 | ||||
1104 | // Read exprs from the attribute, and add them to BeforeVect. | |||
1105 | for (const auto *Arg : A->args()) { | |||
1106 | CapabilityExpr Cp = | |||
1107 | Analyzer.SxBuilder.translateAttrExpr(Arg, nullptr); | |||
1108 | if (const ValueDecl *ArgVd = Cp.valueDecl()) { | |||
1109 | // Get entry for mutex listed in attribute | |||
1110 | BeforeInfo *ArgInfo = getBeforeInfoForDecl(ArgVd, Analyzer); | |||
1111 | ArgInfo->Vect.push_back(Vd); | |||
1112 | } | |||
1113 | } | |||
1114 | break; | |||
1115 | } | |||
1116 | default: | |||
1117 | break; | |||
1118 | } | |||
1119 | } | |||
1120 | ||||
1121 | return Info; | |||
1122 | } | |||
1123 | ||||
1124 | BeforeSet::BeforeInfo * | |||
1125 | BeforeSet::getBeforeInfoForDecl(const ValueDecl *Vd, | |||
1126 | ThreadSafetyAnalyzer &Analyzer) { | |||
1127 | auto It = BMap.find(Vd); | |||
1128 | BeforeInfo *Info = nullptr; | |||
1129 | if (It == BMap.end()) | |||
1130 | Info = insertAttrExprs(Vd, Analyzer); | |||
1131 | else | |||
1132 | Info = It->second.get(); | |||
1133 | assert(Info && "BMap contained nullptr?")((Info && "BMap contained nullptr?") ? static_cast< void> (0) : __assert_fail ("Info && \"BMap contained nullptr?\"" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/clang/lib/Analysis/ThreadSafety.cpp" , 1133, __PRETTY_FUNCTION__)); | |||
1134 | return Info; | |||
1135 | } | |||
1136 | ||||
1137 | /// Return true if any mutexes in FSet are in the acquired_before set of Vd. | |||
1138 | void BeforeSet::checkBeforeAfter(const ValueDecl* StartVd, | |||
1139 | const FactSet& FSet, | |||
1140 | ThreadSafetyAnalyzer& Analyzer, | |||
1141 | SourceLocation Loc, StringRef CapKind) { | |||
1142 | SmallVector<BeforeInfo*, 8> InfoVect; | |||
1143 | ||||
1144 | // Do a depth-first traversal of Vd. | |||
1145 | // Return true if there are cycles. | |||
1146 | std::function<bool (const ValueDecl*)> traverse = [&](const ValueDecl* Vd) { | |||
1147 | if (!Vd) | |||
1148 | return false; | |||
1149 | ||||
1150 | BeforeSet::BeforeInfo *Info = getBeforeInfoForDecl(Vd, Analyzer); | |||
1151 | ||||
1152 | if (Info->Visited == 1) | |||
1153 | return true; | |||
1154 | ||||
1155 | if (Info->Visited == 2) | |||
1156 | return false; | |||
1157 | ||||
1158 | if (Info->Vect.empty()) | |||
1159 | return false; | |||
1160 | ||||
1161 | InfoVect.push_back(Info); | |||
1162 | Info->Visited = 1; | |||
1163 | for (const auto *Vdb : Info->Vect) { | |||
1164 | // Exclude mutexes in our immediate before set. | |||
1165 | if (FSet.containsMutexDecl(Analyzer.FactMan, Vdb)) { | |||
1166 | StringRef L1 = StartVd->getName(); | |||
1167 | StringRef L2 = Vdb->getName(); | |||
1168 | Analyzer.Handler.handleLockAcquiredBefore(CapKind, L1, L2, Loc); | |||
1169 | } | |||
1170 | // Transitively search other before sets, and warn on cycles. | |||
1171 | if (traverse(Vdb)) { | |||
1172 | if (CycMap.find(Vd) == CycMap.end()) { | |||
1173 | CycMap.insert(std::make_pair(Vd, true)); | |||
1174 | StringRef L1 = Vd->getName(); | |||
1175 | Analyzer.Handler.handleBeforeAfterCycle(L1, Vd->getLocation()); | |||
1176 | } | |||
1177 | } | |||
1178 | } | |||
1179 | Info->Visited = 2; | |||
1180 | return false; | |||
1181 | }; | |||
1182 | ||||
1183 | traverse(StartVd); | |||
1184 | ||||
1185 | for (auto *Info : InfoVect) | |||
1186 | Info->Visited = 0; | |||
1187 | } | |||
1188 | ||||
1189 | /// Gets the value decl pointer from DeclRefExprs or MemberExprs. | |||
1190 | static const ValueDecl *getValueDecl(const Expr *Exp) { | |||
1191 | if (const auto *CE = dyn_cast<ImplicitCastExpr>(Exp)) | |||
1192 | return getValueDecl(CE->getSubExpr()); | |||
1193 | ||||
1194 | if (const auto *DR = dyn_cast<DeclRefExpr>(Exp)) | |||
1195 | return DR->getDecl(); | |||
1196 | ||||
1197 | if (const auto *ME = dyn_cast<MemberExpr>(Exp)) | |||
1198 | return ME->getMemberDecl(); | |||
1199 | ||||
1200 | return nullptr; | |||
1201 | } | |||
1202 | ||||
1203 | namespace { | |||
1204 | ||||
1205 | template <typename Ty> | |||
1206 | class has_arg_iterator_range { | |||
1207 | using yes = char[1]; | |||
1208 | using no = char[2]; | |||
1209 | ||||
1210 | template <typename Inner> | |||
1211 | static yes& test(Inner *I, decltype(I->args()) * = nullptr); | |||
1212 | ||||
1213 | template <typename> | |||
1214 | static no& test(...); | |||
1215 | ||||
1216 | public: | |||
1217 | static const bool value = sizeof(test<Ty>(nullptr)) == sizeof(yes); | |||
1218 | }; | |||
1219 | ||||
1220 | } // namespace | |||
1221 | ||||
1222 | static StringRef ClassifyDiagnostic(const CapabilityAttr *A) { | |||
1223 | return A->getName(); | |||
1224 | } | |||
1225 | ||||
1226 | static StringRef ClassifyDiagnostic(QualType VDT) { | |||
1227 | // We need to look at the declaration of the type of the value to determine | |||
1228 | // which it is. The type should either be a record or a typedef, or a pointer | |||
1229 | // or reference thereof. | |||
1230 | if (const auto *RT = VDT->getAs<RecordType>()) { | |||
1231 | if (const auto *RD = RT->getDecl()) | |||
1232 | if (const auto *CA = RD->getAttr<CapabilityAttr>()) | |||
1233 | return ClassifyDiagnostic(CA); | |||
1234 | } else if (const auto *TT = VDT->getAs<TypedefType>()) { | |||
1235 | if (const auto *TD = TT->getDecl()) | |||
1236 | if (const auto *CA = TD->getAttr<CapabilityAttr>()) | |||
1237 | return ClassifyDiagnostic(CA); | |||
1238 | } else if (VDT->isPointerType() || VDT->isReferenceType()) | |||
1239 | return ClassifyDiagnostic(VDT->getPointeeType()); | |||
1240 | ||||
1241 | return "mutex"; | |||
1242 | } | |||
1243 | ||||
1244 | static StringRef ClassifyDiagnostic(const ValueDecl *VD) { | |||
1245 | assert(VD && "No ValueDecl passed")((VD && "No ValueDecl passed") ? static_cast<void> (0) : __assert_fail ("VD && \"No ValueDecl passed\"" , "/build/llvm-toolchain-snapshot-9~svn362543/tools/clang/lib/Analysis/ThreadSafety.cpp" , 1245, __PRETTY_FUNCTION__)); | |||
1246 | ||||
1247 | // The ValueDecl is the declaration of a mutex or role (hopefully). | |||
1248 | return ClassifyDiagnostic(VD->getType()); | |||
1249 | } | |||
1250 | ||||
1251 | template <typename AttrTy> | |||
1252 | static typename std::enable_if<!has_arg_iterator_range<AttrTy>::value, | |||
1253 | StringRef>::type | |||
1254 | ClassifyDiagnostic(const AttrTy *A) { | |||
1255 | if (const ValueDecl *VD = getValueDecl(A->getArg())) | |||
1256 | return ClassifyDiagnostic(VD); | |||
1257 | return "mutex"; | |||
1258 | } | |||
1259 | ||||
1260 | template <typename AttrTy> | |||
1261 | static typename std::enable_if<has_arg_iterator_range<AttrTy>::value, | |||
1262 | StringRef>::type | |||
1263 | ClassifyDiagnostic(const AttrTy *A) { | |||
1264 | for (const auto *Arg : A->args()) { | |||
1265 | if (const ValueDecl *VD = getValueDecl(Arg)) | |||
1266 | return ClassifyDiagnostic(VD); | |||
1267 | } | |||
1268 | return "mutex"; | |||
1269 | } | |||
1270 | ||||
1271 | bool ThreadSafetyAnalyzer::inCurrentScope(const CapabilityExpr &CapE) { | |||
1272 | if (!CurrentMethod) | |||
1273 | return false; | |||
1274 | if (const auto *P = dyn_cast_or_null<til::Project>(CapE.sexpr())) { | |||
1275 | const auto *VD = P->clangDecl(); | |||
1276 | if (VD) | |||
1277 | return VD->getDeclContext() == CurrentMethod->getDeclContext(); | |||
1278 | } | |||
1279 | return false; | |||
1280 | } | |||
1281 | ||||
1282 | /// Add a new lock to the lockset, warning if the lock is already there. | |||
1283 | /// \param ReqAttr -- true if this is part of an initial Requires attribute. | |||
1284 | void ThreadSafetyAnalyzer::addLock(FactSet &FSet, | |||
1285 | std::unique_ptr<FactEntry> Entry, | |||
1286 | StringRef DiagKind, bool ReqAttr) { | |||
1287 | if (Entry->shouldIgnore()) | |||
1288 | return; | |||
1289 | ||||
1290 | if (!ReqAttr && !Entry->negative()) { | |||
1291 | // look for the negative capability, and remove it from the fact set. | |||
1292 | CapabilityExpr NegC = !*Entry; | |||
1293 | const FactEntry *Nen = FSet.findLock(FactMan, NegC); | |||
1294 | if (Nen) { | |||
1295 | FSet.removeLock(FactMan, NegC); | |||
1296 | } | |||
1297 | else { | |||
1298 | if (inCurrentScope(*Entry) && !Entry->asserted()) | |||
1299 | Handler.handleNegativeNotHeld(DiagKind, Entry->toString(), | |||
1300 | NegC.toString(), Entry->loc()); | |||
1301 | } | |||
1302 | } | |||
1303 | ||||
1304 | // Check before/after constraints | |||
1305 | if (Handler.issueBetaWarnings() && | |||
1306 | !Entry->asserted() && !Entry->declared()) { | |||
1307 | GlobalBeforeSet->checkBeforeAfter(Entry->valueDecl(), FSet, *this, | |||
1308 | Entry->loc(), DiagKind); | |||
1309 | } | |||
1310 | ||||
1311 | // FIXME: Don't always warn when we have support for reentrant locks. | |||
1312 | if (const FactEntry *Cp = FSet.findLock(FactMan, *Entry)) { | |||
1313 | if (!Entry->asserted()) | |||
1314 | Cp->handleLock(FSet, FactMan, *Entry, Handler, DiagKind); | |||
1315 | } else { | |||
1316 | FSet.addLock(FactMan, std::move(Entry)); | |||
1317 | } | |||
1318 | } | |||
1319 | ||||
1320 | /// Remove a lock from the lockset, warning if the lock is not there. | |||
1321 | /// \param UnlockLoc The source location of the unlock (only used in error msg) | |||
1322 | void ThreadSafetyAnalyzer::removeLock(FactSet &FSet, const CapabilityExpr &Cp, | |||
1323 | SourceLocation UnlockLoc, | |||
1324 | bool FullyRemove, LockKind ReceivedKind, | |||
1325 | StringRef DiagKind) { | |||
1326 | if (Cp.shouldIgnore()) | |||
1327 | return; | |||
1328 | ||||
1329 | const FactEntry *LDat = FSet.findLock(FactMan, Cp); | |||
1330 | if (!LDat) { | |||
1331 | Handler.handleUnmatchedUnlock(DiagKind, Cp.toString(), UnlockLoc); | |||
1332 | return; | |||
1333 | } | |||
1334 | ||||
1335 | // Generic lock removal doesn't care about lock kind mismatches, but | |||
1336 | // otherwise diagnose when the lock kinds are mismatched. | |||
1337 | if (ReceivedKind != LK_Generic && LDat->kind() != ReceivedKind) { | |||
1338 | Handler.handleIncorrectUnlockKind(DiagKind, Cp.toString(), LDat->kind(), | |||
1339 | ReceivedKind, LDat->loc(), UnlockLoc); | |||
1340 | } | |||
1341 | ||||
1342 | LDat->handleUnlock(FSet, FactMan, Cp, UnlockLoc, FullyRemove, Handler, | |||
1343 | DiagKind); | |||
1344 | } | |||
1345 | ||||
1346 | /// Extract the list of mutexIDs from the attribute on an expression, | |||
1347 | /// and push them onto Mtxs, discarding any duplicates. | |||
1348 | template <typename AttrType> | |||
1349 | void ThreadSafetyAnalyzer::getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, | |||
1350 | const Expr *Exp, const NamedDecl *D, | |||
1351 | VarDecl *SelfDecl) { | |||
1352 | if (Attr->args_size() == 0) { | |||
1353 | // The mutex held is the "this" object. | |||
1354 | CapabilityExpr Cp = SxBuilder.translateAttrExpr(nullptr, D, Exp, SelfDecl); | |||
1355 | if (Cp.isInvalid()) { | |||
1356 | warnInvalidLock(Handler, nullptr, D, Exp, ClassifyDiagnostic(Attr)); | |||
1357 | return; | |||
1358 | } | |||
1359 | //else | |||
1360 | if (!Cp.shouldIgnore()) | |||
1361 | Mtxs.push_back_nodup(Cp); | |||
1362 | return; | |||
1363 | } | |||
1364 | ||||
1365 | for (const auto *Arg : Attr->args()) { | |||
1366 | CapabilityExpr Cp = SxBuilder.translateAttrExpr(Arg, D, Exp, SelfDecl); | |||
1367 | if (Cp.isInvalid()) { | |||
1368 | warnInvalidLock(Handler, nullptr, D, Exp, ClassifyDiagnostic(Attr)); | |||
1369 | continue; | |||
1370 | } | |||
1371 | //else | |||
1372 | if (!Cp.shouldIgnore()) | |||
1373 | Mtxs.push_back_nodup(Cp); | |||
1374 | } | |||
1375 | } | |||
1376 | ||||
1377 | /// Extract the list of mutexIDs from a trylock attribute. If the | |||
1378 | /// trylock applies to the given edge, then push them onto Mtxs, discarding | |||
1379 | /// any duplicates. | |||
1380 | template <class AttrType> | |||
1381 | void ThreadSafetyAnalyzer::getMutexIDs(CapExprSet &Mtxs, AttrType *Attr, | |||
1382 | const Expr *Exp, const NamedDecl *D, | |||
1383 | const CFGBlock *PredBlock, | |||
1384 | const CFGBlock *CurrBlock, | |||
1385 | Expr *BrE, bool Neg) { | |||
1386 | // Find out which branch has the lock | |||
1387 | bool branch = false; | |||
1388 | if (const auto *BLE = dyn_cast_or_null<CXXBoolLiteralExpr>(BrE)) | |||
1389 | branch = BLE->getValue(); | |||
1390 | else if (const auto *ILE = dyn_cast_or_null<IntegerLiteral>(BrE)) | |||
1391 | branch = ILE->getValue().getBoolValue(); | |||
1392 | ||||
1393 | int branchnum = branch ? 0 : 1; | |||
1394 | if (Neg) | |||
1395 | branchnum = !branchnum; | |||
1396 | ||||
1397 | // If we've taken the trylock branch, then add the lock | |||
1398 | int i = 0; | |||
1399 | for (CFGBlock::const_succ_iterator SI = PredBlock->succ_begin(), | |||
1400 | SE = PredBlock->succ_end(); SI != SE && i < 2; ++SI, ++i) { | |||
1401 | if (*SI == CurrBlock && i == branchnum) | |||
1402 | getMutexIDs(Mtxs, Attr, Exp, D); | |||
1403 | } | |||
1404 | } | |||
1405 | ||||
1406 | static bool getStaticBooleanValue(Expr *E, bool &TCond) { | |||
1407 | if (isa<CXXNullPtrLiteralExpr>(E) || isa<GNUNullExpr>(E)) { | |||
1408 | TCond = false; | |||
1409 | return true; | |||
1410 | } else if (const auto *BLE = dyn_cast<CXXBoolLiteralExpr>(E)) { | |||
1411 | TCond = BLE->getValue(); | |||
1412 | return true; | |||
1413 | } else if (const auto *ILE = dyn_cast<IntegerLiteral>(E)) { | |||
1414 | TCond = ILE->getValue().getBoolValue(); | |||
1415 | return true; | |||
1416 | } else if (auto *CE = dyn_cast<ImplicitCastExpr>(E)) | |||
1417 | return getStaticBooleanValue(CE->getSubExpr(), TCond); | |||
1418 | return false; | |||
1419 | } | |||
1420 | ||||
1421 | // If Cond can be traced back to a function call, return the call expression. | |||
1422 | // The negate variable should be called with false, and will be set to true | |||
1423 | // if the function call is negated, e.g. if (!mu.tryLock(...)) | |||
1424 | const CallExpr* ThreadSafetyAnalyzer::getTrylockCallExpr(const Stmt *Cond, | |||
1425 | LocalVarContext C, | |||
1426 | bool &Negate) { | |||
1427 | if (!Cond) | |||
1428 | return nullptr; | |||
1429 | ||||
1430 | if (const auto *CallExp = dyn_cast<CallExpr>(Cond)) { | |||
1431 | if (CallExp->getBuiltinCallee() == Builtin::BI__builtin_expect) | |||
1432 | return getTrylockCallExpr(CallExp->getArg(0), C, Negate); | |||
1433 | return CallExp; | |||
1434 | } | |||
1435 | else if (const auto *PE = dyn_cast<ParenExpr>(Cond)) | |||
1436 | return getTrylockCallExpr(PE->getSubExpr(), C, Negate); | |||
1437 | else if (const auto *CE = dyn_cast<ImplicitCastExpr>(Cond)) | |||
1438 | return getTrylockCallExpr(CE->getSubExpr(), C, Negate); | |||
1439 | else if (const auto *FE = dyn_cast<FullExpr>(Cond)) | |||
1440 | return getTrylockCallExpr(FE->getSubExpr(), C, Negate); | |||
1441 | else if (const auto *DRE = dyn_cast<DeclRefExpr>(Cond)) { | |||
1442 | const Expr *E = LocalVarMap.lookupExpr(DRE->getDecl(), C); | |||
1443 | return getTrylockCallExpr(E, C, Negate); | |||
1444 | } | |||
1445 | else if (const auto *UOP = dyn_cast<UnaryOperator>(Cond)) { | |||
1446 | if (UOP->getOpcode() == UO_LNot) { | |||
1447 | Negate = !Negate; | |||
1448 | return getTrylockCallExpr(UOP->getSubExpr(), C, Negate); | |||
1449 | } | |||
1450 | return nullptr; | |||
1451 | } | |||
1452 | else if (const auto *BOP = dyn_cast<BinaryOperator>(Cond)) { | |||
1453 | if (BOP->getOpcode() == BO_EQ || BOP->getOpcode() == BO_NE) { | |||
1454 | if (BOP->getOpcode() == BO_NE) | |||
1455 | Negate = !Negate; | |||
1456 | ||||
1457 | bool TCond = false; | |||
1458 | if (getStaticBooleanValue(BOP->getRHS(), TCond)) { | |||
1459 | if (!TCond) Negate = !Negate; | |||
1460 | return getTrylockCallExpr(BOP->getLHS(), C, Negate); | |||
1461 | } | |||
1462 | TCond = false; | |||
1463 | if (getStaticBooleanValue(BOP->getLHS(), TCond)) { | |||
1464 | if (!TCond) Negate = !Negate; | |||
1465 | return getTrylockCallExpr(BOP->getRHS(), C, Negate); | |||
1466 | } | |||
1467 | return nullptr; | |||
1468 | } | |||
1469 | if (BOP->getOpcode() == BO_LAnd) { | |||
1470 | // LHS must have been evaluated in a different block. | |||
1471 | return getTrylockCallExpr(BOP->getRHS(), C, Negate); | |||
1472 | } | |||
1473 | if (BOP->getOpcode() == BO_LOr) | |||
1474 | return getTrylockCallExpr(BOP->getRHS(), C, Negate); | |||
1475 | return nullptr; | |||
1476 | } else if (const auto *COP = dyn_cast<ConditionalOperator>(Cond)) { | |||
1477 | bool TCond, FCond; | |||
1478 | if (getStaticBooleanValue(COP->getTrueExpr(), TCond) && | |||
1479 | getStaticBooleanValue(COP->getFalseExpr(), FCond)) { | |||
1480 | if (TCond && !FCond) | |||
1481 | return getTrylockCallExpr(COP->getCond(), C, Negate); | |||
1482 | if (!TCond && FCond) { | |||
1483 | Negate = !Negate; | |||
1484 | return getTrylockCallExpr(COP->getCond(), C, Negate); | |||
1485 | } | |||
1486 | } | |||
1487 | } | |||
1488 | return nullptr; | |||
1489 | } | |||
1490 | ||||
1491 | /// Find the lockset that holds on the edge between PredBlock | |||
1492 | /// and CurrBlock. The edge set is the exit set of PredBlock (passed | |||
1493 | /// as the ExitSet parameter) plus any trylocks, which are conditionally held. | |||
1494 | void ThreadSafetyAnalyzer::getEdgeLockset(FactSet& Result, | |||
1495 | const FactSet &ExitSet, | |||
1496 | const CFGBlock *PredBlock, | |||
1497 | const CFGBlock *CurrBlock) { | |||
1498 | Result = ExitSet; | |||
1499 | ||||
1500 | const Stmt *Cond = PredBlock->getTerminatorCondition(); | |||
1501 | // We don't acquire try-locks on ?: branches, only when its result is used. | |||
1502 | if (!Cond || isa<ConditionalOperator>(PredBlock->getTerminatorStmt())) | |||
1503 | return; | |||
1504 | ||||
1505 | bool Negate = false; | |||
1506 | const CFGBlockInfo *PredBlockInfo = &BlockInfo[PredBlock->getBlockID()]; | |||
1507 | const LocalVarContext &LVarCtx = PredBlockInfo->ExitContext; | |||
1508 | StringRef CapDiagKind = "mutex"; | |||
1509 | ||||
1510 | const auto *Exp = getTrylockCallExpr(Cond, LVarCtx, Negate); | |||
1511 | if (!Exp) | |||
1512 | return; | |||
1513 | ||||
1514 | auto *FunDecl = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); | |||
1515 | if(!FunDecl || !FunDecl->hasAttrs()) | |||
1516 | return; | |||
1517 | ||||
1518 | CapExprSet ExclusiveLocksToAdd; | |||
1519 | CapExprSet SharedLocksToAdd; | |||
1520 | ||||
1521 | // If the condition is a call to a Trylock function, then grab the attributes | |||
1522 | for (const auto *Attr : FunDecl->attrs()) { | |||
1523 | switch (Attr->getKind()) { | |||
1524 | case attr::TryAcquireCapability: { | |||
1525 | auto *A = cast<TryAcquireCapabilityAttr>(Attr); | |||
1526 | getMutexIDs(A->isShared() ? SharedLocksToAdd : ExclusiveLocksToAdd, A, | |||
1527 | Exp, FunDecl, PredBlock, CurrBlock, A->getSuccessValue(), | |||
1528 | Negate); | |||
1529 | CapDiagKind = ClassifyDiagnostic(A); | |||
1530 | break; | |||
1531 | }; | |||
1532 | case attr::ExclusiveTrylockFunction: { | |||
1533 | const auto *A = cast<ExclusiveTrylockFunctionAttr>(Attr); | |||
1534 | getMutexIDs(ExclusiveLocksToAdd, A, Exp, FunDecl, | |||
1535 | PredBlock, CurrBlock, A->getSuccessValue(), Negate); | |||
1536 | CapDiagKind = ClassifyDiagnostic(A); | |||
1537 | break; | |||
1538 | } | |||
1539 | case attr::SharedTrylockFunction: { | |||
1540 | const auto *A = cast<SharedTrylockFunctionAttr>(Attr); | |||
1541 | getMutexIDs(SharedLocksToAdd, A, Exp, FunDecl, | |||
1542 | PredBlock, CurrBlock, A->getSuccessValue(), Negate); | |||
1543 | CapDiagKind = ClassifyDiagnostic(A); | |||
1544 | break; | |||
1545 | } | |||
1546 | default: | |||
1547 | break; | |||
1548 | } | |||
1549 | } | |||
1550 | ||||
1551 | // Add and remove locks. | |||
1552 | SourceLocation Loc = Exp->getExprLoc(); | |||
1553 | for (const auto &ExclusiveLockToAdd : ExclusiveLocksToAdd) | |||
1554 | addLock(Result, llvm::make_unique<LockableFactEntry>(ExclusiveLockToAdd, | |||
1555 | LK_Exclusive, Loc), | |||
1556 | CapDiagKind); | |||
1557 | for (const auto &SharedLockToAdd : SharedLocksToAdd) | |||
1558 | addLock(Result, llvm::make_unique<LockableFactEntry>(SharedLockToAdd, | |||
1559 | LK_Shared, Loc), | |||
1560 | CapDiagKind); | |||
1561 | } | |||
1562 | ||||
1563 | namespace { | |||
1564 | ||||
1565 | /// We use this class to visit different types of expressions in | |||
1566 | /// CFGBlocks, and build up the lockset. | |||
1567 | /// An expression may cause us to add or remove locks from the lockset, or else | |||
1568 | /// output error messages related to missing locks. | |||
1569 | /// FIXME: In future, we may be able to not inherit from a visitor. | |||
1570 | class BuildLockset : public ConstStmtVisitor<BuildLockset> { | |||
1571 | friend class ThreadSafetyAnalyzer; | |||
1572 | ||||
1573 | ThreadSafetyAnalyzer *Analyzer; | |||
1574 | FactSet FSet; | |||
1575 | LocalVariableMap::Context LVarCtx; | |||
1576 | unsigned CtxIndex; | |||
1577 | ||||
1578 | // helper functions | |||
1579 | void warnIfMutexNotHeld(const NamedDecl *D, const Expr *Exp, AccessKind AK, | |||
1580 | Expr *MutexExp, ProtectedOperationKind POK, | |||
1581 | StringRef DiagKind, SourceLocation Loc); | |||
1582 | void warnIfMutexHeld(const NamedDecl *D, const Expr *Exp, Expr *MutexExp, | |||
1583 | StringRef DiagKind); | |||
1584 | ||||
1585 | void checkAccess(const Expr *Exp, AccessKind AK, | |||
1586 | ProtectedOperationKind POK = POK_VarAccess); | |||
1587 | void checkPtAccess(const Expr *Exp, AccessKind AK, | |||
1588 | ProtectedOperationKind POK = POK_VarAccess); | |||
1589 | ||||
1590 | void handleCall(const Expr *Exp, const NamedDecl *D, VarDecl *VD = nullptr); | |||
1591 | void examineArguments(const FunctionDecl *FD, | |||
1592 | CallExpr::const_arg_iterator ArgBegin, | |||
1593 | CallExpr::const_arg_iterator ArgEnd, | |||
1594 | bool SkipFirstParam = false); | |||
1595 | ||||
1596 | public: | |||
1597 | BuildLockset(ThreadSafetyAnalyzer *Anlzr, CFGBlockInfo &Info) | |||
1598 | : ConstStmtVisitor<BuildLockset>(), Analyzer(Anlzr), FSet(Info.EntrySet), | |||
1599 | LVarCtx(Info.EntryContext), CtxIndex(Info.EntryIndex) {} | |||
1600 | ||||
1601 | void VisitUnaryOperator(const UnaryOperator *UO); | |||
1602 | void VisitBinaryOperator(const BinaryOperator *BO); | |||
1603 | void VisitCastExpr(const CastExpr *CE); | |||
1604 | void VisitCallExpr(const CallExpr *Exp); | |||
1605 | void VisitCXXConstructExpr(const CXXConstructExpr *Exp); | |||
1606 | void VisitDeclStmt(const DeclStmt *S); | |||
1607 | }; | |||
1608 | ||||
1609 | } // namespace | |||
1610 | ||||
1611 | /// Warn if the LSet does not contain a lock sufficient to protect access | |||
1612 | /// of at least the passed in AccessKind. | |||
1613 | void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, const Expr *Exp, | |||
1614 | AccessKind AK, Expr *MutexExp, | |||
1615 | ProtectedOperationKind POK, | |||
1616 | StringRef DiagKind, SourceLocation Loc) { | |||
1617 | LockKind LK = getLockKindFromAccessKind(AK); | |||
1618 | ||||
1619 | CapabilityExpr Cp = Analyzer->SxBuilder.translateAttrExpr(MutexExp, D, Exp); | |||
1620 | if (Cp.isInvalid()) { | |||
1621 | warnInvalidLock(Analyzer->Handler, MutexExp, D, Exp, DiagKind); | |||
1622 | return; | |||
1623 | } else if (Cp.shouldIgnore()) { | |||
1624 | return; | |||
1625 | } | |||
1626 | ||||
1627 | if (Cp.negative()) { | |||
1628 | // Negative capabilities act like locks excluded | |||
1629 | const FactEntry *LDat = FSet.findLock(Analyzer->FactMan, !Cp); | |||
1630 | if (LDat) { | |||
1631 | Analyzer->Handler.handleFunExcludesLock( | |||
1632 | DiagKind, D->getNameAsString(), (!Cp).toString(), Loc); | |||
1633 | return; | |||
1634 | } | |||
1635 | ||||
1636 | // If this does not refer to a negative capability in the same class, | |||
1637 | // then stop here. | |||
1638 | if (!Analyzer->inCurrentScope(Cp)) | |||
1639 | return; | |||
1640 | ||||
1641 | // Otherwise the negative requirement must be propagated to the caller. | |||
1642 | LDat = FSet.findLock(Analyzer->FactMan, Cp); | |||
1643 | if (!LDat) { | |||
1644 | Analyzer->Handler.handleMutexNotHeld("", D, POK, Cp.toString(), | |||
1645 | LK_Shared, Loc); | |||
1646 | } | |||
1647 | return; | |||
1648 | } | |||
1649 | ||||
1650 | const FactEntry *LDat = FSet.findLockUniv(Analyzer->FactMan, Cp); | |||
1651 | bool NoError = true; | |||
1652 | if (!LDat) { | |||
1653 | // No exact match found. Look for a partial match. | |||
1654 | LDat = FSet.findPartialMatch(Analyzer->FactMan, Cp); | |||
1655 | if (LDat) { | |||
1656 | // Warn that there's no precise match. | |||
1657 | std::string PartMatchStr = LDat->toString(); | |||
1658 | StringRef PartMatchName(PartMatchStr); | |||
1659 | Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, Cp.toString(), | |||
1660 | LK, Loc, &PartMatchName); | |||
1661 | } else { | |||
1662 | // Warn that there's no match at all. | |||
1663 | Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, Cp.toString(), | |||
1664 | LK, Loc); | |||
1665 | } | |||
1666 | NoError = false; | |||
1667 | } | |||
1668 | // Make sure the mutex we found is the right kind. | |||
1669 | if (NoError && LDat && !LDat->isAtLeast(LK)) { | |||
1670 | Analyzer->Handler.handleMutexNotHeld(DiagKind, D, POK, Cp.toString(), | |||
1671 | LK, Loc); | |||
1672 | } | |||
1673 | } | |||
1674 | ||||
1675 | /// Warn if the LSet contains the given lock. | |||
1676 | void BuildLockset::warnIfMutexHeld(const NamedDecl *D, const Expr *Exp, | |||
1677 | Expr *MutexExp, StringRef DiagKind) { | |||
1678 | CapabilityExpr Cp = Analyzer->SxBuilder.translateAttrExpr(MutexExp, D, Exp); | |||
1679 | if (Cp.isInvalid()) { | |||
1680 | warnInvalidLock(Analyzer->Handler, MutexExp, D, Exp, DiagKind); | |||
1681 | return; | |||
1682 | } else if (Cp.shouldIgnore()) { | |||
1683 | return; | |||
1684 | } | |||
1685 | ||||
1686 | const FactEntry *LDat = FSet.findLock(Analyzer->FactMan, Cp); | |||
1687 | if (LDat) { | |||
1688 | Analyzer->Handler.handleFunExcludesLock( | |||
1689 | DiagKind, D->getNameAsString(), Cp.toString(), Exp->getExprLoc()); | |||
1690 | } | |||
1691 | } | |||
1692 | ||||
1693 | /// Checks guarded_by and pt_guarded_by attributes. | |||
1694 | /// Whenever we identify an access (read or write) to a DeclRefExpr that is | |||
1695 | /// marked with guarded_by, we must ensure the appropriate mutexes are held. | |||
1696 | /// Similarly, we check if the access is to an expression that dereferences | |||
1697 | /// a pointer marked with pt_guarded_by. | |||
1698 | void BuildLockset::checkAccess(const Expr *Exp, AccessKind AK, | |||
1699 | ProtectedOperationKind POK) { | |||
1700 | Exp = Exp->IgnoreImplicit()->IgnoreParenCasts(); | |||
1701 | ||||
1702 | SourceLocation Loc = Exp->getExprLoc(); | |||
1703 | ||||
1704 | // Local variables of reference type cannot be re-assigned; | |||
1705 | // map them to their initializer. | |||
1706 | while (const auto *DRE = dyn_cast<DeclRefExpr>(Exp)) { | |||
1707 | const auto *VD = dyn_cast<VarDecl>(DRE->getDecl()->getCanonicalDecl()); | |||
1708 | if (VD && VD->isLocalVarDecl() && VD->getType()->isReferenceType()) { | |||
1709 | if (const auto *E = VD->getInit()) { | |||
1710 | // Guard against self-initialization. e.g., int &i = i; | |||
1711 | if (E == Exp) | |||
1712 | break; | |||
1713 | Exp = E; | |||
1714 | continue; | |||
1715 | } | |||
1716 | } | |||
1717 | break; | |||
1718 | } | |||
1719 | ||||
1720 | if (const auto *UO = dyn_cast<UnaryOperator>(Exp)) { | |||
1721 | // For dereferences | |||
1722 | if (UO->getOpcode() == UO_Deref) | |||
1723 | checkPtAccess(UO->getSubExpr(), AK, POK); | |||
1724 | return; | |||
1725 | } | |||
1726 | ||||
1727 | if (const auto *AE = dyn_cast<ArraySubscriptExpr>(Exp)) { | |||
1728 | checkPtAccess(AE->getLHS(), AK, POK); | |||
1729 | return; | |||
1730 | } | |||
1731 | ||||
1732 | if (const auto *ME = dyn_cast<MemberExpr>(Exp)) { | |||
1733 | if (ME->isArrow()) | |||
1734 | checkPtAccess(ME->getBase(), AK, POK); | |||
1735 | else | |||
1736 | checkAccess(ME->getBase(), AK, POK); | |||
1737 | } | |||
1738 | ||||
1739 | const ValueDecl *D = getValueDecl(Exp); | |||
1740 | if (!D || !D->hasAttrs()) | |||
1741 | return; | |||
1742 | ||||
1743 | if (D->hasAttr<GuardedVarAttr>() && FSet.isEmpty(Analyzer->FactMan)) { | |||
1744 | Analyzer->Handler.handleNoMutexHeld("mutex", D, POK, AK, Loc); | |||
1745 | } | |||
1746 | ||||
1747 | for (const auto *I : D->specific_attrs<GuardedByAttr>()) | |||
1748 | warnIfMutexNotHeld(D, Exp, AK, I->getArg(), POK, | |||
1749 | ClassifyDiagnostic(I), Loc); | |||
1750 | } | |||
1751 | ||||
1752 | /// Checks pt_guarded_by and pt_guarded_var attributes. | |||
1753 | /// POK is the same operationKind that was passed to checkAccess. | |||
1754 | void BuildLockset::checkPtAccess(const Expr *Exp, AccessKind AK, | |||
1755 | ProtectedOperationKind POK) { | |||
1756 | while (true) { | |||
1757 | if (const auto *PE = dyn_cast<ParenExpr>(Exp)) { | |||
1758 | Exp = PE->getSubExpr(); | |||
1759 | continue; | |||
1760 | } | |||
1761 | if (const auto *CE = dyn_cast<CastExpr>(Exp)) { | |||
1762 | if (CE->getCastKind() == CK_ArrayToPointerDecay) { | |||
1763 | // If it's an actual array, and not a pointer, then it's elements | |||
1764 | // are protected by GUARDED_BY, not PT_GUARDED_BY; | |||
1765 | checkAccess(CE->getSubExpr(), AK, POK); | |||
1766 | return; | |||
1767 | } | |||
1768 | Exp = CE->getSubExpr(); | |||
1769 | continue; | |||
1770 | } | |||
1771 | break; | |||
1772 | } | |||
1773 | ||||
1774 | // Pass by reference warnings are under a different flag. | |||
1775 | ProtectedOperationKind PtPOK = POK_VarDereference; | |||
1776 | if (POK == POK_PassByRef) PtPOK = POK_PtPassByRef; | |||
1777 | ||||
1778 | const ValueDecl *D = getValueDecl(Exp); | |||
1779 | if (!D || !D->hasAttrs()) | |||
1780 | return; | |||
1781 | ||||
1782 | if (D->hasAttr<PtGuardedVarAttr>() && FSet.isEmpty(Analyzer->FactMan)) | |||
1783 | Analyzer->Handler.handleNoMutexHeld("mutex", D, PtPOK, AK, | |||
1784 | Exp->getExprLoc()); | |||
1785 | ||||
1786 | for (auto const *I : D->specific_attrs<PtGuardedByAttr>()) | |||
1787 | warnIfMutexNotHeld(D, Exp, AK, I->getArg(), PtPOK, | |||
1788 | ClassifyDiagnostic(I), Exp->getExprLoc()); | |||
1789 | } | |||
1790 | ||||
1791 | /// Process a function call, method call, constructor call, | |||
1792 | /// or destructor call. This involves looking at the attributes on the | |||
1793 | /// corresponding function/method/constructor/destructor, issuing warnings, | |||
1794 | /// and updating the locksets accordingly. | |||
1795 | /// | |||
1796 | /// FIXME: For classes annotated with one of the guarded annotations, we need | |||
1797 | /// to treat const method calls as reads and non-const method calls as writes, | |||
1798 | /// and check that the appropriate locks are held. Non-const method calls with | |||
1799 | /// the same signature as const method calls can be also treated as reads. | |||
1800 | /// | |||
1801 | void BuildLockset::handleCall(const Expr *Exp, const NamedDecl *D, | |||
1802 | VarDecl *VD) { | |||
1803 | SourceLocation Loc = Exp->getExprLoc(); | |||
1804 | CapExprSet ExclusiveLocksToAdd, SharedLocksToAdd; | |||
1805 | CapExprSet ExclusiveLocksToRemove, SharedLocksToRemove, GenericLocksToRemove; | |||
1806 | CapExprSet ScopedExclusiveReqs, ScopedSharedReqs; | |||
1807 | StringRef CapDiagKind = "mutex"; | |||
1808 | ||||
1809 | // Figure out if we're constructing an object of scoped lockable class | |||
1810 | bool isScopedVar = false; | |||
1811 | if (VD) { | |||
1812 | if (const auto *CD = dyn_cast<const CXXConstructorDecl>(D)) { | |||
1813 | const CXXRecordDecl* PD = CD->getParent(); | |||
1814 | if (PD && PD->hasAttr<ScopedLockableAttr>()) | |||
1815 | isScopedVar = true; | |||
1816 | } | |||
1817 | } | |||
1818 | ||||
1819 | for(const Attr *At : D->attrs()) { | |||
1820 | switch (At->getKind()) { | |||
1821 | // When we encounter a lock function, we need to add the lock to our | |||
1822 | // lockset. | |||
1823 | case attr::AcquireCapability: { | |||
1824 | const auto *A = cast<AcquireCapabilityAttr>(At); | |||
1825 | Analyzer->getMutexIDs(A->isShared() ? SharedLocksToAdd | |||
1826 | : ExclusiveLocksToAdd, | |||
1827 | A, Exp, D, VD); | |||
1828 | ||||
1829 | CapDiagKind = ClassifyDiagnostic(A); | |||
1830 | break; | |||
1831 | } | |||
1832 | ||||
1833 | // An assert will add a lock to the lockset, but will not generate | |||
1834 | // a warning if it is already there, and will not generate a warning | |||
1835 | // if it is not removed. | |||
1836 | case attr::AssertExclusiveLock: { | |||
1837 | const auto *A = cast<AssertExclusiveLockAttr>(At); | |||
1838 | ||||
1839 | CapExprSet AssertLocks; | |||
1840 | Analyzer->getMutexIDs(AssertLocks, A, Exp, D, VD); | |||
1841 | for (const auto &AssertLock : AssertLocks) | |||
1842 | Analyzer->addLock(FSet, | |||
1843 | llvm::make_unique<LockableFactEntry>( | |||
1844 | AssertLock, LK_Exclusive, Loc, false, true), | |||
1845 | ClassifyDiagnostic(A)); | |||
1846 | break; | |||
1847 | } | |||
1848 | case attr::AssertSharedLock: { | |||
1849 | const auto *A = cast<AssertSharedLockAttr>(At); | |||
1850 | ||||
1851 | CapExprSet AssertLocks; | |||
1852 | Analyzer->getMutexIDs(AssertLocks, A, Exp, D, VD); | |||
1853 | for (const auto &AssertLock : AssertLocks) | |||
1854 | Analyzer->addLock(FSet, | |||
1855 | llvm::make_unique<LockableFactEntry>( | |||
1856 | AssertLock, LK_Shared, Loc, false, true), | |||
1857 | ClassifyDiagnostic(A)); | |||
1858 | break; | |||
1859 | } | |||
1860 | ||||
1861 | case attr::AssertCapability: { | |||
1862 | const auto *A = cast<AssertCapabilityAttr>(At); | |||
1863 | CapExprSet AssertLocks; | |||
1864 | Analyzer->getMutexIDs(AssertLocks, A, Exp, D, VD); | |||
1865 | for (const auto &AssertLock : AssertLocks) | |||
1866 | Analyzer->addLock(FSet, | |||
1867 | llvm::make_unique<LockableFactEntry>( | |||
1868 | AssertLock, | |||
1869 | A->isShared() ? LK_Shared : LK_Exclusive, Loc, | |||
1870 | false, true), | |||
1871 | ClassifyDiagnostic(A)); | |||
1872 | break; | |||
1873 | } | |||
1874 | ||||
1875 | // When we encounter an unlock function, we need to remove unlocked | |||
1876 | // mutexes from the lockset, and flag a warning if they are not there. | |||
1877 | case attr::ReleaseCapability: { | |||
1878 | const auto *A = cast<ReleaseCapabilityAttr>(At); | |||
1879 | if (A->isGeneric()) | |||
1880 | Analyzer->getMutexIDs(GenericLocksToRemove, A, Exp, D, VD); | |||
1881 | else if (A->isShared()) | |||
1882 | Analyzer->getMutexIDs(SharedLocksToRemove, A, Exp, D, VD); | |||
1883 | else | |||
1884 | Analyzer->getMutexIDs(ExclusiveLocksToRemove, A, Exp, D, VD); | |||
1885 | ||||
1886 | CapDiagKind = ClassifyDiagnostic(A); | |||
1887 | break; | |||
1888 | } | |||
1889 | ||||
1890 | case attr::RequiresCapability: { | |||
1891 | const auto *A = cast<RequiresCapabilityAttr>(At); | |||
1892 | for (auto *Arg : A->args()) { | |||
1893 | warnIfMutexNotHeld(D, Exp, A->isShared() ? AK_Read : AK_Written, Arg, | |||
1894 | POK_FunctionCall, ClassifyDiagnostic(A), | |||
1895 | Exp->getExprLoc()); | |||
1896 | // use for adopting a lock | |||
1897 | if (isScopedVar) { | |||
1898 | Analyzer->getMutexIDs(A->isShared() ? ScopedSharedReqs | |||
1899 | : ScopedExclusiveReqs, | |||
1900 | A, Exp, D, VD); | |||
1901 | } | |||
1902 | } | |||
1903 | break; | |||
1904 | } | |||
1905 | ||||
1906 | case attr::LocksExcluded: { | |||
1907 | const auto *A = cast<LocksExcludedAttr>(At); | |||
1908 | for (auto *Arg : A->args()) | |||
1909 | warnIfMutexHeld(D, Exp, Arg, ClassifyDiagnostic(A)); | |||
1910 | break; | |||
1911 | } | |||
1912 | ||||
1913 | // Ignore attributes unrelated to thread-safety | |||
1914 | default: | |||
1915 | break; | |||
1916 | } | |||
1917 | } | |||
1918 | ||||
1919 | // Remove locks first to allow lock upgrading/downgrading. | |||
1920 | // FIXME -- should only fully remove if the attribute refers to 'this'. | |||
1921 | bool Dtor = isa<CXXDestructorDecl>(D); | |||
1922 | for (const auto &M : ExclusiveLocksToRemove) | |||
1923 | Analyzer->removeLock(FSet, M, Loc, Dtor, LK_Exclusive, CapDiagKind); | |||
1924 | for (const auto &M : SharedLocksToRemove) | |||
1925 | Analyzer->removeLock(FSet, M, Loc, Dtor, LK_Shared, CapDiagKind); | |||
1926 | for (const auto &M : GenericLocksToRemove) | |||
1927 | Analyzer->removeLock(FSet, M, Loc, Dtor, LK_Generic, CapDiagKind); | |||
1928 | ||||
1929 | // Add locks. | |||
1930 | for (const auto &M : ExclusiveLocksToAdd) | |||
1931 | Analyzer->addLock(FSet, llvm::make_unique<LockableFactEntry>( | |||
1932 | M, LK_Exclusive, Loc, isScopedVar), | |||
1933 | CapDiagKind); | |||
1934 | for (const auto &M : SharedLocksToAdd) | |||
1935 | Analyzer->addLock(FSet, llvm::make_unique<LockableFactEntry>( | |||
1936 | M, LK_Shared, Loc, isScopedVar), | |||
1937 | CapDiagKind); | |||
1938 | ||||
1939 | if (isScopedVar) { | |||
1940 | // Add the managing object as a dummy mutex, mapped to the underlying mutex. | |||
1941 | SourceLocation MLoc = VD->getLocation(); | |||
1942 | DeclRefExpr DRE(VD->getASTContext(), VD, false, VD->getType(), VK_LValue, | |||
1943 | VD->getLocation()); | |||
1944 | // FIXME: does this store a pointer to DRE? | |||
1945 | CapabilityExpr Scp = Analyzer->SxBuilder.translateAttrExpr(&DRE, nullptr); | |||
1946 | ||||
1947 | auto ScopedEntry = llvm::make_unique<ScopedLockableFactEntry>(Scp, MLoc); | |||
1948 | for (const auto &M : ExclusiveLocksToAdd) | |||
1949 | ScopedEntry->addExclusiveLock(M); | |||
1950 | for (const auto &M : ScopedExclusiveReqs) | |||
1951 | ScopedEntry->addExclusiveLock(M); | |||
1952 | for (const auto &M : SharedLocksToAdd) | |||
1953 | ScopedEntry->addSharedLock(M); | |||
1954 | for (const auto &M : ScopedSharedReqs) | |||
1955 | ScopedEntry->addSharedLock(M); | |||
1956 | for (const auto &M : ExclusiveLocksToRemove) | |||
1957 | ScopedEntry->addExclusiveUnlock(M); | |||
1958 | for (const auto &M : SharedLocksToRemove) | |||
1959 | ScopedEntry->addSharedUnlock(M); | |||
1960 | Analyzer->addLock(FSet, std::move(ScopedEntry), CapDiagKind); | |||
1961 | } | |||
1962 | } | |||
1963 | ||||
1964 | /// For unary operations which read and write a variable, we need to | |||
1965 | /// check whether we hold any required mutexes. Reads are checked in | |||
1966 | /// VisitCastExpr. | |||
1967 | void BuildLockset::VisitUnaryOperator(const UnaryOperator *UO) { | |||
1968 | switch (UO->getOpcode()) { | |||
1969 | case UO_PostDec: | |||
1970 | case UO_PostInc: | |||
1971 | case UO_PreDec: | |||
1972 | case UO_PreInc: | |||
1973 | checkAccess(UO->getSubExpr(), AK_Written); | |||
1974 | break; | |||
1975 | default: | |||
1976 | break; | |||
1977 | } | |||
1978 | } | |||
1979 | ||||
1980 | /// For binary operations which assign to a variable (writes), we need to check | |||
1981 | /// whether we hold any required mutexes. | |||
1982 | /// FIXME: Deal with non-primitive types. | |||
1983 | void BuildLockset::VisitBinaryOperator(const BinaryOperator *BO) { | |||
1984 | if (!BO->isAssignmentOp()) | |||
1985 | return; | |||
1986 | ||||
1987 | // adjust the context | |||
1988 | LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, BO, LVarCtx); | |||
1989 | ||||
1990 | checkAccess(BO->getLHS(), AK_Written); | |||
1991 | } | |||
1992 | ||||
1993 | /// Whenever we do an LValue to Rvalue cast, we are reading a variable and | |||
1994 | /// need to ensure we hold any required mutexes. | |||
1995 | /// FIXME: Deal with non-primitive types. | |||
1996 | void BuildLockset::VisitCastExpr(const CastExpr *CE) { | |||
1997 | if (CE->getCastKind() != CK_LValueToRValue) | |||
1998 | return; | |||
1999 | checkAccess(CE->getSubExpr(), AK_Read); | |||
2000 | } | |||
2001 | ||||
2002 | void BuildLockset::examineArguments(const FunctionDecl *FD, | |||
2003 | CallExpr::const_arg_iterator ArgBegin, | |||
2004 | CallExpr::const_arg_iterator ArgEnd, | |||
2005 | bool SkipFirstParam) { | |||
2006 | // Currently we can't do anything if we don't know the function declaration. | |||
2007 | if (!FD) | |||
2008 | return; | |||
2009 | ||||
2010 | // NO_THREAD_SAFETY_ANALYSIS does double duty here. Normally it | |||
2011 | // only turns off checking within the body of a function, but we also | |||
2012 | // use it to turn off checking in arguments to the function. This | |||
2013 | // could result in some false negatives, but the alternative is to | |||
2014 | // create yet another attribute. | |||
2015 | if (FD->hasAttr<NoThreadSafetyAnalysisAttr>()) | |||
2016 | return; | |||
2017 | ||||
2018 | const ArrayRef<ParmVarDecl *> Params = FD->parameters(); | |||
2019 | auto Param = Params.begin(); | |||
2020 | if (SkipFirstParam) | |||
2021 | ++Param; | |||
2022 | ||||
2023 | // There can be default arguments, so we stop when one iterator is at end(). | |||
2024 | for (auto Arg = ArgBegin; Param != Params.end() && Arg != ArgEnd; | |||
2025 | ++Param, ++Arg) { | |||
2026 | QualType Qt = (*Param)->getType(); | |||
2027 | if (Qt->isReferenceType()) | |||
2028 | checkAccess(*Arg, AK_Read, POK_PassByRef); | |||
2029 | } | |||
2030 | } | |||
2031 | ||||
2032 | void BuildLockset::VisitCallExpr(const CallExpr *Exp) { | |||
2033 | if (const auto *CE = dyn_cast<CXXMemberCallExpr>(Exp)) { | |||
2034 | const auto *ME = dyn_cast<MemberExpr>(CE->getCallee()); | |||
2035 | // ME can be null when calling a method pointer | |||
2036 | const CXXMethodDecl *MD = CE->getMethodDecl(); | |||
2037 | ||||
2038 | if (ME && MD) { | |||
2039 | if (ME->isArrow()) { | |||
2040 | if (MD->isConst()) | |||
2041 | checkPtAccess(CE->getImplicitObjectArgument(), AK_Read); | |||
2042 | else // FIXME -- should be AK_Written | |||
2043 | checkPtAccess(CE->getImplicitObjectArgument(), AK_Read); | |||
2044 | } else { | |||
2045 | if (MD->isConst()) | |||
2046 | checkAccess(CE->getImplicitObjectArgument(), AK_Read); | |||
2047 | else // FIXME -- should be AK_Written | |||
2048 | checkAccess(CE->getImplicitObjectArgument(), AK_Read); | |||
2049 | } | |||
2050 | } | |||
2051 | ||||
2052 | examineArguments(CE->getDirectCallee(), CE->arg_begin(), CE->arg_end()); | |||
2053 | } else if (const auto *OE = dyn_cast<CXXOperatorCallExpr>(Exp)) { | |||
2054 | auto OEop = OE->getOperator(); | |||
2055 | switch (OEop) { | |||
2056 | case OO_Equal: { | |||
2057 | const Expr *Target = OE->getArg(0); | |||
2058 | const Expr *Source = OE->getArg(1); | |||
2059 | checkAccess(Target, AK_Written); | |||
2060 | checkAccess(Source, AK_Read); | |||
2061 | break; | |||
2062 | } | |||
2063 | case OO_Star: | |||
2064 | case OO_Arrow: | |||
2065 | case OO_Subscript: | |||
2066 | if (!(OEop == OO_Star && OE->getNumArgs() > 1)) { | |||
2067 | // Grrr. operator* can be multiplication... | |||
2068 | checkPtAccess(OE->getArg(0), AK_Read); | |||
2069 | } | |||
2070 | LLVM_FALLTHROUGH[[clang::fallthrough]]; | |||
2071 | default: { | |||
2072 | // TODO: get rid of this, and rely on pass-by-ref instead. | |||
2073 | const Expr *Obj = OE->getArg(0); | |||
2074 | checkAccess(Obj, AK_Read); | |||
2075 | // Check the remaining arguments. For method operators, the first | |||
2076 | // argument is the implicit self argument, and doesn't appear in the | |||
2077 | // FunctionDecl, but for non-methods it does. | |||
2078 | const FunctionDecl *FD = OE->getDirectCallee(); | |||
2079 | examineArguments(FD, std::next(OE->arg_begin()), OE->arg_end(), | |||
2080 | /*SkipFirstParam*/ !isa<CXXMethodDecl>(FD)); | |||
2081 | break; | |||
2082 | } | |||
2083 | } | |||
2084 | } else { | |||
2085 | examineArguments(Exp->getDirectCallee(), Exp->arg_begin(), Exp->arg_end()); | |||
2086 | } | |||
2087 | ||||
2088 | auto *D = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); | |||
2089 | if(!D || !D->hasAttrs()) | |||
2090 | return; | |||
2091 | handleCall(Exp, D); | |||
2092 | } | |||
2093 | ||||
2094 | void BuildLockset::VisitCXXConstructExpr(const CXXConstructExpr *Exp) { | |||
2095 | const CXXConstructorDecl *D = Exp->getConstructor(); | |||
2096 | if (D && D->isCopyConstructor()) { | |||
2097 | const Expr* Source = Exp->getArg(0); | |||
2098 | checkAccess(Source, AK_Read); | |||
2099 | } else { | |||
2100 | examineArguments(D, Exp->arg_begin(), Exp->arg_end()); | |||
2101 | } | |||
2102 | } | |||
2103 | ||||
2104 | static CXXConstructorDecl * | |||
2105 | findConstructorForByValueReturn(const CXXRecordDecl *RD) { | |||
2106 | // Prefer a move constructor over a copy constructor. If there's more than | |||
2107 | // one copy constructor or more than one move constructor, we arbitrarily | |||
2108 | // pick the first declared such constructor rather than trying to guess which | |||
2109 | // one is more appropriate. | |||
2110 | CXXConstructorDecl *CopyCtor = nullptr; | |||
2111 | for (auto *Ctor : RD->ctors()) { | |||
2112 | if (Ctor->isDeleted()) | |||
2113 | continue; | |||
2114 | if (Ctor->isMoveConstructor()) | |||
2115 | return Ctor; | |||
2116 | if (!CopyCtor && Ctor->isCopyConstructor()) | |||
2117 | CopyCtor = Ctor; | |||
2118 | } | |||
2119 | return CopyCtor; | |||
2120 | } | |||
2121 | ||||
2122 | static Expr *buildFakeCtorCall(CXXConstructorDecl *CD, ArrayRef<Expr *> Args, | |||
2123 | SourceLocation Loc) { | |||
2124 | ASTContext &Ctx = CD->getASTContext(); | |||
2125 | return CXXConstructExpr::Create(Ctx, Ctx.getRecordType(CD->getParent()), Loc, | |||
2126 | CD, true, Args, false, false, false, false, | |||
2127 | CXXConstructExpr::CK_Complete, | |||
2128 | SourceRange(Loc, Loc)); | |||
2129 | } | |||
2130 | ||||
2131 | void BuildLockset::VisitDeclStmt(const DeclStmt *S) { | |||
2132 | // adjust the context | |||
2133 | LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, S, LVarCtx); | |||
2134 | ||||
2135 | for (auto *D : S->getDeclGroup()) { | |||
2136 | if (auto *VD = dyn_cast_or_null<VarDecl>(D)) { | |||
2137 | Expr *E = VD->getInit(); | |||
2138 | if (!E) | |||
2139 | continue; | |||
2140 | E = E->IgnoreParens(); | |||
2141 | ||||
2142 | // handle constructors that involve temporaries | |||
2143 | if (auto *EWC = dyn_cast<ExprWithCleanups>(E)) | |||
2144 | E = EWC->getSubExpr(); | |||
2145 | if (auto *BTE = dyn_cast<CXXBindTemporaryExpr>(E)) | |||
2146 | E = BTE->getSubExpr(); | |||
2147 | ||||
2148 | if (const auto *CE = dyn_cast<CXXConstructExpr>(E)) { | |||
2149 | const auto *CtorD = dyn_cast_or_null<NamedDecl>(CE->getConstructor()); | |||
2150 | if (!CtorD || !CtorD->hasAttrs()) | |||
2151 | continue; | |||
2152 | handleCall(E, CtorD, VD); | |||
2153 | } else if (isa<CallExpr>(E) && E->isRValue()) { | |||
2154 | // If the object is initialized by a function call that returns a | |||
2155 | // scoped lockable by value, use the attributes on the copy or move | |||
2156 | // constructor to figure out what effect that should have on the | |||
2157 | // lockset. | |||
2158 | // FIXME: Is this really the best way to handle this situation? | |||
2159 | auto *RD = E->getType()->getAsCXXRecordDecl(); | |||
2160 | if (!RD || !RD->hasAttr<ScopedLockableAttr>()) | |||
2161 | continue; | |||
2162 | CXXConstructorDecl *CtorD = findConstructorForByValueReturn(RD); | |||
2163 | if (!CtorD || !CtorD->hasAttrs()) | |||
2164 | continue; | |||
2165 | handleCall(buildFakeCtorCall(CtorD, {E}, E->getBeginLoc()), CtorD, VD); | |||
2166 | } | |||
2167 | } | |||
2168 | } | |||
2169 | } | |||
2170 | ||||
2171 | /// Compute the intersection of two locksets and issue warnings for any | |||
2172 | /// locks in the symmetric difference. | |||
2173 | /// | |||
2174 | /// This function is used at a merge point in the CFG when comparing the lockset | |||
2175 | /// of each branch being merged. For example, given the following sequence: | |||
2176 | /// A; if () then B; else C; D; we need to check that the lockset after B and C | |||
2177 | /// are the same. In the event of a difference, we use the intersection of these | |||
2178 | /// two locksets at the start of D. | |||
2179 | /// | |||
2180 | /// \param FSet1 The first lockset. | |||
2181 | /// \param FSet2 The second lockset. | |||
2182 | /// \param JoinLoc The location of the join point for error reporting | |||
2183 | /// \param LEK1 The error message to report if a mutex is missing from LSet1 | |||
2184 | /// \param LEK2 The error message to report if a mutex is missing from Lset2 | |||
2185 | void ThreadSafetyAnalyzer::intersectAndWarn(FactSet &FSet1, | |||
2186 | const FactSet &FSet2, | |||
2187 | SourceLocation JoinLoc, | |||
2188 | LockErrorKind LEK1, | |||
2189 | LockErrorKind LEK2, | |||
2190 | bool Modify) { | |||
2191 | FactSet FSet1Orig = FSet1; | |||
2192 | ||||
2193 | // Find locks in FSet2 that conflict or are not in FSet1, and warn. | |||
2194 | for (const auto &Fact : FSet2) { | |||
2195 | const FactEntry *LDat1 = nullptr; | |||
2196 | const FactEntry *LDat2 = &FactMan[Fact]; | |||
2197 | FactSet::iterator Iter1 = FSet1.findLockIter(FactMan, *LDat2); | |||
2198 | if (Iter1 != FSet1.end()) LDat1 = &FactMan[*Iter1]; | |||
2199 | ||||
2200 | if (LDat1) { | |||
2201 | if (LDat1->kind() != LDat2->kind()) { | |||
2202 | Handler.handleExclusiveAndShared("mutex", LDat2->toString(), | |||
2203 | LDat2->loc(), LDat1->loc()); | |||
2204 | if (Modify && LDat1->kind() != LK_Exclusive) { | |||
2205 | // Take the exclusive lock, which is the one in FSet2. | |||
2206 | *Iter1 = Fact; | |||
2207 | } | |||
2208 | } | |||
2209 | else if (Modify && LDat1->asserted() && !LDat2->asserted()) { | |||
2210 | // The non-asserted lock in FSet2 is the one we want to track. | |||
2211 | *Iter1 = Fact; | |||
2212 | } | |||
2213 | } else { | |||
2214 | LDat2->handleRemovalFromIntersection(FSet2, FactMan, JoinLoc, LEK1, | |||
2215 | Handler); | |||
2216 | } | |||
2217 | } | |||
2218 | ||||
2219 | // Find locks in FSet1 that are not in FSet2, and remove them. | |||
2220 | for (const auto &Fact : FSet1Orig) { | |||
2221 | const FactEntry *LDat1 = &FactMan[Fact]; | |||
2222 | const FactEntry *LDat2 = FSet2.findLock(FactMan, *LDat1); | |||
2223 | ||||
2224 | if (!LDat2) { | |||
2225 | LDat1->handleRemovalFromIntersection(FSet1Orig, FactMan, JoinLoc, LEK2, | |||
2226 | Handler); | |||
2227 | if (Modify) | |||
2228 | FSet1.removeLock(FactMan, *LDat1); | |||
2229 | } | |||
2230 | } | |||
2231 | } | |||
2232 | ||||
2233 | // Return true if block B never continues to its successors. | |||
2234 | static bool neverReturns(const CFGBlock *B) { | |||
2235 | if (B->hasNoReturnElement()) | |||
2236 | return true; | |||
2237 | if (B->empty()) | |||
2238 | return false; | |||
2239 | ||||
2240 | CFGElement Last = B->back(); | |||
2241 | if (Optional<CFGStmt> S = Last.getAs<CFGStmt>()) { | |||
2242 | if (isa<CXXThrowExpr>(S->getStmt())) | |||
2243 | return true; | |||
2244 | } | |||
2245 | return false; | |||
2246 | } | |||
2247 | ||||
2248 | /// Check a function's CFG for thread-safety violations. | |||
2249 | /// | |||
2250 | /// We traverse the blocks in the CFG, compute the set of mutexes that are held | |||
2251 | /// at the end of each block, and issue warnings for thread safety violations. | |||
2252 | /// Each block in the CFG is traversed exactly once. | |||
2253 | void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { | |||
2254 | // TODO: this whole function needs be rewritten as a visitor for CFGWalker. | |||
2255 | // For now, we just use the walker to set things up. | |||
2256 | threadSafety::CFGWalker walker; | |||
2257 | if (!walker.init(AC)) | |||
2258 | return; | |||
2259 | ||||
2260 | // AC.dumpCFG(true); | |||
2261 | // threadSafety::printSCFG(walker); | |||
2262 | ||||
2263 | CFG *CFGraph = walker.getGraph(); | |||
2264 | const NamedDecl *D = walker.getDecl(); | |||
2265 | const auto *CurrentFunction = dyn_cast<FunctionDecl>(D); | |||
2266 | CurrentMethod = dyn_cast<CXXMethodDecl>(D); | |||
2267 | ||||
2268 | if (D->hasAttr<NoThreadSafetyAnalysisAttr>()) | |||
2269 | return; | |||
2270 | ||||
2271 | // FIXME: Do something a bit more intelligent inside constructor and | |||
2272 | // destructor code. Constructors and destructors must assume unique access | |||
2273 | // to 'this', so checks on member variable access is disabled, but we should | |||
2274 | // still enable checks on other objects. | |||
2275 | if (isa<CXXConstructorDecl>(D)) | |||
2276 | return; // Don't check inside constructors. | |||
2277 | if (isa<CXXDestructorDecl>(D)) | |||
2278 | return; // Don't check inside destructors. | |||
2279 | ||||
2280 | Handler.enterFunction(CurrentFunction); | |||
2281 | ||||
2282 | BlockInfo.resize(CFGraph->getNumBlockIDs(), | |||
2283 | CFGBlockInfo::getEmptyBlockInfo(LocalVarMap)); | |||
2284 | ||||
2285 | // We need to explore the CFG via a "topological" ordering. | |||
2286 | // That way, we will be guaranteed to have information about required | |||
2287 | // predecessor locksets when exploring a new block. | |||
2288 | const PostOrderCFGView *SortedGraph = walker.getSortedGraph(); | |||
2289 | PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); | |||
2290 | ||||
2291 | // Mark entry block as reachable | |||
2292 | BlockInfo[CFGraph->getEntry().getBlockID()].Reachable = true; | |||
2293 | ||||
2294 | // Compute SSA names for local variables | |||
2295 | LocalVarMap.traverseCFG(CFGraph, SortedGraph, BlockInfo); | |||
2296 | ||||
2297 | // Fill in source locations for all CFGBlocks. | |||
2298 | findBlockLocations(CFGraph, SortedGraph, BlockInfo); | |||
2299 | ||||
2300 | CapExprSet ExclusiveLocksAcquired; | |||
2301 | CapExprSet SharedLocksAcquired; | |||
2302 | CapExprSet LocksReleased; | |||
2303 | ||||
2304 | // Add locks from exclusive_locks_required and shared_locks_required | |||
2305 | // to initial lockset. Also turn off checking for lock and unlock functions. | |||
2306 | // FIXME: is there a more intelligent way to check lock/unlock functions? | |||
2307 | if (!SortedGraph->empty() && D->hasAttrs()) { | |||
2308 | const CFGBlock *FirstBlock = *SortedGraph->begin(); | |||
2309 | FactSet &InitialLockset = BlockInfo[FirstBlock->getBlockID()].EntrySet; | |||
2310 | ||||
2311 | CapExprSet ExclusiveLocksToAdd; | |||
2312 | CapExprSet SharedLocksToAdd; | |||
2313 | StringRef CapDiagKind = "mutex"; | |||
2314 | ||||
2315 | SourceLocation Loc = D->getLocation(); | |||
2316 | for (const auto *Attr : D->attrs()) { | |||
2317 | Loc = Attr->getLocation(); | |||
2318 | if (const auto *A = dyn_cast<RequiresCapabilityAttr>(Attr)) { | |||
2319 | getMutexIDs(A->isShared() ? SharedLocksToAdd : ExclusiveLocksToAdd, A, | |||
2320 | nullptr, D); | |||
2321 | CapDiagKind = ClassifyDiagnostic(A); | |||
2322 | } else if (const auto *A = dyn_cast<ReleaseCapabilityAttr>(Attr)) { | |||
2323 | // UNLOCK_FUNCTION() is used to hide the underlying lock implementation. | |||
2324 | // We must ignore such methods. | |||
2325 | if (A->args_size() == 0) | |||
2326 | return; | |||
2327 | getMutexIDs(A->isShared() ? SharedLocksToAdd : ExclusiveLocksToAdd, A, | |||
2328 | nullptr, D); | |||
2329 | getMutexIDs(LocksReleased, A, nullptr, D); | |||
2330 | CapDiagKind = ClassifyDiagnostic(A); | |||
2331 | } else if (const auto *A = dyn_cast<AcquireCapabilityAttr>(Attr)) { | |||
2332 | if (A->args_size() == 0) | |||
2333 | return; | |||
2334 | getMutexIDs(A->isShared() ? SharedLocksAcquired | |||
2335 | : ExclusiveLocksAcquired, | |||
2336 | A, nullptr, D); | |||
2337 | CapDiagKind = ClassifyDiagnostic(A); | |||
2338 | } else if (isa<ExclusiveTrylockFunctionAttr>(Attr)) { | |||
2339 | // Don't try to check trylock functions for now. | |||
2340 | return; | |||
2341 | } else if (isa<SharedTrylockFunctionAttr>(Attr)) { | |||
2342 | // Don't try to check trylock functions for now. | |||
2343 | return; | |||
2344 | } else if (isa<TryAcquireCapabilityAttr>(Attr)) { | |||
2345 | // Don't try to check trylock functions for now. | |||
2346 | return; | |||
2347 | } | |||
2348 | } | |||
2349 | ||||
2350 | // FIXME -- Loc can be wrong here. | |||
2351 | for (const auto &Mu : ExclusiveLocksToAdd) { | |||
2352 | auto Entry = llvm::make_unique<LockableFactEntry>(Mu, LK_Exclusive, Loc); | |||
2353 | Entry->setDeclared(true); | |||
2354 | addLock(InitialLockset, std::move(Entry), CapDiagKind, true); | |||
2355 | } | |||
2356 | for (const auto &Mu : SharedLocksToAdd) { | |||
2357 | auto Entry = llvm::make_unique<LockableFactEntry>(Mu, LK_Shared, Loc); | |||
2358 | Entry->setDeclared(true); | |||
2359 | addLock(InitialLockset, std::move(Entry), CapDiagKind, true); | |||
2360 | } | |||
2361 | } | |||
2362 | ||||
2363 | for (const auto *CurrBlock : *SortedGraph) { | |||
2364 | unsigned CurrBlockID = CurrBlock->getBlockID(); | |||
2365 | CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; | |||
2366 | ||||
2367 | // Use the default initial lockset in case there are no predecessors. | |||
2368 | VisitedBlocks.insert(CurrBlock); | |||
2369 | ||||
2370 | // Iterate through the predecessor blocks and warn if the lockset for all | |||
2371 | // predecessors is not the same. We take the entry lockset of the current | |||
2372 | // block to be the intersection of all previous locksets. | |||
2373 | // FIXME: By keeping the intersection, we may output more errors in future | |||
2374 | // for a lock which is not in the intersection, but was in the union. We | |||
2375 | // may want to also keep the union in future. As an example, let's say | |||
2376 | // the intersection contains Mutex L, and the union contains L and M. | |||
2377 | // Later we unlock M. At this point, we would output an error because we | |||
2378 | // never locked M; although the real error is probably that we forgot to | |||
2379 | // lock M on all code paths. Conversely, let's say that later we lock M. | |||
2380 | // In this case, we should compare against the intersection instead of the | |||
2381 | // union because the real error is probably that we forgot to unlock M on | |||
2382 | // all code paths. | |||
2383 | bool LocksetInitialized = false; | |||
2384 | SmallVector<CFGBlock *, 8> SpecialBlocks; | |||
2385 | for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), | |||
2386 | PE = CurrBlock->pred_end(); PI != PE; ++PI) { | |||
2387 | // if *PI -> CurrBlock is a back edge | |||
2388 | if (*PI == nullptr || !VisitedBlocks.alreadySet(*PI)) | |||
2389 | continue; | |||
2390 | ||||
2391 | unsigned PrevBlockID = (*PI)->getBlockID(); | |||
2392 | CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; | |||
2393 | ||||
2394 | // Ignore edges from blocks that can't return. | |||
2395 | if (neverReturns(*PI) || !PrevBlockInfo->Reachable) | |||
2396 | continue; | |||
2397 | ||||
2398 | // Okay, we can reach this block from the entry. | |||
2399 | CurrBlockInfo->Reachable = true; | |||
2400 | ||||
2401 | // If the previous block ended in a 'continue' or 'break' statement, then | |||
2402 | // a difference in locksets is probably due to a bug in that block, rather | |||
2403 | // than in some other predecessor. In that case, keep the other | |||
2404 | // predecessor's lockset. | |||
2405 | if (const Stmt *Terminator = (*PI)->getTerminatorStmt()) { | |||
2406 | if (isa<ContinueStmt>(Terminator) || isa<BreakStmt>(Terminator)) { | |||
2407 | SpecialBlocks.push_back(*PI); | |||
2408 | continue; | |||
2409 | } | |||
2410 | } | |||
2411 | ||||
2412 | FactSet PrevLockset; | |||
2413 | getEdgeLockset(PrevLockset, PrevBlockInfo->ExitSet, *PI, CurrBlock); | |||
2414 | ||||
2415 | if (!LocksetInitialized) { | |||
2416 | CurrBlockInfo->EntrySet = PrevLockset; | |||
2417 | LocksetInitialized = true; | |||
2418 | } else { | |||
2419 | intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset, | |||
2420 | CurrBlockInfo->EntryLoc, | |||
2421 | LEK_LockedSomePredecessors); | |||
2422 | } | |||
2423 | } | |||
2424 | ||||
2425 | // Skip rest of block if it's not reachable. | |||
2426 | if (!CurrBlockInfo->Reachable) | |||
2427 | continue; | |||
2428 | ||||
2429 | // Process continue and break blocks. Assume that the lockset for the | |||
2430 | // resulting block is unaffected by any discrepancies in them. | |||
2431 | for (const auto *PrevBlock : SpecialBlocks) { | |||
2432 | unsigned PrevBlockID = PrevBlock->getBlockID(); | |||
2433 | CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; | |||
2434 | ||||
2435 | if (!LocksetInitialized) { | |||
2436 | CurrBlockInfo->EntrySet = PrevBlockInfo->ExitSet; | |||
2437 | LocksetInitialized = true; | |||
2438 | } else { | |||
2439 | // Determine whether this edge is a loop terminator for diagnostic | |||
2440 | // purposes. FIXME: A 'break' statement might be a loop terminator, but | |||
2441 | // it might also be part of a switch. Also, a subsequent destructor | |||
2442 | // might add to the lockset, in which case the real issue might be a | |||
2443 | // double lock on the other path. | |||
2444 | const Stmt *Terminator = PrevBlock->getTerminatorStmt(); | |||
2445 | bool IsLoop = Terminator && isa<ContinueStmt>(Terminator); | |||
2446 | ||||
2447 | FactSet PrevLockset; | |||
2448 | getEdgeLockset(PrevLockset, PrevBlockInfo->ExitSet, | |||
2449 | PrevBlock, CurrBlock); | |||
2450 | ||||
2451 | // Do not update EntrySet. | |||
2452 | intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset, | |||
2453 | PrevBlockInfo->ExitLoc, | |||
2454 | IsLoop ? LEK_LockedSomeLoopIterations | |||
2455 | : LEK_LockedSomePredecessors, | |||
2456 | false); | |||
2457 | } | |||
2458 | } | |||
2459 | ||||
2460 | BuildLockset LocksetBuilder(this, *CurrBlockInfo); | |||
2461 | ||||
2462 | // Visit all the statements in the basic block. | |||
2463 | for (const auto &BI : *CurrBlock) { | |||
2464 | switch (BI.getKind()) { | |||
2465 | case CFGElement::Statement: { | |||
2466 | CFGStmt CS = BI.castAs<CFGStmt>(); | |||
2467 | LocksetBuilder.Visit(CS.getStmt()); | |||
2468 | break; | |||
2469 | } | |||
2470 | // Ignore BaseDtor, MemberDtor, and TemporaryDtor for now. | |||
2471 | case CFGElement::AutomaticObjectDtor: { | |||
2472 | CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>(); | |||
2473 | const auto *DD = AD.getDestructorDecl(AC.getASTContext()); | |||
2474 | if (!DD->hasAttrs()) | |||
2475 | break; | |||
2476 | ||||
2477 | // Create a dummy expression, | |||
2478 | auto *VD = const_cast<VarDecl *>(AD.getVarDecl()); | |||
2479 | DeclRefExpr DRE(VD->getASTContext(), VD, false, | |||
2480 | VD->getType().getNonReferenceType(), VK_LValue, | |||
2481 | AD.getTriggerStmt()->getEndLoc()); | |||
2482 | LocksetBuilder.handleCall(&DRE, DD); | |||
2483 | break; | |||
2484 | } | |||
2485 | default: | |||
2486 | break; | |||
2487 | } | |||
2488 | } | |||
2489 | CurrBlockInfo->ExitSet = LocksetBuilder.FSet; | |||
2490 | ||||
2491 | // For every back edge from CurrBlock (the end of the loop) to another block | |||
2492 | // (FirstLoopBlock) we need to check that the Lockset of Block is equal to | |||
2493 | // the one held at the beginning of FirstLoopBlock. We can look up the | |||
2494 | // Lockset held at the beginning of FirstLoopBlock in the EntryLockSets map. | |||
2495 | for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), | |||
2496 | SE = CurrBlock->succ_end(); SI != SE; ++SI) { | |||
2497 | // if CurrBlock -> *SI is *not* a back edge | |||
2498 | if (*SI == nullptr || !VisitedBlocks.alreadySet(*SI)) | |||
2499 | continue; | |||
2500 | ||||
2501 | CFGBlock *FirstLoopBlock = *SI; | |||
2502 | CFGBlockInfo *PreLoop = &BlockInfo[FirstLoopBlock->getBlockID()]; | |||
2503 | CFGBlockInfo *LoopEnd = &BlockInfo[CurrBlockID]; | |||
2504 | intersectAndWarn(LoopEnd->ExitSet, PreLoop->EntrySet, | |||
2505 | PreLoop->EntryLoc, | |||
2506 | LEK_LockedSomeLoopIterations, | |||
2507 | false); | |||
2508 | } | |||
2509 | } | |||
2510 | ||||
2511 | CFGBlockInfo *Initial = &BlockInfo[CFGraph->getEntry().getBlockID()]; | |||
2512 | CFGBlockInfo *Final = &BlockInfo[CFGraph->getExit().getBlockID()]; | |||
2513 | ||||
2514 | // Skip the final check if the exit block is unreachable. | |||
2515 | if (!Final->Reachable) | |||
2516 | return; | |||
2517 | ||||
2518 | // By default, we expect all locks held on entry to be held on exit. | |||
2519 | FactSet ExpectedExitSet = Initial->EntrySet; | |||
2520 | ||||
2521 | // Adjust the expected exit set by adding or removing locks, as declared | |||
2522 | // by *-LOCK_FUNCTION and UNLOCK_FUNCTION. The intersect below will then | |||
2523 | // issue the appropriate warning. | |||
2524 | // FIXME: the location here is not quite right. | |||
2525 | for (const auto &Lock : ExclusiveLocksAcquired) | |||
2526 | ExpectedExitSet.addLock(FactMan, llvm::make_unique<LockableFactEntry>( | |||
2527 | Lock, LK_Exclusive, D->getLocation())); | |||
2528 | for (const auto &Lock : SharedLocksAcquired) | |||
2529 | ExpectedExitSet.addLock(FactMan, llvm::make_unique<LockableFactEntry>( | |||
2530 | Lock, LK_Shared, D->getLocation())); | |||
2531 | for (const auto &Lock : LocksReleased) | |||
2532 | ExpectedExitSet.removeLock(FactMan, Lock); | |||
2533 | ||||
2534 | // FIXME: Should we call this function for all blocks which exit the function? | |||
2535 | intersectAndWarn(ExpectedExitSet, Final->ExitSet, | |||
2536 | Final->ExitLoc, | |||
2537 | LEK_LockedAtEndOfFunction, | |||
2538 | LEK_NotLockedAtEndOfFunction, | |||
2539 | false); | |||
2540 | ||||
2541 | Handler.leaveFunction(CurrentFunction); | |||
2542 | } | |||
2543 | ||||
2544 | /// Check a function's CFG for thread-safety violations. | |||
2545 | /// | |||
2546 | /// We traverse the blocks in the CFG, compute the set of mutexes that are held | |||
2547 | /// at the end of each block, and issue warnings for thread safety violations. | |||
2548 | /// Each block in the CFG is traversed exactly once. | |||
2549 | void threadSafety::runThreadSafetyAnalysis(AnalysisDeclContext &AC, | |||
2550 | ThreadSafetyHandler &Handler, | |||
2551 | BeforeSet **BSet) { | |||
2552 | if (!*BSet) | |||
| ||||
2553 | *BSet = new BeforeSet; | |||
2554 | ThreadSafetyAnalyzer Analyzer(Handler, *BSet); | |||
2555 | Analyzer.runAnalysis(AC); | |||
2556 | } | |||
2557 | ||||
2558 | void threadSafety::threadSafetyCleanup(BeforeSet *Cache) { delete Cache; } | |||
2559 | ||||
2560 | /// Helper function that returns a LockKind required for the given level | |||
2561 | /// of access. | |||
2562 | LockKind threadSafety::getLockKindFromAccessKind(AccessKind AK) { | |||
2563 | switch (AK) { | |||
2564 | case AK_Read : | |||
2565 | return LK_Shared; | |||
2566 | case AK_Written : | |||
2567 | return LK_Exclusive; | |||
2568 | } | |||
2569 | llvm_unreachable("Unknown AccessKind")::llvm::llvm_unreachable_internal("Unknown AccessKind", "/build/llvm-toolchain-snapshot-9~svn362543/tools/clang/lib/Analysis/ThreadSafety.cpp" , 2569); | |||
2570 | } |
1 | //===- ThreadSafetyCommon.h -------------------------------------*- C++ -*-===// | |||
2 | // | |||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |||
4 | // See https://llvm.org/LICENSE.txt for license information. | |||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |||
6 | // | |||
7 | //===----------------------------------------------------------------------===// | |||
8 | // | |||
9 | // Parts of thread safety analysis that are not specific to thread safety | |||
10 | // itself have been factored into classes here, where they can be potentially | |||
11 | // used by other analyses. Currently these include: | |||
12 | // | |||
13 | // * Generalize clang CFG visitors. | |||
14 | // * Conversion of the clang CFG to SSA form. | |||
15 | // * Translation of clang Exprs to TIL SExprs | |||
16 | // | |||
17 | // UNDER CONSTRUCTION. USE AT YOUR OWN RISK. | |||
18 | // | |||
19 | //===----------------------------------------------------------------------===// | |||
20 | ||||
21 | #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H | |||
22 | #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H | |||
23 | ||||
24 | #include "clang/AST/Decl.h" | |||
25 | #include "clang/Analysis/Analyses/PostOrderCFGView.h" | |||
26 | #include "clang/Analysis/Analyses/ThreadSafetyTIL.h" | |||
27 | #include "clang/Analysis/Analyses/ThreadSafetyTraverse.h" | |||
28 | #include "clang/Analysis/Analyses/ThreadSafetyUtil.h" | |||
29 | #include "clang/Analysis/AnalysisDeclContext.h" | |||
30 | #include "clang/Analysis/CFG.h" | |||
31 | #include "clang/Basic/LLVM.h" | |||
32 | #include "llvm/ADT/DenseMap.h" | |||
33 | #include "llvm/ADT/SmallVector.h" | |||
34 | #include "llvm/Support/Casting.h" | |||
35 | #include <sstream> | |||
36 | #include <string> | |||
37 | #include <utility> | |||
38 | #include <vector> | |||
39 | ||||
40 | namespace clang { | |||
41 | ||||
42 | class AbstractConditionalOperator; | |||
43 | class ArraySubscriptExpr; | |||
44 | class BinaryOperator; | |||
45 | class CallExpr; | |||
46 | class CastExpr; | |||
47 | class CXXDestructorDecl; | |||
48 | class CXXMemberCallExpr; | |||
49 | class CXXOperatorCallExpr; | |||
50 | class CXXThisExpr; | |||
51 | class DeclRefExpr; | |||
52 | class DeclStmt; | |||
53 | class Expr; | |||
54 | class MemberExpr; | |||
55 | class Stmt; | |||
56 | class UnaryOperator; | |||
57 | ||||
58 | namespace threadSafety { | |||
59 | ||||
60 | // Various helper functions on til::SExpr | |||
61 | namespace sx { | |||
62 | ||||
63 | inline bool equals(const til::SExpr *E1, const til::SExpr *E2) { | |||
64 | return til::EqualsComparator::compareExprs(E1, E2); | |||
65 | } | |||
66 | ||||
67 | inline bool matches(const til::SExpr *E1, const til::SExpr *E2) { | |||
68 | // We treat a top-level wildcard as the "univsersal" lock. | |||
69 | // It matches everything for the purpose of checking locks, but not | |||
70 | // for unlocking them. | |||
71 | if (isa<til::Wildcard>(E1)) | |||
72 | return isa<til::Wildcard>(E2); | |||
73 | if (isa<til::Wildcard>(E2)) | |||
74 | return isa<til::Wildcard>(E1); | |||
75 | ||||
76 | return til::MatchComparator::compareExprs(E1, E2); | |||
77 | } | |||
78 | ||||
79 | inline bool partiallyMatches(const til::SExpr *E1, const til::SExpr *E2) { | |||
80 | const auto *PE1 = dyn_cast_or_null<til::Project>(E1); | |||
81 | if (!PE1) | |||
82 | return false; | |||
83 | const auto *PE2 = dyn_cast_or_null<til::Project>(E2); | |||
84 | if (!PE2) | |||
85 | return false; | |||
86 | return PE1->clangDecl() == PE2->clangDecl(); | |||
87 | } | |||
88 | ||||
89 | inline std::string toString(const til::SExpr *E) { | |||
90 | std::stringstream ss; | |||
91 | til::StdPrinter::print(E, ss); | |||
92 | return ss.str(); | |||
93 | } | |||
94 | ||||
95 | } // namespace sx | |||
96 | ||||
97 | // This class defines the interface of a clang CFG Visitor. | |||
98 | // CFGWalker will invoke the following methods. | |||
99 | // Note that methods are not virtual; the visitor is templatized. | |||
100 | class CFGVisitor { | |||
101 | // Enter the CFG for Decl D, and perform any initial setup operations. | |||
102 | void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {} | |||
103 | ||||
104 | // Enter a CFGBlock. | |||
105 | void enterCFGBlock(const CFGBlock *B) {} | |||
106 | ||||
107 | // Returns true if this visitor implements handlePredecessor | |||
108 | bool visitPredecessors() { return true; } | |||
109 | ||||
110 | // Process a predecessor edge. | |||
111 | void handlePredecessor(const CFGBlock *Pred) {} | |||
112 | ||||
113 | // Process a successor back edge to a previously visited block. | |||
114 | void handlePredecessorBackEdge(const CFGBlock *Pred) {} | |||
115 | ||||
116 | // Called just before processing statements. | |||
117 | void enterCFGBlockBody(const CFGBlock *B) {} | |||
118 | ||||
119 | // Process an ordinary statement. | |||
120 | void handleStatement(const Stmt *S) {} | |||
121 | ||||
122 | // Process a destructor call | |||
123 | void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {} | |||
124 | ||||
125 | // Called after all statements have been handled. | |||
126 | void exitCFGBlockBody(const CFGBlock *B) {} | |||
127 | ||||
128 | // Return true | |||
129 | bool visitSuccessors() { return true; } | |||
130 | ||||
131 | // Process a successor edge. | |||
132 | void handleSuccessor(const CFGBlock *Succ) {} | |||
133 | ||||
134 | // Process a successor back edge to a previously visited block. | |||
135 | void handleSuccessorBackEdge(const CFGBlock *Succ) {} | |||
136 | ||||
137 | // Leave a CFGBlock. | |||
138 | void exitCFGBlock(const CFGBlock *B) {} | |||
139 | ||||
140 | // Leave the CFG, and perform any final cleanup operations. | |||
141 | void exitCFG(const CFGBlock *Last) {} | |||
142 | }; | |||
143 | ||||
144 | // Walks the clang CFG, and invokes methods on a given CFGVisitor. | |||
145 | class CFGWalker { | |||
146 | public: | |||
147 | CFGWalker() = default; | |||
148 | ||||
149 | // Initialize the CFGWalker. This setup only needs to be done once, even | |||
150 | // if there are multiple passes over the CFG. | |||
151 | bool init(AnalysisDeclContext &AC) { | |||
152 | ACtx = &AC; | |||
153 | CFGraph = AC.getCFG(); | |||
154 | if (!CFGraph) | |||
155 | return false; | |||
156 | ||||
157 | // Ignore anonymous functions. | |||
158 | if (!dyn_cast_or_null<NamedDecl>(AC.getDecl())) | |||
159 | return false; | |||
160 | ||||
161 | SortedGraph = AC.getAnalysis<PostOrderCFGView>(); | |||
162 | if (!SortedGraph) | |||
163 | return false; | |||
164 | ||||
165 | return true; | |||
166 | } | |||
167 | ||||
168 | // Traverse the CFG, calling methods on V as appropriate. | |||
169 | template <class Visitor> | |||
170 | void walk(Visitor &V) { | |||
171 | PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); | |||
172 | ||||
173 | V.enterCFG(CFGraph, getDecl(), &CFGraph->getEntry()); | |||
174 | ||||
175 | for (const auto *CurrBlock : *SortedGraph) { | |||
176 | VisitedBlocks.insert(CurrBlock); | |||
177 | ||||
178 | V.enterCFGBlock(CurrBlock); | |||
179 | ||||
180 | // Process predecessors, handling back edges last | |||
181 | if (V.visitPredecessors()) { | |||
182 | SmallVector<CFGBlock*, 4> BackEdges; | |||
183 | // Process successors | |||
184 | for (CFGBlock::const_pred_iterator SI = CurrBlock->pred_begin(), | |||
185 | SE = CurrBlock->pred_end(); | |||
186 | SI != SE; ++SI) { | |||
187 | if (*SI == nullptr) | |||
188 | continue; | |||
189 | ||||
190 | if (!VisitedBlocks.alreadySet(*SI)) { | |||
191 | BackEdges.push_back(*SI); | |||
192 | continue; | |||
193 | } | |||
194 | V.handlePredecessor(*SI); | |||
195 | } | |||
196 | ||||
197 | for (auto *Blk : BackEdges) | |||
198 | V.handlePredecessorBackEdge(Blk); | |||
199 | } | |||
200 | ||||
201 | V.enterCFGBlockBody(CurrBlock); | |||
202 | ||||
203 | // Process statements | |||
204 | for (const auto &BI : *CurrBlock) { | |||
205 | switch (BI.getKind()) { | |||
206 | case CFGElement::Statement: | |||
207 | V.handleStatement(BI.castAs<CFGStmt>().getStmt()); | |||
208 | break; | |||
209 | ||||
210 | case CFGElement::AutomaticObjectDtor: { | |||
211 | CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>(); | |||
212 | auto *DD = const_cast<CXXDestructorDecl *>( | |||
213 | AD.getDestructorDecl(ACtx->getASTContext())); | |||
214 | auto *VD = const_cast<VarDecl *>(AD.getVarDecl()); | |||
215 | V.handleDestructorCall(VD, DD); | |||
216 | break; | |||
217 | } | |||
218 | default: | |||
219 | break; | |||
220 | } | |||
221 | } | |||
222 | ||||
223 | V.exitCFGBlockBody(CurrBlock); | |||
224 | ||||
225 | // Process successors, handling back edges first. | |||
226 | if (V.visitSuccessors()) { | |||
227 | SmallVector<CFGBlock*, 8> ForwardEdges; | |||
228 | ||||
229 | // Process successors | |||
230 | for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), | |||
231 | SE = CurrBlock->succ_end(); | |||
232 | SI != SE; ++SI) { | |||
233 | if (*SI == nullptr) | |||
234 | continue; | |||
235 | ||||
236 | if (!VisitedBlocks.alreadySet(*SI)) { | |||
237 | ForwardEdges.push_back(*SI); | |||
238 | continue; | |||
239 | } | |||
240 | V.handleSuccessorBackEdge(*SI); | |||
241 | } | |||
242 | ||||
243 | for (auto *Blk : ForwardEdges) | |||
244 | V.handleSuccessor(Blk); | |||
245 | } | |||
246 | ||||
247 | V.exitCFGBlock(CurrBlock); | |||
248 | } | |||
249 | V.exitCFG(&CFGraph->getExit()); | |||
250 | } | |||
251 | ||||
252 | const CFG *getGraph() const { return CFGraph; } | |||
253 | CFG *getGraph() { return CFGraph; } | |||
254 | ||||
255 | const NamedDecl *getDecl() const { | |||
256 | return dyn_cast<NamedDecl>(ACtx->getDecl()); | |||
257 | } | |||
258 | ||||
259 | const PostOrderCFGView *getSortedGraph() const { return SortedGraph; } | |||
260 | ||||
261 | private: | |||
262 | CFG *CFGraph = nullptr; | |||
263 | AnalysisDeclContext *ACtx = nullptr; | |||
264 | PostOrderCFGView *SortedGraph = nullptr; | |||
265 | }; | |||
266 | ||||
267 | // TODO: move this back into ThreadSafety.cpp | |||
268 | // This is specific to thread safety. It is here because | |||
269 | // translateAttrExpr needs it, but that should be moved too. | |||
270 | class CapabilityExpr { | |||
271 | private: | |||
272 | /// The capability expression. | |||
273 | const til::SExpr* CapExpr; | |||
274 | ||||
275 | /// True if this is a negative capability. | |||
276 | bool Negated; | |||
277 | ||||
278 | public: | |||
279 | CapabilityExpr(const til::SExpr *E, bool Neg) : CapExpr(E), Negated(Neg) {} | |||
280 | ||||
281 | const til::SExpr* sexpr() const { return CapExpr; } | |||
282 | bool negative() const { return Negated; } | |||
283 | ||||
284 | CapabilityExpr operator!() const { | |||
285 | return CapabilityExpr(CapExpr, !Negated); | |||
286 | } | |||
287 | ||||
288 | bool equals(const CapabilityExpr &other) const { | |||
289 | return (Negated == other.Negated) && sx::equals(CapExpr, other.CapExpr); | |||
290 | } | |||
291 | ||||
292 | bool matches(const CapabilityExpr &other) const { | |||
293 | return (Negated == other.Negated) && sx::matches(CapExpr, other.CapExpr); | |||
294 | } | |||
295 | ||||
296 | bool matchesUniv(const CapabilityExpr &CapE) const { | |||
297 | return isUniversal() || matches(CapE); | |||
298 | } | |||
299 | ||||
300 | bool partiallyMatches(const CapabilityExpr &other) const { | |||
301 | return (Negated == other.Negated) && | |||
302 | sx::partiallyMatches(CapExpr, other.CapExpr); | |||
303 | } | |||
304 | ||||
305 | const ValueDecl* valueDecl() const { | |||
306 | if (Negated || CapExpr == nullptr) | |||
307 | return nullptr; | |||
308 | if (const auto *P = dyn_cast<til::Project>(CapExpr)) | |||
309 | return P->clangDecl(); | |||
310 | if (const auto *P = dyn_cast<til::LiteralPtr>(CapExpr)) | |||
311 | return P->clangDecl(); | |||
312 | return nullptr; | |||
313 | } | |||
314 | ||||
315 | std::string toString() const { | |||
316 | if (Negated) | |||
317 | return "!" + sx::toString(CapExpr); | |||
318 | return sx::toString(CapExpr); | |||
319 | } | |||
320 | ||||
321 | bool shouldIgnore() const { return CapExpr == nullptr; } | |||
322 | ||||
323 | bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); } | |||
324 | ||||
325 | bool isUniversal() const { return sexpr() && isa<til::Wildcard>(sexpr()); } | |||
326 | }; | |||
327 | ||||
328 | // Translate clang::Expr to til::SExpr. | |||
329 | class SExprBuilder { | |||
330 | public: | |||
331 | /// Encapsulates the lexical context of a function call. The lexical | |||
332 | /// context includes the arguments to the call, including the implicit object | |||
333 | /// argument. When an attribute containing a mutex expression is attached to | |||
334 | /// a method, the expression may refer to formal parameters of the method. | |||
335 | /// Actual arguments must be substituted for formal parameters to derive | |||
336 | /// the appropriate mutex expression in the lexical context where the function | |||
337 | /// is called. PrevCtx holds the context in which the arguments themselves | |||
338 | /// should be evaluated; multiple calling contexts can be chained together | |||
339 | /// by the lock_returned attribute. | |||
340 | struct CallingContext { | |||
341 | // The previous context; or 0 if none. | |||
342 | CallingContext *Prev; | |||
343 | ||||
344 | // The decl to which the attr is attached. | |||
345 | const NamedDecl *AttrDecl; | |||
346 | ||||
347 | // Implicit object argument -- e.g. 'this' | |||
348 | const Expr *SelfArg = nullptr; | |||
349 | ||||
350 | // Number of funArgs | |||
351 | unsigned NumArgs = 0; | |||
352 | ||||
353 | // Function arguments | |||
354 | const Expr *const *FunArgs = nullptr; | |||
355 | ||||
356 | // is Self referred to with -> or .? | |||
357 | bool SelfArrow = false; | |||
358 | ||||
359 | CallingContext(CallingContext *P, const NamedDecl *D = nullptr) | |||
360 | : Prev(P), AttrDecl(D) {} | |||
361 | }; | |||
362 | ||||
363 | SExprBuilder(til::MemRegionRef A) : Arena(A) { | |||
364 | // FIXME: we don't always have a self-variable. | |||
365 | SelfVar = new (Arena) til::Variable(nullptr); | |||
366 | SelfVar->setKind(til::Variable::VK_SFun); | |||
| ||||
367 | } | |||
368 | ||||
369 | // Translate a clang expression in an attribute to a til::SExpr. | |||
370 | // Constructs the context from D, DeclExp, and SelfDecl. | |||
371 | CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D, | |||
372 | const Expr *DeclExp, VarDecl *SelfD=nullptr); | |||
373 | ||||
374 | CapabilityExpr translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx); | |||
375 | ||||
376 | // Translate a clang statement or expression to a TIL expression. | |||
377 | // Also performs substitution of variables; Ctx provides the context. | |||
378 | // Dispatches on the type of S. | |||
379 | til::SExpr *translate(const Stmt *S, CallingContext *Ctx); | |||
380 | til::SCFG *buildCFG(CFGWalker &Walker); | |||
381 | ||||
382 | til::SExpr *lookupStmt(const Stmt *S); | |||
383 | ||||
384 | til::BasicBlock *lookupBlock(const CFGBlock *B) { | |||
385 | return BlockMap[B->getBlockID()]; | |||
386 | } | |||
387 | ||||
388 | const til::SCFG *getCFG() const { return Scfg; } | |||
389 | til::SCFG *getCFG() { return Scfg; } | |||
390 | ||||
391 | private: | |||
392 | // We implement the CFGVisitor API | |||
393 | friend class CFGWalker; | |||
394 | ||||
395 | til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE, | |||
396 | CallingContext *Ctx) ; | |||
397 | til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx); | |||
398 | til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx); | |||
399 | til::SExpr *translateObjCIVarRefExpr(const ObjCIvarRefExpr *IVRE, | |||
400 | CallingContext *Ctx); | |||
401 | til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx, | |||
402 | const Expr *SelfE = nullptr); | |||
403 | til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME, | |||
404 | CallingContext *Ctx); | |||
405 | til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE, | |||
406 | CallingContext *Ctx); | |||
407 | til::SExpr *translateUnaryOperator(const UnaryOperator *UO, | |||
408 | CallingContext *Ctx); | |||
409 | til::SExpr *translateBinOp(til::TIL_BinaryOpcode Op, | |||
410 | const BinaryOperator *BO, | |||
411 | CallingContext *Ctx, bool Reverse = false); | |||
412 | til::SExpr *translateBinAssign(til::TIL_BinaryOpcode Op, | |||
413 | const BinaryOperator *BO, | |||
414 | CallingContext *Ctx, bool Assign = false); | |||
415 | til::SExpr *translateBinaryOperator(const BinaryOperator *BO, | |||
416 | CallingContext *Ctx); | |||
417 | til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx); | |||
418 | til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E, | |||
419 | CallingContext *Ctx); | |||
420 | til::SExpr *translateAbstractConditionalOperator( | |||
421 | const AbstractConditionalOperator *C, CallingContext *Ctx); | |||
422 | ||||
423 | til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx); | |||
424 | ||||
425 | // Map from statements in the clang CFG to SExprs in the til::SCFG. | |||
426 | using StatementMap = llvm::DenseMap<const Stmt *, til::SExpr *>; | |||
427 | ||||
428 | // Map from clang local variables to indices in a LVarDefinitionMap. | |||
429 | using LVarIndexMap = llvm::DenseMap<const ValueDecl *, unsigned>; | |||
430 | ||||
431 | // Map from local variable indices to SSA variables (or constants). | |||
432 | using NameVarPair = std::pair<const ValueDecl *, til::SExpr *>; | |||
433 | using LVarDefinitionMap = CopyOnWriteVector<NameVarPair>; | |||
434 | ||||
435 | struct BlockInfo { | |||
436 | LVarDefinitionMap ExitMap; | |||
437 | bool HasBackEdges = false; | |||
438 | ||||
439 | // Successors yet to be processed | |||
440 | unsigned UnprocessedSuccessors = 0; | |||
441 | ||||
442 | // Predecessors already processed | |||
443 | unsigned ProcessedPredecessors = 0; | |||
444 | ||||
445 | BlockInfo() = default; | |||
446 | BlockInfo(BlockInfo &&) = default; | |||
447 | BlockInfo &operator=(BlockInfo &&) = default; | |||
448 | }; | |||
449 | ||||
450 | void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First); | |||
451 | void enterCFGBlock(const CFGBlock *B); | |||
452 | bool visitPredecessors() { return true; } | |||
453 | void handlePredecessor(const CFGBlock *Pred); | |||
454 | void handlePredecessorBackEdge(const CFGBlock *Pred); | |||
455 | void enterCFGBlockBody(const CFGBlock *B); | |||
456 | void handleStatement(const Stmt *S); | |||
457 | void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD); | |||
458 | void exitCFGBlockBody(const CFGBlock *B); | |||
459 | bool visitSuccessors() { return true; } | |||
460 | void handleSuccessor(const CFGBlock *Succ); | |||
461 | void handleSuccessorBackEdge(const CFGBlock *Succ); | |||
462 | void exitCFGBlock(const CFGBlock *B); | |||
463 | void exitCFG(const CFGBlock *Last); | |||
464 | ||||
465 | void insertStmt(const Stmt *S, til::SExpr *E) { | |||
466 | SMap.insert(std::make_pair(S, E)); | |||
467 | } | |||
468 | ||||
469 | til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD); | |||
470 | ||||
471 | til::SExpr *addStatement(til::SExpr *E, const Stmt *S, | |||
472 | const ValueDecl *VD = nullptr); | |||
473 | til::SExpr *lookupVarDecl(const ValueDecl *VD); | |||
474 | til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E); | |||
475 | til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E); | |||
476 | ||||
477 | void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E); | |||
478 | void mergeEntryMap(LVarDefinitionMap Map); | |||
479 | void mergeEntryMapBackEdge(); | |||
480 | void mergePhiNodesBackEdge(const CFGBlock *Blk); | |||
481 | ||||
482 | private: | |||
483 | // Set to true when parsing capability expressions, which get translated | |||
484 | // inaccurately in order to hack around smart pointers etc. | |||
485 | static const bool CapabilityExprMode = true; | |||
486 | ||||
487 | til::MemRegionRef Arena; | |||
488 | ||||
489 | // Variable to use for 'this'. May be null. | |||
490 | til::Variable *SelfVar = nullptr; | |||
491 | ||||
492 | til::SCFG *Scfg = nullptr; | |||
493 | ||||
494 | // Map from Stmt to TIL Variables | |||
495 | StatementMap SMap; | |||
496 | ||||
497 | // Indices of clang local vars. | |||
498 | LVarIndexMap LVarIdxMap; | |||
499 | ||||
500 | // Map from clang to til BBs. | |||
501 | std::vector<til::BasicBlock *> BlockMap; | |||
502 | ||||
503 | // Extra information per BB. Indexed by clang BlockID. | |||
504 | std::vector<BlockInfo> BBInfo; | |||
505 | ||||
506 | LVarDefinitionMap CurrentLVarMap; | |||
507 | std::vector<til::Phi *> CurrentArguments; | |||
508 | std::vector<til::SExpr *> CurrentInstructions; | |||
509 | std::vector<til::Phi *> IncompleteArgs; | |||
510 | til::BasicBlock *CurrentBB = nullptr; | |||
511 | BlockInfo *CurrentBlockInfo = nullptr; | |||
512 | }; | |||
513 | ||||
514 | // Dump an SCFG to llvm::errs(). | |||
515 | void printSCFG(CFGWalker &Walker); | |||
516 | ||||
517 | } // namespace threadSafety | |||
518 | } // namespace clang | |||
519 | ||||
520 | #endif // LLVM_CLANG_THREAD_SAFETY_COMMON_H |