1 /* 2 * Copyright (c) 2011, 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.calc; 26 27 import org.graalvm.compiler.core.common.calc.CanonicalCondition; 28 import org.graalvm.compiler.core.common.type.AbstractPointerStamp; 29 import org.graalvm.compiler.core.common.type.FloatStamp; 30 import org.graalvm.compiler.core.common.type.IntegerStamp; 31 import org.graalvm.compiler.core.common.type.Stamp; 32 import org.graalvm.compiler.debug.GraalError; 33 import org.graalvm.compiler.graph.Node; 34 import org.graalvm.compiler.graph.NodeClass; 35 import org.graalvm.compiler.graph.spi.Canonicalizable.BinaryCommutative; 36 import org.graalvm.compiler.graph.spi.CanonicalizerTool; 37 import org.graalvm.compiler.nodeinfo.NodeInfo; 38 import org.graalvm.compiler.nodes.ConstantNode; 39 import org.graalvm.compiler.nodes.LogicConstantNode; 40 import org.graalvm.compiler.nodes.LogicNegationNode; 41 import org.graalvm.compiler.nodes.LogicNode; 42 import org.graalvm.compiler.nodes.NodeView; 43 import org.graalvm.compiler.nodes.ValueNode; 44 import org.graalvm.compiler.nodes.util.GraphUtil; 45 import org.graalvm.compiler.options.OptionValues; 46 47 import jdk.vm.ci.meta.Constant; 48 import jdk.vm.ci.meta.ConstantReflectionProvider; 49 import jdk.vm.ci.meta.JavaKind; 50 import jdk.vm.ci.meta.MetaAccessProvider; 51 import jdk.vm.ci.meta.PrimitiveConstant; 52 import jdk.vm.ci.meta.TriState; 53 54 @NodeInfo(shortName = "==") 55 public final class IntegerEqualsNode extends CompareNode implements BinaryCommutative<ValueNode> { 56 public static final NodeClass<IntegerEqualsNode> TYPE = NodeClass.create(IntegerEqualsNode.class); 57 private static final IntegerEqualsOp OP = new IntegerEqualsOp(); 58 59 public IntegerEqualsNode(ValueNode x, ValueNode y) { 60 super(TYPE, CanonicalCondition.EQ, false, x, y); 61 assert !x.getStackKind().isNumericFloat() && x.getStackKind() != JavaKind.Object; 62 assert !y.getStackKind().isNumericFloat() && y.getStackKind() != JavaKind.Object; 63 } 64 65 public static LogicNode create(ValueNode x, ValueNode y, NodeView view) { 66 LogicNode result = CompareNode.tryConstantFoldPrimitive(CanonicalCondition.EQ, x, y, false, view); 67 if (result != null) { 68 return result; 69 } 70 if (x instanceof ConditionalNode) { 71 ConditionalNode conditionalNode = (ConditionalNode) x; 72 if (conditionalNode.trueValue() == y) { 73 return conditionalNode.condition(); 74 } 75 if (conditionalNode.falseValue() == y) { 76 return LogicNegationNode.create(conditionalNode.condition()); 77 } 78 } else if (y instanceof ConditionalNode) { 79 ConditionalNode conditionalNode = (ConditionalNode) y; 80 if (conditionalNode.trueValue() == x) { 81 return conditionalNode.condition(); 82 } 83 if (conditionalNode.falseValue() == x) { 84 return LogicNegationNode.create(conditionalNode.condition()); 85 } 86 } 87 return new IntegerEqualsNode(x, y).maybeCommuteInputs(); 88 } 89 90 public static LogicNode create(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, ValueNode x, ValueNode y, 91 NodeView view) { 92 LogicNode value = OP.canonical(constantReflection, metaAccess, options, smallestCompareWidth, CanonicalCondition.EQ, false, x, y, view); 93 if (value != null) { 94 return value; 95 } 96 return create(x, y, view); 97 } 98 99 @Override 100 public Node canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY) { 101 NodeView view = NodeView.from(tool); 102 ValueNode value = OP.canonical(tool.getConstantReflection(), tool.getMetaAccess(), tool.getOptions(), tool.smallestCompareWidth(), CanonicalCondition.EQ, false, forX, forY, view); 103 if (value != null) { 104 return value; 105 } 106 return this; 107 } 108 109 public static class IntegerEqualsOp extends CompareOp { 110 @Override 111 protected LogicNode optimizeNormalizeCompare(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, 112 Constant constant, NormalizeCompareNode normalizeNode, boolean mirrored, NodeView view) { 113 PrimitiveConstant primitive = (PrimitiveConstant) constant; 114 ValueNode a = normalizeNode.getX(); 115 ValueNode b = normalizeNode.getY(); 116 long cst = primitive.asLong(); 117 118 if (cst == 0) { 119 if (normalizeNode.getX().getStackKind() == JavaKind.Double || normalizeNode.getX().getStackKind() == JavaKind.Float) { 120 return FloatEqualsNode.create(constantReflection, metaAccess, options, smallestCompareWidth, a, b, view); 121 } else { 122 return IntegerEqualsNode.create(constantReflection, metaAccess, options, smallestCompareWidth, a, b, view); 123 } 124 } else if (cst == 1) { 125 if (normalizeNode.getX().getStackKind() == JavaKind.Double || normalizeNode.getX().getStackKind() == JavaKind.Float) { 126 return FloatLessThanNode.create(b, a, !normalizeNode.isUnorderedLess, view); 127 } else { 128 return IntegerLessThanNode.create(constantReflection, metaAccess, options, smallestCompareWidth, b, a, view); 129 } 130 } else if (cst == -1) { 131 if (normalizeNode.getX().getStackKind() == JavaKind.Double || normalizeNode.getX().getStackKind() == JavaKind.Float) { 132 return FloatLessThanNode.create(a, b, normalizeNode.isUnorderedLess, view); 133 } else { 134 return IntegerLessThanNode.create(constantReflection, metaAccess, options, smallestCompareWidth, a, b, view); 135 } 136 } else { 137 return LogicConstantNode.contradiction(); 138 } 139 } 140 141 @Override 142 protected CompareNode duplicateModified(ValueNode newX, ValueNode newY, boolean unorderedIsTrue, NodeView view) { 143 if (newX.stamp(view) instanceof FloatStamp && newY.stamp(view) instanceof FloatStamp) { 144 return new FloatEqualsNode(newX, newY); 145 } else if (newX.stamp(view) instanceof IntegerStamp && newY.stamp(view) instanceof IntegerStamp) { 146 return new IntegerEqualsNode(newX, newY); 147 } else if (newX.stamp(view) instanceof AbstractPointerStamp && newY.stamp(view) instanceof AbstractPointerStamp) { 148 return new IntegerEqualsNode(newX, newY); 149 } 150 throw GraalError.shouldNotReachHere(); 151 } 152 153 @Override 154 public LogicNode canonical(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, CanonicalCondition condition, 155 boolean unorderedIsTrue, ValueNode forX, ValueNode forY, NodeView view) { 156 if (GraphUtil.unproxify(forX) == GraphUtil.unproxify(forY)) { 157 return LogicConstantNode.tautology(); 158 } else if (forX.stamp(view).alwaysDistinct(forY.stamp(view))) { 159 return LogicConstantNode.contradiction(); 160 } 161 162 if (forX instanceof AddNode && forY instanceof AddNode) { 163 AddNode addX = (AddNode) forX; 164 AddNode addY = (AddNode) forY; 165 ValueNode v1 = null; 166 ValueNode v2 = null; 167 if (addX.getX() == addY.getX()) { 168 // (x + y) == (x + z) => y == z 169 v1 = addX.getY(); 170 v2 = addY.getY(); 171 } else if (addX.getX() == addY.getY()) { 172 // (x + y) == (z + x) => y == z 173 v1 = addX.getY(); 174 v2 = addY.getX(); 175 } else if (addX.getY() == addY.getX()) { 176 // (y + x) == (x + z) => y == z 177 v1 = addX.getX(); 178 v2 = addY.getY(); 179 } else if (addX.getY() == addY.getY()) { 180 // (y + x) == (z + x) => y == z 181 v1 = addX.getX(); 182 v2 = addY.getX(); 183 } 184 if (v1 != null) { 185 assert v2 != null; 186 return create(v1, v2, view); 187 } 188 } 189 190 if (forX instanceof SubNode && forY instanceof SubNode) { 191 SubNode subX = (SubNode) forX; 192 SubNode subY = (SubNode) forY; 193 ValueNode v1 = null; 194 ValueNode v2 = null; 195 if (subX.getX() == subY.getX()) { 196 // (x - y) == (x - z) => y == z 197 v1 = subX.getY(); 198 v2 = subY.getY(); 199 } else if (subX.getY() == subY.getY()) { 200 // (y - x) == (z - x) => y == z 201 v1 = subX.getX(); 202 v2 = subY.getX(); 203 } 204 if (v1 != null) { 205 assert v2 != null; 206 return create(v1, v2, view); 207 } 208 } 209 210 if (forX instanceof AddNode) { 211 AddNode addNode = (AddNode) forX; 212 if (addNode.getX() == forY) { 213 // (x + y) == x => y == 0 214 return create(addNode.getY(), ConstantNode.forIntegerStamp(view.stamp(addNode), 0), view); 215 } else if (addNode.getY() == forY) { 216 // (x + y) == y => x == 0 217 return create(addNode.getX(), ConstantNode.forIntegerStamp(view.stamp(addNode), 0), view); 218 } 219 } 220 221 if (forY instanceof AddNode) { 222 AddNode addNode = (AddNode) forY; 223 if (addNode.getX() == forX) { 224 // x == (x + y) => y == 0 225 return create(addNode.getY(), ConstantNode.forIntegerStamp(view.stamp(addNode), 0), view); 226 } else if (addNode.getY() == forX) { 227 // y == (x + y) => x == 0 228 return create(addNode.getX(), ConstantNode.forIntegerStamp(view.stamp(addNode), 0), view); 229 } 230 } 231 232 if (forX instanceof SubNode) { 233 SubNode subNode = (SubNode) forX; 234 if (subNode.getX() == forY) { 235 // (x - y) == x => y == 0 236 return create(subNode.getY(), ConstantNode.forIntegerStamp(view.stamp(subNode), 0), view); 237 } 238 } 239 240 if (forY instanceof SubNode) { 241 SubNode subNode = (SubNode) forY; 242 if (forX == subNode.getX()) { 243 // x == (x - y) => y == 0 244 return create(subNode.getY(), ConstantNode.forIntegerStamp(view.stamp(subNode), 0), view); 245 } 246 } 247 248 return super.canonical(constantReflection, metaAccess, options, smallestCompareWidth, condition, unorderedIsTrue, forX, forY, view); 249 } 250 251 @Override 252 protected LogicNode canonicalizeSymmetricConstant(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, 253 CanonicalCondition condition, Constant constant, ValueNode nonConstant, boolean mirrored, boolean unorderedIsTrue, NodeView view) { 254 if (constant instanceof PrimitiveConstant) { 255 PrimitiveConstant primitiveConstant = (PrimitiveConstant) constant; 256 IntegerStamp nonConstantStamp = ((IntegerStamp) nonConstant.stamp(view)); 257 if ((primitiveConstant.asLong() == 1 && nonConstantStamp.upperBound() == 1 && nonConstantStamp.lowerBound() == 0) || 258 (primitiveConstant.asLong() == -1 && nonConstantStamp.upperBound() == 0 && nonConstantStamp.lowerBound() == -1)) { 259 // nonConstant can only be 0 or 1 (respective -1), test against 0 instead of 1 260 // (respective -1) for a more canonical graph and also to allow for faster 261 // execution 262 // on specific platforms. 263 return LogicNegationNode.create( 264 IntegerEqualsNode.create(constantReflection, metaAccess, options, smallestCompareWidth, nonConstant, ConstantNode.forIntegerStamp(nonConstantStamp, 0), 265 view)); 266 } else if (primitiveConstant.asLong() == 0) { 267 if (nonConstant instanceof AndNode) { 268 AndNode andNode = (AndNode) nonConstant; 269 return new IntegerTestNode(andNode.getX(), andNode.getY()); 270 } else if (nonConstant instanceof SubNode) { 271 SubNode subNode = (SubNode) nonConstant; 272 return IntegerEqualsNode.create(constantReflection, metaAccess, options, smallestCompareWidth, subNode.getX(), subNode.getY(), view); 273 } else if (nonConstant instanceof ShiftNode && nonConstant.stamp(view) instanceof IntegerStamp) { 274 if (nonConstant instanceof LeftShiftNode) { 275 LeftShiftNode shift = (LeftShiftNode) nonConstant; 276 if (shift.getY().isConstant()) { 277 int mask = shift.getShiftAmountMask(); 278 int amount = shift.getY().asJavaConstant().asInt() & mask; 279 if (shift.getX().getStackKind() == JavaKind.Int) { 280 return new IntegerTestNode(shift.getX(), ConstantNode.forInt(-1 >>> amount)); 281 } else { 282 assert shift.getX().getStackKind() == JavaKind.Long; 283 return new IntegerTestNode(shift.getX(), ConstantNode.forLong(-1L >>> amount)); 284 } 285 } 286 } else if (nonConstant instanceof RightShiftNode) { 287 RightShiftNode shift = (RightShiftNode) nonConstant; 288 if (shift.getY().isConstant() && ((IntegerStamp) shift.getX().stamp(view)).isPositive()) { 289 int mask = shift.getShiftAmountMask(); 290 int amount = shift.getY().asJavaConstant().asInt() & mask; 291 if (shift.getX().getStackKind() == JavaKind.Int) { 292 return new IntegerTestNode(shift.getX(), ConstantNode.forInt(-1 << amount)); 293 } else { 294 assert shift.getX().getStackKind() == JavaKind.Long; 295 return new IntegerTestNode(shift.getX(), ConstantNode.forLong(-1L << amount)); 296 } 297 } 298 } else if (nonConstant instanceof UnsignedRightShiftNode) { 299 UnsignedRightShiftNode shift = (UnsignedRightShiftNode) nonConstant; 300 if (shift.getY().isConstant()) { 301 int mask = shift.getShiftAmountMask(); 302 int amount = shift.getY().asJavaConstant().asInt() & mask; 303 if (shift.getX().getStackKind() == JavaKind.Int) { 304 return new IntegerTestNode(shift.getX(), ConstantNode.forInt(-1 << amount)); 305 } else { 306 assert shift.getX().getStackKind() == JavaKind.Long; 307 return new IntegerTestNode(shift.getX(), ConstantNode.forLong(-1L << amount)); 308 } 309 } 310 } 311 } 312 } 313 if (nonConstant instanceof AddNode) { 314 AddNode addNode = (AddNode) nonConstant; 315 if (addNode.getY().isJavaConstant()) { 316 return new IntegerEqualsNode(addNode.getX(), ConstantNode.forIntegerStamp(nonConstantStamp, primitiveConstant.asLong() - addNode.getY().asJavaConstant().asLong())); 317 } 318 } 319 if (nonConstant instanceof AndNode) { 320 /* 321 * a & c == c is the same as a & c != 0, if c is a single bit. 322 */ 323 AndNode andNode = (AndNode) nonConstant; 324 if (Long.bitCount(((PrimitiveConstant) constant).asLong()) == 1 && andNode.getY().isConstant() && andNode.getY().asJavaConstant().equals(constant)) { 325 return new LogicNegationNode(new IntegerTestNode(andNode.getX(), andNode.getY())); 326 } 327 } 328 329 if (nonConstant instanceof XorNode && nonConstant.stamp(view) instanceof IntegerStamp) { 330 XorNode xorNode = (XorNode) nonConstant; 331 if (xorNode.getY().isJavaConstant() && xorNode.getY().asJavaConstant().asLong() == 1 && ((IntegerStamp) xorNode.getX().stamp(view)).upMask() == 1) { 332 // x ^ 1 == 0 is the same as x == 1 if x in [0, 1] 333 // x ^ 1 == 1 is the same as x == 0 if x in [0, 1] 334 return new IntegerEqualsNode(xorNode.getX(), ConstantNode.forIntegerStamp(xorNode.getX().stamp(view), primitiveConstant.asLong() ^ 1)); 335 } 336 } 337 } 338 return super.canonicalizeSymmetricConstant(constantReflection, metaAccess, options, smallestCompareWidth, condition, constant, nonConstant, mirrored, unorderedIsTrue, view); 339 } 340 } 341 342 @Override 343 public Stamp getSucceedingStampForX(boolean negated, Stamp xStamp, Stamp yStamp) { 344 if (!negated) { 345 return xStamp.join(yStamp); 346 } 347 return null; 348 } 349 350 @Override 351 public Stamp getSucceedingStampForY(boolean negated, Stamp xStamp, Stamp yStamp) { 352 if (!negated) { 353 return xStamp.join(yStamp); 354 } 355 return null; 356 } 357 358 @Override 359 public TriState tryFold(Stamp xStampGeneric, Stamp yStampGeneric) { 360 if (xStampGeneric instanceof IntegerStamp && yStampGeneric instanceof IntegerStamp) { 361 IntegerStamp xStamp = (IntegerStamp) xStampGeneric; 362 IntegerStamp yStamp = (IntegerStamp) yStampGeneric; 363 if (xStamp.alwaysDistinct(yStamp)) { 364 return TriState.FALSE; 365 } else if (xStamp.neverDistinct(yStamp)) { 366 return TriState.TRUE; 367 } 368 } 369 return TriState.UNKNOWN; 370 } 371 372 @Override 373 public TriState implies(boolean thisNegated, LogicNode other) { 374 // x == y => !(x < y) 375 // x == y => !(y < x) 376 if (!thisNegated && other instanceof IntegerLessThanNode) { 377 ValueNode otherX = ((IntegerLessThanNode) other).getX(); 378 ValueNode otherY = ((IntegerLessThanNode) other).getY(); 379 if ((getX() == otherX && getY() == otherY) || (getX() == otherY && getY() == otherX)) { 380 return TriState.FALSE; 381 } 382 } 383 384 return super.implies(thisNegated, other); 385 } 386 }