Mercurial > hg > truffle

changeset 15585:4d5b1e7a4d93

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
[single-pass-iter] early pruning of state map, visit a whole method
author Miguel Garcia <miguel.m.garcia@oracle.com>
date Fri, 09 May 2014 17:33:14 +0200
parents 56ab99b480af
children 642bd083a5cc
files graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ConditionalEliminationPhase.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ValueAnchorCleanupPhase.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/BaseReduction.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/CheckCastReduction.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FixedGuardReduction.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowSensitiveReduction.java graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/GuardingPiReduction.java graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/SinglePassNodeIterator.java
diffstat 8 files changed, 53 insertions(+), 25 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ConditionalEliminationPhase.java	Fri May 09 16:50:27 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ConditionalEliminationPhase.java	Fri May 09 17:33:14 2014 +0200
@@ -337,7 +337,7 @@
         private final LogicNode trueConstant;
         private final LogicNode falseConstant;
 
-        public ConditionalElimination(FixedNode start, State initialState) {
+        public ConditionalElimination(StartNode start, State initialState) {
             super(start, initialState);
             trueConstant = LogicConstantNode.tautology(graph);
             falseConstant = LogicConstantNode.contradiction(graph);
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ValueAnchorCleanupPhase.java	Fri May 09 16:50:27 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ValueAnchorCleanupPhase.java	Fri May 09 17:33:14 2014 +0200
@@ -65,7 +65,7 @@
 
     private static class CleanupValueAnchorsClosure extends SinglePassNodeIterator<State> {
 
-        public CleanupValueAnchorsClosure(FixedNode start) {
+        public CleanupValueAnchorsClosure(StartNode start) {
             super(start, new State());
         }
 
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/BaseReduction.java	Fri May 09 16:50:27 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/BaseReduction.java	Fri May 09 17:33:14 2014 +0200
@@ -195,7 +195,7 @@
 
     protected final PostponedDeopts postponedDeopts = new PostponedDeopts();
 
-    protected BaseReduction(FixedNode start, State initialState, PhaseContext context) {
+    protected BaseReduction(StartNode start, State initialState, PhaseContext context) {
         super(start, initialState);
         graph = start.graph();
         trueConstant = LogicConstantNode.tautology(graph);
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/CheckCastReduction.java	Fri May 09 16:50:27 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/CheckCastReduction.java	Fri May 09 17:33:14 2014 +0200
@@ -50,7 +50,7 @@
  */
 public abstract class CheckCastReduction extends GuardingPiReduction {
 
-    public CheckCastReduction(FixedNode start, State initialState, PhaseContext context) {
+    public CheckCastReduction(StartNode start, State initialState, PhaseContext context) {
         super(start, initialState, context);
     }
 
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FixedGuardReduction.java	Fri May 09 16:50:27 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FixedGuardReduction.java	Fri May 09 17:33:14 2014 +0200
@@ -41,7 +41,7 @@
  */
 public abstract class FixedGuardReduction extends CheckCastReduction {
 
-    public FixedGuardReduction(FixedNode start, State initialState, PhaseContext context) {
+    public FixedGuardReduction(StartNode start, State initialState, PhaseContext context) {
         super(start, initialState, context);
     }
 
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowSensitiveReduction.java	Fri May 09 16:50:27 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/FlowSensitiveReduction.java	Fri May 09 17:33:14 2014 +0200
@@ -98,7 +98,7 @@
  */
 public class FlowSensitiveReduction extends FixedGuardReduction {
 
-    public FlowSensitiveReduction(FixedNode start, State initialState, PhaseContext context) {
+    public FlowSensitiveReduction(StartNode start, State initialState, PhaseContext context) {
         super(start, initialState, context);
     }
 
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/GuardingPiReduction.java	Fri May 09 16:50:27 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/GuardingPiReduction.java	Fri May 09 17:33:14 2014 +0200
@@ -47,7 +47,7 @@
  */
 public abstract class GuardingPiReduction extends BaseReduction {
 
-    public GuardingPiReduction(FixedNode start, State initialState, PhaseContext context) {
+    public GuardingPiReduction(StartNode start, State initialState, PhaseContext context) {
         super(start, initialState, context);
     }
 
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/SinglePassNodeIterator.java	Fri May 09 16:50:27 2014 +0200
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/SinglePassNodeIterator.java	Fri May 09 17:33:14 2014 +0200
@@ -29,10 +29,9 @@
 import com.oracle.graal.nodes.*;
 
 /**
- * A SinglePassNodeIterator iterates the fixed nodes of the graph in post order starting from a
- * specified fixed node. Unlike in iterative dataflow analysis, a single pass is performed, which
- * allows keeping a smaller working set of pending {@link MergeableState}. This iteration scheme
- * requires:
+ * A SinglePassNodeIterator iterates the fixed nodes of the graph in post order starting from its
+ * start node. Unlike in iterative dataflow analysis, a single pass is performed, which allows
+ * keeping a smaller working set of pending {@link MergeableState}. This iteration scheme requires:
  * <ul>
  * <li>{@link MergeableState#merge(MergeNode, List)} to always return <code>true</code> (an
  * assertion checks this)</li>
@@ -59,11 +58,11 @@
     private final NodeBitMap visitedEnds;
     private final Deque<BeginNode> nodeQueue;
     private final Map<FixedNode, T> nodeStates;
-    private final FixedNode start;
+    private final StartNode start;
 
     protected T state;
 
-    public SinglePassNodeIterator(FixedNode start, T initialState) {
+    public SinglePassNodeIterator(StartNode start, T initialState) {
         StructuredGraph graph = start.graph();
         visitedEnds = graph.createNodeBitMap();
         nodeQueue = new ArrayDeque<>();
@@ -136,17 +135,26 @@
         }
     }
 
+    /**
+     * This method is invoked upon not having a (single) next {@link FixedNode} to visit. This
+     * method picks such next-node-to-visit from {@link #nodeQueue} and updates {@link #state} with
+     * the pre-state for that node.
+     *
+     * <p>
+     * Upon reaching a {@link MergeNode}, some entries are pruned from {@link #nodeStates} (ie, the
+     * entries associated to forward-ends for that merge-node).
+     * </p>
+     */
     private FixedNode nextQueuedNode() {
         int maxIterations = nodeQueue.size();
         while (maxIterations-- > 0) {
             BeginNode node = nodeQueue.removeFirst();
             if (node instanceof MergeNode) {
                 MergeNode merge = (MergeNode) node;
-                state = nodeStates.get(merge.forwardEndAt(0)).clone();
+                state = pruneEntry(merge.forwardEndAt(0)).clone();
                 ArrayList<T> states = new ArrayList<>(merge.forwardEndCount() - 1);
                 for (int i = 1; i < merge.forwardEndCount(); i++) {
-                    T other = nodeStates.get(merge.forwardEndAt(i));
-                    assert other != null;
+                    T other = pruneEntry(merge.forwardEndAt(i));
                     states.add(other);
                 }
                 boolean ready = state.merge(merge, states);
@@ -162,11 +170,18 @@
         return null;
     }
 
+    /**
+     * Once all loop-end-nodes for a given loop-node have been visited:
+     * <ul>
+     * <li>the state for that loop-node is updated based on the states of the loop-end-nodes</li>
+     * <li>entries in {@link #nodeStates} are pruned for the loop (they aren't going to be looked up
+     * again, anyway)</li>
+     * </ul>
+     */
     private void finishLoopEnds(LoopEndNode end) {
         assert !visitedEnds.isMarked(end);
-        assert !nodeStates.containsKey(end);
+        visitedEnds.mark(end);
         keepForLater(end, state);
-        visitedEnds.mark(end);
         LoopBeginNode begin = end.loopBegin();
         boolean endsVisited = true;
         for (LoopEndNode le : begin.loopEnds()) {
@@ -178,20 +193,27 @@
         if (endsVisited) {
             ArrayList<T> states = new ArrayList<>(begin.loopEnds().count());
             for (LoopEndNode le : begin.orderedLoopEnds()) {
-                states.add(nodeStates.get(le));
+                T leState = pruneEntry(le);
+                states.add(leState);
             }
-            T loopBeginState = nodeStates.get(begin);
-            if (loopBeginState != null) {
-                loopBeginState.loopEnds(begin, states);
-            }
+            T loopBeginState = pruneEntry(begin);
+            loopBeginState.loopEnds(begin, states);
         }
     }
 
+    /**
+     * Once all end-nodes for a given merge-node have been visited, that merge-node is added to the
+     * {@link #nodeQueue}
+     *
+     * <p>
+     * {@link #nextQueuedNode()} is in charge of pruning entries for the states of forward-ends
+     * inserted by this method.
+     * </p>
+     */
     private void queueMerge(EndNode end) {
         assert !visitedEnds.isMarked(end);
-        assert !nodeStates.containsKey(end);
+        visitedEnds.mark(end);
         keepForLater(end, state);
-        visitedEnds.mark(end);
         MergeNode merge = end.merge();
         boolean endsVisited = true;
         for (int i = 0; i < merge.forwardEndCount(); i++) {
@@ -242,4 +264,10 @@
         assert !nodeStates.containsKey(x);
         nodeStates.put(x, s);
     }
+
+    private T pruneEntry(FixedNode x) {
+        T result = nodeStates.remove(x);
+        assert result != null;
+        return result;
+    }
 }