Optimization for miranda

• Optimize cava and edge detection schedules (CPU schedules are multi-core now).
• Add fork-extend pass to make fork dimensions multiple of some number (closes #28 (closed)).
• Make GCM add extra dimensions to per-thread arrays in fork-joins.
• Make GCM allocate extra memory for calls in parallel, make RT backend use different memories per parallel call.
• Make not finding xdot binary crash the compiler.
• Some misc. fixes.
• Add conv-like fork-join test.

hercules_opt/src/fork_transforms.rs

@@ -695,7 +695,8 @@ pub fn fork_coalesce_helper(
 
         editor.edit(|mut edit| {
             let new_tid = edit.add_node(new_tid);
-            let edit = edit.replace_all_uses(tid, new_tid)?;
+            let mut edit = edit.replace_all_uses(tid, new_tid)?;
+            edit.sub_edit(tid, new_tid);
             Ok(edit)
         });
     }
@@ -915,7 +916,9 @@ pub fn chunk_all_forks_unguarded(
     };
 
     for (fork, _) in fork_join_map {
-        chunk_fork_unguarded(editor, *fork, dim_idx, dc_id, order);
+        if editor.is_mutable(*fork) {
+            chunk_fork_unguarded(editor, *fork, dim_idx, dc_id, order);
+        }
     }
 }
 // Splits a dimension of a single fork join into multiple.
@@ -1598,3 +1601,130 @@ pub fn clean_monoid_reduces(editor: &mut FunctionEditor, typing: &Vec<TypeID>) {
         }
     }
 }
+
+/*
+ * Extends the dimensions of a fork-join to be a multiple of a number and gates
+ * the execution of the body.
+ */
+pub fn extend_all_forks(
+    editor: &mut FunctionEditor,
+    fork_join_map: &HashMap<NodeID, NodeID>,
+    multiple: usize,
+) {
+    for (fork, join) in fork_join_map {
+        if editor.is_mutable(*fork) {
+            extend_fork(editor, *fork, *join, multiple);
+        }
+    }
+}
+
+fn extend_fork(editor: &mut FunctionEditor, fork: NodeID, join: NodeID, multiple: usize) {
+    let nodes = &editor.func().nodes;
+    let (fork_pred, factors) = nodes[fork.idx()].try_fork().unwrap();
+    let factors = factors.to_vec();
+    let fork_succ = editor
+        .get_users(fork)
+        .filter(|id| nodes[id.idx()].is_control())
+        .next()
+        .unwrap();
+    let join_pred = nodes[join.idx()].try_join().unwrap();
+    let ctrl_between = fork != join_pred;
+    let reduces: Vec<_> = editor
+        .get_users(join)
+        .filter_map(|id| nodes[id.idx()].try_reduce().map(|x| (id, x)))
+        .collect();
+
+    editor.edit(|mut edit| {
+        // We can round up a dynamic constant A to a multiple of another dynamic
+        // constant B via the following math:
+        // ((A + B - 1) / B) * B
+        let new_factors: Vec<_> = factors
+            .iter()
+            .map(|factor| {
+                let b = edit.add_dynamic_constant(DynamicConstant::Constant(multiple));
+                let apb = edit.add_dynamic_constant(DynamicConstant::add(*factor, b));
+                let o = edit.add_dynamic_constant(DynamicConstant::Constant(1));
+                let apbmo = edit.add_dynamic_constant(DynamicConstant::sub(apb, o));
+                let apbmodb = edit.add_dynamic_constant(DynamicConstant::div(apbmo, b));
+                edit.add_dynamic_constant(DynamicConstant::mul(apbmodb, b))
+            })
+            .collect();
+
+        // Create the new control structure.
+        let new_fork = edit.add_node(Node::Fork {
+            control: fork_pred,
+            factors: new_factors.into_boxed_slice(),
+        });
+        edit = edit.replace_all_uses_where(fork, new_fork, |id| *id != fork_succ)?;
+        edit.sub_edit(fork, new_fork);
+        let conds: Vec<_> = factors
+            .iter()
+            .enumerate()
+            .map(|(idx, old_factor)| {
+                let tid = edit.add_node(Node::ThreadID {
+                    control: new_fork,
+                    dimension: idx,
+                });
+                let old_bound = edit.add_node(Node::DynamicConstant { id: *old_factor });
+                edit.add_node(Node::Binary {
+                    op: BinaryOperator::LT,
+                    left: tid,
+                    right: old_bound,
+                })
+            })
+            .collect();
+        let cond = conds
+            .into_iter()
+            .reduce(|left, right| {
+                edit.add_node(Node::Binary {
+                    op: BinaryOperator::And,
+                    left,
+                    right,
+                })
+            })
+            .unwrap();
+        let branch = edit.add_node(Node::If {
+            control: new_fork,
+            cond,
+        });
+        let false_proj = edit.add_node(Node::ControlProjection {
+            control: branch,
+            selection: 0,
+        });
+        let true_proj = edit.add_node(Node::ControlProjection {
+            control: branch,
+            selection: 1,
+        });
+        if ctrl_between {
+            edit = edit.replace_all_uses_where(fork, true_proj, |id| *id == fork_succ)?;
+        }
+        let bottom_region = edit.add_node(Node::Region {
+            preds: Box::new([false_proj, if ctrl_between { join_pred } else { true_proj }]),
+        });
+        let new_join = edit.add_node(Node::Join {
+            control: bottom_region,
+        });
+        edit = edit.replace_all_uses(join, new_join)?;
+        edit.sub_edit(join, new_join);
+        edit = edit.delete_node(fork)?;
+        edit = edit.delete_node(join)?;
+
+        // Update the reduces to use phis on the region node to gate their execution.
+        for (reduce, (_, init, reduct)) in reduces {
+            let phi = edit.add_node(Node::Phi {
+                control: bottom_region,
+                data: Box::new([reduce, reduct]),
+            });
+            let new_reduce = edit.add_node(Node::Reduce {
+                control: new_join,
+                init,
+                reduct: phi,
+            });
+            edit = edit.replace_all_uses(reduce, new_reduce)?;
+            edit.sub_edit(reduce, new_reduce);
+            edit = edit.delete_node(reduce)?;
+        }
+
+        Ok(edit)
+    });
+}