llvm / llvm/llvm-project

Missed redundant load elimination across blocks: `getelementptr [8 x i8], ptr %2, i64 %0` vs. `getelementptr i8, ptr %2, i64 (shl i64 %0, 3)`

Open
#189,326 1 comment 0 reactions 0 assignees View on GitHub
llvm:optimizations missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

The following reduced IR is derived from https://github.com/ruby/ruby/blob/3379c7efbdc34b7936f322a6bc2de4834c8c65fc/ext/-test-/memory_view/memory_view.c#L263

https://godbolt.org/z/cqbYqWfnP
alive2: https://alive2.llvm.org/ce/z/pxn7S3

In the reduced IR, the load from `%scevgep` reads the same location just written by `store i64 0, ptr %3`, since both `%scevgep` and `%3` denote `%2 + 8 * %0`. Therefore `%load_initial` is always 0, and the later store can be simplified to `store i64 0, ptr %gep, align 8`.

```llvm
define noundef i1 @mdview_get_memory_view(i64 %0) local_unnamed_addr {
%2 = tail call ptr @ruby_xmalloc2()
%3 = getelementptr [8 x i8], ptr %2, i64 %0
store i64 0, ptr %3, align 8
%4 = icmp sgt i64 %0, 0
br i1 %4, label %.lr.ph.preheader, label %._crit_edge

.lr.ph.preheader:
%5 = shl i64 %0, 3
%scevgep = getelementptr i8, ptr %2, i64 %5
%load_initial = load i64, ptr %scevgep, align 8
%invariant.gep = getelementptr i8, ptr %2, i64 -8
%gep = getelementptr [8 x i8], ptr %invariant.gep, i64 %0
store i64 %load_initial, ptr %gep, align 8
br label %._crit_edge

._crit_edge:
ret i1 false
}
```

Expected:
```llvm
define noundef i1 @tgt(i64 %0) local_unnamed_addr {
%2 = tail call ptr @ruby_xmalloc2()
%3 = getelementptr [8 x i8], ptr %2, i64 %0
store i64 0, ptr %3, align 8
%4 = icmp sgt i64 %0, 0
br i1 %4, label %.lr.ph.preheader, label %._crit_edge

.lr.ph.preheader:
%invariant.gep = getelementptr i8, ptr %2, i64 -8
%gep = getelementptr [8 x i8], ptr %invariant.gep, i64 %0
store i64 0, ptr %gep, align 8
br label %._crit_edge

._crit_edge:
ret i1 false
}
```

Contributor guide

Open the contributing guide

Research direction

Reproduce the reduced IR in the linked Godbolt example and validate the equivalence with the Alive2 link. Trace the LLVM optimization pass responsible for redundant load elimination across blocks, then add coverage for this IR pattern; done means the load is eliminated and the later store uses value 0 as shown in the expected IR.

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
Clearly specified
Newbie friendliness
55/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.