Add SSA optimization pass to hoist instructions out of blocks to deduplicate them or hoist them out of loops

[jfecher]

Problem

Certain instructions used in loops may be unnecessarily executed on each iteration of the loop. This can happen if the instruction only depends on other values used outside the loop. For example, the program:

unconstrained fn main(x: u32) {
    for _ in 0 .. 10 {
        println(x + 1);
    }
}

Currently produces the SSA:

brillig(inline) fn main f0 {
  b0(v0: u32):
    jmp b1(u32 0)
  b1(v1: u32):
    v4 = lt v1, u32 10
    jmpif v4 then: b3, else: b2
  b3():
    v6 = add v0, u32 1
    call v7(u1 1, v6, [u8 123, u8 34, u8 107, u8 105, u8 110, u8 100, u8 34, u8 58, u8 34, u8 117, u8 110, u8 115, u8 105, u8 103, u8 110, u8 101, u8 100, u8 105, u8 110, u8 116, u8 101, u8 103, u8 101, u8 114, u8 34, u8 44, u8 34, u8 119, u8 105, u8 100, u8 116, u8 104, u8 34, u8 58, u8 51, u8 50, u8 125] of u8, u1 0)
    v30 = add v1, u32 1
    jmp b1(v30)
  b2():
    return
}

Happy Case

We can hoist instructions like v6 out of their blocks to their earliest ancestor to get the SSA:

brillig(inline) fn main f0 {
  b0(v0: u32):
    v6 = add v0, u32 1
    jmp b1(u32 0)
  b1(v1: u32):
    v4 = lt v1, u32 10
    jmpif v4 then: b3, else: b2
  b3():
    call v7(u1 1, v6, [u8 123, u8 34, u8 107, u8 105, u8 110, u8 100, u8 34, u8 58, u8 34, u8 117, u8 110, u8 115, u8 105, u8 103, u8 110, u8 101, u8 100, u8 105, u8 110, u8 116, u8 101, u8 103, u8 101, u8 114, u8 34, u8 44, u8 34, u8 119, u8 105, u8 100, u8 116, u8 104, u8 34, u8 58, u8 51, u8 50, u8 125] of u8, u1 0)
    v30 = add v1, u32 1
    jmp b1(v30)
  b2():
    return
}

The downside of this optimization is that if we apply this for blocks in general we could move instructions out of rarely-executed else blocks and into the happy path.

Another benefit of this optimization is that it allows more instructions to be deduplicated by constant folding since moving instructions to their dependency's common ancestor is much more permissive than checking if the first usage of an instruction dominates each other usage. For example, if we have the program if foo { ... }; if bar { ... }; if baz { ... }, each if body could be duplicated but none dominate each other since it is possible the else branch could have been taken each time. If we hoist to before the first if however, we'd deduplicate the blocks at the cost of executing extra instructions in the else case.

Since this could be a tradeoff in guessing how many times certain blocks may be executed, we could implement an alternate version of this change to start out with: only hoist if the instruction is used multiple times. That way, we could still execute unnecessary instructions but we'd at least guarantee to optimize out (deduplicate) 1 instance of the same instruction.

Workaround

None

Workaround Description

No response

Additional Context

No response

Project Impact

None

Blocker Context

No response

Would you like to submit a PR for this Issue?

None

Support Needs

No response