Exploratory CPU backend

This MR accomplishes the following:

• Compute anti-dependencies between array reads and writes in IR
• Identify logical array allocations - this identifies the size of each individual allocation, and which nodes use which allocation
• Create an incomplete LLVM IR backend for Hercules IR - uses the Inkwell library
  • Inkwell is not feature complete - we will want to emit IR text manually in the future
• Incorporate anti-dependencies into global code motion
• Various helpers for IR - iterators for dominator tree, types, constants
• Remove bitflip op - just not on an int value
• Improve dot graph layout

The matmul.hir example can now be compiled into LLVM IR. When hooked up with some manually written C, it does a matmul properly.

hercules_codegen/src/antideps.rs

+extern crate hercules_ir;
+
+use self::hercules_ir::def_use::*;
+use self::hercules_ir::ir::*;
+
+/*
+ * Top level function to assemble anti-dependence edges. Returns a list of pairs
+ * 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.
+    let mut antideps = vec![];
+
+    for id in (0..function.nodes.len()).map(NodeID::new) {
+        // We only need to consider array reads and writes.
+        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
+            } else {
+                false
+            }
+        });
+        let mut writes = users.iter().filter(|user| {
+            if let Node::WriteArray {
+                array,
+                index: _,
+                data: _,
+            } = function.nodes[user.idx()]
+            {
+                array == id
+            } else {
+                false
+            }
+        });
+
+        // If there are any writes, compute the anti dependence edges.
+        if let Some(write) = writes.next() {
+            for read in reads {
+                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.");
+    }
+
+    antideps
+}