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