001/*
002 * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.phases.common.inlining.walker;
024
025import java.util.*;
026import java.util.function.*;
027
028import com.oracle.graal.compiler.common.*;
029import com.oracle.graal.graph.*;
030import com.oracle.graal.nodes.*;
031
032public class ComputeInliningRelevance {
033
034    private static final double EPSILON = 1d / Integer.MAX_VALUE;
035    private static final double UNINITIALIZED = -1D;
036
037    private static final int EXPECTED_MIN_INVOKE_COUNT = 3;
038    private static final int EXPECTED_INVOKE_RATIO = 20;
039    private static final int EXPECTED_LOOP_COUNT = 3;
040
041    private final StructuredGraph graph;
042    private final ToDoubleFunction<FixedNode> nodeProbabilities;
043
044    /**
045     * Node relevances are pre-computed for all invokes if the graph contains loops. If there are no
046     * loops, the computation happens lazily based on {@link #rootScope}.
047     */
048    private Map<FixedNode, Double> nodeRelevances;
049    /**
050     * This scope is non-null if (and only if) there are no loops in the graph. In this case, the
051     * root scope is used to compute invoke relevances on the fly.
052     */
053    private Scope rootScope;
054
055    public ComputeInliningRelevance(StructuredGraph graph, ToDoubleFunction<FixedNode> nodeProbabilities) {
056        this.graph = graph;
057        this.nodeProbabilities = nodeProbabilities;
058    }
059
060    /**
061     * Initializes or updates the relevance computation. If there are no loops within the graph,
062     * most computation happens lazily.
063     */
064    public void compute() {
065        rootScope = null;
066        if (!graph.hasLoops()) {
067            // fast path for the frequent case of no loops
068            rootScope = new Scope(graph.start(), null);
069        } else {
070            if (nodeRelevances == null) {
071                nodeRelevances = Node.newIdentityMap(EXPECTED_MIN_INVOKE_COUNT + graph.getNodeCount() / EXPECTED_INVOKE_RATIO);
072            }
073            NodeWorkList workList = graph.createNodeWorkList();
074            Map<LoopBeginNode, Scope> loops = Node.newIdentityMap(EXPECTED_LOOP_COUNT);
075
076            loops.put(null, new Scope(graph.start(), null));
077            for (LoopBeginNode loopBegin : graph.getNodes(LoopBeginNode.TYPE)) {
078                createLoopScope(loopBegin, loops);
079            }
080
081            for (Scope scope : loops.values()) {
082                scope.process(workList);
083            }
084        }
085    }
086
087    public double getRelevance(Invoke invoke) {
088        if (rootScope != null) {
089            return rootScope.computeInvokeRelevance(invoke);
090        }
091        assert nodeRelevances != null : "uninitialized relevance";
092        return nodeRelevances.get(invoke);
093    }
094
095    /**
096     * Determines the parent of the given loop and creates a {@link Scope} object for each one. This
097     * method will call itself recursively if no {@link Scope} for the parent loop exists.
098     */
099    private Scope createLoopScope(LoopBeginNode loopBegin, Map<LoopBeginNode, Scope> loops) {
100        Scope scope = loops.get(loopBegin);
101        if (scope == null) {
102            final Scope parent;
103            // look for the parent scope
104            FixedNode current = loopBegin.forwardEnd();
105            while (true) {
106                if (current.predecessor() == null) {
107                    if (current instanceof LoopBeginNode) {
108                        // if we reach a LoopBeginNode then we're within this loop
109                        parent = createLoopScope((LoopBeginNode) current, loops);
110                        break;
111                    } else if (current instanceof StartNode) {
112                        // we're within the outermost scope
113                        parent = loops.get(null);
114                        break;
115                    } else {
116                        assert current instanceof MergeNode : current;
117                        // follow any path upwards - it doesn't matter which one
118                        current = ((AbstractMergeNode) current).forwardEndAt(0);
119                    }
120                } else if (current instanceof LoopExitNode) {
121                    // if we reach a loop exit then we follow this loop and have the same parent
122                    parent = createLoopScope(((LoopExitNode) current).loopBegin(), loops).parent;
123                    break;
124                } else {
125                    current = (FixedNode) current.predecessor();
126                }
127            }
128            scope = new Scope(loopBegin, parent);
129            loops.put(loopBegin, scope);
130        }
131        return scope;
132    }
133
134    /**
135     * A scope holds information for the contents of one loop or of the root of the method. It does
136     * not include child loops, i.e., the iteration in {@link #process(NodeWorkList)} explicitly
137     * excludes the nodes of child loops.
138     */
139    private class Scope {
140        public final FixedNode start;
141        public final Scope parent; // can be null for the outermost scope
142
143        /**
144         * The minimum probability along the most probable path in this scope. Computed lazily.
145         */
146        private double fastPathMinProbability = UNINITIALIZED;
147        /**
148         * A measure of how important this scope is within its parent scope. Computed lazily.
149         */
150        private double scopeRelevanceWithinParent = UNINITIALIZED;
151
152        public Scope(FixedNode start, Scope parent) {
153            this.start = start;
154            this.parent = parent;
155        }
156
157        @SuppressFBWarnings(value = "FE_FLOATING_POINT_EQUALITY", justification = "comparing against -1D is accurate")
158        public double getFastPathMinProbability() {
159            if (fastPathMinProbability == UNINITIALIZED) {
160                fastPathMinProbability = Math.max(EPSILON, computeFastPathMinProbability(start));
161            }
162            return fastPathMinProbability;
163        }
164
165        /**
166         * Computes the ratio between the probabilities of the current scope's entry point and the
167         * parent scope's fastPathMinProbability.
168         */
169        @SuppressFBWarnings(value = "FE_FLOATING_POINT_EQUALITY", justification = "comparing against -1D is accurate")
170        public double getScopeRelevanceWithinParent() {
171            if (scopeRelevanceWithinParent == UNINITIALIZED) {
172                if (start instanceof LoopBeginNode) {
173                    assert parent != null;
174                    double scopeEntryProbability = nodeProbabilities.applyAsDouble(((LoopBeginNode) start).forwardEnd());
175
176                    scopeRelevanceWithinParent = scopeEntryProbability / parent.getFastPathMinProbability();
177                } else {
178                    scopeRelevanceWithinParent = 1D;
179                }
180            }
181            return scopeRelevanceWithinParent;
182        }
183
184        /**
185         * Processes all invokes in this scope by starting at the scope's start node and iterating
186         * all fixed nodes. Child loops are skipped by going from loop entries directly to the loop
187         * exits. Processing stops at loop exits of the current loop.
188         */
189        public void process(NodeWorkList workList) {
190            assert !(start instanceof Invoke);
191            workList.addAll(start.successors());
192
193            for (Node current : workList) {
194                assert current.isAlive();
195
196                if (current instanceof Invoke) {
197                    // process the invoke and queue its successors
198                    nodeRelevances.put((FixedNode) current, computeInvokeRelevance((Invoke) current));
199                    workList.addAll(current.successors());
200                } else if (current instanceof LoopBeginNode) {
201                    // skip child loops by advancing over the loop exits
202                    ((LoopBeginNode) current).loopExits().forEach(exit -> workList.add(exit.next()));
203                } else if (current instanceof LoopEndNode) {
204                    // nothing to do
205                } else if (current instanceof LoopExitNode) {
206                    // nothing to do
207                } else if (current instanceof FixedWithNextNode) {
208                    workList.add(((FixedWithNextNode) current).next());
209                } else if (current instanceof EndNode) {
210                    workList.add(((EndNode) current).merge());
211                } else if (current instanceof ControlSinkNode) {
212                    // nothing to do
213                } else if (current instanceof ControlSplitNode) {
214                    workList.addAll(current.successors());
215                } else {
216                    assert false : current;
217                }
218            }
219        }
220
221        /**
222         * The relevance of an invoke is the ratio between the invoke's probability and the current
223         * scope's fastPathMinProbability, adjusted by scopeRelevanceWithinParent.
224         */
225        public double computeInvokeRelevance(Invoke invoke) {
226            double invokeProbability = nodeProbabilities.applyAsDouble(invoke.asNode());
227            assert !Double.isNaN(invokeProbability);
228
229            double relevance = (invokeProbability / getFastPathMinProbability()) * Math.min(1.0, getScopeRelevanceWithinParent());
230            assert !Double.isNaN(relevance) : invoke + ": " + relevance + " / " + invokeProbability + " / " + getFastPathMinProbability() + " / " + getScopeRelevanceWithinParent();
231            return relevance;
232        }
233    }
234
235    /**
236     * Computes the minimum probability along the most probable path within the scope. During
237     * iteration, the method returns immediately once a loop exit is discovered.
238     */
239    private double computeFastPathMinProbability(FixedNode scopeStart) {
240        ArrayList<FixedNode> pathBeginNodes = new ArrayList<>();
241        pathBeginNodes.add(scopeStart);
242        double minPathProbability = nodeProbabilities.applyAsDouble(scopeStart);
243        boolean isLoopScope = scopeStart instanceof LoopBeginNode;
244
245        do {
246            Node current = pathBeginNodes.remove(pathBeginNodes.size() - 1);
247            do {
248                if (isLoopScope && current instanceof LoopExitNode && ((LoopBeginNode) scopeStart).loopExits().contains((LoopExitNode) current)) {
249                    return minPathProbability;
250                } else if (current instanceof LoopBeginNode && current != scopeStart) {
251                    current = getMaxProbabilityLoopExit((LoopBeginNode) current, pathBeginNodes);
252                    minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability);
253                } else if (current instanceof ControlSplitNode) {
254                    current = getMaxProbabilitySux((ControlSplitNode) current, pathBeginNodes);
255                    minPathProbability = getMinPathProbability((FixedNode) current, minPathProbability);
256                } else {
257                    assert current.successors().count() <= 1;
258                    current = current.successors().first();
259                }
260            } while (current != null);
261        } while (!pathBeginNodes.isEmpty());
262
263        return minPathProbability;
264    }
265
266    private double getMinPathProbability(FixedNode current, double minPathProbability) {
267        return current == null ? minPathProbability : Math.min(minPathProbability, nodeProbabilities.applyAsDouble(current));
268    }
269
270    /**
271     * Returns the most probable successor. If multiple successors share the maximum probability,
272     * one is returned and the others are enqueued in pathBeginNodes.
273     */
274    private static Node getMaxProbabilitySux(ControlSplitNode controlSplit, ArrayList<FixedNode> pathBeginNodes) {
275        Node maxSux = null;
276        double maxProbability = 0.0;
277        int pathBeginCount = pathBeginNodes.size();
278
279        for (Node sux : controlSplit.successors()) {
280            double probability = controlSplit.probability((AbstractBeginNode) sux);
281            if (probability > maxProbability) {
282                maxProbability = probability;
283                maxSux = sux;
284                truncate(pathBeginNodes, pathBeginCount);
285            } else if (probability == maxProbability) {
286                pathBeginNodes.add((FixedNode) sux);
287            }
288        }
289
290        return maxSux;
291    }
292
293    /**
294     * Returns the most probable loop exit. If multiple successors share the maximum probability,
295     * one is returned and the others are enqueued in pathBeginNodes.
296     */
297    private Node getMaxProbabilityLoopExit(LoopBeginNode loopBegin, ArrayList<FixedNode> pathBeginNodes) {
298        Node maxSux = null;
299        double maxProbability = 0.0;
300        int pathBeginCount = pathBeginNodes.size();
301
302        for (LoopExitNode sux : loopBegin.loopExits()) {
303            double probability = nodeProbabilities.applyAsDouble(sux);
304            if (probability > maxProbability) {
305                maxProbability = probability;
306                maxSux = sux;
307                truncate(pathBeginNodes, pathBeginCount);
308            } else if (probability == maxProbability) {
309                pathBeginNodes.add(sux);
310            }
311        }
312
313        return maxSux;
314    }
315
316    private static void truncate(ArrayList<FixedNode> pathBeginNodes, int pathBeginCount) {
317        for (int i = pathBeginNodes.size() - pathBeginCount; i > 0; i--) {
318            pathBeginNodes.remove(pathBeginNodes.size() - 1);
319        }
320    }
321}