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