Author: george.karpenkov Date: Thu Oct 11 15:59:59 2018 New Revision: 344313
URL: http://llvm.org/viewvc/llvm-project?rev=344313&view=rev Log: [analyzer] Experiment with an iteration order only based on location, and not using the stack frame Differential Revision: https://reviews.llvm.org/D53058 Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp cfe/trunk/lib/StaticAnalyzer/Core/CoreEngine.cpp cfe/trunk/lib/StaticAnalyzer/Core/WorkList.cpp Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h?rev=344313&r1=344312&r2=344313&view=diff ============================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h (original) +++ cfe/trunk/include/clang/StaticAnalyzer/Core/AnalyzerOptions.h Thu Oct 11 15:59:59 2018 @@ -186,6 +186,7 @@ public: BFS, UnexploredFirst, UnexploredFirstQueue, + UnexploredFirstLocationQueue, BFSBlockDFSContents, NotSet }; Modified: cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h?rev=344313&r1=344312&r2=344313&view=diff ============================================================================== --- cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h (original) +++ cfe/trunk/include/clang/StaticAnalyzer/Core/PathSensitive/WorkList.h Thu Oct 11 15:59:59 2018 @@ -85,6 +85,7 @@ public: static std::unique_ptr<WorkList> makeBFSBlockDFSContents(); static std::unique_ptr<WorkList> makeUnexploredFirst(); static std::unique_ptr<WorkList> makeUnexploredFirstPriorityQueue(); + static std::unique_ptr<WorkList> makeUnexploredFirstPriorityLocationQueue(); }; } // end ento namespace Modified: cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp?rev=344313&r1=344312&r2=344313&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/AnalyzerOptions.cpp Thu Oct 11 15:59:59 2018 @@ -77,6 +77,8 @@ AnalyzerOptions::getExplorationStrategy( ExplorationStrategyKind::UnexploredFirst) .Case("unexplored_first_queue", ExplorationStrategyKind::UnexploredFirstQueue) + .Case("unexplored_first_location_queue", + ExplorationStrategyKind::UnexploredFirstLocationQueue) .Case("bfs_block_dfs_contents", ExplorationStrategyKind::BFSBlockDFSContents) .Default(ExplorationStrategyKind::NotSet); Modified: cfe/trunk/lib/StaticAnalyzer/Core/CoreEngine.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/CoreEngine.cpp?rev=344313&r1=344312&r2=344313&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/CoreEngine.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/CoreEngine.cpp Thu Oct 11 15:59:59 2018 @@ -53,7 +53,8 @@ STATISTIC(NumPathsExplored, // Core analysis engine. //===----------------------------------------------------------------------===// -static std::unique_ptr<WorkList> generateWorkList(AnalyzerOptions &Opts) { +static std::unique_ptr<WorkList> generateWorkList(AnalyzerOptions &Opts, + SubEngine &subengine) { switch (Opts.getExplorationStrategy()) { case AnalyzerOptions::ExplorationStrategyKind::DFS: return WorkList::makeDFS(); @@ -65,6 +66,8 @@ static std::unique_ptr<WorkList> generat return WorkList::makeUnexploredFirst(); case AnalyzerOptions::ExplorationStrategyKind::UnexploredFirstQueue: return WorkList::makeUnexploredFirstPriorityQueue(); + case AnalyzerOptions::ExplorationStrategyKind::UnexploredFirstLocationQueue: + return WorkList::makeUnexploredFirstPriorityLocationQueue(); default: llvm_unreachable("Unexpected case"); } @@ -72,7 +75,7 @@ static std::unique_ptr<WorkList> generat CoreEngine::CoreEngine(SubEngine &subengine, FunctionSummariesTy *FS, AnalyzerOptions &Opts) - : SubEng(subengine), WList(generateWorkList(Opts)), + : SubEng(subengine), WList(generateWorkList(Opts, subengine)), BCounterFactory(G.getAllocator()), FunctionSummaries(FS) {} /// ExecuteWorkList - Run the worklist algorithm for a maximum number of steps. Modified: cfe/trunk/lib/StaticAnalyzer/Core/WorkList.cpp URL: http://llvm.org/viewvc/llvm-project/cfe/trunk/lib/StaticAnalyzer/Core/WorkList.cpp?rev=344313&r1=344312&r2=344313&view=diff ============================================================================== --- cfe/trunk/lib/StaticAnalyzer/Core/WorkList.cpp (original) +++ cfe/trunk/lib/StaticAnalyzer/Core/WorkList.cpp Thu Oct 11 15:59:59 2018 @@ -252,3 +252,63 @@ public: std::unique_ptr<WorkList> WorkList::makeUnexploredFirstPriorityQueue() { return llvm::make_unique<UnexploredFirstPriorityQueue>(); } + +namespace { +class UnexploredFirstPriorityLocationQueue : public WorkList { + using LocIdentifier = int; + + // How many times each location was visited. + // Is signed because we negate it later in order to have a reversed + // comparison. + using VisitedTimesMap = llvm::DenseMap<LocIdentifier, int>; + + // 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). + using QueuePriority = std::pair<int, unsigned long>; + using QueueItem = std::pair<WorkListUnit, QueuePriority>; + + 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<QueueItem, std::vector<QueueItem>, 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<BlockEntrance>()) + NumVisited = NumReached[BE->getBlock()->getBlockID()]++; + + 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> WorkList::makeUnexploredFirstPriorityLocationQueue() { + return llvm::make_unique<UnexploredFirstPriorityLocationQueue>(); +} _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
