001/*
002 * Copyright (c) 2012, 2014, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.nodes.extended;
024
025import jdk.internal.jvmci.common.*;
026
027import com.oracle.graal.compiler.common.calc.*;
028import com.oracle.graal.graph.*;
029import com.oracle.graal.graph.spi.*;
030import com.oracle.graal.nodeinfo.*;
031import com.oracle.graal.nodes.*;
032import com.oracle.graal.nodes.calc.*;
033import com.oracle.graal.nodes.spi.*;
034
035/**
036 * Instances of this node class will look for a preceding if node and put the given probability into
037 * the if node's taken probability. Then the branch probability node will be removed. This node is
038 * intended primarily for snippets, so that they can define their fast and slow paths.
039 */
040@NodeInfo
041public final class BranchProbabilityNode extends FloatingNode implements Simplifiable, Lowerable {
042
043    public static final NodeClass<BranchProbabilityNode> TYPE = NodeClass.create(BranchProbabilityNode.class);
044    public static final double LIKELY_PROBABILITY = 0.6;
045    public static final double NOT_LIKELY_PROBABILITY = 1 - LIKELY_PROBABILITY;
046
047    public static final double FREQUENT_PROBABILITY = 0.9;
048    public static final double NOT_FREQUENT_PROBABILITY = 1 - FREQUENT_PROBABILITY;
049
050    public static final double FAST_PATH_PROBABILITY = 0.99;
051    public static final double SLOW_PATH_PROBABILITY = 1 - FAST_PATH_PROBABILITY;
052
053    public static final double VERY_FAST_PATH_PROBABILITY = 0.999;
054    public static final double VERY_SLOW_PATH_PROBABILITY = 1 - VERY_FAST_PATH_PROBABILITY;
055
056    @Input ValueNode probability;
057    @Input ValueNode condition;
058
059    public BranchProbabilityNode(ValueNode probability, ValueNode condition) {
060        super(TYPE, condition.stamp());
061        this.probability = probability;
062        this.condition = condition;
063    }
064
065    public ValueNode getProbability() {
066        return probability;
067    }
068
069    public ValueNode getCondition() {
070        return condition;
071    }
072
073    @Override
074    public void simplify(SimplifierTool tool) {
075        if (probability.isConstant()) {
076            double probabilityValue = probability.asJavaConstant().asDouble();
077            if (probabilityValue < 0.0) {
078                throw new JVMCIError("A negative probability of " + probabilityValue + " is not allowed!");
079            } else if (probabilityValue > 1.0) {
080                throw new JVMCIError("A probability of more than 1.0 (" + probabilityValue + ") is not allowed!");
081            } else if (Double.isNaN(probabilityValue)) {
082                /*
083                 * We allow NaN if the node is in unreachable code that will eventually fall away,
084                 * or else an error will be thrown during lowering since we keep the node around.
085                 */
086                return;
087            }
088            boolean couldSet = false;
089            for (IntegerEqualsNode node : this.usages().filter(IntegerEqualsNode.class)) {
090                if (node.condition() == Condition.EQ) {
091                    ValueNode other = node.getX();
092                    if (node.getX() == this) {
093                        other = node.getY();
094                    }
095                    if (other.isConstant()) {
096                        double probabilityToSet = probabilityValue;
097                        if (other.asJavaConstant().asInt() == 0) {
098                            probabilityToSet = 1.0 - probabilityToSet;
099                        }
100                        for (IfNode ifNodeUsages : node.usages().filter(IfNode.class)) {
101                            couldSet = true;
102                            ifNodeUsages.setTrueSuccessorProbability(probabilityToSet);
103                        }
104
105                        if (!couldSet && node.usages().filter(FixedGuardNode.class).isNotEmpty()) {
106                            couldSet = true;
107                        }
108                    }
109                }
110            }
111            if (couldSet) {
112                ValueNode currentCondition = condition;
113                replaceAndDelete(currentCondition);
114                if (tool != null) {
115                    tool.addToWorkList(currentCondition.usages());
116                }
117            } else {
118                if (!isSubstitutionGraph()) {
119                    throw new JVMCIError("Wrong usage of branch probability injection!");
120                }
121            }
122        }
123    }
124
125    private boolean isSubstitutionGraph() {
126        return getUsageCount() == 1 && usages().first() instanceof ReturnNode;
127    }
128
129    /**
130     * This intrinsic should only be used for the condition of an if statement. The parameter
131     * condition should also only denote a simple condition and not a combined condition involving
132     * &amp;&amp; or || operators. It injects the probability of the condition into the if
133     * statement.
134     *
135     * @param probability the probability that the given condition is true as a double value between
136     *            0.0 and 1.0.
137     * @param condition the simple condition without any &amp;&amp; or || operators
138     * @return the condition
139     */
140    @NodeIntrinsic
141    public static native boolean probability(double probability, boolean condition);
142
143    @Override
144    public void lower(LoweringTool tool) {
145        throw new JVMCIError("Branch probability could not be injected, because the probability value did not reduce to a constant value.");
146    }
147}