changeset 3086:02e2c1c4ac53

InliningPhase can take a hint on what to inline, initial work on EscapeAnalysisPhase
author Lukas Stadler <lukas.stadler@jku.at>
date Wed, 22 Jun 2011 11:55:42 +0200
parents f08a810b8449
children 8188167cbb0f
files graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Invoke.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MemoryWrite.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewInstance.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java
diffstat 11 files changed, 518 insertions(+), 85 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java	Tue Jun 21 14:32:12 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/GraalOptions.java	Wed Jun 22 11:55:42 2011 +0200
@@ -54,6 +54,9 @@
     public static int     MaximumDesiredSize                 = 8000;
     public static int     MaximumShortLoopSize               = 5;
 
+    // escape analysis settings
+    public static int     ForcedInlineEscapeWeight           = 0;
+
     // debugging settings
     public static boolean VerifyPointerMaps                  = ____;
     public static int     MethodEndBreakpointGuards          = 0;
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java	Tue Jun 21 14:32:12 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/graph/IR.java	Wed Jun 22 11:55:42 2011 +0200
@@ -90,7 +90,7 @@
         //printGraph("After DeadCodeElimination", compilation.graph);
 
         if (GraalOptions.Inline) {
-            new InliningPhase(compilation, this, GraalOptions.TraceInlining).apply(compilation.graph);
+            new InliningPhase(compilation, this, null, GraalOptions.TraceInlining).apply(compilation.graph);
         }
 
         Graph graph = compilation.graph;
@@ -99,8 +99,11 @@
             new CanonicalizerPhase().apply(graph);
             new DeadCodeEliminationPhase().apply(graph);
         }
-//
-//        new EscapeAnalysisPhase().apply(graph);
+
+        new EscapeAnalysisPhase(compilation, this).apply(graph);
+        new DeadCodeEliminationPhase().apply(graph);
+        new CanonicalizerPhase().apply(graph);
+        new DeadCodeEliminationPhase().apply(graph);
 
         if (GraalOptions.OptLoops) {
             new LoopPhase().apply(graph);
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Invoke.java	Tue Jun 21 14:32:12 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Invoke.java	Wed Jun 22 11:55:42 2011 +0200
@@ -84,7 +84,6 @@
     public final RiMethod target;
     public final RiType returnType;
     public final int bci; // XXX needed because we can not compute the bci from the sateBefore bci of this Invoke was optimized from INVOKEINTERFACE to INVOKESPECIAL
-    public final RiTypeProfile profile;
 
     /**
      * Constructs a new Invoke instruction.
@@ -95,13 +94,12 @@
      * @param isStatic {@code true} if this call is static (no receiver object)
      * @param target the target method being called
      */
-    public Invoke(int bci, int opcode, CiKind result, Value[] args, RiMethod target, RiType returnType, RiTypeProfile profile, Graph graph) {
+    public Invoke(int bci, int opcode, CiKind result, Value[] args, RiMethod target, RiType returnType, Graph graph) {
         super(result, args.length, SUCCESSOR_COUNT, graph);
         this.opcode = opcode;
         this.target = target;
         this.returnType = returnType;
         this.bci = bci;
-        this.profile = profile;
 
         this.argumentCount = args.length;
         for (int i = 0; i < args.length; i++) {
@@ -148,10 +146,6 @@
         return target;
     }
 
-    public RiTypeProfile profile() {
-        return profile;
-    }
-
     /**
      * Checks whether this invocation has a receiver object.
      * @return {@code true} if this invocation has a receiver object; {@code false} otherwise, if this is a
@@ -201,7 +195,7 @@
 
     @Override
     public Node copy(Graph into) {
-        Invoke x = new Invoke(bci, opcode, kind, new Value[argumentCount], target, returnType, profile, into);
+        Invoke x = new Invoke(bci, opcode, kind, new Value[argumentCount], target, returnType, into);
         return x;
     }
 }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MemoryWrite.java	Tue Jun 21 14:32:12 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/MemoryWrite.java	Wed Jun 22 11:55:42 2011 +0200
@@ -23,11 +23,15 @@
 package com.oracle.max.graal.compiler.ir;
 
 import com.oracle.max.graal.compiler.debug.*;
+import com.oracle.max.graal.compiler.ir.NewInstance.*;
+import com.oracle.max.graal.compiler.phases.EscapeAnalysisPhase.*;
 import com.oracle.max.graal.graph.*;
 import com.sun.cri.ci.*;
 
 
 public final class MemoryWrite extends MemoryAccess {
+    private static final EscapeOp ESCAPE = new NewInstanceEscapeOp();
+
     private static final int INPUT_COUNT = 1;
     private static final int INPUT_VALUE = 0;
     private static final int SUCCESSOR_COUNT = 0;
@@ -59,4 +63,20 @@
     public Node copy(Graph into) {
         return new MemoryWrite(super.kind, null, displacement(), into);
     }
+
+    @SuppressWarnings("unchecked")
+    @Override
+    public <T extends Op> T lookup(Class<T> clazz) {
+        if (clazz == EscapeOp.class) {
+            return (T) ESCAPE;
+        }
+        return super.lookup(clazz);
+    }
+
+    private static class NewInstanceEscapeOp implements EscapeOp {
+        @Override
+        public Escape escape(Node node, Node value) {
+            return Escape.NewValue;
+        }
+    }
 }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewInstance.java	Tue Jun 21 14:32:12 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewInstance.java	Wed Jun 22 11:55:42 2011 +0200
@@ -23,6 +23,8 @@
 package com.oracle.max.graal.compiler.ir;
 
 import com.oracle.max.graal.compiler.debug.*;
+import com.oracle.max.graal.compiler.phases.EscapeAnalysisPhase.Escape;
+import com.oracle.max.graal.compiler.phases.EscapeAnalysisPhase.EscapeOp;
 import com.oracle.max.graal.graph.*;
 import com.sun.cri.ci.*;
 import com.sun.cri.ri.*;
@@ -31,6 +33,7 @@
  * The {@code NewInstance} instruction represents the allocation of an instance class object.
  */
 public final class NewInstance extends FloatingNode {
+    private static final EscapeOp ESCAPE = new NewInstanceEscapeOp();
 
     private static final int INPUT_COUNT = 0;
     private static final int SUCCESSOR_COUNT = 0;
@@ -85,4 +88,20 @@
         NewInstance x = new NewInstance(instanceClass, cpi, constantPool, into);
         return x;
     }
+
+    @SuppressWarnings("unchecked")
+    @Override
+    public <T extends Op> T lookup(Class<T> clazz) {
+        if (clazz == EscapeOp.class) {
+            return (T) ESCAPE;
+        }
+        return super.lookup(clazz);
+    }
+
+    private static class NewInstanceEscapeOp implements EscapeOp {
+        @Override
+        public Escape escape(Node node, Node value) {
+            return Escape.NewValue;
+        }
+    }
 }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java	Tue Jun 21 14:32:12 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/DeadCodeEliminationPhase.java	Wed Jun 22 11:55:42 2011 +0200
@@ -29,6 +29,7 @@
 import com.oracle.max.graal.compiler.gen.*;
 import com.oracle.max.graal.compiler.ir.*;
 import com.oracle.max.graal.graph.*;
+import com.sun.cri.ci.*;
 
 
 public class DeadCodeEliminationPhase extends Phase {
@@ -53,20 +54,29 @@
             }
         }
         // remove if nodes with constant-value comparison
-//        for (If ifNode : graph.getNodes(If.class)) {
-//            Compare compare = ifNode.compare();
-//            if (compare.x().isConstant() && compare.y().isConstant()) {
-//                CiConstant constX = compare.x().asConstant();
-//                CiConstant constY = compare.y().asConstant();
-//                Boolean result = compare.condition().foldCondition(constX, constY, GraalCompilation.compilation().runtime);
-//                if (result != null) {
-//                    Node actualSuccessor = result ? ifNode.trueSuccessor() : ifNode.falseSuccessor();
-//                    ifNode.replace(actualSuccessor);
-//                } else {
-//                    TTY.println("if not removed %s %s %s (%s %s)", constX, compare.condition(), constY, constX.kind, constY.kind);
-//                }
-//            }
-//        }
+        for (If ifNode : graph.getNodes(If.class)) {
+            BooleanNode bool = ifNode.compare();
+            if (bool instanceof Compare) {
+                Compare compare = (Compare) bool;
+                if (compare.x().isConstant() && compare.y().isConstant()) {
+                    CiConstant constX = compare.x().asConstant();
+                    CiConstant constY = compare.y().asConstant();
+                    Boolean result = compare.condition().foldCondition(constX, constY, GraalCompilation.compilation().runtime);
+                    if (result != null) {
+                        Node actualSuccessor = result ? ifNode.trueSuccessor() : ifNode.falseSuccessor();
+                        ifNode.replace(actualSuccessor);
+                    } else {
+                        TTY.println("if not removed %s %s %s (%s %s)", constX, compare.condition(), constY, constX.kind, constY.kind);
+                    }
+                }
+            }
+        }
+        // remove unnecessary FixedGuards
+        for (FixedGuard guard : graph.getNodes(FixedGuard.class)) {
+            if (guard.node() instanceof IsNonNull && ((IsNonNull) guard.node()).object() instanceof NewInstance) {
+                guard.replace(guard.next());
+            }
+        }
 
         flood.add(graph.start());
 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/EscapeAnalysisPhase.java	Wed Jun 22 11:55:42 2011 +0200
@@ -0,0 +1,312 @@
+/*
+ * 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.max.graal.compiler.phases;
+
+import java.util.*;
+import java.util.Map.Entry;
+
+import com.oracle.max.graal.compiler.*;
+import com.oracle.max.graal.compiler.debug.*;
+import com.oracle.max.graal.compiler.graph.*;
+import com.oracle.max.graal.compiler.ir.*;
+import com.oracle.max.graal.compiler.schedule.*;
+import com.oracle.max.graal.compiler.value.*;
+import com.oracle.max.graal.graph.*;
+import com.sun.cri.ri.*;
+
+
+public class EscapeAnalysisPhase extends Phase {
+
+
+    public static class BlockExitState {
+        public final HashMap<RiField, Node> fieldState;
+
+        public BlockExitState() {
+            this.fieldState = new HashMap<RiField, Node>();
+        }
+    }
+
+    public class EscapementFixup {
+
+        private List<Block> blocks;
+        private final HashMap<String, RiField> fields = new HashMap<String, RiField>();
+
+        private final HashMap<Block, BlockExitState> exitStates = new HashMap<Block, BlockExitState>();
+
+
+        public void apply(final Graph graph, final Node node) {
+            process(node);
+            removeAllocation(graph, node);
+        }
+
+        public void removeAllocation(final Graph graph, final Node node) {
+            final IdentifyBlocksPhase identifyBlocksPhase = new IdentifyBlocksPhase(true);
+            identifyBlocksPhase.apply(graph);
+            blocks = identifyBlocksPhase.getBlocks();
+
+            final HashMap<Phi, RiField> phis = new HashMap<Phi, RiField>();
+
+            Block.iteratePostOrder(blocks, new BlockClosure() {
+
+                public void apply(Block block) {
+//                    TTY.println("Block %d", block.blockID());
+//                    for (Node n : block.getInstructions()) {
+//                        TTY.println("  %d %s", n.id(), n.shortName());
+//                    }
+//                    for (Block b : block.getSuccessors()) {
+//                        TTY.print(" %d", b.blockID());
+//                    }
+//                    TTY.println();
+
+                    BlockExitState state;
+                    List<Block> predecessors = block.getPredecessors();
+                    Set<RiField> mergedFields = new HashSet<RiField>();
+                    state = new BlockExitState();
+                    for (int i = 0; i < predecessors.size(); i++) {
+                        BlockExitState exitState = exitStates.get(predecessors.get(i));
+                        if (exitState == null) {
+                            mergedFields.addAll(fields.values());
+                        } else {
+                            for (RiField field : fields.values()) {
+                                if (state.fieldState.get(field) == null) {
+                                    state.fieldState.put(field, exitState.fieldState.get(field));
+                                } else if (state.fieldState.get(field) != exitState.fieldState.get(field)) {
+                                    mergedFields.add(field);
+                                }
+                            }
+                        }
+                    }
+                    if (!mergedFields.isEmpty()) {
+                        assert block.firstNode() instanceof Merge : "unexpected: " + block.firstNode().shortName() + " " +  block.firstNode().id();
+                        for (RiField field : mergedFields) {
+                            Phi phi = new Phi(field.kind().stackKind(), (Merge) block.firstNode(), graph);
+                            state.fieldState.put(field, phi);
+                            phis.put(phi, field);
+                        }
+                    }
+
+                    if (identifyBlocksPhase.getNodeToBlock().get(node) == block) {
+                        state = new BlockExitState();
+                    }
+
+                    Node current;
+                    if (block.firstNode() instanceof StartNode) {
+                        current = ((StartNode) block.firstNode()).start();
+                    } else {
+                        current = block.firstNode();
+                    }
+                    while (current != block.lastNode()) {
+                        if (current instanceof LoadField) {
+                            LoadField x = (LoadField) current;
+                            if (x.object() == node) {
+                                for (Node usage : new ArrayList<Node>(x.usages())) {
+                                    assert state.fieldState.get(x.field()) != null;
+                                    usage.inputs().replace(x, state.fieldState.get(x.field()));
+                                }
+                                current = ((Instruction) current).next();
+                                x.replace(x.next());
+                            } else {
+                                current = ((Instruction) current).next();
+                            }
+                        } else if (current instanceof StoreField) {
+                            StoreField x = (StoreField) current;
+                            if (x.object() == node) {
+                                state.fieldState.put(x.field(), x.value());
+                                current = ((Instruction) current).next();
+                                x.replace(x.next());
+                            } else {
+                                current = ((Instruction) current).next();
+                            }
+                        } else {
+                            current = ((Instruction) current).next();
+                        }
+                    }
+
+                    exitStates.put(block, state);
+                }
+            });
+
+            for (Entry<Phi, RiField> entry : phis.entrySet()) {
+                Phi phi = entry.getKey();
+                RiField field = entry.getValue();
+                Block block = identifyBlocksPhase.getNodeToBlock().get(entry.getKey().merge());
+
+                List<Block> predecessors = block.getPredecessors();
+                for (int i = 0; i < predecessors.size(); i++) {
+                    BlockExitState exitState = exitStates.get(predecessors.get(i));
+                    assert exitState != null;
+                    Node value = exitState.fieldState.get(field);
+                    TTY.println("fixing phi %d with %s", phi.id(), value);
+                    if (value == null) {
+                        phi.addInput(Constant.defaultForKind(field.kind(), graph));
+                    } else {
+                        phi.addInput(value);
+                    }
+                }
+
+            }
+
+            node.delete();
+        }
+
+
+        private void process(Node node) {
+            for (Node usage : new ArrayList<Node>(node.usages())) {
+                if (usage instanceof IsNonNull) {
+                    IsNonNull x = (IsNonNull) usage;
+                    if (x.usages().size() == 1 && x.usages().get(0) instanceof FixedGuard) {
+                        FixedGuard guard = (FixedGuard) x.usages().get(0);
+                        guard.replace(guard.next());
+                    }
+                    x.delete();
+                } else if (usage instanceof IsType) {
+                    IsType x = (IsType) usage;
+                    assert x.type() == ((NewInstance) node).instanceClass();
+                    if (x.usages().size() == 1 && x.usages().get(0) instanceof FixedGuard) {
+                        FixedGuard guard = (FixedGuard) x.usages().get(0);
+                        guard.replace(guard.next());
+                    }
+                    x.delete();
+                } else if (usage instanceof FrameState) {
+                    FrameState x = (FrameState) usage;
+                    x.inputs().replace(node, Node.Null);
+                } else if (usage instanceof StoreField) {
+                    StoreField x = (StoreField) usage;
+                    assert x.object() == node;
+                    assert fields.get(x.field().name()) == null || fields.get(x.field().name()) == x.field();
+                    fields.put(x.field().name(), x.field());
+                } else if (usage instanceof AccessMonitor) {
+                    AccessMonitor x = (AccessMonitor) usage;
+                    TTY.println("replacing %d with %d (%s)", x.id(), x.next().id(), x.shortName());
+                    x.replace(x.next());
+                } else if (usage instanceof LoadField) {
+                    LoadField x = (LoadField) usage;
+                    assert x.object() == node;
+                    assert fields.get(x.field().name()) == null || fields.get(x.field().name()) == x.field();
+                    fields.put(x.field().name(), x.field());
+                } else if (usage instanceof RegisterFinalizer) {
+                    RegisterFinalizer x = (RegisterFinalizer) usage;
+                    x.replace(x.next());
+                } else {
+                    assert false;
+                }
+            }
+        }
+    }
+
+    private final GraalCompilation compilation;
+    private final IR ir;
+
+    public EscapeAnalysisPhase(GraalCompilation compilation, IR ir) {
+        this.compilation = compilation;
+        this.ir = ir;
+    }
+
+    @Override
+    protected void run(Graph graph) {
+//        if (compilation.method.holder().name().contains("jnt")) {
+            for (Node node : graph.getNodes()) {
+                if (node instanceof NewInstance && ((NewInstance) node).instanceClass().isResolved()) {
+                    Set<Node> exits = new HashSet<Node>();
+                    Set<Invoke> invokes = new HashSet<Invoke>();
+                    int iterations = 0;
+
+                    int weight;
+                    do {
+                        weight = analyse(node, exits, invokes);
+//                        TTY.print("%d: new value: %d %s, weight %d, escapes at ", iterations, node.id(), node.shortName(), weight);
+//                        for (Node n : exits) {
+//                            TTY.print("%d %s, ", n.id(), n.shortName());
+//                        }
+//                        for (Node n : invokes) {
+//                            TTY.print("%d %s, ", n.id(), n.shortName());
+//                        }
+//                        TTY.println();
+                        if (exits.size() != 0) {
+                            TTY.println("####### escaping object: %d in %s", node.id(), compilation.method);
+                            break;
+                        }
+                        if (invokes.size() == 0) {
+                            TTY.println("!!!!!!!! non-escaping object: %d in %s", node.id(), compilation.method);
+                            new EscapementFixup().apply(graph, node);
+                            break;
+                        }
+                        for (Invoke invoke : invokes) {
+                            new InliningPhase(compilation, ir, invoke, GraalOptions.TraceInlining).apply(graph);
+                        }
+                        exits.clear();
+                        invokes.clear();
+                    } while (weight >= GraalOptions.ForcedInlineEscapeWeight && iterations++ < 15);
+                }
+            }
+//        }
+    }
+
+    private int analyse(Node node, Collection<Node> exits, Collection<Invoke> invokes) {
+        int weight = 0;
+        for (Node usage : node.usages()) {
+            if (usage instanceof IsNonNull) {
+                IsNonNull x = (IsNonNull) usage;
+                weight++;
+            } else if (usage instanceof IsType) {
+                IsType x = (IsType) usage;
+                weight++;
+            } else if (usage instanceof FrameState) {
+                FrameState x = (FrameState) usage;
+            } else if (usage instanceof StoreField) {
+                StoreField x = (StoreField) usage;
+                if (x.value() == node) {
+                    exits.add(x);
+                } else {
+                    weight++;
+                }
+            } else if (usage instanceof AccessMonitor) {
+                AccessMonitor x = (AccessMonitor) usage;
+                weight++;
+            } else if (usage instanceof LoadField) {
+                LoadField x = (LoadField) usage;
+                weight++;
+            } else if (usage instanceof RegisterFinalizer) {
+                RegisterFinalizer x = (RegisterFinalizer) usage;
+                weight++;
+            } else if (usage instanceof Invoke) {
+                Invoke x = (Invoke) usage;
+                invokes.add(x);
+            } else {
+                exits.add(usage);
+            }
+        }
+        return weight;
+    }
+
+
+    public static enum Escape {
+        NewValue,
+        DoesNotEscape,
+        DoesEscape
+    }
+
+    public static interface EscapeOp extends Op {
+        Escape escape(Node node, Node value);
+    }
+}
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java	Tue Jun 21 14:32:12 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/GraphBuilderPhase.java	Wed Jun 22 11:55:42 2011 +0200
@@ -953,7 +953,7 @@
             append(deoptimize);
             frameState.pushReturn(resultType, Constant.defaultForKind(resultType, graph));
         } else {
-            Invoke invoke = new Invoke(bci(), opcode, resultType.stackKind(), args, target, target.signature().returnType(method.holder()), method.typeProfile(bci()), graph);
+            Invoke invoke = new Invoke(bci(), opcode, resultType.stackKind(), args, target, target.signature().returnType(method.holder()), graph);
             Value result = appendWithBCI(invoke);
             invoke.setExceptionEdge(handleException(null, bci()));
             frameState.pushReturn(resultType, result);
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java	Tue Jun 21 14:32:12 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/InliningPhase.java	Wed Jun 22 11:55:42 2011 +0200
@@ -32,25 +32,29 @@
 import com.oracle.max.graal.compiler.ir.Deoptimize.DeoptAction;
 import com.oracle.max.graal.compiler.value.*;
 import com.oracle.max.graal.graph.*;
+import com.sun.cri.bytecode.*;
 import com.sun.cri.ci.*;
 import com.sun.cri.ri.*;
 
 
 public class InliningPhase extends Phase {
 
+    public static HashMap<RiMethod, Integer> methodCount = new HashMap<RiMethod, Integer>();
+
     private final GraalCompilation compilation;
     private final IR ir;
 
     private final Queue<Invoke> invokes = new ArrayDeque<Invoke>();
     private final Queue<RiMethod> methods = new ArrayDeque<RiMethod>();
 
-    private final Map<Invoke, RiMethod> parentMethod = new HashMap<Invoke, RiMethod>();
     private int inliningSize;
     private final boolean trace;
+    private final Invoke hint;
 
-    public InliningPhase(GraalCompilation compilation, IR ir, boolean trace) {
+    public InliningPhase(GraalCompilation compilation, IR ir, Invoke hint, boolean trace) {
         this.compilation = compilation;
         this.ir = ir;
+        this.hint = hint;
         this.trace = trace;
     }
 
@@ -60,59 +64,33 @@
         inliningSize += method.codeSize();
     }
 
-    public static HashMap<RiMethod, Integer> methodCount = new HashMap<RiMethod, Integer>();
+    private Queue<Invoke> newInvokes = new ArrayDeque<Invoke>();
+    private Graph graph;
+
     @Override
     protected void run(Graph graph) {
+        this.graph = graph;
+
         float ratio = GraalOptions.MaximumInlineRatio;
         inliningSize = compilation.method.codeSize();
+
+        if (hint != null) {
+            newInvokes.add(hint);
+        } else {
+            for (Invoke invoke : graph.getNodes(Invoke.class)) {
+                newInvokes.add(invoke);
+            }
+        }
+
         for (int iterations = 0; iterations < GraalOptions.MaximumInlineLevel; iterations++) {
-            for (Invoke invoke : graph.getNodes(Invoke.class)) {
-                RiMethod parent = parentMethod.get(invoke);
-                if (parent == null) {
-                    parent = compilation.method;
-                }
-                RiTypeProfile profile = parent.typeProfile(invoke.bci);
-                if (!checkInvokeConditions(invoke)) {
-                    continue;
-                }
-                if (invoke.target.canBeStaticallyBound()) {
-                    if (checkTargetConditions(invoke.target, iterations) && checkSizeConditions(invoke.target, invoke, profile, ratio)) {
-                        addToQueue(invoke, invoke.target);
+            Queue<Invoke> queue = newInvokes;
+            newInvokes = new ArrayDeque<Invoke>();
+            for (Invoke invoke : queue) {
+                if (!invoke.isDeleted()) {
+                    inlineInvoke(invoke, iterations, ratio);
+                    if (inliningSize > GraalOptions.MaximumInstructionCount) {
+                        break;
                     }
-                } else {
-                    RiMethod concrete = invoke.target.holder().uniqueConcreteMethod(invoke.target);
-                    if (concrete != null) {
-                        if (checkTargetConditions(concrete, iterations) && checkSizeConditions(concrete, invoke, profile, ratio)) {
-                            if (trace) {
-                                String targetName = CiUtil.format("%H.%n(%p):%r", invoke.target, false);
-                                String concreteName = CiUtil.format("%H.%n(%p):%r", concrete, false);
-                                TTY.println("recording concrete method assumption: %s -> %s", targetName, concreteName);
-                            }
-                            compilation.assumptions.recordConcreteMethod(invoke.target, concrete);
-                            addToQueue(invoke, concrete);
-                        }
-                    } else if (profile != null && profile.probabilities != null && profile.probabilities.length > 0 && profile.morphism == 1) {
-                        if (GraalOptions.InlineWithTypeCheck) {
-                            // type check and inlining...
-                            concrete = profile.types[0].resolveMethodImpl(invoke.target);
-                            if (concrete != null && checkTargetConditions(concrete, iterations) && checkSizeConditions(concrete, invoke, profile, ratio)) {
-                                IsType isType = new IsType(invoke.receiver(), profile.types[0], compilation.graph);
-                                FixedGuard guard = new FixedGuard(graph);
-                                guard.setNode(isType);
-                                assert invoke.predecessors().size() == 1;
-                                invoke.predecessors().get(0).successors().replace(invoke, guard);
-                                guard.setNext(invoke);
-
-                                if (trace) {
-                                    TTY.println("inlining with type check, type probability: %5.3f", profile.probabilities[0]);
-                                }
-                                addToQueue(invoke, concrete);
-                            }
-                        }
-                    }
-                }
-                if (inliningSize > GraalOptions.MaximumInstructionCount) {
-                    break;
                 }
             }
 
@@ -157,16 +135,65 @@
         }
     }
 
+    private void inlineInvoke(Invoke invoke, int iterations, float ratio) {
+        RiMethod parent = invoke.stateAfter().method();
+        RiTypeProfile profile = parent.typeProfile(invoke.bci);
+        if (!checkInvokeConditions(invoke)) {
+            return;
+        }
+        if (invoke.opcode() == Bytecodes.INVOKESPECIAL || invoke.target.canBeStaticallyBound()) {
+            if (checkTargetConditions(invoke.target, iterations) && checkSizeConditions(invoke.target, invoke, profile, ratio)) {
+                addToQueue(invoke, invoke.target);
+            }
+        } else {
+            RiMethod concrete = invoke.target.holder().uniqueConcreteMethod(invoke.target);
+            if (concrete != null) {
+                if (checkTargetConditions(concrete, iterations) && checkSizeConditions(concrete, invoke, profile, ratio)) {
+                    if (trace) {
+                        String targetName = CiUtil.format("%H.%n(%p):%r", invoke.target, false);
+                        String concreteName = CiUtil.format("%H.%n(%p):%r", concrete, false);
+                        TTY.println("recording concrete method assumption: %s -> %s", targetName, concreteName);
+                    }
+                    compilation.assumptions.recordConcreteMethod(invoke.target, concrete);
+                    addToQueue(invoke, concrete);
+                }
+            } else if (profile != null && profile.probabilities != null && profile.probabilities.length > 0 && profile.morphism == 1) {
+                if (GraalOptions.InlineWithTypeCheck) {
+                    // type check and inlining...
+                    concrete = profile.types[0].resolveMethodImpl(invoke.target);
+                    if (concrete != null && checkTargetConditions(concrete, iterations) && checkSizeConditions(concrete, invoke, profile, ratio)) {
+                        IsType isType = new IsType(invoke.receiver(), profile.types[0], compilation.graph);
+                        FixedGuard guard = new FixedGuard(graph);
+                        guard.setNode(isType);
+                        assert invoke.predecessors().size() == 1;
+                        invoke.predecessors().get(0).successors().replace(invoke, guard);
+                        guard.setNext(invoke);
+
+                        if (trace) {
+                            TTY.println("inlining with type check, type probability: %5.3f", profile.probabilities[0]);
+                        }
+                        addToQueue(invoke, concrete);
+                    }
+                } else {
+                    if (trace) {
+                        TTY.println("not inlining %s because GraalOptions.InlineWithTypeCheck is false", methodName(invoke.target, invoke));
+                    }
+                }
+            } else {
+            if (trace) {
+                TTY.println("not inlining %s because no monomorphic receiver could be found", methodName(invoke.target, invoke));
+            }
+        }
+        }
+    }
+
     private String methodName(RiMethod method) {
         return CiUtil.format("%H.%n(%p):%r", method, false) + " (" + method.codeSize() + " bytes)";
     }
 
     private String methodName(RiMethod method, Invoke invoke) {
         if (invoke != null) {
-            RiMethod parent = parentMethod.get(invoke);
-            if (parent == null) {
-                parent = compilation.method;
-            }
+            RiMethod parent = invoke.stateAfter().method();
             return parent.name() + "@" + invoke.bci + ": " + CiUtil.format("%H.%n(%p):%r", method, false) + " (" + method.codeSize() + " bytes)";
         } else {
             return CiUtil.format("%H.%n(%p):%r", method, false) + " (" + method.codeSize() + " bytes)";
@@ -241,7 +268,11 @@
     }
 
     private boolean checkStaticSizeConditions(RiMethod method, Invoke invoke) {
-        if (method.codeSize() > GraalOptions.MaximumInlineSize) {
+        int maximumSize = GraalOptions.MaximumInlineSize;
+        if (invoke == hint) {
+            maximumSize = GraalOptions.MaximumFreqInlineSize;
+        }
+        if (method.codeSize() > maximumSize) {
             if (trace) {
                 TTY.println("not inlining %s because of code size (size: %d, max size: %d)", methodName(method, invoke), method.codeSize(), GraalOptions.MaximumInlineSize);
             }
@@ -254,10 +285,7 @@
         int maximumSize = GraalOptions.MaximumTrivialSize;
         float ratio = 0;
         if (profile != null && profile.count > 0) {
-            RiMethod parent = parentMethod.get(invoke);
-            if (parent == null) {
-                parent = compilation.method;
-            }
+            RiMethod parent = invoke.stateAfter().method();
             ratio = profile.count / (float) parent.invocationCount();
             if (ratio >= GraalOptions.FreqInlineRatio) {
                 maximumSize = GraalOptions.MaximumFreqInlineSize;
@@ -265,6 +293,9 @@
                 maximumSize = GraalOptions.MaximumInlineSize;
             }
         }
+        if (invoke == hint) {
+            maximumSize = GraalOptions.MaximumFreqInlineSize;
+        }
         if (method.codeSize() > maximumSize) {
             if (trace) {
                 TTY.println("not inlining %s because of code size (size: %d, max size: %d, ratio %5.3f, %s)", methodName(method, invoke), method.codeSize(), maximumSize, ratio, profile);
@@ -356,7 +387,7 @@
 
         for (Node node : duplicates.values()) {
             if (node instanceof Invoke) {
-                parentMethod.put((Invoke) node, method);
+                newInvokes.add((Invoke) node);
             }
         }
 
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java	Tue Jun 21 14:32:12 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/schedule/Block.java	Wed Jun 22 11:55:42 2011 +0200
@@ -24,6 +24,7 @@
 
 import java.util.*;
 
+import com.oracle.max.graal.compiler.debug.*;
 import com.oracle.max.graal.compiler.ir.*;
 import com.oracle.max.graal.graph.*;
 
@@ -138,4 +139,40 @@
     public void setInstructions(List<Node> instructions) {
         this.instructions = instructions;
     }
+
+
+    public static void iteratePostOrder(List<Block> blocks, BlockClosure closure) {
+        BitMap visited = new BitMap(blocks.size());
+        LinkedList<Block> workList = new LinkedList<Block>();
+        for (Block block : blocks) {
+            if (block.getPredecessors().size() == 0) {
+                workList.add(block);
+                visited.set(block.blockID());
+            }
+        }
+
+        while (!workList.isEmpty()) {
+            Block b = workList.remove();
+
+            closure.apply(b);
+
+            for (Block succ : b.getSuccessors()) {
+                if (!visited.get(succ.blockID())) {
+                    boolean delay = false;
+                    for (Block pred : succ.getPredecessors()) {
+                        if (!visited.get(pred.blockID()) && !(pred.lastNode instanceof LoopEnd)) {
+                            TTY.println("missing pred: %d", pred.blockID());
+                            delay = true;
+                            break;
+                        }
+                    }
+
+                    if (!delay) {
+                        visited.set(succ.blockID());
+                        workList.add(succ);
+                    }
+                }
+            }
+        }
+    }
 }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java	Tue Jun 21 14:32:12 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/value/FrameState.java	Wed Jun 22 11:55:42 2011 +0200
@@ -121,6 +121,10 @@
         return rethrowException;
     }
 
+    public RiMethod method() {
+        return method;
+    }
+
     /**
      * Gets a copy of this frame state.
      */