1/* 2 * Copyright (c) 2013, 2013, 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 */ 23package org.graalvm.compiler.phases.common; 24 25import org.graalvm.compiler.core.common.type.FloatStamp; 26import org.graalvm.compiler.core.common.type.Stamp; 27import org.graalvm.compiler.debug.GraalError; 28import org.graalvm.compiler.graph.Graph; 29import org.graalvm.compiler.graph.Node; 30import org.graalvm.compiler.nodes.AbstractBeginNode; 31import org.graalvm.compiler.nodes.AbstractMergeNode; 32import org.graalvm.compiler.nodes.BeginNode; 33import org.graalvm.compiler.nodes.ConstantNode; 34import org.graalvm.compiler.nodes.EndNode; 35import org.graalvm.compiler.nodes.IfNode; 36import org.graalvm.compiler.nodes.LogicNode; 37import org.graalvm.compiler.nodes.MergeNode; 38import org.graalvm.compiler.nodes.ShortCircuitOrNode; 39import org.graalvm.compiler.nodes.StructuredGraph; 40import org.graalvm.compiler.nodes.ValueNode; 41import org.graalvm.compiler.nodes.calc.ConditionalNode; 42import org.graalvm.compiler.nodes.calc.FloatEqualsNode; 43import org.graalvm.compiler.nodes.calc.FloatLessThanNode; 44import org.graalvm.compiler.nodes.calc.IntegerEqualsNode; 45import org.graalvm.compiler.nodes.calc.IntegerLessThanNode; 46import org.graalvm.compiler.nodes.calc.NormalizeCompareNode; 47import org.graalvm.compiler.phases.Phase; 48 49public class ExpandLogicPhase extends Phase { 50 private static final double EPSILON = 1E-6; 51 52 @Override 53 protected void run(StructuredGraph graph) { 54 for (ShortCircuitOrNode logic : graph.getNodes(ShortCircuitOrNode.TYPE)) { 55 processBinary(logic); 56 } 57 assert graph.getNodes(ShortCircuitOrNode.TYPE).isEmpty(); 58 59 for (NormalizeCompareNode logic : graph.getNodes(NormalizeCompareNode.TYPE)) { 60 processNormalizeCompareNode(logic); 61 } 62 graph.setAfterExpandLogic(); 63 } 64 65 private static void processNormalizeCompareNode(NormalizeCompareNode normalize) { 66 LogicNode equalComp; 67 LogicNode lessComp; 68 StructuredGraph graph = normalize.graph(); 69 ValueNode x = normalize.getX(); 70 ValueNode y = normalize.getY(); 71 if (x.stamp() instanceof FloatStamp) { 72 equalComp = graph.addOrUniqueWithInputs(FloatEqualsNode.create(x, y)); 73 lessComp = graph.addOrUniqueWithInputs(FloatLessThanNode.create(x, y, normalize.isUnorderedLess())); 74 } else { 75 equalComp = graph.addOrUniqueWithInputs(IntegerEqualsNode.create(x, y)); 76 lessComp = graph.addOrUniqueWithInputs(IntegerLessThanNode.create(x, y)); 77 } 78 79 Stamp stamp = normalize.stamp(); 80 ConditionalNode equalValue = graph.unique( 81 new ConditionalNode(equalComp, ConstantNode.forIntegerStamp(stamp, 0, graph), ConstantNode.forIntegerStamp(stamp, 1, graph))); 82 ConditionalNode value = graph.unique(new ConditionalNode(lessComp, ConstantNode.forIntegerStamp(stamp, -1, graph), equalValue)); 83 normalize.replaceAtUsagesAndDelete(value); 84 } 85 86 private static void processBinary(ShortCircuitOrNode binary) { 87 while (binary.usages().isNotEmpty()) { 88 Node usage = binary.usages().first(); 89 if (usage instanceof ShortCircuitOrNode) { 90 processBinary((ShortCircuitOrNode) usage); 91 } else if (usage instanceof IfNode) { 92 processIf(binary.getX(), binary.isXNegated(), binary.getY(), binary.isYNegated(), (IfNode) usage, binary.getShortCircuitProbability()); 93 } else if (usage instanceof ConditionalNode) { 94 processConditional(binary.getX(), binary.isXNegated(), binary.getY(), binary.isYNegated(), (ConditionalNode) usage); 95 } else { 96 throw GraalError.shouldNotReachHere(); 97 } 98 } 99 binary.safeDelete(); 100 } 101 102 private static void processIf(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, IfNode ifNode, double shortCircuitProbability) { 103 /* 104 * this method splits an IfNode, which has a ShortCircuitOrNode as its condition, into two 105 * separate IfNodes: if(X) and if(Y) 106 * 107 * for computing the probabilities P(X) and P(Y), we use two different approaches. The first 108 * one assumes that the shortCircuitProbability and the probability on the IfNode were 109 * created with each other in mind. If this assumption does not hold, we fall back to 110 * another mechanism for computing the probabilities. 111 */ 112 AbstractBeginNode trueTarget = ifNode.trueSuccessor(); 113 AbstractBeginNode falseTarget = ifNode.falseSuccessor(); 114 115 // 1st approach 116 // assumption: P(originalIf.trueSuccessor) == P(X) + ((1 - P(X)) * P(Y)) 117 double firstIfTrueProbability = shortCircuitProbability; 118 double secondIfTrueProbability = sanitizeProbability((ifNode.getTrueSuccessorProbability() - shortCircuitProbability) / (1 - shortCircuitProbability)); 119 double expectedOriginalIfTrueProbability = firstIfTrueProbability + (1 - firstIfTrueProbability) * secondIfTrueProbability; 120 121 if (!doubleEquals(ifNode.getTrueSuccessorProbability(), expectedOriginalIfTrueProbability)) { 122 /* 123 * 2nd approach 124 * 125 * the assumption above did not hold, so we either used an artificial probability as 126 * shortCircuitProbability or the ShortCircuitOrNode was moved to some other IfNode. 127 * 128 * so, we distribute the if's trueSuccessorProbability between the newly generated if 129 * nodes according to the shortCircuitProbability. the following invariant is always 130 * true in this case: P(originalIf.trueSuccessor) == P(X) + ((1 - P(X)) * P(Y)) 131 */ 132 firstIfTrueProbability = ifNode.getTrueSuccessorProbability() * shortCircuitProbability; 133 secondIfTrueProbability = sanitizeProbability(1 - (ifNode.probability(falseTarget) / (1 - firstIfTrueProbability))); 134 } 135 136 ifNode.clearSuccessors(); 137 Graph graph = ifNode.graph(); 138 AbstractMergeNode trueTargetMerge = graph.add(new MergeNode()); 139 trueTargetMerge.setNext(trueTarget); 140 EndNode firstTrueEnd = graph.add(new EndNode()); 141 EndNode secondTrueEnd = graph.add(new EndNode()); 142 trueTargetMerge.addForwardEnd(firstTrueEnd); 143 trueTargetMerge.addForwardEnd(secondTrueEnd); 144 AbstractBeginNode firstTrueTarget = BeginNode.begin(firstTrueEnd); 145 AbstractBeginNode secondTrueTarget = BeginNode.begin(secondTrueEnd); 146 if (yNegated) { 147 secondIfTrueProbability = 1.0 - secondIfTrueProbability; 148 } 149 if (xNegated) { 150 firstIfTrueProbability = 1.0 - firstIfTrueProbability; 151 } 152 AbstractBeginNode secondIf = BeginNode.begin(graph.add(new IfNode(y, yNegated ? falseTarget : secondTrueTarget, yNegated ? secondTrueTarget : falseTarget, secondIfTrueProbability))); 153 IfNode firstIf = graph.add(new IfNode(x, xNegated ? secondIf : firstTrueTarget, xNegated ? firstTrueTarget : secondIf, firstIfTrueProbability)); 154 ifNode.replaceAtPredecessor(firstIf); 155 ifNode.safeDelete(); 156 } 157 158 private static boolean doubleEquals(double a, double b) { 159 assert !Double.isNaN(a) && !Double.isNaN(b) && !Double.isInfinite(a) && !Double.isInfinite(b); 160 return a - EPSILON < b && a + EPSILON > b; 161 } 162 163 private static double sanitizeProbability(double value) { 164 double newValue = Math.min(1.0, Math.max(0.0, value)); 165 if (Double.isNaN(newValue)) { 166 newValue = 0.5; 167 } 168 return newValue; 169 } 170 171 private static void processConditional(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, ConditionalNode conditional) { 172 ValueNode trueTarget = conditional.trueValue(); 173 ValueNode falseTarget = conditional.falseValue(); 174 Graph graph = conditional.graph(); 175 ConditionalNode secondConditional = graph.unique(new ConditionalNode(y, yNegated ? falseTarget : trueTarget, yNegated ? trueTarget : falseTarget)); 176 ConditionalNode firstConditional = graph.unique(new ConditionalNode(x, xNegated ? secondConditional : trueTarget, xNegated ? trueTarget : secondConditional)); 177 conditional.replaceAndDelete(firstConditional); 178 } 179 180 @Override 181 public boolean checkContract() { 182 return false; 183 } 184} 185