From 42461eecee98fff3671b3c14ce10f1a9e18cc95c Mon Sep 17 00:00:00 2001 From: Ted Kremenek Date: Wed, 23 Feb 2011 01:51:59 +0000 Subject: [PATCH] Migrate CFGReachabilityAnalysis out of the IdempotentOperationsChecker and into its own analysis file. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@126289 91177308-0d34-0410-b5e6-96231b3b80d8 --- .../Analyses/CFGReachabilityAnalysis.h | 49 ++++++++++ include/clang/Analysis/AnalysisContext.h | 6 +- lib/Analysis/AnalysisContext.cpp | 13 +++ lib/Analysis/CFGReachabilityAnalysis.cpp | 76 ++++++++++++++++ lib/Analysis/CMakeLists.txt | 1 + .../Checkers/IdempotentOperationChecker.cpp | 91 ++----------------- 6 files changed, 152 insertions(+), 84 deletions(-) create mode 100644 include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h create mode 100644 lib/Analysis/CFGReachabilityAnalysis.cpp diff --git a/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h b/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h new file mode 100644 index 0000000000..72f644aaf0 --- /dev/null +++ b/include/clang/Analysis/Analyses/CFGReachabilityAnalysis.h @@ -0,0 +1,49 @@ +//==- CFGReachabilityAnalysis.h - Basic reachability analysis ----*- 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 flow-sensitive, (mostly) path-insensitive reachability +// analysis based on Clang's CFGs. Clients can query if a given basic block +// is reachable within the CFG. +// +//===----------------------------------------------------------------------===// + +#ifndef CLANG_ANALYSIS_CFG_REACHABILITY +#define CLANG_ANALYSIS_CFG_REACHABILITY + +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" + +namespace clang { + +class CFG; +class CFGBlock; + +// A class that performs reachability queries for CFGBlocks. Several internal +// checks in this checker require reachability information. The requests all +// tend to have a common destination, so we lazily do a predecessor search +// from the destination node and cache the results to prevent work +// duplication. +class CFGReachabilityAnalysis { + typedef llvm::BitVector ReachableSet; + typedef llvm::DenseMap ReachableMap; + ReachableSet analyzed; + ReachableMap reachable; +public: + CFGReachabilityAnalysis(const CFG &cfg); + + /// Returns true if the block 'Dst' can be reached from block 'Src'. + bool isReachable(const CFGBlock *Src, const CFGBlock *Dst); + +private: + void mapReachability(const CFGBlock *Dst); +}; + +} + +#endif diff --git a/include/clang/Analysis/AnalysisContext.h b/include/clang/Analysis/AnalysisContext.h index 69446eb814..8514514578 100644 --- a/include/clang/Analysis/AnalysisContext.h +++ b/include/clang/Analysis/AnalysisContext.h @@ -29,6 +29,7 @@ class Decl; class Stmt; class CFG; class CFGBlock; +class CFGReachabilityAnalysis; class CFGStmtMap; class LiveVariables; class ParentMap; @@ -55,6 +56,7 @@ class AnalysisContext { LiveVariables *relaxedLiveness; ParentMap *PM; PseudoConstantAnalysis *PCA; + CFGReachabilityAnalysis *CFA; llvm::DenseMap *ReferencedBlockVars; llvm::BumpPtrAllocator A; bool UseUnoptimizedCFG; @@ -69,7 +71,7 @@ public: bool addInitializers = false) : D(d), TU(tu), cfg(0), completeCFG(0), cfgStmtMap(0), builtCFG(false), builtCompleteCFG(false), - liveness(0), relaxedLiveness(0), PM(0), PCA(0), + liveness(0), relaxedLiveness(0), PM(0), PCA(0), CFA(0), ReferencedBlockVars(0), UseUnoptimizedCFG(useUnoptimizedCFG), AddEHEdges(addehedges), AddImplicitDtors(addImplicitDtors), AddInitializers(addInitializers) {} @@ -96,6 +98,8 @@ public: CFGStmtMap *getCFGStmtMap(); + CFGReachabilityAnalysis *getCFGReachablityAnalysis(); + /// Return a version of the CFG without any edges pruned. CFG *getUnoptimizedCFG(); diff --git a/lib/Analysis/AnalysisContext.cpp b/lib/Analysis/AnalysisContext.cpp index a982a5c5be..62097ef20d 100644 --- a/lib/Analysis/AnalysisContext.cpp +++ b/lib/Analysis/AnalysisContext.cpp @@ -19,6 +19,7 @@ #include "clang/AST/StmtVisitor.h" #include "clang/Analysis/Analyses/LiveVariables.h" #include "clang/Analysis/Analyses/PseudoConstantAnalysis.h" +#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/Analysis/CFG.h" #include "clang/Analysis/CFGStmtMap.h" @@ -98,7 +99,18 @@ CFGStmtMap *AnalysisContext::getCFGStmtMap() { return 0; } + +CFGReachabilityAnalysis *AnalysisContext::getCFGReachablityAnalysis() { + if (CFA) + return CFA; + + if (CFG *c = getCFG()) { + CFA = new CFGReachabilityAnalysis(*c); + return CFA; + } + return 0; +} void AnalysisContext::dumpCFG() { getCFG()->dump(getASTContext().getLangOptions()); @@ -365,6 +377,7 @@ AnalysisContext::~AnalysisContext() { delete relaxedLiveness; delete PM; delete PCA; + delete CFA; delete ReferencedBlockVars; } diff --git a/lib/Analysis/CFGReachabilityAnalysis.cpp b/lib/Analysis/CFGReachabilityAnalysis.cpp new file mode 100644 index 0000000000..7786584901 --- /dev/null +++ b/lib/Analysis/CFGReachabilityAnalysis.cpp @@ -0,0 +1,76 @@ +//==- CFGReachabilityAnalysis.cpp - Basic reachability analysis --*- 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 flow-sensitive, (mostly) path-insensitive reachability +// analysis based on Clang's CFGs. Clients can query if a given basic block +// is reachable within the CFG. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/SmallVector.h" +#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h" +#include "clang/Analysis/CFG.h" + +using namespace clang; + +CFGReachabilityAnalysis::CFGReachabilityAnalysis(const CFG &cfg) + : analyzed(cfg.getNumBlockIDs(), false) {} + +bool CFGReachabilityAnalysis::isReachable(const CFGBlock *Src, + const CFGBlock *Dst) { + + const unsigned DstBlockID = Dst->getBlockID(); + + // If we haven't analyzed the destination node, run the analysis now + if (!analyzed[DstBlockID]) { + mapReachability(Dst); + analyzed[DstBlockID] = true; + } + + // Return the cached result + return reachable[DstBlockID][Src->getBlockID()]; +} + +// Maps reachability to a common node by walking the predecessors of the +// destination node. +void CFGReachabilityAnalysis::mapReachability(const CFGBlock *Dst) { + llvm::SmallVector worklist; + llvm::BitVector visited(analyzed.size()); + + ReachableSet &DstReachability = reachable[Dst->getBlockID()]; + DstReachability.resize(analyzed.size(), false); + + // Start searching from the destination node, since we commonly will perform + // multiple queries relating to a destination node. + worklist.push_back(Dst); + bool firstRun = true; + + while (!worklist.empty()) { + const CFGBlock *block = worklist.back(); + worklist.pop_back(); + + if (visited[block->getBlockID()]) + continue; + visited[block->getBlockID()] = true; + + // Update reachability information for this node -> Dst + if (!firstRun) { + // Don't insert Dst -> Dst unless it was a predecessor of itself + DstReachability[block->getBlockID()] = true; + } + else + firstRun = false; + + // Add the predecessors to the worklist. + for (CFGBlock::const_pred_iterator i = block->pred_begin(), + e = block->pred_end(); i != e; ++i) { + worklist.push_back(*i); + } + } +} diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt index 0912f3c874..84b211f2cf 100644 --- a/lib/Analysis/CMakeLists.txt +++ b/lib/Analysis/CMakeLists.txt @@ -3,6 +3,7 @@ set(LLVM_USED_LIBS clangBasic clangAST clangIndex) add_clang_library(clangAnalysis AnalysisContext.cpp CFG.cpp + CFGReachabilityAnalysis.cpp CFGStmtMap.cpp CocoaConventions.cpp FormatString.cpp diff --git a/lib/StaticAnalyzer/Checkers/IdempotentOperationChecker.cpp b/lib/StaticAnalyzer/Checkers/IdempotentOperationChecker.cpp index 0d2ccb955f..171b39efe2 100644 --- a/lib/StaticAnalyzer/Checkers/IdempotentOperationChecker.cpp +++ b/lib/StaticAnalyzer/Checkers/IdempotentOperationChecker.cpp @@ -45,6 +45,7 @@ #include "ClangSACheckers.h" #include "clang/Analysis/CFGStmtMap.h" #include "clang/Analysis/Analyses/PseudoConstantAnalysis.h" +#include "clang/Analysis/Analyses/CFGReachabilityAnalysis.h" #include "clang/StaticAnalyzer/Core/CheckerManager.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" #include "clang/StaticAnalyzer/Core/BugReporter/BugType.h" @@ -83,9 +84,8 @@ private: static bool isUnused(const Expr *E, AnalysisContext *AC); static bool isTruncationExtensionAssignment(const Expr *LHS, const Expr *RHS); - bool pathWasCompletelyAnalyzed(const CFG *cfg, + bool pathWasCompletelyAnalyzed(AnalysisContext *AC, const CFGBlock *CB, - const CFGStmtMap *CBM, const CoreEngine &CE); static bool CanVary(const Expr *Ex, AnalysisContext *AC); @@ -105,26 +105,6 @@ private: typedef llvm::DenseMap AssumptionMap; AssumptionMap hash; - - // A class that performs reachability queries for CFGBlocks. Several internal - // checks in this checker require reachability information. The requests all - // tend to have a common destination, so we lazily do a predecessor search - // from the destination node and cache the results to prevent work - // duplication. - class CFGReachabilityAnalysis { - typedef llvm::BitVector ReachableSet; - typedef llvm::DenseMap ReachableMap; - ReachableSet analyzed; - ReachableMap reachable; - public: - CFGReachabilityAnalysis(const CFG &cfg) - : analyzed(cfg.getNumBlockIDs(), false) {} - - inline bool isReachable(const CFGBlock *Src, const CFGBlock *Dst); - private: - void MapReachability(const CFGBlock *Dst); - }; - llvm::OwningPtr CRA; }; } @@ -397,11 +377,9 @@ void IdempotentOperationChecker::VisitEndAnalysis(ExplodedGraph &G, // If the analyzer did not finish, check to see if we can still emit this // warning if (Eng.hasWorkRemaining()) { - const CFGStmtMap *CBM = AC->getCFGStmtMap(); - // If we can trace back - if (!pathWasCompletelyAnalyzed(AC->getCFG(), - CBM->getBlock(B), CBM, + if (!pathWasCompletelyAnalyzed(AC, + AC->getCFGStmtMap()->getBlock(B), Eng.getCoreEngine())) continue; } @@ -561,13 +539,11 @@ bool IdempotentOperationChecker::isTruncationExtensionAssignment( // Returns false if a path to this block was not completely analyzed, or true // otherwise. bool -IdempotentOperationChecker::pathWasCompletelyAnalyzed(const CFG *cfg, +IdempotentOperationChecker::pathWasCompletelyAnalyzed(AnalysisContext *AC, const CFGBlock *CB, - const CFGStmtMap *CBM, const CoreEngine &CE) { - if (!CRA.get()) - CRA.reset(new CFGReachabilityAnalysis(*cfg)); + CFGReachabilityAnalysis *CRA = AC->getCFGReachablityAnalysis(); // Test for reachability from any aborted blocks to this block typedef CoreEngine::BlocksAborted::const_iterator AbortedIterator; @@ -618,14 +594,14 @@ IdempotentOperationChecker::pathWasCompletelyAnalyzed(const CFG *cfg, return CRA.isReachable(B, TargetBlock); } }; - VisitWL visitWL(CBM, CB, *CRA.get()); + VisitWL visitWL(AC->getCFGStmtMap(), CB, *CRA); // Were there any items in the worklist that could potentially reach // this block? if (CE.getWorkList()->visitItemsInWorkList(visitWL)) return false; // Verify that this block is reachable from the entry block - if (!CRA->isReachable(&cfg->getEntry(), CB)) + if (!CRA->isReachable(&AC->getCFG()->getEntry(), CB)) return false; // If we get to this point, there is no connection to the entry block or an @@ -763,57 +739,6 @@ bool IdempotentOperationChecker::containsNonLocalVarDecl(const Stmt *S) { return false; } -bool IdempotentOperationChecker::CFGReachabilityAnalysis::isReachable( - const CFGBlock *Src, - const CFGBlock *Dst) { - const unsigned DstBlockID = Dst->getBlockID(); - - // If we haven't analyzed the destination node, run the analysis now - if (!analyzed[DstBlockID]) { - MapReachability(Dst); - analyzed[DstBlockID] = true; - } - - // Return the cached result - return reachable[DstBlockID][Src->getBlockID()]; -} -// Maps reachability to a common node by walking the predecessors of the -// destination node. -void IdempotentOperationChecker::CFGReachabilityAnalysis::MapReachability( - const CFGBlock *Dst) { - llvm::SmallVector worklist; - llvm::BitVector visited(analyzed.size()); - - ReachableSet &DstReachability = reachable[Dst->getBlockID()]; - DstReachability.resize(analyzed.size(), false); - - // Start searching from the destination node, since we commonly will perform - // multiple queries relating to a destination node. - worklist.push_back(Dst); - bool firstRun = true; - - while (!worklist.empty()) { - const CFGBlock *block = worklist.back(); - worklist.pop_back(); - - if (visited[block->getBlockID()]) - continue; - visited[block->getBlockID()] = true; - - // Update reachability information for this node -> Dst - if (!firstRun) { - // Don't insert Dst -> Dst unless it was a predecessor of itself - DstReachability[block->getBlockID()] = true; - } - else - firstRun = false; - // Add the predecessors to the worklist. - for (CFGBlock::const_pred_iterator i = block->pred_begin(), - e = block->pred_end(); i != e; ++i) { - worklist.push_back(*i); - } - } -} -- 2.40.0