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