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