Optimization with a branch that runs only in the first iteration of loop
- Dominant language
- LLVM
- Stars
- 40.5k
- Forks
- 18.7k
- PR merge metrics
- PR metrics pending
Description
This is an optimization feature request.
Compiler Explorer link:
https://godbolt.org/z/MYf6x1ejE
```c
#include
#include
#include
void func1(char *str, size_t length) {
for (size_t i = length - 1; i != (size_t)-1; i--) {
char ch = str[i];
if (i == length - 1) {
ch &= ~('a' - 'A');
}
putchar(ch);
}
}
void func2a(char *str, size_t length) {
bool first = true;
for (size_t i = length - 1; i != (size_t)-1; i--) {
char ch = str[i];
if (first) {
ch &= ~('a' - 'A');
first = false;
}
putchar(ch);
}
}
void func2b(char *str, size_t length) {
bool following = false;
for (size_t i = length - 1; i != (size_t)-1; i--) {
char ch = str[i];
if (!following) {
ch &= ~('a' - 'A');
following = true;
}
putchar(ch);
}
}
void func3(char *str, size_t length) {
char mask = ~('a' - 'A');
for (size_t i = length - 1; i != (size_t)-1; i--) {
char ch = str[i];
ch &= mask;
mask = ~0;
putchar(ch);
}
}
```
`func1` contains a loop that iterates from `(length - 1)` to 0, and one conditional that's obvious that it would only execute once, in the first iteration of the loop.
`func1` can ideally be optimized to `func2a` or `func2b` (both are equivalent).
`func3` is a more advanced optimization: For operations such as add, sub, bitwise operations etc. the flag variable and the conditional can be replaced with something simpler.
Note: I also made a similar feature request to GCC:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=124861
Contributor guide
Research direction
Start with the Compiler Explorer example and compare the generated code for func1, func2a, func2b, and func3; the linked GCC report provides additional context. Then locate the LLVM optimization area responsible for loop branches and establish regression coverage for the requested first-iteration and flag-elimination transformations; done means the applicable patterns produce equivalent optimized code without changing behavior.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- c
- Domain
- compilers, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Mostly clear
- Newbie friendliness
- 35/100