After several implementation iterations I ended up chosing pretty much the original escape analysis algorithm I described a while ago. All allocation sites in the tree are initially assumed to be captured. In a single pass over the tree we perform liveness analysis on the incoming values of the context, and collect all stores that write a reference into memory. At the end of each trace we look at each PHI instruction and note down in the context slot if it propagates a references allocated in this loop iteration into the context slot (and thus into the next iteration). If so, the entry value of this context slot must not be used anywhere in the tree (which we check with the aforementioned liveness analysis). In a final step we go through all store instructions we collected and flag any allocation site as escaping that has its reference written into a non-captured object.

A slight change from my previous idea is that this final step cannot be done in linear time, because there are no guarantees that we discover that an object escapes before we see a write to it. Instead, we have to either do some breadth-first search, or simply use an iterative algorithm that keeps looping over all writes until no additional escaping objects are found. This latter algorithm is bound by the number of indirections that have to be followed, not by the number of instructions in the program. This example thus would require three passes:


class Rect {
 Point a = new Point();
 Point b = new Point();
}
Rect r = new Rect();


While theoretically quadratic, in practice this algorithm is quasi-linear (C*N).