# HG changeset patch # User Thomas Wuerthinger # Date 1422033637 -3600 # Node ID ef1494ece1a89ec261eaa6b0af268b044b9880b4 # Parent ff232ff8d0280420cb6dada1561810a69254ac0f Move to a system that has an extra counter for extra usages. diff -r ff232ff8d028 -r ef1494ece1a8 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java --- 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) { diff -r ff232ff8d028 -r ef1494ece1a8 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java --- 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}. - * - *

- * Visually, - * - * 

-     * {@code
-     * [1, 2, 3, 4, 5, 6, 7].removeUsagesAndShiftFirst(1, 2) == [1, 4, 6, 7, 5, null, null]}
-     *
- * - * - * @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); } diff -r ff232ff8d028 -r ef1494ece1a8 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeUsageIterable.java --- 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(); } } diff -r ff232ff8d028 -r ef1494ece1a8 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeUsageIterator.java --- 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]; } } }