Source code

001/*
002 * Copyright (c) 2012, 2012, 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.graph.*;
030import com.oracle.graal.graph.Graph.DuplicationReplacement;
031import com.oracle.graal.graph.iterators.*;
032import com.oracle.graal.nodes.*;
033import com.oracle.graal.nodes.cfg.*;
034import com.oracle.graal.nodes.java.*;
035import com.oracle.graal.nodes.spi.*;
036import com.oracle.graal.nodes.virtual.*;
037
038public abstract class LoopFragment {
039
040    private final LoopEx loop;
041    private final LoopFragment original;
042    protected NodeBitMap nodes;
043    protected boolean nodesReady;
044    private Map<Node, Node> duplicationMap;
045
046    public LoopFragment(LoopEx loop) {
047        this(loop, null);
048        this.nodesReady = true;
049    }
050
051    public LoopFragment(LoopEx loop, LoopFragment original) {
052        this.loop = loop;
053        this.original = original;
054        this.nodesReady = false;
055    }
056
057    public LoopEx loop() {
058        return loop;
059    }
060
061    public abstract LoopFragment duplicate();
062
063    public abstract void insertBefore(LoopEx l);
064
065    public void disconnect() {
066        // TODO (gd) possibly abstract
067    }
068
069    public boolean contains(Node n) {
070        return nodes().isMarkedAndGrow(n);
071    }
072
073    @SuppressWarnings("unchecked")
074    public <New extends Node, Old extends New> New getDuplicatedNode(Old n) {
075        assert isDuplicate();
076        return (New) duplicationMap.get(n);
077    }
078
079    protected <New extends Node, Old extends New> void putDuplicatedNode(Old oldNode, New newNode) {
080        duplicationMap.put(oldNode, newNode);
081    }
082
083    /**
084     * Gets the corresponding value in this fragment. Should be called on duplicate fragments with a
085     * node from the original fragment as argument.
086     *
087     * @param b original value
088     * @return corresponding value in the peel
089     */
090    protected abstract ValueNode prim(ValueNode b);
091
092    public boolean isDuplicate() {
093        return original != null;
094    }
095
096    public LoopFragment original() {
097        return original;
098    }
099
100    public abstract NodeBitMap nodes();
101
102    public StructuredGraph graph() {
103        LoopEx l;
104        if (isDuplicate()) {
105            l = original().loop();
106        } else {
107            l = loop();
108        }
109        return l.loopBegin().graph();
110    }
111
112    protected abstract DuplicationReplacement getDuplicationReplacement();
113
114    protected abstract void finishDuplication();
115
116    protected void patchNodes(final DuplicationReplacement dataFix) {
117        if (isDuplicate() && !nodesReady) {
118            assert !original.isDuplicate();
119            final DuplicationReplacement cfgFix = original().getDuplicationReplacement();
120            DuplicationReplacement dr;
121            if (cfgFix == null && dataFix != null) {
122                dr = dataFix;
123            } else if (cfgFix != null && dataFix == null) {
124                dr = cfgFix;
125            } else if (cfgFix != null && dataFix != null) {
126                dr = new DuplicationReplacement() {
127
128                    @Override
129                    public Node replacement(Node o) {
130                        Node r1 = dataFix.replacement(o);
131                        if (r1 != o) {
132                            assert cfgFix.replacement(o) == o;
133                            return r1;
134                        }
135                        Node r2 = cfgFix.replacement(o);
136                        if (r2 != o) {
137                            return r2;
138                        }
139                        return o;
140                    }
141                };
142            } else {
143                dr = null;
144            }
145            NodeIterable<Node> nodesIterable = original().nodes();
146            duplicationMap = graph().addDuplicates(nodesIterable, graph(), nodesIterable.count(), dr);
147            finishDuplication();
148            nodesReady = true;
149        } else {
150            // TODO (gd) apply fix ?
151        }
152    }
153
154    protected static NodeBitMap computeNodes(Graph graph, Iterable<AbstractBeginNode> blocks) {
155        return computeNodes(graph, blocks, Collections.emptyList());
156    }
157
158    protected static NodeBitMap computeNodes(Graph graph, Iterable<AbstractBeginNode> blocks, Iterable<LoopExitNode> earlyExits) {
159        final NodeBitMap nodes = graph.createNodeBitMap();
160        for (AbstractBeginNode b : blocks) {
161            if (b.isDeleted()) {
162                continue;
163            }
164
165            for (Node n : b.getBlockNodes()) {
166                if (n instanceof Invoke) {
167                    nodes.mark(((Invoke) n).callTarget());
168                }
169                if (n instanceof NodeWithState) {
170                    NodeWithState withState = (NodeWithState) n;
171                    withState.states().forEach(state -> state.applyToVirtual(node -> nodes.mark(node)));
172                }
173                nodes.mark(n);
174            }
175        }
176        for (LoopExitNode earlyExit : earlyExits) {
177            if (earlyExit.isDeleted()) {
178                continue;
179            }
180
181            FrameState stateAfter = earlyExit.stateAfter();
182            if (stateAfter != null) {
183                stateAfter.applyToVirtual(node -> nodes.mark(node));
184            }
185            nodes.mark(earlyExit);
186            for (ProxyNode proxy : earlyExit.proxies()) {
187                nodes.mark(proxy);
188            }
189        }
190
191        final NodeBitMap notloopNodes = graph.createNodeBitMap();
192        for (AbstractBeginNode b : blocks) {
193            if (b.isDeleted()) {
194                continue;
195            }
196
197            for (Node n : b.getBlockNodes()) {
198                if (n instanceof CommitAllocationNode) {
199                    for (VirtualObjectNode obj : ((CommitAllocationNode) n).getVirtualObjects()) {
200                        markFloating(obj, nodes, notloopNodes);
201                    }
202                }
203                if (n instanceof MonitorEnterNode) {
204                    markFloating(((MonitorEnterNode) n).getMonitorId(), nodes, notloopNodes);
205                }
206                for (Node usage : n.usages()) {
207                    markFloating(usage, nodes, notloopNodes);
208                }
209            }
210        }
211
212        return nodes;
213    }
214
215    private static boolean markFloating(Node n, NodeBitMap loopNodes, NodeBitMap notloopNodes) {
216        if (loopNodes.isMarked(n)) {
217            return true;
218        }
219        if (notloopNodes.isMarked(n)) {
220            return false;
221        }
222        if (n instanceof FixedNode) {
223            return false;
224        }
225        boolean mark = false;
226        if (n instanceof PhiNode) {
227            PhiNode phi = (PhiNode) n;
228            mark = loopNodes.isMarked(phi.merge());
229            if (mark) {
230                loopNodes.mark(n);
231            } else {
232                notloopNodes.mark(n);
233                return false;
234            }
235        }
236        for (Node usage : n.usages()) {
237            if (markFloating(usage, loopNodes, notloopNodes)) {
238                mark = true;
239            }
240        }
241        if (mark) {
242            loopNodes.mark(n);
243            return true;
244        }
245        notloopNodes.mark(n);
246        return false;
247    }
248
249    public static NodeIterable<AbstractBeginNode> toHirBlocks(final Iterable<Block> blocks) {
250        return new NodeIterable<AbstractBeginNode>() {
251
252            public Iterator<AbstractBeginNode> iterator() {
253                final Iterator<Block> it = blocks.iterator();
254                return new Iterator<AbstractBeginNode>() {
255
256                    @Override
257                    public void remove() {
258                        throw new UnsupportedOperationException();
259                    }
260
261                    public AbstractBeginNode next() {
262                        return it.next().getBeginNode();
263                    }
264
265                    public boolean hasNext() {
266                        return it.hasNext();
267                    }
268                };
269            }
270
271        };
272    }
273
274    public static NodeIterable<LoopExitNode> toHirExits(final Iterable<Block> blocks) {
275        return new NodeIterable<LoopExitNode>() {
276
277            public Iterator<LoopExitNode> iterator() {
278                final Iterator<Block> it = blocks.iterator();
279                return new Iterator<LoopExitNode>() {
280
281                    @Override
282                    public void remove() {
283                        throw new UnsupportedOperationException();
284                    }
285
286                    public LoopExitNode next() {
287                        return (LoopExitNode) it.next().getBeginNode();
288                    }
289
290                    public boolean hasNext() {
291                        return it.hasNext();
292                    }
293                };
294            }
295
296        };
297    }
298
299    /**
300     * Merges the early exits (i.e. loop exits) that were duplicated as part of this fragment, with
301     * the original fragment's exits.
302     */
303    protected void mergeEarlyExits() {
304        assert isDuplicate();
305        StructuredGraph graph = graph();
306        for (AbstractBeginNode earlyExit : LoopFragment.toHirBlocks(original().loop().loop().getExits())) {
307            LoopExitNode loopEarlyExit = (LoopExitNode) earlyExit;
308            FixedNode next = loopEarlyExit.next();
309            if (loopEarlyExit.isDeleted() || !this.original().contains(loopEarlyExit)) {
310                continue;
311            }
312            AbstractBeginNode newEarlyExit = getDuplicatedNode(loopEarlyExit);
313            if (newEarlyExit == null) {
314                continue;
315            }
316            MergeNode merge = graph.add(new MergeNode());
317            EndNode originalEnd = graph.add(new EndNode());
318            EndNode newEnd = graph.add(new EndNode());
319            merge.addForwardEnd(originalEnd);
320            merge.addForwardEnd(newEnd);
321            loopEarlyExit.setNext(originalEnd);
322            newEarlyExit.setNext(newEnd);
323            merge.setNext(next);
324
325            FrameState exitState = loopEarlyExit.stateAfter();
326            if (exitState != null) {
327                FrameState originalExitState = exitState;
328                exitState = exitState.duplicateWithVirtualState();
329                loopEarlyExit.setStateAfter(exitState);
330                merge.setStateAfter(originalExitState);
331                /*
332                 * Using the old exit's state as the merge's state is necessary because some of the
333                 * VirtualState nodes contained in the old exit's state may be shared by other
334                 * dominated VirtualStates. Those dominated virtual states need to see the
335                 * proxy->phi update that are applied below.
336                 *
337                 * We now update the original fragment's nodes accordingly:
338                 */
339                originalExitState.applyToVirtual(node -> original.nodes.clearAndGrow(node));
340                exitState.applyToVirtual(node -> original.nodes.markAndGrow(node));
341            }
342            FrameState finalExitState = exitState;
343
344            for (Node anchored : loopEarlyExit.anchored().snapshot()) {
345                anchored.replaceFirstInput(loopEarlyExit, merge);
346            }
347
348            boolean newEarlyExitIsLoopExit = newEarlyExit instanceof LoopExitNode;
349            for (ProxyNode vpn : loopEarlyExit.proxies().snapshot()) {
350                if (vpn.hasNoUsages()) {
351                    continue;
352                }
353                if (vpn.value() == null) {
354                    assert vpn instanceof GuardProxyNode;
355                    vpn.replaceAtUsages(null);
356                    continue;
357                }
358                final ValueNode replaceWith;
359                ValueNode newVpn = prim(newEarlyExitIsLoopExit ? vpn : vpn.value());
360                if (newVpn != null) {
361                    PhiNode phi;
362                    if (vpn instanceof ValueProxyNode) {
363                        phi = graph.addWithoutUnique(new ValuePhiNode(vpn.stamp(), merge));
364                    } else if (vpn instanceof GuardProxyNode) {
365                        phi = graph.addWithoutUnique(new GuardPhiNode(merge));
366                    } else {
367                        throw JVMCIError.shouldNotReachHere();
368                    }
369                    phi.addInput(vpn);
370                    phi.addInput(newVpn);
371                    replaceWith = phi;
372                } else {
373                    replaceWith = vpn.value();
374                }
375                vpn.replaceAtMatchingUsages(replaceWith, usage -> {
376                    if (merge.isPhiAtMerge(usage)) {
377                        return false;
378                    }
379                    if (usage instanceof VirtualState) {
380                        VirtualState stateUsage = (VirtualState) usage;
381                        if (finalExitState.isPartOfThisState(stateUsage)) {
382                            return false;
383                        }
384                    }
385                    return true;
386                });
387            }
388        }
389    }
390}