[SCEV] Pass an explicit context to computeKnownBits

[reames]

Summary

This actually changes less than it appears. computeKnownBits will chose it's own context if one is not passed in. However, since it doesn't know which function is being queried, it can't use an context for the non-instruction case. So the only actual change in behavior here is for arguments, global values, etc..

The test changes are a bit weird, but I left them in (as opposed to rebasing over them) as I think it's relevant. The interesting instruction has to come before the assume or the ephemeral value logic ignores the assume. That's, well, a bit weird.

[nikic]

I don't think this is solving the problem in the right place -- this is a general computeKnownBits() issue, not specific to SCEV. See D93974 for an alternative approach, and the discussion there regarding how to avoid the ephemeral value issue.

[reames]

In D97077#2575360, @nikic wrote:

I don't think this is solving the problem in the right place -- this is a general computeKnownBits() issue, not specific to SCEV. See D93974 for an alternative approach, and the discussion there regarding how to avoid the ephemeral value issue.

Note: Deleted because I had a silly mistake in my framing, will comment again with a fixed comment.

[nikic]

FWIW, this is basically the patch I have in mind: https://gist.github.com/nikic/10e0538a45093258e43851e57e5180f1

[reames]

(re-post of an earlier comment with mistakes fixed and more context added)

In D97077#2575360, @nikic wrote:

I don't think this is solving the problem in the right place -- this is a general computeKnownBits() issue, not specific to SCEV. See D93974 for an alternative approach, and the discussion there regarding how to avoid the ephemeral value issue.

These are definitely related, but not, I think, directly the same. I'd actually started with an approach very similar to that review before switching course. I went back and cleaned up what I had. That's now posted as D97099.

Right now, I see three related issues: 1) arguments should use the first instruction in the function as context, 2) non-instruction values (such as globals!) should use the first instruction in the function as context, and 3) we should not bail out on an assume which is the context instruction.

The linked patch tries to target (1) and (3). This patch specifically only targets (1) and and maybe (2). The choice not to include (3) was very deliberate to allow step wise progress. We do need a generic solution to (3), but it shouldn't block (1) or (2).

On (2), this patch does not handle that case. It could - and to be honest, I originally thought it did - but as shown by the test case for constant expressions it doesn't currently work out. I'll will note that (2) can not (in general) be done inside computeKnownBits. Why? Because we don't know the function context it's invoked in. (Though, we might be able to play some games with the analyzes as dom tree and assumption cache are tied to a single function scope.)

I believe we should move forward with either this patch or D97099 in the near term. Both are surgical improvements, and don't require solving the (fairly hard) item #3.

[reames]

A common issue to all four alternative approaches has come up in the review for D97092. Marking this as Plan Changes until discussion converges and we decide what to do about the common issue.

llvm/lib/Analysis/ScalarEvolution.cpp

if (const SCEVUnknown *U = dyn_cast<SCEVUnknown>(S)) {
     // Check if the IR explicitly contains !range metadata.
     Optional<ConstantRange> MDRange = GetRangeFromMetadata(U->getValue());
     if (MDRange.hasValue())
       ConservativeResult = ConservativeResult.intersectWith(MDRange.getValue(),
                                                             RangeType);
 
     // See if ValueTracking can give us a useful range.
     const DataLayout &DL = getDataLayout();
-    KnownBits Known = computeKnownBits(U->getValue(), DL, 0, &AC, nullptr, &DT);
+    const Instruction *CxtI = dyn_cast<Instruction>(U->getValue());
+    if (!CxtI)
+      CxtI = &*(F.getEntryBlock().begin());
+    KnownBits Known = computeKnownBits(U->getValue(), DL, 0, &AC, CxtI, &DT);
     if (Known.getBitWidth() != BitWidth)
       Known = Known.zextOrTrunc(BitWidth);
     // If Known does not result in full-set, intersect with it.
     if (Known.getMinValue() != Known.getMaxValue() + 1)
       ConservativeResult = ConservativeResult.intersectWith(
           ConstantRange(Known.getMinValue(), Known.getMaxValue() + 1),
           RangeType);
 
     // ValueTracking may be able to compute a tighter result for the number of
     // sign bits than for the value of those sign bits.
-    unsigned NS = ComputeNumSignBits(U->getValue(), DL, 0, &AC, nullptr, &DT);
+    unsigned NS = ComputeNumSignBits(U->getValue(), DL, 0, &AC, CxtI, &DT);
     // If the pointer size is larger than the index size type, this can cause
     // NS to be larger than BitWidth. So compensate for this.
     if (U->getType()->isPointerTy()) {
       unsigned ptrSize = DL.getPointerTypeSizeInBits(U->getType());
       int ptrIdxDiff = ptrSize - BitWidth;
       if (ptrIdxDiff > 0 && ptrSize > BitWidth && NS > (unsigned)ptrIdxDiff)
         NS -= ptrIdxDiff;
     }

llvm/test/Analysis/ScalarEvolution/ranges.ll

 
 define i32 @ashr(i32 %a) {
 ; CHECK-LABEL: 'ashr'
 ; CHECK-NEXT:  Classifying expressions for: @ashr
 ; CHECK-NEXT:    %ashr = ashr i32 %a, 31
 ; CHECK-NEXT:    --> %ashr U: [0,1) S: [0,1)
 ; CHECK-NEXT:  Determining loop execution counts for: @ashr
 ;
+  %ashr = ashr i32 %a, 31
   %pos = icmp sge i32 %a, 0
   call void @llvm.assume(i1 %pos)
-  %ashr = ashr i32 %a, 31
   ret i32 %ashr
 }
 
 define i32 @shl(i32 %a) {
 ; CHECK-LABEL: 'shl'
 ; CHECK-NEXT:  Classifying expressions for: @shl
 ; CHECK-NEXT:    %res = shl i32 %a, 2
 ; CHECK-NEXT:    --> (4 * %a) U: [0,-3) S: [-2147483648,2147483645)
 ; CHECK-NEXT:  Determining loop execution counts for: @shl
 ;
+  %res = shl i32 %a, 2
   %pos = icmp slt i32 %a, 1024
   call void @llvm.assume(i1 %pos)
-  %res = shl i32 %a, 2
   ret i32 %res
 }
 
 define i32 @lshr(i32 %a) {
 ; CHECK-LABEL: 'lshr'
 ; CHECK-NEXT:  Classifying expressions for: @lshr
 ; CHECK-NEXT:    %res = lshr i32 %a, 31
-; CHECK-NEXT:    --> (%a /u -2147483648) U: [0,2) S: [0,2)
+; CHECK-NEXT:    --> (%a /u -2147483648) U: [0,1) S: [0,1)
 ; CHECK-NEXT:  Determining loop execution counts for: @lshr
 ;
+  %res = lshr i32 %a, 31
   %pos = icmp sge i32 %a, 0
   call void @llvm.assume(i1 %pos)
-  %res = lshr i32 %a, 31
   ret i32 %res
 }
 
 
 define i32 @udiv(i32 %a) {
 ; CHECK-LABEL: 'udiv'
 ; CHECK-NEXT:  Classifying expressions for: @udiv
 ; CHECK-NEXT:    %res = udiv i32 %a, -2147483648
-; CHECK-NEXT:    --> (%a /u -2147483648) U: [0,2) S: [0,2)
+; CHECK-NEXT:    --> (%a /u -2147483648) U: [0,1) S: [0,1)
 ; CHECK-NEXT:  Determining loop execution counts for: @udiv
 ;
+  %res = udiv i32 %a, 2147483648
   %pos = icmp sge i32 %a, 0
   call void @llvm.assume(i1 %pos)
-  %res = udiv i32 %a, 2147483648
   ret i32 %res
 }
 
-define i64 @sext(i32 %a) {
+define i64 @sext(i8 %a) {
 ; CHECK-LABEL: 'sext'
 ; CHECK-NEXT:  Classifying expressions for: @sext
-; CHECK-NEXT:    %res = sext i32 %a to i64
-; CHECK-NEXT:    --> (sext i32 %a to i64) U: [-2147483648,2147483648) S: [-2147483648,2147483648)
+; CHECK-NEXT:    %res = sext i8 %a to i64
+; CHECK-NEXT:    --> (zext i8 %a to i64) U: [0,128) S: [0,128)
 ; CHECK-NEXT:  Determining loop execution counts for: @sext
 ;
-  %pos = icmp sge i32 %a, 0
+  %res = sext i8 %a to i64
+  %pos = icmp sge i8 %a, 0
   call void @llvm.assume(i1 %pos)
-  %res = sext i32 %a to i64
   ret i64 %res
 }
 
-define i64 @zext(i32 %a) {
+define i64 @zext(i8 %a) {
 ; CHECK-LABEL: 'zext'
 ; CHECK-NEXT:  Classifying expressions for: @zext
-; CHECK-NEXT:    %res = zext i32 %a to i64
-; CHECK-NEXT:    --> (zext i32 %a to i64) U: [0,4294967296) S: [0,4294967296)
+; CHECK-NEXT:    %res = zext i8 %a to i64
+; CHECK-NEXT:    --> (zext i8 %a to i64) U: [0,128) S: [0,128)
 ; CHECK-NEXT:  Determining loop execution counts for: @zext
 ;
-  %pos = icmp sge i32 %a, 0
+  %res = zext i8 %a to i64
+  %pos = icmp sge i8 %a, 0
   call void @llvm.assume(i1 %pos)
-  %res = zext i32 %a to i64
   ret i64 %res
 }