1 /*
2 * Copyright (c) 2012, 2018, 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
24
25 package org.graalvm.compiler.java;
26
27 import static org.graalvm.compiler.bytecode.Bytecodes.DUP;
28 import static org.graalvm.compiler.bytecode.Bytecodes.DUP2;
29 import static org.graalvm.compiler.bytecode.Bytecodes.DUP2_X1;
30 import static org.graalvm.compiler.bytecode.Bytecodes.DUP2_X2;
31 import static org.graalvm.compiler.bytecode.Bytecodes.DUP_X1;
32 import static org.graalvm.compiler.bytecode.Bytecodes.DUP_X2;
33 import static org.graalvm.compiler.bytecode.Bytecodes.POP;
34 import static org.graalvm.compiler.bytecode.Bytecodes.POP2;
35 import static org.graalvm.compiler.bytecode.Bytecodes.SWAP;
36 import static org.graalvm.compiler.debug.GraalError.shouldNotReachHere;
37 import static org.graalvm.compiler.nodes.FrameState.TWO_SLOT_MARKER;
38
39 import java.util.ArrayList;
40 import java.util.Arrays;
41 import java.util.List;
42 import java.util.function.Function;
43
44 import org.graalvm.compiler.bytecode.Bytecode;
45 import org.graalvm.compiler.bytecode.ResolvedJavaMethodBytecode;
46 import org.graalvm.compiler.core.common.PermanentBailoutException;
47 import org.graalvm.compiler.core.common.type.StampFactory;
48 import org.graalvm.compiler.core.common.type.StampPair;
49 import org.graalvm.compiler.debug.DebugContext;
50 import org.graalvm.compiler.debug.GraalError;
51 import org.graalvm.compiler.graph.NodeSourcePosition;
52 import org.graalvm.compiler.java.BciBlockMapping.BciBlock;
53 import org.graalvm.compiler.nodeinfo.Verbosity;
54 import org.graalvm.compiler.nodes.AbstractMergeNode;
55 import org.graalvm.compiler.nodes.ConstantNode;
56 import org.graalvm.compiler.nodes.FrameState;
57 import org.graalvm.compiler.nodes.LoopBeginNode;
58 import org.graalvm.compiler.nodes.LoopExitNode;
59 import org.graalvm.compiler.nodes.NodeView;
60 import org.graalvm.compiler.nodes.ParameterNode;
61 import org.graalvm.compiler.nodes.PhiNode;
62 import org.graalvm.compiler.nodes.ProxyNode;
63 import org.graalvm.compiler.nodes.StateSplit;
64 import org.graalvm.compiler.nodes.StructuredGraph;
65 import org.graalvm.compiler.nodes.ValueNode;
66 import org.graalvm.compiler.nodes.ValuePhiNode;
67 import org.graalvm.compiler.nodes.calc.FloatingNode;
68 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderConfiguration.Plugins;
69 import org.graalvm.compiler.nodes.graphbuilderconf.GraphBuilderTool;
70 import org.graalvm.compiler.nodes.graphbuilderconf.IntrinsicContext.SideEffectsState;
71 import org.graalvm.compiler.nodes.graphbuilderconf.ParameterPlugin;
72 import org.graalvm.compiler.nodes.java.MonitorIdNode;
73 import org.graalvm.compiler.nodes.util.GraphUtil;
74
75 import jdk.vm.ci.code.BytecodeFrame;
76 import jdk.vm.ci.meta.Assumptions;
77 import jdk.vm.ci.meta.JavaKind;
78 import jdk.vm.ci.meta.JavaType;
79 import jdk.vm.ci.meta.ResolvedJavaMethod;
80 import jdk.vm.ci.meta.ResolvedJavaType;
81 import jdk.vm.ci.meta.Signature;
82
83 public final class FrameStateBuilder implements SideEffectsState {
84
85 private static final ValueNode[] EMPTY_ARRAY = new ValueNode[0];
86 private static final MonitorIdNode[] EMPTY_MONITOR_ARRAY = new MonitorIdNode[0];
87
88 private final BytecodeParser parser;
89 private final GraphBuilderTool tool;
90 private final Bytecode code;
91 private int stackSize;
92 protected final ValueNode[] locals;
93 protected final ValueNode[] stack;
94 private ValueNode[] lockedObjects;
95 private boolean canVerifyKind;
96
97 /**
98 * @see BytecodeFrame#rethrowException
99 */
100 private boolean rethrowException;
101
102 private MonitorIdNode[] monitorIds;
103 private final StructuredGraph graph;
104 private final boolean clearNonLiveLocals;
105 private FrameState outerFrameState;
106 private NodeSourcePosition outerSourcePosition;
107
108 /**
109 * The closest {@link StateSplit#hasSideEffect() side-effect} predecessors. There will be more
110 * than one when the current block contains no side-effects but merging predecessor blocks do.
111 */
112 private List<StateSplit> sideEffects;
113
114 /**
115 * Creates a new frame state builder for the given method and the given target graph.
116 *
117 * @param method the method whose frame is simulated
118 * @param graph the target graph of Graal nodes created by the builder
119 */
120 public FrameStateBuilder(GraphBuilderTool tool, ResolvedJavaMethod method, StructuredGraph graph) {
121 this(tool, new ResolvedJavaMethodBytecode(method), graph, false);
122 }
123
124 /**
125 * Creates a new frame state builder for the given code attribute, method and the given target
126 * graph. Additionally specifies if nonLiveLocals should be retained.
127 *
128 * @param code the bytecode in which the frame exists
129 * @param graph the target graph of Graal nodes created by the builder
130 * @param shouldRetainLocalVariables specifies if nonLiveLocals should be retained in state.
131 */
132 public FrameStateBuilder(GraphBuilderTool tool, Bytecode code, StructuredGraph graph, boolean shouldRetainLocalVariables) {
133 this.tool = tool;
134 if (tool instanceof BytecodeParser) {
135 this.parser = (BytecodeParser) tool;
136 } else {
137 this.parser = null;
138 }
139 this.code = code;
140 this.locals = allocateArray(code.getMaxLocals());
141 this.stack = allocateArray(Math.max(1, code.getMaxStackSize()));
142 this.lockedObjects = allocateArray(0);
143
144 assert graph != null;
145
146 this.monitorIds = EMPTY_MONITOR_ARRAY;
147 this.graph = graph;
148 this.clearNonLiveLocals = !shouldRetainLocalVariables;
149 this.canVerifyKind = true;
150 }
151
152 public void disableKindVerification() {
153 canVerifyKind = false;
154 }
155
156 public void initializeFromArgumentsArray(ValueNode[] arguments) {
157
158 int javaIndex = 0;
159 int index = 0;
160 if (!getMethod().isStatic()) {
161 // set the receiver
162 locals[javaIndex] = arguments[index];
163 javaIndex = 1;
164 index = 1;
165 }
166 Signature sig = getMethod().getSignature();
167 int max = sig.getParameterCount(false);
168 for (int i = 0; i < max; i++) {
169 JavaKind kind = sig.getParameterKind(i);
170 locals[javaIndex] = arguments[index];
171 javaIndex++;
172 if (kind.needsTwoSlots()) {
173 locals[javaIndex] = TWO_SLOT_MARKER;
174 javaIndex++;
175 }
176 index++;
177 }
178 }
179
180 public void initializeForMethodStart(Assumptions assumptions, boolean eagerResolve, Plugins plugins) {
181
182 int javaIndex = 0;
183 int index = 0;
184 ResolvedJavaMethod method = getMethod();
185 ResolvedJavaType originalType = method.getDeclaringClass();
186 if (!method.isStatic()) {
187 // add the receiver
188 FloatingNode receiver = null;
189 StampPair receiverStamp = null;
190 if (plugins != null) {
191 receiverStamp = plugins.getOverridingStamp(tool, originalType, true);
192 }
193 if (receiverStamp == null) {
194 receiverStamp = StampFactory.forDeclaredType(assumptions, originalType, true);
195 }
196
197 if (plugins != null) {
198 for (ParameterPlugin plugin : plugins.getParameterPlugins()) {
199 receiver = plugin.interceptParameter(tool, index, receiverStamp);
200 if (receiver != null) {
201 break;
202 }
203 }
204 }
205 if (receiver == null) {
206 receiver = new ParameterNode(javaIndex, receiverStamp);
207 }
208
209 locals[javaIndex] = graph.addOrUniqueWithInputs(receiver);
210 javaIndex = 1;
211 index = 1;
212 }
213 Signature sig = method.getSignature();
214 int max = sig.getParameterCount(false);
215 ResolvedJavaType accessingClass = originalType;
216 for (int i = 0; i < max; i++) {
217 JavaType type = sig.getParameterType(i, accessingClass);
218 if (eagerResolve) {
219 type = type.resolve(accessingClass);
220 }
221 JavaKind kind = type.getJavaKind();
222 StampPair stamp = null;
223 if (plugins != null) {
224 stamp = plugins.getOverridingStamp(tool, type, false);
225 }
226 if (stamp == null) {
227 // GR-714: subword inputs cannot be trusted
228 if (kind.getStackKind() != kind) {
229 stamp = StampPair.createSingle(StampFactory.forKind(JavaKind.Int));
230 } else {
231 stamp = StampFactory.forDeclaredType(assumptions, type, false);
232 }
233 }
234
235 FloatingNode param = null;
236 if (plugins != null) {
237 for (ParameterPlugin plugin : plugins.getParameterPlugins()) {
238 param = plugin.interceptParameter(tool, index, stamp);
239 if (param != null) {
240 break;
241 }
242 }
243 }
244 if (param == null) {
245 param = new ParameterNode(index, stamp);
246 }
247
248 locals[javaIndex] = graph.addOrUniqueWithInputs(param);
249 javaIndex++;
250 if (kind.needsTwoSlots()) {
251 locals[javaIndex] = TWO_SLOT_MARKER;
252 javaIndex++;
253 }
254 index++;
255 }
256 }
257
258 private FrameStateBuilder(FrameStateBuilder other) {
259 this.parser = other.parser;
260 this.tool = other.tool;
261 this.code = other.code;
262 this.stackSize = other.stackSize;
263 this.locals = other.locals.clone();
264 this.stack = other.stack.clone();
265 this.lockedObjects = other.lockedObjects.length == 0 ? other.lockedObjects : other.lockedObjects.clone();
266 this.rethrowException = other.rethrowException;
267 this.canVerifyKind = other.canVerifyKind;
268
269 assert locals.length == code.getMaxLocals();
270 assert stack.length == Math.max(1, code.getMaxStackSize());
271
272 assert other.graph != null;
273 graph = other.graph;
274 clearNonLiveLocals = other.clearNonLiveLocals;
275 monitorIds = other.monitorIds.length == 0 ? other.monitorIds : other.monitorIds.clone();
276
277 assert lockedObjects.length == monitorIds.length;
278 }
279
280 private static ValueNode[] allocateArray(int length) {
281 return length == 0 ? EMPTY_ARRAY : new ValueNode[length];
282 }
283
284 public ResolvedJavaMethod getMethod() {
285 return code.getMethod();
286 }
287
288 @Override
289 public String toString() {
290 StringBuilder sb = new StringBuilder();
291 sb.append("[locals: [");
292 for (int i = 0; i < locals.length; i++) {
293 sb.append(i == 0 ? "" : ",").append(locals[i] == null ? "_" : locals[i] == TWO_SLOT_MARKER ? "#" : locals[i].toString(Verbosity.Id));
294 }
295 sb.append("] stack: [");
296 for (int i = 0; i < stackSize; i++) {
297 sb.append(i == 0 ? "" : ",").append(stack[i] == null ? "_" : stack[i] == TWO_SLOT_MARKER ? "#" : stack[i].toString(Verbosity.Id));
298 }
299 sb.append("] locks: [");
300 for (int i = 0; i < lockedObjects.length; i++) {
301 sb.append(i == 0 ? "" : ",").append(lockedObjects[i].toString(Verbosity.Id)).append(" / ").append(monitorIds[i].toString(Verbosity.Id));
302 }
303 sb.append("]");
304 if (rethrowException) {
305 sb.append(" rethrowException");
306 }
307 sb.append("]");
308 return sb.toString();
309 }
310
311 public FrameState create(int bci, StateSplit forStateSplit) {
312 if (parser != null && parser.parsingIntrinsic()) {
313 NodeSourcePosition sourcePosition = parser.getGraph().trackNodeSourcePosition() ? createBytecodePosition(bci) : null;
314 return parser.intrinsicContext.createFrameState(parser.getGraph(), this, forStateSplit, sourcePosition);
315 }
316
317 // Skip intrinsic frames
318 return create(bci, parser != null ? parser.getNonIntrinsicAncestor() : null, false, null, null);
319 }
320
321 /**
322 * @param pushedValues if non-null, values to {@link #push(JavaKind, ValueNode)} to the stack
323 * before creating the {@link FrameState}
324 */
325 public FrameState create(int bci, BytecodeParser parent, boolean duringCall, JavaKind[] pushedSlotKinds, ValueNode[] pushedValues) {
326 if (outerFrameState == null && parent != null) {
327 assert !parent.parsingIntrinsic() : "must already have the next non-intrinsic ancestor";
328 outerFrameState = parent.getFrameStateBuilder().create(parent.bci(), parent.getNonIntrinsicAncestor(), true, null, null);
329 }
330 if (bci == BytecodeFrame.AFTER_EXCEPTION_BCI && parent != null) {
331 FrameState newFrameState = outerFrameState.duplicateModified(outerFrameState.bci, true, false, JavaKind.Void, new JavaKind[]{JavaKind.Object}, new ValueNode[]{stack[0]});
332 return newFrameState;
333 }
334 if (bci == BytecodeFrame.INVALID_FRAMESTATE_BCI) {
335 throw shouldNotReachHere();
336 }
337
338 if (pushedValues != null) {
339 assert pushedSlotKinds.length == pushedValues.length;
340 int stackSizeToRestore = stackSize;
341 for (int i = 0; i < pushedValues.length; i++) {
342 push(pushedSlotKinds[i], pushedValues[i]);
343 }
344 FrameState res = graph.add(new FrameState(outerFrameState, code, bci, locals, stack, stackSize, lockedObjects, Arrays.asList(monitorIds), rethrowException, duringCall));
345 stackSize = stackSizeToRestore;
346 return res;
347 } else {
348 if (bci == BytecodeFrame.AFTER_EXCEPTION_BCI) {
349 assert outerFrameState == null;
350 clearLocals();
351 }
352 return graph.add(new FrameState(outerFrameState, code, bci, locals, stack, stackSize, lockedObjects, Arrays.asList(monitorIds), rethrowException, duringCall));
353 }
354 }
355
356 public NodeSourcePosition createBytecodePosition(int bci) {
357 BytecodeParser parent = parser.getParent();
358 NodeSourcePosition position = create(bci, parent);
359 return position;
360 }
361
362 private NodeSourcePosition create(int bci, BytecodeParser parent) {
363 if (outerSourcePosition == null && parent != null) {
364 outerSourcePosition = parent.getFrameStateBuilder().createBytecodePosition(parent.bci());
365 }
366 if (bci == BytecodeFrame.AFTER_EXCEPTION_BCI && parent != null) {
367 return FrameState.toSourcePosition(outerFrameState);
368 }
369 if (bci == BytecodeFrame.INVALID_FRAMESTATE_BCI) {
370 throw shouldNotReachHere();
371 }
372 if (parser.intrinsicContext != null && (parent == null || parent.intrinsicContext != parser.intrinsicContext)) {
373 // When parsing an intrinsic put in a substitution marker showing the original method as
374 // the caller. This keeps the relationship between the method and the method
375 // substitution clear in resulting NodeSourcePosition.
376 NodeSourcePosition original = new NodeSourcePosition(outerSourcePosition, parser.intrinsicContext.getOriginalMethod(), -1);
377 return NodeSourcePosition.substitution(original, code.getMethod(), bci);
378 } else {
379 return new NodeSourcePosition(outerSourcePosition, code.getMethod(), bci);
380 }
381 }
382
383 public FrameStateBuilder copy() {
384 return new FrameStateBuilder(this);
385 }
386
387 public boolean isCompatibleWith(FrameStateBuilder other) {
388 assert code.equals(other.code) && graph == other.graph && localsSize() == other.localsSize() : "Can only compare frame states of the same method";
389 assert lockedObjects.length == monitorIds.length && other.lockedObjects.length == other.monitorIds.length : "mismatch between lockedObjects and monitorIds";
390
391 if (rethrowException != other.rethrowException) {
392 return false;
393 }
394
395 if (stackSize() != other.stackSize()) {
396 return false;
397 }
398 for (int i = 0; i < stackSize(); i++) {
399 ValueNode x = stack[i];
400 ValueNode y = other.stack[i];
401 assert x != null && y != null;
402 if (x != y && (x == TWO_SLOT_MARKER || x.isDeleted() || y == TWO_SLOT_MARKER || y.isDeleted() || x.getStackKind() != y.getStackKind())) {
403 return false;
404 }
405 }
406 if (lockedObjects.length != other.lockedObjects.length) {
407 return false;
408 }
409 for (int i = 0; i < lockedObjects.length; i++) {
410 if (GraphUtil.originalValue(lockedObjects[i]) != GraphUtil.originalValue(other.lockedObjects[i]) || monitorIds[i] != other.monitorIds[i]) {
411 throw new PermanentBailoutException("unbalanced monitors");
412 }
413 }
414 return true;
415 }
416
417 public void merge(AbstractMergeNode block, FrameStateBuilder other) {
418 GraalError.guarantee(isCompatibleWith(other), "stacks do not match on merge; bytecodes would not verify:%nexpect: %s%nactual: %s", block, other);
419
420 for (int i = 0; i < localsSize(); i++) {
421 locals[i] = merge(locals[i], other.locals[i], block);
422 }
423 for (int i = 0; i < stackSize(); i++) {
424 stack[i] = merge(stack[i], other.stack[i], block);
425 }
426 for (int i = 0; i < lockedObjects.length; i++) {
427 lockedObjects[i] = merge(lockedObjects[i], other.lockedObjects[i], block);
428 assert monitorIds[i] == other.monitorIds[i];
429 }
430
431 if (sideEffects == null) {
432 sideEffects = other.sideEffects;
433 } else {
434 if (other.sideEffects != null) {
435 sideEffects.addAll(other.sideEffects);
436 }
437 }
438 }
439
440 private ValueNode merge(ValueNode currentValue, ValueNode otherValue, AbstractMergeNode block) {
441 if (currentValue == null || currentValue.isDeleted()) {
442 return null;
443 } else if (block.isPhiAtMerge(currentValue)) {
444 if (otherValue == null || otherValue == TWO_SLOT_MARKER || otherValue.isDeleted() || currentValue.getStackKind() != otherValue.getStackKind()) {
445 // This phi must be dead anyway, add input of correct stack kind to keep the graph
446 // invariants.
447 ((PhiNode) currentValue).addInput(ConstantNode.defaultForKind(currentValue.getStackKind(), graph));
448 } else {
449 ((PhiNode) currentValue).addInput(otherValue);
450 }
451 return currentValue;
452 } else if (currentValue != otherValue) {
453 if (currentValue == TWO_SLOT_MARKER || otherValue == TWO_SLOT_MARKER) {
454 return null;
455 } else if (otherValue == null || otherValue.isDeleted() || currentValue.getStackKind() != otherValue.getStackKind()) {
456 return null;
457 }
458 assert !(block instanceof LoopBeginNode) : String.format("Phi functions for loop headers are create eagerly for changed locals and all stack slots: %s != %s", currentValue, otherValue);
459 return createValuePhi(currentValue, otherValue, block);
460 } else {
461 return currentValue;
462 }
463 }
464
465 private ValuePhiNode createValuePhi(ValueNode currentValue, ValueNode otherValue, AbstractMergeNode block) {
466 ValuePhiNode phi = graph.addWithoutUnique(new ValuePhiNode(currentValue.stamp(NodeView.DEFAULT).unrestricted(), block));
467 for (int i = 0; i < block.phiPredecessorCount(); i++) {
468 phi.addInput(currentValue);
469 }
470 phi.addInput(otherValue);
471 assert phi.valueCount() == block.phiPredecessorCount() + 1;
472 return phi;
473 }
474
475 public void inferPhiStamps(AbstractMergeNode block) {
476 for (int i = 0; i < localsSize(); i++) {
477 inferPhiStamp(block, locals[i]);
478 }
479 for (int i = 0; i < stackSize(); i++) {
480 inferPhiStamp(block, stack[i]);
481 }
482 for (int i = 0; i < lockedObjects.length; i++) {
483 inferPhiStamp(block, lockedObjects[i]);
484 }
485 }
486
487 private static void inferPhiStamp(AbstractMergeNode block, ValueNode node) {
488 if (block.isPhiAtMerge(node)) {
489 node.inferStamp();
490 }
491 }
492
493 public void insertLoopPhis(LocalLiveness liveness, int loopId, LoopBeginNode loopBegin, boolean forcePhis, boolean stampFromValueForForcedPhis) {
494 for (int i = 0; i < localsSize(); i++) {
495 boolean changedInLoop = liveness.localIsChangedInLoop(loopId, i);
496 if (forcePhis || changedInLoop) {
497 locals[i] = createLoopPhi(loopBegin, locals[i], stampFromValueForForcedPhis && !changedInLoop);
498 }
499 }
500 for (int i = 0; i < stackSize(); i++) {
501 stack[i] = createLoopPhi(loopBegin, stack[i], false);
502 }
503 for (int i = 0; i < lockedObjects.length; i++) {
504 lockedObjects[i] = createLoopPhi(loopBegin, lockedObjects[i], false);
505 }
506 }
507
508 public void insertLoopProxies(LoopExitNode loopExit, FrameStateBuilder loopEntryState) {
509 DebugContext debug = graph.getDebug();
510 for (int i = 0; i < localsSize(); i++) {
511 ValueNode value = locals[i];
512 if (value != null && value != TWO_SLOT_MARKER && (!loopEntryState.contains(value) || loopExit.loopBegin().isPhiAtMerge(value))) {
513 debug.log(" inserting proxy for %s", value);
514 locals[i] = ProxyNode.forValue(value, loopExit, graph);
515 }
516 }
517 for (int i = 0; i < stackSize(); i++) {
518 ValueNode value = stack[i];
519 if (value != null && value != TWO_SLOT_MARKER && (!loopEntryState.contains(value) || loopExit.loopBegin().isPhiAtMerge(value))) {
520 debug.log(" inserting proxy for %s", value);
521 stack[i] = ProxyNode.forValue(value, loopExit, graph);
522 }
523 }
524 for (int i = 0; i < lockedObjects.length; i++) {
525 ValueNode value = lockedObjects[i];
526 if (value != null && (!loopEntryState.contains(value) || loopExit.loopBegin().isPhiAtMerge(value))) {
527 debug.log(" inserting proxy for %s", value);
528 lockedObjects[i] = ProxyNode.forValue(value, loopExit, graph);
529 }
530 }
531 }
532
533 public void insertProxies(Function<ValueNode, ValueNode> proxyFunction) {
534 DebugContext debug = graph.getDebug();
535 for (int i = 0; i < localsSize(); i++) {
536 ValueNode value = locals[i];
537 if (value != null && value != TWO_SLOT_MARKER) {
538 debug.log(" inserting proxy for %s", value);
539 locals[i] = proxyFunction.apply(value);
540 }
541 }
542 for (int i = 0; i < stackSize(); i++) {
543 ValueNode value = stack[i];
544 if (value != null && value != TWO_SLOT_MARKER) {
545 debug.log(" inserting proxy for %s", value);
546 stack[i] = proxyFunction.apply(value);
547 }
548 }
549 for (int i = 0; i < lockedObjects.length; i++) {
550 ValueNode value = lockedObjects[i];
551 if (value != null) {
552 debug.log(" inserting proxy for %s", value);
553 lockedObjects[i] = proxyFunction.apply(value);
554 }
555 }
556 }
557
558 private ValueNode createLoopPhi(AbstractMergeNode block, ValueNode value, boolean stampFromValue) {
559 if (value == null || value == TWO_SLOT_MARKER) {
560 return value;
561 }
562 assert !block.isPhiAtMerge(value) : "phi function for this block already created";
563
564 ValuePhiNode phi = graph.addWithoutUnique(new ValuePhiNode(stampFromValue ? value.stamp(NodeView.DEFAULT) : value.stamp(NodeView.DEFAULT).unrestricted(), block));
565 phi.addInput(value);
566 return phi;
567 }
568
569 /**
570 * Adds a locked monitor to this frame state.
571 *
572 * @param object the object whose monitor will be locked.
573 */
574 public void pushLock(ValueNode object, MonitorIdNode monitorId) {
575 assert object.isAlive() && object.getStackKind() == JavaKind.Object : "unexpected value: " + object;
576 lockedObjects = Arrays.copyOf(lockedObjects, lockedObjects.length + 1);
577 monitorIds = Arrays.copyOf(monitorIds, monitorIds.length + 1);
578 lockedObjects[lockedObjects.length - 1] = object;
579 monitorIds[monitorIds.length - 1] = monitorId;
580 assert lockedObjects.length == monitorIds.length;
581 }
582
583 /**
584 * Removes a locked monitor from this frame state.
585 *
586 * @return the object whose monitor was removed from the locks list.
587 */
588 public ValueNode popLock() {
589 try {
590 return lockedObjects[lockedObjects.length - 1];
591 } finally {
592 lockedObjects = lockedObjects.length == 1 ? EMPTY_ARRAY : Arrays.copyOf(lockedObjects, lockedObjects.length - 1);
593 monitorIds = monitorIds.length == 1 ? EMPTY_MONITOR_ARRAY : Arrays.copyOf(monitorIds, monitorIds.length - 1);
594 assert lockedObjects.length == monitorIds.length;
595 }
596 }
597
598 public MonitorIdNode peekMonitorId() {
599 return monitorIds[monitorIds.length - 1];
600 }
601
602 /**
603 * @return the current lock depth
604 */
605 public int lockDepth(boolean includeParents) {
606 int depth = lockedObjects.length;
607 assert depth == monitorIds.length;
608 if (includeParents && parser.getParent() != null) {
609 depth += parser.getParent().frameState.lockDepth(true);
610 }
611 return depth;
612 }
613
614 public boolean contains(ValueNode value) {
615 for (int i = 0; i < localsSize(); i++) {
616 if (locals[i] == value) {
617 return true;
618 }
619 }
620 for (int i = 0; i < stackSize(); i++) {
621 if (stack[i] == value) {
622 return true;
623 }
624 }
625 assert lockedObjects.length == monitorIds.length;
626 for (int i = 0; i < lockedObjects.length; i++) {
627 if (lockedObjects[i] == value || monitorIds[i] == value) {
628 return true;
629 }
630 }
631 return false;
632 }
633
634 public void clearNonLiveLocals(BciBlock block, LocalLiveness liveness, boolean liveIn) {
635 /*
636 * Non-live local clearing is mandatory for the entry block of an OSR compilation so that
637 * dead object slots at the OSR entry are cleared. It's not sufficient to rely on PiNodes
638 * with Kind.Illegal, because the conflicting branch might not have been parsed.
639 */
640 boolean isOSREntryBlock = graph.isOSR() && getMethod().equals(graph.method()) && graph.getEntryBCI() == block.startBci;
641 if (!clearNonLiveLocals && !isOSREntryBlock) {
642 return;
643 }
644 if (liveIn) {
645 for (int i = 0; i < locals.length; i++) {
646 if (!liveness.localIsLiveIn(block, i)) {
647 assert locals[i] != TWO_SLOT_MARKER || locals[i - 1] == null : "Clearing of second slot must have cleared the first slot too";
648 locals[i] = null;
649 }
650 }
651 } else {
652 for (int i = 0; i < locals.length; i++) {
653 if (!liveness.localIsLiveOut(block, i)) {
654 assert locals[i] != TWO_SLOT_MARKER || locals[i - 1] == null : "Clearing of second slot must have cleared the first slot too";
655 locals[i] = null;
656 }
657 }
658 }
659 }
660
661 /**
662 * Clears all local variables.
663 */
664 public void clearLocals() {
665 for (int i = 0; i < locals.length; i++) {
666 locals[i] = null;
667 }
668 }
669
670 /**
671 * @see BytecodeFrame#rethrowException
672 */
673 public boolean rethrowException() {
674 return rethrowException;
675 }
676
677 /**
678 * @see BytecodeFrame#rethrowException
679 */
680 public void setRethrowException(boolean b) {
681 rethrowException = b;
682 }
683
684 /**
685 * Returns the size of the local variables.
686 *
687 * @return the size of the local variables
688 */
689 public int localsSize() {
690 return locals.length;
691 }
692
693 /**
694 * Gets the current size (height) of the stack.
695 */
696 public int stackSize() {
697 return stackSize;
698 }
699
700 private boolean verifyKind(JavaKind slotKind, ValueNode x) {
701 assert x != null;
702 assert x != TWO_SLOT_MARKER;
703 assert slotKind.getSlotCount() > 0;
704
705 if (canVerifyKind) {
706 assert x.getStackKind() == slotKind.getStackKind();
707 }
708 return true;
709 }
710
711 /**
712 * Loads the local variable at the specified index, checking that the returned value is non-null
713 * and that two-stack values are properly handled.
714 *
715 * @param i the index of the local variable to load
716 * @param slotKind the kind of the local variable from the point of view of the bytecodes
717 * @return the instruction that produced the specified local
718 */
719 public ValueNode loadLocal(int i, JavaKind slotKind) {
720 ValueNode x = locals[i];
721 assert verifyKind(slotKind, x);
722 assert slotKind.needsTwoSlots() ? locals[i + 1] == TWO_SLOT_MARKER : (i == locals.length - 1 || locals[i + 1] != TWO_SLOT_MARKER);
723 return x;
724 }
725
726 /**
727 * Stores a given local variable at the specified index. If the value occupies two slots, then
728 * the next local variable index is also overwritten.
729 *
730 * @param i the index at which to store
731 * @param slotKind the kind of the local variable from the point of view of the bytecodes
732 * @param x the instruction which produces the value for the local
733 */
734 public void storeLocal(int i, JavaKind slotKind, ValueNode x) {
735 assert verifyKind(slotKind, x);
736
737 if (locals[i] == TWO_SLOT_MARKER) {
738 /* Writing the second slot of a two-slot value invalidates the first slot. */
739 locals[i - 1] = null;
740 }
741 locals[i] = x;
742 if (slotKind.needsTwoSlots()) {
743 if (i < locals.length - 2 && locals[i + 2] == TWO_SLOT_MARKER) {
744 /*
745 * Writing a two-slot marker to an index previously occupied by a two-slot value:
746 * clear the old marker of the second slot.
747 */
748 locals[i + 2] = null;
749 }
750 /* Writing a two-slot value: mark the second slot. */
751 locals[i + 1] = TWO_SLOT_MARKER;
752 } else if (i < locals.length - 1 && locals[i + 1] == TWO_SLOT_MARKER) {
753 /*
754 * Writing a one-slot value to an index previously occupied by a two-slot value: clear
755 * the old marker of the second slot.
756 */
757 locals[i + 1] = null;
758 }
759 }
760
761 /**
762 * Pushes an instruction onto the stack with the expected type.
763 *
764 * @param slotKind the kind of the stack element from the point of view of the bytecodes
765 * @param x the instruction to push onto the stack
766 */
767 public void push(JavaKind slotKind, ValueNode x) {
768 assert verifyKind(slotKind, x);
769
770 xpush(x);
771 if (slotKind.needsTwoSlots()) {
772 xpush(TWO_SLOT_MARKER);
773 }
774 }
775
776 public void pushReturn(JavaKind slotKind, ValueNode x) {
777 if (slotKind != JavaKind.Void) {
778 push(slotKind, x);
779 }
780 }
781
782 /**
783 * Pops an instruction off the stack with the expected type.
784 *
785 * @param slotKind the kind of the stack element from the point of view of the bytecodes
786 * @return the instruction on the top of the stack
787 */
788 public ValueNode pop(JavaKind slotKind) {
789 if (slotKind.needsTwoSlots()) {
790 ValueNode s = xpop();
791 assert s == TWO_SLOT_MARKER : s;
792 }
793 ValueNode x = xpop();
794 assert verifyKind(slotKind, x);
795 return x;
796 }
797
798 private void xpush(ValueNode x) {
799 assert x != null;
800 stack[stackSize++] = x;
801 }
802
803 private ValueNode xpop() {
804 ValueNode result = stack[--stackSize];
805 assert result != null;
806 return result;
807 }
808
809 private ValueNode xpeek() {
810 ValueNode result = stack[stackSize - 1];
811 assert result != null;
812 return result;
813 }
814
815 public ValueNode peekObject() {
816 ValueNode x = xpeek();
817 assert verifyKind(JavaKind.Object, x);
818 return x;
819 }
820
821 /**
822 * Pop the specified number of slots off of this stack and return them as an array of
823 * instructions.
824 *
825 * @return an array containing the arguments off of the stack
826 */
827 public ValueNode[] popArguments(int argSize) {
828 ValueNode[] result = allocateArray(argSize);
829 for (int i = argSize - 1; i >= 0; i--) {
830 ValueNode x = xpop();
831 if (x == TWO_SLOT_MARKER) {
832 /* Ignore second slot of two-slot value. */
833 x = xpop();
834 }
835 assert x != null && x != TWO_SLOT_MARKER : x;
836 result[i] = x;
837 }
838 return result;
839 }
840
841 /**
842 * Clears all values on this stack.
843 */
844 public void clearStack() {
845 stackSize = 0;
846 }
847
848 /**
849 * Performs a raw stack operation as defined in the Java bytecode specification.
850 *
851 * @param opcode The Java bytecode.
852 */
853 public void stackOp(int opcode) {
854 switch (opcode) {
855 case POP: {
856 ValueNode w1 = xpop();
857 assert w1 != TWO_SLOT_MARKER;
858 break;
859 }
860 case POP2: {
861 xpop();
862 ValueNode w2 = xpop();
863 assert w2 != TWO_SLOT_MARKER;
864 break;
865 }
866 case DUP: {
867 ValueNode w1 = xpeek();
868 assert w1 != TWO_SLOT_MARKER;
869 xpush(w1);
870 break;
871 }
872 case DUP_X1: {
873 ValueNode w1 = xpop();
874 ValueNode w2 = xpop();
875 assert w1 != TWO_SLOT_MARKER;
876 xpush(w1);
877 xpush(w2);
878 xpush(w1);
879 break;
880 }
881 case DUP_X2: {
882 ValueNode w1 = xpop();
883 ValueNode w2 = xpop();
884 ValueNode w3 = xpop();
885 assert w1 != TWO_SLOT_MARKER;
886 xpush(w1);
887 xpush(w3);
888 xpush(w2);
889 xpush(w1);
890 break;
891 }
892 case DUP2: {
893 ValueNode w1 = xpop();
894 ValueNode w2 = xpop();
895 xpush(w2);
896 xpush(w1);
897 xpush(w2);
898 xpush(w1);
899 break;
900 }
901 case DUP2_X1: {
902 ValueNode w1 = xpop();
903 ValueNode w2 = xpop();
904 ValueNode w3 = xpop();
905 xpush(w2);
906 xpush(w1);
907 xpush(w3);
908 xpush(w2);
909 xpush(w1);
910 break;
911 }
912 case DUP2_X2: {
913 ValueNode w1 = xpop();
914 ValueNode w2 = xpop();
915 ValueNode w3 = xpop();
916 ValueNode w4 = xpop();
917 xpush(w2);
918 xpush(w1);
919 xpush(w4);
920 xpush(w3);
921 xpush(w2);
922 xpush(w1);
923 break;
924 }
925 case SWAP: {
926 ValueNode w1 = xpop();
927 ValueNode w2 = xpop();
928 assert w1 != TWO_SLOT_MARKER;
929 assert w2 != TWO_SLOT_MARKER;
930 xpush(w1);
931 xpush(w2);
932 break;
933 }
934 default:
935 throw shouldNotReachHere();
936 }
937 }
938
939 @Override
940 public int hashCode() {
941 int result = hashCode(locals, locals.length);
942 result *= 13;
943 result += hashCode(stack, this.stackSize);
944 return result;
945 }
946
947 private static int hashCode(Object[] a, int length) {
948 int result = 1;
949 for (int i = 0; i < length; ++i) {
950 Object element = a[i];
951 result = 31 * result + (element == null ? 0 : System.identityHashCode(element));
952 }
953 return result;
954 }
955
956 private static boolean equals(ValueNode[] a, ValueNode[] b, int length) {
957 for (int i = 0; i < length; ++i) {
958 if (a[i] != b[i]) {
959 return false;
960 }
961 }
962 return true;
963 }
964
965 @Override
966 public boolean equals(Object otherObject) {
967 if (otherObject instanceof FrameStateBuilder) {
968 FrameStateBuilder other = (FrameStateBuilder) otherObject;
969 if (!other.code.equals(code)) {
970 return false;
971 }
972 if (other.stackSize != stackSize) {
973 return false;
974 }
975 if (other.parser != parser) {
976 return false;
977 }
978 if (other.tool != tool) {
979 return false;
980 }
981 if (other.rethrowException != rethrowException) {
982 return false;
983 }
984 if (other.graph != graph) {
985 return false;
986 }
987 if (other.locals.length != locals.length) {
988 return false;
989 }
990 return equals(other.locals, locals, locals.length) && equals(other.stack, stack, stackSize) && equals(other.lockedObjects, lockedObjects, lockedObjects.length) &&
991 equals(other.monitorIds, monitorIds, monitorIds.length);
992 }
993 return false;
994 }
995
996 @Override
997 public boolean isAfterSideEffect() {
998 return sideEffects != null;
999 }
1000
1001 @Override
1002 public Iterable<StateSplit> sideEffects() {
1003 return sideEffects;
1004 }
1005
1006 @Override
1007 public void addSideEffect(StateSplit sideEffect) {
1008 assert sideEffect != null;
1009 assert sideEffect.hasSideEffect();
1010 if (sideEffects == null) {
1011 sideEffects = new ArrayList<>(4);
1012 }
1013 sideEffects.add(sideEffect);
1014 }
1015 }