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 
  87     CompiledFunction(final MethodHandle invoker) {
  88         this(invoker, null, null);
  89     }
  90 
  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 
  95     CompiledFunction(final MethodHandle invoker, final MethodHandle constructor, final Specialization specialization) {
  96         this(invoker, constructor, 0, null, specialization, DebugLogger.DISABLED_LOGGER);
  97     }
  98 
  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 
 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 
 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 
 138     boolean isSpecialization() {
 139         return specialization != null;
 140     }
 141 
 142     boolean hasLinkLogic() {
 143         return getLinkLogicClass() != null;
 144     }
 145 
 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 
 155     boolean convertsNumericArgs() {
 156         return isSpecialization() && specialization.convertsNumericArgs();
 157     }
 158 
 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      */
 173     boolean isOptimistic() {
 174         return isSpecialization() ? specialization.isOptimistic() : false;
 175     }
 176 
 177     boolean isApplyToCall() {
 178         return (flags & FunctionNode.HAS_APPLY_TO_CALL_SPECIALIZATION) != 0;
 179     }
 180 
 181     boolean isVarArg() {
 182         return isVarArgsType(invoker.type());
 183     }
 184 
 185     @Override
 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 
 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      */
 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      */
 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      */
 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      */
 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      */
 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      */
 314     MethodHandle createComposableConstructor() {
 315         return createComposableInvoker(true);
 316     }
 317 
 318     boolean hasConstructor() {
 319         return constructor != null;
 320     }
 321 
 322     MethodType type() {
 323         return invoker.type();
 324     }
 325 
 326     int weight() {
 327         return weight(type());
 328     }
 329 
 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 
 347     static boolean isVarArgsType(final MethodType type) {
 348         assert type.parameterCount() >= 1 : type;
 349         return type.parameterType(type.parameterCount() - 1) == Object[].class;
 350     }
 351 
 352     static boolean moreGenericThan(final MethodType mt0, final MethodType mt1) {
 353         return weight(mt0) > weight(mt1);
 354     }
 355 
 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 
 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 
 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 
 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 
 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 
 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 
 572     private boolean canBeDeoptimized() {
 573         return optimismInfo != null;
 574     }
 575 
 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 
 596         HandleAndAssumptions(final MethodHandle handle, final SwitchPoint assumptions) {
 597             this.handle = handle;
 598             this.assumptions = assumptions;
 599         }
 600 
 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      */
 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 
 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 
 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      */
 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 }