[LoopVectorize] Refine hasIrregularType predicate

[LemonBoy]

Summary

The hasIrregularType predicate checks whether an array of N values of type Ty is "bitcast-compatible" with a <N x Ty> vector.
The previous check returned invalid results in some cases where there's some padding between the array elements: eg. a 4-element array of u7 values is considered as compatible with <4 x u7>, even though the vector is only loading/storing 28 bits instead of 32.

The problem causes LLVM to generate incorrect code for some targets: for AArch64 the vector loads/stores are lowered in terms of ubfx/bfi, effectively losing the top (N * padding bits).

[craig.topper]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

376

Should we remove the unused VF argument?

[LemonBoy]

Remove unused parameter.

[LemonBoy]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

376

Good catch, fixed.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

375

comment needs updating, there's no given vectorization factor any longer, right?

377

The comment also needs to be updated to not refer to VF I think, as it is gone now. Something like Determine if an array of type Ty is "bit cast compatible" with a vector with the same number of elements.

llvm/test/Transforms/LoopVectorize/irregular_type.ll

5

can you add a comment explaining what the test checks?

[LemonBoy]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

381

CC @david-arm
This slightly different formulation of the check was introduced in c5ba0d33cc060cc06a28a5d9101060afd1c0ee9a.

[LemonBoy]

Update some documentation comments.

[LemonBoy]

Ping ?

[lebedev.ri]

Seems good to me.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

380–381

I wonder why can't we still vectorize such cases,
by instead loading <N x DL.getTypeAllocSizeInBits(Ty)> vector and then truncating it?
(beware of endianness)

[LemonBoy]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

380–381

This was meant to be a hotfix targeting LLVM12.
I've experimented with the widen+truncate strategy and the results are promising (at least on x86), I'll submit a patch once I clean up the code.

[lebedev.ri]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

380–381

This was meant to be a hotfix targeting LLVM12.

Sure, i wasn't even suggesting doing that here.

I've experimented with the widen+truncate strategy and the results are promising (at least on x86), I'll submit a patch once I clean up the code.

Nice!

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

assert((isa<LoadInst>(I) || isa<StoreInst>(I)) &&
          "Expected Load or Store instruction");
   if (auto *LI = dyn_cast<LoadInst>(I))
     return LI->getType();
   return cast<StoreInst>(I)->getValueOperand()->getType();
 }
 
 /// A helper function that returns true if the given type is irregular. The
 /// type is irregular if its allocated size doesn't equal the store size of an
 /// element of the corresponding vector type at the given vectorization factor.
-static bool hasIrregularType(Type *Ty, const DataLayout &DL, ElementCount VF) {
+static bool hasIrregularType(Type *Ty, const DataLayout &DL) {
   // Determine if an array of VF elements of type Ty is "bitcast compatible"
   // with a <VF x Ty> vector.
-  if (VF.isVector()) {
-    auto *VectorTy = VectorType::get(Ty, VF);
-    return TypeSize::get(VF.getKnownMinValue() *
-                             DL.getTypeAllocSize(Ty).getFixedValue(),
-                         VF.isScalable()) != DL.getTypeStoreSize(VectorTy);
-  }
-
-  // If the vectorization factor is one, we just check if an array of type Ty
-  // requires padding between elements.
+  // This is only true if there is no padding between the array elements.
   return DL.getTypeAllocSizeInBits(Ty) != DL.getTypeSizeInBits(Ty);
 }
 
 /// A helper function that returns the reciprocal of the block probability of
 /// predicated blocks. If we return X, we are assuming the predicated block
 /// will execute once for every X iterations of the loop header.
 ///
 /// TODO: We should use actual block probability here, if available. Currently,
 ///       we always assume predicated blocks have a 50% chance of executing.
 static unsigned getReciprocalPredBlockProb() { return 2; }
assert(getWideningDecision(I, VF) == CM_Unknown &&
          "Decision should not be set yet.");
   auto *Group = getInterleavedAccessGroup(I);
   assert(Group && "Must have a group.");
 
   // If the instruction's allocated size doesn't equal it's type size, it
   // requires padding and will be scalarized.
   auto &DL = I->getModule()->getDataLayout();
   auto *ScalarTy = getMemInstValueType(I);
-  if (hasIrregularType(ScalarTy, DL, VF))
+  if (hasIrregularType(ScalarTy, DL))
     return false;
 
   // Check if masking is required.
   // A Group may need masking for one of two reasons: it resides in a block that
   // needs predication, or it was decided to use masking to deal with gaps.
   bool PredicatedAccessRequiresMasking =
       Legal->blockNeedsPredication(I->getParent()) && Legal->isMaskRequired(I);
   bool AccessWithGapsRequiresMasking =
bool LoopVectorizationCostModel::memoryInstructionCanBeWidened(
   // scalarized.
   if (isScalarWithPredication(I))
     return false;
 
   // If the instruction's allocated size doesn't equal it's type size, it
   // requires padding and will be scalarized.
   auto &DL = I->getModule()->getDataLayout();
   auto *ScalarTy = LI ? LI->getType() : SI->getValueOperand()->getType();
-  if (hasIrregularType(ScalarTy, DL, VF))
+  if (hasIrregularType(ScalarTy, DL))
     return false;
 
   return true;
 }
 
 void LoopVectorizationCostModel::collectLoopUniforms(ElementCount VF) {
   // We should not collect Uniforms more than once per VF. Right now,
   // this function is called from collectUniformsAndScalars(), which

llvm/test/Transforms/LoopVectorize/irregular_type.ll

+; RUN: opt %s -loop-vectorize -force-vector-width=4 -S | FileCheck %s
+
+; CHECK: foo
+; CHECK: vector.body
+; CHECK-NOT: load <4 x i7>
+; CHECK-NOT: store <4 x i7>
+; CHECK: for.body
+define void @foo(i7* %a, i64 %n) {
+entry:
+  br label %for.body
+
+for.body:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i7, i7* %a, i64 %indvars.iv
+  %0 = load i7, i7* %arrayidx, align 1
+  %sub = add nuw nsw i7 %0, 0
+  store i7 %sub, i7* %arrayidx, align 1
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %cmp = icmp eq i64 %indvars.iv.next, %n
+  br i1 %cmp, label %for.exit, label %for.body
+
+for.exit:
+  ret void
+}