Mercurial > hg > graal-compiler
changeset 11528:8f500c7a510a
inlined NodeUsageList into Node (GRAAL-452)
author | Doug Simon <doug.simon@oracle.com> |
---|---|
date | Thu, 05 Sep 2013 00:44:36 +0200 |
parents | c99e65785936 |
children | 6d221435fff9 |
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/NodeInputList.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeSuccessorList.java graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeUsagesList.java |
diffstat | 5 files changed, 240 insertions(+), 186 deletions(-) [+] |
line wrap: on
line diff
--- 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(); - } -}