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.debug.DebugContext;
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 EXPLICIT_BITMAP_THRESHOLD = 10;
76 protected NodeBitMap inQueue;
77
78 private final DebugContext debug;
79 private int iterationLimit;
80 private Node firstNoChange;
81 private Node lastPull;
82 private Node lastChain;
83
84 public IterativeNodeWorkList(Graph graph, boolean fill, int iterationLimitPerNode) {
85 super(graph, fill);
86 debug = graph.getDebug();
87 assert iterationLimitPerNode > 0;
88 long limit = (long) iterationLimitPerNode * graph.getNodeCount();
89 iterationLimit = (int) Long.min(Integer.MAX_VALUE, limit);
90 }
91
92 @Override
93 public Iterator<Node> iterator() {
94 return new QueueConsumingIterator() {
95 @Override
96 public boolean hasNext() {
97 dropDeleted();
98 if (iterationLimit <= 0) {
99 debug.log(DebugContext.INFO_LEVEL, "Exceeded iteration limit in IterativeNodeWorkList");
100 return false;
101 }
102 return !worklist.isEmpty();
103 }
104
105 @Override
106 public Node next() {
107 if (iterationLimit-- <= 0) {
108 throw new NoSuchElementException();
109 }
110 dropDeleted();
111 Node node = worklist.remove();
112 assert updateInfiniteWork(node);
113 if (inQueue != null) {
114 inQueue.clearAndGrow(node);
115 }
116 return node;
117 }
118
119 private boolean updateInfiniteWork(Node node) {
120 if (lastPull != lastChain) {
121 firstNoChange = null;
122 }
123 lastPull = node;
124 return true;
125 }
126 };
127 }
128
129 @Override
130 public void add(Node node) {
131 if (node != null) {
132 if (inQueue == null && worklist.size() > EXPLICIT_BITMAP_THRESHOLD) {
133 inflateToBitMap(node.graph());
134 }
135
136 if (inQueue != null) {
137 if (inQueue.isMarkedAndGrow(node)) {
138 return;
139 }
140 } else {
141 for (Node queuedNode : worklist) {
142 if (queuedNode == node) {
143 return;
144 }
145 }
146 }
147 assert checkInfiniteWork(node) : "Re-added " + node;
148 if (inQueue != null) {
149 inQueue.markAndGrow(node);
150 }
151 worklist.add(node);
152 }
153 }
154
155 @Override
156 public boolean contains(Node node) {
157 if (inQueue != null) {
158 return inQueue.isMarked(node);
159 } else {
160 for (Node queuedNode : worklist) {
161 if (queuedNode == node) {
162 return true;
163 }
164 }
165 return false;
166 }
167 }
168
169 private boolean checkInfiniteWork(Node node) {
170 if (lastPull == node && !node.hasNoUsages()) {
171 if (firstNoChange == null) {
172 firstNoChange = node;
173 lastChain = node;
174 } else if (node == firstNoChange) {
175 return false;
176 } else {
177 lastChain = node;
178 }
179 } else {
180 firstNoChange = null;
181 }
182 return true;
183 }
184
185 private void inflateToBitMap(Graph graph) {
186 assert inQueue == null;
187 inQueue = graph.createNodeBitMap();
188 for (Node queuedNode : worklist) {
189 if (queuedNode.isAlive()) {
190 inQueue.mark(queuedNode);
191 }
192 }
193 }
194 }
195
196 public static final class SingletonNodeWorkList extends NodeWorkList {
197 protected final NodeBitMap visited;
198
199 public SingletonNodeWorkList(Graph graph) {
200 super(graph, false);
201 visited = graph.createNodeBitMap();
202 }
203
204 @Override
205 public void add(Node node) {
206 if (node != null) {
207 if (!visited.isMarkedAndGrow(node)) {
208 visited.mark(node);
209 worklist.add(node);
210 }
211 }
212 }
213
214 @Override
215 public boolean contains(Node node) {
216 return visited.isMarked(node);
217 }
218
219 @Override
220 public Iterator<Node> iterator() {
221 return new QueueConsumingIterator() {
222 @Override
223 public boolean hasNext() {
224 dropDeleted();
225 return !worklist.isEmpty();
226 }
227
228 @Override
229 public Node next() {
230 dropDeleted();
231 return worklist.remove();
232 }
233 };
234 }
235 }
236 }