switch lowering places compare in different block than shift

[edwintorok]

Bugzilla Link	3253
Resolution	FIXED
Resolved on	Jan 29, 2009 11:21
Version	trunk
OS	Linux
CC	@asl,@lattner,@efriedma-quic,@sunfishcode

Extended Description

Consider this code:
int foo(char *c)
{
return strcspn(c, ":\r\n");
}

llvm-gcc translates this into this (which is better than gcc, which does 3 cmpb!):

.text
.align 16
.globl foo
.type foo,@function
foo:
xorl %eax, %eax
jmp .LBB1_2 # bb24
.LBB1_1: # bb23
incq %rax
.LBB1_2: # bb24
movb (%rdi,%rax), %cl
movl $1, %edx
shlq %cl, %rdx
cmpb $58, %cl
ja .LBB1_1 # bb23
.LBB1_3: # bb24
movabsq $288230376151720961, %rcx
testq %rcx, %rdx
je .LBB1_1 # bb23
.LBB1_4: # bb35
ret
.size foo, .-foo

Tron on #llvm suggested that it could be improved even further:

• movl $1, %rdx; shl %cl, %rdx; test %ecx, %edx == bt
• loading the huge constant (the instruction is 10 bytes long!) should be moved out of the loop

[sunfishcode]

Looks like the first thing to do is to teach switch lowering to put the movl $1
and the shift in the same block as the test in this case. Then it ought to be
possible to get isel to select the 1 + shl + test to bt + jnc.

bt isn't completely equivalent to "... test" because bt only sets CF and not
ZF, SF, OF, etc., so it'll be necessary to select it along with the branch so
that the appropriate branch can be used.

Enabling MachineLICM (llc -machine-licm) does result in the large constant
being hoisted out of the loop. Unfortunately it's not yet enabled by default.
Hopefully it will be soon.

[sunfishcode]

Actually, the bt instruction is not applicable here, since it only tests one bit.

It would still be beneficial to move the 1 and the shl out of the loop though.

[edwintorok]

Actually, the bt instruction is not applicable here, since it only tests one
bit.

One bit is sufficient:
you test if bit CL appears in the constant -> character is accepted
doesn't appear -> character is rejected

It would still be beneficial to move the 1 and the shl out of the loop though.

[sunfishcode]

One bit is sufficient:

Ah, you're right.

Here is what FIRM generates (edited for brevity):

foo:
pushl %ebp
movl 8(%esp), %ecx
xorl %eax, %eax
movl $0x2401, %ebp
jmp .L52
.L57:
btl %edx, %ebp
jb .L83
.L47:
incl %eax
.L52:
movsbl (%eax,%ecx), %edx
cmpl $0x1F, %edx
jg .L47
jmp .L57
.L83:
popl %ebp
ret

[lattner]

Hi Edwin, Can you attach a .i file for this? I'm not seeing strcspn being inlined on my system.

[edwintorok]

Hi Edwin, Can you attach a .i file for this? I'm not seeing strcspn being
inlined on my system.

It isn't inlined here either. Must be some magic in llvm-gcc or llvm ;)

Here is a testcase that uses a plain loop:
int foo2(char *c, size_t len)
{
unsigned i;
for(i=0;i<len;i++) {
unsigned char x = c[i];
if (x == ':' || x == '\r' || x == '\n')
break;
}
return i;
}

[lattner]

it would also be interesting to enhance simplifylibcalls to handle this, if we don't know where/how this magic is happening :)

[efriedma-quic]

Hi Edwin, Can you attach a .i file for this? I'm not seeing strcspn being
inlined on my system.

I think it doesn't inline unless you include string.h.

[efriedma-quic]

One bit is sufficient:

Ah, you're right.

Here is what FIRM generates (edited for brevity):

foo:
pushl %ebp
movl 8(%esp), %ecx
xorl %eax, %eax
movl $0x2401, %ebp
jmp .L52
.L57:
btl %edx, %ebp
jb .L83
.L47:
incl %eax
.L52:
movsbl (%eax,%ecx), %edx
cmpl $0x1F, %edx
jg .L47
jmp .L57
.L83:
popl %ebp
ret

I assume this is for strcspn(c, "\r\n"), rather than the original testcase?

[lattner]

Right, please attach the .i file you get with that! :) Thanks

[efriedma-quic]

Preprocessed version of testcase
Okay, here it is... not sure this has anything useful.

[edwintorok]

llvm-gcc -O1 -E
Found it!

It is not compiler magic, but rather glibc header magic ;)

If I preprocess with -O1 or higher I get a special strcspn macro that uses __builtin_constant_p, __builtin_strcspn, and special versions __strcspn_c1, __strcspn_c2, __strcspn_c3.

Previously I wasn't using -O1 when preprocessing so I got a simple extern definition instead of the macro.
I "love" the way you get a different header included depending on optimization level ;)

[lattner]

Nice! I added some notes here:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20081222/071450.html

simplifylibcalls should really do this. Not all targets have these optimizations (e.g. macos) and using builtin_constantp won't catch many cases that inlining/constant prop can expose.

[lattner]

Here's a simpler example:

void foo (void);
int test (int x, int n) {
if (x & (1 << n))
foo ();
return 0;
}

We should compile this to something like:
test:
subl $12, %esp
movl 20(%esp), %edx
movl 16(%esp), %eax
btl %edx, %eax
jnc .L2
call foo
.L2:
xorl %eax, %eax
addl $12, %esp
ret

[lattner]

We now generate btl instructions where appropriate, see:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20081222/071495.html

However, switch lowering is dropping the shift left in the predecessor block from the comparison. If that got moved to the comparison block, we'd generate it for the switch case.