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