[PATCH] Move fold_div_compare optimization to match.pd (PR tree-optimization/81346)

[Jakub Jelinek]

On Tue, Jul 18, 2017 at 05:21:42PM +0200, Marc Glisse wrote:
> On Tue, 18 Jul 2017, Jakub Jelinek wrote:
> 
> > +/* X / C1 op C2 into a simple range test.  */
> > +(for cmp (simple_comparison)
> > + (simplify
> > +  (cmp (trunc_div:s @0 INTEGER_CST@1) INTEGER_CST@2)
> > +  (if (INTEGRAL_TYPE_P (TREE_TYPE (@0))
> > +       && integer_nonzerop (@1)
> > +       && !TREE_OVERFLOW (@1)
> > +       && !TREE_OVERFLOW (@2))
> 
> (not specific to this patch)
> I wonder if we should check TREE_OVERFLOW for the input that way in many
> more transformations in match.pd, or never, or how to decide in which
> cases to do it...

The reason for putting it here was that: 1) fold_div_compare did that
2) it relies on TREE_OVERFLOW to detect if the optimization is ok or not,
if there are some TREE_OVERFLOW on the inputs, then it might misbehave.

> > +     (with
> > +      {
> > +	tree etype = range_check_type (TREE_TYPE (@0));
> > +	if (etype)
> > +	  {
> > +	    if (! TYPE_UNSIGNED (etype))
> > +	      etype = unsigned_type_for (etype);
> 
> Now that you enforce unsignedness, can you think of cases where going
> through range_check_type is useful compared to
>   tree etype = unsigned_type_for (TREE_TYPE (@0));
> ? I can propose that trivial patch as a follow-up if you like.

I couldn't convince myself it is safe.  While enums and bool are handled
early, aren't there e.g. Ada integral types with weirdo min/max values and
similar stuff where the range_check_type test would fail?  If it never
fails, why we do it there?  The reason I've added unsigned_type_for
afterwards is that that build_range_check actually does something like
that too.
With -fwrapv it will perform the subtraction of lo in whatever type
range_check_type returns (could be e.g. int for -fwrapv) but then
recurses and runs into:
  if (integer_zerop (low))
    {
      if (! TYPE_UNSIGNED (etype))
        {
          etype = unsigned_type_for (etype);
          high = fold_convert_loc (loc, etype, high);
          exp = fold_convert_loc (loc, etype, exp);
        }
      return build_range_check (loc, type, exp, 1, 0, high);
    }
I was thinking whether e.g. range_check_type shouldn't have an extra
argument which would be false for build_range_check and true for
the use in match.pd, and if that arg is false, it would use
!TYPE_OVERFLOW_WRAPS (etype) and if that arg is true, it would
use !TYPE_UNSIGNED (etype) instead.

> > +	    hi = fold_convert (etype, hi);
> > +	    lo = fold_convert (etype, lo);
> > +	    hi = const_binop (MINUS_EXPR, etype, hi, lo);
> > +	  }
> > +      }
> > +      (if (etype && hi && !TREE_OVERFLOW (hi))
> 
> I don't think you can have an overflow here anymore, now that etype is
> always unsigned and since you check the input (doesn't hurt though).

If const_binop for unsigned etype will never return NULL nor TREE_OVERFLOW
on the result, then that can surely go.  But again, I'm not 100% sure.
> 
> > +       (if (code == EQ_EXPR)
> > +	(le (minus (convert:etype @0) { lo; }) { hi; })
> > +	(gt (minus (convert:etype @0) { lo; }) { hi; })))))))))

	Jakub