[RFC] Program Analysis Framework in Relay

[gussmith23]

Please also see #3895, which is @MarisaKirisame's RFC around a specific change to support analyses in Relay.

This RFC pertains to building a centralized, comprehensive program analysis framework in Relay. I see two primary uses of program analyses in Relay: for generating analysis data used by the compiler, to do things such as quantization, and for generating human-readable data used by developers, useful for exploring Relay programs. Whereas Marisa's request pertains more to the first use-case, this request is inspired by the second use-case, and motivated by a desire to build a framework that covers both use-cases. Such frameworks exist -- see LLVM's framework, which is designed to generate data useful to both the compiler and the developer.

I built a small analysis framework for Relay this past summer at Microsoft, useful for building human-readable analyses of Relay programs. A demo of this framework can be found here, on my branch of TVM.

These are features I developed in my simple framework:

• Utilities for exporting analysis results into some more useful format (e.g. pandas)
  • I achieve this in my simple framework by giving utilities which: (1) extract "columns" out of the resulting analysis data and (2) convert analysis data into a record-based format which can be imported into pandas.
• A consistent format for the resulting analysis data, allowing for analyses to be composed and to depend on the outputs of previous analyses.
  • In my framework, analysis data is simply structured into a dictionary-of-dictionaries in Python, where keys are strings representing column/column-group names.
• A helper class for doing simple static dataflow analysis, built on Relay's ExprVisitor.

These are features which could be considered for a full framework:

• Useful for building compiler analysis passes and analysis passes which generate human-readable data
• The ability to do dynamic analysis of programs
  • There is some exploration of this in the demo linked above
• Integration with the Pass Manager, so that dependencies between analyses can be explicit
  • Also so that analyses can be registered and discovered
• Utilities for doing control-flow analyses
• One or more "right ways" of building analyses. These methods of building analyses should be flexible, so as not to limit the power of analyses, but they should enforce a general structure to analyses so that
  • Analyses can compose with each other easily
  • Analyses are readable and maintainable, once you understand the "right ways" to build them.
• It should be quick to write new analyses
• Utilities for pulling data out of analyses

These are open questions that I have:

• What examples of "ad-hoc" program analyses exist in Relay? #3895 lists some.
• What features are needed by compiler analyses?

I'm posting this in advance of the TVM conference this year, as I'm doing a lighting talk on program analysis in Relay and am hoping that the talk generates some discussion.

[zackcquic]

Hi @gussmith23:

I just start playing with TVM this year. I think this is very useful to me.

I'm posting this in advance of the TVM conference this year, as I'm doing a lighting talk on program analysis in Relay and am hoping that the talk generates some discussion.

Do you keep the link? I'd like to know more details.

I am wondering if you have plan to make this upstream to TVM? Seems this RFC didn't updated for a long time.

[masahi]

I assume this is no longer active.