1 //===- ThreadSafety.cpp ----------------------------------------*- 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 // A intra-procedural analysis for thread safety (e.g. deadlocks and race 11 // conditions), based off of an annotation system. 12 // 13 // See http://clang.llvm.org/docs/LanguageExtensions.html#threadsafety for more 14 // information. 15 // 16 //===----------------------------------------------------------------------===// 17 18 #include "clang/Analysis/Analyses/ThreadSafety.h" 19 #include "clang/Analysis/Analyses/PostOrderCFGView.h" 20 #include "clang/Analysis/AnalysisContext.h" 21 #include "clang/Analysis/CFG.h" 22 #include "clang/Analysis/CFGStmtMap.h" 23 #include "clang/AST/DeclCXX.h" 24 #include "clang/AST/ExprCXX.h" 25 #include "clang/AST/StmtCXX.h" 26 #include "clang/AST/StmtVisitor.h" 27 #include "clang/Basic/SourceManager.h" 28 #include "clang/Basic/SourceLocation.h" 29 #include "clang/Basic/OperatorKinds.h" 30 #include "llvm/ADT/BitVector.h" 31 #include "llvm/ADT/FoldingSet.h" 32 #include "llvm/ADT/ImmutableMap.h" 33 #include "llvm/ADT/PostOrderIterator.h" 34 #include "llvm/ADT/SmallVector.h" 35 #include "llvm/ADT/StringRef.h" 36 #include "llvm/Support/raw_ostream.h" 37 #include <algorithm> 38 #include <utility> 39 #include <vector> 40 41 using namespace clang; 42 using namespace thread_safety; 43 44 // Key method definition 45 ThreadSafetyHandler::~ThreadSafetyHandler() {} 46 47 namespace { 48 49 /// SExpr implements a simple expression language that is used to store, 50 /// compare, and pretty-print C++ expressions. Unlike a clang Expr, a SExpr 51 /// does not capture surface syntax, and it does not distinguish between 52 /// C++ concepts, like pointers and references, that have no real semantic 53 /// differences. This simplicity allows SExprs to be meaningfully compared, 54 /// e.g. 55 /// (x) = x 56 /// (*this).foo = this->foo 57 /// *&a = a 58 /// 59 /// Thread-safety analysis works by comparing lock expressions. Within the 60 /// body of a function, an expression such as "x->foo->bar.mu" will resolve to 61 /// a particular mutex object at run-time. Subsequent occurrences of the same 62 /// expression (where "same" means syntactic equality) will refer to the same 63 /// run-time object if three conditions hold: 64 /// (1) Local variables in the expression, such as "x" have not changed. 65 /// (2) Values on the heap that affect the expression have not changed. 66 /// (3) The expression involves only pure function calls. 67 /// 68 /// The current implementation assumes, but does not verify, that multiple uses 69 /// of the same lock expression satisfies these criteria. 70 class SExpr { 71 private: 72 enum ExprOp { 73 EOP_Nop, ///< No-op 74 EOP_Wildcard, ///< Matches anything. 75 EOP_Universal, ///< Universal lock. 76 EOP_This, ///< This keyword. 77 EOP_NVar, ///< Named variable. 78 EOP_LVar, ///< Local variable. 79 EOP_Dot, ///< Field access 80 EOP_Call, ///< Function call 81 EOP_MCall, ///< Method call 82 EOP_Index, ///< Array index 83 EOP_Unary, ///< Unary operation 84 EOP_Binary, ///< Binary operation 85 EOP_Unknown ///< Catchall for everything else 86 }; 87 88 89 class SExprNode { 90 private: 91 unsigned char Op; ///< Opcode of the root node 92 unsigned char Flags; ///< Additional opcode-specific data 93 unsigned short Sz; ///< Number of child nodes 94 const void* Data; ///< Additional opcode-specific data 95 96 public: 97 SExprNode(ExprOp O, unsigned F, const void* D) 98 : Op(static_cast<unsigned char>(O)), 99 Flags(static_cast<unsigned char>(F)), Sz(1), Data(D) 100 { } 101 102 unsigned size() const { return Sz; } 103 void setSize(unsigned S) { Sz = S; } 104 105 ExprOp kind() const { return static_cast<ExprOp>(Op); } 106 107 const NamedDecl* getNamedDecl() const { 108 assert(Op == EOP_NVar || Op == EOP_LVar || Op == EOP_Dot); 109 return reinterpret_cast<const NamedDecl*>(Data); 110 } 111 112 const NamedDecl* getFunctionDecl() const { 113 assert(Op == EOP_Call || Op == EOP_MCall); 114 return reinterpret_cast<const NamedDecl*>(Data); 115 } 116 117 bool isArrow() const { return Op == EOP_Dot && Flags == 1; } 118 void setArrow(bool A) { Flags = A ? 1 : 0; } 119 120 unsigned arity() const { 121 switch (Op) { 122 case EOP_Nop: return 0; 123 case EOP_Wildcard: return 0; 124 case EOP_Universal: return 0; 125 case EOP_NVar: return 0; 126 case EOP_LVar: return 0; 127 case EOP_This: return 0; 128 case EOP_Dot: return 1; 129 case EOP_Call: return Flags+1; // First arg is function. 130 case EOP_MCall: return Flags+1; // First arg is implicit obj. 131 case EOP_Index: return 2; 132 case EOP_Unary: return 1; 133 case EOP_Binary: return 2; 134 case EOP_Unknown: return Flags; 135 } 136 return 0; 137 } 138 139 bool operator==(const SExprNode& Other) const { 140 // Ignore flags and size -- they don't matter. 141 return (Op == Other.Op && 142 Data == Other.Data); 143 } 144 145 bool operator!=(const SExprNode& Other) const { 146 return !(*this == Other); 147 } 148 149 bool matches(const SExprNode& Other) const { 150 return (*this == Other) || 151 (Op == EOP_Wildcard) || 152 (Other.Op == EOP_Wildcard); 153 } 154 }; 155 156 157 /// \brief Encapsulates the lexical context of a function call. The lexical 158 /// context includes the arguments to the call, including the implicit object 159 /// argument. When an attribute containing a mutex expression is attached to 160 /// a method, the expression may refer to formal parameters of the method. 161 /// Actual arguments must be substituted for formal parameters to derive 162 /// the appropriate mutex expression in the lexical context where the function 163 /// is called. PrevCtx holds the context in which the arguments themselves 164 /// should be evaluated; multiple calling contexts can be chained together 165 /// by the lock_returned attribute. 166 struct CallingContext { 167 const NamedDecl* AttrDecl; // The decl to which the attribute is attached. 168 Expr* SelfArg; // Implicit object argument -- e.g. 'this' 169 bool SelfArrow; // is Self referred to with -> or .? 170 unsigned NumArgs; // Number of funArgs 171 Expr** FunArgs; // Function arguments 172 CallingContext* PrevCtx; // The previous context; or 0 if none. 173 174 CallingContext(const NamedDecl *D = 0, Expr *S = 0, 175 unsigned N = 0, Expr **A = 0, CallingContext *P = 0) 176 : AttrDecl(D), SelfArg(S), SelfArrow(false), 177 NumArgs(N), FunArgs(A), PrevCtx(P) 178 { } 179 }; 180 181 typedef SmallVector<SExprNode, 4> NodeVector; 182 183 private: 184 // A SExpr is a list of SExprNodes in prefix order. The Size field allows 185 // the list to be traversed as a tree. 186 NodeVector NodeVec; 187 188 private: 189 unsigned makeNop() { 190 NodeVec.push_back(SExprNode(EOP_Nop, 0, 0)); 191 return NodeVec.size()-1; 192 } 193 194 unsigned makeWildcard() { 195 NodeVec.push_back(SExprNode(EOP_Wildcard, 0, 0)); 196 return NodeVec.size()-1; 197 } 198 199 unsigned makeUniversal() { 200 NodeVec.push_back(SExprNode(EOP_Universal, 0, 0)); 201 return NodeVec.size()-1; 202 } 203 204 unsigned makeNamedVar(const NamedDecl *D) { 205 NodeVec.push_back(SExprNode(EOP_NVar, 0, D)); 206 return NodeVec.size()-1; 207 } 208 209 unsigned makeLocalVar(const NamedDecl *D) { 210 NodeVec.push_back(SExprNode(EOP_LVar, 0, D)); 211 return NodeVec.size()-1; 212 } 213 214 unsigned makeThis() { 215 NodeVec.push_back(SExprNode(EOP_This, 0, 0)); 216 return NodeVec.size()-1; 217 } 218 219 unsigned makeDot(const NamedDecl *D, bool Arrow) { 220 NodeVec.push_back(SExprNode(EOP_Dot, Arrow ? 1 : 0, D)); 221 return NodeVec.size()-1; 222 } 223 224 unsigned makeCall(unsigned NumArgs, const NamedDecl *D) { 225 NodeVec.push_back(SExprNode(EOP_Call, NumArgs, D)); 226 return NodeVec.size()-1; 227 } 228 229 unsigned makeMCall(unsigned NumArgs, const NamedDecl *D) { 230 NodeVec.push_back(SExprNode(EOP_MCall, NumArgs, D)); 231 return NodeVec.size()-1; 232 } 233 234 unsigned makeIndex() { 235 NodeVec.push_back(SExprNode(EOP_Index, 0, 0)); 236 return NodeVec.size()-1; 237 } 238 239 unsigned makeUnary() { 240 NodeVec.push_back(SExprNode(EOP_Unary, 0, 0)); 241 return NodeVec.size()-1; 242 } 243 244 unsigned makeBinary() { 245 NodeVec.push_back(SExprNode(EOP_Binary, 0, 0)); 246 return NodeVec.size()-1; 247 } 248 249 unsigned makeUnknown(unsigned Arity) { 250 NodeVec.push_back(SExprNode(EOP_Unknown, Arity, 0)); 251 return NodeVec.size()-1; 252 } 253 254 /// Build an SExpr from the given C++ expression. 255 /// Recursive function that terminates on DeclRefExpr. 256 /// Note: this function merely creates a SExpr; it does not check to 257 /// ensure that the original expression is a valid mutex expression. 258 /// 259 /// NDeref returns the number of Derefence and AddressOf operations 260 /// preceeding the Expr; this is used to decide whether to pretty-print 261 /// SExprs with . or ->. 262 unsigned buildSExpr(Expr *Exp, CallingContext* CallCtx, int* NDeref = 0) { 263 if (!Exp) 264 return 0; 265 266 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Exp)) { 267 NamedDecl *ND = cast<NamedDecl>(DRE->getDecl()->getCanonicalDecl()); 268 ParmVarDecl *PV = dyn_cast_or_null<ParmVarDecl>(ND); 269 if (PV) { 270 FunctionDecl *FD = 271 cast<FunctionDecl>(PV->getDeclContext())->getCanonicalDecl(); 272 unsigned i = PV->getFunctionScopeIndex(); 273 274 if (CallCtx && CallCtx->FunArgs && 275 FD == CallCtx->AttrDecl->getCanonicalDecl()) { 276 // Substitute call arguments for references to function parameters 277 assert(i < CallCtx->NumArgs); 278 return buildSExpr(CallCtx->FunArgs[i], CallCtx->PrevCtx, NDeref); 279 } 280 // Map the param back to the param of the original function declaration. 281 makeNamedVar(FD->getParamDecl(i)); 282 return 1; 283 } 284 // Not a function parameter -- just store the reference. 285 makeNamedVar(ND); 286 return 1; 287 } else if (isa<CXXThisExpr>(Exp)) { 288 // Substitute parent for 'this' 289 if (CallCtx && CallCtx->SelfArg) { 290 if (!CallCtx->SelfArrow && NDeref) 291 // 'this' is a pointer, but self is not, so need to take address. 292 --(*NDeref); 293 return buildSExpr(CallCtx->SelfArg, CallCtx->PrevCtx, NDeref); 294 } 295 else { 296 makeThis(); 297 return 1; 298 } 299 } else if (MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) { 300 NamedDecl *ND = ME->getMemberDecl(); 301 int ImplicitDeref = ME->isArrow() ? 1 : 0; 302 unsigned Root = makeDot(ND, false); 303 unsigned Sz = buildSExpr(ME->getBase(), CallCtx, &ImplicitDeref); 304 NodeVec[Root].setArrow(ImplicitDeref > 0); 305 NodeVec[Root].setSize(Sz + 1); 306 return Sz + 1; 307 } else if (CXXMemberCallExpr *CMCE = dyn_cast<CXXMemberCallExpr>(Exp)) { 308 // When calling a function with a lock_returned attribute, replace 309 // the function call with the expression in lock_returned. 310 CXXMethodDecl* MD = 311 cast<CXXMethodDecl>(CMCE->getMethodDecl()->getMostRecentDecl()); 312 if (LockReturnedAttr* At = MD->getAttr<LockReturnedAttr>()) { 313 CallingContext LRCallCtx(CMCE->getMethodDecl()); 314 LRCallCtx.SelfArg = CMCE->getImplicitObjectArgument(); 315 LRCallCtx.SelfArrow = 316 dyn_cast<MemberExpr>(CMCE->getCallee())->isArrow(); 317 LRCallCtx.NumArgs = CMCE->getNumArgs(); 318 LRCallCtx.FunArgs = CMCE->getArgs(); 319 LRCallCtx.PrevCtx = CallCtx; 320 return buildSExpr(At->getArg(), &LRCallCtx); 321 } 322 // Hack to treat smart pointers and iterators as pointers; 323 // ignore any method named get(). 324 if (CMCE->getMethodDecl()->getNameAsString() == "get" && 325 CMCE->getNumArgs() == 0) { 326 if (NDeref && dyn_cast<MemberExpr>(CMCE->getCallee())->isArrow()) 327 ++(*NDeref); 328 return buildSExpr(CMCE->getImplicitObjectArgument(), CallCtx, NDeref); 329 } 330 unsigned NumCallArgs = CMCE->getNumArgs(); 331 unsigned Root = 332 makeMCall(NumCallArgs, CMCE->getMethodDecl()->getCanonicalDecl()); 333 unsigned Sz = buildSExpr(CMCE->getImplicitObjectArgument(), CallCtx); 334 Expr** CallArgs = CMCE->getArgs(); 335 for (unsigned i = 0; i < NumCallArgs; ++i) { 336 Sz += buildSExpr(CallArgs[i], CallCtx); 337 } 338 NodeVec[Root].setSize(Sz + 1); 339 return Sz + 1; 340 } else if (CallExpr *CE = dyn_cast<CallExpr>(Exp)) { 341 FunctionDecl* FD = 342 cast<FunctionDecl>(CE->getDirectCallee()->getMostRecentDecl()); 343 if (LockReturnedAttr* At = FD->getAttr<LockReturnedAttr>()) { 344 CallingContext LRCallCtx(CE->getDirectCallee()); 345 LRCallCtx.NumArgs = CE->getNumArgs(); 346 LRCallCtx.FunArgs = CE->getArgs(); 347 LRCallCtx.PrevCtx = CallCtx; 348 return buildSExpr(At->getArg(), &LRCallCtx); 349 } 350 // Treat smart pointers and iterators as pointers; 351 // ignore the * and -> operators. 352 if (CXXOperatorCallExpr *OE = dyn_cast<CXXOperatorCallExpr>(CE)) { 353 OverloadedOperatorKind k = OE->getOperator(); 354 if (k == OO_Star) { 355 if (NDeref) ++(*NDeref); 356 return buildSExpr(OE->getArg(0), CallCtx, NDeref); 357 } 358 else if (k == OO_Arrow) { 359 return buildSExpr(OE->getArg(0), CallCtx, NDeref); 360 } 361 } 362 unsigned NumCallArgs = CE->getNumArgs(); 363 unsigned Root = makeCall(NumCallArgs, 0); 364 unsigned Sz = buildSExpr(CE->getCallee(), CallCtx); 365 Expr** CallArgs = CE->getArgs(); 366 for (unsigned i = 0; i < NumCallArgs; ++i) { 367 Sz += buildSExpr(CallArgs[i], CallCtx); 368 } 369 NodeVec[Root].setSize(Sz+1); 370 return Sz+1; 371 } else if (BinaryOperator *BOE = dyn_cast<BinaryOperator>(Exp)) { 372 unsigned Root = makeBinary(); 373 unsigned Sz = buildSExpr(BOE->getLHS(), CallCtx); 374 Sz += buildSExpr(BOE->getRHS(), CallCtx); 375 NodeVec[Root].setSize(Sz); 376 return Sz; 377 } else if (UnaryOperator *UOE = dyn_cast<UnaryOperator>(Exp)) { 378 // Ignore & and * operators -- they're no-ops. 379 // However, we try to figure out whether the expression is a pointer, 380 // so we can use . and -> appropriately in error messages. 381 if (UOE->getOpcode() == UO_Deref) { 382 if (NDeref) ++(*NDeref); 383 return buildSExpr(UOE->getSubExpr(), CallCtx, NDeref); 384 } 385 if (UOE->getOpcode() == UO_AddrOf) { 386 if (DeclRefExpr* DRE = dyn_cast<DeclRefExpr>(UOE->getSubExpr())) { 387 if (DRE->getDecl()->isCXXInstanceMember()) { 388 // This is a pointer-to-member expression, e.g. &MyClass::mu_. 389 // We interpret this syntax specially, as a wildcard. 390 unsigned Root = makeDot(DRE->getDecl(), false); 391 makeWildcard(); 392 NodeVec[Root].setSize(2); 393 return 2; 394 } 395 } 396 if (NDeref) --(*NDeref); 397 return buildSExpr(UOE->getSubExpr(), CallCtx, NDeref); 398 } 399 unsigned Root = makeUnary(); 400 unsigned Sz = buildSExpr(UOE->getSubExpr(), CallCtx); 401 NodeVec[Root].setSize(Sz); 402 return Sz; 403 } else if (ArraySubscriptExpr *ASE = dyn_cast<ArraySubscriptExpr>(Exp)) { 404 unsigned Root = makeIndex(); 405 unsigned Sz = buildSExpr(ASE->getBase(), CallCtx); 406 Sz += buildSExpr(ASE->getIdx(), CallCtx); 407 NodeVec[Root].setSize(Sz); 408 return Sz; 409 } else if (AbstractConditionalOperator *CE = 410 dyn_cast<AbstractConditionalOperator>(Exp)) { 411 unsigned Root = makeUnknown(3); 412 unsigned Sz = buildSExpr(CE->getCond(), CallCtx); 413 Sz += buildSExpr(CE->getTrueExpr(), CallCtx); 414 Sz += buildSExpr(CE->getFalseExpr(), CallCtx); 415 NodeVec[Root].setSize(Sz); 416 return Sz; 417 } else if (ChooseExpr *CE = dyn_cast<ChooseExpr>(Exp)) { 418 unsigned Root = makeUnknown(3); 419 unsigned Sz = buildSExpr(CE->getCond(), CallCtx); 420 Sz += buildSExpr(CE->getLHS(), CallCtx); 421 Sz += buildSExpr(CE->getRHS(), CallCtx); 422 NodeVec[Root].setSize(Sz); 423 return Sz; 424 } else if (CastExpr *CE = dyn_cast<CastExpr>(Exp)) { 425 return buildSExpr(CE->getSubExpr(), CallCtx, NDeref); 426 } else if (ParenExpr *PE = dyn_cast<ParenExpr>(Exp)) { 427 return buildSExpr(PE->getSubExpr(), CallCtx, NDeref); 428 } else if (ExprWithCleanups *EWC = dyn_cast<ExprWithCleanups>(Exp)) { 429 return buildSExpr(EWC->getSubExpr(), CallCtx, NDeref); 430 } else if (CXXBindTemporaryExpr *E = dyn_cast<CXXBindTemporaryExpr>(Exp)) { 431 return buildSExpr(E->getSubExpr(), CallCtx, NDeref); 432 } else if (isa<CharacterLiteral>(Exp) || 433 isa<CXXNullPtrLiteralExpr>(Exp) || 434 isa<GNUNullExpr>(Exp) || 435 isa<CXXBoolLiteralExpr>(Exp) || 436 isa<FloatingLiteral>(Exp) || 437 isa<ImaginaryLiteral>(Exp) || 438 isa<IntegerLiteral>(Exp) || 439 isa<StringLiteral>(Exp) || 440 isa<ObjCStringLiteral>(Exp)) { 441 makeNop(); 442 return 1; // FIXME: Ignore literals for now 443 } else { 444 makeNop(); 445 return 1; // Ignore. FIXME: mark as invalid expression? 446 } 447 } 448 449 /// \brief Construct a SExpr from an expression. 450 /// \param MutexExp The original mutex expression within an attribute 451 /// \param DeclExp An expression involving the Decl on which the attribute 452 /// occurs. 453 /// \param D The declaration to which the lock/unlock attribute is attached. 454 void buildSExprFromExpr(Expr *MutexExp, Expr *DeclExp, const NamedDecl *D) { 455 CallingContext CallCtx(D); 456 457 458 if (MutexExp) { 459 if (StringLiteral* SLit = dyn_cast<StringLiteral>(MutexExp)) { 460 if (SLit->getString() == StringRef("*")) 461 // The "*" expr is a universal lock, which essentially turns off 462 // checks until it is removed from the lockset. 463 makeUniversal(); 464 else 465 // Ignore other string literals for now. 466 makeNop(); 467 return; 468 } 469 } 470 471 // If we are processing a raw attribute expression, with no substitutions. 472 if (DeclExp == 0) { 473 buildSExpr(MutexExp, 0); 474 return; 475 } 476 477 // Examine DeclExp to find SelfArg and FunArgs, which are used to substitute 478 // for formal parameters when we call buildMutexID later. 479 if (MemberExpr *ME = dyn_cast<MemberExpr>(DeclExp)) { 480 CallCtx.SelfArg = ME->getBase(); 481 CallCtx.SelfArrow = ME->isArrow(); 482 } else if (CXXMemberCallExpr *CE = dyn_cast<CXXMemberCallExpr>(DeclExp)) { 483 CallCtx.SelfArg = CE->getImplicitObjectArgument(); 484 CallCtx.SelfArrow = dyn_cast<MemberExpr>(CE->getCallee())->isArrow(); 485 CallCtx.NumArgs = CE->getNumArgs(); 486 CallCtx.FunArgs = CE->getArgs(); 487 } else if (CallExpr *CE = dyn_cast<CallExpr>(DeclExp)) { 488 CallCtx.NumArgs = CE->getNumArgs(); 489 CallCtx.FunArgs = CE->getArgs(); 490 } else if (CXXConstructExpr *CE = dyn_cast<CXXConstructExpr>(DeclExp)) { 491 CallCtx.SelfArg = 0; // FIXME -- get the parent from DeclStmt 492 CallCtx.NumArgs = CE->getNumArgs(); 493 CallCtx.FunArgs = CE->getArgs(); 494 } else if (D && isa<CXXDestructorDecl>(D)) { 495 // There's no such thing as a "destructor call" in the AST. 496 CallCtx.SelfArg = DeclExp; 497 } 498 499 // If the attribute has no arguments, then assume the argument is "this". 500 if (MutexExp == 0) { 501 buildSExpr(CallCtx.SelfArg, 0); 502 return; 503 } 504 505 // For most attributes. 506 buildSExpr(MutexExp, &CallCtx); 507 } 508 509 /// \brief Get index of next sibling of node i. 510 unsigned getNextSibling(unsigned i) const { 511 return i + NodeVec[i].size(); 512 } 513 514 public: 515 explicit SExpr(clang::Decl::EmptyShell e) { NodeVec.clear(); } 516 517 /// \param MutexExp The original mutex expression within an attribute 518 /// \param DeclExp An expression involving the Decl on which the attribute 519 /// occurs. 520 /// \param D The declaration to which the lock/unlock attribute is attached. 521 /// Caller must check isValid() after construction. 522 SExpr(Expr* MutexExp, Expr *DeclExp, const NamedDecl* D) { 523 buildSExprFromExpr(MutexExp, DeclExp, D); 524 } 525 526 /// Return true if this is a valid decl sequence. 527 /// Caller must call this by hand after construction to handle errors. 528 bool isValid() const { 529 return !NodeVec.empty(); 530 } 531 532 bool shouldIgnore() const { 533 // Nop is a mutex that we have decided to deliberately ignore. 534 assert(NodeVec.size() > 0 && "Invalid Mutex"); 535 return NodeVec[0].kind() == EOP_Nop; 536 } 537 538 bool isUniversal() const { 539 assert(NodeVec.size() > 0 && "Invalid Mutex"); 540 return NodeVec[0].kind() == EOP_Universal; 541 } 542 543 /// Issue a warning about an invalid lock expression 544 static void warnInvalidLock(ThreadSafetyHandler &Handler, Expr* MutexExp, 545 Expr *DeclExp, const NamedDecl* D) { 546 SourceLocation Loc; 547 if (DeclExp) 548 Loc = DeclExp->getExprLoc(); 549 550 // FIXME: add a note about the attribute location in MutexExp or D 551 if (Loc.isValid()) 552 Handler.handleInvalidLockExp(Loc); 553 } 554 555 bool operator==(const SExpr &other) const { 556 return NodeVec == other.NodeVec; 557 } 558 559 bool operator!=(const SExpr &other) const { 560 return !(*this == other); 561 } 562 563 bool matches(const SExpr &Other, unsigned i = 0, unsigned j = 0) const { 564 if (NodeVec[i].matches(Other.NodeVec[j])) { 565 unsigned n = NodeVec[i].arity(); 566 bool Result = true; 567 unsigned ci = i+1; // first child of i 568 unsigned cj = j+1; // first child of j 569 for (unsigned k = 0; k < n; 570 ++k, ci=getNextSibling(ci), cj = Other.getNextSibling(cj)) { 571 Result = Result && matches(Other, ci, cj); 572 } 573 return Result; 574 } 575 return false; 576 } 577 578 // A partial match between a.mu and b.mu returns true a and b have the same 579 // type (and thus mu refers to the same mutex declaration), regardless of 580 // whether a and b are different objects or not. 581 bool partiallyMatches(const SExpr &Other) const { 582 if (NodeVec[0].kind() == EOP_Dot) 583 return NodeVec[0].matches(Other.NodeVec[0]); 584 return false; 585 } 586 587 /// \brief Pretty print a lock expression for use in error messages. 588 std::string toString(unsigned i = 0) const { 589 assert(isValid()); 590 if (i >= NodeVec.size()) 591 return ""; 592 593 const SExprNode* N = &NodeVec[i]; 594 switch (N->kind()) { 595 case EOP_Nop: 596 return "_"; 597 case EOP_Wildcard: 598 return "(?)"; 599 case EOP_Universal: 600 return "*"; 601 case EOP_This: 602 return "this"; 603 case EOP_NVar: 604 case EOP_LVar: { 605 return N->getNamedDecl()->getNameAsString(); 606 } 607 case EOP_Dot: { 608 if (NodeVec[i+1].kind() == EOP_Wildcard) { 609 std::string S = "&"; 610 S += N->getNamedDecl()->getQualifiedNameAsString(); 611 return S; 612 } 613 std::string FieldName = N->getNamedDecl()->getNameAsString(); 614 if (NodeVec[i+1].kind() == EOP_This) 615 return FieldName; 616 617 std::string S = toString(i+1); 618 if (N->isArrow()) 619 return S + "->" + FieldName; 620 else 621 return S + "." + FieldName; 622 } 623 case EOP_Call: { 624 std::string S = toString(i+1) + "("; 625 unsigned NumArgs = N->arity()-1; 626 unsigned ci = getNextSibling(i+1); 627 for (unsigned k=0; k<NumArgs; ++k, ci = getNextSibling(ci)) { 628 S += toString(ci); 629 if (k+1 < NumArgs) S += ","; 630 } 631 S += ")"; 632 return S; 633 } 634 case EOP_MCall: { 635 std::string S = ""; 636 if (NodeVec[i+1].kind() != EOP_This) 637 S = toString(i+1) + "."; 638 if (const NamedDecl *D = N->getFunctionDecl()) 639 S += D->getNameAsString() + "("; 640 else 641 S += "#("; 642 unsigned NumArgs = N->arity()-1; 643 unsigned ci = getNextSibling(i+1); 644 for (unsigned k=0; k<NumArgs; ++k, ci = getNextSibling(ci)) { 645 S += toString(ci); 646 if (k+1 < NumArgs) S += ","; 647 } 648 S += ")"; 649 return S; 650 } 651 case EOP_Index: { 652 std::string S1 = toString(i+1); 653 std::string S2 = toString(i+1 + NodeVec[i+1].size()); 654 return S1 + "[" + S2 + "]"; 655 } 656 case EOP_Unary: { 657 std::string S = toString(i+1); 658 return "#" + S; 659 } 660 case EOP_Binary: { 661 std::string S1 = toString(i+1); 662 std::string S2 = toString(i+1 + NodeVec[i+1].size()); 663 return "(" + S1 + "#" + S2 + ")"; 664 } 665 case EOP_Unknown: { 666 unsigned NumChildren = N->arity(); 667 if (NumChildren == 0) 668 return "(...)"; 669 std::string S = "("; 670 unsigned ci = i+1; 671 for (unsigned j = 0; j < NumChildren; ++j, ci = getNextSibling(ci)) { 672 S += toString(ci); 673 if (j+1 < NumChildren) S += "#"; 674 } 675 S += ")"; 676 return S; 677 } 678 } 679 return ""; 680 } 681 }; 682 683 684 685 /// \brief A short list of SExprs 686 class MutexIDList : public SmallVector<SExpr, 3> { 687 public: 688 /// \brief Return true if the list contains the specified SExpr 689 /// Performs a linear search, because these lists are almost always very small. 690 bool contains(const SExpr& M) { 691 for (iterator I=begin(),E=end(); I != E; ++I) 692 if ((*I) == M) return true; 693 return false; 694 } 695 696 /// \brief Push M onto list, bud discard duplicates 697 void push_back_nodup(const SExpr& M) { 698 if (!contains(M)) push_back(M); 699 } 700 }; 701 702 703 704 /// \brief This is a helper class that stores info about the most recent 705 /// accquire of a Lock. 706 /// 707 /// The main body of the analysis maps MutexIDs to LockDatas. 708 struct LockData { 709 SourceLocation AcquireLoc; 710 711 /// \brief LKind stores whether a lock is held shared or exclusively. 712 /// Note that this analysis does not currently support either re-entrant 713 /// locking or lock "upgrading" and "downgrading" between exclusive and 714 /// shared. 715 /// 716 /// FIXME: add support for re-entrant locking and lock up/downgrading 717 LockKind LKind; 718 bool Managed; // for ScopedLockable objects 719 SExpr UnderlyingMutex; // for ScopedLockable objects 720 721 LockData(SourceLocation AcquireLoc, LockKind LKind, bool M = false) 722 : AcquireLoc(AcquireLoc), LKind(LKind), Managed(M), 723 UnderlyingMutex(Decl::EmptyShell()) 724 {} 725 726 LockData(SourceLocation AcquireLoc, LockKind LKind, const SExpr &Mu) 727 : AcquireLoc(AcquireLoc), LKind(LKind), Managed(false), 728 UnderlyingMutex(Mu) 729 {} 730 731 bool operator==(const LockData &other) const { 732 return AcquireLoc == other.AcquireLoc && LKind == other.LKind; 733 } 734 735 bool operator!=(const LockData &other) const { 736 return !(*this == other); 737 } 738 739 void Profile(llvm::FoldingSetNodeID &ID) const { 740 ID.AddInteger(AcquireLoc.getRawEncoding()); 741 ID.AddInteger(LKind); 742 } 743 744 bool isAtLeast(LockKind LK) { 745 return (LK == LK_Shared) || (LKind == LK_Exclusive); 746 } 747 }; 748 749 750 /// \brief A FactEntry stores a single fact that is known at a particular point 751 /// in the program execution. Currently, this is information regarding a lock 752 /// that is held at that point. 753 struct FactEntry { 754 SExpr MutID; 755 LockData LDat; 756 757 FactEntry(const SExpr& M, const LockData& L) 758 : MutID(M), LDat(L) 759 { } 760 }; 761 762 763 typedef unsigned short FactID; 764 765 /// \brief FactManager manages the memory for all facts that are created during 766 /// the analysis of a single routine. 767 class FactManager { 768 private: 769 std::vector<FactEntry> Facts; 770 771 public: 772 FactID newLock(const SExpr& M, const LockData& L) { 773 Facts.push_back(FactEntry(M,L)); 774 return static_cast<unsigned short>(Facts.size() - 1); 775 } 776 777 const FactEntry& operator[](FactID F) const { return Facts[F]; } 778 FactEntry& operator[](FactID F) { return Facts[F]; } 779 }; 780 781 782 /// \brief A FactSet is the set of facts that are known to be true at a 783 /// particular program point. FactSets must be small, because they are 784 /// frequently copied, and are thus implemented as a set of indices into a 785 /// table maintained by a FactManager. A typical FactSet only holds 1 or 2 786 /// locks, so we can get away with doing a linear search for lookup. Note 787 /// that a hashtable or map is inappropriate in this case, because lookups 788 /// may involve partial pattern matches, rather than exact matches. 789 class FactSet { 790 private: 791 typedef SmallVector<FactID, 4> FactVec; 792 793 FactVec FactIDs; 794 795 public: 796 typedef FactVec::iterator iterator; 797 typedef FactVec::const_iterator const_iterator; 798 799 iterator begin() { return FactIDs.begin(); } 800 const_iterator begin() const { return FactIDs.begin(); } 801 802 iterator end() { return FactIDs.end(); } 803 const_iterator end() const { return FactIDs.end(); } 804 805 bool isEmpty() const { return FactIDs.size() == 0; } 806 807 FactID addLock(FactManager& FM, const SExpr& M, const LockData& L) { 808 FactID F = FM.newLock(M, L); 809 FactIDs.push_back(F); 810 return F; 811 } 812 813 bool removeLock(FactManager& FM, const SExpr& M) { 814 unsigned n = FactIDs.size(); 815 if (n == 0) 816 return false; 817 818 for (unsigned i = 0; i < n-1; ++i) { 819 if (FM[FactIDs[i]].MutID.matches(M)) { 820 FactIDs[i] = FactIDs[n-1]; 821 FactIDs.pop_back(); 822 return true; 823 } 824 } 825 if (FM[FactIDs[n-1]].MutID.matches(M)) { 826 FactIDs.pop_back(); 827 return true; 828 } 829 return false; 830 } 831 832 LockData* findLock(FactManager &FM, const SExpr &M) const { 833 for (const_iterator I = begin(), E = end(); I != E; ++I) { 834 const SExpr &Exp = FM[*I].MutID; 835 if (Exp.matches(M)) 836 return &FM[*I].LDat; 837 } 838 return 0; 839 } 840 841 LockData* findLockUniv(FactManager &FM, const SExpr &M) const { 842 for (const_iterator I = begin(), E = end(); I != E; ++I) { 843 const SExpr &Exp = FM[*I].MutID; 844 if (Exp.matches(M) || Exp.isUniversal()) 845 return &FM[*I].LDat; 846 } 847 return 0; 848 } 849 850 FactEntry* findPartialMatch(FactManager &FM, const SExpr &M) const { 851 for (const_iterator I=begin(), E=end(); I != E; ++I) { 852 const SExpr& Exp = FM[*I].MutID; 853 if (Exp.partiallyMatches(M)) return &FM[*I]; 854 } 855 return 0; 856 } 857 }; 858 859 860 861 /// A Lockset maps each SExpr (defined above) to information about how it has 862 /// been locked. 863 typedef llvm::ImmutableMap<SExpr, LockData> Lockset; 864 typedef llvm::ImmutableMap<const NamedDecl*, unsigned> LocalVarContext; 865 866 class LocalVariableMap; 867 868 /// A side (entry or exit) of a CFG node. 869 enum CFGBlockSide { CBS_Entry, CBS_Exit }; 870 871 /// CFGBlockInfo is a struct which contains all the information that is 872 /// maintained for each block in the CFG. See LocalVariableMap for more 873 /// information about the contexts. 874 struct CFGBlockInfo { 875 FactSet EntrySet; // Lockset held at entry to block 876 FactSet ExitSet; // Lockset held at exit from block 877 LocalVarContext EntryContext; // Context held at entry to block 878 LocalVarContext ExitContext; // Context held at exit from block 879 SourceLocation EntryLoc; // Location of first statement in block 880 SourceLocation ExitLoc; // Location of last statement in block. 881 unsigned EntryIndex; // Used to replay contexts later 882 883 const FactSet &getSet(CFGBlockSide Side) const { 884 return Side == CBS_Entry ? EntrySet : ExitSet; 885 } 886 SourceLocation getLocation(CFGBlockSide Side) const { 887 return Side == CBS_Entry ? EntryLoc : ExitLoc; 888 } 889 890 private: 891 CFGBlockInfo(LocalVarContext EmptyCtx) 892 : EntryContext(EmptyCtx), ExitContext(EmptyCtx) 893 { } 894 895 public: 896 static CFGBlockInfo getEmptyBlockInfo(LocalVariableMap &M); 897 }; 898 899 900 901 // A LocalVariableMap maintains a map from local variables to their currently 902 // valid definitions. It provides SSA-like functionality when traversing the 903 // CFG. Like SSA, each definition or assignment to a variable is assigned a 904 // unique name (an integer), which acts as the SSA name for that definition. 905 // The total set of names is shared among all CFG basic blocks. 906 // Unlike SSA, we do not rewrite expressions to replace local variables declrefs 907 // with their SSA-names. Instead, we compute a Context for each point in the 908 // code, which maps local variables to the appropriate SSA-name. This map 909 // changes with each assignment. 910 // 911 // The map is computed in a single pass over the CFG. Subsequent analyses can 912 // then query the map to find the appropriate Context for a statement, and use 913 // that Context to look up the definitions of variables. 914 class LocalVariableMap { 915 public: 916 typedef LocalVarContext Context; 917 918 /// A VarDefinition consists of an expression, representing the value of the 919 /// variable, along with the context in which that expression should be 920 /// interpreted. A reference VarDefinition does not itself contain this 921 /// information, but instead contains a pointer to a previous VarDefinition. 922 struct VarDefinition { 923 public: 924 friend class LocalVariableMap; 925 926 const NamedDecl *Dec; // The original declaration for this variable. 927 const Expr *Exp; // The expression for this variable, OR 928 unsigned Ref; // Reference to another VarDefinition 929 Context Ctx; // The map with which Exp should be interpreted. 930 931 bool isReference() { return !Exp; } 932 933 private: 934 // Create ordinary variable definition 935 VarDefinition(const NamedDecl *D, const Expr *E, Context C) 936 : Dec(D), Exp(E), Ref(0), Ctx(C) 937 { } 938 939 // Create reference to previous definition 940 VarDefinition(const NamedDecl *D, unsigned R, Context C) 941 : Dec(D), Exp(0), Ref(R), Ctx(C) 942 { } 943 }; 944 945 private: 946 Context::Factory ContextFactory; 947 std::vector<VarDefinition> VarDefinitions; 948 std::vector<unsigned> CtxIndices; 949 std::vector<std::pair<Stmt*, Context> > SavedContexts; 950 951 public: 952 LocalVariableMap() { 953 // index 0 is a placeholder for undefined variables (aka phi-nodes). 954 VarDefinitions.push_back(VarDefinition(0, 0u, getEmptyContext())); 955 } 956 957 /// Look up a definition, within the given context. 958 const VarDefinition* lookup(const NamedDecl *D, Context Ctx) { 959 const unsigned *i = Ctx.lookup(D); 960 if (!i) 961 return 0; 962 assert(*i < VarDefinitions.size()); 963 return &VarDefinitions[*i]; 964 } 965 966 /// Look up the definition for D within the given context. Returns 967 /// NULL if the expression is not statically known. If successful, also 968 /// modifies Ctx to hold the context of the return Expr. 969 const Expr* lookupExpr(const NamedDecl *D, Context &Ctx) { 970 const unsigned *P = Ctx.lookup(D); 971 if (!P) 972 return 0; 973 974 unsigned i = *P; 975 while (i > 0) { 976 if (VarDefinitions[i].Exp) { 977 Ctx = VarDefinitions[i].Ctx; 978 return VarDefinitions[i].Exp; 979 } 980 i = VarDefinitions[i].Ref; 981 } 982 return 0; 983 } 984 985 Context getEmptyContext() { return ContextFactory.getEmptyMap(); } 986 987 /// Return the next context after processing S. This function is used by 988 /// clients of the class to get the appropriate context when traversing the 989 /// CFG. It must be called for every assignment or DeclStmt. 990 Context getNextContext(unsigned &CtxIndex, Stmt *S, Context C) { 991 if (SavedContexts[CtxIndex+1].first == S) { 992 CtxIndex++; 993 Context Result = SavedContexts[CtxIndex].second; 994 return Result; 995 } 996 return C; 997 } 998 999 void dumpVarDefinitionName(unsigned i) { 1000 if (i == 0) { 1001 llvm::errs() << "Undefined"; 1002 return; 1003 } 1004 const NamedDecl *Dec = VarDefinitions[i].Dec; 1005 if (!Dec) { 1006 llvm::errs() << "<<NULL>>"; 1007 return; 1008 } 1009 Dec->printName(llvm::errs()); 1010 llvm::errs() << "." << i << " " << ((const void*) Dec); 1011 } 1012 1013 /// Dumps an ASCII representation of the variable map to llvm::errs() 1014 void dump() { 1015 for (unsigned i = 1, e = VarDefinitions.size(); i < e; ++i) { 1016 const Expr *Exp = VarDefinitions[i].Exp; 1017 unsigned Ref = VarDefinitions[i].Ref; 1018 1019 dumpVarDefinitionName(i); 1020 llvm::errs() << " = "; 1021 if (Exp) Exp->dump(); 1022 else { 1023 dumpVarDefinitionName(Ref); 1024 llvm::errs() << "\n"; 1025 } 1026 } 1027 } 1028 1029 /// Dumps an ASCII representation of a Context to llvm::errs() 1030 void dumpContext(Context C) { 1031 for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) { 1032 const NamedDecl *D = I.getKey(); 1033 D->printName(llvm::errs()); 1034 const unsigned *i = C.lookup(D); 1035 llvm::errs() << " -> "; 1036 dumpVarDefinitionName(*i); 1037 llvm::errs() << "\n"; 1038 } 1039 } 1040 1041 /// Builds the variable map. 1042 void traverseCFG(CFG *CFGraph, PostOrderCFGView *SortedGraph, 1043 std::vector<CFGBlockInfo> &BlockInfo); 1044 1045 protected: 1046 // Get the current context index 1047 unsigned getContextIndex() { return SavedContexts.size()-1; } 1048 1049 // Save the current context for later replay 1050 void saveContext(Stmt *S, Context C) { 1051 SavedContexts.push_back(std::make_pair(S,C)); 1052 } 1053 1054 // Adds a new definition to the given context, and returns a new context. 1055 // This method should be called when declaring a new variable. 1056 Context addDefinition(const NamedDecl *D, Expr *Exp, Context Ctx) { 1057 assert(!Ctx.contains(D)); 1058 unsigned newID = VarDefinitions.size(); 1059 Context NewCtx = ContextFactory.add(Ctx, D, newID); 1060 VarDefinitions.push_back(VarDefinition(D, Exp, Ctx)); 1061 return NewCtx; 1062 } 1063 1064 // Add a new reference to an existing definition. 1065 Context addReference(const NamedDecl *D, unsigned i, Context Ctx) { 1066 unsigned newID = VarDefinitions.size(); 1067 Context NewCtx = ContextFactory.add(Ctx, D, newID); 1068 VarDefinitions.push_back(VarDefinition(D, i, Ctx)); 1069 return NewCtx; 1070 } 1071 1072 // Updates a definition only if that definition is already in the map. 1073 // This method should be called when assigning to an existing variable. 1074 Context updateDefinition(const NamedDecl *D, Expr *Exp, Context Ctx) { 1075 if (Ctx.contains(D)) { 1076 unsigned newID = VarDefinitions.size(); 1077 Context NewCtx = ContextFactory.remove(Ctx, D); 1078 NewCtx = ContextFactory.add(NewCtx, D, newID); 1079 VarDefinitions.push_back(VarDefinition(D, Exp, Ctx)); 1080 return NewCtx; 1081 } 1082 return Ctx; 1083 } 1084 1085 // Removes a definition from the context, but keeps the variable name 1086 // as a valid variable. The index 0 is a placeholder for cleared definitions. 1087 Context clearDefinition(const NamedDecl *D, Context Ctx) { 1088 Context NewCtx = Ctx; 1089 if (NewCtx.contains(D)) { 1090 NewCtx = ContextFactory.remove(NewCtx, D); 1091 NewCtx = ContextFactory.add(NewCtx, D, 0); 1092 } 1093 return NewCtx; 1094 } 1095 1096 // Remove a definition entirely frmo the context. 1097 Context removeDefinition(const NamedDecl *D, Context Ctx) { 1098 Context NewCtx = Ctx; 1099 if (NewCtx.contains(D)) { 1100 NewCtx = ContextFactory.remove(NewCtx, D); 1101 } 1102 return NewCtx; 1103 } 1104 1105 Context intersectContexts(Context C1, Context C2); 1106 Context createReferenceContext(Context C); 1107 void intersectBackEdge(Context C1, Context C2); 1108 1109 friend class VarMapBuilder; 1110 }; 1111 1112 1113 // This has to be defined after LocalVariableMap. 1114 CFGBlockInfo CFGBlockInfo::getEmptyBlockInfo(LocalVariableMap &M) { 1115 return CFGBlockInfo(M.getEmptyContext()); 1116 } 1117 1118 1119 /// Visitor which builds a LocalVariableMap 1120 class VarMapBuilder : public StmtVisitor<VarMapBuilder> { 1121 public: 1122 LocalVariableMap* VMap; 1123 LocalVariableMap::Context Ctx; 1124 1125 VarMapBuilder(LocalVariableMap *VM, LocalVariableMap::Context C) 1126 : VMap(VM), Ctx(C) {} 1127 1128 void VisitDeclStmt(DeclStmt *S); 1129 void VisitBinaryOperator(BinaryOperator *BO); 1130 }; 1131 1132 1133 // Add new local variables to the variable map 1134 void VarMapBuilder::VisitDeclStmt(DeclStmt *S) { 1135 bool modifiedCtx = false; 1136 DeclGroupRef DGrp = S->getDeclGroup(); 1137 for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) { 1138 if (VarDecl *VD = dyn_cast_or_null<VarDecl>(*I)) { 1139 Expr *E = VD->getInit(); 1140 1141 // Add local variables with trivial type to the variable map 1142 QualType T = VD->getType(); 1143 if (T.isTrivialType(VD->getASTContext())) { 1144 Ctx = VMap->addDefinition(VD, E, Ctx); 1145 modifiedCtx = true; 1146 } 1147 } 1148 } 1149 if (modifiedCtx) 1150 VMap->saveContext(S, Ctx); 1151 } 1152 1153 // Update local variable definitions in variable map 1154 void VarMapBuilder::VisitBinaryOperator(BinaryOperator *BO) { 1155 if (!BO->isAssignmentOp()) 1156 return; 1157 1158 Expr *LHSExp = BO->getLHS()->IgnoreParenCasts(); 1159 1160 // Update the variable map and current context. 1161 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(LHSExp)) { 1162 ValueDecl *VDec = DRE->getDecl(); 1163 if (Ctx.lookup(VDec)) { 1164 if (BO->getOpcode() == BO_Assign) 1165 Ctx = VMap->updateDefinition(VDec, BO->getRHS(), Ctx); 1166 else 1167 // FIXME -- handle compound assignment operators 1168 Ctx = VMap->clearDefinition(VDec, Ctx); 1169 VMap->saveContext(BO, Ctx); 1170 } 1171 } 1172 } 1173 1174 1175 // Computes the intersection of two contexts. The intersection is the 1176 // set of variables which have the same definition in both contexts; 1177 // variables with different definitions are discarded. 1178 LocalVariableMap::Context 1179 LocalVariableMap::intersectContexts(Context C1, Context C2) { 1180 Context Result = C1; 1181 for (Context::iterator I = C1.begin(), E = C1.end(); I != E; ++I) { 1182 const NamedDecl *Dec = I.getKey(); 1183 unsigned i1 = I.getData(); 1184 const unsigned *i2 = C2.lookup(Dec); 1185 if (!i2) // variable doesn't exist on second path 1186 Result = removeDefinition(Dec, Result); 1187 else if (*i2 != i1) // variable exists, but has different definition 1188 Result = clearDefinition(Dec, Result); 1189 } 1190 return Result; 1191 } 1192 1193 // For every variable in C, create a new variable that refers to the 1194 // definition in C. Return a new context that contains these new variables. 1195 // (We use this for a naive implementation of SSA on loop back-edges.) 1196 LocalVariableMap::Context LocalVariableMap::createReferenceContext(Context C) { 1197 Context Result = getEmptyContext(); 1198 for (Context::iterator I = C.begin(), E = C.end(); I != E; ++I) { 1199 const NamedDecl *Dec = I.getKey(); 1200 unsigned i = I.getData(); 1201 Result = addReference(Dec, i, Result); 1202 } 1203 return Result; 1204 } 1205 1206 // This routine also takes the intersection of C1 and C2, but it does so by 1207 // altering the VarDefinitions. C1 must be the result of an earlier call to 1208 // createReferenceContext. 1209 void LocalVariableMap::intersectBackEdge(Context C1, Context C2) { 1210 for (Context::iterator I = C1.begin(), E = C1.end(); I != E; ++I) { 1211 const NamedDecl *Dec = I.getKey(); 1212 unsigned i1 = I.getData(); 1213 VarDefinition *VDef = &VarDefinitions[i1]; 1214 assert(VDef->isReference()); 1215 1216 const unsigned *i2 = C2.lookup(Dec); 1217 if (!i2 || (*i2 != i1)) 1218 VDef->Ref = 0; // Mark this variable as undefined 1219 } 1220 } 1221 1222 1223 // Traverse the CFG in topological order, so all predecessors of a block 1224 // (excluding back-edges) are visited before the block itself. At 1225 // each point in the code, we calculate a Context, which holds the set of 1226 // variable definitions which are visible at that point in execution. 1227 // Visible variables are mapped to their definitions using an array that 1228 // contains all definitions. 1229 // 1230 // At join points in the CFG, the set is computed as the intersection of 1231 // the incoming sets along each edge, E.g. 1232 // 1233 // { Context | VarDefinitions } 1234 // int x = 0; { x -> x1 | x1 = 0 } 1235 // int y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 } 1236 // if (b) x = 1; { x -> x2, y -> y1 | x2 = 1, y1 = 0, ... } 1237 // else x = 2; { x -> x3, y -> y1 | x3 = 2, x2 = 1, ... } 1238 // ... { y -> y1 (x is unknown) | x3 = 2, x2 = 1, ... } 1239 // 1240 // This is essentially a simpler and more naive version of the standard SSA 1241 // algorithm. Those definitions that remain in the intersection are from blocks 1242 // that strictly dominate the current block. We do not bother to insert proper 1243 // phi nodes, because they are not used in our analysis; instead, wherever 1244 // a phi node would be required, we simply remove that definition from the 1245 // context (E.g. x above). 1246 // 1247 // The initial traversal does not capture back-edges, so those need to be 1248 // handled on a separate pass. Whenever the first pass encounters an 1249 // incoming back edge, it duplicates the context, creating new definitions 1250 // that refer back to the originals. (These correspond to places where SSA 1251 // might have to insert a phi node.) On the second pass, these definitions are 1252 // set to NULL if the variable has changed on the back-edge (i.e. a phi 1253 // node was actually required.) E.g. 1254 // 1255 // { Context | VarDefinitions } 1256 // int x = 0, y = 0; { x -> x1, y -> y1 | y1 = 0, x1 = 0 } 1257 // while (b) { x -> x2, y -> y1 | [1st:] x2=x1; [2nd:] x2=NULL; } 1258 // x = x+1; { x -> x3, y -> y1 | x3 = x2 + 1, ... } 1259 // ... { y -> y1 | x3 = 2, x2 = 1, ... } 1260 // 1261 void LocalVariableMap::traverseCFG(CFG *CFGraph, 1262 PostOrderCFGView *SortedGraph, 1263 std::vector<CFGBlockInfo> &BlockInfo) { 1264 PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); 1265 1266 CtxIndices.resize(CFGraph->getNumBlockIDs()); 1267 1268 for (PostOrderCFGView::iterator I = SortedGraph->begin(), 1269 E = SortedGraph->end(); I!= E; ++I) { 1270 const CFGBlock *CurrBlock = *I; 1271 int CurrBlockID = CurrBlock->getBlockID(); 1272 CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; 1273 1274 VisitedBlocks.insert(CurrBlock); 1275 1276 // Calculate the entry context for the current block 1277 bool HasBackEdges = false; 1278 bool CtxInit = true; 1279 for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), 1280 PE = CurrBlock->pred_end(); PI != PE; ++PI) { 1281 // if *PI -> CurrBlock is a back edge, so skip it 1282 if (*PI == 0 || !VisitedBlocks.alreadySet(*PI)) { 1283 HasBackEdges = true; 1284 continue; 1285 } 1286 1287 int PrevBlockID = (*PI)->getBlockID(); 1288 CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; 1289 1290 if (CtxInit) { 1291 CurrBlockInfo->EntryContext = PrevBlockInfo->ExitContext; 1292 CtxInit = false; 1293 } 1294 else { 1295 CurrBlockInfo->EntryContext = 1296 intersectContexts(CurrBlockInfo->EntryContext, 1297 PrevBlockInfo->ExitContext); 1298 } 1299 } 1300 1301 // Duplicate the context if we have back-edges, so we can call 1302 // intersectBackEdges later. 1303 if (HasBackEdges) 1304 CurrBlockInfo->EntryContext = 1305 createReferenceContext(CurrBlockInfo->EntryContext); 1306 1307 // Create a starting context index for the current block 1308 saveContext(0, CurrBlockInfo->EntryContext); 1309 CurrBlockInfo->EntryIndex = getContextIndex(); 1310 1311 // Visit all the statements in the basic block. 1312 VarMapBuilder VMapBuilder(this, CurrBlockInfo->EntryContext); 1313 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 1314 BE = CurrBlock->end(); BI != BE; ++BI) { 1315 switch (BI->getKind()) { 1316 case CFGElement::Statement: { 1317 const CFGStmt *CS = cast<CFGStmt>(&*BI); 1318 VMapBuilder.Visit(const_cast<Stmt*>(CS->getStmt())); 1319 break; 1320 } 1321 default: 1322 break; 1323 } 1324 } 1325 CurrBlockInfo->ExitContext = VMapBuilder.Ctx; 1326 1327 // Mark variables on back edges as "unknown" if they've been changed. 1328 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 1329 SE = CurrBlock->succ_end(); SI != SE; ++SI) { 1330 // if CurrBlock -> *SI is *not* a back edge 1331 if (*SI == 0 || !VisitedBlocks.alreadySet(*SI)) 1332 continue; 1333 1334 CFGBlock *FirstLoopBlock = *SI; 1335 Context LoopBegin = BlockInfo[FirstLoopBlock->getBlockID()].EntryContext; 1336 Context LoopEnd = CurrBlockInfo->ExitContext; 1337 intersectBackEdge(LoopBegin, LoopEnd); 1338 } 1339 } 1340 1341 // Put an extra entry at the end of the indexed context array 1342 unsigned exitID = CFGraph->getExit().getBlockID(); 1343 saveContext(0, BlockInfo[exitID].ExitContext); 1344 } 1345 1346 /// Find the appropriate source locations to use when producing diagnostics for 1347 /// each block in the CFG. 1348 static void findBlockLocations(CFG *CFGraph, 1349 PostOrderCFGView *SortedGraph, 1350 std::vector<CFGBlockInfo> &BlockInfo) { 1351 for (PostOrderCFGView::iterator I = SortedGraph->begin(), 1352 E = SortedGraph->end(); I!= E; ++I) { 1353 const CFGBlock *CurrBlock = *I; 1354 CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlock->getBlockID()]; 1355 1356 // Find the source location of the last statement in the block, if the 1357 // block is not empty. 1358 if (const Stmt *S = CurrBlock->getTerminator()) { 1359 CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = S->getLocStart(); 1360 } else { 1361 for (CFGBlock::const_reverse_iterator BI = CurrBlock->rbegin(), 1362 BE = CurrBlock->rend(); BI != BE; ++BI) { 1363 // FIXME: Handle other CFGElement kinds. 1364 if (const CFGStmt *CS = dyn_cast<CFGStmt>(&*BI)) { 1365 CurrBlockInfo->ExitLoc = CS->getStmt()->getLocStart(); 1366 break; 1367 } 1368 } 1369 } 1370 1371 if (!CurrBlockInfo->ExitLoc.isInvalid()) { 1372 // This block contains at least one statement. Find the source location 1373 // of the first statement in the block. 1374 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 1375 BE = CurrBlock->end(); BI != BE; ++BI) { 1376 // FIXME: Handle other CFGElement kinds. 1377 if (const CFGStmt *CS = dyn_cast<CFGStmt>(&*BI)) { 1378 CurrBlockInfo->EntryLoc = CS->getStmt()->getLocStart(); 1379 break; 1380 } 1381 } 1382 } else if (CurrBlock->pred_size() == 1 && *CurrBlock->pred_begin() && 1383 CurrBlock != &CFGraph->getExit()) { 1384 // The block is empty, and has a single predecessor. Use its exit 1385 // location. 1386 CurrBlockInfo->EntryLoc = CurrBlockInfo->ExitLoc = 1387 BlockInfo[(*CurrBlock->pred_begin())->getBlockID()].ExitLoc; 1388 } 1389 } 1390 } 1391 1392 /// \brief Class which implements the core thread safety analysis routines. 1393 class ThreadSafetyAnalyzer { 1394 friend class BuildLockset; 1395 1396 ThreadSafetyHandler &Handler; 1397 LocalVariableMap LocalVarMap; 1398 FactManager FactMan; 1399 std::vector<CFGBlockInfo> BlockInfo; 1400 1401 public: 1402 ThreadSafetyAnalyzer(ThreadSafetyHandler &H) : Handler(H) {} 1403 1404 void addLock(FactSet &FSet, const SExpr &Mutex, const LockData &LDat); 1405 void removeLock(FactSet &FSet, const SExpr &Mutex, 1406 SourceLocation UnlockLoc, bool FullyRemove=false); 1407 1408 template <typename AttrType> 1409 void getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, Expr *Exp, 1410 const NamedDecl *D); 1411 1412 template <class AttrType> 1413 void getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, Expr *Exp, 1414 const NamedDecl *D, 1415 const CFGBlock *PredBlock, const CFGBlock *CurrBlock, 1416 Expr *BrE, bool Neg); 1417 1418 const CallExpr* getTrylockCallExpr(const Stmt *Cond, LocalVarContext C, 1419 bool &Negate); 1420 1421 void getEdgeLockset(FactSet &Result, const FactSet &ExitSet, 1422 const CFGBlock* PredBlock, 1423 const CFGBlock *CurrBlock); 1424 1425 void intersectAndWarn(FactSet &FSet1, const FactSet &FSet2, 1426 SourceLocation JoinLoc, 1427 LockErrorKind LEK1, LockErrorKind LEK2, 1428 bool Modify=true); 1429 1430 void intersectAndWarn(FactSet &FSet1, const FactSet &FSet2, 1431 SourceLocation JoinLoc, LockErrorKind LEK1, 1432 bool Modify=true) { 1433 intersectAndWarn(FSet1, FSet2, JoinLoc, LEK1, LEK1, Modify); 1434 } 1435 1436 void runAnalysis(AnalysisDeclContext &AC); 1437 }; 1438 1439 1440 /// \brief Add a new lock to the lockset, warning if the lock is already there. 1441 /// \param Mutex -- the Mutex expression for the lock 1442 /// \param LDat -- the LockData for the lock 1443 void ThreadSafetyAnalyzer::addLock(FactSet &FSet, const SExpr &Mutex, 1444 const LockData &LDat) { 1445 // FIXME: deal with acquired before/after annotations. 1446 // FIXME: Don't always warn when we have support for reentrant locks. 1447 if (Mutex.shouldIgnore()) 1448 return; 1449 1450 if (FSet.findLock(FactMan, Mutex)) { 1451 Handler.handleDoubleLock(Mutex.toString(), LDat.AcquireLoc); 1452 } else { 1453 FSet.addLock(FactMan, Mutex, LDat); 1454 } 1455 } 1456 1457 1458 /// \brief Remove a lock from the lockset, warning if the lock is not there. 1459 /// \param Mutex The lock expression corresponding to the lock to be removed 1460 /// \param UnlockLoc The source location of the unlock (only used in error msg) 1461 void ThreadSafetyAnalyzer::removeLock(FactSet &FSet, 1462 const SExpr &Mutex, 1463 SourceLocation UnlockLoc, 1464 bool FullyRemove) { 1465 if (Mutex.shouldIgnore()) 1466 return; 1467 1468 const LockData *LDat = FSet.findLock(FactMan, Mutex); 1469 if (!LDat) { 1470 Handler.handleUnmatchedUnlock(Mutex.toString(), UnlockLoc); 1471 return; 1472 } 1473 1474 if (LDat->UnderlyingMutex.isValid()) { 1475 // This is scoped lockable object, which manages the real mutex. 1476 if (FullyRemove) { 1477 // We're destroying the managing object. 1478 // Remove the underlying mutex if it exists; but don't warn. 1479 if (FSet.findLock(FactMan, LDat->UnderlyingMutex)) 1480 FSet.removeLock(FactMan, LDat->UnderlyingMutex); 1481 } else { 1482 // We're releasing the underlying mutex, but not destroying the 1483 // managing object. Warn on dual release. 1484 if (!FSet.findLock(FactMan, LDat->UnderlyingMutex)) { 1485 Handler.handleUnmatchedUnlock(LDat->UnderlyingMutex.toString(), 1486 UnlockLoc); 1487 } 1488 FSet.removeLock(FactMan, LDat->UnderlyingMutex); 1489 return; 1490 } 1491 } 1492 FSet.removeLock(FactMan, Mutex); 1493 } 1494 1495 1496 /// \brief Extract the list of mutexIDs from the attribute on an expression, 1497 /// and push them onto Mtxs, discarding any duplicates. 1498 template <typename AttrType> 1499 void ThreadSafetyAnalyzer::getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, 1500 Expr *Exp, const NamedDecl *D) { 1501 typedef typename AttrType::args_iterator iterator_type; 1502 1503 if (Attr->args_size() == 0) { 1504 // The mutex held is the "this" object. 1505 SExpr Mu(0, Exp, D); 1506 if (!Mu.isValid()) 1507 SExpr::warnInvalidLock(Handler, 0, Exp, D); 1508 else 1509 Mtxs.push_back_nodup(Mu); 1510 return; 1511 } 1512 1513 for (iterator_type I=Attr->args_begin(), E=Attr->args_end(); I != E; ++I) { 1514 SExpr Mu(*I, Exp, D); 1515 if (!Mu.isValid()) 1516 SExpr::warnInvalidLock(Handler, *I, Exp, D); 1517 else 1518 Mtxs.push_back_nodup(Mu); 1519 } 1520 } 1521 1522 1523 /// \brief Extract the list of mutexIDs from a trylock attribute. If the 1524 /// trylock applies to the given edge, then push them onto Mtxs, discarding 1525 /// any duplicates. 1526 template <class AttrType> 1527 void ThreadSafetyAnalyzer::getMutexIDs(MutexIDList &Mtxs, AttrType *Attr, 1528 Expr *Exp, const NamedDecl *D, 1529 const CFGBlock *PredBlock, 1530 const CFGBlock *CurrBlock, 1531 Expr *BrE, bool Neg) { 1532 // Find out which branch has the lock 1533 bool branch = 0; 1534 if (CXXBoolLiteralExpr *BLE = dyn_cast_or_null<CXXBoolLiteralExpr>(BrE)) { 1535 branch = BLE->getValue(); 1536 } 1537 else if (IntegerLiteral *ILE = dyn_cast_or_null<IntegerLiteral>(BrE)) { 1538 branch = ILE->getValue().getBoolValue(); 1539 } 1540 int branchnum = branch ? 0 : 1; 1541 if (Neg) branchnum = !branchnum; 1542 1543 // If we've taken the trylock branch, then add the lock 1544 int i = 0; 1545 for (CFGBlock::const_succ_iterator SI = PredBlock->succ_begin(), 1546 SE = PredBlock->succ_end(); SI != SE && i < 2; ++SI, ++i) { 1547 if (*SI == CurrBlock && i == branchnum) { 1548 getMutexIDs(Mtxs, Attr, Exp, D); 1549 } 1550 } 1551 } 1552 1553 1554 bool getStaticBooleanValue(Expr* E, bool& TCond) { 1555 if (isa<CXXNullPtrLiteralExpr>(E) || isa<GNUNullExpr>(E)) { 1556 TCond = false; 1557 return true; 1558 } else if (CXXBoolLiteralExpr *BLE = dyn_cast<CXXBoolLiteralExpr>(E)) { 1559 TCond = BLE->getValue(); 1560 return true; 1561 } else if (IntegerLiteral *ILE = dyn_cast<IntegerLiteral>(E)) { 1562 TCond = ILE->getValue().getBoolValue(); 1563 return true; 1564 } else if (ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(E)) { 1565 return getStaticBooleanValue(CE->getSubExpr(), TCond); 1566 } 1567 return false; 1568 } 1569 1570 1571 // If Cond can be traced back to a function call, return the call expression. 1572 // The negate variable should be called with false, and will be set to true 1573 // if the function call is negated, e.g. if (!mu.tryLock(...)) 1574 const CallExpr* ThreadSafetyAnalyzer::getTrylockCallExpr(const Stmt *Cond, 1575 LocalVarContext C, 1576 bool &Negate) { 1577 if (!Cond) 1578 return 0; 1579 1580 if (const CallExpr *CallExp = dyn_cast<CallExpr>(Cond)) { 1581 return CallExp; 1582 } 1583 else if (const ParenExpr *PE = dyn_cast<ParenExpr>(Cond)) { 1584 return getTrylockCallExpr(PE->getSubExpr(), C, Negate); 1585 } 1586 else if (const ImplicitCastExpr *CE = dyn_cast<ImplicitCastExpr>(Cond)) { 1587 return getTrylockCallExpr(CE->getSubExpr(), C, Negate); 1588 } 1589 else if (const ExprWithCleanups* EWC = dyn_cast<ExprWithCleanups>(Cond)) { 1590 return getTrylockCallExpr(EWC->getSubExpr(), C, Negate); 1591 } 1592 else if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Cond)) { 1593 const Expr *E = LocalVarMap.lookupExpr(DRE->getDecl(), C); 1594 return getTrylockCallExpr(E, C, Negate); 1595 } 1596 else if (const UnaryOperator *UOP = dyn_cast<UnaryOperator>(Cond)) { 1597 if (UOP->getOpcode() == UO_LNot) { 1598 Negate = !Negate; 1599 return getTrylockCallExpr(UOP->getSubExpr(), C, Negate); 1600 } 1601 return 0; 1602 } 1603 else if (const BinaryOperator *BOP = dyn_cast<BinaryOperator>(Cond)) { 1604 if (BOP->getOpcode() == BO_EQ || BOP->getOpcode() == BO_NE) { 1605 if (BOP->getOpcode() == BO_NE) 1606 Negate = !Negate; 1607 1608 bool TCond = false; 1609 if (getStaticBooleanValue(BOP->getRHS(), TCond)) { 1610 if (!TCond) Negate = !Negate; 1611 return getTrylockCallExpr(BOP->getLHS(), C, Negate); 1612 } 1613 else if (getStaticBooleanValue(BOP->getLHS(), TCond)) { 1614 if (!TCond) Negate = !Negate; 1615 return getTrylockCallExpr(BOP->getRHS(), C, Negate); 1616 } 1617 return 0; 1618 } 1619 return 0; 1620 } 1621 // FIXME -- handle && and || as well. 1622 return 0; 1623 } 1624 1625 1626 /// \brief Find the lockset that holds on the edge between PredBlock 1627 /// and CurrBlock. The edge set is the exit set of PredBlock (passed 1628 /// as the ExitSet parameter) plus any trylocks, which are conditionally held. 1629 void ThreadSafetyAnalyzer::getEdgeLockset(FactSet& Result, 1630 const FactSet &ExitSet, 1631 const CFGBlock *PredBlock, 1632 const CFGBlock *CurrBlock) { 1633 Result = ExitSet; 1634 1635 if (!PredBlock->getTerminatorCondition()) 1636 return; 1637 1638 bool Negate = false; 1639 const Stmt *Cond = PredBlock->getTerminatorCondition(); 1640 const CFGBlockInfo *PredBlockInfo = &BlockInfo[PredBlock->getBlockID()]; 1641 const LocalVarContext &LVarCtx = PredBlockInfo->ExitContext; 1642 1643 CallExpr *Exp = 1644 const_cast<CallExpr*>(getTrylockCallExpr(Cond, LVarCtx, Negate)); 1645 if (!Exp) 1646 return; 1647 1648 NamedDecl *FunDecl = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); 1649 if(!FunDecl || !FunDecl->hasAttrs()) 1650 return; 1651 1652 1653 MutexIDList ExclusiveLocksToAdd; 1654 MutexIDList SharedLocksToAdd; 1655 1656 // If the condition is a call to a Trylock function, then grab the attributes 1657 AttrVec &ArgAttrs = FunDecl->getAttrs(); 1658 for (unsigned i = 0; i < ArgAttrs.size(); ++i) { 1659 Attr *Attr = ArgAttrs[i]; 1660 switch (Attr->getKind()) { 1661 case attr::ExclusiveTrylockFunction: { 1662 ExclusiveTrylockFunctionAttr *A = 1663 cast<ExclusiveTrylockFunctionAttr>(Attr); 1664 getMutexIDs(ExclusiveLocksToAdd, A, Exp, FunDecl, 1665 PredBlock, CurrBlock, A->getSuccessValue(), Negate); 1666 break; 1667 } 1668 case attr::SharedTrylockFunction: { 1669 SharedTrylockFunctionAttr *A = 1670 cast<SharedTrylockFunctionAttr>(Attr); 1671 getMutexIDs(ExclusiveLocksToAdd, A, Exp, FunDecl, 1672 PredBlock, CurrBlock, A->getSuccessValue(), Negate); 1673 break; 1674 } 1675 default: 1676 break; 1677 } 1678 } 1679 1680 // Add and remove locks. 1681 SourceLocation Loc = Exp->getExprLoc(); 1682 for (unsigned i=0,n=ExclusiveLocksToAdd.size(); i<n; ++i) { 1683 addLock(Result, ExclusiveLocksToAdd[i], 1684 LockData(Loc, LK_Exclusive)); 1685 } 1686 for (unsigned i=0,n=SharedLocksToAdd.size(); i<n; ++i) { 1687 addLock(Result, SharedLocksToAdd[i], 1688 LockData(Loc, LK_Shared)); 1689 } 1690 } 1691 1692 1693 /// \brief We use this class to visit different types of expressions in 1694 /// CFGBlocks, and build up the lockset. 1695 /// An expression may cause us to add or remove locks from the lockset, or else 1696 /// output error messages related to missing locks. 1697 /// FIXME: In future, we may be able to not inherit from a visitor. 1698 class BuildLockset : public StmtVisitor<BuildLockset> { 1699 friend class ThreadSafetyAnalyzer; 1700 1701 ThreadSafetyAnalyzer *Analyzer; 1702 FactSet FSet; 1703 LocalVariableMap::Context LVarCtx; 1704 unsigned CtxIndex; 1705 1706 // Helper functions 1707 const ValueDecl *getValueDecl(Expr *Exp); 1708 1709 void warnIfMutexNotHeld(const NamedDecl *D, Expr *Exp, AccessKind AK, 1710 Expr *MutexExp, ProtectedOperationKind POK); 1711 void warnIfMutexHeld(const NamedDecl *D, Expr *Exp, Expr *MutexExp); 1712 1713 void checkAccess(Expr *Exp, AccessKind AK); 1714 void checkDereference(Expr *Exp, AccessKind AK); 1715 void handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD = 0); 1716 1717 public: 1718 BuildLockset(ThreadSafetyAnalyzer *Anlzr, CFGBlockInfo &Info) 1719 : StmtVisitor<BuildLockset>(), 1720 Analyzer(Anlzr), 1721 FSet(Info.EntrySet), 1722 LVarCtx(Info.EntryContext), 1723 CtxIndex(Info.EntryIndex) 1724 {} 1725 1726 void VisitUnaryOperator(UnaryOperator *UO); 1727 void VisitBinaryOperator(BinaryOperator *BO); 1728 void VisitCastExpr(CastExpr *CE); 1729 void VisitCallExpr(CallExpr *Exp); 1730 void VisitCXXConstructExpr(CXXConstructExpr *Exp); 1731 void VisitDeclStmt(DeclStmt *S); 1732 }; 1733 1734 1735 /// \brief Gets the value decl pointer from DeclRefExprs or MemberExprs 1736 const ValueDecl *BuildLockset::getValueDecl(Expr *Exp) { 1737 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Exp)) 1738 return DR->getDecl(); 1739 1740 if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) 1741 return ME->getMemberDecl(); 1742 1743 return 0; 1744 } 1745 1746 /// \brief Warn if the LSet does not contain a lock sufficient to protect access 1747 /// of at least the passed in AccessKind. 1748 void BuildLockset::warnIfMutexNotHeld(const NamedDecl *D, Expr *Exp, 1749 AccessKind AK, Expr *MutexExp, 1750 ProtectedOperationKind POK) { 1751 LockKind LK = getLockKindFromAccessKind(AK); 1752 1753 SExpr Mutex(MutexExp, Exp, D); 1754 if (!Mutex.isValid()) { 1755 SExpr::warnInvalidLock(Analyzer->Handler, MutexExp, Exp, D); 1756 return; 1757 } else if (Mutex.shouldIgnore()) { 1758 return; 1759 } 1760 1761 LockData* LDat = FSet.findLockUniv(Analyzer->FactMan, Mutex); 1762 bool NoError = true; 1763 if (!LDat) { 1764 // No exact match found. Look for a partial match. 1765 FactEntry* FEntry = FSet.findPartialMatch(Analyzer->FactMan, Mutex); 1766 if (FEntry) { 1767 // Warn that there's no precise match. 1768 LDat = &FEntry->LDat; 1769 std::string PartMatchStr = FEntry->MutID.toString(); 1770 StringRef PartMatchName(PartMatchStr); 1771 Analyzer->Handler.handleMutexNotHeld(D, POK, Mutex.toString(), LK, 1772 Exp->getExprLoc(), &PartMatchName); 1773 } else { 1774 // Warn that there's no match at all. 1775 Analyzer->Handler.handleMutexNotHeld(D, POK, Mutex.toString(), LK, 1776 Exp->getExprLoc()); 1777 } 1778 NoError = false; 1779 } 1780 // Make sure the mutex we found is the right kind. 1781 if (NoError && LDat && !LDat->isAtLeast(LK)) 1782 Analyzer->Handler.handleMutexNotHeld(D, POK, Mutex.toString(), LK, 1783 Exp->getExprLoc()); 1784 } 1785 1786 /// \brief Warn if the LSet contains the given lock. 1787 void BuildLockset::warnIfMutexHeld(const NamedDecl *D, Expr* Exp, 1788 Expr *MutexExp) { 1789 SExpr Mutex(MutexExp, Exp, D); 1790 if (!Mutex.isValid()) { 1791 SExpr::warnInvalidLock(Analyzer->Handler, MutexExp, Exp, D); 1792 return; 1793 } 1794 1795 LockData* LDat = FSet.findLock(Analyzer->FactMan, Mutex); 1796 if (LDat) 1797 Analyzer->Handler.handleFunExcludesLock(D->getName(), Mutex.toString(), 1798 Exp->getExprLoc()); 1799 } 1800 1801 1802 /// \brief This method identifies variable dereferences and checks pt_guarded_by 1803 /// and pt_guarded_var annotations. Note that we only check these annotations 1804 /// at the time a pointer is dereferenced. 1805 /// FIXME: We need to check for other types of pointer dereferences 1806 /// (e.g. [], ->) and deal with them here. 1807 /// \param Exp An expression that has been read or written. 1808 void BuildLockset::checkDereference(Expr *Exp, AccessKind AK) { 1809 UnaryOperator *UO = dyn_cast<UnaryOperator>(Exp); 1810 if (!UO || UO->getOpcode() != clang::UO_Deref) 1811 return; 1812 Exp = UO->getSubExpr()->IgnoreParenCasts(); 1813 1814 const ValueDecl *D = getValueDecl(Exp); 1815 if(!D || !D->hasAttrs()) 1816 return; 1817 1818 if (D->getAttr<PtGuardedVarAttr>() && FSet.isEmpty()) 1819 Analyzer->Handler.handleNoMutexHeld(D, POK_VarDereference, AK, 1820 Exp->getExprLoc()); 1821 1822 const AttrVec &ArgAttrs = D->getAttrs(); 1823 for(unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i) 1824 if (PtGuardedByAttr *PGBAttr = dyn_cast<PtGuardedByAttr>(ArgAttrs[i])) 1825 warnIfMutexNotHeld(D, Exp, AK, PGBAttr->getArg(), POK_VarDereference); 1826 } 1827 1828 /// \brief Checks guarded_by and guarded_var attributes. 1829 /// Whenever we identify an access (read or write) of a DeclRefExpr or 1830 /// MemberExpr, we need to check whether there are any guarded_by or 1831 /// guarded_var attributes, and make sure we hold the appropriate mutexes. 1832 void BuildLockset::checkAccess(Expr *Exp, AccessKind AK) { 1833 const ValueDecl *D = getValueDecl(Exp); 1834 if(!D || !D->hasAttrs()) 1835 return; 1836 1837 if (D->getAttr<GuardedVarAttr>() && FSet.isEmpty()) 1838 Analyzer->Handler.handleNoMutexHeld(D, POK_VarAccess, AK, 1839 Exp->getExprLoc()); 1840 1841 const AttrVec &ArgAttrs = D->getAttrs(); 1842 for(unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i) 1843 if (GuardedByAttr *GBAttr = dyn_cast<GuardedByAttr>(ArgAttrs[i])) 1844 warnIfMutexNotHeld(D, Exp, AK, GBAttr->getArg(), POK_VarAccess); 1845 } 1846 1847 /// \brief Process a function call, method call, constructor call, 1848 /// or destructor call. This involves looking at the attributes on the 1849 /// corresponding function/method/constructor/destructor, issuing warnings, 1850 /// and updating the locksets accordingly. 1851 /// 1852 /// FIXME: For classes annotated with one of the guarded annotations, we need 1853 /// to treat const method calls as reads and non-const method calls as writes, 1854 /// and check that the appropriate locks are held. Non-const method calls with 1855 /// the same signature as const method calls can be also treated as reads. 1856 /// 1857 void BuildLockset::handleCall(Expr *Exp, const NamedDecl *D, VarDecl *VD) { 1858 const AttrVec &ArgAttrs = D->getAttrs(); 1859 MutexIDList ExclusiveLocksToAdd; 1860 MutexIDList SharedLocksToAdd; 1861 MutexIDList LocksToRemove; 1862 1863 for(unsigned i = 0; i < ArgAttrs.size(); ++i) { 1864 Attr *At = const_cast<Attr*>(ArgAttrs[i]); 1865 switch (At->getKind()) { 1866 // When we encounter an exclusive lock function, we need to add the lock 1867 // to our lockset with kind exclusive. 1868 case attr::ExclusiveLockFunction: { 1869 ExclusiveLockFunctionAttr *A = cast<ExclusiveLockFunctionAttr>(At); 1870 Analyzer->getMutexIDs(ExclusiveLocksToAdd, A, Exp, D); 1871 break; 1872 } 1873 1874 // When we encounter a shared lock function, we need to add the lock 1875 // to our lockset with kind shared. 1876 case attr::SharedLockFunction: { 1877 SharedLockFunctionAttr *A = cast<SharedLockFunctionAttr>(At); 1878 Analyzer->getMutexIDs(SharedLocksToAdd, A, Exp, D); 1879 break; 1880 } 1881 1882 // When we encounter an unlock function, we need to remove unlocked 1883 // mutexes from the lockset, and flag a warning if they are not there. 1884 case attr::UnlockFunction: { 1885 UnlockFunctionAttr *A = cast<UnlockFunctionAttr>(At); 1886 Analyzer->getMutexIDs(LocksToRemove, A, Exp, D); 1887 break; 1888 } 1889 1890 case attr::ExclusiveLocksRequired: { 1891 ExclusiveLocksRequiredAttr *A = cast<ExclusiveLocksRequiredAttr>(At); 1892 1893 for (ExclusiveLocksRequiredAttr::args_iterator 1894 I = A->args_begin(), E = A->args_end(); I != E; ++I) 1895 warnIfMutexNotHeld(D, Exp, AK_Written, *I, POK_FunctionCall); 1896 break; 1897 } 1898 1899 case attr::SharedLocksRequired: { 1900 SharedLocksRequiredAttr *A = cast<SharedLocksRequiredAttr>(At); 1901 1902 for (SharedLocksRequiredAttr::args_iterator I = A->args_begin(), 1903 E = A->args_end(); I != E; ++I) 1904 warnIfMutexNotHeld(D, Exp, AK_Read, *I, POK_FunctionCall); 1905 break; 1906 } 1907 1908 case attr::LocksExcluded: { 1909 LocksExcludedAttr *A = cast<LocksExcludedAttr>(At); 1910 1911 for (LocksExcludedAttr::args_iterator I = A->args_begin(), 1912 E = A->args_end(); I != E; ++I) { 1913 warnIfMutexHeld(D, Exp, *I); 1914 } 1915 break; 1916 } 1917 1918 // Ignore other (non thread-safety) attributes 1919 default: 1920 break; 1921 } 1922 } 1923 1924 // Figure out if we're calling the constructor of scoped lockable class 1925 bool isScopedVar = false; 1926 if (VD) { 1927 if (const CXXConstructorDecl *CD = dyn_cast<const CXXConstructorDecl>(D)) { 1928 const CXXRecordDecl* PD = CD->getParent(); 1929 if (PD && PD->getAttr<ScopedLockableAttr>()) 1930 isScopedVar = true; 1931 } 1932 } 1933 1934 // Add locks. 1935 SourceLocation Loc = Exp->getExprLoc(); 1936 for (unsigned i=0,n=ExclusiveLocksToAdd.size(); i<n; ++i) { 1937 Analyzer->addLock(FSet, ExclusiveLocksToAdd[i], 1938 LockData(Loc, LK_Exclusive, isScopedVar)); 1939 } 1940 for (unsigned i=0,n=SharedLocksToAdd.size(); i<n; ++i) { 1941 Analyzer->addLock(FSet, SharedLocksToAdd[i], 1942 LockData(Loc, LK_Shared, isScopedVar)); 1943 } 1944 1945 // Add the managing object as a dummy mutex, mapped to the underlying mutex. 1946 // FIXME -- this doesn't work if we acquire multiple locks. 1947 if (isScopedVar) { 1948 SourceLocation MLoc = VD->getLocation(); 1949 DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, VD->getLocation()); 1950 SExpr SMutex(&DRE, 0, 0); 1951 1952 for (unsigned i=0,n=ExclusiveLocksToAdd.size(); i<n; ++i) { 1953 Analyzer->addLock(FSet, SMutex, LockData(MLoc, LK_Exclusive, 1954 ExclusiveLocksToAdd[i])); 1955 } 1956 for (unsigned i=0,n=SharedLocksToAdd.size(); i<n; ++i) { 1957 Analyzer->addLock(FSet, SMutex, LockData(MLoc, LK_Shared, 1958 SharedLocksToAdd[i])); 1959 } 1960 } 1961 1962 // Remove locks. 1963 // FIXME -- should only fully remove if the attribute refers to 'this'. 1964 bool Dtor = isa<CXXDestructorDecl>(D); 1965 for (unsigned i=0,n=LocksToRemove.size(); i<n; ++i) { 1966 Analyzer->removeLock(FSet, LocksToRemove[i], Loc, Dtor); 1967 } 1968 } 1969 1970 1971 /// \brief For unary operations which read and write a variable, we need to 1972 /// check whether we hold any required mutexes. Reads are checked in 1973 /// VisitCastExpr. 1974 void BuildLockset::VisitUnaryOperator(UnaryOperator *UO) { 1975 switch (UO->getOpcode()) { 1976 case clang::UO_PostDec: 1977 case clang::UO_PostInc: 1978 case clang::UO_PreDec: 1979 case clang::UO_PreInc: { 1980 Expr *SubExp = UO->getSubExpr()->IgnoreParenCasts(); 1981 checkAccess(SubExp, AK_Written); 1982 checkDereference(SubExp, AK_Written); 1983 break; 1984 } 1985 default: 1986 break; 1987 } 1988 } 1989 1990 /// For binary operations which assign to a variable (writes), we need to check 1991 /// whether we hold any required mutexes. 1992 /// FIXME: Deal with non-primitive types. 1993 void BuildLockset::VisitBinaryOperator(BinaryOperator *BO) { 1994 if (!BO->isAssignmentOp()) 1995 return; 1996 1997 // adjust the context 1998 LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, BO, LVarCtx); 1999 2000 Expr *LHSExp = BO->getLHS()->IgnoreParenCasts(); 2001 checkAccess(LHSExp, AK_Written); 2002 checkDereference(LHSExp, AK_Written); 2003 } 2004 2005 /// Whenever we do an LValue to Rvalue cast, we are reading a variable and 2006 /// need to ensure we hold any required mutexes. 2007 /// FIXME: Deal with non-primitive types. 2008 void BuildLockset::VisitCastExpr(CastExpr *CE) { 2009 if (CE->getCastKind() != CK_LValueToRValue) 2010 return; 2011 Expr *SubExp = CE->getSubExpr()->IgnoreParenCasts(); 2012 checkAccess(SubExp, AK_Read); 2013 checkDereference(SubExp, AK_Read); 2014 } 2015 2016 2017 void BuildLockset::VisitCallExpr(CallExpr *Exp) { 2018 NamedDecl *D = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); 2019 if(!D || !D->hasAttrs()) 2020 return; 2021 handleCall(Exp, D); 2022 } 2023 2024 void BuildLockset::VisitCXXConstructExpr(CXXConstructExpr *Exp) { 2025 // FIXME -- only handles constructors in DeclStmt below. 2026 } 2027 2028 void BuildLockset::VisitDeclStmt(DeclStmt *S) { 2029 // adjust the context 2030 LVarCtx = Analyzer->LocalVarMap.getNextContext(CtxIndex, S, LVarCtx); 2031 2032 DeclGroupRef DGrp = S->getDeclGroup(); 2033 for (DeclGroupRef::iterator I = DGrp.begin(), E = DGrp.end(); I != E; ++I) { 2034 Decl *D = *I; 2035 if (VarDecl *VD = dyn_cast_or_null<VarDecl>(D)) { 2036 Expr *E = VD->getInit(); 2037 // handle constructors that involve temporaries 2038 if (ExprWithCleanups *EWC = dyn_cast_or_null<ExprWithCleanups>(E)) 2039 E = EWC->getSubExpr(); 2040 2041 if (CXXConstructExpr *CE = dyn_cast_or_null<CXXConstructExpr>(E)) { 2042 NamedDecl *CtorD = dyn_cast_or_null<NamedDecl>(CE->getConstructor()); 2043 if (!CtorD || !CtorD->hasAttrs()) 2044 return; 2045 handleCall(CE, CtorD, VD); 2046 } 2047 } 2048 } 2049 } 2050 2051 2052 2053 /// \brief Compute the intersection of two locksets and issue warnings for any 2054 /// locks in the symmetric difference. 2055 /// 2056 /// This function is used at a merge point in the CFG when comparing the lockset 2057 /// of each branch being merged. For example, given the following sequence: 2058 /// A; if () then B; else C; D; we need to check that the lockset after B and C 2059 /// are the same. In the event of a difference, we use the intersection of these 2060 /// two locksets at the start of D. 2061 /// 2062 /// \param FSet1 The first lockset. 2063 /// \param FSet2 The second lockset. 2064 /// \param JoinLoc The location of the join point for error reporting 2065 /// \param LEK1 The error message to report if a mutex is missing from LSet1 2066 /// \param LEK2 The error message to report if a mutex is missing from Lset2 2067 void ThreadSafetyAnalyzer::intersectAndWarn(FactSet &FSet1, 2068 const FactSet &FSet2, 2069 SourceLocation JoinLoc, 2070 LockErrorKind LEK1, 2071 LockErrorKind LEK2, 2072 bool Modify) { 2073 FactSet FSet1Orig = FSet1; 2074 2075 for (FactSet::const_iterator I = FSet2.begin(), E = FSet2.end(); 2076 I != E; ++I) { 2077 const SExpr &FSet2Mutex = FactMan[*I].MutID; 2078 const LockData &LDat2 = FactMan[*I].LDat; 2079 2080 if (const LockData *LDat1 = FSet1.findLock(FactMan, FSet2Mutex)) { 2081 if (LDat1->LKind != LDat2.LKind) { 2082 Handler.handleExclusiveAndShared(FSet2Mutex.toString(), 2083 LDat2.AcquireLoc, 2084 LDat1->AcquireLoc); 2085 if (Modify && LDat1->LKind != LK_Exclusive) { 2086 FSet1.removeLock(FactMan, FSet2Mutex); 2087 FSet1.addLock(FactMan, FSet2Mutex, LDat2); 2088 } 2089 } 2090 } else { 2091 if (LDat2.UnderlyingMutex.isValid()) { 2092 if (FSet2.findLock(FactMan, LDat2.UnderlyingMutex)) { 2093 // If this is a scoped lock that manages another mutex, and if the 2094 // underlying mutex is still held, then warn about the underlying 2095 // mutex. 2096 Handler.handleMutexHeldEndOfScope(LDat2.UnderlyingMutex.toString(), 2097 LDat2.AcquireLoc, 2098 JoinLoc, LEK1); 2099 } 2100 } 2101 else if (!LDat2.Managed && !FSet2Mutex.isUniversal()) 2102 Handler.handleMutexHeldEndOfScope(FSet2Mutex.toString(), 2103 LDat2.AcquireLoc, 2104 JoinLoc, LEK1); 2105 } 2106 } 2107 2108 for (FactSet::const_iterator I = FSet1.begin(), E = FSet1.end(); 2109 I != E; ++I) { 2110 const SExpr &FSet1Mutex = FactMan[*I].MutID; 2111 const LockData &LDat1 = FactMan[*I].LDat; 2112 2113 if (!FSet2.findLock(FactMan, FSet1Mutex)) { 2114 if (LDat1.UnderlyingMutex.isValid()) { 2115 if (FSet1Orig.findLock(FactMan, LDat1.UnderlyingMutex)) { 2116 // If this is a scoped lock that manages another mutex, and if the 2117 // underlying mutex is still held, then warn about the underlying 2118 // mutex. 2119 Handler.handleMutexHeldEndOfScope(LDat1.UnderlyingMutex.toString(), 2120 LDat1.AcquireLoc, 2121 JoinLoc, LEK1); 2122 } 2123 } 2124 else if (!LDat1.Managed && !FSet1Mutex.isUniversal()) 2125 Handler.handleMutexHeldEndOfScope(FSet1Mutex.toString(), 2126 LDat1.AcquireLoc, 2127 JoinLoc, LEK2); 2128 if (Modify) 2129 FSet1.removeLock(FactMan, FSet1Mutex); 2130 } 2131 } 2132 } 2133 2134 2135 2136 /// \brief Check a function's CFG for thread-safety violations. 2137 /// 2138 /// We traverse the blocks in the CFG, compute the set of mutexes that are held 2139 /// at the end of each block, and issue warnings for thread safety violations. 2140 /// Each block in the CFG is traversed exactly once. 2141 void ThreadSafetyAnalyzer::runAnalysis(AnalysisDeclContext &AC) { 2142 CFG *CFGraph = AC.getCFG(); 2143 if (!CFGraph) return; 2144 const NamedDecl *D = dyn_cast_or_null<NamedDecl>(AC.getDecl()); 2145 2146 // AC.dumpCFG(true); 2147 2148 if (!D) 2149 return; // Ignore anonymous functions for now. 2150 if (D->getAttr<NoThreadSafetyAnalysisAttr>()) 2151 return; 2152 // FIXME: Do something a bit more intelligent inside constructor and 2153 // destructor code. Constructors and destructors must assume unique access 2154 // to 'this', so checks on member variable access is disabled, but we should 2155 // still enable checks on other objects. 2156 if (isa<CXXConstructorDecl>(D)) 2157 return; // Don't check inside constructors. 2158 if (isa<CXXDestructorDecl>(D)) 2159 return; // Don't check inside destructors. 2160 2161 BlockInfo.resize(CFGraph->getNumBlockIDs(), 2162 CFGBlockInfo::getEmptyBlockInfo(LocalVarMap)); 2163 2164 // We need to explore the CFG via a "topological" ordering. 2165 // That way, we will be guaranteed to have information about required 2166 // predecessor locksets when exploring a new block. 2167 PostOrderCFGView *SortedGraph = AC.getAnalysis<PostOrderCFGView>(); 2168 PostOrderCFGView::CFGBlockSet VisitedBlocks(CFGraph); 2169 2170 // Compute SSA names for local variables 2171 LocalVarMap.traverseCFG(CFGraph, SortedGraph, BlockInfo); 2172 2173 // Fill in source locations for all CFGBlocks. 2174 findBlockLocations(CFGraph, SortedGraph, BlockInfo); 2175 2176 // Add locks from exclusive_locks_required and shared_locks_required 2177 // to initial lockset. Also turn off checking for lock and unlock functions. 2178 // FIXME: is there a more intelligent way to check lock/unlock functions? 2179 if (!SortedGraph->empty() && D->hasAttrs()) { 2180 const CFGBlock *FirstBlock = *SortedGraph->begin(); 2181 FactSet &InitialLockset = BlockInfo[FirstBlock->getBlockID()].EntrySet; 2182 const AttrVec &ArgAttrs = D->getAttrs(); 2183 2184 MutexIDList ExclusiveLocksToAdd; 2185 MutexIDList SharedLocksToAdd; 2186 2187 SourceLocation Loc = D->getLocation(); 2188 for (unsigned i = 0; i < ArgAttrs.size(); ++i) { 2189 Attr *Attr = ArgAttrs[i]; 2190 Loc = Attr->getLocation(); 2191 if (ExclusiveLocksRequiredAttr *A 2192 = dyn_cast<ExclusiveLocksRequiredAttr>(Attr)) { 2193 getMutexIDs(ExclusiveLocksToAdd, A, (Expr*) 0, D); 2194 } else if (SharedLocksRequiredAttr *A 2195 = dyn_cast<SharedLocksRequiredAttr>(Attr)) { 2196 getMutexIDs(SharedLocksToAdd, A, (Expr*) 0, D); 2197 } else if (isa<UnlockFunctionAttr>(Attr)) { 2198 // Don't try to check unlock functions for now 2199 return; 2200 } else if (isa<ExclusiveLockFunctionAttr>(Attr)) { 2201 // Don't try to check lock functions for now 2202 return; 2203 } else if (isa<SharedLockFunctionAttr>(Attr)) { 2204 // Don't try to check lock functions for now 2205 return; 2206 } else if (isa<ExclusiveTrylockFunctionAttr>(Attr)) { 2207 // Don't try to check trylock functions for now 2208 return; 2209 } else if (isa<SharedTrylockFunctionAttr>(Attr)) { 2210 // Don't try to check trylock functions for now 2211 return; 2212 } 2213 } 2214 2215 // FIXME -- Loc can be wrong here. 2216 for (unsigned i=0,n=ExclusiveLocksToAdd.size(); i<n; ++i) { 2217 addLock(InitialLockset, ExclusiveLocksToAdd[i], 2218 LockData(Loc, LK_Exclusive)); 2219 } 2220 for (unsigned i=0,n=SharedLocksToAdd.size(); i<n; ++i) { 2221 addLock(InitialLockset, SharedLocksToAdd[i], 2222 LockData(Loc, LK_Shared)); 2223 } 2224 } 2225 2226 for (PostOrderCFGView::iterator I = SortedGraph->begin(), 2227 E = SortedGraph->end(); I!= E; ++I) { 2228 const CFGBlock *CurrBlock = *I; 2229 int CurrBlockID = CurrBlock->getBlockID(); 2230 CFGBlockInfo *CurrBlockInfo = &BlockInfo[CurrBlockID]; 2231 2232 // Use the default initial lockset in case there are no predecessors. 2233 VisitedBlocks.insert(CurrBlock); 2234 2235 // Iterate through the predecessor blocks and warn if the lockset for all 2236 // predecessors is not the same. We take the entry lockset of the current 2237 // block to be the intersection of all previous locksets. 2238 // FIXME: By keeping the intersection, we may output more errors in future 2239 // for a lock which is not in the intersection, but was in the union. We 2240 // may want to also keep the union in future. As an example, let's say 2241 // the intersection contains Mutex L, and the union contains L and M. 2242 // Later we unlock M. At this point, we would output an error because we 2243 // never locked M; although the real error is probably that we forgot to 2244 // lock M on all code paths. Conversely, let's say that later we lock M. 2245 // In this case, we should compare against the intersection instead of the 2246 // union because the real error is probably that we forgot to unlock M on 2247 // all code paths. 2248 bool LocksetInitialized = false; 2249 llvm::SmallVector<CFGBlock*, 8> SpecialBlocks; 2250 for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), 2251 PE = CurrBlock->pred_end(); PI != PE; ++PI) { 2252 2253 // if *PI -> CurrBlock is a back edge 2254 if (*PI == 0 || !VisitedBlocks.alreadySet(*PI)) 2255 continue; 2256 2257 // Ignore edges from blocks that can't return. 2258 if ((*PI)->hasNoReturnElement()) 2259 continue; 2260 2261 // If the previous block ended in a 'continue' or 'break' statement, then 2262 // a difference in locksets is probably due to a bug in that block, rather 2263 // than in some other predecessor. In that case, keep the other 2264 // predecessor's lockset. 2265 if (const Stmt *Terminator = (*PI)->getTerminator()) { 2266 if (isa<ContinueStmt>(Terminator) || isa<BreakStmt>(Terminator)) { 2267 SpecialBlocks.push_back(*PI); 2268 continue; 2269 } 2270 } 2271 2272 int PrevBlockID = (*PI)->getBlockID(); 2273 CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; 2274 FactSet PrevLockset; 2275 getEdgeLockset(PrevLockset, PrevBlockInfo->ExitSet, *PI, CurrBlock); 2276 2277 if (!LocksetInitialized) { 2278 CurrBlockInfo->EntrySet = PrevLockset; 2279 LocksetInitialized = true; 2280 } else { 2281 intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset, 2282 CurrBlockInfo->EntryLoc, 2283 LEK_LockedSomePredecessors); 2284 } 2285 } 2286 2287 // Process continue and break blocks. Assume that the lockset for the 2288 // resulting block is unaffected by any discrepancies in them. 2289 for (unsigned SpecialI = 0, SpecialN = SpecialBlocks.size(); 2290 SpecialI < SpecialN; ++SpecialI) { 2291 CFGBlock *PrevBlock = SpecialBlocks[SpecialI]; 2292 int PrevBlockID = PrevBlock->getBlockID(); 2293 CFGBlockInfo *PrevBlockInfo = &BlockInfo[PrevBlockID]; 2294 2295 if (!LocksetInitialized) { 2296 CurrBlockInfo->EntrySet = PrevBlockInfo->ExitSet; 2297 LocksetInitialized = true; 2298 } else { 2299 // Determine whether this edge is a loop terminator for diagnostic 2300 // purposes. FIXME: A 'break' statement might be a loop terminator, but 2301 // it might also be part of a switch. Also, a subsequent destructor 2302 // might add to the lockset, in which case the real issue might be a 2303 // double lock on the other path. 2304 const Stmt *Terminator = PrevBlock->getTerminator(); 2305 bool IsLoop = Terminator && isa<ContinueStmt>(Terminator); 2306 2307 FactSet PrevLockset; 2308 getEdgeLockset(PrevLockset, PrevBlockInfo->ExitSet, 2309 PrevBlock, CurrBlock); 2310 2311 // Do not update EntrySet. 2312 intersectAndWarn(CurrBlockInfo->EntrySet, PrevLockset, 2313 PrevBlockInfo->ExitLoc, 2314 IsLoop ? LEK_LockedSomeLoopIterations 2315 : LEK_LockedSomePredecessors, 2316 false); 2317 } 2318 } 2319 2320 BuildLockset LocksetBuilder(this, *CurrBlockInfo); 2321 2322 // Visit all the statements in the basic block. 2323 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 2324 BE = CurrBlock->end(); BI != BE; ++BI) { 2325 switch (BI->getKind()) { 2326 case CFGElement::Statement: { 2327 const CFGStmt *CS = cast<CFGStmt>(&*BI); 2328 LocksetBuilder.Visit(const_cast<Stmt*>(CS->getStmt())); 2329 break; 2330 } 2331 // Ignore BaseDtor, MemberDtor, and TemporaryDtor for now. 2332 case CFGElement::AutomaticObjectDtor: { 2333 const CFGAutomaticObjDtor *AD = cast<CFGAutomaticObjDtor>(&*BI); 2334 CXXDestructorDecl *DD = const_cast<CXXDestructorDecl*>( 2335 AD->getDestructorDecl(AC.getASTContext())); 2336 if (!DD->hasAttrs()) 2337 break; 2338 2339 // Create a dummy expression, 2340 VarDecl *VD = const_cast<VarDecl*>(AD->getVarDecl()); 2341 DeclRefExpr DRE(VD, false, VD->getType(), VK_LValue, 2342 AD->getTriggerStmt()->getLocEnd()); 2343 LocksetBuilder.handleCall(&DRE, DD); 2344 break; 2345 } 2346 default: 2347 break; 2348 } 2349 } 2350 CurrBlockInfo->ExitSet = LocksetBuilder.FSet; 2351 2352 // For every back edge from CurrBlock (the end of the loop) to another block 2353 // (FirstLoopBlock) we need to check that the Lockset of Block is equal to 2354 // the one held at the beginning of FirstLoopBlock. We can look up the 2355 // Lockset held at the beginning of FirstLoopBlock in the EntryLockSets map. 2356 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 2357 SE = CurrBlock->succ_end(); SI != SE; ++SI) { 2358 2359 // if CurrBlock -> *SI is *not* a back edge 2360 if (*SI == 0 || !VisitedBlocks.alreadySet(*SI)) 2361 continue; 2362 2363 CFGBlock *FirstLoopBlock = *SI; 2364 CFGBlockInfo *PreLoop = &BlockInfo[FirstLoopBlock->getBlockID()]; 2365 CFGBlockInfo *LoopEnd = &BlockInfo[CurrBlockID]; 2366 intersectAndWarn(LoopEnd->ExitSet, PreLoop->EntrySet, 2367 PreLoop->EntryLoc, 2368 LEK_LockedSomeLoopIterations, 2369 false); 2370 } 2371 } 2372 2373 CFGBlockInfo *Initial = &BlockInfo[CFGraph->getEntry().getBlockID()]; 2374 CFGBlockInfo *Final = &BlockInfo[CFGraph->getExit().getBlockID()]; 2375 2376 // FIXME: Should we call this function for all blocks which exit the function? 2377 intersectAndWarn(Initial->EntrySet, Final->ExitSet, 2378 Final->ExitLoc, 2379 LEK_LockedAtEndOfFunction, 2380 LEK_NotLockedAtEndOfFunction, 2381 false); 2382 } 2383 2384 } // end anonymous namespace 2385 2386 2387 namespace clang { 2388 namespace thread_safety { 2389 2390 /// \brief Check a function's CFG for thread-safety violations. 2391 /// 2392 /// We traverse the blocks in the CFG, compute the set of mutexes that are held 2393 /// at the end of each block, and issue warnings for thread safety violations. 2394 /// Each block in the CFG is traversed exactly once. 2395 void runThreadSafetyAnalysis(AnalysisDeclContext &AC, 2396 ThreadSafetyHandler &Handler) { 2397 ThreadSafetyAnalyzer Analyzer(Handler); 2398 Analyzer.runAnalysis(AC); 2399 } 2400 2401 /// \brief Helper function that returns a LockKind required for the given level 2402 /// of access. 2403 LockKind getLockKindFromAccessKind(AccessKind AK) { 2404 switch (AK) { 2405 case AK_Read : 2406 return LK_Shared; 2407 case AK_Written : 2408 return LK_Exclusive; 2409 } 2410 llvm_unreachable("Unknown AccessKind"); 2411 } 2412 2413 }} // end namespace clang::thread_safety 2414