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

    <tr>
        <th>Summary</th>
        <td>
            [InstCombine] Optimize ceil division idiom
        </td>
    </tr>

    <tr>
      <th>Labels</th>
      <td>
            llvm:instcombine,
            missed-optimization
      </td>
    </tr>

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

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

<pre>
    https://alive2.llvm.org/ce/z/Lo75y7
```llvm
define i8 @src(i8 %x, i8 %y) {
  %wo = call {i8, i1} @llvm.uadd.with.overflow(i8 %x, i8 %y)
  %ov = extractvalue {i8, i1} %wo, 1
  %ov.not = xor i1 %ov, true
  call void @llvm.assume(i1 %ov.not)

  %nonzero = icmp ne i8 %x, 0
  %bias = zext i1 %nonzero to i8
  %sub = sub i8 %x, %bias
 %div = udiv i8 %sub, %y
  %add = add i8 %div, %bias
  ret i8 %add
}

define i8 @tgt(i8 %x, i8 %y) {
  %y.minus.1 = add i8 %y, -1
  %add = add i8 %x, %y.minus.1
  %div = udiv i8 %add, %y
  ret i8 %div
}
```

We could optimize `Bias = Y != 0; (X - Bias) / Y + 1` to the more efficient `(X + Y - 1) / Y` if we know that the addition cannot overflow.

Probably the more important case is where the udiv is a lshr instead, as that's where the relative overhead is higher.
</pre>
<img width="1px" height="1px" alt="" src="http://email.email.llvm.org/o/eJyMVMGOqzYU_RqzuQoyJpBkwWJmIqRKldpd-5bGvoTbBziyDZnM11c2JMOb11aVItmxzzn3nGtj6RxdRsSKFa-sOCdy8p2x1UjfSSWN0feq8_7qWP7CRM1ELXuaUaR9Pw-psRcmaoVM1B9M1L-aQ3E_MH5m_IWVfPkF4LKksaURgY7A9txZxcQxzEXxzsQbLNM7Eydgh9eFAWHpZoDlZ1Cy78MOHSM6Y4dz0Ik-Jql1eiPfpWZG2_bm9m_aG10zR11891YqP8t-wp_0Q_XwN_uBl47GR-67sUDZshhg3k74QEa_syH9dCmdmwYMzrJPnaenTYXRjB9ol9ikhiusXVvT8A20Ieki7gPf_erlQfcG6LjBuqmJ0DBu5FaVFchEoWnpzBQmC9BNzQq9bwSl1hEYxgWnaf5ZEiz6dV9qvaY9nLexf7ga_uL_59W4pwONk0uzLzbugbXL_tPqI_tTY4P-hw4E51868BkrxP4S63H9tyn_QFBm6jWYq6eBPhBYyV8fJ_gNmMjChLP8FZg4_gk7CLsxt6gj4BUyVvJwtL5DGIxFwLYlRTj6oBZpAfYNdpA9mYFDLdwQvo_mBr6TPgpIrcmTGUHJMVzqx-eTbm3_bk0jm_7-WZKGq7Fejh6UdAjk4NahxQhYeuZAQu86CzQ6jzL2TrpYmInDFm-xl55mjLU7lDqQO7p0aNNEV7k-5SeZYJUdsuN-X5aCJ13FW67lQYmyaNqGH4_ZqWlUcSpFXuT5XhcJVYKLPS-zIuPZgfO0VfzEW1mWudZHpfZsz3GQ1D8fsoScm7A6FWUhkl422Lv4JAoRX7D8JSRRZmhoRCYEE29MiIGcQ71bz1OGVoa94pzYKtB2zXRx4fsn591nKU--jw_uL6Pzb6tmcYbfHvdCIfWgaSYXDoc0mSGZbP_lKb6Q76YmVWZgoo4ul2F3teYvVJ6JOoZyTNRLrrkSfwcAAP__yh22HA">