diff options
11 files changed, 174 insertions, 40 deletions
diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h index f8f7e25d8bb..3cbecf7d6ef 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/AnalysisManager.h @@ -30,33 +30,6 @@ namespace idx { namespace ento { class CheckerManager; -typedef llvm::SmallPtrSet<const Decl*,24> SetOfDecls; - -class FunctionSummariesTy { - struct FunctionSummary { - /// True if this function has reached a max block count while inlined from - /// at least one call site. - bool MayReachMaxBlockCount; - FunctionSummary() : MayReachMaxBlockCount(false) {} - }; - - typedef llvm::DenseMap<const Decl*, FunctionSummary> MapTy; - MapTy Map; - -public: - void markReachedMaxBlockCount(const Decl* D) { - Map[D].MayReachMaxBlockCount = true; - } - - bool hasReachedMaxBlockCount(const Decl* D) { - MapTy::const_iterator I = Map.find(D); - if (I != Map.end()) - return I->second.MayReachMaxBlockCount; - return false; - } - -}; - class AnalysisManager : public BugReporterData { virtual void anchor(); AnalysisDeclContextManager AnaCtxMgr; diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h index 85d92ff5f7b..d9156441dba 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/CoreEngine.h @@ -18,6 +18,7 @@ #include "clang/AST/Expr.h" #include "clang/Analysis/AnalysisContext.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h" #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" #include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" #include "llvm/ADT/OwningPtr.h" @@ -83,6 +84,10 @@ private: /// AnalysisConsumer. It can be null. SetOfDecls *AnalyzedCallees; + /// The information about functions shared by the whole translation unit. + /// (This data is owned by AnalysisConsumer.) + FunctionSummariesTy *FunctionSummaries; + void generateNode(const ProgramPoint &Loc, ProgramStateRef State, ExplodedNode *Pred); @@ -104,11 +109,13 @@ private: public: /// Construct a CoreEngine object to analyze the provided CFG using /// a DFS exploration of the exploded graph. - CoreEngine(SubEngine& subengine, SetOfDecls *VisitedCallees) + CoreEngine(SubEngine& subengine, SetOfDecls *VisitedCallees, + FunctionSummariesTy *FS) : SubEng(subengine), G(new ExplodedGraph()), WList(WorkList::makeBFS()), BCounterFactory(G->getAllocator()), - AnalyzedCallees(VisitedCallees) {} + AnalyzedCallees(VisitedCallees), + FunctionSummaries(FS){} ~CoreEngine() { delete WList; diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h index f4d2e6027b5..4d1ee5436f9 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h @@ -90,10 +90,6 @@ class ExprEngine : public SubEngine { /// destructor is called before the rest of the ExprEngine is destroyed. GRBugReporter BR; - /// The information about functions shared by the whole translation unit. - /// (This data is owned by AnalysisConsumer.) - FunctionSummariesTy *FunctionSummaries; - public: ExprEngine(AnalysisManager &mgr, bool gcEnabled, SetOfDecls *VisitedCallees, FunctionSummariesTy *FS); diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h new file mode 100644 index 00000000000..e1e15620fa3 --- /dev/null +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h @@ -0,0 +1,96 @@ +//== FunctionSummary.h - Stores summaries of functions. ------------*- 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 summary of a function gathered/used by static analyzes. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_GR_FUNCTIONSUMMARY_H +#define LLVM_CLANG_GR_FUNCTIONSUMMARY_H + +#include "clang/AST/Decl.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/BitVector.h" + +namespace clang { +namespace ento { +typedef llvm::SmallPtrSet<const Decl*,24> SetOfDecls; + +class FunctionSummariesTy { + struct FunctionSummary { + /// True if this function has reached a max block count while inlined from + /// at least one call site. + bool MayReachMaxBlockCount; + + /// Total number of blocks in the function. + unsigned TotalBasicBlocks; + + /// Marks the IDs of the basic blocks visited during the analyzes. + llvm::BitVector VisitedBasicBlocks; + + FunctionSummary() : + MayReachMaxBlockCount(false), + TotalBasicBlocks(0), + VisitedBasicBlocks(0) {} + }; + + typedef llvm::DenseMap<const Decl*, FunctionSummary*> MapTy; + MapTy Map; + +public: + ~FunctionSummariesTy(); + + MapTy::iterator findOrInsertSummary(const Decl *D) { + MapTy::iterator I = Map.find(D); + if (I != Map.end()) + return I; + FunctionSummary *DS = new FunctionSummary(); + I = Map.insert(std::pair<const Decl*, FunctionSummary*>(D, DS)).first; + assert(I != Map.end()); + return I; + } + + void markReachedMaxBlockCount(const Decl* D) { + MapTy::iterator I = findOrInsertSummary(D); + I->second->MayReachMaxBlockCount = true; + } + + bool hasReachedMaxBlockCount(const Decl* D) { + MapTy::const_iterator I = Map.find(D); + if (I != Map.end()) + return I->second->MayReachMaxBlockCount; + return false; + } + + void markVisitedBasicBlock(unsigned ID, const Decl* D, unsigned TotalIDs) { + MapTy::iterator I = findOrInsertSummary(D); + llvm::BitVector &Blocks = I->second->VisitedBasicBlocks; + assert(ID < TotalIDs); + if (TotalIDs > Blocks.size()) { + Blocks.resize(TotalIDs); + I->second->TotalBasicBlocks = TotalIDs; + } + Blocks[ID] = true; + } + + unsigned getNumVisitedBasicBlocks(const Decl* D) { + MapTy::const_iterator I = Map.find(D); + if (I != Map.end()) + return I->second->VisitedBasicBlocks.count(); + return 0; + } + + unsigned getTotalNumBasicBlocks(); + unsigned getTotalNumVisitedBasicBlocks(); +}; + +}} // end clang ento namespaces + +#endif diff --git a/clang/lib/StaticAnalyzer/Core/CMakeLists.txt b/clang/lib/StaticAnalyzer/Core/CMakeLists.txt index 216e94a395e..1ea25bd01ba 100644 --- a/clang/lib/StaticAnalyzer/Core/CMakeLists.txt +++ b/clang/lib/StaticAnalyzer/Core/CMakeLists.txt @@ -22,6 +22,7 @@ add_clang_library(clangStaticAnalyzerCore ExprEngineCXX.cpp ExprEngineCallAndReturn.cpp ExprEngineObjC.cpp + FunctionSummary.cpp HTMLDiagnostics.cpp MemRegion.cpp ObjCMessage.cpp diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp index de94f0f2ddc..eb986afa3db 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -174,6 +174,11 @@ bool CoreEngine::ExecuteWorkList(const LocationContext *L, unsigned Steps, assert (Entry->succ_size() == 1 && "Entry block must have 1 successor."); + // Mark the entry block as visited. + FunctionSummaries->markVisitedBasicBlock(Entry->getBlockID(), + L->getDecl(), + L->getCFG()->getNumBlockIDs()); + // Get the solitary successor. const CFGBlock *Succ = *(Entry->succ_begin()); @@ -280,6 +285,12 @@ void CoreEngine::HandleBlockEdge(const BlockEdge &L, ExplodedNode *Pred) { const CFGBlock *Blk = L.getDst(); NodeBuilderContext BuilderCtx(*this, Blk, Pred); + // Mark this block as visited. + const LocationContext *LC = Pred->getLocationContext(); + FunctionSummaries->markVisitedBasicBlock(Blk->getBlockID(), + LC->getDecl(), + LC->getCFG()->getNumBlockIDs()); + // Check if we are entering the EXIT block. if (Blk == &(L.getLocationContext()->getCFG()->getExit())) { @@ -312,10 +323,11 @@ void CoreEngine::HandleBlockEntrance(const BlockEntrance &L, ExplodedNode *Pred) { // Increment the block counter. + const LocationContext *LC = Pred->getLocationContext(); + unsigned BlockId = L.getBlock()->getBlockID(); BlockCounter Counter = WList->getBlockCounter(); - Counter = BCounterFactory.IncrementCount(Counter, - Pred->getLocationContext()->getCurrentStackFrame(), - L.getBlock()->getBlockID()); + Counter = BCounterFactory.IncrementCount(Counter, LC->getCurrentStackFrame(), + BlockId); WList->setBlockCounter(Counter); // Process the entrance of the block. diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp index 35c751a89de..70921c5a7cb 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngine.cpp @@ -71,7 +71,7 @@ ExprEngine::ExprEngine(AnalysisManager &mgr, bool gcEnabled, FunctionSummariesTy *FS) : AMgr(mgr), AnalysisDeclContexts(mgr.getAnalysisDeclContextManager()), - Engine(*this, VisitedCallees), + Engine(*this, VisitedCallees, FS), G(Engine.getGraph()), StateMgr(getContext(), mgr.getStoreManagerCreator(), mgr.getConstraintManagerCreator(), G.getAllocator(), @@ -82,7 +82,7 @@ ExprEngine::ExprEngine(AnalysisManager &mgr, bool gcEnabled, currentStmt(NULL), currentStmtIdx(0), currentBuilderContext(0), NSExceptionII(NULL), NSExceptionInstanceRaiseSelectors(NULL), RaiseSel(GetNullarySelector("raise", getContext())), - ObjCGCEnabled(gcEnabled), BR(mgr, *this), FunctionSummaries(FS) { + ObjCGCEnabled(gcEnabled), BR(mgr, *this) { if (mgr.shouldEagerlyTrimExplodedGraph()) { // Enable eager node reclaimation when constructing the ExplodedGraph. @@ -1051,7 +1051,7 @@ void ExprEngine::processCFGBlockEntrance(const BlockEdge &L, const LocationContext *RootLC = (*G.roots_begin())->getLocation().getLocationContext(); if (RootLC->getCurrentStackFrame() != CalleeSF) { - FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl()); + Engine.FunctionSummaries->markReachedMaxBlockCount(CalleeSF->getDecl()); // Re-run the call evaluation without inlining it, by storing the // no-inlining policy in the state and enqueuing the new work item on diff --git a/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp b/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp index 272f13eb6b0..b99bd5441e4 100644 --- a/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp +++ b/clang/lib/StaticAnalyzer/Core/ExprEngineCallAndReturn.cpp @@ -138,7 +138,7 @@ bool ExprEngine::shouldInlineDecl(const FunctionDecl *FD, ExplodedNode *Pred) { == AMgr.InlineMaxStackDepth) return false; - if (FunctionSummaries->hasReachedMaxBlockCount(FD)) + if (Engine.FunctionSummaries->hasReachedMaxBlockCount(FD)) return false; if (CalleeCFG->getNumBlockIDs() > AMgr.InlineMaxFunctionSize) diff --git a/clang/lib/StaticAnalyzer/Core/FunctionSummary.cpp b/clang/lib/StaticAnalyzer/Core/FunctionSummary.cpp new file mode 100644 index 00000000000..c227aac2b4c --- /dev/null +++ b/clang/lib/StaticAnalyzer/Core/FunctionSummary.cpp @@ -0,0 +1,38 @@ +//== FunctionSummary.h - Stores summaries of functions. ------------*- 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 summary of a function gathered/used by static analyzes. +// +//===----------------------------------------------------------------------===// + +#include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h" +using namespace clang; +using namespace ento; + +FunctionSummariesTy::~FunctionSummariesTy() { + for (MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I) { + delete(I->second); + } +} + +unsigned FunctionSummariesTy::getTotalNumBasicBlocks() { + unsigned Total = 0; + for (MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I) { + Total += I->second->TotalBasicBlocks; + } + return Total; +} + +unsigned FunctionSummariesTy::getTotalNumVisitedBasicBlocks() { + unsigned Total = 0; + for (MapTy::iterator I = Map.begin(), E = Map.end(); I != E; ++I) { + Total += I->second->VisitedBasicBlocks.count(); + } + return Total; +} diff --git a/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp b/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp index 3b9deda2bac..df2d265cad0 100644 --- a/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp +++ b/clang/lib/StaticAnalyzer/Frontend/AnalysisConsumer.cpp @@ -53,6 +53,9 @@ static ExplodedNode::Auditor* CreateUbiViz(); STATISTIC(NumFunctionTopLevel, "The # of functions at top level."); STATISTIC(NumFunctionsAnalyzed, "The # of functions analysed (as top level)."); +STATISTIC(NumBlocksInAnalyzedFunctions, + "The # of basic blocks in the analyzed functions."); +STATISTIC(PercentReachableBlocks, "The % of reachable basic blocks."); //===----------------------------------------------------------------------===// // Special PathDiagnosticConsumers. @@ -122,6 +125,13 @@ public: } ~AnalysisConsumer() { + // Count how many basic blocks we have not covered. + NumBlocksInAnalyzedFunctions = FunctionSummaries.getTotalNumBasicBlocks(); + if (NumBlocksInAnalyzedFunctions > 0) + PercentReachableBlocks = + (FunctionSummaries.getTotalNumVisitedBasicBlocks() * 100) / + NumBlocksInAnalyzedFunctions; + if (Opts.PrintStats) delete TUTotalTimer; } diff --git a/clang/test/Analysis/stats.c b/clang/test/Analysis/stats.c index 8ba812193c2..6beadbeb412 100644 --- a/clang/test/Analysis/stats.c +++ b/clang/test/Analysis/stats.c @@ -4,4 +4,5 @@ void foo() { int x; } // CHECK: ... Statistics Collected ... +// CHECK:100 AnalysisConsumer - The % of reachable basic blocks. // CHECK:The # of times RemoveDeadBindings is called |
