Anti-dependencies rewrite

• Re-write anti-dependencies properly using full dataflow analysis, incorporating new collection information.
• Use anti-dependencies properly in code generation.
  • TODO: figure out how anti-dependencies gets incorporated into GCM.
• Track which nodes mutate collections in collection analysis.
• Skeleton for materialize clones pass.
• Test for anti-dependencies (passes) and for materializing clones (fails).
• Fix pass.rs not clearing a bunch of analyses.

hercules_cg/src/cpu.rs

@@ -27,6 +27,7 @@ pub fn cpu_codegen<W: Write>(
     reverse_postorder: &Vec<NodeID>,
     typing: &Vec<TypeID>,
     control_subgraph: &Subgraph,
+    antideps: &Vec<(NodeID, NodeID)>,
     bbs: &Vec<NodeID>,
     w: &mut W,
 ) -> Result<(), Error> {
@@ -38,6 +39,7 @@ pub fn cpu_codegen<W: Write>(
         reverse_postorder,
         typing,
         control_subgraph,
+        antideps,
         bbs,
     };
     ctx.codegen_function(w)
@@ -51,6 +53,7 @@ struct CPUContext<'a> {
     reverse_postorder: &'a Vec<NodeID>,
     typing: &'a Vec<TypeID>,
     control_subgraph: &'a Subgraph,
+    antideps: &'a Vec<(NodeID, NodeID)>,
     bbs: &'a Vec<NodeID>,
 }
 
@@ -128,6 +131,7 @@ impl<'a> CPUContext<'a> {
                 .filter(|id| !self.function.nodes[id.idx()].is_control()),
         );
         let mut visited = bitvec![u8, Lsb0; 0; self.function.nodes.len()];
+        let antideps = flip_antideps(&self.antideps);
         while let Some(id) = worklist.pop_front() {
             let node = &self.function.nodes[id.idx()];
             if node.is_phi()
@@ -135,7 +139,12 @@ impl<'a> CPUContext<'a> {
                 || get_uses(node)
                     .as_ref()
                     .into_iter()
-                    .all(|u| self.function.nodes[u.idx()].is_control() || visited[u.idx()])
+                    .chain(antideps.get(&id).into_iter().flatten())
+                    .all(|u| {
+                        self.function.nodes[u.idx()].is_control()
+                            || self.bbs[u.idx()] != self.bbs[id.idx()]
+                            || visited[u.idx()]
+                    })
             {
                 self.codegen_data_node(*id, &mut blocks)?;
                 visited.set(id.idx(), true);