This is an archive of the discontinued LLVM Phabricator instance.

Differential D44759

[analyzer] [NFC] Move worklist implementation to WorkList.cpp
ClosedPublic

Authored by george.karpenkov on Mar 21 2018, 4:03 PM.

Details

Reviewers
dcoughlin
NoQ
Commits
rG40b42a3ad825: [analyzer] [NFC] Move worklist implementation to WorkList.cpp
rC328280: [analyzer] [NFC] Move worklist implementation to WorkList.cpp
rL328280: [analyzer] [NFC] Move worklist implementation to WorkList.cpp
Summary

Current location is very confusing, especially because there is already WorkList.h, and other code in CoreEngine.cpp is not related to work list implementation.

Diff Detail

Repository
rL LLVM

Event Timeline

george.karpenkov created this revision.Mar 21 2018, 4:03 PM
Herald added subscribers: a.sidorin, szepet, xazax.hun, mgorny. · View Herald TranscriptMar 21 2018, 4:03 PM
NoQ accepted this revision.Mar 21 2018, 5:16 PM
This revision is now accepted and ready to land.Mar 21 2018, 5:16 PM
Closed by commit rL328280: [analyzer] [NFC] Move worklist implementation to WorkList.cpp (authored by george.karpenkov). · Explain WhyMar 22 2018, 5:18 PM
This revision was automatically updated to reflect the committed changes.
Herald added a subscriber: llvm-commits. · View Herald TranscriptMar 22 2018, 5:18 PM

Revision Contents

PathSize
cfe/
trunk/
lib/
StaticAnalyzer/
Core/
1 line
230 lines
252 lines

Diff 139536

cfe/trunk/lib/StaticAnalyzer/Core/CMakeLists.txt

Show First 20 Lines • Show All 45 Lines • ▼ Show 20 Linesadd_clang_library(clangStaticAnalyzerCore
RegionStore.cpp RegionStore.cpp
SValBuilder.cpp SValBuilder.cpp
SVals.cpp SVals.cpp
SimpleConstraintManager.cpp SimpleConstraintManager.cpp
SimpleSValBuilder.cpp SimpleSValBuilder.cpp
Store.cpp Store.cpp
SubEngine.cpp SubEngine.cpp
SymbolManager.cpp SymbolManager.cpp
WorkList.cpp
Z3ConstraintManager.cpp Z3ConstraintManager.cpp
LINK_LIBS LINK_LIBS
clangAST clangAST
clangASTMatchers clangASTMatchers
clangAnalysis clangAnalysis
clangBasic clangBasic
clangCrossTU clangCrossTU
Show All 11 Lines

cfe/trunk/lib/StaticAnalyzer/Core/CoreEngine.cpp

Show All 21 Lines
#include "clang/Analysis/ProgramPoint.h" #include "clang/Analysis/ProgramPoint.h"
#include "clang/Basic/LLVM.h" #include "clang/Basic/LLVM.h"
#include "clang/StaticAnalyzer/Core/AnalyzerOptions.h" #include "clang/StaticAnalyzer/Core/AnalyzerOptions.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h" #include "clang/StaticAnalyzer/Core/PathSensitive/BlockCounter.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h" #include "clang/StaticAnalyzer/Core/PathSensitive/ExplodedGraph.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h" #include "clang/StaticAnalyzer/Core/PathSensitive/FunctionSummary.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h" #include "clang/StaticAnalyzer/Core/PathSensitive/SubEngine.h"
#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h" #include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/Optional.h" #include "llvm/ADT/Optional.h"
#include "llvm/ADT/PriorityQueue.h"
#include "llvm/ADT/STLExtras.h" #include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h" #include "llvm/ADT/Statistic.h"
#include "llvm/Support/Casting.h" #include "llvm/Support/Casting.h"
#include "llvm/Support/ErrorHandling.h" #include "llvm/Support/ErrorHandling.h"
#include <algorithm> #include <algorithm>
#include <cassert> #include <cassert>
#include <deque>
#include <memory> #include <memory>
#include <utility> #include <utility>
#include <vector>
using namespace clang; using namespace clang;
using namespace ento; using namespace ento;
#define DEBUG_TYPE "CoreEngine" #define DEBUG_TYPE "CoreEngine"
STATISTIC(NumSteps, STATISTIC(NumSteps,
"The # of steps executed."); "The # of steps executed.");
STATISTIC(NumReachedMaxSteps, STATISTIC(NumReachedMaxSteps,
"The # of times we reached the max number of steps."); "The # of times we reached the max number of steps.");
STATISTIC(NumPathsExplored, STATISTIC(NumPathsExplored,
"The # of paths explored by the analyzer."); "The # of paths explored by the analyzer.");
STATISTIC(MaxQueueSize, "Maximum size of the worklist");
STATISTIC(MaxReachableSize, "Maximum size of auxiliary worklist set");
//===----------------------------------------------------------------------===//
// Worklist classes for exploration of reachable states.
//===----------------------------------------------------------------------===//
namespace {
class DFS : public WorkList {
SmallVector<WorkListUnit, 20> Stack;
public:
bool hasWork() const override {
return !Stack.empty();
}
void enqueue(const WorkListUnit& U) override {
Stack.push_back(U);
}
WorkListUnit dequeue() override {
assert(!Stack.empty());
const WorkListUnit& U = Stack.back();
Stack.pop_back(); // This technically "invalidates" U, but we are fine.
return U;
}
};
class BFS : public WorkList {
std::deque<WorkListUnit> Queue;
public:
bool hasWork() const override {
return !Queue.empty();
}
void enqueue(const WorkListUnit& U) override {
Queue.push_back(U);
}
WorkListUnit dequeue() override {
WorkListUnit U = Queue.front();
Queue.pop_front();
return U;
}
};
} // namespace
// Place the dstor for WorkList here because it contains virtual member
// functions, and we the code for the dstor generated in one compilation unit.
WorkList::~WorkList() = default;
std::unique_ptr<WorkList> WorkList::makeDFS() {
return llvm::make_unique<DFS>();
}
std::unique_ptr<WorkList> WorkList::makeBFS() {
return llvm::make_unique<BFS>();
}
namespace {
class BFSBlockDFSContents : public WorkList {
std::deque<WorkListUnit> Queue;
SmallVector<WorkListUnit, 20> Stack;
public:
bool hasWork() const override {
return !Queue.empty() || !Stack.empty();
}
void enqueue(const WorkListUnit& U) override {
if (U.getNode()->getLocation().getAs<BlockEntrance>())
Queue.push_front(U);
else
Stack.push_back(U);
}
WorkListUnit dequeue() override {
// Process all basic blocks to completion.
if (!Stack.empty()) {
const WorkListUnit& U = Stack.back();
Stack.pop_back(); // This technically "invalidates" U, but we are fine.
return U;
}
assert(!Queue.empty());
// Don't use const reference. The subsequent pop_back() might make it
// unsafe.
WorkListUnit U = Queue.front();
Queue.pop_front();
return U;
}
};
} // namespace
std::unique_ptr<WorkList> WorkList::makeBFSBlockDFSContents() {
return llvm::make_unique<BFSBlockDFSContents>();
}
namespace {
class UnexploredFirstStack : public WorkList {
/// Stack of nodes known to have statements we have not traversed yet.
SmallVector<WorkListUnit, 20> StackUnexplored;
/// Stack of all other nodes.
SmallVector<WorkListUnit, 20> StackOthers;
using BlockID = unsigned;
using LocIdentifier = std::pair<BlockID, const StackFrameContext *>;
llvm::DenseSet<LocIdentifier> Reachable;
public:
bool hasWork() const override {
return !(StackUnexplored.empty() && StackOthers.empty());
}
void enqueue(const WorkListUnit &U) override {
const ExplodedNode *N = U.getNode();
auto BE = N->getLocation().getAs<BlockEntrance>();
if (!BE) {
// Assume the choice of the order of the preceeding block entrance was
// correct.
StackUnexplored.push_back(U);
} else {
LocIdentifier LocId = std::make_pair(
BE->getBlock()->getBlockID(), N->getStackFrame());
auto InsertInfo = Reachable.insert(LocId);
if (InsertInfo.second) {
StackUnexplored.push_back(U);
} else {
StackOthers.push_back(U);
}
}
MaxReachableSize.updateMax(Reachable.size());
MaxQueueSize.updateMax(StackUnexplored.size() + StackOthers.size());
}
WorkListUnit dequeue() override {
if (!StackUnexplored.empty()) {
WorkListUnit &U = StackUnexplored.back();
StackUnexplored.pop_back();
return U;
} else {
WorkListUnit &U = StackOthers.back();
StackOthers.pop_back();
return U;
}
}
};
} // namespace
std::unique_ptr<WorkList> WorkList::makeUnexploredFirst() {
return llvm::make_unique<UnexploredFirstStack>();
}
class UnexploredFirstPriorityQueue : public WorkList {
using BlockID = unsigned;
using LocIdentifier = std::pair<BlockID, const StackFrameContext *>;
// 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>()) {
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> WorkList::makeUnexploredFirstPriorityQueue() {
return llvm::make_unique<UnexploredFirstPriorityQueue>();
}
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
// Core analysis engine. // Core analysis engine.
//===----------------------------------------------------------------------===// //===----------------------------------------------------------------------===//
static std::unique_ptr<WorkList> generateWorkList(AnalyzerOptions &Opts) { static std::unique_ptr<WorkList> generateWorkList(AnalyzerOptions &Opts) {
switch (Opts.getExplorationStrategy()) { switch (Opts.getExplorationStrategy()) {
case AnalyzerOptions::ExplorationStrategyKind::DFS: case AnalyzerOptions::ExplorationStrategyKind::DFS:
return WorkList::makeDFS(); return WorkList::makeDFS();
▲ Show 20 Lines • Show All 590 Lines • Show Last 20 Lines

cfe/trunk/lib/StaticAnalyzer/Core/WorkList.cpp

//===- WorkList.cpp - Analyzer work-list implementation--------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Defines different worklist implementations for the static analyzer.
//
//===----------------------------------------------------------------------===//
#include "clang/StaticAnalyzer/Core/PathSensitive/WorkList.h"
#include "llvm/ADT/PriorityQueue.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
#include <deque>
#include <vector>
using namespace clang;
using namespace ento;
#define DEBUG_TYPE "WorkList"
STATISTIC(MaxQueueSize, "Maximum size of the worklist");
STATISTIC(MaxReachableSize, "Maximum size of auxiliary worklist set");
//===----------------------------------------------------------------------===//
// Worklist classes for exploration of reachable states.
//===----------------------------------------------------------------------===//
namespace {
class DFS : public WorkList {
SmallVector<WorkListUnit, 20> Stack;
public:
bool hasWork() const override {
return !Stack.empty();
}
void enqueue(const WorkListUnit& U) override {
Stack.push_back(U);
}
WorkListUnit dequeue() override {
assert(!Stack.empty());
const WorkListUnit& U = Stack.back();
Stack.pop_back(); // This technically "invalidates" U, but we are fine.
return U;
}
};
class BFS : public WorkList {
std::deque<WorkListUnit> Queue;
public:
bool hasWork() const override {
return !Queue.empty();
}
void enqueue(const WorkListUnit& U) override {
Queue.push_back(U);
}
WorkListUnit dequeue() override {
WorkListUnit U = Queue.front();
Queue.pop_front();
return U;
}
};
} // namespace
// Place the dstor for WorkList here because it contains virtual member
// functions, and we the code for the dstor generated in one compilation unit.
WorkList::~WorkList() = default;
std::unique_ptr<WorkList> WorkList::makeDFS() {
return llvm::make_unique<DFS>();
}
std::unique_ptr<WorkList> WorkList::makeBFS() {
return llvm::make_unique<BFS>();
}
namespace {
class BFSBlockDFSContents : public WorkList {
std::deque<WorkListUnit> Queue;
SmallVector<WorkListUnit, 20> Stack;
public:
bool hasWork() const override {
return !Queue.empty() || !Stack.empty();
}
void enqueue(const WorkListUnit& U) override {
if (U.getNode()->getLocation().getAs<BlockEntrance>())
Queue.push_front(U);
else
Stack.push_back(U);
}
WorkListUnit dequeue() override {
// Process all basic blocks to completion.
if (!Stack.empty()) {
const WorkListUnit& U = Stack.back();
Stack.pop_back(); // This technically "invalidates" U, but we are fine.
return U;
}
assert(!Queue.empty());
// Don't use const reference. The subsequent pop_back() might make it
// unsafe.
WorkListUnit U = Queue.front();
Queue.pop_front();
return U;
}
};
} // namespace
std::unique_ptr<WorkList> WorkList::makeBFSBlockDFSContents() {
return llvm::make_unique<BFSBlockDFSContents>();
}
namespace {
class UnexploredFirstStack : public WorkList {
/// Stack of nodes known to have statements we have not traversed yet.
SmallVector<WorkListUnit, 20> StackUnexplored;
/// Stack of all other nodes.
SmallVector<WorkListUnit, 20> StackOthers;
using BlockID = unsigned;
using LocIdentifier = std::pair<BlockID, const StackFrameContext *>;
llvm::DenseSet<LocIdentifier> Reachable;
public:
bool hasWork() const override {
return !(StackUnexplored.empty() && StackOthers.empty());
}
void enqueue(const WorkListUnit &U) override {
const ExplodedNode *N = U.getNode();
auto BE = N->getLocation().getAs<BlockEntrance>();
if (!BE) {
// Assume the choice of the order of the preceeding block entrance was
// correct.
StackUnexplored.push_back(U);
} else {
LocIdentifier LocId = std::make_pair(
BE->getBlock()->getBlockID(),
N->getLocationContext()->getCurrentStackFrame());
auto InsertInfo = Reachable.insert(LocId);
if (InsertInfo.second) {
StackUnexplored.push_back(U);
} else {
StackOthers.push_back(U);
}
}
MaxReachableSize.updateMax(Reachable.size());
MaxQueueSize.updateMax(StackUnexplored.size() + StackOthers.size());
}
WorkListUnit dequeue() override {
if (!StackUnexplored.empty()) {
WorkListUnit &U = StackUnexplored.back();
StackUnexplored.pop_back();
return U;
} else {
WorkListUnit &U = StackOthers.back();
StackOthers.pop_back();
return U;
}
}
};
} // namespace
std::unique_ptr<WorkList> WorkList::makeUnexploredFirst() {
return llvm::make_unique<UnexploredFirstStack>();
}
class UnexploredFirstPriorityQueue : public WorkList {
using BlockID = unsigned;
using LocIdentifier = std::pair<BlockID, const StackFrameContext *>;
// 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>()) {
LocIdentifier LocId = std::make_pair(
BE->getBlock()->getBlockID(),
N->getLocationContext()->getCurrentStackFrame());
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> WorkList::makeUnexploredFirstPriorityQueue() {
return llvm::make_unique<UnexploredFirstPriorityQueue>();
}