It’s hard to get optimizers right. Even if you build up a painstaking test suite by hand, you will likely miss corner cases, especially corner cases at the interactions of multiple components or multiple optimization passes.
I wanted to see if I could write a fuzzer to catch some of these bugs automatically. But a fuzzer alone isn’t much use without some correctness oracle—in this case, we want a more interesting bug than accidentally crashing the optimizer. We want to see if the optimizer introduces a correctness bug in the program.
So I set off in the most straightforward way possible, inspired by my hazy memories of a former CF blog post.
Generating programs
Generating random programs isn’t so bad. We have program generation APIs and we can dynamically pick which ones we want to call. I wrote a small loop that generates load s from and store s to the arguments at random offsets and with random values, and escape s to random instructions with outputs. The idea with the escape is to keep track of the values as if there was some other function relying on them.
def generate_program (): bb = Block () args = [ bb . getarg ( i ) for i in range ( 3 )] num_ops = random . randint ( 0 , 30 ) ops_with_values = args [:] for _ in range ( num_ops ): op = random . choice ([ "load" , "store" , "escape" ]) arg = random . choice ( args ) a_value = random . choice ( ops_with_values ) offset = random . randint ( 0 , 4 ) if op == "load" : v = bb . load ( arg , offset ) ops_with_values . append ( v ) elif op == "store" : value = random . randint ( 0 , 10 ) bb . store ( arg , offset , value ) elif op == "escape" : bb . escape ( a_value ) else : raise NotImplementedError ( f "Unknown operation { op } " ) return bb
This generates random programs. Here is an example stringified random program:
var0 = getarg(0) var1 = getarg(1) var2 = getarg(2) var3 = load(var2, 0) var4 = load(var0, 1) var5 = load(var1, 1) var6 = escape(var0) var7 = store(var0, 2, 3) var8 = store(var2, 0, 7)
No idea what would generate something like this, but oh well.
Verifying programs
... continue reading