1 /*
2 * Copyright (c) 2011, 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.phases.common.inlining.walker;
24
25 import java.util.ArrayDeque;
26 import java.util.Deque;
27 import java.util.Iterator;
28 import java.util.LinkedList;
29
30 import org.graalvm.compiler.graph.Node;
31 import org.graalvm.compiler.graph.NodeBitMap;
32 import org.graalvm.compiler.nodes.AbstractEndNode;
33 import org.graalvm.compiler.nodes.AbstractMergeNode;
34 import org.graalvm.compiler.nodes.ControlSinkNode;
35 import org.graalvm.compiler.nodes.ControlSplitNode;
36 import org.graalvm.compiler.nodes.EndNode;
37 import org.graalvm.compiler.nodes.FixedNode;
38 import org.graalvm.compiler.nodes.FixedWithNextNode;
39 import org.graalvm.compiler.nodes.Invoke;
40 import org.graalvm.compiler.nodes.LoopBeginNode;
41 import org.graalvm.compiler.nodes.LoopEndNode;
42 import org.graalvm.compiler.nodes.StartNode;
43 import org.graalvm.compiler.nodes.StructuredGraph;
44 import org.graalvm.compiler.nodes.java.MethodCallTargetNode;
45
46 /**
47 * Given a graph, visit all fixed nodes in dominator-based order, collecting in the process the
48 * {@link Invoke} nodes with {@link MethodCallTargetNode}. Such list of callsites is returned by
49 * {@link #apply()}
50 */
51 public class InliningIterator {
52
53 private final StartNode start;
54 private final Deque<FixedNode> nodeQueue;
55 private final NodeBitMap queuedNodes;
56
57 public InliningIterator(StructuredGraph graph) {
58 this.start = graph.start();
59 this.nodeQueue = new ArrayDeque<>();
60 this.queuedNodes = graph.createNodeBitMap();
61 assert start.isAlive();
62 }
63
64 public LinkedList<Invoke> apply() {
65 LinkedList<Invoke> invokes = new LinkedList<>();
66 FixedNode current;
67 forcedQueue(start);
68
69 while ((current = nextQueuedNode()) != null) {
70 assert current.isAlive();
71
72 if (current instanceof Invoke && ((Invoke) current).callTarget() instanceof MethodCallTargetNode) {
73 if (current != start) {
74 invokes.addLast((Invoke) current);
75 }
76 queueSuccessors(current);
77 } else if (current instanceof LoopBeginNode) {
78 queueSuccessors(current);
79 } else if (current instanceof LoopEndNode) {
80 // nothing to do
81 } else if (current instanceof AbstractMergeNode) {
82 queueSuccessors(current);
83 } else if (current instanceof FixedWithNextNode) {
84 queueSuccessors(current);
85 } else if (current instanceof EndNode) {
86 queueMerge((EndNode) current);
87 } else if (current instanceof ControlSinkNode) {
88 // nothing to do
89 } else if (current instanceof ControlSplitNode) {
90 queueSuccessors(current);
91 } else {
92 assert false : current;
93 }
94 }
95
96 assert invokes.size() == count(start.graph().getInvokes());
97 return invokes;
98 }
99
100 private void queueSuccessors(FixedNode x) {
101 for (Node node : x.successors()) {
102 queue(node);
103 }
104 }
105
106 private void queue(Node node) {
107 if (node != null && !queuedNodes.isMarked(node)) {
108 forcedQueue(node);
109 }
110 }
111
112 private void forcedQueue(Node node) {
113 queuedNodes.mark(node);
114 nodeQueue.addFirst((FixedNode) node);
115 }
116
117 private FixedNode nextQueuedNode() {
118 if (nodeQueue.isEmpty()) {
119 return null;
120 }
121
122 FixedNode result = nodeQueue.removeFirst();
123 assert queuedNodes.isMarked(result);
124 return result;
125 }
126
127 private void queueMerge(AbstractEndNode end) {
128 AbstractMergeNode merge = end.merge();
129 if (!queuedNodes.isMarked(merge) && visitedAllEnds(merge)) {
130 queuedNodes.mark(merge);
131 nodeQueue.add(merge);
132 }
133 }
134
135 private boolean visitedAllEnds(AbstractMergeNode merge) {
136 for (int i = 0; i < merge.forwardEndCount(); i++) {
137 if (!queuedNodes.isMarked(merge.forwardEndAt(i))) {
138 return false;
139 }
140 }
141 return true;
142 }
143
144 private static int count(Iterable<Invoke> invokes) {
145 int count = 0;
146 Iterator<Invoke> iterator = invokes.iterator();
147 while (iterator.hasNext()) {
148 iterator.next();
149 count++;
150 }
151 return count;
152 }
153 }