1 /* 2 * Copyright (c) 2012, 2019, 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.core.common.type; 26 27 import static org.graalvm.compiler.core.common.calc.FloatConvert.I2D; 28 import static org.graalvm.compiler.core.common.calc.FloatConvert.I2F; 29 import static org.graalvm.compiler.core.common.calc.FloatConvert.L2D; 30 import static org.graalvm.compiler.core.common.calc.FloatConvert.L2F; 31 32 import java.nio.ByteBuffer; 33 import java.util.Formatter; 34 35 import org.graalvm.compiler.core.common.LIRKind; 36 import org.graalvm.compiler.core.common.NumUtil; 37 import org.graalvm.compiler.core.common.spi.LIRKindTool; 38 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp; 39 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.FloatConvertOp; 40 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.IntegerConvertOp; 41 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.ShiftOp; 42 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.UnaryOp; 43 import org.graalvm.compiler.debug.GraalError; 44 45 import jdk.vm.ci.code.CodeUtil; 46 import jdk.vm.ci.meta.Constant; 47 import jdk.vm.ci.meta.JavaConstant; 48 import jdk.vm.ci.meta.JavaKind; 49 import jdk.vm.ci.meta.MetaAccessProvider; 50 import jdk.vm.ci.meta.PrimitiveConstant; 51 import jdk.vm.ci.meta.ResolvedJavaType; 52 import jdk.vm.ci.meta.SerializableConstant; 53 54 /** 55 * Describes the possible values of a node that produces an int or long result. 56 * 57 * The description consists of (inclusive) lower and upper bounds and up (may be set) and down 58 * (always set) bit-masks. 59 */ 60 public final class IntegerStamp extends PrimitiveStamp { 61 62 private final long lowerBound; 63 private final long upperBound; 64 private final long downMask; 65 private final long upMask; 66 IntegerStamp(int bits, long lowerBound, long upperBound, long downMask, long upMask)67 private IntegerStamp(int bits, long lowerBound, long upperBound, long downMask, long upMask) { 68 super(bits, OPS); 69 70 this.lowerBound = lowerBound; 71 this.upperBound = upperBound; 72 this.downMask = downMask; 73 this.upMask = upMask; 74 75 assert lowerBound >= CodeUtil.minValue(bits) : this; 76 assert upperBound <= CodeUtil.maxValue(bits) : this; 77 assert (downMask & CodeUtil.mask(bits)) == downMask : this; 78 assert (upMask & CodeUtil.mask(bits)) == upMask : this; 79 } 80 create(int bits, long lowerBoundInput, long upperBoundInput)81 public static IntegerStamp create(int bits, long lowerBoundInput, long upperBoundInput) { 82 return create(bits, lowerBoundInput, upperBoundInput, 0, CodeUtil.mask(bits)); 83 } 84 create(int bits, long lowerBoundInput, long upperBoundInput, long downMask, long upMask)85 public static IntegerStamp create(int bits, long lowerBoundInput, long upperBoundInput, long downMask, long upMask) { 86 assert (downMask & ~upMask) == 0 : String.format("\u21ca: %016x \u21c8: %016x", downMask, upMask); 87 88 // Set lower bound, use masks to make it more precise 89 long minValue = minValueForMasks(bits, downMask, upMask); 90 long lowerBoundTmp = Math.max(lowerBoundInput, minValue); 91 92 // Set upper bound, use masks to make it more precise 93 long maxValue = maxValueForMasks(bits, downMask, upMask); 94 long upperBoundTmp = Math.min(upperBoundInput, maxValue); 95 96 // Assign masks now with the bounds in mind. 97 final long boundedDownMask; 98 final long boundedUpMask; 99 long defaultMask = CodeUtil.mask(bits); 100 if (lowerBoundTmp == upperBoundTmp) { 101 boundedDownMask = lowerBoundTmp; 102 boundedUpMask = lowerBoundTmp; 103 } else if (lowerBoundTmp >= 0) { 104 int upperBoundLeadingZeros = Long.numberOfLeadingZeros(upperBoundTmp); 105 long differentBits = lowerBoundTmp ^ upperBoundTmp; 106 int sameBitCount = Long.numberOfLeadingZeros(differentBits << upperBoundLeadingZeros); 107 108 boundedUpMask = upperBoundTmp | -1L >>> (upperBoundLeadingZeros + sameBitCount); 109 boundedDownMask = upperBoundTmp & ~(-1L >>> (upperBoundLeadingZeros + sameBitCount)); 110 } else { 111 if (upperBoundTmp >= 0) { 112 boundedUpMask = defaultMask; 113 boundedDownMask = 0; 114 } else { 115 int lowerBoundLeadingOnes = Long.numberOfLeadingZeros(~lowerBoundTmp); 116 long differentBits = lowerBoundTmp ^ upperBoundTmp; 117 int sameBitCount = Long.numberOfLeadingZeros(differentBits << lowerBoundLeadingOnes); 118 119 boundedUpMask = lowerBoundTmp | -1L >>> (lowerBoundLeadingOnes + sameBitCount) | ~(-1L >>> lowerBoundLeadingOnes); 120 boundedDownMask = lowerBoundTmp & ~(-1L >>> (lowerBoundLeadingOnes + sameBitCount)) | ~(-1L >>> lowerBoundLeadingOnes); 121 } 122 } 123 124 return new IntegerStamp(bits, lowerBoundTmp, upperBoundTmp, defaultMask & (downMask | boundedDownMask), defaultMask & upMask & boundedUpMask); 125 } 126 significantBit(long bits, long value)127 private static long significantBit(long bits, long value) { 128 return (value >>> (bits - 1)) & 1; 129 } 130 minValueForMasks(int bits, long downMask, long upMask)131 private static long minValueForMasks(int bits, long downMask, long upMask) { 132 if (significantBit(bits, upMask) == 0) { 133 // Value is always positive. Minimum value always positive. 134 assert significantBit(bits, downMask) == 0; 135 return downMask; 136 } else { 137 // Value can be positive or negative. Minimum value always negative. 138 return downMask | (-1L << (bits - 1)); 139 } 140 } 141 maxValueForMasks(int bits, long downMask, long upMask)142 private static long maxValueForMasks(int bits, long downMask, long upMask) { 143 if (significantBit(bits, downMask) == 1) { 144 // Value is always negative. Maximum value always negative. 145 assert significantBit(bits, upMask) == 1; 146 return CodeUtil.signExtend(upMask, bits); 147 } else { 148 // Value can be positive or negative. Maximum value always positive. 149 return upMask & (CodeUtil.mask(bits) >>> 1); 150 } 151 } 152 stampForMask(int bits, long downMask, long upMask)153 public static IntegerStamp stampForMask(int bits, long downMask, long upMask) { 154 return new IntegerStamp(bits, minValueForMasks(bits, downMask, upMask), maxValueForMasks(bits, downMask, upMask), downMask, upMask); 155 } 156 157 @Override unrestricted()158 public IntegerStamp unrestricted() { 159 return new IntegerStamp(getBits(), CodeUtil.minValue(getBits()), CodeUtil.maxValue(getBits()), 0, CodeUtil.mask(getBits())); 160 } 161 162 @Override empty()163 public IntegerStamp empty() { 164 return new IntegerStamp(getBits(), CodeUtil.maxValue(getBits()), CodeUtil.minValue(getBits()), CodeUtil.mask(getBits()), 0); 165 } 166 167 @Override constant(Constant c, MetaAccessProvider meta)168 public Stamp constant(Constant c, MetaAccessProvider meta) { 169 if (c instanceof PrimitiveConstant) { 170 PrimitiveConstant primitiveConstant = (PrimitiveConstant) c; 171 long value = primitiveConstant.asLong(); 172 if (primitiveConstant.getJavaKind() == JavaKind.Boolean && value == 1) { 173 // Need to special case booleans as integer stamps are always signed values. 174 value = -1; 175 } 176 Stamp returnedStamp = StampFactory.forInteger(getBits(), value, value); 177 assert returnedStamp.hasValues(); 178 return returnedStamp; 179 } 180 return this; 181 } 182 183 @Override deserialize(ByteBuffer buffer)184 public SerializableConstant deserialize(ByteBuffer buffer) { 185 switch (getBits()) { 186 case 1: 187 return JavaConstant.forBoolean(buffer.get() != 0); 188 case 8: 189 return JavaConstant.forByte(buffer.get()); 190 case 16: 191 return JavaConstant.forShort(buffer.getShort()); 192 case 32: 193 return JavaConstant.forInt(buffer.getInt()); 194 case 64: 195 return JavaConstant.forLong(buffer.getLong()); 196 default: 197 throw GraalError.shouldNotReachHere(); 198 } 199 } 200 201 @Override hasValues()202 public boolean hasValues() { 203 return lowerBound <= upperBound; 204 } 205 206 @Override getStackKind()207 public JavaKind getStackKind() { 208 if (getBits() > 32) { 209 return JavaKind.Long; 210 } else { 211 return JavaKind.Int; 212 } 213 } 214 215 @Override getLIRKind(LIRKindTool tool)216 public LIRKind getLIRKind(LIRKindTool tool) { 217 return tool.getIntegerKind(getBits()); 218 } 219 220 @Override javaType(MetaAccessProvider metaAccess)221 public ResolvedJavaType javaType(MetaAccessProvider metaAccess) { 222 switch (getBits()) { 223 case 1: 224 return metaAccess.lookupJavaType(Boolean.TYPE); 225 case 8: 226 return metaAccess.lookupJavaType(Byte.TYPE); 227 case 16: 228 return metaAccess.lookupJavaType(Short.TYPE); 229 case 32: 230 return metaAccess.lookupJavaType(Integer.TYPE); 231 case 64: 232 return metaAccess.lookupJavaType(Long.TYPE); 233 default: 234 throw GraalError.shouldNotReachHere(); 235 } 236 } 237 238 /** 239 * The signed inclusive lower bound on the value described by this stamp. 240 */ lowerBound()241 public long lowerBound() { 242 return lowerBound; 243 } 244 245 /** 246 * The signed inclusive upper bound on the value described by this stamp. 247 */ upperBound()248 public long upperBound() { 249 return upperBound; 250 } 251 252 /** 253 * This bit-mask describes the bits that are always set in the value described by this stamp. 254 */ downMask()255 public long downMask() { 256 return downMask; 257 } 258 259 /** 260 * This bit-mask describes the bits that can be set in the value described by this stamp. 261 */ upMask()262 public long upMask() { 263 return upMask; 264 } 265 266 @Override isUnrestricted()267 public boolean isUnrestricted() { 268 return lowerBound == CodeUtil.minValue(getBits()) && upperBound == CodeUtil.maxValue(getBits()) && downMask == 0 && upMask == CodeUtil.mask(getBits()); 269 } 270 contains(long value)271 public boolean contains(long value) { 272 return value >= lowerBound && value <= upperBound && (value & downMask) == downMask && (value & upMask) == (value & CodeUtil.mask(getBits())); 273 } 274 isPositive()275 public boolean isPositive() { 276 return lowerBound() >= 0; 277 } 278 isNegative()279 public boolean isNegative() { 280 return upperBound() <= 0; 281 } 282 isStrictlyPositive()283 public boolean isStrictlyPositive() { 284 return lowerBound() > 0; 285 } 286 isStrictlyNegative()287 public boolean isStrictlyNegative() { 288 return upperBound() < 0; 289 } 290 canBePositive()291 public boolean canBePositive() { 292 return upperBound() > 0; 293 } 294 canBeNegative()295 public boolean canBeNegative() { 296 return lowerBound() < 0; 297 } 298 299 @Override toString()300 public String toString() { 301 StringBuilder str = new StringBuilder(); 302 str.append('i'); 303 str.append(getBits()); 304 if (hasValues()) { 305 if (lowerBound == upperBound) { 306 str.append(" [").append(lowerBound).append(']'); 307 } else if (lowerBound != CodeUtil.minValue(getBits()) || upperBound != CodeUtil.maxValue(getBits())) { 308 str.append(" [").append(lowerBound).append(" - ").append(upperBound).append(']'); 309 } 310 if (downMask != 0) { 311 str.append(" \u21ca"); 312 new Formatter(str).format("%016x", downMask); 313 } 314 if (upMask != CodeUtil.mask(getBits())) { 315 str.append(" \u21c8"); 316 new Formatter(str).format("%016x", upMask); 317 } 318 } else { 319 str.append("<empty>"); 320 } 321 return str.toString(); 322 } 323 createStamp(IntegerStamp other, long newUpperBound, long newLowerBound, long newDownMask, long newUpMask)324 private IntegerStamp createStamp(IntegerStamp other, long newUpperBound, long newLowerBound, long newDownMask, long newUpMask) { 325 assert getBits() == other.getBits(); 326 if (newLowerBound > newUpperBound || (newDownMask & (~newUpMask)) != 0 || (newUpMask == 0 && (newLowerBound > 0 || newUpperBound < 0))) { 327 return empty(); 328 } else if (newLowerBound == lowerBound && newUpperBound == upperBound && newDownMask == downMask && newUpMask == upMask) { 329 return this; 330 } else if (newLowerBound == other.lowerBound && newUpperBound == other.upperBound && newDownMask == other.downMask && newUpMask == other.upMask) { 331 return other; 332 } else { 333 return IntegerStamp.create(getBits(), newLowerBound, newUpperBound, newDownMask, newUpMask); 334 } 335 } 336 337 @Override meet(Stamp otherStamp)338 public Stamp meet(Stamp otherStamp) { 339 if (otherStamp == this) { 340 return this; 341 } 342 if (isEmpty()) { 343 return otherStamp; 344 } 345 if (otherStamp.isEmpty()) { 346 return this; 347 } 348 IntegerStamp other = (IntegerStamp) otherStamp; 349 return createStamp(other, Math.max(upperBound, other.upperBound), Math.min(lowerBound, other.lowerBound), downMask & other.downMask, upMask | other.upMask); 350 } 351 352 @Override join(Stamp otherStamp)353 public IntegerStamp join(Stamp otherStamp) { 354 if (otherStamp == this) { 355 return this; 356 } 357 IntegerStamp other = (IntegerStamp) otherStamp; 358 long newDownMask = downMask | other.downMask; 359 long newLowerBound = Math.max(lowerBound, other.lowerBound); 360 long newUpperBound = Math.min(upperBound, other.upperBound); 361 long newUpMask = upMask & other.upMask; 362 return createStamp(other, newUpperBound, newLowerBound, newDownMask, newUpMask); 363 } 364 365 @Override isCompatible(Stamp stamp)366 public boolean isCompatible(Stamp stamp) { 367 if (this == stamp) { 368 return true; 369 } 370 if (stamp instanceof IntegerStamp) { 371 IntegerStamp other = (IntegerStamp) stamp; 372 return getBits() == other.getBits(); 373 } 374 return false; 375 } 376 377 @Override isCompatible(Constant constant)378 public boolean isCompatible(Constant constant) { 379 if (constant instanceof PrimitiveConstant) { 380 PrimitiveConstant prim = (PrimitiveConstant) constant; 381 return prim.getJavaKind().isNumericInteger(); 382 } 383 return false; 384 } 385 unsignedUpperBound()386 public long unsignedUpperBound() { 387 if (sameSignBounds()) { 388 return CodeUtil.zeroExtend(upperBound(), getBits()); 389 } 390 return NumUtil.maxValueUnsigned(getBits()); 391 } 392 unsignedLowerBound()393 public long unsignedLowerBound() { 394 if (sameSignBounds()) { 395 return CodeUtil.zeroExtend(lowerBound(), getBits()); 396 } 397 return 0; 398 } 399 sameSignBounds()400 private boolean sameSignBounds() { 401 return NumUtil.sameSign(lowerBound, upperBound); 402 } 403 404 @Override hashCode()405 public int hashCode() { 406 final int prime = 31; 407 int result = 1; 408 result = prime * result + super.hashCode(); 409 result = prime * result + (int) (lowerBound ^ (lowerBound >>> 32)); 410 result = prime * result + (int) (upperBound ^ (upperBound >>> 32)); 411 result = prime * result + (int) (downMask ^ (downMask >>> 32)); 412 result = prime * result + (int) (upMask ^ (upMask >>> 32)); 413 return result; 414 } 415 416 @Override equals(Object obj)417 public boolean equals(Object obj) { 418 if (this == obj) { 419 return true; 420 } 421 if (obj == null || getClass() != obj.getClass() || !super.equals(obj)) { 422 return false; 423 } 424 IntegerStamp other = (IntegerStamp) obj; 425 if (lowerBound != other.lowerBound || upperBound != other.upperBound || downMask != other.downMask || upMask != other.upMask) { 426 return false; 427 } 428 return super.equals(other); 429 } 430 upMaskFor(int bits, long lowerBound, long upperBound)431 private static long upMaskFor(int bits, long lowerBound, long upperBound) { 432 long mask = lowerBound | upperBound; 433 if (mask == 0) { 434 return 0; 435 } else { 436 return ((-1L) >>> Long.numberOfLeadingZeros(mask)) & CodeUtil.mask(bits); 437 } 438 } 439 440 /** 441 * Checks if the 2 stamps represent values of the same sign. Returns true if the two stamps are 442 * both positive of null or if they are both strictly negative 443 * 444 * @return true if the two stamps are both positive of null or if they are both strictly 445 * negative 446 */ sameSign(IntegerStamp s1, IntegerStamp s2)447 public static boolean sameSign(IntegerStamp s1, IntegerStamp s2) { 448 return s1.isPositive() && s2.isPositive() || s1.isStrictlyNegative() && s2.isStrictlyNegative(); 449 } 450 451 @Override asConstant()452 public JavaConstant asConstant() { 453 if (lowerBound == upperBound) { 454 switch (getBits()) { 455 case 1: 456 return JavaConstant.forBoolean(lowerBound != 0); 457 case 8: 458 return JavaConstant.forByte((byte) lowerBound); 459 case 16: 460 return JavaConstant.forShort((short) lowerBound); 461 case 32: 462 return JavaConstant.forInt((int) lowerBound); 463 case 64: 464 return JavaConstant.forLong(lowerBound); 465 } 466 } 467 return null; 468 } 469 addCanOverflow(IntegerStamp a, IntegerStamp b)470 public static boolean addCanOverflow(IntegerStamp a, IntegerStamp b) { 471 assert a.getBits() == b.getBits(); 472 return addOverflowsPositively(a.upperBound(), b.upperBound(), a.getBits()) || 473 addOverflowsNegatively(a.lowerBound(), b.lowerBound(), a.getBits()); 474 475 } 476 addOverflowsPositively(long x, long y, int bits)477 public static boolean addOverflowsPositively(long x, long y, int bits) { 478 long result = x + y; 479 if (bits == 64) { 480 return (~x & ~y & result) < 0; 481 } else { 482 return result > CodeUtil.maxValue(bits); 483 } 484 } 485 addOverflowsNegatively(long x, long y, int bits)486 public static boolean addOverflowsNegatively(long x, long y, int bits) { 487 long result = x + y; 488 if (bits == 64) { 489 return (x & y & ~result) < 0; 490 } else { 491 return result < CodeUtil.minValue(bits); 492 } 493 } 494 carryBits(long x, long y)495 public static long carryBits(long x, long y) { 496 return (x + y) ^ x ^ y; 497 } 498 saturate(long v, int bits)499 private static long saturate(long v, int bits) { 500 if (bits < 64) { 501 long max = CodeUtil.maxValue(bits); 502 if (v > max) { 503 return max; 504 } 505 long min = CodeUtil.minValue(bits); 506 if (v < min) { 507 return min; 508 } 509 } 510 return v; 511 } 512 multiplicationOverflows(long a, long b, int bits)513 public static boolean multiplicationOverflows(long a, long b, int bits) { 514 assert bits <= 64 && bits >= 0; 515 long result = a * b; 516 // result is positive if the sign is the same 517 boolean positive = (a >= 0 && b >= 0) || (a < 0 && b < 0); 518 if (bits == 64) { 519 if (a > 0 && b > 0) { 520 return a > 0x7FFFFFFF_FFFFFFFFL / b; 521 } else if (a > 0 && b <= 0) { 522 return b < 0x80000000_00000000L / a; 523 } else if (a <= 0 && b > 0) { 524 return a < 0x80000000_00000000L / b; 525 } else { 526 // a<=0 && b <=0 527 return a != 0 && b < 0x7FFFFFFF_FFFFFFFFL / a; 528 } 529 } else { 530 if (positive) { 531 return result > CodeUtil.maxValue(bits); 532 } else { 533 return result < CodeUtil.minValue(bits); 534 } 535 } 536 } 537 multiplicationCanOverflow(IntegerStamp a, IntegerStamp b)538 public static boolean multiplicationCanOverflow(IntegerStamp a, IntegerStamp b) { 539 // see IntegerStamp#foldStamp for details 540 assert a.getBits() == b.getBits(); 541 if (a.upMask() == 0) { 542 return false; 543 } else if (b.upMask() == 0) { 544 return false; 545 } 546 if (a.isUnrestricted()) { 547 return true; 548 } 549 if (b.isUnrestricted()) { 550 return true; 551 } 552 int bits = a.getBits(); 553 long minNegA = a.lowerBound(); 554 long maxNegA = Math.min(0, a.upperBound()); 555 long minPosA = Math.max(0, a.lowerBound()); 556 long maxPosA = a.upperBound(); 557 558 long minNegB = b.lowerBound(); 559 long maxNegB = Math.min(0, b.upperBound()); 560 long minPosB = Math.max(0, b.lowerBound()); 561 long maxPosB = b.upperBound(); 562 563 boolean mayOverflow = false; 564 if (a.canBePositive()) { 565 if (b.canBePositive()) { 566 mayOverflow |= IntegerStamp.multiplicationOverflows(maxPosA, maxPosB, bits); 567 mayOverflow |= IntegerStamp.multiplicationOverflows(minPosA, minPosB, bits); 568 } 569 if (b.canBeNegative()) { 570 mayOverflow |= IntegerStamp.multiplicationOverflows(minPosA, maxNegB, bits); 571 mayOverflow |= IntegerStamp.multiplicationOverflows(maxPosA, minNegB, bits); 572 573 } 574 } 575 if (a.canBeNegative()) { 576 if (b.canBePositive()) { 577 mayOverflow |= IntegerStamp.multiplicationOverflows(maxNegA, minPosB, bits); 578 mayOverflow |= IntegerStamp.multiplicationOverflows(minNegA, maxPosB, bits); 579 } 580 if (b.canBeNegative()) { 581 mayOverflow |= IntegerStamp.multiplicationOverflows(minNegA, minNegB, bits); 582 mayOverflow |= IntegerStamp.multiplicationOverflows(maxNegA, maxNegB, bits); 583 } 584 } 585 return mayOverflow; 586 } 587 subtractionCanOverflow(IntegerStamp x, IntegerStamp y)588 public static boolean subtractionCanOverflow(IntegerStamp x, IntegerStamp y) { 589 assert x.getBits() == y.getBits(); 590 return subtractionOverflows(x.lowerBound(), y.upperBound(), x.getBits()) || subtractionOverflows(x.upperBound(), y.lowerBound(), x.getBits()); 591 } 592 subtractionOverflows(long x, long y, int bits)593 public static boolean subtractionOverflows(long x, long y, int bits) { 594 long result = x - y; 595 if (bits == 64) { 596 return (((x ^ y) & (x ^ result)) < 0); 597 } 598 return result < CodeUtil.minValue(bits) || result > CodeUtil.maxValue(bits); 599 } 600 601 public static final ArithmeticOpTable OPS = new ArithmeticOpTable( 602 603 new UnaryOp.Neg() { 604 605 @Override 606 public Constant foldConstant(Constant value) { 607 PrimitiveConstant c = (PrimitiveConstant) value; 608 return JavaConstant.forIntegerKind(c.getJavaKind(), -c.asLong()); 609 } 610 611 @Override 612 public Stamp foldStamp(Stamp s) { 613 if (s.isEmpty()) { 614 return s; 615 } 616 IntegerStamp stamp = (IntegerStamp) s; 617 int bits = stamp.getBits(); 618 if (stamp.lowerBound == stamp.upperBound) { 619 long value = CodeUtil.convert(-stamp.lowerBound(), stamp.getBits(), false); 620 return StampFactory.forInteger(stamp.getBits(), value, value); 621 } 622 if (stamp.lowerBound() != CodeUtil.minValue(bits)) { 623 // TODO(ls) check if the mask calculation is correct... 624 return StampFactory.forInteger(bits, -stamp.upperBound(), -stamp.lowerBound()); 625 } else { 626 return stamp.unrestricted(); 627 } 628 } 629 }, 630 631 new BinaryOp.Add(true, true) { 632 633 @Override 634 public Constant foldConstant(Constant const1, Constant const2) { 635 PrimitiveConstant a = (PrimitiveConstant) const1; 636 PrimitiveConstant b = (PrimitiveConstant) const2; 637 assert a.getJavaKind() == b.getJavaKind(); 638 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() + b.asLong()); 639 } 640 641 @Override 642 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) { 643 if (stamp1.isEmpty()) { 644 return stamp1; 645 } 646 if (stamp2.isEmpty()) { 647 return stamp2; 648 } 649 IntegerStamp a = (IntegerStamp) stamp1; 650 IntegerStamp b = (IntegerStamp) stamp2; 651 652 int bits = a.getBits(); 653 assert bits == b.getBits() : String.format("stamp1.bits=%d, stamp2.bits=%d", bits, b.getBits()); 654 655 if (a.lowerBound == a.upperBound && b.lowerBound == b.upperBound) { 656 long value = CodeUtil.convert(a.lowerBound() + b.lowerBound(), a.getBits(), false); 657 return StampFactory.forInteger(a.getBits(), value, value); 658 } 659 660 if (a.isUnrestricted()) { 661 return a; 662 } else if (b.isUnrestricted()) { 663 return b; 664 } 665 long defaultMask = CodeUtil.mask(bits); 666 long variableBits = (a.downMask() ^ a.upMask()) | (b.downMask() ^ b.upMask()); 667 long variableBitsWithCarry = variableBits | (carryBits(a.downMask(), b.downMask()) ^ carryBits(a.upMask(), b.upMask())); 668 long newDownMask = (a.downMask() + b.downMask()) & ~variableBitsWithCarry; 669 long newUpMask = (a.downMask() + b.downMask()) | variableBitsWithCarry; 670 671 newDownMask &= defaultMask; 672 newUpMask &= defaultMask; 673 674 long newLowerBound; 675 long newUpperBound; 676 boolean lowerOverflowsPositively = addOverflowsPositively(a.lowerBound(), b.lowerBound(), bits); 677 boolean upperOverflowsPositively = addOverflowsPositively(a.upperBound(), b.upperBound(), bits); 678 boolean lowerOverflowsNegatively = addOverflowsNegatively(a.lowerBound(), b.lowerBound(), bits); 679 boolean upperOverflowsNegatively = addOverflowsNegatively(a.upperBound(), b.upperBound(), bits); 680 if ((lowerOverflowsNegatively && !upperOverflowsNegatively) || (!lowerOverflowsPositively && upperOverflowsPositively)) { 681 newLowerBound = CodeUtil.minValue(bits); 682 newUpperBound = CodeUtil.maxValue(bits); 683 } else { 684 newLowerBound = CodeUtil.signExtend((a.lowerBound() + b.lowerBound()) & defaultMask, bits); 685 newUpperBound = CodeUtil.signExtend((a.upperBound() + b.upperBound()) & defaultMask, bits); 686 } 687 IntegerStamp limit = StampFactory.forInteger(bits, newLowerBound, newUpperBound); 688 newUpMask &= limit.upMask(); 689 newUpperBound = CodeUtil.signExtend(newUpperBound & newUpMask, bits); 690 newDownMask |= limit.downMask(); 691 newLowerBound |= newDownMask; 692 return new IntegerStamp(bits, newLowerBound, newUpperBound, newDownMask, newUpMask); 693 } 694 695 @Override 696 public boolean isNeutral(Constant value) { 697 PrimitiveConstant n = (PrimitiveConstant) value; 698 return n.asLong() == 0; 699 } 700 }, 701 702 new BinaryOp.Sub(true, false) { 703 704 @Override 705 public Constant foldConstant(Constant const1, Constant const2) { 706 PrimitiveConstant a = (PrimitiveConstant) const1; 707 PrimitiveConstant b = (PrimitiveConstant) const2; 708 assert a.getJavaKind() == b.getJavaKind(); 709 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() - b.asLong()); 710 } 711 712 @Override 713 public Stamp foldStamp(Stamp a, Stamp b) { 714 return OPS.getAdd().foldStamp(a, OPS.getNeg().foldStamp(b)); 715 } 716 717 @Override 718 public boolean isNeutral(Constant value) { 719 PrimitiveConstant n = (PrimitiveConstant) value; 720 return n.asLong() == 0; 721 } 722 723 @Override 724 public Constant getZero(Stamp s) { 725 IntegerStamp stamp = (IntegerStamp) s; 726 return JavaConstant.forPrimitiveInt(stamp.getBits(), 0); 727 } 728 }, 729 730 new BinaryOp.Mul(true, true) { 731 732 @Override 733 public Constant foldConstant(Constant const1, Constant const2) { 734 PrimitiveConstant a = (PrimitiveConstant) const1; 735 PrimitiveConstant b = (PrimitiveConstant) const2; 736 assert a.getJavaKind() == b.getJavaKind(); 737 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() * b.asLong()); 738 } 739 740 @Override 741 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) { 742 if (stamp1.isEmpty()) { 743 return stamp1; 744 } 745 if (stamp2.isEmpty()) { 746 return stamp2; 747 } 748 IntegerStamp a = (IntegerStamp) stamp1; 749 IntegerStamp b = (IntegerStamp) stamp2; 750 751 int bits = a.getBits(); 752 assert bits == b.getBits(); 753 754 if (a.lowerBound == a.upperBound && b.lowerBound == b.upperBound) { 755 long value = CodeUtil.convert(a.lowerBound() * b.lowerBound(), a.getBits(), false); 756 return StampFactory.forInteger(a.getBits(), value, value); 757 } 758 759 // if a==0 or b==0 result of a*b is always 0 760 if (a.upMask() == 0) { 761 return a; 762 } else if (b.upMask() == 0) { 763 return b; 764 } else { 765 // if a has the full range or b, the result will also have it 766 if (a.isUnrestricted()) { 767 return a; 768 } else if (b.isUnrestricted()) { 769 return b; 770 } 771 // a!=0 && b !=0 holds 772 long newLowerBound = Long.MAX_VALUE; 773 long newUpperBound = Long.MIN_VALUE; 774 /* 775 * Based on the signs of the incoming stamps lower and upper bound 776 * of the result of the multiplication may be swapped. LowerBound 777 * can become upper bound if both signs are negative, and so on. To 778 * determine the new values for lower and upper bound we need to 779 * look at the max and min of the cases blow: 780 * 781 * @formatter:off 782 * 783 * a.lowerBound * b.lowerBound 784 * a.lowerBound * b.upperBound 785 * a.upperBound * b.lowerBound 786 * a.upperBound * b.upperBound 787 * 788 * @formatter:on 789 * 790 * We are only interested in those cases that are relevant due to 791 * the sign of the involved stamps (whether a stamp includes 792 * negative and / or positive values). Based on the signs, the maximum 793 * or minimum of the above multiplications form the new lower and 794 * upper bounds. 795 * 796 * The table below contains the interesting candidates for lower and 797 * upper bound after multiplication. 798 * 799 * For example if we consider two stamps a & b that both contain 800 * negative and positive values, the product of minNegA * minNegB 801 * (both the smallest negative value for each stamp) can only be the 802 * highest positive number. The other candidates can be computed in 803 * a similar fashion. Some of them can never be a new minimum or 804 * maximum and are therefore excluded. 805 * 806 * 807 * @formatter:off 808 * 809 * [x................0................y] 810 * ------------------------------------- 811 * [minNeg maxNeg minPos maxPos] 812 * 813 * where maxNeg = min(0,y) && minPos = max(0,x) 814 * 815 * 816 * |minNegA maxNegA minPosA maxPosA 817 * _______ |____________________________________ 818 * minNegB | MAX / : / MIN 819 * maxNegB | / MIN : MAX / 820 * |------------------+----------------- 821 * minPosB | / MAX : MIN / 822 * maxPosB | MIN / : / MAX 823 * 824 * @formatter:on 825 */ 826 // We materialize all factors here. If they are needed, the signs of 827 // the stamp will ensure the correct value is used. 828 long minNegA = a.lowerBound(); 829 long maxNegA = Math.min(0, a.upperBound()); 830 long minPosA = Math.max(0, a.lowerBound()); 831 long maxPosA = a.upperBound(); 832 833 long minNegB = b.lowerBound(); 834 long maxNegB = Math.min(0, b.upperBound()); 835 long minPosB = Math.max(0, b.lowerBound()); 836 long maxPosB = b.upperBound(); 837 838 // multiplication has shift semantics 839 long newUpMask = ~CodeUtil.mask(Math.min(64, Long.numberOfTrailingZeros(a.upMask) + Long.numberOfTrailingZeros(b.upMask))) & CodeUtil.mask(bits); 840 841 if (a.canBePositive()) { 842 if (b.canBePositive()) { 843 if (multiplicationOverflows(maxPosA, maxPosB, bits)) { 844 return a.unrestricted(); 845 } 846 long maxCandidate = maxPosA * maxPosB; 847 if (multiplicationOverflows(minPosA, minPosB, bits)) { 848 return a.unrestricted(); 849 } 850 long minCandidate = minPosA * minPosB; 851 newLowerBound = Math.min(newLowerBound, minCandidate); 852 newUpperBound = Math.max(newUpperBound, maxCandidate); 853 } 854 if (b.canBeNegative()) { 855 if (multiplicationOverflows(minPosA, maxNegB, bits)) { 856 return a.unrestricted(); 857 } 858 long maxCandidate = minPosA * maxNegB; 859 if (multiplicationOverflows(maxPosA, minNegB, bits)) { 860 return a.unrestricted(); 861 } 862 long minCandidate = maxPosA * minNegB; 863 newLowerBound = Math.min(newLowerBound, minCandidate); 864 newUpperBound = Math.max(newUpperBound, maxCandidate); 865 } 866 } 867 if (a.canBeNegative()) { 868 if (b.canBePositive()) { 869 if (multiplicationOverflows(maxNegA, minPosB, bits)) { 870 return a.unrestricted(); 871 } 872 long maxCandidate = maxNegA * minPosB; 873 if (multiplicationOverflows(minNegA, maxPosB, bits)) { 874 return a.unrestricted(); 875 } 876 long minCandidate = minNegA * maxPosB; 877 newLowerBound = Math.min(newLowerBound, minCandidate); 878 newUpperBound = Math.max(newUpperBound, maxCandidate); 879 } 880 if (b.canBeNegative()) { 881 if (multiplicationOverflows(minNegA, minNegB, bits)) { 882 return a.unrestricted(); 883 } 884 long maxCandidate = minNegA * minNegB; 885 if (multiplicationOverflows(maxNegA, maxNegB, bits)) { 886 return a.unrestricted(); 887 } 888 long minCandidate = maxNegA * maxNegB; 889 newLowerBound = Math.min(newLowerBound, minCandidate); 890 newUpperBound = Math.max(newUpperBound, maxCandidate); 891 } 892 } 893 894 assert newLowerBound <= newUpperBound; 895 return StampFactory.forIntegerWithMask(bits, newLowerBound, newUpperBound, 0, newUpMask); 896 } 897 } 898 899 @Override 900 public boolean isNeutral(Constant value) { 901 PrimitiveConstant n = (PrimitiveConstant) value; 902 return n.asLong() == 1; 903 } 904 }, 905 906 new BinaryOp.MulHigh(true, true) { 907 908 @Override 909 public Constant foldConstant(Constant const1, Constant const2) { 910 PrimitiveConstant a = (PrimitiveConstant) const1; 911 PrimitiveConstant b = (PrimitiveConstant) const2; 912 assert a.getJavaKind() == b.getJavaKind(); 913 return JavaConstant.forIntegerKind(a.getJavaKind(), multiplyHigh(a.asLong(), b.asLong(), a.getJavaKind())); 914 } 915 916 @Override 917 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) { 918 if (stamp1.isEmpty()) { 919 return stamp1; 920 } 921 if (stamp2.isEmpty()) { 922 return stamp2; 923 } 924 IntegerStamp a = (IntegerStamp) stamp1; 925 IntegerStamp b = (IntegerStamp) stamp2; 926 JavaKind javaKind = a.getStackKind(); 927 928 assert a.getBits() == b.getBits(); 929 assert javaKind == b.getStackKind(); 930 assert (javaKind == JavaKind.Int || javaKind == JavaKind.Long); 931 932 if (a.isEmpty() || b.isEmpty()) { 933 return a.empty(); 934 } else if (a.isUnrestricted() || b.isUnrestricted()) { 935 return a.unrestricted(); 936 } 937 938 long[] xExtremes = {a.lowerBound(), a.upperBound()}; 939 long[] yExtremes = {b.lowerBound(), b.upperBound()}; 940 long min = Long.MAX_VALUE; 941 long max = Long.MIN_VALUE; 942 for (long x : xExtremes) { 943 for (long y : yExtremes) { 944 long result = multiplyHigh(x, y, javaKind); 945 min = Math.min(min, result); 946 max = Math.max(max, result); 947 } 948 } 949 return StampFactory.forInteger(javaKind, min, max); 950 } 951 952 @Override 953 public boolean isNeutral(Constant value) { 954 return false; 955 } 956 957 private long multiplyHigh(long x, long y, JavaKind javaKind) { 958 if (javaKind == JavaKind.Int) { 959 return (x * y) >> 32; 960 } else { 961 assert javaKind == JavaKind.Long; 962 long x0 = x & 0xFFFFFFFFL; 963 long x1 = x >> 32; 964 965 long y0 = y & 0xFFFFFFFFL; 966 long y1 = y >> 32; 967 968 long z0 = x0 * y0; 969 long t = x1 * y0 + (z0 >>> 32); 970 long z1 = t & 0xFFFFFFFFL; 971 long z2 = t >> 32; 972 z1 += x0 * y1; 973 974 return x1 * y1 + z2 + (z1 >> 32); 975 } 976 } 977 }, 978 979 new BinaryOp.UMulHigh(true, true) { 980 981 @Override 982 public Constant foldConstant(Constant const1, Constant const2) { 983 PrimitiveConstant a = (PrimitiveConstant) const1; 984 PrimitiveConstant b = (PrimitiveConstant) const2; 985 assert a.getJavaKind() == b.getJavaKind(); 986 return JavaConstant.forIntegerKind(a.getJavaKind(), multiplyHighUnsigned(a.asLong(), b.asLong(), a.getJavaKind())); 987 } 988 989 @Override 990 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) { 991 if (stamp1.isEmpty()) { 992 return stamp1; 993 } 994 if (stamp2.isEmpty()) { 995 return stamp2; 996 } 997 IntegerStamp a = (IntegerStamp) stamp1; 998 IntegerStamp b = (IntegerStamp) stamp2; 999 JavaKind javaKind = a.getStackKind(); 1000 1001 assert a.getBits() == b.getBits(); 1002 assert javaKind == b.getStackKind(); 1003 assert (javaKind == JavaKind.Int || javaKind == JavaKind.Long); 1004 1005 if (a.isEmpty() || b.isEmpty()) { 1006 return a.empty(); 1007 } else if (a.isUnrestricted() || b.isUnrestricted()) { 1008 return a.unrestricted(); 1009 } 1010 1011 // Note that the minima and maxima are calculated using signed min/max 1012 // functions, while the values themselves are unsigned. 1013 long[] xExtremes = getUnsignedExtremes(a); 1014 long[] yExtremes = getUnsignedExtremes(b); 1015 long min = Long.MAX_VALUE; 1016 long max = Long.MIN_VALUE; 1017 for (long x : xExtremes) { 1018 for (long y : yExtremes) { 1019 long result = multiplyHighUnsigned(x, y, javaKind); 1020 min = Math.min(min, result); 1021 max = Math.max(max, result); 1022 } 1023 } 1024 1025 // if min is negative, then the value can reach into the unsigned range 1026 if (min == max || min >= 0) { 1027 return StampFactory.forInteger(javaKind, min, max); 1028 } else { 1029 return StampFactory.forKind(javaKind); 1030 } 1031 } 1032 1033 @Override 1034 public boolean isNeutral(Constant value) { 1035 return false; 1036 } 1037 1038 private long[] getUnsignedExtremes(IntegerStamp stamp) { 1039 if (stamp.lowerBound() < 0 && stamp.upperBound() >= 0) { 1040 /* 1041 * If -1 and 0 are both in the signed range, then we can't say 1042 * anything about the unsigned range, so we have to return [0, 1043 * MAX_UNSIGNED]. 1044 */ 1045 return new long[]{0, -1L}; 1046 } else { 1047 return new long[]{stamp.lowerBound(), stamp.upperBound()}; 1048 } 1049 } 1050 1051 private long multiplyHighUnsigned(long x, long y, JavaKind javaKind) { 1052 if (javaKind == JavaKind.Int) { 1053 long xl = x & 0xFFFFFFFFL; 1054 long yl = y & 0xFFFFFFFFL; 1055 long r = xl * yl; 1056 return (int) (r >>> 32); 1057 } else { 1058 assert javaKind == JavaKind.Long; 1059 long x0 = x & 0xFFFFFFFFL; 1060 long x1 = x >>> 32; 1061 1062 long y0 = y & 0xFFFFFFFFL; 1063 long y1 = y >>> 32; 1064 1065 long z0 = x0 * y0; 1066 long t = x1 * y0 + (z0 >>> 32); 1067 long z1 = t & 0xFFFFFFFFL; 1068 long z2 = t >>> 32; 1069 z1 += x0 * y1; 1070 1071 return x1 * y1 + z2 + (z1 >>> 32); 1072 } 1073 } 1074 }, 1075 1076 new BinaryOp.Div(true, false) { 1077 1078 @Override 1079 public Constant foldConstant(Constant const1, Constant const2) { 1080 PrimitiveConstant a = (PrimitiveConstant) const1; 1081 PrimitiveConstant b = (PrimitiveConstant) const2; 1082 assert a.getJavaKind() == b.getJavaKind(); 1083 if (b.asLong() == 0) { 1084 return null; 1085 } 1086 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() / b.asLong()); 1087 } 1088 1089 @Override 1090 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) { 1091 if (stamp1.isEmpty()) { 1092 return stamp1; 1093 } 1094 if (stamp2.isEmpty()) { 1095 return stamp2; 1096 } 1097 IntegerStamp a = (IntegerStamp) stamp1; 1098 IntegerStamp b = (IntegerStamp) stamp2; 1099 assert a.getBits() == b.getBits(); 1100 if (a.lowerBound == a.upperBound && b.lowerBound == b.upperBound && b.lowerBound != 0) { 1101 long value = CodeUtil.convert(a.lowerBound() / b.lowerBound(), a.getBits(), false); 1102 return StampFactory.forInteger(a.getBits(), value, value); 1103 } else if (b.isStrictlyPositive()) { 1104 long newLowerBound = a.lowerBound() < 0 ? a.lowerBound() / b.lowerBound() : a.lowerBound() / b.upperBound(); 1105 long newUpperBound = a.upperBound() < 0 ? a.upperBound() / b.upperBound() : a.upperBound() / b.lowerBound(); 1106 return StampFactory.forInteger(a.getBits(), newLowerBound, newUpperBound); 1107 } else { 1108 return a.unrestricted(); 1109 } 1110 } 1111 1112 @Override 1113 public boolean isNeutral(Constant value) { 1114 PrimitiveConstant n = (PrimitiveConstant) value; 1115 return n.asLong() == 1; 1116 } 1117 }, 1118 1119 new BinaryOp.Rem(false, false) { 1120 1121 @Override 1122 public Constant foldConstant(Constant const1, Constant const2) { 1123 PrimitiveConstant a = (PrimitiveConstant) const1; 1124 PrimitiveConstant b = (PrimitiveConstant) const2; 1125 assert a.getJavaKind() == b.getJavaKind(); 1126 if (b.asLong() == 0) { 1127 return null; 1128 } 1129 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() % b.asLong()); 1130 } 1131 1132 @Override 1133 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) { 1134 if (stamp1.isEmpty()) { 1135 return stamp1; 1136 } 1137 if (stamp2.isEmpty()) { 1138 return stamp2; 1139 } 1140 IntegerStamp a = (IntegerStamp) stamp1; 1141 IntegerStamp b = (IntegerStamp) stamp2; 1142 assert a.getBits() == b.getBits(); 1143 1144 if (a.lowerBound == a.upperBound && b.lowerBound == b.upperBound && b.lowerBound != 0) { 1145 long value = CodeUtil.convert(a.lowerBound() % b.lowerBound(), a.getBits(), false); 1146 return StampFactory.forInteger(a.getBits(), value, value); 1147 } 1148 1149 // zero is always possible 1150 long newLowerBound = Math.min(a.lowerBound(), 0); 1151 long newUpperBound = Math.max(a.upperBound(), 0); 1152 1153 /* the maximum absolute value of the result, derived from b */ 1154 long magnitude; 1155 if (b.lowerBound() == CodeUtil.minValue(b.getBits())) { 1156 // Math.abs(...) - 1 does not work in a case 1157 magnitude = CodeUtil.maxValue(b.getBits()); 1158 } else { 1159 magnitude = Math.max(Math.abs(b.lowerBound()), Math.abs(b.upperBound())) - 1; 1160 } 1161 newLowerBound = Math.max(newLowerBound, -magnitude); 1162 newUpperBound = Math.min(newUpperBound, magnitude); 1163 1164 return StampFactory.forInteger(a.getBits(), newLowerBound, newUpperBound); 1165 } 1166 }, 1167 1168 new UnaryOp.Not() { 1169 1170 @Override 1171 public Constant foldConstant(Constant c) { 1172 PrimitiveConstant value = (PrimitiveConstant) c; 1173 return JavaConstant.forIntegerKind(value.getJavaKind(), ~value.asLong()); 1174 } 1175 1176 @Override 1177 public Stamp foldStamp(Stamp stamp) { 1178 if (stamp.isEmpty()) { 1179 return stamp; 1180 } 1181 IntegerStamp integerStamp = (IntegerStamp) stamp; 1182 int bits = integerStamp.getBits(); 1183 long defaultMask = CodeUtil.mask(bits); 1184 return new IntegerStamp(bits, ~integerStamp.upperBound(), ~integerStamp.lowerBound(), (~integerStamp.upMask()) & defaultMask, (~integerStamp.downMask()) & defaultMask); 1185 } 1186 }, 1187 1188 new BinaryOp.And(true, true) { 1189 1190 @Override 1191 public Constant foldConstant(Constant const1, Constant const2) { 1192 PrimitiveConstant a = (PrimitiveConstant) const1; 1193 PrimitiveConstant b = (PrimitiveConstant) const2; 1194 assert a.getJavaKind() == b.getJavaKind(); 1195 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() & b.asLong()); 1196 } 1197 1198 @Override 1199 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) { 1200 if (stamp1.isEmpty()) { 1201 return stamp1; 1202 } 1203 if (stamp2.isEmpty()) { 1204 return stamp2; 1205 } 1206 IntegerStamp a = (IntegerStamp) stamp1; 1207 IntegerStamp b = (IntegerStamp) stamp2; 1208 assert a.getBits() == b.getBits(); 1209 return stampForMask(a.getBits(), a.downMask() & b.downMask(), a.upMask() & b.upMask()); 1210 } 1211 1212 @Override 1213 public boolean isNeutral(Constant value) { 1214 PrimitiveConstant n = (PrimitiveConstant) value; 1215 int bits = n.getJavaKind().getBitCount(); 1216 long mask = CodeUtil.mask(bits); 1217 return (n.asLong() & mask) == mask; 1218 } 1219 }, 1220 1221 new BinaryOp.Or(true, true) { 1222 1223 @Override 1224 public Constant foldConstant(Constant const1, Constant const2) { 1225 PrimitiveConstant a = (PrimitiveConstant) const1; 1226 PrimitiveConstant b = (PrimitiveConstant) const2; 1227 assert a.getJavaKind() == b.getJavaKind(); 1228 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() | b.asLong()); 1229 } 1230 1231 @Override 1232 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) { 1233 if (stamp1.isEmpty()) { 1234 return stamp1; 1235 } 1236 if (stamp2.isEmpty()) { 1237 return stamp2; 1238 } 1239 IntegerStamp a = (IntegerStamp) stamp1; 1240 IntegerStamp b = (IntegerStamp) stamp2; 1241 assert a.getBits() == b.getBits(); 1242 return stampForMask(a.getBits(), a.downMask() | b.downMask(), a.upMask() | b.upMask()); 1243 } 1244 1245 @Override 1246 public boolean isNeutral(Constant value) { 1247 PrimitiveConstant n = (PrimitiveConstant) value; 1248 return n.asLong() == 0; 1249 } 1250 }, 1251 1252 new BinaryOp.Xor(true, true) { 1253 1254 @Override 1255 public Constant foldConstant(Constant const1, Constant const2) { 1256 PrimitiveConstant a = (PrimitiveConstant) const1; 1257 PrimitiveConstant b = (PrimitiveConstant) const2; 1258 assert a.getJavaKind() == b.getJavaKind(); 1259 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() ^ b.asLong()); 1260 } 1261 1262 @Override 1263 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) { 1264 if (stamp1.isEmpty()) { 1265 return stamp1; 1266 } 1267 if (stamp2.isEmpty()) { 1268 return stamp2; 1269 } 1270 IntegerStamp a = (IntegerStamp) stamp1; 1271 IntegerStamp b = (IntegerStamp) stamp2; 1272 assert a.getBits() == b.getBits(); 1273 1274 long variableBits = (a.downMask() ^ a.upMask()) | (b.downMask() ^ b.upMask()); 1275 long newDownMask = (a.downMask() ^ b.downMask()) & ~variableBits; 1276 long newUpMask = (a.downMask() ^ b.downMask()) | variableBits; 1277 return stampForMask(a.getBits(), newDownMask, newUpMask); 1278 } 1279 1280 @Override 1281 public boolean isNeutral(Constant value) { 1282 PrimitiveConstant n = (PrimitiveConstant) value; 1283 return n.asLong() == 0; 1284 } 1285 1286 @Override 1287 public Constant getZero(Stamp s) { 1288 IntegerStamp stamp = (IntegerStamp) s; 1289 return JavaConstant.forPrimitiveInt(stamp.getBits(), 0); 1290 } 1291 }, 1292 1293 new ShiftOp.Shl() { 1294 1295 @Override 1296 public Constant foldConstant(Constant value, int amount) { 1297 PrimitiveConstant c = (PrimitiveConstant) value; 1298 switch (c.getJavaKind()) { 1299 case Int: 1300 return JavaConstant.forInt(c.asInt() << amount); 1301 case Long: 1302 return JavaConstant.forLong(c.asLong() << amount); 1303 default: 1304 throw GraalError.shouldNotReachHere(); 1305 } 1306 } 1307 1308 private boolean testNoSignChangeAfterShifting(int bits, long value, int shiftAmount) { 1309 long removedBits = -1L << (bits - shiftAmount - 1); 1310 if (value < 0) { 1311 return (value & removedBits) == removedBits; 1312 } else { 1313 return (value & removedBits) == 0; 1314 } 1315 } 1316 1317 @Override 1318 public Stamp foldStamp(Stamp stamp, IntegerStamp shift) { 1319 IntegerStamp value = (IntegerStamp) stamp; 1320 int bits = value.getBits(); 1321 if (value.isEmpty()) { 1322 return value; 1323 } else if (shift.isEmpty()) { 1324 return StampFactory.forInteger(bits).empty(); 1325 } else if (value.upMask() == 0) { 1326 return value; 1327 } 1328 1329 int shiftMask = getShiftAmountMask(stamp); 1330 int shiftBits = Integer.bitCount(shiftMask); 1331 if (shift.lowerBound() == shift.upperBound()) { 1332 int shiftAmount = (int) (shift.lowerBound() & shiftMask); 1333 if (shiftAmount == 0) { 1334 return value; 1335 } 1336 // the mask of bits that will be lost or shifted into the sign bit 1337 if (testNoSignChangeAfterShifting(bits, value.lowerBound(), shiftAmount) && testNoSignChangeAfterShifting(bits, value.upperBound(), shiftAmount)) { 1338 /* 1339 * use a better stamp if neither lower nor upper bound can lose 1340 * bits 1341 */ 1342 IntegerStamp result = new IntegerStamp(bits, value.lowerBound() << shiftAmount, value.upperBound() << shiftAmount, 1343 (value.downMask() << shiftAmount) & CodeUtil.mask(bits), 1344 (value.upMask() << shiftAmount) & CodeUtil.mask(bits)); 1345 return result; 1346 } 1347 } 1348 if ((shift.lowerBound() >>> shiftBits) == (shift.upperBound() >>> shiftBits)) { 1349 long defaultMask = CodeUtil.mask(bits); 1350 long downMask = defaultMask; 1351 long upMask = 0; 1352 for (long i = shift.lowerBound(); i <= shift.upperBound(); i++) { 1353 if (shift.contains(i)) { 1354 downMask &= value.downMask() << (i & shiftMask); 1355 upMask |= value.upMask() << (i & shiftMask); 1356 } 1357 } 1358 return IntegerStamp.stampForMask(bits, downMask, upMask & defaultMask); 1359 } 1360 return value.unrestricted(); 1361 } 1362 1363 @Override 1364 public int getShiftAmountMask(Stamp s) { 1365 IntegerStamp stamp = (IntegerStamp) s; 1366 assert CodeUtil.isPowerOf2(stamp.getBits()); 1367 return stamp.getBits() - 1; 1368 } 1369 }, 1370 1371 new ShiftOp.Shr() { 1372 1373 @Override 1374 public Constant foldConstant(Constant value, int amount) { 1375 PrimitiveConstant c = (PrimitiveConstant) value; 1376 switch (c.getJavaKind()) { 1377 case Int: 1378 return JavaConstant.forInt(c.asInt() >> amount); 1379 case Long: 1380 return JavaConstant.forLong(c.asLong() >> amount); 1381 default: 1382 throw GraalError.shouldNotReachHere(); 1383 } 1384 } 1385 1386 @Override 1387 public Stamp foldStamp(Stamp stamp, IntegerStamp shift) { 1388 IntegerStamp value = (IntegerStamp) stamp; 1389 int bits = value.getBits(); 1390 if (value.isEmpty()) { 1391 return value; 1392 } else if (shift.isEmpty()) { 1393 return StampFactory.forInteger(bits).empty(); 1394 } else if (shift.lowerBound() == shift.upperBound()) { 1395 long shiftCount = shift.lowerBound() & getShiftAmountMask(stamp); 1396 if (shiftCount == 0) { 1397 return stamp; 1398 } 1399 1400 int extraBits = 64 - bits; 1401 long defaultMask = CodeUtil.mask(bits); 1402 // shifting back and forth performs sign extension 1403 long downMask = (value.downMask() << extraBits) >> (shiftCount + extraBits) & defaultMask; 1404 long upMask = (value.upMask() << extraBits) >> (shiftCount + extraBits) & defaultMask; 1405 return new IntegerStamp(bits, value.lowerBound() >> shiftCount, value.upperBound() >> shiftCount, downMask, upMask); 1406 } 1407 long mask = IntegerStamp.upMaskFor(bits, value.lowerBound(), value.upperBound()); 1408 return IntegerStamp.stampForMask(bits, 0, mask); 1409 } 1410 1411 @Override 1412 public int getShiftAmountMask(Stamp s) { 1413 IntegerStamp stamp = (IntegerStamp) s; 1414 assert CodeUtil.isPowerOf2(stamp.getBits()); 1415 return stamp.getBits() - 1; 1416 } 1417 }, 1418 1419 new ShiftOp.UShr() { 1420 1421 @Override 1422 public Constant foldConstant(Constant value, int amount) { 1423 PrimitiveConstant c = (PrimitiveConstant) value; 1424 switch (c.getJavaKind()) { 1425 case Int: 1426 return JavaConstant.forInt(c.asInt() >>> amount); 1427 case Long: 1428 return JavaConstant.forLong(c.asLong() >>> amount); 1429 default: 1430 throw GraalError.shouldNotReachHere(); 1431 } 1432 } 1433 1434 @Override 1435 public Stamp foldStamp(Stamp stamp, IntegerStamp shift) { 1436 IntegerStamp value = (IntegerStamp) stamp; 1437 int bits = value.getBits(); 1438 if (value.isEmpty()) { 1439 return value; 1440 } else if (shift.isEmpty()) { 1441 return StampFactory.forInteger(bits).empty(); 1442 } 1443 1444 if (shift.lowerBound() == shift.upperBound()) { 1445 long shiftCount = shift.lowerBound() & getShiftAmountMask(stamp); 1446 if (shiftCount == 0) { 1447 return stamp; 1448 } 1449 1450 long downMask = value.downMask() >>> shiftCount; 1451 long upMask = value.upMask() >>> shiftCount; 1452 if (value.lowerBound() < 0) { 1453 return new IntegerStamp(bits, downMask, upMask, downMask, upMask); 1454 } else { 1455 return new IntegerStamp(bits, value.lowerBound() >>> shiftCount, value.upperBound() >>> shiftCount, downMask, upMask); 1456 } 1457 } 1458 long mask = IntegerStamp.upMaskFor(bits, value.lowerBound(), value.upperBound()); 1459 return IntegerStamp.stampForMask(bits, 0, mask); 1460 } 1461 1462 @Override 1463 public int getShiftAmountMask(Stamp s) { 1464 IntegerStamp stamp = (IntegerStamp) s; 1465 assert CodeUtil.isPowerOf2(stamp.getBits()); 1466 return stamp.getBits() - 1; 1467 } 1468 }, 1469 1470 new UnaryOp.Abs() { 1471 1472 @Override 1473 public Constant foldConstant(Constant value) { 1474 PrimitiveConstant c = (PrimitiveConstant) value; 1475 return JavaConstant.forIntegerKind(c.getJavaKind(), Math.abs(c.asLong())); 1476 } 1477 1478 @Override 1479 public Stamp foldStamp(Stamp input) { 1480 if (input.isEmpty()) { 1481 return input; 1482 } 1483 IntegerStamp stamp = (IntegerStamp) input; 1484 int bits = stamp.getBits(); 1485 if (stamp.lowerBound == stamp.upperBound) { 1486 long value = CodeUtil.convert(Math.abs(stamp.lowerBound()), stamp.getBits(), false); 1487 return StampFactory.forInteger(stamp.getBits(), value, value); 1488 } 1489 if (stamp.lowerBound() == CodeUtil.minValue(bits)) { 1490 return input.unrestricted(); 1491 } else { 1492 long limit = Math.max(-stamp.lowerBound(), stamp.upperBound()); 1493 return StampFactory.forInteger(bits, 0, limit); 1494 } 1495 } 1496 }, 1497 1498 null, 1499 1500 new IntegerConvertOp.ZeroExtend() { 1501 1502 @Override 1503 public Constant foldConstant(int inputBits, int resultBits, Constant c) { 1504 PrimitiveConstant value = (PrimitiveConstant) c; 1505 return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.zeroExtend(value.asLong(), inputBits)); 1506 } 1507 1508 @Override 1509 public Stamp foldStamp(int inputBits, int resultBits, Stamp input) { 1510 if (input.isEmpty()) { 1511 return StampFactory.forInteger(resultBits).empty(); 1512 } 1513 IntegerStamp stamp = (IntegerStamp) input; 1514 assert inputBits == stamp.getBits(); 1515 assert inputBits <= resultBits; 1516 1517 if (inputBits == resultBits) { 1518 return input; 1519 } 1520 1521 if (input.isEmpty()) { 1522 return StampFactory.forInteger(resultBits).empty(); 1523 } 1524 1525 long downMask = CodeUtil.zeroExtend(stamp.downMask(), inputBits); 1526 long upMask = CodeUtil.zeroExtend(stamp.upMask(), inputBits); 1527 long lowerBound = stamp.unsignedLowerBound(); 1528 long upperBound = stamp.unsignedUpperBound(); 1529 return IntegerStamp.create(resultBits, lowerBound, upperBound, downMask, upMask); 1530 } 1531 1532 @Override 1533 public Stamp invertStamp(int inputBits, int resultBits, Stamp outStamp) { 1534 IntegerStamp stamp = (IntegerStamp) outStamp; 1535 if (stamp.isEmpty()) { 1536 return StampFactory.forInteger(inputBits).empty(); 1537 } 1538 return StampFactory.forUnsignedInteger(inputBits, stamp.lowerBound(), stamp.upperBound(), stamp.downMask(), stamp.upMask()); 1539 } 1540 }, 1541 1542 new IntegerConvertOp.SignExtend() { 1543 1544 @Override 1545 public Constant foldConstant(int inputBits, int resultBits, Constant c) { 1546 PrimitiveConstant value = (PrimitiveConstant) c; 1547 return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.signExtend(value.asLong(), inputBits)); 1548 } 1549 1550 @Override 1551 public Stamp foldStamp(int inputBits, int resultBits, Stamp input) { 1552 if (input.isEmpty()) { 1553 return StampFactory.forInteger(resultBits).empty(); 1554 } 1555 IntegerStamp stamp = (IntegerStamp) input; 1556 assert inputBits == stamp.getBits(); 1557 assert inputBits <= resultBits; 1558 1559 long defaultMask = CodeUtil.mask(resultBits); 1560 long downMask = CodeUtil.signExtend(stamp.downMask(), inputBits) & defaultMask; 1561 long upMask = CodeUtil.signExtend(stamp.upMask(), inputBits) & defaultMask; 1562 1563 return new IntegerStamp(resultBits, stamp.lowerBound(), stamp.upperBound(), downMask, upMask); 1564 } 1565 1566 @Override 1567 public Stamp invertStamp(int inputBits, int resultBits, Stamp outStamp) { 1568 if (outStamp.isEmpty()) { 1569 return StampFactory.forInteger(inputBits).empty(); 1570 } 1571 IntegerStamp stamp = (IntegerStamp) outStamp; 1572 long mask = CodeUtil.mask(inputBits); 1573 return StampFactory.forIntegerWithMask(inputBits, stamp.lowerBound(), stamp.upperBound(), stamp.downMask() & mask, stamp.upMask() & mask); 1574 } 1575 }, 1576 1577 new IntegerConvertOp.Narrow() { 1578 1579 @Override 1580 public Constant foldConstant(int inputBits, int resultBits, Constant c) { 1581 PrimitiveConstant value = (PrimitiveConstant) c; 1582 return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.narrow(value.asLong(), resultBits)); 1583 } 1584 1585 @Override 1586 public Stamp foldStamp(int inputBits, int resultBits, Stamp input) { 1587 if (input.isEmpty()) { 1588 return StampFactory.forInteger(resultBits).empty(); 1589 } 1590 IntegerStamp stamp = (IntegerStamp) input; 1591 assert inputBits == stamp.getBits(); 1592 assert resultBits <= inputBits; 1593 if (resultBits == inputBits) { 1594 return stamp; 1595 } 1596 1597 final long upperBound; 1598 if (stamp.lowerBound() < CodeUtil.minValue(resultBits)) { 1599 upperBound = CodeUtil.maxValue(resultBits); 1600 } else { 1601 upperBound = saturate(stamp.upperBound(), resultBits); 1602 } 1603 final long lowerBound; 1604 if (stamp.upperBound() > CodeUtil.maxValue(resultBits)) { 1605 lowerBound = CodeUtil.minValue(resultBits); 1606 } else { 1607 lowerBound = saturate(stamp.lowerBound(), resultBits); 1608 } 1609 1610 long defaultMask = CodeUtil.mask(resultBits); 1611 long newDownMask = stamp.downMask() & defaultMask; 1612 long newUpMask = stamp.upMask() & defaultMask; 1613 long newLowerBound = CodeUtil.signExtend((lowerBound | newDownMask) & newUpMask, resultBits); 1614 long newUpperBound = CodeUtil.signExtend((upperBound | newDownMask) & newUpMask, resultBits); 1615 1616 IntegerStamp result = new IntegerStamp(resultBits, newLowerBound, newUpperBound, newDownMask, newUpMask); 1617 assert result.hasValues(); 1618 return result; 1619 } 1620 }, 1621 1622 new FloatConvertOp(I2F) { 1623 1624 @Override 1625 public Constant foldConstant(Constant c) { 1626 PrimitiveConstant value = (PrimitiveConstant) c; 1627 return JavaConstant.forFloat(value.asInt()); 1628 } 1629 1630 @Override 1631 public Stamp foldStamp(Stamp input) { 1632 if (input.isEmpty()) { 1633 return StampFactory.empty(JavaKind.Float); 1634 } 1635 IntegerStamp stamp = (IntegerStamp) input; 1636 assert stamp.getBits() == 32; 1637 float lowerBound = stamp.lowerBound(); 1638 float upperBound = stamp.upperBound(); 1639 return StampFactory.forFloat(JavaKind.Float, lowerBound, upperBound, true); 1640 } 1641 }, 1642 1643 new FloatConvertOp(L2F) { 1644 1645 @Override 1646 public Constant foldConstant(Constant c) { 1647 PrimitiveConstant value = (PrimitiveConstant) c; 1648 return JavaConstant.forFloat(value.asLong()); 1649 } 1650 1651 @Override 1652 public Stamp foldStamp(Stamp input) { 1653 if (input.isEmpty()) { 1654 return StampFactory.empty(JavaKind.Float); 1655 } 1656 IntegerStamp stamp = (IntegerStamp) input; 1657 assert stamp.getBits() == 64; 1658 float lowerBound = stamp.lowerBound(); 1659 float upperBound = stamp.upperBound(); 1660 return StampFactory.forFloat(JavaKind.Float, lowerBound, upperBound, true); 1661 } 1662 }, 1663 1664 new FloatConvertOp(I2D) { 1665 1666 @Override 1667 public Constant foldConstant(Constant c) { 1668 PrimitiveConstant value = (PrimitiveConstant) c; 1669 return JavaConstant.forDouble(value.asInt()); 1670 } 1671 1672 @Override 1673 public Stamp foldStamp(Stamp input) { 1674 if (input.isEmpty()) { 1675 return StampFactory.empty(JavaKind.Double); 1676 } 1677 IntegerStamp stamp = (IntegerStamp) input; 1678 assert stamp.getBits() == 32; 1679 double lowerBound = stamp.lowerBound(); 1680 double upperBound = stamp.upperBound(); 1681 return StampFactory.forFloat(JavaKind.Double, lowerBound, upperBound, true); 1682 } 1683 }, 1684 1685 new FloatConvertOp(L2D) { 1686 1687 @Override 1688 public Constant foldConstant(Constant c) { 1689 PrimitiveConstant value = (PrimitiveConstant) c; 1690 return JavaConstant.forDouble(value.asLong()); 1691 } 1692 1693 @Override 1694 public Stamp foldStamp(Stamp input) { 1695 if (input.isEmpty()) { 1696 return StampFactory.empty(JavaKind.Double); 1697 } 1698 IntegerStamp stamp = (IntegerStamp) input; 1699 assert stamp.getBits() == 64; 1700 double lowerBound = stamp.lowerBound(); 1701 double upperBound = stamp.upperBound(); 1702 return StampFactory.forFloat(JavaKind.Double, lowerBound, upperBound, true); 1703 } 1704 }); 1705 } 1706