[InstCombine] Try to narrow expr if trunc cannot be removed.

[fhahn]

Summary

Narrowing an input expression of a truncate to a type larger than the
result of the truncate won't allow removing the truncate, but it may
enable further optimizations, e.g. allowing for larger vectorization
factors.

For now this is intentionally limited to integer types only, to avoid
producing new vector ops that might not be suitable for the target.

If we know that the only user is a trunc, we can also be allow more
cases, e.g. also shortening expressions with some additional shifts.

I would appreciate feedback on the best place to do such a narrowing.

This fixes PR43580.

[RKSimon]

vector test cases? I realize for PR43580 we can get this done before vectorization

[spatel]

In D82973#2125918, @RKSimon wrote:

vector test cases? I realize for PR43580 we can get this done before vectorization

We could add tests, but I don't think we can see changes as long as we are using shouldChangeType() to guard the transform:

bool InstCombiner::shouldChangeType(Type *From, Type *To) const {
  // TODO: This could be extended to allow vectors. Datalayout changes might be
  // needed to properly support that.
  if (!From->isIntegerTy() || !To->isIntegerTy())
    return false;

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

725

DestTy should be NewDestTy here?

[fhahn]

Use NewDestTy instead DestTy

In D82973#2125923, @spatel wrote:

In D82973#2125918, @RKSimon wrote:

vector test cases? I realize for PR43580 we can get this done before vectorization

We could add tests, but I don't think we can see changes as long as we are using shouldChangeType() to guard the transform:

Thanks, I added a vector test, but it won't be transformed currently, as I don't think there's an easy way to check if the new vector would be legal (as noted in shouldChangeType. Also, limiting to integer types allows using getExtendedType.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

725

Still reads as DestTy to me

[fhahn]

Actually upload patch to use NewDestTy instead of DestTy........

[lebedev.ri]

LG

llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp

LLVM_DEBUG(
         dbgs() << "ICE: EvaluateInDifferentType converting expression type"
                   " to avoid cast: "
                << Trunc << '\n');
     Value *Res = EvaluateInDifferentType(Src, DestTy, false);
     assert(Res->getType() == DestTy);
     return replaceInstUsesWith(Trunc, Res);
   }
 
+  // For integer types, check if we can shorten the entire input expression to
+  // DestWidth * 2, which won't allow removing the truncate, but reducing the
+  // width may enable further optimizations, e.g. allowing for larger
+  // vectorization factors.
+  if (auto *DestITy = dyn_cast<IntegerType>(DestTy)) {
+    if (DestWidth * 2 < SrcWidth) {
+      auto *NewDestTy = DestITy->getExtendedType();
+      if (shouldChangeType(SrcTy, NewDestTy) &&
+          canEvaluateTruncated(Src, NewDestTy, *this, &Trunc)) {
+        LLVM_DEBUG(
+            dbgs() << "ICE: EvaluateInDifferentType converting expression type"
+                      " to reduce the width of operand of"
+                   << Trunc << '\n');
+        Value *Res = EvaluateInDifferentType(Src, NewDestTy, false);
+        return new TruncInst(Res, DestTy);
+      }
+    }
+  }
+
   // Test if the trunc is the user of a select which is part of a
   // minimum or maximum operation. If so, don't do any more simplification.
   // Even simplifying demanded bits can break the canonical form of a
   // min/max.
   Value *LHS, *RHS;
   if (SelectInst *Sel = dyn_cast<SelectInst>(Src))
     if (matchSelectPattern(Sel, LHS, RHS).Flavor != SPF_UNKNOWN)
       return nullptr;

llvm/test/Transforms/InstCombine/trunc-binop-ext.ll

;
   %b = mul <2 x i32> %y32op0, %x32
   %r = trunc <2 x i32> %b to <2 x i16>
   ret <2 x i16> %r
 }
 
 ; Test cases for PR43580
 define i8 @narrow_zext_ashr_keep_trunc(i8 %i1, i8 %i2) {
 ; CHECK-LABEL: @narrow_zext_ashr_keep_trunc(
-; CHECK-NEXT:    [[I1_EXT:%.*]] = sext i8 [[I1:%.*]] to i32
-; CHECK-NEXT:    [[I2_EXT:%.*]] = sext i8 [[I2:%.*]] to i32
-; CHECK-NEXT:    [[SUB:%.*]] = add nsw i32 [[I1_EXT]], [[I2_EXT]]
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[SUB]], 1
-; CHECK-NEXT:    [[T:%.*]] = trunc i32 [[TMP1]] to i8
+; CHECK-NEXT:    [[I1_EXT:%.*]] = sext i8 [[I1:%.*]] to i16
+; CHECK-NEXT:    [[I2_EXT:%.*]] = sext i8 [[I2:%.*]] to i16
+; CHECK-NEXT:    [[SUB:%.*]] = add nsw i16 [[I1_EXT]], [[I2_EXT]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i16 [[SUB]], 1
+; CHECK-NEXT:    [[T:%.*]] = trunc i16 [[TMP1]] to i8
 ; CHECK-NEXT:    ret i8 [[T]]
 ;
   %i1.ext = sext i8 %i1 to i32
   %i2.ext = sext i8 %i2 to i32
   %sub = add nsw i32 %i1.ext, %i2.ext
   %shift = ashr i32 %sub, 1
   %t = trunc i32 %shift to i8
   ret i8 %t
 }
 
 define i8 @narrow_zext_ashr_keep_trunc2(i9 %i1, i9 %i2) {
 ; CHECK-LABEL: @narrow_zext_ashr_keep_trunc2(
-; CHECK-NEXT:    [[I1_EXT1:%.*]] = zext i9 [[I1:%.*]] to i64
-; CHECK-NEXT:    [[I2_EXT2:%.*]] = zext i9 [[I2:%.*]] to i64
-; CHECK-NEXT:    [[SUB:%.*]] = add nuw nsw i64 [[I1_EXT1]], [[I2_EXT2]]
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i64 [[SUB]], 1
-; CHECK-NEXT:    [[T:%.*]] = trunc i64 [[TMP1]] to i8
+; CHECK-NEXT:    [[I1_EXT1:%.*]] = zext i9 [[I1:%.*]] to i16
+; CHECK-NEXT:    [[I2_EXT2:%.*]] = zext i9 [[I2:%.*]] to i16
+; CHECK-NEXT:    [[SUB:%.*]] = add nuw nsw i16 [[I1_EXT1]], [[I2_EXT2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i16 [[SUB]], 1
+; CHECK-NEXT:    [[T:%.*]] = trunc i16 [[TMP1]] to i8
 ; CHECK-NEXT:    ret i8 [[T]]
 ;
   %i1.ext = sext i9 %i1 to i64
   %i2.ext = sext i9 %i2 to i64
   %sub = add nsw i64 %i1.ext, %i2.ext
   %shift = ashr i64 %sub, 1
   %t = trunc i64 %shift to i8
   ret i8 %t
 }
 
 define i7 @narrow_zext_ashr_keep_trunc3(i8 %i1, i8 %i2) {
 ; CHECK-LABEL: @narrow_zext_ashr_keep_trunc3(
-; CHECK-NEXT:    [[I1_EXT1:%.*]] = zext i8 [[I1:%.*]] to i64
-; CHECK-NEXT:    [[I2_EXT2:%.*]] = zext i8 [[I2:%.*]] to i64
-; CHECK-NEXT:    [[SUB:%.*]] = add nuw nsw i64 [[I1_EXT1]], [[I2_EXT2]]
-; CHECK-NEXT:    [[TMP1:%.*]] = lshr i64 [[SUB]], 1
-; CHECK-NEXT:    [[T:%.*]] = trunc i64 [[TMP1]] to i7
+; CHECK-NEXT:    [[I1_EXT1:%.*]] = zext i8 [[I1:%.*]] to i14
+; CHECK-NEXT:    [[I2_EXT2:%.*]] = zext i8 [[I2:%.*]] to i14
+; CHECK-NEXT:    [[SUB:%.*]] = add nuw nsw i14 [[I1_EXT1]], [[I2_EXT2]]
+; CHECK-NEXT:    [[TMP1:%.*]] = lshr i14 [[SUB]], 1
+; CHECK-NEXT:    [[T:%.*]] = trunc i14 [[TMP1]] to i7
 ; CHECK-NEXT:    ret i7 [[T]]
 ;
   %i1.ext = sext i8 %i1 to i64
   %i2.ext = sext i8 %i2 to i64
   %sub = add nsw i64 %i1.ext, %i2.ext
   %shift = ashr i64 %sub, 1
   %t = trunc i64 %shift to i7
   ret i7 %t