1 /*
2  * Copyright (c) 2012, 2020, 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.Position;
41 import org.graalvm.compiler.graph.iterators.NodeIterable;
42 import org.graalvm.compiler.nodes.AbstractBeginNode;
43 import org.graalvm.compiler.nodes.AbstractEndNode;
44 import org.graalvm.compiler.nodes.AbstractMergeNode;
45 import org.graalvm.compiler.nodes.BeginNode;
46 import org.graalvm.compiler.nodes.ConstantNode;
47 import org.graalvm.compiler.nodes.EndNode;
48 import org.graalvm.compiler.nodes.FixedNode;
49 import org.graalvm.compiler.nodes.FixedWithNextNode;
50 import org.graalvm.compiler.nodes.FrameState;
51 import org.graalvm.compiler.nodes.GuardPhiNode;
52 import org.graalvm.compiler.nodes.IfNode;
53 import org.graalvm.compiler.nodes.LogicNode;
54 import org.graalvm.compiler.nodes.LoopBeginNode;
55 import org.graalvm.compiler.nodes.LoopEndNode;
56 import org.graalvm.compiler.nodes.LoopExitNode;
57 import org.graalvm.compiler.nodes.MergeNode;
58 import org.graalvm.compiler.nodes.NodeView;
59 import org.graalvm.compiler.nodes.PhiNode;
60 import org.graalvm.compiler.nodes.ProxyNode;
61 import org.graalvm.compiler.nodes.SafepointNode;
62 import org.graalvm.compiler.nodes.StateSplit;
63 import org.graalvm.compiler.nodes.StructuredGraph;
64 import org.graalvm.compiler.nodes.ValueNode;
65 import org.graalvm.compiler.nodes.ValuePhiNode;
66 import org.graalvm.compiler.nodes.VirtualState.NodePositionClosure;
67 import org.graalvm.compiler.nodes.calc.AddNode;
68 import org.graalvm.compiler.nodes.calc.CompareNode;
69 import org.graalvm.compiler.nodes.calc.ConditionalNode;
70 import org.graalvm.compiler.nodes.calc.IntegerBelowNode;
71 import org.graalvm.compiler.nodes.calc.SubNode;
72 import org.graalvm.compiler.nodes.extended.OpaqueNode;
73 import org.graalvm.compiler.nodes.memory.MemoryPhiNode;
74 import org.graalvm.compiler.nodes.util.GraphUtil;
75 import org.graalvm.compiler.nodes.util.IntegerHelper;
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 originalNode = mainPhiNode.valueAt(1);
173             ValueNode duplicatedNode = getDuplicatedNode(originalNode);
174             if (duplicatedNode == null) {
175                 if (mainLoopBegin.isPhiAtMerge(originalNode)) {
176                     duplicatedNode = ((PhiNode) (originalNode)).valueAt(1);
177                 } else {
178                     assert originalNode.isConstant() || loop.isOutsideLoop(originalNode) : "Not duplicated node " + originalNode;
179                 }
180             }
181             backedgeValues.add(duplicatedNode);
182         }
183         int index = 0;
184         for (PhiNode mainPhiNode : mainLoopBegin.phis()) {
185             ValueNode duplicatedNode = backedgeValues.get(index++);
186             if (duplicatedNode != null) {
187                 mainPhiNode.setValueAt(1, duplicatedNode);
188             }
189         }
190 
191         placeNewSegmentAndCleanup(loop);
192 
193         // Remove any safepoints from the original copy leaving only the duplicated one
194         assert loop.whole().nodes().filter(SafepointNode.class).count() == nodes().filter(SafepointNode.class).count();
195         for (SafepointNode safepoint : loop.whole().nodes().filter(SafepointNode.class)) {
196             graph().removeFixed(safepoint);
197         }
198 
199         StructuredGraph graph = mainLoopBegin.graph();
200         if (opaqueUnrolledStrides != null) {
201             OpaqueNode opaque = opaqueUnrolledStrides.get(loop.loopBegin());
202             CountedLoopInfo counted = loop.counted();
203             ValueNode counterStride = counted.getCounter().strideNode();
204             if (opaque == null) {
205                 opaque = new OpaqueNode(AddNode.add(counterStride, counterStride, NodeView.DEFAULT));
206                 ValueNode limit = counted.getLimit();
207                 int bits = ((IntegerStamp) limit.stamp(NodeView.DEFAULT)).getBits();
208                 ValueNode newLimit = SubNode.create(limit, opaque, NodeView.DEFAULT);
209                 IntegerHelper helper = counted.getCounterIntegerHelper();
210                 LogicNode overflowCheck;
211                 ConstantNode extremum;
212                 if (counted.getDirection() == InductionVariable.Direction.Up) {
213                     // limit - counterStride could overflow negatively if limit - min <
214                     // counterStride
215                     extremum = ConstantNode.forIntegerBits(bits, helper.minValue());
216                     overflowCheck = IntegerBelowNode.create(SubNode.create(limit, extremum, NodeView.DEFAULT), opaque, NodeView.DEFAULT);
217                 } else {
218                     assert counted.getDirection() == InductionVariable.Direction.Down;
219                     // limit - counterStride could overflow if max - limit < -counterStride
220                     // i.e., counterStride < limit - max
221                     extremum = ConstantNode.forIntegerBits(bits, helper.maxValue());
222                     overflowCheck = IntegerBelowNode.create(opaque, SubNode.create(limit, extremum, NodeView.DEFAULT), NodeView.DEFAULT);
223                 }
224                 newLimit = ConditionalNode.create(overflowCheck, extremum, newLimit, NodeView.DEFAULT);
225                 CompareNode compareNode = (CompareNode) counted.getLimitTest().condition();
226                 compareNode.replaceFirstInput(limit, graph.addOrUniqueWithInputs(newLimit));
227                 opaqueUnrolledStrides.put(loop.loopBegin(), opaque);
228             } else {
229                 assert counted.getCounter().isConstantStride();
230                 assert Math.addExact(counted.getCounter().constantStride(), counted.getCounter().constantStride()) == counted.getCounter().constantStride() * 2;
231                 ValueNode previousValue = opaque.getValue();
232                 opaque.setValue(graph.addOrUniqueWithInputs(AddNode.add(counterStride, previousValue, NodeView.DEFAULT)));
233                 GraphUtil.tryKillUnused(previousValue);
234             }
235         }
236         mainLoopBegin.setUnrollFactor(mainLoopBegin.getUnrollFactor() * 2);
237         mainLoopBegin.setLoopFrequency(Math.max(1.0, mainLoopBegin.loopFrequency() / 2));
238         graph.getDebug().dump(DebugContext.DETAILED_LEVEL, graph, "LoopPartialUnroll %s", loop);
239 
240         mainLoopBegin.getDebug().dump(DebugContext.VERBOSE_LEVEL, mainLoopBegin.graph(), "After insertWithinAfter %s", mainLoopBegin);
241     }
242 
placeNewSegmentAndCleanup(LoopEx loop)243     private void placeNewSegmentAndCleanup(LoopEx loop) {
244         CountedLoopInfo mainCounted = loop.counted();
245         LoopBeginNode mainLoopBegin = loop.loopBegin();
246         // Discard the segment entry and its flow, after if merging it into the loop
247         StructuredGraph graph = mainLoopBegin.graph();
248         IfNode loopTest = mainCounted.getLimitTest();
249         IfNode newSegmentLoopTest = getDuplicatedNode(loopTest);
250 
251         // Redirect anchors
252         AbstractBeginNode falseSuccessor = newSegmentLoopTest.falseSuccessor();
253         for (Node usage : falseSuccessor.anchored().snapshot()) {
254             usage.replaceFirstInput(falseSuccessor, loopTest.falseSuccessor());
255         }
256         AbstractBeginNode trueSuccessor = newSegmentLoopTest.trueSuccessor();
257         for (Node usage : trueSuccessor.anchored().snapshot()) {
258             usage.replaceFirstInput(trueSuccessor, loopTest.trueSuccessor());
259         }
260 
261         // remove if test
262         graph.removeSplitPropagate(newSegmentLoopTest, loopTest.trueSuccessor() == mainCounted.getBody() ? trueSuccessor : falseSuccessor);
263 
264         graph.getDebug().dump(DebugContext.DETAILED_LEVEL, graph, "Before placing segment");
265         if (mainCounted.getBody().next() instanceof LoopEndNode) {
266             GraphUtil.killCFG(getDuplicatedNode(mainLoopBegin));
267         } else {
268             AbstractBeginNode newSegmentBegin = getDuplicatedNode(mainLoopBegin);
269             FixedNode newSegmentFirstNode = newSegmentBegin.next();
270             EndNode newSegmentEnd = getBlockEnd(newSegmentBegin);
271             FixedWithNextNode newSegmentLastNode = (FixedWithNextNode) newSegmentEnd.predecessor();
272             LoopEndNode loopEndNode = mainLoopBegin.getSingleLoopEnd();
273             FixedWithNextNode lastCodeNode = (FixedWithNextNode) loopEndNode.predecessor();
274 
275             newSegmentBegin.clearSuccessors();
276             lastCodeNode.replaceFirstSuccessor(loopEndNode, newSegmentFirstNode);
277             newSegmentLastNode.replaceFirstSuccessor(newSegmentEnd, loopEndNode);
278 
279             newSegmentBegin.safeDelete();
280             newSegmentEnd.safeDelete();
281         }
282         graph.getDebug().dump(DebugContext.DETAILED_LEVEL, graph, "After placing segment");
283     }
284 
getBlockEnd(FixedNode node)285     private static EndNode getBlockEnd(FixedNode node) {
286         FixedNode curNode = node;
287         while (curNode instanceof FixedWithNextNode) {
288             curNode = ((FixedWithNextNode) curNode).next();
289         }
290         return (EndNode) curNode;
291     }
292 
293     @Override
nodes()294     public NodeBitMap nodes() {
295         if (nodes == null) {
296             LoopFragmentWhole whole = loop().whole();
297             whole.nodes(); // init nodes bitmap in whole
298             nodes = whole.nodes.copy();
299             // remove the phis
300             LoopBeginNode loopBegin = loop().loopBegin();
301             for (PhiNode phi : loopBegin.phis()) {
302                 nodes.clear(phi);
303             }
304             clearStateNodes(loopBegin);
305             for (LoopExitNode exit : exits()) {
306                 clearStateNodes(exit);
307                 for (ProxyNode proxy : exit.proxies()) {
308                     nodes.clear(proxy);
309                 }
310             }
311         }
312         return nodes;
313     }
314 
clearStateNodes(StateSplit stateSplit)315     private void clearStateNodes(StateSplit stateSplit) {
316         FrameState loopState = stateSplit.stateAfter();
317         if (loopState != null) {
318             loopState.applyToVirtual(v -> {
319                 if (v.usages().filter(n -> nodes.isMarked(n) && n != stateSplit).isEmpty()) {
320                     nodes.clear(v);
321                 }
322             });
323         }
324     }
325 
exits()326     public NodeIterable<LoopExitNode> exits() {
327         return loop().loopBegin().loopExits();
328     }
329 
330     @Override
331     @SuppressWarnings("try")
getDuplicationReplacement()332     protected DuplicationReplacement getDuplicationReplacement() {
333         final LoopBeginNode loopBegin = loop().loopBegin();
334         final StructuredGraph graph = graph();
335         return new DuplicationReplacement() {
336 
337             private EconomicMap<Node, Node> seenNode = EconomicMap.create(Equivalence.IDENTITY);
338 
339             @Override
340             public Node replacement(Node original) {
341                 try (DebugCloseable position = original.withNodeSourcePosition()) {
342                     if (original == loopBegin) {
343                         Node value = seenNode.get(original);
344                         if (value != null) {
345                             return value;
346                         }
347                         AbstractBeginNode newValue = graph.add(new BeginNode());
348                         seenNode.put(original, newValue);
349                         return newValue;
350                     }
351                     if (original instanceof LoopExitNode && ((LoopExitNode) original).loopBegin() == loopBegin) {
352                         Node value = seenNode.get(original);
353                         if (value != null) {
354                             return value;
355                         }
356                         AbstractBeginNode newValue = graph.add(new BeginNode());
357                         seenNode.put(original, newValue);
358                         return newValue;
359                     }
360                     if (original instanceof LoopEndNode && ((LoopEndNode) original).loopBegin() == loopBegin) {
361                         Node value = seenNode.get(original);
362                         if (value != null) {
363                             return value;
364                         }
365                         EndNode newValue = graph.add(new EndNode());
366                         seenNode.put(original, newValue);
367                         return newValue;
368                     }
369                     return original;
370                 }
371             }
372         };
373     }
374 
375     @Override
beforeDuplication()376     protected void beforeDuplication() {
377         // Nothing to do
378     }
379 
patchPhi(StructuredGraph graph, PhiNode phi, AbstractMergeNode merge)380     private static PhiNode patchPhi(StructuredGraph graph, PhiNode phi, AbstractMergeNode merge) {
381         PhiNode ret;
382         if (phi instanceof ValuePhiNode) {
383             ret = new ValuePhiNode(phi.stamp(NodeView.DEFAULT), merge);
384         } else if (phi instanceof GuardPhiNode) {
385             ret = new GuardPhiNode(merge);
386         } else if (phi instanceof MemoryPhiNode) {
387             ret = new MemoryPhiNode(merge, ((MemoryPhiNode) phi).getLocationIdentity());
388         } else {
389             throw GraalError.shouldNotReachHere();
390         }
391         return graph.addWithoutUnique(ret);
392     }
393 
patchPeeling(LoopFragmentInside peel)394     private void patchPeeling(LoopFragmentInside peel) {
395         LoopBeginNode loopBegin = loop().loopBegin();
396         StructuredGraph graph = loopBegin.graph();
397         List<PhiNode> newPhis = new LinkedList<>();
398 
399         NodeBitMap usagesToPatch = nodes.copy();
400         for (LoopExitNode exit : exits()) {
401             markStateNodes(exit, usagesToPatch);
402             for (ProxyNode proxy : exit.proxies()) {
403                 usagesToPatch.markAndGrow(proxy);
404             }
405         }
406         markStateNodes(loopBegin, usagesToPatch);
407 
408         List<PhiNode> oldPhis = loopBegin.phis().snapshot();
409         for (PhiNode phi : oldPhis) {
410             if (phi.hasNoUsages()) {
411                 continue;
412             }
413             ValueNode first;
414             if (loopBegin.loopEnds().count() == 1) {
415                 ValueNode b = phi.valueAt(loopBegin.loopEnds().first()); // back edge value
416                 first = peel.prim(b); // corresponding value in the peel
417             } else {
418                 first = peel.mergedInitializers.get(phi);
419             }
420             // create a new phi (we don't patch the old one since some usages of the old one may
421             // still be valid)
422             PhiNode newPhi = patchPhi(graph, phi, loopBegin);
423             newPhi.addInput(first);
424             for (LoopEndNode end : loopBegin.orderedLoopEnds()) {
425                 newPhi.addInput(phi.valueAt(end));
426             }
427             peel.putDuplicatedNode(phi, newPhi);
428             newPhis.add(newPhi);
429             for (Node usage : phi.usages().snapshot()) {
430                 // patch only usages that should use the new phi ie usages that were peeled
431                 if (usagesToPatch.isMarkedAndGrow(usage)) {
432                     usage.replaceFirstInput(phi, newPhi);
433                 }
434             }
435         }
436         // check new phis to see if they have as input some old phis, replace those inputs with the
437         // new corresponding phis
438         for (PhiNode phi : newPhis) {
439             for (int i = 0; i < phi.valueCount(); i++) {
440                 ValueNode v = phi.valueAt(i);
441                 if (loopBegin.isPhiAtMerge(v)) {
442                     PhiNode newV = peel.getDuplicatedNode((PhiNode) v);
443                     if (newV != null) {
444                         phi.setValueAt(i, newV);
445                     }
446                 }
447             }
448         }
449 
450         boolean progress = true;
451         while (progress) {
452             progress = false;
453             int i = 0;
454             outer: while (i < oldPhis.size()) {
455                 PhiNode oldPhi = oldPhis.get(i);
456                 for (Node usage : oldPhi.usages()) {
457                     if (usage instanceof PhiNode && oldPhis.contains(usage)) {
458                         // Do not mark.
459                     } else {
460                         // Mark alive by removing from delete set.
461                         oldPhis.remove(i);
462                         progress = true;
463                         continue outer;
464                     }
465                 }
466                 i++;
467             }
468         }
469 
470         for (PhiNode deadPhi : oldPhis) {
471             deadPhi.clearInputs();
472         }
473 
474         for (PhiNode deadPhi : oldPhis) {
475             if (deadPhi.isAlive()) {
476                 GraphUtil.killWithUnusedFloatingInputs(deadPhi);
477             }
478         }
479     }
480 
markStateNodes(StateSplit stateSplit, NodeBitMap marks)481     private static void markStateNodes(StateSplit stateSplit, NodeBitMap marks) {
482         FrameState exitState = stateSplit.stateAfter();
483         if (exitState != null) {
484             exitState.applyToVirtual(v -> marks.markAndGrow(v));
485         }
486     }
487 
488     /**
489      * Gets the corresponding value in this fragment.
490      *
491      * @param b original value
492      * @return corresponding value in the peel
493      */
494     @Override
prim(ValueNode b)495     protected ValueNode prim(ValueNode b) {
496         assert isDuplicate();
497         LoopBeginNode loopBegin = original().loop().loopBegin();
498         if (loopBegin.isPhiAtMerge(b)) {
499             PhiNode phi = (PhiNode) b;
500             return phi.valueAt(loopBegin.forwardEnd());
501         } else if (nodesReady) {
502             ValueNode v = getDuplicatedNode(b);
503             if (v == null) {
504                 return b;
505             }
506             return v;
507         } else {
508             return b;
509         }
510     }
511 
primAfter(ValueNode b)512     protected ValueNode primAfter(ValueNode b) {
513         assert isDuplicate();
514         LoopBeginNode loopBegin = original().loop().loopBegin();
515         if (loopBegin.isPhiAtMerge(b)) {
516             PhiNode phi = (PhiNode) b;
517             assert phi.valueCount() == 2;
518             return phi.valueAt(1);
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     @SuppressWarnings("try")
mergeEnds()531     private AbstractBeginNode mergeEnds() {
532         assert isDuplicate();
533         List<EndNode> endsToMerge = new LinkedList<>();
534         // map peel exits to the corresponding loop exits
535         EconomicMap<AbstractEndNode, LoopEndNode> reverseEnds = EconomicMap.create(Equivalence.IDENTITY);
536         LoopBeginNode loopBegin = original().loop().loopBegin();
537         for (LoopEndNode le : loopBegin.loopEnds()) {
538             AbstractEndNode duplicate = getDuplicatedNode(le);
539             if (duplicate != null) {
540                 endsToMerge.add((EndNode) duplicate);
541                 reverseEnds.put(duplicate, le);
542             }
543         }
544         mergedInitializers = EconomicMap.create(Equivalence.IDENTITY);
545         AbstractBeginNode newExit;
546         StructuredGraph graph = graph();
547         if (endsToMerge.size() == 1) {
548             AbstractEndNode end = endsToMerge.get(0);
549             assert end.hasNoUsages();
550             try (DebugCloseable position = end.withNodeSourcePosition()) {
551                 newExit = graph.add(new BeginNode());
552                 end.replaceAtPredecessor(newExit);
553                 end.safeDelete();
554             }
555         } else {
556             assert endsToMerge.size() > 1;
557             AbstractMergeNode newExitMerge = graph.add(new MergeNode());
558             newExit = newExitMerge;
559             FrameState state = loopBegin.stateAfter();
560             FrameState duplicateState = null;
561             if (state != null) {
562                 duplicateState = state.duplicateWithVirtualState();
563                 newExitMerge.setStateAfter(duplicateState);
564             }
565             for (EndNode end : endsToMerge) {
566                 newExitMerge.addForwardEnd(end);
567             }
568 
569             for (final PhiNode phi : loopBegin.phis().snapshot()) {
570                 if (phi.hasNoUsages()) {
571                     continue;
572                 }
573                 final PhiNode firstPhi = patchPhi(graph, phi, newExitMerge);
574                 for (AbstractEndNode end : newExitMerge.forwardEnds()) {
575                     LoopEndNode loopEnd = reverseEnds.get(end);
576                     ValueNode prim = prim(phi.valueAt(loopEnd));
577                     assert prim != null;
578                     firstPhi.addInput(prim);
579                 }
580                 ValueNode initializer = firstPhi;
581                 if (duplicateState != null) {
582                     // fix the merge's state after
583                     duplicateState.applyToNonVirtual(new NodePositionClosure<Node>() {
584                         @Override
585                         public void apply(Node from, Position p) {
586                             if (p.get(from) == phi) {
587                                 p.set(from, firstPhi);
588                             }
589                         }
590                     });
591                 }
592                 mergedInitializers.put(phi, initializer);
593             }
594         }
595         return newExit;
596     }
597 }
598