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 java.util.ArrayList;
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 * Merge the types of the inputs. The result will have the {@link PlatformKind} of one of the
174 * inputs. If all inputs are values (references), the result is a value (reference). Otherwise,
175 * the result is an unknown reference.
176 *
177 * This method should be used to construct the result {@link LIRKind} of merge operation that
178 * does not modify values (e.g. phis).
179 */
180 public static LIRKind merge(Value... inputs) {
181 assert inputs.length > 0;
182 ArrayList<LIRKind> kinds = new ArrayList<>(inputs.length);
183 for (int i = 0; i < inputs.length; i++) {
184 kinds.add(inputs[i].getValueKind(LIRKind.class));
185 }
186 return merge(kinds);
187 }
188
189 /**
190 * Helper method to construct derived reference kinds. Returns the base value of a reference or
191 * derived reference. For values it returns {@code null}, and for unknown references it returns
192 * {@link Value#ILLEGAL}.
193 */
194 public static AllocatableValue derivedBaseFromValue(AllocatableValue value) {
195 ValueKind<?> valueKind = value.getValueKind();
196 if (valueKind instanceof LIRKind) {
197 LIRKind kind = value.getValueKind(LIRKind.class);
198 if (kind.isValue()) {
199 return null;
200 } else if (kind.isDerivedReference()) {
201 return kind.getDerivedReferenceBase();
202 } else if (kind.isUnknownReference()) {
203 return Value.ILLEGAL;
204 } else {
205 // kind is a reference
206 return value;
207 }
208 } else {
209 return Value.ILLEGAL;
210 }
211 }
212
213 /**
214 * Helper method to construct derived reference kinds. If one of {@code base1} or {@code base2}
215 * are set, it creates a derived reference using it as the base. If both are set, the result is
216 * an unknown reference.
217 */
218 public static LIRKind combineDerived(LIRKind kind, AllocatableValue base1, AllocatableValue base2) {
219 if (base1 == null && base2 == null) {
220 return kind;
221 } else if (base1 == null) {
222 return kind.makeDerivedReference(base2);
223 } else if (base2 == null) {
224 return kind.makeDerivedReference(base1);
225 } else {
226 return kind.makeUnknownReference();
227 }
228 }
229
230 /**
231 * @see #merge(Value...)
232 */
233 public static LIRKind merge(Iterable<LIRKind> kinds) {
234 LIRKind mergeKind = null;
235
236 for (LIRKind kind : kinds) {
237
238 if (kind.isUnknownReference()) {
239 /**
240 * Kind is an unknown reference, therefore the result can only be also an unknown
241 * reference.
242 */
243 mergeKind = kind;
244 break;
245 }
246 if (mergeKind == null) {
247 mergeKind = kind;
248 continue;
249 }
250
251 if (kind.isValue()) {
252 /* Kind is a value. */
253 if (mergeKind.referenceMask != 0) {
254 /*
255 * Inputs consists of values and references. Make the result an unknown
256 * reference.
257 */
258 mergeKind = mergeKind.makeUnknownReference();
259 break;
260 }
261 /* Check that other inputs are also values. */
262 } else {
263 /* Kind is a reference. */
264 if (mergeKind.referenceMask != kind.referenceMask) {
265 /*
266 * Reference maps do not match so the result can only be an unknown reference.
267 */
268 mergeKind = mergeKind.makeUnknownReference();
269 break;
270 }
271 }
272
273 }
274 assert mergeKind != null && verifyMerge(mergeKind, kinds);
275
276 // all inputs are values or references, just return one of them
277 return mergeKind;
278 }
279
280 private static boolean verifyMerge(LIRKind mergeKind, Iterable<LIRKind> kinds) {
281 for (LIRKind kind : kinds) {
282 assert mergeKind == null || verifyMoveKinds(mergeKind, kind) : String.format("Input kinds do not match %s vs. %s", mergeKind, kind);
283 }
284 return true;
285 }
286
287 /**
288 * Create a new {@link LIRKind} with the same reference information and a new
289 * {@linkplain #getPlatformKind platform kind}. If the new kind is a longer vector than this,
290 * the new elements are marked as untracked values.
291 */
292 @Override
293 public LIRKind changeType(PlatformKind newPlatformKind) {
294 if (newPlatformKind == getPlatformKind()) {
295 return this;
296 } else if (isUnknownReference()) {
297 return unknownReference(newPlatformKind);
298 } else if (referenceMask == 0) {
299 // value type
300 return LIRKind.value(newPlatformKind);
301 } else {
302 // reference type
303 int newLength = Math.min(32, newPlatformKind.getVectorLength());
304 int newReferenceMask = referenceMask & (0xFFFFFFFF >>> (32 - newLength));
305 assert newReferenceMask != UNKNOWN_REFERENCE;
306 return new LIRKind(newPlatformKind, newReferenceMask, derivedReferenceBase);
307 }
308 }
309
310 /**
311 * Create a new {@link LIRKind} with a new {@linkplain #getPlatformKind platform kind}. If the
312 * new kind is longer than this, the reference positions are repeated to fill the vector.
313 */
314 public LIRKind repeat(PlatformKind newPlatformKind) {
315 if (isUnknownReference()) {
316 return unknownReference(newPlatformKind);
317 } else if (referenceMask == 0) {
318 // value type
319 return LIRKind.value(newPlatformKind);
320 } else {
321 // reference type
322 int oldLength = getPlatformKind().getVectorLength();
323 int newLength = newPlatformKind.getVectorLength();
324 assert oldLength <= newLength && newLength < 32 && (newLength % oldLength) == 0;
325
326 // repeat reference mask to fill new kind
327 int newReferenceMask = 0;
328 for (int i = 0; i < newLength; i += getPlatformKind().getVectorLength()) {
329 newReferenceMask |= referenceMask << i;
330 }
331
332 assert newReferenceMask != UNKNOWN_REFERENCE;
333 return new LIRKind(newPlatformKind, newReferenceMask, derivedReferenceBase);
334 }
335 }
336
337 /**
338 * Create a new {@link LIRKind} with the same type, but marked as containing an
339 * {@link LIRKind#unknownReference}.
340 */
341 public LIRKind makeUnknownReference() {
342 return new LIRKind(getPlatformKind(), UNKNOWN_REFERENCE, null);
343 }
344
345 /**
346 * Check whether this value is a derived reference.
347 */
348 public boolean isDerivedReference() {
349 return getDerivedReferenceBase() != null;
350 }
351
352 /**
353 * Get the base value of a derived reference.
354 */
355 public AllocatableValue getDerivedReferenceBase() {
356 return derivedReferenceBase;
357 }
358
359 /**
360 * Change the base value of a derived reference. This must be called on derived references only.
361 */
362 public void setDerivedReferenceBase(AllocatableValue derivedReferenceBase) {
363 assert isDerivedReference();
364 this.derivedReferenceBase = derivedReferenceBase;
365 }
366
367 /**
368 * Check whether this value is derived from a reference in a non-linear way. If this returns
369 * {@code true}, this value must not be live at safepoints.
370 */
371 public boolean isUnknownReference() {
372 return referenceMask == UNKNOWN_REFERENCE;
373 }
374
375 public static boolean isUnknownReference(ValueKind<?> kind) {
376 if (kind instanceof LIRKind) {
377 return ((LIRKind) kind).isUnknownReference();
378 } else {
379 return true;
380 }
381 }
382
383 public static boolean isUnknownReference(Value value) {
384 return isUnknownReference(value.getValueKind());
385 }
386
387 public int getReferenceCount() {
388 assert !isUnknownReference();
389 return Integer.bitCount(referenceMask);
390 }
391
392 /**
393 * Check whether the {@code idx}th part of this value is a reference that must be tracked at
394 * safepoints.
395 *
396 * @param idx The index into the vector if this is a vector kind. Must be 0 if this is a scalar
397 * kind.
398 */
399 public boolean isReference(int idx) {
400 assert 0 <= idx && idx < getPlatformKind().getVectorLength() : "invalid index " + idx + " in " + this;
401 return !isUnknownReference() && (referenceMask & 1 << idx) != 0;
402 }
403
404 /**
405 * Check whether this kind is a value type that doesn't need to be tracked at safepoints.
406 */
407 public boolean isValue() {
408 return referenceMask == 0;
409 }
410
411 public static boolean isValue(ValueKind<?> kind) {
412 if (kind instanceof LIRKind) {
413 return ((LIRKind) kind).isValue();
414 } else {
415 return false;
416 }
417 }
418
419 public static boolean isValue(Value value) {
420 return isValue(value.getValueKind());
421 }
422
423 @Override
424 public String toString() {
425 if (isValue()) {
426 return getPlatformKind().name();
427 } else if (isUnknownReference()) {
428 return getPlatformKind().name() + "[*]";
429 } else {
430 StringBuilder ret = new StringBuilder();
431 ret.append(getPlatformKind().name());
432 ret.append('[');
433 for (int i = 0; i < getPlatformKind().getVectorLength(); i++) {
434 if (isReference(i)) {
435 ret.append('.');
436 } else {
437 ret.append(' ');
438 }
439 }
440 ret.append(']');
441 return ret.toString();
442 }
443 }
444
445 @Override
446 public int hashCode() {
447 final int prime = 31;
448 int result = 1;
449 result = prime * result + ((getPlatformKind() == null) ? 0 : getPlatformKind().hashCode());
450 result = prime * result + referenceMask;
451 return result;
452 }
453
454 @Override
455 public boolean equals(Object obj) {
456 if (this == obj) {
457 return true;
458 }
459 if (!(obj instanceof LIRKind)) {
460 return false;
461 }
462
463 LIRKind other = (LIRKind) obj;
464 return getPlatformKind() == other.getPlatformKind() && referenceMask == other.referenceMask;
465 }
466
467 public static boolean verifyMoveKinds(ValueKind<?> dst, ValueKind<?> src) {
468 if (src.equals(dst)) {
469 return true;
470 }
471 if (src.getPlatformKind().equals(dst.getPlatformKind())) {
472 return !isUnknownReference(src) || isUnknownReference(dst);
473 }
474 return false;
475 }
476 }