1 /* 2 * Copyright (c) 2009, 2011, 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.nodes; 26 27 import static org.graalvm.compiler.nodeinfo.InputType.Association; 28 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_0; 29 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_0; 30 31 import java.util.List; 32 33 import org.graalvm.compiler.debug.DebugCloseable; 34 import org.graalvm.compiler.graph.IterableNodeType; 35 import org.graalvm.compiler.graph.Node; 36 import org.graalvm.compiler.graph.NodeClass; 37 import org.graalvm.compiler.graph.NodeInputList; 38 import org.graalvm.compiler.graph.iterators.NodeIterable; 39 import org.graalvm.compiler.graph.spi.Simplifiable; 40 import org.graalvm.compiler.graph.spi.SimplifierTool; 41 import org.graalvm.compiler.nodeinfo.NodeInfo; 42 import org.graalvm.compiler.nodes.memory.MemoryPhiNode; 43 import org.graalvm.compiler.nodes.spi.LIRLowerable; 44 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool; 45 import org.graalvm.compiler.nodes.util.GraphUtil; 46 47 /** 48 * Denotes the merging of multiple control-flow paths. 49 */ 50 @NodeInfo(allowedUsageTypes = Association, cycles = CYCLES_0, size = SIZE_0) 51 public abstract class AbstractMergeNode extends BeginStateSplitNode implements IterableNodeType, Simplifiable, LIRLowerable { 52 public static final NodeClass<AbstractMergeNode> TYPE = NodeClass.create(AbstractMergeNode.class); 53 AbstractMergeNode(NodeClass<? extends AbstractMergeNode> c)54 protected AbstractMergeNode(NodeClass<? extends AbstractMergeNode> c) { 55 super(c); 56 } 57 58 @Input(Association) protected NodeInputList<EndNode> ends = new NodeInputList<>(this); 59 60 @Override generate(NodeLIRBuilderTool gen)61 public void generate(NodeLIRBuilderTool gen) { 62 gen.visitMerge(this); 63 } 64 forwardEndIndex(EndNode end)65 public int forwardEndIndex(EndNode end) { 66 return ends.indexOf(end); 67 } 68 addForwardEnd(EndNode end)69 public void addForwardEnd(EndNode end) { 70 ends.add(end); 71 } 72 forwardEndCount()73 public final int forwardEndCount() { 74 return ends.size(); 75 } 76 forwardEndAt(int index)77 public final EndNode forwardEndAt(int index) { 78 return ends.get(index); 79 } 80 81 @Override cfgPredecessors()82 public NodeIterable<EndNode> cfgPredecessors() { 83 return ends; 84 } 85 86 /** 87 * Determines if a given node is a phi whose {@linkplain PhiNode#merge() merge} is this node. 88 * 89 * @param value the instruction to test 90 * @return {@code true} if {@code value} is a phi and its merge is {@code this} 91 */ isPhiAtMerge(Node value)92 public boolean isPhiAtMerge(Node value) { 93 return value instanceof PhiNode && ((PhiNode) value).merge() == this; 94 } 95 96 /** 97 * Removes the given end from the merge, along with the entries corresponding to this end in the 98 * phis connected to the merge. 99 * 100 * @param pred the end to remove 101 */ removeEnd(AbstractEndNode pred)102 public void removeEnd(AbstractEndNode pred) { 103 int predIndex = phiPredecessorIndex(pred); 104 assert predIndex != -1; 105 deleteEnd(pred); 106 for (PhiNode phi : phis().snapshot()) { 107 if (phi.isDeleted()) { 108 continue; 109 } 110 ValueNode removedValue = phi.valueAt(predIndex); 111 phi.removeInput(predIndex); 112 if (removedValue != null) { 113 GraphUtil.tryKillUnused(removedValue); 114 } 115 } 116 } 117 deleteEnd(AbstractEndNode end)118 protected void deleteEnd(AbstractEndNode end) { 119 ends.remove(end); 120 } 121 clearEnds()122 public void clearEnds() { 123 ends.clear(); 124 } 125 forwardEnds()126 public NodeInputList<EndNode> forwardEnds() { 127 return ends; 128 } 129 phiPredecessorCount()130 public int phiPredecessorCount() { 131 return forwardEndCount(); 132 } 133 phiPredecessorIndex(AbstractEndNode pred)134 public int phiPredecessorIndex(AbstractEndNode pred) { 135 return forwardEndIndex((EndNode) pred); 136 } 137 phiPredecessorAt(int index)138 public AbstractEndNode phiPredecessorAt(int index) { 139 return forwardEndAt(index); 140 } 141 phis()142 public NodeIterable<PhiNode> phis() { 143 return this.usages().filter(PhiNode.class).filter(this::isPhiAtMerge); 144 } 145 valuePhis()146 public NodeIterable<ValuePhiNode> valuePhis() { 147 return this.usages().filter(ValuePhiNode.class); 148 } 149 memoryPhis()150 public NodeIterable<MemoryPhiNode> memoryPhis() { 151 return this.usages().filter(MemoryPhiNode.class); 152 } 153 154 @Override anchored()155 public NodeIterable<Node> anchored() { 156 return super.anchored().filter(n -> !isPhiAtMerge(n)); 157 } 158 159 /** 160 * This simplify method can deal with a null value for tool, so that it can be used outside of 161 * canonicalization. 162 */ 163 @Override 164 @SuppressWarnings("try") simplify(SimplifierTool tool)165 public void simplify(SimplifierTool tool) { 166 FixedNode currentNext = next(); 167 if (currentNext instanceof AbstractEndNode) { 168 AbstractEndNode origLoopEnd = (AbstractEndNode) currentNext; 169 AbstractMergeNode merge = origLoopEnd.merge(); 170 if (merge instanceof LoopBeginNode && !(origLoopEnd instanceof LoopEndNode)) { 171 return; 172 } 173 // in order to move anchored values to the other merge we would need to check if the 174 // anchors are used by phis of the other merge 175 if (this.anchored().isNotEmpty()) { 176 return; 177 } 178 if (merge.stateAfter() == null && this.stateAfter() != null) { 179 // We hold a state, but the succeeding merge does not => do not combine. 180 return; 181 } 182 for (PhiNode phi : phis()) { 183 for (Node usage : phi.usages()) { 184 if (!(usage instanceof VirtualState) && !merge.isPhiAtMerge(usage)) { 185 return; 186 } 187 } 188 } 189 getDebug().log("Split %s into ends for %s.", this, merge); 190 int numEnds = this.forwardEndCount(); 191 for (int i = 0; i < numEnds - 1; i++) { 192 AbstractEndNode end = forwardEndAt(numEnds - 1 - i); 193 if (tool != null) { 194 tool.addToWorkList(end); 195 } 196 AbstractEndNode newEnd; 197 try (DebugCloseable position = end.withNodeSourcePosition()) { 198 if (merge instanceof LoopBeginNode) { 199 newEnd = graph().add(new LoopEndNode((LoopBeginNode) merge)); 200 } else { 201 EndNode tmpEnd = graph().add(new EndNode()); 202 merge.addForwardEnd(tmpEnd); 203 newEnd = tmpEnd; 204 } 205 } 206 for (PhiNode phi : merge.phis()) { 207 ValueNode v = phi.valueAt(origLoopEnd); 208 ValueNode newInput; 209 if (isPhiAtMerge(v)) { 210 PhiNode endPhi = (PhiNode) v; 211 newInput = endPhi.valueAt(end); 212 } else { 213 newInput = v; 214 } 215 phi.addInput(newInput); 216 } 217 this.removeEnd(end); 218 end.replaceAtPredecessor(newEnd); 219 end.safeDelete(); 220 if (tool != null) { 221 tool.addToWorkList(newEnd.predecessor()); 222 } 223 } 224 graph().reduceTrivialMerge(this); 225 } else if (currentNext instanceof ReturnNode) { 226 ReturnNode returnNode = (ReturnNode) currentNext; 227 if (anchored().isNotEmpty() || returnNode.getMemoryMap() != null) { 228 return; 229 } 230 List<PhiNode> phis = phis().snapshot(); 231 for (PhiNode phi : phis) { 232 for (Node usage : phi.usages()) { 233 if (usage != returnNode && !(usage instanceof FrameState)) { 234 return; 235 } 236 } 237 } 238 239 ValuePhiNode returnValuePhi = returnNode.result() == null || !isPhiAtMerge(returnNode.result()) ? null : (ValuePhiNode) returnNode.result(); 240 List<EndNode> endNodes = forwardEnds().snapshot(); 241 for (EndNode end : endNodes) { 242 try (DebugCloseable position = returnNode.withNodeSourcePosition()) { 243 ReturnNode newReturn = graph().add(new ReturnNode(returnValuePhi == null ? returnNode.result() : returnValuePhi.valueAt(end))); 244 if (tool != null) { 245 tool.addToWorkList(end.predecessor()); 246 } 247 end.replaceAtPredecessor(newReturn); 248 } 249 } 250 GraphUtil.killCFG(this); 251 for (EndNode end : endNodes) { 252 end.safeDelete(); 253 } 254 for (PhiNode phi : phis) { 255 if (tool.allUsagesAvailable() && phi.isAlive() && phi.hasNoUsages()) { 256 GraphUtil.killWithUnusedFloatingInputs(phi); 257 } 258 } 259 } 260 } 261 } 262