1#!/usr/bin/env python 2 3"""A shuffle-select vector fuzz tester. 4 5This is a python program to fuzz test the LLVM shufflevector and select 6instructions. It generates a function with a random sequnece of shufflevectors 7while optionally attaching it with a select instruction (regular or zero merge), 8maintaining the element mapping accumulated across the function. It then 9generates a main function which calls it with a different value in each element 10and checks that the result matches the expected mapping. 11 12Take the output IR printed to stdout, compile it to an executable using whatever 13set of transforms you want to test, and run the program. If it crashes, it found 14a bug (an error message with the expected and actual result is printed). 15""" 16from __future__ import print_function 17 18import random 19import uuid 20import argparse 21 22# Possibility of one undef index in generated mask for shufflevector instruction 23SHUF_UNDEF_POS = 0.15 24 25# Possibility of one undef index in generated mask for select instruction 26SEL_UNDEF_POS = 0.15 27 28# Possibility of adding a select instruction to the result of a shufflevector 29ADD_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. 34MERGE_SEL_POS = 0.5 35 36 37test_template = r''' 38define internal fastcc {ty} @test({inputs}) noinline nounwind {{ 39entry: 40{instructions} 41 ret {ty} {last_name} 42}} 43''' 44 45error_template = r'''@error.{lane} = private unnamed_addr global [64 x i8] c"FAIL: lane {lane}, expected {exp}, found %d\0A{padding}"''' 46 47main_template = r''' 48define i32 @main() {{ 49entry: 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 61declare i32 @strlen(i8*) 62declare i32 @write(i32, i8*, i32) 63declare i32 @sprintf(i8*, i8*, ...) 64declare void @llvm.trap() noreturn nounwind 65''' 66 67check_template = r''' 68test.{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 74undef_check_template = r''' 75test.{lane}: 76; Skip this lane, its value is undef. 77 br label %test.{n_lane} 78''' 79 80die_template = r''' 81die.{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 90class 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. 113class 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). 121class 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 134class 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 168class 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 202def 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. 219def 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. 260def 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. 273def 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. 284def 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 330def 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 402if __name__ == '__main__': 403 main() 404 405 406