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