Join GitHub today
GitHub is home to over 28 million developers working together to host and review code, manage projects, and build software together.Sign up
cmd/compile: better escape analysis documentation #23109
Despite repeated efforts, I'm still confused by our escape analysis code. Also, based on discussion with other compiler devs, apparently this difficulty understanding is not unique to me. It would be good to better document this code so we can hopefully simplify and improve it.
Some specific questions I've had trying to understand the code:
If I understand correctly, the example assumes there is a type
The reflooding is added in CL https://go-review.googlesource.com/c/go/+/30693. Its CL description explains it. Probably we should add this as a comment.
pushed a commit
Jun 26, 2018
Over the weekend, I reimplemented a basic variant of esc.go's escape analysis logic, and now I better understand how it works in practice and what the documentation is explaining.
One thing I still don't understand though is the handling of recursive functions. In particular, this bit:
It looks like in esccall that we handle recursive calls, including wiring their return values into the flow graph correctly (look for "function in same mutually recursive group. Incorporate into flow graph").
I tried disabling this code by adding
This code comes from CL 6741044 (507fcf3). It's true that before that CL we lost track of the return values in mutually recursive function calls, but the CL appears to have added both. So maybe the "if e.recursive" logic was written first, then lvd@ decided to fix the return value tracking, but forgot to remove the original (now unnecessary) fix?
When I was working on this and thought I understood it, the recursive punt seemed necessary.
I also don't know that this is that worthwhile; I took a stab at handling recursion and even had a CL for it that I somewhat trusted, and it avoided practically no heap allocations, so I didn't pursue it. The problem is that if anything escapes, the this-field-versus-that-field precision is lacking, and so everything escapes.
I am however very interested in any writeup you can put together, because the algorithm is a real pain to understand.
So here's the basic idea I understand:
Escape analysis treats the control flow graph as a bunch of locations, and assignments between them. Individual assignments can involve addressing or an arbitrary number of dereferences. For example:
Assignments can also be to the "sink" (basically, the Go heap).
All Go language constructs can be lowered into this assignment graph. For example,
can be represented as
Assignments to global variables, through pointers, passing arguments to unknown functions, etc. are recorded as assignments to the sink. Also, if q has a greater loop depth than p, then
This is an imprecise but conservative representation of data flow.
As an optimization, the Go source might lower into multiple edges between the same two locations; it's only necessary to track the shortest edge.
Once we have a graph representing one or more functions, we can walk the graph to compute each node's "distance" from the sink and from any return parameters. This is basically just a bunch of shortest-path computations, except that distance is bounded as non-negative. For example, if p has distance 0 from some location, and there's an edge
Finally, we can observe two things from the resulting distance computations:
Notably, esc.go doesn't exactly follow this approach. Instead of simply constructing a graph and walking it as I describe above, escassign/escflow construct a partial graph (synthesizing OADDR/ODEREF nodes in lieu of tracking edge lengths directly) and escflood/escwalk walk the remaining edges. The subsequent computations based on the distance calculations are also intermingled into the walking logic, and tracking/recording distances is much more complicated.
As an update, I have a WIP branch where I've written a new escape analysis pass. You can see the new code here: https://github.com/mdempsky/go/blob/esc5/src/cmd/compile/internal/gc/esc2.go
It's still a little rough and I need to add documentation and better debugging facilities. (The latter being mostly ad hocly developed while I bring it up to feature parity with esc.go.)
However, I believe it's about on par with esc.go in terms of correctness, and it's less than half the number of lines of code (1117 vs 2425).
It roughly follows the description I made above: the stmts/stmt/value/assign/call methods all trudge through the AST tracking pointer flows and constructing a graph of EscLocations, and then flood+walk do a simple walk over the graph identifying locations that escape and value flows from pointers to result parameters.
The graphs it builds also tend to be much smaller than esc.go's. For example:
esc2.go only needed about 40% as many graph nodes as esc.go, and about 80% as many edges. There's room for further improvement here too.
My next immediate goal is continuing to dig through the differences in behavior between esc.go and esc2.go, and then polishing it up for review for the next dev cycle.