[IVDescriptor] Make sure the sign is included for negative extension.

[fhahn]

Summary

At the moment, computeRecurrenceType does not include any sign bits in
the maximum bit width. If the value can be negative, this means the sign
bit will be missing and the sext won't properly extend the value.

If the value can be negative, increment the bitwidth by one to make sure
there is at least one sign bit in the result value.

Note that the increment is also needed *if* the value is *known* to be
negative, as a sign bit needs to be preserved for the sext to work.

Note that this at the moment prevents vectorization, because the
analysis computes i1 as type for the recurrence when looking through the
AND in lookThroughAnd.

Fixes PR51794, PR52485.

[fhahn]

Ping :)

should also fix PR51794

[fhahn]

In D113056#3127479, @fhahn wrote:

Ping :)

should also fix PR51794

Should be PR52485....

[RKSimon]

In D113056#3127482, @fhahn wrote:

In D113056#3127479, @fhahn wrote:

Ping :)

should also fix PR51794

Should be PR52485....

Worth an extra test case?

[fhahn]

In D113056#3127502, @RKSimon wrote:

In D113056#3127482, @fhahn wrote:

In D113056#3127479, @fhahn wrote:

Ping :)

should also fix PR51794

Should be PR52485....

Worth an extra test case?

Rebased on top of committed test from PR52485.

[spatel]

LGTM

llvm/lib/Analysis/IVDescriptors.cpp

149–151

typo: "at at"

llvm/lib/Analysis/IVDescriptors.cpp

if (MaxBitWidth == DL.getTypeSizeInBits(Exit->getType()) && AC && DT) {
     auto NumTypeBits = DL.getTypeSizeInBits(Exit->getType());
     MaxBitWidth = NumTypeBits - NumSignBits;
     KnownBits Bits = computeKnownBits(Exit, DL);
     if (!Bits.isNonNegative()) {
       // If the value is not known to be non-negative, we set IsSigned to true,
       // meaning that we will use sext instructions instead of zext
       // instructions to restore the original type.
       IsSigned = true;
-      if (!Bits.isNegative())
-        // If the value is not known to be negative, we don't known what the
-        // upper bit is, and therefore, we don't know what kind of extend we
-        // will need. In this case, just increase the bit width by one bit and
-        // use sext.
-        ++MaxBitWidth;
+      // Make sure at at least one sign bit is included in the result, so it
+      // will get properly sign-extended.
     }
   }
   if (!isPowerOf2_64(MaxBitWidth))
     MaxBitWidth = NextPowerOf2(MaxBitWidth);
 
   return std::make_pair(Type::getIntNTy(Exit->getContext(), MaxBitWidth),
                         IsSigned);
 }

llvm/test/Transforms/LoopVectorize/reduction-small-size.ll

 
 for.end:
   %tmp1 = phi i32 [ %r.next, %for.body ]
   ret i32 %tmp1
 }
 
 define i32 @pr51794_signed_negative(i16 %iv.start, i32 %xor.start) {
 ; CHECK-LABEL: define {{.*}} @pr51794_signed_negative(
-; CHECK:   [[XOR_START:%.+]] = insertelement <4 x i32> zeroinitializer, i32 %xor.start, i32 0
-; CHECK-LABEL: vector.body:
-; CHECK:         [[XOR_RED:%.+]] = phi <4 x i32> [ [[XOR_START]], %vector.ph ], [ [[XOR_SEXT:%.+]], %vector.body ]
-; CHECK:         [[AND:%.+]] = and <4 x i32> [[XOR_RED]], <i32 1, i32 1, i32 1, i32 1>
-; CHECK-NEXT:    [[XOR:%.+]] = xor <4 x i32> [[AND]], <i32 -1, i32 -1, i32 -1, i32 -1>
-; CHECK:         [[XOR_TRUNC:%.+]] = trunc <4 x i32> [[XOR]] to <4 x i1>
-; CHECK-NEXT:    [[XOR_SEXT]] = sext <4 x i1> [[XOR_TRUNC]] to <4 x i32>
-;
-; CHECK-LABEL: middle.block:
-; CHECK-NEXT:   [[RES_TRUNC:%.+]] = trunc <4 x i32> [[XOR_SEXT]] to <4 x i1>
-; CHECK-NEXT:   [[RES_RED:%.+]]  = call i1 @llvm.vector.reduce.xor.v4i1(<4 x i1> [[RES_TRUNC]])
-; CHECK-NEXT:   sext i1 [[RES_RED]] to i32
+; CHECK-NOT: vector.body:
 ;
 entry:
   br label %loop
 
 loop:
   %xor.red = phi i32 [ %xor.start, %entry ], [ %xor, %loop ]
   %iv = phi i16 [ %iv.start, %entry ], [ %iv.next, %loop ]
   %iv.next = add i16 %iv, -1
   %and = and i32 %xor.red, 1
   %xor = xor i32 %and, -1
   %tobool.not = icmp eq i16 %iv.next, 0
   br i1 %tobool.not, label %exit, label %loop
 
 exit:
   %xor.lcssa = phi i32 [ %xor, %loop ]
   ret i32 %xor.lcssa
 }
 
 define i32 @pr52485_signed_negative(i32 %xor.start) {
 ; CHECK-LABEL: define {{.*}} @pr52485_signed_negative(
-; CHECK:   [[XOR_START:%.+]] = insertelement <4 x i32> zeroinitializer, i32 %xor.start, i32 0
-; CHECK-LABEL: vector.body:
-; CHECK:         [[XOR_RED:%.+]] = phi <4 x i32> [ [[XOR_START]], %vector.ph ], [ [[XOR_SEXT:%.+]], %vector.body ]
-; CHECK:         [[AND:%.+]] = and <4 x i32> [[XOR_RED]], <i32 255, i32 255, i32 255, i32 255>
-; CHECK-NEXT:    [[XOR:%.+]] = xor <4 x i32> [[AND]], <i32 -9, i32 -9, i32 -9, i32 -9>
-; CHECK:         [[XOR_TRUNC:%.+]] = trunc <4 x i32> [[XOR]] to <4 x i8>
-; CHECK-NEXT:    [[XOR_SEXT]] = sext <4 x i8> [[XOR_TRUNC]] to <4 x i32>
-;
-; CHECK-LABEL: middle.block:
-; CHECK-NEXT:   [[RES_TRUNC:%.+]] = trunc <4 x i32> [[XOR_SEXT]] to <4 x i8>
-; CHECK-NEXT:   [[RES_RED:%.+]]  = call i8 @llvm.vector.reduce.xor.v4i8(<4 x i8> [[RES_TRUNC]])
-; CHECK-NEXT:   sext i8 [[RES_RED]] to i32
+; CHECK-NOT: vector.body:
 ;
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [ -23, %entry ], [ %iv.next, %loop ]
   %xor.red = phi i32 [ %xor.start, %entry ], [ %xor, %loop ]
   %and = and i32 %xor.red, 255