--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/jdk.internal.vm.compiler/share/classes/org.graalvm.compiler.core.common/src/org/graalvm/compiler/core/common/type/IntegerStamp.java Tue Sep 12 19:03:39 2017 +0200
@@ -0,0 +1,1556 @@
+/*
+ * Copyright (c) 2012, 2015, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ */
+package org.graalvm.compiler.core.common.type;
+
+import static org.graalvm.compiler.core.common.calc.FloatConvert.I2D;
+import static org.graalvm.compiler.core.common.calc.FloatConvert.I2F;
+import static org.graalvm.compiler.core.common.calc.FloatConvert.L2D;
+import static org.graalvm.compiler.core.common.calc.FloatConvert.L2F;
+
+import java.nio.ByteBuffer;
+import java.util.Formatter;
+
+import org.graalvm.compiler.core.common.LIRKind;
+import org.graalvm.compiler.core.common.NumUtil;
+import org.graalvm.compiler.core.common.spi.LIRKindTool;
+import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp;
+import org.graalvm.compiler.core.common.type.ArithmeticOpTable.FloatConvertOp;
+import org.graalvm.compiler.core.common.type.ArithmeticOpTable.IntegerConvertOp;
+import org.graalvm.compiler.core.common.type.ArithmeticOpTable.ShiftOp;
+import org.graalvm.compiler.core.common.type.ArithmeticOpTable.UnaryOp;
+import org.graalvm.compiler.debug.GraalError;
+
+import jdk.vm.ci.code.CodeUtil;
+import jdk.vm.ci.meta.Constant;
+import jdk.vm.ci.meta.JavaConstant;
+import jdk.vm.ci.meta.JavaKind;
+import jdk.vm.ci.meta.MetaAccessProvider;
+import jdk.vm.ci.meta.PrimitiveConstant;
+import jdk.vm.ci.meta.ResolvedJavaType;
+import jdk.vm.ci.meta.SerializableConstant;
+
+/**
+ * Describes the possible values of a node that produces an int or long result.
+ *
+ * The description consists of (inclusive) lower and upper bounds and up (may be set) and down
+ * (always set) bit-masks.
+ */
+public final class IntegerStamp extends PrimitiveStamp {
+
+ private final long lowerBound;
+ private final long upperBound;
+ private final long downMask;
+ private final long upMask;
+
+ private IntegerStamp(int bits, long lowerBound, long upperBound, long downMask, long upMask) {
+ super(bits, OPS);
+
+ this.lowerBound = lowerBound;
+ this.upperBound = upperBound;
+ this.downMask = downMask;
+ this.upMask = upMask;
+
+ assert lowerBound >= CodeUtil.minValue(bits) : this;
+ assert upperBound <= CodeUtil.maxValue(bits) : this;
+ assert (downMask & CodeUtil.mask(bits)) == downMask : this;
+ assert (upMask & CodeUtil.mask(bits)) == upMask : this;
+ }
+
+ public static IntegerStamp create(int bits, long lowerBoundInput, long upperBoundInput) {
+ return create(bits, lowerBoundInput, upperBoundInput, 0, CodeUtil.mask(bits));
+ }
+
+ public static IntegerStamp create(int bits, long lowerBoundInput, long upperBoundInput, long downMask, long upMask) {
+ assert (downMask & ~upMask) == 0 : String.format("\u21ca: %016x \u21c8: %016x", downMask, upMask);
+
+ // Set lower bound, use masks to make it more precise
+ long minValue = minValueForMasks(bits, downMask, upMask);
+ long lowerBoundTmp = Math.max(lowerBoundInput, minValue);
+
+ // Set upper bound, use masks to make it more precise
+ long maxValue = maxValueForMasks(bits, downMask, upMask);
+ long upperBoundTmp = Math.min(upperBoundInput, maxValue);
+
+ // Assign masks now with the bounds in mind.
+ final long boundedDownMask;
+ final long boundedUpMask;
+ long defaultMask = CodeUtil.mask(bits);
+ if (lowerBoundTmp == upperBoundTmp) {
+ boundedDownMask = lowerBoundTmp;
+ boundedUpMask = lowerBoundTmp;
+ } else if (lowerBoundTmp >= 0) {
+ int upperBoundLeadingZeros = Long.numberOfLeadingZeros(upperBoundTmp);
+ long differentBits = lowerBoundTmp ^ upperBoundTmp;
+ int sameBitCount = Long.numberOfLeadingZeros(differentBits << upperBoundLeadingZeros);
+
+ boundedUpMask = upperBoundTmp | -1L >>> (upperBoundLeadingZeros + sameBitCount);
+ boundedDownMask = upperBoundTmp & ~(-1L >>> (upperBoundLeadingZeros + sameBitCount));
+ } else {
+ if (upperBoundTmp >= 0) {
+ boundedUpMask = defaultMask;
+ boundedDownMask = 0;
+ } else {
+ int lowerBoundLeadingOnes = Long.numberOfLeadingZeros(~lowerBoundTmp);
+ long differentBits = lowerBoundTmp ^ upperBoundTmp;
+ int sameBitCount = Long.numberOfLeadingZeros(differentBits << lowerBoundLeadingOnes);
+
+ boundedUpMask = lowerBoundTmp | -1L >>> (lowerBoundLeadingOnes + sameBitCount) | ~(-1L >>> lowerBoundLeadingOnes);
+ boundedDownMask = lowerBoundTmp & ~(-1L >>> (lowerBoundLeadingOnes + sameBitCount)) | ~(-1L >>> lowerBoundLeadingOnes);
+ }
+ }
+
+ return new IntegerStamp(bits, lowerBoundTmp, upperBoundTmp, defaultMask & (downMask | boundedDownMask), defaultMask & upMask & boundedUpMask);
+ }
+
+ static long significantBit(long bits, long value) {
+ return (value >>> (bits - 1)) & 1;
+ }
+
+ static long minValueForMasks(int bits, long downMask, long upMask) {
+ if (significantBit(bits, upMask) == 0) {
+ // Value is always positive. Minimum value always positive.
+ assert significantBit(bits, downMask) == 0;
+ return downMask;
+ } else {
+ // Value can be positive or negative. Minimum value always negative.
+ return downMask | (-1L << (bits - 1));
+ }
+ }
+
+ static long maxValueForMasks(int bits, long downMask, long upMask) {
+ if (significantBit(bits, downMask) == 1) {
+ // Value is always negative. Maximum value always negative.
+ assert significantBit(bits, upMask) == 1;
+ return CodeUtil.signExtend(upMask, bits);
+ } else {
+ // Value can be positive or negative. Maximum value always positive.
+ return upMask & (CodeUtil.mask(bits) >>> 1);
+ }
+ }
+
+ public static IntegerStamp stampForMask(int bits, long downMask, long upMask) {
+ return new IntegerStamp(bits, minValueForMasks(bits, downMask, upMask), maxValueForMasks(bits, downMask, upMask), downMask, upMask);
+ }
+
+ @Override
+ public IntegerStamp unrestricted() {
+ return new IntegerStamp(getBits(), CodeUtil.minValue(getBits()), CodeUtil.maxValue(getBits()), 0, CodeUtil.mask(getBits()));
+ }
+
+ @Override
+ public IntegerStamp empty() {
+ return new IntegerStamp(getBits(), CodeUtil.maxValue(getBits()), CodeUtil.minValue(getBits()), CodeUtil.mask(getBits()), 0);
+ }
+
+ @Override
+ public Stamp constant(Constant c, MetaAccessProvider meta) {
+ if (c instanceof PrimitiveConstant) {
+ long value = ((PrimitiveConstant) c).asLong();
+ return StampFactory.forInteger(getBits(), value, value);
+ }
+ return this;
+ }
+
+ @Override
+ public SerializableConstant deserialize(ByteBuffer buffer) {
+ switch (getBits()) {
+ case 1:
+ return JavaConstant.forBoolean(buffer.get() != 0);
+ case 8:
+ return JavaConstant.forByte(buffer.get());
+ case 16:
+ return JavaConstant.forShort(buffer.getShort());
+ case 32:
+ return JavaConstant.forInt(buffer.getInt());
+ case 64:
+ return JavaConstant.forLong(buffer.getLong());
+ default:
+ throw GraalError.shouldNotReachHere();
+ }
+ }
+
+ @Override
+ public boolean hasValues() {
+ return lowerBound <= upperBound;
+ }
+
+ @Override
+ public JavaKind getStackKind() {
+ if (getBits() > 32) {
+ return JavaKind.Long;
+ } else {
+ return JavaKind.Int;
+ }
+ }
+
+ @Override
+ public LIRKind getLIRKind(LIRKindTool tool) {
+ return tool.getIntegerKind(getBits());
+ }
+
+ @Override
+ public ResolvedJavaType javaType(MetaAccessProvider metaAccess) {
+ switch (getBits()) {
+ case 1:
+ return metaAccess.lookupJavaType(Boolean.TYPE);
+ case 8:
+ return metaAccess.lookupJavaType(Byte.TYPE);
+ case 16:
+ return metaAccess.lookupJavaType(Short.TYPE);
+ case 32:
+ return metaAccess.lookupJavaType(Integer.TYPE);
+ case 64:
+ return metaAccess.lookupJavaType(Long.TYPE);
+ default:
+ throw GraalError.shouldNotReachHere();
+ }
+ }
+
+ /**
+ * The signed inclusive lower bound on the value described by this stamp.
+ */
+ public long lowerBound() {
+ return lowerBound;
+ }
+
+ /**
+ * The signed inclusive upper bound on the value described by this stamp.
+ */
+ public long upperBound() {
+ return upperBound;
+ }
+
+ /**
+ * This bit-mask describes the bits that are always set in the value described by this stamp.
+ */
+ public long downMask() {
+ return downMask;
+ }
+
+ /**
+ * This bit-mask describes the bits that can be set in the value described by this stamp.
+ */
+ public long upMask() {
+ return upMask;
+ }
+
+ @Override
+ public boolean isUnrestricted() {
+ return lowerBound == CodeUtil.minValue(getBits()) && upperBound == CodeUtil.maxValue(getBits()) && downMask == 0 && upMask == CodeUtil.mask(getBits());
+ }
+
+ public boolean contains(long value) {
+ return value >= lowerBound && value <= upperBound && (value & downMask) == downMask && (value & upMask) == (value & CodeUtil.mask(getBits()));
+ }
+
+ public boolean isPositive() {
+ return lowerBound() >= 0;
+ }
+
+ public boolean isNegative() {
+ return upperBound() <= 0;
+ }
+
+ public boolean isStrictlyPositive() {
+ return lowerBound() > 0;
+ }
+
+ public boolean isStrictlyNegative() {
+ return upperBound() < 0;
+ }
+
+ public boolean canBePositive() {
+ return upperBound() > 0;
+ }
+
+ public boolean canBeNegative() {
+ return lowerBound() < 0;
+ }
+
+ @Override
+ public String toString() {
+ StringBuilder str = new StringBuilder();
+ str.append('i');
+ str.append(getBits());
+ if (hasValues()) {
+ if (lowerBound == upperBound) {
+ str.append(" [").append(lowerBound).append(']');
+ } else if (lowerBound != CodeUtil.minValue(getBits()) || upperBound != CodeUtil.maxValue(getBits())) {
+ str.append(" [").append(lowerBound).append(" - ").append(upperBound).append(']');
+ }
+ if (downMask != 0) {
+ str.append(" \u21ca");
+ new Formatter(str).format("%016x", downMask);
+ }
+ if (upMask != CodeUtil.mask(getBits())) {
+ str.append(" \u21c8");
+ new Formatter(str).format("%016x", upMask);
+ }
+ } else {
+ str.append("<empty>");
+ }
+ return str.toString();
+ }
+
+ private IntegerStamp createStamp(IntegerStamp other, long newUpperBound, long newLowerBound, long newDownMask, long newUpMask) {
+ assert getBits() == other.getBits();
+ if (newLowerBound > newUpperBound || (newDownMask & (~newUpMask)) != 0 || (newUpMask == 0 && (newLowerBound > 0 || newUpperBound < 0))) {
+ return empty();
+ } else if (newLowerBound == lowerBound && newUpperBound == upperBound && newDownMask == downMask && newUpMask == upMask) {
+ return this;
+ } else if (newLowerBound == other.lowerBound && newUpperBound == other.upperBound && newDownMask == other.downMask && newUpMask == other.upMask) {
+ return other;
+ } else {
+ return IntegerStamp.create(getBits(), newLowerBound, newUpperBound, newDownMask, newUpMask);
+ }
+ }
+
+ @Override
+ public Stamp meet(Stamp otherStamp) {
+ if (otherStamp == this) {
+ return this;
+ }
+ IntegerStamp other = (IntegerStamp) otherStamp;
+ return createStamp(other, Math.max(upperBound, other.upperBound), Math.min(lowerBound, other.lowerBound), downMask & other.downMask, upMask | other.upMask);
+ }
+
+ @Override
+ public IntegerStamp join(Stamp otherStamp) {
+ if (otherStamp == this) {
+ return this;
+ }
+ IntegerStamp other = (IntegerStamp) otherStamp;
+ long newDownMask = downMask | other.downMask;
+ long newLowerBound = Math.max(lowerBound, other.lowerBound);
+ long newUpperBound = Math.min(upperBound, other.upperBound);
+ long newUpMask = upMask & other.upMask;
+ return createStamp(other, newUpperBound, newLowerBound, newDownMask, newUpMask);
+ }
+
+ @Override
+ public boolean isCompatible(Stamp stamp) {
+ if (this == stamp) {
+ return true;
+ }
+ if (stamp instanceof IntegerStamp) {
+ IntegerStamp other = (IntegerStamp) stamp;
+ return getBits() == other.getBits();
+ }
+ return false;
+ }
+
+ @Override
+ public boolean isCompatible(Constant constant) {
+ if (constant instanceof PrimitiveConstant) {
+ PrimitiveConstant prim = (PrimitiveConstant) constant;
+ return prim.getJavaKind().isNumericInteger();
+ }
+ return false;
+ }
+
+ public long unsignedUpperBound() {
+ if (sameSignBounds()) {
+ return CodeUtil.zeroExtend(upperBound(), getBits());
+ }
+ return NumUtil.maxValueUnsigned(getBits());
+ }
+
+ public long unsignedLowerBound() {
+ if (sameSignBounds()) {
+ return CodeUtil.zeroExtend(lowerBound(), getBits());
+ }
+ return 0;
+ }
+
+ private boolean sameSignBounds() {
+ return NumUtil.sameSign(lowerBound, upperBound);
+ }
+
+ @Override
+ public int hashCode() {
+ final int prime = 31;
+ int result = 1;
+ result = prime * result + super.hashCode();
+ result = prime * result + (int) (lowerBound ^ (lowerBound >>> 32));
+ result = prime * result + (int) (upperBound ^ (upperBound >>> 32));
+ result = prime * result + (int) (downMask ^ (downMask >>> 32));
+ result = prime * result + (int) (upMask ^ (upMask >>> 32));
+ return result;
+ }
+
+ @Override
+ public boolean equals(Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj == null || getClass() != obj.getClass() || !super.equals(obj)) {
+ return false;
+ }
+ IntegerStamp other = (IntegerStamp) obj;
+ if (lowerBound != other.lowerBound || upperBound != other.upperBound || downMask != other.downMask || upMask != other.upMask) {
+ return false;
+ }
+ return super.equals(other);
+ }
+
+ public static long upMaskFor(int bits, long lowerBound, long upperBound) {
+ long mask = lowerBound | upperBound;
+ if (mask == 0) {
+ return 0;
+ } else {
+ return ((-1L) >>> Long.numberOfLeadingZeros(mask)) & CodeUtil.mask(bits);
+ }
+ }
+
+ /**
+ * Checks if the 2 stamps represent values of the same sign. Returns true if the two stamps are
+ * both positive of null or if they are both strictly negative
+ *
+ * @return true if the two stamps are both positive of null or if they are both strictly
+ * negative
+ */
+ public static boolean sameSign(IntegerStamp s1, IntegerStamp s2) {
+ return s1.isPositive() && s2.isPositive() || s1.isStrictlyNegative() && s2.isStrictlyNegative();
+ }
+
+ @Override
+ public JavaConstant asConstant() {
+ if (lowerBound == upperBound) {
+ switch (getBits()) {
+ case 1:
+ return JavaConstant.forBoolean(lowerBound != 0);
+ case 8:
+ return JavaConstant.forByte((byte) lowerBound);
+ case 16:
+ return JavaConstant.forShort((short) lowerBound);
+ case 32:
+ return JavaConstant.forInt((int) lowerBound);
+ case 64:
+ return JavaConstant.forLong(lowerBound);
+ }
+ }
+ return null;
+ }
+
+ public static boolean addCanOverflow(IntegerStamp a, IntegerStamp b) {
+ assert a.getBits() == b.getBits();
+ return addOverflowsPositively(a.upperBound(), b.upperBound(), a.getBits()) ||
+ addOverflowsNegatively(a.lowerBound(), b.lowerBound(), a.getBits());
+
+ }
+
+ public static boolean addOverflowsPositively(long x, long y, int bits) {
+ long result = x + y;
+ if (bits == 64) {
+ return (~x & ~y & result) < 0;
+ } else {
+ return result > CodeUtil.maxValue(bits);
+ }
+ }
+
+ public static boolean addOverflowsNegatively(long x, long y, int bits) {
+ long result = x + y;
+ if (bits == 64) {
+ return (x & y & ~result) < 0;
+ } else {
+ return result < CodeUtil.minValue(bits);
+ }
+ }
+
+ public static long carryBits(long x, long y) {
+ return (x + y) ^ x ^ y;
+ }
+
+ private static long saturate(long v, int bits) {
+ if (bits < 64) {
+ long max = CodeUtil.maxValue(bits);
+ if (v > max) {
+ return max;
+ }
+ long min = CodeUtil.minValue(bits);
+ if (v < min) {
+ return min;
+ }
+ }
+ return v;
+ }
+
+ public static boolean multiplicationOverflows(long a, long b, int bits) {
+ assert bits <= 64 && bits >= 0;
+ long result = a * b;
+ // result is positive if the sign is the same
+ boolean positive = (a >= 0 && b >= 0) || (a < 0 && b < 0);
+ if (bits == 64) {
+ if (a > 0 && b > 0) {
+ return a > 0x7FFFFFFF_FFFFFFFFL / b;
+ } else if (a > 0 && b <= 0) {
+ return b < 0x80000000_00000000L / a;
+ } else if (a <= 0 && b > 0) {
+ return a < 0x80000000_00000000L / b;
+ } else {
+ // a<=0 && b <=0
+ return a != 0 && b < 0x7FFFFFFF_FFFFFFFFL / a;
+ }
+ } else {
+ if (positive) {
+ return result > CodeUtil.maxValue(bits);
+ } else {
+ return result < CodeUtil.minValue(bits);
+ }
+ }
+ }
+
+ public static boolean multiplicationCanOverflow(IntegerStamp a, IntegerStamp b) {
+ // see IntegerStamp#foldStamp for details
+ assert a.getBits() == b.getBits();
+ if (a.upMask() == 0) {
+ return false;
+ } else if (b.upMask() == 0) {
+ return false;
+ }
+ if (a.isUnrestricted()) {
+ return true;
+ }
+ if (b.isUnrestricted()) {
+ return true;
+ }
+ int bits = a.getBits();
+ long minNegA = a.lowerBound();
+ long maxNegA = Math.min(0, a.upperBound());
+ long minPosA = Math.max(0, a.lowerBound());
+ long maxPosA = a.upperBound();
+
+ long minNegB = b.lowerBound();
+ long maxNegB = Math.min(0, b.upperBound());
+ long minPosB = Math.max(0, b.lowerBound());
+ long maxPosB = b.upperBound();
+
+ boolean mayOverflow = false;
+ if (a.canBePositive()) {
+ if (b.canBePositive()) {
+ mayOverflow |= IntegerStamp.multiplicationOverflows(maxPosA, maxPosB, bits);
+ mayOverflow |= IntegerStamp.multiplicationOverflows(minPosA, minPosB, bits);
+ }
+ if (b.canBeNegative()) {
+ mayOverflow |= IntegerStamp.multiplicationOverflows(minPosA, maxNegB, bits);
+ mayOverflow |= IntegerStamp.multiplicationOverflows(maxPosA, minNegB, bits);
+
+ }
+ }
+ if (a.canBeNegative()) {
+ if (b.canBePositive()) {
+ mayOverflow |= IntegerStamp.multiplicationOverflows(maxNegA, minPosB, bits);
+ mayOverflow |= IntegerStamp.multiplicationOverflows(minNegA, maxPosB, bits);
+ }
+ if (b.canBeNegative()) {
+ mayOverflow |= IntegerStamp.multiplicationOverflows(minNegA, minNegB, bits);
+ mayOverflow |= IntegerStamp.multiplicationOverflows(maxNegA, maxNegB, bits);
+ }
+ }
+ return mayOverflow;
+ }
+
+ public static boolean subtractionCanOverflow(IntegerStamp x, IntegerStamp y) {
+ assert x.getBits() == y.getBits();
+ return subtractionOverflows(x.lowerBound(), y.upperBound(), x.getBits()) || subtractionOverflows(x.upperBound(), y.lowerBound(), x.getBits());
+ }
+
+ public static boolean subtractionOverflows(long x, long y, int bits) {
+ long result = x - y;
+ if (bits == 64) {
+ return (((x ^ y) & (x ^ result)) < 0);
+ }
+ return result < CodeUtil.minValue(bits) || result > CodeUtil.maxValue(bits);
+ }
+
+ public static final ArithmeticOpTable OPS = new ArithmeticOpTable(
+
+ new UnaryOp.Neg() {
+
+ @Override
+ public Constant foldConstant(Constant value) {
+ PrimitiveConstant c = (PrimitiveConstant) value;
+ return JavaConstant.forIntegerKind(c.getJavaKind(), -c.asLong());
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp s) {
+ IntegerStamp stamp = (IntegerStamp) s;
+ int bits = stamp.getBits();
+ if (stamp.lowerBound() != CodeUtil.minValue(bits)) {
+ // TODO(ls) check if the mask calculation is correct...
+ return StampFactory.forInteger(bits, -stamp.upperBound(), -stamp.lowerBound());
+ } else {
+ return stamp.unrestricted();
+ }
+ }
+ },
+
+ new BinaryOp.Add(true, true) {
+
+ @Override
+ public Constant foldConstant(Constant const1, Constant const2) {
+ PrimitiveConstant a = (PrimitiveConstant) const1;
+ PrimitiveConstant b = (PrimitiveConstant) const2;
+ assert a.getJavaKind() == b.getJavaKind();
+ return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() + b.asLong());
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
+ IntegerStamp a = (IntegerStamp) stamp1;
+ IntegerStamp b = (IntegerStamp) stamp2;
+
+ int bits = a.getBits();
+ assert bits == b.getBits();
+
+ if (a.isUnrestricted()) {
+ return a;
+ } else if (b.isUnrestricted()) {
+ return b;
+ }
+ long defaultMask = CodeUtil.mask(bits);
+ long variableBits = (a.downMask() ^ a.upMask()) | (b.downMask() ^ b.upMask());
+ long variableBitsWithCarry = variableBits | (carryBits(a.downMask(), b.downMask()) ^ carryBits(a.upMask(), b.upMask()));
+ long newDownMask = (a.downMask() + b.downMask()) & ~variableBitsWithCarry;
+ long newUpMask = (a.downMask() + b.downMask()) | variableBitsWithCarry;
+
+ newDownMask &= defaultMask;
+ newUpMask &= defaultMask;
+
+ long newLowerBound;
+ long newUpperBound;
+ boolean lowerOverflowsPositively = addOverflowsPositively(a.lowerBound(), b.lowerBound(), bits);
+ boolean upperOverflowsPositively = addOverflowsPositively(a.upperBound(), b.upperBound(), bits);
+ boolean lowerOverflowsNegatively = addOverflowsNegatively(a.lowerBound(), b.lowerBound(), bits);
+ boolean upperOverflowsNegatively = addOverflowsNegatively(a.upperBound(), b.upperBound(), bits);
+ if ((lowerOverflowsNegatively && !upperOverflowsNegatively) || (!lowerOverflowsPositively && upperOverflowsPositively)) {
+ newLowerBound = CodeUtil.minValue(bits);
+ newUpperBound = CodeUtil.maxValue(bits);
+ } else {
+ newLowerBound = CodeUtil.signExtend((a.lowerBound() + b.lowerBound()) & defaultMask, bits);
+ newUpperBound = CodeUtil.signExtend((a.upperBound() + b.upperBound()) & defaultMask, bits);
+ }
+ IntegerStamp limit = StampFactory.forInteger(bits, newLowerBound, newUpperBound);
+ newUpMask &= limit.upMask();
+ newUpperBound = CodeUtil.signExtend(newUpperBound & newUpMask, bits);
+ newDownMask |= limit.downMask();
+ newLowerBound |= newDownMask;
+ return new IntegerStamp(bits, newLowerBound, newUpperBound, newDownMask, newUpMask);
+ }
+
+ @Override
+ public boolean isNeutral(Constant value) {
+ PrimitiveConstant n = (PrimitiveConstant) value;
+ return n.asLong() == 0;
+ }
+ },
+
+ new BinaryOp.Sub(true, false) {
+
+ @Override
+ public Constant foldConstant(Constant const1, Constant const2) {
+ PrimitiveConstant a = (PrimitiveConstant) const1;
+ PrimitiveConstant b = (PrimitiveConstant) const2;
+ assert a.getJavaKind() == b.getJavaKind();
+ return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() - b.asLong());
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp a, Stamp b) {
+ return OPS.getAdd().foldStamp(a, OPS.getNeg().foldStamp(b));
+ }
+
+ @Override
+ public boolean isNeutral(Constant value) {
+ PrimitiveConstant n = (PrimitiveConstant) value;
+ return n.asLong() == 0;
+ }
+
+ @Override
+ public Constant getZero(Stamp s) {
+ IntegerStamp stamp = (IntegerStamp) s;
+ return JavaConstant.forPrimitiveInt(stamp.getBits(), 0);
+ }
+ },
+
+ new BinaryOp.Mul(true, true) {
+
+ @Override
+ public Constant foldConstant(Constant const1, Constant const2) {
+ PrimitiveConstant a = (PrimitiveConstant) const1;
+ PrimitiveConstant b = (PrimitiveConstant) const2;
+ assert a.getJavaKind() == b.getJavaKind();
+ return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() * b.asLong());
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
+ IntegerStamp a = (IntegerStamp) stamp1;
+ IntegerStamp b = (IntegerStamp) stamp2;
+
+ int bits = a.getBits();
+ assert bits == b.getBits();
+ // if a==0 or b==0 result of a*b is always 0
+ if (a.upMask() == 0) {
+ return a;
+ } else if (b.upMask() == 0) {
+ return b;
+ } else {
+ // if a has the full range or b, the result will also have it
+ if (a.isUnrestricted()) {
+ return a;
+ } else if (b.isUnrestricted()) {
+ return b;
+ }
+ // a!=0 && b !=0 holds
+ long newLowerBound = Long.MAX_VALUE;
+ long newUpperBound = Long.MIN_VALUE;
+ /*
+ * Based on the signs of the incoming stamps lower and upper bound
+ * of the result of the multiplication may be swapped. LowerBound
+ * can become upper bound if both signs are negative, and so on. To
+ * determine the new values for lower and upper bound we need to
+ * look at the max and min of the cases blow:
+ *
+ * @formatter:off
+ *
+ * a.lowerBound * b.lowerBound
+ * a.lowerBound * b.upperBound
+ * a.upperBound * b.lowerBound
+ * a.upperBound * b.upperBound
+ *
+ * @formatter:on
+ *
+ * We are only interested in those cases that are relevant due to
+ * the sign of the involved stamps (whether a stamp includes
+ * negative and / or positive values). Based on the signs, the maximum
+ * or minimum of the above multiplications form the new lower and
+ * upper bounds.
+ *
+ * The table below contains the interesting candidates for lower and
+ * upper bound after multiplication.
+ *
+ * For example if we consider two stamps a & b that both contain
+ * negative and positive values, the product of minNegA * minNegB
+ * (both the smallest negative value for each stamp) can only be the
+ * highest positive number. The other candidates can be computed in
+ * a similar fashion. Some of them can never be a new minimum or
+ * maximum and are therefore excluded.
+ *
+ *
+ * @formatter:off
+ *
+ * [x................0................y]
+ * -------------------------------------
+ * [minNeg maxNeg minPos maxPos]
+ *
+ * where maxNeg = min(0,y) && minPos = max(0,x)
+ *
+ *
+ * |minNegA maxNegA minPosA maxPosA
+ * _______ |____________________________________
+ * minNegB | MAX / : / MIN
+ * maxNegB | / MIN : MAX /
+ * |------------------+-----------------
+ * minPosB | / MAX : MIN /
+ * maxPosB | MIN / : / MAX
+ *
+ * @formatter:on
+ */
+ // We materialize all factors here. If they are needed, the signs of
+ // the stamp will ensure the correct value is used.
+ long minNegA = a.lowerBound();
+ long maxNegA = Math.min(0, a.upperBound());
+ long minPosA = Math.max(0, a.lowerBound());
+ long maxPosA = a.upperBound();
+
+ long minNegB = b.lowerBound();
+ long maxNegB = Math.min(0, b.upperBound());
+ long minPosB = Math.max(0, b.lowerBound());
+ long maxPosB = b.upperBound();
+
+ // multiplication has shift semantics
+ long newUpMask = ~CodeUtil.mask(Long.numberOfTrailingZeros(a.upMask) + Long.numberOfTrailingZeros(b.upMask)) & CodeUtil.mask(bits);
+
+ if (a.canBePositive()) {
+ if (b.canBePositive()) {
+ if (multiplicationOverflows(maxPosA, maxPosB, bits)) {
+ return a.unrestricted();
+ }
+ long maxCandidate = maxPosA * maxPosB;
+ if (multiplicationOverflows(minPosA, minPosB, bits)) {
+ return a.unrestricted();
+ }
+ long minCandidate = minPosA * minPosB;
+ newLowerBound = Math.min(newLowerBound, minCandidate);
+ newUpperBound = Math.max(newUpperBound, maxCandidate);
+ }
+ if (b.canBeNegative()) {
+ if (multiplicationOverflows(minPosA, maxNegB, bits)) {
+ return a.unrestricted();
+ }
+ long maxCandidate = minPosA * maxNegB;
+ if (multiplicationOverflows(maxPosA, minNegB, bits)) {
+ return a.unrestricted();
+ }
+ long minCandidate = maxPosA * minNegB;
+ newLowerBound = Math.min(newLowerBound, minCandidate);
+ newUpperBound = Math.max(newUpperBound, maxCandidate);
+ }
+ }
+ if (a.canBeNegative()) {
+ if (b.canBePositive()) {
+ if (multiplicationOverflows(maxNegA, minPosB, bits)) {
+ return a.unrestricted();
+ }
+ long maxCandidate = maxNegA * minPosB;
+ if (multiplicationOverflows(minNegA, maxPosB, bits)) {
+ return a.unrestricted();
+ }
+ long minCandidate = minNegA * maxPosB;
+ newLowerBound = Math.min(newLowerBound, minCandidate);
+ newUpperBound = Math.max(newUpperBound, maxCandidate);
+ }
+ if (b.canBeNegative()) {
+ if (multiplicationOverflows(minNegA, minNegB, bits)) {
+ return a.unrestricted();
+ }
+ long maxCandidate = minNegA * minNegB;
+ if (multiplicationOverflows(maxNegA, maxNegB, bits)) {
+ return a.unrestricted();
+ }
+ long minCandidate = maxNegA * maxNegB;
+ newLowerBound = Math.min(newLowerBound, minCandidate);
+ newUpperBound = Math.max(newUpperBound, maxCandidate);
+ }
+ }
+
+ assert newLowerBound <= newUpperBound;
+ return StampFactory.forIntegerWithMask(bits, newLowerBound, newUpperBound, 0, newUpMask);
+ }
+ }
+
+ @Override
+ public boolean isNeutral(Constant value) {
+ PrimitiveConstant n = (PrimitiveConstant) value;
+ return n.asLong() == 1;
+ }
+ },
+
+ new BinaryOp.MulHigh(true, true) {
+
+ @Override
+ public Constant foldConstant(Constant const1, Constant const2) {
+ PrimitiveConstant a = (PrimitiveConstant) const1;
+ PrimitiveConstant b = (PrimitiveConstant) const2;
+ assert a.getJavaKind() == b.getJavaKind();
+ return JavaConstant.forIntegerKind(a.getJavaKind(), multiplyHigh(a.asLong(), b.asLong(), a.getJavaKind()));
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
+ IntegerStamp a = (IntegerStamp) stamp1;
+ IntegerStamp b = (IntegerStamp) stamp2;
+ JavaKind javaKind = a.getStackKind();
+
+ assert a.getBits() == b.getBits();
+ assert javaKind == b.getStackKind();
+ assert (javaKind == JavaKind.Int || javaKind == JavaKind.Long);
+
+ if (a.isEmpty() || b.isEmpty()) {
+ return a.empty();
+ } else if (a.isUnrestricted() || b.isUnrestricted()) {
+ return a.unrestricted();
+ }
+
+ long[] xExtremes = {a.lowerBound(), a.upperBound()};
+ long[] yExtremes = {b.lowerBound(), b.upperBound()};
+ long min = Long.MAX_VALUE;
+ long max = Long.MIN_VALUE;
+ for (long x : xExtremes) {
+ for (long y : yExtremes) {
+ long result = multiplyHigh(x, y, javaKind);
+ min = Math.min(min, result);
+ max = Math.max(max, result);
+ }
+ }
+ return StampFactory.forInteger(javaKind, min, max);
+ }
+
+ @Override
+ public boolean isNeutral(Constant value) {
+ return false;
+ }
+
+ private long multiplyHigh(long x, long y, JavaKind javaKind) {
+ if (javaKind == JavaKind.Int) {
+ return (x * y) >> 32;
+ } else {
+ assert javaKind == JavaKind.Long;
+ long x0 = x & 0xFFFFFFFFL;
+ long x1 = x >> 32;
+
+ long y0 = y & 0xFFFFFFFFL;
+ long y1 = y >> 32;
+
+ long z0 = x0 * y0;
+ long t = x1 * y0 + (z0 >>> 32);
+ long z1 = t & 0xFFFFFFFFL;
+ long z2 = t >> 32;
+ z1 += x0 * y1;
+
+ return x1 * y1 + z2 + (z1 >> 32);
+ }
+ }
+ },
+
+ new BinaryOp.UMulHigh(true, true) {
+
+ @Override
+ public Constant foldConstant(Constant const1, Constant const2) {
+ PrimitiveConstant a = (PrimitiveConstant) const1;
+ PrimitiveConstant b = (PrimitiveConstant) const2;
+ assert a.getJavaKind() == b.getJavaKind();
+ return JavaConstant.forIntegerKind(a.getJavaKind(), multiplyHighUnsigned(a.asLong(), b.asLong(), a.getJavaKind()));
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
+ IntegerStamp a = (IntegerStamp) stamp1;
+ IntegerStamp b = (IntegerStamp) stamp2;
+ JavaKind javaKind = a.getStackKind();
+
+ assert a.getBits() == b.getBits();
+ assert javaKind == b.getStackKind();
+ assert (javaKind == JavaKind.Int || javaKind == JavaKind.Long);
+
+ if (a.isEmpty() || b.isEmpty()) {
+ return a.empty();
+ } else if (a.isUnrestricted() || b.isUnrestricted()) {
+ return a.unrestricted();
+ }
+
+ // Note that the minima and maxima are calculated using signed min/max
+ // functions, while the values themselves are unsigned.
+ long[] xExtremes = getUnsignedExtremes(a);
+ long[] yExtremes = getUnsignedExtremes(b);
+ long min = Long.MAX_VALUE;
+ long max = Long.MIN_VALUE;
+ for (long x : xExtremes) {
+ for (long y : yExtremes) {
+ long result = multiplyHighUnsigned(x, y, javaKind);
+ min = Math.min(min, result);
+ max = Math.max(max, result);
+ }
+ }
+
+ // if min is negative, then the value can reach into the unsigned range
+ if (min == max || min >= 0) {
+ return StampFactory.forInteger(javaKind, min, max);
+ } else {
+ return StampFactory.forKind(javaKind);
+ }
+ }
+
+ @Override
+ public boolean isNeutral(Constant value) {
+ return false;
+ }
+
+ private long[] getUnsignedExtremes(IntegerStamp stamp) {
+ if (stamp.lowerBound() < 0 && stamp.upperBound() >= 0) {
+ /*
+ * If -1 and 0 are both in the signed range, then we can't say
+ * anything about the unsigned range, so we have to return [0,
+ * MAX_UNSIGNED].
+ */
+ return new long[]{0, -1L};
+ } else {
+ return new long[]{stamp.lowerBound(), stamp.upperBound()};
+ }
+ }
+
+ private long multiplyHighUnsigned(long x, long y, JavaKind javaKind) {
+ if (javaKind == JavaKind.Int) {
+ long xl = x & 0xFFFFFFFFL;
+ long yl = y & 0xFFFFFFFFL;
+ long r = xl * yl;
+ return (int) (r >>> 32);
+ } else {
+ assert javaKind == JavaKind.Long;
+ long x0 = x & 0xFFFFFFFFL;
+ long x1 = x >>> 32;
+
+ long y0 = y & 0xFFFFFFFFL;
+ long y1 = y >>> 32;
+
+ long z0 = x0 * y0;
+ long t = x1 * y0 + (z0 >>> 32);
+ long z1 = t & 0xFFFFFFFFL;
+ long z2 = t >>> 32;
+ z1 += x0 * y1;
+
+ return x1 * y1 + z2 + (z1 >>> 32);
+ }
+ }
+ },
+
+ new BinaryOp.Div(true, false) {
+
+ @Override
+ public Constant foldConstant(Constant const1, Constant const2) {
+ PrimitiveConstant a = (PrimitiveConstant) const1;
+ PrimitiveConstant b = (PrimitiveConstant) const2;
+ assert a.getJavaKind() == b.getJavaKind();
+ return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() / b.asLong());
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
+ IntegerStamp a = (IntegerStamp) stamp1;
+ IntegerStamp b = (IntegerStamp) stamp2;
+ assert a.getBits() == b.getBits();
+ if (b.isStrictlyPositive()) {
+ long newLowerBound = a.lowerBound() / b.upperBound();
+ long newUpperBound = a.upperBound() / b.lowerBound();
+ return StampFactory.forInteger(a.getBits(), newLowerBound, newUpperBound);
+ } else {
+ return a.unrestricted();
+ }
+ }
+
+ @Override
+ public boolean isNeutral(Constant value) {
+ PrimitiveConstant n = (PrimitiveConstant) value;
+ return n.asLong() == 1;
+ }
+ },
+
+ new BinaryOp.Rem(false, false) {
+
+ @Override
+ public Constant foldConstant(Constant const1, Constant const2) {
+ PrimitiveConstant a = (PrimitiveConstant) const1;
+ PrimitiveConstant b = (PrimitiveConstant) const2;
+ assert a.getJavaKind() == b.getJavaKind();
+ return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() % b.asLong());
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
+ IntegerStamp a = (IntegerStamp) stamp1;
+ IntegerStamp b = (IntegerStamp) stamp2;
+ assert a.getBits() == b.getBits();
+ // zero is always possible
+ long newLowerBound = Math.min(a.lowerBound(), 0);
+ long newUpperBound = Math.max(a.upperBound(), 0);
+
+ /* the maximum absolute value of the result, derived from b */
+ long magnitude;
+ if (b.lowerBound() == CodeUtil.minValue(b.getBits())) {
+ // Math.abs(...) - 1 does not work in a case
+ magnitude = CodeUtil.maxValue(b.getBits());
+ } else {
+ magnitude = Math.max(Math.abs(b.lowerBound()), Math.abs(b.upperBound())) - 1;
+ }
+ newLowerBound = Math.max(newLowerBound, -magnitude);
+ newUpperBound = Math.min(newUpperBound, magnitude);
+
+ return StampFactory.forInteger(a.getBits(), newLowerBound, newUpperBound);
+ }
+ },
+
+ new UnaryOp.Not() {
+
+ @Override
+ public Constant foldConstant(Constant c) {
+ PrimitiveConstant value = (PrimitiveConstant) c;
+ return JavaConstant.forIntegerKind(value.getJavaKind(), ~value.asLong());
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp stamp) {
+ IntegerStamp integerStamp = (IntegerStamp) stamp;
+ int bits = integerStamp.getBits();
+ long defaultMask = CodeUtil.mask(bits);
+ return new IntegerStamp(bits, ~integerStamp.upperBound(), ~integerStamp.lowerBound(), (~integerStamp.upMask()) & defaultMask, (~integerStamp.downMask()) & defaultMask);
+ }
+ },
+
+ new BinaryOp.And(true, true) {
+
+ @Override
+ public Constant foldConstant(Constant const1, Constant const2) {
+ PrimitiveConstant a = (PrimitiveConstant) const1;
+ PrimitiveConstant b = (PrimitiveConstant) const2;
+ assert a.getJavaKind() == b.getJavaKind();
+ return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() & b.asLong());
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
+ IntegerStamp a = (IntegerStamp) stamp1;
+ IntegerStamp b = (IntegerStamp) stamp2;
+ assert a.getBits() == b.getBits();
+ return stampForMask(a.getBits(), a.downMask() & b.downMask(), a.upMask() & b.upMask());
+ }
+
+ @Override
+ public boolean isNeutral(Constant value) {
+ PrimitiveConstant n = (PrimitiveConstant) value;
+ int bits = n.getJavaKind().getBitCount();
+ long mask = CodeUtil.mask(bits);
+ return (n.asLong() & mask) == mask;
+ }
+ },
+
+ new BinaryOp.Or(true, true) {
+
+ @Override
+ public Constant foldConstant(Constant const1, Constant const2) {
+ PrimitiveConstant a = (PrimitiveConstant) const1;
+ PrimitiveConstant b = (PrimitiveConstant) const2;
+ assert a.getJavaKind() == b.getJavaKind();
+ return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() | b.asLong());
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
+ IntegerStamp a = (IntegerStamp) stamp1;
+ IntegerStamp b = (IntegerStamp) stamp2;
+ assert a.getBits() == b.getBits();
+ return stampForMask(a.getBits(), a.downMask() | b.downMask(), a.upMask() | b.upMask());
+ }
+
+ @Override
+ public boolean isNeutral(Constant value) {
+ PrimitiveConstant n = (PrimitiveConstant) value;
+ return n.asLong() == 0;
+ }
+ },
+
+ new BinaryOp.Xor(true, true) {
+
+ @Override
+ public Constant foldConstant(Constant const1, Constant const2) {
+ PrimitiveConstant a = (PrimitiveConstant) const1;
+ PrimitiveConstant b = (PrimitiveConstant) const2;
+ assert a.getJavaKind() == b.getJavaKind();
+ return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() ^ b.asLong());
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
+ IntegerStamp a = (IntegerStamp) stamp1;
+ IntegerStamp b = (IntegerStamp) stamp2;
+ assert a.getBits() == b.getBits();
+
+ long variableBits = (a.downMask() ^ a.upMask()) | (b.downMask() ^ b.upMask());
+ long newDownMask = (a.downMask() ^ b.downMask()) & ~variableBits;
+ long newUpMask = (a.downMask() ^ b.downMask()) | variableBits;
+ return stampForMask(a.getBits(), newDownMask, newUpMask);
+ }
+
+ @Override
+ public boolean isNeutral(Constant value) {
+ PrimitiveConstant n = (PrimitiveConstant) value;
+ return n.asLong() == 0;
+ }
+
+ @Override
+ public Constant getZero(Stamp s) {
+ IntegerStamp stamp = (IntegerStamp) s;
+ return JavaConstant.forPrimitiveInt(stamp.getBits(), 0);
+ }
+ },
+
+ new ShiftOp.Shl() {
+
+ @Override
+ public Constant foldConstant(Constant value, int amount) {
+ PrimitiveConstant c = (PrimitiveConstant) value;
+ switch (c.getJavaKind()) {
+ case Int:
+ return JavaConstant.forInt(c.asInt() << amount);
+ case Long:
+ return JavaConstant.forLong(c.asLong() << amount);
+ default:
+ throw GraalError.shouldNotReachHere();
+ }
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp stamp, IntegerStamp shift) {
+ IntegerStamp value = (IntegerStamp) stamp;
+ int bits = value.getBits();
+ if (value.isEmpty()) {
+ return value;
+ } else if (shift.isEmpty()) {
+ return StampFactory.forInteger(bits).empty();
+ } else if (value.upMask() == 0) {
+ return value;
+ }
+
+ int shiftMask = getShiftAmountMask(stamp);
+ int shiftBits = Integer.bitCount(shiftMask);
+ if (shift.lowerBound() == shift.upperBound()) {
+ int shiftAmount = (int) (shift.lowerBound() & shiftMask);
+ if (shiftAmount == 0) {
+ return value;
+ }
+ // the mask of bits that will be lost or shifted into the sign bit
+ long removedBits = -1L << (bits - shiftAmount - 1);
+ if ((value.lowerBound() & removedBits) == 0 && (value.upperBound() & removedBits) == 0) {
+ /*
+ * use a better stamp if neither lower nor upper bound can lose
+ * bits
+ */
+ return new IntegerStamp(bits, value.lowerBound() << shiftAmount, value.upperBound() << shiftAmount, value.downMask() << shiftAmount, value.upMask() << shiftAmount);
+ }
+ }
+ if ((shift.lowerBound() >>> shiftBits) == (shift.upperBound() >>> shiftBits)) {
+ long defaultMask = CodeUtil.mask(bits);
+ long downMask = defaultMask;
+ long upMask = 0;
+ for (long i = shift.lowerBound(); i <= shift.upperBound(); i++) {
+ if (shift.contains(i)) {
+ downMask &= value.downMask() << (i & shiftMask);
+ upMask |= value.upMask() << (i & shiftMask);
+ }
+ }
+ Stamp result = IntegerStamp.stampForMask(bits, downMask, upMask & defaultMask);
+ return result;
+ }
+ return value.unrestricted();
+ }
+
+ @Override
+ public int getShiftAmountMask(Stamp s) {
+ IntegerStamp stamp = (IntegerStamp) s;
+ assert CodeUtil.isPowerOf2(stamp.getBits());
+ return stamp.getBits() - 1;
+ }
+ },
+
+ new ShiftOp.Shr() {
+
+ @Override
+ public Constant foldConstant(Constant value, int amount) {
+ PrimitiveConstant c = (PrimitiveConstant) value;
+ switch (c.getJavaKind()) {
+ case Int:
+ return JavaConstant.forInt(c.asInt() >> amount);
+ case Long:
+ return JavaConstant.forLong(c.asLong() >> amount);
+ default:
+ throw GraalError.shouldNotReachHere();
+ }
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp stamp, IntegerStamp shift) {
+ IntegerStamp value = (IntegerStamp) stamp;
+ int bits = value.getBits();
+ if (value.isEmpty()) {
+ return value;
+ } else if (shift.isEmpty()) {
+ return StampFactory.forInteger(bits).empty();
+ } else if (shift.lowerBound() == shift.upperBound()) {
+ long shiftCount = shift.lowerBound() & getShiftAmountMask(stamp);
+ if (shiftCount == 0) {
+ return stamp;
+ }
+
+ int extraBits = 64 - bits;
+ long defaultMask = CodeUtil.mask(bits);
+ // shifting back and forth performs sign extension
+ long downMask = (value.downMask() << extraBits) >> (shiftCount + extraBits) & defaultMask;
+ long upMask = (value.upMask() << extraBits) >> (shiftCount + extraBits) & defaultMask;
+ return new IntegerStamp(bits, value.lowerBound() >> shiftCount, value.upperBound() >> shiftCount, downMask, upMask);
+ }
+ long mask = IntegerStamp.upMaskFor(bits, value.lowerBound(), value.upperBound());
+ return IntegerStamp.stampForMask(bits, 0, mask);
+ }
+
+ @Override
+ public int getShiftAmountMask(Stamp s) {
+ IntegerStamp stamp = (IntegerStamp) s;
+ assert CodeUtil.isPowerOf2(stamp.getBits());
+ return stamp.getBits() - 1;
+ }
+ },
+
+ new ShiftOp.UShr() {
+
+ @Override
+ public Constant foldConstant(Constant value, int amount) {
+ PrimitiveConstant c = (PrimitiveConstant) value;
+ switch (c.getJavaKind()) {
+ case Int:
+ return JavaConstant.forInt(c.asInt() >>> amount);
+ case Long:
+ return JavaConstant.forLong(c.asLong() >>> amount);
+ default:
+ throw GraalError.shouldNotReachHere();
+ }
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp stamp, IntegerStamp shift) {
+ IntegerStamp value = (IntegerStamp) stamp;
+ int bits = value.getBits();
+ if (value.isEmpty()) {
+ return value;
+ } else if (shift.isEmpty()) {
+ return StampFactory.forInteger(bits).empty();
+ }
+
+ if (shift.lowerBound() == shift.upperBound()) {
+ long shiftCount = shift.lowerBound() & getShiftAmountMask(stamp);
+ if (shiftCount == 0) {
+ return stamp;
+ }
+
+ long downMask = value.downMask() >>> shiftCount;
+ long upMask = value.upMask() >>> shiftCount;
+ if (value.lowerBound() < 0) {
+ return new IntegerStamp(bits, downMask, upMask, downMask, upMask);
+ } else {
+ return new IntegerStamp(bits, value.lowerBound() >>> shiftCount, value.upperBound() >>> shiftCount, downMask, upMask);
+ }
+ }
+ long mask = IntegerStamp.upMaskFor(bits, value.lowerBound(), value.upperBound());
+ return IntegerStamp.stampForMask(bits, 0, mask);
+ }
+
+ @Override
+ public int getShiftAmountMask(Stamp s) {
+ IntegerStamp stamp = (IntegerStamp) s;
+ assert CodeUtil.isPowerOf2(stamp.getBits());
+ return stamp.getBits() - 1;
+ }
+ },
+
+ new UnaryOp.Abs() {
+
+ @Override
+ public Constant foldConstant(Constant value) {
+ PrimitiveConstant c = (PrimitiveConstant) value;
+ return JavaConstant.forIntegerKind(c.getJavaKind(), Math.abs(c.asLong()));
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp input) {
+ IntegerStamp stamp = (IntegerStamp) input;
+ int bits = stamp.getBits();
+ if (stamp.lowerBound() == CodeUtil.minValue(bits)) {
+ return input.unrestricted();
+ } else {
+ long limit = Math.max(-stamp.lowerBound(), stamp.upperBound());
+ return StampFactory.forInteger(bits, 0, limit);
+ }
+ }
+ },
+
+ null,
+
+ new IntegerConvertOp.ZeroExtend() {
+
+ @Override
+ public Constant foldConstant(int inputBits, int resultBits, Constant c) {
+ PrimitiveConstant value = (PrimitiveConstant) c;
+ return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.zeroExtend(value.asLong(), inputBits));
+ }
+
+ @Override
+ public Stamp foldStamp(int inputBits, int resultBits, Stamp input) {
+ IntegerStamp stamp = (IntegerStamp) input;
+ assert inputBits == stamp.getBits();
+ assert inputBits <= resultBits;
+
+ if (inputBits == resultBits) {
+ return input;
+ }
+
+ if (input.isEmpty()) {
+ return StampFactory.forInteger(resultBits).empty();
+ }
+
+ long downMask = CodeUtil.zeroExtend(stamp.downMask(), inputBits);
+ long upMask = CodeUtil.zeroExtend(stamp.upMask(), inputBits);
+ long lowerBound = stamp.unsignedLowerBound();
+ long upperBound = stamp.unsignedUpperBound();
+ return IntegerStamp.create(resultBits, lowerBound, upperBound, downMask, upMask);
+ }
+
+ @Override
+ public Stamp invertStamp(int inputBits, int resultBits, Stamp outStamp) {
+ IntegerStamp stamp = (IntegerStamp) outStamp;
+ if (stamp.isEmpty()) {
+ return StampFactory.forInteger(inputBits).empty();
+ }
+ return StampFactory.forUnsignedInteger(inputBits, stamp.lowerBound(), stamp.upperBound(), stamp.downMask(), stamp.upMask());
+ }
+ },
+
+ new IntegerConvertOp.SignExtend() {
+
+ @Override
+ public Constant foldConstant(int inputBits, int resultBits, Constant c) {
+ PrimitiveConstant value = (PrimitiveConstant) c;
+ return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.signExtend(value.asLong(), inputBits));
+ }
+
+ @Override
+ public Stamp foldStamp(int inputBits, int resultBits, Stamp input) {
+ IntegerStamp stamp = (IntegerStamp) input;
+ assert inputBits == stamp.getBits();
+ assert inputBits <= resultBits;
+
+ long defaultMask = CodeUtil.mask(resultBits);
+ long downMask = CodeUtil.signExtend(stamp.downMask(), inputBits) & defaultMask;
+ long upMask = CodeUtil.signExtend(stamp.upMask(), inputBits) & defaultMask;
+
+ return new IntegerStamp(resultBits, stamp.lowerBound(), stamp.upperBound(), downMask, upMask);
+ }
+
+ @Override
+ public Stamp invertStamp(int inputBits, int resultBits, Stamp outStamp) {
+ IntegerStamp stamp = (IntegerStamp) outStamp;
+ long mask = CodeUtil.mask(inputBits);
+ return StampFactory.forIntegerWithMask(inputBits, stamp.lowerBound(), stamp.upperBound(), stamp.downMask() & mask, stamp.upMask() & mask);
+ }
+ },
+
+ new IntegerConvertOp.Narrow() {
+
+ @Override
+ public Constant foldConstant(int inputBits, int resultBits, Constant c) {
+ PrimitiveConstant value = (PrimitiveConstant) c;
+ return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.narrow(value.asLong(), resultBits));
+ }
+
+ @Override
+ public Stamp foldStamp(int inputBits, int resultBits, Stamp input) {
+ IntegerStamp stamp = (IntegerStamp) input;
+ assert inputBits == stamp.getBits();
+ assert resultBits <= inputBits;
+ if (resultBits == inputBits) {
+ return stamp;
+ }
+
+ final long upperBound;
+ if (stamp.lowerBound() < CodeUtil.minValue(resultBits)) {
+ upperBound = CodeUtil.maxValue(resultBits);
+ } else {
+ upperBound = saturate(stamp.upperBound(), resultBits);
+ }
+ final long lowerBound;
+ if (stamp.upperBound() > CodeUtil.maxValue(resultBits)) {
+ lowerBound = CodeUtil.minValue(resultBits);
+ } else {
+ lowerBound = saturate(stamp.lowerBound(), resultBits);
+ }
+
+ long defaultMask = CodeUtil.mask(resultBits);
+ long newDownMask = stamp.downMask() & defaultMask;
+ long newUpMask = stamp.upMask() & defaultMask;
+ long newLowerBound = CodeUtil.signExtend((lowerBound | newDownMask) & newUpMask, resultBits);
+ long newUpperBound = CodeUtil.signExtend((upperBound | newDownMask) & newUpMask, resultBits);
+ return new IntegerStamp(resultBits, newLowerBound, newUpperBound, newDownMask, newUpMask);
+ }
+ },
+
+ new FloatConvertOp(I2F) {
+
+ @Override
+ public Constant foldConstant(Constant c) {
+ PrimitiveConstant value = (PrimitiveConstant) c;
+ return JavaConstant.forFloat(value.asInt());
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp input) {
+ IntegerStamp stamp = (IntegerStamp) input;
+ assert stamp.getBits() == 32;
+ float lowerBound = stamp.lowerBound();
+ float upperBound = stamp.upperBound();
+ return StampFactory.forFloat(JavaKind.Float, lowerBound, upperBound, true);
+ }
+ },
+
+ new FloatConvertOp(L2F) {
+
+ @Override
+ public Constant foldConstant(Constant c) {
+ PrimitiveConstant value = (PrimitiveConstant) c;
+ return JavaConstant.forFloat(value.asLong());
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp input) {
+ IntegerStamp stamp = (IntegerStamp) input;
+ assert stamp.getBits() == 64;
+ float lowerBound = stamp.lowerBound();
+ float upperBound = stamp.upperBound();
+ return StampFactory.forFloat(JavaKind.Float, lowerBound, upperBound, true);
+ }
+ },
+
+ new FloatConvertOp(I2D) {
+
+ @Override
+ public Constant foldConstant(Constant c) {
+ PrimitiveConstant value = (PrimitiveConstant) c;
+ return JavaConstant.forDouble(value.asInt());
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp input) {
+ IntegerStamp stamp = (IntegerStamp) input;
+ assert stamp.getBits() == 32;
+ double lowerBound = stamp.lowerBound();
+ double upperBound = stamp.upperBound();
+ return StampFactory.forFloat(JavaKind.Double, lowerBound, upperBound, true);
+ }
+ },
+
+ new FloatConvertOp(L2D) {
+
+ @Override
+ public Constant foldConstant(Constant c) {
+ PrimitiveConstant value = (PrimitiveConstant) c;
+ return JavaConstant.forDouble(value.asLong());
+ }
+
+ @Override
+ public Stamp foldStamp(Stamp input) {
+ IntegerStamp stamp = (IntegerStamp) input;
+ assert stamp.getBits() == 64;
+ double lowerBound = stamp.lowerBound();
+ double upperBound = stamp.upperBound();
+ return StampFactory.forFloat(JavaKind.Double, lowerBound, upperBound, true);
+ }
+ });
+}