[InstCombine] Transform `icmp eq/ne ({su}div exact X,Y),C` -> `icmp eq/ne X, Y*C`

[goldstein.w.n]

Summary

We can do this if Y*C doesn't overflow. This is trivial if C is
0/1. Otherwise we actually generate a mul instruction iff the div
has one use.

Alive2 Links:

udiv: https://alive2.llvm.org/ce/z/GWPW67
sdiv: https://alive2.llvm.org/ce/z/bUoX9h

[goldstein.w.n]

ping.

[nikic]

LGTM

llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp

3331–3332

Drop this part of the comment, it does not reflect the implementation.

3339

Check hasOneUse() first here.

[nikic]

I'd also suggest to update the proofs to match what you are actually implementing. The current ones are rather roundabout.

[goldstein.w.n]

Fixup some nits