Bug in Incremental SSA Construction

[dibyendumajumdar]

The following code generates bad IR:

func sieve(N: Int)->[Int]
{
    // The main Sieve array
    var ary = new [Int]{len=N,value=0}
    // The primes less than N
    var primes = new [Int]{len=N/2,value=0}
    // Number of primes so far, searching at index p
    var nprimes = 0
    var p=2
    // Find primes while p^2 < N
    while( p*p < N ) {
        // skip marked non-primes
        while( ary[p] ) {
            p = p + 1
        }
        // p is now a prime
        primes[nprimes] = p
        nprimes = nprimes+1
        // Mark out the rest non-primes
        var i = p + p
        while( i < N ) {
            ary[i] = 1
            i = i + p
        }
        p = p + 1
    }

    // Now just collect the remaining primes, no more marking
    while ( p < N ) {
        if( !ary[p] ) {
            primes[nprimes] = p
            nprimes = nprimes + 1
        }
        p = p + 1
    }

    // Copy/shrink the result array
    var rez = new [Int]{len=nprimes,value=0}
    var j = 0
    while( j < nprimes ) {
        rez[j] = primes[j]
        j = j + 1
    }
    return rez
}
func eq(a: [Int], b: [Int], n: Int)->Int
{
    var result = 1
    var i = 0
    while (i < n)
    {
        if (a[i] != b[i])
        {
            result = 0
            break
        }
        i = i + 1
    }
    return result
}

func main()->Int
{
    var rez = sieve(20)
    var expected = new [Int]{2,3,5,7,11,13,17,19}
    return eq(rez,expected,8)
}

IR generated:

L0:
    arg N
    %t8 = New([Int], len=N, initValue=0)
    ary = %t8
    %t10 = N/2
    %t9 = New([Int], len=%t10, initValue=0)
    primes = %t9
    nprimes = 0
    p = 2
    goto  L2
L2:
    nprimes_2 = phi(nprimes, nprimes_3)
    ary_2 = phi(ary, ary_3)
    N_1 = phi(N, N_2)
    p_1 = phi(p, p_5)
    %t11 = p_1*p_1
    %t13 = %t11<N_1
    if %t13 goto L3 else goto L4
L3:
    goto  L5
L5:
    p_2 = phi(p_1, p_3)
    %t15 = ary_2[p_2]
    if %t15 goto L6 else goto L7
L6:
    %t18 = p_2+1
    p_3 = %t18
    goto  L5
L7:
    primes[nprimes_2] = p_2
    %t25 = nprimes_2+1
    nprimes_3 = %t25
    %t27 = p_2+p_2
    i = %t27
    goto  L8
L8:
    i_1 = phi(i, i_2)
    %t28 = i_1<N_1
    if %t28 goto L9 else goto L10
L9:
    ary_1[i_1] = 1
    %t32 = i_1+p_2
    i_2 = %t32
    goto  L8
L10:
    %t36 = p_4+1
    p_5 = %t36
    goto  L2
L4:
    goto  L11
L11:
    nprimes_5 = phi(nprimes_2, nprimes_7)
    p_6 = phi(p_1, p_8)
    %t40 = p_6<N_1
    if %t40 goto L12 else goto L13
L12:
    %t43 = ary_2[p_6]
    %t45 = !%t43
    if %t45 goto L14 else goto L15
L14:
    primes_2[nprimes_5] = p_6
    %t48 = nprimes_5+1
    nprimes_6 = %t48
    goto  L15
L15:
    nprimes_7 = phi(nprimes_5, nprimes_6)
    %t50 = p_6+1
    p_8 = %t50
    goto  L11
L13:
    %t57 = New([Int], len=nprimes_5, initValue=0)
    rez = %t57
    j = 0
    goto  L16
L16:
    j_1 = phi(j, j_2)
    %t58 = j_1<nprimes_5
    if %t58 goto L17 else goto L18
L17:
    %t61 = primes_4[j_1]
    rez[j_1] = %t61
    %t64 = j_1+1
    j_2 = %t64
    goto  L16
L18:
    ret rez_1
    goto  L1
L1:

Issues

L9:
    ary_1[i_1] = 1

L10:
    %t36 = p_4+1