Mercurial > hg > truffle

changeset 20928:d9713313e88c

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Change recursive LoweringPhase.Round.processBlock to state machine with emulated stack. Also use the same traversal in DominatorConditionalEliminationPhase.Instance.processBlock. Required, as the recursive implementation exceeds the stack on SPARC.
author Stefan Anzinger <stefan.anzinger@oracle.com>
date Tue, 14 Apr 2015 13:37:47 +0200
parents 2402d5534773
children c617a74a9eab
files graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/DominatorConditionalEliminationPhase.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java
diffstat 3 files changed, 158 insertions(+), 34 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java	Fri Apr 10 16:22:46 2015 +0200
+++ b/graal/com.oracle.graal.compiler.common/src/com/oracle/graal/compiler/common/cfg/AbstractControlFlowGraph.java	Tue Apr 14 13:37:47 2015 +0200
@@ -90,8 +90,9 @@
         while (f != null) {
             if (!f.dominated.hasNext()) { // Retreat
                 f.block.setDominatorNumbers(f.myNumber, f.maxNumber);
-                if (f.parent != null)
+                if (f.parent != null) {
                     f.parent.maxNumber = f.maxNumber;
+                }
                 f = f.parent;
             } else {
                 T d = f.dominated.next();
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/DominatorConditionalEliminationPhase.java	Fri Apr 10 16:22:46 2015 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/DominatorConditionalEliminationPhase.java	Tue Apr 14 13:37:47 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<InstanceFrame> {
             List<Runnable> 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<Runnable> undoOperations) {
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java	Fri Apr 10 16:22:46 2015 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java	Tue Apr 14 13:37:47 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<ProcessFrame> {
+            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:
+     *
+     * <pre>
+     * void processBlock(Block block) {
+     *     preprocess();
+     *     // Process always reached block first.
+     *     Block alwaysReachedBlock = block.getPostdominator();
+     *     if (alwaysReachedBlock != null &amp;&amp; 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();
+     * }
+     * </pre>
+     *
+     * 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<T extends Frame<?>> {
+        final Block block;
+        final T parent;
+        Iterator<Block> 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();
+    }
+
 }