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