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

["Richard Guenther" <richard.guenther@gmail.com>]

[-- 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" } } */