Quoting Jason Ekstrand (2018-12-03 14:12:41) > On Mon, Dec 3, 2018 at 3:50 PM Dylan Baker <[email protected]> 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
signature.asc
Description: signature
_______________________________________________ mesa-dev mailing list [email protected] https://lists.freedesktop.org/mailman/listinfo/mesa-dev
