Bug fixes for CCP

Two fixes to CCP

1. Delay deletion of branches with a constant condition so all unreachable nodes (including these conditions and their projections) are deleted together to avoid leaving uses of deleted nodes.
2. Compute reachability of data nodes as the join of the reachability of its uses so that data nodes in unreachable parts of code are marked unreachable.

hercules_opt/src/ccp.rs

@@ -53,6 +53,19 @@ impl CCPLattice {
     }
 }
 
+impl ReachabilityLattice {
+    // We define join for the reachability lattice as for data nodes we join the reachability of
+    // its uses since it is unreachable if any of its uses are unreachable
+    fn join(a: &Self, b: &Self) -> Self {
+        match (a, b) {
+            (ReachabilityLattice::Reachable, ReachabilityLattice::Reachable) => {
+                ReachabilityLattice::Reachable
+            }
+            _ => ReachabilityLattice::Unreachable,
+        }
+    }
+}
+
 impl ConstantLattice {
     fn is_top(&self) -> bool {
         *self == ConstantLattice::Top
@@ -274,11 +287,10 @@ pub fn ccp(editor: &mut FunctionEditor, reverse_postorder: &Vec<NodeID>) {
                     // Replace all uses of the single reachable user with the node preceeding the
                     // branch node
                     edit = edit.replace_all_uses(the_reachable_user, control)?;
-                    // Delete all users and the branch node
-                    for user in users {
-                        edit = edit.delete_node(user)?;
-                    }
-                    edit.delete_node(branch_id)
+                    // Mark the reachable user and the branch as unreachable so they'll be deleted
+                    unreachable.insert(the_reachable_user);
+                    unreachable.insert(branch_id);
+                    Ok(edit)
                 });
             }
         }
@@ -629,7 +641,7 @@ fn ccp_flow_function(
             };
 
             CCPLattice {
-                reachability: ReachabilityLattice::meet(left_reachability, right_reachability),
+                reachability: ReachabilityLattice::join(left_reachability, right_reachability),
                 constant: new_constant,
             }
         }
@@ -682,9 +694,9 @@ fn ccp_flow_function(
             };
 
             CCPLattice {
-                reachability: ReachabilityLattice::meet(
+                reachability: ReachabilityLattice::join(
                     first_reachability,
-                    &ReachabilityLattice::meet(second_reachability, third_reachability),
+                    &ReachabilityLattice::join(second_reachability, third_reachability),
                 ),
                 constant: new_constant,
             }
@@ -696,13 +708,13 @@ fn ccp_flow_function(
             dynamic_constants: _,
             args,
         } => CCPLattice {
-            reachability: args.iter().fold(ReachabilityLattice::top(), |val, id| {
-                ReachabilityLattice::meet(&val, &inputs[id.idx()].reachability)
+            reachability: args.iter().fold(ReachabilityLattice::bottom(), |val, id| {
+                ReachabilityLattice::join(&val, &inputs[id.idx()].reachability)
             }),
             constant: ConstantLattice::bottom(),
         },
         Node::IntrinsicCall { intrinsic, args } => {
-            let mut new_reachability = ReachabilityLattice::top();
+            let mut new_reachability = ReachabilityLattice::bottom();
             let mut new_constant = ConstantLattice::top();
             let mut constants = vec![];
             let mut all_constants = true;
@@ -713,7 +725,7 @@ fn ccp_flow_function(
                     ref constant,
                 } = inputs[arg.idx()];
 
-                new_reachability = ReachabilityLattice::meet(&new_reachability, reachability);
+                new_reachability = ReachabilityLattice::join(&new_reachability, reachability);
                 new_constant = ConstantLattice::meet(&new_constant, constant);
 
                 if let ConstantLattice::Constant(constant) = constant {
@@ -908,14 +920,14 @@ fn ccp_flow_function(
             data,
             indices,
         } => {
-            let mut reachability = ReachabilityLattice::meet(
+            let mut reachability = ReachabilityLattice::join(
                 &inputs[collect.idx()].reachability,
                 &inputs[data.idx()].reachability,
             );
             for index in indices.iter() {
                 if let Index::Position(positions) = index {
                     for position in positions.iter() {
-                        reachability = ReachabilityLattice::meet(
+                        reachability = ReachabilityLattice::join(
                             &reachability,
                             &inputs[position.idx()].reachability,
                         );