JIT ideas

[hrj]

• [x] removing needless PC increments from the JIT (PC gets restored to a constant on jump, on error, or on end of block/trace)
• [x] removing empty else clauses in JIT emitted code. Empty else clauses have disappeared after delayed PC increments from above fix.
• [ ] Detecting "simple" Java functions, that is, functions that don't have branches, don't throw exceptions, don't call other functions, etc.
  • These simple functions can be JIT optimised immediately after first run.
  • Simple functions also don't need frame.locals. Their local array can be just symbols in emitted code.
  • Simple functions will also be ideal candidates for inlining.
• [ ] The JIT emiters can use symbolic frame.locals just as they use a symbolic operand stack. This will be useful to optimise "simple" functions, and help in inlining functions.
• [ ] Implement function inlining.
• [ ] Peep hole optimisations. For example, javac has a tendency to emit code like this: istore_0; iload_0. This can be optimised to dup; istore_0;. This optimisation can be done at JIT time. Or perhaps as a separate pass, triggered before JIT threshold is reached. Alternatively, this can be done by a separate tool AOT.

Things which I have already experimented with, and got mixed results:

• Convert to fast opcodes during JIT whenever possible.
• Re-JIT after fast opcodes are written in interpreter mode.
• Attaching values to emitted JIT function. For example, constant lookups need not be done when the emitted function is run. They can be pre-computed and attached to the emitted function. Gives good performance on every benchmark, except Scimark.
• Various ways of optimising the interpreter loop.
  • using switch-case statement to lookup JIT functions
  • swapping in a different interpreter function when JIT threshold is reached

[hrj]

Some more ideas:

• Shorten the names of some APIs used in emitted JIT functions. Eg: fieldOwnerConstructor
• Add API for registering method overrides. Follow up from #435. This is not exactly related a JIT TODO. I was just waiting for JIT to land and mature, so that I can hand-tune methods selectively.
• Support for more opcodes. I just lazily added JIT emitters for the opcodes I encountered in my benchmarks.
• Support for wide instructions. Though I haven't encountered the WIDE opcode prefix in any of my benchmarks.

[jvilk]

The JIT should eventually change to perform a pre-JIT pass to determine basic blocks and construct a control flow graph. As it currently stands, the JIT may inline a basic block into multiple blocks due to the way it handles branches. The CFG will let us figure out when a block is jumped to once, letting us inline branches (including if/else branches), among other improvements.

Detecting "simple" Java functions, that is, functions that don't have branches, don't throw exceptions, don't call other functions, etc.

Yes; we should have a mechanism to deposit JIT metadata on methods, such as whether or not a function can complete synchronously. We could probably support exceptions in there if we are sufficiently clever, e.g. lazily constructing stack frames when needed.

There are other tricks here we can use from other JVMs. For example, private methods cannot be overridden, so virtual calls to private methods are not actually virtual -- so we know the destination method statically.

Finally, we should probably augment the native method API at some point so the JIT can tell which functions are synchronous.

[jvilk]

Shorten the names of some APIs used in emitted JIT functions. Eg: fieldOwnerConstructor

I don't view this as a useful optimization? Unless you mean to optimize for some of Chrome's inlining heuristics (e.g. source code size).

[hrj]

Shorten the names of some APIs used in emitted JIT functions. Eg: fieldOwnerConstructor

I don't view this as a useful optimization? Unless you mean to optimize for some of Chrome's inlining heuristics (e.g. source code size).

Reducing the source code size so as to reduce parsing time, and also to a certain extent -- memory consumption. But the latter is not specific to JIT; the parsing time is.

[jvilk]

@hrj I experimented with changing the JIT over to emitting a single Function, with case statements for each basic block. I changed your opcode size functionality to cover 100% of the opcodes, so the JIT can compile an entire method at once. (And fixed some bugs -- for example, invokeinterface is actually 5 bytes long because it has an empty 5th byte.)

This JIT is currently slower than yours, likely because it does not unconditionally inline basic blocks when a branch is not taken. But I think it is a good basis from which we can build a control flow graph of basic blocks, which we can use to inline blocks into their dominators.

It's in a branch here. I restructured some of the code to make the JIT a little more self-encapsulated. I don't want to merge it in until it is roughly at parity with the speed of your JIT. Feel free to build on it.

[hrj]

@jvilk Interesting. I just had a glance and will look deeper into it later.

It will be good to merge the bug fix and JIT restructuring into master, so that even if we are unable to optimise or enhance that branch, development on master branch can continue without merge conflicts or regressions.