This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH][4.3] Backport fix for PR32044


This backports the fix for PR32044 (the famous final value replacement
bug).

Bootstrapped and tested on {x86_64,i586,ppc,ppc64,s390,s390x,ia64}-linux,
applied to the branch.

Richard.


	Backport from mainline
	2008-12-12  Zdenek Dvorak  <ook@ucw.cz>

	PR tree-optimization/32044
	* tree-scalar-evolution.h (expression_expensive_p): Declare.
	* tree-scalar-evolution.c (expression_expensive_p): New function.
	(scev_const_prop): Avoid introducing expensive expressions.
	* tree-ssa-loop-ivopts.c (may_eliminate_iv): Ditto.

	* gcc.dg/pr34027-1.c: Change outcome.
	* gcc.dg/tree-ssa/pr32044.c: New test.

Index: gcc/testsuite/gcc.dg/pr34027-1.c
===================================================================
--- gcc/testsuite/gcc.dg/pr34027-1.c	(revision 142718)
+++ gcc/testsuite/gcc.dg/pr34027-1.c	(revision 142719)
@@ -8,5 +8,9 @@ unsigned long foobar(unsigned long ns)
   return ns;
 }
 
-/* { dg-final { scan-tree-dump "ns % 10000" "optimized" } } */
+/* This test was originally introduced to test that we transform
+   to ns % 10000.  See the discussion of PR 32044 why we do not do
+   that anymore.  */
+/* { dg-final { scan-tree-dump-times "%" 0 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "/" 0 "optimized" } } */
 /* { dg-final { cleanup-tree-dump "optimized" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/pr32044.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/pr32044.c	(revision 0)
+++ gcc/testsuite/gcc.dg/tree-ssa/pr32044.c	(revision 142719)
@@ -0,0 +1,55 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-empty -fdump-tree-final_cleanup" } */
+
+int foo (int n)
+{
+  while (n >= 45)
+    n -= 45;
+
+  return n;
+}
+
+int bar (int n)
+{
+  while (n >= 64)
+    n -= 64;
+
+  return n;
+}
+
+int bla (int n)
+{
+  int i = 0;
+
+  while (n >= 45)
+    {
+      i++;
+      n -= 45;
+    }
+
+  return i;
+}
+
+int baz (int n)
+{
+  int i = 0;
+
+  while (n >= 64)
+    {
+      i++;
+      n -= 64;
+    }
+
+  return i;
+}
+
+/* The loops computing division/modulo by 64 should be eliminated.  */
+/* { dg-final { scan-tree-dump-times "Removing empty loop" 2 "empty" } } */
+
+/* There should be no division/modulo in the final dump (division and modulo
+   by 64 are done using bit operations).  */
+/* { dg-final { scan-tree-dump-times "/" 0 "final_cleanup" } } */
+/* { dg-final { scan-tree-dump-times "%" 0 "final_cleanup" } } */
+
+/* { dg-final { cleanup-tree-dump "empty" } } */
+/* { dg-final { cleanup-tree-dump "final_cleanup" } } */
Index: gcc/tree-ssa-loop-ivopts.c
===================================================================
--- gcc/tree-ssa-loop-ivopts.c	(revision 142718)
+++ gcc/tree-ssa-loop-ivopts.c	(revision 142719)
@@ -3844,7 +3844,12 @@ may_eliminate_iv (struct ivopts_data *da
     return false;
 
   cand_value_at (loop, cand, use->stmt, nit, &bnd);
+
   *bound = aff_combination_to_tree (&bnd);
+  /* It is unlikely that computing the number of iterations using division
+     would be more profitable than keeping the original induction variable.  */
+  if (expression_expensive_p (*bound))
+    return false;
   return true;
 }
 
Index: gcc/tree-scalar-evolution.c
===================================================================
*** gcc/tree-scalar-evolution.c	(revision 147732)
--- gcc/tree-scalar-evolution.c	(working copy)
*************** scev_finalize (void)
*** 2714,2719 ****
--- 2714,2763 ----
    scalar_evolution_info = NULL;
  }
  
+ /* Returns true if the expression EXPR is considered to be too expensive
+    for scev_const_prop.  */
+ 
+ bool
+ expression_expensive_p (tree expr)
+ {
+   enum tree_code code;
+ 
+   if (is_gimple_val (expr))
+     return false;
+ 
+   code = TREE_CODE (expr);
+   if (code == TRUNC_DIV_EXPR
+       || code == CEIL_DIV_EXPR
+       || code == FLOOR_DIV_EXPR
+       || code == ROUND_DIV_EXPR
+       || code == TRUNC_MOD_EXPR
+       || code == CEIL_MOD_EXPR
+       || code == FLOOR_MOD_EXPR
+       || code == ROUND_MOD_EXPR
+       || code == EXACT_DIV_EXPR)
+     {
+       /* Division by power of two is usually cheap, so we allow it.
+ 	 Forbid anything else.  */
+       if (!integer_pow2p (TREE_OPERAND (expr, 1)))
+ 	return true;
+     }
+ 
+   switch (TREE_CODE_CLASS (code))
+     {
+     case tcc_binary:
+     case tcc_comparison:
+       if (expression_expensive_p (TREE_OPERAND (expr, 1)))
+ 	return true;
+ 
+       /* Fallthru.  */
+     case tcc_unary:
+       return expression_expensive_p (TREE_OPERAND (expr, 0));
+ 
+     default:
+       return true;
+     }
+ }
+ 
  /* Replace ssa names for that scev can prove they are constant by the
     appropriate constants.  Also perform final value replacement in loops,
     in case the replacement expressions are cheap.
*************** scev_const_prop (void)
*** 2800,2811 ****
  	continue;
  
        niter = number_of_latch_executions (loop);
-       /* We used to check here whether the computation of NITER is expensive,
- 	 and avoided final value elimination if that is the case.  The problem
- 	 is that it is hard to evaluate whether the expression is too
- 	 expensive, as we do not know what optimization opportunities the
- 	 the elimination of the final value may reveal.  Therefore, we now
- 	 eliminate the final values of induction variables unconditionally.  */
        if (niter == chrec_dont_know)
  	continue;
  
--- 2844,2849 ----
*************** scev_const_prop (void)
*** 2836,2842 ****
  	      /* Moving the computation from the loop may prolong life range
  		 of some ssa names, which may cause problems if they appear
  		 on abnormal edges.  */
! 	      || contains_abnormal_ssa_name_p (def))
  	    continue;
  
  	  /* Eliminate the PHI node and replace it by a computation outside
--- 2874,2888 ----
  	      /* Moving the computation from the loop may prolong life range
  		 of some ssa names, which may cause problems if they appear
  		 on abnormal edges.  */
! 	      || contains_abnormal_ssa_name_p (def)
! 	      /* Do not emit expensive expressions.  The rationale is that
! 		 when someone writes a code like
! 
! 		 while (n > 45) n -= 45;
! 
! 		 he probably knows that n is not large, and does not want it
! 		 to be turned into n %= 45.  */
! 	      || expression_expensive_p (def))
  	    continue;
  
  	  /* Eliminate the PHI node and replace it by a computation outside
Index: gcc/tree-scalar-evolution.h
===================================================================
*** gcc/tree-scalar-evolution.h	(revision 147732)
--- gcc/tree-scalar-evolution.h	(working copy)
*************** extern void gather_stats_on_scev_databas
*** 35,40 ****
--- 35,41 ----
  extern void scev_analysis (void);
  unsigned int scev_const_prop (void);
  
+ bool expression_expensive_p (tree);
  extern bool simple_iv (struct loop *, tree, tree, affine_iv *, bool);
  
  /* Returns the loop of the polynomial chrec CHREC.  */


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]