[SLP] Distinguish "demanded and shrinkable" from "demanded and not shrinkable" values when determining the minimum bitwidth

[haicheng]

Summary

We use two approaches for determining the minimum bitwidth.

1. Demanded bits
2. Value tracking

If demanded bits doesn't result in a narrower type, we then try value tracking. We need this if we want to root SLP trees with the indices of getelementptr instructions since all the bits of the indices are demanded.

But there is a missing piece though. We need to be able to distinguish "demanded and shrinkable" from "demanded and not shrinkable". For example, the bits of %i in

%i = sext i32 %e1 to i64 
%gep = getelementptr inbounds i64, i64* %p, i64 %i

are demanded, but we can shrink %i's type to i32 because it won't change the result of the getelementptr. On the other hand, in

%tmp15 = sext i32 %tmp14 to i64 
%tmp16 = insertvalue { i64, i64 } undef, i64 %tmp15, 0

it doesn't make sense to shrink %tmp15 and we can skip the value tracking.

This patch still adds z|sext to demote list, but does not use value tracking if they are not shrinkable. So, cast<vect>, trunc <vect>, exctract <vect>, cast <extract> are only generated when they are useful (shrinkable). For now, this patch only considers gep index as a shrinkable usage.

Most words above are from @mssimpso .

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4336 ↗

(On Diff #139716)

You don't capture anything in lambda, so remove & from the capture list.

4337 ↗

(On Diff #139716)

What if only begin use is GEP and others are not?

test/Transforms/SLPVectorizer/AArch64/ext-trunc.ll

1 ↗

(On Diff #139716)

1. Commit this test separately as NFC with checks for the current version of the compiler.
2. Generate test checks using utils/update_test_checks.py

3–4 ↗

(On Diff #139716)

Pass this data as test arguments.

[haicheng]

Update to address Alexey's comments. Thank you very much.

lib/Transforms/Vectorize/SLPVectorizer.cpp

4337 ↗

(On Diff #139716)

I think we've checked earlier that there is only one use here.

test/Transforms/SLPVectorizer/AArch64/ext-trunc.ll

1 ↗

(On Diff #139716)

I will commit the separately.

[lebedev.ri]

test/Transforms/SLPVectorizer/AArch64/ext-trunc.ll

1 ↗

(On Diff #139716)

Commit this test separately as NFC with checks for the current version of the compiler.

I will commit the separately.

What i think was meant is, commit the test now, and rebase the differential ontop of that commit,
so the diff actually shows what this differential changes in the testcase.

[haicheng]

test/Transforms/SLPVectorizer/AArch64/ext-trunc.ll

1 ↗

(On Diff #139716)

Thank you for pointing this out. I am working on it now.

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4337 ↗

(On Diff #139800)

You can use just R->user_back()

4337 ↗

(On Diff #139716)

Add the assert, please

test/Transforms/SLPVectorizer/AArch64/ext-trunc.ll

1 ↗

(On Diff #139716)

That's right

[haicheng]

Rebase and update the patch.

[ABataev]

lib/Transforms/Vectorize/SLPVectorizer.cpp

4338 ↗

(On Diff #139811)

Yuu don't need to dereference here if you're using user_back()

test/Transforms/SLPVectorizer/AArch64/ext-trunc.ll

12–14 ↗

(On Diff #139811)

Why you removed some checks generated by utils/update_test_checks.py?

[haicheng]

Updated to address Alexey's latest comments. Thank you again.

[ABataev]

test/Transforms/SLPVectorizer/AArch64/ext-trunc.ll

12–14 ↗

(On Diff #139829)

Add the full check to the original test too

[haicheng]

Rebase the test case.

[haicheng]

Kindly Ping

[mssimpso]

Hi Haicheng,

This looks fine to me, but please wait for Alexey to approve. Thanks.

[ABataev]

LG

llvm/trunk/lib/Transforms/Vectorize/SLPVectorizer.cpp

for (auto *Root : TreeRoot)
     if (!Root->hasOneUse() || Expr.count(*Root->user_begin()))
       return;
 
   // Conservatively determine if we can actually truncate the roots of the
   // expression. Collect the values that can be demoted in ToDemote and
   // additional roots that require investigating in Roots.
   SmallVector<Value *, 32> ToDemote;
   SmallVector<Value *, 4> Roots;
-  for (auto *Root : TreeRoot) {
-    // Do not include top zext/sext/trunc operations to those to be demoted, it
-    // produces noise cast<vect>, trunc <vect>, exctract <vect>, cast <extract>
-    // sequence.
-    if (isa<Constant>(Root))
-      continue;
-    auto *I = dyn_cast<Instruction>(Root);
-    if (!I || !I->hasOneUse() || !Expr.count(I))
-      return;
-    if (isa<ZExtInst>(I) || isa<SExtInst>(I))
-      continue;
-    if (auto *TI = dyn_cast<TruncInst>(I)) {
-      Roots.push_back(TI->getOperand(0));
-      continue;
-    }
+  for (auto *Root : TreeRoot)
     if (!collectValuesToDemote(Root, Expr, ToDemote, Roots))
       return;
-  }
 
   // The maximum bit width required to represent all the values that can be
   // demoted without loss of precision. It would be safe to truncate the roots
   // of the expression to this width.
   auto MaxBitWidth = 8u;
 
   // We first check if all the bits of the roots are demanded. If they're not,
   // we can truncate the roots to this narrower type.
void BoUpSLP::computeMinimumValueSizes() {
   // compute a narrower type. This can happen, for example, if the roots are
   // getelementptr indices. InstCombine promotes these indices to the pointer
   // width. Thus, all their bits are technically demanded even though the
   // address computation might be vectorized in a smaller type.
   //
   // We start by looking at each entry that can be demoted. We compute the
   // maximum bit width required to store the scalar by using ValueTracking to
   // compute the number of high-order bits we can truncate.
-  if (MaxBitWidth == DL->getTypeSizeInBits(TreeRoot[0]->getType())) {
+  if (MaxBitWidth == DL->getTypeSizeInBits(TreeRoot[0]->getType()) &&
+      llvm::all_of(TreeRoot, [](Value *R) {
+        assert(R->hasOneUse() && "Root should have only one use!");
+        return isa<GetElementPtrInst>(R->user_back());
+      })) {
     MaxBitWidth = 8u;
 
     // Determine if the sign bit of all the roots is known to be zero. If not,
     // IsKnownPositive is set to False.
     IsKnownPositive = llvm::all_of(TreeRoot, [&](Value *R) {
       KnownBits Known = computeKnownBits(R, *DL);
       return Known.isNonNegative();
     });

llvm/trunk/test/Transforms/SLPVectorizer/AArch64/ext-trunc.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -slp-vectorizer -mtriple=aarch64--linux-gnu -instcombine < %s | FileCheck %s
 
 target datalayout = "e-m:e-i32:64-i128:128-n32:64-S128"
 
 declare void @foo(i64, i64, i64, i64)
 
 define void @test(<4 x i16> %a, <4 x i16> %b, i64* %p) {
 ; Make sure types of sub and its sources are not extended.
 ; CHECK-LABEL: @test(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[Z0:%.*]] = zext <4 x i16> [[A:%.*]] to <4 x i64>
-; CHECK-NEXT:    [[Z1:%.*]] = zext <4 x i16> [[B:%.*]] to <4 x i64>
-; CHECK-NEXT:    [[SUB0:%.*]] = sub nsw <4 x i64> [[Z0]], [[Z1]]
-; CHECK-NEXT:    [[TMP0:%.*]] = extractelement <4 x i64> [[SUB0]], i32 0
-; CHECK-NEXT:    [[GEP0:%.*]] = getelementptr inbounds i64, i64* [[P:%.*]], i64 [[TMP0]]
+; CHECK-NEXT:    [[Z0:%.*]] = zext <4 x i16> [[A:%.*]] to <4 x i32>
+; CHECK-NEXT:    [[Z1:%.*]] = zext <4 x i16> [[B:%.*]] to <4 x i32>
+; CHECK-NEXT:    [[SUB0:%.*]] = sub nsw <4 x i32> [[Z0]], [[Z1]]
+; CHECK-NEXT:    [[TMP0:%.*]] = extractelement <4 x i32> [[SUB0]], i32 0
+; CHECK-NEXT:    [[TMP1:%.*]] = sext i32 [[TMP0]] to i64
+; CHECK-NEXT:    [[GEP0:%.*]] = getelementptr inbounds i64, i64* [[P:%.*]], i64 [[TMP1]]
 ; CHECK-NEXT:    [[LOAD0:%.*]] = load i64, i64* [[GEP0]], align 4
-; CHECK-NEXT:    [[TMP1:%.*]] = extractelement <4 x i64> [[SUB0]], i32 1
-; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr inbounds i64, i64* [[P]], i64 [[TMP1]]
+; CHECK-NEXT:    [[TMP2:%.*]] = extractelement <4 x i32> [[SUB0]], i32 1
+; CHECK-NEXT:    [[TMP3:%.*]] = sext i32 [[TMP2]] to i64
+; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr inbounds i64, i64* [[P]], i64 [[TMP3]]
 ; CHECK-NEXT:    [[LOAD1:%.*]] = load i64, i64* [[GEP1]], align 4
-; CHECK-NEXT:    [[TMP2:%.*]] = extractelement <4 x i64> [[SUB0]], i32 2
-; CHECK-NEXT:    [[GEP2:%.*]] = getelementptr inbounds i64, i64* [[P]], i64 [[TMP2]]
+; CHECK-NEXT:    [[TMP4:%.*]] = extractelement <4 x i32> [[SUB0]], i32 2
+; CHECK-NEXT:    [[TMP5:%.*]] = sext i32 [[TMP4]] to i64
+; CHECK-NEXT:    [[GEP2:%.*]] = getelementptr inbounds i64, i64* [[P]], i64 [[TMP5]]
 ; CHECK-NEXT:    [[LOAD2:%.*]] = load i64, i64* [[GEP2]], align 4
-; CHECK-NEXT:    [[TMP3:%.*]] = extractelement <4 x i64> [[SUB0]], i32 3
-; CHECK-NEXT:    [[GEP3:%.*]] = getelementptr inbounds i64, i64* [[P]], i64 [[TMP3]]
+; CHECK-NEXT:    [[TMP6:%.*]] = extractelement <4 x i32> [[SUB0]], i32 3
+; CHECK-NEXT:    [[TMP7:%.*]] = sext i32 [[TMP6]] to i64
+; CHECK-NEXT:    [[GEP3:%.*]] = getelementptr inbounds i64, i64* [[P]], i64 [[TMP7]]
 ; CHECK-NEXT:    [[LOAD3:%.*]] = load i64, i64* [[GEP3]], align 4
 ; CHECK-NEXT:    call void @foo(i64 [[LOAD0]], i64 [[LOAD1]], i64 [[LOAD2]], i64 [[LOAD3]])
 ; CHECK-NEXT:    ret void
 ;
 entry:
   %z0 = zext <4 x i16> %a to <4 x i32>
   %z1 = zext <4 x i16> %b to <4 x i32>
   %sub0 = sub <4 x i32> %z0, %z1

llvm/trunk/test/Transforms/SLPVectorizer/X86/partail.ll

 ; CHECK-NEXT:    [[TMP3:%.*]] = insertelement <4 x i32> undef, i32 [[SHR15]], i32 0
 ; CHECK-NEXT:    [[TMP4:%.*]] = insertelement <4 x i32> [[TMP3]], i32 undef, i32 1
 ; CHECK-NEXT:    [[TMP5:%.*]] = insertelement <4 x i32> [[TMP4]], i32 undef, i32 2
 ; CHECK-NEXT:    [[TMP6:%.*]] = insertelement <4 x i32> [[TMP5]], i32 undef, i32 3
 ; CHECK-NEXT:    [[TMP7:%.*]] = select <4 x i1> [[TMP2]], <4 x i32> [[TMP6]], <4 x i32> zeroinitializer
 ; CHECK-NEXT:    [[TMP8:%.*]] = icmp slt <4 x i32> [[TMP7]], undef
 ; CHECK-NEXT:    [[TMP9:%.*]] = select <4 x i1> [[TMP8]], <4 x i32> [[TMP7]], <4 x i32> undef
 ; CHECK-NEXT:    [[TMP10:%.*]] = sext <4 x i32> [[TMP9]] to <4 x i64>
-; CHECK-NEXT:    [[TMP11:%.*]] = extractelement <4 x i64> [[TMP10]], i32 0
-; CHECK-NEXT:    [[ARRAYIDX31:%.*]] = getelementptr inbounds i16*, i16** undef, i64 [[TMP11]]
-; CHECK-NEXT:    [[TMP12:%.*]] = extractelement <4 x i64> [[TMP10]], i32 1
-; CHECK-NEXT:    [[ARRAYIDX31_1:%.*]] = getelementptr inbounds i16*, i16** undef, i64 [[TMP12]]
-; CHECK-NEXT:    [[TMP13:%.*]] = extractelement <4 x i64> [[TMP10]], i32 2
-; CHECK-NEXT:    [[ARRAYIDX31_2:%.*]] = getelementptr inbounds i16*, i16** undef, i64 [[TMP13]]
-; CHECK-NEXT:    [[TMP14:%.*]] = extractelement <4 x i64> [[TMP10]], i32 3
-; CHECK-NEXT:    [[ARRAYIDX31_3:%.*]] = getelementptr inbounds i16*, i16** undef, i64 [[TMP14]]
+; CHECK-NEXT:    [[TMP11:%.*]] = trunc <4 x i64> [[TMP10]] to <4 x i32>
+; CHECK-NEXT:    [[TMP12:%.*]] = extractelement <4 x i32> [[TMP11]], i32 0
+; CHECK-NEXT:    [[TMP13:%.*]] = sext i32 [[TMP12]] to i64
+; CHECK-NEXT:    [[ARRAYIDX31:%.*]] = getelementptr inbounds i16*, i16** undef, i64 [[TMP13]]
+; CHECK-NEXT:    [[TMP14:%.*]] = extractelement <4 x i32> [[TMP11]], i32 1
+; CHECK-NEXT:    [[TMP15:%.*]] = sext i32 [[TMP14]] to i64
+; CHECK-NEXT:    [[ARRAYIDX31_1:%.*]] = getelementptr inbounds i16*, i16** undef, i64 [[TMP15]]
+; CHECK-NEXT:    [[TMP16:%.*]] = extractelement <4 x i32> [[TMP11]], i32 2
+; CHECK-NEXT:    [[TMP17:%.*]] = sext i32 [[TMP16]] to i64
+; CHECK-NEXT:    [[ARRAYIDX31_2:%.*]] = getelementptr inbounds i16*, i16** undef, i64 [[TMP17]]
+; CHECK-NEXT:    [[TMP18:%.*]] = extractelement <4 x i32> [[TMP11]], i32 3
+; CHECK-NEXT:    [[TMP19:%.*]] = sext i32 [[TMP18]] to i64
+; CHECK-NEXT:    [[ARRAYIDX31_3:%.*]] = getelementptr inbounds i16*, i16** undef, i64 [[TMP19]]
 ; CHECK-NEXT:    unreachable
 ;
 entry:
   br label %land.lhs.true
 
 land.lhs.true:                                    ; preds = %entry
   br i1 undef, label %if.then, label %if.end