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

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

# expmed synth_multiply patch

• To: tege at matematik dot su dot se
• Subject: expmed synth_multiply patch
• From: Jeffrey A Law <law at cygnus dot com>
• Date: Fri, 27 Mar 1998 16:17:48 -0700
• cc: egcs at cygnus dot com
• Reply-To: 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
\$5 = alg_m
(gdb) p alg.op
\$6 = alg_sub_t2_m
(gdb) p alg.op

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.  */

```

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