# Lazy method handles
(2011-12-22 version)

## Problems:
- MH instantiation is slow (native calls to set up assembly stubs).
- exact MH invocation is slow (no good compiled code path).
- MH compilation work is not shared among similar MHs.
- Multi-bound MH layout is not compact.
- Ricochet frames introduce a significant porting and maintenance burden.

## Solutions:
- Make MH instantiation be lightweight symbolic composition.
- Create optimized invocation paths only after "sufficient" invocation (cf. hot-spot treatment of methods).
- Collect bound values at the root level of MH structure (for eventual use by fast path).
- Reuse/cache common code structure (modulo bound values).
- Have MH.invoke methods include an extra level of recursion, in all but the most optimized states.

## MH layout:
    struct MH {
      header : usual JVM header
      type : immutable type
      form : immutable behavior (type `LambdaForm`)
      form.exactInvoker : mutable (optimizable) entry point for invoking the MH
      data... : immutable values, inline
    }

The various MH constructors initialize the type, form, and data to permanent values.
The type, form, and data determine the semantics of the MH.
The type, form, and data are disjoint (as a rule, when convenient to the implementation).

The form's `exactInvoker` field is set to an initial linking routine.
This field may be amended later to an optimized routine.
There are no race conditions, since the exactInvoker field always contains
a valid entry point for the given (immutable) type, form, and data.

When the form.exactInvoker field is executed, the MH reference is in leading position (e.g., register rcx).
Therefore, any machine code is reached by the MH code address is able to obtain the MH type, form, and data.
Code for a given "form" is optimized, but operates on the type and data as free variables (extra arguments).

Composition is performed by creating a new version of the MH with an adjusted MH.form field.
The new MH may also have additional (or completely different) data fields.

Additional fields may be worth adding:
 - Have a code field directly in the MH itself, which is a copy (or specialization) of form.exactInvoker.
 - Have additional invoker paths for the `LambdaForm`, such as `genericInvoker`, `spreadInvoker`, `partialInvoker`.

### old MH layout _(as of JDK7 FCS)_
Same as above, with the following exceptions:

- no "form" field (no symbolic representation, which limits sharing)
- adapter or bound MH contains a tail-called "vmtarget" (sharing of executable nodes, only)
- data fields are limited to a single reference (a common case, but requires boxing, cascading, etc.)
- code field is called "vmentry", and various among a small (~100) set of predefined combinators
- code field does not support compiled fast path (NYI)
- composition is performed by tail-call chaining, with incremental argument transformations

Having the code field be a raw machine-level pointer meant that the Java code
for creating method handles had to include native calls, which tend to be slow.

### uses of metadata in new data structures

In the new design raw machine-level pointers are limited to the internal
type `MemberName`.  Member names must be resolved by a reflective query to
the JVM, which involves native calls.

The machine-level pointer in a member name is called `vmtarget`, and it
is of (internal) type `methodOop`.  There is also an internal integer
field called `vmindex`, used to store a vtable or itable index.

(Member names can also refer to fields, in which case `vmtarget` is
of type `klassOop`, and `vmindex` is a field offset.)

A `MemberName` reference can be bound to a method handle or other structure
(`LambdaForm.exactInvoker`) with a simple Java-level field assignment.

Unlike method handles, member names are relatively easy to cache, and
do not need to be created frequently.  They are associated with uses
of the `MethodHandles.Lookup` API, which is advertised as "reflective".

Member names are also used by lazy bytecode spinning mechanisms which
create optimized invokers for "mature" or "warm" lambda forms.
The internal method oops created in this way are subject to further
profiling and optimization by the JVM, just as for user-level methods.

## MH exact invocation paths

Here are the paths to aim at.  All other paths can be comparatively slow,
as long as the fast paths are attained in warm code.

(Also, if families of similar method handles are created, warming some
of them should allow all the future ones to share the optimized code.
The later method handles in the same family should quickly acquire the
code.  This requires that the forms be built with structure sharing,
or acquire structure sharing over time, and that the shared structures
be mappable to the optimized invocation paths.)

### compiled fast path

- place method handle in rcx (standard register for first reference argument)
- preserve stack pointer (spill rsp to callee-saved rbp)
- materialize expected MH.type (as constant)
- verify `rcx.type` (slowly throw error if mismatched)
- load `rcx.form.exactInvoker.vmtarget` (three indirections to get to methodOop)
- jump directly to `_from_compiled_entry` of the `LambdaForm.exactInvoker` method

After the jump:

- enter nmethod code for `LambdaForm.exactInvoker` method (`L0 == rcx == the MH`)
- shuffle arguments as needed (load `MH.data[*]` and/or `MH.type[*]`)
- tail-call eventual target, return a value, etc...
- return to caller
- restore stack pointer (reload rsp from rbp)

In JDK7 FCS, the compiled path is longer:

- place method handle in rcx (standard register for first reference argument)
- preserve stack pointer (spill rsp to callee-saved rbp)
- jump to compiled entry point of the MH.invokeExact method
- execute a C2I adapter: extend the stack, rebuild argument list for interpreter
- jump to interpreter entry point of the same MH.invokeExact method
- perform interpreter-mode MH invocation sequence (see below)

### MH exact invocation, *interpreted path*

- preserve stack pointer (spill rsp to rsi, as for all interpreter calls)
- materialize expected MH.type (from MH.invokeExact methodOop in rbx)
- load method handle from stack into rcx (using stack depth obtained from MH.type)
- verify `rcx.type` (slowly throw error if mismatched)
- load `rcx.form.exactInvoker.vmtarget` (three indirections to get to methodOop)
- jump directly to `_from_interpreted_entry` of the `LambdaForm.exactInvoker` method

After the jump, if the lambda form is not yet mature:

- enter interpreted or compiled code for common JVM bytecoded method (`L0 == rcx == the MH`)
- execute generic AST-walking interpreter for LFs

After the jump, if the lambda form is mature and has been given customized `exactInvoker`:

- enter interpreted or compiled code for customized JVM bytecoded method (`L0 == rcx == the MH`)
- shuffle arguments as needed (load `MH.data[*]` and/or `MH.type[*]`)
- tail-call eventual target, return a value, etc...

## Invokers

The field `LambdaForm.exactInvoker` points to a `MemberName` that is
(at all times) capable of executing the semantics of the lambda form.

Initially, this method is an AST-walking interpreter which is shared
by all LF's of the same basic type signature.

The LF's exact invoker is created as a static bytecoded method.
Its first argument is the MH itself.

The behavior of the invoker is determined by the lamba form itself.
Typically, it is at least partially optimized,
by rendering the contents of the form as bytecodes.

Initially, the invoker may be unspecialized to the form's body, in which
case it must interpret the structure for the form, as a non-constant
parameter (on the same footing as the MH type and data).
Such invokers can be show great laziness, generating more optimized
forms only after complex sharing heuristics are consulted.

In principle, and in the reverse direction, the invoker may be
specialized to information in the MH beyond the form.  For example,
the MH type field can be folded into the invoker as a constant,
or one or more MH data elements (or merely their types) can be
folded in.  This would require a new code invoker field
in method handles, or some other sort of multiway dispatch
on method handle invocation.

The current case is that the invoker depends on only the form, and
functionally replaces it.  The fully optimized code of the invoker
will unpack the MH type and data into additional arguments, and will
ignore the form.  (I.e., no AST walking.)

### direct MH invoker
For a direct method handle to the static method `C#m(A)`,
there are no data fields, just a type and form.
The invoker is therefore:

    (mh, A a)->{ignore mh; C.m(a)}

A direct method handle to something other than a static method
is exactly analogous.

### bound MH invoker to virtual
For a bound method handle to a virtual method `c#m(A)`,
there is one data field of type `C`, plus the type and form.
The invoker is therefore:

    (mh, A a)->{C c = mh.data_c; c.m(a)}

A bound method handle to another kind of direct method handle
is exactly analogous.

### multiply-bound MH invoker
If a method handle is bound several times, or bound to a complex
adapted method handle, the newly bound value is accumulated into
a copy of the target method handle, and the invokers are composed.
The old invoker is adjusted to take its parameter values from the
new (copied) method handle.

Here is a doubly-bound method handle to a static method `C#m(P,Q,A)`:

    (mh, A a)->{P p = mh.data_p; Q q = mh.data_q; C.m(p, q, a)}

More generally, a binding on top of a complex method handle looks
like this:

    (mh, A a)->{P p = mh.data_p; target.invoker(mh, p, a)}

Note that mh need not contain a pointer to its target, as long as
the target's invoker is known (or can be extracted from mh).
In fact, assuming the target's invoker depends only on the
target's form, and the new bound handle's form is derived from
the target's form, the target's invoker is know from the
new bound handle's own form, and can be compiled directly into
the new bound handle's invoker.

There is an additional trick assumed by the code above.
The new bound method is passed to the target's invoker,
even though the target invoker expects the target.
This trick only works if the target and the new bound
handle supply the identical values required by the target
invoker.  This will be the case only if (a) the bound
handle copies all data values from the target handle
that the target invoker requires, (b) the `data_p`
field does not overlap with any of those fields,
and (c) any use of the target's type field by the
target invoker is consistent with the bound handle's
own type field.

If this trick fails, the target invoker can (and must)
be inlined into the new invoker.

### return adapter MH invoker
A adapter method handle which adapts its return value can be
viewed as a simple composition of a return transform `#r` on
top of the original target method handle.  The adapted method
handle is a copy of the original target method, with a different
form, whose invoker is therefore:

    (mh, A a)->{ x=target.invoker(mh, a); r(x) }

This assumes that the return transform is a simple static method.

### composed method handle invoker
The composition of two arbitrary method handles requires
a composed invoker which can emulate the invokers of the
two component method handles, and requires that all bound
values in both component method handles be available in
composite method handle.

There are several ways to implement this.  The composite
handle can be populated with all data values from the
components, or (at the other extreme) the composite
handle can have two data pointers, one to each component.

A mixed approach seems promising, where one handle,
viewed as the nominal "target", is copied into the
composite.  The other, viewed as the nominal "transform",
is inlined into the invoker as much as possible,
and any remaining parameters are added to the
target, probably with a level of indirection.

## form

A form is simply a symbolic representation of an invoker.

The form schema is competent to specify all MH transforms.

It is as follows:

    form:       function
    function:   method | intrinsic | lambda
      method:     (CONSTANT_MethodHandle instance)
      intrinsic:  (ad hoc intrinsic, such as iadd)
      lambda:     formals returns '->' body
    formals:    '(' LIST[formal] ')'
    returns:    ':' (basictype | 'void')
    body:       '{' (temp? call ';')* call '}'
      temp:       formal '='
      call:       function '(' LIST[argument] ')'
    LIST[E]:    (E (',' E)*)?
    formal:     basictype vardef
      basictype:  'int' | 'long' | 'float' | 'double' | 'reference'
      vardef:     (nothing; vars are lexically numbered)
    argument:   varref | constant | MAYBE_LATER[function]
      varref:     (a natural number; the lexical index of var; no uplevel refs)
      constant:   (any constant pool constant or "live" reference)
      MAYBE_LATER[E]: (maybe E, later)

Calls cannot be nested.  The final call is always treated as a tail-call.

The incoming formal parameters are numbered starting at zero.
The temporary variables (if any) are numbered immediately after.
Variable references are only relative to the immediately enclosing lambda.

The MH parameter (passed to the invoker) is conventionally the first formal parameter.
It is not otherwise distinguished in this grammar.  Bound values are extracted
via field references, which are encoded as calls to direct method handle constants.

(Also, this formalism might be useful for spinning JDK 8 closures.
In that case, the first argument would be a non-MH closure object.)

If lambdas are allowed as literals, they will be interpreted as pre-optimized
direct method handle references.  There is presently no need to define internal
"frames" or bound value displays, other than the data fields of the MH itself.

The basic type structure of a lambda type is a list of simplified "basic types",
similar to an erased `MethodType`.  Subword types like `boolean` are
represented as `int` and all references map to `Object`.

Although this erasing means that unsafe code can be constructed,
it allows much greater code sharing among lambda forms, and therefore
much less reliance on dynamic creation of bytecodes.
In particular, many direct method handles can be implemented by
a single lambda form, as long as they all agree on a common
arity and use of integral or floating primitives.

(Compare this with the reflection implementation of Java SE, which
must spin one internal bytecoded method per distinct Java method
that will be invoked.)

Lambda forms are required and trusted to preserve static type safety with
respect to the full set of MethodType signatures.

The raw structure of a lambda body is a list of calls.
The raw structure of each call is a list of functions and arguments.
Thus, a lambda body is, in its raw structure, a ragged array of values.

The classes representing these will be something like
`FunctionForm`, `LambdaForm`, `CallForm`, `ArgumentForm`.

The form types will be private to the JVM implementation.
Forms will be trusted and (usually) not verified.

The typing of intermediate values will use only basic types, excluding
the subword types (boolean, byte, char, short).

This representation is designed to be as simple as possible, so that it can be
readily constructed, walked, memoized, and optimized to bytecode.

### relation to JDK 7 implementation

The supported MH transforms include the internal nodes of the JDK 7 FCS
representation.  They relate to the new symbolic form roughly as follows:

<table border="1">
  <tr><th>operation</th> <th>invoker component</th></tr>
  <tr><td>direct MH</td> <td>JVM <code>CONSTANT_MethodHandle</code></td></tr>
  <tr><td>bound MH</td> <td>field load (of <code>MH.data_N</code>)</td></tr>
  <tr><td>profiling MH</td> <td>field load/store (of <code>CMH.data_vmcount</code>)</td></tr>
  <tr><td>retype AMH</td> <td>none (invokers are trusted)</td></tr>
  <tr><td>checkcast AMH</td> <td>invoke of Class.cast</td></tr>
  <tr><td>prim/ref conversion AMH</td> <td>invoke of conversion method</td></tr>
  <tr><td>permuting AMH</td> <td>explicit numbering of component inputs</td></tr>
  <tr><td>collect AMH</td> <td>invoke of array constructor</td></tr>
  <tr><td>spread AMH</td> <td>invoke of element accessors</td></tr>
  <tr><td>filter/fold AMH</td> <td>invoke of transform method handle</td></tr>
</table>

### MemberName invokers

There are invokers for direct method handles, one for each basic type
signature and invocation mode:

    dmh.invokeStatic(a*) => M(a*)
    dmh.invokeVirtual(x,a*) => M(x.class)(x,a*)
    dmh.invokeSpecial(x,a*) => M(x,a*)
    dmh.invokeInterface(x,a*) => M(x.class)(x,a*)

In each case the invoked method M depends on the target method handle `dmh`,
which must be a `DirectMethodHandle` whose `member` field is a member name
that refers to a method of the compatible type.

(In the case of `invokeSpecial`, the member name can be a constructor also.)

For creating weakly typed method handle invocations from inside lambda forms,
there is also a signature-polymorphic method that acts as an unchecked form
of `MH.invokeExact`:

    mh.invokeBasic(a*) => mh.invokeExact(a*)  (no WrongMethodTypeException)

As with `invokeExact`, the call site signature of `invokeBasic` must agree with
the target method handle.  The agreement is loosened to basic type signature.
(I.e, references are erased to `Object` and subword types to `int`.)
Failure to agree is an error which can crash the JVM.

The Java Language Specification allows all these additional invocation methods
to be signature polymorphic.  Note that they are *not* public.

The compilers are expected to be able to compile calls to these methods
efficiently, both with constant and non-constant MH targets.
In the case of a constant direct method handle for `invokeStatic`,
`invokeVirtual`, etc., the compiler should generate the same code
as if had encountered a normal symbolic reference to the `methodOop`
of the constant `MemberName`.

### varargs invokers

For each basic type signature sig:

    invokeVarargs[sig] := lambda (mh, args) {
      assert(mh.type.basicTypeSignature == sig);
      assert(!mh.isVarargsInvoker);
      Object arg_ref_i = ((Object[]) args )[i]; ...
      T_i arg_i = convertAndUnbox[T_i]( mh.type.parameterType(i), arg_ref_i ); ...
      assert(sig[i] == T_i); ...
      T_r res = (T_r) mh.invokeExactTrusted(arg_i...);
      Object res_ref = box[T_r](res);
      return res_ref;
    }

## conversions

Conversion functions (for arguments and return values) can be made via
MHs.identity and MH.asType.

In order to lift these to pure JVM methods, a reified type is sometimes
required as the leading argument.  For uniformity we present the leading
argument even when it is not used.

    convertAndUnbox[T in {int, long, float, double}] = lambda (_, Object x) : T {
      MH conv = MHs.identity(T).asType(methodType(T, Object));
      return (T) conv.invoke(x);
    }

To deal with the representation of boolean/byte/short/char as int, an
additional cast may also be necessary.

    convertAndUnbox[T in {byte, short, char}] = lambda (_, Object x) : int {
      MH conv = MHs.identity(T).asType(methodType(T, Object));
      MH rawconv = conv.asType(methodType(int, Object));
      return (int) rawconv.invoke(x);
    }

    convertAndUnbox[T = boolean] = lambda (_, Object x) : int {
      MH conv = MHs.identity(boolean).asType(methodType(boolean, Object));
      MH rawconv = MHs.explicitCastArguments(conv, methodType(int, Object));  // handles boolean->int
      return (int) rawconv.invoke(x);
    }

For reference types, the reified target type must be dynamically specified:

    convertAndUnbox[T <: Object] = lambda (Class T, Object x) : Object {
      MH conv = MHs.identity(Object).asType(methodType(Object, T));
      return (Object) conv.invoke(x);
    }

This boils down to a simple cast:

    convertAndUnbox[T <: Object] = lamba (T, x) (Object) T.cast(x)
    convertAndUnbox[T <: Object] = Class::cast

In cases where the reference type is statically known to be exactly Object,
things can be much simpler:

    convertAndUnbox[T = Object] = lambda (_, Object x) : Object { return x; }
    convertAndUnbox[T = Object] = MHs.identity(Object).dropArguments(0, Class)

In cases where we are generating code for a basic type signature to be shared
by multiple MethodTypes, certain runtime information must be incrementally
available.  This is why the extra argument is present.  Each reference type
(except those somehow known in advance, e.g., as Object or Object[]) must be
reified dynamically.  If it participates in reference casting only, it needs
to be combined with something as simple as Class::cast.  If it participates in
primitive unboxing or boxing from an inexact reference type, something
trickier from ValueConversions is needed to manage primitive conversions on
the fly.  Each integer subrange type (boolean/byte/short/char) needs to be
reified somehow also, enough to select one out of four possible cases.