# HG changeset patch
# User Thomas Wuerthinger <thomas@wuerthinger.net>
# Date 1305901891 -7200
# Node ID 0c5791bc90fb70440b148bf75b45fb86e5219036
# Parent  152b98832b0ebb7f344cef01ea15325939568b3e
More on scheduling.

diff -r 152b98832b0e -r 0c5791bc90fb graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java
--- a/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java	Fri May 20 14:52:25 2011 +0200
+++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java	Fri May 20 16:31:31 2011 +0200
@@ -26,7 +26,6 @@
 
 import com.oracle.graal.graph.*;
 import com.sun.c1x.debug.*;
-import com.sun.c1x.ir.*;
 
 
 public class Schedule {
@@ -56,23 +55,26 @@
     }
 
     private void identifyBlocks() {
-        final NodeBitMap bottomUpBitMap = NodeIterator.iterate(EdgeType.PREDECESSORS, graph.end(), null);
-        NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start(), new NodeVisitor() {
+
+        // Identify nodes that form the control flow.
+        final NodeBitMap topDownBitMap = NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start(), null, null);
+        final NodeBitMap combinedBitMap = NodeIterator.iterate(EdgeType.PREDECESSORS, graph.end(), topDownBitMap, null);
+
+        // Identify blocks.
+        final ArrayList<Node> blockBeginNodes = new ArrayList<Node>();
+        NodeIterator.iterate(EdgeType.SUCCESSORS, graph.start(), combinedBitMap, new NodeVisitor() {
             @Override
-            public boolean visit(Node n) {
-                if (!bottomUpBitMap.isMarked(n)) {
-                    return false;
-                }
-
+            public void visit(Node n) {
                 Node singlePred = null;
                 for (Node pred : n.predecessors()) {
-                    if (pred != null && bottomUpBitMap.isMarked(pred)) {
+                    if (pred != null && combinedBitMap.isMarked(pred)) {
                         if (singlePred == null) {
                             singlePred = pred;
                         } else {
                             // We have more than one predecessor => we are a merge block.
                             assignBlock(n);
-                            return true;
+                            blockBeginNodes.add(n);
+                            return;
                         }
                     }
                 }
@@ -80,24 +82,34 @@
                 if (singlePred == null) {
                     // We have no predecessor => we are the start block.
                     assignBlock(n);
+                    blockBeginNodes.add(n);
                 } else {
                     // We have a single predecessor => its successor count.
                     int successorCount = 0;
                     for (Node succ : singlePred.successors()) {
-                        if (succ != null && bottomUpBitMap.isMarked(succ)) {
+                        if (succ != null && combinedBitMap.isMarked(succ)) {
                             successorCount++;
                             if (successorCount > 1) {
                                 // Our predecessor is a split => we need a new block.
                                 assignBlock(n);
-                                return true;
+                                blockBeginNodes.add(n);
+                                return;
                             }
                         }
                     }
                     nodeToBlock.set(n, nodeToBlock.get(singlePred));
                 }
-                return true;
             }}
         );
+
+        // Connect blocks.
+        for (Node n : blockBeginNodes) {
+            Block block = nodeToBlock.get(n);
+            for (Node pred : n.predecessors()) {
+                Block predBlock = nodeToBlock.get(pred);
+                predBlock.addSuccessor(block);
+            }
+        }
     }
 
     private void print() {
diff -r 152b98832b0e -r 0c5791bc90fb graal/GraalCompiler/src/com/sun/c1x/gen/PhiSimplifier.java
--- a/graal/GraalCompiler/src/com/sun/c1x/gen/PhiSimplifier.java	Fri May 20 14:52:25 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/gen/PhiSimplifier.java	Fri May 20 16:31:31 2011 +0200
@@ -25,45 +25,21 @@
 import com.oracle.graal.graph.*;
 import com.sun.c1x.graph.*;
 import com.sun.c1x.ir.*;
-import com.sun.c1x.value.*;
 
 /**
  * The {@code PhiSimplifier} class is a helper class that can reduce phi instructions.
- *
- * @author Ben L. Titzer
  */
-public final class PhiSimplifier implements BlockClosure {
-
-    final IR ir;
+public final class PhiSimplifier {
 
     public PhiSimplifier(IR ir) {
-        this.ir = ir;
-        //ir.getHIRStartBlock().iterateAnyOrder(this, false);
-
         for (Node n : ir.compilation.graph.getNodes()) {
             if (n instanceof Phi) {
-                simplify((Phi)n);
+                simplify((Phi) n);
             }
         }
-
-
-    }
-
-    /**
-     * This method is called for each block and processes any phi statements in the block.
-     * @param block the block to apply the simplification to
-     */
-    public void apply(BlockBegin block) {
-        FrameState state = block.stateBefore();
-        for (int i = 0; i < state.stackSize(); i++) {
-            simplify(state.stackAt(i));
-        }
-        for (int i = 0; i < state.localsSize(); i++) {
-            simplify(state.localAt(i));
-        }
     }
 
-    Value simplify(Value x) {
+    private Value simplify(Value x) {
         if (x == null || !(x instanceof Phi)) {
             return x;
         }
diff -r 152b98832b0e -r 0c5791bc90fb graal/GraalGraph/src/com/oracle/graal/graph/Node.java
--- a/graal/GraalGraph/src/com/oracle/graal/graph/Node.java	Fri May 20 14:52:25 2011 +0200
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/Node.java	Fri May 20 16:31:31 2011 +0200
@@ -53,8 +53,8 @@
         return Collections.unmodifiableList(predecessors);
     }
 
-    public Collection<Node> usages() {
-        return Collections.unmodifiableCollection(usages);
+    public List<Node> usages() {
+        return Collections.unmodifiableList(usages);
     }
 
     public NodeArray inputs() {
diff -r 152b98832b0e -r 0c5791bc90fb graal/GraalGraph/src/com/oracle/graal/graph/NodeBitMap.java
--- a/graal/GraalGraph/src/com/oracle/graal/graph/NodeBitMap.java	Fri May 20 14:52:25 2011 +0200
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeBitMap.java	Fri May 20 16:31:31 2011 +0200
@@ -35,6 +35,14 @@
         bitMap = new CiBitMap(graph.nextId);
     }
 
+    public boolean setIntersect(NodeBitMap other) {
+        return bitMap.setIntersect(other.bitMap);
+    }
+
+    public void setUnion(NodeBitMap other) {
+        bitMap.setUnion(other.bitMap);
+    }
+
     public boolean isMarked(Node node) {
         check(node);
         return bitMap.get(node.id());
@@ -49,4 +57,9 @@
         assert node.graph == graph : "this node is not part of the graph";
         assert node.id() < bitMap.size() : "this node (" + node.id() + ") was added to the graph after creating the node bitmap (" + bitMap.length() + ")";
     }
+
+    @Override
+    public String toString() {
+        return bitMap.toBinaryString(-1);
+    }
 }
diff -r 152b98832b0e -r 0c5791bc90fb graal/GraalGraph/src/com/oracle/graal/graph/NodeIterator.java
--- a/graal/GraalGraph/src/com/oracle/graal/graph/NodeIterator.java	Fri May 20 14:52:25 2011 +0200
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeIterator.java	Fri May 20 16:31:31 2011 +0200
@@ -27,46 +27,47 @@
 
 
 public class NodeIterator {
-    public static NodeBitMap iterate(EdgeType e, Node start, NodeVisitor visitor) {
+    public static NodeBitMap iterate(EdgeType e, Node start, NodeBitMap constraint, NodeVisitor visitor) {
         LinkedList<Node> nodes = new LinkedList<Node>();
         NodeBitMap nodeBitMap = start.graph.createNodeBitMap();
 
-        add(nodes, nodeBitMap, start);
+        add(nodes, nodeBitMap, start, constraint, null);
         while (nodes.size() > 0) {
             Node n = nodes.remove();
-            if (visitor == null || visitor.visit(n)) {
-                switch(e) {
-                    case INPUTS:
-                        for (Node inputs : n.inputs()) {
-                            add(nodes, nodeBitMap, inputs);
-                        }
-                        break;
-                    case USAGES:
-                        for (Node usage : n.usages()) {
-                            add(nodes, nodeBitMap, usage);
-                        }
-                        break;
-                    case PREDECESSORS:
-                        for (Node preds : n.predecessors()) {
-                            add(nodes, nodeBitMap, preds);
-                        }
-                        break;
-                    case SUCCESSORS:
-                        for (Node succ : n.successors()) {
-                            add(nodes, nodeBitMap, succ);
-                        }
-                        break;
-                    default:
-                        assert false : "unknown edge type";
-                }
+            if (visitor != null) {
+                visitor.visit(n);
+            }
+            switch(e) {
+                case INPUTS:
+                    for (Node inputs : n.inputs()) {
+                        add(nodes, nodeBitMap, inputs, constraint, n.usages());
+                    }
+                    break;
+                case USAGES:
+                    for (Node usage : n.usages()) {
+                        add(nodes, nodeBitMap, usage, constraint, n.inputs());
+                    }
+                    break;
+                case PREDECESSORS:
+                    for (Node preds : n.predecessors()) {
+                        add(nodes, nodeBitMap, preds, constraint, n.successors());
+                    }
+                    break;
+                case SUCCESSORS:
+                    for (Node succ : n.successors()) {
+                        add(nodes, nodeBitMap, succ, constraint, n.predecessors());
+                    }
+                    break;
+                default:
+                    assert false : "unknown edge type";
             }
         }
 
         return nodeBitMap;
     }
 
-    private static void add(List<Node> nodes, NodeBitMap nodeBitMap, Node node) {
-        if (node != null && !nodeBitMap.isMarked(node)) {
+    private static void add(List<Node> nodes, NodeBitMap nodeBitMap, Node node, NodeBitMap constraint, List<Node> others) {
+        if (node != null && !nodeBitMap.isMarked(node) && (constraint == null || constraint.isMarked(node))) {
             nodes.add(node);
             nodeBitMap.mark(node);
         }
diff -r 152b98832b0e -r 0c5791bc90fb graal/GraalGraph/src/com/oracle/graal/graph/NodeVisitor.java
--- a/graal/GraalGraph/src/com/oracle/graal/graph/NodeVisitor.java	Fri May 20 14:52:25 2011 +0200
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeVisitor.java	Fri May 20 16:31:31 2011 +0200
@@ -24,5 +24,5 @@
 
 
 public interface NodeVisitor {
-    boolean visit(Node n);
+    void visit(Node n);
 }