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