Mercurial > hg > truffle
changeset 15153:d224a3a0e6a9
Various optimizations of Node.replaceAtMatchingUsages and Node.replaceAtUsages
author | Gilles Duboscq <duboscq@ssw.jku.at> |
---|---|
date | Tue, 15 Apr 2014 18:24:22 +0200 |
parents | 5f75a06505a6 |
children | d708c2fc5cba |
files | graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Node.java |
diffstat | 1 files changed, 82 insertions(+), 74 deletions(-) [+] |
line wrap: on
line diff
--- 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); } }