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 */
23package org.graalvm.compiler.graph;
24
25import java.util.Arrays;
26import java.util.Iterator;
27
28import org.graalvm.compiler.graph.iterators.NodeIterable;
29
30public final class NodeBitMap implements NodeIterable<Node> {
31    private static final int SHIFT = 6;
32
33    private long[] bits;
34    private int nodeCount;
35    private int counter;
36    private final Graph graph;
37
38    public NodeBitMap(Graph graph) {
39        this.nodeCount = graph.nodeIdCount();
40        this.bits = new long[sizeForNodeCount(nodeCount)];
41        this.graph = graph;
42    }
43
44    private static int sizeForNodeCount(int nodeCount) {
45        return (nodeCount + Long.SIZE - 1) >> SHIFT;
46    }
47
48    public int getCounter() {
49        return counter;
50    }
51
52    private NodeBitMap(NodeBitMap other) {
53        this.bits = other.bits.clone();
54        this.nodeCount = other.nodeCount;
55        this.graph = other.graph;
56    }
57
58    public Graph graph() {
59        return graph;
60    }
61
62    public boolean isNew(Node node) {
63        return node.id() >= nodeCount;
64    }
65
66    public boolean isMarked(Node node) {
67        assert check(node, false);
68        return isMarked(node.id());
69    }
70
71    public boolean checkAndMarkInc(Node node) {
72        if (!isMarked(node)) {
73            this.counter++;
74            this.mark(node);
75            return true;
76        } else {
77            return false;
78        }
79    }
80
81    public boolean isMarked(int id) {
82        return (bits[id >> SHIFT] & (1L << id)) != 0;
83    }
84
85    public boolean isMarkedAndGrow(Node node) {
86        assert check(node, true);
87        int id = node.id();
88        checkGrow(id);
89        return isMarked(id);
90    }
91
92    public void mark(Node node) {
93        assert check(node, false);
94        int id = node.id();
95        bits[id >> SHIFT] |= (1L << id);
96    }
97
98    public void markAndGrow(Node node) {
99        assert check(node, true);
100        int id = node.id();
101        checkGrow(id);
102        bits[id >> SHIFT] |= (1L << id);
103    }
104
105    public void clear(Node node) {
106        assert check(node, false);
107        int id = node.id();
108        bits[id >> SHIFT] &= ~(1L << id);
109    }
110
111    public void clearAndGrow(Node node) {
112        assert check(node, true);
113        int id = node.id();
114        checkGrow(id);
115        bits[id >> SHIFT] &= ~(1L << id);
116    }
117
118    private void checkGrow(int id) {
119        if (id >= nodeCount) {
120            if ((id >> SHIFT) >= bits.length) {
121                grow();
122            } else {
123                nodeCount = id + 1;
124            }
125        }
126    }
127
128    public void clearAll() {
129        Arrays.fill(bits, 0);
130    }
131
132    public void intersect(NodeBitMap other) {
133        assert graph() == other.graph();
134        int commonLength = Math.min(bits.length, other.bits.length);
135        for (int i = commonLength; i < bits.length; i++) {
136            bits[i] = 0;
137        }
138        for (int i = 0; i < commonLength; i++) {
139            bits[i] &= other.bits[i];
140        }
141    }
142
143    public void subtract(NodeBitMap other) {
144        assert graph() == other.graph();
145        int commonLength = Math.min(bits.length, other.bits.length);
146        for (int i = 0; i < commonLength; i++) {
147            bits[i] &= ~other.bits[i];
148        }
149    }
150
151    public void union(NodeBitMap other) {
152        assert graph() == other.graph();
153        grow();
154        if (bits.length < other.bits.length) {
155            bits = Arrays.copyOf(bits, other.bits.length);
156        }
157        for (int i = 0; i < bits.length; i++) {
158            bits[i] |= other.bits[i];
159        }
160    }
161
162    public void grow() {
163        nodeCount = Math.max(nodeCount, graph().nodeIdCount());
164        int newLength = sizeForNodeCount(nodeCount);
165        if (newLength > bits.length) {
166            newLength = Math.max(newLength, (bits.length * 3 / 2) + 1);
167            bits = Arrays.copyOf(bits, newLength);
168        }
169    }
170
171    private boolean check(Node node, boolean grow) {
172        assert node.graph() == graph() : "this node is not part of the graph: " + node;
173        assert grow || !isNew(node) : "node was added to the graph after creating the node bitmap: " + node;
174        assert node.isAlive() : "node is deleted!" + node;
175        return true;
176    }
177
178    public <T extends Node> void markAll(Iterable<T> nodes) {
179        for (Node node : nodes) {
180            mark(node);
181        }
182    }
183
184    private static class MarkedNodeIterator implements Iterator<Node> {
185
186        private final NodeBitMap visited;
187        private Iterator<Node> nodes;
188        private Node nextNode;
189
190        MarkedNodeIterator(NodeBitMap visited, Iterator<Node> nodes) {
191            this.visited = visited;
192            this.nodes = nodes;
193            forward();
194        }
195
196        private void forward() {
197            do {
198                if (!nodes.hasNext()) {
199                    nextNode = null;
200                    return;
201                }
202                nextNode = nodes.next();
203                if (visited.isNew(nextNode)) {
204                    nextNode = null;
205                    return;
206                }
207            } while (!visited.isMarked(nextNode));
208        }
209
210        @Override
211        public boolean hasNext() {
212            return nextNode != null;
213        }
214
215        @Override
216        public Node next() {
217            try {
218                return nextNode;
219            } finally {
220                forward();
221            }
222        }
223
224        @Override
225        public void remove() {
226            throw new UnsupportedOperationException();
227        }
228
229    }
230
231    @Override
232    public Iterator<Node> iterator() {
233        return new MarkedNodeIterator(NodeBitMap.this, graph().getNodes().iterator());
234    }
235
236    public NodeBitMap copy() {
237        return new NodeBitMap(this);
238    }
239
240    @Override
241    public int count() {
242        int count = 0;
243        for (long l : bits) {
244            count += Long.bitCount(l);
245        }
246        return count;
247    }
248
249    @Override
250    public boolean contains(Node node) {
251        return isMarked(node);
252    }
253
254    @Override
255    public String toString() {
256        return snapshot().toString();
257    }
258}
259