Contributing a new Inliner (BenefitInliner) to OMR

[xiacijie]

Contributing a new Inliner (BenefitInliner) to OMR

Over the last 3 years IBM has funded a joint research project with the University of Alberta to explore new inlining technologies for Eclipse OMR. With the master’s thesis work of ‪Erick Ochoa, which forms the core of this new inliner implementation, along with work from Cijie Xia and Spencer Killen, who have also made contributions, the research team now feels the implementation of this inliner is mature enough to contribute to the community.

The BenefitInliner is a new approach to inlining which aims at maximizing the opportunity for optimization when selecting methods to inline. The inliner uses abstract interpretation to simulate program execution at little cost and to identify potential opportunities for optimization such as branch folding and null-check folding etc. Those potential optimization opportunities will be taken as one major factor along with others when developing inlining strategies.

We are proposing to contribute the core infrastructure of this new inliner to Eclipse OMR. In parallel, we are proposing to the OpenJ9 project to contribute an implementation of our abstract interpreter which operates on Java bytecode so that they could consume this new inliner as part of their project. Our experiments have shown that this new inliner produces inlining plans that are roughly equivalent in performance to the current inliner in OpenJ9, but without some of the limitations of their current inliner and no hacky heuristics to guide the choice of inlining decisions. The major advantage of the BenefitInliner approach is the determinism and explainability of the plans that it produces.

Parts to be contributed to OMR:

1. IDT

The BenefitInliner starts by building an IDT. IDT stands for Inlining Dependency Tree. It is a data structure that holds all candidate methods to be inlined. The parent-child relationship in the IDT corresponds to the caller-callee relationship.

2. IDTNode

IDTNode is the building block of IDT. It is an abstract representation of a method containing useful information for inlining. Two most important pieces of information are the cost and benefit. The cost is equal to the size of the method. The benefit is calculated as the product of the method's call ratio and benefits of the optimizations from inlining the method. They will be used for selecting methods to be inlined by the inliner packing algorithm.

3. IDTBuilder

IDTBuilder is used for constructing the IDT. In order to build the IDT, it needs two core functionalities. One is generating the control flow graph and the other is running the abstract interpretation. CFG is needed during abstract interpretation. CFG generation and abstract interpretation require language specific implementations. Abstract interpretation identifies call sites, generating the inlining method summary and simulates the program state.

4. InliningMethodSummary

The Inlining summary captures potential optimization opportunities of inlining one particular method and also specifies the constraints that are the maximal safe values to make the optimizations happen. The summary itself alone is not enough to determine which optimization will be unlocked after inlining because those constraints may or may not be satisfied. Therefore, we need to test the simulated program states against the summary to see whether the constraints are satisfied or not. InliningMethodSummary is extensible and reusable. It enables compiler engineers to compute their customized constraints through static analyses.

5. AbsValue, AbsOpStack, AbsLocalVarArray and AbsState

As their names suggest, the above classes are components that simulate the program state and used for abstract interpretation. AbsValue encapsulates the VPConstraint as the constraint for different types of values.

6. BenefitInliner and InliningProposal

BenefitInliner contains the code of the inliner packing algorithm and the code for performing the inlining. Inliner packing algorithm analyzes all the candidate methods in IDT based on their cost and benefit and generates an Inlining Proposal containing the optimal set of methods to be inlined.

Contribution plan

The contribution will have three phases.

• Phase 1: Contribute the basic classes for abstract interpretation.

AbsValue.cpp

AbsState.cpp

AbsLocalVarArray.cpp

AbsOpStack.cpp

• Phase 2: Contribute the code for IDT building and abstract interpretation.

IDT.cpp

IDTNode.cpp

OMRIDTBuilder.cpp

InliningMethodSummary.cpp

• Phase 3: Contribute the code for Inliner packing and inlining

BenefitInliner.cpp

InliningProposal.cpp