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.spi.LIRKindTool; 35import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp; 36import org.graalvm.compiler.core.common.type.ArithmeticOpTable.FloatConvertOp; 37import org.graalvm.compiler.core.common.type.ArithmeticOpTable.IntegerConvertOp; 38import org.graalvm.compiler.core.common.type.ArithmeticOpTable.ShiftOp; 39import org.graalvm.compiler.core.common.type.ArithmeticOpTable.UnaryOp; 40import org.graalvm.compiler.debug.GraalError; 41 42import jdk.vm.ci.code.CodeUtil; 43import jdk.vm.ci.meta.Constant; 44import jdk.vm.ci.meta.JavaConstant; 45import jdk.vm.ci.meta.JavaKind; 46import jdk.vm.ci.meta.MetaAccessProvider; 47import jdk.vm.ci.meta.PrimitiveConstant; 48import jdk.vm.ci.meta.ResolvedJavaType; 49import jdk.vm.ci.meta.SerializableConstant; 50 51/** 52 * Describes the possible values of a node that produces an int or long result. 53 * 54 * The description consists of (inclusive) lower and upper bounds and up (may be set) and down 55 * (always set) bit-masks. 56 */ 57public class IntegerStamp extends PrimitiveStamp { 58 59 private final long lowerBound; 60 private final long upperBound; 61 private final long downMask; 62 private final long upMask; 63 64 public IntegerStamp(int bits, long lowerBound, long upperBound, long downMask, long upMask) { 65 super(bits, OPS); 66 this.lowerBound = lowerBound; 67 this.upperBound = upperBound; 68 this.downMask = downMask; 69 this.upMask = upMask; 70 assert lowerBound >= CodeUtil.minValue(bits) : this; 71 assert upperBound <= CodeUtil.maxValue(bits) : this; 72 assert (downMask & CodeUtil.mask(bits)) == downMask : this; 73 assert (upMask & CodeUtil.mask(bits)) == upMask : this; 74 } 75 76 public static IntegerStamp stampForMask(int bits, long downMask, long upMask) { 77 long lowerBound; 78 long upperBound; 79 if (((upMask >>> (bits - 1)) & 1) == 0) { 80 lowerBound = downMask; 81 upperBound = upMask; 82 } else if (((downMask >>> (bits - 1)) & 1) == 1) { 83 lowerBound = downMask; 84 upperBound = upMask; 85 } else { 86 lowerBound = downMask | (-1L << (bits - 1)); 87 upperBound = CodeUtil.maxValue(bits) & upMask; 88 } 89 lowerBound = CodeUtil.convert(lowerBound, bits, false); 90 upperBound = CodeUtil.convert(upperBound, bits, false); 91 return new IntegerStamp(bits, lowerBound, upperBound, downMask, upMask); 92 } 93 94 @Override 95 public IntegerStamp unrestricted() { 96 return new IntegerStamp(getBits(), CodeUtil.minValue(getBits()), CodeUtil.maxValue(getBits()), 0, CodeUtil.mask(getBits())); 97 } 98 99 @Override 100 public Stamp empty() { 101 return new IntegerStamp(getBits(), CodeUtil.maxValue(getBits()), CodeUtil.minValue(getBits()), CodeUtil.mask(getBits()), 0); 102 } 103 104 @Override 105 public Stamp constant(Constant c, MetaAccessProvider meta) { 106 if (c instanceof PrimitiveConstant) { 107 long value = ((PrimitiveConstant) c).asLong(); 108 return StampFactory.forInteger(getBits(), value, value); 109 } 110 return this; 111 } 112 113 @Override 114 public SerializableConstant deserialize(ByteBuffer buffer) { 115 switch (getBits()) { 116 case 1: 117 return JavaConstant.forBoolean(buffer.get() != 0); 118 case 8: 119 return JavaConstant.forByte(buffer.get()); 120 case 16: 121 return JavaConstant.forShort(buffer.getShort()); 122 case 32: 123 return JavaConstant.forInt(buffer.getInt()); 124 case 64: 125 return JavaConstant.forLong(buffer.getLong()); 126 default: 127 throw GraalError.shouldNotReachHere(); 128 } 129 } 130 131 @Override 132 public boolean hasValues() { 133 return lowerBound <= upperBound; 134 } 135 136 @Override 137 public JavaKind getStackKind() { 138 if (getBits() > 32) { 139 return JavaKind.Long; 140 } else { 141 return JavaKind.Int; 142 } 143 } 144 145 @Override 146 public LIRKind getLIRKind(LIRKindTool tool) { 147 return tool.getIntegerKind(getBits()); 148 } 149 150 @Override 151 public ResolvedJavaType javaType(MetaAccessProvider metaAccess) { 152 switch (getBits()) { 153 case 1: 154 return metaAccess.lookupJavaType(Boolean.TYPE); 155 case 8: 156 return metaAccess.lookupJavaType(Byte.TYPE); 157 case 16: 158 return metaAccess.lookupJavaType(Short.TYPE); 159 case 32: 160 return metaAccess.lookupJavaType(Integer.TYPE); 161 case 64: 162 return metaAccess.lookupJavaType(Long.TYPE); 163 default: 164 throw GraalError.shouldNotReachHere(); 165 } 166 } 167 168 /** 169 * The signed inclusive lower bound on the value described by this stamp. 170 */ 171 public long lowerBound() { 172 return lowerBound; 173 } 174 175 /** 176 * The signed inclusive upper bound on the value described by this stamp. 177 */ 178 public long upperBound() { 179 return upperBound; 180 } 181 182 /** 183 * This bit-mask describes the bits that are always set in the value described by this stamp. 184 */ 185 public long downMask() { 186 return downMask; 187 } 188 189 /** 190 * This bit-mask describes the bits that can be set in the value described by this stamp. 191 */ 192 public long upMask() { 193 return upMask; 194 } 195 196 public boolean isUnrestricted() { 197 return lowerBound == CodeUtil.minValue(getBits()) && upperBound == CodeUtil.maxValue(getBits()) && downMask == 0 && upMask == CodeUtil.mask(getBits()); 198 } 199 200 public boolean contains(long value) { 201 return value >= lowerBound && value <= upperBound && (value & downMask) == downMask && (value & upMask) == (value & CodeUtil.mask(getBits())); 202 } 203 204 public boolean isPositive() { 205 return lowerBound() >= 0; 206 } 207 208 public boolean isNegative() { 209 return upperBound() <= 0; 210 } 211 212 public boolean isStrictlyPositive() { 213 return lowerBound() > 0; 214 } 215 216 public boolean isStrictlyNegative() { 217 return upperBound() < 0; 218 } 219 220 public boolean canBePositive() { 221 return upperBound() > 0; 222 } 223 224 public boolean canBeNegative() { 225 return lowerBound() < 0; 226 } 227 228 @Override 229 public String toString() { 230 StringBuilder str = new StringBuilder(); 231 str.append('i'); 232 str.append(getBits()); 233 if (lowerBound == upperBound) { 234 str.append(" [").append(lowerBound).append(']'); 235 } else if (lowerBound != CodeUtil.minValue(getBits()) || upperBound != CodeUtil.maxValue(getBits())) { 236 str.append(" [").append(lowerBound).append(" - ").append(upperBound).append(']'); 237 } 238 if (downMask != 0) { 239 str.append(" \u21ca"); 240 new Formatter(str).format("%016x", downMask); 241 } 242 if (upMask != CodeUtil.mask(getBits())) { 243 str.append(" \u21c8"); 244 new Formatter(str).format("%016x", upMask); 245 } 246 return str.toString(); 247 } 248 249 private Stamp createStamp(IntegerStamp other, long newUpperBound, long newLowerBound, long newDownMask, long newUpMask) { 250 assert getBits() == other.getBits(); 251 if (newLowerBound > newUpperBound || (newDownMask & (~newUpMask)) != 0 || (newUpMask == 0 && (newLowerBound > 0 || newUpperBound < 0))) { 252 return empty(); 253 } else if (newLowerBound == lowerBound && newUpperBound == upperBound && newDownMask == downMask && newUpMask == upMask) { 254 return this; 255 } else if (newLowerBound == other.lowerBound && newUpperBound == other.upperBound && newDownMask == other.downMask && newUpMask == other.upMask) { 256 return other; 257 } else { 258 return new IntegerStamp(getBits(), newLowerBound, newUpperBound, newDownMask, newUpMask); 259 } 260 } 261 262 @Override 263 public Stamp meet(Stamp otherStamp) { 264 if (otherStamp == this) { 265 return this; 266 } 267 IntegerStamp other = (IntegerStamp) otherStamp; 268 return createStamp(other, Math.max(upperBound, other.upperBound), Math.min(lowerBound, other.lowerBound), downMask & other.downMask, upMask | other.upMask); 269 } 270 271 @Override 272 public Stamp join(Stamp otherStamp) { 273 if (otherStamp == this) { 274 return this; 275 } 276 IntegerStamp other = (IntegerStamp) otherStamp; 277 long newDownMask = downMask | other.downMask; 278 long newLowerBound = Math.max(lowerBound, other.lowerBound) | newDownMask; 279 long newUpperBound = Math.min(upperBound, other.upperBound); 280 long newUpMask = upMask & other.upMask; 281 IntegerStamp limit = StampFactory.forInteger(getBits(), newLowerBound, newUpperBound); 282 return createStamp(other, newUpperBound, newLowerBound, limit.downMask() | newDownMask, limit.upMask() & newUpMask); 283 } 284 285 @Override 286 public boolean isCompatible(Stamp stamp) { 287 if (this == stamp) { 288 return true; 289 } 290 if (stamp instanceof IntegerStamp) { 291 IntegerStamp other = (IntegerStamp) stamp; 292 return getBits() == other.getBits(); 293 } 294 return false; 295 } 296 297 @Override 298 public boolean isCompatible(Constant constant) { 299 if (constant instanceof PrimitiveConstant) { 300 PrimitiveConstant prim = (PrimitiveConstant) constant; 301 return prim.getJavaKind().isNumericInteger(); 302 } 303 return false; 304 } 305 306 @Override 307 public int hashCode() { 308 final int prime = 31; 309 int result = 1; 310 result = prime * result + super.hashCode(); 311 result = prime * result + (int) (lowerBound ^ (lowerBound >>> 32)); 312 result = prime * result + (int) (upperBound ^ (upperBound >>> 32)); 313 result = prime * result + (int) (downMask ^ (downMask >>> 32)); 314 result = prime * result + (int) (upMask ^ (upMask >>> 32)); 315 return result; 316 } 317 318 @Override 319 public boolean equals(Object obj) { 320 if (this == obj) { 321 return true; 322 } 323 if (obj == null || getClass() != obj.getClass() || !super.equals(obj)) { 324 return false; 325 } 326 IntegerStamp other = (IntegerStamp) obj; 327 if (lowerBound != other.lowerBound || upperBound != other.upperBound || downMask != other.downMask || upMask != other.upMask) { 328 return false; 329 } 330 return super.equals(other); 331 } 332 333 public static long upMaskFor(int bits, long lowerBound, long upperBound) { 334 long mask = lowerBound | upperBound; 335 if (mask == 0) { 336 return 0; 337 } else { 338 return ((-1L) >>> Long.numberOfLeadingZeros(mask)) & CodeUtil.mask(bits); 339 } 340 } 341 342 /** 343 * Checks if the 2 stamps represent values of the same sign. Returns true if the two stamps are 344 * both positive of null or if they are both strictly negative 345 * 346 * @return true if the two stamps are both positive of null or if they are both strictly 347 * negative 348 */ 349 public static boolean sameSign(IntegerStamp s1, IntegerStamp s2) { 350 return s1.isPositive() && s2.isPositive() || s1.isStrictlyNegative() && s2.isStrictlyNegative(); 351 } 352 353 @Override 354 public JavaConstant asConstant() { 355 if (lowerBound == upperBound) { 356 switch (getBits()) { 357 case 1: 358 return JavaConstant.forBoolean(lowerBound != 0); 359 case 8: 360 return JavaConstant.forByte((byte) lowerBound); 361 case 16: 362 return JavaConstant.forShort((short) lowerBound); 363 case 32: 364 return JavaConstant.forInt((int) lowerBound); 365 case 64: 366 return JavaConstant.forLong(lowerBound); 367 } 368 } 369 return null; 370 } 371 372 public static boolean addOverflowsPositively(long x, long y, int bits) { 373 long result = x + y; 374 if (bits == 64) { 375 return (~x & ~y & result) < 0; 376 } else { 377 return result > CodeUtil.maxValue(bits); 378 } 379 } 380 381 public static boolean addOverflowsNegatively(long x, long y, int bits) { 382 long result = x + y; 383 if (bits == 64) { 384 return (x & y & ~result) < 0; 385 } else { 386 return result < CodeUtil.minValue(bits); 387 } 388 } 389 390 public static long carryBits(long x, long y) { 391 return (x + y) ^ x ^ y; 392 } 393 394 private static long saturate(long v, int bits) { 395 if (bits < 64) { 396 long max = CodeUtil.maxValue(bits); 397 if (v > max) { 398 return max; 399 } 400 long min = CodeUtil.minValue(bits); 401 if (v < min) { 402 return min; 403 } 404 } 405 return v; 406 } 407 408 public static boolean multiplicationOverflows(long a, long b, int bits) { 409 assert bits <= 64 && bits >= 0; 410 long result = a * b; 411 // result is positive if the sign is the same 412 boolean positive = (a >= 0 && b >= 0) || (a < 0 && b < 0); 413 if (bits == 64) { 414 if (a > 0 && b > 0) { 415 return a > 0x7FFFFFFF_FFFFFFFFL / b; 416 } else if (a > 0 && b <= 0) { 417 return b < 0x80000000_00000000L / a; 418 } else if (a <= 0 && b > 0) { 419 return a < 0x80000000_00000000L / b; 420 } else { 421 // a<=0 && b <=0 422 return a != 0 && b < 0x7FFFFFFF_FFFFFFFFL / a; 423 } 424 } else { 425 if (positive) { 426 return result > CodeUtil.maxValue(bits); 427 } else { 428 return result < CodeUtil.minValue(bits); 429 } 430 } 431 } 432 433 public static boolean subtractionCanOverflow(IntegerStamp x, IntegerStamp y) { 434 assert x.getBits() == y.getBits(); 435 // Checkstyle: stop 436 long x_l = x.lowerBound(); 437 long x_h = x.upperBound(); 438 long y_l = y.lowerBound(); 439 long y_h = y.upperBound(); 440 // Checkstyle: resume 441 return subtractionOverflows(x_l, y_h, x.getBits()) || subtractionOverflows(x_h, y_l, x.getBits()); 442 } 443 444 public static boolean subtractionOverflows(long x, long y, int bits) { 445 long result = x - y; 446 if (bits == 64) { 447 return (((x ^ y) & (x ^ result)) < 0); 448 } 449 return result < CodeUtil.minValue(bits) || result > CodeUtil.maxValue(bits); 450 } 451 452 public static final ArithmeticOpTable OPS = new ArithmeticOpTable( 453 454 new UnaryOp.Neg() { 455 456 @Override 457 public Constant foldConstant(Constant value) { 458 PrimitiveConstant c = (PrimitiveConstant) value; 459 return JavaConstant.forIntegerKind(c.getJavaKind(), -c.asLong()); 460 } 461 462 @Override 463 public Stamp foldStamp(Stamp s) { 464 IntegerStamp stamp = (IntegerStamp) s; 465 int bits = stamp.getBits(); 466 if (stamp.lowerBound() != CodeUtil.minValue(bits)) { 467 // TODO(ls) check if the mask calculation is correct... 468 return StampFactory.forInteger(bits, -stamp.upperBound(), -stamp.lowerBound()); 469 } else { 470 return stamp.unrestricted(); 471 } 472 } 473 }, 474 475 new BinaryOp.Add(true, true) { 476 477 @Override 478 public Constant foldConstant(Constant const1, Constant const2) { 479 PrimitiveConstant a = (PrimitiveConstant) const1; 480 PrimitiveConstant b = (PrimitiveConstant) const2; 481 assert a.getJavaKind() == b.getJavaKind(); 482 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() + b.asLong()); 483 } 484 485 @Override 486 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) { 487 IntegerStamp a = (IntegerStamp) stamp1; 488 IntegerStamp b = (IntegerStamp) stamp2; 489 490 int bits = a.getBits(); 491 assert bits == b.getBits(); 492 493 if (a.isUnrestricted()) { 494 return a; 495 } else if (b.isUnrestricted()) { 496 return b; 497 } 498 long defaultMask = CodeUtil.mask(bits); 499 long variableBits = (a.downMask() ^ a.upMask()) | (b.downMask() ^ b.upMask()); 500 long variableBitsWithCarry = variableBits | (carryBits(a.downMask(), b.downMask()) ^ carryBits(a.upMask(), b.upMask())); 501 long newDownMask = (a.downMask() + b.downMask()) & ~variableBitsWithCarry; 502 long newUpMask = (a.downMask() + b.downMask()) | variableBitsWithCarry; 503 504 newDownMask &= defaultMask; 505 newUpMask &= defaultMask; 506 507 long newLowerBound; 508 long newUpperBound; 509 boolean lowerOverflowsPositively = addOverflowsPositively(a.lowerBound(), b.lowerBound(), bits); 510 boolean upperOverflowsPositively = addOverflowsPositively(a.upperBound(), b.upperBound(), bits); 511 boolean lowerOverflowsNegatively = addOverflowsNegatively(a.lowerBound(), b.lowerBound(), bits); 512 boolean upperOverflowsNegatively = addOverflowsNegatively(a.upperBound(), b.upperBound(), bits); 513 if ((lowerOverflowsNegatively && !upperOverflowsNegatively) || (!lowerOverflowsPositively && upperOverflowsPositively)) { 514 newLowerBound = CodeUtil.minValue(bits); 515 newUpperBound = CodeUtil.maxValue(bits); 516 } else { 517 newLowerBound = CodeUtil.signExtend((a.lowerBound() + b.lowerBound()) & defaultMask, bits); 518 newUpperBound = CodeUtil.signExtend((a.upperBound() + b.upperBound()) & defaultMask, bits); 519 } 520 IntegerStamp limit = StampFactory.forInteger(bits, newLowerBound, newUpperBound); 521 newUpMask &= limit.upMask(); 522 newUpperBound = CodeUtil.signExtend(newUpperBound & newUpMask, bits); 523 newDownMask |= limit.downMask(); 524 newLowerBound |= newDownMask; 525 return new IntegerStamp(bits, newLowerBound, newUpperBound, newDownMask, newUpMask); 526 } 527 528 @Override 529 public boolean isNeutral(Constant value) { 530 PrimitiveConstant n = (PrimitiveConstant) value; 531 return n.asLong() == 0; 532 } 533 }, 534 535 new BinaryOp.Sub(true, false) { 536 537 @Override 538 public Constant foldConstant(Constant const1, Constant const2) { 539 PrimitiveConstant a = (PrimitiveConstant) const1; 540 PrimitiveConstant b = (PrimitiveConstant) const2; 541 assert a.getJavaKind() == b.getJavaKind(); 542 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() - b.asLong()); 543 } 544 545 @Override 546 public Stamp foldStamp(Stamp a, Stamp b) { 547 return OPS.getAdd().foldStamp(a, OPS.getNeg().foldStamp(b)); 548 } 549 550 @Override 551 public boolean isNeutral(Constant value) { 552 PrimitiveConstant n = (PrimitiveConstant) value; 553 return n.asLong() == 0; 554 } 555 556 @Override 557 public Constant getZero(Stamp s) { 558 IntegerStamp stamp = (IntegerStamp) s; 559 return JavaConstant.forPrimitiveInt(stamp.getBits(), 0); 560 } 561 }, 562 563 new BinaryOp.Mul(true, true) { 564 565 @Override 566 public Constant foldConstant(Constant const1, Constant const2) { 567 PrimitiveConstant a = (PrimitiveConstant) const1; 568 PrimitiveConstant b = (PrimitiveConstant) const2; 569 assert a.getJavaKind() == b.getJavaKind(); 570 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() * b.asLong()); 571 } 572 573 @Override 574 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) { 575 IntegerStamp a = (IntegerStamp) stamp1; 576 IntegerStamp b = (IntegerStamp) stamp2; 577 578 int bits = a.getBits(); 579 assert bits == b.getBits(); 580 // if a==0 or b==0 result of a*b is always 0 581 if (a.upMask() == 0) { 582 return a; 583 } else if (b.upMask() == 0) { 584 return b; 585 } else { 586 // if a has the full range or b, the result will also have it 587 if (a.isUnrestricted()) { 588 return a; 589 } else if (b.isUnrestricted()) { 590 return b; 591 } 592 // a!=0 && b !=0 holds 593 long newLowerBound = Long.MAX_VALUE; 594 long newUpperBound = Long.MIN_VALUE; 595 /* 596 * Based on the signs of the incoming stamps lower and upper bound 597 * of the result of the multiplication may be swapped. LowerBound 598 * can become upper bound if both signs are negative, and so on. To 599 * determine the new values for lower and upper bound we need to 600 * look at the max and min of the cases blow: 601 * 602 * @formatter:off 603 * 604 * a.lowerBound * b.lowerBound 605 * a.lowerBound * b.upperBound 606 * a.upperBound * b.lowerBound 607 * a.upperBound * b.upperBound 608 * 609 * @formatter:on 610 * 611 * We are only interested in those cases that are relevant due to 612 * the sign of the involved stamps (whether a stamp includes 613 * negative and / or positive values). Based on the signs, the maximum 614 * or minimum of the above multiplications form the new lower and 615 * upper bounds. 616 * 617 * The table below contains the interesting candidates for lower and 618 * upper bound after multiplication. 619 * 620 * For example if we consider two stamps a & b that both contain 621 * negative and positive values, the product of minN_a * minN_b 622 * (both the smallest negative value for each stamp) can only be the 623 * highest positive number. The other candidates can be computed in 624 * a similar fashion. Some of them can never be a new minimum or 625 * maximum and are therefore excluded. 626 * 627 * 628 * @formatter:off 629 * 630 * [x..........0..........y] 631 * ------------------------- 632 * [minN maxN minP maxP] 633 * where maxN = min(0,y) && minP = max(0,x) 634 * 635 * 636 * |minN_a maxN_a minP_a maxP_a 637 * _______|________________________________ 638 * minN_b |MAX / : / MIN 639 * maxN_b | / MIN : MAX / 640 * |---------------+---------------- 641 * minP_b | / MAX : MIN / 642 * maxP_b |MIN / : / MAX 643 * 644 * @formatter:on 645 */ 646 // We materialize all factors here. If they are needed, the signs of 647 // the stamp will ensure the correct value is used. 648 // Checkstyle: stop 649 long minN_a = a.lowerBound(); 650 long maxN_a = Math.min(0, a.upperBound()); 651 long minP_a = Math.max(0, a.lowerBound()); 652 long maxP_a = a.upperBound(); 653 654 long minN_b = b.lowerBound(); 655 long maxN_b = Math.min(0, b.upperBound()); 656 long minP_b = Math.max(0, b.lowerBound()); 657 long maxP_b = b.upperBound(); 658 // Checkstyle: resume 659 660 // multiplication has shift semantics 661 long newUpMask = ~CodeUtil.mask(Long.numberOfTrailingZeros(a.upMask) + Long.numberOfTrailingZeros(b.upMask)) & CodeUtil.mask(bits); 662 663 if (a.canBePositive()) { 664 if (b.canBePositive()) { 665 if (multiplicationOverflows(maxP_a, maxP_b, bits)) { 666 return a.unrestricted(); 667 } 668 long maxCandidate = maxP_a * maxP_b; 669 if (multiplicationOverflows(minP_a, minP_b, bits)) { 670 return a.unrestricted(); 671 } 672 long minCandidate = minP_a * minP_b; 673 newLowerBound = Math.min(newLowerBound, minCandidate); 674 newUpperBound = Math.max(newUpperBound, maxCandidate); 675 } 676 if (b.canBeNegative()) { 677 if (multiplicationOverflows(minP_a, maxN_b, bits)) { 678 return a.unrestricted(); 679 } 680 long maxCandidate = minP_a * maxN_b; 681 if (multiplicationOverflows(maxP_a, minN_b, bits)) { 682 return a.unrestricted(); 683 } 684 long minCandidate = maxP_a * minN_b; 685 newLowerBound = Math.min(newLowerBound, minCandidate); 686 newUpperBound = Math.max(newUpperBound, maxCandidate); 687 } 688 } 689 if (a.canBeNegative()) { 690 if (b.canBePositive()) { 691 if (multiplicationOverflows(maxN_a, minP_b, bits)) { 692 return a.unrestricted(); 693 } 694 long maxCandidate = maxN_a * minP_b; 695 if (multiplicationOverflows(minN_a, maxP_b, bits)) { 696 return a.unrestricted(); 697 } 698 long minCandidate = minN_a * maxP_b; 699 newLowerBound = Math.min(newLowerBound, minCandidate); 700 newUpperBound = Math.max(newUpperBound, maxCandidate); 701 } 702 if (b.canBeNegative()) { 703 if (multiplicationOverflows(minN_a, minN_b, bits)) { 704 return a.unrestricted(); 705 } 706 long maxCandidate = minN_a * minN_b; 707 if (multiplicationOverflows(maxN_a, maxN_b, bits)) { 708 return a.unrestricted(); 709 } 710 long minCandidate = maxN_a * maxN_b; 711 newLowerBound = Math.min(newLowerBound, minCandidate); 712 newUpperBound = Math.max(newUpperBound, maxCandidate); 713 } 714 } 715 716 assert newLowerBound <= newUpperBound; 717 return StampFactory.forIntegerWithMask(bits, newLowerBound, newUpperBound, 0, newUpMask); 718 } 719 } 720 721 @Override 722 public boolean isNeutral(Constant value) { 723 PrimitiveConstant n = (PrimitiveConstant) value; 724 return n.asLong() == 1; 725 } 726 }, 727 728 new BinaryOp.Div(true, false) { 729 730 @Override 731 public Constant foldConstant(Constant const1, Constant const2) { 732 PrimitiveConstant a = (PrimitiveConstant) const1; 733 PrimitiveConstant b = (PrimitiveConstant) const2; 734 assert a.getJavaKind() == b.getJavaKind(); 735 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() / b.asLong()); 736 } 737 738 @Override 739 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) { 740 IntegerStamp a = (IntegerStamp) stamp1; 741 IntegerStamp b = (IntegerStamp) stamp2; 742 assert a.getBits() == b.getBits(); 743 if (b.isStrictlyPositive()) { 744 long newLowerBound = a.lowerBound() / b.upperBound(); 745 long newUpperBound = a.upperBound() / b.lowerBound(); 746 return StampFactory.forInteger(a.getBits(), newLowerBound, newUpperBound); 747 } else { 748 return a.unrestricted(); 749 } 750 } 751 752 @Override 753 public boolean isNeutral(Constant value) { 754 PrimitiveConstant n = (PrimitiveConstant) value; 755 return n.asLong() == 1; 756 } 757 }, 758 759 new BinaryOp.Rem(false, false) { 760 761 @Override 762 public Constant foldConstant(Constant const1, Constant const2) { 763 PrimitiveConstant a = (PrimitiveConstant) const1; 764 PrimitiveConstant b = (PrimitiveConstant) const2; 765 assert a.getJavaKind() == b.getJavaKind(); 766 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() % b.asLong()); 767 } 768 769 @Override 770 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) { 771 IntegerStamp a = (IntegerStamp) stamp1; 772 IntegerStamp b = (IntegerStamp) stamp2; 773 assert a.getBits() == b.getBits(); 774 // zero is always possible 775 long newLowerBound = Math.min(a.lowerBound(), 0); 776 long newUpperBound = Math.max(a.upperBound(), 0); 777 778 /* the maximum absolute value of the result, derived from b */ 779 long magnitude; 780 if (b.lowerBound() == CodeUtil.minValue(b.getBits())) { 781 // Math.abs(...) - 1 does not work in a case 782 magnitude = CodeUtil.maxValue(b.getBits()); 783 } else { 784 magnitude = Math.max(Math.abs(b.lowerBound()), Math.abs(b.upperBound())) - 1; 785 } 786 newLowerBound = Math.max(newLowerBound, -magnitude); 787 newUpperBound = Math.min(newUpperBound, magnitude); 788 789 return StampFactory.forInteger(a.getBits(), newLowerBound, newUpperBound); 790 } 791 }, 792 793 new UnaryOp.Not() { 794 795 @Override 796 public Constant foldConstant(Constant c) { 797 PrimitiveConstant value = (PrimitiveConstant) c; 798 return JavaConstant.forIntegerKind(value.getJavaKind(), ~value.asLong()); 799 } 800 801 @Override 802 public Stamp foldStamp(Stamp stamp) { 803 IntegerStamp integerStamp = (IntegerStamp) stamp; 804 int bits = integerStamp.getBits(); 805 long defaultMask = CodeUtil.mask(bits); 806 return new IntegerStamp(bits, ~integerStamp.upperBound(), ~integerStamp.lowerBound(), (~integerStamp.upMask()) & defaultMask, (~integerStamp.downMask()) & defaultMask); 807 } 808 }, 809 810 new BinaryOp.And(true, true) { 811 812 @Override 813 public Constant foldConstant(Constant const1, Constant const2) { 814 PrimitiveConstant a = (PrimitiveConstant) const1; 815 PrimitiveConstant b = (PrimitiveConstant) const2; 816 assert a.getJavaKind() == b.getJavaKind(); 817 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() & b.asLong()); 818 } 819 820 @Override 821 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) { 822 IntegerStamp a = (IntegerStamp) stamp1; 823 IntegerStamp b = (IntegerStamp) stamp2; 824 assert a.getBits() == b.getBits(); 825 return stampForMask(a.getBits(), a.downMask() & b.downMask(), a.upMask() & b.upMask()); 826 } 827 828 @Override 829 public boolean isNeutral(Constant value) { 830 PrimitiveConstant n = (PrimitiveConstant) value; 831 int bits = n.getJavaKind().getBitCount(); 832 long mask = CodeUtil.mask(bits); 833 return (n.asLong() & mask) == mask; 834 } 835 }, 836 837 new BinaryOp.Or(true, true) { 838 839 @Override 840 public Constant foldConstant(Constant const1, Constant const2) { 841 PrimitiveConstant a = (PrimitiveConstant) const1; 842 PrimitiveConstant b = (PrimitiveConstant) const2; 843 assert a.getJavaKind() == b.getJavaKind(); 844 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() | b.asLong()); 845 } 846 847 @Override 848 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) { 849 IntegerStamp a = (IntegerStamp) stamp1; 850 IntegerStamp b = (IntegerStamp) stamp2; 851 assert a.getBits() == b.getBits(); 852 return stampForMask(a.getBits(), a.downMask() | b.downMask(), a.upMask() | b.upMask()); 853 } 854 855 @Override 856 public boolean isNeutral(Constant value) { 857 PrimitiveConstant n = (PrimitiveConstant) value; 858 return n.asLong() == 0; 859 } 860 }, 861 862 new BinaryOp.Xor(true, true) { 863 864 @Override 865 public Constant foldConstant(Constant const1, Constant const2) { 866 PrimitiveConstant a = (PrimitiveConstant) const1; 867 PrimitiveConstant b = (PrimitiveConstant) const2; 868 assert a.getJavaKind() == b.getJavaKind(); 869 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() ^ b.asLong()); 870 } 871 872 @Override 873 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) { 874 IntegerStamp a = (IntegerStamp) stamp1; 875 IntegerStamp b = (IntegerStamp) stamp2; 876 assert a.getBits() == b.getBits(); 877 878 long variableBits = (a.downMask() ^ a.upMask()) | (b.downMask() ^ b.upMask()); 879 long newDownMask = (a.downMask() ^ b.downMask()) & ~variableBits; 880 long newUpMask = (a.downMask() ^ b.downMask()) | variableBits; 881 return stampForMask(a.getBits(), newDownMask, newUpMask); 882 } 883 884 @Override 885 public boolean isNeutral(Constant value) { 886 PrimitiveConstant n = (PrimitiveConstant) value; 887 return n.asLong() == 0; 888 } 889 890 @Override 891 public Constant getZero(Stamp s) { 892 IntegerStamp stamp = (IntegerStamp) s; 893 return JavaConstant.forPrimitiveInt(stamp.getBits(), 0); 894 } 895 }, 896 897 new ShiftOp.Shl() { 898 899 @Override 900 public Constant foldConstant(Constant value, int amount) { 901 PrimitiveConstant c = (PrimitiveConstant) value; 902 switch (c.getJavaKind()) { 903 case Int: 904 return JavaConstant.forInt(c.asInt() << amount); 905 case Long: 906 return JavaConstant.forLong(c.asLong() << amount); 907 default: 908 throw GraalError.shouldNotReachHere(); 909 } 910 } 911 912 @Override 913 public Stamp foldStamp(Stamp stamp, IntegerStamp shift) { 914 IntegerStamp value = (IntegerStamp) stamp; 915 int bits = value.getBits(); 916 long defaultMask = CodeUtil.mask(bits); 917 if (value.upMask() == 0) { 918 return value; 919 } 920 int shiftMask = getShiftAmountMask(stamp); 921 int shiftBits = Integer.bitCount(shiftMask); 922 if (shift.lowerBound() == shift.upperBound()) { 923 int shiftAmount = (int) (shift.lowerBound() & shiftMask); 924 if (shiftAmount == 0) { 925 return value; 926 } 927 // the mask of bits that will be lost or shifted into the sign bit 928 long removedBits = -1L << (bits - shiftAmount - 1); 929 if ((value.lowerBound() & removedBits) == 0 && (value.upperBound() & removedBits) == 0) { 930 /* 931 * use a better stamp if neither lower nor upper bound can lose 932 * bits 933 */ 934 return new IntegerStamp(bits, value.lowerBound() << shiftAmount, value.upperBound() << shiftAmount, value.downMask() << shiftAmount, value.upMask() << shiftAmount); 935 } 936 } 937 if ((shift.lowerBound() >>> shiftBits) == (shift.upperBound() >>> shiftBits)) { 938 long downMask = defaultMask; 939 long upMask = 0; 940 for (long i = shift.lowerBound(); i <= shift.upperBound(); i++) { 941 if (shift.contains(i)) { 942 downMask &= value.downMask() << (i & shiftMask); 943 upMask |= value.upMask() << (i & shiftMask); 944 } 945 } 946 Stamp result = IntegerStamp.stampForMask(bits, downMask, upMask & defaultMask); 947 return result; 948 } 949 return value.unrestricted(); 950 } 951 952 @Override 953 public int getShiftAmountMask(Stamp s) { 954 IntegerStamp stamp = (IntegerStamp) s; 955 assert CodeUtil.isPowerOf2(stamp.getBits()); 956 return stamp.getBits() - 1; 957 } 958 }, 959 960 new ShiftOp.Shr() { 961 962 @Override 963 public Constant foldConstant(Constant value, int amount) { 964 PrimitiveConstant c = (PrimitiveConstant) value; 965 switch (c.getJavaKind()) { 966 case Int: 967 return JavaConstant.forInt(c.asInt() >> amount); 968 case Long: 969 return JavaConstant.forLong(c.asLong() >> amount); 970 default: 971 throw GraalError.shouldNotReachHere(); 972 } 973 } 974 975 @Override 976 public Stamp foldStamp(Stamp stamp, IntegerStamp shift) { 977 IntegerStamp value = (IntegerStamp) stamp; 978 int bits = value.getBits(); 979 if (shift.lowerBound() == shift.upperBound()) { 980 long shiftCount = shift.lowerBound() & getShiftAmountMask(stamp); 981 if (shiftCount == 0) { 982 return stamp; 983 } 984 985 int extraBits = 64 - bits; 986 long defaultMask = CodeUtil.mask(bits); 987 // shifting back and forth performs sign extension 988 long downMask = (value.downMask() << extraBits) >> (shiftCount + extraBits) & defaultMask; 989 long upMask = (value.upMask() << extraBits) >> (shiftCount + extraBits) & defaultMask; 990 return new IntegerStamp(bits, value.lowerBound() >> shiftCount, value.upperBound() >> shiftCount, downMask, upMask); 991 } 992 long mask = IntegerStamp.upMaskFor(bits, value.lowerBound(), value.upperBound()); 993 return IntegerStamp.stampForMask(bits, 0, mask); 994 } 995 996 @Override 997 public int getShiftAmountMask(Stamp s) { 998 IntegerStamp stamp = (IntegerStamp) s; 999 assert CodeUtil.isPowerOf2(stamp.getBits()); 1000 return stamp.getBits() - 1; 1001 } 1002 }, 1003 1004 new ShiftOp.UShr() { 1005 1006 @Override 1007 public Constant foldConstant(Constant value, int amount) { 1008 PrimitiveConstant c = (PrimitiveConstant) value; 1009 switch (c.getJavaKind()) { 1010 case Int: 1011 return JavaConstant.forInt(c.asInt() >>> amount); 1012 case Long: 1013 return JavaConstant.forLong(c.asLong() >>> amount); 1014 default: 1015 throw GraalError.shouldNotReachHere(); 1016 } 1017 } 1018 1019 @Override 1020 public Stamp foldStamp(Stamp stamp, IntegerStamp shift) { 1021 IntegerStamp value = (IntegerStamp) stamp; 1022 int bits = value.getBits(); 1023 if (shift.lowerBound() == shift.upperBound()) { 1024 long shiftCount = shift.lowerBound() & getShiftAmountMask(stamp); 1025 if (shiftCount == 0) { 1026 return stamp; 1027 } 1028 1029 long downMask = value.downMask() >>> shiftCount; 1030 long upMask = value.upMask() >>> shiftCount; 1031 if (value.lowerBound() < 0) { 1032 return new IntegerStamp(bits, downMask, upMask, downMask, upMask); 1033 } else { 1034 return new IntegerStamp(bits, value.lowerBound() >>> shiftCount, value.upperBound() >>> shiftCount, downMask, upMask); 1035 } 1036 } 1037 long mask = IntegerStamp.upMaskFor(bits, value.lowerBound(), value.upperBound()); 1038 return IntegerStamp.stampForMask(bits, 0, mask); 1039 } 1040 1041 @Override 1042 public int getShiftAmountMask(Stamp s) { 1043 IntegerStamp stamp = (IntegerStamp) s; 1044 assert CodeUtil.isPowerOf2(stamp.getBits()); 1045 return stamp.getBits() - 1; 1046 } 1047 }, 1048 1049 new UnaryOp.Abs() { 1050 1051 @Override 1052 public Constant foldConstant(Constant value) { 1053 PrimitiveConstant c = (PrimitiveConstant) value; 1054 return JavaConstant.forIntegerKind(c.getJavaKind(), Math.abs(c.asLong())); 1055 } 1056 1057 @Override 1058 public Stamp foldStamp(Stamp input) { 1059 IntegerStamp stamp = (IntegerStamp) input; 1060 int bits = stamp.getBits(); 1061 if (stamp.lowerBound() == CodeUtil.minValue(bits)) { 1062 return input.unrestricted(); 1063 } else { 1064 long limit = Math.max(-stamp.lowerBound(), stamp.upperBound()); 1065 return StampFactory.forInteger(bits, 0, limit); 1066 } 1067 } 1068 }, 1069 1070 null, 1071 1072 new IntegerConvertOp.ZeroExtend() { 1073 1074 @Override 1075 public Constant foldConstant(int inputBits, int resultBits, Constant c) { 1076 PrimitiveConstant value = (PrimitiveConstant) c; 1077 return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.zeroExtend(value.asLong(), inputBits)); 1078 } 1079 1080 @Override 1081 public Stamp foldStamp(int inputBits, int resultBits, Stamp input) { 1082 IntegerStamp stamp = (IntegerStamp) input; 1083 assert inputBits == stamp.getBits(); 1084 assert inputBits <= resultBits; 1085 1086 long downMask = CodeUtil.zeroExtend(stamp.downMask(), inputBits); 1087 long upMask = CodeUtil.zeroExtend(stamp.upMask(), inputBits); 1088 1089 if (stamp.lowerBound() < 0 && stamp.upperBound() >= 0) { 1090 /* signed range including 0 and -1 */ 1091 /* 1092 * after sign extension, the whole range from 0 to MAX_INT is 1093 * possible 1094 */ 1095 return IntegerStamp.stampForMask(resultBits, downMask, upMask); 1096 } 1097 1098 long lowerBound = CodeUtil.zeroExtend(stamp.lowerBound(), inputBits); 1099 long upperBound = CodeUtil.zeroExtend(stamp.upperBound(), inputBits); 1100 1101 return new IntegerStamp(resultBits, lowerBound, upperBound, downMask, upMask); 1102 } 1103 }, 1104 1105 new IntegerConvertOp.SignExtend() { 1106 1107 @Override 1108 public Constant foldConstant(int inputBits, int resultBits, Constant c) { 1109 PrimitiveConstant value = (PrimitiveConstant) c; 1110 return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.signExtend(value.asLong(), inputBits)); 1111 } 1112 1113 @Override 1114 public Stamp foldStamp(int inputBits, int resultBits, Stamp input) { 1115 IntegerStamp stamp = (IntegerStamp) input; 1116 assert inputBits == stamp.getBits(); 1117 assert inputBits <= resultBits; 1118 1119 long defaultMask = CodeUtil.mask(resultBits); 1120 long downMask = CodeUtil.signExtend(stamp.downMask(), inputBits) & defaultMask; 1121 long upMask = CodeUtil.signExtend(stamp.upMask(), inputBits) & defaultMask; 1122 1123 return new IntegerStamp(resultBits, stamp.lowerBound(), stamp.upperBound(), downMask, upMask); 1124 } 1125 }, 1126 1127 new IntegerConvertOp.Narrow() { 1128 1129 @Override 1130 public Constant foldConstant(int inputBits, int resultBits, Constant c) { 1131 PrimitiveConstant value = (PrimitiveConstant) c; 1132 return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.narrow(value.asLong(), resultBits)); 1133 } 1134 1135 @Override 1136 public Stamp foldStamp(int inputBits, int resultBits, Stamp input) { 1137 IntegerStamp stamp = (IntegerStamp) input; 1138 assert inputBits == stamp.getBits(); 1139 assert resultBits <= inputBits; 1140 if (resultBits == inputBits) { 1141 return stamp; 1142 } 1143 1144 final long upperBound; 1145 if (stamp.lowerBound() < CodeUtil.minValue(resultBits)) { 1146 upperBound = CodeUtil.maxValue(resultBits); 1147 } else { 1148 upperBound = saturate(stamp.upperBound(), resultBits); 1149 } 1150 final long lowerBound; 1151 if (stamp.upperBound() > CodeUtil.maxValue(resultBits)) { 1152 lowerBound = CodeUtil.minValue(resultBits); 1153 } else { 1154 lowerBound = saturate(stamp.lowerBound(), resultBits); 1155 } 1156 1157 long defaultMask = CodeUtil.mask(resultBits); 1158 long newDownMask = stamp.downMask() & defaultMask; 1159 long newUpMask = stamp.upMask() & defaultMask; 1160 long newLowerBound = CodeUtil.signExtend((lowerBound | newDownMask) & newUpMask, resultBits); 1161 long newUpperBound = CodeUtil.signExtend((upperBound | newDownMask) & newUpMask, resultBits); 1162 return new IntegerStamp(resultBits, newLowerBound, newUpperBound, newDownMask, newUpMask); 1163 } 1164 }, 1165 1166 new FloatConvertOp(I2F) { 1167 1168 @Override 1169 public Constant foldConstant(Constant c) { 1170 PrimitiveConstant value = (PrimitiveConstant) c; 1171 return JavaConstant.forFloat(value.asInt()); 1172 } 1173 1174 @Override 1175 public Stamp foldStamp(Stamp input) { 1176 IntegerStamp stamp = (IntegerStamp) input; 1177 assert stamp.getBits() == 32; 1178 float lowerBound = stamp.lowerBound(); 1179 float upperBound = stamp.upperBound(); 1180 return StampFactory.forFloat(JavaKind.Float, lowerBound, upperBound, true); 1181 } 1182 }, 1183 1184 new FloatConvertOp(L2F) { 1185 1186 @Override 1187 public Constant foldConstant(Constant c) { 1188 PrimitiveConstant value = (PrimitiveConstant) c; 1189 return JavaConstant.forFloat(value.asLong()); 1190 } 1191 1192 @Override 1193 public Stamp foldStamp(Stamp input) { 1194 IntegerStamp stamp = (IntegerStamp) input; 1195 assert stamp.getBits() == 64; 1196 float lowerBound = stamp.lowerBound(); 1197 float upperBound = stamp.upperBound(); 1198 return StampFactory.forFloat(JavaKind.Float, lowerBound, upperBound, true); 1199 } 1200 }, 1201 1202 new FloatConvertOp(I2D) { 1203 1204 @Override 1205 public Constant foldConstant(Constant c) { 1206 PrimitiveConstant value = (PrimitiveConstant) c; 1207 return JavaConstant.forDouble(value.asInt()); 1208 } 1209 1210 @Override 1211 public Stamp foldStamp(Stamp input) { 1212 IntegerStamp stamp = (IntegerStamp) input; 1213 assert stamp.getBits() == 32; 1214 double lowerBound = stamp.lowerBound(); 1215 double upperBound = stamp.upperBound(); 1216 return StampFactory.forFloat(JavaKind.Double, lowerBound, upperBound, true); 1217 } 1218 }, 1219 1220 new FloatConvertOp(L2D) { 1221 1222 @Override 1223 public Constant foldConstant(Constant c) { 1224 PrimitiveConstant value = (PrimitiveConstant) c; 1225 return JavaConstant.forDouble(value.asLong()); 1226 } 1227 1228 @Override 1229 public Stamp foldStamp(Stamp input) { 1230 IntegerStamp stamp = (IntegerStamp) input; 1231 assert stamp.getBits() == 64; 1232 double lowerBound = stamp.lowerBound(); 1233 double upperBound = stamp.upperBound(); 1234 return StampFactory.forFloat(JavaKind.Double, lowerBound, upperBound, true); 1235 } 1236 }); 1237} 1238