# HG changeset patch
# User Doug Simon <doug.simon@oracle.com>
# Date 1383678222 -3600
# Node ID 43301f080126c5cc0667368f7cee370f75d5d4e3
# Parent  ca8ab182026f7b88327c212ec75f4bb03c11ed45
added graph compression (GRAAL-571)

diff -r ca8ab182026f -r 43301f080126 graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java
--- a/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Tue Nov 05 19:54:32 2013 +0100
+++ b/graal/com.oracle.graal.compiler/src/com/oracle/graal/compiler/GraalCompiler.java	Tue Nov 05 20:03:42 2013 +0100
@@ -209,12 +209,15 @@
 
         HighTierContext highTierContext = new HighTierContext(providers, assumptions, cache, plan, optimisticOpts);
         suites.getHighTier().apply(graph, highTierContext);
+        graph.maybeCompress();
 
         MidTierContext midTierContext = new MidTierContext(providers, assumptions, target, optimisticOpts);
         suites.getMidTier().apply(graph, midTierContext);
+        graph.maybeCompress();
 
         LowTierContext lowTierContext = new LowTierContext(providers, assumptions, target);
         suites.getLowTier().apply(graph, lowTierContext);
+        graph.maybeCompress();
 
         // we do not want to store statistics about OSR compilations because it may prevent inlining
         if (!graph.isOSR()) {
diff -r ca8ab182026f -r 43301f080126 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	Tue Nov 05 19:54:32 2013 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Tue Nov 05 20:03:42 2013 +0100
@@ -24,6 +24,7 @@
 
 import java.util.*;
 
+import com.oracle.graal.debug.*;
 import com.oracle.graal.graph.GraphEvent.NodeEvent;
 import com.oracle.graal.graph.Node.ValueNumberable;
 import com.oracle.graal.graph.iterators.*;
@@ -37,7 +38,15 @@
 
     private static final boolean TIME_TRAVEL = false;
 
-    private final ArrayList<Node> nodes;
+    /**
+     * The set of nodes in the graph, ordered by {@linkplain #register(Node) registration} time.
+     */
+    private Node[] nodes;
+
+    /**
+     * The number of valid entries in {@link #nodes}.
+     */
+    private int nodesSize;
 
     /**
      * Records the modification count for nodes. This is only used in assertions.
@@ -53,9 +62,15 @@
     // they contain the first and last pointer to a linked list of all nodes with this type.
     private final ArrayList<Node> nodeCacheFirst;
     private final ArrayList<Node> nodeCacheLast;
-    private int deletedNodeCount;
+    private int nodesDeletedSinceLastCompression;
+    private int nodesDeletedBeforeLastCompression;
     private GraphEventLog eventLog;
 
+    /**
+     * The number of times this graph has been compressed.
+     */
+    int compressions;
+
     NodeChangedListener inputChangedListener;
     NodeChangedListener usagesDroppedToZeroListener;
     private final HashMap<CacheEntry, Node> cachedNodes = new HashMap<>();
@@ -110,19 +125,21 @@
         return enabled;
     }
 
+    private static final int INITIAL_NODES_SIZE = 32;
+
     /**
      * Creates an empty Graph with a given name.
      * 
      * @param name the name of the graph, used for debugging purposes
      */
     public Graph(String name) {
-        nodes = new ArrayList<>(32);
+        nodes = new Node[INITIAL_NODES_SIZE];
         nodeCacheFirst = new ArrayList<>(NodeClass.cacheSize());
         nodeCacheLast = new ArrayList<>(NodeClass.cacheSize());
         this.name = name;
         if (MODIFICATION_COUNTS_ENABLED) {
-            nodeModCounts = new int[nodes.size()];
-            nodeUsageModCounts = new int[nodes.size()];
+            nodeModCounts = new int[INITIAL_NODES_SIZE];
+            nodeUsageModCounts = new int[INITIAL_NODES_SIZE];
         }
     }
 
@@ -204,16 +221,31 @@
      * @return the number of live nodes in this graph
      */
     public int getNodeCount() {
-        return nodes.size() - getDeletedNodeCount();
+        return nodesSize - getNodesDeletedSinceLastCompression();
+    }
+
+    /**
+     * Gets the number of times this graph has been {@linkplain #maybeCompress() compressed}. Node
+     * identifiers are only stable between compressions. To ensure this constraint is observed, any
+     * entity relying upon stable node identifiers should use {@link NodeIdAccessor}.
+     */
+    public int getCompressions() {
+        return compressions;
     }
 
     /**
-     * Gets the number of node which have been deleted from this graph.
-     * 
-     * @return the number of node which have been deleted from this graph
+     * Gets the number of nodes which have been deleted from this graph since it was last
+     * {@linkplain #maybeCompress() compressed}.
      */
-    public int getDeletedNodeCount() {
-        return deletedNodeCount;
+    public int getNodesDeletedSinceLastCompression() {
+        return nodesDeletedSinceLastCompression;
+    }
+
+    /**
+     * Gets the total number of nodes which have been deleted from this graph.
+     */
+    public int getTotalNodesDeleted() {
+        return nodesDeletedSinceLastCompression + nodesDeletedBeforeLastCompression;
     }
 
     /**
@@ -401,10 +433,11 @@
     /**
      * A snapshot of the {@linkplain Graph#getNodeCount() live node count} in a graph.
      */
-    public static class Mark {
+    public static class Mark extends NodeIdAccessor {
         private final int value;
 
         Mark(Graph graph) {
+            super(graph);
             this.value = graph.nodeIdCount();
         }
 
@@ -412,14 +445,14 @@
         public boolean equals(Object obj) {
             if (obj instanceof Mark) {
                 Mark other = (Mark) obj;
-                return other.getValue() == getValue();
+                return other.getValue() == getValue() && other.getGraph() == getGraph();
             }
             return false;
         }
 
         @Override
         public int hashCode() {
-            return value;
+            return value ^ (epoch + 11);
         }
 
         /**
@@ -459,22 +492,22 @@
         }
 
         private void forward() {
-            if (index < nodes.size()) {
+            if (index < nodesSize) {
                 do {
                     index++;
-                } while (index < nodes.size() && nodes.get(index) == null);
+                } while (index < nodesSize && nodes[index] == null);
             }
         }
 
         @Override
         public boolean hasNext() {
             checkForDeletedNode();
-            return index < nodes.size();
+            return index < nodesSize;
         }
 
         private void checkForDeletedNode() {
-            if (index < nodes.size()) {
-                while (index < nodes.size() && nodes.get(index) == null) {
+            if (index < nodesSize) {
+                while (index < nodesSize && nodes[index] == null) {
                     index++;
                 }
             }
@@ -483,7 +516,7 @@
         @Override
         public Node next() {
             try {
-                return nodes.get(index);
+                return nodes[index];
             } finally {
                 forward();
             }
@@ -533,6 +566,52 @@
     private static final Node PLACE_HOLDER = new Node() {
     };
 
+    /**
+     * When the percent of live nodes in {@link #nodes} fall below this number, a call to
+     * {@link #maybeCompress()} will actually do compression.
+     */
+    public static final int COMPRESSION_THRESHOLD = Integer.getInteger("graal.graphCompressionThreshold", 70);
+
+    private static final DebugMetric GraphCompressions = Debug.metric("GraphCompressions");
+
+    /**
+     * If the {@linkplain #COMPRESSION_THRESHOLD compression threshold} is met, the list of nodes is
+     * compressed such that all non-null entries precede all null entries while preserving the
+     * ordering between the nodes within the list.
+     */
+    public boolean maybeCompress() {
+        int liveNodeCount = getNodeCount();
+        int liveNodePercent = liveNodeCount * 100 / nodesSize;
+        if (COMPRESSION_THRESHOLD == 0 || liveNodePercent >= COMPRESSION_THRESHOLD) {
+            return false;
+        }
+        GraphCompressions.increment();
+        int nextId = 0;
+        for (int i = 0; nextId < liveNodeCount; i++) {
+            Node n = nodes[i];
+            if (n != null) {
+                assert n.id == i;
+                if (i != nextId) {
+                    assert n.id > nextId;
+                    n.id = nextId;
+                    nodes[nextId] = n;
+                    nodes[i] = null;
+                }
+                nextId++;
+            }
+        }
+        if (MODIFICATION_COUNTS_ENABLED) {
+            // This will cause any current iteration to fail with an assertion
+            Arrays.fill(nodeModCounts, 0);
+            Arrays.fill(nodeUsageModCounts, 0);
+        }
+        nodesSize = nextId;
+        compressions++;
+        nodesDeletedBeforeLastCompression += nodesDeletedSinceLastCompression;
+        nodesDeletedSinceLastCompression = 0;
+        return true;
+    }
+
     private class TypedNodeIterator<T extends IterableNodeType> implements Iterator<T> {
 
         private final int[] ids;
@@ -696,8 +775,12 @@
     void register(Node node) {
         assert !node.isExternal();
         assert node.id() == Node.INITIAL_ID;
-        int id = nodes.size();
-        nodes.add(id, node);
+        if (nodes.length == nodesSize) {
+            nodes = Arrays.copyOf(nodes, (nodesSize * 2) + 1);
+        }
+        int id = nodesSize;
+        nodes[id] = node;
+        nodesSize++;
 
         int nodeClassId = node.getNodeClass().iterableId();
         if (nodeClassId != NodeClass.NOT_ITERABLE) {
@@ -744,8 +827,8 @@
     void unregister(Node node) {
         assert !node.isDeleted() : "cannot delete a node twice! node=" + node;
         logNodeDeleted(node);
-        nodes.set(node.id(), null);
-        deletedNodeCount++;
+        nodes[node.id] = null;
+        nodesDeletedSinceLastCompression++;
 
         // nodes aren't removed from the type cache here - they will be removed during iteration
     }
@@ -768,7 +851,7 @@
     }
 
     Node getNode(int i) {
-        return nodes.get(i);
+        return nodes[i];
     }
 
     /**
@@ -777,7 +860,7 @@
      * @return the number of node ids generated so far
      */
     int nodeIdCount() {
-        return nodes.size();
+        return nodesSize;
     }
 
     /**
diff -r ca8ab182026f -r 43301f080126 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java	Tue Nov 05 19:54:32 2013 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java	Tue Nov 05 20:03:42 2013 +0100
@@ -30,8 +30,8 @@
 
     private final boolean autoGrow;
     private final BitSet bitMap;
-    private final Graph graph;
     private int nodeCount;
+    private final NodeIdAccessor nodeIdAccessor;
 
     public NodeBitMap(Graph graph) {
         this(graph, false);
@@ -42,14 +42,14 @@
     }
 
     private NodeBitMap(Graph graph, boolean autoGrow, int nodeCount, BitSet bits) {
-        this.graph = graph;
+        this.nodeIdAccessor = new NodeIdAccessor(graph);
         this.autoGrow = autoGrow;
         this.nodeCount = nodeCount;
         bitMap = bits;
     }
 
     public Graph graph() {
-        return graph;
+        return nodeIdAccessor.getGraph();
     }
 
     public void setUnion(NodeBitMap other) {
@@ -70,11 +70,11 @@
     }
 
     public boolean isMarked(Node node) {
-        return bitMap.get(node.id());
+        return bitMap.get(nodeIdAccessor.getNodeId(node));
     }
 
     public boolean isNew(Node node) {
-        return node.id() >= nodeCount;
+        return nodeIdAccessor.getNodeId(node) >= nodeCount;
     }
 
     public void mark(Node node) {
@@ -82,7 +82,7 @@
             grow();
         }
         assert check(node);
-        bitMap.set(node.id());
+        bitMap.set(nodeIdAccessor.getNodeId(node));
     }
 
     public void clear(Node node) {
@@ -90,7 +90,7 @@
             return;
         }
         assert check(node);
-        bitMap.clear(node.id());
+        bitMap.clear(nodeIdAccessor.getNodeId(node));
     }
 
     public void clearAll() {
@@ -98,20 +98,20 @@
     }
 
     public void intersect(NodeBitMap other) {
-        assert graph == other.graph;
+        assert graph() == other.graph();
         bitMap.and(other.bitMap);
     }
 
     public void grow(Node node) {
-        nodeCount = Math.max(nodeCount, node.id() + 1);
+        nodeCount = Math.max(nodeCount, nodeIdAccessor.getNodeId(node) + 1);
     }
 
     public void grow() {
-        nodeCount = Math.max(nodeCount, graph.nodeIdCount());
+        nodeCount = Math.max(nodeCount, graph().nodeIdCount());
     }
 
     private boolean check(Node node) {
-        assert node.graph() == graph : "this node is not part of the graph";
+        assert node.graph() == graph() : "this node is not part of the graph";
         assert !isNew(node) : "node was added to the graph after creating the node bitmap: " + node;
         assert node.isAlive() : "node is deleted!";
         return true;
@@ -180,7 +180,7 @@
     }
 
     public NodeBitMap copy() {
-        return new NodeBitMap(graph, autoGrow, nodeCount, (BitSet) bitMap.clone());
+        return new NodeBitMap(graph(), autoGrow, nodeCount, (BitSet) bitMap.clone());
     }
 
     @Override
diff -r ca8ab182026f -r 43301f080126 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java	Tue Nov 05 19:54:32 2013 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeClass.java	Tue Nov 05 20:03:42 2013 +0100
@@ -1272,7 +1272,7 @@
 
     static Map<Node, Node> addGraphDuplicate(final Graph graph, final Graph oldGraph, int estimatedNodeCount, Iterable<Node> nodes, final DuplicationReplacement replacements) {
         final Map<Node, Node> newNodes;
-        if (estimatedNodeCount > (oldGraph.getNodeCount() + oldGraph.getDeletedNodeCount() >> 4)) {
+        if (estimatedNodeCount > (oldGraph.getNodeCount() + oldGraph.getNodesDeletedSinceLastCompression() >> 4)) {
             // Use dense map
             newNodes = new NodeNodeMap(oldGraph);
         } else {
diff -r ca8ab182026f -r 43301f080126 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeIdAccessor.java
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeIdAccessor.java	Tue Nov 05 20:03:42 2013 +0100
@@ -0,0 +1,63 @@
+/*
+ * Copyright (c) 2013, 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;
+
+/**
+ * An entity that depends upon {@linkplain Graph#maybeCompress() stable} node identifiers.
+ */
+class NodeIdAccessor {
+    final Graph graph;
+    final int epoch;
+
+    public NodeIdAccessor(Graph graph) {
+        this.graph = graph;
+        this.epoch = graph.compressions;
+    }
+
+    Graph getGraph() {
+        return graph;
+    }
+
+    /**
+     * Verifies that node identifiers have not changed since this object was created.
+     * 
+     * @return true if the check succeeds
+     * @throws VerificationError if the check fails
+     */
+    public boolean verifyIdsAreStable() {
+        int compressions = graph.compressions - epoch;
+        if (compressions != 0) {
+            throw new VerificationError("accessing node id in %s across %d graph compression%s", graph, compressions, compressions == 1 ? "" : "s");
+        }
+        return true;
+    }
+
+    /**
+     * Gets the identifier for a node. If assertions are enabled, this method asserts that the
+     * identifier is stable.
+     */
+    public int getNodeId(Node node) {
+        assert verifyIdsAreStable();
+        return node.id();
+    }
+}
diff -r ca8ab182026f -r 43301f080126 graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java	Tue Nov 05 19:54:32 2013 +0100
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeMap.java	Tue Nov 05 20:03:42 2013 +0100
@@ -26,9 +26,8 @@
 import java.util.*;
 import java.util.Map.Entry;
 
-public class NodeMap<T> {
+public class NodeMap<T> extends NodeIdAccessor {
 
-    private final Graph graph;
     private final boolean autogrow;
     protected Object[] values;
 
@@ -37,13 +36,13 @@
     }
 
     public NodeMap(Graph graph, boolean autogrow) {
-        this.graph = graph;
+        super(graph);
         this.values = new Object[graph.nodeIdCount()];
         this.autogrow = autogrow;
     }
 
     public NodeMap(NodeMap<T> copyFrom) {
-        this.graph = copyFrom.graph;
+        super(copyFrom.graph);
         this.values = Arrays.copyOf(copyFrom.values, copyFrom.values.length);
         this.autogrow = copyFrom.autogrow;
     }
@@ -51,7 +50,7 @@
     @SuppressWarnings("unchecked")
     public T get(Node node) {
         check(node);
-        return (T) values[node.id()];
+        return (T) values[getNodeId(node)];
     }
 
     public boolean isEmpty() {
@@ -83,7 +82,7 @@
 
     public void set(Node node, T value) {
         check(node);
-        values[node.id()] = value;
+        values[getNodeId(node)] = value;
     }
 
     public int size() {
@@ -91,7 +90,7 @@
     }
 
     public boolean isNew(Node node) {
-        return node.id() >= size();
+        return getNodeId(node) >= size();
     }
 
     public void grow() {
diff -r ca8ab182026f -r 43301f080126 graal/com.oracle.graal.printer/src/com/oracle/graal/printer/BinaryGraphPrinter.java
--- a/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/BinaryGraphPrinter.java	Tue Nov 05 19:54:32 2013 +0100
+++ b/graal/com.oracle.graal.printer/src/com/oracle/graal/printer/BinaryGraphPrinter.java	Tue Nov 05 20:03:42 2013 +0100
@@ -408,7 +408,7 @@
             }
         }
         Map<Object, Object> props = new HashMap<>();
-        int firstExternalNodeId = graph.getNodeCount() + graph.getDeletedNodeCount();
+        int firstExternalNodeId = graph.getNodeCount() + graph.getTotalNodesDeleted();
         for (Node node : graph.getNodes()) {
             for (Node input : node.inputs()) {
                 if (input.isExternal()) {