1 /* 2 * Copyright (c) 2013, 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 24 25 package org.graalvm.compiler.nodes; 26 27 import static org.graalvm.compiler.nodeinfo.InputType.Condition; 28 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_0; 29 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_0; 30 31 import org.graalvm.compiler.core.common.type.IntegerStamp; 32 import org.graalvm.compiler.graph.IterableNodeType; 33 import org.graalvm.compiler.graph.NodeClass; 34 import org.graalvm.compiler.graph.spi.Canonicalizable; 35 import org.graalvm.compiler.graph.spi.CanonicalizerTool; 36 import org.graalvm.compiler.nodeinfo.NodeInfo; 37 import org.graalvm.compiler.nodes.calc.IntegerBelowNode; 38 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode; 39 40 import jdk.vm.ci.meta.TriState; 41 42 @NodeInfo(cycles = CYCLES_0, size = SIZE_0) 43 public final class ShortCircuitOrNode extends LogicNode implements IterableNodeType, Canonicalizable.Binary<LogicNode> { 44 public static final NodeClass<ShortCircuitOrNode> TYPE = NodeClass.create(ShortCircuitOrNode.class); 45 @Input(Condition) LogicNode x; 46 @Input(Condition) LogicNode y; 47 protected boolean xNegated; 48 protected boolean yNegated; 49 protected double shortCircuitProbability; 50 ShortCircuitOrNode(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, double shortCircuitProbability)51 public ShortCircuitOrNode(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, double shortCircuitProbability) { 52 super(TYPE); 53 this.x = x; 54 this.xNegated = xNegated; 55 this.y = y; 56 this.yNegated = yNegated; 57 this.shortCircuitProbability = shortCircuitProbability; 58 } 59 60 @Override getX()61 public LogicNode getX() { 62 return x; 63 } 64 65 @Override getY()66 public LogicNode getY() { 67 return y; 68 } 69 isXNegated()70 public boolean isXNegated() { 71 return xNegated; 72 } 73 isYNegated()74 public boolean isYNegated() { 75 return yNegated; 76 } 77 78 /** 79 * Gets the probability that the {@link #getY() y} part of this binary node is <b>not</b> 80 * evaluated. This is the probability that this operator will short-circuit its execution. 81 */ getShortCircuitProbability()82 public double getShortCircuitProbability() { 83 return shortCircuitProbability; 84 } 85 canonicalizeNegation(LogicNode forX, LogicNode forY)86 protected ShortCircuitOrNode canonicalizeNegation(LogicNode forX, LogicNode forY) { 87 LogicNode xCond = forX; 88 boolean xNeg = xNegated; 89 while (xCond instanceof LogicNegationNode) { 90 xCond = ((LogicNegationNode) xCond).getValue(); 91 xNeg = !xNeg; 92 } 93 94 LogicNode yCond = forY; 95 boolean yNeg = yNegated; 96 while (yCond instanceof LogicNegationNode) { 97 yCond = ((LogicNegationNode) yCond).getValue(); 98 yNeg = !yNeg; 99 } 100 101 if (xCond != forX || yCond != forY) { 102 return new ShortCircuitOrNode(xCond, xNeg, yCond, yNeg, shortCircuitProbability); 103 } else { 104 return this; 105 } 106 } 107 108 @Override canonical(CanonicalizerTool tool, LogicNode forX, LogicNode forY)109 public LogicNode canonical(CanonicalizerTool tool, LogicNode forX, LogicNode forY) { 110 ShortCircuitOrNode ret = canonicalizeNegation(forX, forY); 111 if (ret != this) { 112 return ret; 113 } 114 115 if (forX == forY) { 116 // @formatter:off 117 // a || a = a 118 // a || !a = true 119 // !a || a = true 120 // !a || !a = !a 121 // @formatter:on 122 if (isXNegated()) { 123 if (isYNegated()) { 124 // !a || !a = !a 125 return LogicNegationNode.create(forX); 126 } else { 127 // !a || a = true 128 return LogicConstantNode.tautology(); 129 } 130 } else { 131 if (isYNegated()) { 132 // a || !a = true 133 return LogicConstantNode.tautology(); 134 } else { 135 // a || a = a 136 return forX; 137 } 138 } 139 } 140 if (forX instanceof LogicConstantNode) { 141 if (((LogicConstantNode) forX).getValue() ^ isXNegated()) { 142 return LogicConstantNode.tautology(); 143 } else { 144 if (isYNegated()) { 145 return new LogicNegationNode(forY); 146 } else { 147 return forY; 148 } 149 } 150 } 151 if (forY instanceof LogicConstantNode) { 152 if (((LogicConstantNode) forY).getValue() ^ isYNegated()) { 153 return LogicConstantNode.tautology(); 154 } else { 155 if (isXNegated()) { 156 return new LogicNegationNode(forX); 157 } else { 158 return forX; 159 } 160 } 161 } 162 163 if (forX instanceof ShortCircuitOrNode) { 164 ShortCircuitOrNode inner = (ShortCircuitOrNode) forX; 165 if (forY == inner.getX()) { 166 return optimizeShortCircuit(inner, this.xNegated, this.yNegated, true); 167 } else if (forY == inner.getY()) { 168 return optimizeShortCircuit(inner, this.xNegated, this.yNegated, false); 169 } 170 } else if (forY instanceof ShortCircuitOrNode) { 171 ShortCircuitOrNode inner = (ShortCircuitOrNode) forY; 172 if (inner.getX() == forX) { 173 return optimizeShortCircuit(inner, this.yNegated, this.xNegated, true); 174 } else if (inner.getY() == forX) { 175 return optimizeShortCircuit(inner, this.yNegated, this.xNegated, false); 176 } 177 } 178 179 // !X => Y constant 180 TriState impliedForY = forX.implies(!isXNegated(), forY); 181 if (impliedForY.isKnown()) { 182 boolean yResult = impliedForY.toBoolean() ^ isYNegated(); 183 return yResult 184 ? LogicConstantNode.tautology() 185 : (isXNegated() 186 ? LogicNegationNode.create(forX) 187 : forX); 188 } 189 190 // if X >= 0: 191 // u < 0 || X < u ==>> X |<| u 192 if (!isXNegated() && !isYNegated()) { 193 LogicNode sym = simplifyComparison(forX, forY); 194 if (sym != null) { 195 return sym; 196 } 197 } 198 199 // if X >= 0: 200 // X |<| u || X < u ==>> X |<| u 201 if (forX instanceof IntegerBelowNode && forY instanceof IntegerLessThanNode && !isXNegated() && !isYNegated()) { 202 IntegerBelowNode xNode = (IntegerBelowNode) forX; 203 IntegerLessThanNode yNode = (IntegerLessThanNode) forY; 204 ValueNode xxNode = xNode.getX(); // X >= 0 205 ValueNode yxNode = yNode.getX(); // X >= 0 206 if (xxNode == yxNode && ((IntegerStamp) xxNode.stamp(NodeView.DEFAULT)).isPositive()) { 207 ValueNode xyNode = xNode.getY(); // u 208 ValueNode yyNode = yNode.getY(); // u 209 if (xyNode == yyNode) { 210 return forX; 211 } 212 } 213 } 214 215 // if X >= 0: 216 // u < 0 || (X < u || tail) ==>> X |<| u || tail 217 if (forY instanceof ShortCircuitOrNode && !isXNegated() && !isYNegated()) { 218 ShortCircuitOrNode yNode = (ShortCircuitOrNode) forY; 219 if (!yNode.isXNegated()) { 220 LogicNode sym = simplifyComparison(forX, yNode.getX()); 221 if (sym != null) { 222 double p1 = getShortCircuitProbability(); 223 double p2 = yNode.getShortCircuitProbability(); 224 return new ShortCircuitOrNode(sym, isXNegated(), yNode.getY(), yNode.isYNegated(), p1 + (1 - p1) * p2); 225 } 226 } 227 } 228 229 return this; 230 } 231 simplifyComparison(LogicNode forX, LogicNode forY)232 private static LogicNode simplifyComparison(LogicNode forX, LogicNode forY) { 233 LogicNode sym = simplifyComparisonOrdered(forX, forY); 234 if (sym == null) { 235 return simplifyComparisonOrdered(forY, forX); 236 } 237 return sym; 238 } 239 simplifyComparisonOrdered(LogicNode forX, LogicNode forY)240 private static LogicNode simplifyComparisonOrdered(LogicNode forX, LogicNode forY) { 241 // if X is >= 0: 242 // u < 0 || X < u ==>> X |<| u 243 if (forX instanceof IntegerLessThanNode && forY instanceof IntegerLessThanNode) { 244 IntegerLessThanNode xNode = (IntegerLessThanNode) forX; 245 IntegerLessThanNode yNode = (IntegerLessThanNode) forY; 246 ValueNode xyNode = xNode.getY(); // 0 247 if (xyNode.isConstant() && IntegerStamp.OPS.getAdd().isNeutral(xyNode.asConstant())) { 248 ValueNode yxNode = yNode.getX(); // X >= 0 249 IntegerStamp stamp = (IntegerStamp) yxNode.stamp(NodeView.DEFAULT); 250 if (stamp.isPositive()) { 251 if (xNode.getX() == yNode.getY()) { 252 ValueNode u = xNode.getX(); 253 return IntegerBelowNode.create(yxNode, u, NodeView.DEFAULT); 254 } 255 } 256 } 257 } 258 259 return null; 260 } 261 optimizeShortCircuit(ShortCircuitOrNode inner, boolean innerNegated, boolean matchNegated, boolean matchIsInnerX)262 private static LogicNode optimizeShortCircuit(ShortCircuitOrNode inner, boolean innerNegated, boolean matchNegated, boolean matchIsInnerX) { 263 boolean innerMatchNegated; 264 if (matchIsInnerX) { 265 innerMatchNegated = inner.isXNegated(); 266 } else { 267 innerMatchNegated = inner.isYNegated(); 268 } 269 if (!innerNegated) { 270 // The four digit results of the expression used in the 16 subsequent formula comments 271 // correspond to results when using the following truth table for inputs a and b 272 // and testing all 4 possible input combinations: 273 // _ 1234 274 // a 1100 275 // b 1010 276 if (innerMatchNegated == matchNegated) { 277 // ( (!a ||!b) ||!a) => 0111 (!a ||!b) 278 // ( (!a || b) ||!a) => 1011 (!a || b) 279 // ( ( a ||!b) || a) => 1101 ( a ||!b) 280 // ( ( a || b) || a) => 1110 ( a || b) 281 // Only the inner or is relevant, the outer or never adds information. 282 return inner; 283 } else { 284 // ( ( a || b) ||!a) => 1111 (true) 285 // ( (!a ||!b) || a) => 1111 (true) 286 // ( (!a || b) || a) => 1111 (true) 287 // ( ( a ||!b) ||!a) => 1111 (true) 288 // The result of the expression is always true. 289 return LogicConstantNode.tautology(); 290 } 291 } else { 292 if (innerMatchNegated == matchNegated) { 293 // (!(!a ||!b) ||!a) => 1011 (!a || b) 294 // (!(!a || b) ||!a) => 0111 (!a ||!b) 295 // (!( a ||!b) || a) => 1110 ( a || b) 296 // (!( a || b) || a) => 1101 ( a ||!b) 297 boolean newInnerXNegated = inner.isXNegated(); 298 boolean newInnerYNegated = inner.isYNegated(); 299 double newProbability = inner.getShortCircuitProbability(); 300 if (matchIsInnerX) { 301 newInnerYNegated = !newInnerYNegated; 302 } else { 303 newInnerXNegated = !newInnerXNegated; 304 newProbability = 1.0 - newProbability; 305 } 306 // The expression can be transformed into a single or. 307 return new ShortCircuitOrNode(inner.getX(), newInnerXNegated, inner.getY(), newInnerYNegated, newProbability); 308 } else { 309 // (!(!a ||!b) || a) => 1100 (a) 310 // (!(!a || b) || a) => 1100 (a) 311 // (!( a ||!b) ||!a) => 0011 (!a) 312 // (!( a || b) ||!a) => 0011 (!a) 313 LogicNode result = inner.getY(); 314 if (matchIsInnerX) { 315 result = inner.getX(); 316 } 317 // Only the second part of the outer or is relevant. 318 if (matchNegated) { 319 return LogicNegationNode.create(result); 320 } else { 321 return result; 322 } 323 } 324 } 325 } 326 } 327