1 /*
2 * Copyright (c) 2012, 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.nodes.extended;
24
25 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_0;
26 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_0;
27
28 import org.graalvm.compiler.core.common.calc.Condition;
29 import org.graalvm.compiler.debug.GraalError;
30 import org.graalvm.compiler.graph.NodeClass;
31 import org.graalvm.compiler.graph.iterators.NodePredicates;
32 import org.graalvm.compiler.graph.spi.Simplifiable;
33 import org.graalvm.compiler.graph.spi.SimplifierTool;
34 import org.graalvm.compiler.nodeinfo.NodeInfo;
35 import org.graalvm.compiler.nodes.FixedGuardNode;
36 import org.graalvm.compiler.nodes.IfNode;
37 import org.graalvm.compiler.nodes.ReturnNode;
38 import org.graalvm.compiler.nodes.ValueNode;
39 import org.graalvm.compiler.nodes.calc.ConditionalNode;
40 import org.graalvm.compiler.nodes.calc.FloatingNode;
41 import org.graalvm.compiler.nodes.calc.IntegerEqualsNode;
42 import org.graalvm.compiler.nodes.spi.Lowerable;
43 import org.graalvm.compiler.nodes.spi.LoweringTool;
44
45 /**
46 * Instances of this node class will look for a preceding if node and put the given probability into
47 * the if node's taken probability. Then the branch probability node will be removed. This node is
48 * intended primarily for snippets, so that they can define their fast and slow paths.
49 */
50 @NodeInfo(cycles = CYCLES_0, cyclesRationale = "Artificial Node", size = SIZE_0)
51 public final class BranchProbabilityNode extends FloatingNode implements Simplifiable, Lowerable {
52
53 public static final NodeClass<BranchProbabilityNode> TYPE = NodeClass.create(BranchProbabilityNode.class);
54 public static final double LIKELY_PROBABILITY = 0.6;
55 public static final double NOT_LIKELY_PROBABILITY = 1 - LIKELY_PROBABILITY;
56
57 public static final double FREQUENT_PROBABILITY = 0.9;
58 public static final double NOT_FREQUENT_PROBABILITY = 1 - FREQUENT_PROBABILITY;
59
60 public static final double FAST_PATH_PROBABILITY = 0.99;
61 public static final double SLOW_PATH_PROBABILITY = 1 - FAST_PATH_PROBABILITY;
62
63 public static final double VERY_FAST_PATH_PROBABILITY = 0.999;
64 public static final double VERY_SLOW_PATH_PROBABILITY = 1 - VERY_FAST_PATH_PROBABILITY;
65
66 @Input ValueNode probability;
67 @Input ValueNode condition;
68
69 public BranchProbabilityNode(ValueNode probability, ValueNode condition) {
70 super(TYPE, condition.stamp());
71 this.probability = probability;
72 this.condition = condition;
73 }
74
75 public ValueNode getProbability() {
76 return probability;
77 }
78
79 public ValueNode getCondition() {
80 return condition;
81 }
82
83 @Override
84 public void simplify(SimplifierTool tool) {
85 if (!hasUsages()) {
86 return;
87 }
88 if (probability.isConstant()) {
89 double probabilityValue = probability.asJavaConstant().asDouble();
90 if (probabilityValue < 0.0) {
91 throw new GraalError("A negative probability of " + probabilityValue + " is not allowed!");
92 } else if (probabilityValue > 1.0) {
93 throw new GraalError("A probability of more than 1.0 (" + probabilityValue + ") is not allowed!");
94 } else if (Double.isNaN(probabilityValue)) {
95 /*
96 * We allow NaN if the node is in unreachable code that will eventually fall away,
97 * or else an error will be thrown during lowering since we keep the node around.
98 */
99 return;
100 }
101 boolean usageFound = false;
102 for (IntegerEqualsNode node : this.usages().filter(IntegerEqualsNode.class)) {
103 assert node.condition() == Condition.EQ;
104 ValueNode other = node.getX();
105 if (node.getX() == this) {
106 other = node.getY();
107 }
108 if (other.isConstant()) {
109 double probabilityToSet = probabilityValue;
110 if (other.asJavaConstant().asInt() == 0) {
111 probabilityToSet = 1.0 - probabilityToSet;
112 }
113 for (IfNode ifNodeUsages : node.usages().filter(IfNode.class)) {
114 usageFound = true;
115 ifNodeUsages.setTrueSuccessorProbability(probabilityToSet);
116 }
117 if (!usageFound) {
118 usageFound = node.usages().filter(NodePredicates.isA(FixedGuardNode.class).or(ConditionalNode.class)).isNotEmpty();
119 }
120 }
121 }
122 if (usageFound) {
123 ValueNode currentCondition = condition;
124 replaceAndDelete(currentCondition);
125 if (tool != null) {
126 tool.addToWorkList(currentCondition.usages());
127 }
128 } else {
129 if (!isSubstitutionGraph()) {
130 throw new GraalError("Wrong usage of branch probability injection!");
131 }
132 }
133 }
134 }
135
136 private boolean isSubstitutionGraph() {
137 return hasExactlyOneUsage() && usages().first() instanceof ReturnNode;
138 }
139
140 /**
141 * This intrinsic should only be used for the condition of an if statement. The parameter
142 * condition should also only denote a simple condition and not a combined condition involving
143 * && or || operators. It injects the probability of the condition into the if
144 * statement.
145 *
146 * @param probability the probability that the given condition is true as a double value between
147 * 0.0 and 1.0.
148 * @param condition the simple condition without any && or || operators
149 * @return the condition
150 */
151 @NodeIntrinsic
152 public static native boolean probability(double probability, boolean condition);
153
154 @Override
155 public void lower(LoweringTool tool) {
156 throw new GraalError("Branch probability could not be injected, because the probability value did not reduce to a constant value.");
157 }
158 }