slyubomirsky opened a new pull request, #15689: URL: https://github.com/apache/tvm/pull/15689
As part of #15319, this PR implements liveness analysis, which is implemented using a dataflow analysis framework similar to that described by Adrian Sampson in these lecture notes: https://www.cs.cornell.edu/courses/cs6120/2020fa/lesson/4/. See also Chapter 5 of [Static Program Analysis](https://cs.au.dk/~amoeller/spa/spa.pdf) by Møller and Schwartzbach. This required, for good or ill, introducing quite a bit of infrastructure. Here is a summary: * A control flow graph representation, representing a function in terms of bindings (which maps closely to the notion of bindings within Relax's AST, but we also need to represent the `body` field of `SeqExpr`s and we have to consider the condition, true branch, false branch, and the merge point at the end of an `If` node, so the mapping is not one-to-one). * An implementation of the general dataflow framework from the sources listed. * An implementation of liveness analysis using Sampson's approach (which ended up being very compact thanks to the dataflow framework). The liveness analysis results are given in terms of a set of live variables per node in the control flow graph. A helper function is included for mapping between the AST and the CFG. I highly encourage review, since I am a bit nervous about introducing new infrastructure; I am especially concerned about having clear naming (I am worried about having a name so close to the dataflow pattern matching). I felt it was unavoidable in this case, because there does not seem to be any other way for us to annotate program locations with liveness information. However, I am very glad to have implemented the general dataflow framework, since it could also be used for alias analysis and likely further analyses down the line. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
