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