--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Negate.java	Thu Jun 09 11:30:58 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/ir/Negate.java	Thu Jun 09 14:20:39 2011 +0200
@@ -23,6 +23,7 @@
 package com.oracle.max.graal.compiler.ir;
 
 import com.oracle.max.graal.compiler.debug.*;
+import com.oracle.max.graal.compiler.phases.CanonicalizerPhase.*;
 import com.oracle.max.graal.compiler.util.*;
 import com.oracle.max.graal.graph.*;
 import com.sun.cri.bytecode.*;
@@ -32,6 +33,7 @@
  * The {@code NegateOp} instruction negates its operand.
  */
 public final class Negate extends FloatingNode {
+    private static final NegateCanonicalizerOp CANONICALIZER = new NegateCanonicalizerOp();
 
     private static final int INPUT_COUNT = 2;
     private static final int INPUT_X = 0;
@@ -103,4 +105,31 @@
         Negate x = new Negate(kind, into);
         return x;
     }
+
+    @SuppressWarnings("unchecked")
+    @Override
+    public <T extends Op> T lookup(Class<T> clazz) {
+        if (clazz == CanonicalizerOp.class) {
+            return (T) CANONICALIZER;
+        }
+        return super.lookup(clazz);
+    }
+
+    private static class NegateCanonicalizerOp implements CanonicalizerOp {
+        @Override
+        public Node canonical(Node node) {
+            Negate negate = (Negate) node;
+            Value x = negate.x();
+            Graph graph = negate.graph();
+            if (x.isConstant()) {
+                switch (x.kind) {
+                    case Int: return Constant.forInt(-x.asConstant().asInt(), graph);
+                    case Long: return Constant.forLong(-x.asConstant().asLong(), graph);
+                    case Float: return Constant.forFloat(-x.asConstant().asFloat(), graph);
+                    case Double: return Constant.forDouble(-x.asConstant().asDouble(), graph);
+                }
+            }
+            return negate;
+        }
+    }
 }

--- a/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java	Thu Jun 09 11:30:58 2011 +0200
+++ b/graal/com.oracle.max.graal.compiler/src/com/oracle/max/graal/compiler/phases/CanonicalizerPhase.java	Thu Jun 09 14:20:39 2011 +0200
@@ -22,46 +22,25 @@
  */
 package com.oracle.max.graal.compiler.phases;
 
-import java.util.*;
-
 import com.oracle.max.graal.compiler.*;
 import com.oracle.max.graal.graph.*;
 
 public class CanonicalizerPhase extends Phase {
-
+    private static final int MAX_ITERATION_PER_NODE = 10;
 
     @Override
     protected void run(Graph graph) {
-        NodeBitMap visited = graph.createNodeBitMap();
-        List<Node> nodes = new ArrayList<Node>(graph.getNodes());
-        for (Node n : nodes) {
-            if (n == null) {
-                continue;
-            }
-            if (!n.isDeleted() && !visited.isMarked(n)) {
-                this.canonicalize(n, visited);
-            }
-        }
-    }
-
-    private void canonicalize(Node n, NodeBitMap visited) {
-        visited.mark(n);
-        for (Node input : n.inputs()) {
-            if (input == null) {
-                continue;
-            }
-            if (!visited.isNew(input) && !visited.isMarked(input)) {
-                canonicalize(input, visited);
-            }
-        }
-
-        CanonicalizerOp op = n.lookup(CanonicalizerOp.class);
-        if (op != null) {
-            Node canonical = op.canonical(n);
-            if (canonical != n) {
-                n.replace(canonical);
-                //System.out.println("-->" + n + " canonicalized to " + canonical);
-                GraalMetrics.NodesCanonicalized++;
+        NodeWorkList nodeWorkList = graph.createNodeWorkList(true, MAX_ITERATION_PER_NODE);
+        for (Node node : nodeWorkList) {
+            CanonicalizerOp op = node.lookup(CanonicalizerOp.class);
+            if (op != null) {
+                Node canonical = op.canonical(node);
+                if (canonical != node) {
+                    node.replace(canonical);
+                    nodeWorkList.replaced(canonical, node, EdgeType.USAGES);
+                    //System.out.println("-->" + n + " canonicalized to " + canonical);
+                    GraalMetrics.NodesCanonicalized++;
+                }
             }
         }
     }

--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java	Thu Jun 09 11:30:58 2011 +0200
+++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/Graph.java	Thu Jun 09 14:20:39 2011 +0200
@@ -84,10 +84,12 @@
             } while (nextNode == null || !type.isInstance(nextNode));
         }
 
+        @Override
         public boolean hasNext() {
             return nextNode != null;
         }
 
+        @Override
         @SuppressWarnings("unchecked")
         public T next() {
             try {
@@ -97,6 +99,7 @@
             }
         }
 
+        @Override
         public void remove() {
             throw new UnsupportedOperationException();
         }
@@ -104,6 +107,7 @@
 
     public <T extends Node> Iterable<T> getNodes(final Class<T> type) {
         return new Iterable<T>() {
+            @Override
             public Iterator<T> iterator() {
                 return new TypedNodeIterator<T>(type, nodes.iterator());
             }
@@ -137,6 +141,14 @@
         return new NodeFlood(this);
     }
 
+    public NodeWorkList createNodeWorkList() {
+        return new NodeWorkList(this);
+    }
+
+    public NodeWorkList createNodeWorkList(boolean fill, int iterationLimitPerNode) {
+        return new NodeWorkList(this, fill, iterationLimitPerNode);
+    }
+
     public Map<Node, Node> addDuplicate(Collection<Node> nodes, Map<Node, Node> replacements) {
         Map<Node, Node> newNodes = new HashMap<Node, Node>();
         // create node duplicates

--- a/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeBitMap.java	Thu Jun 09 11:30:58 2011 +0200
+++ b/graal/com.oracle.max.graal.graph/src/com/oracle/max/graal/graph/NodeBitMap.java	Thu Jun 09 14:20:39 2011 +0200
@@ -66,6 +66,10 @@
         bitMap.clear(node.id());
     }
 
+    public void grow(Node node) {
+        bitMap.grow(node.id() + 1);
+    }
+
     private void check(Node node) {
         assert node.graph == graph : "this node is not part of the graph";
         assert !isNew(node) : "this node (" + node.id() + ") was added to the graph after creating the node bitmap (" + bitMap.length() + ")";