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