Mercurial > hg > truffle

comparison graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampTool.java @ 15131:9c1e53adc159

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Remove unsigned flag from IntegerStamp.
author Roland Schatz <roland.schatz@oracle.com>
date Tue, 15 Apr 2014 19:08:29 +0200
parents ea712c41c5a2
children 844cfee4041a
comparison
equal deleted inserted replaced
15130:ec22234bde0d 15131:9c1e53adc159
51 51
52 public static Stamp negate(Stamp stamp) { 52 public static Stamp negate(Stamp stamp) {
53 if (stamp instanceof IntegerStamp) { 53 if (stamp instanceof IntegerStamp) {
54 IntegerStamp integerStamp = (IntegerStamp) stamp; 54 IntegerStamp integerStamp = (IntegerStamp) stamp;
55 int bits = integerStamp.getBits(); 55 int bits = integerStamp.getBits();
56 if (integerStamp.lowerBound() != IntegerStamp.defaultMinValue(bits, false)) { 56 if (integerStamp.lowerBound() != IntegerStamp.defaultMinValue(bits)) {
57 // TODO(ls) check if the mask calculation is correct... 57 // TODO(ls) check if the mask calculation is correct...
58 return StampFactory.forInteger(bits, false, -integerStamp.upperBound(), -integerStamp.lowerBound()); 58 return StampFactory.forInteger(bits, -integerStamp.upperBound(), -integerStamp.lowerBound());
59 } 59 }
60 } else if (stamp instanceof FloatStamp) { 60 } else if (stamp instanceof FloatStamp) {
61 FloatStamp floatStamp = (FloatStamp) stamp; 61 FloatStamp floatStamp = (FloatStamp) stamp;
62 return new FloatStamp(floatStamp.getBits(), -floatStamp.upperBound(), -floatStamp.lowerBound(), floatStamp.isNonNaN()); 62 return new FloatStamp(floatStamp.getBits(), -floatStamp.upperBound(), -floatStamp.lowerBound(), floatStamp.isNonNaN());
63 } 63 }
68 public static Stamp not(Stamp stamp) { 68 public static Stamp not(Stamp stamp) {
69 if (stamp instanceof IntegerStamp) { 69 if (stamp instanceof IntegerStamp) {
70 IntegerStamp integerStamp = (IntegerStamp) stamp; 70 IntegerStamp integerStamp = (IntegerStamp) stamp;
71 int bits = integerStamp.getBits(); 71 int bits = integerStamp.getBits();
72 long defaultMask = IntegerStamp.defaultMask(bits); 72 long defaultMask = IntegerStamp.defaultMask(bits);
73 return new IntegerStamp(bits, integerStamp.isUnsigned(), ~integerStamp.upperBound(), ~integerStamp.lowerBound(), (~integerStamp.upMask()) & defaultMask, (~integerStamp.downMask()) & 73 return new IntegerStamp(bits, ~integerStamp.upperBound(), ~integerStamp.lowerBound(), (~integerStamp.upMask()) & defaultMask, (~integerStamp.downMask()) & defaultMask);
74 defaultMask);
75 } 74 }
76 return stamp.unrestricted(); 75 return stamp.unrestricted();
77 } 76 }
78 77
79 public static Stamp meet(Collection<? extends StampProvider> values) { 78 public static Stamp meet(Collection<? extends StampProvider> values) {
110 } 109 }
111 return joinIllegal(stamp1, stamp2); 110 return joinIllegal(stamp1, stamp2);
112 } 111 }
113 112
114 public static Stamp div(IntegerStamp stamp1, IntegerStamp stamp2) { 113 public static Stamp div(IntegerStamp stamp1, IntegerStamp stamp2) {
115 assert stamp1.getBits() == stamp2.getBits() && stamp1.isUnsigned() == stamp2.isUnsigned(); 114 assert stamp1.getBits() == stamp2.getBits();
116 if (stamp2.isStrictlyPositive()) { 115 if (stamp2.isStrictlyPositive()) {
117 long lowerBound = stamp1.lowerBound() / stamp2.lowerBound(); 116 long lowerBound = stamp1.lowerBound() / stamp2.lowerBound();
118 long upperBound = stamp1.upperBound() / stamp2.lowerBound(); 117 long upperBound = stamp1.upperBound() / stamp2.lowerBound();
119 return StampFactory.forInteger(stamp1.getBits(), stamp1.isUnsigned(), lowerBound, upperBound); 118 return StampFactory.forInteger(stamp1.getBits(), lowerBound, upperBound);
120 } 119 }
121 return stamp1.unrestricted(); 120 return stamp1.unrestricted();
122 } 121 }
123 122
124 private static boolean addOverflowsPositively(long x, long y, int bits, boolean unsigned) { 123 private static boolean addOverflowsPositively(long x, long y, int bits) {
125 long result = x + y; 124 long result = x + y;
126 if (bits == 64) { 125 if (bits == 64) {
127 if (unsigned) { 126 return (~x & ~y & result) < 0;
128 return ((x | y) & ~result) < 0; 127 } else {
129 } else { 128 return result > IntegerStamp.defaultMaxValue(bits);
130 return (~x & ~y & result) < 0; 129 }
131 } 130 }
132 } else { 131
133 return result > IntegerStamp.defaultMaxValue(bits, unsigned); 132 private static boolean addOverflowsNegatively(long x, long y, int bits) {
134 }
135 }
136
137 private static boolean addOverflowsNegatively(long x, long y, int bits, boolean unsigned) {
138 if (unsigned) {
139 return false;
140 }
141
142 long result = x + y; 133 long result = x + y;
143 if (bits == 64) { 134 if (bits == 64) {
144 return (x & y & ~result) < 0; 135 return (x & y & ~result) < 0;
145 } else { 136 } else {
146 return result < IntegerStamp.defaultMinValue(bits, unsigned); 137 return result < IntegerStamp.defaultMinValue(bits);
147 } 138 }
148 } 139 }
149 140
150 public static IntegerStamp add(IntegerStamp stamp1, IntegerStamp stamp2) { 141 public static IntegerStamp add(IntegerStamp stamp1, IntegerStamp stamp2) {
151 int bits = stamp1.getBits(); 142 int bits = stamp1.getBits();
152 boolean unsigned = stamp1.isUnsigned(); 143 assert bits == stamp2.getBits();
153 assert bits == stamp2.getBits() && unsigned == stamp2.isUnsigned();
154 144
155 if (stamp1.isUnrestricted()) { 145 if (stamp1.isUnrestricted()) {
156 return stamp1; 146 return stamp1;
157 } else if (stamp2.isUnrestricted()) { 147 } else if (stamp2.isUnrestricted()) {
158 return stamp2; 148 return stamp2;
166 newDownMask &= defaultMask; 156 newDownMask &= defaultMask;
167 newUpMask &= defaultMask; 157 newUpMask &= defaultMask;
168 158
169 long lowerBound; 159 long lowerBound;
170 long upperBound; 160 long upperBound;
171 boolean lowerOverflowsPositively = addOverflowsPositively(stamp1.lowerBound(), stamp2.lowerBound(), bits, unsigned); 161 boolean lowerOverflowsPositively = addOverflowsPositively(stamp1.lowerBound(), stamp2.lowerBound(), bits);
172 boolean upperOverflowsPositively = addOverflowsPositively(stamp1.upperBound(), stamp2.upperBound(), bits, unsigned); 162 boolean upperOverflowsPositively = addOverflowsPositively(stamp1.upperBound(), stamp2.upperBound(), bits);
173 boolean lowerOverflowsNegatively = addOverflowsNegatively(stamp1.lowerBound(), stamp2.lowerBound(), bits, unsigned); 163 boolean lowerOverflowsNegatively = addOverflowsNegatively(stamp1.lowerBound(), stamp2.lowerBound(), bits);
174 boolean upperOverflowsNegatively = addOverflowsNegatively(stamp1.upperBound(), stamp2.upperBound(), bits, unsigned); 164 boolean upperOverflowsNegatively = addOverflowsNegatively(stamp1.upperBound(), stamp2.upperBound(), bits);
175 if ((lowerOverflowsNegatively && !upperOverflowsNegatively) || (!lowerOverflowsPositively && upperOverflowsPositively)) { 165 if ((lowerOverflowsNegatively && !upperOverflowsNegatively) || (!lowerOverflowsPositively && upperOverflowsPositively)) {
176 lowerBound = IntegerStamp.defaultMinValue(bits, unsigned); 166 lowerBound = IntegerStamp.defaultMinValue(bits);
177 upperBound = IntegerStamp.defaultMaxValue(bits, unsigned); 167 upperBound = IntegerStamp.defaultMaxValue(bits);
178 } else { 168 } else {
179 lowerBound = (stamp1.lowerBound() + stamp2.lowerBound()) & defaultMask; 169 lowerBound = SignExtendNode.signExtend((stamp1.lowerBound() + stamp2.lowerBound()) & defaultMask, bits);
180 upperBound = (stamp1.upperBound() + stamp2.upperBound()) & defaultMask; 170 upperBound = SignExtendNode.signExtend((stamp1.upperBound() + stamp2.upperBound()) & defaultMask, bits);
181 if (!unsigned) { 171 }
182 lowerBound = SignExtendNode.signExtend(lowerBound, bits); 172 IntegerStamp limit = StampFactory.forInteger(bits, lowerBound, upperBound);
183 upperBound = SignExtendNode.signExtend(upperBound, bits);
184 }
185 }
186 IntegerStamp limit = StampFactory.forInteger(bits, unsigned, lowerBound, upperBound);
187 newUpMask &= limit.upMask(); 173 newUpMask &= limit.upMask();
188 upperBound &= newUpMask; 174 upperBound = SignExtendNode.signExtend(upperBound & newUpMask, bits);
189 if (!unsigned) {
190 upperBound = SignExtendNode.signExtend(upperBound, bits);
191 }
192 newDownMask |= limit.downMask(); 175 newDownMask |= limit.downMask();
193 lowerBound |= newDownMask; 176 lowerBound |= newDownMask;
194 return new IntegerStamp(bits, unsigned, lowerBound, upperBound, newDownMask, newUpMask); 177 return new IntegerStamp(bits, lowerBound, upperBound, newDownMask, newUpMask);
195 } 178 }
196 179
197 public static Stamp sub(IntegerStamp stamp1, IntegerStamp stamp2) { 180 public static Stamp sub(IntegerStamp stamp1, IntegerStamp stamp2) {
198 if (stamp1.isUnrestricted() || stamp2.isUnrestricted()) { 181 if (stamp1.isUnrestricted() || stamp2.isUnrestricted()) {
199 return stamp1.unrestricted(); 182 return stamp1.unrestricted();
210 } else if (((downMask >>> (bits - 1)) & 1) == 1) { 193 } else if (((downMask >>> (bits - 1)) & 1) == 1) {
211 lowerBound = downMask; 194 lowerBound = downMask;
212 upperBound = upMask; 195 upperBound = upMask;
213 } else { 196 } else {
214 lowerBound = downMask | (-1L << (bits - 1)); 197 lowerBound = downMask | (-1L << (bits - 1));
215 upperBound = IntegerStamp.defaultMaxValue(bits, false) & upMask; 198 upperBound = IntegerStamp.defaultMaxValue(bits) & upMask;
216 } 199 }
217 lowerBound = IntegerConvertNode.convert(lowerBound, bits, false); 200 lowerBound = IntegerConvertNode.convert(lowerBound, bits, false);
218 upperBound = IntegerConvertNode.convert(upperBound, bits, false); 201 upperBound = IntegerConvertNode.convert(upperBound, bits, false);
219 return new IntegerStamp(bits, false, lowerBound, upperBound, downMask, upMask); 202 return new IntegerStamp(bits, lowerBound, upperBound, downMask, upMask);
220 } 203 }
221 204
222 public static Stamp and(Stamp stamp1, Stamp stamp2) { 205 public static Stamp and(Stamp stamp1, Stamp stamp2) {
223 if (stamp1 instanceof IntegerStamp && stamp2 instanceof IntegerStamp) { 206 if (stamp1 instanceof IntegerStamp && stamp2 instanceof IntegerStamp) {
224 return and((IntegerStamp) stamp1, (IntegerStamp) stamp2); 207 return and((IntegerStamp) stamp1, (IntegerStamp) stamp2);
280 upperBound = upMask; 263 upperBound = upMask;
281 } else { 264 } else {
282 lowerBound = value.lowerBound() >>> shiftCount; 265 lowerBound = value.lowerBound() >>> shiftCount;
283 upperBound = value.upperBound() >>> shiftCount; 266 upperBound = value.upperBound() >>> shiftCount;
284 } 267 }
285 return new IntegerStamp(bits, value.isUnsigned(), lowerBound, upperBound, downMask, upMask); 268 return new IntegerStamp(bits, lowerBound, upperBound, downMask, upMask);
286 } 269 }
287 } 270 }
288 long mask = IntegerStamp.upMaskFor(bits, value.lowerBound(), value.upperBound()); 271 long mask = IntegerStamp.upMaskFor(bits, value.lowerBound(), value.upperBound());
289 return stampForMask(bits, 0, mask); 272 return stampForMask(bits, 0, mask);
290 } 273 }
327 310
328 long defaultMask = IntegerStamp.defaultMask(resultBits); 311 long defaultMask = IntegerStamp.defaultMask(resultBits);
329 long downMask = SignExtendNode.signExtend(inputStamp.downMask(), inputBits) & defaultMask; 312 long downMask = SignExtendNode.signExtend(inputStamp.downMask(), inputBits) & defaultMask;
330 long upMask = SignExtendNode.signExtend(inputStamp.upMask(), inputBits) & defaultMask; 313 long upMask = SignExtendNode.signExtend(inputStamp.upMask(), inputBits) & defaultMask;
331 314
332 long lowerBound; 315 return new IntegerStamp(resultBits, inputStamp.lowerBound(), inputStamp.upperBound(), downMask, upMask);
333 long upperBound;
334 if (inputStamp.isUnsigned()) {
335 lowerBound = SignExtendNode.signExtend(inputStamp.lowerBound(), inputBits) & defaultMask;
336 upperBound = SignExtendNode.signExtend(inputStamp.upperBound(), inputBits) & defaultMask;
337 } else {
338 lowerBound = inputStamp.lowerBound();
339 upperBound = inputStamp.upperBound();
340 }
341
342 return new IntegerStamp(resultBits, inputStamp.isUnsigned(), lowerBound, upperBound, downMask, upMask);
343 } else { 316 } else {
344 return input.illegal(); 317 return input.illegal();
345 } 318 }
346 } 319 }
347 320
361 } 334 }
362 335
363 long lowerBound = ZeroExtendNode.zeroExtend(inputStamp.lowerBound(), inputBits); 336 long lowerBound = ZeroExtendNode.zeroExtend(inputStamp.lowerBound(), inputBits);
364 long upperBound = ZeroExtendNode.zeroExtend(inputStamp.upperBound(), inputBits); 337 long upperBound = ZeroExtendNode.zeroExtend(inputStamp.upperBound(), inputBits);
365 338
366 return new IntegerStamp(resultBits, inputStamp.isUnsigned(), lowerBound, upperBound, downMask, upMask); 339 return new IntegerStamp(resultBits, lowerBound, upperBound, downMask, upMask);
367 } else { 340 } else {
368 return input.illegal(); 341 return input.illegal();
369 } 342 }
370 } 343 }
371 344
372 public static Stamp narrowingConversion(Stamp input, int resultBits) { 345 public static Stamp narrowingConversion(Stamp input, int resultBits) {
373 if (input instanceof IntegerStamp) { 346 if (input instanceof IntegerStamp) {
374 IntegerStamp inputStamp = (IntegerStamp) input; 347 IntegerStamp inputStamp = (IntegerStamp) input;
375 boolean unsigned = inputStamp.isUnsigned();
376 int inputBits = inputStamp.getBits(); 348 int inputBits = inputStamp.getBits();
377 assert resultBits <= inputBits; 349 assert resultBits <= inputBits;
378 if (resultBits == inputBits) { 350 if (resultBits == inputBits) {
379 return inputStamp; 351 return inputStamp;
380 } 352 }
381 353
382 final long upperBound; 354 final long upperBound;
383 if (inputStamp.lowerBound() < IntegerStamp.defaultMinValue(resultBits, unsigned)) { 355 if (inputStamp.lowerBound() < IntegerStamp.defaultMinValue(resultBits)) {
384 upperBound = IntegerStamp.defaultMaxValue(resultBits, unsigned); 356 upperBound = IntegerStamp.defaultMaxValue(resultBits);
385 } else { 357 } else {
386 upperBound = saturate(inputStamp.upperBound(), resultBits, unsigned); 358 upperBound = saturate(inputStamp.upperBound(), resultBits);
387 } 359 }
388 final long lowerBound; 360 final long lowerBound;
389 if (inputStamp.upperBound() > IntegerStamp.defaultMaxValue(resultBits, unsigned)) { 361 if (inputStamp.upperBound() > IntegerStamp.defaultMaxValue(resultBits)) {
390 lowerBound = IntegerStamp.defaultMinValue(resultBits, unsigned); 362 lowerBound = IntegerStamp.defaultMinValue(resultBits);
391 } else { 363 } else {
392 lowerBound = saturate(inputStamp.lowerBound(), resultBits, unsigned); 364 lowerBound = saturate(inputStamp.lowerBound(), resultBits);
393 } 365 }
394 366
395 long defaultMask = IntegerStamp.defaultMask(resultBits); 367 long defaultMask = IntegerStamp.defaultMask(resultBits);
396 long newDownMask = inputStamp.downMask() & defaultMask; 368 long newDownMask = inputStamp.downMask() & defaultMask;
397 long newUpMask = inputStamp.upMask() & defaultMask; 369 long newUpMask = inputStamp.upMask() & defaultMask;
398 long newLowerBound = (lowerBound | newDownMask) & newUpMask; 370 long newLowerBound = SignExtendNode.signExtend((lowerBound | newDownMask) & newUpMask, resultBits);
399 long newUpperBound = (upperBound | newDownMask) & newUpMask; 371 long newUpperBound = SignExtendNode.signExtend((upperBound | newDownMask) & newUpMask, resultBits);
400 if (!unsigned) { 372 return new IntegerStamp(resultBits, newLowerBound, newUpperBound, newDownMask, newUpMask);
401 newLowerBound = SignExtendNode.signExtend(newLowerBound, resultBits);
402 newUpperBound = SignExtendNode.signExtend(newUpperBound, resultBits);
403 }
404 return new IntegerStamp(resultBits, unsigned, newLowerBound, newUpperBound, newDownMask, newUpMask);
405 } else { 373 } else {
406 return input.illegal(); 374 return input.illegal();
407 } 375 }
408 } 376 }
409 377
424 392
425 long defaultMask = IntegerStamp.defaultMask(toKind.getBitCount()); 393 long defaultMask = IntegerStamp.defaultMask(toKind.getBitCount());
426 long intMask = IntegerStamp.defaultMask(32); 394 long intMask = IntegerStamp.defaultMask(32);
427 long newUpMask = signExtend(fromStamp.upMask() & defaultMask, toKind) & intMask; 395 long newUpMask = signExtend(fromStamp.upMask() & defaultMask, toKind) & intMask;
428 long newDownMask = signExtend(fromStamp.downMask() & defaultMask, toKind) & intMask; 396 long newDownMask = signExtend(fromStamp.downMask() & defaultMask, toKind) & intMask;
429 return new IntegerStamp(toKind.getStackKind().getBitCount(), false, (int) ((lowerBound | newDownMask) & newUpMask), (int) ((upperBound | newDownMask) & newUpMask), newDownMask, newUpMask); 397 return new IntegerStamp(toKind.getStackKind().getBitCount(), (int) ((lowerBound | newDownMask) & newUpMask), (int) ((upperBound | newDownMask) & newUpMask), newDownMask, newUpMask);
430 } 398 }
431 399
432 private static long signExtend(long value, Kind valueKind) { 400 private static long signExtend(long value, Kind valueKind) {
433 if (valueKind != Kind.Char && valueKind != Kind.Long && (value >>> (valueKind.getBitCount() - 1) & 1) == 1) { 401 if (valueKind != Kind.Char && valueKind != Kind.Long && (value >>> (valueKind.getBitCount() - 1) & 1) == 1) {
434 return value | (-1L << valueKind.getBitCount()); 402 return value | (-1L << valueKind.getBitCount());
435 } else { 403 } else {
436 return value; 404 return value;
437 } 405 }
438 } 406 }
439 407
440 private static long saturate(long v, int bits, boolean unsigned) { 408 private static long saturate(long v, int bits) {
441 if (bits < 64) { 409 if (bits < 64) {
442 long max = IntegerStamp.defaultMaxValue(bits, unsigned); 410 long max = IntegerStamp.defaultMaxValue(bits);
443 if (v > max) { 411 if (v > max) {
444 return max; 412 return max;
445 } 413 }
446 long min = IntegerStamp.defaultMinValue(bits, unsigned); 414 long min = IntegerStamp.defaultMinValue(bits);
447 if (v < min) { 415 if (v < min) {
448 return min; 416 return min;
449 } 417 }
450 } 418 }
451 return v; 419 return v;
463 return v; 431 return v;
464 } 432 }
465 433
466 /** 434 /**
467 * Compute the stamp resulting from the unsigned comparison being true. 435 * Compute the stamp resulting from the unsigned comparison being true.
468 * 436 *
469 * @return null if it's can't be true or it nothing useful can be encoded. 437 * @return null if it's can't be true or it nothing useful can be encoded.
470 */ 438 */
471 public static Stamp unsignedCompare(Stamp stamp, Stamp stamp2) { 439 public static Stamp unsignedCompare(Stamp stamp, Stamp stamp2) {
472 IntegerStamp x = (IntegerStamp) stamp; 440 IntegerStamp x = (IntegerStamp) stamp;
473 IntegerStamp y = (IntegerStamp) stamp2; 441 IntegerStamp y = (IntegerStamp) stamp2;
486 // Test will fail. Return illegalStamp instead? 454 // Test will fail. Return illegalStamp instead?
487 return null; 455 return null;
488 } 456 }
489 // If the test succeeds then this proves that n is at greater than c so the bounds 457 // If the test succeeds then this proves that n is at greater than c so the bounds
490 // are [c+1..-n.upperBound)]. 458 // are [c+1..-n.upperBound)].
491 return StampFactory.forInteger(x.getBits(), false, x.lowerBound() + 1, y.upperBound()); 459 return StampFactory.forInteger(x.getBits(), x.lowerBound() + 1, y.upperBound());
492 } 460 }
493 return null; 461 return null;
494 } 462 }
495 // n <| c, where c is a strictly positive constant 463 // n <| c, where c is a strictly positive constant
496 if (y.lowerBound() == y.upperBound() && y.isStrictlyPositive()) { 464 if (y.lowerBound() == y.upperBound() && y.isStrictlyPositive()) {
497 // The test proves that n is positive and less than c, [0..c-1] 465 // The test proves that n is positive and less than c, [0..c-1]
498 return StampFactory.forInteger(y.getBits(), false, 0, y.lowerBound() - 1); 466 return StampFactory.forInteger(y.getBits(), 0, y.lowerBound() - 1);
499 } 467 }
500 return null; 468 return null;
501 } 469 }
502 } 470 }