AVR signed int / 2 divide

[Marek Michalkiewicz <marekm at t19 dot ds dot pwr dot wroc dot pl>]

I use the current CVS gcc and binutils for the avr target, it
works quite well but recently I've found this.

Consider these two functions ("int" is 16 bits):

int idiv2(int x) { return x / 2; }
int idiv4(int x) { return x / 4; }

For idiv4() gcc does the right thing and generates code that is
almost perfect, equivalent to this:

	if (x < 0) x += 3;
	return x >> 2;

(could still be optimized by one instruction, but that's not
critical so let's save it for later).  Same for 8, 16, ...

The problem is with idiv2() - the code for x / 2 is correct but
inefficient, equivalent to this:

	return (x + ((unsigned int) x >> 15)) >> 1;

when it would be better done like this (similar to x / 4):

	if (x < 0) x++;
	return x >> 1;

I think I found the place where this decision is made (but please
correct if wrong) - expmed.c function expand_divmod(), line 3236:

	if (abs_d != 2 && BRANCH_COST < 3)

I see why - on most "big" machines gcc is targeted for, shifts
(even by many bits) are relatively cheap compared to branches.
But on the AVR (and possibly other small targets too), shifts by
more than one bit are generally expensive, so I think it would
be good to make this condition always true on such targets.

I suggest to make this condition a macro which a target can
define in its preferred way (if not defined, use the current
condition by default).  (This is just my suggestion, please
feel free to suggest better solutions if there are any.)

Now that ashrhi3 by 15 is optimized (added yesterday), it is
much faster than it used to be (loop 15 times shifting bits one
by one...)  but still 12 -> 5 instructions looks like a big win,
as divide by 2 is quite often found in many programs.

Thanks, and keep up the good work!

Marek