[LV] Fix PR45525: Incorrect assert in blend recipe

[gilr]

Summary

Fix an assert introduced in 41ed5d856c1: a phi with a single predecessor and a mask is a valid case, already supported.

[fhahn]

I think this is related to PR44800, which has similarly redundant phis, but with 2 incoming values from the same block. Relaxing the assertion seems a fine workaround for now, but I think ideally we would eliminate such redundant PHIs in VPlan later on.

LGTM, with some suggestions for the test. It would be good to wait with committing a day or so, in case there are additional comments.

llvm/test/Transforms/LoopVectorize/pr45525.ll

2

Should this have -force-vector-width=4 or something, to not rely on the cost model?

44

it would be nice to rename the values to have a bit more compact/descriptive names, e.g. %iv and %iv.next and so on instead of the longer names.

45

Branch on undef is UB, please use a different branch condition (e.g. through a parameter).

48

Better to also have a concrete value instead of undef. Also, might be good to have a user of the value to make the test more robust (in case we decide to remove unused values in a VP2VP transform later on).

[fhahn]

Oh and it would be great if you could add a bit more details to the commit message title :)

[gilr]

Addressed comments and narrowed LIT checks to the relevant vectorized instructions.
Thanks @fhahn !

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

void VPBlendRecipe::execute(VPTransformState &State) {
   // At this point we generate the predication tree. There may be
   // duplications since this is a simple recursive scan, but future
   // optimizations will clean it up.
 
   unsigned NumIncoming = getNumIncomingValues();
 
   // Generate a sequence of selects of the form:
   // SELECT(Mask3, In3,
-  //      SELECT(Mask2, In2,
-  //                   ( ...)))
+  //        SELECT(Mask2, In2,
+  //               SELECT(Mask1, In1,
+  //                      In0)))
+  // Note that Mask0 is never used: lanes for which no path reaches this phi and
+  // are essentially undef are taken from In0.
   InnerLoopVectorizer::VectorParts Entry(State.UF);
   for (unsigned In = 0; In < NumIncoming; ++In) {
     for (unsigned Part = 0; Part < State.UF; ++Part) {
       // We might have single edge PHIs (blocks) - use an identity
       // 'select' for the first PHI operand.
       Value *In0 = State.get(getIncomingValue(In), Part);
       if (In == 0)
         Entry[Part] = In0; // Initialize with the first incoming value.

llvm/lib/Transforms/Vectorize/VPlan.h

 
 /// A recipe for vectorizing a phi-node as a sequence of mask-based select
 /// instructions.
 class VPBlendRecipe : public VPRecipeBase {
   PHINode *Phi;
 
   /// The blend operation is a User of the incoming values and of their
   /// respective masks, ordered [I0, M0, I1, M1, ...]. Note that a single value
-  /// would be incoming with a full mask for which there is no VPValue.
+  /// might be incoming with a full mask for which there is no VPValue.
   VPUser User;
 
 public:
   VPBlendRecipe(PHINode *Phi, ArrayRef<VPValue *> Operands)
       : VPRecipeBase(VPBlendSC), Phi(Phi), User(Operands) {
-    assert(((Operands.size() == 1) ||
-            (Operands.size() > 2 && Operands.size() % 2 == 0)) &&
-           "Expected either a single incoming value or a greater than two and "
-           "even number of operands");
+    assert(Operands.size() > 0 &&
+           ((Operands.size() == 1) || (Operands.size() % 2 == 0)) &&
+           "Expected either a single incoming value or a positive even number "
+           "of operands");
   }
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == VPRecipeBase::VPBlendSC;
   }
 
   /// Return the number of incoming values, taking into account that a single

llvm/test/Transforms/LoopVectorize/pr45525.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -loop-vectorize -S | FileCheck %s
+
+; Test case for PR45525. Checks that phi's with a single predecessor are supported.
+
+define void @main() {
+; CHECK-LABEL: @main(
+; CHECK-NEXT:  bb.0:
+; CHECK-NEXT:    br i1 false, label [[SCALAR_PH:%.*]], label [[VECTOR_PH:%.*]]
+; CHECK:       vector.ph:
+; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
+; CHECK:       vector.body:
+; CHECK-NEXT:    [[INDEX:%.*]] = phi i32 [ 0, [[VECTOR_PH]] ], [ [[INDEX_NEXT:%.*]], [[VECTOR_BODY]] ]
+; CHECK-NEXT:    [[BROADCAST_SPLATINSERT:%.*]] = insertelement <4 x i32> undef, i32 [[INDEX]], i32 0
+; CHECK-NEXT:    [[BROADCAST_SPLAT:%.*]] = shufflevector <4 x i32> [[BROADCAST_SPLATINSERT]], <4 x i32> undef, <4 x i32> zeroinitializer
+; CHECK-NEXT:    [[INDUCTION:%.*]] = add <4 x i32> [[BROADCAST_SPLAT]], <i32 0, i32 1, i32 2, i32 3>
+; CHECK-NEXT:    [[TMP0:%.*]] = add i32 [[INDEX]], 0
+; CHECK-NEXT:    [[INDEX_NEXT]] = add i32 [[INDEX]], 4
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[INDEX_NEXT]], 32
+; CHECK-NEXT:    br i1 [[TMP1]], label [[MIDDLE_BLOCK:%.*]], label [[VECTOR_BODY]], !llvm.loop !0
+; CHECK:       middle.block:
+; CHECK-NEXT:    [[CMP_N:%.*]] = icmp eq i32 32, 32
+; CHECK-NEXT:    br i1 [[CMP_N]], label [[BB_4:%.*]], label [[SCALAR_PH]]
+; CHECK:       scalar.ph:
+; CHECK-NEXT:    [[BC_RESUME_VAL:%.*]] = phi i32 [ 32, [[MIDDLE_BLOCK]] ], [ 0, [[BB_0:%.*]] ]
+; CHECK-NEXT:    br label [[BB_1:%.*]]
+; CHECK:       bb.1:
+; CHECK-NEXT:    [[V_LOOP_1814_0:%.*]] = phi i32 [ [[BC_RESUME_VAL]], [[SCALAR_PH]] ], [ [[INC1290:%.*]], [[BB_3:%.*]] ]
+; CHECK-NEXT:    br i1 undef, label [[BB_3]], label [[BB_2:%.*]]
+; CHECK:       bb.2:
+; CHECK-NEXT:    [[COND9203:%.*]] = phi i32 [ undef, [[BB_1]] ]
+; CHECK-NEXT:    br label [[BB_3]]
+; CHECK:       bb.3:
+; CHECK-NEXT:    [[INC1290]] = add i32 [[V_LOOP_1814_0]], 1
+; CHECK-NEXT:    [[CMP816:%.*]] = icmp ult i32 [[INC1290]], 32
+; CHECK-NEXT:    br i1 [[CMP816]], label [[BB_1]], label [[BB_4]], !llvm.loop !2
+; CHECK:       bb.4:
+; CHECK-NEXT:    ret void
+;
+bb.0:
+  br label %bb.1
+
+bb.1:                                             ; preds = %bb.3, %bb.0
+  %v_loop_1814.0 = phi i32 [ 0, %bb.0 ], [ %inc1290, %bb.3 ]
+  br i1 undef, label %bb.3, label %bb.2
+
+bb.2:                                             ; preds = %bb.1
+  %cond9203 = phi i32 [ undef, %bb.1 ]
+  br label %bb.3
+
+bb.3:                                             ; preds = %bb.2, %bb.1
+  %inc1290 = add i32 %v_loop_1814.0, 1
+  %cmp816 = icmp ult i32 %inc1290, 32
+  br i1 %cmp816, label %bb.1, label %bb.4
+
+bb.4:                                             ; preds = %bb.3
+  ret void
+}