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