[LV] Untangle the concepts of uniform and scalar

[mssimpso]

Summary

This patch refactors the logic in collectLoopUniforms and collectValuesToIgnore, untangling the concepts of "uniform" and "scalar". It adds isScalarAfterVectorization along side isUniformAfterVectorization to distinguish the two. Known scalar values include those that are uniform, getelementptr instructions that won't be vectorized, and induction variables and induction variable update instructions whose users are all known to be scalar.

This patch includes the following functional changes:

• In collectLoopUniforms, we mark uniform the pointer operands of interleaved accesses. Although non-consecutive, these pointers are treated like consecutive pointers during vectorization.
• In collectValuesToIgnore, we insert a value into VecValuesToIgnore if it isScalarAfterVectorization rather than isUniformAfterVectorization. This differs from the previous functionality in that we now add getelementptr instructions that will not be vectorized into VecValuesToIgnore.

This patch also removes the ValuesNotWidened set used for induction variable scalarization since, after the above changes, it is now equivalent to isScalarAfterVectorization.

[mssimpso]

Removed unused SmallPtrSet.

[wmi]

test/Transforms/LoopVectorize/induction.ll

295 ↗

(On Diff #65750)

Hi Matthew,

A problem I see to make getelementptr as uniform when it is non-consecutive is:

For the testcase here, if we don't enable interleave memory access,
we will generate vectorized version for "%0 = shl nsw i64 %i, 2". However with your patch "%0 = shl nsw i64 %i, 2" will also be marked as uniform because "%1 = getelementptr inbounds i32, i32* %a, i64 %0" is marked as uniform. These are contradicted results.

Even if we generate scalarized version for "%0 = shl nsw i64 %i, 2", the instruction cost for "%0 = shl nsw i64 %i, 2" should be VF. Marking it as uniform will lower its cost estimation to be only 1.

Thanks,
Wei.

[anemet]

lib/Transforms/Vectorize/LoopVectorize.cpp

1518–1519 ↗

(On Diff #65750)

I was looking at this code recently and was surprised to see that we never actually describe what uniformity is (especially because we use it for other things than just loop-invariant addresses). As a first step, would you mind filling this gap?

My take is that we currently call something uniform if we don't need to generate values for each horizontal value in a vector loop iteration, more precisely we only need to generate the first one. This is true for a few things: the induction variable, loop-invariant addresses, pointers for consecutive accesses (because the vector access instruction implicitly generates the horizontal addresses).

[mssimpso]

lib/Transforms/Vectorize/LoopVectorize.cpp

1518–1519 ↗

(On Diff #65750)

I completely agree and don't mind doing this at all. Thanks for putting that into words!

test/Transforms/LoopVectorize/induction.ll

295 ↗

(On Diff #65750)

You're right - the GEP will only be uniform here if the loads/stores are in interleaved groups. This makes some sense to me because when interleaving we treat the pointer as if it was consecutive. Thanks! I will update the patch.

[mssimpso]

Addressed comments from Adam and Wei.

• Properly defined uniform after vectorization and updated comments.
• Untangled the concepts of "uniform" and "scalar".
• Updated the revision title and summary.

Thanks!

[mssimpso]

Actually, I don't this this revision is quite right yet. I"ll post another update shortly. Sorry!

[mssimpso]

Addressed issues I alluded to in my previous comment.

This revision completely separates the decision to scalarize an induction variable from the logic in collectLoopUniforms and collectValuesToIgnore. The need to do this became apparent after better defining what we mean by uniform (see the added comment above the collectLoopUniforms declaration). Since scalar doesn't imply uniformity, it doesn't make sense to use collectLoopUniforms to determine which induction variables will be scalar.

[anemet]

Very nice clean-up, Matt!

I liked it in the old description that it listed the functional changes. These are gone now (I am assuming you will be using the description for the commit log).

I still want to think a little bit about the functionality changes but would be good if you could take care of the one thing below.

lib/Transforms/Vectorize/LoopVectorize.cpp

1480–1490 ↗

(On Diff #65977)

Moving this inside Legal seems orthogonal to this patch, if so please split this part out and commit.

[mkuper]

I'll look at this tomorrow, I hope.
For now, just a note about what Adam suggested.

lib/Transforms/Vectorize/LoopVectorize.cpp

1487 ↗

(On Diff #65977)

If you're going to split this out and commit - note that this sequence is what we have the getPointerOperand() helper (that I still want to unify with the 6 others we have throughout the code base...) for.

[mssimpso]

lib/Transforms/Vectorize/LoopVectorize.cpp

1480–1490 ↗

(On Diff #65977)

Moving this inside Legal seems orthogonal to this patch, if so please split this part out and commit.

Right. Will do.

If you're going to split this out and commit - note that this sequence is what we have the getPointerOperand() helper (that I still want to unify with the 6 others we have throughout the code base...) for.

Right. Shall I go ahead and commit an additional prequel patch that does this unification?

[mssimpso]

Rebased on top of the two (yet to be committed) NFC's.

The first NFC will move the getPointerOperand helper and use it throughout LoopVectorize.cpp where appropriate. I'll commit it once Michael gives the go-ahead. The second will move isGatherOrScatterLegal into LoopVectorizationLegality (using the getPointerOperand helper).

Regarding the functional changes, yes I'll includ those in the commit log. They are:

• Marking the pointer operands of interleaved accesses uniform. They're treated as if they're consecutive when vectorizing interleaved groups. We have to collect the interleaved groups before the uniforms now.
• Moving the induction variable logic out of collectValuesToIgnore. IVs and their updates will now only be placed in VecValuesToIgnore if they're uniform. I believe the existing code was there because the IV scalarization logic needed VecValuesToIgnore to decide if a scalar IV was desired. But now, with a clear distinction between uniform and scalar, I think we should move this out. The IVs are handled by isScalarAfterVectorization now.

[mssimpso]

• Moving the induction variable logic out of collectValuesToIgnore. IVs and their updates will now only be placed in VecValuesToIgnore if they're uniform. I believe the existing code was there because the IV scalarization logic needed VecValuesToIgnore to decide if a scalar IV was desired. But now, with a clear distinction between uniform and scalar, think we should move this out. The IVs are handled by isScalarAfterVectorization now.

Matt, however, not just IV scalarization logic needs VecValuesToIgnore, calculateRegisterUsage to compute vector register pressure also needs it. Because IV's live range always spreads across the whole loop body, and it is often promoted to i64 type, it is important to include IV in VecValuesToIgnore if there is no vector version IV.

Thanks,
Wei.

Yes, calculuateRegisterUsage uses VecValuesToIgnore. But if we scalarize an induction variable that isn't uniform, we will still create a value for it corresponding to every iteration of the original scalar loop. For example,

%index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
%3 = or i64 %index, 1
%4 = or i64 %index, 2
%5 = or i64 %index, 3
...
%10 = getelementptr inbounds %pair.i16, %pair.i16* %p, i64 %index, i32 1
%11 = getelementptr inbounds %pair.i16, %pair.i16* %p, i64 %3, i32 1
%12 = getelementptr inbounds %pair.i16, %pair.i16* %p, i64 %4, i32 1
%13 = getelementptr inbounds %pair.i16, %pair.i16* %p, i64 %5, i32 1

Do we not want to consider the ORs in calculateRegisterUsage (or am I misunderstanding the purpose of this function)? Even so, if the GEPs aren't added to VecValuesToIgnore in this case (they're not), why should we add the IV?

[mssimpso]

Wei,

I should've also mentioned that the uniform scalar IVs will still be placed in VecValuesToIgnore. The non-uniform scalar IVs will not. I tried to clarify the distinction in the comment above collectLoopUniforms.

Matt.

[anemet]

lib/Transforms/Vectorize/LoopVectorize.cpp

6356–6360 ↗

(On Diff #66125)

This is essentially LGTM now (assuming that @wmi an @mkuper are happy too) and I am only wondering about test-coverage now and that the patch really only changes the described functionality.

1. Do we already have test-coverage for this in the original version?

2. Did you try to perf-test this patch or in combination with some other patches? The new version is way better and we can actually reason about what's going on (thank you!) but want to make sure that we didn't miss anything.

Thanks for your work!

[mssimpso]

lib/Transforms/Vectorize/LoopVectorize.cpp

6356–6360 ↗

(On Diff #66125)

Thanks Adam!

Do we already have test-coverage for this in the original version?

We have the existing induction variable scalarization tests, which all continue to pass. Previously, we relied on the IVs being in VecValuesToIgnore. Beyond that we have at least one register usage test (X86), which continues to pass. calculateRegisterUsage also relies on VecValuesToIgnore.

Did you try to perf-test this patch or in combination with some other patches?

Yes, I tested this patch together with D22869 on spec2006 and spec2000 (LTO, Kryo). I saw small improvements in several benchmarks with no non-noise regressions. The most significant improvements were in spec2006/h264ref and spec2000/mesa and were on the order of 1-2%.

[mssimpso]

lib/Transforms/Vectorize/LoopVectorize.cpp

6356–6360 ↗

(On Diff #66125)

I should have also pointed out to everyone for further clarity that the code I removed here was already (mostly) duplicated. Over in collectLoopUniforms, we mark IVs uniform if they or their updates are only used by uniforms. Thus, here in collectValuesToIgnore, the uniform IVs would have already been added to VecValuesToIgnore (line 6269).

The functional change here is that now we are not adding to VecValuesToIgnore the non-uniform IVs that are used by non-consecutive pointers. This makes sense to me, as I mentioned in my reply to Wei, since we will still create a scalar value for such IVs corresponding to every iteration of the original scalar loop.

[wmi]

Yes, calculuateRegisterUsage uses VecValuesToIgnore. But if we scalarize an induction variable that isn't uniform, we will still create a value for it corresponding to every iteration of the original scalar loop. For example,

%index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
%3 = or i64 %index, 1
%4 = or i64 %index, 2
%5 = or i64 %index, 3
...
%10 = getelementptr inbounds %pair.i16, %pair.i16* %p, i64 %index, i32 1
%11 = getelementptr inbounds %pair.i16, %pair.i16* %p, i64 %3, i32 1
%12 = getelementptr inbounds %pair.i16, %pair.i16* %p, i64 %4, i32 1
%13 = getelementptr inbounds %pair.i16, %pair.i16* %p, i64 %5, i32 1

Do we not want to consider the ORs in calculateRegisterUsage (or am I misunderstanding the purpose of this function)? Even so, if the GEPs aren't added to VecValuesToIgnore in this case (they're not), why should we add the IV?

There are two factors here:

1. Now calculateRegisterUsage only considers the pressure of vector register, not scalar register. TTI.getNumberOfRegisters only returns vector register number. Scalar register pressure is not modeled in loop vectorization.
2. induction variable has larger impact on register pressure than ORs above, it has live range across the loop while ORs generated have limited live range. If we don't add iv to VecValuesToIgnore, it may involve some impact from scalar register pressure increase into consideration, but it will definitely pessimize the maximum vector register pressure.

I think it is also better to add GEP to VecValuesToIgnore too for non-consecutive memory access case. although GEP has less impact on vector register pressure than iv.

Thanks,
Wei.

[anemet]

LGTM but please wait for the other reviewers.

[mssimpso]

In D22867#500844, @wmi wrote:

There are two factors here:

1. Now calculateRegisterUsage only considers the pressure of vector register, not scalar register. TTI.getNumberOfRegisters only returns vector register number. Scalar register pressure is not modeled in loop vectorization.

This doesn't make sense to me. We use register pressure when deciding to unroll, and we surely do that when we're not vectorizing (VF = 1). I believe TTI.getNumberOfRegisters(true) is what returns the number of vector registers, but in a quick scan of calculateRegisterUsage it doesn't even look like we consider this. I think we just count the number of live intervals. Am I missing something?

2. induction variable has larger impact on register pressure than ORs above, it has live range across the loop while ORs generated have limited live range. If we don't add iv to VecValuesToIgnore, it may involve some impact from scalar register pressure increase into consideration, but it will definitely pessimize the maximum vector register pressure.

I think it is also better to add GEP to VecValuesToIgnore too for non-consecutive memory access case. although GEP has less impact on vector register pressure than iv.

It sounds like you're advocating to add values to VecValuesToIgnore if isScalarAfterVectorization is true rather than isUniformAfterVectorization? This would make sense to me if calculateRegisterUsage is only intended to track the pressure of vector registers, but I'm not sure that it is. Can you please clarify?

[mkuper]

First of all, thanks a lot for working on untangling this!

I'll try to restate my understanding of what we should be doing - that I think aligns with Wei's.

We have three types of values:

1. Uniform scalar - every value for which we generate a single scalar - the primary IV, base pointer for consecutive pointer values, etc.
2. Non-uniform "scalar" - values that are non-uniform, but for which we generate VF scalar values, instead of a single vector. For instance, the "scalar IVs".
3. Non-uniform non-scalar - values that actually get vectorized.

(Perhaps we can adjust the terminology for (2) and (3) - my preference would be to call (3) "vector" and (2) "multi-scalar", but I'm open to other suggestions.)

In any case, as Wei wrote, we need two different groupings:
(a) One for 1 vs. 2 + 3, for operation cost estimation. This is what should go into ValuesNotWidened
(b) The other, for 1 + 2 vs. 3, for vector register pressure estimation.

After this patch we still seem to conflate the two - calculateRegisterUsage() assumes VecValuesToIgnore contains values in groups 3, but it will get 2 + 3.

lib/Transforms/Vectorize/LoopVectorize.cpp

2005 ↗

(On Diff #66125)

Maybe return false early if !ScalarInd ?
There's no need to compute ScalarIndUpdate in that case, is there?

[mkuper]

In D22867#500889, @mssimpso wrote:

In D22867#500844, @wmi wrote:

There are two factors here:

1. Now calculateRegisterUsage only considers the pressure of vector register, not scalar register. TTI.getNumberOfRegisters only returns vector register number. Scalar register pressure is not modeled in loop vectorization.

This doesn't make sense to me. We use register pressure when deciding to unroll, and we surely do that when we're not vectorizing (VF = 1). I believe TTI.getNumberOfRegisters(true) is what returns the number of vector registers, but in a quick scan of calculateRegisterUsage it doesn't even look like we consider this. I think we just count the number of live intervals. Am I missing something?

calculateRegisterUsage() will skip values in VecValuesToIgnore when VF > 1. So when we're only unrolling it will estimate scalar register pressure (by counting all live intervals, which are all scalar), but when we're both vectorizing and unrolling, it will estimate vector register pressure (by considering only the live intervals that correspond to values that will actually be vectorized).
I'm not saying this necessarily makes sense, just describing the state of the world.

[mssimpso]

From Wei:

What I mean is only vector register pressure is considered when selectVectorizationFactor. scalar register pressure is only considered in selectInterleaveCount and only when VF==1. When selectVectorizationFactor, scalar register pressure is not considered, so we don't want to count scalarized iv as a live range usage.

All right, I think I can agree with that. I think the confusing part here is that the "meaning" of calculateRegisterUsage seems to be different depending on who calls it.

Yes, calculateRegisterUsage is only intended to track the pressure of vector registers when selectVectorizationFactor. The reason is explained above. Yes, I think it is better to add values to VecValuesToIgnore if isScalarAfterVectorization is true.

Okay. I think we're saying that calcuateRegisterUsage is used to track vector register pressure for vector factor selection, vector register pressure for unrolling (VF > 1), and scalar register pressure for unrolling (VF = 1). It doesn't make a distinction between general purpose and vector registers. So if the loop will have both scalar and vector values, the estimate may be less precise. In that case, I think I agree here. If VF > 1, the intended purpose is to only track the pressure of vector registers, so we should ignore all scalar values.

From Michael:

We have three types of values:

1. Uniform scalar - every value for which we generate a single scalar - the primary IV, base pointer for consecutive pointer values, etc.
2. Non-uniform "scalar" - values that are non-uniform, but for which we generate VF scalar values, instead of a single vector. For instance, the "scalar IVs".
3. Non-uniform non-scalar - values that actually get vectorized.

...

In any case, as Wei wrote, we need two different groupings:
(a) One for 1 vs. 2 + 3, for operation cost estimation. This is what should go into ValuesNotWidened
(b) The other, for 1 + 2 vs. 3, for vector register pressure estimation.

I think I agree, but want to clarify since I removed ValuesNotWidened.

For cost estimation, we will consider (1): isUniformAfterVectorization(), and for register pressure estimation and IV scalarization, we will consider (3): isScalarAfterVectorization. In that case, I think if I replace isUniformAfterVectorization with isScalarAfterVectorization in collectValuesToIgnore, we will all be happy.

lib/Transforms/Vectorize/LoopVectorize.cpp

2005 ↗

(On Diff #66125)

Right, good point! I removed the optimization when trying to make the code easier to read. I'll update the patch.

[mssimpso]

Also, if we use isScalarAfterVectorization in collectValuesToIgnore and for IV scalarization, it probably makes sense to pre-compute this like we do for collectLoopUniforms. I think this will be a little cleaner than passing around ValuesNotWidened as before. I'll update the patch! Thanks for all the feedback.

Matt.

[mssimpso]

Addressed comments from Michael and Wei.

• Use isScalarAfterVectorization in collectValuesToIngore instead of isUniformAfterVectorization
• Precompute isScalarAfterVectorization like we do for isUniformAfterVectorization.

[mkuper]

lib/Transforms/Vectorize/LoopVectorize.cpp

1539 ↗

(On Diff #66168)

represted -> represented.

4955 ↗

(On Diff #66168)

This is still not quite right.
getUniformPtr() doesn't actually return a pointer if I has a uniform pointer argument. It does for the consecutive and interleaved case, but not for "real" scalar loop-invariant uniform pointers (e.g. a load from a global) - that is, uniform in the Legal->isUniform() sense.

Have I already thanked you for untangling this? :-)

[mssimpso]

lib/Transforms/Vectorize/LoopVectorize.cpp

1539 ↗

(On Diff #66168)

Thanks.

4955 ↗

(On Diff #66168)

Good point. Actually, given the smallness of the change here (just adding the interleaved case), I'm thinking it might make sense to move getUniformPtr back inside collectLoopUniforms, with the appropriate updates to the comments. There's probably value in avoiding creating additional uses of the term "uniform".

[mssimpso]

Addressed Michael's comments.

• Fixed spelling mistake.
• Moved getUniformPtr functionality inside collectLoopUniforms to avoid creating further "uniform" confusion.
• Updated summary to reflect functional changes.

[mkuper]

LGTM

[wmi]

LGTM. Thanks for the great untangle work!

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

public:
 
   // Perform the actual loop widening (vectorization).
   // MinimumBitWidths maps scalar integer values to the smallest bitwidth they
   // can be validly truncated to. The cost model has assumed this truncation
   // will happen when vectorizing. VecValuesToIgnore contains scalar values
   // that the cost model has chosen to ignore because they will not be
   // vectorized.
   void vectorize(LoopVectorizationLegality *L,
-                 const MapVector<Instruction *, uint64_t> &MinimumBitWidths,
-                 SmallPtrSetImpl<const Value *> &VecValuesToIgnore) {
+                 const MapVector<Instruction *, uint64_t> &MinimumBitWidths) {
     MinBWs = &MinimumBitWidths;
-    ValuesNotWidened = &VecValuesToIgnore;
     Legal = L;
     // Create a new empty loop. Unlink the old loop and connect the new one.
     createEmptyLoop();
     // Widen each instruction in the old loop to a new one in the new loop.
     // Use the Legality module to find the induction and reduction variables.
     vectorizeLoop();
   }
 
protected:
   /// Trip count of the widened loop (TripCount - TripCount % (VF*UF))
   Value *VectorTripCount;
 
   /// Map of scalar integer values to the smallest bitwidth they can be legally
   /// represented as. The vector equivalents of these values should be truncated
   /// to this type.
   const MapVector<Instruction *, uint64_t> *MinBWs;
 
-  /// A set of values that should not be widened. This is taken from
-  /// VecValuesToIgnore in the cost model.
-  SmallPtrSetImpl<const Value *> *ValuesNotWidened;
-
   LoopVectorizationLegality *Legal;
 
   // Record whether runtime checks are added.
   bool AddedSafetyChecks;
 };
 
 class InnerLoopUnroller : public InnerLoopVectorizer {
 public:
public:
   /// 0 - Stride is unknown or non-consecutive.
   /// 1 - Address is consecutive.
   /// -1 - Address is consecutive, and decreasing.
   int isConsecutivePtr(Value *Ptr);
 
   /// Returns true if the value V is uniform within the loop.
   bool isUniform(Value *V);
 
-  /// Returns true if this instruction will remain scalar after vectorization.
+  /// Returns true if \p I is known to be uniform after vectorization.
   bool isUniformAfterVectorization(Instruction *I) { return Uniforms.count(I); }
 
+  /// Returns true if \p I is known to be scalar after vectorization.
+  bool isScalarAfterVectorization(Instruction *I) { return Scalars.count(I); }
+
   /// Returns the information that we collected about runtime memory check.
   const RuntimePointerChecking *getRuntimePointerChecking() const {
     return LAI->getRuntimePointerChecking();
   }
 
   const LoopAccessInfo *getLAI() const { return LAI; }
 
   /// \brief Check if \p Instr belongs to any interleaved access group.
private:
   /// legal to vectorize the code, considering only memory constrains.
   /// Returns true if the loop is vectorizable
   bool canVectorizeMemory();
 
   /// Return true if we can vectorize this loop using the IF-conversion
   /// transformation.
   bool canVectorizeWithIfConvert();
 
-  /// Collect the variables that need to stay uniform after vectorization.
+  /// Collect the instructions that are uniform after vectorization. An
+  /// instruction is uniform if we represent it with a single scalar value in
+  /// the vectorized loop corresponding to each vector iteration. Examples of
+  /// uniform instructions include pointer operands of consecutive or
+  /// interleaved memory accesses. Note that although uniformity implies an
+  /// instruction will be scalar, the reverse is not true. In general, a
+  /// scalarized instruction will be represented by VF scalar values in the
+  /// vectorized loop, each corresponding to an iteration of the original
+  /// scalar loop.
   void collectLoopUniforms();
 
+  /// Collect the instructions that are scalar after vectorization. An
+  /// instruction is scalar if it is known to be uniform or will be scalarized
+  /// during vectorization. Non-uniform scalarized instructions will be
+  /// represented by VF values in the vectorized loop, each corresponding to an
+  /// iteration of the original scalar loop.
+  void collectLoopScalars();
+
   /// Return true if all of the instructions in the block can be speculatively
   /// executed. \p SafePtrs is a list of addresses that are known to be legal
   /// and we know that we can read from them without segfault.
   bool blockCanBePredicated(BasicBlock *BB, SmallPtrSetImpl<Value *> &SafePtrs);
 
   /// Updates the vectorization state by adding \p Phi to the inductions list.
   /// This can set \p Phi as the main induction of the loop if \p Phi is a
   /// better choice for the main induction than the existing one.
private:
   /// Holds the phi nodes that are first-order recurrences.
   RecurrenceSet FirstOrderRecurrences;
   /// Holds the widest induction type encountered.
   Type *WidestIndTy;
 
   /// Allowed outside users. This holds the induction and reduction
   /// vars which can be accessed from outside the loop.
   SmallPtrSet<Value *, 4> AllowedExit;
-  /// This set holds the variables which are known to be uniform after
-  /// vectorization.
+
+  /// Holds the instructions known to be uniform after vectorization.
   SmallPtrSet<Instruction *, 4> Uniforms;
 
+  /// Holds the instructions known to be scalar after vectorization.
+  SmallPtrSet<Instruction *, 4> Scalars;
+
   /// Can we assume the absence of NaNs.
   bool HasFunNoNaNAttr;
 
   /// Vectorization requirements that will go through late-evaluation.
   LoopVectorizationRequirements *Requirements;
 
   /// Used to emit an analysis of any legality issues.
   LoopVectorizeHints *Hints;
void InnerLoopVectorizer::widenIntInduction(PHINode *IV, VectorParts &Entry,
   // get it now.
   if (ID.getConstIntStepValue())
     Step = ID.getConstIntStepValue();
 
   // 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 (VF > 1 && IV->getType() == Induction->getType() && Step &&
-      !ValuesNotWidened->count(IV))
+      !Legal->isScalarAfterVectorization(IV))
     return createVectorIntInductionPHI(ID, Entry, TruncType);
 
   // The scalar value to broadcast. This will be derived from the canonical
   // induction variable.
   Value *ScalarIV = nullptr;
 
   // Define the scalar induction variable and step values. If we were given a
   // truncation type, truncate the canonical induction variable and constant
for (unsigned Part = 0; Part < UF; ++Part)
     Entry[Part] = getStepVector(Broadcasted, VF * Part, Step);
 
   // If an induction variable is only used for counting loop iterations or
   // calculating addresses, it doesn't need to be widened. 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.
-  if (VF > 1 && ValuesNotWidened->count(IV)) {
+  if (VF > 1 && Legal->isScalarAfterVectorization(IV)) {
     auto *EntryVal = Trunc ? cast<Value>(Trunc) : IV;
     buildScalarSteps(ScalarIV, Step, EntryVal);
   }
 }
 
 Value *InnerLoopVectorizer::getStepVector(Value *Val, int StartIdx, Value *Step,
                                           Instruction::BinaryOps BinOp) {
   // Create and check the types.
bool LoopVectorizationLegality::canVectorize() {
   }
 
   // Go over each instruction and look at memory deps.
   if (!canVectorizeMemory()) {
     DEBUG(dbgs() << "LV: Can't vectorize due to memory conflicts\n");
     return false;
   }
 
-  // Collect all of the variables that remain uniform after vectorization.
-  collectLoopUniforms();
-
   DEBUG(dbgs() << "LV: We can vectorize this loop"
                << (LAI->getRuntimePointerChecking()->Need
                        ? " (with a runtime bound check)"
                        : "")
                << "!\n");
 
   bool UseInterleaved = TTI->enableInterleavedAccessVectorization();
 
   // If an override option has been passed in for interleaved accesses, use it.
   if (EnableInterleavedMemAccesses.getNumOccurrences() > 0)
     UseInterleaved = EnableInterleavedMemAccesses;
 
   // Analyze interleaved memory accesses.
   if (UseInterleaved)
     InterleaveInfo.analyzeInterleaving(*getSymbolicStrides());
 
+  // Collect all instructions that are known to be uniform after vectorization.
+  collectLoopUniforms();
+
+  // Collect all instructions that are known to be scalar after vectorization.
+  collectLoopScalars();
+
   unsigned SCEVThreshold = VectorizeSCEVCheckThreshold;
   if (Hints->getForce() == LoopVectorizeHints::FK_Enabled)
     SCEVThreshold = PragmaVectorizeSCEVCheckThreshold;
 
   if (PSE.getUnionPredicate().getComplexity() > SCEVThreshold) {
     emitAnalysis(VectorizationReport()
                  << "Too many SCEV assumptions need to be made and checked "
                  << "at runtime");
bool LoopVectorizationLegality::canVectorizeInstrs() {
   // is the same size. If it's not, unset it here and InnerLoopVectorizer
   // will create another.
   if (Induction && WidestIndTy != Induction->getType())
     Induction = nullptr;
 
   return true;
 }
 
+void LoopVectorizationLegality::collectLoopScalars() {
+
+  // If an instruction is uniform after vectorization, it will remain scalar.
+  Scalars.insert(Uniforms.begin(), Uniforms.end());
+
+  // Collect the getelementptr instructions that will not be vectorized. A
+  // getelementptr instruction is only vectorized if it is used for a legal
+  // gather or scatter operation.
+  for (auto *BB : TheLoop->blocks())
+    for (auto &I : *BB) {
+      if (auto *GEP = dyn_cast<GetElementPtrInst>(&I)) {
+        Scalars.insert(GEP);
+        continue;
+      }
+      auto *Ptr = getPointerOperand(&I);
+      if (!Ptr)
+        continue;
+      auto *GEP = getGEPInstruction(Ptr);
+      if (GEP && isLegalGatherOrScatter(&I))
+        Scalars.erase(GEP);
+    }
+
+  // An induction variable will remain scalar if all users of the induction
+  // variable and induction variable update remain scalar.
+  auto *Latch = TheLoop->getLoopLatch();
+  for (auto &Induction : *getInductionVars()) {
+    auto *Ind = Induction.first;
+    auto *IndUpdate = cast<Instruction>(Ind->getIncomingValueForBlock(Latch));
+
+    // Determine if all users of the induction variable are scalar after
+    // vectorization.
+    auto ScalarInd = all_of(Ind->users(), [&](User *U) -> bool {
+      auto *I = cast<Instruction>(U);
+      return I == IndUpdate || !TheLoop->contains(I) || Scalars.count(I);
+    });
+    if (!ScalarInd)
+      continue;
+
+    // Determine if all users of the induction variable update instruction are
+    // scalar after vectorization.
+    auto ScalarIndUpdate = all_of(IndUpdate->users(), [&](User *U) -> bool {
+      auto *I = cast<Instruction>(U);
+      return I == Ind || !TheLoop->contains(I) || Scalars.count(I);
+    });
+    if (!ScalarIndUpdate)
+      continue;
+
+    // The induction variable and its update instruction will remain scalar.
+    Scalars.insert(Ind);
+    Scalars.insert(IndUpdate);
+  }
+}
+
 void LoopVectorizationLegality::collectLoopUniforms() {
   // We now know that the loop is vectorizable!
   // Collect variables that will remain uniform after vectorization.
 
   // If V is not an instruction inside the current loop, it is a Value
   // outside of the scope which we are interesting in.
   auto isOutOfScope = [&](Value *V) -> bool {
     Instruction *I = dyn_cast<Instruction>(V);
     return (!I || !TheLoop->contains(I));
   };
 
   SetVector<Instruction *> Worklist;
   BasicBlock *Latch = TheLoop->getLoopLatch();
   // Start with the conditional branch.
   if (!isOutOfScope(Latch->getTerminator()->getOperand(0))) {
     Instruction *Cmp = cast<Instruction>(Latch->getTerminator()->getOperand(0));
     Worklist.insert(Cmp);
     DEBUG(dbgs() << "LV: Found uniform instruction: " << *Cmp << "\n");
   }
 
-  // Also add all consecutive pointer values; these values will be uniform
-  // after vectorization (and subsequent cleanup).
-  for (auto *BB : TheLoop->blocks()) {
+  // Add all consecutive pointer values; these values will be uniform after
+  // vectorization (and subsequent cleanup). Although non-consecutive, we also
+  // add the pointer operands of interleaved accesses since they are treated
+  // like consecutive pointers during vectorization.
+  for (auto *BB : TheLoop->blocks())
     for (auto &I : *BB) {
-      if (I.getType()->isPointerTy() && isConsecutivePtr(&I)) {
-        Worklist.insert(&I);
-        DEBUG(dbgs() << "LV: Found uniform instruction: " << I << "\n");
-      }
-    }
+      Instruction *Ptr = nullptr;
+      if (I.getType()->isPointerTy() && isConsecutivePtr(&I))
+        Ptr = &I;
+      else if (isAccessInterleaved(&I))
+        Ptr = cast<Instruction>(getPointerOperand(&I));
+      else
+        continue;
+      Worklist.insert(Ptr);
+      DEBUG(dbgs() << "LV: Found uniform instruction: " << *Ptr << "\n");
     }
 
   // Expand Worklist in topological order: whenever a new instruction
   // is added , its users should be either already inside Worklist, or
   // out of scope. It ensures a uniform instruction will only be used
   // by uniform instructions or out of scope instructions.
   unsigned idx = 0;
   while (idx != Worklist.size()) {
     Instruction *I = Worklist[idx++];
void LoopVectorizationCostModel::collectValuesToIgnore() {
   // Ignore type-promoting instructions we identified during reduction
   // detection.
   for (auto &Reduction : *Legal->getReductionVars()) {
     RecurrenceDescriptor &RedDes = Reduction.second;
     SmallPtrSetImpl<Instruction *> &Casts = RedDes.getCastInsts();
     VecValuesToIgnore.insert(Casts.begin(), Casts.end());
   }
 
-  // Insert uniform instruction into VecValuesToIgnore.
-  // Collect non-gather/scatter and non-consecutive ptr in NonConsecutivePtr.
-  SmallPtrSet<Instruction *, 8> NonConsecutivePtr;
-  for (auto *BB : TheLoop->getBlocks()) {
-    for (auto &I : *BB) {
-      if (Legal->isUniformAfterVectorization(&I))
+  // Insert values known to be scalar into VecValuesToIgnore.
+  for (auto *BB : TheLoop->getBlocks())
+    for (auto &I : *BB)
+      if (Legal->isScalarAfterVectorization(&I))
         VecValuesToIgnore.insert(&I);
-      Instruction *PI = dyn_cast_or_null<Instruction>(getPointerOperand(&I));
-      if (PI && !Legal->isConsecutivePtr(PI) &&
-          !Legal->isLegalGatherOrScatter(&I))
-        NonConsecutivePtr.insert(PI);
-    }
-  }
-
-  // Ignore induction phis that are either used in uniform instructions or
-  // NonConsecutivePtr.
-  for (auto &Induction : *Legal->getInductionVars()) {
-    auto *PN = Induction.first;
-    auto *UpdateV = PN->getIncomingValueForBlock(TheLoop->getLoopLatch());
-
-    if (std::all_of(PN->user_begin(), PN->user_end(),
-                    [&](User *U) -> bool {
-                      Instruction *UI = dyn_cast<Instruction>(U);
-                      return U == UpdateV || !TheLoop->contains(UI) ||
-                             Legal->isUniformAfterVectorization(UI) ||
-                             NonConsecutivePtr.count(UI);
-                    }) &&
-        std::all_of(UpdateV->user_begin(), UpdateV->user_end(),
-                    [&](User *U) -> bool {
-                      Instruction *UI = dyn_cast<Instruction>(U);
-                      return U == PN || !TheLoop->contains(UI) ||
-                             Legal->isUniformAfterVectorization(UI) ||
-                             NonConsecutivePtr.count(UI);
-                    })) {
-      VecValuesToIgnore.insert(PN);
-      VecValuesToIgnore.insert(UpdateV);
-    }
-  }
 }
 
 void InnerLoopUnroller::scalarizeInstruction(Instruction *Instr,
                                              bool IfPredicateStore) {
   assert(!Instr->getType()->isAggregateType() && "Can't handle vectors");
   // Holds vector parameters or scalars, in case of uniform vals.
   SmallVector<VectorParts, 4> Params;
 
if (!VectorizeLoop && !InterleaveLoop) {
     DEBUG(dbgs() << "LV: Interleave Count is " << IC << '\n');
   }
 
   if (!VectorizeLoop) {
     assert(IC > 1 && "interleave count should not be 1 or 0");
     // If we decided that it is not legal to vectorize the loop, then
     // interleave it.
     InnerLoopUnroller Unroller(L, PSE, LI, DT, TLI, TTI, AC, ORE, IC);
-    Unroller.vectorize(&LVL, CM.MinBWs, CM.VecValuesToIgnore);
+    Unroller.vectorize(&LVL, CM.MinBWs);
 
     ORE->emitOptimizationRemark(LV_NAME, L,
                                 Twine("interleaved loop (interleaved count: ") +
                                     Twine(IC) + ")");
   } else {
     // If we decided that it is *legal* to vectorize the loop, then do it.
     InnerLoopVectorizer LB(L, PSE, LI, DT, TLI, TTI, AC, ORE, VF.Width, IC);
-    LB.vectorize(&LVL, CM.MinBWs, CM.VecValuesToIgnore);
+    LB.vectorize(&LVL, CM.MinBWs);
     ++LoopsVectorized;
 
     // Add metadata to disable runtime unrolling a scalar loop when there are
     // no runtime checks about strides and memory. A scalar loop that is
     // rarely used is not worth unrolling.
     if (!LB.areSafetyChecksAdded())
       AddRuntimeUnrollDisableMetaData(L);
 

llvm/trunk/test/Transforms/LoopVectorize/induction.ll

for.body:
   %i.next = add nuw nsw i64 %i, 1
   %cond = icmp slt i64 %i.next, %n
   br i1 %cond, label %for.body, label %for.end
 
 for.end:
   ret void
 }
 
+; Make sure we scalarize the step vectors used for the pointer arithmetic. We
+; can't easily simplify vectorized step vectors. (Interleaved accesses.)
+;
+; for (int i = 0; i < n; ++i)
+;   p[i].f = a[i * 4]
+;
+; INTERLEAVE-LABEL: @scalarize_induction_variable_04(
+; INTERLEAVE: vector.body:
+; INTERLEAVE:   %[[i0:.+]] = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
+; INTERLEAVE:   %[[i1:.+]] = or i64 %[[i0]], 1
+; INTERLEAVE:   %[[i2:.+]] = or i64 %[[i0]], 2
+; INTERLEAVE:   %[[i3:.+]] = or i64 %[[i0]], 3
+; INTERLEAVE:   %[[i4:.+]] = or i64 %[[i0]], 4
+; INTERLEAVE:   %[[i5:.+]] = or i64 %[[i0]], 5
+; INTERLEAVE:   %[[i6:.+]] = or i64 %[[i0]], 6
+; INTERLEAVE:   %[[i7:.+]] = or i64 %[[i0]], 7
+; INTERLEAVE:   getelementptr inbounds %pair, %pair* %p, i64 %[[i0]], i32 1
+; INTERLEAVE:   getelementptr inbounds %pair, %pair* %p, i64 %[[i1]], i32 1
+; INTERLEAVE:   getelementptr inbounds %pair, %pair* %p, i64 %[[i2]], i32 1
+; INTERLEAVE:   getelementptr inbounds %pair, %pair* %p, i64 %[[i3]], i32 1
+; INTERLEAVE:   getelementptr inbounds %pair, %pair* %p, i64 %[[i4]], i32 1
+; INTERLEAVE:   getelementptr inbounds %pair, %pair* %p, i64 %[[i5]], i32 1
+; INTERLEAVE:   getelementptr inbounds %pair, %pair* %p, i64 %[[i6]], i32 1
+; INTERLEAVE:   getelementptr inbounds %pair, %pair* %p, i64 %[[i7]], i32 1
+
+define void @scalarize_induction_variable_04(i32* %a, %pair* %p, i32 %n) {
+entry:
+  br label %for.body
+
+for.body:
+  %i = phi i64 [ %i.next, %for.body ], [ 0, %entry]
+  %0 = shl nsw i64 %i, 2
+  %1 = getelementptr inbounds i32, i32* %a, i64 %0
+  %2 = load i32, i32* %1, align 1
+  %3 = getelementptr inbounds %pair, %pair* %p, i64 %i, i32 1
+  store i32 %2, i32* %3, align 1
+  %i.next = add nuw nsw i64 %i, 1
+  %4 = trunc i64 %i.next to i32
+  %cond = icmp eq i32 %4, %n
+  br i1 %cond, label %for.end, label %for.body
+
+for.end:
+  ret void
+}
+
 ; Make sure that the loop exit count computation does not overflow for i8 and
 ; i16. The exit count of these loops is i8/i16 max + 1. If we don't cast the
 ; induction variable to a bigger type the exit count computation will overflow
 ; to 0.
 ; PR17532
 
 ; CHECK-LABEL: i8_loop
 ; CHECK: icmp eq i32 {{.*}}, 256