[LV] Teach about non header phis that have uses outside the loop

[anna]

Summary

This patch identifies non header phis that have no cyclic dependencies with
header phis (reduction/induction/first order recurrence phis).
If those phis have outside uses, we can still vectorize the loop and extract the
last element. This is because the iteration dependence distance for these phis
can be widened upto VF (similar to how we do for induction/reduction) since they do not
have a cyclic dependence with header phis.

The key point is to extract the last element from the vectorized phi and update
the scalar loop exit block phi to contain this extracted element from the vector
loop.

[Ayal]

lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

610

Only 2 incoming values: only header phi's are required to have two incoming values; non-header phi's get if-converted for any number of predecessors.

Only 1 use: in general, it shouldn't really matter how many uses there are, nor whether I is a PHINode; if I is defined inside the loop, and the loop gets vectorized, it should be possible to obtain the value of I associated with the last iteration, either inside or outside the loop. Regarding cyclic dependencies, these are taken care of by analyzing each header phi, and they in turn take care of their own live-outs, by pre-computing (Inductions) or post-processing (Reductions); so any cross-iteration dependence issues will be detected, and need to be addressed, there (cf. D22341).

Note that some Instructions may require special attention when obtaining last-lane value, e.g., isUniformAfterVectorization(). So starting with non-header PHI's sounds like a good first step.

lib/Transforms/Vectorize/LoopVectorize.cpp

3723–3733

Would it suffice to do here

Builder.SetInsertPoint(LoopMiddleBlock->getTerminator());
Value *LastIncomingValue = getOrCreateScalarValue(IncomingValue, {UF-1, VF-1});
LCSSAPhi.addIncoming(LastIncomingValue, LoopMiddleBlock);

instead of the below? Note that in general, if IncomingValue isUniformAfterVectorization(), we'll need to ask for lane 0 instead of VF-1.

test/Transforms/LoopVectorize/no_outside_user.ll

18–27

Good to also check that the live-out is extracted correctly.

55

This vectorizes just fine, right?

82

This cannot be vectorized, because reductions are allowed to have only the bump as a single inside user, plus outside users. The header %sum.02 phi flags this. See RecurrenceDescriptor::AddReductionVar

[anna]

lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

610

I'll update the code. For now, I'm going to start with non-header PHIs as the instruction defined inside the loop and having outside use.
The "single use" check was a very conservative way to avoid cyclic dependency -will check how to address this separately during the header phi analysis for reductions/inductions/first order recurrences.

lib/Transforms/Vectorize/LoopVectorize.cpp

3723–3733

From the code in getOrCreateScalarValue, it looks like it handles scalarization versus "unroll without vectorization" versus "unrolled and vectorized".
So, I think what you've written above is a succinct and complete version for what I need, without having to repeat the code down below. Thanks!

test/Transforms/LoopVectorize/no_outside_user.ll

18–27

yes.

55

vectorizes only with the patch.

Without the patch, Vectorization fails with:

LV: Found an outside user for :   %.lcssa = phi i32 [ %tmp17, %bb16 ]
remark: <unknown>:0:0: loop not vectorized: value could not be identified as an induction or reduction variable
LV: Can't vectorize the instructions or CFG
LV: Not vectorizing: Cannot prove legality.

[anna]

thanks for the comments Ayal. Have added inline comments. Will address those in upcoming patch.

[anna]

addressed review comments. added more tests.

[Ayal]

Overall looks good to me, though it could be cleaned up a bit more?

lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

438

Worth updating the above comment, to also include non-header Phi's.

Perhaps leave behind a TODO somewhere, that other (non-Phi) instructions should also be able to work with the new extract-scalar-of-last-iteration code.

602

Checking if Phi has outside users here becomes redundant, when AllowNonHdrExits becomes redundant (see below).

lib/Transforms/Vectorize/LoopVectorize.cpp

3724

Distinguishing between different AllowedExits here seem redundant: if IncomingValue isLoopInvariant(), as asserted below, getOrCreateScalarValue({UF-1,VF-1}) will simply return it. So the 'else' case below can also take care of the 'then' case. In general, whatever the allowed exit may be, grab the scalar value associated with the last iteration.

This will make AllowedNonHdrExits useless.

In the most general form, one may need to do

unsigned LastLane = Cost->isUniformAfterVectorization(IncomingValue, VF) ? 0 : VF - 1;
Value *lastIncomingValue =
          getOrCreateScalarValue(IncomingValue, {UF - 1, LastLane});

but this is not needed for this patch.

test/Transforms/LoopVectorize/no_outside_user.ll

12–16

Suffice to say "tmp17" is a non-header phi, which is an allowed exit.

92

(Check that) %predphi1 has %predphi as one of its operands, right? Thereby merging the more than 2 original incoming values together.

207

In cyclic_dep_with_indvar() below, %iv is conditionally reset inside the loop, disqualifying it from being an induction variable; so the loop isn't vectorizable, regardless of live-outs. Right?

[anna]

lib/Transforms/Vectorize/LoopVectorize.cpp

3724

good point. will reduce complexity here.

test/Transforms/LoopVectorize/no_outside_user.ll

207

yes, I had added the test case to show that cyclic dependencies that do not make the loop vectorizable still remain non-vectorizable. Same behaviour with not allowable cyclic dependencies for reductions.

I don't think there's a test where the loop was vectorizable in absence of live-outs and now is no longer vectorizable because of the live-outs. That's what this patch fixes :)

[anna]

addressed review comments and simplified code.

include/llvm/Transforms/Vectorize/LoopVectorizationLegality.h

public:
   bool isInductionVariable(const Value *V);
 
   /// Returns True if PN is a reduction variable in this loop.
   bool isReductionVariable(PHINode *PN) { return Reductions.count(PN); }
 
   /// Returns True if Phi is a first-order recurrence in this loop.
   bool isFirstOrderRecurrence(const PHINode *Phi);
 
+  /// Returns True if the value which is not defined in loop header (and hence
+  /// not an induction/reduction/first order recurrence) is allowed outside the loop.
+  bool isAllowedNonHeaderExit(const Value *V) {
+    return AllowedNonHdrExits.count(V);
+  }
+
   /// Return true if the block BB needs to be predicated in order for the loop
   /// to be vectorized.
   bool blockNeedsPredication(BasicBlock *BB);
 
   /// Check if this pointer is consecutive when vectorizing. This happens
   /// when the last index of the GEP is the induction variable, or that the
   /// pointer itself is an induction variable.
   /// This check allows us to vectorize A[idx] into a wide load/store.
private:
 
   /// Holds the widest induction type encountered.
   Type *WidestIndTy = nullptr;
 
   /// Allowed outside users. This holds the induction and reduction
   /// vars which can be accessed from outside the loop.
   SmallPtrSet<Value *, 4> AllowedExit;
 
+  /// Allowed non header phis which can be accessed from outside the loop.
+  SmallPtrSet<Value *, 4> AllowedNonHdrExits;
+
   /// Can we assume the absence of NaNs.
   bool HasFunNoNaNAttr = false;
 
   /// Vectorization requirements that will go through late-evaluation.
   LoopVectorizationRequirements *Requirements;
 
   /// Used to emit an analysis of any legality issues.
   LoopVectorizeHints *Hints;

lib/Transforms/Vectorize/LoopVectorizationLegality.cpp

static Type *getWiderType(const DataLayout &DL, Type *Ty0, Type *Ty1) {
   return Ty1;
 }
 
 /// Check that the instruction has outside loop users and is not an
 /// identified reduction variable.
 static bool hasOutsideLoopUser(const Loop *TheLoop, Instruction *Inst,
                                SmallPtrSetImpl<Value *> &AllowedExit) {
   // Reduction and Induction instructions are allowed to have exit users. All
   // other instructions must not have external users.
   if (!AllowedExit.count(Inst))
     // Check that all of the users of the loop are inside the BB.
     for (User *U : Inst->users()) {
       Instruction *UI = cast<Instruction>(U);
       // This user may be a reduction exit value.
       if (!TheLoop->contains(UI)) {
         LLVM_DEBUG(dbgs() << "LV: Found an outside user for : " << *UI << '\n');
         return true;
for (Instruction &I : *BB) {
         }
 
         // If this PHINode is not in the header block, then we know that we
         // can convert it to select during if-conversion. No need to check if
         // the PHIs in this block are induction or reduction variables.
         if (BB != Header) {
           // Check that this instruction has no outside users or is an
           // identified reduction value with an outside user.
           if (!hasOutsideLoopUser(TheLoop, Phi, AllowedExit))
             continue;
-          ORE->emit(createMissedAnalysis("NeitherInductionNorReduction", Phi)
-                    << "value could not be identified as "
-                       "an induction or reduction variable");
-          return false;
+          // Non-header phi nodes that have outside uses can be vectorized. Add
+          // them to the list of allowed exits and the AllowedNonHdrExits for
+          // post process fixing of LCSSAs.
+          // Unsafe cyclic dependencies with header phis are identified during
+          // legalization for reduction, induction and first order
+          // recurrences.
+          AllowedExit.insert(Phi);
+          AllowedNonHdrExits.insert(Phi);
+          continue;
         }
 
         // We only allow if-converted PHIs with exactly two incoming values.
         if (Phi->getNumIncomingValues() != 2) {
           ORE->emit(createMissedAnalysis("CFGNotUnderstood", Phi)
                     << "control flow not understood by vectorizer");
           LLVM_DEBUG(dbgs() << "LV: Found an invalid PHI.\n");
           return false;

lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::fixReduction(PHINode *Phi) {
   int SelfEdgeBlockIdx = (IncomingEdgeBlockIdx ? 0 : 1);
   Phi->setIncomingValue(SelfEdgeBlockIdx, BCBlockPhi);
   Phi->setIncomingValue(IncomingEdgeBlockIdx, LoopExitInst);
 }
 
 void InnerLoopVectorizer::fixLCSSAPHIs() {
   for (PHINode &LCSSAPhi : LoopExitBlock->phis()) {
     if (LCSSAPhi.getNumIncomingValues() == 1) {
+      auto *IncomingValue = LCSSAPhi.getIncomingValue(0);
+      if (!Legal->isAllowedNonHeaderExit(IncomingValue)) {
         assert(OrigLoop->isLoopInvariant(LCSSAPhi.getIncomingValue(0)) &&
                "Incoming value isn't loop invariant");
         LCSSAPhi.addIncoming(LCSSAPhi.getIncomingValue(0), LoopMiddleBlock);
+      } else {
+        Builder.SetInsertPoint(LoopMiddleBlock->getTerminator());
+        Value *lastIncomingValue =
+            getOrCreateScalarValue(IncomingValue, {UF - 1, VF - 1});
+        LCSSAPhi.addIncoming(lastIncomingValue, LoopMiddleBlock);
+      }
     }
   }
 }
 
 void InnerLoopVectorizer::sinkScalarOperands(Instruction *PredInst) {
   // The basic block and loop containing the predicated instruction.
   auto *PredBB = PredInst->getParent();
   auto *VectorLoop = LI->getLoopFor(PredBB);

test/Transforms/LoopVectorize/no_outside_user.ll

 ; RUN: opt -S -loop-vectorize -force-vector-interleave=1 -force-vector-width=2 < %s 2>&1 | FileCheck %s
 
-; CHECK: remark: {{.*}}: loop not vectorized: value could not be identified as an induction or reduction variable
-
 target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32-n8:16:32-S128"
 
 @f = common global i32 0, align 4
 @.str = private unnamed_addr constant [4 x i8] c"%d\0A\00", align 1
 @c = common global i32 0, align 4
 @a = common global i32 0, align 4
 @b = common global i32 0, align 4
 @e = common global i32 0, align 4
 
-; We used to vectorize this loop. But it has a value that is used outside of the
+; It has a value that is used outside of the loop
 ; and is not a recognized reduction variable "tmp17".
+; However, tmp17 does not have a cyclic dependence with any header phis. So, the
+; iteration dependence distance for tmp17 can also be widened to VF (just like
+; we do for reduction/induction).
 
-; CHECK-LABEL: @main(
-; CHECK-NOT: <2 x i32>
+; CHECK-LABEL: @test1(
+; CHECK: %vec.ind = phi <2 x i32>
+; CHECK: [[CMP:%[a-zA-Z0-9.]+]] = icmp sgt <2 x i32> %vec.ind, <i32 10, i32 10>
+; CHECK: %predphi = select <2 x i1> [[CMP]], <2 x i32> <i32 1, i32 1>, <2 x i32> zeroinitializer
+
+; CHECK-LABEL: middle.block:
+; CHECK:          [[E1:%[a-zA-Z0-9.]+]] = extractelement <2 x i32> %predphi, i32 1
+
+; CHECK-LABEL: f1.exit.loopexit:
+; CHECK:          %.lcssa = phi i32 [ %tmp17, %bb16 ], [ [[E1]], %middle.block ]
 
-define i32 @main()  {
+define i32 @test1()  {
 bb:
   %b.promoted = load i32, i32* @b, align 4
   br label %.lr.ph.i
 
 .lr.ph.i:
   %tmp8 = phi i32 [ %tmp18, %bb16 ], [ %b.promoted, %bb ]
   %tmp2 = icmp sgt i32 %tmp8, 10
   br i1 %tmp2, label %bb16, label %bb10
 
 bb10:
   br label %bb16
 
 bb16:
   %tmp17 = phi i32 [ 0, %bb10 ], [ 1, %.lr.ph.i ]
   %tmp18 = add nsw i32 %tmp8, 1
   %tmp19 = icmp slt i32 %tmp18, 4
   br i1 %tmp19, label %.lr.ph.i, label %f1.exit.loopexit
 
 f1.exit.loopexit:
   %.lcssa = phi i32 [ %tmp17, %bb16 ]
   ret i32 %.lcssa
 }
+
+; non-hdr phi depends on header phi.
+; CHECK-LABEL: @test2(
+; CHECK: %vec.ind = phi <2 x i32>
+; CHECK: [[CMP:%[a-zA-Z0-9.]+]] = icmp sgt <2 x i32> %vec.ind, <i32 10, i32 10>
+; CHECK: %predphi = select <2 x i1> [[CMP]], <2 x i32> <i32 1, i32 1>, <2 x i32> %vec.ind
+
+; CHECK-LABEL: middle.block:
+; CHECK:          [[E1:%[a-zA-Z0-9.]+]] = extractelement <2 x i32> %predphi, i32 1
+
+; CHECK-LABEL: f1.exit.loopexit:
+; CHECK:          %.lcssa = phi i32 [ %tmp17, %bb16 ], [ [[E1]], %middle.block ]
+define i32 @test2()  {
+bb:
+  %b.promoted = load i32, i32* @b, align 4
+  br label %.lr.ph.i
+
+.lr.ph.i:
+  %tmp8 = phi i32 [ %tmp18, %bb16 ], [ %b.promoted, %bb ]
+  %tmp2 = icmp sgt i32 %tmp8, 10
+  br i1 %tmp2, label %bb16, label %bb10
+
+bb10:
+  br label %bb16
+
+bb16:
+  %tmp17 = phi i32 [ %tmp8, %bb10 ], [ 1, %.lr.ph.i ]
+  %tmp18 = add nsw i32 %tmp8, 1
+  %tmp19 = icmp slt i32 %tmp18, 4
+  br i1 %tmp19, label %.lr.ph.i, label %f1.exit.loopexit
+
+f1.exit.loopexit:
+  %.lcssa = phi i32 [ %tmp17, %bb16 ]
+  ret i32 %.lcssa
+}
+
+; more than 2 incoming values for tmp17 phi that is used outside loop.
+; CHECK-LABEL: test3(
+; CHECK-LABEL: vector.body:
+; CHECK:          %predphi = select <2 x i1>
+; CHECK:          %predphi1 = select <2 x i1>
+
+; CHECK-LABEL: middle.block:
+; CHECK:          [[E1:%[a-zA-Z0-9.]+]] = extractelement <2 x i32> %predphi1, i32 1
+
+; CHECK-LABEL: f1.exit.loopexit:
+; CHECK:          phi i32 [ %tmp17, %bb16 ], [ [[E1]], %middle.block ]
+define i32 @test3(i32 %N)  {
+bb:
+  %b.promoted = load i32, i32* @b, align 4
+  br label %.lr.ph.i
+
+.lr.ph.i:
+  %tmp8 = phi i32 [ %tmp18, %bb16 ], [ %b.promoted, %bb ]
+  %tmp2 = icmp sgt i32 %tmp8, 10
+  br i1 %tmp2, label %bb16, label %bb10
+
+bb10:
+  %cmp = icmp sgt i32 %tmp8, %N
+  br i1  %cmp, label %bb12, label %bb16
+
+bb12:
+  br label %bb16
+
+bb16:
+  %tmp17 = phi i32 [ 0, %bb10 ], [ 1, %.lr.ph.i ], [ 2, %bb12 ]
+  %tmp18 = add nsw i32 %tmp8, 1
+  %tmp19 = icmp slt i32 %tmp18, 4
+  br i1 %tmp19, label %.lr.ph.i, label %f1.exit.loopexit
+
+f1.exit.loopexit:
+  %.lcssa = phi i32 [ %tmp17, %bb16 ]
+  ret i32 %.lcssa
+}
+
+; more than one incoming value for outside user: %.lcssa
+; CHECK-LABEL: test4(
+; CHECK-LABEL: vector.body:
+; CHECK:          %predphi = select <2 x i1>
+
+; CHECK-LABEL: middle.block:
+; CHECK:          [[E1:%[a-zA-Z0-9.]+]] = extractelement <2 x i32> %predphi, i32 1
+
+; CHECK-LABEL: f1.exit.loopexit.loopexit:
+; CHECK:          %tmp17.lcssa = phi i32 [ %tmp17, %bb16 ], [ [[E1]], %middle.block ]
+; CHECK-NEXT:     br label %f1.exit.loopexit
+
+; CHECK-LABEL: f1.exit.loopexit:
+; CHECK:          %.lcssa = phi i32 [ 2, %bb ], [ %tmp17.lcssa, %f1.exit.loopexit.loopexit ]
+define i32 @test4(i32 %N)  {
+bb:
+  %b.promoted = load i32, i32* @b, align 4
+  %icmp = icmp slt i32 %b.promoted, %N
+  br i1 %icmp, label %f1.exit.loopexit, label %.lr.ph.i
+
+.lr.ph.i:
+  %tmp8 = phi i32 [ %tmp18, %bb16 ], [ %b.promoted, %bb ]
+  %tmp2 = icmp sgt i32 %tmp8, 10
+  br i1 %tmp2, label %bb16, label %bb10
+
+bb10:
+  br label %bb16
+
+bb16:
+  %tmp17 = phi i32 [ 0, %bb10 ], [ 1, %.lr.ph.i ]
+  %tmp18 = add nsw i32 %tmp8, 1
+  %tmp19 = icmp slt i32 %tmp18, 4
+  br i1 %tmp19, label %.lr.ph.i, label %f1.exit.loopexit
+
+f1.exit.loopexit:
+  %.lcssa = phi i32 [ %tmp17, %bb16 ], [ 2, %bb ]
+  ret i32 %.lcssa
+}
+
+; non hdr phi that depends on reduction and is used outside the loop.
+; reduction phis are only allowed to have bump or reduction operations as the inside user, so we should
+; not vectorize this.
+; CHECK-LABEL: reduction_sum(
+; CHECK-NOT: <2 x i32>
+define i32 @reduction_sum(i32 %n, i32* noalias nocapture %A, i32* noalias nocapture %B) nounwind uwtable readonly noinline ssp {
+entry:
+  %c1 = icmp sgt i32 %n, 0
+  br i1 %c1, label %header, label %._crit_edge
+
+header:                                           ; preds = %0, %.lr.ph
+  %indvars.iv = phi i64 [ %indvars.iv.next, %bb16 ], [ 0, %entry ]
+  %sum.02 = phi i32 [ %c9, %bb16 ], [ 0, %entry ]
+  %c2 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %c3 = load i32, i32* %c2, align 4
+  %c4 = getelementptr inbounds i32, i32* %B, i64 %indvars.iv
+  %c5 = load i32, i32* %c4, align 4
+  %tmp2 = icmp sgt i32 %sum.02, 10
+  br i1 %tmp2, label %bb16, label %bb10
+
+bb10:
+  br label %bb16
+
+bb16:
+  %tmp17 = phi i32 [ %sum.02, %bb10 ], [ 1, %header ]
+  %c6 = trunc i64 %indvars.iv to i32
+  %c7 = add i32 %sum.02, %c6
+  %c8 = add i32 %c7, %c3
+  %c9 = add i32 %c8, %c5
+  %indvars.iv.next = add i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %n
+  br i1 %exitcond, label %._crit_edge, label %header
+
+._crit_edge:                                      ; preds = %.lr.ph, %0
+  %sum.0.lcssa = phi i32 [ 0, %entry ], [ %c9, %bb16 ]
+  %nonhdr.lcssa = phi i32 [ 1, %entry], [ %tmp17, %bb16 ]
+  ret i32 %sum.0.lcssa
+}
+
+; cyclic dependency with induction var
+; cannot vectorize.
+; CHECK-LABEL: cyclic_dep_with_indvar(
+; CHECK-NOT: <2 x i32>
+define i32 @cyclic_dep_with_indvar()  {
+bb:
+  %b.promoted = load i32, i32* @b, align 4
+  br label %.lr.ph.i
+
+.lr.ph.i:
+  %iv = phi i32 [ %ivnext, %bb16 ], [ %b.promoted, %bb ]
+  %tmp2 = icmp sgt i32 %iv, 10
+  br i1 %tmp2, label %bb16, label %bb10
+
+bb10:
+  br label %bb16
+
+bb16:
+  %tmp17 = phi i32 [ 0, %bb10 ], [ %iv, %.lr.ph.i ]
+  %ivnext = add nsw i32 %tmp17, 1
+  %tmp19 = icmp slt i32 %ivnext, 4
+  br i1 %tmp19, label %.lr.ph.i, label %f1.exit.loopexit
+
+f1.exit.loopexit:
+  %.lcssa = phi i32 [ %tmp17, %bb16 ]
+  ret i32 %.lcssa
+}
+
+; non-reduction phi 'tmp17' used outside loop has cyclic dependence with reduction phi
+; (%x.05)
+; cannot vectorize.
+; CHECK-LABEL: not_valid_reduction(
+; CHECK-NOT: <2 x i32>
+define i32 @not_valid_reduction(i32 %n, i32* noalias nocapture %A) nounwind uwtable readonly {
+entry:
+  %cmp4 = icmp sgt i32 %n, 0
+  br i1 %cmp4, label %for.body, label %for.end
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %latch ], [ 0, %entry ]
+  %x.05 = phi i32 [ %tmp17, %latch ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv
+  %tmp0 = load i32, i32* %arrayidx, align 4
+  %tmp2 = icmp sgt i64 %indvars.iv, 10
+  %sub = sub nsw i32 %x.05, %tmp0
+  br i1 %tmp2, label %bb16, label %bb10
+
+bb10:
+  br label %bb16
+
+bb16:
+  %tmp17 = phi i32 [ 1, %bb10 ], [ %sub, %for.body ]
+  br label %latch
+
+latch:
+  %indvars.iv.next = add i64 %indvars.iv, 1
+  %lftr.wideiv = trunc i64 %indvars.iv.next to i32
+  %exitcond = icmp eq i32 %lftr.wideiv, %n
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  %x.0.lcssa = phi i32 [ 0, %entry ], [ %tmp17 , %latch ]
+  ret i32 %x.0.lcssa
+}