[VPlan] Replace IR based truncateToMinimalBitwidths with VPlan version.

[fhahn]

Summary

This patch replaces the IR based truncateToMinimalBitwidths with a VPlan
version. This has 2 benefits:

1. the VPlan-based version is simpler; we don't need to implement special codegen for each supported instruction type like the IR based one.
2. Removes a dependency on the cost-model after VPlan execution and
3. Removes a use of getVPValue that uses underlying values after VPlan execution (See removed FIXME).

Depends on D149081.

Depends on D149079.

[Ayal]

llvm/lib/Transforms/Vectorize/VPlan.h

280 ↗

(On Diff #553760)

How/Is this removal related?

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

769

(Future) Thought: wonder if instead of iterating over all live-ins looking to truncate any, it may be better to iterate over MinBWs and check if any are live-ins. Or lookup MinBWs upon construction of a live-in.

770

nit: use LiveInInst or something similar rather than UI?

776

783

Set once before the loop for all live-ins to be truncated.

792

Any order other than depth first would also do, right?

803

(Future) Thought: this is an awkward way of retrieving "the" recipe that corresponds to each member of MinBWs - look through all recipes for those having the desired "underlying" insn. Perhaps better lookup MinBWs upon construction of a recipe for an Instruction.
Or migrate the analysis that builds MinBWs to run on VPlan.

804

nit: lookup.

809

Would be good to comment how memory and replicate cases are (not) processed.

815

Better assert than continue? Here ProcessedRecipes was already bumped, but should all MinBWs members correspond to Integer types, of distinct (smaller) size, whether live-in or not?

825

This deals only with ZExt/SExt, easier to check directly if Opcode is one or the other?

OTOH, better handle Trunc here as well? Is it handled well below?

829

// SExt/Zext is redundant - stick with its operand.
?

836

Place assert earlier?

838–839

850

This means the size of all operands is equal to NewResSizeInBits, can this be?

854–855

nit: keep consistent with above.

863–865

nit: keep consistent with above.

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

47

nit: a VPlan transform should fold redundant ZExt-Trunc pairs rather than leaving them ("as hints") to InstCombine.

Being a public method, which does not need SE, should the caller of optimize() precede its call with a direct call to trunctateToMinimalBitwidth(), rather than pass MinBWs to optimize()?

[fhahn]

Address latest comments, apologies for the delay!

llvm/lib/Transforms/Vectorize/VPlan.h

280 ↗

(On Diff #553760)

The last user of this function has been removed in the patch.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

759–760

Code has been moved to D159202

762–764

code has been moved to D159202

768

Wrapped and added comment, thanks!

770

Renamed, thanks!

771

Updated, thanks!

776

Adjusted, thanks!

777

Turned into assert, thanks!

783

hoisted, thanks!

792

Yes, I think the order doesn't matter here.

804

Done, thanks!

809

Added a comment, thanks!

815

Turned isIntegerTy into assert but retained size check as there entries where the sizes are the same (e.g. for truncs).

825

Thanks, changed to if. I don't think Trunc is handled explicitly in the latest version.

829

this check has been moved up and is not needed any longer.

836

moved up,, thanks!

838–839

adjusted, thanks!

850

There are cases where a Zext narrowed earlier is used as operand here, so the tie is already adjusted.

854–855

Adjusted, thanks!

863–865

reordered, thanks!

[Ayal]

Various comments, also trying to reason about how this patch changes tests.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3564

Retain a comment explaining why replicate recipes are not truncated?

3599

Retain this comment regarding dropping wrapping flags?

3614

A Trunc is handled by shrinking its operand.

3639

(If nothing is done to the operands, what is the result extended too?)

llvm/lib/Transforms/Vectorize/VPlan.h

280 ↗

(On Diff #553760)

Very well!

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

760

Thought: worth introducing as a member of VPValue, to be overridden by VPWidenCastRecipe? Note that this is Element/Scalar Type.

Effectively adding scalar type info to all VPValues? Might be good to investigate separately, although the current use-cases would probably be very limited

Very well.

768

Suffice to ask if (!NewResSizeInBits)?

769

Thoughts about the above? Hopefully avoids exposing getLiveIns(), at the expense of holding a mapping between Values and LiveIns, as in LiveOuts.

772

assert "MinBW member must be integer" rather than continue - thereby skipping a MinBW member.

785

Thought: could/should each MinBW be attached to its recipe asap - when the latter is created, considering it depends on associated underlying instruction?

Might be a potential follow-up, but we would still potentially updated MinBWs on each recipe replacement?

Sure, like updating any other property of a recipe when replaced.

788

Can skip phi's, none are included in MinBWs.

789

Are any loads included in MinBWs, or is this dead code? Stores of course are irrelevant.

801

Agreed - MinBW should specify a consistent minimal bit width for all users, and for all operands, but there seems to be some discrepancy that is confusing:

A. Instructions whose operands and return value are all of a single type (excluding condition operand of selects) are converted to operate on a narrower type by (a) shrinking their operands to the narrower type and (b) extending their result from the narrower type to their original type. Instructions that feed values to such instructions or use their values, continue to feed and use values of the original type.
A pair of such instructions where one feeds the other will be added a zext-trunc pair between them which will later be folded.

B. Instructions that convert between two distinct types, continue to digest the original source type but are updated to produce values of the new destination type. Their users, when reached subsequently, need to check if any of their operands have been narrowed. But if this is the case, why bother expanding results in (b) above? OTOH, the narrowed results of conversion instructions can also be expanded (to be folded later), keeping the treatment consistent? Always expecting the new type to be strictly smaller than the current one. Perhaps conversion instructions could be skipped now and handled by subsequent folding pass - looking for trunc-trunc and sext-trunc pairs in addition to zext-trunc ones?

C. Loads are ignored - excluded from MiinBWs? They could potentially be narrowed to load only the required bits, though its unclear if a strided narrow load is better than a unit-strided wider load and trunc - as in an interleave-group(?)

D. Phis are ignored - excluded from MinBWs. Truncated header induction phi's are handled separately. Other phi's may deserve narrowing(?)

802

Suffice to ask if (!NewResSizeInBits)?

803

Thoughts about the above?

811

Should replicate recipes be handled next to handling widen memory recipes above?

815

nit: ResTy >> OldResTy, ResSizeInBits >> OldResSizeInBits

818

assert(ResSizeInBits > NewResSizeInBits && "Nothing to shrink?"); here instead of below?

824

nit: VPC >> OldExt, Opc >> OldOpc?

825

Does Trunc (which can truncate to a smaller bitwidth) implicitly fall through and has its operand shrunk to the smaller bitwidth, effectively turning it into a ZExt?

828

Comment is obsolete here - dealt with new type being equal to operand type, which should result in replacing the SExt/ZExt with its operand, see below.

829

?

833

nit: C >> NewCast?

If getTypeSizeInBits(Op) == NewResSizeInBits should C be set to Op (w/o inserting it) instead of creating a redundant cast?

850

Maybe worth a comment.

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

47

Thoughts on the above?
Better truncate to minimal bitwidth asap, as it relies on IR information? Conceptually a scalar transform.
Does "as hints to InstCombine" below still hold?

llvm/test/Transforms/LoopVectorize/AArch64/deterministic-type-shrinkage.ll

9–10

hmm, we now spot the redundant duplicate zext of WIDE_LOAD from <16 x i8> to <16 x i16>, originally both TMP4 and TMP10.

15

Spotted and removed duplicate zext of WIDE_LOAD8.

55

BROADCAST_SPLAT is (still) trunc'ed twice due to UF=2?

55

BROADCAST_SPLAT2 is (still) trunc'ed twice due to UF=2?

55

This testcase stores the 2nd least significant byte of a 32b product (of two invariant values, one 16b and the other 32b) checking that computing 16b product suffices. But more optimizations should take place: the expansion of the multipliers to 32b should be eliminated (along with their truncation to 16b), and the invariant multiplication-lshr-trunc sequence should be hoisted out of the loop.

56

Both insertelement's now use poison.

llvm/test/Transforms/LoopVectorize/AArch64/loop-vectorization-factors.ll

308 ↗

(On Diff #557740)

We now fold a trunc-zext of zext'ed WIDE_LOAD from <16 x i16> => <16 x i32> => <16 x i16>,
but fail to fold a similar one following the add-2's?

338 ↗

(On Diff #557740)

We now get rid of a pair of <8 x i16> => <8 x i32> => <8 x i16> before the add-2's (so this is not an NFC patch), but still retain the pair of <8 x i16> => <8 x i32> => <8 x i16> after it - missed MinBW/trunc-zext opportunity?

484 ↗

(On Diff #557740)

Hmm, before we narrowed these two sufflevectors to operate on <16 x i8> and zext-trunc their result, now we let them operate on original <16 x i32> and truncate the result?

498 ↗

(On Diff #557740)

Many zext-trunc pairs left to collect.

513 ↗

(On Diff #557740)

Above trunc of TMP2 is redundant along with its zext in the ph.

520 ↗

(On Diff #557740)

Above trunc of TMP4 is redundant along with its zext in the ph.

llvm/test/Transforms/LoopVectorize/trunc-shifts.ll

334 ↗

(On Diff #557740)

We now get rid of a pair of <4 x i16> => <4 x i32> => <4 x i16> before the lshr (so this is not an NFC patch), but still retain the pair/triple of <4 x i16> => <4 x i32> => <4 x i16> => <4 x i8> after it - missed MinBW opportunity?

[fhahn]

Address comments and major simplification after moving cast folding to simplifyRecipes.

Hope all comments should be addressed, hope i didn't miss any.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

3564

Retained when skipping VPReplicateRecipe.

3599

Done, thanks!

3639

It stays the same, there's no extend in that case.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

760

This has been updated to now use VPTypeAnalysis.

768

This code has now been removed; LiveIns are handled when truncating the other operands of an instruction; otherwise we leave the type info in an inconsistent state.

769

LiveIns are now handled directly when truncating other operands; getLiveIns has been removed.

772

Turned into an assert, thanks!

788

There's an early continue now that skips phis and other unsupported recipes.

789

Nope, looks like this is not needed in the latest version.

801

The latest version doesn't have special treatment for casts, they remain unchanged and VPlan recipe simplification will take care of folding them if possible.

802

Simplified, thanks!

803

I think it would be best to have the analysis based on VPlan. Building MinBWs early would probably require extra work to update/invalidate it during transforms.

811

We still need to count them for verification

[fhahn]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

815

Renamed, thanks!

818

Done, and also removed continue

824

This code is now gone, handled by recipe simplification.

828

Code is gone now

829

Code now gone.

833

Code gone now.

llvm/test/Transforms/LoopVectorize/AArch64/deterministic-type-shrinkage.ll

55

The latest version avoids truncating the same value twice.

55

The latest version avoids truncating the same value twice.

55

still more work to do :)

Arguably the invariant instructions are artificial, in the regular pipeline, no invariant instructions should remain.

56

I think the use of undef is a leftover that wasn't updated; it should be poison.

llvm/test/Transforms/LoopVectorize/AArch64/loop-vectorization-factors.ll

308 ↗

(On Diff #557740)

folding now happens all in simplifyRecieps, should handle this now

484 ↗

(On Diff #557740)

I think there's nothing we can do about that; we first need to splat the value when generating code, but InstCombine should take care of that.

498 ↗

(On Diff #557740)

Should be better cleaned up now

llvm/test/Transforms/LoopVectorize/trunc-shifts.ll

334 ↗

(On Diff #557740)

trunc/ext pairs should be better cleaned up in the latest version

[Ayal]

Looks much simpler! Minor last nits.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

757

nit: are these still hints to InstCombine, or to subsequent VPlan cleanups?

757–759

nit

766–769

?

792

But a (more) expensive RPOT order is needed, to handle defs before uses?

816

Is it possible for MinBWs not to contain Op's live-in IR value in this case?

[fhahn]

Address latest comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

757

Updated, thanks!

757–759

Done thanks! This also limits the scope of TypeInfo to the range where it is valid. after `truncateToMinimalBitwidths, we would need to invalidate the info for the modified recipes otherwise. This can be done in the future.

766–769

Simplified , thanks!

792

The latest version should not need RPO, as the bit width of the results do not change for any user (previously they might due to early cast simplifications). Changed to depth first.

816

Yes, MinBWs only contains instructions, but not other values like arguments. Added a clarifying assert.

[fhahn]

ping :)

[Ayal]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

757–759

Very well. Worth commenting that TypeInfo should not be used following truncateToMinimalBitwidths.

763

nit: ProcessedRecipesNum?

763

ProcessedTruncs is used outside ifdef below, move its definition out of ifdef here? Or is it meant to ensure truncated operands are counted once by ProcessedRecipes for debugging only? If an operand is truncated multiple times, all its truncations must be to the same size, because "MinBW should specify a consistent minimal bit width for all users(, and for all operands)"?

Worth explaining why processed truncs are recorded.

766

Should PH be skipped? Trying to shrink the (live-in) operands of recipes in PH will insert them at the end of PH...

769

Shrunk operands are placed before R, but its extension is placed after - and calls for this make_early_inc_range, right?

785

Just note that the counting of ProcessedRecipes may miss casts that fail to be processed later.

785

Just noting potential follow-up, possibly as a TODO somewhere: attach each MinBW to its recipe when the latter is created, supplementing its underlying inst.

790

Does OldResSizeInBits equal to the size of OldResTy, for the non-cast Widen or Select R?

807

Ins? Perhaps ProcessedTrunc?

808

Handle the simple if !ins.second /* Op already processed */ case first, potentially early-continuing?

Clearer to check if ProcessedTruncs.lookup(Op) or if ProcessedTruncs.contains(Op) and if so use ProcessedTruncs[Op], otherwise insert it?

811

nit: place simpler if !isLiveIn case first?

813–816

nit

821

Note that truncations of live-ins could also be inserted before R, thereby leaving the treatment of live-ins to debugging only, and leaving their LICM and commoning to a subsequent VPlan cleanup pass, along with trunc-zext foldings.

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

47

WDYT on the above: should the caller of optimize() precede its call with a direct call to trunctateToMinimalBitwidth(), rather than pass MinBWs to optimize()?

[fhahn]

Rebase and address latest comments, thanks!

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

757–759

Sunk further into truncateToMinimualBitwidths

763

Changed to NumProcessedRecipes

763

It's to re-use previously generated truncates. Note that we cannot RAUW after creating the new truncate, as this may make other uses not well typed (until they are processed and all their operands are truncated)

Moved out of ifdef

766

Good point, there should be nothing to shrink in PH for now, as the analysis is for the loop body only, adjusted!

769

Yep

785

Do you mean updating the comment here or just a general note? We need to include the recipes in the count, otherwise the verification later will fail

790

Yes, I forgot to remove this use of IR getType. Updated to use TypeInfo.inferScalarType(ResultVPV) and then getScalarSizeInBits of the returned type.

807

Updated, thanks!

808

Early continue would mean duplicating the code to update the operands, I left things for now as is, including using insert. insert means we only need to lookup the insert-pos once, vs 2 lookups with separate lookup and then `[]. WDYT?

811

Done, thanks!

821

Yep, for now it is simpler and results in a smaller test diff to do it directly there as it is not only LICM but also very simple CSE

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

47

Sounds good, updated, thanks!

[Ayal]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

756–835

nit: redundant move of empty line?

763

Note that we cannot RAUW after creating the new truncate, as this may make other uses not well typed (until they are processed and all their operands are truncated)

Very well, may deserve a comment.

785

I mean we count casts as if they are processed, expecting they will be later, w/o checking that they actually do.

790

Ah, ok, wondered if using the size of the type of UI directly would be simpler?

795

Should be the same Ctx passed in as parameter?

808

OK, WDYT of the something as follows:

        auto [ProcessedIter, DidNotExist] = ProcessedTruncs.insert({Op, nullptr});
        VPWidenCastRecipe *NewOp = DidNotExist ? new VPWidenCastRecipe(Instruction::Trunc, Op, NewResTy)
                                               : ProcessedIter->second;
        R.setOperand(Idx, NewOp);
        if (!DidNotExist)
          continue;
        ProcessedIter->second = NewOp;
        if (!Op->isLiveIn()) {
          Shrunk->insertBefore(&R);
        } else {
          PH->appendRecipe(Shrunk);
#ifndef NDEBUG
          auto *OpInst = dyn_cast<Instruction>(Op->getLiveInIRValue());
          bool IsContained = MinBWs.contains(OpInst);
          assert((!OpInst || IsContained) &&
                 "All processed instructions should be contained in MinBWs.");
          NumProcessedRecipes += IsContained;
#endif
        }

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

47

[Ayal]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

808

Maybe IterIsEmpty would be a better name, to avoid double negation, as in:

        auto [ProcessedIter, IterIsEmpty] = ProcessedTruncs.insert({Op, nullptr});
        VPWidenCastRecipe *NewOp = IterIsEmpty ? new VPWidenCastRecipe(Instruction::Trunc, Op, NewResTy)
                                               : ProcessedIter->second;
        R.setOperand(Idx, NewOp);
        if (!IterIsEmpty)
          continue;
        ProcessedIter->second = NewOp;
        if (!Op->isLiveIn()) {
          NewOp->insertBefore(&R);
        } else {
          PH->appendRecipe(NewOp);
#ifndef NDEBUG
          auto *OpInst = dyn_cast<Instruction>(Op->getLiveInIRValue());
          bool IsContained = MinBWs.contains(OpInst);
          assert((!OpInst || IsContained) &&
                 "All processed instructions should be contained in MinBWs.");
          NumProcessedRecipes += IsContained;
#endif
        }

[fhahn]

Addressed latest comments, thanks!

[fhahn]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

756–835

changed back, thanks!

763

Added a comment to ProcessedTruncs definition.

785

They don't need handling explicitly, as redundant casts will be removed later. Expanded the comment slightly to

Also skip casts which do not need to be handled explicitly here, as redundant casts will be removed during recipe simplification.

790

It might be slightly simpler, but would mean this may lead to a crash further down the line, once we support recipes without underlying values/instructions (and we forget to update this line) and/or if some other transform adjusted the type. Left as is for now

795

Yes, fixed!

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

47

Fixed, thanks!

[Ayal]

This looks good to me, thanks for accommodating!
Adding a minor redundancy spotted plus some test related notes.

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

833

redundant - hoist above the early-continue.

llvm/test/Transforms/LoopVectorize/AArch64/deterministic-type-shrinkage.ll

54

Trunc & insertelement LICM'd from vec.epilog.vector.body to vec.epilog.ph.

55

Duplicated TMP0 and TMP1 still here?

55

Still seeing duplicate TMP2 and TMP3?

55–56

ditto.

llvm/test/Transforms/LoopVectorize/AArch64/loop-vectorization-factors.ll

308 ↗

(On Diff #557740)

The one following the add-2's is also folded now.

338 ↗

(On Diff #557740)

Other pair also folded now.

484 ↗

(On Diff #557740)

Worth testing with a subsequent instCombine, to ensure pessimization is avoided?

498 ↗

(On Diff #557740)

Indeed looks like it!

30 ↗

(On Diff #558195)

Fold zext-trunc pair, several such cases follow.

llvm/test/Transforms/LoopVectorize/trunc-shifts.ll

334 ↗

(On Diff #557740)

Indeed!

[fhahn]

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

833

Fixed in the committed version, thanks!

llvm/test/Transforms/LoopVectorize/AArch64/deterministic-type-shrinkage.ll

55

They were due to redundant casts being added for Live-in values, fixed by checking in VPWidenCastRecipe::execute for now, with a FIXME to address this with explicit unrolling.

[mstorsjo]

This triggers failed asserts, see https://github.com/llvm/llvm-project/issues/74231.

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp

protected:
   /// Clear NSW/NUW flags from reduction instructions if necessary.
   void clearReductionWrapFlags(VPReductionPHIRecipe *PhiR,
                                VPTransformState &State);
 
   /// Iteratively sink the scalarized operands of a predicated instruction into
   /// the block that was created for it.
   void sinkScalarOperands(Instruction *PredInst);
 
-  /// Shrinks vector element sizes to the smallest bitwidth they can be legally
-  /// represented as.
-  void truncateToMinimalBitwidths(VPTransformState &State);
-
   /// Returns (and creates if needed) the trip count of the widened loop.
   Value *getOrCreateVectorTripCount(BasicBlock *InsertBlock);
 
   /// Returns a bitcasted value to the requested vector type.
   /// Also handles bitcasts of vector<float> <-> vector<pointer> types.
   Value *createBitOrPointerCast(Value *V, VectorType *DstVTy,
                                 const DataLayout &DL);
 

 }
 
 static Type *largestIntegerVectorType(Type *T1, Type *T2) {
   auto *I1 = cast<IntegerType>(cast<VectorType>(T1)->getElementType());
   auto *I2 = cast<IntegerType>(cast<VectorType>(T2)->getElementType());
   return I1->getBitWidth() > I2->getBitWidth() ? T1 : T2;
 }
 
-void InnerLoopVectorizer::truncateToMinimalBitwidths(VPTransformState &State) {
-  // For every instruction `I` in MinBWs, truncate the operands, create a
-  // truncated version of `I` and reextend its result. InstCombine runs
-  // later and will remove any ext/trunc pairs.
-  SmallPtrSet<Value *, 4> Erased;
-  for (const auto &KV : Cost->getMinimalBitwidths()) {
-    // If the value wasn't vectorized, we must maintain the original scalar
-    // type. The absence of the value from State indicates that it
-    // wasn't vectorized.
-    // FIXME: Should not rely on getVPValue at this point.
-    VPValue *Def = State.Plan->getVPValue(KV.first, true);
-    if (!State.hasAnyVectorValue(Def))
-      continue;
-    for (unsigned Part = 0; Part < UF; ++Part) {
-      Value *I = State.get(Def, Part);
-      if (Erased.count(I) || I->use_empty() || !isa<Instruction>(I))
-        continue;
-      Type *OriginalTy = I->getType();
-      Type *ScalarTruncatedTy =
-          IntegerType::get(OriginalTy->getContext(), KV.second);
-      auto *TruncatedTy = VectorType::get(
-          ScalarTruncatedTy, cast<VectorType>(OriginalTy)->getElementCount());
-      if (TruncatedTy == OriginalTy)
-        continue;
-
-      IRBuilder<> B(cast<Instruction>(I));
-      auto ShrinkOperand = [&](Value *V) -> Value * {
-        if (auto *ZI = dyn_cast<ZExtInst>(V))
-          if (ZI->getSrcTy() == TruncatedTy)
-            return ZI->getOperand(0);
-        return B.CreateZExtOrTrunc(V, TruncatedTy);
-      };
-
-      // The actual instruction modification depends on the instruction type,
-      // unfortunately.
-      Value *NewI = nullptr;
-      if (auto *BO = dyn_cast<BinaryOperator>(I)) {
-        NewI = B.CreateBinOp(BO->getOpcode(), ShrinkOperand(BO->getOperand(0)),
-                             ShrinkOperand(BO->getOperand(1)));
-
-        // Any wrapping introduced by shrinking this operation shouldn't be
-        // considered undefined behavior. So, we can't unconditionally copy
-        // arithmetic wrapping flags to NewI.
-        cast<BinaryOperator>(NewI)->copyIRFlags(I, /*IncludeWrapFlags=*/false);
-      } else if (auto *CI = dyn_cast<ICmpInst>(I)) {
-        NewI =
-            B.CreateICmp(CI->getPredicate(), ShrinkOperand(CI->getOperand(0)),
-                         ShrinkOperand(CI->getOperand(1)));
-      } else if (auto *SI = dyn_cast<SelectInst>(I)) {
-        NewI = B.CreateSelect(SI->getCondition(),
-                              ShrinkOperand(SI->getTrueValue()),
-                              ShrinkOperand(SI->getFalseValue()));
-      } else if (auto *CI = dyn_cast<CastInst>(I)) {
-        switch (CI->getOpcode()) {
-        default:
-          llvm_unreachable("Unhandled cast!");
-        case Instruction::Trunc:
-          NewI = ShrinkOperand(CI->getOperand(0));
-          break;
-        case Instruction::SExt:
-          NewI = B.CreateSExtOrTrunc(
-              CI->getOperand(0),
-              smallestIntegerVectorType(OriginalTy, TruncatedTy));
-          break;
-        case Instruction::ZExt:
-          NewI = B.CreateZExtOrTrunc(
-              CI->getOperand(0),
-              smallestIntegerVectorType(OriginalTy, TruncatedTy));
-          break;
-        }
-      } else if (auto *SI = dyn_cast<ShuffleVectorInst>(I)) {
-        auto Elements0 =
-            cast<VectorType>(SI->getOperand(0)->getType())->getElementCount();
-        auto *O0 = B.CreateZExtOrTrunc(
-            SI->getOperand(0), VectorType::get(ScalarTruncatedTy, Elements0));
-        auto Elements1 =
-            cast<VectorType>(SI->getOperand(1)->getType())->getElementCount();
-        auto *O1 = B.CreateZExtOrTrunc(
-            SI->getOperand(1), VectorType::get(ScalarTruncatedTy, Elements1));
-
-        NewI = B.CreateShuffleVector(O0, O1, SI->getShuffleMask());
-      } else if (isa<LoadInst>(I) || isa<PHINode>(I)) {
-        // Don't do anything with the operands, just extend the result.
-        continue;
-      } else if (auto *IE = dyn_cast<InsertElementInst>(I)) {
-        auto Elements =
-            cast<VectorType>(IE->getOperand(0)->getType())->getElementCount();
-        auto *O0 = B.CreateZExtOrTrunc(
-            IE->getOperand(0), VectorType::get(ScalarTruncatedTy, Elements));
-        auto *O1 = B.CreateZExtOrTrunc(IE->getOperand(1), ScalarTruncatedTy);
-        NewI = B.CreateInsertElement(O0, O1, IE->getOperand(2));
-      } else if (auto *EE = dyn_cast<ExtractElementInst>(I)) {
-        auto Elements =
-            cast<VectorType>(EE->getOperand(0)->getType())->getElementCount();
-        auto *O0 = B.CreateZExtOrTrunc(
-            EE->getOperand(0), VectorType::get(ScalarTruncatedTy, Elements));
-        NewI = B.CreateExtractElement(O0, EE->getOperand(2));
-      } else {
-        // If we don't know what to do, be conservative and don't do anything.
-        continue;
-      }
-
-      // Lastly, extend the result.
-      NewI->takeName(cast<Instruction>(I));
-      Value *Res = B.CreateZExtOrTrunc(NewI, OriginalTy);
-      I->replaceAllUsesWith(Res);
-      cast<Instruction>(I)->eraseFromParent();
-      Erased.insert(I);
-      State.reset(Def, Res, Part);
-    }
-  }
-
-  // We'll have created a bunch of ZExts that are now parentless. Clean up.
-  for (const auto &KV : Cost->getMinimalBitwidths()) {
-    // If the value wasn't vectorized, we must maintain the original scalar
-    // type. The absence of the value from State indicates that it
-    // wasn't vectorized.
-    // FIXME: Should not rely on getVPValue at this point.
-    VPValue *Def = State.Plan->getVPValue(KV.first, true);
-    if (!State.hasAnyVectorValue(Def))
-      continue;
-    for (unsigned Part = 0; Part < UF; ++Part) {
-      Value *I = State.get(Def, Part);
-      ZExtInst *Inst = dyn_cast<ZExtInst>(I);
-      if (Inst && Inst->use_empty()) {
-        Value *NewI = Inst->getOperand(0);
-        Inst->eraseFromParent();
-        State.reset(Def, NewI, Part);
-      }
-    }
-  }
-}
-
 void InnerLoopVectorizer::fixVectorizedLoop(VPTransformState &State,
                                             VPlan &Plan) {
-  // Insert truncates and extends for any truncated instructions as hints to
-  // InstCombine.
-  if (VF.isVector())
-    truncateToMinimalBitwidths(State);
-
   // Fix widened non-induction PHIs by setting up the PHI operands.
   if (EnableVPlanNativePath)
     fixNonInductionPHIs(Plan, State);
 
   // At this point every instruction in the original loop is widened to a
   // vector form. Now we need to fix the recurrences in the loop. These PHI
   // nodes are currently empty because we did not want to introduce cycles.
   // This is the second stage of vectorizing recurrences.
std::optional<VPlanPtr> LoopVectorizationPlanner::tryToBuildVPlanWithVPRecipes(
 
   // ---------------------------------------------------------------------------
   // Transform initial VPlan: Apply previously taken decisions, in order, to
   // bring the VPlan to its final state.
   // ---------------------------------------------------------------------------
 
   VPlanTransforms::removeRedundantCanonicalIVs(*Plan);
   VPlanTransforms::removeRedundantInductionCasts(*Plan);
+  VPlanTransforms::truncateToMinimalBitwidths(*Plan, CM.getMinimalBitwidths());
 
   // Adjust the recipes for any inloop reductions.
   adjustRecipesForReductions(cast<VPBasicBlock>(TopRegion->getExiting()), Plan,
                              RecipeBuilder, Range.Start);
 
   // Sink users of fixed-order recurrence past the recipe defining the previous
   // value and introduce FirstOrderRecurrenceSplice VPInstructions.
   if (!VPlanTransforms::adjustFixedOrderRecurrences(*Plan, Builder))

llvm/lib/Transforms/Vectorize/VPlanTransforms.h

struct VPlanTransforms {
 
   /// Wrap predicated VPReplicateRecipes with a mask operand in an if-then
   /// region block and remove the mask operand. Optimize the created regions by
   /// iteratively sinking scalar operands into the region, followed by merging
   /// regions until no improvements are remaining.
   static void createAndOptimizeReplicateRegions(VPlan &Plan);
 
   /// Remove redundant VPBasicBlocks by merging them into their predecessor if
   /// the predecessor has a single successor.
   static bool mergeBlocksIntoPredecessors(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.
struct VPlanTransforms {
   /// not valid.
   static bool adjustFixedOrderRecurrences(VPlan &Plan, VPBuilder &Builder);
 
   /// Optimize \p Plan based on \p BestVF and \p BestUF. This may restrict the
   /// resulting plan to \p BestVF and \p BestUF.
   static void optimizeForVFAndUF(VPlan &Plan, ElementCount BestVF,
                                  unsigned BestUF,
                                  PredicatedScalarEvolution &PSE);
+  /// Insert truncates and extends for any truncated instructions as hints to
+  /// InstCombine.
+  static void
+  truncateToMinimalBitwidths(VPlan &Plan,
+                             const MapVector<Instruction *, uint64_t> &MinBWs);
 };
 
 } // namespace llvm
 
 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLANTRANSFORMS_H

llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

auto *RecurSplice = cast<VPInstruction>(
                              {FOR, FOR->getBackedgeValue()}));
 
     FOR->replaceAllUsesWith(RecurSplice);
     // Set the first operand of RecurSplice to FOR again, after replacing
     // all users.
     RecurSplice->setOperand(0, FOR);
   }
   return true;
 }
+
+void VPlanTransforms::truncateToMinimalBitwidths(
+    VPlan &Plan, const MapVector<Instruction *, uint64_t> &MinBWs) {
+  auto GetType = [](VPValue *Op) {
+    auto *UV = Op->getUnderlyingValue();
+    if (UV)
+      return UV->getType();
+    if (auto *VPC = dyn_cast<VPWidenCastRecipe>(Op)) {
+      return VPC->getResultType();
+    }
+    llvm_unreachable("trying to get type of a VPValue without type info");
+  };
+  for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(
+           vp_depth_first_deep(Plan.getEntry()))) {
+    for (VPRecipeBase &R : make_early_inc_range(*VPBB)) {
+      if (R.getNumDefinedValues() != 1)
+        continue;
+
+      auto *UV =
+          cast_or_null<Instruction>(R.getVPSingleValue()->getUnderlyingValue());
+      auto I = MinBWs.find(UV);
+      if (!UV || I == MinBWs.end())
+        continue;
+
+      Type *ResTy = UV->getType();
+      if (!ResTy->isIntegerTy() || ResTy->getScalarSizeInBits() == I->second)
+        continue;
+
+      if (!isa<VPWidenRecipe, VPWidenSelectRecipe, VPWidenCastRecipe>(&R))
+        continue;
+
+      LLVMContext &Ctx = ResTy->getContext();
+
+      // Try to replace wider SExt/ZExts with narrower ones if possible.
+      if (auto *VPW = dyn_cast<VPWidenCastRecipe>(&R)) {
+        Instruction *UI = VPW->getUnderlyingInstr();
+        switch (UI->getOpcode()) {
+        default:
+          break;
+        case Instruction::SExt:
+        case Instruction::ZExt: {
+          if (UI->getType()->getScalarSizeInBits() > I->second) {
+            if (GetType(VPW->getOperand(0))->getScalarSizeInBits() >= I->second)
+              break;
+            auto *C = new VPWidenCastRecipe(cast<CastInst>(UI)->getOpcode(),
+                                            VPW->getOperand(0),
+                                            IntegerType::get(Ctx, I->second));
+            C->insertBefore(VPW);
+            VPW->replaceAllUsesWith(C);
+            continue;
+          }
+        }
+        }
+      }
+
+      // Shrink operands by introducing truncates as needed.
+      for (unsigned Idx = 0; Idx != R.getNumOperands(); ++Idx) {
+        auto *Op = R.getOperand(Idx);
+        if (GetType(Op)->getScalarSizeInBits() == I->second)
+          continue;
+        if (auto *VPW = dyn_cast<VPWidenRecipe>(&R))
+          VPW->dropPoisonGeneratingFlags();
+
+        auto *Shrunk =
+            new VPWidenCastRecipe(Instruction::Trunc, R.getOperand(Idx),
+                                  IntegerType::get(Ctx, I->second));
+        R.setOperand(Idx, Shrunk);
+        Shrunk->insertBefore(&R);
+      }
+
+      // Extend result to original width.
+      auto *Ext =
+          new VPWidenCastRecipe(Instruction::ZExt, R.getVPSingleValue(), ResTy);
+      R.getVPSingleValue()->replaceAllUsesWith(Ext);
+      Ext->setOperand(0, R.getVPSingleValue());
+      Ext->insertAfter(&R);
+    }
+  }
+}

llvm/test/Transforms/LoopVectorize/AArch64/deterministic-type-shrinkage.ll

 ; RUN: opt -opaque-pointers=0 -S < %s -passes=loop-vectorize,instcombine 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
 target triple = "aarch64"
 
 ;; See https://llvm.org/bugs/show_bug.cgi?id=25490
 ;; Due to the data structures used, the LLVM IR was not determinisic.
 ;; This test comes from the PR.
 
 ;; CHECK-LABEL: @test(
 ; CHECK: load <16 x i8>
+; CHECK-NEXT: zext <16 x i8>
 ; CHECK-NEXT: getelementptr
 ; CHECK-NEXT: bitcast
 ; CHECK-NEXT: load <16 x i8>
 ; CHECK-NEXT: zext <16 x i8>
-; CHECK-NEXT: zext <16 x i8>
 define void @test(i32 %n, i8* nocapture %a, i8* nocapture %b, i8* nocapture readonly %c) {
 entry:
   %cmp.28 = icmp eq i32 %n, 0
   br i1 %cmp.28, label %for.cond.cleanup, label %for.body.preheader
 
 for.body.preheader:                               ; preds = %entry
   br label %for.body
 
for.body:                                         ; preds = %for.body.preheader, %for.body
   %mul10 = mul nuw nsw i32 %conv9, %conv
   %shr11.27 = lshr i32 %mul10, 8
   %conv12 = trunc i32 %shr11.27 to i8
   store i8 %conv12, i8* %arrayidx8, align 1
   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
   %lftr.wideiv = trunc i64 %indvars.iv.next to i32
   %exitcond = icmp eq i32 %lftr.wideiv, %n
   br i1 %exitcond, label %for.cond.cleanup.loopexit, label %for.body
 }

llvm/test/Transforms/LoopVectorize/ARM/pointer_iv.ll

 ; CHECK-NEXT:    [[NEXT_GEP:%.*]] = getelementptr i8, ptr [[A]], i32 [[TMP0]]
 ; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[INDEX]], 2
 ; CHECK-NEXT:    [[NEXT_GEP4:%.*]] = getelementptr i8, ptr [[B]], i32 [[TMP1]]
 ; CHECK-NEXT:    [[WIDE_VEC:%.*]] = load <8 x i32>, ptr [[NEXT_GEP]], align 4
 ; CHECK-NEXT:    [[STRIDED_VEC:%.*]] = shufflevector <8 x i32> [[WIDE_VEC]], <8 x i32> poison, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
 ; CHECK-NEXT:    [[TMP2:%.*]] = add nsw <4 x i32> [[STRIDED_VEC]], [[BROADCAST_SPLAT]]
 ; CHECK-NEXT:    store <4 x i32> [[TMP2]], ptr [[NEXT_GEP4]], align 4
 ; CHECK-NEXT:    [[INDEX_NEXT]] = add nuw i32 [[INDEX]], 4
-; CHECK-NEXT:    [[TMP4:%.*]] = icmp eq i32 [[INDEX_NEXT]], 996
-; CHECK-NEXT:    br i1 [[TMP4]], label [[FOR_BODY:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP3:![0-9]+]]
+; CHECK-NEXT:    [[TMP3:%.*]] = icmp eq i32 [[INDEX_NEXT]], 996
+; CHECK-NEXT:    br i1 [[TMP3]], label [[FOR_BODY:%.*]], label [[VECTOR_BODY]], !llvm.loop [[LOOP3:![0-9]+]]
 ; CHECK:       for.body:
 ; CHECK-NEXT:    [[A_ADDR_09:%.*]] = phi ptr [ [[ADD_PTR:%.*]], [[FOR_BODY]] ], [ [[IND_END]], [[VECTOR_BODY]] ]
 ; CHECK-NEXT:    [[I_08:%.*]] = phi i32 [ [[INC:%.*]], [[FOR_BODY]] ], [ 996, [[VECTOR_BODY]] ]
 ; CHECK-NEXT:    [[B_ADDR_07:%.*]] = phi ptr [ [[INCDEC_PTR:%.*]], [[FOR_BODY]] ], [ [[IND_END2]], [[VECTOR_BODY]] ]
 ; CHECK-NEXT:    [[TMP4:%.*]] = load i32, ptr [[A_ADDR_09]], align 4
 ; CHECK-NEXT:    [[ADD_PTR]] = getelementptr inbounds i32, ptr [[A_ADDR_09]], i32 2
 ; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[TMP4]], [[Y]]
 ; CHECK-NEXT:    store i32 [[ADD]], ptr [[B_ADDR_07]], align 4
for.body:
   %inc = add nuw nsw i32 %i.07, 1
   %exitcond = icmp eq i32 %inc, 10000
   br i1 %exitcond, label %for.cond.cleanup, label %for.body, !llvm.loop !2
 }
 
 define hidden void @mult_ptr_iv(ptr noalias nocapture readonly %x, ptr noalias nocapture %z) {
 ; CHECK-LABEL: @mult_ptr_iv(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[UGLYGEP:%.*]] = getelementptr i8, ptr [[Z:%.*]], i32 3000
-; CHECK-NEXT:    [[UGLYGEP1:%.*]] = getelementptr i8, ptr [[X:%.*]], i32 3000
-; CHECK-NEXT:    [[BOUND0:%.*]] = icmp ugt ptr [[UGLYGEP1]], [[Z]]
-; CHECK-NEXT:    [[BOUND1:%.*]] = icmp ugt ptr [[UGLYGEP]], [[X]]
+; CHECK-NEXT:    [[SCEVGEP:%.*]] = getelementptr i8, ptr [[Z:%.*]], i32 3000
+; CHECK-NEXT:    [[SCEVGEP1:%.*]] = getelementptr i8, ptr [[X:%.*]], i32 3000
+; CHECK-NEXT:    [[BOUND0:%.*]] = icmp ugt ptr [[SCEVGEP1]], [[Z]]
+; CHECK-NEXT:    [[BOUND1:%.*]] = icmp ugt ptr [[SCEVGEP]], [[X]]
 ; CHECK-NEXT:    [[FOUND_CONFLICT:%.*]] = and i1 [[BOUND0]], [[BOUND1]]
 ; CHECK-NEXT:    br i1 [[FOUND_CONFLICT]], label [[FOR_BODY:%.*]], label [[VECTOR_PH:%.*]]
 ; CHECK:       vector.ph:
 ; CHECK-NEXT:    [[IND_END:%.*]] = getelementptr i8, ptr [[X]], i32 3000
 ; CHECK-NEXT:    [[IND_END2:%.*]] = getelementptr i8, ptr [[Z]], i32 3000
 ; CHECK-NEXT:    br label [[VECTOR_BODY:%.*]]
 ; CHECK:       vector.body:
 ; CHECK-NEXT:    [[POINTER_PHI:%.*]] = phi ptr [ [[X]], [[VECTOR_PH]] ], [ [[PTR_IND:%.*]], [[VECTOR_BODY]] ]