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