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