1 /*
   2  * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 package org.graalvm.compiler.graph;
  24 
  25 import java.util.Arrays;
  26 import java.util.ConcurrentModificationException;
  27 import java.util.Iterator;
  28 import java.util.NoSuchElementException;
  29 
  30 import org.graalvm.compiler.graph.iterators.NodeIterable;
  31 
  32 public final class NodeBitMap extends NodeIdAccessor implements NodeIterable<Node> {
  33     private static final int SHIFT = 6;
  34 
  35     private long[] bits;
  36     private int nodeCount;
  37     private int counter;
  38 
  39     public NodeBitMap(Graph graph) {
  40         super(graph);
  41         this.nodeCount = graph.nodeIdCount();
  42         this.bits = new long[sizeForNodeCount(nodeCount)];
  43     }
  44 
  45     private static int sizeForNodeCount(int nodeCount) {
  46         return (nodeCount + Long.SIZE - 1) >> SHIFT;
  47     }
  48 
  49     public int getCounter() {
  50         return counter;
  51     }
  52 
  53     private NodeBitMap(NodeBitMap other) {
  54         super(other.graph);
  55         this.bits = other.bits.clone();
  56         this.nodeCount = other.nodeCount;
  57     }
  58 
  59     public Graph graph() {
  60         return graph;
  61     }
  62 
  63     public boolean isNew(Node node) {
  64         return getNodeId(node) >= nodeCount;
  65     }
  66 
  67     public boolean isMarked(Node node) {
  68         assert check(node, false);
  69         return isMarked(getNodeId(node));
  70     }
  71 
  72     public boolean checkAndMarkInc(Node node) {
  73         if (!isMarked(node)) {
  74             this.counter++;
  75             this.mark(node);
  76             return true;
  77         } else {
  78             return false;
  79         }
  80     }
  81 
  82     public boolean isMarked(int id) {
  83         return (bits[id >> SHIFT] & (1L << id)) != 0;
  84     }
  85 
  86     public boolean isMarkedAndGrow(Node node) {
  87         assert check(node, true);
  88         int id = getNodeId(node);
  89         checkGrow(id);
  90         return isMarked(id);
  91     }
  92 
  93     public void mark(Node node) {
  94         assert check(node, false);
  95         int id = getNodeId(node);
  96         bits[id >> SHIFT] |= (1L << id);
  97     }
  98 
  99     public void markAndGrow(Node node) {
 100         assert check(node, true);
 101         int id = getNodeId(node);
 102         checkGrow(id);
 103         bits[id >> SHIFT] |= (1L << id);
 104     }
 105 
 106     public void clear(Node node) {
 107         assert check(node, false);
 108         int id = getNodeId(node);
 109         bits[id >> SHIFT] &= ~(1L << id);
 110     }
 111 
 112     public void clearAndGrow(Node node) {
 113         assert check(node, true);
 114         int id = getNodeId(node);
 115         checkGrow(id);
 116         bits[id >> SHIFT] &= ~(1L << id);
 117     }
 118 
 119     private void checkGrow(int id) {
 120         if (id >= nodeCount) {
 121             if ((id >> SHIFT) >= bits.length) {
 122                 grow();
 123             } else {
 124                 nodeCount = id + 1;
 125             }
 126         }
 127     }
 128 
 129     public void clearAll() {
 130         Arrays.fill(bits, 0);
 131     }
 132 
 133     public void intersect(NodeBitMap other) {
 134         assert graph() == other.graph();
 135         int commonLength = Math.min(bits.length, other.bits.length);
 136         for (int i = commonLength; i < bits.length; i++) {
 137             bits[i] = 0;
 138         }
 139         for (int i = 0; i < commonLength; i++) {
 140             bits[i] &= other.bits[i];
 141         }
 142     }
 143 
 144     public void subtract(NodeBitMap other) {
 145         assert graph() == other.graph();
 146         int commonLength = Math.min(bits.length, other.bits.length);
 147         for (int i = 0; i < commonLength; i++) {
 148             bits[i] &= ~other.bits[i];
 149         }
 150     }
 151 
 152     public void union(NodeBitMap other) {
 153         assert graph() == other.graph();
 154         grow();
 155         if (bits.length < other.bits.length) {
 156             bits = Arrays.copyOf(bits, other.bits.length);
 157         }
 158         for (int i = 0; i < Math.min(bits.length, other.bits.length); i++) {
 159             bits[i] |= other.bits[i];
 160         }
 161     }
 162 
 163     public void grow() {
 164         nodeCount = Math.max(nodeCount, graph().nodeIdCount());
 165         int newLength = sizeForNodeCount(nodeCount);
 166         if (newLength > bits.length) {
 167             newLength = Math.max(newLength, (bits.length * 3 / 2) + 1);
 168             bits = Arrays.copyOf(bits, newLength);
 169         }
 170     }
 171 
 172     private boolean check(Node node, boolean grow) {
 173         assert node.graph() == graph() : "this node is not part of the graph: " + node;
 174         assert grow || !isNew(node) : "node was added to the graph after creating the node bitmap: " + node;
 175         assert node.isAlive() : "node is deleted!" + node;
 176         return true;
 177     }
 178 
 179     public <T extends Node> void markAll(Iterable<T> nodes) {
 180         for (Node node : nodes) {
 181             mark(node);
 182         }
 183     }
 184 
 185     protected Node nextMarkedNode(int fromNodeId) {
 186         assert fromNodeId >= 0;
 187         int wordIndex = fromNodeId >> SHIFT;
 188         int wordsInUse = bits.length;
 189         if (wordIndex < wordsInUse) {
 190             long word = getPartOfWord(bits[wordIndex], fromNodeId);
 191             while (true) {
 192                 while (word != 0) {
 193                     int bitIndex = Long.numberOfTrailingZeros(word);
 194                     int nodeId = wordIndex * Long.SIZE + bitIndex;
 195                     Node result = graph.getNode(nodeId);
 196                     if (result == null) {
 197                         // node was deleted -> clear the bit and continue searching
 198                         bits[wordIndex] = bits[wordIndex] & ~(1L << bitIndex);
 199                         int nextNodeId = nodeId + 1;
 200                         if ((nextNodeId & (Long.SIZE - 1)) == 0) {
 201                             // we reached the end of this word
 202                             break;
 203                         } else {
 204                             word = getPartOfWord(word, nextNodeId);
 205                         }
 206                     } else {
 207                         return result;
 208                     }
 209                 }
 210                 if (++wordIndex == wordsInUse) {
 211                     break;
 212                 }
 213                 word = bits[wordIndex];
 214             }
 215         }
 216         return null;
 217     }
 218 
 219     private static long getPartOfWord(long word, int firstNodeIdToInclude) {
 220         return word & (0xFFFFFFFFFFFFFFFFL << firstNodeIdToInclude);
 221     }
 222 
 223     /**
 224      * This iterator only returns nodes that are marked in the {@link NodeBitMap} and are alive in
 225      * the corresponding {@link Graph}.
 226      */
 227     private class MarkedNodeIterator implements Iterator<Node> {
 228         private int currentNodeId;
 229         private Node currentNode;
 230 
 231         MarkedNodeIterator() {
 232             currentNodeId = -1;
 233             forward();
 234         }
 235 
 236         private void forward() {
 237             assert currentNode == null;
 238             currentNode = NodeBitMap.this.nextMarkedNode(currentNodeId + 1);
 239             if (currentNode != null) {
 240                 assert currentNode.isAlive();
 241                 currentNodeId = getNodeId(currentNode);
 242             } else {
 243                 currentNodeId = -1;
 244             }
 245         }
 246 
 247         @Override
 248         public boolean hasNext() {
 249             if (currentNode == null && currentNodeId >= 0) {
 250                 forward();
 251             }
 252             return currentNodeId >= 0;
 253         }
 254 
 255         @Override
 256         public Node next() {
 257             if (!hasNext()) {
 258                 throw new NoSuchElementException();
 259             }
 260             if (!currentNode.isAlive()) {
 261                 throw new ConcurrentModificationException("NodeBitMap was modified between the calls to hasNext() and next()");
 262             }
 263 
 264             Node result = currentNode;
 265             currentNode = null;
 266             return result;
 267         }
 268 
 269         @Override
 270         public void remove() {
 271             throw new UnsupportedOperationException();
 272         }
 273 
 274     }
 275 
 276     @Override
 277     public Iterator<Node> iterator() {
 278         return new MarkedNodeIterator();
 279     }
 280 
 281     public NodeBitMap copy() {
 282         return new NodeBitMap(this);
 283     }
 284 
 285     @Override
 286     public int count() {
 287         int count = 0;
 288         for (long l : bits) {
 289             count += Long.bitCount(l);
 290         }
 291         return count;
 292     }
 293 
 294     @Override
 295     public boolean contains(Node node) {
 296         return isMarked(node);
 297     }
 298 
 299     @Override
 300     public String toString() {
 301         return snapshot().toString();
 302     }
 303 }