LoopFragment.java revision 13264:48566d838608 
1/*
2 * Copyright (c) 2012, 2012, 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.Collections;
26import java.util.Iterator;
27
28import org.graalvm.compiler.debug.GraalError;
29import org.graalvm.compiler.graph.Graph;
30import org.graalvm.compiler.graph.Graph.DuplicationReplacement;
31import org.graalvm.compiler.graph.Node;
32import org.graalvm.compiler.graph.NodeBitMap;
33import org.graalvm.compiler.graph.iterators.NodeIterable;
34import org.graalvm.compiler.nodes.AbstractBeginNode;
35import org.graalvm.compiler.nodes.EndNode;
36import org.graalvm.compiler.nodes.FixedNode;
37import org.graalvm.compiler.nodes.FrameState;
38import org.graalvm.compiler.nodes.GuardNode;
39import org.graalvm.compiler.nodes.GuardPhiNode;
40import org.graalvm.compiler.nodes.GuardProxyNode;
41import org.graalvm.compiler.nodes.Invoke;
42import org.graalvm.compiler.nodes.LoopExitNode;
43import org.graalvm.compiler.nodes.MergeNode;
44import org.graalvm.compiler.nodes.PhiNode;
45import org.graalvm.compiler.nodes.ProxyNode;
46import org.graalvm.compiler.nodes.StructuredGraph;
47import org.graalvm.compiler.nodes.ValueNode;
48import org.graalvm.compiler.nodes.ValuePhiNode;
49import org.graalvm.compiler.nodes.ValueProxyNode;
50import org.graalvm.compiler.nodes.VirtualState;
51import org.graalvm.compiler.nodes.cfg.Block;
52import org.graalvm.compiler.nodes.java.MonitorEnterNode;
53import org.graalvm.compiler.nodes.spi.NodeWithState;
54import org.graalvm.compiler.nodes.virtual.CommitAllocationNode;
55import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
56import org.graalvm.util.EconomicMap;
57
58public abstract class LoopFragment {
59
60    private final LoopEx loop;
61    private final LoopFragment original;
62    protected NodeBitMap nodes;
63    protected boolean nodesReady;
64    private EconomicMap<Node, Node> duplicationMap;
65
66    public LoopFragment(LoopEx loop) {
67        this(loop, null);
68        this.nodesReady = true;
69    }
70
71    public LoopFragment(LoopEx loop, LoopFragment original) {
72        this.loop = loop;
73        this.original = original;
74        this.nodesReady = false;
75    }
76
77    public LoopEx loop() {
78        return loop;
79    }
80
81    public abstract LoopFragment duplicate();
82
83    public abstract void insertBefore(LoopEx l);
84
85    public void disconnect() {
86        // TODO (gd) possibly abstract
87    }
88
89    public boolean contains(Node n) {
90        return nodes().isMarkedAndGrow(n);
91    }
92
93    @SuppressWarnings("unchecked")
94    public <New extends Node, Old extends New> New getDuplicatedNode(Old n) {
95        assert isDuplicate();
96        return (New) duplicationMap.get(n);
97    }
98
99    protected <New extends Node, Old extends New> void putDuplicatedNode(Old oldNode, New newNode) {
100        duplicationMap.put(oldNode, newNode);
101    }
102
103    /**
104     * Gets the corresponding value in this fragment. Should be called on duplicate fragments with a
105     * node from the original fragment as argument.
106     *
107     * @param b original value
108     * @return corresponding value in the peel
109     */
110    protected abstract ValueNode prim(ValueNode b);
111
112    public boolean isDuplicate() {
113        return original != null;
114    }
115
116    public LoopFragment original() {
117        return original;
118    }
119
120    public abstract NodeBitMap nodes();
121
122    public StructuredGraph graph() {
123        LoopEx l;
124        if (isDuplicate()) {
125            l = original().loop();
126        } else {
127            l = loop();
128        }
129        return l.loopBegin().graph();
130    }
131
132    protected abstract DuplicationReplacement getDuplicationReplacement();
133
134    protected abstract void beforeDuplication();
135
136    protected abstract void finishDuplication();
137
138    protected void patchNodes(final DuplicationReplacement dataFix) {
139        if (isDuplicate() && !nodesReady) {
140            assert !original.isDuplicate();
141            final DuplicationReplacement cfgFix = original().getDuplicationReplacement();
142            DuplicationReplacement dr;
143            if (cfgFix == null && dataFix != null) {
144                dr = dataFix;
145            } else if (cfgFix != null && dataFix == null) {
146                dr = cfgFix;
147            } else if (cfgFix != null && dataFix != null) {
148                dr = new DuplicationReplacement() {
149
150                    @Override
151                    public Node replacement(Node o) {
152                        Node r1 = dataFix.replacement(o);
153                        if (r1 != o) {
154                            assert cfgFix.replacement(o) == o;
155                            return r1;
156                        }
157                        Node r2 = cfgFix.replacement(o);
158                        if (r2 != o) {
159                            return r2;
160                        }
161                        return o;
162                    }
163                };
164            } else {
165                dr = null;
166            }
167            beforeDuplication();
168            NodeIterable<Node> nodesIterable = original().nodes();
169            duplicationMap = graph().addDuplicates(nodesIterable, graph(), nodesIterable.count(), dr);
170            finishDuplication();
171            nodesReady = true;
172        } else {
173            // TODO (gd) apply fix ?
174        }
175    }
176
177    protected static NodeBitMap computeNodes(Graph graph, Iterable<AbstractBeginNode> blocks) {
178        return computeNodes(graph, blocks, Collections.emptyList());
179    }
180
181    protected static NodeBitMap computeNodes(Graph graph, Iterable<AbstractBeginNode> blocks, Iterable<AbstractBeginNode> earlyExits) {
182        final NodeBitMap nodes = graph.createNodeBitMap();
183        computeNodes(nodes, graph, blocks, earlyExits);
184        return nodes;
185    }
186
187    protected static void computeNodes(NodeBitMap nodes, Graph graph, Iterable<AbstractBeginNode> blocks, Iterable<AbstractBeginNode> earlyExits) {
188        for (AbstractBeginNode b : blocks) {
189            if (b.isDeleted()) {
190                continue;
191            }
192
193            for (Node n : b.getBlockNodes()) {
194                if (n instanceof Invoke) {
195                    nodes.mark(((Invoke) n).callTarget());
196                }
197                if (n instanceof NodeWithState) {
198                    NodeWithState withState = (NodeWithState) n;
199                    withState.states().forEach(state -> state.applyToVirtual(node -> nodes.mark(node)));
200                }
201                nodes.mark(n);
202            }
203        }
204        for (AbstractBeginNode earlyExit : earlyExits) {
205            if (earlyExit.isDeleted()) {
206                continue;
207            }
208
209            nodes.mark(earlyExit);
210
211            if (earlyExit instanceof LoopExitNode) {
212                LoopExitNode loopExit = (LoopExitNode) earlyExit;
213                FrameState stateAfter = loopExit.stateAfter();
214                if (stateAfter != null) {
215                    stateAfter.applyToVirtual(node -> nodes.mark(node));
216                }
217                for (ProxyNode proxy : loopExit.proxies()) {
218                    nodes.mark(proxy);
219                }
220            }
221        }
222
223        final NodeBitMap nonLoopNodes = graph.createNodeBitMap();
224        for (AbstractBeginNode b : blocks) {
225            if (b.isDeleted()) {
226                continue;
227            }
228
229            for (Node n : b.getBlockNodes()) {
230                if (n instanceof CommitAllocationNode) {
231                    for (VirtualObjectNode obj : ((CommitAllocationNode) n).getVirtualObjects()) {
232                        markFloating(obj, nodes, nonLoopNodes);
233                    }
234                }
235                if (n instanceof MonitorEnterNode) {
236                    markFloating(((MonitorEnterNode) n).getMonitorId(), nodes, nonLoopNodes);
237                }
238                for (Node usage : n.usages()) {
239                    markFloating(usage, nodes, nonLoopNodes);
240                }
241            }
242        }
243    }
244
245    private static boolean markFloating(Node n, NodeBitMap loopNodes, NodeBitMap nonLoopNodes) {
246        if (loopNodes.isMarked(n)) {
247            return true;
248        }
249        if (nonLoopNodes.isMarked(n)) {
250            return false;
251        }
252        if (n instanceof FixedNode) {
253            return false;
254        }
255        boolean mark = false;
256        if (n instanceof PhiNode) {
257            PhiNode phi = (PhiNode) n;
258            mark = loopNodes.isMarked(phi.merge());
259            if (mark) {
260                loopNodes.mark(n);
261            } else {
262                nonLoopNodes.mark(n);
263                return false;
264            }
265        }
266        for (Node usage : n.usages()) {
267            if (markFloating(usage, loopNodes, nonLoopNodes)) {
268                mark = true;
269            }
270        }
271        if (!mark && n instanceof GuardNode) {
272            // (gd) this is only OK if we are not going to make loop transforms based on this
273            assert !((GuardNode) n).graph().hasValueProxies();
274            mark = true;
275        }
276        if (mark) {
277            loopNodes.mark(n);
278            return true;
279        }
280        nonLoopNodes.mark(n);
281        return false;
282    }
283
284    public static NodeIterable<AbstractBeginNode> toHirBlocks(final Iterable<Block> blocks) {
285        return new NodeIterable<AbstractBeginNode>() {
286
287            @Override
288            public Iterator<AbstractBeginNode> iterator() {
289                final Iterator<Block> it = blocks.iterator();
290                return new Iterator<AbstractBeginNode>() {
291
292                    @Override
293                    public void remove() {
294                        throw new UnsupportedOperationException();
295                    }
296
297                    @Override
298                    public AbstractBeginNode next() {
299                        return it.next().getBeginNode();
300                    }
301
302                    @Override
303                    public boolean hasNext() {
304                        return it.hasNext();
305                    }
306                };
307            }
308
309        };
310    }
311
312    public static NodeIterable<AbstractBeginNode> toHirExits(final Iterable<Block> blocks) {
313        return new NodeIterable<AbstractBeginNode>() {
314
315            @Override
316            public Iterator<AbstractBeginNode> iterator() {
317                final Iterator<Block> it = blocks.iterator();
318                return new Iterator<AbstractBeginNode>() {
319
320                    @Override
321                    public void remove() {
322                        throw new UnsupportedOperationException();
323                    }
324
325                    /**
326                     * Return the true LoopExitNode for this loop or the BeginNode for the block.
327                     */
328                    @Override
329                    public AbstractBeginNode next() {
330                        Block next = it.next();
331                        LoopExitNode exit = next.getLoopExit();
332                        if (exit != null) {
333                            return exit;
334                        }
335                        return next.getBeginNode();
336                    }
337
338                    @Override
339                    public boolean hasNext() {
340                        return it.hasNext();
341                    }
342                };
343            }
344
345        };
346    }
347
348    /**
349     * Merges the early exits (i.e. loop exits) that were duplicated as part of this fragment, with
350     * the original fragment's exits.
351     */
352    protected void mergeEarlyExits() {
353        assert isDuplicate();
354        StructuredGraph graph = graph();
355        for (AbstractBeginNode earlyExit : LoopFragment.toHirBlocks(original().loop().loop().getExits())) {
356            LoopExitNode loopEarlyExit = (LoopExitNode) earlyExit;
357            FixedNode next = loopEarlyExit.next();
358            if (loopEarlyExit.isDeleted() || !this.original().contains(loopEarlyExit)) {
359                continue;
360            }
361            AbstractBeginNode newEarlyExit = getDuplicatedNode(loopEarlyExit);
362            if (newEarlyExit == null) {
363                continue;
364            }
365            MergeNode merge = graph.add(new MergeNode());
366            EndNode originalEnd = graph.add(new EndNode());
367            EndNode newEnd = graph.add(new EndNode());
368            merge.addForwardEnd(originalEnd);
369            merge.addForwardEnd(newEnd);
370            loopEarlyExit.setNext(originalEnd);
371            newEarlyExit.setNext(newEnd);
372            merge.setNext(next);
373
374            FrameState exitState = loopEarlyExit.stateAfter();
375            if (exitState != null) {
376                FrameState originalExitState = exitState;
377                exitState = exitState.duplicateWithVirtualState();
378                loopEarlyExit.setStateAfter(exitState);
379                merge.setStateAfter(originalExitState);
380                /*
381                 * Using the old exit's state as the merge's state is necessary because some of the
382                 * VirtualState nodes contained in the old exit's state may be shared by other
383                 * dominated VirtualStates. Those dominated virtual states need to see the
384                 * proxy->phi update that are applied below.
385                 *
386                 * We now update the original fragment's nodes accordingly:
387                 */
388                originalExitState.applyToVirtual(node -> original.nodes.clearAndGrow(node));
389                exitState.applyToVirtual(node -> original.nodes.markAndGrow(node));
390            }
391            FrameState finalExitState = exitState;
392
393            for (Node anchored : loopEarlyExit.anchored().snapshot()) {
394                anchored.replaceFirstInput(loopEarlyExit, merge);
395            }
396
397            boolean newEarlyExitIsLoopExit = newEarlyExit instanceof LoopExitNode;
398            for (ProxyNode vpn : loopEarlyExit.proxies().snapshot()) {
399                if (vpn.hasNoUsages()) {
400                    continue;
401                }
402                if (vpn.value() == null) {
403                    assert vpn instanceof GuardProxyNode;
404                    vpn.replaceAtUsages(null);
405                    continue;
406                }
407                final ValueNode replaceWith;
408                ValueNode newVpn = prim(newEarlyExitIsLoopExit ? vpn : vpn.value());
409                if (newVpn != null) {
410                    PhiNode phi;
411                    if (vpn instanceof ValueProxyNode) {
412                        phi = graph.addWithoutUnique(new ValuePhiNode(vpn.stamp(), merge));
413                    } else if (vpn instanceof GuardProxyNode) {
414                        phi = graph.addWithoutUnique(new GuardPhiNode(merge));
415                    } else {
416                        throw GraalError.shouldNotReachHere();
417                    }
418                    phi.addInput(vpn);
419                    phi.addInput(newVpn);
420                    replaceWith = phi;
421                } else {
422                    replaceWith = vpn.value();
423                }
424                vpn.replaceAtMatchingUsages(replaceWith, usage -> {
425                    if (merge.isPhiAtMerge(usage)) {
426                        return false;
427                    }
428                    if (usage instanceof VirtualState) {
429                        VirtualState stateUsage = (VirtualState) usage;
430                        if (finalExitState != null && finalExitState.isPartOfThisState(stateUsage)) {
431                            return false;
432                        }
433                    }
434                    return true;
435                });
436            }
437        }
438    }
439}
440