Proper loop induced clone detection

• Properly implemented loop induced clone materialization.
  • Finds "fringe" users of a collection inside a loop and phis them back to the beginning of the loop.
  • Adds a clone at the top of the loop to give each iteration a fresh copy, inside the same memory.
  • Basically reconstructs SSA for a loop variable that originally isn't loop carried, but is artificially made to be loop carried.

Oh my this was hard and I'm far from confident that this works in general. It definitely does not work for non-natural loops, those we might as well throw out the window. But, it works on some pretty complicated tests and it works on matmul, so I'll merge for now. Just for my own sanity, I ask that we write benchmarks in general s.t. collection variables are let-bound at the top level and that implicit clones are kept to a minimum. In theory it should work no matter what, and we do need it to since optimizations may do whatever, but let's not tempt fate too much.

This still doesn't handle anti-dependency induced clones, but I've yet to see those in the wild and those are in theory easy, so I'm going to focus on other stuff for now.

requested review from @aaronjc4

assigned to @rarbore2

It sounds like the limitations are fine, especially as long as our main/only front-end is Juno, since Juno only has structured control-flow (and I don't think any of our optimizations would produce non-natural loops from natural loops). Anti-dep clones are definitely possible to generate from Juno but I think generally avoidable, they should only result from explicit clones in Juno which I don't think any of the benchmarks we're looking at require.

approved this merge request

mentioned in commit 350cee4d

merged