1 /*
   2  * Copyright (c) 2012, 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 
  24 
  25 package org.graalvm.compiler.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();
 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                         @Override
1302                         public Stamp foldStamp(Stamp stamp, IntegerStamp shift) {
1303                             IntegerStamp value = (IntegerStamp) stamp;
1304                             int bits = value.getBits();
1305                             if (value.isEmpty()) {
1306                                 return value;
1307                             } else if (shift.isEmpty()) {
1308                                 return StampFactory.forInteger(bits).empty();
1309                             } else if (value.upMask() == 0) {
1310                                 return value;
1311                             }
1312 
1313                             int shiftMask = getShiftAmountMask(stamp);
1314                             int shiftBits = Integer.bitCount(shiftMask);
1315                             if (shift.lowerBound() == shift.upperBound()) {
1316                                 int shiftAmount = (int) (shift.lowerBound() & shiftMask);
1317                                 if (shiftAmount == 0) {
1318                                     return value;
1319                                 }
1320                                 // the mask of bits that will be lost or shifted into the sign bit
1321                                 long removedBits = -1L << (bits - shiftAmount - 1);
1322                                 if ((value.lowerBound() & removedBits) == 0 && (value.upperBound() & removedBits) == 0) {
1323                                     /*
1324                                      * use a better stamp if neither lower nor upper bound can lose
1325                                      * bits
1326                                      */
1327                                     return new IntegerStamp(bits, value.lowerBound() << shiftAmount, value.upperBound() << shiftAmount, value.downMask() << shiftAmount, value.upMask() << shiftAmount);
1328                                 }
1329                             }
1330                             if ((shift.lowerBound() >>> shiftBits) == (shift.upperBound() >>> shiftBits)) {
1331                                 long defaultMask = CodeUtil.mask(bits);
1332                                 long downMask = defaultMask;
1333                                 long upMask = 0;
1334                                 for (long i = shift.lowerBound(); i <= shift.upperBound(); i++) {
1335                                     if (shift.contains(i)) {
1336                                         downMask &= value.downMask() << (i & shiftMask);
1337                                         upMask |= value.upMask() << (i & shiftMask);
1338                                     }
1339                                 }
1340                                 return IntegerStamp.stampForMask(bits, downMask, upMask & defaultMask);
1341                             }
1342                             return value.unrestricted();
1343                         }
1344 
1345                         @Override
1346                         public int getShiftAmountMask(Stamp s) {
1347                             IntegerStamp stamp = (IntegerStamp) s;
1348                             assert CodeUtil.isPowerOf2(stamp.getBits());
1349                             return stamp.getBits() - 1;
1350                         }
1351                     },
1352 
1353                     new ShiftOp.Shr() {
1354 
1355                         @Override
1356                         public Constant foldConstant(Constant value, int amount) {
1357                             PrimitiveConstant c = (PrimitiveConstant) value;
1358                             switch (c.getJavaKind()) {
1359                                 case Int:
1360                                     return JavaConstant.forInt(c.asInt() >> amount);
1361                                 case Long:
1362                                     return JavaConstant.forLong(c.asLong() >> amount);
1363                                 default:
1364                                     throw GraalError.shouldNotReachHere();
1365                             }
1366                         }
1367 
1368                         @Override
1369                         public Stamp foldStamp(Stamp stamp, IntegerStamp shift) {
1370                             IntegerStamp value = (IntegerStamp) stamp;
1371                             int bits = value.getBits();
1372                             if (value.isEmpty()) {
1373                                 return value;
1374                             } else if (shift.isEmpty()) {
1375                                 return StampFactory.forInteger(bits).empty();
1376                             } else if (shift.lowerBound() == shift.upperBound()) {
1377                                 long shiftCount = shift.lowerBound() & getShiftAmountMask(stamp);
1378                                 if (shiftCount == 0) {
1379                                     return stamp;
1380                                 }
1381 
1382                                 int extraBits = 64 - bits;
1383                                 long defaultMask = CodeUtil.mask(bits);
1384                                 // shifting back and forth performs sign extension
1385                                 long downMask = (value.downMask() << extraBits) >> (shiftCount + extraBits) & defaultMask;
1386                                 long upMask = (value.upMask() << extraBits) >> (shiftCount + extraBits) & defaultMask;
1387                                 return new IntegerStamp(bits, value.lowerBound() >> shiftCount, value.upperBound() >> shiftCount, downMask, upMask);
1388                             }
1389                             long mask = IntegerStamp.upMaskFor(bits, value.lowerBound(), value.upperBound());
1390                             return IntegerStamp.stampForMask(bits, 0, mask);
1391                         }
1392 
1393                         @Override
1394                         public int getShiftAmountMask(Stamp s) {
1395                             IntegerStamp stamp = (IntegerStamp) s;
1396                             assert CodeUtil.isPowerOf2(stamp.getBits());
1397                             return stamp.getBits() - 1;
1398                         }
1399                     },
1400 
1401                     new ShiftOp.UShr() {
1402 
1403                         @Override
1404                         public Constant foldConstant(Constant value, int amount) {
1405                             PrimitiveConstant c = (PrimitiveConstant) value;
1406                             switch (c.getJavaKind()) {
1407                                 case Int:
1408                                     return JavaConstant.forInt(c.asInt() >>> amount);
1409                                 case Long:
1410                                     return JavaConstant.forLong(c.asLong() >>> amount);
1411                                 default:
1412                                     throw GraalError.shouldNotReachHere();
1413                             }
1414                         }
1415 
1416                         @Override
1417                         public Stamp foldStamp(Stamp stamp, IntegerStamp shift) {
1418                             IntegerStamp value = (IntegerStamp) stamp;
1419                             int bits = value.getBits();
1420                             if (value.isEmpty()) {
1421                                 return value;
1422                             } else if (shift.isEmpty()) {
1423                                 return StampFactory.forInteger(bits).empty();
1424                             }
1425 
1426                             if (shift.lowerBound() == shift.upperBound()) {
1427                                 long shiftCount = shift.lowerBound() & getShiftAmountMask(stamp);
1428                                 if (shiftCount == 0) {
1429                                     return stamp;
1430                                 }
1431 
1432                                 long downMask = value.downMask() >>> shiftCount;
1433                                 long upMask = value.upMask() >>> shiftCount;
1434                                 if (value.lowerBound() < 0) {
1435                                     return new IntegerStamp(bits, downMask, upMask, downMask, upMask);
1436                                 } else {
1437                                     return new IntegerStamp(bits, value.lowerBound() >>> shiftCount, value.upperBound() >>> shiftCount, downMask, upMask);
1438                                 }
1439                             }
1440                             long mask = IntegerStamp.upMaskFor(bits, value.lowerBound(), value.upperBound());
1441                             return IntegerStamp.stampForMask(bits, 0, mask);
1442                         }
1443 
1444                         @Override
1445                         public int getShiftAmountMask(Stamp s) {
1446                             IntegerStamp stamp = (IntegerStamp) s;
1447                             assert CodeUtil.isPowerOf2(stamp.getBits());
1448                             return stamp.getBits() - 1;
1449                         }
1450                     },
1451 
1452                     new UnaryOp.Abs() {
1453 
1454                         @Override
1455                         public Constant foldConstant(Constant value) {
1456                             PrimitiveConstant c = (PrimitiveConstant) value;
1457                             return JavaConstant.forIntegerKind(c.getJavaKind(), Math.abs(c.asLong()));
1458                         }
1459 
1460                         @Override
1461                         public Stamp foldStamp(Stamp input) {
1462                             if (input.isEmpty()) {
1463                                 return input;
1464                             }
1465                             IntegerStamp stamp = (IntegerStamp) input;
1466                             int bits = stamp.getBits();
1467                             if (stamp.lowerBound == stamp.upperBound) {
1468                                 long value = CodeUtil.convert(Math.abs(stamp.lowerBound()), stamp.getBits(), false);
1469                                 return StampFactory.forInteger(stamp.getBits(), value, value);
1470                             }
1471                             if (stamp.lowerBound() == CodeUtil.minValue(bits)) {
1472                                 return input.unrestricted();
1473                             } else {
1474                                 long limit = Math.max(-stamp.lowerBound(), stamp.upperBound());
1475                                 return StampFactory.forInteger(bits, 0, limit);
1476                             }
1477                         }
1478                     },
1479 
1480                     null,
1481 
1482                     new IntegerConvertOp.ZeroExtend() {
1483 
1484                         @Override
1485                         public Constant foldConstant(int inputBits, int resultBits, Constant c) {
1486                             PrimitiveConstant value = (PrimitiveConstant) c;
1487                             return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.zeroExtend(value.asLong(), inputBits));
1488                         }
1489 
1490                         @Override
1491                         public Stamp foldStamp(int inputBits, int resultBits, Stamp input) {
1492                             if (input.isEmpty()) {
1493                                 return StampFactory.forInteger(resultBits).empty();
1494                             }
1495                             IntegerStamp stamp = (IntegerStamp) input;
1496                             assert inputBits == stamp.getBits();
1497                             assert inputBits <= resultBits;
1498 
1499                             if (inputBits == resultBits) {
1500                                 return input;
1501                             }
1502 
1503                             if (input.isEmpty()) {
1504                                 return StampFactory.forInteger(resultBits).empty();
1505                             }
1506 
1507                             long downMask = CodeUtil.zeroExtend(stamp.downMask(), inputBits);
1508                             long upMask = CodeUtil.zeroExtend(stamp.upMask(), inputBits);
1509                             long lowerBound = stamp.unsignedLowerBound();
1510                             long upperBound = stamp.unsignedUpperBound();
1511                             return IntegerStamp.create(resultBits, lowerBound, upperBound, downMask, upMask);
1512                         }
1513 
1514                         @Override
1515                         public Stamp invertStamp(int inputBits, int resultBits, Stamp outStamp) {
1516                             IntegerStamp stamp = (IntegerStamp) outStamp;
1517                             if (stamp.isEmpty()) {
1518                                 return StampFactory.forInteger(inputBits).empty();
1519                             }
1520                             return StampFactory.forUnsignedInteger(inputBits, stamp.lowerBound(), stamp.upperBound(), stamp.downMask(), stamp.upMask());
1521                         }
1522                     },
1523 
1524                     new IntegerConvertOp.SignExtend() {
1525 
1526                         @Override
1527                         public Constant foldConstant(int inputBits, int resultBits, Constant c) {
1528                             PrimitiveConstant value = (PrimitiveConstant) c;
1529                             return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.signExtend(value.asLong(), inputBits));
1530                         }
1531 
1532                         @Override
1533                         public Stamp foldStamp(int inputBits, int resultBits, Stamp input) {
1534                             if (input.isEmpty()) {
1535                                 return StampFactory.forInteger(resultBits).empty();
1536                             }
1537                             IntegerStamp stamp = (IntegerStamp) input;
1538                             assert inputBits == stamp.getBits();
1539                             assert inputBits <= resultBits;
1540 
1541                             long defaultMask = CodeUtil.mask(resultBits);
1542                             long downMask = CodeUtil.signExtend(stamp.downMask(), inputBits) & defaultMask;
1543                             long upMask = CodeUtil.signExtend(stamp.upMask(), inputBits) & defaultMask;
1544 
1545                             return new IntegerStamp(resultBits, stamp.lowerBound(), stamp.upperBound(), downMask, upMask);
1546                         }
1547 
1548                         @Override
1549                         public Stamp invertStamp(int inputBits, int resultBits, Stamp outStamp) {
1550                             if (outStamp.isEmpty()) {
1551                                 return StampFactory.forInteger(inputBits).empty();
1552                             }
1553                             IntegerStamp stamp = (IntegerStamp) outStamp;
1554                             long mask = CodeUtil.mask(inputBits);
1555                             return StampFactory.forIntegerWithMask(inputBits, stamp.lowerBound(), stamp.upperBound(), stamp.downMask() & mask, stamp.upMask() & mask);
1556                         }
1557                     },
1558 
1559                     new IntegerConvertOp.Narrow() {
1560 
1561                         @Override
1562                         public Constant foldConstant(int inputBits, int resultBits, Constant c) {
1563                             PrimitiveConstant value = (PrimitiveConstant) c;
1564                             return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.narrow(value.asLong(), resultBits));
1565                         }
1566 
1567                         @Override
1568                         public Stamp foldStamp(int inputBits, int resultBits, Stamp input) {
1569                             if (input.isEmpty()) {
1570                                 return StampFactory.forInteger(resultBits).empty();
1571                             }
1572                             IntegerStamp stamp = (IntegerStamp) input;
1573                             assert inputBits == stamp.getBits();
1574                             assert resultBits <= inputBits;
1575                             if (resultBits == inputBits) {
1576                                 return stamp;
1577                             }
1578 
1579                             final long upperBound;
1580                             if (stamp.lowerBound() < CodeUtil.minValue(resultBits)) {
1581                                 upperBound = CodeUtil.maxValue(resultBits);
1582                             } else {
1583                                 upperBound = saturate(stamp.upperBound(), resultBits);
1584                             }
1585                             final long lowerBound;
1586                             if (stamp.upperBound() > CodeUtil.maxValue(resultBits)) {
1587                                 lowerBound = CodeUtil.minValue(resultBits);
1588                             } else {
1589                                 lowerBound = saturate(stamp.lowerBound(), resultBits);
1590                             }
1591 
1592                             long defaultMask = CodeUtil.mask(resultBits);
1593                             long newDownMask = stamp.downMask() & defaultMask;
1594                             long newUpMask = stamp.upMask() & defaultMask;
1595                             long newLowerBound = CodeUtil.signExtend((lowerBound | newDownMask) & newUpMask, resultBits);
1596                             long newUpperBound = CodeUtil.signExtend((upperBound | newDownMask) & newUpMask, resultBits);
1597                             return new IntegerStamp(resultBits, newLowerBound, newUpperBound, newDownMask, newUpMask);
1598                         }
1599                     },
1600 
1601                     new FloatConvertOp(I2F) {
1602 
1603                         @Override
1604                         public Constant foldConstant(Constant c) {
1605                             PrimitiveConstant value = (PrimitiveConstant) c;
1606                             return JavaConstant.forFloat(value.asInt());
1607                         }
1608 
1609                         @Override
1610                         public Stamp foldStamp(Stamp input) {
1611                             if (input.isEmpty()) {
1612                                 return StampFactory.empty(JavaKind.Float);
1613                             }
1614                             IntegerStamp stamp = (IntegerStamp) input;
1615                             assert stamp.getBits() == 32;
1616                             float lowerBound = stamp.lowerBound();
1617                             float upperBound = stamp.upperBound();
1618                             return StampFactory.forFloat(JavaKind.Float, lowerBound, upperBound, true);
1619                         }
1620                     },
1621 
1622                     new FloatConvertOp(L2F) {
1623 
1624                         @Override
1625                         public Constant foldConstant(Constant c) {
1626                             PrimitiveConstant value = (PrimitiveConstant) c;
1627                             return JavaConstant.forFloat(value.asLong());
1628                         }
1629 
1630                         @Override
1631                         public Stamp foldStamp(Stamp input) {
1632                             if (input.isEmpty()) {
1633                                 return StampFactory.empty(JavaKind.Float);
1634                             }
1635                             IntegerStamp stamp = (IntegerStamp) input;
1636                             assert stamp.getBits() == 64;
1637                             float lowerBound = stamp.lowerBound();
1638                             float upperBound = stamp.upperBound();
1639                             return StampFactory.forFloat(JavaKind.Float, lowerBound, upperBound, true);
1640                         }
1641                     },
1642 
1643                     new FloatConvertOp(I2D) {
1644 
1645                         @Override
1646                         public Constant foldConstant(Constant c) {
1647                             PrimitiveConstant value = (PrimitiveConstant) c;
1648                             return JavaConstant.forDouble(value.asInt());
1649                         }
1650 
1651                         @Override
1652                         public Stamp foldStamp(Stamp input) {
1653                             if (input.isEmpty()) {
1654                                 return StampFactory.empty(JavaKind.Double);
1655                             }
1656                             IntegerStamp stamp = (IntegerStamp) input;
1657                             assert stamp.getBits() == 32;
1658                             double lowerBound = stamp.lowerBound();
1659                             double upperBound = stamp.upperBound();
1660                             return StampFactory.forFloat(JavaKind.Double, lowerBound, upperBound, true);
1661                         }
1662                     },
1663 
1664                     new FloatConvertOp(L2D) {
1665 
1666                         @Override
1667                         public Constant foldConstant(Constant c) {
1668                             PrimitiveConstant value = (PrimitiveConstant) c;
1669                             return JavaConstant.forDouble(value.asLong());
1670                         }
1671 
1672                         @Override
1673                         public Stamp foldStamp(Stamp input) {
1674                             if (input.isEmpty()) {
1675                                 return StampFactory.empty(JavaKind.Double);
1676                             }
1677                             IntegerStamp stamp = (IntegerStamp) input;
1678                             assert stamp.getBits() == 64;
1679                             double lowerBound = stamp.lowerBound();
1680                             double upperBound = stamp.upperBound();
1681                             return StampFactory.forFloat(JavaKind.Double, lowerBound, upperBound, true);
1682                         }
1683                     });
1684 }