A plan for method inlining in Jato

As a first step, we implement method inlining only for static method calls. This ensures that we know the method body to be inlined (as opposed to speculating for virtual calls).

High-level Algorithm
- Detect invokestatic instructions (STMT_INVOKE)
- For each argument
- replace pushing the argument with (STMT_STORE temp = arg_expr)
(Store the mapping between arguments and temporaries)
- Inline method body with references to local_0 to local_(nargs-1) replaced by references to the corresponding temporaries. Replace local variables with temporaries in a similar fashion.
- Convert return in method body to the following sequence of instructions
- ret_temp = return_expr; goto inlined_code_end (For STMT_RETURN)
- goto inlined_code_end (For STMT_VOID_RETURN)

Method inlining in Cacao VM

In Cacao, Method inlining is done at IR level. First we have to select the "root" method to be inlined. This method contains callsites which could be inlined for performance. Once the "root" method is selected, we have to decide which call-sites could be inlined. This includes all static calls and all monomorphic virtual calls. Then we have to create an inlining plan which determines whether we should inline callsites in inlined method etc.

inline_inline() is the main driver method for inlining. inline_make_inlining_plan() analyses code and stores candidate callsites which can be inlined. This method depends on the inlining stratgy being used (Breadth First, Depth First, or knapsack). inline_transform() uses the inlining plan and does the actual inlining of IR instructions. We'll see the details of actual inlining in a later post.

Ref:
[1] "Adaptive optimization and On-stack replacement in CACAO VM" - Steiner, Krall, and Thalinger
[2] CACAO source code

Profiling results for inline caching

Read this

Megamorphic

Finished implementing megamorphic ICs for x86_32. The performance improvement seems to be minimal (performs worse for some benchmarks). Planning to add a stats collector for ICs to see what's going on.

Things to lookout for:-

# of ICed callsites with 1 or 2 calls - Large number implies we are spending too much time on ICing callsites which don't gain anything from IC.

# of callsites with a miss after 1 or 2 hits - Megamorphic callsites. This number should not be too high.

[PATCH] x86: Inline cache with clean and monomorphic states for INVOKEVIRTUAL.

goto patch

Design of IC - emission of callsite

See a discussion regarding IC design here

The discussion is one how to implement the inline cached callsite code emission.

Three kinds of classes

Primitive

These are classes which correspond to primitive data types like short. Note that these are different from the classes java.lang.Short and such. These classes are preloaded by Jato and used only by Java Standard Library.

Array

These are classes which correspond to types of references like

int [] ia = new int[10];

There cannot be any subclasses for these classes.

Regular

All other "normal" classes fall into this category.