X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=utils%2Fshuffle_fuzz.py;h=985d1dab9e23e8ffdf5788bdcb0482d70668ef84;hb=0ea5f0022615b65f67424bfb12d6ddec46fc5011;hp=1f1a0478f2bbc46fbf60c0d631c46ac6fb395d95;hpb=918801162a649a5fff0a345db0746018687a5dad;p=oota-llvm.git

diff --git a/utils/shuffle_fuzz.py b/utils/shuffle_fuzz.py
index 1f1a0478f2b..985d1dab9e2 100755
--- a/utils/shuffle_fuzz.py
+++ b/utils/shuffle_fuzz.py
@@ -17,48 +17,92 @@ import argparse
 import itertools
 import random
 import sys
+import uuid
 
 def main():
+  element_types=['i8', 'i16', 'i32', 'i64', 'f32', 'f64']
   parser = argparse.ArgumentParser(description=__doc__)
-  parser.add_argument('seed',
-                      help='A string used to seed the RNG')
   parser.add_argument('-v', '--verbose', action='store_true',
                       help='Show verbose output')
+  parser.add_argument('--seed', default=str(uuid.uuid4()),
+                      help='A string used to seed the RNG')
   parser.add_argument('--max-shuffle-height', type=int, default=16,
                       help='Specify a fixed height of shuffle tree to test')
   parser.add_argument('--no-blends', dest='blends', action='store_false',
                       help='Include blends of two input vectors')
   parser.add_argument('--fixed-bit-width', type=int, choices=[128, 256],
                       help='Specify a fixed bit width of vector to test')
+  parser.add_argument('--fixed-element-type', choices=element_types,
+                      help='Specify a fixed element type to test')
   parser.add_argument('--triple',
                       help='Specify a triple string to include in the IR')
   args = parser.parse_args()
 
   random.seed(args.seed)
 
+  if args.fixed_element_type is not None:
+    element_types=[args.fixed_element_type]
+
   if args.fixed_bit_width is not None:
     if args.fixed_bit_width == 128:
+      width_map={'i64': 2, 'i32': 4, 'i16': 8, 'i8': 16, 'f64': 2, 'f32': 4}
       (width, element_type) = random.choice(
-          [(2, 'i64'), (4, 'i32'), (8, 'i16'), (16, 'i8'),
-           (2, 'f64'), (4, 'f32')])
+          [(width_map[t], t) for t in element_types])
     elif args.fixed_bit_width == 256:
-      (width, element_type) = random.choice([
-          (4, 'i64'), (8, 'i32'), (16, 'i16'), (32, 'i8'),
-          (4, 'f64'), (8, 'f32')])
+      width_map={'i64': 4, 'i32': 8, 'i16': 16, 'i8': 32, 'f64': 4, 'f32': 8}
+      (width, element_type) = random.choice(
+          [(width_map[t], t) for t in element_types])
     else:
       sys.exit(1) # Checked above by argument parsing.
   else:
     width = random.choice([2, 4, 8, 16, 32, 64])
-    element_type = random.choice(['i8', 'i16', 'i32', 'i64', 'f32', 'f64'])
+    element_type = random.choice(element_types)
 
   element_modulus = {
       'i8': 1 << 8, 'i16': 1 << 16, 'i32': 1 << 32, 'i64': 1 << 64,
       'f32': 1 << 32, 'f64': 1 << 64}[element_type]
 
   shuffle_range = (2 * width) if args.blends else width
-  shuffle_indices = [-1] + range(shuffle_range)
 
-  shuffle_tree = [[[random.choice(shuffle_indices)
+  # Because undef (-1) saturates and is indistinguishable when testing the
+  # correctness of a shuffle, we want to bias our fuzz toward having a decent
+  # mixture of non-undef lanes in the end. With a deep shuffle tree, the
+  # probabilies aren't good so we need to bias things. The math here is that if
+  # we uniformly select between -1 and the other inputs, each element of the
+  # result will have the following probability of being undef:
+  #
+  #   1 - (shuffle_range/(shuffle_range+1))^max_shuffle_height
+  #
+  # More generally, for any probability P of selecting a defined element in
+  # a single shuffle, the end result is:
+  #
+  #   1 - P^max_shuffle_height
+  #
+  # The power of the shuffle height is the real problem, as we want:
+  #
+  #   1 - shuffle_range/(shuffle_range+1)
+  #
+  # So we bias the selection of undef at any given node based on the tree
+  # height. Below, let 'A' be 'len(shuffle_range)', 'C' be 'max_shuffle_height',
+  # and 'B' be the bias we use to compensate for
+  # C '((A+1)*A^(1/C))/(A*(A+1)^(1/C))':
+  #
+  #   1 - (B * A)/(A + 1)^C = 1 - A/(A + 1)
+  #
+  # So at each node we use:
+  #
+  #   1 - (B * A)/(A + 1)
+  # = 1 - ((A + 1) * A * A^(1/C))/(A * (A + 1) * (A + 1)^(1/C))
+  # = 1 - ((A + 1) * A^((C + 1)/C))/(A * (A + 1)^((C + 1)/C))
+  #
+  # This is the formula we use to select undef lanes in the shuffle.
+  A = float(shuffle_range)
+  C = float(args.max_shuffle_height)
+  undef_prob = 1.0 - (((A + 1.0) * pow(A, (C + 1.0)/C)) /
+                      (A * pow(A + 1.0, (C + 1.0)/C)))
+
+  shuffle_tree = [[[-1 if random.random() <= undef_prob
+                       else random.choice(range(shuffle_range))
                     for _ in itertools.repeat(None, width)]
                    for _ in itertools.repeat(None, args.max_shuffle_height - i)]
                   for i in xrange(args.max_shuffle_height)]
@@ -129,7 +173,7 @@ entry:""" % dict(subst,
   # Generate some string constants that we can use to report errors.
   for i, r in enumerate(result):
     if r != -1:
-      s = ('FAIL(%(seed)s): lane %(lane)d, expected %(result)d, found %%d\\0A' %
+      s = ('FAIL(%(seed)s): lane %(lane)d, expected %(result)d, found %%d\n\\0A' %
            {'seed': args.seed, 'lane': i, 'result': r})
       s += ''.join(['\\00' for _ in itertools.repeat(None, 128 - len(s) + 2)])
       print """
@@ -191,8 +235,7 @@ die.%(i)d:
   %%bad.%(i)d = trunc i2048 %%tmp.%(i)d to i32
   call i32 (i8*, i8*, ...)* @sprintf(i8* %%str.ptr, i8* getelementptr inbounds ([128 x i8]* @error.%(i)d, i32 0, i32 0), i32 %%bad.%(i)d)
   %%length.%(i)d = call i32 @strlen(i8* %%str.ptr)
-  %%size.%(i)d = add i32 %%length.%(i)d, 1
-  call i32 @write(i32 2, i8* %%str.ptr, i32 %%size.%(i)d)
+  call i32 @write(i32 2, i8* %%str.ptr, i32 %%length.%(i)d)
   call void @llvm.trap()
   unreachable
 """ % dict(subst, i=i, next_i=i + 1, r=r)