Induction variable elimination

[vezenovm]

Problem

If we have some loop:

for i in 0..10 {
     println(a[i]);
}

When a contains composite types, we currently will generate extra operations for array indexing.

An example SSA loop body:

    jmp b27(u32 0)
  b27(v12: u32):
    v200 = lt v12, u32 10
    jmpif v200 then: b29, else: b28
  b29():
    v201 = mul v12, u32 2
    v202 = array_get v165, index v201 -> [Field; 3]
    v203 = add v201, u32 1
    v204 = array_get v165, index v203 -> [(Field, [Field; 3], [Field; 3]); 4]
    call v205(u1 1, v202, v204, v198, u1 0)
    v207 = add v12, u32 1
    jmp b27(v207)

v12 is our loop's basic induction variable. We know that v201 = mul v12, u32 2 is a derived induction variable. Which means that v201 is a linear function of a basic induction variable v = c * i + d, where c and d are loop invariants. We should be able to transform our loop to only perform only an addition in the loop and move the multiplication out of the loop.

Happy Case

From the loop header in the snippet above:

    jmp b27(u32 0)
  b27(v12: u32):
    v200 = lt v12, u32 10
    jmpif v200 then: b29, else: b28
  b29():
    v201 = mul v12, u32 2
    ...
    ...
    v207 = add v12, u32 1
    jmp b27(v207)

We know that the upper bound of our loop is 10. Knowing that our induction variable is v201 = mul v12, u32 2 we should be able to rewrite our loop as such:

    v200 = mul u32 10, u32 2
    jmp b27(u32 0)
  b27(v12: u32):
    v201 = lt v12, u32 v200
    jmpif v201 then: b29, else: b28
  b29():
    ...
    ...
    v207 = add v12, u32 2
    jmp b27(v207)

After propagating the new instructions following induction variable elimination, let's take a look at the remaining instructions in b29 from above. We can see how this largely simplifies array indexing.

    v200 = mul u32 10, u32 2
    jmp b27(u32 0)
  b27(v12: u32):
    v201 = lt v12, u32 v200
    jmpif v201 then: b29, else: b28
  b29():
    v202 = array_get v165, index v12 -> [Field; 3]
    v203 = add v12, u32 1
    v204 = array_get v165, index v203 -> [(Field, [Field; 3], [Field; 3]); 4]
    call v205(u1 1, v202, v204, v198, u1 0)
    v207 = add v12, u32 2
    jmp b27(v207)

For more info these slides from CMU are very helpful:
https://www.cs.cmu.edu/afs/cs/academic/class/15745-s19/www/lectures/L8-Induction-Variables.pdf

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