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_THREAD_SAFETY_COMMON_H 23 #define LLVM_CLANG_THREAD_SAFETY_COMMON_H 24 25 #include "clang/Analysis/Analyses/PostOrderCFGView.h" 26 #include "clang/Analysis/Analyses/ThreadSafetyTIL.h" 27 #include "clang/Analysis/AnalysisContext.h" 28 #include "clang/Basic/OperatorKinds.h" 29 30 #include <memory> 31 #include <vector> 32 33 34 namespace clang { 35 namespace threadSafety { 36 37 // This class defines the interface of a clang CFG Visitor. 38 // CFGWalker will invoke the following methods. 39 // Note that methods are not virtual; the visitor is templatized. 40 class CFGVisitor { 41 // Enter the CFG for Decl D, and perform any initial setup operations. 42 void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {} 43 44 // Enter a CFGBlock. 45 void enterCFGBlock(const CFGBlock *B) {} 46 47 // Returns true if this visitor implements handlePredecessor 48 bool visitPredecessors() { return true; } 49 50 // Process a predecessor edge. 51 void handlePredecessor(const CFGBlock *Pred) {} 52 53 // Process a successor back edge to a previously visited block. 54 void handlePredecessorBackEdge(const CFGBlock *Pred) {} 55 56 // Called just before processing statements. 57 void enterCFGBlockBody(const CFGBlock *B) {} 58 59 // Process an ordinary statement. 60 void handleStatement(const Stmt *S) {} 61 62 // Process a destructor call 63 void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {} 64 65 // Called after all statements have been handled. 66 void exitCFGBlockBody(const CFGBlock *B) {} 67 68 // Return true 69 bool visitSuccessors() { return true; } 70 71 // Process a successor edge. 72 void handleSuccessor(const CFGBlock *Succ) {} 73 74 // Process a successor back edge to a previously visited block. 75 void handleSuccessorBackEdge(const CFGBlock *Succ) {} 76 77 // Leave a CFGBlock. 78 void exitCFGBlock(const CFGBlock *B) {} 79 80 // Leave the CFG, and perform any final cleanup operations. 81 void exitCFG(const CFGBlock *Last) {} 82 }; 83 84 85 // Walks the clang CFG, and invokes methods on a given CFGVisitor. 86 class CFGWalker { 87 public: 88 CFGWalker() : CFGraph(nullptr), ACtx(nullptr), SortedGraph(nullptr) {} 89 90 // Initialize the CFGWalker. This setup only needs to be done once, even 91 // if there are multiple passes over the CFG. 92 bool init(AnalysisDeclContext &AC) { 93 ACtx = &AC; 94 CFGraph = AC.getCFG(); 95 if (!CFGraph) 96 return false; 97 98 // Ignore anonymous functions. 99 if (!dyn_cast_or_null<NamedDecl>(AC.getDecl())) 100 return false; 101 102 SortedGraph = AC.getAnalysis<PostOrderCFGView>(); 103 if (!SortedGraph) 104 return false; 105 106 return true; 107 } 108 109 // Traverse the CFG, calling methods on V as appropriate. 110 template <class Visitor> 111 void walk(Visitor &V) { 112 PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); 113 114 V.enterCFG(CFGraph, getDecl(), &CFGraph->getEntry()); 115 116 for (const auto *CurrBlock : *SortedGraph) { 117 VisitedBlocks.insert(CurrBlock); 118 119 V.enterCFGBlock(CurrBlock); 120 121 // Process predecessors, handling back edges last 122 if (V.visitPredecessors()) { 123 SmallVector<CFGBlock*, 4> BackEdges; 124 // Process successors 125 for (CFGBlock::const_pred_iterator SI = CurrBlock->pred_begin(), 126 SE = CurrBlock->pred_end(); 127 SI != SE; ++SI) { 128 if (*SI == nullptr) 129 continue; 130 131 if (!VisitedBlocks.alreadySet(*SI)) { 132 BackEdges.push_back(*SI); 133 continue; 134 } 135 V.handlePredecessor(*SI); 136 } 137 138 for (auto *Blk : BackEdges) 139 V.handlePredecessorBackEdge(Blk); 140 } 141 142 V.enterCFGBlockBody(CurrBlock); 143 144 // Process statements 145 for (const auto &BI : *CurrBlock) { 146 switch (BI.getKind()) { 147 case CFGElement::Statement: { 148 V.handleStatement(BI.castAs<CFGStmt>().getStmt()); 149 break; 150 } 151 case CFGElement::AutomaticObjectDtor: { 152 CFGAutomaticObjDtor AD = BI.castAs<CFGAutomaticObjDtor>(); 153 CXXDestructorDecl *DD = const_cast<CXXDestructorDecl*>( 154 AD.getDestructorDecl(ACtx->getASTContext())); 155 VarDecl *VD = const_cast<VarDecl*>(AD.getVarDecl()); 156 V.handleDestructorCall(VD, DD); 157 break; 158 } 159 default: 160 break; 161 } 162 } 163 164 V.exitCFGBlockBody(CurrBlock); 165 166 // Process successors, handling back edges first. 167 if (V.visitSuccessors()) { 168 SmallVector<CFGBlock*, 8> ForwardEdges; 169 170 // Process successors 171 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 172 SE = CurrBlock->succ_end(); 173 SI != SE; ++SI) { 174 if (*SI == nullptr) 175 continue; 176 177 if (!VisitedBlocks.alreadySet(*SI)) { 178 ForwardEdges.push_back(*SI); 179 continue; 180 } 181 V.handleSuccessorBackEdge(*SI); 182 } 183 184 for (auto *Blk : ForwardEdges) 185 V.handleSuccessor(Blk); 186 } 187 188 V.exitCFGBlock(CurrBlock); 189 } 190 V.exitCFG(&CFGraph->getExit()); 191 } 192 193 const CFG *getGraph() const { return CFGraph; } 194 CFG *getGraph() { return CFGraph; } 195 196 const NamedDecl *getDecl() const { 197 return dyn_cast<NamedDecl>(ACtx->getDecl()); 198 } 199 200 const PostOrderCFGView *getSortedGraph() const { return SortedGraph; } 201 202 private: 203 CFG *CFGraph; 204 AnalysisDeclContext *ACtx; 205 PostOrderCFGView *SortedGraph; 206 }; 207 208 209 // Translate clang::Expr to til::SExpr. 210 class SExprBuilder { 211 public: 212 /// \brief Encapsulates the lexical context of a function call. The lexical 213 /// context includes the arguments to the call, including the implicit object 214 /// argument. When an attribute containing a mutex expression is attached to 215 /// a method, the expression may refer to formal parameters of the method. 216 /// Actual arguments must be substituted for formal parameters to derive 217 /// the appropriate mutex expression in the lexical context where the function 218 /// is called. PrevCtx holds the context in which the arguments themselves 219 /// should be evaluated; multiple calling contexts can be chained together 220 /// by the lock_returned attribute. 221 struct CallingContext { 222 const NamedDecl *AttrDecl; // The decl to which the attr is attached. 223 const Expr *SelfArg; // Implicit object argument -- e.g. 'this' 224 unsigned NumArgs; // Number of funArgs 225 const Expr *const *FunArgs; // Function arguments 226 CallingContext *Prev; // The previous context; or 0 if none. 227 bool SelfArrow; // is Self referred to with -> or .? 228 229 CallingContext(const NamedDecl *D = nullptr, const Expr *S = nullptr, 230 unsigned N = 0, const Expr *const *A = nullptr, 231 CallingContext *P = nullptr) 232 : AttrDecl(D), SelfArg(S), NumArgs(N), FunArgs(A), Prev(P), 233 SelfArrow(false) 234 {} 235 }; 236 237 SExprBuilder(til::MemRegionRef A) 238 : Arena(A), SelfVar(nullptr), Scfg(nullptr), CurrentBB(nullptr), 239 CurrentBlockInfo(nullptr) { 240 // FIXME: we don't always have a self-variable. 241 SelfVar = new (Arena) til::Variable(nullptr); 242 SelfVar->setKind(til::Variable::VK_SFun); 243 } 244 245 // Translate a clang statement or expression to a TIL expression. 246 // Also performs substitution of variables; Ctx provides the context. 247 // Dispatches on the type of S. 248 til::SExpr *translate(const Stmt *S, CallingContext *Ctx); 249 til::SCFG *buildCFG(CFGWalker &Walker); 250 251 til::SExpr *lookupStmt(const Stmt *S); 252 253 til::BasicBlock *lookupBlock(const CFGBlock *B) { 254 return BlockMap[B->getBlockID()]; 255 } 256 257 const til::SCFG *getCFG() const { return Scfg; } 258 til::SCFG *getCFG() { return Scfg; } 259 260 private: 261 til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE, 262 CallingContext *Ctx) ; 263 til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx); 264 til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx); 265 til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx); 266 til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME, 267 CallingContext *Ctx); 268 til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE, 269 CallingContext *Ctx); 270 til::SExpr *translateUnaryOperator(const UnaryOperator *UO, 271 CallingContext *Ctx); 272 til::SExpr *translateBinOp(til::TIL_BinaryOpcode Op, 273 const BinaryOperator *BO, 274 CallingContext *Ctx, bool Reverse = false); 275 til::SExpr *translateBinAssign(til::TIL_BinaryOpcode Op, 276 const BinaryOperator *BO, 277 CallingContext *Ctx, bool Assign = false); 278 til::SExpr *translateBinaryOperator(const BinaryOperator *BO, 279 CallingContext *Ctx); 280 til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx); 281 til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E, 282 CallingContext *Ctx); 283 til::SExpr *translateConditionalOperator(const ConditionalOperator *C, 284 CallingContext *Ctx); 285 til::SExpr *translateBinaryConditionalOperator( 286 const BinaryConditionalOperator *C, CallingContext *Ctx); 287 288 til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx); 289 290 // Map from statements in the clang CFG to SExprs in the til::SCFG. 291 typedef llvm::DenseMap<const Stmt*, til::SExpr*> StatementMap; 292 293 // Map from clang local variables to indices in a LVarDefinitionMap. 294 typedef llvm::DenseMap<const ValueDecl *, unsigned> LVarIndexMap; 295 296 // Map from local variable indices to SSA variables (or constants). 297 typedef std::pair<const ValueDecl *, til::SExpr *> NameVarPair; 298 typedef CopyOnWriteVector<NameVarPair> LVarDefinitionMap; 299 300 struct BlockInfo { 301 LVarDefinitionMap ExitMap; 302 bool HasBackEdges; 303 unsigned UnprocessedSuccessors; // Successors yet to be processed 304 unsigned ProcessedPredecessors; // Predecessors already processed 305 306 BlockInfo() 307 : HasBackEdges(false), UnprocessedSuccessors(0), 308 ProcessedPredecessors(0) {} 309 BlockInfo(BlockInfo &&RHS) 310 : ExitMap(std::move(RHS.ExitMap)), 311 HasBackEdges(RHS.HasBackEdges), 312 UnprocessedSuccessors(RHS.UnprocessedSuccessors), 313 ProcessedPredecessors(RHS.ProcessedPredecessors) {} 314 315 BlockInfo &operator=(BlockInfo &&RHS) { 316 if (this != &RHS) { 317 ExitMap = std::move(RHS.ExitMap); 318 HasBackEdges = RHS.HasBackEdges; 319 UnprocessedSuccessors = RHS.UnprocessedSuccessors; 320 ProcessedPredecessors = RHS.ProcessedPredecessors; 321 } 322 return *this; 323 } 324 325 private: 326 BlockInfo(const BlockInfo &) LLVM_DELETED_FUNCTION; 327 void operator=(const BlockInfo &) LLVM_DELETED_FUNCTION; 328 }; 329 330 // We implement the CFGVisitor API 331 friend class CFGWalker; 332 333 void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First); 334 void enterCFGBlock(const CFGBlock *B); 335 bool visitPredecessors() { return true; } 336 void handlePredecessor(const CFGBlock *Pred); 337 void handlePredecessorBackEdge(const CFGBlock *Pred); 338 void enterCFGBlockBody(const CFGBlock *B); 339 void handleStatement(const Stmt *S); 340 void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD); 341 void exitCFGBlockBody(const CFGBlock *B); 342 bool visitSuccessors() { return true; } 343 void handleSuccessor(const CFGBlock *Succ); 344 void handleSuccessorBackEdge(const CFGBlock *Succ); 345 void exitCFGBlock(const CFGBlock *B); 346 void exitCFG(const CFGBlock *Last); 347 348 void insertStmt(const Stmt *S, til::SExpr *E) { 349 SMap.insert(std::make_pair(S, E)); 350 } 351 til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD); 352 353 til::SExpr *addStatement(til::SExpr *E, const Stmt *S, 354 const ValueDecl *VD = nullptr); 355 til::SExpr *lookupVarDecl(const ValueDecl *VD); 356 til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E); 357 til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E); 358 359 void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E); 360 void mergeEntryMap(LVarDefinitionMap Map); 361 void mergeEntryMapBackEdge(); 362 void mergePhiNodesBackEdge(const CFGBlock *Blk); 363 364 private: 365 til::MemRegionRef Arena; 366 til::Variable *SelfVar; // Variable to use for 'this'. May be null. 367 til::SCFG *Scfg; 368 369 StatementMap SMap; // Map from Stmt to TIL Variables 370 LVarIndexMap LVarIdxMap; // Indices of clang local vars. 371 std::vector<til::BasicBlock *> BlockMap; // Map from clang to til BBs. 372 std::vector<BlockInfo> BBInfo; // Extra information per BB. 373 // Indexed by clang BlockID. 374 std::unique_ptr<SExprBuilder::CallingContext> CallCtx; // Root calling context 375 376 LVarDefinitionMap CurrentLVarMap; 377 std::vector<til::Variable*> CurrentArguments; 378 std::vector<til::Variable*> CurrentInstructions; 379 std::vector<til::Variable*> IncompleteArgs; 380 til::BasicBlock *CurrentBB; 381 BlockInfo *CurrentBlockInfo; 382 }; 383 384 385 // Dump an SCFG to llvm::errs(). 386 void printSCFG(CFGWalker &Walker); 387 388 389 } // end namespace threadSafety 390 391 } // end namespace clang 392 393 #endif // LLVM_CLANG_THREAD_SAFETY_COMMON_H 394
