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).
"""
from __future__ importprint_function

importrandom
importuuid
importargparse

# 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
'''

classType:
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

defdump(self):
ifself.is_float:
str_elt='float'ifself.elt_width==32else'double'
else:
str_elt='i'+str(self.elt_width)

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

defget_scalar_type(self):
returnType(self.is_float, self.elt_width, 1)



# Class to represent any value (variable) that can be used.
classValue:
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).
classInstruction(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

defdump(self): pass

defcalc_value(self): pass


# Class to represent an IR shuffle instruction
classShufInstr(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)

defdump(self):
str_mask= [('i32 '+str(idx)) ifidx!=-1else'i32 undef'foridxinself.mask]
str_mask='<'+ (', ').join(str_mask) +'>'
returnself.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)

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

result= []
foriinrange(len(self.mask)):
index=self.mask[i]

ifindex<self.ty.elt_numandindex>=0:
result.append(self.op0.value[index])
elifindex>=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
classSelectInstr(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)

defdump(self):
str_mask= [('i1 '+str(idx)) ifidx!=-1else'i1 undef'foridxinself.mask]
str_mask='<'+ (', ').join(str_mask) +'>'
returnself.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)

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

result= []
foriinrange(len(self.mask)):
index=self.mask[i]

ifindex==1:
result.append(self.op0.value[i])
elifindex==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
defgen_inputs(ty, num):
inputs= []
foriinrange(num):
inp= []
forjinrange(ty.elt_num):
ifty.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))

returninputs


# 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.
defget_random_type(ty, num_elts):
ifty!=None:
ifty=='i8':
is_float=False
width=8
elifty=='i16':
is_float=False
width=16
elifty=='i32':
is_float=False
width=32
elifty=='i64':
is_float=False
width=64
elifty=='f32':
is_float=True
width=32
elifty=='f64':
is_float=True
width=64

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

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

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

returnType(is_float, width, num_elts)


# Generate mask for shufflevector IR instruction, with SHUF_UNDEF_POS possibility
# of one undef index.
defgen_shuf_mask(ty):
mask= []
foriinrange(ty.elt_num):
ifSHUF_UNDEF_POS/ty.elt_num>random.random():
mask.append(-1)
else:
mask.append(random.randint(0, ty.elt_num*2-1))

returnmask


# Generate mask for select IR instruction, with SEL_UNDEF_POS possibility
# of one undef index.
defgen_sel_mask(ty):
mask= []
foriinrange(ty.elt_num):
ifSEL_UNDEF_POS/ty.elt_num>random.random():
mask.append(-1)
else:
mask.append(random.randint(0, 1))

returnmask

# Generate shuffle instructions with optional select instruction after.
defgen_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
whilelen(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.
ifrandom.random() <ADD_SEL_POS:
# Either blending with a random Value or with an all-zero vector.
ifrandom.random() <MERGE_SEL_POS:
op2=random.choice(inputs)
else:
op2=float_zero_initifty.is_floatelseint_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)

delinputs[idx1]
delinputs[idx0]
name_idx+=1

returninsts


defmain():
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)

assertargs.min_num_inputs<args.max_num_inputs , "Minimum value greater than maximum."
assertargs.typein [None, 'i8', 'i16', 'i32', 'i64', 'f32', 'f64'], "Illegal type."
assertargs.num_elts==Noneorargs.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.nameforinpininputs])
inputs_values= [inp.valueforinpininputs]

insts=gen_insts(inputs, ty)

assertlen(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() forinstininsts])
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
foriinrange(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'ifty.is_floatelse'i'
ordered='o'ifty.is_floatelse''
foriinrange(len(res.value)):
ifres.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) foriininp]) forinpininputs_values]
inputs=', '.join([ty.dump() +' <'+inp+'>'forinpininputs_values])

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


if__name__=='__main__':
main()