Fix CCP assertions

Move the assertions in CCP from the flow-function to after the data-flow has finished. In particular, we check that for each reachable node

• If it is a region node, at least one predecessor is reachable
• If it is a phi node, the control predecessor (region) is reachable and each data input for a reachable predecessor of the region is reachable
• For all other nodes, all uses should be reachable

hercules_opt/src/ccp.rs

@@ -5,6 +5,7 @@ use std::iter::zip;
 
 use self::hercules_ir::dataflow::*;
 use self::hercules_ir::ir::*;
+use self::hercules_ir::def_use::get_uses;
 
 use crate::*;
 
@@ -180,6 +181,39 @@ pub fn ccp(editor: &mut FunctionEditor, reverse_postorder: &Vec<NodeID>) {
         ccp_flow_function(inputs, node_id, editor)
     });
 
+    // Check the results of CCP. In particular we assert that for every reachable node (except for
+    // region and phi nodes) all of its uses are also reachable. For phi nodes we check this
+    // property only on live branches and for regions we check that at least one of its
+    // predecessors is reachable if it is reachable
+    for node_idx in 0..result.len() {
+        if !result[node_idx].is_reachable() {
+            continue;
+        }
+        match &editor.func().nodes[node_idx] {
+            Node::Region { preds } => {
+                assert!(preds.iter().any(|n| result[n.idx()].is_reachable()))
+            }
+            Node::Phi { control, data } => {
+                assert!(result[control.idx()].is_reachable());
+                let region_preds =
+                    if let Node::Region { preds } = &editor.func().nodes[control.idx()] {
+                        preds
+                    } else {
+                        panic!("A phi's control input must be a region node.")
+                    };
+                assert!(zip(region_preds.iter(), data.iter()).all(|(region, data)| {
+                    !result[region.idx()].is_reachable() || result[data.idx()].is_reachable()
+                }));
+            }
+            _ => {
+                assert!(get_uses(&editor.func().nodes[node_idx])
+                    .as_ref()
+                    .iter()
+                    .all(|n| result[n.idx()].is_reachable()));
+            }
+        }
+    }
+
     // Step 2: propagate constants. For each node that was found to have a constant value, we
     // create a node for that constant value, replace uses of the original node with the constant,
     // and finally delete the original node
@@ -380,14 +414,8 @@ fn ccp_flow_function(
         }),
         // If node has only one output, if doesn't directly handle crossover of
         // reachability and constant propagation. Read handles that.
-        Node::If { control, cond } => {
-            assert!(!inputs[control.idx()].is_reachable() || inputs[cond.idx()].is_reachable());
-            inputs[control.idx()].clone()
-        }
-        Node::Match { control, sum } => {
-            assert!(!inputs[control.idx()].is_reachable() || inputs[sum.idx()].is_reachable());
-            inputs[control.idx()].clone()
-        }
+        Node::If { control, cond } => inputs[control.idx()].clone(),
+        Node::Match { control, sum } => inputs[control.idx()].clone(),
         Node::Fork {
             control,
             factors: _,
@@ -426,7 +454,6 @@ fn ccp_flow_function(
             control,
             dimension: _,
         } => inputs[control.idx()].clone(),
-        // TODO: At least for now, reduce nodes always produce unknown values.
         Node::Reduce {
             control,
             init,
@@ -434,7 +461,6 @@ fn ccp_flow_function(
         } => {
             let reachability = inputs[control.idx()].reachability.clone();
             if reachability == ReachabilityLattice::Reachable {
-                assert!(inputs[init.idx()].is_reachable());
                 let mut constant = inputs[init.idx()].constant.clone();
                 if inputs[reduct.idx()].is_reachable() {
                     constant = ConstantLattice::meet(&constant, &inputs[reduct.idx()].constant);