• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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"""
16
17import random
18import uuid
19import argparse
20
21# Possibility of one undef index in generated mask for shufflevector instruction
22SHUF_UNDEF_POS = 0.15
23
24# Possibility of one undef index in generated mask for select instruction
25SEL_UNDEF_POS = 0.15
26
27# Possibility of adding a select instruction to the result of a shufflevector
28ADD_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.
33MERGE_SEL_POS = 0.5
34
35
36test_template = r'''
37define internal fastcc {ty} @test({inputs}) noinline nounwind {{
38entry:
39{instructions}
40  ret {ty} {last_name}
41}}
42'''
43
44error_template = r'''@error.{lane} = private unnamed_addr global [64 x i8] c"FAIL: lane {lane}, expected {exp}, found %d\0A{padding}"'''
45
46main_template = r'''
47define i32 @main() {{
48entry:
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
60declare i32 @strlen(i8*)
61declare i32 @write(i32, i8*, i32)
62declare i32 @sprintf(i8*, i8*, ...)
63declare void @llvm.trap() noreturn nounwind
64'''
65
66check_template = r'''
67test.{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
73undef_check_template = r'''
74test.{lane}:
75; Skip this lane, its value is undef.
76  br label %test.{n_lane}
77'''
78
79die_template = r'''
80die.{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
89class 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.
112class 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).
120class 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
133class 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
167class 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
201def 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.
218def 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.
259def 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.
272def 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.
283def 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
329def 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
401if __name__ == '__main__':
402  main()
403
404
405