Fix DFS walk.
Fix http://llvm.org/bugs/show_bug.cgi?id=923
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@30630 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/PostDominators.cpp b/lib/Analysis/PostDominators.cpp
index bfa1520..9f1f468 100644
--- a/lib/Analysis/PostDominators.cpp
+++ b/lib/Analysis/PostDominators.cpp
@@ -28,36 +28,49 @@
unsigned ImmediatePostDominators::DFSPass(BasicBlock *V, InfoRec &VInfo,
unsigned N) {
-
std::vector<std::pair<BasicBlock *, InfoRec *> > workStack;
+ std::set<BasicBlock *> visited;
workStack.push_back(std::make_pair(V, &VInfo));
do {
BasicBlock *currentBB = workStack.back().first;
InfoRec *currentVInfo = workStack.back().second;
- workStack.pop_back();
- currentVInfo->Semi = ++N;
- currentVInfo->Label = currentBB;
+ // Visit each block only once.
+ if (visited.count(currentBB) == 0) {
- Vertex.push_back(currentBB); // Vertex[n] = current;
- // Info[currentBB].Ancestor = 0;
- // Ancestor[n] = 0
- // Child[currentBB] = 0;
- currentVInfo->Size = 1; // Size[currentBB] = 1
+ visited.insert(currentBB);
+ currentVInfo->Semi = ++N;
+ currentVInfo->Label = currentBB;
+
+ Vertex.push_back(currentBB); // Vertex[n] = current;
+ // Info[currentBB].Ancestor = 0;
+ // Ancestor[n] = 0
+ // Child[currentBB] = 0;
+ currentVInfo->Size = 1; // Size[currentBB] = 1
+ }
- // For PostDominators, we want to walk predecessors rather than successors
- // as we do in forward Dominators.
+ // Visit children
+ bool visitChild = false;
for (pred_iterator PI = pred_begin(currentBB), PE = pred_end(currentBB);
- PI != PE; ++PI) {
+ PI != PE && !visitChild; ++PI) {
InfoRec &SuccVInfo = Info[*PI];
if (SuccVInfo.Semi == 0) {
SuccVInfo.Parent = currentBB;
-
- workStack.push_back(std::make_pair(*PI, &SuccVInfo));
+ if (visited.count (*PI) == 0) {
+ workStack.push_back(std::make_pair(*PI, &SuccVInfo));
+ visitChild = true;
+ }
}
}
+
+ // If all children are visited or if this block has no child then pop this
+ // block out of workStack.
+ if (!visitChild)
+ workStack.pop_back();
+
} while (!workStack.empty());
+
return N;
}