cmd/compile: early loop rotation

[Jorropo]

go version go1.26-devel_e7c0b74a97 Tue Jan 6 20:29:01 2026 +0100 linux/amd64

We do loop rotation extremely late.
Consider this loop:

 for range c {
  a()
 }

We will compile to this (pseudo-code):

 i := c
goto check
loop:
 a()
 i--
check:
 if i != 0 { goto loop }

The "classical" form would be*:

 if c == 0 { goto skip }
 i := c
loop:
 a()
 i--
 if i != 0 { goto loop }
skip:

*reversing iteration order of loops isn't classic, but it's not what I want to point out.

[Jorropo]

I think the best bet is to do that inside prove for two reasons:

1. we should do early loop rotation before prove because many loops would be proven to run at least once, this allows us to skip the check before the loop

• however if we do it before would have to update loopbce to match rotated loops

2. prove already spends CPU cycles to figure out where loops are, we can keep reuse this info

A bit of work will be needed to update the induction variables tracking to the rotated form but not in loopbce.

[Jorropo]

The classical form uses more space in the jump prediction buffer since there are two conditional jumps rather than one, which can cause a regression if this is causing an other loop to be miss-speculated that wouldn't otherwise have been.

However if this is not an issue, having two cases helps since there often is a discontinuity around 0 to 1 n iterations,
in other words somewhat common loops either run not at all, or a couple of times or more. But very rarely ~1 time.

Using two conditional jump prediction entries allows the first one to predict « will we even loop ? » while the second one exclusively asks itself « how many iterations are we doing ? ».

[gabyhelp]

Related Issues

• cmd/compile: range loop over []byte, []int can avoid base pointer increments #15809 (closed)
• cmd/compile: loads/constants not lifted out of loop #15808
• cmd/compile: loop optimization #24240
• cmd/compile: for loop prevents inlining #22636 (closed)
• cmd/compile: looprotate picking wrong jump target #20355 (closed)
• cmd/compile/internal: loop opt #44384 (closed)

Related Code Changes

• cmd/compile: loop rotate for bottom testing
• cmd/compile: experiment w/ loop rotation as part of layout
• cmd/compile: hoist induction variable
• cmd/compile: don't produce a past-the-end pointer in range loops

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[gopherbot]

Change https://go.dev/cl/736022 mentions this issue: cmd/compile: rotate loops early (in prove)

[randall77]

I'm not convinced this is worth doing. The benefits seem pretty minor, and the cost is both branch predictor entries (which you mention) and code is probably larger as well.

[y1yang0]

However if this is not an issue, having two cases helps since there often is a discontinuity around 0 to 1 n iterations,
in other words somewhat common loops either run not at all, or a couple of times or more. But very rarely ~1 time.

Using two conditional jump prediction entries allows the first one to predict « will we even loop ? » while the second one exclusively asks itself « how many iterations are we doing ? »

To transform a loop into the "classic" form shown below:

      entry
        │
        │
        ▼
    loop header◄──┐
        │         │
        │         │
        ▼         │
    loop body     │
        │         │
        │         │
        ▼         │
    loop latch────┘
        │
        │
        ▼
    loop exit

We need to handle the case where the loop executes zero or one time, which typically requires adding an if guard(i.e.if c == 0 { goto skip } you mentioned)

         entry
           │
           │
           ▼
    ┌──loop guard
    │      │
    │      │
    │      ▼
    |  loop land 
    │      │
    │      │
    │      ▼
    │  loop header◄──┐
    │      │         │
    │      │         │
    │      ▼         │
    │  loop body     │
    │      │         │
    │      │         │
    │      ▼         │
    │  loop latch────┘
    │      │
    │      │
    │      ▼
    └─► loop exit

But, implementing this if-guard and the Loop Rotation transform itself is not as straightforward as it might seem (as discussed in issue #63670), the main problem is fixing up all the data dependencies.

To get loop rotation working, we'd almost certainly have to implement LCSSA first(ensures that all values defined inside the loop are only used within loop), and that's a huge amount of work on its own.

On top of that, the real-world performance of loop rotation is tightly coupled with the block layout algorithm. From my testing, a pure loop rotation gives minor gains.

So, to put it another way: we need to write a ton of code (at least LCSSA + loop rotation) just for the prep work, and it might not even make things faster.

But without that prep work, we're blocked from doing loop opts like LICM or loop unrolling.

This is an unfortunate dilemma :( , but still looking forward to seeing loop opts in the Go compiler in the future.