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 */ 23package org.graalvm.compiler.core.common; 24 25import org.graalvm.compiler.core.common.alloc.RegisterAllocationConfig; 26 27import jdk.vm.ci.code.Architecture; 28import jdk.vm.ci.meta.AllocatableValue; 29import jdk.vm.ci.meta.JavaKind; 30import jdk.vm.ci.meta.PlatformKind; 31import jdk.vm.ci.meta.Value; 32import 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 */ 65public 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} 482