[LV] Scalarize instructions marked scalar after vectorization

[mssimpso]

Summary

This patch ensures that we actually scalarize instructions marked scalar after vectorization. Previously, such instructions may have been vectorized.

[mkuper]

Would it make sense to commit the different changes here separately?

That is:
Patch 1: collectLoopUniforms()
Patch 2: The parts that only emit instructions for the low lane of uniforms.
Patch 3: vectorizeBlockInLoop()

If I'm not mistaken both (1) and (2) should be good independently. (1) because it will make other things that care about uniformity slightly more correct, and (2) because it may help some instructions we already scalarize today (although I'm not sure we actually have such cases now. So maybe 2+3 should go in together).

lib/Transforms/Vectorize/LoopVectorize.cpp

2263

Why "scalar"?

2265

Why not

return (!OrigLoop->contains(I) || !Legal->isScalarAfterVectorization(I)
        || Legal->isUniformAfterVectorization(I))

?

2278

Why do we need this?
Wouldn't we already mark EntryVal as uniform in collectLoopUniforms(), if all its users are uniform / consecutive pointers?

4576

This scares me a bit. :-)
As I said on the PR, I definitely think we should do it, but it still scares me. Perhaps add a bit more testing?

Regardless, there's (at least?) one more special case I see below - DbgInfoIntrinsic.

[hfinkel]

lib/Transforms/Vectorize/LoopVectorize.cpp

4576

As I said on the PR, I definitely think we should do it, but it still scares me. Perhaps add a bit more testing?

Which PR?

[mkuper]

lib/Transforms/Vectorize/LoopVectorize.cpp

4576

My bad, not a PR, meant "on the other review". :-)
https://reviews.llvm.org/D23509

[mssimpso]

In D23889#525581, @mkuper wrote:

Would it make sense to commit the different changes here separately?

That is:
Patch 1: collectLoopUniforms()
Patch 2: The parts that only emit instructions for the low lane of uniforms.
Patch 3: vectorizeBlockInLoop()

If I'm not mistaken both (1) and (2) should be good independently. (1) because it will make other things that care about uniformity slightly more correct, and (2) because it may help some instructions we already scalarize today (although I'm not sure we actually have such cases now. So maybe 2+3 should go in together).

Right, that's what I was thinking. I wanted to included everything here in the review (at least initially) for context. We can split it up exactly as you suggested. Regarding an independent patch 2, it should be NFC post-instcombine. Pre-instcombine, we would at least no longer generate unnecessary steps for uniform IVs.

lib/Transforms/Vectorize/LoopVectorize.cpp

2263

This probably makes more sense with the response below. We're checking to see if all the scalar users of the IV we are scalarizing are also uniform. We can scalarize an IV if it has both vector and scalar users (ending up with two versions).

2265

That should work!

2278

This is for the cases in which we both want a vector and a scalar version of an IV. We scalarize an IV that's not marked scalar after vectorization when it has at least one scalar user. For such an IV, if all it's scalar users are also uniform, we will only ever need the first lane of the scalar IV.

4576

Right! Thanks for pointing out the debug intrinsics. Perhaps it would make better sense to handle all of the cases individually, instead all together at the top?

[mkuper]

lib/Transforms/Vectorize/LoopVectorize.cpp

2263

Oh, ok, I understand now - this checks "isScalar() implies isUniform()" by computing "!isScalar() || isUniform()".
I read "scalar users" as "pre-vectorization users" not "users that are going to stay scalar", and got confused.

2278

Ah, got it, thanks!

Sentences like "all its scalar users are uniform" still confuse me, because of the terminology we've adopted.
My personal preference is still "uniform" for what we call "uniform scalar" and "multi-scalar" for what we call "non-uniform scalar" - then we could say that we're looking for an IV that has no multi-scalar users. But maybe I just need to get used to the current state. :-)

4576

Hmpf. I think I still prefer handling this at the top - duplicating this check into each case seems silly.

[mssimpso]

Thanks for the quick feedback, Michael! I'll start addressing your comments by first pulling out the changes to collectLoopUniforms in a separate review, and adding some specific tests for it.

lib/Transforms/Vectorize/LoopVectorize.cpp

2278

I agree the terminology is a bit confusing. At the very least, I'll add a more detailed comment here.

4576

Agreed.

[mssimpso]

I pulled out the changes to collectLoopUniforms (Patch 1) in D24271 and rebased. I also addressed Michael's comments on this existing patch. Next, I'll pull out the changes to uniform instruction emission (Patch 2) in a separate review.

[mssimpso]

I pulled out the changes to uniform instruction emission (Patch 2) in D24275 and rebased.

[mssimpso]

Added a simplified version of Sam's original test case.

[mkuper]

LGTM

[mssimpso]

Thanks, Michael!

lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::buildScalarSteps(Value *ScalarIV, Value *Step,
   // We shouldn't have to build scalar steps if we aren't vectorizing.
   assert(VF > 1 && "VF should be greater than one");
 
   // Get the value type and ensure it and the step have the same integer type.
   Type *ScalarIVTy = ScalarIV->getType()->getScalarType();
   assert(ScalarIVTy->isIntegerTy() && ScalarIVTy == Step->getType() &&
          "Val and Step should have the same integer type");
 
   auto scalarUserIsUniform = [&](User *U) -> bool {
     auto *I = cast<Instruction>(U);
     return !OrigLoop->contains(I) || !Legal->isScalarAfterVectorization(I) ||
            Legal->isUniformAfterVectorization(I);
   };
 
   // Determine the number of scalars we need to generate for each unroll
   // iteration. If EntryVal is uniform or all it's scalar users are uniform, we
   // only need to generate the first lane. Otherwise, we generate all VF
   // values. We are essentially determining if the induction variable has no
   // "multi-scalar" (non-uniform scalar) users.
   unsigned Lanes = VF;
   if (Legal->isUniformAfterVectorization(cast<Instruction>(EntryVal)) ||
       all_of(EntryVal->users(), scalarUserIsUniform))
     Lanes = 1;
 
   // Compute the scalar steps and save the results in VectorLoopValueMap.
   ScalarParts Entry(UF);
   for (unsigned Part = 0; Part < UF; ++Part) {
     Entry[Part].resize(VF);
     for (unsigned Lane = 0; Lane < Lanes; ++Lane) {
       auto *StartIdx = ConstantInt::get(ScalarIVTy, VF * Part + Lane);
       auto *Mul = Builder.CreateMul(StartIdx, Step);
       auto *Add = Builder.CreateAdd(ScalarIV, Mul);
static bool mayDivideByZero(Instruction &I) {
   Value *Divisor = I.getOperand(1);
   auto *CInt = dyn_cast<ConstantInt>(Divisor);
   return !CInt || CInt->isZero();
 }
 
 void InnerLoopVectorizer::vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV) {
   // For each instruction in the old loop.
   for (Instruction &I : *BB) {
+
+    // Scalarize instructions that should remain scalar after vectorization.
+    if (!(isa<BranchInst>(&I) || isa<PHINode>(&I) ||
+          isa<DbgInfoIntrinsic>(&I)) &&
+        Legal->isScalarAfterVectorization(&I)) {
+      scalarizeInstruction(&I);
+      continue;
+    }
+
     switch (I.getOpcode()) {
     case Instruction::Br:
       // Nothing to do for PHIs and BR, since we already took care of the
       // loop control flow instructions.
       continue;
     case Instruction::PHI: {
       // Vectorize PHINodes.
       widenPHIInstruction(&I, UF, VF, PV);

test/Transforms/LoopVectorize/PowerPC/small-loop-rdx.ll

 ; RUN: opt < %s -loop-vectorize -S | FileCheck %s
 
+; CHECK: vector.body:
 ; CHECK: fadd
 ; CHECK-NEXT: fadd
 ; CHECK-NEXT: fadd
 ; CHECK-NEXT: fadd
 ; CHECK-NEXT: fadd
 ; CHECK-NEXT: fadd
 ; CHECK-NEXT: fadd
 ; CHECK-NEXT: fadd
 ; CHECK-NEXT: fadd
 ; CHECK-NEXT: fadd
 ; CHECK-NEXT: fadd
 ; CHECK-NEXT: fadd
-; CHECK-NEXT: =
 ; CHECK-NOT: fadd
-; CHECK-SAME: >
+; CHECK: middle.block
 
 target datalayout = "e-m:e-i64:64-n32:64"
 target triple = "powerpc64le-ibm-linux-gnu"
 
 define void @test(double* nocapture readonly %arr, i32 signext %len) #0 {
 entry:
   %cmp4 = icmp sgt i32 %len, 0
   br i1 %cmp4, label %for.body.lr.ph, label %for.end

test/Transforms/LoopVectorize/PowerPC/vsx-tsvc-s173.ll

for.end:                                          ; preds = %for.body3
   %cmp = icmp slt i32 %inc11, %mul
   br i1 %cmp, label %for.cond1.preheader, label %for.end12
 
 for.end12:                                        ; preds = %for.end, %entry
   ret i32 0
 
 ; CHECK-LABEL: @s173
 ; CHECK: load <4 x float>, <4 x float>*
-; CHECK: add i64 %index, 16000
+; CHECK: add nsw i64 %index, 16000
 ; CHECK: ret i32 0
 }
 
 attributes #0 = { nounwind }
 

test/Transforms/LoopVectorize/global_alias.ll

 ; /// Different objects, negative induction, shortening slide
 ; int noAlias08 (int a) {
 ;   int i;
 ;   for (i=0; i<SIZE-10; i++)
 ;     Foo.A[SIZE-i-1] = Foo.B[SIZE-i-10] + a;
 ;   return Foo.A[a];
 ; }
 ; CHECK-LABEL: define i32 @noAlias08(
-; CHECK: sub <4 x i32>
+; CHECK: load <4 x i32>
 ; CHECK: ret
 
 define i32 @noAlias08(i32 %a) #0 {
 entry:
   %a.addr = alloca i32, align 4
   %i = alloca i32, align 4
   store i32 %a, i32* %a.addr, align 4
   store i32 0, i32* %i, align 4

 ; /// Different objects, negative induction, widening slide
 ; int noAlias09 (int a) {
 ;   int i;
 ;   for (i=0; i<SIZE; i++)
 ;     Foo.A[SIZE-i-10] = Foo.B[SIZE-i-1] + a;
 ;   return Foo.A[a];
 ; }
 ; CHECK-LABEL: define i32 @noAlias09(
-; CHECK: sub <4 x i32>
+; CHECK: load <4 x i32>
 ; CHECK: ret
 
 define i32 @noAlias09(i32 %a) #0 {
 entry:
   %a.addr = alloca i32, align 4
   %i = alloca i32, align 4
   store i32 %a, i32* %a.addr, align 4
   store i32 0, i32* %i, align 4

 ; /// Same objects, negative induction, constant distance, just enough for vector size
 ; int noAlias14 (int a) {
 ;   int i;
 ;   for (i=0; i<SIZE; i++)
 ;     Foo.A[SIZE-i-1] = Foo.A[SIZE-i-5] + a;
 ;   return Foo.A[a];
 ; }
 ; CHECK-LABEL: define i32 @noAlias14(
-; CHECK: sub <4 x i32>
+; CHECK: load <4 x i32>
 ; CHECK: ret
 
 define i32 @noAlias14(i32 %a) #0 {
 entry:
   %a.addr = alloca i32, align 4
   %i = alloca i32, align 4
   store i32 %a, i32* %a.addr, align 4
   store i32 0, i32* %i, align 4

test/Transforms/LoopVectorize/induction_plus.ll

 ; RUN: opt < %s -loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -S | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-apple-macosx10.8.0"
 
 @array = common global [1024 x i32] zeroinitializer, align 16
 
 ;CHECK-LABEL: @array_at_plus_one(
 ;CHECK: %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
 ;CHECK: %vec.ind = phi <4 x i64> [ <i64 0, i64 1, i64 2, i64 3>, %vector.ph ], [ %vec.ind.next, %vector.body ]
 ;CHECK: %vec.ind1 = phi <4 x i32> [ <i32 0, i32 1, i32 2, i32 3>, %vector.ph ], [ %vec.ind.next2, %vector.body ]
-;CHECK: add nsw <4 x i64> %vec.ind, <i64 12, i64 12, i64 12, i64 12>
+;CHECK: %[[T1:.+]] = add i64 %index, 0
+;CHECK: %[[T2:.+]] = add nsw i64 %[[T1]], 12
+;CHECK: getelementptr inbounds [1024 x i32], [1024 x i32]* @array, i64 0, i64 %[[T2]]
 ;CHECK: %vec.ind.next = add <4 x i64> %vec.ind, <i64 4, i64 4, i64 4, i64 4>
 ;CHECK: %vec.ind.next2 = add <4 x i32> %vec.ind1, <i32 4, i32 4, i32 4, i32 4>
 ;CHECK: ret i32
 define i32 @array_at_plus_one(i32 %n) nounwind uwtable ssp {
   %1 = icmp sgt i32 %n, 0
   br i1 %1, label %.lr.ph, label %._crit_edge
 
 .lr.ph:                                           ; preds = %0, %.lr.ph