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 
LoopFragmentInside(LoopEx loop)109     public LoopFragmentInside(LoopEx loop) {
110         super(loop);
111     }
112 
LoopFragmentInside(LoopFragmentInside original)113     public LoopFragmentInside(LoopFragmentInside original) {
114         super(null, original);
115     }
116 
117     @Override
duplicate()118     public LoopFragmentInside duplicate() {
119         assert !isDuplicate();
120         return new LoopFragmentInside(this);
121     }
122 
123     @Override
original()124     public LoopFragmentInside original() {
125         return (LoopFragmentInside) super.original();
126     }
127 
128     @SuppressWarnings("unused")
appendInside(LoopEx loop)129     public void appendInside(LoopEx loop) {
130         // TODO (gd)
131     }
132 
133     @Override
loop()134     public LoopEx loop() {
135         assert !this.isDuplicate();
136         return super.loop();
137     }
138 
139     @Override
insertBefore(LoopEx loop)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      */
insertWithinAfter(LoopEx loop, EconomicMap<LoopBeginNode, OpaqueNode> opaqueUnrolledStrides)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 
placeNewSegmentAndCleanup(LoopEx loop)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 
getBlockEnd(FixedNode node)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
nodes()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 
clearStateNodes(StateSplit stateSplit)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 
exits()344     public NodeIterable<LoopExitNode> exits() {
345         return loop().loopBegin().loopExits();
346     }
347 
348     @Override
349     @SuppressWarnings("try")
getDuplicationReplacement()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
finishDuplication()394     protected void finishDuplication() {
395         // TODO (gd) ?
396     }
397 
398     @Override
beforeDuplication()399     protected void beforeDuplication() {
400         // Nothing to do
401     }
402 
patchPhi(StructuredGraph graph, PhiNode phi, AbstractMergeNode merge)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 
patchPeeling(LoopFragmentInside peel)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 
markStateNodes(StateSplit stateSplit, NodeBitMap marks)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
prim(ValueNode b)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 
primAfter(ValueNode b)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")
mergeEnds()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 }
622