[Bug tree-optimization/113426] New: Missed optimization of loop invariant elimination

[Bug tree-optimization/113426] New: Missed optimization of loop invariant elimination

[652023330028 at smail dot nju.edu.cn]

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

            Bug ID: 113426
           Summary: Missed optimization of loop invariant elimination
           Product: gcc
           Version: 14.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: 652023330028 at smail dot nju.edu.cn
  Target Milestone: ---

Hello, we noticed that maybe there is a missed optimization for loop invariant
elimination.

Loop invariant: a+b.

https://godbolt.org/z/Ebzd3dMPW

int a, b, c;
int n;
int w;
void func(){
    for(int i=0;i<100;i++){
        c=n;
        a+=w;
        b-=w;
        n=a+b;
    }
}

GCC -O3:
func():
        mov     r9d, DWORD PTR a[rip]
        mov     r10d, DWORD PTR b[rip]
        mov     eax, 100
        mov     edi, DWORD PTR n[rip]
        mov     esi, DWORD PTR w[rip]
        mov     ecx, r10d
        mov     edx, r9d
.L2:
        mov     r8d, edi
        lea     edi, [rcx+rdx]  
        sub     ecx, esi
        add     edx, esi
        sub     eax, 1
        jne     .L2
        imul    edx, esi, -99
        lea     eax, [rsi+r9]
        add     r9d, r10d
        mov     DWORD PTR c[rip], r8d
        mov     DWORD PTR n[rip], r9d
        sub     eax, edx
        mov     DWORD PTR a[rip], eax
        mov     eax, r10d
        sub     eax, esi
        add     eax, edx
        mov     DWORD PTR b[rip], eax
        ret

Expected code (Clang):
func():                               # @func()
        mov     eax, dword ptr [rip + a]
        mov     ecx, dword ptr [rip + b]
        lea     edx, [rcx + rax]
        imul    esi, dword ptr [rip + w], 100
        add     eax, esi
        sub     ecx, esi
        mov     dword ptr [rip + n], edx
        mov     dword ptr [rip + c], edx
        mov     dword ptr [rip + a], eax
        mov     dword ptr [rip + b], ecx
        ret

We analyze and find that in the optimization results of GCC, the calculation of
n is actually outside the loop (add r9d, r10d; mov DWORD PTR n[rip], r9d). 
However, because of the effect of c=n, a+b is calculated once each time through
the loop.
Hope this analysis will help with this issue.

Thank you very much for your time and effort! We look forward to hearing from
you.

[Bug tree-optimization/113426] Missing scalar evolution replacement sometimes

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|Missed optimization of loop |Missing scalar evolution
                   |invariant elimination       |replacement sometimes
           Severity|normal                      |enhancement

[Bug tree-optimization/113426] Missing scalar evolution replacement sometimes

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2024-01-17
     Ever confirmed|0                           |1

--- Comment #1 from Richard Biener <rguenth at gcc dot gnu.org> ---
We cannot analyze the evolution of 'n', so it's computation prevails inside the
loop.

  <bb 3> [local count: 1063004408]:
  # i_18 = PHI <i_15(5), 0(2)>
  # n_lsm.10_20 = PHI <_7(5), n_lsm.10_17(2)>
  # a_lsm.12_9 = PHI <_4(5), a_lsm.12_22(2)>
  # b_lsm.13_8 = PHI <_6(5), b_lsm.13_23(2)>
  _4 = w.2_3 + a_lsm.12_9;
  _6 = b_lsm.13_8 - w.2_3;
  _7 = b_lsm.13_8 + a_lsm.12_9;
  i_15 = i_18 + 1;
  if (i_15 != 100)
    goto <bb 5>; [98.99%]
  else
    goto <bb 4>; [1.01%]

  <bb 5> [local count: 1052266995]:
  goto <bb 3>; [100.00%]

  <bb 4> [local count: 10737416]:
  # n_lsm.10_21 = PHI <n_lsm.10_20(3)>


(analyze_scalar_evolution
  (loop_nb = 1)
  (scalar = _7)
(get_scalar_evolution
  (scalar = _7)
  (scalar_evolution = a_lsm.12_22 + b_lsm.13_23))
) 
(instantiate_scev
  (instantiate_below = 2 -> 3)
  (evolution_loop = 1)
  (chrec = a_lsm.12_22 + b_lsm.13_23)
  (res = a_lsm.12_22 + b_lsm.13_23))
  (evolution_function = scev_not_known))

that's a bit odd (a_lsm.12_22 + b_lsm.13_23 is invariant).