Andreas Gal

Mason found a problem with the Singleton Analysis Pass. Objects that were allocated and then written to an array were not correctly flagged as non-singleton. Besides this rather obvious bug I also fixed the way context slots are handled. When trying to write up a formal proof of the algorithm for the PLDI paper I realized that a non-eliminated load from a context kills any and all allocations that flow into that contexts. Previously I was checking at the end of each trace whether allocations flow into a context and killed the allocation there. However, this is not sufficient. Instead, we have to collect for each context all allocations flowing into it along the loop edge and the kill all allocations if we observe a load from the context slot. To do this in linear time we collect a set of allocations flowing into to each context and a list of loads that touch contexts and then resolve and kill allocations after we have seen the entire tree.

The reason that a load kills the singleton properties is that it might see a previous state instead of a freshly initialized value (i.e. 0/0.0/null). The LoadElimination phase eliminates almost all same-iteration reads from a newly allocated objects, so as long an object is only used within the current iteration this will not inhibit the allocation from being detected as singleton. Only reading from it in the next iteration prevents this (because the LoadElimination doesn’t try to eliminate loads from context slots because it doesn’t track which allocations flow into context slots).

I finished today the Singleton Allocation Analysis phase which was the last building block missing to enable Invariant Allocation Hoising (move NEWs out of loops, which is our equivalent of escape-analysis based stack allocation). The SAA pass goes over the tree in forward order and builds an interference graph between context slots and allocation instructions. For this we track all live allocation instructions in a set and add that set to the interference set of a context slot every time it is read. The resulting interference set denots for each slot the allocation instructions that context slot interfers with.

To decide which allocation is singleton (only one instance of it lives in the loop) we have to check two properties. First, if an allocation flows back along the backedge, the context slot it flows into must not flow into another context slot along the backedge in the subsequent iteration. This ensures that we don’t “carry over” instances into future loop iterations. In a second step we then check for each context slot where an allocation flows into along the backedge whether that context slot interfers with said allocation (using the interference graph above). If there is an interference it means that the newly allocated object and the object allocated in the previous iteration are alive at the same time, which precludes the allocation site from being singleton.

Allocations can be moved out of the loop if they are singleton and captured. I updated the Invariant Code Motion phase to do so accordingly. This should significantly speed up our JavaScript JIT which dynamically allocates a ton of small objects inside loops.