[LV] Use vector vphis for more induction variables

[mkuper]

Summary

Use a real vector IV for integer IVs that are the same type as the primary, and have a constant step - but are not necessarily the primary IV itself.

This is an expansion of http://reviews.llvm.org/rL271410

[delena]

lib/Transforms/Vectorize/LoopVectorize.cpp

4102

If you need only SEXT or TRUNC for a secondary induction variable, you can send the type to widenInductionVariable() in the last parameter.

[mkuper]

lib/Transforms/Vectorize/LoopVectorize.cpp

4102

I'm intentionally getting this in in very small steps, so as not to regress the world in case the vector IVs aren't handled well by downstream passes.

In any case, passing the type to widenInductionVariable isn't the right thing here, since we don't need to truncate the start value. It should be enough to just remove the condition and let it fall into the widenInductionVariable case. That's going to be the next follow-up.

[delena]

lib/Transforms/Vectorize/LoopVectorize.cpp

2122

I thought, that you can put here Builder.CreateSExtOrTrunc(Start, TruncType) , Start and Step should have the same type anyway.
You can change name from TruncType to CastType.

But if I'm wrong, you can submit this patch as is.

[mkuper]

Thanks, Elena!
I'll commit this as is, and remove the restriction on types in a separate commit.

lib/Transforms/Vectorize/LoopVectorize.cpp

2122

There are two places that call widenInductionVariable.
The callsite that calls it with a TruncType will always need a trunc, not a sext, since having a sext there make the transformation unsafe.
The callsite that calls it without a TruncType should, if I'm not mistaken, keep calling it without a TruncType - the type already matches what we want.

So, I'd rather keep it as Instruction::Trunc. SExtOrTrunc will work, but this makes what we want explicit.

lib/Transforms/Vectorize/LoopVectorize.cpp

protected:
 
   /// This function adds (StartIdx, StartIdx + Step, StartIdx + 2*Step, ...)
   /// to each vector element of Val. The sequence starts at StartIndex.
   /// Step is a SCEV. In order to get StepValue it takes the existing value
   /// from SCEV or creates a new using SCEVExpander.
   virtual Value *getStepVector(Value *Val, int StartIdx, const SCEV *Step);
 
   /// Create a vector induction variable based on an existing scalar one.
-  /// Currently only works for integer primary induction variables with
-  /// a constant step.
+  /// Currently only works for integer induction variables with a constant
+  /// step.
   /// If TruncType is provided, instead of widening the original IV, we
   /// widen a version of the IV truncated to TruncType.
   void widenInductionVariable(const InductionDescriptor &II, VectorParts &Entry,
                               IntegerType *TruncType = nullptr);
 
   /// When we go over instructions in the basic block we rely on previous
   /// values within the current basic block or on loop invariant values.
   /// When we widen (vectorize) values we place them in the map. If the values
void InnerLoopVectorizer::widenInductionVariable(const InductionDescriptor &II,
   ConstantInt *Step = II.getConstIntStepValue();
   assert(Step && "Can not widen an IV with a non-constant step");
 
   // Construct the initial value of the vector IV in the vector loop preheader
   auto CurrIP = Builder.saveIP();
   Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator());
   if (TruncType) {
     Step = ConstantInt::getSigned(TruncType, Step->getSExtValue());
     Start = Builder.CreateCast(Instruction::Trunc, Start, TruncType);
   }
   Value *SplatStart = Builder.CreateVectorSplat(VF, Start);
   Value *SteppedStart = getStepVector(SplatStart, 0, Step);
   Builder.restoreIP(CurrIP);
 
   Value *SplatVF =
-      ConstantVector::getSplat(VF, ConstantInt::get(Start->getType(), VF));
+      ConstantVector::getSplat(VF, ConstantInt::getSigned(Start->getType(),
+                               VF * Step->getSExtValue()));
   // We may need to add the step a number of times, depending on the unroll
   // factor. The last of those goes into the PHI.
   PHINode *VecInd = PHINode::Create(SteppedStart->getType(), 2, "vec.ind",
                                     &*LoopVectorBody->getFirstInsertionPt());
   Value *LastInduction = VecInd;
   for (unsigned Part = 0; Part < UF; ++Part) {
     Entry[Part] = LastInduction;
     LastInduction = Builder.CreateAdd(LastInduction, SplatVF, "step.add");
void InnerLoopVectorizer::widenPHIInstruction(
 
   // FIXME: The newly created binary instructions should contain nsw/nuw flags,
   // which can be found from the original scalar operations.
   switch (II.getKind()) {
   case InductionDescriptor::IK_NoInduction:
     llvm_unreachable("Unknown induction");
   case InductionDescriptor::IK_IntInduction: {
     assert(P->getType() == II.getStartValue()->getType() && "Types must match");
-    if (P != OldInduction || VF == 1) {
+    if (VF == 1 || P->getType() != Induction->getType() ||
+        !II.getConstIntStepValue()) {
       Value *V = Induction;
       // Handle other induction variables that are now based on the
       // canonical one.
       if (P != OldInduction) {
         V = Builder.CreateSExtOrTrunc(Induction, P->getType());
         V = II.transform(Builder, V, PSE.getSE(), DL);
         V->setName("offset.idx");
       }

test/Transforms/LoopVectorize/induction.ll

 
 ; The SCEV expression of %sphi is (zext i8 {%t,+,1}<%loop> to i32)
 ; In order to recognize %sphi as an induction PHI and vectorize this loop,
 ; we need to convert the SCEV expression into an AddRecExpr.
 ; The expression gets converted to {zext i8 %t to i32,+,1}.
 
 ; CHECK-LABEL: wrappingindvars1
 ; CHECK-LABEL: vector.scevcheck
+; CHECK-LABEL: vector.ph
+; CHECK: %[[START:.*]] = add <2 x i32> %{{.*}}, <i32 0, i32 1>
 ; CHECK-LABEL: vector.body
-; CHECK: add <2 x i32> {{%[^ ]*}}, <i32 0, i32 1>
+; CHECK: %[[PHI:.*]] = phi <2 x i32> [ %[[START]], %vector.ph ], [ %[[STEP:.*]], %vector.body ]
+; CHECK: %[[STEP]] = add <2 x i32> %[[PHI]], <i32 2, i32 2>
 define void @wrappingindvars1(i8 %t, i32 %len, i32 *%A) {
  entry:
   %st = zext i8 %t to i16
   %ext = zext i8 %t to i32
   %ecmp = icmp ult i16 %st, 42
   br i1 %ecmp, label %loop, label %exit
 
  loop:

 }
 
 ; The SCEV expression of %sphi is (4 * (zext i8 {%t,+,1}<%loop> to i32))
 ; In order to recognize %sphi as an induction PHI and vectorize this loop,
 ; we need to convert the SCEV expression into an AddRecExpr.
 ; The expression gets converted to ({4 * (zext %t to i32),+,4}).
 ; CHECK-LABEL: wrappingindvars2
 ; CHECK-LABEL: vector.scevcheck
+; CHECK-LABEL: vector.ph
+; CHECK: %[[START:.*]] = add <2 x i32> %{{.*}}, <i32 0, i32 4>
 ; CHECK-LABEL: vector.body
-; CHECK: add <2 x i32> {{%[^ ]*}}, <i32 0, i32 4>
+; CHECK: %[[PHI:.*]] = phi <2 x i32> [ %[[START]], %vector.ph ], [ %[[STEP:.*]], %vector.body ]
+; CHECK: %[[STEP]] = add <2 x i32> %[[PHI]], <i32 8, i32 8>
 define void @wrappingindvars2(i8 %t, i32 %len, i32 *%A) {
 
 entry:
   %st = zext i8 %t to i16
   %ext = zext i8 %t to i32
   %ext.mul = mul i32 %ext, 4
 
   %ecmp = icmp ult i16 %st, 42
for.body:
   store i32 %trunc.iv, i32* %arrayidx, align 4
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
   %exitcond = icmp eq i64 %indvars.iv.next, %k
   br i1 %exitcond, label %exit, label %for.body
 
 exit:
   ret void
 }
+
+; IND-LABEL: nonprimary
+; IND-LABEL: vector.ph
+; IND: %[[INSERT:.*]] = insertelement <2 x i32> undef, i32 %i, i32 0
+; IND: %[[SPLAT:.*]] = shufflevector <2 x i32> %[[INSERT]], <2 x i32> undef, <2 x i32> zeroinitializer
+; IND: %[[START:.*]] = add <2 x i32> %[[SPLAT]], <i32 0, i32 42>
+; IND-LABEL: vector.body:
+; IND: %index = phi i32 [ 0, %vector.ph ], [ %index.next, %vector.body ]
+; IND: %vec.ind = phi <2 x i32> [ %[[START]], %vector.ph ], [ %step.add, %vector.body ]
+; IND: %step.add = add <2 x i32> %vec.ind, <i32 84, i32 84>
+; IND: %index.next = add i32 %index, 2
+; IND: %[[CMP:.*]] = icmp eq i32 %index.next
+; IND: br i1 %[[CMP]]
+; UNROLL-LABEL: nonprimary
+; UNROLL-LABEL: vector.ph
+; UNROLL: %[[INSERT:.*]] = insertelement <2 x i32> undef, i32 %i, i32 0
+; UNROLL: %[[SPLAT:.*]] = shufflevector <2 x i32> %[[INSERT]], <2 x i32> undef, <2 x i32> zeroinitializer
+; UNROLL: %[[START:.*]] = add <2 x i32> %[[SPLAT]], <i32 0, i32 42>
+; UNROLL-LABEL: vector.body:
+; UNROLL: %index = phi i32 [ 0, %vector.ph ], [ %index.next, %vector.body ]
+; UNROLL: %vec.ind = phi <2 x i32> [ %[[START]], %vector.ph ], [ %step.add1, %vector.body ]
+; UNROLL: %step.add = add <2 x i32> %vec.ind, <i32 84, i32 84>
+; UNROLL: %step.add1 = add <2 x i32> %vec.ind, <i32 168, i32 168>
+; UNROLL: %index.next = add i32 %index, 4
+; UNROLL: %[[CMP:.*]] = icmp eq i32 %index.next
+; UNROLL: br i1 %[[CMP]]
+define void @nonprimary(i32* nocapture %a, i32 %start, i32 %i, i32 %k) {
+for.body.preheader:
+  br label %for.body
+
+for.body:
+  %indvars.iv = phi i32 [ %indvars.iv.next, %for.body ], [ %i, %for.body.preheader ]
+  %arrayidx = getelementptr inbounds i32, i32* %a, i32 %indvars.iv
+  store i32 %indvars.iv, i32* %arrayidx, align 4
+  %indvars.iv.next = add nuw nsw i32 %indvars.iv, 42
+  %exitcond = icmp eq i32 %indvars.iv.next, %k
+  br i1 %exitcond, label %exit, label %for.body
+
+exit:
+  ret void
+}

test/Transforms/LoopVectorize/reverse_induction.ll

 ; RUN: opt < %s -loop-vectorize -force-vector-interleave=2 -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"
 
 ; Make sure consecutive vector generates correct negative indices.
 ; PR15882
 
 ; CHECK-LABEL: @reverse_induction_i64(
-; CHECK: add <4 x i64> %[[SPLAT:.*]], <i64 0, i64 -1, i64 -2, i64 -3>
-; CHECK: add <4 x i64> %[[SPLAT]], <i64 -4, i64 -5, i64 -6, i64 -7>
+; CHECK: %step.add = add <4 x i64> %vec.ind, <i64 -4, i64 -4, i64 -4, i64 -4>
+; CHECK: %step.add2 = add <4 x i64> %step.add, <i64 -4, i64 -4, i64 -4, i64 -4>
 
 define i32 @reverse_induction_i64(i64 %startval, i32 * %ptr) {
 entry:
   br label %for.body
 
 for.body:
   %add.i7 = phi i64 [ %startval, %entry ], [ %add.i, %for.body ]
   %i.06 = phi i32 [ 0, %entry ], [ %inc4, %for.body ]
   %redux5 = phi i32 [ 0, %entry ], [ %inc.redux, %for.body ]
   %add.i = add i64 %add.i7, -1
   %kind_.i = getelementptr inbounds i32, i32* %ptr, i64 %add.i
   %tmp.i1 = load i32, i32* %kind_.i, align 4
   %inc.redux = add i32 %tmp.i1, %redux5
   %inc4 = add i32 %i.06, 1
   %exitcond = icmp ne i32 %inc4, 1024
   br i1 %exitcond, label %for.body, label %loopend
 
 loopend:
   ret i32 %inc.redux
 }
 
 ; CHECK-LABEL: @reverse_induction_i128(
-; CHECK: add <4 x i128> %[[SPLAT:.*]], <i128 0, i128 -1, i128 -2, i128 -3>
-; CHECK: add <4 x i128> %[[SPLAT]], <i128 -4, i128 -5, i128 -6, i128 -7>
+; CHECK: %step.add = add <4 x i128> %vec.ind, <i128 -4, i128 -4, i128 -4, i128 -4>
+; CHECK: %step.add2 = add <4 x i128> %step.add, <i128 -4, i128 -4, i128 -4, i128 -4>
 define i32 @reverse_induction_i128(i128 %startval, i32 * %ptr) {
 entry:
   br label %for.body
 
 for.body:
   %add.i7 = phi i128 [ %startval, %entry ], [ %add.i, %for.body ]
   %i.06 = phi i32 [ 0, %entry ], [ %inc4, %for.body ]
   %redux5 = phi i32 [ 0, %entry ], [ %inc.redux, %for.body ]

 ;     a[reverse_induction] = forward_induction;
 ;     --reverse_induction;
 ;   }
 ; }
 
 ; CHECK-LABEL: @reverse_forward_induction_i64_i8(
 ; CHECK: vector.body
 ; CHECK: %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
-; CHECK: %offset.idx = sub i64 1023, %index
+; CHECK: %vec.ind = phi <4 x i64> [ <i64 1023, i64 1022, i64 1021, i64 1020>, %vector.ph ]
+; CHECK: %step.add = add <4 x i64> %vec.ind, <i64 -4, i64 -4, i64 -4, i64 -4>
 ; CHECK: trunc i64 %index to i8
 
 define void @reverse_forward_induction_i64_i8() {
 entry:
   br label %while.body
 
 while.body:
   %indvars.iv = phi i64 [ 1023, %entry ], [ %indvars.iv.next, %while.body ]

 
 while.end:
   ret void
 }
 
 ; CHECK-LABEL: @reverse_forward_induction_i64_i8_signed(
 ; CHECK: vector.body:
 ; CHECK:  %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
-; CHECK:  %offset.idx = sub i64 1023, %index
+; CHECK: %vec.ind = phi <4 x i64> [ <i64 1023, i64 1022, i64 1021, i64 1020>, %vector.ph ]
+; CHECK: %step.add = add <4 x i64> %vec.ind, <i64 -4, i64 -4, i64 -4, i64 -4>
 
 define void @reverse_forward_induction_i64_i8_signed() {
 entry:
   br label %while.body
 
 while.body:
   %indvars.iv = phi i64 [ 1023, %entry ], [ %indvars.iv.next, %while.body ]
   %forward_induction.05 = phi i8 [ -127, %entry ], [ %inc, %while.body ]