152d861ce41ce84d8389495ea78d97bcc962ac5baTom Care//==--AnalyzerStatsChecker.cpp - Analyzer visitation statistics --*- C++ -*-==// 252d861ce41ce84d8389495ea78d97bcc962ac5baTom Care// 352d861ce41ce84d8389495ea78d97bcc962ac5baTom Care// The LLVM Compiler Infrastructure 452d861ce41ce84d8389495ea78d97bcc962ac5baTom Care// 552d861ce41ce84d8389495ea78d97bcc962ac5baTom Care// This file is distributed under the University of Illinois Open Source 652d861ce41ce84d8389495ea78d97bcc962ac5baTom Care// License. See LICENSE.TXT for details. 752d861ce41ce84d8389495ea78d97bcc962ac5baTom Care// 852d861ce41ce84d8389495ea78d97bcc962ac5baTom Care//===----------------------------------------------------------------------===// 952d861ce41ce84d8389495ea78d97bcc962ac5baTom Care// This file reports various statistics about analyzer visitation. 1052d861ce41ce84d8389495ea78d97bcc962ac5baTom Care//===----------------------------------------------------------------------===// 1158f2e7c3c3860e410fa3d8252862ef10be7cdc70Argyrios Kyrtzidis#include "ClangSACheckers.h" 1255fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/AST/DeclObjC.h" 1355fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/Basic/SourceManager.h" 1455fc873017f10f6f566b182b70f6fc22aefa3464Chandler Carruth#include "clang/StaticAnalyzer/Core/BugReporter/BugReporter.h" 15ec8605f1d7ec846dbf51047bfd5c56d32d1ff91cArgyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/Checker.h" 1658f2e7c3c3860e410fa3d8252862ef10be7cdc70Argyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/CheckerManager.h" 179b663716449b618ba0390b1dbebc54fa8e971124Ted Kremenek#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" 1858f2e7c3c3860e410fa3d8252862ef10be7cdc70Argyrios Kyrtzidis#include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" 1952d861ce41ce84d8389495ea78d97bcc962ac5baTom Care#include "llvm/ADT/SmallPtrSet.h" 208fe83e1df954d72c0f4ffc15d20a5222ec151c21Benjamin Kramer#include "llvm/ADT/SmallString.h" 21749bbe6f5f23676244f12a0d41511c8e73516febAnna Zaks#include "llvm/ADT/Statistic.h" 22a93d0f280693b8418bc88cf7a8c93325f7fcf4c6Benjamin Kramer#include "llvm/Support/raw_ostream.h" 2352d861ce41ce84d8389495ea78d97bcc962ac5baTom Care 2452d861ce41ce84d8389495ea78d97bcc962ac5baTom Careusing namespace clang; 259ef6537a894c33003359b1f9b9676e9178e028b7Ted Kremenekusing namespace ento; 2652d861ce41ce84d8389495ea78d97bcc962ac5baTom Care 276bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines#define DEBUG_TYPE "StatsChecker" 286bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines 29749bbe6f5f23676244f12a0d41511c8e73516febAnna ZaksSTATISTIC(NumBlocks, 30749bbe6f5f23676244f12a0d41511c8e73516febAnna Zaks "The # of blocks in top level functions"); 31749bbe6f5f23676244f12a0d41511c8e73516febAnna ZaksSTATISTIC(NumBlocksUnreachable, 32749bbe6f5f23676244f12a0d41511c8e73516febAnna Zaks "The # of unreachable blocks in analyzing top level functions"); 33749bbe6f5f23676244f12a0d41511c8e73516febAnna Zaks 3452d861ce41ce84d8389495ea78d97bcc962ac5baTom Carenamespace { 35ec8605f1d7ec846dbf51047bfd5c56d32d1ff91cArgyrios Kyrtzidisclass AnalyzerStatsChecker : public Checker<check::EndAnalysis> { 3652d861ce41ce84d8389495ea78d97bcc962ac5baTom Carepublic: 3758f2e7c3c3860e410fa3d8252862ef10be7cdc70Argyrios Kyrtzidis void checkEndAnalysis(ExplodedGraph &G, BugReporter &B,ExprEngine &Eng) const; 3852d861ce41ce84d8389495ea78d97bcc962ac5baTom Care}; 3952d861ce41ce84d8389495ea78d97bcc962ac5baTom Care} 4052d861ce41ce84d8389495ea78d97bcc962ac5baTom Care 4158f2e7c3c3860e410fa3d8252862ef10be7cdc70Argyrios Kyrtzidisvoid AnalyzerStatsChecker::checkEndAnalysis(ExplodedGraph &G, 4252d861ce41ce84d8389495ea78d97bcc962ac5baTom Care BugReporter &B, 4358f2e7c3c3860e410fa3d8252862ef10be7cdc70Argyrios Kyrtzidis ExprEngine &Eng) const { 446bcf27bb9a4b5c3f79cb44c0e4654a6d7619ad89Stephen Hines const CFG *C = nullptr; 4552d861ce41ce84d8389495ea78d97bcc962ac5baTom Care const SourceManager &SM = B.getSourceManager(); 4658f2e7c3c3860e410fa3d8252862ef10be7cdc70Argyrios Kyrtzidis llvm::SmallPtrSet<const CFGBlock*, 256> reachable; 4752d861ce41ce84d8389495ea78d97bcc962ac5baTom Care 4864394e2cc57d597eafe980bd94b060e2967a1cbdAnna Zaks // Root node should have the location context of the top most function. 4964394e2cc57d597eafe980bd94b060e2967a1cbdAnna Zaks const ExplodedNode *GraphRoot = *G.roots_begin(); 5064ee9d03c9fa0e9f4b944300167f871d9a65a991Anna Zaks const LocationContext *LC = GraphRoot->getLocation().getLocationContext(); 5164ee9d03c9fa0e9f4b944300167f871d9a65a991Anna Zaks 5264ee9d03c9fa0e9f4b944300167f871d9a65a991Anna Zaks const Decl *D = LC->getDecl(); 5364394e2cc57d597eafe980bd94b060e2967a1cbdAnna Zaks 5464394e2cc57d597eafe980bd94b060e2967a1cbdAnna Zaks // Iterate over the exploded graph. 5552d861ce41ce84d8389495ea78d97bcc962ac5baTom Care for (ExplodedGraph::node_iterator I = G.nodes_begin(); 5652d861ce41ce84d8389495ea78d97bcc962ac5baTom Care I != G.nodes_end(); ++I) { 5752d861ce41ce84d8389495ea78d97bcc962ac5baTom Care const ProgramPoint &P = I->getLocation(); 5864394e2cc57d597eafe980bd94b060e2967a1cbdAnna Zaks 5964ee9d03c9fa0e9f4b944300167f871d9a65a991Anna Zaks // Only check the coverage in the top level function (optimization). 6064ee9d03c9fa0e9f4b944300167f871d9a65a991Anna Zaks if (D != P.getLocationContext()->getDecl()) 6164394e2cc57d597eafe980bd94b060e2967a1cbdAnna Zaks continue; 6252d861ce41ce84d8389495ea78d97bcc962ac5baTom Care 637a95de68c093991047ed8d339479ccad51b88663David Blaikie if (Optional<BlockEntrance> BE = P.getAs<BlockEntrance>()) { 642cb5520f62e52f09175f546af12b8b8fb05b81adTom Care const CFGBlock *CB = BE->getBlock(); 6552d861ce41ce84d8389495ea78d97bcc962ac5baTom Care reachable.insert(CB); 6652d861ce41ce84d8389495ea78d97bcc962ac5baTom Care } 6752d861ce41ce84d8389495ea78d97bcc962ac5baTom Care } 6852d861ce41ce84d8389495ea78d97bcc962ac5baTom Care 6964ee9d03c9fa0e9f4b944300167f871d9a65a991Anna Zaks // Get the CFG and the Decl of this block. 7052d861ce41ce84d8389495ea78d97bcc962ac5baTom Care C = LC->getCFG(); 7152d861ce41ce84d8389495ea78d97bcc962ac5baTom Care 7252d861ce41ce84d8389495ea78d97bcc962ac5baTom Care unsigned total = 0, unreachable = 0; 7352d861ce41ce84d8389495ea78d97bcc962ac5baTom Care 7452d861ce41ce84d8389495ea78d97bcc962ac5baTom Care // Find CFGBlocks that were not covered by any node 7552d861ce41ce84d8389495ea78d97bcc962ac5baTom Care for (CFG::const_iterator I = C->begin(); I != C->end(); ++I) { 7652d861ce41ce84d8389495ea78d97bcc962ac5baTom Care const CFGBlock *CB = *I; 7752d861ce41ce84d8389495ea78d97bcc962ac5baTom Care ++total; 7852d861ce41ce84d8389495ea78d97bcc962ac5baTom Care // Check if the block is unreachable 7952d861ce41ce84d8389495ea78d97bcc962ac5baTom Care if (!reachable.count(CB)) { 8052d861ce41ce84d8389495ea78d97bcc962ac5baTom Care ++unreachable; 8152d861ce41ce84d8389495ea78d97bcc962ac5baTom Care } 8252d861ce41ce84d8389495ea78d97bcc962ac5baTom Care } 8352d861ce41ce84d8389495ea78d97bcc962ac5baTom Care 8452d861ce41ce84d8389495ea78d97bcc962ac5baTom Care // We never 'reach' the entry block, so correct the unreachable count 8552d861ce41ce84d8389495ea78d97bcc962ac5baTom Care unreachable--; 8664394e2cc57d597eafe980bd94b060e2967a1cbdAnna Zaks // There is no BlockEntrance corresponding to the exit block as well, so 8764394e2cc57d597eafe980bd94b060e2967a1cbdAnna Zaks // assume it is reached as well. 8864394e2cc57d597eafe980bd94b060e2967a1cbdAnna Zaks unreachable--; 8952d861ce41ce84d8389495ea78d97bcc962ac5baTom Care 9052d861ce41ce84d8389495ea78d97bcc962ac5baTom Care // Generate the warning string 91f7ccbad5d9949e7ddd1cbef43d482553b811e026Dylan Noblesmith SmallString<128> buf; 9252d861ce41ce84d8389495ea78d97bcc962ac5baTom Care llvm::raw_svector_ostream output(buf); 9352d861ce41ce84d8389495ea78d97bcc962ac5baTom Care PresumedLoc Loc = SM.getPresumedLoc(D->getLocation()); 9465552ca127ac5d9b767c5f0b09d86e17cb3e9e5eAnna Zaks if (!Loc.isValid()) 9565552ca127ac5d9b767c5f0b09d86e17cb3e9e5eAnna Zaks return; 9652d861ce41ce84d8389495ea78d97bcc962ac5baTom Care 9765552ca127ac5d9b767c5f0b09d86e17cb3e9e5eAnna Zaks if (isa<FunctionDecl>(D) || isa<ObjCMethodDecl>(D)) { 9865552ca127ac5d9b767c5f0b09d86e17cb3e9e5eAnna Zaks const NamedDecl *ND = cast<NamedDecl>(D); 9965552ca127ac5d9b767c5f0b09d86e17cb3e9e5eAnna Zaks output << *ND; 10065552ca127ac5d9b767c5f0b09d86e17cb3e9e5eAnna Zaks } 10165552ca127ac5d9b767c5f0b09d86e17cb3e9e5eAnna Zaks else if (isa<BlockDecl>(D)) { 10265552ca127ac5d9b767c5f0b09d86e17cb3e9e5eAnna Zaks output << "block(line:" << Loc.getLine() << ":col:" << Loc.getColumn(); 10352d861ce41ce84d8389495ea78d97bcc962ac5baTom Care } 104cb7b1e17b63967317ab5cc55682168cf0380519aDouglas Gregor 105749bbe6f5f23676244f12a0d41511c8e73516febAnna Zaks NumBlocksUnreachable += unreachable; 106749bbe6f5f23676244f12a0d41511c8e73516febAnna Zaks NumBlocks += total; 10765552ca127ac5d9b767c5f0b09d86e17cb3e9e5eAnna Zaks std::string NameOfRootFunction = output.str(); 108749bbe6f5f23676244f12a0d41511c8e73516febAnna Zaks 10952d861ce41ce84d8389495ea78d97bcc962ac5baTom Care output << " -> Total CFGBlocks: " << total << " | Unreachable CFGBlocks: " 110422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek << unreachable << " | Exhausted Block: " 111422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek << (Eng.wasBlocksExhausted() ? "yes" : "no") 11252d861ce41ce84d8389495ea78d97bcc962ac5baTom Care << " | Empty WorkList: " 1130e1cd944398c9e9a3d4c0cf5273a126be91830e8Tom Care << (Eng.hasEmptyWorkList() ? "yes" : "no"); 11452d861ce41ce84d8389495ea78d97bcc962ac5baTom Care 115651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines B.EmitBasicReport(D, this, "Analyzer Statistics", "Internal Statistics", 11607189521a15d9c088216b943649cb9fe231cbb57Ted Kremenek output.str(), PathDiagnosticLocation(D, SM)); 1172cb5520f62e52f09175f546af12b8b8fb05b81adTom Care 11865552ca127ac5d9b767c5f0b09d86e17cb3e9e5eAnna Zaks // Emit warning for each block we bailed out on. 119422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek typedef CoreEngine::BlocksExhausted::const_iterator ExhaustedIterator; 120d2592a34a059e7cbb2b11dc53649ac4912422909Argyrios Kyrtzidis const CoreEngine &CE = Eng.getCoreEngine(); 121422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek for (ExhaustedIterator I = CE.blocks_exhausted_begin(), 122422ab7a49a9a4252dbc6350e49d7a5708337b9c7Ted Kremenek E = CE.blocks_exhausted_end(); I != E; ++I) { 1232cb5520f62e52f09175f546af12b8b8fb05b81adTom Care const BlockEdge &BE = I->first; 1242cb5520f62e52f09175f546af12b8b8fb05b81adTom Care const CFGBlock *Exit = BE.getDst(); 1252cb5520f62e52f09175f546af12b8b8fb05b81adTom Care const CFGElement &CE = Exit->front(); 126b07805485c603be3d8011f72611465324c9e664bDavid Blaikie if (Optional<CFGStmt> CS = CE.getAs<CFGStmt>()) { 12765552ca127ac5d9b767c5f0b09d86e17cb3e9e5eAnna Zaks SmallString<128> bufI; 12865552ca127ac5d9b767c5f0b09d86e17cb3e9e5eAnna Zaks llvm::raw_svector_ostream outputI(bufI); 12965552ca127ac5d9b767c5f0b09d86e17cb3e9e5eAnna Zaks outputI << "(" << NameOfRootFunction << ")" << 13065552ca127ac5d9b767c5f0b09d86e17cb3e9e5eAnna Zaks ": The analyzer generated a sink at this point"; 131b07805485c603be3d8011f72611465324c9e664bDavid Blaikie B.EmitBasicReport( 132651f13cea278ec967336033dd032faef0e9fc2ecStephen Hines D, this, "Sink Point", "Internal Statistics", outputI.str(), 133b07805485c603be3d8011f72611465324c9e664bDavid Blaikie PathDiagnosticLocation::createBegin(CS->getStmt(), SM, LC)); 13465552ca127ac5d9b767c5f0b09d86e17cb3e9e5eAnna Zaks } 1352cb5520f62e52f09175f546af12b8b8fb05b81adTom Care } 13652d861ce41ce84d8389495ea78d97bcc962ac5baTom Care} 13758f2e7c3c3860e410fa3d8252862ef10be7cdc70Argyrios Kyrtzidis 13858f2e7c3c3860e410fa3d8252862ef10be7cdc70Argyrios Kyrtzidisvoid ento::registerAnalyzerStatsChecker(CheckerManager &mgr) { 13958f2e7c3c3860e410fa3d8252862ef10be7cdc70Argyrios Kyrtzidis mgr.registerChecker<AnalyzerStatsChecker>(); 14058f2e7c3c3860e410fa3d8252862ef10be7cdc70Argyrios Kyrtzidis} 141