Source code

001/*
002 * Copyright (c) 2012, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.loop;
024
025import java.util.*;
026
027import jdk.internal.jvmci.common.*;
028
029import com.oracle.graal.compiler.common.*;
030import com.oracle.graal.graph.Graph.DuplicationReplacement;
031import com.oracle.graal.graph.*;
032import com.oracle.graal.graph.iterators.*;
033import com.oracle.graal.nodes.*;
034import com.oracle.graal.nodes.VirtualState.NodeClosure;
035import com.oracle.graal.nodes.memory.*;
036import com.oracle.graal.nodes.util.*;
037
038public class LoopFragmentInside extends LoopFragment {
039
040    /**
041     * mergedInitializers. When an inside fragment's (loop)ends are merged to create a unique exit
042     * point, some phis must be created : they phis together all the back-values of the loop-phis
043     * These can then be used to update the loop-phis' forward edge value ('initializer') in the
044     * peeling case. In the unrolling case they will be used as the value that replace the loop-phis
045     * of the duplicated inside fragment
046     */
047    private Map<ValuePhiNode, ValueNode> mergedInitializers;
048    private final DuplicationReplacement dataFixBefore = new DuplicationReplacement() {
049
050        @Override
051        public Node replacement(Node oriInput) {
052            if (!(oriInput instanceof ValueNode)) {
053                return oriInput;
054            }
055            return prim((ValueNode) oriInput);
056        }
057    };
058
059    public LoopFragmentInside(LoopEx loop) {
060        super(loop);
061    }
062
063    public LoopFragmentInside(LoopFragmentInside original) {
064        super(null, original);
065    }
066
067    @Override
068    public LoopFragmentInside duplicate() {
069        assert !isDuplicate();
070        return new LoopFragmentInside(this);
071    }
072
073    @Override
074    public LoopFragmentInside original() {
075        return (LoopFragmentInside) super.original();
076    }
077
078    @SuppressWarnings("unused")
079    public void appendInside(LoopEx loop) {
080        // TODO (gd)
081    }
082
083    @Override
084    public LoopEx loop() {
085        assert !this.isDuplicate();
086        return super.loop();
087    }
088
089    @Override
090    public void insertBefore(LoopEx loop) {
091        assert this.isDuplicate() && this.original().loop() == loop;
092
093        patchNodes(dataFixBefore);
094
095        AbstractBeginNode end = mergeEnds();
096
097        mergeEarlyExits();
098
099        original().patchPeeling(this);
100
101        AbstractBeginNode entry = getDuplicatedNode(loop.loopBegin());
102        loop.entryPoint().replaceAtPredecessor(entry);
103        end.setNext(loop.entryPoint());
104    }
105
106    @Override
107    public NodeBitMap nodes() {
108        if (nodes == null) {
109            LoopFragmentWhole whole = loop().whole();
110            whole.nodes(); // init nodes bitmap in whole
111            nodes = whole.nodes.copy();
112            // remove the phis
113            LoopBeginNode loopBegin = loop().loopBegin();
114            for (PhiNode phi : loopBegin.phis()) {
115                nodes.clear(phi);
116            }
117            clearStateNodes(loopBegin);
118            for (LoopExitNode exit : exits()) {
119                clearStateNodes(exit);
120                for (ProxyNode proxy : exit.proxies()) {
121                    nodes.clear(proxy);
122                }
123            }
124        }
125        return nodes;
126    }
127
128    private void clearStateNodes(StateSplit stateSplit) {
129        FrameState loopState = stateSplit.stateAfter();
130        if (loopState != null) {
131            loopState.applyToVirtual(v -> {
132                if (v.usages().filter(n -> nodes.isMarked(n) && n != stateSplit).isEmpty()) {
133                    nodes.clear(v);
134                }
135            });
136        }
137    }
138
139    public NodeIterable<LoopExitNode> exits() {
140        return loop().loopBegin().loopExits();
141    }
142
143    @Override
144    protected DuplicationReplacement getDuplicationReplacement() {
145        final LoopBeginNode loopBegin = loop().loopBegin();
146        final StructuredGraph graph = graph();
147        return new DuplicationReplacement() {
148
149            private Map<Node, Node> seenNode = Node.newMap();
150
151            @Override
152            public Node replacement(Node original) {
153                if (original == loopBegin) {
154                    Node value = seenNode.get(original);
155                    if (value != null) {
156                        return value;
157                    }
158                    AbstractBeginNode newValue = graph.add(new BeginNode());
159                    seenNode.put(original, newValue);
160                    return newValue;
161                }
162                if (original instanceof LoopExitNode && ((LoopExitNode) original).loopBegin() == loopBegin) {
163                    Node value = seenNode.get(original);
164                    if (value != null) {
165                        return value;
166                    }
167                    AbstractBeginNode newValue = graph.add(new BeginNode());
168                    seenNode.put(original, newValue);
169                    return newValue;
170                }
171                if (original instanceof LoopEndNode && ((LoopEndNode) original).loopBegin() == loopBegin) {
172                    Node value = seenNode.get(original);
173                    if (value != null) {
174                        return value;
175                    }
176                    EndNode newValue = graph.add(new EndNode());
177                    seenNode.put(original, newValue);
178                    return newValue;
179                }
180                return original;
181            }
182        };
183    }
184
185    @Override
186    protected void finishDuplication() {
187        // TODO (gd) ?
188    }
189
190    private static PhiNode patchPhi(StructuredGraph graph, PhiNode phi, AbstractMergeNode merge) {
191        PhiNode ret;
192        if (phi instanceof ValuePhiNode) {
193            ret = new ValuePhiNode(phi.stamp(), merge);
194        } else if (phi instanceof GuardPhiNode) {
195            ret = new GuardPhiNode(merge);
196        } else if (phi instanceof MemoryPhiNode) {
197            ret = new MemoryPhiNode(merge, ((MemoryPhiNode) phi).getLocationIdentity());
198        } else {
199            throw JVMCIError.shouldNotReachHere();
200        }
201        return graph.addWithoutUnique(ret);
202    }
203
204    private void patchPeeling(LoopFragmentInside peel) {
205        LoopBeginNode loopBegin = loop().loopBegin();
206        StructuredGraph graph = loopBegin.graph();
207        List<PhiNode> newPhis = new LinkedList<>();
208
209        NodeBitMap usagesToPatch = nodes.copy();
210        for (LoopExitNode exit : exits()) {
211            markStateNodes(exit, usagesToPatch);
212            for (ProxyNode proxy : exit.proxies()) {
213                usagesToPatch.markAndGrow(proxy);
214            }
215        }
216        markStateNodes(loopBegin, usagesToPatch);
217
218        for (PhiNode phi : loopBegin.phis().snapshot()) {
219            if (phi.hasNoUsages()) {
220                continue;
221            }
222            ValueNode first;
223            if (loopBegin.loopEnds().count() == 1) {
224                ValueNode b = phi.valueAt(loopBegin.loopEnds().first()); // back edge value
225                first = peel.prim(b); // corresponding value in the peel
226            } else {
227                first = peel.mergedInitializers.get(phi);
228            }
229            // create a new phi (we don't patch the old one since some usages of the old one may
230            // still be valid)
231            PhiNode newPhi = patchPhi(graph, phi, loopBegin);
232            newPhi.addInput(first);
233            for (LoopEndNode end : loopBegin.orderedLoopEnds()) {
234                newPhi.addInput(phi.valueAt(end));
235            }
236            peel.putDuplicatedNode(phi, newPhi);
237            newPhis.add(newPhi);
238            for (Node usage : phi.usages().snapshot()) {
239                // patch only usages that should use the new phi ie usages that were peeled
240                if (usagesToPatch.isMarkedAndGrow(usage)) {
241                    usage.replaceFirstInput(phi, newPhi);
242                }
243            }
244        }
245        // check new phis to see if they have as input some old phis, replace those inputs with the
246        // new corresponding phis
247        for (PhiNode phi : newPhis) {
248            for (int i = 0; i < phi.valueCount(); i++) {
249                ValueNode v = phi.valueAt(i);
250                if (loopBegin.isPhiAtMerge(v)) {
251                    PhiNode newV = peel.getDuplicatedNode((ValuePhiNode) v);
252                    if (newV != null) {
253                        phi.setValueAt(i, newV);
254                    }
255                }
256            }
257        }
258
259        for (PhiNode deadPhi : loopBegin.phis().filter(n -> n.hasNoUsages()).snapshot()) {
260            if (deadPhi.isAlive()) {
261                GraphUtil.killWithUnusedFloatingInputs(deadPhi);
262            }
263        }
264    }
265
266    private static void markStateNodes(StateSplit stateSplit, NodeBitMap marks) {
267        FrameState exitState = stateSplit.stateAfter();
268        if (exitState != null) {
269            exitState.applyToVirtual(v -> marks.markAndGrow(v));
270        }
271    }
272
273    /**
274     * Gets the corresponding value in this fragment.
275     *
276     * @param b original value
277     * @return corresponding value in the peel
278     */
279    @Override
280    protected ValueNode prim(ValueNode b) {
281        assert isDuplicate();
282        LoopBeginNode loopBegin = original().loop().loopBegin();
283        if (loopBegin.isPhiAtMerge(b)) {
284            PhiNode phi = (PhiNode) b;
285            return phi.valueAt(loopBegin.forwardEnd());
286        } else if (nodesReady) {
287            ValueNode v = getDuplicatedNode(b);
288            if (v == null) {
289                return b;
290            }
291            return v;
292        } else {
293            return b;
294        }
295    }
296
297    private AbstractBeginNode mergeEnds() {
298        assert isDuplicate();
299        List<EndNode> endsToMerge = new LinkedList<>();
300        // map peel exits to the corresponding loop exits
301        Map<AbstractEndNode, LoopEndNode> reverseEnds = CollectionsFactory.newMap();
302        LoopBeginNode loopBegin = original().loop().loopBegin();
303        for (LoopEndNode le : loopBegin.loopEnds()) {
304            AbstractEndNode duplicate = getDuplicatedNode(le);
305            if (duplicate != null) {
306                endsToMerge.add((EndNode) duplicate);
307                reverseEnds.put(duplicate, le);
308            }
309        }
310        mergedInitializers = Node.newIdentityMap();
311        AbstractBeginNode newExit;
312        StructuredGraph graph = graph();
313        if (endsToMerge.size() == 1) {
314            AbstractEndNode end = endsToMerge.get(0);
315            assert end.hasNoUsages();
316            newExit = graph.add(new BeginNode());
317            end.replaceAtPredecessor(newExit);
318            end.safeDelete();
319        } else {
320            assert endsToMerge.size() > 1;
321            AbstractMergeNode newExitMerge = graph.add(new MergeNode());
322            newExit = newExitMerge;
323            FrameState state = loopBegin.stateAfter();
324            FrameState duplicateState = null;
325            if (state != null) {
326                duplicateState = state.duplicateWithVirtualState();
327                newExitMerge.setStateAfter(duplicateState);
328            }
329            for (EndNode end : endsToMerge) {
330                newExitMerge.addForwardEnd(end);
331            }
332
333            for (final PhiNode phi : loopBegin.phis().snapshot()) {
334                if (phi.hasNoUsages()) {
335                    continue;
336                }
337                final PhiNode firstPhi = patchPhi(graph, phi, newExitMerge);
338                for (AbstractEndNode end : newExitMerge.forwardEnds()) {
339                    LoopEndNode loopEnd = reverseEnds.get(end);
340                    ValueNode prim = prim(phi.valueAt(loopEnd));
341                    assert prim != null;
342                    firstPhi.addInput(prim);
343                }
344                ValueNode initializer = firstPhi;
345                if (duplicateState != null) {
346                    // fix the merge's state after
347                    duplicateState.applyToNonVirtual(new NodeClosure<ValueNode>() {
348
349                        @Override
350                        public void apply(Node from, ValueNode node) {
351                            if (node == phi) {
352                                from.replaceFirstInput(phi, firstPhi);
353                            }
354                        }
355                    });
356                }
357                mergedInitializers.put((ValuePhiNode) phi, initializer);
358            }
359        }
360        return newExit;
361    }
362}