acvm/compiler/optimizers/
mod.rs

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

acvm/compiler/optimizers/
mod.rs
