| //==- DeadStoresChecker.cpp - Check for stores to dead variables -*- C++ -*-==// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file defines a DeadStores, a flow-sensitive checker that looks for |
| // stores to variables that are no longer live. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "ClangSACheckers.h" |
| #include "clang/AST/ASTContext.h" |
| #include "clang/AST/ParentMap.h" |
| #include "clang/AST/RecursiveASTVisitor.h" |
| #include "clang/Analysis/Analyses/LiveVariables.h" |
| #include "clang/Analysis/Visitors/CFGRecStmtDeclVisitor.h" |
| #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" |
| #include "clang/StaticAnalyzer/Core/Checker.h" |
| #include "clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h" |
| #include "llvm/ADT/BitVector.h" |
| #include "llvm/ADT/SmallString.h" |
| #include "llvm/Support/SaveAndRestore.h" |
| |
| using namespace clang; |
| using namespace ento; |
| |
| namespace { |
| |
| /// A simple visitor to record what VarDecls occur in EH-handling code. |
| class EHCodeVisitor : public RecursiveASTVisitor<EHCodeVisitor> { |
| public: |
| bool inEH; |
| llvm::DenseSet<const VarDecl *> &S; |
| |
| bool TraverseObjCAtFinallyStmt(ObjCAtFinallyStmt *S) { |
| SaveAndRestore<bool> inFinally(inEH, true); |
| return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtFinallyStmt(S); |
| } |
| |
| bool TraverseObjCAtCatchStmt(ObjCAtCatchStmt *S) { |
| SaveAndRestore<bool> inCatch(inEH, true); |
| return ::RecursiveASTVisitor<EHCodeVisitor>::TraverseObjCAtCatchStmt(S); |
| } |
| |
| bool TraverseCXXCatchStmt(CXXCatchStmt *S) { |
| SaveAndRestore<bool> inCatch(inEH, true); |
| return TraverseStmt(S->getHandlerBlock()); |
| } |
| |
| bool VisitDeclRefExpr(DeclRefExpr *DR) { |
| if (inEH) |
| if (const VarDecl *D = dyn_cast<VarDecl>(DR->getDecl())) |
| S.insert(D); |
| return true; |
| } |
| |
| EHCodeVisitor(llvm::DenseSet<const VarDecl *> &S) : |
| inEH(false), S(S) {} |
| }; |
| |
| // FIXME: Eventually migrate into its own file, and have it managed by |
| // AnalysisManager. |
| class ReachableCode { |
| const CFG &cfg; |
| llvm::BitVector reachable; |
| public: |
| ReachableCode(const CFG &cfg) |
| : cfg(cfg), reachable(cfg.getNumBlockIDs(), false) {} |
| |
| void computeReachableBlocks(); |
| |
| bool isReachable(const CFGBlock *block) const { |
| return reachable[block->getBlockID()]; |
| } |
| }; |
| } |
| |
| void ReachableCode::computeReachableBlocks() { |
| if (!cfg.getNumBlockIDs()) |
| return; |
| |
| SmallVector<const CFGBlock*, 10> worklist; |
| worklist.push_back(&cfg.getEntry()); |
| |
| while (!worklist.empty()) { |
| const CFGBlock *block = worklist.back(); |
| worklist.pop_back(); |
| llvm::BitVector::reference isReachable = reachable[block->getBlockID()]; |
| if (isReachable) |
| continue; |
| isReachable = true; |
| for (CFGBlock::const_succ_iterator i = block->succ_begin(), |
| e = block->succ_end(); i != e; ++i) |
| if (const CFGBlock *succ = *i) |
| worklist.push_back(succ); |
| } |
| } |
| |
| static const Expr *LookThroughTransitiveAssignments(const Expr *Ex) { |
| while (Ex) { |
| const BinaryOperator *BO = |
| dyn_cast<BinaryOperator>(Ex->IgnoreParenCasts()); |
| if (!BO) |
| break; |
| if (BO->getOpcode() == BO_Assign) { |
| Ex = BO->getRHS(); |
| continue; |
| } |
| break; |
| } |
| return Ex; |
| } |
| |
| namespace { |
| class DeadStoreObs : public LiveVariables::Observer { |
| const CFG &cfg; |
| ASTContext &Ctx; |
| BugReporter& BR; |
| AnalysisDeclContext* AC; |
| ParentMap& Parents; |
| llvm::SmallPtrSet<const VarDecl*, 20> Escaped; |
| OwningPtr<ReachableCode> reachableCode; |
| const CFGBlock *currentBlock; |
| llvm::OwningPtr<llvm::DenseSet<const VarDecl *> > InEH; |
| |
| enum DeadStoreKind { Standard, Enclosing, DeadIncrement, DeadInit }; |
| |
| public: |
| DeadStoreObs(const CFG &cfg, ASTContext &ctx, |
| BugReporter& br, AnalysisDeclContext* ac, ParentMap& parents, |
| llvm::SmallPtrSet<const VarDecl*, 20> &escaped) |
| : cfg(cfg), Ctx(ctx), BR(br), AC(ac), Parents(parents), |
| Escaped(escaped), currentBlock(0) {} |
| |
| virtual ~DeadStoreObs() {} |
| |
| bool isLive(const LiveVariables::LivenessValues &Live, const VarDecl *D) { |
| if (Live.isLive(D)) |
| return true; |
| // Lazily construct the set that records which VarDecls are in |
| // EH code. |
| if (!InEH.get()) { |
| InEH.reset(new llvm::DenseSet<const VarDecl *>()); |
| EHCodeVisitor V(*InEH.get()); |
| V.TraverseStmt(AC->getBody()); |
| } |
| // Treat all VarDecls that occur in EH code as being "always live" |
| // when considering to suppress dead stores. Frequently stores |
| // are followed by reads in EH code, but we don't have the ability |
| // to analyze that yet. |
| return InEH->count(D); |
| } |
| |
| void Report(const VarDecl *V, DeadStoreKind dsk, |
| PathDiagnosticLocation L, SourceRange R) { |
| if (Escaped.count(V)) |
| return; |
| |
| // Compute reachable blocks within the CFG for trivial cases |
| // where a bogus dead store can be reported because itself is unreachable. |
| if (!reachableCode.get()) { |
| reachableCode.reset(new ReachableCode(cfg)); |
| reachableCode->computeReachableBlocks(); |
| } |
| |
| if (!reachableCode->isReachable(currentBlock)) |
| return; |
| |
| SmallString<64> buf; |
| llvm::raw_svector_ostream os(buf); |
| const char *BugType = 0; |
| |
| switch (dsk) { |
| case DeadInit: |
| BugType = "Dead initialization"; |
| os << "Value stored to '" << *V |
| << "' during its initialization is never read"; |
| break; |
| |
| case DeadIncrement: |
| BugType = "Dead increment"; |
| case Standard: |
| if (!BugType) BugType = "Dead assignment"; |
| os << "Value stored to '" << *V << "' is never read"; |
| break; |
| |
| case Enclosing: |
| // Don't report issues in this case, e.g.: "if (x = foo())", |
| // where 'x' is unused later. We have yet to see a case where |
| // this is a real bug. |
| return; |
| } |
| |
| BR.EmitBasicReport(AC->getDecl(), BugType, "Dead store", os.str(), L, R); |
| } |
| |
| void CheckVarDecl(const VarDecl *VD, const Expr *Ex, const Expr *Val, |
| DeadStoreKind dsk, |
| const LiveVariables::LivenessValues &Live) { |
| |
| if (!VD->hasLocalStorage()) |
| return; |
| // Reference types confuse the dead stores checker. Skip them |
| // for now. |
| if (VD->getType()->getAs<ReferenceType>()) |
| return; |
| |
| if (!isLive(Live, VD) && |
| !(VD->getAttr<UnusedAttr>() || VD->getAttr<BlocksAttr>())) { |
| |
| PathDiagnosticLocation ExLoc = |
| PathDiagnosticLocation::createBegin(Ex, BR.getSourceManager(), AC); |
| Report(VD, dsk, ExLoc, Val->getSourceRange()); |
| } |
| } |
| |
| void CheckDeclRef(const DeclRefExpr *DR, const Expr *Val, DeadStoreKind dsk, |
| const LiveVariables::LivenessValues& Live) { |
| if (const VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) |
| CheckVarDecl(VD, DR, Val, dsk, Live); |
| } |
| |
| bool isIncrement(VarDecl *VD, const BinaryOperator* B) { |
| if (B->isCompoundAssignmentOp()) |
| return true; |
| |
| const Expr *RHS = B->getRHS()->IgnoreParenCasts(); |
| const BinaryOperator* BRHS = dyn_cast<BinaryOperator>(RHS); |
| |
| if (!BRHS) |
| return false; |
| |
| const DeclRefExpr *DR; |
| |
| if ((DR = dyn_cast<DeclRefExpr>(BRHS->getLHS()->IgnoreParenCasts()))) |
| if (DR->getDecl() == VD) |
| return true; |
| |
| if ((DR = dyn_cast<DeclRefExpr>(BRHS->getRHS()->IgnoreParenCasts()))) |
| if (DR->getDecl() == VD) |
| return true; |
| |
| return false; |
| } |
| |
| virtual void observeStmt(const Stmt *S, const CFGBlock *block, |
| const LiveVariables::LivenessValues &Live) { |
| |
| currentBlock = block; |
| |
| // Skip statements in macros. |
| if (S->getLocStart().isMacroID()) |
| return; |
| |
| // Only cover dead stores from regular assignments. ++/-- dead stores |
| // have never flagged a real bug. |
| if (const BinaryOperator* B = dyn_cast<BinaryOperator>(S)) { |
| if (!B->isAssignmentOp()) return; // Skip non-assignments. |
| |
| if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(B->getLHS())) |
| if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { |
| // Special case: check for assigning null to a pointer. |
| // This is a common form of defensive programming. |
| const Expr *RHS = LookThroughTransitiveAssignments(B->getRHS()); |
| |
| QualType T = VD->getType(); |
| if (T->isPointerType() || T->isObjCObjectPointerType()) { |
| if (RHS->isNullPointerConstant(Ctx, Expr::NPC_ValueDependentIsNull)) |
| return; |
| } |
| |
| RHS = RHS->IgnoreParenCasts(); |
| // Special case: self-assignments. These are often used to shut up |
| // "unused variable" compiler warnings. |
| if (const DeclRefExpr *RhsDR = dyn_cast<DeclRefExpr>(RHS)) |
| if (VD == dyn_cast<VarDecl>(RhsDR->getDecl())) |
| return; |
| |
| // Otherwise, issue a warning. |
| DeadStoreKind dsk = Parents.isConsumedExpr(B) |
| ? Enclosing |
| : (isIncrement(VD,B) ? DeadIncrement : Standard); |
| |
| CheckVarDecl(VD, DR, B->getRHS(), dsk, Live); |
| } |
| } |
| else if (const UnaryOperator* U = dyn_cast<UnaryOperator>(S)) { |
| if (!U->isIncrementOp() || U->isPrefix()) |
| return; |
| |
| const Stmt *parent = Parents.getParentIgnoreParenCasts(U); |
| if (!parent || !isa<ReturnStmt>(parent)) |
| return; |
| |
| const Expr *Ex = U->getSubExpr()->IgnoreParenCasts(); |
| |
| if (const DeclRefExpr *DR = dyn_cast<DeclRefExpr>(Ex)) |
| CheckDeclRef(DR, U, DeadIncrement, Live); |
| } |
| else if (const DeclStmt *DS = dyn_cast<DeclStmt>(S)) |
| // Iterate through the decls. Warn if any initializers are complex |
| // expressions that are not live (never used). |
| for (DeclStmt::const_decl_iterator DI=DS->decl_begin(), DE=DS->decl_end(); |
| DI != DE; ++DI) { |
| |
| VarDecl *V = dyn_cast<VarDecl>(*DI); |
| |
| if (!V) |
| continue; |
| |
| if (V->hasLocalStorage()) { |
| // Reference types confuse the dead stores checker. Skip them |
| // for now. |
| if (V->getType()->getAs<ReferenceType>()) |
| return; |
| |
| if (const Expr *E = V->getInit()) { |
| while (const ExprWithCleanups *exprClean = |
| dyn_cast<ExprWithCleanups>(E)) |
| E = exprClean->getSubExpr(); |
| |
| // Look through transitive assignments, e.g.: |
| // int x = y = 0; |
| E = LookThroughTransitiveAssignments(E); |
| |
| // Don't warn on C++ objects (yet) until we can show that their |
| // constructors/destructors don't have side effects. |
| if (isa<CXXConstructExpr>(E)) |
| return; |
| |
| // A dead initialization is a variable that is dead after it |
| // is initialized. We don't flag warnings for those variables |
| // marked 'unused'. |
| if (!isLive(Live, V) && V->getAttr<UnusedAttr>() == 0) { |
| // Special case: check for initializations with constants. |
| // |
| // e.g. : int x = 0; |
| // |
| // If x is EVER assigned a new value later, don't issue |
| // a warning. This is because such initialization can be |
| // due to defensive programming. |
| if (E->isEvaluatable(Ctx)) |
| return; |
| |
| if (const DeclRefExpr *DRE = |
| dyn_cast<DeclRefExpr>(E->IgnoreParenCasts())) |
| if (const VarDecl *VD = dyn_cast<VarDecl>(DRE->getDecl())) { |
| // Special case: check for initialization from constant |
| // variables. |
| // |
| // e.g. extern const int MyConstant; |
| // int x = MyConstant; |
| // |
| if (VD->hasGlobalStorage() && |
| VD->getType().isConstQualified()) |
| return; |
| // Special case: check for initialization from scalar |
| // parameters. This is often a form of defensive |
| // programming. Non-scalars are still an error since |
| // because it more likely represents an actual algorithmic |
| // bug. |
| if (isa<ParmVarDecl>(VD) && VD->getType()->isScalarType()) |
| return; |
| } |
| |
| PathDiagnosticLocation Loc = |
| PathDiagnosticLocation::create(V, BR.getSourceManager()); |
| Report(V, DeadInit, Loc, E->getSourceRange()); |
| } |
| } |
| } |
| } |
| } |
| }; |
| |
| } // end anonymous namespace |
| |
| //===----------------------------------------------------------------------===// |
| // Driver function to invoke the Dead-Stores checker on a CFG. |
| //===----------------------------------------------------------------------===// |
| |
| namespace { |
| class FindEscaped : public CFGRecStmtDeclVisitor<FindEscaped>{ |
| CFG *cfg; |
| public: |
| FindEscaped(CFG *c) : cfg(c) {} |
| |
| CFG& getCFG() { return *cfg; } |
| |
| llvm::SmallPtrSet<const VarDecl*, 20> Escaped; |
| |
| void VisitUnaryOperator(UnaryOperator* U) { |
| // Check for '&'. Any VarDecl whose value has its address-taken we |
| // treat as escaped. |
| Expr *E = U->getSubExpr()->IgnoreParenCasts(); |
| if (U->getOpcode() == UO_AddrOf) |
| if (DeclRefExpr *DR = dyn_cast<DeclRefExpr>(E)) |
| if (VarDecl *VD = dyn_cast<VarDecl>(DR->getDecl())) { |
| Escaped.insert(VD); |
| return; |
| } |
| Visit(E); |
| } |
| }; |
| } // end anonymous namespace |
| |
| |
| //===----------------------------------------------------------------------===// |
| // DeadStoresChecker |
| //===----------------------------------------------------------------------===// |
| |
| namespace { |
| class DeadStoresChecker : public Checker<check::ASTCodeBody> { |
| public: |
| void checkASTCodeBody(const Decl *D, AnalysisManager& mgr, |
| BugReporter &BR) const { |
| if (LiveVariables *L = mgr.getAnalysis<LiveVariables>(D)) { |
| CFG &cfg = *mgr.getCFG(D); |
| AnalysisDeclContext *AC = mgr.getAnalysisDeclContext(D); |
| ParentMap &pmap = mgr.getParentMap(D); |
| FindEscaped FS(&cfg); |
| FS.getCFG().VisitBlockStmts(FS); |
| DeadStoreObs A(cfg, BR.getContext(), BR, AC, pmap, FS.Escaped); |
| L->runOnAllBlocks(A); |
| } |
| } |
| }; |
| } |
| |
| void ento::registerDeadStoresChecker(CheckerManager &mgr) { |
| mgr.registerChecker<DeadStoresChecker>(); |
| } |