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