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