| Issue |
204070
|
| Summary |
[SCEV] Missed trip count for same-base inbounds pointer-IV loop with `< end` exit
|
| Labels |
new issue
|
| Assignees |
|
| Reporter |
134ARG
|
SCEV currently fails to infer the simple trip count for a same-base inbounds pointer-IV loop. This was motivated by a simple pointer-walk pattern in SPEC 2017 `500.perlbench_r`, `doop.c:S_do_trans_count`. Below is the extracted snippet from the original context:
```c
uint64_t count_matches_lt(const unsigned char *s, size_t len,
const int16_t *tbl) {
const unsigned char *send = s + len;
uint64_t matches = 0;
while (s < send) {
if (tbl[*s++] >= 0)
matches++;
}
return matches;
}
```
SCEV gives such results
```shell
Loop %do.body: backedge-taken count is
(-1 + (-1 * (ptrtoint ptr %s to i64)) +
((1 + (ptrtoint ptr %s to i64)) umax ((ptrtoint ptr %s to i64) + %len)))
Loop %do.body: symbolic max backedge-taken count is
(-1 + (-1 * (ptrtoint ptr %s to i64)) +
((1 + (ptrtoint ptr %s to i64)) umax ((ptrtoint ptr %s to i64) + %len)))
```
which reports a conservative ptrtoint / umax _expression_ instead of len - 1. As a result, downstream loop transforms do not see an ordinary counted loop. The final x86 asm just doe s a plain loop like this:
```asm
count_matches_lt:
testq %rsi, %rsi
je .LBB0_1
addq %rdi, %rsi
xorl %eax, %eax
.LBB0_4:
movzbl (%rdi), %ecx
incq %rdi
xorl %r8d, %r8d
cmpw $0, (%rdx,%rcx,2)
setns %r8b
addq %r8, %rax
cmpq %rsi, %rdi
jb .LBB0_4
retq
.LBB0_1:
xorl %eax, %eax
retq
```
The point of it being a possible missed opimization is, if we explicitly implement the pattern matching in SCEV, or simply change the guard from `s < send` to `s != send`, SCEV could give the concise trip count:
```shell
Loop %do.body: backedge-taken count is (-1 + %len)
Loop %do.body: symbolic max backedge-taken count is (-1 + %len)
```
And the final x86 asm is properly unrolled by 4:
```asm
count_matches_ne:
testq %rsi, %rsi
je .LBB1_1
movl %esi, %ecx
andl $3, %ecx
cmpq $4, %rsi
jae .LBB1_5
...
.LBB1_6:
movzbl (%rdi), %r8d
...
movzbl 1(%rdi), %r8d
...
movzbl 2(%rdi), %r8d
...
movzbl 3(%rdi), %r8d
addq $4, %rdi
...
addq $-4, %rsi
jne .LBB1_6
```
Godbolt: https://godbolt.org/z/7o96WYP73
![]()
_______________________________________________
llvm-bugs mailing list
[email protected]
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-bugs
