1/* 2 * Copyright (c) 2012, 2016, 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 */ 23package org.graalvm.compiler.loop; 24 25import java.util.ArrayList; 26import java.util.LinkedList; 27import java.util.List; 28 29import org.graalvm.compiler.debug.DebugContext; 30import org.graalvm.compiler.debug.GraalError; 31import org.graalvm.compiler.graph.Graph.DuplicationReplacement; 32import org.graalvm.compiler.graph.Node; 33import org.graalvm.compiler.graph.NodeBitMap; 34import org.graalvm.compiler.graph.iterators.NodeIterable; 35import org.graalvm.compiler.nodes.AbstractBeginNode; 36import org.graalvm.compiler.nodes.AbstractEndNode; 37import org.graalvm.compiler.nodes.AbstractMergeNode; 38import org.graalvm.compiler.nodes.BeginNode; 39import org.graalvm.compiler.nodes.ConstantNode; 40import org.graalvm.compiler.nodes.EndNode; 41import org.graalvm.compiler.nodes.FixedNode; 42import org.graalvm.compiler.nodes.FixedWithNextNode; 43import org.graalvm.compiler.nodes.FrameState; 44import org.graalvm.compiler.nodes.GuardPhiNode; 45import org.graalvm.compiler.nodes.IfNode; 46import org.graalvm.compiler.nodes.LogicNode; 47import org.graalvm.compiler.nodes.LoopBeginNode; 48import org.graalvm.compiler.nodes.LoopEndNode; 49import org.graalvm.compiler.nodes.LoopExitNode; 50import org.graalvm.compiler.nodes.MergeNode; 51import org.graalvm.compiler.nodes.PhiNode; 52import org.graalvm.compiler.nodes.ProxyNode; 53import org.graalvm.compiler.nodes.SafepointNode; 54import org.graalvm.compiler.nodes.StateSplit; 55import org.graalvm.compiler.nodes.StructuredGraph; 56import org.graalvm.compiler.nodes.ValueNode; 57import org.graalvm.compiler.nodes.ValuePhiNode; 58import org.graalvm.compiler.nodes.VirtualState.NodeClosure; 59import org.graalvm.compiler.nodes.calc.AddNode; 60import org.graalvm.compiler.nodes.calc.CompareNode; 61import org.graalvm.compiler.nodes.calc.SubNode; 62import org.graalvm.compiler.nodes.memory.MemoryPhiNode; 63import org.graalvm.compiler.nodes.util.GraphUtil; 64import org.graalvm.util.EconomicMap; 65import org.graalvm.util.Equivalence; 66 67public class LoopFragmentInside extends LoopFragment { 68 69 /** 70 * mergedInitializers. When an inside fragment's (loop)ends are merged to create a unique exit 71 * point, some phis must be created : they phis together all the back-values of the loop-phis 72 * These can then be used to update the loop-phis' forward edge value ('initializer') in the 73 * peeling case. In the unrolling case they will be used as the value that replace the loop-phis 74 * of the duplicated inside fragment 75 */ 76 private EconomicMap<PhiNode, ValueNode> mergedInitializers; 77 private final DuplicationReplacement dataFixBefore = new DuplicationReplacement() { 78 79 @Override 80 public Node replacement(Node oriInput) { 81 if (!(oriInput instanceof ValueNode)) { 82 return oriInput; 83 } 84 return prim((ValueNode) oriInput); 85 } 86 }; 87 88 private final DuplicationReplacement dataFixWithinAfter = new DuplicationReplacement() { 89 90 @Override 91 public Node replacement(Node oriInput) { 92 if (!(oriInput instanceof ValueNode)) { 93 return oriInput; 94 } 95 return primAfter((ValueNode) oriInput); 96 } 97 }; 98 99 public LoopFragmentInside(LoopEx loop) { 100 super(loop); 101 } 102 103 public LoopFragmentInside(LoopFragmentInside original) { 104 super(null, original); 105 } 106 107 @Override 108 public LoopFragmentInside duplicate() { 109 assert !isDuplicate(); 110 return new LoopFragmentInside(this); 111 } 112 113 @Override 114 public LoopFragmentInside original() { 115 return (LoopFragmentInside) super.original(); 116 } 117 118 @SuppressWarnings("unused") 119 public void appendInside(LoopEx loop) { 120 // TODO (gd) 121 } 122 123 @Override 124 public LoopEx loop() { 125 assert !this.isDuplicate(); 126 return super.loop(); 127 } 128 129 @Override 130 public void insertBefore(LoopEx loop) { 131 assert this.isDuplicate() && this.original().loop() == loop; 132 133 patchNodes(dataFixBefore); 134 135 AbstractBeginNode end = mergeEnds(); 136 137 mergeEarlyExits(); 138 139 original().patchPeeling(this); 140 141 AbstractBeginNode entry = getDuplicatedNode(loop.loopBegin()); 142 loop.entryPoint().replaceAtPredecessor(entry); 143 end.setNext(loop.entryPoint()); 144 } 145 146 /** 147 * Duplicate the body within the loop after the current copy copy of the body, updating the 148 * iteration limit to account for the duplication. 149 * 150 * @param loop 151 */ 152 public void insertWithinAfter(LoopEx loop) { 153 insertWithinAfter(loop, true); 154 } 155 156 /** 157 * Duplicate the body within the loop after the current copy copy of the body. 158 * 159 * @param loop 160 * @param updateLimit true if the iteration limit should be adjusted. 161 */ 162 public void insertWithinAfter(LoopEx loop, boolean updateLimit) { 163 assert isDuplicate() && original().loop() == loop; 164 165 patchNodes(dataFixWithinAfter); 166 167 /* 168 * Collect any new back edges values before updating them since they might reference each 169 * other. 170 */ 171 LoopBeginNode mainLoopBegin = loop.loopBegin(); 172 ArrayList<ValueNode> backedgeValues = new ArrayList<>(); 173 for (PhiNode mainPhiNode : mainLoopBegin.phis()) { 174 ValueNode duplicatedNode = getDuplicatedNode(mainPhiNode.valueAt(1)); 175 if (duplicatedNode == null) { 176 if (mainLoopBegin.isPhiAtMerge(mainPhiNode.valueAt(1))) { 177 duplicatedNode = ((PhiNode) (mainPhiNode.valueAt(1))).valueAt(1); 178 } else { 179 assert mainPhiNode.valueAt(1).isConstant() : mainPhiNode.valueAt(1); 180 } 181 } 182 backedgeValues.add(duplicatedNode); 183 } 184 int index = 0; 185 for (PhiNode mainPhiNode : mainLoopBegin.phis()) { 186 ValueNode duplicatedNode = backedgeValues.get(index++); 187 if (duplicatedNode != null) { 188 mainPhiNode.setValueAt(1, duplicatedNode); 189 } 190 } 191 192 placeNewSegmentAndCleanup(loop); 193 194 // Remove any safepoints from the original copy leaving only the duplicated one 195 assert loop.whole().nodes().filter(SafepointNode.class).count() == nodes().filter(SafepointNode.class).count(); 196 for (SafepointNode safepoint : loop.whole().nodes().filter(SafepointNode.class)) { 197 graph().removeFixed(safepoint); 198 } 199 200 int unrollFactor = mainLoopBegin.getUnrollFactor(); 201 StructuredGraph graph = mainLoopBegin.graph(); 202 if (updateLimit) { 203 // Now use the previous unrollFactor to update the exit condition to power of two 204 InductionVariable iv = loop.counted().getCounter(); 205 CompareNode compareNode = (CompareNode) loop.counted().getLimitTest().condition(); 206 ValueNode compareBound; 207 if (compareNode.getX() == iv.valueNode()) { 208 compareBound = compareNode.getY(); 209 } else if (compareNode.getY() == iv.valueNode()) { 210 compareBound = compareNode.getX(); 211 } else { 212 throw GraalError.shouldNotReachHere(); 213 } 214 long originalStride = unrollFactor == 1 ? iv.constantStride() : iv.constantStride() / unrollFactor; 215 if (iv.direction() == InductionVariable.Direction.Up) { 216 ConstantNode aboveVal = graph.unique(ConstantNode.forIntegerStamp(iv.initNode().stamp(), unrollFactor * originalStride)); 217 ValueNode newLimit = graph.addWithoutUnique(new SubNode(compareBound, aboveVal)); 218 compareNode.replaceFirstInput(compareBound, newLimit); 219 } else if (iv.direction() == InductionVariable.Direction.Down) { 220 ConstantNode aboveVal = graph.unique(ConstantNode.forIntegerStamp(iv.initNode().stamp(), unrollFactor * -originalStride)); 221 ValueNode newLimit = graph.addWithoutUnique(new AddNode(compareBound, aboveVal)); 222 compareNode.replaceFirstInput(compareBound, newLimit); 223 } 224 } 225 mainLoopBegin.setUnrollFactor(unrollFactor * 2); 226 mainLoopBegin.setLoopFrequency(mainLoopBegin.loopFrequency() / 2); 227 graph.getDebug().dump(DebugContext.DETAILED_LEVEL, graph, "LoopPartialUnroll %s", loop); 228 229 mainLoopBegin.getDebug().dump(DebugContext.VERBOSE_LEVEL, mainLoopBegin.graph(), "After insertWithinAfter %s", mainLoopBegin); 230 } 231 232 private void placeNewSegmentAndCleanup(LoopEx loop) { 233 CountedLoopInfo mainCounted = loop.counted(); 234 LoopBeginNode mainLoopBegin = loop.loopBegin(); 235 // Discard the segment entry and its flow, after if merging it into the loop 236 StructuredGraph graph = mainLoopBegin.graph(); 237 IfNode loopTest = mainCounted.getLimitTest(); 238 IfNode newSegmentTest = getDuplicatedNode(loopTest); 239 AbstractBeginNode trueSuccessor = loopTest.trueSuccessor(); 240 AbstractBeginNode falseSuccessor = loopTest.falseSuccessor(); 241 FixedNode firstNode; 242 boolean codeInTrueSide = false; 243 if (trueSuccessor == mainCounted.getBody()) { 244 firstNode = trueSuccessor.next(); 245 codeInTrueSide = true; 246 } else { 247 assert (falseSuccessor == mainCounted.getBody()); 248 firstNode = falseSuccessor.next(); 249 } 250 trueSuccessor = newSegmentTest.trueSuccessor(); 251 falseSuccessor = newSegmentTest.falseSuccessor(); 252 for (Node usage : falseSuccessor.anchored().snapshot()) { 253 usage.replaceFirstInput(falseSuccessor, loopTest.falseSuccessor()); 254 } 255 for (Node usage : trueSuccessor.anchored().snapshot()) { 256 usage.replaceFirstInput(trueSuccessor, loopTest.trueSuccessor()); 257 } 258 AbstractBeginNode startBlockNode; 259 if (codeInTrueSide) { 260 startBlockNode = trueSuccessor; 261 } else { 262 graph.getDebug().dump(DebugContext.VERBOSE_LEVEL, mainLoopBegin.graph(), "before"); 263 startBlockNode = falseSuccessor; 264 } 265 FixedNode lastNode = getBlockEnd(startBlockNode); 266 LoopEndNode loopEndNode = mainLoopBegin.getSingleLoopEnd(); 267 FixedWithNextNode lastCodeNode = (FixedWithNextNode) loopEndNode.predecessor(); 268 FixedNode newSegmentFirstNode = getDuplicatedNode(firstNode); 269 FixedWithNextNode newSegmentLastNode = getDuplicatedNode(lastCodeNode); 270 graph.getDebug().dump(DebugContext.DETAILED_LEVEL, loopEndNode.graph(), "Before placing segment"); 271 if (firstNode instanceof LoopEndNode) { 272 GraphUtil.killCFG(getDuplicatedNode(mainLoopBegin)); 273 } else { 274 newSegmentLastNode.clearSuccessors(); 275 startBlockNode.setNext(lastNode); 276 lastCodeNode.replaceFirstSuccessor(loopEndNode, newSegmentFirstNode); 277 newSegmentLastNode.replaceFirstSuccessor(lastNode, loopEndNode); 278 lastCodeNode.setNext(newSegmentFirstNode); 279 newSegmentLastNode.setNext(loopEndNode); 280 startBlockNode.clearSuccessors(); 281 lastNode.safeDelete(); 282 Node newSegmentTestStart = newSegmentTest.predecessor(); 283 LogicNode newSegmentIfTest = newSegmentTest.condition(); 284 newSegmentTestStart.clearSuccessors(); 285 newSegmentTest.safeDelete(); 286 newSegmentIfTest.safeDelete(); 287 trueSuccessor.safeDelete(); 288 falseSuccessor.safeDelete(); 289 newSegmentTestStart.safeDelete(); 290 } 291 graph.getDebug().dump(DebugContext.DETAILED_LEVEL, loopEndNode.graph(), "After placing segment"); 292 } 293 294 private static EndNode getBlockEnd(FixedNode node) { 295 FixedNode curNode = node; 296 while (curNode instanceof FixedWithNextNode) { 297 curNode = ((FixedWithNextNode) curNode).next(); 298 } 299 return (EndNode) curNode; 300 } 301 302 @Override 303 public NodeBitMap nodes() { 304 if (nodes == null) { 305 LoopFragmentWhole whole = loop().whole(); 306 whole.nodes(); // init nodes bitmap in whole 307 nodes = whole.nodes.copy(); 308 // remove the phis 309 LoopBeginNode loopBegin = loop().loopBegin(); 310 for (PhiNode phi : loopBegin.phis()) { 311 nodes.clear(phi); 312 } 313 clearStateNodes(loopBegin); 314 for (LoopExitNode exit : exits()) { 315 clearStateNodes(exit); 316 for (ProxyNode proxy : exit.proxies()) { 317 nodes.clear(proxy); 318 } 319 } 320 } 321 return nodes; 322 } 323 324 private void clearStateNodes(StateSplit stateSplit) { 325 FrameState loopState = stateSplit.stateAfter(); 326 if (loopState != null) { 327 loopState.applyToVirtual(v -> { 328 if (v.usages().filter(n -> nodes.isMarked(n) && n != stateSplit).isEmpty()) { 329 nodes.clear(v); 330 } 331 }); 332 } 333 } 334 335 public NodeIterable<LoopExitNode> exits() { 336 return loop().loopBegin().loopExits(); 337 } 338 339 @Override 340 protected DuplicationReplacement getDuplicationReplacement() { 341 final LoopBeginNode loopBegin = loop().loopBegin(); 342 final StructuredGraph graph = graph(); 343 return new DuplicationReplacement() { 344 345 private EconomicMap<Node, Node> seenNode = EconomicMap.create(Equivalence.IDENTITY); 346 347 @Override 348 public Node replacement(Node original) { 349 if (original == loopBegin) { 350 Node value = seenNode.get(original); 351 if (value != null) { 352 return value; 353 } 354 AbstractBeginNode newValue = graph.add(new BeginNode()); 355 seenNode.put(original, newValue); 356 return newValue; 357 } 358 if (original instanceof LoopExitNode && ((LoopExitNode) original).loopBegin() == loopBegin) { 359 Node value = seenNode.get(original); 360 if (value != null) { 361 return value; 362 } 363 AbstractBeginNode newValue = graph.add(new BeginNode()); 364 seenNode.put(original, newValue); 365 return newValue; 366 } 367 if (original instanceof LoopEndNode && ((LoopEndNode) original).loopBegin() == loopBegin) { 368 Node value = seenNode.get(original); 369 if (value != null) { 370 return value; 371 } 372 EndNode newValue = graph.add(new EndNode()); 373 seenNode.put(original, newValue); 374 return newValue; 375 } 376 return original; 377 } 378 }; 379 } 380 381 @Override 382 protected void finishDuplication() { 383 // TODO (gd) ? 384 } 385 386 @Override 387 protected void beforeDuplication() { 388 // Nothing to do 389 } 390 391 private static PhiNode patchPhi(StructuredGraph graph, PhiNode phi, AbstractMergeNode merge) { 392 PhiNode ret; 393 if (phi instanceof ValuePhiNode) { 394 ret = new ValuePhiNode(phi.stamp(), merge); 395 } else if (phi instanceof GuardPhiNode) { 396 ret = new GuardPhiNode(merge); 397 } else if (phi instanceof MemoryPhiNode) { 398 ret = new MemoryPhiNode(merge, ((MemoryPhiNode) phi).getLocationIdentity()); 399 } else { 400 throw GraalError.shouldNotReachHere(); 401 } 402 return graph.addWithoutUnique(ret); 403 } 404 405 private void patchPeeling(LoopFragmentInside peel) { 406 LoopBeginNode loopBegin = loop().loopBegin(); 407 StructuredGraph graph = loopBegin.graph(); 408 List<PhiNode> newPhis = new LinkedList<>(); 409 410 NodeBitMap usagesToPatch = nodes.copy(); 411 for (LoopExitNode exit : exits()) { 412 markStateNodes(exit, usagesToPatch); 413 for (ProxyNode proxy : exit.proxies()) { 414 usagesToPatch.markAndGrow(proxy); 415 } 416 } 417 markStateNodes(loopBegin, usagesToPatch); 418 419 List<PhiNode> oldPhis = loopBegin.phis().snapshot(); 420 for (PhiNode phi : oldPhis) { 421 if (phi.hasNoUsages()) { 422 continue; 423 } 424 ValueNode first; 425 if (loopBegin.loopEnds().count() == 1) { 426 ValueNode b = phi.valueAt(loopBegin.loopEnds().first()); // back edge value 427 first = peel.prim(b); // corresponding value in the peel 428 } else { 429 first = peel.mergedInitializers.get(phi); 430 } 431 // create a new phi (we don't patch the old one since some usages of the old one may 432 // still be valid) 433 PhiNode newPhi = patchPhi(graph, phi, loopBegin); 434 newPhi.addInput(first); 435 for (LoopEndNode end : loopBegin.orderedLoopEnds()) { 436 newPhi.addInput(phi.valueAt(end)); 437 } 438 peel.putDuplicatedNode(phi, newPhi); 439 newPhis.add(newPhi); 440 for (Node usage : phi.usages().snapshot()) { 441 // patch only usages that should use the new phi ie usages that were peeled 442 if (usagesToPatch.isMarkedAndGrow(usage)) { 443 usage.replaceFirstInput(phi, newPhi); 444 } 445 } 446 } 447 // check new phis to see if they have as input some old phis, replace those inputs with the 448 // new corresponding phis 449 for (PhiNode phi : newPhis) { 450 for (int i = 0; i < phi.valueCount(); i++) { 451 ValueNode v = phi.valueAt(i); 452 if (loopBegin.isPhiAtMerge(v)) { 453 PhiNode newV = peel.getDuplicatedNode((ValuePhiNode) v); 454 if (newV != null) { 455 phi.setValueAt(i, newV); 456 } 457 } 458 } 459 } 460 461 boolean progress = true; 462 while (progress) { 463 progress = false; 464 int i = 0; 465 outer: while (i < oldPhis.size()) { 466 PhiNode oldPhi = oldPhis.get(i); 467 for (Node usage : oldPhi.usages()) { 468 if (usage instanceof PhiNode && oldPhis.contains(usage)) { 469 // Do not mark. 470 } else { 471 // Mark alive by removing from delete set. 472 oldPhis.remove(i); 473 progress = true; 474 continue outer; 475 } 476 } 477 i++; 478 } 479 } 480 481 for (PhiNode deadPhi : oldPhis) { 482 deadPhi.clearInputs(); 483 } 484 485 for (PhiNode deadPhi : oldPhis) { 486 if (deadPhi.isAlive()) { 487 GraphUtil.killWithUnusedFloatingInputs(deadPhi); 488 } 489 } 490 } 491 492 private static void markStateNodes(StateSplit stateSplit, NodeBitMap marks) { 493 FrameState exitState = stateSplit.stateAfter(); 494 if (exitState != null) { 495 exitState.applyToVirtual(v -> marks.markAndGrow(v)); 496 } 497 } 498 499 /** 500 * Gets the corresponding value in this fragment. 501 * 502 * @param b original value 503 * @return corresponding value in the peel 504 */ 505 @Override 506 protected ValueNode prim(ValueNode b) { 507 assert isDuplicate(); 508 LoopBeginNode loopBegin = original().loop().loopBegin(); 509 if (loopBegin.isPhiAtMerge(b)) { 510 PhiNode phi = (PhiNode) b; 511 return phi.valueAt(loopBegin.forwardEnd()); 512 } else if (nodesReady) { 513 ValueNode v = getDuplicatedNode(b); 514 if (v == null) { 515 return b; 516 } 517 return v; 518 } else { 519 return b; 520 } 521 } 522 523 protected ValueNode primAfter(ValueNode b) { 524 assert isDuplicate(); 525 LoopBeginNode loopBegin = original().loop().loopBegin(); 526 if (loopBegin.isPhiAtMerge(b)) { 527 PhiNode phi = (PhiNode) b; 528 assert phi.valueCount() == 2; 529 return phi.valueAt(1); 530 } else if (nodesReady) { 531 ValueNode v = getDuplicatedNode(b); 532 if (v == null) { 533 return b; 534 } 535 return v; 536 } else { 537 return b; 538 } 539 } 540 541 private AbstractBeginNode mergeEnds() { 542 assert isDuplicate(); 543 List<EndNode> endsToMerge = new LinkedList<>(); 544 // map peel exits to the corresponding loop exits 545 EconomicMap<AbstractEndNode, LoopEndNode> reverseEnds = EconomicMap.create(Equivalence.IDENTITY); 546 LoopBeginNode loopBegin = original().loop().loopBegin(); 547 for (LoopEndNode le : loopBegin.loopEnds()) { 548 AbstractEndNode duplicate = getDuplicatedNode(le); 549 if (duplicate != null) { 550 endsToMerge.add((EndNode) duplicate); 551 reverseEnds.put(duplicate, le); 552 } 553 } 554 mergedInitializers = EconomicMap.create(Equivalence.IDENTITY); 555 AbstractBeginNode newExit; 556 StructuredGraph graph = graph(); 557 if (endsToMerge.size() == 1) { 558 AbstractEndNode end = endsToMerge.get(0); 559 assert end.hasNoUsages(); 560 newExit = graph.add(new BeginNode()); 561 end.replaceAtPredecessor(newExit); 562 end.safeDelete(); 563 } else { 564 assert endsToMerge.size() > 1; 565 AbstractMergeNode newExitMerge = graph.add(new MergeNode()); 566 newExit = newExitMerge; 567 FrameState state = loopBegin.stateAfter(); 568 FrameState duplicateState = null; 569 if (state != null) { 570 duplicateState = state.duplicateWithVirtualState(); 571 newExitMerge.setStateAfter(duplicateState); 572 } 573 for (EndNode end : endsToMerge) { 574 newExitMerge.addForwardEnd(end); 575 } 576 577 for (final PhiNode phi : loopBegin.phis().snapshot()) { 578 if (phi.hasNoUsages()) { 579 continue; 580 } 581 final PhiNode firstPhi = patchPhi(graph, phi, newExitMerge); 582 for (AbstractEndNode end : newExitMerge.forwardEnds()) { 583 LoopEndNode loopEnd = reverseEnds.get(end); 584 ValueNode prim = prim(phi.valueAt(loopEnd)); 585 assert prim != null; 586 firstPhi.addInput(prim); 587 } 588 ValueNode initializer = firstPhi; 589 if (duplicateState != null) { 590 // fix the merge's state after 591 duplicateState.applyToNonVirtual(new NodeClosure<ValueNode>() { 592 593 @Override 594 public void apply(Node from, ValueNode node) { 595 if (node == phi) { 596 from.replaceFirstInput(phi, firstPhi); 597 } 598 } 599 }); 600 } 601 mergedInitializers.put(phi, initializer); 602 } 603 } 604 return newExit; 605 } 606} 607