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