1/*
2 * Copyright (c) 2011, 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.hotspot.phases;
24
25import static org.graalvm.compiler.phases.common.DeadCodeEliminationPhase.Optionality.Required;
26
27import org.graalvm.compiler.common.PermanentBailoutException;
28import org.graalvm.compiler.core.common.cfg.Loop;
29import org.graalvm.compiler.debug.Debug;
30import org.graalvm.compiler.debug.GraalError;
31import org.graalvm.compiler.graph.Node;
32import org.graalvm.compiler.graph.iterators.NodeIterable;
33import org.graalvm.compiler.loop.LoopsData;
34import org.graalvm.compiler.loop.phases.LoopTransformations;
35import org.graalvm.compiler.nodeinfo.InputType;
36import org.graalvm.compiler.nodeinfo.Verbosity;
37import org.graalvm.compiler.nodes.AbstractBeginNode;
38import org.graalvm.compiler.nodes.EntryMarkerNode;
39import org.graalvm.compiler.nodes.EntryProxyNode;
40import org.graalvm.compiler.nodes.FixedNode;
41import org.graalvm.compiler.nodes.FrameState;
42import org.graalvm.compiler.nodes.StartNode;
43import org.graalvm.compiler.nodes.StructuredGraph;
44import org.graalvm.compiler.nodes.ValueNode;
45import org.graalvm.compiler.nodes.cfg.Block;
46import org.graalvm.compiler.nodes.extended.OSRLocalNode;
47import org.graalvm.compiler.nodes.extended.OSRStartNode;
48import org.graalvm.compiler.nodes.util.GraphUtil;
49import org.graalvm.compiler.phases.Phase;
50import org.graalvm.compiler.phases.common.DeadCodeEliminationPhase;
51
52import jdk.vm.ci.runtime.JVMCICompiler;
53
54public class OnStackReplacementPhase extends Phase {
55
56    @Override
57    protected void run(StructuredGraph graph) {
58        if (graph.getEntryBCI() == JVMCICompiler.INVOCATION_ENTRY_BCI) {
59            // This happens during inlining in a OSR method, because the same phase plan will be
60            // used.
61            assert graph.getNodes(EntryMarkerNode.TYPE).isEmpty();
62            return;
63        }
64        Debug.dump(Debug.INFO_LOG_LEVEL, graph, "OnStackReplacement initial");
65        EntryMarkerNode osr;
66        int maxIterations = -1;
67        int iterations = 0;
68        do {
69            osr = getEntryMarker(graph);
70            LoopsData loops = new LoopsData(graph);
71            // Find the loop that contains the EntryMarker
72            Loop<Block> l = loops.getCFG().getNodeToBlock().get(osr).getLoop();
73            if (l == null) {
74                break;
75            }
76            iterations++;
77            if (maxIterations == -1) {
78                maxIterations = l.getDepth();
79            } else if (iterations > maxIterations) {
80                throw GraalError.shouldNotReachHere();
81            }
82            // Peel the outermost loop first
83            while (l.getParent() != null) {
84                l = l.getParent();
85            }
86
87            LoopTransformations.peel(loops.loop(l));
88            osr.replaceAtUsages(InputType.Guard, AbstractBeginNode.prevBegin((FixedNode) osr.predecessor()));
89            for (Node usage : osr.usages().snapshot()) {
90                EntryProxyNode proxy = (EntryProxyNode) usage;
91                proxy.replaceAndDelete(proxy.value());
92            }
93            GraphUtil.removeFixedWithUnusedInputs(osr);
94            Debug.dump(Debug.INFO_LOG_LEVEL, graph, "OnStackReplacement loop peeling result");
95        } while (true);
96
97        FrameState osrState = osr.stateAfter();
98        osr.setStateAfter(null);
99        OSRStartNode osrStart = graph.add(new OSRStartNode());
100        StartNode start = graph.start();
101        FixedNode next = osr.next();
102        osr.setNext(null);
103        osrStart.setNext(next);
104        graph.setStart(osrStart);
105        osrStart.setStateAfter(osrState);
106
107        for (int i = 0; i < osrState.localsSize(); i++) {
108            ValueNode value = osrState.localAt(i);
109            if (value instanceof EntryProxyNode) {
110                EntryProxyNode proxy = (EntryProxyNode) value;
111                /*
112                 * we need to drop the stamp since the types we see during OSR may be too precise
113                 * (if a branch was not parsed for example).
114                 */
115                proxy.replaceAndDelete(graph.addOrUnique(new OSRLocalNode(i, proxy.stamp().unrestricted())));
116            } else {
117                assert value == null || value instanceof OSRLocalNode;
118            }
119        }
120        osr.replaceAtUsages(InputType.Guard, osrStart);
121        assert osr.usages().isEmpty();
122
123        GraphUtil.killCFG(start);
124
125        Debug.dump(Debug.INFO_LOG_LEVEL, graph, "OnStackReplacement result");
126        new DeadCodeEliminationPhase(Required).apply(graph);
127    }
128
129    private static EntryMarkerNode getEntryMarker(StructuredGraph graph) {
130        NodeIterable<EntryMarkerNode> osrNodes = graph.getNodes(EntryMarkerNode.TYPE);
131        EntryMarkerNode osr = osrNodes.first();
132        if (osr == null) {
133            throw new PermanentBailoutException("No OnStackReplacementNode generated");
134        }
135        if (osrNodes.count() > 1) {
136            throw new GraalError("Multiple OnStackReplacementNodes generated");
137        }
138        if (osr.stateAfter().locksSize() != 0) {
139            throw new PermanentBailoutException("OSR with locks not supported");
140        }
141        if (osr.stateAfter().stackSize() != 0) {
142            throw new PermanentBailoutException("OSR with stack entries not supported: %s", osr.stateAfter().toString(Verbosity.Debugger));
143        }
144        return osr;
145    }
146
147    @Override
148    public float codeSizeIncrease() {
149        return 5.0f;
150    }
151}
152