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