eclipse-openj9
Refine intra-block liveness for local references
The JIT code generator is responsible for building live reference maps for the garbage collector at various yield points in a method. During instruction selection, for each block, the reference local map is initialized from some starter set on block entry and adjusted as nodes are evaluated in a block [1]. At lower optimization levels and in certain JIT modes the starter set is quite conservative where all references are assumed to be live at every point in the method. But at higher optimization levels a reference liveness analysis (liveVariablesForGC [2]) is performed in the optimizer before code generation that computes a refined live-on-entry set of references for each block.
The JIT employs a conservative approach to local reference liveness within blocks in that it tracks liveness on block entry [1] and when a reference becomes live within a block [3], but it does not refine those live ranges should a local reference die within a block. Tracking only when references become live within a block is a reasonable approximation for the JIT to make as refining live ranges has a higher computational cost in terms of compile time and complexity for generally little benefit.
However, there are situations where the JIT's conservative approach may prevent some provably dead (and possibly very large) objects from being reclaimed sooner. A more precise live range for reference locals within blocks would benefit such applications, but comes at the cost of a more expensive analysis. The JIT already supports an "aggressive liveness" option which enables a more rigorous live local reference analysis to be performed at the cold optimization level (in addition to the same analysis applied at opt level warm and above). This same option can be used to enable a more expensive live range analysis.
The objective of the analysis is simple: modify the intra-block local reference liveness propagation in the code generator to track when local references are killed. That is, for references that are not live-on-exit to a block, kill the reference in the intra-block liveness bit vector after the last use of the reference in the block. With a refined liveness set the GC maps will take care of themselves.
One possible way of implementing this is the following (use this as a general guide only as there are likely details that I haven't thought of here), which should only apply when the aggressive liveness option is used. We will first need some means of determining the last load or loadaddr of a local reference symbol in a block which will require an analysis of the block before node evaluation. Introduce a pass during the lower trees phase to record the last load or loadaddr node of a local reference symbol as seen in evaluation order. Each block could maintain a map (for example) of symbol references to nodes for such references. Note that it cannot be assumed that a load of a symbol is commoned in a block that all such loads are commoned.
Furthermore, the reference locals of interest are only those that are not live-on-exit from a block (if they are then they can't be killed within the block). However, at present, live-on-exit information is not maintained on a block (only live-on-entry). When a new block is encountered, it's live-on-exit set can be computed through a union of the entry sets of all its successors. If, for some reason, a successor block does not have liveness information then its live-on-entry set should assume all are live. Therefore, the symbol reference to node mapping need only be maintained for symbol references not live on exit.
This information is consulted during the J9::CodeGenerator::doInstructionSelection()evaluation walk. If a node is evaluated that appears in the last load or loadaddr mapping then it can be killed in the liveness set.
Note that register rematerialization, compact locals, and deferred evaluation of some nodes in the code generator may interfere with this analysis, so the effects of these analyses should be studied and mitigated (and determining a more exhaustive set of analyses that could impede this analysis). Disabling register rematerialization when aggressive liveness is enabled might be one solution, for example.
[1] https://github.com/eclipse-openj9/openj9/blob/34eacb42356a4cfbfbedfce412df7cc276cd3770/runtime/compiler/codegen/J9CodeGenerator.cpp#L1710 [2] https://github.com/eclipse-openj9/openj9/blob/34eacb42356a4cfbfbedfce412df7cc276cd3770/runtime/compiler/optimizer/LiveVariablesForGC.cpp#L61 [3] https://github.com/eclipse-openj9/openj9/blob/34eacb42356a4cfbfbedfce412df7cc276cd3770/runtime/compiler/codegen/J9CodeGenerator.cpp#L2175
This issue needs more investigation to ensure we understand the problem and the implemented fix correctly.