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.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.spi.ConstantFieldProvider; 32 import org.graalvm.compiler.core.common.type.IntegerStamp; 33 import org.graalvm.compiler.core.common.type.Stamp; 34 import org.graalvm.compiler.graph.IterableNodeType; 35 import org.graalvm.compiler.graph.NodeClass; 36 import org.graalvm.compiler.graph.spi.Canonicalizable; 37 import org.graalvm.compiler.graph.spi.CanonicalizerTool; 38 import org.graalvm.compiler.nodeinfo.NodeInfo; 39 import org.graalvm.compiler.nodes.calc.CompareNode; 40 import org.graalvm.compiler.nodes.calc.IntegerBelowNode; 41 import org.graalvm.compiler.nodes.calc.IntegerLessThanNode; 42 import org.graalvm.compiler.options.OptionValues; 43 44 import jdk.vm.ci.meta.Assumptions; 45 import jdk.vm.ci.meta.ConstantReflectionProvider; 46 import jdk.vm.ci.meta.MetaAccessProvider; 47 import jdk.vm.ci.meta.TriState; 48 49 @NodeInfo(cycles = CYCLES_0, size = SIZE_0) 50 public final class ShortCircuitOrNode extends LogicNode implements IterableNodeType, Canonicalizable.Binary<LogicNode> { 51 public static final NodeClass<ShortCircuitOrNode> TYPE = NodeClass.create(ShortCircuitOrNode.class); 52 @Input(Condition) LogicNode x; 53 @Input(Condition) LogicNode y; 54 protected boolean xNegated; 55 protected boolean yNegated; 56 protected double shortCircuitProbability; 57 ShortCircuitOrNode(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, double shortCircuitProbability)58 public ShortCircuitOrNode(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, double shortCircuitProbability) { 59 super(TYPE); 60 this.x = x; 61 this.xNegated = xNegated; 62 this.y = y; 63 this.yNegated = yNegated; 64 this.shortCircuitProbability = shortCircuitProbability; 65 } 66 create(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, double shortCircuitProbability)67 public static LogicNode create(LogicNode x, boolean xNegated, LogicNode y, boolean yNegated, double shortCircuitProbability) { 68 return new ShortCircuitOrNode(x, xNegated, y, yNegated, shortCircuitProbability); 69 } 70 71 @Override getX()72 public LogicNode getX() { 73 return x; 74 } 75 76 @Override getY()77 public LogicNode getY() { 78 return y; 79 } 80 isXNegated()81 public boolean isXNegated() { 82 return xNegated; 83 } 84 isYNegated()85 public boolean isYNegated() { 86 return yNegated; 87 } 88 89 /** 90 * Gets the probability that the {@link #getY() y} part of this binary node is <b>not</b> 91 * evaluated. This is the probability that this operator will short-circuit its execution. 92 */ getShortCircuitProbability()93 public double getShortCircuitProbability() { 94 return shortCircuitProbability; 95 } 96 canonicalizeNegation(LogicNode forX, LogicNode forY)97 protected ShortCircuitOrNode canonicalizeNegation(LogicNode forX, LogicNode forY) { 98 LogicNode xCond = forX; 99 boolean xNeg = xNegated; 100 while (xCond instanceof LogicNegationNode) { 101 xCond = ((LogicNegationNode) xCond).getValue(); 102 xNeg = !xNeg; 103 } 104 105 LogicNode yCond = forY; 106 boolean yNeg = yNegated; 107 while (yCond instanceof LogicNegationNode) { 108 yCond = ((LogicNegationNode) yCond).getValue(); 109 yNeg = !yNeg; 110 } 111 112 if (xCond != forX || yCond != forY) { 113 return new ShortCircuitOrNode(xCond, xNeg, yCond, yNeg, shortCircuitProbability); 114 } else { 115 return this; 116 } 117 } 118 119 @Override canonical(CanonicalizerTool tool, LogicNode forX, LogicNode forY)120 public LogicNode canonical(CanonicalizerTool tool, LogicNode forX, LogicNode forY) { 121 ShortCircuitOrNode ret = canonicalizeNegation(forX, forY); 122 if (ret != this) { 123 return ret; 124 } 125 NodeView view = NodeView.from(tool); 126 127 if (forX == forY) { 128 // @formatter:off 129 // a || a = a 130 // a || !a = true 131 // !a || a = true 132 // !a || !a = !a 133 // @formatter:on 134 if (isXNegated()) { 135 if (isYNegated()) { 136 // !a || !a = !a 137 return LogicNegationNode.create(forX); 138 } else { 139 // !a || a = true 140 return LogicConstantNode.tautology(); 141 } 142 } else { 143 if (isYNegated()) { 144 // a || !a = true 145 return LogicConstantNode.tautology(); 146 } else { 147 // a || a = a 148 return forX; 149 } 150 } 151 } 152 if (forX instanceof LogicConstantNode) { 153 if (((LogicConstantNode) forX).getValue() ^ isXNegated()) { 154 return LogicConstantNode.tautology(); 155 } else { 156 if (isYNegated()) { 157 return new LogicNegationNode(forY); 158 } else { 159 return forY; 160 } 161 } 162 } 163 if (forY instanceof LogicConstantNode) { 164 if (((LogicConstantNode) forY).getValue() ^ isYNegated()) { 165 return LogicConstantNode.tautology(); 166 } else { 167 if (isXNegated()) { 168 return new LogicNegationNode(forX); 169 } else { 170 return forX; 171 } 172 } 173 } 174 175 if (forX instanceof ShortCircuitOrNode) { 176 ShortCircuitOrNode inner = (ShortCircuitOrNode) forX; 177 if (forY == inner.getX()) { 178 return optimizeShortCircuit(inner, this.xNegated, this.yNegated, true); 179 } else if (forY == inner.getY()) { 180 return optimizeShortCircuit(inner, this.xNegated, this.yNegated, false); 181 } 182 } else if (forY instanceof ShortCircuitOrNode) { 183 ShortCircuitOrNode inner = (ShortCircuitOrNode) forY; 184 if (inner.getX() == forX) { 185 return optimizeShortCircuit(inner, this.yNegated, this.xNegated, true); 186 } else if (inner.getY() == forX) { 187 return optimizeShortCircuit(inner, this.yNegated, this.xNegated, false); 188 } 189 } 190 191 // !X => Y constant 192 TriState impliedForY = forX.implies(!isXNegated(), forY); 193 if (impliedForY.isKnown()) { 194 boolean yResult = impliedForY.toBoolean() ^ isYNegated(); 195 return yResult 196 ? LogicConstantNode.tautology() 197 : (isXNegated() 198 ? LogicNegationNode.create(forX) 199 : forX); 200 } 201 202 // if X >= 0: 203 // u < 0 || X < u ==>> X |<| u 204 if (!isXNegated() && !isYNegated()) { 205 LogicNode sym = simplifyComparison(forX, forY); 206 if (sym != null) { 207 return sym; 208 } 209 } 210 211 // if X >= 0: 212 // X |<| u || X < u ==>> X |<| u 213 if (forX instanceof IntegerBelowNode && forY instanceof IntegerLessThanNode && !isXNegated() && !isYNegated()) { 214 IntegerBelowNode xNode = (IntegerBelowNode) forX; 215 IntegerLessThanNode yNode = (IntegerLessThanNode) forY; 216 ValueNode xxNode = xNode.getX(); // X >= 0 217 ValueNode yxNode = yNode.getX(); // X >= 0 218 if (xxNode == yxNode && ((IntegerStamp) xxNode.stamp(view)).isPositive()) { 219 ValueNode xyNode = xNode.getY(); // u 220 ValueNode yyNode = yNode.getY(); // u 221 if (xyNode == yyNode) { 222 return forX; 223 } 224 } 225 } 226 227 // if X >= 0: 228 // u < 0 || (X < u || tail) ==>> X |<| u || tail 229 if (forY instanceof ShortCircuitOrNode && !isXNegated() && !isYNegated()) { 230 ShortCircuitOrNode yNode = (ShortCircuitOrNode) forY; 231 if (!yNode.isXNegated()) { 232 LogicNode sym = simplifyComparison(forX, yNode.getX()); 233 if (sym != null) { 234 double p1 = getShortCircuitProbability(); 235 double p2 = yNode.getShortCircuitProbability(); 236 return new ShortCircuitOrNode(sym, isXNegated(), yNode.getY(), yNode.isYNegated(), p1 + (1 - p1) * p2); 237 } 238 } 239 } 240 241 if (forX instanceof CompareNode && forY instanceof CompareNode) { 242 CompareNode xCompare = (CompareNode) forX; 243 CompareNode yCompare = (CompareNode) forY; 244 245 if (xCompare.getX() == yCompare.getX() || xCompare.getX() == yCompare.getY()) { 246 247 Stamp succeedingStampX = xCompare.getSucceedingStampForX(!xNegated, xCompare.getX().stamp(view), xCompare.getY().stamp(view)); 248 // Try to canonicalize the other comparison using the knowledge gained from assuming 249 // the first part of the short circuit or is false (which is the only relevant case 250 // for the second part of the short circuit or). 251 if (succeedingStampX != null && !succeedingStampX.isUnrestricted()) { 252 CanonicalizerTool proxyTool = new ProxyCanonicalizerTool(succeedingStampX, xCompare.getX(), tool, view); 253 ValueNode result = yCompare.canonical(proxyTool); 254 if (result != yCompare) { 255 return ShortCircuitOrNode.create(forX, xNegated, (LogicNode) result, yNegated, this.shortCircuitProbability); 256 } 257 } 258 } 259 } 260 261 return this; 262 } 263 264 private static class ProxyCanonicalizerTool implements CanonicalizerTool, NodeView { 265 266 private final Stamp stamp; 267 private final ValueNode node; 268 private final CanonicalizerTool tool; 269 private final NodeView view; 270 ProxyCanonicalizerTool(Stamp stamp, ValueNode node, CanonicalizerTool tool, NodeView view)271 ProxyCanonicalizerTool(Stamp stamp, ValueNode node, CanonicalizerTool tool, NodeView view) { 272 this.stamp = stamp; 273 this.node = node; 274 this.tool = tool; 275 this.view = view; 276 } 277 278 @Override stamp(ValueNode n)279 public Stamp stamp(ValueNode n) { 280 if (n == node) { 281 return stamp; 282 } 283 return view.stamp(n); 284 } 285 286 @Override getAssumptions()287 public Assumptions getAssumptions() { 288 return tool.getAssumptions(); 289 } 290 291 @Override getMetaAccess()292 public MetaAccessProvider getMetaAccess() { 293 return tool.getMetaAccess(); 294 } 295 296 @Override getConstantReflection()297 public ConstantReflectionProvider getConstantReflection() { 298 return tool.getConstantReflection(); 299 } 300 301 @Override getConstantFieldProvider()302 public ConstantFieldProvider getConstantFieldProvider() { 303 return tool.getConstantFieldProvider(); 304 } 305 306 @Override canonicalizeReads()307 public boolean canonicalizeReads() { 308 return tool.canonicalizeReads(); 309 } 310 311 @Override allUsagesAvailable()312 public boolean allUsagesAvailable() { 313 return tool.allUsagesAvailable(); 314 } 315 316 @Override smallestCompareWidth()317 public Integer smallestCompareWidth() { 318 return tool.smallestCompareWidth(); 319 } 320 321 @Override getOptions()322 public OptionValues getOptions() { 323 return tool.getOptions(); 324 } 325 } 326 simplifyComparison(LogicNode forX, LogicNode forY)327 private static LogicNode simplifyComparison(LogicNode forX, LogicNode forY) { 328 LogicNode sym = simplifyComparisonOrdered(forX, forY); 329 if (sym == null) { 330 return simplifyComparisonOrdered(forY, forX); 331 } 332 return sym; 333 } 334 simplifyComparisonOrdered(LogicNode forX, LogicNode forY)335 private static LogicNode simplifyComparisonOrdered(LogicNode forX, LogicNode forY) { 336 // if X is >= 0: 337 // u < 0 || X < u ==>> X |<| u 338 if (forX instanceof IntegerLessThanNode && forY instanceof IntegerLessThanNode) { 339 IntegerLessThanNode xNode = (IntegerLessThanNode) forX; 340 IntegerLessThanNode yNode = (IntegerLessThanNode) forY; 341 ValueNode xyNode = xNode.getY(); // 0 342 if (xyNode.isConstant() && IntegerStamp.OPS.getAdd().isNeutral(xyNode.asConstant())) { 343 ValueNode yxNode = yNode.getX(); // X >= 0 344 IntegerStamp stamp = (IntegerStamp) yxNode.stamp(NodeView.DEFAULT); 345 if (stamp.isPositive()) { 346 if (xNode.getX() == yNode.getY()) { 347 ValueNode u = xNode.getX(); 348 return IntegerBelowNode.create(yxNode, u, NodeView.DEFAULT); 349 } 350 } 351 } 352 } 353 354 return null; 355 } 356 optimizeShortCircuit(ShortCircuitOrNode inner, boolean innerNegated, boolean matchNegated, boolean matchIsInnerX)357 private static LogicNode optimizeShortCircuit(ShortCircuitOrNode inner, boolean innerNegated, boolean matchNegated, boolean matchIsInnerX) { 358 boolean innerMatchNegated; 359 if (matchIsInnerX) { 360 innerMatchNegated = inner.isXNegated(); 361 } else { 362 innerMatchNegated = inner.isYNegated(); 363 } 364 if (!innerNegated) { 365 // The four digit results of the expression used in the 16 subsequent formula comments 366 // correspond to results when using the following truth table for inputs a and b 367 // and testing all 4 possible input combinations: 368 // _ 1234 369 // a 1100 370 // b 1010 371 if (innerMatchNegated == matchNegated) { 372 // ( (!a ||!b) ||!a) => 0111 (!a ||!b) 373 // ( (!a || b) ||!a) => 1011 (!a || b) 374 // ( ( a ||!b) || a) => 1101 ( a ||!b) 375 // ( ( a || b) || a) => 1110 ( a || b) 376 // Only the inner or is relevant, the outer or never adds information. 377 return inner; 378 } else { 379 // ( ( a || b) ||!a) => 1111 (true) 380 // ( (!a ||!b) || a) => 1111 (true) 381 // ( (!a || b) || a) => 1111 (true) 382 // ( ( a ||!b) ||!a) => 1111 (true) 383 // The result of the expression is always true. 384 return LogicConstantNode.tautology(); 385 } 386 } else { 387 if (innerMatchNegated == matchNegated) { 388 // (!(!a ||!b) ||!a) => 1011 (!a || b) 389 // (!(!a || b) ||!a) => 0111 (!a ||!b) 390 // (!( a ||!b) || a) => 1110 ( a || b) 391 // (!( a || b) || a) => 1101 ( a ||!b) 392 boolean newInnerXNegated = inner.isXNegated(); 393 boolean newInnerYNegated = inner.isYNegated(); 394 double newProbability = inner.getShortCircuitProbability(); 395 if (matchIsInnerX) { 396 newInnerYNegated = !newInnerYNegated; 397 } else { 398 newInnerXNegated = !newInnerXNegated; 399 newProbability = 1.0 - newProbability; 400 } 401 // The expression can be transformed into a single or. 402 return new ShortCircuitOrNode(inner.getX(), newInnerXNegated, inner.getY(), newInnerYNegated, newProbability); 403 } else { 404 // (!(!a ||!b) || a) => 1100 (a) 405 // (!(!a || b) || a) => 1100 (a) 406 // (!( a ||!b) ||!a) => 0011 (!a) 407 // (!( a || b) ||!a) => 0011 (!a) 408 LogicNode result = inner.getY(); 409 if (matchIsInnerX) { 410 result = inner.getX(); 411 } 412 // Only the second part of the outer or is relevant. 413 if (matchNegated) { 414 return LogicNegationNode.create(result); 415 } else { 416 return result; 417 } 418 } 419 } 420 } 421 } 422