Skip to content
Snippets Groups Projects

Proper loop induced clone detection

Merged Proper loop induced clone detection
clone_detection6 into main
Merged rarbore2 requested to merge clone_detection6 into main
Viewing commit d190f629
Prev Next
Show latest version
2 files
+ 175
− 176
Compare changes
  • Side-by-side
  • Inline
Files
2
hercules_opt/src/legalize_reference_semantics.rs
+ 174
− 176
@@ -724,199 +724,197 @@ fn materialize_clones(
@@ -724,199 +724,197 @@ fn materialize_clones(
// Helper to induce a clone when an implicit clone is identified.
// Helper to induce a clone when an implicit clone is identified.
let nodes = nodes.clone();
let nodes = nodes.clone();
let mut induce_clone =
let mut induce_clone = |object: NodeID,
|object: NodeID, user: NodeID, value: &BTreeMap<NodeID, BTreeSet<NodeID>>| {
user: NodeID,
// If `user` already used `object` and tries to use it again, then the
value: &BTreeMap<NodeID, BTreeSet<NodeID>>| {
// clone is a "loop induced" clone. Otherwise, it's a simple clone.
// If `user` already used `object` and tries to use it again, then the
if !value[&object].contains(&user) {
// clone is a "loop induced" clone. Otherwise, it's a simple clone.
let success = editor.edit(|mut edit| {
if !value[&object].contains(&user) {
// Create the constant collection object for allocation.
let success = editor.edit(|mut edit| {
let object_ty = typing[object.idx()];
// Create the constant collection object for allocation.
let object_cons = edit.add_zero_constant(object_ty);
let object_ty = typing[object.idx()];
let cons_node = edit.add_node(Node::Constant { id: object_cons });
let object_cons = edit.add_zero_constant(object_ty);
 
let cons_node = edit.add_node(Node::Constant { id: object_cons });
// Create the clone into the new constant collection.
// Create the clone into the new constant collection.
let clone_node = edit.add_node(Node::Write {
let clone_node = edit.add_node(Node::Write {
collect: cons_node,
collect: cons_node,
data: object,
data: object,
indices: vec![].into_boxed_slice(),
indices: vec![].into_boxed_slice(),
});
// Make user use the cloned object.
edit.replace_all_uses_where(object, clone_node, |id| *id == user)
});
assert!(success);
} else {
// Figure out where to place that phi. This is the deepest
// loop header where `user` is responsible for making `object` used
// used at the top of the block, and the block dominates the block
// containing `user`. If `user` is a phi, then the region it's
// attached to is excluded from eligibility.
let eligible_blocks = rev_po.iter().map(|bb| *bb).filter(|bb| {
lattice[bb_to_prefix_sum[bb.idx()]]
.get(&object)
.unwrap_or(&BTreeSet::new())
.contains(&user)
&& dom.does_dom(*bb, bbs.0[user.idx()])
&& loops.contains(*bb)
&& loops.is_in_loop(*bb, bbs.0[user.idx()])
&& (!editor.func().nodes[user.idx()].is_phi() || *bb != bbs.0[user.idx()])
});
});
let top_block = eligible_blocks
.max_by_key(|bb| loops.nesting(*bb).unwrap())
.unwrap();
assert!(editor.func().nodes[top_block.idx()].is_region());
// Figure out the users of `object` that we need to phi back
// Make user use the cloned object.
// upwards. Assign each user a number indicating how far down the
edit.replace_all_uses_where(object, clone_node, |id| *id == user)
// user chain it is, higher is farther down. This is used for
});
// picking the most downstream user later.
assert!(success);
let mut users: BTreeMap<NodeID, usize> = BTreeMap::new();
} else {
let mut workset: BTreeSet<NodeID> = BTreeSet::new();
// Figure out where to place that phi. This is the deepest
workset.insert(object);
// loop header where `user` is responsible for making `object` used
let mut chain_ordering = 1;
// used at the top of the block, and the block dominates the block
while let Some(pop) = workset.pop_first() {
// containing `user`. If `user` is a phi, then the region it's
let iterated_users: BTreeSet<_> = super_value
// attached to is excluded from eligibility.
.get(&pop)
let eligible_blocks = rev_po.iter().map(|bb| *bb).filter(|bb| {
.map(|users| users.into_iter())
lattice[bb_to_prefix_sum[bb.idx()]]
.into_iter()
.get(&object)
.flatten()
.unwrap_or(&BTreeSet::new())
.map(|id| *id)
.contains(&user)
.filter(|iterated_user| {
&& dom.does_dom(*bb, bbs.0[user.idx()])
loops.is_in_loop(top_block, bbs.0[iterated_user.idx()])
&& loops.contains(*bb)
&& dom.does_dom(bbs.0[pop.idx()], bbs.0[iterated_user.idx()])
&& loops.is_in_loop(*bb, bbs.0[user.idx()])
})
&& (!editor.func().nodes[user.idx()].is_phi() || *bb != bbs.0[user.idx()])
.collect();
});
workset.extend(iterated_users.iter().filter(|id| !users.contains_key(id)));
let top_block = eligible_blocks
for user in iterated_users {
.max_by_key(|bb| loops.nesting(*bb).unwrap())
*users.entry(user).or_default() = chain_ordering;
.unwrap();
chain_ordering += 1;
assert!(editor.func().nodes[top_block.idx()].is_region());
}
 
// Figure out the users of `object` that we need to phi back
 
// upwards. Assign each user a number indicating how far down the
 
// user chain it is, higher is farther down. This is used for
 
// picking the most downstream user later.
 
let mut users: BTreeMap<NodeID, usize> = BTreeMap::new();
 
let mut workset: BTreeSet<NodeID> = BTreeSet::new();
 
workset.insert(object);
 
let mut chain_ordering = 1;
 
while let Some(pop) = workset.pop_first() {
 
let iterated_users: BTreeSet<_> = super_value
 
.get(&pop)
 
.map(|users| users.into_iter())
 
.into_iter()
 
.flatten()
 
.map(|id| *id)
 
.filter(|iterated_user| loops.is_in_loop(top_block, bbs.0[iterated_user.idx()]))
 
.collect();
 
workset.extend(iterated_users.iter().filter(|id| !users.contains_key(id)));
 
for user in iterated_users {
 
*users.entry(user).or_default() = chain_ordering;
 
chain_ordering += 1;
}
}
 
}
// The fringe users may not dominate any predecessors of the loop
// The fringe users may not dominate any predecessors of the loop
// header. The following is some Juno code that exposes this:
// header. The following is some Juno code that exposes this:
//
//
// fn problematic(a : size) -> i32 {
// fn problematic(a : size) -> i32 {
// for i = 0 to a {
// for i = 0 to a {
// let arr : i32[1];
// let arr : i32[1];
// for j = 0 to a {
// for j = 0 to a {
// arr[0] = 1;
// arr[0] = 1;
// }
// }
// }
// }
// return 0;
// return 0;
// }
// }
//
//
// Note that `arr` induces a clone each iteration, since its value
// Note that `arr` induces a clone each iteration, since its value
// needs to be reset to all zeros. However, it should also be noted
// needs to be reset to all zeros. However, it should also be noted
// that the most fringe user of `arr`, the write inside the inner
// that the most fringe user of `arr`, the write inside the inner
// loop, does not dominate the bottom of the outer loop. Thus, we
// loop, does not dominate the bottom of the outer loop. Thus, we
// need to insert a phi in the bottom block of the outer loop to
// need to insert a phi in the bottom block of the outer loop to
// retrieve either the write, or `arr` before the inner loop. The
// retrieve either the write, or `arr` before the inner loop. The
// general version of this problem requires the following solution.
// general version of this problem requires the following solution.
// Our goal is to figure out which downstream user represents
// Our goal is to figure out which downstream user represents
// `object` at each block in the loop. We first assign each block
// `object` at each block in the loop. We first assign each block
// containing a user the most downstream user it contains. Then, we
// containing a user the most downstream user it contains. Then, we
// create a dummy phi for every region (including the header) in the
// create a dummy phi for every region (including the header) in the
// loop, which is the downstream user for that block. Then, every
// loop, which is the downstream user for that block. Then, every
// other block is assigned the downstream user of its single
// other block is assigned the downstream user of its single
// predecessor. This basically amounts to recreating SSA for
// predecessor. This basically amounts to recreating SSA for
// `object` inside the loop.
// `object` inside the loop.
let mut user_per_loop_bb = BTreeMap::new();
let mut user_per_loop_bb = BTreeMap::new();
let mut added_phis = BTreeMap::new();
let mut added_phis = BTreeMap::new();
let mut top_phi = NodeID::new(0);
let mut top_phi = NodeID::new(0);
// Assign existing users.
// Assign existing users.
for (user, ordering) in users.iter() {
for (user, ordering) in users.iter() {
let bb = bbs.0[user.idx()];
let bb = bbs.0[user.idx()];
if let Some(old_user) = user_per_loop_bb.get(&bb)
if let Some(old_user) = user_per_loop_bb.get(&bb)
&& users[old_user] > *ordering
&& users[old_user] > *ordering
{
{
} else {
} else {
user_per_loop_bb.insert(bb, *user);
user_per_loop_bb.insert(bb, *user);
}
}
}
// Assign dummy phis.
}
for bb in loops.nodes_in_loop(top_block) {
// Assign dummy phis.
if (!user_per_loop_bb.contains_key(&bb) || bb == top_block)
for bb in loops.nodes_in_loop(top_block) {
&& editor.func().nodes[bb.idx()].is_region()
if (!user_per_loop_bb.contains_key(&bb) || bb == top_block)
{
&& editor.func().nodes[bb.idx()].is_region()
let success = editor.edit(|mut edit| {
{
let phi_node = edit.add_node(Node::Phi {
let success = editor.edit(|mut edit| {
control: bb,
let phi_node = edit.add_node(Node::Phi {
data: empty().collect(),
control: bb,
});
data: empty().collect(),
if bb != top_block || !user_per_loop_bb.contains_key(&bb) {
user_per_loop_bb.insert(bb, phi_node);
}
if bb == top_block {
top_phi = phi_node;
}
added_phis.insert(phi_node, bb);
Ok(edit)
});
});
assert!(success);
if bb != top_block || !user_per_loop_bb.contains_key(&bb) {
}
user_per_loop_bb.insert(bb, phi_node);
 
}
 
if bb == top_block {
 
top_phi = phi_node;
 
}
 
added_phis.insert(phi_node, bb);
 
Ok(edit)
 
});
 
assert!(success);
}
}
// Assign users for the rest of the blocks.
}
for bb in rev_po.iter().filter(|bb| loops.is_in_loop(top_block, **bb)) {
// Assign users for the rest of the blocks.
if !user_per_loop_bb.contains_key(&bb) {
for bb in rev_po.iter().filter(|bb| loops.is_in_loop(top_block, **bb)) {
assert!(control_subgraph.preds(*bb).count() == 1);
if !user_per_loop_bb.contains_key(&bb) {
user_per_loop_bb.insert(
assert!(control_subgraph.preds(*bb).count() == 1);
*bb,
user_per_loop_bb.insert(
user_per_loop_bb[&control_subgraph.preds(*bb).next().unwrap()],
*bb,
);
user_per_loop_bb[&control_subgraph.preds(*bb).next().unwrap()],
}
);
}
}
 
}
// Induce the clone.
// Induce the clone.
let success = editor.edit(|mut edit| {
let success = editor.edit(|mut edit| {
// Create the constant collection object for allocation.
// Create the constant collection object for allocation.
let object_ty = typing[object.idx()];
let object_ty = typing[object.idx()];
let object_cons = edit.add_zero_constant(object_ty);
let object_cons = edit.add_zero_constant(object_ty);
let cons_node = edit.add_node(Node::Constant { id: object_cons });
let cons_node = edit.add_node(Node::Constant { id: object_cons });
// Create the phis.
// Create the phis.
let mut real_phis = BTreeMap::new();
let mut real_phis = BTreeMap::new();
for (dummy, bb) in added_phis {
for (dummy, bb) in added_phis {
let real = edit.add_node(Node::Phi {
let real = edit.add_node(Node::Phi {
control: bb,
control: bb,
data: control_subgraph
data: control_subgraph
.preds(bb)
.preds(bb)
.map(|pred| *user_per_loop_bb.get(&pred).unwrap_or(&cons_node))
.map(|pred| *user_per_loop_bb.get(&pred).unwrap_or(&cons_node))
.collect(),
.collect(),
});
real_phis.insert(dummy, real);
}
// Create the clone into the phi.
let clone_node = edit.add_node(Node::Write {
collect: real_phis[&top_phi],
data: object,
indices: vec![].into_boxed_slice(),
});
});
 
real_phis.insert(dummy, real);
 
}
// Make user use the cloned object.
// Create the clone into the phi.
edit = edit.replace_all_uses_where(object, clone_node, |id| {
let clone_node = edit.add_node(Node::Write {
id.idx() < bbs.0.len() && loops.is_in_loop(top_block, bbs.0[id.idx()])
collect: real_phis[&top_phi],
})?;
data: object,
 
indices: vec![].into_boxed_slice(),
 
});
// Get rid of the dummy phis.
// Make users use the cloned object.
for (dummy, real) in real_phis {
edit = edit.replace_all_uses_where(object, clone_node, |id| {
edit = edit.replace_all_uses(dummy, real)?;
id.idx() < bbs.0.len() && loops.is_in_loop(top_block, bbs.0[id.idx()])
edit = edit.delete_node(dummy)?;
})?;
}
Ok(edit)
// Get rid of the dummy phis.
});
for (dummy, real) in real_phis {
assert!(success);
edit = edit.replace_all_uses(dummy, real)?;
 
edit = edit.delete_node(dummy)?;
 
}
// De-duplicate phis.
Ok(edit)
gvn(editor, false);
});
 
assert!(success);
// Get rid of unused phis.
// De-duplicate phis.
dce(editor);
gvn(editor, false);
}
};
// Get rid of unused phis.
 
dce(editor);
 
}
 
};
// Now that we've computed the used collections dataflow analysis, use the
// Now that we've computed the used collections dataflow analysis, use the
// results to materialize a clone whenever a node attempts to use an already
// results to materialize a clone whenever a node attempts to use an already