1 /*
2 * Copyright (c) 2012, 2019, 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.nodes.extended;
26
27 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_0;
28 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_0;
29
30 import jdk.vm.ci.meta.JavaKind;
31 import org.graalvm.compiler.core.common.calc.CanonicalCondition;
32 import org.graalvm.compiler.core.common.type.IntegerStamp;
33 import org.graalvm.compiler.core.common.type.StampFactory;
34 import org.graalvm.compiler.debug.GraalError;
35 import org.graalvm.compiler.graph.Node;
36 import org.graalvm.compiler.graph.NodeClass;
37 import org.graalvm.compiler.graph.iterators.NodePredicates;
38 import org.graalvm.compiler.graph.spi.Canonicalizable;
39 import org.graalvm.compiler.graph.spi.CanonicalizerTool;
40 import org.graalvm.compiler.graph.spi.Simplifiable;
41 import org.graalvm.compiler.graph.spi.SimplifierTool;
42 import org.graalvm.compiler.nodeinfo.NodeInfo;
43 import org.graalvm.compiler.nodes.FixedGuardNode;
44 import org.graalvm.compiler.nodes.IfNode;
45 import org.graalvm.compiler.nodes.NodeView;
46 import org.graalvm.compiler.nodes.ReturnNode;
47 import org.graalvm.compiler.nodes.ValueNode;
48 import org.graalvm.compiler.nodes.calc.ConditionalNode;
49 import org.graalvm.compiler.nodes.calc.FloatingNode;
50 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
51 import org.graalvm.compiler.nodes.calc.NarrowNode;
52 import org.graalvm.compiler.nodes.calc.ZeroExtendNode;
53 import org.graalvm.compiler.nodes.spi.Lowerable;
54 import org.graalvm.compiler.nodes.spi.LoweringTool;
55
56 /**
57 * Instances of this node class will look for a preceding if node and put the given probability into
58 * the if node's taken probability. Then the branch probability node will be removed. This node is
59 * intended primarily for snippets, so that they can define their fast and slow paths.
60 */
61 @NodeInfo(cycles = CYCLES_0, cyclesRationale = "Artificial Node", size = SIZE_0)
62 public final class BranchProbabilityNode extends FloatingNode implements Simplifiable, Lowerable, Canonicalizable {
63
64 public static final NodeClass<BranchProbabilityNode> TYPE = NodeClass.create(BranchProbabilityNode.class);
65 public static final double LIKELY_PROBABILITY = 0.6;
66 public static final double NOT_LIKELY_PROBABILITY = 1 - LIKELY_PROBABILITY;
67
68 public static final double FREQUENT_PROBABILITY = 0.9;
69 public static final double NOT_FREQUENT_PROBABILITY = 1 - FREQUENT_PROBABILITY;
70
71 public static final double FAST_PATH_PROBABILITY = 0.99;
72 public static final double SLOW_PATH_PROBABILITY = 1 - FAST_PATH_PROBABILITY;
73
74 public static final double VERY_FAST_PATH_PROBABILITY = 0.999;
75 public static final double VERY_SLOW_PATH_PROBABILITY = 1 - VERY_FAST_PATH_PROBABILITY;
76
77 public static final double DEOPT_PROBABILITY = 0.0;
78
79 /*
80 * This probability may seem excessive, but it makes a difference in long running loops. Lets
81 * say a loop is executed 100k times and it has a few null checks with probability 0.999. As
82 * these probabilities multiply for every loop iteration, the overall loop frequency will be
83 * calculated as approximately 30 while it should be 100k.
84 */
85 public static final double LUDICROUSLY_FAST_PATH_PROBABILITY = 0.999999;
86 public static final double LUDICROUSLY_SLOW_PATH_PROBABILITY = 1 - LUDICROUSLY_FAST_PATH_PROBABILITY;
87
88 @Input ValueNode probability;
89 @Input ValueNode condition;
90
91 public BranchProbabilityNode(ValueNode probability, ValueNode condition) {
92 super(TYPE, StampFactory.forKind(JavaKind.Boolean));
93 this.probability = probability;
94 this.condition = condition;
95 }
96
97 public ValueNode getProbability() {
98 return probability;
99 }
100
101 public ValueNode getCondition() {
102 return condition;
103 }
104
105 @Override
106 public Node canonical(CanonicalizerTool tool) {
107 if (condition.isConstant()) {
108 // fold constant conditions early during PE
109 return condition;
110 }
111 return this;
112 }
113
114 @Override
115 public void simplify(SimplifierTool tool) {
116 if (!hasUsages()) {
117 return;
118 }
119 if (probability.isConstant()) {
120 double probabilityValue = probability.asJavaConstant().asDouble();
121 if (probabilityValue < 0.0) {
122 throw new GraalError("A negative probability of " + probabilityValue + " is not allowed!");
123 } else if (probabilityValue > 1.0) {
124 throw new GraalError("A probability of more than 1.0 (" + probabilityValue + ") is not allowed!");
125 } else if (Double.isNaN(probabilityValue)) {
126 /*
127 * We allow NaN if the node is in unreachable code that will eventually fall away,
128 * or else an error will be thrown during lowering since we keep the node around.
129 */
130 return;
131 }
132 boolean usageFound = false;
133 for (IntegerEqualsNode node : this.usages().filter(IntegerEqualsNode.class)) {
134 assert node.condition() == CanonicalCondition.EQ;
135 ValueNode other = node.getX();
136 if (node.getX() == this) {
137 other = node.getY();
138 }
139 if (other.isConstant()) {
140 double probabilityToSet = probabilityValue;
141 if (other.asJavaConstant().asInt() == 0) {
142 probabilityToSet = 1.0 - probabilityToSet;
143 }
144 for (IfNode ifNodeUsages : node.usages().filter(IfNode.class)) {
145 usageFound = true;
146 ifNodeUsages.setTrueSuccessorProbability(probabilityToSet);
147 }
148 if (!usageFound) {
149 usageFound = node.usages().filter(NodePredicates.isA(FixedGuardNode.class).or(ConditionalNode.class)).isNotEmpty();
150 }
151 }
152 }
153 if (usageFound) {
154 ValueNode currentCondition = condition;
155 IntegerStamp currentStamp = (IntegerStamp) currentCondition.stamp(NodeView.DEFAULT);
156 if (currentStamp.lowerBound() < 0 || 1 < currentStamp.upperBound()) {
157 ValueNode narrow = graph().maybeAddOrUnique(NarrowNode.create(currentCondition, 1, NodeView.DEFAULT));
158 currentCondition = graph().maybeAddOrUnique(ZeroExtendNode.create(narrow, 32, NodeView.DEFAULT));
159 }
160 replaceAndDelete(currentCondition);
161 if (tool != null) {
162 tool.addToWorkList(currentCondition.usages());
163 }
164 } else {
165 if (!isSubstitutionGraph()) {
166 throw new GraalError("Wrong usage of branch probability injection!");
167 }
168 }
169 }
170 }
171
172 private boolean isSubstitutionGraph() {
173 return hasExactlyOneUsage() && usages().first() instanceof ReturnNode;
174 }
175
176 /**
177 * This intrinsic should only be used for the condition of an if statement. The parameter
178 * condition should also only denote a simple condition and not a combined condition involving
179 * && or || operators. It injects the probability of the condition into the if
180 * statement.
181 *
182 * @param probability the probability that the given condition is true as a double value between
183 * 0.0 and 1.0.
184 * @param condition the simple condition without any && or || operators
185 * @return the condition
186 */
187 @NodeIntrinsic
188 public static native boolean probability(double probability, boolean condition);
189
190 @Override
191 public void lower(LoweringTool tool) {
192 throw new GraalError("Branch probability could not be injected, because the probability value did not reduce to a constant value.");
193 }
194 }