[LV] Model if-converted phi node cost

[mssimpso]

Summary

Phi nodes in non-header blocks are converted to select instructions after if-conversion. This patch updates the cost model to account for the selects.

[mkuper]

LGTM

lib/Transforms/Vectorize/LoopVectorize.cpp

7280 ↗

(On Diff #94742)

We don't need to handle Phi->getNumIncomingValues() == 0 - it doesn't pass the verifier, right?

7285 ↗

(On Diff #94742)

This returns 1 by default, right? I'm not entirely sure that's the right thing to do here, but it's probably no worse than the current state.

test/Transforms/LoopVectorize/phi-cost.ll

7 ↗

(On Diff #94742)

Please also add a CHECK for the induction phi.

[mssimpso]

Thanks, Michael!

lib/Transforms/Vectorize/LoopVectorize.cpp

7280 ↗

(On Diff #94742)

That's right.

7285 ↗

(On Diff #94742)

Yes, it returns 1. We went with getCFInstrCost(Instrunction::PHI) when doing the inserts for predicated instructions, so I thought it would be good to be consistent.

test/Transforms/LoopVectorize/phi-cost.ll

7 ↗

(On Diff #94742)

Will do.

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

unsigned LoopVectorizationCostModel::getInstructionCost(Instruction *I,
   case Instruction::PHI: {
     auto *Phi = cast<PHINode>(I);
 
     // First-order recurrences are replaced by vector shuffles inside the loop.
     if (VF > 1 && Legal->isFirstOrderRecurrence(Phi))
       return TTI.getShuffleCost(TargetTransformInfo::SK_ExtractSubvector,
                                 VectorTy, VF - 1, VectorTy);
 
-    // TODO: IF-converted IFs become selects.
-    return 0;
+    // Phi nodes in non-header blocks (not inductions, reductions, etc.) are
+    // converted into select instructions. We require N - 1 selects per phi
+    // node, where N is the number of incoming values.
+    if (VF > 1 && Phi->getParent() != TheLoop->getHeader())
+      return (Phi->getNumIncomingValues() - 1) *
+             TTI.getCmpSelInstrCost(
+                 Instruction::Select, ToVectorTy(Phi->getType(), VF),
+                 ToVectorTy(Type::getInt1Ty(Phi->getContext()), VF));
+
+    return TTI.getCFInstrCost(Instruction::PHI);
   }
   case Instruction::UDiv:
   case Instruction::SDiv:
   case Instruction::URem:
   case Instruction::SRem:
     // If we have a predicated instruction, it may not be executed for each
     // vector lane. Get the scalarization cost and scale this amount by the
     // probability of executing the predicated block. If the instruction is not

llvm/trunk/test/Transforms/LoopVectorize/phi-cost.ll

+; REQUIRES: asserts
+; RUN: opt < %s -loop-vectorize -force-vector-width=2 -force-vector-interleave=1 -instcombine -debug-only=loop-vectorize -disable-output -print-after=instcombine 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+
+; CHECK-LABEL: phi_two_incoming_values
+; CHECK:       LV: Found an estimated cost of 1 for VF 2 For instruction: %i = phi i64 [ %i.next, %if.end ], [ 0, %entry ]
+; CHECK:       LV: Found an estimated cost of 1 for VF 2 For instruction: %tmp5 = phi i32 [ %tmp1, %for.body ], [ %tmp4, %if.then ]
+; CHECK:       vector.body:
+; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
+; CHECK:         [[WIDE_LOAD:%.*]] = load <2 x i32>, <2 x i32>* {{.*}}
+; CHECK:         [[TMP5:%.*]] = icmp sgt <2 x i32> [[WIDE_LOAD]], zeroinitializer
+; CHECK-NEXT:    [[TMP6:%.*]] = add <2 x i32> [[WIDE_LOAD]], <i32 1, i32 1>
+; CHECK-NEXT:    [[PREDPHI:%.*]] = select <2 x i1> [[TMP5]], <2 x i32> [[TMP6]], <2 x i32> [[WIDE_LOAD]]
+; CHECK:         store <2 x i32> [[PREDPHI]], <2 x i32>* {{.*}}
+; CHECK-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 2
+;
+define void @phi_two_incoming_values(i32* %a, i32* %b, i64 %n) {
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i64 [ %i.next, %if.end ], [ 0, %entry ]
+  %tmp0 = getelementptr inbounds i32, i32* %a, i64 %i
+  %tmp1 = load i32, i32* %tmp0, align 4
+  %tmp2 = getelementptr inbounds i32, i32* %b, i64 %i
+  %tmp3 = icmp sgt i32 %tmp1, 0
+  br i1 %tmp3, label %if.then, label %if.end
+
+if.then:
+  %tmp4 = add i32 %tmp1, 1
+  br label %if.end
+
+if.end:
+  %tmp5 = phi i32 [ %tmp1, %for.body ], [ %tmp4, %if.then ]
+  store i32 %tmp5, i32* %tmp2, align 4
+  %i.next = add i64 %i, 1
+  %cond = icmp eq i64 %i, %n
+  br i1 %cond, label %for.end, label %for.body
+
+for.end:
+  ret void
+}
+
+; CHECK-LABEL: phi_three_incoming_values
+; CHECK:       LV: Found an estimated cost of 1 for VF 2 For instruction: %i = phi i64 [ %i.next, %if.end ], [ 0, %entry ]
+; CHECK:       LV: Found an estimated cost of 2 for VF 2 For instruction: %tmp8 = phi i32 [ 9, %for.body ], [ 3, %if.then ], [ %tmp7, %if.else ]
+; CHECK:       vector.body:
+; CHECK-NEXT:    [[INDEX:%.*]] = phi i64 [ 0, %vector.ph ], [ [[INDEX_NEXT:%.*]], %vector.body ]
+; CHECK:         [[PREDPHI:%.*]] = select <2 x i1> {{.*}}, <2 x i32> <i32 3, i32 3>, <2 x i32> <i32 9, i32 9>
+; CHECK:         [[PREDPHI7:%.*]] = select <2 x i1> {{.*}}, <2 x i32> {{.*}}, <2 x i32> [[PREDPHI]]
+; CHECK:         store <2 x i32> [[PREDPHI7]], <2 x i32>* {{.*}}
+; CHECK-NEXT:    [[INDEX_NEXT]] = add i64 [[INDEX]], 2
+;
+define void @phi_three_incoming_values(i32* %a, i32* %b, i64 %n) {
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i64 [ %i.next, %if.end ], [ 0, %entry ]
+  %tmp0 = getelementptr inbounds i32, i32* %a, i64 %i
+  %tmp1 = load i32, i32* %tmp0, align 4
+  %tmp2 = getelementptr inbounds i32, i32* %b, i64 %i
+  %tmp3 = load i32, i32* %tmp2, align 4
+  %tmp4 = icmp sgt i32 %tmp1, %tmp3
+  br i1 %tmp4, label %if.then, label %if.end
+
+if.then:
+  %tmp5 = icmp sgt i32 %tmp1, 19
+  br i1 %tmp5, label %if.end, label %if.else
+
+if.else:
+  %tmp6 = icmp slt i32 %tmp3, 4
+  %tmp7 = select i1 %tmp6, i32 4, i32 5
+  br label %if.end
+
+if.end:
+  %tmp8 = phi i32 [ 9, %for.body ], [ 3, %if.then ], [ %tmp7, %if.else ]
+  store i32 %tmp8, i32* %tmp0, align 4
+  %i.next = add i64 %i, 1
+  %cond = icmp eq i64 %i, %n
+  br i1 %cond, label %for.end, label %for.body
+
+for.end:
+  ret void
+}