[PATCH] Fix PR34027, SCEV const-prop pessimizes -Os

[PATCH] Fix PR34027, SCEV const-prop pessimizes -Os

[Richard Guenther]

[-- Attachment #1: Type: text/plain, Size: 777 bytes --]

With the now famous enough testcase

unsigned long long foobar(unsigned long long ns)
{
  while(ns >= 1000000000L)
    ns -= 1000000000L;
  return ns;
}

SCEV const-prop creates the expression

  ns + (ns /[fl] 1000000000L) / -1000000000L

for the final value of ns and we are not able to fold this
to the more efficient modulus expression,

The following patch does extend fold to handle this
case, but as it was very late when I wrote this patch I'd
appreciate another eye on possible corner-cases that
we could get wrong.

Thanks,
Richard.

2007-11-11  Richard Guenther  <rguenther@suse.de>

        PR middle-end/34027
        * fold-const.c (fold_binary): Fold n - (n / m) * m to n % m.

        * gcc.dg/pr34027-1.c: New testcase.
        * gcc.dg/pr34027-2.c: Likewise.

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: fix-pr34027.diff --]
[-- Type: text/x-patch; name=fix-pr34027.diff, Size: 3531 bytes --]

2007-11-11  Richard Guenther  <rguenther@suse.de>

	PR middle-end/34027
	* fold-const.c (fold_binary): Fold n - (n / m) * m to n % m.

	* gcc.dg/pr34027-1.c: New testcase.
	* gcc.dg/pr34027-2.c: Likewise.

Index: fold-const.c
===================================================================
*** fold-const.c	(revision 130076)
--- fold-const.c	(working copy)
*************** fold_binary (enum tree_code code, tree t
*** 9653,9658 ****
--- 9653,9677 ----
  		  return omit_one_operand (type, t1, arg0);
  		}
  	    }
+ 
+ 	  /* X + (X / CST) * -CST is X % CST.  */
+ 	  if (TREE_CODE (arg1) == MULT_EXPR
+ 	      && (TREE_CODE (TREE_OPERAND (arg1, 0)) == TRUNC_DIV_EXPR
+ 		  || TREE_CODE (TREE_OPERAND (arg1, 0)) == FLOOR_DIV_EXPR)
+ 	      && operand_equal_p (arg0,
+ 				  TREE_OPERAND (TREE_OPERAND (arg1, 0), 0), 0))
+ 	    {
+ 	      tree cst0 = TREE_OPERAND (TREE_OPERAND (arg1, 0), 1);
+ 	      tree cst1 = TREE_OPERAND (arg1, 1);
+ 	      tree diff = fold_binary (PLUS_EXPR, TREE_TYPE (cst1), cst1,
+ 				       fold_convert (TREE_TYPE (cst1), cst0));
+ 	      enum tree_code code;
+ 	      code = TREE_CODE (TREE_OPERAND (arg1, 0)) == TRUNC_DIV_EXPR
+ 		     ? TRUNC_MOD_EXPR : FLOOR_MOD_EXPR;
+ 	      if (diff && integer_zerop (diff))
+ 		return fold_build2 (code, type, op0,
+ 				    fold_convert (type, cst0));
+ 	    }
  	}
  
        /* Handle (A1 * C1) + (A2 * C2) with A1, A2 or C1, C2 being the
*************** fold_binary (enum tree_code code, tree t
*** 10061,10066 ****
--- 10080,10106 ----
  	  && integer_all_onesp (arg0))
  	return fold_build1 (BIT_NOT_EXPR, type, op1);
  
+ 
+       /* X - (X / CST) * CST is X % CST.  */
+       if (INTEGRAL_TYPE_P (type)
+ 	  && TREE_CODE (arg1) == MULT_EXPR
+ 	  && (TREE_CODE (TREE_OPERAND (arg1, 0)) == TRUNC_DIV_EXPR
+ 	      || TREE_CODE (TREE_OPERAND (arg1, 0)) == FLOOR_DIV_EXPR)
+ 	  && operand_equal_p (arg0,
+ 			      TREE_OPERAND (TREE_OPERAND (arg1, 0), 0), 0))
+ 	{
+ 	  tree cst0 = TREE_OPERAND (TREE_OPERAND (arg1, 0), 1);
+ 	  tree cst1 = TREE_OPERAND (arg1, 1);
+ 	  tree diff = fold_binary (MINUS_EXPR, TREE_TYPE (cst1), cst1,
+ 				   fold_convert (TREE_TYPE (cst1), cst0));
+ 	  enum tree_code code;
+ 	  code = TREE_CODE (TREE_OPERAND (arg1, 0)) == TRUNC_DIV_EXPR
+ 		 ? TRUNC_MOD_EXPR : FLOOR_MOD_EXPR;
+ 	  if (diff && integer_zerop (diff))
+ 	    return fold_build2 (code, type, op0,
+ 				fold_convert (type, cst0));
+ 	}
+ 
        if (! FLOAT_TYPE_P (type))
  	{
  	  if (integer_zerop (arg0))
Index: testsuite/gcc.dg/pr34027-1.c
===================================================================
*** testsuite/gcc.dg/pr34027-1.c	(revision 0)
--- testsuite/gcc.dg/pr34027-1.c	(revision 0)
***************
*** 0 ****
--- 1,12 ----
+ /* { dg-do compile } */
+ /* { dg-options "-Os -fdump-tree-optimized" } */
+ 
+ unsigned long foobar(unsigned long ns)
+ {
+   while(ns >= 10000L)
+     ns -= 10000L;
+   return ns;
+ }
+ 
+ /* { dg-final { scan-tree-dump "ns %\\\[fl\\\] 10000" "optimized" } } */
+ /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: testsuite/gcc.dg/pr34027-2.c
===================================================================
*** testsuite/gcc.dg/pr34027-2.c	(revision 0)
--- testsuite/gcc.dg/pr34027-2.c	(revision 0)
***************
*** 0 ****
--- 1,10 ----
+ /* { dg-do compile } */
+ /* { dg-options "-fdump-tree-gimple" } */
+ 
+ long foo(long n, long m)
+ {
+   return n - (n / m) * m;
+ }
+ 
+ /* { dg-final { scan-tree-dump "n % m" "gimple" } } */
+ /* { dg-final { cleanup-tree-dump "gimple" } } */

Re: [PATCH] Fix PR34027, SCEV const-prop pessimizes -Os

[Manuel López-Ibáñez]

Richard, should this transformation be documented in
http://gcc.gnu.org/wiki/Simplifications ?

Thanks,

Manuel.

Re: [PATCH] Fix PR34027, SCEV const-prop pessimizes -Os

[Richard Guenther]

On Nov 12, 2007 4:15 PM, Manuel López-Ibáñez <lopezibanez@gmail.com> wrote:
> Richard, should this transformation be documented in
> http://gcc.gnu.org/wiki/Simplifications ?

No idea - this list looks very incomplete.

Richard.

Re: [PATCH] Fix PR34027, SCEV const-prop pessimizes -Os

[Andrew Pinski]

On 11/12/07, Richard Guenther <richard.guenther@gmail.com> wrote:
> On Nov 12, 2007 4:15 PM, Manuel López-Ibáñez <lopezibanez@gmail.com> wrote:
> > Richard, should this transformation be documented in
> > http://gcc.gnu.org/wiki/Simplifications ?
>
> No idea - this list looks very incomplete.

It is very incomplete because nobody edits it that much.  I tried to
add the ones I find while working but I don't always add them
everytime I see one.

-- Pinski

Re: [PATCH] Fix PR34027, SCEV const-prop pessimizes -Os

[Manuel López-Ibáñez]

On 12/11/2007, Andrew Pinski <pinskia@gmail.com> wrote:
> On 11/12/07, Richard Guenther <richard.guenther@gmail.com> wrote:
> > On Nov 12, 2007 4:15 PM, Manuel López-Ibáñez <lopezibanez@gmail.com> wrote:
> > > Richard, should this transformation be documented in
> > > http://gcc.gnu.org/wiki/Simplifications ?
> >
> > No idea - this list looks very incomplete.
>
> It is very incomplete because nobody edits it that much.  I tried to
> add the ones I find while working but I don't always add them
> everytime I see one.
>

And it will get more incomplete if no one bothers to document the
transformations that they add...

If the page is useless, it would be better just to delete it altogether.

Cheers,

Manuel.

Re: [PATCH] Fix PR34027, SCEV const-prop pessimizes -Os

[Bernd Schmidt]

Richard Guenther wrote:
> With the now famous enough testcase
> 
> unsigned long long foobar(unsigned long long ns)
> {
>   while(ns >= 1000000000L)
>     ns -= 1000000000L;
>   return ns;
> }
> 
> SCEV const-prop creates the expression
> 
>   ns + (ns /[fl] 1000000000L) / -1000000000L
> 
> for the final value of ns

Am I the only one here who thinks this is a spectacularly bad idea?
Divisions are expensive, especially on targets without hardware divide.


Bernd
-- 
This footer brought to you by insane German lawmakers.
Analog Devices GmbH      Wilhelm-Wagenfeld-Str. 6      80807 Muenchen
Sitz der Gesellschaft Muenchen, Registergericht Muenchen HRB 40368
Geschaeftsfuehrer Thomas Wessel, William A. Martin, Margaret Seif

Re: [PATCH] Fix PR34027, SCEV const-prop pessimizes -Os

[Richard Guenther]

On Nov 13, 2007 1:29 AM, Bernd Schmidt <bernds_cb1@t-online.de> wrote:
> Richard Guenther wrote:
> > With the now famous enough testcase
> >
> > unsigned long long foobar(unsigned long long ns)
> > {
> >   while(ns >= 1000000000L)
> >     ns -= 1000000000L;
> >   return ns;
> > }
> >
> > SCEV const-prop creates the expression
> >
> >   ns + (ns /[fl] 1000000000L) / -1000000000L
> >
> > for the final value of ns
>
> Am I the only one here who thinks this is a spectacularly bad idea?
> Divisions are expensive, especially on targets without hardware divide.

No you are not ;)  In fact the kernel people complained about this
already.

Richard.