Reachability analysis for Brillig entry point globals initialization

[vezenovm]

Aim

If I have multiple Brillig entry points, I should only initialize globals for the entry points that use those globals. For example let's take this program:

global EXPONENTIATE: [[Field; 2]; 2] = [[1, 1], [0, 0]];

fn main(x: u32, y: pub Field) {
     /// Safety: testing context
    unsafe {
        check_acc_entry_point(x as Field, y);
        assert(entry_point(x) == 2);
    }
}
unconstrained fn check_acc_entry_point(x: Field, y: Field) {
    let mut acc: Field = 0;
    for i in 0..2 {
        for j in 0..2 {
            acc += EXPONENTIATE[i][j];
        }
    }
    assert(acc != 0);
    assert(x != y);
}
fn inner(x: u32) -> u32 {
    x + 1
}
unconstrained fn entry_point(x: u32) -> u32 {
    inner(x + 1)
}

I have two entry points: check_acc_entry_point and entry_point. I want to be able to initialize the appropriate globals for the given entry point without any repeat initialization.

Expected Behavior

I should initialize all the globals for check_acc_entry_point, however, this is unnecessary for entry_point which does not use all of the globals like the EXPONENTIATE array. I should also be able to differentiate which globals are used in which entry points. For example, the 1 constant in entry_point can be shared with the global space 1 constant. We should be able to only initialize the globals used in a given a entry point.

Bug

Currently we are executing all the Brillig necessary to initialize all globals for every entry point.

Taking the ACIR for the program above:

Details

unconstrained func 0

[Const { destination: Direct(2), bit_size: Integer(U32), value: 1 }, Const { destination: Direct(1), bit_size: Integer(U32), value: 49221 }, Const { destination: Direct(0), bit_size: Integer(U32), value: 3 }, Const { destination: Relative(3), bit_size: Integer(U32), value: 2 }, Const { destination: Relative(4), bit_size: Integer(U32), value: 0 }, CalldataCopy { destination_address: Direct(49219), size_address: Relative(3), offset_address: Relative(4) }, Mov { destination: Relative(1), source: Direct(49219) }, Mov { destination: Relative(2), source: Direct(49220) }, Call { location: 13 }, Call { location: 43 }, Const { destination: Relative(1), bit_size: Integer(U32), value: 49221 }, Const { destination: Relative(2), bit_size: Integer(U32), value: 0 }, Stop { return_data: HeapVector { pointer: Relative(1), size: Relative(2) } }, Const { destination: Direct(32835), bit_size: Field, value: 1 }, Mov { destination: Direct(32836), source: Direct(1) }, Const { destination: Direct(32837), bit_size: Integer(U32), value: 3 }, BinaryIntOp { destination: Direct(1), op: Add, bit_size: U32, lhs: Direct(1), rhs: Direct(32837) }, IndirectConst { destination_pointer: Direct(32836), bit_size: Integer(U32), value: 1 }, BinaryIntOp { destination: Direct(32837), op: Add, bit_size: U32, lhs: Direct(32836), rhs: Direct(2) }, Mov { destination: Direct(32838), source: Direct(32837) }, Store { destination_pointer: Direct(32838), source: Direct(32835) }, BinaryIntOp { destination: Direct(32838), op: Add, bit_size: U32, lhs: Direct(32838), rhs: Direct(2) }, Store { destination_pointer: Direct(32838), source: Direct(32835) }, Const { destination: Direct(32837), bit_size: Field, value: 0 }, Mov { destination: Direct(32838), source: Direct(1) }, Const { destination: Direct(32839), bit_size: Integer(U32), value: 3 }, BinaryIntOp { destination: Direct(1), op: Add, bit_size: U32, lhs: Direct(1), rhs: Direct(32839) }, IndirectConst { destination_pointer: Direct(32838), bit_size: Integer(U32), value: 1 }, BinaryIntOp { destination: Direct(32839), op: Add, bit_size: U32, lhs: Direct(32838), rhs: Direct(2) }, Mov { destination: Direct(32840), source: Direct(32839) }, Store { destination_pointer: Direct(32840), source: Direct(32837) }, BinaryIntOp { destination: Direct(32840), op: Add, bit_size: U32, lhs: Direct(32840), rhs: Direct(2) }, Store { destination_pointer: Direct(32840), source: Direct(32837) }, Mov { destination: Direct(32839), source: Direct(1) }, Const { destination: Direct(32840), bit_size: Integer(U32), value: 3 }, BinaryIntOp { destination: Direct(1), op: Add, bit_size: U32, lhs: Direct(1), rhs: Direct(32840) }, IndirectConst { destination_pointer: Direct(32839), bit_size: Integer(U32), value: 1 }, BinaryIntOp { destination: Direct(32840), op: Add, bit_size: U32, lhs: Direct(32839), rhs: Direct(2) }, Mov { destination: Direct(32841), source: Direct(32840) }, Store { destination_pointer: Direct(32841), source: Direct(32836) }, BinaryIntOp { destination: Direct(32841), op: Add, bit_size: U32, lhs: Direct(32841), rhs: Direct(2) }, Store { destination_pointer: Direct(32841), source: Direct(32838) }, Return, Call { location: 89 }, Mov { destination: Relative(4), source: Direct(1) }, BinaryIntOp { destination: Direct(1), op: Add, bit_size: U32, lhs: Direct(1), rhs: Direct(2) }, Const { destination: Relative(5), bit_size: Field, value: 0 }, Store { destination_pointer: Relative(4), source: Relative(5) }, Const { destination: Relative(6), bit_size: Integer(U32), value: 1 }, Const { destination: Relative(7), bit_size: Integer(U32), value: 0 }, Const { destination: Relative(8), bit_size: Integer(U32), value: 2 }, Mov { destination: Relative(3), source: Relative(7) }, Jump { location: 53 }, BinaryIntOp { destination: Relative(9), op: LessThan, bit_size: U32, lhs: Relative(3), rhs: Relative(8) }, JumpIf { condition: Relative(9), location: 69 }, Jump { location: 56 }, Load { destination: Relative(3), source_pointer: Relative(4) }, BinaryFieldOp { destination: Relative(4), op: Equals, lhs: Relative(3), rhs: Relative(5) }, Const { destination: Relative(3), bit_size: Integer(U1), value: 0 }, BinaryIntOp { destination: Relative(5), op: Equals, bit_size: U1, lhs: Relative(4), rhs: Relative(3) }, JumpIf { condition: Relative(5), location: 63 }, Const { destination: Relative(6), bit_size: Integer(U32), value: 0 }, Trap { revert_data: HeapVector { pointer: Direct(1), size: Relative(6) } }, BinaryFieldOp { destination: Relative(4), op: Equals, lhs: Relative(1), rhs: Relative(2) }, BinaryIntOp { destination: Relative(1), op: Equals, bit_size: U1, lhs: Relative(4), rhs: Relative(3) }, JumpIf { condition: Relative(1), location: 68 }, Const { destination: Relative(2), bit_size: Integer(U32), value: 0 }, Trap { revert_data: HeapVector { pointer: Direct(1), size: Relative(2) } }, Return, Const { destination: Relative(10), bit_size: Integer(U32), value: 2 }, BinaryIntOp { destination: Relative(11), op: LessThan, bit_size: U32, lhs: Relative(3), rhs: Relative(10) }, JumpIf { condition: Relative(11), location: 73 }, Call { location: 95 }, BinaryIntOp { destination: Relative(10), op: Add, bit_size: U32, lhs: Direct(32839), rhs: Direct(2) }, BinaryIntOp { destination: Relative(11), op: Add, bit_size: U32, lhs: Relative(10), rhs: Relative(3) }, Load { destination: Relative(9), source_pointer: Relative(11) }, Load { destination: Relative(10), source_pointer: Relative(4) }, BinaryIntOp { destination: Relative(12), op: Add, bit_size: U32, lhs: Relative(9), rhs: Direct(2) }, BinaryIntOp { destination: Relative(13), op: Add, bit_size: U32, lhs: Relative(12), rhs: Relative(7) }, Load { destination: Relative(11), source_pointer: Relative(13) }, BinaryFieldOp { destination: Relative(12), op: Add, lhs: Relative(10), rhs: Relative(11) }, BinaryIntOp { destination: Relative(11), op: Add, bit_size: U32, lhs: Relative(9), rhs: Direct(2) }, BinaryIntOp { destination: Relative(13), op: Add, bit_size: U32, lhs: Relative(11), rhs: Relative(6) }, Load { destination: Relative(10), source_pointer: Relative(13) }, BinaryFieldOp { destination: Relative(9), op: Add, lhs: Relative(12), rhs: Relative(10) }, Store { destination_pointer: Relative(4), source: Relative(9) }, BinaryIntOp { destination: Relative(9), op: Add, bit_size: U32, lhs: Relative(3), rhs: Relative(6) }, Mov { destination: Relative(3), source: Relative(9) }, Jump { location: 53 }, Const { destination: Direct(32772), bit_size: Integer(U32), value: 30720 }, BinaryIntOp { destination: Direct(32771), op: LessThan, bit_size: U32, lhs: Direct(0), rhs: Direct(32772) }, JumpIf { condition: Direct(32771), location: 94 }, IndirectConst { destination_pointer: Direct(1), bit_size: Integer(U64), value: 17843811134343075018 }, Trap { revert_data: HeapVector { pointer: Direct(1), size: Direct(2) } }, Return, IndirectConst { destination_pointer: Direct(1), bit_size: Integer(U64), value: 16761564377371454734 }, Trap { revert_data: HeapVector { pointer: Direct(1), size: Direct(2) } }, Return]

unconstrained func 1

[Const { destination: Direct(2), bit_size: Integer(U32), value: 1 }, Const { destination: Direct(1), bit_size: Integer(U32), value: 49221 }, Const { destination: Direct(0), bit_size: Integer(U32), value: 3 }, Const { destination: Relative(2), bit_size: Integer(U32), value: 1 }, Const { destination: Relative(3), bit_size: Integer(U32), value: 0 }, CalldataCopy { destination_address: Direct(49219), size_address: Relative(2), offset_address: Relative(3) }, Cast { destination: Direct(49219), source: Direct(49219), bit_size: Integer(U32) }, Mov { destination: Relative(1), source: Direct(49219) }, Call { location: 14 }, Call { location: 44 }, Mov { destination: Direct(49220), source: Relative(1) }, Const { destination: Relative(2), bit_size: Integer(U32), value: 49220 }, Const { destination: Relative(3), bit_size: Integer(U32), value: 1 }, Stop { return_data: HeapVector { pointer: Relative(2), size: Relative(3) } }, Const { destination: Direct(32835), bit_size: Field, value: 1 }, Mov { destination: Direct(32836), source: Direct(1) }, Const { destination: Direct(32837), bit_size: Integer(U32), value: 3 }, BinaryIntOp { destination: Direct(1), op: Add, bit_size: U32, lhs: Direct(1), rhs: Direct(32837) }, IndirectConst { destination_pointer: Direct(32836), bit_size: Integer(U32), value: 1 }, BinaryIntOp { destination: Direct(32837), op: Add, bit_size: U32, lhs: Direct(32836), rhs: Direct(2) }, Mov { destination: Direct(32838), source: Direct(32837) }, Store { destination_pointer: Direct(32838), source: Direct(32835) }, BinaryIntOp { destination: Direct(32838), op: Add, bit_size: U32, lhs: Direct(32838), rhs: Direct(2) }, Store { destination_pointer: Direct(32838), source: Direct(32835) }, Const { destination: Direct(32837), bit_size: Field, value: 0 }, Mov { destination: Direct(32838), source: Direct(1) }, Const { destination: Direct(32839), bit_size: Integer(U32), value: 3 }, BinaryIntOp { destination: Direct(1), op: Add, bit_size: U32, lhs: Direct(1), rhs: Direct(32839) }, IndirectConst { destination_pointer: Direct(32838), bit_size: Integer(U32), value: 1 }, BinaryIntOp { destination: Direct(32839), op: Add, bit_size: U32, lhs: Direct(32838), rhs: Direct(2) }, Mov { destination: Direct(32840), source: Direct(32839) }, Store { destination_pointer: Direct(32840), source: Direct(32837) }, BinaryIntOp { destination: Direct(32840), op: Add, bit_size: U32, lhs: Direct(32840), rhs: Direct(2) }, Store { destination_pointer: Direct(32840), source: Direct(32837) }, Mov { destination: Direct(32839), source: Direct(1) }, Const { destination: Direct(32840), bit_size: Integer(U32), value: 3 }, BinaryIntOp { destination: Direct(1), op: Add, bit_size: U32, lhs: Direct(1), rhs: Direct(32840) }, IndirectConst { destination_pointer: Direct(32839), bit_size: Integer(U32), value: 1 }, BinaryIntOp { destination: Direct(32840), op: Add, bit_size: U32, lhs: Direct(32839), rhs: Direct(2) }, Mov { destination: Direct(32841), source: Direct(32840) }, Store { destination_pointer: Direct(32841), source: Direct(32836) }, BinaryIntOp { destination: Direct(32841), op: Add, bit_size: U32, lhs: Direct(32841), rhs: Direct(2) }, Store { destination_pointer: Direct(32841), source: Direct(32838) }, Return, Call { location: 55 }, Const { destination: Relative(2), bit_size: Integer(U32), value: 1 }, BinaryIntOp { destination: Relative(3), op: Add, bit_size: U32, lhs: Relative(1), rhs: Relative(2) }, BinaryIntOp { destination: Relative(4), op: LessThanEquals, bit_size: U32, lhs: Relative(1), rhs: Relative(3) }, JumpIf { condition: Relative(4), location: 50 }, Call { location: 61 }, BinaryIntOp { destination: Relative(1), op: Add, bit_size: U32, lhs: Relative(3), rhs: Relative(2) }, BinaryIntOp { destination: Relative(4), op: LessThanEquals, bit_size: U32, lhs: Relative(3), rhs: Relative(1) }, JumpIf { condition: Relative(4), location: 54 }, Call { location: 61 }, Return, Const { destination: Direct(32772), bit_size: Integer(U32), value: 30720 }, BinaryIntOp { destination: Direct(32771), op: LessThan, bit_size: U32, lhs: Direct(0), rhs: Direct(32772) }, JumpIf { condition: Direct(32771), location: 60 }, IndirectConst { destination_pointer: Direct(1), bit_size: Integer(U64), value: 17843811134343075018 }, Trap { revert_data: HeapVector { pointer: Direct(1), size: Direct(2) } }, Return, IndirectConst { destination_pointer: Direct(1), bit_size: Integer(U64), value: 5019202896831570965 }, Trap { revert_data: HeapVector { pointer: Direct(1), size: Direct(2) } }, Return]

If you run a diff on the Brillig for unconstrained func 0 and 1 you will be see a large chunk of identical Brillig code (it starts with Const { destination: Direct(32835), bit_size: Field, value: 1 }). This is the globals initialization.

To outline this more clearly this is the output of --show-brillig

Details

GlobalInit:
CONST M32835 = 1
MOV M32836, FreeMem
CONST M32837 = 3
FreeMem = FreeMem + M32837
ICONST M32836 = 1
M32837 = M32836 + M2
MOV M32838, M32837
STORE *M32838 = M32835
M32838 = M32838 + M2
STORE *M32838 = M32835
CONST M32837 = 0
MOV M32838, FreeMem
CONST M32839 = 3
FreeMem = FreeMem + M32839
ICONST M32838 = 1
M32839 = M32838 + M2
MOV M32840, M32839
STORE *M32840 = M32837
M32840 = M32840 + M2
STORE *M32840 = M32837
MOV M32839, FreeMem
CONST M32840 = 3
FreeMem = FreeMem + M32840
ICONST M32839 = 1
M32840 = M32839 + M2
MOV M32841, M32840
STORE *M32841 = M32836
M32841 = M32841 + M2
STORE *M32841 = M32838
RETURN
Function(Id(1), None):
CALL Procedure(CheckMaxStackDepth)

... continued Brillig

GlobalsInit is the first external call of every entry point. You can see that the globals_init flag is set to true for all calls to gen_brillig_for:

noir/compiler/noirc_evaluator/src/brillig/brillig_gen.rs

Line 65 in c8d5ce5

true,

To Reproduce

1. Make a new program with nargo and copy the program above
2. Run nargo execute --show-ssa --show-brillig --print-acir to see all the relevant output.
3. Observe that there is only one GlobalsInit function and it is reused for the two different Brillig entry points called from ACIR

Workaround

None

Workaround Description

No response

Additional Context

No response

Project Impact

Blocker

Blocker Context

I am marking this is a blocker as it is a pretty meaningful cost that cannot be avoided when using globals

Nargo Version

nargo version = 1.0.0-beta.1 noirc version = 1.0.0-beta.1+02056d6a3ca2932a0062552859195a4e3b11f9dc (git version hash: 02056d6, is dirty: true)

NoirJS Version

No response

Proving Backend Tooling & Version

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response