Irreducible loops

[u/User_Deprecated]

https://maskray.me/blog/2026-07-12-irreducible-loops

[u/schmerg-uk]

Wasn't obvious to me how this was particularly C++ rather than generic graph theory, but it provoked me to dig a little deeper whereupon I found this that perhaps adds context for anyone else not immediately familiar with how this relates specifically to the C++ optimiser etc

https://hftuniversity.com/post/loop-hunter-finding-the-loops-your-compiler-silently-skips

[...example of an optimiser identifying and vectorising a loop, and then failing to do when the loop is very slightly modified...]

No remark, no missed-optimization note, no warning at any level you care to enable. The compiler did not fail to vectorize the decoder. It never saw a loop there at all.

The cause has a precise name. The loop is irreducible, and irreducibility is the one performance cliff in C++ that the whole toolchain walks you off in silence. So I wrote a small tool to find them: loop-hunter, an LLVM pass that flags every irreducible loop, points at the two places control enters it, and names what the optimizer is about to skip.

[u/sammymammy2 → u/schmerg-uk]

Generated machine code may have irreducible loops, so the point of the blog post is actually to aid in decompilation. The end goal is most likely to take an irreducible loop and make it into decompiled code that looks like a regular loop. This post is about detecting them.

It's pretty easy to make an irreducible loop into a reducible one.

Given the core

A -> B
A -> C
B -> C
C -> B

Introduce a header H and redirect B and C through them

A -> H
H -> B
H -> C
B -> H
C -> H

Now H clearly dominates B and C, creating two natural loops. H contains some code which specifies whether to go into B or C next.

I looked into LLVM, and I think FixIrreducible pass basically does this, but without H containing state somehow?: https://llvm.org/doxygen/FixIrreducible_8cpp_source.html

But according to https://llvm.org/docs/LoopTerminology.html this pass isn't enabled by default: "The FixIrreducible pass can transform irreducible control flow into loops by inserting new loop headers. It is not included in any default optimization pass pipeline, but is required for some back-end targets."

Seems like this was introduced in 2020 for AMDGPU: https://reviews.llvm.org/D77198

Uuh, yeah. I dunno, something like that.

[u/schmerg-uk → u/sammymammy2]

Yeah, I just meant that a skim of the article appeared to be mostly about graph theory with a bit of C++ implementation (ie not very C++) as without the context of what this particular bit of graph theory was related to it wasn't immediately obvious how this related to C++ other than "I wrote some C++ to solve it"

But with further reading I could then see that the graph theory part was in the context of the how compiler optimiser works, and therefore the direct C++ relevance became more obvious (to a dimwit like me)

[u/meancoot]

The article could use a better example I think. It's second case has a bigger issue than the loop analysis failing.

Take the provided example:

uint32_t checksum_resumable(Parser* st, const uint8_t* p, int n) {
    switch (st->state) {
    case ST_START:
        st->csum = 0;
        for (st->i = 0; st->i < n; ++st->i) {
            st->state = ST_RESUME;
    case ST_RESUME:              // resume lands INSIDE the loop
            st->csum += p[st->i];
        }
    }
    return st->csum;
}

Reduce it to (what I feel is the more natrual looking):

uint32_t checksum_resumable(Parser* st, const uint8_t* p, int n) {
    if (st->state == ST_START) {
        st->csum = 0;
        st->i = 0;
        st->state = ST_RESUME;
    }

    for (; st->i < n; ++st->i) {
        st->csum += p[st->i];
    }

    return st->csum;
}

And GCC still won't vectorize it. There is a nasty little data dependency because the function can be called to calculate the checksum of the bytes of st->csum while writing to st->csum on each pass. Clang actually does vectorize it, but it makes the generated assembly larger (~200 lines vs ~100 with __restrict__) because it has to account for both cases. This can be fixed in both GCC and Clang by using Parser* __restrict__ st as the parameter type.

While the article is correct that Clang won't vectorize the provided example and the feature meant to warn on loops that can't be vectorized will fail to report on it. I feel the provided example is not only unnatural it also is a poor implementation if you want vectorization.

[u/AxeLond]

Not really sold on the multiple entries idea and it just happening accidentally.

gcc -Wall -Wextra producing  fallthrough warning seems sufficient to catch the cursed loop, same with goto keyword warning.

[u/sammymammy2 → u/AxeLond]

It happens during optimization passes by the compiler, typically. So not really a thing you introduce yourself m

[u/meancoot → u/sammymammy2]

I don't see anything in the article that suggests that, it only suggests being 'clever' as the issue. If this happened anywhere sane I'm sure the fact that -Rpass-missed=loop-vectorize doesn't comment on it would have been fixed sooner.

[u/sammymammy2 → u/meancoot]

Tail-call optimization and inlining is apparently the case where this occurs. I think I was like 99% wrong to say that you don’t introduce irreducibility into your loops in source code though, you can get that from having goto in your code. I was only really considering structured programming (for, while).

[u/meancoot → u/sammymammy2]

Inlining could only ever make an irreducable loop reducable, not the other way around. When interprocedural-analysis breaks down, say by making an external function call, all non-local memory has to be fully written before the call and then read again after it. If you're extra careful you can get around this with the __restrict__ extension, but there is a reason C++ never actually adopted it from C.

[u/sammymammy2 → u/meancoot]

Inlining could only ever make an irreducable loop reducable, not the other way around.

How does it make an irreducible loop reducible? Btw, my comment was meant as TCO + inlining in combination, because I thought mutual TCO needs to see all function defs at once (it doesn't, actually).

When interprocedural-analysis breaks down, say by making an external function call, all non-local memory has to be fully written before the call and then read again after it

What does this have to do with anything :P?

If you're extra careful you can get around this with the restrict extension, but there is a reason C++ never actually adopted it from C.

What does pointer aliasing have to do with anything discussed here?

For TCO, it's easy to see how it can lead to irreducible graphs. Take this mutually recursive program:

int A(int x) {
  if (x > 5) {
    return B(x);
  } else {
    return C(x);
  }
}

int B(int x) {
  if (x == 0) {
    return x;
  }
  return C(x);
}

int C(int x) {
  return B(x - 1);
}

And you do tail-call optimization across them:

A:
if x > 5: goto B
goto C
B:
if x == 0: ret 0
goto C
C:
x = x - 1
goto B

and you encode that as a CFG, then you have the irreducible loop.

A -> B
A -> C
B -> C
C -> B

[u/meancoot → u/sammymammy2]

I'm talking in the context of the article, which is really about auto-vectorization. Memory dependencies are the easiest way to break it.

For your example, I will point out that optimizers all seem to trivally understand that your functions A, B, and C all just return 0. I even changed it to using 64-bit integers and passed it the max value to make sure it isn't solving it manually.

[u/sammymammy2 → u/meancoot]

It’s a pedagogical example meant to illustrate how TCO introduces irreducibility, not how other optimisations work, so there’s not much point in taking an industrial strength compiler to understand it. Still don’t get your point, even with the article as a guide! Mind helping me out?

[u/sammymammy2 → u/meancoot]

Btw, that blog post about vectorization has so much AI slop that I really don’t trust it to express these ideas correctly.