Skip to content

Proper loop induced clone detection

rarbore2 requested to merge clone_detection6 into main
  • 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.

Merge request reports

Loading