[InstSimplify] Peephole optimization for icmp (urem X, Y), X
authorXavier Denis <xldenis@gmail.com>
Tue, 4 Aug 2020 18:44:47 +0000 (20:44 +0200)
committerNikita Popov <nikita.ppv@gmail.com>
Tue, 4 Aug 2020 18:48:37 +0000 (20:48 +0200)
commit29fe3fe6155fd79ce731a119ce8065a8a0d26b56
treee0832a483a4bfbb8b8cde258f7632e5d7f3e496a
parentb778b04b69d02a2fa18b22a1858f3eb26c2f7f24
[InstSimplify] Peephole optimization for icmp (urem X, Y), X

This revision adds the following peephole optimization
and it's negation:

    %a = urem i64 %x, %y
    %b = icmp ule i64 %a, %x
    ====>
    %b = true

With John Regehr's help this optimization was checked with Alive2
which suggests it should be valid.

This pattern occurs in the bound checks of Rust code, the program

    const N: usize = 3;
    const T = u8;

    pub fn split_mutiple(slice: &[T]) -> (&[T], &[T]) {
        let len = slice.len() / N;
        slice.split_at(len * N)
    }

the method call slice.split_at will check that len * N is within
the bounds of slice, this bounds check is after some transformations
turned into the urem seen above and then LLVM fails to optimize it
any further. Adding this optimization would cause this bounds check
to be fully optimized away.

ref: https://github.com/rust-lang/rust/issues/74938

Differential Revision: https://reviews.llvm.org/D85092
llvm/lib/Analysis/InstructionSimplify.cpp
llvm/test/Transforms/InstSimplify/compare.ll