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

acvm/compiler/
mod.rs
