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