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