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 54c6647f05904f039b69827a8cc9523f65ed5c56..dc260af0fc75ff2b00a999a6eea71ef1afa1a8e1 100644 (file)
--- a/lib/CodeGen/StrongPHIElimination.cpp
+++ b/lib/CodeGen/StrongPHIElimination.cpp
@@ -400,12 +400,18 @@ void StrongPHIElimination::addReg(unsigned Reg) {
 
 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) {