Mercurial > hg > graal-jvmci-8
changeset 19568:6c676b3301be
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; + } }