expmed synth_multiply patch

[Jeffrey A Law <law at cygnus dot com>]

Given this call to expand_mult:

mode =	SImode
op0 = 	(reg/v:SI 94)
op1 =	(const_int -1)

We choose the following algorithm:

(gdb) p alg.op[0]
$5 = alg_m
(gdb) p alg.op[1]
$6 = alg_sub_t2_m
(gdb) p alg.op[2]
$7 = alg_add_factor


alg_m:   	t = r94
alg_sub_t2_m:	t = t * -1 - r94
alg_add_factor:	t = t * -1 + t

Note that the "add_factor" step will always produce the value zero, which
is obviously wrong.  It's also interesting to note this case took 54 calls
to synth_multiply!  Seems rather high.

Anyway, T is odd, so we end up in this code:

  /* If we have an odd number, add or subtract one.  */
  if ((t & 1) != 0)
    {
      unsigned HOST_WIDE_INT w;

      for (w = 1; (w & t) != 0; w <<= 1)
        ;
      if (w > 2
          /* Reject the case where t is 3.
             Thus we prefer addition in that case.  */
          && t != 3)
        {
          /* T ends with ...111.  Multiply by (T + 1) and subtract 1.  */
[ ... ]
      else
        {
          /* T ends with ...01 or ...011.  Multiply by (T - 1) and add 1.  */
[ ... ]

Interestingly enough we end up in the else clause even though the value -1
doesn't have any zeros.  This is because W will have the value zero at loop
exit if T == -1.

This may be the root of the problem, then again it may not.  I don't know this
code well enough to be sure either way.

If we force -1 to be handled by the first if clause (...111.), then we get
the right result, with a better alg and only 7 calls to synth_mult.


Tege -- thoughts?


	* expmed.c (synth_mult): The value -1, has no zeros, so it can
	never have the form ...011.

Index: expmed.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/./gcc/expmed.c,v
retrieving revision 1.9
diff -c -3 -p -r1.9 expmed.c
*** expmed.c	1998/03/20 14:57:57	1.9
--- expmed.c	1998/03/27 23:06:19
*************** synth_mult (alg_out, t, cost_limit)
*** 1992,2001 ****
  
        for (w = 1; (w & t) != 0; w <<= 1)
  	;
!       if (w > 2
! 	  /* Reject the case where t is 3.
! 	     Thus we prefer addition in that case.  */
! 	  && t != 3)
  	{
  	  /* T ends with ...111.  Multiply by (T + 1) and subtract 1.  */
  
--- 1992,2007 ----
  
        for (w = 1; (w & t) != 0; w <<= 1)
  	;
!       /* If T was -1, then W will be zero after the loop.  This is another
! 	 case where T ends with ...111.  Handling this with (T + 1) and 
! 	 subtract 1 produces slightly better code and results in algorithm
! 	 selection much faster than treating it like the ...0111 case
! 	 below.  */
!       if (w == 0
! 	  || (w > 2
! 	      /* Reject the case where t is 3.
! 		 Thus we prefer addition in that case.  */
! 	      && t != 3))
  	{
  	  /* T ends with ...111.  Multiply by (T + 1) and subtract 1.  */