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 */
23 package org.graalvm.compiler.hotspot.phases;
24
25 import static org.graalvm.compiler.phases.common.DeadCodeEliminationPhase.Optionality.Required;
26
27 import org.graalvm.compiler.core.common.PermanentBailoutException;
28 import org.graalvm.compiler.core.common.cfg.Loop;
29 import org.graalvm.compiler.core.common.type.Stamp;
30 import org.graalvm.compiler.debug.CounterKey;
31 import org.graalvm.compiler.debug.DebugContext;
32 import org.graalvm.compiler.debug.GraalError;
33 import org.graalvm.compiler.graph.Node;
34 import org.graalvm.compiler.graph.iterators.NodeIterable;
35 import org.graalvm.compiler.loop.LoopsData;
36 import org.graalvm.compiler.loop.phases.LoopTransformations;
37 import org.graalvm.compiler.nodeinfo.InputType;
38 import org.graalvm.compiler.nodeinfo.Verbosity;
39 import org.graalvm.compiler.nodes.AbstractBeginNode;
40 import org.graalvm.compiler.nodes.AbstractLocalNode;
41 import org.graalvm.compiler.nodes.EntryMarkerNode;
42 import org.graalvm.compiler.nodes.EntryProxyNode;
43 import org.graalvm.compiler.nodes.FixedNode;
44 import org.graalvm.compiler.nodes.FrameState;
45 import org.graalvm.compiler.nodes.LoopBeginNode;
46 import org.graalvm.compiler.nodes.ParameterNode;
47 import org.graalvm.compiler.nodes.StartNode;
48 import org.graalvm.compiler.nodes.StructuredGraph;
49 import org.graalvm.compiler.nodes.ValueNode;
50 import org.graalvm.compiler.nodes.cfg.Block;
51 import org.graalvm.compiler.nodes.extended.OSRLocalNode;
52 import org.graalvm.compiler.nodes.extended.OSRLockNode;
53 import org.graalvm.compiler.nodes.extended.OSRMonitorEnterNode;
54 import org.graalvm.compiler.nodes.extended.OSRStartNode;
55 import org.graalvm.compiler.nodes.java.AccessMonitorNode;
56 import org.graalvm.compiler.nodes.java.MonitorEnterNode;
57 import org.graalvm.compiler.nodes.java.MonitorExitNode;
58 import org.graalvm.compiler.nodes.java.MonitorIdNode;
59 import org.graalvm.compiler.nodes.util.GraphUtil;
60 import org.graalvm.compiler.options.Option;
61 import org.graalvm.compiler.options.OptionKey;
62 import org.graalvm.compiler.options.OptionType;
63 import org.graalvm.compiler.options.OptionValues;
64 import org.graalvm.compiler.phases.Phase;
65 import org.graalvm.compiler.phases.common.DeadCodeEliminationPhase;
66
67 import jdk.vm.ci.runtime.JVMCICompiler;
68
69 public class OnStackReplacementPhase extends Phase {
70
71 public static class Options {
72 // @formatter:off
73 @Option(help = "Deoptimize OSR compiled code when the OSR entry loop is finished " +
74 "if there is no mature profile available for the rest of the method.", type = OptionType.Debug)
75 public static final OptionKey<Boolean> DeoptAfterOSR = new OptionKey<>(true);
76 @Option(help = "Support OSR compilations with locks. If DeoptAfterOSR is true we can per definition not have " +
77 "unbalaced enter/extis mappings. If DeoptAfterOSR is false insert artificial monitor enters after " +
78 "the OSRStart to have balanced enter/exits in the graph.", type = OptionType.Debug)
79 public static final OptionKey<Boolean> SupportOSRWithLocks = new OptionKey<>(true);
80 // @formatter:on
81 }
82
83 private static final CounterKey OsrWithLocksCount = DebugContext.counter("OSRWithLocks");
84
85 private static boolean supportOSRWithLocks(OptionValues options) {
86 return Options.SupportOSRWithLocks.getValue(options);
87 }
88
89 @Override
90 protected void run(StructuredGraph graph) {
91 DebugContext debug = graph.getDebug();
92 if (graph.getEntryBCI() == JVMCICompiler.INVOCATION_ENTRY_BCI) {
93 // This happens during inlining in a OSR method, because the same phase plan will be
94 // used.
95 assert graph.getNodes(EntryMarkerNode.TYPE).isEmpty();
96 return;
97 }
98 debug.dump(DebugContext.DETAILED_LEVEL, graph, "OnStackReplacement initial at bci %d", graph.getEntryBCI());
99
100 EntryMarkerNode osr;
101 int maxIterations = -1;
102 int iterations = 0;
103
104 final EntryMarkerNode originalOSRNode = getEntryMarker(graph);
105 final LoopBeginNode originalOSRLoop = osrLoop(originalOSRNode);
106 final boolean currentOSRWithLocks = osrWithLocks(originalOSRNode);
107
108 if (originalOSRLoop == null) {
109 /*
110 * OSR with Locks: We do not have an OSR loop for the original OSR bci. Therefore we
111 * cannot decide where to deopt and which framestate will be used. In the worst case the
112 * framestate of the OSR entry would be used.
113 */
114 throw new PermanentBailoutException("OSR compilation without OSR entry loop.");
115 }
116
117 if (!supportOSRWithLocks(graph.getOptions()) && currentOSRWithLocks) {
118 throw new PermanentBailoutException("OSR with locks disabled.");
119 }
120
121 do {
122 osr = getEntryMarker(graph);
123 LoopsData loops = new LoopsData(graph);
124 // Find the loop that contains the EntryMarker
125 Loop<Block> l = loops.getCFG().getNodeToBlock().get(osr).getLoop();
126 if (l == null) {
127 break;
128 }
129
130 iterations++;
131 if (maxIterations == -1) {
132 maxIterations = l.getDepth();
133 } else if (iterations > maxIterations) {
134 throw GraalError.shouldNotReachHere();
135 }
136 // Peel the outermost loop first
137 while (l.getParent() != null) {
138 l = l.getParent();
139 }
140
141 LoopTransformations.peel(loops.loop(l));
142 osr.replaceAtUsages(InputType.Guard, AbstractBeginNode.prevBegin((FixedNode) osr.predecessor()));
143 for (Node usage : osr.usages().snapshot()) {
144 EntryProxyNode proxy = (EntryProxyNode) usage;
145 proxy.replaceAndDelete(proxy.value());
146 }
147 GraphUtil.removeFixedWithUnusedInputs(osr);
148 debug.dump(DebugContext.DETAILED_LEVEL, graph, "OnStackReplacement loop peeling result");
149 } while (true);
150
151 FrameState osrState = osr.stateAfter();
152 osr.setStateAfter(null);
153 OSRStartNode osrStart = graph.add(new OSRStartNode());
154 StartNode start = graph.start();
155 FixedNode next = osr.next();
156 osr.setNext(null);
157 osrStart.setNext(next);
158 graph.setStart(osrStart);
159 osrStart.setStateAfter(osrState);
160
161 debug.dump(DebugContext.DETAILED_LEVEL, graph, "OnStackReplacement after setting OSR start");
162 final int localsSize = osrState.localsSize();
163 final int locksSize = osrState.locksSize();
164
165 for (int i = 0; i < localsSize + locksSize; i++) {
166 ValueNode value = null;
167 if (i >= localsSize) {
168 value = osrState.lockAt(i - localsSize);
169 } else {
170 value = osrState.localAt(i);
171 }
172 if (value instanceof EntryProxyNode) {
173 EntryProxyNode proxy = (EntryProxyNode) value;
174 /*
175 * we need to drop the stamp since the types we see during OSR may be too precise
176 * (if a branch was not parsed for example).
177 */
178 Stamp s = proxy.stamp().unrestricted();
179 AbstractLocalNode osrLocal = null;
180 if (i >= localsSize) {
181 osrLocal = graph.addOrUnique(new OSRLockNode(i - localsSize, s));
182 } else {
183 osrLocal = graph.addOrUnique(new OSRLocalNode(i, s));
184 }
185 proxy.replaceAndDelete(osrLocal);
186 } else {
187 assert value == null || value instanceof OSRLocalNode;
188 }
189 }
190
191 osr.replaceAtUsages(InputType.Guard, osrStart);
192 debug.dump(DebugContext.DETAILED_LEVEL, graph, "OnStackReplacement after replacing entry proxies");
193 GraphUtil.killCFG(start);
194 debug.dump(DebugContext.DETAILED_LEVEL, graph, "OnStackReplacement result");
195 new DeadCodeEliminationPhase(Required).apply(graph);
196
197 if (currentOSRWithLocks) {
198 OsrWithLocksCount.increment(debug);
199 for (int i = osrState.monitorIdCount() - 1; i >= 0; --i) {
200 MonitorIdNode id = osrState.monitorIdAt(i);
201 ValueNode lockedObject = osrState.lockAt(i);
202 OSRMonitorEnterNode osrMonitorEnter = graph.add(new OSRMonitorEnterNode(lockedObject, id));
203 for (Node usage : id.usages()) {
204 if (usage instanceof AccessMonitorNode) {
205 AccessMonitorNode access = (AccessMonitorNode) usage;
206 access.setObject(lockedObject);
207 }
208 }
209 FixedNode oldNext = osrStart.next();
210 oldNext.replaceAtPredecessor(null);
211 osrMonitorEnter.setNext(oldNext);
212 osrStart.setNext(osrMonitorEnter);
213 }
214 debug.dump(DebugContext.DETAILED_LEVEL, graph, "After inserting OSR monitor enters");
215 /*
216 * Ensure balanced monitorenter - monitorexit
217 *
218 * Ensure that there is no monitor exit without a monitor enter in the graph. If there
219 * is one this can only be done by bytecode as we have the monitor enter before the OSR
220 * loop but the exit in a path of the loop that must be under a condition, else it will
221 * throw an IllegalStateException anyway in the 2.iteration
222 */
223 for (MonitorExitNode exit : graph.getNodes(MonitorExitNode.TYPE)) {
224 MonitorIdNode id = exit.getMonitorId();
225 if (id.usages().filter(MonitorEnterNode.class).count() != 1) {
226 throw new PermanentBailoutException("Unbalanced monitor enter-exit in OSR compilation with locks. Object is locked before the loop but released inside the loop.");
227 }
228 }
229 }
230 debug.dump(DebugContext.DETAILED_LEVEL, graph, "OnStackReplacement result");
231 new DeadCodeEliminationPhase(Required).apply(graph);
232 /*
233 * There must not be any parameter nodes left after OSR compilation.
234 */
235 assert graph.getNodes(ParameterNode.TYPE).count() == 0 : "OSR Compilation contains references to parameters.";
236 }
237
238 private static EntryMarkerNode getEntryMarker(StructuredGraph graph) {
239 NodeIterable<EntryMarkerNode> osrNodes = graph.getNodes(EntryMarkerNode.TYPE);
240 EntryMarkerNode osr = osrNodes.first();
241 if (osr == null) {
242 throw new PermanentBailoutException("No OnStackReplacementNode generated");
243 }
244 if (osrNodes.count() > 1) {
245 throw new GraalError("Multiple OnStackReplacementNodes generated");
246 }
247 if (osr.stateAfter().stackSize() != 0) {
248 throw new PermanentBailoutException("OSR with stack entries not supported: %s", osr.stateAfter().toString(Verbosity.Debugger));
249 }
250 return osr;
251 }
252
253 private static LoopBeginNode osrLoop(EntryMarkerNode osr) {
254 // Check that there is an OSR loop for the OSR begin
255 LoopsData loops = new LoopsData(osr.graph());
256 Loop<Block> l = loops.getCFG().getNodeToBlock().get(osr).getLoop();
257 if (l == null) {
258 return null;
259 }
260 return (LoopBeginNode) l.getHeader().getBeginNode();
261 }
262
263 private static boolean osrWithLocks(EntryMarkerNode osr) {
264 return osr.stateAfter().locksSize() != 0;
265 }
266
267 @Override
268 public float codeSizeIncrease() {
269 return 5.0f;
270 }
271 }