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.