Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Check whether check_for_negated_jmpif_condition optimization would benefit ACIR functions. #6624

Open
TomAFrench opened this issue Nov 26, 2024 · 0 comments

Comments

@TomAFrench
Copy link
Member

In #5891 we started swapping the then and else branches of if-else statements in brillig functions if the if condition was being negated. Due to some issues with the flattening pass we didn't apply this optimization to ACIR functions.

The CFG allows querying the block in which the two branches will merge again:

pub(super) fn find_branch_ends(
function: &Function,
cfg: &ControlFlowGraph,
) -> HashMap<BasicBlockId, BasicBlockId> {
let mut block = function.entry_block();
let mut context = Context::new(cfg);
loop {
let mut successors = cfg.successors(block);
if successors.len() == 2 {
block = context.find_join_point_of_branches(block, successors);
} else if successors.len() == 1 {
block = successors.next().unwrap();
} else if successors.len() == 0 {
// return encountered. We have nothing to join, so we're done
break;
} else {
unreachable!("A block can only have 0, 1, or 2 successors");
}
}
context.branch_ends
}

Using this we can perform some inspection to determine whether we're in a situation where the two blocks merge inside of the else branch (and so swapping the condition would move it to the then branch) or whether it's save to negate the condition.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Status: 📋 Backlog
Development

No branches or pull requests

1 participant