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