alexshap created this revision.
alexshap added reviewers: NoQ, zaks.anna.
alexshap added a subscriber: cfe-commits.
alexshap set the repository for this revision to rL LLVM.
The class DataflowWorklist internally maintains a sorted list of pointers to
CFGBlock and
the method enqueuePredecessors has to call sortWorklist to maintain the
invariant.
The implementation based on vector + sort works well for small sizes but gets
infeasible
for relatively large sizes. In particular the issue takes place for some
cryptographic libraries which use code generation.
This diff replaces vector + sort with set.
The slowdown for small sizes (measured on the current tests) is negligeable (I
was looking at the reported "Testing Time" for check-clang-analysis and the
difference was less then 0.01s (the total time is 3.93s)).
Repository:
rL LLVM
https://reviews.llvm.org/D25503
Files:
lib/Analysis/LiveVariables.cpp
Index: lib/Analysis/LiveVariables.cpp
===================================================================
--- lib/Analysis/LiveVariables.cpp
+++ lib/Analysis/LiveVariables.cpp
@@ -21,59 +21,51 @@
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
+#include <set>
#include <vector>
using namespace clang;
namespace {
class DataflowWorklist {
- SmallVector<const CFGBlock *, 20> worklist;
llvm::BitVector enqueuedBlocks;
PostOrderCFGView *POV;
+ std::multiset<const CFGBlock *, PostOrderCFGView::BlockOrderCompare>
worklist;
public:
DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx)
: enqueuedBlocks(cfg.getNumBlockIDs()),
- POV(Ctx.getAnalysis<PostOrderCFGView>()) {}
+ POV(Ctx.getAnalysis<PostOrderCFGView>()),
+ worklist(POV->getComparator()) {}
void enqueueBlock(const CFGBlock *block);
void enqueuePredecessors(const CFGBlock *block);
const CFGBlock *dequeue();
-
- void sortWorklist();
};
}
void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) {
if (block && !enqueuedBlocks[block->getBlockID()]) {
enqueuedBlocks[block->getBlockID()] = true;
- worklist.push_back(block);
+ worklist.insert(block);
}
}
void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) {
- const unsigned OldWorklistSize = worklist.size();
for (CFGBlock::const_pred_iterator I = block->pred_begin(),
E = block->pred_end(); I != E; ++I) {
enqueueBlock(*I);
}
-
- if (OldWorklistSize == 0 || OldWorklistSize == worklist.size())
- return;
-
- sortWorklist();
-}
-
-void DataflowWorklist::sortWorklist() {
- std::sort(worklist.begin(), worklist.end(), POV->getComparator());
}
const CFGBlock *DataflowWorklist::dequeue() {
if (worklist.empty())
return nullptr;
- const CFGBlock *b = worklist.pop_back_val();
+ const auto I = --worklist.end();
+ const CFGBlock *b = *I;
+ worklist.erase(I);
enqueuedBlocks[b->getBlockID()] = false;
return b;
}
@@ -528,8 +520,6 @@
}
}
- worklist.sortWorklist();
-
while (const CFGBlock *block = worklist.dequeue()) {
// Determine if the block's end value has changed. If not, we
// have nothing left to do for this block.
Index: lib/Analysis/LiveVariables.cpp
===================================================================
--- lib/Analysis/LiveVariables.cpp
+++ lib/Analysis/LiveVariables.cpp
@@ -21,59 +21,51 @@
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
+#include <set>
#include <vector>
using namespace clang;
namespace {
class DataflowWorklist {
- SmallVector<const CFGBlock *, 20> worklist;
llvm::BitVector enqueuedBlocks;
PostOrderCFGView *POV;
+ std::multiset<const CFGBlock *, PostOrderCFGView::BlockOrderCompare> worklist;
public:
DataflowWorklist(const CFG &cfg, AnalysisDeclContext &Ctx)
: enqueuedBlocks(cfg.getNumBlockIDs()),
- POV(Ctx.getAnalysis<PostOrderCFGView>()) {}
+ POV(Ctx.getAnalysis<PostOrderCFGView>()),
+ worklist(POV->getComparator()) {}
void enqueueBlock(const CFGBlock *block);
void enqueuePredecessors(const CFGBlock *block);
const CFGBlock *dequeue();
-
- void sortWorklist();
};
}
void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) {
if (block && !enqueuedBlocks[block->getBlockID()]) {
enqueuedBlocks[block->getBlockID()] = true;
- worklist.push_back(block);
+ worklist.insert(block);
}
}
void DataflowWorklist::enqueuePredecessors(const clang::CFGBlock *block) {
- const unsigned OldWorklistSize = worklist.size();
for (CFGBlock::const_pred_iterator I = block->pred_begin(),
E = block->pred_end(); I != E; ++I) {
enqueueBlock(*I);
}
-
- if (OldWorklistSize == 0 || OldWorklistSize == worklist.size())
- return;
-
- sortWorklist();
-}
-
-void DataflowWorklist::sortWorklist() {
- std::sort(worklist.begin(), worklist.end(), POV->getComparator());
}
const CFGBlock *DataflowWorklist::dequeue() {
if (worklist.empty())
return nullptr;
- const CFGBlock *b = worklist.pop_back_val();
+ const auto I = --worklist.end();
+ const CFGBlock *b = *I;
+ worklist.erase(I);
enqueuedBlocks[b->getBlockID()] = false;
return b;
}
@@ -528,8 +520,6 @@
}
}
- worklist.sortWorklist();
-
while (const CFGBlock *block = worklist.dequeue()) {
// Determine if the block's end value has changed. If not, we
// have nothing left to do for this block.
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
