001/*
002 * Copyright (c) 2009, 2015, 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.java;
024
025import static com.oracle.graal.bytecode.Bytecodes.*;
026import static com.oracle.graal.compiler.common.GraalOptions.*;
027import static com.oracle.graal.compiler.common.type.StampFactory.*;
028import static com.oracle.graal.graphbuilderconf.IntrinsicContext.CompilationContext.*;
029import static com.oracle.graal.java.BytecodeParser.Options.*;
030import static com.oracle.graal.nodes.type.StampTool.*;
031import static java.lang.String.*;
032import static jdk.internal.jvmci.common.JVMCIError.*;
033import static jdk.internal.jvmci.meta.DeoptimizationAction.*;
034import static jdk.internal.jvmci.meta.DeoptimizationReason.*;
035
036import java.util.*;
037
038import jdk.internal.jvmci.code.*;
039import jdk.internal.jvmci.common.*;
040import jdk.internal.jvmci.compiler.Compiler;
041import com.oracle.graal.debug.*;
042import com.oracle.graal.debug.Debug.Scope;
043
044import jdk.internal.jvmci.meta.*;
045import jdk.internal.jvmci.options.*;
046
047import com.oracle.graal.bytecode.*;
048import com.oracle.graal.compiler.common.*;
049import com.oracle.graal.compiler.common.calc.*;
050import com.oracle.graal.compiler.common.type.*;
051import com.oracle.graal.graph.Graph.Mark;
052import com.oracle.graal.graph.*;
053import com.oracle.graal.graph.Node.ValueNumberable;
054import com.oracle.graal.graph.iterators.*;
055import com.oracle.graal.graphbuilderconf.*;
056import com.oracle.graal.graphbuilderconf.InlineInvokePlugin.InlineInfo;
057import com.oracle.graal.graphbuilderconf.InvocationPlugins.InvocationPluginReceiver;
058import com.oracle.graal.java.BciBlockMapping.BciBlock;
059import com.oracle.graal.java.BciBlockMapping.ExceptionDispatchBlock;
060import com.oracle.graal.nodeinfo.*;
061import com.oracle.graal.nodes.*;
062import com.oracle.graal.nodes.CallTargetNode.InvokeKind;
063import com.oracle.graal.nodes.calc.*;
064import com.oracle.graal.nodes.extended.*;
065import com.oracle.graal.nodes.java.*;
066import com.oracle.graal.nodes.spi.*;
067import com.oracle.graal.nodes.type.*;
068import com.oracle.graal.nodes.util.*;
069import com.oracle.graal.phases.*;
070
071/**
072 * The {@code GraphBuilder} class parses the bytecode of a method and builds the IR graph.
073 */
074public class BytecodeParser implements GraphBuilderContext {
075
076    public static class Options {
077        @Option(help = "The trace level for the bytecode parser used when building a graph from bytecode", type = OptionType.Debug)//
078        public static final OptionValue<Integer> TraceBytecodeParserLevel = new OptionValue<>(0);
079
080        @Option(help = "Inlines trivial methods during bytecode parsing.", type = OptionType.Expert)//
081        public static final StableOptionValue<Boolean> InlineDuringParsing = new StableOptionValue<>(true);
082
083        @Option(help = "Inlines intrinsic methods during bytecode parsing.", type = OptionType.Expert)//
084        public static final StableOptionValue<Boolean> InlineIntrinsicsDuringParsing = new StableOptionValue<>(true);
085
086        @Option(help = "Traces inlining performed during bytecode parsing.", type = OptionType.Debug)//
087        public static final StableOptionValue<Boolean> TraceInlineDuringParsing = new StableOptionValue<>(false);
088
089        @Option(help = "Traces use of plugins during bytecode parsing.", type = OptionType.Debug)//
090        public static final StableOptionValue<Boolean> TraceParserPlugins = new StableOptionValue<>(false);
091
092        @Option(help = "Maximum depth when inlining during bytecode parsing.", type = OptionType.Debug)//
093        public static final StableOptionValue<Integer> InlineDuringParsingMaxDepth = new StableOptionValue<>(10);
094
095        @Option(help = "Dump graphs after non-trivial changes during bytecode parsing.", type = OptionType.Debug)//
096        public static final StableOptionValue<Boolean> DumpDuringGraphBuilding = new StableOptionValue<>(false);
097
098        @Option(help = "Max number of loop explosions per method.", type = OptionType.Debug)//
099        public static final OptionValue<Integer> MaximumLoopExplosionCount = new OptionValue<>(10000);
100
101        @Option(help = "Do not bail out but throw an exception on failed loop explosion.", type = OptionType.Debug)//
102        public static final OptionValue<Boolean> FailedLoopExplosionIsFatal = new OptionValue<>(false);
103
104        @Option(help = "When creating info points hide the methods of the substitutions.", type = OptionType.Debug)//
105        public static final OptionValue<Boolean> HideSubstitutionStates = new OptionValue<>(false);
106    }
107
108    /**
109     * The minimum value to which {@link Options#TraceBytecodeParserLevel} must be set to trace the
110     * bytecode instructions as they are parsed.
111     */
112    public static final int TRACELEVEL_INSTRUCTIONS = 1;
113
114    /**
115     * The minimum value to which {@link Options#TraceBytecodeParserLevel} must be set to trace the
116     * frame state before each bytecode instruction as it is parsed.
117     */
118    public static final int TRACELEVEL_STATE = 2;
119
120    /**
121     * Meters the number of actual bytecodes parsed.
122     */
123    public static final DebugMetric BytecodesParsed = Debug.metric("BytecodesParsed");
124
125    protected static final DebugMetric EXPLICIT_EXCEPTIONS = Debug.metric("ExplicitExceptions");
126
127    /**
128     * A scoped object for tasks to be performed after parsing an intrinsic such as processing
129     * {@linkplain BytecodeFrame#isPlaceholderBci(int) placeholder} frames states.
130     */
131    static class IntrinsicScope implements AutoCloseable {
132        FrameState stateBefore;
133        final Mark mark;
134        final BytecodeParser parser;
135
136        /**
137         * Creates a scope for root parsing an intrinsic.
138         *
139         * @param parser the parsing context of the intrinsic
140         */
141        public IntrinsicScope(BytecodeParser parser) {
142            this.parser = parser;
143            assert parser.parent == null;
144            assert parser.bci() == 0;
145            mark = null;
146        }
147
148        /**
149         * Creates a scope for parsing an intrinsic during graph builder inlining.
150         *
151         * @param parser the parsing context of the (non-intrinsic) method calling the intrinsic
152         * @param args the arguments to the call
153         */
154        public IntrinsicScope(BytecodeParser parser, Kind[] argSlotKinds, ValueNode[] args) {
155            assert !parser.parsingIntrinsic();
156            this.parser = parser;
157            mark = parser.getGraph().getMark();
158            stateBefore = parser.frameState.create(parser.bci(), parser.getNonIntrinsicAncestor(), false, argSlotKinds, args);
159        }
160
161        public void close() {
162            IntrinsicContext intrinsic = parser.intrinsicContext;
163            if (intrinsic != null && intrinsic.isPostParseInlined()) {
164                return;
165            }
166
167            processPlaceholderFrameStates(intrinsic);
168        }
169
170        /**
171         * Fixes up the {@linkplain BytecodeFrame#isPlaceholderBci(int) placeholder} frame states
172         * added to the graph while parsing/inlining the intrinsic for which this object exists.
173         */
174        private void processPlaceholderFrameStates(IntrinsicContext intrinsic) {
175            FrameState stateAfterReturn = null;
176            StructuredGraph graph = parser.getGraph();
177            for (Node node : graph.getNewNodes(mark)) {
178                if (node instanceof FrameState) {
179                    FrameState frameState = (FrameState) node;
180                    if (BytecodeFrame.isPlaceholderBci(frameState.bci)) {
181                        if (frameState.bci == BytecodeFrame.AFTER_BCI) {
182                            FrameStateBuilder frameStateBuilder = parser.frameState;
183                            if (frameState.stackSize() != 0) {
184                                assert frameState.usages().count() == 1;
185                                ValueNode returnVal = frameState.stackAt(0);
186                                assert returnVal == frameState.usages().first();
187
188                                /*
189                                 * Swap the top-of-stack value with the side-effect return value
190                                 * using the frame state.
191                                 */
192                                Kind returnKind = parser.currentInvokeReturnType.getKind();
193                                ValueNode tos = frameStateBuilder.pop(returnKind);
194                                assert tos.getKind() == returnVal.getKind();
195                                FrameState newFrameState = frameStateBuilder.create(parser.stream.nextBCI(), parser.getNonIntrinsicAncestor(), false, new Kind[]{returnKind},
196                                                new ValueNode[]{returnVal});
197                                frameState.replaceAndDelete(newFrameState);
198                                frameStateBuilder.push(returnKind, tos);
199                            } else {
200                                if (stateAfterReturn == null) {
201                                    if (intrinsic != null) {
202                                        assert intrinsic.isCompilationRoot();
203                                        stateAfterReturn = graph.add(new FrameState(BytecodeFrame.INVALID_FRAMESTATE_BCI));
204                                    } else {
205                                        stateAfterReturn = frameStateBuilder.create(parser.stream.nextBCI(), null);
206                                    }
207                                }
208                                frameState.replaceAndDelete(stateAfterReturn);
209                            }
210                        } else if (frameState.bci == BytecodeFrame.BEFORE_BCI) {
211                            if (stateBefore == null) {
212                                stateBefore = graph.start().stateAfter();
213                            }
214                            if (stateBefore != frameState) {
215                                frameState.replaceAndDelete(stateBefore);
216                            }
217                        } else {
218                            assert frameState.bci == BytecodeFrame.INVALID_FRAMESTATE_BCI;
219                        }
220                    }
221                }
222            }
223        }
224    }
225
226    private static class Target {
227        FixedNode fixed;
228        FrameStateBuilder state;
229
230        public Target(FixedNode fixed, FrameStateBuilder state) {
231            this.fixed = fixed;
232            this.state = state;
233        }
234    }
235
236    private static class ExplodedLoopContext {
237        private BciBlock header;
238        private int[] targetPeelIteration;
239        private int peelIteration;
240    }
241
242    @SuppressWarnings("serial")
243    public static class BytecodeParserError extends JVMCIError {
244
245        public BytecodeParserError(Throwable cause) {
246            super(cause);
247        }
248
249        public BytecodeParserError(String msg, Object... args) {
250            super(msg, args);
251        }
252    }
253
254    private final GraphBuilderPhase.Instance graphBuilderInstance;
255    protected final StructuredGraph graph;
256
257    private BciBlockMapping blockMap;
258    private LocalLiveness liveness;
259    protected final int entryBCI;
260    private final BytecodeParser parent;
261
262    private LineNumberTable lnt;
263    private int previousLineNumber;
264    private int currentLineNumber;
265
266    private ValueNode methodSynchronizedObject;
267
268    private ValueNode returnValue;
269    private FixedWithNextNode beforeReturnNode;
270    private ValueNode unwindValue;
271    private FixedWithNextNode beforeUnwindNode;
272
273    private FixedWithNextNode lastInstr;                 // the last instruction added
274    private final boolean explodeLoops;
275    private final boolean mergeExplosions;
276    private final Map<FrameStateBuilder, Integer> mergeExplosionsMap;
277    private Deque<ExplodedLoopContext> explodeLoopsContext;
278    private int nextPeelIteration = 1;
279    private boolean controlFlowSplit;
280    private final InvocationPluginReceiver invocationPluginReceiver = new InvocationPluginReceiver(this);
281
282    private FixedWithNextNode[] firstInstructionArray;
283    private FrameStateBuilder[] entryStateArray;
284    private FixedWithNextNode[][] firstInstructionMatrix;
285    private FrameStateBuilder[][] entryStateMatrix;
286
287    protected BytecodeParser(GraphBuilderPhase.Instance graphBuilderInstance, StructuredGraph graph, BytecodeParser parent, ResolvedJavaMethod method, int entryBCI, IntrinsicContext intrinsicContext) {
288        this.graphBuilderInstance = graphBuilderInstance;
289        this.graph = graph;
290        this.graphBuilderConfig = graphBuilderInstance.graphBuilderConfig;
291        this.optimisticOpts = graphBuilderInstance.optimisticOpts;
292        this.metaAccess = graphBuilderInstance.metaAccess;
293        this.stampProvider = graphBuilderInstance.stampProvider;
294        this.constantReflection = graphBuilderInstance.constantReflection;
295        this.stream = new BytecodeStream(method.getCode());
296        this.profilingInfo = (graphBuilderConfig.getUseProfiling() ? method.getProfilingInfo() : null);
297        this.constantPool = method.getConstantPool();
298        this.method = method;
299        this.intrinsicContext = intrinsicContext;
300        this.entryBCI = entryBCI;
301        this.parent = parent;
302
303        assert method.getCode() != null : "method must contain bytecodes: " + method;
304
305        if (graphBuilderConfig.insertNonSafepointDebugInfo() && !parsingIntrinsic()) {
306            lnt = method.getLineNumberTable();
307            previousLineNumber = -1;
308        }
309
310        LoopExplosionPlugin loopExplosionPlugin = graphBuilderConfig.getPlugins().getLoopExplosionPlugin();
311        if (loopExplosionPlugin != null) {
312            explodeLoops = loopExplosionPlugin.shouldExplodeLoops(method);
313            if (explodeLoops) {
314                mergeExplosions = loopExplosionPlugin.shouldMergeExplosions(method);
315                mergeExplosionsMap = new HashMap<>();
316            } else {
317                mergeExplosions = false;
318                mergeExplosionsMap = null;
319            }
320        } else {
321            explodeLoops = false;
322            mergeExplosions = false;
323            mergeExplosionsMap = null;
324        }
325    }
326
327    public ValueNode getReturnValue() {
328        return returnValue;
329    }
330
331    public FixedWithNextNode getBeforeReturnNode() {
332        return this.beforeReturnNode;
333    }
334
335    public ValueNode getUnwindValue() {
336        return unwindValue;
337    }
338
339    public FixedWithNextNode getBeforeUnwindNode() {
340        return this.beforeUnwindNode;
341    }
342
343    protected void buildRootMethod() {
344        FrameStateBuilder startFrameState = new FrameStateBuilder(this, method, graph);
345        startFrameState.initializeForMethodStart(graphBuilderConfig.eagerResolving() || intrinsicContext != null, graphBuilderConfig.getPlugins().getParameterPlugins());
346
347        try (IntrinsicScope s = intrinsicContext != null ? new IntrinsicScope(this) : null) {
348            build(graph.start(), startFrameState);
349        }
350
351        cleanupFinalGraph();
352        ComputeLoopFrequenciesClosure.compute(graph);
353    }
354
355    protected void build(FixedWithNextNode startInstruction, FrameStateBuilder startFrameState) {
356        if (PrintProfilingInformation.getValue() && profilingInfo != null) {
357            TTY.println("Profiling info for " + method.format("%H.%n(%p)"));
358            TTY.println(MetaUtil.indent(profilingInfo.toString(method, CodeUtil.NEW_LINE), "  "));
359        }
360
361        try (Indent indent = Debug.logAndIndent("build graph for %s", method)) {
362
363            // compute the block map, setup exception handlers and get the entrypoint(s)
364            BciBlockMapping newMapping = BciBlockMapping.create(stream, method);
365            this.blockMap = newMapping;
366            this.firstInstructionArray = new FixedWithNextNode[blockMap.getBlockCount()];
367            this.entryStateArray = new FrameStateBuilder[blockMap.getBlockCount()];
368
369            /*
370             * Configure the assertion checking behavior of the FrameStateBuilder. This needs to be
371             * done only when assertions are enabled, so it is wrapped in an assertion itself.
372             */
373            assert computeKindVerification(startFrameState);
374
375            try (Scope s = Debug.scope("LivenessAnalysis")) {
376                int maxLocals = method.getMaxLocals();
377                liveness = LocalLiveness.compute(stream, blockMap.getBlocks(), maxLocals, blockMap.getLoopCount());
378            } catch (Throwable e) {
379                throw Debug.handle(e);
380            }
381
382            lastInstr = startInstruction;
383            this.setCurrentFrameState(startFrameState);
384            stream.setBCI(0);
385
386            BciBlock startBlock = blockMap.getStartBlock();
387            if (this.parent == null) {
388                StartNode startNode = graph.start();
389                if (method.isSynchronized()) {
390                    assert !parsingIntrinsic();
391                    startNode.setStateAfter(createFrameState(BytecodeFrame.BEFORE_BCI, startNode));
392                } else {
393                    if (!parsingIntrinsic()) {
394                        if (graph.method() != null && graph.method().isJavaLangObjectInit()) {
395                            /*
396                             * Don't clear the receiver when Object.<init> is the compilation root.
397                             * The receiver is needed as input to RegisterFinalizerNode.
398                             */
399                        } else {
400                            frameState.clearNonLiveLocals(startBlock, liveness, true);
401                        }
402                        assert bci() == 0;
403                        startNode.setStateAfter(createFrameState(bci(), startNode));
404                    } else {
405                        if (startNode.stateAfter() == null) {
406                            FrameState stateAfterStart = createStateAfterStartOfReplacementGraph();
407                            startNode.setStateAfter(stateAfterStart);
408                        }
409                    }
410                }
411            }
412
413            if (method.isSynchronized()) {
414                // add a monitor enter to the start block
415                methodSynchronizedObject = synchronizedObject(frameState, method);
416                frameState.clearNonLiveLocals(startBlock, liveness, true);
417                assert bci() == 0;
418                genMonitorEnter(methodSynchronizedObject, bci());
419            }
420
421            finishPrepare(lastInstr);
422
423            if (graphBuilderConfig.insertNonSafepointDebugInfo() && !parsingIntrinsic()) {
424                genInfoPointNode(InfopointReason.METHOD_START, null);
425            }
426
427            currentBlock = blockMap.getStartBlock();
428            setEntryState(startBlock, 0, frameState);
429            if (startBlock.isLoopHeader && !explodeLoops) {
430                appendGoto(startBlock);
431            } else {
432                setFirstInstruction(startBlock, 0, lastInstr);
433            }
434
435            int index = 0;
436            BciBlock[] blocks = blockMap.getBlocks();
437            while (index < blocks.length) {
438                BciBlock block = blocks[index];
439                index = iterateBlock(blocks, block);
440            }
441
442            if (this.mergeExplosions) {
443                Debug.dump(graph, "Before loop detection");
444                detectLoops(startInstruction);
445            }
446
447            if (Debug.isDumpEnabled() && DumpDuringGraphBuilding.getValue() && this.beforeReturnNode != startInstruction) {
448                Debug.dump(graph, "Bytecodes parsed: " + method.getDeclaringClass().getUnqualifiedName() + "." + method.getName());
449            }
450        }
451    }
452
453    private boolean computeKindVerification(FrameStateBuilder startFrameState) {
454        if (blockMap.hasJsrBytecodes) {
455            /*
456             * The JSR return address is an int value, but stored using the astore bytecode. Instead
457             * of weakening the kind assertion checking for all methods, we disable it completely
458             * for methods that contain a JSR bytecode.
459             */
460            startFrameState.disableKindVerification();
461        }
462
463        for (NodePlugin plugin : graphBuilderConfig.getPlugins().getNodePlugins()) {
464            if (plugin.canChangeStackKind(this)) {
465                /*
466                 * We have a plugin that can change the kind of values, so no kind assertion
467                 * checking is possible.
468                 */
469                startFrameState.disableKindVerification();
470            }
471        }
472        return true;
473    }
474
475    /**
476     * Hook for subclasses to modify the graph start instruction or append new instructions to it.
477     *
478     * @param startInstr the start instruction of the graph
479     */
480    protected void finishPrepare(FixedWithNextNode startInstr) {
481    }
482
483    protected void cleanupFinalGraph() {
484        GraphUtil.normalizeLoops(graph);
485
486        // Remove dead parameters.
487        for (ParameterNode param : graph.getNodes(ParameterNode.TYPE)) {
488            if (param.hasNoUsages()) {
489                assert param.inputs().isEmpty();
490                param.safeDelete();
491            }
492        }
493
494        // Remove redundant begin nodes.
495        for (BeginNode beginNode : graph.getNodes(BeginNode.TYPE)) {
496            Node predecessor = beginNode.predecessor();
497            if (predecessor instanceof ControlSplitNode) {
498                // The begin node is necessary.
499            } else {
500                if (beginNode.hasUsages()) {
501                    reanchorGuardedNodes(beginNode);
502                }
503                GraphUtil.unlinkFixedNode(beginNode);
504                beginNode.safeDelete();
505            }
506        }
507    }
508
509    /**
510     * Removes {@link GuardedNode}s from {@code beginNode}'s usages and re-attaches them to an
511     * appropriate preceeding {@link GuardingNode}.
512     */
513    protected void reanchorGuardedNodes(BeginNode beginNode) {
514        // Find the new guarding node
515        GuardingNode guarding = null;
516        Node pred = beginNode.predecessor();
517        while (pred != null) {
518            if (pred instanceof BeginNode) {
519                if (pred.predecessor() instanceof ControlSplitNode) {
520                    guarding = (GuardingNode) pred;
521                    break;
522                }
523            } else if (pred.getNodeClass().getAllowedUsageTypes().contains(InputType.Guard)) {
524                guarding = (GuardingNode) pred;
525                break;
526            }
527            pred = pred.predecessor();
528        }
529
530        // Reset the guard for all of beginNode's usages
531        for (Node usage : beginNode.usages().snapshot()) {
532            GuardedNode guarded = (GuardedNode) usage;
533            assert guarded.getGuard() == beginNode;
534            guarded.setGuard(guarding);
535        }
536        assert beginNode.hasNoUsages() : beginNode;
537    }
538
539    /**
540     * Creates the frame state after the start node of a graph for an {@link IntrinsicContext
541     * intrinsic} that is the parse root (either for root compiling or for post-parse inlining).
542     */
543    private FrameState createStateAfterStartOfReplacementGraph() {
544        assert parent == null;
545        assert frameState.getMethod().equals(intrinsicContext.getIntrinsicMethod());
546        assert bci() == 0;
547        assert frameState.stackSize() == 0;
548        FrameState stateAfterStart;
549        if (intrinsicContext.isPostParseInlined()) {
550            stateAfterStart = graph.add(new FrameState(BytecodeFrame.BEFORE_BCI));
551        } else {
552            ResolvedJavaMethod original = intrinsicContext.getOriginalMethod();
553            ValueNode[] locals;
554            if (original.getMaxLocals() == frameState.localsSize() || original.isNative()) {
555                locals = new ValueNode[original.getMaxLocals()];
556                for (int i = 0; i < locals.length; i++) {
557                    ValueNode node = frameState.locals[i];
558                    if (node == FrameState.TWO_SLOT_MARKER) {
559                        node = null;
560                    }
561                    locals[i] = node;
562                }
563            } else {
564                locals = new ValueNode[original.getMaxLocals()];
565                int parameterCount = original.getSignature().getParameterCount(!original.isStatic());
566                for (int i = 0; i < parameterCount; i++) {
567                    ValueNode param = frameState.locals[i];
568                    if (param == FrameState.TWO_SLOT_MARKER) {
569                        param = null;
570                    }
571                    locals[i] = param;
572                    assert param == null || param instanceof ParameterNode || param.isConstant();
573                }
574            }
575            ValueNode[] stack = {};
576            int stackSize = 0;
577            ValueNode[] locks = {};
578            List<MonitorIdNode> monitorIds = Collections.emptyList();
579            stateAfterStart = graph.add(new FrameState(null, original, 0, locals, stack, stackSize, locks, monitorIds, false, false));
580        }
581        return stateAfterStart;
582    }
583
584    private void detectLoops(FixedNode startInstruction) {
585        NodeBitMap visited = graph.createNodeBitMap();
586        NodeBitMap active = graph.createNodeBitMap();
587        Deque<Node> stack = new ArrayDeque<>();
588        stack.add(startInstruction);
589        visited.mark(startInstruction);
590        while (!stack.isEmpty()) {
591            Node next = stack.peek();
592            assert next.isDeleted() || visited.isMarked(next);
593            if (next.isDeleted() || active.isMarked(next)) {
594                stack.pop();
595                if (!next.isDeleted()) {
596                    active.clear(next);
597                }
598            } else {
599                active.mark(next);
600                for (Node n : next.cfgSuccessors()) {
601                    if (active.contains(n)) {
602                        // Detected cycle.
603                        assert n instanceof MergeNode;
604                        assert next instanceof EndNode;
605                        MergeNode merge = (MergeNode) n;
606                        EndNode endNode = (EndNode) next;
607                        merge.removeEnd(endNode);
608                        FixedNode afterMerge = merge.next();
609                        if (!(afterMerge instanceof EndNode) || !(((EndNode) afterMerge).merge() instanceof LoopBeginNode)) {
610                            merge.setNext(null);
611                            LoopBeginNode newLoopBegin = this.appendLoopBegin(merge);
612                            newLoopBegin.setNext(afterMerge);
613                        }
614                        LoopBeginNode loopBegin = (LoopBeginNode) ((EndNode) merge.next()).merge();
615                        LoopEndNode loopEnd = graph.add(new LoopEndNode(loopBegin));
616                        if (parsingIntrinsic()) {
617                            loopEnd.disableSafepoint();
618                        }
619                        endNode.replaceAndDelete(loopEnd);
620                    } else if (visited.contains(n)) {
621                        // Normal merge into a branch we are already exploring.
622                    } else {
623                        visited.mark(n);
624                        stack.push(n);
625                    }
626                }
627            }
628        }
629
630        Debug.dump(graph, "After loops detected");
631        insertLoopEnds(startInstruction);
632    }
633
634    private void insertLoopEnds(FixedNode startInstruction) {
635        NodeBitMap visited = graph.createNodeBitMap();
636        Deque<Node> stack = new ArrayDeque<>();
637        stack.add(startInstruction);
638        visited.mark(startInstruction);
639        List<LoopBeginNode> loopBegins = new ArrayList<>();
640        while (!stack.isEmpty()) {
641            Node next = stack.pop();
642            assert visited.isMarked(next);
643            if (next instanceof LoopBeginNode) {
644                loopBegins.add((LoopBeginNode) next);
645            }
646            for (Node n : next.cfgSuccessors()) {
647                if (visited.contains(n)) {
648                    // Nothing to do.
649                } else {
650                    visited.mark(n);
651                    stack.push(n);
652                }
653            }
654        }
655
656        IdentityHashMap<LoopBeginNode, List<LoopBeginNode>> innerLoopsMap = new IdentityHashMap<>();
657        for (int i = loopBegins.size() - 1; i >= 0; --i) {
658            LoopBeginNode loopBegin = loopBegins.get(i);
659            insertLoopExits(loopBegin, innerLoopsMap);
660            if (DumpDuringGraphBuilding.getValue()) {
661                Debug.dump(graph, "After building loop exits for %s.", loopBegin);
662            }
663        }
664
665        // Remove degenerated merges with only one predecessor.
666        for (LoopBeginNode loopBegin : loopBegins) {
667            Node pred = loopBegin.forwardEnd().predecessor();
668            if (pred instanceof MergeNode) {
669                MergeNode.removeMergeIfDegenerated((MergeNode) pred);
670            }
671        }
672    }
673
674    private void insertLoopExits(LoopBeginNode loopBegin, IdentityHashMap<LoopBeginNode, List<LoopBeginNode>> innerLoopsMap) {
675        NodeBitMap visited = graph.createNodeBitMap();
676        Deque<Node> stack = new ArrayDeque<>();
677        for (LoopEndNode loopEnd : loopBegin.loopEnds()) {
678            stack.push(loopEnd);
679            visited.mark(loopEnd);
680        }
681
682        List<ControlSplitNode> controlSplits = new ArrayList<>();
683        List<LoopBeginNode> innerLoopBegins = new ArrayList<>();
684
685        while (!stack.isEmpty()) {
686            Node current = stack.pop();
687            if (current == loopBegin) {
688                continue;
689            }
690            for (Node pred : current.cfgPredecessors()) {
691                if (!visited.isMarked(pred)) {
692                    visited.mark(pred);
693                    if (pred instanceof LoopExitNode) {
694                        // Inner loop
695                        LoopExitNode loopExitNode = (LoopExitNode) pred;
696                        LoopBeginNode innerLoopBegin = loopExitNode.loopBegin();
697                        if (!visited.isMarked(innerLoopBegin)) {
698                            stack.push(innerLoopBegin);
699                            visited.mark(innerLoopBegin);
700                            innerLoopBegins.add(innerLoopBegin);
701                        }
702                    } else {
703                        if (pred instanceof ControlSplitNode) {
704                            ControlSplitNode controlSplitNode = (ControlSplitNode) pred;
705                            controlSplits.add(controlSplitNode);
706                        }
707                        stack.push(pred);
708                    }
709                }
710            }
711        }
712
713        for (ControlSplitNode controlSplit : controlSplits) {
714            for (Node succ : controlSplit.cfgSuccessors()) {
715                if (!visited.isMarked(succ)) {
716                    LoopExitNode loopExit = graph.add(new LoopExitNode(loopBegin));
717                    FixedNode next = ((FixedWithNextNode) succ).next();
718                    next.replaceAtPredecessor(loopExit);
719                    loopExit.setNext(next);
720                }
721            }
722        }
723
724        for (LoopBeginNode inner : innerLoopBegins) {
725            addLoopExits(loopBegin, inner, innerLoopsMap, visited);
726            if (DumpDuringGraphBuilding.getValue()) {
727                Debug.dump(graph, "After adding loop exits for %s.", inner);
728            }
729        }
730
731        innerLoopsMap.put(loopBegin, innerLoopBegins);
732    }
733
734    private void addLoopExits(LoopBeginNode loopBegin, LoopBeginNode inner, IdentityHashMap<LoopBeginNode, List<LoopBeginNode>> innerLoopsMap, NodeBitMap visited) {
735        for (LoopExitNode exit : inner.loopExits()) {
736            if (!visited.isMarked(exit)) {
737                LoopExitNode newLoopExit = graph.add(new LoopExitNode(loopBegin));
738                FixedNode next = exit.next();
739                next.replaceAtPredecessor(newLoopExit);
740                newLoopExit.setNext(next);
741            }
742        }
743
744        for (LoopBeginNode innerInner : innerLoopsMap.get(inner)) {
745            addLoopExits(loopBegin, innerInner, innerLoopsMap, visited);
746        }
747    }
748
749    private int iterateBlock(BciBlock[] blocks, BciBlock block) {
750        if (block.isLoopHeader && this.explodeLoops) {
751            return iterateExplodedLoopHeader(blocks, block);
752        } else {
753            processBlock(this, block);
754            return block.getId() + 1;
755        }
756    }
757
758    private int iterateExplodedLoopHeader(BciBlock[] blocks, BciBlock header) {
759        if (explodeLoopsContext == null) {
760            explodeLoopsContext = new ArrayDeque<>();
761        }
762
763        ExplodedLoopContext context = new ExplodedLoopContext();
764        context.header = header;
765        context.peelIteration = this.getCurrentDimension();
766        if (this.mergeExplosions) {
767            this.addToMergeCache(getEntryState(context.header, context.peelIteration), context.peelIteration);
768        }
769        explodeLoopsContext.push(context);
770        if (Debug.isDumpEnabled() && DumpDuringGraphBuilding.getValue()) {
771            Debug.dump(graph, "before loop explosion dimension " + context.peelIteration);
772        }
773        peelIteration(blocks, header, context);
774        explodeLoopsContext.pop();
775        return header.loopEnd + 1;
776    }
777
778    private void addToMergeCache(FrameStateBuilder key, int dimension) {
779        mergeExplosionsMap.put(key, dimension);
780    }
781
782    private void peelIteration(BciBlock[] blocks, BciBlock header, ExplodedLoopContext context) {
783        while (true) {
784            if (TraceParserPlugins.getValue()) {
785                traceWithContext("exploding loop, iteration %d", context.peelIteration);
786            }
787            processBlock(this, header);
788            int j = header.getId() + 1;
789            while (j <= header.loopEnd) {
790                BciBlock block = blocks[j];
791                j = iterateBlock(blocks, block);
792            }
793
794            int[] targets = context.targetPeelIteration;
795            if (targets != null) {
796                // We were reaching the backedge during explosion. Explode further.
797                for (int i = 0; i < targets.length; ++i) {
798                    context.peelIteration = targets[i];
799                    context.targetPeelIteration = null;
800                    if (Debug.isDumpEnabled() && DumpDuringGraphBuilding.getValue()) {
801                        Debug.dump(graph, "next loop explosion iteration " + context.peelIteration);
802                    }
803                    if (i < targets.length - 1) {
804                        peelIteration(blocks, header, context);
805                    }
806                }
807            } else {
808                // We did not reach the backedge. Exit.
809                break;
810            }
811        }
812    }
813
814    /**
815     * @param type the unresolved type of the constant
816     */
817    protected void handleUnresolvedLoadConstant(JavaType type) {
818        assert !graphBuilderConfig.eagerResolving();
819        append(new DeoptimizeNode(InvalidateRecompile, Unresolved));
820    }
821
822    /**
823     * @param type the unresolved type of the type check
824     * @param object the object value whose type is being checked against {@code type}
825     */
826    protected void handleUnresolvedCheckCast(JavaType type, ValueNode object) {
827        assert !graphBuilderConfig.eagerResolving();
828        append(new FixedGuardNode(graph.unique(new IsNullNode(object)), Unresolved, InvalidateRecompile));
829        frameState.push(Kind.Object, appendConstant(JavaConstant.NULL_POINTER));
830    }
831
832    /**
833     * @param type the unresolved type of the type check
834     * @param object the object value whose type is being checked against {@code type}
835     */
836    protected void handleUnresolvedInstanceOf(JavaType type, ValueNode object) {
837        assert !graphBuilderConfig.eagerResolving();
838        AbstractBeginNode successor = graph.add(new BeginNode());
839        DeoptimizeNode deopt = graph.add(new DeoptimizeNode(InvalidateRecompile, Unresolved));
840        append(new IfNode(graph.unique(new IsNullNode(object)), successor, deopt, 1));
841        lastInstr = successor;
842        frameState.push(Kind.Int, appendConstant(JavaConstant.INT_0));
843    }
844
845    /**
846     * @param type the type being instantiated
847     */
848    protected void handleUnresolvedNewInstance(JavaType type) {
849        assert !graphBuilderConfig.eagerResolving();
850        append(new DeoptimizeNode(InvalidateRecompile, Unresolved));
851    }
852
853    /**
854     * @param type the type of the array being instantiated
855     * @param length the length of the array
856     */
857    protected void handleUnresolvedNewObjectArray(JavaType type, ValueNode length) {
858        assert !graphBuilderConfig.eagerResolving();
859        append(new DeoptimizeNode(InvalidateRecompile, Unresolved));
860    }
861
862    /**
863     * @param type the type being instantiated
864     * @param dims the dimensions for the multi-array
865     */
866    protected void handleUnresolvedNewMultiArray(JavaType type, List<ValueNode> dims) {
867        assert !graphBuilderConfig.eagerResolving();
868        append(new DeoptimizeNode(InvalidateRecompile, Unresolved));
869    }
870
871    /**
872     * @param field the unresolved field
873     * @param receiver the object containing the field or {@code null} if {@code field} is static
874     */
875    protected void handleUnresolvedLoadField(JavaField field, ValueNode receiver) {
876        assert !graphBuilderConfig.eagerResolving();
877        append(new DeoptimizeNode(InvalidateRecompile, Unresolved));
878    }
879
880    /**
881     * @param field the unresolved field
882     * @param value the value being stored to the field
883     * @param receiver the object containing the field or {@code null} if {@code field} is static
884     */
885    protected void handleUnresolvedStoreField(JavaField field, ValueNode value, ValueNode receiver) {
886        assert !graphBuilderConfig.eagerResolving();
887        append(new DeoptimizeNode(InvalidateRecompile, Unresolved));
888    }
889
890    /**
891     * @param type
892     */
893    protected void handleUnresolvedExceptionType(JavaType type) {
894        assert !graphBuilderConfig.eagerResolving();
895        append(new DeoptimizeNode(InvalidateRecompile, Unresolved));
896    }
897
898    /**
899     * @param javaMethod
900     * @param invokeKind
901     */
902    protected void handleUnresolvedInvoke(JavaMethod javaMethod, InvokeKind invokeKind) {
903        assert !graphBuilderConfig.eagerResolving();
904        append(new DeoptimizeNode(InvalidateRecompile, Unresolved));
905    }
906
907    private DispatchBeginNode handleException(ValueNode exceptionObject, int bci) {
908        assert bci == BytecodeFrame.BEFORE_BCI || bci == bci() : "invalid bci";
909        Debug.log("Creating exception dispatch edges at %d, exception object=%s, exception seen=%s", bci, exceptionObject, (profilingInfo == null ? "" : profilingInfo.getExceptionSeen(bci)));
910
911        BciBlock dispatchBlock = currentBlock.exceptionDispatchBlock();
912        /*
913         * The exception dispatch block is always for the last bytecode of a block, so if we are not
914         * at the endBci yet, there is no exception handler for this bci and we can unwind
915         * immediately.
916         */
917        if (bci != currentBlock.endBci || dispatchBlock == null) {
918            dispatchBlock = blockMap.getUnwindBlock();
919        }
920
921        FrameStateBuilder dispatchState = frameState.copy();
922        dispatchState.clearStack();
923
924        DispatchBeginNode dispatchBegin;
925        if (exceptionObject == null) {
926            dispatchBegin = graph.add(new ExceptionObjectNode(metaAccess));
927            dispatchState.push(Kind.Object, dispatchBegin);
928            dispatchState.setRethrowException(true);
929            dispatchBegin.setStateAfter(dispatchState.create(bci, dispatchBegin));
930        } else {
931            dispatchBegin = graph.add(new DispatchBeginNode());
932            dispatchState.push(Kind.Object, exceptionObject);
933            dispatchState.setRethrowException(true);
934            dispatchBegin.setStateAfter(dispatchState.create(bci, dispatchBegin));
935        }
936        this.controlFlowSplit = true;
937        FixedNode target = createTarget(dispatchBlock, dispatchState);
938        FixedWithNextNode finishedDispatch = finishInstruction(dispatchBegin, dispatchState);
939        finishedDispatch.setNext(target);
940        return dispatchBegin;
941    }
942
943    protected ValueNode genLoadIndexed(ValueNode array, ValueNode index, Kind kind) {
944        return LoadIndexedNode.create(array, index, kind, metaAccess, constantReflection);
945    }
946
947    protected void genStoreIndexed(ValueNode array, ValueNode index, Kind kind, ValueNode value) {
948        add(new StoreIndexedNode(array, index, kind, value));
949    }
950
951    protected ValueNode genIntegerAdd(ValueNode x, ValueNode y) {
952        return AddNode.create(x, y);
953    }
954
955    protected ValueNode genIntegerSub(ValueNode x, ValueNode y) {
956        return SubNode.create(x, y);
957    }
958
959    protected ValueNode genIntegerMul(ValueNode x, ValueNode y) {
960        return MulNode.create(x, y);
961    }
962
963    protected ValueNode genFloatAdd(ValueNode x, ValueNode y) {
964        return AddNode.create(x, y);
965    }
966
967    protected ValueNode genFloatSub(ValueNode x, ValueNode y) {
968        return SubNode.create(x, y);
969    }
970
971    protected ValueNode genFloatMul(ValueNode x, ValueNode y) {
972        return MulNode.create(x, y);
973    }
974
975    protected ValueNode genFloatDiv(ValueNode x, ValueNode y) {
976        return DivNode.create(x, y);
977    }
978
979    protected ValueNode genFloatRem(ValueNode x, ValueNode y) {
980        return new RemNode(x, y);
981    }
982
983    protected ValueNode genIntegerDiv(ValueNode x, ValueNode y) {
984        return new IntegerDivNode(x, y);
985    }
986
987    protected ValueNode genIntegerRem(ValueNode x, ValueNode y) {
988        return new IntegerRemNode(x, y);
989    }
990
991    protected ValueNode genNegateOp(ValueNode x) {
992        return (new NegateNode(x));
993    }
994
995    protected ValueNode genLeftShift(ValueNode x, ValueNode y) {
996        return new LeftShiftNode(x, y);
997    }
998
999    protected ValueNode genRightShift(ValueNode x, ValueNode y) {
1000        return new RightShiftNode(x, y);
1001    }
1002
1003    protected ValueNode genUnsignedRightShift(ValueNode x, ValueNode y) {
1004        return new UnsignedRightShiftNode(x, y);
1005    }
1006
1007    protected ValueNode genAnd(ValueNode x, ValueNode y) {
1008        return AndNode.create(x, y);
1009    }
1010
1011    protected ValueNode genOr(ValueNode x, ValueNode y) {
1012        return OrNode.create(x, y);
1013    }
1014
1015    protected ValueNode genXor(ValueNode x, ValueNode y) {
1016        return XorNode.create(x, y);
1017    }
1018
1019    protected ValueNode genNormalizeCompare(ValueNode x, ValueNode y, boolean isUnorderedLess) {
1020        return NormalizeCompareNode.create(x, y, isUnorderedLess, constantReflection);
1021    }
1022
1023    protected ValueNode genFloatConvert(FloatConvert op, ValueNode input) {
1024        return FloatConvertNode.create(op, input);
1025    }
1026
1027    protected ValueNode genNarrow(ValueNode input, int bitCount) {
1028        return NarrowNode.create(input, bitCount);
1029    }
1030
1031    protected ValueNode genSignExtend(ValueNode input, int bitCount) {
1032        return SignExtendNode.create(input, bitCount);
1033    }
1034
1035    protected ValueNode genZeroExtend(ValueNode input, int bitCount) {
1036        return ZeroExtendNode.create(input, bitCount);
1037    }
1038
1039    protected void genGoto() {
1040        appendGoto(currentBlock.getSuccessor(0));
1041        assert currentBlock.numNormalSuccessors() == 1;
1042    }
1043
1044    protected LogicNode genObjectEquals(ValueNode x, ValueNode y) {
1045        return ObjectEqualsNode.create(x, y, constantReflection);
1046    }
1047
1048    protected LogicNode genIntegerEquals(ValueNode x, ValueNode y) {
1049        return IntegerEqualsNode.create(x, y, constantReflection);
1050    }
1051
1052    protected LogicNode genIntegerLessThan(ValueNode x, ValueNode y) {
1053        return IntegerLessThanNode.create(x, y, constantReflection);
1054    }
1055
1056    protected ValueNode genUnique(ValueNode x) {
1057        return (ValueNode) graph.unique((Node & ValueNumberable) x);
1058    }
1059
1060    protected ValueNode genIfNode(LogicNode condition, FixedNode falseSuccessor, FixedNode trueSuccessor, double d) {
1061        return new IfNode(condition, falseSuccessor, trueSuccessor, d);
1062    }
1063
1064    protected void genThrow() {
1065        genInfoPointNode(InfopointReason.LINE_NUMBER, null);
1066
1067        ValueNode exception = frameState.pop(Kind.Object);
1068        FixedGuardNode nullCheck = append(new FixedGuardNode(graph.unique(new IsNullNode(exception)), NullCheckException, InvalidateReprofile, true));
1069        PiNode nonNullException = graph.unique(new PiNode(exception, exception.stamp().join(objectNonNull())));
1070        nonNullException.setGuard(nullCheck);
1071        lastInstr.setNext(handleException(nonNullException, bci()));
1072    }
1073
1074    protected ValueNode createCheckCast(ResolvedJavaType type, ValueNode object, JavaTypeProfile profileForTypeCheck, boolean forStoreCheck) {
1075        return CheckCastNode.create(type, object, profileForTypeCheck, forStoreCheck, graph.getAssumptions());
1076    }
1077
1078    protected ValueNode createInstanceOf(ResolvedJavaType type, ValueNode object, JavaTypeProfile profileForTypeCheck) {
1079        return InstanceOfNode.create(type, object, profileForTypeCheck);
1080    }
1081
1082    protected ValueNode genConditional(ValueNode x) {
1083        return new ConditionalNode((LogicNode) x);
1084    }
1085
1086    protected NewInstanceNode createNewInstance(ResolvedJavaType type, boolean fillContents) {
1087        return new NewInstanceNode(type, fillContents);
1088    }
1089
1090    protected NewArrayNode createNewArray(ResolvedJavaType elementType, ValueNode length, boolean fillContents) {
1091        return new NewArrayNode(elementType, length, fillContents);
1092    }
1093
1094    protected NewMultiArrayNode createNewMultiArray(ResolvedJavaType type, List<ValueNode> dimensions) {
1095        return new NewMultiArrayNode(type, dimensions.toArray(new ValueNode[0]));
1096    }
1097
1098    protected ValueNode genLoadField(ValueNode receiver, ResolvedJavaField field) {
1099        return new LoadFieldNode(receiver, field);
1100    }
1101
1102    protected ValueNode emitExplicitNullCheck(ValueNode receiver) {
1103        if (StampTool.isPointerNonNull(receiver.stamp())) {
1104            return receiver;
1105        }
1106        BytecodeExceptionNode exception = graph.add(new BytecodeExceptionNode(metaAccess, NullPointerException.class));
1107        AbstractBeginNode falseSucc = graph.add(new BeginNode());
1108        PiNode nonNullReceiver = graph.unique(new PiNode(receiver, receiver.stamp().join(objectNonNull())));
1109        nonNullReceiver.setGuard(falseSucc);
1110        append(new IfNode(graph.unique(new IsNullNode(receiver)), exception, falseSucc, 0.01));
1111        lastInstr = falseSucc;
1112
1113        exception.setStateAfter(createFrameState(bci(), exception));
1114        exception.setNext(handleException(exception, bci()));
1115        return nonNullReceiver;
1116    }
1117
1118    protected void emitExplicitBoundsCheck(ValueNode index, ValueNode length) {
1119        AbstractBeginNode trueSucc = graph.add(new BeginNode());
1120        BytecodeExceptionNode exception = graph.add(new BytecodeExceptionNode(metaAccess, ArrayIndexOutOfBoundsException.class, index));
1121        append(new IfNode(graph.unique(IntegerBelowNode.create(index, length, constantReflection)), trueSucc, exception, 0.99));
1122        lastInstr = trueSucc;
1123
1124        exception.setStateAfter(createFrameState(bci(), exception));
1125        exception.setNext(handleException(exception, bci()));
1126    }
1127
1128    protected ValueNode genArrayLength(ValueNode x) {
1129        return ArrayLengthNode.create(x, constantReflection);
1130    }
1131
1132    protected void genStoreField(ValueNode receiver, ResolvedJavaField field, ValueNode value) {
1133        StoreFieldNode storeFieldNode = new StoreFieldNode(receiver, field, value);
1134        append(storeFieldNode);
1135        storeFieldNode.setStateAfter(this.createFrameState(stream.nextBCI(), storeFieldNode));
1136    }
1137
1138    /**
1139     * Ensure that concrete classes are at least linked before generating an invoke. Interfaces may
1140     * never be linked so simply return true for them.
1141     *
1142     * @param target
1143     * @return true if the declared holder is an interface or is linked
1144     */
1145    private static boolean callTargetIsResolved(JavaMethod target) {
1146        if (target instanceof ResolvedJavaMethod) {
1147            ResolvedJavaMethod resolvedTarget = (ResolvedJavaMethod) target;
1148            ResolvedJavaType resolvedType = resolvedTarget.getDeclaringClass();
1149            return resolvedType.isInterface() || resolvedType.isLinked();
1150        }
1151        return false;
1152    }
1153
1154    protected void genInvokeStatic(JavaMethod target) {
1155        if (callTargetIsResolved(target)) {
1156            ResolvedJavaMethod resolvedTarget = (ResolvedJavaMethod) target;
1157            ResolvedJavaType holder = resolvedTarget.getDeclaringClass();
1158            if (!holder.isInitialized() && ResolveClassBeforeStaticInvoke.getValue()) {
1159                handleUnresolvedInvoke(target, InvokeKind.Static);
1160            } else {
1161                ValueNode[] args = frameState.popArguments(resolvedTarget.getSignature().getParameterCount(false));
1162                appendInvoke(InvokeKind.Static, resolvedTarget, args);
1163            }
1164        } else {
1165            handleUnresolvedInvoke(target, InvokeKind.Static);
1166        }
1167    }
1168
1169    protected void genInvokeInterface(JavaMethod target) {
1170        if (callTargetIsResolved(target)) {
1171            ValueNode[] args = frameState.popArguments(target.getSignature().getParameterCount(true));
1172            appendInvoke(InvokeKind.Interface, (ResolvedJavaMethod) target, args);
1173        } else {
1174            handleUnresolvedInvoke(target, InvokeKind.Interface);
1175        }
1176    }
1177
1178    protected void genInvokeDynamic(JavaMethod target) {
1179        if (target instanceof ResolvedJavaMethod) {
1180            JavaConstant appendix = constantPool.lookupAppendix(stream.readCPI4(), Bytecodes.INVOKEDYNAMIC);
1181            if (appendix != null) {
1182                frameState.push(Kind.Object, ConstantNode.forConstant(appendix, metaAccess, graph));
1183            }
1184            ValueNode[] args = frameState.popArguments(target.getSignature().getParameterCount(false));
1185            appendInvoke(InvokeKind.Static, (ResolvedJavaMethod) target, args);
1186        } else {
1187            handleUnresolvedInvoke(target, InvokeKind.Static);
1188        }
1189    }
1190
1191    protected void genInvokeVirtual(JavaMethod target) {
1192        if (callTargetIsResolved(target)) {
1193            /*
1194             * Special handling for runtimes that rewrite an invocation of MethodHandle.invoke(...)
1195             * or MethodHandle.invokeExact(...) to a static adapter. HotSpot does this - see
1196             * https://wikis.oracle.com/display/HotSpotInternals/Method+handles +and+invokedynamic
1197             */
1198            boolean hasReceiver = !((ResolvedJavaMethod) target).isStatic();
1199            JavaConstant appendix = constantPool.lookupAppendix(stream.readCPI(), Bytecodes.INVOKEVIRTUAL);
1200            if (appendix != null) {
1201                frameState.push(Kind.Object, ConstantNode.forConstant(appendix, metaAccess, graph));
1202            }
1203            ValueNode[] args = frameState.popArguments(target.getSignature().getParameterCount(hasReceiver));
1204            if (hasReceiver) {
1205                appendInvoke(InvokeKind.Virtual, (ResolvedJavaMethod) target, args);
1206            } else {
1207                appendInvoke(InvokeKind.Static, (ResolvedJavaMethod) target, args);
1208            }
1209        } else {
1210            handleUnresolvedInvoke(target, InvokeKind.Virtual);
1211        }
1212
1213    }
1214
1215    protected void genInvokeSpecial(JavaMethod target) {
1216        if (callTargetIsResolved(target)) {
1217            assert target != null;
1218            assert target.getSignature() != null;
1219            ValueNode[] args = frameState.popArguments(target.getSignature().getParameterCount(true));
1220            appendInvoke(InvokeKind.Special, (ResolvedJavaMethod) target, args);
1221        } else {
1222            handleUnresolvedInvoke(target, InvokeKind.Special);
1223        }
1224    }
1225
1226    private InvokeKind currentInvokeKind;
1227    private JavaType currentInvokeReturnType;
1228    protected FrameStateBuilder frameState;
1229    protected BciBlock currentBlock;
1230    protected final BytecodeStream stream;
1231    protected final GraphBuilderConfiguration graphBuilderConfig;
1232    protected final ResolvedJavaMethod method;
1233    protected final ProfilingInfo profilingInfo;
1234    protected final OptimisticOptimizations optimisticOpts;
1235    protected final ConstantPool constantPool;
1236    protected final MetaAccessProvider metaAccess;
1237    private final ConstantReflectionProvider constantReflection;
1238    private final StampProvider stampProvider;
1239    protected final IntrinsicContext intrinsicContext;
1240
1241    public InvokeKind getInvokeKind() {
1242        return currentInvokeKind;
1243    }
1244
1245    public JavaType getInvokeReturnType() {
1246        return currentInvokeReturnType;
1247    }
1248
1249    private boolean forceInliningEverything;
1250
1251    public void handleReplacedInvoke(InvokeKind invokeKind, ResolvedJavaMethod targetMethod, ValueNode[] args, boolean inlineEverything) {
1252        boolean previous = forceInliningEverything;
1253        forceInliningEverything = previous || inlineEverything;
1254        try {
1255            appendInvoke(invokeKind, targetMethod, args);
1256        } finally {
1257            forceInliningEverything = previous;
1258        }
1259    }
1260
1261    private void appendInvoke(InvokeKind initialInvokeKind, ResolvedJavaMethod initialTargetMethod, ValueNode[] args) {
1262        ResolvedJavaMethod targetMethod = initialTargetMethod;
1263        InvokeKind invokeKind = initialInvokeKind;
1264        if (initialInvokeKind.isIndirect()) {
1265            ResolvedJavaType contextType = this.frameState.getMethod().getDeclaringClass();
1266            ResolvedJavaMethod specialCallTarget = MethodCallTargetNode.findSpecialCallTarget(initialInvokeKind, args[0], initialTargetMethod, contextType);
1267            if (specialCallTarget != null) {
1268                invokeKind = InvokeKind.Special;
1269                targetMethod = specialCallTarget;
1270            }
1271        }
1272
1273        Kind resultType = targetMethod.getSignature().getReturnKind();
1274        if (DeoptALot.getValue()) {
1275            append(new DeoptimizeNode(DeoptimizationAction.None, RuntimeConstraint));
1276            frameState.pushReturn(resultType, ConstantNode.defaultForKind(resultType, graph));
1277            return;
1278        }
1279
1280        JavaType returnType = targetMethod.getSignature().getReturnType(method.getDeclaringClass());
1281        if (graphBuilderConfig.eagerResolving() || parsingIntrinsic()) {
1282            returnType = returnType.resolve(targetMethod.getDeclaringClass());
1283        }
1284        if (invokeKind.hasReceiver()) {
1285            args[0] = emitExplicitExceptions(args[0], null);
1286
1287            if (args[0].isNullConstant()) {
1288                append(new DeoptimizeNode(InvalidateRecompile, NullCheckException));
1289                return;
1290            }
1291        }
1292
1293        try {
1294            currentInvokeReturnType = returnType;
1295            currentInvokeKind = invokeKind;
1296            if (tryNodePluginForInvocation(args, targetMethod)) {
1297                if (TraceParserPlugins.getValue()) {
1298                    traceWithContext("used node plugin for %s", targetMethod.format("%h.%n(%p)"));
1299                }
1300                return;
1301            }
1302
1303            if (invokeKind.isDirect()) {
1304                if (tryInvocationPlugin(args, targetMethod, resultType)) {
1305                    if (TraceParserPlugins.getValue()) {
1306                        traceWithContext("used invocation plugin for %s", targetMethod.format("%h.%n(%p)"));
1307                    }
1308                    return;
1309                }
1310
1311                if (tryInline(args, targetMethod, returnType)) {
1312                    return;
1313                }
1314            }
1315        } finally {
1316            currentInvokeReturnType = null;
1317            currentInvokeKind = null;
1318        }
1319
1320        JavaTypeProfile profile = null;
1321        if (invokeKind.isIndirect() && profilingInfo != null && this.optimisticOpts.useTypeCheckHints()) {
1322            profile = profilingInfo.getTypeProfile(bci());
1323        }
1324        MethodCallTargetNode callTarget = graph.add(createMethodCallTarget(invokeKind, targetMethod, args, returnType, profile));
1325
1326        // be conservative if information was not recorded (could result in endless
1327        // recompiles otherwise)
1328        Invoke invoke;
1329        if (lastInlineInfo == InlineInfo.DO_NOT_INLINE_NO_EXCEPTION || graphBuilderConfig.omitAllExceptionEdges() ||
1330                        (!StressInvokeWithExceptionNode.getValue() && optimisticOpts.useExceptionProbability() && profilingInfo != null && profilingInfo.getExceptionSeen(bci()) == TriState.FALSE)) {
1331            invoke = createInvoke(callTarget, resultType);
1332        } else {
1333            invoke = createInvokeWithException(callTarget, resultType);
1334            AbstractBeginNode beginNode = graph.add(new KillingBeginNode(LocationIdentity.any()));
1335            invoke.setNext(beginNode);
1336            lastInstr = beginNode;
1337        }
1338
1339        for (InlineInvokePlugin plugin : graphBuilderConfig.getPlugins().getInlineInvokePlugins()) {
1340            plugin.notifyNotInlined(this, targetMethod, invoke);
1341        }
1342    }
1343
1344    /**
1345     * Contains all the assertion checking logic around the application of an
1346     * {@link InvocationPlugin}. This class is only loaded when assertions are enabled.
1347     */
1348    class InvocationPluginAssertions {
1349        final InvocationPlugin plugin;
1350        final ValueNode[] args;
1351        final ResolvedJavaMethod targetMethod;
1352        final Kind resultType;
1353        final int beforeStackSize;
1354        final boolean needsNullCheck;
1355        final int nodeCount;
1356        final Mark mark;
1357
1358        public InvocationPluginAssertions(InvocationPlugin plugin, ValueNode[] args, ResolvedJavaMethod targetMethod, Kind resultType) {
1359            guarantee(assertionsEnabled(), "%s should only be loaded and instantiated if assertions are enabled", getClass().getSimpleName());
1360            this.plugin = plugin;
1361            this.targetMethod = targetMethod;
1362            this.args = args;
1363            this.resultType = resultType;
1364            this.beforeStackSize = frameState.stackSize();
1365            this.needsNullCheck = !targetMethod.isStatic() && args[0].getKind() == Kind.Object && !StampTool.isPointerNonNull(args[0].stamp());
1366            this.nodeCount = graph.getNodeCount();
1367            this.mark = graph.getMark();
1368        }
1369
1370        String error(String format, Object... a) {
1371            return String.format(format, a) + String.format("%n\tplugin at %s", plugin.getApplySourceLocation(metaAccess));
1372        }
1373
1374        boolean check(boolean pluginResult) {
1375            if (pluginResult == true) {
1376                int expectedStackSize = beforeStackSize + resultType.getSlotCount();
1377                assert expectedStackSize == frameState.stackSize() : error("plugin manipulated the stack incorrectly: expected=%d, actual=%d", expectedStackSize, frameState.stackSize());
1378                NodeIterable<Node> newNodes = graph.getNewNodes(mark);
1379                assert !needsNullCheck || isPointerNonNull(args[0].stamp()) : error("plugin needs to null check the receiver of %s: receiver=%s", targetMethod.format("%H.%n(%p)"), args[0]);
1380                for (Node n : newNodes) {
1381                    if (n instanceof StateSplit) {
1382                        StateSplit stateSplit = (StateSplit) n;
1383                        assert stateSplit.stateAfter() != null || !stateSplit.hasSideEffect() : error("%s node added by plugin for %s need to have a non-null frame state: %s",
1384                                        StateSplit.class.getSimpleName(), targetMethod.format("%H.%n(%p)"), stateSplit);
1385                    }
1386                }
1387                try {
1388                    graphBuilderConfig.getPlugins().getInvocationPlugins().checkNewNodes(BytecodeParser.this, plugin, newNodes);
1389                } catch (Throwable t) {
1390                    throw new AssertionError(error("Error in plugin"), t);
1391                }
1392            } else {
1393                assert nodeCount == graph.getNodeCount() : error("plugin that returns false must not create new nodes");
1394                assert beforeStackSize == frameState.stackSize() : error("plugin that returns false must not modify the stack");
1395            }
1396            return true;
1397        }
1398    }
1399
1400    private boolean tryInvocationPlugin(ValueNode[] args, ResolvedJavaMethod targetMethod, Kind resultType) {
1401        InvocationPlugin plugin = graphBuilderConfig.getPlugins().getInvocationPlugins().lookupInvocation(targetMethod);
1402        if (plugin != null) {
1403
1404            if (intrinsicContext != null && intrinsicContext.isCallToOriginal(targetMethod)) {
1405                // Self recursive intrinsic means the original
1406                // method should be called.
1407                assert !targetMethod.hasBytecodes() : "TODO: when does this happen?";
1408                return false;
1409            }
1410
1411            InvocationPluginAssertions assertions = assertionsEnabled() ? new InvocationPluginAssertions(plugin, args, targetMethod, resultType) : null;
1412            if (plugin.execute(this, targetMethod, invocationPluginReceiver.init(targetMethod, args), args)) {
1413                assert assertions.check(true);
1414                return true;
1415            }
1416            assert assertions.check(false);
1417        }
1418        return false;
1419    }
1420
1421    private boolean tryNodePluginForInvocation(ValueNode[] args, ResolvedJavaMethod targetMethod) {
1422        for (NodePlugin plugin : graphBuilderConfig.getPlugins().getNodePlugins()) {
1423            if (plugin.handleInvoke(this, targetMethod, args)) {
1424                return true;
1425            }
1426        }
1427        return false;
1428    }
1429
1430    InlineInfo lastInlineInfo;
1431
1432    private boolean tryInline(ValueNode[] args, ResolvedJavaMethod targetMethod, JavaType returnType) {
1433        boolean canBeInlined = forceInliningEverything || parsingIntrinsic() || targetMethod.canBeInlined();
1434        if (!canBeInlined) {
1435            return false;
1436        }
1437
1438        if (forceInliningEverything) {
1439            return inline(targetMethod, targetMethod, false, args);
1440        }
1441
1442        for (InlineInvokePlugin plugin : graphBuilderConfig.getPlugins().getInlineInvokePlugins()) {
1443            lastInlineInfo = plugin.shouldInlineInvoke(this, targetMethod, args, returnType);
1444            if (lastInlineInfo != null) {
1445                if (lastInlineInfo.getMethodToInline() == null) {
1446                    /* Do not inline, and do not ask the remaining plugins. */
1447                    return false;
1448                } else {
1449                    return inline(targetMethod, lastInlineInfo.getMethodToInline(), lastInlineInfo.isIntrinsic(), args);
1450                }
1451            }
1452        }
1453        return false;
1454    }
1455
1456    public void intrinsify(ResolvedJavaMethod targetMethod, ResolvedJavaMethod substitute, ValueNode[] args) {
1457        boolean res = inline(targetMethod, substitute, true, args);
1458        assert res : "failed to inline " + substitute;
1459    }
1460
1461    private boolean inline(ResolvedJavaMethod targetMethod, ResolvedJavaMethod inlinedMethod, boolean isIntrinsic, ValueNode[] args) {
1462        if (TraceInlineDuringParsing.getValue() || TraceParserPlugins.getValue()) {
1463            if (targetMethod.equals(inlinedMethod)) {
1464                traceWithContext("inlining call to %s", inlinedMethod.format("%h.%n(%p)"));
1465            } else {
1466                traceWithContext("inlining call to %s as intrinsic for %s", inlinedMethod.format("%h.%n(%p)"), targetMethod.format("%h.%n(%p)"));
1467            }
1468        }
1469        IntrinsicContext intrinsic = this.intrinsicContext;
1470        if (intrinsic != null && intrinsic.isCallToOriginal(targetMethod)) {
1471            if (intrinsic.isCompilationRoot()) {
1472                // A root compiled intrinsic needs to deoptimize
1473                // if the slow path is taken. During frame state
1474                // assignment, the deopt node will get its stateBefore
1475                // from the start node of the intrinsic
1476                append(new DeoptimizeNode(InvalidateRecompile, RuntimeConstraint));
1477                return true;
1478            } else {
1479                // Otherwise inline the original method. Any frame state created
1480                // during the inlining will exclude frame(s) in the
1481                // intrinsic method (see HIRFrameStateBuilder.create(int bci)).
1482                if (intrinsic.getOriginalMethod().isNative()) {
1483                    return false;
1484                }
1485                parseAndInlineCallee(intrinsic.getOriginalMethod(), args, null);
1486                return true;
1487            }
1488        } else {
1489            if (intrinsic == null && isIntrinsic) {
1490                assert !inlinedMethod.equals(targetMethod);
1491                intrinsic = new IntrinsicContext(targetMethod, inlinedMethod, INLINE_DURING_PARSING);
1492            }
1493            if (inlinedMethod.hasBytecodes()) {
1494                for (InlineInvokePlugin plugin : graphBuilderConfig.getPlugins().getInlineInvokePlugins()) {
1495                    plugin.notifyBeforeInline(inlinedMethod);
1496                }
1497                parseAndInlineCallee(inlinedMethod, args, intrinsic);
1498                for (InlineInvokePlugin plugin : graphBuilderConfig.getPlugins().getInlineInvokePlugins()) {
1499                    plugin.notifyAfterInline(inlinedMethod);
1500                }
1501            } else {
1502                return false;
1503            }
1504        }
1505        return true;
1506    }
1507
1508    /**
1509     * Prints a line to {@link TTY} with a prefix indicating the current parse context. The prefix
1510     * is of the form:
1511     *
1512     * <pre>
1513     * {SPACE * n} {name of method being parsed} "(" {file name} ":" {line number} ")"
1514     * </pre>
1515     *
1516     * where {@code n} is the current inlining depth.
1517     *
1518     * @param format a format string
1519     * @param args arguments to the format string
1520     */
1521
1522    protected void traceWithContext(String format, Object... args) {
1523        StackTraceElement where = method.asStackTraceElement(bci());
1524        TTY.println(format("%s%s (%s:%d) %s", nSpaces(getDepth()), method.isConstructor() ? method.format("%h.%n") : method.getName(), where.getFileName(), where.getLineNumber(), format(format, args)));
1525    }
1526
1527    protected BytecodeParserError asParserError(Throwable e) {
1528        if (e instanceof BytecodeParserError) {
1529            return (BytecodeParserError) e;
1530        }
1531        BytecodeParser bp = this;
1532        BytecodeParserError res = new BytecodeParserError(e);
1533        while (bp != null) {
1534            res.addContext("parsing " + bp.method.asStackTraceElement(bp.bci()));
1535            bp = bp.parent;
1536        }
1537        return res;
1538    }
1539
1540    private void parseAndInlineCallee(ResolvedJavaMethod targetMethod, ValueNode[] args, IntrinsicContext calleeIntrinsicContext) {
1541        try (IntrinsicScope s = calleeIntrinsicContext != null && !parsingIntrinsic() ? new IntrinsicScope(this, targetMethod.getSignature().toParameterKinds(!targetMethod.isStatic()), args) : null) {
1542
1543            BytecodeParser parser = graphBuilderInstance.createBytecodeParser(graph, this, targetMethod, Compiler.INVOCATION_ENTRY_BCI, calleeIntrinsicContext);
1544            FrameStateBuilder startFrameState = new FrameStateBuilder(parser, targetMethod, graph);
1545            if (!targetMethod.isStatic()) {
1546                args[0] = nullCheckedValue(args[0]);
1547            }
1548            startFrameState.initializeFromArgumentsArray(args);
1549            parser.build(this.lastInstr, startFrameState);
1550
1551            FixedWithNextNode calleeBeforeReturnNode = parser.getBeforeReturnNode();
1552            this.lastInstr = calleeBeforeReturnNode;
1553            Kind calleeReturnKind = targetMethod.getSignature().getReturnKind();
1554            if (calleeBeforeReturnNode != null) {
1555                ValueNode calleeReturnValue = parser.getReturnValue();
1556                if (calleeReturnValue != null) {
1557                    frameState.push(calleeReturnKind.getStackKind(), calleeReturnValue);
1558                }
1559            }
1560
1561            FixedWithNextNode calleeBeforeUnwindNode = parser.getBeforeUnwindNode();
1562            if (calleeBeforeUnwindNode != null) {
1563                ValueNode calleeUnwindValue = parser.getUnwindValue();
1564                assert calleeUnwindValue != null;
1565                calleeBeforeUnwindNode.setNext(handleException(calleeUnwindValue, bci()));
1566            }
1567
1568            // Record inlined method dependency in the graph
1569            graph.recordInlinedMethod(targetMethod);
1570        }
1571    }
1572
1573    protected MethodCallTargetNode createMethodCallTarget(InvokeKind invokeKind, ResolvedJavaMethod targetMethod, ValueNode[] args, JavaType returnType, JavaTypeProfile profile) {
1574        return new MethodCallTargetNode(invokeKind, targetMethod, args, returnType, profile);
1575    }
1576
1577    protected InvokeNode createInvoke(CallTargetNode callTarget, Kind resultType) {
1578        InvokeNode invoke = append(new InvokeNode(callTarget, bci()));
1579        frameState.pushReturn(resultType, invoke);
1580        invoke.setStateAfter(createFrameState(stream.nextBCI(), invoke));
1581        return invoke;
1582    }
1583
1584    protected InvokeWithExceptionNode createInvokeWithException(CallTargetNode callTarget, Kind resultType) {
1585        if (currentBlock != null && stream.nextBCI() > currentBlock.endBci) {
1586            /*
1587             * Clear non-live locals early so that the exception handler entry gets the cleared
1588             * state.
1589             */
1590            frameState.clearNonLiveLocals(currentBlock, liveness, false);
1591        }
1592
1593        DispatchBeginNode exceptionEdge = handleException(null, bci());
1594        InvokeWithExceptionNode invoke = append(new InvokeWithExceptionNode(callTarget, exceptionEdge, bci()));
1595        frameState.pushReturn(resultType, invoke);
1596        invoke.setStateAfter(createFrameState(stream.nextBCI(), invoke));
1597        return invoke;
1598    }
1599
1600    protected void genReturn(ValueNode returnVal, Kind returnKind) {
1601        if (parsingIntrinsic() && returnVal != null) {
1602            if (returnVal instanceof StateSplit) {
1603                StateSplit stateSplit = (StateSplit) returnVal;
1604                FrameState stateAfter = stateSplit.stateAfter();
1605                if (stateSplit.hasSideEffect()) {
1606                    assert stateSplit != null;
1607                    if (stateAfter.bci == BytecodeFrame.AFTER_BCI) {
1608                        assert stateAfter.usages().count() == 1;
1609                        assert stateAfter.usages().first() == stateSplit;
1610                        stateAfter.replaceAtUsages(graph.add(new FrameState(BytecodeFrame.AFTER_BCI, returnVal)));
1611                        GraphUtil.killWithUnusedFloatingInputs(stateAfter);
1612                    } else {
1613                        /*
1614                         * This must be the return value from within a partial intrinsification.
1615                         */
1616                        assert !BytecodeFrame.isPlaceholderBci(stateAfter.bci);
1617                    }
1618                } else {
1619                    assert stateAfter == null;
1620                }
1621            }
1622        }
1623        if (parent == null) {
1624            frameState.setRethrowException(false);
1625            frameState.clearStack();
1626            beforeReturn(returnVal, returnKind);
1627            append(new ReturnNode(returnVal));
1628        } else {
1629            if (blockMap.getReturnCount() == 1 || !controlFlowSplit) {
1630                // There is only a single return.
1631                beforeReturn(returnVal, returnKind);
1632                this.returnValue = returnVal;
1633                this.beforeReturnNode = this.lastInstr;
1634                this.lastInstr = null;
1635            } else {
1636                frameState.setRethrowException(false);
1637                frameState.clearStack();
1638                if (returnVal != null) {
1639                    frameState.push(returnKind, returnVal);
1640                }
1641                assert blockMap.getReturnCount() > 1;
1642                appendGoto(blockMap.getReturnBlock());
1643            }
1644        }
1645    }
1646
1647    private void beforeReturn(ValueNode x, Kind kind) {
1648        if (graph.method() != null && graph.method().isJavaLangObjectInit()) {
1649            append(new RegisterFinalizerNode(frameState.loadLocal(0, Kind.Object)));
1650        }
1651        if (graphBuilderConfig.insertNonSafepointDebugInfo() && !parsingIntrinsic()) {
1652            genInfoPointNode(InfopointReason.METHOD_END, x);
1653        }
1654
1655        synchronizedEpilogue(BytecodeFrame.AFTER_BCI, x, kind);
1656        if (frameState.lockDepth(false) != 0) {
1657            throw bailout("unbalanced monitors");
1658        }
1659    }
1660
1661    protected void genMonitorEnter(ValueNode x, int bci) {
1662        MonitorIdNode monitorId = graph.add(new MonitorIdNode(frameState.lockDepth(true)));
1663        MonitorEnterNode monitorEnter = append(new MonitorEnterNode(x, monitorId));
1664        frameState.pushLock(x, monitorId);
1665        monitorEnter.setStateAfter(createFrameState(bci, monitorEnter));
1666    }
1667
1668    protected void genMonitorExit(ValueNode x, ValueNode escapedReturnValue, int bci) {
1669        MonitorIdNode monitorId = frameState.peekMonitorId();
1670        ValueNode lockedObject = frameState.popLock();
1671        if (GraphUtil.originalValue(lockedObject) != GraphUtil.originalValue(x)) {
1672            throw bailout(String.format("unbalanced monitors: mismatch at monitorexit, %s != %s", GraphUtil.originalValue(x), GraphUtil.originalValue(lockedObject)));
1673        }
1674        MonitorExitNode monitorExit = append(new MonitorExitNode(x, monitorId, escapedReturnValue));
1675        monitorExit.setStateAfter(createFrameState(bci, monitorExit));
1676    }
1677
1678    protected void genJsr(int dest) {
1679        BciBlock successor = currentBlock.getJsrSuccessor();
1680        assert successor.startBci == dest : successor.startBci + " != " + dest + " @" + bci();
1681        JsrScope scope = currentBlock.getJsrScope();
1682        int nextBci = getStream().nextBCI();
1683        if (!successor.getJsrScope().pop().equals(scope)) {
1684            throw new JsrNotSupportedBailout("unstructured control flow (internal limitation)");
1685        }
1686        if (successor.getJsrScope().nextReturnAddress() != nextBci) {
1687            throw new JsrNotSupportedBailout("unstructured control flow (internal limitation)");
1688        }
1689        ConstantNode nextBciNode = getJsrConstant(nextBci);
1690        frameState.push(Kind.Object, nextBciNode);
1691        appendGoto(successor);
1692    }
1693
1694    protected void genRet(int localIndex) {
1695        BciBlock successor = currentBlock.getRetSuccessor();
1696        ValueNode local = frameState.loadLocal(localIndex, Kind.Object);
1697        JsrScope scope = currentBlock.getJsrScope();
1698        int retAddress = scope.nextReturnAddress();
1699        ConstantNode returnBciNode = getJsrConstant(retAddress);
1700        LogicNode guard = IntegerEqualsNode.create(local, returnBciNode, constantReflection);
1701        guard = graph.unique(guard);
1702        append(new FixedGuardNode(guard, JavaSubroutineMismatch, InvalidateReprofile));
1703        if (!successor.getJsrScope().equals(scope.pop())) {
1704            throw new JsrNotSupportedBailout("unstructured control flow (ret leaves more than one scope)");
1705        }
1706        appendGoto(successor);
1707    }
1708
1709    private ConstantNode getJsrConstant(long bci) {
1710        JavaConstant nextBciConstant = new RawConstant(bci);
1711        Stamp nextBciStamp = StampFactory.forConstant(nextBciConstant);
1712        ConstantNode nextBciNode = new ConstantNode(nextBciConstant, nextBciStamp);
1713        return graph.unique(nextBciNode);
1714    }
1715
1716    protected void genIntegerSwitch(ValueNode value, ArrayList<BciBlock> actualSuccessors, int[] keys, double[] keyProbabilities, int[] keySuccessors) {
1717        if (value.isConstant()) {
1718            JavaConstant constant = (JavaConstant) value.asConstant();
1719            int constantValue = constant.asInt();
1720            for (int i = 0; i < keys.length; ++i) {
1721                if (keys[i] == constantValue) {
1722                    appendGoto(actualSuccessors.get(keySuccessors[i]));
1723                    return;
1724                }
1725            }
1726            appendGoto(actualSuccessors.get(keySuccessors[keys.length]));
1727        } else {
1728            this.controlFlowSplit = true;
1729            double[] successorProbabilities = successorProbabilites(actualSuccessors.size(), keySuccessors, keyProbabilities);
1730            IntegerSwitchNode switchNode = append(new IntegerSwitchNode(value, actualSuccessors.size(), keys, keyProbabilities, keySuccessors));
1731            for (int i = 0; i < actualSuccessors.size(); i++) {
1732                switchNode.setBlockSuccessor(i, createBlockTarget(successorProbabilities[i], actualSuccessors.get(i), frameState));
1733            }
1734        }
1735    }
1736
1737    /**
1738     * Helper function that sums up the probabilities of all keys that lead to a specific successor.
1739     *
1740     * @return an array of size successorCount with the accumulated probability for each successor.
1741     */
1742    private static double[] successorProbabilites(int successorCount, int[] keySuccessors, double[] keyProbabilities) {
1743        double[] probability = new double[successorCount];
1744        for (int i = 0; i < keySuccessors.length; i++) {
1745            probability[keySuccessors[i]] += keyProbabilities[i];
1746        }
1747        return probability;
1748    }
1749
1750    protected ConstantNode appendConstant(JavaConstant constant) {
1751        assert constant != null;
1752        return ConstantNode.forConstant(constant, metaAccess, graph);
1753    }
1754
1755    @Override
1756    public <T extends ValueNode> T append(T v) {
1757        if (v.graph() != null) {
1758            return v;
1759        }
1760        T added = graph.addOrUnique(v);
1761        if (added == v) {
1762            updateLastInstruction(v);
1763        }
1764        return added;
1765    }
1766
1767    public <T extends ValueNode> T recursiveAppend(T v) {
1768        if (v.graph() != null) {
1769            return v;
1770        }
1771        T added = graph.addOrUniqueWithInputs(v);
1772        if (added == v) {
1773            updateLastInstruction(v);
1774        }
1775        return added;
1776    }
1777
1778    private <T extends ValueNode> void updateLastInstruction(T v) {
1779        if (v instanceof FixedNode) {
1780            FixedNode fixedNode = (FixedNode) v;
1781            lastInstr.setNext(fixedNode);
1782            if (fixedNode instanceof FixedWithNextNode) {
1783                FixedWithNextNode fixedWithNextNode = (FixedWithNextNode) fixedNode;
1784                assert fixedWithNextNode.next() == null : "cannot append instruction to instruction which isn't end";
1785                lastInstr = fixedWithNextNode;
1786            } else {
1787                lastInstr = null;
1788            }
1789        }
1790    }
1791
1792    private Target checkLoopExit(FixedNode target, BciBlock targetBlock, FrameStateBuilder state) {
1793        if (currentBlock != null && !explodeLoops) {
1794            long exits = currentBlock.loops & ~targetBlock.loops;
1795            if (exits != 0) {
1796                LoopExitNode firstLoopExit = null;
1797                LoopExitNode lastLoopExit = null;
1798
1799                int pos = 0;
1800                ArrayList<BciBlock> exitLoops = new ArrayList<>(Long.bitCount(exits));
1801                do {
1802                    long lMask = 1L << pos;
1803                    if ((exits & lMask) != 0) {
1804                        exitLoops.add(blockMap.getLoopHeader(pos));
1805                        exits &= ~lMask;
1806                    }
1807                    pos++;
1808                } while (exits != 0);
1809
1810                Collections.sort(exitLoops, new Comparator<BciBlock>() {
1811
1812                    @Override
1813                    public int compare(BciBlock o1, BciBlock o2) {
1814                        return Long.bitCount(o2.loops) - Long.bitCount(o1.loops);
1815                    }
1816                });
1817
1818                int bci = targetBlock.startBci;
1819                if (targetBlock instanceof ExceptionDispatchBlock) {
1820                    bci = ((ExceptionDispatchBlock) targetBlock).deoptBci;
1821                }
1822                FrameStateBuilder newState = state.copy();
1823                for (BciBlock loop : exitLoops) {
1824                    LoopBeginNode loopBegin = (LoopBeginNode) getFirstInstruction(loop, this.getCurrentDimension());
1825                    LoopExitNode loopExit = graph.add(new LoopExitNode(loopBegin));
1826                    if (lastLoopExit != null) {
1827                        lastLoopExit.setNext(loopExit);
1828                    }
1829                    if (firstLoopExit == null) {
1830                        firstLoopExit = loopExit;
1831                    }
1832                    lastLoopExit = loopExit;
1833                    Debug.log("Target %s Exits %s, scanning framestates...", targetBlock, loop);
1834                    newState.insertLoopProxies(loopExit, getEntryState(loop, this.getCurrentDimension()));
1835                    loopExit.setStateAfter(newState.create(bci, loopExit));
1836                }
1837
1838                lastLoopExit.setNext(target);
1839                return new Target(firstLoopExit, newState);
1840            }
1841        }
1842        return new Target(target, state);
1843    }
1844
1845    private FrameStateBuilder getEntryState(BciBlock block, int dimension) {
1846        int id = block.id;
1847        if (dimension == 0) {
1848            return entryStateArray[id];
1849        } else {
1850            return getEntryStateMultiDimension(dimension, id);
1851        }
1852    }
1853
1854    private FrameStateBuilder getEntryStateMultiDimension(int dimension, int id) {
1855        if (entryStateMatrix != null && dimension - 1 < entryStateMatrix.length) {
1856            FrameStateBuilder[] entryStateArrayEntry = entryStateMatrix[dimension - 1];
1857            if (entryStateArrayEntry == null) {
1858                return null;
1859            }
1860            return entryStateArrayEntry[id];
1861        } else {
1862            return null;
1863        }
1864    }
1865
1866    private void setEntryState(BciBlock block, int dimension, FrameStateBuilder entryState) {
1867        int id = block.id;
1868        if (dimension == 0) {
1869            this.entryStateArray[id] = entryState;
1870        } else {
1871            setEntryStateMultiDimension(dimension, entryState, id);
1872        }
1873    }
1874
1875    private void setEntryStateMultiDimension(int dimension, FrameStateBuilder entryState, int id) {
1876        if (entryStateMatrix == null) {
1877            entryStateMatrix = new FrameStateBuilder[4][];
1878        }
1879        if (dimension - 1 < entryStateMatrix.length) {
1880            // We are within bounds.
1881        } else {
1882            // We are out of bounds.
1883            entryStateMatrix = Arrays.copyOf(entryStateMatrix, Math.max(entryStateMatrix.length * 2, dimension));
1884        }
1885        if (entryStateMatrix[dimension - 1] == null) {
1886            entryStateMatrix[dimension - 1] = new FrameStateBuilder[blockMap.getBlockCount()];
1887        }
1888        entryStateMatrix[dimension - 1][id] = entryState;
1889    }
1890
1891    private void setFirstInstruction(BciBlock block, int dimension, FixedWithNextNode firstInstruction) {
1892        int id = block.id;
1893        if (dimension == 0) {
1894            this.firstInstructionArray[id] = firstInstruction;
1895        } else {
1896            setFirstInstructionMultiDimension(dimension, firstInstruction, id);
1897        }
1898    }
1899
1900    private void setFirstInstructionMultiDimension(int dimension, FixedWithNextNode firstInstruction, int id) {
1901        if (firstInstructionMatrix == null) {
1902            firstInstructionMatrix = new FixedWithNextNode[4][];
1903        }
1904        if (dimension - 1 < firstInstructionMatrix.length) {
1905            // We are within bounds.
1906        } else {
1907            // We are out of bounds.
1908            firstInstructionMatrix = Arrays.copyOf(firstInstructionMatrix, Math.max(firstInstructionMatrix.length * 2, dimension));
1909        }
1910        if (firstInstructionMatrix[dimension - 1] == null) {
1911            firstInstructionMatrix[dimension - 1] = new FixedWithNextNode[blockMap.getBlockCount()];
1912        }
1913        firstInstructionMatrix[dimension - 1][id] = firstInstruction;
1914    }
1915
1916    private FixedWithNextNode getFirstInstruction(BciBlock block, int dimension) {
1917        int id = block.id;
1918        if (dimension == 0) {
1919            return firstInstructionArray[id];
1920        } else {
1921            return getFirstInstructionMultiDimension(dimension, id);
1922        }
1923    }
1924
1925    private FixedWithNextNode getFirstInstructionMultiDimension(int dimension, int id) {
1926        if (firstInstructionMatrix != null && dimension - 1 < firstInstructionMatrix.length) {
1927            FixedWithNextNode[] firstInstructionArrayEntry = firstInstructionMatrix[dimension - 1];
1928            if (firstInstructionArrayEntry == null) {
1929                return null;
1930            }
1931            return firstInstructionArrayEntry[id];
1932        } else {
1933            return null;
1934        }
1935    }
1936
1937    private FixedNode createTarget(double probability, BciBlock block, FrameStateBuilder stateAfter) {
1938        assert probability >= 0 && probability <= 1.01 : probability;
1939        if (isNeverExecutedCode(probability)) {
1940            return graph.add(new DeoptimizeNode(InvalidateReprofile, UnreachedCode));
1941        } else {
1942            assert block != null;
1943            return createTarget(block, stateAfter);
1944        }
1945    }
1946
1947    private FixedNode createTarget(BciBlock block, FrameStateBuilder state) {
1948        return createTarget(block, state, false, false);
1949    }
1950
1951    private FixedNode createTarget(BciBlock block, FrameStateBuilder state, boolean canReuseInstruction, boolean canReuseState) {
1952        assert block != null && state != null;
1953        assert !block.isExceptionEntry || state.stackSize() == 1;
1954
1955        int operatingDimension = findOperatingDimension(block, state);
1956
1957        if (getFirstInstruction(block, operatingDimension) == null) {
1958            /*
1959             * This is the first time we see this block as a branch target. Create and return a
1960             * placeholder that later can be replaced with a MergeNode when we see this block again.
1961             */
1962            FixedNode targetNode;
1963            if (canReuseInstruction && (block.getPredecessorCount() == 1 || !controlFlowSplit) && !block.isLoopHeader && (currentBlock.loops & ~block.loops) == 0) {
1964                setFirstInstruction(block, operatingDimension, lastInstr);
1965                lastInstr = null;
1966            } else {
1967                setFirstInstruction(block, operatingDimension, graph.add(new BeginNode()));
1968            }
1969            targetNode = getFirstInstruction(block, operatingDimension);
1970            Target target = checkLoopExit(targetNode, block, state);
1971            FixedNode result = target.fixed;
1972            FrameStateBuilder currentEntryState = target.state == state ? (canReuseState ? state : state.copy()) : target.state;
1973            setEntryState(block, operatingDimension, currentEntryState);
1974            currentEntryState.clearNonLiveLocals(block, liveness, true);
1975
1976            Debug.log("createTarget %s: first visit, result: %s", block, targetNode);
1977            return result;
1978        }
1979
1980        // We already saw this block before, so we have to merge states.
1981        if (!getEntryState(block, operatingDimension).isCompatibleWith(state)) {
1982            throw bailout("stacks do not match; bytecodes would not verify");
1983        }
1984
1985        if (getFirstInstruction(block, operatingDimension) instanceof LoopBeginNode) {
1986            assert this.explodeLoops || (block.isLoopHeader && currentBlock.getId() >= block.getId()) : "must be backward branch";
1987            /*
1988             * Backward loop edge. We need to create a special LoopEndNode and merge with the loop
1989             * begin node created before.
1990             */
1991            LoopBeginNode loopBegin = (LoopBeginNode) getFirstInstruction(block, operatingDimension);
1992            LoopEndNode loopEnd = graph.add(new LoopEndNode(loopBegin));
1993            if (parsingIntrinsic()) {
1994                loopEnd.disableSafepoint();
1995            }
1996            Target target = checkLoopExit(loopEnd, block, state);
1997            FixedNode result = target.fixed;
1998            getEntryState(block, operatingDimension).merge(loopBegin, target.state);
1999
2000            Debug.log("createTarget %s: merging backward branch to loop header %s, result: %s", block, loopBegin, result);
2001            return result;
2002        }
2003        assert currentBlock == null || currentBlock.getId() < block.getId() || this.mergeExplosions : "must not be backward branch";
2004        assert getFirstInstruction(block, operatingDimension).next() == null || this.mergeExplosions : "bytecodes already parsed for block";
2005
2006        if (getFirstInstruction(block, operatingDimension) instanceof AbstractBeginNode && !(getFirstInstruction(block, operatingDimension) instanceof AbstractMergeNode)) {
2007            /*
2008             * This is the second time we see this block. Create the actual MergeNode and the End
2009             * Node for the already existing edge.
2010             */
2011            AbstractBeginNode beginNode = (AbstractBeginNode) getFirstInstruction(block, operatingDimension);
2012
2013            // The EndNode for the already existing edge.
2014            EndNode end = graph.add(new EndNode());
2015            // The MergeNode that replaces the placeholder.
2016            AbstractMergeNode mergeNode = graph.add(new MergeNode());
2017            FixedNode next = beginNode.next();
2018
2019            if (beginNode.predecessor() instanceof ControlSplitNode) {
2020                beginNode.setNext(end);
2021            } else {
2022                beginNode.replaceAtPredecessor(end);
2023                beginNode.safeDelete();
2024            }
2025
2026            mergeNode.addForwardEnd(end);
2027            mergeNode.setNext(next);
2028
2029            setFirstInstruction(block, operatingDimension, mergeNode);
2030        }
2031
2032        AbstractMergeNode mergeNode = (AbstractMergeNode) getFirstInstruction(block, operatingDimension);
2033
2034        // The EndNode for the newly merged edge.
2035        EndNode newEnd = graph.add(new EndNode());
2036        Target target = checkLoopExit(newEnd, block, state);
2037        FixedNode result = target.fixed;
2038        getEntryState(block, operatingDimension).merge(mergeNode, target.state);
2039        mergeNode.addForwardEnd(newEnd);
2040
2041        Debug.log("createTarget %s: merging state, result: %s", block, result);
2042        return result;
2043    }
2044
2045    private int findOperatingDimension(BciBlock block, FrameStateBuilder state) {
2046        if (this.explodeLoops && this.explodeLoopsContext != null && !this.explodeLoopsContext.isEmpty()) {
2047            return findOperatingDimensionWithLoopExplosion(block, state);
2048        }
2049        return this.getCurrentDimension();
2050    }
2051
2052    private int findOperatingDimensionWithLoopExplosion(BciBlock block, FrameStateBuilder state) {
2053        for (ExplodedLoopContext context : explodeLoopsContext) {
2054            if (context.header == block) {
2055
2056                if (this.mergeExplosions) {
2057                    state.clearNonLiveLocals(block, liveness, true);
2058                    Integer cachedDimension = mergeExplosionsMap.get(state);
2059                    if (cachedDimension != null) {
2060                        return cachedDimension;
2061                    }
2062                }
2063
2064                // We have a hit on our current explosion context loop begin.
2065                if (context.targetPeelIteration == null) {
2066                    context.targetPeelIteration = new int[1];
2067                } else {
2068                    context.targetPeelIteration = Arrays.copyOf(context.targetPeelIteration, context.targetPeelIteration.length + 1);
2069                }
2070
2071                // This is the first hit => allocate a new dimension and at the same
2072                // time mark the context loop begin as hit during the current
2073                // iteration.
2074                if (this.mergeExplosions) {
2075                    this.addToMergeCache(state, nextPeelIteration);
2076                }
2077                context.targetPeelIteration[context.targetPeelIteration.length - 1] = nextPeelIteration++;
2078                if (nextPeelIteration > MaximumLoopExplosionCount.getValue()) {
2079                    String message = "too many loop explosion iterations - does the explosion not terminate for method " + method + "?";
2080                    if (FailedLoopExplosionIsFatal.getValue()) {
2081                        throw new RuntimeException(message);
2082                    } else {
2083                        throw bailout(message);
2084                    }
2085                }
2086
2087                // Operate on the target dimension.
2088                return context.targetPeelIteration[context.targetPeelIteration.length - 1];
2089            } else if (block.getId() > context.header.getId() && block.getId() <= context.header.loopEnd) {
2090                // We hit the range of this context.
2091                return context.peelIteration;
2092            }
2093        }
2094
2095        // No dimension found.
2096        return 0;
2097    }
2098
2099    /**
2100     * Returns a block begin node with the specified state. If the specified probability is 0, the
2101     * block deoptimizes immediately.
2102     */
2103    private AbstractBeginNode createBlockTarget(double probability, BciBlock block, FrameStateBuilder stateAfter) {
2104        FixedNode target = createTarget(probability, block, stateAfter);
2105        AbstractBeginNode begin = BeginNode.begin(target);
2106
2107        assert !(target instanceof DeoptimizeNode && begin instanceof BeginStateSplitNode && ((BeginStateSplitNode) begin).stateAfter() != null) : "We are not allowed to set the stateAfter of the begin node, because we have to deoptimize "
2108                        + "to a bci _before_ the actual if, so that the interpreter can update the profiling information.";
2109        return begin;
2110    }
2111
2112    private ValueNode synchronizedObject(FrameStateBuilder state, ResolvedJavaMethod target) {
2113        if (target.isStatic()) {
2114            return appendConstant(target.getDeclaringClass().getJavaClass());
2115        } else {
2116            return state.loadLocal(0, Kind.Object);
2117        }
2118    }
2119
2120    protected void processBlock(BytecodeParser parser, BciBlock block) {
2121        // Ignore blocks that have no predecessors by the time their bytecodes are parsed
2122        int currentDimension = this.getCurrentDimension();
2123        FixedWithNextNode firstInstruction = getFirstInstruction(block, currentDimension);
2124        if (firstInstruction == null) {
2125            Debug.log("Ignoring block %s", block);
2126            return;
2127        }
2128        try (Indent indent = Debug.logAndIndent("Parsing block %s  firstInstruction: %s  loopHeader: %b", block, firstInstruction, block.isLoopHeader)) {
2129
2130            lastInstr = firstInstruction;
2131            frameState = getEntryState(block, currentDimension);
2132            frameState.cleanDeletedNodes();
2133            parser.setCurrentFrameState(frameState);
2134            currentBlock = block;
2135
2136            if (firstInstruction instanceof AbstractMergeNode) {
2137                setMergeStateAfter(block, firstInstruction);
2138            }
2139
2140            if (block == blockMap.getReturnBlock()) {
2141                handleReturnBlock();
2142            } else if (block == blockMap.getUnwindBlock()) {
2143                handleUnwindBlock();
2144            } else if (block instanceof ExceptionDispatchBlock) {
2145                createExceptionDispatch((ExceptionDispatchBlock) block);
2146            } else {
2147                frameState.setRethrowException(false);
2148                iterateBytecodesForBlock(block);
2149            }
2150        }
2151    }
2152
2153    private void handleUnwindBlock() {
2154        if (parent == null) {
2155            frameState.setRethrowException(false);
2156            createUnwind();
2157        } else {
2158            ValueNode exception = frameState.pop(Kind.Object);
2159            this.unwindValue = exception;
2160            this.beforeUnwindNode = this.lastInstr;
2161        }
2162    }
2163
2164    private void handleReturnBlock() {
2165        Kind returnKind = method.getSignature().getReturnKind().getStackKind();
2166        ValueNode x = returnKind == Kind.Void ? null : frameState.pop(returnKind);
2167        assert frameState.stackSize() == 0;
2168        beforeReturn(x, returnKind);
2169        this.returnValue = x;
2170        this.beforeReturnNode = this.lastInstr;
2171    }
2172
2173    private void setMergeStateAfter(BciBlock block, FixedWithNextNode firstInstruction) {
2174        AbstractMergeNode abstractMergeNode = (AbstractMergeNode) firstInstruction;
2175        if (abstractMergeNode.stateAfter() == null) {
2176            int bci = block.startBci;
2177            if (block instanceof ExceptionDispatchBlock) {
2178                bci = ((ExceptionDispatchBlock) block).deoptBci;
2179            }
2180            abstractMergeNode.setStateAfter(createFrameState(bci, abstractMergeNode));
2181        }
2182    }
2183
2184    private void createUnwind() {
2185        assert frameState.stackSize() == 1 : frameState;
2186        ValueNode exception = frameState.pop(Kind.Object);
2187        synchronizedEpilogue(BytecodeFrame.AFTER_EXCEPTION_BCI, null, null);
2188        append(new UnwindNode(exception));
2189    }
2190
2191    private void synchronizedEpilogue(int bci, ValueNode currentReturnValue, Kind currentReturnValueKind) {
2192        if (method.isSynchronized()) {
2193            if (currentReturnValue != null) {
2194                frameState.push(currentReturnValueKind, currentReturnValue);
2195            }
2196            genMonitorExit(methodSynchronizedObject, currentReturnValue, bci);
2197            assert !frameState.rethrowException();
2198        }
2199    }
2200
2201    private void createExceptionDispatch(ExceptionDispatchBlock block) {
2202        assert frameState.stackSize() == 1 : frameState;
2203        if (block.handler.isCatchAll()) {
2204            assert block.getSuccessorCount() == 1;
2205            appendGoto(block.getSuccessor(0));
2206            return;
2207        }
2208
2209        JavaType catchType = block.handler.getCatchType();
2210        if (graphBuilderConfig.eagerResolving()) {
2211            catchType = lookupType(block.handler.catchTypeCPI(), INSTANCEOF);
2212        }
2213        boolean initialized = (catchType instanceof ResolvedJavaType);
2214        if (initialized && graphBuilderConfig.getSkippedExceptionTypes() != null) {
2215            ResolvedJavaType resolvedCatchType = (ResolvedJavaType) catchType;
2216            for (ResolvedJavaType skippedType : graphBuilderConfig.getSkippedExceptionTypes()) {
2217                if (skippedType.isAssignableFrom(resolvedCatchType)) {
2218                    BciBlock nextBlock = block.getSuccessorCount() == 1 ? blockMap.getUnwindBlock() : block.getSuccessor(1);
2219                    ValueNode exception = frameState.stack[0];
2220                    FixedNode trueSuccessor = graph.add(new DeoptimizeNode(InvalidateReprofile, UnreachedCode));
2221                    FixedNode nextDispatch = createTarget(nextBlock, frameState);
2222                    append(new IfNode(graph.unique(InstanceOfNode.create((ResolvedJavaType) catchType, exception, null)), trueSuccessor, nextDispatch, 0));
2223                    return;
2224                }
2225            }
2226        }
2227
2228        if (initialized) {
2229            BciBlock nextBlock = block.getSuccessorCount() == 1 ? blockMap.getUnwindBlock() : block.getSuccessor(1);
2230            ValueNode exception = frameState.stack[0];
2231            CheckCastNode checkCast = graph.add(new CheckCastNode((ResolvedJavaType) catchType, exception, null, false));
2232            frameState.pop(Kind.Object);
2233            frameState.push(Kind.Object, checkCast);
2234            FixedNode catchSuccessor = createTarget(block.getSuccessor(0), frameState);
2235            frameState.pop(Kind.Object);
2236            frameState.push(Kind.Object, exception);
2237            FixedNode nextDispatch = createTarget(nextBlock, frameState);
2238            checkCast.setNext(catchSuccessor);
2239            append(new IfNode(graph.unique(InstanceOfNode.create((ResolvedJavaType) catchType, exception, null)), checkCast, nextDispatch, 0.5));
2240        } else {
2241            handleUnresolvedExceptionType(catchType);
2242        }
2243    }
2244
2245    private void appendGoto(BciBlock successor) {
2246        FixedNode targetInstr = createTarget(successor, frameState, true, true);
2247        if (lastInstr != null && lastInstr != targetInstr) {
2248            lastInstr.setNext(targetInstr);
2249        }
2250    }
2251
2252    protected void iterateBytecodesForBlock(BciBlock block) {
2253        if (block.isLoopHeader && !explodeLoops) {
2254            // Create the loop header block, which later will merge the backward branches of
2255            // the loop.
2256            controlFlowSplit = true;
2257            LoopBeginNode loopBegin = appendLoopBegin(this.lastInstr);
2258            lastInstr = loopBegin;
2259
2260            // Create phi functions for all local variables and operand stack slots.
2261            frameState.insertLoopPhis(liveness, block.loopId, loopBegin, forceLoopPhis());
2262            loopBegin.setStateAfter(createFrameState(block.startBci, loopBegin));
2263
2264            /*
2265             * We have seen all forward branches. All subsequent backward branches will merge to the
2266             * loop header. This ensures that the loop header has exactly one non-loop predecessor.
2267             */
2268            setFirstInstruction(block, this.getCurrentDimension(), loopBegin);
2269            /*
2270             * We need to preserve the frame state builder of the loop header so that we can merge
2271             * values for phi functions, so make a copy of it.
2272             */
2273            setEntryState(block, this.getCurrentDimension(), frameState.copy());
2274
2275            Debug.log("  created loop header %s", loopBegin);
2276        } else if (block.isLoopHeader && explodeLoops && this.mergeExplosions) {
2277            frameState = frameState.copy();
2278        }
2279        assert lastInstr.next() == null : "instructions already appended at block " + block;
2280        Debug.log("  frameState: %s", frameState);
2281
2282        lastInstr = finishInstruction(lastInstr, frameState);
2283
2284        int endBCI = stream.endBCI();
2285
2286        stream.setBCI(block.startBci);
2287        int bci = block.startBci;
2288        BytecodesParsed.add(block.endBci - bci);
2289
2290        /* Reset line number for new block */
2291        if (graphBuilderConfig.insertSimpleDebugInfo()) {
2292            previousLineNumber = -1;
2293        }
2294
2295        while (bci < endBCI) {
2296            if (graphBuilderConfig.insertNonSafepointDebugInfo() && !parsingIntrinsic()) {
2297                currentLineNumber = lnt != null ? lnt.getLineNumber(bci) : (graphBuilderConfig.insertFullDebugInfo() ? -1 : bci);
2298                if (currentLineNumber != previousLineNumber) {
2299                    genInfoPointNode(InfopointReason.LINE_NUMBER, null);
2300                    previousLineNumber = currentLineNumber;
2301                }
2302            }
2303
2304            // read the opcode
2305            int opcode = stream.currentBC();
2306            assert traceState();
2307            assert traceInstruction(bci, opcode, bci == block.startBci);
2308            if (parent == null && bci == entryBCI) {
2309                if (block.getJsrScope() != JsrScope.EMPTY_SCOPE) {
2310                    throw new BailoutException("OSR into a JSR scope is not supported");
2311                }
2312                EntryMarkerNode x = append(new EntryMarkerNode());
2313                frameState.insertProxies(value -> graph.unique(new EntryProxyNode(value, x)));
2314                x.setStateAfter(createFrameState(bci, x));
2315            }
2316
2317            try {
2318                processBytecode(bci, opcode);
2319            } catch (Throwable e) {
2320                throw asParserError(e);
2321            }
2322
2323            if (lastInstr == null || lastInstr.next() != null) {
2324                break;
2325            }
2326
2327            stream.next();
2328            bci = stream.currentBCI();
2329
2330            assert block == currentBlock;
2331            assert checkLastInstruction();
2332            lastInstr = finishInstruction(lastInstr, frameState);
2333            if (bci < endBCI) {
2334                if (bci > block.endBci) {
2335                    assert !block.getSuccessor(0).isExceptionEntry;
2336                    assert block.numNormalSuccessors() == 1;
2337                    // we fell through to the next block, add a goto and break
2338                    appendGoto(block.getSuccessor(0));
2339                    break;
2340                }
2341            }
2342        }
2343    }
2344
2345    /* Also a hook for subclasses. */
2346    protected boolean forceLoopPhis() {
2347        return graph.isOSR();
2348    }
2349
2350    protected boolean checkLastInstruction() {
2351        if (lastInstr instanceof BeginNode) {
2352            // ignore
2353        } else if (lastInstr instanceof StateSplit) {
2354            StateSplit stateSplit = (StateSplit) lastInstr;
2355            if (stateSplit.hasSideEffect()) {
2356                assert stateSplit.stateAfter() != null : "side effect " + lastInstr + " requires a non-null stateAfter";
2357            }
2358        }
2359        return true;
2360    }
2361
2362    private LoopBeginNode appendLoopBegin(FixedWithNextNode fixedWithNext) {
2363        EndNode preLoopEnd = graph.add(new EndNode());
2364        LoopBeginNode loopBegin = graph.add(new LoopBeginNode());
2365        fixedWithNext.setNext(preLoopEnd);
2366        // Add the single non-loop predecessor of the loop header.
2367        loopBegin.addForwardEnd(preLoopEnd);
2368        return loopBegin;
2369    }
2370
2371    /**
2372     * Hook for subclasses to modify the last instruction or add other instructions.
2373     *
2374     * @param instr The last instruction (= fixed node) which was added.
2375     * @param state The current frame state.
2376     * @return Returns the (new) last instruction.
2377     */
2378    protected FixedWithNextNode finishInstruction(FixedWithNextNode instr, FrameStateBuilder state) {
2379        return instr;
2380    }
2381
2382    private void genInfoPointNode(InfopointReason reason, ValueNode escapedReturnValue) {
2383        if (!parsingIntrinsic()) {
2384            if (graphBuilderConfig.insertFullDebugInfo()) {
2385                append(new FullInfopointNode(reason, createFrameState(bci(), null), escapedReturnValue));
2386            } else {
2387                BytecodePosition position = createBytecodePosition();
2388                // Update the previous infopoint position if no new fixed nodes were inserted
2389                if (lastInstr instanceof SimpleInfopointNode) {
2390                    SimpleInfopointNode lastInfopoint = (SimpleInfopointNode) lastInstr;
2391                    if (lastInfopoint.getReason() == reason) {
2392                        lastInfopoint.setPosition(position);
2393                    }
2394                }
2395                append(new SimpleInfopointNode(reason, position));
2396            }
2397        }
2398    }
2399
2400    private boolean traceState() {
2401        if (Debug.isEnabled() && Options.TraceBytecodeParserLevel.getValue() >= TRACELEVEL_STATE && Debug.isLogEnabled()) {
2402            frameState.traceState();
2403        }
2404        return true;
2405    }
2406
2407    protected void genIf(ValueNode x, Condition cond, ValueNode y) {
2408        assert x.getKind().getStackKind() == y.getKind().getStackKind();
2409        assert currentBlock.getSuccessorCount() == 2;
2410        BciBlock trueBlock = currentBlock.getSuccessor(0);
2411        BciBlock falseBlock = currentBlock.getSuccessor(1);
2412        if (trueBlock == falseBlock) {
2413            // The target block is the same independent of the condition.
2414            appendGoto(trueBlock);
2415            return;
2416        }
2417
2418        ValueNode a = x;
2419        ValueNode b = y;
2420
2421        // Check whether the condition needs to mirror the operands.
2422        if (cond.canonicalMirror()) {
2423            a = y;
2424            b = x;
2425        }
2426
2427        // Create the logic node for the condition.
2428        LogicNode condition = createLogicNode(cond, a, b);
2429
2430        // Check whether the condition needs to negate the result.
2431        boolean negate = cond.canonicalNegate();
2432
2433        // Remove a logic negation node and fold it into the negate boolean.
2434        if (condition instanceof LogicNegationNode) {
2435            LogicNegationNode logicNegationNode = (LogicNegationNode) condition;
2436            negate = !negate;
2437            condition = logicNegationNode.getValue();
2438        }
2439
2440        if (condition instanceof LogicConstantNode) {
2441            genConstantTargetIf(trueBlock, falseBlock, negate, condition);
2442        } else {
2443            if (condition.graph() == null) {
2444                condition = graph.unique(condition);
2445            }
2446
2447            // Need to get probability based on current bci.
2448            double probability = branchProbability();
2449
2450            if (negate) {
2451                BciBlock tmpBlock = trueBlock;
2452                trueBlock = falseBlock;
2453                falseBlock = tmpBlock;
2454                probability = 1 - probability;
2455            }
2456
2457            if (isNeverExecutedCode(probability)) {
2458                append(new FixedGuardNode(condition, UnreachedCode, InvalidateReprofile, true));
2459                appendGoto(falseBlock);
2460                return;
2461            } else if (isNeverExecutedCode(1 - probability)) {
2462                append(new FixedGuardNode(condition, UnreachedCode, InvalidateReprofile, false));
2463                appendGoto(trueBlock);
2464                return;
2465            }
2466
2467            int oldBci = stream.currentBCI();
2468            int trueBlockInt = checkPositiveIntConstantPushed(trueBlock);
2469            if (trueBlockInt != -1) {
2470                int falseBlockInt = checkPositiveIntConstantPushed(falseBlock);
2471                if (falseBlockInt != -1) {
2472                    if (tryGenConditionalForIf(trueBlock, falseBlock, condition, oldBci, trueBlockInt, falseBlockInt)) {
2473                        return;
2474                    }
2475                }
2476            }
2477
2478            this.controlFlowSplit = true;
2479            FixedNode trueSuccessor = createTarget(trueBlock, frameState, false, false);
2480            FixedNode falseSuccessor = createTarget(falseBlock, frameState, false, true);
2481            ValueNode ifNode = genIfNode(condition, trueSuccessor, falseSuccessor, probability);
2482            append(ifNode);
2483            if (parsingIntrinsic()) {
2484                if (x instanceof BranchProbabilityNode) {
2485                    ((BranchProbabilityNode) x).simplify(null);
2486                } else if (y instanceof BranchProbabilityNode) {
2487                    ((BranchProbabilityNode) y).simplify(null);
2488                }
2489            }
2490        }
2491    }
2492
2493    private boolean tryGenConditionalForIf(BciBlock trueBlock, BciBlock falseBlock, LogicNode condition, int oldBci, int trueBlockInt, int falseBlockInt) {
2494        if (gotoOrFallThroughAfterConstant(trueBlock) && gotoOrFallThroughAfterConstant(falseBlock) && trueBlock.getSuccessor(0) == falseBlock.getSuccessor(0)) {
2495            genConditionalForIf(trueBlock, condition, oldBci, trueBlockInt, falseBlockInt, false);
2496            return true;
2497        } else if (this.parent != null && returnAfterConstant(trueBlock) && returnAfterConstant(falseBlock)) {
2498            genConditionalForIf(trueBlock, condition, oldBci, trueBlockInt, falseBlockInt, true);
2499            return true;
2500        }
2501        return false;
2502    }
2503
2504    private void genConditionalForIf(BciBlock trueBlock, LogicNode condition, int oldBci, int trueBlockInt, int falseBlockInt, boolean genReturn) {
2505        ConstantNode trueValue = graph.unique(ConstantNode.forInt(trueBlockInt));
2506        ConstantNode falseValue = graph.unique(ConstantNode.forInt(falseBlockInt));
2507        ValueNode conditionalNode = ConditionalNode.create(condition, trueValue, falseValue);
2508        if (conditionalNode.graph() == null) {
2509            conditionalNode = graph.addOrUnique(conditionalNode);
2510        }
2511        if (genReturn) {
2512            Kind returnKind = method.getSignature().getReturnKind().getStackKind();
2513            this.genReturn(conditionalNode, returnKind);
2514        } else {
2515            frameState.push(Kind.Int, conditionalNode);
2516            appendGoto(trueBlock.getSuccessor(0));
2517            stream.setBCI(oldBci);
2518        }
2519    }
2520
2521    private LogicNode createLogicNode(Condition cond, ValueNode a, ValueNode b) {
2522        LogicNode condition;
2523        assert !a.getKind().isNumericFloat();
2524        if (cond == Condition.EQ || cond == Condition.NE) {
2525            if (a.getKind() == Kind.Object) {
2526                condition = genObjectEquals(a, b);
2527            } else {
2528                condition = genIntegerEquals(a, b);
2529            }
2530        } else {
2531            assert a.getKind() != Kind.Object && !cond.isUnsigned();
2532            condition = genIntegerLessThan(a, b);
2533        }
2534        return condition;
2535    }
2536
2537    private void genConstantTargetIf(BciBlock trueBlock, BciBlock falseBlock, boolean negate, LogicNode condition) {
2538        LogicConstantNode constantLogicNode = (LogicConstantNode) condition;
2539        boolean value = constantLogicNode.getValue();
2540        if (negate) {
2541            value = !value;
2542        }
2543        BciBlock nextBlock = falseBlock;
2544        if (value) {
2545            nextBlock = trueBlock;
2546        }
2547        appendGoto(nextBlock);
2548    }
2549
2550    private int checkPositiveIntConstantPushed(BciBlock block) {
2551        stream.setBCI(block.startBci);
2552        int currentBC = stream.currentBC();
2553        if (currentBC >= Bytecodes.ICONST_0 && currentBC <= Bytecodes.ICONST_5) {
2554            int constValue = currentBC - Bytecodes.ICONST_0;
2555            return constValue;
2556        }
2557        return -1;
2558    }
2559
2560    private boolean gotoOrFallThroughAfterConstant(BciBlock block) {
2561        stream.setBCI(block.startBci);
2562        int currentBCI = stream.nextBCI();
2563        stream.setBCI(currentBCI);
2564        int currentBC = stream.currentBC();
2565        return stream.currentBCI() > block.endBci || currentBC == Bytecodes.GOTO || currentBC == Bytecodes.GOTO_W;
2566    }
2567
2568    private boolean returnAfterConstant(BciBlock block) {
2569        stream.setBCI(block.startBci);
2570        int currentBCI = stream.nextBCI();
2571        stream.setBCI(currentBCI);
2572        int currentBC = stream.currentBC();
2573        return currentBC == Bytecodes.IRETURN;
2574    }
2575
2576    public StampProvider getStampProvider() {
2577        return stampProvider;
2578    }
2579
2580    public MetaAccessProvider getMetaAccess() {
2581        return metaAccess;
2582    }
2583
2584    public void push(Kind slotKind, ValueNode value) {
2585        assert value.isAlive();
2586        frameState.push(slotKind, value);
2587    }
2588
2589    private int getCurrentDimension() {
2590        if (this.explodeLoopsContext == null || this.explodeLoopsContext.isEmpty()) {
2591            return 0;
2592        } else {
2593            return this.explodeLoopsContext.peek().peelIteration;
2594        }
2595    }
2596
2597    public ConstantReflectionProvider getConstantReflection() {
2598        return constantReflection;
2599    }
2600
2601    /**
2602     * Gets the graph being processed by this builder.
2603     */
2604    public StructuredGraph getGraph() {
2605        return graph;
2606    }
2607
2608    public BytecodeParser getParent() {
2609        return parent;
2610    }
2611
2612    public IntrinsicContext getIntrinsic() {
2613        return intrinsicContext;
2614    }
2615
2616    @Override
2617    public String toString() {
2618        Formatter fmt = new Formatter();
2619        BytecodeParser bp = this;
2620        String indent = "";
2621        while (bp != null) {
2622            if (bp != this) {
2623                fmt.format("%n%s", indent);
2624            }
2625            fmt.format("%s [bci: %d, intrinsic: %s]", bp.method.asStackTraceElement(bp.bci()), bp.bci(), bp.parsingIntrinsic());
2626            fmt.format("%n%s", new BytecodeDisassembler().disassemble(bp.method, bp.bci(), bp.bci() + 10));
2627            bp = bp.parent;
2628            indent += " ";
2629        }
2630        return fmt.toString();
2631    }
2632
2633    public BailoutException bailout(String string) {
2634        FrameState currentFrameState = createFrameState(bci(), null);
2635        StackTraceElement[] elements = GraphUtil.approxSourceStackTraceElement(currentFrameState);
2636        BailoutException bailout = new BailoutException(string);
2637        throw GraphUtil.createBailoutException(string, bailout, elements);
2638    }
2639
2640    private FrameState createFrameState(int bci, StateSplit forStateSplit) {
2641        if (currentBlock != null && bci > currentBlock.endBci) {
2642            frameState.clearNonLiveLocals(currentBlock, liveness, false);
2643        }
2644        return frameState.create(bci, forStateSplit);
2645    }
2646
2647    public void setStateAfter(StateSplit sideEffect) {
2648        assert sideEffect.hasSideEffect();
2649        FrameState stateAfter = createFrameState(stream.nextBCI(), sideEffect);
2650        sideEffect.setStateAfter(stateAfter);
2651    }
2652
2653    private BytecodePosition createBytecodePosition() {
2654        return frameState.createBytecodePosition(bci());
2655    }
2656
2657    public void setCurrentFrameState(FrameStateBuilder frameState) {
2658        this.frameState = frameState;
2659    }
2660
2661    protected final BytecodeStream getStream() {
2662        return stream;
2663    }
2664
2665    public int bci() {
2666        return stream.currentBCI();
2667    }
2668
2669    public void loadLocal(int index, Kind kind) {
2670        ValueNode value = frameState.loadLocal(index, kind);
2671        frameState.push(kind, value);
2672    }
2673
2674    public void storeLocal(Kind kind, int index) {
2675        ValueNode value = frameState.pop(kind);
2676        frameState.storeLocal(index, kind, value);
2677    }
2678
2679    private void genLoadConstant(int cpi, int opcode) {
2680        Object con = lookupConstant(cpi, opcode);
2681
2682        if (con instanceof JavaType) {
2683            // this is a load of class constant which might be unresolved
2684            JavaType type = (JavaType) con;
2685            if (type instanceof ResolvedJavaType) {
2686                frameState.push(Kind.Object, appendConstant(((ResolvedJavaType) type).getJavaClass()));
2687            } else {
2688                handleUnresolvedLoadConstant(type);
2689            }
2690        } else if (con instanceof JavaConstant) {
2691            JavaConstant constant = (JavaConstant) con;
2692            frameState.push(constant.getKind(), appendConstant(constant));
2693        } else {
2694            throw new Error("lookupConstant returned an object of incorrect type");
2695        }
2696    }
2697
2698    private void genLoadIndexed(Kind kind) {
2699        ValueNode index = frameState.pop(Kind.Int);
2700        ValueNode array = emitExplicitExceptions(frameState.pop(Kind.Object), index);
2701
2702        for (NodePlugin plugin : graphBuilderConfig.getPlugins().getNodePlugins()) {
2703            if (plugin.handleLoadIndexed(this, array, index, kind)) {
2704                return;
2705            }
2706        }
2707
2708        frameState.push(kind, append(genLoadIndexed(array, index, kind)));
2709    }
2710
2711    private void genStoreIndexed(Kind kind) {
2712        ValueNode value = frameState.pop(kind);
2713        ValueNode index = frameState.pop(Kind.Int);
2714        ValueNode array = emitExplicitExceptions(frameState.pop(Kind.Object), index);
2715
2716        for (NodePlugin plugin : graphBuilderConfig.getPlugins().getNodePlugins()) {
2717            if (plugin.handleStoreIndexed(this, array, index, kind, value)) {
2718                return;
2719            }
2720        }
2721
2722        genStoreIndexed(array, index, kind, value);
2723    }
2724
2725    private void genArithmeticOp(Kind kind, int opcode) {
2726        ValueNode y = frameState.pop(kind);
2727        ValueNode x = frameState.pop(kind);
2728        ValueNode v;
2729        switch (opcode) {
2730            case IADD:
2731            case LADD:
2732                v = genIntegerAdd(x, y);
2733                break;
2734            case FADD:
2735            case DADD:
2736                v = genFloatAdd(x, y);
2737                break;
2738            case ISUB:
2739            case LSUB:
2740                v = genIntegerSub(x, y);
2741                break;
2742            case FSUB:
2743            case DSUB:
2744                v = genFloatSub(x, y);
2745                break;
2746            case IMUL:
2747            case LMUL:
2748                v = genIntegerMul(x, y);
2749                break;
2750            case FMUL:
2751            case DMUL:
2752                v = genFloatMul(x, y);
2753                break;
2754            case FDIV:
2755            case DDIV:
2756                v = genFloatDiv(x, y);
2757                break;
2758            case FREM:
2759            case DREM:
2760                v = genFloatRem(x, y);
2761                break;
2762            default:
2763                throw shouldNotReachHere();
2764        }
2765        frameState.push(kind, append(v));
2766    }
2767
2768    private void genIntegerDivOp(Kind kind, int opcode) {
2769        ValueNode y = frameState.pop(kind);
2770        ValueNode x = frameState.pop(kind);
2771        ValueNode v;
2772        switch (opcode) {
2773            case IDIV:
2774            case LDIV:
2775                v = genIntegerDiv(x, y);
2776                break;
2777            case IREM:
2778            case LREM:
2779                v = genIntegerRem(x, y);
2780                break;
2781            default:
2782                throw shouldNotReachHere();
2783        }
2784        frameState.push(kind, append(v));
2785    }
2786
2787    private void genNegateOp(Kind kind) {
2788        ValueNode x = frameState.pop(kind);
2789        frameState.push(kind, append(genNegateOp(x)));
2790    }
2791
2792    private void genShiftOp(Kind kind, int opcode) {
2793        ValueNode s = frameState.pop(Kind.Int);
2794        ValueNode x = frameState.pop(kind);
2795        ValueNode v;
2796        switch (opcode) {
2797            case ISHL:
2798            case LSHL:
2799                v = genLeftShift(x, s);
2800                break;
2801            case ISHR:
2802            case LSHR:
2803                v = genRightShift(x, s);
2804                break;
2805            case IUSHR:
2806            case LUSHR:
2807                v = genUnsignedRightShift(x, s);
2808                break;
2809            default:
2810                throw shouldNotReachHere();
2811        }
2812        frameState.push(kind, append(v));
2813    }
2814
2815    private void genLogicOp(Kind kind, int opcode) {
2816        ValueNode y = frameState.pop(kind);
2817        ValueNode x = frameState.pop(kind);
2818        ValueNode v;
2819        switch (opcode) {
2820            case IAND:
2821            case LAND:
2822                v = genAnd(x, y);
2823                break;
2824            case IOR:
2825            case LOR:
2826                v = genOr(x, y);
2827                break;
2828            case IXOR:
2829            case LXOR:
2830                v = genXor(x, y);
2831                break;
2832            default:
2833                throw shouldNotReachHere();
2834        }
2835        frameState.push(kind, append(v));
2836    }
2837
2838    private void genCompareOp(Kind kind, boolean isUnorderedLess) {
2839        ValueNode y = frameState.pop(kind);
2840        ValueNode x = frameState.pop(kind);
2841        frameState.push(Kind.Int, append(genNormalizeCompare(x, y, isUnorderedLess)));
2842    }
2843
2844    private void genFloatConvert(FloatConvert op, Kind from, Kind to) {
2845        ValueNode input = frameState.pop(from);
2846        frameState.push(to, append(genFloatConvert(op, input)));
2847    }
2848
2849    private void genSignExtend(Kind from, Kind to) {
2850        ValueNode input = frameState.pop(from);
2851        if (from != from.getStackKind()) {
2852            input = append(genNarrow(input, from.getBitCount()));
2853        }
2854        frameState.push(to, append(genSignExtend(input, to.getBitCount())));
2855    }
2856
2857    private void genZeroExtend(Kind from, Kind to) {
2858        ValueNode input = frameState.pop(from);
2859        if (from != from.getStackKind()) {
2860            input = append(genNarrow(input, from.getBitCount()));
2861        }
2862        frameState.push(to, append(genZeroExtend(input, to.getBitCount())));
2863    }
2864
2865    private void genNarrow(Kind from, Kind to) {
2866        ValueNode input = frameState.pop(from);
2867        frameState.push(to, append(genNarrow(input, to.getBitCount())));
2868    }
2869
2870    private void genIncrement() {
2871        int index = getStream().readLocalIndex();
2872        int delta = getStream().readIncrement();
2873        ValueNode x = frameState.loadLocal(index, Kind.Int);
2874        ValueNode y = appendConstant(JavaConstant.forInt(delta));
2875        frameState.storeLocal(index, Kind.Int, append(genIntegerAdd(x, y)));
2876    }
2877
2878    private void genIfZero(Condition cond) {
2879        ValueNode y = appendConstant(JavaConstant.INT_0);
2880        ValueNode x = frameState.pop(Kind.Int);
2881        genIf(x, cond, y);
2882    }
2883
2884    private void genIfNull(Condition cond) {
2885        ValueNode y = appendConstant(JavaConstant.NULL_POINTER);
2886        ValueNode x = frameState.pop(Kind.Object);
2887        genIf(x, cond, y);
2888    }
2889
2890    private void genIfSame(Kind kind, Condition cond) {
2891        ValueNode y = frameState.pop(kind);
2892        ValueNode x = frameState.pop(kind);
2893        genIf(x, cond, y);
2894    }
2895
2896    protected JavaType lookupType(int cpi, int bytecode) {
2897        maybeEagerlyResolve(cpi, bytecode);
2898        JavaType result = constantPool.lookupType(cpi, bytecode);
2899        assert !graphBuilderConfig.unresolvedIsError() || result instanceof ResolvedJavaType;
2900        return result;
2901    }
2902
2903    private JavaMethod lookupMethod(int cpi, int opcode) {
2904        maybeEagerlyResolve(cpi, opcode);
2905        JavaMethod result = constantPool.lookupMethod(cpi, opcode);
2906        /*
2907         * In general, one cannot assume that the declaring class being initialized is useful, since
2908         * the actual concrete receiver may be a different class (except for static calls). Also,
2909         * interfaces are initialized only under special circumstances, so that this assertion would
2910         * often fail for interface calls.
2911         */
2912        assert !graphBuilderConfig.unresolvedIsError() || (result instanceof ResolvedJavaMethod && (opcode != INVOKESTATIC || ((ResolvedJavaMethod) result).getDeclaringClass().isInitialized())) : result;
2913        return result;
2914    }
2915
2916    private JavaField lookupField(int cpi, int opcode) {
2917        maybeEagerlyResolve(cpi, opcode);
2918        JavaField result = constantPool.lookupField(cpi, opcode);
2919        if (graphBuilderConfig.eagerResolving()) {
2920            assert result instanceof ResolvedJavaField : "Not resolved: " + result;
2921            ResolvedJavaType declaringClass = ((ResolvedJavaField) result).getDeclaringClass();
2922            if (!declaringClass.isInitialized()) {
2923                assert declaringClass.isInterface() : "Declaring class not initialized but not an interface? " + declaringClass;
2924                declaringClass.initialize();
2925            }
2926        }
2927        assert !graphBuilderConfig.unresolvedIsError() || (result instanceof ResolvedJavaField && ((ResolvedJavaField) result).getDeclaringClass().isInitialized()) : result;
2928        return result;
2929    }
2930
2931    private Object lookupConstant(int cpi, int opcode) {
2932        maybeEagerlyResolve(cpi, opcode);
2933        Object result = constantPool.lookupConstant(cpi);
2934        assert !graphBuilderConfig.eagerResolving() || !(result instanceof JavaType) || (result instanceof ResolvedJavaType) : result;
2935        return result;
2936    }
2937
2938    private void maybeEagerlyResolve(int cpi, int bytecode) {
2939        if (graphBuilderConfig.eagerResolving() || intrinsicContext != null) {
2940            constantPool.loadReferencedType(cpi, bytecode);
2941        }
2942    }
2943
2944    private JavaTypeProfile getProfileForTypeCheck(ResolvedJavaType type) {
2945        if (parsingIntrinsic() || profilingInfo == null || !optimisticOpts.useTypeCheckHints() || type.isLeaf()) {
2946            return null;
2947        } else {
2948            return profilingInfo.getTypeProfile(bci());
2949        }
2950    }
2951
2952    private void genCheckCast() {
2953        int cpi = getStream().readCPI();
2954        JavaType type = lookupType(cpi, CHECKCAST);
2955        ValueNode object = frameState.pop(Kind.Object);
2956
2957        if (!(type instanceof ResolvedJavaType)) {
2958            handleUnresolvedCheckCast(type, object);
2959            return;
2960        }
2961        ResolvedJavaType resolvedType = (ResolvedJavaType) type;
2962        JavaTypeProfile profile = getProfileForTypeCheck(resolvedType);
2963
2964        for (NodePlugin plugin : graphBuilderConfig.getPlugins().getNodePlugins()) {
2965            if (plugin.handleCheckCast(this, object, resolvedType, profile)) {
2966                return;
2967            }
2968        }
2969
2970        ValueNode checkCastNode = null;
2971        if (profile != null) {
2972            if (profile.getNullSeen().isFalse()) {
2973                object = appendNullCheck(object);
2974                ResolvedJavaType singleType = profile.asSingleType();
2975                if (singleType != null) {
2976                    LogicNode typeCheck = append(TypeCheckNode.create(singleType, object));
2977                    if (typeCheck.isTautology()) {
2978                        checkCastNode = object;
2979                    } else {
2980                        FixedGuardNode fixedGuard = append(new FixedGuardNode(typeCheck, DeoptimizationReason.TypeCheckedInliningViolated, DeoptimizationAction.InvalidateReprofile, false));
2981                        checkCastNode = append(new PiNode(object, StampFactory.exactNonNull(singleType), fixedGuard));
2982                    }
2983                }
2984            }
2985        }
2986        if (checkCastNode == null) {
2987            checkCastNode = append(createCheckCast(resolvedType, object, profile, false));
2988        }
2989        frameState.push(Kind.Object, checkCastNode);
2990    }
2991
2992    private ValueNode appendNullCheck(ValueNode object) {
2993        if (object.stamp() instanceof AbstractPointerStamp) {
2994            AbstractPointerStamp stamp = (AbstractPointerStamp) object.stamp();
2995            if (stamp.nonNull()) {
2996                return object;
2997            }
2998        }
2999
3000        IsNullNode isNull = append(new IsNullNode(object));
3001        FixedGuardNode fixedGuard = append(new FixedGuardNode(isNull, DeoptimizationReason.NullCheckException, DeoptimizationAction.InvalidateReprofile, true));
3002        return append(new PiNode(object, object.stamp().join(StampFactory.objectNonNull()), fixedGuard));
3003    }
3004
3005    private void genInstanceOf() {
3006        int cpi = getStream().readCPI();
3007        JavaType type = lookupType(cpi, INSTANCEOF);
3008        ValueNode object = frameState.pop(Kind.Object);
3009
3010        if (!(type instanceof ResolvedJavaType)) {
3011            handleUnresolvedInstanceOf(type, object);
3012            return;
3013        }
3014        ResolvedJavaType resolvedType = (ResolvedJavaType) type;
3015        JavaTypeProfile profile = getProfileForTypeCheck(resolvedType);
3016
3017        for (NodePlugin plugin : graphBuilderConfig.getPlugins().getNodePlugins()) {
3018            if (plugin.handleInstanceOf(this, object, resolvedType, profile)) {
3019                return;
3020            }
3021        }
3022
3023        ValueNode instanceOfNode = null;
3024        if (profile != null) {
3025            if (profile.getNullSeen().isFalse()) {
3026                object = appendNullCheck(object);
3027                ResolvedJavaType singleType = profile.asSingleType();
3028                if (singleType != null) {
3029                    LogicNode typeCheck = append(TypeCheckNode.create(singleType, object));
3030                    if (!typeCheck.isTautology()) {
3031                        append(new FixedGuardNode(typeCheck, DeoptimizationReason.TypeCheckedInliningViolated, DeoptimizationAction.InvalidateReprofile));
3032                    }
3033                    instanceOfNode = LogicConstantNode.forBoolean(resolvedType.isAssignableFrom(singleType));
3034                }
3035            }
3036        }
3037        if (instanceOfNode == null) {
3038            instanceOfNode = createInstanceOf(resolvedType, object, profile);
3039        }
3040        frameState.push(Kind.Int, append(genConditional(genUnique(instanceOfNode))));
3041    }
3042
3043    void genNewInstance(int cpi) {
3044        JavaType type = lookupType(cpi, NEW);
3045
3046        if (!(type instanceof ResolvedJavaType) || !((ResolvedJavaType) type).isInitialized()) {
3047            handleUnresolvedNewInstance(type);
3048            return;
3049        }
3050        ResolvedJavaType resolvedType = (ResolvedJavaType) type;
3051
3052        ResolvedJavaType[] skippedExceptionTypes = this.graphBuilderConfig.getSkippedExceptionTypes();
3053        if (skippedExceptionTypes != null) {
3054            for (ResolvedJavaType exceptionType : skippedExceptionTypes) {
3055                if (exceptionType.isAssignableFrom(resolvedType)) {
3056                    append(new DeoptimizeNode(DeoptimizationAction.None, TransferToInterpreter));
3057                    return;
3058                }
3059            }
3060        }
3061
3062        frameState.push(Kind.Object, append(createNewInstance(resolvedType, true)));
3063    }
3064
3065    /**
3066     * Gets the kind of array elements for the array type code that appears in a
3067     * {@link Bytecodes#NEWARRAY} bytecode.
3068     *
3069     * @param code the array type code
3070     * @return the kind from the array type code
3071     */
3072    private static Class<?> arrayTypeCodeToClass(int code) {
3073        switch (code) {
3074            case 4:
3075                return boolean.class;
3076            case 5:
3077                return char.class;
3078            case 6:
3079                return float.class;
3080            case 7:
3081                return double.class;
3082            case 8:
3083                return byte.class;
3084            case 9:
3085                return short.class;
3086            case 10:
3087                return int.class;
3088            case 11:
3089                return long.class;
3090            default:
3091                throw new IllegalArgumentException("unknown array type code: " + code);
3092        }
3093    }
3094
3095    private void genNewPrimitiveArray(int typeCode) {
3096        ResolvedJavaType elementType = metaAccess.lookupJavaType(arrayTypeCodeToClass(typeCode));
3097        ValueNode length = frameState.pop(Kind.Int);
3098        frameState.push(Kind.Object, append(createNewArray(elementType, length, true)));
3099    }
3100
3101    private void genNewObjectArray(int cpi) {
3102        JavaType type = lookupType(cpi, ANEWARRAY);
3103        ValueNode length = frameState.pop(Kind.Int);
3104
3105        if (!(type instanceof ResolvedJavaType)) {
3106            handleUnresolvedNewObjectArray(type, length);
3107            return;
3108        }
3109        ResolvedJavaType resolvedType = (ResolvedJavaType) type;
3110
3111        frameState.push(Kind.Object, append(createNewArray(resolvedType, length, true)));
3112    }
3113
3114    private void genNewMultiArray(int cpi) {
3115        JavaType type = lookupType(cpi, MULTIANEWARRAY);
3116        int rank = getStream().readUByte(bci() + 3);
3117        List<ValueNode> dims = new ArrayList<>(Collections.nCopies(rank, null));
3118        for (int i = rank - 1; i >= 0; i--) {
3119            dims.set(i, frameState.pop(Kind.Int));
3120        }
3121
3122        if (!(type instanceof ResolvedJavaType)) {
3123            handleUnresolvedNewMultiArray(type, dims);
3124            return;
3125        }
3126        ResolvedJavaType resolvedType = (ResolvedJavaType) type;
3127
3128        frameState.push(Kind.Object, append(createNewMultiArray(resolvedType, dims)));
3129    }
3130
3131    private void genGetField(JavaField field) {
3132        ValueNode receiver = emitExplicitExceptions(frameState.pop(Kind.Object), null);
3133
3134        if (!(field instanceof ResolvedJavaField) || !((ResolvedJavaField) field).getDeclaringClass().isInitialized()) {
3135            handleUnresolvedLoadField(field, receiver);
3136            return;
3137        }
3138        ResolvedJavaField resolvedField = (ResolvedJavaField) field;
3139
3140        for (NodePlugin plugin : graphBuilderConfig.getPlugins().getNodePlugins()) {
3141            if (plugin.handleLoadField(this, receiver, resolvedField)) {
3142                return;
3143            }
3144        }
3145
3146        frameState.push(field.getKind(), append(genLoadField(receiver, resolvedField)));
3147    }
3148
3149    /**
3150     * @param receiver the receiver of an object based operation
3151     * @param index the index of an array based operation that is to be tested for out of bounds.
3152     *            This is null for a non-array operation.
3153     * @return the receiver value possibly modified to have a tighter stamp
3154     */
3155    protected ValueNode emitExplicitExceptions(ValueNode receiver, ValueNode index) {
3156        assert receiver != null;
3157        if (graphBuilderConfig.omitAllExceptionEdges() || profilingInfo == null ||
3158                        (optimisticOpts.useExceptionProbabilityForOperations() && profilingInfo.getExceptionSeen(bci()) == TriState.FALSE && !GraalOptions.StressExplicitExceptionCode.getValue())) {
3159            return receiver;
3160        }
3161
3162        ValueNode nonNullReceiver = emitExplicitNullCheck(receiver);
3163        if (index != null) {
3164            ValueNode length = append(genArrayLength(nonNullReceiver));
3165            emitExplicitBoundsCheck(index, length);
3166        }
3167        EXPLICIT_EXCEPTIONS.increment();
3168        return nonNullReceiver;
3169    }
3170
3171    private void genPutField(JavaField field) {
3172        ValueNode value = frameState.pop(field.getKind());
3173        ValueNode receiver = emitExplicitExceptions(frameState.pop(Kind.Object), null);
3174
3175        if (!(field instanceof ResolvedJavaField) || !((ResolvedJavaField) field).getDeclaringClass().isInitialized()) {
3176            handleUnresolvedStoreField(field, value, receiver);
3177            return;
3178        }
3179        ResolvedJavaField resolvedField = (ResolvedJavaField) field;
3180
3181        for (NodePlugin plugin : graphBuilderConfig.getPlugins().getNodePlugins()) {
3182            if (plugin.handleStoreField(this, receiver, resolvedField, value)) {
3183                return;
3184            }
3185        }
3186
3187        genStoreField(receiver, resolvedField, value);
3188    }
3189
3190    private void genGetStatic(JavaField field) {
3191        if (!(field instanceof ResolvedJavaField) || !((ResolvedJavaType) field.getDeclaringClass()).isInitialized()) {
3192            handleUnresolvedLoadField(field, null);
3193            return;
3194        }
3195        ResolvedJavaField resolvedField = (ResolvedJavaField) field;
3196
3197        /*
3198         * Javac does not allow use of "$assertionsDisabled" for a field name but Eclipse does, in
3199         * which case a suffix is added to the generated field.
3200         */
3201        if ((parsingIntrinsic() || graphBuilderConfig.omitAssertions()) && resolvedField.isSynthetic() && resolvedField.getName().startsWith("$assertionsDisabled")) {
3202            frameState.push(field.getKind(), ConstantNode.forBoolean(true, graph));
3203            return;
3204        }
3205
3206        for (NodePlugin plugin : graphBuilderConfig.getPlugins().getNodePlugins()) {
3207            if (plugin.handleLoadStaticField(this, resolvedField)) {
3208                return;
3209            }
3210        }
3211
3212        frameState.push(field.getKind(), append(genLoadField(null, resolvedField)));
3213    }
3214
3215    private void genPutStatic(JavaField field) {
3216        ValueNode value = frameState.pop(field.getKind());
3217        if (!(field instanceof ResolvedJavaField) || !((ResolvedJavaType) field.getDeclaringClass()).isInitialized()) {
3218            handleUnresolvedStoreField(field, value, null);
3219            return;
3220        }
3221        ResolvedJavaField resolvedField = (ResolvedJavaField) field;
3222
3223        for (NodePlugin plugin : graphBuilderConfig.getPlugins().getNodePlugins()) {
3224            if (plugin.handleStoreStaticField(this, resolvedField, value)) {
3225                return;
3226            }
3227        }
3228
3229        genStoreField(null, resolvedField, value);
3230    }
3231
3232    private double[] switchProbability(int numberOfCases, int bci) {
3233        double[] prob = (profilingInfo == null ? null : profilingInfo.getSwitchProbabilities(bci));
3234        if (prob != null) {
3235            assert prob.length == numberOfCases;
3236        } else {
3237            Debug.log("Missing probability (switch) in %s at bci %d", method, bci);
3238            prob = new double[numberOfCases];
3239            for (int i = 0; i < numberOfCases; i++) {
3240                prob[i] = 1.0d / numberOfCases;
3241            }
3242        }
3243        assert allPositive(prob);
3244        return prob;
3245    }
3246
3247    private static boolean allPositive(double[] a) {
3248        for (double d : a) {
3249            if (d < 0) {
3250                return false;
3251            }
3252        }
3253        return true;
3254    }
3255
3256    static class SuccessorInfo {
3257        final int blockIndex;
3258        int actualIndex;
3259
3260        public SuccessorInfo(int blockSuccessorIndex) {
3261            this.blockIndex = blockSuccessorIndex;
3262            actualIndex = -1;
3263        }
3264    }
3265
3266    private void genSwitch(BytecodeSwitch bs) {
3267        int bci = bci();
3268        ValueNode value = frameState.pop(Kind.Int);
3269
3270        int nofCases = bs.numberOfCases();
3271        double[] keyProbabilities = switchProbability(nofCases + 1, bci);
3272
3273        Map<Integer, SuccessorInfo> bciToBlockSuccessorIndex = new HashMap<>();
3274        for (int i = 0; i < currentBlock.getSuccessorCount(); i++) {
3275            assert !bciToBlockSuccessorIndex.containsKey(currentBlock.getSuccessor(i).startBci);
3276            if (!bciToBlockSuccessorIndex.containsKey(currentBlock.getSuccessor(i).startBci)) {
3277                bciToBlockSuccessorIndex.put(currentBlock.getSuccessor(i).startBci, new SuccessorInfo(i));
3278            }
3279        }
3280
3281        ArrayList<BciBlock> actualSuccessors = new ArrayList<>();
3282        int[] keys = new int[nofCases];
3283        int[] keySuccessors = new int[nofCases + 1];
3284        int deoptSuccessorIndex = -1;
3285        int nextSuccessorIndex = 0;
3286        boolean constantValue = value.isConstant();
3287        for (int i = 0; i < nofCases + 1; i++) {
3288            if (i < nofCases) {
3289                keys[i] = bs.keyAt(i);
3290            }
3291
3292            if (!constantValue && isNeverExecutedCode(keyProbabilities[i])) {
3293                if (deoptSuccessorIndex < 0) {
3294                    deoptSuccessorIndex = nextSuccessorIndex++;
3295                    actualSuccessors.add(null);
3296                }
3297                keySuccessors[i] = deoptSuccessorIndex;
3298            } else {
3299                int targetBci = i >= nofCases ? bs.defaultTarget() : bs.targetAt(i);
3300                SuccessorInfo info = bciToBlockSuccessorIndex.get(targetBci);
3301                if (info.actualIndex < 0) {
3302                    info.actualIndex = nextSuccessorIndex++;
3303                    actualSuccessors.add(currentBlock.getSuccessor(info.blockIndex));
3304                }
3305                keySuccessors[i] = info.actualIndex;
3306            }
3307        }
3308
3309        genIntegerSwitch(value, actualSuccessors, keys, keyProbabilities, keySuccessors);
3310
3311    }
3312
3313    protected boolean isNeverExecutedCode(double probability) {
3314        return probability == 0 && optimisticOpts.removeNeverExecutedCode();
3315    }
3316
3317    protected double branchProbability() {
3318        if (profilingInfo == null) {
3319            return 0.5;
3320        }
3321        assert assertAtIfBytecode();
3322        double probability = profilingInfo.getBranchTakenProbability(bci());
3323        if (probability < 0) {
3324            assert probability == -1 : "invalid probability";
3325            Debug.log("missing probability in %s at bci %d", method, bci());
3326            probability = 0.5;
3327        }
3328
3329        if (!optimisticOpts.removeNeverExecutedCode()) {
3330            if (probability == 0) {
3331                probability = 0.0000001;
3332            } else if (probability == 1) {
3333                probability = 0.999999;
3334            }
3335        }
3336        return probability;
3337    }
3338
3339    private boolean assertAtIfBytecode() {
3340        int bytecode = stream.currentBC();
3341        switch (bytecode) {
3342            case IFEQ:
3343            case IFNE:
3344            case IFLT:
3345            case IFGE:
3346            case IFGT:
3347            case IFLE:
3348            case IF_ICMPEQ:
3349            case IF_ICMPNE:
3350            case IF_ICMPLT:
3351            case IF_ICMPGE:
3352            case IF_ICMPGT:
3353            case IF_ICMPLE:
3354            case IF_ACMPEQ:
3355            case IF_ACMPNE:
3356            case IFNULL:
3357            case IFNONNULL:
3358                return true;
3359        }
3360        assert false : String.format("%x is not an if bytecode", bytecode);
3361        return true;
3362    }
3363
3364    public final void processBytecode(int bci, int opcode) {
3365        int cpi;
3366
3367        // @formatter:off
3368        // Checkstyle: stop
3369        switch (opcode) {
3370            case NOP            : /* nothing to do */ break;
3371            case ACONST_NULL    : frameState.push(Kind.Object, appendConstant(JavaConstant.NULL_POINTER)); break;
3372            case ICONST_M1      : // fall through
3373            case ICONST_0       : // fall through
3374            case ICONST_1       : // fall through
3375            case ICONST_2       : // fall through
3376            case ICONST_3       : // fall through
3377            case ICONST_4       : // fall through
3378            case ICONST_5       : frameState.push(Kind.Int, appendConstant(JavaConstant.forInt(opcode - ICONST_0))); break;
3379            case LCONST_0       : // fall through
3380            case LCONST_1       : frameState.push(Kind.Long, appendConstant(JavaConstant.forLong(opcode - LCONST_0))); break;
3381            case FCONST_0       : // fall through
3382            case FCONST_1       : // fall through
3383            case FCONST_2       : frameState.push(Kind.Float, appendConstant(JavaConstant.forFloat(opcode - FCONST_0))); break;
3384            case DCONST_0       : // fall through
3385            case DCONST_1       : frameState.push(Kind.Double, appendConstant(JavaConstant.forDouble(opcode - DCONST_0))); break;
3386            case BIPUSH         : frameState.push(Kind.Int, appendConstant(JavaConstant.forInt(stream.readByte()))); break;
3387            case SIPUSH         : frameState.push(Kind.Int, appendConstant(JavaConstant.forInt(stream.readShort()))); break;
3388            case LDC            : // fall through
3389            case LDC_W          : // fall through
3390            case LDC2_W         : genLoadConstant(stream.readCPI(), opcode); break;
3391            case ILOAD          : loadLocal(stream.readLocalIndex(), Kind.Int); break;
3392            case LLOAD          : loadLocal(stream.readLocalIndex(), Kind.Long); break;
3393            case FLOAD          : loadLocal(stream.readLocalIndex(), Kind.Float); break;
3394            case DLOAD          : loadLocal(stream.readLocalIndex(), Kind.Double); break;
3395            case ALOAD          : loadLocal(stream.readLocalIndex(), Kind.Object); break;
3396            case ILOAD_0        : // fall through
3397            case ILOAD_1        : // fall through
3398            case ILOAD_2        : // fall through
3399            case ILOAD_3        : loadLocal(opcode - ILOAD_0, Kind.Int); break;
3400            case LLOAD_0        : // fall through
3401            case LLOAD_1        : // fall through
3402            case LLOAD_2        : // fall through
3403            case LLOAD_3        : loadLocal(opcode - LLOAD_0, Kind.Long); break;
3404            case FLOAD_0        : // fall through
3405            case FLOAD_1        : // fall through
3406            case FLOAD_2        : // fall through
3407            case FLOAD_3        : loadLocal(opcode - FLOAD_0, Kind.Float); break;
3408            case DLOAD_0        : // fall through
3409            case DLOAD_1        : // fall through
3410            case DLOAD_2        : // fall through
3411            case DLOAD_3        : loadLocal(opcode - DLOAD_0, Kind.Double); break;
3412            case ALOAD_0        : // fall through
3413            case ALOAD_1        : // fall through
3414            case ALOAD_2        : // fall through
3415            case ALOAD_3        : loadLocal(opcode - ALOAD_0, Kind.Object); break;
3416            case IALOAD         : genLoadIndexed(Kind.Int   ); break;
3417            case LALOAD         : genLoadIndexed(Kind.Long  ); break;
3418            case FALOAD         : genLoadIndexed(Kind.Float ); break;
3419            case DALOAD         : genLoadIndexed(Kind.Double); break;
3420            case AALOAD         : genLoadIndexed(Kind.Object); break;
3421            case BALOAD         : genLoadIndexed(Kind.Byte  ); break;
3422            case CALOAD         : genLoadIndexed(Kind.Char  ); break;
3423            case SALOAD         : genLoadIndexed(Kind.Short ); break;
3424            case ISTORE         : storeLocal(Kind.Int, stream.readLocalIndex()); break;
3425            case LSTORE         : storeLocal(Kind.Long, stream.readLocalIndex()); break;
3426            case FSTORE         : storeLocal(Kind.Float, stream.readLocalIndex()); break;
3427            case DSTORE         : storeLocal(Kind.Double, stream.readLocalIndex()); break;
3428            case ASTORE         : storeLocal(Kind.Object, stream.readLocalIndex()); break;
3429            case ISTORE_0       : // fall through
3430            case ISTORE_1       : // fall through
3431            case ISTORE_2       : // fall through
3432            case ISTORE_3       : storeLocal(Kind.Int, opcode - ISTORE_0); break;
3433            case LSTORE_0       : // fall through
3434            case LSTORE_1       : // fall through
3435            case LSTORE_2       : // fall through
3436            case LSTORE_3       : storeLocal(Kind.Long, opcode - LSTORE_0); break;
3437            case FSTORE_0       : // fall through
3438            case FSTORE_1       : // fall through
3439            case FSTORE_2       : // fall through
3440            case FSTORE_3       : storeLocal(Kind.Float, opcode - FSTORE_0); break;
3441            case DSTORE_0       : // fall through
3442            case DSTORE_1       : // fall through
3443            case DSTORE_2       : // fall through
3444            case DSTORE_3       : storeLocal(Kind.Double, opcode - DSTORE_0); break;
3445            case ASTORE_0       : // fall through
3446            case ASTORE_1       : // fall through
3447            case ASTORE_2       : // fall through
3448            case ASTORE_3       : storeLocal(Kind.Object, opcode - ASTORE_0); break;
3449            case IASTORE        : genStoreIndexed(Kind.Int   ); break;
3450            case LASTORE        : genStoreIndexed(Kind.Long  ); break;
3451            case FASTORE        : genStoreIndexed(Kind.Float ); break;
3452            case DASTORE        : genStoreIndexed(Kind.Double); break;
3453            case AASTORE        : genStoreIndexed(Kind.Object); break;
3454            case BASTORE        : genStoreIndexed(Kind.Byte  ); break;
3455            case CASTORE        : genStoreIndexed(Kind.Char  ); break;
3456            case SASTORE        : genStoreIndexed(Kind.Short ); break;
3457            case POP            : // fall through
3458            case POP2           : // fall through
3459            case DUP            : // fall through
3460            case DUP_X1         : // fall through
3461            case DUP_X2         : // fall through
3462            case DUP2           : // fall through
3463            case DUP2_X1        : // fall through
3464            case DUP2_X2        : // fall through
3465            case SWAP           : frameState.stackOp(opcode); break;
3466            case IADD           : // fall through
3467            case ISUB           : // fall through
3468            case IMUL           : genArithmeticOp(Kind.Int, opcode); break;
3469            case IDIV           : // fall through
3470            case IREM           : genIntegerDivOp(Kind.Int, opcode); break;
3471            case LADD           : // fall through
3472            case LSUB           : // fall through
3473            case LMUL           : genArithmeticOp(Kind.Long, opcode); break;
3474            case LDIV           : // fall through
3475            case LREM           : genIntegerDivOp(Kind.Long, opcode); break;
3476            case FADD           : // fall through
3477            case FSUB           : // fall through
3478            case FMUL           : // fall through
3479            case FDIV           : // fall through
3480            case FREM           : genArithmeticOp(Kind.Float, opcode); break;
3481            case DADD           : // fall through
3482            case DSUB           : // fall through
3483            case DMUL           : // fall through
3484            case DDIV           : // fall through
3485            case DREM           : genArithmeticOp(Kind.Double, opcode); break;
3486            case INEG           : genNegateOp(Kind.Int); break;
3487            case LNEG           : genNegateOp(Kind.Long); break;
3488            case FNEG           : genNegateOp(Kind.Float); break;
3489            case DNEG           : genNegateOp(Kind.Double); break;
3490            case ISHL           : // fall through
3491            case ISHR           : // fall through
3492            case IUSHR          : genShiftOp(Kind.Int, opcode); break;
3493            case IAND           : // fall through
3494            case IOR            : // fall through
3495            case IXOR           : genLogicOp(Kind.Int, opcode); break;
3496            case LSHL           : // fall through
3497            case LSHR           : // fall through
3498            case LUSHR          : genShiftOp(Kind.Long, opcode); break;
3499            case LAND           : // fall through
3500            case LOR            : // fall through
3501            case LXOR           : genLogicOp(Kind.Long, opcode); break;
3502            case IINC           : genIncrement(); break;
3503            case I2F            : genFloatConvert(FloatConvert.I2F, Kind.Int, Kind.Float); break;
3504            case I2D            : genFloatConvert(FloatConvert.I2D, Kind.Int, Kind.Double); break;
3505            case L2F            : genFloatConvert(FloatConvert.L2F, Kind.Long, Kind.Float); break;
3506            case L2D            : genFloatConvert(FloatConvert.L2D, Kind.Long, Kind.Double); break;
3507            case F2I            : genFloatConvert(FloatConvert.F2I, Kind.Float, Kind.Int); break;
3508            case F2L            : genFloatConvert(FloatConvert.F2L, Kind.Float, Kind.Long); break;
3509            case F2D            : genFloatConvert(FloatConvert.F2D, Kind.Float, Kind.Double); break;
3510            case D2I            : genFloatConvert(FloatConvert.D2I, Kind.Double, Kind.Int); break;
3511            case D2L            : genFloatConvert(FloatConvert.D2L, Kind.Double, Kind.Long); break;
3512            case D2F            : genFloatConvert(FloatConvert.D2F, Kind.Double, Kind.Float); break;
3513            case L2I            : genNarrow(Kind.Long, Kind.Int); break;
3514            case I2L            : genSignExtend(Kind.Int, Kind.Long); break;
3515            case I2B            : genSignExtend(Kind.Byte, Kind.Int); break;
3516            case I2S            : genSignExtend(Kind.Short, Kind.Int); break;
3517            case I2C            : genZeroExtend(Kind.Char, Kind.Int); break;
3518            case LCMP           : genCompareOp(Kind.Long, false); break;
3519            case FCMPL          : genCompareOp(Kind.Float, true); break;
3520            case FCMPG          : genCompareOp(Kind.Float, false); break;
3521            case DCMPL          : genCompareOp(Kind.Double, true); break;
3522            case DCMPG          : genCompareOp(Kind.Double, false); break;
3523            case IFEQ           : genIfZero(Condition.EQ); break;
3524            case IFNE           : genIfZero(Condition.NE); break;
3525            case IFLT           : genIfZero(Condition.LT); break;
3526            case IFGE           : genIfZero(Condition.GE); break;
3527            case IFGT           : genIfZero(Condition.GT); break;
3528            case IFLE           : genIfZero(Condition.LE); break;
3529            case IF_ICMPEQ      : genIfSame(Kind.Int, Condition.EQ); break;
3530            case IF_ICMPNE      : genIfSame(Kind.Int, Condition.NE); break;
3531            case IF_ICMPLT      : genIfSame(Kind.Int, Condition.LT); break;
3532            case IF_ICMPGE      : genIfSame(Kind.Int, Condition.GE); break;
3533            case IF_ICMPGT      : genIfSame(Kind.Int, Condition.GT); break;
3534            case IF_ICMPLE      : genIfSame(Kind.Int, Condition.LE); break;
3535            case IF_ACMPEQ      : genIfSame(Kind.Object, Condition.EQ); break;
3536            case IF_ACMPNE      : genIfSame(Kind.Object, Condition.NE); break;
3537            case GOTO           : genGoto(); break;
3538            case JSR            : genJsr(stream.readBranchDest()); break;
3539            case RET            : genRet(stream.readLocalIndex()); break;
3540            case TABLESWITCH    : genSwitch(new BytecodeTableSwitch(getStream(), bci())); break;
3541            case LOOKUPSWITCH   : genSwitch(new BytecodeLookupSwitch(getStream(), bci())); break;
3542            case IRETURN        : genReturn(frameState.pop(Kind.Int), Kind.Int); break;
3543            case LRETURN        : genReturn(frameState.pop(Kind.Long), Kind.Long); break;
3544            case FRETURN        : genReturn(frameState.pop(Kind.Float), Kind.Float); break;
3545            case DRETURN        : genReturn(frameState.pop(Kind.Double), Kind.Double); break;
3546            case ARETURN        : genReturn(frameState.pop(Kind.Object), Kind.Object); break;
3547            case RETURN         : genReturn(null, Kind.Void); break;
3548            case GETSTATIC      : cpi = stream.readCPI(); genGetStatic(lookupField(cpi, opcode)); break;
3549            case PUTSTATIC      : cpi = stream.readCPI(); genPutStatic(lookupField(cpi, opcode)); break;
3550            case GETFIELD       : cpi = stream.readCPI(); genGetField(lookupField(cpi, opcode)); break;
3551            case PUTFIELD       : cpi = stream.readCPI(); genPutField(lookupField(cpi, opcode)); break;
3552            case INVOKEVIRTUAL  : cpi = stream.readCPI(); genInvokeVirtual(lookupMethod(cpi, opcode)); break;
3553            case INVOKESPECIAL  : cpi = stream.readCPI(); genInvokeSpecial(lookupMethod(cpi, opcode)); break;
3554            case INVOKESTATIC   : cpi = stream.readCPI(); genInvokeStatic(lookupMethod(cpi, opcode)); break;
3555            case INVOKEINTERFACE: cpi = stream.readCPI(); genInvokeInterface(lookupMethod(cpi, opcode)); break;
3556            case INVOKEDYNAMIC  : cpi = stream.readCPI4(); genInvokeDynamic(lookupMethod(cpi, opcode)); break;
3557            case NEW            : genNewInstance(stream.readCPI()); break;
3558            case NEWARRAY       : genNewPrimitiveArray(stream.readLocalIndex()); break;
3559            case ANEWARRAY      : genNewObjectArray(stream.readCPI()); break;
3560            case ARRAYLENGTH    : genArrayLength(); break;
3561            case ATHROW         : genThrow(); break;
3562            case CHECKCAST      : genCheckCast(); break;
3563            case INSTANCEOF     : genInstanceOf(); break;
3564            case MONITORENTER   : genMonitorEnter(frameState.pop(Kind.Object), stream.nextBCI()); break;
3565            case MONITOREXIT    : genMonitorExit(frameState.pop(Kind.Object), null, stream.nextBCI()); break;
3566            case MULTIANEWARRAY : genNewMultiArray(stream.readCPI()); break;
3567            case IFNULL         : genIfNull(Condition.EQ); break;
3568            case IFNONNULL      : genIfNull(Condition.NE); break;
3569            case GOTO_W         : genGoto(); break;
3570            case JSR_W          : genJsr(stream.readBranchDest()); break;
3571            case BREAKPOINT     : throw new BailoutException("concurrent setting of breakpoint");
3572            default             : throw new BailoutException("Unsupported opcode %d (%s) [bci=%d]", opcode, nameOf(opcode), bci);
3573        }
3574        // @formatter:on
3575        // Checkstyle: resume
3576    }
3577
3578    private void genArrayLength() {
3579        frameState.push(Kind.Int, append(genArrayLength(frameState.pop(Kind.Object))));
3580    }
3581
3582    public ResolvedJavaMethod getMethod() {
3583        return method;
3584    }
3585
3586    public FrameStateBuilder getFrameStateBuilder() {
3587        return frameState;
3588    }
3589
3590    protected boolean traceInstruction(int bci, int opcode, boolean blockStart) {
3591        if (Debug.isEnabled() && Options.TraceBytecodeParserLevel.getValue() >= TRACELEVEL_INSTRUCTIONS && Debug.isLogEnabled()) {
3592            traceInstructionHelper(bci, opcode, blockStart);
3593        }
3594        return true;
3595    }
3596
3597    private void traceInstructionHelper(int bci, int opcode, boolean blockStart) {
3598        StringBuilder sb = new StringBuilder(40);
3599        sb.append(blockStart ? '+' : '|');
3600        if (bci < 10) {
3601            sb.append("  ");
3602        } else if (bci < 100) {
3603            sb.append(' ');
3604        }
3605        sb.append(bci).append(": ").append(Bytecodes.nameOf(opcode));
3606        for (int i = bci + 1; i < stream.nextBCI(); ++i) {
3607            sb.append(' ').append(stream.readUByte(i));
3608        }
3609        if (!currentBlock.getJsrScope().isEmpty()) {
3610            sb.append(' ').append(currentBlock.getJsrScope());
3611        }
3612        Debug.log("%s", sb);
3613    }
3614
3615    public boolean parsingIntrinsic() {
3616        return intrinsicContext != null;
3617    }
3618
3619    public BytecodeParser getNonIntrinsicAncestor() {
3620        BytecodeParser ancestor = parent;
3621        while (ancestor != null && ancestor.parsingIntrinsic()) {
3622            ancestor = ancestor.parent;
3623        }
3624        return ancestor;
3625    }
3626
3627    static String nSpaces(int n) {
3628        return n == 0 ? "" : format("%" + n + "s", "");
3629    }
3630
3631    @SuppressWarnings("all")
3632    private static boolean assertionsEnabled() {
3633        boolean assertionsEnabled = false;
3634        assert assertionsEnabled = true;
3635        return assertionsEnabled;
3636    }
3637}