Perform early dead gate elimination for unreachable branches

[robinhundt]

Compiling the following program will take a long time, irrespective of whether THRESHOLD is > 5 or not. This is due to Garble compiling both branches of the if expressions and then removing the not taken branch when the ouputs are MUXed with a constant selection bit.

const THRESHOLD: u8 = PARTY_0::THRESHOLD;

pub fn main(a: u64, b: u64) -> u64 {
  if THRESHOLD  > 5 {
    slow_computation()
  } else {
    fast_computation()
  }
}

fn slow_computation(a: u64, b: u64) -> u64 {
  // compute a * b in a really slow way, with many gates
  // maybe by doing a + a + .. + a for b times
}

fn fast_computation(a: u64, b: u64) -> u64 {
  a * b
}

For cases where only the fast to compile branch is actually taken, the compilation of the whole program could be severely improved by eliminating the not-taken branch before it is actually compiled. In the compilation of the ExprEnum::If, we could check whether the condition compiles to a constant 0 or 1 (this should work, as constant folding is done eagerly during compilation) and only compile both branches if it is not a constant.

garble-lang/src/compile.rs

Lines 1153 to 1178 in 4b0ebd7

	ExprEnum::If(condition, case_true, case_false) => {
	let condition = condition.compile(prg, env, circuit);
	let panic_before_branches = circuit.peek_panic().clone();
	assert_eq!(condition.len(), 1);
	let condition = condition[0];
	let mut env_if_true = env.clone();
	let mut env_if_false = env.clone();
	let case_true = case_true.compile(prg, &mut env_if_true, circuit);
	let panic_if_true = circuit.replace_panic_with(panic_before_branches.clone());
	let case_false = case_false.compile(prg, &mut env_if_false, circuit);
	let panic_if_false = circuit.replace_panic_with(panic_before_branches);
	*env = circuit.mux_envs(condition, env_if_true, env_if_false);
	let muxed_panic = circuit.mux_panic(condition, &panic_if_true, &panic_if_false);
	circuit.replace_panic_with(muxed_panic);
	assert_eq!(case_true.len(), case_false.len());
	let mut gate_indexes = Vec::with_capacity(case_true.len());
	for i in 0..case_true.len() {
	gate_indexes.push(circuit.push_mux(condition, case_true[i], case_false[i]));
	}
	gate_indexes

See measles.garble.rs for a more realistic program where this compilation time blowup occurs.

Open questions:

• Can this also be done with other branching constructs like match expressions?