Index: llvm/trunk/utils/shuffle_select_fuzz_tester.py =================================================================== --- llvm/trunk/utils/shuffle_select_fuzz_tester.py +++ llvm/trunk/utils/shuffle_select_fuzz_tester.py @@ -0,0 +1,404 @@ +#!/usr/bin/env python + +"""A shuffle-select vector fuzz tester. + +This is a python program to fuzz test the LLVM shufflevector and select +instructions. It generates a function with a random sequnece of shufflevectors +while optionally attaching it with a select instruction (regular or zero merge), +maintaining the element mapping accumulated across the function. It then +generates a main function which calls it with a different value in each element +and checks that the result matches the expected mapping. + +Take the output IR printed to stdout, compile it to an executable using whatever +set of transforms you want to test, and run the program. If it crashes, it found +a bug (an error message with the expected and actual result is printed). +""" + +import random +import uuid +import argparse + +# Possibility of one undef index in generated mask for shufflevector instruction +SHUF_UNDEF_POS = 0.15 + +# Possibility of one undef index in generated mask for select instruction +SEL_UNDEF_POS = 0.15 + +# Possibility of adding a select instruction to the result of a shufflevector +ADD_SEL_POS = 0.4 + +# If we are adding a select instruction, this is the possibility of a +# merge-select instruction (1 - MERGE_SEL_POS = possibility of zero-merge-select +# instruction. +MERGE_SEL_POS = 0.5 + + +test_template = r''' +define internal fastcc {ty} @test({inputs}) noinline nounwind {{ +entry: +{instructions} + ret {ty} {last_name} +}} +''' + +error_template = r'''@error.{lane} = private unnamed_addr global [64 x i8] c"FAIL: lane {lane}, expected {exp}, found %d\0A{padding}"''' + +main_template = r''' +define i32 @main() {{ +entry: + ; Create a scratch space to print error messages. + %str = alloca [64 x i8] + %str.ptr = getelementptr inbounds [64 x i8], [64 x i8]* %str, i32 0, i32 0 + + ; Build the input vector and call the test function. + %v = call fastcc {ty} @test({inputs}) + br label %test.0 + + {check_die} +}} + +declare i32 @strlen(i8*) +declare i32 @write(i32, i8*, i32) +declare i32 @sprintf(i8*, i8*, ...) +declare void @llvm.trap() noreturn nounwind +''' + +check_template = r''' +test.{lane}: + %v.{lane} = extractelement {ty} %v, i32 {lane} + %cmp.{lane} = {i_f}cmp {ordered}ne {scalar_ty} %v.{lane}, {exp} + br i1 %cmp.{lane}, label %die.{lane}, label %test.{n_lane} +''' + +undef_check_template = r''' +test.{lane}: +; Skip this lane, its value is undef. + br label %test.{n_lane} +''' + +die_template = r''' +die.{lane}: +; Capture the actual value and print an error message. + call i32 (i8*, i8*, ...) @sprintf(i8* %str.ptr, i8* getelementptr inbounds ([64 x i8], [64 x i8]* @error.{lane}, i32 0, i32 0), {scalar_ty} %v.{lane}) + %length.{lane} = call i32 @strlen(i8* %str.ptr) + call i32 @write(i32 2, i8* %str.ptr, i32 %length.{lane}) + call void @llvm.trap() + unreachable +''' + +class Type: + def __init__(self, is_float, elt_width, elt_num): + self.is_float = is_float # Boolean + self.elt_width = elt_width # Integer + self.elt_num = elt_num # Integer + + def dump(self): + if self.is_float: + str_elt = 'float' if self.elt_width == 32 else 'double' + else: + str_elt = 'i' + str(self.elt_width) + + if self.elt_num == 1: + return str_elt + else: + return '<' + str(self.elt_num) + ' x ' + str_elt + '>' + + def get_scalar_type(self): + return Type(self.is_float, self.elt_width, 1) + + + +# Class to represent any value (variable) that can be used. +class Value: + def __init__(self, name, ty, value = None): + self.ty = ty # Type + self.name = name # String + self.value = value # list of integers or floating points + + +# Class to represent an IR instruction (shuffle/select). +class Instruction(Value): + def __init__(self, name, ty, op0, op1, mask): + Value.__init__(self, name, ty) + self.op0 = op0 # Value + self.op1 = op1 # Value + self.mask = mask # list of integers + + def dump(self): pass + + def calc_value(self): pass + + +# Class to represent an IR shuffle instruction +class ShufInstr(Instruction): + + shuf_template = ' {name} = shufflevector {ty} {op0}, {ty} {op1}, <{num} x i32> {mask}\n' + + def __init__(self, name, ty, op0, op1, mask): + Instruction.__init__(self, '%shuf' + name, ty, op0, op1, mask) + + def dump(self): + str_mask = [('i32 ' + str(idx)) if idx != -1 else 'i32 undef' for idx in self.mask] + str_mask = '<' + (', ').join(str_mask) + '>' + return self.shuf_template.format(name = self.name, ty = self.ty.dump(), op0 = self.op0.name, + op1 = self.op1.name, num = self.ty.elt_num, mask = str_mask) + + def calc_value(self): + if self.value != None: + print 'Trying to calculate the value of a shuffle instruction twice' + exit(1) + + result = [] + for i in range(len(self.mask)): + index = self.mask[i] + + if index < self.ty.elt_num and index >= 0: + result.append(self.op0.value[index]) + elif index >= self.ty.elt_num: + index = index % self.ty.elt_num + result.append(self.op1.value[index]) + else: # -1 => undef + result.append(-1) + + self.value = result + + +# Class to represent an IR select instruction +class SelectInstr(Instruction): + + sel_template = ' {name} = select <{num} x i1> {mask}, {ty} {op0}, {ty} {op1}\n' + + def __init__(self, name, ty, op0, op1, mask): + Instruction.__init__(self, '%sel' + name, ty, op0, op1, mask) + + def dump(self): + str_mask = [('i1 ' + str(idx)) if idx != -1 else 'i1 undef' for idx in self.mask] + str_mask = '<' + (', ').join(str_mask) + '>' + return self.sel_template.format(name = self.name, ty = self.ty.dump(), op0 = self.op0.name, + op1 = self.op1.name, num = self.ty.elt_num, mask = str_mask) + + def calc_value(self): + if self.value != None: + print 'Trying to calculate the value of a select instruction twice' + exit(1) + + result = [] + for i in range(len(self.mask)): + index = self.mask[i] + + if index == 1: + result.append(self.op0.value[i]) + elif index == 0: + result.append(self.op1.value[i]) + else: # -1 => undef + result.append(-1) + + self.value = result + + +# Returns a list of Values initialized with actual numbers according to the +# provided type +def gen_inputs(ty, num): + inputs = [] + for i in range(num): + inp = [] + for j in range(ty.elt_num): + if ty.is_float: + inp.append(float(i*ty.elt_num + j)) + else: + inp.append((i*ty.elt_num + j) % (1 << ty.elt_width)) + inputs.append(Value('%inp' + str(i), ty, inp)) + + return inputs + + +# Returns a random vector type to be tested +# In case one of the dimensions (scalar type/number of elements) is provided, +# fill the blank dimension and return appropriate Type object. +def get_random_type(ty, num_elts): + if ty != None: + if ty == 'i8': + is_float = False + width = 8 + elif ty == 'i16': + is_float = False + width = 16 + elif ty == 'i32': + is_float = False + width = 32 + elif ty == 'i64': + is_float = False + width = 64 + elif ty == 'f32': + is_float = True + width = 32 + elif ty == 'f64': + is_float = True + width = 64 + + int_elt_widths = [8, 16, 32, 64] + float_elt_widths = [32, 64] + + if num_elts == None: + num_elts = random.choice(range(2, 65)) + + if ty == None: + # 1 for integer type, 0 for floating-point + if random.randint(0,1): + is_float = False + width = random.choice(int_elt_widths) + else: + is_float = True + width = random.choice(float_elt_widths) + + return Type(is_float, width, num_elts) + + +# Generate mask for shufflevector IR instruction, with SHUF_UNDEF_POS possibility +# of one undef index. +def gen_shuf_mask(ty): + mask = [] + for i in range(ty.elt_num): + if SHUF_UNDEF_POS/ty.elt_num > random.random(): + mask.append(-1) + else: + mask.append(random.randint(0, ty.elt_num*2 - 1)) + + return mask + + +# Generate mask for select IR instruction, with SEL_UNDEF_POS possibility +# of one undef index. +def gen_sel_mask(ty): + mask = [] + for i in range(ty.elt_num): + if SEL_UNDEF_POS/ty.elt_num > random.random(): + mask.append(-1) + else: + mask.append(random.randint(0, 1)) + + return mask + +# Generate shuffle instructions with optional select instruction after. +def gen_insts(inputs, ty): + int_zero_init = Value('zeroinitializer', ty, [0]*ty.elt_num) + float_zero_init = Value('zeroinitializer', ty, [0.0]*ty.elt_num) + + insts = [] + name_idx = 0 + while len(inputs) > 1: + # Choose 2 available Values - remove them from inputs list. + [idx0, idx1] = sorted(random.sample(range(len(inputs)), 2)) + op0 = inputs[idx0] + op1 = inputs[idx1] + + # Create the shuffle instruction. + shuf_mask = gen_shuf_mask(ty) + shuf_inst = ShufInstr(str(name_idx), ty, op0, op1, shuf_mask) + shuf_inst.calc_value() + + # Add the new shuffle instruction to the list of instructions. + insts.append(shuf_inst) + + # Optionally, add select instruction with the result of the previous shuffle. + if random.random() < ADD_SEL_POS: + # Either blending with a random Value or with an all-zero vector. + if random.random() < MERGE_SEL_POS: + op2 = random.choice(inputs) + else: + op2 = float_zero_init if ty.is_float else int_zero_init + + select_mask = gen_sel_mask(ty) + select_inst = SelectInstr(str(name_idx), ty, shuf_inst, op2, select_mask) + select_inst.calc_value() + + # Add the select instructions to the list of instructions and to the available Values. + insts.append(select_inst) + inputs.append(select_inst) + else: + # If the shuffle instruction is not followed by select, add it to the available Values. + inputs.append(shuf_inst) + + del inputs[idx1] + del inputs[idx0] + name_idx += 1 + + return insts + + +def main(): + parser = argparse.ArgumentParser(description=__doc__) + parser.add_argument('--seed', default=str(uuid.uuid4()), + help='A string used to seed the RNG') + parser.add_argument('--max-num-inputs', type=int, default=20, + help='Specify the maximum number of vector inputs for the test. (default: 20)') + parser.add_argument('--min-num-inputs', type=int, default=10, + help='Specify the minimum number of vector inputs for the test. (default: 10)') + parser.add_argument('--type', default=None, + help=''' + Choose specific type to be tested. + i8, i16, i32, i64, f32 or f64. + (default: random)''') + parser.add_argument('--num-elts', default=None, type=int, + help='Choose specific number of vector elements to be tested. (default: random)') + args = parser.parse_args() + + print '; The seed used for this test is ' + args.seed + + assert args.min_num_inputs < args.max_num_inputs , "Minimum value greater than maximum." + assert args.type in [None, 'i8', 'i16', 'i32', 'i64', 'f32', 'f64'], "Illegal type." + assert args.num_elts == None or args.num_elts > 0, "num_elts must be a positive integer." + + random.seed(args.seed) + ty = get_random_type(args.type, args.num_elts) + inputs = gen_inputs(ty, random.randint(args.min_num_inputs, args.max_num_inputs)) + inputs_str = (', ').join([inp.ty.dump() + ' ' + inp.name for inp in inputs]) + inputs_values = [inp.value for inp in inputs] + + insts = gen_insts(inputs, ty) + + assert len(inputs) == 1, "Only one value should be left after generating phase" + res = inputs[0] + + # print the actual test function by dumping the generated instructions. + insts_str = ''.join([inst.dump() for inst in insts]) + print test_template.format(ty = ty.dump(), inputs = inputs_str, + instructions = insts_str, last_name = res.name) + + # Print the error message templates as global strings + for i in range(len(res.value)): + pad = ''.join(['\\00']*(31 - len(str(i)) - len(str(res.value[i])))) + print error_template.format(lane = str(i), exp = str(res.value[i]), + padding = pad) + + # Prepare the runtime checks and failure handlers. + scalar_ty = ty.get_scalar_type() + check_die = '' + i_f = 'f' if ty.is_float else 'i' + ordered = 'o' if ty.is_float else '' + for i in range(len(res.value)): + if res.value[i] != -1: + # Emit runtime check for each non-undef expected value. + check_die += check_template.format(lane = str(i), n_lane = str(i+1), + ty = ty.dump(), i_f = i_f, scalar_ty = scalar_ty.dump(), + exp = str(res.value[i]), ordered = ordered) + # Emit failure handler for each runtime check with proper error message + check_die += die_template.format(lane = str(i), scalar_ty = scalar_ty.dump()) + else: + # Ignore lanes with undef result + check_die += undef_check_template.format(lane = str(i), n_lane = str(i+1)) + + check_die += '\ntest.' + str(len(res.value)) + ':\n' + check_die += ' ret i32 0' + + # Prepare the input values passed to the test function. + inputs_values = [', '.join([scalar_ty.dump() + ' ' + str(i) for i in inp]) for inp in inputs_values] + inputs = ', '.join([ty.dump() + ' <' + inp + '>' for inp in inputs_values]) + + print main_template.format(ty = ty.dump(), inputs = inputs, check_die = check_die) + + +if __name__ == '__main__': + main() + +