1 /*
   2  * Copyright (c) 2014, 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 static org.graalvm.compiler.graph.Graph.isModificationCountsEnabled;
  28 import static org.graalvm.compiler.graph.Node.NOT_ITERABLE;
  29 import static org.graalvm.compiler.graph.UnsafeAccess.UNSAFE;
  30 
  31 import java.util.ArrayList;
  32 import java.util.Iterator;
  33 
  34 import org.graalvm.compiler.core.common.Fields;
  35 import org.graalvm.compiler.core.common.FieldsScanner;
  36 import org.graalvm.compiler.graph.NodeClass.EdgeInfo;
  37 
  38 /**
  39  * Describes {@link Node} fields representing the set of inputs for the node or the set of the
  40  * node's successors.
  41  */
  42 public abstract class Edges extends Fields {
  43 
  44     /**
  45      * Constants denoting whether a set of edges are inputs or successors.
  46      */
  47     public enum Type {
  48         Inputs,
  49         Successors;
  50     }
  51 
  52     private final int directCount;
  53     private final Type type;
  54 
  55     public Edges(Type type, int directCount, ArrayList<? extends FieldsScanner.FieldInfo> edges) {
  56         super(edges);
  57         this.type = type;
  58         this.directCount = directCount;
  59     }
  60 
  61     public static void translateInto(Edges edges, ArrayList<EdgeInfo> infos) {
  62         for (int index = 0; index < edges.getCount(); index++) {
  63             infos.add(new EdgeInfo(edges.offsets[index], edges.getName(index), edges.getType(index), edges.getDeclaringClass(index)));
  64         }
  65     }
  66 
  67     public static Node getNodeUnsafe(Node node, long offset) {
  68         return (Node) UNSAFE.getObject(node, offset);
  69     }
  70 
  71     @SuppressWarnings("unchecked")
  72     public static NodeList<Node> getNodeListUnsafe(Node node, long offset) {
  73         return (NodeList<Node>) UNSAFE.getObject(node, offset);
  74     }
  75 
  76     public static void putNodeUnsafe(Node node, long offset, Node value) {
  77         UNSAFE.putObject(node, offset, value);
  78     }
  79 
  80     public static void putNodeListUnsafe(Node node, long offset, NodeList<?> value) {
  81         UNSAFE.putObject(node, offset, value);
  82     }
  83 
  84     /**
  85      * Get the number of direct edges represented by this object. A direct edge goes directly to
  86      * another {@link Node}. An indirect edge goes via a {@link NodeList}.
  87      */
  88     public int getDirectCount() {
  89         return directCount;
  90     }
  91 
  92     /**
  93      * Gets the {@link Node} at the end point of a {@linkplain #getDirectCount() direct} edge.
  94      *
  95      * @param node one end point of the edge
  96      * @param index the index of a non-list the edge (must be less than {@link #getDirectCount()})
  97      * @return the Node at the other edge of the requested edge
  98      */
  99     public static Node getNode(Node node, long[] offsets, int index) {
 100         return getNodeUnsafe(node, offsets[index]);
 101     }
 102 
 103     /**
 104      * Gets the {@link NodeList} at the end point of a {@linkplain #getDirectCount() direct} edge.
 105      *
 106      * @param node one end point of the edge
 107      * @param index the index of a non-list the edge (must be equal to or greater than
 108      *            {@link #getDirectCount()})
 109      * @return the {@link NodeList} at the other edge of the requested edge
 110      */
 111     public static NodeList<Node> getNodeList(Node node, long[] offsets, int index) {
 112         return getNodeListUnsafe(node, offsets[index]);
 113     }
 114 
 115     /**
 116      * Clear edges in a given node. This is accomplished by setting {@linkplain #getDirectCount()
 117      * direct} edges to null and replacing the lists containing indirect edges with new lists. The
 118      * latter is important so that this method can be used to clear the edges of cloned nodes.
 119      *
 120      * @param node the node whose edges are to be cleared
 121      */
 122     public void clear(Node node) {
 123         final long[] curOffsets = this.offsets;
 124         final Type curType = this.type;
 125         int index = 0;
 126         int curDirectCount = getDirectCount();
 127         while (index < curDirectCount) {
 128             initializeNode(node, index++, null);
 129         }
 130         int curCount = getCount();
 131         while (index < curCount) {
 132             NodeList<Node> list = getNodeList(node, curOffsets, index);
 133             if (list != null) {
 134                 int size = list.initialSize;
 135                 NodeList<Node> newList = curType == Edges.Type.Inputs ? new NodeInputList<>(node, size) : new NodeSuccessorList<>(node, size);
 136 
 137                 // replacing with a new list object is the expected behavior!
 138                 initializeList(node, index, newList);
 139             }
 140             index++;
 141         }
 142     }
 143 
 144     /**
 145      * Initializes the list edges in a given node based on the size of the list edges in a prototype
 146      * node.
 147      *
 148      * @param node the node whose list edges are to be initialized
 149      * @param prototype the node whose list edge sizes are used when creating new edge lists
 150      */
 151     public void initializeLists(Node node, Node prototype) {
 152         int index = getDirectCount();
 153         final long[] curOffsets = this.offsets;
 154         final Edges.Type curType = this.type;
 155         while (index < getCount()) {
 156             NodeList<Node> list = getNodeList(prototype, curOffsets, index);
 157             if (list != null) {
 158                 int size = list.initialSize;
 159                 NodeList<Node> newList = curType == Edges.Type.Inputs ? new NodeInputList<>(node, size) : new NodeSuccessorList<>(node, size);
 160                 initializeList(node, index, newList);
 161             }
 162             index++;
 163         }
 164     }
 165 
 166     /**
 167      * Copies edges from {@code fromNode} to {@code toNode}. The nodes are expected to be of the
 168      * exact same type.
 169      *
 170      * @param fromNode the node from which the edges should be copied.
 171      * @param toNode the node to which the edges should be copied.
 172      */
 173     public void copy(Node fromNode, Node toNode) {
 174         assert fromNode != toNode;
 175         assert fromNode.getNodeClass().getClazz() == toNode.getNodeClass().getClazz();
 176         int index = 0;
 177         final long[] curOffsets = this.offsets;
 178         final Type curType = this.type;
 179         int curDirectCount = getDirectCount();
 180         while (index < curDirectCount) {
 181             initializeNode(toNode, index, getNode(fromNode, curOffsets, index));
 182             index++;
 183         }
 184         int curCount = getCount();
 185         while (index < curCount) {
 186             NodeList<Node> list = getNodeList(toNode, curOffsets, index);
 187             NodeList<Node> fromList = getNodeList(fromNode, curOffsets, index);
 188             if (list == null || list == fromList) {
 189                 list = curType == Edges.Type.Inputs ? new NodeInputList<>(toNode, fromList) : new NodeSuccessorList<>(toNode, fromList);
 190                 initializeList(toNode, index, list);
 191             } else {
 192                 list.copy(fromList);
 193             }
 194             index++;
 195         }
 196     }
 197 
 198     @Override
 199     public void set(Object node, int index, Object value) {
 200         throw new IllegalArgumentException("Cannot call set on " + this);
 201     }
 202 
 203     /**
 204      * Sets the value of a given edge without notifying the new and old nodes on the other end of
 205      * the edge of the change.
 206      *
 207      * @param node the node whose edge is to be updated
 208      * @param index the index of the edge (between 0 and {@link #getCount()})
 209      * @param value the node to be written to the edge
 210      */
 211     public void initializeNode(Node node, int index, Node value) {
 212         verifyUpdateValid(node, index, value);
 213         putNodeUnsafe(node, offsets[index], value);
 214     }
 215 
 216     public void initializeList(Node node, int index, NodeList<Node> value) {
 217         verifyUpdateValid(node, index, value);
 218         putNodeListUnsafe(node, offsets[index], value);
 219     }
 220 
 221     private void verifyUpdateValid(Node node, int index, Object newValue) {
 222         if (newValue != null && !getType(index).isAssignableFrom(newValue.getClass())) {
 223             throw new IllegalArgumentException("Can not assign " + newValue.getClass() + " to " + getType(index) + " in " + node);
 224         }
 225     }
 226 
 227     /**
 228      * Sets the value of a given edge and notifies the new and old nodes on the other end of the
 229      * edge of the change.
 230      *
 231      * @param node the node whose edge is to be updated
 232      * @param index the index of the edge (between 0 and {@link #getCount()})
 233      * @param value the node to be written to the edge
 234      */
 235     public void setNode(Node node, int index, Node value) {
 236         assert index < directCount;
 237         Node old = getNodeUnsafe(node, offsets[index]);
 238         initializeNode(node, index, value);
 239         update(node, old, value);
 240     }
 241 
 242     public abstract void update(Node node, Node oldValue, Node newValue);
 243 
 244     public boolean contains(Node node, Node value) {
 245         final long[] curOffsets = this.offsets;
 246         for (int i = 0; i < directCount; i++) {
 247             if (getNode(node, curOffsets, i) == value) {
 248                 return true;
 249             }
 250         }
 251         for (int i = directCount; i < getCount(); i++) {
 252             NodeList<?> curList = getNodeList(node, curOffsets, i);
 253             if (curList != null && curList.contains(value)) {
 254                 return true;
 255             }
 256         }
 257         return false;
 258     }
 259 
 260     /**
 261      * An iterator that will iterate over edges.
 262      *
 263      * An iterator of this type will not return null values, unless edges are modified concurrently.
 264      * Concurrent modifications are detected by an assertion on a best-effort basis.
 265      */
 266     private static class EdgesIterator implements Iterator<Position> {
 267         protected final Node node;
 268         protected final Edges edges;
 269         protected int index;
 270         protected int subIndex;
 271         protected boolean needsForward;
 272         protected final int directCount;
 273         protected final long[] offsets;
 274 
 275         /**
 276          * Creates an iterator that will iterate over some given edges in a given node.
 277          */
 278         EdgesIterator(Node node, Edges edges) {
 279             this.node = node;
 280             this.edges = edges;
 281             index = NOT_ITERABLE;
 282             subIndex = 0;
 283             needsForward = true;
 284             this.directCount = edges.getDirectCount();
 285             this.offsets = edges.getOffsets();
 286         }
 287 
 288         void forward() {
 289             needsForward = false;
 290             if (index < directCount) {
 291                 index++;
 292                 if (index < directCount) {
 293                     return;
 294                 }
 295             } else {
 296                 subIndex++;
 297             }
 298             if (index < edges.getCount()) {
 299                 forwardNodeList();
 300             }
 301         }
 302 
 303         private void forwardNodeList() {
 304             do {
 305                 NodeList<?> list = Edges.getNodeList(node, offsets, index);
 306                 if (list != null) {
 307                     if (subIndex < list.size()) {
 308                         return;
 309                     }
 310                 }
 311                 subIndex = 0;
 312                 index++;
 313             } while (index < edges.getCount());
 314         }
 315 
 316         @Override
 317         public boolean hasNext() {
 318             if (needsForward) {
 319                 forward();
 320             }
 321             return index < edges.getCount();
 322         }
 323 
 324         @Override
 325         public Position next() {
 326             if (needsForward) {
 327                 forward();
 328             }
 329             needsForward = true;
 330             if (index < directCount) {
 331                 return new Position(edges, index, NOT_ITERABLE);
 332             } else {
 333                 return new Position(edges, index, subIndex);
 334             }
 335         }
 336 
 337         @Override
 338         public void remove() {
 339             throw new UnsupportedOperationException();
 340         }
 341     }
 342 
 343     private static final class EdgesWithModCountIterator extends EdgesIterator {
 344         private final int modCount;
 345 
 346         private EdgesWithModCountIterator(Node node, Edges edges) {
 347             super(node, edges);
 348             assert isModificationCountsEnabled();
 349             this.modCount = node.modCount();
 350         }
 351 
 352         @Override
 353         public boolean hasNext() {
 354             try {
 355                 return super.hasNext();
 356             } finally {
 357                 assert modCount == node.modCount() : "must not be modified";
 358             }
 359         }
 360 
 361         @Override
 362         public Position next() {
 363             try {
 364                 return super.next();
 365             } finally {
 366                 assert modCount == node.modCount() : "must not be modified";
 367             }
 368         }
 369     }
 370 
 371     public Iterable<Position> getPositionsIterable(final Node node) {
 372         return new Iterable<Position>() {
 373 
 374             @Override
 375             public Iterator<Position> iterator() {
 376                 if (isModificationCountsEnabled()) {
 377                     return new EdgesWithModCountIterator(node, Edges.this);
 378                 } else {
 379                     return new EdgesIterator(node, Edges.this);
 380                 }
 381             }
 382         };
 383     }
 384 
 385     public Type type() {
 386         return type;
 387     }
 388 }