# HG changeset patch # User Stefan Anzinger # Date 1429012878 -7200 # Node ID c617a74a9eaba5b724ba1f9cf277f703b789c209 # Parent d9713313e88c1c0fd9dcf1f5d6bcbee5e1caecf8# Parent cea0b72851900c95a2778102ce0be7644e6d29d4 Merge diff -r cea0b7285190 -r c617a74a9eab 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 Apr 14 12:08:41 2015 +0200 +++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java Tue Apr 14 14:01:18 2015 +0200 @@ -66,17 +66,40 @@ } dominator.getDominated().add(block); } - calcDominatorRanges(cfg.getStartBlock(), 0); + calcDominatorRanges(cfg.getStartBlock()); } - static > int calcDominatorRanges(T block, int next) { - int myNumber = next; - int maxNumber = myNumber; - for (T dominated : block.getDominated()) { - maxNumber = calcDominatorRanges(dominated, maxNumber + 1); + static > void calcDominatorRanges(T block) { + final class Frame { + int myNumber; + int maxNumber; + T block; + Iterator dominated; + Frame parent; + + public Frame(int myNumber, T block, Iterator dominated, Frame parent) { + super(); + this.myNumber = myNumber; + this.maxNumber = myNumber; + this.block = block; + this.dominated = dominated; + this.parent = parent; + } } - block.setDominatorNumbers(myNumber, maxNumber); - return maxNumber; + Frame f = new Frame<>(0, block, block.getDominated().iterator(), null); + while (f != null) { + if (!f.dominated.hasNext()) { // Retreat + f.block.setDominatorNumbers(f.myNumber, f.maxNumber); + if (f.parent != null) { + f.parent.maxNumber = f.maxNumber; + } + f = f.parent; + } else { + T d = f.dominated.next(); + List dd = d.getDominated(); + f = new Frame<>(f.maxNumber + 1, d, dd.iterator(), f); + } + } } /** diff -r cea0b7285190 -r c617a74a9eab graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/DominatorConditionalEliminationPhase.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/DominatorConditionalEliminationPhase.java Tue Apr 14 12:08:41 2015 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/DominatorConditionalEliminationPhase.java Tue Apr 14 14:01:18 2015 +0200 @@ -40,6 +40,7 @@ import com.oracle.graal.nodes.java.*; import com.oracle.graal.nodes.util.*; import com.oracle.graal.phases.*; +import com.oracle.graal.phases.common.LoweringPhase.*; import com.oracle.graal.phases.schedule.*; public class DominatorConditionalEliminationPhase extends Phase { @@ -141,27 +142,32 @@ this.nodeToBlock = nodeToBlock; } - private void processBlock(Block block) { + public void processBlock(Block startBlock) { + LoweringPhase.processBlock(new InstanceFrame(startBlock, null)); + } + + public class InstanceFrame extends LoweringPhase.Frame { List undoOperations = new ArrayList<>(); - preprocess(block, undoOperations); + public InstanceFrame(Block block, InstanceFrame parent) { + super(block, parent); + } - // Process always reached block first. - Block postdominator = block.getPostdominator(); - if (postdominator != null && postdominator.getDominator() == block) { - processBlock(postdominator); + @Override + public Frame enter(Block b) { + return new InstanceFrame(b, this); } - // Now go for the other dominators. - for (Block dominated : block.getDominated()) { - if (dominated != postdominator) { - assert dominated.getDominator() == block; - processBlock(dominated); - } + @Override + public void preprocess() { + Instance.this.preprocess(block, undoOperations); } - postprocess(undoOperations); + @Override + public void postprocess() { + Instance.postprocess(undoOperations); + } } private static void postprocess(List undoOperations) { diff -r cea0b7285190 -r c617a74a9eab graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java --- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java Tue Apr 14 12:08:41 2015 +0200 +++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java Tue Apr 14 14:01:18 2015 +0200 @@ -23,10 +23,12 @@ package com.oracle.graal.phases.common; import static com.oracle.graal.compiler.common.GraalOptions.*; +import static com.oracle.graal.phases.common.LoweringPhase.ProcessBlockState.*; import java.util.*; import com.oracle.graal.api.meta.*; +import com.oracle.graal.compiler.common.*; import com.oracle.graal.compiler.common.type.*; import com.oracle.graal.graph.Graph.Mark; import com.oracle.graal.graph.*; @@ -250,35 +252,43 @@ @Override public void run(StructuredGraph graph) { schedule.apply(graph, false); - processBlock(schedule.getCFG().getStartBlock(), graph.createNodeBitMap(), null); + Block startBlock = schedule.getCFG().getStartBlock(); + ProcessFrame rootFrame = new ProcessFrame(startBlock, graph.createNodeBitMap(), startBlock.getBeginNode(), null); + LoweringPhase.processBlock(rootFrame); } - private void processBlock(Block block, NodeBitMap activeGuards, AnchoringNode parentAnchor) { + private class ProcessFrame extends Frame { + private final NodeBitMap activeGuards; + private AnchoringNode anchor; - AnchoringNode anchor = parentAnchor; - if (anchor == null) { - anchor = block.getBeginNode(); + public ProcessFrame(Block block, NodeBitMap activeGuards, AnchoringNode anchor, ProcessFrame parent) { + super(block, parent); + this.activeGuards = activeGuards; + this.anchor = anchor; } - anchor = process(block, activeGuards, anchor); - // Process always reached block first. - Block alwaysReachedBlock = block.getPostdominator(); - if (alwaysReachedBlock != null && alwaysReachedBlock.getDominator() == block) { - processBlock(alwaysReachedBlock, activeGuards, anchor); + @Override + public void preprocess() { + this.anchor = Round.this.process(block, activeGuards, anchor); } - // Now go for the other dominators. - for (Block dominated : block.getDominated()) { - if (dominated != alwaysReachedBlock) { - assert dominated.getDominator() == block; - processBlock(dominated, activeGuards, null); - } + @Override + public ProcessFrame enter(Block b) { + return new ProcessFrame(b, activeGuards, b.getBeginNode(), this); } - if (parentAnchor == null && OptEliminateGuards.getValue()) { - for (GuardNode guard : anchor.asNode().usages().filter(GuardNode.class)) { - if (activeGuards.isMarkedAndGrow(guard)) { - activeGuards.clear(guard); + @Override + public Frame enterAlwaysReached(Block b) { + return new ProcessFrame(b, activeGuards, anchor, this); + } + + @Override + public void postprocess() { + if (anchor != null && OptEliminateGuards.getValue()) { + for (GuardNode guard : anchor.asNode().usages().filter(GuardNode.class)) { + if (activeGuards.isMarkedAndGrow(guard)) { + activeGuards.clear(guard); + } } } } @@ -366,4 +376,111 @@ return unscheduledUsages; } } + + enum ProcessBlockState { + ST_ENTER, + ST_PROCESS, + ST_ENTER_ALWAYS_REACHED, + ST_LEAVE, + ST_PROCESS_ALWAYS_REACHED; + } + + /** + * This state-machine resembles the following recursion: + * + * 
+     * void processBlock(Block block) {
+     *     preprocess();
+     *     // Process always reached block first.
+     *     Block alwaysReachedBlock = block.getPostdominator();
+     *     if (alwaysReachedBlock != null && alwaysReachedBlock.getDominator() == block) {
+     *         processBlock(alwaysReachedBlock);
+     *     }
+     * 
+     *     // Now go for the other dominators.
+     *     for (Block dominated : block.getDominated()) {
+     *         if (dominated != alwaysReachedBlock) {
+     *             assert dominated.getDominator() == block;
+     *             processBlock(dominated);
+     *         }
+     *     }
+     *     postprocess();
+     * }
+     *
+ * + * This is necessary, as the recursive implementation quickly exceed the stack depth on SPARC. + * + * @param rootFrame contains the starting block. + */ + public static void processBlock(final Frame rootFrame) { + ProcessBlockState state = ST_PROCESS; + Frame f = rootFrame; + while (f != null) { + ProcessBlockState nextState; + if (state == ST_PROCESS || state == ST_PROCESS_ALWAYS_REACHED) { + f.preprocess(); + nextState = state == ST_PROCESS_ALWAYS_REACHED ? ST_ENTER : ST_ENTER_ALWAYS_REACHED; + } else if (state == ST_ENTER_ALWAYS_REACHED) { + if (f.alwaysReachedBlock != null && f.alwaysReachedBlock == f.block) { + f = f.enterAlwaysReached(f.alwaysReachedBlock); + nextState = ST_PROCESS; + } else { + nextState = ST_ENTER; + } + } else if (state == ST_ENTER) { + if (f.dominated.hasNext()) { + Block n = f.dominated.next(); + if (n == f.alwaysReachedBlock) { + if (f.dominated.hasNext()) { + n = f.dominated.next(); + } else { + n = null; + } + } + if (n == null) { + nextState = ST_LEAVE; + } else { + f = f.enter(n); + assert f.block.getDominator() == f.parent.block; + nextState = ST_PROCESS; + } + } else { + nextState = ST_LEAVE; + } + } else if (state == ST_LEAVE) { + f.postprocess(); + f = f.parent; + nextState = ST_ENTER; + } else { + throw GraalInternalError.shouldNotReachHere(); + } + state = nextState; + } + } + + public abstract static class Frame> { + final Block block; + final T parent; + Iterator dominated; + final Block alwaysReachedBlock; + + public Frame(Block block, T parent) { + super(); + this.block = block; + this.alwaysReachedBlock = block.getPostdominator(); + this.dominated = block.getDominated().iterator(); + this.parent = parent; + } + + public Frame enterAlwaysReached(Block b) { + return enter(b); + } + + public abstract Frame enter(Block b); + + public abstract void preprocess(); + + public abstract void postprocess(); + } + }