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