[InstCombine] Miscompile of (x & (~(-1 << x))) << x

[meheff]

Bugzilla Link	49778
Resolution	FIXED
Resolved on	May 03, 2021 16:55
Version	trunk
OS	All
Blocks	#48246 #48661
CC	@LebedevRI,@RKSimon,@rotateright,@tstellar
Fixed by commit(s)	5352490 dceb3e5 2760a80 907a751 4a4b1c7 c27ad80

Extended Description

This expression is miscompiled in the case where x is zext of a single bit value. Here's before and after from a single instcombine transform extracted using debug_counter and fed to Alive:

---

define i32 @​src(i1 %x2) {
%0:
%x13 = zext i1 %x2 to i32
%_7 = shl i32 4294967295, %x13
%mask = xor i32 %_7, 4294967295
%_8 = and i32 %mask, %x13
%_9 = shl i32 %_8, %x13
ret i32 %_9
}
=>
define i32 @​tgt(i1 %x2) {
%0:
%x13 = zext i1 %x2 to i32
%1 = shl i32 %x13, %x13
%_9 = and i32 %1, 0
ret i32 %_9
}
Transformation doesn't verify!
ERROR: Value mismatch

Example:
i1 %x2 = #x1 (1)

Source:
i32 %x13 = #x00000001 (1)
i32 %_7 = #xfffffffe (4294967294, -2)
i32 %mask = #x00000001 (1)
i32 %_8 = #x00000001 (1)
i32 %_9 = #x00000002 (2)

Target:
i32 %x13 = #x00000001 (1)
i32 %1 = #x00000002 (2)
i32 %_9 = #x00000000 (0)
Source value: #x00000002 (2)
Target value: #x00000000 (0)

I suspect the problematic transform is this one:

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

Line 168 in c06a8f9

// b) (x & (~(-1 << MaskShAmt))) << ShiftShAmt

Looks like maybe(?) NewMask is incorrectly being computed as zero:

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

Line 317 in c06a8f9

return BinaryOperator::Create(Instruction::And, NewShift, NewMask);

[meheff]

assigned to @LebedevRI

[LebedevRI]

Does not repro on main: https://godbolt.org/z/zdfbEKns9

[meheff]

Does not repro on main: https://godbolt.org/z/zdfbEKns9

Looks like the link you sent shows that it does repro? The optimized version is unconditionally zero. It shouldn't be.

[meheff]

Just to clarify my earlier comment, the posted code snippet can conceivably be simplified to:

%x13 = zext i1 %x2 to i32
%result = shl i32 %x13, %x13
ret i32 %result

Which looks like what that instcombine transformation might be trying to accomplish. The truth table for this is:

f(0) => 0
f(1) => 2

However, it is being replaced with zero by the optimizer because of the addition of an AND with zero.

[meheff]

I think the bug lies here:

auto *SumOfShAmts = dyn_cast_or_null(SimplifyAddInst(
MaskShAmt, ShiftShAmt, /IsNSW=/false, /IsNUW=/false, Q));

llvm-project/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp

Line 229 in 2c4548e

auto *SumOfShAmts = dyn_cast_or_null<Constant>(SimplifyAddInst(

It's trying to simplify the sum of the two shift values (MaskShAmt and ShiftShAmt) in the expression:

(x & (~(-1 << MaskShAmt))) << ShiftShAmt

Where the code again is:

%x13 = zext i1 %x2 to i32
%_7 = shl i32 4294967295, %x13
%mask = xor i32 %_7, 4294967295
%_8 = and i32 %mask, %x13
%_9 = shl i32 %_8, %x13

In this case both MaskShAmt and ShiftShAmt in the expression above are i1 %x2 (the matching looks through zexts). So, of course, it can simplify i1 %x2 + %x2 to zero, but that is incorrect for the purposes of the transformation because it overflows the type i1 which results in the wrong mask being generated.

[meheff]

fwiw, a C repro:

#include <stdio.h>
#include <stdbool.h>

unsigned int f(bool b) {
unsigned int ub = b;
return (ub & (~((unsigned int) -1 << ub))) << ub;
}

int main(int argc, char** argv) {
printf("f(0) = %d\n", f(0));
printf("f(1) = %d\n", f(1));
return 0;
}

$ clang -O2 foo.c && ./a.out
f(0) = 0
f(1) = 0
$ gcc -O2 foo.c && ./a.out
f(0) = 0
f(1) = 2

https://godbolt.org/z/jT1sKa1rq
https://godbolt.org/z/v1j1TMzv7

[rotateright]

I'm not sure if this would be considered a legitimate/complete fix, but we are missing this simplification:
https://alive2.llvm.org/ce/z/bBuyks

define i32 @​src(i1 %b) {
%z = zext i1 %b to i32
%s1 = shl i32 -1, %z
%x1 = xor i32 %s1, -1
ret i32 %x1
}

define i32 @​tgt(i1 %b) {
%z = zext i1 %b to i32
ret i32 %z
}

If we had that, it might guarantee that the bug in instcombine is covered up?

[rotateright]

If the only known problem case is with a bool type, there's a 1-line fix?
We can deal with the missed optimization in another patch.

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp b/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
index 2007cf0bbc9c..eba29e8e24e1 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineShifts.cpp
@@ -222,7 +222,8 @@ dropRedundantMaskingOfLeftShiftInput(BinaryOperator *OuterShift,

 // We have two shift amounts from two different shifts. The types of those
 // shift amounts may not match. If that's the case let's bailout now.

• if (MaskShAmt->getType() != ShiftShAmt->getType())

• if (MaskShAmt->getType() != ShiftShAmt->getType() ||

•    MaskShAmt->getType()->getScalarSizeInBits() == 1)
   return nullptr;
  

  // Can we simplify (MaskShAmt+ShiftShAmt) ?

[LebedevRI]

The fix would consist of copypasting 781d077.

[LebedevRI]

Sorry for the delay, fixed.
This should probably be backported.

[meheff]

Thanks for the quick fix!

[tstellar]

There are 3 commits listed in the "Fixed By Commits" field. Do these all need to be backported?

[LebedevRI]

There are 3 commits listed in the "Fixed By Commits" field. Do these all
need to be backported?

Yep

[tstellar]

Merged: c27ad80