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