shuffle_select_fuzz_tester.py

#!/usr/bin/env python

"""A shuffle-select vector fuzz tester.

This is a python program to fuzz test the LLVM shufflevector and select
instructions. It generates a function with a random sequnece of shufflevectors
while optionally attaching it with a select instruction (regular or zero merge),
maintaining the element mapping accumulated across the function. It then
generates a main function which calls it with a different value in each element
and checks that the result matches the expected mapping.

Take the output IR printed to stdout, compile it to an executable using whatever
set of transforms you want to test, and run the program. If it crashes, it found
a bug (an error message with the expected and actual result is printed).
"""

import random
import uuid
import argparse

# Possibility of one undef index in generated mask for shufflevector instruction
SHUF_UNDEF_POS = 0.15

# Possibility of one undef index in generated mask for select instruction
SEL_UNDEF_POS = 0.15

# Possibility of adding a select instruction to the result of a shufflevector
ADD_SEL_POS = 0.4

# If we are adding a select instruction, this is the possibility of a
# merge-select instruction (1 - MERGE_SEL_POS = possibility of zero-merge-select
# instruction.
MERGE_SEL_POS = 0.5


test_template = r'''
define internal fastcc {ty} @test({inputs}) noinline nounwind {{
entry:
{instructions}
  ret {ty} {last_name}
}}
'''

error_template = r'''@error.{lane} = private unnamed_addr global [64 x i8] c"FAIL: lane {lane}, expected {exp}, found %d\0A{padding}"'''

main_template = r'''
define i32 @main() {{
entry:
  ; Create a scratch space to print error messages.
  %str = alloca [64 x i8]
  %str.ptr = getelementptr inbounds [64 x i8], [64 x i8]* %str, i32 0, i32 0

  ; Build the input vector and call the test function.
  %v = call fastcc {ty} @test({inputs})
  br label %test.0

  {check_die}
}}

declare i32 @strlen(i8*)
declare i32 @write(i32, i8*, i32)
declare i32 @sprintf(i8*, i8*, ...)
declare void @llvm.trap() noreturn nounwind
'''

check_template = r'''
test.{lane}:
  %v.{lane} = extractelement {ty} %v, i32 {lane}
  %cmp.{lane} = {i_f}cmp {ordered}ne {scalar_ty} %v.{lane}, {exp}
  br i1 %cmp.{lane}, label %die.{lane}, label %test.{n_lane}
'''

undef_check_template = r'''
test.{lane}:
; Skip this lane, its value is undef.
  br label %test.{n_lane}
'''

die_template = r'''
die.{lane}:
; Capture the actual value and print an error message.
  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})
  %length.{lane} = call i32 @strlen(i8* %str.ptr)
  call i32 @write(i32 2, i8* %str.ptr, i32 %length.{lane})
  call void @llvm.trap()
  unreachable
'''

class Type:
  def __init__(self, is_float, elt_width, elt_num):
    self.is_float = is_float        # Boolean
    self.elt_width = elt_width      # Integer
    self.elt_num = elt_num          # Integer

  def dump(self):
    if self.is_float:
      str_elt = 'float' if self.elt_width == 32 else 'double'
    else:
      str_elt = 'i' + str(self.elt_width)

    if self.elt_num == 1:
      return str_elt
    else:
      return '<' + str(self.elt_num) + ' x ' + str_elt + '>'

  def get_scalar_type(self):
    return Type(self.is_float, self.elt_width, 1)



# Class to represent any value (variable) that can be used.
class Value:
  def __init__(self, name, ty, value = None):
    self.ty = ty                  # Type
    self.name = name              # String
    self.value = value            # list of integers or floating points


# Class to represent an IR instruction (shuffle/select).
class Instruction(Value):
  def __init__(self, name, ty, op0, op1, mask):
    Value.__init__(self, name, ty)
    self.op0 = op0                # Value
    self.op1 = op1                # Value
    self.mask = mask              # list of integers

  def dump(self): pass

  def calc_value(self): pass


# Class to represent an IR shuffle instruction
class ShufInstr(Instruction):

  shuf_template = '  {name} = shufflevector {ty} {op0}, {ty} {op1}, <{num} x i32> {mask}\n'

  def __init__(self, name, ty, op0, op1, mask):
    Instruction.__init__(self, '%shuf' + name, ty, op0, op1, mask)

  def dump(self):
    str_mask = [('i32 ' + str(idx)) if idx != -1 else 'i32 undef' for idx in self.mask]
    str_mask = '<' + (', ').join(str_mask) + '>'
    return self.shuf_template.format(name = self.name, ty = self.ty.dump(), op0 = self.op0.name,
                               op1 = self.op1.name, num = self.ty.elt_num, mask = str_mask)

  def calc_value(self):
    if self.value != None:
      print 'Trying to calculate the value of a shuffle instruction twice'
      exit(1)

    result = []
    for i in range(len(self.mask)):
      index = self.mask[i]

      if index < self.ty.elt_num and index >= 0:
        result.append(self.op0.value[index])
      elif index >= self.ty.elt_num:
        index = index % self.ty.elt_num
        result.append(self.op1.value[index])
      else: # -1 => undef
        result.append(-1)

    self.value = result


# Class to represent an IR select instruction
class SelectInstr(Instruction):

  sel_template = '  {name} = select <{num} x i1> {mask}, {ty} {op0}, {ty} {op1}\n'

  def __init__(self, name, ty, op0, op1, mask):
    Instruction.__init__(self, '%sel' + name, ty, op0, op1, mask)

  def dump(self):
    str_mask = [('i1 ' + str(idx)) if idx != -1 else 'i1 undef' for idx in self.mask]
    str_mask = '<' + (', ').join(str_mask) + '>'
    return self.sel_template.format(name = self.name, ty = self.ty.dump(), op0 = self.op0.name,
                               op1 = self.op1.name, num = self.ty.elt_num, mask = str_mask)

  def calc_value(self):
    if self.value != None:
      print 'Trying to calculate the value of a select instruction twice'
      exit(1)

    result = []
    for i in range(len(self.mask)):
      index = self.mask[i]

      if index == 1:
        result.append(self.op0.value[i])
      elif index == 0:
        result.append(self.op1.value[i])
      else: # -1 => undef
        result.append(-1)

    self.value = result


# Returns a list of Values initialized with actual numbers according to the
# provided type
def gen_inputs(ty, num):
  inputs = []
  for i in range(num):
    inp = []
    for j in range(ty.elt_num):
      if ty.is_float:
        inp.append(float(i*ty.elt_num + j))
      else:
        inp.append((i*ty.elt_num + j) % (1 << ty.elt_width))
    inputs.append(Value('%inp' + str(i), ty, inp))

  return inputs


# Returns a random vector type to be tested
# In case one of the dimensions (scalar type/number of elements) is provided,
# fill the blank dimension and return appropriate Type object.
def get_random_type(ty, num_elts):
  if ty != None:
    if ty == 'i8':
      is_float = False
      width = 8
    elif ty == 'i16':
      is_float = False
      width = 16
    elif ty == 'i32':
      is_float = False
      width = 32
    elif ty == 'i64':
      is_float = False
      width = 64
    elif ty == 'f32':
      is_float = True
      width = 32
    elif ty == 'f64':
      is_float = True
      width = 64

  int_elt_widths = [8, 16, 32, 64]
  float_elt_widths = [32, 64]

  if num_elts == None:
    num_elts = random.choice(range(2, 65))

  if ty == None:
    # 1 for integer type, 0 for floating-point
    if random.randint(0,1):
      is_float = False
      width = random.choice(int_elt_widths)
    else:
      is_float = True
      width = random.choice(float_elt_widths)

  return Type(is_float, width, num_elts)


# Generate mask for shufflevector IR instruction, with SHUF_UNDEF_POS possibility
# of one undef index.
def gen_shuf_mask(ty):
  mask = []
  for i in range(ty.elt_num):
    if SHUF_UNDEF_POS/ty.elt_num > random.random():
      mask.append(-1)
    else:
      mask.append(random.randint(0, ty.elt_num*2 - 1))

  return mask


# Generate mask for select IR instruction, with SEL_UNDEF_POS possibility
# of one undef index.
def gen_sel_mask(ty):
  mask = []
  for i in range(ty.elt_num):
    if SEL_UNDEF_POS/ty.elt_num > random.random():
      mask.append(-1)
    else:
      mask.append(random.randint(0, 1))

  return mask

# Generate shuffle instructions with optional select instruction after.
def gen_insts(inputs, ty):
  int_zero_init = Value('zeroinitializer', ty, [0]*ty.elt_num)
  float_zero_init = Value('zeroinitializer', ty, [0.0]*ty.elt_num)

  insts = []
  name_idx = 0
  while len(inputs) > 1:
    # Choose 2 available Values - remove them from inputs list.
    [idx0, idx1] = sorted(random.sample(range(len(inputs)), 2))
    op0 = inputs[idx0]
    op1 = inputs[idx1]

    # Create the shuffle instruction.
    shuf_mask = gen_shuf_mask(ty)
    shuf_inst = ShufInstr(str(name_idx), ty, op0, op1, shuf_mask)
    shuf_inst.calc_value()

    # Add the new shuffle instruction to the list of instructions.
    insts.append(shuf_inst)

    # Optionally, add select instruction with the result of the previous shuffle.
    if random.random() < ADD_SEL_POS:
      #  Either blending with a random Value or with an all-zero vector.
      if random.random() < MERGE_SEL_POS:
        op2 = random.choice(inputs)
      else:
        op2 = float_zero_init if ty.is_float else int_zero_init

      select_mask = gen_sel_mask(ty)
      select_inst = SelectInstr(str(name_idx), ty, shuf_inst, op2, select_mask)
      select_inst.calc_value()

      # Add the select instructions to the list of instructions and to the available Values.
      insts.append(select_inst)
      inputs.append(select_inst)
    else:
      # If the shuffle instruction is not followed by select, add it to the available Values.
      inputs.append(shuf_inst)

    del inputs[idx1]
    del inputs[idx0]
    name_idx += 1

  return insts


def main():
  parser = argparse.ArgumentParser(description=__doc__)
  parser.add_argument('--seed', default=str(uuid.uuid4()),
                      help='A string used to seed the RNG')
  parser.add_argument('--max-num-inputs', type=int, default=20,
          help='Specify the maximum number of vector inputs for the test. (default: 20)')
  parser.add_argument('--min-num-inputs', type=int, default=10,
          help='Specify the minimum number of vector inputs for the test. (default: 10)')
  parser.add_argument('--type', default=None,
                      help='''
                          Choose specific type to be tested.
                          i8, i16, i32, i64, f32 or f64.
                          (default: random)''')
  parser.add_argument('--num-elts', default=None, type=int,
                      help='Choose specific number of vector elements to be tested. (default: random)')
  args = parser.parse_args()

  print '; The seed used for this test is ' + args.seed

  assert args.min_num_inputs < args.max_num_inputs , "Minimum value greater than maximum."
  assert args.type in [None, 'i8', 'i16', 'i32', 'i64', 'f32', 'f64'], "Illegal type."
  assert args.num_elts == None or args.num_elts > 0, "num_elts must be a positive integer."

  random.seed(args.seed)
  ty = get_random_type(args.type, args.num_elts)
  inputs = gen_inputs(ty, random.randint(args.min_num_inputs, args.max_num_inputs))
  inputs_str = (', ').join([inp.ty.dump() + ' ' + inp.name for inp in inputs])
  inputs_values = [inp.value for inp in inputs]

  insts = gen_insts(inputs, ty)

  assert len(inputs) == 1, "Only one value should be left after generating phase"
  res = inputs[0]

  # print the actual test function by dumping the generated instructions.
  insts_str = ''.join([inst.dump() for inst in insts])
  print test_template.format(ty = ty.dump(), inputs = inputs_str,
                             instructions = insts_str, last_name = res.name)

  # Print the error message templates as global strings
  for i in range(len(res.value)):
    pad = ''.join(['\\00']*(31 - len(str(i)) - len(str(res.value[i]))))
    print error_template.format(lane = str(i), exp = str(res.value[i]),
                                padding = pad)

  # Prepare the runtime checks and failure handlers.
  scalar_ty = ty.get_scalar_type()
  check_die = ''
  i_f = 'f' if ty.is_float else 'i'
  ordered = 'o' if ty.is_float else ''
  for i in range(len(res.value)):
    if res.value[i] != -1:
      # Emit runtime check for each non-undef expected value.
      check_die += check_template.format(lane = str(i), n_lane = str(i+1),
                             ty = ty.dump(), i_f = i_f, scalar_ty = scalar_ty.dump(),
                             exp = str(res.value[i]), ordered = ordered)
      # Emit failure handler for each runtime check with proper error message
      check_die += die_template.format(lane = str(i), scalar_ty = scalar_ty.dump())
    else:
      # Ignore lanes with undef result
      check_die += undef_check_template.format(lane = str(i), n_lane = str(i+1))

  check_die += '\ntest.' + str(len(res.value)) + ':\n'
  check_die += '  ret i32 0'

  # Prepare the input values passed to the test function.
  inputs_values = [', '.join([scalar_ty.dump() + ' ' + str(i) for i in inp]) for inp in inputs_values]
  inputs = ', '.join([ty.dump() + ' <' + inp + '>' for inp in inputs_values])

  print main_template.format(ty = ty.dump(), inputs = inputs, check_die = check_die)


if __name__ == '__main__':
  main()