llvm / llvm/llvm-project

Optimization with a branch that runs only in the first iteration of loop

Open
#191,617 2 comments 0 reactions 0 assignees View on GitHub
loopoptim missed-optimization
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.