[PATCH 13/20] alpha: copy four quads a trip below the ev6 unrolled loop

[Matt Turner]

Copies shorter than 128 bytes never reach the unrolled loop, and the
remainder of the ones that do is up to 63 bytes; both were handled a
quadword at a time by a loop spending eight issue slots per eight bytes.
That is the wrong shape for the work.  Short copies miss nothing, replay
nothing and retire better than two instructions a cycle, so unlike the long
copies this file spends most of its comments on they are issue-bound, and
what they want is fewer instructions per byte.

Take four quads a trip while at least 32 bytes remain, then fall into the
existing one-quad loop.  Measured on an EV68CB, hot, cycles per call:

  size    before   after
  112       64.7    36.2   1.79x
  120       65.9    37.7   1.75x
  127       69.4    42.2   1.64x
  160       80.0    52.8   1.52x
  96        40.3    31.7   1.27x
  64        32.2    27.1   1.19x
  128       52.8    47.8   1.11x

The loop body sits out of line, past every return path, and that placement
is not incidental.  With it inline just above $move_a_quad, copies of 1KB
and 2KB lost about 5% -- 228 cycles becoming 237 at 1KB -- even though a
copy that size never executes a single one of these instructions.  Growing
the straight-line distance between the unrolled loop and the tail is enough
to do that on its own.  Out of line, 1KB gains 4% and 2KB is level, and the
only price is a few percent of the gain between 32 and 96 bytes.

Copies below 32 bytes pay one cycle for the test that skips the new loop --
about 5% at 8 to 24 bytes, where the call is only 17 to 22 cycles to begin
with.  The instruction count at the head is unchanged, since the test takes
the place of two nops; the cost is the branch itself.  Note that GCC expands
small constant-size copies inline, so the lengths that lose here are the
ones least likely to reach this code at all.

Sizes from 256 to 512 still measure 2-3% down for the same layout reason,
which no placement tried made go away entirely.

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 | 45 ++++++++++++++++++++++++++++++--
 2 files changed, 86 insertions(+), 4 deletions(-)

diff --git ./sysdeps/alpha/alphaev6/memcpy.S ./sysdeps/alpha/alphaev6/memcpy.S
index ee251e8b8f..d86c00b9be 100644
--- ./sysdeps/alpha/alphaev6/memcpy.S
+++ ./sysdeps/alpha/alphaev6/memcpy.S
@@ -253,8 +253,8 @@ $no_unroll:
 	.align 4
 	subq	$18, 8, $18		# E : At least a quad left?
 	blt	$18, $less_than_8	# U : Nope
-	nop				# E :
-	nop				# E :
+	subq	$18, 24, $1		# E : four whole quads left?
+	bge	$1, $move_four_quads	# U : yes -- out of line, below
 
 $move_a_quad:
 	ldq	$1, 0($17)		# L : fetch 8
@@ -402,6 +402,47 @@ $nomoredata:
 	nop				# E :
 	nop				# E :
 
+
+	/*
+	 * Four quads a trip, for the 32..127 byte copies that never reach the
+	 * unrolled loop and for the remainder of the ones that do.  Short
+	 * copies are issue-bound -- they miss nothing and replay nothing, and
+	 * retire better than two instructions a cycle -- so what they want is
+	 * simply fewer instructions per byte than the one-quad loop above.
+	 *
+	 * This lives out of line, past every return path, on purpose.  Placed
+	 * inline just above $move_a_quad it costs long copies about 5% at 1KB
+	 * and 2KB, even though a copy that size never executes a single one of
+	 * these instructions, purely by pushing the unrolled loop and the tail
+	 * further apart.  Moving it down here recovers that and gives up only
+	 * a few percent of the gain between 32 and 96 bytes.
+	 *
+	 * $18 counts bytes remaining less eight, so a full trip needs $18 >= 24.
+	 * Falling out can leave $18 negative and $move_a_quad is a do-while, so
+	 * the count is rechecked before going back to it.
+	 */
+	.align 4
+$move_four_quads:
+	ldq	$1, 0($17)		# L : 32 bytes
+	ldq	$2, 8($17)		# L :
+	ldq	$3, 16($17)		# L :
+	ldq	$5, 24($17)		# L :
+
+	stq	$1, 0($16)		# L :
+	stq	$2, 8($16)		# L :
+	stq	$3, 16($16)		# L :
+	stq	$5, 24($16)		# L :
+
+	addq	$17, 32, $17		# E : src += 32
+	addq	$16, 32, $16		# E : dest += 32
+	subq	$18, 32, $18		# E : count -= 32
+	nop				# E :
+
+	subq	$18, 24, $1		# E : room for another full trip?
+	bge	$1, $move_four_quads	# U :
+	bge	$18, $move_a_quad	# U : a whole quad still left
+	br	$31, $less_than_8	# U : only trailing bytes
+
 END(memcpy)
 #ifndef USE_AS_MEMPCPY
 libc_hidden_builtin_def (memcpy)
diff --git ./sysdeps/alpha/alphaev6/memmove.S ./sysdeps/alpha/alphaev6/memmove.S
index d587a90dd9..a69a0588a2 100644
--- ./sysdeps/alpha/alphaev6/memmove.S
+++ ./sysdeps/alpha/alphaev6/memmove.S
@@ -237,8 +237,8 @@ $no_unroll:
 	.align 4
 	subq	$18, 8, $18		# E : At least a quad left?
 	blt	$18, $less_than_8	# U : Nope
-	nop				# E :
-	nop				# E :
+	subq	$18, 24, $1		# E : four whole quads left?
+	bge	$1, $move_four_quads	# U : yes -- out of line, below
 
 $move_a_quad:
 	ldq	$1, 0($17)		# L : fetch 8
@@ -412,5 +412,46 @@ $back_b:
 	bne	$18, $back_b		# U :
 	ret	$31, ($26), 1		# L0 :
 
+
+	/*
+	 * Four quads a trip, for the 32..127 byte copies that never reach the
+	 * unrolled loop and for the remainder of the ones that do.  Short
+	 * copies are issue-bound -- they miss nothing and replay nothing, and
+	 * retire better than two instructions a cycle -- so what they want is
+	 * simply fewer instructions per byte than the one-quad loop above.
+	 *
+	 * This lives out of line, past every return path, on purpose.  Placed
+	 * inline just above $move_a_quad it costs long copies about 5% at 1KB
+	 * and 2KB, even though a copy that size never executes a single one of
+	 * these instructions, purely by pushing the unrolled loop and the tail
+	 * further apart.  Moving it down here recovers that and gives up only
+	 * a few percent of the gain between 32 and 96 bytes.
+	 *
+	 * $18 counts bytes remaining less eight, so a full trip needs $18 >= 24.
+	 * Falling out can leave $18 negative and $move_a_quad is a do-while, so
+	 * the count is rechecked before going back to it.
+	 */
+	.align 4
+$move_four_quads:
+	ldq	$1, 0($17)		# L : 32 bytes
+	ldq	$2, 8($17)		# L :
+	ldq	$3, 16($17)		# L :
+	ldq	$5, 24($17)		# L :
+
+	stq	$1, 0($16)		# L :
+	stq	$2, 8($16)		# L :
+	stq	$3, 16($16)		# L :
+	stq	$5, 24($16)		# L :
+
+	addq	$17, 32, $17		# E : src += 32
+	addq	$16, 32, $16		# E : dest += 32
+	subq	$18, 32, $18		# E : count -= 32
+	nop				# E :
+
+	subq	$18, 24, $1		# E : room for another full trip?
+	bge	$1, $move_four_quads	# U :
+	bge	$18, $move_a_quad	# U : a whole quad still left
+	br	$31, $less_than_8	# U : only trailing bytes
+
 END(memmove)
 libc_hidden_builtin_def (memmove)
-- 
2.54.0