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