InstCombine produces worse code when provided with range information

[llvmbot]

Bugzilla Link	37636
Version	trunk
OS	Windows NT
Reporter	LLVM Bugzilla Contributor
CC	@RKSimon,@rotateright

Extended Description

Instcombine can sometimes produce a worse code when dealing with values annotated by ranges than if there was no range. Apparently it tries to replace sdiv with bit magic and it breaks some other pattern recognition.

Tests:

define i1 @​good(i32* %A) {
%A.val = load i32, i32* %A, align 8
%B = sdiv i32 %A.val, 2
%C = icmp sge i32 0, %B
ret i1 %C
}

define i1 @​bad(i32* %A) {
%A.val = load i32, i32* %A, align 8, !range !​0
%B = sdiv i32 %A.val, 2
%C = icmp sge i32 0, %B
ret i1 %C
}

!​0 = !{i32 0, i32 2147483647}

Run opt -instcombine -S

The result is:

define i1 @​good(i32* %A) {
%A.val = load i32, i32* %A, align 8
%C = icmp slt i32 %A.val, 2
ret i1 %C
}

define i1 @​bad(i32* %A) {
%A.val = load i32, i32* %A, align 8, !range !​0
%B.mask = and i32 %A.val, 2147483646
%C = icmp eq i32 %B.mask, 0
ret i1 %C
}

!​0 = !{i32 0, i32 2147483647}

[llvmbot]

Looks like the relevant piece of code is this one:

// FIXME: If the operand types don't match the type of the divide
// then don't attempt this transform. The code below doesn't have the
// logic to deal with a signed divide and an unsigned compare (and
// vice versa). This is because (x /s C2) <s C produces different
// results than (x /s C2) <u C or (x /u C2) <s C or even
// (x /u C2) <u C. Simply casting the operands and result won't
// work. :( The if statement below tests that condition and bails
// if it finds it.
bool DivIsSigned = Div->getOpcode() == Instruction::SDiv;
if (!Cmp.isEquality() && DivIsSigned != Cmp.isSigned())
return nullptr;

We do not handle the case when signed and unsigned division are basically the same.

[llvmbot]

Scratch the previous comment. The problem is that we replace sdiv -> udiv -> shift, and then we do not process "cmp(shift)" as we do "cmp(sdiv)".

[rotateright]

https://rise4fun.com/Alive/slCV

%sh = lshr i32 %x, 1
%r = icmp slt i32 %sh, 1
=>
%r = icmp ult i32 %x, 2

We're missing this fold?

[rotateright]

https://rise4fun.com/Alive/slCV

%sh = lshr i32 %x, 1
%r = icmp slt i32 %sh, 1
=>
%r = icmp ult i32 %x, 2

We're missing this fold?

No, I see now that we do have that fold.

We could view this as an ordering problem within InstCombiner::visitICmpInst(). We really shouldn't be calling foldICmpUsingKnownBits() before we try other folds because using knownbits is expensive. But that's going to expose more problems.

The whole thing needs to be restructured, so that we don't do information-losing transforms before simplifications. Or we have to fill in the mask bits that demanded bits removes:

define i1 @​notbad(i32* %A) {
%x = load i32, i32* %A, align 8, !range !​0
%sh = and i32 %x, -2 ; this will change to 2147483646 using demanded bits
%r = icmp eq i32 %sh, 0
ret i1 %r
}

[llvmbot]

Hi Sanjay,

Do you plan to take any actions on that? I think I can fix it in my own, just double-check that we are not duplicating efforts.

[rotateright]

Hi Sanjay,

Do you plan to take any actions on that? I think I can fix it in my own,
just double-check that we are not duplicating efforts.

Hi Max -

This isn't on my immediate TODO list, so please go ahead. Thanks!

[llvmbot]

Ok! I'll take this one yet. Thanks!

[llvmbot]

https://reviews.llvm.org/D48584

[llvmbot]

Fixed by https://reviews.llvm.org/rL336172

[rotateright]

Reopening because the fix was reverted due to other regressions:
https://reviews.llvm.org/rL336410

Can we solve this directly in computeKnownBits by making it smarter about range metadata?