1 /* 2 * Copyright (c) 2017, 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 static jdk.vm.ci.code.CodeUtil.mask; 28 29 import org.graalvm.compiler.core.common.calc.CanonicalCondition; 30 import org.graalvm.compiler.core.common.type.IntegerStamp; 31 import org.graalvm.compiler.core.common.type.Stamp; 32 import org.graalvm.compiler.graph.NodeClass; 33 import org.graalvm.compiler.nodeinfo.NodeInfo; 34 import org.graalvm.compiler.nodes.ConstantNode; 35 import org.graalvm.compiler.nodes.LogicConstantNode; 36 import org.graalvm.compiler.nodes.LogicNegationNode; 37 import org.graalvm.compiler.nodes.LogicNode; 38 import org.graalvm.compiler.nodes.NodeView; 39 import org.graalvm.compiler.nodes.ValueNode; 40 import org.graalvm.compiler.nodes.util.GraphUtil; 41 import org.graalvm.compiler.options.OptionValues; 42 43 import jdk.vm.ci.code.CodeUtil; 44 import jdk.vm.ci.meta.ConstantReflectionProvider; 45 import jdk.vm.ci.meta.JavaConstant; 46 import jdk.vm.ci.meta.MetaAccessProvider; 47 import jdk.vm.ci.meta.TriState; 48 49 /** 50 * Common super-class for "a < b" comparisons both {@linkplain IntegerLowerThanNode signed} and 51 * {@linkplain IntegerBelowNode unsigned}. 52 */ 53 @NodeInfo() 54 public abstract class IntegerLowerThanNode extends CompareNode { 55 public static final NodeClass<IntegerLowerThanNode> TYPE = NodeClass.create(IntegerLowerThanNode.class); 56 private final LowerOp op; 57 58 protected IntegerLowerThanNode(NodeClass<? extends CompareNode> c, ValueNode x, ValueNode y, LowerOp op) { 59 super(c, op.getCondition(), false, x, y); 60 this.op = op; 61 } 62 63 protected LowerOp getOp() { 64 return op; 65 } 66 67 @Override 68 public Stamp getSucceedingStampForX(boolean negated, Stamp xStampGeneric, Stamp yStampGeneric) { 69 return getSucceedingStampForX(negated, !negated, xStampGeneric, yStampGeneric, getX(), getY()); 70 } 71 72 @Override 73 public Stamp getSucceedingStampForY(boolean negated, Stamp xStampGeneric, Stamp yStampGeneric) { 74 return getSucceedingStampForX(!negated, !negated, yStampGeneric, xStampGeneric, getY(), getX()); 75 } 76 77 private Stamp getSucceedingStampForX(boolean mirror, boolean strict, Stamp xStampGeneric, Stamp yStampGeneric, ValueNode forX, ValueNode forY) { 78 Stamp s = getSucceedingStampForX(mirror, strict, xStampGeneric, yStampGeneric); 79 if (s != null && s.isUnrestricted()) { 80 s = null; 81 } 82 if (forY instanceof AddNode && xStampGeneric instanceof IntegerStamp) { 83 IntegerStamp xStamp = (IntegerStamp) xStampGeneric; 84 AddNode addNode = (AddNode) forY; 85 IntegerStamp aStamp = null; 86 if (addNode.getX() == forX && addNode.getY().stamp(NodeView.DEFAULT) instanceof IntegerStamp) { 87 // x < x + a 88 aStamp = (IntegerStamp) addNode.getY().stamp(NodeView.DEFAULT); 89 } else if (addNode.getY() == forX && addNode.getX().stamp(NodeView.DEFAULT) instanceof IntegerStamp) { 90 // x < a + x 91 aStamp = (IntegerStamp) addNode.getX().stamp(NodeView.DEFAULT); 92 } 93 if (aStamp != null) { 94 IntegerStamp result = getOp().getSucceedingStampForXLowerXPlusA(mirror, strict, aStamp, xStamp); 95 result = (IntegerStamp) xStamp.tryImproveWith(result); 96 if (result != null) { 97 if (s != null) { 98 s = s.improveWith(result); 99 } else { 100 s = result; 101 } 102 } 103 } 104 } 105 return s; 106 } 107 108 private Stamp getSucceedingStampForX(boolean mirror, boolean strict, Stamp xStampGeneric, Stamp yStampGeneric) { 109 if (xStampGeneric instanceof IntegerStamp) { 110 IntegerStamp xStamp = (IntegerStamp) xStampGeneric; 111 if (yStampGeneric instanceof IntegerStamp) { 112 IntegerStamp yStamp = (IntegerStamp) yStampGeneric; 113 assert yStamp.getBits() == xStamp.getBits(); 114 Stamp s = getOp().getSucceedingStampForX(xStamp, yStamp, mirror, strict); 115 if (s != null) { 116 return s; 117 } 118 } 119 } 120 return null; 121 } 122 123 @Override 124 public TriState tryFold(Stamp xStampGeneric, Stamp yStampGeneric) { 125 return getOp().tryFold(xStampGeneric, yStampGeneric); 126 } 127 128 public abstract static class LowerOp extends CompareOp { 129 @Override 130 public LogicNode canonical(ConstantReflectionProvider constantReflection, MetaAccessProvider metaAccess, OptionValues options, Integer smallestCompareWidth, CanonicalCondition condition, 131 boolean unorderedIsTrue, ValueNode forX, ValueNode forY, NodeView view) { 132 LogicNode result = super.canonical(constantReflection, metaAccess, options, smallestCompareWidth, condition, unorderedIsTrue, forX, forY, view); 133 if (result != null) { 134 return result; 135 } 136 LogicNode synonym = findSynonym(forX, forY, view); 137 if (synonym != null) { 138 return synonym; 139 } 140 return null; 141 } 142 143 protected abstract long upperBound(IntegerStamp stamp); 144 145 protected abstract long lowerBound(IntegerStamp stamp); 146 147 protected abstract int compare(long a, long b); 148 149 protected abstract long min(long a, long b); 150 151 protected abstract long max(long a, long b); 152 153 protected long min(long a, long b, int bits) { 154 return min(cast(a, bits), cast(b, bits)); 155 } 156 157 protected long max(long a, long b, int bits) { 158 return max(cast(a, bits), cast(b, bits)); 159 } 160 161 protected abstract long cast(long a, int bits); 162 163 protected abstract long minValue(int bits); 164 165 protected abstract long maxValue(int bits); 166 167 protected abstract IntegerStamp forInteger(int bits, long min, long max); 168 169 protected abstract CanonicalCondition getCondition(); 170 171 protected abstract IntegerLowerThanNode createNode(ValueNode x, ValueNode y); 172 173 public LogicNode create(ValueNode x, ValueNode y, NodeView view) { 174 LogicNode result = CompareNode.tryConstantFoldPrimitive(getCondition(), x, y, false, view); 175 if (result != null) { 176 return result; 177 } else { 178 result = findSynonym(x, y, view); 179 if (result != null) { 180 return result; 181 } 182 return createNode(x, y); 183 } 184 } 185 186 protected LogicNode findSynonym(ValueNode forX, ValueNode forY, NodeView view) { 187 if (GraphUtil.unproxify(forX) == GraphUtil.unproxify(forY)) { 188 return LogicConstantNode.contradiction(); 189 } 190 Stamp xStampGeneric = forX.stamp(view); 191 TriState fold = tryFold(xStampGeneric, forY.stamp(view)); 192 if (fold.isTrue()) { 193 return LogicConstantNode.tautology(); 194 } else if (fold.isFalse()) { 195 return LogicConstantNode.contradiction(); 196 } 197 if (forY.stamp(view) instanceof IntegerStamp) { 198 IntegerStamp yStamp = (IntegerStamp) forY.stamp(view); 199 IntegerStamp xStamp = (IntegerStamp) xStampGeneric; 200 int bits = yStamp.getBits(); 201 if (forX.isJavaConstant() && !forY.isConstant()) { 202 // bring the constant on the right 203 long xValue = forX.asJavaConstant().asLong(); 204 if (xValue != maxValue(bits)) { 205 // c < x <=> !(c >= x) <=> !(x <= c) <=> !(x < c + 1) 206 return LogicNegationNode.create(create(forY, ConstantNode.forIntegerStamp(yStamp, xValue + 1), view)); 207 } 208 } 209 if (forY.isJavaConstant()) { 210 long yValue = forY.asJavaConstant().asLong(); 211 212 // x < MAX <=> x != MAX 213 if (yValue == maxValue(bits)) { 214 return LogicNegationNode.create(IntegerEqualsNode.create(forX, forY, view)); 215 } 216 217 // x < MIN + 1 <=> x <= MIN <=> x == MIN 218 if (yValue == minValue(bits) + 1) { 219 return IntegerEqualsNode.create(forX, ConstantNode.forIntegerStamp(yStamp, minValue(bits)), view); 220 } 221 222 // (x < c && x >= c - 1) => x == c - 1 223 // If the constant is negative, only signed comparison is allowed. 224 if (yValue != minValue(bits) && xStamp.lowerBound() == yValue - 1 && (yValue > 0 || getCondition() == CanonicalCondition.LT)) { 225 return IntegerEqualsNode.create(forX, ConstantNode.forIntegerStamp(yStamp, yValue - 1), view); 226 } 227 228 } else if (forY instanceof AddNode) { 229 AddNode addNode = (AddNode) forY; 230 LogicNode canonical = canonicalizeXLowerXPlusA(forX, addNode, false, true, view); 231 if (canonical != null) { 232 return canonical; 233 } 234 } 235 if (forX instanceof AddNode) { 236 AddNode addNode = (AddNode) forX; 237 LogicNode canonical = canonicalizeXLowerXPlusA(forY, addNode, true, false, view); 238 if (canonical != null) { 239 return canonical; 240 } 241 } 242 } 243 return null; 244 } 245 246 /** 247 * Exploit the fact that adding the (signed) MIN_VALUE on both side flips signed and 248 * unsigned comparison. 249 * 250 * In particular: 251 * <ul> 252 * <li>{@code x + MIN_VALUE < y + MIN_VALUE <=> x |<| y}</li> 253 * <li>{@code x + MIN_VALUE |<| y + MIN_VALUE <=> x < y}</li> 254 * </ul> 255 */ 256 protected static LogicNode canonicalizeRangeFlip(ValueNode forX, ValueNode forY, int bits, boolean signed, NodeView view) { 257 long min = CodeUtil.minValue(bits); 258 long xResidue = 0; 259 ValueNode left = null; 260 JavaConstant leftCst = null; 261 if (forX instanceof AddNode) { 262 AddNode xAdd = (AddNode) forX; 263 if (xAdd.getY().isJavaConstant() && !xAdd.getY().asJavaConstant().isDefaultForKind()) { 264 long xCst = xAdd.getY().asJavaConstant().asLong(); 265 xResidue = xCst - min; 266 left = xAdd.getX(); 267 } 268 } else if (forX.isJavaConstant()) { 269 leftCst = forX.asJavaConstant(); 270 } 271 if (left == null && leftCst == null) { 272 return null; 273 } 274 long yResidue = 0; 275 ValueNode right = null; 276 JavaConstant rightCst = null; 277 if (forY instanceof AddNode) { 278 AddNode yAdd = (AddNode) forY; 279 if (yAdd.getY().isJavaConstant() && !yAdd.getY().asJavaConstant().isDefaultForKind()) { 280 long yCst = yAdd.getY().asJavaConstant().asLong(); 281 yResidue = yCst - min; 282 right = yAdd.getX(); 283 } 284 } else if (forY.isJavaConstant()) { 285 rightCst = forY.asJavaConstant(); 286 } 287 if (right == null && rightCst == null) { 288 return null; 289 } 290 if ((xResidue == 0 && left != null) || (yResidue == 0 && right != null)) { 291 if (left == null) { 292 left = ConstantNode.forIntegerBits(bits, leftCst.asLong() - min); 293 } else if (xResidue != 0) { 294 left = AddNode.create(left, ConstantNode.forIntegerBits(bits, xResidue), view); 295 } 296 if (right == null) { 297 right = ConstantNode.forIntegerBits(bits, rightCst.asLong() - min); 298 } else if (yResidue != 0) { 299 right = AddNode.create(right, ConstantNode.forIntegerBits(bits, yResidue), view); 300 } 301 if (signed) { 302 return new IntegerBelowNode(left, right); 303 } else { 304 return new IntegerLessThanNode(left, right); 305 } 306 } 307 return null; 308 } 309 310 private LogicNode canonicalizeXLowerXPlusA(ValueNode forX, AddNode addNode, boolean mirrored, boolean strict, NodeView view) { 311 // x < x + a 312 // x |<| x + a 313 IntegerStamp xStamp = (IntegerStamp) forX.stamp(view); 314 IntegerStamp succeedingXStamp; 315 boolean exact; 316 if (addNode.getX() == forX && addNode.getY().stamp(view) instanceof IntegerStamp) { 317 IntegerStamp aStamp = (IntegerStamp) addNode.getY().stamp(view); 318 succeedingXStamp = getSucceedingStampForXLowerXPlusA(mirrored, strict, aStamp, xStamp); 319 exact = aStamp.lowerBound() == aStamp.upperBound(); 320 } else if (addNode.getY() == forX && addNode.getX().stamp(view) instanceof IntegerStamp) { 321 IntegerStamp aStamp = (IntegerStamp) addNode.getX().stamp(view); 322 succeedingXStamp = getSucceedingStampForXLowerXPlusA(mirrored, strict, aStamp, xStamp); 323 exact = aStamp.lowerBound() == aStamp.upperBound(); 324 } else { 325 return null; 326 } 327 if (succeedingXStamp.join(forX.stamp(view)).isEmpty()) { 328 return LogicConstantNode.contradiction(); 329 } else if (exact && !succeedingXStamp.isEmpty()) { 330 int bits = succeedingXStamp.getBits(); 331 if (compare(lowerBound(succeedingXStamp), minValue(bits)) > 0) { 332 // x must be in [L..MAX] <=> x >= L <=> !(x < L) 333 return LogicNegationNode.create(create(forX, ConstantNode.forIntegerStamp(succeedingXStamp, lowerBound(succeedingXStamp)), view)); 334 } else if (compare(upperBound(succeedingXStamp), maxValue(bits)) < 0) { 335 // x must be in [MIN..H] <=> x <= H <=> !(H < x) 336 return LogicNegationNode.create(create(ConstantNode.forIntegerStamp(succeedingXStamp, upperBound(succeedingXStamp)), forX, view)); 337 } 338 } 339 return null; 340 } 341 342 protected TriState tryFold(Stamp xStampGeneric, Stamp yStampGeneric) { 343 if (xStampGeneric instanceof IntegerStamp && yStampGeneric instanceof IntegerStamp) { 344 IntegerStamp xStamp = (IntegerStamp) xStampGeneric; 345 IntegerStamp yStamp = (IntegerStamp) yStampGeneric; 346 if (compare(upperBound(xStamp), lowerBound(yStamp)) < 0) { 347 return TriState.TRUE; 348 } 349 if (compare(lowerBound(xStamp), upperBound(yStamp)) >= 0) { 350 return TriState.FALSE; 351 } 352 } 353 return TriState.UNKNOWN; 354 } 355 356 protected IntegerStamp getSucceedingStampForX(IntegerStamp xStamp, IntegerStamp yStamp, boolean mirror, boolean strict) { 357 int bits = xStamp.getBits(); 358 assert yStamp.getBits() == bits; 359 if (mirror) { 360 long low = lowerBound(yStamp); 361 if (strict) { 362 if (low == maxValue(bits)) { 363 return null; 364 } 365 low += 1; 366 } 367 if (compare(low, lowerBound(xStamp)) > 0 || upperBound(xStamp) != (xStamp.upperBound() & mask(xStamp.getBits()))) { 368 return forInteger(bits, low, upperBound(xStamp)); 369 } 370 } else { 371 // x < y, i.e., x < y <= Y_UPPER_BOUND so x <= Y_UPPER_BOUND - 1 372 long low = upperBound(yStamp); 373 if (strict) { 374 if (low == minValue(bits)) { 375 return null; 376 } 377 low -= 1; 378 } 379 if (compare(low, upperBound(xStamp)) < 0 || lowerBound(xStamp) != (xStamp.lowerBound() & mask(xStamp.getBits()))) { 380 return forInteger(bits, lowerBound(xStamp), low); 381 } 382 } 383 return null; 384 } 385 386 protected IntegerStamp getSucceedingStampForXLowerXPlusA(boolean mirrored, boolean strict, IntegerStamp aStamp, IntegerStamp xStamp) { 387 int bits = aStamp.getBits(); 388 long min = minValue(bits); 389 long max = maxValue(bits); 390 391 /* 392 * if x < x + a <=> x + a didn't overflow: 393 * 394 * x is outside ]MAX - a, MAX], i.e., inside [MIN, MAX - a] 395 * 396 * if a is negative those bounds wrap around correctly. 397 * 398 * If a is exactly zero this gives an unbounded stamp (any integer) in the positive case 399 * and an empty stamp in the negative case: if x |<| x is true, then either x has no 400 * value or any value... 401 * 402 * This does not use upper/lowerBound from LowerOp because it's about the (signed) 403 * addition not the comparison. 404 */ 405 if (mirrored) { 406 if (aStamp.contains(0)) { 407 // a may be zero 408 return aStamp.unrestricted(); 409 } 410 return forInteger(bits, min(max - aStamp.lowerBound() + 1, max - aStamp.upperBound() + 1, bits), min(max, upperBound(xStamp))); 411 } else { 412 long aLower = aStamp.lowerBound(); 413 long aUpper = aStamp.upperBound(); 414 if (strict) { 415 if (aLower == 0) { 416 aLower = 1; 417 } 418 if (aUpper == 0) { 419 aUpper = -1; 420 } 421 if (aLower > aUpper) { 422 // impossible 423 return aStamp.empty(); 424 } 425 } 426 if (aLower < 0 && aUpper > 0) { 427 // a may be zero 428 return aStamp.unrestricted(); 429 } 430 return forInteger(bits, min, max(max - aLower, max - aUpper, bits)); 431 } 432 } 433 } 434 }