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