llvm / llvm/llvm-project

Missed reassociation enabling reuse of previously computed values

Open
#191,341 2 comments 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/casadi/casadi/blob/1110ce/external_packages/casadi-sundials/sundials/sundials_direct.c#L32 and https://github.com/HDFGroup/hdf5/blob/d35c31/src/H5HFsection.c#L2204.

Godbolt: https://godbolt.org/z/W8eK45bj9
alive2 proof: https://alive2.llvm.org/ce/z/tsaFxY

In the following code, the first function misses a reassociation opportunity that could reuse `%4 = shl i8 %1, 1` and the second function misses a reassociation opportunity that could reuse `%4 = add i32 %2, 1`.

```llvm
define i8 @newDenseMat(i8 %0, i8 %1, ptr %2) {
%4 = shl i8 %1, 1
%5 = shl i8 %0, 1
%6 = mul i8 %5, %1
store i8 %6, ptr %2, align 8
ret i8 %4
}
define i8 @tgt1(i8 %0, i8 %1, ptr %2) {
%4 = shl i8 %1, 1
%5 = mul i8 %0, %4
store i8 %5, ptr %2, align 8
ret i8 %4
}

define noundef i32 @H5HF__sect_indirect_init_rows(ptr %0, i32 %1, i32 %2) {
%4 = add i32 %2, 1
store i32 %4, ptr %0, align 8
%reass.sub = sub i32 %2, %1
%5 = add i32 %reass.sub, 1
ret i32 %5
}
define noundef i32 @tgt2(ptr %0, i32 %1, i32 %2) {
%4 = add i32 %2, 1
store i32 %4, ptr %0, align 8
%5 = sub i32 %4, %1
ret i32 %5
}
```

Contributor guide

Open the contributing guide

Research direction

Start with the reduced IR in the linked Godbolt example and validate its equivalence using the linked Alive2 proof. Then trace LLVM's reassociation handling for @newDenseMat and @H5HF__sect_indirect_init_rows, using the linked CasADi and HDF5 source locations as motivating cases. Done means the missed reuse is handled without changing the shown semantics and is covered by an LLVM regression test.

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.