1 /* 2 * Copyright (c) 2011, 2014, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 package org.graalvm.compiler.phases.graph; 24 25 import java.util.ArrayDeque; 26 import java.util.Deque; 27 28 import org.graalvm.compiler.graph.Node; 29 import org.graalvm.compiler.graph.NodeBitMap; 30 import org.graalvm.compiler.nodes.AbstractBeginNode; 31 import org.graalvm.compiler.nodes.AbstractMergeNode; 32 import org.graalvm.compiler.nodes.ControlSinkNode; 33 import org.graalvm.compiler.nodes.ControlSplitNode; 34 import org.graalvm.compiler.nodes.EndNode; 35 import org.graalvm.compiler.nodes.FixedNode; 36 import org.graalvm.compiler.nodes.FixedWithNextNode; 37 import org.graalvm.compiler.nodes.LoopBeginNode; 38 import org.graalvm.compiler.nodes.LoopEndNode; 39 40 /** 41 * This iterator implements a reverse post order iteration over the fixed nodes in the graph, 42 * starting at the given fixed node. 43 * 44 * No changes to the fixed nodes are expected during the iteration, they cause undefined behavior. 45 */ 46 public abstract class StatelessPostOrderNodeIterator { 47 48 private final NodeBitMap visitedEnds; 49 private final Deque<AbstractBeginNode> nodeQueue; 50 private final FixedNode start; 51 52 public StatelessPostOrderNodeIterator(FixedNode start) { 53 visitedEnds = start.graph().createNodeBitMap(); 54 nodeQueue = new ArrayDeque<>(); 55 this.start = start; 56 } 57 58 public void apply() { 59 FixedNode current = start; 60 61 do { 62 if (current instanceof LoopBeginNode) { 63 loopBegin((LoopBeginNode) current); 64 current = ((LoopBeginNode) current).next(); 65 assert current != null; 66 } else if (current instanceof LoopEndNode) { 67 loopEnd((LoopEndNode) current); 68 assert !visitedEnds.isMarked(current); 69 visitedEnds.mark(current); 70 current = nodeQueue.pollFirst(); 71 } else if (current instanceof AbstractMergeNode) { 72 merge((AbstractMergeNode) current); 73 current = ((AbstractMergeNode) current).next(); 74 assert current != null; 75 } else if (current instanceof FixedWithNextNode) { 76 node(current); 77 current = ((FixedWithNextNode) current).next(); 78 } else if (current instanceof EndNode) { 79 end((EndNode) current); 80 queueMerge((EndNode) current); 81 current = nodeQueue.pollFirst(); 82 } else if (current instanceof ControlSinkNode) { 83 node(current); 84 current = nodeQueue.pollFirst(); 85 } else if (current instanceof ControlSplitNode) { 86 controlSplit((ControlSplitNode) current); 87 for (Node node : current.successors()) { 88 nodeQueue.addFirst((AbstractBeginNode) node); 89 } 90 current = nodeQueue.pollFirst(); 91 } else { 92 assert false : current; 93 } 94 } while (current != null); 95 finished(); 96 } 97 98 private void queueMerge(EndNode end) { 99 assert !visitedEnds.isMarked(end); 100 visitedEnds.mark(end); 101 AbstractMergeNode merge = end.merge(); 102 boolean endsVisited = true; 103 for (int i = 0; i < merge.forwardEndCount(); i++) { 104 if (!visitedEnds.isMarked(merge.forwardEndAt(i))) { 105 endsVisited = false; 106 break; 107 } 108 } 109 if (endsVisited) { 110 nodeQueue.add(merge); 111 } 112 } 113 114 protected void node(@SuppressWarnings("unused") FixedNode node) { 115 // empty default implementation 116 } 117 118 protected void end(EndNode endNode) { 119 node(endNode); 120 } 121 122 protected void merge(AbstractMergeNode merge) { 123 node(merge); 124 } 125 126 protected void loopBegin(LoopBeginNode loopBegin) { 127 node(loopBegin); 128 } 129 130 protected void loopEnd(LoopEndNode loopEnd) { 131 node(loopEnd); 132 } 133 134 protected void controlSplit(ControlSplitNode controlSplit) { 135 node(controlSplit); 136 } 137 138 protected void finished() { 139 // nothing to do 140 } 141 }