llvm / llvm/llvm-project

[InstCombine] Range check comparing alloca with non-aliasing ptr not eliminated

Open
#210,650 5 comments 0 reactions 0 assignees View on GitHub
llvm:instcombine missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

```llvm
define i1 @src(ptr %base, i64 %len) {
%2 = alloca i64, align 8
%12 = getelementptr inbounds i8, ptr %base, i64 %len
%13 = icmp uge ptr %2, %base
%14 = icmp ult ptr %2, %12
%15 = and i1 %13, %14
ret i1 %15
}

define i1 @tgt(ptr %base, i64 %len) {
ret i1 false
}
```

https://alive2.llvm.org/ce/z/u_8tT7

This pattern occurs very often with SmallVector, which on push_back of large (>16B) structs first checks whether the reference is inside the vector's storage, and is never eliminated. Probably something that InstCombine (or maybe even InstSimplify?) should eliminate.

Contributor guide

Open the contributing guide

Research direction

Start with the InstCombine code path for pointer range comparisons and compare it with the possible InstSimplify path. Reproduce the LLVM IR example from the issue and use the linked Alive2 result as the behavioral reference; done means the check involving the alloca and non-aliasing pointer range is eliminated to false.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.