acvm/compiler/optimizers/
mod.rs

1use std::collections::BTreeMap;
2
3use acir::{
4    AcirField,
5    circuit::{Circuit, Opcode, brillig::BrilligFunctionId},
6};
7
8mod common_subexpression;
9mod general;
10mod redundant_range;
11mod unused_memory;
12
13pub(crate) use general::GeneralOptimizer;
14pub(crate) use redundant_range::RangeOptimizer;
15use tracing::info;
16
17use self::unused_memory::UnusedMemoryOptimizer;
18
19use super::{AcirTransformationMap, transform_assert_messages};
20
21/// Applies backend independent optimizations to a [`Circuit`].
22pub fn optimize<F: AcirField>(
23    acir: Circuit<F>,
24    brillig_side_effects: &BTreeMap<BrilligFunctionId, bool>,
25) -> (Circuit<F>, AcirTransformationMap) {
26    // Track original acir opcode positions throughout the transformation passes of the compilation
27    // by applying the modifications done to the circuit opcodes and also to the opcode_positions (delete and insert)
28    // For instance, here before any transformation, the old acir opcode positions have not changed.
29    // So acir_opcode_positions = 0, 1,...,n-1, representing the index of the opcode in Circuit.opcodes vector.
30    let acir_opcode_positions = (0..acir.opcodes.len()).collect();
31
32    // `optimize_internal()` may change the circuit, and it returns a new one, as well the new_opcode_positions
33    // In the new circuit, the opcode at index `i` corresponds to the opcode at index `new_opcode_positions[i]` in the original circuit.
34    // For instance let's say it removed the opcode at index 3, and replaced the one at index 5 by two new opcodes
35    // The new_opcode_positions is now: 0,1,2,4,5,5,6,....n-1
36    let (mut acir, new_opcode_positions) =
37        optimize_internal(acir, acir_opcode_positions, brillig_side_effects);
38
39    let transformation_map = AcirTransformationMap::new(&new_opcode_positions);
40
41    acir.assert_messages = transform_assert_messages(acir.assert_messages, &transformation_map);
42
43    (acir, transformation_map)
44}
45
46/// Applies backend independent optimizations to a [`Circuit`].
47///
48/// Accepts an injected `acir_opcode_positions` to allow optimizations to be applied in a loop.
49/// It run the following passes:
50/// - General optimizer
51/// - Unused Memory optimization
52/// - Redundant Ranges optimization
53#[tracing::instrument(level = "trace", name = "optimize_acir" skip(acir, acir_opcode_positions))]
54pub(super) fn optimize_internal<F: AcirField>(
55    acir: Circuit<F>,
56    acir_opcode_positions: Vec<usize>,
57    brillig_side_effects: &BTreeMap<BrilligFunctionId, bool>,
58) -> (Circuit<F>, Vec<usize>) {
59    if acir.opcodes.len() == 1 && matches!(acir.opcodes[0], Opcode::BrilligCall { .. }) {
60        info!("Program is fully unconstrained, skipping optimization pass");
61        return (acir, acir_opcode_positions);
62    }
63
64    info!("Number of opcodes before: {}", acir.opcodes.len());
65
66    // General optimizer pass: simplify expressions and remove trivially-satisfied constraints.
67    let (opcodes, acir_opcode_positions): (Vec<_>, Vec<_>) = acir
68        .opcodes
69        .into_iter()
70        .zip(acir_opcode_positions)
71        .filter_map(|(opcode, position)| {
72            if let Opcode::AssertZero(arith_expr) = opcode {
73                let optimized = GeneralOptimizer::optimize(arith_expr);
74                if optimized.is_zero() {
75                    return None;
76                }
77                Some((Opcode::AssertZero(optimized), position))
78            } else {
79                Some((opcode, position))
80            }
81        })
82        .unzip();
83    let acir = Circuit { opcodes, ..acir };
84
85    // Unused memory optimization pass
86    let memory_optimizer = UnusedMemoryOptimizer::new(acir);
87    let (acir, acir_opcode_positions) =
88        memory_optimizer.remove_unused_memory_initializations(acir_opcode_positions);
89
90    // Range optimization pass
91    let range_optimizer = RangeOptimizer::new(acir, brillig_side_effects);
92    let (acir, acir_opcode_positions) =
93        range_optimizer.replace_redundant_ranges(acir_opcode_positions);
94
95    let max_transformer_passes_or_default = None;
96    let (acir, acir_opcode_positions, _opcodes_hash_stabilized) =
97        common_subexpression::transform_internal(
98            acir,
99            acir_opcode_positions,
100            brillig_side_effects,
101            max_transformer_passes_or_default,
102        );
103
104    info!("Number of opcodes after: {}", acir.opcodes.len());
105
106    (acir, acir_opcode_positions)
107}
108
109#[cfg(test)]
110mod tests {
111    use acir::{FieldElement, circuit::Circuit};
112    use std::collections::BTreeMap;
113
114    use crate::{assert_circuit_snapshot, compiler::optimizers::optimize_internal};
115
116    #[test]
117    fn removes_empty_assert_zero_opcodes() {
118        let src = "
119        private parameters: [w0, w1]
120        public parameters: []
121        return values: []
122        ASSERT w0*w1 - w1*w0 = 0
123        ";
124        let circuit = Circuit::<FieldElement>::from_str(src).unwrap();
125        let acir_opcode_positions = (0..circuit.opcodes.len()).collect();
126        let (optimized, _) = optimize_internal(circuit, acir_opcode_positions, &BTreeMap::new());
127        assert_circuit_snapshot!(optimized, @r"
128        private parameters: [w0, w1]
129        public parameters: []
130        return values: []
131        ");
132    }
133}
acvm/compiler/optimizers/mod.rs

acvm/compiler/optimizers/
mod.rs
