1 /* 2 * Copyright (c) 2014, 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.graph; 26 27 import static org.graalvm.compiler.nodes.cfg.ControlFlowGraph.multiplyProbabilities; 28 29 import java.util.function.ToDoubleFunction; 30 31 import jdk.internal.vm.compiler.collections.EconomicMap; 32 import jdk.internal.vm.compiler.collections.Equivalence; 33 import org.graalvm.compiler.debug.CounterKey; 34 import org.graalvm.compiler.debug.DebugContext; 35 import org.graalvm.compiler.graph.Node; 36 import org.graalvm.compiler.graph.NodeInputList; 37 import org.graalvm.compiler.nodes.AbstractBeginNode; 38 import org.graalvm.compiler.nodes.AbstractEndNode; 39 import org.graalvm.compiler.nodes.AbstractMergeNode; 40 import org.graalvm.compiler.nodes.ControlSplitNode; 41 import org.graalvm.compiler.nodes.EndNode; 42 import org.graalvm.compiler.nodes.FixedNode; 43 import org.graalvm.compiler.nodes.LoopBeginNode; 44 import org.graalvm.compiler.nodes.StartNode; 45 46 /** 47 * Compute probabilities for fixed nodes on the fly and cache them at {@link AbstractBeginNode}s. 48 */ 49 public class FixedNodeProbabilityCache implements ToDoubleFunction<FixedNode> { 50 51 private static final CounterKey computeNodeProbabilityCounter = DebugContext.counter("ComputeNodeProbability"); 52 53 private final EconomicMap<FixedNode, Double> cache = EconomicMap.create(Equivalence.IDENTITY); 54 55 /** 56 * <p> 57 * Given a {@link FixedNode} this method finds the most immediate {@link AbstractBeginNode} 58 * preceding it that either: 59 * <ul> 60 * <li>has no predecessor (ie, the begin-node is a merge, in particular a loop-begin, or the 61 * start-node)</li> 62 * <li>has a control-split predecessor</li> 63 * </ul> 64 * </p> 65 * 66 * <p> 67 * The thus found {@link AbstractBeginNode} is equi-probable with the {@link FixedNode} it was 68 * obtained from. When computed for the first time (afterwards a cache lookup returns it) that 69 * probability is computed as follows, again depending on the begin-node's predecessor: 70 * <ul> 71 * <li>No predecessor. In this case the begin-node is either:</li> 72 * <ul> 73 * <li>a merge-node, whose probability adds up those of its forward-ends</li> 74 * <li>a loop-begin, with probability as above multiplied by the loop-frequency</li> 75 * </ul> 76 * <li>Control-split predecessor: probability of the branch times that of the control-split</li> 77 * </ul> 78 * </p> 79 * 80 * <p> 81 * As an exception to all the above, a probability of 1 is assumed for a {@link FixedNode} that 82 * appears to be dead-code (ie, lacks a predecessor). 83 * </p> 84 * 85 */ 86 @Override 87 public double applyAsDouble(FixedNode node) { 88 assert node != null; 89 computeNodeProbabilityCounter.increment(node.getDebug()); 90 91 FixedNode current = findBegin(node); 92 if (current == null) { 93 // this should only appear for dead code 94 return 1D; 95 } 96 97 assert current instanceof AbstractBeginNode; 98 Double cachedValue = cache.get(current); 99 if (cachedValue != null) { 100 return cachedValue; 101 } 102 103 double probability = 0.0; 104 if (current.predecessor() == null) { 105 if (current instanceof AbstractMergeNode) { 106 probability = handleMerge(current, probability); 107 } else { 108 assert current instanceof StartNode; 109 probability = 1D; 110 } 111 } else { 112 ControlSplitNode split = (ControlSplitNode) current.predecessor(); 113 probability = multiplyProbabilities(split.probability((AbstractBeginNode) current), applyAsDouble(split)); 114 } 115 assert !Double.isNaN(probability) && !Double.isInfinite(probability) : current + " " + probability; 116 cache.put(current, probability); 117 return probability; 118 } 119 120 private double handleMerge(FixedNode current, double probability) { 121 double result = probability; 122 AbstractMergeNode currentMerge = (AbstractMergeNode) current; 123 NodeInputList<EndNode> currentForwardEnds = currentMerge.forwardEnds(); 124 /* 125 * Use simple iteration instead of streams, since the stream infrastructure adds many frames 126 * which causes the recursion to overflow the stack earlier than it would otherwise. 127 */ 128 for (AbstractEndNode endNode : currentForwardEnds) { 129 result += applyAsDouble(endNode); 130 } 131 if (current instanceof LoopBeginNode) { 132 result = multiplyProbabilities(result, ((LoopBeginNode) current).loopFrequency()); 133 } 134 return result; 135 } 136 137 private static FixedNode findBegin(FixedNode node) { 138 FixedNode current = node; 139 while (true) { 140 assert current != null; 141 Node predecessor = current.predecessor(); 142 if (current instanceof AbstractBeginNode) { 143 if (predecessor == null) { 144 break; 145 } else if (predecessor.successors().count() != 1) { 146 assert predecessor instanceof ControlSplitNode : "a FixedNode with multiple successors needs to be a ControlSplitNode: " + current + " / " + predecessor; 147 break; 148 } 149 } else if (predecessor == null) { 150 current = null; 151 break; 152 } 153 current = (FixedNode) predecessor; 154 } 155 return current; 156 } 157 }