Block scoped store/load -> folding simplifcation

[joss-aztec]

Problem

The following contains an unnecessary load instruction:

fn foo(x: [Field; 2]) -> Field {
  x[0] = 1;
  x[0] = 2;
  x[0]
}

foo {
  block0(x: pointer):
    v0 = mul Field 0, Field 1
    v1 = add x, v0
    store Field 1, v1
    store Field 2, v1
    v2 = load v1
    return v2
}

This could be simplified to:

foo {
  block0(x: pointer):
    v0 = mul Field 0, Field 1
    v1 = add x, v0
    store Field 1, v1
    store Field 2, v1
    return Field 2
}

Proposed solution

For each block:

• record the last store instruction for each array
• when you see a load instruction to the same array (same array = ValueIds are equal), replace it with the value of the last store in the current block, if known
• don’t remember anything across blocks for simplicity. Leave it to other passes to simplify block structure

Alternatives considered

No response

Additional context

No response

Submission Checklist

• Once I hit submit, I will assign this issue to the Project Board with the appropriate tags.

[joss-aztec]

Tagging @jfecher to check I've documented the issue correctly

[jfecher]

Right, the ssa refactor doesn't have a load/store/mem2reg pass at all yet which is one of the passes it will need to be able to compile to ACIR. Your proposed solution is pretty much what I had in mind as well regarding the basic flow of the pass - though we should also remove unnecessary store instructions. So the final IR would be:

fn foo {
  block0(v0: reference):
    v1 = mul Field 0, Field 1
    v2 = add v0, v1
    return Field 2
}

A pass to remove unused instructions afterwards would be nice as well, but it is lower priority since it isn't strictly necessary to generate ACIR.
Edit: The constant folding PR was just merged which will actually fold away both v1 and v2 anyway.

[joss-aztec]

Your proposed solution is pretty much what I had in mind

It precisely is - since I merely copy and pasted from chat ;)

we should also remove unnecessary store instructions

By which I suppose you're referring to stores to the same address (without a function call in between)? I think anything else would require analysis beyond the scope of the block in question.

[jfecher]

By which I suppose you're referring to stores to the same address (without a function call in between)? I think anything else would require analysis beyond the scope of the block in question.

Right, and to elaborate on goals a bit my goal for structuring this pass with the simple "separate/fresh context for each block" approach was to have the pass:

• Eliminate all loads and stores if run as the last SSA pass when there is only a single block (and no non-intrinsic function calls) in the code
• Still work if run earlier when there are multiple blocks, simplifying the program where possible.

I think we may be able to count the loads that we failed to remove (per-allocation if possible) and then if this is 0 we can remove the allocate instruction and all stores to the array as well since it is never loaded from. We could also add this in a later PR though since it is functionally separate from the original pass of removing known loads.

[joss-aztec]

Since I was short of time I've focused on the last SSA pass use case. The PR could probably be adapted to handle both cases without too much work. Feel free to modify if you need this work merged before I get back (I'm off Thursday/Friday).