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