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 public <T extends Node> T addWithoutUniqueWithInputs(T node) {
476 addInputs(node);
477 return addHelper(node);
478 }
479
480 private final class AddInputsFilter extends Node.EdgeVisitor {
481
482 @Override
483 public Node apply(Node self, Node input) {
484 if (!input.isAlive()) {
485 assert !input.isDeleted();
486 return addOrUniqueWithInputs(input);
487 } else {
488 return input;
489 }
490 }
491
492 }
493
494 private AddInputsFilter addInputsFilter = new AddInputsFilter();
495
496 private <T extends Node> void addInputs(T node) {
497 node.applyInputs(addInputsFilter);
498 }
499
500 private <T extends Node> T addHelper(T node) {
501 node.initialize(this);
502 return node;
503 }
504
505 /**
506 * The type of events sent to a {@link NodeEventListener}.
507 */
508 public enum NodeEvent {
509 /**
510 * A node's input is changed.
511 */
512 INPUT_CHANGED,
513
514 /**
515 * A node's {@linkplain Node#usages() usages} count dropped to zero.
516 */
517 ZERO_USAGES,
518
519 /**
520 * A node was added to a graph.
521 */
522 NODE_ADDED,
523
524 /**
525 * A node was removed from the graph.
526 */
527 NODE_REMOVED;
528 }
529
530 /**
531 * Client interested in one or more node related events.
532 */
533 public abstract static class NodeEventListener {
534
535 /**
536 * A method called when a change event occurs.
537 *
538 * This method dispatches the event to user-defined triggers. The methods that change the
539 * graph (typically in Graph and Node) must call this method to dispatch the event.
540 *
541 * @param e an event
542 * @param node the node related to {@code e}
543 */
544 final void event(NodeEvent e, Node node) {
545 switch (e) {
546 case INPUT_CHANGED:
547 inputChanged(node);
548 break;
549 case ZERO_USAGES:
550 usagesDroppedToZero(node);
551 break;
552 case NODE_ADDED:
553 nodeAdded(node);
554 break;
555 case NODE_REMOVED:
556 nodeRemoved(node);
557 break;
558 }
559 changed(e, node);
560 }
561
562 /**
563 * Notifies this listener about any change event in the graph.
564 *
565 * @param e an event
566 * @param node the node related to {@code e}
567 */
568 public void changed(NodeEvent e, Node node) {
569 }
570
571 /**
572 * Notifies this listener about a change in a node's inputs.
573 *
574 * @param node a node who has had one of its inputs changed
575 */
576 public void inputChanged(Node node) {
577 }
578
579 /**
580 * Notifies this listener of a node becoming unused.
581 *
582 * @param node a node whose {@link Node#usages()} just became empty
583 */
584 public void usagesDroppedToZero(Node node) {
585 }
586
587 /**
588 * Notifies this listener of an added node.
589 *
590 * @param node a node that was just added to the graph
591 */
592 public void nodeAdded(Node node) {
593 }
594
595 /**
596 * Notifies this listener of a removed node.
597 *
598 * @param node
599 */
600 public void nodeRemoved(Node node) {
601 }
602 }
603
604 /**
605 * Registers a given {@link NodeEventListener} with the enclosing graph until this object is
606 * {@linkplain #close() closed}.
607 */
608 public final class NodeEventScope implements AutoCloseable {
609 NodeEventScope(NodeEventListener listener) {
610 if (nodeEventListener == null) {
611 nodeEventListener = listener;
612 } else {
613 nodeEventListener = new ChainedNodeEventListener(listener, nodeEventListener);
614 }
615 }
616
617 @Override
618 public void close() {
619 assert nodeEventListener != null;
620 if (nodeEventListener instanceof ChainedNodeEventListener) {
621 nodeEventListener = ((ChainedNodeEventListener) nodeEventListener).next;
622 } else {
623 nodeEventListener = null;
624 }
625 }
626 }
627
628 private static class ChainedNodeEventListener extends NodeEventListener {
629
630 NodeEventListener head;
631 NodeEventListener next;
632
633 ChainedNodeEventListener(NodeEventListener head, NodeEventListener next) {
634 this.head = head;
635 this.next = next;
636 }
637
638 @Override
639 public void nodeAdded(Node node) {
640 head.event(NodeEvent.NODE_ADDED, node);
641 next.event(NodeEvent.NODE_ADDED, node);
642 }
643
644 @Override
645 public void inputChanged(Node node) {
646 head.event(NodeEvent.INPUT_CHANGED, node);
647 next.event(NodeEvent.INPUT_CHANGED, node);
648 }
649
650 @Override
651 public void usagesDroppedToZero(Node node) {
652 head.event(NodeEvent.ZERO_USAGES, node);
653 next.event(NodeEvent.ZERO_USAGES, node);
654 }
655
656 @Override
657 public void nodeRemoved(Node node) {
658 head.event(NodeEvent.NODE_REMOVED, node);
659 next.event(NodeEvent.NODE_REMOVED, node);
660 }
661
662 @Override
663 public void changed(NodeEvent e, Node node) {
664 head.event(e, node);
665 next.event(e, node);
666 }
667 }
668
669 /**
670 * Registers a given {@link NodeEventListener} with this graph. This should be used in
671 * conjunction with try-with-resources statement as follows:
672 *
673 * <pre>
674 * try (NodeEventScope nes = graph.trackNodeEvents(listener)) {
675 * // make changes to the graph
676 * }
677 * </pre>
678 */
679 public NodeEventScope trackNodeEvents(NodeEventListener listener) {
680 return new NodeEventScope(listener);
681 }
682
683 /**
684 * Looks for a node <i>similar</i> to {@code node} and returns it if found. Otherwise
685 * {@code node} is added to this graph and returned.
686 *
687 * @return a node similar to {@code node} if one exists, otherwise {@code node}
688 */
689 public <T extends Node & ValueNumberable> T unique(T node) {
690 return uniqueHelper(node);
691 }
692
693 <T extends Node> T uniqueHelper(T node) {
694 assert node.getNodeClass().valueNumberable();
695 T other = this.findDuplicate(node);
696 if (other != null) {
697 return other;
698 } else {
699 T result = addHelper(node);
700 if (node.getNodeClass().isLeafNode()) {
701 putNodeIntoCache(result);
702 }
703 return result;
704 }
705 }
706
707 void removeNodeFromCache(Node node) {
708 assert node.graph() == this || node.graph() == null;
709 assert node.getNodeClass().valueNumberable();
710 assert node.getNodeClass().isLeafNode() : node.getClass();
711
712 int leafId = node.getNodeClass().getLeafId();
713 if (cachedLeafNodes != null && cachedLeafNodes.length > leafId && cachedLeafNodes[leafId] != null) {
714 cachedLeafNodes[leafId].removeKey(node);
715 }
716 }
717
718 @SuppressWarnings({"unchecked", "rawtypes"})
719 void putNodeIntoCache(Node node) {
720 assert node.graph() == this || node.graph() == null;
721 assert node.getNodeClass().valueNumberable();
722 assert node.getNodeClass().isLeafNode() : node.getClass();
723
724 int leafId = node.getNodeClass().getLeafId();
725 if (cachedLeafNodes == null || cachedLeafNodes.length <= leafId) {
726 EconomicMap[] newLeafNodes = new EconomicMap[leafId + 1];
727 if (cachedLeafNodes != null) {
728 System.arraycopy(cachedLeafNodes, 0, newLeafNodes, 0, cachedLeafNodes.length);
729 }
730 cachedLeafNodes = newLeafNodes;
731 }
732
733 if (cachedLeafNodes[leafId] == null) {
734 cachedLeafNodes[leafId] = EconomicMap.create(NODE_VALUE_COMPARE);
735 }
736
737 cachedLeafNodes[leafId].put(node, node);
738 }
739
740 Node findNodeInCache(Node node) {
741 int leafId = node.getNodeClass().getLeafId();
742 if (cachedLeafNodes == null || cachedLeafNodes.length <= leafId || cachedLeafNodes[leafId] == null) {
743 return null;
744 }
745
746 Node result = cachedLeafNodes[leafId].get(node);
747 assert result == null || result.isAlive() : result;
748 return result;
749 }
750
751 /**
752 * Returns a possible duplicate for the given node in the graph or {@code null} if no such
753 * duplicate exists.
754 */
755 @SuppressWarnings("unchecked")
756 public <T extends Node> T findDuplicate(T node) {
757 NodeClass<?> nodeClass = node.getNodeClass();
758 assert nodeClass.valueNumberable();
759 if (nodeClass.isLeafNode()) {
760 // Leaf node: look up in cache
761 Node cachedNode = findNodeInCache(node);
762 if (cachedNode != null && cachedNode != node) {
763 return (T) cachedNode;
764 } else {
765 return null;
766 }
767 } else {
768 /*
769 * Non-leaf node: look for another usage of the node's inputs that has the same data,
770 * inputs and successors as the node. To reduce the cost of this computation, only the
771 * input with lowest usage count is considered. If this node is the only user of any
772 * input then the search can terminate early. The usage count is only incremented once
773 * the Node is in the Graph, so account for that in the test.
774 */
775 final int earlyExitUsageCount = node.graph() != null ? 1 : 0;
776 int minCount = Integer.MAX_VALUE;
777 Node minCountNode = null;
778 for (Node input : node.inputs()) {
779 int usageCount = input.getUsageCount();
780 if (usageCount == earlyExitUsageCount) {
781 return null;
782 } else if (usageCount < minCount) {
783 minCount = usageCount;
784 minCountNode = input;
785 }
786 }
787 if (minCountNode != null) {
788 for (Node usage : minCountNode.usages()) {
789 if (usage != node && nodeClass == usage.getNodeClass() && node.valueEquals(usage) && nodeClass.equalInputs(node, usage) &&
790 nodeClass.equalSuccessors(node, usage)) {
791 return (T) usage;
792 }
793 }
794 return null;
795 }
796 return null;
797 }
798 }
799
800 public boolean isNew(Mark mark, Node node) {
801 return node.id >= mark.getValue();
802 }
803
804 /**
805 * A snapshot of the {@linkplain Graph#getNodeCount() live node count} in a graph.
806 */
807 public static class Mark extends NodeIdAccessor {
808 private final int value;
809
810 Mark(Graph graph) {
811 super(graph);
812 this.value = graph.nodeIdCount();
813 }
814
815 @Override
816 public boolean equals(Object obj) {
817 if (obj instanceof Mark) {
818 Mark other = (Mark) obj;
819 return other.getValue() == getValue() && other.getGraph() == getGraph();
820 }
821 return false;
822 }
823
824 @Override
825 public int hashCode() {
826 return value ^ (epoch + 11);
827 }
828
829 /**
830 * Determines if this mark is positioned at the first live node in the graph.
831 */
832 public boolean isStart() {
833 return value == 0;
834 }
835
836 /**
837 * Gets the {@linkplain Graph#getNodeCount() live node count} of the associated graph when
838 * this object was created.
839 */
840 int getValue() {
841 return value;
842 }
843
844 /**
845 * Determines if this mark still represents the {@linkplain Graph#getNodeCount() live node
846 * count} of the graph.
847 */
848 public boolean isCurrent() {
849 return value == graph.nodeIdCount();
850 }
851 }
852
853 /**
854 * Gets a mark that can be used with {@link #getNewNodes}.
855 */
856 public Mark getMark() {
857 return new Mark(this);
858 }
859
860 /**
861 * Returns an {@link Iterable} providing all nodes added since the last {@link Graph#getMark()
862 * mark}.
863 */
864 public NodeIterable<Node> getNewNodes(Mark mark) {
865 final int index = mark == null ? 0 : mark.getValue();
866 return new NodeIterable<Node>() {
867
868 @Override
869 public Iterator<Node> iterator() {
870 return new GraphNodeIterator(Graph.this, index);
871 }
872 };
873 }
874
875 /**
876 * Returns an {@link Iterable} providing all the live nodes.
877 *
878 * @return an {@link Iterable} providing all the live nodes.
879 */
880 public NodeIterable<Node> getNodes() {
881 return new NodeIterable<Node>() {
882
883 @Override
884 public Iterator<Node> iterator() {
885 return new GraphNodeIterator(Graph.this);
886 }
887
888 @Override
889 public int count() {
890 return getNodeCount();
891 }
892 };
893 }
894
895 // Fully qualified annotation name is required to satisfy javac
896 @org.graalvm.compiler.nodeinfo.NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED)
897 static final class PlaceHolderNode extends Node {
898
899 public static final NodeClass<PlaceHolderNode> TYPE = NodeClass.create(PlaceHolderNode.class);
900
901 protected PlaceHolderNode() {
902 super(TYPE);
903 }
904
905 }
906
907 private static final CounterKey GraphCompressions = DebugContext.counter("GraphCompressions");
908
909 /**
910 * If the {@linkplain Options#GraphCompressionThreshold compression threshold} is met, the list
911 * of nodes is compressed such that all non-null entries precede all null entries while
912 * preserving the ordering between the nodes within the list.
913 */
914 public boolean maybeCompress() {
915 if (debug.isDumpEnabledForMethod() || debug.isLogEnabledForMethod()) {
916 return false;
917 }
918 int liveNodeCount = getNodeCount();
919 int liveNodePercent = liveNodeCount * 100 / nodesSize;
920 int compressionThreshold = Options.GraphCompressionThreshold.getValue(options);
921 if (compressionThreshold == 0 || liveNodePercent >= compressionThreshold) {
922 return false;
923 }
924 GraphCompressions.increment(debug);
925 int nextId = 0;
926 for (int i = 0; nextId < liveNodeCount; i++) {
927 Node n = nodes[i];
928 if (n != null) {
929 assert n.id == i;
930 if (i != nextId) {
931 assert n.id > nextId;
932 n.id = nextId;
933 nodes[nextId] = n;
934 nodes[i] = null;
935 }
936 nextId++;
937 }
938 }
939 if (isModificationCountsEnabled()) {
940 // This will cause any current iteration to fail with an assertion
941 Arrays.fill(nodeModCounts, 0);
942 Arrays.fill(nodeUsageModCounts, 0);
943 }
944 nodesSize = nextId;
945 compressions++;
946 nodesDeletedBeforeLastCompression += nodesDeletedSinceLastCompression;
947 nodesDeletedSinceLastCompression = 0;
948 return true;
949 }
950
951 /**
952 * Returns an {@link Iterable} providing all the live nodes whose type is compatible with
953 * {@code type}.
954 *
955 * @param nodeClass the type of node to return
956 * @return an {@link Iterable} providing all the matching nodes
957 */
958 public <T extends Node & IterableNodeType> NodeIterable<T> getNodes(final NodeClass<T> nodeClass) {
959 return new NodeIterable<T>() {
960
961 @Override
962 public Iterator<T> iterator() {
963 return new TypedGraphNodeIterator<>(nodeClass, Graph.this);
964 }
965 };
966 }
967
968 /**
969 * Returns whether the graph contains at least one node of the given type.
970 *
971 * @param type the type of node that is checked for occurrence
972 * @return whether there is at least one such node
973 */
974 public <T extends Node & IterableNodeType> boolean hasNode(final NodeClass<T> type) {
975 return getNodes(type).iterator().hasNext();
976 }
977
978 /**
979 * @param iterableId
980 * @return the first live Node with a matching iterableId
981 */
982 Node getIterableNodeStart(int iterableId) {
983 if (iterableNodesFirst.size() <= iterableId) {
984 return null;
985 }
986 Node start = iterableNodesFirst.get(iterableId);
987 if (start == null || !start.isDeleted()) {
988 return start;
989 }
990 return findFirstLiveIterable(iterableId, start);
991 }
992
993 private Node findFirstLiveIterable(int iterableId, Node node) {
994 Node start = node;
995 while (start != null && start.isDeleted()) {
996 start = start.typeCacheNext;
997 }
998 /*
999 * Multiple threads iterating nodes can update this cache simultaneously. This is a benign
1000 * race, since all threads update it to the same value.
1001 */
1002 iterableNodesFirst.set(iterableId, start);
1003 if (start == null) {
1004 iterableNodesLast.set(iterableId, start);
1005 }
1006 return start;
1007 }
1008
1009 /**
1010 * @param node
1011 * @return return the first live Node with a matching iterableId starting from {@code node}
1012 */
1013 Node getIterableNodeNext(Node node) {
1014 if (node == null) {
1015 return null;
1016 }
1017 Node n = node;
1018 if (n == null || !n.isDeleted()) {
1019 return n;
1020 }
1021
1022 return findNextLiveiterable(node);
1023 }
1024
1025 private Node findNextLiveiterable(Node start) {
1026 Node n = start;
1027 while (n != null && n.isDeleted()) {
1028 n = n.typeCacheNext;
1029 }
1030 if (n == null) {
1031 // Only dead nodes after this one
1032 start.typeCacheNext = null;
1033 int nodeClassId = start.getNodeClass().iterableId();
1034 assert nodeClassId != Node.NOT_ITERABLE;
1035 iterableNodesLast.set(nodeClassId, start);
1036 } else {
1037 // Everything in between is dead
1038 start.typeCacheNext = n;
1039 }
1040 return n;
1041 }
1042
1043 public NodeBitMap createNodeBitMap() {
1044 return new NodeBitMap(this);
1045 }
1046
1047 public <T> NodeMap<T> createNodeMap() {
1048 return new NodeMap<>(this);
1049 }
1050
1051 public NodeFlood createNodeFlood() {
1052 return new NodeFlood(this);
1053 }
1054
1055 public NodeWorkList createNodeWorkList() {
1056 return new NodeWorkList.SingletonNodeWorkList(this);
1057 }
1058
1059 public NodeWorkList createIterativeNodeWorkList(boolean fill, int iterationLimitPerNode) {
1060 return new NodeWorkList.IterativeNodeWorkList(this, fill, iterationLimitPerNode);
1061 }
1062
1063 void register(Node node) {
1064 assert !isFrozen();
1065 assert node.id() == Node.INITIAL_ID;
1066 if (nodes.length == nodesSize) {
1067 grow();
1068 }
1069 int id = nodesSize++;
1070 nodes[id] = node;
1071 node.id = id;
1072 if (currentNodeSourcePosition != null) {
1073 node.setNodeSourcePosition(currentNodeSourcePosition);
1074 }
1075 seenNodeSourcePosition = seenNodeSourcePosition || node.getNodeSourcePosition() != null;
1076
1077 updateNodeCaches(node);
1078
1079 if (nodeEventListener != null) {
1080 nodeEventListener.event(NodeEvent.NODE_ADDED, node);
1081 }
1082 afterRegister(node);
1083 }
1084
1085 private void grow() {
1086 Node[] newNodes = new Node[(nodesSize * 2) + 1];
1087 System.arraycopy(nodes, 0, newNodes, 0, nodesSize);
1088 nodes = newNodes;
1089 }
1090
1091 @SuppressWarnings("unused")
1092 protected void afterRegister(Node node) {
1093
1094 }
1095
1096 @SuppressWarnings("unused")
1097 private void postDeserialization() {
1098 recomputeIterableNodeLists();
1099 }
1100
1101 /**
1102 * Rebuilds the lists used to support {@link #getNodes(NodeClass)}. This is useful for
1103 * serialization where the underlying {@linkplain NodeClass#iterableId() iterable ids} may have
1104 * changed.
1105 */
1106 private void recomputeIterableNodeLists() {
1107 iterableNodesFirst.clear();
1108 iterableNodesLast.clear();
1109 for (Node node : nodes) {
1110 if (node != null && node.isAlive()) {
1111 updateNodeCaches(node);
1112 }
1113 }
1114 }
1115
1116 private void updateNodeCaches(Node node) {
1117 int nodeClassId = node.getNodeClass().iterableId();
1118 if (nodeClassId != Node.NOT_ITERABLE) {
1119 while (iterableNodesFirst.size() <= nodeClassId) {
1120 iterableNodesFirst.add(null);
1121 iterableNodesLast.add(null);
1122 }
1123 Node prev = iterableNodesLast.get(nodeClassId);
1124 if (prev != null) {
1125 prev.typeCacheNext = node;
1126 } else {
1127 iterableNodesFirst.set(nodeClassId, node);
1128 }
1129 iterableNodesLast.set(nodeClassId, node);
1130 }
1131 }
1132
1133 void unregister(Node node) {
1134 assert !isFrozen();
1135 assert !node.isDeleted() : node;
1136 if (node.getNodeClass().isLeafNode() && node.getNodeClass().valueNumberable()) {
1137 removeNodeFromCache(node);
1138 }
1139 nodes[node.id] = null;
1140 nodesDeletedSinceLastCompression++;
1141
1142 if (nodeEventListener != null) {
1143 nodeEventListener.event(NodeEvent.NODE_ADDED, node);
1144 }
1145
1146 // nodes aren't removed from the type cache here - they will be removed during iteration
1147 }
1148
1149 public boolean verify() {
1150 if (Options.VerifyGraalGraphs.getValue(options)) {
1151 for (Node node : getNodes()) {
1152 try {
1153 try {
1154 assert node.verify();
1155 } catch (AssertionError t) {
1156 throw new GraalError(t);
1157 } catch (RuntimeException t) {
1158 throw new GraalError(t);
1159 }
1160 } catch (GraalError e) {
1161 throw GraalGraphError.transformAndAddContext(e, node).addContext(this);
1162 }
1163 }
1164 }
1165 return true;
1166 }
1167
1168 public Node getNode(int id) {
1169 return nodes[id];
1170 }
1171
1172 /**
1173 * Returns the number of node ids generated so far.
1174 *
1175 * @return the number of node ids generated so far
1176 */
1177 int nodeIdCount() {
1178 return nodesSize;
1179 }
1180
1181 /**
1182 * Adds duplicates of the nodes in {@code newNodes} to this graph. This will recreate any edges
1183 * between the duplicate nodes. The {@code replacement} map can be used to replace a node from
1184 * the source graph by a given node (which must already be in this graph). Edges between
1185 * duplicate and replacement nodes will also be recreated so care should be taken regarding the
1186 * matching of node types in the replacement map.
1187 *
1188 * @param newNodes the nodes to be duplicated
1189 * @param replacementsMap the replacement map (can be null if no replacement is to be performed)
1190 * @return a map which associates the original nodes from {@code nodes} to their duplicates
1191 */
1192 public UnmodifiableEconomicMap<Node, Node> addDuplicates(Iterable<? extends Node> newNodes, final Graph oldGraph, int estimatedNodeCount, EconomicMap<Node, Node> replacementsMap) {
1193 DuplicationReplacement replacements;
1194 if (replacementsMap == null) {
1195 replacements = null;
1196 } else {
1197 replacements = new MapReplacement(replacementsMap);
1198 }
1199 return addDuplicates(newNodes, oldGraph, estimatedNodeCount, replacements);
1200 }
1201
1202 public interface DuplicationReplacement {
1203
1204 Node replacement(Node original);
1205 }
1206
1207 private static final class MapReplacement implements DuplicationReplacement {
1208
1209 private final EconomicMap<Node, Node> map;
1210
1211 MapReplacement(EconomicMap<Node, Node> map) {
1212 this.map = map;
1213 }
1214
1215 @Override
1216 public Node replacement(Node original) {
1217 Node replacement = map.get(original);
1218 return replacement != null ? replacement : original;
1219 }
1220
1221 }
1222
1223 private static final TimerKey DuplicateGraph = DebugContext.timer("DuplicateGraph");
1224
1225 @SuppressWarnings({"all", "try"})
1226 public EconomicMap<Node, Node> addDuplicates(Iterable<? extends Node> newNodes, final Graph oldGraph, int estimatedNodeCount, DuplicationReplacement replacements) {
1227 try (DebugCloseable s = DuplicateGraph.start(getDebug())) {
1228 return NodeClass.addGraphDuplicate(this, oldGraph, estimatedNodeCount, newNodes, replacements);
1229 }
1230 }
1231
1232 public boolean isFrozen() {
1233 return freezeState != FreezeState.Unfrozen;
1234 }
1235
1236 public void freeze() {
1237 this.freezeState = FreezeState.DeepFreeze;
1238 }
1239
1240 public void temporaryFreeze() {
1241 if (this.freezeState == FreezeState.DeepFreeze) {
1242 throw new GraalError("Graph was permanetly frozen.");
1243 }
1244 this.freezeState = FreezeState.TemporaryFreeze;
1245 }
1246
1247 public void unfreeze() {
1248 if (this.freezeState == FreezeState.DeepFreeze) {
1249 throw new GraalError("Graph was permanetly frozen.");
1250 }
1251 this.freezeState = FreezeState.Unfrozen;
1252 }
1253 }