Alternative version of TypeGeneralizing

[kripken]

In offline discussion we thought it would be useful to compare the current TypeGeneralizing impl with one that does not use the new optimization framework, to get an idea for overheads etc.

This PR reimplements that pass on top of #6105, #6106, #6107, specifically it uses the extracted subtyping discovery logic from Unsubtyping, and on top of that it builds a graph and does a flow on it to find the generalized types.

The existing test has a new run line. Results look right to me, though a few are different as this pass does look into unreachable code (and does not run DCE internally).

Marking as draft as this is just for comparison purposes.

[tlively]

It is definitely nice that this can re-use the logic from unsubtyping. I'll be interested to see if there continue to be no functional differences once I finish the transfer function for the other expressions.

[kripken]

I simplified this code a little by using the ValType lattice from the analysis framework (see last commit). That is, instead of handwritten code that does the GLB, the flow operation here now works on a proper lattice and keeps calling meet until things stabilize on the fixed point.

I think this might be a good approach overall: the formalization of lattices is very nice, and our implementation of them is very nice as well. But we may not always need a full CFG analysis in all passes - in general, it is more efficient to distill the necessary graph to analyze on from the CFG, as GUFA and this pass do.

Perhaps there's a way to use even more of the framework here, that is, not just a lattice but also a more general framework that isn't CFG-oriented, but it receives a general graph?

[tlively]

If you build up a small data structure that you can "interpret" to do the transfer function for each basic block, then you never need to look at the contents of the basic block when evaluating the transfer function, but you can still use the framework. Is that along the lines of what you were thinking?

[kripken]

It was just a vague idea at this point. But more along the lines of a framework with 3 parts:

1. The lattice.
2. The graph building.
3. The graph flowing.

So part 2 could build a graph using a CFG, but that would be only one way to build a graph. Another way is what this pass does now, or what GUFA does. I'm not sure if there is a good way to define a general graph that can include both CFGs and other things in a non-limiting way.

[kripken]

Updated after the new batch of tests landed for TypeGeneralizing.

This matches the output on almost all of them, except for

• CallRef where I don't think we know what we want yet, so I didn't look into it.
• ArrayCopy cases where one reference is null, which is unreachable code anyhow.

The code seems reasonable to me but it could be simplified more. In particular there are some obvious similarities to GUFA, so some kind of framework could be extracted to support them both.

[kripken]

@tlively Just a reminder for both of us that if we plan to look into the new optimization framework again then we should discuss this PR. I think it shows shorter and faster code than the other version of TypeGeneralizing, which suggests the new framework could be improved before we go in depth to use it in more places.

[tlively]

Yes, agreed. Finishing this single optimization with and without the new framework, then comparing the code complexity and performance will be an important first step before using the new framework more broadly.