<table border="1" cellspacing="0" cellpadding="8">
    <tr>
        <th>Issue</th>
        <td>
            <a href=https://github.com/llvm/llvm-project/issues/117318>117318</a>
        </td>
    </tr>

    <tr>
        <th>Summary</th>
        <td>
            [LSR][SCEV] Increses register spilling in 503.bwaves_r (SPEC CPU 2017)
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            loopoptim,
            performance,
            llvm:SCEV
      </td>
    </tr>

    <tr>
      <th>Assignees</th>
      <td>
      </td>
    </tr>

    <tr>
      <th>Reporter</th>
      <td>
          yus3710-fj
      </td>
    </tr>
</table>

<pre>
    This issue became apparent with #110063.

LSR increses register spilling, causing a performance regression on 503.bwaves_r in SPEC2017. The regression is eliminated when the option `-disable-lsr` is enabled. This looks similar to #60325, but the root cause may differ.

Minimal reproducer: https://godbolt.org/z/Y46xsvjK8
The code above shows the state before the patch, and the code below shows the state after the patch. (Please note that the patch is only related to the frontend.) Register spilling occurs only after the patch. The difference between the two IRs is as follows:

```diff
35,36c35,36
<   %21 = srem i32 %20, %9
< %22 = add i32 %21, 1
---
>   %21 = urem i32 %20, %9
>   %22 = add nuw i32 %21, 1
61,62c61,62
<   %40 = srem i32 %39, %8
<   %41 = add i32 %40, 1
---
>   %40 = urem i32 %39, %8
>   %41 = add nuw i32 %40, 1
```

FYI: The original Fortran code of the reproducer is the following.

```fortran
function repro(x,nb,nx,ny)
  implicit none
  integer nb,nx,ny,i,j,m,l,im1,ip1,jm1,jp1

  real(8) x(nb,nx,ny),repro

  repro = 0.0
  do j=1,ny
    jm1 = mod(j-2,ny) + 1
    jp1 = mod(j,ny) + 1
    do i=1,nx
      im1 = mod(i-2,nx) + 1
      ip1 = mod(i,nx) + 1
      do l=1,nb
        ! added "llvm.loop.unroll.disable" metadata manually
        do m=1,nb
 repro = repro &
            + x(m,ip1,j) + x(m,i,jp1) + x(m,i,j) + x(m,im1,j) + x(m,i,jm1) 
        end do
      end do
    end do
  end do

end function
```

---

I think there are two possible causes for this issue. Perhaps, this issue would be resolved by either of them. (I'm not familiar with LSR pass, so any comments are welcome.)

One is about the baseline cost. The baseline cost seems to be calculated based on Formulae that consume more registers than original code. For example, Formula correspoing to the address of `x(m,i,j)` is `reg({{{%0,+,(8 * (zext i32 (0 smax %5) to i64) * (zext i32 (0 smax %8) to i64))}<%19>,+,(8 * (zext i32 (0 smax %5) to i64))<nuw><nsw>}<%38>,+,8}<%57>)` in the beginning. However, Formula reflecting the original code strictly would be `reg(%0) + 8*reg({0,+,((zext i32 (0 smax %5) to i64) * (zext i32 (0 smax %8) to i64))}<%19>) + 8*reg({0,+,(zext i32 (0 smax %5) to i64)}<%38>) + 8*reg({0,+,1}<nuw><nsw><%57>)`. (If I make mistakes, please correct me.) The baseline cost is calculated using the former. This leads to optimizations that increase register spilling being preferentially selected.

The other is related to the analysis for `SCEVUDivExpr`. `urem %a, %b` is interpreted as `(add (mul -1, (mul (udiv %a, %b), %b), %a)` by SCEV. On the other hand, `srem` and `sdiv` are ignored by SCEV. SCEV which have `udiv` operations aren't optimized considering zero division. The following is the debug message.

```
After generating reuse formulae:
LSR is examining the following uses:
 :
  LSR Use: Kind=Address of double in addrspace(0), Offsets={0}, widest fixup type: ptr
    reg({{((8 * (zext i32 (0 smax %5) to i64) * (zext i32 (0 smax %8) to i64) * (-1 + (sext i32 ((-1 * ({1,+,1}<%19> /u %9) * %9) + {2,+,1}<%19>) to i64))<nsw>) + %0),+,(8 * (zext i32 (0 smax %5) to i64))<nuw><nsw>}<%38>,+,8}<%57>)
  LSR Use: Kind=Address of double in addrspace(0), Offsets={0}, widest fixup type: ptr
    reg({((8 * (zext i32 (0 smax %5) to i64) * (-1 + (sext i32 ((-1 * ({1,+,1}<%38> /u %8) * %8) + {2,+,1}<%38>) to i64))<nsw>) + {%0,+,(8 * (zext i32 (0 smax %5) to i64) * (zext i32 (0 smax %8) to i64))}<%19>),+,8}<nw><%57>)
```

Translating Formulae is necessary to find other Formulae which can save the number of registers, but it doesn't work.
Actually, it is obvious that zero division never happens in this case. When I tried removing the check below experimentally, the problematic optimization was improved.

https://github.com/llvm/llvm-project/blob/dde9477d8c0b85d445f10b08b0120f3d361cb77f/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp#L2332-L2337

</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJzMWNtu4zjSfhrmphBDonyQL3KROAn-YObHNLqndzFXC0os2UxTpEBSPvTTL4qUfEo6s9vA7ixg0FKpWCTr8FUVhfdqbRDv2OyBzR5vRB821t0del8s8uy2eb2prDzc_b5RHpT3PUKFtWgRRNcJhybAToUNMF7keZbNiwnLHll2n8Zfv3wGZWqHHj04XCsf0IHvlNbKrBlfQS16r8waBHToGutaYWokVofeK2vAGphlxaTaiS36fzhQBr58elrxLF9M4PfNBa_ygFq1yoiAEnYbNBA2CLYL9JXNs1upvKg03mrv2DyLEwwRJMlSHrS13zx41SotHARL55pnBZ_RXqs-RHnO2hA3jtCKA0jVNOguzv3_yqhWaHDYOSv7Gh0r7mETQudZcc_4M-PPaysrq8PEujXjz98Zf_5jOt_77esvZRJCh6utRBCV3SL4jd35uL4PIpAZGuswEjoR6g3tUBgZCXFahdru3kwTDZngOGsCjJefNAqPYGwgeSKcPpOGrNEHcKijUoONHxtnTUAjJ4wv4fO1YcHWde-GmW8WpHMlnSHZusKww8FSYWfh5TM5GggPjdXa7qLGznTL5ln6kYxEKsg8xbwe_ge-YgUAjM94Dqx4BO-wBVXwSMpIW4zPlideIvPIKaQ8MubEmCeu29vbkf3pQnT_oeiR9yTc9Lt3F5jTy5zXw__VOabZm3MUy2Gx8po3vz7JNPvwJIPw_kPhT2-En53kYoGjkc4t9_zHC4UB2d86tVZGaHi2LjhhksfaJsXXMWrIEaK7RU9QZj151xOaJCRRm97UMd6jGMbLPeMrU9EQnw6MD6YBUG2nVa0CGGvwSDQB1-jgcs5KMb56ZXzVMr7S9N6SlVRH42t8fu3y8-0BOBSa8bKkINkzXl7vgq_SHq8mdc5GBWeTbCRKC6-seMzT1IEI8NomU7RWMl6-3vJRNDD-MNoiMnYXjD9ikxbUuMz-RCZFnc9XaaH9OxIA1MVS6seM0oIeF6vOP5CT5eReKIFxrvW2nWhru0lvnNV6MoA44xxaDEKKIKAVphdaHy7lSAvt9RIn_Q5PfH45KW3gIVqsPZl4PMORPFj8PfIbYvtjEW0ScbEFNBKkPaddUy7fz9_SSJQxEj4IyRMQxPEFwkaZbxRzDkG4hMid9V5VGlPOI1wmPB_rgQl8QrcRnafwP5FhZ3stoaJw9lZvUUJ1AFQkegj0NiafF8YXLeUeaESrtBIuVRRUO3TCR7HegjAHqG3bogk-7myHurYtTo7hnMbfDMb0UdkhW1fCo1aGkqIPKftckMAjtp4SW0Un1HWfMh0xSSo_nq1rey2G1Fhb4_sWoaXkO5Y0hFLCnFCN0GxCEwH3ou3IV1ejHKitc-g7S4lySKdCSqphSC9snl270lCpsHnmcM14yRYPw4_PCHQZf4hjWQLj96TT77gPAy6XGfhW7AmhZ-RowYKaT5MnfsBbXvDSb_HIihXjs3zJiqefXpV-xcr0OxJSrIyPD6PsojyXXR7ps0WkJ02kUqHCtTKGUgL8n93hFt25jh02GusQVXyebmKa8cGpOujDyUVPqo0aTVFaMn5_VPiFnv87Gv6zXfxL6r7S7Icy88R9bZxrC6SobeAFWvENoVU-iG8Y47RLhWT08DpAis53Qk7580hLHUDK865FN9biKGSMS6rfW_VdEJb5FIWxqaCl3jQVUCGNncNYYAZFWQE8kjugvKgfYiES8Uj56wJXGKEPXiWwY_Psy-rpb18f1fZp37mkg3kWiyXGZ2Kok6ohUKmAcJ1DEidi3DJeUrVEcd1ruM3ThPjCeNlLtb2Uw5dvH8Xg_9UBaDMT-G3obuIJNsLIyDjPqEAkRmoG6FWqbXx1CGptrEtInGTQCLuNqjewEdsYCP3Abzt0g8qpz2N8EUZLoIwwqCQ60vV3dBak2ipqwhLCHgu2sYKTWPVraNF7scb3q7j0eh_bhTWauLpZg0NqtJoBhI_NQGwtfcRXZU7-My5LierIC6enmFa-epIDvygjWfF4fwJfaXvKc8pERPadqJGCazDCb03jMXhWPMawWTwScack-gCN2vcdhEMXJXfBnVL1BWhH8PiP4fTIe5vHOGe89Gezxg-RhS0e8uvIH7EHGH_uUw9zlDk-PwBbPPAfzXwP6xOKjJMTwP5V-eN_wAl-3gN-3qpRL0erlmdWLf_Eqse88bFV_9paZHltcvNO4vpxEfy7E8brhDbHYk95MFgTXrkDLd4oIwesPfIk4KyFAU_gSQhk-rZKBe6xNhyvjlQAadEnJN1Z922Awfs6pNaFr4hHebDVVtl-SHUX6AqGKh3YiK5D41MtFJOpxwn8fYMGXiA4hRIctnY74mK9wfrbcCGE-w6dojp6XDTezThbaWxFUPVFvoWd8NQmO7u9yp5Xt1kqbPpqUtuW8Wfq2Ia_287ZV6wD48-VthXjz1LicrpYyLLOqnImp9NZk2dVVlZZzrOmkMU8r6vFojmTo2hetBKlAc_489egNP1_qYUW7mlrdU-7fdp3wkh0k7rrGC9-5UXBb2lcpD3fyLtCLouluMG7fFFwvpjNl_xmc7espKh5vSiaIpOiFrJezORcNHIq6nJeVjfqjmd8muec5_k0L_hkOudzUde8wgbFMp-yaYatUHoS21Xr1jexDbrL80WRlzdaVKh9vGTlnJrZqGTGU8zxs8vPIy2evrinFE202eONu4sqrfq1Z9NMKx_8abmggo63uL9--cxmj2z2EGfOHuHlhzew5EAXt6uMl18-Pa1g9ekr8CxfML686Z2--7eNHQ9PFhrOv73j_wwAAP__qjlvvQ">