Changes in directory llvm/lib/Transforms/Scalar:
GVNPRE.cpp updated: 1.54 -> 1.55
---
Log message:
Rework topo_sort so eliminate some behavior that scaled terribly. This reduces
the time to optimize 403.gcc from 18.2s to 17.5s,
and has an even larger effect on larger testcases.
---
Diffs of the changes: (+40 -57)
GVNPRE.cpp | 97 +++++++++++++++++++++++++------------------------------------
1 files changed, 40 insertions(+), 57 deletions(-)
Index: llvm/lib/Transforms/Scalar/GVNPRE.cpp
diff -u llvm/lib/Transforms/Scalar/GVNPRE.cpp:1.54
llvm/lib/Transforms/Scalar/GVNPRE.cpp:1.55
--- llvm/lib/Transforms/Scalar/GVNPRE.cpp:1.54 Fri Jun 22 13:27:04 2007
+++ llvm/lib/Transforms/Scalar/GVNPRE.cpp Fri Jun 22 16:31:16 2007
@@ -650,71 +650,54 @@
/// topo_sort - Given a set of values, sort them by topological
/// order into the provided vector.
void GVNPRE::topo_sort(SmallPtrSet<Value*, 32>& set, std::vector<Value*>& vec)
{
- SmallPtrSet<Value*, 32> toErase;
+ SmallPtrSet<Value*, 32> visited;
+ std::vector<Value*> stack;
for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
I != E; ++I) {
- if (BinaryOperator* BO = dyn_cast<BinaryOperator>(*I))
- for (SmallPtrSet<Value*, 32>::iterator SI = set.begin(); SI != E; ++SI) {
- if (VN.lookup(BO->getOperand(0)) == VN.lookup(*SI) ||
- VN.lookup(BO->getOperand(1)) == VN.lookup(*SI)) {
- toErase.insert(*SI);
+ if (visited.count(*I) == 0)
+ stack.push_back(*I);
+
+ while (!stack.empty()) {
+ Value* e = stack.back();
+
+ if (BinaryOperator* BO = dyn_cast<BinaryOperator>(e)) {
+ Value* l = find_leader(set, VN.lookup(BO->getOperand(0)));
+ Value* r = find_leader(set, VN.lookup(BO->getOperand(1)));
+
+ if (l != 0 && isa<Instruction>(l) &&
+ visited.count(l) == 0)
+ stack.push_back(l);
+ else if (r != 0 && isa<Instruction>(r) &&
+ visited.count(r) == 0)
+ stack.push_back(r);
+ else {
+ vec.push_back(e);
+ visited.insert(e);
+ stack.pop_back();
}
- }
- else if (CmpInst* C = dyn_cast<CmpInst>(*I))
- for (SmallPtrSet<Value*, 32>::iterator SI = set.begin(); SI != E; ++SI) {
- if (VN.lookup(C->getOperand(0)) == VN.lookup(*SI) ||
- VN.lookup(C->getOperand(1)) == VN.lookup(*SI)) {
- toErase.insert(*SI);
+ } else if (CmpInst* C = dyn_cast<CmpInst>(e)) {
+ Value* l = find_leader(set, VN.lookup(C->getOperand(0)));
+ Value* r = find_leader(set, VN.lookup(C->getOperand(1)));
+
+ if (l != 0 && isa<Instruction>(l) &&
+ visited.count(l) == 0)
+ stack.push_back(l);
+ else if (r != 0 && isa<Instruction>(r) &&
+ visited.count(r) == 0)
+ stack.push_back(r);
+ else {
+ vec.push_back(e);
+ visited.insert(e);
+ stack.pop_back();
}
- }
- }
-
- std::vector<Value*> Q;
- for (SmallPtrSet<Value*, 32>::iterator I = set.begin(), E = set.end();
- I != E; ++I) {
- if (toErase.count(*I) == 0)
- Q.push_back(*I);
- }
-
- SmallPtrSet<Value*, 32> visited;
- while (!Q.empty()) {
- Value* e = Q.back();
-
- if (BinaryOperator* BO = dyn_cast<BinaryOperator>(e)) {
- Value* l = find_leader(set, VN.lookup(BO->getOperand(0)));
- Value* r = find_leader(set, VN.lookup(BO->getOperand(1)));
-
- if (l != 0 && isa<Instruction>(l) &&
- visited.count(l) == 0)
- Q.push_back(l);
- else if (r != 0 && isa<Instruction>(r) &&
- visited.count(r) == 0)
- Q.push_back(r);
- else {
- vec.push_back(e);
+ } else {
visited.insert(e);
- Q.pop_back();
- }
- } else if (CmpInst* C = dyn_cast<CmpInst>(e)) {
- Value* l = find_leader(set, VN.lookup(C->getOperand(0)));
- Value* r = find_leader(set, VN.lookup(C->getOperand(1)));
-
- if (l != 0 && isa<Instruction>(l) &&
- visited.count(l) == 0)
- Q.push_back(l);
- else if (r != 0 && isa<Instruction>(r) &&
- visited.count(r) == 0)
- Q.push_back(r);
- else {
vec.push_back(e);
- visited.insert(e);
- Q.pop_back();
+ stack.pop_back();
}
- } else {
- visited.insert(e);
- vec.push_back(e);
- Q.pop_back();
}
+
+ stack.clear();
}
}
_______________________________________________
llvm-commits mailing list
llvm-commits@cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
