Mercurial > hg > truffle

changeset 20929:c617a74a9eab

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge
author Stefan Anzinger <stefan.anzinger@oracle.com>
date Tue, 14 Apr 2015 14:01:18 +0200
parents d9713313e88c (diff) cea0b7285190 (current diff)
children 143c532a550e
files graal/com.oracle.graal.graphbuilderconf/src/com/oracle/graal/graphbuilderconf/InvocationPluginIdHolder.java graal/com.oracle.truffle.api.test/src/com/oracle/truffle/api/test/instrument/ToolNodeInstrumentationTest.java graal/com.oracle.truffle.api/src/com/oracle/truffle/api/instrument/ASTInstrumentListener.java graal/com.oracle.truffle.api/src/com/oracle/truffle/api/instrument/InstrumentListener.java graal/com.oracle.truffle.api/src/com/oracle/truffle/api/instrument/ToolNode.java graal/com.oracle.truffle.api/src/com/oracle/truffle/api/instrument/ToolNodeInstrumentListener.java graal/com.oracle.truffle.api/src/com/oracle/truffle/api/instrument/impl/DefaultASTInstrumentListener.java graal/com.oracle.truffle.api/src/com/oracle/truffle/api/instrument/impl/DefaultInstrumentListener.java graal/com.oracle.truffle.api/src/com/oracle/truffle/api/instrument/impl/SimpleASTInstrumentListener.java graal/com.oracle.truffle.api/src/com/oracle/truffle/api/instrument/impl/SimpleInstrumentListener.java graal/com.oracle.truffle.api/src/com/oracle/truffle/api/source/StandardSourceTag.java
diffstat 3 files changed, 187 insertions(+), 41 deletions(-) [+]
line wrap: on
line diff
--- 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 <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);
+    static <T extends AbstractBlockBase<T>> void calcDominatorRanges(T block) {
+        final class Frame<T> {
+            int myNumber;
+            int maxNumber;
+            T block;
+            Iterator<T> dominated;
+            Frame<T> parent;
+
+            public Frame(int myNumber, T block, Iterator<T> dominated, Frame<T> parent) {
+                super();
+                this.myNumber = myNumber;
+                this.maxNumber = myNumber;
+                this.block = block;
+                this.dominated = dominated;
+                this.parent = parent;
+            }
         }
-        block.setDominatorNumbers(myNumber, maxNumber);
-        return maxNumber;
+        Frame<T> 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<T> dd = d.getDominated();
+                f = new Frame<>(f.maxNumber + 1, d, dd.iterator(), f);
+            }
+        }
     }
 
     /**
--- 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<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	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<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();
+    }
+
 }