[PATCH] Expand LSHIFT_EXPR as sequence of additions

[Roger Sayle]

The following patch tweaks the middle-end's expand_shift function to
consider implementing left shifts by an integer constant by an inline
chain of additions.  Now that combine will no longer collapse addition
chains if that isn't profitable, we can improve code generation by
choosing better instruction sequences during initial RTL expansion.


With this patch the following functions

int shift2(int x)
{
  return x << 2;
}

int shift3(int x)
{
  return x << 3;
}


are now expanded as two additions for the first, but as a shift for
the second when tuning for the pentium4 (with "-O2 -fomit-frame-pointer).

shift2: movl    4(%esp), %eax
        addl    %eax, %eax
        addl    %eax, %eax
        ret

shift3: movl    4(%esp), %eax
        sall    $3, %eax
        ret


I've also updated the "cost" calculation in synth_mult, so that its aware
of the changes to expand_shift, such it uses an accurate "observed"
cost for a "virtual shift".  The semantics of shift_cost remain the same,
the cost of a real shift instruction, and can be used for both left and
right shifts.


The following patch has been tested on i686-pc-linux-gnu with a complete
"make bootstrap", all default languages, and regression tested with a
top-level "make -k check" with no new failures.

Ok for mainline?



2004-06-30  Roger Sayle  <roger@eyesopen.com>

	* expmed.c (expand_shift): Consider expanding LSHIFT_EXPR by a
	constant as a sequence of additions depending upon the rtx_costs.
	(synth_mult): Update the "observed" cost of a shift, based upon
	the above optimization.


Index: expmed.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/expmed.c,v
retrieving revision 1.172
diff -c -3 -p -r1.172 expmed.c
*** expmed.c	30 Jun 2004 12:30:00 -0000	1.172
--- expmed.c	30 Jun 2004 21:34:42 -0000
*************** expand_shift (enum tree_code code, enum
*** 2017,2022 ****
--- 2017,2040 ----
    if (op1 == const0_rtx)
      return shifted;

+   /* Check whether its cheaper to implement a left shift by a constant
+      bit count by a sequence of additions.  */
+   if (code == LSHIFT_EXPR
+       && GET_CODE (op1) == CONST_INT
+       && INTVAL (op1) > 0
+       && INTVAL (op1) < GET_MODE_BITSIZE (mode)
+       && shift_cost[mode][INTVAL (op1)] > INTVAL (op1) * add_cost[mode])
+     {
+       int i;
+       for (i = 0; i < INTVAL (op1); i++)
+ 	{
+ 	  temp = force_reg (mode, shifted);
+ 	  shifted = expand_binop (mode, add_optab, temp, temp, NULL_RTX,
+ 				  unsignedp, OPTAB_LIB_WIDEN);
+ 	}
+       return shifted;
+     }
+
    for (try = 0; temp == 0 && try < 3; try++)
      {
        enum optab_methods methods;
*************** synth_mult (struct algorithm *alg_out, u
*** 2242,2248 ****
        if (m < maxm)
  	{
  	  q = t >> m;
! 	  cost = shift_cost[mode][m];
  	  synth_mult (alg_in, q, cost_limit - cost, mode);

  	  cost += alg_in->cost;
--- 2260,2271 ----
        if (m < maxm)
  	{
  	  q = t >> m;
! 	  /* The function expand_shift will choose between a shift and
! 	     a sequence of additions, so the observed cost is given as
! 	     MIN (m * add_cost[mode], shift_cost[mode][m]).  */
! 	  cost = m * add_cost[mode];
! 	  if (shift_cost[mode][m] < cost)
! 	    cost = shift_cost[mode][m];
  	  synth_mult (alg_in, q, cost_limit - cost, mode);

  	  cost += alg_in->cost;

Roger
--
Roger Sayle,                         E-mail: roger@eyesopen.com
OpenEye Scientific Software,         WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road,     Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507.         Fax: (+1) 505-473-0833