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