1 /* 2 * Copyright (c) 2011, 2015, 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 v1 = addX.getY(); 169 v2 = addY.getY(); 170 } else if (addX.getX() == addY.getY()) { 171 v1 = addX.getY(); 172 v2 = addY.getX(); 173 } else if (addX.getY() == addY.getX()) { 174 v1 = addX.getX(); 175 v2 = addY.getY(); 176 } else if (addX.getY() == addY.getY()) { 177 v1 = addX.getX(); 178 v2 = addY.getX(); 179 } 180 if (v1 != null) { 181 assert v2 != null; 182 return create(v1, v2, view); 183 } 184 } 185 186 return super.canonical(constantReflection, metaAccess, options, smallestCompareWidth, condition, unorderedIsTrue, forX, forY, view); 187 } 188 189 @Override 190 protected LogicNode canonicalizeSymmetricConstant(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, 191 CanonicalCondition condition, Constant constant, ValueNode nonConstant, boolean mirrored, boolean unorderedIsTrue, NodeView view) { 192 if (constant instanceof PrimitiveConstant) { 193 PrimitiveConstant primitiveConstant = (PrimitiveConstant) constant; 194 IntegerStamp nonConstantStamp = ((IntegerStamp) nonConstant.stamp(view)); 195 if ((primitiveConstant.asLong() == 1 && nonConstantStamp.upperBound() == 1 && nonConstantStamp.lowerBound() == 0) || 196 (primitiveConstant.asLong() == -1 && nonConstantStamp.upperBound() == 0 && nonConstantStamp.lowerBound() == -1)) { 197 // nonConstant can only be 0 or 1 (respective -1), test against 0 instead of 1 198 // (respective -1) for a more canonical graph and also to allow for faster 199 // execution 200 // on specific platforms. 201 return LogicNegationNode.create( 202 IntegerEqualsNode.create(constantReflection, metaAccess, options, smallestCompareWidth, nonConstant, ConstantNode.forIntegerKind(nonConstant.getStackKind(), 0), 203 view)); 204 } else if (primitiveConstant.asLong() == 0) { 205 if (nonConstant instanceof AndNode) { 206 AndNode andNode = (AndNode) nonConstant; 207 return new IntegerTestNode(andNode.getX(), andNode.getY()); 208 } else if (nonConstant instanceof SubNode) { 209 SubNode subNode = (SubNode) nonConstant; 210 return IntegerEqualsNode.create(constantReflection, metaAccess, options, smallestCompareWidth, subNode.getX(), subNode.getY(), view); 211 } else if (nonConstant instanceof ShiftNode && nonConstant.stamp(view) instanceof IntegerStamp) { 212 if (nonConstant instanceof LeftShiftNode) { 213 LeftShiftNode shift = (LeftShiftNode) nonConstant; 214 if (shift.getY().isConstant()) { 215 int mask = shift.getShiftAmountMask(); 216 int amount = shift.getY().asJavaConstant().asInt() & mask; 217 if (shift.getX().getStackKind() == JavaKind.Int) { 218 return new IntegerTestNode(shift.getX(), ConstantNode.forInt(-1 >>> amount)); 219 } else { 220 assert shift.getX().getStackKind() == JavaKind.Long; 221 return new IntegerTestNode(shift.getX(), ConstantNode.forLong(-1L >>> amount)); 222 } 223 } 224 } else if (nonConstant instanceof RightShiftNode) { 225 RightShiftNode shift = (RightShiftNode) nonConstant; 226 if (shift.getY().isConstant() && ((IntegerStamp) shift.getX().stamp(view)).isPositive()) { 227 int mask = shift.getShiftAmountMask(); 228 int amount = shift.getY().asJavaConstant().asInt() & mask; 229 if (shift.getX().getStackKind() == JavaKind.Int) { 230 return new IntegerTestNode(shift.getX(), ConstantNode.forInt(-1 << amount)); 231 } else { 232 assert shift.getX().getStackKind() == JavaKind.Long; 233 return new IntegerTestNode(shift.getX(), ConstantNode.forLong(-1L << amount)); 234 } 235 } 236 } else if (nonConstant instanceof UnsignedRightShiftNode) { 237 UnsignedRightShiftNode shift = (UnsignedRightShiftNode) nonConstant; 238 if (shift.getY().isConstant()) { 239 int mask = shift.getShiftAmountMask(); 240 int amount = shift.getY().asJavaConstant().asInt() & mask; 241 if (shift.getX().getStackKind() == JavaKind.Int) { 242 return new IntegerTestNode(shift.getX(), ConstantNode.forInt(-1 << amount)); 243 } else { 244 assert shift.getX().getStackKind() == JavaKind.Long; 245 return new IntegerTestNode(shift.getX(), ConstantNode.forLong(-1L << amount)); 246 } 247 } 248 } 249 } 250 } 251 if (nonConstant instanceof AddNode) { 252 AddNode addNode = (AddNode) nonConstant; 253 if (addNode.getY().isJavaConstant()) { 254 return new IntegerEqualsNode(addNode.getX(), ConstantNode.forIntegerStamp(nonConstantStamp, primitiveConstant.asLong() - addNode.getY().asJavaConstant().asLong())); 255 } 256 } 257 if (nonConstant instanceof AndNode) { 258 /* 259 * a & c == c is the same as a & c != 0, if c is a single bit. 260 */ 261 AndNode andNode = (AndNode) nonConstant; 262 if (Long.bitCount(((PrimitiveConstant) constant).asLong()) == 1 && andNode.getY().isConstant() && andNode.getY().asJavaConstant().equals(constant)) { 263 return new LogicNegationNode(new IntegerTestNode(andNode.getX(), andNode.getY())); 264 } 265 } 266 267 if (nonConstant instanceof XorNode && nonConstant.stamp(view) instanceof IntegerStamp) { 268 XorNode xorNode = (XorNode) nonConstant; 269 if (xorNode.getY().isJavaConstant() && xorNode.getY().asJavaConstant().asLong() == 1 && ((IntegerStamp) xorNode.getX().stamp(view)).upMask() == 1) { 270 // x ^ 1 == 0 is the same as x == 1 if x in [0, 1] 271 // x ^ 1 == 1 is the same as x == 0 if x in [0, 1] 272 return new IntegerEqualsNode(xorNode.getX(), ConstantNode.forIntegerStamp(xorNode.getX().stamp(view), primitiveConstant.asLong() ^ 1)); 273 } 274 } 275 } 276 return super.canonicalizeSymmetricConstant(constantReflection, metaAccess, options, smallestCompareWidth, condition, constant, nonConstant, mirrored, unorderedIsTrue, view); 277 } 278 } 279 280 @Override 281 public Stamp getSucceedingStampForX(boolean negated, Stamp xStamp, Stamp yStamp) { 282 if (!negated) { 283 return xStamp.join(yStamp); 284 } 285 return null; 286 } 287 288 @Override 289 public Stamp getSucceedingStampForY(boolean negated, Stamp xStamp, Stamp yStamp) { 290 if (!negated) { 291 return xStamp.join(yStamp); 292 } 293 return null; 294 } 295 296 @Override 297 public TriState tryFold(Stamp xStampGeneric, Stamp yStampGeneric) { 298 if (xStampGeneric instanceof IntegerStamp && yStampGeneric instanceof IntegerStamp) { 299 IntegerStamp xStamp = (IntegerStamp) xStampGeneric; 300 IntegerStamp yStamp = (IntegerStamp) yStampGeneric; 301 if (xStamp.alwaysDistinct(yStamp)) { 302 return TriState.FALSE; 303 } else if (xStamp.neverDistinct(yStamp)) { 304 return TriState.TRUE; 305 } 306 } 307 return TriState.UNKNOWN; 308 } 309 }