# HG changeset patch
# User Lukas Stadler <lukas.stadler@oracle.com>
# Date 1401290381 -7200
# Node ID 3f48e9a1016c4493135a0ff9d6cbb6ed92a53d9a
# Parent  cda2a7d1dcff638ff5ba82b1749c3d58901a0bf4
NodeBitMap refactoring

diff -r cda2a7d1dcff -r 3f48e9a1016c 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	Wed May 28 17:19:41 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/Graph.java	Wed May 28 17:19:41 2014 +0200
@@ -740,11 +740,7 @@
     }
 
     public NodeBitMap createNodeBitMap() {
-        return createNodeBitMap(false);
-    }
-
-    public NodeBitMap createNodeBitMap(boolean autoGrow) {
-        return new NodeBitMap(this, autoGrow);
+        return new NodeBitMap(this);
     }
 
     public <T> NodeMap<T> createNodeMap() {
diff -r cda2a7d1dcff -r 3f48e9a1016c 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	Wed May 28 17:19:41 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeBitMap.java	Wed May 28 17:19:41 2014 +0200
@@ -27,92 +27,109 @@
 import com.oracle.graal.graph.iterators.*;
 
 public final class NodeBitMap implements NodeIterable<Node> {
+    private static final int SHIFT = 6;
 
-    private final boolean autoGrow;
-    private final BitSet bitMap;
+    private long[] bits;
     private int nodeCount;
     private final NodeIdAccessor nodeIdAccessor;
 
     public NodeBitMap(Graph graph) {
-        this(graph, false);
+        nodeCount = graph.nodeIdCount();
+        bits = new long[sizeForNodeCount(nodeCount)];
+        this.nodeIdAccessor = new NodeIdAccessor(graph);
     }
 
-    public NodeBitMap(Graph graph, boolean autoGrow) {
-        this(graph, autoGrow, graph.nodeIdCount(), new BitSet(graph.nodeIdCount()));
+    private static int sizeForNodeCount(int nodeCount) {
+        return (nodeCount + Long.SIZE - 1) >> SHIFT;
     }
 
-    private NodeBitMap(Graph graph, boolean autoGrow, int nodeCount, BitSet bits) {
-        this.nodeIdAccessor = new NodeIdAccessor(graph);
-        this.autoGrow = autoGrow;
-        this.nodeCount = nodeCount;
-        bitMap = bits;
+    private NodeBitMap(NodeBitMap other) {
+        this.bits = other.bits.clone();
+        this.nodeCount = other.nodeCount;
+        this.nodeIdAccessor = other.nodeIdAccessor;
     }
 
     public Graph graph() {
         return nodeIdAccessor.getGraph();
     }
 
-    public void setUnion(NodeBitMap other) {
-        bitMap.or(other.bitMap);
-    }
-
-    public void negate() {
-        grow();
-        bitMap.flip(0, nodeCount);
-    }
-
-    public boolean isNotNewMarked(Node node) {
-        return !isNew(node) && isMarked(node);
-    }
-
-    public boolean isNotNewNotMarked(Node node) {
-        return !isNew(node) && !isMarked(node);
-    }
-
-    public boolean isMarked(Node node) {
-        return bitMap.get(nodeIdAccessor.getNodeId(node));
-    }
-
     public boolean isNew(Node node) {
         return nodeIdAccessor.getNodeId(node) >= nodeCount;
     }
 
+    public boolean isMarked(Node node) {
+        assert check(node, false);
+        int id = nodeIdAccessor.getNodeId(node);
+        return (bits[id >> SHIFT] & (1L << id)) != 0;
+    }
+
+    public boolean isMarkedAndGrow(Node node) {
+        assert check(node, true);
+        int id = nodeIdAccessor.getNodeId(node);
+        checkGrow(id);
+        return (bits[id >> SHIFT] & (1L << id)) != 0;
+    }
+
     public void mark(Node node) {
-        if (autoGrow && isNew(node)) {
-            grow();
-        }
-        assert check(node);
-        bitMap.set(nodeIdAccessor.getNodeId(node));
+        assert check(node, false);
+        int id = nodeIdAccessor.getNodeId(node);
+        bits[id >> SHIFT] |= (1L << id);
+    }
+
+    public void markAndGrow(Node node) {
+        assert check(node, true);
+        int id = nodeIdAccessor.getNodeId(node);
+        checkGrow(id);
+        bits[id >> SHIFT] |= (1L << id);
     }
 
     public void clear(Node node) {
-        if (autoGrow && isNew(node)) {
-            return;
+        assert check(node, false);
+        int id = nodeIdAccessor.getNodeId(node);
+        bits[id >> SHIFT] &= ~(1L << id);
+    }
+
+    public void clearAndGrow(Node node) {
+        assert check(node, true);
+        int id = nodeIdAccessor.getNodeId(node);
+        checkGrow(id);
+        bits[id >> SHIFT] &= ~(1L << id);
+    }
+
+    private void checkGrow(int id) {
+        if (id >= nodeCount) {
+            if ((id >> SHIFT) >= bits.length) {
+                grow();
+            } else {
+                nodeCount = id + 1;
+            }
         }
-        assert check(node);
-        bitMap.clear(nodeIdAccessor.getNodeId(node));
     }
 
     public void clearAll() {
-        bitMap.clear();
+        Arrays.fill(bits, 0);
     }
 
     public void intersect(NodeBitMap other) {
         assert graph() == other.graph();
-        bitMap.and(other.bitMap);
-    }
-
-    public void grow(Node node) {
-        nodeCount = Math.max(nodeCount, nodeIdAccessor.getNodeId(node) + 1);
+        int commonLength = Math.min(bits.length, other.bits.length);
+        for (int i = commonLength; i < bits.length; i++) {
+            bits[i] = 0;
+        }
+        for (int i = 0; i < commonLength; i++) {
+            bits[i] &= other.bits[i];
+        }
     }
 
-    public void grow() {
+    private void grow() {
         nodeCount = Math.max(nodeCount, graph().nodeIdCount());
+        int newLength = Math.max((bits.length * 3 / 2) + 1, sizeForNodeCount(nodeCount));
+        bits = Arrays.copyOf(bits, newLength);
     }
 
-    private boolean check(Node node) {
+    private boolean check(Node node, boolean grow) {
         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 grow || !isNew(node) : "node was added to the graph after creating the node bitmap: " + node;
         assert node.isAlive() : "node is deleted!";
         return true;
     }
@@ -175,12 +192,8 @@
         return new MarkedNodeIterator(NodeBitMap.this, graph().getNodes().iterator());
     }
 
-    public int cardinality() {
-        return bitMap.cardinality();
-    }
-
     public NodeBitMap copy() {
-        return new NodeBitMap(graph(), autoGrow, nodeCount, (BitSet) bitMap.clone());
+        return new NodeBitMap(this);
     }
 
     @Override
@@ -190,7 +203,11 @@
 
     @Override
     public int count() {
-        return bitMap.cardinality();
+        int count = 0;
+        for (long l : bits) {
+            count += Long.bitCount(l);
+        }
+        return count;
     }
 
     @Override
diff -r cda2a7d1dcff -r 3f48e9a1016c graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeWorkList.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeWorkList.java	Wed May 28 17:19:41 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/NodeWorkList.java	Wed May 28 17:19:41 2014 +0200
@@ -34,6 +34,7 @@
     private Node lastPull;
     private Node lastChain;
 
+    // boolean addAgain
     public NodeWorkList(Graph graph) {
         this(graph, false, -1);
     }
@@ -65,22 +66,14 @@
 
     public void add(Node node) {
         if (node != null) {
-            if (visited.isNew(node)) {
-                visited.grow(node);
-                inQueue.grow(node);
-            }
-            if (!visited.isMarked(node)) {
+            if (!visited.isMarkedAndGrow(node)) {
                 addAgain(node);
             }
         }
     }
 
     public void addAgain(Node node) {
-        if (visited.isNew(node)) {
-            visited.grow(node);
-            inQueue.grow(node);
-        }
-        if (node != null && !inQueue.isMarked(node)) {
+        if (node != null && !inQueue.isMarkedAndGrow(node)) {
             if (lastPull == node) {
                 if (firstNoChange == null) {
                     firstNoChange = node;
@@ -93,8 +86,8 @@
             } else {
                 firstNoChange = null;
             }
-            visited.mark(node);
-            inQueue.mark(node);
+            visited.markAndGrow(node);
+            inQueue.markAndGrow(node);
             worklist.add(node);
         }
     }
@@ -121,7 +114,7 @@
     }
 
     public boolean isMarked(Node node) {
-        return visited.isMarked(node);
+        return visited.isMarkedAndGrow(node);
     }
 
     public boolean isNew(Node node) {
@@ -133,7 +126,7 @@
     }
 
     public boolean isInQueue(Node node) {
-        return !inQueue.isNew(node) && inQueue.isMarked(node);
+        return !inQueue.isNew(node) && inQueue.isMarkedAndGrow(node);
     }
 
     private class QueueConsumingIterator implements Iterator<Node> {
@@ -161,7 +154,7 @@
                 firstNoChange = null;
             }
             lastPull = node;
-            inQueue.clear(node);
+            inQueue.clearAndGrow(node);
             return node;
         }
 
diff -r cda2a7d1dcff -r 3f48e9a1016c graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/DistinctPredicatedProxyNodeIterator.java
--- a/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/DistinctPredicatedProxyNodeIterator.java	Wed May 28 17:19:41 2014 +0200
+++ b/graal/com.oracle.graal.graph/src/com/oracle/graal/graph/iterators/DistinctPredicatedProxyNodeIterator.java	Wed May 28 17:19:41 2014 +0200
@@ -50,7 +50,7 @@
             return true;
         }
         if (visited == null) {
-            visited = n.graph().createNodeBitMap(true);
+            visited = n.graph().createNodeBitMap();
         }
         boolean accept = !visited.isMarked(n);
         visited.mark(n);
diff -r cda2a7d1dcff -r 3f48e9a1016c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java	Wed May 28 17:19:41 2014 +0200
+++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragment.java	Wed May 28 17:19:41 2014 +0200
@@ -155,7 +155,7 @@
     }
 
     protected static NodeBitMap computeNodes(Graph graph, Iterable<BeginNode> blocks, Iterable<LoopExitNode> earlyExits) {
-        final NodeBitMap nodes = graph.createNodeBitMap(true);
+        final NodeBitMap nodes = graph.createNodeBitMap();
         for (BeginNode b : blocks) {
             if (b.isDeleted()) {
                 continue;
@@ -187,7 +187,7 @@
             }
         }
 
-        final NodeBitMap notloopNodes = graph.createNodeBitMap(true);
+        final NodeBitMap notloopNodes = graph.createNodeBitMap();
         for (BeginNode b : blocks) {
             if (b.isDeleted()) {
                 continue;
@@ -336,8 +336,8 @@
                  *
                  * We now update the original fragment's nodes accordingly:
                  */
-                state.applyToVirtual(node -> original.nodes.clear(node));
-                exitState.applyToVirtual(node -> original.nodes.mark(node));
+                state.applyToVirtual(node -> original.nodes.clearAndGrow(node));
+                exitState.applyToVirtual(node -> original.nodes.markAndGrow(node));
             }
             FrameState finalExitState = exitState;
 
diff -r cda2a7d1dcff -r 3f48e9a1016c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInside.java
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInside.java	Wed May 28 17:19:41 2014 +0200
+++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopFragmentInside.java	Wed May 28 17:19:41 2014 +0200
@@ -203,10 +203,10 @@
         for (LoopExitNode exit : exits()) {
             FrameState exitState = exit.stateAfter();
             if (exitState != null) {
-                exitState.applyToVirtual(v -> usagesToPatch.mark(v));
+                exitState.applyToVirtual(v -> usagesToPatch.markAndGrow(v));
             }
             for (ProxyNode proxy : exit.proxies()) {
-                usagesToPatch.mark(proxy);
+                usagesToPatch.markAndGrow(proxy);
             }
         }
 
@@ -232,7 +232,7 @@
             newPhis.add(newPhi);
             for (Node usage : phi.usages().snapshot()) {
                 // patch only usages that should use the new phi ie usages that were peeled
-                if (usagesToPatch.isMarked(usage)) {
+                if (usagesToPatch.isMarkedAndGrow(usage)) {
                     usage.replaceFirstInput(phi, newPhi);
                 }
             }
diff -r cda2a7d1dcff -r 3f48e9a1016c graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java
--- a/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java	Wed May 28 17:19:41 2014 +0200
+++ b/graal/com.oracle.graal.loop/src/com/oracle/graal/loop/LoopPolicies.java	Wed May 28 17:19:41 2014 +0200
@@ -72,7 +72,7 @@
         for (Node successor : controlSplit.successors()) {
             BeginNode branch = (BeginNode) successor;
             // this may count twice because of fall-through in switches
-            inBranchTotal += loop.nodesInLoopFrom(branch, postDom).cardinality();
+            inBranchTotal += loop.nodesInLoopFrom(branch, postDom).count();
             double probability = controlSplit.probability(branch);
             if (probability > maxProbability) {
                 maxProbability = probability;
diff -r cda2a7d1dcff -r 3f48e9a1016c graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java
--- a/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java	Wed May 28 17:19:41 2014 +0200
+++ b/graal/com.oracle.graal.phases.common/src/com/oracle/graal/phases/common/LoweringPhase.java	Wed May 28 17:19:41 2014 +0200
@@ -145,8 +145,7 @@
             } else {
                 GuardNode newGuard = graph.unique(new GuardNode(condition, guardAnchor, deoptReason, action, negated, Constant.NULL_OBJECT));
                 if (OptEliminateGuards.getValue()) {
-                    activeGuards.grow();
-                    activeGuards.mark(newGuard);
+                    activeGuards.markAndGrow(newGuard);
                 }
                 return newGuard;
             }
@@ -283,7 +282,7 @@
 
             if (parentAnchor == null && OptEliminateGuards.getValue()) {
                 for (GuardNode guard : anchor.asNode().usages().filter(GuardNode.class)) {
-                    if (activeGuards.contains(guard)) {
+                    if (activeGuards.isMarkedAndGrow(guard)) {
                         activeGuards.clear(guard);
                     }
                 }