1 /* 2 * Copyright (c) 2011, 2015, 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.nodes; 24 25 import static org.graalvm.compiler.graph.iterators.NodePredicates.isNotA; 26 27 import org.graalvm.compiler.core.common.type.IntegerStamp; 28 import org.graalvm.compiler.graph.IterableNodeType; 29 import org.graalvm.compiler.graph.Node; 30 import org.graalvm.compiler.graph.NodeClass; 31 import org.graalvm.compiler.graph.iterators.NodeIterable; 32 import org.graalvm.compiler.graph.spi.SimplifierTool; 33 import org.graalvm.compiler.nodeinfo.InputType; 34 import org.graalvm.compiler.nodeinfo.NodeInfo; 35 import org.graalvm.compiler.nodes.calc.AddNode; 36 import org.graalvm.compiler.nodes.extended.GuardingNode; 37 import org.graalvm.compiler.nodes.spi.LIRLowerable; 38 import org.graalvm.compiler.nodes.spi.NodeLIRBuilderTool; 39 import org.graalvm.compiler.nodes.util.GraphUtil; 40 41 @NodeInfo 42 public final class LoopBeginNode extends AbstractMergeNode implements IterableNodeType, LIRLowerable { 43 44 public static final NodeClass<LoopBeginNode> TYPE = NodeClass.create(LoopBeginNode.class); 45 protected double loopFrequency; 46 protected int nextEndIndex; 47 protected int unswitches; 48 protected int inversionCount; 49 50 /** See {@link LoopEndNode#canSafepoint} for more information. */ 51 boolean canEndsSafepoint; 52 53 @OptionalInput(InputType.Guard) GuardingNode overflowGuard; 54 55 public LoopBeginNode() { 56 super(TYPE); 57 loopFrequency = 1; 58 this.canEndsSafepoint = true; 59 } 60 61 /** Disables safepoint for the whole loop, i.e., for all {@link LoopEndNode loop ends}. */ 62 public void disableSafepoint() { 63 /* Store flag locally in case new loop ends are created later on. */ 64 this.canEndsSafepoint = false; 65 /* Propagate flag to all existing loop ends. */ 66 for (LoopEndNode loopEnd : loopEnds()) { 67 loopEnd.disableSafepoint(); 68 } 69 } 70 71 public double loopFrequency() { 72 return loopFrequency; 73 } 74 75 public void setLoopFrequency(double loopFrequency) { 76 assert loopFrequency >= 0; 77 this.loopFrequency = loopFrequency; 78 } 79 80 /** 81 * Returns the <b>unordered</b> set of {@link LoopEndNode} that correspond to back-edges for 82 * this loop. The order of the back-edges is unspecified, if you need to get an ordering 83 * compatible for {@link PhiNode} creation, use {@link #orderedLoopEnds()}. 84 * 85 * @return the set of {@code LoopEndNode} that correspond to back-edges for this loop 86 */ 87 public NodeIterable<LoopEndNode> loopEnds() { 88 return usages().filter(LoopEndNode.class); 89 } 90 91 public NodeIterable<LoopExitNode> loopExits() { 92 return usages().filter(LoopExitNode.class); 93 } 94 95 @Override 96 public NodeIterable<Node> anchored() { 97 return super.anchored().filter(isNotA(LoopEndNode.class).nor(LoopExitNode.class)); 98 } 99 100 /** 101 * Returns the set of {@link LoopEndNode} that correspond to back-edges for this loop, in 102 * increasing {@link #phiPredecessorIndex} order. This method is suited to create new loop 103 * {@link PhiNode}.<br> 104 * 105 * For example a new PhiNode may be added as follow: 106 * 107 * <pre> 108 * PhiNode phi = new ValuePhiNode(stamp, loop); 109 * phi.addInput(forwardEdgeValue); 110 * for (LoopEndNode loopEnd : loop.orderedLoopEnds()) { 111 * phi.addInput(backEdgeValue(loopEnd)); 112 * } 113 * </pre> 114 * 115 * @return the set of {@code LoopEndNode} that correspond to back-edges for this loop 116 */ 117 public LoopEndNode[] orderedLoopEnds() { 118 LoopEndNode[] result = new LoopEndNode[this.getLoopEndCount()]; 119 for (LoopEndNode end : loopEnds()) { 120 result[end.endIndex()] = end; 121 } 122 return result; 123 } 124 125 public AbstractEndNode forwardEnd() { 126 assert forwardEndCount() == 1; 127 return forwardEndAt(0); 128 } 129 130 @Override 131 public void generate(NodeLIRBuilderTool gen) { 132 // Nothing to emit, since this is node is used for structural purposes only. 133 } 134 135 @Override 136 protected void deleteEnd(AbstractEndNode end) { 137 if (end instanceof LoopEndNode) { 138 LoopEndNode loopEnd = (LoopEndNode) end; 139 loopEnd.setLoopBegin(null); 140 int idx = loopEnd.endIndex(); 141 for (LoopEndNode le : loopEnds()) { 142 int leIdx = le.endIndex(); 143 assert leIdx != idx; 144 if (leIdx > idx) { 145 le.setEndIndex(leIdx - 1); 146 } 147 } 148 nextEndIndex--; 149 } else { 150 super.deleteEnd(end); 151 } 152 } 153 154 @Override 155 public int phiPredecessorCount() { 156 return forwardEndCount() + loopEnds().count(); 157 } 158 159 @Override 160 public int phiPredecessorIndex(AbstractEndNode pred) { 161 if (pred instanceof LoopEndNode) { 162 LoopEndNode loopEnd = (LoopEndNode) pred; 163 if (loopEnd.loopBegin() == this) { 164 assert loopEnd.endIndex() < loopEnds().count() : "Invalid endIndex : " + loopEnd; 165 return loopEnd.endIndex() + forwardEndCount(); 166 } 167 } else { 168 return super.forwardEndIndex((EndNode) pred); 169 } 170 throw ValueNodeUtil.shouldNotReachHere("unknown pred : " + pred); 171 } 172 173 @Override 174 public AbstractEndNode phiPredecessorAt(int index) { 175 if (index < forwardEndCount()) { 176 return forwardEndAt(index); 177 } 178 for (LoopEndNode end : loopEnds()) { 179 int idx = index - forwardEndCount(); 180 assert idx >= 0; 181 if (end.endIndex() == idx) { 182 return end; 183 } 184 } 185 throw ValueNodeUtil.shouldNotReachHere(); 186 } 187 188 @Override 189 public boolean verify() { 190 assertTrue(loopEnds().isNotEmpty(), "missing loopEnd"); 191 return super.verify(); 192 } 193 194 int nextEndIndex() { 195 return nextEndIndex++; 196 } 197 198 public int getLoopEndCount() { 199 return nextEndIndex; 200 } 201 202 public int unswitches() { 203 return unswitches; 204 } 205 206 public void incrementUnswitches() { 207 unswitches++; 208 } 209 210 public int getInversionCount() { 211 return inversionCount; 212 } 213 214 public void setInversionCount(int count) { 215 inversionCount = count; 216 } 217 218 @Override 219 public void simplify(SimplifierTool tool) { 220 canonicalizePhis(tool); 221 } 222 223 public boolean isLoopExit(AbstractBeginNode begin) { 224 return begin instanceof LoopExitNode && ((LoopExitNode) begin).loopBegin() == this; 225 } 226 227 public void removeExits() { 228 for (LoopExitNode loopexit : loopExits().snapshot()) { 229 loopexit.removeProxies(); 230 FrameState loopStateAfter = loopexit.stateAfter(); 231 graph().replaceFixedWithFixed(loopexit, graph().add(new BeginNode())); 232 if (loopStateAfter != null && loopStateAfter.isAlive() && loopStateAfter.hasNoUsages()) { 233 GraphUtil.killWithUnusedFloatingInputs(loopStateAfter); 234 } 235 } 236 } 237 238 public GuardingNode getOverflowGuard() { 239 return overflowGuard; 240 } 241 242 public void setOverflowGuard(GuardingNode overflowGuard) { 243 updateUsagesInterface(this.overflowGuard, overflowGuard); 244 this.overflowGuard = overflowGuard; 245 } 246 247 private static final int NO_INCREMENT = Integer.MIN_VALUE; 248 249 /** 250 * Returns an array with one entry for each input of the phi, which is either 251 * {@link #NO_INCREMENT} or the increment, i.e., the value by which the phi is incremented in 252 * the corresponding branch. 253 */ 254 private static int[] getSelfIncrements(PhiNode phi) { 255 int[] selfIncrement = new int[phi.valueCount()]; 256 for (int i = 0; i < phi.valueCount(); i++) { 257 ValueNode input = phi.valueAt(i); 258 long increment = NO_INCREMENT; 259 if (input != null && input instanceof AddNode && input.stamp() instanceof IntegerStamp) { 260 AddNode add = (AddNode) input; 261 if (add.getX() == phi && add.getY().isConstant()) { 262 increment = add.getY().asJavaConstant().asLong(); 263 } else if (add.getY() == phi && add.getX().isConstant()) { 264 increment = add.getX().asJavaConstant().asLong(); 265 } 266 } else if (input == phi) { 267 increment = 0; 268 } 269 if (increment < Integer.MIN_VALUE || increment > Integer.MAX_VALUE || increment == NO_INCREMENT) { 270 increment = NO_INCREMENT; 271 } 272 selfIncrement[i] = (int) increment; 273 } 274 return selfIncrement; 275 } 276 277 /** 278 * Coalesces loop phis that represent the same value (which is not handled by normal Global 279 * Value Numbering). 280 */ 281 public void canonicalizePhis(SimplifierTool tool) { 282 int phiCount = phis().count(); 283 if (phiCount > 1) { 284 int phiInputCount = phiPredecessorCount(); 285 int phiIndex = 0; 286 int[][] selfIncrement = new int[phiCount][]; 287 PhiNode[] phis = this.phis().snapshot().toArray(new PhiNode[phiCount]); 288 289 for (phiIndex = 0; phiIndex < phiCount; phiIndex++) { 290 PhiNode phi = phis[phiIndex]; 291 if (phi != null) { 292 nextPhi: for (int otherPhiIndex = phiIndex + 1; otherPhiIndex < phiCount; otherPhiIndex++) { 293 PhiNode otherPhi = phis[otherPhiIndex]; 294 if (otherPhi == null || phi.getNodeClass() != otherPhi.getNodeClass() || !phi.valueEquals(otherPhi)) { 295 continue nextPhi; 296 } 297 if (selfIncrement[phiIndex] == null) { 298 selfIncrement[phiIndex] = getSelfIncrements(phi); 299 } 300 if (selfIncrement[otherPhiIndex] == null) { 301 selfIncrement[otherPhiIndex] = getSelfIncrements(otherPhi); 302 } 303 int[] phiIncrement = selfIncrement[phiIndex]; 304 int[] otherPhiIncrement = selfIncrement[otherPhiIndex]; 305 for (int inputIndex = 0; inputIndex < phiInputCount; inputIndex++) { 306 if (phiIncrement[inputIndex] == NO_INCREMENT) { 307 if (phi.valueAt(inputIndex) != otherPhi.valueAt(inputIndex)) { 308 continue nextPhi; 309 } 310 } 311 if (phiIncrement[inputIndex] != otherPhiIncrement[inputIndex]) { 312 continue nextPhi; 313 } 314 } 315 if (tool != null) { 316 tool.addToWorkList(otherPhi.usages()); 317 } 318 otherPhi.replaceAtUsages(phi); 319 GraphUtil.killWithUnusedFloatingInputs(otherPhi); 320 phis[otherPhiIndex] = null; 321 } 322 } 323 } 324 } 325 } 326 }