Prototype ParametricInversion using MethodTable overlay approach from CassetteOverlay.jl

[zenna]

ParametricInversion.jl currently relies on IRTools, Mjolnir, and the generated function trick to implement the inverse pass. This suffers from all of the well-known limitations of that approach:

1. It's unstable -- weird bugs pop out of nowhere
2. The resulting compiled code can be slow due to a propagation of failures of type inference
3. Compile time can be extremely slow and unpredictable

Recently, there have been some suggestions, by people like Oscar Smith and other Julia developers, that using "method overlay tables" could provide a more effective way to implement non-standard interpretations within Julia. I could guess, but am not currently familiar with method overlay tables, but nevertheless, CassetteOverlay.jl is a Cassete.jl near-clone from Shuhei Kadowaki that appears to take this approach under the hood. In doing so, it claims/appears to circumvent some of the above problems, perhaps with a slight loss in expressiveness.

It seems likely to me that the method table approach could be used as a mechanism to implement ParametricInversion. The code is constrained to a single file https://github.com/JuliaDebug/CassetteOverlay.jl/blob/master/src/CassetteOverlay.jl, but of course hooks into the Julia compiler at several points.

The objective of this issue is to implement a modification to ParametricInverison.jl that replaces the generated function approach, with the mechanism deployed by CassetteOverlay

A suggested course of action could be:

1. Implement the absolute minimal implementation that does not use ParametricInversion.jl at all, and only uses the method overlay approach to implement the basic inversion pass on a restricted subset of the language (e.g single-block, only primitive function calls)
2. Extend the implementation to use some of the functionality in ParametricInversion.jl that is not related to the actual IR passes, e.g. to use our set of primitive inversion operators https://github.com/zenna/ParametricInversion.jl/blob/master/src/primitives.jl,
3. Swap out the core inversion/reorientation code in https://github.com/zenna/ParametricInversion.jl/blob/master/src/invert.jl and https://github.com/zenna/ParametricInversion.jl/blob/master/src/reorient.jl

The second objective is to understand the potential and limitations of this approach. Some specific questions:

• Generally, how does the method overlap approach work?
• Currently, ParametricInversion relies on Mjolnir for two reasons (i) to ensure the inversion is done on typed IR, (ii) to take advantage of its constant propagation, because e.g. a = x + 1 requires just an inversion, whereas a = x + y requires a parametric inversion -- and we need to differentiate between the two.
• What are the runtime / compile time performance implications?
• What are the limits on expressivity