# HG changeset patch
# User Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
# Date 1425379831 -3600
# Node ID d9e44edfca9b47fb34ab020271b1120ff9374836
# Parent  c96f8337292e9ad4fc22697f8be18c2c3b6f1fef
Improve common dominator calculations.

diff -r c96f8337292e -r d9e44edfca9b graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractBlockBase.java
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractBlockBase.java	Tue Mar 03 00:01:36 2015 +0100
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractBlockBase.java	Tue Mar 03 11:50:31 2015 +0100
@@ -34,6 +34,8 @@
 
     private T dominator;
     private List<T> dominated;
+    private int domNumber;
+    private int maxChildDomNumber;
 
     private boolean align;
     private int linearScanNumber;
@@ -43,6 +45,19 @@
         this.linearScanNumber = -1;
     }
 
+    public void setDominatorNumbers(int domNumber, int maxChildDomNumber) {
+        this.domNumber = domNumber;
+        this.maxChildDomNumber = maxChildDomNumber;
+    }
+
+    public int getDominatorNumber() {
+        return domNumber;
+    }
+
+    public int getMaxChildDominatorNumber() {
+        return this.maxChildDomNumber;
+    }
+
     public int getId() {
         return id;
     }
diff -r c96f8337292e -r d9e44edfca9b graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java	Tue Mar 03 00:01:36 2015 +0100
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java	Tue Mar 03 11:50:31 2015 +0100
@@ -46,6 +46,7 @@
     /**
      * Computes the dominators of control flow graph.
      */
+    @SuppressWarnings("unchecked")
     static <T extends AbstractBlockBase<T>> void computeDominators(AbstractControlFlowGraph<T> cfg) {
         List<T> reversePostOrder = cfg.getBlocks();
         assert reversePostOrder.get(0).getPredecessorCount() == 0 : "start block has no predecessor and therefore no dominator";
@@ -55,7 +56,7 @@
             T dominator = null;
             for (T pred : block.getPredecessors()) {
                 if (!pred.isLoopEnd()) {
-                    dominator = commonDominatorTyped(dominator, pred);
+                    dominator = (T) ((dominator == null) ? pred : commonDominatorRaw(dominator, pred));
                 }
             }
             // set dominator
@@ -65,21 +66,26 @@
             }
             dominator.getDominated().add(block);
         }
+        calcDominatorRanges(cfg.getStartBlock(), 0);
+    }
+
+    static <T extends AbstractBlockBase<T>> int calcDominatorRanges(T block, int next) {
+        int myNumber = next;
+        int maxNumber = myNumber;
+        for (T dominated : block.getDominated()) {
+            maxNumber = calcDominatorRanges(dominated, maxNumber + 1);
+        }
+        block.setDominatorNumbers(myNumber, maxNumber);
+        return maxNumber;
     }
 
     /**
      * True if block {@code a} is dominated by block {@code b}.
      */
     static boolean isDominatedBy(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
-        assert a != null && b != null;
-        if (a == b) {
-            return true;
-        }
-        if (a.getDominatorDepth() < b.getDominatorDepth()) {
-            return false;
-        }
-
-        return b == (AbstractBlockBase<?>) a.getDominator(a.getDominatorDepth() - b.getDominatorDepth());
+        int domNumberA = a.getDominatorNumber();
+        int domNumberB = b.getDominatorNumber();
+        return domNumberA >= domNumberB && domNumberA <= b.getMaxChildDominatorNumber();
     }
 
     /**
@@ -101,21 +107,49 @@
     static AbstractBlockBase<?> commonDominator(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
         if (a == null) {
             return b;
-        }
-        if (b == null) {
+        } else if (b == null) {
             return a;
+        } else {
+            int aDomDepth = a.getDominatorDepth();
+            int bDomDepth = b.getDominatorDepth();
+            AbstractBlockBase<?> aTemp;
+            AbstractBlockBase<?> bTemp;
+            if (aDomDepth > bDomDepth) {
+                aTemp = a;
+                bTemp = b;
+            } else {
+                aTemp = b;
+                bTemp = a;
+            }
+            return commonDominatorHelper(aTemp, bTemp);
         }
+    }
 
-        AbstractBlockBase<?> iterA = a;
-        AbstractBlockBase<?> iterB = b;
+    static AbstractBlockBase<?> commonDominatorHelper(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
+        int domNumberA = a.getDominatorNumber();
+        AbstractBlockBase<?> result = b;
+        while (domNumberA < result.getDominatorNumber()) {
+            result = result.getDominator();
+        }
+        while (domNumberA > result.getMaxChildDominatorNumber()) {
+            result = result.getDominator();
+        }
+        return result;
+    }
+
+    static AbstractBlockBase<?> commonDominatorRaw(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
         int aDomDepth = a.getDominatorDepth();
         int bDomDepth = b.getDominatorDepth();
         if (aDomDepth > bDomDepth) {
-            iterA = a.getDominator(aDomDepth - bDomDepth);
+            return commonDominatorRawSameDepth(a.getDominator(aDomDepth - bDomDepth), b);
         } else {
-            iterB = b.getDominator(bDomDepth - aDomDepth);
+            return commonDominatorRawSameDepth(a, b.getDominator(bDomDepth - aDomDepth));
         }
+    }
 
+    static AbstractBlockBase<?> commonDominatorRawSameDepth(AbstractBlockBase<?> a, AbstractBlockBase<?> b) {
+        AbstractBlockBase<?> iterA = a;
+        AbstractBlockBase<?> iterB = b;
         while (iterA != iterB) {
             iterA = iterA.getDominator();
             iterB = iterB.getDominator();
diff -r c96f8337292e -r d9e44edfca9b graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java	Tue Mar 03 00:01:36 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java	Tue Mar 03 11:50:31 2015 +0100
@@ -30,7 +30,6 @@
 
 public final class Block extends AbstractBlockBase<Block> {
 
-    public static final int DISTANCED_DOMINATOR_CACHE = 5;
     protected final AbstractBeginNode beginNode;
 
     protected FixedNode endNode;
@@ -177,28 +176,10 @@
         this.probability = probability;
     }
 
-    public Block getDistancedDominatorCache() {
-        Block result = this.distancedDominatorCache;
-        if (result == null) {
-            Block current = this;
-            for (int i = 0; i < DISTANCED_DOMINATOR_CACHE; ++i) {
-                current = current.getDominator();
-            }
-            distancedDominatorCache = current;
-            return current;
-        } else {
-            return result;
-        }
-    }
-
     @Override
     public Block getDominator(int distance) {
         Block result = this;
-        int i = 0;
-        for (; i < distance - (DISTANCED_DOMINATOR_CACHE - 1); i += DISTANCED_DOMINATOR_CACHE) {
-            result = result.getDistancedDominatorCache();
-        }
-        for (; i < distance; ++i) {
+        for (int i = 0; i < distance; ++i) {
             result = result.getDominator();
         }
         return result;