1 /*
2 * Copyright (c) 2011, 2018, 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.core.common.GraalOptions.TrackNodeInsertion;
28 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED;
29 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;
30
31 import java.util.ArrayList;
32 import java.util.Arrays;
33 import java.util.Iterator;
34 import java.util.function.Consumer;
35
36 import jdk.internal.vm.compiler.collections.EconomicMap;
37 import jdk.internal.vm.compiler.collections.Equivalence;
38 import jdk.internal.vm.compiler.collections.UnmodifiableEconomicMap;
39 import org.graalvm.compiler.core.common.GraalOptions;
40 import org.graalvm.compiler.debug.CounterKey;
41 import org.graalvm.compiler.debug.DebugCloseable;
42 import org.graalvm.compiler.debug.DebugContext;
43 import org.graalvm.compiler.debug.GraalError;
44 import org.graalvm.compiler.debug.TimerKey;
45 import org.graalvm.compiler.graph.Node.NodeInsertionStackTrace;
46 import org.graalvm.compiler.graph.Node.ValueNumberable;
47 import org.graalvm.compiler.graph.iterators.NodeIterable;
48 import org.graalvm.compiler.options.Option;
49 import org.graalvm.compiler.options.OptionKey;
50 import org.graalvm.compiler.options.OptionType;
51 import org.graalvm.compiler.options.OptionValues;
52
53 import jdk.vm.ci.meta.ResolvedJavaMethod;
54
55 /**
56 * This class is a graph container, it contains the set of nodes that belong to this graph.
57 */
58 public class Graph {
59
60 public static class Options {
61 @Option(help = "Verify graphs often during compilation when assertions are turned on", type = OptionType.Debug)//
62 public static final OptionKey<Boolean> VerifyGraalGraphs = new OptionKey<>(true);
63 @Option(help = "Perform expensive verification of graph inputs, usages, successors and predecessors", type = OptionType.Debug)//
64 public static final OptionKey<Boolean> VerifyGraalGraphEdges = new OptionKey<>(false);
65 @Option(help = "Graal graph compression is performed when percent of live nodes falls below this value", type = OptionType.Debug)//
66 public static final OptionKey<Integer> GraphCompressionThreshold = new OptionKey<>(70);
67 }
68
69 private enum FreezeState {
70 Unfrozen,
71 TemporaryFreeze,
72 DeepFreeze
73 }
74
75 public final String name;
76
77 /**
78 * The set of nodes in the graph, ordered by {@linkplain #register(Node) registration} time.
79 */
80 Node[] nodes;
81
82 /**
83 * Source information to associate with newly created nodes.
84 */
85 NodeSourcePosition currentNodeSourcePosition;
86
87 /**
88 * Records if updating of node source information is required when performing inlining.
89 */
90 protected boolean trackNodeSourcePosition;
91
92 /**
93 * The number of valid entries in {@link #nodes}.
94 */
95 int nodesSize;
96
97 /**
98 * Records the modification count for nodes. This is only used in assertions.
99 */
100 private int[] nodeModCounts;
101
102 /**
103 * Records the modification count for nodes' usage lists. This is only used in assertions.
104 */
105 private int[] nodeUsageModCounts;
106
107 // these two arrays contain one entry for each NodeClass, indexed by NodeClass.iterableId.
108 // they contain the first and last pointer to a linked list of all nodes with this type.
109 private final ArrayList<Node> iterableNodesFirst;
110 private final ArrayList<Node> iterableNodesLast;
111
112 private int nodesDeletedSinceLastCompression;
113 private int nodesDeletedBeforeLastCompression;
114
115 /**
116 * The number of times this graph has been compressed.
117 */
118 int compressions;
119
120 NodeEventListener nodeEventListener;
121
122 /**
123 * Used to global value number {@link ValueNumberable} {@linkplain NodeClass#isLeafNode() leaf}
124 * nodes.
125 */
126 private EconomicMap<Node, Node>[] cachedLeafNodes;
127
128 private static final Equivalence NODE_VALUE_COMPARE = new Equivalence() {
129
130 @Override
131 public boolean equals(Object a, Object b) {
132 if (a == b) {
133 return true;
134 }
135
136 assert a.getClass() == b.getClass();
137 return ((Node) a).valueEquals((Node) b);
138 }
139
140 @Override
141 public int hashCode(Object k) {
142 return ((Node) k).getNodeClass().valueNumber((Node) k);
143 }
144 };
145
146 /**
147 * Indicates that the graph should no longer be modified. Frozen graphs can be used by multiple
148 * threads so it's only safe to read them.
149 */
150 private FreezeState freezeState = FreezeState.Unfrozen;
151
152 /**
153 * The option values used while compiling this graph.
154 */
155 private final OptionValues options;
156
157 /**
158 * The {@link DebugContext} used while compiling this graph.
159 */
160 private DebugContext debug;
161
162 private class NodeSourcePositionScope implements DebugCloseable {
163 private final NodeSourcePosition previous;
164
165 NodeSourcePositionScope(NodeSourcePosition sourcePosition) {
166 previous = currentNodeSourcePosition;
167 currentNodeSourcePosition = sourcePosition;
168 }
169
170 @Override
171 public DebugContext getDebug() {
172 return debug;
173 }
174
175 @Override
176 public void close() {
177 currentNodeSourcePosition = previous;
178 }
179 }
180
181 public NodeSourcePosition currentNodeSourcePosition() {
182 return currentNodeSourcePosition;
183 }
184
185 /**
186 * Opens a scope in which the source information from {@code node} is copied into nodes created
187 * within the scope. If {@code node} has no source information information, no scope is opened
188 * and {@code null} is returned.
189 *
190 * @return a {@link DebugCloseable} for managing the opened scope or {@code null} if no scope
191 * was opened
192 */
193 public DebugCloseable withNodeSourcePosition(Node node) {
194 return withNodeSourcePosition(node.getNodeSourcePosition());
195 }
196
197 /**
198 * Opens a scope in which {@code sourcePosition} is copied into nodes created within the scope.
199 * If {@code sourcePosition == null}, no scope is opened and {@code null} is returned.
200 *
201 * @return a {@link DebugCloseable} for managing the opened scope or {@code null} if no scope
202 * was opened
203 */
204 public DebugCloseable withNodeSourcePosition(NodeSourcePosition sourcePosition) {
205 return trackNodeSourcePosition() && sourcePosition != null ? new NodeSourcePositionScope(sourcePosition) : null;
206 }
207
208 /**
209 * Opens a scope in which newly created nodes do not get any source information added.
210 *
211 * @return a {@link DebugCloseable} for managing the opened scope
212 */
213 public DebugCloseable withoutNodeSourcePosition() {
214 return new NodeSourcePositionScope(null);
215 }
216
217 public boolean trackNodeSourcePosition() {
218 return trackNodeSourcePosition;
219 }
220
221 public void setTrackNodeSourcePosition() {
222 if (!trackNodeSourcePosition) {
223 assert getNodeCount() == 1 : "can't change the value after nodes have been added";
224 trackNodeSourcePosition = true;
225 }
226 }
227
228 public static boolean trackNodeSourcePositionDefault(OptionValues options, DebugContext debug) {
229 return (GraalOptions.TrackNodeSourcePosition.getValue(options) || debug.isDumpEnabledForMethod());
230 }
231
232 /**
233 * Creates an empty Graph with no name.
234 */
235 public Graph(OptionValues options, DebugContext debug) {
236 this(null, options, debug, false);
237 }
238
239 /**
240 * We only want the expensive modification count tracking when assertions are enabled for the
241 * {@link Graph} class.
242 */
243 @SuppressWarnings("all")
244 public static boolean isModificationCountsEnabled() {
245 boolean enabled = false;
246 assert enabled = true;
247 return enabled;
248 }
249
250 private static final int INITIAL_NODES_SIZE = 32;
251
252 /**
253 * Creates an empty Graph with a given name.
254 *
255 * @param name the name of the graph, used for debugging purposes
256 */
257 public Graph(String name, OptionValues options, DebugContext debug, boolean trackNodeSourcePosition) {
258 nodes = new Node[INITIAL_NODES_SIZE];
259 iterableNodesFirst = new ArrayList<>(NodeClass.allocatedNodeIterabledIds());
260 iterableNodesLast = new ArrayList<>(NodeClass.allocatedNodeIterabledIds());
261 this.name = name;
262 this.options = options;
263 this.trackNodeSourcePosition = trackNodeSourcePosition || trackNodeSourcePositionDefault(options, debug);
264 assert debug != null;
265 this.debug = debug;
266
267 if (isModificationCountsEnabled()) {
268 nodeModCounts = new int[INITIAL_NODES_SIZE];
269 nodeUsageModCounts = new int[INITIAL_NODES_SIZE];
270 }
271 }
272
273 int extractOriginalNodeId(Node node) {
274 int id = node.id;
275 if (id <= Node.DELETED_ID_START) {
276 id = Node.DELETED_ID_START - id;
277 }
278 return id;
279 }
280
281 int modCount(Node node) {
282 int id = extractOriginalNodeId(node);
283 if (id >= 0 && id < nodeModCounts.length) {
284 return nodeModCounts[id];
285 }
286 return 0;
287 }
288
289 void incModCount(Node node) {
290 int id = extractOriginalNodeId(node);
291 if (id >= 0) {
292 if (id >= nodeModCounts.length) {
293 nodeModCounts = Arrays.copyOf(nodeModCounts, id * 2 + 30);
294 }
295 nodeModCounts[id]++;
296 } else {
297 assert false;
298 }
299 }
300
301 int usageModCount(Node node) {
302 int id = extractOriginalNodeId(node);
303 if (id >= 0 && id < nodeUsageModCounts.length) {
304 return nodeUsageModCounts[id];
305 }
306 return 0;
307 }
308
309 void incUsageModCount(Node node) {
310 int id = extractOriginalNodeId(node);
311 if (id >= 0) {
312 if (id >= nodeUsageModCounts.length) {
313 nodeUsageModCounts = Arrays.copyOf(nodeUsageModCounts, id * 2 + 30);
314 }
315 nodeUsageModCounts[id]++;
316 } else {
317 assert false;
318 }
319 }
320
321 /**
322 * Creates a copy of this graph.
323 *
324 * @param debugForCopy the debug context for the graph copy. This must not be the debug for this
325 * graph if this graph can be accessed from multiple threads (e.g., it's in a cache
326 * accessed by multiple threads).
327 */
328 public final Graph copy(DebugContext debugForCopy) {
329 return copy(name, null, debugForCopy);
330 }
331
332 /**
333 * Creates a copy of this graph.
334 *
335 * @param duplicationMapCallback consumer of the duplication map created during the copying
336 * @param debugForCopy the debug context for the graph copy. This must not be the debug for this
337 * graph if this graph can be accessed from multiple threads (e.g., it's in a cache
338 * accessed by multiple threads).
339 */
340 public final Graph copy(Consumer<UnmodifiableEconomicMap<Node, Node>> duplicationMapCallback, DebugContext debugForCopy) {
341 return copy(name, duplicationMapCallback, debugForCopy);
342 }
343
344 /**
345 * Creates a copy of this graph.
346 *
347 * @param newName the name of the copy, used for debugging purposes (can be null)
348 * @param debugForCopy the debug context for the graph copy. This must not be the debug for this
349 * graph if this graph can be accessed from multiple threads (e.g., it's in a cache
350 * accessed by multiple threads).
351 */
352 public final Graph copy(String newName, DebugContext debugForCopy) {
353 return copy(newName, null, debugForCopy);
354 }
355
356 /**
357 * Creates a copy of this graph.
358 *
359 * @param newName the name of the copy, used for debugging purposes (can be null)
360 * @param duplicationMapCallback consumer of the duplication map created during the copying
361 * @param debugForCopy the debug context for the graph copy. This must not be the debug for this
362 * graph if this graph can be accessed from multiple threads (e.g., it's in a cache
363 * accessed by multiple threads).
364 */
365 protected Graph copy(String newName, Consumer<UnmodifiableEconomicMap<Node, Node>> duplicationMapCallback, DebugContext debugForCopy) {
366 Graph copy = new Graph(newName, options, debugForCopy, trackNodeSourcePosition());
367 UnmodifiableEconomicMap<Node, Node> duplicates = copy.addDuplicates(getNodes(), this, this.getNodeCount(), (EconomicMap<Node, Node>) null);
368 if (duplicationMapCallback != null) {
369 duplicationMapCallback.accept(duplicates);
370 }
371 return copy;
372 }
373
374 public final OptionValues getOptions() {
375 return options;
376 }
377
378 public DebugContext getDebug() {
379 return debug;
380 }
381
382 /**
383 * Resets the {@link DebugContext} for this graph to a new value. This is useful when a graph is
384 * "handed over" from its creating thread to another thread.
385 *
386 * This must only be done when the current thread is no longer using the graph. This is in
387 * general impossible to test due to races and since metrics can be updated at any time. As
388 * such, this method only performs a weak sanity check that at least the current debug context
389 * does not have a nested scope open (the top level scope will always be open if scopes are
390 * enabled).
391 */
392 public void resetDebug(DebugContext newDebug) {
393 assert newDebug == debug || !debug.inNestedScope() : String.format("Cannot reset the debug context for %s while it has the nested scope \"%s\" open", this, debug.getCurrentScopeName());
394 this.debug = newDebug;
395 }
396
397 @Override
398 public String toString() {
399 return name == null ? super.toString() : "Graph " + name;
400 }
401
402 /**
403 * Gets the number of live nodes in this graph. That is the number of nodes which have been
404 * added to the graph minus the number of deleted nodes.
405 *
406 * @return the number of live nodes in this graph
407 */
408 public int getNodeCount() {
409 return nodesSize - getNodesDeletedSinceLastCompression();
410 }
411
412 /**
413 * Gets the number of times this graph has been {@linkplain #maybeCompress() compressed}. Node
414 * identifiers are only stable between compressions. To ensure this constraint is observed, any
415 * entity relying upon stable node identifiers should use {@link NodeIdAccessor}.
416 */
417 public int getCompressions() {
418 return compressions;
419 }
420
421 /**
422 * Gets the number of nodes which have been deleted from this graph since it was last
423 * {@linkplain #maybeCompress() compressed}.
424 */
425 public int getNodesDeletedSinceLastCompression() {
426 return nodesDeletedSinceLastCompression;
427 }
428
429 /**
430 * Gets the total number of nodes which have been deleted from this graph.
431 */
432 public int getTotalNodesDeleted() {
433 return nodesDeletedSinceLastCompression + nodesDeletedBeforeLastCompression;
434 }
435
436 /**
437 * Adds a new node to the graph.
438 *
439 * @param node the node to be added
440 * @return the node which was added to the graph
441 */
442 public <T extends Node> T add(T node) {
443 if (node.getNodeClass().valueNumberable()) {
444 throw new IllegalStateException("Using add for value numberable node. Consider using either unique or addWithoutUnique.");
445 }
446 return addHelper(node);
447 }
448
449 public <T extends Node> T addWithoutUnique(T node) {
450 return addHelper(node);
451 }
452
453 public <T extends Node> T addOrUnique(T node) {
454 if (node.getNodeClass().valueNumberable()) {
455 return uniqueHelper(node);
456 }
457 return add(node);
458 }
459
460 public <T extends Node> T maybeAddOrUnique(T node) {
461 if (node.isAlive()) {
462 return node;
463 }
464 return addOrUnique(node);
465 }
466
467 public <T extends Node> T addOrUniqueWithInputs(T node) {
468 if (node.isAlive()) {
469 assert node.graph() == this;
470 return node;
471 } else {
472 assert node.isUnregistered();
473 addInputs(node);
474 if (node.getNodeClass().valueNumberable()) {
475 return uniqueHelper(node);
476 }
477 return add(node);
478 }
479 }
480
481 public <T extends Node> T addWithoutUniqueWithInputs(T node) {
482 addInputs(node);
483 return addHelper(node);
484 }
485
486 private final class AddInputsFilter extends Node.EdgeVisitor {
487
488 @Override
489 public Node apply(Node self, Node input) {
490 if (!input.isAlive()) {
491 assert !input.isDeleted();
492 return addOrUniqueWithInputs(input);
493 } else {
494 return input;
495 }
496 }
497
498 }
499
500 private AddInputsFilter addInputsFilter = new AddInputsFilter();
501
502 private <T extends Node> void addInputs(T node) {
503 node.applyInputs(addInputsFilter);
504 }
505
506 private <T extends Node> T addHelper(T node) {
507 node.initialize(this);
508 return node;
509 }
510
511 /**
512 * The type of events sent to a {@link NodeEventListener}.
513 */
514 public enum NodeEvent {
515 /**
516 * A node's input is changed.
517 */
518 INPUT_CHANGED,
519
520 /**
521 * A node's {@linkplain Node#usages() usages} count dropped to zero.
522 */
523 ZERO_USAGES,
524
525 /**
526 * A node was added to a graph.
527 */
528 NODE_ADDED,
529
530 /**
531 * A node was removed from the graph.
532 */
533 NODE_REMOVED
534 }
535
536 /**
537 * Client interested in one or more node related events.
538 */
539 public abstract static class NodeEventListener {
540
541 /**
542 * A method called when a change event occurs.
543 *
544 * This method dispatches the event to user-defined triggers. The methods that change the
545 * graph (typically in Graph and Node) must call this method to dispatch the event.
546 *
547 * @param e an event
548 * @param node the node related to {@code e}
549 */
550 final void event(NodeEvent e, Node node) {
551 switch (e) {
552 case INPUT_CHANGED:
553 inputChanged(node);
554 break;
555 case ZERO_USAGES:
556 usagesDroppedToZero(node);
557 break;
558 case NODE_ADDED:
559 nodeAdded(node);
560 break;
561 case NODE_REMOVED:
562 nodeRemoved(node);
563 break;
564 }
565 changed(e, node);
566 }
567
568 /**
569 * Notifies this listener about any change event in the graph.
570 *
571 * @param e an event
572 * @param node the node related to {@code e}
573 */
574 public void changed(NodeEvent e, Node node) {
575 }
576
577 /**
578 * Notifies this listener about a change in a node's inputs.
579 *
580 * @param node a node who has had one of its inputs changed
581 */
582 public void inputChanged(Node node) {
583 }
584
585 /**
586 * Notifies this listener of a node becoming unused.
587 *
588 * @param node a node whose {@link Node#usages()} just became empty
589 */
590 public void usagesDroppedToZero(Node node) {
591 }
592
593 /**
594 * Notifies this listener of an added node.
595 *
596 * @param node a node that was just added to the graph
597 */
598 public void nodeAdded(Node node) {
599 }
600
601 /**
602 * Notifies this listener of a removed node.
603 *
604 * @param node
605 */
606 public void nodeRemoved(Node node) {
607 }
608 }
609
610 /**
611 * Registers a given {@link NodeEventListener} with the enclosing graph until this object is
612 * {@linkplain #close() closed}.
613 */
614 public final class NodeEventScope implements AutoCloseable {
615 NodeEventScope(NodeEventListener listener) {
616 if (nodeEventListener == null) {
617 nodeEventListener = listener;
618 } else {
619 nodeEventListener = new ChainedNodeEventListener(listener, nodeEventListener);
620 }
621 }
622
623 @Override
624 public void close() {
625 assert nodeEventListener != null;
626 if (nodeEventListener instanceof ChainedNodeEventListener) {
627 nodeEventListener = ((ChainedNodeEventListener) nodeEventListener).next;
628 } else {
629 nodeEventListener = null;
630 }
631 }
632 }
633
634 private static class ChainedNodeEventListener extends NodeEventListener {
635
636 NodeEventListener head;
637 NodeEventListener next;
638
639 ChainedNodeEventListener(NodeEventListener head, NodeEventListener next) {
640 this.head = head;
641 this.next = next;
642 }
643
644 @Override
645 public void nodeAdded(Node node) {
646 head.event(NodeEvent.NODE_ADDED, node);
647 next.event(NodeEvent.NODE_ADDED, node);
648 }
649
650 @Override
651 public void inputChanged(Node node) {
652 head.event(NodeEvent.INPUT_CHANGED, node);
653 next.event(NodeEvent.INPUT_CHANGED, node);
654 }
655
656 @Override
657 public void usagesDroppedToZero(Node node) {
658 head.event(NodeEvent.ZERO_USAGES, node);
659 next.event(NodeEvent.ZERO_USAGES, node);
660 }
661
662 @Override
663 public void nodeRemoved(Node node) {
664 head.event(NodeEvent.NODE_REMOVED, node);
665 next.event(NodeEvent.NODE_REMOVED, node);
666 }
667
668 @Override
669 public void changed(NodeEvent e, Node node) {
670 head.event(e, node);
671 next.event(e, node);
672 }
673 }
674
675 /**
676 * Registers a given {@link NodeEventListener} with this graph. This should be used in
677 * conjunction with try-with-resources statement as follows:
678 *
679 * <pre>
680 * try (NodeEventScope nes = graph.trackNodeEvents(listener)) {
681 * // make changes to the graph
682 * }
683 * </pre>
684 */
685 public NodeEventScope trackNodeEvents(NodeEventListener listener) {
686 return new NodeEventScope(listener);
687 }
688
689 /**
690 * Looks for a node <i>similar</i> to {@code node} and returns it if found. Otherwise
691 * {@code node} is added to this graph and returned.
692 *
693 * @return a node similar to {@code node} if one exists, otherwise {@code node}
694 */
695 public <T extends Node & ValueNumberable> T unique(T node) {
696 return uniqueHelper(node);
697 }
698
699 <T extends Node> T uniqueHelper(T node) {
700 assert node.getNodeClass().valueNumberable();
701 T other = this.findDuplicate(node);
702 if (other != null) {
703 if (other.getNodeSourcePosition() == null) {
704 other.setNodeSourcePosition(node.getNodeSourcePosition());
705 }
706 return other;
707 } else {
708 T result = addHelper(node);
709 if (node.getNodeClass().isLeafNode()) {
710 putNodeIntoCache(result);
711 }
712 return result;
713 }
714 }
715
716 void removeNodeFromCache(Node node) {
717 assert node.graph() == this || node.graph() == null;
718 assert node.getNodeClass().valueNumberable();
719 assert node.getNodeClass().isLeafNode() : node.getClass();
720
721 int leafId = node.getNodeClass().getLeafId();
722 if (cachedLeafNodes != null && cachedLeafNodes.length > leafId && cachedLeafNodes[leafId] != null) {
723 cachedLeafNodes[leafId].removeKey(node);
724 }
725 }
726
727 @SuppressWarnings({"unchecked", "rawtypes"})
728 void putNodeIntoCache(Node node) {
729 assert node.graph() == this || node.graph() == null;
730 assert node.getNodeClass().valueNumberable();
731 assert node.getNodeClass().isLeafNode() : node.getClass();
732
733 int leafId = node.getNodeClass().getLeafId();
734 if (cachedLeafNodes == null || cachedLeafNodes.length <= leafId) {
735 EconomicMap[] newLeafNodes = new EconomicMap[leafId + 1];
736 if (cachedLeafNodes != null) {
737 System.arraycopy(cachedLeafNodes, 0, newLeafNodes, 0, cachedLeafNodes.length);
738 }
739 cachedLeafNodes = newLeafNodes;
740 }
741
742 if (cachedLeafNodes[leafId] == null) {
743 cachedLeafNodes[leafId] = EconomicMap.create(NODE_VALUE_COMPARE);
744 }
745
746 cachedLeafNodes[leafId].put(node, node);
747 }
748
749 Node findNodeInCache(Node node) {
750 int leafId = node.getNodeClass().getLeafId();
751 if (cachedLeafNodes == null || cachedLeafNodes.length <= leafId || cachedLeafNodes[leafId] == null) {
752 return null;
753 }
754
755 Node result = cachedLeafNodes[leafId].get(node);
756 assert result == null || result.isAlive() : result;
757 return result;
758 }
759
760 /**
761 * Returns a possible duplicate for the given node in the graph or {@code null} if no such
762 * duplicate exists.
763 */
764 @SuppressWarnings("unchecked")
765 public <T extends Node> T findDuplicate(T node) {
766 NodeClass<?> nodeClass = node.getNodeClass();
767 assert nodeClass.valueNumberable();
768 if (nodeClass.isLeafNode()) {
769 // Leaf node: look up in cache
770 Node cachedNode = findNodeInCache(node);
771 if (cachedNode != null && cachedNode != node) {
772 return (T) cachedNode;
773 } else {
774 return null;
775 }
776 } else {
777 /*
778 * Non-leaf node: look for another usage of the node's inputs that has the same data,
779 * inputs and successors as the node. To reduce the cost of this computation, only the
780 * input with lowest usage count is considered. If this node is the only user of any
781 * input then the search can terminate early. The usage count is only incremented once
782 * the Node is in the Graph, so account for that in the test.
783 */
784 final int earlyExitUsageCount = node.graph() != null ? 1 : 0;
785 int minCount = Integer.MAX_VALUE;
786 Node minCountNode = null;
787 for (Node input : node.inputs()) {
788 int usageCount = input.getUsageCount();
789 if (usageCount == earlyExitUsageCount) {
790 return null;
791 } else if (usageCount < minCount) {
792 minCount = usageCount;
793 minCountNode = input;
794 }
795 }
796 if (minCountNode != null) {
797 for (Node usage : minCountNode.usages()) {
798 if (usage != node && nodeClass == usage.getNodeClass() && node.valueEquals(usage) && nodeClass.equalInputs(node, usage) &&
799 nodeClass.equalSuccessors(node, usage)) {
800 return (T) usage;
801 }
802 }
803 return null;
804 }
805 return null;
806 }
807 }
808
809 public boolean isNew(Mark mark, Node node) {
810 return node.id >= mark.getValue();
811 }
812
813 /**
814 * A snapshot of the {@linkplain Graph#getNodeCount() live node count} in a graph.
815 */
816 public static class Mark extends NodeIdAccessor {
817 private final int value;
818
819 Mark(Graph graph) {
820 super(graph);
821 this.value = graph.nodeIdCount();
822 }
823
824 @Override
825 public boolean equals(Object obj) {
826 if (obj instanceof Mark) {
827 Mark other = (Mark) obj;
828 return other.getValue() == getValue() && other.getGraph() == getGraph();
829 }
830 return false;
831 }
832
833 @Override
834 public int hashCode() {
835 return value ^ (epoch + 11);
836 }
837
838 /**
839 * Determines if this mark is positioned at the first live node in the graph.
840 */
841 public boolean isStart() {
842 return value == 0;
843 }
844
845 /**
846 * Gets the {@linkplain Graph#getNodeCount() live node count} of the associated graph when
847 * this object was created.
848 */
849 int getValue() {
850 return value;
851 }
852
853 /**
854 * Determines if this mark still represents the {@linkplain Graph#getNodeCount() live node
855 * count} of the graph.
856 */
857 public boolean isCurrent() {
858 return value == graph.nodeIdCount();
859 }
860 }
861
862 /**
863 * Gets a mark that can be used with {@link #getNewNodes}.
864 */
865 public Mark getMark() {
866 return new Mark(this);
867 }
868
869 /**
870 * Returns an {@link Iterable} providing all nodes added since the last {@link Graph#getMark()
871 * mark}.
872 */
873 public NodeIterable<Node> getNewNodes(Mark mark) {
874 final int index = mark == null ? 0 : mark.getValue();
875 return new NodeIterable<Node>() {
876
877 @Override
878 public Iterator<Node> iterator() {
879 return new GraphNodeIterator(Graph.this, index);
880 }
881 };
882 }
883
884 /**
885 * Returns an {@link Iterable} providing all the live nodes.
886 *
887 * @return an {@link Iterable} providing all the live nodes.
888 */
889 public NodeIterable<Node> getNodes() {
890 return new NodeIterable<Node>() {
891
892 @Override
893 public Iterator<Node> iterator() {
894 return new GraphNodeIterator(Graph.this);
895 }
896
897 @Override
898 public int count() {
899 return getNodeCount();
900 }
901 };
902 }
903
904 // Fully qualified annotation name is required to satisfy javac
905 @org.graalvm.compiler.nodeinfo.NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED)
906 static final class PlaceHolderNode extends Node {
907
908 public static final NodeClass<PlaceHolderNode> TYPE = NodeClass.create(PlaceHolderNode.class);
909
910 protected PlaceHolderNode() {
911 super(TYPE);
912 }
913
914 }
915
916 private static final CounterKey GraphCompressions = DebugContext.counter("GraphCompressions");
917
918 /**
919 * If the {@linkplain Options#GraphCompressionThreshold compression threshold} is met, the list
920 * of nodes is compressed such that all non-null entries precede all null entries while
921 * preserving the ordering between the nodes within the list.
922 */
923 public boolean maybeCompress() {
924 if (debug.isDumpEnabledForMethod() || debug.isLogEnabledForMethod()) {
925 return false;
926 }
927 int liveNodeCount = getNodeCount();
928 int liveNodePercent = liveNodeCount * 100 / nodesSize;
929 int compressionThreshold = Options.GraphCompressionThreshold.getValue(options);
930 if (compressionThreshold == 0 || liveNodePercent >= compressionThreshold) {
931 return false;
932 }
933 GraphCompressions.increment(debug);
934 int nextId = 0;
935 for (int i = 0; nextId < liveNodeCount; i++) {
936 Node n = nodes[i];
937 if (n != null) {
938 assert n.id == i;
939 if (i != nextId) {
940 assert n.id > nextId;
941 n.id = nextId;
942 nodes[nextId] = n;
943 nodes[i] = null;
944 }
945 nextId++;
946 }
947 }
948 if (isModificationCountsEnabled()) {
949 // This will cause any current iteration to fail with an assertion
950 Arrays.fill(nodeModCounts, 0);
951 Arrays.fill(nodeUsageModCounts, 0);
952 }
953 nodesSize = nextId;
954 compressions++;
955 nodesDeletedBeforeLastCompression += nodesDeletedSinceLastCompression;
956 nodesDeletedSinceLastCompression = 0;
957 return true;
958 }
959
960 /**
961 * Returns an {@link Iterable} providing all the live nodes whose type is compatible with
962 * {@code type}.
963 *
964 * @param nodeClass the type of node to return
965 * @return an {@link Iterable} providing all the matching nodes
966 */
967 public <T extends Node & IterableNodeType> NodeIterable<T> getNodes(final NodeClass<T> nodeClass) {
968 return new NodeIterable<T>() {
969
970 @Override
971 public Iterator<T> iterator() {
972 return new TypedGraphNodeIterator<>(nodeClass, Graph.this);
973 }
974 };
975 }
976
977 /**
978 * Returns whether the graph contains at least one node of the given type.
979 *
980 * @param type the type of node that is checked for occurrence
981 * @return whether there is at least one such node
982 */
983 public <T extends Node & IterableNodeType> boolean hasNode(final NodeClass<T> type) {
984 return getNodes(type).iterator().hasNext();
985 }
986
987 /**
988 * @param iterableId
989 * @return the first live Node with a matching iterableId
990 */
991 Node getIterableNodeStart(int iterableId) {
992 if (iterableNodesFirst.size() <= iterableId) {
993 return null;
994 }
995 Node start = iterableNodesFirst.get(iterableId);
996 if (start == null || !start.isDeleted()) {
997 return start;
998 }
999 return findFirstLiveIterable(iterableId, start);
1000 }
1001
1002 private Node findFirstLiveIterable(int iterableId, Node node) {
1003 Node start = node;
1004 while (start != null && start.isDeleted()) {
1005 start = start.typeCacheNext;
1006 }
1007 /*
1008 * Multiple threads iterating nodes can update this cache simultaneously. This is a benign
1009 * race, since all threads update it to the same value.
1010 */
1011 iterableNodesFirst.set(iterableId, start);
1012 if (start == null) {
1013 iterableNodesLast.set(iterableId, start);
1014 }
1015 return start;
1016 }
1017
1018 /**
1019 * @param node
1020 * @return return the first live Node with a matching iterableId starting from {@code node}
1021 */
1022 Node getIterableNodeNext(Node node) {
1023 if (node == null) {
1024 return null;
1025 }
1026 Node n = node;
1027 if (n == null || !n.isDeleted()) {
1028 return n;
1029 }
1030
1031 return findNextLiveiterable(node);
1032 }
1033
1034 private Node findNextLiveiterable(Node start) {
1035 Node n = start;
1036 while (n != null && n.isDeleted()) {
1037 n = n.typeCacheNext;
1038 }
1039 if (n == null) {
1040 // Only dead nodes after this one
1041 start.typeCacheNext = null;
1042 int nodeClassId = start.getNodeClass().iterableId();
1043 assert nodeClassId != Node.NOT_ITERABLE;
1044 iterableNodesLast.set(nodeClassId, start);
1045 } else {
1046 // Everything in between is dead
1047 start.typeCacheNext = n;
1048 }
1049 return n;
1050 }
1051
1052 public NodeBitMap createNodeBitMap() {
1053 return new NodeBitMap(this);
1054 }
1055
1056 public <T> NodeMap<T> createNodeMap() {
1057 return new NodeMap<>(this);
1058 }
1059
1060 public NodeFlood createNodeFlood() {
1061 return new NodeFlood(this);
1062 }
1063
1064 public NodeWorkList createNodeWorkList() {
1065 return new NodeWorkList.SingletonNodeWorkList(this);
1066 }
1067
1068 public NodeWorkList createIterativeNodeWorkList(boolean fill, int iterationLimitPerNode) {
1069 return new NodeWorkList.IterativeNodeWorkList(this, fill, iterationLimitPerNode);
1070 }
1071
1072 void register(Node node) {
1073 assert !isFrozen();
1074 assert node.id() == Node.INITIAL_ID;
1075 if (nodes.length == nodesSize) {
1076 grow();
1077 }
1078 int id = nodesSize++;
1079 nodes[id] = node;
1080 node.id = id;
1081 if (currentNodeSourcePosition != null && trackNodeSourcePosition()) {
1082 node.setNodeSourcePosition(currentNodeSourcePosition);
1083 }
1084 if (TrackNodeInsertion.getValue(getOptions())) {
1085 node.setInsertionPosition(new NodeInsertionStackTrace());
1086 }
1087
1088 updateNodeCaches(node);
1089
1090 if (nodeEventListener != null) {
1091 nodeEventListener.event(NodeEvent.NODE_ADDED, node);
1092 }
1093 afterRegister(node);
1094 }
1095
1096 private void grow() {
1097 Node[] newNodes = new Node[(nodesSize * 2) + 1];
1098 System.arraycopy(nodes, 0, newNodes, 0, nodesSize);
1099 nodes = newNodes;
1100 }
1101
1102 @SuppressWarnings("unused")
1103 protected void afterRegister(Node node) {
1104
1105 }
1106
1107 @SuppressWarnings("unused")
1108 private void postDeserialization() {
1109 recomputeIterableNodeLists();
1110 }
1111
1112 /**
1113 * Rebuilds the lists used to support {@link #getNodes(NodeClass)}. This is useful for
1114 * serialization where the underlying {@linkplain NodeClass#iterableId() iterable ids} may have
1115 * changed.
1116 */
1117 private void recomputeIterableNodeLists() {
1118 iterableNodesFirst.clear();
1119 iterableNodesLast.clear();
1120 for (Node node : nodes) {
1121 if (node != null && node.isAlive()) {
1122 updateNodeCaches(node);
1123 }
1124 }
1125 }
1126
1127 private void updateNodeCaches(Node node) {
1128 int nodeClassId = node.getNodeClass().iterableId();
1129 if (nodeClassId != Node.NOT_ITERABLE) {
1130 while (iterableNodesFirst.size() <= nodeClassId) {
1131 iterableNodesFirst.add(null);
1132 iterableNodesLast.add(null);
1133 }
1134 Node prev = iterableNodesLast.get(nodeClassId);
1135 if (prev != null) {
1136 prev.typeCacheNext = node;
1137 } else {
1138 iterableNodesFirst.set(nodeClassId, node);
1139 }
1140 iterableNodesLast.set(nodeClassId, node);
1141 }
1142 }
1143
1144 void unregister(Node node) {
1145 assert !isFrozen();
1146 assert !node.isDeleted() : node;
1147 if (node.getNodeClass().isLeafNode() && node.getNodeClass().valueNumberable()) {
1148 removeNodeFromCache(node);
1149 }
1150 nodes[node.id] = null;
1151 nodesDeletedSinceLastCompression++;
1152
1153 if (nodeEventListener != null) {
1154 nodeEventListener.event(NodeEvent.NODE_ADDED, node);
1155 }
1156
1157 // nodes aren't removed from the type cache here - they will be removed during iteration
1158 }
1159
1160 public boolean verify() {
1161 if (Options.VerifyGraalGraphs.getValue(options)) {
1162 for (Node node : getNodes()) {
1163 try {
1164 try {
1165 assert node.verify();
1166 } catch (AssertionError t) {
1167 throw new GraalError(t);
1168 } catch (RuntimeException t) {
1169 throw new GraalError(t);
1170 }
1171 } catch (GraalError e) {
1172 throw GraalGraphError.transformAndAddContext(e, node).addContext(this);
1173 }
1174 }
1175 }
1176 return true;
1177 }
1178
1179 public boolean verifySourcePositions(boolean performConsistencyCheck) {
1180 if (trackNodeSourcePosition()) {
1181 ResolvedJavaMethod root = null;
1182 for (Node node : getNodes()) {
1183 NodeSourcePosition pos = node.getNodeSourcePosition();
1184 if (pos != null) {
1185 if (root == null) {
1186 root = pos.getRootMethod();
1187 } else {
1188 assert pos.verifyRootMethod(root) : node;
1189 }
1190 }
1191
1192 // More strict node-type-specific check
1193 if (performConsistencyCheck) {
1194 // Disabled due to GR-10445.
1195 // node.verifySourcePosition();
1196 }
1197 }
1198 }
1199 return true;
1200 }
1201
1202 public Node getNode(int id) {
1203 return nodes[id];
1204 }
1205
1206 /**
1207 * Returns the number of node ids generated so far.
1208 *
1209 * @return the number of node ids generated so far
1210 */
1211 int nodeIdCount() {
1212 return nodesSize;
1213 }
1214
1215 /**
1216 * Adds duplicates of the nodes in {@code newNodes} to this graph. This will recreate any edges
1217 * between the duplicate nodes. The {@code replacement} map can be used to replace a node from
1218 * the source graph by a given node (which must already be in this graph). Edges between
1219 * duplicate and replacement nodes will also be recreated so care should be taken regarding the
1220 * matching of node types in the replacement map.
1221 *
1222 * @param newNodes the nodes to be duplicated
1223 * @param replacementsMap the replacement map (can be null if no replacement is to be performed)
1224 * @return a map which associates the original nodes from {@code nodes} to their duplicates
1225 */
1226 public UnmodifiableEconomicMap<Node, Node> addDuplicates(Iterable<? extends Node> newNodes, final Graph oldGraph, int estimatedNodeCount, EconomicMap<Node, Node> replacementsMap) {
1227 DuplicationReplacement replacements;
1228 if (replacementsMap == null) {
1229 replacements = null;
1230 } else {
1231 replacements = new MapReplacement(replacementsMap);
1232 }
1233 return addDuplicates(newNodes, oldGraph, estimatedNodeCount, replacements);
1234 }
1235
1236 public interface DuplicationReplacement {
1237
1238 Node replacement(Node original);
1239 }
1240
1241 private static final class MapReplacement implements DuplicationReplacement {
1242
1243 private final EconomicMap<Node, Node> map;
1244
1245 MapReplacement(EconomicMap<Node, Node> map) {
1246 this.map = map;
1247 }
1248
1249 @Override
1250 public Node replacement(Node original) {
1251 Node replacement = map.get(original);
1252 return replacement != null ? replacement : original;
1253 }
1254
1255 }
1256
1257 private static final TimerKey DuplicateGraph = DebugContext.timer("DuplicateGraph");
1258
1259 @SuppressWarnings({"all", "try"})
1260 public EconomicMap<Node, Node> addDuplicates(Iterable<? extends Node> newNodes, final Graph oldGraph, int estimatedNodeCount, DuplicationReplacement replacements) {
1261 try (DebugCloseable s = DuplicateGraph.start(getDebug())) {
1262 return NodeClass.addGraphDuplicate(this, oldGraph, estimatedNodeCount, newNodes, replacements);
1263 }
1264 }
1265
1266 public boolean isFrozen() {
1267 return freezeState != FreezeState.Unfrozen;
1268 }
1269
1270 public void freeze() {
1271 this.freezeState = FreezeState.DeepFreeze;
1272 }
1273
1274 public void temporaryFreeze() {
1275 if (this.freezeState == FreezeState.DeepFreeze) {
1276 throw new GraalError("Graph was permanetly frozen.");
1277 }
1278 this.freezeState = FreezeState.TemporaryFreeze;
1279 }
1280
1281 public void unfreeze() {
1282 if (this.freezeState == FreezeState.DeepFreeze) {
1283 throw new GraalError("Graph was permanetly frozen.");
1284 }
1285 this.freezeState = FreezeState.Unfrozen;
1286 }
1287 }