ThreadSafetyCommon.h source code [clang_source_code/include/clang/Analysis/Analyses/ThreadSafetyCommon.h]

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
521