[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

2257 ↗

(On Diff #69280)

Why "scalar"?

2259 ↗

(On Diff #69280)

Why not

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

?

2272 ↗

(On Diff #69280)

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

4550 ↗

(On Diff #69280)

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

4550 ↗

(On Diff #69280)

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

4550 ↗

(On Diff #69280)

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

2257 ↗

(On Diff #69280)

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).

2259 ↗

(On Diff #69280)

That should work!

2272 ↗

(On Diff #69280)

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.

4550 ↗

(On Diff #69280)

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

2257 ↗

(On Diff #69280)

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.

2272 ↗

(On Diff #69280)

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. :-)

4550 ↗

(On Diff #69280)

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

2272 ↗

(On Diff #69280)

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

4550 ↗

(On Diff #69280)

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!

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

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);

llvm/trunk/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

llvm/trunk/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 }
 

llvm/trunk/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

llvm/trunk/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

llvm/trunk/test/Transforms/LoopVectorize/scalar_after_vectorization.ll

+; RUN: opt < %s -force-vector-width=4 -force-vector-interleave=2 -loop-vectorize -instcombine -S | FileCheck %s
+; RUN: opt < %s -force-vector-width=4 -force-vector-interleave=2 -loop-vectorize -S | FileCheck %s --check-prefix=NO-IC
+
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+
+; CHECK-LABEL: @scalar_after_vectorization_0
+;
+; CHECK: vector.body:
+; CHECK:   %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
+; CHECK:   %offset.idx = or i64 %index, 1
+; CHECK:   %[[T2:.+]] = add nuw nsw i64 %offset.idx, %tmp0
+; CHECK:   %[[T3:.+]] = sub nsw i64 %[[T2]], %x
+; CHECK:   %[[T4:.+]] = getelementptr inbounds i32, i32* %a, i64 %[[T3]]
+; CHECK:   %[[T5:.+]] = bitcast i32* %[[T4]] to <4 x i32>*
+; CHECK:   load <4 x i32>, <4 x i32>* %[[T5]], align 4
+; CHECK:   %[[T6:.+]] = getelementptr i32, i32* %[[T4]], i64 4
+; CHECK:   %[[T7:.+]] = bitcast i32* %[[T6]] to <4 x i32>*
+; CHECK:   load <4 x i32>, <4 x i32>* %[[T7]], align 4
+; CHECK:   br {{.*}}, label %middle.block, label %vector.body
+;
+; NO-IC-LABEL: @scalar_after_vectorization_0
+;
+; NO-IC: vector.body:
+; NO-IC:   %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
+; NO-IC:   %offset.idx = add i64 1, %index
+; NO-IC:   %[[T2:.+]] = add i64 %offset.idx, 0
+; NO-IC:   %[[T3:.+]] = add i64 %offset.idx, 4
+; NO-IC:   %[[T4:.+]] = add nuw nsw i64 %[[T2]], %tmp0
+; NO-IC:   %[[T5:.+]] = add nuw nsw i64 %[[T3]], %tmp0
+; NO-IC:   %[[T6:.+]] = sub nsw i64 %[[T4]], %x
+; NO-IC:   %[[T7:.+]] = sub nsw i64 %[[T5]], %x
+; NO-IC:   %[[T8:.+]] = getelementptr inbounds i32, i32* %a, i64 %[[T6]]
+; NO-IC:   %[[T9:.+]] = getelementptr inbounds i32, i32* %a, i64 %[[T7]]
+; NO-IC:   %[[T10:.+]] = getelementptr i32, i32* %[[T8]], i32 0
+; NO-IC:   %[[T11:.+]] = bitcast i32* %[[T10]] to <4 x i32>*
+; NO-IC:   load <4 x i32>, <4 x i32>* %[[T11]], align 4
+; NO-IC:   %[[T12:.+]] = getelementptr i32, i32* %[[T8]], i32 4
+; NO-IC:   %[[T13:.+]] = bitcast i32* %[[T12]] to <4 x i32>*
+; NO-IC:   load <4 x i32>, <4 x i32>* %[[T13]], align 4
+; NO-IC:   br {{.*}}, label %middle.block, label %vector.body
+;
+define void @scalar_after_vectorization_0(i32* noalias %a, i32* noalias %b, i64 %x, i64 %y) {
+
+outer.ph:
+  br label %outer.body
+
+outer.body:
+  %i = phi i64 [ 1, %outer.ph ], [ %i.next, %inner.end ]
+  %tmp0 = mul nuw nsw i64 %i, %x
+  br label %inner.ph
+
+inner.ph:
+  br label %inner.body
+
+inner.body:
+  %j = phi i64 [ 1, %inner.ph ], [ %j.next, %inner.body ]
+  %tmp1 = add nuw nsw i64 %j, %tmp0
+  %tmp2 = sub nsw i64 %tmp1, %x
+  %tmp3 = getelementptr inbounds i32, i32* %a, i64 %tmp2
+  %tmp4 = load i32, i32* %tmp3, align 4
+  %tmp5 = getelementptr inbounds i32, i32* %b, i64 %tmp1
+  store i32 %tmp4, i32* %tmp5, align 4
+  %j.next = add i64 %j, 1
+  %cond.j = icmp slt i64 %j.next, %y
+  br i1 %cond.j, label %inner.body, label %inner.end
+
+inner.end:
+  %i.next = add i64 %i, 1
+  %cond.i = icmp slt i64 %i.next, %y
+  br i1 %cond.i, label %outer.body, label %outer.end
+
+outer.end:
+  ret void
+}