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    pub(crate) fn new(
96        circuit: Circuit<F>,
97        brillig_side_effects: &'a BTreeMap<BrilligFunctionId, bool>,
98    ) -> Self {
99        let infos = Self::collect_ranges(&circuit);
100        Self { circuit, infos, brillig_side_effects }
101    }
102
103    /// Collect range information about witnesses.
104    fn collect_ranges(circuit: &Circuit<F>) -> BTreeMap<Witness, RangeInfo> {
105        let mut infos: BTreeMap<Witness, RangeInfo> = BTreeMap::new();
106        let mut memory_block_lengths_bit_size: HashMap<BlockId, u32> = HashMap::new();
107
108        let update_witness_entry = |infos: &mut BTreeMap<Witness, RangeInfo>,
109                                    witness: Witness,
110                                    num_bits: u32,
111                                    is_implied: bool,
112                                    idx: usize| {
113            infos
114                .entry(witness)
115                .and_modify(|info| {
116                    if num_bits < info.num_bits
117                        || num_bits == info.num_bits && is_implied && !info.is_implied
118                    {
119                        info.switch_points.insert(idx);
120                        info.num_bits = num_bits;
121                        info.is_implied = is_implied;
122                    }
123                })
124                .or_insert_with(|| RangeInfo {
125                    num_bits,
126                    is_implied,
127                    switch_points: BTreeSet::from_iter(std::iter::once(idx)),
128                });
129        };
130
131        for (idx, opcode) in circuit.opcodes.iter().enumerate() {
132            match opcode {
133                Opcode::AssertZero(expr) => {
134                    // If the opcode is constraining a witness to be equal to a value then it can be considered
135                    // as a range opcode for the number of bits required to hold that value.
136                    if expr.is_degree_one_univariate() {
137                        let (k, witness) = expr.linear_combinations[0];
138                        let constant = expr.q_c;
139                        assert!(
140                            k != F::zero(),
141                            "collect_ranges: attempting to divide -constant by F::zero()"
142                        );
143                        let witness_value = -constant / k;
144
145                        let num_bits =
146                            if witness_value.is_zero() { 0 } else { witness_value.num_bits() };
147                        update_witness_entry(&mut infos, witness, num_bits, true, idx);
148                    }
149                }
150
151                Opcode::BlackBoxFuncCall(BlackBoxFuncCall::RANGE {
152                    input: FunctionInput::Witness(witness),
153                    num_bits,
154                }) => {
155                    update_witness_entry(&mut infos, *witness, *num_bits, false, idx);
156                }
157
158                Opcode::MemoryInit { block_id, init, .. } => {
159                    memory_block_lengths_bit_size
160                        .insert(*block_id, memory_block_implied_max_bits(init));
161                }
162
163                Opcode::MemoryOp { block_id, op: MemOp { index, .. }, .. } => {
164                    if let Some(witness) = index.to_witness() {
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, witness, num_bits, true, idx);
169                    }
170                }
171
172                // Barretenberg implementation of the AND and XOR blackbox constrain the inputs and output to be 'num_bit' bits
173                Opcode::BlackBoxFuncCall(BlackBoxFuncCall::AND { lhs, rhs, num_bits, output })
174                | Opcode::BlackBoxFuncCall(BlackBoxFuncCall::XOR { lhs, rhs, num_bits, output }) => {
175                    if let FunctionInput::Witness(witness) = lhs {
176                        update_witness_entry(&mut infos, *witness, *num_bits, true, idx);
177                    }
178                    if let FunctionInput::Witness(witness) = rhs {
179                        update_witness_entry(&mut infos, *witness, *num_bits, true, idx);
180                    }
181                    update_witness_entry(&mut infos, *output, *num_bits, true, idx);
182                }
183
184                Opcode::BlackBoxFuncCall(BlackBoxFuncCall::MultiScalarMul {
185                    scalars,
186                    predicate,
187                    ..
188                }) => {
189                    // When predicate is 1, the scalar inputs must be valid Grumpkin scalars.
190                    // Barretenberg implementation of the blackbox will implicitly constrain them to not overflow the Grumpkin scalar field modulus,
191                    // so we can assume that the low scalars are constrained to 128 bits and the high scalars to 126 bits.
192                    if predicate == &FunctionInput::Constant(F::one()) {
193                        let mut scalar_iters = scalars.iter();
194                        let mut lo = scalar_iters.next();
195                        while lo.is_some() {
196                            let lo_input = lo.unwrap();
197                            let hi_input =
198                                scalar_iters.next().expect("Missing scalar hi value for MSM");
199
200                            if let FunctionInput::Witness(lo_witness) = lo_input {
201                                update_witness_entry(&mut infos, *lo_witness, 128, true, idx);
202                            }
203                            if let FunctionInput::Witness(hi_witness) = hi_input {
204                                update_witness_entry(&mut infos, *hi_witness, 126, true, idx);
205                            }
206                            lo = scalar_iters.next();
207                        }
208                    }
209                }
210
211                _ => {}
212            }
213        }
214        infos
215    }
216
217    /// Returns a `Circuit` where each Witness is only range constrained
218    /// a minimal number of times that still allows us to avoid executing
219    /// any new side effects due to their removal.
220    ///
221    /// The idea is to keep only the RANGE opcodes that have strictly smaller bit-size requirements
222    /// than before, i.e the ones that are at a 'switch point'.
223    /// Furthermore, we only keep the switch points that are last before
224    /// a 'side-effect' opcode (i.e a Brillig call).
225    /// As a result, we simply do a backward pass on the opcodes, so that the last Brillig call
226    /// is known before reaching a RANGE opcode.
227    pub(crate) fn replace_redundant_ranges(
228        self,
229        order_list: Vec<usize>,
230    ) -> (Circuit<F>, Vec<usize>) {
231        let mut new_order_list = Vec::with_capacity(order_list.len());
232        let mut optimized_opcodes = Vec::with_capacity(self.circuit.opcodes.len());
233        // Consider the index beyond the last as a pseudo side effect by which time all constraints need to be inserted.
234        let mut next_side_effect = self.circuit.opcodes.len();
235        // Going in reverse so we can propagate the side effect information backwards.
236        for (idx, opcode) in self.circuit.opcodes.into_iter().enumerate().rev() {
237            let Some(witness) = (match opcode {
238                Opcode::BlackBoxFuncCall(BlackBoxFuncCall::RANGE {
239                    input: FunctionInput::Witness(witness),
240                    ..
241                }) => Some(witness),
242                Opcode::BrilligCall { id, .. } => {
243                    // Assume that Brillig calls might have side effects, unless we know they don't.
244                    if self.brillig_side_effects.get(&id).copied().unwrap_or(true) {
245                        next_side_effect = idx;
246                    }
247                    None
248                }
249                _ => None,
250            }) else {
251                // If its not the range opcode, add it to the opcode list and continue.
252                optimized_opcodes.push(opcode.clone());
253                new_order_list.push(order_list[idx]);
254                continue;
255            };
256
257            let info = self.infos.get(&witness).expect("Could not find witness. This should never be the case if `collect_ranges` is called");
258
259            // If this is not a switch point, then we should have already added a range constraint at least as strict, if it was needed.
260            if !info.switch_points.contains(&idx) {
261                continue;
262            }
263
264            // Check if we have an even stricter point before the next side effect.
265            let has_stricter_before_next_side_effect = info
266                .switch_points
267                .iter()
268                .any(|switch_idx| *switch_idx > idx && *switch_idx < next_side_effect);
269
270            // If there is something even stricter before the next side effect (or the end), we don't need this.
271            if has_stricter_before_next_side_effect {
272                continue;
273            }
274
275            new_order_list.push(order_list[idx]);
276            optimized_opcodes.push(opcode.clone());
277        }
278
279        // Restore forward order.
280        optimized_opcodes.reverse();
281        new_order_list.reverse();
282
283        (Circuit { opcodes: optimized_opcodes, ..self.circuit }, new_order_list)
284    }
285}
286
287/// Calculate the maximum number of bits required to index a memory block of a certain size.
288fn memory_block_implied_max_bits(init: &[Witness]) -> u32 {
289    let array_len = init.len() as u32;
290    let max_index = array_len.saturating_sub(1);
291    32 - max_index.leading_zeros()
292}
293
294#[cfg(test)]
295mod tests {
296    use std::collections::BTreeMap;
297
298    use crate::{
299        FieldElement, assert_circuit_snapshot,
300        compiler::{
301            CircuitSimulator,
302            optimizers::{
303                Opcode,
304                redundant_range::{RangeOptimizer, memory_block_implied_max_bits},
305            },
306        },
307    };
308    use acir::{
309        AcirField,
310        circuit::{Circuit, brillig::BrilligFunctionId},
311        native_types::{Expression, Witness},
312    };
313
314    #[test]
315    fn correctly_calculates_memory_block_implied_max_bits() {
316        assert_eq!(memory_block_implied_max_bits(&[]), 0);
317        assert_eq!(memory_block_implied_max_bits(&[Witness(0); 1]), 0);
318        assert_eq!(memory_block_implied_max_bits(&[Witness(0); 2]), 1);
319        assert_eq!(memory_block_implied_max_bits(&[Witness(0); 3]), 2);
320        assert_eq!(memory_block_implied_max_bits(&[Witness(0); 4]), 2);
321        assert_eq!(memory_block_implied_max_bits(&[Witness(0); 8]), 3);
322        assert_eq!(memory_block_implied_max_bits(&[Witness(0); u8::MAX as usize]), 8);
323        assert_eq!(memory_block_implied_max_bits(&[Witness(0); u16::MAX as usize]), 16);
324    }
325
326    #[test]
327    fn retain_lowest_range_size() {
328        // The optimizer should keep the lowest bit size range constraint
329        let src = "
330        private parameters: [w1]
331        public parameters: []
332        return values: []
333        BLACKBOX::RANGE input: w1, bits: 32
334        BLACKBOX::RANGE input: w1, bits: 16
335        ";
336        let circuit = Circuit::from_str(src).unwrap();
337        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
338
339        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
340        let brillig_side_effects = BTreeMap::new();
341        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
342
343        let info = optimizer
344            .infos
345            .get(&Witness(1))
346            .expect("Witness(1) was inserted, but it is missing from the map");
347        assert_eq!(
348            info.num_bits, 16,
349            "expected a range size of 16 since that was the lowest bit size provided"
350        );
351
352        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
353        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
354        assert_circuit_snapshot!(optimized_circuit, @r"
355        private parameters: [w1]
356        public parameters: []
357        return values: []
358        BLACKBOX::RANGE input: w1, bits: 16
359        ");
360    }
361
362    #[test]
363    fn remove_duplicates() {
364        // The optimizer should remove all duplicate range opcodes.
365        let src = "
366        private parameters: [w1, w2]
367        public parameters: []
368        return values: []
369        BLACKBOX::RANGE input: w1, bits: 16
370        BLACKBOX::RANGE input: w1, bits: 16
371        BLACKBOX::RANGE input: w2, bits: 23
372        BLACKBOX::RANGE input: w2, bits: 23
373        ";
374        let circuit = Circuit::from_str(src).unwrap();
375        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
376
377        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
378        let brillig_side_effects = BTreeMap::new();
379        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
380        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
381        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
382        assert_circuit_snapshot!(optimized_circuit, @r"
383        private parameters: [w1, w2]
384        public parameters: []
385        return values: []
386        BLACKBOX::RANGE input: w1, bits: 16
387        BLACKBOX::RANGE input: w2, bits: 23
388        ");
389    }
390
391    #[test]
392    fn non_range_opcodes() {
393        // The optimizer should not remove or change non-range opcodes
394        // The four AssertZero opcodes should remain unchanged.
395        let src = "
396        private parameters: [w1]
397        public parameters: []
398        return values: []
399        BLACKBOX::RANGE input: w1, bits: 16
400        BLACKBOX::RANGE input: w1, bits: 16
401        ASSERT 0 = 0
402        ASSERT 0 = 0
403        ASSERT 0 = 0
404        ASSERT 0 = 0
405        ";
406        let circuit = Circuit::from_str(src).unwrap();
407        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
408
409        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
410        let brillig_side_effects = BTreeMap::new();
411        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
412        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
413        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
414        assert_circuit_snapshot!(optimized_circuit, @r"
415        private parameters: [w1]
416        public parameters: []
417        return values: []
418        BLACKBOX::RANGE input: w1, bits: 16
419        ASSERT 0 = 0
420        ASSERT 0 = 0
421        ASSERT 0 = 0
422        ASSERT 0 = 0
423        ");
424    }
425
426    #[test]
427    fn constant_implied_ranges() {
428        // The optimizer should use knowledge about constant witness assignments to remove range opcodes, when possible.
429        // In this case, the `BLACKBOX::RANGE` opcode is expected to be removed because its range is larger than
430        // the range checked by the `ASSERT` opcode
431        let src = "
432        private parameters: [w1]
433        public parameters: []
434        return values: []
435        BLACKBOX::RANGE input: w1, bits: 16
436        ASSERT w1 = 0
437        ";
438        let circuit = Circuit::from_str(src).unwrap();
439        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
440
441        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
442        let brillig_side_effects = BTreeMap::new();
443        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
444        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
445        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
446        assert_circuit_snapshot!(optimized_circuit, @r"
447        private parameters: [w1]
448        public parameters: []
449        return values: []
450        ASSERT w1 = 0
451        ");
452    }
453
454    #[test]
455    fn large_constant_implied_ranges() {
456        // The optimizer should use knowledge about constant witness assignments to remove range opcodes, when possible.
457        // In this case, the `BLACKBOX::RANGE` opcode is expected to be retained because its range is smaller than
458        // the range checked by the `ASSERT` opcode
459        let src = "
460        private parameters: [w1]
461        public parameters: []
462        return values: []
463        BLACKBOX::RANGE input: w1, bits: 8
464        ASSERT w1 = 256
465        ";
466        let circuit = Circuit::from_str(src).unwrap();
467        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
468
469        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
470        let brillig_side_effects = BTreeMap::new();
471        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
472        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
473        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
474        assert_circuit_snapshot!(optimized_circuit, @r"
475        private parameters: [w1]
476        public parameters: []
477        return values: []
478        BLACKBOX::RANGE input: w1, bits: 8
479        ASSERT w1 = 256
480        ");
481    }
482
483    #[test]
484    fn logic_opcode() {
485        // Logic operations implicitly constrain their inputs and outputs to fit within their bit size.
486        let src = "
487        private parameters: [w0, w1]
488        public parameters: []
489        return values: [w2]
490        BLACKBOX::RANGE input: w0, bits: 8
491        BLACKBOX::RANGE input: w1, bits: 8
492        BLACKBOX::XOR lhs: w0, rhs: w1, output: w2, bits: 8
493        ";
494        let circuit = Circuit::from_str(src).unwrap();
495        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
496
497        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
498        let brillig_side_effects = BTreeMap::new();
499        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
500        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
501        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
502        assert_circuit_snapshot!(optimized_circuit, @r"
503        private parameters: [w0, w1]
504        public parameters: []
505        return values: [w2]
506        BLACKBOX::XOR lhs: w0, rhs: w1, output: w2, bits: 8
507        ");
508    }
509
510    #[test]
511    fn potential_side_effects() {
512        // The optimizer should not remove range constraints if doing so might allow invalid side effects to go through.
513        let src = "
514        private parameters: [w1, w2]
515        public parameters: []
516        return values: []
517        BLACKBOX::RANGE input: w1, bits: 32
518
519        // Call brillig with w2
520        BRILLIG CALL func: 0, predicate: 1, inputs: [w2], outputs: []
521        BLACKBOX::RANGE input: w1, bits: 16
522
523        // Another call
524        BRILLIG CALL func: 0, predicate: 1, inputs: [w2], outputs: []
525
526        // One more constraint, but this is redundant.
527        BLACKBOX::RANGE input: w1, bits: 64
528
529        // assert w1 == 0
530        ASSERT w1 = 0
531        ";
532        let circuit = Circuit::from_str(src).unwrap();
533        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
534
535        let acir_opcode_positions: Vec<usize> =
536            circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
537
538        // Consider the Brillig function to have a side effect.
539        let brillig_side_effects = BTreeMap::from_iter(vec![(BrilligFunctionId(0), true)]);
540
541        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
542        let (optimized_circuit, _) =
543            optimizer.replace_redundant_ranges(acir_opcode_positions.clone());
544        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
545
546        // `BLACKBOX::RANGE [w1]:32 bits []` remains: The minimum does not propagate backwards.
547        assert_circuit_snapshot!(optimized_circuit, @r"
548        private parameters: [w1, w2]
549        public parameters: []
550        return values: []
551        BLACKBOX::RANGE input: w1, bits: 32
552        BRILLIG CALL func: 0, predicate: 1, inputs: [w2], outputs: []
553        BLACKBOX::RANGE input: w1, bits: 16
554        BRILLIG CALL func: 0, predicate: 1, inputs: [w2], outputs: []
555        ASSERT w1 = 0
556        ");
557
558        // Applying again should have no effect (despite the range having the same bit size as the assert).
559        let optimizer = RangeOptimizer::new(optimized_circuit.clone(), &brillig_side_effects);
560        let (double_optimized_circuit, _) =
561            optimizer.replace_redundant_ranges(acir_opcode_positions);
562        assert_eq!(optimized_circuit.to_string(), double_optimized_circuit.to_string());
563    }
564
565    #[test]
566    fn array_implied_ranges() {
567        // The optimizer should use knowledge about array lengths and witnesses used to index these to remove range opcodes, when possible.
568        // The `BLACKBOX::RANGE` call is removed because its range is larger than the array's length
569        let src = "
570        private parameters: [w0, w1]
571        public parameters: []
572        return values: []
573        BLACKBOX::RANGE input: w1, bits: 16
574        INIT b0 = [w0, w0, w0, w0, w0, w0, w0, w0]
575        READ w2 = b0[w1]
576        ";
577        let circuit = Circuit::from_str(src).unwrap();
578        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
579
580        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
581        let brillig_side_effects = BTreeMap::new();
582        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
583        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
584        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
585        assert_circuit_snapshot!(optimized_circuit, @r"
586        private parameters: [w0, w1]
587        public parameters: []
588        return values: []
589        INIT b0 = [w0, w0, w0, w0, w0, w0, w0, w0]
590        READ w2 = b0[w1]
591        ");
592    }
593
594    #[test]
595    fn large_array_implied_ranges() {
596        // The optimizer should use knowledge about array lengths and witnesses used to index these to remove range opcodes, when possible.
597        // The `BLACKBOX::RANGE` call is not removed because its range is smaller than the array's length
598        let src = "
599        private parameters: [w0, w1]
600        public parameters: []
601        return values: []
602        BLACKBOX::RANGE input: w1, bits: 2
603        INIT b0 = [w0, w0, w0, w0, w0, w0, w0, w0]
604        READ w2 = b0[w1]
605        ";
606        let circuit = Circuit::from_str(src).unwrap();
607        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
608
609        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
610        let brillig_side_effects = BTreeMap::new();
611        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
612        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
613        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
614        assert_circuit_snapshot!(optimized_circuit, @r"
615        private parameters: [w0, w1]
616        public parameters: []
617        return values: []
618        BLACKBOX::RANGE input: w1, bits: 2
619        INIT b0 = [w0, w0, w0, w0, w0, w0, w0, w0]
620        READ w2 = b0[w1]
621        ");
622    }
623
624    #[test]
625    #[should_panic(expected = "collect_ranges: attempting to divide -constant by F::zero()")]
626    fn collect_ranges_zero_linear_combination_panics() {
627        let src = "
628        private parameters: [w1]
629        public parameters: []
630        return values: []
631        ";
632        let mut circuit = Circuit::from_str(src).unwrap();
633        let expr = Expression {
634            mul_terms: vec![],
635            linear_combinations: vec![(FieldElement::zero(), Witness(0))],
636            q_c: FieldElement::one(),
637        };
638        let opcode = Opcode::AssertZero(expr);
639        circuit.opcodes.push(opcode);
640        RangeOptimizer::collect_ranges(&circuit);
641    }
642
643    #[test]
644    fn msm_implied_ranges() {
645        // The optimizer should use knowledge about MultiScalarMul implied range constraints on its scalar inputs to remove range opcodes, when possible.
646        let src = "
647        private parameters: [w1, w2, w3, w4, w5, w6]
648        public parameters: []
649        return values: []
650        BLACKBOX::RANGE input: w1, bits: 128
651        BLACKBOX::RANGE input: w2, bits: 128
652        BLACKBOX::MULTI_SCALAR_MUL points: [w3, w4, 1], scalars: [w1, w2], predicate: 1, outputs: [w5, w6, w7]
653        ";
654        let circuit = Circuit::from_str(src).unwrap();
655        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
656
657        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
658        let brillig_side_effects = BTreeMap::new();
659        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
660
661        // Verify that the optimizer detected the implied ranges from MSM
662        let lo_info = optimizer.infos.get(&Witness(1)).expect("w1 should have range info");
663        assert_eq!(lo_info.num_bits, 128, "lo scalar should be constrained to 128 bits");
664        assert!(lo_info.is_implied, "lo scalar constraint should be marked as implied");
665
666        let hi_info = optimizer.infos.get(&Witness(2)).expect("w2 should have range info");
667        assert_eq!(hi_info.num_bits, 126, "hi scalar should be constrained to 126 bits");
668        assert!(hi_info.is_implied, "hi scalar constraint should be marked as implied");
669
670        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
671        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
672
673        // Both explicit RANGE opcodes should be removed
674        assert_circuit_snapshot!(optimized_circuit, @r"
675        private parameters: [w1, w2, w3, w4, w5, w6]
676        public parameters: []
677        return values: []
678        BLACKBOX::MULTI_SCALAR_MUL points: [w3, w4, 1], scalars: [w1, w2], predicate: 1, outputs: [w5, w6, w7]
679        ");
680    }
681
682    #[test]
683    fn msm_stricter_explicit_range_retained() {
684        // When the explicit range is stricter than the MSM implied range, it should be retained.
685        let src = "
686        private parameters: [w1, w2, w3, w4, w5, w6]
687        public parameters: []
688        return values: []
689        BLACKBOX::RANGE input: w1, bits: 64
690        BLACKBOX::RANGE input: w2, bits: 64
691        BLACKBOX::MULTI_SCALAR_MUL points: [w3, w4, 1], scalars: [w1, w2], predicate: 1, outputs: [w5, w6, w7]
692        ";
693        let circuit = Circuit::from_str(src).unwrap();
694        assert!(CircuitSimulator::check_circuit(&circuit).is_none());
695
696        let acir_opcode_positions = circuit.opcodes.iter().enumerate().map(|(i, _)| i).collect();
697        let brillig_side_effects = BTreeMap::new();
698        let optimizer = RangeOptimizer::new(circuit, &brillig_side_effects);
699
700        // The strictest constraint should be 64 bits (from the explicit RANGE), not 128/126 from MSM
701        let lo_info = optimizer.infos.get(&Witness(1)).expect("w1 should have range info");
702        assert_eq!(lo_info.num_bits, 64, "explicit 64-bit range should be the strictest");
703
704        let hi_info = optimizer.infos.get(&Witness(2)).expect("w2 should have range info");
705        assert_eq!(hi_info.num_bits, 64, "explicit 64-bit range should be the strictest");
706
707        let (optimized_circuit, _) = optimizer.replace_redundant_ranges(acir_opcode_positions);
708        assert!(CircuitSimulator::check_circuit(&optimized_circuit).is_none());
709
710        // The 64-bit ranges should be retained since they're stricter than the MSM implies
711        assert_circuit_snapshot!(optimized_circuit, @r"
712        private parameters: [w1, w2, w3, w4, w5, w6]
713        public parameters: []
714        return values: []
715        BLACKBOX::RANGE input: w1, bits: 64
716        BLACKBOX::RANGE input: w2, bits: 64
717        BLACKBOX::MULTI_SCALAR_MUL points: [w3, w4, 1], scalars: [w1, w2], predicate: 1, outputs: [w5, w6, w7]
718        ");
719    }
720}
acvm/compiler/optimizers/redundant_range.rs

acvm/compiler/optimizers/
redundant_range.rs
