# HG changeset patch
# User Thomas Wuerthinger <thomas@wuerthinger.net>
# Date 1305894142 -7200
# Node ID 0fe79e7435c370a0252f890060610a90994f0917
# Parent  114fc809462f7bb9c7cf05c59e0e7f1da45929a5
More scheduling. Removed need for cfg iteration in the phi simplifier.

diff -r 114fc809462f -r 0fe79e7435c3 graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java	Fri May 20 12:08:58 2011 +0200
+++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java	Fri May 20 14:22:22 2011 +0200
@@ -27,6 +27,7 @@
 
 public class Block {
 
+    private int blockID;
     private final List<Block> successors = new ArrayList<Block>();
     private final List<Block> predecessors = new ArrayList<Block>();
 
@@ -38,8 +39,21 @@
         return Collections.unmodifiableList(predecessors);
     }
 
+    public Block(int blockID) {
+        this.blockID = blockID;
+    }
+
     public void addSuccessor(Block other) {
         successors.add(other);
         other.predecessors.add(this);
     }
+
+    public int blockID() {
+        return blockID;
+    }
+
+    @Override
+    public String toString() {
+        return "B" + blockID;
+    }
 }
diff -r 114fc809462f -r 0fe79e7435c3 graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java	Fri May 20 12:08:58 2011 +0200
+++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java	Fri May 20 14:22:22 2011 +0200
@@ -25,6 +25,8 @@
 import java.util.*;
 
 import com.oracle.graal.graph.*;
+import com.sun.c1x.debug.*;
+import com.sun.c1x.ir.*;
 
 
 public class Schedule {
@@ -38,12 +40,96 @@
         identifyBlocks();
     }
 
+    private Block createBlock() {
+        Block b = new Block(blocks.size());
+        blocks.add(b);
+        return b;
+    }
+
+    private Block assignBlock(Node n) {
+        Block curBlock = nodeToBlock.get(n);
+        if (curBlock == null) {
+            curBlock = createBlock();
+            nodeToBlock.set(n, curBlock);
+        }
+        return curBlock;
+    }
+
     private void identifyBlocks() {
-        NodeIterator.doBFS(EdgeType.SUCCESSORS, graph.root(), new NodeVisitor() {
+        final NodeBitMap bottomUpBitMap = NodeIterator.iterate(EdgeType.PREDECESSORS, graph.end(), null);
+        NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start(), new NodeVisitor() {
             @Override
             public boolean visit(Node n) {
+                if (!bottomUpBitMap.isMarked(n)) {
+                    return false;
+                }
+
+                Node singlePred = null;
+                for (Node pred : n.predecessors()) {
+                    if (pred != null && bottomUpBitMap.isMarked(pred)) {
+                        if (singlePred == null) {
+                            singlePred = pred;
+                        } else {
+                            // We have more than one predecessor => we are a merge block.
+                            assignBlock(n);
+                            return true;
+                        }
+                    }
+                }
+
+                if (singlePred == null) {
+                    // We have no predecessor => we are the start block.
+                    assignBlock(n);
+                } else {
+                    // We have a single predecessor => its successor count.
+                    int successorCount = 0;
+                    for (Node succ : singlePred.successors()) {
+                        if (succ != null && bottomUpBitMap.isMarked(succ)) {
+                            successorCount++;
+                            if (successorCount > 1) {
+                                // Our predecessor is a split => we need a new block.
+                                assignBlock(n);
+                                return true;
+                            }
+                        }
+                    }
+                    nodeToBlock.set(n, nodeToBlock.get(singlePred));
+                }
                 return true;
+            }}
+        );
+    }
+
+    private void print() {
+        TTY.println("============================================");
+        TTY.println("%d blocks", blocks.size());
+        for (Block b : blocks) {
+           TTY.print(b.toString());
+
+           TTY.print(" succs=");
+           for (Block succ : b.getSuccessors()) {
+               TTY.print(succ + ";");
+           }
+
+           TTY.print(" preds=");
+           for (Block pred : b.getPredecessors()) {
+               TTY.print(pred + ";");
+           }
+           TTY.println();
+        }
+
+
+        TTY.println("============================================");
+        TTY.println("%d nodes", nodeToBlock.size());
+        for (Node n : graph.getNodes()) {
+            if (n != null) {
+                TTY.print("Node %d: %s", n.id(), n.getClass().toString());
+                Block curBlock = nodeToBlock.get(n);
+                if (curBlock != null) {
+                    TTY.print(" %s", curBlock);
+                }
+                TTY.println();
             }
-        });
+        }
     }
 }
diff -r 114fc809462f -r 0fe79e7435c3 graal/GraalCompiler/src/com/sun/c1x/gen/PhiSimplifier.java
--- a/graal/GraalCompiler/src/com/sun/c1x/gen/PhiSimplifier.java	Fri May 20 12:08:58 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/gen/PhiSimplifier.java	Fri May 20 14:22:22 2011 +0200
@@ -22,6 +22,7 @@
  */
 package com.sun.c1x.gen;
 
+import com.oracle.graal.graph.*;
 import com.sun.c1x.graph.*;
 import com.sun.c1x.ir.*;
 import com.sun.c1x.value.*;
@@ -37,7 +38,15 @@
 
     public PhiSimplifier(IR ir) {
         this.ir = ir;
-        ir.getHIRStartBlock().iterateAnyOrder(this, false);
+        //ir.getHIRStartBlock().iterateAnyOrder(this, false);
+
+        for (Node n : ir.compilation.graph.getNodes()) {
+            if (n instanceof Phi) {
+                simplify((Phi)n);
+            }
+        }
+
+
     }
 
     /**
diff -r 114fc809462f -r 0fe79e7435c3 graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java
--- a/graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java	Fri May 20 12:08:58 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/graph/GraphBuilder.java	Fri May 20 14:22:22 2011 +0200
@@ -180,7 +180,7 @@
         BlockBegin startBlockBegin = new BlockBegin(0, startBlock.blockID, graph);
         startBlock.firstInstruction = startBlockBegin;
 
-        graph.root().setStart(startBlockBegin);
+        graph.start().setStart(startBlockBegin);
 
         RiExceptionHandler[] handlers = rootMethod.exceptionHandlers();
         if (handlers != null && handlers.length > 0) {
diff -r 114fc809462f -r 0fe79e7435c3 graal/GraalCompiler/src/com/sun/c1x/graph/IR.java
--- a/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java	Fri May 20 12:08:58 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java	Fri May 20 14:22:22 2011 +0200
@@ -256,6 +256,6 @@
     }
 
     public BlockBegin getHIRStartBlock() {
-        return (BlockBegin) compilation.graph.root().successors().get(0);
+        return (BlockBegin) compilation.graph.start().successors().get(0);
     }
 }
diff -r 114fc809462f -r 0fe79e7435c3 graal/GraalCompiler/src/com/sun/c1x/ir/BlockBegin.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/BlockBegin.java	Fri May 20 12:08:58 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/BlockBegin.java	Fri May 20 14:22:22 2011 +0200
@@ -116,7 +116,7 @@
      */
     @SuppressWarnings({ "unchecked", "rawtypes" })
     public List<Instruction> blockPredecessors() {
-        if (predecessors().size() == 1 && predecessors().get(0) == graph().root()) {
+        if (predecessors().size() == 1 && predecessors().get(0) == graph().start()) {
             return Collections.EMPTY_LIST;
         } else {
             return (List) Collections.unmodifiableList(predecessors());
@@ -145,65 +145,6 @@
     }
 
     /**
-     * Iterate over all blocks transitively reachable from this block.
-     * @param closure the closure to apply to each block
-     * @param predecessors {@code true} if also to include this blocks predecessors
-     */
-    public void iterateAnyOrder(BlockClosure closure, boolean predecessors) {
-        IdentityHashMap<BlockBegin, BlockBegin> mark = new IdentityHashMap<BlockBegin, BlockBegin>();
-        LinkedList<BlockBegin> queue = new LinkedList<BlockBegin>();
-        queue.offer(this);
-        mark.put(this, this);
-        BlockBegin block;
-        while ((block = queue.poll()) != null) {
-            closure.apply(block);
-
-            Instruction inst = block;
-            ArrayList<BlockBegin> excBlocks = new ArrayList<BlockBegin>();
-            while (inst != null) {
-                if (inst instanceof ExceptionEdgeInstruction) {
-                    excBlocks.add(((ExceptionEdgeInstruction) inst).exceptionEdge());
-                }
-                inst = inst.next();
-            }
-            while (excBlocks.remove(null)) {
-                // nothing
-            }
-            if (excBlocks.size() > 0) {
-                queueBlocks(queue, excBlocks, mark);
-            }
-
-            queueBlocks(queue, block.end().blockSuccessors(), mark);
-            if (predecessors) {
-                queueBlockEnds(queue, block.blockPredecessors(), mark);
-            }
-        }
-    }
-
-    private void queueBlocks(LinkedList<BlockBegin> queue, List<BlockBegin> list, IdentityHashMap<BlockBegin, BlockBegin> mark) {
-        if (list != null) {
-            for (BlockBegin b : list) {
-                if (!mark.containsKey(b)) {
-                    queue.offer(b);
-                    mark.put(b, b);
-                }
-            }
-        }
-    }
-
-    private void queueBlockEnds(LinkedList<BlockBegin> queue, List<Instruction> list, IdentityHashMap<BlockBegin, BlockBegin> mark) {
-        if (list != null) {
-            for (Instruction end : list) {
-                BlockBegin b = end.block();
-                if (!mark.containsKey(b)) {
-                    queue.offer(b);
-                    mark.put(b, b);
-                }
-            }
-        }
-    }
-
-    /**
      * Gets the bytecode index of this instruction.
      * @return the bytecode index of this instruction
      */
@@ -298,7 +239,7 @@
      */
     public int numberOfPreds() {
         // ignore the graph root
-        if (predecessors().size() == 1 && predecessors().get(0) == graph().root()) {
+        if (predecessors().size() == 1 && predecessors().get(0) == graph().start()) {
             return 0;
         } else {
             return predecessors().size();
diff -r 114fc809462f -r 0fe79e7435c3 graal/GraalCompiler/src/com/sun/c1x/ir/Return.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Return.java	Fri May 20 12:08:58 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Return.java	Fri May 20 14:22:22 2011 +0200
@@ -34,7 +34,8 @@
     private static final int INPUT_COUNT = 1;
     private static final int INPUT_RESULT = 0;
 
-    private static final int SUCCESSOR_COUNT = 0;
+    private static final int SUCCESSOR_COUNT = 1;
+    private static final int SUCCESSOR_END = 0;
 
     @Override
     protected int inputCount() {
@@ -57,6 +58,11 @@
         return (Value) inputs().set(super.inputCount() + INPUT_RESULT, n);
     }
 
+    @Override
+    public Instruction next() {
+        return null;
+    }
+
     /**
      * Constructs a new Return instruction.
      * @param result the instruction producing the result for this return; {@code null} if this
@@ -67,6 +73,7 @@
     public Return(Value result, Graph graph) {
         super(result == null ? CiKind.Void : result.kind, null, 0, INPUT_COUNT, SUCCESSOR_COUNT, graph);
         setResult(result);
+        successors().set(SUCCESSOR_END, graph.end());
     }
 
     @Override
diff -r 114fc809462f -r 0fe79e7435c3 graal/GraalCompiler/src/com/sun/c1x/ir/Unwind.java
--- a/graal/GraalCompiler/src/com/sun/c1x/ir/Unwind.java	Fri May 20 12:08:58 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/ir/Unwind.java	Fri May 20 14:22:22 2011 +0200
@@ -34,7 +34,8 @@
     private static final int INPUT_COUNT = 1;
     private static final int INPUT_EXCEPTION = 0;
 
-    private static final int SUCCESSOR_COUNT = 0;
+    private static final int SUCCESSOR_COUNT = 1;
+    private static final int SUCCESSOR_END = 0;
 
     @Override
     protected int inputCount() {
@@ -46,6 +47,11 @@
         return super.successorCount() + SUCCESSOR_COUNT;
     }
 
+    @Override
+    public Instruction next() {
+        return null;
+    }
+
     /**
      * The instruction that produces the exception object.
      */
@@ -61,6 +67,7 @@
     public Unwind(Value exception, Graph graph) {
         super(CiKind.Object, null, 0, INPUT_COUNT, SUCCESSOR_COUNT, graph);
         setException(exception);
+        successors().set(SUCCESSOR_END, graph.end());
     }
 
     @Override
diff -r 114fc809462f -r 0fe79e7435c3 graal/GraalGraph/src/com/oracle/graal/graph/Graph.java
--- a/graal/GraalGraph/src/com/oracle/graal/graph/Graph.java	Fri May 20 12:08:58 2011 +0200
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/Graph.java	Fri May 20 14:22:22 2011 +0200
@@ -29,12 +29,14 @@
 public class Graph {
 
     private final ArrayList<Node> nodes;
-    private final Root root;
+    private final StartNode start;
+    private final EndNode end;
     int nextId;
 
     public Graph() {
         nodes = new ArrayList<Node>();
-        root = new Root(this);
+        start = new StartNode(this);
+        end = new EndNode(this);
     }
 
     public Collection<Node> getNodes() {
@@ -51,8 +53,12 @@
         nodes.set(node.id(), Node.Null);
     }
 
-    public Root root() {
-        return root;
+    public StartNode start() {
+        return start;
+    }
+
+    public EndNode end() {
+        return end;
     }
 
     public NodeBitMap createNodeBitMap() {
diff -r 114fc809462f -r 0fe79e7435c3 graal/GraalGraph/src/com/oracle/graal/graph/Node.java
--- a/graal/GraalGraph/src/com/oracle/graal/graph/Node.java	Fri May 20 12:08:58 2011 +0200
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/Node.java	Fri May 20 14:22:22 2011 +0200
@@ -27,7 +27,7 @@
 import java.util.Collections;
 import java.util.List;
 
-public abstract class Node implements Cloneable {
+public abstract class Node {
 
     public static final Node Null = null;
     public static final int DeletedID = -1;
diff -r 114fc809462f -r 0fe79e7435c3 graal/GraalGraph/src/com/oracle/graal/graph/NodeIterator.java
--- a/graal/GraalGraph/src/com/oracle/graal/graph/NodeIterator.java	Fri May 20 12:08:58 2011 +0200
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeIterator.java	Fri May 20 14:22:22 2011 +0200
@@ -27,14 +27,14 @@
 
 
 public class NodeIterator {
-    public static void doBFS(EdgeType e, Node start, NodeVisitor visitor) {
+    public static NodeBitMap iterate(EdgeType e, Node start, NodeVisitor visitor) {
         LinkedList<Node> nodes = new LinkedList<Node>();
         NodeBitMap nodeBitMap = start.graph.createNodeBitMap();
 
         add(nodes, nodeBitMap, start);
         while (nodes.size() > 0) {
             Node n = nodes.remove();
-            if (visitor.visit(n)) {
+            if (visitor == null || visitor.visit(n)) {
                 switch(e) {
                     case INPUTS:
                         for (Node inputs : n.inputs()) {
@@ -61,6 +61,8 @@
                 }
             }
         }
+
+        return nodeBitMap;
     }
 
     private static void add(List<Node> nodes, NodeBitMap nodeBitMap, Node node) {
diff -r 114fc809462f -r 0fe79e7435c3 graal/GraalGraph/src/com/oracle/graal/graph/NodeMap.java
--- a/graal/GraalGraph/src/com/oracle/graal/graph/NodeMap.java	Fri May 20 12:08:58 2011 +0200
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeMap.java	Fri May 20 14:22:22 2011 +0200
@@ -45,6 +45,10 @@
         values[node.id()] = value;
     }
 
+    public int size() {
+        return values.length;
+    }
+
     private void check(Node node) {
         assert node.graph == graph : "this node is not part of the graph";
         assert node.id() < values.length : "this node was added to the graph after creating the node map";
diff -r 114fc809462f -r 0fe79e7435c3 graal/GraalGraph/src/com/oracle/graal/graph/Root.java
--- a/graal/GraalGraph/src/com/oracle/graal/graph/Root.java	Fri May 20 12:08:58 2011 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,74 +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.graph;
-
-public class Root extends Node {
-
-    private static final int INPUT_COUNT = 0;
-
-    private static final int SUCCESSOR_COUNT = 1;
-    private static final int SUCCESSOR_START = 0;
-
-    @Override
-    protected int inputCount() {
-        return super.inputCount() + INPUT_COUNT;
-    }
-
-    @Override
-    protected int successorCount() {
-        return super.successorCount() + SUCCESSOR_COUNT;
-    }
-
-    public Node start() {
-        return (Node) successors().get(super.successorCount() + SUCCESSOR_START);
-    }
-
-    public Node setStart(Node next) {
-        return successors().set(super.successorCount() + SUCCESSOR_START, next);
-    }
-
-    Root(Graph graph) {
-        super(INPUT_COUNT, SUCCESSOR_COUNT, graph);
-    }
-
-    @Override
-    public void replace(Node other) {
-        throw new UnsupportedOperationException();
-    }
-
-    @Override
-    public void delete() {
-        throw new UnsupportedOperationException();
-    }
-
-    @Override
-    protected Object clone() throws CloneNotSupportedException {
-        throw new UnsupportedOperationException();
-    }
-
-    @Override
-    public Node copy(Graph into) {
-        throw new UnsupportedOperationException();
-    }
-
-}
diff -r 114fc809462f -r 0fe79e7435c3 graal/GraalGraph/src/com/oracle/graal/graph/StartNode.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/StartNode.java	Fri May 20 14:22:22 2011 +0200
@@ -0,0 +1,69 @@
+/*
+ * 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.graph;
+
+public class StartNode extends Node {
+
+    private static final int INPUT_COUNT = 0;
+
+    private static final int SUCCESSOR_COUNT = 1;
+    private static final int SUCCESSOR_START = 0;
+
+    @Override
+    protected int inputCount() {
+        return super.inputCount() + INPUT_COUNT;
+    }
+
+    @Override
+    protected int successorCount() {
+        return super.successorCount() + SUCCESSOR_COUNT;
+    }
+
+    public Node start() {
+        return (Node) successors().get(super.successorCount() + SUCCESSOR_START);
+    }
+
+    public Node setStart(Node next) {
+        return successors().set(super.successorCount() + SUCCESSOR_START, next);
+    }
+
+    StartNode(Graph graph) {
+        super(INPUT_COUNT, SUCCESSOR_COUNT, graph);
+    }
+
+    @Override
+    public void replace(Node other) {
+        throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public void delete() {
+        throw new UnsupportedOperationException();
+    }
+
+    @Override
+    public Node copy(Graph into) {
+        throw new UnsupportedOperationException();
+    }
+
+}