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 }