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.Debug;
31 import org.graalvm.compiler.debug.DebugCounter;
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 DebugCounter OsrWithLocksCount = Debug.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 if (graph.getEntryBCI() == JVMCICompiler.INVOCATION_ENTRY_BCI) {
92 // This happens during inlining in a OSR method, because the same phase plan will be
93 // used.
94 assert graph.getNodes(EntryMarkerNode.TYPE).isEmpty();
95 return;
96 }
97 Debug.dump(Debug.DETAILED_LEVEL, graph, "OnStackReplacement initial at bci %d", graph.getEntryBCI());
98
99 EntryMarkerNode osr;
100 int maxIterations = -1;
101 int iterations = 0;
102
103 final EntryMarkerNode originalOSRNode = getEntryMarker(graph);
104 final LoopBeginNode originalOSRLoop = osrLoop(originalOSRNode);
105 final boolean currentOSRWithLocks = osrWithLocks(originalOSRNode);
106
107 if (originalOSRLoop == null) {
108 /*
109 * OSR with Locks: We do not have an OSR loop for the original OSR bci. Therefore we
110 * cannot decide where to deopt and which framestate will be used. In the worst case the
111 * framestate of the OSR entry would be used.
112 */
113 throw new PermanentBailoutException("OSR compilation without OSR entry loop.");
114 }
115
116 if (!supportOSRWithLocks(graph.getOptions()) && currentOSRWithLocks) {
117 throw new PermanentBailoutException("OSR with locks disabled.");
118 }
119
120 do {
121 osr = getEntryMarker(graph);
122 LoopsData loops = new LoopsData(graph);
123 // Find the loop that contains the EntryMarker
124 Loop<Block> l = loops.getCFG().getNodeToBlock().get(osr).getLoop();
125 if (l == null) {
126 break;
127 }
128
129 iterations++;
130 if (maxIterations == -1) {
131 maxIterations = l.getDepth();
132 } else if (iterations > maxIterations) {
133 throw GraalError.shouldNotReachHere();
134 }
135 // Peel the outermost loop first
136 while (l.getParent() != null) {
137 l = l.getParent();
138 }
139
140 LoopTransformations.peel(loops.loop(l));
141 osr.replaceAtUsages(InputType.Guard, AbstractBeginNode.prevBegin((FixedNode) osr.predecessor()));
142 for (Node usage : osr.usages().snapshot()) {
143 EntryProxyNode proxy = (EntryProxyNode) usage;
144 proxy.replaceAndDelete(proxy.value());
145 }
146 GraphUtil.removeFixedWithUnusedInputs(osr);
147 Debug.dump(Debug.DETAILED_LEVEL, graph, "OnStackReplacement loop peeling result");
148 } while (true);
149
150 FrameState osrState = osr.stateAfter();
151 osr.setStateAfter(null);
152 OSRStartNode osrStart = graph.add(new OSRStartNode());
153 StartNode start = graph.start();
154 FixedNode next = osr.next();
155 osr.setNext(null);
156 osrStart.setNext(next);
157 graph.setStart(osrStart);
158 osrStart.setStateAfter(osrState);
159
160 Debug.dump(Debug.DETAILED_LEVEL, graph, "OnStackReplacement after setting OSR start");
161 final int localsSize = osrState.localsSize();
162 final int locksSize = osrState.locksSize();
163
164 for (int i = 0; i < localsSize + locksSize; i++) {
165 ValueNode value = null;
166 if (i >= localsSize) {
167 value = osrState.lockAt(i - localsSize);
168 } else {
169 value = osrState.localAt(i);
170 }
171 if (value instanceof EntryProxyNode) {
172 EntryProxyNode proxy = (EntryProxyNode) value;
173 /*
174 * we need to drop the stamp since the types we see during OSR may be too precise
175 * (if a branch was not parsed for example).
176 */
177 Stamp s = proxy.stamp().unrestricted();
178 AbstractLocalNode osrLocal = null;
179 if (i >= localsSize) {
180 osrLocal = graph.addOrUnique(new OSRLockNode(i - localsSize, s));
181 } else {
182 osrLocal = graph.addOrUnique(new OSRLocalNode(i, s));
183 }
184 proxy.replaceAndDelete(osrLocal);
185 } else {
186 assert value == null || value instanceof OSRLocalNode;
187 }
188 }
189
190 osr.replaceAtUsages(InputType.Guard, osrStart);
191 Debug.dump(Debug.DETAILED_LEVEL, graph, "OnStackReplacement after replacing entry proxies");
192 GraphUtil.killCFG(start);
193 Debug.dump(Debug.DETAILED_LEVEL, graph, "OnStackReplacement result");
194 new DeadCodeEliminationPhase(Required).apply(graph);
195
196 if (currentOSRWithLocks) {
197 OsrWithLocksCount.increment();
198 for (int i = osrState.monitorIdCount() - 1; i >= 0; --i) {
199 MonitorIdNode id = osrState.monitorIdAt(i);
200 ValueNode lockedObject = osrState.lockAt(i);
201 OSRMonitorEnterNode osrMonitorEnter = graph.add(new OSRMonitorEnterNode(lockedObject, id));
202 for (Node usage : id.usages()) {
203 if (usage instanceof AccessMonitorNode) {
204 AccessMonitorNode access = (AccessMonitorNode) usage;
205 access.setObject(lockedObject);
206 }
207 }
208 FixedNode oldNext = osrStart.next();
209 oldNext.replaceAtPredecessor(null);
210 osrMonitorEnter.setNext(oldNext);
211 osrStart.setNext(osrMonitorEnter);
212 }
213 Debug.dump(Debug.DETAILED_LEVEL, graph, "After inserting OSR monitor enters");
214 /*
215 * Ensure balanced monitorenter - monitorexit
216 *
217 * Ensure that there is no monitor exit without a monitor enter in the graph. If there
218 * is one this can only be done by bytecode as we have the monitor enter before the OSR
219 * loop but the exit in a path of the loop that must be under a condition, else it will
220 * throw an IllegalStateException anyway in the 2.iteration
221 */
222 for (MonitorExitNode exit : graph.getNodes(MonitorExitNode.TYPE)) {
223 MonitorIdNode id = exit.getMonitorId();
224 if (id.usages().filter(MonitorEnterNode.class).count() != 1) {
225 throw new PermanentBailoutException("Unbalanced monitor enter-exit in OSR compilation with locks. Object is locked before the loop but released inside the loop.");
226 }
227 }
228 }
229 Debug.dump(Debug.DETAILED_LEVEL, graph, "OnStackReplacement result");
230 new DeadCodeEliminationPhase(Required).apply(graph);
231 /*
232 * There must not be any parameter nodes left after OSR compilation.
233 */
234 assert graph.getNodes(ParameterNode.TYPE).count() == 0 : "OSR Compilation contains references to parameters.";
235 }
236
237 private static EntryMarkerNode getEntryMarker(StructuredGraph graph) {
238 NodeIterable<EntryMarkerNode> osrNodes = graph.getNodes(EntryMarkerNode.TYPE);
239 EntryMarkerNode osr = osrNodes.first();
240 if (osr == null) {
241 throw new PermanentBailoutException("No OnStackReplacementNode generated");
242 }
243 if (osrNodes.count() > 1) {
244 throw new GraalError("Multiple OnStackReplacementNodes generated");
245 }
246 if (osr.stateAfter().stackSize() != 0) {
247 throw new PermanentBailoutException("OSR with stack entries not supported: %s", osr.stateAfter().toString(Verbosity.Debugger));
248 }
249 return osr;
250 }
251
252 private static LoopBeginNode osrLoop(EntryMarkerNode osr) {
253 // Check that there is an OSR loop for the OSR begin
254 LoopsData loops = new LoopsData(osr.graph());
255 Loop<Block> l = loops.getCFG().getNodeToBlock().get(osr).getLoop();
256 if (l == null) {
257 return null;
258 }
259 return (LoopBeginNode) l.getHeader().getBeginNode();
260 }
261
262 private static boolean osrWithLocks(EntryMarkerNode osr) {
263 return osr.stateAfter().locksSize() != 0;
264 }
265
266 @Override
267 public float codeSizeIncrease() {
268 return 5.0f;
269 }
270 }