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