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