acvm/compiler/optimizers/
redundant_range.rs

1//! The redundant range constraint optimization pass aims to remove any `BlackBoxFunc::Range` opcodes
2//! which doesn't result in additional restrictions on the values of witnesses.
3//!
4//! Suppose we had the following pseudo-code:
5//!
6//! ```noir
7//! let z1 = x as u16;
8//! let z2 = x as u32;
9//! ```
10//! It is clear that if `x` fits inside of a 16-bit integer,
11//! it must also fit inside of a 32-bit integer.
12//!
13//! The generated ACIR may produce two range opcodes however;
14//! - One for the 16 bit range constraint of `x`
15//! - One for the 32-bit range constraint of `x`
16//!
17//! This optimization pass will keep the 16-bit range constraint
18//! and remove the 32-bit range constraint opcode.
19//!
20//! # Implicit range constraints
21//!
22//! We also consider implicit range constraints on witnesses - constraints other than `BlackBoxFunc::Range`
23//! which limit the size of a witness.
24//!
25//! ## Constant assignments
26//!
27//! The most obvious of these are when a witness is constrained to be equal to a constant value.
28//!
29//! ```noir
30//! let z1 = x as u16;
31//! assert_eq(z1, 100);
32//! ```
33//!
34//! We can consider the assertion that `z1 == 100` to be equivalent to a range constraint for `z1` to fit within
35//! 7 bits (the minimum necessary to hold the value `100`).
36//!
37//! ## Array indexing
38//!
39//! Another situation which adds an implicit range constraint are array indexing, for example in the program:
40//!
41//! ```noir
42//! fn main(index: u32) -> pub Field {
43//!     let array: [Field; 10] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
44//!     array[index]
45//! }
46//! ```
47//!
48//! Here the variable `index` is range constrained to fit within 32 bits by the `u32` type however
49//! it's constrained more restrictively by the length of `array`. If `index` were 10 or greater then
50//! it would result in a read past the end of the array, which is invalid. We can then remove the explicit
51//! range constraint on `index` as the usage as an array index more tightly constrains its value.
52//!
53//! # Side effects
54//!
55//! The pass will keep range constraints where, should the constraint have failed, removing it
56//! would allow potentially side effecting Brillig calls to be executed, before another constraint
57//! further down the line would have stopped the circuit.
58//!
59//! [BlackBoxFunc::Range]: acir::circuit::black_box_functions::BlackBoxFunc::RANGE
60
61use acir::{
62    AcirField,
63    circuit::{
64        Circuit, Opcode,
65        brillig::BrilligFunctionId,
66        opcodes::{BlackBoxFuncCall, BlockId, FunctionInput, MemOp},
67    },
68    native_types::Witness,
69};
70use std::collections::{BTreeMap, BTreeSet, HashMap};
71
72/// Information gathered about witnesses which are subject to range constraints.
73struct RangeInfo {
74    /// Opcode positions which updated this `RangeInfo`, i.e
75    /// at which stricter bit size information becomes available.
76    switch_points: BTreeSet<usize>,
77    /// Strictest constraint on bit size so far.
78    num_bits: u32,
79    /// Indicate whether the bit size comes from an assertion or from array indexing,
80    /// in which cases we can save an equivalent range constraint.
81    is_implied: bool,
82}
83
84pub(crate) struct RangeOptimizer<'a, F: AcirField> {
85    /// Maps witnesses to their bit size switch points.
86    infos: BTreeMap<Witness, RangeInfo>,
87    /// The next potential side effect for each opcode.
88    brillig_side_effects: &'a BTreeMap<BrilligFunctionId, bool>,
89    circuit: Circuit<F>,
90}
91
92impl<'a, F: AcirField> RangeOptimizer<'a, F> {
93    /// Creates a new `RangeOptimizer` by collecting all known range
94    /// constraints from `Circuit`.
95    #[tracing::instrument(level = "trace", name = "redundant_range_collect", skip_all)]
96    pub(crate) fn new(
97        circuit: Circuit<F>,
98        brillig_side_effects: &'a BTreeMap<BrilligFunctionId, bool>,
99    ) -> Self {
100        let infos = Self::collect_ranges(&circuit);
101        Self { circuit, infos, brillig_side_effects }
102    }
103
104    /// Collect range information about witnesses.
105    fn collect_ranges(circuit: &Circuit<F>) -> BTreeMap<Witness, RangeInfo> {
106        let mut infos: BTreeMap<Witness, RangeInfo> = BTreeMap::new();
107        let mut memory_block_lengths_bit_size: HashMap<BlockId, u32> = HashMap::new();
108
109        let update_witness_entry = |infos: &mut BTreeMap<Witness, RangeInfo>,
110                                    witness: Witness,
111                                    num_bits: u32,
112                                    is_implied: bool,
113                                    idx: usize| {
114            infos
115                .entry(witness)
116                .and_modify(|info| {
117                    if num_bits < info.num_bits
118                        || num_bits == info.num_bits && is_implied && !info.is_implied
119                    {
120                        info.switch_points.insert(idx);
121                        info.num_bits = num_bits;
122                        info.is_implied = is_implied;
123                    }
124                })
125                .or_insert_with(|| RangeInfo {
126                    num_bits,
127                    is_implied,
128                    switch_points: BTreeSet::from_iter(std::iter::once(idx)),
129                });
130        };
131
132        for (idx, opcode) in circuit.opcodes.iter().enumerate() {
133            match opcode {
134                Opcode::AssertZero(expr) => {
135                    // If the opcode is constraining a witness to be equal to a value then it can be considered
136                    // as a range opcode for the number of bits required to hold that value.
137                    if expr.is_degree_one_univariate() {
138                        let (k, witness) = expr.linear_combinations[0];
139                        let constant = expr.q_c;
140                        assert!(
141                            k != F::zero(),
142                            "collect_ranges: attempting to divide -constant by F::zero()"
143                        );
144                        let witness_value = -constant / k;
145
146                        let num_bits =
147                            if witness_value.is_zero() { 0 } else { witness_value.num_bits() };
148                        update_witness_entry(&mut infos, witness, num_bits, true, idx);
149                    }
150                }
151
152                Opcode::BlackBoxFuncCall(BlackBoxFuncCall::RANGE {
153                    input: FunctionInput::Witness(witness),
154                    num_bits,
155                }) => {
156                    update_witness_entry(&mut infos, *witness, *num_bits, false, idx);
157                }
158
159                Opcode::MemoryInit { block_id, init, .. } => {
160                    memory_block_lengths_bit_size
161                        .insert(*block_id, memory_block_implied_max_bits(init));
162                }
163
164                Opcode::MemoryOp { block_id, op: MemOp { index, .. }, .. } => {
165                    let num_bits = *memory_block_lengths_bit_size
166                        .get(block_id)
167                        .expect("memory must be initialized before any reads/writes");
168                    update_witness_entry(&mut infos, *index, num_bits, true, idx);
169                }
170
171                // Barretenberg implementation of the AND and XOR blackbox constrain the inputs and output to be 'num_bit' bits
172                Opcode::BlackBoxFuncCall(BlackBoxFuncCall::AND { lhs, rhs, num_bits, output })
173                | Opcode::BlackBoxFuncCall(BlackBoxFuncCall::XOR { lhs, rhs, num_bits, output }) => {
174                    if let FunctionInput::Witness(witness) = lhs {
175                        update_witness_entry(&mut infos, *witness, *num_bits, true, idx);
176                    }
177                    if let FunctionInput::Witness(witness) = rhs {
178                        update_witness_entry(&mut infos, *witness, *num_bits, true, idx);
179                    }
180                    update_witness_entry(&mut infos, *output, *num_bits, true, idx);
181                }
182
183                Opcode::BlackBoxFuncCall(BlackBoxFuncCall::MultiScalarMul {
184                    scalars,
185                    predicate,
186                    ..
187                })
188                    // When predicate is 1, the scalar inputs must be valid Grumpkin scalars.
189                    // Barretenberg implementation of the blackbox will implicitly constrain them to not overflow the Grumpkin scalar field modulus,
190                    // so we can assume that the low scalars are constrained to 128 bits and the high scalars to 126 bits.
191                    if predicate == &FunctionInput::Constant(F::one()) => {
192                        let mut scalar_iters = scalars.iter();
193                        let mut lo = scalar_iters.next();
194                        while lo.is_some() {
195                            let lo_input = lo.unwrap();
196                            let hi_input =
197                                scalar_iters.next().expect("Missing scalar hi value for MSM");
198
199                            if let FunctionInput::Witness(lo_witness) = lo_input {
200                                update_witness_entry(&mut infos, *lo_witness, 128, true, idx);
201                            }
202                            if let FunctionInput::Witness(hi_witness) = hi_input {
203                                update_witness_entry(&mut infos, *hi_witness, 126, true, idx);
204                            }
205                            lo = scalar_iters.next();
206                        }
207                    }
208
209                _ => {}
210            }
211        }
212        infos
213    }
214
215    /// Returns a `Circuit` where each Witness is only range constrained
216    /// a minimal number of times that still allows us to avoid executing
217    /// any new side effects due to their removal.
218    ///
219    /// The idea is to keep only the RANGE opcodes that have strictly smaller bit-size requirements
220    /// than before, i.e the ones that are at a 'switch point'.
221    /// Furthermore, we only keep the switch points that are last before
222    /// a 'side-effect' opcode (i.e a Brillig call).
223    /// As a result, we simply do a backward pass on the opcodes, so that the last Brillig call
224    /// is known before reaching a RANGE opcode.
225    #[tracing::instrument(level = "trace", name = "redundant_range_replace", skip_all)]
226    pub(crate) fn replace_redundant_ranges(
227        self,
228        order_list: Vec<usize>,
229    ) -> (Circuit<F>, Vec<usize>) {
230        let mut new_order_list = Vec::with_capacity(order_list.len());
231        let mut optimized_opcodes = Vec::with_capacity(self.circuit.opcodes.len());
232        // Consider the index beyond the last as a pseudo side effect by which time all constraints need to be inserted.
233        let mut next_side_effect = self.circuit.opcodes.len();
234        // Going in reverse so we can propagate the side effect information backwards.
235        for (idx, opcode) in self.circuit.opcodes.into_iter().enumerate().rev() {
236            let Some(witness) = (match opcode {
237                Opcode::BlackBoxFuncCall(BlackBoxFuncCall::RANGE {
238                    input: FunctionInput::Witness(witness),
239                    ..
240                }) => Some(witness),
241                Opcode::BrilligCall { id, .. } => {
242                    // Assume that Brillig calls might have side effects, unless we know they don't.
243                    if self.brillig_side_effects.get(&id).copied().unwrap_or(true) {
244                        next_side_effect = idx;
245                    }
246                    None
247                }
248                Opcode::Call { .. } => {
249                    // A call into a separate ACIR circuit can transitively execute side-effecting
250                    // Brillig, so it must act as a side-effect boundary like a direct Brillig call.
251                    next_side_effect = idx;
252                    None
253                }
254                _ => None,
255            }) else {
256                // If its not the range opcode, add it to the opcode list and continue.
257                optimized_opcodes.push(opcode);
258                new_order_list.push(order_list[idx]);
259                continue;
260            };
261
262            let info = self.infos.get(&witness).expect("Could not find witness. This should never be the case if `collect_ranges` is called");
263
264            // If this is not a switch point, then we should have already added a range constraint at least as strict, if it was needed.
265            if !info.switch_points.contains(&idx) {
266                continue;
267            }
268
269            // Check if we have an even stricter point before the next side effect.
270            let has_stricter_before_next_side_effect = info
271                .switch_points
272                .iter()
273                .any(|switch_idx| *switch_idx > idx && *switch_idx < next_side_effect);
274
275            // If there is something even stricter before the next side effect (or the end), we don't need this.
276            if has_stricter_before_next_side_effect {
277                continue;
278            }
279
280            new_order_list.push(order_list[idx]);
281            optimized_opcodes.push(opcode);
282        }
283
284        // Restore forward order.
285        optimized_opcodes.reverse();
286        new_order_list.reverse();
287
288        (Circuit { opcodes: optimized_opcodes, ..self.circuit }, new_order_list)
289    }
290}
291
292/// Calculate the maximum number of bits required to index a memory block of a certain size.
293fn memory_block_implied_max_bits(init: &[Witness]) -> u32 {
294    let array_len = init.len() as u32;
295    let max_index = array_len.saturating_sub(1);
296    32 - max_index.leading_zeros()
297}
298
299#[cfg(test)]
300mod tests {
301    use std::collections::BTreeMap;
302
303    use crate::{
304        FieldElement, assert_circuit_snapshot,
305        compiler::{
306            CircuitSimulator,
307            optimizers::{
308                Opcode,
309                redundant_range::{RangeOptimizer, memory_block_implied_max_bits},
310            },
311        },
312    };
313    use acir::{
314        AcirField,
315        circuit::{Circuit, brillig::BrilligFunctionId},
316        native_types::{Expression, Witness},
317    };
318    use test_case::test_case;
319
320    #[test]
321    fn correctly_calculates_memory_block_implied_max_bits() {
322        assert_eq!(memory_block_implied_max_bits(&[]), 0);
323        assert_eq!(memory_block_implied_max_bits(&[Witness(0); 1]), 0);
324        assert_eq!(memory_block_implied_max_bits(&[Witness(0); 2]), 1);
325        assert_eq!(memory_block_implied_max_bits(&[Witness(0); 3]), 2);
326        assert_eq!(memory_block_implied_max_bits(&[Witness(0); 4]), 2);
327        assert_eq!(memory_block_implied_max_bits(&[Witness(0); 8]), 3);
328        assert_eq!(memory_block_implied_max_bits(&[Witness(0); u8::MAX as usize]), 8);
329        assert_eq!(memory_block_implied_max_bits(&[Witness(0); u16::MAX as usize]), 16);
330    }
331
332    #[test]
333    fn retain_lowest_range_size() {
334        // The optimizer should keep the lowest bit size range constraint
335        let src = "
336        private parameters: [w1]
337        public parameters: []
338        return values: []
339        BLACKBOX::RANGE input: w1, bits: 32
340        BLACKBOX::RANGE input: w1, bits: 16
341        ";
342        let circuit = Circuit::from_str(src).unwrap();
343        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
344
345        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
346        let brillig_side_effects = BTreeMap::new();
347        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
348
349        let info = optimizer
350            .infos
351            .get(&Witness(1))
352            .expect("Witness(1) was inserted, but it is missing from the map");
353        assert_eq!(
354            info.num_bits, 16,
355            "expected a range size of 16 since that was the lowest bit size provided"
356        );
357
358        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
359        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
360        assert_circuit_snapshot!(optimized_circuit, @r"
361        private parameters: [w1]
362        public parameters: []
363        return values: []
364        BLACKBOX::RANGE input: w1, bits: 16
365        ");
366    }
367
368    #[test]
369    fn remove_duplicates() {
370        // The optimizer should remove all duplicate range opcodes.
371        let src = "
372        private parameters: [w1, w2]
373        public parameters: []
374        return values: []
375        BLACKBOX::RANGE input: w1, bits: 16
376        BLACKBOX::RANGE input: w1, bits: 16
377        BLACKBOX::RANGE input: w2, bits: 23
378        BLACKBOX::RANGE input: w2, bits: 23
379        ";
380        let circuit = Circuit::from_str(src).unwrap();
381        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
382
383        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
384        let brillig_side_effects = BTreeMap::new();
385        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
386        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
387        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
388        assert_circuit_snapshot!(optimized_circuit, @r"
389        private parameters: [w1, w2]
390        public parameters: []
391        return values: []
392        BLACKBOX::RANGE input: w1, bits: 16
393        BLACKBOX::RANGE input: w2, bits: 23
394        ");
395    }
396
397    #[test]
398    fn non_range_opcodes() {
399        // The optimizer should not remove or change non-range opcodes
400        // The four AssertZero opcodes should remain unchanged.
401        let src = "
402        private parameters: [w1]
403        public parameters: []
404        return values: []
405        BLACKBOX::RANGE input: w1, bits: 16
406        BLACKBOX::RANGE input: w1, bits: 16
407        ASSERT 0 = 0
408        ASSERT 0 = 0
409        ASSERT 0 = 0
410        ASSERT 0 = 0
411        ";
412        let circuit = Circuit::from_str(src).unwrap();
413        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
414
415        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
416        let brillig_side_effects = BTreeMap::new();
417        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
418        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
419        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
420        assert_circuit_snapshot!(optimized_circuit, @r"
421        private parameters: [w1]
422        public parameters: []
423        return values: []
424        BLACKBOX::RANGE input: w1, bits: 16
425        ASSERT 0 = 0
426        ASSERT 0 = 0
427        ASSERT 0 = 0
428        ASSERT 0 = 0
429        ");
430    }
431
432    #[test]
433    fn constant_implied_ranges() {
434        // The optimizer should use knowledge about constant witness assignments to remove range opcodes, when possible.
435        // In this case, the `BLACKBOX::RANGE` opcode is expected to be removed because its range is larger than
436        // the range checked by the `ASSERT` opcode
437        let src = "
438        private parameters: [w1]
439        public parameters: []
440        return values: []
441        BLACKBOX::RANGE input: w1, bits: 16
442        ASSERT w1 = 0
443        ";
444        let circuit = Circuit::from_str(src).unwrap();
445        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
446
447        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
448        let brillig_side_effects = BTreeMap::new();
449        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
450        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
451        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
452        assert_circuit_snapshot!(optimized_circuit, @r"
453        private parameters: [w1]
454        public parameters: []
455        return values: []
456        ASSERT w1 = 0
457        ");
458    }
459
460    #[test]
461    fn large_constant_implied_ranges() {
462        // The optimizer should use knowledge about constant witness assignments to remove range opcodes, when possible.
463        // In this case, the `BLACKBOX::RANGE` opcode is expected to be retained because its range is smaller than
464        // the range checked by the `ASSERT` opcode
465        let src = "
466        private parameters: [w1]
467        public parameters: []
468        return values: []
469        BLACKBOX::RANGE input: w1, bits: 8
470        ASSERT w1 = 256
471        ";
472        let circuit = Circuit::from_str(src).unwrap();
473        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
474
475        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
476        let brillig_side_effects = BTreeMap::new();
477        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
478        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
479        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
480        assert_circuit_snapshot!(optimized_circuit, @r"
481        private parameters: [w1]
482        public parameters: []
483        return values: []
484        BLACKBOX::RANGE input: w1, bits: 8
485        ASSERT w1 = 256
486        ");
487    }
488
489    #[test]
490    fn logic_opcode() {
491        // Logic operations implicitly constrain their inputs and outputs to fit within their bit size.
492        let src = "
493        private parameters: [w0, w1]
494        public parameters: []
495        return values: [w2]
496        BLACKBOX::RANGE input: w0, bits: 8
497        BLACKBOX::RANGE input: w1, bits: 8
498        BLACKBOX::XOR lhs: w0, rhs: w1, output: w2, bits: 8
499        ";
500        let circuit = Circuit::from_str(src).unwrap();
501        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
502
503        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
504        let brillig_side_effects = BTreeMap::new();
505        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
506        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
507        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
508        assert_circuit_snapshot!(optimized_circuit, @r"
509        private parameters: [w0, w1]
510        public parameters: []
511        return values: [w2]
512        BLACKBOX::XOR lhs: w0, rhs: w1, output: w2, bits: 8
513        ");
514    }
515
516    #[test]
517    fn potential_side_effects() {
518        // The optimizer should not remove range constraints if doing so might allow invalid side effects to go through.
519        let src = "
520        private parameters: [w1, w2]
521        public parameters: []
522        return values: []
523        BLACKBOX::RANGE input: w1, bits: 32
524
525        // Call brillig with w2
526        BRILLIG CALL func: 0, predicate: 1, inputs: [w2], outputs: []
527        BLACKBOX::RANGE input: w1, bits: 16
528
529        // Another call
530        BRILLIG CALL func: 0, predicate: 1, inputs: [w2], outputs: []
531
532        // One more constraint, but this is redundant.
533        BLACKBOX::RANGE input: w1, bits: 64
534
535        // assert w1 == 0
536        ASSERT w1 = 0
537        ";
538        let circuit = Circuit::from_str(src).unwrap();
539        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
540
541        let acir_opcode_positions: Vec<usize> =
542            circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
543
544        // Consider the Brillig function to have a side effect.
545        let brillig_side_effects = BTreeMap::from_iter(vec![(BrilligFunctionId::new(0), true)]);
546
547        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
548        let (optimized_circuit, _) =
549            optimizer.replace_redundant_ranges(acir_opcode_positions.clone());
550        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
551
552        // `BLACKBOX::RANGE [w1]:32 bits []` remains: The minimum does not propagate backwards.
553        assert_circuit_snapshot!(optimized_circuit, @r"
554        private parameters: [w1, w2]
555        public parameters: []
556        return values: []
557        BLACKBOX::RANGE input: w1, bits: 32
558        BRILLIG CALL func: 0, predicate: 1, inputs: [w2], outputs: []
559        BLACKBOX::RANGE input: w1, bits: 16
560        BRILLIG CALL func: 0, predicate: 1, inputs: [w2], outputs: []
561        ASSERT w1 = 0
562        ");
563
564        // Applying again should have no effect (despite the range having the same bit size as the assert).
565        let optimizer = RangeOptimizer::new(optimized_circuit.clone(), &brillig_side_effects);
566        let (double_optimized_circuit, _) =
567            optimizer.replace_redundant_ranges(acir_opcode_positions);
568        assert_eq!(optimized_circuit.to_string(), double_optimized_circuit.to_string());
569    }
570
571    #[test]
572    fn acir_call_is_a_side_effect_boundary() {
573        // An `Opcode::Call` dispatches into a separate ACIR circuit that can transitively run
574        // side-effecting Brillig. Just like a `BrilligCall`, it must act as a side-effect boundary:
575        // a caller-side explicit RANGE before the call must not be removed even when a later
576        // implied constraint (here `ASSERT w1 = 0`) would otherwise make it redundant.
577        let src = "
578        private parameters: [w1, w2]
579        public parameters: []
580        return values: []
581        BLACKBOX::RANGE input: w1, bits: 32
582        CALL func: 1, predicate: 1, inputs: [w2], outputs: []
583        ASSERT w1 = 0
584        ";
585        let circuit = Circuit::from_str(src).unwrap();
586        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
587
588        let acir_opcode_positions: Vec<usize> =
589            circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
590        let brillig_side_effects = BTreeMap::new();
591        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
592        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
593        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
594
595        // The range must be retained before the `CALL`.
596        assert_circuit_snapshot!(optimized_circuit, @r"
597        private parameters: [w1, w2]
598        public parameters: []
599        return values: []
600        BLACKBOX::RANGE input: w1, bits: 32
601        CALL func: 1, predicate: 1, inputs: [w2], outputs: []
602        ASSERT w1 = 0
603        ");
604    }
605
606    #[test]
607    fn array_implied_ranges() {
608        // The optimizer should use knowledge about array lengths and witnesses used to index these to remove range opcodes, when possible.
609        // The `BLACKBOX::RANGE` call is removed because its range is larger than the array's length
610        let src = "
611        private parameters: [w0, w1]
612        public parameters: []
613        return values: []
614        BLACKBOX::RANGE input: w1, bits: 16
615        INIT b0 = [w0, w0, w0, w0, w0, w0, w0, w0]
616        READ w2 = b0[w1]
617        ";
618        let circuit = Circuit::from_str(src).unwrap();
619        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
620
621        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
622        let brillig_side_effects = BTreeMap::new();
623        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
624        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
625        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
626        assert_circuit_snapshot!(optimized_circuit, @r"
627        private parameters: [w0, w1]
628        public parameters: []
629        return values: []
630        INIT b0 = [w0, w0, w0, w0, w0, w0, w0, w0]
631        READ w2 = b0[w1]
632        ");
633    }
634
635    #[test]
636    fn large_array_implied_ranges() {
637        // The optimizer should use knowledge about array lengths and witnesses used to index these to remove range opcodes, when possible.
638        // The `BLACKBOX::RANGE` call is not removed because its range is smaller than the array's length
639        let src = "
640        private parameters: [w0, w1]
641        public parameters: []
642        return values: []
643        BLACKBOX::RANGE input: w1, bits: 2
644        INIT b0 = [w0, w0, w0, w0, w0, w0, w0, w0]
645        READ w2 = b0[w1]
646        ";
647        let circuit = Circuit::from_str(src).unwrap();
648        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
649
650        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
651        let brillig_side_effects = BTreeMap::new();
652        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
653        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
654        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
655        assert_circuit_snapshot!(optimized_circuit, @r"
656        private parameters: [w0, w1]
657        public parameters: []
658        return values: []
659        BLACKBOX::RANGE input: w1, bits: 2
660        INIT b0 = [w0, w0, w0, w0, w0, w0, w0, w0]
661        READ w2 = b0[w1]
662        ");
663    }
664
665    #[test]
666    #[should_panic(expected = "collect_ranges: attempting to divide -constant by F::zero()")]
667    fn collect_ranges_zero_linear_combination_panics() {
668        let src = "
669        private parameters: [w1]
670        public parameters: []
671        return values: []
672        ";
673        let mut circuit = Circuit::from_str(src).unwrap();
674        let expr = Expression {
675            mul_terms: vec![],
676            linear_combinations: vec![(FieldElement::zero(), Witness(0))],
677            q_c: FieldElement::one(),
678        };
679        let opcode = Opcode::AssertZero(expr);
680        circuit.opcodes.push(opcode);
681        RangeOptimizer::collect_ranges(&circuit);
682    }
683
684    #[test]
685    fn msm_implied_ranges() {
686        // The optimizer should use knowledge about MultiScalarMul implied range constraints on its scalar inputs to remove range opcodes, when possible.
687        let src = "
688        private parameters: [w1, w2, w3, w4, w5, w6]
689        public parameters: []
690        return values: []
691        BLACKBOX::RANGE input: w1, bits: 128
692        BLACKBOX::RANGE input: w2, bits: 128
693        BLACKBOX::MULTI_SCALAR_MUL points: [w3, w4], scalars: [w1, w2], predicate: 1, outputs: [w5, w6]
694        ";
695        let circuit = Circuit::from_str(src).unwrap();
696        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
697
698        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
699        let brillig_side_effects = BTreeMap::new();
700        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
701
702        // Verify that the optimizer detected the implied ranges from MSM
703        let lo_info = optimizer.infos.get(&Witness(1)).expect("w1 should have range info");
704        assert_eq!(lo_info.num_bits, 128, "lo scalar should be constrained to 128 bits");
705        assert!(lo_info.is_implied, "lo scalar constraint should be marked as implied");
706
707        let hi_info = optimizer.infos.get(&Witness(2)).expect("w2 should have range info");
708        assert_eq!(hi_info.num_bits, 126, "hi scalar should be constrained to 126 bits");
709        assert!(hi_info.is_implied, "hi scalar constraint should be marked as implied");
710
711        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
712        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
713
714        // Both explicit RANGE opcodes should be removed
715        assert_circuit_snapshot!(optimized_circuit, @r"
716        private parameters: [w1, w2, w3, w4, w5, w6]
717        public parameters: []
718        return values: []
719        BLACKBOX::MULTI_SCALAR_MUL points: [w3, w4], scalars: [w1, w2], predicate: 1, outputs: [w5, w6]
720        ");
721    }
722
723    #[test]
724    fn msm_stricter_explicit_range_retained() {
725        // When the explicit range is stricter than the MSM implied range, it should be retained.
726        let src = "
727        private parameters: [w1, w2, w3, w4, w5, w6]
728        public parameters: []
729        return values: []
730        BLACKBOX::RANGE input: w1, bits: 64
731        BLACKBOX::RANGE input: w2, bits: 64
732        BLACKBOX::MULTI_SCALAR_MUL points: [w3, w4], scalars: [w1, w2], predicate: 1, outputs: [w5, w6]
733        ";
734        let circuit = Circuit::from_str(src).unwrap();
735        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
736
737        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
738        let brillig_side_effects = BTreeMap::new();
739        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
740
741        // The strictest constraint should be 64 bits (from the explicit RANGE), not 128/126 from MSM
742        let lo_info = optimizer.infos.get(&Witness(1)).expect("w1 should have range info");
743        assert_eq!(lo_info.num_bits, 64, "explicit 64-bit range should be the strictest");
744
745        let hi_info = optimizer.infos.get(&Witness(2)).expect("w2 should have range info");
746        assert_eq!(hi_info.num_bits, 64, "explicit 64-bit range should be the strictest");
747
748        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
749        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
750
751        // The 64-bit ranges should be retained since they're stricter than the MSM implies
752        assert_circuit_snapshot!(optimized_circuit, @r"
753        private parameters: [w1, w2, w3, w4, w5, w6]
754        public parameters: []
755        return values: []
756        BLACKBOX::RANGE input: w1, bits: 64
757        BLACKBOX::RANGE input: w2, bits: 64
758        BLACKBOX::MULTI_SCALAR_MUL points: [w3, w4], scalars: [w1, w2], predicate: 1, outputs: [w5, w6]
759        ");
760    }
761
762    // A MultiScalarMul only implicitly range-constrains its scalars when it is enabled, i.e. when
763    // the predicate is the constant 1. A constant-0 predicate disables the opcode, and a witness
764    // predicate can be assigned 0 by the prover; in both cases barretenberg imposes no constraint
765    // on the scalars, so the optimizer must not treat the MSM as a source of implied ranges and the
766    // explicit RANGE opcodes must survive.
767    #[test_case("0"; "constant zero predicate")]
768    #[test_case("w7"; "witness predicate")]
769    fn msm_disabled_predicate_retains_explicit_range(predicate: &str) {
770        // `w7` is declared regardless; an unused private parameter is harmless for the constant case.
771        let src = format!(
772            "
773            private parameters: [w1, w2, w3, w4, w5, w6, w7]
774            public parameters: []
775            return values: []
776            BLACKBOX::RANGE input: w1, bits: 128
777            BLACKBOX::RANGE input: w2, bits: 128
778            BLACKBOX::MULTI_SCALAR_MUL points: [w3, w4], scalars: [w1, w2], predicate: {predicate}, outputs: [w5, w6]
779            "
780        );
781        let circuit = Circuit::from_str(&src).unwrap();
782        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
783
784        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
785        let brillig_side_effects = BTreeMap::new();
786        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
787
788        // The disabled MSM must not contribute any implied range; the constraint on each scalar must
789        // come from its explicit RANGE opcode.
790        for scalar in [Witness(1), Witness(2)] {
791            let info = optimizer.infos.get(&scalar).expect("scalar should have range info");
792            assert_eq!(info.num_bits, 128, "only the explicit 128-bit range should apply");
793            assert!(
794                !info.is_implied,
795                "constraint should come from the explicit RANGE, not the MSM"
796            );
797        }
798
799        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
800        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
801
802        // Nothing is removed: the optimized circuit is identical to the input.
803        let expected = Circuit::<FieldElement>::from_str(&src).unwrap().to_string();
804        assert_eq!(optimized_circuit.to_string(), expected, "no opcode should be removed");
805    }
806}
acvm/compiler/optimizers/redundant_range.rs

acvm/compiler/optimizers/
redundant_range.rs
