Loop vectorization with uniform load

[delena]

Summary

Considered a loop with uniform load:

float inc = 0.5;
void foo(float *A, unsigned N) {

for (int i=0;i<N;i++){
  A[i] += inc; // Uniform load of inc
}

}
If the "uniform load" is not hoisted before vectorization, the cost of the uniform load is "scalar load + broadcast".
It is not correctly calculated in the current version and a huge cost for one splat vector prevents loop vectorization.

[Ayal]

This seems like the right cost to attribute to a uniform load.

In general, as in this testcase, uniform loads that are loop-invariant better be hoisted before the vectorizer, yielding potentially even lower costs. But that's an orthogonal issue.

It would be good to align the instructions emitted when vectorizing such a load (i.e., scalarizeInstruction's insertElements) with this cost attributed to it.

../test/Transforms/LoopVectorize/X86/uniform_load.ll

1

Suffice to invoke -loop-vectorize rather than -O2?

[delena]

Updated test file, according to Ayal's comments.

[hfinkel]

../lib/Transforms/Vectorize/LoopVectorize.cpp

5827

This can just be + instead of +=, otherwise, this LGTM.

[delena]

../lib/Transforms/Vectorize/LoopVectorize.cpp

5827

Yes, of course. Thank you.

[anemet]

If the "uniform load" is not hoisted before vectorization, the cost of the uniform load is "scalar load + broadcast".

This is not necessarily a criticism of your change but in most cases this cost is still too conservative.

If we need memchecks to disambiguate the the uniform access against the other memory accesses, the uniform load becomes loop-invariant after vectorization and a subsequent LICM will hoist it out of the loop (D17191). Thus the cost is really zero.

I also think that this is the common case, like your testcase. Just schedule a licm afterward and the load+shuffles will be hoisted out of the loop.

It is not correctly calculated in the current version and a huge cost for one splat vector prevents loop vectorization.

Can you please elaborate, how was the cost computed before?

Thanks,
Adam

[delena]

Can you please elaborate, how was the cost computed before?

25 for VF=2, 51 for VF=4 and 103 for VF=8

Thus the cost is really zero.

I know that the actual cost is 0, but I can't put 0 when the load is inside the loop.

the uniform load becomes loop-invariant after vectorization and a subsequent LICM will hoist it out of the loop

Do you know why the load wasn't hoisted before vectorization?

[anemet]

In D18940#397500, @delena wrote:

Can you please elaborate, how was the cost computed before?

25 for VF=2, 51 for VF=4 and 103 for VF=8

I don't mean the actual number.

Did we assume that we needed VF number of loads for each element rather than a single one with a shuffle/broadcast?

I am just trying to understand the before-picture. You only said that we were building a splat but that is true even after.

Thus the cost is really zero.

I know that the actual cost is 0, but I can't put 0 when the load is inside the loop.

Why not, if we know that it will be hoisted out? I don't see a way how this load wouldn't be loop-invariant if it's legal to vectorize the loop. For example, in:

for (i = 0; i < 10; i++) {

 .. = a[5]
a[i] = ...

}

a[5] is loop-variant but dependence analysis would not allow this loop to be vectorized because the dependence distance between a[5] and a[i] is not constant.

the uniform load becomes loop-invariant after vectorization and a subsequent LICM will hoist it out of the loop

Do you know why the load wasn't hoisted before vectorization?

Because it requires multi-versioning of the loop with memchecks because we couldn't disambiguate the invariant load against the stores in the loop at compile time.

LICM does not currently perform multiversioning by default.

[delena]

I don't mean the actual number.
Did we assume that we needed VF number of loads for each element rather than a single one with a shuffle/broadcast?

Yes
The address computation cost is taken as VF * getAddressComputationCost(Ty, IsComplex)
IsComplex is true.

Why not, if we know that it will be hoisted out?

I can change the cost to 0 and add comments.

[Ayal]

Indeed, "isUniform" actually means "versionably invariant". Note that invariance implies uniformity but the converse may not always hold in general, in which case a positive shuffle cost inside the loop would be right. However in our current innermost-loop (predicated-)scev-based analysis case, they are synonymous, hence such loads should always be hoistable.

Unfortunate that such a naïve testcase evades alias analysis. Add "float * __restrict A" to see licm hoist inc.

../lib/Transforms/Vectorize/LoopVectorize.cpp

case Instruction::Load: {
     Value *Ptr = SI ? SI->getPointerOperand() : LI->getPointerOperand();
     // We add the cost of address computation here instead of with the gep
     // instruction because only here we know whether the operation is
     // scalarized.
     if (VF == 1)
       return TTI.getAddressComputationCost(VectorTy) +
         TTI.getMemoryOpCost(I->getOpcode(), VectorTy, Alignment, AS);
 
+    if (LI && Legal->isUniform(Ptr)) {
+      // Scalar load + broadcast
+      unsigned Cost = TTI.getAddressComputationCost(ValTy->getScalarType());
+      Cost += TTI.getMemoryOpCost(I->getOpcode(), ValTy->getScalarType(),
+                                  Alignment, AS);
+      return Cost += TTI.getShuffleCost(TargetTransformInfo::SK_Broadcast,
+                                        ValTy);
+    }
+
     // For an interleaved access, calculate the total cost of the whole
     // interleave group.
     if (Legal->isAccessInterleaved(I)) {
       auto Group = Legal->getInterleavedAccessGroup(I);
       assert(Group && "Fail to get an interleaved access group.");
 
       // Only calculate the cost once at the insert position.
       if (Group->getInsertPos() != I)

../test/Transforms/LoopVectorize/X86/uniform_load.ll

+; RUN: opt -O2 -S -mcpu=core-avx2 < %s | FileCheck %s
+
+;float inc = 0.5;
+;void foo(float *A, unsigned N) {
+;
+;  for (unsigned i=0; i<N; i++){
+;    A[i] += inc;
+;  }
+;}
+
+; CHECK-LABEL: foo
+; CHECK: vector.body
+; CHECK: load <8 x float>
+; CHECK: fadd <8 x float>
+; CHECK: store <8 x float>
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+@inc = global float 5.000000e-01, align 4
+
+; Function Attrs: nounwind uwtable
+define void @foo(float* %A, i32 %N) {
+entry:
+  %A.addr = alloca float*, align 8
+  %N.addr = alloca i32, align 4
+  %i = alloca i32, align 4
+  store float* %A, float** %A.addr, align 8
+  store i32 %N, i32* %N.addr, align 4
+  store i32 0, i32* %i, align 4
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %0 = load i32, i32* %i, align 4
+  %1 = load i32, i32* %N.addr, align 4
+  %cmp = icmp ult i32 %0, %1
+  br i1 %cmp, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %2 = load float, float* @inc, align 4
+  %3 = load i32, i32* %i, align 4
+  %idxprom = sext i32 %3 to i64
+  %4 = load float*, float** %A.addr, align 8
+  %arrayidx = getelementptr inbounds float, float* %4, i64 %idxprom
+  %5 = load float, float* %arrayidx, align 4
+  %add = fadd float %5, %2
+  store float %add, float* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %6 = load i32, i32* %i, align 4
+  %inc = add nsw i32 %6, 1
+  store i32 %inc, i32* %i, align 4
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}