feat: avoid unnecessary witness assignments in euclidian division / bound constraint

[TomAFrench]

Description

Problem*

Consider the program

fn main(x: u8) -> pub u8 {
    x >> 2 
}

This is currently compiled as

Compiled ACIR for main:
current witness index : 7
public parameters indices : []
return value indices : [2]
BLACKBOX::RANGE [(_1, num_bits: 8)] [ ]
DIR::QUOTIENT PREDICATE = %EXPR [ 1 ]%
(out : _x1,  (_2, %EXPR [ 4 ]%), _3)
BLACKBOX::RANGE [(_2, num_bits: 8)] [ ]
BLACKBOX::RANGE [(_3, num_bits: 8)] [ ]
EXPR [ (1, _3) (-1, _4) 0 ]
BLACKBOX::RANGE [(_4, num_bits: 2)] [ ]
EXPR [ (-1, _5) 4 ]
EXPR [ (1, _2, _5) (1, _3) (-1, _6) 0 ]
EXPR [ (1, _1) (-1, _7) 0 ]
EXPR [ (-1, _6) (1, _7) 0 ]

This creates a lot of unnecessary witnesses (w1 == w6 == w7, w5 is used only to introduce a constant). This is due to euclidian division acir gen creating 3 new witnesses unconditionally even if the expression is already degree 1 or less.

Summary*

This PR uses mul_with_witness to only create new witnesses if they're absolutely necessary. The same program now compiles down to the ACIR below

Compiled ACIR for main:
current witness index : 3
public parameters indices : []
return value indices : [2]
BLACKBOX::RANGE [(_1, num_bits: 8)] [ ]
DIR::QUOTIENT PREDICATE = %EXPR [ 1 ]%
(out : _x1,  (_2, %EXPR [ 4 ]%), _3)
BLACKBOX::RANGE [(_2, num_bits: 8)] [ ]
BLACKBOX::RANGE [(_3, num_bits: 8)] [ ] // Will be optimized away by ACVM.
BLACKBOX::RANGE [(_3, num_bits: 2)] [ ]
EXPR [ (1, _1) (-4, _2) (-1, _3) 0 ]

This also includes an optimisation I noticed in bound_constraint_with_offset where we're also unconditionally creating new witnesses.

Documentation

• This PR requires documentation updates when merged.

  • I will submit a noir-lang/docs PR.
  • I will request for and support Dev Rel's help in documenting this PR.

Additional Context

PR Checklist*

• I have tested the changes locally.
• I have formatted the changes with Prettier and/or cargo fmt on default settings.

[kevaundray]

LGTM - mul_with_witness should likely not live in sort.rs but in generated_acir.rs as its not only used for sorting

[TomAFrench]

Agreed, I wanted to avoid conflicts with #1980 however.