# HG changeset patch
# User Miguel Garcia
# Date 1399645374 -7200
# Node ID d331b7c3d7c4217c81ad780d652f63dd8b374cc8
# Parent 9a5b5a5b22461e34567f5044c550093f92957737
[single-pass-iter] start of evolution towards a node iterator less memory-hungry
diff -r 9a5b5a5b2246 -r d331b7c3d7c4 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ConditionalEliminationPhase.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ConditionalEliminationPhase.java Fri May 09 14:45:48 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ConditionalEliminationPhase.java Fri May 09 16:22:54 2014 +0200
@@ -332,7 +332,7 @@
}
}
- public class ConditionalElimination extends PostOrderNodeIterator {
+ public class ConditionalElimination extends SinglePassNodeIterator {
private final LogicNode trueConstant;
private final LogicNode falseConstant;
diff -r 9a5b5a5b2246 -r d331b7c3d7c4 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ValueAnchorCleanupPhase.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ValueAnchorCleanupPhase.java Fri May 09 14:45:48 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ValueAnchorCleanupPhase.java Fri May 09 16:22:54 2014 +0200
@@ -63,7 +63,7 @@
}
}
- private static class CleanupValueAnchorsClosure extends PostOrderNodeIterator {
+ private static class CleanupValueAnchorsClosure extends SinglePassNodeIterator {
public CleanupValueAnchorsClosure(FixedNode start) {
super(start, new State());
diff -r 9a5b5a5b2246 -r d331b7c3d7c4 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/BaseReduction.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/BaseReduction.java Fri May 09 14:45:48 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/cfs/BaseReduction.java Fri May 09 16:22:54 2014 +0200
@@ -30,7 +30,7 @@
import com.oracle.graal.graph.spi.CanonicalizerTool;
import com.oracle.graal.nodes.*;
import com.oracle.graal.compiler.common.type.ObjectStamp;
-import com.oracle.graal.phases.graph.PostOrderNodeIterator;
+import com.oracle.graal.phases.graph.SinglePassNodeIterator;
import com.oracle.graal.phases.tiers.PhaseContext;
import java.util.ArrayList;
@@ -55,7 +55,7 @@
*
*
*/
-public abstract class BaseReduction extends PostOrderNodeIterator {
+public abstract class BaseReduction extends SinglePassNodeIterator {
protected static final DebugMetric metricCheckCastRemoved = Debug.metric("FSR-CheckCastRemoved");
protected static final DebugMetric metricGuardingPiNodeRemoved = Debug.metric("FSR-GuardingPiNodeRemoved");
diff -r 9a5b5a5b2246 -r d331b7c3d7c4 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/SinglePassNodeIterator.java
--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/SinglePassNodeIterator.java Fri May 09 16:22:54 2014 +0200
@@ -0,0 +1,251 @@
+/*
+ * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package com.oracle.graal.phases.graph;
+
+import java.util.*;
+
+import com.oracle.graal.graph.*;
+import com.oracle.graal.graph.util.*;
+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:
+ *
+ * - {@link MergeableState#merge(MergeNode, List)} to always return
true
(an
+ * assertion checks this)
+ * - {@link #controlSplit(ControlSplitNode)} to always return all successors (otherwise, not all
+ * associated {@link EndNode} will be visited. In turn, visiting all the end nodes for a given
+ * {@link MergeNode} is a precondition before that merge node can be visited)
+ *
+ *
+ *
+ * For this iterator the CFG is defined by the classical CFG nodes (
+ * {@link com.oracle.graal.nodes.ControlSplitNode}, {@link com.oracle.graal.nodes.MergeNode}...) and
+ * the {@link com.oracle.graal.nodes.FixedWithNextNode#next() next} pointers of
+ * {@link com.oracle.graal.nodes.FixedWithNextNode}.
+ *
+ *
+ *
+ * The lifecycle that single-pass node iterators go through is described in {@link #apply()}
+ *
+ *
+ * @param the type of {@link MergeableState} handled by this SinglePassNodeIterator
+ */
+public abstract class SinglePassNodeIterator> {
+
+ private final NodeBitMap visitedEnds;
+ private final Deque nodeQueue;
+ private final Map nodeStates;
+ private final FixedNode start;
+
+ protected T state;
+
+ public SinglePassNodeIterator(FixedNode start, T initialState) {
+ StructuredGraph graph = start.graph();
+ visitedEnds = graph.createNodeBitMap();
+ nodeQueue = new ArrayDeque<>();
+ nodeStates = CollectionsAccess.newNodeIdentityMap();
+ this.start = start;
+ this.state = initialState;
+ }
+
+ /**
+ * Performs a single-pass iteration.
+ *
+ *
+ * After this method has been invoked, the {@link SinglePassNodeIterator} instance can't be used
+ * again. This saves clearing up fields in {@link #finished()}, the assumption being that this
+ * instance will be garbage-collected soon afterwards.
+ *
+ */
+ public void apply() {
+ FixedNode current = start;
+
+ do {
+ if (current instanceof InvokeWithExceptionNode) {
+ invoke((Invoke) current);
+ queueSuccessors(current, null);
+ current = nextQueuedNode();
+ } else if (current instanceof LoopBeginNode) {
+ state.loopBegin((LoopBeginNode) current);
+ nodeStates.put(current, state);
+ state = state.clone();
+ loopBegin((LoopBeginNode) current);
+ current = ((LoopBeginNode) current).next();
+ assert current != null;
+ } else if (current instanceof LoopEndNode) {
+ loopEnd((LoopEndNode) current);
+ finishLoopEnds((LoopEndNode) current);
+ current = nextQueuedNode();
+ } else if (current instanceof MergeNode) {
+ merge((MergeNode) current);
+ current = ((MergeNode) current).next();
+ assert current != null;
+ } else if (current instanceof FixedWithNextNode) {
+ FixedNode next = ((FixedWithNextNode) current).next();
+ assert next != null : current;
+ node(current);
+ current = next;
+ } else if (current instanceof EndNode) {
+ end((EndNode) current);
+ queueMerge((EndNode) current);
+ current = nextQueuedNode();
+ } else if (current instanceof ControlSinkNode) {
+ node(current);
+ current = nextQueuedNode();
+ } else if (current instanceof ControlSplitNode) {
+ Set successors = controlSplit((ControlSplitNode) current);
+ queueSuccessors(current, successors);
+ current = nextQueuedNode();
+ } else {
+ assert false : current;
+ }
+ } while (current != null);
+ finished();
+ }
+
+ private void queueSuccessors(FixedNode x, Set successors) {
+ nodeStates.put(x, state);
+ if (successors != null) {
+ for (Node node : successors) {
+ if (node != null) {
+ nodeStates.put((FixedNode) node.predecessor(), state);
+ nodeQueue.addFirst((BeginNode) node);
+ }
+ }
+ } else {
+ for (Node node : x.successors()) {
+ if (node != null) {
+ nodeQueue.addFirst((BeginNode) node);
+ }
+ }
+ }
+ }
+
+ 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();
+ ArrayList states = new ArrayList<>(merge.forwardEndCount() - 1);
+ for (int i = 1; i < merge.forwardEndCount(); i++) {
+ T other = nodeStates.get(merge.forwardEndAt(i));
+ assert other != null;
+ states.add(other);
+ }
+ boolean ready = state.merge(merge, states);
+ assert ready;
+ if (ready) {
+ return merge;
+ } else {
+ nodeQueue.addLast(merge);
+ }
+ } else {
+ assert node.predecessor() != null;
+ state = nodeStates.get(node.predecessor()).clone();
+ state.afterSplit(node);
+ return node;
+ }
+ }
+ return null;
+ }
+
+ private void finishLoopEnds(LoopEndNode end) {
+ assert !visitedEnds.isMarked(end);
+ assert !nodeStates.containsKey(end);
+ nodeStates.put(end, state);
+ visitedEnds.mark(end);
+ LoopBeginNode begin = end.loopBegin();
+ boolean endsVisited = true;
+ for (LoopEndNode le : begin.loopEnds()) {
+ if (!visitedEnds.isMarked(le)) {
+ endsVisited = false;
+ break;
+ }
+ }
+ if (endsVisited) {
+ ArrayList states = new ArrayList<>(begin.loopEnds().count());
+ for (LoopEndNode le : begin.orderedLoopEnds()) {
+ states.add(nodeStates.get(le));
+ }
+ T loopBeginState = nodeStates.get(begin);
+ if (loopBeginState != null) {
+ loopBeginState.loopEnds(begin, states);
+ }
+ }
+ }
+
+ private void queueMerge(EndNode end) {
+ assert !visitedEnds.isMarked(end);
+ assert !nodeStates.containsKey(end);
+ nodeStates.put(end, state);
+ visitedEnds.mark(end);
+ MergeNode merge = end.merge();
+ boolean endsVisited = true;
+ for (int i = 0; i < merge.forwardEndCount(); i++) {
+ if (!visitedEnds.isMarked(merge.forwardEndAt(i))) {
+ endsVisited = false;
+ break;
+ }
+ }
+ if (endsVisited) {
+ nodeQueue.add(merge);
+ }
+ }
+
+ protected abstract void node(FixedNode node);
+
+ protected void end(EndNode endNode) {
+ node(endNode);
+ }
+
+ protected void merge(MergeNode merge) {
+ node(merge);
+ }
+
+ protected void loopBegin(LoopBeginNode loopBegin) {
+ node(loopBegin);
+ }
+
+ protected void loopEnd(LoopEndNode loopEnd) {
+ node(loopEnd);
+ }
+
+ protected Set controlSplit(ControlSplitNode controlSplit) {
+ node(controlSplit);
+ return null;
+ }
+
+ protected void invoke(Invoke invoke) {
+ node(invoke.asNode());
+ }
+
+ protected void finished() {
+ // nothing to do
+ }
+}