[Mesa-dev] [PATCH 1/2] nir/algebraic: Rewrite bit-size inference
Dylan Baker
dylan at pnwbakers.com
Tue Dec 4 17:19:00 UTC 2018
Quoting Connor Abbott (2018-12-04 01:58:28)
> On Mon, Dec 3, 2018 at 11:39 PM Dylan Baker <dylan at pnwbakers.com> wrote:
> >
> > 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.
> >
> > If it's not a hot path I'm okay with that then, the `if not foo` is about 4x
> > faster than `if foo == 0`, so if it's really hot it might be worth the tradeoff.
> >
> > Maybe I'll add type annotations after we drop python2 support.
>
> The largest script that uses this is nir_opt_algebraic.py, which
> finishes in well under half a second on my machine, so I don't think
> it's too important to optimize for speed. I'd agree with Jason that ==
> 0 is more readable here since "not foo" doesn't tell you anything
> about the type of foo.
I mean, it is a duck typed language :)
If it's not a hot path then go ahead and leave it.
>
> >
> > >
> > >
> > > > + 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.
> > >
> > > --Jason
-------------- 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/20181204/2691bf9f/attachment.sig>
More information about the mesa-dev
mailing list