[Mesa-dev] [PATCH 1/2] nir/algebraic: Rewrite bit-size inference

[Dylan Baker]

Quoting Jason Ekstrand (2018-12-03 14:12:41)
> On Mon, Dec 3, 2018 at 3:50 PM Dylan Baker <dylan at pnwbakers.com> wrote:
> 
>     Quoting Connor Abbott (2018-11-29 10:32:02)
>     > Before this commit, there were two copies of the algorithm: one in C,
>     > that we would use to figure out what bit-size to give the replacement
>     > expression, and one in Python, that emulated the C one and tried to
>     > prove that the C algorithm would never fail to correctly assign
>     > bit-sizes. That seemed pretty fragile, and likely to fall over if we
>     > make any changes. Furthermore, the C code was really just recomputing
>     > more-or-less the same thing as the Python code every time. Instead, we
>     > can just store the results of the Python algorithm in the C
>     > datastructure, and consult it to compute the bitsize of each value,
>     > moving the "brains" entirely into Python. Since the Python algorithm no
>     > longer has to match C, it's also a lot easier to change it to something
>     > more closely approximating an actual type-inference algorithm. The
>     > algorithm used is based on Hindley-Milner, although deliberately
>     > weakened a little. It's a few more lines than the old one, judging by
>     > the diffstat, but I think it's easier to verify that it's correct while
>     > being as general as possible.
>     >
>     > We could split this up into two changes, first making the C code use the
>     > results of the Python code and then rewriting the Python algorithm, but
>     > since the old algorithm never tracked which variable each equivalence
>     > class, it would mean we'd have to add some non-trivial code which would
>     > then get thrown away. I think it's better to see the final state all at
>     > once, although I could also try splitting it up.
>     > ---
>     >  src/compiler/nir/nir_algebraic.py | 518 ++++++++++++++++--------------
>     >  src/compiler/nir/nir_search.c     | 146 +--------
>     >  src/compiler/nir/nir_search.h     |   2 +-
>     >  3 files changed, 295 insertions(+), 371 deletions(-)
>     >
>     > diff --git a/src/compiler/nir/nir_algebraic.py b/src/compiler/nir/
>     nir_algebraic.py
>     > index 728196136ab..48390dbde38 100644
>     > --- a/src/compiler/nir/nir_algebraic.py
>     > +++ b/src/compiler/nir/nir_algebraic.py
>     > @@ -88,7 +88,7 @@ class Value(object):
>     > 
>     >     __template = mako.template.Template("""
>     >  static const ${val.c_type} ${val.name} = {
>     > -   { ${val.type_enum}, ${val.bit_size} },
>     > +   { ${val.type_enum}, ${val.c_bit_size} },
>     >  % if isinstance(val, Constant):
>     >     ${val.type()}, { ${val.hex()} /* ${val.value} */ },
>     >  % elif isinstance(val, Variable):
>     > @@ -112,6 +112,40 @@ static const ${val.c_type} ${val.name} = {
>     >     def __str__(self):
>     >        return self.in_val
>     > 
>     > +   def get_bit_size(self):
>     > +      """Get the physical bit-size that has been chosen for this value,
>     or if
>     > +      there is none, the canonical value which currently represents this
>     > +      bit-size class. Variables will be preferred, i.e. if there are any
>     > +      variables in the equivalence class, the canonical value will be a
>     > +      variable. We do this since we'll need to know which variable each
>     value
>     > +      is equivalent to when constructing the replacement expression.
>     This is
>     > +      the "find" part of the union-find algorithm.
>     > +      """
>     > +      bit_size = self
>     > +
>     > +      while isinstance(bit_size, Value):
>     > +         if bit_size._bit_size == None:
> 
>     Use "is" and "is not" instead of "==" and "!=" when comparing singletons
>     like
>     None, True, False; the former are the identity operators, they'll be faster
>     and
>     avoid any surprises.
> 
>     > +            break
>     > +         bit_size = bit_size._bit_size
>     > +
>     > +      if bit_size != self:
> 
>     Is this a comparison of identity or equality? If it's identity you should
>     use
>     "is not"
> 
> 
> I just saw this one in v2.  Agreed; it should be "is not"
>  
> 
>     > +         self._bit_size = bit_size
>     > +      return bit_size
>     > +
> 
>     [snip]
> 
>     >           else:
>     > -            if val.common_class != 0:
>     > -               assert val.bit_size == 0 or val.bit_size ==
>     val.common_class
>     > -            else:
>     > -               val.common_class = val.bit_size
>     > -            return val.common_class
>     > +            self.unify_bit_size(src, src_type_bits,
>     > +               lambda src_bit_size, unused:
>     > +                  '{} must have {} bits, but as a source of nir_op_{} '\
>     > +                  'it must have {} bits'.format(src, src_bit_size,
>     nir_op.name, src_type_bits)
>     > +                  if self.is_search else
>     > +                  '{} has the bit size of {}, but as a source of nir_op_
>     {} '\
>     > +                  'it must have {} bits, which may not be the
>     same'.format(
>     > +                     src, src_bit_size, nir_op.name, src_type_bits))
>     > +
>     > +      if dst_type_bits == 0:
> 
>     The common idiom is `if not dst_type_bits`, which will also be faster (for
>     ints', `if val` is equivalent to `if val != 0`, and `if not val` is
>     equivalent
>     to `if val == 0`).
> 
> 
> While it may not be pythonic, I think I prefer == 0 because that makes the
> reader explicitly aware that it's an integer.
>  
> 
>     > +         for src_type, src in zip(nir_op.input_types, val.sources):
>     > +            src_type_bits = type_bits(src_type)
>     > +            if src_type_bits == 0:
>     > +               self.unify_bit_size(val, src,
>     > +                  lambda val_bit_size, src_bit_size:
>     > +                     '{} must have the bit size of {}, while its source
>     {} must '
>     > +                     'have incompatible bit size {}'.format(
>     > +                        val, val_bit_size, src, src_bit_size)
>     > +                     if self.is_search else
>     > +                     '{} must have {} bits, but its source {} ' \
>     > +                     '(bit size of {}) may not have that bit size ' \
>     > +                     'when building the replacement.'.format(
>     > +                        val, val_bit_size, src, src_bit_size))
> 
>     This is a case where a ternary hurts readability, how about just using a
>     local
>     function?
> 
> 
> I could go either way.  I didn't find it too hard but I agree it's kind-of
> mashed together.  For that matter,
> 
> if self.is_search:
>    unify_bit_size(...)
> else:
>    unify_bit_size(...)
> 
> would be even better.

Or even:
str1 = '{} must have bit size...'
str2 = '{} must have {} bits...'

lambda v, s: (str1 if self.is_search else str2).format(val, v, s)

That parens trick might be useful for removing duplication elsewhere, actually.

Dylan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 228 bytes
Desc: signature
URL: <https://lists.freedesktop.org/archives/mesa-dev/attachments/20181203/0c15793e/attachment.sig>