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