On 09/05/2018 08:58 AM, Michael Matz wrote:
Hi,

On Tue, 4 Sep 2018, Aldy Hernandez wrote:

to make the result ~[0, 5], is it?  At least the original code dropped
that to VARYING.  For the same reason truncating [3, 765] from
short to unsigned char isn't [3, 253].  But maybe I'm missing something.

Sorry for chiming in, but this catched my eye:

No apologies needed. I welcome all masochists to join me in my personal hell :).


Correct, but in that case we will realize that in wide_int_range_convert and
refuse to do the conversion:

   /* If the conversion is not truncating we can convert the min and
      max values and canonicalize the resulting range.  Otherwise we
      can do the conversion if the size of the range is less than what
      the precision of the target type can represent.  */
   if (outer_prec >= inner_prec
       || wi::rshift (wi::sub (vr0_max, vr0_min),
                     wi::uhwi (outer_prec, inner_prec),
                     inner_sign) == 0)
(followed by this code:)
+    {
+      min = widest_int::from (vr0_min, inner_sign);
+      max = widest_int::from (vr0_max, inner_sign);
+      widest_int min_value
+       = widest_int::from (wi::min_value (outer_prec, outer_sign),outer_sign);
+      widest_int max_value
+       = widest_int::from (wi::max_value (outer_prec, outer_sign),outer_sign);
+      return !wi::eq_p (min, min_value) || !wi::eq_p (max, max_value);
+    }
+  return false;

How can this test and following code catch all problematic cases?  Assume
a range of [253..257], truncating to 8 bits unsigned.  The size of the
range is 5 (not 4 as the code above calculates), well representable in 8
bits.  Nevertheless, the min of the new range isn't 253, nor is the max of
the new range 257.  In fact the new range must be [0..255] (if you have no
multi ranges or anti-ranges).  So whatever this function is supposed to
do (what btw?), it certainly does not convert a range.

Welcome to the wonderful world of anti ranges, where nothing is as it seems.

First you're not looking at what's currently in mainline. Richard approved the first incantation of this code. But even so, I believe the above is correct as well.

What you're missing is the call to set_and_canonicalize_value_range in the caller which will transform ranges into anti-ranges when the returned range has min/max swapped:

     if (wide_int_range_convert (wmin, wmax,
                                  inner_sign, inner_prec,
                                  outer_sign, outer_prec,
                                  vr0_min, vr0_max))
        {
          tree min = wide_int_to_tree (outer_type, wmin);
          tree max = wide_int_to_tree (outer_type, wmax);
          set_and_canonicalize_value_range (vr, vr_type, min, max, NULL);
        }


Take your truncating example of [253, 257]. Wide_int_range_convert will return [253,1] and set_and_canonicalize_value_range will transform this into ~[2, 252].

See:
  /* Wrong order for min and max, to swap them and the VR type we need
     to adjust them.  */
  if (tree_int_cst_lt (max, min))

Also, I took care of documenting this need for canonizing in my code:

...
   Caller is responsible for canonicalizing the resulting range.  */

If desired, I could further document that the range returned may have its contents swapped and that is why it needs canonizing. But hey, that shit was already broken when I got here ;-).

If you follow the code in tree-vrp.c before my patch you will see that the path is the same... we calculate a nonsensical range of [253, 1] and then massage it into ~[2, 252] in set_and_canonicalize_value_range.

I think the fact that it's so hard to get all this right, is a strong argument for getting rid of anti ranges. Almost all the bugs or oversights I've fixed over the past months in VRP have been related to anti ranges.

Aldy

Reply via email to