RE: [PATCH v2] kbuild: treat char as always unsigned

David Laight
2022-12-30T11:39:46Z

From: Holger Lubitz
> Sent: 24 December 2022 09:34
>
> On Thu, 2022-12-22 at 10:41 +0000, David Laight wrote:
> > I wonder how much slower it is - m68k is likely to be microcoded
> > and I don't think instruction timings are actually available.
>
> Not sure if these are in any way official, but
> http://oldwww.nvg.ntnu.no/amiga/MC680x0_Sections/mc68030timing.HTML

I thought about that some more and remember seeing memory timings
on a logic analyser - and getting timings that (more or less)
implied sequential execution limited by the obvious memory (cache)
accesses.

The microcoding is more apparent in the large mid-instruction
interrupt stack frames - eg for page faults.

>
> (There's also
> http://oldwww.nvg.ntnu.no/amiga/MC680x0_Sections/mc68000timing.HTML
> but that is probably only interesting to demo coders by now)
>
> > The fastest version probably uses subx (with carry) to generate
> > 0/-1 and leaves +delta for the other result - but getting the
> > compares and branches in the right order is hard.
>
> Guess it must have been over 20 years since I wrote any 68k asm, but
> now I actually ended up installing Debian on qemu to experiment.
>
> There are two interesting differences between 68k and x86 that can be
> useful here: Unlike x86, MOV on 68k sets the flags. And also, subx
> differs from sbb in that it resets the zero flag on a non-zero result,
> but does not set it on a zero result. So if it is set, it must have
> been set before.
>
> Here are the two functions I came up with (tested only stand-alone, not
> in a kernel build. Also no benchmarks because this 68040 is only
> emulated)
> #1 (optimized for minimum instruction count in loop,
> 68k + Coldfire ISA_B)
>
> int strcmp1(const char *cs, const char *ct)
> {
> int res;
>
> asm ("\n"
> "1: move.b (%0)+,%2\n" /* get *cs */
> " jeq 2f\n" /* end of first string? */
> " cmp.b (%1)+,%2\n" /* compare *ct */
> " jeq 1b\n" /* if equal, continue */
> " jra 3f\n" /* else skip to tail */
> "2: cmp.b (%1)+,%2\n" /* compare one last byte */
> "3: subx.l %2, %2\n" /* -1 if borrow, 0 if not */
> " jls 4f\n" /* if set, z is from sub.b */

The subx will set Z unless C was set.
So that doesn't seem right.

> " moveq.l #1, %2\n" /* 1 if !borrow */
> "4:"
> : "+a" (cs), "+a" (ct), "=d" (res));
> return res;
> }

I think this should work:
(But the jc might need to be jnc.)

" moveq.l #0,%2\n" /* zero high bits of result */
"1: move.b (%1)+,%2\n" /* get *ct */
" jeq 2f\n" /* end of second string? */
" cmp.b (%0)+,%2\n" /* compare *cs */
" jeq 1b\n" /* if equal, continue */
" jc 4f /* return +ve */
" moveq.l #-1, %2\n" /* return -ve */
" jra 4f\n"
"2: move.b (%0),%2\n" /* check for matching strings */
"4:"

> #2 (optimized for minimum code size,
> Coldfire ISA_A compatible)
>
> int strcmp2(const char *cs, const char *ct)
> {
> int res = 0, tmp = 0;
>
> asm ("\n"
> "1: move.b (%0)+,%2\n" /* get *cs */
> " move.b (%1)+,%3\n" /* get *ct */
> " subx.l %3,%2\n" /* compare a byte */
> " jeq 2f\n" /* both inputs were zero */

That doesn't seem right.
Z will be set if either *ct is zero or the bytes match.

> " tst.l %2\n" /* check result */

This only sets Z when it was already set by the subx.

> " jeq 1b\n" /* if zero, continue */
> "2:"
> : "+a" (cs), "+a" (ct), "+d" (res), "+d" (tmp));
> return res;
> }
>
> However, this one needs res and tmp to be set to zero, because we read
> only bytes (no automatic zero-extend on 68k), but then do a long
> operation on them. Coldfire ISA_A dropped cmpb, it only reappeared in
> ISA_B.
>
> So the real instruction count is likely to be two more, unless gcc
> happens to have one or two zeros it can reuse.
>
> > I believe some of the other m68k asm functions are also missing
> > the "memory" 'clobber' and so could get mis-optimised.
>
> In which case would that happen? This function doesn't clobber memory
> and its result does get used. If gcc mistakenly thinks the parameters
> haven't changed and uses a previously cached result, wouldn't that
> apply to a C function too?

You need a memory 'clobber' on anything that READS memory as well
as writes it.

> > While I can write (or rather have written) m68k asm I don't have
> > a compiler.
>
> Well, I now have an emulated Quadra 800 running Debian 68k.(Getting the
> emulated networking to work reliably was a bit problematic, though. But
> now it runs Kernel 6.0) qemu could emulate Coldfire too, but I am not
> sure where I would find a distribution for that.
>
> I did not attach a patch because it seems already to be decided that
> the function is gone. But should anyone still want to include one (or
> both) of these functions, just give credit to me and I'm fine.

Thinking further the fastest strcmp() probably uses big-endian word compares
with a check for a zero byte.
Especially on 64 bit systems that support misaligned loads.
But I'd need to think hard about the actual details.

David

-
Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1PT, UK
Registration No: 1397386 (Wales)