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