Contributing an experimental inliner

[efferifick]

Hello,

My name is Erick and I've been working with @andrewcraik on an experimental inliner. The inliner is closed source at the moment and we would like to contribute it soon. We have already submitted a couple of PRs, however more will be coming soon.

So, why would this be good for OpenJ9?

• Instead of inlining as the call graph is traversed, the inliner first creates a data type called the Inlining Dependency Tree (IDT), which holds the universe of inlining decisions available for the inliner. Each node in the tree represents an inlining opportunity and has both a benefit and a cost.
• Having the IDT allows us to use the nested packing algorithm that produces a solution to the following problem: Which nodes in IDT should be selected such that we have the greatest cummulative benefit but do not exceed a cost?
• Keeps track of reasons why a callsite-method pair is given benefits so that we can answer questions like: Why was this callsite-method selected for inlining?
• One can add criteria to decide if a callsite-method pair should be inlined in the form of constraints and assign a benefit if that constraint is satisfied.
• Uses a fast approximation to find out static estimates about the operand stack and local variable array.

Some of the PRs that will be incoming in the next weeks will be:

• [ ] Obtaining the CFG from TR_EstimateCodeSize::realSize
• [ ] The contribution of the IDT class and how to build it
• [ ] Adding frequency information to the IDT (how often a call-site method pair is executed)
• [ ] Using BitVectors to represent inlining plans over the IDT.
• [ ] The inliner packing algorithm
• [ ] An abstract interpreter to find static approximation of run time values
• [ ] Method summaries to encode constraints

This inliner will probably not be used by default and some contributions will not be in use right away. There are still work we want to do to improve it.

If there are any questions feel free to ask! As more PRs are submitted, I'm sure more level of detail will be required for a meaningful discussion. We will be working to provide documentation for this inliner and also discuss design decisions so that this contribution fits OMR/OpenJ9's standards.

[DanHeidinga]

@efferifick (and @andrewcraik) this sounds amazing! It'll be great to see these kinds of improvements and experiments land in OpenJ9.

Can you expand a bit on how the inliner will be brought into the project? Is it intended to be #ifdefd and a compile time option to start with?

If it's runtime enabled, are there are additional footprint / performance costs to including it?

I expect you and Andrew have been talking about some of these things already and it would be good to reflect that discussion here for broader awareness.

[efferifick]

@DanHeidinga , @andrewcraik is on vacation right now, but it is my understanding that it will be runtime enabled. So, basically given an option in the -Xjit we can enable this experimental inliner.

We haven't done a lot of studies on the additional footprint / performance cost to including it and not running it. (I.e. running an unaltered OpenJ9 JVM against an altered OpenJ9 JVM but without enabling this experimental inliner). We mostly have focused on studying the performance cost of enabling this inliner. Right now the inliner runs about 5% slower when calculating the run time geometric mean using the Dacapo benchmarking suite and our compilation time is around 10% slower (again geometric mean across the different workloads). This comparison was done against an old version of OpenJ9.

It wouldn't be too much work to build this inliner as a compile time option. So, I would be open to #ifdef it out to avoid increasing the binary size.

[jdmpapin]

#ifdef makes the experimental code more prone to bit-rot, and makes debugging less flexible. For example, with a JIT option it would be possible to enable or disable the new inliner on a per-method basis. Could we measure the footprint cost before deciding whether to use #ifdef? Perhaps it's small enough. And the footprint should be the only real cost when the new inliner is not in use. The generated code will be unaffected, and the compile-time cost of checking the option should be negligible.

[efferifick]

For example, with a JIT option it would be possible to enable or disable the new inliner on a per-method basis.

The way we had imagined to originally contribute this experimental inliner was to use a template to select an inliner when the optimizer is adding optimizations to the _opt array. For example:

_opts[OMR::inlining] = new (comp->allocator())
        TR::OptimizationManager(self(),
        //enableExperimentalInlining is a flag on JIT options
        TR::SelectOpt<enableExperimentalInlining, OMR::ExperimentalInliner, OMR::TrivialInlining>::create, OMR::inlining);

I am not sure whether this will allow to select inliners on a per-method basis. (Is the optimizer initialized once per run or are instances of the optimizer created for every single compilation unit? Maybe some engineering is required to be able to select inliners on a per-method basis. One would also need to check the signature of the method against a regex supplied through the JIT options to select an inliner on a per-method basis.)

Could we measure the footprint cost before deciding whether to use #ifdef?

Sure but, what exactly do you mean by footprint and how would you like to measure it? I think by using the template there is no cost except the increase in binary size. But if one wants to select inliners on a per-method basis, then yes a small cost would be incurred every single time we check a regex and decide which inliner to use.

[DanHeidinga]

There are usually two parts to footprint:

• binary size aka size on disk
• runtime memory use, usually measured through RSS

The simplest way to check the first is to compare the size of the JIT dll with and without the inliner though I wouldn't expect it to cost much there.

The runtime footprint can be checked by looking at the RSS of a process. For code that's present but not used I wouldn't expect much growth but better to check before merging.

[jdmpapin]

Is the optimizer initialized once per run or are instances of the optimizer created for every single compilation unit?

It's created for each compilation. (Actually at least twice per compilation it seems, which I think is because we create an Optimizer to run ilgen opts.)

One would also need to check the signature of the method against a regex supplied through the JIT options to select an inliner on a per-method basis.

This is a generic feature of the JIT option system (option sets). If enableExperimentalInlining is a boolean option not flagged NOT_IN_SUBSET, then we can do

-Xjit:'{java/util/HashMap.put(*)*}(enableExperimentalInlining)'

and the option will be set only in HashMap.put.

[efferifick]

@DanHeidinga cool! I think we can do that in a bit. We are just updating our code base to use the latest OpenJ9/OMR commits and branches since we were working on an old version from last year.

@jdmpapin Thanks for clearing that out. I did know about regexes but I wasn't sure about the Optimizer and whether it is instanciated per-method or per-run. I was almost sure it was a per-run. So then, yes, the inliners can be selected on a per-method basis.