RE: Mined out of comp.std.c...

RE: Mined out of comp.std.c...

[Rupert Wood]

> OK, last thought on the matter before I go slit my wrists in 
> shame.

Except that didn't work. I think I'll give up and go home - I can't seem
to manage to redeem myself.

Problem is I put 'setnc' as a quick hack and didn't notice it broke my
non-overflow testcase. What I really needed was 'set carry xor overflow'
but there's no primitive for that and I can't construct something out of
set[n]o and sbb or adc.

Re: Mined out of comp.std.c...

[Peter Barada]

>> OK, last thought on the matter before I go slit my wrists in 
>> shame.
>
>Except that didn't work. I think I'll give up and go home - I can't seem
>to manage to redeem myself.
>
>Problem is I put 'setnc' as a quick hack and didn't notice it broke my
>non-overflow testcase. What I really needed was 'set carry xor overflow'
>but there's no primitive for that and I can't construct something out of
>set[n]o and sbb or adc.

Go grab superopt-2.5.tar.gz from the gnu tree, config it for intel
and run it to search for a sequence that evaluates 'maxs':

[pbarada: ~/src/superopt-2.5] > ./superopt -fmaxs -max-cost 5
Searching for { r = (signed_word) v0 > (signed_word) v1 ? v0 : v1; }
Superoptimizing at cost 1 2 3 4 5 failure.


Which indicates that the superoptimizer can not find a 5 instruction
sequence to do this.  Obviously if you crank up max-costs a bit and
let it run over the weekend it *might* find a sequence worth
investigating.  If your max function is *unsigned*, superopt finds a
batch of matches quite quickly:

[pbarada: ~/src/superopt-2.5] > ./superopt -fmaxu -max-cost 5
Searching for { r = (unsigned_word) v0 > (unsigned_word) v1 ? v0 : v1; }
Superoptimizing at cost 1 2 3 4 5
1:	r1:=sub_co(r1,r0)
	r0:=add_co(r0,r1)
	r2:=sub_cio(r2,r2)
	r2:=and_rc(r2,r1)
	r0:=sub_co(r0,r2)
2:	r1:=sub_co(r1,r0)
	r0:=add_co(r0,r1)
	r2:=sub_cio(r2,r2)
	r1:=and_rc(r1,r2)
	r0:=sub_co(r0,r1)
...


Have Fun!

-- 
Peter Barada                                   Peter.Barada@motorola.com
Wizard                                         781-852-2768 (direct)
WaveMark Solutions(wholly owned by Motorola)   781-270-0193 (fax)

RE: Mined out of comp.std.c...

[Rupert Wood]

OK, last thought on the matter before I go slit my wrists in shame. How
about the following: Alan's fixed version in six x86 instructions
hopefully overflow proof.

    xorl    %edx, %edx
    subl    %ecx, %eax
    setnc   %dl
    dec     %edx
    andl    %edx, %eax
    addl    %ecx, %eax

This is 12 bytes. I've no idea how quick it'd be.

RE: Mined out of comp.std.c...

[Rupert Wood]

I wrote:

> Also, consider a == b. Then d = 0 which we 'and' by. It'll only ever
> return 0.
> 
> As far as I can see this routine is only ever likely to work for d
> negative, i.e. we know that a > b beforehand.

... which is exactly what Alan's correction was about. Sorry. I'll shut
up until I wake up.

(Tim - yes, didn't consider overflow. Been too long since I've done
anything numerical.)

Re: Mined out of comp.std.c...

[Tim Hollebeek]

On Thu, Apr 25, 2002 at 09:38:58AM +0100, Rupert Wood wrote:
> Zack Weinberg wrote:
> 
> > static int int_max (int a, int b) {
> >     int d = (b - a);
> >     return (b - d) & (d >> (CHAR_BIT*sizeof(int) - 1));
> > }
> 
> Maybe I need more coffee, but isn't (b-d) == a?

Consider overflow.

-Tim

RE: Mined out of comp.std.c...

[Rupert Wood]

Nathan Sidwell wrote:

> this optimization is relying on sign (b - a) indicating the
> truthfulness of a > b. That is not correct, as b - a might overflow.

Also, consider a == b. Then d = 0 which we 'and' by. It'll only ever
return 0.

As far as I can see this routine is only ever likely to work for d
negative, i.e. we know that a > b beforehand.

Re: Mined out of comp.std.c...

[Nathan Sidwell]

Richard Henderson wrote:
> 
> On Wed, Apr 24, 2002 at 11:51:17PM -0700, Zack Weinberg wrote:
> > More interesting to me is the observation that - since we know the
> > arithmetic properties of the target - we could transform
> > ((a > b) ? a : b) into the above, if it were a win.  What I'm
> > wondering is if it is.

this optimization is relying on sign (b - a) indicating the truthfulness
of a > b. That is not correct, as b - a might overflow. For instance
a = 7fffffff (most pos), b=80000000 (most neg).
a is most definitely > b, but b - a will be 1 (or some overflow trap)

nathan

-- 
Dr Nathan Sidwell :: Computer Science Department :: Bristol University
           The voices in my head told me to say this
nathan@acm.org  http://www.cs.bris.ac.uk/~nathan/  nathan@cs.bris.ac.uk

RE: Mined out of comp.std.c...

[Rupert Wood]

Zack Weinberg wrote:

> static int int_max (int a, int b) {
>     int d = (b - a);
>     return (b - d) & (d >> (CHAR_BIT*sizeof(int) - 1));
> }

Maybe I need more coffee, but isn't (b-d) == a?

>    8:   89 c2                   mov    %eax,%edx
>    a:   29 ca                   sub    %ecx,%edx
>    c:   29 d0                   sub    %edx,%eax
>    e:   c1 fa 1f                sar    $0x1f,%edx
>   11:   21 d0                   and    %edx,%eax

so rather

        subl    %eax, %ecx
        sarl    $31, %ecx
        andl    %ecx, %eax

Rup.

Re: Mined out of comp.std.c...

[Richard Henderson]

On Wed, Apr 24, 2002 at 11:51:17PM -0700, Zack Weinberg wrote:
> More interesting to me is the observation that - since we know the
> arithmetic properties of the target - we could transform 
> ((a > b) ? a : b) into the above, if it were a win.  What I'm
> wondering is if it is.

It is almost certainly on all 3-address isa's that don't implement
conditional move (sparc, mips3, ppc).  Because it's 4 insns for
the sub+sub+shift+and, and 3 for cmp+jmp+move.


r~

Re: Mined out of comp.std.c...

[Alan Modra]

On Wed, Apr 24, 2002 at 11:51:17PM -0700, Zack Weinberg wrote:
> ... an interesting microoptimization.
> 
> The original post on comp.std.c is about whether
> 
> static int int_max (int a, int b) {
>     int d = (b - a);
>     return (b - d) & (d >> (CHAR_BIT*sizeof(int) - 1));
> }

This might work better :)

static int int_max (int a, int b) {
    int d = (b - a);
    return b - (d & (d >> (CHAR_BIT*sizeof(int) - 1)));
}

-- 
Alan Modra
IBM OzLabs - Linux Technology Centre

Mined out of comp.std.c...

[Zack Weinberg]

... an interesting microoptimization.

The original post on comp.std.c is about whether

static int int_max (int a, int b) {
    int d = (b - a);
    return (b - d) & (d >> (CHAR_BIT*sizeof(int) - 1));
}

is or is not portable within the standard.  If you have twos-
complement arithmetic and >> does arithmetic right shift, it's
equivalent to the usual ((a > b) ? a : b).

More interesting to me is the observation that - since we know the
arithmetic properties of the target - we could transform 
((a > b) ? a : b) into the above, if it were a win.  What I'm
wondering is if it is.  On an i386, it's definitely not a space win:

   8:   89 c2                   mov    %eax,%edx
   a:   29 ca                   sub    %ecx,%edx
   c:   29 d0                   sub    %edx,%eax
   e:   c1 fa 1f                sar    $0x1f,%edx
  11:   21 d0                   and    %edx,%eax

vs.

  28:   39 d0                   cmp    %ecx,%eax
  2a:   7d 02                   jge    2e <int_max_2+0xe>
  2c:   89 d0                   mov    %ecx,%eax

or

  28:   39 c2                   cmp    %eax,%ecx
  2a:   0f 4d c2                cmovge %ecx,%eax

(input parameters in eax, ecx in all three cases).  It's unlikely that
the clever bit shifts are faster than the conditional move, especially
in real life where we would be able to schedule other ops between the
cmp and the cmovge.  However, shifts might well be faster than jumps.
Anyone know for sure?

zw