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.ArrayDeque;
26 import java.util.Iterator;
27 import java.util.NoSuchElementException;
28 import java.util.Queue;
29
30 public abstract class NodeWorkList implements Iterable<Node> {
31
32 protected final Queue<Node> worklist;
33
34 private NodeWorkList(Graph graph, boolean fill) {
35 if (fill) {
36 ArrayDeque<Node> deque = new ArrayDeque<>(graph.getNodeCount());
37 for (Node node : graph.getNodes()) {
38 deque.add(node);
39 }
40 worklist = deque;
41 } else {
42 worklist = new ArrayDeque<>();
43 }
44 }
45
46 public void addAll(Iterable<? extends Node> nodes) {
47 for (Node node : nodes) {
48 if (node.isAlive()) {
49 this.add(node);
50 }
51 }
52 }
53
54 public abstract void add(Node node);
55
56 public abstract boolean contains(Node node);
57
58 private abstract class QueueConsumingIterator implements Iterator<Node> {
59
60 protected void dropDeleted() {
61 while (!worklist.isEmpty() && worklist.peek().isDeleted()) {
62 worklist.remove();
63 }
64 }
65
66 @Override
67 public void remove() {
68 throw new UnsupportedOperationException();
69 }
70 }
71
72 public static final class IterativeNodeWorkList extends NodeWorkList {
73
74 private static final int EXPLICIT_BITMAP_THRESHOLD = 10;
75 protected NodeBitMap inQueue;
76
77 private int iterationLimit = Integer.MAX_VALUE;
78 private Node firstNoChange;
79 private Node lastPull;
80 private Node lastChain;
81
82 public IterativeNodeWorkList(Graph graph, boolean fill, int iterationLimitPerNode) {
83 super(graph, fill);
84 if (iterationLimitPerNode > 0) {
85 iterationLimit = iterationLimitPerNode * graph.getNodeCount();
86 }
87 }
88
89 @Override
90 public Iterator<Node> iterator() {
91 return new QueueConsumingIterator() {
92 @Override
93 public boolean hasNext() {
94 dropDeleted();
95 return iterationLimit > 0 && !worklist.isEmpty();
96 }
97
98 @Override
99 public Node next() {
100 if (iterationLimit-- <= 0) {
101 throw new NoSuchElementException();
102 }
103 dropDeleted();
104 Node node = worklist.remove();
105 assert updateInfiniteWork(node);
106 if (inQueue != null) {
107 inQueue.clearAndGrow(node);
108 }
109 return node;
110 }
111
112 private boolean updateInfiniteWork(Node node) {
113 if (lastPull != lastChain) {
114 firstNoChange = null;
115 }
116 lastPull = node;
117 return true;
118 }
119 };
120 }
121
122 @Override
123 public void add(Node node) {
124 if (node != null) {
125 if (inQueue == null && worklist.size() > EXPLICIT_BITMAP_THRESHOLD) {
126 inflateToBitMap(node.graph());
127 }
128
129 if (inQueue != null) {
130 if (inQueue.isMarkedAndGrow(node)) {
131 return;
132 }
133 } else {
134 for (Node queuedNode : worklist) {
135 if (queuedNode == node) {
136 return;
137 }
138 }
139 }
140 assert checkInfiniteWork(node) : "Readded " + node;
141 if (inQueue != null) {
142 inQueue.markAndGrow(node);
143 }
144 worklist.add(node);
145 }
146 }
147
148 @Override
149 public boolean contains(Node node) {
150 if (inQueue != null) {
151 return inQueue.isMarked(node);
152 } else {
153 for (Node queuedNode : worklist) {
154 if (queuedNode == node) {
155 return true;
156 }
157 }
158 return false;
159 }
160 }
161
162 private boolean checkInfiniteWork(Node node) {
163 if (lastPull == node && !node.hasNoUsages()) {
164 if (firstNoChange == null) {
165 firstNoChange = node;
166 lastChain = node;
167 } else if (node == firstNoChange) {
168 return false;
169 } else {
170 lastChain = node;
171 }
172 } else {
173 firstNoChange = null;
174 }
175 return true;
176 }
177
178 private void inflateToBitMap(Graph graph) {
179 assert inQueue == null;
180 inQueue = graph.createNodeBitMap();
181 for (Node queuedNode : worklist) {
182 if (queuedNode.isAlive()) {
183 inQueue.mark(queuedNode);
184 }
185 }
186 }
187 }
188
189 public static final class SingletonNodeWorkList extends NodeWorkList {
190 protected final NodeBitMap visited;
191
192 public SingletonNodeWorkList(Graph graph) {
193 super(graph, false);
194 visited = graph.createNodeBitMap();
195 }
196
197 @Override
198 public void add(Node node) {
199 if (node != null) {
200 if (!visited.isMarkedAndGrow(node)) {
201 visited.mark(node);
202 worklist.add(node);
203 }
204 }
205 }
206
207 @Override
208 public boolean contains(Node node) {
209 return visited.isMarked(node);
210 }
211
212 @Override
213 public Iterator<Node> iterator() {
214 return new QueueConsumingIterator() {
215 @Override
216 public boolean hasNext() {
217 dropDeleted();
218 return !worklist.isEmpty();
219 }
220
221 @Override
222 public Node next() {
223 dropDeleted();
224 return worklist.remove();
225 }
226 };
227 }
228 }
229 }