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