[VPlan] Turn VPReductionRecipe into a VPValue

[dmgreen]

Summary

This converts the VPReductionRecipe into a VPValue, like other VPRecipe's in preparation for traversing def-use chains.

It doesn't yet change how the VPReductionRecipes are created. It will need to call replaceAllUsesWith from the original recipe they replace, but that is not done yet as VPWidenRecipe need to be created first.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.cpp

941–942

now that this is a VPValue we should probably just reference the VPValue name using printAsOperand(), which will use the underlying value if available.

[dmgreen]

Thanks. I've updated the printing, but not rebased this onto any other patches yet.

[dmgreen]

Rebase and update.

[dmgreen]

Rebase

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8097

nit: assign in if() and use below?

8121

The recipes that get converted should also be updated to use State directly to map the result VPValue to the generated IR. Could this just be State.set(this, NextInChain, Part)?

llvm/lib/Transforms/Vectorize/VPlan.cpp

951

If it's not too much trouble, it would also be good to add a test to vplan-printing.ll

[dmgreen]

Ooops. I thought this was already using State.set, but uploaded the wrong version. Now with that and the other changes.

[fhahn]

LGTM, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7978

Now that both VPWidenREcipe and VPRedcutionRecipe are VPValues, we have to update all users of WidenRecipe with RedRecipe.

7986

We need to update the users of VPWidenRecipe's VPValue or assert that there are none.

[dmgreen]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7978

I think these were happening in the other order, if I am understanding you correctly. The VPWidenRecipe patch is added on top of this, and hopefully fixes up what you are referring to?

7986

Hmm. This is the cmp in a min/max pattern. I am hoping that it would only have one user that we have removed above. At least, I can't seem to get it to vectorize when it has multiple uses. I'll make sure this is an assert in the VPWiden patch.

[fhahn]

small nit for the commit message: might be good to mention that this also turns it into a VPUser.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

7978

Yes I think that should be fine after checking the other patch. Looks like I looked at the patches out-of-order for the final round.

7986

Sounds good, Could you perhaps add an assert that the users are empty to D88447?

[fhahn]

llvm/lib/Transforms/Vectorize/VPlan.cpp

111

now that VPReductionRecipe is also a VPUser, it should also be added here. (this will go away once all recipes have been converted)

[dmgreen]

llvm/lib/Transforms/Vectorize/VPlan.cpp

111

Yeah thanks, I noticed this one as I was getting the patch together for committing. I was trying a sanitizer build to check they are OK, which is taking a rather long time..

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

for (Instruction *R : ReductionOperations) {
       VPValue *VecOp = Plan->getVPValue(R->getOperand(VecOpId));
 
       auto *CondOp = CM.foldTailByMasking()
                          ? RecipeBuilder.createBlockInMask(R->getParent(), Plan)
                          : nullptr;
       VPReductionRecipe *RedRecipe = new VPReductionRecipe(
           &RdxDesc, R, ChainOp, VecOp, CondOp, Legal->hasFunNoNaNAttr(), TTI);
       WidenRecipe->getParent()->insert(RedRecipe, WidenRecipe->getIterator());
       WidenRecipe->eraseFromParent();
 
       if (Kind == RecurrenceDescriptor::RK_IntegerMinMax ||
           Kind == RecurrenceDescriptor::RK_FloatMinMax) {
         VPRecipeBase *CompareRecipe =
             RecipeBuilder.getRecipe(cast<Instruction>(R->getOperand(0)));
         assert(isa<VPWidenRecipe>(CompareRecipe) &&
                "Expected to replace a VPWidenSC");
         CompareRecipe->eraseFromParent();
       }
       Chain = R;
     }
   }
 }
 
 Value* LoopVectorizationPlanner::VPCallbackILV::
 getOrCreateVectorValues(Value *V, unsigned Part) {
void VPInterleaveRecipe::execute(VPTransformState &State) {
   assert(!State.Instance && "Interleave group being replicated.");
   State.ILV->vectorizeInterleaveGroup(IG, State, getAddr(), getMask());
 }
 
 void VPReductionRecipe::execute(VPTransformState &State) {
   assert(!State.Instance && "Reduction being replicated.");
   for (unsigned Part = 0; Part < State.UF; ++Part) {
     RecurrenceDescriptor::RecurrenceKind Kind = RdxDesc->getRecurrenceKind();
-    Value *NewVecOp = State.get(VecOp, Part);
-    if (CondOp) {
-      Value *NewCond = State.get(CondOp, Part);
+    Value *NewVecOp = State.get(getVecOp(), Part);
+    if (VPValue *Cond = getCondOp()) {
+      Value *NewCond = State.get(Cond, Part);
       VectorType *VecTy = cast<VectorType>(NewVecOp->getType());
       Constant *Iden = RecurrenceDescriptor::getRecurrenceIdentity(
           Kind, RdxDesc->getMinMaxRecurrenceKind(), VecTy->getElementType());
       Constant *IdenVec =
           ConstantVector::getSplat(VecTy->getElementCount(), Iden);
       Value *Select = State.Builder.CreateSelect(NewCond, NewVecOp, IdenVec);
       NewVecOp = Select;
     }
     Value *NewRed =
         createTargetReduction(State.Builder, TTI, *RdxDesc, NewVecOp, NoNaN);
-    Value *PrevInChain = State.get(ChainOp, Part);
+    Value *PrevInChain = State.get(getChainOp(), Part);
     Value *NextInChain;
     if (Kind == RecurrenceDescriptor::RK_IntegerMinMax ||
         Kind == RecurrenceDescriptor::RK_FloatMinMax) {
       NextInChain =
           createMinMaxOp(State.Builder, RdxDesc->getMinMaxRecurrenceKind(),
                          NewRed, PrevInChain);
     } else {
       NextInChain = State.Builder.CreateBinOp(
-          (Instruction::BinaryOps)I->getOpcode(), NewRed, PrevInChain);
+          (Instruction::BinaryOps)getUnderlyingInstr()->getOpcode(), NewRed,
+          PrevInChain);
     }
-    State.ValueMap.setVectorValue(I, Part, NextInChain);
+    State.set(this, getUnderlyingInstr(), NextInChain, Part);
   }
 }
 
 void VPReplicateRecipe::execute(VPTransformState &State) {
   if (State.Instance) { // Generate a single instance.
     State.ILV->scalarizeInstruction(Ingredient, *this, *State.Instance,
                                     IsPredicated, State);
     // Insert scalar instance packing it into a vector.

llvm/lib/Transforms/Vectorize/VPlan.h

public:
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 
   const InterleaveGroup<Instruction> *getInterleaveGroup() { return IG; }
 };
 
 /// A recipe to represent inloop reduction operations, performing a reduction on
 /// a vector operand into a scalar value, and adding the result to a chain.
-class VPReductionRecipe : public VPRecipeBase {
+/// The Operands are {ChainOp, VecOp, [Condition]}.
+class VPReductionRecipe : public VPRecipeBase, public VPValue, public VPUser {
   /// The recurrence decriptor for the reduction in question.
   RecurrenceDescriptor *RdxDesc;
-  /// The original instruction being converted to a reduction.
-  Instruction *I;
-  /// The VPValue of the vector value to be reduced.
-  VPValue *VecOp;
-  /// The VPValue of the scalar Chain being accumulated.
-  VPValue *ChainOp;
-  /// The VPValue of the condition for the block.
-  VPValue *CondOp;
   /// Fast math flags to use for the resulting reduction operation.
   bool NoNaN;
   /// Pointer to the TTI, needed to create the target reduction
   const TargetTransformInfo *TTI;
 
 public:
   VPReductionRecipe(RecurrenceDescriptor *R, Instruction *I, VPValue *ChainOp,
                     VPValue *VecOp, VPValue *CondOp, bool NoNaN,
                     const TargetTransformInfo *TTI)
-      : VPRecipeBase(VPReductionSC), RdxDesc(R), I(I), VecOp(VecOp),
-        ChainOp(ChainOp), CondOp(CondOp), NoNaN(NoNaN), TTI(TTI) {}
+      : VPRecipeBase(VPRecipeBase::VPReductionSC),
+        VPValue(VPValue::VPReductionSC, I), VPUser({ChainOp, VecOp}),
+        RdxDesc(R), NoNaN(NoNaN), TTI(TTI) {
+    if (CondOp)
+      addOperand(CondOp);
+  }
 
   ~VPReductionRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
+  static inline bool classof(const VPValue *V) {
+    return V->getVPValueID() == VPValue::VPReductionSC;
+  }
   static inline bool classof(const VPRecipeBase *V) {
     return V->getVPRecipeID() == VPRecipeBase::VPReductionSC;
   }
 
   /// Generate the reduction in the loop
   void execute(VPTransformState &State) override;
 
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
+
+  /// The VPValue of the scalar Chain being accumulated.
+  VPValue *getChainOp() const { return getOperand(0); }
+  /// The VPValue of the vector value to be reduced.
+  VPValue *getVecOp() const { return getOperand(1); }
+  /// The VPValue of the condition for the block.
+  VPValue *getCondOp() const {
+    return getNumOperands() > 2 ? getOperand(2) : nullptr;
+  }
 };
 
 /// VPReplicateRecipe replicates a given instruction producing multiple scalar
 /// copies of the original scalar type, one per lane, instead of producing a
 /// single copy of widened type for all lanes. If the instruction is known to be
 /// uniform only one copy, per lane zero, will be generated.
 class VPReplicateRecipe : public VPRecipeBase, public VPUser {
   /// The instruction being replicated.

llvm/lib/Transforms/Vectorize/VPlan.cpp

 //===----------------------------------------------------------------------===//
 
 #include "VPlan.h"
 #include "VPlanDominatorTree.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Twine.h"
+#include "llvm/Analysis/IVDescriptors.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Value.h"
VPUser *VPRecipeBase::toVPUser() {
   if (auto *U = dyn_cast<VPBlendRecipe>(this))
     return U;
   if (auto *U = dyn_cast<VPInterleaveRecipe>(this))
     return U;
   if (auto *U = dyn_cast<VPReplicateRecipe>(this))
     return U;
   if (auto *U = dyn_cast<VPBranchOnMaskRecipe>(this))
     return U;
   if (auto *U = dyn_cast<VPWidenMemoryInstructionRecipe>(this))
     return U;
+  if (auto *U = dyn_cast<VPReductionRecipe>(this))
+    return U;
   return nullptr;
 }
 
 VPValue *VPRecipeBase::toVPValue() {
   if (auto *V = dyn_cast<VPInstruction>(this))
     return V;
+  if (auto *V = dyn_cast<VPReductionRecipe>(this))
+    return V;
   if (auto *V = dyn_cast<VPWidenMemoryInstructionRecipe>(this))
     return V;
   if (auto *V = dyn_cast<VPWidenCallRecipe>(this))
     return V;
   if (auto *V = dyn_cast<VPWidenSelectRecipe>(this))
     return V;
   if (auto *V = dyn_cast<VPWidenGEPRecipe>(this))
     return V;
   return nullptr;
 }
 
 const VPValue *VPRecipeBase::toVPValue() const {
   if (auto *V = dyn_cast<VPInstruction>(this))
     return V;
+  if (auto *V = dyn_cast<VPReductionRecipe>(this))
+    return V;
   if (auto *V = dyn_cast<VPWidenMemoryInstructionRecipe>(this))
     return V;
   if (auto *V = dyn_cast<VPWidenCallRecipe>(this))
     return V;
   if (auto *V = dyn_cast<VPWidenSelectRecipe>(this))
     return V;
   if (auto *V = dyn_cast<VPWidenGEPRecipe>(this))
     return V;
for (unsigned I = 0, E = getNumIncomingValues(); I < E; ++I) {
       getIncomingValue(I)->printAsOperand(O, SlotTracker);
       O << "/";
       getMask(I)->printAsOperand(O, SlotTracker);
     }
   }
 }
 
 void VPReductionRecipe::print(raw_ostream &O, const Twine &Indent,
                               VPSlotTracker &SlotTracker) const {
-  O << "\"REDUCE of" << *I << " as ";
-  ChainOp->printAsOperand(O, SlotTracker);
-  O << " + reduce(";
-  VecOp->printAsOperand(O, SlotTracker);
-  if (CondOp) {
+  O << "\"REDUCE ";
+  printAsOperand(O, SlotTracker);
+  O << " = ";
+  getChainOp()->printAsOperand(O, SlotTracker);
+  O << " + reduce." << Instruction::getOpcodeName(RdxDesc->getRecurrenceBinOp())
+    << " (";
+  getVecOp()->printAsOperand(O, SlotTracker);
+  if (getCondOp()) {
     O << ", ";
-    CondOp->printAsOperand(O, SlotTracker);
+    getCondOp()->printAsOperand(O, SlotTracker);
   }
   O << ")";
 }
 
 void VPReplicateRecipe::print(raw_ostream &O, const Twine &Indent,
                               VPSlotTracker &SlotTracker) const {
   O << "\"" << (IsUniform ? "CLONE " : "REPLICATE ")
     << VPlanIngredient(Ingredient);

llvm/lib/Transforms/Vectorize/VPlanValue.h

public:
   /// An enumeration for keeping track of the concrete subclass of VPValue that
   /// are actually instantiated. Values of this enumeration are kept in the
   /// SubclassID field of the VPValue objects. They are used for concrete
   /// type identification.
   enum {
     VPValueSC,
     VPInstructionSC,
     VPMemoryInstructionSC,
+    VPReductionSC,
     VPVWidenCallSC,
+    VPVWidenGEPSC,
     VPVWidenSelectSC,
-    VPVWidenGEPSC
   };
 
   VPValue(Value *UV = nullptr, VPDef *Def = nullptr)
       : VPValue(VPValueSC, UV, Def) {}
   VPValue(const VPValue &) = delete;
   VPValue &operator=(const VPValue &) = delete;
 
   virtual ~VPValue();

llvm/test/Transforms/LoopVectorize/vplan-printing.ll

 ; REQUIRES: asserts
 
-; RUN: opt -loop-vectorize -debug-only=loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -disable-output %s 2>&1 | FileCheck %s
+; RUN: opt -loop-vectorize -debug-only=loop-vectorize -force-vector-interleave=1 -force-vector-width=4 -prefer-inloop-reductions -disable-output %s 2>&1 | 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"
 
 ; Tests for printing VPlans.
 
 define void @print_call_and_memory(i64 %n, float* noalias %y, float* noalias %x) nounwind uwtable {
 ; CHECK: N0 [label =
 ; CHECK-NEXT: "for.body:\n" +
for.body:                                         ; preds = %entry, %for.body
   %iv.next = add i64 %iv, 1
   %exitcond = icmp eq i64 %iv.next, %n
   br i1 %exitcond, label %for.end, label %for.body
 
 for.end:                                          ; preds = %for.body, %entry
   ret void
 }
 
+define float @print_reduction(i64 %n, float* noalias %y) {
+; CHECK: N0 [label =
+; CHECK-NEXT: "for.body:\n" +
+; CHECK-NEXT:       "WIDEN-INDUCTION %iv = phi %iv.next, 0\l" +
+; CHECK-NEXT:       "WIDEN-PHI %red = phi %red.next, 0.000000e+00\l" +
+; CHECK-NEXT:       "CLONE %arrayidx = getelementptr %y, %iv\l" +
+; CHECK-NEXT:       "WIDEN ir<%lv> = load ir<%arrayidx>\l" +
+; CHECK-NEXT:       "REDUCE ir<%red.next> = ir<%red> + reduce.fadd (ir<%lv>)\l"
+; CHECK-NEXT:   ]
+
+entry:
+  br label %for.body
+
+for.body:                                         ; preds = %entry, %for.body
+  %iv = phi i64 [ %iv.next, %for.body ], [ 0, %entry ]
+  %red = phi float [ %red.next, %for.body ], [ 0.0, %entry ]
+  %arrayidx = getelementptr inbounds float, float* %y, i64 %iv
+  %lv = load float, float* %arrayidx, align 4
+  %red.next = fadd fast float %lv, %red
+  %iv.next = add i64 %iv, 1
+  %exitcond = icmp eq i64 %iv.next, %n
+  br i1 %exitcond, label %for.end, label %for.body
+
+for.end:                                          ; preds = %for.body, %entry
+  ret float %red.next
+}
+
 declare float @llvm.sqrt.f32(float) nounwind readnone