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

    <tr>
        <th>Summary</th>
        <td>
            unprofitable SCEV/INDVARS transform
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            backend:ARM,
            backend:X86,
            llvm:optimizations,
            SCEV
      </td>
    </tr>

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

    <tr>
      <th>Reporter</th>
      <td>
          nickdesaulniers
      </td>
    </tr>
</table>

<pre>
    ```llvm
target triple = "armv4t-unknown-linux-gnueabi"

@scpart_scan_partmap_offs = external global i64

define void @scpart_scan_partmap() {
entry:
  br label %while.body.preheader

while.body.preheader:                             ; preds = %entry
  br label %while.body

while.body:                                       ; preds = %while.body, %while.body.preheader
  %add13 = phi i64 [ %add, %while.body ], [ undef, %while.body.preheader ]
  %add = add nsw i64 %add13, 12
  %cmp = icmp slt i64 %add13, 0
  br i1 %cmp, label %while.body, label %while.cond.while.end_crit_edge

while.cond.while.end_crit_edge:                   ; preds = %while.body
  %add.lcssa = phi i64 [ %add13, %while.body ]
  store i64 %add.lcssa, ptr null, align 8
  ret void
}
```
```sh
$ opt -passes=indvars reduced.ll -S
```
produces
```llvm
source_filename = "reduced.ll"
target triple = "armv4t-unknown-linux-gnueabi"

@scpart_scan_partmap_offs = external global i64

define void @scpart_scan_partmap() {
entry:
  br label %while.body.preheader

while.body.preheader:                             ; preds = %entry
  %smax = call i64 @llvm.smax.i64(i64 undef, i64 0)
  %0 = sub i64 %smax, undef
  %umin = call i64 @llvm.umin.i64(i64 %0, i64 1)
  %1 = sub i64 %0, %umin
  %2 = udiv i64 %1, 12
  %3 = add i64 %umin, %2
  %4 = mul i64 %3, 12
  br label %while.body

while.body:                                       ; preds = %while.body, %while.body.preheader
  br i1 false, label %while.body, label %while.cond.while.end_crit_edge

while.cond.while.end_crit_edge:                   ; preds = %while.body
  %5 = add i64 %4, undef
  store i64 %5, ptr null, align 8
  ret void
}

; Function Attrs: nocallback nofree nosync nounwind readnone speculatable willreturn
declare i64 @llvm.smax.i64(i64, i64) #0

; Function Attrs: nocallback nofree nosync nounwind readnone speculatable willreturn
declare i64 @llvm.umin.i64(i64, i64) #0

attributes #0 = { nocallback nofree nosync nounwind readnone speculatable willreturn }
```
unfortunately the `udiv` we got from SCEV is going to be lowered to an relatively expensive libcall to `__aeabi_uldivmod` (32b x86 is also affected, the libcall is `__udivdi3`). So we may have eliminated the loop body, but we replaced it with a relatively expensive libcall.

Forked from https://github.com/ClangBuiltLinux/linux/issues/1635. https://github.com/ClangBuiltLinux/linux/issues/1635#issuecomment-1126412761 has the reduced C code, and demonstrates GCC keeping the tight loop:
```asm
      24: 04 f0 9d a4   ldrge   pc, [sp], #4
      28: 0c 30 93 e2   adds    r3, r3, #12
      2c: 00 20 a2 e2   adc     r2, r2, #0
      30: 01 00 53 e1   cmp     r3, r1
      34: 00 c0 d2 e0   sbcs    r12, r2, r0
      38: fa ff ff ba   blt     0x28 <scpart_scan_partmap+0x28> @ imm = #-24
```

`llvm::rewriteLoopExitValues` in llvm/lib/Transforms/Utils/LoopUtils.cpp tries to replace the loop body regardless of cost if the loop can be deleted.  I'm not sure if we could exclude such transforms if the SCEV contains a udiv larger than the target word size, or if the target doesn't support division `ARMSubTarget::hasDivideInARMMode()`, or something more generic?

See also https://reviews.llvm.org/D9800 / e2538b5639a8ed4756ef134a4a552e4efb295df4,

cc @LebedevRI @fhahn @sjoerdmeijer @wmi-11 @preames @atrick 
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJztV0tv4zYQ_jX2hYghUZIfBx_y2BQLbHvYtIveDEoc2dylSIGk4qS_vjOUbMuJ1wXaAm2BGoIlkfPiPL4ZlVa-rifzpL-0fm4mycMkuQ3CbSGw4FSrgU2yBzbhXLjmOQ83nflm7N7caGW6l5ut6UCUCrd7zuE_T3zVChc2vhJmQ0-NaDe2rn2UBi8BnBGabbUt8abm-ZhdQq0MsGerJLssasKXE75ik8VdzwEmuNdJNvAzVjqmRQka7S72O6VhVuJRZ62DHQgJbqzt4n6GQq78JtkdQ2LpB-cUvQFXtV_W-UearugcCeH310_KaFtImWaRud0p8jmbFHfDxjsJuPcQF5GkMxiRKzoi7ZmeqIXuxu97TYN6kpLyEXHVtJFY0YPX4R11MvKqSgcW2rjk4vfLlTVy1j-CkZvKqbABuYX30fgu5cUIXYvGmStmuvJefMft_RHfO36Q4IN1MPJIL4tY2uCY6bSmZ6HV1rDlgclh5VLpDCdcDNKOZf7m1e-GBZ4z2wZ20wrvwaO9yshn4TwKlF0FqFyzm6eLwlpnicS_2TwBiredq2BT4yGNaI6QcpJ8BJD_oecvQQ---0a8xL1KaN0nTx5DMaOdGR2YL2n5WNb0kuChRkKSKMF35SH7iJdoe6YTYdcoc1kb7Yy0kdCDsvRcWfpWWTJUBYkY0fFI10n1fCBM3-FJdoSegSTK6MWN6fJI13T6QPcGmv6NGN4jYC20h_8KABZvw5G_S6IzkCv-JLj1_2jSY2eqoKxhtyE4T6YbS6lZiuobPtYOAG_-1VR468weQQ6FCmkslr1voeq0CKJE7NkrrVFd58wBGiotDpZerKghvSM88Cz5Z007L78rpgm0RpVdAB-3-nAu7v4G49j3mk9nautCZ0QA_crCDoF-nlBd443tgW1tYLWzDXu6__CFKY8LymxZsKwEpu0eMO_oTRi0AfWqZ5IDLy0Yj89MqzLCEZKgxM1GUKPYdBo1NFaSEvRKxkv2spyTeKwoFFbXUAWIoxCZdBCC-1EI2SdVRofgqxl7smRpI17ZTqBK0AodjgeSPbO1LTtUJDqXaB20WmC7YwpfVdgxcdX62ThIj9Z9Q87olF0ILaXPhD_itUVJXYnF2-DLvRZme9cpHT5Rj8QVPdyV9x02aP6YzrNi9jfIwFyJ78jUYAu6SVM-z1O-mKfoEB-dMLR3ds8qKyNkCcwaCY01PjhBGffD_T37BtDG8CJLUNtdiN47ttRj7gjfHGCAfjynEkpyVidsJZnIcU1LnB7w3lbD7OrbwxzLs_yMexm5K4YZv8oYcFxDmPK052IvcMNslp2aQmSsImPCeMIEPzBWcc_xyMgHxmTMh2_ElxIrdilIcY1m3pHC9Iw-H_RUCZOoJ8E1X1a9gelIkTtXE89VC1bXdJUC10ocq-mXvPAllvf9xanmjnYn2QcCEKaaZoD17IbnF2v4uBinPAxWdutgjz0DPmH0Pryo8EVoShesNhwRIhWlUon_PzthPEJAQ8n0S1Ca7sQWn2dV29IAiOmBBTxUzXlV4epWOKnBe2ZrTC-PHw71iQZPRlAhQQNW5IyxjxO-aBC5Ao4ZBJQ1FWRlERKw8CrdSQSxrtqh2oNlB3kRgrA1BqEMIkU_fmiaUh3uo56Ytv3UurdOMq9-i7lu3UHEsCsteBxFFmRD2yIAMhSlPHUEdNLt5x-fuvLnSNq7E8voAQkkfDS4-WMsIZo9IwJF-d42EHZUOw310C0YcArz83EcoidE7ghw5zXv4FnB3s9is7Bui0sPq2VC0PiIWV1ky7KYZyuxBJkvijnUaZaLXBQFhxzqkq8KWVNbGauqKsqeT1CChOfPH-ml3omdiaP0VwtONqC-0gdjnuwbhZhBTzhF4DeBp0eBYcd-M5XrTK5Q-TSooGHdGfzCqFXfXyggaOPHnx6-3H5-OkVs2jm9voJrhwzE2w2K-4pgP8a0Yp4W2XS35lm2qvIFlCtZSciKJEmqYpULkIvFYsmraZyv_BrBBT89qD3isIQaMUT0KRIrf7T863J-Wh5KBT-zsFn8JmgY8Kfd_mAcAWuq1jzhPJnzlKfFKklmWSWyus6yok4xFmWJvoJGKH0M39St48nKbutpBFA-nGI7xU86HKMAotUoX3RhZ93aoLMleNFpo8D5aXTGOnrid6pHYng">