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