llvm / llvm/llvm-project

[SCEV] Missed trip count for same-base inbounds pointer-IV loop with `< end` exit

Open
#204,070 1 comment 0 reactions 1 assignee Claimed by @sreedivyakottilingal View on GitHub
llvm:SCEV missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

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 does 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

SCEV dump: https://llvm.godbolt.org/z/scjYozr9x

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.