Fix PR15346

On Mon, 1 Dec 2014, Joseph Myers wrote:

> On Mon, 1 Dec 2014, Richard Biener wrote:
> 
> > +/* Combine two successive divisions.  */
> > +(for div (trunc_div ceil_div floor_div round_div exact_div)
> 
> This doesn't seem correct for all kinds of division and signedness of 
> arguments.
> 
> TRUNC_DIV_EXPR (C division) and EXACT_DIV_EXPR should be OK regardless.  
> But for CEIL_DIV_EXPR and FLOOR_DIV_EXPR, in ((a / b) / c) you need c to 
> be positive so that both roundings are in the same direction (consider 
> e.g. 3 FLOOR_DIV -2 FLOOR_DIV -2 == 1, but 3 FLOOR_DIV 4 == 0).  And for 
> ROUND_DIV_EXPR, it can be incorrect whatever the signs (e.g. 2 ROUND_DIV 3 
> ROUND_DIV 2 == 1, but 2 ROUND_DIV 6 == 0).
> 
> I'm not sure if these forms of division actually occur in places where 
> this could cause a problem, but it does look like Ada may enable you to 
> generate ROUND_DIV_EXPR.

Hmm.  I thought I was following what extract_muldiv_1 does (but of course
that function is quite hard to follow).

    case TRUNC_DIV_EXPR:  case CEIL_DIV_EXPR:  case FLOOR_DIV_EXPR:
    case ROUND_DIV_EXPR:  case EXACT_DIV_EXPR:
...
      /* If these are the same operation types, we can associate them
         assuming no overflow.  */
      if (tcode == code)
        {
          bool overflow_p = false;
          bool overflow_mul_p;
          signop sign = TYPE_SIGN (ctype);
          wide_int mul = wi::mul (op1, c, sign, &overflow_mul_p);
          overflow_p = TREE_OVERFLOW (c) | TREE_OVERFLOW (op1);
          if (overflow_mul_p
              && ((sign == UNSIGNED && tcode != MULT_EXPR) || sign == 
SIGNED))
            overflow_p = true;
          if (!overflow_p)
            return fold_build2 (tcode, ctype, fold_convert (ctype, op0),
                                wide_int_to_tree (ctype, mul));

but yeah, I see you are correct.  I'll restrict the pattern to
TRUNC_DIV_EXPR and EXACT_DIV_EXPR which are the only ones I've
ever seen generated from C.

I don't know how to generate testcases for the other division
opcodes - eventually we should have builtins just for the sake
of being able to generate testcases...

Committed as obvoious.

Thanks,
Richard.

2014-12-02  Richard Biener  <rguenther@suse.de>

	* match.pd: Restrict division combining to trunc_div and
	exact_div.

On Tue, 2 Dec 2014, Richard Biener wrote:

> > I'm not sure if these forms of division actually occur in places where 
> > this could cause a problem, but it does look like Ada may enable you to 
> > generate ROUND_DIV_EXPR.
> 
> Hmm.  I thought I was following what extract_muldiv_1 does (but of course
> that function is quite hard to follow).

I don't claim existing optimizations are correct for all these forms of 
division.

In fact even wide-int doesn't handle ROUND_DIV_EXPR correctly (round to 
nearest, ties away from 0) - at a glance, without testing, ROUND_MOD_EXPR 
has the same bug (wi::ges_p (wi::abs (remainder), wi::lrshift (wi::abs 
(y), 1)) is not the right condition for rounding away).  The following Ada 
testcase test_round_div.adb will generate a ROUND_DIV_EXPR which is 
executed correctly at -O0, but fails at -O3.  (The separate division 
function seems necessary to stop the front end from doing its own constant 
folding, though there may for all I know be more idiomatic Ada ways of 
doing that.)

procedure Test_Round_Div is
   type Fixed is delta 1.0 range -2147483648.0 .. 2147483647.0;
   A : Fixed := 1.0;
   B : Fixed := 3.0;
   C : Integer;
   function Divide (X, Y : Fixed) return Integer is
   begin
      return Integer (X / Y);
   end;
begin
   C := Divide (A, B);
   if C /= 0 then
      raise Program_Error;
   end if;
end Test_Round_Div;

On Tue, 2 Dec 2014, Joseph Myers wrote:

> (y), 1)) is not the right condition for rounding away).  The following Ada 
> testcase test_round_div.adb will generate a ROUND_DIV_EXPR which is 

I should add that I'm not sure if Ada requires correct rounding for 
fixed-point division converted to integer like this, or, if not, whether 
GNU Ada nevertheless guarantees it; it's simply a case that does generate 
such a ROUND_DIV_EXPR and so can be used to test how ROUND_DIV_EXPR 
behaves (in the absence of built-in functions).