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 43 inline bool equals(const til::SExpr *E1, const til::SExpr *E2) { 44 return til::EqualsComparator::compareExprs(E1, E2); 45 } 46 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 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 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. 84 void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {} 85 86 // Enter a CFGBlock. 87 void enterCFGBlock(const CFGBlock *B) {} 88 89 // Returns true if this visitor implements handlePredecessor 90 bool visitPredecessors() { return true; } 91 92 // Process a predecessor edge. 93 void handlePredecessor(const CFGBlock *Pred) {} 94 95 // Process a successor back edge to a previously visited block. 96 void handlePredecessorBackEdge(const CFGBlock *Pred) {} 97 98 // Called just before processing statements. 99 void enterCFGBlockBody(const CFGBlock *B) {} 100 101 // Process an ordinary statement. 102 void handleStatement(const Stmt *S) {} 103 104 // Process a destructor call 105 void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {} 106 107 // Called after all statements have been handled. 108 void exitCFGBlockBody(const CFGBlock *B) {} 109 110 // Return true 111 bool visitSuccessors() { return true; } 112 113 // Process a successor edge. 114 void handleSuccessor(const CFGBlock *Succ) {} 115 116 // Process a successor back edge to a previously visited block. 117 void handleSuccessorBackEdge(const CFGBlock *Succ) {} 118 119 // Leave a CFGBlock. 120 void exitCFGBlock(const CFGBlock *B) {} 121 122 // Leave the CFG, and perform any final cleanup operations. 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: 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. 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> 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 235 const CFG *getGraph() const { return CFGraph; } 236 CFG *getGraph() { return CFGraph; } 237 238 const NamedDecl *getDecl() const { 239 return dyn_cast<NamedDecl>(ACtx->getDecl()); 240 } 241 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: 263 CapabilityExpr(const til::SExpr *E, bool Neg) : CapExpr(E), Negated(Neg) {} 264 265 const til::SExpr* sexpr() const { return CapExpr; } 266 bool negative() const { return Negated; } 267 268 CapabilityExpr operator!() const { 269 return CapabilityExpr(CapExpr, !Negated); 270 } 271 272 bool equals(const CapabilityExpr &other) const { 273 return (Negated == other.Negated) && sx::equals(CapExpr, other.CapExpr); 274 } 275 276 bool matches(const CapabilityExpr &other) const { 277 return (Negated == other.Negated) && sx::matches(CapExpr, other.CapExpr); 278 } 279 280 bool matchesUniv(const CapabilityExpr &CapE) const { 281 return isUniversal() || matches(CapE); 282 } 283 284 bool partiallyMatches(const CapabilityExpr &other) const { 285 return (Negated == other.Negated) && 286 sx::partiallyMatches(CapExpr, other.CapExpr); 287 } 288 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 299 std::string toString() const { 300 if (Negated) 301 return "!" + sx::toString(CapExpr); 302 return sx::toString(CapExpr); 303 } 304 305 bool shouldIgnore() const { return CapExpr == nullptr; } 306 307 bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); } 308 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) 335 : Prev(P), AttrDecl(D), SelfArg(nullptr), 336 NumArgs(0), FunArgs(nullptr), SelfArrow(false) 337 {} 338 }; 339 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 363 til::BasicBlock *lookupBlock(const CFGBlock *B) { 364 return BlockMap[B->getBlockID()]; 365 } 366 367 const til::SCFG *getCFG() const { return Scfg; } 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 415 BlockInfo() 416 : HasBackEdges(false), UnprocessedSuccessors(0), 417 ProcessedPredecessors(0) {} 418 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); 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); 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 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