IR development

• Nested array types
• Read / write node consolidation
• Reduce node in fork-joins
• Textual LLVM IR emitting in beta version of CPU codegen
• Generalize anti-dependence analysis routine
• Change some IR APIs

hercules_cg/src/antideps.rs

@@ -8,32 +8,38 @@ use self::hercules_ir::ir::*;
  * of nodes. The first item in the pair is the read node, and the second item is
  * the write node.
  */
-pub fn antideps(function: &Function, def_use: &ImmutableDefUseMap) -> Vec<(NodeID, NodeID)> {
-    // Array typed values are not directly computed on. Thus, there are actually
-    // very few nodes that have array inputs or output. As a result, when
-    // forming anti-dependencies for a single allocation, we only need to
-    // consider immediate users that are read or write nodes - no proper
-    // dataflow analysis necessary.
+pub fn antideps<I: Iterator<Item = NodeID>>(
+    function: &Function,
+    def_use: &ImmutableDefUseMap,
+    nodes: I,
+) -> Vec<(NodeID, NodeID)> {
+    // Anti-dependence edges are between a write node and a read node, where
+    // each node uses the same array value. The read must be scheduled before
+    // the write to avoid incorrect compilation.
     let mut antideps = vec![];
 
-    for id in (0..function.nodes.len()).map(NodeID::new) {
-        // We only need to consider array reads and writes.
+    for id in nodes {
+        // Collect the reads and writes to / from this collection.
         let users = def_use.get_users(id);
         let reads = users.iter().filter(|user| {
-            if let Node::ReadArray { array, index: _ } = function.nodes[user.idx()] {
-                array == id
+            if let Node::Read {
+                collect,
+                indices: _,
+            } = function.nodes[user.idx()]
+            {
+                collect == id
             } else {
                 false
             }
         });
         let mut writes = users.iter().filter(|user| {
-            if let Node::WriteArray {
-                array,
-                index: _,
+            if let Node::Write {
+                collect,
                 data: _,
+                indices: _,
             } = function.nodes[user.idx()]
             {
-                array == id
+                collect == id
             } else {
                 false
             }
@@ -45,8 +51,28 @@ pub fn antideps(function: &Function, def_use: &ImmutableDefUseMap) -> Vec<(NodeI
                 antideps.push((*read, *write));
             }
         }
-        assert!(writes.next() == None, "Can't form anti-dependencies when there are two independent writes depending on a single array value.");
+
+        // TODO: Multiple write uses should clone the collection for N - 1 of the writes.
+        assert!(writes.next() == None, "Can't form anti-dependencies when there are two independent writes depending on a single collection value.");
     }
 
     antideps
 }
+
+/*
+ * Sometimes, we are only interested in anti-dependence edges involving arrays.
+ */
+pub fn array_antideps(
+    function: &Function,
+    def_use: &ImmutableDefUseMap,
+    types: &Vec<Type>,
+    typing: &Vec<TypeID>,
+) -> Vec<(NodeID, NodeID)> {
+    antideps(
+        function,
+        def_use,
+        (0..function.nodes.len())
+            .map(NodeID::new)
+            .filter(|id| types[typing[id.idx()].idx()].is_array()),
+    )
+}