utils/shuffle_select_fuzz_tester.py

   1 #!/usr/bin/env python
   2
   3 """A shuffle-select vector fuzz tester.
   4
   5 This is a python program to fuzz test the LLVM shufflevector and select
   6 instructions. It generates a function with a random sequnece of shufflevectors
   7 while optionally attaching it with a select instruction (regular or zero merge),
   8 maintaining the element mapping accumulated across the function. It then
   9 generates a main function which calls it with a different value in each element
  10 and checks that the result matches the expected mapping.
  11
  12 Take the output IR printed to stdout, compile it to an executable using whatever
  13 set of transforms you want to test, and run the program. If it crashes, it found
  14 a bug (an error message with the expected and actual result is printed).
  15 """
  16
  17 import random
  18 import uuid
  19 import argparse
  20
  21 # Possibility of one undef index in generated mask for shufflevector instruction
  22 SHUF_UNDEF_POS = 0.15
  23
  24 # Possibility of one undef index in generated mask for select instruction
  25 SEL_UNDEF_POS = 0.15
  26
  27 # Possibility of adding a select instruction to the result of a shufflevector
  28 ADD_SEL_POS = 0.4
  29
  30 # If we are adding a select instruction, this is the possibility of a
  31 # merge-select instruction (1 - MERGE_SEL_POS = possibility of zero-merge-select
  32 # instruction.
  33 MERGE_SEL_POS = 0.5
  34
  35
  36 test_template = r'''
  37 define internal fastcc {ty} @test({inputs}) noinline nounwind {{
  38 entry:
  39 {instructions}
  40   ret {ty} {last_name}
  41 }}
  42 '''
  43
  44 error_template = r'''@error.{lane} = private unnamed_addr global [64 x i8] c"FAIL: lane {lane}, expected {exp}, found %d\0A{padding}"'''
  45
  46 main_template = r'''
  47 define i32 @main() {{
  48 entry:
  49   ; Create a scratch space to print error messages.
  50   %str = alloca [64 x i8]
  51   %str.ptr = getelementptr inbounds [64 x i8], [64 x i8]* %str, i32 0, i32 0
  52
  53   ; Build the input vector and call the test function.
  54   %v = call fastcc {ty} @test({inputs})
  55   br label %test.0
  56
  57   {check_die}
  58 }}
  59
  60 declare i32 @strlen(i8*)
  61 declare i32 @write(i32, i8*, i32)
  62 declare i32 @sprintf(i8*, i8*, ...)
  63 declare void @llvm.trap() noreturn nounwind
  64 '''
  65
  66 check_template = r'''
  67 test.{lane}:
  68   %v.{lane} = extractelement {ty} %v, i32 {lane}
  69   %cmp.{lane} = {i_f}cmp {ordered}ne {scalar_ty} %v.{lane}, {exp}
  70   br i1 %cmp.{lane}, label %die.{lane}, label %test.{n_lane}
  71 '''
  72
  73 undef_check_template = r'''
  74 test.{lane}:
  75 ; Skip this lane, its value is undef.
  76   br label %test.{n_lane}
  77 '''
  78
  79 die_template = r'''
  80 die.{lane}:
  81 ; Capture the actual value and print an error message.
  82   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})
  83   %length.{lane} = call i32 @strlen(i8* %str.ptr)
  84   call i32 @write(i32 2, i8* %str.ptr, i32 %length.{lane})
  85   call void @llvm.trap()
  86   unreachable
  87 '''
  88
  89 class Type:
  90   def __init__(self, is_float, elt_width, elt_num):
  91     self.is_float = is_float        # Boolean
  92     self.elt_width = elt_width      # Integer
  93     self.elt_num = elt_num          # Integer
  94
  95   def dump(self):
  96     if self.is_float:
  97       str_elt = 'float' if self.elt_width == 32 else 'double'
  98     else:
  99       str_elt = 'i' + str(self.elt_width)
 100
 101     if self.elt_num == 1:
 102       return str_elt
 103     else:
 104       return '<' + str(self.elt_num) + ' x ' + str_elt + '>'
 105
 106   def get_scalar_type(self):
 107     return Type(self.is_float, self.elt_width, 1)
 108
 109
 110
 111 # Class to represent any value (variable) that can be used.
 112 class Value:
 113   def __init__(self, name, ty, value = None):
 114     self.ty = ty                  # Type
 115     self.name = name              # String
 116     self.value = value            # list of integers or floating points
 117
 118
 119 # Class to represent an IR instruction (shuffle/select).
 120 class Instruction(Value):
 121   def __init__(self, name, ty, op0, op1, mask):
 122     Value.__init__(self, name, ty)
 123     self.op0 = op0                # Value
 124     self.op1 = op1                # Value
 125     self.mask = mask              # list of integers
 126
 127   def dump(self): pass
 128
 129   def calc_value(self): pass
 130
 131
 132 # Class to represent an IR shuffle instruction
 133 class ShufInstr(Instruction):
 134
 135   shuf_template = '  {name} = shufflevector {ty} {op0}, {ty} {op1}, <{num} x i32> {mask}\n'
 136
 137   def __init__(self, name, ty, op0, op1, mask):
 138     Instruction.__init__(self, '%shuf' + name, ty, op0, op1, mask)
 139
 140   def dump(self):
 141     str_mask = [('i32 ' + str(idx)) if idx != -1 else 'i32 undef' for idx in self.mask]
 142     str_mask = '<' + (', ').join(str_mask) + '>'
 143     return self.shuf_template.format(name = self.name, ty = self.ty.dump(), op0 = self.op0.name,
 144                                op1 = self.op1.name, num = self.ty.elt_num, mask = str_mask)
 145
 146   def calc_value(self):
 147     if self.value != None:
 148       print 'Trying to calculate the value of a shuffle instruction twice'
 149       exit(1)
 150
 151     result = []
 152     for i in range(len(self.mask)):
 153       index = self.mask[i]
 154
 155       if index < self.ty.elt_num and index >= 0:
 156         result.append(self.op0.value[index])
 157       elif index >= self.ty.elt_num:
 158         index = index % self.ty.elt_num
 159         result.append(self.op1.value[index])
 160       else: # -1 => undef
 161         result.append(-1)
 162
 163     self.value = result
 164
 165
 166 # Class to represent an IR select instruction
 167 class SelectInstr(Instruction):
 168
 169   sel_template = '  {name} = select <{num} x i1> {mask}, {ty} {op0}, {ty} {op1}\n'
 170
 171   def __init__(self, name, ty, op0, op1, mask):
 172     Instruction.__init__(self, '%sel' + name, ty, op0, op1, mask)
 173
 174   def dump(self):
 175     str_mask = [('i1 ' + str(idx)) if idx != -1 else 'i1 undef' for idx in self.mask]
 176     str_mask = '<' + (', ').join(str_mask) + '>'
 177     return self.sel_template.format(name = self.name, ty = self.ty.dump(), op0 = self.op0.name,
 178                                op1 = self.op1.name, num = self.ty.elt_num, mask = str_mask)
 179
 180   def calc_value(self):
 181     if self.value != None:
 182       print 'Trying to calculate the value of a select instruction twice'
 183       exit(1)
 184
 185     result = []
 186     for i in range(len(self.mask)):
 187       index = self.mask[i]
 188
 189       if index == 1:
 190         result.append(self.op0.value[i])
 191       elif index == 0:
 192         result.append(self.op1.value[i])
 193       else: # -1 => undef
 194         result.append(-1)
 195
 196     self.value = result
 197
 198
 199 # Returns a list of Values initialized with actual numbers according to the
 200 # provided type
 201 def gen_inputs(ty, num):
 202   inputs = []
 203   for i in range(num):
 204     inp = []
 205     for j in range(ty.elt_num):
 206       if ty.is_float:
 207         inp.append(float(i*ty.elt_num + j))
 208       else:
 209         inp.append((i*ty.elt_num + j) % (1 << ty.elt_width))
 210     inputs.append(Value('%inp' + str(i), ty, inp))
 211
 212   return inputs
 213
 214
 215 # Returns a random vector type to be tested
 216 # In case one of the dimensions (scalar type/number of elements) is provided,
 217 # fill the blank dimension and return appropriate Type object.
 218 def get_random_type(ty, num_elts):
 219   if ty != None:
 220     if ty == 'i8':
 221       is_float = False
 222       width = 8
 223     elif ty == 'i16':
 224       is_float = False
 225       width = 16
 226     elif ty == 'i32':
 227       is_float = False
 228       width = 32
 229     elif ty == 'i64':
 230       is_float = False
 231       width = 64
 232     elif ty == 'f32':
 233       is_float = True
 234       width = 32
 235     elif ty == 'f64':
 236       is_float = True
 237       width = 64
 238
 239   int_elt_widths = [8, 16, 32, 64]
 240   float_elt_widths = [32, 64]
 241
 242   if num_elts == None:
 243     num_elts = random.choice(range(2, 65))
 244
 245   if ty == None:
 246     # 1 for integer type, 0 for floating-point
 247     if random.randint(0,1):
 248       is_float = False
 249       width = random.choice(int_elt_widths)
 250     else:
 251       is_float = True
 252       width = random.choice(float_elt_widths)
 253
 254   return Type(is_float, width, num_elts)
 255
 256
 257 # Generate mask for shufflevector IR instruction, with SHUF_UNDEF_POS possibility
 258 # of one undef index.
 259 def gen_shuf_mask(ty):
 260   mask = []
 261   for i in range(ty.elt_num):
 262     if SHUF_UNDEF_POS/ty.elt_num > random.random():
 263       mask.append(-1)
 264     else:
 265       mask.append(random.randint(0, ty.elt_num*2 - 1))
 266
 267   return mask
 268
 269
 270 # Generate mask for select IR instruction, with SEL_UNDEF_POS possibility
 271 # of one undef index.
 272 def gen_sel_mask(ty):
 273   mask = []
 274   for i in range(ty.elt_num):
 275     if SEL_UNDEF_POS/ty.elt_num > random.random():
 276       mask.append(-1)
 277     else:
 278       mask.append(random.randint(0, 1))
 279
 280   return mask
 281
 282 # Generate shuffle instructions with optional select instruction after.
 283 def gen_insts(inputs, ty):
 284   int_zero_init = Value('zeroinitializer', ty, [0]*ty.elt_num)
 285   float_zero_init = Value('zeroinitializer', ty, [0.0]*ty.elt_num)
 286
 287   insts = []
 288   name_idx = 0
 289   while len(inputs) > 1:
 290     # Choose 2 available Values - remove them from inputs list.
 291     [idx0, idx1] = sorted(random.sample(range(len(inputs)), 2))
 292     op0 = inputs[idx0]
 293     op1 = inputs[idx1]
 294
 295     # Create the shuffle instruction.
 296     shuf_mask = gen_shuf_mask(ty)
 297     shuf_inst = ShufInstr(str(name_idx), ty, op0, op1, shuf_mask)
 298     shuf_inst.calc_value()
 299
 300     # Add the new shuffle instruction to the list of instructions.
 301     insts.append(shuf_inst)
 302
 303     # Optionally, add select instruction with the result of the previous shuffle.
 304     if random.random() < ADD_SEL_POS:
 305       #  Either blending with a random Value or with an all-zero vector.
 306       if random.random() < MERGE_SEL_POS:
 307         op2 = random.choice(inputs)
 308       else:
 309         op2 = float_zero_init if ty.is_float else int_zero_init
 310
 311       select_mask = gen_sel_mask(ty)
 312       select_inst = SelectInstr(str(name_idx), ty, shuf_inst, op2, select_mask)
 313       select_inst.calc_value()
 314
 315       # Add the select instructions to the list of instructions and to the available Values.
 316       insts.append(select_inst)
 317       inputs.append(select_inst)
 318     else:
 319       # If the shuffle instruction is not followed by select, add it to the available Values.
 320       inputs.append(shuf_inst)
 321
 322     del inputs[idx1]
 323     del inputs[idx0]
 324     name_idx += 1
 325
 326   return insts
 327
 328
 329 def main():
 330   parser = argparse.ArgumentParser(description=__doc__)
 331   parser.add_argument('--seed', default=str(uuid.uuid4()),
 332                       help='A string used to seed the RNG')
 333   parser.add_argument('--max-num-inputs', type=int, default=20,
 334           help='Specify the maximum number of vector inputs for the test. (default: 20)')
 335   parser.add_argument('--min-num-inputs', type=int, default=10,
 336           help='Specify the minimum number of vector inputs for the test. (default: 10)')
 337   parser.add_argument('--type', default=None,
 338                       help='''
 339                           Choose specific type to be tested.
 340                           i8, i16, i32, i64, f32 or f64.
 341                           (default: random)''')
 342   parser.add_argument('--num-elts', default=None, type=int,
 343                       help='Choose specific number of vector elements to be tested. (default: random)')
 344   args = parser.parse_args()
 345
 346   print '; The seed used for this test is ' + args.seed
 347
 348   assert args.min_num_inputs < args.max_num_inputs , "Minimum value greater than maximum."
 349   assert args.type in [None, 'i8', 'i16', 'i32', 'i64', 'f32', 'f64'], "Illegal type."
 350   assert args.num_elts == None or args.num_elts > 0, "num_elts must be a positive integer."
 351
 352   random.seed(args.seed)
 353   ty = get_random_type(args.type, args.num_elts)
 354   inputs = gen_inputs(ty, random.randint(args.min_num_inputs, args.max_num_inputs))
 355   inputs_str = (', ').join([inp.ty.dump() + ' ' + inp.name for inp in inputs])
 356   inputs_values = [inp.value for inp in inputs]
 357
 358   insts = gen_insts(inputs, ty)
 359
 360   assert len(inputs) == 1, "Only one value should be left after generating phase"
 361   res = inputs[0]
 362
 363   # print the actual test function by dumping the generated instructions.
 364   insts_str = ''.join([inst.dump() for inst in insts])
 365   print test_template.format(ty = ty.dump(), inputs = inputs_str,
 366                              instructions = insts_str, last_name = res.name)
 367
 368   # Print the error message templates as global strings
 369   for i in range(len(res.value)):
 370     pad = ''.join(['\\00']*(31 - len(str(i)) - len(str(res.value[i]))))
 371     print error_template.format(lane = str(i), exp = str(res.value[i]),
 372                                 padding = pad)
 373
 374   # Prepare the runtime checks and failure handlers.
 375   scalar_ty = ty.get_scalar_type()
 376   check_die = ''
 377   i_f = 'f' if ty.is_float else 'i'
 378   ordered = 'o' if ty.is_float else ''
 379   for i in range(len(res.value)):
 380     if res.value[i] != -1:
 381       # Emit runtime check for each non-undef expected value.
 382       check_die += check_template.format(lane = str(i), n_lane = str(i+1),
 383                              ty = ty.dump(), i_f = i_f, scalar_ty = scalar_ty.dump(),
 384                              exp = str(res.value[i]), ordered = ordered)
 385       # Emit failure handler for each runtime check with proper error message
 386       check_die += die_template.format(lane = str(i), scalar_ty = scalar_ty.dump())
 387     else:
 388       # Ignore lanes with undef result
 389       check_die += undef_check_template.format(lane = str(i), n_lane = str(i+1))
 390
 391   check_die += '\ntest.' + str(len(res.value)) + ':\n'
 392   check_die += '  ret i32 0'
 393
 394   # Prepare the input values passed to the test function.
 395   inputs_values = [', '.join([scalar_ty.dump() + ' ' + str(i) for i in inp]) for inp in inputs_values]
 396   inputs = ', '.join([ty.dump() + ' <' + inp + '>' for inp in inputs_values])
 397
 398   print main_template.format(ty = ty.dump(), inputs = inputs, check_die = check_die)
 399
 400
 401 if __name__ == '__main__':
 402   main()
 403
 404