1 /*
2 * Copyright (c) 2013, 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.ArrayList;
26 import java.util.Map;
27 import java.util.function.ToDoubleFunction;
28
29 import org.graalvm.compiler.core.common.SuppressFBWarnings;
30 import org.graalvm.compiler.graph.Node;
31 import org.graalvm.compiler.graph.NodeWorkList;
32 import org.graalvm.compiler.nodes.AbstractBeginNode;
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.LoopExitNode;
43 import org.graalvm.compiler.nodes.MergeNode;
44 import org.graalvm.compiler.nodes.StartNode;
45 import org.graalvm.compiler.nodes.StructuredGraph;
46 import org.graalvm.compiler.phases.common.inlining.InliningUtil;
47
48 public class ComputeInliningRelevance {
49
50 private static final double EPSILON = 1d / Integer.MAX_VALUE;
51 private static final double UNINITIALIZED = -1D;
52
53 private static final int EXPECTED_MIN_INVOKE_COUNT = 3;
54 private static final int EXPECTED_INVOKE_RATIO = 20;
55 private static final int EXPECTED_LOOP_COUNT = 3;
56
57 private final StructuredGraph graph;
58 private final ToDoubleFunction<FixedNode> nodeProbabilities;
59
60 /**
61 * Node relevances are pre-computed for all invokes if the graph contains loops. If there are no
62 * loops, the computation happens lazily based on {@link #rootScope}.
63 */
64 private Map<FixedNode, Double> nodeRelevances;
65 /**
66 * This scope is non-null if (and only if) there are no loops in the graph. In this case, the
67 * root scope is used to compute invoke relevances on the fly.
68 */
69 private Scope rootScope;
70
71 public ComputeInliningRelevance(StructuredGraph graph, ToDoubleFunction<FixedNode> nodeProbabilities) {
72 this.graph = graph;
73 this.nodeProbabilities = nodeProbabilities;
74 }
75
76 /**
77 * Initializes or updates the relevance computation. If there are no loops within the graph,
78 * most computation happens lazily.
79 */
80 public void compute() {
81 rootScope = null;
82 if (!graph.hasLoops()) {
83 // fast path for the frequent case of no loops
84 rootScope = new Scope(graph.start(), null);
85 } else {
86 if (nodeRelevances == null) {
87 nodeRelevances = Node.newIdentityMap(EXPECTED_MIN_INVOKE_COUNT + InliningUtil.getNodeCount(graph) / EXPECTED_INVOKE_RATIO);
88 }
89 NodeWorkList workList = graph.createNodeWorkList();
90 Map<LoopBeginNode, Scope> loops = Node.newIdentityMap(EXPECTED_LOOP_COUNT);
91
92 loops.put(null, new Scope(graph.start(), null));
93 for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.TYPE)) {
94 createLoopScope(loopBegin, loops);
95 }
96
97 for (Scope scope : loops.values()) {
98 scope.process(workList);
99 }
100 }
101 }
102
103 public double getRelevance(Invoke invoke) {
104 if (rootScope != null) {
105 return rootScope.computeInvokeRelevance(invoke);
106 }
107 assert nodeRelevances != null : "uninitialized relevance";
108 return nodeRelevances.get(invoke);
109 }
110
111 /**
112 * Determines the parent of the given loop and creates a {@link Scope} object for each one. This
113 * method will call itself recursively if no {@link Scope} for the parent loop exists.
114 */
115 private Scope createLoopScope(LoopBeginNode loopBegin, Map<LoopBeginNode, Scope> loops) {
116 Scope scope = loops.get(loopBegin);
117 if (scope == null) {
118 final Scope parent;
119 // look for the parent scope
120 FixedNode current = loopBegin.forwardEnd();
121 while (true) {
122 if (current.predecessor() == null) {
123 if (current instanceof LoopBeginNode) {
124 // if we reach a LoopBeginNode then we're within this loop
125 parent = createLoopScope((LoopBeginNode) current, loops);
126 break;
127 } else if (current instanceof StartNode) {
128 // we're within the outermost scope
129 parent = loops.get(null);
130 break;
131 } else {
132 assert current instanceof MergeNode : current;
133 // follow any path upwards - it doesn't matter which one
134 current = ((AbstractMergeNode) current).forwardEndAt(0);
135 }
136 } else if (current instanceof LoopExitNode) {
137 // if we reach a loop exit then we follow this loop and have the same parent
138 parent = createLoopScope(((LoopExitNode) current).loopBegin(), loops).parent;
139 break;
140 } else {
141 current = (FixedNode) current.predecessor();
142 }
143 }
144 scope = new Scope(loopBegin, parent);
145 loops.put(loopBegin, scope);
146 }
147 return scope;
148 }
149
150 /**
151 * A scope holds information for the contents of one loop or of the root of the method. It does
152 * not include child loops, i.e., the iteration in {@link #process(NodeWorkList)} explicitly
153 * excludes the nodes of child loops.
154 */
155 private class Scope {
156 public final FixedNode start;
157 public final Scope parent; // can be null for the outermost scope
158
159 /**
160 * The minimum probability along the most probable path in this scope. Computed lazily.
161 */
162 private double fastPathMinProbability = UNINITIALIZED;
163 /**
164 * A measure of how important this scope is within its parent scope. Computed lazily.
165 */
166 private double scopeRelevanceWithinParent = UNINITIALIZED;
167
168 Scope(FixedNode start, Scope parent) {
169 this.start = start;
170 this.parent = parent;
171 }
172
173 @SuppressFBWarnings(value = "FE_FLOATING_POINT_EQUALITY", justification = "comparing against -1D is accurate")
174 public double getFastPathMinProbability() {
175 if (fastPathMinProbability == UNINITIALIZED) {
176 fastPathMinProbability = Math.max(EPSILON, computeFastPathMinProbability(start));
177 }
178 return fastPathMinProbability;
179 }
180
181 /**
182 * Computes the ratio between the probabilities of the current scope's entry point and the
183 * parent scope's fastPathMinProbability.
184 */
185 @SuppressFBWarnings(value = "FE_FLOATING_POINT_EQUALITY", justification = "comparing against -1D is accurate")
186 public double getScopeRelevanceWithinParent() {
187 if (scopeRelevanceWithinParent == UNINITIALIZED) {
188 if (start instanceof LoopBeginNode) {
189 assert parent != null;
190 double scopeEntryProbability = nodeProbabilities.applyAsDouble(((LoopBeginNode) start).forwardEnd());
191
192 scopeRelevanceWithinParent = scopeEntryProbability / parent.getFastPathMinProbability();
193 } else {
194 scopeRelevanceWithinParent = 1D;
195 }
196 }
197 return scopeRelevanceWithinParent;
198 }
199
200 /**
201 * Processes all invokes in this scope by starting at the scope's start node and iterating
202 * all fixed nodes. Child loops are skipped by going from loop entries directly to the loop
203 * exits. Processing stops at loop exits of the current loop.
204 */
205 public void process(NodeWorkList workList) {
206 assert !(start instanceof Invoke);
207 workList.addAll(start.successors());
208
209 for (Node current : workList) {
210 assert current.isAlive();
211
212 if (current instanceof Invoke) {
213 // process the invoke and queue its successors
214 nodeRelevances.put((FixedNode) current, computeInvokeRelevance((Invoke) current));
215 workList.addAll(current.successors());
216 } else if (current instanceof LoopBeginNode) {
217 // skip child loops by advancing over the loop exits
218 ((LoopBeginNode) current).loopExits().forEach(exit -> workList.add(exit.next()));
219 } else if (current instanceof LoopEndNode) {
220 // nothing to do
221 } else if (current instanceof LoopExitNode) {
222 // nothing to do
223 } else if (current instanceof FixedWithNextNode) {
224 workList.add(((FixedWithNextNode) current).next());
225 } else if (current instanceof EndNode) {
226 workList.add(((EndNode) current).merge());
227 } else if (current instanceof ControlSinkNode) {
228 // nothing to do
229 } else if (current instanceof ControlSplitNode) {
230 workList.addAll(current.successors());
231 } else {
232 assert false : current;
233 }
234 }
235 }
236
237 /**
238 * The relevance of an invoke is the ratio between the invoke's probability and the current
239 * scope's fastPathMinProbability, adjusted by scopeRelevanceWithinParent.
240 */
241 public double computeInvokeRelevance(Invoke invoke) {
242 double invokeProbability = nodeProbabilities.applyAsDouble(invoke.asNode());
243 assert !Double.isNaN(invokeProbability);
244
245 double relevance = (invokeProbability / getFastPathMinProbability()) * Math.min(1.0, getScopeRelevanceWithinParent());
246 assert !Double.isNaN(relevance) : invoke + ": " + relevance + " / " + invokeProbability + " / " + getFastPathMinProbability() + " / " + getScopeRelevanceWithinParent();
247 return relevance;
248 }
249 }
250
251 /**
252 * Computes the minimum probability along the most probable path within the scope. During
253 * iteration, the method returns immediately once a loop exit is discovered.
254 */
255 private double computeFastPathMinProbability(FixedNode scopeStart) {
256 ArrayList<FixedNode> pathBeginNodes = new ArrayList<>();
257 pathBeginNodes.add(scopeStart);
258 double minPathProbability = nodeProbabilities.applyAsDouble(scopeStart);
259 boolean isLoopScope = scopeStart instanceof LoopBeginNode;
260
261 do {
262 Node current = pathBeginNodes.remove(pathBeginNodes.size() - 1);
263 do {
264 if (isLoopScope && current instanceof LoopExitNode && ((LoopBeginNode) scopeStart).loopExits().contains((LoopExitNode) current)) {
265 return minPathProbability;
266 } else if (current instanceof LoopBeginNode && current != scopeStart) {
267 current = getMaxProbabilityLoopExit((LoopBeginNode) current, pathBeginNodes);
268 minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability);
269 } else if (current instanceof ControlSplitNode) {
270 current = getMaxProbabilitySux((ControlSplitNode) current, pathBeginNodes);
271 minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability);
272 } else {
273 assert current.successors().count() <= 1;
274 current = current.successors().first();
275 }
276 } while (current != null);
277 } while (!pathBeginNodes.isEmpty());
278
279 return minPathProbability;
280 }
281
282 private double getMinPathProbability(FixedNode current, double minPathProbability) {
283 return current == null ? minPathProbability : Math.min(minPathProbability, nodeProbabilities.applyAsDouble(current));
284 }
285
286 /**
287 * Returns the most probable successor. If multiple successors share the maximum probability,
288 * one is returned and the others are enqueued in pathBeginNodes.
289 */
290 private static Node getMaxProbabilitySux(ControlSplitNode controlSplit, ArrayList<FixedNode> pathBeginNodes) {
291 Node maxSux = null;
292 double maxProbability = 0.0;
293 int pathBeginCount = pathBeginNodes.size();
294
295 for (Node sux : controlSplit.successors()) {
296 double probability = controlSplit.probability((AbstractBeginNode) sux);
297 if (probability > maxProbability) {
298 maxProbability = probability;
299 maxSux = sux;
300 truncate(pathBeginNodes, pathBeginCount);
301 } else if (probability == maxProbability) {
302 pathBeginNodes.add((FixedNode) sux);
303 }
304 }
305
306 return maxSux;
307 }
308
309 /**
310 * Returns the most probable loop exit. If multiple successors share the maximum probability,
311 * one is returned and the others are enqueued in pathBeginNodes.
312 */
313 private Node getMaxProbabilityLoopExit(LoopBeginNode loopBegin, ArrayList<FixedNode> pathBeginNodes) {
314 Node maxSux = null;
315 double maxProbability = 0.0;
316 int pathBeginCount = pathBeginNodes.size();
317
318 for (LoopExitNode sux : loopBegin.loopExits()) {
319 double probability = nodeProbabilities.applyAsDouble(sux);
320 if (probability > maxProbability) {
321 maxProbability = probability;
322 maxSux = sux;
323 truncate(pathBeginNodes, pathBeginCount);
324 } else if (probability == maxProbability) {
325 pathBeginNodes.add(sux);
326 }
327 }
328
329 return maxSux;
330 }
331
332 private static void truncate(ArrayList<FixedNode> pathBeginNodes, int pathBeginCount) {
333 for (int i = pathBeginNodes.size() - pathBeginCount; i > 0; i--) {
334 pathBeginNodes.remove(pathBeginNodes.size() - 1);
335 }
336 }
337 }