Can HotSpot optimize away redundant calls to pure methods without inlining them?

Question

Pure methods are those without side effects: their only effect is to return a value which is a function of their arguments.

Two calls to the same pure method with the same arguments will return the same value. So, given two calls to a pure method with identical arguments, can HotSpot optimize away the second call, simply re-using the value from the first call?

For example:

int add(int x, int y) {
  return x + y;
}

int addTwice(int x, int y) {
  return add(x, y) + add(x, y);
}

If HotSpot doesn't inline add inside addTwice does it understand that add is pure and thus call add only once and double the return value?

Of course, such a trivial [mcve] isn't likely to be of direct interest, but similar situations can occur in practice due to inlining, divergent control flow, auto-generated code, etc.

Key

The Java HotSpot Performance Engine Architecture does not seem to mention pure method detection. I would expect that such a feature would be highlighted if it were present. – Vining

@JimGarrison - Yup, although to be fair, that is a very high-level overview that only explicitly mentions five important techniques. Even if pure method detection did exist, I think it would be a couple levels of obscurity removed from ever being included in a list like that (although the fast "instanceof" thing they mentioned is pretty obscure). Here's a somewhat dated but more comprehensive list which also doesn't mention pure method detection. – Key

Given the optimization potential of pure method result caching, I'd be surprised if it wasn't mentioned :-) – Vining

Hiotspot can do anything it likes that isn't observable under the rules of the JLS and JVM Specification. – Dragoon

Afaik code analysis (of the optimization kind) only happens when a method is JITed. A not-inlined method might still be interpreted, so HotSpot wouldn't know if the method was pure. I would also be surprised if HotSpot would look at this when code is loaded, just to see if a method is pure, when it's not always known if a method will even be used. Besides, a method could act pure for a specific run of a program, or for a specific call site. It's not a real answer, but those factors push me in the direction of "no". – Kluge

@JornVernee It is false that a function can "act" pure. The definition of a pure function is that the result(s) only depend on the parameters. The VM (or any compiler) has full knowledge of the AST of the function and the function it calls. The only condition here is that the object file(s) are known to the VM and in RAM. It is relativly trivial to check if a function is indeed pure. Additionally a VM has the advantage over static compilers that it can instrument the code, optimize optimistically, deoptimize if it failed etc. Your statement is just so false. – Roughen

@Roughen - sure, but the JIT could use a looser definition of pure as well: it could consider a function conditionally pure if the current compiled version was pure, considering uncommon traps as pure, even if the whole function isn't pure. For example, if a function contains unpure behavior that is never observed in practice before compilation (e.g., logging on an error handling path), the JIT will usually choose not to compile the not-taken branch at all, but simply insert an uncommon trap covering that case, which would force recompilation of the function if it. – Key

Such a conditionally pure function could be optimized like a pure function if deoptimization in the uncommon trap case is also able to fix up the callers to remove the pure assumption. I don't think deoptimization usually affects the callers like that, but one could imagine it could. Still I agree with you that the JIT isn't generally going to evaluate pureness based on observed behavior, but simply based on a simple bytecode analysis that considers a function pure if it doesn't contain any heap reads or writes (perhaps augmented with escape analysis to ignore non-escaping reads/writes). – Key

Answer 1

HotSpot cannot do this so far.

If not inlined, a method call is typically opaque for JIT compiler. It is hard to make cross-method optimizations. One of the reasons is that a method entry point is volatile, i.e. it can change concurrently at run-time due to JIT compilation, re-compilation, deoptimization, JVMTI calls and so on. When HotSpot makes an explicit method call, it does not know whether the target method is interpreted or compiled, wether it collects JIT statistics, whether it is being debugged, if it has a breakpoint inside, or if JVMTI method events are enabled.

On the other hand, even if such optimization existed, it would not be too useful. Pure methods are very limited in what they can do, so they are typically short and simple and have much chances to be inlined. It is much easier for JIT to do optimizations within the same compilation scope after inlining.

Carbonation

Thanks, it makes sense (especially the part about how a function could vary between pure and non-pure depending on things like breakpoints, JVMTI, etc). When you say the entry point is volatile, do you mean that the actual entry point address of the called function can change (e.g., due to recompilation) or only that the body of the function can change? If I assume the former, then the volatility doesn't really seem to pose a problem: since if the entry point changes, all callers have to be recompiled anyways, at which point they could take the new "pureness" state into account, right? – Key

@Key The entry point address changes. Callers don't have to be recompiled, since the method is invoked by an indirect call, not by a direct address. – Carbonation

Thanks. I do see a lot of direct calls in C2 code, but perhaps those are for other types of stub routines or runtime methods, and not other methods. – Key

what about this? goertzel.org/papers/SupercompilingJavaMay2002.htm . Pure functions are not always "trivial". It is common in (pure) functional languages to write elaborate pure functions. – Roughen

I am so sick of this inlining, common subexpression elimination, etc and other standard themes in these compiler discussions!? Where are the compilers which produce the code on the level of supercompilers and superoptimizers? – Roughen