Pessimization in doloop

[Bernd Schmidt <bernds_cb1 at t-online dot de>]

Consider this testcase, reduced from sqlite:

struct a {
     unsigned int init;
     unsigned int size;
};

unsigned int foo (struct a *pa, const char *p) {
   unsigned int cksum = pa->init;
   int i = pa->size - 200;
   while( i>0 ){
     cksum += p[i];
     i -= 200;
   }
   return cksum;
}

I discovered that with our gcc-4.1 based Blackfin compiler, the doloop 
optimization pass decides to get clever, and determines it can compute 
the number of iterations as follows:
   number of iterations: (udiv:SI (plus:SI (reg/v:SI 69 [ i ])
         (const_int -1 [0xffffffff]))
     (const_int 200 [0xc8]))

That's correct, but passing this through force_operand results in a
sequence involving a libcall to __udivsi3, which is hardly an
optimization anymore.  Since this doesn't happen with a 3.4 based 
compiler, I'm calling it a regression.

This patch fixes the pessimization by looking at the costs involved in
the operation.  The cutoff is tunable, for the moment it stops if the 
cost of computing the number of iterations is more than 10 simple 
instructions.

Bootstrapped on i686-linux, regression tested against bfin-elf. 
Committed on trunk as 116966.


Bernd

Index: ChangeLog
===================================================================
--- ChangeLog	(revision 116965)
+++ ChangeLog	(working copy)
@@ -1,3 +1,9 @@
+2005-09-15  Bernd Schmidt  <bernd.schmidt@analog.com>
+
+	* params.def (PARAM_MAX_ITERATIONS_COMPUTATION_COST): New.
+	* loop-doloop.c (doloop_optimize): Use it to limit costs of
+	expanding the number of iterations.
+
 2006-09-15  Kazu Hirata  <kazu@codesourcery.com>
 
 	* doc/tm.texi (TARGET_FUNCTION_VALUE): Put @deftypefn all in
Index: loop-doloop.c
===================================================================
--- loop-doloop.c	(revision 116965)
+++ loop-doloop.c	(working copy)
@@ -484,7 +484,7 @@
   rtx iterations_max;
   rtx start_label;
   rtx condition;
-  unsigned level, est_niter;
+  unsigned level, est_niter, max_cost;
   struct niter_desc *desc;
   unsigned word_mode_size;
   unsigned HOST_WIDE_INT word_mode_max;
@@ -525,6 +525,17 @@
       return false;
     }
 
+  max_cost
+    = COSTS_N_INSNS (PARAM_VALUE (PARAM_MAX_ITERATIONS_COMPUTATION_COST));
+  if (rtx_cost (desc->niter_expr, SET) > max_cost)
+    {
+      if (dump_file)
+	fprintf (dump_file,
+		 "Doloop: number of iterations too costly to compute.\n",
+		 est_niter);
+      return false;
+    }
+
   count = copy_rtx (desc->niter_expr);
   iterations = desc->const_iter ? desc->niter_expr : const0_rtx;
   iterations_max = GEN_INT (desc->niter_max);
Index: params.def
===================================================================
--- params.def	(revision 116965)
+++ params.def	(working copy)
@@ -292,6 +292,12 @@
 	"max-iterations-to-track",
 	"Bound on the number of iterations the brute force # of iterations analysis algorithm evaluates",
 	1000, 0, 0)
+/* A cutoff to avoid costly computations of the number of iterations in
+   the doloop transformation.  */
+DEFPARAM(PARAM_MAX_ITERATIONS_COMPUTATION_COST,
+	"max-iterations-computation-cost",
+	"Bound on the cost of an expression to compute the number of iterations",
+	10, 0, 0)
 
 DEFPARAM(PARAM_MAX_SMS_LOOP_NUMBER,
 	 "max-sms-loop-number",