AnalysisBasedWarnings.cpp revision b0656ec72e25e5c8e463c2dc39914636f0cb06d1
1//=- AnalysisBasedWarnings.cpp - Sema warnings based on libAnalysis -*- 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// This file defines analysis_warnings::[Policy,Executor]. 11// Together they are used by Sema to issue warnings based on inexpensive 12// static analysis algorithms in libAnalysis. 13// 14//===----------------------------------------------------------------------===// 15 16#include "clang/Sema/AnalysisBasedWarnings.h" 17#include "clang/Sema/SemaInternal.h" 18#include "clang/Sema/ScopeInfo.h" 19#include "clang/Basic/SourceManager.h" 20#include "clang/Lex/Preprocessor.h" 21#include "clang/AST/DeclObjC.h" 22#include "clang/AST/DeclCXX.h" 23#include "clang/AST/ExprObjC.h" 24#include "clang/AST/ExprCXX.h" 25#include "clang/AST/StmtObjC.h" 26#include "clang/AST/StmtCXX.h" 27#include "clang/AST/EvaluatedExprVisitor.h" 28#include "clang/AST/StmtVisitor.h" 29#include "clang/Analysis/AnalysisContext.h" 30#include "clang/Analysis/CFG.h" 31#include "clang/Analysis/Analyses/ReachableCode.h" 32#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h" 33#include "clang/Analysis/CFGStmtMap.h" 34#include "clang/Analysis/Analyses/UninitializedValues.h" 35#include "llvm/ADT/BitVector.h" 36#include "llvm/ADT/FoldingSet.h" 37#include "llvm/ADT/ImmutableMap.h" 38#include "llvm/ADT/PostOrderIterator.h" 39#include "llvm/ADT/SmallVector.h" 40#include "llvm/Support/Casting.h" 41#include <algorithm> 42#include <vector> 43 44using namespace clang; 45 46//===----------------------------------------------------------------------===// 47// Unreachable code analysis. 48//===----------------------------------------------------------------------===// 49 50namespace { 51 class UnreachableCodeHandler : public reachable_code::Callback { 52 Sema &S; 53 public: 54 UnreachableCodeHandler(Sema &s) : S(s) {} 55 56 void HandleUnreachable(SourceLocation L, SourceRange R1, SourceRange R2) { 57 S.Diag(L, diag::warn_unreachable) << R1 << R2; 58 } 59 }; 60} 61 62/// CheckUnreachable - Check for unreachable code. 63static void CheckUnreachable(Sema &S, AnalysisContext &AC) { 64 UnreachableCodeHandler UC(S); 65 reachable_code::FindUnreachableCode(AC, UC); 66} 67 68//===----------------------------------------------------------------------===// 69// Check for missing return value. 70//===----------------------------------------------------------------------===// 71 72enum ControlFlowKind { 73 UnknownFallThrough, 74 NeverFallThrough, 75 MaybeFallThrough, 76 AlwaysFallThrough, 77 NeverFallThroughOrReturn 78}; 79 80/// CheckFallThrough - Check that we don't fall off the end of a 81/// Statement that should return a value. 82/// 83/// \returns AlwaysFallThrough iff we always fall off the end of the statement, 84/// MaybeFallThrough iff we might or might not fall off the end, 85/// NeverFallThroughOrReturn iff we never fall off the end of the statement or 86/// return. We assume NeverFallThrough iff we never fall off the end of the 87/// statement but we may return. We assume that functions not marked noreturn 88/// will return. 89static ControlFlowKind CheckFallThrough(AnalysisContext &AC) { 90 CFG *cfg = AC.getCFG(); 91 if (cfg == 0) return UnknownFallThrough; 92 93 // The CFG leaves in dead things, and we don't want the dead code paths to 94 // confuse us, so we mark all live things first. 95 llvm::BitVector live(cfg->getNumBlockIDs()); 96 unsigned count = reachable_code::ScanReachableFromBlock(&cfg->getEntry(), 97 live); 98 99 bool AddEHEdges = AC.getAddEHEdges(); 100 if (!AddEHEdges && count != cfg->getNumBlockIDs()) 101 // When there are things remaining dead, and we didn't add EH edges 102 // from CallExprs to the catch clauses, we have to go back and 103 // mark them as live. 104 for (CFG::iterator I = cfg->begin(), E = cfg->end(); I != E; ++I) { 105 CFGBlock &b = **I; 106 if (!live[b.getBlockID()]) { 107 if (b.pred_begin() == b.pred_end()) { 108 if (b.getTerminator() && isa<CXXTryStmt>(b.getTerminator())) 109 // When not adding EH edges from calls, catch clauses 110 // can otherwise seem dead. Avoid noting them as dead. 111 count += reachable_code::ScanReachableFromBlock(&b, live); 112 continue; 113 } 114 } 115 } 116 117 // Now we know what is live, we check the live precessors of the exit block 118 // and look for fall through paths, being careful to ignore normal returns, 119 // and exceptional paths. 120 bool HasLiveReturn = false; 121 bool HasFakeEdge = false; 122 bool HasPlainEdge = false; 123 bool HasAbnormalEdge = false; 124 125 // Ignore default cases that aren't likely to be reachable because all 126 // enums in a switch(X) have explicit case statements. 127 CFGBlock::FilterOptions FO; 128 FO.IgnoreDefaultsWithCoveredEnums = 1; 129 130 for (CFGBlock::filtered_pred_iterator 131 I = cfg->getExit().filtered_pred_start_end(FO); I.hasMore(); ++I) { 132 const CFGBlock& B = **I; 133 if (!live[B.getBlockID()]) 134 continue; 135 136 // Destructors can appear after the 'return' in the CFG. This is 137 // normal. We need to look pass the destructors for the return 138 // statement (if it exists). 139 CFGBlock::const_reverse_iterator ri = B.rbegin(), re = B.rend(); 140 bool hasNoReturnDtor = false; 141 142 for ( ; ri != re ; ++ri) { 143 CFGElement CE = *ri; 144 145 // FIXME: The right solution is to just sever the edges in the 146 // CFG itself. 147 if (const CFGImplicitDtor *iDtor = ri->getAs<CFGImplicitDtor>()) 148 if (iDtor->isNoReturn(AC.getASTContext())) { 149 hasNoReturnDtor = true; 150 HasFakeEdge = true; 151 break; 152 } 153 154 if (isa<CFGStmt>(CE)) 155 break; 156 } 157 158 if (hasNoReturnDtor) 159 continue; 160 161 // No more CFGElements in the block? 162 if (ri == re) { 163 if (B.getTerminator() && isa<CXXTryStmt>(B.getTerminator())) { 164 HasAbnormalEdge = true; 165 continue; 166 } 167 // A labeled empty statement, or the entry block... 168 HasPlainEdge = true; 169 continue; 170 } 171 172 CFGStmt CS = cast<CFGStmt>(*ri); 173 const Stmt *S = CS.getStmt(); 174 if (isa<ReturnStmt>(S)) { 175 HasLiveReturn = true; 176 continue; 177 } 178 if (isa<ObjCAtThrowStmt>(S)) { 179 HasFakeEdge = true; 180 continue; 181 } 182 if (isa<CXXThrowExpr>(S)) { 183 HasFakeEdge = true; 184 continue; 185 } 186 if (const AsmStmt *AS = dyn_cast<AsmStmt>(S)) { 187 if (AS->isMSAsm()) { 188 HasFakeEdge = true; 189 HasLiveReturn = true; 190 continue; 191 } 192 } 193 if (isa<CXXTryStmt>(S)) { 194 HasAbnormalEdge = true; 195 continue; 196 } 197 198 bool NoReturnEdge = false; 199 if (const CallExpr *C = dyn_cast<CallExpr>(S)) { 200 if (std::find(B.succ_begin(), B.succ_end(), &cfg->getExit()) 201 == B.succ_end()) { 202 HasAbnormalEdge = true; 203 continue; 204 } 205 const Expr *CEE = C->getCallee()->IgnoreParenCasts(); 206 QualType calleeType = CEE->getType(); 207 if (calleeType == AC.getASTContext().BoundMemberTy) { 208 calleeType = Expr::findBoundMemberType(CEE); 209 assert(!calleeType.isNull() && "analyzing unresolved call?"); 210 } 211 if (getFunctionExtInfo(calleeType).getNoReturn()) { 212 NoReturnEdge = true; 213 HasFakeEdge = true; 214 } else if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(CEE)) { 215 const ValueDecl *VD = DRE->getDecl(); 216 if (VD->hasAttr<NoReturnAttr>()) { 217 NoReturnEdge = true; 218 HasFakeEdge = true; 219 } 220 } 221 } 222 // FIXME: Add noreturn message sends. 223 if (NoReturnEdge == false) 224 HasPlainEdge = true; 225 } 226 if (!HasPlainEdge) { 227 if (HasLiveReturn) 228 return NeverFallThrough; 229 return NeverFallThroughOrReturn; 230 } 231 if (HasAbnormalEdge || HasFakeEdge || HasLiveReturn) 232 return MaybeFallThrough; 233 // This says AlwaysFallThrough for calls to functions that are not marked 234 // noreturn, that don't return. If people would like this warning to be more 235 // accurate, such functions should be marked as noreturn. 236 return AlwaysFallThrough; 237} 238 239namespace { 240 241struct CheckFallThroughDiagnostics { 242 unsigned diag_MaybeFallThrough_HasNoReturn; 243 unsigned diag_MaybeFallThrough_ReturnsNonVoid; 244 unsigned diag_AlwaysFallThrough_HasNoReturn; 245 unsigned diag_AlwaysFallThrough_ReturnsNonVoid; 246 unsigned diag_NeverFallThroughOrReturn; 247 bool funMode; 248 SourceLocation FuncLoc; 249 250 static CheckFallThroughDiagnostics MakeForFunction(const Decl *Func) { 251 CheckFallThroughDiagnostics D; 252 D.FuncLoc = Func->getLocation(); 253 D.diag_MaybeFallThrough_HasNoReturn = 254 diag::warn_falloff_noreturn_function; 255 D.diag_MaybeFallThrough_ReturnsNonVoid = 256 diag::warn_maybe_falloff_nonvoid_function; 257 D.diag_AlwaysFallThrough_HasNoReturn = 258 diag::warn_falloff_noreturn_function; 259 D.diag_AlwaysFallThrough_ReturnsNonVoid = 260 diag::warn_falloff_nonvoid_function; 261 262 // Don't suggest that virtual functions be marked "noreturn", since they 263 // might be overridden by non-noreturn functions. 264 bool isVirtualMethod = false; 265 if (const CXXMethodDecl *Method = dyn_cast<CXXMethodDecl>(Func)) 266 isVirtualMethod = Method->isVirtual(); 267 268 if (!isVirtualMethod) 269 D.diag_NeverFallThroughOrReturn = 270 diag::warn_suggest_noreturn_function; 271 else 272 D.diag_NeverFallThroughOrReturn = 0; 273 274 D.funMode = true; 275 return D; 276 } 277 278 static CheckFallThroughDiagnostics MakeForBlock() { 279 CheckFallThroughDiagnostics D; 280 D.diag_MaybeFallThrough_HasNoReturn = 281 diag::err_noreturn_block_has_return_expr; 282 D.diag_MaybeFallThrough_ReturnsNonVoid = 283 diag::err_maybe_falloff_nonvoid_block; 284 D.diag_AlwaysFallThrough_HasNoReturn = 285 diag::err_noreturn_block_has_return_expr; 286 D.diag_AlwaysFallThrough_ReturnsNonVoid = 287 diag::err_falloff_nonvoid_block; 288 D.diag_NeverFallThroughOrReturn = 289 diag::warn_suggest_noreturn_block; 290 D.funMode = false; 291 return D; 292 } 293 294 bool checkDiagnostics(Diagnostic &D, bool ReturnsVoid, 295 bool HasNoReturn) const { 296 if (funMode) { 297 return (ReturnsVoid || 298 D.getDiagnosticLevel(diag::warn_maybe_falloff_nonvoid_function, 299 FuncLoc) == Diagnostic::Ignored) 300 && (!HasNoReturn || 301 D.getDiagnosticLevel(diag::warn_noreturn_function_has_return_expr, 302 FuncLoc) == Diagnostic::Ignored) 303 && (!ReturnsVoid || 304 D.getDiagnosticLevel(diag::warn_suggest_noreturn_block, FuncLoc) 305 == Diagnostic::Ignored); 306 } 307 308 // For blocks. 309 return ReturnsVoid && !HasNoReturn 310 && (!ReturnsVoid || 311 D.getDiagnosticLevel(diag::warn_suggest_noreturn_block, FuncLoc) 312 == Diagnostic::Ignored); 313 } 314}; 315 316} 317 318/// CheckFallThroughForFunctionDef - Check that we don't fall off the end of a 319/// function that should return a value. Check that we don't fall off the end 320/// of a noreturn function. We assume that functions and blocks not marked 321/// noreturn will return. 322static void CheckFallThroughForBody(Sema &S, const Decl *D, const Stmt *Body, 323 const BlockExpr *blkExpr, 324 const CheckFallThroughDiagnostics& CD, 325 AnalysisContext &AC) { 326 327 bool ReturnsVoid = false; 328 bool HasNoReturn = false; 329 330 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 331 ReturnsVoid = FD->getResultType()->isVoidType(); 332 HasNoReturn = FD->hasAttr<NoReturnAttr>() || 333 FD->getType()->getAs<FunctionType>()->getNoReturnAttr(); 334 } 335 else if (const ObjCMethodDecl *MD = dyn_cast<ObjCMethodDecl>(D)) { 336 ReturnsVoid = MD->getResultType()->isVoidType(); 337 HasNoReturn = MD->hasAttr<NoReturnAttr>(); 338 } 339 else if (isa<BlockDecl>(D)) { 340 QualType BlockTy = blkExpr->getType(); 341 if (const FunctionType *FT = 342 BlockTy->getPointeeType()->getAs<FunctionType>()) { 343 if (FT->getResultType()->isVoidType()) 344 ReturnsVoid = true; 345 if (FT->getNoReturnAttr()) 346 HasNoReturn = true; 347 } 348 } 349 350 Diagnostic &Diags = S.getDiagnostics(); 351 352 // Short circuit for compilation speed. 353 if (CD.checkDiagnostics(Diags, ReturnsVoid, HasNoReturn)) 354 return; 355 356 // FIXME: Function try block 357 if (const CompoundStmt *Compound = dyn_cast<CompoundStmt>(Body)) { 358 switch (CheckFallThrough(AC)) { 359 case UnknownFallThrough: 360 break; 361 362 case MaybeFallThrough: 363 if (HasNoReturn) 364 S.Diag(Compound->getRBracLoc(), 365 CD.diag_MaybeFallThrough_HasNoReturn); 366 else if (!ReturnsVoid) 367 S.Diag(Compound->getRBracLoc(), 368 CD.diag_MaybeFallThrough_ReturnsNonVoid); 369 break; 370 case AlwaysFallThrough: 371 if (HasNoReturn) 372 S.Diag(Compound->getRBracLoc(), 373 CD.diag_AlwaysFallThrough_HasNoReturn); 374 else if (!ReturnsVoid) 375 S.Diag(Compound->getRBracLoc(), 376 CD.diag_AlwaysFallThrough_ReturnsNonVoid); 377 break; 378 case NeverFallThroughOrReturn: 379 if (ReturnsVoid && !HasNoReturn && CD.diag_NeverFallThroughOrReturn) { 380 if (const FunctionDecl *FD = dyn_cast<FunctionDecl>(D)) { 381 S.Diag(Compound->getLBracLoc(), CD.diag_NeverFallThroughOrReturn) 382 << FD; 383 } else { 384 S.Diag(Compound->getLBracLoc(), CD.diag_NeverFallThroughOrReturn); 385 } 386 } 387 break; 388 case NeverFallThrough: 389 break; 390 } 391 } 392} 393 394//===----------------------------------------------------------------------===// 395// -Wuninitialized 396//===----------------------------------------------------------------------===// 397 398namespace { 399/// ContainsReference - A visitor class to search for references to 400/// a particular declaration (the needle) within any evaluated component of an 401/// expression (recursively). 402class ContainsReference : public EvaluatedExprVisitor<ContainsReference> { 403 bool FoundReference; 404 const DeclRefExpr *Needle; 405 406public: 407 ContainsReference(ASTContext &Context, const DeclRefExpr *Needle) 408 : EvaluatedExprVisitor<ContainsReference>(Context), 409 FoundReference(false), Needle(Needle) {} 410 411 void VisitExpr(Expr *E) { 412 // Stop evaluating if we already have a reference. 413 if (FoundReference) 414 return; 415 416 EvaluatedExprVisitor<ContainsReference>::VisitExpr(E); 417 } 418 419 void VisitDeclRefExpr(DeclRefExpr *E) { 420 if (E == Needle) 421 FoundReference = true; 422 else 423 EvaluatedExprVisitor<ContainsReference>::VisitDeclRefExpr(E); 424 } 425 426 bool doesContainReference() const { return FoundReference; } 427}; 428} 429 430/// DiagnoseUninitializedUse -- Helper function for diagnosing uses of an 431/// uninitialized variable. This manages the different forms of diagnostic 432/// emitted for particular types of uses. Returns true if the use was diagnosed 433/// as a warning. If a pariticular use is one we omit warnings for, returns 434/// false. 435static bool DiagnoseUninitializedUse(Sema &S, const VarDecl *VD, 436 const Expr *E, bool isAlwaysUninit) { 437 bool isSelfInit = false; 438 439 if (const DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(E)) { 440 if (isAlwaysUninit) { 441 // Inspect the initializer of the variable declaration which is 442 // being referenced prior to its initialization. We emit 443 // specialized diagnostics for self-initialization, and we 444 // specifically avoid warning about self references which take the 445 // form of: 446 // 447 // int x = x; 448 // 449 // This is used to indicate to GCC that 'x' is intentionally left 450 // uninitialized. Proven code paths which access 'x' in 451 // an uninitialized state after this will still warn. 452 // 453 // TODO: Should we suppress maybe-uninitialized warnings for 454 // variables initialized in this way? 455 if (const Expr *Initializer = VD->getInit()) { 456 if (DRE == Initializer->IgnoreParenImpCasts()) 457 return false; 458 459 ContainsReference CR(S.Context, DRE); 460 CR.Visit(const_cast<Expr*>(Initializer)); 461 isSelfInit = CR.doesContainReference(); 462 } 463 if (isSelfInit) { 464 S.Diag(DRE->getLocStart(), 465 diag::warn_uninit_self_reference_in_init) 466 << VD->getDeclName() << VD->getLocation() << DRE->getSourceRange(); 467 } else { 468 S.Diag(DRE->getLocStart(), diag::warn_uninit_var) 469 << VD->getDeclName() << DRE->getSourceRange(); 470 } 471 } else { 472 S.Diag(DRE->getLocStart(), diag::warn_maybe_uninit_var) 473 << VD->getDeclName() << DRE->getSourceRange(); 474 } 475 } else { 476 const BlockExpr *BE = cast<BlockExpr>(E); 477 S.Diag(BE->getLocStart(), 478 isAlwaysUninit ? diag::warn_uninit_var_captured_by_block 479 : diag::warn_maybe_uninit_var_captured_by_block) 480 << VD->getDeclName(); 481 } 482 483 // Report where the variable was declared when the use wasn't within 484 // the initializer of that declaration. 485 if (!isSelfInit) 486 S.Diag(VD->getLocStart(), diag::note_uninit_var_def) 487 << VD->getDeclName(); 488 489 return true; 490} 491 492static void SuggestInitializationFixit(Sema &S, const VarDecl *VD) { 493 // Don't issue a fixit if there is already an initializer. 494 if (VD->getInit()) 495 return; 496 497 // Suggest possible initialization (if any). 498 const char *initialization = 0; 499 QualType VariableTy = VD->getType().getCanonicalType(); 500 501 if (VariableTy->isObjCObjectPointerType() || 502 VariableTy->isBlockPointerType()) { 503 // Check if 'nil' is defined. 504 if (S.PP.getMacroInfo(&S.getASTContext().Idents.get("nil"))) 505 initialization = " = nil"; 506 else 507 initialization = " = 0"; 508 } 509 else if (VariableTy->isRealFloatingType()) 510 initialization = " = 0.0"; 511 else if (VariableTy->isBooleanType() && S.Context.getLangOptions().CPlusPlus) 512 initialization = " = false"; 513 else if (VariableTy->isEnumeralType()) 514 return; 515 else if (VariableTy->isPointerType() || VariableTy->isMemberPointerType()) { 516 if (S.Context.getLangOptions().CPlusPlus0x) 517 initialization = " = nullptr"; 518 // Check if 'NULL' is defined. 519 else if (S.PP.getMacroInfo(&S.getASTContext().Idents.get("NULL"))) 520 initialization = " = NULL"; 521 else 522 initialization = " = 0"; 523 } 524 else if (VariableTy->isScalarType()) 525 initialization = " = 0"; 526 527 if (initialization) { 528 SourceLocation loc = S.PP.getLocForEndOfToken(VD->getLocEnd()); 529 S.Diag(loc, diag::note_var_fixit_add_initialization) 530 << FixItHint::CreateInsertion(loc, initialization); 531 } 532} 533 534typedef std::pair<const Expr*, bool> UninitUse; 535 536namespace { 537struct SLocSort { 538 bool operator()(const UninitUse &a, const UninitUse &b) { 539 SourceLocation aLoc = a.first->getLocStart(); 540 SourceLocation bLoc = b.first->getLocStart(); 541 return aLoc.getRawEncoding() < bLoc.getRawEncoding(); 542 } 543}; 544 545class UninitValsDiagReporter : public UninitVariablesHandler { 546 Sema &S; 547 typedef SmallVector<UninitUse, 2> UsesVec; 548 typedef llvm::DenseMap<const VarDecl *, UsesVec*> UsesMap; 549 UsesMap *uses; 550 551public: 552 UninitValsDiagReporter(Sema &S) : S(S), uses(0) {} 553 ~UninitValsDiagReporter() { 554 flushDiagnostics(); 555 } 556 557 void handleUseOfUninitVariable(const Expr *ex, const VarDecl *vd, 558 bool isAlwaysUninit) { 559 if (!uses) 560 uses = new UsesMap(); 561 562 UsesVec *&vec = (*uses)[vd]; 563 if (!vec) 564 vec = new UsesVec(); 565 566 vec->push_back(std::make_pair(ex, isAlwaysUninit)); 567 } 568 569 void flushDiagnostics() { 570 if (!uses) 571 return; 572 573 for (UsesMap::iterator i = uses->begin(), e = uses->end(); i != e; ++i) { 574 const VarDecl *vd = i->first; 575 UsesVec *vec = i->second; 576 577 // Sort the uses by their SourceLocations. While not strictly 578 // guaranteed to produce them in line/column order, this will provide 579 // a stable ordering. 580 std::sort(vec->begin(), vec->end(), SLocSort()); 581 582 for (UsesVec::iterator vi = vec->begin(), ve = vec->end(); vi != ve; 583 ++vi) { 584 if (!DiagnoseUninitializedUse(S, vd, vi->first, 585 /*isAlwaysUninit=*/vi->second)) 586 continue; 587 588 SuggestInitializationFixit(S, vd); 589 590 // Skip further diagnostics for this variable. We try to warn only on 591 // the first point at which a variable is used uninitialized. 592 break; 593 } 594 595 delete vec; 596 } 597 delete uses; 598 } 599}; 600} 601 602 603//===----------------------------------------------------------------------===// 604// -Wthread-safety 605//===----------------------------------------------------------------------===// 606 607namespace { 608/// \brief Implements a set of CFGBlocks using a BitVector. 609/// 610/// This class contains a minimal interface, primarily dictated by the SetType 611/// template parameter of the llvm::po_iterator template, as used with external 612/// storage. We also use this set to keep track of which CFGBlocks we visit 613/// during the analysis. 614class CFGBlockSet { 615 llvm::BitVector VisitedBlockIDs; 616 617public: 618 // po_iterator requires this iterator, but the only interface needed is the 619 // value_type typedef. 620 struct iterator { 621 typedef const CFGBlock *value_type; 622 }; 623 624 CFGBlockSet() {} 625 CFGBlockSet(const CFG *G) : VisitedBlockIDs(G->getNumBlockIDs(), false) {} 626 627 /// \brief Set the bit associated with a particular CFGBlock. 628 /// This is the important method for the SetType template parameter. 629 bool insert(const CFGBlock *Block) { 630 // Note that insert() is called by po_iterator, which doesn't check to make 631 // sure that Block is non-null. Moreover, the CFGBlock iterator will 632 // occasionally hand out null pointers for pruned edges, so we catch those 633 // here. 634 if (Block == 0) 635 return false; // if an edge is trivially false. 636 if (VisitedBlockIDs.test(Block->getBlockID())) 637 return false; 638 VisitedBlockIDs.set(Block->getBlockID()); 639 return true; 640 } 641 642 /// \brief Check if the bit for a CFGBlock has been already set. 643 /// This method is for tracking visited blocks in the main threadsafety loop. 644 /// Block must not be null. 645 bool alreadySet(const CFGBlock *Block) { 646 return VisitedBlockIDs.test(Block->getBlockID()); 647 } 648}; 649 650/// \brief We create a helper class which we use to iterate through CFGBlocks in 651/// the topological order. 652class TopologicallySortedCFG { 653 typedef llvm::po_iterator<const CFG*, CFGBlockSet, true> po_iterator; 654 655 std::vector<const CFGBlock*> Blocks; 656 657public: 658 typedef std::vector<const CFGBlock*>::reverse_iterator iterator; 659 660 TopologicallySortedCFG(const CFG *CFGraph) { 661 Blocks.reserve(CFGraph->getNumBlockIDs()); 662 CFGBlockSet BSet(CFGraph); 663 664 for (po_iterator I = po_iterator::begin(CFGraph, BSet), 665 E = po_iterator::end(CFGraph, BSet); I != E; ++I) { 666 Blocks.push_back(*I); 667 } 668 } 669 670 iterator begin() { 671 return Blocks.rbegin(); 672 } 673 674 iterator end() { 675 return Blocks.rend(); 676 } 677}; 678 679/// \brief A LockID object uniquely identifies a particular lock acquired, and 680/// is built from an Expr* (i.e. calling a lock function). 681/// 682/// Thread-safety analysis works by comparing lock expressions. Within the 683/// body of a function, an expression such as "x->foo->bar.mu" will resolve to 684/// a particular lock object at run-time. Subsequent occurrences of the same 685/// expression (where "same" means syntactic equality) will refer to the same 686/// run-time object if three conditions hold: 687/// (1) Local variables in the expression, such as "x" have not changed. 688/// (2) Values on the heap that affect the expression have not changed. 689/// (3) The expression involves only pure function calls. 690/// The current implementation assumes, but does not verify, that multiple uses 691/// of the same lock expression satisfies these criteria. 692/// 693/// Clang introduces an additional wrinkle, which is that it is difficult to 694/// derive canonical expressions, or compare expressions directly for equality. 695/// Thus, we identify a lock not by an Expr, but by the set of named 696/// declarations that are referenced by the Expr. In other words, 697/// x->foo->bar.mu will be a four element vector with the Decls for 698/// mu, bar, and foo, and x. The vector will uniquely identify the expression 699/// for all practical purposes. 700/// 701/// Note we will need to perform substitution on "this" and function parameter 702/// names when constructing a lock expression. 703/// 704/// For example: 705/// class C { Mutex Mu; void lock() EXCLUSIVE_LOCK_FUNCTION(this->Mu); }; 706/// void myFunc(C *X) { ... X->lock() ... } 707/// The original expression for the lock acquired by myFunc is "this->Mu", but 708/// "X" is substituted for "this" so we get X->Mu(); 709/// 710/// For another example: 711/// foo(MyList *L) EXCLUSIVE_LOCKS_REQUIRED(L->Mu) { ... } 712/// MyList *MyL; 713/// foo(MyL); // requires lock MyL->Mu to be held 714/// 715/// FIXME: In C++0x Mutexes are the objects that control access to shared 716/// variables, while Locks are the objects that acquire and release Mutexes. We 717/// may want to switch to this new terminology soon, in which case we should 718/// rename this class "Mutex" and rename "LockId" to "MutexId", as well as 719/// making sure that the terms Lock and Mutex throughout this code are 720/// consistent with C++0x 721/// 722/// FIXME: We should also pick one and canonicalize all usage of lock vs acquire 723/// and unlock vs release as verbs. 724class LockID { 725 SmallVector<NamedDecl*, 2> DeclSeq; 726 727 /// Build a Decl sequence representing the lock from the given expression. 728 /// Recursive function that bottoms out when the final DeclRefExpr is reached. 729 void buildLock(Expr *Exp) { 730 if (DeclRefExpr *DRE = dyn_cast<DeclRefExpr>(Exp)) { 731 NamedDecl *ND = cast<NamedDecl>(DRE->getDecl()->getCanonicalDecl()); 732 DeclSeq.push_back(ND); 733 } else if (MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) { 734 NamedDecl *ND = ME->getMemberDecl(); 735 DeclSeq.push_back(ND); 736 buildLock(ME->getBase()); 737 } else { 738 // FIXME: add diagnostic 739 llvm::report_fatal_error("Expected lock expression!"); 740 } 741 } 742 743public: 744 LockID(Expr *LExpr) { 745 buildLock(LExpr); 746 assert(!DeclSeq.empty()); 747 } 748 749 bool operator==(const LockID &other) const { 750 return DeclSeq == other.DeclSeq; 751 } 752 753 bool operator!=(const LockID &other) const { 754 return !(*this == other); 755 } 756 757 // SmallVector overloads Operator< to do lexicographic ordering. Note that 758 // we use pointer equality (and <) to compare NamedDecls. This means the order 759 // of LockIDs in a lockset is nondeterministic. In order to output 760 // diagnostics in a deterministic ordering, we must order all diagnostics to 761 // output by SourceLocation when iterating through this lockset. 762 bool operator<(const LockID &other) const { 763 return DeclSeq < other.DeclSeq; 764 } 765 766 /// \brief Returns the name of the first Decl in the list for a given LockID; 767 /// e.g. the lock expression foo.bar() has name "bar". 768 /// The caret will point unambiguously to the lock expression, so using this 769 /// name in diagnostics is a way to get simple, and consistent, lock names. 770 /// We do not want to output the entire expression text for security reasons. 771 StringRef getName() const { 772 return DeclSeq.front()->getName(); 773 } 774 775 void Profile(llvm::FoldingSetNodeID &ID) const { 776 for (SmallVectorImpl<NamedDecl*>::const_iterator I = DeclSeq.begin(), 777 E = DeclSeq.end(); I != E; ++I) { 778 ID.AddPointer(*I); 779 } 780 } 781}; 782 783/// \brief This is a helper class that stores info about the most recent 784/// accquire of a Lock. 785/// 786/// The main body of the analysis maps LockIDs to LockDatas. 787struct LockData { 788 SourceLocation AcquireLoc; 789 790 LockData(SourceLocation Loc) : AcquireLoc(Loc) {} 791 792 bool operator==(const LockData &other) const { 793 return AcquireLoc == other.AcquireLoc; 794 } 795 796 bool operator!=(const LockData &other) const { 797 return !(*this == other); 798 } 799 800 void Profile(llvm::FoldingSetNodeID &ID) const { 801 ID.AddInteger(AcquireLoc.getRawEncoding()); 802 } 803}; 804 805/// A Lockset maps each LockID (defined above) to information about how it has 806/// been locked. 807typedef llvm::ImmutableMap<LockID, LockData> Lockset; 808 809/// \brief We use this class to visit different types of expressions in 810/// CFGBlocks, and build up the lockset. 811/// An expression may cause us to add or remove locks from the lockset, or else 812/// output error messages related to missing locks. 813/// FIXME: In future, we may be able to not inherit from a visitor. 814class BuildLockset : public StmtVisitor<BuildLockset> { 815 Sema &S; 816 Lockset LSet; 817 Lockset::Factory &LocksetFactory; 818 819 // Helper functions 820 void removeLock(SourceLocation UnlockLoc, Expr *LockExp); 821 void addLock(SourceLocation LockLoc, Expr *LockExp); 822 const ValueDecl *getValueDecl(Expr *Exp); 823 void checkAccess(Expr *Exp); 824 void checkDereference(Expr *Exp); 825 826public: 827 BuildLockset(Sema &S, Lockset LS, Lockset::Factory &F) 828 : StmtVisitor<BuildLockset>(), S(S), LSet(LS), 829 LocksetFactory(F) {} 830 831 Lockset getLockset() { 832 return LSet; 833 } 834 835 void VisitUnaryOperator(UnaryOperator *UO); 836 void VisitBinaryOperator(BinaryOperator *BO); 837 void VisitCastExpr(CastExpr *CE); 838 void VisitCXXMemberCallExpr(CXXMemberCallExpr *Exp); 839}; 840 841/// \brief Add a new lock to the lockset, warning if the lock is already there. 842/// \param LockLoc The source location of the acquire 843/// \param LockExp The lock expression corresponding to the lock to be added 844void BuildLockset::addLock(SourceLocation LockLoc, Expr *LockExp) { 845 LockID Lock(LockExp); 846 LockData NewLockData(LockLoc); 847 848 if (LSet.contains(Lock)) 849 S.Diag(LockLoc, diag::warn_double_lock) << Lock.getName(); 850 851 LSet = LocksetFactory.add(LSet, Lock, NewLockData); 852} 853 854/// \brief Remove a lock from the lockset, warning if the lock is not there. 855/// \param LockExp The lock expression corresponding to the lock to be removed 856/// \param UnlockLoc The source location of the unlock (only used in error msg) 857void BuildLockset::removeLock(SourceLocation UnlockLoc, Expr *LockExp) { 858 LockID Lock(LockExp); 859 860 Lockset NewLSet = LocksetFactory.remove(LSet, Lock); 861 if(NewLSet == LSet) 862 S.Diag(UnlockLoc, diag::warn_unlock_but_no_acquire) << Lock.getName(); 863 864 LSet = NewLSet; 865} 866 867/// \brief Gets the value decl pointer from DeclRefExprs or MemberExprs 868const ValueDecl *BuildLockset::getValueDecl(Expr *Exp) { 869 if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Exp)) 870 return DR->getDecl(); 871 872 if (const MemberExpr *ME = dyn_cast<MemberExpr>(Exp)) 873 return ME->getMemberDecl(); 874 875 return 0; 876} 877 878/// \brief This method identifies variable dereferences and checks pt_guarded_by 879/// and pt_guarded_var annotations. Note that we only check these annotations 880/// at the time a pointer is dereferenced. 881/// FIXME: We need to check for other types of pointer dereferences 882/// (e.g. [], ->) and deal with them here. 883/// \param Exp An expression that has been read or written. 884void BuildLockset::checkDereference(Expr *Exp) { 885 UnaryOperator *UO = dyn_cast<UnaryOperator>(Exp); 886 if (!UO || UO->getOpcode() != clang::UO_Deref) 887 return; 888 Exp = UO->getSubExpr()->IgnoreParenCasts(); 889 890 const ValueDecl *D = getValueDecl(Exp); 891 if(!D || !D->hasAttrs()) 892 return; 893 894 if (D->getAttr<PtGuardedVarAttr>() && LSet.isEmpty()) 895 S.Diag(Exp->getExprLoc(), diag::warn_var_deref_requires_any_lock) 896 << D->getName(); 897 898 const AttrVec &ArgAttrs = D->getAttrs(); 899 for(unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i) { 900 if (ArgAttrs[i]->getKind() != attr::PtGuardedBy) 901 continue; 902 PtGuardedByAttr *PGBAttr = cast<PtGuardedByAttr>(ArgAttrs[i]); 903 LockID Lock(PGBAttr->getArg()); 904 if (!LSet.contains(Lock)) 905 S.Diag(Exp->getExprLoc(), diag::warn_var_deref_requires_lock) 906 << D->getName() << Lock.getName(); 907 } 908} 909 910/// \brief Checks guarded_by and guarded_var attributes. 911/// Whenever we identify an access (read or write) of a DeclRefExpr or 912/// MemberExpr, we need to check whether there are any guarded_by or 913/// guarded_var attributes, and make sure we hold the appropriate locks. 914void BuildLockset::checkAccess(Expr *Exp) { 915 const ValueDecl *D = getValueDecl(Exp); 916 if(!D || !D->hasAttrs()) 917 return; 918 919 if (D->getAttr<GuardedVarAttr>() && LSet.isEmpty()) 920 S.Diag(Exp->getExprLoc(), diag::warn_variable_requires_any_lock) 921 << D->getName(); 922 923 const AttrVec &ArgAttrs = D->getAttrs(); 924 for(unsigned i = 0, Size = ArgAttrs.size(); i < Size; ++i) { 925 if (ArgAttrs[i]->getKind() != attr::GuardedBy) 926 continue; 927 GuardedByAttr *GBAttr = cast<GuardedByAttr>(ArgAttrs[i]); 928 LockID Lock(GBAttr->getArg()); 929 if (!LSet.contains(Lock)) 930 S.Diag(Exp->getExprLoc(), diag::warn_variable_requires_lock) 931 << D->getName() << Lock.getName(); 932 } 933} 934 935/// \brief For unary operations which read and write a variable, we need to 936/// check whether we hold any required locks. Reads are checked in 937/// VisitCastExpr. 938void BuildLockset::VisitUnaryOperator(UnaryOperator *UO) { 939 switch (UO->getOpcode()) { 940 case clang::UO_PostDec: 941 case clang::UO_PostInc: 942 case clang::UO_PreDec: 943 case clang::UO_PreInc: { 944 Expr *SubExp = UO->getSubExpr()->IgnoreParenCasts(); 945 checkAccess(SubExp); 946 checkDereference(SubExp); 947 break; 948 } 949 default: 950 break; 951 } 952} 953 954/// For binary operations which assign to a variable (writes), we need to check 955/// whether we hold any required locks. 956/// FIXME: Deal with non-primitive types. 957void BuildLockset::VisitBinaryOperator(BinaryOperator *BO) { 958 if (!BO->isAssignmentOp()) 959 return; 960 Expr *LHSExp = BO->getLHS()->IgnoreParenCasts(); 961 checkAccess(LHSExp); 962 checkDereference(LHSExp); 963} 964 965/// Whenever we do an LValue to Rvalue cast, we are reading a variable and 966/// need to ensure we hold any required locks. 967/// FIXME: Deal with non-primitive types. 968void BuildLockset::VisitCastExpr(CastExpr *CE) { 969 if (CE->getCastKind() != CK_LValueToRValue) 970 return; 971 Expr *SubExp = CE->getSubExpr()->IgnoreParenCasts(); 972 checkAccess(SubExp); 973 checkDereference(SubExp); 974} 975 976 977/// \brief When visiting CXXMemberCallExprs we need to examine the attributes on 978/// the method that is being called and add, remove or check locks in the 979/// lockset accordingly. 980/// 981/// FIXME: For classes annotated with one of the guarded annotations, we need 982/// to treat const method calls as reads and non-const method calls as writes, 983/// and check that the appropriate locks are held. Non-const method calls with 984/// the same signature as const method calls can be also treated as reads. 985void BuildLockset::VisitCXXMemberCallExpr(CXXMemberCallExpr *Exp) { 986 NamedDecl *D = dyn_cast_or_null<NamedDecl>(Exp->getCalleeDecl()); 987 988 SourceLocation ExpLocation = Exp->getExprLoc(); 989 Expr *Parent = Exp->getImplicitObjectArgument(); 990 991 if(!D || !D->hasAttrs()) 992 return; 993 994 AttrVec &ArgAttrs = D->getAttrs(); 995 for(unsigned i = 0; i < ArgAttrs.size(); ++i) { 996 Attr *Attr = ArgAttrs[i]; 997 switch (Attr->getKind()) { 998 // When we encounter an exclusive lock function, we need to add the lock 999 // to our lockset. 1000 case attr::ExclusiveLockFunction: { 1001 ExclusiveLockFunctionAttr *ELFAttr = 1002 cast<ExclusiveLockFunctionAttr>(Attr); 1003 1004 if (ELFAttr->args_size() == 0) {// The lock held is the "this" object. 1005 addLock(ExpLocation, Parent); 1006 break; 1007 } 1008 1009 for (ExclusiveLockFunctionAttr::args_iterator I = ELFAttr->args_begin(), 1010 E = ELFAttr->args_end(); I != E; ++I) 1011 addLock(ExpLocation, *I); 1012 // FIXME: acquired_after/acquired_before annotations 1013 break; 1014 } 1015 1016 // When we encounter an unlock function, we need to remove unlocked locks 1017 // from the lockset, and flag a warning if they are not there. 1018 case attr::UnlockFunction: { 1019 UnlockFunctionAttr *UFAttr = cast<UnlockFunctionAttr>(Attr); 1020 1021 if (UFAttr->args_size() == 0) { // The lock held is the "this" object. 1022 removeLock(ExpLocation, Parent); 1023 break; 1024 } 1025 1026 for (UnlockFunctionAttr::args_iterator I = UFAttr->args_begin(), 1027 E = UFAttr->args_end(); I != E; ++I) 1028 removeLock(ExpLocation, *I); 1029 break; 1030 } 1031 1032 // Ignore other (non thread-safety) attributes 1033 default: 1034 break; 1035 } 1036 } 1037} 1038 1039typedef std::pair<SourceLocation, PartialDiagnostic> DelayedDiag; 1040typedef llvm::SmallVector<DelayedDiag, 4> DiagList; 1041 1042struct SortDiagBySourceLocation { 1043 Sema &S; 1044 1045 SortDiagBySourceLocation(Sema &S) : S(S) {} 1046 1047 bool operator()(const DelayedDiag &left, const DelayedDiag &right) { 1048 // Although this call will be slow, this is only called when outputting 1049 // multiple warnings. 1050 return S.getSourceManager().isBeforeInTranslationUnit(left.first, 1051 right.first); 1052 } 1053}; 1054} // end anonymous namespace 1055 1056/// \brief Emit all buffered diagnostics in order of sourcelocation. 1057/// We need to output diagnostics produced while iterating through 1058/// the lockset in deterministic order, so this function orders diagnostics 1059/// and outputs them. 1060static void EmitDiagnostics(Sema &S, DiagList &D) { 1061 SortDiagBySourceLocation SortDiagBySL(S); 1062 sort(D.begin(), D.end(), SortDiagBySL); 1063 for (DiagList::iterator I = D.begin(), E = D.end(); I != E; ++I) 1064 S.Diag(I->first, I->second); 1065} 1066 1067/// \brief Compute the intersection of two locksets and issue warnings for any 1068/// locks in the symmetric difference. 1069/// 1070/// This function is used at a merge point in the CFG when comparing the lockset 1071/// of each branch being merged. For example, given the following sequence: 1072/// A; if () then B; else C; D; we need to check that the lockset after B and C 1073/// are the same. In the event of a difference, we use the intersection of these 1074/// two locksets at the start of D. 1075static Lockset intersectAndWarn(Sema &S, Lockset LSet1, Lockset LSet2, 1076 Lockset::Factory &Fact) { 1077 Lockset Intersection = LSet1; 1078 DiagList Warnings; 1079 1080 for (Lockset::iterator I = LSet2.begin(), E = LSet2.end(); I != E; ++I) { 1081 if (!LSet1.contains(I.getKey())) { 1082 const LockID &MissingLock = I.getKey(); 1083 const LockData &MissingLockData = I.getData(); 1084 PartialDiagnostic Warning = 1085 S.PDiag(diag::warn_lock_not_released_in_scope) << MissingLock.getName(); 1086 Warnings.push_back(DelayedDiag(MissingLockData.AcquireLoc, Warning)); 1087 } 1088 } 1089 1090 for (Lockset::iterator I = LSet1.begin(), E = LSet1.end(); I != E; ++I) { 1091 if (!LSet2.contains(I.getKey())) { 1092 const LockID &MissingLock = I.getKey(); 1093 const LockData &MissingLockData = I.getData(); 1094 PartialDiagnostic Warning = 1095 S.PDiag(diag::warn_lock_not_released_in_scope) << MissingLock.getName(); 1096 Warnings.push_back(DelayedDiag(MissingLockData.AcquireLoc, Warning)); 1097 Intersection = Fact.remove(Intersection, MissingLock); 1098 } 1099 } 1100 1101 EmitDiagnostics(S, Warnings); 1102 return Intersection; 1103} 1104 1105/// \brief Returns the location of the first Stmt in a Block. 1106static SourceLocation getFirstStmtLocation(CFGBlock *Block) { 1107 SourceLocation Loc; 1108 for (CFGBlock::const_iterator BI = Block->begin(), BE = Block->end(); 1109 BI != BE; ++BI) { 1110 if (const CFGStmt *CfgStmt = dyn_cast<CFGStmt>(&(*BI))) { 1111 Loc = CfgStmt->getStmt()->getLocStart(); 1112 if (Loc.isValid()) return Loc; 1113 } 1114 } 1115 if (Stmt *S = Block->getTerminator().getStmt()) { 1116 Loc = S->getLocStart(); 1117 if (Loc.isValid()) return Loc; 1118 } 1119 return Loc; 1120} 1121 1122/// \brief Warn about different locksets along backedges of loops. 1123/// This function is called when we encounter a back edge. At that point, 1124/// we need to verify that the lockset before taking the backedge is the 1125/// same as the lockset before entering the loop. 1126/// 1127/// \param LoopEntrySet Locks held before starting the loop 1128/// \param LoopReentrySet Locks held in the last CFG block of the loop 1129static void warnBackEdgeUnequalLocksets(Sema &S, const Lockset LoopReentrySet, 1130 const Lockset LoopEntrySet, 1131 SourceLocation FirstLocInLoop) { 1132 assert(FirstLocInLoop.isValid()); 1133 DiagList Warnings; 1134 1135 // Warn for locks held at the start of the loop, but not the end. 1136 for (Lockset::iterator I = LoopEntrySet.begin(), E = LoopEntrySet.end(); 1137 I != E; ++I) { 1138 if (!LoopReentrySet.contains(I.getKey())) { 1139 const LockID &MissingLock = I.getKey(); 1140 // We report this error at the location of the first statement in a loop 1141 PartialDiagnostic Warning = 1142 S.PDiag(diag::warn_expecting_lock_held_on_loop) 1143 << MissingLock.getName(); 1144 Warnings.push_back(DelayedDiag(FirstLocInLoop, Warning)); 1145 } 1146 } 1147 1148 // Warn for locks held at the end of the loop, but not at the start. 1149 for (Lockset::iterator I = LoopReentrySet.begin(), E = LoopReentrySet.end(); 1150 I != E; ++I) { 1151 if (!LoopEntrySet.contains(I.getKey())) { 1152 const LockID &MissingLock = I.getKey(); 1153 const LockData &MissingLockData = I.getData(); 1154 PartialDiagnostic Warning = 1155 S.PDiag(diag::warn_lock_not_released_in_scope) << MissingLock.getName(); 1156 Warnings.push_back(DelayedDiag(MissingLockData.AcquireLoc, Warning)); 1157 } 1158 } 1159 1160 EmitDiagnostics(S, Warnings); 1161} 1162 1163/// \brief Check a function's CFG for thread-safety violations. 1164/// 1165/// We traverse the blocks in the CFG, compute the set of locks that are held 1166/// at the end of each block, and issue warnings for thread safety violations. 1167/// Each block in the CFG is traversed exactly once. 1168static void checkThreadSafety(Sema &S, AnalysisContext &AC) { 1169 CFG *CFGraph = AC.getCFG(); 1170 if (!CFGraph) return; 1171 1172 Lockset::Factory LocksetFactory; 1173 1174 // FIXME: Swith to SmallVector? Otherwise improve performance impact? 1175 std::vector<Lockset> EntryLocksets(CFGraph->getNumBlockIDs(), 1176 LocksetFactory.getEmptyMap()); 1177 std::vector<Lockset> ExitLocksets(CFGraph->getNumBlockIDs(), 1178 LocksetFactory.getEmptyMap()); 1179 1180 // We need to explore the CFG via a "topological" ordering. 1181 // That way, we will be guaranteed to have information about required 1182 // predecessor locksets when exploring a new block. 1183 TopologicallySortedCFG SortedGraph(CFGraph); 1184 CFGBlockSet VisitedBlocks(CFGraph); 1185 1186 for (TopologicallySortedCFG::iterator I = SortedGraph.begin(), 1187 E = SortedGraph.end(); I!= E; ++I) { 1188 const CFGBlock *CurrBlock = *I; 1189 int CurrBlockID = CurrBlock->getBlockID(); 1190 1191 VisitedBlocks.insert(CurrBlock); 1192 1193 // Use the default initial lockset in case there are no predecessors. 1194 Lockset &Entryset = EntryLocksets[CurrBlockID]; 1195 Lockset &Exitset = ExitLocksets[CurrBlockID]; 1196 1197 // Iterate through the predecessor blocks and warn if the lockset for all 1198 // predecessors is not the same. We take the entry lockset of the current 1199 // block to be the intersection of all previous locksets. 1200 // FIXME: By keeping the intersection, we may output more errors in future 1201 // for a lock which is not in the intersection, but was in the union. We 1202 // may want to also keep the union in future. As an example, let's say 1203 // the intersection contains Lock L, and the union contains L and M. 1204 // Later we unlock M. At this point, we would output an error because we 1205 // never locked M; although the real error is probably that we forgot to 1206 // lock M on all code paths. Conversely, let's say that later we lock M. 1207 // In this case, we should compare against the intersection instead of the 1208 // union because the real error is probably that we forgot to unlock M on 1209 // all code paths. 1210 bool LocksetInitialized = false; 1211 for (CFGBlock::const_pred_iterator PI = CurrBlock->pred_begin(), 1212 PE = CurrBlock->pred_end(); PI != PE; ++PI) { 1213 1214 // if *PI -> CurrBlock is a back edge 1215 if (*PI == 0 || !VisitedBlocks.alreadySet(*PI)) 1216 continue; 1217 1218 int PrevBlockID = (*PI)->getBlockID(); 1219 if (!LocksetInitialized) { 1220 Entryset = ExitLocksets[PrevBlockID]; 1221 LocksetInitialized = true; 1222 } else { 1223 Entryset = intersectAndWarn(S, Entryset, ExitLocksets[PrevBlockID], 1224 LocksetFactory); 1225 } 1226 } 1227 1228 BuildLockset LocksetBuilder(S, Entryset, LocksetFactory); 1229 for (CFGBlock::const_iterator BI = CurrBlock->begin(), 1230 BE = CurrBlock->end(); BI != BE; ++BI) { 1231 if (const CFGStmt *CfgStmt = dyn_cast<CFGStmt>(&*BI)) 1232 LocksetBuilder.Visit(const_cast<Stmt*>(CfgStmt->getStmt())); 1233 } 1234 Exitset = LocksetBuilder.getLockset(); 1235 1236 // For every back edge from CurrBlock (the end of the loop) to another block 1237 // (FirstLoopBlock) we need to check that the Lockset of Block is equal to 1238 // the one held at the beginning of FirstLoopBlock. We can look up the 1239 // Lockset held at the beginning of FirstLoopBlock in the EntryLockSets map. 1240 for (CFGBlock::const_succ_iterator SI = CurrBlock->succ_begin(), 1241 SE = CurrBlock->succ_end(); SI != SE; ++SI) { 1242 1243 // if CurrBlock -> *SI is *not* a back edge 1244 if (*SI == 0 || !VisitedBlocks.alreadySet(*SI)) 1245 continue; 1246 1247 CFGBlock *FirstLoopBlock = *SI; 1248 SourceLocation FirstLoopLocation = getFirstStmtLocation(FirstLoopBlock); 1249 1250 assert(FirstLoopLocation.isValid()); 1251 // Fail gracefully in release code. 1252 if (!FirstLoopLocation.isValid()) 1253 continue; 1254 1255 Lockset PreLoop = EntryLocksets[FirstLoopBlock->getBlockID()]; 1256 Lockset LoopEnd = ExitLocksets[CurrBlockID]; 1257 warnBackEdgeUnequalLocksets(S, LoopEnd, PreLoop, FirstLoopLocation); 1258 } 1259 } 1260 1261 Lockset FinalLockset = ExitLocksets[CFGraph->getExit().getBlockID()]; 1262 if (!FinalLockset.isEmpty()) { 1263 DiagList Warnings; 1264 for (Lockset::iterator I=FinalLockset.begin(), E=FinalLockset.end(); 1265 I != E; ++I) { 1266 const LockID &MissingLock = I.getKey(); 1267 const LockData &MissingLockData = I.getData(); 1268 1269 std::string FunName = "<unknown>"; 1270 if (const NamedDecl *ContextDecl = dyn_cast<NamedDecl>(AC.getDecl())) { 1271 FunName = ContextDecl->getDeclName().getAsString(); 1272 } 1273 1274 PartialDiagnostic Warning = 1275 S.PDiag(diag::warn_locks_not_released) 1276 << MissingLock.getName() << FunName; 1277 Warnings.push_back(DelayedDiag(MissingLockData.AcquireLoc, Warning)); 1278 } 1279 EmitDiagnostics(S, Warnings); 1280 } 1281} 1282 1283 1284//===----------------------------------------------------------------------===// 1285// AnalysisBasedWarnings - Worker object used by Sema to execute analysis-based 1286// warnings on a function, method, or block. 1287//===----------------------------------------------------------------------===// 1288 1289clang::sema::AnalysisBasedWarnings::Policy::Policy() { 1290 enableCheckFallThrough = 1; 1291 enableCheckUnreachable = 0; 1292 enableThreadSafetyAnalysis = 0; 1293} 1294 1295clang::sema::AnalysisBasedWarnings::AnalysisBasedWarnings(Sema &s) 1296 : S(s), 1297 NumFunctionsAnalyzed(0), 1298 NumFunctionsWithBadCFGs(0), 1299 NumCFGBlocks(0), 1300 MaxCFGBlocksPerFunction(0), 1301 NumUninitAnalysisFunctions(0), 1302 NumUninitAnalysisVariables(0), 1303 MaxUninitAnalysisVariablesPerFunction(0), 1304 NumUninitAnalysisBlockVisits(0), 1305 MaxUninitAnalysisBlockVisitsPerFunction(0) { 1306 Diagnostic &D = S.getDiagnostics(); 1307 DefaultPolicy.enableCheckUnreachable = (unsigned) 1308 (D.getDiagnosticLevel(diag::warn_unreachable, SourceLocation()) != 1309 Diagnostic::Ignored); 1310 DefaultPolicy.enableThreadSafetyAnalysis = (unsigned) 1311 (D.getDiagnosticLevel(diag::warn_double_lock, SourceLocation()) != 1312 Diagnostic::Ignored); 1313 1314} 1315 1316static void flushDiagnostics(Sema &S, sema::FunctionScopeInfo *fscope) { 1317 for (SmallVectorImpl<sema::PossiblyUnreachableDiag>::iterator 1318 i = fscope->PossiblyUnreachableDiags.begin(), 1319 e = fscope->PossiblyUnreachableDiags.end(); 1320 i != e; ++i) { 1321 const sema::PossiblyUnreachableDiag &D = *i; 1322 S.Diag(D.Loc, D.PD); 1323 } 1324} 1325 1326void clang::sema:: 1327AnalysisBasedWarnings::IssueWarnings(sema::AnalysisBasedWarnings::Policy P, 1328 sema::FunctionScopeInfo *fscope, 1329 const Decl *D, const BlockExpr *blkExpr) { 1330 1331 // We avoid doing analysis-based warnings when there are errors for 1332 // two reasons: 1333 // (1) The CFGs often can't be constructed (if the body is invalid), so 1334 // don't bother trying. 1335 // (2) The code already has problems; running the analysis just takes more 1336 // time. 1337 Diagnostic &Diags = S.getDiagnostics(); 1338 1339 // Do not do any analysis for declarations in system headers if we are 1340 // going to just ignore them. 1341 if (Diags.getSuppressSystemWarnings() && 1342 S.SourceMgr.isInSystemHeader(D->getLocation())) 1343 return; 1344 1345 // For code in dependent contexts, we'll do this at instantiation time. 1346 if (cast<DeclContext>(D)->isDependentContext()) 1347 return; 1348 1349 if (Diags.hasErrorOccurred() || Diags.hasFatalErrorOccurred()) { 1350 // Flush out any possibly unreachable diagnostics. 1351 flushDiagnostics(S, fscope); 1352 return; 1353 } 1354 1355 const Stmt *Body = D->getBody(); 1356 assert(Body); 1357 1358 AnalysisContext AC(D, 0); 1359 1360 // Don't generate EH edges for CallExprs as we'd like to avoid the n^2 1361 // explosion for destrutors that can result and the compile time hit. 1362 AC.getCFGBuildOptions().PruneTriviallyFalseEdges = true; 1363 AC.getCFGBuildOptions().AddEHEdges = false; 1364 AC.getCFGBuildOptions().AddInitializers = true; 1365 AC.getCFGBuildOptions().AddImplicitDtors = true; 1366 1367 // Force that certain expressions appear as CFGElements in the CFG. This 1368 // is used to speed up various analyses. 1369 // FIXME: This isn't the right factoring. This is here for initial 1370 // prototyping, but we need a way for analyses to say what expressions they 1371 // expect to always be CFGElements and then fill in the BuildOptions 1372 // appropriately. This is essentially a layering violation. 1373 if (P.enableCheckUnreachable) { 1374 // Unreachable code analysis requires a linearized CFG. 1375 AC.getCFGBuildOptions().setAllAlwaysAdd(); 1376 } 1377 else { 1378 AC.getCFGBuildOptions() 1379 .setAlwaysAdd(Stmt::BinaryOperatorClass) 1380 .setAlwaysAdd(Stmt::BlockExprClass) 1381 .setAlwaysAdd(Stmt::CStyleCastExprClass) 1382 .setAlwaysAdd(Stmt::DeclRefExprClass) 1383 .setAlwaysAdd(Stmt::ImplicitCastExprClass) 1384 .setAlwaysAdd(Stmt::UnaryOperatorClass); 1385 } 1386 1387 // Construct the analysis context with the specified CFG build options. 1388 1389 // Emit delayed diagnostics. 1390 if (!fscope->PossiblyUnreachableDiags.empty()) { 1391 bool analyzed = false; 1392 1393 // Register the expressions with the CFGBuilder. 1394 for (SmallVectorImpl<sema::PossiblyUnreachableDiag>::iterator 1395 i = fscope->PossiblyUnreachableDiags.begin(), 1396 e = fscope->PossiblyUnreachableDiags.end(); 1397 i != e; ++i) { 1398 if (const Stmt *stmt = i->stmt) 1399 AC.registerForcedBlockExpression(stmt); 1400 } 1401 1402 if (AC.getCFG()) { 1403 analyzed = true; 1404 for (SmallVectorImpl<sema::PossiblyUnreachableDiag>::iterator 1405 i = fscope->PossiblyUnreachableDiags.begin(), 1406 e = fscope->PossiblyUnreachableDiags.end(); 1407 i != e; ++i) 1408 { 1409 const sema::PossiblyUnreachableDiag &D = *i; 1410 bool processed = false; 1411 if (const Stmt *stmt = i->stmt) { 1412 const CFGBlock *block = AC.getBlockForRegisteredExpression(stmt); 1413 assert(block); 1414 if (CFGReverseBlockReachabilityAnalysis *cra = AC.getCFGReachablityAnalysis()) { 1415 // Can this block be reached from the entrance? 1416 if (cra->isReachable(&AC.getCFG()->getEntry(), block)) 1417 S.Diag(D.Loc, D.PD); 1418 processed = true; 1419 } 1420 } 1421 if (!processed) { 1422 // Emit the warning anyway if we cannot map to a basic block. 1423 S.Diag(D.Loc, D.PD); 1424 } 1425 } 1426 } 1427 1428 if (!analyzed) 1429 flushDiagnostics(S, fscope); 1430 } 1431 1432 1433 // Warning: check missing 'return' 1434 if (P.enableCheckFallThrough) { 1435 const CheckFallThroughDiagnostics &CD = 1436 (isa<BlockDecl>(D) ? CheckFallThroughDiagnostics::MakeForBlock() 1437 : CheckFallThroughDiagnostics::MakeForFunction(D)); 1438 CheckFallThroughForBody(S, D, Body, blkExpr, CD, AC); 1439 } 1440 1441 // Warning: check for unreachable code 1442 if (P.enableCheckUnreachable) 1443 CheckUnreachable(S, AC); 1444 1445 // Check for thread safety violations 1446 if (P.enableThreadSafetyAnalysis) 1447 checkThreadSafety(S, AC); 1448 1449 if (Diags.getDiagnosticLevel(diag::warn_uninit_var, D->getLocStart()) 1450 != Diagnostic::Ignored || 1451 Diags.getDiagnosticLevel(diag::warn_maybe_uninit_var, D->getLocStart()) 1452 != Diagnostic::Ignored) { 1453 if (CFG *cfg = AC.getCFG()) { 1454 UninitValsDiagReporter reporter(S); 1455 UninitVariablesAnalysisStats stats; 1456 std::memset(&stats, 0, sizeof(UninitVariablesAnalysisStats)); 1457 runUninitializedVariablesAnalysis(*cast<DeclContext>(D), *cfg, AC, 1458 reporter, stats); 1459 1460 if (S.CollectStats && stats.NumVariablesAnalyzed > 0) { 1461 ++NumUninitAnalysisFunctions; 1462 NumUninitAnalysisVariables += stats.NumVariablesAnalyzed; 1463 NumUninitAnalysisBlockVisits += stats.NumBlockVisits; 1464 MaxUninitAnalysisVariablesPerFunction = 1465 std::max(MaxUninitAnalysisVariablesPerFunction, 1466 stats.NumVariablesAnalyzed); 1467 MaxUninitAnalysisBlockVisitsPerFunction = 1468 std::max(MaxUninitAnalysisBlockVisitsPerFunction, 1469 stats.NumBlockVisits); 1470 } 1471 } 1472 } 1473 1474 // Collect statistics about the CFG if it was built. 1475 if (S.CollectStats && AC.isCFGBuilt()) { 1476 ++NumFunctionsAnalyzed; 1477 if (CFG *cfg = AC.getCFG()) { 1478 // If we successfully built a CFG for this context, record some more 1479 // detail information about it. 1480 NumCFGBlocks += cfg->getNumBlockIDs(); 1481 MaxCFGBlocksPerFunction = std::max(MaxCFGBlocksPerFunction, 1482 cfg->getNumBlockIDs()); 1483 } else { 1484 ++NumFunctionsWithBadCFGs; 1485 } 1486 } 1487} 1488 1489void clang::sema::AnalysisBasedWarnings::PrintStats() const { 1490 llvm::errs() << "\n*** Analysis Based Warnings Stats:\n"; 1491 1492 unsigned NumCFGsBuilt = NumFunctionsAnalyzed - NumFunctionsWithBadCFGs; 1493 unsigned AvgCFGBlocksPerFunction = 1494 !NumCFGsBuilt ? 0 : NumCFGBlocks/NumCFGsBuilt; 1495 llvm::errs() << NumFunctionsAnalyzed << " functions analyzed (" 1496 << NumFunctionsWithBadCFGs << " w/o CFGs).\n" 1497 << " " << NumCFGBlocks << " CFG blocks built.\n" 1498 << " " << AvgCFGBlocksPerFunction 1499 << " average CFG blocks per function.\n" 1500 << " " << MaxCFGBlocksPerFunction 1501 << " max CFG blocks per function.\n"; 1502 1503 unsigned AvgUninitVariablesPerFunction = !NumUninitAnalysisFunctions ? 0 1504 : NumUninitAnalysisVariables/NumUninitAnalysisFunctions; 1505 unsigned AvgUninitBlockVisitsPerFunction = !NumUninitAnalysisFunctions ? 0 1506 : NumUninitAnalysisBlockVisits/NumUninitAnalysisFunctions; 1507 llvm::errs() << NumUninitAnalysisFunctions 1508 << " functions analyzed for uninitialiazed variables\n" 1509 << " " << NumUninitAnalysisVariables << " variables analyzed.\n" 1510 << " " << AvgUninitVariablesPerFunction 1511 << " average variables per function.\n" 1512 << " " << MaxUninitAnalysisVariablesPerFunction 1513 << " max variables per function.\n" 1514 << " " << NumUninitAnalysisBlockVisits << " block visits.\n" 1515 << " " << AvgUninitBlockVisitsPerFunction 1516 << " average block visits per function.\n" 1517 << " " << MaxUninitAnalysisBlockVisitsPerFunction 1518 << " max block visits per function.\n"; 1519} 1520