1 /* 2 * Copyright (c) 2010, 2013, 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 package jdk.nashorn.internal.runtime; 26 27 import static jdk.nashorn.internal.lookup.Lookup.MH; 28 import static jdk.nashorn.internal.runtime.UnwarrantedOptimismException.INVALID_PROGRAM_POINT; 29 import static jdk.nashorn.internal.runtime.UnwarrantedOptimismException.isValid; 30 31 import java.lang.invoke.CallSite; 32 import java.lang.invoke.MethodHandle; 33 import java.lang.invoke.MethodHandles; 34 import java.lang.invoke.MethodType; 35 import java.lang.invoke.MutableCallSite; 36 import java.lang.invoke.SwitchPoint; 37 import java.util.ArrayList; 38 import java.util.Collection; 39 import java.util.Collections; 40 import java.util.Iterator; 41 import java.util.List; 42 import java.util.Map; 43 import java.util.TreeMap; 44 import java.util.function.Supplier; 45 import java.util.logging.Level; 46 import jdk.dynalink.linker.GuardedInvocation; 47 import jdk.nashorn.internal.codegen.Compiler; 48 import jdk.nashorn.internal.codegen.Compiler.CompilationPhases; 49 import jdk.nashorn.internal.codegen.TypeMap; 50 import jdk.nashorn.internal.codegen.types.ArrayType; 51 import jdk.nashorn.internal.codegen.types.Type; 52 import jdk.nashorn.internal.ir.FunctionNode; 53 import jdk.nashorn.internal.objects.annotations.SpecializedFunction.LinkLogic; 54 import jdk.nashorn.internal.runtime.events.RecompilationEvent; 55 import jdk.nashorn.internal.runtime.linker.Bootstrap; 56 import jdk.nashorn.internal.runtime.logging.DebugLogger; 57 58 /** 59 * An version of a JavaScript function, native or JavaScript. 60 * Supports lazily generating a constructor version of the invocation. 61 */ 62 final class CompiledFunction { 63 64 private static final MethodHandle NEWFILTER = findOwnMH("newFilter", Object.class, Object.class, Object.class); 65 private static final MethodHandle RELINK_COMPOSABLE_INVOKER = findOwnMH("relinkComposableInvoker", void.class, CallSite.class, CompiledFunction.class, boolean.class); 66 private static final MethodHandle HANDLE_REWRITE_EXCEPTION = findOwnMH("handleRewriteException", MethodHandle.class, CompiledFunction.class, OptimismInfo.class, RewriteException.class); 67 private static final MethodHandle RESTOF_INVOKER = MethodHandles.exactInvoker(MethodType.methodType(Object.class, RewriteException.class)); 68 69 private final DebugLogger log; 70 71 static final Collection<CompiledFunction> NO_FUNCTIONS = Collections.emptySet(); 72 73 /** 74 * The method type may be more specific than the invoker, if. e.g. 75 * the invoker is guarded, and a guard with a generic object only 76 * fallback, while the target is more specific, we still need the 77 * more specific type for sorting 78 */ 79 private MethodHandle invoker; 80 private MethodHandle constructor; 81 private OptimismInfo optimismInfo; 82 private final int flags; // from FunctionNode 83 private final MethodType callSiteType; 84 85 private final Specialization specialization; 86 CompiledFunction(final MethodHandle invoker)87 CompiledFunction(final MethodHandle invoker) { 88 this(invoker, null, null); 89 } 90 createBuiltInConstructor(final MethodHandle invoker, final Specialization specialization)91 static CompiledFunction createBuiltInConstructor(final MethodHandle invoker, final Specialization specialization) { 92 return new CompiledFunction(MH.insertArguments(invoker, 0, false), createConstructorFromInvoker(MH.insertArguments(invoker, 0, true)), specialization); 93 } 94 CompiledFunction(final MethodHandle invoker, final MethodHandle constructor, final Specialization specialization)95 CompiledFunction(final MethodHandle invoker, final MethodHandle constructor, final Specialization specialization) { 96 this(invoker, constructor, 0, null, specialization, DebugLogger.DISABLED_LOGGER); 97 } 98 CompiledFunction(final MethodHandle invoker, final MethodHandle constructor, final int flags, final MethodType callSiteType, final Specialization specialization, final DebugLogger log)99 CompiledFunction(final MethodHandle invoker, final MethodHandle constructor, final int flags, final MethodType callSiteType, final Specialization specialization, final DebugLogger log) { 100 this.specialization = specialization; 101 if (specialization != null && specialization.isOptimistic()) { 102 /* 103 * An optimistic builtin with isOptimistic=true works like any optimistic generated function, i.e. it 104 * can throw unwarranted optimism exceptions. As native functions trivially can't have parts of them 105 * regenerated as "restOf" methods, this only works if the methods are atomic/functional in their behavior 106 * and doesn't modify state before an UOE can be thrown. If they aren't, we can reexecute a wider version 107 * of the same builtin in a recompilation handler for FinalScriptFunctionData. There are several 108 * candidate methods in Native* that would benefit from this, but I haven't had time to implement any 109 * of them currently. In order to fit in with the relinking framework, the current thinking is 110 * that the methods still take a program point to fit in with other optimistic functions, but 111 * it is set to "first", which is the beginning of the method. The relinker can tell the difference 112 * between builtin and JavaScript functions. This might change. TODO 113 */ 114 this.invoker = MH.insertArguments(invoker, invoker.type().parameterCount() - 1, UnwarrantedOptimismException.FIRST_PROGRAM_POINT); 115 throw new AssertionError("Optimistic (UnwarrantedOptimismException throwing) builtin functions are currently not in use"); 116 } 117 this.invoker = invoker; 118 this.constructor = constructor; 119 this.flags = flags; 120 this.callSiteType = callSiteType; 121 this.log = log; 122 } 123 CompiledFunction(final MethodHandle invoker, final RecompilableScriptFunctionData functionData, final Map<Integer, Type> invalidatedProgramPoints, final MethodType callSiteType, final int flags)124 CompiledFunction(final MethodHandle invoker, final RecompilableScriptFunctionData functionData, 125 final Map<Integer, Type> invalidatedProgramPoints, final MethodType callSiteType, final int flags) { 126 this(invoker, null, flags, callSiteType, null, functionData.getLogger()); 127 if ((flags & FunctionNode.IS_DEOPTIMIZABLE) != 0) { 128 optimismInfo = new OptimismInfo(functionData, invalidatedProgramPoints); 129 } else { 130 optimismInfo = null; 131 } 132 } 133 createBuiltInConstructor(final MethodHandle invoker)134 static CompiledFunction createBuiltInConstructor(final MethodHandle invoker) { 135 return new CompiledFunction(MH.insertArguments(invoker, 0, false), createConstructorFromInvoker(MH.insertArguments(invoker, 0, true)), null); 136 } 137 isSpecialization()138 boolean isSpecialization() { 139 return specialization != null; 140 } 141 hasLinkLogic()142 boolean hasLinkLogic() { 143 return getLinkLogicClass() != null; 144 } 145 getLinkLogicClass()146 Class<? extends LinkLogic> getLinkLogicClass() { 147 if (isSpecialization()) { 148 final Class<? extends LinkLogic> linkLogicClass = specialization.getLinkLogicClass(); 149 assert !LinkLogic.isEmpty(linkLogicClass) : "empty link logic classes should have been removed by nasgen"; 150 return linkLogicClass; 151 } 152 return null; 153 } 154 convertsNumericArgs()155 boolean convertsNumericArgs() { 156 return isSpecialization() && specialization.convertsNumericArgs(); 157 } 158 getFlags()159 int getFlags() { 160 return flags; 161 } 162 163 /** 164 * An optimistic specialization is one that can throw UnwarrantedOptimismException. 165 * This is allowed for native methods, as long as they are functional, i.e. don't change 166 * any state between entering and throwing the UOE. Then we can re-execute a wider version 167 * of the method in the continuation. Rest-of method generation for optimistic builtins is 168 * of course not possible, but this approach works and fits into the same relinking 169 * framework 170 * 171 * @return true if optimistic builtin 172 */ isOptimistic()173 boolean isOptimistic() { 174 return isSpecialization() ? specialization.isOptimistic() : false; 175 } 176 isApplyToCall()177 boolean isApplyToCall() { 178 return (flags & FunctionNode.HAS_APPLY_TO_CALL_SPECIALIZATION) != 0; 179 } 180 isVarArg()181 boolean isVarArg() { 182 return isVarArgsType(invoker.type()); 183 } 184 185 @Override toString()186 public String toString() { 187 final StringBuilder sb = new StringBuilder(); 188 final Class<? extends LinkLogic> linkLogicClass = getLinkLogicClass(); 189 190 sb.append("[invokerType="). 191 append(invoker.type()). 192 append(" ctor="). 193 append(constructor). 194 append(" weight="). 195 append(weight()). 196 append(" linkLogic="). 197 append(linkLogicClass != null ? linkLogicClass.getSimpleName() : "none"); 198 199 return sb.toString(); 200 } 201 needsCallee()202 boolean needsCallee() { 203 return ScriptFunctionData.needsCallee(invoker); 204 } 205 206 /** 207 * Returns an invoker method handle for this function. Note that the handle is safely composable in 208 * the sense that you can compose it with other handles using any combinators even if you can't affect call site 209 * invalidation. If this compiled function is non-optimistic, then it returns the same value as 210 * {@link #getInvokerOrConstructor(boolean)}. However, if the function is optimistic, then this handle will 211 * incur an overhead as it will add an intermediate internal call site that can relink itself when the function 212 * needs to regenerate its code to always point at the latest generated code version. 213 * @return a guaranteed composable invoker method handle for this function. 214 */ createComposableInvoker()215 MethodHandle createComposableInvoker() { 216 return createComposableInvoker(false); 217 } 218 219 /** 220 * Returns an invoker method handle for this function when invoked as a constructor. Note that the handle should be 221 * considered non-composable in the sense that you can only compose it with other handles using any combinators if 222 * you can ensure that the composition is guarded by {@link #getOptimisticAssumptionsSwitchPoint()} if it's 223 * non-null, and that you can relink the call site it is set into as a target if the switch point is invalidated. In 224 * all other cases, use {@link #createComposableConstructor()}. 225 * @return a direct constructor method handle for this function. 226 */ getConstructor()227 private MethodHandle getConstructor() { 228 if (constructor == null) { 229 constructor = createConstructorFromInvoker(createInvokerForPessimisticCaller()); 230 } 231 232 return constructor; 233 } 234 235 /** 236 * Creates a version of the invoker intended for a pessimistic caller (return type is Object, no caller optimistic 237 * program point available). 238 * @return a version of the invoker intended for a pessimistic caller. 239 */ createInvokerForPessimisticCaller()240 private MethodHandle createInvokerForPessimisticCaller() { 241 return createInvoker(Object.class, INVALID_PROGRAM_POINT); 242 } 243 244 /** 245 * Compose a constructor from an invoker. 246 * 247 * @param invoker invoker 248 * @return the composed constructor 249 */ createConstructorFromInvoker(final MethodHandle invoker)250 private static MethodHandle createConstructorFromInvoker(final MethodHandle invoker) { 251 final boolean needsCallee = ScriptFunctionData.needsCallee(invoker); 252 // If it was (callee, this, args...), permute it to (this, callee, args...). We're doing this because having 253 // "this" in the first argument position is what allows the elegant folded composition of 254 // (newFilter x constructor x allocator) further down below in the code. Also, ensure the composite constructor 255 // always returns Object. 256 final MethodHandle swapped = needsCallee ? swapCalleeAndThis(invoker) : invoker; 257 258 final MethodHandle returnsObject = MH.asType(swapped, swapped.type().changeReturnType(Object.class)); 259 260 final MethodType ctorType = returnsObject.type(); 261 262 // Construct a dropping type list for NEWFILTER, but don't include constructor "this" into it, so it's actually 263 // captured as "allocation" parameter of NEWFILTER after we fold the constructor into it. 264 // (this, [callee, ]args...) => ([callee, ]args...) 265 final Class<?>[] ctorArgs = ctorType.dropParameterTypes(0, 1).parameterArray(); 266 267 // Fold constructor into newFilter that replaces the return value from the constructor with the originally 268 // allocated value when the originally allocated value is a JS primitive (String, Boolean, Number). 269 // (result, this, [callee, ]args...) x (this, [callee, ]args...) => (this, [callee, ]args...) 270 final MethodHandle filtered = MH.foldArguments(MH.dropArguments(NEWFILTER, 2, ctorArgs), returnsObject); 271 272 // allocate() takes a ScriptFunction and returns a newly allocated ScriptObject... 273 if (needsCallee) { 274 // ...we either fold it into the previous composition, if we need both the ScriptFunction callee object and 275 // the newly allocated object in the arguments, so (this, callee, args...) x (callee) => (callee, args...), 276 // or... 277 return MH.foldArguments(filtered, ScriptFunction.ALLOCATE); 278 } 279 280 // ...replace the ScriptFunction argument with the newly allocated object, if it doesn't need the callee 281 // (this, args...) filter (callee) => (callee, args...) 282 return MH.filterArguments(filtered, 0, ScriptFunction.ALLOCATE); 283 } 284 285 /** 286 * Permutes the parameters in the method handle from {@code (callee, this, ...)} to {@code (this, callee, ...)}. 287 * Used when creating a constructor handle. 288 * @param mh a method handle with order of arguments {@code (callee, this, ...)} 289 * @return a method handle with order of arguments {@code (this, callee, ...)} 290 */ swapCalleeAndThis(final MethodHandle mh)291 private static MethodHandle swapCalleeAndThis(final MethodHandle mh) { 292 final MethodType type = mh.type(); 293 assert type.parameterType(0) == ScriptFunction.class : type; 294 assert type.parameterType(1) == Object.class : type; 295 final MethodType newType = type.changeParameterType(0, Object.class).changeParameterType(1, ScriptFunction.class); 296 final int[] reorder = new int[type.parameterCount()]; 297 reorder[0] = 1; 298 assert reorder[1] == 0; 299 for (int i = 2; i < reorder.length; ++i) { 300 reorder[i] = i; 301 } 302 return MethodHandles.permuteArguments(mh, newType, reorder); 303 } 304 305 /** 306 * Returns an invoker method handle for this function when invoked as a constructor. Note that the handle is safely 307 * composable in the sense that you can compose it with other handles using any combinators even if you can't affect 308 * call site invalidation. If this compiled function is non-optimistic, then it returns the same value as 309 * {@link #getConstructor()}. However, if the function is optimistic, then this handle will incur an overhead as it 310 * will add an intermediate internal call site that can relink itself when the function needs to regenerate its code 311 * to always point at the latest generated code version. 312 * @return a guaranteed composable constructor method handle for this function. 313 */ createComposableConstructor()314 MethodHandle createComposableConstructor() { 315 return createComposableInvoker(true); 316 } 317 hasConstructor()318 boolean hasConstructor() { 319 return constructor != null; 320 } 321 type()322 MethodType type() { 323 return invoker.type(); 324 } 325 weight()326 int weight() { 327 return weight(type()); 328 } 329 weight(final MethodType type)330 private static int weight(final MethodType type) { 331 if (isVarArgsType(type)) { 332 return Integer.MAX_VALUE; //if there is a varargs it should be the heavist and last fallback 333 } 334 335 int weight = Type.typeFor(type.returnType()).getWeight(); 336 for (int i = 0 ; i < type.parameterCount() ; i++) { 337 final Class<?> paramType = type.parameterType(i); 338 final int pweight = Type.typeFor(paramType).getWeight() * 2; //params are more important than call types as return values are always specialized 339 weight += pweight; 340 } 341 342 weight += type.parameterCount(); //more params outweigh few parameters 343 344 return weight; 345 } 346 isVarArgsType(final MethodType type)347 static boolean isVarArgsType(final MethodType type) { 348 assert type.parameterCount() >= 1 : type; 349 return type.parameterType(type.parameterCount() - 1) == Object[].class; 350 } 351 moreGenericThan(final MethodType mt0, final MethodType mt1)352 static boolean moreGenericThan(final MethodType mt0, final MethodType mt1) { 353 return weight(mt0) > weight(mt1); 354 } 355 betterThanFinal(final CompiledFunction other, final MethodType callSiteMethodType)356 boolean betterThanFinal(final CompiledFunction other, final MethodType callSiteMethodType) { 357 // Prefer anything over nothing, as we can't compile new versions. 358 if (other == null) { 359 return true; 360 } 361 return betterThanFinal(this, other, callSiteMethodType); 362 } 363 betterThanFinal(final CompiledFunction cf, final CompiledFunction other, final MethodType callSiteMethodType)364 private static boolean betterThanFinal(final CompiledFunction cf, final CompiledFunction other, final MethodType callSiteMethodType) { 365 final MethodType thisMethodType = cf.type(); 366 final MethodType otherMethodType = other.type(); 367 final int thisParamCount = getParamCount(thisMethodType); 368 final int otherParamCount = getParamCount(otherMethodType); 369 final int callSiteRawParamCount = getParamCount(callSiteMethodType); 370 final boolean csVarArg = callSiteRawParamCount == Integer.MAX_VALUE; 371 // Subtract 1 for callee for non-vararg call sites 372 final int callSiteParamCount = csVarArg ? callSiteRawParamCount : callSiteRawParamCount - 1; 373 374 // Prefer the function that discards less parameters 375 final int thisDiscardsParams = Math.max(callSiteParamCount - thisParamCount, 0); 376 final int otherDiscardsParams = Math.max(callSiteParamCount - otherParamCount, 0); 377 if(thisDiscardsParams < otherDiscardsParams) { 378 return true; 379 } 380 if(thisDiscardsParams > otherDiscardsParams) { 381 return false; 382 } 383 384 final boolean thisVarArg = thisParamCount == Integer.MAX_VALUE; 385 final boolean otherVarArg = otherParamCount == Integer.MAX_VALUE; 386 if(!(thisVarArg && otherVarArg && csVarArg)) { 387 // At least one of them isn't vararg 388 final Type[] thisType = toTypeWithoutCallee(thisMethodType, 0); // Never has callee 389 final Type[] otherType = toTypeWithoutCallee(otherMethodType, 0); // Never has callee 390 final Type[] callSiteType = toTypeWithoutCallee(callSiteMethodType, 1); // Always has callee 391 392 int narrowWeightDelta = 0; 393 int widenWeightDelta = 0; 394 final int minParamsCount = Math.min(Math.min(thisParamCount, otherParamCount), callSiteParamCount); 395 final boolean convertsNumericArgs = cf.convertsNumericArgs(); 396 for(int i = 0; i < minParamsCount; ++i) { 397 final Type callSiteParamType = getParamType(i, callSiteType, csVarArg); 398 final Type thisParamType = getParamType(i, thisType, thisVarArg); 399 if (!convertsNumericArgs && callSiteParamType.isBoolean() && thisParamType.isNumeric()) { 400 // When an argument is converted to number by a function it is safe to "widen" booleans to numeric types. 401 // However, we must avoid this conversion for generic functions such as Array.prototype.push. 402 return false; 403 } 404 final int callSiteParamWeight = callSiteParamType.getWeight(); 405 // Delta is negative for narrowing, positive for widening 406 final int thisParamWeightDelta = thisParamType.getWeight() - callSiteParamWeight; 407 final int otherParamWeightDelta = getParamType(i, otherType, otherVarArg).getWeight() - callSiteParamWeight; 408 // Only count absolute values of narrowings 409 narrowWeightDelta += Math.max(-thisParamWeightDelta, 0) - Math.max(-otherParamWeightDelta, 0); 410 // Only count absolute values of widenings 411 widenWeightDelta += Math.max(thisParamWeightDelta, 0) - Math.max(otherParamWeightDelta, 0); 412 } 413 414 // If both functions accept more arguments than what is passed at the call site, account for ability 415 // to receive Undefined un-narrowed in the remaining arguments. 416 if(!thisVarArg) { 417 for(int i = callSiteParamCount; i < thisParamCount; ++i) { 418 narrowWeightDelta += Math.max(Type.OBJECT.getWeight() - thisType[i].getWeight(), 0); 419 } 420 } 421 if(!otherVarArg) { 422 for(int i = callSiteParamCount; i < otherParamCount; ++i) { 423 narrowWeightDelta -= Math.max(Type.OBJECT.getWeight() - otherType[i].getWeight(), 0); 424 } 425 } 426 427 // Prefer function that narrows less 428 if(narrowWeightDelta < 0) { 429 return true; 430 } 431 if(narrowWeightDelta > 0) { 432 return false; 433 } 434 435 // Prefer function that widens less 436 if(widenWeightDelta < 0) { 437 return true; 438 } 439 if(widenWeightDelta > 0) { 440 return false; 441 } 442 } 443 444 // Prefer the function that exactly matches the arity of the call site. 445 if(thisParamCount == callSiteParamCount && otherParamCount != callSiteParamCount) { 446 return true; 447 } 448 if(thisParamCount != callSiteParamCount && otherParamCount == callSiteParamCount) { 449 return false; 450 } 451 452 // Otherwise, neither function matches arity exactly. We also know that at this point, they both can receive 453 // more arguments than call site, otherwise we would've already chosen the one that discards less parameters. 454 // Note that variable arity methods are preferred, as they actually match the call site arity better, since they 455 // really have arbitrary arity. 456 if(thisVarArg) { 457 if(!otherVarArg) { 458 return true; // 459 } 460 } else if(otherVarArg) { 461 return false; 462 } 463 464 // Neither is variable arity; chose the one that has less extra parameters. 465 final int fnParamDelta = thisParamCount - otherParamCount; 466 if(fnParamDelta < 0) { 467 return true; 468 } 469 if(fnParamDelta > 0) { 470 return false; 471 } 472 473 final int callSiteRetWeight = Type.typeFor(callSiteMethodType.returnType()).getWeight(); 474 // Delta is negative for narrower return type, positive for wider return type 475 final int thisRetWeightDelta = Type.typeFor(thisMethodType.returnType()).getWeight() - callSiteRetWeight; 476 final int otherRetWeightDelta = Type.typeFor(otherMethodType.returnType()).getWeight() - callSiteRetWeight; 477 478 // Prefer function that returns a less wide return type 479 final int widenRetDelta = Math.max(thisRetWeightDelta, 0) - Math.max(otherRetWeightDelta, 0); 480 if(widenRetDelta < 0) { 481 return true; 482 } 483 if(widenRetDelta > 0) { 484 return false; 485 } 486 487 // Prefer function that returns a less narrow return type 488 final int narrowRetDelta = Math.max(-thisRetWeightDelta, 0) - Math.max(-otherRetWeightDelta, 0); 489 if(narrowRetDelta < 0) { 490 return true; 491 } 492 if(narrowRetDelta > 0) { 493 return false; 494 } 495 496 //if they are equal, pick the specialized one first 497 if (cf.isSpecialization() != other.isSpecialization()) { 498 return cf.isSpecialization(); //always pick the specialized version if we can 499 } 500 501 if (cf.isSpecialization() && other.isSpecialization()) { 502 return cf.getLinkLogicClass() != null; //pick link logic specialization above generic specializations 503 } 504 505 // Signatures are identical 506 throw new AssertionError(thisMethodType + " identically applicable to " + otherMethodType + " for " + callSiteMethodType); 507 } 508 toTypeWithoutCallee(final MethodType type, final int thisIndex)509 private static Type[] toTypeWithoutCallee(final MethodType type, final int thisIndex) { 510 final int paramCount = type.parameterCount(); 511 final Type[] t = new Type[paramCount - thisIndex]; 512 for(int i = thisIndex; i < paramCount; ++i) { 513 t[i - thisIndex] = Type.typeFor(type.parameterType(i)); 514 } 515 return t; 516 } 517 getParamType(final int i, final Type[] paramTypes, final boolean isVarArg)518 private static Type getParamType(final int i, final Type[] paramTypes, final boolean isVarArg) { 519 final int fixParamCount = paramTypes.length - (isVarArg ? 1 : 0); 520 if(i < fixParamCount) { 521 return paramTypes[i]; 522 } 523 assert isVarArg; 524 return ((ArrayType)paramTypes[paramTypes.length - 1]).getElementType(); 525 } 526 matchesCallSite(final MethodType other, final boolean pickVarArg)527 boolean matchesCallSite(final MethodType other, final boolean pickVarArg) { 528 if (other.equals(this.callSiteType)) { 529 return true; 530 } 531 final MethodType type = type(); 532 final int fnParamCount = getParamCount(type); 533 final boolean isVarArg = fnParamCount == Integer.MAX_VALUE; 534 if (isVarArg) { 535 return pickVarArg; 536 } 537 538 final int csParamCount = getParamCount(other); 539 final boolean csIsVarArg = csParamCount == Integer.MAX_VALUE; 540 if (csIsVarArg && isApplyToCall()) { 541 return false; // apply2call function must be called with exact number of parameters 542 } 543 final int thisThisIndex = needsCallee() ? 1 : 0; // Index of "this" parameter in this function's type 544 545 final int fnParamCountNoCallee = fnParamCount - thisThisIndex; 546 final int minParams = Math.min(csParamCount - 1, fnParamCountNoCallee); // callSiteType always has callee, so subtract 1 547 // We must match all incoming parameters, including "this". "this" will usually be Object, but there 548 // are exceptions, e.g. when calling functions with primitive "this" in strict mode or through call/apply. 549 for(int i = 0; i < minParams; ++i) { 550 final Type fnType = Type.typeFor(type.parameterType(i + thisThisIndex)); 551 final Type csType = csIsVarArg ? Type.OBJECT : Type.typeFor(other.parameterType(i + 1)); 552 if(!fnType.isEquivalentTo(csType)) { 553 return false; 554 } 555 } 556 557 // Must match any undefined parameters to Object type. 558 for(int i = minParams; i < fnParamCountNoCallee; ++i) { 559 if(!Type.typeFor(type.parameterType(i + thisThisIndex)).isEquivalentTo(Type.OBJECT)) { 560 return false; 561 } 562 } 563 564 return true; 565 } 566 getParamCount(final MethodType type)567 private static int getParamCount(final MethodType type) { 568 final int paramCount = type.parameterCount(); 569 return type.parameterType(paramCount - 1).isArray() ? Integer.MAX_VALUE : paramCount; 570 } 571 canBeDeoptimized()572 private boolean canBeDeoptimized() { 573 return optimismInfo != null; 574 } 575 createComposableInvoker(final boolean isConstructor)576 private MethodHandle createComposableInvoker(final boolean isConstructor) { 577 final MethodHandle handle = getInvokerOrConstructor(isConstructor); 578 579 // If compiled function is not optimistic, it can't ever change its invoker/constructor, so just return them 580 // directly. 581 if(!canBeDeoptimized()) { 582 return handle; 583 } 584 585 // Otherwise, we need a new level of indirection; need to introduce a mutable call site that can relink itself 586 // to the compiled function's changed target whenever the optimistic assumptions are invalidated. 587 final CallSite cs = new MutableCallSite(handle.type()); 588 relinkComposableInvoker(cs, this, isConstructor); 589 return cs.dynamicInvoker(); 590 } 591 592 private static class HandleAndAssumptions { 593 final MethodHandle handle; 594 final SwitchPoint assumptions; 595 HandleAndAssumptions(final MethodHandle handle, final SwitchPoint assumptions)596 HandleAndAssumptions(final MethodHandle handle, final SwitchPoint assumptions) { 597 this.handle = handle; 598 this.assumptions = assumptions; 599 } 600 createInvocation()601 GuardedInvocation createInvocation() { 602 return new GuardedInvocation(handle, assumptions); 603 } 604 } 605 606 /** 607 * Returns a pair of an invocation created with a passed-in supplier and a non-invalidated switch point for 608 * optimistic assumptions (or null for the switch point if the function can not be deoptimized). While the method 609 * makes a best effort to return a non-invalidated switch point (compensating for possible deoptimizing 610 * recompilation happening on another thread) it is still possible that by the time this method returns the 611 * switchpoint has been invalidated by a {@code RewriteException} triggered on another thread for this function. 612 * This is not a problem, though, as these switch points are always used to produce call sites that fall back to 613 * relinking when they are invalidated, and in this case the execution will end up here again. What this method 614 * basically does is minimize such busy-loop relinking while the function is being recompiled on a different thread. 615 * @param invocationSupplier the supplier that constructs the actual invocation method handle; should use the 616 * {@code CompiledFunction} method itself in some capacity. 617 * @return a tuple object containing the method handle as created by the supplier and an optimistic assumptions 618 * switch point that is guaranteed to not have been invalidated before the call to this method (or null if the 619 * function can't be further deoptimized). 620 */ getValidOptimisticInvocation(final Supplier<MethodHandle> invocationSupplier)621 private synchronized HandleAndAssumptions getValidOptimisticInvocation(final Supplier<MethodHandle> invocationSupplier) { 622 for(;;) { 623 final MethodHandle handle = invocationSupplier.get(); 624 final SwitchPoint assumptions = canBeDeoptimized() ? optimismInfo.optimisticAssumptions : null; 625 if(assumptions != null && assumptions.hasBeenInvalidated()) { 626 // We can be in a situation where one thread is in the middle of a deoptimizing compilation when we hit 627 // this and thus, it has invalidated the old switch point, but hasn't created the new one yet. Note that 628 // the behavior of invalidating the old switch point before recompilation, and only creating the new one 629 // after recompilation is by design. If we didn't wait here for the recompilation to complete, we would 630 // be busy looping through the fallback path of the invalidated switch point, relinking the call site 631 // again with the same invalidated switch point, invoking the fallback, etc. stealing CPU cycles from 632 // the recompilation task we're dependent on. This can still happen if the switch point gets invalidated 633 // after we grabbed it here, in which case we'll indeed do one busy relink immediately. 634 try { 635 wait(); 636 } catch (final InterruptedException e) { 637 // Intentionally ignored. There's nothing meaningful we can do if we're interrupted 638 } 639 } else { 640 return new HandleAndAssumptions(handle, assumptions); 641 } 642 } 643 } 644 relinkComposableInvoker(final CallSite cs, final CompiledFunction inv, final boolean constructor)645 private static void relinkComposableInvoker(final CallSite cs, final CompiledFunction inv, final boolean constructor) { 646 final HandleAndAssumptions handleAndAssumptions = inv.getValidOptimisticInvocation(new Supplier<MethodHandle>() { 647 @Override 648 public MethodHandle get() { 649 return inv.getInvokerOrConstructor(constructor); 650 } 651 }); 652 final MethodHandle handle = handleAndAssumptions.handle; 653 final SwitchPoint assumptions = handleAndAssumptions.assumptions; 654 final MethodHandle target; 655 if(assumptions == null) { 656 target = handle; 657 } else { 658 final MethodHandle relink = MethodHandles.insertArguments(RELINK_COMPOSABLE_INVOKER, 0, cs, inv, constructor); 659 target = assumptions.guardWithTest(handle, MethodHandles.foldArguments(cs.dynamicInvoker(), relink)); 660 } 661 cs.setTarget(target.asType(cs.type())); 662 } 663 getInvokerOrConstructor(final boolean selectCtor)664 private MethodHandle getInvokerOrConstructor(final boolean selectCtor) { 665 return selectCtor ? getConstructor() : createInvokerForPessimisticCaller(); 666 } 667 668 /** 669 * Returns a guarded invocation for this function when not invoked as a constructor. The guarded invocation has no 670 * guard but it potentially has an optimistic assumptions switch point. As such, it will probably not be used as a 671 * final guarded invocation, but rather as a holder for an invocation handle and switch point to be decomposed and 672 * reassembled into a different final invocation by the user of this method. Any recompositions should take care to 673 * continue to use the switch point. If that is not possible, use {@link #createComposableInvoker()} instead. 674 * @return a guarded invocation for an ordinary (non-constructor) invocation of this function. 675 */ createFunctionInvocation(final Class<?> callSiteReturnType, final int callerProgramPoint)676 GuardedInvocation createFunctionInvocation(final Class<?> callSiteReturnType, final int callerProgramPoint) { 677 return getValidOptimisticInvocation(new Supplier<MethodHandle>() { 678 @Override 679 public MethodHandle get() { 680 return createInvoker(callSiteReturnType, callerProgramPoint); 681 } 682 }).createInvocation(); 683 } 684 685 /** 686 * Returns a guarded invocation for this function when invoked as a constructor. The guarded invocation has no guard 687 * but it potentially has an optimistic assumptions switch point. As such, it will probably not be used as a final 688 * guarded invocation, but rather as a holder for an invocation handle and switch point to be decomposed and 689 * reassembled into a different final invocation by the user of this method. Any recompositions should take care to 690 * continue to use the switch point. If that is not possible, use {@link #createComposableConstructor()} instead. 691 * @return a guarded invocation for invocation of this function as a constructor. 692 */ 693 GuardedInvocation createConstructorInvocation() { 694 return getValidOptimisticInvocation(new Supplier<MethodHandle>() { 695 @Override 696 public MethodHandle get() { 697 return getConstructor(); 698 } 699 }).createInvocation(); 700 } 701 702 private MethodHandle createInvoker(final Class<?> callSiteReturnType, final int callerProgramPoint) { 703 final boolean isOptimistic = canBeDeoptimized(); 704 MethodHandle handleRewriteException = isOptimistic ? createRewriteExceptionHandler() : null; 705 706 MethodHandle inv = invoker; 707 if(isValid(callerProgramPoint)) { 708 inv = OptimisticReturnFilters.filterOptimisticReturnValue(inv, callSiteReturnType, callerProgramPoint); 709 inv = changeReturnType(inv, callSiteReturnType); 710 if(callSiteReturnType.isPrimitive() && handleRewriteException != null) { 711 // because handleRewriteException always returns Object 712 handleRewriteException = OptimisticReturnFilters.filterOptimisticReturnValue(handleRewriteException, 713 callSiteReturnType, callerProgramPoint); 714 } 715 } else if(isOptimistic) { 716 // Required so that rewrite exception has the same return type. It'd be okay to do it even if we weren't 717 // optimistic, but it isn't necessary as the linker upstream will eventually convert the return type. 718 inv = changeReturnType(inv, callSiteReturnType); 719 } 720 721 if(isOptimistic) { 722 assert handleRewriteException != null; 723 final MethodHandle typedHandleRewriteException = changeReturnType(handleRewriteException, inv.type().returnType()); 724 return MH.catchException(inv, RewriteException.class, typedHandleRewriteException); 725 } 726 return inv; 727 } 728 729 private MethodHandle createRewriteExceptionHandler() { 730 return MH.foldArguments(RESTOF_INVOKER, MH.insertArguments(HANDLE_REWRITE_EXCEPTION, 0, this, optimismInfo)); 731 } 732 733 private static MethodHandle changeReturnType(final MethodHandle mh, final Class<?> newReturnType) { 734 return Bootstrap.getLinkerServices().asType(mh, mh.type().changeReturnType(newReturnType)); 735 } 736 737 @SuppressWarnings("unused") 738 private static MethodHandle handleRewriteException(final CompiledFunction function, final OptimismInfo oldOptimismInfo, final RewriteException re) { 739 return function.handleRewriteException(oldOptimismInfo, re); 740 } 741 742 /** 743 * Debug function for printing out all invalidated program points and their 744 * invalidation mapping to next type 745 * @param ipp 746 * @return string describing the ipp map 747 */ 748 private static List<String> toStringInvalidations(final Map<Integer, Type> ipp) { 749 if (ipp == null) { 750 return Collections.emptyList(); 751 } 752 753 final List<String> list = new ArrayList<>(); 754 755 for (final Iterator<Map.Entry<Integer, Type>> iter = ipp.entrySet().iterator(); iter.hasNext(); ) { 756 final Map.Entry<Integer, Type> entry = iter.next(); 757 final char bct = entry.getValue().getBytecodeStackType(); 758 final String type; 759 760 switch (entry.getValue().getBytecodeStackType()) { 761 case 'A': 762 type = "object"; 763 break; 764 case 'I': 765 type = "int"; 766 break; 767 case 'J': 768 type = "long"; 769 break; 770 case 'D': 771 type = "double"; 772 break; 773 default: 774 type = String.valueOf(bct); 775 break; 776 } 777 778 final StringBuilder sb = new StringBuilder(); 779 sb.append('['). 780 append("program point: "). 781 append(entry.getKey()). 782 append(" -> "). 783 append(type). 784 append(']'); 785 786 list.add(sb.toString()); 787 } 788 789 return list; 790 } 791 792 private void logRecompile(final String reason, final FunctionNode fn, final MethodType type, final Map<Integer, Type> ipp) { 793 if (log.isEnabled()) { 794 log.info(reason, DebugLogger.quote(fn.getName()), " signature: ", type); 795 log.indent(); 796 for (final String str : toStringInvalidations(ipp)) { 797 log.fine(str); 798 } 799 log.unindent(); 800 } 801 } 802 803 /** 804 * Handles a {@link RewriteException} raised during the execution of this function by recompiling (if needed) the 805 * function with an optimistic assumption invalidated at the program point indicated by the exception, and then 806 * executing a rest-of method to complete the execution with the deoptimized version. 807 * @param oldOptInfo the optimism info of this function. We must store it explicitly as a bound argument in the 808 * method handle, otherwise it could be null for handling a rewrite exception in an outer invocation of a recursive 809 * function when recursive invocations of the function have completely deoptimized it. 810 * @param re the rewrite exception that was raised 811 * @return the method handle for the rest-of method, for folding composition. 812 */ 813 private synchronized MethodHandle handleRewriteException(final OptimismInfo oldOptInfo, final RewriteException re) { 814 if (log.isEnabled()) { 815 log.info( 816 new RecompilationEvent( 817 Level.INFO, 818 re, 819 re.getReturnValueNonDestructive()), 820 "caught RewriteException ", 821 re.getMessageShort()); 822 log.indent(); 823 } 824 825 final MethodType type = type(); 826 827 // Compiler needs a call site type as its input, which always has a callee parameter, so we must add it if 828 // this function doesn't have a callee parameter. 829 final MethodType ct = type.parameterType(0) == ScriptFunction.class ? 830 type : 831 type.insertParameterTypes(0, ScriptFunction.class); 832 final OptimismInfo currentOptInfo = optimismInfo; 833 final boolean shouldRecompile = currentOptInfo != null && currentOptInfo.requestRecompile(re); 834 835 // Effective optimism info, for subsequent use. We'll normally try to use the current (latest) one, but if it 836 // isn't available, we'll use the old one bound into the call site. 837 final OptimismInfo effectiveOptInfo = currentOptInfo != null ? currentOptInfo : oldOptInfo; 838 FunctionNode fn = effectiveOptInfo.reparse(); 839 final boolean cached = fn.isCached(); 840 final Compiler compiler = effectiveOptInfo.getCompiler(fn, ct, re); //set to non rest-of 841 842 if (!shouldRecompile) { 843 // It didn't necessarily recompile, e.g. for an outer invocation of a recursive function if we already 844 // recompiled a deoptimized version for an inner invocation. 845 // We still need to do the rest of from the beginning 846 logRecompile("Rest-of compilation [STANDALONE] ", fn, ct, effectiveOptInfo.invalidatedProgramPoints); 847 return restOfHandle(effectiveOptInfo, compiler.compile(fn, cached ? CompilationPhases.COMPILE_CACHED_RESTOF : CompilationPhases.COMPILE_ALL_RESTOF), currentOptInfo != null); 848 } 849 850 logRecompile("Deoptimizing recompilation (up to bytecode) ", fn, ct, effectiveOptInfo.invalidatedProgramPoints); 851 fn = compiler.compile(fn, cached ? CompilationPhases.RECOMPILE_CACHED_UPTO_BYTECODE : CompilationPhases.COMPILE_UPTO_BYTECODE); 852 log.fine("Reusable IR generated"); 853 854 // compile the rest of the function, and install it 855 log.info("Generating and installing bytecode from reusable IR..."); 856 logRecompile("Rest-of compilation [CODE PIPELINE REUSE] ", fn, ct, effectiveOptInfo.invalidatedProgramPoints); 857 final FunctionNode normalFn = compiler.compile(fn, CompilationPhases.GENERATE_BYTECODE_AND_INSTALL); 858 859 if (effectiveOptInfo.data.usePersistentCodeCache()) { 860 final RecompilableScriptFunctionData data = effectiveOptInfo.data; 861 final int functionNodeId = data.getFunctionNodeId(); 862 final TypeMap typeMap = data.typeMap(ct); 863 final Type[] paramTypes = typeMap == null ? null : typeMap.getParameterTypes(functionNodeId); 864 final String cacheKey = CodeStore.getCacheKey(functionNodeId, paramTypes); 865 compiler.persistClassInfo(cacheKey, normalFn); 866 } 867 868 final boolean canBeDeoptimized = normalFn.canBeDeoptimized(); 869 870 if (log.isEnabled()) { 871 log.unindent(); 872 log.info("Done."); 873 874 log.info("Recompiled '", fn.getName(), "' (", Debug.id(this), ") ", canBeDeoptimized ? "can still be deoptimized." : " is completely deoptimized."); 875 log.finest("Looking up invoker..."); 876 } 877 878 final MethodHandle newInvoker = effectiveOptInfo.data.lookup(fn); 879 invoker = newInvoker.asType(type.changeReturnType(newInvoker.type().returnType())); 880 constructor = null; // Will be regenerated when needed 881 882 log.info("Done: ", invoker); 883 final MethodHandle restOf = restOfHandle(effectiveOptInfo, compiler.compile(fn, CompilationPhases.GENERATE_BYTECODE_AND_INSTALL_RESTOF), canBeDeoptimized); 884 885 // Note that we only adjust the switch point after we set the invoker/constructor. This is important. 886 if (canBeDeoptimized) { 887 effectiveOptInfo.newOptimisticAssumptions(); // Otherwise, set a new switch point. 888 } else { 889 optimismInfo = null; // If we got to a point where we no longer have optimistic assumptions, let the optimism info go. 890 } 891 notifyAll(); 892 893 return restOf; 894 } 895 896 private MethodHandle restOfHandle(final OptimismInfo info, final FunctionNode restOfFunction, final boolean canBeDeoptimized) { 897 assert info != null; 898 assert restOfFunction.getCompileUnit().getUnitClassName().contains("restOf"); 899 final MethodHandle restOf = 900 changeReturnType( 901 info.data.lookupCodeMethod( 902 restOfFunction.getCompileUnit().getCode(), 903 MH.type(restOfFunction.getReturnType().getTypeClass(), 904 RewriteException.class)), 905 Object.class); 906 907 if (!canBeDeoptimized) { 908 return restOf; 909 } 910 911 // If rest-of is itself optimistic, we must make sure that we can repeat a deoptimization if it, too hits an exception. 912 return MH.catchException(restOf, RewriteException.class, createRewriteExceptionHandler()); 913 914 } 915 916 private static class OptimismInfo { 917 // TODO: this is pointing to its owning ScriptFunctionData. Re-evaluate if that's okay. 918 private final RecompilableScriptFunctionData data; 919 private final Map<Integer, Type> invalidatedProgramPoints; 920 private SwitchPoint optimisticAssumptions; 921 private final DebugLogger log; 922 923 OptimismInfo(final RecompilableScriptFunctionData data, final Map<Integer, Type> invalidatedProgramPoints) { 924 this.data = data; 925 this.log = data.getLogger(); 926 this.invalidatedProgramPoints = invalidatedProgramPoints == null ? new TreeMap<>() : invalidatedProgramPoints; 927 newOptimisticAssumptions(); 928 } 929 930 private void newOptimisticAssumptions() { 931 optimisticAssumptions = new SwitchPoint(); 932 } 933 934 boolean requestRecompile(final RewriteException e) { 935 final Type retType = e.getReturnType(); 936 final Type previousFailedType = invalidatedProgramPoints.put(e.getProgramPoint(), retType); 937 938 if (previousFailedType != null && !previousFailedType.narrowerThan(retType)) { 939 final StackTraceElement[] stack = e.getStackTrace(); 940 final String functionId = stack.length == 0 ? 941 data.getName() : 942 stack[0].getClassName() + "." + stack[0].getMethodName(); 943 944 log.info("RewriteException for an already invalidated program point ", e.getProgramPoint(), " in ", functionId, ". This is okay for a recursive function invocation, but a bug otherwise."); 945 946 return false; 947 } 948 949 SwitchPoint.invalidateAll(new SwitchPoint[] { optimisticAssumptions }); 950 951 return true; 952 } 953 954 Compiler getCompiler(final FunctionNode fn, final MethodType actualCallSiteType, final RewriteException e) { 955 return data.getCompiler(fn, actualCallSiteType, e.getRuntimeScope(), invalidatedProgramPoints, getEntryPoints(e)); 956 } 957 958 private static int[] getEntryPoints(final RewriteException e) { 959 final int[] prevEntryPoints = e.getPreviousContinuationEntryPoints(); 960 final int[] entryPoints; 961 if (prevEntryPoints == null) { 962 entryPoints = new int[1]; 963 } else { 964 final int l = prevEntryPoints.length; 965 entryPoints = new int[l + 1]; 966 System.arraycopy(prevEntryPoints, 0, entryPoints, 1, l); 967 } 968 entryPoints[0] = e.getProgramPoint(); 969 return entryPoints; 970 } 971 972 FunctionNode reparse() { 973 return data.reparse(); 974 } 975 } 976 977 @SuppressWarnings("unused") 978 private static Object newFilter(final Object result, final Object allocation) { 979 return (result instanceof ScriptObject || !JSType.isPrimitive(result))? result : allocation; 980 } 981 982 private static MethodHandle findOwnMH(final String name, final Class<?> rtype, final Class<?>... types) { 983 return MH.findStatic(MethodHandles.lookup(), CompiledFunction.class, name, MH.type(rtype, types)); 984 } 985 } 986