InstCombine: lshr + "sext" => ashr canonicalization

[LebedevRI]

Bugzilla Link	42389
Version	trunk
OS	Linux
Depends On	#41736 #42909 #42940
CC	@RKSimon,@nikic,@rotateright
Fixed by commit(s)	373964, 375378

Extended Description

I have not triaged yet what folds are missing, but this gigantic fold is missing:
https://godbolt.org/z/E9-txU

int bad(unsigned input, unsigned len) {
    unsigned diff = input >> (32 - len);
    // If the first bit is 1 we need to turn this into a negative number
    if (diff >> (len - 1))
        diff -= (1 << len);
    return diff;
}
int good(unsigned input, unsigned len) {
    return int(input) >> (32 - len);
}

https://rise4fun.com/Alive/l3k

Name: ashr
  %o3 = sub i32 32, %nbits
  %o4 = lshr i32 %x, %o3
  %o5 = add i32 %nbits, -1
  %o6 = lshr i32 %o4, %o5
  %o7 = icmp eq i32 %o6, 0
  %o8 = shl i32 1, %nbits
  %o9 = select i1 %o7, i32 0, i32 %o8
  %r = sub i32 %o4, %o9
=>
  %n0 = sub i32 32, %nbits
  %r = ashr i32 %x, %n0

I'm seeing this in real code.

[LebedevRI]

assigned to @LebedevRI

[LebedevRI]

After D63812+D63829 we are now down to

define dso_local i32 @_Z3badjj(i32, i32) local_unnamed_addr #0 {
  %3 = sub i32 32, %1
  %4 = lshr i32 %0, %3
  %5 = icmp sgt i32 %0, -1
  %6 = shl i32 1, %1
  %7 = select i1 %5, i32 0, i32 %6
  %8 = sub i32 %4, %7
  ret i32 %8
}

Is there any other obvious canonicalization missing?
I can't think of any right now.

[LebedevRI]

Okay, i believe i have fixed all the prereqs i know of.
Proceeding..

[LebedevRI]

The fold itself added in r373964,
but more work is needed to produce said sign-bit checks;
and ideally zext-vs-sext, in sub-vs-add.

[LebedevRI]

There's also a case with constants:

int sext(unsigned x) {
    int extracted = x >> (32-4);
    if(extracted & (1U << 3))
      extracted -= 1U << 4;
    return extracted;
}

https://godbolt.org/z/Qjs3OW

Name: llvm/llvm-project#41734 
Pre: C2 == -1 << (32-C1)
  %2 = lshr i32 %0, C1
  %3 = icmp slt i32 %0, 0
  %4 = or i32 %2, C2
  %5 = select i1 %3, i32 %4, i32 %2
  =>
%5 = ashr i32 %0, C1

https://rise4fun.com/Alive/QRly

This one i will look into.

[LebedevRI]

There's also a case with constants:
And not unexpectedly things go bad as usual when there's trunc, we don't form
sign-bit-check:

int sext(unsigned long x) {
    int extracted = x >> (64-4);
    if(extracted & (1U << 3))
      extracted -= 1U << 4;
    return extracted;
}

Name: llvm/llvm-project#41734 
  %2 = lshr i64 %0, 60
  %3 = trunc i64 %2 to i32
  %4 = and i32 %3, 8
  %5 = icmp eq i32 %4, 0
  %6 = or i32 %3, -16
  %7 = select i1 %5, i32 %3, i32 %6
  =>
%zz = ashr i64 %0, 60
%7 = trunc i64 %zz to i32

https://godbolt.org/z/bHiPfS
https://rise4fun.com/Alive/JeAb

[LebedevRI]

mentioned in issue #41736

[LebedevRI]

mentioned in issue llvm/llvm-bugzilla-archive#42412

[LebedevRI]

mentioned in issue #42909

[LebedevRI]

mentioned in issue #42940