This is an archive of the discontinued LLVM Phabricator instance.

[InstSimplify] Peephole optimization for icmp (urem X, Y), X
ClosedPublic

Authored by xldenis on Aug 2 2020, 4:43 AM.

Details

Summary

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

Diff Detail

Event Timeline

xldenis created this revision.Aug 2 2020, 4:43 AM
xldenis requested review of this revision.Aug 2 2020, 4:43 AM
xldenis edited the summary of this revision. (Show Details)
lebedev.ri retitled this revision from Peephole optimization for icmp (urem X, Y), X to [InstSimplify] Peephole optimization for icmp (urem X, Y), X.Aug 2 2020, 5:26 AM
lebedev.ri edited reviewers, added: lebedev.ri, spatel; removed: craig.topper, ctetreau, regehr.
lebedev.ri added a reviewer: nikic.

Thank you for the patch!

llvm/lib/Analysis/InstructionSimplify.cpp
2967

This appears correct, but you also need to handle icmp pred Y, (urem Y, X) case.
I know that naively one would expect it to be canonicalized by complexity sorting,
and i think said complexity sorting is a subtle evil.

llvm/test/Transforms/InstSimplify/compare.ll
726

I think these could be i8, to simplify the life of alive :)

nikic added inline comments.Aug 2 2020, 6:53 AM
llvm/lib/Analysis/InstructionSimplify.cpp
2967

I've applied some cleanup in https://github.com/llvm/llvm-project/commit/a0addbb4ec8c7bf791139699d46b08413c46eed7 to only explicitly handle the binop on the LHS and treat the other side via swapped predicate.

Added the symmetric case for icmp X (urem X Y) and changed the test bitwidths to i8.

xldenis added inline comments.Aug 2 2020, 7:05 AM
llvm/lib/Analysis/InstructionSimplify.cpp
2967

ah I just added the mirrored version of the opt, should I remove it then? I'll leave the test cases.

Removed mirror transformation since it is unnecessary and fix the additional mirrored tests.

lebedev.ri added inline comments.Aug 2 2020, 7:08 AM
llvm/lib/Analysis/InstructionSimplify.cpp
2967

You need to rebase the patch, moving a single variant of the fold into simplifyICmpWithBinOpOnLHS()

I think it's also possible to apply the same logic to both X % Y <= Y and X % Y <= X

Rebase patch on latest master.

I think it's also possible to apply the same logic to both X % Y <= Y and X % Y <= X

The first optimization already exists (line 2787, sorry having a hard time in this UI). And I'm adding the second one, unless I misunderstood?

nikic added inline comments.Aug 2 2020, 7:32 AM
llvm/test/Transforms/InstSimplify/compare.ll
731

These tests aren't testing the right fold. You are checking for (X % Y) <= Y, which is a fold that already exists. What you add here is (X % Y) <= X.

lebedev.ri added inline comments.Aug 2 2020, 7:36 AM
llvm/lib/Analysis/InstructionSimplify.cpp
2756

Minor nit: icmp pred (urem X, Y), X might be better for readability

2757

LBO && part is not needed, we know it's a non-null ptr already.

xldenis marked an inline comment as done.
nikic accepted this revision.Aug 2 2020, 1:01 PM

LGTM

This revision is now accepted and ready to land.Aug 2 2020, 1:01 PM

@xldenis if you need help committing do state so, and specify the Author: name <e@ma.il> line for commit attribution.

xldenis marked an inline comment as done.EditedAug 3 2020, 7:54 AM

@lebedev.ri yes, I do, I don't actually know what the next step is here.

For the attribution

Author: Xavier Denis <xldenis@gmail.com>

is fine. Unless you want me to edit the patch message directly?

This revision was automatically updated to reflect the committed changes.