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