[InstCombine] Optimize ceil division idiom

[nikic]

https://alive2.llvm.org/ce/z/Lo75y7

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 = X != 0; (X - Bias) / Y + Bias 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.

[jayfoad]

We could optimize Bias = Y != 0; (X - Bias) / Y + 1

It's Bias = X != 0; (X - Bias) / Y + Bias

[nikic]

Based on discussion in #100977, it looks like in practice we don't really have enough information to prove the necessary pre-condition, so I'll go ahead and close this.