[ValueTracking] Improve ComputeNumSignBits to handle Trunc

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

3315–3325

return 1 here, we don't want to fall through to computeKnownBits (the ComptueNumSignBits will have already used it if possible).

3319

I don't think this is right for vectors. You're taking the size of the full vector here, not of the vector elements. Using U->getOperand(0)->getType()->getScalarSizeInBits() should be fine here (as trunc is only defined on integers, so we don't need fancy DL machinery).

Please also add a vector test.

3320

nit: Omit braces for single-line if.

[resistor]

llvm/lib/Analysis/ValueTracking.cpp

3315–3325

I don't think that's the case? We invoked ComputeNumSignBits on the input to the trunc, so we haven't yet had an opportunity to use computeKnownBits results for the output.

[resistor]

Update for test comments and add tests.

[nikic]

llvm/lib/Analysis/ValueTracking.cpp

3315–3325

Hm, I guess you are right. If the truncated part doesn't have sign bits and the part directly following has more than one known zero/one bits, then the computeKnownBits() call is still useful.

Do we already have a test that fails if it is removed?

llvm/test/Transforms/InstCombine/vector-trunc.ll

25

It would be slightly better to test the values where the behavior flips, so I guess that should be a shift by 17 above and by 16 here.

42

Am I missing something, or is this test the same as the previous one?

[resistor]

Update for feedback

llvm/lib/Analysis/ValueTracking.cpp

3315–3325

No test currently fails, so I've gone ahead and changed it.

[nikic]

LGTM

llvm/lib/Analysis/ValueTracking.cpp

case Instruction::PHI: {
         if (Tmp == 1) return Tmp;
         RecQ.CxtI = PN->getIncomingBlock(i)->getTerminator();
         Tmp = std::min(
             Tmp, ComputeNumSignBits(PN->getIncomingValue(i), Depth + 1, RecQ));
       }
       return Tmp;
     }
 
-    case Instruction::Trunc:
-      // FIXME: it's tricky to do anything useful for this, but it is an
-      // important case for targets like X86.
-      break;
+    case Instruction::Trunc: {
+      // If the input contained enough sign bits that some remain after the
+      // truncation, then we can make use of that. Otherwise we don't know
+      // anything.
+      Tmp = ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
+      unsigned OperandTyBits = U->getOperand(0)->getType()->getScalarSizeInBits();
+      if (Tmp > (OperandTyBits - TyBits))
+        return Tmp - (OperandTyBits - TyBits);
+
+      return 1;
+    }
 
     case Instruction::ExtractElement:
       // Look through extract element. At the moment we keep this simple and
       // skip tracking the specific element. But at least we might find
       // information valid for all elements of the vector (for example if vector
       // is sign extended, shifted, etc).
       return ComputeNumSignBits(U->getOperand(0), Depth + 1, Q);
 

llvm/test/Transforms/InstCombine/high-bit-signmask-with-trunc.ll

;
   %r = sub i32 0, %t1
   ret i32 %r
 }
 
 define i32 @n10(i64 %x) {
 ; CHECK-LABEL: @n10(
 ; CHECK-NEXT:    [[T0_NEG:%.*]] = ashr i64 [[X:%.*]], 63
 ; CHECK-NEXT:    [[T1_NEG:%.*]] = trunc i64 [[T0_NEG]] to i32
-; CHECK-NEXT:    [[R:%.*]] = add i32 [[T1_NEG]], 1
+; CHECK-NEXT:    [[R:%.*]] = add nsw i32 [[T1_NEG]], 1
 ; CHECK-NEXT:    ret i32 [[R]]
 ;
   %t0 = lshr i64 %x, 63
   %t1 = trunc i64 %t0 to i32
   %r = sub i32 1, %t1
   ret i32 %r
 }

llvm/test/Transforms/InstCombine/negated-bitmask.ll

;
   ret <4 x i32> %neg
 }
 
 define i8 @sub_mask1_trunc_lshr(i64 %a0) {
 ; CHECK-LABEL: @sub_mask1_trunc_lshr(
 ; CHECK-NEXT:    [[TMP1:%.*]] = shl i64 [[A0:%.*]], 48
 ; CHECK-NEXT:    [[TMP2:%.*]] = ashr i64 [[TMP1]], 63
 ; CHECK-NEXT:    [[TMP3:%.*]] = trunc i64 [[TMP2]] to i8
-; CHECK-NEXT:    [[NEG:%.*]] = add i8 [[TMP3]], 10
+; CHECK-NEXT:    [[NEG:%.*]] = add nsw i8 [[TMP3]], 10
 ; CHECK-NEXT:    ret i8 [[NEG]]
 ;
   %shift = lshr i64 %a0, 15
   %trunc = trunc i64 %shift to i8
   %mask = and i8 %trunc, 1
   %neg = sub i8 10, %mask
   ret i8 %neg
 }
 
 define i32 @sub_sext_mask1_trunc_lshr(i64 %a0) {
 ; CHECK-LABEL: @sub_sext_mask1_trunc_lshr(
 ; CHECK-NEXT:    [[TMP1:%.*]] = shl i64 [[A0:%.*]], 48
 ; CHECK-NEXT:    [[TMP2:%.*]] = ashr i64 [[TMP1]], 63
 ; CHECK-NEXT:    [[TMP3:%.*]] = trunc i64 [[TMP2]] to i8
-; CHECK-NEXT:    [[NARROW:%.*]] = add i8 [[TMP3]], 10
+; CHECK-NEXT:    [[NARROW:%.*]] = add nsw i8 [[TMP3]], 10
 ; CHECK-NEXT:    [[NEG:%.*]] = zext i8 [[NARROW]] to i32
 ; CHECK-NEXT:    ret i32 [[NEG]]
 ;
   %shift = lshr i64 %a0, 15
   %trunc = trunc i64 %shift to i8
   %mask = and i8 %trunc, 1
   %sext = sext i8 %mask to i32
   %neg = sub i32 10, %sext

llvm/test/Transforms/InstCombine/vector-trunc.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -passes=instcombine -S | FileCheck %s
+
+define <4 x i16> @trunc_add_nsw(<4 x i32> %0) {
+; CHECK-LABEL: @trunc_add_nsw(
+; CHECK-NEXT:    [[TMP2:%.*]] = ashr <4 x i32> [[TMP0:%.*]], <i32 17, i32 17, i32 17, i32 17>
+; CHECK-NEXT:    [[TMP3:%.*]] = trunc <4 x i32> [[TMP2]] to <4 x i16>
+; CHECK-NEXT:    [[TMP4:%.*]] = add nsw <4 x i16> [[TMP3]], <i16 1, i16 1, i16 1, i16 1>
+; CHECK-NEXT:    ret <4 x i16> [[TMP4]]
+;
+  %2 = ashr <4 x i32> %0, <i32 17, i32 17, i32 17, i32 17>
+  %3 = trunc <4 x i32> %2 to <4 x i16>
+  %4 = add <4 x i16> %3, <i16 1, i16 1, i16 1, i16 1>
+  ret <4 x i16> %4
+}
+
+define <4 x i16> @trunc_add_no_nsw(<4 x i32> %0) {
+; CHECK-LABEL: @trunc_add_no_nsw(
+; CHECK-NEXT:    [[TMP2:%.*]] = lshr <4 x i32> [[TMP0:%.*]], <i32 16, i32 16, i32 16, i32 16>
+; CHECK-NEXT:    [[TMP3:%.*]] = trunc <4 x i32> [[TMP2]] to <4 x i16>
+; CHECK-NEXT:    [[TMP4:%.*]] = add <4 x i16> [[TMP3]], <i16 1, i16 1, i16 1, i16 1>
+; CHECK-NEXT:    ret <4 x i16> [[TMP4]]
+;
+  %2 = ashr <4 x i32> %0, <i32 16, i32 16, i32 16, i32 16>
+  %3 = trunc <4 x i32> %2 to <4 x i16>
+  %4 = add <4 x i16> %3, <i16 1, i16 1, i16 1, i16 1>
+  ret <4 x i16> %4
+}
+
+define <4 x i16> @trunc_add_mixed(<4 x i32> %0) {
+; CHECK-LABEL: @trunc_add_mixed(
+; CHECK-NEXT:    [[TMP2:%.*]] = ashr <4 x i32> [[TMP0:%.*]], <i32 17, i32 16, i32 17, i32 16>
+; CHECK-NEXT:    [[TMP3:%.*]] = trunc <4 x i32> [[TMP2]] to <4 x i16>
+; CHECK-NEXT:    [[TMP4:%.*]] = add <4 x i16> [[TMP3]], <i16 1, i16 1, i16 1, i16 1>
+; CHECK-NEXT:    ret <4 x i16> [[TMP4]]
+;
+  %2 = ashr <4 x i32> %0, <i32 17, i32 16, i32 17, i32 16>
+  %3 = trunc <4 x i32> %2 to <4 x i16>
+  %4 = add <4 x i16> %3, <i16 1, i16 1, i16 1, i16 1>
+  ret <4 x i16> %4
+}