[sinking] testcase that needs sinking enabled

[ohmantics]

Bugzilla Link	3206
Version	unspecified
OS	MacOS X
CC	@ohmantics,@asl

Extended Description

On i386-apple-darwin, built with "llvmc -O3 -S select_reduced.c" with or without -clang. At the end of each case should be a select/cmov.

inline attribute((always_inline))
unsigned short _OSSwapInt16(unsigned short _data)
{
return ((_data << 8) | (_data >> 8));
}

inline attribute((always_inline))
unsigned short ReadSwapShort(unsigned char* data, unsigned int offset)
{
return _OSSwapInt16((unsigned short) &data[offset]);
}

unsigned short* myfunc(unsigned short* endCodes, unsigned short probe, unsigned short entrySelector, unsigned short c)
{
#define PROBE_SHIFT
{
probe >>= 1;
if (c > _OSSwapInt16(endCodes[probe >> 1]))
endCodes = &endCodes[probe >> 1];
}

switch (entrySelector)
{
	case 15:	PROBE_SHIFT;	// FALL-THRU
	case 14:	PROBE_SHIFT;	// FALL-THRU
	case 13:	PROBE_SHIFT;	// FALL-THRU
	case 12:	PROBE_SHIFT;	// FALL-THRU
	case 11:	PROBE_SHIFT;	// FALL-THRU
	case 10:	PROBE_SHIFT;	// FALL-THRU
	case  9:	PROBE_SHIFT;	// FALL-THRU
	case  8:	PROBE_SHIFT;	// FALL-THRU
	case  7:	PROBE_SHIFT;	// FALL-THRU
	case  6:	PROBE_SHIFT;	// FALL-THRU
	case  5:	PROBE_SHIFT;	// FALL-THRU
	case  4:	PROBE_SHIFT;	// FALL-THRU
}

return endCodes;    

}

[lattner]

Very interesting, I see a bunch of blocks with:

jae	LBB3_4	## bb13

LBB3_3: ## bb12
movl %ecx, %eax
LBB3_4: ## bb13
...
leal (%eax,%ecx,2), %ecx
jae LBB3_6 ## bb15
LBB3_5: ## bb14
movl %ecx, %eax
LBB3_6: ## bb15
movw %di, %cx

etc. The deal is that '4" and "6" have a switch statement as a predecessor too.

[lattner]

Ok, even more fun: this really wants sinking, because the LEA is partially dead. With this command:

$ llvm-gcc t.c -S -o - -O3 -emit-llvm | llvm-as | llc --enable-sinking

We get:

shrw	%si
cmpw	%dx, %di
jae	LBB3_18	## bb27

LBB3_17: ## bb26
leal (%eax,%ecx,2), %eax
LBB3_18: ## bb27
movw %si, %cx
shrw $2, %cx

[lattner]

Yes, I'm inclined to think that this really should be solved by enabling sinking by default. The tradeoff between the branch vs select will depend on the dynamic behavior of the data, which the compiler can't predict without profile info. Using a branch over the lea is a pretty reasonable thing to do.

[lattner]

Another very interesting code sequence:
movw %si, %cx
shrw $2, %cx
movzwl %cx, %ecx
movw (%eax,%ecx,2), %di

I don't see any reason not to use:

    movzwl  %si, %ecx
    andl %ecx, ~3
    movw    (%eax,%ecx), %di

[lattner]

Aha, the 2) is multiply by 2, not shift by 2. This is still achievable, but requires being trickier about the other shift.

[ohmantics]

This is a reduction of a binary search on a TrueType 'cmap' format 4 lookup table. The tables come with precalculated values that were designed to improve performance on a 68000. This is very close to the intended original algorithm vs. the conventional binary search code found elsewhere such as in FreeType. In this case, entrySelector is the maximum number of probes the search will take, e.g. floor power of two of the table size. For TimesNewRoman, that number is 7. The trailing four cases elided here iterate forward (with post-increment addressing) instead of bothering to wiggle among them.

As a binary search, the branch vs. select decision can't reasonably be determined with profile info with the exception that ASCII will tend to hit in a clump at the beginning of the table so likely test data sets will have common profiles, which may incorrectly skew the decision. Old school local-only optimization is the winner here. The same problem turns up in interpreter loops where optimizations like PRE may pressimize the code.

[bwendling]

Looks like we're generating the cmov instructions now:

	.text
	.file	"pr.c"
	.globl	myfunc                          # -- Begin function myfunc
	.p2align	4, 0x90
	.type	myfunc,@function
myfunc:                                 # @myfunc
	.cfi_startproc
# %bb.0:
                                        # kill: def $edx killed $edx def $rdx
	movq	%rdi, %rax
	addl	$-4, %edx
	cmpw	$11, %dx
	ja	.LBB0_14
# %bb.1:
	movzwl	%dx, %edx
	jmpq	*.LJTI0_0(,%rdx,8)
.LBB0_2:
	movzwl	%si, %edx
	movl	%edx, %esi
	shrl	%esi
	shrq	$2, %rdx
	movzwl	(%rax,%rdx,2), %edi
	rolw	$8, %di
	leaq	(%rax,%rdx,2), %rdx
	cmpw	%cx, %di
	cmovbq	%rdx, %rax
.LBB0_3:
	movzwl	%si, %edx
	movl	%edx, %esi
	shrl	%esi
	shrq	$2, %rdx
	movzwl	(%rax,%rdx,2), %edi
	rolw	$8, %di
	leaq	(%rax,%rdx,2), %rdx
	cmpw	%cx, %di
	cmovbq	%rdx, %rax
.LBB0_4:
	movzwl	%si, %edx
	movl	%edx, %esi
	shrl	%esi
	shrq	$2, %rdx
	movzwl	(%rax,%rdx,2), %edi
	rolw	$8, %di
	leaq	(%rax,%rdx,2), %rdx
	cmpw	%cx, %di
	cmovbq	%rdx, %rax
.LBB0_5:
	movzwl	%si, %edx
	movl	%edx, %esi
	shrl	%esi
	shrq	$2, %rdx
	movzwl	(%rax,%rdx,2), %edi
	rolw	$8, %di
	leaq	(%rax,%rdx,2), %rdx
	cmpw	%cx, %di
	cmovbq	%rdx, %rax
.LBB0_6:
	movzwl	%si, %edx
	movl	%edx, %esi
	shrl	%esi
	shrq	$2, %rdx
	movzwl	(%rax,%rdx,2), %edi
	rolw	$8, %di
	leaq	(%rax,%rdx,2), %rdx
	cmpw	%cx, %di
	cmovbq	%rdx, %rax
.LBB0_7:
	movzwl	%si, %edx
	movl	%edx, %esi
	shrl	%esi
	shrq	$2, %rdx
	movzwl	(%rax,%rdx,2), %edi
	rolw	$8, %di
	leaq	(%rax,%rdx,2), %rdx
	cmpw	%cx, %di
	cmovbq	%rdx, %rax
.LBB0_8:
	movzwl	%si, %edx
	movl	%edx, %esi
	shrl	%esi
	shrq	$2, %rdx
	movzwl	(%rax,%rdx,2), %edi
	rolw	$8, %di
	leaq	(%rax,%rdx,2), %rdx
	cmpw	%cx, %di
	cmovbq	%rdx, %rax
.LBB0_9:
	movzwl	%si, %edx
	movl	%edx, %esi
	shrl	%esi
	shrq	$2, %rdx
	movzwl	(%rax,%rdx,2), %edi
	rolw	$8, %di
	leaq	(%rax,%rdx,2), %rdx
	cmpw	%cx, %di
	cmovbq	%rdx, %rax
.LBB0_10:
	movzwl	%si, %edx
	movl	%edx, %esi
	shrl	%esi
	shrq	$2, %rdx
	movzwl	(%rax,%rdx,2), %edi
	rolw	$8, %di
	leaq	(%rax,%rdx,2), %rdx
	cmpw	%cx, %di
	cmovbq	%rdx, %rax
.LBB0_11:
	movzwl	%si, %edx
	movl	%edx, %esi
	shrl	%esi
	shrq	$2, %rdx
	movzwl	(%rax,%rdx,2), %edi
	rolw	$8, %di
	leaq	(%rax,%rdx,2), %rdx
	cmpw	%cx, %di
	cmovbq	%rdx, %rax
.LBB0_12:
	movzwl	%si, %edx
	movl	%edx, %esi
	shrl	%esi
	shrq	$2, %rdx
	movzwl	(%rax,%rdx,2), %edi
	rolw	$8, %di
	leaq	(%rax,%rdx,2), %rdx
	cmpw	%cx, %di
	cmovbq	%rdx, %rax
.LBB0_13:
	movzwl	%si, %edx
	shrq	$2, %rdx
	movzwl	(%rax,%rdx,2), %esi
	rolw	$8, %si
	leaq	(%rax,%rdx,2), %rdx
	cmpw	%cx, %si
	cmovbq	%rdx, %rax
.LBB0_14:
	retq
.Lfunc_end0:
	.size	myfunc, .Lfunc_end0-myfunc
	.cfi_endproc
	.section	.rodata,"a",@progbits
	.p2align	3
.LJTI0_0:
	.quad	.LBB0_13
	.quad	.LBB0_12
	.quad	.LBB0_11
	.quad	.LBB0_10
	.quad	.LBB0_9
	.quad	.LBB0_8
	.quad	.LBB0_7
	.quad	.LBB0_6
	.quad	.LBB0_5
	.quad	.LBB0_4
	.quad	.LBB0_3
	.quad	.LBB0_2
                                        # -- End function
	.ident	"Debian clang version 13.0.1-+rc1-1~exp4"
	.section	".note.GNU-stack","",@progbits
	.addrsig