1 /* 2 * Copyright (c) 2014, 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 java.util.Arrays; 29 import static java.lang.invoke.LambdaForm.*; 30 import static java.lang.invoke.LambdaForm.BasicType.*; 31 import static java.lang.invoke.MethodHandleImpl.Intrinsic; 32 import java.util.Collections; 33 import java.util.concurrent.ConcurrentHashMap; 34 35 import sun.invoke.util.Wrapper; 36 37 /** Transforms on LFs. 38 * A lambda-form editor can derive new LFs from its base LF. 39 * The editor can cache derived LFs, which simplifies the reuse of their underlying bytecodes. 40 * To support this caching, a LF has an optional pointer to its editor. 41 */ 42 class LambdaFormEditor { 43 final LambdaForm lambdaForm; 44 45 private LambdaFormEditor(LambdaForm lambdaForm) { 46 this.lambdaForm = lambdaForm; 47 } 48 49 // Factory method. 50 static LambdaFormEditor lambdaFormEditor(LambdaForm lambdaForm) { 51 // TO DO: Consider placing intern logic here, to cut down on duplication. 52 // lambdaForm = findPreexistingEquivalent(lambdaForm) 53 return new LambdaFormEditor(lambdaForm); 54 } 55 56 /** A description of a cached transform, possibly associated with the result of the transform. 57 * The logical content is a sequence of byte values, starting with a Kind.ordinal value. 58 * The sequence is unterminated, ending with an indefinite number of zero bytes. 59 * Sequences that are simple (short enough and with small enough values) pack into a 64-bit long. 60 */ 61 private static final class Transform { 62 final long packedBytes; 63 final byte[] fullBytes; 64 final LambdaForm result; // result of transform, or null, if there is none available 65 66 private enum Kind { 67 NO_KIND, // necessary because ordinal must be greater than zero 68 BIND_ARG, ADD_ARG, DUP_ARG, 69 SPREAD_ARGS, 70 FILTER_ARG, FILTER_RETURN, FILTER_RETURN_TO_ZERO, 71 COLLECT_ARGS, COLLECT_ARGS_TO_VOID, COLLECT_ARGS_TO_ARRAY, 72 FOLD_ARGS, FOLD_ARGS_TO_VOID, 73 PERMUTE_ARGS 74 //maybe add more for guard with test, catch exception, pointwise type conversions 75 } 76 77 private static final boolean STRESS_TEST = false; // turn on to disable most packing 78 private static final int 79 PACKED_BYTE_SIZE = (STRESS_TEST ? 2 : 4), 80 PACKED_BYTE_MASK = (1 << PACKED_BYTE_SIZE) - 1, 81 PACKED_BYTE_MAX_LENGTH = (STRESS_TEST ? 3 : 64 / PACKED_BYTE_SIZE); 82 83 private static long packedBytes(byte[] bytes) { 84 if (bytes.length > PACKED_BYTE_MAX_LENGTH) return 0; 85 long pb = 0; 86 int bitset = 0; 87 for (int i = 0; i < bytes.length; i++) { 88 int b = bytes[i] & 0xFF; 89 bitset |= b; 90 pb |= (long)b << (i * PACKED_BYTE_SIZE); 91 } 92 if (!inRange(bitset)) 93 return 0; 94 return pb; 95 } 96 private static long packedBytes(int b0, int b1) { 97 assert(inRange(b0 | b1)); 98 return ( (b0 << 0*PACKED_BYTE_SIZE) 99 | (b1 << 1*PACKED_BYTE_SIZE)); 100 } 101 private static long packedBytes(int b0, int b1, int b2) { 102 assert(inRange(b0 | b1 | b2)); 103 return ( (b0 << 0*PACKED_BYTE_SIZE) 104 | (b1 << 1*PACKED_BYTE_SIZE) 105 | (b2 << 2*PACKED_BYTE_SIZE)); 106 } 107 private static long packedBytes(int b0, int b1, int b2, int b3) { 108 assert(inRange(b0 | b1 | b2 | b3)); 109 return ( (b0 << 0*PACKED_BYTE_SIZE) 110 | (b1 << 1*PACKED_BYTE_SIZE) 111 | (b2 << 2*PACKED_BYTE_SIZE) 112 | (b3 << 3*PACKED_BYTE_SIZE)); 113 } 114 private static boolean inRange(int bitset) { 115 assert((bitset & 0xFF) == bitset); // incoming values must fit in *unsigned* byte 116 return ((bitset & ~PACKED_BYTE_MASK) == 0); 117 } 118 private static byte[] fullBytes(int... byteValues) { 119 byte[] bytes = new byte[byteValues.length]; 120 int i = 0; 121 for (int bv : byteValues) { 122 bytes[i++] = bval(bv); 123 } 124 assert(packedBytes(bytes) == 0); 125 return bytes; 126 } 127 128 private byte byteAt(int i) { 129 long pb = packedBytes; 130 if (pb == 0) { 131 if (i >= fullBytes.length) return 0; 132 return fullBytes[i]; 133 } 134 assert(fullBytes == null); 135 if (i > PACKED_BYTE_MAX_LENGTH) return 0; 136 int pos = (i * PACKED_BYTE_SIZE); 137 return (byte)((pb >>> pos) & PACKED_BYTE_MASK); 138 } 139 140 Kind kind() { return Kind.values()[byteAt(0)]; } 141 142 private Transform(long packedBytes, byte[] fullBytes, LambdaForm result) { 143 this.packedBytes = packedBytes; 144 this.fullBytes = fullBytes; 145 this.result = result; 146 } 147 private Transform(long packedBytes) { 148 this(packedBytes, null, null); 149 assert(packedBytes != 0); 150 } 151 private Transform(byte[] fullBytes) { 152 this(0, fullBytes, null); 153 } 154 155 private static byte bval(int b) { 156 assert((b & 0xFF) == b); // incoming value must fit in *unsigned* byte 157 return (byte)b; 158 } 159 private static byte bval(Kind k) { 160 return bval(k.ordinal()); 161 } 162 static Transform of(Kind 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(Kind k, int b1, int b2) { 170 byte b0 = (byte) k.ordinal(); 171 if (inRange(b0 | b1 | b2)) 172 return new Transform(packedBytes(b0, b1, b2)); 173 else 174 return new Transform(fullBytes(b0, b1, b2)); 175 } 176 static Transform of(Kind k, int b1, int b2, int b3) { 177 byte b0 = (byte) k.ordinal(); 178 if (inRange(b0 | b1 | b2 | b3)) 179 return new Transform(packedBytes(b0, b1, b2, b3)); 180 else 181 return new Transform(fullBytes(b0, b1, b2, b3)); 182 } 183 private static final byte[] NO_BYTES = {}; 184 static Transform of(Kind k, int... b123) { 185 return ofBothArrays(k, b123, NO_BYTES); 186 } 187 static Transform of(Kind k, int b1, byte[] b234) { 188 return ofBothArrays(k, new int[]{ b1 }, b234); 189 } 190 static Transform of(Kind k, int b1, int b2, byte[] b345) { 191 return ofBothArrays(k, new int[]{ b1, b2 }, b345); 192 } 193 private static Transform ofBothArrays(Kind k, int[] b123, byte[] b456) { 194 byte[] fullBytes = new byte[1 + b123.length + b456.length]; 195 int i = 0; 196 fullBytes[i++] = bval(k); 197 for (int bv : b123) { 198 fullBytes[i++] = bval(bv); 199 } 200 for (byte bv : b456) { 201 fullBytes[i++] = bv; 202 } 203 long packedBytes = packedBytes(fullBytes); 204 if (packedBytes != 0) 205 return new Transform(packedBytes); 206 else 207 return new Transform(fullBytes); 208 } 209 210 Transform withResult(LambdaForm result) { 211 return new Transform(this.packedBytes, this.fullBytes, result); 212 } 213 214 @Override 215 public boolean equals(Object obj) { 216 return obj instanceof Transform && equals((Transform)obj); 217 } 218 public boolean equals(Transform that) { 219 return this.packedBytes == that.packedBytes && Arrays.equals(this.fullBytes, that.fullBytes); 220 } 221 @Override 222 public int hashCode() { 223 if (packedBytes != 0) { 224 assert(fullBytes == null); 225 return Long.hashCode(packedBytes); 226 } 227 return Arrays.hashCode(fullBytes); 228 } 229 @Override 230 public String toString() { 231 StringBuilder buf = new StringBuilder(); 232 long bits = packedBytes; 233 if (bits != 0) { 234 buf.append("("); 235 while (bits != 0) { 236 buf.append(bits & PACKED_BYTE_MASK); 237 bits >>>= PACKED_BYTE_SIZE; 238 if (bits != 0) buf.append(","); 239 } 240 buf.append(")"); 241 } 242 if (fullBytes != null) { 243 buf.append("unpacked"); 244 buf.append(Arrays.toString(fullBytes)); 245 } 246 if (result != null) { 247 buf.append(" result="); 248 buf.append(result); 249 } 250 return buf.toString(); 251 } 252 } 253 254 /** Find a previously cached transform equivalent to the given one, and return its result. */ 255 private LambdaForm getInCache(Transform key) { 256 assert(key.result == null); 257 // The transformCache is one of null, Transform, Transform[], or ConcurrentHashMap. 258 Object c = lambdaForm.transformCache; 259 Transform k = null; 260 if (c instanceof ConcurrentHashMap) { 261 @SuppressWarnings("unchecked") 262 ConcurrentHashMap<Transform,Transform> m = (ConcurrentHashMap<Transform,Transform>) c; 263 k = m.get(key); 264 } else if (c == null) { 265 return null; 266 } else if (c instanceof Transform) { 267 // one-element cache avoids overhead of an array 268 Transform t = (Transform)c; 269 if (t.equals(key)) k = t; 270 } else { 271 Transform[] ta = (Transform[])c; 272 for (int i = 0; i < ta.length; i++) { 273 Transform t = ta[i]; 274 if (t == null) break; 275 if (t.equals(key)) { k = t; break; } 276 } 277 } 278 assert(k == null || key.equals(k)); 279 return k == null ? null : k.result; 280 } 281 282 /** Arbitrary but reasonable limits on Transform[] size for cache. */ 283 private static final int MIN_CACHE_ARRAY_SIZE = 4, MAX_CACHE_ARRAY_SIZE = 16; 284 285 /** Cache a transform with its result, and return that result. 286 * But if an equivalent transform has already been cached, return its result instead. 287 */ 288 private LambdaForm putInCache(Transform key, LambdaForm form) { 289 key = key.withResult(form); 290 for (int pass = 0; ; pass++) { 291 Object c = lambdaForm.transformCache; 292 if (c instanceof ConcurrentHashMap) { 293 @SuppressWarnings("unchecked") 294 ConcurrentHashMap<Transform,Transform> m = (ConcurrentHashMap<Transform,Transform>) c; 295 Transform k = m.putIfAbsent(key, key); 296 return k != null ? k.result : form; 297 } 298 assert(pass == 0); 299 synchronized (lambdaForm) { 300 c = lambdaForm.transformCache; 301 if (c instanceof ConcurrentHashMap) 302 continue; 303 if (c == null) { 304 lambdaForm.transformCache = key; 305 return form; 306 } 307 Transform[] ta; 308 if (c instanceof Transform) { 309 Transform k = (Transform)c; 310 if (k.equals(key)) { 311 return k.result; 312 } 313 // expand one-element cache to small array 314 ta = new Transform[MIN_CACHE_ARRAY_SIZE]; 315 ta[0] = k; 316 lambdaForm.transformCache = c = ta; 317 } else { 318 // it is already expanded 319 ta = (Transform[])c; 320 } 321 int len = ta.length; 322 int i; 323 for (i = 0; i < len; i++) { 324 Transform k = ta[i]; 325 if (k == null) { 326 break; 327 } 328 if (k.equals(key)) { 329 return k.result; 330 } 331 } 332 if (i < len) { 333 // just fall through to cache update 334 } else if (len < MAX_CACHE_ARRAY_SIZE) { 335 len = Math.min(len * 2, MAX_CACHE_ARRAY_SIZE); 336 ta = Arrays.copyOf(ta, len); 337 lambdaForm.transformCache = ta; 338 } else { 339 ConcurrentHashMap<Transform, Transform> m = new ConcurrentHashMap<>(MAX_CACHE_ARRAY_SIZE * 2); 340 for (Transform k : ta) { 341 m.put(k, k); 342 } 343 lambdaForm.transformCache = m; 344 // The second iteration will update for this query, concurrently. 345 continue; 346 } 347 ta[i] = key; 348 return form; 349 } 350 } 351 } 352 353 private LambdaFormBuffer buffer() { 354 return new LambdaFormBuffer(lambdaForm); 355 } 356 357 /// Editing methods for method handles. These need to have fast paths. 358 359 private BoundMethodHandle.SpeciesData oldSpeciesData() { 360 return BoundMethodHandle.speciesData(lambdaForm); 361 } 362 private BoundMethodHandle.SpeciesData newSpeciesData(BasicType type) { 363 return oldSpeciesData().extendWith(type); 364 } 365 366 BoundMethodHandle bindArgumentL(BoundMethodHandle mh, int pos, Object value) { 367 assert(mh.speciesData() == oldSpeciesData()); 368 BasicType bt = L_TYPE; 369 MethodType type2 = bindArgumentType(mh, pos, bt); 370 LambdaForm form2 = bindArgumentForm(1+pos); 371 return mh.copyWithExtendL(type2, form2, value); 372 } 373 BoundMethodHandle bindArgumentI(BoundMethodHandle mh, int pos, int value) { 374 assert(mh.speciesData() == oldSpeciesData()); 375 BasicType bt = I_TYPE; 376 MethodType type2 = bindArgumentType(mh, pos, bt); 377 LambdaForm form2 = bindArgumentForm(1+pos); 378 return mh.copyWithExtendI(type2, form2, value); 379 } 380 381 BoundMethodHandle bindArgumentJ(BoundMethodHandle mh, int pos, long value) { 382 assert(mh.speciesData() == oldSpeciesData()); 383 BasicType bt = J_TYPE; 384 MethodType type2 = bindArgumentType(mh, pos, bt); 385 LambdaForm form2 = bindArgumentForm(1+pos); 386 return mh.copyWithExtendJ(type2, form2, value); 387 } 388 389 BoundMethodHandle bindArgumentF(BoundMethodHandle mh, int pos, float value) { 390 assert(mh.speciesData() == oldSpeciesData()); 391 BasicType bt = F_TYPE; 392 MethodType type2 = bindArgumentType(mh, pos, bt); 393 LambdaForm form2 = bindArgumentForm(1+pos); 394 return mh.copyWithExtendF(type2, form2, value); 395 } 396 397 BoundMethodHandle bindArgumentD(BoundMethodHandle mh, int pos, double value) { 398 assert(mh.speciesData() == oldSpeciesData()); 399 BasicType bt = D_TYPE; 400 MethodType type2 = bindArgumentType(mh, pos, bt); 401 LambdaForm form2 = bindArgumentForm(1+pos); 402 return mh.copyWithExtendD(type2, form2, value); 403 } 404 405 private MethodType bindArgumentType(BoundMethodHandle mh, int pos, BasicType bt) { 406 assert(mh.form == lambdaForm); 407 assert(mh.form.names[1+pos].type == bt); 408 assert(BasicType.basicType(mh.type().parameterType(pos)) == bt); 409 return mh.type().dropParameterTypes(pos, pos+1); 410 } 411 412 /// Editing methods for lambda forms. 413 // Each editing method can (potentially) cache the edited LF so that it can be reused later. 414 415 LambdaForm bindArgumentForm(int pos) { 416 Transform key = Transform.of(Transform.Kind.BIND_ARG, pos); 417 LambdaForm form = getInCache(key); 418 if (form != null) { 419 assert(form.parameterConstraint(0) == newSpeciesData(lambdaForm.parameterType(pos))); 420 return form; 421 } 422 LambdaFormBuffer buf = buffer(); 423 buf.startEdit(); 424 425 BoundMethodHandle.SpeciesData oldData = oldSpeciesData(); 426 BoundMethodHandle.SpeciesData newData = newSpeciesData(lambdaForm.parameterType(pos)); 427 Name oldBaseAddress = lambdaForm.parameter(0); // BMH holding the values 428 Name newBaseAddress; 429 NamedFunction getter = newData.getterFunction(oldData.fieldCount()); 430 431 if (pos != 0) { 432 // The newly created LF will run with a different BMH. 433 // Switch over any pre-existing BMH field references to the new BMH class. 434 buf.replaceFunctions(oldData.getterFunctions(), newData.getterFunctions(), oldBaseAddress); 435 newBaseAddress = oldBaseAddress.withConstraint(newData); 436 buf.renameParameter(0, newBaseAddress); 437 buf.replaceParameterByNewExpression(pos, new Name(getter, newBaseAddress)); 438 } else { 439 // cannot bind the MH arg itself, unless oldData is empty 440 assert(oldData == BoundMethodHandle.SpeciesData.EMPTY); 441 newBaseAddress = new Name(L_TYPE).withConstraint(newData); 442 buf.replaceParameterByNewExpression(0, new Name(getter, newBaseAddress)); 443 buf.insertParameter(0, newBaseAddress); 444 } 445 446 buf.endEdit(); 447 form = buf.lambdaForm(); 448 return putInCache(key, form); 449 } 450 }