Re: [PATCH] Fix PR15346

2014-12-02 Thread Richard Biener 
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  rguent...@suse.de

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

Index: gcc/match.pd
===
--- gcc/match.pd(revision 218258)
+++ gcc/match.pd(working copy)
@@ -129,8 +129,9 @@ (define_operator_list inverted_tcc_compa
TYPE_UNSIGNED (type))
   (trunc_div @0 @1)))
 
-/* Combine two successive divisions.  */
-(for div (trunc_div ceil_div floor_div round_div exact_div)
+/* Combine two successive divisions.  Note that combining ceil_div
+   and floor_div is trickier and combining round_div even more so.  */
+(for div (trunc_div exact_div)
  (simplify
   (div (div @0 INTEGER_CST@1) INTEGER_CST@2)
   (with {

Re: [PATCH] Fix PR15346

2014-12-02 Thread Richard Biener 
On Mon, 1 Dec 2014, Marc Glisse wrote:

 On Mon, 1 Dec 2014, Richard Biener wrote:
 
  The following fixes the oldest bug in my list of assigned PRs, namely
  combining A / CST / CST' to A / (CST * CST').  extract_muldiv does
  this in fold-const.c (but it fails to optimize to zero when CST * CST'
  overflows).
  
  Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.
  
  Richard.
  
  2014-12-01  Richard Biener  rguent...@suse.de
  
  PR tree-optimization/15346
  * Makefile.in (gimple-match.o-warn): Remove -Wno-unused-parameter,
  add -Wno-unused-but-set-variable.
  * match.pd: Combine two successive divisions.
  
  * gcc.dg/tree-ssa/forwprop-32.c: New testcase.
  
  Index: gcc/match.pd
  ===
  --- gcc/match.pd(revision 218140)
  +++ gcc/match.pd(working copy)
  @@ -129,6 +129,19 @@ (define_operator_list inverted_tcc_compa
 TYPE_UNSIGNED (type))
(trunc_div @0 @1)))
  
  +/* Combine two successive divisions.  */
  +(for div (trunc_div ceil_div floor_div round_div exact_div)
  + (simplify
  +  (div (div @0 INTEGER_CST@1) INTEGER_CST@2)
  +  (with {
  +bool overflow_p;
  +wide_int mul = wi::mul (@1, @2, TYPE_SIGN (type), overflow_p);
  +   }
  +   (if (!overflow_p)
  +(div @0 { wide_int_to_tree (type, mul); }))
  +   (if (overflow_p)
  +{ build_zero_cst (type); }
  +
 
 Can't you have something like:
 INT_MIN / 2 / (INT_MIN / -2) == -1
 where
 2 * (INT_MIN / -2) overflows?

Hmm, right.  It should work if overflow_p  mul != INT_MIN as far
as I can see.

I am testing the following.

Thanks,
Richard.

2014-12-02  Richard Biener  rguent...@suse.de

* match.pd: When combining divisions exclude the degenerate
case involving INT_MIN from overflow handling.

* gcc.dg/torture/20141202-1.c: New testcase.

Index: gcc/match.pd
===
--- gcc/match.pd(revision 218260)
+++ gcc/match.pd(working copy)
@@ -140,7 +140,9 @@ (define_operator_list inverted_tcc_compa
}
(if (!overflow_p)
 (div @0 { wide_int_to_tree (type, mul); }))
-   (if (overflow_p)
+   (if (overflow_p
+ (TYPE_UNSIGNED (type)
+   || mul != wi::min_value (TYPE_PRECISION (type), SIGNED)))
 { build_zero_cst (type); }
 
 /* Optimize A / A to 1.0 if we don't care about
Index: gcc/testsuite/gcc.dg/torture/20141202-1.c
===
--- gcc/testsuite/gcc.dg/torture/20141202-1.c   (revision 0)
+++ gcc/testsuite/gcc.dg/torture/20141202-1.c   (working copy)
@@ -0,0 +1,15 @@
+/* { dg-do run } */
+
+extern void abort (void);
+
+int foo (int x)
+{
+  return (x / 2) / ((-__INT_MAX__ - 1) / -2);
+}
+
+int main()
+{
+  if (foo (- __INT_MAX__ - 1) != -1)
+abort ();
+  return 0;
+}

Re: [PATCH] Fix PR15346

2014-12-02 Thread Joseph Myers 
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;

-- 
Joseph S. Myers
jos...@codesourcery.com

Re: [PATCH] Fix PR15346

2014-12-02 Thread Joseph Myers 
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).

-- 
Joseph S. Myers
jos...@codesourcery.com

[PATCH] Fix PR15346

2014-12-01 Thread Richard Biener 

The following fixes the oldest bug in my list of assigned PRs, namely
combining A / CST / CST' to A / (CST * CST').  extract_muldiv does
this in fold-const.c (but it fails to optimize to zero when CST * CST'
overflows).

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

2014-12-01  Richard Biener  rguent...@suse.de

PR tree-optimization/15346
* Makefile.in (gimple-match.o-warn): Remove -Wno-unused-parameter,
add -Wno-unused-but-set-variable.
* match.pd: Combine two successive divisions.

* gcc.dg/tree-ssa/forwprop-32.c: New testcase.

Index: gcc/match.pd
===
--- gcc/match.pd(revision 218140)
+++ gcc/match.pd(working copy)
@@ -129,6 +129,19 @@ (define_operator_list inverted_tcc_compa
TYPE_UNSIGNED (type))
   (trunc_div @0 @1)))
 
+/* Combine two successive divisions.  */
+(for div (trunc_div ceil_div floor_div round_div exact_div)
+ (simplify
+  (div (div @0 INTEGER_CST@1) INTEGER_CST@2)
+  (with {
+bool overflow_p;
+wide_int mul = wi::mul (@1, @2, TYPE_SIGN (type), overflow_p);
+   }
+   (if (!overflow_p)
+(div @0 { wide_int_to_tree (type, mul); }))
+   (if (overflow_p)
+{ build_zero_cst (type); }
+
 /* Optimize A / A to 1.0 if we don't care about
NaNs or Infinities.  */
 (simplify
Index: gcc/testsuite/gcc.dg/tree-ssa/forwprop-32.c
===
--- gcc/testsuite/gcc.dg/tree-ssa/forwprop-32.c (revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/forwprop-32.c (working copy)
@@ -0,0 +1,18 @@
+/* { dg-do compile } */
+/* { dg-options -O -fdump-tree-forwprop1 -fdump-tree-ccp1 } */
+
+int foo (int x)
+{
+  int tem = x / 3;
+  return tem / 5;
+}
+int bar (int x)
+{
+  int tem = x / 3;
+  return tem / (__INT_MAX__ / 2);
+}
+
+/* { dg-final { scan-tree-dump x_.\\(D\\) / 15 forwprop1 } } */
+/* { dg-final { scan-tree-dump return 0; ccp1 } } */
+/* { dg-final { cleanup-tree-dump forwprop1 } } */
+/* { dg-final { cleanup-tree-dump ccp1 } } */
Index: gcc/Makefile.in
===
--- gcc/Makefile.in (revision 218142)
+++ gcc/Makefile.in (working copy)
@@ -209,8 +209,8 @@ gengtype-lex.o-warn = -Wno-error
 libgcov-util.o-warn = -Wno-error
 libgcov-driver-tool.o-warn = -Wno-error
 libgcov-merge-tool.o-warn = -Wno-error
-gimple-match.o-warn = -Wno-unused-variable -Wno-unused-parameter
-generic-match.o-warn = -Wno-unused-variable -Wno-unused-parameter
+gimple-match.o-warn = -Wno-unused-variable -Wno-unused-but-set-variable
+generic-match.o-warn = -Wno-unused-variable -Wno-unused-but-set-variable
 
 # All warnings have to be shut off in stage1 if the compiler used then
 # isn't gcc; configure determines that.  WARN_CFLAGS will be either

Re: [PATCH] Fix PR15346

2014-12-01 Thread Ulrich Weigand 
Richard Biener wrote:

   * Makefile.in (gimple-match.o-warn): Remove -Wno-unused-parameter,
   add -Wno-unused-but-set-variable.

This seems to cause

cc1plus: error: unrecognized command line option -Wno-unused-but-set-variable 

   
make[3]: *** [gimple-match.o] Error 1   

   

in stage1 when bootstrapping on SLES 11 (gcc 4.3.4 host compiler).

Bye,
Ulrich

-- 
  Dr. Ulrich Weigand
  GNU/Linux compilers and toolchain
  ulrich.weig...@de.ibm.com

Re: [PATCH] Fix PR15346

2014-12-01 Thread Richard Biener 
On Mon, 1 Dec 2014, Ulrich Weigand wrote:

 Richard Biener wrote:
 
  * Makefile.in (gimple-match.o-warn): Remove -Wno-unused-parameter,
  add -Wno-unused-but-set-variable.
 
 This seems to cause
 
 cc1plus: error: unrecognized command line option 
 -Wno-unused-but-set-variable
 
 make[3]: *** [gimple-match.o] Error 1 
   

 
 in stage1 when bootstrapping on SLES 11 (gcc 4.3.4 host compiler).

Oh.  Hmm, so I guess

build/gengtype-lex.o-warn = -Wno-error
gengtype-lex.o-warn = -Wno-error

and friends are also incorrect for host compilers that do not know
-Wno-error?  Which means we need configure checks and substitutes
for all -Wno-X we use.  4.3 has -Wunused so I can just replace
-Wno-unused-variable -Wno-unused-but-set-variable with
-Wno-unused as a quick fix for you.  Will do that now (I didn't
want to use -Wno-error because that makes the compile quite
uselessly verbose and fails to diagnose real issues).

Thanks for the report,
Richard.

Re: [PATCH] Fix PR15346

2014-12-01 Thread Jakub Jelinek 
On Mon, Dec 01, 2014 at 04:10:35PM +0100, Richard Biener wrote:
 On Mon, 1 Dec 2014, Ulrich Weigand wrote:
 
  Richard Biener wrote:
  
 * Makefile.in (gimple-match.o-warn): Remove -Wno-unused-parameter,
 add -Wno-unused-but-set-variable.
  
  This seems to cause
  
  cc1plus: error: unrecognized command line option 
  -Wno-unused-but-set-variable  

  make[3]: *** [gimple-match.o] Error 1   
  
 
  
  in stage1 when bootstrapping on SLES 11 (gcc 4.3.4 host compiler).
 
 Oh.  Hmm, so I guess
 
 build/gengtype-lex.o-warn = -Wno-error
 gengtype-lex.o-warn = -Wno-error
 
 and friends are also incorrect for host compilers that do not know
 -Wno-error?  Which means we need configure checks and substitutes
 for all -Wno-X we use.  4.3 has -Wunused so I can just replace
 -Wno-unused-variable -Wno-unused-but-set-variable with
 -Wno-unused as a quick fix for you.  Will do that now (I didn't
 want to use -Wno-error because that makes the compile quite
 uselessly verbose and fails to diagnose real issues).

No, -Wno-error or -Wno-unused in there is just fine.
$($(@D)-warn) and $($@-warn) are only added to GCC_WARN_C{,XX}FLAGS vars
and those are added only if the compiler is GCC.

Jakub

Re: [PATCH] Fix PR15346

2014-12-01 Thread Marc Glisse 

On Mon, 1 Dec 2014, Richard Biener wrote:


The following fixes the oldest bug in my list of assigned PRs, namely
combining A / CST / CST' to A / (CST * CST').  extract_muldiv does
this in fold-const.c (but it fails to optimize to zero when CST * CST'
overflows).

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

2014-12-01  Richard Biener  rguent...@suse.de

PR tree-optimization/15346
* Makefile.in (gimple-match.o-warn): Remove -Wno-unused-parameter,
add -Wno-unused-but-set-variable.
* match.pd: Combine two successive divisions.

* gcc.dg/tree-ssa/forwprop-32.c: New testcase.

Index: gcc/match.pd
===
--- gcc/match.pd(revision 218140)
+++ gcc/match.pd(working copy)
@@ -129,6 +129,19 @@ (define_operator_list inverted_tcc_compa
   TYPE_UNSIGNED (type))
  (trunc_div @0 @1)))

+/* Combine two successive divisions.  */
+(for div (trunc_div ceil_div floor_div round_div exact_div)
+ (simplify
+  (div (div @0 INTEGER_CST@1) INTEGER_CST@2)
+  (with {
+bool overflow_p;
+wide_int mul = wi::mul (@1, @2, TYPE_SIGN (type), overflow_p);
+   }
+   (if (!overflow_p)
+(div @0 { wide_int_to_tree (type, mul); }))
+   (if (overflow_p)
+{ build_zero_cst (type); }
+


Can't you have something like:
INT_MIN / 2 / (INT_MIN / -2) == -1
where
2 * (INT_MIN / -2) 
overflows?


--
Marc Glisse

Re: [PATCH] Fix PR15346

2014-12-01 Thread Joseph Myers 
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.

-- 
Joseph S. Myers
jos...@codesourcery.com