llvm / llvm/llvm-project

LLVM does not propagate sign information out of trivial loop

Open
#174,813 16 comments 0 reactions 0 assignees View on GitHub
llvm:analysis missed-optimization
Dominant language
LLVM
Stars
40.5k
Forks
18.7k
PR merge metrics
PR metrics pending

Description

See https://godbolt.org/z/xnrGGvdYK

Consider this code:
```c++
double CompareDistmats(double* distmat1, double* distmat2){
double RMSD = 0.0;
for (int i=0; i<1; i++){
RMSD += (distmat1[i]-distmat2[i]) * (distmat1[i]-distmat2[i]);
}
return std::sqrt(RMSD);
}
```
Ideally the sqrt should become 1 HW instruction. However, due to...history, sqrt needs to set ERRNO if the argument is out of range (smaller than -0.0), therefore LLVM inserts a branch to the library function to handle that case correctly, incurring a performance and code size penalty (left panel on CE).
This is of course redundant if the argument can never be negative, and LLVM already optimizes this away if [[assume]] is used (middle panel on CE).
The compiler can sometimes deduce this non-negativity on its own, for example here if the loop is removed (right panel on CE), but a trivial loop like this is sufficient to break the analysis and result in the branch getting inserted.

LLVM should be able to propagate such non-negativity information out of simple loops like this.

Contributor guide

Open the contributing guide

Research direction

Start with the Compiler Explorer example at https://godbolt.org/z/xnrGGvdYK and compare the generated code for the loop, the [[assume]] variant, and the loop-free variant. Trace the analysis responsible for proving the sqrt argument is non-negative; done means the trivial loop no longer causes the unnecessary errno-handling branch, with the example providing a regression case.

Written by the indexing model from the issue text.

Assessment

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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.