001/*
002 * Copyright (c) 2009, 2014, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.nodes;
024
025import static jdk.internal.jvmci.code.BytecodeFrame.*;
026
027import java.util.*;
028
029import jdk.internal.jvmci.code.*;
030import com.oracle.graal.debug.*;
031import jdk.internal.jvmci.meta.*;
032
033import com.oracle.graal.bytecode.*;
034import com.oracle.graal.compiler.common.type.*;
035import com.oracle.graal.graph.*;
036import com.oracle.graal.graph.iterators.*;
037import com.oracle.graal.nodeinfo.*;
038import com.oracle.graal.nodes.java.*;
039import com.oracle.graal.nodes.virtual.*;
040
041/**
042 * The {@code FrameState} class encapsulates the frame state (i.e. local variables and operand
043 * stack) at a particular point in the abstract interpretation.
044 *
045 * This can be used as debug or deoptimization information.
046 */
047@NodeInfo(nameTemplate = "@{p#method/s}:{p#bci}")
048public final class FrameState extends VirtualState implements IterableNodeType {
049    public static final NodeClass<FrameState> TYPE = NodeClass.create(FrameState.class);
050
051    private static final DebugMetric METRIC_FRAMESTATE_COUNT = Debug.metric("FrameStateCount");
052
053    /**
054     * Marker value for the second slot of values that occupy two local variable or expression stack
055     * slots. The marker value is used by the bytecode parser, but replaced with {@code null} in the
056     * {@link #values} of the {@link FrameState}.
057     */
058    public static final ValueNode TWO_SLOT_MARKER = new TwoSlotMarker();
059
060    @NodeInfo
061    private static final class TwoSlotMarker extends ValueNode {
062        public static final NodeClass<TwoSlotMarker> TYPE = NodeClass.create(TwoSlotMarker.class);
063
064        protected TwoSlotMarker() {
065            super(TYPE, StampFactory.forKind(Kind.Illegal));
066        }
067    }
068
069    protected final int localsSize;
070
071    protected final int stackSize;
072
073    /**
074     * @see BytecodeFrame#rethrowException
075     */
076    protected boolean rethrowException;
077
078    protected final boolean duringCall;
079
080    @OptionalInput(value = InputType.State) FrameState outerFrameState;
081
082    /**
083     * Contains the locals, the expressions and the locked objects, in this order.
084     */
085    @OptionalInput NodeInputList<ValueNode> values;
086
087    @OptionalInput(InputType.Association) NodeInputList<MonitorIdNode> monitorIds;
088
089    @OptionalInput(InputType.State) NodeInputList<EscapeObjectState> virtualObjectMappings;
090
091    /**
092     * The bytecode index to which this frame state applies.
093     */
094    public final int bci;
095
096    protected final ResolvedJavaMethod method;
097
098    public FrameState(FrameState outerFrameState, ResolvedJavaMethod method, int bci, int localsSize, int stackSize, int lockSize, boolean rethrowException, boolean duringCall,
099                    List<MonitorIdNode> monitorIds, List<EscapeObjectState> virtualObjectMappings) {
100        super(TYPE);
101        assert stackSize >= 0;
102        this.outerFrameState = outerFrameState;
103        this.method = method;
104        this.bci = bci;
105        this.localsSize = localsSize;
106        this.stackSize = stackSize;
107        this.values = new NodeInputList<>(this, localsSize + stackSize + lockSize);
108
109        if (monitorIds != null && monitorIds.size() > 0) {
110            this.monitorIds = new NodeInputList<>(this, monitorIds);
111        }
112
113        if (virtualObjectMappings != null && virtualObjectMappings.size() > 0) {
114            this.virtualObjectMappings = new NodeInputList<>(this, virtualObjectMappings);
115        }
116
117        this.rethrowException = rethrowException;
118        this.duringCall = duringCall;
119        assert !this.rethrowException || this.stackSize == 1 : "must have exception on top of the stack";
120        assert this.locksSize() == this.monitorIdCount();
121        METRIC_FRAMESTATE_COUNT.increment();
122    }
123
124    public FrameState(FrameState outerFrameState, ResolvedJavaMethod method, int bci, List<ValueNode> values, int localsSize, int stackSize, boolean rethrowException, boolean duringCall,
125                    List<MonitorIdNode> monitorIds, List<EscapeObjectState> virtualObjectMappings) {
126        this(outerFrameState, method, bci, localsSize, stackSize, values.size() - localsSize - stackSize, rethrowException, duringCall, monitorIds, virtualObjectMappings);
127        for (int i = 0; i < values.size(); ++i) {
128            this.values.initialize(i, values.get(i));
129        }
130    }
131
132    public FrameState(int bci) {
133        this(null, null, bci, 0, 0, 0, false, false, null, Collections.<EscapeObjectState> emptyList());
134        assert bci == BytecodeFrame.BEFORE_BCI || bci == BytecodeFrame.AFTER_BCI || bci == BytecodeFrame.AFTER_EXCEPTION_BCI || bci == BytecodeFrame.UNKNOWN_BCI ||
135                        bci == BytecodeFrame.INVALID_FRAMESTATE_BCI;
136    }
137
138    /**
139     * Creates a placeholder frame state with a single element on the stack representing a return
140     * value. This allows the parsing of an intrinsic to communicate the returned value in a
141     * {@link StateSplit#stateAfter() stateAfter} to the inlining call site.
142     *
143     * @param bci this must be {@link BytecodeFrame#AFTER_BCI}
144     */
145    public FrameState(int bci, ValueNode returnValue) {
146        this(null, null, bci, 0, returnValue.getKind().getSlotCount(), 0, false, false, null, Collections.<EscapeObjectState> emptyList());
147        assert bci == BytecodeFrame.AFTER_BCI;
148        this.values.initialize(0, returnValue);
149    }
150
151    public FrameState(FrameState outerFrameState, ResolvedJavaMethod method, int bci, ValueNode[] locals, ValueNode[] stack, int stackSize, ValueNode[] locks, List<MonitorIdNode> monitorIds,
152                    boolean rethrowException, boolean duringCall) {
153        this(outerFrameState, method, bci, locals.length, stackSize, locks.length, rethrowException, duringCall, monitorIds, Collections.<EscapeObjectState> emptyList());
154        createValues(locals, stack, locks);
155    }
156
157    private void createValues(ValueNode[] locals, ValueNode[] stack, ValueNode[] locks) {
158        int index = 0;
159        for (int i = 0; i < locals.length; ++i) {
160            ValueNode value = locals[i];
161            if (value == TWO_SLOT_MARKER) {
162                value = null;
163            }
164            this.values.initialize(index++, value);
165        }
166        for (int i = 0; i < stackSize; ++i) {
167            ValueNode value = stack[i];
168            if (value == TWO_SLOT_MARKER) {
169                value = null;
170            }
171            this.values.initialize(index++, value);
172        }
173        for (int i = 0; i < locks.length; ++i) {
174            ValueNode value = locks[i];
175            assert value != TWO_SLOT_MARKER;
176            this.values.initialize(index++, value);
177        }
178    }
179
180    public NodeInputList<ValueNode> values() {
181        return values;
182    }
183
184    public NodeInputList<MonitorIdNode> monitorIds() {
185        return monitorIds;
186    }
187
188    public FrameState outerFrameState() {
189        return outerFrameState;
190    }
191
192    public void setOuterFrameState(FrameState x) {
193        updateUsages(this.outerFrameState, x);
194        this.outerFrameState = x;
195    }
196
197    public BytecodePosition toBytecodePosition() {
198        return toBytecodePosition(this);
199    }
200
201    public static BytecodePosition toBytecodePosition(FrameState fs) {
202        if (fs == null) {
203            return null;
204        }
205        return new BytecodePosition(toBytecodePosition(fs.outerFrameState()), fs.method(), fs.bci);
206    }
207
208    /**
209     * @see BytecodeFrame#rethrowException
210     */
211    public boolean rethrowException() {
212        return rethrowException;
213    }
214
215    public boolean duringCall() {
216        return duringCall;
217    }
218
219    public ResolvedJavaMethod method() {
220        return method;
221    }
222
223    public void addVirtualObjectMapping(EscapeObjectState virtualObject) {
224        if (virtualObjectMappings == null) {
225            virtualObjectMappings = new NodeInputList<>(this);
226        }
227        virtualObjectMappings.add(virtualObject);
228    }
229
230    public int virtualObjectMappingCount() {
231        if (virtualObjectMappings == null) {
232            return 0;
233        }
234        return virtualObjectMappings.size();
235    }
236
237    public EscapeObjectState virtualObjectMappingAt(int i) {
238        return virtualObjectMappings.get(i);
239    }
240
241    public NodeInputList<EscapeObjectState> virtualObjectMappings() {
242        return virtualObjectMappings;
243    }
244
245    /**
246     * Gets a copy of this frame state.
247     */
248    public FrameState duplicate(int newBci) {
249        return graph().add(new FrameState(outerFrameState(), method, newBci, values, localsSize, stackSize, rethrowException, duringCall, monitorIds, virtualObjectMappings));
250    }
251
252    /**
253     * Gets a copy of this frame state.
254     */
255    public FrameState duplicate() {
256        return duplicate(bci);
257    }
258
259    /**
260     * Duplicates a FrameState, along with a deep copy of all connected VirtualState (outer
261     * FrameStates, VirtualObjectStates, ...).
262     */
263    @Override
264    public FrameState duplicateWithVirtualState() {
265        FrameState newOuterFrameState = outerFrameState();
266        if (newOuterFrameState != null) {
267            newOuterFrameState = newOuterFrameState.duplicateWithVirtualState();
268        }
269        ArrayList<EscapeObjectState> newVirtualMappings = null;
270        if (virtualObjectMappings != null) {
271            newVirtualMappings = new ArrayList<>(virtualObjectMappings.size());
272            for (EscapeObjectState state : virtualObjectMappings) {
273                newVirtualMappings.add(state.duplicateWithVirtualState());
274            }
275        }
276        return graph().add(new FrameState(newOuterFrameState, method, bci, values, localsSize, stackSize, rethrowException, duringCall, monitorIds, newVirtualMappings));
277    }
278
279    /**
280     * Creates a copy of this frame state with one stack element of type {@code popKind} popped from
281     * the stack.
282     */
283    public FrameState duplicateModifiedDuringCall(int newBci, Kind popKind) {
284        return duplicateModified(graph(), newBci, rethrowException, true, popKind, null, null);
285    }
286
287    public FrameState duplicateModifiedBeforeCall(int newBci, Kind popKind, Kind[] pushedSlotKinds, ValueNode[] pushedValues) {
288        return duplicateModified(graph(), newBci, rethrowException, false, popKind, pushedSlotKinds, pushedValues);
289    }
290
291    /**
292     * Creates a copy of this frame state with one stack element of type {@code popKind} popped from
293     * the stack and the values in {@code pushedValues} pushed on the stack. The
294     * {@code pushedValues} will be formatted correctly in slot encoding: a long or double will be
295     * followed by a null slot.
296     */
297    public FrameState duplicateModified(int newBci, boolean newRethrowException, Kind popKind, Kind[] pushedSlotKinds, ValueNode[] pushedValues) {
298        return duplicateModified(graph(), newBci, newRethrowException, duringCall, popKind, pushedSlotKinds, pushedValues);
299    }
300
301    /**
302     * Creates a copy of this frame state with the top of stack replaced with with
303     * {@code pushedValue} which must be of type {@code popKind}.
304     */
305    public FrameState duplicateModified(Kind popKind, Kind pushedSlotKind, ValueNode pushedValue) {
306        assert pushedValue != null && pushedValue.getKind() == popKind;
307        return duplicateModified(graph(), bci, rethrowException, duringCall, popKind, new Kind[]{pushedSlotKind}, new ValueNode[]{pushedValue});
308    }
309
310    /**
311     * Creates a copy of this frame state with one stack element of type popKind popped from the
312     * stack and the values in pushedValues pushed on the stack. The pushedValues will be formatted
313     * correctly in slot encoding: a long or double will be followed by a null slot. The bci will be
314     * changed to newBci.
315     */
316    public FrameState duplicateModified(StructuredGraph graph, int newBci, boolean newRethrowException, boolean newDuringCall, Kind popKind, Kind[] pushedSlotKinds, ValueNode[] pushedValues) {
317        ArrayList<ValueNode> copy;
318        if (newRethrowException && !rethrowException && popKind == Kind.Void) {
319            assert popKind == Kind.Void;
320            copy = new ArrayList<>(values.subList(0, localsSize));
321        } else {
322            copy = new ArrayList<>(values.subList(0, localsSize + stackSize));
323            if (popKind != Kind.Void) {
324                if (stackAt(stackSize() - 1) == null) {
325                    copy.remove(copy.size() - 1);
326                }
327                ValueNode lastSlot = copy.get(copy.size() - 1);
328                assert lastSlot.getKind().getStackKind() == popKind.getStackKind();
329                copy.remove(copy.size() - 1);
330            }
331        }
332        if (pushedValues != null) {
333            assert pushedSlotKinds.length == pushedValues.length;
334            for (int i = 0; i < pushedValues.length; i++) {
335                copy.add(pushedValues[i]);
336                if (pushedSlotKinds[i].needsTwoSlots()) {
337                    copy.add(null);
338                }
339            }
340        }
341        int newStackSize = copy.size() - localsSize;
342        copy.addAll(values.subList(localsSize + stackSize, values.size()));
343
344        assert checkStackDepth(bci, stackSize, duringCall, rethrowException, newBci, newStackSize, newDuringCall, newRethrowException);
345        return graph.add(new FrameState(outerFrameState(), method, newBci, copy, localsSize, newStackSize, newRethrowException, newDuringCall, monitorIds, virtualObjectMappings));
346    }
347
348    /**
349     * Perform a few sanity checks on the transformation of the stack state. The current expectation
350     * is that a stateAfter is being transformed into a stateDuring, so the stack depth may change.
351     */
352    private boolean checkStackDepth(int oldBci, int oldStackSize, boolean oldDuringCall, boolean oldRethrowException, int newBci, int newStackSize, boolean newDuringCall, boolean newRethrowException) {
353        if (BytecodeFrame.isPlaceholderBci(oldBci)) {
354            return true;
355        }
356        /*
357         * It would be nice to have a complete check of the shape of the FrameState based on a
358         * dataflow of the bytecodes but for now just check for obvious expression stack depth
359         * mistakes.
360         */
361        byte[] codes = method.getCode();
362        if (codes == null) {
363            /* Graph was constructed manually. */
364            return true;
365        }
366        byte newCode = codes[newBci];
367        if (oldBci == newBci) {
368            assert oldStackSize == newStackSize || oldDuringCall != newDuringCall || oldRethrowException != newRethrowException : "bci is unchanged, stack depth shouldn't change";
369        } else {
370            byte oldCode = codes[oldBci];
371            assert Bytecodes.lengthOf(newCode) + newBci == oldBci || Bytecodes.lengthOf(oldCode) + oldBci == newBci : "expecting roll back or forward";
372        }
373        assert !newDuringCall || Bytecodes.isInvoke(newCode) || newStackSize + Bytecodes.stackEffectOf(newCode) >= 0 : "stack underflow at " + Bytecodes.nameOf(newCode);
374        return true;
375    }
376
377    /**
378     * Gets the size of the local variables.
379     */
380    public int localsSize() {
381        return localsSize;
382    }
383
384    /**
385     * Gets the current size (height) of the stack.
386     */
387    public int stackSize() {
388        return stackSize;
389    }
390
391    /**
392     * Gets the number of locked monitors in this frame state.
393     */
394    public int locksSize() {
395        return values.size() - localsSize - stackSize;
396    }
397
398    /**
399     * Gets the number of locked monitors in this frame state and all
400     * {@linkplain #outerFrameState() outer} frame states.
401     */
402    public int nestedLockDepth() {
403        int depth = locksSize();
404        for (FrameState outer = outerFrameState(); outer != null; outer = outer.outerFrameState()) {
405            depth += outer.locksSize();
406        }
407        return depth;
408    }
409
410    /**
411     * Gets the value in the local variables at the specified index.
412     *
413     * @param i the index into the locals
414     * @return the instruction that produced the value for the specified local
415     */
416    public ValueNode localAt(int i) {
417        assert i >= 0 && i < localsSize : "local variable index out of range: " + i;
418        return values.get(i);
419    }
420
421    /**
422     * Get the value on the stack at the specified stack index.
423     *
424     * @param i the index into the stack, with {@code 0} being the bottom of the stack
425     * @return the instruction at the specified position in the stack
426     */
427    public ValueNode stackAt(int i) {
428        assert i >= 0 && i < stackSize;
429        return values.get(localsSize + i);
430    }
431
432    /**
433     * Get the monitor owner at the specified index.
434     *
435     * @param i the index into the list of locked monitors.
436     * @return the lock owner at the given index.
437     */
438    public ValueNode lockAt(int i) {
439        assert i >= 0 && i < locksSize();
440        return values.get(localsSize + stackSize + i);
441    }
442
443    /**
444     * Get the MonitorIdNode that corresponds to the locked object at the specified index.
445     */
446    public MonitorIdNode monitorIdAt(int i) {
447        assert monitorIds != null && i >= 0 && i < locksSize();
448        return monitorIds.get(i);
449    }
450
451    public int monitorIdCount() {
452        if (monitorIds == null) {
453            return 0;
454        } else {
455            return monitorIds.size();
456        }
457    }
458
459    public NodeIterable<FrameState> innerFrameStates() {
460        return usages().filter(FrameState.class);
461    }
462
463    private static String toString(FrameState frameState) {
464        StringBuilder sb = new StringBuilder();
465        String nl = CodeUtil.NEW_LINE;
466        FrameState fs = frameState;
467        while (fs != null) {
468            MetaUtil.appendLocation(sb, fs.method, fs.bci);
469            if (BytecodeFrame.isPlaceholderBci(fs.bci)) {
470                sb.append("//").append(getPlaceholderBciName(fs.bci));
471            }
472            sb.append(nl);
473            sb.append("locals: [");
474            for (int i = 0; i < fs.localsSize(); i++) {
475                sb.append(i == 0 ? "" : ", ").append(fs.localAt(i) == null ? "_" : fs.localAt(i).toString(Verbosity.Id));
476            }
477            sb.append("]").append(nl).append("stack: [");
478            for (int i = 0; i < fs.stackSize(); i++) {
479                sb.append(i == 0 ? "" : ", ").append(fs.stackAt(i) == null ? "_" : fs.stackAt(i).toString(Verbosity.Id));
480            }
481            sb.append("]").append(nl).append("locks: [");
482            for (int i = 0; i < fs.locksSize(); i++) {
483                sb.append(i == 0 ? "" : ", ").append(fs.lockAt(i) == null ? "_" : fs.lockAt(i).toString(Verbosity.Id));
484            }
485            sb.append(']').append(nl);
486            fs = fs.outerFrameState();
487        }
488        return sb.toString();
489    }
490
491    @Override
492    public String toString(Verbosity verbosity) {
493        if (verbosity == Verbosity.Debugger) {
494            return toString(this);
495        } else if (verbosity == Verbosity.Name) {
496            String res = super.toString(Verbosity.Name) + "@" + bci;
497            if (BytecodeFrame.isPlaceholderBci(bci)) {
498                res += "[" + getPlaceholderBciName(bci) + "]";
499            }
500            return res;
501        } else {
502            return super.toString(verbosity);
503        }
504    }
505
506    @Override
507    public Map<Object, Object> getDebugProperties(Map<Object, Object> map) {
508        Map<Object, Object> properties = super.getDebugProperties(map);
509        if (method != null) {
510            // properties.put("method", MetaUtil.format("%H.%n(%p):%r", method));
511            StackTraceElement ste = method.asStackTraceElement(bci);
512            if (ste.getFileName() != null && ste.getLineNumber() >= 0) {
513                properties.put("sourceFile", ste.getFileName());
514                properties.put("sourceLine", ste.getLineNumber());
515            }
516        }
517        if (isPlaceholderBci(bci)) {
518            properties.put("bci", getPlaceholderBciName(bci));
519        }
520        properties.put("locksSize", values.size() - stackSize - localsSize);
521        return properties;
522    }
523
524    @Override
525    public boolean verify() {
526        if (virtualObjectMappingCount() > 0) {
527            for (EscapeObjectState state : virtualObjectMappings()) {
528                assertTrue(state != null, "must be non-null");
529            }
530        }
531        assertTrue(locksSize() == monitorIdCount(), "mismatch in number of locks");
532        for (ValueNode value : values) {
533            assertTrue(value == null || !value.isDeleted(), "frame state must not contain deleted nodes");
534            assertTrue(value == null || value instanceof VirtualObjectNode || (value.getKind() != Kind.Void), "unexpected value: %s", value);
535        }
536        return super.verify();
537    }
538
539    @Override
540    public void applyToNonVirtual(NodeClosure<? super ValueNode> closure) {
541        for (ValueNode value : values) {
542            if (value != null) {
543                closure.apply(this, value);
544            }
545        }
546
547        if (monitorIds != null) {
548            for (MonitorIdNode monitorId : monitorIds) {
549                if (monitorId != null) {
550                    closure.apply(this, monitorId);
551                }
552            }
553        }
554
555        if (virtualObjectMappings != null) {
556            for (EscapeObjectState state : virtualObjectMappings) {
557                state.applyToNonVirtual(closure);
558            }
559        }
560
561        if (outerFrameState() != null) {
562            outerFrameState().applyToNonVirtual(closure);
563        }
564    }
565
566    @Override
567    public void applyToVirtual(VirtualClosure closure) {
568        closure.apply(this);
569        if (virtualObjectMappings != null) {
570            for (EscapeObjectState state : virtualObjectMappings) {
571                state.applyToVirtual(closure);
572            }
573        }
574        if (outerFrameState() != null) {
575            outerFrameState().applyToVirtual(closure);
576        }
577    }
578
579    @Override
580    public boolean isPartOfThisState(VirtualState state) {
581        if (state == this) {
582            return true;
583        }
584        if (outerFrameState() != null && outerFrameState().isPartOfThisState(state)) {
585            return true;
586        }
587        if (virtualObjectMappings != null) {
588            for (EscapeObjectState objectState : virtualObjectMappings) {
589                if (objectState.isPartOfThisState(state)) {
590                    return true;
591                }
592            }
593        }
594        return false;
595    }
596}