Merge remote-tracking branch 'origin/swift-3.1-branch' into stable
* origin/swift-3.1-branch:
[analyzer] Remove superquadratic behaviour from DataflowWorklist
diff --git a/lib/Analysis/LiveVariables.cpp b/lib/Analysis/LiveVariables.cpp
index 5e0a9a0..cd73a62 100644
--- a/lib/Analysis/LiveVariables.cpp
+++ b/lib/Analysis/LiveVariables.cpp
@@ -19,6 +19,7 @@
#include "clang/Analysis/CFG.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/PriorityQueue.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <vector>
@@ -28,20 +29,21 @@
namespace {
class DataflowWorklist {
- SmallVector<const CFGBlock *, 20> worklist;
llvm::BitVector enqueuedBlocks;
PostOrderCFGView *POV;
+ llvm::PriorityQueue<const CFGBlock *, SmallVector<const CFGBlock *, 20>,
+ 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();
};
}
@@ -49,31 +51,22 @@
void DataflowWorklist::enqueueBlock(const clang::CFGBlock *block) {
if (block && !enqueuedBlocks[block->getBlockID()]) {
enqueuedBlocks[block->getBlockID()] = true;
- worklist.push_back(block);
+ worklist.push(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 CFGBlock *b = worklist.top();
+ worklist.pop();
enqueuedBlocks[b->getBlockID()] = false;
return b;
}
@@ -528,8 +521,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.