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