llvm / llvm/llvm-project

[Missed Optimization] Idiom recognition for contiguous interval membership tests

Open
#216,391 0 comments 0 reactions 0 assignees View on GitHub
loopoptim missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

### Description
LLVM misses an idiom recognition opportunity to optimize membership tests over contiguous intervals.

Due to C not allowing relational comparisons between unrelated pointer, strictly standard-conforming tests for whether whether a pointer lies within a contiguous memory region must pointwise compare against every single memory location within that region in a loop. C++11 is more accommodating by offering global pointer comparisons via `std::less`, allowing for a double relational comparison test instead. However, the most efficient approach relies on implementation-defined behaviour by subtracting the unsigned integer addresses of the pointer and the memory region, and comparing the result against the region's size.

Unfortunately, LLVM fails to optimize both pointwise and double relational comparisons into single relational comparisons. In some cases, it fails to eliminate the loop of the pointwise comparison altogether, such as in the example for the pointwise past-the-end-excluding region test.

### Reproducer
A minimal reproducible example can be found on Compiler Explorer: https://godbolt.org/z/f7scjvdPY
A more extensive example suite containing past-the-end-including tests and several different pointwise implementation approaches is available here: https://godbolt.org/z/sr79GncM3

```c
bool in_bounds_exclusive_pointwise(void *arr, size_t size, void *ptr) {
while (size > 0) {
if (ptr == (unsigned char *)arr + --size) {
return true;
}
}
return false;
}

bool in_bounds_exclusive_comparisons(void *arr, size_t size, void *ptr) {
return (unsigned char *)ptr >= (unsigned char *)arr && (unsigned char *)ptr < (unsigned char *)arr + size;
}

bool in_bounds_exclusive_uintptr_t(void *arr, size_t size, void *ptr) {
return (uintptr_t)ptr - (uintptr_t)arr < size;
}
```

### Observed Assembler (Clang -Os)
The loop survives scalar optimization passes intact:

```asm
in_bounds_exclusive_pointwise:
dec rdi
.LBB3_1:
mov rax, rsi
add rsi, -1
jae .LBB3_3
lea rcx, [rdi + rax]
cmp rcx, rdx
jne .LBB3_1
.LBB3_3:
test rax, rax
setne al
ret

in_bounds_exclusive_comparisons:
cmp rdx, rdi
setae cl
add rsi, rdi
cmp rdx, rsi
setb al
and al, cl
ret

in_bounds_exclusive_uintptr_t:
sub rdx, rdi
cmp rdx, rsi
setb al
ret
```

### Expected Output
In all cases, the code should be lowered to the corresponding `uintptr_t` version.

### Additional Context
- This behavior is consistent across all Clang versions and target architectures available on compiler explorer, though the exact code generation and optimisation deficiencies vary across optimisation levels and concrete pointwise implementations.
- While this report focuses on pointers due to their standard-imposed restrictions, the same optimisation could likewise be applied to contiguous interval membership tests for other types, such as integers or even floating point numbers.
- Since this pattern represents the only strictly standard-compliant ways to test contiguous interval membership in modern C and C++, respectively, optimizing this idiom would significantly benefit safety-conscious, standard-conforming codebases.

Contributor guide

Open the contributing guide

Research direction

Start with the minimal Compiler Explorer reproducer and compile the three membership-test functions with Clang at -Os, then compare the generated assembly with the uintptr_t case. Check the extended Compiler Explorer suite for past-the-end and alternative pointwise implementations. Done means the pointwise and double-comparison forms lower to equivalent single relational code across the reported cases.

Written by the indexing model from the issue text.

Assessment

Tech stack
c, cpp
Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.