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