Missed reassociation enabling reuse of previously computed values
- 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
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