1 /*
2 * Copyright (c) 2014, 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 jdk.vm.ci.meta;
24
25 import java.util.ArrayList;
26
27 /**
28 * Represents the type of values in the LIR. It is composed of a {@link PlatformKind} that gives the
29 * low level representation of the value, and a {@link #referenceMask} that describes the location
30 * of object references in the value, and optionally a {@link #derivedReferenceBase}.
31 *
32 * <h2>Constructing {@link LIRKind} instances</h2>
33 *
34 * During LIR generation, every new {@link Value} should get a {@link LIRKind} of the correct
35 * {@link PlatformKind} that also contains the correct reference information. {@linkplain LIRKind
36 * LIRKinds} should be created as follows:
37 *
38 * <p>
39 * If the result value is created from one or more input values, the {@link LIRKind} should be
40 * created with {@link LIRKind#combine}(inputs). If the result has a different {@link PlatformKind}
41 * than the inputs, {@link LIRKind#combine}(inputs).{@link #changeType}(resultKind) should be used.
42 * <p>
43 * If the result is an exact copy of one of the inputs, {@link Value#getLIRKind()} can be used. Note
44 * that this is only correct for move-like operations, like conditional move or compare-and-swap.
45 * For convert operations, {@link LIRKind#combine} should be used.
46 * <p>
47 * If it is known that the result will be a reference (e.g. pointer arithmetic where the end result
48 * is a valid oop), {@link LIRKind#reference} should be used.
49 * <p>
50 * If it is known that the result will neither be a reference nor be derived from a reference,
51 * {@link LIRKind#value} can be used. If the operation producing this value has inputs, this is very
52 * likely wrong, and {@link LIRKind#combine} should be used instead.
53 * <p>
54 * If it is known that the result is derived from a reference in a way that the garbage collector
55 * can not track, {@link LIRKind#unknownReference} can be used. In most cases,
56 * {@link LIRKind#combine} should be used instead, since it is able to detect this automatically.
57 */
58 public final class LIRKind {
59
60 private static enum IllegalKind implements PlatformKind {
61 ILLEGAL;
62
63 private final EnumKey<IllegalKind> key = new EnumKey<>(this);
64
65 public Key getKey() {
66 return key;
67 }
68
69 public int getSizeInBytes() {
70 return 0;
71 }
72
73 public int getVectorLength() {
74 return 0;
75 }
76
77 public char getTypeChar() {
78 return '-';
79 }
80 }
81
82 /**
83 * The non-type. This uses {@link #unknownReference}, so it can never be part of an oop map.
84 */
85 public static final LIRKind Illegal = unknownReference(IllegalKind.ILLEGAL);
86
87 private final PlatformKind platformKind;
88 private final int referenceMask;
89
90 private AllocatableValue derivedReferenceBase;
91
92 private static final int UNKNOWN_REFERENCE = -1;
93
94 private LIRKind(PlatformKind platformKind, int referenceMask, AllocatableValue derivedReferenceBase) {
95 this.platformKind = platformKind;
96 this.referenceMask = referenceMask;
97 this.derivedReferenceBase = derivedReferenceBase;
98
99 assert derivedReferenceBase == null || !derivedReferenceBase.getLIRKind().isDerivedReference() : "derived reference can't have another derived reference as base";
100 }
101
102 /**
103 * Create a {@link LIRKind} of type {@code platformKind} that contains a primitive value. Should
104 * be only used when it's guaranteed that the value is not even indirectly derived from a
105 * reference. Otherwise, {@link #combine(Value...)} should be used instead.
106 */
107 public static LIRKind value(PlatformKind platformKind) {
108 return new LIRKind(platformKind, 0, null);
109 }
110
111 /**
112 * Create a {@link LIRKind} of type {@code platformKind} that contains a single tracked oop
113 * reference.
114 */
115 public static LIRKind reference(PlatformKind platformKind) {
116 return derivedReference(platformKind, null);
117 }
118
119 /**
120 * Create a {@link LIRKind} of type {@code platformKind} that contains a derived reference.
121 */
122 public static LIRKind derivedReference(PlatformKind platformKind, AllocatableValue base) {
123 int length = platformKind.getVectorLength();
124 assert 0 < length && length < 32 : "vector of " + length + " references not supported";
125 return new LIRKind(platformKind, (1 << length) - 1, base);
126 }
127
128 /**
129 * Create a {@link LIRKind} of type {@code platformKind} that contains a value that is derived
130 * from a reference in a non-linear way. Values of this {@link LIRKind} can not be live at
131 * safepoints. In most cases, this should not be called directly. {@link #combine} should be
132 * used instead to automatically propagate this information.
133 */
134 public static LIRKind unknownReference(PlatformKind platformKind) {
135 return new LIRKind(platformKind, UNKNOWN_REFERENCE, null);
136 }
137
138 /**
139 * Create a derived reference.
140 *
141 * @param base An {@link AllocatableValue} containing the base pointer of the derived reference.
142 */
143 public LIRKind makeDerivedReference(AllocatableValue base) {
144 assert !isUnknownReference() && derivedReferenceBase == null;
145 if (Value.ILLEGAL.equals(base)) {
146 return makeUnknownReference();
147 } else {
148 if (isValue()) {
149 return derivedReference(platformKind, base);
150 } else {
151 return new LIRKind(platformKind, referenceMask, base);
152 }
153 }
154 }
155
156 /**
157 * Derive a new type from inputs. The result will have the {@link PlatformKind} of one of the
158 * inputs. If all inputs are values, the result is a value. Otherwise, the result is an unknown
159 * reference.
160 *
161 * This method should be used to construct the result {@link LIRKind} of any operation that
162 * modifies values (e.g. arithmetics).
163 */
164 public static LIRKind combine(Value... inputs) {
165 assert inputs.length > 0;
166 for (Value input : inputs) {
167 LIRKind kind = input.getLIRKind();
168 if (kind.isUnknownReference()) {
169 return kind;
170 } else if (!kind.isValue()) {
171 return kind.makeUnknownReference();
172 }
173 }
174
175 // all inputs are values, just return one of them
176 return inputs[0].getLIRKind();
177 }
178
179 /**
180 * Merge the types of the inputs. The result will have the {@link PlatformKind} of one of the
181 * inputs. If all inputs are values (references), the result is a value (reference). Otherwise,
182 * the result is an unknown reference.
183 *
184 * This method should be used to construct the result {@link LIRKind} of merge operation that
185 * does not modify values (e.g. phis).
186 */
187 public static LIRKind merge(Value... inputs) {
188 assert inputs.length > 0;
189 ArrayList<LIRKind> kinds = new ArrayList<>(inputs.length);
190 for (int i = 0; i < inputs.length; i++) {
191 kinds.add(inputs[i].getLIRKind());
192 }
193 return merge(kinds);
194 }
195
196 /**
197 * Helper method to construct derived reference kinds. Returns the base value of a reference or
198 * derived reference. For values it returns {@code null}, and for unknown references it returns
199 * {@link Value#ILLEGAL}.
200 */
201 public static AllocatableValue derivedBaseFromValue(AllocatableValue value) {
202 LIRKind kind = value.getLIRKind();
203 if (kind.isValue()) {
204 return null;
205 } else if (kind.isDerivedReference()) {
206 return kind.getDerivedReferenceBase();
207 } else if (kind.isUnknownReference()) {
208 return Value.ILLEGAL;
209 } else {
210 // kind is a reference
211 return value;
212 }
213 }
214
215 /**
216 * Helper method to construct derived reference kinds. If one of {@code base1} or {@code base2}
217 * are set, it creates a derived reference using it as the base. If both are set, the result is
218 * an unknown reference.
219 */
220 public static LIRKind combineDerived(LIRKind kind, AllocatableValue base1, AllocatableValue base2) {
221 if (base1 == null && base2 == null) {
222 return kind;
223 } else if (base1 == null) {
224 return kind.makeDerivedReference(base2);
225 } else if (base2 == null) {
226 return kind.makeDerivedReference(base1);
227 } else {
228 return kind.makeUnknownReference();
229 }
230 }
231
232 /**
233 * @see #merge(Value...)
234 */
235 public static LIRKind merge(Iterable<LIRKind> kinds) {
236 LIRKind mergeKind = null;
237
238 for (LIRKind kind : kinds) {
239
240 if (kind.isUnknownReference()) {
241 /**
242 * Kind is an unknown reference, therefore the result can only be also an unknown
243 * reference.
244 */
245 mergeKind = kind;
246 break;
247 }
248 if (mergeKind == null) {
249 mergeKind = kind;
250 continue;
251 }
252
253 if (kind.isValue()) {
254 /* Kind is a value. */
255 if (mergeKind.referenceMask != 0) {
256 /*
257 * Inputs consists of values and references. Make the result an unknown
258 * reference.
259 */
260 mergeKind = mergeKind.makeUnknownReference();
261 break;
262 }
263 /* Check that other inputs are also values. */
264 } else {
265 /* Kind is a reference. */
266 if (mergeKind.referenceMask != kind.referenceMask) {
267 /*
268 * Reference maps do not match so the result can only be an unknown reference.
269 */
270 mergeKind = mergeKind.makeUnknownReference();
271 break;
272 }
273 }
274
275 }
276 assert mergeKind != null && verifyMerge(mergeKind, kinds);
277
278 // all inputs are values or references, just return one of them
279 return mergeKind;
280 }
281
282 private static boolean verifyMerge(LIRKind mergeKind, Iterable<LIRKind> kinds) {
283 for (LIRKind kind : kinds) {
284 assert mergeKind == null || verifyMoveKinds(mergeKind, kind) : String.format("Input kinds do not match %s vs. %s", mergeKind, kind);
285 }
286 return true;
287 }
288
289 /**
290 * Create a new {@link LIRKind} with the same reference information and a new
291 * {@linkplain #getPlatformKind platform kind}. If the new kind is a longer vector than this,
292 * the new elements are marked as untracked values.
293 */
294 public LIRKind changeType(PlatformKind newPlatformKind) {
295 if (newPlatformKind == platformKind) {
296 return this;
297 } else if (isUnknownReference()) {
298 return unknownReference(newPlatformKind);
299 } else if (referenceMask == 0) {
300 // value type
301 return LIRKind.value(newPlatformKind);
302 } else {
303 // reference type
304 int newLength = Math.min(32, newPlatformKind.getVectorLength());
305 int newReferenceMask = referenceMask & (0xFFFFFFFF >>> (32 - newLength));
306 assert newReferenceMask != UNKNOWN_REFERENCE;
307 return new LIRKind(newPlatformKind, newReferenceMask, derivedReferenceBase);
308 }
309 }
310
311 /**
312 * Create a new {@link LIRKind} with a new {@linkplain #getPlatformKind platform kind}. If the
313 * new kind is longer than this, the reference positions are repeated to fill the vector.
314 */
315 public LIRKind repeat(PlatformKind newPlatformKind) {
316 if (isUnknownReference()) {
317 return unknownReference(newPlatformKind);
318 } else if (referenceMask == 0) {
319 // value type
320 return LIRKind.value(newPlatformKind);
321 } else {
322 // reference type
323 int oldLength = platformKind.getVectorLength();
324 int newLength = newPlatformKind.getVectorLength();
325 assert oldLength <= newLength && newLength < 32 && (newLength % oldLength) == 0;
326
327 // repeat reference mask to fill new kind
328 int newReferenceMask = 0;
329 for (int i = 0; i < newLength; i += platformKind.getVectorLength()) {
330 newReferenceMask |= referenceMask << i;
331 }
332
333 assert newReferenceMask != UNKNOWN_REFERENCE;
334 return new LIRKind(newPlatformKind, newReferenceMask, derivedReferenceBase);
335 }
336 }
337
338 /**
339 * Create a new {@link LIRKind} with the same type, but marked as containing an
340 * {@link LIRKind#unknownReference}.
341 */
342 public LIRKind makeUnknownReference() {
343 return new LIRKind(platformKind, UNKNOWN_REFERENCE, null);
344 }
345
346 /**
347 * Get the low level type that is used in code generation.
348 */
349 public PlatformKind getPlatformKind() {
350 return platformKind;
351 }
352
353 /**
354 * Check whether this value is a derived reference.
355 */
356 public boolean isDerivedReference() {
357 return getDerivedReferenceBase() != null;
358 }
359
360 /**
361 * Get the base value of a derived reference.
362 */
363 public AllocatableValue getDerivedReferenceBase() {
364 return derivedReferenceBase;
365 }
366
367 /**
368 * Change the base value of a derived reference. This must be called on derived references only.
369 */
370 public void setDerivedReferenceBase(AllocatableValue derivedReferenceBase) {
371 assert isDerivedReference();
372 this.derivedReferenceBase = derivedReferenceBase;
373 }
374
375 /**
376 * Check whether this value is derived from a reference in a non-linear way. If this returns
377 * {@code true}, this value must not be live at safepoints.
378 */
379 public boolean isUnknownReference() {
380 return referenceMask == UNKNOWN_REFERENCE;
381 }
382
383 public int getReferenceCount() {
384 assert !isUnknownReference();
385 return Integer.bitCount(referenceMask);
386 }
387
388 /**
389 * Check whether the {@code idx}th part of this value is a reference that must be tracked at
390 * safepoints.
391 *
392 * @param idx The index into the vector if this is a vector kind. Must be 0 if this is a scalar
393 * kind.
394 */
395 public boolean isReference(int idx) {
396 assert 0 <= idx && idx < platformKind.getVectorLength() : "invalid index " + idx + " in " + this;
397 return !isUnknownReference() && (referenceMask & 1 << idx) != 0;
398 }
399
400 /**
401 * Check whether this kind is a value type that doesn't need to be tracked at safepoints.
402 */
403 public boolean isValue() {
404 return referenceMask == 0;
405 }
406
407 @Override
408 public String toString() {
409 if (isValue()) {
410 return platformKind.name();
411 } else if (isUnknownReference()) {
412 return platformKind.name() + "[*]";
413 } else {
414 StringBuilder ret = new StringBuilder();
415 ret.append(platformKind.name());
416 ret.append('[');
417 for (int i = 0; i < platformKind.getVectorLength(); i++) {
418 if (isReference(i)) {
419 ret.append('.');
420 } else {
421 ret.append(' ');
422 }
423 }
424 ret.append(']');
425 return ret.toString();
426 }
427 }
428
429 @Override
430 public int hashCode() {
431 final int prime = 31;
432 int result = 1;
433 result = prime * result + ((platformKind == null) ? 0 : platformKind.hashCode());
434 result = prime * result + referenceMask;
435 return result;
436 }
437
438 @Override
439 public boolean equals(Object obj) {
440 if (this == obj) {
441 return true;
442 }
443 if (!(obj instanceof LIRKind)) {
444 return false;
445 }
446
447 LIRKind other = (LIRKind) obj;
448 return platformKind == other.platformKind && referenceMask == other.referenceMask;
449 }
450
451 public static boolean verifyMoveKinds(LIRKind dst, LIRKind src) {
452 if (src.equals(dst)) {
453 return true;
454 }
455 if (src.getPlatformKind().equals(dst.getPlatformKind())) {
456 return !src.isUnknownReference() || dst.isUnknownReference();
457 }
458 return false;
459 }
460 }