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
applyAsDouble(FixedNode node)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 
handleMerge(FixedNode current, double probability)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 
findBegin(FixedNode node)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 }
158