acvm/compiler/
mod.rs

1//! The `compiler` module contains several passes to transform an ACIR program.
2//! Roughly, the passes are separated into the `optimizers` which try to reduce the number of opcodes
3//! and the `transformers` which adapt the opcodes to the proving backend.
4//!
5//! # Optimizers
6//! - `GeneralOptimizer`: simple pass which simplifies `AssertZero` opcodes when possible (e.g remove terms with null coefficient)
7//! - `RangeOptimizer`: forward pass to collect range check information, and backward pass to remove the ones that are redundant.
8//! - `CommonSubexpressionOptimizer`: Assigns common subexpressions to witnesses to simplify expressions and reduce the number of opcodes.
9//!
10//! ACIR generation is performed by calling the `Ssa::into_acir` method, providing any necessary brillig bytecode.
11//! The compiled program will be returned as an `Artifacts` type.
12//!
13
14use std::collections::HashMap;
15
16use acir::circuit::{AcirOpcodeLocation, AssertionPayload, OpcodeLocation};
17
18// The various passes that we can use over ACIR
19pub use optimizers::optimize;
20mod optimizers;
21mod simulator;
22pub mod validator;
23
24pub use simulator::{CircuitSimulator, SimulationFailure};
25
26/// This module can move and decompose acir opcodes into multiple opcodes. The transformation map allows consumers of this module to map
27/// metadata they had about the opcodes to the new opcode structure generated after the transformation.
28/// ACIR opcodes are stored inside a vector of opcodes. A transformation pass will generate a new vector of opcodes,
29/// but each opcode is the result of the transformation of an opcode in the original vector.
30/// So we simply keep track of the relation:  index of the original opcode -> index of the new opcode in the new vector
31/// However we need a vector of new indexes for the map values in the case the old opcode is decomposed into multiple opcodes.
32#[derive(Debug)]
33pub struct AcirTransformationMap {
34    /// Maps the old acir indices to the new acir indices
35    old_indices_to_new_indices: HashMap<usize, Vec<usize>>,
36}
37
38impl AcirTransformationMap {
39    /// Builds a map from a vector of pointers to the old acir opcodes.
40    /// The index in the vector is the new opcode index.
41    /// The value of the vector is where the old opcode index was pointed.
42    /// E.g: If `acir_opcode_positions` = 0,1,2,4,5,5,6
43    /// that means that old indices 0,1,2,4,5,5,6 are mapped to the new indexes: 0,1,2,3,4,5,6
44    /// This gives the following map:
45    /// 0 -> 0
46    /// 1 -> 1
47    /// 2 -> 2
48    /// 4 -> 3
49    /// 5 -> [4, 5]
50    /// 6 -> 6
51    fn new(acir_opcode_positions: &[usize]) -> Self {
52        let mut old_indices_to_new_indices = HashMap::with_capacity(acir_opcode_positions.len());
53        for (new_index, old_index) in acir_opcode_positions.iter().copied().enumerate() {
54            old_indices_to_new_indices.entry(old_index).or_insert_with(Vec::new).push(new_index);
55        }
56        AcirTransformationMap { old_indices_to_new_indices }
57    }
58
59    /// Returns the new opcode location(s) corresponding to the old opcode.
60    /// An `OpcodeLocation` contains the index of the opcode in the vector of opcodes
61    /// This function returns the new `OpcodeLocation` by 'updating' the index within the given `OpcodeLocation`
62    /// using the `AcirTransformationMap`. In fact, it does not update the given `OpcodeLocation` 'in-memory' but rather
63    /// returns a new one, and even a vector of `OpcodeLocation`'s in case there are multiple new indexes corresponding
64    /// to the old opcode index.
65    pub fn new_locations(
66        &self,
67        old_location: OpcodeLocation,
68    ) -> impl Iterator<Item = OpcodeLocation> + '_ {
69        let old_acir_index = match old_location {
70            OpcodeLocation::Acir(index) => index,
71            OpcodeLocation::Brillig { acir_index, .. } => acir_index,
72        };
73
74        self.old_indices_to_new_indices.get(&old_acir_index).into_iter().flat_map(
75            move |new_indices| {
76                new_indices.iter().map(move |new_index| match old_location {
77                    OpcodeLocation::Acir(_) => OpcodeLocation::Acir(*new_index),
78                    OpcodeLocation::Brillig { brillig_index, .. } => {
79                        OpcodeLocation::Brillig { acir_index: *new_index, brillig_index }
80                    }
81                })
82            },
83        )
84    }
85
86    /// This function is similar to `new_locations()`, but only deals with
87    /// the `AcirOpcodeLocation` variant
88    pub fn new_acir_locations(
89        &self,
90        old_location: AcirOpcodeLocation,
91    ) -> impl Iterator<Item = AcirOpcodeLocation> + '_ {
92        let old_acir_index = old_location.index();
93
94        self.old_indices_to_new_indices.get(&old_acir_index).into_iter().flat_map(
95            move |new_indices| {
96                new_indices.iter().map(move |new_index| AcirOpcodeLocation::new(*new_index))
97            },
98        )
99    }
100}
101
102/// Update the assert messages to point to the new opcode locations.
103fn transform_assert_messages<F: Clone>(
104    assert_messages: Vec<(OpcodeLocation, AssertionPayload<F>)>,
105    map: &AcirTransformationMap,
106) -> Vec<(OpcodeLocation, AssertionPayload<F>)> {
107    assert_messages
108        .into_iter()
109        .flat_map(|(location, message)| {
110            let new_locations = map.new_locations(location);
111            new_locations.map(move |new_location| (new_location, message.clone()))
112        })
113        .collect()
114}
115
116#[macro_export]
117macro_rules! assert_circuit_snapshot {
118    ($acir:expr, $($arg:tt)*) => {
119        #[allow(unused_mut)]
120        let acir_string = $acir.to_string();
121        insta::assert_snapshot!(acir_string, $($arg)*)
122    };
123}
acvm/compiler/mod.rs

acvm/compiler/
mod.rs
