utils/shuffle_fuzz.py

   1 #!/usr/bin/env python
   2
   3 """A shuffle vector fuzz tester.
   4
   5 This is a python program to fuzz test the LLVM shufflevector instruction. It
   6 generates a function with a random sequnece of shufflevectors, maintaining the
   7 element mapping accumulated across the function. It then generates a main
   8 function which calls it with a different value in each element and checks that
   9 the result matches the expected mapping.
  10
  11 Take the output IR printed to stdout, compile it to an executable using whatever
  12 set of transforms you want to test, and run the program. If it crashes, it found
  13 a bug.
  14 """
  15
  16 import argparse
  17 import itertools
  18 import random
  19 import sys
  20
  21 def main():
  22   parser = argparse.ArgumentParser(description=__doc__)
  23   parser.add_argument('seed',
  24                       help='A string used to seed the RNG')
  25   parser.add_argument('-v', '--verbose', action='store_true',
  26                       help='Show verbose output')
  27   parser.add_argument('--fixed-num-shuffles', type=int,
  28                       help='Specify a fixed number of shuffles to test')
  29   parser.add_argument('--fixed-bit-width', type=int, choices=[128, 256],
  30                       help='Specify a fixed bit width of vector to test')
  31   parser.add_argument('--triple',
  32                       help='Specify a triple string to include in the IR')
  33   args = parser.parse_args()
  34
  35   random.seed(args.seed)
  36
  37   if args.fixed_bit_width is not None:
  38     if args.fixed_bit_width == 128:
  39       (width, element_type) = random.choice(
  40           [(2, 'i64'), (4, 'i32'), (8, 'i16'), (16, 'i8'),
  41            (2, 'f64'), (4, 'f32')])
  42     elif args.fixed_bit_width == 256:
  43       (width, element_type) = random.choice([
  44           (4, 'i64'), (8, 'i32'), (16, 'i16'), (32, 'i8'),
  45           (4, 'f64'), (8, 'f32')])
  46     else:
  47       sys.exit(1) # Checked above by argument parsing.
  48   else:
  49     width = random.choice([2, 4, 8, 16, 32, 64])
  50     element_type = random.choice(['i8', 'i16', 'i32', 'i64', 'f32', 'f64'])
  51
  52   # FIXME: Support blends.
  53   shuffle_indices = [-1] + range(width)
  54
  55   if args.fixed_num_shuffles is not None:
  56     num_shuffles = args.fixed_num_shuffles
  57   else:
  58     num_shuffles = random.randint(0, 16)
  59
  60   shuffles = [[random.choice(shuffle_indices)
  61                for _ in itertools.repeat(None, width)]
  62               for _ in itertools.repeat(None, num_shuffles)]
  63
  64   if args.verbose:
  65     # Print out the shuffle sequence in a compact form.
  66     print >>sys.stderr, 'Testing shuffle sequence:'
  67     for s in shuffles:
  68       print >>sys.stderr, '  v%d%s: %s' % (width, element_type, s)
  69     print >>sys.stderr, ''
  70
  71   # Compute a round-trip of the shuffle.
  72   result = range(1, width + 1)
  73   for s in shuffles:
  74     result = [result[i] if i != -1 else -1 for i in s]
  75
  76   if args.verbose:
  77     print >>sys.stderr, 'Which transforms:'
  78     print >>sys.stderr, '  from: %s' % (range(1, width + 1),)
  79     print >>sys.stderr, '  into: %s' % (result,)
  80     print >>sys.stderr, ''
  81
  82   # The IR uses silly names for floating point types. We also need a same-size
  83   # integer type.
  84   integral_element_type = element_type
  85   if element_type == 'f32':
  86     integral_element_type = 'i32'
  87     element_type = 'float'
  88   elif element_type == 'f64':
  89     integral_element_type = 'i64'
  90     element_type = 'double'
  91
  92   # Now we need to generate IR for the shuffle function.
  93   subst = {'N': width, 'T': element_type, 'IT': integral_element_type}
  94   print """
  95 define internal <%(N)d x %(T)s> @test(<%(N)d x %(T)s> %%v) noinline nounwind {
  96 entry:""" % subst
  97
  98   for i, s in enumerate(shuffles):
  99     print """
 100   %%s%(i)d = shufflevector <%(N)d x %(T)s> %(I)s, <%(N)d x %(T)s> undef, <%(N)d x i32> <%(S)s>
 101 """.strip() % dict(subst,
 102                 i=i,
 103                 I=('%%s%d' % (i - 1)) if i != 0 else '%v',
 104                 S=', '.join(['i32 %s' % (str(si) if si != -1 else 'undef',)
 105                              for si in s]))
 106
 107   print """
 108   ret <%(N)d x %(T)s> %%s%(i)d
 109 }
 110 """ % dict(subst, i=len(shuffles) - 1)
 111
 112   # Generate some string constants that we can use to report errors.
 113   for i, r in enumerate(result):
 114     if r != -1:
 115       s = ('FAIL(%(seed)s): lane %(lane)d, expected %(result)d, found %%d\\0A' %
 116            {'seed': args.seed, 'lane': i, 'result': r})
 117       s += ''.join(['\\00' for _ in itertools.repeat(None, 64 - len(s) + 2)])
 118       print """
 119 @error.%(i)d = private unnamed_addr global [64 x i8] c"%(s)s"
 120 """.strip() % {'i': i, 's': s}
 121
 122   # Finally, generate a main function which will trap if any lanes are mapped
 123   # incorrectly (in an observable way).
 124   print """
 125 define i32 @main() optnone noinline {
 126 entry:
 127   ; Create a scratch space to print error messages.
 128   %%str = alloca [64 x i8]
 129   %%str.ptr = getelementptr inbounds [64 x i8]* %%str, i32 0, i32 0
 130
 131   ; Build the input vector and call the test function.
 132   %%input = bitcast <%(N)d x %(IT)s> <%(input)s> to <%(N)d x %(T)s>
 133   %%v = call <%(N)d x %(T)s> @test(<%(N)d x %(T)s> %%input)
 134   ; We need to cast this back to an integer type vector to easily check the
 135   ; result.
 136   %%v.cast = bitcast <%(N)d x %(T)s> %%v to <%(N)d x %(IT)s>
 137   br label %%test.0
 138 """ % dict(subst,
 139            input=', '.join(['%(IT)s %(i)s' % dict(subst, i=i)
 140                             for i in xrange(1, width + 1)]),
 141            result=', '.join(['%(IT)s %(i)s' % dict(subst,
 142                                                    i=i if i != -1 else 'undef')
 143                              for i in result]))
 144
 145   # Test that each non-undef result lane contains the expected value.
 146   for i, r in enumerate(result):
 147     if r == -1:
 148       print """
 149 test.%(i)d:
 150   ; Skip this lane, its value is undef.
 151   br label %%test.%(next_i)d
 152 """ % dict(subst, i=i, next_i=i + 1)
 153     else:
 154       print """
 155 test.%(i)d:
 156   %%v.%(i)d = extractelement <%(N)d x %(IT)s> %%v.cast, i32 %(i)d
 157   %%cmp.%(i)d = icmp ne %(IT)s %%v.%(i)d, %(r)d
 158   br i1 %%cmp.%(i)d, label %%die.%(i)d, label %%test.%(next_i)d
 159
 160 die.%(i)d:
 161   ; Capture the actual value and print an error message.
 162   %%tmp.%(i)d = zext %(IT)s %%v.%(i)d to i2048
 163   %%bad.%(i)d = trunc i2048 %%tmp.%(i)d to i32
 164   call i32 (i8*, i8*, ...)* @sprintf(i8* %%str.ptr, i8* getelementptr inbounds ([64 x i8]* @error.%(i)d, i32 0, i32 0), i32 %%bad.%(i)d)
 165   %%length.%(i)d = call i32 @strlen(i8* %%str.ptr)
 166   %%size.%(i)d = add i32 %%length.%(i)d, 1
 167   call i32 @write(i32 2, i8* %%str.ptr, i32 %%size.%(i)d)
 168   call void @llvm.trap()
 169   unreachable
 170 """ % dict(subst, i=i, next_i=i + 1, r=r)
 171
 172   print """
 173 test.%d:
 174   ret i32 0
 175 }
 176
 177 declare i32 @strlen(i8*)
 178 declare i32 @write(i32, i8*, i32)
 179 declare i32 @sprintf(i8*, i8*, ...)
 180 declare void @llvm.trap() noreturn nounwind
 181 """ % (len(result),)
 182
 183 if __name__ == '__main__':
 184   main()