[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.