[ValueTracking] avoid crashing from bad assumptions (PR31809)

[spatel]

Summary

A program may contain llvm.assume info that disagrees with other analysis. This may be caused by UB in the program, so we must not crash because of that.

As noted in the code comments and PR31809:
https://llvm.org/bugs/show_bug.cgi?id=31809
...we can do better, but this at least avoids the assert/crash in the bug report.

[majnemer]

LGTM

[davide]

I have a question about the improvement you proposed (inline).

llvm/trunk/lib/Analysis/ValueTracking.cpp

800–803

Have you looked into how hard it would be to implement this invalidation? Also, why is that a stronger version? (i.e. there are cases where this actually matters or you're just speculating?)
Also, clearing the whole assumption cache is really what we want? I mean, what if there are other informations that are not inconsistent and we want to use them anyway?

[davide]

llvm/trunk/lib/Analysis/ValueTracking.cpp

800–803

In other words, I'm not entirely sure we should add this FIXME.

[hfinkel]

llvm/trunk/lib/Analysis/ValueTracking.cpp

800–803

I agree. This is a rare case and I don't think we need to make the infrastructure more complicated than necessary to handle it. Plus, it is a useful invariant that all of the assumptions are in the cache.

[spatel]

llvm/trunk/lib/Analysis/ValueTracking.cpp

800–803

Yes, I looked at putting Q.AC->clear() here. Let me attach a draft of that patch (or should I open a new review?).
I think that would be stronger in the sense that we'd be less likely to "leak" a transform based on a bad assumption.

I have no evidence that this matters or works the way I'm imagining (other than it affects the test cases included in this patch). That's why I didn't include it here. I was (possibly incorrectly) assuming that once we hit a bad assumption, we go into "all bets are off" mode, so we might as well nuke the cache. Let's remove the FIXME if that's wrong.

Personally, I think emitting the warning is the more important thing to do because we're now silently continuing compilation when we know something bad has happened.

[spatel]

badass2.patch7 KBDownload

Attaching a draft of the assumption cache invalidation patch that I was working on. This is just for reference. I don't think we want to pursue it because it's more trouble than it's worth even if it is "stronger".

[davide]

In D29395#663457, @spatel wrote:

badass2.patch7 KBDownload

Attaching a draft of the assumption cache invalidation patch that I was working on. This is just for reference. I don't think we want to pursue it because it's more trouble than it's worth even if it is "stronger".

I don't think it's stronger, but it's definitely more trouble. Remove the FIXME from the original patch and LGTM.

llvm/trunk/lib/Analysis/ValueTracking.cpp

// assume(v <_u c)
       if (isKnownToBeAPowerOfTwo(A, false, Depth + 1, Query(Q, I)))
         KnownZero |=
           APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes()+1);
       else
         KnownZero |=
           APInt::getHighBitsSet(BitWidth, RHSKnownZero.countLeadingOnes());
     }
   }
+
+  // If assumptions conflict with each other or previous known bits, then we
+  // have a logical fallacy. This should only happen when a program has
+  // undefined behavior. We can't assert/crash, so clear out the known bits and
+  // hope for the best.
+
+  // FIXME: Publish a warning/remark that we have encountered UB or the compiler
+  // is broken.
+
+  // FIXME: Implement a stronger version of "I give up" by invalidating/clearing
+  // the assumption cache. This should indicate that the cache is corrupted so
+  // future callers will not waste time repopulating it with faulty assumptions.
+
+  if ((KnownZero & KnownOne) != 0) {
+    KnownZero.clearAllBits();
+    KnownOne.clearAllBits();
+  }
 }
 
 // Compute known bits from a shift operator, including those with a
 // non-constant shift amount. KnownZero and KnownOne are the outputs of this
 // function. KnownZero2 and KnownOne2 are pre-allocated temporaries with the
 // same bit width as KnownZero and KnownOne. KZF and KOF are operator-specific
 // functors that, given the known-zero or known-one bits respectively, and a
 // shift amount, compute the implied known-zero or known-one bits of the shift

llvm/trunk/test/Transforms/InstSimplify/assume.ll

 ; NOTE: Assertions have been autogenerated by update_test_checks.py
 ; RUN: opt -instsimplify -S < %s | FileCheck %s
 
 define void @test1() {
 ; CHECK-LABEL: @test1(
 ; CHECK:         ret void
 ;
   call void @llvm.assume(i1 1)
   ret void
 
 }
 
+; The alloca guarantees that the low bits of %a are zero because of alignment.
+; The assume says the opposite. The assume is processed last, so that's the 
+; return value. There's no way to win (we can't undo transforms that happened
+; based on half-truths), so just don't crash.
+
+define i64 @PR31809() {
+; CHECK-LABEL: @PR31809(
+; CHECK-NEXT:    ret i64 3
+;
+  %a = alloca i32
+  %t1 = ptrtoint i32* %a to i64
+  %cond = icmp eq i64 %t1, 3
+  call void @llvm.assume(i1 %cond)
+  ret i64 %t1
+}
+
+; Similar to above: there's no way to know which assumption is truthful,
+; so just don't crash. The second icmp+assume gets processed later, so that
+; determines the return value. This can be improved by permanently invalidating
+; the cached assumptions for this function. 
+
+define i8 @conflicting_assumptions(i8 %x) {
+; CHECK-LABEL: @conflicting_assumptions(
+; CHECK-NEXT:    call void @llvm.assume(i1 false)
+; CHECK-NEXT:    [[COND2:%.*]] = icmp eq i8 %x, 4
+; CHECK-NEXT:    call void @llvm.assume(i1 [[COND2]])
+; CHECK-NEXT:    ret i8 5
+;
+  %add = add i8 %x, 1
+  %cond1 = icmp eq i8 %x, 3
+  call void @llvm.assume(i1 %cond1)
+  %cond2 = icmp eq i8 %x, 4
+  call void @llvm.assume(i1 %cond2)
+  ret i8 %add
+}
+
 declare void @llvm.assume(i1) nounwind