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