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 beforeDuplication() {
 395         // Nothing to do
 396     }
 397 
 398     private static PhiNode patchPhi(StructuredGraph graph, PhiNode phi, AbstractMergeNode merge) {
 399         PhiNode ret;
 400         if (phi instanceof ValuePhiNode) {
 401             ret = new ValuePhiNode(phi.stamp(NodeView.DEFAULT), merge);
 402         } else if (phi instanceof GuardPhiNode) {
 403             ret = new GuardPhiNode(merge);
 404         } else if (phi instanceof MemoryPhiNode) {
 405             ret = new MemoryPhiNode(merge, ((MemoryPhiNode) phi).getLocationIdentity());
 406         } else {
 407             throw GraalError.shouldNotReachHere();
 408         }
 409         return graph.addWithoutUnique(ret);
 410     }
 411 
 412     private void patchPeeling(LoopFragmentInside peel) {
 413         LoopBeginNode loopBegin = loop().loopBegin();
 414         StructuredGraph graph = loopBegin.graph();
 415         List<PhiNode> newPhis = new LinkedList<>();
 416 
 417         NodeBitMap usagesToPatch = nodes.copy();
 418         for (LoopExitNode exit : exits()) {
 419             markStateNodes(exit, usagesToPatch);
 420             for (ProxyNode proxy : exit.proxies()) {
 421                 usagesToPatch.markAndGrow(proxy);
 422             }
 423         }
 424         markStateNodes(loopBegin, usagesToPatch);
 425 
 426         List<PhiNode> oldPhis = loopBegin.phis().snapshot();
 427         for (PhiNode phi : oldPhis) {
 428             if (phi.hasNoUsages()) {
 429                 continue;
 430             }
 431             ValueNode first;
 432             if (loopBegin.loopEnds().count() == 1) {
 433                 ValueNode b = phi.valueAt(loopBegin.loopEnds().first()); // back edge value
 434                 first = peel.prim(b); // corresponding value in the peel
 435             } else {
 436                 first = peel.mergedInitializers.get(phi);
 437             }
 438             // create a new phi (we don't patch the old one since some usages of the old one may
 439             // still be valid)
 440             PhiNode newPhi = patchPhi(graph, phi, loopBegin);
 441             newPhi.addInput(first);
 442             for (LoopEndNode end : loopBegin.orderedLoopEnds()) {
 443                 newPhi.addInput(phi.valueAt(end));
 444             }
 445             peel.putDuplicatedNode(phi, newPhi);
 446             newPhis.add(newPhi);
 447             for (Node usage : phi.usages().snapshot()) {
 448                 // patch only usages that should use the new phi ie usages that were peeled
 449                 if (usagesToPatch.isMarkedAndGrow(usage)) {
 450                     usage.replaceFirstInput(phi, newPhi);
 451                 }
 452             }
 453         }
 454         // check new phis to see if they have as input some old phis, replace those inputs with the
 455         // new corresponding phis
 456         for (PhiNode phi : newPhis) {
 457             for (int i = 0; i < phi.valueCount(); i++) {
 458                 ValueNode v = phi.valueAt(i);
 459                 if (loopBegin.isPhiAtMerge(v)) {
 460                     PhiNode newV = peel.getDuplicatedNode((ValuePhiNode) v);
 461                     if (newV != null) {
 462                         phi.setValueAt(i, newV);
 463                     }
 464                 }
 465             }
 466         }
 467 
 468         boolean progress = true;
 469         while (progress) {
 470             progress = false;
 471             int i = 0;
 472             outer: while (i < oldPhis.size()) {
 473                 PhiNode oldPhi = oldPhis.get(i);
 474                 for (Node usage : oldPhi.usages()) {
 475                     if (usage instanceof PhiNode && oldPhis.contains(usage)) {
 476                         // Do not mark.
 477                     } else {
 478                         // Mark alive by removing from delete set.
 479                         oldPhis.remove(i);
 480                         progress = true;
 481                         continue outer;
 482                     }
 483                 }
 484                 i++;
 485             }
 486         }
 487 
 488         for (PhiNode deadPhi : oldPhis) {
 489             deadPhi.clearInputs();
 490         }
 491 
 492         for (PhiNode deadPhi : oldPhis) {
 493             if (deadPhi.isAlive()) {
 494                 GraphUtil.killWithUnusedFloatingInputs(deadPhi);
 495             }
 496         }
 497     }
 498 
 499     private static void markStateNodes(StateSplit stateSplit, NodeBitMap marks) {
 500         FrameState exitState = stateSplit.stateAfter();
 501         if (exitState != null) {
 502             exitState.applyToVirtual(v -> marks.markAndGrow(v));
 503         }
 504     }
 505 
 506     /**
 507      * Gets the corresponding value in this fragment.
 508      *
 509      * @param b original value
 510      * @return corresponding value in the peel
 511      */
 512     @Override
 513     protected ValueNode prim(ValueNode b) {
 514         assert isDuplicate();
 515         LoopBeginNode loopBegin = original().loop().loopBegin();
 516         if (loopBegin.isPhiAtMerge(b)) {
 517             PhiNode phi = (PhiNode) b;
 518             return phi.valueAt(loopBegin.forwardEnd());
 519         } else if (nodesReady) {
 520             ValueNode v = getDuplicatedNode(b);
 521             if (v == null) {
 522                 return b;
 523             }
 524             return v;
 525         } else {
 526             return b;
 527         }
 528     }
 529 
 530     protected ValueNode primAfter(ValueNode b) {
 531         assert isDuplicate();
 532         LoopBeginNode loopBegin = original().loop().loopBegin();
 533         if (loopBegin.isPhiAtMerge(b)) {
 534             PhiNode phi = (PhiNode) b;
 535             assert phi.valueCount() == 2;
 536             return phi.valueAt(1);
 537         } else if (nodesReady) {
 538             ValueNode v = getDuplicatedNode(b);
 539             if (v == null) {
 540                 return b;
 541             }
 542             return v;
 543         } else {
 544             return b;
 545         }
 546     }
 547 
 548     @SuppressWarnings("try")
 549     private AbstractBeginNode mergeEnds() {
 550         assert isDuplicate();
 551         List<EndNode> endsToMerge = new LinkedList<>();
 552         // map peel exits to the corresponding loop exits
 553         EconomicMap<AbstractEndNode, LoopEndNode> reverseEnds = EconomicMap.create(Equivalence.IDENTITY);
 554         LoopBeginNode loopBegin = original().loop().loopBegin();
 555         for (LoopEndNode le : loopBegin.loopEnds()) {
 556             AbstractEndNode duplicate = getDuplicatedNode(le);
 557             if (duplicate != null) {
 558                 endsToMerge.add((EndNode) duplicate);
 559                 reverseEnds.put(duplicate, le);
 560             }
 561         }
 562         mergedInitializers = EconomicMap.create(Equivalence.IDENTITY);
 563         AbstractBeginNode newExit;
 564         StructuredGraph graph = graph();
 565         if (endsToMerge.size() == 1) {
 566             AbstractEndNode end = endsToMerge.get(0);
 567             assert end.hasNoUsages();
 568             try (DebugCloseable position = end.withNodeSourcePosition()) {
 569                 newExit = graph.add(new BeginNode());
 570                 end.replaceAtPredecessor(newExit);
 571                 end.safeDelete();
 572             }
 573         } else {
 574             assert endsToMerge.size() > 1;
 575             AbstractMergeNode newExitMerge = graph.add(new MergeNode());
 576             newExit = newExitMerge;
 577             FrameState state = loopBegin.stateAfter();
 578             FrameState duplicateState = null;
 579             if (state != null) {
 580                 duplicateState = state.duplicateWithVirtualState();
 581                 newExitMerge.setStateAfter(duplicateState);
 582             }
 583             for (EndNode end : endsToMerge) {
 584                 newExitMerge.addForwardEnd(end);
 585             }
 586 
 587             for (final PhiNode phi : loopBegin.phis().snapshot()) {
 588                 if (phi.hasNoUsages()) {
 589                     continue;
 590                 }
 591                 final PhiNode firstPhi = patchPhi(graph, phi, newExitMerge);
 592                 for (AbstractEndNode end : newExitMerge.forwardEnds()) {
 593                     LoopEndNode loopEnd = reverseEnds.get(end);
 594                     ValueNode prim = prim(phi.valueAt(loopEnd));
 595                     assert prim != null;
 596                     firstPhi.addInput(prim);
 597                 }
 598                 ValueNode initializer = firstPhi;
 599                 if (duplicateState != null) {
 600                     // fix the merge's state after
 601                     duplicateState.applyToNonVirtual(new NodeClosure<ValueNode>() {
 602 
 603                         @Override
 604                         public void apply(Node from, ValueNode node) {
 605                             if (node == phi) {
 606                                 from.replaceFirstInput(phi, firstPhi);
 607                             }
 608                         }
 609                     });
 610                 }
 611                 mergedInitializers.put(phi, initializer);
 612             }
 613         }
 614         return newExit;
 615     }
 616 }