missing instcombine: select (icmp ugt A, N), (shr A, M), 0 -> shr A, M, when N < 2^M

[zygoloid]

Example, seen in the wild in libcap-ng:

void f(int, int);
void g(unsigned int capability) {
 	int idx;

	if (capability > 31) {
		idx = capability>>5;
		capability %= 32;
	} else
		idx = 0;

        f(idx, capability);
}

produces:

define dso_local void @g(i32 noundef %0) local_unnamed_addr #0 {
  %2 = icmp ugt i32 %0, 31
  %3 = lshr i32 %0, 5
  %4 = and i32 %0, 31
  %5 = select i1 %2, i32 %3, i32 0
  tail call void @f(i32 noundef %5, i32 noundef %4) #2
  ret void
}

This could be optimized further to:

define dso_local void @g(i32 noundef %0) local_unnamed_addr #0 {
  %1 = lshr i32 %0, 5
  %2 = and i32 %0, 31
  tail call void @f(i32 noundef %1, i32 noundef %2) #2
  ret void
}

The general pattern here is:

select (icmp ugt A, N), (shr A, M), 0 -> shr A, M

whenever N < 2^M.

[rotateright]

We probably want an even more general match using knownbits (ValueTracking) when the compare (select condition) is a disguised bit-test (see llvm::decomposeBitTestICmp()).

For example, we also miss the optimization with an 'and' instruction instead of a shift:
https://alive2.llvm.org/ce/z/ns7yER

define i8 @src(i8 %x) {
  %is_low_val = icmp ult i8 %x, 32
  %high_mask_x = and i8 %x, -32
  %r = select i1 %is_low_val, i8 0, i8 %high_mask_x
  ret i8 %r
} 

define i8 @tgt(i8 %x) {
  %high_mask_x = and i8 %x, -32
  ret i8 %high_mask_x
} 

[nikic]

I'd probably approach this in terms of icmp(X) ? f(X) : C where f(exact_icmp_range) == C.

[alexander-shaposhnikov]

I've prepared a patch, planning to send it for review ~soon.