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