Bit-Tracking Dead Code Elimination (BDCE) fails to invalidate nsw/nuw after transforms

[dbabokin]

Bugzilla Link	33695
Resolution	FIXED
Resolved on	Jan 01, 2019 07:50
Version	trunk
OS	All
Blocks	#33196
CC	@dbabokin,@chengniansun,@majnemer,@zmodem,@hfinkel,@nunoplopes,@regehr,@sanjoy,@rotateright,@zhendongsu,@Vsevolod-Livinskij

Extended Description

clang trunk (also reproducible with 4.0, not reproducible with 3.9), x86_64.

cat f.cpp
#include <stdio.h>

unsigned char uc = 170;
unsigned char var_1 = 252;
unsigned int var_33 = 1346838541U;
unsigned char var_36;
void foo() {
var_36 = (((var_33 | (0xaf2597a4 | uc)) << 26) - var_1) * 70983U;
}

int main() {
foo();
printf("result: %d\n", var_36);
return 0;
}

clang++ -O0 f.cpp -o out0
./out0
result: 28

clang++ -O2 f.cpp -o out2
./out2
result: 0

Opt-bisect points to "Combine redundant instructions on function", which removes the calculations and foo() and stores 0 to var_36, which is incorrect value.

[llvmbot]

Nice, you found a very old regression.
This bisects to:

commit a979978
Author: Sanjay Patel spatel@rotateright.com
Date: Thu Jul 21 00:24:18 2016 +0000

[InstCombine] LogicOpc (zext X), C --> zext (LogicOpc X, C) (#28476 )

The benefits of this change include:
1. Remove DeMorgan-matching code that was added specifically to work-around
   the missing transform in http://reviews.llvm.org/rL248634.
2. Makes the DeMorgan transform work for vectors too.
3. Fix llvm/llvm-project#28850 : https://llvm.org/bugs/show_bug.cgi?id=28476

Extending this transform to other casts and other associative operators may
be useful too. See https://reviews.llvm.org/D22421 for a prerequisite for
doing that though.

Differential Revision: https://reviews.llvm.org/D22271

:040000 040000 993dcf12908a5bb8a9cbe347686249eeefb34078 47ce16c2e420b5cec3cd803cc1251e26aee50b50 M llvm
bisect run success

Reducing it now :)

[llvmbot]

This looks like a miscompile :)

diff pre-instcombine & post-instcombine

--- pre.ll 2017-07-06 12:07:43.650455998 -0700
+++ post.ll 2017-07-06 12:07:47.259322057 -0700
@@ -12,18 +12,7 @@
; Function Attrs: norecurse nounwind uwtable
define void @​foo() local_unnamed_addr #​0 {
entry:

• %0 = load i32, i32* @​var_33, align 4, !tbaa !​2
• %1 = load i8, i8* @​uc, align 1, !tbaa !​6
• %2 = or i8 0, 36
• %or = zext i8 0 to i32
• %or1 = or i32 0, 0
• %shl = shl i32 0, 26
• %3 = load i8, i8* @​var_1, align 1, !tbaa !​6
• %conv2 = zext i8 %3 to i32
• %sub = sub nuw i32 %shl, %conv2
• %mul = mul i32 %sub, 70983
• %conv3 = trunc i32 %mul to i8
• store i8 %conv3, i8* @​var_36, align 1, !tbaa !​6

• store i8 0, i8* @​var_36, align 1, !tbaa !​2
  ret void
  }

@@ -31,7 +20,7 @@
define i32 @​main() local_unnamed_addr #​1 {
entry:
call void @​foo()

• %0 = load i8, i8* @​var_36, align 1, !tbaa !​6

• %0 = load i8, i8* @​var_36, align 1, !tbaa !​2
  %conv = zext i8 %0 to i32
  %call = call i32 (i8*, ...) @​printf(i8* getelementptr inbounds ([12 x i8], [12 x i8]* @.str, i64 0, i64 0), i32 %conv)
  ret i32 0
  @@ -50,7 +39,5 @@
  !​0 = !{i32 1, !"wchar_size", i32 4}
  !​1 = !{!"clang version 5.0.0 (trunk 306964) (llvm/trunk 307215)"}
  !​2 = !{Fix a compilation error on gcc8 #3, !​3, i64 0}
  -Fix a compilation error on gcc8 #3 = !{!"int", !​4, i64 0}
  -Fix a compilation error on gcc8 #4 = !{!"omnipotent char", !​5, i64 0}
  -Seedarg/member/wip #5 = !{!"Simple C/C++ TBAA"}
  -Add check for matching HeaderFilter before emitting Diagnostic #6 = !{Fix a compilation error on gcc8 #4, !​4, i64 0}
  +Fix a compilation error on gcc8 #3 = !{!"omnipotent char", !​4, i64 0}
  +Fix a compilation error on gcc8 #4 = !{!"Simple C/C++ TBAA"}

[llvmbot]

Reduced
(run with opt -instcombine -bdce -instcombine)

@​uc = local_unnamed_addr global i8 -86, align 1
@​var_1 = local_unnamed_addr global i8 -4, align 1
@​var_33 = local_unnamed_addr global i32 1346838541, align 4
@​var_36 = common local_unnamed_addr global i8 0, align 1

define void @​patatino() {
%1 = load i32, i32* @​var_33, align 4
%2 = load i8, i8* @​uc, align 1
%3 = zext i8 %2 to i32
%4 = or i32 -1356490844, %3
%5 = or i32 %1, %4
%6 = shl i32 %5, 26
%7 = load i8, i8* @​var_1, align 1
%8 = zext i8 %7 to i32
%9 = sub i32 %6, %8
%10 = mul i32 %9, 70983
%11 = trunc i32 %10 to i8
store i8 %11, i8* @​var_36, align 1
ret void
}

[rotateright]

The test in comment 3 gave me a clue about how this goes wrong. The initial -instcombine in that case just adds 'nuw' to the sub in that example. That nuw is correct AFAICT.

Now, when -bdce goes to check demanded bits, it correctly sees that it can zap a bunch of operands to '0'. But doing that transform requires that we remove 'nuw' from the sub. Otherwise, we get "sub nuw 0, %something" - if that can't wrap, then instcombine correctly nukes it!

So a more reduced case to show the bug in -bdce:

define i1 @​#33695 (i1 %b, i8 %x) {
%setbit = or i8 %x, 64
%positive_number = zext i1 %b to i8
%negative_number = shl i8 %setbit, 1
%sub = sub nuw i8 %negative_number, %positive_number
%trunc = trunc i8 %sub to i1
ret i1 %trunc
}

$ ./opt -instcombine bd.ll -S
define i1 @​#33695 (i1 %b, i8 %x) {
ret i1 %b
}

$ ./opt -bdce -instcombine bd.ll -S
define i1 @​#33695 (i1 %b, i8 %x) {
ret i1 false
}

[hfinkel]

Funny, I thought replacing the value with 0 instead of undef would be safer ;)

[rotateright]

Funny, I thought replacing the value with 0 instead of undef would be safer
;)

Heh...there's a Mr. Yuck joke in here somewhere!

The names in my example can be improved a bit so we're not mixing our signed-ness:

define i1 @​#33695 (i1 %b, i8 %x) {
%setbit = or i8 %x, 64
%little_number = zext i1 %b to i8
%big_number = shl i8 %setbit, 1
%sub = sub nuw i8 %big_number, %little_number
%trunc = trunc i8 %sub to i1
ret i1 %trunc
}

$ ./opt -bdce bd.ll -S
define i1 @​#33695 (i1 %b, i8 %x) {
%setbit = or i8 %x, 64
%little_number = zext i1 %b to i8
%big_number = shl i8 0, 1 <-- that's not the big number we thought we had
%sub = sub nuw i8 %big_number, %little_number
%trunc = trunc i8 %sub to i1
ret i1 %trunc
}

---

I've never looked at bdce before today, so if someone else want to take a shot at a patch, feel free. If not, I'll try to get to this next week.

[llvmbot]

I don't understand undef/poison well enough to propose a proper fix, but I cc:ed Nuno & the undef crew as they may have thoughts :)

[regehr]

Ah, I don't know BCDE either and am on vacation for a couple more days but I will look at this.

[nunoplopes]

I totally agree with Sanjay's root causing.
(see this for example: http://rise4fun.com/Alive/Db)

Probably the only easy/sane way to fix this bug is to drop all of nsw/nuw/exact attributes from any expression that (transitively) uses the result of any changed instruction.
Since changing the value produced by an instruction can have arbitrary repercussions down in the expression tree, all assumptions made before (nsw/nuw/etc) must be dropped.
This BDCE pass doesn't have much information to its disposal; I guess the only thing we can rely on is that the root of the expression (an instruction of the expression used by a store/call/return) cannot change value and therefore can keep all of its assumptions.

Besides the arithmetic attributes, other things like @​llvm.assume and range metadata must also be dropped (unless proven they are safe).

[nunoplopes]

Nice catch btw :)

[hfinkel]

Let me make sure I understand...

The problem here is that BDCE, via an analysis of the use/def chain, has deduced that no bits of the value are required. Thus, is does not matter what they are. However, via flags, assumptions, etc. there might be implicit constraints on these bits can contribute to this determination. As a result, the replacement value may not always be zero, as zero might not have been consistent with these assumptions.

To put it another way, some of bits here aren't actually "dead", but are, rather, implicitly constrained.

BDCE is supposed to be a canonicalization transformation, and as a result, we should try not to have it cause information loss. We can recurse down the def/use chain, removing flags, we'd need to remove assumptions too. This gets messy.

[llvmbot]

Let me make sure I understand...

The problem here is that BDCE, via an analysis of the use/def chain, has
deduced that no bits of the value are required. Thus, is does not matter
what they are. However, via flags, assumptions, etc. there might be implicit
constraints on these bits can contribute to this determination. As a result,
the replacement value may not always be zero, as zero might not have been
consistent with these assumptions.

To put it another way, some of bits here aren't actually "dead", but are,
rather, implicitly constrained.

BDCE is supposed to be a canonicalization transformation, and as a result,
we should try not to have it cause information loss. We can recurse down the
def/use chain, removing flags, we'd need to remove assumptions too. This
gets messy.

Yes. I actually tried to implement what Nuno suggested and it gets very messy very quickly. I'm not sure if there's a better solution though ... we could consider preventing this optimization in case there's anything in the transitive closure that has flags/etc..., but that makes BDCE really conservative, probably too much.

[nunoplopes]

To put it another way, some of bits here aren't actually "dead", but are,
rather, implicitly constrained.

Yep, that's a good description of the problem.

BDCE is supposed to be a canonicalization transformation, and as a result,
we should try not to have it cause information loss. We can recurse down the
def/use chain, removing flags, we'd need to remove assumptions too. This
gets messy.

If BDCE removes a few instructions, I guess it's worth to pay the price of a few removed NSW attributes.

Actually, in theory it's possible to do this without too much loss of information, but that needs a bit more work.
Any value in the def/use chain that has all bits set as non-dead (by the demanded bit analysis) cannot have its value changed: if all bits are needed, all bits must keep the same value before/after optimization. That means that our "taint" propagation (of removing attributes/assumptions) can end there.

Hence the only potential loss of information is within the changed expression, but many of these removals are required for correctness and the remaining will be just a few (guessing).

[hfinkel]

Maybe the fix for this is the same thing we need to make known-bits caching work? The known-bits functions, etc. can (optionally) return a list of instructions that contributed to the decision. With such a list, we can clear flags in a targeted way.

[rotateright]

I've never looked at bdce before today, so if someone else want to take a
shot at a patch, feel free. If not, I'll try to get to this next week.

I failed on that. Also, I won't be able to look at this (or any other bugs) until Aug, so please feel free to fix this. :)

Finally, must correct my earlier misspelled reference to "Mr. Yuk":
https://en.wikipedia.org/wiki/Mr._Yuk