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