SSA: Enable mem2reg to be per function rather than per block

[vezenovm]

Problem

The mem2reg pass is currently done in a single block context. This means that values which contain loads whose results are known from store instructions in previous blocks will not be removed. This causes issues in a couple situations:

In #1889, merging of slices occurs during flattening of the CFG. However, mem2reg currently occurs after flattening (because we can perform mem2reg on one flattened block). Thus, we cannot merge slices in flattening as we have not loaded the array value that was stored in a previous block. Being able to resolve loads from stores in previous blocks will enable us to handle merge slices in flattening.

In #1035 as per #1035 (comment) moving the mem2reg pass before unrolling fixes the issue, however, due to mem2reg being per block rather than per function other bugs are not caught. Firstly, the issue of slices not being correctly loaded for merge_slices still exists. Moving the mem2reg pass before unrolling also causes this snippet to be incorrect:

fn main(x : Field, y : pub Field) {
    let q = &mut &mut 0;
    let q1 = *q;
    let q2 = *q;

    if x != y {
        *q1 = 1;
        // mem2reg will know q1 = 1, but not that q2 = 1
        *q2 = 2; // now we'd expect q1 == q2 == 2, but mem2reg now thinks q1 = 1 & q2 = 2
        
        // This now passes and we've broken mem2reg :(
        assert(*q1 == 1);
    }
}

We should expect assert(*q1 == 1) to fail. This failure occurs with how the SSA is currently set-up but with the limitations listed above.

Happy Case

We should be able to easily reorder mem2reg in the SSA. This will require mem2reg to run with a context per function rather than per block. After moving mem2reg before unrolling, the current functionality of the SSA should not be reduced and the issues listed in the Problem section should be addressed.

Alternatives Considered

N/A

In order for merge_slices to still occur in flattening there is really no other option than being able to resolve loads from stores in previous blocks. Otherwise, flattening of slice would start to get unnecessarily complex. Switching to per function for mem2reg will potentially also fix other bugs along with providing functionality for the merger of slices.

Additional Context

No response

Would you like to submit a PR for this Issue?

No

Support Needs

No response