001/*
002 * Copyright (c) 2014, 2015, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.
008 *
009 * This code is distributed in the hope that it will be useful, but WITHOUT
010 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
011 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
012 * version 2 for more details (a copy is included in the LICENSE file that
013 * accompanied this code).
014 *
015 * You should have received a copy of the GNU General Public License version
016 * 2 along with this work; if not, write to the Free Software Foundation,
017 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
018 *
019 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
020 * or visit www.oracle.com if you need additional information or have any
021 * questions.
022 */
023package jdk.internal.jvmci.meta;
024
025import java.util.*;
026
027/**
028 * Represents the type of values in the LIR. It is composed of a {@link PlatformKind} that gives the
029 * low level representation of the value, and a {@link #referenceMask} that describes the location
030 * of object references in the value, and optionally a {@link #derivedReferenceBase}.
031 *
032 * <h2>Constructing {@link LIRKind} instances</h2>
033 *
034 * During LIR generation, every new {@link Value} should get a {@link LIRKind} of the correct
035 * {@link PlatformKind} that also contains the correct reference information. {@linkplain LIRKind
036 * LIRKinds} should be created as follows:
037 *
038 * <p>
039 * If the result value is created from one or more input values, the {@link LIRKind} should be
040 * created with {@link LIRKind#combine}(inputs). If the result has a different {@link PlatformKind}
041 * than the inputs, {@link LIRKind#combine}(inputs).{@link #changeType}(resultKind) should be used.
042 * <p>
043 * If the result is an exact copy of one of the inputs, {@link Value#getLIRKind()} can be used. Note
044 * that this is only correct for move-like operations, like conditional move or compare-and-swap.
045 * For convert operations, {@link LIRKind#combine} should be used.
046 * <p>
047 * If it is known that the result will be a reference (e.g. pointer arithmetic where the end result
048 * is a valid oop), {@link LIRKind#reference} should be used.
049 * <p>
050 * If it is known that the result will neither be a reference nor be derived from a reference,
051 * {@link LIRKind#value} can be used. If the operation producing this value has inputs, this is very
052 * likely wrong, and {@link LIRKind#combine} should be used instead.
053 * <p>
054 * If it is known that the result is derived from a reference in a way that the garbage collector
055 * can not track, {@link LIRKind#unknownReference} can be used. In most cases,
056 * {@link LIRKind#combine} should be used instead, since it is able to detect this automatically.
057 */
058public final class LIRKind {
059
060    /**
061     * The non-type. This uses {@link #unknownReference}, so it can never be part of an oop map.
062     */
063    public static final LIRKind Illegal = unknownReference(Kind.Illegal);
064
065    private final PlatformKind platformKind;
066    private final int referenceMask;
067
068    private AllocatableValue derivedReferenceBase;
069
070    private static final int UNKNOWN_REFERENCE = -1;
071
072    private LIRKind(PlatformKind platformKind, int referenceMask, AllocatableValue derivedReferenceBase) {
073        this.platformKind = platformKind;
074        this.referenceMask = referenceMask;
075        this.derivedReferenceBase = derivedReferenceBase;
076
077        assert derivedReferenceBase == null || !derivedReferenceBase.getLIRKind().isDerivedReference() : "derived reference can't have another derived reference as base";
078    }
079
080    /**
081     * Create a {@link LIRKind} of type {@code platformKind} that contains a primitive value. Should
082     * be only used when it's guaranteed that the value is not even indirectly derived from a
083     * reference. Otherwise, {@link #combine(Value...)} should be used instead.
084     */
085    public static LIRKind value(PlatformKind platformKind) {
086        assert platformKind != Kind.Object : "Object should always be used as reference type";
087        return new LIRKind(platformKind, 0, null);
088    }
089
090    /**
091     * Create a {@link LIRKind} of type {@code platformKind} that contains a single tracked oop
092     * reference.
093     */
094    public static LIRKind reference(PlatformKind platformKind) {
095        return derivedReference(platformKind, null);
096    }
097
098    /**
099     * 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 Kind) {
447            return ((Kind) platformKind).getStackKind();
448        }
449        return platformKind;
450    }
451}