[InstCombine] Missed optimization for icmp ult <power-of-2> & mask check

[erikdesjardins]

define i1 @src(i32 %arg) {
  %a = icmp ult i32 %arg, C1
  %b = and i32 %arg, C2
  %c = icmp ne i32 %b, C2
  %r = and i1 %a, %c
  ret i1 %r
}

is equivalent to:

define i1 @tgt(i32 %arg) {
  %r = icmp ult i32, %arg, C2
  ret i1 %r
}

where C1 is a power of 2, and C2 is a contiguous mask of bits starting 1 bit "below" C1.

For example:

If C1 is       00100000

then C2 can be 00010000
            or 00011000
            or 00011100, etc.

and can not be 00010100
            or 00111000, etc.

This is already optimized if C2 is also a power of 2, but not if it has more than one set bit: https://godbolt.org/z/3a6WbKabr

Alive2 proof: https://alive2.llvm.org/ce/z/3Se4bm

[jmciver]

I am interested in working on this issue. I have started looking into a solution.

[jmciver]

I am still working on a solution.

[jmciver]

Apologies, I was not aware that pushes to my forked repository would cause notifications on this ticket.

I am currently developing associated test cases for the solution.

[jmciver]

Phabricator differential: https://reviews.llvm.org/D125717

[erikdesjardins]

Fixed in 1001f90