Mercurial > hg > graal-compiler
changeset 14889:5accc969c8c7
use StatelessPostOrderNodeIterator in GraphOrder
author | Lukas Stadler <lukas.stadler@oracle.com> |
---|---|
date | Mon, 31 Mar 2014 13:45:40 +0200 |
parents | f6630873316b |
children | 8ebeb60167ee |
files | graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/MergeableState.java graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/StatelessPostOrderNodeIterator.java graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java |
diffstat | 3 files changed, 134 insertions(+), 14 deletions(-) [+] |
line wrap: on
line diff
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/MergeableState.java Mon Mar 31 10:03:32 2014 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/MergeableState.java Mon Mar 31 13:45:40 2014 +0200 @@ -61,17 +61,4 @@ public void afterSplit(AbstractBeginNode node) { // empty default implementation } - - public static final class EmptyState extends MergeableState<EmptyState> implements Cloneable { - - @Override - public EmptyState clone() { - return this; - } - - @Override - public boolean merge(MergeNode merge, List<EmptyState> withStates) { - return true; - } - } }
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/graph/StatelessPostOrderNodeIterator.java Mon Mar 31 13:45:40 2014 +0200 @@ -0,0 +1,133 @@ +/* + * Copyright (c) 2011, 2014, 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.nodes.*; + +/** + * This iterator implements a reverse post order iteration over the fixed nodes in the graph, + * starting at the given fixed node. + * + * No changes to the fixed nodes are expected during the iteration, they cause undefined behavior. + */ +public abstract class StatelessPostOrderNodeIterator { + + private final NodeBitMap visitedEnds; + private final Deque<AbstractBeginNode> nodeQueue; + private final FixedNode start; + + public StatelessPostOrderNodeIterator(FixedNode start) { + visitedEnds = start.graph().createNodeBitMap(); + nodeQueue = new ArrayDeque<>(); + this.start = start; + } + + public void apply() { + FixedNode current = start; + + do { + if (current instanceof LoopBeginNode) { + loopBegin((LoopBeginNode) current); + current = ((LoopBeginNode) current).next(); + assert current != null; + } else if (current instanceof LoopEndNode) { + loopEnd((LoopEndNode) current); + assert !visitedEnds.isMarked(current); + visitedEnds.mark(current); + current = nodeQueue.pollFirst(); + } else if (current instanceof MergeNode) { + merge((MergeNode) current); + current = ((MergeNode) current).next(); + assert current != null; + } else if (current instanceof FixedWithNextNode) { + node(current); + current = ((FixedWithNextNode) current).next(); + } else if (current instanceof EndNode) { + end((EndNode) current); + queueMerge((EndNode) current); + current = nodeQueue.pollFirst(); + } else if (current instanceof ControlSinkNode) { + node(current); + current = nodeQueue.pollFirst(); + } else if (current instanceof ControlSplitNode) { + controlSplit((ControlSplitNode) current); + for (Node node : current.successors()) { + if (node != null) { + nodeQueue.addFirst((AbstractBeginNode) node); + } + } + current = nodeQueue.pollFirst(); + } else { + assert false : current; + } + } while (current != null); + finished(); + } + + private void queueMerge(EndNode end) { + assert !visitedEnds.isMarked(end); + 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 void node(@SuppressWarnings("unused") FixedNode node) { + // empty default implementation + } + + 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 void controlSplit(ControlSplitNode controlSplit) { + node(controlSplit); + } + + protected void finished() { + // nothing to do + } +}
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java Mon Mar 31 10:03:32 2014 +0200 +++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/util/GraphOrder.java Mon Mar 31 13:45:40 2014 +0200 @@ -80,7 +80,7 @@ final ArrayList<Node> nodes = new ArrayList<>(); final NodeBitMap visited = graph.createNodeBitMap(); - new PostOrderNodeIterator<MergeableState.EmptyState>(graph.start(), new MergeableState.EmptyState()) { + new StatelessPostOrderNodeIterator(graph.start()) { @Override protected void node(FixedNode node) { visitForward(nodes, visited, node, false);