1 /*
   2  * Copyright (c) 2011, 2018, 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 
  24 
  25 package org.graalvm.compiler.graph;
  26 
  27 import java.util.Arrays;
  28 import java.util.ConcurrentModificationException;
  29 import java.util.Iterator;
  30 import java.util.NoSuchElementException;
  31 
  32 import org.graalvm.compiler.graph.iterators.NodeIterable;
  33 
  34 public final class NodeBitMap extends NodeIdAccessor implements NodeIterable<Node> {
  35     private static final int SHIFT = 6;
  36 
  37     private long[] bits;
  38     private int nodeCount;
  39     private int counter;
  40 
  41     public NodeBitMap(Graph graph) {
  42         super(graph);
  43         this.nodeCount = graph.nodeIdCount();
  44         this.bits = new long[sizeForNodeCount(nodeCount)];
  45     }
  46 
  47     private static int sizeForNodeCount(int nodeCount) {
  48         return (nodeCount + Long.SIZE - 1) >> SHIFT;
  49     }
  50 
  51     public int getCounter() {
  52         return counter;
  53     }
  54 
  55     private NodeBitMap(NodeBitMap other) {
  56         super(other.graph);
  57         this.bits = other.bits.clone();
  58         this.nodeCount = other.nodeCount;
  59     }
  60 
  61     public Graph graph() {
  62         return graph;
  63     }
  64 
  65     public boolean isNew(Node node) {
  66         return getNodeId(node) >= nodeCount;
  67     }
  68 
  69     public boolean isMarked(Node node) {
  70         assert check(node, false);
  71         return isMarked(getNodeId(node));
  72     }
  73 
  74     public boolean checkAndMarkInc(Node node) {
  75         if (!isMarked(node)) {
  76             this.counter++;
  77             this.mark(node);
  78             return true;
  79         } else {
  80             return false;
  81         }
  82     }
  83 
  84     public boolean isMarked(int id) {
  85         return (bits[id >> SHIFT] & (1L << id)) != 0;
  86     }
  87 
  88     public boolean isMarkedAndGrow(Node node) {
  89         assert check(node, true);
  90         int id = getNodeId(node);
  91         checkGrow(id);
  92         return isMarked(id);
  93     }
  94 
  95     public void mark(Node node) {
  96         assert check(node, false);
  97         int id = getNodeId(node);
  98         bits[id >> SHIFT] |= (1L << id);
  99     }
 100 
 101     public void markAndGrow(Node node) {
 102         assert check(node, true);
 103         int id = getNodeId(node);
 104         checkGrow(id);
 105         bits[id >> SHIFT] |= (1L << id);
 106     }
 107 
 108     public void clear(Node node) {
 109         assert check(node, false);
 110         int id = getNodeId(node);
 111         bits[id >> SHIFT] &= ~(1L << id);
 112     }
 113 
 114     public void clearAndGrow(Node node) {
 115         assert check(node, true);
 116         int id = getNodeId(node);
 117         checkGrow(id);
 118         bits[id >> SHIFT] &= ~(1L << id);
 119     }
 120 
 121     private void checkGrow(int id) {
 122         if (id >= nodeCount) {
 123             if ((id >> SHIFT) >= bits.length) {
 124                 grow();
 125             } else {
 126                 nodeCount = id + 1;
 127             }
 128         }
 129     }
 130 
 131     public void clearAll() {
 132         Arrays.fill(bits, 0);
 133     }
 134 
 135     public void intersect(NodeBitMap other) {
 136         assert graph() == other.graph();
 137         int commonLength = Math.min(bits.length, other.bits.length);
 138         for (int i = commonLength; i < bits.length; i++) {
 139             bits[i] = 0;
 140         }
 141         for (int i = 0; i < commonLength; i++) {
 142             bits[i] &= other.bits[i];
 143         }
 144     }
 145 
 146     public void subtract(NodeBitMap other) {
 147         assert graph() == other.graph();
 148         int commonLength = Math.min(bits.length, other.bits.length);
 149         for (int i = 0; i < commonLength; i++) {
 150             bits[i] &= ~other.bits[i];
 151         }
 152     }
 153 
 154     public void union(NodeBitMap other) {
 155         assert graph() == other.graph();
 156         grow();
 157         if (bits.length < other.bits.length) {
 158             bits = Arrays.copyOf(bits, other.bits.length);
 159         }
 160         for (int i = 0; i < Math.min(bits.length, other.bits.length); i++) {
 161             bits[i] |= other.bits[i];
 162         }
 163     }
 164 
 165     public void invert() {
 166         for (int i = 0; i < bits.length; i++) {
 167             bits[i] = ~bits[i];
 168         }
 169     }
 170 
 171     public void grow() {
 172         nodeCount = Math.max(nodeCount, graph().nodeIdCount());
 173         int newLength = sizeForNodeCount(nodeCount);
 174         if (newLength > bits.length) {
 175             newLength = Math.max(newLength, (bits.length * 3 / 2) + 1);
 176             bits = Arrays.copyOf(bits, newLength);
 177         }
 178     }
 179 
 180     private boolean check(Node node, boolean grow) {
 181         assert node.graph() == graph() : "this node is not part of the graph: " + node;
 182         assert grow || !isNew(node) : "node was added to the graph after creating the node bitmap: " + node;
 183         assert node.isAlive() : "node is deleted!" + node;
 184         return true;
 185     }
 186 
 187     public <T extends Node> void markAll(Iterable<T> nodes) {
 188         for (Node node : nodes) {
 189             mark(node);
 190         }
 191     }
 192 
 193     protected Node nextMarkedNode(int fromNodeId) {
 194         assert fromNodeId >= 0;
 195         int wordIndex = fromNodeId >> SHIFT;
 196         int wordsInUse = bits.length;
 197         if (wordIndex < wordsInUse) {
 198             long word = getPartOfWord(bits[wordIndex], fromNodeId);
 199             while (true) {
 200                 while (word != 0) {
 201                     int bitIndex = Long.numberOfTrailingZeros(word);
 202                     int nodeId = wordIndex * Long.SIZE + bitIndex;
 203                     Node result = graph.getNode(nodeId);
 204                     if (result == null) {
 205                         // node was deleted -> clear the bit and continue searching
 206                         bits[wordIndex] = bits[wordIndex] & ~(1L << bitIndex);
 207                         int nextNodeId = nodeId + 1;
 208                         if ((nextNodeId & (Long.SIZE - 1)) == 0) {
 209                             // we reached the end of this word
 210                             break;
 211                         } else {
 212                             word = getPartOfWord(word, nextNodeId);
 213                         }
 214                     } else {
 215                         return result;
 216                     }
 217                 }
 218                 if (++wordIndex == wordsInUse) {
 219                     break;
 220                 }
 221                 word = bits[wordIndex];
 222             }
 223         }
 224         return null;
 225     }
 226 
 227     private static long getPartOfWord(long word, int firstNodeIdToInclude) {
 228         return word & (0xFFFFFFFFFFFFFFFFL << firstNodeIdToInclude);
 229     }
 230 
 231     /**
 232      * This iterator only returns nodes that are marked in the {@link NodeBitMap} and are alive in
 233      * the corresponding {@link Graph}.
 234      */
 235     private class MarkedNodeIterator implements Iterator<Node> {
 236         private int currentNodeId;
 237         private Node currentNode;
 238 
 239         MarkedNodeIterator() {
 240             currentNodeId = -1;
 241             forward();
 242         }
 243 
 244         private void forward() {
 245             assert currentNode == null;
 246             currentNode = NodeBitMap.this.nextMarkedNode(currentNodeId + 1);
 247             if (currentNode != null) {
 248                 assert currentNode.isAlive();
 249                 currentNodeId = getNodeId(currentNode);
 250             } else {
 251                 currentNodeId = -1;
 252             }
 253         }
 254 
 255         @Override
 256         public boolean hasNext() {
 257             if (currentNode == null && currentNodeId >= 0) {
 258                 forward();
 259             }
 260             return currentNodeId >= 0;
 261         }
 262 
 263         @Override
 264         public Node next() {
 265             if (!hasNext()) {
 266                 throw new NoSuchElementException();
 267             }
 268             if (!currentNode.isAlive()) {
 269                 throw new ConcurrentModificationException("NodeBitMap was modified between the calls to hasNext() and next()");
 270             }
 271 
 272             Node result = currentNode;
 273             currentNode = null;
 274             return result;
 275         }
 276 
 277         @Override
 278         public void remove() {
 279             throw new UnsupportedOperationException();
 280         }
 281 
 282     }
 283 
 284     @Override
 285     public Iterator<Node> iterator() {
 286         return new MarkedNodeIterator();
 287     }
 288 
 289     public NodeBitMap copy() {
 290         return new NodeBitMap(this);
 291     }
 292 
 293     @Override
 294     public int count() {
 295         int count = 0;
 296         for (long l : bits) {
 297             count += Long.bitCount(l);
 298         }
 299         return count;
 300     }
 301 
 302     @Override
 303     public boolean contains(Node node) {
 304         return isMarked(node);
 305     }
 306 
 307     @Override
 308     public String toString() {
 309         return snapshot().toString();
 310     }
 311 }