[LV] Remove dead IV casts using VPlan (NFC).

[fhahn]

Summary

This patch simplifies handling of dead induction casts, by removing dead
cast instructions after initial VPlan construction. This has the
following benefits:

1. fixes a crash (see @test_optimized_cast_induction_feeding_first_order_recurrence)
2. Simplifies VPWidenIntOrFpInduction to a single-def recipes
3. Retires recordVectorLoopValueForInductionCast.

[Ayal]

Marvelous!
Worth adding in the summary that all redundant casts will now first be represented in VPlan using recipes, instead of being treated as DeadInstructions and rejected out of hand.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

661

Worth retaining some of this explanation, somewhere?

9087

dead >> redundant?

9104

Would be good to ensure that all members of Casts get processed.
How about recording the recipes of Casts upfront, and traverse Casts here retrieving their recipes directly and RAUW them with IV?

Note that this Redundant Cast Elimination can-be/is done before sinkAfter, because such casts can feed only themselves, so they cannot feed candidates that want to sinkAfter them. However, perhaps better to swap them, given that sinkAfter is mandatory whereas RCE is an optimization - presumably code is functionally correct (yet suboptimal) w/o it? Worth outlining to reduce the size of buildVPlanWithVPRecipes() which is already excessive?

9112

Now that the redundant casts became dead - useless, they can be cleaned up with a general VPlan DCE, which may become useful in additional cases. This local self-clean-up is also fine of-course.

[fhahn]

Move transform to VPlanTransforms.cpp, run after sink-after, retain essence of comment.

[fhahn]

remove stray newline

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

661

I tried to capture the essence (the bit about why the casts are redundant) in the doc-comment for removeRedundantInductionCasts.

9104

Would be good to ensure that all members of Casts get processed.

I added an assert that we add exactly Casts.size() elements to remove.

How about recording the recipes of Casts upfront, and traverse Casts here retrieving their recipes directly and RAUW them with IV?

I moved it to VPlanTransforms, but retained the logic to discover the casts be traversing IV users. I am not sure if it is worth relying on the extra state in this case, we can get all the information directly from the plan without too much effort. We only need to look through instructions in Casts, so it should be a very small amount of extra work. WDYT?

9112

There's no VPlan DCE yet unfortunately, so I kept it for now. But that's certainly something to follow up on.

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

9104

I moved it to VPlanTransforms, but retained the logic to discover the casts be traversing IV users. I am not sure if it is worth relying on the extra state in this case, we can get all the information directly from the plan without too much effort. We only need to look through instructions in Casts, so it should be a very small amount of extra work. WDYT?

Doing

for (auto &Cast : Casts)
  RecipeBuilder.getRecipe(Cast)->getVPSingleValue()->replaceAllUsesWith(IV);

does seem (more) straightforward, albeit dependent on recording Casts in RecipeBuilder, and does not convey nor check that Casts are chained from IV.
Amount of extra work is indeed expected to be small, and can be slightly decreased - see below. Furthermore, perhaps at some point this could become a truly VPlan-to-VPlan transformation, which also identifies the redundancy of such casts independently, instead of relying on initial external identification. Ship it!

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

308

Used only in assert, needs #ifndef?

313

(This cannot loop forever because Casts excludes the header phi chaining Casts into a cycle.)

There typically will be a few Casts if any, but it does seem somewhat wasteful to go through all users of all Casts. Perhaps loop until the last Cast is reached, saving the redundant traversal over its users? (And reducing the risk of infinite loop if something went wrong?)
Can also repeatedly search for a single next cast among the users of the current CastDef, stopping as soon as one is found, instead of always appending all users for traversal.

[fhahn]

Adjust loop to exit once all casts have been seen.

Note that the patch depends on D115111 which adds InductionDecriptor to VPWidenIntOrFpInductionRecipe.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

313

I adjusted the loop to keep track of the number of casts already removed in the loop and only iterate until NumDeadCasts == Casts.size(). That should ensure that we bail out as soon as all casts have been visited, without adding the need for an extra bailout.

It also removes the need for the assertion below I think, because this is now guaranteed by the loop directly. WDYT?

[Ayal]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8060

Wonder if PrimaryInduction can have redundant casts; and if so, do they get removed now and/or with this patch?

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

305

If IV has a TruncInst all of its Casts are to be retained?

308

"in Cast[s]"

313

This is fine, thanks!

Nits:
"while" >> "for", even if the bump is left inside?
In general better pre-compute Casts.size(), but loop is expected to be very short.
Another way of doing this, anticipating/enforcing a chain of casts:

VPRecipeBase *FindMyCast = IV;
for (unsigned NumCastsToRemove =  Casts.size(); NumCastsToRemove > 0; NumCastsToRemove--) {
  VPRecipeBase *FoundUserCast = nullptr;
  for (auto &UserCast : FindMyCast->Users)
    if (UserCast.getNumDefinedValues() == 1 &&
        is_contained(Casts, UserCast.getVPSingleValue()->getUnderlyingValue())) {
      FoundUserCast = &UserCast
      break;
    }
  assert(FoundUserCast && "Missing a cast to remove");
  FoundUserCast->getVPSingleValue()->replaceAllUsesWith(IV);
  DeadCasts.push_back(FoundUserCast);
  FindMyCast = FoundUserCast;
}

[fhahn]

Adjust code as suggested, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

8060

I tried to construct such a test case, but I don't think that's possible at the moment. We require the trip-count to be computable to start with, but when the primary induction variable has casts, I don't think that would be the case. At least I couldn't construct a test. In any case, I think it would probably crash with the code currently in tree and would be handled correctly with the patch.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

305

For now, the TruncInst handling is completely separate tat the moment; If the Trunc has not been removed as dead, we will create a new (optimized) VPWidenIntOrFpInductionRecipe for the TruncInst, so there is nothing to remove here.

313

Thanks, I updated the code. With that style, we cannot RAUW in the loop, because this will nuke the users of FoundUserCast. I slightly adjusted the code so that DeadCasts also RAUW. Note that this required to adjust main loop a bit, now using the number of phi recipes. The phis() range relies in the first-non-phi iterator, which may be invalidated by removing recipes.

There's also no need to use is_contained. The instructions in Casts are in reverse visitation order and we can use that.

[Ayal]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

313

There's also no need to use is_contained. The instructions in Casts are in reverse visitation order and we can use that.

In this case, how about iterating over Casts in reverse order, searching for the recipe of each Cast (instead of recording and retrieving it directly as raised earlier).

If DeadCasts ("CastsToRemove"?) accumulates all candidate recipes and these are removed in a separate loop at the end, the main loop can more simply iterate over phis. The RAUW loop can loop over the last Casts.size() entries of DeadCasts (in reverse? ;-), or a separate CastsToRAUW can be used which can fill CastsToRemove; or a <Recipe, IV> map can be used to also delay RAUW to the end.

321

Nit: the following reverse order more clearly coveys that checking a single defined value guards getVPSingleValue:

if (UserCast->getNumDefinedValues() == 1 &&
    UserCast->getVPSingleValue()->getUnderlyingValue()) ==
        Casts[NumCastsToRemove - 1])

[fhahn]

Updated to use SmallVector<std::pair<VPRecipeBase *, VPValue *>> CastsToRemove to keep phi iteration simpler.

[fhahn]

Changed to iterate over Casts vector instead of count the number of casts.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

313

I updated the code to iterate over the Casts vector instead of counting the casts we removed.

I also CastsToRemove to use SmallVector<std::pair<VPRecipeBase *, VPValue *>> and got back to the simpler iterating over phis.

321

Thanks, reordered conditions.

[Ayal]

This looks good to me, thanks!

[Ayal]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

305

It seems a bit more logical then to have "if (!IV || IV->getTruncInst()) continue", thereby indicating which recipes are (ir)relevant for this transformation.

If an IV with a TruncInst can have Casts, are their recipes removed/not-generated elsewhere? Otherwise, can we assert that there's no TruncInst after we checked that there are Casts?

[fhahn]

Adjust checks as suggested.

[fhahn]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

305

Thanks, the latest version indeed doesn't really need to check the size of Casts any more, because it directly iterates over them, so there's nothing extra to do it empty. Adjusted!

[Ayal]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

305

there's nothing extra to do it empty. Adjusted!

Good!

If the Trunc has not been removed as dead, we will create a new (optimized) VPWidenIntOrFpInductionRecipe for the TruncInst, so there is nothing to remove here.

ok, agreed. Would be good to add a line explaining why we must bail-out when IV has a Trunc. An IV phi feeding one or more Truncs will have multiple VPWidenIntOrFpInductionRecipes associated with it; its redundant casts however need to be removed exactly once - e.g., when reaching the recipe associated directly with it, having no Trunc, as done here.
(pr35773.ll demonstrates this by failing due to missing the casts to remove, if this bail-out is removed.)

Perhaps this Trunc-of-an-IV optimization should also be done as a VPlan-to-VPlan transformation, placed after Redundant Casts Elimination (which originated in D38948). It goes back to e266efb70bfdd which moved truncation of a vectorized IV to operate on the scalar IV.

325

Note that this order of traversal, going forward from the phi, is the more efficient one for RAUW'ing.
Going backwards towards the phi, following the original order of Casts, would result in repeated RAUW's.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

void scalarizeInstruction(Instruction *Instr, VPReplicateRecipe *RepRecipe,
                             const VPIteration &Instance, bool IfPredicateInstr,
                             VPTransformState &State);
 
   /// Widen an integer or floating-point induction variable \p IV. If \p Trunc
   /// is provided, the integer induction variable will first be truncated to
   /// the corresponding type.
   void widenIntOrFpInduction(PHINode *IV, const InductionDescriptor &ID,
                              Value *Start, TruncInst *Trunc, VPValue *Def,
-                             VPValue *CastDef, VPTransformState &State);
+                             VPTransformState &State);
 
   /// Construct the vector value of a scalarized value \p V one lane at a time.
   void packScalarIntoVectorValue(VPValue *Def, const VPIteration &Instance,
                                  VPTransformState &State);
 
   /// Try to vectorize interleaved access group \p Group with the base address
   /// given in \p Addr, optionally masking the vector operations if \p
   /// BlockInMask is non-null. Use \p State to translate given VPValues to IR
protected:
 
   /// Compute scalar induction steps. \p ScalarIV is the scalar induction
   /// variable on which to base the steps, \p Step is the size of the step, and
   /// \p EntryVal is the value from the original loop that maps to the steps.
   /// Note that \p EntryVal doesn't have to be an induction variable - it
   /// can also be a truncate instruction.
   void buildScalarSteps(Value *ScalarIV, Value *Step, Instruction *EntryVal,
                         const InductionDescriptor &ID, VPValue *Def,
-                        VPValue *CastDef, VPTransformState &State);
+                        VPTransformState &State);
 
   /// Create a vector induction phi node based on an existing scalar one. \p
   /// EntryVal is the value from the original loop that maps to the vector phi
   /// node, and \p Step is the loop-invariant step. If \p EntryVal is a
   /// truncate instruction, instead of widening the original IV, we widen a
   /// version of the IV truncated to \p EntryVal's type.
   void createVectorIntOrFpInductionPHI(const InductionDescriptor &II,
                                        Value *Step, Value *Start,
                                        Instruction *EntryVal, VPValue *Def,
-                                       VPValue *CastDef,
                                        VPTransformState &State);
 
   /// Returns true if an instruction \p I should be scalarized instead of
   /// vectorized for the chosen vectorization factor.
   bool shouldScalarizeInstruction(Instruction *I) const;
 
   /// Returns true if we should generate a scalar version of \p IV.
   bool needsScalarInduction(Instruction *IV) const;
 
-  /// If there is a cast involved in the induction variable \p ID, which should
-  /// be ignored in the vectorized loop body, this function records the
-  /// VectorLoopValue of the respective Phi also as the VectorLoopValue of the
-  /// cast. We had already proved that the casted Phi is equal to the uncasted
-  /// Phi in the vectorized loop (under a runtime guard), and therefore
-  /// there is no need to vectorize the cast - the same value can be used in the
-  /// vector loop for both the Phi and the cast.
-  /// If \p VectorLoopValue is a scalarized value, \p Lane is also specified,
-  /// Otherwise, \p VectorLoopValue is a widened/vectorized value.
-  ///
-  /// \p EntryVal is the value from the original loop that maps to the vector
-  /// phi node and is used to distinguish what is the IV currently being
-  /// processed - original one (if \p EntryVal is a phi corresponding to the
-  /// original IV) or the "newly-created" one based on the proof mentioned above
-  /// (see also buildScalarSteps() and createVectorIntOrFPInductionPHI()). In the
-  /// latter case \p EntryVal is a TruncInst and we must not record anything for
-  /// that IV, but it's error-prone to expect callers of this routine to care
-  /// about that, hence this explicit parameter.
-  void recordVectorLoopValueForInductionCast(
-      const InductionDescriptor &ID, const Instruction *EntryVal,
-      Value *VectorLoopValue, VPValue *CastDef, VPTransformState &State,
-      unsigned Part, unsigned Lane = UINT_MAX);
-
   /// Generate a shuffle sequence that will reverse the vector Vec.
   virtual Value *reverseVector(Value *Vec);
 
   /// Returns (and creates if needed) the original loop trip count.
   Value *getOrCreateTripCount(Loop *NewLoop);
 
   /// Returns (and creates if needed) the trip count of the widened loop.
   Value *getOrCreateVectorTripCount(Loop *NewLoop);
Value *InnerLoopVectorizer::getBroadcastInstrs(Value *V) {
   // Broadcast the scalar into all locations in the vector.
   Value *Shuf = Builder.CreateVectorSplat(VF, V, "broadcast");
 
   return Shuf;
 }
 
 void InnerLoopVectorizer::createVectorIntOrFpInductionPHI(
     const InductionDescriptor &II, Value *Step, Value *Start,
-    Instruction *EntryVal, VPValue *Def, VPValue *CastDef,
-    VPTransformState &State) {
+    Instruction *EntryVal, VPValue *Def, VPTransformState &State) {
   assert((isa<PHINode>(EntryVal) || isa<TruncInst>(EntryVal)) &&
          "Expected either an induction phi-node or a truncate of it!");
 
   // Construct the initial value of the vector IV in the vector loop preheader
   auto CurrIP = Builder.saveIP();
   Builder.SetInsertPoint(LoopVectorPreHeader->getTerminator());
   if (isa<TruncInst>(EntryVal)) {
     assert(Start->getType()->isIntegerTy() &&
PHINode *VecInd = PHINode::Create(SteppedStart->getType(), 2, "vec.ind",
                                     &*LoopVectorBody->getFirstInsertionPt());
   VecInd->setDebugLoc(EntryVal->getDebugLoc());
   Instruction *LastInduction = VecInd;
   for (unsigned Part = 0; Part < UF; ++Part) {
     State.set(Def, LastInduction, Part);
 
     if (isa<TruncInst>(EntryVal))
       addMetadata(LastInduction, EntryVal);
-    recordVectorLoopValueForInductionCast(II, EntryVal, LastInduction, CastDef,
-                                          State, Part);
 
     LastInduction = cast<Instruction>(
         Builder.CreateBinOp(AddOp, LastInduction, SplatVF, "step.add"));
     LastInduction->setDebugLoc(EntryVal->getDebugLoc());
   }
 
   // Move the last step to the end of the latch block. This ensures consistent
   // placement of all induction updates.
if (shouldScalarizeInstruction(IV))
     return true;
   auto isScalarInst = [&](User *U) -> bool {
     auto *I = cast<Instruction>(U);
     return (OrigLoop->contains(I) && shouldScalarizeInstruction(I));
   };
   return llvm::any_of(IV->users(), isScalarInst);
 }
 
-void InnerLoopVectorizer::recordVectorLoopValueForInductionCast(
-    const InductionDescriptor &ID, const Instruction *EntryVal,
-    Value *VectorLoopVal, VPValue *CastDef, VPTransformState &State,
-    unsigned Part, unsigned Lane) {
-  assert((isa<PHINode>(EntryVal) || isa<TruncInst>(EntryVal)) &&
-         "Expected either an induction phi-node or a truncate of it!");
-
-  // This induction variable is not the phi from the original loop but the
-  // newly-created IV based on the proof that casted Phi is equal to the
-  // uncasted Phi in the vectorized loop (under a runtime guard possibly). It
-  // re-uses the same InductionDescriptor that original IV uses but we don't
-  // have to do any recording in this case - that is done when original IV is
-  // processed.
-  if (isa<TruncInst>(EntryVal))
-    return;
-
-  if (!CastDef) {
-    assert(ID.getCastInsts().empty() &&
-           "there are casts for ID, but no CastDef");
-    return;
-  }
-  assert(!ID.getCastInsts().empty() &&
-         "there is a CastDef, but no casts for ID");
-  // Only the first Cast instruction in the Casts vector is of interest.
-  // The rest of the Casts (if exist) have no uses outside the
-  // induction update chain itself.
-  if (Lane < UINT_MAX)
-    State.set(CastDef, VectorLoopVal, VPIteration(Part, Lane));
-  else
-    State.set(CastDef, VectorLoopVal, Part);
-}
-
 void InnerLoopVectorizer::widenIntOrFpInduction(PHINode *IV,
                                                 const InductionDescriptor &ID,
                                                 Value *Start, TruncInst *Trunc,
-                                                VPValue *Def, VPValue *CastDef,
+                                                VPValue *Def,
                                                 VPTransformState &State) {
   assert((IV->getType()->isIntegerTy() || IV != OldInduction) &&
          "Primary induction variable must have an integer type");
   assert(IV->getType() == ID.getStartValue()->getType() && "Types must match");
 
   // The value from the original loop to which we are mapping the new induction
   // variable.
   Instruction *EntryVal = Trunc ? cast<Instruction>(Trunc) : IV;
for (unsigned Part = 0; Part < UF; ++Part) {
       else
         StartIdx = getRuntimeVF(Builder, Step->getType(), VF * Part);
 
       Value *EntryPart =
           getStepVector(Broadcasted, StartIdx, Step, ID.getInductionOpcode());
       State.set(Def, EntryPart, Part);
       if (Trunc)
         addMetadata(EntryPart, Trunc);
-      recordVectorLoopValueForInductionCast(ID, EntryVal, EntryPart, CastDef,
-                                            State, Part);
     }
   };
 
   // Fast-math-flags propagate from the original induction instruction.
   IRBuilder<>::FastMathFlagGuard FMFG(Builder);
   if (ID.getInductionBinOp() && isa<FPMathOperator>(ID.getInductionBinOp()))
     Builder.setFastMathFlags(ID.getInductionBinOp()->getFastMathFlags());
 
   // Now do the actual transformations, and start with creating the step value.
   Value *Step = CreateStepValue(ID.getStep());
   if (VF.isZero() || VF.isScalar()) {
     Value *ScalarIV = CreateScalarIV(Step);
     CreateSplatIV(ScalarIV, Step);
     return;
   }
 
   // Determine if we want a scalar version of the induction variable. This is
   // true if the induction variable itself is not widened, or if it has at
   // least one user in the loop that is not widened.
   auto NeedsScalarIV = needsScalarInduction(EntryVal);
   if (!NeedsScalarIV) {
-    createVectorIntOrFpInductionPHI(ID, Step, Start, EntryVal, Def, CastDef,
-                                    State);
+    createVectorIntOrFpInductionPHI(ID, Step, Start, EntryVal, Def, State);
     return;
   }
 
   // Try to create a new independent vector induction variable. If we can't
   // create the phi node, we will splat the scalar induction variable in each
   // loop iteration.
   if (!shouldScalarizeInstruction(EntryVal)) {
-    createVectorIntOrFpInductionPHI(ID, Step, Start, EntryVal, Def, CastDef,
-                                    State);
+    createVectorIntOrFpInductionPHI(ID, Step, Start, EntryVal, Def, State);
     Value *ScalarIV = CreateScalarIV(Step);
     // Create scalar steps that can be used by instructions we will later
     // scalarize. Note that the addition of the scalar steps will not increase
     // the number of instructions in the loop in the common case prior to
     // InstCombine. We will be trading one vector extract for each scalar step.
-    buildScalarSteps(ScalarIV, Step, EntryVal, ID, Def, CastDef, State);
+    buildScalarSteps(ScalarIV, Step, EntryVal, ID, Def, State);
     return;
   }
 
   // All IV users are scalar instructions, so only emit a scalar IV, not a
   // vectorised IV. Except when we tail-fold, then the splat IV feeds the
   // predicate used by the masked loads/stores.
   Value *ScalarIV = CreateScalarIV(Step);
   if (!Cost->isScalarEpilogueAllowed())
     CreateSplatIV(ScalarIV, Step);
-  buildScalarSteps(ScalarIV, Step, EntryVal, ID, Def, CastDef, State);
+  buildScalarSteps(ScalarIV, Step, EntryVal, ID, Def, State);
 }
 
 Value *InnerLoopVectorizer::getStepVector(Value *Val, Value *StartIdx,
                                           Value *Step,
                                           Instruction::BinaryOps BinOp) {
   // Create and check the types.
   auto *ValVTy = cast<VectorType>(Val->getType());
   ElementCount VLen = ValVTy->getElementCount();
Value *InnerLoopVectorizer::getStepVector(Value *Val, Value *StartIdx,
   Step = Builder.CreateVectorSplat(VLen, Step);
   Value *MulOp = Builder.CreateFMul(InitVec, Step);
   return Builder.CreateBinOp(BinOp, Val, MulOp, "induction");
 }
 
 void InnerLoopVectorizer::buildScalarSteps(Value *ScalarIV, Value *Step,
                                            Instruction *EntryVal,
                                            const InductionDescriptor &ID,
-                                           VPValue *Def, VPValue *CastDef,
+                                           VPValue *Def,
                                            VPTransformState &State) {
   // We shouldn't have to build scalar steps if we aren't vectorizing.
   assert(VF.isVector() && "VF should be greater than one");
   // Get the value type and ensure it and the step have the same integer type.
   Type *ScalarIVTy = ScalarIV->getType()->getScalarType();
   assert(ScalarIVTy == Step->getType() &&
          "Val and Step should have the same type");
 
for (unsigned Part = 0; Part < UF; ++Part) {
     if (!IsUniform && VF.isScalable()) {
       auto *SplatStartIdx = Builder.CreateVectorSplat(VF, StartIdx0);
       auto *InitVec = Builder.CreateAdd(SplatStartIdx, UnitStepVec);
       if (ScalarIVTy->isFloatingPointTy())
         InitVec = Builder.CreateSIToFP(InitVec, VecIVTy);
       auto *Mul = Builder.CreateBinOp(MulOp, InitVec, SplatStep);
       auto *Add = Builder.CreateBinOp(AddOp, SplatIV, Mul);
       State.set(Def, Add, Part);
-      recordVectorLoopValueForInductionCast(ID, EntryVal, Add, CastDef, State,
-                                            Part);
       // It's useful to record the lane values too for the known minimum number
       // of elements so we do those below. This improves the code quality when
       // trying to extract the first element, for example.
     }
 
     if (ScalarIVTy->isFloatingPointTy())
       StartIdx0 = Builder.CreateSIToFP(StartIdx0, ScalarIVTy);
 
     for (unsigned Lane = 0; Lane < Lanes; ++Lane) {
       Value *StartIdx = Builder.CreateBinOp(
           AddOp, StartIdx0, getSignedIntOrFpConstant(ScalarIVTy, Lane));
       // The step returned by `createStepForVF` is a runtime-evaluated value
       // when VF is scalable. Otherwise, it should be folded into a Constant.
       assert((VF.isScalable() || isa<Constant>(StartIdx)) &&
              "Expected StartIdx to be folded to a constant when VF is not "
              "scalable");
       auto *Mul = Builder.CreateBinOp(MulOp, StartIdx, Step);
       auto *Add = Builder.CreateBinOp(AddOp, ScalarIV, Mul);
       State.set(Def, Add, VPIteration(Part, Lane));
-      recordVectorLoopValueForInductionCast(ID, EntryVal, Add, CastDef, State,
-                                            Part, Lane);
     }
   }
 }
 
 void InnerLoopVectorizer::packScalarIntoVectorValue(VPValue *Def,
                                                     const VPIteration &Instance,
                                                     VPTransformState &State) {
   Value *ScalarInst = State.get(Def, Instance);
void LoopVectorizationPlanner::collectTriviallyDeadInstructions(
   auto *Latch = OrigLoop->getLoopLatch();
   for (auto &Induction : Legal->getInductionVars()) {
     PHINode *Ind = Induction.first;
     auto *IndUpdate = cast<Instruction>(Ind->getIncomingValueForBlock(Latch));
 
     // If the tail is to be folded by masking, the primary induction variable,
     // if exists, isn't dead: it will be used for masking. Don't kill it.
     if (CM.foldTailByMasking() && IndUpdate == Legal->getPrimaryInduction())
       continue;
 
     if (llvm::all_of(IndUpdate->users(), [&](User *U) -> bool {
           return U == Ind || DeadInstructions.count(cast<Instruction>(U));
         }))
       DeadInstructions.insert(IndUpdate);
-
-    // We record as "Dead" also the type-casting instructions we had identified
-    // during induction analysis. We don't need any handling for them in the
-    // vectorized loop because we have proven that, under a proper runtime
-    // test guarding the vectorized loop, the value of the phi, and the casted
-    // value of the phi, are the same. The last instruction in this casting chain
-    // will get its scalar/vector/widened def from the scalar/vector/widened def
-    // of the respective phi node. Any other casts in the induction def-use chain
-    // have no other uses outside the phi update chain, and will be ignored.
-    const InductionDescriptor &IndDes = Induction.second;
-    const SmallVectorImpl<Instruction *> &Casts = IndDes.getCastInsts();
-    DeadInstructions.insert(Casts.begin(), Casts.end());
   }
 }
 
 Value *InnerLoopUnroller::reverseVector(Value *Vec) { return Vec; }
 
 Value *InnerLoopUnroller::getBroadcastInstrs(Value *V) { return V; }
 
 Value *InnerLoopUnroller::getStepVector(Value *Val, Value *StartIdx,

 VPWidenIntOrFpInductionRecipe *
 VPRecipeBuilder::tryToOptimizeInductionPHI(PHINode *Phi,
                                            ArrayRef<VPValue *> Operands) const {
   // Check if this is an integer or fp induction. If so, build the recipe that
   // produces its scalar and vector values.
   if (auto *II = Legal->getIntOrFpInductionDescriptor(Phi)) {
     assert(II->getStartValue() ==
            Phi->getIncomingValueForBlock(OrigLoop->getLoopPreheader()));
-    const SmallVectorImpl<Instruction *> &Casts = II->getCastInsts();
-    return new VPWidenIntOrFpInductionRecipe(
-        Phi, Operands[0], *II, Casts.empty() ? nullptr : Casts.front());
+    return new VPWidenIntOrFpInductionRecipe(Phi, Operands[0], *II);
   }
 
   return nullptr;
 }
 
 VPWidenIntOrFpInductionRecipe *VPRecipeBuilder::tryToOptimizeInductionTruncate(
     TruncInst *I, ArrayRef<VPValue *> Operands, VFRange &Range,
     VPlan &Plan) const {
VPlanPtr LoopVectorizationPlanner::buildVPlanWithVPRecipes(
   }
 
   assert(isa<VPRegionBlock>(Plan->getEntry()) &&
          !Plan->getEntry()->getEntryBasicBlock()->empty() &&
          "entry block must be set to a VPRegionBlock having a non-empty entry "
          "VPBasicBlock");
   RecipeBuilder.fixHeaderPhis();
 
   // ---------------------------------------------------------------------------
   // Transform initial VPlan: Apply previously taken decisions, in order, to
   // bring the VPlan to its final state.
   // ---------------------------------------------------------------------------
 
   // Apply Sink-After legal constraints.
   auto GetReplicateRegion = [](VPRecipeBase *R) -> VPRegionBlock * {
     auto *Region = dyn_cast_or_null<VPRegionBlock>(R->getParent()->getParent());
     if (Region && Region->isReplicator()) {
       assert(Region->getNumSuccessors() == 1 &&
              Region->getNumPredecessors() == 1 && "Expected SESE region!");
       assert(R->getParent()->size() == 1 &&
              "A recipe in an original replicator region must be the only "
              "recipe in its block");
       return Region;
     }
     return nullptr;
   };
   for (auto &Entry : SinkAfter) {
     VPRecipeBase *Sink = RecipeBuilder.getRecipe(Entry.first);
     VPRecipeBase *Target = RecipeBuilder.getRecipe(Entry.second);
 
     auto *TargetRegion = GetReplicateRegion(Target);
     auto *SinkRegion = GetReplicateRegion(Sink);
     if (!SinkRegion) {
       // If the sink source is not a replicate region, sink the recipe directly.
       if (TargetRegion) {
         // The target is in a replication region, make sure to move Sink to
         // the block after it, not into the replication region itself.
         VPBasicBlock *NextBlock =
             cast<VPBasicBlock>(TargetRegion->getSuccessors().front());
         Sink->moveBefore(*NextBlock, NextBlock->getFirstNonPhi());
       } else
         Sink->moveAfter(Target);
if (TargetRegion) {
       VPBlockUtils::connectBlocks(SinkRegion, SplitBlock);
       if (VPBB == SplitPred)
         VPBB = SplitBlock;
     }
   }
 
   cast<VPRegionBlock>(Plan->getEntry())->setExit(VPBB);
 
+  VPlanTransforms::removeRedundantInductionCasts(*Plan);
+
   // Now that sink-after is done, move induction recipes for optimized truncates
   // to the phi section of the header block.
   for (VPWidenIntOrFpInductionRecipe *Ind : InductionsToMove)
     Ind->moveBefore(*HeaderVPBB, HeaderVPBB->getFirstNonPhi());
 
   // Adjust the recipes for any inloop reductions.
   adjustRecipesForReductions(VPBB, Plan, RecipeBuilder, Range.Start);
 
for (unsigned Part = 0; Part < State.UF; ++Part) {
       State.set(this, NewGEP, Part);
       State.ILV->addMetadata(NewGEP, GEP);
     }
   }
 }
 
 void VPWidenIntOrFpInductionRecipe::execute(VPTransformState &State) {
   assert(!State.Instance && "Int or FP induction being replicated.");
-  State.ILV->widenIntOrFpInduction(
-      IV, getInductionDescriptor(), getStartValue()->getLiveInIRValue(),
-      getTruncInst(), getVPValue(0), getCastValue(), State);
+  State.ILV->widenIntOrFpInduction(IV, getInductionDescriptor(),
+                                   getStartValue()->getLiveInIRValue(),
+                                   getTruncInst(), getVPValue(0), State);
 }
 
 void VPWidenPHIRecipe::execute(VPTransformState &State) {
   State.ILV->widenPHIInstruction(cast<PHINode>(getUnderlyingValue()), this,
                                  State);
 }
 
 void VPBlendRecipe::execute(VPTransformState &State) {

llvm/lib/Transforms/Vectorize/VPlan.h

#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 #endif
 };
 
 /// A recipe for handling phi nodes of integer and floating-point inductions,
 /// producing their vector and scalar values.
-class VPWidenIntOrFpInductionRecipe : public VPRecipeBase {
+class VPWidenIntOrFpInductionRecipe : public VPRecipeBase, public VPValue {
   PHINode *IV;
   const InductionDescriptor &IndDesc;
 
 public:
   VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start,
-                                const InductionDescriptor &IndDesc,
-                                Instruction *Cast = nullptr)
-      : VPRecipeBase(VPWidenIntOrFpInductionSC, {Start}), IV(IV),
-        IndDesc(IndDesc) {
-    new VPValue(IV, this);
-
-    if (Cast)
-      new VPValue(Cast, this);
-  }
+                                const InductionDescriptor &IndDesc)
+      : VPRecipeBase(VPWidenIntOrFpInductionSC, {Start}), VPValue(IV, this),
+        IV(IV), IndDesc(IndDesc) {}
 
   VPWidenIntOrFpInductionRecipe(PHINode *IV, VPValue *Start,
                                 const InductionDescriptor &IndDesc,
                                 TruncInst *Trunc)
-      : VPRecipeBase(VPWidenIntOrFpInductionSC, {Start}), IV(IV),
-        IndDesc(IndDesc) {
-    new VPValue(Trunc, this);
-  }
+      : VPRecipeBase(VPWidenIntOrFpInductionSC, {Start}), VPValue(Trunc, this),
+        IV(IV), IndDesc(IndDesc) {}
 
   ~VPWidenIntOrFpInductionRecipe() override = default;
 
   /// Method to support type inquiry through isa, cast, and dyn_cast.
   static inline bool classof(const VPDef *D) {
     return D->getVPDefID() == VPRecipeBase::VPWidenIntOrFpInductionSC;
   }
 
   /// Generate the vectorized and scalarized versions of the phi node as
   /// needed by their users.
   void execute(VPTransformState &State) override;
 
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print the recipe.
   void print(raw_ostream &O, const Twine &Indent,
              VPSlotTracker &SlotTracker) const override;
 #endif
 
   /// Returns the start value of the induction.
   VPValue *getStartValue() { return getOperand(0); }
 
-  /// Returns the cast VPValue, if one is attached, or nullptr otherwise.
-  VPValue *getCastValue() {
-    if (getNumDefinedValues() != 2)
-      return nullptr;
-    return getVPValue(1);
-  }
-
   /// Returns the first defined value as TruncInst, if it is one or nullptr
   /// otherwise.
   TruncInst *getTruncInst() {
     return dyn_cast_or_null<TruncInst>(getVPValue(0)->getUnderlyingValue());
   }
   const TruncInst *getTruncInst() const {
     return dyn_cast_or_null<TruncInst>(getVPValue(0)->getUnderlyingValue());
   }

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

VPInstructionsToVPRecipes(Loop *OrigLoop, VPlanPtr &Plan,
                             function_ref<const InductionDescriptor *(PHINode *)>
                                 GetIntOrFpInductionDescriptor,
                             SmallPtrSetImpl<Instruction *> &DeadInstructions,
                             ScalarEvolution &SE);
 
   static bool sinkScalarOperands(VPlan &Plan);
 
   static bool mergeReplicateRegions(VPlan &Plan);
+
+  /// Remove redundant casts of inductions.
+  ///
+  /// Such redundant casts are casts of induction variables that can be ignored,
+  /// because we already proved that the casted phi is equal to the uncasted phi
+  /// in the vectorized loop. There is no need to vectorize the cast - the same
+  /// value can be used for both the phi and casts in the vector loop.
+  static void removeRedundantInductionCasts(VPlan &Plan);
 };
 
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLANTRANSFORMS_H

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

for (VPRegionBlock *Region1 : CandidateRegions) {
     VPBlockUtils::disconnectBlocks(Region1, MiddleBasicBlock);
     DeletedRegions.insert(Region1);
   }
 
   for (VPRegionBlock *ToDelete : DeletedRegions)
     delete ToDelete;
   return Changed;
 }
+
+void VPlanTransforms::removeRedundantInductionCasts(VPlan &Plan) {
+  SmallVector<std::pair<VPRecipeBase *, VPValue *>> CastsToRemove;
+  for (auto &Phi : Plan.getEntry()->getEntryBasicBlock()->phis()) {
+    auto *IV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi);
+    if (!IV || IV->getTruncInst())
+      continue;
+
+    // Visit all casts connected to IV and in Casts. Collect them.
+    // remember them for removal.
+    auto &Casts = IV->getInductionDescriptor().getCastInsts();
+    VPValue *FindMyCast = IV;
+    for (Instruction *IRCast : reverse(Casts)) {
+      VPRecipeBase *FoundUserCast = nullptr;
+      for (auto *U : FindMyCast->users()) {
+        auto *UserCast = cast<VPRecipeBase>(U);
+        if (UserCast->getNumDefinedValues() == 1 &&
+            UserCast->getVPSingleValue()->getUnderlyingValue() == IRCast) {
+          FoundUserCast = UserCast;
+          break;
+        }
+      }
+      assert(FoundUserCast && "Missing a cast to remove");
+      CastsToRemove.emplace_back(FoundUserCast, IV);
+      FindMyCast = FoundUserCast->getVPSingleValue();
+    }
+  }
+  for (auto &E : CastsToRemove) {
+    E.first->getVPSingleValue()->replaceAllUsesWith(E.second);
+    E.first->eraseFromParent();
+  }
+}

llvm/test/Transforms/LoopVectorize/induction.ll

loop:
   %add = add i32 %iv.trunc, %mul
   store i32 %add, i32* %dst.gep
   %exitcond = icmp eq i32 %trunc.iv.next, 100
   br i1 %exitcond, label %exit, label %loop
 
 exit:
   ret void
 }
+
+; Test case where %iv.2.ext and %iv.2.conv become redundant due to the SCEV
+; predicates generated for the vector loop. They should be removed in the
+; vector loop.
+define void @test_optimized_cast_induction_feeding_first_order_recurrence(i64 %n, i32 %step, i32* %ptr) {
+; CHECK-LABEL: @test_optimized_cast_induction_feeding_first_order_recurrence(
+; CHECK-LABEL: vector.body:
+; CHECK-NEXT:    [[MAIN_IV:%.+]] = phi i64 [ 0, %vector.ph ], [ [[MAIN_IV_NEXT:%.+]], %vector.body ]
+; CHECK-NEXT:    [[VEC_RECUR:%.+]] = phi <2 x i32> [ <i32 poison, i32 0>, %vector.ph ], [ [[VEC_IV:%.+]], %vector.body ]
+; CHECK-NEXT:    [[VEC_IV]] = phi <2 x i32> [ %induction, %vector.ph ], [ [[VEC_IV_NEXT:%.+]], %vector.body ]
+; CHECK-NEXT:    [[MAIN_IV_0:%.+]] = add i64 [[MAIN_IV]], 0
+; CHECK-NEXT:    [[RECUR_SHUFFLE:%.+]] = shufflevector <2 x i32> [[VEC_RECUR]], <2 x i32> [[VEC_IV]], <2 x i32> <i32 1, i32 2>
+; CHECK-NEXT:    [[GEP0:%.+]] = getelementptr inbounds i32, i32* %ptr, i64 [[MAIN_IV_0]]
+; CHECK-NEXT:    [[GEP1:%.+]] = getelementptr inbounds i32, i32* [[GEP0]], i32 0
+; CHECK-NEXT:    [[GEP_CAST:%.+]] = bitcast i32* [[GEP1]] to <2 x i32>*
+; CHECK-NEXT:    store <2 x i32> [[RECUR_SHUFFLE]], <2 x i32>* [[GEP_CAST]], align 4
+; CHECK-NEXT:    [[MAIN_IV_NEXT]] = add nuw i64 [[MAIN_IV]], 2
+; CHECK-NEXT:    [[VEC_IV_NEXT]] = add <2 x i32> [[VEC_IV]],
+;
+entry:
+  br label %loop
+
+loop:
+  %for = phi i32 [ 0, %entry ], [ %iv.2.conv, %loop ]
+  %iv.1 = phi i64 [ 0, %entry ], [ %iv.1.next, %loop ]
+  %iv.2 = phi i32 [ 0, %entry ], [ %iv.2.next, %loop ]
+  %iv.2.ext = shl i32 %iv.2, 24
+  %iv.2.conv = ashr exact i32 %iv.2.ext, 24
+  %gep = getelementptr inbounds i32, i32* %ptr, i64 %iv.1
+  store i32 %for, i32* %gep, align 4
+  %iv.2.next = add nsw i32 %iv.2.conv, %step
+  %iv.1.next = add nuw nsw i64 %iv.1, 1
+  %exitcond = icmp eq i64 %iv.1.next, %n
+  br i1 %exitcond, label %exit, label %loop
+
+exit:
+  ret void
+}