--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java	Tue Apr 15 13:40:43 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java	Tue Apr 15 18:24:22 2014 +0200
@@ -189,7 +189,6 @@
         Node current;
 
         private void advance() {
-            assert index == -1 || current != null;
             current = null;
             index++;
             if (index == 0) {
@@ -246,13 +245,7 @@
 
         @Override
         public int count() {
-            if (usage0 == null) {
-                return 0;
-            }
-            if (usage1 == null) {
-                return 1;
-            }
-            return 2 + indexOfLastNonNull(extraUsages) + 1;
+            return usageCount();
         }
     }
 
@@ -349,64 +342,79 @@
         }
     }
 
+    private int usageCount() {
+        if (usage0 == null) {
+            return 0;
+        }
+        if (usage1 == null) {
+            return 1;
+        }
+        return 2 + indexOfLastNonNull(extraUsages) + 1;
+    }
+
     /**
-     * Remove all usages between {@code fromIndex} and {@code toIndex} (inclusive).
+     * Remove all usages between {@code fromIndex} and {@code toIndex} (exclusive), also, if
+     * {@code toIndex} is a valid usage, it is moved to {@code fromIndex}.
+     *
+     * <p>
+     * Visually,
+     *
+     * <pre>
+     * {@code
+     * [1, 2, 3, 4, 5, 6, 7].removeUsagesAndShiftFirst(1, 2) == [1, 4, 6, 7, 5, null, null]}
+     * </pre>
+     *
      *
      * @param fromIndex the index of the first element to be removed
-     * @param toIndex the index of the last element to be removed
+     * @param toIndex the index after the last element to be removed
      */
-    private void removeUsages(int fromIndex, int toIndex) {
-        assert fromIndex >= toIndex;
-        assert toIndex < usages().count();
-        int from, holeLength;
-        if (fromIndex < INLINE_USAGE_COUNT) {
-            if (fromIndex == 0) {
-                if (toIndex == 0) {
-                    usage0 = usage1;
-                    if (extraUsages.length > 0) {
-                        usage1 = extraUsages[0];
-                    } else {
-                        usage1 = null;
-                    }
-                } else {
-                    if (extraUsages.length > toIndex - INLINE_USAGE_COUNT + 1) {
-                        usage0 = extraUsages[toIndex - INLINE_USAGE_COUNT + 1];
-                    } else {
-                        usage0 = null;
-                    }
-                    if (extraUsages.length > toIndex - INLINE_USAGE_COUNT + 2) {
-                        usage1 = extraUsages[toIndex - INLINE_USAGE_COUNT + 2];
-                    } else {
-                        usage1 = null;
-                    }
-                }
-            } else {
-                if (extraUsages.length > toIndex - INLINE_USAGE_COUNT + 1) {
-                    usage1 = extraUsages[toIndex - INLINE_USAGE_COUNT + 1];
-                } else {
-                    usage1 = null;
-                }
-            }
-            from = 0;
-        } else {
-            from = fromIndex - INLINE_USAGE_COUNT;
+    private void removeUsagesAndShiftFirst(int fromIndex, int toIndex) {
+        assert fromIndex < toIndex;
+        int firstNullIndex = usageCount();
+        assert toIndex <= firstNullIndex;
+        int i = fromIndex;
+        int limit = toIndex;
+        if (toIndex < firstNullIndex) {
+            // move usage at toIndex to fromIndex(!)
+            movUsageTo(toIndex, fromIndex);
+            limit++;
+            i++;
         }
-        holeLength = toIndex - fromIndex + 1;
-        int i = from;
-        while (i + holeLength < extraUsages.length) {
-            if (extraUsages[i] == null) {
-                return;
-            }
-            extraUsages[i] = extraUsages[i + holeLength];
+        while (i < limit && firstNullIndex > limit) {
+            movUsageTo(firstNullIndex - 1, i);
+            firstNullIndex--;
             i++;
         }
-        while (i < extraUsages.length) {
-            if (extraUsages[i] == null) {
-                return;
+        while (i < limit) {
+            if (i == 0) {
+                usage0 = null;
+            } else if (i == 1) {
+                usage1 = null;
+            } else {
+                extraUsages[i - INLINE_USAGE_COUNT] = null;
             }
-            extraUsages[i] = null;
             i++;
         }
+
+    }
+
+    private void movUsageTo(int usageIndex, int toIndex) {
+        assert usageIndex > toIndex;
+        if (toIndex == 0) {
+            if (usageIndex == 1) {
+                usage0 = usage1;
+                usage1 = null;
+            } else {
+                usage0 = extraUsages[usageIndex - INLINE_USAGE_COUNT];
+                extraUsages[usageIndex - INLINE_USAGE_COUNT] = null;
+            }
+        } else if (toIndex == 1) {
+            usage1 = extraUsages[usageIndex - INLINE_USAGE_COUNT];
+            extraUsages[usageIndex - INLINE_USAGE_COUNT] = null;
+        } else {
+            extraUsages[toIndex - INLINE_USAGE_COUNT] = extraUsages[usageIndex - INLINE_USAGE_COUNT];
+            extraUsages[usageIndex - INLINE_USAGE_COUNT] = null;
+        }
     }
 
     /**
@@ -417,6 +425,7 @@
      */
     private boolean removeUsage(Node node) {
         assert recordsUsages();
+        assert node != null;
         // It is critical that this method maintains the invariant that
         // the usage list has no null element preceding a non-null element
         incUsageModCount();
@@ -448,20 +457,19 @@
             }
             return true;
         }
-        int lastNonNull = indexOfLastNonNull(extraUsages);
-        if (lastNonNull >= 0) {
-            for (int i = 0; i <= lastNonNull; ++i) {
-                Node n = extraUsages[i];
-                if (n == node) {
-                    if (i < lastNonNull) {
-                        extraUsages[i] = extraUsages[lastNonNull];
-                        extraUsages[lastNonNull] = null;
-                    } else {
-                        extraUsages[i] = null;
-                    }
-                    return true;
-                }
+        int matchIndex = -1;
+        int i = 0;
+        Node n;
+        while (i < extraUsages.length && (n = extraUsages[i]) != null) {
+            if (n == node) {
+                matchIndex = i;
             }
+            i++;
+        }
+        if (matchIndex >= 0) {
+            extraUsages[matchIndex] = extraUsages[i - 1];
+            extraUsages[i - 1] = null;
+            return true;
         }
         return false;
     }
@@ -623,17 +631,17 @@
                 }
             } else {
                 if (removeStart >= 0) {
-                    int removeEndIndex = it.index - 2;
-                    removeUsages(removeStart, removeEndIndex);
+                    int removeEndIndex = it.index - 1;
+                    removeUsagesAndShiftFirst(removeStart, removeEndIndex);
                     it.index = removeStart;
                     it.advance();
+                    removeStart = -1;
                 }
-                removeStart = -1;
             }
         }
         if (removeStart >= 0) {
-            int removeEndIndex = it.index - 1;
-            removeUsages(removeStart, removeEndIndex);
+            int removeEndIndex = it.index;
+            removeUsagesAndShiftFirst(removeStart, removeEndIndex);
         }
     }