From 6dcbc1dbb387cf465090cffece6fccc1564233ab Mon Sep 17 00:00:00 2001 From: George Karpenkov Date: Mon, 26 Feb 2018 22:14:18 +0000 Subject: [PATCH] [analyzer] Exploration strategy prioritizing unexplored nodes first See D42775 for discussion. Turns out, just exploring nodes which weren't explored first is not quite enough, as e.g. the first quick traversal resulting in a report can mark everything as "visited", and then subsequent traversals of the same region will get all the pitfalls of DFS. Priority queue-based approach in comparison shows much greater increase in coverage and even performance, without sacrificing memory. Differential Revision: https://reviews.llvm.org/D43354 llvm-svn: 326136 --- .../clang/StaticAnalyzer/Core/AnalyzerOptions.h | 1 + .../StaticAnalyzer/Core/PathSensitive/WorkList.h | 1 + clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp | 2 + clang/lib/StaticAnalyzer/Core/CoreEngine.cpp | 64 ++++++++++++++++++++++ .../exploration_order/prefer_unexplored.cc | 1 + 5 files changed, 69 insertions(+) diff --git a/clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h b/clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h index 04d3d99..30c3fb3 100644 --- a/clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h +++ b/clang/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h @@ -192,6 +192,7 @@ public: DFS, BFS, UnexploredFirst, + UnexploredFirstQueue, BFSBlockDFSContents, NotSet }; diff --git a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h index cc2b6af..3169791 100644 --- a/clang/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h +++ b/clang/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h @@ -84,6 +84,7 @@ public: static std::unique_ptr makeBFS(); static std::unique_ptr makeBFSBlockDFSContents(); static std::unique_ptr makeUnexploredFirst(); + static std::unique_ptr makeUnexploredFirstPriorityQueue(); }; } // end GR namespace diff --git a/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp b/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp index 49533d4..c01e531 100644 --- a/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp +++ b/clang/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp @@ -68,6 +68,8 @@ AnalyzerOptions::getExplorationStrategy() { .Case("bfs", ExplorationStrategyKind::BFS) .Case("unexplored_first", ExplorationStrategyKind::UnexploredFirst) + .Case("unexplored_first_queue", + ExplorationStrategyKind::UnexploredFirstQueue) .Case("bfs_block_dfs_contents", ExplorationStrategyKind::BFSBlockDFSContents) .Default(ExplorationStrategyKind::NotSet); diff --git a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp index 16a7a76..efc83c3 100644 --- a/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp +++ b/clang/lib/StaticAnalyzer/Core/CoreEngine.cpp @@ -20,7 +20,9 @@ #include "clang/StaticAnalyzer/Core/PathSensitive/ExprEngine.h" #include "llvm/ADT/Statistic.h" #include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/DenseMap.h" #include "llvm/Support/Casting.h" +#include "llvm/ADT/PriorityQueue.h" using namespace clang; using namespace ento; @@ -192,6 +194,66 @@ std::unique_ptr WorkList::makeUnexploredFirst() { return llvm::make_unique(); } +class UnexploredFirstPriorityQueue : public WorkList { + typedef unsigned BlockID; + typedef std::pair LocIdentifier; + + // How many times each location was visited. + // Is signed because we negate it later in order to have a reversed + // comparison. + typedef llvm::DenseMap VisitedTimesMap; + + // Compare by number of times the location was visited first (negated + // to prefer less often visited locations), then by insertion time (prefer + // expanding nodes inserted sooner first). + typedef std::pair QueuePriority; + typedef std::pair QueueItem; + + struct ExplorationComparator { + bool operator() (const QueueItem &LHS, const QueueItem &RHS) { + return LHS.second < RHS.second; + } + }; + + // Number of inserted nodes, used to emulate DFS ordering in the priority + // queue when insertions are equal. + unsigned long Counter = 0; + + // Number of times a current location was reached. + VisitedTimesMap NumReached; + + // The top item is the largest one. + llvm::PriorityQueue, ExplorationComparator> + queue; + +public: + bool hasWork() const override { + return !queue.empty(); + } + + void enqueue(const WorkListUnit &U) override { + const ExplodedNode *N = U.getNode(); + unsigned NumVisited = 0; + if (auto BE = N->getLocation().getAs()) { + LocIdentifier LocId = std::make_pair( + BE->getBlock()->getBlockID(), N->getStackFrame()); + NumVisited = NumReached[LocId]++; + } + + queue.push(std::make_pair(U, std::make_pair(-NumVisited, ++Counter))); + } + + WorkListUnit dequeue() override { + QueueItem U = queue.top(); + queue.pop(); + return U.first; + } +}; + +std::unique_ptr WorkList::makeUnexploredFirstPriorityQueue() { + return llvm::make_unique(); +} + //===----------------------------------------------------------------------===// // Core analysis engine. //===----------------------------------------------------------------------===// @@ -206,6 +268,8 @@ static std::unique_ptr generateWorkList(AnalyzerOptions &Opts) { return WorkList::makeBFSBlockDFSContents(); case AnalyzerOptions::ExplorationStrategyKind::UnexploredFirst: return WorkList::makeUnexploredFirst(); + case AnalyzerOptions::ExplorationStrategyKind::UnexploredFirstQueue: + return WorkList::makeUnexploredFirstPriorityQueue(); default: llvm_unreachable("Unexpected case"); } diff --git a/clang/test/Analysis/exploration_order/prefer_unexplored.cc b/clang/test/Analysis/exploration_order/prefer_unexplored.cc index e9f25ed..317b88a 100644 --- a/clang/test/Analysis/exploration_order/prefer_unexplored.cc +++ b/clang/test/Analysis/exploration_order/prefer_unexplored.cc @@ -1,4 +1,5 @@ // RUN: %clang_analyze_cc1 -w -analyzer-checker=core -analyzer-config exploration_strategy=unexplored_first -analyzer-output=text -verify %s | FileCheck %s +// RUN: %clang_analyze_cc1 -w -analyzer-checker=core -analyzer-config exploration_strategy=unexplored_first_queue -analyzer-output=text -verify %s | FileCheck %s extern int coin(); -- 2.7.4