changeset 3108:44b3508a12c8

Make NewInstance a FixedWithNext to avoid it from floating too much (could be hoisted out of loops for exemple). Fixes for loop peeling
author Gilles Duboscq <gilles.duboscq@oracle.com>
date Fri, 01 Jul 2011 12:56:52 +0200
parents 9ef0777a61d5
children 3664989976e2
files graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinterObserver.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/LoopPhase.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/GraphUtil.java graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java src/share/tools/IdealGraphVisualizer/Coordinator/src/com/sun/hotspot/igv/coordinator/StandardGroupOrganizer.java
diffstat 6 files changed, 169 insertions(+), 79 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinterObserver.java	Thu Jun 30 10:07:49 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/debug/IdealGraphPrinterObserver.java	Fri Jul 01 12:56:52 2011 +0200
@@ -140,13 +140,18 @@
 
     @Override
     public void compilationEvent(CompilationEvent event) {
+        boolean lazyStart = false;
         if (printer == null && event.isErrorEvent()) {
-            this.compilationStarted(event); // lazy start
+            this.compilationStarted(event);
+            lazyStart = true;
         }
         if (printer != null && event.getGraph() != null && event.isHIRValid()) {
             Graph graph = event.getGraph();
             printer.print(graph, event.getLabel(), true, event.getDebugObjects());
         }
+        if (lazyStart) {
+            this.compilationFinished(event);
+        }
     }
 
     @Override
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewInstance.java	Thu Jun 30 10:07:49 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/NewInstance.java	Fri Jul 01 12:56:52 2011 +0200
@@ -35,7 +35,7 @@
 /**
  * The {@code NewInstance} instruction represents the allocation of an instance class object.
  */
-public final class NewInstance extends FloatingNode {
+public final class NewInstance extends FixedNodeWithNext {
     private static final EscapeOp ESCAPE = new NewInstanceEscapeOp();
 
     private static final int INPUT_COUNT = 0;
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java	Thu Jun 30 10:07:49 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/LoopPhase.java	Fri Jul 01 12:56:52 2011 +0200
@@ -38,14 +38,15 @@
     protected void run(Graph graph) {
         List<Loop> loops = LoopUtil.computeLoops(graph);
 
+//        for (Loop loop : loops) {
+//            System.out.println("Peel loop : " + loop.loopBegin());
+//            LoopUtil.peelLoop(loop);
+//        }
+//        loops = LoopUtil.computeLoops(graph); // TODO (gd) avoid recomputing loops
+
         for (Loop loop : loops) {
-            LoopUtil.peelLoop(loop);
+            doLoopCounters(loop);
         }
-        loops = LoopUtil.computeLoops(graph); // TODO (gd) avoid recomputing loops
-
-//        for (Loop loop : loops) {
-//            doLoopCounters(loop);
-//        }
     }
 
     private void doLoopCounters(Loop loop) {
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/GraphUtil.java	Thu Jun 30 10:07:49 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/GraphUtil.java	Fri Jul 01 12:56:52 2011 +0200
@@ -30,6 +30,7 @@
 import com.oracle.max.graal.compiler.observer.*;
 import com.oracle.max.graal.compiler.value.*;
 import com.oracle.max.graal.graph.*;
+import com.oracle.max.graal.graph.NodeWorkList.*;
 
 public class GraphUtil {
 
@@ -174,9 +175,16 @@
                         Value v = phi.valueAt(i);
                         if (v != null) {
                             T color = internalColoring.get(merge.phiPredecessorAt(i));
-                            Value replace = lambda.fixPhiInput(v, color);
-                            if (replace != v) {
-                                phi.setValueAt(i, replace);
+                            if (color != null) {
+                                Value replace = lambda.fixPhiInput(v, color);
+                                if (replace != v) {
+                                    phi.setValueAt(i, replace);
+                                } else {
+                                    if (lambda.explore(v) && coloring.get(v) == null && !work.isNew(v)) {
+                                        //System.out.println("Split : Add input " + input + " to work from " + node);
+                                        work.add(v);
+                                    }
+                                }
                             }
                         }
                     }
@@ -266,37 +274,39 @@
                             }
                         }
                     }
-                }
+                    if (node instanceof StateSplit) {
+                        FrameState stateAfter = ((StateSplit) node).stateAfter();
+                        if (stateAfter != null && lambda.explore(stateAfter) && !work.isNew(stateAfter)) {
+                            //System.out.println("Split : Add framestate to work");
+                            work.add(stateAfter);
+                        }
+                    }
 
-                if (node instanceof StateSplit) {
-                    FrameState stateAfter = ((StateSplit) node).stateAfter();
-                    if (stateAfter != null && lambda.explore(stateAfter) && !work.isNew(stateAfter)) {
-                        //System.out.println("Split : Add framestate to work");
-                        work.add(stateAfter);
+                    if (node instanceof Merge) {
+                        for (Node usage : node.usages()) {
+                            if (!work.isNew(usage)) {
+                                work.add(usage);
+                            }
+                        }
                     }
-                }
 
-                if (node instanceof Merge) {
-                    for (Node usage : node.usages()) {
-                        if (!work.isNew(usage)) {
-                            work.add(usage);
+                    if (node instanceof LoopEnd) {
+                        work.add(((LoopEnd) node).loopBegin());
+                    }
+
+                    for (Node input : node.dataInputs()) {
+                        if (lambda.explore(input) && coloring.get(input) == null && !work.isNew(input)) {
+                            //System.out.println("Split : Add input " + input + " to work from " + node);
+                            work.add(input);
                         }
                     }
                 }
-
-                if (node instanceof LoopEnd) {
-                    work.add(((LoopEnd) node).loopBegin());
-                }
-
-                for (Node input : node.dataInputs()) {
-                    if (lambda.explore(input) && coloring.get(input) == null && !work.isNew(input)) {
-                        //System.out.println("Split : Add input " + input + " to work from " + node);
-                        work.add(input);
-                    }
-                }
             }
-        } catch (RuntimeException re) {
-            re.printStackTrace();
+        } catch (InfiniteWorkException re) {
+            System.out.println("Infinite work, current queue :");
+            for (Node n : work) {
+                System.out.println(" - " + n);
+            }
             GraalCompilation compilation = GraalCompilation.compilation();
             if (compilation.compiler.isObserved()) {
                 NodeMap<T> debugColoring = coloring.graph().createNodeMap();
@@ -307,6 +317,17 @@
                 debug.put("split", debugColoring);
                 compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "RuntimeException in split", coloring.graph(), true, false, true, debug));
             }
+            throw re;
+        }
+        GraalCompilation compilation = GraalCompilation.compilation();
+        if (compilation.compiler.isObserved()) {
+            NodeMap<T> debugColoring = coloring.graph().createNodeMap();
+            for (Entry<Node, T> entry : internalColoring.entrySet()) {
+                debugColoring.set(entry.getKey(), entry.getValue());
+            }
+            Map<String, Object> debug = new HashMap<String, Object>();
+            debug.put("split", debugColoring);
+            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "Split end!!", coloring.graph(), true, false, debug));
         }
     }
 }
--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java	Thu Jun 30 10:07:49 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/util/LoopUtil.java	Fri Jul 01 12:56:52 2011 +0200
@@ -39,9 +39,9 @@
 
     public static class Loop {
         private final LoopBegin loopBegin;
-        private final NodeBitMap nodes;
+        private NodeBitMap nodes;
         private Loop parent;
-        private final NodeBitMap exits;
+        private NodeBitMap exits;
         public Loop(LoopBegin loopBegin, NodeBitMap nodes, NodeBitMap exits) {
             this.loopBegin = loopBegin;
             this.nodes = nodes;
@@ -67,6 +67,10 @@
         public void setParent(Loop parent) {
             this.parent = parent;
         }
+
+        public boolean isChild(Loop loop) {
+            return loop.parent != null && (loop.parent == this || loop.parent.isChild(this));
+        }
     }
 
     private static class PeelingResult {
@@ -90,26 +94,8 @@
         List<Loop> loops = new LinkedList<LoopUtil.Loop>();
         for (LoopBegin loopBegin : graph.getNodes(LoopBegin.class)) {
             NodeBitMap nodes = computeLoopNodes(loopBegin);
-            NodeBitMap exits = graph.createNodeBitMap();
-            Loop loop = new Loop(loopBegin, nodes, exits);
-            NodeFlood workCFG = graph.createNodeFlood();
-            workCFG.add(loopBegin.loopEnd());
-            for (Node n : workCFG) {
-                if (n == loopBegin) {
-                    continue;
-                }
-                if (IdentifyBlocksPhase.trueSuccessorCount(n) > 1) {
-                    for (Node sux : n.cfgSuccessors()) {
-                        if (!nodes.isMarked(sux) && sux instanceof FixedNode) {
-                            exits.mark(sux);
-                        }
-                    }
-                }
-                for (Node pred : n.cfgPredecessors()) {
-                    workCFG.add(pred);
-                }
-            }
-            loops.add(loop);
+            NodeBitMap exits = computeLoopExits(loopBegin, nodes);
+            loops.add(new Loop(loopBegin, nodes, exits));
         }
         for (Loop loop : loops) {
             for (Loop other : loops) {
@@ -123,6 +109,29 @@
         return loops;
     }
 
+    public static NodeBitMap computeLoopExits(LoopBegin loopBegin, NodeBitMap nodes) {
+        Graph graph = loopBegin.graph();
+        NodeBitMap exits = graph.createNodeBitMap();
+        NodeFlood workCFG = graph.createNodeFlood();
+        workCFG.add(loopBegin.loopEnd());
+        for (Node n : workCFG) {
+            if (n == loopBegin) {
+                continue;
+            }
+            if (IdentifyBlocksPhase.trueSuccessorCount(n) > 1) {
+                for (Node sux : n.cfgSuccessors()) {
+                    if (!nodes.isMarked(sux) && sux instanceof FixedNode) {
+                        exits.mark(sux);
+                    }
+                }
+            }
+            for (Node pred : n.cfgPredecessors()) {
+                workCFG.add(pred);
+            }
+        }
+        return exits;
+    }
+
     public static NodeBitMap computeLoopNodes(LoopBegin loopBegin) {
         return computeLoopNodesFrom(loopBegin, loopBegin.loopEnd());
     }
@@ -138,7 +147,7 @@
         }
         NodeBitMap inOrAfter = loopBegin.graph().createNodeBitMap();
         for (Node n : workData1) {
-            inOrAfter.mark(n);
+            markWithState(n, inOrAfter);
             for (Node usage : n.dataUsages()) {
                 if (usage instanceof Phi) { // filter out data graph cycles
                     Phi phi = (Phi) usage;
@@ -158,13 +167,13 @@
         }
         NodeBitMap inOrBefore = loopBegin.graph().createNodeBitMap();
         for (Node n : workData2) {
-            inOrBefore.mark(n);
-            if (n instanceof Phi) {
+            markWithState(n, inOrBefore);
+            if (n instanceof Phi) { // filter out data graph cycles
                 Phi phi = (Phi) n;
                 if (!phi.isDead()) {
                     int backIndex = -1;
                     Merge merge = phi.merge();
-                    if (merge instanceof LoopBegin) {
+                    if (!loopNodes.isMarked(merge) && merge instanceof LoopBegin) {
                         LoopBegin phiLoop = (LoopBegin) merge;
                         backIndex = phiLoop.phiPredecessorIndex(phiLoop.loopEnd());
                     }
@@ -193,7 +202,7 @@
                 debug.put("loopNodes", loopNodes);
                 debug.put("inOrAfter", inOrAfter);
                 debug.put("inOrBefore", inOrBefore);
-                compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "Compute loop nodes", loopBegin.graph(), true, false, debug));
+                compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "Compute loop nodes loop#" + loopBegin.id(), loopBegin.graph(), true, false, debug));
             }
             recurse = false;
         }
@@ -268,6 +277,13 @@
         if (compilation.compiler.isObserved()) {
             compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After rewirePeeling", loopEnd.graph(), true, false));
         }
+        // update parents
+        Loop parent = loop.parent();
+        while (parent != null) {
+            parent.nodes = computeLoopNodes(loop.loopBegin);
+            parent.exits = computeLoopExits(parent.loopBegin, parent.nodes);
+            parent = parent.parent;
+        }
     }
 
     private static void rewirePeeling(PeelingResult peeling, Loop loop, FixedNode from) {
@@ -501,7 +517,7 @@
             }
             @Override
             public boolean explore(Node n) {
-                return !inOrBefore.isNew(n) && !inOrBefore.isMarked(n) && !(n instanceof Local); //TODO (gd) hum
+                return !inOrBefore.isNew(n) && !inOrBefore.isMarked(n) && !(n instanceof Local) && !(n instanceof Constant); //TODO (gd) hum
             }
             @Override
             public void fixNode(Node node, Node color) {
@@ -546,16 +562,17 @@
             compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "After computeLoopNodesFrom", loopBegin.graph(), true, false, debug));
         }
         if (from == loopBegin.loopEnd()) {
-            marked.clear(from);
+            clearWithState(from, marked);
         }
-        marked.clear(loopBegin);
+        clearWithState(loopBegin, marked);
         Map<Node, Node> replacements = new HashMap<Node, Node>();
         NodeMap<Placeholder> phis = graph.createNodeMap();
         NodeMap<Placeholder> exits = graph.createNodeMap();
 
         for (Node exit : loop.exits()) {
             if (marked.isMarked(exit.singlePredecessor())) {
-                marked.mark(((Placeholder) exit).stateAfter());
+                Placeholder pExit = (Placeholder) exit;
+                marked.mark(pExit.stateAfter());
                 Placeholder p = new Placeholder(graph);
                 replacements.put(exit, p);
                 exits.set(exit, p);
@@ -563,12 +580,6 @@
         }
 
         for (Node n : marked) {
-            if (n instanceof StateSplit) {
-                FrameState stateAfter = ((StateSplit) n).stateAfter();
-                if (stateAfter != null) {
-                    marked.mark(stateAfter);
-                }
-            }
             if (n instanceof Phi && ((Phi) n).merge() == loopBegin) {
                 Placeholder p = new Placeholder(graph);
                 replacements.put(n, p);
@@ -586,7 +597,7 @@
         if (compilation.compiler.isObserved()) {
             Map<String, Object> debug = new HashMap<String, Object>();
             debug.put("marked", marked);
-            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "Before addDuplicate", loopBegin.graph(), true, false, debug));
+            compilation.compiler.fireCompilationEvent(new CompilationEvent(compilation, "Before addDuplicate loop#" + loopBegin.id(), loopBegin.graph(), true, false, debug));
         }
 
         Map<Node, Node> duplicates = graph.addDuplicate(marked, replacements);
@@ -596,7 +607,7 @@
             for (Node usage : n.dataUsages()) {
                 if (!marked.isMarked(usage)
                                 && !loop.nodes().isNew(usage) && loop.nodes().isMarked(usage)
-                                && !((usage instanceof Phi) || ((Phi) usage).merge() != loopBegin)) {
+                                && !((usage instanceof Phi) && ((Phi) usage).merge() != loopBegin)) {
                     dataOut.set(n, duplicates.get(n));
                     break;
                 }
@@ -624,18 +635,70 @@
         Graph graph = loop.loopBegin().graph();
         NodeBitMap inOrBefore = graph.createNodeBitMap();
         NodeFlood work = graph.createNodeFlood();
-        work.addAll(loop.nodes());
+        NodeBitMap loopNodes = loop.nodes();
+        work.addAll(loopNodes);
         for (Node n : work) {
             inOrBefore.mark(n);
             for (Node pred : n.predecessors()) {
                 work.add(pred);
             }
-            for (Node in : n.inputs()) {
-                if (in != null) {
-                    work.add(in);
+            if (n instanceof Phi) { // filter out data graph cycles
+                Phi phi = (Phi) n;
+                if (!phi.isDead()) {
+                    int backIndex = -1;
+                    Merge merge = phi.merge();
+                    if (!loopNodes.isNew(merge) && !loopNodes.isMarked(merge) && merge instanceof LoopBegin) {
+                        LoopBegin phiLoop = (LoopBegin) merge;
+                        backIndex = phiLoop.phiPredecessorIndex(phiLoop.loopEnd());
+                    }
+                    for (int i = 0; i < phi.valueCount(); i++) {
+                        if (i != backIndex) {
+                            work.add(phi.valueAt(i));
+                        }
+                    }
+                }
+            } else {
+                for (Node in : n.inputs()) {
+                    if (in != null) {
+                        work.add(in);
+                    }
+                }
+                if (n instanceof LoopBegin) {
+                    Loop p = loop.parent;
+                    boolean isParent = false;
+                    while (p != null) {
+                        if (p.loopBegin() == n) {
+                            isParent = true;
+                            break;
+                        }
+                        p = p.parent;
+                    }
+                    if (!isParent) {
+                        work.add(((LoopBegin) n).loopEnd());
+                    }
                 }
             }
         }
         return inOrBefore;
     }
+
+    private static void markWithState(Node n, NodeBitMap map) {
+        map.mark(n);
+        if (n instanceof StateSplit) {
+            FrameState stateAfter = ((StateSplit) n).stateAfter();
+            if (stateAfter != null) {
+                map.mark(stateAfter);
+            }
+        }
+    }
+
+    private static void clearWithState(Node n, NodeBitMap map) {
+        map.clear(n);
+        if (n instanceof StateSplit) {
+            FrameState stateAfter = ((StateSplit) n).stateAfter();
+            if (stateAfter != null) {
+                map.clear(stateAfter);
+            }
+        }
+    }
 }
--- a/src/share/tools/IdealGraphVisualizer/Coordinator/src/com/sun/hotspot/igv/coordinator/StandardGroupOrganizer.java	Thu Jun 30 10:07:49 2011 +0200
+++ b/src/share/tools/IdealGraphVisualizer/Coordinator/src/com/sun/hotspot/igv/coordinator/StandardGroupOrganizer.java	Fri Jul 01 12:56:52 2011 +0200
@@ -51,7 +51,7 @@
                 List<Group> children = new ArrayList<Group>();
                 children.add(g);
                 if(g.getGraphs().size() == 1) {
-                    //g.getGraphs().get(0).setName(g.getName() + " / " + g.getGraphs().get(0).getName());
+                    g.getGraphs().get(0).setName(g.getName() + " / " + g.getGraphs().get(0).getName());
                     result.add(new Pair<String, List<Group>>("", children));
                 } else {
                     Pair<String, List<Group>> p = new Pair<String, List<Group>>();