Escape Analysis

[galderz]

Escape Analysis is implemented according to IBM's Stack Allocation and Synchronization Optimizations for Java Using Escape Analysis paper. The code follows the flow insensitive algorithm within the paper, which is the simplest version to implement.

The implementation works through the intra-method and inter-method analysis to build connection graphs representing allocations, connections to these, and their escape state. The possible values for escape state are: global, argument or not escape. Allocations that do not escape can be stack allocated:

• All allocations are initially treated as not escaping, except for instances of Runnable, ThreadGroup and Thread, which are initially marked as global.
• Allocations that do not escape a method are stack allocated.
• Allocations that are assigned to static variables have their escape state changed to global and are not stack allocated.
• Allocations that are passed as parameters to other methods are stack allocated, if and only if, none of the methods in the call chain below assign them to static variables.
• Allocations that are assigned to field(s) of input parameter(s) are marked as escaping and are not stack allocated.
• Allocations that are returned from methods are marked as escaping and are not stack allocated.
  • With inlining, small methods that return new allocations could be merged with callers and could make allocations not escape, and hence result in stack allocations.
• Allocations of exceptions that are thrown are assumed to escape.
• Allocations happening within imperative loops are never stack allocated, even if they're marked as not escaping.

The intra-method and inter-method analysis work this way:

• In the intra-method analysis phase, each method is analysed independently to compute the connection graph and escape value for its nodes.
• In the inter-method analysis phase, a reverse topological order traversal is done over the program control flow. In this bottom-up traversal, the connection graph of callee methods is used to update the connection graph of the caller. The most important update that happens in this phase is that if a caller sends an allocation as a parameter to the callee, and the callee assigns it to a static variable, the allocation in the caller is marked as global escape.
• When the methods invoked are interface or abstract methods, the analysis makes a union of the connection graphs of all possible targets and uses the result of that to update the caller.

I've added a visitor for producing connection graphs, which visualizes New instances and nodes that link to them. Along with colour coding to identify no, argument or global escaping nodes, it helps visualize the internal connection graph. Two sets of graphs are produced, one for each of the escape analysis phases: intra-method and inter-method (see paper for more details).

Escape analysis, and the related optimizations, are enabled by default. A command line flag is available, --no-escape-analysis, to disable it, e.g. useful when diagnosing problem root causes. The --gen-graph flag has been enhanced to control generation of dot files for connection graphs.

Future work:

• Implement and compare flow sensitive algorithm.
• The current implementation does not use phantom nodes per se. Instead it relies on existing graph nodes to act them. During inter-method analysis this leads to extra computations. Phantom nodes might be added in certain places to avoid this.
• Apply further optimizations, e.g. remove synchronization from allocations that do not escape globally.
• More testing, e.g. with and without debugging info, with inlining...etc.
• Micro benchmarking escape analysis logic to understand its cost. This will also help to avoid unnecessary performance regressions and evaluate costs of code changes.

Other options considered:

• Partial Escape Analysis. The IBM option was chosen because it felt better suited and offered more possibilities for information reuse (e.g. connection graphs and points-to analysis could share some of the same information). With good inlining both algorithms can perform just as well (as mentioned by Charlie in his Escape Analysis presentation from 2020).

[dmlloyd]

Very cool work, nice job @galderz!

The implementation works through the intra-method and inter-method analysis to build connection graphs representing allocations, connections to these, and their escape state.

Is there a way for other plugins to determine whether any given Value escapes or not?

• All Runnable instances are always considered to escape globally.

Why is that? Wouldn't one of the previous rules account for any Runnable which were used in an escaping manner?

If the rules err on the side of deciding a value is non-escaping when it actually is, then the optimization will produce incorrect code and cannot be enabled.

• The current implementation does not use phantom nodes per se. Instead it relies on existing graph nodes to act them. During inter-method analysis this leads to extra computations. Phantom nodes might be added in certain places to avoid this.

What do the phantom nodes represent? The fact that a value has escaped?

[galderz]

Very cool work, nice job @galderz!

Thanks! 😊

The implementation works through the intra-method and inter-method analysis to build connection graphs representing allocations, connections to these, and their escape state.

Is there a way for other plugins to determine whether any given Value escapes or not?

All escape state, including connection graphs...etc are accessible via EscapeAnalysisState class. It can be retrieved via the CompilationContext, e.g. EscapeAnalysisState.get(ctxt).

Currently EscapeAnalysisState contains a single query method which looks like boolean isNotEscapingMethod(New new_, ExecutableElement element). It technically the first parameter could be any Node (or could be limited to Value) but I kept the type as specific as possible in this first iteration because so far I'm just querying with New instances.

• All Runnable instances are always considered to escape globally.

Why is that?

This comes from the paper itself. It assumes that Runnable instances will be passed to threads to execute and considers them a thread object. It conservatively assumes that each static field and thread objects outlive every method in the program.

Wouldn't one of the previous rules account for any Runnable which were used in an escaping manner?

If the rules err on the side of deciding a value is non-escaping when it actually is, then the optimization will produce incorrect code and cannot be enabled.

Not sure I understand what you mean. In the case of Runnable, it's assuming that it escapes globally so they'd never be stack allocated. So, if anything it errs on the side of deciding that it escapes, so no optimization is applied.

One more thing: I forgot to add to the discussion that Thread and ThreadGroup allocations are treated the same way. Thread, ThreadGroup and Runnable are initialized with escape state being global. Every other allocation is initialized as not escaping. I'll add more details to the discussion on this.

• The current implementation does not use phantom nodes per se. Instead it relies on existing graph nodes to act them. During inter-method analysis this leads to extra computations. Phantom nodes might be added in certain places to avoid this.

What do the phantom nodes represent? The fact that a value has escaped?

No, phantom values is what allows to summarise the effects of a callee method (that is, both connection graph and escape values associated with the nodes in it) independent of the calling context. According to the paper, phantom values would be used to point to arguments (e.g. ParameterValue) and returned values, and they would be used as starting point when iterating to merge callee information with the caller information.

So, what I mean above is that I didn't create these phantom nodes per se, but instead used existing graph nodes as phantom nodes. That's what I did with ParameterValue. I already explained this to Dan in early draft PR. However, this means that for things to work, I have to include the ParameterValue itself when iterating through to merge callee info with caller info. Doing this feels awkward in the code. It think having a phantom node to point to ParameterValue would make things cleaner.

I also want to have an idea of the cost differences between the two approaches before committing things. One more thing: I forgot to add that future work is micro benchmarking escape analysis performance. Having these benchmarks in place would with this.

[dmlloyd]

• All Runnable instances are always considered to escape globally.

Why is that?

This comes from the paper itself. It assumes that Runnable instances will be passed to threads to execute and considers them a thread object. It conservatively assumes that each static field and thread objects outlive every method in the program.

Ah I see. This may have been true at the time of writing but now many functional APIs accept Runnable and specifically do not escape.

What do the phantom nodes represent? The fact that a value has escaped?

No, phantom values is what allows to summarise the effects of a callee method (that is, both connection graph and escape values associated with the nodes in it) independent of the calling context. According to the paper, phantom values would be used to point to arguments (e.g. ParameterValue) and returned values, and they would be used as starting point when iterating to merge callee information with the caller information.

Ah I see. I think we do eventually need a good solution for summarizing callee info since many optimizations can be derived from that information.

[galderz]

• All Runnable instances are always considered to escape globally.

Why is that?

This comes from the paper itself. It assumes that Runnable instances will be passed to threads to execute and considers them a thread object. It conservatively assumes that each static field and thread objects outlive every method in the program.

Ah I see. This may have been true at the time of writing but now many functional APIs accept Runnable and specifically do not escape.

Good point. I'll remove special handling of Runnable.

[galderz]

Ah I see. I think we do eventually need a good solution for summarizing callee info since many optimizations can be derived from that information.

I clarified this in the chat, but I wanted to put it here for future reference: summarizing callee info is already in place per se. It's slightly suboptimal at the moment but I feel it's only a small penalty at the moment. Aside from that, all the pieces for summarising the information is already in place and working as expected.