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