1 /* 2 * Copyright (c) 2013, 2018, 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 24 25 package org.graalvm.compiler.phases.graph; 26 27 import java.util.ArrayDeque; 28 import java.util.Deque; 29 30 import org.graalvm.compiler.graph.Node; 31 import org.graalvm.compiler.graph.NodeBitMap; 32 import org.graalvm.compiler.graph.iterators.NodeIterable; 33 import org.graalvm.compiler.nodes.AbstractEndNode; 34 import org.graalvm.compiler.nodes.AbstractMergeNode; 35 import org.graalvm.compiler.nodes.ControlSinkNode; 36 import org.graalvm.compiler.nodes.ControlSplitNode; 37 import org.graalvm.compiler.nodes.EndNode; 38 import org.graalvm.compiler.nodes.FixedNode; 39 import org.graalvm.compiler.nodes.FixedWithNextNode; 40 import org.graalvm.compiler.nodes.Invoke; 41 import org.graalvm.compiler.nodes.LoopBeginNode; 42 import org.graalvm.compiler.nodes.LoopEndNode; 43 import org.graalvm.compiler.nodes.LoopExitNode; 44 import org.graalvm.compiler.nodes.StructuredGraph; 45 46 public abstract class ScopedPostOrderNodeIterator { 47 48 private final Deque<FixedNode> nodeQueue; 49 private final NodeBitMap queuedNodes; 50 private final Deque<FixedNode> scopes; 51 52 protected FixedNode currentScopeStart; 53 ScopedPostOrderNodeIterator(StructuredGraph graph)54 public ScopedPostOrderNodeIterator(StructuredGraph graph) { 55 this.queuedNodes = graph.createNodeBitMap(); 56 this.nodeQueue = new ArrayDeque<>(); 57 this.scopes = getScopes(graph); 58 } 59 apply()60 public void apply() { 61 while (!scopes.isEmpty()) { 62 queuedNodes.clearAll(); 63 this.currentScopeStart = scopes.pop(); 64 initializeScope(); 65 processScope(); 66 } 67 } 68 processScope()69 public void processScope() { 70 FixedNode current; 71 queue(currentScopeStart); 72 73 while ((current = nextQueuedNode()) != null) { 74 assert current.isAlive(); 75 76 if (current instanceof Invoke) { 77 invoke((Invoke) current); 78 queueSuccessors(current); 79 } else if (current instanceof LoopBeginNode) { 80 queueLoopBeginSuccessors((LoopBeginNode) current); 81 } else if (current instanceof LoopExitNode) { 82 queueLoopExitSuccessors((LoopExitNode) current); 83 } else if (current instanceof LoopEndNode) { 84 // nothing todo 85 } else if (current instanceof AbstractMergeNode) { 86 queueSuccessors(current); 87 } else if (current instanceof FixedWithNextNode) { 88 queueSuccessors(current); 89 } else if (current instanceof EndNode) { 90 queueMerge((EndNode) current); 91 } else if (current instanceof ControlSinkNode) { 92 // nothing todo 93 } else if (current instanceof ControlSplitNode) { 94 queueSuccessors(current); 95 } else { 96 assert false : current; 97 } 98 } 99 } 100 queueLoopBeginSuccessors(LoopBeginNode node)101 protected void queueLoopBeginSuccessors(LoopBeginNode node) { 102 if (currentScopeStart == node) { 103 queue(node.next()); 104 } else if (currentScopeStart instanceof LoopBeginNode) { 105 // so we are currently processing loop A and found another loop B 106 // -> queue all loop exits of B except those that also exit loop A 107 for (LoopExitNode loopExit : node.loopExits()) { 108 if (!((LoopBeginNode) currentScopeStart).loopExits().contains(loopExit)) { 109 queue(loopExit); 110 } 111 } 112 } else { 113 queue(node.loopExits()); 114 } 115 } 116 queueLoopExitSuccessors(LoopExitNode node)117 protected void queueLoopExitSuccessors(LoopExitNode node) { 118 if (!(currentScopeStart instanceof LoopBeginNode) || !((LoopBeginNode) currentScopeStart).loopExits().contains(node)) { 119 queueSuccessors(node); 120 } 121 } 122 getScopes(StructuredGraph graph)123 protected Deque<FixedNode> getScopes(StructuredGraph graph) { 124 Deque<FixedNode> result = new ArrayDeque<>(); 125 result.push(graph.start()); 126 for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.TYPE)) { 127 result.push(loopBegin); 128 } 129 return result; 130 } 131 queueSuccessors(FixedNode x)132 private void queueSuccessors(FixedNode x) { 133 queue(x.successors()); 134 } 135 queue(NodeIterable<? extends Node> iter)136 private void queue(NodeIterable<? extends Node> iter) { 137 for (Node node : iter) { 138 queue(node); 139 } 140 } 141 queue(Node node)142 private void queue(Node node) { 143 if (node != null && !queuedNodes.isMarked(node)) { 144 queuedNodes.mark(node); 145 nodeQueue.addFirst((FixedNode) node); 146 } 147 } 148 nextQueuedNode()149 private FixedNode nextQueuedNode() { 150 if (nodeQueue.isEmpty()) { 151 return null; 152 } 153 154 FixedNode result = nodeQueue.removeFirst(); 155 assert queuedNodes.isMarked(result); 156 return result; 157 } 158 queueMerge(AbstractEndNode end)159 private void queueMerge(AbstractEndNode end) { 160 AbstractMergeNode merge = end.merge(); 161 if (!queuedNodes.isMarked(merge) && visitedAllEnds(merge)) { 162 queue(merge); 163 } 164 } 165 visitedAllEnds(AbstractMergeNode merge)166 private boolean visitedAllEnds(AbstractMergeNode merge) { 167 for (int i = 0; i < merge.forwardEndCount(); i++) { 168 if (!queuedNodes.isMarked(merge.forwardEndAt(i))) { 169 return false; 170 } 171 } 172 return true; 173 } 174 initializeScope()175 protected abstract void initializeScope(); 176 invoke(Invoke invoke)177 protected abstract void invoke(Invoke invoke); 178 } 179