# HG changeset patch
# User Christian Haeubl <haeubl@ssw.jku.at>
# Date 1352988641 -3600
# Node ID 0d7dfa5b79e8d70801ca4e4c453259263ef81999
# Parent  8c5333c80cfd55589935ba68b1cb132143c9b1a6
merged inlining and intrinsification phases
some optimizations for Integer- and TypeSwitch
added iterator to do the inlining in control-flow order

diff -r 8c5333c80cfd -r 0d7dfa5b79e8 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Thu Nov 15 11:40:50 2012 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Thu Nov 15 15:10:41 2012 +0100
@@ -118,10 +118,6 @@
             new CanonicalizerPhase(target, runtime, assumptions).apply(graph);
         }
 
-        if (GraalOptions.Intrinsify) {
-            new IntrinsificationPhase(runtime).apply(graph);
-        }
-
         if (GraalOptions.Inline && !plan.isPhaseDisabled(InliningPhase.class)) {
             new InliningPhase(target, runtime, null, assumptions, cache, plan, optimisticOpts).apply(graph);
 
diff -r 8c5333c80cfd -r 0d7dfa5b79e8 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java	Thu Nov 15 11:40:50 2012 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/gen/LIRGenerator.java	Thu Nov 15 15:10:41 2012 +0100
@@ -841,16 +841,15 @@
         } else {
             Variable value = load(operand(x.value()));
             LabelRef defaultTarget = x.defaultSuccessor() == null ? null : getLIRBlock(x.defaultSuccessor());
-            if (value.getKind() == Kind.Object || keyCount < GraalOptions.SequentialSwitchLimit) {
+            if (value.getKind() == Kind.Object) {
                 // only a few entries
                 emitSequentialSwitch(x, value, defaultTarget);
             } else {
                 long valueRange = x.keyAt(keyCount - 1).asLong() - x.keyAt(0).asLong() + 1;
                 int switchRangeCount = switchRangeCount(x);
-                int rangeDensity = keyCount / switchRangeCount;
-                if (rangeDensity >= GraalOptions.RangeTestsSwitchDensity) {
-                    emitSwitchRanges(x, switchRangeCount, value, defaultTarget);
-                } else if (keyCount / (double) valueRange >= GraalOptions.MinTableSwitchDensity) {
+                if (switchRangeCount == 0) {
+                    emitJump(getLIRBlock(x.defaultSuccessor()), null);
+                } else if (switchRangeCount >= GraalOptions.MinimumJumpTableSize && keyCount / (double) valueRange >= GraalOptions.MinTableSwitchDensity) {
                     int minValue = x.keyAt(0).asInt();
                     assert valueRange < Integer.MAX_VALUE;
                     LabelRef[] targets = new LabelRef[(int) valueRange];
@@ -861,6 +860,8 @@
                         targets[x.keyAt(i).asInt() - minValue] = getLIRBlock(x.keySuccessor(i));
                     }
                     emitTableSwitch(minValue, defaultTarget, targets, value);
+                } else if (keyCount / switchRangeCount >= GraalOptions.RangeTestsSwitchDensity) {
+                    emitSwitchRanges(x, switchRangeCount, value, defaultTarget);
                 } else {
                     emitSequentialSwitch(x, value, defaultTarget);
                 }
@@ -891,27 +892,26 @@
 
     private static int switchRangeCount(SwitchNode x) {
         int keyCount = x.keyCount();
-        int i = 0;
-        while (i < keyCount && x.keySuccessorIndex(i) == x.defaultSuccessorIndex()) {
-            i++;
+        int switchRangeCount = 0;
+        int defaultSux = x.defaultSuccessorIndex();
+
+        int key = x.keyAt(0).asInt();
+        int sux = x.keySuccessorIndex(0);
+        for (int i = 0; i < keyCount; i++) {
+            int newKey = x.keyAt(i).asInt();
+            int newSux = x.keySuccessorIndex(i);
+            if (newSux != defaultSux && (newKey != key + 1 || sux != newSux)) {
+                switchRangeCount++;
+            }
+            key = newKey;
+            sux = newSux;
         }
-        if (i == keyCount) {
-            return 0;
-        } else {
-            int switchRangeCount = 1;
-            i++;
-            for (; i < keyCount; i++) {
-                if (x.keySuccessorIndex(i) != x.defaultSuccessorIndex()) {
-                    if (x.keyAt(i).asInt() != x.keyAt(i - 1).asInt() + 1 || x.keySuccessorIndex(i) != x.keySuccessorIndex(i - 1)) {
-                        switchRangeCount++;
-                    }
-                }
-            }
-            return switchRangeCount;
-        }
+        return switchRangeCount;
     }
 
     private void emitSwitchRanges(SwitchNode x, int switchRangeCount, Variable keyValue, LabelRef defaultTarget) {
+        assert switchRangeCount >= 1 : "switch ranges should not be used for emitting only the default case";
+
         int[] lowKeys = new int[switchRangeCount];
         int[] highKeys = new int[switchRangeCount];
         LabelRef[] targets = new LabelRef[switchRangeCount];
@@ -919,40 +919,28 @@
         int keyCount = x.keyCount();
         int defaultSuccessor = x.defaultSuccessorIndex();
 
-        int current = 0;
-        int i = 0;
-        while (i < keyCount && x.keySuccessorIndex(i) == x.defaultSuccessorIndex()) {
-            i++;
+        int current = -1;
+        int key = -1;
+        int successor = -1;
+        for (int i = 0; i < keyCount; i++) {
+            int newSuccessor = x.keySuccessorIndex(i);
+            int newKey = x.keyAt(i).asInt();
+            if (newSuccessor != defaultSuccessor) {
+                if (key + 1 == newKey && successor == newSuccessor) {
+                    // still in same range
+                    highKeys[current] = newKey;
+                } else {
+                    current++;
+                    lowKeys[current] = newKey;
+                    highKeys[current] = newKey;
+                    targets[current] = getLIRBlock(x.blockSuccessor(newSuccessor));
+                }
+            }
+            key = newKey;
+            successor = newSuccessor;
         }
-        if (i == keyCount) {
-            emitJump(defaultTarget, null);
-        } else {
-            int key = x.keyAt(i).asInt();
-            int successor = x.keySuccessorIndex(i);
-            lowKeys[current] = key;
-            highKeys[current] = key;
-            targets[current] = getLIRBlock(x.blockSuccessor(successor));
-            i++;
-            for (; i < keyCount; i++) {
-                int newSuccessor = x.keySuccessorIndex(i);
-                if (newSuccessor != defaultSuccessor) {
-                    int newKey = x.keyAt(i).asInt();
-                    if (key + 1 == newKey && successor == newSuccessor) {
-                        // still in same range
-                        highKeys[current] = newKey;
-                    } else {
-                        current++;
-                        lowKeys[current] = newKey;
-                        highKeys[current] = newKey;
-                        targets[current] = getLIRBlock(x.blockSuccessor(newSuccessor));
-                    }
-                    key = newKey;
-                }
-                successor = newSuccessor;
-            }
-            assert current == switchRangeCount - 1;
-            emitSwitchRanges(lowKeys, highKeys, targets, defaultTarget, keyValue);
-        }
+        assert current == switchRangeCount - 1;
+        emitSwitchRanges(lowKeys, highKeys, targets, defaultTarget, keyValue);
     }
 
     public FrameMap frameMap() {
diff -r 8c5333c80cfd -r 0d7dfa5b79e8 graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java
--- a/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java	Thu Nov 15 11:40:50 2012 +0100
+++ b/graal/com.oracle.graal.java/src/com/oracle/graal/java/GraphBuilderPhase.java	Thu Nov 15 15:10:41 2012 +0100
@@ -1088,32 +1088,60 @@
         ValueNode value = frameState.ipop();
 
         int nofCases = bs.numberOfCases();
+        double[] keyProbabilities = switchProbability(nofCases + 1, bci);
 
-        Map<Integer, Integer> bciToSuccessorIndex = new HashMap<>();
-        int successorCount = currentBlock.successors.size();
-        for (int i = 0; i < successorCount; i++) {
-            assert !bciToSuccessorIndex.containsKey(currentBlock.successors.get(i).startBci);
-            if (!bciToSuccessorIndex.containsKey(currentBlock.successors.get(i).startBci)) {
-                bciToSuccessorIndex.put(currentBlock.successors.get(i).startBci, i);
+        Map<Integer, SuccessorInfo> bciToBlockSuccessorIndex = new HashMap<>();
+        for (int i = 0; i < currentBlock.successors.size(); i++) {
+            assert !bciToBlockSuccessorIndex.containsKey(currentBlock.successors.get(i).startBci);
+            if (!bciToBlockSuccessorIndex.containsKey(currentBlock.successors.get(i).startBci)) {
+                bciToBlockSuccessorIndex.put(currentBlock.successors.get(i).startBci, new SuccessorInfo(i));
             }
         }
 
-        double[] keyProbabilities = switchProbability(nofCases + 1, bci);
-
+        ArrayList<Block> actualSuccessors = new ArrayList<>();
         int[] keys = new int[nofCases];
         int[] keySuccessors = new int[nofCases + 1];
-        for (int i = 0; i < nofCases; i++) {
-            keys[i] = bs.keyAt(i);
-            keySuccessors[i] = bciToSuccessorIndex.get(bs.targetAt(i));
-        }
-        keySuccessors[nofCases] = bciToSuccessorIndex.get(bs.defaultTarget());
+        int deoptSuccessorIndex = -1;
+        int nextSuccessorIndex = 0;
+        for (int i = 0; i < nofCases + 1; i++) {
+            if (i < nofCases) {
+                keys[i] = bs.keyAt(i);
+            }
 
-        double[] successorProbabilities = IntegerSwitchNode.successorProbabilites(successorCount, keySuccessors, keyProbabilities);
-        IntegerSwitchNode lookupSwitch = currentGraph.add(new IntegerSwitchNode(value, successorCount, keys, keyProbabilities, keySuccessors));
-        for (int i = 0; i < successorCount; i++) {
-            lookupSwitch.setBlockSuccessor(i, createBlockTarget(successorProbabilities[i], currentBlock.successors.get(i), frameState));
+            if (isNeverExecutedCode(keyProbabilities[i])) {
+                if (deoptSuccessorIndex < 0) {
+                    deoptSuccessorIndex = nextSuccessorIndex++;
+                    actualSuccessors.add(null);
+                }
+                keySuccessors[i] = deoptSuccessorIndex;
+            } else {
+                int targetBci = i >= nofCases ? bs.defaultTarget() : bs.targetAt(i);
+                SuccessorInfo info = bciToBlockSuccessorIndex.get(targetBci);
+                if (info.actualIndex < 0) {
+                    info.actualIndex = nextSuccessorIndex++;
+                    actualSuccessors.add(currentBlock.successors.get(info.blockIndex));
+                }
+                keySuccessors[i] = info.actualIndex;
+            }
         }
-        append(lookupSwitch);
+
+        double[] successorProbabilities = IntegerSwitchNode.successorProbabilites(actualSuccessors.size(), keySuccessors, keyProbabilities);
+        IntegerSwitchNode switchNode = currentGraph.add(new IntegerSwitchNode(value, actualSuccessors.size(), keys, keyProbabilities, keySuccessors));
+        for (int i = 0; i < actualSuccessors.size(); i++) {
+            switchNode.setBlockSuccessor(i, createBlockTarget(successorProbabilities[i], actualSuccessors.get(i), frameState));
+        }
+
+        append(switchNode);
+    }
+
+    private static class SuccessorInfo {
+        int blockIndex;
+        int actualIndex;
+
+        public SuccessorInfo(int blockSuccessorIndex) {
+            this.blockIndex = blockSuccessorIndex;
+            actualIndex = -1;
+        }
     }
 
     private ConstantNode appendConstant(Constant constant) {
@@ -1206,13 +1234,18 @@
 
     private FixedNode createTarget(double probability, Block block, FrameStateBuilder stateAfter) {
         assert probability >= 0 && probability <= 1.01 : probability;
-        if (probability == 0 && optimisticOpts.removeNeverExecutedCode() && entryBCI == StructuredGraph.INVOCATION_ENTRY_BCI) {
+        if (isNeverExecutedCode(probability)) {
             return currentGraph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.UnreachedCode, graphId));
         } else {
+            assert block != null;
             return createTarget(block, stateAfter);
         }
     }
 
+    private boolean isNeverExecutedCode(double probability) {
+        return probability == 0 && optimisticOpts.removeNeverExecutedCode() && entryBCI == StructuredGraph.INVOCATION_ENTRY_BCI;
+    }
+
     private FixedNode createTarget(Block block, FrameStateBuilder state) {
         assert block != null && state != null;
         assert !block.isExceptionEntry || state.stackSize() == 1;
diff -r 8c5333c80cfd -r 0d7dfa5b79e8 graal/com.oracle.graal.lir.amd64/src/com/oracle/graal/lir/amd64/AMD64ControlFlow.java
--- a/graal/com.oracle.graal.lir.amd64/src/com/oracle/graal/lir/amd64/AMD64ControlFlow.java	Thu Nov 15 11:40:50 2012 +0100
+++ b/graal/com.oracle.graal.lir.amd64/src/com/oracle/graal/lir/amd64/AMD64ControlFlow.java	Thu Nov 15 15:10:41 2012 +0100
@@ -31,8 +31,8 @@
 import com.oracle.graal.api.code.CompilationResult.JumpTable;
 import com.oracle.graal.api.meta.*;
 import com.oracle.graal.asm.*;
+import com.oracle.graal.asm.amd64.AMD64Assembler.ConditionFlag;
 import com.oracle.graal.asm.amd64.*;
-import com.oracle.graal.asm.amd64.AMD64Assembler.*;
 import com.oracle.graal.graph.*;
 import com.oracle.graal.lir.*;
 import com.oracle.graal.lir.LIRInstruction.Opcode;
@@ -204,29 +204,33 @@
 
         @Override
         public void emitCode(TargetMethodAssembler tasm, AMD64MacroAssembler masm) {
+            assert isSorted(lowKeys) && isSorted(highKeys);
+
+            Label actualDefaultTarget = defaultTarget == null ? new Label() : defaultTarget.label();
+            int prevHighKey = 0;
+            boolean skipLowCheck = false;
             for (int i = 0; i < lowKeys.length; i++) {
                 int lowKey = lowKeys[i];
                 int highKey = highKeys[i];
                 if (lowKey == highKey) {
                     masm.cmpl(asIntReg(key), lowKey);
                     masm.jcc(ConditionFlag.equal, keyTargets[i].label());
-                } else if (lowKey + 1 == highKey) {
-                    masm.cmpl(asIntReg(key), lowKey);
-                    masm.jcc(ConditionFlag.equal, keyTargets[i].label());
-                    masm.cmpl(asIntReg(key), highKey);
-                    masm.jcc(ConditionFlag.equal, keyTargets[i].label());
+                    skipLowCheck = false;
                 } else {
-                    Label skip = new Label();
-                    masm.cmpl(asIntReg(key), lowKey);
-                    masm.jcc(ConditionFlag.less, skip);
+                    if (!skipLowCheck || (prevHighKey + 1) != lowKey) {
+                        masm.cmpl(asIntReg(key), lowKey);
+                        masm.jcc(ConditionFlag.less, actualDefaultTarget);
+                    }
                     masm.cmpl(asIntReg(key), highKey);
                     masm.jcc(ConditionFlag.lessEqual, keyTargets[i].label());
-                    masm.bind(skip);
+                    skipLowCheck = true;
                 }
+                prevHighKey = highKey;
             }
             if (defaultTarget != null) {
                 masm.jmp(defaultTarget.label());
             } else {
+                masm.bind(actualDefaultTarget);
                 masm.hlt();
             }
         }
@@ -248,6 +252,15 @@
         public void setFallThroughTarget(LabelRef target) {
             defaultTarget = target;
         }
+
+        private static boolean isSorted(int[] values) {
+            for (int i = 1; i < values.length; i++) {
+                if (values[i - 1] >= values[i]) {
+                    return false;
+                }
+            }
+            return true;
+        }
     }
 
 
diff -r 8c5333c80cfd -r 0d7dfa5b79e8 graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/TypeSwitchNode.java
--- a/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/TypeSwitchNode.java	Thu Nov 15 11:40:50 2012 +0100
+++ b/graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/java/TypeSwitchNode.java	Thu Nov 15 15:10:41 2012 +0100
@@ -41,8 +41,8 @@
     private final ResolvedJavaType[] keys;
 
     /**
-     * Constructs a type switch instruction. The keyProbabilities and keySuccessors array contain key.length + 1
-     * entries, the last entry describes the default (fall through) case.
+     * Constructs a type switch instruction. The keyProbabilities array contain key.length + 1
+     * entries. The last entry in every array describes the default case.
      *
      * @param value the instruction producing the value being switched on
      * @param successors the list of successors
@@ -52,8 +52,8 @@
      */
     public TypeSwitchNode(ValueNode value, BeginNode[] successors, double[] successorProbabilities, ResolvedJavaType[] keys, double[] keyProbabilities, int[] keySuccessors) {
         super(value, successors, successorProbabilities, keySuccessors, keyProbabilities);
-        assert successors.length == keys.length + 1;
-        assert successors.length == keyProbabilities.length;
+        assert successors.length <= keys.length + 1;
+        assert keySuccessors.length == keyProbabilities.length;
         this.keys = keys;
     }
 
diff -r 8c5333c80cfd -r 0d7dfa5b79e8 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeProbabilityPhase.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeProbabilityPhase.java	Thu Nov 15 11:40:50 2012 +0100
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/ComputeProbabilityPhase.java	Thu Nov 15 15:10:41 2012 +0100
@@ -100,6 +100,8 @@
                 double originalProbability = probability / frequency;
                 assert isRelativeProbability(originalProbability);
                 return (1 / frequency) * Math.max(1, Math.pow(originalProbability, 1.5) * Math.log10(frequency));
+            case -4:
+                return 1 / probability;
             default:
                 throw GraalInternalError.shouldNotReachHere();
         }
@@ -337,6 +339,7 @@
 
     private static FrequencyPropagationPolicy createFrequencyPropagationPolicy() {
         switch (GraalOptions.LoopFrequencyPropagationPolicy) {
+            case -4:
             case -3:
             case -2:
             case -1:
diff -r 8c5333c80cfd -r 0d7dfa5b79e8 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java	Thu Nov 15 11:40:50 2012 +0100
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningPhase.java	Thu Nov 15 15:10:41 2012 +0100
@@ -34,10 +34,9 @@
 import com.oracle.graal.nodes.*;
 import com.oracle.graal.nodes.spi.*;
 import com.oracle.graal.phases.*;
-import com.oracle.graal.phases.PhasePlan.*;
-import com.oracle.graal.phases.common.InliningUtil.*;
-import com.oracle.graal.phases.util.*;
-
+import com.oracle.graal.phases.PhasePlan.PhasePosition;
+import com.oracle.graal.phases.common.InliningUtil.InlineInfo;
+import com.oracle.graal.phases.common.InliningUtil.InliningCallback;
 
 public class InliningPhase extends Phase implements InliningCallback {
     /*
@@ -51,7 +50,6 @@
 
     private final Collection<? extends Invoke> hints;
 
-    private final PriorityQueue<InlineInfo> inlineCandidates = new PriorityQueue<>();
     private Assumptions assumptions;
 
     private final PhasePlan plan;
@@ -64,6 +62,7 @@
     private static final DebugMetric metricInliningPerformed = Debug.metric("InliningPerformed");
     private static final DebugMetric metricInliningConsidered = Debug.metric("InliningConsidered");
     private static final DebugMetric metricInliningStoppedByMaxDesiredSize = Debug.metric("InliningStoppedByMaxDesiredSize");
+    private static final DebugMetric metricInliningRuns = Debug.metric("Runs");
 
     public InliningPhase(TargetDescription target, GraalCodeCacheProvider runtime, Collection<? extends Invoke> hints, Assumptions assumptions, GraphCache cache, PhasePlan plan, OptimisticOptimizations optimisticOpts) {
         this.target = target;
@@ -77,109 +76,87 @@
         this.inliningPolicy = createInliningPolicy();
     }
 
-    @SuppressWarnings("unchecked")
     @Override
     protected void run(final StructuredGraph graph) {
-        graph.createNodeMap();
+        NodeBitMap visitedFixedNodes = graph.createNodeBitMap(true);
+        Deque<Invoke> sortedInvokes = new ArrayDeque<>();
 
-        if (hints != null) {
-            scanInvokes((Iterable<? extends Node>) Util.uncheckedCast(this.hints));
-        } else {
-            scanInvokes(graph.getNodes(InvokeNode.class));
-            scanInvokes(graph.getNodes(InvokeWithExceptionNode.class));
-        }
+        queueInvokes(graph.start(), sortedInvokes, visitedFixedNodes);
 
-        while (!inlineCandidates.isEmpty() && graph.getNodeCount() < GraalOptions.MaximumDesiredSize) {
-            InlineInfo candidate = inlineCandidates.remove();
-            if (!candidate.invoke.node().isAlive()) {
+        while (!sortedInvokes.isEmpty() && graph.getNodeCount() < GraalOptions.MaximumDesiredSize) {
+            final Invoke invoke = sortedInvokes.pop();
+            if (hints != null && !hints.contains(invoke)) {
                 continue;
             }
-            // refresh infos
-            final InlineInfo info = InliningUtil.getInlineInfo(candidate.invoke, candidate.level, runtime, assumptions, this, optimisticOpts);
 
-            boolean inline = Debug.scope("InliningDecisions", new Callable<Boolean>() {
+            InlineInfo candidate = Debug.scope("InliningDecisions", new Callable<InlineInfo>() {
                 @Override
-                public Boolean call() throws Exception {
-                    return info != null && inliningPolicy.isWorthInlining(graph, info);
+                public InlineInfo call() throws Exception {
+                    InlineInfo info = InliningUtil.getInlineInfo(invoke, computeInliningLevel(invoke), runtime, assumptions, InliningPhase.this, optimisticOpts);
+                    if (info == null || !info.invoke.node().isAlive() || info.level > GraalOptions.MaximumInlineLevel) {
+                        return null;
+                    }
+                    metricInliningConsidered.increment();
+                    if (inliningPolicy.isWorthInlining(graph, info)) {
+                        return info;
+                    } else {
+                        return null;
+                    }
                 }
             });
 
-            if (inline) {
+            // TEMP:
+//            if (GraalOptions.AlwaysInlineTrivialMethods) {
+//                TODO: Continue;
+//            }
+
+            if (candidate != null) {
                 int mark = graph.getMark();
-                Iterable<Node> newNodes = null;
                 try {
-                    info.inline(graph, runtime, this);
-                    Debug.dump(graph, "after %s", info);
-                    newNodes = graph.getNewNodes(mark);
+                    FixedNode predecessor = (FixedNode) invoke.predecessor();
+                    candidate.inline(graph, runtime, InliningPhase.this);
+                    Debug.dump(graph, "after %s", candidate);
                     if (GraalOptions.OptCanonicalizer) {
                         new CanonicalizerPhase(target, runtime, assumptions, mark, null).apply(graph);
                     }
-//                    if (GraalOptions.Intrinsify) {
-//                        new IntrinsificationPhase(runtime).apply(graph);
-//                    }
                     metricInliningPerformed.increment();
+
+                    queueInvokes(predecessor, sortedInvokes, visitedFixedNodes);
                 } catch (BailoutException bailout) {
                     // TODO determine if we should really bail out of the whole compilation.
                     throw bailout;
                 } catch (AssertionError e) {
-                    throw new GraalInternalError(e).addContext(info.toString());
+                    throw new GraalInternalError(e).addContext(candidate.toString());
                 } catch (RuntimeException e) {
-                    throw new GraalInternalError(e).addContext(info.toString());
+                    throw new GraalInternalError(e).addContext(candidate.toString());
                 } catch (GraalInternalError e) {
-                    throw e.addContext(info.toString());
-                }
-
-                if (newNodes != null && info.level < GraalOptions.MaximumInlineLevel) {
-                    scanInvokes(newNodes);
+                    throw e.addContext(candidate.toString());
                 }
             }
         }
 
-        if (GraalOptions.Debug && graph.getNodeCount() >= GraalOptions.MaximumDesiredSize) {
-            Debug.scope("InliningDecisions", new Runnable() {
-                public void run() {
-                    for (InlineInfo info : inlineCandidates) {
-                        Debug.log("not inlining %s because inlining cut off by MaximumDesiredSize", InliningUtil.methodName(info));
+        if (graph.getNodeCount() >= GraalOptions.MaximumDesiredSize) {
+            if (GraalOptions.Debug) {
+                Debug.scope("InliningDecisions", new Runnable() {
+                    public void run() {
+                        Debug.log("inlining is cut off by MaximumDesiredSize");
                     }
-                }
-            });
+                });
 
-            metricInliningStoppedByMaxDesiredSize.increment();
+                metricInliningStoppedByMaxDesiredSize.increment();
+            }
         }
     }
 
-    private void scanInvokes(final Iterable<? extends Node> nodes) {
-        Debug.scope("InliningDecisions", new Runnable() {
-            public void run() {
-                for (Node node : nodes) {
-                    if (node != null) {
-                        if (node instanceof Invoke) {
-                            Invoke invoke = (Invoke) node;
-                            scanInvoke(invoke);
-                        }
-                        for (Node usage : node.usages().filterInterface(Invoke.class).snapshot()) {
-                            scanInvoke((Invoke) usage);
-                        }
-                    }
-                }
-            }
-        });
-    }
-
-    private void scanInvoke(Invoke invoke) {
-        InlineInfo info = InliningUtil.getInlineInfo(invoke, computeInliningLevel(invoke), runtime, assumptions, this, optimisticOpts);
-        if (info != null) {
-            metricInliningConsidered.increment();
-            inlineCandidates.add(info);
+    private static void queueInvokes(FixedNode start, Deque<Invoke> invokes, NodeBitMap visitedFixedNodes) {
+        ArrayList<Invoke> results = new ArrayList<>();
+        new InliningIterator(start, results, visitedFixedNodes).apply();
+        // insert the newly found invokes in their correct control-flow order
+        for (int i = results.size() - 1; i >= 0; i--) {
+            invokes.addFirst(results.get(i));
         }
     }
 
-    public static final Map<JavaMethod, Integer> parsedMethods = new HashMap<>();
-
-
-
-    private static final DebugMetric metricInliningRuns = Debug.metric("Runs");
-
     @Override
     public StructuredGraph buildGraph(final ResolvedJavaMethod method) {
         metricInliningRuns.increment();
@@ -202,9 +179,6 @@
         if (GraalOptions.OptCanonicalizer) {
             new CanonicalizerPhase(target, runtime, assumptions).apply(newGraph);
         }
-        if (GraalOptions.Intrinsify) {
-            new IntrinsificationPhase(runtime).apply(newGraph);
-        }
         if (GraalOptions.CullFrameStates) {
             new CullFrameStatesPhase().apply(newGraph);
         }
@@ -417,4 +391,103 @@
             return complexity;
         }
     }
+
+    private static class InliningIterator {
+        private final FixedNode start;
+        private final Collection<Invoke> invokes;
+        private final NodeBitMap processedNodes;
+
+        private final Deque<FixedNode> nodeQueue;
+        private final NodeBitMap queuedNodes;
+
+        public InliningIterator(FixedNode start, Collection<Invoke> invokes, NodeBitMap visitedFixedNodes) {
+            this.start = start;
+            this.invokes = invokes;
+            this.processedNodes = visitedFixedNodes;
+
+            this.nodeQueue = new ArrayDeque<>();
+            this.queuedNodes = visitedFixedNodes.copy();
+
+            assert start.isAlive();
+        }
+
+        public void apply() {
+            FixedNode current = start;
+            do {
+                assert current.isAlive();
+                processedNodes.mark(current);
+
+                if (current instanceof InvokeWithExceptionNode || current instanceof InvokeNode) {
+                    invoke((Invoke) current);
+                    queueSuccessors(current);
+                    current = nextQueuedNode();
+                } else if (current instanceof LoopBeginNode) {
+                    current = ((LoopBeginNode) current).next();
+                    assert current != null;
+                } else if (current instanceof LoopEndNode) {
+                    current = nextQueuedNode();
+                } else if (current instanceof MergeNode) {
+                    current = ((MergeNode) current).next();
+                    assert current != null;
+                } else if (current instanceof FixedWithNextNode) {
+                    queueSuccessors(current);
+                    current = nextQueuedNode();
+                } else if (current instanceof EndNode) {
+                    queueMerge((EndNode) current);
+                    current = nextQueuedNode();
+                } else if (current instanceof DeoptimizeNode) {
+                    current = nextQueuedNode();
+                } else if (current instanceof ReturnNode) {
+                    current = nextQueuedNode();
+                } else if (current instanceof UnwindNode) {
+                    current = nextQueuedNode();
+                } else if (current instanceof ControlSplitNode) {
+                    queueSuccessors(current);
+                    current = nextQueuedNode();
+                } else {
+                    assert false : current;
+                }
+            } while(current != null);
+        }
+
+        private void queueSuccessors(FixedNode x) {
+            for (Node node : x.successors()) {
+                if (node != null && !queuedNodes.isMarked(node)) {
+                    queuedNodes.mark(node);
+                    nodeQueue.addFirst((FixedNode) node);
+                }
+            }
+        }
+
+        private FixedNode nextQueuedNode() {
+            if (nodeQueue.isEmpty()) {
+                return null;
+            }
+
+            FixedNode result = nodeQueue.removeFirst();
+            assert queuedNodes.isMarked(result);
+            return result;
+        }
+
+        private void queueMerge(EndNode end) {
+            MergeNode merge = end.merge();
+            if (!queuedNodes.isMarked(merge) && visitedAllEnds(merge)) {
+                queuedNodes.mark(merge);
+                nodeQueue.add(merge);
+            }
+        }
+
+        private boolean visitedAllEnds(MergeNode merge) {
+            for (int i = 0; i < merge.forwardEndCount(); i++) {
+                if (!processedNodes.isMarked(merge.forwardEndAt(i))) {
+                    return false;
+                }
+            }
+            return true;
+        }
+
+        protected void invoke(Invoke invoke) {
+            invokes.add(invoke);
+        }
+    }
 }
diff -r 8c5333c80cfd -r 0d7dfa5b79e8 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java	Thu Nov 15 11:40:50 2012 +0100
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/InliningUtil.java	Thu Nov 15 15:10:41 2012 +0100
@@ -107,11 +107,16 @@
             return (weight < o.weight) ? -1 : (weight > o.weight) ? 1 : 0;
         }
 
-        protected static StructuredGraph getGraph(final ResolvedJavaMethod concrete, final InliningCallback callback) {
+        protected static StructuredGraph getGraph(final Invoke invoke, final ResolvedJavaMethod concrete, final GraalCodeCacheProvider runtime, final InliningCallback callback) {
             return Debug.scope("GetInliningGraph", concrete, new Callable<StructuredGraph>() {
                 @Override
                 public StructuredGraph call() throws Exception {
-                    return callback.buildGraph(concrete);
+                    StructuredGraph result = getIntrinsicGraph(invoke, concrete, runtime);
+                    if (result == null) {
+                        assert !Modifier.isNative(concrete.getModifiers());
+                        result = callback.buildGraph(concrete);
+                    }
+                    return result;
                 }
             });
         }
@@ -143,8 +148,7 @@
 
         @Override
         public void inline(StructuredGraph compilerGraph, GraalCodeCacheProvider runtime, final InliningCallback callback) {
-            StructuredGraph graph = getGraph(concrete, callback);
-            assert !IntrinsificationPhase.canIntrinsify(invoke, concrete, runtime);
+            StructuredGraph graph = getGraph(invoke, concrete, runtime, callback);
             callback.recordMethodContentsAssumption(concrete);
             InliningUtil.inline(invoke, graph, true);
         }
@@ -203,8 +207,7 @@
             graph.addBeforeFixed(invoke.node(), guard);
             graph.addBeforeFixed(invoke.node(), anchor);
 
-            StructuredGraph calleeGraph = getGraph(concrete, callback);
-            assert !IntrinsificationPhase.canIntrinsify(invoke, concrete, runtime);
+            StructuredGraph calleeGraph = getGraph(invoke, concrete, runtime, callback);
             callback.recordMethodContentsAssumption(concrete);
             InliningUtil.inline(invoke, calleeGraph, false);
         }
@@ -300,27 +303,26 @@
             }
 
             // create one separate block for each invoked method
-            BeginNode[] calleeEntryNodes = new BeginNode[numberOfMethods];
+            BeginNode[] successors = new BeginNode[numberOfMethods + 1];
             for (int i = 0; i < numberOfMethods; i++) {
-                int predecessors = 0;
                 double probability = 0;
                 for (int j = 0; j < typesToConcretes.length; j++) {
                     if (typesToConcretes[j] == i) {
-                        predecessors++;
                         probability += ptypes[j].getProbability();
                     }
                 }
 
-                calleeEntryNodes[i] = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, predecessors, invoke.probability() * probability, true);
+                successors[i] = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, invoke.probability() * probability, true);
             }
 
             // create the successor for an unknown type
-            FixedNode unknownTypeNode;
+            FixedNode unknownTypeSux;
             if (shouldFallbackToInvoke()) {
-                unknownTypeNode = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, 1, notRecordedTypeProbability, false);
+                unknownTypeSux = createInvocationBlock(graph, invoke, returnMerge, returnValuePhi, exceptionMerge, exceptionObjectPhi, notRecordedTypeProbability, false);
             } else {
-                unknownTypeNode = graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.TypeCheckedInliningViolated, invoke.leafGraphId()));
+                unknownTypeSux = graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.TypeCheckedInliningViolated, invoke.leafGraphId()));
             }
+            successors[successors.length - 1] = BeginNode.begin(unknownTypeSux);
 
             // replace the invoke exception edge
             if (invoke instanceof InvokeWithExceptionNode) {
@@ -332,10 +334,19 @@
                 GraphUtil.killCFG(invokeWithExceptionNode.exceptionEdge());
             }
 
+            // get all graphs and record assumptions
+            assert invoke.node().isAlive();
+            StructuredGraph[] calleeGraphs = new StructuredGraph[numberOfMethods];
+            for (int i = 0; i < numberOfMethods; i++) {
+                ResolvedJavaMethod concrete = concretes.get(i);
+                calleeGraphs[i] = getGraph(invoke, concrete, runtime, callback);
+                callback.recordMethodContentsAssumption(concrete);
+            }
+
             // replace the invoke with a switch on the type of the actual receiver
             LoadHubNode receiverHub = graph.add(new LoadHubNode(invoke.methodCallTarget().receiver()));
             graph.addBeforeFixed(invoke.node(), receiverHub);
-            FixedNode dispatchOnType = createDispatchOnType(graph, receiverHub, calleeEntryNodes, unknownTypeNode);
+            FixedNode dispatchOnType = createDispatchOnType(graph, receiverHub, successors);
 
             assert invoke.next() == continuation;
             invoke.setNext(null);
@@ -346,8 +357,8 @@
             ArrayList<PiNode> replacements = new ArrayList<>();
 
             // do the actual inlining for every invoke
-            for (int i = 0; i < calleeEntryNodes.length; i++) {
-                BeginNode node = calleeEntryNodes[i];
+            for (int i = 0; i < numberOfMethods; i++) {
+                BeginNode node = successors[i];
                 Invoke invokeForInlining = (Invoke) node.next();
 
                 ResolvedJavaType commonType = getLeastCommonType(i);
@@ -356,10 +367,7 @@
                 PiNode anchoredReceiver = createAnchoredReceiver(graph, node, commonType, receiver, exact);
                 invokeForInlining.callTarget().replaceFirstInput(receiver, anchoredReceiver);
 
-                ResolvedJavaMethod concrete = concretes.get(i);
-                StructuredGraph calleeGraph = getGraph(concrete, callback);
-                callback.recordMethodContentsAssumption(concrete);
-                assert !IntrinsificationPhase.canIntrinsify(invokeForInlining, concrete, runtime);
+                StructuredGraph calleeGraph = calleeGraphs[i];
                 InliningUtil.inline(invokeForInlining, calleeGraph, false);
                 replacements.add(anchoredReceiver);
             }
@@ -417,58 +425,50 @@
         private void inlineSingleMethod(StructuredGraph graph, GraalCodeCacheProvider runtime, InliningCallback callback) {
             assert concretes.size() == 1 && ptypes.length > 1 && !shouldFallbackToInvoke() && notRecordedTypeProbability == 0;
 
-            MergeNode calleeEntryNode = graph.add(new MergeNode());
+            BeginNode calleeEntryNode = graph.add(new BeginNode());
             calleeEntryNode.setProbability(invoke.probability());
             LoadHubNode receiverHub = graph.add(new LoadHubNode(invoke.methodCallTarget().receiver()));
             graph.addBeforeFixed(invoke.node(), receiverHub);
 
-            FixedNode unknownTypeNode = graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.TypeCheckedInliningViolated, invoke.leafGraphId()));
-            FixedNode dispatchOnType = createDispatchOnType(graph, receiverHub, new BeginNode[] {calleeEntryNode}, unknownTypeNode);
+            BeginNode unknownTypeSux = BeginNode.begin(graph.add(new DeoptimizeNode(DeoptimizationAction.InvalidateReprofile, DeoptimizationReason.TypeCheckedInliningViolated, invoke.leafGraphId())));
+            BeginNode[] successors = new BeginNode[] {calleeEntryNode, unknownTypeSux};
+            FixedNode dispatchOnType = createDispatchOnType(graph, receiverHub, successors);
 
             FixedWithNextNode pred = (FixedWithNextNode) invoke.node().predecessor();
             pred.setNext(dispatchOnType);
             calleeEntryNode.setNext(invoke.node());
 
             ResolvedJavaMethod concrete = concretes.get(0);
-            StructuredGraph calleeGraph = getGraph(concrete, callback);
-            assert !IntrinsificationPhase.canIntrinsify(invoke, concrete, runtime);
+            StructuredGraph calleeGraph = getGraph(invoke, concrete, runtime, callback);
             callback.recordMethodContentsAssumption(concrete);
             InliningUtil.inline(invoke, calleeGraph, false);
         }
 
-        private FixedNode createDispatchOnType(StructuredGraph graph, LoadHubNode objectClassNode, BeginNode[] calleeEntryNodes, FixedNode unknownTypeSux) {
+        private FixedNode createDispatchOnType(StructuredGraph graph, LoadHubNode objectClassNode, BeginNode[] successors) {
             assert ptypes.length > 1;
 
-            ResolvedJavaType[] types = new ResolvedJavaType[ptypes.length];
-            double[] probabilities = new double[ptypes.length + 1];
-            BeginNode[] successors = new BeginNode[ptypes.length + 1];
+            ResolvedJavaType[] keys = new ResolvedJavaType[ptypes.length];
+            double[] keyProbabilities = new double[ptypes.length + 1];
             int[] keySuccessors = new int[ptypes.length + 1];
             for (int i = 0; i < ptypes.length; i++) {
-                types[i] = ptypes[i].getType();
-                probabilities[i] = ptypes[i].getProbability();
-                FixedNode entry = calleeEntryNodes[typesToConcretes[i]];
-                if (entry instanceof MergeNode) {
-                    EndNode endNode = graph.add(new EndNode());
-                    ((MergeNode) entry).addForwardEnd(endNode);
-                    entry = endNode;
-                }
-                successors[i] = BeginNode.begin(entry);
-                keySuccessors[i] = i;
+                keys[i] = ptypes[i].getType();
+                keyProbabilities[i] = ptypes[i].getProbability();
+                keySuccessors[i] = typesToConcretes[i];
+                assert keySuccessors[i] < successors.length - 1 : "last successor is the unknownTypeSux";
             }
-            assert !(unknownTypeSux instanceof MergeNode);
-            successors[successors.length - 1] = BeginNode.begin(unknownTypeSux);
-            probabilities[successors.length - 1] = notRecordedTypeProbability;
-            keySuccessors[successors.length - 1] = successors.length - 1;
+            keyProbabilities[keyProbabilities.length - 1] = notRecordedTypeProbability;
+            keySuccessors[keySuccessors.length - 1] = successors.length - 1;
 
-            TypeSwitchNode typeSwitch = graph.add(new TypeSwitchNode(objectClassNode, successors, probabilities, types, probabilities, keySuccessors));
+            double[] successorProbabilities = SwitchNode.successorProbabilites(successors.length, keySuccessors, keyProbabilities);
+            TypeSwitchNode typeSwitch = graph.add(new TypeSwitchNode(objectClassNode, successors, successorProbabilities, keys, keyProbabilities, keySuccessors));
 
             return typeSwitch;
         }
 
         private static BeginNode createInvocationBlock(StructuredGraph graph, Invoke invoke, MergeNode returnMerge, PhiNode returnValuePhi,
-                        MergeNode exceptionMerge, PhiNode exceptionObjectPhi, int predecessors, double probability, boolean useForInlining) {
+                        MergeNode exceptionMerge, PhiNode exceptionObjectPhi, double probability, boolean useForInlining) {
             Invoke duplicatedInvoke = duplicateInvokeForInlining(graph, invoke, exceptionMerge, exceptionObjectPhi, useForInlining, probability);
-            BeginNode calleeEntryNode = graph.add(predecessors > 1 ? new MergeNode() : new BeginNode());
+            BeginNode calleeEntryNode = graph.add(new BeginNode());
             calleeEntryNode.setNext(duplicatedInvoke.node());
             calleeEntryNode.setProbability(probability);
 
@@ -588,7 +588,7 @@
             // The invoke has already been lowered , or has been created as a low-level node. We have no method information.
             return null;
         }
-        ResolvedJavaMethod parent = invoke.stateAfter().method();
+        ResolvedJavaMethod caller = getCaller(invoke);
         MethodCallTargetNode callTarget = invoke.methodCallTarget();
         ResolvedJavaMethod targetMethod = callTarget.targetMethod();
         if (targetMethod == null) {
@@ -599,8 +599,8 @@
         }
 
         if (callTarget.invokeKind() == InvokeKind.Special || targetMethod.canBeStaticallyBound()) {
-            if (checkTargetConditions(invoke, targetMethod, optimisticOpts)) {
-                double weight = callback == null ? 0 : callback.inliningWeight(parent, targetMethod, invoke);
+            if (checkTargetConditions(invoke, targetMethod, optimisticOpts, runtime)) {
+                double weight = callback == null ? 0 : callback.inliningWeight(caller, targetMethod, invoke);
                 return new ExactInlineInfo(invoke, weight, level, targetMethod);
             }
             return null;
@@ -610,8 +610,8 @@
         if (receiverStamp.isExactType()) {
             assert receiverType.isSubtypeOf(targetMethod.getDeclaringClass()) : receiverType + " subtype of " + targetMethod.getDeclaringClass() + " for " + targetMethod;
             ResolvedJavaMethod resolved = receiverType.resolveMethod(targetMethod);
-            if (checkTargetConditions(invoke, resolved, optimisticOpts)) {
-                double weight = callback == null ? 0 : callback.inliningWeight(parent, resolved, invoke);
+            if (checkTargetConditions(invoke, resolved, optimisticOpts, runtime)) {
+                double weight = callback == null ? 0 : callback.inliningWeight(caller, resolved, invoke);
                 return new ExactInlineInfo(invoke, weight, level, resolved);
             }
             return null;
@@ -629,8 +629,8 @@
         if (assumptions != null) {
             ResolvedJavaMethod concrete = holder.findUniqueConcreteMethod(targetMethod);
             if (concrete != null) {
-                if (checkTargetConditions(invoke, concrete, optimisticOpts)) {
-                    double weight = callback == null ? 0 : callback.inliningWeight(parent, concrete, invoke);
+                if (checkTargetConditions(invoke, concrete, optimisticOpts, runtime)) {
+                    double weight = callback == null ? 0 : callback.inliningWeight(caller, concrete, invoke);
                     return new AssumptionInlineInfo(invoke, weight, level, holder, concrete);
                 }
                 return null;
@@ -638,11 +638,11 @@
         }
 
         // type check based inlining
-        return getTypeCheckedInlineInfo(invoke, level, callback, parent, targetMethod, optimisticOpts);
+        return getTypeCheckedInlineInfo(invoke, level, callback, caller, targetMethod, optimisticOpts, runtime);
     }
 
-    private static InlineInfo getTypeCheckedInlineInfo(Invoke invoke, int level, InliningCallback callback, ResolvedJavaMethod parent, ResolvedJavaMethod targetMethod, OptimisticOptimizations optimisticOpts) {
-        ProfilingInfo profilingInfo = parent.getProfilingInfo();
+    private static InlineInfo getTypeCheckedInlineInfo(Invoke invoke, int level, InliningCallback callback, ResolvedJavaMethod caller, ResolvedJavaMethod targetMethod, OptimisticOptimizations optimisticOpts, GraalCodeCacheProvider runtime) {
+        ProfilingInfo profilingInfo = caller.getProfilingInfo();
         JavaTypeProfile typeProfile = profilingInfo.getTypeProfile(invoke.bci());
         if (typeProfile != null) {
             ProfiledType[] ptypes = typeProfile.getTypes();
@@ -653,8 +653,8 @@
                     if (optimisticOpts.inlineMonomorphicCalls()) {
                         ResolvedJavaType type = ptypes[0].getType();
                         ResolvedJavaMethod concrete = type.resolveMethod(targetMethod);
-                        if (checkTargetConditions(invoke, concrete, optimisticOpts)) {
-                            double weight = callback == null ? 0 : callback.inliningWeight(parent, concrete, invoke);
+                        if (checkTargetConditions(invoke, concrete, optimisticOpts, runtime)) {
+                            double weight = callback == null ? 0 : callback.inliningWeight(caller, concrete, invoke);
                             return new TypeGuardInlineInfo(invoke, weight, level, concrete, type);
                         }
 
@@ -692,11 +692,11 @@
                         double totalWeight = 0;
                         boolean canInline = true;
                         for (ResolvedJavaMethod concrete: concreteMethods) {
-                            if (!checkTargetConditions(invoke, concrete, optimisticOpts)) {
+                            if (!checkTargetConditions(invoke, concrete, optimisticOpts, runtime)) {
                                 canInline = false;
                                 break;
                             }
-                            totalWeight += callback == null ? 0 : callback.inliningWeight(parent, concrete, invoke);
+                            totalWeight += callback == null ? 0 : callback.inliningWeight(caller, concrete, invoke);
                         }
 
                         if (canInline) {
@@ -724,6 +724,10 @@
         }
     }
 
+    private static ResolvedJavaMethod getCaller(Invoke invoke) {
+        return invoke.stateAfter().method();
+    }
+
     private static PiNode createAnchoredReceiver(StructuredGraph graph, FixedNode anchor, ResolvedJavaType commonType, ValueNode receiver, boolean exact) {
         // to avoid that floating reads on receiver fields float above the type check
         return graph.unique(new PiNode(receiver, anchor, exact ? StampFactory.exactNonNull(commonType) : StampFactory.declaredNonNull(commonType)));
@@ -745,39 +749,34 @@
         return true;
     }
 
-    private static boolean checkTargetConditions(Invoke invoke, JavaMethod method, OptimisticOptimizations optimisticOpts) {
+    private static boolean checkTargetConditions(Invoke invoke, ResolvedJavaMethod method, OptimisticOptimizations optimisticOpts, GraalCodeCacheProvider runtime) {
         if (method == null) {
             Debug.log("not inlining because method is not resolved");
             return false;
         }
-        if (!(method instanceof ResolvedJavaMethod)) {
-            Debug.log("not inlining %s because it is unresolved", method.toString());
+        if (Modifier.isNative(method.getModifiers()) && (!GraalOptions.Intrinsify || !InliningUtil.canIntrinsify(invoke, method, runtime))) {
+            Debug.log("not inlining %s because it is a non-intrinsic native method", methodName(method, invoke));
             return false;
         }
-        ResolvedJavaMethod resolvedMethod = (ResolvedJavaMethod) method;
-        if (Modifier.isNative(resolvedMethod.getModifiers())) {
-            Debug.log("not inlining %s because it is a native method", methodName(resolvedMethod, invoke));
+        if (Modifier.isAbstract(method.getModifiers())) {
+            Debug.log("not inlining %s because it is an abstract method", methodName(method, invoke));
             return false;
         }
-        if (Modifier.isAbstract(resolvedMethod.getModifiers())) {
-            Debug.log("not inlining %s because it is an abstract method", methodName(resolvedMethod, invoke));
+        if (!method.getDeclaringClass().isInitialized()) {
+            Debug.log("not inlining %s because of non-initialized class", methodName(method, invoke));
             return false;
         }
-        if (!resolvedMethod.getDeclaringClass().isInitialized()) {
-            Debug.log("not inlining %s because of non-initialized class", methodName(resolvedMethod, invoke));
-            return false;
-        }
-        if (!resolvedMethod.canBeInlined()) {
-            Debug.log("not inlining %s because it is marked non-inlinable", methodName(resolvedMethod, invoke));
+        if (!method.canBeInlined()) {
+            Debug.log("not inlining %s because it is marked non-inlinable", methodName(method, invoke));
             return false;
         }
-        if (computeRecursiveInliningLevel(invoke.stateAfter(), (ResolvedJavaMethod) method) > GraalOptions.MaximumRecursiveInlining) {
-            Debug.log("not inlining %s because it exceeds the maximum recursive inlining depth", methodName(resolvedMethod, invoke));
+        if (computeRecursiveInliningLevel(invoke.stateAfter(), method) > GraalOptions.MaximumRecursiveInlining) {
+            Debug.log("not inlining %s because it exceeds the maximum recursive inlining depth", methodName(method, invoke));
             return false;
         }
-        OptimisticOptimizations calleeOpts = new OptimisticOptimizations(resolvedMethod);
+        OptimisticOptimizations calleeOpts = new OptimisticOptimizations(method);
         if (calleeOpts.lessOptimisticThan(optimisticOpts)) {
-            Debug.log("not inlining %s because callee uses less optimistic optimizations than caller", methodName(resolvedMethod, invoke));
+            Debug.log("not inlining %s because callee uses less optimistic optimizations than caller", methodName(method, invoke));
             return false;
         }
 
@@ -953,4 +952,19 @@
             graph.addBeforeFixed(invoke.node(), graph.add(new FixedGuardNode(graph.unique(new IsNullNode(firstParam)), DeoptimizationReason.NullCheckException, DeoptimizationAction.InvalidateReprofile, true, invoke.leafGraphId())));
         }
     }
+
+    public static boolean canIntrinsify(Invoke invoke, ResolvedJavaMethod target, GraalCodeCacheProvider runtime) {
+        return getIntrinsicGraph(invoke, target, runtime) != null;
+    }
+
+    private static StructuredGraph getIntrinsicGraph(Invoke invoke, ResolvedJavaMethod target, GraalCodeCacheProvider runtime) {
+        assert invoke.node().isAlive();
+
+        StructuredGraph intrinsicGraph = (StructuredGraph) target.getCompilerStorage().get(Graph.class);
+        if (intrinsicGraph == null) {
+            // TODO remove once all intrinsics are available via compilerStorage
+            intrinsicGraph = runtime.intrinsicGraph(invoke.stateAfter().method(), invoke.bci(), target, invoke.callTarget().arguments());
+        }
+        return intrinsicGraph;
+    }
 }
diff -r 8c5333c80cfd -r 0d7dfa5b79e8 graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/IntrinsificationPhase.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/IntrinsificationPhase.java	Thu Nov 15 11:40:50 2012 +0100
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,77 +0,0 @@
-/*
- * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved.
- * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
- *
- * This code is free software; you can redistribute it and/or modify it
- * under the terms of the GNU General Public License version 2 only, as
- * published by the Free Software Foundation.
- *
- * This code is distributed in the hope that it will be useful, but WITHOUT
- * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
- * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
- * version 2 for more details (a copy is included in the LICENSE file that
- * accompanied this code).
- *
- * You should have received a copy of the GNU General Public License version
- * 2 along with this work; if not, write to the Free Software Foundation,
- * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
- *
- * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
- * or visit www.oracle.com if you need additional information or have any
- * questions.
- */
-package com.oracle.graal.phases.common;
-
-import com.oracle.graal.api.meta.*;
-import com.oracle.graal.debug.*;
-import com.oracle.graal.graph.*;
-import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.java.*;
-import com.oracle.graal.nodes.spi.*;
-import com.oracle.graal.phases.*;
-
-public class IntrinsificationPhase extends Phase {
-
-    private final GraalCodeCacheProvider runtime;
-
-    public IntrinsificationPhase(GraalCodeCacheProvider runtime) {
-        this.runtime = runtime;
-    }
-
-    @Override
-    protected void run(StructuredGraph graph) {
-        for (InvokeNode invoke : graph.getNodes(InvokeNode.class)) {
-            tryIntrinsify(invoke, runtime);
-        }
-        for (InvokeWithExceptionNode invoke : graph.getNodes(InvokeWithExceptionNode.class)) {
-            tryIntrinsify(invoke, runtime);
-        }
-    }
-
-    public static boolean canIntrinsify(Invoke invoke, ResolvedJavaMethod target, GraalCodeCacheProvider runtime) {
-        return getIntrinsicGraph(invoke, target, runtime) != null;
-    }
-
-    private static void tryIntrinsify(Invoke invoke, GraalCodeCacheProvider runtime) {
-        if (invoke.callTarget() instanceof MethodCallTargetNode && invoke.methodCallTarget().targetMethod() != null) {
-            tryIntrinsify(invoke, invoke.methodCallTarget().targetMethod(), runtime);
-        }
-    }
-
-    private static void tryIntrinsify(Invoke invoke, ResolvedJavaMethod target, GraalCodeCacheProvider runtime) {
-        StructuredGraph intrinsicGraph = getIntrinsicGraph(invoke, target, runtime);
-        if (intrinsicGraph != null) {
-            Debug.log(" > Intrinsify %s", target);
-            InliningUtil.inline(invoke, intrinsicGraph, true);
-        }
-    }
-
-    private static StructuredGraph getIntrinsicGraph(Invoke invoke, ResolvedJavaMethod target, GraalCodeCacheProvider runtime) {
-        StructuredGraph intrinsicGraph = (StructuredGraph) target.getCompilerStorage().get(Graph.class);
-        if (intrinsicGraph == null) {
-            // TODO remove once all intrinsics are available via compilerStorage
-            intrinsicGraph = runtime.intrinsicGraph(invoke.stateAfter().method(), invoke.bci(), target, invoke.callTarget().arguments());
-        }
-        return intrinsicGraph;
-    }
-}
diff -r 8c5333c80cfd -r 0d7dfa5b79e8 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java	Thu Nov 15 11:40:50 2012 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/GraalOptions.java	Thu Nov 15 15:10:41 2012 +0100
@@ -48,6 +48,7 @@
     public static int     MaximumTrivialSize                 = 10;
     public static int     MaximumInlineLevel                 = 30;
     public static int     MaximumDesiredSize                 = 3000;
+    public static boolean AlwaysInlineTrivialMethods         = ____;
     public static int     MaximumRecursiveInlining           = 1;
     public static int     SmallCompiledCodeSize              = 2200;
     public static boolean LimitInlinedProbability            = ____;
@@ -172,7 +173,7 @@
     public static boolean ResolveClassBeforeStaticInvoke     = true;
 
     // Translating tableswitch instructions
-    public static int     SequentialSwitchLimit              = 4;
+    public static int     MinimumJumpTableSize               = 5;
     public static int     RangeTestsSwitchDensity            = 5;
     public static double  MinTableSwitchDensity              = 0.5;
 
diff -r 8c5333c80cfd -r 0d7dfa5b79e8 graal/com.oracle.graal.phases/src/com/oracle/graal/phases/OptimisticOptimizations.java
--- a/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/OptimisticOptimizations.java	Thu Nov 15 11:40:50 2012 +0100
+++ b/graal/com.oracle.graal.phases/src/com/oracle/graal/phases/OptimisticOptimizations.java	Thu Nov 15 15:10:41 2012 +0100
@@ -59,19 +59,23 @@
         if (checkDeoptimizations(profilingInfo, DeoptimizationReason.NotCompiledExceptionHandler)) {
             enabledOpts.add(Optimization.UseExceptionProbability);
         }
+
+        log(method);
     }
 
     private OptimisticOptimizations(Set<Optimization> enabledOpts) {
         this.enabledOpts = enabledOpts;
     }
 
-    public void log(JavaMethod method) {
-        for (Optimization opt: Optimization.values()) {
-            if (!enabledOpts.contains(opt)) {
-                if (GraalOptions.PrintDisabledOptimisticOptimizations) {
-                    TTY.println("WARN: deactivated optimistic optimization %s for %s", opt.name(), MetaUtil.format("%H.%n(%p)", method));
+    private void log(ResolvedJavaMethod method) {
+        if (Debug.isLogEnabled()) {
+            for (Optimization opt: Optimization.values()) {
+                if (!enabledOpts.contains(opt)) {
+                    if (GraalOptions.PrintDisabledOptimisticOptimizations) {
+                        Debug.log("WARN: deactivated optimistic optimization %s for %s", opt.name(), MetaUtil.format("%H.%n(%p)", method));
+                    }
+                    disabledOptimisticOptsMetric.increment();
                 }
-                disabledOptimisticOptsMetric.increment();
             }
         }
     }
diff -r 8c5333c80cfd -r 0d7dfa5b79e8 graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetInstaller.java
--- a/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetInstaller.java	Thu Nov 15 11:40:50 2012 +0100
+++ b/graal/com.oracle.graal.snippets/src/com/oracle/graal/snippets/SnippetInstaller.java	Thu Nov 15 15:10:41 2012 +0100
@@ -52,7 +52,7 @@
      * A graph cache used by this installer to avoid using the compiler
      * storage for each method processed during snippet installation.
      * Without this, all processed methods are to be determined as
-     * {@linkplain IntrinsificationPhase#canIntrinsify intrinsifiable}.
+     * {@linkplain InliningUtil#canIntrinsify intrinsifiable}.
      */
     private final Map<ResolvedJavaMethod, StructuredGraph> graphCache;