From https://bugs.freebsd.org/216614, building recent versions of emacs with recent clang can fail with an assertion: Assertion failed: ((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"), function computeKnownBits, file lib/Analysis/ValueTracking.cpp, line 1606. Reduced test case, reproduces with trunk r293557: /* clang -cc1 -triple x86_64 -S -O2 testcase.c */ enum { x0, x1 } x2(long x3, x4) { return __builtin_assume_aligned(x3 - x4, 8); } x5(void *x3) { return x3; } union x6 { int x7 } x8() { long x9 = x5(&(union x6){}); x2(x9, x1); } This started to appear somewhere between r282311 and r289043, no narrower window yet.
Bisection shows this assertion to start appearing after: ------------------------------------------------------------------------ r282312 | spatel | 2016-09-24 01:17:29 +0200 (Sat, 24 Sep 2016) | 10 lines [x86] fix FCOPYSIGN lowering to create constants instead of ConstantPool loads This is similar to: https://reviews.llvm.org/rL279958 By not prematurely lowering to loads, we should be able to more easily eliminate the 'or' with zero instructions seen in copysign-constant-magnitude.ll. We should also be able to extend this code to handle vectors. ------------------------------------------------------------------------ Sanjay, any ideas? :)
Apologies Sanjay, it isn't caused by r282312, this was a bisection error. It turns out this has been a problem for far longer, and is a regression from clang 3.7 to 3.8. It was introduced by: ------------------------------------------------------------------------ r251146 | hfinkel | 2015-10-23 22:37:08 +0200 (Fri, 23 Oct 2015) | 40 lines Handle non-constant shifts in computeKnownBits, and use computeKnownBits for constant folding in InstCombine/Simplify [... long commit message ...] ------------------------------------------------------------------------ Since the assertion itself is in computeKnownBits, this must be some sort of scenario that wasn't foreseen when this commit was done. Hal, any idea?
The x86 change can't be the cause because this fails in IR. :) I started reducing a test, so I'll dig in here: %union.x6 = type { i32 } declare void @llvm.assume(i1) define i32 @x8() { %compound = alloca %union.x6, align 4 %x7 = getelementptr inbounds %union.x6, %union.x6* %compound, i64 0, i32 0 store i32 0, i32* %x7, align 4 %t0 = bitcast %union.x6* %compound to i8* %t1 = ptrtoint i8* %t0 to i64 %t2 = trunc i64 %t1 to i32 %conv = sext i32 %t2 to i64 %sub = sub nsw i64 %conv, 1 %maskedptr = and i64 %sub, 7 %maskcond = icmp eq i64 %maskedptr, 0 call void @llvm.assume(i1 %maskcond) %t3 = trunc i64 %sub to i32 ret i32 %t3 } ------------------------------------------------------------------------------ $ ./opt -early-cse 31809min.ll -S Assertion failed: ((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"), function computeKnownBits, file /Users/spatel/myllvm/llvm/lib/Analysis/ValueTracking.cpp, line 1606.
I'm not sure where to go from here. The IR test can be reduced to something like this: declare void @llvm.assume(i1) define i64 @PR31809() { %a = alloca i32 <--- low 2 bits are guaranteed 0 due to alignment %t1 = ptrtoint i32* %a to i64 %cond = icmp eq i64 %t1, 3 call void @llvm.assume(i1 %cond) <--- assume low 2 bits are set ret i64 %t1 } ./opt -instsimplify 31809min.ll -S -debug Assertion failed: ((KnownZero & KnownOne) == 0 && "Bits known to be one AND zero?"), function computeKnownBits, file /Users/spatel/myllvm/llvm/lib/Analysis/ValueTracking.cpp, line 1606. ---------------------------------------------------------------------------------- Does the original program have UB? Did we produce faulty IR before this stage? Even so, we should not crash?
(In reply to comment #4) > I'm not sure where to go from here. The IR test can be reduced to something > like this: > > declare void @llvm.assume(i1) > > define i64 @PR31809() { > %a = alloca i32 <--- low 2 bits are guaranteed 0 due to alignment > %t1 = ptrtoint i32* %a to i64 > %cond = icmp eq i64 %t1, 3 > call void @llvm.assume(i1 %cond) <--- assume low 2 bits are set > ret i64 %t1 > } > > ./opt -instsimplify 31809min.ll -S -debug > Assertion failed: ((KnownZero & KnownOne) == 0 && "Bits known to be one AND > zero?"), function computeKnownBits, file > /Users/spatel/myllvm/llvm/lib/Analysis/ValueTracking.cpp, line 1606. > > ----------------------------------------------------------------------------- > ----- > > Does the original program have UB? Did we produce faulty IR before this > stage? Even so, we should not crash? We shouldn't crash, but it does look like the program has UB (the reduction certainly does). Asking the compiler to assume some alignment for a pointer which the compiler otherwise knows can't have that alignment.
Created attachment 17920 [details] Original full test case For reference, here is the original preprocessed test case from emacs-devel. It may very well be the case that there is UB in there, it is a very nasty lisp interpreter after all. (And don't start about the horrific things with sbrk() it does. :)
computeKnownBits deals with logical fallacies by returning "I don't know", we should do the same for this case.
Sigh, this is probably a ridicolous typo in ValueTracking.cpp. around line 588: // For those bits in the mask that are known to be one, we can propagate // known bits from the RHS to V. KnownZero |= RHSKnownZero & MaskKnownOne; KnownOne |= RHSKnownOne & MaskKnownOne; I thought I was getting crazy after 20 minutes in visual studio trying to understand why APInt(7u) & APInt(0U) was returning APInt(7u) then I realized we were doing an and with the wrong mask :|
Fix coming shortly.
Or not, as some tests are failing. Digging further.
And I was so wrong, I apologize :( This was already guessed in the thread, but more in detail. As pointed out by Sanjay the alloca gives us the two lowest bits are always zero i.e. KnownZero = 3 and then this matcher gives us: // assume(v & b = a) } else if (match(Arg, m_c_ICmp(Pred, m_c_And(m_V, m_Value(B)), m_Value(A))) && Pred == ICmpInst::ICMP_EQ && isValidAssumeForContext(I, Q.CxtI, Q.DT)) { APInt RHSKnownZero(BitWidth, 0), RHSKnownOne(BitWidth, 0); computeKnownBits(A, RHSKnownZero, RHSKnownOne, Depth+1, Query(Q, I)); APInt MaskKnownZero(BitWidth, 0), MaskKnownOne(BitWidth, 0); computeKnownBits(B, MaskKnownZero, MaskKnownOne, Depth+1, Query(Q, I)); A : KnownZero: -1 (all set) B : KnownOne: 7 So when we derive bits from assume we end up an inconsistency (and assert). While I agree that bailing out in case we find one bit that's both zero and one, can't we just pick a winner? e.g. the one that gives the highest number of known bits.
(In reply to comment #11) > So when we derive bits from assume we end up an inconsistency (and assert). > While I agree that bailing out in case we find one bit that's both zero and > one, can't we just pick a winner? e.g. the one that gives the highest number > of known bits. There's a possibly enlightening comment about undef above computeKnownBits(): /// NOTE: we cannot consider 'undef' to be "IsZero" here. The problem is that /// we cannot optimize based on the assumption that it is zero without changing /// it to be an explicit zero. If we don't change it to zero, other code could /// optimized based on the contradictory assumption that it is non-zero. /// Because instcombine aggressively folds operations with undef args anyway, /// this won't lose us code quality. And here's a comment from computeKnownBitsFromShiftOperator(): // If there is conflict between KnownZero and KnownOne, this must be an // overflowing left shift, so the shift result is undefined. Clear KnownZero // and KnownOne bits so that other code could propagate this undef. So as David suggests, the safe (correct?) thing is to clear the registers and let the caller take action if they want, but we shouldn't return a known bogus value because that might conflict with some other value and cause the compiler to crash in another spot.
Yes, as I agreed in https://llvm.org/bugs/show_bug.cgi?id=31809#c11 probably giving up is the safest thing to do here. I still wonder if we can do better, but probably not worth it. Hal, WDYT?
(In reply to comment #13) > Yes, as I agreed in https://llvm.org/bugs/show_bug.cgi?id=31809#c11 probably > giving up is the safest thing to do here. I still wonder if we can do > better, but probably not worth it. Hal, WDYT? I think that giving up is reasonable. It might be even better to ignore the assume-derived bits in this case. Given that we always check bits from assumes last in computeKnownBits, this seems reasonable to implement. It would be nice to eventually add code to emit an optimization remark in this case too.
(In reply to comment #14) > (In reply to comment #13) > > Yes, as I agreed in https://llvm.org/bugs/show_bug.cgi?id=31809#c11 probably > > giving up is the safest thing to do here. I still wonder if we can do > > better, but probably not worth it. Hal, WDYT? > > I think that giving up is reasonable. > > It might be even better to ignore the assume-derived bits in this case. > Given that we always check bits from assumes last in computeKnownBits, this > seems reasonable to implement. It would be nice to eventually add code to > emit an optimization remark in this case too. I think emitting a remark is the best thing, but I haven't used that API yet, so minimal patch as step 1: https://reviews.llvm.org/D29395
The patch to avoid the assertion failure was committed here: https://reviews.llvm.org/rL293773 I was hoping to show kind of warning in this case, but that may not be feasible because we can potentially get to a conflicting known bits state in a program that doesn't actually have visible UB: https://reviews.llvm.org/D29404
Resolving as fixed (although there may now be undefined behavior in the program that gets silently compiled to something unexpected). It should be possible to see a compiler analysis remark for this example after: https://reviews.llvm.org/rL294208 See also related bug 31882.
*** Bug 33366 has been marked as a duplicate of this bug. ***