1 /*
2  * Copyright (c) 2012, 2016, Oracle and/or its affiliates. All rights reserved.
3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4  *
5  * This code is free software; you can redistribute it and/or modify it
6  * under the terms of the GNU General Public License version 2 only, as
7  * published by the Free Software Foundation.
8  *
9  * This code is distributed in the hope that it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12  * version 2 for more details (a copy is included in the LICENSE file that
13  * accompanied this code).
14  *
15  * You should have received a copy of the GNU General Public License version
16  * 2 along with this work; if not, write to the Free Software Foundation,
17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18  *
19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20  * or visit www.oracle.com if you need additional information or have any
21  * questions.
22  */
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.debug.DebugCloseable;
34 import org.graalvm.compiler.debug.DebugContext;
35 import org.graalvm.compiler.debug.GraalError;
36 import org.graalvm.compiler.graph.Graph.DuplicationReplacement;
37 import org.graalvm.compiler.graph.Node;
38 import org.graalvm.compiler.graph.NodeBitMap;
39 import org.graalvm.compiler.graph.iterators.NodeIterable;
40 import org.graalvm.compiler.nodes.AbstractBeginNode;
41 import org.graalvm.compiler.nodes.AbstractEndNode;
42 import org.graalvm.compiler.nodes.AbstractMergeNode;
43 import org.graalvm.compiler.nodes.BeginNode;
44 import org.graalvm.compiler.nodes.ConstantNode;
45 import org.graalvm.compiler.nodes.EndNode;
46 import org.graalvm.compiler.nodes.FixedNode;
47 import org.graalvm.compiler.nodes.FixedWithNextNode;
48 import org.graalvm.compiler.nodes.FrameState;
49 import org.graalvm.compiler.nodes.GuardPhiNode;
50 import org.graalvm.compiler.nodes.IfNode;
51 import org.graalvm.compiler.nodes.LogicNode;
52 import org.graalvm.compiler.nodes.LoopBeginNode;
53 import org.graalvm.compiler.nodes.LoopEndNode;
54 import org.graalvm.compiler.nodes.LoopExitNode;
55 import org.graalvm.compiler.nodes.MergeNode;
56 import org.graalvm.compiler.nodes.NodeView;
57 import org.graalvm.compiler.nodes.PhiNode;
58 import org.graalvm.compiler.nodes.ProxyNode;
59 import org.graalvm.compiler.nodes.SafepointNode;
60 import org.graalvm.compiler.nodes.StateSplit;
61 import org.graalvm.compiler.nodes.StructuredGraph;
62 import org.graalvm.compiler.nodes.ValueNode;
63 import org.graalvm.compiler.nodes.ValuePhiNode;
64 import org.graalvm.compiler.nodes.VirtualState.NodeClosure;
65 import org.graalvm.compiler.nodes.calc.AddNode;
66 import org.graalvm.compiler.nodes.calc.CompareNode;
67 import org.graalvm.compiler.nodes.calc.SubNode;
68 import org.graalvm.compiler.nodes.memory.MemoryPhiNode;
69 import org.graalvm.compiler.nodes.util.GraphUtil;
70 
71 public class LoopFragmentInside extends LoopFragment {
72 
73     /**
74      * mergedInitializers. When an inside fragment's (loop)ends are merged to create a unique exit
75      * point, some phis must be created : they phis together all the back-values of the loop-phis
76      * These can then be used to update the loop-phis' forward edge value ('initializer') in the
77      * peeling case. In the unrolling case they will be used as the value that replace the loop-phis
78      * of the duplicated inside fragment
79      */
80     private EconomicMap<PhiNode, ValueNode> mergedInitializers;
81     private final DuplicationReplacement dataFixBefore = new DuplicationReplacement() {
82 
83         @Override
84         public Node replacement(Node oriInput) {
85             if (!(oriInput instanceof ValueNode)) {
86                 return oriInput;
87             }
88             return prim((ValueNode) oriInput);
89         }
90     };
91 
92     private final DuplicationReplacement dataFixWithinAfter = new DuplicationReplacement() {
93 
94         @Override
95         public Node replacement(Node oriInput) {
96             if (!(oriInput instanceof ValueNode)) {
97                 return oriInput;
98             }
99             return primAfter((ValueNode) oriInput);
100         }
101     };
102 
LoopFragmentInside(LoopEx loop)103     public LoopFragmentInside(LoopEx loop) {
104         super(loop);
105     }
106 
LoopFragmentInside(LoopFragmentInside original)107     public LoopFragmentInside(LoopFragmentInside original) {
108         super(null, original);
109     }
110 
111     @Override
duplicate()112     public LoopFragmentInside duplicate() {
113         assert !isDuplicate();
114         return new LoopFragmentInside(this);
115     }
116 
117     @Override
original()118     public LoopFragmentInside original() {
119         return (LoopFragmentInside) super.original();
120     }
121 
122     @SuppressWarnings("unused")
appendInside(LoopEx loop)123     public void appendInside(LoopEx loop) {
124         // TODO (gd)
125     }
126 
127     @Override
loop()128     public LoopEx loop() {
129         assert !this.isDuplicate();
130         return super.loop();
131     }
132 
133     @Override
insertBefore(LoopEx loop)134     public void insertBefore(LoopEx loop) {
135         assert this.isDuplicate() && this.original().loop() == loop;
136 
137         patchNodes(dataFixBefore);
138 
139         AbstractBeginNode end = mergeEnds();
140 
141         mergeEarlyExits();
142 
143         original().patchPeeling(this);
144 
145         AbstractBeginNode entry = getDuplicatedNode(loop.loopBegin());
146         loop.entryPoint().replaceAtPredecessor(entry);
147         end.setNext(loop.entryPoint());
148     }
149 
150     /**
151      * Duplicate the body within the loop after the current copy copy of the body, updating the
152      * iteration limit to account for the duplication.
153      *
154      * @param loop
155      */
insertWithinAfter(LoopEx loop)156     public void insertWithinAfter(LoopEx loop) {
157         insertWithinAfter(loop, true);
158     }
159 
160     /**
161      * Duplicate the body within the loop after the current copy copy of the body.
162      *
163      * @param loop
164      * @param updateLimit true if the iteration limit should be adjusted.
165      */
insertWithinAfter(LoopEx loop, boolean updateLimit)166     public void insertWithinAfter(LoopEx loop, boolean updateLimit) {
167         assert isDuplicate() && original().loop() == loop;
168 
169         patchNodes(dataFixWithinAfter);
170 
171         /*
172          * Collect any new back edges values before updating them since they might reference each
173          * other.
174          */
175         LoopBeginNode mainLoopBegin = loop.loopBegin();
176         ArrayList<ValueNode> backedgeValues = new ArrayList<>();
177         for (PhiNode mainPhiNode : mainLoopBegin.phis()) {
178             ValueNode duplicatedNode = getDuplicatedNode(mainPhiNode.valueAt(1));
179             if (duplicatedNode == null) {
180                 if (mainLoopBegin.isPhiAtMerge(mainPhiNode.valueAt(1))) {
181                     duplicatedNode = ((PhiNode) (mainPhiNode.valueAt(1))).valueAt(1);
182                 } else {
183                     assert mainPhiNode.valueAt(1).isConstant() : mainPhiNode.valueAt(1);
184                 }
185             }
186             backedgeValues.add(duplicatedNode);
187         }
188         int index = 0;
189         for (PhiNode mainPhiNode : mainLoopBegin.phis()) {
190             ValueNode duplicatedNode = backedgeValues.get(index++);
191             if (duplicatedNode != null) {
192                 mainPhiNode.setValueAt(1, duplicatedNode);
193             }
194         }
195 
196         placeNewSegmentAndCleanup(loop);
197 
198         // Remove any safepoints from the original copy leaving only the duplicated one
199         assert loop.whole().nodes().filter(SafepointNode.class).count() == nodes().filter(SafepointNode.class).count();
200         for (SafepointNode safepoint : loop.whole().nodes().filter(SafepointNode.class)) {
201             graph().removeFixed(safepoint);
202         }
203 
204         int unrollFactor = mainLoopBegin.getUnrollFactor();
205         StructuredGraph graph = mainLoopBegin.graph();
206         if (updateLimit) {
207             // Now use the previous unrollFactor to update the exit condition to power of two
208             InductionVariable iv = loop.counted().getCounter();
209             CompareNode compareNode = (CompareNode) loop.counted().getLimitTest().condition();
210             ValueNode compareBound;
211             if (compareNode.getX() == iv.valueNode()) {
212                 compareBound = compareNode.getY();
213             } else if (compareNode.getY() == iv.valueNode()) {
214                 compareBound = compareNode.getX();
215             } else {
216                 throw GraalError.shouldNotReachHere();
217             }
218             long originalStride = unrollFactor == 1 ? iv.constantStride() : iv.constantStride() / unrollFactor;
219             if (iv.direction() == InductionVariable.Direction.Up) {
220                 ConstantNode aboveVal = graph.unique(ConstantNode.forIntegerStamp(iv.initNode().stamp(NodeView.DEFAULT), unrollFactor * originalStride));
221                 ValueNode newLimit = graph.addWithoutUnique(new SubNode(compareBound, aboveVal));
222                 compareNode.replaceFirstInput(compareBound, newLimit);
223             } else if (iv.direction() == InductionVariable.Direction.Down) {
224                 ConstantNode aboveVal = graph.unique(ConstantNode.forIntegerStamp(iv.initNode().stamp(NodeView.DEFAULT), unrollFactor * -originalStride));
225                 ValueNode newLimit = graph.addWithoutUnique(new AddNode(compareBound, aboveVal));
226                 compareNode.replaceFirstInput(compareBound, newLimit);
227             }
228         }
229         mainLoopBegin.setUnrollFactor(unrollFactor * 2);
230         mainLoopBegin.setLoopFrequency(mainLoopBegin.loopFrequency() / 2);
231         graph.getDebug().dump(DebugContext.DETAILED_LEVEL, graph, "LoopPartialUnroll %s", loop);
232 
233         mainLoopBegin.getDebug().dump(DebugContext.VERBOSE_LEVEL, mainLoopBegin.graph(), "After insertWithinAfter %s", mainLoopBegin);
234     }
235 
placeNewSegmentAndCleanup(LoopEx loop)236     private void placeNewSegmentAndCleanup(LoopEx loop) {
237         CountedLoopInfo mainCounted = loop.counted();
238         LoopBeginNode mainLoopBegin = loop.loopBegin();
239         // Discard the segment entry and its flow, after if merging it into the loop
240         StructuredGraph graph = mainLoopBegin.graph();
241         IfNode loopTest = mainCounted.getLimitTest();
242         IfNode newSegmentTest = getDuplicatedNode(loopTest);
243         AbstractBeginNode trueSuccessor = loopTest.trueSuccessor();
244         AbstractBeginNode falseSuccessor = loopTest.falseSuccessor();
245         FixedNode firstNode;
246         boolean codeInTrueSide = false;
247         if (trueSuccessor == mainCounted.getBody()) {
248             firstNode = trueSuccessor.next();
249             codeInTrueSide = true;
250         } else {
251             assert (falseSuccessor == mainCounted.getBody());
252             firstNode = falseSuccessor.next();
253         }
254         trueSuccessor = newSegmentTest.trueSuccessor();
255         falseSuccessor = newSegmentTest.falseSuccessor();
256         for (Node usage : falseSuccessor.anchored().snapshot()) {
257             usage.replaceFirstInput(falseSuccessor, loopTest.falseSuccessor());
258         }
259         for (Node usage : trueSuccessor.anchored().snapshot()) {
260             usage.replaceFirstInput(trueSuccessor, loopTest.trueSuccessor());
261         }
262         AbstractBeginNode startBlockNode;
263         if (codeInTrueSide) {
264             startBlockNode = trueSuccessor;
265         } else {
266             graph.getDebug().dump(DebugContext.VERBOSE_LEVEL, mainLoopBegin.graph(), "before");
267             startBlockNode = falseSuccessor;
268         }
269         FixedNode lastNode = getBlockEnd(startBlockNode);
270         LoopEndNode loopEndNode = mainLoopBegin.getSingleLoopEnd();
271         FixedWithNextNode lastCodeNode = (FixedWithNextNode) loopEndNode.predecessor();
272         FixedNode newSegmentFirstNode = getDuplicatedNode(firstNode);
273         FixedWithNextNode newSegmentLastNode = getDuplicatedNode(lastCodeNode);
274         graph.getDebug().dump(DebugContext.DETAILED_LEVEL, loopEndNode.graph(), "Before placing segment");
275         if (firstNode instanceof LoopEndNode) {
276             GraphUtil.killCFG(getDuplicatedNode(mainLoopBegin));
277         } else {
278             newSegmentLastNode.clearSuccessors();
279             startBlockNode.setNext(lastNode);
280             lastCodeNode.replaceFirstSuccessor(loopEndNode, newSegmentFirstNode);
281             newSegmentLastNode.replaceFirstSuccessor(lastNode, loopEndNode);
282             lastCodeNode.setNext(newSegmentFirstNode);
283             newSegmentLastNode.setNext(loopEndNode);
284             startBlockNode.clearSuccessors();
285             lastNode.safeDelete();
286             Node newSegmentTestStart = newSegmentTest.predecessor();
287             LogicNode newSegmentIfTest = newSegmentTest.condition();
288             newSegmentTestStart.clearSuccessors();
289             newSegmentTest.safeDelete();
290             newSegmentIfTest.safeDelete();
291             trueSuccessor.safeDelete();
292             falseSuccessor.safeDelete();
293             newSegmentTestStart.safeDelete();
294         }
295         graph.getDebug().dump(DebugContext.DETAILED_LEVEL, loopEndNode.graph(), "After placing segment");
296     }
297 
getBlockEnd(FixedNode node)298     private static EndNode getBlockEnd(FixedNode node) {
299         FixedNode curNode = node;
300         while (curNode instanceof FixedWithNextNode) {
301             curNode = ((FixedWithNextNode) curNode).next();
302         }
303         return (EndNode) curNode;
304     }
305 
306     @Override
nodes()307     public NodeBitMap nodes() {
308         if (nodes == null) {
309             LoopFragmentWhole whole = loop().whole();
310             whole.nodes(); // init nodes bitmap in whole
311             nodes = whole.nodes.copy();
312             // remove the phis
313             LoopBeginNode loopBegin = loop().loopBegin();
314             for (PhiNode phi : loopBegin.phis()) {
315                 nodes.clear(phi);
316             }
317             clearStateNodes(loopBegin);
318             for (LoopExitNode exit : exits()) {
319                 clearStateNodes(exit);
320                 for (ProxyNode proxy : exit.proxies()) {
321                     nodes.clear(proxy);
322                 }
323             }
324         }
325         return nodes;
326     }
327 
clearStateNodes(StateSplit stateSplit)328     private void clearStateNodes(StateSplit stateSplit) {
329         FrameState loopState = stateSplit.stateAfter();
330         if (loopState != null) {
331             loopState.applyToVirtual(v -> {
332                 if (v.usages().filter(n -> nodes.isMarked(n) && n != stateSplit).isEmpty()) {
333                     nodes.clear(v);
334                 }
335             });
336         }
337     }
338 
exits()339     public NodeIterable<LoopExitNode> exits() {
340         return loop().loopBegin().loopExits();
341     }
342 
343     @Override
344     @SuppressWarnings("try")
getDuplicationReplacement()345     protected DuplicationReplacement getDuplicationReplacement() {
346         final LoopBeginNode loopBegin = loop().loopBegin();
347         final StructuredGraph graph = graph();
348         return new DuplicationReplacement() {
349 
350             private EconomicMap<Node, Node> seenNode = EconomicMap.create(Equivalence.IDENTITY);
351 
352             @Override
353             public Node replacement(Node original) {
354                 try (DebugCloseable position = original.withNodeSourcePosition()) {
355                     if (original == loopBegin) {
356                         Node value = seenNode.get(original);
357                         if (value != null) {
358                             return value;
359                         }
360                         AbstractBeginNode newValue = graph.add(new BeginNode());
361                         seenNode.put(original, newValue);
362                         return newValue;
363                     }
364                     if (original instanceof LoopExitNode && ((LoopExitNode) original).loopBegin() == loopBegin) {
365                         Node value = seenNode.get(original);
366                         if (value != null) {
367                             return value;
368                         }
369                         AbstractBeginNode newValue = graph.add(new BeginNode());
370                         seenNode.put(original, newValue);
371                         return newValue;
372                     }
373                     if (original instanceof LoopEndNode && ((LoopEndNode) original).loopBegin() == loopBegin) {
374                         Node value = seenNode.get(original);
375                         if (value != null) {
376                             return value;
377                         }
378                         EndNode newValue = graph.add(new EndNode());
379                         seenNode.put(original, newValue);
380                         return newValue;
381                     }
382                     return original;
383                 }
384             }
385         };
386     }
387 
388     @Override
finishDuplication()389     protected void finishDuplication() {
390         // TODO (gd) ?
391     }
392 
393     @Override
beforeDuplication()394     protected void beforeDuplication() {
395         // Nothing to do
396     }
397 
patchPhi(StructuredGraph graph, PhiNode phi, AbstractMergeNode merge)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 
patchPeeling(LoopFragmentInside peel)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 
markStateNodes(StateSplit stateSplit, NodeBitMap marks)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
prim(ValueNode b)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 
primAfter(ValueNode b)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")
mergeEnds()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 }
617