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.spi.LIRKindTool;
35 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.BinaryOp;
36 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.FloatConvertOp;
37 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.IntegerConvertOp;
38 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.ShiftOp;
39 import org.graalvm.compiler.core.common.type.ArithmeticOpTable.UnaryOp;
40 import org.graalvm.compiler.debug.GraalError;
41
42 import jdk.vm.ci.code.CodeUtil;
43 import jdk.vm.ci.meta.Constant;
44 import jdk.vm.ci.meta.JavaConstant;
45 import jdk.vm.ci.meta.JavaKind;
46 import jdk.vm.ci.meta.MetaAccessProvider;
47 import jdk.vm.ci.meta.PrimitiveConstant;
48 import jdk.vm.ci.meta.ResolvedJavaType;
49 import jdk.vm.ci.meta.SerializableConstant;
50
51 /**
52 * Describes the possible values of a node that produces an int or long result.
53 *
54 * The description consists of (inclusive) lower and upper bounds and up (may be set) and down
55 * (always set) bit-masks.
56 */
57 public class IntegerStamp extends PrimitiveStamp {
58
59 private final long lowerBound;
60 private final long upperBound;
61 private final long downMask;
62 private final long upMask;
63
64 public IntegerStamp(int bits, long lowerBound, long upperBound, long downMask, long upMask) {
65 super(bits, OPS);
66 this.lowerBound = lowerBound;
67 this.upperBound = upperBound;
68 this.downMask = downMask;
69 this.upMask = upMask;
70 assert lowerBound >= CodeUtil.minValue(bits) : this;
71 assert upperBound <= CodeUtil.maxValue(bits) : this;
72 assert (downMask & CodeUtil.mask(bits)) == downMask : this;
73 assert (upMask & CodeUtil.mask(bits)) == upMask : this;
74 }
75
76 public static IntegerStamp stampForMask(int bits, long downMask, long upMask) {
77 long lowerBound;
78 long upperBound;
79 if (((upMask >>> (bits - 1)) & 1) == 0) {
80 lowerBound = downMask;
81 upperBound = upMask;
82 } else if (((downMask >>> (bits - 1)) & 1) == 1) {
83 lowerBound = downMask;
84 upperBound = upMask;
85 } else {
86 lowerBound = downMask | (-1L << (bits - 1));
87 upperBound = CodeUtil.maxValue(bits) & upMask;
88 }
89 lowerBound = CodeUtil.convert(lowerBound, bits, false);
90 upperBound = CodeUtil.convert(upperBound, bits, false);
91 return new IntegerStamp(bits, lowerBound, upperBound, downMask, upMask);
92 }
93
94 @Override
95 public IntegerStamp unrestricted() {
96 return new IntegerStamp(getBits(), CodeUtil.minValue(getBits()), CodeUtil.maxValue(getBits()), 0, CodeUtil.mask(getBits()));
97 }
98
99 @Override
100 public Stamp empty() {
101 return new IntegerStamp(getBits(), CodeUtil.maxValue(getBits()), CodeUtil.minValue(getBits()), CodeUtil.mask(getBits()), 0);
102 }
103
104 @Override
105 public Stamp constant(Constant c, MetaAccessProvider meta) {
106 if (c instanceof PrimitiveConstant) {
107 long value = ((PrimitiveConstant) c).asLong();
108 return StampFactory.forInteger(getBits(), value, value);
109 }
110 return this;
111 }
112
113 @Override
114 public SerializableConstant deserialize(ByteBuffer buffer) {
115 switch (getBits()) {
116 case 1:
117 return JavaConstant.forBoolean(buffer.get() != 0);
118 case 8:
119 return JavaConstant.forByte(buffer.get());
120 case 16:
121 return JavaConstant.forShort(buffer.getShort());
122 case 32:
123 return JavaConstant.forInt(buffer.getInt());
124 case 64:
125 return JavaConstant.forLong(buffer.getLong());
126 default:
127 throw GraalError.shouldNotReachHere();
128 }
129 }
130
131 @Override
132 public boolean hasValues() {
133 return lowerBound <= upperBound;
134 }
135
136 @Override
137 public JavaKind getStackKind() {
138 if (getBits() > 32) {
139 return JavaKind.Long;
140 } else {
141 return JavaKind.Int;
142 }
143 }
144
145 @Override
146 public LIRKind getLIRKind(LIRKindTool tool) {
147 return tool.getIntegerKind(getBits());
148 }
149
150 @Override
151 public ResolvedJavaType javaType(MetaAccessProvider metaAccess) {
152 switch (getBits()) {
153 case 1:
154 return metaAccess.lookupJavaType(Boolean.TYPE);
155 case 8:
156 return metaAccess.lookupJavaType(Byte.TYPE);
157 case 16:
158 return metaAccess.lookupJavaType(Short.TYPE);
159 case 32:
160 return metaAccess.lookupJavaType(Integer.TYPE);
161 case 64:
162 return metaAccess.lookupJavaType(Long.TYPE);
163 default:
164 throw GraalError.shouldNotReachHere();
165 }
166 }
167
168 /**
169 * The signed inclusive lower bound on the value described by this stamp.
170 */
171 public long lowerBound() {
172 return lowerBound;
173 }
174
175 /**
176 * The signed inclusive upper bound on the value described by this stamp.
177 */
178 public long upperBound() {
179 return upperBound;
180 }
181
182 /**
183 * This bit-mask describes the bits that are always set in the value described by this stamp.
184 */
185 public long downMask() {
186 return downMask;
187 }
188
189 /**
190 * This bit-mask describes the bits that can be set in the value described by this stamp.
191 */
192 public long upMask() {
193 return upMask;
194 }
195
196 public boolean isUnrestricted() {
197 return lowerBound == CodeUtil.minValue(getBits()) && upperBound == CodeUtil.maxValue(getBits()) && downMask == 0 && upMask == CodeUtil.mask(getBits());
198 }
199
200 public boolean contains(long value) {
201 return value >= lowerBound && value <= upperBound && (value & downMask) == downMask && (value & upMask) == (value & CodeUtil.mask(getBits()));
202 }
203
204 public boolean isPositive() {
205 return lowerBound() >= 0;
206 }
207
208 public boolean isNegative() {
209 return upperBound() <= 0;
210 }
211
212 public boolean isStrictlyPositive() {
213 return lowerBound() > 0;
214 }
215
216 public boolean isStrictlyNegative() {
217 return upperBound() < 0;
218 }
219
220 public boolean canBePositive() {
221 return upperBound() > 0;
222 }
223
224 public boolean canBeNegative() {
225 return lowerBound() < 0;
226 }
227
228 @Override
229 public String toString() {
230 StringBuilder str = new StringBuilder();
231 str.append('i');
232 str.append(getBits());
233 if (lowerBound == upperBound) {
234 str.append(" [").append(lowerBound).append(']');
235 } else if (lowerBound != CodeUtil.minValue(getBits()) || upperBound != CodeUtil.maxValue(getBits())) {
236 str.append(" [").append(lowerBound).append(" - ").append(upperBound).append(']');
237 }
238 if (downMask != 0) {
239 str.append(" \u21ca");
240 new Formatter(str).format("%016x", downMask);
241 }
242 if (upMask != CodeUtil.mask(getBits())) {
243 str.append(" \u21c8");
244 new Formatter(str).format("%016x", upMask);
245 }
246 return str.toString();
247 }
248
249 private Stamp createStamp(IntegerStamp other, long newUpperBound, long newLowerBound, long newDownMask, long newUpMask) {
250 assert getBits() == other.getBits();
251 if (newLowerBound > newUpperBound || (newDownMask & (~newUpMask)) != 0 || (newUpMask == 0 && (newLowerBound > 0 || newUpperBound < 0))) {
252 return empty();
253 } else if (newLowerBound == lowerBound && newUpperBound == upperBound && newDownMask == downMask && newUpMask == upMask) {
254 return this;
255 } else if (newLowerBound == other.lowerBound && newUpperBound == other.upperBound && newDownMask == other.downMask && newUpMask == other.upMask) {
256 return other;
257 } else {
258 return new IntegerStamp(getBits(), newLowerBound, newUpperBound, newDownMask, newUpMask);
259 }
260 }
261
262 @Override
263 public Stamp meet(Stamp otherStamp) {
264 if (otherStamp == this) {
265 return this;
266 }
267 IntegerStamp other = (IntegerStamp) otherStamp;
268 return createStamp(other, Math.max(upperBound, other.upperBound), Math.min(lowerBound, other.lowerBound), downMask & other.downMask, upMask | other.upMask);
269 }
270
271 @Override
272 public Stamp join(Stamp otherStamp) {
273 if (otherStamp == this) {
274 return this;
275 }
276 IntegerStamp other = (IntegerStamp) otherStamp;
277 long newDownMask = downMask | other.downMask;
278 long newLowerBound = Math.max(lowerBound, other.lowerBound) | newDownMask;
279 long newUpperBound = Math.min(upperBound, other.upperBound);
280 long newUpMask = upMask & other.upMask;
281 IntegerStamp limit = StampFactory.forInteger(getBits(), newLowerBound, newUpperBound);
282 return createStamp(other, newUpperBound, newLowerBound, limit.downMask() | newDownMask, limit.upMask() & newUpMask);
283 }
284
285 @Override
286 public boolean isCompatible(Stamp stamp) {
287 if (this == stamp) {
288 return true;
289 }
290 if (stamp instanceof IntegerStamp) {
291 IntegerStamp other = (IntegerStamp) stamp;
292 return getBits() == other.getBits();
293 }
294 return false;
295 }
296
297 @Override
298 public boolean isCompatible(Constant constant) {
299 if (constant instanceof PrimitiveConstant) {
300 PrimitiveConstant prim = (PrimitiveConstant) constant;
301 return prim.getJavaKind().isNumericInteger();
302 }
303 return false;
304 }
305
306 @Override
307 public int hashCode() {
308 final int prime = 31;
309 int result = 1;
310 result = prime * result + super.hashCode();
311 result = prime * result + (int) (lowerBound ^ (lowerBound >>> 32));
312 result = prime * result + (int) (upperBound ^ (upperBound >>> 32));
313 result = prime * result + (int) (downMask ^ (downMask >>> 32));
314 result = prime * result + (int) (upMask ^ (upMask >>> 32));
315 return result;
316 }
317
318 @Override
319 public boolean equals(Object obj) {
320 if (this == obj) {
321 return true;
322 }
323 if (obj == null || getClass() != obj.getClass() || !super.equals(obj)) {
324 return false;
325 }
326 IntegerStamp other = (IntegerStamp) obj;
327 if (lowerBound != other.lowerBound || upperBound != other.upperBound || downMask != other.downMask || upMask != other.upMask) {
328 return false;
329 }
330 return super.equals(other);
331 }
332
333 public static long upMaskFor(int bits, long lowerBound, long upperBound) {
334 long mask = lowerBound | upperBound;
335 if (mask == 0) {
336 return 0;
337 } else {
338 return ((-1L) >>> Long.numberOfLeadingZeros(mask)) & CodeUtil.mask(bits);
339 }
340 }
341
342 /**
343 * Checks if the 2 stamps represent values of the same sign. Returns true if the two stamps are
344 * both positive of null or if they are both strictly negative
345 *
346 * @return true if the two stamps are both positive of null or if they are both strictly
347 * negative
348 */
349 public static boolean sameSign(IntegerStamp s1, IntegerStamp s2) {
350 return s1.isPositive() && s2.isPositive() || s1.isStrictlyNegative() && s2.isStrictlyNegative();
351 }
352
353 @Override
354 public JavaConstant asConstant() {
355 if (lowerBound == upperBound) {
356 switch (getBits()) {
357 case 1:
358 return JavaConstant.forBoolean(lowerBound != 0);
359 case 8:
360 return JavaConstant.forByte((byte) lowerBound);
361 case 16:
362 return JavaConstant.forShort((short) lowerBound);
363 case 32:
364 return JavaConstant.forInt((int) lowerBound);
365 case 64:
366 return JavaConstant.forLong(lowerBound);
367 }
368 }
369 return null;
370 }
371
372 public static boolean addOverflowsPositively(long x, long y, int bits) {
373 long result = x + y;
374 if (bits == 64) {
375 return (~x & ~y & result) < 0;
376 } else {
377 return result > CodeUtil.maxValue(bits);
378 }
379 }
380
381 public static boolean addOverflowsNegatively(long x, long y, int bits) {
382 long result = x + y;
383 if (bits == 64) {
384 return (x & y & ~result) < 0;
385 } else {
386 return result < CodeUtil.minValue(bits);
387 }
388 }
389
390 public static long carryBits(long x, long y) {
391 return (x + y) ^ x ^ y;
392 }
393
394 private static long saturate(long v, int bits) {
395 if (bits < 64) {
396 long max = CodeUtil.maxValue(bits);
397 if (v > max) {
398 return max;
399 }
400 long min = CodeUtil.minValue(bits);
401 if (v < min) {
402 return min;
403 }
404 }
405 return v;
406 }
407
408 public static boolean multiplicationOverflows(long a, long b, int bits) {
409 assert bits <= 64 && bits >= 0;
410 long result = a * b;
411 // result is positive if the sign is the same
412 boolean positive = (a >= 0 && b >= 0) || (a < 0 && b < 0);
413 if (bits == 64) {
414 if (a > 0 && b > 0) {
415 return a > 0x7FFFFFFF_FFFFFFFFL / b;
416 } else if (a > 0 && b <= 0) {
417 return b < 0x80000000_00000000L / a;
418 } else if (a <= 0 && b > 0) {
419 return a < 0x80000000_00000000L / b;
420 } else {
421 // a<=0 && b <=0
422 return a != 0 && b < 0x7FFFFFFF_FFFFFFFFL / a;
423 }
424 } else {
425 if (positive) {
426 return result > CodeUtil.maxValue(bits);
427 } else {
428 return result < CodeUtil.minValue(bits);
429 }
430 }
431 }
432
433 public static boolean subtractionCanOverflow(IntegerStamp x, IntegerStamp y) {
434 assert x.getBits() == y.getBits();
435 // Checkstyle: stop
436 long x_l = x.lowerBound();
437 long x_h = x.upperBound();
438 long y_l = y.lowerBound();
439 long y_h = y.upperBound();
440 // Checkstyle: resume
441 return subtractionOverflows(x_l, y_h, x.getBits()) || subtractionOverflows(x_h, y_l, x.getBits());
442 }
443
444 public static boolean subtractionOverflows(long x, long y, int bits) {
445 long result = x - y;
446 if (bits == 64) {
447 return (((x ^ y) & (x ^ result)) < 0);
448 }
449 return result < CodeUtil.minValue(bits) || result > CodeUtil.maxValue(bits);
450 }
451
452 public static final ArithmeticOpTable OPS = new ArithmeticOpTable(
453
454 new UnaryOp.Neg() {
455
456 @Override
457 public Constant foldConstant(Constant value) {
458 PrimitiveConstant c = (PrimitiveConstant) value;
459 return JavaConstant.forIntegerKind(c.getJavaKind(), -c.asLong());
460 }
461
462 @Override
463 public Stamp foldStamp(Stamp s) {
464 IntegerStamp stamp = (IntegerStamp) s;
465 int bits = stamp.getBits();
466 if (stamp.lowerBound() != CodeUtil.minValue(bits)) {
467 // TODO(ls) check if the mask calculation is correct...
468 return StampFactory.forInteger(bits, -stamp.upperBound(), -stamp.lowerBound());
469 } else {
470 return stamp.unrestricted();
471 }
472 }
473 },
474
475 new BinaryOp.Add(true, true) {
476
477 @Override
478 public Constant foldConstant(Constant const1, Constant const2) {
479 PrimitiveConstant a = (PrimitiveConstant) const1;
480 PrimitiveConstant b = (PrimitiveConstant) const2;
481 assert a.getJavaKind() == b.getJavaKind();
482 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() + b.asLong());
483 }
484
485 @Override
486 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
487 IntegerStamp a = (IntegerStamp) stamp1;
488 IntegerStamp b = (IntegerStamp) stamp2;
489
490 int bits = a.getBits();
491 assert bits == b.getBits();
492
493 if (a.isUnrestricted()) {
494 return a;
495 } else if (b.isUnrestricted()) {
496 return b;
497 }
498 long defaultMask = CodeUtil.mask(bits);
499 long variableBits = (a.downMask() ^ a.upMask()) | (b.downMask() ^ b.upMask());
500 long variableBitsWithCarry = variableBits | (carryBits(a.downMask(), b.downMask()) ^ carryBits(a.upMask(), b.upMask()));
501 long newDownMask = (a.downMask() + b.downMask()) & ~variableBitsWithCarry;
502 long newUpMask = (a.downMask() + b.downMask()) | variableBitsWithCarry;
503
504 newDownMask &= defaultMask;
505 newUpMask &= defaultMask;
506
507 long newLowerBound;
508 long newUpperBound;
509 boolean lowerOverflowsPositively = addOverflowsPositively(a.lowerBound(), b.lowerBound(), bits);
510 boolean upperOverflowsPositively = addOverflowsPositively(a.upperBound(), b.upperBound(), bits);
511 boolean lowerOverflowsNegatively = addOverflowsNegatively(a.lowerBound(), b.lowerBound(), bits);
512 boolean upperOverflowsNegatively = addOverflowsNegatively(a.upperBound(), b.upperBound(), bits);
513 if ((lowerOverflowsNegatively && !upperOverflowsNegatively) || (!lowerOverflowsPositively && upperOverflowsPositively)) {
514 newLowerBound = CodeUtil.minValue(bits);
515 newUpperBound = CodeUtil.maxValue(bits);
516 } else {
517 newLowerBound = CodeUtil.signExtend((a.lowerBound() + b.lowerBound()) & defaultMask, bits);
518 newUpperBound = CodeUtil.signExtend((a.upperBound() + b.upperBound()) & defaultMask, bits);
519 }
520 IntegerStamp limit = StampFactory.forInteger(bits, newLowerBound, newUpperBound);
521 newUpMask &= limit.upMask();
522 newUpperBound = CodeUtil.signExtend(newUpperBound & newUpMask, bits);
523 newDownMask |= limit.downMask();
524 newLowerBound |= newDownMask;
525 return new IntegerStamp(bits, newLowerBound, newUpperBound, newDownMask, newUpMask);
526 }
527
528 @Override
529 public boolean isNeutral(Constant value) {
530 PrimitiveConstant n = (PrimitiveConstant) value;
531 return n.asLong() == 0;
532 }
533 },
534
535 new BinaryOp.Sub(true, false) {
536
537 @Override
538 public Constant foldConstant(Constant const1, Constant const2) {
539 PrimitiveConstant a = (PrimitiveConstant) const1;
540 PrimitiveConstant b = (PrimitiveConstant) const2;
541 assert a.getJavaKind() == b.getJavaKind();
542 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() - b.asLong());
543 }
544
545 @Override
546 public Stamp foldStamp(Stamp a, Stamp b) {
547 return OPS.getAdd().foldStamp(a, OPS.getNeg().foldStamp(b));
548 }
549
550 @Override
551 public boolean isNeutral(Constant value) {
552 PrimitiveConstant n = (PrimitiveConstant) value;
553 return n.asLong() == 0;
554 }
555
556 @Override
557 public Constant getZero(Stamp s) {
558 IntegerStamp stamp = (IntegerStamp) s;
559 return JavaConstant.forPrimitiveInt(stamp.getBits(), 0);
560 }
561 },
562
563 new BinaryOp.Mul(true, true) {
564
565 @Override
566 public Constant foldConstant(Constant const1, Constant const2) {
567 PrimitiveConstant a = (PrimitiveConstant) const1;
568 PrimitiveConstant b = (PrimitiveConstant) const2;
569 assert a.getJavaKind() == b.getJavaKind();
570 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() * b.asLong());
571 }
572
573 @Override
574 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
575 IntegerStamp a = (IntegerStamp) stamp1;
576 IntegerStamp b = (IntegerStamp) stamp2;
577
578 int bits = a.getBits();
579 assert bits == b.getBits();
580 // if a==0 or b==0 result of a*b is always 0
581 if (a.upMask() == 0) {
582 return a;
583 } else if (b.upMask() == 0) {
584 return b;
585 } else {
586 // if a has the full range or b, the result will also have it
587 if (a.isUnrestricted()) {
588 return a;
589 } else if (b.isUnrestricted()) {
590 return b;
591 }
592 // a!=0 && b !=0 holds
593 long newLowerBound = Long.MAX_VALUE;
594 long newUpperBound = Long.MIN_VALUE;
595 /*
596 * Based on the signs of the incoming stamps lower and upper bound
597 * of the result of the multiplication may be swapped. LowerBound
598 * can become upper bound if both signs are negative, and so on. To
599 * determine the new values for lower and upper bound we need to
600 * look at the max and min of the cases blow:
601 *
602 * @formatter:off
603 *
604 * a.lowerBound * b.lowerBound
605 * a.lowerBound * b.upperBound
606 * a.upperBound * b.lowerBound
607 * a.upperBound * b.upperBound
608 *
609 * @formatter:on
610 *
611 * We are only interested in those cases that are relevant due to
612 * the sign of the involved stamps (whether a stamp includes
613 * negative and / or positive values). Based on the signs, the maximum
614 * or minimum of the above multiplications form the new lower and
615 * upper bounds.
616 *
617 * The table below contains the interesting candidates for lower and
618 * upper bound after multiplication.
619 *
620 * For example if we consider two stamps a & b that both contain
621 * negative and positive values, the product of minN_a * minN_b
622 * (both the smallest negative value for each stamp) can only be the
623 * highest positive number. The other candidates can be computed in
624 * a similar fashion. Some of them can never be a new minimum or
625 * maximum and are therefore excluded.
626 *
627 *
628 * @formatter:off
629 *
630 * [x..........0..........y]
631 * -------------------------
632 * [minN maxN minP maxP]
633 * where maxN = min(0,y) && minP = max(0,x)
634 *
635 *
636 * |minN_a maxN_a minP_a maxP_a
637 * _______|________________________________
638 * minN_b |MAX / : / MIN
639 * maxN_b | / MIN : MAX /
640 * |---------------+----------------
641 * minP_b | / MAX : MIN /
642 * maxP_b |MIN / : / MAX
643 *
644 * @formatter:on
645 */
646 // We materialize all factors here. If they are needed, the signs of
647 // the stamp will ensure the correct value is used.
648 // Checkstyle: stop
649 long minN_a = a.lowerBound();
650 long maxN_a = Math.min(0, a.upperBound());
651 long minP_a = Math.max(0, a.lowerBound());
652 long maxP_a = a.upperBound();
653
654 long minN_b = b.lowerBound();
655 long maxN_b = Math.min(0, b.upperBound());
656 long minP_b = Math.max(0, b.lowerBound());
657 long maxP_b = b.upperBound();
658 // Checkstyle: resume
659
660 // multiplication has shift semantics
661 long newUpMask = ~CodeUtil.mask(Long.numberOfTrailingZeros(a.upMask) + Long.numberOfTrailingZeros(b.upMask)) & CodeUtil.mask(bits);
662
663 if (a.canBePositive()) {
664 if (b.canBePositive()) {
665 if (multiplicationOverflows(maxP_a, maxP_b, bits)) {
666 return a.unrestricted();
667 }
668 long maxCandidate = maxP_a * maxP_b;
669 if (multiplicationOverflows(minP_a, minP_b, bits)) {
670 return a.unrestricted();
671 }
672 long minCandidate = minP_a * minP_b;
673 newLowerBound = Math.min(newLowerBound, minCandidate);
674 newUpperBound = Math.max(newUpperBound, maxCandidate);
675 }
676 if (b.canBeNegative()) {
677 if (multiplicationOverflows(minP_a, maxN_b, bits)) {
678 return a.unrestricted();
679 }
680 long maxCandidate = minP_a * maxN_b;
681 if (multiplicationOverflows(maxP_a, minN_b, bits)) {
682 return a.unrestricted();
683 }
684 long minCandidate = maxP_a * minN_b;
685 newLowerBound = Math.min(newLowerBound, minCandidate);
686 newUpperBound = Math.max(newUpperBound, maxCandidate);
687 }
688 }
689 if (a.canBeNegative()) {
690 if (b.canBePositive()) {
691 if (multiplicationOverflows(maxN_a, minP_b, bits)) {
692 return a.unrestricted();
693 }
694 long maxCandidate = maxN_a * minP_b;
695 if (multiplicationOverflows(minN_a, maxP_b, bits)) {
696 return a.unrestricted();
697 }
698 long minCandidate = minN_a * maxP_b;
699 newLowerBound = Math.min(newLowerBound, minCandidate);
700 newUpperBound = Math.max(newUpperBound, maxCandidate);
701 }
702 if (b.canBeNegative()) {
703 if (multiplicationOverflows(minN_a, minN_b, bits)) {
704 return a.unrestricted();
705 }
706 long maxCandidate = minN_a * minN_b;
707 if (multiplicationOverflows(maxN_a, maxN_b, bits)) {
708 return a.unrestricted();
709 }
710 long minCandidate = maxN_a * maxN_b;
711 newLowerBound = Math.min(newLowerBound, minCandidate);
712 newUpperBound = Math.max(newUpperBound, maxCandidate);
713 }
714 }
715
716 assert newLowerBound <= newUpperBound;
717 return StampFactory.forIntegerWithMask(bits, newLowerBound, newUpperBound, 0, newUpMask);
718 }
719 }
720
721 @Override
722 public boolean isNeutral(Constant value) {
723 PrimitiveConstant n = (PrimitiveConstant) value;
724 return n.asLong() == 1;
725 }
726 },
727
728 new BinaryOp.Div(true, false) {
729
730 @Override
731 public Constant foldConstant(Constant const1, Constant const2) {
732 PrimitiveConstant a = (PrimitiveConstant) const1;
733 PrimitiveConstant b = (PrimitiveConstant) const2;
734 assert a.getJavaKind() == b.getJavaKind();
735 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() / b.asLong());
736 }
737
738 @Override
739 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
740 IntegerStamp a = (IntegerStamp) stamp1;
741 IntegerStamp b = (IntegerStamp) stamp2;
742 assert a.getBits() == b.getBits();
743 if (b.isStrictlyPositive()) {
744 long newLowerBound = a.lowerBound() / b.upperBound();
745 long newUpperBound = a.upperBound() / b.lowerBound();
746 return StampFactory.forInteger(a.getBits(), newLowerBound, newUpperBound);
747 } else {
748 return a.unrestricted();
749 }
750 }
751
752 @Override
753 public boolean isNeutral(Constant value) {
754 PrimitiveConstant n = (PrimitiveConstant) value;
755 return n.asLong() == 1;
756 }
757 },
758
759 new BinaryOp.Rem(false, false) {
760
761 @Override
762 public Constant foldConstant(Constant const1, Constant const2) {
763 PrimitiveConstant a = (PrimitiveConstant) const1;
764 PrimitiveConstant b = (PrimitiveConstant) const2;
765 assert a.getJavaKind() == b.getJavaKind();
766 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() % b.asLong());
767 }
768
769 @Override
770 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
771 IntegerStamp a = (IntegerStamp) stamp1;
772 IntegerStamp b = (IntegerStamp) stamp2;
773 assert a.getBits() == b.getBits();
774 // zero is always possible
775 long newLowerBound = Math.min(a.lowerBound(), 0);
776 long newUpperBound = Math.max(a.upperBound(), 0);
777
778 /* the maximum absolute value of the result, derived from b */
779 long magnitude;
780 if (b.lowerBound() == CodeUtil.minValue(b.getBits())) {
781 // Math.abs(...) - 1 does not work in a case
782 magnitude = CodeUtil.maxValue(b.getBits());
783 } else {
784 magnitude = Math.max(Math.abs(b.lowerBound()), Math.abs(b.upperBound())) - 1;
785 }
786 newLowerBound = Math.max(newLowerBound, -magnitude);
787 newUpperBound = Math.min(newUpperBound, magnitude);
788
789 return StampFactory.forInteger(a.getBits(), newLowerBound, newUpperBound);
790 }
791 },
792
793 new UnaryOp.Not() {
794
795 @Override
796 public Constant foldConstant(Constant c) {
797 PrimitiveConstant value = (PrimitiveConstant) c;
798 return JavaConstant.forIntegerKind(value.getJavaKind(), ~value.asLong());
799 }
800
801 @Override
802 public Stamp foldStamp(Stamp stamp) {
803 IntegerStamp integerStamp = (IntegerStamp) stamp;
804 int bits = integerStamp.getBits();
805 long defaultMask = CodeUtil.mask(bits);
806 return new IntegerStamp(bits, ~integerStamp.upperBound(), ~integerStamp.lowerBound(), (~integerStamp.upMask()) & defaultMask, (~integerStamp.downMask()) & defaultMask);
807 }
808 },
809
810 new BinaryOp.And(true, true) {
811
812 @Override
813 public Constant foldConstant(Constant const1, Constant const2) {
814 PrimitiveConstant a = (PrimitiveConstant) const1;
815 PrimitiveConstant b = (PrimitiveConstant) const2;
816 assert a.getJavaKind() == b.getJavaKind();
817 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() & b.asLong());
818 }
819
820 @Override
821 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
822 IntegerStamp a = (IntegerStamp) stamp1;
823 IntegerStamp b = (IntegerStamp) stamp2;
824 assert a.getBits() == b.getBits();
825 return stampForMask(a.getBits(), a.downMask() & b.downMask(), a.upMask() & b.upMask());
826 }
827
828 @Override
829 public boolean isNeutral(Constant value) {
830 PrimitiveConstant n = (PrimitiveConstant) value;
831 int bits = n.getJavaKind().getBitCount();
832 long mask = CodeUtil.mask(bits);
833 return (n.asLong() & mask) == mask;
834 }
835 },
836
837 new BinaryOp.Or(true, true) {
838
839 @Override
840 public Constant foldConstant(Constant const1, Constant const2) {
841 PrimitiveConstant a = (PrimitiveConstant) const1;
842 PrimitiveConstant b = (PrimitiveConstant) const2;
843 assert a.getJavaKind() == b.getJavaKind();
844 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() | b.asLong());
845 }
846
847 @Override
848 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
849 IntegerStamp a = (IntegerStamp) stamp1;
850 IntegerStamp b = (IntegerStamp) stamp2;
851 assert a.getBits() == b.getBits();
852 return stampForMask(a.getBits(), a.downMask() | b.downMask(), a.upMask() | b.upMask());
853 }
854
855 @Override
856 public boolean isNeutral(Constant value) {
857 PrimitiveConstant n = (PrimitiveConstant) value;
858 return n.asLong() == 0;
859 }
860 },
861
862 new BinaryOp.Xor(true, true) {
863
864 @Override
865 public Constant foldConstant(Constant const1, Constant const2) {
866 PrimitiveConstant a = (PrimitiveConstant) const1;
867 PrimitiveConstant b = (PrimitiveConstant) const2;
868 assert a.getJavaKind() == b.getJavaKind();
869 return JavaConstant.forIntegerKind(a.getJavaKind(), a.asLong() ^ b.asLong());
870 }
871
872 @Override
873 public Stamp foldStamp(Stamp stamp1, Stamp stamp2) {
874 IntegerStamp a = (IntegerStamp) stamp1;
875 IntegerStamp b = (IntegerStamp) stamp2;
876 assert a.getBits() == b.getBits();
877
878 long variableBits = (a.downMask() ^ a.upMask()) | (b.downMask() ^ b.upMask());
879 long newDownMask = (a.downMask() ^ b.downMask()) & ~variableBits;
880 long newUpMask = (a.downMask() ^ b.downMask()) | variableBits;
881 return stampForMask(a.getBits(), newDownMask, newUpMask);
882 }
883
884 @Override
885 public boolean isNeutral(Constant value) {
886 PrimitiveConstant n = (PrimitiveConstant) value;
887 return n.asLong() == 0;
888 }
889
890 @Override
891 public Constant getZero(Stamp s) {
892 IntegerStamp stamp = (IntegerStamp) s;
893 return JavaConstant.forPrimitiveInt(stamp.getBits(), 0);
894 }
895 },
896
897 new ShiftOp.Shl() {
898
899 @Override
900 public Constant foldConstant(Constant value, int amount) {
901 PrimitiveConstant c = (PrimitiveConstant) value;
902 switch (c.getJavaKind()) {
903 case Int:
904 return JavaConstant.forInt(c.asInt() << amount);
905 case Long:
906 return JavaConstant.forLong(c.asLong() << amount);
907 default:
908 throw GraalError.shouldNotReachHere();
909 }
910 }
911
912 @Override
913 public Stamp foldStamp(Stamp stamp, IntegerStamp shift) {
914 IntegerStamp value = (IntegerStamp) stamp;
915 int bits = value.getBits();
916 long defaultMask = CodeUtil.mask(bits);
917 if (value.upMask() == 0) {
918 return value;
919 }
920 int shiftMask = getShiftAmountMask(stamp);
921 int shiftBits = Integer.bitCount(shiftMask);
922 if (shift.lowerBound() == shift.upperBound()) {
923 int shiftAmount = (int) (shift.lowerBound() & shiftMask);
924 if (shiftAmount == 0) {
925 return value;
926 }
927 // the mask of bits that will be lost or shifted into the sign bit
928 long removedBits = -1L << (bits - shiftAmount - 1);
929 if ((value.lowerBound() & removedBits) == 0 && (value.upperBound() & removedBits) == 0) {
930 /*
931 * use a better stamp if neither lower nor upper bound can lose
932 * bits
933 */
934 return new IntegerStamp(bits, value.lowerBound() << shiftAmount, value.upperBound() << shiftAmount, value.downMask() << shiftAmount, value.upMask() << shiftAmount);
935 }
936 }
937 if ((shift.lowerBound() >>> shiftBits) == (shift.upperBound() >>> shiftBits)) {
938 long downMask = defaultMask;
939 long upMask = 0;
940 for (long i = shift.lowerBound(); i <= shift.upperBound(); i++) {
941 if (shift.contains(i)) {
942 downMask &= value.downMask() << (i & shiftMask);
943 upMask |= value.upMask() << (i & shiftMask);
944 }
945 }
946 Stamp result = IntegerStamp.stampForMask(bits, downMask, upMask & defaultMask);
947 return result;
948 }
949 return value.unrestricted();
950 }
951
952 @Override
953 public int getShiftAmountMask(Stamp s) {
954 IntegerStamp stamp = (IntegerStamp) s;
955 assert CodeUtil.isPowerOf2(stamp.getBits());
956 return stamp.getBits() - 1;
957 }
958 },
959
960 new ShiftOp.Shr() {
961
962 @Override
963 public Constant foldConstant(Constant value, int amount) {
964 PrimitiveConstant c = (PrimitiveConstant) value;
965 switch (c.getJavaKind()) {
966 case Int:
967 return JavaConstant.forInt(c.asInt() >> amount);
968 case Long:
969 return JavaConstant.forLong(c.asLong() >> amount);
970 default:
971 throw GraalError.shouldNotReachHere();
972 }
973 }
974
975 @Override
976 public Stamp foldStamp(Stamp stamp, IntegerStamp shift) {
977 IntegerStamp value = (IntegerStamp) stamp;
978 int bits = value.getBits();
979 if (shift.lowerBound() == shift.upperBound()) {
980 long shiftCount = shift.lowerBound() & getShiftAmountMask(stamp);
981 if (shiftCount == 0) {
982 return stamp;
983 }
984
985 int extraBits = 64 - bits;
986 long defaultMask = CodeUtil.mask(bits);
987 // shifting back and forth performs sign extension
988 long downMask = (value.downMask() << extraBits) >> (shiftCount + extraBits) & defaultMask;
989 long upMask = (value.upMask() << extraBits) >> (shiftCount + extraBits) & defaultMask;
990 return new IntegerStamp(bits, value.lowerBound() >> shiftCount, value.upperBound() >> shiftCount, downMask, upMask);
991 }
992 long mask = IntegerStamp.upMaskFor(bits, value.lowerBound(), value.upperBound());
993 return IntegerStamp.stampForMask(bits, 0, mask);
994 }
995
996 @Override
997 public int getShiftAmountMask(Stamp s) {
998 IntegerStamp stamp = (IntegerStamp) s;
999 assert CodeUtil.isPowerOf2(stamp.getBits());
1000 return stamp.getBits() - 1;
1001 }
1002 },
1003
1004 new ShiftOp.UShr() {
1005
1006 @Override
1007 public Constant foldConstant(Constant value, int amount) {
1008 PrimitiveConstant c = (PrimitiveConstant) value;
1009 switch (c.getJavaKind()) {
1010 case Int:
1011 return JavaConstant.forInt(c.asInt() >>> amount);
1012 case Long:
1013 return JavaConstant.forLong(c.asLong() >>> amount);
1014 default:
1015 throw GraalError.shouldNotReachHere();
1016 }
1017 }
1018
1019 @Override
1020 public Stamp foldStamp(Stamp stamp, IntegerStamp shift) {
1021 IntegerStamp value = (IntegerStamp) stamp;
1022 int bits = value.getBits();
1023 if (shift.lowerBound() == shift.upperBound()) {
1024 long shiftCount = shift.lowerBound() & getShiftAmountMask(stamp);
1025 if (shiftCount == 0) {
1026 return stamp;
1027 }
1028
1029 long downMask = value.downMask() >>> shiftCount;
1030 long upMask = value.upMask() >>> shiftCount;
1031 if (value.lowerBound() < 0) {
1032 return new IntegerStamp(bits, downMask, upMask, downMask, upMask);
1033 } else {
1034 return new IntegerStamp(bits, value.lowerBound() >>> shiftCount, value.upperBound() >>> shiftCount, downMask, upMask);
1035 }
1036 }
1037 long mask = IntegerStamp.upMaskFor(bits, value.lowerBound(), value.upperBound());
1038 return IntegerStamp.stampForMask(bits, 0, mask);
1039 }
1040
1041 @Override
1042 public int getShiftAmountMask(Stamp s) {
1043 IntegerStamp stamp = (IntegerStamp) s;
1044 assert CodeUtil.isPowerOf2(stamp.getBits());
1045 return stamp.getBits() - 1;
1046 }
1047 },
1048
1049 new UnaryOp.Abs() {
1050
1051 @Override
1052 public Constant foldConstant(Constant value) {
1053 PrimitiveConstant c = (PrimitiveConstant) value;
1054 return JavaConstant.forIntegerKind(c.getJavaKind(), Math.abs(c.asLong()));
1055 }
1056
1057 @Override
1058 public Stamp foldStamp(Stamp input) {
1059 IntegerStamp stamp = (IntegerStamp) input;
1060 int bits = stamp.getBits();
1061 if (stamp.lowerBound() == CodeUtil.minValue(bits)) {
1062 return input.unrestricted();
1063 } else {
1064 long limit = Math.max(-stamp.lowerBound(), stamp.upperBound());
1065 return StampFactory.forInteger(bits, 0, limit);
1066 }
1067 }
1068 },
1069
1070 null,
1071
1072 new IntegerConvertOp.ZeroExtend() {
1073
1074 @Override
1075 public Constant foldConstant(int inputBits, int resultBits, Constant c) {
1076 PrimitiveConstant value = (PrimitiveConstant) c;
1077 return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.zeroExtend(value.asLong(), inputBits));
1078 }
1079
1080 @Override
1081 public Stamp foldStamp(int inputBits, int resultBits, Stamp input) {
1082 IntegerStamp stamp = (IntegerStamp) input;
1083 assert inputBits == stamp.getBits();
1084 assert inputBits <= resultBits;
1085
1086 long downMask = CodeUtil.zeroExtend(stamp.downMask(), inputBits);
1087 long upMask = CodeUtil.zeroExtend(stamp.upMask(), inputBits);
1088
1089 if (stamp.lowerBound() < 0 && stamp.upperBound() >= 0) {
1090 /* signed range including 0 and -1 */
1091 /*
1092 * after sign extension, the whole range from 0 to MAX_INT is
1093 * possible
1094 */
1095 return IntegerStamp.stampForMask(resultBits, downMask, upMask);
1096 }
1097
1098 long lowerBound = CodeUtil.zeroExtend(stamp.lowerBound(), inputBits);
1099 long upperBound = CodeUtil.zeroExtend(stamp.upperBound(), inputBits);
1100
1101 return new IntegerStamp(resultBits, lowerBound, upperBound, downMask, upMask);
1102 }
1103 },
1104
1105 new IntegerConvertOp.SignExtend() {
1106
1107 @Override
1108 public Constant foldConstant(int inputBits, int resultBits, Constant c) {
1109 PrimitiveConstant value = (PrimitiveConstant) c;
1110 return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.signExtend(value.asLong(), inputBits));
1111 }
1112
1113 @Override
1114 public Stamp foldStamp(int inputBits, int resultBits, Stamp input) {
1115 IntegerStamp stamp = (IntegerStamp) input;
1116 assert inputBits == stamp.getBits();
1117 assert inputBits <= resultBits;
1118
1119 long defaultMask = CodeUtil.mask(resultBits);
1120 long downMask = CodeUtil.signExtend(stamp.downMask(), inputBits) & defaultMask;
1121 long upMask = CodeUtil.signExtend(stamp.upMask(), inputBits) & defaultMask;
1122
1123 return new IntegerStamp(resultBits, stamp.lowerBound(), stamp.upperBound(), downMask, upMask);
1124 }
1125 },
1126
1127 new IntegerConvertOp.Narrow() {
1128
1129 @Override
1130 public Constant foldConstant(int inputBits, int resultBits, Constant c) {
1131 PrimitiveConstant value = (PrimitiveConstant) c;
1132 return JavaConstant.forPrimitiveInt(resultBits, CodeUtil.narrow(value.asLong(), resultBits));
1133 }
1134
1135 @Override
1136 public Stamp foldStamp(int inputBits, int resultBits, Stamp input) {
1137 IntegerStamp stamp = (IntegerStamp) input;
1138 assert inputBits == stamp.getBits();
1139 assert resultBits <= inputBits;
1140 if (resultBits == inputBits) {
1141 return stamp;
1142 }
1143
1144 final long upperBound;
1145 if (stamp.lowerBound() < CodeUtil.minValue(resultBits)) {
1146 upperBound = CodeUtil.maxValue(resultBits);
1147 } else {
1148 upperBound = saturate(stamp.upperBound(), resultBits);
1149 }
1150 final long lowerBound;
1151 if (stamp.upperBound() > CodeUtil.maxValue(resultBits)) {
1152 lowerBound = CodeUtil.minValue(resultBits);
1153 } else {
1154 lowerBound = saturate(stamp.lowerBound(), resultBits);
1155 }
1156
1157 long defaultMask = CodeUtil.mask(resultBits);
1158 long newDownMask = stamp.downMask() & defaultMask;
1159 long newUpMask = stamp.upMask() & defaultMask;
1160 long newLowerBound = CodeUtil.signExtend((lowerBound | newDownMask) & newUpMask, resultBits);
1161 long newUpperBound = CodeUtil.signExtend((upperBound | newDownMask) & newUpMask, resultBits);
1162 return new IntegerStamp(resultBits, newLowerBound, newUpperBound, newDownMask, newUpMask);
1163 }
1164 },
1165
1166 new FloatConvertOp(I2F) {
1167
1168 @Override
1169 public Constant foldConstant(Constant c) {
1170 PrimitiveConstant value = (PrimitiveConstant) c;
1171 return JavaConstant.forFloat(value.asInt());
1172 }
1173
1174 @Override
1175 public Stamp foldStamp(Stamp input) {
1176 IntegerStamp stamp = (IntegerStamp) input;
1177 assert stamp.getBits() == 32;
1178 float lowerBound = stamp.lowerBound();
1179 float upperBound = stamp.upperBound();
1180 return StampFactory.forFloat(JavaKind.Float, lowerBound, upperBound, true);
1181 }
1182 },
1183
1184 new FloatConvertOp(L2F) {
1185
1186 @Override
1187 public Constant foldConstant(Constant c) {
1188 PrimitiveConstant value = (PrimitiveConstant) c;
1189 return JavaConstant.forFloat(value.asLong());
1190 }
1191
1192 @Override
1193 public Stamp foldStamp(Stamp input) {
1194 IntegerStamp stamp = (IntegerStamp) input;
1195 assert stamp.getBits() == 64;
1196 float lowerBound = stamp.lowerBound();
1197 float upperBound = stamp.upperBound();
1198 return StampFactory.forFloat(JavaKind.Float, lowerBound, upperBound, true);
1199 }
1200 },
1201
1202 new FloatConvertOp(I2D) {
1203
1204 @Override
1205 public Constant foldConstant(Constant c) {
1206 PrimitiveConstant value = (PrimitiveConstant) c;
1207 return JavaConstant.forDouble(value.asInt());
1208 }
1209
1210 @Override
1211 public Stamp foldStamp(Stamp input) {
1212 IntegerStamp stamp = (IntegerStamp) input;
1213 assert stamp.getBits() == 32;
1214 double lowerBound = stamp.lowerBound();
1215 double upperBound = stamp.upperBound();
1216 return StampFactory.forFloat(JavaKind.Double, lowerBound, upperBound, true);
1217 }
1218 },
1219
1220 new FloatConvertOp(L2D) {
1221
1222 @Override
1223 public Constant foldConstant(Constant c) {
1224 PrimitiveConstant value = (PrimitiveConstant) c;
1225 return JavaConstant.forDouble(value.asLong());
1226 }
1227
1228 @Override
1229 public Stamp foldStamp(Stamp input) {
1230 IntegerStamp stamp = (IntegerStamp) input;
1231 assert stamp.getBits() == 64;
1232 double lowerBound = stamp.lowerBound();
1233 double upperBound = stamp.upperBound();
1234 return StampFactory.forFloat(JavaKind.Double, lowerBound, upperBound, true);
1235 }
1236 });
1237 }