Debugging Optimizing Compiler

Introduction

Some notes on how I debug the compiler.

Problem

The following example failed to run when run through the SSA/optimization pipeline.

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)
}

Error during execution indicated attempt to access a stack location (in the function frame) where no value was present.

I used debugger to put a break point on the exception and looked at the instruction / call stack. The failure appeared to occur in sieve function.

Below is part of the final IR leading up to the problem line:

L0:
    arg N_0
    %t8_0 = New([Int], len=N_0, initValue=0)
    %t10_0 = N_0/2
    %t9_0 = New([Int], len=%t10_0, initValue=0)
    %t19_0 = 2
    %t15_0 = 0
    goto  L2
L2:
    %t11_0 = %t19_0*%t19_0
    %t12_0 = %t11_0<N_0
    if %t12_0 goto L3 else goto L4
L3:
    %t14_0 = %t24_0
    goto  L5
L5:
    %t13_0 = %t8_0[%t14_0]

The issue above is that %t14_0 is assigned %t24_0 but latter is not defined yet...

The Incremental SSA version failed too, but the error was different, so indicated a different issue.

Clearly the generated IR is incorrect.

My first step was to disable the SCCP passes to see if it made a difference. The same error occurred.

Next step was to create an SSA test case and see if the transform to SSA was correct. I found that there was an issue with the sieve function, when transforming via the Dominator method. Braun's method seemed okay, but given the test using this was also failing, albeit with a different error, this indicated that there was more than just 1 error happening.

My next step was to try to create a small reproducible test case, initially just for the SSA transform.

I noticed that the error was happening with regards to the variable p. This variable is used in two while loops, and some conditional branches inside the loop. I thought maybe that the issue was related to the fact that the variable was interacting badly with arrays, or there was an issue because of its use in two separate loops.

I eliminated the arrays access and saw that the problem still occurred.

I was able to cut down the problem case to the following snippet:

func bug(N: Int)
{
    var p=2
    while( p < N ) {
        if (p) {
            p = p + 1
        }
    }
    while ( p < N ) {
        p = p + 1
    }
}

This generated following under the Dominator based SSA construction:

L0:
    arg N_0
    p_0 = 2
    goto  L2
L2:
    p_1 = phi(p_0, p_5)
    %t2_0 = p_1<N_0
    if %t2_0 goto L3 else goto L4
L3:
    if p_2 goto L5 else goto L6
L5:
    %t3_0 = p_2+1
    p_4 = %t3_0
    goto  L6
L6:
    p_5 = phi(p_2, p_4)
    goto  L2
L4:
    goto  L7
L7:
    p_2 = phi(p_1, p_3)
    %t4_0 = p_2<N_0
    if %t4_0 goto L8 else goto L9
L8:
    %t5_0 = p_2+1
    p_3 = %t5_0
    goto  L7
L9:
    goto  L1
L1:

The issue is in L3 basic block, where p2 is accessed but this is not yet defined.

Braun's method appears to generate correct SSA:

L0:
    arg N
    p = 2
    goto  L2
L2:
    p_1 = phi(p, p_3)
    %t2 = p_1<N
    if %t2 goto L3 else goto L4
L3:
    if p_1 goto L5 else goto L6
L5:
    %t5 = p_1+1
    p_2 = %t5
    goto  L6
L6:
    p_3 = phi(p_1, p_2)
    goto  L2
L4:
    goto  L7
L7:
    p_4 = phi(p_1, p_5)
    %t9 = p_4<N_1
    if %t9 goto L8 else goto L9
L8:
    %t12 = p_4+1
    p_5 = %t12
    goto  L7
L9:
    goto  L1
L1:

Given that even the test cases failed when using Braun's method of SSA construction, I think that more than one error is present. Since we also use a Dominator based method to exit from SSA, potentially this could also be where there are issues, in which case it is worth checking that the Dominator tree is correct for above program.

Control Flow Graph

Here is the control flow graph