001/*
002 * Copyright (c) 2012, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package com.oracle.graal.compiler.common.type;
024
025import static com.oracle.graal.compiler.common.calc.FloatConvert.*;
026
027import java.nio.*;
028import java.util.*;
029
030import jdk.internal.jvmci.code.*;
031import jdk.internal.jvmci.common.*;
032import jdk.internal.jvmci.meta.*;
033
034import com.oracle.graal.compiler.common.spi.*;
035import com.oracle.graal.compiler.common.type.ArithmeticOpTable.BinaryOp;
036import com.oracle.graal.compiler.common.type.ArithmeticOpTable.FloatConvertOp;
037import com.oracle.graal.compiler.common.type.ArithmeticOpTable.IntegerConvertOp;
038import com.oracle.graal.compiler.common.type.ArithmeticOpTable.ShiftOp;
039import com.oracle.graal.compiler.common.type.ArithmeticOpTable.UnaryOp;
040
041/**
042 * Describes the possible values of a node that produces an int or long result.
043 *
044 * The description consists of (inclusive) lower and upper bounds and up (may be set) and down
045 * (always set) bit-masks.
046 */
047public class IntegerStamp extends PrimitiveStamp {
048
049    private final long lowerBound;
050    private final long upperBound;
051    private final long downMask;
052    private final long upMask;
053
054    public IntegerStamp(int bits, long lowerBound, long upperBound, long downMask, long upMask) {
055        super(bits, OPS);
056        this.lowerBound = lowerBound;
057        this.upperBound = upperBound;
058        this.downMask = downMask;
059        this.upMask = upMask;
060        assert lowerBound >= CodeUtil.minValue(bits) : this;
061        assert upperBound <= CodeUtil.maxValue(bits) : this;
062        assert (downMask & CodeUtil.mask(bits)) == downMask : this;
063        assert (upMask & CodeUtil.mask(bits)) == upMask : this;
064    }
065
066    public static IntegerStamp stampForMask(int bits, long downMask, long upMask) {
067        long lowerBound;
068        long upperBound;
069        if (((upMask >>> (bits - 1)) & 1) == 0) {
070            lowerBound = downMask;
071            upperBound = upMask;
072        } else if (((downMask >>> (bits - 1)) & 1) == 1) {
073            lowerBound = downMask;
074            upperBound = upMask;
075        } else {
076            lowerBound = downMask | (-1L << (bits - 1));
077            upperBound = CodeUtil.maxValue(bits) & upMask;
078        }
079        lowerBound = CodeUtil.convert(lowerBound, bits, false);
080        upperBound = CodeUtil.convert(upperBound, bits, false);
081        return new IntegerStamp(bits, lowerBound, upperBound, downMask, upMask);
082    }
083
084    @Override
085    public IntegerStamp unrestricted() {
086        return new IntegerStamp(getBits(), CodeUtil.minValue(getBits()), CodeUtil.maxValue(getBits()), 0, CodeUtil.mask(getBits()));
087    }
088
089    @Override
090    public Stamp empty() {
091        return new IntegerStamp(getBits(), CodeUtil.maxValue(getBits()), CodeUtil.minValue(getBits()), CodeUtil.mask(getBits()), 0);
092    }
093
094    @Override
095    public Stamp constant(Constant c, MetaAccessProvider meta) {
096        if (c instanceof PrimitiveConstant) {
097            long value = ((PrimitiveConstant) c).asLong();
098            return StampFactory.forInteger(getBits(), value, value);
099        }
100        return this;
101    }
102
103    @Override
104    public SerializableConstant deserialize(ByteBuffer buffer) {
105        switch (getBits()) {
106            case 1:
107                return JavaConstant.forBoolean(buffer.get() != 0);
108            case 8:
109                return JavaConstant.forByte(buffer.get());
110            case 16:
111                return JavaConstant.forShort(buffer.getShort());
112            case 32:
113                return JavaConstant.forInt(buffer.getInt());
114            case 64:
115                return JavaConstant.forLong(buffer.getLong());
116            default:
117                throw JVMCIError.shouldNotReachHere();
118        }
119    }
120
121    @Override
122    public boolean hasValues() {
123        return lowerBound <= upperBound;
124    }
125
126    @Override
127    public Kind getStackKind() {
128        if (getBits() > 32) {
129            return Kind.Long;
130        } else {
131            return Kind.Int;
132        }
133    }
134
135    @Override
136    public LIRKind getLIRKind(LIRKindTool tool) {
137        return tool.getIntegerKind(getBits());
138    }
139
140    @Override
141    public ResolvedJavaType javaType(MetaAccessProvider metaAccess) {
142        switch (getBits()) {
143            case 1:
144                return metaAccess.lookupJavaType(Boolean.TYPE);
145            case 8:
146                return metaAccess.lookupJavaType(Byte.TYPE);
147            case 16:
148                return metaAccess.lookupJavaType(Short.TYPE);
149            case 32:
150                return metaAccess.lookupJavaType(Integer.TYPE);
151            case 64:
152                return metaAccess.lookupJavaType(Long.TYPE);
153            default:
154                throw JVMCIError.shouldNotReachHere();
155        }
156    }
157
158    /**
159     * The signed inclusive lower bound on the value described by this stamp.
160     */
161    public long lowerBound() {
162        return lowerBound;
163    }
164
165    /**
166     * The signed inclusive upper bound on the value described by this stamp.
167     */
168    public long upperBound() {
169        return upperBound;
170    }
171
172    /**
173     * This bit-mask describes the bits that are always set in the value described by this stamp.
174     */
175    public long downMask() {
176        return downMask;
177    }
178
179    /**
180     * This bit-mask describes the bits that can be set in the value described by this stamp.
181     */
182    public long upMask() {
183        return upMask;
184    }
185
186    public boolean isUnrestricted() {
187        return lowerBound == CodeUtil.minValue(getBits()) && upperBound == CodeUtil.maxValue(getBits()) && downMask == 0 && upMask == CodeUtil.mask(getBits());
188    }
189
190    public boolean contains(long value) {
191        return value >= lowerBound && value <= upperBound && (value & downMask) == downMask && (value & upMask) == (value & CodeUtil.mask(getBits()));
192    }
193
194    public boolean isPositive() {
195        return lowerBound() >= 0;
196    }
197
198    public boolean isNegative() {
199        return upperBound() <= 0;
200    }
201
202    public boolean isStrictlyPositive() {
203        return lowerBound() > 0;
204    }
205
206    public boolean isStrictlyNegative() {
207        return upperBound() < 0;
208    }
209
210    public boolean canBePositive() {
211        return upperBound() > 0;
212    }
213
214    public boolean canBeNegative() {
215        return lowerBound() < 0;
216    }
217
218    @Override
219    public String toString() {
220        StringBuilder str = new StringBuilder();
221        str.append('i');
222        str.append(getBits());
223        if (lowerBound == upperBound) {
224            str.append(" [").append(lowerBound).append(']');
225        } else if (lowerBound != CodeUtil.minValue(getBits()) || upperBound != CodeUtil.maxValue(getBits())) {
226            str.append(" [").append(lowerBound).append(" - ").append(upperBound).append(']');
227        }
228        if (downMask != 0) {
229            str.append(" \u21ca");
230            new Formatter(str).format("%016x", downMask);
231        }
232        if (upMask != CodeUtil.mask(getBits())) {
233            str.append(" \u21c8");
234            new Formatter(str).format("%016x", upMask);
235        }
236        return str.toString();
237    }
238
239    private Stamp createStamp(IntegerStamp other, long newUpperBound, long newLowerBound, long newDownMask, long newUpMask) {
240        assert getBits() == other.getBits();
241        if (newLowerBound > newUpperBound || (newDownMask & (~newUpMask)) != 0 || (newUpMask == 0 && (newLowerBound > 0 || newUpperBound < 0))) {
242            return empty();
243        } else if (newLowerBound == lowerBound && newUpperBound == upperBound && newDownMask == downMask && newUpMask == upMask) {
244            return this;
245        } else if (newLowerBound == other.lowerBound && newUpperBound == other.upperBound && newDownMask == other.downMask && newUpMask == other.upMask) {
246            return other;
247        } else {
248            return new IntegerStamp(getBits(), newLowerBound, newUpperBound, newDownMask, newUpMask);
249        }
250    }
251
252    @Override
253    public Stamp meet(Stamp otherStamp) {
254        if (otherStamp == this) {
255            return this;
256        }
257        IntegerStamp other = (IntegerStamp) otherStamp;
258        return createStamp(other, Math.max(upperBound, other.upperBound), Math.min(lowerBound, other.lowerBound), downMask & other.downMask, upMask | other.upMask);
259    }
260
261    @Override
262    public Stamp join(Stamp otherStamp) {
263        if (otherStamp == this) {
264            return this;
265        }
266        IntegerStamp other = (IntegerStamp) otherStamp;
267        long newDownMask = downMask | other.downMask;
268        long newLowerBound = Math.max(lowerBound, other.lowerBound) | newDownMask;
269        return createStamp(other, Math.min(upperBound, other.upperBound), newLowerBound, newDownMask, upMask & other.upMask);
270    }
271
272    @Override
273    public boolean isCompatible(Stamp stamp) {
274        if (this == stamp) {
275            return true;
276        }
277        if (stamp instanceof IntegerStamp) {
278            IntegerStamp other = (IntegerStamp) stamp;
279            return getBits() == other.getBits();
280        }
281        return false;
282    }
283
284    @Override
285    public int hashCode() {
286        final int prime = 31;
287        int result = 1;
288        result = prime * result + super.hashCode();
289        result = prime * result + (int) (lowerBound ^ (lowerBound >>> 32));
290        result = prime * result + (int) (upperBound ^ (upperBound >>> 32));
291        result = prime * result + (int) (downMask ^ (downMask >>> 32));
292        result = prime * result + (int) (upMask ^ (upMask >>> 32));
293        return result;
294    }
295
296    @Override
297    public boolean equals(Object obj) {
298        if (this == obj) {
299            return true;
300        }
301        if (obj == null || getClass() != obj.getClass() || !super.equals(obj)) {
302            return false;
303        }
304        IntegerStamp other = (IntegerStamp) obj;
305        if (lowerBound != other.lowerBound || upperBound != other.upperBound || downMask != other.downMask || upMask != other.upMask) {
306            return false;
307        }
308        return super.equals(other);
309    }
310
311    public static long upMaskFor(int bits, long lowerBound, long upperBound) {
312        long mask = lowerBound | upperBound;
313        if (mask == 0) {
314            return 0;
315        } else {
316            return ((-1L) >>> Long.numberOfLeadingZeros(mask)) & CodeUtil.mask(bits);
317        }
318    }
319
320    /**
321     * Checks if the 2 stamps represent values of the same sign. Returns true if the two stamps are
322     * both positive of null or if they are both strictly negative
323     *
324     * @return true if the two stamps are both positive of null or if they are both strictly
325     *         negative
326     */
327    public static boolean sameSign(IntegerStamp s1, IntegerStamp s2) {
328        return s1.isPositive() && s2.isPositive() || s1.isStrictlyNegative() && s2.isStrictlyNegative();
329    }
330
331    @Override
332    public JavaConstant asConstant() {
333        if (lowerBound == upperBound) {
334            switch (getBits()) {
335                case 1:
336                    return JavaConstant.forBoolean(lowerBound != 0);
337                case 8:
338                    return JavaConstant.forByte((byte) lowerBound);
339                case 16:
340                    return JavaConstant.forShort((short) lowerBound);
341                case 32:
342                    return JavaConstant.forInt((int) lowerBound);
343                case 64:
344                    return JavaConstant.forLong(lowerBound);
345            }
346        }
347        return null;
348    }
349
350    public static boolean addOverflowsPositively(long x, long y, int bits) {
351        long result = x + y;
352        if (bits == 64) {
353            return (~x & ~y & result) < 0;
354        } else {
355            return result > CodeUtil.maxValue(bits);
356        }
357    }
358
359    public static boolean addOverflowsNegatively(long x, long y, int bits) {
360        long result = x + y;
361        if (bits == 64) {
362            return (x & y & ~result) < 0;
363        } else {
364            return result < CodeUtil.minValue(bits);
365        }
366    }
367
368    public static long carryBits(long x, long y) {
369        return (x + y) ^ x ^ y;
370    }
371
372    private static long saturate(long v, int bits) {
373        if (bits < 64) {
374            long max = CodeUtil.maxValue(bits);
375            if (v > max) {
376                return max;
377            }
378            long min = CodeUtil.minValue(bits);
379            if (v < min) {
380                return min;
381            }
382        }
383        return v;
384    }
385
386    public static final ArithmeticOpTable OPS = new ArithmeticOpTable(
387
388    new UnaryOp.Neg() {
389
390        @Override
391        public Constant foldConstant(Constant value) {
392            PrimitiveConstant c = (PrimitiveConstant) value;
393            return JavaConstant.forIntegerKind(c.getKind(), -c.asLong());
394        }
395
396        @Override
397        public Stamp foldStamp(Stamp s) {
398            IntegerStamp stamp = (IntegerStamp) s;
399            int bits = stamp.getBits();
400            if (stamp.lowerBound() != CodeUtil.minValue(bits)) {
401                // TODO(ls) check if the mask calculation is correct...
402                return StampFactory.forInteger(bits, -stamp.upperBound(), -stamp.lowerBound());
403            } else {
404                return stamp.unrestricted();
405            }
406        }
407    },
408
409    new BinaryOp.Add(true, true) {
410
411        @Override
412        public Constant foldConstant(Constant const1, Constant const2) {
413            PrimitiveConstant a = (PrimitiveConstant) const1;
414            PrimitiveConstant b = (PrimitiveConstant) const2;
415            assert a.getKind() == b.getKind();
416            return JavaConstant.forIntegerKind(a.getKind(), a.asLong() + b.asLong());
417        }
418
419        @Override
420        public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
421            IntegerStamp a = (IntegerStamp) stamp1;
422            IntegerStamp b = (IntegerStamp) stamp2;
423
424            int bits = a.getBits();
425            assert bits == b.getBits();
426
427            if (a.isUnrestricted()) {
428                return a;
429            } else if (b.isUnrestricted()) {
430                return b;
431            }
432            long defaultMask = CodeUtil.mask(bits);
433            long variableBits = (a.downMask() ^ a.upMask()) | (b.downMask() ^ b.upMask());
434            long variableBitsWithCarry = variableBits | (carryBits(a.downMask(), b.downMask()) ^ carryBits(a.upMask(), b.upMask()));
435            long newDownMask = (a.downMask() + b.downMask()) & ~variableBitsWithCarry;
436            long newUpMask = (a.downMask() + b.downMask()) | variableBitsWithCarry;
437
438            newDownMask &= defaultMask;
439            newUpMask &= defaultMask;
440
441            long newLowerBound;
442            long newUpperBound;
443            boolean lowerOverflowsPositively = addOverflowsPositively(a.lowerBound(), b.lowerBound(), bits);
444            boolean upperOverflowsPositively = addOverflowsPositively(a.upperBound(), b.upperBound(), bits);
445            boolean lowerOverflowsNegatively = addOverflowsNegatively(a.lowerBound(), b.lowerBound(), bits);
446            boolean upperOverflowsNegatively = addOverflowsNegatively(a.upperBound(), b.upperBound(), bits);
447            if ((lowerOverflowsNegatively && !upperOverflowsNegatively) || (!lowerOverflowsPositively && upperOverflowsPositively)) {
448                newLowerBound = CodeUtil.minValue(bits);
449                newUpperBound = CodeUtil.maxValue(bits);
450            } else {
451                newLowerBound = CodeUtil.signExtend((a.lowerBound() + b.lowerBound()) & defaultMask, bits);
452                newUpperBound = CodeUtil.signExtend((a.upperBound() + b.upperBound()) & defaultMask, bits);
453            }
454            IntegerStamp limit = StampFactory.forInteger(bits, newLowerBound, newUpperBound);
455            newUpMask &= limit.upMask();
456            newUpperBound = CodeUtil.signExtend(newUpperBound & newUpMask, bits);
457            newDownMask |= limit.downMask();
458            newLowerBound |= newDownMask;
459            return new IntegerStamp(bits, newLowerBound, newUpperBound, newDownMask, newUpMask);
460        }
461
462        @Override
463        public boolean isNeutral(Constant value) {
464            PrimitiveConstant n = (PrimitiveConstant) value;
465            return n.asLong() == 0;
466        }
467    },
468
469    new BinaryOp.Sub(true, false) {
470
471        @Override
472        public Constant foldConstant(Constant const1, Constant const2) {
473            PrimitiveConstant a = (PrimitiveConstant) const1;
474            PrimitiveConstant b = (PrimitiveConstant) const2;
475            assert a.getKind() == b.getKind();
476            return JavaConstant.forIntegerKind(a.getKind(), a.asLong() - b.asLong());
477        }
478
479        @Override
480        public Stamp foldStamp(Stamp a, Stamp b) {
481            return OPS.getAdd().foldStamp(a, OPS.getNeg().foldStamp(b));
482        }
483
484        @Override
485        public boolean isNeutral(Constant value) {
486            PrimitiveConstant n = (PrimitiveConstant) value;
487            return n.asLong() == 0;
488        }
489
490        @Override
491        public Constant getZero(Stamp s) {
492            IntegerStamp stamp = (IntegerStamp) s;
493            return JavaConstant.forPrimitiveInt(stamp.getBits(), 0);
494        }
495    },
496
497    new BinaryOp.Mul(true, true) {
498
499        @Override
500        public Constant foldConstant(Constant const1, Constant const2) {
501            PrimitiveConstant a = (PrimitiveConstant) const1;
502            PrimitiveConstant b = (PrimitiveConstant) const2;
503            assert a.getKind() == b.getKind();
504            return JavaConstant.forIntegerKind(a.getKind(), a.asLong() * b.asLong());
505        }
506
507        @Override
508        public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
509            IntegerStamp a = (IntegerStamp) stamp1;
510            IntegerStamp b = (IntegerStamp) stamp2;
511            if (a.upMask() == 0) {
512                return a;
513            } else if (b.upMask() == 0) {
514                return b;
515            } else {
516                // TODO
517                return a.unrestricted();
518            }
519        }
520
521        @Override
522        public boolean isNeutral(Constant value) {
523            PrimitiveConstant n = (PrimitiveConstant) value;
524            return n.asLong() == 1;
525        }
526    },
527
528    new BinaryOp.Div(true, false) {
529
530        @Override
531        public Constant foldConstant(Constant const1, Constant const2) {
532            PrimitiveConstant a = (PrimitiveConstant) const1;
533            PrimitiveConstant b = (PrimitiveConstant) const2;
534            assert a.getKind() == b.getKind();
535            return JavaConstant.forIntegerKind(a.getKind(), a.asLong() / b.asLong());
536        }
537
538        @Override
539        public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
540            IntegerStamp a = (IntegerStamp) stamp1;
541            IntegerStamp b = (IntegerStamp) stamp2;
542            assert a.getBits() == b.getBits();
543            if (b.isStrictlyPositive()) {
544                long newLowerBound = a.lowerBound() / b.lowerBound();
545                long newUpperBound = a.upperBound() / b.lowerBound();
546                return StampFactory.forInteger(a.getBits(), newLowerBound, newUpperBound);
547            } else {
548                return a.unrestricted();
549            }
550        }
551
552        @Override
553        public boolean isNeutral(Constant value) {
554            PrimitiveConstant n = (PrimitiveConstant) value;
555            return n.asLong() == 1;
556        }
557    },
558
559    new BinaryOp.Rem(false, false) {
560
561        @Override
562        public Constant foldConstant(Constant const1, Constant const2) {
563            PrimitiveConstant a = (PrimitiveConstant) const1;
564            PrimitiveConstant b = (PrimitiveConstant) const2;
565            assert a.getKind() == b.getKind();
566            return JavaConstant.forIntegerKind(a.getKind(), a.asLong() % b.asLong());
567        }
568
569        @Override
570        public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
571            IntegerStamp a = (IntegerStamp) stamp1;
572            IntegerStamp b = (IntegerStamp) stamp2;
573            assert a.getBits() == b.getBits();
574            // zero is always possible
575            long newLowerBound = Math.min(a.lowerBound(), 0);
576            long newUpperBound = Math.max(a.upperBound(), 0);
577
578            long magnitude; // the maximum absolute value of the result, derived from b
579            if (b.lowerBound() == CodeUtil.minValue(b.getBits())) {
580                // Math.abs(...) - 1 does not work in a case
581                magnitude = CodeUtil.maxValue(b.getBits());
582            } else {
583                magnitude = Math.max(Math.abs(b.lowerBound()), Math.abs(b.upperBound())) - 1;
584            }
585            newLowerBound = Math.max(newLowerBound, -magnitude);
586            newUpperBound = Math.min(newUpperBound, magnitude);
587
588            return StampFactory.forInteger(a.getBits(), newLowerBound, newUpperBound);
589        }
590    },
591
592    new UnaryOp.Not() {
593
594        @Override
595        public Constant foldConstant(Constant c) {
596            PrimitiveConstant value = (PrimitiveConstant) c;
597            return JavaConstant.forIntegerKind(value.getKind(), ~value.asLong());
598        }
599
600        @Override
601        public Stamp foldStamp(Stamp stamp) {
602            IntegerStamp integerStamp = (IntegerStamp) stamp;
603            int bits = integerStamp.getBits();
604            long defaultMask = CodeUtil.mask(bits);
605            return new IntegerStamp(bits, ~integerStamp.upperBound(), ~integerStamp.lowerBound(), (~integerStamp.upMask()) & defaultMask, (~integerStamp.downMask()) & defaultMask);
606        }
607    },
608
609    new BinaryOp.And(true, true) {
610
611        @Override
612        public Constant foldConstant(Constant const1, Constant const2) {
613            PrimitiveConstant a = (PrimitiveConstant) const1;
614            PrimitiveConstant b = (PrimitiveConstant) const2;
615            assert a.getKind() == b.getKind();
616            return JavaConstant.forIntegerKind(a.getKind(), a.asLong() & b.asLong());
617        }
618
619        @Override
620        public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
621            IntegerStamp a = (IntegerStamp) stamp1;
622            IntegerStamp b = (IntegerStamp) stamp2;
623            assert a.getBits() == b.getBits();
624            return stampForMask(a.getBits(), a.downMask() & b.downMask(), a.upMask() & b.upMask());
625        }
626
627        @Override
628        public boolean isNeutral(Constant value) {
629            PrimitiveConstant n = (PrimitiveConstant) value;
630            int bits = n.getKind().getBitCount();
631            long mask = CodeUtil.mask(bits);
632            return (n.asLong() & mask) == mask;
633        }
634    },
635
636    new BinaryOp.Or(true, true) {
637
638        @Override
639        public Constant foldConstant(Constant const1, Constant const2) {
640            PrimitiveConstant a = (PrimitiveConstant) const1;
641            PrimitiveConstant b = (PrimitiveConstant) const2;
642            assert a.getKind() == b.getKind();
643            return JavaConstant.forIntegerKind(a.getKind(), a.asLong() | b.asLong());
644        }
645
646        @Override
647        public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
648            IntegerStamp a = (IntegerStamp) stamp1;
649            IntegerStamp b = (IntegerStamp) stamp2;
650            assert a.getBits() == b.getBits();
651            return stampForMask(a.getBits(), a.downMask() | b.downMask(), a.upMask() | b.upMask());
652        }
653
654        @Override
655        public boolean isNeutral(Constant value) {
656            PrimitiveConstant n = (PrimitiveConstant) value;
657            return n.asLong() == 0;
658        }
659    },
660
661    new BinaryOp.Xor(true, true) {
662
663        @Override
664        public Constant foldConstant(Constant const1, Constant const2) {
665            PrimitiveConstant a = (PrimitiveConstant) const1;
666            PrimitiveConstant b = (PrimitiveConstant) const2;
667            assert a.getKind() == b.getKind();
668            return JavaConstant.forIntegerKind(a.getKind(), a.asLong() ^ b.asLong());
669        }
670
671        @Override
672        public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
673            IntegerStamp a = (IntegerStamp) stamp1;
674            IntegerStamp b = (IntegerStamp) stamp2;
675            assert a.getBits() == b.getBits();
676
677            long variableBits = (a.downMask() ^ a.upMask()) | (b.downMask() ^ b.upMask());
678            long newDownMask = (a.downMask() ^ b.downMask()) & ~variableBits;
679            long newUpMask = (a.downMask() ^ b.downMask()) | variableBits;
680            return stampForMask(a.getBits(), newDownMask, newUpMask);
681        }
682
683        @Override
684        public boolean isNeutral(Constant value) {
685            PrimitiveConstant n = (PrimitiveConstant) value;
686            return n.asLong() == 0;
687        }
688
689        @Override
690        public Constant getZero(Stamp s) {
691            IntegerStamp stamp = (IntegerStamp) s;
692            return JavaConstant.forPrimitiveInt(stamp.getBits(), 0);
693        }
694    },
695
696    new ShiftOp.Shl() {
697
698        @Override
699        public Constant foldConstant(Constant value, int amount) {
700            PrimitiveConstant c = (PrimitiveConstant) value;
701            switch (c.getKind()) {
702                case Int:
703                    return JavaConstant.forInt(c.asInt() << amount);
704                case Long:
705                    return JavaConstant.forLong(c.asLong() << amount);
706                default:
707                    throw JVMCIError.shouldNotReachHere();
708            }
709        }
710
711        @Override
712        public Stamp foldStamp(Stamp stamp, IntegerStamp shift) {
713            IntegerStamp value = (IntegerStamp) stamp;
714            int bits = value.getBits();
715            long defaultMask = CodeUtil.mask(bits);
716            if (value.upMask() == 0) {
717                return value;
718            }
719            int shiftMask = getShiftAmountMask(stamp);
720            int shiftBits = Integer.bitCount(shiftMask);
721            if (shift.lowerBound() == shift.upperBound()) {
722                int shiftAmount = (int) (shift.lowerBound() & shiftMask);
723                if (shiftAmount == 0) {
724                    return value;
725                }
726                // the mask of bits that will be lost or shifted into the sign bit
727                long removedBits = -1L << (bits - shiftAmount - 1);
728                if ((value.lowerBound() & removedBits) == 0 && (value.upperBound() & removedBits) == 0) {
729                    // use a better stamp if neither lower nor upper bound can lose bits
730                    return new IntegerStamp(bits, value.lowerBound() << shiftAmount, value.upperBound() << shiftAmount, value.downMask() << shiftAmount, value.upMask() << shiftAmount);
731                }
732            }
733            if ((shift.lowerBound() >>> shiftBits) == (shift.upperBound() >>> shiftBits)) {
734                long downMask = defaultMask;
735                long upMask = 0;
736                for (long i = shift.lowerBound(); i <= shift.upperBound(); i++) {
737                    if (shift.contains(i)) {
738                        downMask &= value.downMask() << (i & shiftMask);
739                        upMask |= value.upMask() << (i & shiftMask);
740                    }
741                }
742                Stamp result = IntegerStamp.stampForMask(bits, downMask, upMask & defaultMask);
743                return result;
744            }
745            return value.unrestricted();
746        }
747
748        @Override
749        public int getShiftAmountMask(Stamp s) {
750            IntegerStamp stamp = (IntegerStamp) s;
751            assert CodeUtil.isPowerOf2(stamp.getBits());
752            return stamp.getBits() - 1;
753        }
754    },
755
756    new ShiftOp.Shr() {
757
758        @Override
759        public Constant foldConstant(Constant value, int amount) {
760            PrimitiveConstant c = (PrimitiveConstant) value;
761            switch (c.getKind()) {
762                case Int:
763                    return JavaConstant.forInt(c.asInt() >> amount);
764                case Long:
765                    return JavaConstant.forLong(c.asLong() >> amount);
766                default:
767                    throw JVMCIError.shouldNotReachHere();
768            }
769        }
770
771        @Override
772        public Stamp foldStamp(Stamp stamp, IntegerStamp shift) {
773            IntegerStamp value = (IntegerStamp) stamp;
774            int bits = value.getBits();
775            if (shift.lowerBound() == shift.upperBound()) {
776                long shiftCount = shift.lowerBound() & getShiftAmountMask(stamp);
777                if (shiftCount == 0) {
778                    return stamp;
779                }
780
781                int extraBits = 64 - bits;
782                long defaultMask = CodeUtil.mask(bits);
783                // shifting back and forth performs sign extension
784                long downMask = (value.downMask() << extraBits) >> (shiftCount + extraBits) & defaultMask;
785                long upMask = (value.upMask() << extraBits) >> (shiftCount + extraBits) & defaultMask;
786                return new IntegerStamp(bits, value.lowerBound() >> shiftCount, value.upperBound() >> shiftCount, downMask, upMask);
787            }
788            long mask = IntegerStamp.upMaskFor(bits, value.lowerBound(), value.upperBound());
789            return IntegerStamp.stampForMask(bits, 0, mask);
790        }
791
792        @Override
793        public int getShiftAmountMask(Stamp s) {
794            IntegerStamp stamp = (IntegerStamp) s;
795            assert CodeUtil.isPowerOf2(stamp.getBits());
796            return stamp.getBits() - 1;
797        }
798    },
799
800    new ShiftOp.UShr() {
801
802        @Override
803        public Constant foldConstant(Constant value, int amount) {
804            PrimitiveConstant c = (PrimitiveConstant) value;
805            switch (c.getKind()) {
806                case Int:
807                    return JavaConstant.forInt(c.asInt() >>> amount);
808                case Long:
809                    return JavaConstant.forLong(c.asLong() >>> amount);
810                default:
811                    throw JVMCIError.shouldNotReachHere();
812            }
813        }
814
815        @Override
816        public Stamp foldStamp(Stamp stamp, IntegerStamp shift) {
817            IntegerStamp value = (IntegerStamp) stamp;
818            int bits = value.getBits();
819            if (shift.lowerBound() == shift.upperBound()) {
820                long shiftCount = shift.lowerBound() & getShiftAmountMask(stamp);
821                if (shiftCount == 0) {
822                    return stamp;
823                }
824
825                long downMask = value.downMask() >>> shiftCount;
826                long upMask = value.upMask() >>> shiftCount;
827                if (value.lowerBound() < 0) {
828                    return new IntegerStamp(bits, downMask, upMask, downMask, upMask);
829                } else {
830                    return new IntegerStamp(bits, value.lowerBound() >>> shiftCount, value.upperBound() >>> shiftCount, downMask, upMask);
831                }
832            }
833            long mask = IntegerStamp.upMaskFor(bits, value.lowerBound(), value.upperBound());
834            return IntegerStamp.stampForMask(bits, 0, mask);
835        }
836
837        @Override
838        public int getShiftAmountMask(Stamp s) {
839            IntegerStamp stamp = (IntegerStamp) s;
840            assert CodeUtil.isPowerOf2(stamp.getBits());
841            return stamp.getBits() - 1;
842        }
843    },
844
845    new UnaryOp.Abs() {
846
847        @Override
848        public Constant foldConstant(Constant value) {
849            PrimitiveConstant c = (PrimitiveConstant) value;
850            return JavaConstant.forIntegerKind(c.getKind(), Math.abs(c.asLong()));
851        }
852
853        @Override
854        public Stamp foldStamp(Stamp input) {
855            IntegerStamp stamp = (IntegerStamp) input;
856            int bits = stamp.getBits();
857            if (stamp.lowerBound() == CodeUtil.minValue(bits)) {
858                return input.unrestricted();
859            } else {
860                long limit = Math.max(-stamp.lowerBound(), stamp.upperBound());
861                return StampFactory.forInteger(bits, 0, limit);
862            }
863        }
864    },
865
866    null,
867
868    new IntegerConvertOp.ZeroExtend() {
869
870        @Override
871        public Constant foldConstant(int inputBits, int resultBits, Constant c) {
872            PrimitiveConstant value = (PrimitiveConstant) c;
873            return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.zeroExtend(value.asLong(), inputBits));
874        }
875
876        @Override
877        public Stamp foldStamp(int inputBits, int resultBits, Stamp input) {
878            IntegerStamp stamp = (IntegerStamp) input;
879            assert inputBits == stamp.getBits();
880            assert inputBits <= resultBits;
881
882            long downMask = CodeUtil.zeroExtend(stamp.downMask(), inputBits);
883            long upMask = CodeUtil.zeroExtend(stamp.upMask(), inputBits);
884
885            if (stamp.lowerBound() < 0 && stamp.upperBound() >= 0) {
886                // signed range including 0 and -1
887                // after sign extension, the whole range from 0 to MAX_INT is possible
888                return IntegerStamp.stampForMask(resultBits, downMask, upMask);
889            }
890
891            long lowerBound = CodeUtil.zeroExtend(stamp.lowerBound(), inputBits);
892            long upperBound = CodeUtil.zeroExtend(stamp.upperBound(), inputBits);
893
894            return new IntegerStamp(resultBits, lowerBound, upperBound, downMask, upMask);
895        }
896    },
897
898    new IntegerConvertOp.SignExtend() {
899
900        @Override
901        public Constant foldConstant(int inputBits, int resultBits, Constant c) {
902            PrimitiveConstant value = (PrimitiveConstant) c;
903            return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.signExtend(value.asLong(), inputBits));
904        }
905
906        @Override
907        public Stamp foldStamp(int inputBits, int resultBits, Stamp input) {
908            IntegerStamp stamp = (IntegerStamp) input;
909            assert inputBits == stamp.getBits();
910            assert inputBits <= resultBits;
911
912            long defaultMask = CodeUtil.mask(resultBits);
913            long downMask = CodeUtil.signExtend(stamp.downMask(), inputBits) & defaultMask;
914            long upMask = CodeUtil.signExtend(stamp.upMask(), inputBits) & defaultMask;
915
916            return new IntegerStamp(resultBits, stamp.lowerBound(), stamp.upperBound(), downMask, upMask);
917        }
918    },
919
920    new IntegerConvertOp.Narrow() {
921
922        @Override
923        public Constant foldConstant(int inputBits, int resultBits, Constant c) {
924            PrimitiveConstant value = (PrimitiveConstant) c;
925            return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.narrow(value.asLong(), resultBits));
926        }
927
928        @Override
929        public Stamp foldStamp(int inputBits, int resultBits, Stamp input) {
930            IntegerStamp stamp = (IntegerStamp) input;
931            assert inputBits == stamp.getBits();
932            assert resultBits <= inputBits;
933            if (resultBits == inputBits) {
934                return stamp;
935            }
936
937            final long upperBound;
938            if (stamp.lowerBound() < CodeUtil.minValue(resultBits)) {
939                upperBound = CodeUtil.maxValue(resultBits);
940            } else {
941                upperBound = saturate(stamp.upperBound(), resultBits);
942            }
943            final long lowerBound;
944            if (stamp.upperBound() > CodeUtil.maxValue(resultBits)) {
945                lowerBound = CodeUtil.minValue(resultBits);
946            } else {
947                lowerBound = saturate(stamp.lowerBound(), resultBits);
948            }
949
950            long defaultMask = CodeUtil.mask(resultBits);
951            long newDownMask = stamp.downMask() & defaultMask;
952            long newUpMask = stamp.upMask() & defaultMask;
953            long newLowerBound = CodeUtil.signExtend((lowerBound | newDownMask) & newUpMask, resultBits);
954            long newUpperBound = CodeUtil.signExtend((upperBound | newDownMask) & newUpMask, resultBits);
955            return new IntegerStamp(resultBits, newLowerBound, newUpperBound, newDownMask, newUpMask);
956        }
957    },
958
959    new FloatConvertOp(I2F) {
960
961        @Override
962        public Constant foldConstant(Constant c) {
963            PrimitiveConstant value = (PrimitiveConstant) c;
964            return JavaConstant.forFloat(value.asInt());
965        }
966
967        @Override
968        public Stamp foldStamp(Stamp input) {
969            IntegerStamp stamp = (IntegerStamp) input;
970            assert stamp.getBits() == 32;
971            float lowerBound = stamp.lowerBound();
972            float upperBound = stamp.upperBound();
973            return StampFactory.forFloat(Kind.Float, lowerBound, upperBound, true);
974        }
975    },
976
977    new FloatConvertOp(L2F) {
978
979        @Override
980        public Constant foldConstant(Constant c) {
981            PrimitiveConstant value = (PrimitiveConstant) c;
982            return JavaConstant.forFloat(value.asLong());
983        }
984
985        @Override
986        public Stamp foldStamp(Stamp input) {
987            IntegerStamp stamp = (IntegerStamp) input;
988            assert stamp.getBits() == 64;
989            float lowerBound = stamp.lowerBound();
990            float upperBound = stamp.upperBound();
991            return StampFactory.forFloat(Kind.Float, lowerBound, upperBound, true);
992        }
993    },
994
995    new FloatConvertOp(I2D) {
996
997        @Override
998        public Constant foldConstant(Constant c) {
999            PrimitiveConstant value = (PrimitiveConstant) c;
1000            return JavaConstant.forDouble(value.asInt());
1001        }
1002
1003        @Override
1004        public Stamp foldStamp(Stamp input) {
1005            IntegerStamp stamp = (IntegerStamp) input;
1006            assert stamp.getBits() == 32;
1007            double lowerBound = stamp.lowerBound();
1008            double upperBound = stamp.upperBound();
1009            return StampFactory.forFloat(Kind.Double, lowerBound, upperBound, true);
1010        }
1011    },
1012
1013    new FloatConvertOp(L2D) {
1014
1015        @Override
1016        public Constant foldConstant(Constant c) {
1017            PrimitiveConstant value = (PrimitiveConstant) c;
1018            return JavaConstant.forDouble(value.asLong());
1019        }
1020
1021        @Override
1022        public Stamp foldStamp(Stamp input) {
1023            IntegerStamp stamp = (IntegerStamp) input;
1024            assert stamp.getBits() == 64;
1025            double lowerBound = stamp.lowerBound();
1026            double upperBound = stamp.upperBound();
1027            return StampFactory.forFloat(Kind.Double, lowerBound, upperBound, true);
1028        }
1029    });
1030}