[VPlan] Iterate over phi recipes to detect reductions to fix.

[fhahn]

Summary

After refactoring the phi recipes, we can now iterate over all header
phis in a VPlan to detect reductions when it comes to fixing them up
when tail folding.

This reduces the coupling with the cost model & legal by using the
information directly available in VPlan. It also removes a call to
getOrAddVPValue, which references the original IR value which may
become outdated after VPlan transformations.

[fhahn]

ping :)

[Ayal]

Reducing the coupling with the cost model by using information directly in VPlan is great. Have a few comments.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4298

number of operands must be 2, right?

this may be fragile, if some (cast?) vpinstruction is introduced between the VPReductionRecipe and the header phi it feeds? Since in-loop-reduction phi's require special code-gen handling, perhaps their recipes should be marked as such?

4717

ditto

9457–9458

Perhaps RecipeBuilder should allow checking if it has any (in-loop) reduction phi's, and iterate over them?

[fhahn]

Remove unnecessary check on number of operands, add assertion to catch if we miss an in-loop reduction in VPlan.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4298

number of operands must be 2, right?

It's not needed here, I removed it.

this may be fragile, if some (cast?) vpinstruction is introduced between the VPReductionRecipe and the header phi it feeds? Since in-loop-reduction phi's require special code-gen handling, perhaps their recipes should be marked as such?

Agreed, but not sure if we need to fix this issue before landing the patch?

I added an assertion in the code below to catch the case where we fail to identify an in-loop reduction in VPlan.

4717

here PhiR could also be a first order recurrence, so for now I think we need to at least make sure it's a reduction.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4298

wouldn't it be simpler, clearer and more robust if adjustRecipesForInLoopReductions() would turn on an "IsInLoop" bit inside VPWidenPhiRecipe, when converting its associated VPWiden[Select]Recipes into VPReductionRecipes?

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4298

It would be simpler, but I'm not sure if it is worth adding this extra coupling by adding a new InLoopReduction field to the general VPWidenPHIRecipe that needs to be maintained at this point? We could also just traverse the whole cycle if needed I think as in practice it should be only a very small number of steps. WDYT?

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4298

Agreed - the overhead of checking the cycle/chain to figure out if the reduction is in-loop or not, should be tolerable. It's about having recipes clearly model the code they represent up-front, during VPlan construction and/or planning, than whether to cache the results of this "isInLoop" query eagerly versus (re)running it lazily on demand during VPlan execution. A phi recipe representing an in-loop reduction is arguably conceptually distinct from a "regular" VPWidenPHIRecipe, with respect to the scalar-versus-vector data each operates on, and the epilogue each feeds. If the "cached result" needs to be updated, so may the cost of the recipe and of dependent recipes. Sounds reasonable?

4717

Agreed; "ditto" referred to asking here too directly if PhiR->isInLoopReduction().

9458

This is to avoid redundant creation of the header block in-mask when the loop contains no non-in-loop reductions?
Worth doing in a separate patch?

9458

#ifndef NDEBUG?

perhaps an overkill - would CM.getInLoopReductionChains() eventually be discarded?

9463

ditto ;-)

[fhahn]

Thanks for the latest comments!

This is just a rebase, will address comments separately!

[fhahn]

Add isInLoopReduction helper & use it instead isa<VPReductionRecipe>

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4298

I went ahead and added a VPWidenPHIRecipe::isInLoopReduction helper.

I'm not 100% sure this is in line with your suggestions, please let me know if I misunderstood and we should add a flag as well to start with :)

9458

Yes I think CM.getInLoopReductionChains is going away at some point. But until then it might be good to try to ensure they do not diverge. But I'd be more than happy to drop it as well, it might just be a bit too paranoid

[fhahn]

Clang-format.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

4298

This API looks good to me, thanks!
Adding a flag to implement it, as argued above, would also be good.
As stated elsewhere, there are actually 3 types of reductions, including two types of in-loop reductions: ordered and unordered.

9458

There's a subtle change here: BlockInMask may currently be created redundantly here if there are reductions but no in-loop reductions; this modification eliminates this redundancy.
Probably insignificant, given foldTailByMasking?

9458

I'd vote for cleaner, paranoia free code in this case.

One could verify the integrity of in-loop reduction chains (or VPlan in general?), say before code-gen; i.e., that in-loop header phi recipes are consistent with reduction recipes.

9463

nit: suffice to check if (!PhiR || PhiR->isInLoopReduction()) - the latter implies PhiR has a recurrence descriptor.

9523

Wouldn't it be better, if in addition to converting widen recipes of in-loop-reduction chains into reduction recipes here, we also convert their header phi upfront:

auto *PhiR = cast<VPWidenPHIRecipe>(RecipeBuilder.getRecipe(Phi));
PhiR->setIsInLoopReduction();

?

(Making sure to record the recipe of Phi)

llvm/lib/Transforms/Vectorize/VPlan.cpp

1076 ↗

(On Diff #343183)

(being 'const' it can't even cache the result for repeated queries...)

[fhahn]

rebased after the other phi handling refactoring patches landed. The patch now just updates the tail folding handling for reduction values to iterate over the phis in the VPlan and use VPReductionPHIRecipe directly. This reduces some late callbacks to Legal and the cost model, as well as a call to getOrAddVPValue(), which could become out-of-date after VPlan transformations.

ping :)

[Ayal]

This does look pretty simpler now :-). Adding some more thoughts, could be addressed separately.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9457–9458

Checking if (!Cond) seems redundant; if we want to avoid creating BlockInMask for the header block here unless there is at-least one reduction (although it will probably be created anyhow, especially under foldTail), may as well call createBlockInMask() repeatedly - it provides internal caching. I.e., should be renamed more accurately getOrCreateBlockInMask().

9457–9458

Perhaps wrap the following insert-select-for-non-in-loop-reduction-under-fold-tail along with the above, under adjustRecipesForReductions()? buildVPlanWithVPRecipes() has grown out of propotion.

9460

VPValue *Red = PhiR->getBackedgeValue ();?

Would be good to note that (and remember how ;-) ILV::fixReduction() later hooks up to this select, as it seems pretty useless here.

[fhahn]

Address Ayal's comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9457–9458

Checking if (!Cond) seems redundant; if we want to avoid creating BlockInMask for the header block here unless there is at-least one reduction (although it will probably be created anyhow, especially under foldTail), may as well call createBlockInMask() repeatedly - it provides internal caching. I.e., should be renamed more accurately getOrCreateBlockInMask().

Right, I just updated the code to unconditionally create the condition, relying on the caching.

Perhaps wrap the following insert-select-for-non-in-loop-reduction-under-fold-tail along with the above, under adjustRecipesForReductions()? buildVPlanWithVPRecipes() has grown out of propotion.

Done!

9460

I updated the code as suggested, but is the loop exit value always the backedge value? I added a note that the select here is only to model the def-use chain in VPlan (AFAIU)

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9458

Thanks! Rename adjustRecipesForInLoopReductions() to adjustRecipesForReductions()?

Would be good to iterate over all header (reduction) phi's once, checking for inLoop or not. Note that the select handles only non-inLoop reductions, under foldTail. Deserves a separate patch?

9460

is the loop exit value always the backedge value?

It appears so, taken from IVDescriptors.cpp/RecurrenceDescriptor::AddReductionVar():

// The instruction used by an outside user must be the last instruction
// before we feed back to the reduction phi. Otherwise, we loose VF-1
// operations on the value.
if (!is_contained(Phi->operands(), Cur))
  return false;
  
ExitInstruction = Cur;
continue;

Otherwise the generated the select between exit-instruction and phi may be erroneous.
It would be clearer if getLoopExitInstr() would return Phi's operand across the backedge, instead of recording ExitInstruction.

9583

Ah, ILV::fixReduction() actually looks for this select and hooks up to it, under foldTail:

Instruction *LoopExitInst = RdxDesc.getLoopExitInstr();
...
VPValue *LoopExitInstDef = State.Plan->getVPValue(LoopExitInst);
...
if (Cost->foldTailByMasking() && !PhiR->isInLoop()) {
  for (unsigned Part = 0; Part < UF; ++Part) {
    Value *VecLoopExitInst = State.get(LoopExitInstDef, Part);
    Value *Sel = nullptr;
    for (User *U : VecLoopExitInst->users()) {
      if (isa<SelectInst>(U)) {
        assert(!Sel && "Reduction exit feeding two selects");
        Sel = U;
      } else
        assert(isa<PHINode>(U) && "Reduction exit must feed Phi's or select");
    }
    assert(Sel && "Reduction exit feeds no select");
    State.reset(LoopExitInstDef, Sel, Part);
  
    // If the target can create a predicated operator for the reduction at no
    // extra cost in the loop (for example a predicated vadd), it can be
    // cheaper for the select to remain in the loop than be sunk out of it,
    // and so use the select value for the phi instead of the old
    // LoopExitValue.
    if (PreferPredicatedReductionSelect ||
        TTI->preferPredicatedReductionSelect(
            RdxDesc.getOpcode(), PhiTy,
            TargetTransformInfo::ReductionFlags())) {
      auto *VecRdxPhi =
          cast<PHINode>(State.get(PhiR->getVPSingleValue(), Part));
      VecRdxPhi->setIncomingValueForBlock(
          LI->getLoopFor(LoopVectorBody)->getLoopLatch(), Sel);
    }
  }
}

Simply take PhiR->getBackedgeValue() instead there as well?

PreferPredicatedReductionSelect should also hack the phi recipe and be taken care of by VPlan execute? (Here or in a separate patch.)

[fhahn]

Address comments: fix name, use getBackedgeValue at an additional place.

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9458

Thanks! Rename adjustRecipesForInLoopReductions() to adjustRecipesForReductions()?

Ah thanks, I thought I renamed it, but was wrong. should be updated now.

Would be good to iterate over all header (reduction) phi's once, checking for inLoop or not. Note that the select handles only non-inLoop reductions, under foldTail. Deserves a separate patch?

Can update as separate patch to keep the diff cleaner.

9460

Ok great!

9583

Simply take PhiR->getBackedgeValue() instead there as well?

Should be updated there, thanks!

PreferPredicatedReductionSelect should also hack the phi recipe and be taken care of by VPlan execute? (Here or in a separate patch.)

I can do that in a separate one.

[Ayal]

Thanks! This looks good to me, with a minor comment comment.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9582

Update comment? As noted below, fixReduction does rely on the select generated by this recipe, rather than introduce another one.

nit: extra space at the beginning of each line?

llvm/lib/Transforms/Vectorize/LoopVectorizationPlanner.h

VPlanPtr buildVPlanWithVPRecipes(
       VFRange &Range, SmallPtrSetImpl<Instruction *> &DeadInstructions,
       const MapVector<Instruction *, Instruction *> &SinkAfter);
 
   /// Build VPlans for power-of-2 VF's between \p MinVF and \p MaxVF inclusive,
   /// according to the information gathered by Legal when it checked if it is
   /// legal to vectorize the loop. This method creates VPlans using VPRecipes.
   void buildVPlansWithVPRecipes(ElementCount MinVF, ElementCount MaxVF);
 
-  /// Adjust the recipes for any inloop reductions. The chain of instructions
-  /// leading from the loop exit instr to the phi need to be converted to
-  /// reductions, with one operand being vector and the other being the scalar
-  /// reduction chain.
-  void adjustRecipesForInLoopReductions(VPlanPtr &Plan,
-                                        VPRecipeBuilder &RecipeBuilder,
-                                        ElementCount MinVF);
+  // Adjust the recipes for reductions. For in-loop reductions the chain of
+  // instructions leading from the loop exit instr to the phi need to be
+  // converted to reductions, with one operand being vector and the other being
+  // the scalar reduction chain. For other reductions, a select is introduced
+  // between the phi and live-out recipes when folding the tail.
+  void adjustRecipesForReductions(VPBasicBlock *LatchVPBB, VPlanPtr &Plan,
 };
 
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZATIONPLANNER_H

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

void InnerLoopVectorizer::fixReduction(VPReductionPHIRecipe *PhiR,
   assert(Legal->isReductionVariable(OrigPhi) &&
          "Unable to find the reduction variable");
   const RecurrenceDescriptor &RdxDesc = PhiR->getRecurrenceDescriptor();
 
   RecurKind RK = RdxDesc.getRecurrenceKind();
   TrackingVH<Value> ReductionStartValue = RdxDesc.getRecurrenceStartValue();
   Instruction *LoopExitInst = RdxDesc.getLoopExitInstr();
   setDebugLocFromInst(ReductionStartValue);
 
-  VPValue *LoopExitInstDef = State.Plan->getVPValue(LoopExitInst);
+  VPValue *LoopExitInstDef = PhiR->getBackedgeValue();
   // This is the vector-clone of the value that leaves the loop.
   Type *VecTy = State.get(LoopExitInstDef, 0)->getType();
 
   // Wrap flags are in general invalid after vectorization, clear them.
   clearReductionWrapFlags(RdxDesc, State);
 
   // Fix the vector-loop phi.
 
void InnerLoopVectorizer::widenPHIInstruction(Instruction *PN,
 
   assert(PN->getParent() == OrigLoop->getHeader() &&
          "Non-header phis should have been handled elsewhere");
 
   // In order to support recurrences we need to be able to vectorize Phi nodes.
   // Phi nodes have cycles, so we need to vectorize them in two stages. This is
   // stage #1: We create a new vector PHI node with no incoming edges. We'll use
   // this value when we vectorize all of the instructions that use the PHI.
 
   assert(!Legal->isReductionVariable(P) &&
          "reductions should be handled elsewhere");
 
   setDebugLocFromInst(P);
 
   // This PHINode must be an induction variable.
   // Make sure that we know about it.
   assert(Legal->getInductionVars().count(P) && "Not an induction variable");
for (unsigned i = 0; i < IG->getFactor(); ++i)
           Plan->addVPValue(Member, VPIG->getVPValue(J));
           OriginalV->replaceAllUsesWith(VPIG->getVPValue(J));
           J++;
         }
         RecipeBuilder.getRecipe(Member)->eraseFromParent();
       }
   }
 
   // Adjust the recipes for any inloop reductions.
-  adjustRecipesForInLoopReductions(Plan, RecipeBuilder, Range.Start);
-
-  // Finally, if tail is folded by masking, introduce selects between the phi
-  // and the live-out instruction of each reduction, at the end of the latch.
-  if (CM.foldTailByMasking() && !Legal->getReductionVars().empty()) {
-    Builder.setInsertPoint(VPBB);
-    auto *Cond = RecipeBuilder.createBlockInMask(OrigLoop->getHeader(), Plan);
-    for (auto &Reduction : Legal->getReductionVars()) {
-      if (CM.isInLoopReduction(Reduction.first))
-        continue;
-      VPValue *Phi = Plan->getOrAddVPValue(Reduction.first);
-      VPValue *Red = Plan->getOrAddVPValue(Reduction.second.getLoopExitInstr());
-      Builder.createNaryOp(Instruction::Select, {Cond, Red, Phi});
-    }
-  }
+  adjustRecipesForReductions(VPBB, Plan, RecipeBuilder, Range.Start);
 
   VPlanTransforms::sinkScalarOperands(*Plan);
   VPlanTransforms::mergeReplicateRegions(*Plan);
 
   std::string PlanName;
   raw_string_ostream RSO(PlanName);
   ElementCount VF = Range.Start;
   Plan->addVF(VF);
   RSO << "Initial VPlan for VF={" << VF;
   for (VF *= 2; ElementCount::isKnownLT(VF, Range.End); VF *= 2) {
     Plan->addVF(VF);
     RSO << "," << VF;
   }
VPlanPtr LoopVectorizationPlanner::buildVPlan(VFRange &Range) {
 
   SmallPtrSet<Instruction *, 1> DeadInstructions;
   VPlanTransforms::VPInstructionsToVPRecipes(OrigLoop, Plan,
                                              Legal->getInductionVars(),
                                              DeadInstructions, *PSE.getSE());
   return Plan;
 }
 
-// Adjust the recipes for any inloop reductions. The chain of instructions
-// leading from the loop exit instr to the phi need to be converted to
-// reductions, with one operand being vector and the other being the scalar
-// reduction chain.
-void LoopVectorizationPlanner::adjustRecipesForInLoopReductions(
-    VPlanPtr &Plan, VPRecipeBuilder &RecipeBuilder, ElementCount MinVF) {
+// Adjust the recipes for reductions. For in-loop reductions the chain of
+// instructions leading from the loop exit instr to the phi need to be converted
+// to reductions, with one operand being vector and the other being the scalar
+// reduction chain. For other reductions, a select is introduced between the phi
+// and live-out recipes when folding the tail.
+void LoopVectorizationPlanner::adjustRecipesForReductions(
+    VPBasicBlock *LatchVPBB, VPlanPtr &Plan, VPRecipeBuilder &RecipeBuilder,
+    ElementCount MinVF) {
   for (auto &Reduction : CM.getInLoopReductionChains()) {
     PHINode *Phi = Reduction.first;
     RecurrenceDescriptor &RdxDesc = Legal->getReductionVars()[Phi];
     const SmallVector<Instruction *, 4> &ReductionOperations = Reduction.second;
 
     if (MinVF.isScalar() && !CM.useOrderedReductions(RdxDesc))
       continue;
 
     // ReductionOperations are orders top-down from the phi's use to the
     // LoopExitValue. We keep a track of the previous item (the Chain) to tell
for (Instruction *R : ReductionOperations) {
                "Expected to replace a VPWidenSC");
         assert(cast<VPWidenRecipe>(CompareRecipe)->getNumUsers() == 0 &&
                "Expected no remaining users");
         CompareRecipe->eraseFromParent();
       }
       Chain = R;
     }
   }
+
+  // If tail is folded by masking, introduce selects between the phi
+  //  and the live-out instruction of each reduction, at the end of the latch.
+  //  Note that this is currently only used to reflect the def-use chains in
+  //  VPlan. fixReduction will introduce the appropriate selects and update the
+  //  users outside the loop without relying on the select recipe.
+  if (CM.foldTailByMasking()) {
+    for (VPRecipeBase &R : Plan->getEntry()->getEntryBasicBlock()->phis()) {
+      VPReductionPHIRecipe *PhiR = dyn_cast<VPReductionPHIRecipe>(&R);
+      if (!PhiR || PhiR->isInLoop())
+        continue;
+      Builder.setInsertPoint(LatchVPBB);
+      VPValue *Cond =
+          RecipeBuilder.createBlockInMask(OrigLoop->getHeader(), Plan);
+      VPValue *Red = PhiR->getBackedgeValue();
+      Builder.createNaryOp(Instruction::Select, {Cond, Red, PhiR});
+    }
+  }
 }
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
 void VPInterleaveRecipe::print(raw_ostream &O, const Twine &Indent,
                                VPSlotTracker &SlotTracker) const {
   O << Indent << "INTERLEAVE-GROUP with factor " << IG->getFactor() << " at ";
   IG->getInsertPos()->printAsOperand(O, false);
   O << ", ";