1 /* 2 * Copyright (c) 2014, 2018, 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. Oracle designates this 8 * particular file as subject to the "Classpath" exception as provided 9 * by Oracle in the LICENSE file that accompanied this code. 10 * 11 * This code is distributed in the hope that it will be useful, but WITHOUT 12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14 * version 2 for more details (a copy is included in the LICENSE file that 15 * accompanied this code). 16 * 17 * You should have received a copy of the GNU General Public License version 18 * 2 along with this work; if not, write to the Free Software Foundation, 19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 20 * 21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 22 * or visit www.oracle.com if you need additional information or have any 23 * questions. 24 */ 25 26 package java.lang.invoke; 27 28 import sun.invoke.util.Wrapper; 29 30 import java.lang.invoke.MethodHandles.Lookup; 31 import java.lang.ref.SoftReference; 32 import java.util.Arrays; 33 import java.util.Collections; 34 import java.util.Comparator; 35 import java.util.TreeMap; 36 import java.util.concurrent.ConcurrentHashMap; 37 38 import static java.lang.invoke.LambdaForm.*; 39 import static java.lang.invoke.LambdaForm.BasicType.*; 40 import static java.lang.invoke.MethodHandleImpl.Intrinsic; 41 import static java.lang.invoke.MethodHandleImpl.NF_loop; 42 import static java.lang.invoke.MethodHandleImpl.makeIntrinsic; 43 44 /** Transforms on LFs. 45 * A lambda-form editor can derive new LFs from its base LF. 46 * The editor can cache derived LFs, which simplifies the reuse of their underlying bytecodes. 47 * To support this caching, a LF has an optional pointer to its editor. 48 */ 49 class LambdaFormEditor { 50 final LambdaForm lambdaForm; 51 52 private LambdaFormEditor(LambdaForm lambdaForm) { 53 this.lambdaForm = lambdaForm; 54 } 55 56 // Factory method. 57 static LambdaFormEditor lambdaFormEditor(LambdaForm lambdaForm) { 58 // TO DO: Consider placing intern logic here, to cut down on duplication. 59 // lambdaForm = findPreexistingEquivalent(lambdaForm) 60 61 // Always use uncustomized version for editing. 62 // It helps caching and customized LambdaForms reuse transformCache field to keep a link to uncustomized version. 63 return new LambdaFormEditor(lambdaForm.uncustomize()); 64 } 65 66 // Transform types 67 // maybe add more for guard with test, catch exception, pointwise type conversions 68 private static final byte 69 BIND_ARG = 1, 70 ADD_ARG = 2, 71 DUP_ARG = 3, 72 SPREAD_ARGS = 4, 73 FILTER_ARG = 5, 74 FILTER_RETURN = 6, 75 FILTER_RETURN_TO_ZERO = 7, 76 COLLECT_ARGS = 8, 77 COLLECT_ARGS_TO_VOID = 9, 78 COLLECT_ARGS_TO_ARRAY = 10, 79 FOLD_ARGS = 11, 80 FOLD_ARGS_TO_VOID = 12, 81 PERMUTE_ARGS = 13, 82 LOCAL_TYPES = 14, 83 FOLD_SELECT_ARGS = 15, 84 FOLD_SELECT_ARGS_TO_VOID = 16, 85 FILTER_SELECT_ARGS = 17, 86 REPEAT_FILTER_ARGS = 18; 87 88 /** 89 * A description of a cached transform, possibly associated with the result of the transform. 90 * The logical content is a sequence of byte values, starting with a kind value. 91 * The sequence is unterminated, ending with an indefinite number of zero bytes. 92 * Sequences that are simple (short enough and with small enough values) pack into a 64-bit long. 93 * 94 * Tightly coupled with the TransformKey class, which is used to lookup existing 95 * Transforms. 96 */ 97 private static final class Transform extends SoftReference<LambdaForm> { 98 final long packedBytes; 99 final byte[] fullBytes; 100 101 private Transform(long packedBytes, byte[] fullBytes, LambdaForm result) { 102 super(result); 103 this.packedBytes = packedBytes; 104 this.fullBytes = fullBytes; 105 } 106 107 @Override 108 public boolean equals(Object obj) { 109 if (obj instanceof TransformKey) { 110 return equals((TransformKey) obj); 111 } 112 return obj instanceof Transform && equals((Transform)obj); 113 } 114 115 private boolean equals(TransformKey that) { 116 return this.packedBytes == that.packedBytes && Arrays.equals(this.fullBytes, that.fullBytes); 117 } 118 119 private boolean equals(Transform that) { 120 return this.packedBytes == that.packedBytes && Arrays.equals(this.fullBytes, that.fullBytes); 121 } 122 123 @Override 124 public int hashCode() { 125 if (packedBytes != 0) { 126 assert(fullBytes == null); 127 return Long.hashCode(packedBytes); 128 } 129 return Arrays.hashCode(fullBytes); 130 } 131 132 @Override 133 public String toString() { 134 StringBuilder buf = new StringBuilder(); 135 buf.append(new TransformKey(packedBytes, fullBytes).toString()); 136 LambdaForm result = get(); 137 if (result != null) { 138 buf.append(" result="); 139 buf.append(result); 140 } 141 return buf.toString(); 142 } 143 } 144 145 /** 146 * Used as a lookup key to find existing Transforms 147 */ 148 private static final class TransformKey { 149 final long packedBytes; 150 final byte[] fullBytes; 151 152 private TransformKey(long packedBytes) { 153 this.packedBytes = packedBytes; 154 this.fullBytes = null; 155 } 156 157 private TransformKey(byte[] fullBytes) { 158 this.fullBytes = fullBytes; 159 this.packedBytes = 0; 160 } 161 162 private TransformKey(long packedBytes, byte[] fullBytes) { 163 this.fullBytes = fullBytes; 164 this.packedBytes = packedBytes; 165 } 166 167 private static byte bval(int b) { 168 assert((b & 0xFF) == b); // incoming value must fit in *unsigned* byte 169 return (byte)b; 170 } 171 static TransformKey of(byte k, int b1) { 172 byte b0 = bval(k); 173 if (inRange(b0 | b1)) 174 return new TransformKey(packedBytes(b0, b1)); 175 else 176 return new TransformKey(fullBytes(b0, b1)); 177 } 178 static TransformKey of(byte b0, int b1, int b2) { 179 if (inRange(b0 | b1 | b2)) 180 return new TransformKey(packedBytes(b0, b1, b2)); 181 else 182 return new TransformKey(fullBytes(b0, b1, b2)); 183 } 184 static TransformKey of(byte b0, int b1, int b2, int b3) { 185 if (inRange(b0 | b1 | b2 | b3)) 186 return new TransformKey(packedBytes(b0, b1, b2, b3)); 187 else 188 return new TransformKey(fullBytes(b0, b1, b2, b3)); 189 } 190 private static final byte[] NO_BYTES = {}; 191 static TransformKey of(byte kind, int... b123) { 192 return ofBothArrays(kind, b123, NO_BYTES); 193 } 194 195 static TransformKey of(byte kind, int b1, int[] b23456) { 196 byte[] fullBytes = new byte[b23456.length + 2]; 197 fullBytes[0] = kind; 198 fullBytes[1] = bval(b1); 199 for (int i = 0; i < b23456.length; i++) { 200 fullBytes[i + 2] = TransformKey.bval(b23456[i]); 201 } 202 long packedBytes = packedBytes(fullBytes); 203 if (packedBytes != 0) 204 return new TransformKey(packedBytes); 205 else 206 return new TransformKey(fullBytes); 207 } 208 209 static TransformKey of(byte kind, int b1, int b2, byte[] b345) { 210 return ofBothArrays(kind, new int[]{ b1, b2 }, b345); 211 } 212 private static TransformKey ofBothArrays(byte kind, int[] b123, byte[] b456) { 213 byte[] fullBytes = new byte[1 + b123.length + b456.length]; 214 int i = 0; 215 fullBytes[i++] = bval(kind); 216 for (int bv : b123) { 217 fullBytes[i++] = bval(bv); 218 } 219 for (byte bv : b456) { 220 fullBytes[i++] = bv; 221 } 222 long packedBytes = packedBytes(fullBytes); 223 if (packedBytes != 0) 224 return new TransformKey(packedBytes); 225 else 226 return new TransformKey(fullBytes); 227 } 228 229 private static final boolean STRESS_TEST = false; // turn on to disable most packing 230 private static final int 231 PACKED_BYTE_SIZE = (STRESS_TEST ? 2 : 4), 232 PACKED_BYTE_MASK = (1 << PACKED_BYTE_SIZE) - 1, 233 PACKED_BYTE_MAX_LENGTH = (STRESS_TEST ? 3 : 64 / PACKED_BYTE_SIZE); 234 235 private static long packedBytes(byte[] bytes) { 236 if (!inRange(bytes[0]) || bytes.length > PACKED_BYTE_MAX_LENGTH) 237 return 0; 238 long pb = 0; 239 int bitset = 0; 240 for (int i = 0; i < bytes.length; i++) { 241 int b = bytes[i] & 0xFF; 242 bitset |= b; 243 pb |= (long)b << (i * PACKED_BYTE_SIZE); 244 } 245 if (!inRange(bitset)) 246 return 0; 247 return pb; 248 } 249 private static long packedBytes(int b0, int b1) { 250 assert(inRange(b0 | b1)); 251 return ( (b0 << 0*PACKED_BYTE_SIZE) 252 | (b1 << 1*PACKED_BYTE_SIZE)); 253 } 254 private static long packedBytes(int b0, int b1, int b2) { 255 assert(inRange(b0 | b1 | b2)); 256 return ( (b0 << 0*PACKED_BYTE_SIZE) 257 | (b1 << 1*PACKED_BYTE_SIZE) 258 | (b2 << 2*PACKED_BYTE_SIZE)); 259 } 260 private static long packedBytes(int b0, int b1, int b2, int b3) { 261 assert(inRange(b0 | b1 | b2 | b3)); 262 return ( (b0 << 0*PACKED_BYTE_SIZE) 263 | (b1 << 1*PACKED_BYTE_SIZE) 264 | (b2 << 2*PACKED_BYTE_SIZE) 265 | (b3 << 3*PACKED_BYTE_SIZE)); 266 } 267 private static boolean inRange(int bitset) { 268 assert((bitset & 0xFF) == bitset); // incoming values must fit in *unsigned* byte 269 return ((bitset & ~PACKED_BYTE_MASK) == 0); 270 } 271 private static byte[] fullBytes(int... byteValues) { 272 byte[] bytes = new byte[byteValues.length]; 273 int i = 0; 274 for (int bv : byteValues) { 275 bytes[i++] = bval(bv); 276 } 277 assert(packedBytes(bytes) == 0); 278 return bytes; 279 } 280 281 Transform withResult(LambdaForm result) { 282 return new Transform(this.packedBytes, this.fullBytes, result); 283 } 284 285 @Override 286 public String toString() { 287 StringBuilder buf = new StringBuilder(); 288 long bits = packedBytes; 289 if (bits != 0) { 290 buf.append("("); 291 while (bits != 0) { 292 buf.append(bits & PACKED_BYTE_MASK); 293 bits >>>= PACKED_BYTE_SIZE; 294 if (bits != 0) buf.append(","); 295 } 296 buf.append(")"); 297 } 298 if (fullBytes != null) { 299 buf.append("unpacked"); 300 buf.append(Arrays.toString(fullBytes)); 301 } 302 return buf.toString(); 303 } 304 305 @Override 306 public boolean equals(Object obj) { 307 if (obj instanceof TransformKey) { 308 return equals((TransformKey) obj); 309 } 310 return obj instanceof Transform && equals((Transform)obj); 311 } 312 313 private boolean equals(TransformKey that) { 314 return this.packedBytes == that.packedBytes && Arrays.equals(this.fullBytes, that.fullBytes); 315 } 316 317 private boolean equals(Transform that) { 318 return this.packedBytes == that.packedBytes && Arrays.equals(this.fullBytes, that.fullBytes); 319 } 320 321 @Override 322 public int hashCode() { 323 if (packedBytes != 0) { 324 assert(fullBytes == null); 325 return Long.hashCode(packedBytes); 326 } 327 return Arrays.hashCode(fullBytes); 328 } 329 } 330 331 /** Find a previously cached transform equivalent to the given one, and return its result. */ 332 private LambdaForm getInCache(TransformKey key) { 333 // The transformCache is one of null, Transform, Transform[], or ConcurrentHashMap. 334 Object c = lambdaForm.transformCache; 335 Transform k = null; 336 if (c instanceof ConcurrentHashMap) { 337 @SuppressWarnings("unchecked") 338 ConcurrentHashMap<Transform,Transform> m = (ConcurrentHashMap<Transform,Transform>) c; 339 k = m.get(key); 340 } else if (c == null) { 341 return null; 342 } else if (c instanceof Transform t) { 343 // one-element cache avoids overhead of an array 344 if (t.equals(key)) k = t; 345 } else { 346 Transform[] ta = (Transform[])c; 347 for (int i = 0; i < ta.length; i++) { 348 Transform t = ta[i]; 349 if (t == null) break; 350 if (t.equals(key)) { k = t; break; } 351 } 352 } 353 assert(k == null || key.equals(k)); 354 return (k != null) ? k.get() : null; 355 } 356 357 /** Arbitrary but reasonable limits on Transform[] size for cache. */ 358 private static final int MIN_CACHE_ARRAY_SIZE = 4, MAX_CACHE_ARRAY_SIZE = 16; 359 360 /** Cache a transform with its result, and return that result. 361 * But if an equivalent transform has already been cached, return its result instead. 362 */ 363 private LambdaForm putInCache(TransformKey key, LambdaForm form) { 364 Transform transform = key.withResult(form); 365 for (int pass = 0; ; pass++) { 366 Object c = lambdaForm.transformCache; 367 if (c instanceof ConcurrentHashMap) { 368 @SuppressWarnings("unchecked") 369 ConcurrentHashMap<Transform,Transform> m = (ConcurrentHashMap<Transform,Transform>) c; 370 Transform k = m.putIfAbsent(transform, transform); 371 if (k == null) return form; 372 LambdaForm result = k.get(); 373 if (result != null) { 374 return result; 375 } else { 376 if (m.replace(transform, k, transform)) { 377 return form; 378 } else { 379 continue; 380 } 381 } 382 } 383 assert(pass == 0); 384 synchronized (lambdaForm) { 385 c = lambdaForm.transformCache; 386 if (c instanceof ConcurrentHashMap) 387 continue; 388 if (c == null) { 389 lambdaForm.transformCache = transform; 390 return form; 391 } 392 Transform[] ta; 393 if (c instanceof Transform k) { 394 if (k.equals(key)) { 395 LambdaForm result = k.get(); 396 if (result == null) { 397 lambdaForm.transformCache = transform; 398 return form; 399 } else { 400 return result; 401 } 402 } else if (k.get() == null) { // overwrite stale entry 403 lambdaForm.transformCache = transform; 404 return form; 405 } 406 // expand one-element cache to small array 407 ta = new Transform[MIN_CACHE_ARRAY_SIZE]; 408 ta[0] = k; 409 lambdaForm.transformCache = ta; 410 } else { 411 // it is already expanded 412 ta = (Transform[])c; 413 } 414 int len = ta.length; 415 int stale = -1; 416 int i; 417 for (i = 0; i < len; i++) { 418 Transform k = ta[i]; 419 if (k == null) { 420 break; 421 } 422 if (k.equals(transform)) { 423 LambdaForm result = k.get(); 424 if (result == null) { 425 ta[i] = transform; 426 return form; 427 } else { 428 return result; 429 } 430 } else if (stale < 0 && k.get() == null) { 431 stale = i; // remember 1st stale entry index 432 } 433 } 434 if (i < len || stale >= 0) { 435 // just fall through to cache update 436 } else if (len < MAX_CACHE_ARRAY_SIZE) { 437 len = Math.min(len * 2, MAX_CACHE_ARRAY_SIZE); 438 ta = Arrays.copyOf(ta, len); 439 lambdaForm.transformCache = ta; 440 } else { 441 ConcurrentHashMap<Transform, Transform> m = new ConcurrentHashMap<>(MAX_CACHE_ARRAY_SIZE * 2); 442 for (Transform k : ta) { 443 m.put(k, k); 444 } 445 lambdaForm.transformCache = m; 446 // The second iteration will update for this query, concurrently. 447 continue; 448 } 449 int idx = (stale >= 0) ? stale : i; 450 ta[idx] = transform; 451 return form; 452 } 453 } 454 } 455 456 private LambdaFormBuffer buffer() { 457 return new LambdaFormBuffer(lambdaForm); 458 } 459 460 /// Editing methods for method handles. These need to have fast paths. 461 462 private BoundMethodHandle.SpeciesData oldSpeciesData() { 463 return BoundMethodHandle.speciesDataFor(lambdaForm); 464 } 465 466 private BoundMethodHandle.SpeciesData newSpeciesData(BasicType type) { 467 return oldSpeciesData().extendWith((byte) type.ordinal()); 468 } 469 470 BoundMethodHandle bindArgumentL(BoundMethodHandle mh, int pos, Object value) { 471 assert(mh.speciesData() == oldSpeciesData()); 472 BasicType bt = L_TYPE; 473 MethodType type2 = bindArgumentType(mh, pos, bt); 474 LambdaForm form2 = bindArgumentForm(1+pos); 475 return mh.copyWithExtendL(type2, form2, value); 476 } 477 BoundMethodHandle bindArgumentI(BoundMethodHandle mh, int pos, int value) { 478 assert(mh.speciesData() == oldSpeciesData()); 479 BasicType bt = I_TYPE; 480 MethodType type2 = bindArgumentType(mh, pos, bt); 481 LambdaForm form2 = bindArgumentForm(1+pos); 482 return mh.copyWithExtendI(type2, form2, value); 483 } 484 485 BoundMethodHandle bindArgumentJ(BoundMethodHandle mh, int pos, long value) { 486 assert(mh.speciesData() == oldSpeciesData()); 487 BasicType bt = J_TYPE; 488 MethodType type2 = bindArgumentType(mh, pos, bt); 489 LambdaForm form2 = bindArgumentForm(1+pos); 490 return mh.copyWithExtendJ(type2, form2, value); 491 } 492 493 BoundMethodHandle bindArgumentF(BoundMethodHandle mh, int pos, float value) { 494 assert(mh.speciesData() == oldSpeciesData()); 495 BasicType bt = F_TYPE; 496 MethodType type2 = bindArgumentType(mh, pos, bt); 497 LambdaForm form2 = bindArgumentForm(1+pos); 498 return mh.copyWithExtendF(type2, form2, value); 499 } 500 501 BoundMethodHandle bindArgumentD(BoundMethodHandle mh, int pos, double value) { 502 assert(mh.speciesData() == oldSpeciesData()); 503 BasicType bt = D_TYPE; 504 MethodType type2 = bindArgumentType(mh, pos, bt); 505 LambdaForm form2 = bindArgumentForm(1+pos); 506 return mh.copyWithExtendD(type2, form2, value); 507 } 508 509 private MethodType bindArgumentType(BoundMethodHandle mh, int pos, BasicType bt) { 510 assert(mh.form.uncustomize() == lambdaForm); 511 assert(mh.form.names[1+pos].type == bt); 512 assert(BasicType.basicType(mh.type().parameterType(pos)) == bt); 513 return mh.type().dropParameterTypes(pos, pos+1); 514 } 515 516 /// Editing methods for lambda forms. 517 // Each editing method can (potentially) cache the edited LF so that it can be reused later. 518 519 LambdaForm bindArgumentForm(int pos) { 520 TransformKey key = TransformKey.of(BIND_ARG, pos); 521 LambdaForm form = getInCache(key); 522 if (form != null) { 523 assert(form.parameterConstraint(0) == newSpeciesData(lambdaForm.parameterType(pos))); 524 return form; 525 } 526 LambdaFormBuffer buf = buffer(); 527 buf.startEdit(); 528 529 BoundMethodHandle.SpeciesData oldData = oldSpeciesData(); 530 BoundMethodHandle.SpeciesData newData = newSpeciesData(lambdaForm.parameterType(pos)); 531 Name oldBaseAddress = lambdaForm.parameter(0); // BMH holding the values 532 Name newBaseAddress; 533 NamedFunction getter = newData.getterFunction(oldData.fieldCount()); 534 535 if (pos != 0) { 536 // The newly created LF will run with a different BMH. 537 // Switch over any pre-existing BMH field references to the new BMH class. 538 buf.replaceFunctions(oldData.getterFunctions(), newData.getterFunctions(), oldBaseAddress); 539 newBaseAddress = oldBaseAddress.withConstraint(newData); 540 buf.renameParameter(0, newBaseAddress); 541 buf.replaceParameterByNewExpression(pos, new Name(getter, newBaseAddress)); 542 } else { 543 // cannot bind the MH arg itself, unless oldData is empty 544 assert(oldData == BoundMethodHandle.SPECIALIZER.topSpecies()); 545 newBaseAddress = new Name(L_TYPE).withConstraint(newData); 546 buf.replaceParameterByNewExpression(0, new Name(getter, newBaseAddress)); 547 buf.insertParameter(0, newBaseAddress); 548 } 549 550 form = buf.endEdit(); 551 return putInCache(key, form); 552 } 553 554 LambdaForm addArgumentForm(int pos, BasicType type) { 555 TransformKey key = TransformKey.of(ADD_ARG, pos, type.ordinal()); 556 LambdaForm form = getInCache(key); 557 if (form != null) { 558 assert(form.arity == lambdaForm.arity+1); 559 assert(form.parameterType(pos) == type); 560 return form; 561 } 562 LambdaFormBuffer buf = buffer(); 563 buf.startEdit(); 564 565 buf.insertParameter(pos, new Name(type)); 566 567 form = buf.endEdit(); 568 return putInCache(key, form); 569 } 570 571 LambdaForm dupArgumentForm(int srcPos, int dstPos) { 572 TransformKey key = TransformKey.of(DUP_ARG, srcPos, dstPos); 573 LambdaForm form = getInCache(key); 574 if (form != null) { 575 assert(form.arity == lambdaForm.arity-1); 576 return form; 577 } 578 LambdaFormBuffer buf = buffer(); 579 buf.startEdit(); 580 581 assert(lambdaForm.parameter(srcPos).constraint == null); 582 assert(lambdaForm.parameter(dstPos).constraint == null); 583 buf.replaceParameterByCopy(dstPos, srcPos); 584 585 form = buf.endEdit(); 586 return putInCache(key, form); 587 } 588 589 LambdaForm spreadArgumentsForm(int pos, Class<?> arrayType, int arrayLength) { 590 Class<?> elementType = arrayType.getComponentType(); 591 Class<?> erasedArrayType = arrayType; 592 if (!elementType.isPrimitive()) 593 erasedArrayType = Object[].class; 594 BasicType bt = basicType(elementType); 595 int elementTypeKey = bt.ordinal(); 596 if (bt.basicTypeClass() != elementType) { 597 if (elementType.isPrimitive()) { 598 elementTypeKey = TYPE_LIMIT + Wrapper.forPrimitiveType(elementType).ordinal(); 599 } 600 } 601 TransformKey key = TransformKey.of(SPREAD_ARGS, pos, elementTypeKey, arrayLength); 602 LambdaForm form = getInCache(key); 603 if (form != null) { 604 assert(form.arity == lambdaForm.arity - arrayLength + 1); 605 return form; 606 } 607 LambdaFormBuffer buf = buffer(); 608 buf.startEdit(); 609 610 assert(pos <= MethodType.MAX_JVM_ARITY); 611 assert(pos + arrayLength <= lambdaForm.arity); 612 assert(pos > 0); // cannot spread the MH arg itself 613 614 Name spreadParam = new Name(L_TYPE); 615 Name checkSpread = new Name(MethodHandleImpl.getFunction(MethodHandleImpl.NF_checkSpreadArgument), 616 spreadParam, arrayLength); 617 618 // insert the new expressions 619 int exprPos = lambdaForm.arity(); 620 buf.insertExpression(exprPos++, checkSpread); 621 // adjust the arguments 622 MethodHandle aload = MethodHandles.arrayElementGetter(erasedArrayType); 623 for (int i = 0; i < arrayLength; i++) { 624 Name loadArgument = new Name(new NamedFunction(makeIntrinsic(aload, Intrinsic.ARRAY_LOAD)), spreadParam, i); 625 buf.insertExpression(exprPos + i, loadArgument); 626 buf.replaceParameterByCopy(pos + i, exprPos + i); 627 } 628 buf.insertParameter(pos, spreadParam); 629 630 form = buf.endEdit(); 631 return putInCache(key, form); 632 } 633 634 LambdaForm collectArgumentsForm(int pos, MethodType collectorType) { 635 int collectorArity = collectorType.parameterCount(); 636 boolean dropResult = (collectorType.returnType() == void.class); 637 if (collectorArity == 1 && !dropResult) { 638 return filterArgumentForm(pos, basicType(collectorType.parameterType(0))); 639 } 640 byte[] newTypes = BasicType.basicTypesOrd(collectorType.ptypes()); 641 byte kind = (dropResult ? COLLECT_ARGS_TO_VOID : COLLECT_ARGS); 642 if (dropResult && collectorArity == 0) pos = 1; // pure side effect 643 TransformKey key = TransformKey.of(kind, pos, collectorArity, newTypes); 644 LambdaForm form = getInCache(key); 645 if (form != null) { 646 assert(form.arity == lambdaForm.arity - (dropResult ? 0 : 1) + collectorArity); 647 return form; 648 } 649 form = makeArgumentCombinationForm(pos, collectorType, false, dropResult); 650 return putInCache(key, form); 651 } 652 653 LambdaForm filterArgumentForm(int pos, BasicType newType) { 654 TransformKey key = TransformKey.of(FILTER_ARG, pos, newType.ordinal()); 655 LambdaForm form = getInCache(key); 656 if (form != null) { 657 assert(form.arity == lambdaForm.arity); 658 assert(form.parameterType(pos) == newType); 659 return form; 660 } 661 662 BasicType oldType = lambdaForm.parameterType(pos); 663 MethodType filterType = MethodType.methodType(oldType.basicTypeClass(), 664 newType.basicTypeClass()); 665 form = makeArgumentCombinationForm(pos, filterType, false, false); 666 return putInCache(key, form); 667 } 668 669 /** 670 * This creates a LF that will repeatedly invoke some unary filter function 671 * at each of the given positions. This allows fewer LFs and BMH species 672 * classes to be generated in typical cases compared to building up the form 673 * by reapplying of {@code filterArgumentForm(int,BasicType)}, and should do 674 * no worse in the worst case. 675 */ 676 LambdaForm filterRepeatedArgumentForm(BasicType newType, int... argPositions) { 677 assert (argPositions.length > 1); 678 TransformKey key = TransformKey.of(REPEAT_FILTER_ARGS, newType.ordinal(), argPositions); 679 LambdaForm form = getInCache(key); 680 if (form != null) { 681 assert(form.arity == lambdaForm.arity && 682 formParametersMatch(form, newType, argPositions)); 683 return form; 684 } 685 BasicType oldType = lambdaForm.parameterType(argPositions[0]); 686 MethodType filterType = MethodType.methodType(oldType.basicTypeClass(), 687 newType.basicTypeClass()); 688 form = makeRepeatedFilterForm(filterType, argPositions); 689 assert (formParametersMatch(form, newType, argPositions)); 690 return putInCache(key, form); 691 } 692 693 private boolean formParametersMatch(LambdaForm form, BasicType newType, int... argPositions) { 694 for (int i : argPositions) { 695 if (form.parameterType(i) != newType) { 696 return false; 697 } 698 } 699 return true; 700 } 701 702 private LambdaForm makeRepeatedFilterForm(MethodType combinerType, int... positions) { 703 assert (combinerType.parameterCount() == 1 && 704 combinerType == combinerType.basicType() && 705 combinerType.returnType() != void.class); 706 LambdaFormBuffer buf = buffer(); 707 buf.startEdit(); 708 709 BoundMethodHandle.SpeciesData oldData = oldSpeciesData(); 710 BoundMethodHandle.SpeciesData newData = newSpeciesData(L_TYPE); 711 712 // The newly created LF will run with a different BMH. 713 // Switch over any pre-existing BMH field references to the new BMH class. 714 Name oldBaseAddress = lambdaForm.parameter(0); // BMH holding the values 715 buf.replaceFunctions(oldData.getterFunctions(), newData.getterFunctions(), oldBaseAddress); 716 Name newBaseAddress = oldBaseAddress.withConstraint(newData); 717 buf.renameParameter(0, newBaseAddress); 718 719 // Insert the new expressions at the end 720 int exprPos = lambdaForm.arity(); 721 Name getCombiner = new Name(newData.getterFunction(oldData.fieldCount()), newBaseAddress); 722 buf.insertExpression(exprPos++, getCombiner); 723 724 // After inserting expressions, we insert parameters in order 725 // from lowest to highest, simplifying the calculation of where parameters 726 // and expressions are 727 var newParameters = new TreeMap<Name, Integer>(new Comparator<>() { 728 public int compare(Name n1, Name n2) { 729 return n1.index - n2.index; 730 } 731 }); 732 733 // Insert combiner expressions in reverse order so that the invocation of 734 // the resulting form will invoke the combiners in left-to-right order 735 for (int i = positions.length - 1; i >= 0; --i) { 736 int pos = positions[i]; 737 assert (pos > 0 && pos <= MethodType.MAX_JVM_ARITY && pos < lambdaForm.arity); 738 739 Name newParameter = new Name(pos, basicType(combinerType.parameterType(0))); 740 Object[] combinerArgs = {getCombiner, newParameter}; 741 742 Name callCombiner = new Name(combinerType, combinerArgs); 743 buf.insertExpression(exprPos++, callCombiner); 744 newParameters.put(newParameter, exprPos); 745 } 746 747 // Mix in new parameters from left to right in the buffer (this doesn't change 748 // execution order 749 int offset = 0; 750 for (var entry : newParameters.entrySet()) { 751 Name newParameter = entry.getKey(); 752 int from = entry.getValue(); 753 buf.insertParameter(newParameter.index() + 1 + offset, newParameter); 754 buf.replaceParameterByCopy(newParameter.index() + offset, from + offset); 755 offset++; 756 } 757 return buf.endEdit(); 758 } 759 760 761 private LambdaForm makeArgumentCombinationForm(int pos, 762 MethodType combinerType, 763 boolean keepArguments, boolean dropResult) { 764 LambdaFormBuffer buf = buffer(); 765 buf.startEdit(); 766 int combinerArity = combinerType.parameterCount(); 767 int resultArity = (dropResult ? 0 : 1); 768 769 assert(pos <= MethodType.MAX_JVM_ARITY); 770 assert(pos + resultArity + (keepArguments ? combinerArity : 0) <= lambdaForm.arity); 771 assert(pos > 0); // cannot filter the MH arg itself 772 assert(combinerType == combinerType.basicType()); 773 assert(combinerType.returnType() != void.class || dropResult); 774 775 BoundMethodHandle.SpeciesData oldData = oldSpeciesData(); 776 BoundMethodHandle.SpeciesData newData = newSpeciesData(L_TYPE); 777 778 // The newly created LF will run with a different BMH. 779 // Switch over any pre-existing BMH field references to the new BMH class. 780 Name oldBaseAddress = lambdaForm.parameter(0); // BMH holding the values 781 buf.replaceFunctions(oldData.getterFunctions(), newData.getterFunctions(), oldBaseAddress); 782 Name newBaseAddress = oldBaseAddress.withConstraint(newData); 783 buf.renameParameter(0, newBaseAddress); 784 785 Name getCombiner = new Name(newData.getterFunction(oldData.fieldCount()), newBaseAddress); 786 Object[] combinerArgs = new Object[1 + combinerArity]; 787 combinerArgs[0] = getCombiner; 788 Name[] newParams; 789 if (keepArguments) { 790 newParams = new Name[0]; 791 System.arraycopy(lambdaForm.names, pos + resultArity, 792 combinerArgs, 1, combinerArity); 793 } else { 794 newParams = new Name[combinerArity]; 795 for (int i = 0; i < newParams.length; i++) { 796 newParams[i] = new Name(pos + i, basicType(combinerType.parameterType(i))); 797 } 798 System.arraycopy(newParams, 0, 799 combinerArgs, 1, combinerArity); 800 } 801 Name callCombiner = new Name(combinerType, combinerArgs); 802 803 // insert the two new expressions 804 int exprPos = lambdaForm.arity(); 805 buf.insertExpression(exprPos+0, getCombiner); 806 buf.insertExpression(exprPos+1, callCombiner); 807 808 // insert new arguments, if needed 809 int argPos = pos + resultArity; // skip result parameter 810 for (Name newParam : newParams) { 811 buf.insertParameter(argPos++, newParam); 812 } 813 assert(buf.lastIndexOf(callCombiner) == exprPos+1+newParams.length); 814 if (!dropResult) { 815 buf.replaceParameterByCopy(pos, exprPos+1+newParams.length); 816 } 817 818 return buf.endEdit(); 819 } 820 821 private LambdaForm makeArgumentCombinationForm(int pos, 822 MethodType combinerType, 823 int[] argPositions, 824 boolean keepArguments, 825 boolean dropResult) { 826 LambdaFormBuffer buf = buffer(); 827 buf.startEdit(); 828 int combinerArity = combinerType.parameterCount(); 829 assert(combinerArity == argPositions.length); 830 831 int resultArity = (dropResult ? 0 : 1); 832 833 assert(pos <= lambdaForm.arity); 834 assert(pos > 0); // cannot filter the MH arg itself 835 assert(combinerType == combinerType.basicType()); 836 assert(combinerType.returnType() != void.class || dropResult); 837 838 BoundMethodHandle.SpeciesData oldData = oldSpeciesData(); 839 BoundMethodHandle.SpeciesData newData = newSpeciesData(L_TYPE); 840 841 // The newly created LF will run with a different BMH. 842 // Switch over any pre-existing BMH field references to the new BMH class. 843 Name oldBaseAddress = lambdaForm.parameter(0); // BMH holding the values 844 buf.replaceFunctions(oldData.getterFunctions(), newData.getterFunctions(), oldBaseAddress); 845 Name newBaseAddress = oldBaseAddress.withConstraint(newData); 846 buf.renameParameter(0, newBaseAddress); 847 848 Name getCombiner = new Name(newData.getterFunction(oldData.fieldCount()), newBaseAddress); 849 Object[] combinerArgs = new Object[1 + combinerArity]; 850 combinerArgs[0] = getCombiner; 851 Name newParam = null; 852 if (keepArguments) { 853 for (int i = 0; i < combinerArity; i++) { 854 combinerArgs[i + 1] = lambdaForm.parameter(1 + argPositions[i]); 855 assert (basicType(combinerType.parameterType(i)) == lambdaForm.parameterType(1 + argPositions[i])); 856 } 857 } else { 858 newParam = new Name(pos, BasicType.basicType(combinerType.returnType())); 859 for (int i = 0; i < combinerArity; i++) { 860 int argPos = 1 + argPositions[i]; 861 if (argPos == pos) { 862 combinerArgs[i + 1] = newParam; 863 } else { 864 combinerArgs[i + 1] = lambdaForm.parameter(argPos); 865 } 866 assert (basicType(combinerType.parameterType(i)) == lambdaForm.parameterType(1 + argPositions[i])); 867 } 868 } 869 Name callCombiner = new Name(combinerType, combinerArgs); 870 871 // insert the two new expressions 872 int exprPos = lambdaForm.arity(); 873 buf.insertExpression(exprPos+0, getCombiner); 874 buf.insertExpression(exprPos+1, callCombiner); 875 876 // insert new arguments, if needed 877 int argPos = pos + resultArity; // skip result parameter 878 if (newParam != null) { 879 buf.insertParameter(argPos++, newParam); 880 exprPos++; 881 } 882 assert(buf.lastIndexOf(callCombiner) == exprPos+1); 883 if (!dropResult) { 884 buf.replaceParameterByCopy(pos, exprPos+1); 885 } 886 887 return buf.endEdit(); 888 } 889 890 LambdaForm filterReturnForm(BasicType newType, boolean constantZero) { 891 byte kind = (constantZero ? FILTER_RETURN_TO_ZERO : FILTER_RETURN); 892 TransformKey key = TransformKey.of(kind, newType.ordinal()); 893 LambdaForm form = getInCache(key); 894 if (form != null) { 895 assert(form.arity == lambdaForm.arity); 896 assert(form.returnType() == newType); 897 return form; 898 } 899 LambdaFormBuffer buf = buffer(); 900 buf.startEdit(); 901 902 int insPos = lambdaForm.names.length; 903 Name callFilter; 904 if (constantZero) { 905 // Synthesize a constant zero value for the given type. 906 if (newType == V_TYPE) 907 callFilter = null; 908 else 909 callFilter = new Name(constantZero(newType)); 910 } else { 911 BoundMethodHandle.SpeciesData oldData = oldSpeciesData(); 912 BoundMethodHandle.SpeciesData newData = newSpeciesData(L_TYPE); 913 914 // The newly created LF will run with a different BMH. 915 // Switch over any pre-existing BMH field references to the new BMH class. 916 Name oldBaseAddress = lambdaForm.parameter(0); // BMH holding the values 917 buf.replaceFunctions(oldData.getterFunctions(), newData.getterFunctions(), oldBaseAddress); 918 Name newBaseAddress = oldBaseAddress.withConstraint(newData); 919 buf.renameParameter(0, newBaseAddress); 920 921 Name getFilter = new Name(newData.getterFunction(oldData.fieldCount()), newBaseAddress); 922 buf.insertExpression(insPos++, getFilter); 923 BasicType oldType = lambdaForm.returnType(); 924 if (oldType == V_TYPE) { 925 MethodType filterType = MethodType.methodType(newType.basicTypeClass()); 926 callFilter = new Name(filterType, getFilter); 927 } else { 928 MethodType filterType = MethodType.methodType(newType.basicTypeClass(), oldType.basicTypeClass()); 929 callFilter = new Name(filterType, getFilter, lambdaForm.names[lambdaForm.result]); 930 } 931 } 932 933 if (callFilter != null) 934 buf.insertExpression(insPos++, callFilter); 935 buf.setResult(callFilter); 936 937 form = buf.endEdit(); 938 return putInCache(key, form); 939 } 940 941 LambdaForm collectReturnValueForm(MethodType combinerType) { 942 LambdaFormBuffer buf = buffer(); 943 buf.startEdit(); 944 int combinerArity = combinerType.parameterCount(); 945 int argPos = lambdaForm.arity(); 946 int exprPos = lambdaForm.names.length; 947 948 BoundMethodHandle.SpeciesData oldData = oldSpeciesData(); 949 BoundMethodHandle.SpeciesData newData = newSpeciesData(L_TYPE); 950 951 // The newly created LF will run with a different BMH. 952 // Switch over any pre-existing BMH field references to the new BMH class. 953 Name oldBaseAddress = lambdaForm.parameter(0); // BMH holding the values 954 buf.replaceFunctions(oldData.getterFunctions(), newData.getterFunctions(), oldBaseAddress); 955 Name newBaseAddress = oldBaseAddress.withConstraint(newData); 956 buf.renameParameter(0, newBaseAddress); 957 958 // Now we set up the call to the filter 959 Name getCombiner = new Name(newData.getterFunction(oldData.fieldCount()), newBaseAddress); 960 961 Object[] combinerArgs = new Object[combinerArity + 1]; 962 combinerArgs[0] = getCombiner; // first (synthetic) argument should be the MH that acts as a target of the invoke 963 964 // set up additional adapter parameters (in case the combiner is not a unary function) 965 Name[] newParams = new Name[combinerArity - 1]; // last combiner parameter is the return adapter 966 for (int i = 0; i < newParams.length; i++) { 967 newParams[i] = new Name(argPos + i, basicType(combinerType.parameterType(i))); 968 } 969 970 // set up remaining filter parameters to point to the corresponding adapter parameters (see above) 971 System.arraycopy(newParams, 0, 972 combinerArgs, 1, combinerArity - 1); 973 974 // the last filter argument is set to point at the result of the target method handle 975 combinerArgs[combinerArity] = buf.name(lambdaForm.names.length - 1); 976 Name callCombiner = new Name(combinerType, combinerArgs); 977 978 // insert the two new expressions 979 buf.insertExpression(exprPos, getCombiner); 980 buf.insertExpression(exprPos + 1, callCombiner); 981 982 // insert additional arguments 983 int insPos = argPos; 984 for (Name newParam : newParams) { 985 buf.insertParameter(insPos++, newParam); 986 } 987 988 buf.setResult(callCombiner); 989 return buf.endEdit(); 990 } 991 992 LambdaForm foldArgumentsForm(int foldPos, boolean dropResult, MethodType combinerType) { 993 int combinerArity = combinerType.parameterCount(); 994 byte kind = (dropResult ? FOLD_ARGS_TO_VOID : FOLD_ARGS); 995 TransformKey key = TransformKey.of(kind, foldPos, combinerArity); 996 LambdaForm form = getInCache(key); 997 if (form != null) { 998 assert(form.arity == lambdaForm.arity - (kind == FOLD_ARGS ? 1 : 0)); 999 return form; 1000 } 1001 form = makeArgumentCombinationForm(foldPos, combinerType, true, dropResult); 1002 return putInCache(key, form); 1003 } 1004 1005 LambdaForm foldArgumentsForm(int foldPos, boolean dropResult, MethodType combinerType, int ... argPositions) { 1006 byte kind = (dropResult ? FOLD_SELECT_ARGS_TO_VOID : FOLD_SELECT_ARGS); 1007 TransformKey key = TransformKey.of(kind, foldPos, argPositions); 1008 LambdaForm form = getInCache(key); 1009 if (form != null) { 1010 assert(form.arity == lambdaForm.arity - (kind == FOLD_SELECT_ARGS ? 1 : 0)); 1011 return form; 1012 } 1013 form = makeArgumentCombinationForm(foldPos, combinerType, argPositions, true, dropResult); 1014 return putInCache(key, form); 1015 } 1016 1017 LambdaForm filterArgumentsForm(int filterPos, MethodType combinerType, int ... argPositions) { 1018 TransformKey key = TransformKey.of(FILTER_SELECT_ARGS, filterPos, argPositions); 1019 LambdaForm form = getInCache(key); 1020 if (form != null) { 1021 assert(form.arity == lambdaForm.arity); 1022 return form; 1023 } 1024 form = makeArgumentCombinationForm(filterPos, combinerType, argPositions, false, false); 1025 return putInCache(key, form); 1026 } 1027 1028 LambdaForm permuteArgumentsForm(int skip, int[] reorder) { 1029 assert(skip == 1); // skip only the leading MH argument, names[0] 1030 int length = lambdaForm.names.length; 1031 int outArgs = reorder.length; 1032 int inTypes = 0; 1033 boolean nullPerm = true; 1034 for (int i = 0; i < reorder.length; i++) { 1035 int inArg = reorder[i]; 1036 if (inArg != i) nullPerm = false; 1037 inTypes = Math.max(inTypes, inArg+1); 1038 } 1039 assert(skip + reorder.length == lambdaForm.arity); 1040 if (nullPerm) return lambdaForm; // do not bother to cache 1041 TransformKey key = TransformKey.of(PERMUTE_ARGS, reorder); 1042 LambdaForm form = getInCache(key); 1043 if (form != null) { 1044 assert(form.arity == skip+inTypes) : form; 1045 return form; 1046 } 1047 1048 BasicType[] types = new BasicType[inTypes]; 1049 for (int i = 0; i < outArgs; i++) { 1050 int inArg = reorder[i]; 1051 types[inArg] = lambdaForm.names[skip + i].type; 1052 } 1053 assert (skip + outArgs == lambdaForm.arity); 1054 assert (permutedTypesMatch(reorder, types, lambdaForm.names, skip)); 1055 int pos = 0; 1056 while (pos < outArgs && reorder[pos] == pos) { 1057 pos += 1; 1058 } 1059 Name[] names2 = new Name[length - outArgs + inTypes]; 1060 System.arraycopy(lambdaForm.names, 0, names2, 0, skip + pos); 1061 int bodyLength = length - lambdaForm.arity; 1062 System.arraycopy(lambdaForm.names, skip + outArgs, names2, skip + inTypes, bodyLength); 1063 int arity2 = names2.length - bodyLength; 1064 int result2 = lambdaForm.result; 1065 if (result2 >= skip) { 1066 if (result2 < skip + outArgs) { 1067 result2 = reorder[result2 - skip] + skip; 1068 } else { 1069 result2 = result2 - outArgs + inTypes; 1070 } 1071 } 1072 for (int j = pos; j < outArgs; j++) { 1073 Name n = lambdaForm.names[skip + j]; 1074 int i = reorder[j]; 1075 Name n2 = names2[skip + i]; 1076 if (n2 == null) { 1077 names2[skip + i] = n2 = new Name(types[i]); 1078 } else { 1079 assert (n2.type == types[i]); 1080 } 1081 for (int k = arity2; k < names2.length; k++) { 1082 names2[k] = names2[k].replaceName(n, n2); 1083 } 1084 } 1085 for (int i = skip + pos; i < arity2; i++) { 1086 if (names2[i] == null) { 1087 names2[i] = argument(i, types[i - skip]); 1088 } 1089 } 1090 for (int j = lambdaForm.arity; j < lambdaForm.names.length; j++) { 1091 int i = j - lambdaForm.arity + arity2; 1092 Name n = lambdaForm.names[j]; 1093 Name n2 = names2[i]; 1094 if (n != n2) { 1095 for (int k = i + 1; k < names2.length; k++) { 1096 names2[k] = names2[k].replaceName(n, n2); 1097 } 1098 } 1099 } 1100 1101 form = new LambdaForm(arity2, names2, result2); 1102 return putInCache(key, form); 1103 } 1104 1105 LambdaForm noteLoopLocalTypesForm(int pos, BasicType[] localTypes) { 1106 assert(lambdaForm.isLoop(pos)); 1107 int[] desc = BasicType.basicTypeOrds(localTypes); 1108 desc = Arrays.copyOf(desc, desc.length + 1); 1109 desc[desc.length - 1] = pos; 1110 TransformKey key = TransformKey.of(LOCAL_TYPES, desc); 1111 LambdaForm form = getInCache(key); 1112 if (form != null) { 1113 return form; 1114 } 1115 1116 // replace the null entry in the MHImpl.loop invocation with localTypes 1117 Name invokeLoop = lambdaForm.names[pos + 1]; 1118 assert(invokeLoop.function.equals(MethodHandleImpl.getFunction(NF_loop))); 1119 Object[] args = Arrays.copyOf(invokeLoop.arguments, invokeLoop.arguments.length); 1120 assert(args[0] == null); 1121 args[0] = localTypes; 1122 1123 LambdaFormBuffer buf = buffer(); 1124 buf.startEdit(); 1125 buf.changeName(pos + 1, new Name(MethodHandleImpl.getFunction(NF_loop), args)); 1126 form = buf.endEdit(); 1127 1128 return putInCache(key, form); 1129 } 1130 1131 static boolean permutedTypesMatch(int[] reorder, BasicType[] types, Name[] names, int skip) { 1132 for (int i = 0; i < reorder.length; i++) { 1133 assert (names[skip + i].isParam()); 1134 assert (names[skip + i].type == types[reorder[i]]); 1135 } 1136 return true; 1137 } 1138 }