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