Mercurial > hg > truffle

changeset 18938:ef1494ece1a8

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Move to a system that has an extra counter for extra usages.
author Thomas Wuerthinger <thomas.wuerthinger@oracle.com>
date Fri, 23 Jan 2015 18:20:37 +0100
parents ff232ff8d028
children 732748092bae
files graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeUsageIterable.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeUsageIterator.java
diffstat 4 files changed, 52 insertions(+), 169 deletions(-) [+]
line wrap: on
line diff
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Fri Jan 23 11:52:36 2015 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Fri Jan 23 18:20:37 2015 +0100
@@ -505,7 +505,7 @@
             Node minCountNode = null;
             for (Node input : node.inputs()) {
                 if (input != null) {
-                    int estimate = input.getUsageCountUpperBound();
+                    int estimate = input.getUsageCount();
                     if (estimate == 0) {
                         return null;
                     } else if (estimate < minCount) {
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java	Fri Jan 23 11:52:36 2015 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java	Fri Jan 23 18:20:37 2015 +0100
@@ -190,6 +190,7 @@
     Node usage0;
     Node usage1;
     Node[] extraUsages;
+    int extraUsagesCount;
 
     private Node predecessor;
     private NodeClass nodeClass;
@@ -291,14 +292,14 @@
     /**
      * Gets the maximum number of usages this node has had at any point in time.
      */
-    int getUsageCountUpperBound() {
+    public int getUsageCount() {
         if (usage0 == null) {
             return 0;
         }
         if (usage1 == null) {
             return 1;
         }
-        return 2 + extraUsages.length;
+        return 2 + extraUsagesCount;
     }
 
     /**
@@ -316,40 +317,6 @@
     }
 
     /**
-     * Finds the index of the last non-null entry in a node array. The search assumes that all
-     * non-null entries precede the first null entry in the array.
-     *
-     * @param nodes the array to search
-     * @return the index of the last non-null entry in {@code nodes} if it exists, else -1
-     */
-    private static int indexOfLastNonNull(Node[] nodes) {
-        if (nodes.length == 0 || nodes[0] == null) {
-            return -1;
-        }
-        if (nodes[nodes.length - 1] != null) {
-            return nodes.length - 1;
-        }
-
-        // binary search
-        int low = 0;
-        int high = nodes.length - 1;
-        while (true) {
-            int mid = (low + high) >>> 1;
-            if (nodes[mid] == null) {
-                if (nodes[mid - 1] != null) {
-                    return mid - 1;
-                }
-                high = mid - 1;
-            } else {
-                if (mid == nodes.length - 1 || nodes[mid + 1] == null) {
-                    return mid;
-                }
-                low = mid + 1;
-            }
-        }
-    }
-
-    /**
      * Adds a given node to this node's {@linkplain #usages() usages}.
      *
      * @param node the node to add
@@ -364,94 +331,38 @@
             int length = extraUsages.length;
             if (length == 0) {
                 extraUsages = new Node[4];
-                extraUsages[0] = node;
-            } else {
-                int lastNonNull = indexOfLastNonNull(extraUsages);
-                if (lastNonNull == length - 1) {
-                    extraUsages = Arrays.copyOf(extraUsages, length * 2 + 1);
-                    extraUsages[length] = node;
-                } else if (lastNonNull == -1) {
-                    extraUsages[0] = node;
-                } else {
-                    extraUsages[lastNonNull + 1] = node;
-                }
+            } else if (extraUsagesCount == length) {
+                extraUsages = Arrays.copyOf(extraUsages, length * 2 + 1);
             }
+            extraUsages[extraUsagesCount++] = node;
         }
     }
 
-    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} (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 after the last element to be removed
-     */
-    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++;
-        }
-        while (i < limit && firstNullIndex > limit) {
-            movUsageTo(firstNullIndex - 1, i);
-            firstNullIndex--;
-            i++;
-        }
-        while (i < limit) {
-            if (i == 0) {
+    private void movUsageFromEndTo(int destIndex) {
+        int lastIndex = this.getUsageCount() - 1;
+        if (destIndex == 0) {
+            if (lastIndex == 0) {
                 usage0 = null;
-            } else if (i == 1) {
-                usage1 = null;
-            } else {
-                extraUsages[i - INLINE_USAGE_COUNT] = null;
-            }
-            i++;
-        }
-
-    }
-
-    private void movUsageTo(int usageIndex, int toIndex) {
-        assert usageIndex > toIndex;
-        if (toIndex == 0) {
-            if (usageIndex == 1) {
+                return;
+            } else if (lastIndex == 1) {
                 usage0 = usage1;
                 usage1 = null;
+                return;
             } else {
-                usage0 = extraUsages[usageIndex - INLINE_USAGE_COUNT];
-                extraUsages[usageIndex - INLINE_USAGE_COUNT] = null;
+                usage0 = extraUsages[lastIndex - INLINE_USAGE_COUNT];
             }
-        } else if (toIndex == 1) {
-            usage1 = extraUsages[usageIndex - INLINE_USAGE_COUNT];
-            extraUsages[usageIndex - INLINE_USAGE_COUNT] = null;
+        } else if (destIndex == 1) {
+            if (lastIndex == 1) {
+                usage1 = null;
+                return;
+            }
+            usage1 = extraUsages[lastIndex - INLINE_USAGE_COUNT];
         } else {
-            extraUsages[toIndex - INLINE_USAGE_COUNT] = extraUsages[usageIndex - INLINE_USAGE_COUNT];
-            extraUsages[usageIndex - INLINE_USAGE_COUNT] = null;
+            Node n = extraUsages[lastIndex - INLINE_USAGE_COUNT];
+            extraUsages[destIndex - INLINE_USAGE_COUNT] = n;
         }
+        extraUsages[lastIndex - INLINE_USAGE_COUNT] = null;
+        this.extraUsagesCount--;
     }
 
     /**
@@ -466,46 +377,18 @@
         // the usage list has no null element preceding a non-null element
         incUsageModCount();
         if (usage0 == node) {
-            if (usage1 != null) {
-                int lastNonNull = indexOfLastNonNull(extraUsages);
-                if (lastNonNull >= 0) {
-                    usage0 = extraUsages[lastNonNull];
-                    extraUsages[lastNonNull] = null;
-                } else {
-                    // usage1 is the last element
-                    usage0 = usage1;
-                    usage1 = null;
-                }
-            } else {
-                // usage0 is the last element
-                usage0 = null;
-            }
+            this.movUsageFromEndTo(0);
             return true;
         }
         if (usage1 == node) {
-            int lastNonNull = indexOfLastNonNull(extraUsages);
-            if (lastNonNull >= 0) {
-                usage1 = extraUsages[lastNonNull];
-                extraUsages[lastNonNull] = null;
-            } else {
-                // usage1 is the last element
-                usage1 = null;
-            }
+            this.movUsageFromEndTo(1);
             return true;
         }
-        int matchIndex = -1;
-        int i = 0;
-        Node n;
-        while (i < extraUsages.length && (n = extraUsages[i]) != null) {
-            if (n == node) {
-                matchIndex = i;
+        for (int i = 0; i < this.extraUsagesCount; ++i) {
+            if (extraUsages[i] == node) {
+                this.movUsageFromEndTo(i + INLINE_USAGE_COUNT);
+                return true;
             }
-            i++;
-        }
-        if (matchIndex >= 0) {
-            extraUsages[matchIndex] = extraUsages[i - 1];
-            extraUsages[i - 1] = null;
-            return true;
         }
         return false;
     }
@@ -515,6 +398,7 @@
         usage0 = null;
         usage1 = null;
         extraUsages = NO_NODES;
+        extraUsagesCount = 0;
     }
 
     public final Node predecessor() {
@@ -642,36 +526,33 @@
         clearUsages();
     }
 
+    public Node getUsageAt(int index) {
+        if (index == 0) {
+            return this.usage0;
+        } else if (index == 1) {
+            return this.usage1;
+        } else {
+            return this.extraUsages[index - INLINE_USAGE_COUNT];
+        }
+    }
+
     public void replaceAtMatchingUsages(Node other, NodePredicate usagePredicate) {
         assert checkReplaceWith(other);
-        NodeUsageIterator it = (NodeUsageIterator) usages().iterator();
-        int removeStart = -1;
-        while (it.hasNext()) {
-            Node usage = it.next();
+        int index = 0;
+        while (index < this.getUsageCount()) {
+            Node usage = getUsageAt(index);
             if (usagePredicate.apply(usage)) {
-                if (removeStart < 0) {
-                    removeStart = it.index - 1;
-                }
                 boolean result = usage.getNodeClass().getEdges(Inputs).replaceFirst(usage, this, other);
                 assert assertTrue(result, "not found in inputs, usage: %s", usage);
                 if (other != null) {
                     maybeNotifyInputChanged(usage);
                     other.addUsage(usage);
                 }
+                this.movUsageFromEndTo(index);
             } else {
-                if (removeStart >= 0) {
-                    int removeEndIndex = it.index - 1;
-                    removeUsagesAndShiftFirst(removeStart, removeEndIndex);
-                    it.index = removeStart;
-                    it.advance();
-                    removeStart = -1;
-                }
+                index++;
             }
         }
-        if (removeStart >= 0) {
-            int removeEndIndex = it.index;
-            removeUsagesAndShiftFirst(removeStart, removeEndIndex);
-        }
     }
 
     public void replaceAtUsages(InputType type, Node other) {
@@ -884,6 +765,7 @@
                 newNode.usage0 = null;
                 newNode.usage1 = null;
                 newNode.predecessor = null;
+                newNode.extraUsagesCount = 0;
                 copyOrClearEdgesForClone(newNode, Inputs, edgesToCopy);
                 copyOrClearEdgesForClone(newNode, Successors, edgesToCopy);
             }
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeUsageIterable.java	Fri Jan 23 11:52:36 2015 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeUsageIterable.java	Fri Jan 23 18:20:37 2015 +0100
@@ -54,6 +54,6 @@
 
     @Override
     public int count() {
-        return node.usageCount();
+        return node.getUsageCount();
     }
 }
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeUsageIterator.java	Fri Jan 23 11:52:36 2015 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeUsageIterator.java	Fri Jan 23 18:20:37 2015 +0100
@@ -38,8 +38,9 @@
         } else if (index == 1) {
             current = node.usage1;
         } else {
-            if (index - Node.INLINE_USAGE_COUNT < node.extraUsages.length) {
-                current = node.extraUsages[index - Node.INLINE_USAGE_COUNT];
+            int relativeIndex = index - Node.INLINE_USAGE_COUNT;
+            if (relativeIndex < node.extraUsagesCount) {
+                current = node.extraUsages[relativeIndex];
             }
         }
     }