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