Mercurial > hg > truffle

changeset 19561:6c676b3301be

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Create a more efficient version of commonDominator.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Mon, 23 Feb 2015 19:11:48 +0100
parents 4d70d150944f
children 94f71c29c016
files graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractBlockBase.java graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java
diffstat 3 files changed, 46 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractBlockBase.java	Mon Feb 23 18:37:20 2015 +0100
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractBlockBase.java	Mon Feb 23 19:11:48 2015 +0100
@@ -27,6 +27,7 @@
 public abstract class AbstractBlockBase<T extends AbstractBlockBase<T>> {
 
     protected int id;
+    protected int domDepth;
 
     protected List<T> predecessors;
     protected List<T> successors;
@@ -72,6 +73,11 @@
 
     public void setDominator(T dominator) {
         this.dominator = dominator;
+        this.domDepth = dominator.domDepth + 1;
+    }
+
+    public int getDominatorDepth() {
+        return domDepth;
     }
 
     public List<T> getDominated() {
@@ -127,4 +133,6 @@
     public abstract T getPostdominator();
 
     public abstract double probability();
+
+    public abstract T getDominator(int distance);
 }
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java	Mon Feb 23 18:37:20 2015 +0100
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java	Mon Feb 23 19:11:48 2015 +0100
@@ -111,8 +111,17 @@
         if (b == null) {
             return a;
         }
+
         AbstractBlockBase<?> iterA = a;
         AbstractBlockBase<?> iterB = b;
+        int aDomDepth = a.getDominatorDepth();
+        int bDomDepth = b.getDominatorDepth();
+        if (aDomDepth > bDomDepth) {
+            iterA = a.getDominator(aDomDepth - bDomDepth);
+        } else {
+            iterB = b.getDominator(bDomDepth - aDomDepth);
+        }
+
         while (iterA != iterB) {
             if (iterA.getId() > iterB.getId()) {
                 iterA = iterA.getDominator();
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java	Mon Feb 23 18:37:20 2015 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/cfg/Block.java	Mon Feb 23 19:11:48 2015 +0100
@@ -30,6 +30,7 @@
 
 public final class Block extends AbstractBlockBase<Block> {
 
+    public static final int DISTANCED_DOMINATOR_CACHE = 5;
     protected final AbstractBeginNode beginNode;
 
     protected FixedNode endNode;
@@ -38,6 +39,7 @@
     protected Loop<Block> loop;
 
     protected Block postdominator;
+    protected Block distancedDominatorCache;
 
     protected Block(AbstractBeginNode node) {
         this.beginNode = node;
@@ -174,4 +176,31 @@
         assert probability >= 0 && Double.isFinite(probability);
         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) {
+            result = result.getDominator();
+        }
+        return result;
+    }
 }