--- a/graal/com.oracle.graal.hotspot.test/src/com/oracle/graal/hotspot/test/WriteBarrierAdditionTest.java	Thu May 15 16:45:08 2014 +0200
+++ b/graal/com.oracle.graal.hotspot.test/src/com/oracle/graal/hotspot/test/WriteBarrierAdditionTest.java	Thu May 15 17:25:49 2014 +0200
@@ -26,6 +26,7 @@
 import java.lang.ref.*;
 import java.lang.reflect.*;
 
+import com.oracle.graal.phases.common.inlining.policy.InlineEverythingPolicy;
 import org.junit.*;
 
 import com.oracle.graal.api.code.*;
@@ -249,7 +250,7 @@
             StructuredGraph graph = parse(snippet);
             HighTierContext highContext = new HighTierContext(getProviders(), new Assumptions(false), null, getDefaultGraphBuilderSuite(), OptimisticOptimizations.ALL);
             MidTierContext midContext = new MidTierContext(getProviders(), new Assumptions(false), getCodeCache().getTarget(), OptimisticOptimizations.ALL, graph.method().getProfilingInfo(), null);
-            new InliningPhase(new InliningPhase.InlineEverythingPolicy(), new CanonicalizerPhase(true)).apply(graph, highContext);
+            new InliningPhase(new InlineEverythingPolicy(), new CanonicalizerPhase(true)).apply(graph, highContext);
             new LoweringPhase(new CanonicalizerPhase(true), LoweringTool.StandardLoweringStage.HIGH_TIER).apply(graph, highContext);
             new GuardLoweringPhase().apply(graph, midContext);
             new LoweringPhase(new CanonicalizerPhase(true), LoweringTool.StandardLoweringStage.MID_TIER).apply(graph, midContext);

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/ComputeInliningRelevance.java	Thu May 15 16:45:08 2014 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,324 +0,0 @@
-/*
- * Copyright (c) 2013, 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.inlining;
-
-import static com.oracle.graal.graph.util.CollectionsAccess.*;
-
-import java.util.*;
-import java.util.function.*;
-
-import com.oracle.graal.graph.*;
-import com.oracle.graal.nodes.*;
-
-import edu.umd.cs.findbugs.annotations.*;
-
-public class ComputeInliningRelevance {
-
-    private static final double EPSILON = 1d / Integer.MAX_VALUE;
-    private static final double UNINITIALIZED = -1D;
-
-    private static final int EXPECTED_MIN_INVOKE_COUNT = 3;
-    private static final int EXPECTED_INVOKE_RATIO = 20;
-    private static final int EXPECTED_LOOP_COUNT = 3;
-
-    private final StructuredGraph graph;
-    private final ToDoubleFunction<FixedNode> nodeProbabilities;
-
-    /**
-     * Node relevances are pre-computed for all invokes if the graph contains loops. If there are no
-     * loops, the computation happens lazily based on {@link #rootScope}.
-     */
-    private Map<FixedNode, Double> nodeRelevances;
-    /**
-     * This scope is non-null if (and only if) there are no loops in the graph. In this case, the
-     * root scope is used to compute invoke relevances on the fly.
-     */
-    private Scope rootScope;
-
-    public ComputeInliningRelevance(StructuredGraph graph, ToDoubleFunction<FixedNode> nodeProbabilities) {
-        this.graph = graph;
-        this.nodeProbabilities = nodeProbabilities;
-    }
-
-    /**
-     * Initializes or updates the relevance computation. If there are no loops within the graph,
-     * most computation happens lazily.
-     */
-    public void compute() {
-        rootScope = null;
-        if (!graph.hasLoops()) {
-            // fast path for the frequent case of no loops
-            rootScope = new Scope(graph.start(), null);
-        } else {
-            if (nodeRelevances == null) {
-                nodeRelevances = newNodeIdentityMap(EXPECTED_MIN_INVOKE_COUNT + graph.getNodeCount() / EXPECTED_INVOKE_RATIO);
-            }
-            NodeWorkList workList = graph.createNodeWorkList();
-            Map<LoopBeginNode, Scope> loops = newNodeIdentityMap(EXPECTED_LOOP_COUNT);
-
-            loops.put(null, new Scope(graph.start(), null));
-            for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.class)) {
-                createLoopScope(loopBegin, loops);
-            }
-
-            for (Scope scope : loops.values()) {
-                scope.process(workList);
-            }
-        }
-    }
-
-    public double getRelevance(Invoke invoke) {
-        if (rootScope != null) {
-            return rootScope.computeInvokeRelevance(invoke);
-        }
-        assert nodeRelevances != null : "uninitialized relevance";
-        return nodeRelevances.get(invoke);
-    }
-
-    /**
-     * Determines the parent of the given loop and creates a {@link Scope} object for each one. This
-     * method will call itself recursively if no {@link Scope} for the parent loop exists.
-     */
-    private Scope createLoopScope(LoopBeginNode loopBegin, Map<LoopBeginNode, Scope> loops) {
-        Scope scope = loops.get(loopBegin);
-        if (scope == null) {
-            final Scope parent;
-            // look for the parent scope
-            FixedNode current = loopBegin.forwardEnd();
-            while (true) {
-                if (current.predecessor() == null) {
-                    if (current instanceof LoopBeginNode) {
-                        // if we reach a LoopBeginNode then we're within this loop
-                        parent = createLoopScope((LoopBeginNode) current, loops);
-                        break;
-                    } else if (current instanceof StartNode) {
-                        // we're within the outermost scope
-                        parent = loops.get(null);
-                        break;
-                    } else {
-                        assert current.getClass() == MergeNode.class : current;
-                        // follow any path upwards - it doesn't matter which one
-                        current = ((MergeNode) current).forwardEndAt(0);
-                    }
-                } else if (current instanceof LoopExitNode) {
-                    // if we reach a loop exit then we follow this loop and have the same parent
-                    parent = createLoopScope(((LoopExitNode) current).loopBegin(), loops).parent;
-                    break;
-                } else {
-                    current = (FixedNode) current.predecessor();
-                }
-            }
-            scope = new Scope(loopBegin, parent);
-            loops.put(loopBegin, scope);
-        }
-        return scope;
-    }
-
-    /**
-     * A scope holds information for the contents of one loop or of the root of the method. It does
-     * not include child loops, i.e., the iteration in {@link #process(NodeWorkList)} explicitly
-     * excludes the nodes of child loops.
-     */
-    private class Scope {
-        public final FixedNode start;
-        public final Scope parent; // can be null for the outermost scope
-
-        /**
-         * The minimum probability along the most probable path in this scope. Computed lazily.
-         */
-        private double fastPathMinProbability = UNINITIALIZED;
-        /**
-         * A measure of how important this scope is within its parent scope. Computed lazily.
-         */
-        private double scopeRelevanceWithinParent = UNINITIALIZED;
-
-        public Scope(FixedNode start, Scope parent) {
-            this.start = start;
-            this.parent = parent;
-        }
-
-        @SuppressFBWarnings("FE_FLOATING_POINT_EQUALITY")
-        public double getFastPathMinProbability() {
-            if (fastPathMinProbability == UNINITIALIZED) {
-                fastPathMinProbability = Math.max(EPSILON, computeFastPathMinProbability(start));
-            }
-            return fastPathMinProbability;
-        }
-
-        /**
-         * Computes the ratio between the probabilities of the current scope's entry point and the
-         * parent scope's fastPathMinProbability.
-         */
-        @SuppressFBWarnings("FE_FLOATING_POINT_EQUALITY")
-        public double getScopeRelevanceWithinParent() {
-            if (scopeRelevanceWithinParent == UNINITIALIZED) {
-                if (start instanceof LoopBeginNode) {
-                    assert parent != null;
-                    double scopeEntryProbability = nodeProbabilities.applyAsDouble(((LoopBeginNode) start).forwardEnd());
-
-                    scopeRelevanceWithinParent = scopeEntryProbability / parent.getFastPathMinProbability();
-                } else {
-                    scopeRelevanceWithinParent = 1D;
-                }
-            }
-            return scopeRelevanceWithinParent;
-        }
-
-        /**
-         * Processes all invokes in this scope by starting at the scope's start node and iterating
-         * all fixed nodes. Child loops are skipped by going from loop entries directly to the loop
-         * exits. Processing stops at loop exits of the current loop.
-         */
-        public void process(NodeWorkList workList) {
-            assert !(start instanceof Invoke);
-            workList.addAll(start.successors());
-
-            for (Node current : workList) {
-                assert current.isAlive();
-
-                if (current instanceof Invoke) {
-                    // process the invoke and queue its successors
-                    nodeRelevances.put((FixedNode) current, computeInvokeRelevance((Invoke) current));
-                    workList.addAll(current.successors());
-                } else if (current instanceof LoopBeginNode) {
-                    // skip child loops by advancing over the loop exits
-                    ((LoopBeginNode) current).loopExits().forEach(exit -> workList.add(exit.next()));
-                } else if (current instanceof LoopEndNode) {
-                    // nothing to do
-                } else if (current instanceof LoopExitNode) {
-                    // nothing to do
-                } else if (current instanceof FixedWithNextNode) {
-                    workList.add(((FixedWithNextNode) current).next());
-                } else if (current instanceof EndNode) {
-                    workList.add(((EndNode) current).merge());
-                } else if (current instanceof ControlSinkNode) {
-                    // nothing to do
-                } else if (current instanceof ControlSplitNode) {
-                    workList.addAll(current.successors());
-                } else {
-                    assert false : current;
-                }
-            }
-        }
-
-        /**
-         * The relevance of an invoke is the ratio between the invoke's probability and the current
-         * scope's fastPathMinProbability, adjusted by scopeRelevanceWithinParent.
-         */
-        public double computeInvokeRelevance(Invoke invoke) {
-            double invokeProbability = nodeProbabilities.applyAsDouble(invoke.asNode());
-            assert !Double.isNaN(invokeProbability);
-
-            double relevance = (invokeProbability / getFastPathMinProbability()) * Math.min(1.0, getScopeRelevanceWithinParent());
-            assert !Double.isNaN(relevance) : invoke + ": " + relevance + " / " + invokeProbability + " / " + getFastPathMinProbability() + " / " + getScopeRelevanceWithinParent();
-            return relevance;
-        }
-    }
-
-    /**
-     * Computes the minimum probability along the most probable path within the scope. During
-     * iteration, the method returns immediately once a loop exit is discovered.
-     */
-    private double computeFastPathMinProbability(FixedNode scopeStart) {
-        ArrayList<FixedNode> pathBeginNodes = new ArrayList<>();
-        pathBeginNodes.add(scopeStart);
-        double minPathProbability = nodeProbabilities.applyAsDouble(scopeStart);
-        boolean isLoopScope = scopeStart instanceof LoopBeginNode;
-
-        do {
-            Node current = pathBeginNodes.remove(pathBeginNodes.size() - 1);
-            do {
-                if (isLoopScope && current instanceof LoopExitNode && ((LoopBeginNode) scopeStart).loopExits().contains((LoopExitNode) current)) {
-                    return minPathProbability;
-                } else if (current instanceof LoopBeginNode && current != scopeStart) {
-                    current = getMaxProbabilityLoopExit((LoopBeginNode) current, pathBeginNodes);
-                    minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability);
-                } else if (current instanceof ControlSplitNode) {
-                    current = getMaxProbabilitySux((ControlSplitNode) current, pathBeginNodes);
-                    minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability);
-                } else {
-                    assert current.successors().count() <= 1;
-                    current = current.successors().first();
-                }
-            } while (current != null);
-        } while (!pathBeginNodes.isEmpty());
-
-        return minPathProbability;
-    }
-
-    private double getMinPathProbability(FixedNode current, double minPathProbability) {
-        return current == null ? minPathProbability : Math.min(minPathProbability, nodeProbabilities.applyAsDouble(current));
-    }
-
-    /**
-     * Returns the most probable successor. If multiple successors share the maximum probability,
-     * one is returned and the others are enqueued in pathBeginNodes.
-     */
-    private static Node getMaxProbabilitySux(ControlSplitNode controlSplit, ArrayList<FixedNode> pathBeginNodes) {
-        Node maxSux = null;
-        double maxProbability = 0.0;
-        int pathBeginCount = pathBeginNodes.size();
-
-        for (Node sux : controlSplit.successors()) {
-            double probability = controlSplit.probability((BeginNode) sux);
-            if (probability > maxProbability) {
-                maxProbability = probability;
-                maxSux = sux;
-                truncate(pathBeginNodes, pathBeginCount);
-            } else if (probability == maxProbability) {
-                pathBeginNodes.add((FixedNode) sux);
-            }
-        }
-
-        return maxSux;
-    }
-
-    /**
-     * Returns the most probable loop exit. If multiple successors share the maximum probability,
-     * one is returned and the others are enqueued in pathBeginNodes.
-     */
-    private Node getMaxProbabilityLoopExit(LoopBeginNode loopBegin, ArrayList<FixedNode> pathBeginNodes) {
-        Node maxSux = null;
-        double maxProbability = 0.0;
-        int pathBeginCount = pathBeginNodes.size();
-
-        for (LoopExitNode sux : loopBegin.loopExits()) {
-            double probability = nodeProbabilities.applyAsDouble(sux);
-            if (probability > maxProbability) {
-                maxProbability = probability;
-                maxSux = sux;
-                truncate(pathBeginNodes, pathBeginCount);
-            } else if (probability == maxProbability) {
-                pathBeginNodes.add(sux);
-            }
-        }
-
-        return maxSux;
-    }
-
-    private static void truncate(ArrayList<FixedNode> pathBeginNodes, int pathBeginCount) {
-        for (int i = pathBeginNodes.size() - pathBeginCount; i > 0; i--) {
-            pathBeginNodes.remove(pathBeginNodes.size() - 1);
-        }
-    }
-}

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/DepthSearchUtil.java	Thu May 15 16:45:08 2014 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,149 +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.inlining;
-
-import com.oracle.graal.api.meta.Constant;
-import com.oracle.graal.api.meta.ResolvedJavaMethod;
-import com.oracle.graal.compiler.common.type.Stamp;
-import com.oracle.graal.debug.Debug;
-import com.oracle.graal.graph.NodeInputList;
-import com.oracle.graal.nodes.*;
-import com.oracle.graal.phases.common.CanonicalizerPhase;
-import com.oracle.graal.phases.common.DeadCodeEliminationPhase;
-import com.oracle.graal.phases.tiers.HighTierContext;
-
-import static com.oracle.graal.compiler.common.GraalOptions.OptCanonicalizer;
-
-/**
- * The workings of {@link InliningPhase#run(StructuredGraph, HighTierContext)} include delving into
- * a callsite to explore inlining opportunities. The utilities used for that are grouped in this
- * class.
- */
-public class DepthSearchUtil {
-
-    private DepthSearchUtil() {
-        // no instances
-    }
-
-    static InliningUtil.Inlineable getInlineableElement(final ResolvedJavaMethod method, Invoke invoke, HighTierContext context, CanonicalizerPhase canonicalizer) {
-        Class<? extends FixedWithNextNode> macroNodeClass = InliningUtil.getMacroNodeClass(context.getReplacements(), method);
-        if (macroNodeClass != null) {
-            return new InliningUtil.InlineableMacroNode(macroNodeClass);
-        } else {
-            return new InliningUtil.InlineableGraph(buildGraph(method, invoke, context, canonicalizer));
-        }
-    }
-
-    private static StructuredGraph buildGraph(final ResolvedJavaMethod method, final Invoke invoke, final HighTierContext context, CanonicalizerPhase canonicalizer) {
-        final StructuredGraph newGraph;
-        final boolean parseBytecodes;
-
-        // TODO (chaeubl): copying the graph is only necessary if it is modified or if it contains
-        // any invokes
-        StructuredGraph intrinsicGraph = InliningUtil.getIntrinsicGraph(context.getReplacements(), method);
-        if (intrinsicGraph != null) {
-            newGraph = intrinsicGraph.copy();
-            parseBytecodes = false;
-        } else {
-            StructuredGraph cachedGraph = getCachedGraph(method, context);
-            if (cachedGraph != null) {
-                newGraph = cachedGraph.copy();
-                parseBytecodes = false;
-            } else {
-                newGraph = new StructuredGraph(method);
-                parseBytecodes = true;
-            }
-        }
-
-        try (Debug.Scope s = Debug.scope("InlineGraph", newGraph)) {
-            if (parseBytecodes) {
-                parseBytecodes(newGraph, context, canonicalizer);
-            }
-
-            boolean callerHasMoreInformationAboutArguments = false;
-            NodeInputList<ValueNode> args = invoke.callTarget().arguments();
-            for (ParameterNode param : newGraph.getNodes(ParameterNode.class).snapshot()) {
-                ValueNode arg = args.get(param.index());
-                if (arg.isConstant()) {
-                    Constant constant = arg.asConstant();
-                    newGraph.replaceFloating(param, ConstantNode.forConstant(constant, context.getMetaAccess(), newGraph));
-                    callerHasMoreInformationAboutArguments = true;
-                } else {
-                    Stamp joinedStamp = param.stamp().join(arg.stamp());
-                    if (joinedStamp != null && !joinedStamp.equals(param.stamp())) {
-                        param.setStamp(joinedStamp);
-                        callerHasMoreInformationAboutArguments = true;
-                    }
-                }
-            }
-
-            if (!callerHasMoreInformationAboutArguments) {
-                // TODO (chaeubl): if args are not more concrete, inlining should be avoided
-                // in most cases or we could at least use the previous graph size + invoke
-                // probability to check the inlining
-            }
-
-            if (OptCanonicalizer.getValue()) {
-                canonicalizer.apply(newGraph, context);
-            }
-
-            return newGraph;
-        } catch (Throwable e) {
-            throw Debug.handle(e);
-        }
-    }
-
-    private static StructuredGraph getCachedGraph(ResolvedJavaMethod method, HighTierContext context) {
-        if (context.getGraphCache() != null) {
-            StructuredGraph cachedGraph = context.getGraphCache().get(method);
-            if (cachedGraph != null) {
-                return cachedGraph;
-            }
-        }
-        return null;
-    }
-
-    /**
-     * This method builds the IR nodes for <code>newGraph</code> and canonicalizes them. Provided
-     * profiling info is mature, the resulting graph is cached.
-     */
-    private static StructuredGraph parseBytecodes(StructuredGraph newGraph, HighTierContext context, CanonicalizerPhase canonicalizer) {
-        final boolean hasMatureProfilingInfo = newGraph.method().getProfilingInfo().isMature();
-
-        if (context.getGraphBuilderSuite() != null) {
-            context.getGraphBuilderSuite().apply(newGraph, context);
-        }
-        assert newGraph.start().next() != null : "graph needs to be populated during PhasePosition.AFTER_PARSING";
-
-        new DeadCodeEliminationPhase().apply(newGraph);
-
-        if (OptCanonicalizer.getValue()) {
-            canonicalizer.apply(newGraph, context);
-        }
-
-        if (hasMatureProfilingInfo && context.getGraphCache() != null) {
-            context.getGraphCache().put(newGraph.method(), newGraph.copy());
-        }
-        return newGraph;
-    }
-}

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/InliningIterator.java	Thu May 15 16:45:08 2014 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,130 +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.inlining;
-
-import com.oracle.graal.graph.Node;
-import com.oracle.graal.graph.NodeBitMap;
-import com.oracle.graal.nodes.*;
-import com.oracle.graal.nodes.java.MethodCallTargetNode;
-
-import java.util.ArrayDeque;
-import java.util.Deque;
-import java.util.LinkedList;
-
-/**
- * Given a graph, visit all fixed nodes in dominator-based order, collecting in the process the
- * {@link Invoke} nodes with {@link MethodCallTargetNode}. Such list of callsites is returned by
- * {@link #apply()}
- */
-class InliningIterator {
-
-    private final StartNode start;
-    private final Deque<FixedNode> nodeQueue;
-    private final NodeBitMap queuedNodes;
-
-    public InliningIterator(StructuredGraph graph) {
-        this.start = graph.start();
-        this.nodeQueue = new ArrayDeque<>();
-        this.queuedNodes = graph.createNodeBitMap();
-        assert start.isAlive();
-    }
-
-    public LinkedList<Invoke> apply() {
-        LinkedList<Invoke> invokes = new LinkedList<>();
-        FixedNode current;
-        forcedQueue(start);
-
-        while ((current = nextQueuedNode()) != null) {
-            assert current.isAlive();
-
-            if (current instanceof Invoke && ((Invoke) current).callTarget() instanceof MethodCallTargetNode) {
-                if (current != start) {
-                    invokes.addLast((Invoke) current);
-                }
-                queueSuccessors(current);
-            } else if (current instanceof LoopBeginNode) {
-                queueSuccessors(current);
-            } else if (current instanceof LoopEndNode) {
-                // nothing to do
-            } else if (current instanceof MergeNode) {
-                queueSuccessors(current);
-            } else if (current instanceof FixedWithNextNode) {
-                queueSuccessors(current);
-            } else if (current instanceof EndNode) {
-                queueMerge((EndNode) current);
-            } else if (current instanceof ControlSinkNode) {
-                // nothing to do
-            } else if (current instanceof ControlSplitNode) {
-                queueSuccessors(current);
-            } else {
-                assert false : current;
-            }
-        }
-
-        return invokes;
-    }
-
-    private void queueSuccessors(FixedNode x) {
-        for (Node node : x.successors()) {
-            queue(node);
-        }
-    }
-
-    private void queue(Node node) {
-        if (node != null && !queuedNodes.isMarked(node)) {
-            forcedQueue(node);
-        }
-    }
-
-    private void forcedQueue(Node 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(AbstractEndNode 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 (!queuedNodes.isMarked(merge.forwardEndAt(i))) {
-                return false;
-            }
-        }
-        return true;
-    }
-}

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/InliningPhase.java	Thu May 15 16:45:08 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/InliningPhase.java	Thu May 15 17:25:49 2014 +0200
@@ -22,36 +22,23 @@
  */
 package com.oracle.graal.phases.common.inlining;
 
-import static com.oracle.graal.compiler.common.GraalOptions.*;
-import static com.oracle.graal.phases.common.inlining.InliningPhase.Options.*;
-
 import java.util.*;
 import java.util.function.*;
 
-import com.oracle.graal.api.code.*;
-import com.oracle.graal.api.meta.*;
-import com.oracle.graal.compiler.common.*;
-import com.oracle.graal.debug.*;
-import com.oracle.graal.debug.Debug.Scope;
-import com.oracle.graal.graph.Graph.Mark;
-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.options.*;
 import com.oracle.graal.phases.common.*;
-import com.oracle.graal.phases.common.inlining.info.InlineInfo;
-import com.oracle.graal.phases.common.inlining.InliningUtil.Inlineable;
-import com.oracle.graal.phases.common.inlining.InliningUtil.InlineableGraph;
-import com.oracle.graal.phases.common.inlining.InliningUtil.InlineableMacroNode;
-import com.oracle.graal.phases.common.inlining.InliningUtil.InliningPolicy;
+import com.oracle.graal.phases.common.inlining.policy.GreedyInliningPolicy;
+import com.oracle.graal.phases.common.inlining.policy.InliningPolicy;
+import com.oracle.graal.phases.common.inlining.walker.CallsiteHolder;
+import com.oracle.graal.phases.common.inlining.walker.InliningData;
+import com.oracle.graal.phases.common.inlining.walker.MethodInvocation;
 import com.oracle.graal.phases.graph.*;
 import com.oracle.graal.phases.tiers.*;
-import com.oracle.graal.phases.util.*;
 
 public class InliningPhase extends AbstractInliningPhase {
 
-    static class Options {
+    public static class Options {
 
         // @formatter:off
         @Option(help = "Unconditionally inline intrinsics")
@@ -65,12 +52,6 @@
     private int inliningCount;
     private int maxMethodPerInlining = Integer.MAX_VALUE;
 
-    // Metrics
-    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("InliningRuns");
-
     public InliningPhase(CanonicalizerPhase canonicalizer) {
         this(new GreedyInliningPolicy(null), canonicalizer);
     }
@@ -95,16 +76,17 @@
     /**
      * <p>
      * The space of inlining decisions is explored depth-first with the help of a stack realized by
-     * {@link InliningData}. At any point in time, its topmost element consist of:
+     * {@link com.oracle.graal.phases.common.inlining.walker.InliningData}. At any point in time,
+     * its topmost element consist of:
      * <ul>
      * <li>
-     * one or more {@link GraphInfo}s of inlining candidates, all of them corresponding to a single
-     * callsite (details below). For example, "exact inline" leads to a single candidate.</li>
+     * one or more {@link CallsiteHolder}s of inlining candidates, all of them corresponding to a
+     * single callsite (details below). For example, "exact inline" leads to a single candidate.</li>
      * <li>
      * the callsite (for the targets above) is tracked as a {@link MethodInvocation}. The difference
-     * between {@link MethodInvocation#totalGraphs()} and {@link MethodInvocation#processedGraphs()}
-     * indicates the topmost {@link GraphInfo}s that might be delved-into to explore inlining
-     * opportunities.</li>
+     * between {@link com.oracle.graal.phases.common.inlining.walker.MethodInvocation#totalGraphs()}
+     * and {@link MethodInvocation#processedGraphs()} indicates the topmost {@link CallsiteHolder}s
+     * that might be delved-into to explore inlining opportunities.</li>
      * </ul>
      * </p>
      *
@@ -112,10 +94,11 @@
      * The bottom-most element in the stack consists of:
      * <ul>
      * <li>
-     * a single {@link GraphInfo} (the root one, for the method on which inlining was called)</li>
+     * a single {@link CallsiteHolder} (the root one, for the method on which inlining was called)</li>
      * <li>
-     * a single {@link MethodInvocation} (the {@link MethodInvocation#isRoot} one, ie the unknown
-     * caller of the root graph)</li>
+     * a single {@link MethodInvocation} (the
+     * {@link com.oracle.graal.phases.common.inlining.walker.MethodInvocation#isRoot} one, ie the
+     * unknown caller of the root graph)</li>
      * </ul>
      *
      * </p>
@@ -132,7 +115,8 @@
      * <li>
      * try to inline: move past the current inlining candidate (remove it from the topmost element).
      * If that was the last one then try to inline the callsite that is (still) in the topmost
-     * element of {@link InliningData}, and then remove such callsite.</li>
+     * element of {@link com.oracle.graal.phases.common.inlining.walker.InliningData}, and then
+     * remove such callsite.</li>
      * </ol>
      * </p>
      *
@@ -156,35 +140,13 @@
      */
     @Override
     protected void run(final StructuredGraph graph, final HighTierContext context) {
-        final InliningData data = new InliningData(graph, context.getAssumptions(), maxMethodPerInlining, canonicalizer);
+        final InliningData data = new InliningData(graph, context.getAssumptions(), maxMethodPerInlining, canonicalizer, inliningPolicy);
         ToDoubleFunction<FixedNode> probabilities = new FixedNodeProbabilityCache();
 
         while (data.hasUnprocessedGraphs()) {
-            final MethodInvocation currentInvocation = data.currentInvocation();
-            if (!currentInvocation.isRoot() &&
-                            !inliningPolicy.isWorthInlining(probabilities, context.getReplacements(), currentInvocation.callee(), data.inliningDepth(), currentInvocation.probability(),
-                                            currentInvocation.relevance(), false)) {
-                int remainingGraphs = currentInvocation.totalGraphs() - currentInvocation.processedGraphs();
-                assert remainingGraphs > 0;
-                data.popGraphs(remainingGraphs);
-                data.popInvocation();
-            } else if (data.currentGraph().hasRemainingInvokes() && inliningPolicy.continueInlining(data.currentGraph().graph())) {
-                data.processNextInvoke(context);
-            } else {
-                data.popGraph();
-                if (!currentInvocation.isRoot()) {
-                    assert currentInvocation.callee().invoke().asNode().isAlive();
-                    currentInvocation.incrementProcessedGraphs();
-                    if (currentInvocation.processedGraphs() == currentInvocation.totalGraphs()) {
-                        data.popInvocation();
-                        final MethodInvocation parentInvoke = data.currentInvocation();
-                        try (Scope s = Debug.scope("Inlining", data.inliningContext())) {
-                            tryToInline(probabilities, data.currentGraph(), currentInvocation, parentInvoke, data.inliningDepth() + 1, context);
-                        } catch (Throwable e) {
-                            throw Debug.handle(e);
-                        }
-                    }
-                }
+            boolean wasInlined = data.moveForward(context, probabilities);
+            if (wasInlined) {
+                inliningCount++;
             }
         }
 
@@ -192,552 +154,4 @@
         assert data.graphCount() == 0;
     }
 
-    private void tryToInline(ToDoubleFunction<FixedNode> probabilities, GraphInfo callerGraphInfo, MethodInvocation calleeInfo, MethodInvocation parentInvocation, int inliningDepth,
-                    HighTierContext context) {
-        InlineInfo callee = calleeInfo.callee();
-        Assumptions callerAssumptions = parentInvocation.assumptions();
-
-        if (inliningPolicy.isWorthInlining(probabilities, context.getReplacements(), callee, inliningDepth, calleeInfo.probability(), calleeInfo.relevance(), true)) {
-            doInline(callerGraphInfo, calleeInfo, callerAssumptions, context);
-        } else if (context.getOptimisticOptimizations().devirtualizeInvokes()) {
-            callee.tryToDevirtualizeInvoke(context.getMetaAccess(), callerAssumptions);
-        }
-        metricInliningConsidered.increment();
-    }
-
-    private void doInline(GraphInfo callerGraphInfo, MethodInvocation calleeInfo, Assumptions callerAssumptions, HighTierContext context) {
-        StructuredGraph callerGraph = callerGraphInfo.graph();
-        Mark markBeforeInlining = callerGraph.getMark();
-        InlineInfo callee = calleeInfo.callee();
-        try {
-            try (Scope scope = Debug.scope("doInline", callerGraph)) {
-                List<Node> invokeUsages = callee.invoke().asNode().usages().snapshot();
-                callee.inline(new Providers(context), callerAssumptions);
-                callerAssumptions.record(calleeInfo.assumptions());
-                metricInliningRuns.increment();
-                Debug.dump(callerGraph, "after %s", callee);
-
-                if (OptCanonicalizer.getValue()) {
-                    Mark markBeforeCanonicalization = callerGraph.getMark();
-                    canonicalizer.applyIncremental(callerGraph, context, invokeUsages, markBeforeInlining);
-
-                    // process invokes that are possibly created during canonicalization
-                    for (Node newNode : callerGraph.getNewNodes(markBeforeCanonicalization)) {
-                        if (newNode instanceof Invoke) {
-                            callerGraphInfo.pushInvoke((Invoke) newNode);
-                        }
-                    }
-                }
-
-                callerGraphInfo.computeProbabilities();
-
-                inliningCount++;
-                metricInliningPerformed.increment();
-            }
-        } catch (BailoutException bailout) {
-            throw bailout;
-        } catch (AssertionError | RuntimeException e) {
-            throw new GraalInternalError(e).addContext(callee.toString());
-        } catch (GraalInternalError e) {
-            throw e.addContext(callee.toString());
-        }
-    }
-
-    private abstract static class AbstractInliningPolicy implements InliningPolicy {
-
-        protected final Map<Invoke, Double> hints;
-
-        public AbstractInliningPolicy(Map<Invoke, Double> hints) {
-            this.hints = hints;
-        }
-
-        protected double computeMaximumSize(double relevance, int configuredMaximum) {
-            double inlineRatio = Math.min(RelevanceCapForInlining.getValue(), relevance);
-            return configuredMaximum * inlineRatio;
-        }
-
-        protected double getInliningBonus(InlineInfo info) {
-            if (hints != null && hints.containsKey(info.invoke())) {
-                return hints.get(info.invoke());
-            }
-            return 1;
-        }
-
-        protected boolean isIntrinsic(Replacements replacements, InlineInfo info) {
-            if (AlwaysInlineIntrinsics.getValue()) {
-                return onlyIntrinsics(replacements, info);
-            } else {
-                return onlyForcedIntrinsics(replacements, info);
-            }
-        }
-
-        private static boolean onlyIntrinsics(Replacements replacements, InlineInfo info) {
-            for (int i = 0; i < info.numberOfMethods(); i++) {
-                if (!InliningUtil.canIntrinsify(replacements, info.methodAt(i))) {
-                    return false;
-                }
-            }
-            return true;
-        }
-
-        private static boolean onlyForcedIntrinsics(Replacements replacements, InlineInfo info) {
-            for (int i = 0; i < info.numberOfMethods(); i++) {
-                if (!InliningUtil.canIntrinsify(replacements, info.methodAt(i))) {
-                    return false;
-                }
-                if (!replacements.isForcedSubstitution(info.methodAt(i))) {
-                    return false;
-                }
-            }
-            return true;
-        }
-
-        protected static int previousLowLevelGraphSize(InlineInfo info) {
-            int size = 0;
-            for (int i = 0; i < info.numberOfMethods(); i++) {
-                ResolvedJavaMethod m = info.methodAt(i);
-                ProfilingInfo profile = m.getProfilingInfo();
-                int compiledGraphSize = profile.getCompilerIRSize(StructuredGraph.class);
-                if (compiledGraphSize > 0) {
-                    size += compiledGraphSize;
-                }
-            }
-            return size;
-        }
-
-        protected static int determineNodeCount(InlineInfo info) {
-            int nodes = 0;
-            for (int i = 0; i < info.numberOfMethods(); i++) {
-                Inlineable elem = info.inlineableElementAt(i);
-                if (elem != null) {
-                    nodes += elem.getNodeCount();
-                }
-            }
-            return nodes;
-        }
-
-        protected static double determineInvokeProbability(ToDoubleFunction<FixedNode> probabilities, InlineInfo info) {
-            double invokeProbability = 0;
-            for (int i = 0; i < info.numberOfMethods(); i++) {
-                Inlineable callee = info.inlineableElementAt(i);
-                Iterable<Invoke> invokes = callee.getInvokes();
-                if (invokes.iterator().hasNext()) {
-                    for (Invoke invoke : invokes) {
-                        invokeProbability += probabilities.applyAsDouble(invoke.asNode());
-                    }
-                }
-            }
-            return invokeProbability;
-        }
-    }
-
-    public static class GreedyInliningPolicy extends AbstractInliningPolicy {
-
-        public GreedyInliningPolicy(Map<Invoke, Double> hints) {
-            super(hints);
-        }
-
-        public boolean continueInlining(StructuredGraph currentGraph) {
-            if (currentGraph.getNodeCount() >= MaximumDesiredSize.getValue()) {
-                InliningUtil.logInliningDecision("inlining is cut off by MaximumDesiredSize");
-                metricInliningStoppedByMaxDesiredSize.increment();
-                return false;
-            }
-            return true;
-        }
-
-        @Override
-        public boolean isWorthInlining(ToDoubleFunction<FixedNode> probabilities, Replacements replacements, InlineInfo info, int inliningDepth, double probability, double relevance,
-                        boolean fullyProcessed) {
-            if (InlineEverything.getValue()) {
-                return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "inline everything");
-            }
-
-            if (isIntrinsic(replacements, info)) {
-                return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "intrinsic");
-            }
-
-            if (info.shouldInline()) {
-                return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "forced inlining");
-            }
-
-            double inliningBonus = getInliningBonus(info);
-            int nodes = determineNodeCount(info);
-            int lowLevelGraphSize = previousLowLevelGraphSize(info);
-
-            if (SmallCompiledLowLevelGraphSize.getValue() > 0 && lowLevelGraphSize > SmallCompiledLowLevelGraphSize.getValue() * inliningBonus) {
-                return InliningUtil.logNotInlinedMethod(info, inliningDepth, "too large previous low-level graph (low-level-nodes: %d, relevance=%f, probability=%f, bonus=%f, nodes=%d)",
-                                lowLevelGraphSize, relevance, probability, inliningBonus, nodes);
-            }
-
-            if (nodes < TrivialInliningSize.getValue() * inliningBonus) {
-                return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "trivial (relevance=%f, probability=%f, bonus=%f, nodes=%d)", relevance, probability, inliningBonus, nodes);
-            }
-
-            /*
-             * TODO (chaeubl): invoked methods that are on important paths but not yet compiled ->
-             * will be compiled anyways and it is likely that we are the only caller... might be
-             * useful to inline those methods but increases bootstrap time (maybe those methods are
-             * also getting queued in the compilation queue concurrently)
-             */
-            double invokes = determineInvokeProbability(probabilities, info);
-            if (LimitInlinedInvokes.getValue() > 0 && fullyProcessed && invokes > LimitInlinedInvokes.getValue() * inliningBonus) {
-                return InliningUtil.logNotInlinedMethod(info, inliningDepth, "callee invoke probability is too high (invokeP=%f, relevance=%f, probability=%f, bonus=%f, nodes=%d)", invokes,
-                                relevance, probability, inliningBonus, nodes);
-            }
-
-            double maximumNodes = computeMaximumSize(relevance, (int) (MaximumInliningSize.getValue() * inliningBonus));
-            if (nodes <= maximumNodes) {
-                return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "relevance-based (relevance=%f, probability=%f, bonus=%f, nodes=%d <= %f)", relevance, probability,
-                                inliningBonus, nodes, maximumNodes);
-            }
-
-            return InliningUtil.logNotInlinedMethod(info, inliningDepth, "relevance-based (relevance=%f, probability=%f, bonus=%f, nodes=%d > %f)", relevance, probability, inliningBonus, nodes,
-                            maximumNodes);
-        }
-    }
-
-    public static final class InlineEverythingPolicy implements InliningPolicy {
-
-        public boolean continueInlining(StructuredGraph graph) {
-            if (graph.getNodeCount() >= MaximumDesiredSize.getValue()) {
-                throw new BailoutException("Inline all calls failed. The resulting graph is too large.");
-            }
-            return true;
-        }
-
-        public boolean isWorthInlining(ToDoubleFunction<FixedNode> probabilities, Replacements replacements, InlineInfo info, int inliningDepth, double probability, double relevance,
-                        boolean fullyProcessed) {
-            return true;
-        }
-    }
-
-    /**
-     * Holds the data for building the callee graphs recursively: graphs and invocations (each
-     * invocation can have multiple graphs).
-     */
-    static class InliningData {
-
-        private static final GraphInfo DummyGraphInfo = new GraphInfo(null, 1.0, 1.0);
-
-        /**
-         * Call hierarchy from outer most call (i.e., compilation unit) to inner most callee.
-         */
-        private final ArrayDeque<GraphInfo> graphQueue;
-        private final ArrayDeque<MethodInvocation> invocationQueue;
-        private final int maxMethodPerInlining;
-        private final CanonicalizerPhase canonicalizer;
-
-        private int maxGraphs;
-
-        public InliningData(StructuredGraph rootGraph, Assumptions rootAssumptions, int maxMethodPerInlining, CanonicalizerPhase canonicalizer) {
-            this.graphQueue = new ArrayDeque<>();
-            this.invocationQueue = new ArrayDeque<>();
-            this.maxMethodPerInlining = maxMethodPerInlining;
-            this.canonicalizer = canonicalizer;
-            this.maxGraphs = 1;
-
-            invocationQueue.push(new MethodInvocation(null, rootAssumptions, 1.0, 1.0));
-            pushGraph(rootGraph, 1.0, 1.0);
-        }
-
-        /**
-         * Process the next invoke and enqueue all its graphs for processing.
-         */
-        void processNextInvoke(HighTierContext context) {
-            GraphInfo graphInfo = currentGraph();
-            Invoke invoke = graphInfo.popInvoke();
-            MethodInvocation callerInvocation = currentInvocation();
-            Assumptions parentAssumptions = callerInvocation.assumptions();
-            InlineInfo info = InliningUtil.getInlineInfo(this, invoke, maxMethodPerInlining, context.getReplacements(), parentAssumptions, context.getOptimisticOptimizations());
-
-            if (info != null) {
-                double invokeProbability = graphInfo.invokeProbability(invoke);
-                double invokeRelevance = graphInfo.invokeRelevance(invoke);
-                MethodInvocation calleeInvocation = pushInvocation(info, parentAssumptions, invokeProbability, invokeRelevance);
-
-                for (int i = 0; i < info.numberOfMethods(); i++) {
-                    Inlineable elem = DepthSearchUtil.getInlineableElement(info.methodAt(i), info.invoke(), context.replaceAssumptions(calleeInvocation.assumptions()), canonicalizer);
-                    info.setInlinableElement(i, elem);
-                    if (elem instanceof InlineableGraph) {
-                        pushGraph(((InlineableGraph) elem).getGraph(), invokeProbability * info.probabilityAt(i), invokeRelevance * info.relevanceAt(i));
-                    } else {
-                        assert elem instanceof InlineableMacroNode;
-                        pushDummyGraph();
-                    }
-                }
-            }
-        }
-
-        public int graphCount() {
-            return graphQueue.size();
-        }
-
-        private void pushGraph(StructuredGraph graph, double probability, double relevance) {
-            assert !contains(graph);
-            graphQueue.push(new GraphInfo(graph, probability, relevance));
-            assert graphQueue.size() <= maxGraphs;
-        }
-
-        private void pushDummyGraph() {
-            graphQueue.push(DummyGraphInfo);
-        }
-
-        public boolean hasUnprocessedGraphs() {
-            return !graphQueue.isEmpty();
-        }
-
-        public GraphInfo currentGraph() {
-            return graphQueue.peek();
-        }
-
-        public void popGraph() {
-            graphQueue.pop();
-            assert graphQueue.size() <= maxGraphs;
-        }
-
-        public void popGraphs(int count) {
-            assert count >= 0;
-            for (int i = 0; i < count; i++) {
-                graphQueue.pop();
-            }
-        }
-
-        private static final Object[] NO_CONTEXT = {};
-
-        /**
-         * Gets the call hierarchy of this inlining from outer most call to inner most callee.
-         */
-        public Object[] inliningContext() {
-            if (!Debug.isDumpEnabled()) {
-                return NO_CONTEXT;
-            }
-            Object[] result = new Object[graphQueue.size()];
-            int i = 0;
-            for (GraphInfo g : graphQueue) {
-                result[i++] = g.graph.method();
-            }
-            return result;
-        }
-
-        public MethodInvocation currentInvocation() {
-            return invocationQueue.peekFirst();
-        }
-
-        private MethodInvocation pushInvocation(InlineInfo info, Assumptions assumptions, double probability, double relevance) {
-            MethodInvocation methodInvocation = new MethodInvocation(info, new Assumptions(assumptions.useOptimisticAssumptions()), probability, relevance);
-            invocationQueue.addFirst(methodInvocation);
-            maxGraphs += info.numberOfMethods();
-            assert graphQueue.size() <= maxGraphs;
-            return methodInvocation;
-        }
-
-        public void popInvocation() {
-            maxGraphs -= invocationQueue.peekFirst().callee.numberOfMethods();
-            assert graphQueue.size() <= maxGraphs;
-            invocationQueue.removeFirst();
-        }
-
-        public int countRecursiveInlining(ResolvedJavaMethod method) {
-            int count = 0;
-            for (GraphInfo graphInfo : graphQueue) {
-                if (method.equals(graphInfo.method())) {
-                    count++;
-                }
-            }
-            return count;
-        }
-
-        public int inliningDepth() {
-            assert invocationQueue.size() > 0;
-            return invocationQueue.size() - 1;
-        }
-
-        @Override
-        public String toString() {
-            StringBuilder result = new StringBuilder("Invocations: ");
-
-            for (MethodInvocation invocation : invocationQueue) {
-                if (invocation.callee() != null) {
-                    result.append(invocation.callee().numberOfMethods());
-                    result.append("x ");
-                    result.append(invocation.callee().invoke());
-                    result.append("; ");
-                }
-            }
-
-            result.append("\nGraphs: ");
-            for (GraphInfo graph : graphQueue) {
-                result.append(graph.graph());
-                result.append("; ");
-            }
-
-            return result.toString();
-        }
-
-        private boolean contains(StructuredGraph graph) {
-            for (GraphInfo info : graphQueue) {
-                if (info.graph() == graph) {
-                    return true;
-                }
-            }
-            return false;
-        }
-    }
-
-    private static class MethodInvocation {
-
-        private final InlineInfo callee;
-        private final Assumptions assumptions;
-        private final double probability;
-        private final double relevance;
-
-        private int processedGraphs;
-
-        public MethodInvocation(InlineInfo info, Assumptions assumptions, double probability, double relevance) {
-            this.callee = info;
-            this.assumptions = assumptions;
-            this.probability = probability;
-            this.relevance = relevance;
-        }
-
-        public void incrementProcessedGraphs() {
-            processedGraphs++;
-            assert processedGraphs <= callee.numberOfMethods();
-        }
-
-        public int processedGraphs() {
-            assert processedGraphs <= callee.numberOfMethods();
-            return processedGraphs;
-        }
-
-        public int totalGraphs() {
-            return callee.numberOfMethods();
-        }
-
-        public InlineInfo callee() {
-            return callee;
-        }
-
-        public Assumptions assumptions() {
-            return assumptions;
-        }
-
-        public double probability() {
-            return probability;
-        }
-
-        public double relevance() {
-            return relevance;
-        }
-
-        public boolean isRoot() {
-            return callee == null;
-        }
-
-        @Override
-        public String toString() {
-            if (isRoot()) {
-                return "<root>";
-            }
-            CallTargetNode callTarget = callee.invoke().callTarget();
-            if (callTarget instanceof MethodCallTargetNode) {
-                ResolvedJavaMethod calleeMethod = ((MethodCallTargetNode) callTarget).targetMethod();
-                return MetaUtil.format("Invoke#%H.%n(%p)", calleeMethod);
-            } else {
-                return "Invoke#" + callTarget.targetName();
-            }
-        }
-    }
-
-    /**
-     * Information about a graph that will potentially be inlined. This includes tracking the
-     * invocations in graph that will subject to inlining themselves.
-     */
-    private static class GraphInfo {
-
-        private final StructuredGraph graph;
-        private final LinkedList<Invoke> remainingInvokes;
-        private final double probability;
-        private final double relevance;
-
-        private final ToDoubleFunction<FixedNode> probabilities;
-        private final ComputeInliningRelevance computeInliningRelevance;
-
-        public GraphInfo(StructuredGraph graph, double probability, double relevance) {
-            this.graph = graph;
-            if (graph == null) {
-                this.remainingInvokes = new LinkedList<>();
-            } else {
-                LinkedList<Invoke> invokes = new InliningIterator(graph).apply();
-                assert invokes.size() == count(graph.getInvokes());
-                this.remainingInvokes = invokes;
-            }
-            this.probability = probability;
-            this.relevance = relevance;
-
-            if (graph != null && !remainingInvokes.isEmpty()) {
-                probabilities = new FixedNodeProbabilityCache();
-                computeInliningRelevance = new ComputeInliningRelevance(graph, probabilities);
-                computeProbabilities();
-            } else {
-                probabilities = null;
-                computeInliningRelevance = null;
-            }
-        }
-
-        private static int count(Iterable<Invoke> invokes) {
-            int count = 0;
-            Iterator<Invoke> iterator = invokes.iterator();
-            while (iterator.hasNext()) {
-                iterator.next();
-                count++;
-            }
-            return count;
-        }
-
-        /**
-         * Gets the method associated with the {@linkplain #graph() graph} represented by this
-         * object.
-         */
-        public ResolvedJavaMethod method() {
-            return graph.method();
-        }
-
-        public boolean hasRemainingInvokes() {
-            return !remainingInvokes.isEmpty();
-        }
-
-        /**
-         * The graph about which this object contains inlining information.
-         */
-        public StructuredGraph graph() {
-            return graph;
-        }
-
-        public Invoke popInvoke() {
-            return remainingInvokes.removeFirst();
-        }
-
-        public void pushInvoke(Invoke invoke) {
-            remainingInvokes.push(invoke);
-        }
-
-        public void computeProbabilities() {
-            computeInliningRelevance.compute();
-        }
-
-        public double invokeProbability(Invoke invoke) {
-            return probability * probabilities.applyAsDouble(invoke.asNode());
-        }
-
-        public double invokeRelevance(Invoke invoke) {
-            return Math.min(CapInheritedRelevance.getValue(), relevance) * computeInliningRelevance.getRelevance(invoke);
-        }
-
-        @Override
-        public String toString() {
-            return (graph != null ? MetaUtil.format("%H.%n(%p)", method()) : "<null method>") + remainingInvokes;
-        }
-    }
 }

--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/InliningUtil.java	Thu May 15 16:45:08 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/InliningUtil.java	Thu May 15 17:25:49 2014 +0200
@@ -28,7 +28,6 @@
 import static com.oracle.graal.compiler.common.type.StampFactory.*;
 
 import java.util.*;
-import java.util.function.*;
 
 import com.oracle.graal.api.code.*;
 import com.oracle.graal.api.code.Assumptions.Assumption;
@@ -50,8 +49,8 @@
 import com.oracle.graal.nodes.type.*;
 import com.oracle.graal.nodes.util.*;
 import com.oracle.graal.phases.*;
-import com.oracle.graal.phases.common.inlining.InliningPhase.*;
 import com.oracle.graal.phases.common.inlining.info.*;
+import com.oracle.graal.phases.common.inlining.walker.InliningData;
 
 public class InliningUtil {
 
@@ -63,13 +62,6 @@
      */
     public static final DebugMetric InlinedBytecodes = Debug.metric("InlinedBytecodes");
 
-    public interface InliningPolicy {
-
-        boolean continueInlining(StructuredGraph graph);
-
-        boolean isWorthInlining(ToDoubleFunction<FixedNode> probabilities, Replacements replacements, InlineInfo info, int inliningDepth, double probability, double relevance, boolean fullyProcessed);
-    }
-
     public interface Inlineable {
 
         int getNodeCount();

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/policy/AbstractInliningPolicy.java	Thu May 15 17:25:49 2014 +0200
@@ -0,0 +1,126 @@
+/*
+ * 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.inlining.policy;
+
+import com.oracle.graal.api.meta.ProfilingInfo;
+import com.oracle.graal.api.meta.ResolvedJavaMethod;
+import com.oracle.graal.nodes.FixedNode;
+import com.oracle.graal.nodes.Invoke;
+import com.oracle.graal.nodes.StructuredGraph;
+import com.oracle.graal.nodes.spi.Replacements;
+import com.oracle.graal.phases.common.inlining.InliningUtil;
+import com.oracle.graal.phases.common.inlining.info.InlineInfo;
+
+import java.util.Map;
+import java.util.function.ToDoubleFunction;
+
+import static com.oracle.graal.compiler.common.GraalOptions.RelevanceCapForInlining;
+import static com.oracle.graal.phases.common.inlining.InliningPhase.Options.AlwaysInlineIntrinsics;
+
+public abstract class AbstractInliningPolicy implements InliningPolicy {
+
+    protected final Map<Invoke, Double> hints;
+
+    public AbstractInliningPolicy(Map<Invoke, Double> hints) {
+        this.hints = hints;
+    }
+
+    protected double computeMaximumSize(double relevance, int configuredMaximum) {
+        double inlineRatio = Math.min(RelevanceCapForInlining.getValue(), relevance);
+        return configuredMaximum * inlineRatio;
+    }
+
+    protected double getInliningBonus(InlineInfo info) {
+        if (hints != null && hints.containsKey(info.invoke())) {
+            return hints.get(info.invoke());
+        }
+        return 1;
+    }
+
+    protected boolean isIntrinsic(Replacements replacements, InlineInfo info) {
+        if (AlwaysInlineIntrinsics.getValue()) {
+            return onlyIntrinsics(replacements, info);
+        } else {
+            return onlyForcedIntrinsics(replacements, info);
+        }
+    }
+
+    private static boolean onlyIntrinsics(Replacements replacements, InlineInfo info) {
+        for (int i = 0; i < info.numberOfMethods(); i++) {
+            if (!InliningUtil.canIntrinsify(replacements, info.methodAt(i))) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    private static boolean onlyForcedIntrinsics(Replacements replacements, InlineInfo info) {
+        for (int i = 0; i < info.numberOfMethods(); i++) {
+            if (!InliningUtil.canIntrinsify(replacements, info.methodAt(i))) {
+                return false;
+            }
+            if (!replacements.isForcedSubstitution(info.methodAt(i))) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    protected static int previousLowLevelGraphSize(InlineInfo info) {
+        int size = 0;
+        for (int i = 0; i < info.numberOfMethods(); i++) {
+            ResolvedJavaMethod m = info.methodAt(i);
+            ProfilingInfo profile = m.getProfilingInfo();
+            int compiledGraphSize = profile.getCompilerIRSize(StructuredGraph.class);
+            if (compiledGraphSize > 0) {
+                size += compiledGraphSize;
+            }
+        }
+        return size;
+    }
+
+    protected static int determineNodeCount(InlineInfo info) {
+        int nodes = 0;
+        for (int i = 0; i < info.numberOfMethods(); i++) {
+            InliningUtil.Inlineable elem = info.inlineableElementAt(i);
+            if (elem != null) {
+                nodes += elem.getNodeCount();
+            }
+        }
+        return nodes;
+    }
+
+    protected static double determineInvokeProbability(ToDoubleFunction<FixedNode> probabilities, InlineInfo info) {
+        double invokeProbability = 0;
+        for (int i = 0; i < info.numberOfMethods(); i++) {
+            InliningUtil.Inlineable callee = info.inlineableElementAt(i);
+            Iterable<Invoke> invokes = callee.getInvokes();
+            if (invokes.iterator().hasNext()) {
+                for (Invoke invoke : invokes) {
+                    invokeProbability += probabilities.applyAsDouble(invoke.asNode());
+                }
+            }
+        }
+        return invokeProbability;
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/policy/GreedyInliningPolicy.java	Thu May 15 17:25:49 2014 +0200
@@ -0,0 +1,105 @@
+/*
+ * 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.inlining.policy;
+
+import com.oracle.graal.debug.Debug;
+import com.oracle.graal.debug.DebugMetric;
+import com.oracle.graal.nodes.FixedNode;
+import com.oracle.graal.nodes.Invoke;
+import com.oracle.graal.nodes.StructuredGraph;
+import com.oracle.graal.nodes.spi.Replacements;
+import com.oracle.graal.phases.common.inlining.InliningUtil;
+import com.oracle.graal.phases.common.inlining.info.InlineInfo;
+
+import java.util.Map;
+import java.util.function.ToDoubleFunction;
+
+import static com.oracle.graal.compiler.common.GraalOptions.*;
+
+public class GreedyInliningPolicy extends AbstractInliningPolicy {
+
+    private static final DebugMetric metricInliningStoppedByMaxDesiredSize = Debug.metric("InliningStoppedByMaxDesiredSize");
+
+    public GreedyInliningPolicy(Map<Invoke, Double> hints) {
+        super(hints);
+    }
+
+    public boolean continueInlining(StructuredGraph currentGraph) {
+        if (currentGraph.getNodeCount() >= MaximumDesiredSize.getValue()) {
+            InliningUtil.logInliningDecision("inlining is cut off by MaximumDesiredSize");
+            metricInliningStoppedByMaxDesiredSize.increment();
+            return false;
+        }
+        return true;
+    }
+
+    @Override
+    public boolean isWorthInlining(ToDoubleFunction<FixedNode> probabilities, Replacements replacements, InlineInfo info, int inliningDepth, double probability, double relevance,
+                    boolean fullyProcessed) {
+        if (InlineEverything.getValue()) {
+            return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "inline everything");
+        }
+
+        if (isIntrinsic(replacements, info)) {
+            return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "intrinsic");
+        }
+
+        if (info.shouldInline()) {
+            return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "forced inlining");
+        }
+
+        double inliningBonus = getInliningBonus(info);
+        int nodes = determineNodeCount(info);
+        int lowLevelGraphSize = previousLowLevelGraphSize(info);
+
+        if (SmallCompiledLowLevelGraphSize.getValue() > 0 && lowLevelGraphSize > SmallCompiledLowLevelGraphSize.getValue() * inliningBonus) {
+            return InliningUtil.logNotInlinedMethod(info, inliningDepth, "too large previous low-level graph (low-level-nodes: %d, relevance=%f, probability=%f, bonus=%f, nodes=%d)",
+                            lowLevelGraphSize, relevance, probability, inliningBonus, nodes);
+        }
+
+        if (nodes < TrivialInliningSize.getValue() * inliningBonus) {
+            return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "trivial (relevance=%f, probability=%f, bonus=%f, nodes=%d)", relevance, probability, inliningBonus, nodes);
+        }
+
+        /*
+         * TODO (chaeubl): invoked methods that are on important paths but not yet compiled -> will
+         * be compiled anyways and it is likely that we are the only caller... might be useful to
+         * inline those methods but increases bootstrap time (maybe those methods are also getting
+         * queued in the compilation queue concurrently)
+         */
+        double invokes = determineInvokeProbability(probabilities, info);
+        if (LimitInlinedInvokes.getValue() > 0 && fullyProcessed && invokes > LimitInlinedInvokes.getValue() * inliningBonus) {
+            return InliningUtil.logNotInlinedMethod(info, inliningDepth, "callee invoke probability is too high (invokeP=%f, relevance=%f, probability=%f, bonus=%f, nodes=%d)", invokes, relevance,
+                            probability, inliningBonus, nodes);
+        }
+
+        double maximumNodes = computeMaximumSize(relevance, (int) (MaximumInliningSize.getValue() * inliningBonus));
+        if (nodes <= maximumNodes) {
+            return InliningUtil.logInlinedMethod(info, inliningDepth, fullyProcessed, "relevance-based (relevance=%f, probability=%f, bonus=%f, nodes=%d <= %f)", relevance, probability,
+                            inliningBonus, nodes, maximumNodes);
+        }
+
+        return InliningUtil.logNotInlinedMethod(info, inliningDepth, "relevance-based (relevance=%f, probability=%f, bonus=%f, nodes=%d > %f)", relevance, probability, inliningBonus, nodes,
+                        maximumNodes);
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/policy/InlineEverythingPolicy.java	Thu May 15 17:25:49 2014 +0200
@@ -0,0 +1,48 @@
+/*
+ * 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.inlining.policy;
+
+import com.oracle.graal.api.code.BailoutException;
+import com.oracle.graal.nodes.FixedNode;
+import com.oracle.graal.nodes.StructuredGraph;
+import com.oracle.graal.nodes.spi.Replacements;
+import com.oracle.graal.phases.common.inlining.info.InlineInfo;
+
+import java.util.function.ToDoubleFunction;
+
+import static com.oracle.graal.compiler.common.GraalOptions.MaximumDesiredSize;
+
+public final class InlineEverythingPolicy implements InliningPolicy {
+
+    public boolean continueInlining(StructuredGraph graph) {
+        if (graph.getNodeCount() >= MaximumDesiredSize.getValue()) {
+            throw new BailoutException("Inline all calls failed. The resulting graph is too large.");
+        }
+        return true;
+    }
+
+    public boolean isWorthInlining(ToDoubleFunction<FixedNode> probabilities, Replacements replacements, InlineInfo info, int inliningDepth, double probability, double relevance,
+                    boolean fullyProcessed) {
+        return true;
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/policy/InliningPolicy.java	Thu May 15 17:25:49 2014 +0200
@@ -0,0 +1,37 @@
+/*
+ * 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.inlining.policy;
+
+import com.oracle.graal.nodes.FixedNode;
+import com.oracle.graal.nodes.StructuredGraph;
+import com.oracle.graal.nodes.spi.Replacements;
+import com.oracle.graal.phases.common.inlining.info.InlineInfo;
+
+import java.util.function.ToDoubleFunction;
+
+public interface InliningPolicy {
+
+    boolean continueInlining(StructuredGraph graph);
+
+    boolean isWorthInlining(ToDoubleFunction<FixedNode> probabilities, Replacements replacements, InlineInfo info, int inliningDepth, double probability, double relevance, boolean fullyProcessed);
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/CallsiteHolder.java	Thu May 15 17:25:49 2014 +0200
@@ -0,0 +1,126 @@
+/*
+ * 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.inlining.walker;
+
+import com.oracle.graal.api.meta.MetaUtil;
+import com.oracle.graal.api.meta.ResolvedJavaMethod;
+import com.oracle.graal.nodes.FixedNode;
+import com.oracle.graal.nodes.Invoke;
+import com.oracle.graal.nodes.StructuredGraph;
+import com.oracle.graal.phases.graph.FixedNodeProbabilityCache;
+
+import java.util.Iterator;
+import java.util.LinkedList;
+import java.util.function.ToDoubleFunction;
+
+import static com.oracle.graal.compiler.common.GraalOptions.CapInheritedRelevance;
+
+/**
+ * Information about a graph that will potentially be inlined. This includes tracking the
+ * invocations in graph that will subject to inlining themselves.
+ */
+public class CallsiteHolder {
+
+    private final StructuredGraph graph;
+    private final LinkedList<Invoke> remainingInvokes;
+    private final double probability;
+    private final double relevance;
+
+    private final ToDoubleFunction<FixedNode> probabilities;
+    private final ComputeInliningRelevance computeInliningRelevance;
+
+    public CallsiteHolder(StructuredGraph graph, double probability, double relevance) {
+        this.graph = graph;
+        if (graph == null) {
+            this.remainingInvokes = new LinkedList<>();
+        } else {
+            LinkedList<Invoke> invokes = new InliningIterator(graph).apply();
+            assert invokes.size() == count(graph.getInvokes());
+            this.remainingInvokes = invokes;
+        }
+        this.probability = probability;
+        this.relevance = relevance;
+
+        if (graph != null && !remainingInvokes.isEmpty()) {
+            probabilities = new FixedNodeProbabilityCache();
+            computeInliningRelevance = new ComputeInliningRelevance(graph, probabilities);
+            computeProbabilities();
+        } else {
+            probabilities = null;
+            computeInliningRelevance = null;
+        }
+    }
+
+    private static int count(Iterable<Invoke> invokes) {
+        int count = 0;
+        Iterator<Invoke> iterator = invokes.iterator();
+        while (iterator.hasNext()) {
+            iterator.next();
+            count++;
+        }
+        return count;
+    }
+
+    /**
+     * Gets the method associated with the {@linkplain #graph() graph} represented by this object.
+     */
+    public ResolvedJavaMethod method() {
+        return graph.method();
+    }
+
+    public boolean hasRemainingInvokes() {
+        return !remainingInvokes.isEmpty();
+    }
+
+    /**
+     * The graph about which this object contains inlining information.
+     */
+    public StructuredGraph graph() {
+        return graph;
+    }
+
+    public Invoke popInvoke() {
+        return remainingInvokes.removeFirst();
+    }
+
+    public void pushInvoke(Invoke invoke) {
+        remainingInvokes.push(invoke);
+    }
+
+    public void computeProbabilities() {
+        computeInliningRelevance.compute();
+    }
+
+    public double invokeProbability(Invoke invoke) {
+        return probability * probabilities.applyAsDouble(invoke.asNode());
+    }
+
+    public double invokeRelevance(Invoke invoke) {
+        return Math.min(CapInheritedRelevance.getValue(), relevance) * computeInliningRelevance.getRelevance(invoke);
+    }
+
+    @Override
+    public String toString() {
+        return (graph != null ? MetaUtil.format("%H.%n(%p)", method()) : "<null method>") + remainingInvokes;
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/ComputeInliningRelevance.java	Thu May 15 17:25:49 2014 +0200
@@ -0,0 +1,324 @@
+/*
+ * Copyright (c) 2013, 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.inlining.walker;
+
+import static com.oracle.graal.graph.util.CollectionsAccess.*;
+
+import java.util.*;
+import java.util.function.*;
+
+import com.oracle.graal.graph.*;
+import com.oracle.graal.nodes.*;
+
+import edu.umd.cs.findbugs.annotations.*;
+
+public class ComputeInliningRelevance {
+
+    private static final double EPSILON = 1d / Integer.MAX_VALUE;
+    private static final double UNINITIALIZED = -1D;
+
+    private static final int EXPECTED_MIN_INVOKE_COUNT = 3;
+    private static final int EXPECTED_INVOKE_RATIO = 20;
+    private static final int EXPECTED_LOOP_COUNT = 3;
+
+    private final StructuredGraph graph;
+    private final ToDoubleFunction<FixedNode> nodeProbabilities;
+
+    /**
+     * Node relevances are pre-computed for all invokes if the graph contains loops. If there are no
+     * loops, the computation happens lazily based on {@link #rootScope}.
+     */
+    private Map<FixedNode, Double> nodeRelevances;
+    /**
+     * This scope is non-null if (and only if) there are no loops in the graph. In this case, the
+     * root scope is used to compute invoke relevances on the fly.
+     */
+    private Scope rootScope;
+
+    public ComputeInliningRelevance(StructuredGraph graph, ToDoubleFunction<FixedNode> nodeProbabilities) {
+        this.graph = graph;
+        this.nodeProbabilities = nodeProbabilities;
+    }
+
+    /**
+     * Initializes or updates the relevance computation. If there are no loops within the graph,
+     * most computation happens lazily.
+     */
+    public void compute() {
+        rootScope = null;
+        if (!graph.hasLoops()) {
+            // fast path for the frequent case of no loops
+            rootScope = new Scope(graph.start(), null);
+        } else {
+            if (nodeRelevances == null) {
+                nodeRelevances = newNodeIdentityMap(EXPECTED_MIN_INVOKE_COUNT + graph.getNodeCount() / EXPECTED_INVOKE_RATIO);
+            }
+            NodeWorkList workList = graph.createNodeWorkList();
+            Map<LoopBeginNode, Scope> loops = newNodeIdentityMap(EXPECTED_LOOP_COUNT);
+
+            loops.put(null, new Scope(graph.start(), null));
+            for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.class)) {
+                createLoopScope(loopBegin, loops);
+            }
+
+            for (Scope scope : loops.values()) {
+                scope.process(workList);
+            }
+        }
+    }
+
+    public double getRelevance(Invoke invoke) {
+        if (rootScope != null) {
+            return rootScope.computeInvokeRelevance(invoke);
+        }
+        assert nodeRelevances != null : "uninitialized relevance";
+        return nodeRelevances.get(invoke);
+    }
+
+    /**
+     * Determines the parent of the given loop and creates a {@link Scope} object for each one. This
+     * method will call itself recursively if no {@link Scope} for the parent loop exists.
+     */
+    private Scope createLoopScope(LoopBeginNode loopBegin, Map<LoopBeginNode, Scope> loops) {
+        Scope scope = loops.get(loopBegin);
+        if (scope == null) {
+            final Scope parent;
+            // look for the parent scope
+            FixedNode current = loopBegin.forwardEnd();
+            while (true) {
+                if (current.predecessor() == null) {
+                    if (current instanceof LoopBeginNode) {
+                        // if we reach a LoopBeginNode then we're within this loop
+                        parent = createLoopScope((LoopBeginNode) current, loops);
+                        break;
+                    } else if (current instanceof StartNode) {
+                        // we're within the outermost scope
+                        parent = loops.get(null);
+                        break;
+                    } else {
+                        assert current.getClass() == MergeNode.class : current;
+                        // follow any path upwards - it doesn't matter which one
+                        current = ((MergeNode) current).forwardEndAt(0);
+                    }
+                } else if (current instanceof LoopExitNode) {
+                    // if we reach a loop exit then we follow this loop and have the same parent
+                    parent = createLoopScope(((LoopExitNode) current).loopBegin(), loops).parent;
+                    break;
+                } else {
+                    current = (FixedNode) current.predecessor();
+                }
+            }
+            scope = new Scope(loopBegin, parent);
+            loops.put(loopBegin, scope);
+        }
+        return scope;
+    }
+
+    /**
+     * A scope holds information for the contents of one loop or of the root of the method. It does
+     * not include child loops, i.e., the iteration in {@link #process(NodeWorkList)} explicitly
+     * excludes the nodes of child loops.
+     */
+    private class Scope {
+        public final FixedNode start;
+        public final Scope parent; // can be null for the outermost scope
+
+        /**
+         * The minimum probability along the most probable path in this scope. Computed lazily.
+         */
+        private double fastPathMinProbability = UNINITIALIZED;
+        /**
+         * A measure of how important this scope is within its parent scope. Computed lazily.
+         */
+        private double scopeRelevanceWithinParent = UNINITIALIZED;
+
+        public Scope(FixedNode start, Scope parent) {
+            this.start = start;
+            this.parent = parent;
+        }
+
+        @SuppressFBWarnings("FE_FLOATING_POINT_EQUALITY")
+        public double getFastPathMinProbability() {
+            if (fastPathMinProbability == UNINITIALIZED) {
+                fastPathMinProbability = Math.max(EPSILON, computeFastPathMinProbability(start));
+            }
+            return fastPathMinProbability;
+        }
+
+        /**
+         * Computes the ratio between the probabilities of the current scope's entry point and the
+         * parent scope's fastPathMinProbability.
+         */
+        @SuppressFBWarnings("FE_FLOATING_POINT_EQUALITY")
+        public double getScopeRelevanceWithinParent() {
+            if (scopeRelevanceWithinParent == UNINITIALIZED) {
+                if (start instanceof LoopBeginNode) {
+                    assert parent != null;
+                    double scopeEntryProbability = nodeProbabilities.applyAsDouble(((LoopBeginNode) start).forwardEnd());
+
+                    scopeRelevanceWithinParent = scopeEntryProbability / parent.getFastPathMinProbability();
+                } else {
+                    scopeRelevanceWithinParent = 1D;
+                }
+            }
+            return scopeRelevanceWithinParent;
+        }
+
+        /**
+         * Processes all invokes in this scope by starting at the scope's start node and iterating
+         * all fixed nodes. Child loops are skipped by going from loop entries directly to the loop
+         * exits. Processing stops at loop exits of the current loop.
+         */
+        public void process(NodeWorkList workList) {
+            assert !(start instanceof Invoke);
+            workList.addAll(start.successors());
+
+            for (Node current : workList) {
+                assert current.isAlive();
+
+                if (current instanceof Invoke) {
+                    // process the invoke and queue its successors
+                    nodeRelevances.put((FixedNode) current, computeInvokeRelevance((Invoke) current));
+                    workList.addAll(current.successors());
+                } else if (current instanceof LoopBeginNode) {
+                    // skip child loops by advancing over the loop exits
+                    ((LoopBeginNode) current).loopExits().forEach(exit -> workList.add(exit.next()));
+                } else if (current instanceof LoopEndNode) {
+                    // nothing to do
+                } else if (current instanceof LoopExitNode) {
+                    // nothing to do
+                } else if (current instanceof FixedWithNextNode) {
+                    workList.add(((FixedWithNextNode) current).next());
+                } else if (current instanceof EndNode) {
+                    workList.add(((EndNode) current).merge());
+                } else if (current instanceof ControlSinkNode) {
+                    // nothing to do
+                } else if (current instanceof ControlSplitNode) {
+                    workList.addAll(current.successors());
+                } else {
+                    assert false : current;
+                }
+            }
+        }
+
+        /**
+         * The relevance of an invoke is the ratio between the invoke's probability and the current
+         * scope's fastPathMinProbability, adjusted by scopeRelevanceWithinParent.
+         */
+        public double computeInvokeRelevance(Invoke invoke) {
+            double invokeProbability = nodeProbabilities.applyAsDouble(invoke.asNode());
+            assert !Double.isNaN(invokeProbability);
+
+            double relevance = (invokeProbability / getFastPathMinProbability()) * Math.min(1.0, getScopeRelevanceWithinParent());
+            assert !Double.isNaN(relevance) : invoke + ": " + relevance + " / " + invokeProbability + " / " + getFastPathMinProbability() + " / " + getScopeRelevanceWithinParent();
+            return relevance;
+        }
+    }
+
+    /**
+     * Computes the minimum probability along the most probable path within the scope. During
+     * iteration, the method returns immediately once a loop exit is discovered.
+     */
+    private double computeFastPathMinProbability(FixedNode scopeStart) {
+        ArrayList<FixedNode> pathBeginNodes = new ArrayList<>();
+        pathBeginNodes.add(scopeStart);
+        double minPathProbability = nodeProbabilities.applyAsDouble(scopeStart);
+        boolean isLoopScope = scopeStart instanceof LoopBeginNode;
+
+        do {
+            Node current = pathBeginNodes.remove(pathBeginNodes.size() - 1);
+            do {
+                if (isLoopScope && current instanceof LoopExitNode && ((LoopBeginNode) scopeStart).loopExits().contains((LoopExitNode) current)) {
+                    return minPathProbability;
+                } else if (current instanceof LoopBeginNode && current != scopeStart) {
+                    current = getMaxProbabilityLoopExit((LoopBeginNode) current, pathBeginNodes);
+                    minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability);
+                } else if (current instanceof ControlSplitNode) {
+                    current = getMaxProbabilitySux((ControlSplitNode) current, pathBeginNodes);
+                    minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability);
+                } else {
+                    assert current.successors().count() <= 1;
+                    current = current.successors().first();
+                }
+            } while (current != null);
+        } while (!pathBeginNodes.isEmpty());
+
+        return minPathProbability;
+    }
+
+    private double getMinPathProbability(FixedNode current, double minPathProbability) {
+        return current == null ? minPathProbability : Math.min(minPathProbability, nodeProbabilities.applyAsDouble(current));
+    }
+
+    /**
+     * Returns the most probable successor. If multiple successors share the maximum probability,
+     * one is returned and the others are enqueued in pathBeginNodes.
+     */
+    private static Node getMaxProbabilitySux(ControlSplitNode controlSplit, ArrayList<FixedNode> pathBeginNodes) {
+        Node maxSux = null;
+        double maxProbability = 0.0;
+        int pathBeginCount = pathBeginNodes.size();
+
+        for (Node sux : controlSplit.successors()) {
+            double probability = controlSplit.probability((BeginNode) sux);
+            if (probability > maxProbability) {
+                maxProbability = probability;
+                maxSux = sux;
+                truncate(pathBeginNodes, pathBeginCount);
+            } else if (probability == maxProbability) {
+                pathBeginNodes.add((FixedNode) sux);
+            }
+        }
+
+        return maxSux;
+    }
+
+    /**
+     * Returns the most probable loop exit. If multiple successors share the maximum probability,
+     * one is returned and the others are enqueued in pathBeginNodes.
+     */
+    private Node getMaxProbabilityLoopExit(LoopBeginNode loopBegin, ArrayList<FixedNode> pathBeginNodes) {
+        Node maxSux = null;
+        double maxProbability = 0.0;
+        int pathBeginCount = pathBeginNodes.size();
+
+        for (LoopExitNode sux : loopBegin.loopExits()) {
+            double probability = nodeProbabilities.applyAsDouble(sux);
+            if (probability > maxProbability) {
+                maxProbability = probability;
+                maxSux = sux;
+                truncate(pathBeginNodes, pathBeginCount);
+            } else if (probability == maxProbability) {
+                pathBeginNodes.add(sux);
+            }
+        }
+
+        return maxSux;
+    }
+
+    private static void truncate(ArrayList<FixedNode> pathBeginNodes, int pathBeginCount) {
+        for (int i = pathBeginNodes.size() - pathBeginCount; i > 0; i--) {
+            pathBeginNodes.remove(pathBeginNodes.size() - 1);
+        }
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/DepthSearchUtil.java	Thu May 15 17:25:49 2014 +0200
@@ -0,0 +1,149 @@
+/*
+ * 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.inlining.walker;
+
+import com.oracle.graal.api.meta.Constant;
+import com.oracle.graal.api.meta.ResolvedJavaMethod;
+import com.oracle.graal.compiler.common.type.Stamp;
+import com.oracle.graal.debug.Debug;
+import com.oracle.graal.graph.NodeInputList;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.phases.common.CanonicalizerPhase;
+import com.oracle.graal.phases.common.DeadCodeEliminationPhase;
+import com.oracle.graal.phases.common.inlining.InliningUtil;
+import com.oracle.graal.phases.tiers.HighTierContext;
+
+import static com.oracle.graal.compiler.common.GraalOptions.OptCanonicalizer;
+
+/**
+ * The workings of {@link InliningData} include delving into a callsite to explore inlining
+ * opportunities. The utilities used for that are grouped in this class.
+ */
+public class DepthSearchUtil {
+
+    private DepthSearchUtil() {
+        // no instances
+    }
+
+    public static InliningUtil.Inlineable getInlineableElement(final ResolvedJavaMethod method, Invoke invoke, HighTierContext context, CanonicalizerPhase canonicalizer) {
+        Class<? extends FixedWithNextNode> macroNodeClass = InliningUtil.getMacroNodeClass(context.getReplacements(), method);
+        if (macroNodeClass != null) {
+            return new InliningUtil.InlineableMacroNode(macroNodeClass);
+        } else {
+            return new InliningUtil.InlineableGraph(buildGraph(method, invoke, context, canonicalizer));
+        }
+    }
+
+    private static StructuredGraph buildGraph(final ResolvedJavaMethod method, final Invoke invoke, final HighTierContext context, CanonicalizerPhase canonicalizer) {
+        final StructuredGraph newGraph;
+        final boolean parseBytecodes;
+
+        // TODO (chaeubl): copying the graph is only necessary if it is modified or if it contains
+        // any invokes
+        StructuredGraph intrinsicGraph = InliningUtil.getIntrinsicGraph(context.getReplacements(), method);
+        if (intrinsicGraph != null) {
+            newGraph = intrinsicGraph.copy();
+            parseBytecodes = false;
+        } else {
+            StructuredGraph cachedGraph = getCachedGraph(method, context);
+            if (cachedGraph != null) {
+                newGraph = cachedGraph.copy();
+                parseBytecodes = false;
+            } else {
+                newGraph = new StructuredGraph(method);
+                parseBytecodes = true;
+            }
+        }
+
+        try (Debug.Scope s = Debug.scope("InlineGraph", newGraph)) {
+            if (parseBytecodes) {
+                parseBytecodes(newGraph, context, canonicalizer);
+            }
+
+            boolean callerHasMoreInformationAboutArguments = false;
+            NodeInputList<ValueNode> args = invoke.callTarget().arguments();
+            for (ParameterNode param : newGraph.getNodes(ParameterNode.class).snapshot()) {
+                ValueNode arg = args.get(param.index());
+                if (arg.isConstant()) {
+                    Constant constant = arg.asConstant();
+                    newGraph.replaceFloating(param, ConstantNode.forConstant(constant, context.getMetaAccess(), newGraph));
+                    callerHasMoreInformationAboutArguments = true;
+                } else {
+                    Stamp joinedStamp = param.stamp().join(arg.stamp());
+                    if (joinedStamp != null && !joinedStamp.equals(param.stamp())) {
+                        param.setStamp(joinedStamp);
+                        callerHasMoreInformationAboutArguments = true;
+                    }
+                }
+            }
+
+            if (!callerHasMoreInformationAboutArguments) {
+                // TODO (chaeubl): if args are not more concrete, inlining should be avoided
+                // in most cases or we could at least use the previous graph size + invoke
+                // probability to check the inlining
+            }
+
+            if (OptCanonicalizer.getValue()) {
+                canonicalizer.apply(newGraph, context);
+            }
+
+            return newGraph;
+        } catch (Throwable e) {
+            throw Debug.handle(e);
+        }
+    }
+
+    private static StructuredGraph getCachedGraph(ResolvedJavaMethod method, HighTierContext context) {
+        if (context.getGraphCache() != null) {
+            StructuredGraph cachedGraph = context.getGraphCache().get(method);
+            if (cachedGraph != null) {
+                return cachedGraph;
+            }
+        }
+        return null;
+    }
+
+    /**
+     * This method builds the IR nodes for <code>newGraph</code> and canonicalizes them. Provided
+     * profiling info is mature, the resulting graph is cached.
+     */
+    private static StructuredGraph parseBytecodes(StructuredGraph newGraph, HighTierContext context, CanonicalizerPhase canonicalizer) {
+        final boolean hasMatureProfilingInfo = newGraph.method().getProfilingInfo().isMature();
+
+        if (context.getGraphBuilderSuite() != null) {
+            context.getGraphBuilderSuite().apply(newGraph, context);
+        }
+        assert newGraph.start().next() != null : "graph needs to be populated during PhasePosition.AFTER_PARSING";
+
+        new DeadCodeEliminationPhase().apply(newGraph);
+
+        if (OptCanonicalizer.getValue()) {
+            canonicalizer.apply(newGraph, context);
+        }
+
+        if (hasMatureProfilingInfo && context.getGraphCache() != null) {
+            context.getGraphCache().put(newGraph.method(), newGraph.copy());
+        }
+        return newGraph;
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/InliningData.java	Thu May 15 17:25:49 2014 +0200
@@ -0,0 +1,330 @@
+/*
+ * 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.inlining.walker;
+
+import com.oracle.graal.api.code.Assumptions;
+import com.oracle.graal.api.code.BailoutException;
+import com.oracle.graal.api.meta.ResolvedJavaMethod;
+import com.oracle.graal.compiler.common.GraalInternalError;
+import com.oracle.graal.debug.Debug;
+import com.oracle.graal.debug.DebugMetric;
+import com.oracle.graal.graph.Graph;
+import com.oracle.graal.graph.Node;
+import com.oracle.graal.nodes.FixedNode;
+import com.oracle.graal.nodes.Invoke;
+import com.oracle.graal.nodes.StructuredGraph;
+import com.oracle.graal.phases.common.CanonicalizerPhase;
+import com.oracle.graal.phases.common.inlining.InliningUtil;
+import com.oracle.graal.phases.common.inlining.info.InlineInfo;
+import com.oracle.graal.phases.common.inlining.policy.InliningPolicy;
+import com.oracle.graal.phases.tiers.HighTierContext;
+import com.oracle.graal.phases.util.Providers;
+
+import java.util.ArrayDeque;
+import java.util.List;
+import java.util.function.ToDoubleFunction;
+
+import static com.oracle.graal.compiler.common.GraalOptions.OptCanonicalizer;
+
+/**
+ * Holds the data for building the callee graphs recursively: graphs and invocations (each
+ * invocation can have multiple graphs).
+ */
+public class InliningData {
+
+    private static final CallsiteHolder DUMMY_CALLSITE_HOLDER = new CallsiteHolder(null, 1.0, 1.0);
+    // Metrics
+    private static final DebugMetric metricInliningPerformed = Debug.metric("InliningPerformed");
+    private static final DebugMetric metricInliningRuns = Debug.metric("InliningRuns");
+    private static final DebugMetric metricInliningConsidered = Debug.metric("InliningConsidered");
+
+    /**
+     * Call hierarchy from outer most call (i.e., compilation unit) to inner most callee.
+     */
+    private final ArrayDeque<CallsiteHolder> graphQueue;
+    private final ArrayDeque<MethodInvocation> invocationQueue;
+    private final int maxMethodPerInlining;
+    private final CanonicalizerPhase canonicalizer;
+    private final InliningPolicy inliningPolicy;
+
+    private int maxGraphs;
+
+    public InliningData(StructuredGraph rootGraph, Assumptions rootAssumptions, int maxMethodPerInlining, CanonicalizerPhase canonicalizer, InliningPolicy inliningPolicy) {
+        assert rootGraph != null;
+        this.graphQueue = new ArrayDeque<>();
+        this.invocationQueue = new ArrayDeque<>();
+        this.maxMethodPerInlining = maxMethodPerInlining;
+        this.canonicalizer = canonicalizer;
+        this.inliningPolicy = inliningPolicy;
+        this.maxGraphs = 1;
+
+        invocationQueue.push(new MethodInvocation(null, rootAssumptions, 1.0, 1.0));
+        pushGraph(rootGraph, 1.0, 1.0);
+    }
+
+    private void doInline(CallsiteHolder callerCallsiteHolder, MethodInvocation calleeInfo, Assumptions callerAssumptions, HighTierContext context) {
+        StructuredGraph callerGraph = callerCallsiteHolder.graph();
+        Graph.Mark markBeforeInlining = callerGraph.getMark();
+        InlineInfo callee = calleeInfo.callee();
+        try {
+            try (Debug.Scope scope = Debug.scope("doInline", callerGraph)) {
+                List<Node> invokeUsages = callee.invoke().asNode().usages().snapshot();
+                callee.inline(new Providers(context), callerAssumptions);
+                callerAssumptions.record(calleeInfo.assumptions());
+                metricInliningRuns.increment();
+                Debug.dump(callerGraph, "after %s", callee);
+
+                if (OptCanonicalizer.getValue()) {
+                    Graph.Mark markBeforeCanonicalization = callerGraph.getMark();
+                    canonicalizer.applyIncremental(callerGraph, context, invokeUsages, markBeforeInlining);
+
+                    // process invokes that are possibly created during canonicalization
+                    for (Node newNode : callerGraph.getNewNodes(markBeforeCanonicalization)) {
+                        if (newNode instanceof Invoke) {
+                            callerCallsiteHolder.pushInvoke((Invoke) newNode);
+                        }
+                    }
+                }
+
+                callerCallsiteHolder.computeProbabilities();
+
+                metricInliningPerformed.increment();
+            }
+        } catch (BailoutException bailout) {
+            throw bailout;
+        } catch (AssertionError | RuntimeException e) {
+            throw new GraalInternalError(e).addContext(callee.toString());
+        } catch (GraalInternalError e) {
+            throw e.addContext(callee.toString());
+        }
+    }
+
+    /**
+     * @return true iff inlining was actually performed
+     */
+    private boolean tryToInline(ToDoubleFunction<FixedNode> probabilities, CallsiteHolder callerCallsiteHolder, MethodInvocation calleeInfo, MethodInvocation parentInvocation, int inliningDepth,
+                    HighTierContext context) {
+        InlineInfo callee = calleeInfo.callee();
+        Assumptions callerAssumptions = parentInvocation.assumptions();
+        metricInliningConsidered.increment();
+
+        if (inliningPolicy.isWorthInlining(probabilities, context.getReplacements(), callee, inliningDepth, calleeInfo.probability(), calleeInfo.relevance(), true)) {
+            doInline(callerCallsiteHolder, calleeInfo, callerAssumptions, context);
+            return true;
+        }
+
+        if (context.getOptimisticOptimizations().devirtualizeInvokes()) {
+            callee.tryToDevirtualizeInvoke(context.getMetaAccess(), callerAssumptions);
+        }
+
+        return false;
+    }
+
+    /**
+     * Process the next invoke and enqueue all its graphs for processing.
+     */
+    void processNextInvoke(HighTierContext context) {
+        CallsiteHolder callsiteHolder = currentGraph();
+        Invoke invoke = callsiteHolder.popInvoke();
+        MethodInvocation callerInvocation = currentInvocation();
+        Assumptions parentAssumptions = callerInvocation.assumptions();
+        InlineInfo info = InliningUtil.getInlineInfo(this, invoke, maxMethodPerInlining, context.getReplacements(), parentAssumptions, context.getOptimisticOptimizations());
+
+        if (info != null) {
+            double invokeProbability = callsiteHolder.invokeProbability(invoke);
+            double invokeRelevance = callsiteHolder.invokeRelevance(invoke);
+            MethodInvocation calleeInvocation = pushInvocation(info, parentAssumptions, invokeProbability, invokeRelevance);
+
+            for (int i = 0; i < info.numberOfMethods(); i++) {
+                InliningUtil.Inlineable elem = DepthSearchUtil.getInlineableElement(info.methodAt(i), info.invoke(), context.replaceAssumptions(calleeInvocation.assumptions()), canonicalizer);
+                info.setInlinableElement(i, elem);
+                if (elem instanceof InliningUtil.InlineableGraph) {
+                    pushGraph(((InliningUtil.InlineableGraph) elem).getGraph(), invokeProbability * info.probabilityAt(i), invokeRelevance * info.relevanceAt(i));
+                } else {
+                    assert elem instanceof InliningUtil.InlineableMacroNode;
+                    pushDummyGraph();
+                }
+            }
+        }
+    }
+
+    public int graphCount() {
+        return graphQueue.size();
+    }
+
+    private void pushGraph(StructuredGraph graph, double probability, double relevance) {
+        assert graph != null;
+        assert !contains(graph);
+        graphQueue.push(new CallsiteHolder(graph, probability, relevance));
+        assert graphQueue.size() <= maxGraphs;
+    }
+
+    private void pushDummyGraph() {
+        graphQueue.push(DUMMY_CALLSITE_HOLDER);
+    }
+
+    public boolean hasUnprocessedGraphs() {
+        return !graphQueue.isEmpty();
+    }
+
+    public CallsiteHolder currentGraph() {
+        return graphQueue.peek();
+    }
+
+    public void popGraph() {
+        graphQueue.pop();
+        assert graphQueue.size() <= maxGraphs;
+    }
+
+    public void popGraphs(int count) {
+        assert count >= 0;
+        for (int i = 0; i < count; i++) {
+            graphQueue.pop();
+        }
+    }
+
+    private static final Object[] NO_CONTEXT = {};
+
+    /**
+     * Gets the call hierarchy of this inlining from outer most call to inner most callee.
+     */
+    public Object[] inliningContext() {
+        if (!Debug.isDumpEnabled()) {
+            return NO_CONTEXT;
+        }
+        Object[] result = new Object[graphQueue.size()];
+        int i = 0;
+        for (CallsiteHolder g : graphQueue) {
+            result[i++] = g.method();
+        }
+        return result;
+    }
+
+    public MethodInvocation currentInvocation() {
+        return invocationQueue.peekFirst();
+    }
+
+    private MethodInvocation pushInvocation(InlineInfo info, Assumptions assumptions, double probability, double relevance) {
+        MethodInvocation methodInvocation = new MethodInvocation(info, new Assumptions(assumptions.useOptimisticAssumptions()), probability, relevance);
+        invocationQueue.addFirst(methodInvocation);
+        maxGraphs += info.numberOfMethods();
+        assert graphQueue.size() <= maxGraphs;
+        return methodInvocation;
+    }
+
+    public void popInvocation() {
+        maxGraphs -= invocationQueue.peekFirst().callee().numberOfMethods();
+        assert graphQueue.size() <= maxGraphs;
+        invocationQueue.removeFirst();
+    }
+
+    public int countRecursiveInlining(ResolvedJavaMethod method) {
+        int count = 0;
+        for (CallsiteHolder callsiteHolder : graphQueue) {
+            if (method.equals(callsiteHolder.method())) {
+                count++;
+            }
+        }
+        return count;
+    }
+
+    public int inliningDepth() {
+        assert invocationQueue.size() > 0;
+        return invocationQueue.size() - 1;
+    }
+
+    @Override
+    public String toString() {
+        StringBuilder result = new StringBuilder("Invocations: ");
+
+        for (MethodInvocation invocation : invocationQueue) {
+            if (invocation.callee() != null) {
+                result.append(invocation.callee().numberOfMethods());
+                result.append("x ");
+                result.append(invocation.callee().invoke());
+                result.append("; ");
+            }
+        }
+
+        result.append("\nGraphs: ");
+        for (CallsiteHolder graph : graphQueue) {
+            result.append(graph.graph());
+            result.append("; ");
+        }
+
+        return result.toString();
+    }
+
+    private boolean contains(StructuredGraph graph) {
+        for (CallsiteHolder info : graphQueue) {
+            if (info.graph() == graph) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    /**
+     * @return true iff inlining was actually performed
+     */
+    public boolean moveForward(HighTierContext context, ToDoubleFunction<FixedNode> probabilities) {
+
+        final MethodInvocation currentInvocation = currentInvocation();
+
+        final boolean backtrack = (!currentInvocation.isRoot() && !inliningPolicy.isWorthInlining(probabilities, context.getReplacements(), currentInvocation.callee(), inliningDepth(),
+                        currentInvocation.probability(), currentInvocation.relevance(), false));
+        if (backtrack) {
+            int remainingGraphs = currentInvocation.totalGraphs() - currentInvocation.processedGraphs();
+            assert remainingGraphs > 0;
+            popGraphs(remainingGraphs);
+            popInvocation();
+            return false;
+        }
+
+        final boolean delve = currentGraph().hasRemainingInvokes() && inliningPolicy.continueInlining(currentGraph().graph());
+        if (delve) {
+            processNextInvoke(context);
+            return false;
+        }
+
+        popGraph();
+        if (currentInvocation.isRoot()) {
+            return false;
+        }
+
+        // try to inline
+        assert currentInvocation.callee().invoke().asNode().isAlive();
+        currentInvocation.incrementProcessedGraphs();
+        if (currentInvocation.processedGraphs() == currentInvocation.totalGraphs()) {
+            popInvocation();
+            final MethodInvocation parentInvoke = currentInvocation();
+            try (Debug.Scope s = Debug.scope("Inlining", inliningContext())) {
+                return tryToInline(probabilities, currentGraph(), currentInvocation, parentInvoke, inliningDepth() + 1, context);
+            } catch (Throwable e) {
+                throw Debug.handle(e);
+            }
+        }
+
+        return false;
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/InliningIterator.java	Thu May 15 17:25:49 2014 +0200
@@ -0,0 +1,130 @@
+/*
+ * 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.inlining.walker;
+
+import com.oracle.graal.graph.Node;
+import com.oracle.graal.graph.NodeBitMap;
+import com.oracle.graal.nodes.*;
+import com.oracle.graal.nodes.java.MethodCallTargetNode;
+
+import java.util.ArrayDeque;
+import java.util.Deque;
+import java.util.LinkedList;
+
+/**
+ * Given a graph, visit all fixed nodes in dominator-based order, collecting in the process the
+ * {@link Invoke} nodes with {@link MethodCallTargetNode}. Such list of callsites is returned by
+ * {@link #apply()}
+ */
+public class InliningIterator {
+
+    private final StartNode start;
+    private final Deque<FixedNode> nodeQueue;
+    private final NodeBitMap queuedNodes;
+
+    public InliningIterator(StructuredGraph graph) {
+        this.start = graph.start();
+        this.nodeQueue = new ArrayDeque<>();
+        this.queuedNodes = graph.createNodeBitMap();
+        assert start.isAlive();
+    }
+
+    public LinkedList<Invoke> apply() {
+        LinkedList<Invoke> invokes = new LinkedList<>();
+        FixedNode current;
+        forcedQueue(start);
+
+        while ((current = nextQueuedNode()) != null) {
+            assert current.isAlive();
+
+            if (current instanceof Invoke && ((Invoke) current).callTarget() instanceof MethodCallTargetNode) {
+                if (current != start) {
+                    invokes.addLast((Invoke) current);
+                }
+                queueSuccessors(current);
+            } else if (current instanceof LoopBeginNode) {
+                queueSuccessors(current);
+            } else if (current instanceof LoopEndNode) {
+                // nothing to do
+            } else if (current instanceof MergeNode) {
+                queueSuccessors(current);
+            } else if (current instanceof FixedWithNextNode) {
+                queueSuccessors(current);
+            } else if (current instanceof EndNode) {
+                queueMerge((EndNode) current);
+            } else if (current instanceof ControlSinkNode) {
+                // nothing to do
+            } else if (current instanceof ControlSplitNode) {
+                queueSuccessors(current);
+            } else {
+                assert false : current;
+            }
+        }
+
+        return invokes;
+    }
+
+    private void queueSuccessors(FixedNode x) {
+        for (Node node : x.successors()) {
+            queue(node);
+        }
+    }
+
+    private void queue(Node node) {
+        if (node != null && !queuedNodes.isMarked(node)) {
+            forcedQueue(node);
+        }
+    }
+
+    private void forcedQueue(Node 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(AbstractEndNode 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 (!queuedNodes.isMarked(merge.forwardEndAt(i))) {
+                return false;
+            }
+        }
+        return true;
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/inlining/walker/MethodInvocation.java	Thu May 15 17:25:49 2014 +0200
@@ -0,0 +1,95 @@
+/*
+ * 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.inlining.walker;
+
+import com.oracle.graal.api.code.Assumptions;
+import com.oracle.graal.api.meta.MetaUtil;
+import com.oracle.graal.api.meta.ResolvedJavaMethod;
+import com.oracle.graal.nodes.CallTargetNode;
+import com.oracle.graal.nodes.java.MethodCallTargetNode;
+import com.oracle.graal.phases.common.inlining.info.InlineInfo;
+
+public class MethodInvocation {
+
+    private final InlineInfo callee;
+    private final Assumptions assumptions;
+    private final double probability;
+    private final double relevance;
+
+    private int processedGraphs;
+
+    public MethodInvocation(InlineInfo info, Assumptions assumptions, double probability, double relevance) {
+        this.callee = info;
+        this.assumptions = assumptions;
+        this.probability = probability;
+        this.relevance = relevance;
+    }
+
+    public void incrementProcessedGraphs() {
+        processedGraphs++;
+        assert processedGraphs <= callee.numberOfMethods();
+    }
+
+    public int processedGraphs() {
+        assert processedGraphs <= callee.numberOfMethods();
+        return processedGraphs;
+    }
+
+    public int totalGraphs() {
+        return callee.numberOfMethods();
+    }
+
+    public InlineInfo callee() {
+        return callee;
+    }
+
+    public Assumptions assumptions() {
+        return assumptions;
+    }
+
+    public double probability() {
+        return probability;
+    }
+
+    public double relevance() {
+        return relevance;
+    }
+
+    public boolean isRoot() {
+        return callee == null;
+    }
+
+    @Override
+    public String toString() {
+        if (isRoot()) {
+            return "<root>";
+        }
+        CallTargetNode callTarget = callee.invoke().callTarget();
+        if (callTarget instanceof MethodCallTargetNode) {
+            ResolvedJavaMethod calleeMethod = ((MethodCallTargetNode) callTarget).targetMethod();
+            return MetaUtil.format("Invoke#%H.%n(%p)", calleeMethod);
+        } else {
+            return "Invoke#" + callTarget.targetName();
+        }
+    }
+}