Struct MergeExpressionsOptimizer

pub(crate) struct MergeExpressionsOptimizer<F: AcirField> {
    resolved_blocks: HashMap<BlockId, BTreeSet<Witness>>,
    modified_gates: HashMap<usize, Opcode<F>>,
    deleted_gates: BTreeSet<usize>,
}

Fields

resolved_blocks: HashMap<BlockId, BTreeSet<Witness>>

modified_gates: HashMap<usize, Opcode<F>>

deleted_gates: BTreeSet<usize>

Implementations

impl<F: AcirField> MergeExpressionsOptimizer<F>

pub(crate) fn new() -> Self

pub(crate) fn eliminate_intermediate_variable( &mut self, circuit: &Circuit<F>, acir_opcode_positions: Vec<usize>, ) -> (Vec<Opcode<F>>, Vec<usize>)

This pass analyzes the circuit and identifies intermediate variables that are only used in two AssertZero opcodes. It then merges the opcode which produces the intermediate variable into the second one that uses it

The first pass maps witnesses to the index of the opcodes using them. Public inputs are not considered because they cannot be simplified. Witnesses used by MemoryInit opcodes are put in a separate map and marked as used by a Brillig call if the memory block is an input to the call.

The second pass looks for AssertZero opcodes having a witness which is only used by another arithmetic opcode. In that case, the opcode with the smallest index is merged into the other one via Gaussian elimination. For instance, if we have ‘w1’ used only by these two opcodes, 5*w2*w3 and w1: w2w3 + 2w2 + w1 + w3 = 0 // This opcode ‘defines’ the variable w1 2w3w4 + w1 + w4 = 0 // which is only used here

For w1 we can say: w1 = -1/2w2w3 - w2 - 1/2*w3

Then we will remove the first one and modify the second one like this: 2w3w4 + w4 - w2 - 1/2w3 - 1/2w2*w3 = 0

This transformation is relevant for Plonk-ish backends although they have a limited width because they can potentially handle expressions with large linear combinations using ‘big-add’ gates.

Pre-condition:

• This pass is only relevant for backends that can handle unlimited width
• CSAT pass should have been run prior to this one.

fn for_each_brillig_input_wit( &self, input: &BrilligInputs<F>, f: impl FnMut(Witness), )

fn for_each_brillig_output_wit( &self, output: &BrilligOutputs, f: impl FnMut(Witness), )

fn witness_inputs(&self, opcode: &Opcode<F>) -> BTreeSet<Witness>

fn merge_expression( target: &Expression<F>, expr: &Expression<F>, w: Witness, ) -> Option<Expression<F>>

fn get_opcode(&self, g: usize, circuit: &Circuit<F>) -> Option<Opcode<F>>

Returns the ‘updated’ opcode at index ‘g’ in the circuit The modifications to the circuits are stored with ‘deleted_gates’ and ‘modified_gates’ These structures are used to give the ‘updated’ opcode. For instance, if the opcode has been deleted inside ‘deleted_gates’, then it returns None.