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