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/PointerIntPair.h" 34 #include "llvm/ADT/SmallVector.h" 35 #include "llvm/Support/Casting.h" 36 #include <sstream> 37 #include <string> 38 #include <utility> 39 #include <vector> 40 41 namespace clang { 42 43 class AbstractConditionalOperator; 44 class ArraySubscriptExpr; 45 class BinaryOperator; 46 class CallExpr; 47 class CastExpr; 48 class CXXDestructorDecl; 49 class CXXMemberCallExpr; 50 class CXXOperatorCallExpr; 51 class CXXThisExpr; 52 class DeclRefExpr; 53 class DeclStmt; 54 class Expr; 55 class MemberExpr; 56 class Stmt; 57 class UnaryOperator; 58 59 namespace threadSafety { 60 61 // Various helper functions on til::SExpr 62 namespace sx { 63 64 inline bool equals(const til::SExpr *E1, const til::SExpr *E2) { 65 return til::EqualsComparator::compareExprs(E1, E2); 66 } 67 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); 76 77 return til::MatchComparator::compareExprs(E1, E2); 78 } 79 80 inline bool partiallyMatches(const til::SExpr *E1, const til::SExpr *E2) { 81 const auto *PE1 = dyn_cast_or_null<til::Project>(E1); 82 if (!PE1) 83 return false; 84 const auto *PE2 = dyn_cast_or_null<til::Project>(E2); 85 if (!PE2) 86 return false; 87 return PE1->clangDecl() == PE2->clangDecl(); 88 } 89 90 inline std::string toString(const til::SExpr *E) { 91 std::stringstream ss; 92 til::StdPrinter::print(E, ss); 93 return ss.str(); 94 } 95 96 } // namespace sx 97 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. 101 class CFGVisitor { 102 // Enter the CFG for Decl D, and perform any initial setup operations. 103 void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First) {} 104 105 // Enter a CFGBlock. 106 void enterCFGBlock(const CFGBlock *B) {} 107 108 // Returns true if this visitor implements handlePredecessor 109 bool visitPredecessors() { return true; } 110 111 // Process a predecessor edge. 112 void handlePredecessor(const CFGBlock *Pred) {} 113 114 // Process a successor back edge to a previously visited block. 115 void handlePredecessorBackEdge(const CFGBlock *Pred) {} 116 117 // Called just before processing statements. 118 void enterCFGBlockBody(const CFGBlock *B) {} 119 120 // Process an ordinary statement. 121 void handleStatement(const Stmt *S) {} 122 123 // Process a destructor call 124 void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD) {} 125 126 // Called after all statements have been handled. 127 void exitCFGBlockBody(const CFGBlock *B) {} 128 129 // Return true 130 bool visitSuccessors() { return true; } 131 132 // Process a successor edge. 133 void handleSuccessor(const CFGBlock *Succ) {} 134 135 // Process a successor back edge to a previously visited block. 136 void handleSuccessorBackEdge(const CFGBlock *Succ) {} 137 138 // Leave a CFGBlock. 139 void exitCFGBlock(const CFGBlock *B) {} 140 141 // Leave the CFG, and perform any final cleanup operations. 142 void exitCFG(const CFGBlock *Last) {} 143 }; 144 145 // Walks the clang CFG, and invokes methods on a given CFGVisitor. 146 class CFGWalker { 147 public: 148 CFGWalker() = default; 149 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) { 153 ACtx = &AC; 154 CFGraph = AC.getCFG(); 155 if (!CFGraph) 156 return false; 157 158 // Ignore anonymous functions. 159 if (!isa_and_nonnull<NamedDecl>(AC.getDecl())) 160 return false; 161 162 SortedGraph = AC.getAnalysis<PostOrderCFGView>(); 163 if (!SortedGraph) 164 return false; 165 166 return true; 167 } 168 169 // Traverse the CFG, calling methods on V as appropriate. 170 template <class Visitor> 171 void walk(Visitor &V) { 172 PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); 173 174 V.enterCFG(CFGraph, getDecl(), &CFGraph->getEntry()); 175 176 for (const auto *CurrBlock : *SortedGraph) { 177 VisitedBlocks.insert(CurrBlock); 178 179 V.enterCFGBlock(CurrBlock); 180 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(); 187 SI != SE; ++SI) { 188 if (*SI == nullptr) 189 continue; 190 191 if (!VisitedBlocks.alreadySet(*SI)) { 192 BackEdges.push_back(*SI); 193 continue; 194 } 195 V.handlePredecessor(*SI); 196 } 197 198 for (auto *Blk : BackEdges) 199 V.handlePredecessorBackEdge(Blk); 200 } 201 202 V.enterCFGBlockBody(CurrBlock); 203 204 // Process statements 205 for (const auto &BI : *CurrBlock) { 206 switch (BI.getKind()) { 207 case CFGElement::Statement: 208 V.handleStatement(BI.castAs<CFGStmt>().getStmt()); 209 break; 210 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); 217 break; 218 } 219 default: 220 break; 221 } 222 } 223 224 V.exitCFGBlockBody(CurrBlock); 225 226 // Process successors, handling back edges first. 227 if (V.visitSuccessors()) { 228 SmallVector<CFGBlock*, 8> ForwardEdges; 229 230 // Process successors 231 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 232 SE = CurrBlock->succ_end(); 233 SI != SE; ++SI) { 234 if (*SI == nullptr) 235 continue; 236 237 if (!VisitedBlocks.alreadySet(*SI)) { 238 ForwardEdges.push_back(*SI); 239 continue; 240 } 241 V.handleSuccessorBackEdge(*SI); 242 } 243 244 for (auto *Blk : ForwardEdges) 245 V.handleSuccessor(Blk); 246 } 247 248 V.exitCFGBlock(CurrBlock); 249 } 250 V.exitCFG(&CFGraph->getExit()); 251 } 252 253 const CFG *getGraph() const { return CFGraph; } 254 CFG *getGraph() { return CFGraph; } 255 256 const NamedDecl *getDecl() const { 257 return dyn_cast<NamedDecl>(ACtx->getDecl()); 258 } 259 260 const PostOrderCFGView *getSortedGraph() const { return SortedGraph; } 261 262 private: 263 CFG *CFGraph = nullptr; 264 AnalysisDeclContext *ACtx = nullptr; 265 PostOrderCFGView *SortedGraph = nullptr; 266 }; 267 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 { 272 private: 273 /// The capability expression and whether it's negated. 274 llvm::PointerIntPair<const til::SExpr *, 1, bool> CapExpr; 275 276 /// The kind of capability as specified by @ref CapabilityAttr::getName. 277 StringRef CapKind; 278 279 public: 280 CapabilityExpr() : CapExpr(nullptr, false) {} 281 CapabilityExpr(const til::SExpr *E, StringRef Kind, bool Neg) 282 : CapExpr(E, Neg), CapKind(Kind) {} 283 284 // Don't allow implicitly-constructed StringRefs since we'll capture them. 285 template <typename T> CapabilityExpr(const til::SExpr *, T, bool) = delete; 286 287 const til::SExpr *sexpr() const { return CapExpr.getPointer(); } 288 StringRef getKind() const { return CapKind; } 289 bool negative() const { return CapExpr.getInt(); } 290 291 CapabilityExpr operator!() const { 292 return CapabilityExpr(CapExpr.getPointer(), CapKind, !CapExpr.getInt()); 293 } 294 295 bool equals(const CapabilityExpr &other) const { 296 return (negative() == other.negative()) && 297 sx::equals(sexpr(), other.sexpr()); 298 } 299 300 bool matches(const CapabilityExpr &other) const { 301 return (negative() == other.negative()) && 302 sx::matches(sexpr(), other.sexpr()); 303 } 304 305 bool matchesUniv(const CapabilityExpr &CapE) const { 306 return isUniversal() || matches(CapE); 307 } 308 309 bool partiallyMatches(const CapabilityExpr &other) const { 310 return (negative() == other.negative()) && 311 sx::partiallyMatches(sexpr(), other.sexpr()); 312 } 313 314 const ValueDecl* valueDecl() const { 315 if (negative() || sexpr() == nullptr) 316 return nullptr; 317 if (const auto *P = dyn_cast<til::Project>(sexpr())) 318 return P->clangDecl(); 319 if (const auto *P = dyn_cast<til::LiteralPtr>(sexpr())) 320 return P->clangDecl(); 321 return nullptr; 322 } 323 324 std::string toString() const { 325 if (negative()) 326 return "!" + sx::toString(sexpr()); 327 return sx::toString(sexpr()); 328 } 329 330 bool shouldIgnore() const { return sexpr() == nullptr; } 331 332 bool isInvalid() const { return sexpr() && isa<til::Undefined>(sexpr()); } 333 334 bool isUniversal() const { return sexpr() && isa<til::Wildcard>(sexpr()); } 335 }; 336 337 // Translate clang::Expr to til::SExpr. 338 class SExprBuilder { 339 public: 340 /// Encapsulates the lexical context of a function call. The lexical 341 /// context includes the arguments to the call, including the implicit object 342 /// argument. When an attribute containing a mutex expression is attached to 343 /// a method, the expression may refer to formal parameters of the method. 344 /// Actual arguments must be substituted for formal parameters to derive 345 /// the appropriate mutex expression in the lexical context where the function 346 /// is called. PrevCtx holds the context in which the arguments themselves 347 /// should be evaluated; multiple calling contexts can be chained together 348 /// by the lock_returned attribute. 349 struct CallingContext { 350 // The previous context; or 0 if none. 351 CallingContext *Prev; 352 353 // The decl to which the attr is attached. 354 const NamedDecl *AttrDecl; 355 356 // Implicit object argument -- e.g. 'this' 357 const Expr *SelfArg = nullptr; 358 359 // Number of funArgs 360 unsigned NumArgs = 0; 361 362 // Function arguments 363 const Expr *const *FunArgs = nullptr; 364 365 // is Self referred to with -> or .? 366 bool SelfArrow = false; 367 368 CallingContext(CallingContext *P, const NamedDecl *D = nullptr) 369 : Prev(P), AttrDecl(D) {} 370 }; 371 372 SExprBuilder(til::MemRegionRef A) : Arena(A) { 373 // FIXME: we don't always have a self-variable. 374 SelfVar = new (Arena) til::Variable(nullptr); 375 SelfVar->setKind(til::Variable::VK_SFun); 376 } 377 378 // Translate a clang expression in an attribute to a til::SExpr. 379 // Constructs the context from D, DeclExp, and SelfDecl. 380 CapabilityExpr translateAttrExpr(const Expr *AttrExp, const NamedDecl *D, 381 const Expr *DeclExp, VarDecl *SelfD=nullptr); 382 383 CapabilityExpr translateAttrExpr(const Expr *AttrExp, CallingContext *Ctx); 384 385 // Translate a clang statement or expression to a TIL expression. 386 // Also performs substitution of variables; Ctx provides the context. 387 // Dispatches on the type of S. 388 til::SExpr *translate(const Stmt *S, CallingContext *Ctx); 389 til::SCFG *buildCFG(CFGWalker &Walker); 390 391 til::SExpr *lookupStmt(const Stmt *S); 392 393 til::BasicBlock *lookupBlock(const CFGBlock *B) { 394 return BlockMap[B->getBlockID()]; 395 } 396 397 const til::SCFG *getCFG() const { return Scfg; } 398 til::SCFG *getCFG() { return Scfg; } 399 400 private: 401 // We implement the CFGVisitor API 402 friend class CFGWalker; 403 404 til::SExpr *translateDeclRefExpr(const DeclRefExpr *DRE, 405 CallingContext *Ctx) ; 406 til::SExpr *translateCXXThisExpr(const CXXThisExpr *TE, CallingContext *Ctx); 407 til::SExpr *translateMemberExpr(const MemberExpr *ME, CallingContext *Ctx); 408 til::SExpr *translateObjCIVarRefExpr(const ObjCIvarRefExpr *IVRE, 409 CallingContext *Ctx); 410 til::SExpr *translateCallExpr(const CallExpr *CE, CallingContext *Ctx, 411 const Expr *SelfE = nullptr); 412 til::SExpr *translateCXXMemberCallExpr(const CXXMemberCallExpr *ME, 413 CallingContext *Ctx); 414 til::SExpr *translateCXXOperatorCallExpr(const CXXOperatorCallExpr *OCE, 415 CallingContext *Ctx); 416 til::SExpr *translateUnaryOperator(const UnaryOperator *UO, 417 CallingContext *Ctx); 418 til::SExpr *translateBinOp(til::TIL_BinaryOpcode Op, 419 const BinaryOperator *BO, 420 CallingContext *Ctx, bool Reverse = false); 421 til::SExpr *translateBinAssign(til::TIL_BinaryOpcode Op, 422 const BinaryOperator *BO, 423 CallingContext *Ctx, bool Assign = false); 424 til::SExpr *translateBinaryOperator(const BinaryOperator *BO, 425 CallingContext *Ctx); 426 til::SExpr *translateCastExpr(const CastExpr *CE, CallingContext *Ctx); 427 til::SExpr *translateArraySubscriptExpr(const ArraySubscriptExpr *E, 428 CallingContext *Ctx); 429 til::SExpr *translateAbstractConditionalOperator( 430 const AbstractConditionalOperator *C, CallingContext *Ctx); 431 432 til::SExpr *translateDeclStmt(const DeclStmt *S, CallingContext *Ctx); 433 434 // Map from statements in the clang CFG to SExprs in the til::SCFG. 435 using StatementMap = llvm::DenseMap<const Stmt *, til::SExpr *>; 436 437 // Map from clang local variables to indices in a LVarDefinitionMap. 438 using LVarIndexMap = llvm::DenseMap<const ValueDecl *, unsigned>; 439 440 // Map from local variable indices to SSA variables (or constants). 441 using NameVarPair = std::pair<const ValueDecl *, til::SExpr *>; 442 using LVarDefinitionMap = CopyOnWriteVector<NameVarPair>; 443 444 struct BlockInfo { 445 LVarDefinitionMap ExitMap; 446 bool HasBackEdges = false; 447 448 // Successors yet to be processed 449 unsigned UnprocessedSuccessors = 0; 450 451 // Predecessors already processed 452 unsigned ProcessedPredecessors = 0; 453 454 BlockInfo() = default; 455 BlockInfo(BlockInfo &&) = default; 456 BlockInfo &operator=(BlockInfo &&) = default; 457 }; 458 459 void enterCFG(CFG *Cfg, const NamedDecl *D, const CFGBlock *First); 460 void enterCFGBlock(const CFGBlock *B); 461 bool visitPredecessors() { return true; } 462 void handlePredecessor(const CFGBlock *Pred); 463 void handlePredecessorBackEdge(const CFGBlock *Pred); 464 void enterCFGBlockBody(const CFGBlock *B); 465 void handleStatement(const Stmt *S); 466 void handleDestructorCall(const VarDecl *VD, const CXXDestructorDecl *DD); 467 void exitCFGBlockBody(const CFGBlock *B); 468 bool visitSuccessors() { return true; } 469 void handleSuccessor(const CFGBlock *Succ); 470 void handleSuccessorBackEdge(const CFGBlock *Succ); 471 void exitCFGBlock(const CFGBlock *B); 472 void exitCFG(const CFGBlock *Last); 473 474 void insertStmt(const Stmt *S, til::SExpr *E) { 475 SMap.insert(std::make_pair(S, E)); 476 } 477 478 til::SExpr *getCurrentLVarDefinition(const ValueDecl *VD); 479 480 til::SExpr *addStatement(til::SExpr *E, const Stmt *S, 481 const ValueDecl *VD = nullptr); 482 til::SExpr *lookupVarDecl(const ValueDecl *VD); 483 til::SExpr *addVarDecl(const ValueDecl *VD, til::SExpr *E); 484 til::SExpr *updateVarDecl(const ValueDecl *VD, til::SExpr *E); 485 486 void makePhiNodeVar(unsigned i, unsigned NPreds, til::SExpr *E); 487 void mergeEntryMap(LVarDefinitionMap Map); 488 void mergeEntryMapBackEdge(); 489 void mergePhiNodesBackEdge(const CFGBlock *Blk); 490 491 private: 492 // Set to true when parsing capability expressions, which get translated 493 // inaccurately in order to hack around smart pointers etc. 494 static const bool CapabilityExprMode = true; 495 496 til::MemRegionRef Arena; 497 498 // Variable to use for 'this'. May be null. 499 til::Variable *SelfVar = nullptr; 500 501 til::SCFG *Scfg = nullptr; 502 503 // Map from Stmt to TIL Variables 504 StatementMap SMap; 505 506 // Indices of clang local vars. 507 LVarIndexMap LVarIdxMap; 508 509 // Map from clang to til BBs. 510 std::vector<til::BasicBlock *> BlockMap; 511 512 // Extra information per BB. Indexed by clang BlockID. 513 std::vector<BlockInfo> BBInfo; 514 515 LVarDefinitionMap CurrentLVarMap; 516 std::vector<til::Phi *> CurrentArguments; 517 std::vector<til::SExpr *> CurrentInstructions; 518 std::vector<til::Phi *> IncompleteArgs; 519 til::BasicBlock *CurrentBB = nullptr; 520 BlockInfo *CurrentBlockInfo = nullptr; 521 }; 522 523 // Dump an SCFG to llvm::errs(). 524 void printSCFG(CFGWalker &Walker); 525 526 } // namespace threadSafety 527 } // namespace clang 528 529 #endif // LLVM_CLANG_ANALYSIS_ANALYSES_THREADSAFETYCOMMON_H 530