Novel escape analysis algorithm for Java

Today I read a very interesting article about escape analysis in Java called Escape Analysis for Object Oriented Languages: Application to Java

I think I have some grasp on how escape analysis works and how it is implemented, but I don't understand how the above algorithm works at all. I have also read two other papers on escape analysis in Java, Escape analysis for Java and Compositional pointer and escape analysis for Java programs. The algorithms in those papers are very similar and I understand on a high-level how they work.

But Blanchet's escape analysis algorithm appears to be completely different and I do not understand it at all. So the question is if someone can explain how his algorithm works? How is it different from "normal" escape analysis algorithms?

(this question comes from Stack Overflow)

Edit: I think I have finally figured out one big difference in Blanchet's algoritm vs the others. He does not build a tree at all and instead just uses forward and backward propagation. Consider this example:

Object foo() {
...
a = c;
a = b.f;
return a;
}


The backward propagation starts at return a; and sees that a is returned, so a escapes. It then goes to line a = b.f; and sees that a is assigned b.f. Since a escapes, b.f also escapes. Next, it looks at a = c; and like before a escapes so c escapes. And so on. This appears to be a big flaw in his algorithm, it overestimates the number of escapees. Because he is not building a reference graph like the other algorithms he cannot see that c doesn't escape at all because of the a = b.f; on the next line. So the algorithm is likely very fast (doesn't build a graph) but not precise enough.

• Have you seen: HotSpot, 4 years younger article with diagrams and code examples with 4 times more pages? I am not sure about the core difference, but does normal escape analysis makes two passes, the second backwards with intermeddiate result as integers? – Evil Oct 12 '17 at 23:47
• I am not sure what is the main question here, is it about how the whole algorithm works? It would be rather big task, and it seems that you understand the similar techniques. So maybe some part of it would suffice (making it more focused)? What implements it is rather off-topic here. Still there are two huge questions, one that require rewriting 16 page article and one comparing to two more. The usual rule is one question per post. Maybe you could strip a bit? – Evil Oct 12 '17 at 23:53
• No, I hadn't seen that article before, thanks. It almost looks like a rewrite of the article he published in 1999. Perhaps that article is easier to read (the first one isn't, imho). Yes, the question is "how does the whole algorithm work?" Especially why it it is different from the ones in the other articles. I don't think the question is to board. – Björn Lindqvist Oct 13 '17 at 15:06