Add value range support into memcpy/memset expansion

> > Nice extension. Test cases would be great to have.
> Fore those you need i386 changes to actually use the info.  I will post that
> after some cleanup and additional testing.

Hi,
since I already caught your attention, here is the target specific part for
comments.

this patch implements memcpy/memset prologues and epilogues as suggested by
Ondrej Bilka.  His glibc implementation use IMO very smart trick with single
misaligned move to copy first N and last N bytes of the block.  The remainder
of the block is then copied by the usual loop that gets aligned to the proper
address.

This leads to partial memory stall, but that is handled well by modern x86
chips.

For example in the following testcase:
char *a;
char *b;
t1()
{
  memcpy (a,b,140);
}

We now produce:
        movq    b(%rip), %rsi
        movq    a(%rip), %rcx
        movq    (%rsi), %rax <- first 8 bytes are moved
        leaq    8(%rcx), %rdi
        andq    $-8, %rdi   <- dest is aligned
        movq    %rax, (%rcx)
        movq    132(%rsi), %rax  <- last 8 bytes are moved
        movq    %rax, 132(%rcx)
        subq    %rdi, %rcx  <- alignment is subtracted from count
        subq    %rcx, %rsi  <- source is aligned
        addl    $140, %ecx  <- normal copying of 8 byte chunks
        shrl    $3, %ecx
        rep; movsq
        ret

Instead of:
	movq	a(%rip), %rdi
	movq	b(%rip), %rsi
	movl	$140, %eax
	testb	$1, %dil
	jne	.L28
	testb	$2, %dil
	jne	.L29
.L3:
	testb	$4, %dil
	jne	.L30
.L4:
	movl	%eax, %ecx
	xorl	%edx, %edx
	shrl	$3, %ecx
	testb	$4, %al
	rep movsq
	je	.L5
	movl	(%rsi), %edx
	movl	%edx, (%rdi)
	movl	$4, %edx
.L5:
	testb	$2, %al
	je	.L6
	movzwl	(%rsi,%rdx), %ecx
	movw	%cx, (%rdi,%rdx)
	addq	$2, %rdx
.L6:
	testb	$1, %al
	je	.L8
	movzbl	(%rsi,%rdx), %eax
	movb	%al, (%rdi,%rdx)
.L8:
	rep
	ret
	.p2align 4,,10
	.p2align 3
.L28:
	movzbl	(%rsi), %eax
	addq	$1, %rsi
	movb	%al, (%rdi)
	addq	$1, %rdi
	movl	$139, %eax
	testb	$2, %dil
	je	.L3
	.p2align 4,,10
	.p2align 3
.L29:
	movzwl	(%rsi), %edx
	subl	$2, %eax
	addq	$2, %rsi
	movw	%dx, (%rdi)
	addq	$2, %rdi
	testb	$4, %dil
	je	.L4
	.p2align 4,,10
	.p2align 3
.L30:
	movl	(%rsi), %edx
	subl	$4, %eax
	addq	$4, %rsi
	movl	%edx, (%rdi)
	addq	$4, %rdi
	jmp	.L4

With the proposed value range code we can now take advantage of it even for
non-constant moves.  Somewhat artificial testcase:

char *p,*q;
t(unsigned int a)
{
  if (a>8 && a<100)
    memcpy(q,p,a);

}

Still generate pretty much same code (while -minline-all-stringops code on
mainline is just horrible):
        leal    -9(%rdi), %edx
        movl    %edi, %eax
        cmpl    $90, %edx
        jbe     .L5
        rep; ret
        .p2align 4,,10
        .p2align 3
.L5:
        movq    p(%rip), %rsi
        movq    q(%rip), %rcx
        movq    (%rsi), %rdx
        movq    %rdx, (%rcx)
        movl    %edi, %edx
        movq    -8(%rsi,%rdx), %rdi
        movq    %rdi, -8(%rcx,%rdx)
        leaq    8(%rcx), %rdi
        andq    $-8, %rdi
        subq    %rdi, %rcx
        subq    %rcx, %rsi
        addl    %eax, %ecx
        shrl    $3, %ecx
        rep; movsq
        ret

Of course it is quite common to know only upper bound on the block.  In this case
we need to generate prologue for first few bytes:
char *p,*q;
t(unsigned int a)
{
  if (a<100)
    memcpy(q,p,a);

}
t:
.LFB0:
        .cfi_startproc
        cmpl    $99, %edi
        jbe     .L15
.L7:
        rep; ret
        .p2align 4,,10
        .p2align 3
.L15:
        cmpl    $8, %edi
        movq    q(%rip), %rdx
        movq    p(%rip), %rsi
        jae     .L3
        testb   $4, %dil
        jne     .L16
        testl   %edi, %edi
        je      .L7
        movzbl  (%rsi), %eax
        testb   $2, %dil
        movb    %al, (%rdx)
        je      .L7
        movl    %edi, %edi
        movzwl  -2(%rsi,%rdi), %eax
        movw    %ax, -2(%rdx,%rdi)
        ret
        .p2align 4,,10
        .p2align 3
.L3:
        movq    (%rsi), %rax
        movq    %rax, (%rdx)
        movl    %edi, %eax
        movq    -8(%rsi,%rax), %rcx
        movq    %rcx, -8(%rdx,%rax)
        leaq    8(%rdx), %rax
        andq    $-8, %rax
        subq    %rax, %rdx
        addl    %edx, %edi
        subq    %rdx, %rsi
        shrl    $3, %edi
        movl    %edi, %ecx
        movq    %rax, %rdi
        rep; movsq
        ret
        .p2align 4,,10
        .p2align 3
.L16:
        movl    (%rsi), %eax
        movl    %edi, %edi
        movl    %eax, (%rdx)
        movl    -4(%rsi,%rdi), %eax
        movl    %eax, -4(%rdx,%rdi)
        ret
        .cfi_endproc
.LFE0:

Mainline would output a libcall here (because size is unknown to it) and with
inlining all stringops it winds up 210 bytes of code instead of 142 bytes
above.

Unforutnately the following testcase:
char *p,*q;
t(int a)
{
  if (a<100)
    memcpy(q,p,a);

}
Won't get inlined.  This is because A is known to be smaller than 100 that
results in anti range after conversion to size_t.  This anti range allows very
large values (above INT_MAX) and thus we do not know the block size.
I am not sure if the sane range can be recovered somehow.  If not, maybe
this is common enough to add support for "probable" upper bound parameter to
the template.

Use of value ranges makes it harder to choose proper algorithm since the average
size is no longer known.  For the moment I take simple average of lower and upper
bound, but this is wrong.

Libcall starts to win only for pretty large blocks (over 4GB definitely) so it makes
sense to inline functions with range 0....4096 even though the cost tables tells
to expand libcall for everything bigger than 140 bytes:  if blocks are small we will
get noticeable win and if blocks are big, we won't lose much.

I am considering assigning value ranges to the algorithms, too, for more sane
choices in decide_alg.

I also think the misaligned move trick can/should be performed by
move_by_pieces and we ought to consider sane use of SSE - current vector_loop
with unrolling factor of 4 seems bit extreme.  At least buldozer is happy with
2 and I would expect SSE moves to be especially useful for moving blocks with
known size where they are not used at all.

Currently I disabled misaligned move prologues/epilogues for Michael's vector
loop path since they ends up longer than the traditional code (that use loop
for epilogue)

I will deal with that incrementally.

Bootstrapped/regtested x86_64-linux with and without misaligned move prologues
and also with -minline-all-stringop.

I plan to do some furhter testing tomorrow and add testcases while waiting for
the generic part to be reviewed.
Comments are welcome.

	* i386.h (TARGET_MISALIGNED_MOVE_STRING_PROLOGUES_EPILOGUES): New macro.
	* i386.md (movmem, setmem insn patterms): Add new parameters for value
	range.
	* i386-protos.h (ix86_expand_movmem, ix86_expand_setmem): Add new
	parameters for value range.
	* i386.c (expand_small_movmem): New function.
	(expand_movmem_prologue_epilogue_by_misaligned_moves): New function.
	(expand_small_setmem): New function.
	(expand_setmem_prologue_epilogue_by_misaligned_moves): New funcion.
	(alg_usable_p): New function.
	(decide_alg): Add zero_memset parameter; cleanup; consider value ranges.
	(ix86_expand_movmem): Add value range parameters; update block comment;
	add support for value ranges; add support for misaligned move prologues.
	(ix86_expand_setmem): Likewise.

Add value range support into memcpy/memset expansion

Commit Message

Comments

Patch