How to avoid auto-vectorization for this loop (rolls at most 3 times)

How to avoid auto-vectorization for this loop (rolls at most 3 times)

[Fang, Changpeng]

It seems  the auto-vectorizer could not recognize that this loop will roll at most 3 times.
And it will generate quite messy code. 

int a[1024], b[1024]; 
void foo (int n) 
{
  int i;
  for (i = (n/4)*4; i< n; i++)
    a[i] =  a[i] +  b[i];
}

How can we correctly estimate the number of iterations for this case and use this info for the vectorizer?

Thanks,

Changpeng

RE: How to avoid auto-vectorization for this loop (rolls at most 3 times)

[Fang, Changpeng]

[-- Attachment #1: Type: text/plain, Size: 986 bytes --]

>> It seems  the auto-vectorizer could not recognize that this loop will
>> roll at most 3 times.
>> And it will generate quite messy code.
>>
>> int a[1024], b[1024];
>> void foo (int n)
>> {
>>   int i;
>>   for (i = (n/4)*4; i< n; i++)
>>     a[i] =  a[i] +  b[i];
>> }
>>
>> How can we correctly estimate the number of iterations for this case
>> and use this info for the vectorizer?

>Does it recognise it if you rewrite the loop as follows:

>for (i = n&~0x3; i< n; i++)
 >    a[i] =  a[i] +  b[i];

NO.  

But it is OK for the following case:

 for (i = n-3; i< n; i++)
     a[i] =  a[i] +  b[i];

It seems it fails at the case of "unknown but small". Anyway, this mostly
affects compilation time and code size, and has limited impact on 
performance.

For
for (i = n&~0x3; i< n; i++)
    a[i] =  a[i] +  b[i]; 

The attached foo-O3-no-tree-vectorize.s is what we expect from the optimizer.
foo-O3.s is too bad.

Thanks,

Changpeng


 

[-- Attachment #2: foo-O3-no-tree-vectorize.s --]
[-- Type: application/octet-stream, Size: 500 bytes --]

	.file	"foo1.c"
	.text
	.p2align 4,,15
	.globl	foo
	.type	foo, @function
foo:
.LFB0:
	.cfi_startproc
	movl	%edi, %eax
	andl	$-4, %eax
	cmpl	%eax, %edi
	jle	.L1
	.p2align 4,,10
	.p2align 3
.L4:
	movslq	%eax, %rdx
	addl	$1, %eax
	movl	a(,%rdx,4), %ecx
	addl	b(,%rdx,4), %ecx
	cmpl	%edi, %eax
	movl	%ecx, a(,%rdx,4)
	jne	.L4
.L1:
	rep
	ret
	.cfi_endproc
.LFE0:
	.size	foo, .-foo
	.comm	b,4096,32
	.comm	a,4096,32
	.ident	"GCC: (GNU) 4.6.0 20100831 (experimental)"
	.section	.note.GNU-stack,"",@progbits

[-- Attachment #3: foo-O3.s --]
[-- Type: application/octet-stream, Size: 1634 bytes --]

	.file	"foo1.c"
	.text
	.p2align 4,,15
	.globl	foo
	.type	foo, @function
foo:
.LFB0:
	.cfi_startproc
	movl	%edi, %esi
	pushq	%rbp
	.cfi_def_cfa_offset 16
	andl	$-4, %esi
	cmpl	%esi, %edi
	pushq	%rbx
	.cfi_def_cfa_offset 24
	jle	.L1
	.cfi_offset 3, -24
	.cfi_offset 6, -16
	movslq	%esi, %rbx
	movl	%edi, %r9d
	leaq	a(,%rbx,4), %r8
	subl	%esi, %r9d
	andl	$15, %r8d
	shrq	$2, %r8
	negl	%r8d
	andl	$3, %r8d
	cmpl	%r9d, %r8d
	cmova	%r9d, %r8d
	testl	%r8d, %r8d
	mov	%r8d, %ebp
	je	.L8
	movl	%esi, %eax
	.p2align 4,,10
	.p2align 3
.L4:
	movslq	%eax, %rdx
	addl	$1, %eax
	movl	a(,%rdx,4), %ecx
	addl	b(,%rdx,4), %ecx
	movl	%ecx, a(,%rdx,4)
	movl	%eax, %edx
	subl	%esi, %edx
	cmpl	%edx, %r8d
	ja	.L4
	cmpl	%r8d, %r9d
	je	.L1
.L3:
	movl	%r9d, %r11d
	subl	%r8d, %r11d
	movl	%r11d, %r8d
	shrl	$2, %r8d
	leal	0(,%r8,4), %r10d
	testl	%r10d, %r10d
	je	.L9
	leaq	(%rbx,%rbp), %r9
	xorl	%edx, %edx
	xorl	%ecx, %ecx
	salq	$2, %r9
	leaq	a(%r9), %rsi
	addq	$b, %r9
	.p2align 4,,10
	.p2align 3
.L6:
	movdqu	(%r9,%rdx), %xmm0
	addl	$1, %ecx
	paddd	(%rsi,%rdx), %xmm0
	movdqa	%xmm0, (%rsi,%rdx)
	addq	$16, %rdx
	cmpl	%r8d, %ecx
	jb	.L6
	addl	%r10d, %eax
	cmpl	%r10d, %r11d
	je	.L1
	.p2align 4,,10
	.p2align 3
.L9:
	movslq	%eax, %rdx
	addl	$1, %eax
	movl	a(,%rdx,4), %ecx
	addl	b(,%rdx,4), %ecx
	cmpl	%eax, %edi
	movl	%ecx, a(,%rdx,4)
	jg	.L9
.L1:
	popq	%rbx
	.cfi_remember_state
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	ret
.L8:
	.cfi_restore_state
	movl	%esi, %eax
	jmp	.L3
	.cfi_endproc
.LFE0:
	.size	foo, .-foo
	.comm	b,4096,32
	.comm	a,4096,32
	.ident	"GCC: (GNU) 4.6.0 20100831 (experimental)"
	.section	.note.GNU-stack,"",@progbits