1 /*
2  * Copyright (c) 2009, 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.nodes;
26 
27 import static jdk.vm.ci.code.BytecodeFrame.getPlaceholderBciName;
28 import static jdk.vm.ci.code.BytecodeFrame.isPlaceholderBci;
29 import static org.graalvm.compiler.nodeinfo.InputType.Association;
30 import static org.graalvm.compiler.nodeinfo.InputType.State;
31 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_0;
32 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED;
33 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_1;
34 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;
35 
36 import java.util.ArrayList;
37 import java.util.Collections;
38 import java.util.List;
39 import java.util.Map;
40 import java.util.Objects;
41 
42 import org.graalvm.compiler.api.replacements.MethodSubstitution;
43 import org.graalvm.compiler.bytecode.Bytecode;
44 import org.graalvm.compiler.bytecode.Bytecodes;
45 import org.graalvm.compiler.core.common.type.StampFactory;
46 import org.graalvm.compiler.debug.GraalError;
47 import org.graalvm.compiler.graph.IterableNodeType;
48 import org.graalvm.compiler.graph.NodeClass;
49 import org.graalvm.compiler.graph.NodeInputList;
50 import org.graalvm.compiler.graph.NodeSourcePosition;
51 import org.graalvm.compiler.graph.iterators.NodeIterable;
52 import org.graalvm.compiler.nodeinfo.InputType;
53 import org.graalvm.compiler.nodeinfo.NodeInfo;
54 import org.graalvm.compiler.nodeinfo.Verbosity;
55 import org.graalvm.compiler.nodes.java.ExceptionObjectNode;
56 import org.graalvm.compiler.nodes.java.MonitorIdNode;
57 import org.graalvm.compiler.nodes.virtual.EscapeObjectState;
58 import org.graalvm.compiler.nodes.virtual.VirtualObjectNode;
59 
60 import jdk.vm.ci.code.BytecodeFrame;
61 import jdk.vm.ci.code.CodeUtil;
62 import jdk.vm.ci.meta.JavaKind;
63 import jdk.vm.ci.meta.ResolvedJavaMethod;
64 
65 /**
66  * The {@code FrameState} class encapsulates the frame state (i.e. local variables and operand
67  * stack) at a particular point in the abstract interpretation.
68  *
69  * This can be used as debug or deoptimization information.
70  */
71 @NodeInfo(nameTemplate = "@{p#code/s}:{p#bci}", cycles = CYCLES_0, size = SIZE_1)
72 public final class FrameState extends VirtualState implements IterableNodeType {
73     public static final NodeClass<FrameState> TYPE = NodeClass.create(FrameState.class);
74 
75     /**
76      * Marker value for the second slot of values that occupy two local variable or expression stack
77      * slots. The marker value is used by the bytecode parser, but replaced with {@code null} in the
78      * {@link #values} of the {@link FrameState}.
79      */
80     public static final ValueNode TWO_SLOT_MARKER = new TwoSlotMarker();
81 
82     @NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED)
83     private static final class TwoSlotMarker extends ValueNode {
84         public static final NodeClass<TwoSlotMarker> TYPE = NodeClass.create(TwoSlotMarker.class);
85 
TwoSlotMarker()86         protected TwoSlotMarker() {
87             super(TYPE, StampFactory.forKind(JavaKind.Illegal));
88         }
89     }
90 
91     protected final int localsSize;
92 
93     protected final int stackSize;
94 
95     /**
96      * @see BytecodeFrame#rethrowException
97      */
98     protected final boolean rethrowException;
99 
100     protected final boolean duringCall;
101 
102     @OptionalInput(value = InputType.State) FrameState outerFrameState;
103 
104     /**
105      * Contains the locals, the expressions and the locked objects, in this order.
106      */
107     @OptionalInput NodeInputList<ValueNode> values;
108 
109     @Input(Association) NodeInputList<MonitorIdNode> monitorIds;
110 
111     @OptionalInput(State) NodeInputList<EscapeObjectState> virtualObjectMappings;
112 
113     /**
114      * The bytecode index to which this frame state applies.
115      */
116     public final int bci;
117 
118     /**
119      * The bytecode to which this frame state applies.
120      */
121     protected final Bytecode code;
122 
FrameState(FrameState outerFrameState, Bytecode code, int bci, int localsSize, int stackSize, int lockSize, boolean rethrowException, boolean duringCall, List<MonitorIdNode> monitorIds, List<EscapeObjectState> virtualObjectMappings)123     public FrameState(FrameState outerFrameState, Bytecode code, int bci, int localsSize, int stackSize, int lockSize, boolean rethrowException, boolean duringCall,
124                     List<MonitorIdNode> monitorIds, List<EscapeObjectState> virtualObjectMappings) {
125         super(TYPE);
126         if (code != null) {
127             /*
128              * Make sure the bci is within range of the bytecodes. If the code size is 0 then allow
129              * any value, otherwise the bci must be less than the code size. Any negative value is
130              * also allowed to represent special bytecode states.
131              */
132             int codeSize = code.getCodeSize();
133             if (codeSize != 0 && bci >= codeSize) {
134                 throw new GraalError("bci %d is out of range for %s %d bytes", bci, code.getMethod().format("%H.%n(%p)"), codeSize);
135             }
136         }
137         assert stackSize >= 0;
138         this.outerFrameState = outerFrameState;
139         assert outerFrameState == null || outerFrameState.bci >= 0;
140         this.code = code;
141         this.bci = bci;
142         this.localsSize = localsSize;
143         this.stackSize = stackSize;
144         this.values = new NodeInputList<>(this, localsSize + stackSize + lockSize);
145 
146         if (monitorIds != null && monitorIds.size() > 0) {
147             this.monitorIds = new NodeInputList<>(this, monitorIds);
148         }
149 
150         if (virtualObjectMappings != null && virtualObjectMappings.size() > 0) {
151             this.virtualObjectMappings = new NodeInputList<>(this, virtualObjectMappings);
152         }
153 
154         this.rethrowException = rethrowException;
155         this.duringCall = duringCall;
156         assert !this.rethrowException || this.stackSize == 1 : "must have exception on top of the stack";
157         assert this.locksSize() == this.monitorIdCount();
158     }
159 
FrameState(FrameState outerFrameState, Bytecode code, int bci, List<ValueNode> values, int localsSize, int stackSize, boolean rethrowException, boolean duringCall, List<MonitorIdNode> monitorIds, List<EscapeObjectState> virtualObjectMappings)160     public FrameState(FrameState outerFrameState, Bytecode code, int bci, List<ValueNode> values, int localsSize, int stackSize, boolean rethrowException, boolean duringCall,
161                     List<MonitorIdNode> monitorIds, List<EscapeObjectState> virtualObjectMappings) {
162         this(outerFrameState, code, bci, localsSize, stackSize, values.size() - localsSize - stackSize, rethrowException, duringCall, monitorIds, virtualObjectMappings);
163         for (int i = 0; i < values.size(); ++i) {
164             this.values.initialize(i, values.get(i));
165         }
166     }
167 
verifyAfterExceptionState()168     private void verifyAfterExceptionState() {
169         if (this.bci == BytecodeFrame.AFTER_EXCEPTION_BCI) {
170             assert this.outerFrameState == null;
171             for (int i = 0; i < this.localsSize; i++) {
172                 assertTrue(this.values.get(i) == null, "locals should be null in AFTER_EXCEPTION_BCI state");
173             }
174         }
175     }
176 
FrameState(int bci)177     public FrameState(int bci) {
178         this(null, null, bci, 0, 0, 0, false, false, null, Collections.<EscapeObjectState> emptyList());
179         assert bci == BytecodeFrame.BEFORE_BCI || bci == BytecodeFrame.AFTER_BCI || bci == BytecodeFrame.AFTER_EXCEPTION_BCI || bci == BytecodeFrame.UNKNOWN_BCI ||
180                         bci == BytecodeFrame.INVALID_FRAMESTATE_BCI;
181     }
182 
183     /**
184      * Creates a placeholder frame state with a single element on the stack representing a return
185      * value or thrown exception. This allows the parsing of an intrinsic to communicate the
186      * returned or thrown value in a {@link StateSplit#stateAfter() stateAfter} to the inlining call
187      * site.
188      *
189      * @param bci this must be {@link BytecodeFrame#AFTER_BCI}
190      */
FrameState(int bci, ValueNode returnValueOrExceptionObject)191     public FrameState(int bci, ValueNode returnValueOrExceptionObject) {
192         this(null, null, bci, 0, returnValueOrExceptionObject.getStackKind().getSlotCount(), 0, returnValueOrExceptionObject instanceof ExceptionObjectNode, false, null,
193                         Collections.<EscapeObjectState> emptyList());
194         assert (bci == BytecodeFrame.AFTER_BCI && !rethrowException()) || (bci == BytecodeFrame.AFTER_EXCEPTION_BCI && rethrowException());
195         this.values.initialize(0, returnValueOrExceptionObject);
196     }
197 
FrameState(FrameState outerFrameState, Bytecode code, int bci, ValueNode[] locals, ValueNode[] stack, int stackSize, ValueNode[] locks, List<MonitorIdNode> monitorIds, boolean rethrowException, boolean duringCall)198     public FrameState(FrameState outerFrameState, Bytecode code, int bci, ValueNode[] locals, ValueNode[] stack, int stackSize, ValueNode[] locks, List<MonitorIdNode> monitorIds,
199                     boolean rethrowException, boolean duringCall) {
200         this(outerFrameState, code, bci, locals.length, stackSize, locks.length, rethrowException, duringCall, monitorIds, Collections.<EscapeObjectState> emptyList());
201         createValues(locals, stack, locks);
202     }
203 
createValues(ValueNode[] locals, ValueNode[] stack, ValueNode[] locks)204     private void createValues(ValueNode[] locals, ValueNode[] stack, ValueNode[] locks) {
205         int index = 0;
206         for (int i = 0; i < locals.length; ++i) {
207             ValueNode value = locals[i];
208             if (value == TWO_SLOT_MARKER) {
209                 value = null;
210             }
211             this.values.initialize(index++, value);
212         }
213         for (int i = 0; i < stackSize; ++i) {
214             ValueNode value = stack[i];
215             if (value == TWO_SLOT_MARKER) {
216                 value = null;
217             }
218             this.values.initialize(index++, value);
219         }
220         for (int i = 0; i < locks.length; ++i) {
221             ValueNode value = locks[i];
222             assert value != TWO_SLOT_MARKER;
223             this.values.initialize(index++, value);
224         }
225     }
226 
values()227     public NodeInputList<ValueNode> values() {
228         return values;
229     }
230 
monitorIds()231     public NodeInputList<MonitorIdNode> monitorIds() {
232         return monitorIds;
233     }
234 
outerFrameState()235     public FrameState outerFrameState() {
236         return outerFrameState;
237     }
238 
setOuterFrameState(FrameState x)239     public void setOuterFrameState(FrameState x) {
240         assert x == null || (!x.isDeleted() && x.bci >= 0) : "cannot set outer frame state of:\n" + toString(this) +
241                         "\nto:\n" + toString(x) + "\nisDeleted=" + x.isDeleted();
242         updateUsages(this.outerFrameState, x);
243         this.outerFrameState = x;
244     }
245 
toSourcePosition(FrameState fs)246     public static NodeSourcePosition toSourcePosition(FrameState fs) {
247         if (fs == null) {
248             return null;
249         }
250         return new NodeSourcePosition(toSourcePosition(fs.outerFrameState()), fs.code.getMethod(), fs.bci);
251     }
252 
253     /**
254      * @see BytecodeFrame#rethrowException
255      */
rethrowException()256     public boolean rethrowException() {
257         return rethrowException;
258     }
259 
duringCall()260     public boolean duringCall() {
261         return duringCall;
262     }
263 
getCode()264     public Bytecode getCode() {
265         return code;
266     }
267 
getMethod()268     public ResolvedJavaMethod getMethod() {
269         return code == null ? null : code.getMethod();
270     }
271 
272     /**
273      * Determines if this frame state can be converted to a {@link BytecodeFrame}.
274      *
275      * Since a {@link BytecodeFrame} encodes {@link #getMethod()} and {@link #bci}, it does not
276      * preserve {@link #getCode()}. {@link #bci} is only guaranteed to be valid in terms of
277      * {@code getCode().getCode()} which may be different from {@code getMethod().getCode()} if the
278      * latter has been subject to instrumentation.
279      */
canProduceBytecodeFrame()280     public boolean canProduceBytecodeFrame() {
281         return code != null && code.getCode() == code.getMethod().getCode();
282     }
283 
addVirtualObjectMapping(EscapeObjectState virtualObject)284     public void addVirtualObjectMapping(EscapeObjectState virtualObject) {
285         if (virtualObjectMappings == null) {
286             virtualObjectMappings = new NodeInputList<>(this);
287         }
288         virtualObjectMappings.add(virtualObject);
289     }
290 
virtualObjectMappingCount()291     public int virtualObjectMappingCount() {
292         if (virtualObjectMappings == null) {
293             return 0;
294         }
295         return virtualObjectMappings.size();
296     }
297 
virtualObjectMappingAt(int i)298     public EscapeObjectState virtualObjectMappingAt(int i) {
299         return virtualObjectMappings.get(i);
300     }
301 
virtualObjectMappings()302     public NodeInputList<EscapeObjectState> virtualObjectMappings() {
303         return virtualObjectMappings;
304     }
305 
306     /**
307      * Gets a copy of this frame state.
308      */
duplicate(int newBci)309     public FrameState duplicate(int newBci) {
310         return graph().add(new FrameState(outerFrameState(), code, newBci, values, localsSize, stackSize, rethrowException, duringCall, monitorIds, virtualObjectMappings));
311     }
312 
313     /**
314      * Gets a copy of this frame state.
315      */
duplicate()316     public FrameState duplicate() {
317         return duplicate(bci);
318     }
319 
320     /**
321      * Duplicates a FrameState, along with a deep copy of all connected VirtualState (outer
322      * FrameStates, VirtualObjectStates, ...).
323      */
324     @Override
duplicateWithVirtualState()325     public FrameState duplicateWithVirtualState() {
326         FrameState newOuterFrameState = outerFrameState();
327         if (newOuterFrameState != null) {
328             newOuterFrameState = newOuterFrameState.duplicateWithVirtualState();
329         }
330         ArrayList<EscapeObjectState> newVirtualMappings = null;
331         if (virtualObjectMappings != null) {
332             newVirtualMappings = new ArrayList<>(virtualObjectMappings.size());
333             for (EscapeObjectState state : virtualObjectMappings) {
334                 newVirtualMappings.add(state.duplicateWithVirtualState());
335             }
336         }
337         return graph().add(new FrameState(newOuterFrameState, code, bci, values, localsSize, stackSize, rethrowException, duringCall, monitorIds, newVirtualMappings));
338     }
339 
340     /**
341      * Creates a copy of this frame state with one stack element of type {@code popKind} popped from
342      * the stack.
343      */
duplicateModifiedDuringCall(int newBci, JavaKind popKind)344     public FrameState duplicateModifiedDuringCall(int newBci, JavaKind popKind) {
345         return duplicateModified(graph(), newBci, rethrowException, true, popKind, null, null);
346     }
347 
duplicateModifiedBeforeCall(int newBci, JavaKind popKind, JavaKind[] pushedSlotKinds, ValueNode[] pushedValues)348     public FrameState duplicateModifiedBeforeCall(int newBci, JavaKind popKind, JavaKind[] pushedSlotKinds, ValueNode[] pushedValues) {
349         return duplicateModified(graph(), newBci, rethrowException, false, popKind, pushedSlotKinds, pushedValues);
350     }
351 
352     /**
353      * Creates a copy of this frame state with one stack element of type {@code popKind} popped from
354      * the stack and the values in {@code pushedValues} pushed on the stack. The
355      * {@code pushedValues} will be formatted correctly in slot encoding: a long or double will be
356      * followed by a null slot.
357      */
duplicateModified(int newBci, boolean newRethrowException, JavaKind popKind, JavaKind[] pushedSlotKinds, ValueNode[] pushedValues)358     public FrameState duplicateModified(int newBci, boolean newRethrowException, JavaKind popKind, JavaKind[] pushedSlotKinds, ValueNode[] pushedValues) {
359         return duplicateModified(graph(), newBci, newRethrowException, duringCall, popKind, pushedSlotKinds, pushedValues);
360     }
361 
duplicateModified(int newBci, boolean newRethrowException, boolean newDuringCall, JavaKind popKind, JavaKind[] pushedSlotKinds, ValueNode[] pushedValues)362     public FrameState duplicateModified(int newBci, boolean newRethrowException, boolean newDuringCall, JavaKind popKind, JavaKind[] pushedSlotKinds, ValueNode[] pushedValues) {
363         return duplicateModified(graph(), newBci, newRethrowException, newDuringCall, popKind, pushedSlotKinds, pushedValues);
364     }
365 
366     /**
367      * Creates a copy of this frame state with the top of stack replaced with with
368      * {@code pushedValue} which must be of type {@code popKind}.
369      */
duplicateModified(JavaKind popKind, JavaKind pushedSlotKind, ValueNode pushedValue)370     public FrameState duplicateModified(JavaKind popKind, JavaKind pushedSlotKind, ValueNode pushedValue) {
371         assert pushedValue != null && pushedValue.getStackKind() == popKind;
372         return duplicateModified(graph(), bci, rethrowException, duringCall, popKind, new JavaKind[]{pushedSlotKind}, new ValueNode[]{pushedValue});
373     }
374 
375     /**
376      * Creates a copy of this frame state with one stack element of type popKind popped from the
377      * stack and the values in pushedValues pushed on the stack. The pushedValues will be formatted
378      * correctly in slot encoding: a long or double will be followed by a null slot. The bci will be
379      * changed to newBci.
380      */
duplicateModified(StructuredGraph graph, int newBci, boolean newRethrowException, boolean newDuringCall, JavaKind popKind, JavaKind[] pushedSlotKinds, ValueNode[] pushedValues)381     public FrameState duplicateModified(StructuredGraph graph, int newBci, boolean newRethrowException, boolean newDuringCall, JavaKind popKind, JavaKind[] pushedSlotKinds, ValueNode[] pushedValues) {
382         ArrayList<ValueNode> copy;
383         if (newRethrowException && !rethrowException && popKind == JavaKind.Void) {
384             assert popKind == JavaKind.Void;
385             copy = new ArrayList<>(values.subList(0, localsSize));
386         } else {
387             copy = new ArrayList<>(values.subList(0, localsSize + stackSize));
388             if (popKind != JavaKind.Void) {
389                 if (stackAt(stackSize() - 1) == null) {
390                     copy.remove(copy.size() - 1);
391                 }
392                 ValueNode lastSlot = copy.get(copy.size() - 1);
393                 assert lastSlot.getStackKind() == popKind.getStackKind();
394                 copy.remove(copy.size() - 1);
395             }
396         }
397         if (pushedValues != null) {
398             assert pushedSlotKinds.length == pushedValues.length;
399             for (int i = 0; i < pushedValues.length; i++) {
400                 copy.add(pushedValues[i]);
401                 if (pushedSlotKinds[i].needsTwoSlots()) {
402                     copy.add(null);
403                 }
404             }
405         }
406         int newStackSize = copy.size() - localsSize;
407         copy.addAll(values.subList(localsSize + stackSize, values.size()));
408 
409         assert checkStackDepth(bci, stackSize, duringCall, rethrowException, newBci, newStackSize, newDuringCall, newRethrowException);
410         return graph.add(new FrameState(outerFrameState(), code, newBci, copy, localsSize, newStackSize, newRethrowException, newDuringCall, monitorIds, virtualObjectMappings));
411     }
412 
413     /**
414      * Perform a few sanity checks on the transformation of the stack state. The current expectation
415      * is that a stateAfter is being transformed into a stateDuring, so the stack depth may change.
416      */
checkStackDepth(int oldBci, int oldStackSize, boolean oldDuringCall, boolean oldRethrowException, int newBci, int newStackSize, boolean newDuringCall, boolean newRethrowException)417     private boolean checkStackDepth(int oldBci, int oldStackSize, boolean oldDuringCall, boolean oldRethrowException, int newBci, int newStackSize, boolean newDuringCall,
418                     boolean newRethrowException) {
419         if (BytecodeFrame.isPlaceholderBci(oldBci)) {
420             return true;
421         }
422         /*
423          * It would be nice to have a complete check of the shape of the FrameState based on a
424          * dataflow of the bytecodes but for now just check for obvious expression stack depth
425          * mistakes.
426          */
427         byte[] codes = code.getCode();
428         if (codes == null) {
429             /* Graph was constructed manually. */
430             return true;
431         }
432         byte newCode = codes[newBci];
433         if (oldBci == newBci) {
434             assert oldStackSize == newStackSize || oldDuringCall != newDuringCall || oldRethrowException != newRethrowException : "bci is unchanged, stack depth shouldn't change";
435         } else {
436             byte oldCode = codes[oldBci];
437             assert Bytecodes.lengthOf(newCode) + newBci == oldBci || Bytecodes.lengthOf(oldCode) + oldBci == newBci : "expecting roll back or forward";
438         }
439         return true;
440     }
441 
442     /**
443      * Gets the size of the local variables.
444      */
localsSize()445     public int localsSize() {
446         return localsSize;
447     }
448 
449     /**
450      * Gets the current size (height) of the stack.
451      */
stackSize()452     public int stackSize() {
453         return stackSize;
454     }
455 
456     /**
457      * Gets the number of locked monitors in this frame state.
458      */
locksSize()459     public int locksSize() {
460         return values.size() - localsSize - stackSize;
461     }
462 
463     /**
464      * Gets the number of locked monitors in this frame state and all {@linkplain #outerFrameState()
465      * outer} frame states.
466      */
nestedLockDepth()467     public int nestedLockDepth() {
468         int depth = locksSize();
469         for (FrameState outer = outerFrameState(); outer != null; outer = outer.outerFrameState()) {
470             depth += outer.locksSize();
471         }
472         return depth;
473     }
474 
475     /**
476      * Gets the value in the local variables at the specified index.
477      *
478      * @param i the index into the locals
479      * @return the instruction that produced the value for the specified local
480      */
localAt(int i)481     public ValueNode localAt(int i) {
482         assert i >= 0 && i < localsSize : "local variable index out of range: " + i;
483         return values.get(i);
484     }
485 
486     /**
487      * Get the value on the stack at the specified stack index.
488      *
489      * @param i the index into the stack, with {@code 0} being the bottom of the stack
490      * @return the instruction at the specified position in the stack
491      */
492     public ValueNode stackAt(int i) {
493         assert i >= 0 && i < stackSize;
494         return values.get(localsSize + i);
495     }
496 
497     /**
498      * Get the monitor owner at the specified index.
499      *
500      * @param i the index into the list of locked monitors.
501      * @return the lock owner at the given index.
502      */
503     public ValueNode lockAt(int i) {
504         assert i >= 0 && i < locksSize();
505         return values.get(localsSize + stackSize + i);
506     }
507 
508     /**
509      * Get the MonitorIdNode that corresponds to the locked object at the specified index.
510      */
511     public MonitorIdNode monitorIdAt(int i) {
512         assert monitorIds != null && i >= 0 && i < locksSize();
513         return monitorIds.get(i);
514     }
515 
516     public int monitorIdCount() {
517         if (monitorIds == null) {
518             return 0;
519         } else {
520             return monitorIds.size();
521         }
522     }
523 
524     public NodeIterable<FrameState> innerFrameStates() {
525         return usages().filter(FrameState.class);
526     }
527 
528     private static String toString(FrameState frameState) {
529         StringBuilder sb = new StringBuilder();
530         String nl = CodeUtil.NEW_LINE;
531         FrameState fs = frameState;
532         while (fs != null) {
533             Bytecode.appendLocation(sb, fs.getCode(), fs.bci);
534             if (BytecodeFrame.isPlaceholderBci(fs.bci)) {
535                 sb.append("//").append(getPlaceholderBciName(fs.bci));
536             }
537             sb.append(nl);
538             sb.append("locals: [");
539             for (int i = 0; i < fs.localsSize(); i++) {
540                 sb.append(i == 0 ? "" : ", ").append(fs.localAt(i) == null ? "_" : fs.localAt(i).toString(Verbosity.Id));
541             }
542             sb.append("]").append(nl).append("stack: [");
543             for (int i = 0; i < fs.stackSize(); i++) {
544                 sb.append(i == 0 ? "" : ", ").append(fs.stackAt(i) == null ? "_" : fs.stackAt(i).toString(Verbosity.Id));
545             }
546             sb.append("]").append(nl).append("locks: [");
547             for (int i = 0; i < fs.locksSize(); i++) {
548                 sb.append(i == 0 ? "" : ", ").append(fs.lockAt(i) == null ? "_" : fs.lockAt(i).toString(Verbosity.Id));
549             }
550             sb.append(']').append(nl);
551             fs = fs.outerFrameState();
552         }
553         return sb.toString();
554     }
555 
556     @Override
557     public String toString(Verbosity verbosity) {
558         if (verbosity == Verbosity.Debugger) {
559             return toString(this);
560         } else if (verbosity == Verbosity.Name) {
561             String res = super.toString(Verbosity.Name) + "@" + bci;
562             if (BytecodeFrame.isPlaceholderBci(bci)) {
563                 res += "[" + getPlaceholderBciName(bci) + "]";
564             }
565             return res;
566         } else {
567             return super.toString(verbosity);
568         }
569     }
570 
571     @Override
572     public Map<Object, Object> getDebugProperties(Map<Object, Object> map) {
573         Map<Object, Object> properties = super.getDebugProperties(map);
574         if (code != null) {
575             // properties.put("method", MetaUtil.format("%H.%n(%p):%r", method));
576             StackTraceElement ste = code.asStackTraceElement(bci);
577             if (ste.getFileName() != null && ste.getLineNumber() >= 0) {
578                 properties.put("sourceFile", ste.getFileName());
579                 properties.put("sourceLine", ste.getLineNumber());
580             }
581         }
582         if (isPlaceholderBci(bci)) {
583             properties.put("bci", getPlaceholderBciName(bci));
584         }
585         properties.put("locksSize", values.size() - stackSize - localsSize);
586         return properties;
587     }
588 
589     @Override
590     public boolean verify() {
591         if (virtualObjectMappingCount() > 0) {
592             for (EscapeObjectState state : virtualObjectMappings()) {
593                 assertTrue(state != null, "must be non-null");
594             }
595         }
596         /*
597          * The outermost FrameState should have a method that matches StructuredGraph.method except
598          * when it's a substitution or it's null.
599          */
600         assertTrue(outerFrameState != null || graph() == null || graph().method() == null || code == null || Objects.equals(graph().method(), code.getMethod()) ||
601                         graph().method().getAnnotation(MethodSubstitution.class) != null, "wrong outerFrameState %s != %s", code == null ? "null" : code.getMethod(), graph().method());
602         if (monitorIds() != null && monitorIds().size() > 0) {
603             int depth = outerLockDepth();
604             for (MonitorIdNode monitor : monitorIds()) {
605                 assertTrue(monitor.getLockDepth() == depth++, "wrong depth");
606             }
607         }
608         assertTrue(locksSize() == monitorIdCount(), "mismatch in number of locks");
609         for (ValueNode value : values) {
610             assertTrue(value == null || !value.isDeleted(), "frame state must not contain deleted nodes: %s", value);
611             assertTrue(value == null || value instanceof VirtualObjectNode || (value.getStackKind() != JavaKind.Void), "unexpected value: %s", value);
612         }
613         verifyAfterExceptionState();
614         return super.verify();
615     }
616 
617     private int outerLockDepth() {
618         int depth = 0;
619         FrameState outer = outerFrameState;
620         while (outer != null) {
621             depth += outer.monitorIdCount();
622             outer = outer.outerFrameState;
623         }
624         return depth;
625     }
626 
627     @Override
628     public void applyToNonVirtual(NodeClosure<? super ValueNode> closure) {
629         for (ValueNode value : values) {
630             if (value != null) {
631                 closure.apply(this, value);
632             }
633         }
634 
635         if (monitorIds != null) {
636             for (MonitorIdNode monitorId : monitorIds) {
637                 if (monitorId != null) {
638                     closure.apply(this, monitorId);
639                 }
640             }
641         }
642 
643         if (virtualObjectMappings != null) {
644             for (EscapeObjectState state : virtualObjectMappings) {
645                 state.applyToNonVirtual(closure);
646             }
647         }
648 
649         if (outerFrameState() != null) {
650             outerFrameState().applyToNonVirtual(closure);
651         }
652     }
653 
654     @Override
655     public void applyToVirtual(VirtualClosure closure) {
656         closure.apply(this);
657         if (virtualObjectMappings != null) {
658             for (EscapeObjectState state : virtualObjectMappings) {
659                 state.applyToVirtual(closure);
660             }
661         }
662         if (outerFrameState() != null) {
663             outerFrameState().applyToVirtual(closure);
664         }
665     }
666 
667     @Override
668     public boolean isPartOfThisState(VirtualState state) {
669         if (state == this) {
670             return true;
671         }
672         if (outerFrameState() != null && outerFrameState().isPartOfThisState(state)) {
673             return true;
674         }
675         if (virtualObjectMappings != null) {
676             for (EscapeObjectState objectState : virtualObjectMappings) {
677                 if (objectState.isPartOfThisState(state)) {
678                     return true;
679                 }
680             }
681         }
682         return false;
683     }
684 
685     public boolean isExceptionHandlingBCI() {
686         return bci == BytecodeFrame.AFTER_EXCEPTION_BCI || bci == BytecodeFrame.UNWIND_BCI;
687     }
688 }
689