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