001/*
002 * Copyright (c) 2011, 2011, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.graph;
024
025import java.util.*;
026
027public abstract class NodeWorkList implements Iterable<Node> {
028
029    protected final Queue<Node> worklist;
030
031    private NodeWorkList(Graph graph, boolean fill) {
032        if (fill) {
033            ArrayDeque<Node> deque = new ArrayDeque<>(graph.getNodeCount());
034            for (Node node : graph.getNodes()) {
035                deque.add(node);
036            }
037            worklist = deque;
038        } else {
039            worklist = new ArrayDeque<>();
040        }
041    }
042
043    public void addAll(Iterable<? extends Node> nodes) {
044        for (Node node : nodes) {
045            if (node.isAlive()) {
046                this.add(node);
047            }
048        }
049    }
050
051    public abstract void add(Node node);
052
053    public abstract boolean contains(Node node);
054
055    private abstract class QueueConsumingIterator implements Iterator<Node> {
056
057        protected void dropDeleted() {
058            while (!worklist.isEmpty() && worklist.peek().isDeleted()) {
059                worklist.remove();
060            }
061        }
062
063        @Override
064        public void remove() {
065            throw new UnsupportedOperationException();
066        }
067    }
068
069    public static final class IterativeNodeWorkList extends NodeWorkList {
070
071        private static final int EXPLICIT_BITMAP_THRESHOLD = 10;
072        protected NodeBitMap inQueue;
073
074        private int iterationLimit = Integer.MAX_VALUE;
075        private Node firstNoChange;
076        private Node lastPull;
077        private Node lastChain;
078
079        public IterativeNodeWorkList(Graph graph, boolean fill, int iterationLimitPerNode) {
080            super(graph, fill);
081            if (iterationLimitPerNode > 0) {
082                iterationLimit = iterationLimitPerNode * graph.getNodeCount();
083            }
084        }
085
086        @Override
087        public Iterator<Node> iterator() {
088            return new QueueConsumingIterator() {
089                @Override
090                public boolean hasNext() {
091                    dropDeleted();
092                    return iterationLimit > 0 && !worklist.isEmpty();
093                }
094
095                @Override
096                public Node next() {
097                    if (iterationLimit-- <= 0) {
098                        throw new NoSuchElementException();
099                    }
100                    dropDeleted();
101                    Node node = worklist.remove();
102                    assert updateInfiniteWork(node);
103                    if (inQueue != null) {
104                        inQueue.clearAndGrow(node);
105                    }
106                    return node;
107                }
108
109                private boolean updateInfiniteWork(Node node) {
110                    if (lastPull != lastChain) {
111                        firstNoChange = null;
112                    }
113                    lastPull = node;
114                    return true;
115                }
116            };
117        }
118
119        @Override
120        public void add(Node node) {
121            if (node != null) {
122                if (inQueue != null) {
123                    if (inQueue.isMarkedAndGrow(node)) {
124                        return;
125                    }
126                } else {
127                    if (worklist.size() > EXPLICIT_BITMAP_THRESHOLD) {
128                        inflateToBitMap(node.graph());
129                    } else {
130                        for (Node queuedNode : worklist) {
131                            if (queuedNode == node) {
132                                return;
133                            }
134                        }
135                    }
136                }
137                assert checkInfiniteWork(node) : "Readded " + node;
138                if (inQueue != null) {
139                    inQueue.markAndGrow(node);
140                }
141                worklist.add(node);
142            }
143        }
144
145        @Override
146        public boolean contains(Node node) {
147            if (inQueue != null) {
148                return inQueue.isMarked(node);
149            } else {
150                for (Node queuedNode : worklist) {
151                    if (queuedNode == node) {
152                        return true;
153                    }
154                }
155                return false;
156            }
157        }
158
159        private boolean checkInfiniteWork(Node node) {
160            if (lastPull == node && !node.hasNoUsages()) {
161                if (firstNoChange == null) {
162                    firstNoChange = node;
163                    lastChain = node;
164                } else if (node == firstNoChange) {
165                    return false;
166                } else {
167                    lastChain = node;
168                }
169            } else {
170                firstNoChange = null;
171            }
172            return true;
173        }
174
175        private void inflateToBitMap(Graph graph) {
176            assert inQueue == null;
177            inQueue = graph.createNodeBitMap();
178            for (Node queuedNode : worklist) {
179                if (queuedNode.isAlive()) {
180                    inQueue.mark(queuedNode);
181                }
182            }
183        }
184    }
185
186    public static final class SingletonNodeWorkList extends NodeWorkList {
187        protected final NodeBitMap visited;
188
189        public SingletonNodeWorkList(Graph graph) {
190            super(graph, false);
191            visited = graph.createNodeBitMap();
192        }
193
194        @Override
195        public void add(Node node) {
196            if (node != null) {
197                if (!visited.isMarkedAndGrow(node)) {
198                    visited.mark(node);
199                    worklist.add(node);
200                }
201            }
202        }
203
204        @Override
205        public boolean contains(Node node) {
206            return visited.isMarked(node);
207        }
208
209        @Override
210        public Iterator<Node> iterator() {
211            return new QueueConsumingIterator() {
212                @Override
213                public boolean hasNext() {
214                    dropDeleted();
215                    return !worklist.isEmpty();
216                }
217
218                @Override
219                public Node next() {
220                    dropDeleted();
221                    return worklist.remove();
222                }
223            };
224        }
225    }
226}