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 IntegerEqualsNode(ValueNode x, ValueNode y)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 create(ValueNode x, ValueNode y, NodeView view)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 create(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, ValueNode x, ValueNode y, NodeView view)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 canonical(CanonicalizerTool tool, ValueNode forX, ValueNode forY)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 optimizeNormalizeCompare(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, Constant constant, AbstractNormalizeCompareNode normalizeNode, boolean mirrored, NodeView view)111 protected LogicNode optimizeNormalizeCompare(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, 112 Constant constant, AbstractNormalizeCompareNode normalizeNode, boolean mirrored, NodeView view) { 113 PrimitiveConstant primitive = (PrimitiveConstant) constant; 114 long cst = primitive.asLong(); 115 if (cst == 0) { 116 return normalizeNode.createEqualComparison(constantReflection, metaAccess, options, smallestCompareWidth, view); 117 } else if (cst == 1) { 118 return normalizeNode.createLowerComparison(true, constantReflection, metaAccess, options, smallestCompareWidth, view); 119 } else if (cst == -1) { 120 return normalizeNode.createLowerComparison(false, constantReflection, metaAccess, options, smallestCompareWidth, view); 121 } else { 122 return LogicConstantNode.contradiction(); 123 } 124 } 125 126 @Override duplicateModified(ValueNode newX, ValueNode newY, boolean unorderedIsTrue, NodeView view)127 protected CompareNode duplicateModified(ValueNode newX, ValueNode newY, boolean unorderedIsTrue, NodeView view) { 128 if (newX.stamp(view) instanceof FloatStamp && newY.stamp(view) instanceof FloatStamp) { 129 return new FloatEqualsNode(newX, newY); 130 } else if (newX.stamp(view) instanceof IntegerStamp && newY.stamp(view) instanceof IntegerStamp) { 131 return new IntegerEqualsNode(newX, newY); 132 } else if (newX.stamp(view) instanceof AbstractPointerStamp && newY.stamp(view) instanceof AbstractPointerStamp) { 133 return new IntegerEqualsNode(newX, newY); 134 } 135 throw GraalError.shouldNotReachHere(); 136 } 137 138 @Override canonical(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, CanonicalCondition condition, boolean unorderedIsTrue, ValueNode forX, ValueNode forY, NodeView view)139 public LogicNode canonical(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, CanonicalCondition condition, 140 boolean unorderedIsTrue, ValueNode forX, ValueNode forY, NodeView view) { 141 if (GraphUtil.unproxify(forX) == GraphUtil.unproxify(forY)) { 142 return LogicConstantNode.tautology(); 143 } else if (forX.stamp(view).alwaysDistinct(forY.stamp(view))) { 144 return LogicConstantNode.contradiction(); 145 } 146 147 if (forX instanceof AddNode && forY instanceof AddNode) { 148 AddNode addX = (AddNode) forX; 149 AddNode addY = (AddNode) forY; 150 ValueNode v1 = null; 151 ValueNode v2 = null; 152 if (addX.getX() == addY.getX()) { 153 // (x + y) == (x + z) => y == z 154 v1 = addX.getY(); 155 v2 = addY.getY(); 156 } else if (addX.getX() == addY.getY()) { 157 // (x + y) == (z + x) => y == z 158 v1 = addX.getY(); 159 v2 = addY.getX(); 160 } else if (addX.getY() == addY.getX()) { 161 // (y + x) == (x + z) => y == z 162 v1 = addX.getX(); 163 v2 = addY.getY(); 164 } else if (addX.getY() == addY.getY()) { 165 // (y + x) == (z + x) => y == z 166 v1 = addX.getX(); 167 v2 = addY.getX(); 168 } 169 if (v1 != null) { 170 assert v2 != null; 171 return create(v1, v2, view); 172 } 173 } 174 175 if (forX instanceof SubNode && forY instanceof SubNode) { 176 SubNode subX = (SubNode) forX; 177 SubNode subY = (SubNode) forY; 178 ValueNode v1 = null; 179 ValueNode v2 = null; 180 if (subX.getX() == subY.getX()) { 181 // (x - y) == (x - z) => y == z 182 v1 = subX.getY(); 183 v2 = subY.getY(); 184 } else if (subX.getY() == subY.getY()) { 185 // (y - x) == (z - x) => y == z 186 v1 = subX.getX(); 187 v2 = subY.getX(); 188 } 189 if (v1 != null) { 190 assert v2 != null; 191 return create(v1, v2, view); 192 } 193 } 194 195 if (forX instanceof AddNode) { 196 AddNode addNode = (AddNode) forX; 197 if (addNode.getX() == forY) { 198 // (x + y) == x => y == 0 199 return create(addNode.getY(), ConstantNode.forIntegerStamp(view.stamp(addNode), 0), view); 200 } else if (addNode.getY() == forY) { 201 // (x + y) == y => x == 0 202 return create(addNode.getX(), ConstantNode.forIntegerStamp(view.stamp(addNode), 0), view); 203 } 204 } 205 206 if (forY instanceof AddNode) { 207 AddNode addNode = (AddNode) forY; 208 if (addNode.getX() == forX) { 209 // x == (x + y) => y == 0 210 return create(addNode.getY(), ConstantNode.forIntegerStamp(view.stamp(addNode), 0), view); 211 } else if (addNode.getY() == forX) { 212 // y == (x + y) => x == 0 213 return create(addNode.getX(), ConstantNode.forIntegerStamp(view.stamp(addNode), 0), view); 214 } 215 } 216 217 if (forX instanceof SubNode) { 218 SubNode subNode = (SubNode) forX; 219 if (subNode.getX() == forY) { 220 // (x - y) == x => y == 0 221 return create(subNode.getY(), ConstantNode.forIntegerStamp(view.stamp(subNode), 0), view); 222 } 223 } 224 225 if (forY instanceof SubNode) { 226 SubNode subNode = (SubNode) forY; 227 if (forX == subNode.getX()) { 228 // x == (x - y) => y == 0 229 return create(subNode.getY(), ConstantNode.forIntegerStamp(view.stamp(subNode), 0), view); 230 } 231 } 232 233 return super.canonical(constantReflection, metaAccess, options, smallestCompareWidth, condition, unorderedIsTrue, forX, forY, view); 234 } 235 236 @Override canonicalizeSymmetricConstant(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, CanonicalCondition condition, Constant constant, ValueNode nonConstant, boolean mirrored, boolean unorderedIsTrue, NodeView view)237 protected LogicNode canonicalizeSymmetricConstant(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, 238 CanonicalCondition condition, Constant constant, ValueNode nonConstant, boolean mirrored, boolean unorderedIsTrue, NodeView view) { 239 if (constant instanceof PrimitiveConstant) { 240 PrimitiveConstant primitiveConstant = (PrimitiveConstant) constant; 241 IntegerStamp nonConstantStamp = ((IntegerStamp) nonConstant.stamp(view)); 242 if ((primitiveConstant.asLong() == 1 && nonConstantStamp.upperBound() == 1 && nonConstantStamp.lowerBound() == 0) || 243 (primitiveConstant.asLong() == -1 && nonConstantStamp.upperBound() == 0 && nonConstantStamp.lowerBound() == -1)) { 244 // nonConstant can only be 0 or 1 (respective -1), test against 0 instead of 1 245 // (respective -1) for a more canonical graph and also to allow for faster 246 // execution 247 // on specific platforms. 248 return LogicNegationNode.create( 249 IntegerEqualsNode.create(constantReflection, metaAccess, options, smallestCompareWidth, nonConstant, ConstantNode.forIntegerStamp(nonConstantStamp, 0), 250 view)); 251 } else if (primitiveConstant.asLong() == 0) { 252 if (nonConstant instanceof AndNode) { 253 AndNode andNode = (AndNode) nonConstant; 254 return new IntegerTestNode(andNode.getX(), andNode.getY()); 255 } else if (nonConstant instanceof SubNode) { 256 SubNode subNode = (SubNode) nonConstant; 257 return IntegerEqualsNode.create(constantReflection, metaAccess, options, smallestCompareWidth, subNode.getX(), subNode.getY(), view); 258 } else if (nonConstant instanceof ShiftNode && nonConstant.stamp(view) instanceof IntegerStamp) { 259 if (nonConstant instanceof LeftShiftNode) { 260 LeftShiftNode shift = (LeftShiftNode) nonConstant; 261 if (shift.getY().isConstant()) { 262 int mask = shift.getShiftAmountMask(); 263 int amount = shift.getY().asJavaConstant().asInt() & mask; 264 if (shift.getX().getStackKind() == JavaKind.Int) { 265 return new IntegerTestNode(shift.getX(), ConstantNode.forInt(-1 >>> amount)); 266 } else { 267 assert shift.getX().getStackKind() == JavaKind.Long; 268 return new IntegerTestNode(shift.getX(), ConstantNode.forLong(-1L >>> amount)); 269 } 270 } 271 } else if (nonConstant instanceof RightShiftNode) { 272 RightShiftNode shift = (RightShiftNode) nonConstant; 273 if (shift.getY().isConstant() && ((IntegerStamp) shift.getX().stamp(view)).isPositive()) { 274 int mask = shift.getShiftAmountMask(); 275 int amount = shift.getY().asJavaConstant().asInt() & mask; 276 if (shift.getX().getStackKind() == JavaKind.Int) { 277 return new IntegerTestNode(shift.getX(), ConstantNode.forInt(-1 << amount)); 278 } else { 279 assert shift.getX().getStackKind() == JavaKind.Long; 280 return new IntegerTestNode(shift.getX(), ConstantNode.forLong(-1L << amount)); 281 } 282 } 283 } else if (nonConstant instanceof UnsignedRightShiftNode) { 284 UnsignedRightShiftNode shift = (UnsignedRightShiftNode) nonConstant; 285 if (shift.getY().isConstant()) { 286 int mask = shift.getShiftAmountMask(); 287 int amount = shift.getY().asJavaConstant().asInt() & mask; 288 if (shift.getX().getStackKind() == JavaKind.Int) { 289 return new IntegerTestNode(shift.getX(), ConstantNode.forInt(-1 << amount)); 290 } else { 291 assert shift.getX().getStackKind() == JavaKind.Long; 292 return new IntegerTestNode(shift.getX(), ConstantNode.forLong(-1L << amount)); 293 } 294 } 295 } 296 } 297 } 298 if (nonConstant instanceof AddNode) { 299 AddNode addNode = (AddNode) nonConstant; 300 if (addNode.getY().isJavaConstant()) { 301 return new IntegerEqualsNode(addNode.getX(), ConstantNode.forIntegerStamp(nonConstantStamp, primitiveConstant.asLong() - addNode.getY().asJavaConstant().asLong())); 302 } 303 } 304 if (nonConstant instanceof AndNode) { 305 /* 306 * a & c == c is the same as a & c != 0, if c is a single bit. 307 */ 308 AndNode andNode = (AndNode) nonConstant; 309 if (Long.bitCount(((PrimitiveConstant) constant).asLong()) == 1 && andNode.getY().isConstant() && andNode.getY().asJavaConstant().equals(constant)) { 310 return new LogicNegationNode(new IntegerTestNode(andNode.getX(), andNode.getY())); 311 } 312 } 313 314 if (nonConstant instanceof XorNode && nonConstant.stamp(view) instanceof IntegerStamp) { 315 XorNode xorNode = (XorNode) nonConstant; 316 if (xorNode.getY().isJavaConstant() && xorNode.getY().asJavaConstant().asLong() == 1 && ((IntegerStamp) xorNode.getX().stamp(view)).upMask() == 1) { 317 // x ^ 1 == 0 is the same as x == 1 if x in [0, 1] 318 // x ^ 1 == 1 is the same as x == 0 if x in [0, 1] 319 return new IntegerEqualsNode(xorNode.getX(), ConstantNode.forIntegerStamp(xorNode.getX().stamp(view), primitiveConstant.asLong() ^ 1)); 320 } 321 } 322 } 323 return super.canonicalizeSymmetricConstant(constantReflection, metaAccess, options, smallestCompareWidth, condition, constant, nonConstant, mirrored, unorderedIsTrue, view); 324 } 325 } 326 327 @Override getSucceedingStampForX(boolean negated, Stamp xStamp, Stamp yStamp)328 public Stamp getSucceedingStampForX(boolean negated, Stamp xStamp, Stamp yStamp) { 329 if (!negated) { 330 return xStamp.join(yStamp); 331 } 332 return null; 333 } 334 335 @Override getSucceedingStampForY(boolean negated, Stamp xStamp, Stamp yStamp)336 public Stamp getSucceedingStampForY(boolean negated, Stamp xStamp, Stamp yStamp) { 337 if (!negated) { 338 return xStamp.join(yStamp); 339 } 340 return null; 341 } 342 343 @Override tryFold(Stamp xStampGeneric, Stamp yStampGeneric)344 public TriState tryFold(Stamp xStampGeneric, Stamp yStampGeneric) { 345 if (xStampGeneric instanceof IntegerStamp && yStampGeneric instanceof IntegerStamp) { 346 IntegerStamp xStamp = (IntegerStamp) xStampGeneric; 347 IntegerStamp yStamp = (IntegerStamp) yStampGeneric; 348 if (xStamp.alwaysDistinct(yStamp)) { 349 return TriState.FALSE; 350 } else if (xStamp.neverDistinct(yStamp)) { 351 return TriState.TRUE; 352 } 353 } 354 return TriState.UNKNOWN; 355 } 356 357 @Override implies(boolean thisNegated, LogicNode other)358 public TriState implies(boolean thisNegated, LogicNode other) { 359 // x == y => !(x < y) 360 // x == y => !(y < x) 361 if (!thisNegated && other instanceof IntegerLessThanNode) { 362 ValueNode otherX = ((IntegerLessThanNode) other).getX(); 363 ValueNode otherY = ((IntegerLessThanNode) other).getY(); 364 if ((getX() == otherX && getY() == otherY) || (getX() == otherY && getY() == otherX)) { 365 return TriState.FALSE; 366 } 367 } 368 369 return super.implies(thisNegated, other); 370 } 371 } 372