# HG changeset patch
# User Thomas Wuerthinger <thomas@wuerthinger.net>
# Date 1305886119 -7200
# Node ID 45a58c9536debf1369dec23cd583b3f82351667d
# Parent  49a8790b85a22618a832575c5d5ae043d99473dd
Added BFS node iteration. Started drafting scheduling.

diff -r 49a8790b85a2 -r 45a58c9536de graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Block.java	Fri May 20 12:08:39 2011 +0200
@@ -0,0 +1,45 @@
+/*
+ * Copyright (c) 2011, 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.schedule;
+
+import java.util.*;
+
+
+public class Block {
+
+    private final List<Block> successors = new ArrayList<Block>();
+    private final List<Block> predecessors = new ArrayList<Block>();
+
+    public List<Block> getSuccessors() {
+        return Collections.unmodifiableList(successors);
+    }
+
+    public List<Block> getPredecessors() {
+        return Collections.unmodifiableList(predecessors);
+    }
+
+    public void addSuccessor(Block other) {
+        successors.add(other);
+        other.predecessors.add(this);
+    }
+}
diff -r 49a8790b85a2 -r 45a58c9536de graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/GraalCompiler/src/com/oracle/max/graal/schedule/Schedule.java	Fri May 20 12:08:39 2011 +0200
@@ -0,0 +1,49 @@
+/*
+ * Copyright (c) 2011, 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.schedule;
+
+import java.util.*;
+
+import com.oracle.graal.graph.*;
+
+
+public class Schedule {
+    private final List<Block> blocks = new ArrayList<Block>();
+    private final NodeMap<Block> nodeToBlock;
+    private final Graph graph;
+
+    public Schedule(Graph graph) {
+        this.graph = graph;
+        nodeToBlock = graph.createNodeMap();
+        identifyBlocks();
+    }
+
+    private void identifyBlocks() {
+        NodeIterator.doBFS(EdgeType.SUCCESSORS, graph.root(), new NodeVisitor() {
+            @Override
+            public boolean visit(Node n) {
+                return true;
+            }
+        });
+    }
+}
diff -r 49a8790b85a2 -r 45a58c9536de graal/GraalCompiler/src/com/sun/c1x/graph/IR.java
--- a/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java	Fri May 20 11:29:55 2011 +0200
+++ b/graal/GraalCompiler/src/com/sun/c1x/graph/IR.java	Fri May 20 12:08:39 2011 +0200
@@ -24,6 +24,7 @@
 
 import java.util.*;
 
+import com.oracle.max.graal.schedule.*;
 import com.sun.c1x.*;
 import com.sun.c1x.debug.*;
 import com.sun.c1x.ir.*;
@@ -80,6 +81,8 @@
             C1XTimers.HIR_OPTIMIZE.start();
         }
 
+        Schedule schedule = new Schedule(this.compilation.graph);
+
         computeLinearScanOrder();
 
         if (C1XOptions.PrintTimers) {
diff -r 49a8790b85a2 -r 45a58c9536de graal/GraalGraph/src/com/oracle/graal/graph/EdgeType.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/EdgeType.java	Fri May 20 12:08:39 2011 +0200
@@ -0,0 +1,31 @@
+/*
+ * 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 enum EdgeType {
+    INPUTS,
+    USAGES,
+    PREDECESSORS,
+    SUCCESSORS;
+}
diff -r 49a8790b85a2 -r 45a58c9536de graal/GraalGraph/src/com/oracle/graal/graph/Graph.java
--- a/graal/GraalGraph/src/com/oracle/graal/graph/Graph.java	Fri May 20 11:29:55 2011 +0200
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/Graph.java	Fri May 20 12:08:39 2011 +0200
@@ -26,13 +26,11 @@
 import java.util.Collection;
 import java.util.Collections;
 
-import com.sun.cri.ci.CiBitMap;
-
 public class Graph {
 
     private final ArrayList<Node> nodes;
     private final Root root;
-    private int nextId;
+    int nextId;
 
     public Graph() {
         nodes = new ArrayList<Node>();
@@ -58,57 +56,10 @@
     }
 
     public NodeBitMap createNodeBitMap() {
-        return new NodeBitMap();
+        return new NodeBitMap(this);
     }
 
     public <T> NodeMap<T> createNodeMap() {
-        return new NodeMap<T>();
-    }
-
-    public final class NodeBitMap {
-
-        private final CiBitMap bitMap = new CiBitMap(nextId);
-
-        private NodeBitMap() {
-        }
-
-        public boolean isMarked(Node node) {
-            check(node);
-            return bitMap.get(node.id());
-        }
-
-        public void mark(Node node) {
-            check(node);
-            bitMap.set(node.id());
-        }
-
-        private void check(Node node) {
-            assert node.graph == Graph.this : "this node is not part of the graph";
-            assert node.id() < bitMap.length() : "this node was added to the graph after creating the node bitmap";
-        }
-    }
-
-    public final class NodeMap<T> {
-
-        private final Object[] values = new Object[nextId];
-
-        private NodeMap() {
-        }
-
-        @SuppressWarnings("unchecked")
-        public T get(Node node) {
-            check(node);
-            return (T) values[node.id()];
-        }
-
-        public void set(Node node, T value) {
-            check(node);
-            values[node.id()] = value;
-        }
-
-        private void check(Node node) {
-            assert node.graph == Graph.this : "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";
-        }
+        return new NodeMap<T>(this);
     }
 }
diff -r 49a8790b85a2 -r 45a58c9536de graal/GraalGraph/src/com/oracle/graal/graph/NodeBitMap.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeBitMap.java	Fri May 20 12:08:39 2011 +0200
@@ -0,0 +1,52 @@
+/*
+ * Copyright (c) 2011, 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;
+
+import com.sun.cri.ci.CiBitMap;
+
+
+public final class NodeBitMap {
+
+    private final CiBitMap bitMap;
+    private final Graph graph;
+
+    NodeBitMap(Graph graph) {
+        this.graph = graph;
+        bitMap = new CiBitMap(graph.nextId);
+    }
+
+    public boolean isMarked(Node node) {
+        check(node);
+        return bitMap.get(node.id());
+    }
+
+    public void mark(Node node) {
+        check(node);
+        bitMap.set(node.id());
+    }
+
+    private void check(Node node) {
+        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() + ")";
+    }
+}
diff -r 49a8790b85a2 -r 45a58c9536de graal/GraalGraph/src/com/oracle/graal/graph/NodeIterator.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeIterator.java	Fri May 20 12:08:39 2011 +0200
@@ -0,0 +1,72 @@
+/*
+ * Copyright (c) 2011, 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;
+
+import java.util.LinkedList;
+import java.util.List;
+
+
+public class NodeIterator {
+    public static void doBFS(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)) {
+                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";
+                }
+            }
+        }
+    }
+
+    private static void add(List<Node> nodes, NodeBitMap nodeBitMap, Node node) {
+        if (node != null && !nodeBitMap.isMarked(node)) {
+            nodes.add(node);
+            nodeBitMap.mark(node);
+        }
+    }
+}
diff -r 49a8790b85a2 -r 45a58c9536de graal/GraalGraph/src/com/oracle/graal/graph/NodeMap.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeMap.java	Fri May 20 12:08:39 2011 +0200
@@ -0,0 +1,52 @@
+/*
+ * Copyright (c) 2011, 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 final class NodeMap<T> {
+
+    private final Object[] values;
+    private final Graph graph;
+
+    NodeMap(Graph graph) {
+        this.graph = graph;
+        values = new Object[graph.nextId];
+    }
+
+    @SuppressWarnings("unchecked")
+    public T get(Node node) {
+        check(node);
+        return (T) values[node.id()];
+    }
+
+    public void set(Node node, T value) {
+        check(node);
+        values[node.id()] = value;
+    }
+
+    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 49a8790b85a2 -r 45a58c9536de graal/GraalGraph/src/com/oracle/graal/graph/NodeVisitor.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/NodeVisitor.java	Fri May 20 12:08:39 2011 +0200
@@ -0,0 +1,28 @@
+/*
+ * Copyright (c) 2011, 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 interface NodeVisitor {
+    boolean visit(Node n);
+}