[PATCH 12/20] alpha: finish the ev6 memcpy and memmove tails without a byte loop

[Matt Turner]

Once the quadword loop runs out there are 1 to 7 bytes left, and they were
copied one at a time by a loop costing about eight issue slots a byte.  For
copies whose length is not a multiple of eight that dominates: on an EV68CB
a 15-byte copy cost 40.7 cycles against 22.1 for a 16-byte one, so asking
for one byte less than a whole number of quadwords made the call 85% dearer.

Every path into $tail_quads leaves the source and destination both 0mod8,
and the quadword loop preserves it, so the remainder can be done as at most
one longword, one word and one byte with no unaligned access -- 0mod8 is
0mod4, and after the longword 4mod8 is still 2-aligned.  That replaces up
to seven loop trips with three tests and at most three load/store pairs.

Measured on an EV68CB, hot, cycles per call:

  size    before   after
  15        40.7    21.1   1.93x
  23        41.9    24.1   1.74x
  31        47.3    28.8   1.64x
  7         34.7    25.6   1.36x
  63        54.4    40.2   1.35x
  95        57.3    42.3   1.36x
  127       82.5    64.9   1.27x

The counters confirm this is simply instruction count: at 15 bytes the call
retires 69.2 instructions before and 43.1 after, at an IPC just over two
with no Bcache misses and no replay traps.  Short copies are issue-bound,
unlike the long ones this file spends most of its comments on.

Lengths leaving exactly one trailing byte pay about 1.5 cycles -- two extra
instructions -- because the three tests cost more than a single trip of the
old loop.  A length of 9 goes from 18.3 to 19.8 cycles.  That is the whole
downside and it is worth it for a factor approaching two elsewhere.

This is deliberately not memset's trailing masked store, which reads and
rewrites the destination quadword: that touches bytes past the end of the
destination, and memcpy has never written memory the caller did not ask for.

Verified on an EV68CB against the C memcpy and memmove for every length from
0 to 600 at 72 destination alignments, and for memmove across source-
destination gaps from 8 bytes to 1KB, with 512-byte guard regions checked
for stray writes.
---
 sysdeps/alpha/alphaev6/memcpy.S  | 45 +++++++++++++++++++++++++++-----
 sysdeps/alpha/alphaev6/memmove.S | 44 ++++++++++++++++++++++++++-----
 2 files changed, 76 insertions(+), 13 deletions(-)

diff --git ./sysdeps/alpha/alphaev6/memcpy.S ./sysdeps/alpha/alphaev6/memcpy.S
index d11138420d..ee251e8b8f 100644
--- ./sysdeps/alpha/alphaev6/memcpy.S
+++ ./sysdeps/alpha/alphaev6/memcpy.S
@@ -274,16 +274,47 @@ $less_than_8:
 	nop				# E :
 	nop				# E :
 
-	/* Trailing bytes */
+	/*
+	 * 1..7 trailing bytes, with source and destination both 0mod8 -- every
+	 * path into $tail_quads guarantees that, and the quad loop above keeps
+	 * it.  Do them as at most one longword, one word and one byte rather
+	 * than looping a byte at a time: the loop spends about eight issue
+	 * slots per byte, which on an EV68CB made a 15-byte copy 85% dearer
+	 * than a 16-byte one.  Each step leaves the pointers aligned for the
+	 * next -- 0mod8 is 0mod4, and 4mod8 is still 2-aligned -- so none of
+	 * these accesses is unaligned.
+	 *
+	 * Deliberately not a single wider store masked down to size, the way
+	 * memset finishes: that reads and rewrites bytes beyond the end of the
+	 * destination, and memcpy has never touched memory the caller did not
+	 * ask it to write.
+	 */
 $tail_bytes:
-	subq	$18, 1, $18		# E : count--
-	ldbu	$1, 0($17)		# L : fetch a byte
-	addq	$17, 1, $17		# E : src++
+	and	$18, 4, $1		# E : longword to do?
+	and	$18, 2, $3		# E : word to do?
+	beq	$1, $tail_word		# U :
 	nop				# E :
 
-	stb	$1, 0($16)		# L : store a byte
-	addq	$16, 1, $16		# E : dest++
-	bgt	$18, $tail_bytes	# U : more to be done?
+	ldl	$2, 0($17)		# L : 4 bytes
+	stl	$2, 0($16)		# L :
+	addq	$17, 4, $17		# E : src += 4
+	addq	$16, 4, $16		# E : dest += 4
+
+$tail_word:
+	and	$18, 1, $1		# E : odd byte to do?
+	beq	$3, $tail_byte		# U :
+	ldwu	$2, 0($17)		# L : 2 bytes
+	stw	$2, 0($16)		# L :
+
+	addq	$17, 2, $17		# E : src += 2
+	addq	$16, 2, $16		# E : dest += 2
+	nop				# E :
+	nop				# E :
+
+$tail_byte:
+	beq	$1, $nomoredata		# U :
+	ldbu	$2, 0($17)		# L : last byte
+	stb	$2, 0($16)		# L :
 	nop				# E :
 
 	/* branching to exit takes 3 extra cycles, so replicate exit here */
diff --git ./sysdeps/alpha/alphaev6/memmove.S ./sysdeps/alpha/alphaev6/memmove.S
index 7c0cca1391..d587a90dd9 100644
--- ./sysdeps/alpha/alphaev6/memmove.S
+++ ./sysdeps/alpha/alphaev6/memmove.S
@@ -258,15 +258,47 @@ $less_than_8:
 	nop				# E :
 	nop				# E :
 
+	/*
+	 * 1..7 trailing bytes, with source and destination both 0mod8 -- every
+	 * path into $tail_quads guarantees that, and the quad loop above keeps
+	 * it.  Do them as at most one longword, one word and one byte rather
+	 * than looping a byte at a time: the loop spends about eight issue
+	 * slots per byte, which on an EV68CB made a 15-byte copy 85% dearer
+	 * than a 16-byte one.  Each step leaves the pointers aligned for the
+	 * next -- 0mod8 is 0mod4, and 4mod8 is still 2-aligned -- so none of
+	 * these accesses is unaligned.
+	 *
+	 * Deliberately not a single wider store masked down to size, the way
+	 * memset finishes: that reads and rewrites bytes beyond the end of the
+	 * destination, and memcpy has never touched memory the caller did not
+	 * ask it to write.
+	 */
 $tail_bytes:
-	subq	$18, 1, $18		# E : count--
-	ldbu	$1, 0($17)		# L : fetch a byte
-	addq	$17, 1, $17		# E : src++
+	and	$18, 4, $1		# E : longword to do?
+	and	$18, 2, $3		# E : word to do?
+	beq	$1, $tail_word		# U :
 	nop				# E :
 
-	stb	$1, 0($16)		# L : store a byte
-	addq	$16, 1, $16		# E : dest++
-	bgt	$18, $tail_bytes	# U : more to be done?
+	ldl	$2, 0($17)		# L : 4 bytes
+	stl	$2, 0($16)		# L :
+	addq	$17, 4, $17		# E : src += 4
+	addq	$16, 4, $16		# E : dest += 4
+
+$tail_word:
+	and	$18, 1, $1		# E : odd byte to do?
+	beq	$3, $tail_byte		# U :
+	ldwu	$2, 0($17)		# L : 2 bytes
+	stw	$2, 0($16)		# L :
+
+	addq	$17, 2, $17		# E : src += 2
+	addq	$16, 2, $16		# E : dest += 2
+	nop				# E :
+	nop				# E :
+
+$tail_byte:
+	beq	$1, $nomoredata		# U :
+	ldbu	$2, 0($17)		# L : last byte
+	stb	$2, 0($16)		# L :
 	nop				# E :
 
 	ret	$31, ($26), 1		# L0 :
-- 
2.54.0