Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1406706 > unrolled thread

[PATCH 08/10] m68k: Add <asm/archhash.h>

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  [PATCH 08/10] m68k: Add <asm/archhash.h> "George Spelvin" <linux@sciencehorizons.net> - 2016-05-25 09:40 +0200
    Re: [PATCH 08/10] m68k: Add <asm/archhash.h> Geert Uytterhoeven <geert@linux-m68k.org> - 2016-05-25 10:10 +0200
      Re: [PATCH 08/10] m68k: Add <asm/archhash.h> "George Spelvin" <linux@sciencehorizons.net> - 2016-05-25 10:30 +0200
      Re: [PATCH 08v2/10] m68k: Add <asm/archhash.h> "George Spelvin" <linux@sciencehorizons.net> - 2016-05-25 10:30 +0200
        Re: [PATCH 08v2/10] m68k: Add <asm/archhash.h> Geert Uytterhoeven <geert@linux-m68k.org> - 2016-05-25 10:50 +0200
    Re: [PATCH 08/10] m68k: Add <asm/archhash.h> Philippe De Muyter <phdm@macq.eu> - 2016-05-25 11:10 +0200
      Re: [PATCH 08/10] m68k: Add <asm/archhash.h> "George Spelvin" <linux@sciencehorizons.net> - 2016-05-25 11:20 +0200
        Re: [PATCH 08/10] m68k: Add <asm/archhash.h> Andreas Schwab <schwab@linux-m68k.org> - 2016-05-25 11:40 +0200
        Re: [PATCH 08/10] m68k: Add <asm/archhash.h> Philippe De Muyter <phdm@macq.eu> - 2016-05-25 12:00 +0200
    Re: [PATCH 08/10] m68k: Add <asm/archhash.h> Philippe De Muyter <phdm@macq.eu> - 2016-05-25 15:30 +0200
      Re: [PATCH 08/10] m68k: Add <asm/archhash.h> "George Spelvin" <linux@sciencehorizons.net> - 2016-05-25 15:50 +0200
    [PATCH v2 08/10] m68k: Add <asm/hash.h> "George Spelvin" <linux@horizon.com> - 2016-05-27 17:10 +0200

#1406706 — [PATCH 08/10] m68k: Add <asm/archhash.h>

This provides a multiply by constant GOLDEN_RATIO_32 = 0x61C88647
for the original mc68000, which lacks a 32x32-bit multiply instruction.

Yes, the amount of optimization effort put in is excessive. :-)

Addition chains found by Yevgen Voronenko's Hcub algorithm at
http://spiral.ece.cmu.edu/mcm/gen.html

Signed-off-by: George Spelvin <linux@sciencehorizons.net>
Cc: Geert Uytterhoeven <geert@linux-m68k.org>
Cc: Greg Ungerer <gerg@linux-m68k.org>
Cc: linux-m68k@lists.linux-m68k.org
---
 arch/m68k/Kconfig                |  1 +
 arch/m68k/include/asm/archhash.h | 67 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 68 insertions(+)
 create mode 100644 arch/m68k/include/asm/archhash.h

diff --git a/arch/m68k/Kconfig b/arch/m68k/Kconfig
index 498b567f..95197d5e 100644
--- a/arch/m68k/Kconfig
+++ b/arch/m68k/Kconfig
@@ -23,6 +23,7 @@ config M68K
 	select MODULES_USE_ELF_RELA
 	select OLD_SIGSUSPEND3
 	select OLD_SIGACTION
+	select HAVE_ARCH_HASH
 
 config RWSEM_GENERIC_SPINLOCK
 	bool
diff --git a/arch/m68k/include/asm/archhash.h b/arch/m68k/include/asm/archhash.h
new file mode 100644
index 00000000..c2bb2fc5
--- /dev/null
+++ b/arch/m68k/include/asm/archhash.h
@@ -0,0 +1,67 @@
+#ifndef _ASM_ARCHHASH_H
+#define _ASM_ARCHHASH_H
+
+/*
+ * The only 68k processors that lack MULU.L and so need this workaround
+ * are the original 68000 and 68010.
+ *
+ * Annoyingly, GCC defines __mc68000 for all processors in the family;
+ * the only way to identify an mc68000 is by the *absence* of other
+ * symbols; __mcpu32, __mcoldfire__, __mc68020, etc.
+ */
+#if ! (defined(__mc68020) || \
+	defined(__mc68030) || \
+	defined(__mc68040) || \
+	defined(__mc68060) || \
+	defined(__mcpu32)  || \
+	defined(__mcoldfire))
+
+#define HAVE_ARCH__HASH_32 1
+/*
+ * While it would be legal to substitute a different hash operation
+ * entirely, let's keep it simple and just use an optimized multiply
+ * by GOLDEN_RATIO_32 = 0x61C88647.
+ *
+ * The best way to do that appears to be to multiply by 0x8647 with
+ * shifts and adds, and use mulu.w to multiply the high half by 0x61C8.
+ *
+ * Because the 68000 has multi-cycle shifts, this addition chain is
+ * chosen to minimise the shift distances.
+ *
+ * Despite every attempt to spoon-feed GCC simple operations, GCC 6.1.1
+ * doggedly insists on doing annoying things like converting "lsl.l #2,<reg>"
+ * (12 cycles) to two adds (8+8 cycles).
+ *
+ * It also likes to notice two shifts in a row, like "a = x << 2" and
+ * "a <<= 7", and convert that to "a = x << 9".  But shifts longer than
+ * 8 bits are extra-slow on m68k, so that's a lose.
+ *
+ * Since the 68000 is a very simple in-order processor with no instruction
+ * scheduling effects on execution time, we can safely take it out of GCC's
+ * hands and write one big asm() block.
+ *
+ * Without calling overhead, this operation is 30 bytes (14 instructions
+ * plus one immediate constant) and 166 cycles.
+ */
+static inline u32 __attribute_const__ __hash_32(u32 x)
+{
+	u32 a, b;
+
+	asm(   "move.l %2,%0"	/* 0x0001 */
+	"\n	lsl.l #2,%0"	/* 0x0004 */
+	"\n	move.l %0,%1"
+	"\n	lsl.l #7,%0"	/* 0x0200 */
+	"\n	add.l %2,%0"	/* 0x0201 */
+	"\n	add.l %0,%1"	/* 0x0205 */
+	"\n	add.l %0,%0"	/* 0x0402 */
+	"\n	add.l %0,%1"	/* 0x0607 */
+	"\n	lsl.l #5,%0"	/* 0x8040 */
+				/* 0x8647 */
+	: "=&d" (a), "=&r" (b)
+	: "g" (x));
+
+	return ((u16)(x*0x61c8) << 16) + a + b;
+}
+#endif	/* HAVE_ARCH__HASH_32 */
+
+#endif	/* _ASM_ARCHHASH_H */
-- 
2.8.1

[toc] | [next] | [standalone]

#1406717

Hi George,

On Wed, May 25, 2016 at 9:34 AM, George Spelvin
<linux@sciencehorizons.net> wrote:
> This provides a multiply by constant GOLDEN_RATIO_32 = 0x61C88647
> for the original mc68000, which lacks a 32x32-bit multiply instruction.
>
> Yes, the amount of optimization effort put in is excessive. :-)
>
> Addition chains found by Yevgen Voronenko's Hcub algorithm at
> http://spiral.ece.cmu.edu/mcm/gen.html
>
> Signed-off-by: George Spelvin <linux@sciencehorizons.net>
> Cc: Geert Uytterhoeven <geert@linux-m68k.org>
> Cc: Greg Ungerer <gerg@linux-m68k.org>
> Cc: linux-m68k@lists.linux-m68k.org
> ---
>  arch/m68k/Kconfig                |  1 +
>  arch/m68k/include/asm/archhash.h | 67 ++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 68 insertions(+)
>  create mode 100644 arch/m68k/include/asm/archhash.h
>
> diff --git a/arch/m68k/Kconfig b/arch/m68k/Kconfig
> index 498b567f..95197d5e 100644
> --- a/arch/m68k/Kconfig
> +++ b/arch/m68k/Kconfig
> @@ -23,6 +23,7 @@ config M68K
>         select MODULES_USE_ELF_RELA
>         select OLD_SIGSUSPEND3
>         select OLD_SIGACTION
> +       select HAVE_ARCH_HASH

"select HAVE_ARCH_HASH if M68000"?

Or better, move the select to the M68000 section in arch/m68k/Kconfig.cpu.

> --- /dev/null
> +++ b/arch/m68k/include/asm/archhash.h
> @@ -0,0 +1,67 @@
> +#ifndef _ASM_ARCHHASH_H
> +#define _ASM_ARCHHASH_H
> +
> +/*
> + * The only 68k processors that lack MULU.L and so need this workaround
> + * are the original 68000 and 68010.
> + *
> + * Annoyingly, GCC defines __mc68000 for all processors in the family;
> + * the only way to identify an mc68000 is by the *absence* of other
> + * symbols; __mcpu32, __mcoldfire__, __mc68020, etc.
> + */
> +#if ! (defined(__mc68020) || \
> +       defined(__mc68030) || \
> +       defined(__mc68040) || \
> +       defined(__mc68060) || \
> +       defined(__mcpu32)  || \
> +       defined(__mcoldfire))

With my comment above, you wouldn't need this, but I'm gonna comment anyway.

We don't use special GCCs to target specific CPU variants. Hence inside the
kernel, you should check the config symbols, to see if support for 68000 or
68010 (which isn't supported by the kernel yet) is enabled.

Hence the check should be:

    #if defined(CONFIG_M68000) || defined(CONFIG_M68010)

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

[toc] | [prev] | [next] | [standalone]

#1406735

> With my comment above, you wouldn't need this, but I'm gonna comment anyway.
> 
> We don't use special GCCs to target specific CPU variants. Hence inside the
> kernel, you should check the config symbols, to see if support for 68000 or
> 68010 (which isn't supported by the kernel yet) is enabled.

Do you remember some earlier discussion about the m68k Makefile and old
GCC versions?  In particular, lines like:

cpuflags-$(CONFIG_M525x)        := $(call cc-option,-mcpu=5253,-m5200)
cpuflags-$(CONFIG_M5249)        := $(call cc-option,-mcpu=5249,-m5200)
cpuflags-$(CONFIG_M520x)        := $(call cc-option,-mcpu=5208,-m5200)
cpuflags-$(CONFIG_M5206e)       := $(call cc-option,-mcpu=5206e,-m5200)
cpuflags-$(CONFIG_M5206)        := $(call cc-option,-mcpu=5206,-m5200)

The problem is that whether MULU.L exists depends on the targeted
architecture, and *that* depends on this Makefile trickery, not
just CONFIG symbols...

Oh, f*** me.


I misremembered.  That problem exists, but only for DIVU.L.  As I said in
the comments (which I wrote *after* deciding I needed this approach), all
ColdFire have MULU.L.  It's DIVU.L that's missing from some early ones.

You're absolutely right.  MULU.L support can be done perfectly from
CONFIG_ options.


Improved patch coming in a few minutes.  My sincere apologies.

[toc] | [prev] | [next] | [standalone]

#1406741 — Re: [PATCH 08v2/10] m68k: Add <asm/archhash.h>

This provides a multiply by constant GOLDEN_RATIO_32 = 0x61C88647
for the original mc68000, which lacks a 32x32-bit multiply instruction.

Yes, the amount of optimization effort put in is excessive. :-)

Addition chains found by Yevgen Voronenko's Hcub algorithm at
http://spiral.ece.cmu.edu/mcm/gen.html

Signed-off-by: George Spelvin <linux@sciencehorizons.net>
Cc: Geert Uytterhoeven <geert@linux-m68k.org>
Cc: Greg Ungerer <gerg@linux-m68k.org>
Cc: linux-m68k@lists.linux-m68k.org
---
 arch/m68k/Kconfig.cpu            |  1 +
 arch/m68k/include/asm/archhash.h | 58 ++++++++++++++++++++++++++++++++++++++++
 2 files changed, 59 insertions(+)
 create mode 100644 arch/m68k/include/asm/archhash.h

diff --git a/arch/m68k/Kconfig.cpu b/arch/m68k/Kconfig.cpu
index 0dfcf128..bf3de464 100644
--- a/arch/m68k/Kconfig.cpu
+++ b/arch/m68k/Kconfig.cpu
@@ -40,6 +40,7 @@ config M68000
 	select CPU_HAS_NO_MULDIV64
 	select CPU_HAS_NO_UNALIGNED
 	select GENERIC_CSUM
+	select HAVE_ARCH_HASH
 	help
 	  The Freescale (was Motorola) 68000 CPU is the first generation of
 	  the well known M68K family of processors. The CPU core as well as
diff --git a/arch/m68k/include/asm/archhash.h b/arch/m68k/include/asm/archhash.h
new file mode 100644
index 00000000..2532cf92
--- /dev/null
+++ b/arch/m68k/include/asm/archhash.h
@@ -0,0 +1,58 @@
+#ifndef _ASM_ARCHHASH_H
+#define _ASM_ARCHHASH_H
+
+/*
+ * The only 68k processors that lack MULU.L and so need this workaround
+ * are the original 68000 and 68010.
+ */
+#if defined(CONFIG_M68000) || defined(CONFIG_M68010)
+
+#define HAVE_ARCH__HASH_32 1
+/*
+ * While it would be legal to substitute a different hash operation
+ * entirely, let's keep it simple and just use an optimized multiply
+ * by GOLDEN_RATIO_32 = 0x61C88647.
+ *
+ * The best way to do that appears to be to multiply by 0x8647 with
+ * shifts and adds, and use mulu.w to multiply the high half by 0x61C8.
+ *
+ * Because the 68000 has multi-cycle shifts, this addition chain is
+ * chosen to minimise the shift distances.
+ *
+ * Despite every attempt to spoon-feed GCC simple operations, GCC 6.1.1
+ * doggedly insists on doing annoying things like converting "lsl.l #2,<reg>"
+ * (12 cycles) to two adds (8+8 cycles).
+ *
+ * It also likes to notice two shifts in a row, like "a = x << 2" and
+ * "a <<= 7", and convert that to "a = x << 9".  But shifts longer than
+ * 8 bits are extra-slow on m68k, so that's a lose.
+ *
+ * Since the 68000 is a very simple in-order processor with no instruction
+ * scheduling effects on execution time, we can safely take it out of GCC's
+ * hands and write one big asm() block.
+ *
+ * Without calling overhead, this operation is 30 bytes (14 instructions
+ * plus one immediate constant) and 166 cycles.
+ */
+static inline u32 __attribute_const__ __hash_32(u32 x)
+{
+	u32 a, b;
+
+	asm(   "move.l %2,%0"	/* 0x0001 */
+	"\n	lsl.l #2,%0"	/* 0x0004 */
+	"\n	move.l %0,%1"
+	"\n	lsl.l #7,%0"	/* 0x0200 */
+	"\n	add.l %2,%0"	/* 0x0201 */
+	"\n	add.l %0,%1"	/* 0x0205 */
+	"\n	add.l %0,%0"	/* 0x0402 */
+	"\n	add.l %0,%1"	/* 0x0607 */
+	"\n	lsl.l #5,%0"	/* 0x8040 */
+				/* 0x8647 */
+	: "=&d" (a), "=&r" (b)
+	: "g" (x));
+
+	return ((u16)(x*0x61c8) << 16) + a + b;
+}
+#endif	/* HAVE_ARCH__HASH_32 */
+
+#endif	/* _ASM_ARCHHASH_H */
-- 
2.8.1

[toc] | [prev] | [next] | [standalone]

#1406748 — Re: [PATCH 08v2/10] m68k: Add <asm/archhash.h>

On Wed, May 25, 2016 at 10:24 AM, George Spelvin
<linux@sciencehorizons.net> wrote:
> --- a/arch/m68k/Kconfig.cpu
> +++ b/arch/m68k/Kconfig.cpu
> @@ -40,6 +40,7 @@ config M68000
>         select CPU_HAS_NO_MULDIV64
>         select CPU_HAS_NO_UNALIGNED
>         select GENERIC_CSUM
> +       select HAVE_ARCH_HASH
>         help
>           The Freescale (was Motorola) 68000 CPU is the first generation of
>           the well known M68K family of processors. The CPU core as well as
> diff --git a/arch/m68k/include/asm/archhash.h b/arch/m68k/include/asm/archhash.h
> new file mode 100644
> index 00000000..2532cf92
> --- /dev/null
> +++ b/arch/m68k/include/asm/archhash.h
> @@ -0,0 +1,58 @@
> +#ifndef _ASM_ARCHHASH_H
> +#define _ASM_ARCHHASH_H
> +
> +/*
> + * The only 68k processors that lack MULU.L and so need this workaround
> + * are the original 68000 and 68010.
> + */
> +#if defined(CONFIG_M68000) || defined(CONFIG_M68010)

As I said before, I don't think you need this check, given HAVE_ARCH_HASH is
selected by M68000, and M68010 doesn't exist.

Gr{oetje,eeting}s,

                        Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@linux-m68k.org

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds

[toc] | [prev] | [next] | [standalone]

#1406762

On Wed, May 25, 2016 at 03:34:55AM -0400, George Spelvin wrote:
> +static inline u32 __attribute_const__ __hash_32(u32 x)
> +{
> +	u32 a, b;
> +
> +	asm(   "move.l %2,%0"	/* 0x0001 */
> +	"\n	lsl.l #2,%0"	/* 0x0004 */
> +	"\n	move.l %0,%1"
> +	"\n	lsl.l #7,%0"	/* 0x0200 */
> +	"\n	add.l %2,%0"	/* 0x0201 */
> +	"\n	add.l %0,%1"	/* 0x0205 */
> +	"\n	add.l %0,%0"	/* 0x0402 */
> +	"\n	add.l %0,%1"	/* 0x0607 */
> +	"\n	lsl.l #5,%0"	/* 0x8040 */
> +				/* 0x8647 */

There is no standard way to write asm in the kernel, but I prefer
a simple semicolon after each insn

	asm("move.l	%2,%0;"	/* 0x0001 */
	    "lsl.l	#2,%0;"	/* 0x0004 */
	    "move.l	%0,%1;"
	    "lsl.l	#7,%0;"	/* 0x0200 */
	    "add.l	%2,%0;"	/* 0x0201 */
	    "add.l	%0,%1;"	/* 0x0205 */
	    "add.l	%0,%0;"	/* 0x0402 */
	    "add.l	%0,%1;"	/* 0x0607 */
	    "lsl.l	#5,%0"	/* 0x8040 */
				/* 0x8647 */

Also, it took me some time to understand the hexadecimal constants
in the comments (and the last one predicts a future event :)).

> +	: "=&d" (a), "=&r" (b)
> +	: "g" (x));
> +
> +	return ((u16)(x*0x61c8) << 16) + a + b;
> +}

Just my two cents

Philippe

[toc] | [prev] | [next] | [standalone]

#1406765

> On Wed, May 25, 2016 at 03:34:55AM -0400, George Spelvin wrote:
>> +static inline u32 __attribute_const__ __hash_32(u32 x)
>> +{
>> +	u32 a, b;
>> +
>> +	asm(   "move.l %2,%0"	/* 0x0001 */
>> +	"\n	lsl.l #2,%0"	/* 0x0004 */
>> +	"\n	move.l %0,%1"
>> +	"\n	lsl.l #7,%0"	/* 0x0200 */
>> +	"\n	add.l %2,%0"	/* 0x0201 */
>> +	"\n	add.l %0,%1"	/* 0x0205 */
>> +	"\n	add.l %0,%0"	/* 0x0402 */
>> +	"\n	add.l %0,%1"	/* 0x0607 */
>> +	"\n	lsl.l #5,%0"	/* 0x8040 */
>> +				/* 0x8647 */

> There is no standard way to write asm in the kernel, but I prefer
> a simple semicolon after each insn

I did it the way I did above because it makes the gcc -S output very
legible.  Just like I put a space before the perands on m68k but a tab
on h8300: that's what GCC does on those platforms.

I started with the "\n\t" suffixes on each line like so much other
kernel code, but then figured out the format above which is legible
both in C source and compiler output.

>>	asm("move.l	%2,%0;"	/* 0x0001 */
>>	    "lsl.l	#2,%0;"	/* 0x0004 */
>>	    "move.l	%0,%1;"
>>	    "lsl.l	#7,%0;"	/* 0x0200 */
>>	    "add.l	%2,%0;"	/* 0x0201 */
>>	    "add.l	%0,%1;"	/* 0x0205 */
>>	    "add.l	%0,%0;"	/* 0x0402 */
>>	    "add.l	%0,%1;"	/* 0x0607 */
>>	    "lsl.l	#5,%0"	/* 0x8040 */
>>				/* 0x8647 */

> Also, it took me some time to understand the hexadecimal constants
> in the comments (and the last one predicts a future event :)).


Can you recmmend a better way to comment this?  My nose is so deep
in the code it's hard for me to judge.

> Just my two cents

And thank you very much for them!

[toc] | [prev] | [next] | [standalone]

#1406773

"George Spelvin" <linux@sciencehorizons.net> writes:

> Can you recmmend a better way to comment this?  My nose is so deep
> in the code it's hard for me to judge.

It's probably best to express the effect of the insns in plain C.

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

[toc] | [prev] | [next] | [standalone]

#1406800

On Wed, May 25, 2016 at 05:14:35AM -0400, George Spelvin wrote:
> 
> I did it the way I did above because it makes the gcc -S output very
> legible.  Just like I put a space before the perands on m68k but a tab
> on h8300: that's what GCC does on those platforms.
> 
> I started with the "\n\t" suffixes on each line like so much other
> kernel code, but then figured out the format above which is legible
> both in C source and compiler output.

OK thanks.

> 
> >>	asm("move.l	%2,%0;"	/* 0x0001 */
> >>	    "lsl.l	#2,%0;"	/* 0x0004 */
> >>	    "move.l	%0,%1;"
> >>	    "lsl.l	#7,%0;"	/* 0x0200 */
> >>	    "add.l	%2,%0;"	/* 0x0201 */
> >>	    "add.l	%0,%1;"	/* 0x0205 */
> >>	    "add.l	%0,%0;"	/* 0x0402 */
> >>	    "add.l	%0,%1;"	/* 0x0607 */
> >>	    "lsl.l	#5,%0"	/* 0x8040 */
> >>				/* 0x8647 */
> 
> > Also, it took me some time to understand the hexadecimal constants
> > in the comments (and the last one predicts a future event :)).
> 
> 
> Can you recmmend a better way to comment this?  My nose is so deep
> in the code it's hard for me to judge.

I second Andreas' suggestion.

Philippe
-- 
Philippe De Muyter +32 2 6101532 Macq SA rue de l'Aeronef 2 B-1140 Bruxelles

[toc] | [prev] | [next] | [standalone]

#1406897

On Wed, May 25, 2016 at 03:34:55AM -0400, George Spelvin wrote:
> This provides a multiply by constant GOLDEN_RATIO_32 = 0x61C88647
> for the original mc68000, which lacks a 32x32-bit multiply instruction.
> 
> Addition chains found by Yevgen Voronenko's Hcub algorithm at
> http://spiral.ece.cmu.edu/mcm/gen.html

Shouldn't you put that reference in the comments of your archhash.h file ?

Philippe

[toc] | [prev] | [next] | [standalone]

#1406911

Philippe De Muyter wrote:
> On Wed, May 25, 2016 at 03:34:55AM -0400, George Spelvin wrote:
>> Addition chains found by Yevgen Voronenko's Hcub algorithm at
>> http://spiral.ece.cmu.edu/mcm/gen.html

> Shouldn't you put that reference in the comments of your archhash.h file ?

I don't really care either way, but generally comments show what the
code does and commit messages talk about how it was created and by whom.
That references seemed to fall into the latter category.

Rationales (*why* it does what it does) can go in both places, with the
commit message providing more room.


I have a revised set of arch/ patches including all of the suggestions
made so far, currently awaiting the requested self-test.

(I found a clean way to do it using the *value* of the HAVE_FOO define
to indicate whether the function is meant to be equivalent to the
generic one.  If it's 1, the self-test will compare the arch-specific
and generic implementations.)

[toc] | [prev] | [next] | [standalone]

#1408126 — [PATCH v2 08/10] m68k: Add <asm/hash.h>

This provides a multiply by constant GOLDEN_RATIO_32 = 0x61C88647
for the original mc68000, which lacks a 32x32-bit multiply instruction.

Yes, the amount of optimization effort put in is excessive. :-)

Shift-add chain found by Yevgen Voronenko's Hcub algorithm at
http://spiral.ece.cmu.edu/mcm/gen.html

Signed-off-by: George Spelvin <linux@sciencehorizons.net>
Cc: Geert Uytterhoeven <geert@linux-m68k.org>
Cc: Greg Ungerer <gerg@linux-m68k.org>
Cc: Andreas Schwab <schwab@linux-m68k.org>
Cc: Philippe De Muyter <phdm@macq.eu>
Cc: linux-m68k@lists.linux-m68k.org
---
 arch/m68k/Kconfig.cpu        |  1 +
 arch/m68k/include/asm/hash.h | 59 ++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 60 insertions(+)
 create mode 100644 arch/m68k/include/asm/hash.h

diff --git a/arch/m68k/Kconfig.cpu b/arch/m68k/Kconfig.cpu
index 0dfcf128..bf3de464 100644
--- a/arch/m68k/Kconfig.cpu
+++ b/arch/m68k/Kconfig.cpu
@@ -40,6 +40,7 @@ config M68000
 	select CPU_HAS_NO_MULDIV64
 	select CPU_HAS_NO_UNALIGNED
 	select GENERIC_CSUM
+	select HAVE_ARCH_HASH
 	help
 	  The Freescale (was Motorola) 68000 CPU is the first generation of
 	  the well known M68K family of processors. The CPU core as well as
diff --git a/arch/m68k/include/asm/hash.h b/arch/m68k/include/asm/hash.h
new file mode 100644
index 00000000..6407af84
--- /dev/null
+++ b/arch/m68k/include/asm/hash.h
@@ -0,0 +1,59 @@
+#ifndef _ASM_HASH_H
+#define _ASM_HASH_H
+
+/*
+ * If CONFIG_M68000=y (original mc68000/010), this file is #included
+ * to work around the lack of a MULU.L instruction.
+ */
+
+#define HAVE_ARCH__HASH_32 1
+/*
+ * While it would be legal to substitute a different hash operation
+ * entirely, let's keep it simple and just use an optimized multiply
+ * by GOLDEN_RATIO_32 = 0x61C88647.
+ *
+ * The best way to do that appears to be to multiply by 0x8647 with
+ * shifts and adds, and use mulu.w to multiply the high half by 0x61C8.
+ *
+ * Because the 68000 has multi-cycle shifts, this addition chain is
+ * chosen to minimise the shift distances.
+ *
+ * Despite every attempt to spoon-feed it simple operations, GCC
+ * 6.1.1 doggedly insists on doing annoying things like converting
+ * "lsl.l #2,<reg>" (12 cycles) to two adds (8+8 cycles).
+ *
+ * It also likes to notice two shifts in a row, like "a = x << 2" and
+ * "a <<= 7", and convert that to "a = x << 9".  But shifts longer
+ * than 8 bits are extra-slow on m68k, so that's a lose.
+ *
+ * Since the 68000 is a very simple in-order processor with no
+ * instruction scheduling effects on execution time, we can safely
+ * take it out of GCC's hands and write one big asm() block.
+ *
+ * Without calling overhead, this operation is 30 bytes (14 instructions
+ * plus one immediate constant) and 166 cycles.
+ *
+ * (Because %2 is fetched twice, it can't be postincrement, and thus it
+ * can't be a fully general "g" or "m".  Register is preferred, but
+ * offsettable memory or immediate will work.)
+ */
+static inline u32 __attribute_const__ __hash_32(u32 x)
+{
+	u32 a, b;
+
+	asm(   "move.l %2,%0"	/* a = x * 0x0001 */
+	"\n	lsl.l #2,%0"	/* a = x * 0x0004 */
+	"\n	move.l %0,%1"
+	"\n	lsl.l #7,%0"	/* a = x * 0x0200 */
+	"\n	add.l %2,%0"	/* a = x * 0x0201 */
+	"\n	add.l %0,%1"	/* b = x * 0x0205 */
+	"\n	add.l %0,%0"	/* a = x * 0x0402 */
+	"\n	add.l %0,%1"	/* b = x * 0x0607 */
+	"\n	lsl.l #5,%0"	/* a = x * 0x8040 */
+	: "=&d,d" (a), "=&r,r" (b)
+	: "r,roi?" (x));	/* a+b = x*0x8647 */
+
+	return ((u16)(x*0x61c8) << 16) + a + b;
+}
+
+#endif	/* _ASM_HASH_H */
-- 
2.8.1

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web