[Bug rtl-optimization/115344] New: Missing loop counter reversal

["cmuellner at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=115344

            Bug ID: 115344
           Summary: Missing loop counter reversal
           Product: gcc
           Version: 15.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: cmuellner at gcc dot gnu.org
  Target Milestone: ---

Let's take a simple for-loop with an unknown bound:

void bar ();
void foo1 (int n) {
    for (int i = 0; i < n; i++) {
        bar ();
    }
}

We see that two variables are in the program,
but we could eliminate the loop variable `i` as follows:

void bar ();
void foo2 (int n) {
    while (n) {
        bar ();
        n--;
    }
}

Optimizing the loop as above has the following benefits:
- No need for a register for the loop variable `i`
- No need for an additional slot in the stack frame
- No need for instructions to save/restore the loop variable register in the
prologue/epilogue
- No need for an initialization instruction for the loop variable `i` (to zero)

LLVM does this transformation on (at least) x86-64,  RISC-V (rv64gc),
and AArch64 with -O3, but GCC does not.
Tests have been done with trunk and older GCC releases (I've tested down to GCC
4.4).

Related bug tickets:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=22041 (open - with uses of the
loop counter as an array index)
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=31238 (closed - fixed for GCC
4.5.0)
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=40886 (closed - fixed for GCC
4.5.0)

GCC AArch64 -O3:
foo1:
        cmp     w0, 0
        ble     .L6
        stp     x29, x30, [sp, -32]!
        mov     x29, sp
        stp     x19, x20, [sp, 16]
        mov     w20, w0
        mov     w19, 0
.L3:
        add     w19, w19, 1
        bl      bar
        cmp     w20, w19
        bne     .L3
        ldp     x19, x20, [sp, 16]
        ldp     x29, x30, [sp], 32
        ret
.L6:
        ret
foo2:
        cbz     w0, .L18
        stp     x29, x30, [sp, -32]!
        mov     x29, sp
        str     x19, [sp, 16]
        mov     w19, w0
.L12:
        bl      bar
        subs    w19, w19, #1
        bne     .L12
        ldr     x19, [sp, 16]
        ldp     x29, x30, [sp], 32
        ret
.L18:
        ret

LLVM AArch64 -O3:
foo1:                                   // @foo1
        cmp     w0, #1
        b.lt    .LBB0_4
        stp     x29, x30, [sp, #-32]!           // 16-byte Folded Spill
        str     x19, [sp, #16]                  // 8-byte Folded Spill
        mov     x29, sp
        mov     w19, w0
.LBB0_2:                                // =>This Inner Loop Header: Depth=1
        bl      bar
        subs    w19, w19, #1
        b.ne    .LBB0_2
        ldr     x19, [sp, #16]                  // 8-byte Folded Reload
        ldp     x29, x30, [sp], #32             // 16-byte Folded Reload
.LBB0_4:
        ret
foo2:                                   // @foo2
        cbz     w0, .LBB1_4
        stp     x29, x30, [sp, #-32]!           // 16-byte Folded Spill
        str     x19, [sp, #16]                  // 8-byte Folded Spill
        mov     x29, sp
        mov     w19, w0
.LBB1_2:                                // =>This Inner Loop Header: Depth=1
        bl      bar
        subs    w19, w19, #1
        b.ne    .LBB1_2
        ldr     x19, [sp, #16]                  // 8-byte Folded Reload
        ldp     x29, x30, [sp], #32             // 16-byte Folded Reload
.LBB1_4:
        ret

GCC RISC-V -O3 -march=rv64gc:
foo1:
        ble     a0,zero,.L6
        addi    sp,sp,-32
        sd      s0,16(sp)
        sd      s1,8(sp)
        sd      ra,24(sp)
        mv      s1,a0
        li      s0,0
.L3:
        addiw   s0,s0,1
        call    bar
        bne     s1,s0,.L3
        ld      ra,24(sp)
        ld      s0,16(sp)
        ld      s1,8(sp)
        addi    sp,sp,32
        jr      ra
.L6:
        ret
foo2:
        beq     a0,zero,.L18
        addi    sp,sp,-16
        sd      s0,0(sp)
        sd      ra,8(sp)
        mv      s0,a0
.L12:
        addiw   s0,s0,-1
        call    bar
        bne     s0,zero,.L12
        ld      ra,8(sp)
        ld      s0,0(sp)
        addi    sp,sp,16
        jr      ra
.L18:
        ret

LLVM RISC-V -O3 -march=rv64gc
foo1:                                   # @foo1
        blez    a0, .LBB0_4
        addi    sp, sp, -16
        sd      ra, 8(sp)                       # 8-byte Folded Spill
        sd      s0, 0(sp)                       # 8-byte Folded Spill
        mv      s0, a0
.LBB0_2:                                # =>This Inner Loop Header: Depth=1
        call    bar
        addiw   s0, s0, -1
        bnez    s0, .LBB0_2
        ld      ra, 8(sp)                       # 8-byte Folded Reload
        ld      s0, 0(sp)                       # 8-byte Folded Reload
        addi    sp, sp, 16
.LBB0_4:
        ret
foo2:                                   # @foo2
        beqz    a0, .LBB1_4
        addi    sp, sp, -16
        sd      ra, 8(sp)                       # 8-byte Folded Spill
        sd      s0, 0(sp)                       # 8-byte Folded Spill
        mv      s0, a0
.LBB1_2:                                # =>This Inner Loop Header: Depth=1
        call    bar
        addiw   s0, s0, -1
        bnez    s0, .LBB1_2
        ld      ra, 8(sp)                       # 8-byte Folded Reload
        ld      s0, 0(sp)                       # 8-byte Folded Reload
        addi    sp, sp, 16
.LBB1_4:
        ret

GCC x86-64 -O3:
foo1:
        testl   %edi, %edi
        jle     .L6
        pushq   %rbp
        movl    %edi, %ebp
        pushq   %rbx
        xorl    %ebx, %ebx
        subq    $8, %rsp
.L3:
        xorl    %eax, %eax
        addl    $1, %ebx
        call    bar
        cmpl    %ebx, %ebp
        jne     .L3
        addq    $8, %rsp
        popq    %rbx
        popq    %rbp
        ret
.L6:
        ret
foo2:
        testl   %edi, %edi
        je      .L18
        pushq   %rbx
        movl    %edi, %ebx
.L12:
        xorl    %eax, %eax
        call    bar
        subl    $1, %ebx
        jne     .L12
        popq    %rbx
        ret

LLVM x86-64 -O3:
foo1:                                   # @foo1
        testl   %edi, %edi
        jle     .LBB0_4
        pushq   %rbx
        movl    %edi, %ebx
.LBB0_2:                                # =>This Inner Loop Header: Depth=1
        xorl    %eax, %eax
        callq   bar@PLT
        decl    %ebx
        jne     .LBB0_2
        popq    %rbx
.LBB0_4:
        retq
foo2:                                   # @foo2
        testl   %edi, %edi
        je      .LBB1_4
        pushq   %rbx
        movl    %edi, %ebx
.LBB1_2:                                # =>This Inner Loop Header: Depth=1
        xorl    %eax, %eax
        callq   bar@PLT
        decl    %ebx
        jne     .LBB1_2
        popq    %rbx
.LBB1_4:
        retq