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).