Switch to path halving from path compression for a small speedup. This also
makes getLeader() nonrecursive.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122811 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/StrongPHIElimination.cpp b/lib/CodeGen/StrongPHIElimination.cpp
index 54c6647..dc260af 100644
--- a/lib/CodeGen/StrongPHIElimination.cpp
+++ b/lib/CodeGen/StrongPHIElimination.cpp
@@ -400,12 +400,18 @@
StrongPHIElimination::Node*
StrongPHIElimination::Node::getLeader() {
- Node* parentPointer = parent.getPointer();
- if (parentPointer == this)
- return this;
- Node* newParent = parentPointer->getLeader();
- parent.setPointer(newParent);
- return newParent;
+ Node* N = this;
+ Node* Parent = parent.getPointer();
+ Node* Grandparent = Parent->parent.getPointer();
+
+ while (Parent != Grandparent) {
+ N->parent.setPointer(Grandparent);
+ N = Grandparent;
+ Parent = Parent->parent.getPointer();
+ Grandparent = Parent->parent.getPointer();
+ }
+
+ return Parent;
}
unsigned StrongPHIElimination::getRegColor(unsigned Reg) {