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.

hercules_ir/src/dom.rs

@@ -77,6 +77,26 @@ impl DomTree {
         .1
     }
 
+    /*
+     * Find the node with the shallowest level in the dom tree amongst the nodes
+     * given.
+     */
+    pub fn shallowest_amongst<I>(&self, x: I) -> NodeID
+    where
+        I: Iterator<Item = NodeID>,
+    {
+        x.map(|x| {
+            if x == self.root {
+                (0, x)
+            } else {
+                (self.idom[&x].0, x)
+            }
+        })
+        .min_by(|x, y| x.0.cmp(&y.0))
+        .unwrap()
+        .1
+    }
+
     /*
      * Find the least common ancestor in the tree of two nodes. This is an
      * ancestor of the two nodes that is as far down the tree as possible.