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
24
25 package org.graalvm.compiler.phases.common.inlining.walker;
26
27 import java.util.BitSet;
28 import java.util.LinkedList;
29 import java.util.function.ToDoubleFunction;
30
31 import jdk.internal.vm.compiler.collections.EconomicSet;
32 import jdk.internal.vm.compiler.collections.Equivalence;
33 import org.graalvm.compiler.nodes.FixedNode;
34 import org.graalvm.compiler.nodes.Invoke;
35 import org.graalvm.compiler.nodes.ParameterNode;
36 import org.graalvm.compiler.nodes.StructuredGraph;
37 import org.graalvm.compiler.nodes.ValueNode;
38 import org.graalvm.compiler.phases.common.inlining.policy.AbstractInliningPolicy;
39 import org.graalvm.compiler.phases.graph.FixedNodeProbabilityCache;
40
41 import jdk.vm.ci.meta.ResolvedJavaMethod;
42
43 /**
44 * <p>
45 * A {@link CallsiteHolder} whose graph has been copied already and thus can be modified without
46 * affecting the original (usually cached) version.
47 * </p>
48 *
49 * <p>
50 * An instance of this class is derived from an
51 * {@link org.graalvm.compiler.phases.common.inlining.info.elem.InlineableGraph InlineableGraph} and
52 * contains a subset of the information there: just the {@link Invoke} nodes from it. Such nodes are
53 * candidates for depth-first search of further inlining opportunities (thus the adjective
54 * "explorable" given to this class)
55 * </p>
56 *
57 * @see InliningData#moveForward()
58 */
59 public final class CallsiteHolderExplorable extends CallsiteHolder {
60
61 /**
62 * Graph in which inlining may be performed at one or more of the callsites containined in
63 * {@link #remainingInvokes}.
64 */
65 private final StructuredGraph graph;
66
67 private final LinkedList<Invoke> remainingInvokes;
68 private final double probability;
69 private final double relevance;
70
71 /**
72 * @see #getFixedParams()
73 */
74 private final EconomicSet<ParameterNode> fixedParams;
75
76 private final ToDoubleFunction<FixedNode> probabilities;
77 private final ComputeInliningRelevance computeInliningRelevance;
78
79 public CallsiteHolderExplorable(StructuredGraph graph, double probability, double relevance, BitSet freshlyInstantiatedArguments, LinkedList<Invoke> invokes) {
80 assert graph != null;
81 this.graph = graph;
82 this.probability = probability;
83 this.relevance = relevance;
84 this.fixedParams = fixedParamsAt(freshlyInstantiatedArguments);
85 remainingInvokes = invokes == null ? new InliningIterator(graph).apply() : invokes;
86 if (remainingInvokes.isEmpty()) {
87 probabilities = null;
88 computeInliningRelevance = null;
89 } else {
90 probabilities = new FixedNodeProbabilityCache();
91 computeInliningRelevance = new ComputeInliningRelevance(graph, probabilities);
92 computeProbabilities();
93 }
94 assert repOK();
95 }
96
97 /**
98 * @see #getFixedParams()
99 */
100 private EconomicSet<ParameterNode> fixedParamsAt(BitSet freshlyInstantiatedArguments) {
101 if (freshlyInstantiatedArguments == null || freshlyInstantiatedArguments.isEmpty()) {
102 return EconomicSet.create(Equivalence.IDENTITY);
103 }
104 EconomicSet<ParameterNode> result = EconomicSet.create(Equivalence.IDENTITY);
105 for (ParameterNode p : graph.getNodes(ParameterNode.TYPE)) {
106 if (freshlyInstantiatedArguments.get(p.index())) {
107 result.add(p);
108 }
109 }
110 return result;
111 }
112
113 /**
114 * <p>
115 * Parameters for which the callsite targeting {@link #graph()} provides "fixed" arguments. That
116 * callsite isn't referenced by this instance. Instead, it belongs to the graph of the caller of
117 * this {@link CallsiteHolderExplorable}
118 * </p>
119 *
120 * <p>
121 * Constant arguments don't contribute to fixed-params: those params have been removed already,
122 * see {@link org.graalvm.compiler.phases.common.inlining.info.elem.InlineableGraph}.
123 * </p>
124 *
125 * <p>
126 * Instead, fixed-params are those receiving freshly instantiated arguments (possibly
127 * instantiated several levels up in the call-hierarchy)
128 * </p>
129 */
130 public EconomicSet<ParameterNode> getFixedParams() {
131 return fixedParams;
132 }
133
134 public boolean repOK() {
135 for (Invoke invoke : remainingInvokes) {
136 if (!invoke.asNode().isAlive() || !containsInvoke(invoke)) {
137 assert false;
138 return false;
139 }
140 if (!allArgsNonNull(invoke)) {
141 assert false;
142 return false;
143 }
144 }
145 for (ParameterNode fixedParam : fixedParams) {
146 if (!containsParam(fixedParam)) {
147 assert false;
148 return false;
149 }
150 }
151 return true;
152 }
153
154 @Override
155 public ResolvedJavaMethod method() {
156 return graph == null ? null : graph.method();
157 }
158
159 @Override
160 public boolean hasRemainingInvokes() {
161 return !remainingInvokes.isEmpty();
162 }
163
164 @Override
165 public StructuredGraph graph() {
166 return graph;
167 }
168
169 public Invoke popInvoke() {
170 return remainingInvokes.removeFirst();
171 }
172
173 public void pushInvoke(Invoke invoke) {
174 remainingInvokes.push(invoke);
175 }
176
177 public static boolean allArgsNonNull(Invoke invoke) {
178 for (ValueNode arg : invoke.callTarget().arguments()) {
179 if (arg == null) {
180 assert false;
181 return false;
182 }
183 }
184 return true;
185 }
186
187 public boolean containsInvoke(Invoke invoke) {
188 for (Invoke i : graph().getInvokes()) {
189 if (i == invoke) {
190 return true;
191 }
192 }
193 return false;
194 }
195
196 public boolean containsParam(ParameterNode param) {
197 for (ParameterNode p : graph.getNodes(ParameterNode.TYPE)) {
198 if (p == param) {
199 return true;
200 }
201 }
202 return false;
203 }
204
205 public void computeProbabilities() {
206 computeInliningRelevance.compute();
207 }
208
209 public double invokeProbability(Invoke invoke) {
210 return probability * probabilities.applyAsDouble(invoke.asNode());
211 }
212
213 public double invokeRelevance(Invoke invoke) {
214 return Math.min(AbstractInliningPolicy.CapInheritedRelevance, relevance) * computeInliningRelevance.getRelevance(invoke);
215 }
216
217 @Override
218 public String toString() {
219 return (graph != null ? method().format("%H.%n(%p)") : "<null method>") + remainingInvokes;
220 }
221 }