--- a/graal/GraalGraph/src/com/oracle/graal/graph/Graph.java	Thu Apr 28 14:35:35 2011 +0200
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/Graph.java	Thu Apr 28 18:30:55 2011 +0200
@@ -35,20 +35,17 @@
         nodes = new ArrayList<Node>();
     }
 
-    public synchronized int nextId(Node node) {
+    public Collection<Node> getNodes() {
+        return Collections.unmodifiableCollection(nodes);
+    }
+
+    int register(Node node) {
         int id = nextId++;
         nodes.add(id, node);
         return id;
     }
 
-    public Collection<Node> getNodes() {
-        return Collections.unmodifiableCollection(nodes);
-    }
-
-    public Node local(Node node) {
-        if (node.graph() == this) {
-            return node;
-        }
-        return node.cloneNode(this);
+    void unregister(Node node) {
+        nodes.set(node.id(), Node.Null);
     }
 }

--- a/graal/GraalGraph/src/com/oracle/graal/graph/Node.java	Thu Apr 28 14:35:35 2011 +0200
+++ b/graal/GraalGraph/src/com/oracle/graal/graph/Node.java	Thu Apr 28 18:30:55 2011 +0200
@@ -22,119 +22,48 @@
  */
 package com.oracle.graal.graph;
 
+import java.util.AbstractList;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collection;
 import java.util.Collections;
 import java.util.Iterator;
 
-public abstract class Node {
+public abstract class Node implements Cloneable {
+
+    public static final Node Null = null;
+    public static final int DeletedID = -1;
 
     private final Graph graph;
-    private final int id;
+    private int id;
     private final NodeArray inputs;
     private final NodeArray successors;
     private final ArrayList<Node> usages;
     private final ArrayList<Node> predecessors;
 
-    public Node(Node[] inputs, Node[] successors, Graph graph) {
+    public Node(int inputCount, int successorCount, Graph graph) {
+        assert graph != null;
         this.graph = graph;
-        if (graph != null) {
-            this.id = graph.nextId(this); // this pointer escaping in a constructor..
-        } else {
-            this.id = -1;
-        }
-        this.inputs = new NodeArray(inputs);
-        this.successors = new NodeArray(successors);
+        this.id = graph.register(this);
+        this.inputs = new NodeArray(inputCount);
+        this.successors = new NodeArray(successorCount);
         this.predecessors = new ArrayList<Node>();
         this.usages = new ArrayList<Node>();
-        for (Node input : inputs) {
-            input.usages.add(this);
-        }
-        for (Node successor : successors) {
-            successor.predecessors.add(this);
-        }
-    }
-
-    public Node(int inputs, int successors, Graph graph) {
-        this(nullNodes(inputs, graph), nullNodes(successors, graph), graph);
     }
 
-    public class NodeArray implements Iterable<Node> {
-
-        private final Node[] nodes;
-
-        public NodeArray(Node[] nodes) {
-            this.nodes = nodes;
-        }
-
-        @Override
-        public Iterator<Node> iterator() {
-            return Arrays.asList(this.nodes).iterator();
-        }
-
-        public Node set(int index, Node node) {
-            if (node.graph != Node.this.graph) {
-                // fail
-                System.err.println("node.graph != Node.this.graph");
-            }
-            Node old = nodes[index];
-            nodes[index] = node;
-            if (Node.this.inputs == this) { // :-/
-                old.usages.remove(Node.this);
-                node.usages.add(Node.this);
-            } else {
-                assert Node.this.successors == this;
-                old.predecessors.remove(Node.this);
-                node.predecessors.add(Node.this);
-            }
-
-            return old;
-        }
-
-        public boolean contains(Node n) {
-            for (int i = 0; i < nodes.length; i++) {
-                if (nodes[i] == n) { // equals?
-                    return true;
-                }
-            }
-            return false;
-        }
-
-        public boolean replace(Node toReplace, Node replacement) {
-            for (int i = 0; i < nodes.length; i++) {
-                if (nodes[i] == toReplace) { // equals?
-                    this.set(i, replacement);
-                    return true; // replace only one occurrence
-                }
-            }
-            return false;
-        }
-
-        public Node[] asArray() {
-            Node[] copy = new Node[nodes.length];
-            System.arraycopy(nodes, 0, copy, 0, nodes.length);
-            return copy;
-        }
-
-        public int size() {
-            return nodes.length;
-        }
-    }
-
-    public Collection<Node> getPredecessors() {
+    public Collection<Node> predecessors() {
         return Collections.unmodifiableCollection(predecessors);
     }
 
-    public Collection<Node> getUsages() {
+    public Collection<Node> usages() {
         return Collections.unmodifiableCollection(usages);
     }
 
-    public NodeArray getInputs() {
+    public NodeArray inputs() {
         return inputs;
     }
 
-    public NodeArray getSuccessors() {
+    public NodeArray successors() {
         return successors;
     }
 
@@ -147,50 +76,128 @@
     }
 
     public void replace(Node other) {
-        if (other.graph != this.graph) {
-            other = other.cloneNode(this.graph);
-        }
-        Node[] myInputs = inputs.nodes;
-        for (int i = 0; i < myInputs.length; i++) {
-            other.inputs.set(i, myInputs[i]);
-        }
-        while (!usages.isEmpty()) {
-            Node usage = usages.get(0);
-            usage.inputs.replace(this, other);
-        }
-
-        Node[] mySuccessors = successors.nodes;
-        for (int i = 0; i < mySuccessors.length; i++) {
-            other.successors.set(i, mySuccessors[i]);
+        assert !isDeleted() && !other.isDeleted();
+        assert other.graph == graph;
+        for (Node usage : usages) {
+            usage.inputs.replaceFirstOccurrence(this, other);
         }
         for (Node predecessor : predecessors) {
-            predecessor.successors.replace(this, other);
+            predecessor.successors.replaceFirstOccurrence(this, other);
+        }
+        other.usages.addAll(usages);
+        other.predecessors.addAll(predecessors);
+        usages.clear();
+        predecessors.clear();
+        delete();
+    }
+
+    public boolean isDeleted() {
+        return id == DeletedID;
+    }
+
+    public void delete() {
+        assert !isDeleted();
+        for (int i = 0; i < inputs.size(); ++i) {
+            inputs.set(i, Null);
+        }
+        for (int i = 0; i < successors.size(); ++i) {
+            successors.set(i, Null);
         }
+        graph.unregister(this);
+        id = DeletedID;
+        assert isDeleted();
+    }
+
+    public Node copy() {
+        return copy(graph);
+    }
+
+    /**
+     * 
+     * @param into
+     * @return
+     */
+    public abstract Node copy(Graph into);
+
+    /**
+     * 
+     * @return
+     */
+    protected int inputCount() {
+        return 0;
+    }
+
+    /**
+     * 
+     * @return
+     */
+    protected int successorCount() {
+        return 0;
     }
 
-    protected Node setInput(int index, Node in) {
-        return this.getInputs().set(index, in);
-    }
+    public class NodeArray extends AbstractList<Node> {
+
+        private final Node[] nodes;
+
+        public NodeArray(int length) {
+            this.nodes = new Node[length];
+        }
 
-    protected Node setSuccessor(int index, Node sux) {
-        return this.getSuccessors().set(index, sux);
-    }
+        public Iterator<Node> iterator() {
+            return Arrays.asList(this.nodes).iterator();
+        }
 
-    public abstract Node cloneNode(Graph into);
+        private Node self() {
+            return Node.this;
+        }
+
+        public Node set(int index, Node node) {
+            assert node.graph == self().graph;
+            Node old = nodes[index];
 
-    protected Node getInput(int index) {
-        return this.inputs.nodes[index];
-    }
+            if (old != node) {
+                nodes[index] = node;
+                if (Node.this.inputs == this) {
+                    if (old != null) {
+                        old.usages.remove(self());
+                    }
+                    if (node != null) {
+                        node.usages.add(self());
+                    }
+                } else {
+                    assert Node.this.successors == this;
+                    if (old != null) {
+                        old.predecessors.remove(self());
+                    }
+                    if (node != null) {
+                        node.predecessors.add(self());
+                    }
+                }
+            }
 
-    protected Node getSuccessor(int index) {
-        return this.successors.nodes[index];
-    }
+            return old;
+        }
+
+        public Node get(int index) {
+            return nodes[index];
+        }
+
+        public Node[] toArray() {
+            return Arrays.copyOf(nodes, nodes.length);
+        }
 
-    private static Node[] nullNodes(int number, Graph graph) {
-        Node[] nodes = new Node[number];
-        for (int i = 0; i < number; i++) {
-            nodes[i] = new NullNode(0, 0, graph);
+        private boolean replaceFirstOccurrence(Node toReplace, Node replacement) {
+            for (int i = 0; i < nodes.length; i++) {
+                if (nodes[i] == toReplace) {
+                    nodes[i] = replacement;
+                    return true;
+                }
+            }
+            return false;
         }
-        return nodes;
+
+        public int size() {
+            return nodes.length;
+        }
     }
 }

--- a/graal/GraalGraph/src/com/oracle/graal/graph/NullNode.java	Thu Apr 28 14:35:35 2011 +0200
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,39 +0,0 @@
-/*
- * 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 class NullNode extends Node {
-
-    public NullNode(int inputs, int successors, Graph graph) {
-        super(inputs, successors, graph);
-    }
-
-    public NullNode(Graph graph) {
-        super(0, 0, graph);
-    }
-
-    @Override
-    public NullNode cloneNode(Graph into) {
-        return new NullNode(0, 0, into);
-    }
-}

--- a/graal/GraalGraph/test/com/oracle/graal/graph/NodeTest.java	Thu Apr 28 14:35:35 2011 +0200
+++ b/graal/GraalGraph/test/com/oracle/graal/graph/NodeTest.java	Thu Apr 28 18:30:55 2011 +0200
@@ -30,95 +30,112 @@
 
     @Test
     public void testBasics() {
-        DummyNode n1 = new DummyNode(2, 1, null);
 
         Graph g1 = new Graph();
 
+        DummyNode n1 = new DummyNode(2, 1, g1);
         DummyNode n2 = new DummyNode(1, 1, g1);
-        NullNode null1 = new NullNode(g1);
         DummyNode n3 = new DummyNode(0, 0, g1);
-        n2.dummySetInput(0, null1);
+        n2.dummySetInput(0, Node.Null);
         n2.dummySetSuccessor(0, n3);
 
-        assertSame(null1, n2.getInput(0));
-        assertSame(n3, n2.getSuccessor(0));
-
-        for (Node in : n1.getInputs()) {
-            assertNotNull(in);
-        }
-        for (Node sux : n1.getSuccessors()) {
-            assertNotNull(sux);
-        }
-        assertEquals(n1.getInputs().size(), 2);
-        assertEquals(n1.getSuccessors().size(), 1);
+        assertSame(Node.Null, n2.inputs().get(0));
+        assertSame(n3, n2.successors().get(0));
+        assertEquals(n1.inputs().size(), 2);
+        assertEquals(n1.successors().size(), 1);
     }
 
     @Test
     public void testReplace() {
         Graph g2 = new Graph();
 
-        NullNode null2 = new NullNode(g2);
-        NullNode null3 = new NullNode(g2);
-        NullNode null4 = new NullNode(g2);
-        NullNode null5 = new NullNode(g2);
-
-        DummyOp2 o1 = new DummyOp2(null2, null3, g2);
-        DummyOp2 o2 = new DummyOp2(o1, null4, g2);
-        DummyOp2 o3 = new DummyOp2(o2, null4, g2);
-        DummyOp2 o4 = new DummyOp2(null5, null5, g2);
+        DummyOp2 o1 = new DummyOp2(Node.Null, Node.Null, g2);
+        DummyOp2 o2 = new DummyOp2(o1, Node.Null, g2);
+        DummyOp2 o3 = new DummyOp2(o2, Node.Null, g2);
+        DummyOp2 o4 = new DummyOp2(Node.Null, Node.Null, g2);
 
         o2.replace(o4);
 
-        assertTrue(o1.getUsages().contains(o4));
-        assertTrue(null4.getUsages().contains(o4));
-        assertFalse(o3.getInputs().contains(o2));
-        assertTrue(o3.getInputs().contains(o4));
+        assertFalse(o3.inputs().contains(o2));
+        assertTrue(o3.inputs().contains(o4));
     }
 
     private static class DummyNode extends Node {
 
-        public DummyNode(int inputs, int successors, Graph graph) {
-            super(inputs, successors, graph);
+        private final int inputCount;
+        private final int successorCount;
+
+        public DummyNode(int inputCount, int successorCount, Graph graph) {
+            super(inputCount, successorCount, graph);
+            this.inputCount = inputCount;
+            this.successorCount = successorCount;
         }
 
-        public DummyNode(Node[] inputs, Node[] successors, Graph graph) {
-            super(inputs, successors, graph);
+        @Override
+        protected int inputCount() {
+            return super.inputCount() + inputCount;
+        }
+
+        @Override
+        protected int successorCount() {
+            return super.inputCount() + successorCount;
         }
 
         public void dummySetInput(int idx, Node n) {
-            this.setInput(idx, n);
+            inputs().set(idx, n);
         }
 
         public void dummySetSuccessor(int idx, Node n) {
-            this.setSuccessor(idx, n);
+            successors().set(idx, n);
         }
 
         @Override
-        public Node cloneNode(Graph into) {
-            return new DummyNode(this.getInputs().asArray(), this.getSuccessors().asArray(), into);
+        public Node copy(Graph into) {
+            return new DummyNode(inputCount, successorCount, into);
         }
 
     }
 
-    private static class DummyOp2 extends Node {
+    public static class DummyOp2 extends Node {
+
+        public static final int SUCCESSOR_COUNT = 0;
+        public static final int INPUT_COUNT = 2;
+        public static final int INPUT_X = 0;
+        public static final int INPUT_Y = 1;
 
         public DummyOp2(Node x, Node y, Graph graph) {
-            super(new Node[] {x, y}, new Node[] {}, graph);
+            this(graph);
+            setX(x);
+            setY(y);
+        }
+        public DummyOp2(Graph graph) {
+            super(INPUT_COUNT, SUCCESSOR_COUNT, graph);
+        }
+
+        @Override
+        protected int inputCount() {
+            return super.inputCount() + INPUT_COUNT;
         }
 
         public Node x() {
-            return this.getInput(0);
+            return inputs().get(super.inputCount() + INPUT_X);
         }
 
         public Node y() {
-            return this.getInput(1);
+            return inputs().get(super.inputCount() + INPUT_Y);
+        }
+
+        public Node setX(Node n) {
+            return inputs().set(super.inputCount() + INPUT_X, n);
+        }
+
+        public Node setY(Node n) {
+            return inputs().set(super.inputCount() + INPUT_Y, n);
         }
 
         @Override
-        public Node cloneNode(Graph into) {
-            return new DummyOp2(x(), y(), into); // this may create a Node which has inputs which do not belong to its
-                                                 // graph
+        public Node copy(Graph into) {
+            return new DummyOp2(into);
         }
-
     }
 }