1 //===- ThreadSafetyCommon.h -------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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:
14 // * Generalize clang CFG visitors.
15 // * Conversion of the clang CFG to SSA form.
16 // * Translation of clang Exprs to TIL SExprs
18 // UNDER CONSTRUCTION. USE AT YOUR OWN RISK.
20 //===----------------------------------------------------------------------===//
22 #ifndef LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H
23 #define LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H
25 #include "clang/AST/Decl.h"
26 #include "clang/Analysis/Analyses/PostOrderCFGView.h"
27 #include "clang/Analysis/Analyses/ThreadSafetyTIL.h"
28 #include "clang/Analysis/Analyses/ThreadSafetyTraverse.h"
29 #include "clang/Analysis/Analyses/ThreadSafetyUtil.h"
30 #include "clang/Analysis/AnalysisDeclContext.h"
31 #include "clang/Analysis/CFG.h"
32 #include "clang/Basic/LLVM.h"
33 #include "llvm/ADT/DenseMap.h"
34 #include "llvm/ADT/SmallVector.h"
35 #include "llvm/Support/Casting.h"
43 class AbstractConditionalOperator;
44 class ArraySubscriptExpr;
48 class CXXDestructorDecl;
49 class CXXMemberCallExpr;
50 class CXXOperatorCallExpr;
59 namespace threadSafety {
61 // Various helper functions on til::SExpr
64 inline bool equals(const til::SExpr *E1, const til::SExpr *E2) {
65 return til::EqualsComparator::compareExprs(E1, E2);
68 inline bool matches(const til::SExpr *E1, const til::SExpr *E2) {
69 // We treat a top-level wildcard as the "univsersal" lock.
70 // It matches everything for the purpose of checking locks, but not
71 // for unlocking them.
72 if (isa<til::Wildcard>(E1))
73 return isa<til::Wildcard>(E2);
74 if (isa<til::Wildcard>(E2))
75 return isa<til::Wildcard>(E1);
77 return til::MatchComparator::compareExprs(E1, E2);
80 inline bool partiallyMatches(const til::SExpr *E1, const til::SExpr *E2) {
81 const auto *PE1 = dyn_cast_or_null<til::Project>(E1);
84 const auto *PE2 = dyn_cast_or_null<til::Project>(E2);
87 return PE1->clangDecl() == PE2->clangDecl();
90 inline std::string toString(const til::SExpr *E) {
92 til::StdPrinter::print(E, ss);
98 // This class defines the interface of a clang CFG Visitor.
99 // CFGWalker will invoke the following methods.
100 // Note that methods are not virtual; the visitor is templatized.
102 // Enter the CFG for Decl D, and perform any initial setup operations.
103 void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {}
106 void enterCFGBlock(const CFGBlock *B) {}
108 // Returns true if this visitor implements handlePredecessor
109 bool visitPredecessors() { return true; }
111 // Process a predecessor edge.
112 void handlePredecessor(const CFGBlock *Pred) {}
114 // Process a successor back edge to a previously visited block.
115 void handlePredecessorBackEdge(const CFGBlock *Pred) {}
117 // Called just before processing statements.
118 void enterCFGBlockBody(const CFGBlock *B) {}
120 // Process an ordinary statement.
121 void handleStatement(const Stmt *S) {}
123 // Process a destructor call
124 void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {}
126 // Called after all statements have been handled.
127 void exitCFGBlockBody(const CFGBlock *B) {}
130 bool visitSuccessors() { return true; }
132 // Process a successor edge.
133 void handleSuccessor(const CFGBlock *Succ) {}
135 // Process a successor back edge to a previously visited block.
136 void handleSuccessorBackEdge(const CFGBlock *Succ) {}
139 void exitCFGBlock(const CFGBlock *B) {}
141 // Leave the CFG, and perform any final cleanup operations.
142 void exitCFG(const CFGBlock *Last) {}
145 // Walks the clang CFG, and invokes methods on a given CFGVisitor.
148 CFGWalker() = default;
150 // Initialize the CFGWalker. This setup only needs to be done once, even
151 // if there are multiple passes over the CFG.
152 bool init(AnalysisDeclContext &AC) {
154 CFGraph = AC.getCFG();
158 // Ignore anonymous functions.
159 if (!dyn_cast_or_null<NamedDecl>(AC.getDecl()))
162 SortedGraph = AC.getAnalysis<PostOrderCFGView>();
169 // Traverse the CFG, calling methods on V as appropriate.
170 template <class Visitor>
171 void walk(Visitor &V) {
172 PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph);
174 V.enterCFG(CFGraph, getDecl(), &CFGraph->getEntry());
176 for (const auto *CurrBlock : *SortedGraph) {
177 VisitedBlocks.insert(CurrBlock);
179 V.enterCFGBlock(CurrBlock);
181 // Process predecessors, handling back edges last
182 if (V.visitPredecessors()) {
183 SmallVector<CFGBlock*, 4> BackEdges;
184 // Process successors
185 for (CFGBlock::const_pred_iterator SI = CurrBlock->pred_begin(),
186 SE = CurrBlock->pred_end();
191 if (!VisitedBlocks.alreadySet(*SI)) {
192 BackEdges.push_back(*SI);
195 V.handlePredecessor(*SI);
198 for (auto *Blk : BackEdges)
199 V.handlePredecessorBackEdge(Blk);
202 V.enterCFGBlockBody(CurrBlock);
204 // Process statements
205 for (const auto &BI : *CurrBlock) {
206 switch (BI.getKind()) {
207 case CFGElement::Statement:
208 V.handleStatement(BI.castAs<CFGStmt>().getStmt());
211 case CFGElement::AutomaticObjectDtor: {
212 CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>();
213 auto *DD = const_cast<CXXDestructorDecl *>(
214 AD.getDestructorDecl(ACtx->getASTContext()));
215 auto *VD = const_cast<VarDecl *>(AD.getVarDecl());
216 V.handleDestructorCall(VD, DD);
224 V.exitCFGBlockBody(CurrBlock);
226 // Process successors, handling back edges first.
227 if (V.visitSuccessors()) {
228 SmallVector<CFGBlock*, 8> ForwardEdges;
230 // Process successors
231 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(),
232 SE = CurrBlock->succ_end();
237 if (!VisitedBlocks.alreadySet(*SI)) {
238 ForwardEdges.push_back(*SI);
241 V.handleSuccessorBackEdge(*SI);
244 for (auto *Blk : ForwardEdges)
245 V.handleSuccessor(Blk);
248 V.exitCFGBlock(CurrBlock);
250 V.exitCFG(&CFGraph->getExit());
253 const CFG *getGraph() const { return CFGraph; }
254 CFG *getGraph() { return CFGraph; }
256 const NamedDecl *getDecl() const {
257 return dyn_cast<NamedDecl>(ACtx->getDecl());
260 const PostOrderCFGView *getSortedGraph() const { return SortedGraph; }
263 CFG *CFGraph = nullptr;
264 AnalysisDeclContext *ACtx = nullptr;
265 PostOrderCFGView *SortedGraph = nullptr;
268 // TODO: move this back into ThreadSafety.cpp
269 // This is specific to thread safety. It is here because
270 // translateAttrExpr needs it, but that should be moved too.
271 class CapabilityExpr {
273 /// The capability expression.
274 const til::SExpr* CapExpr;
276 /// True if this is a negative capability.
280 CapabilityExpr(const til::SExpr *E, bool Neg) : CapExpr(E), Negated(Neg) {}
282 const til::SExpr* sexpr() const { return CapExpr; }
283 bool negative() const { return Negated; }
285 CapabilityExpr operator!() const {
286 return CapabilityExpr(CapExpr, !Negated);
289 bool equals(const CapabilityExpr &other) const {
290 return (Negated == other.Negated) && sx::equals(CapExpr, other.CapExpr);
293 bool matches(const CapabilityExpr &other) const {
294 return (Negated == other.Negated) && sx::matches(CapExpr, other.CapExpr);
297 bool matchesUniv(const CapabilityExpr &CapE) const {
298 return isUniversal() || matches(CapE);
301 bool partiallyMatches(const CapabilityExpr &other) const {
302 return (Negated == other.Negated) &&
303 sx::partiallyMatches(CapExpr, other.CapExpr);
306 const ValueDecl* valueDecl() const {
307 if (Negated || CapExpr == nullptr)
309 if (const auto *P = dyn_cast<til::Project>(CapExpr))
310 return P->clangDecl();
311 if (const auto *P = dyn_cast<til::LiteralPtr>(CapExpr))
312 return P->clangDecl();
316 std::string toString() const {
318 return "!" + sx::toString(CapExpr);
319 return sx::toString(CapExpr);
322 bool shouldIgnore() const { return CapExpr == nullptr; }
324 bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); }
326 bool isUniversal() const { return sexpr() && isa<til::Wildcard>(sexpr()); }
329 // Translate clang::Expr to til::SExpr.
332 /// Encapsulates the lexical context of a function call. The lexical
333 /// context includes the arguments to the call, including the implicit object
334 /// argument. When an attribute containing a mutex expression is attached to
335 /// a method, the expression may refer to formal parameters of the method.
336 /// Actual arguments must be substituted for formal parameters to derive
337 /// the appropriate mutex expression in the lexical context where the function
338 /// is called. PrevCtx holds the context in which the arguments themselves
339 /// should be evaluated; multiple calling contexts can be chained together
340 /// by the lock_returned attribute.
341 struct CallingContext {
342 // The previous context; or 0 if none.
343 CallingContext *Prev;
345 // The decl to which the attr is attached.
346 const NamedDecl *AttrDecl;
348 // Implicit object argument -- e.g. 'this'
349 const Expr *SelfArg = nullptr;
352 unsigned NumArgs = 0;
354 // Function arguments
355 const Expr *const *FunArgs = nullptr;
357 // is Self referred to with -> or .?
358 bool SelfArrow = false;
360 CallingContext(CallingContext *P, const NamedDecl *D = nullptr)
361 : Prev(P), AttrDecl(D) {}
364 SExprBuilder(til::MemRegionRef A) : Arena(A) {
365 // FIXME: we don't always have a self-variable.
366 SelfVar = new (Arena) til::Variable(nullptr);
367 SelfVar->setKind(til::Variable::VK_SFun);
370 // Translate a clang expression in an attribute to a til::SExpr.
371 // Constructs the context from D, DeclExp, and SelfDecl.
372 CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D,
373 const Expr *DeclExp, VarDecl *SelfD=nullptr);
375 CapabilityExpr translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx);
377 // Translate a clang statement or expression to a TIL expression.
378 // Also performs substitution of variables; Ctx provides the context.
379 // Dispatches on the type of S.
380 til::SExpr *translate(const Stmt *S, CallingContext *Ctx);
381 til::SCFG *buildCFG(CFGWalker &Walker);
383 til::SExpr *lookupStmt(const Stmt *S);
385 til::BasicBlock *lookupBlock(const CFGBlock *B) {
386 return BlockMap[B->getBlockID()];
389 const til::SCFG *getCFG() const { return Scfg; }
390 til::SCFG *getCFG() { return Scfg; }
393 // We implement the CFGVisitor API
394 friend class CFGWalker;
396 til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE,
397 CallingContext *Ctx) ;
398 til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx);
399 til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx);
400 til::SExpr *translateObjCIVarRefExpr(const ObjCIvarRefExpr *IVRE,
401 CallingContext *Ctx);
402 til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx,
403 const Expr *SelfE = nullptr);
404 til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME,
405 CallingContext *Ctx);
406 til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE,
407 CallingContext *Ctx);
408 til::SExpr *translateUnaryOperator(const UnaryOperator *UO,
409 CallingContext *Ctx);
410 til::SExpr *translateBinOp(til::TIL_BinaryOpcode Op,
411 const BinaryOperator *BO,
412 CallingContext *Ctx, bool Reverse = false);
413 til::SExpr *translateBinAssign(til::TIL_BinaryOpcode Op,
414 const BinaryOperator *BO,
415 CallingContext *Ctx, bool Assign = false);
416 til::SExpr *translateBinaryOperator(const BinaryOperator *BO,
417 CallingContext *Ctx);
418 til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx);
419 til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E,
420 CallingContext *Ctx);
421 til::SExpr *translateAbstractConditionalOperator(
422 const AbstractConditionalOperator *C, CallingContext *Ctx);
424 til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx);
426 // Map from statements in the clang CFG to SExprs in the til::SCFG.
427 using StatementMap = llvm::DenseMap<const Stmt *, til::SExpr *>;
429 // Map from clang local variables to indices in a LVarDefinitionMap.
430 using LVarIndexMap = llvm::DenseMap<const ValueDecl *, unsigned>;
432 // Map from local variable indices to SSA variables (or constants).
433 using NameVarPair = std::pair<const ValueDecl *, til::SExpr *>;
434 using LVarDefinitionMap = CopyOnWriteVector<NameVarPair>;
437 LVarDefinitionMap ExitMap;
438 bool HasBackEdges = false;
440 // Successors yet to be processed
441 unsigned UnprocessedSuccessors = 0;
443 // Predecessors already processed
444 unsigned ProcessedPredecessors = 0;
446 BlockInfo() = default;
447 BlockInfo(BlockInfo &&) = default;
448 BlockInfo &operator=(BlockInfo &&) = default;
451 void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First);
452 void enterCFGBlock(const CFGBlock *B);
453 bool visitPredecessors() { return true; }
454 void handlePredecessor(const CFGBlock *Pred);
455 void handlePredecessorBackEdge(const CFGBlock *Pred);
456 void enterCFGBlockBody(const CFGBlock *B);
457 void handleStatement(const Stmt *S);
458 void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD);
459 void exitCFGBlockBody(const CFGBlock *B);
460 bool visitSuccessors() { return true; }
461 void handleSuccessor(const CFGBlock *Succ);
462 void handleSuccessorBackEdge(const CFGBlock *Succ);
463 void exitCFGBlock(const CFGBlock *B);
464 void exitCFG(const CFGBlock *Last);
466 void insertStmt(const Stmt *S, til::SExpr *E) {
467 SMap.insert(std::make_pair(S, E));
470 til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD);
472 til::SExpr *addStatement(til::SExpr *E, const Stmt *S,
473 const ValueDecl *VD = nullptr);
474 til::SExpr *lookupVarDecl(const ValueDecl *VD);
475 til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E);
476 til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E);
478 void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E);
479 void mergeEntryMap(LVarDefinitionMap Map);
480 void mergeEntryMapBackEdge();
481 void mergePhiNodesBackEdge(const CFGBlock *Blk);
484 // Set to true when parsing capability expressions, which get translated
485 // inaccurately in order to hack around smart pointers etc.
486 static const bool CapabilityExprMode = true;
488 til::MemRegionRef Arena;
490 // Variable to use for 'this'. May be null.
491 til::Variable *SelfVar = nullptr;
493 til::SCFG *Scfg = nullptr;
495 // Map from Stmt to TIL Variables
498 // Indices of clang local vars.
499 LVarIndexMap LVarIdxMap;
501 // Map from clang to til BBs.
502 std::vector<til::BasicBlock *> BlockMap;
504 // Extra information per BB. Indexed by clang BlockID.
505 std::vector<BlockInfo> BBInfo;
507 LVarDefinitionMap CurrentLVarMap;
508 std::vector<til::Phi *> CurrentArguments;
509 std::vector<til::SExpr *> CurrentInstructions;
510 std::vector<til::Phi *> IncompleteArgs;
511 til::BasicBlock *CurrentBB = nullptr;
512 BlockInfo *CurrentBlockInfo = nullptr;
515 // Dump an SCFG to llvm::errs().
516 void printSCFG(CFGWalker &Walker);
518 } // namespace threadSafety
521 #endif // LLVM_CLANG_THREAD_SAFETY_COMMON_H