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 }