--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Wed Sep 04 10:47:37 2013 -0400
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Thu Sep 05 00:44:36 2013 +0200
@@ -45,6 +45,11 @@
      */
     private int[] nodeModCounts;
 
+    /**
+     * Records the modification count for nodes' usage lists. This is only used in assertions.
+     */
+    private int[] nodeUsageModCounts;
+
     // these two arrays contain one entry for each NodeClass, indexed by NodeClass.iterableId.
     // they contain the first and last pointer to a linked list of all nodes with this type.
     private final ArrayList<Node> nodeCacheFirst;
@@ -116,6 +121,7 @@
         this.name = name;
         if (MODIFICATION_COUNTS_ENABLED) {
             nodeModCounts = new int[nodes.size()];
+            nodeUsageModCounts = new int[nodes.size()];
         }
     }
 
@@ -137,6 +143,24 @@
         }
     }
 
+    int usageModCount(Node node) {
+        if (node.id >= 0 && node.id < nodeUsageModCounts.length) {
+            return nodeUsageModCounts[node.id];
+        }
+        return 0;
+    }
+
+    void incUsageModCount(Node node) {
+        if (node.id >= 0) {
+            if (node.id >= nodeUsageModCounts.length) {
+                nodeUsageModCounts = Arrays.copyOf(nodeUsageModCounts, node.id + 30);
+            }
+            nodeUsageModCounts[node.id]++;
+        } else {
+            assert false;
+        }
+    }
+
     /**
      * Creates a copy of this graph.
      */

--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java	Wed Sep 04 10:47:37 2013 -0400
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java	Thu Sep 05 00:44:36 2013 +0200
@@ -121,7 +121,17 @@
     // therefore points to the next Node of the same type.
     Node typeCacheNext;
 
-    private NodeUsagesList usages;
+    private static final int INLINE_USAGE_COUNT = 2;
+    private static final Node[] NO_NODES = {};
+
+    /**
+     * Head of usage list. The elements of the usage list in order are {@link #usage0},
+     * {@link #usage1} and {@link #extraUsages}. The first null entry terminates the list.
+     */
+    private Node usage0;
+    private Node usage1;
+    private Node[] extraUsages = NO_NODES;
+
     private Node predecessor;
 
     public Node() {
@@ -157,8 +167,184 @@
         return getNodeClass().getSuccessorIterable(this);
     }
 
+    class NodeUsageIterator implements Iterator<Node> {
+
+        private final int expectedModCount = usageModCount();
+        int index = -1;
+        Node current;
+
+        private void advance() {
+            assert index == -1 || current != null;
+            current = null;
+            index++;
+            if (index == 0) {
+                current = usage0;
+            } else if (index == 1) {
+                current = usage1;
+            } else {
+                if (index - INLINE_USAGE_COUNT < extraUsages.length) {
+                    current = extraUsages[index - INLINE_USAGE_COUNT];
+                }
+            }
+        }
+
+        public NodeUsageIterator() {
+            advance();
+        }
+
+        public boolean hasNext() {
+            assert expectedModCount == usageModCount();
+            return current != null;
+        }
+
+        public Node next() {
+            assert expectedModCount == usageModCount();
+            Node result = current;
+            if (result == null) {
+                throw new NoSuchElementException();
+            }
+            advance();
+            return result;
+        }
+
+        public void remove() {
+            throw new UnsupportedOperationException();
+        }
+    }
+
+    class NodeUsageIterable extends AbstractNodeIterable<Node> {
+
+        public NodeUsageIterator iterator() {
+            return new NodeUsageIterator();
+        }
+
+        @Override
+        public boolean isEmpty() {
+            return usage0 == null;
+        }
+
+        @Override
+        public boolean isNotEmpty() {
+            return usage0 != null;
+        }
+
+        @Override
+        public int count() {
+            if (usage0 == null) {
+                return 0;
+            }
+            if (usage1 == null) {
+                return 1;
+            }
+            int count = 2;
+            for (int i = 0; i < extraUsages.length && extraUsages[i] != null; i++) {
+                count++;
+            }
+            return count;
+        }
+    }
+
+    /**
+     * Gets the list of nodes that use this node (e.g., as an input).
+     */
     public final NodeIterable<Node> usages() {
-        return usages;
+        return new NodeUsageIterable();
+    }
+
+    /**
+     * Adds a given node to this node's {@linkplain #usages() usages}.
+     * 
+     * @param node the node to add
+     */
+    private void addUsage(Node node) {
+        incUsageModCount();
+        if (usage0 == null) {
+            usage0 = node;
+        } else if (usage1 == null) {
+            usage1 = node;
+        } else {
+            int length = extraUsages.length;
+            int start = extraUsages.length >> 1;
+            if (start < length && extraUsages[start] == null) {
+                start = 0;
+            }
+            for (int i = start; i < length; i++) {
+                if (extraUsages[i] == null) {
+                    extraUsages[i] = node;
+                    return;
+                }
+            }
+            extraUsages = Arrays.copyOf(extraUsages, length * 2 + 1);
+            extraUsages[length] = node;
+        }
+    }
+
+    private Node removeFirstExtraUsage() {
+        Node res = null;
+        if (extraUsages.length > 0) {
+            res = extraUsages[0];
+            for (int i = 1; i < extraUsages.length; ++i) {
+                Node n = extraUsages[i];
+                extraUsages[i - 1] = n;
+                if (n == null) {
+                    break;
+                }
+            }
+            extraUsages[extraUsages.length - 1] = null;
+        }
+        return res;
+    }
+
+    /**
+     * Removes a given node from this node's {@linkplain #usages() usages}.
+     * 
+     * @param node the node to remove
+     * @return whether or not {@code usage} was in the usage list
+     */
+    private boolean removeUsage(Node node) {
+        // It is critical that this method maintains the invariant that
+        // the usage list has no null element preceding a non-null element
+        incUsageModCount();
+        if (usage0 == null) {
+            return false;
+        }
+        if (usage0 == node) {
+            usage0 = usage1;
+            if (usage1 != null) {
+                usage1 = removeFirstExtraUsage();
+            }
+            return true;
+        }
+        if (usage1 == null) {
+            return false;
+        }
+        if (usage1 == node) {
+            usage1 = removeFirstExtraUsage();
+            return true;
+        }
+        int length = extraUsages.length;
+        for (int i = 0; i < length; i++) {
+            if (extraUsages[i] == node) {
+                for (int j = i + 1; j < length; j++) {
+                    Node toMove = extraUsages[j];
+                    extraUsages[j - 1] = toMove;
+                    if (toMove == null) {
+                        break;
+                    }
+                }
+                extraUsages[length - 1] = null;
+
+                return true;
+            }
+        }
+        return false;
+    }
+
+    private void clearUsages() {
+        incUsageModCount();
+        usage0 = null;
+        usage1 = null;
+        extraUsages = NO_NODES;
     }
 
     public final Node predecessor() {
@@ -178,6 +364,19 @@
         }
     }
 
+    final int usageModCount() {
+        if (MODIFICATION_COUNTS_ENABLED && graph != null) {
+            return graph.usageModCount(this);
+        }
+        return 0;
+    }
+
+    final void incUsageModCount() {
+        if (MODIFICATION_COUNTS_ENABLED && graph != null) {
+            graph.incUsageModCount(this);
+        }
+    }
+
     public boolean isDeleted() {
         return id <= DELETED_ID_START;
     }
@@ -191,7 +390,6 @@
      * newInput: removes this node from oldInput's usages and adds this node to newInput's usages.
      */
     protected void updateUsages(Node oldInput, Node newInput) {
-        assert assertTrue(usages != null, "usages == null while adding %s to %s", newInput, this);
         if (oldInput != newInput) {
             if (oldInput != null) {
                 boolean result = removeThisFromUsages(oldInput);
@@ -202,8 +400,7 @@
                 if (inputChanged != null) {
                     inputChanged.nodeChanged(this);
                 }
-                assert newInput.usages != null : "not yet added? " + newInput;
-                newInput.usages.add(this);
+                newInput.addUsage(this);
             } else if (oldInput != null && oldInput.usages().isEmpty()) {
                 NodeChangedListener nodeChangedListener = graph.usagesDroppedZero;
                 if (nodeChangedListener != null) {
@@ -219,7 +416,6 @@
      * this node to newSuccessor's predecessors.
      */
     protected void updatePredecessor(Node oldSuccessor, Node newSuccessor) {
-        assert assertTrue(usages != null, "usages == null while adding %s to %s", newSuccessor, this);
         if (oldSuccessor != newSuccessor) {
             if (oldSuccessor != null) {
                 assert assertTrue(oldSuccessor.predecessor == this, "wrong predecessor in old successor (%s): %s", oldSuccessor, oldSuccessor.predecessor);
@@ -236,7 +432,6 @@
         assert assertTrue(id == INITIAL_ID, "unexpected id: %d", id);
         this.graph = newGraph;
         newGraph.register(this);
-        usages = new NodeUsagesList();
         for (Node input : inputs()) {
             updateUsages(null, input);
         }
@@ -259,7 +454,7 @@
 
     public void replaceAtUsages(Node other) {
         assert checkReplaceWith(other);
-        for (Node usage : usages) {
+        for (Node usage : usages()) {
             boolean result = usage.getNodeClass().replaceFirstInput(usage, this, other);
             assert assertTrue(result, "not found in inputs, usage: %s", usage);
             if (other != null) {
@@ -267,10 +462,10 @@
                 if (inputChanged != null) {
                     inputChanged.nodeChanged(usage);
                 }
-                other.usages.add(usage);
+                other.addUsage(usage);
             }
         }
-        usages.clear();
+        clearUsages();
     }
 
     public void replaceAtPredecessor(Node other) {
@@ -320,11 +515,7 @@
     }
 
     private boolean removeThisFromUsages(Node n) {
-        if (n.usages.remove(this)) {
-            return true;
-        } else {
-            return false;
-        }
+        return n.removeUsage(this);
     }
 
     public void clearSuccessors() {
@@ -338,7 +529,7 @@
     }
 
     private boolean checkDeletion() {
-        assertTrue(usages.isEmpty(), "cannot delete node %s because of usages: %s", this, usages);
+        assertTrue(usages().isEmpty(), "cannot delete node %s because of usages: %s", this, usages());
         assertTrue(predecessor == null, "cannot delete node %s because of predecessor: %s", this, predecessor);
         return true;
     }
@@ -361,7 +552,7 @@
         NodeClass clazz = getNodeClass();
         clazz.copyInputs(this, newNode);
         for (Node input : inputs()) {
-            input.usages.add(newNode);
+            input.addUsage(newNode);
         }
         return newNode;
     }
@@ -379,7 +570,9 @@
         newNode.typeCacheNext = null;
         newNode.id = INITIAL_ID;
         into.register(newNode);
-        newNode.usages = new NodeUsagesList();
+        newNode.usage0 = null;
+        newNode.usage1 = null;
+        newNode.extraUsages = NO_NODES;
         newNode.predecessor = null;
         return newNode;
     }
@@ -581,10 +774,10 @@
         }
 
         if (precision > 0) {
-            if (this.usages.count() > 0) {
+            if (!usages().isEmpty()) {
                 formatter.format(" usages={");
                 int z = 0;
-                for (Node usage : this.usages) {
+                for (Node usage : usages()) {
                     if (z != 0) {
                         formatter.format(", ");
                     }

--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeInputList.java	Wed Sep 04 10:47:37 2013 -0400
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeInputList.java	Thu Sep 05 00:44:36 2013 +0200
@@ -39,13 +39,13 @@
 
     public NodeInputList(Node self, T[] elements) {
         super(elements);
-        assert self.usages() == null;
+        assert self.usages().isEmpty();
         this.self = self;
     }
 
     public NodeInputList(Node self, List<? extends T> elements) {
         super(elements);
-        assert self.usages() == null;
+        assert self.usages().isEmpty();
         this.self = self;
     }
 

--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeSuccessorList.java	Wed Sep 04 10:47:37 2013 -0400
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeSuccessorList.java	Thu Sep 05 00:44:36 2013 +0200
@@ -37,7 +37,7 @@
 
     public NodeSuccessorList(Node self, T[] elements) {
         super(elements);
-        assert self.usages() == null;
+        assert self.usages().isEmpty();
         this.self = self;
     }
 

--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeUsagesList.java	Wed Sep 04 10:47:37 2013 -0400
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,163 +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;
-
-import java.util.*;
-
-import com.oracle.graal.graph.iterators.*;
-
-public final class NodeUsagesList extends AbstractNodeIterable<Node> {
-
-    protected static final Node[] EMPTY_NODE_ARRAY = new Node[0];
-
-    protected Node[] nodes = EMPTY_NODE_ARRAY;
-    private int size;
-    private int modCount;
-
-    NodeUsagesList() {
-        this.size = 0;
-        this.nodes = EMPTY_NODE_ARRAY;
-    }
-
-    NodeUsagesList(Node[] nodes) {
-        this.size = nodes.length;
-        this.nodes = nodes;
-    }
-
-    @Override
-    public boolean isEmpty() {
-        return size == 0;
-    }
-
-    @Override
-    public boolean isNotEmpty() {
-        return size > 0;
-    }
-
-    @Override
-    public int count() {
-        return size;
-    }
-
-    @Override
-    public Iterator<Node> iterator() {
-        return new Iterator<Node>() {
-
-            private final int expectedModCount = NodeUsagesList.this.modCount;
-            private int index = 0;
-
-            @Override
-            public boolean hasNext() {
-                assert expectedModCount == NodeUsagesList.this.modCount;
-                return index < NodeUsagesList.this.size;
-            }
-
-            @Override
-            public Node next() {
-                assert expectedModCount == NodeUsagesList.this.modCount;
-                return NodeUsagesList.this.nodes[index++];
-            }
-
-            @Override
-            public void remove() {
-                throw new UnsupportedOperationException();
-            }
-        };
-    }
-
-    @Override
-    public boolean contains(Node other) {
-        for (int i = 0; i < size; i++) {
-            if (nodes[i] == other) {
-                return true;
-            }
-        }
-        return false;
-    }
-
-    @Override
-    public List<Node> snapshot() {
-        return Arrays.asList(Arrays.copyOf(NodeUsagesList.this.nodes, NodeUsagesList.this.size));
-    }
-
-    private void incModCount() {
-        modCount++;
-    }
-
-    boolean add(Node node) {
-        incModCount();
-        if (size == nodes.length) {
-            nodes = Arrays.copyOf(nodes, nodes.length * 2 + 1);
-        }
-        nodes[size++] = node;
-        return true;
-    }
-
-    void copyAndClear(NodeUsagesList other) {
-        incModCount();
-        other.incModCount();
-        nodes = other.nodes;
-        size = other.size;
-        nodes = EMPTY_NODE_ARRAY;
-        size = 0;
-    }
-
-    void clear() {
-        incModCount();
-        nodes = EMPTY_NODE_ARRAY;
-        size = 0;
-    }
-
-    boolean remove(Node node) {
-        int i = 0;
-        incModCount();
-        while (i < size && nodes[i] != node) {
-            i++;
-        }
-        if (i < size) {
-            i++;
-            while (i < size) {
-                nodes[i - 1] = nodes[i];
-                i++;
-            }
-            nodes[--size] = null;
-            return true;
-        } else {
-            return false;
-        }
-    }
-
-    @Override
-    public String toString() {
-        StringBuilder str = new StringBuilder();
-        str.append('[');
-        for (int i = 0; i < size; i++) {
-            if (i > 0) {
-                str.append(", ");
-            }
-            str.append(nodes[i]);
-        }
-        str.append(']');
-        return str.toString();
-    }
-}