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 }