Mercurial > hg > truffle

comparison graal/com.oracle.graal.nodes/src/com/oracle/graal/nodes/type/StampTool.java @ 11352:8185c119d731

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
"always set" bit mask on IntegerStamps
author Lukas Stadler <lukas.stadler@jku.at>
date Fri, 16 Aug 2013 13:15:42 +0200
parents ef6915cf1e59
children 90201030d3cf
comparison
equal deleted inserted replaced
11314:dc14bcf752ea 11352:8185c119d731
27 import com.oracle.graal.api.meta.*; 27 import com.oracle.graal.api.meta.*;
28 28
29 /** 29 /**
30 * Helper class that is used to keep all stamp-related operations in one place. 30 * Helper class that is used to keep all stamp-related operations in one place.
31 */ 31 */
32 // TODO(ls) maybe move the contents into IntegerStamp
33 public class StampTool { 32 public class StampTool {
34 33
35 public static Stamp negate(Stamp stamp) { 34 public static Stamp negate(Stamp stamp) {
35 if (true) {
36 return StampFactory.forKind(stamp.kind());
37 }
36 Kind kind = stamp.kind(); 38 Kind kind = stamp.kind();
37 if (stamp instanceof IntegerStamp) { 39 if (stamp instanceof IntegerStamp) {
38 IntegerStamp integerStamp = (IntegerStamp) stamp; 40 IntegerStamp integerStamp = (IntegerStamp) stamp;
39 if (integerStamp.lowerBound() != kind.getMinValue()) { 41 if (integerStamp.lowerBound() != kind.getMinValue()) {
40 // TODO(ls) check if the mask calculation is correct... 42 // TODO(ls) check if the mask calculation is correct...
41 return new IntegerStamp(kind, -integerStamp.upperBound(), -integerStamp.lowerBound(), IntegerStamp.defaultMask(kind) & (integerStamp.mask() | -integerStamp.mask())); 43 return StampFactory.forInteger(kind, -integerStamp.upperBound(), -integerStamp.lowerBound());
42 } 44 }
43 } 45 } else if (stamp instanceof FloatStamp) {
46 FloatStamp floatStamp = (FloatStamp) stamp;
47 return new FloatStamp(kind, -floatStamp.upperBound(), -floatStamp.lowerBound(), floatStamp.isNonNaN());
48 }
49
44 return StampFactory.forKind(kind); 50 return StampFactory.forKind(kind);
51 }
52
53 public static Stamp not(Stamp stamp) {
54 if (stamp instanceof IntegerStamp) {
55 IntegerStamp integerStamp = (IntegerStamp) stamp;
56 assert stamp.kind() == Kind.Int || stamp.kind() == Kind.Long;
57 long defaultMask = IntegerStamp.defaultMask(stamp.kind());
58 return new IntegerStamp(stamp.kind(), ~integerStamp.upperBound(), ~integerStamp.lowerBound(), (~integerStamp.upMask()) & defaultMask, (~integerStamp.downMask()) & defaultMask);
59 }
60 return StampFactory.forKind(stamp.kind());
45 } 61 }
46 62
47 public static Stamp meet(Collection<? extends StampProvider> values) { 63 public static Stamp meet(Collection<? extends StampProvider> values) {
48 Iterator<? extends StampProvider> iterator = values.iterator(); 64 Iterator<? extends StampProvider> iterator = values.iterator();
49 if (iterator.hasNext()) { 65 if (iterator.hasNext()) {
62 return add((IntegerStamp) stamp1, (IntegerStamp) stamp2); 78 return add((IntegerStamp) stamp1, (IntegerStamp) stamp2);
63 } 79 }
64 return StampFactory.illegal(); 80 return StampFactory.illegal();
65 } 81 }
66 82
67 public static Stamp add(IntegerStamp stamp1, IntegerStamp stamp2) { 83 private static long carryBits(long x, long y) {
68 Kind kind = stamp1.kind(); 84 return (x + y) ^ x ^ y;
69 assert kind == stamp2.kind();
70 if (addOverflow(stamp1.lowerBound(), stamp2.lowerBound(), kind)) {
71 return StampFactory.forKind(kind);
72 }
73 if (addOverflow(stamp1.upperBound(), stamp2.upperBound(), kind)) {
74 return StampFactory.forKind(kind);
75 }
76 long lowerBound = stamp1.lowerBound() + stamp2.lowerBound();
77 long upperBound = stamp1.upperBound() + stamp2.upperBound();
78 long mask = IntegerStamp.maskFor(kind, lowerBound, upperBound);
79
80 return StampFactory.forInteger(kind, lowerBound, upperBound, mask);
81 } 85 }
82 86
83 public static Stamp sub(Stamp stamp1, Stamp stamp2) { 87 public static Stamp sub(Stamp stamp1, Stamp stamp2) {
84 return add(stamp1, StampTool.negate(stamp2)); 88 return add(stamp1, StampTool.negate(stamp2));
85 } 89 }
90 } 94 }
91 return StampFactory.illegal(); 95 return StampFactory.illegal();
92 } 96 }
93 97
94 public static Stamp div(IntegerStamp stamp1, IntegerStamp stamp2) { 98 public static Stamp div(IntegerStamp stamp1, IntegerStamp stamp2) {
99 assert stamp1.kind() == stamp2.kind();
95 Kind kind = stamp1.kind(); 100 Kind kind = stamp1.kind();
96 if (stamp2.isStrictlyPositive()) { 101 if (stamp2.isStrictlyPositive()) {
97 long lowerBound = stamp1.lowerBound() / stamp2.lowerBound(); 102 long lowerBound = stamp1.lowerBound() / stamp2.lowerBound();
98 long upperBound = stamp1.upperBound() / stamp2.lowerBound(); 103 long upperBound = stamp1.upperBound() / stamp2.lowerBound();
99 return StampFactory.forInteger(kind, lowerBound, upperBound, IntegerStamp.maskFor(kind, lowerBound, upperBound)); 104 return StampFactory.forInteger(kind, lowerBound, upperBound);
100 } 105 }
101 return StampFactory.forKind(kind); 106 return StampFactory.forKind(kind);
102 } 107 }
103 108
104 private static boolean addOverflow(long x, long y, Kind kind) { 109 private static boolean addOverflows(long x, long y, Kind kind) {
105 long result = x + y; 110 long result = x + y;
106 if (kind == Kind.Long) { 111 if (kind == Kind.Long) {
107 return ((x ^ result) & (y ^ result)) < 0; 112 return ((x ^ result) & (y ^ result)) < 0;
108 } else { 113 } else {
109 assert kind == Kind.Int; 114 assert kind == Kind.Int;
110 return result > Integer.MAX_VALUE || result < Integer.MIN_VALUE; 115 return result > Integer.MAX_VALUE || result < Integer.MIN_VALUE;
111 } 116 }
112 } 117 }
113 118
114 private static final long INTEGER_SIGN_BIT = 0x80000000L; 119 public static IntegerStamp add(IntegerStamp stamp1, IntegerStamp stamp2) {
115 private static final long LONG_SIGN_BIT = 0x8000000000000000L; 120 try {
116 121 if (stamp1.isUnrestricted() || stamp2.isUnrestricted()) {
117 private static Stamp stampForMask(Kind kind, long mask) { 122 return (IntegerStamp) StampFactory.forKind(stamp1.kind());
118 return stampForMask(kind, mask, 0); 123 }
119 } 124 Kind kind = stamp1.kind();
120 125 assert stamp1.kind() == stamp2.kind();
121 private static Stamp stampForMask(Kind kind, long mask, long alwaysSetBits) { 126 long defaultMask = IntegerStamp.defaultMask(kind);
127 long variableBits = (stamp1.downMask() ^ stamp1.upMask()) | (stamp2.downMask() ^ stamp2.upMask());
128 long variableBitsWithCarry = variableBits | (carryBits(stamp1.downMask(), stamp2.downMask()) ^ carryBits(stamp1.upMask(), stamp2.upMask()));
129 long newDownMask = (stamp1.downMask() + stamp2.downMask()) & ~variableBitsWithCarry;
130 long newUpMask = (stamp1.downMask() + stamp2.downMask()) | variableBitsWithCarry;
131
132 newDownMask &= defaultMask;
133 newUpMask &= defaultMask;
134
135 long lowerBound;
136 long upperBound;
137 if (addOverflows(stamp1.lowerBound(), stamp2.lowerBound(), kind) || addOverflows(stamp1.upperBound(), stamp2.upperBound(), kind)) {
138 lowerBound = kind.getMinValue();
139 upperBound = kind.getMaxValue();
140 } else {
141 lowerBound = stamp1.lowerBound() + stamp2.lowerBound();
142 upperBound = stamp1.upperBound() + stamp2.upperBound();
143 }
144 IntegerStamp limit = StampFactory.forInteger(kind, lowerBound, upperBound);
145 newUpMask &= limit.upMask();
146 return new IntegerStamp(kind, lowerBound | newDownMask, signExtend(upperBound & newUpMask, kind), newDownMask, newUpMask);
147 } catch (Throwable e) {
148 throw new RuntimeException(stamp1 + " + " + stamp2, e);
149 }
150 }
151
152 public static Stamp sub(IntegerStamp stamp1, IntegerStamp stamp2) {
153 if (stamp1.isUnrestricted() || stamp2.isUnrestricted()) {
154 return StampFactory.forKind(stamp1.kind());
155 }
156 return add(stamp1, (IntegerStamp) StampTool.negate(stamp2));
157 }
158
159 private static Stamp stampForMask(Kind kind, long downMask, long upMask) {
122 long lowerBound; 160 long lowerBound;
123 long upperBound; 161 long upperBound;
124 if (kind == Kind.Int && (mask & INTEGER_SIGN_BIT) != 0) { 162 if (((upMask >>> (kind.getBitCount() - 1)) & 1) == 0) {
125 // the mask is negative 163 lowerBound = downMask;
126 lowerBound = Integer.MIN_VALUE; 164 upperBound = upMask;
127 upperBound = mask ^ INTEGER_SIGN_BIT; 165 } else if (((downMask >>> (kind.getBitCount() - 1)) & 1) == 1) {
128 } else if (kind == Kind.Long && (mask & LONG_SIGN_BIT) != 0) { 166 lowerBound = downMask;
129 // the mask is negative 167 upperBound = upMask;
130 lowerBound = Long.MIN_VALUE; 168 } else {
131 upperBound = mask ^ LONG_SIGN_BIT; 169 lowerBound = upMask;
132 } else { 170 upperBound = kind.getMaxValue() & upMask;
133 lowerBound = alwaysSetBits; 171 }
134 upperBound = mask; 172 if (kind == Kind.Int) {
135 } 173 return StampFactory.forInteger(kind, (int) lowerBound, (int) upperBound, downMask, upMask);
136 return StampFactory.forInteger(kind, lowerBound, upperBound, mask); 174 } else {
175 return StampFactory.forInteger(kind, lowerBound, upperBound, downMask, upMask);
176 }
137 } 177 }
138 178
139 public static Stamp and(Stamp stamp1, Stamp stamp2) { 179 public static Stamp and(Stamp stamp1, Stamp stamp2) {
140 if (stamp1 instanceof IntegerStamp && stamp2 instanceof IntegerStamp) { 180 if (stamp1 instanceof IntegerStamp && stamp2 instanceof IntegerStamp) {
141 return and((IntegerStamp) stamp1, (IntegerStamp) stamp2); 181 return and((IntegerStamp) stamp1, (IntegerStamp) stamp2);
142 } 182 }
143 return StampFactory.illegal(); 183 return StampFactory.illegal();
144 } 184 }
145 185
146 public static Stamp and(IntegerStamp stamp1, IntegerStamp stamp2) { 186 public static Stamp and(IntegerStamp stamp1, IntegerStamp stamp2) {
147 Kind kind = stamp1.kind(); 187 assert stamp1.kind() == stamp2.kind();
148 long mask = stamp1.mask() & stamp2.mask(); 188 return stampForMask(stamp1.kind(), stamp1.downMask() & stamp2.downMask(), stamp1.upMask() & stamp2.upMask());
149 return stampForMask(kind, mask);
150 } 189 }
151 190
152 public static Stamp or(Stamp stamp1, Stamp stamp2) { 191 public static Stamp or(Stamp stamp1, Stamp stamp2) {
153 if (stamp1 instanceof IntegerStamp && stamp2 instanceof IntegerStamp) { 192 if (stamp1 instanceof IntegerStamp && stamp2 instanceof IntegerStamp) {
154 return or((IntegerStamp) stamp1, (IntegerStamp) stamp2); 193 return or((IntegerStamp) stamp1, (IntegerStamp) stamp2);
155 } 194 }
156 return StampFactory.illegal(); 195 return StampFactory.illegal();
157 } 196 }
158 197
159 public static Stamp or(IntegerStamp stamp1, IntegerStamp stamp2) { 198 public static Stamp or(IntegerStamp stamp1, IntegerStamp stamp2) {
160 Kind kind = stamp1.kind(); 199 assert stamp1.kind() == stamp2.kind();
161 long mask = stamp1.mask() | stamp2.mask(); 200 return stampForMask(stamp1.kind(), stamp1.downMask() | stamp2.downMask(), stamp1.upMask() | stamp2.upMask());
162 if (stamp1.lowerBound() >= 0 && stamp2.lowerBound() >= 0) {
163 return stampForMask(kind, mask, stamp1.lowerBound() | stamp2.lowerBound());
164 } else {
165 return stampForMask(kind, mask);
166 }
167 } 201 }
168 202
169 public static Stamp xor(Stamp stamp1, Stamp stamp2) { 203 public static Stamp xor(Stamp stamp1, Stamp stamp2) {
170 if (stamp1 instanceof IntegerStamp && stamp2 instanceof IntegerStamp) { 204 if (stamp1 instanceof IntegerStamp && stamp2 instanceof IntegerStamp) {
171 return xor((IntegerStamp) stamp1, (IntegerStamp) stamp2); 205 return xor((IntegerStamp) stamp1, (IntegerStamp) stamp2);
172 } 206 }
173 return StampFactory.illegal(); 207 return StampFactory.illegal();
174 } 208 }
175 209
176 public static Stamp xor(IntegerStamp stamp1, IntegerStamp stamp2) { 210 public static Stamp xor(IntegerStamp stamp1, IntegerStamp stamp2) {
177 Kind kind = stamp1.kind(); 211 assert stamp1.kind() == stamp2.kind();
178 long mask = stamp1.mask() | stamp2.mask(); 212 long variableBits = (stamp1.downMask() ^ stamp1.upMask()) | (stamp2.downMask() ^ stamp2.upMask());
179 return stampForMask(kind, mask); 213 long newDownMask = (stamp1.downMask() ^ stamp2.downMask()) & ~variableBits;
214 long newUpMask = (stamp1.downMask() ^ stamp2.downMask()) | variableBits;
215 return stampForMask(stamp1.kind(), newDownMask, newUpMask);
180 } 216 }
181 217
182 public static Stamp unsignedRightShift(Stamp value, Stamp shift) { 218 public static Stamp unsignedRightShift(Stamp value, Stamp shift) {
183 if (value instanceof IntegerStamp && shift instanceof IntegerStamp) { 219 if (value instanceof IntegerStamp && shift instanceof IntegerStamp) {
184 return unsignedRightShift((IntegerStamp) value, (IntegerStamp) shift); 220 return unsignedRightShift((IntegerStamp) value, (IntegerStamp) shift);
199 upperBound = IntegerStamp.defaultMask(kind) >>> shiftCount; 235 upperBound = IntegerStamp.defaultMask(kind) >>> shiftCount;
200 } else { 236 } else {
201 lowerBound = value.lowerBound() >>> shiftCount; 237 lowerBound = value.lowerBound() >>> shiftCount;
202 upperBound = value.upperBound() >>> shiftCount; 238 upperBound = value.upperBound() >>> shiftCount;
203 } 239 }
204 long mask = value.mask() >>> shiftCount; 240 return new IntegerStamp(kind, lowerBound, upperBound, value.downMask() >>> shiftCount, value.upMask() >>> shiftCount);
205 return StampFactory.forInteger(kind, lowerBound, upperBound, mask); 241 }
206 } 242 }
207 } 243 long mask = IntegerStamp.upMaskFor(kind, value.lowerBound(), value.upperBound());
208 long mask = IntegerStamp.maskFor(kind, value.lowerBound(), value.upperBound()); 244 return stampForMask(kind, 0, mask);
209 return stampForMask(kind, mask);
210 } 245 }
211 246
212 public static Stamp leftShift(Stamp value, Stamp shift) { 247 public static Stamp leftShift(Stamp value, Stamp shift) {
213 if (value instanceof IntegerStamp && shift instanceof IntegerStamp) { 248 if (value instanceof IntegerStamp && shift instanceof IntegerStamp) {
214 return leftShift((IntegerStamp) value, (IntegerStamp) shift); 249 return leftShift((IntegerStamp) value, (IntegerStamp) shift);
216 return StampFactory.illegal(); 251 return StampFactory.illegal();
217 } 252 }
218 253
219 public static Stamp leftShift(IntegerStamp value, IntegerStamp shift) { 254 public static Stamp leftShift(IntegerStamp value, IntegerStamp shift) {
220 Kind kind = value.kind(); 255 Kind kind = value.kind();
256 long defaultMask = IntegerStamp.defaultMask(kind);
257 if (value.upMask() == 0) {
258 return value;
259 }
221 int shiftBits = kind == Kind.Int ? 5 : 6; 260 int shiftBits = kind == Kind.Int ? 5 : 6;
222 long shiftMask = kind == Kind.Int ? 0x1FL : 0x3FL; 261 long shiftMask = kind == Kind.Int ? 0x1FL : 0x3FL;
223 if ((shift.lowerBound() >>> shiftBits) == (shift.upperBound() >>> shiftBits)) { 262 if ((shift.lowerBound() >>> shiftBits) == (shift.upperBound() >>> shiftBits)) {
224 long mask = 0; 263 long downMask = defaultMask;
225 for (long i = shift.lowerBound() & shiftMask; i <= (shift.upperBound() & shiftMask); i++) { 264 long upMask = 0;
226 mask |= value.mask() << i; 265 for (long i = shift.lowerBound(); i <= shift.upperBound(); i++) {
227 } 266 if (shift.contains(i)) {
228 mask &= IntegerStamp.defaultMask(kind); 267 downMask &= value.downMask() << (i & shiftMask);
229 return stampForMask(kind, mask); 268 upMask |= value.upMask() << (i & shiftMask);
269 }
270 }
271 Stamp result = stampForMask(kind, downMask, upMask & IntegerStamp.defaultMask(kind));
272 return result;
230 } 273 }
231 return StampFactory.forKind(kind); 274 return StampFactory.forKind(kind);
232 } 275 }
233 276
234 public static Stamp intToLong(IntegerStamp intStamp) { 277 public static Stamp intToLong(IntegerStamp intStamp) {
235 long mask; 278 return StampFactory.forInteger(Kind.Long, intStamp.lowerBound(), intStamp.upperBound(), signExtend(intStamp.downMask(), Kind.Int), signExtend(intStamp.upMask(), Kind.Int));
236 if (intStamp.isPositive()) { 279 }
237 mask = intStamp.mask(); 280
238 } else { 281 private static IntegerStamp narrowingKindConvertion(IntegerStamp fromStamp, Kind toKind) {
239 mask = 0xffffffff00000000L | intStamp.mask(); 282 assert toKind == Kind.Byte || toKind == Kind.Char || toKind == Kind.Short || toKind == Kind.Int;
240 } 283 final long upperBound;
241 return StampFactory.forInteger(Kind.Long, intStamp.lowerBound(), intStamp.upperBound(), mask);
242 }
243
244 private static Stamp narrowingKindConvertion(IntegerStamp fromStamp, Kind toKind) {
245 long mask = fromStamp.mask() & IntegerStamp.defaultMask(toKind);
246 long lowerBound = saturate(fromStamp.lowerBound(), toKind);
247 long upperBound = saturate(fromStamp.upperBound(), toKind);
248 if (fromStamp.lowerBound() < toKind.getMinValue()) { 284 if (fromStamp.lowerBound() < toKind.getMinValue()) {
249 upperBound = toKind.getMaxValue(); 285 upperBound = toKind.getMaxValue();
250 } 286 } else {
287 upperBound = saturate(fromStamp.upperBound(), toKind);
288 }
289 final long lowerBound;
251 if (fromStamp.upperBound() > toKind.getMaxValue()) { 290 if (fromStamp.upperBound() > toKind.getMaxValue()) {
252 lowerBound = toKind.getMinValue(); 291 lowerBound = toKind.getMinValue();
253 } 292 } else {
254 return StampFactory.forInteger(toKind.getStackKind(), lowerBound, upperBound, mask); 293 lowerBound = saturate(fromStamp.lowerBound(), toKind);
255 } 294 }
256 295
257 public static Stamp intToByte(IntegerStamp intStamp) { 296 long defaultMask = IntegerStamp.defaultMask(toKind);
297 long intMask = IntegerStamp.defaultMask(Kind.Int);
298 long newUpMask = signExtend(fromStamp.upMask() & defaultMask, toKind) & intMask;
299 long newDownMask = signExtend(fromStamp.downMask() & defaultMask, toKind) & intMask;
300 return new IntegerStamp(toKind.getStackKind(), (int) ((lowerBound | newDownMask) & newUpMask), (int) ((upperBound | newDownMask) & newUpMask), newDownMask, newUpMask);
301 }
302
303 private static long signExtend(long value, Kind valueKind) {
304 if (valueKind != Kind.Char && (value >>> (valueKind.getBitCount() - 1) & 1) == 1) {
305 return value | (-1L << valueKind.getBitCount());
306 } else {
307 return value;
308 }
309 }
310
311 public static IntegerStamp intToByte(IntegerStamp intStamp) {
312 assert intStamp.kind() == Kind.Int;
258 return narrowingKindConvertion(intStamp, Kind.Byte); 313 return narrowingKindConvertion(intStamp, Kind.Byte);
259 } 314 }
260 315
261 public static Stamp intToShort(IntegerStamp intStamp) { 316 public static IntegerStamp intToShort(IntegerStamp intStamp) {
317 assert intStamp.kind() == Kind.Int;
262 return narrowingKindConvertion(intStamp, Kind.Short); 318 return narrowingKindConvertion(intStamp, Kind.Short);
263 } 319 }
264 320
265 public static Stamp intToChar(IntegerStamp intStamp) { 321 public static IntegerStamp intToChar(IntegerStamp intStamp) {
322 assert intStamp.kind() == Kind.Int;
266 return narrowingKindConvertion(intStamp, Kind.Char); 323 return narrowingKindConvertion(intStamp, Kind.Char);
267 } 324 }
268 325
269 public static Stamp longToInt(IntegerStamp longStamp) { 326 public static IntegerStamp longToInt(IntegerStamp longStamp) {
327 assert longStamp.kind() == Kind.Long;
270 return narrowingKindConvertion(longStamp, Kind.Int); 328 return narrowingKindConvertion(longStamp, Kind.Int);
271 } 329 }
272 330
273 public static long saturate(long v, Kind kind) { 331 public static long saturate(long v, Kind kind) {
274 long max = kind.getMaxValue(); 332 long max = kind.getMaxValue();