Reducing the costs of cast instructions to enable more vectorization of smaller types in LoopVectorize

[samparker]

Summary

Hi,

So I have completely rewritten the patch so that it doesn't use getWidestType and that it searches for clamped values and instructions. I have reversed the search through the loop body so that trunc instructions can be searched up from to the zext/sext nodes, noting smaller type requirements.

Cheers,
Sam

[sbaranga]

Hi Sam,

If I understand correctly, this implementation allows for only s/zext -> op -> trunc chains (with only one operation). Is this correct (or perhaps I'm missing something)? I think in theory it should be possible to have arbitrary long chains, depending on what operations are in them.

-Silviu

lib/Transforms/Vectorize/LoopVectorize.cpp

4519

APInt::getMaxValue(ScalarWidth) should be used as (1 << ScalarWidth) - 1 might return different values depending on the host machine.

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

141

I think this would be cleaner without the metadata.

[samparker]

Hi Silviu,

Yes, that is how is it implemented at the moment and I agree longer chains should be considered. I just wasn't sure what types of nodes it wouldn't be legal for and would welcome suggestions.

Cheers,
sam

[samparker]

Now use SmallPtrSet and ValueMap in place of the standard containers for the instructions and types found by the new function.
Also compare against APInt::getMaxValue as Silviu suggested.
Removed metadata from test file.

[jmolloy]

Hi Sam,

I've given an initial review, but I'm not sure this will catch all the interesting cases.

You don't recurse anywhere, so you only check single operations. For example, you'll miss this:

%1 = zext i32 %a to i64
%2 = add %1, %1
%3 = add %2, %1
%4 = trunc i64 %3 to i32

There are more complex cases it won't catch either, but I'm less worried about that as primarily this comes up with C promotion rules, so everything gets promoted to the same size (i32) which simplifies things somewhat.

Cheers,

James

lib/Transforms/Vectorize/LoopVectorize.cpp

891

This needs doxygen comment style (///) and also a description of what a clamped type is.

895

This needs documentation. Does it assume I is a CastInst?

4379

Whitespace change.

4387

Please add a comment as to why we're reversing through the loop.

4484

There's no need for this to be split over two lines - the "bool" will fit inside the 80 char limit.

4490

"so any extends would have been found earlier." - SPAG and clarification

4491

The canonical way to do this is "if (!isa<TruncInst>(I))"

4492

This can simply be "return FreeCasts.count(I);"

4498

I know it's pedantic, but this comment implies that it was the user's fault that we were called on a non-integer operation. Actually, we just don't deal with them, so I'd suggest rewriting to something like:

"// We only care about integer operations."

4514

Canonical form has local variables as UpperCamelCase.

4516

You can merge this and the next line with:

if (ConstantInst *CI = dyn_cast<ConstantInst>(ChainInst->getOperand(i)))

[samparker]

Chains of instructions are now searched through, with the limitations that they are either an Add, And, Or, Xor, Mul or Shl.
The instructions are saved in a map with their clamped value type and so during vectorization, these types can be used instead.
This is performed by enclosing the binary operations within truncs and zext operations in the hope that these get optimised out.

[jmolloy]

Hi Sam,

Thanks for making this update. I have lots of coding style nits but primarily we need two algorithms changed from being purely recursive to being iterative. They'll still do the same thing just without overflowing the stack on large programs.

Cheers,

James

lib/Transforms/Vectorize/LoopVectorize.cpp

2639

This is recursive, and unboundedly so. This means that with a large function, we may blow the stack.

Instead of recursing, you could change this to be a simple iterative algorithm. Just iterate as you are currently doing, but call visitClampedInstr() for ALL instructions that are clamped, not just TruncInsts.

Store the newly created clamped instructions in a map<Value*,Value*>, and when you're visiting a clamped instruction check the map for each of its operands. If a value exists, we've already visited this - use it. Otherwise insert a cast.

Then, when we hit a trunc instruction, do the replacement (using OldTrunc->replaceAllUsesWith(NewTrunc)) and that'll make the entire tree live.

This will only really work if you visit all instructions in dominator order, so we visit defs before uses. Luckily the caller of this function already finds such an ordering (LoopBlocksDFS), so you can just use that.

4581

This is also unboundedly recursive. But it can be changed into an iterative algorithm.

Instead of searching bottom-up, search top-down. For every instruction (visiting defs before uses, so in LoopBlocksDFS order!), check if it is narrow. That's easy because you just need to check its immediate operands. If so, store it.

Because we visit all instructions, and we visit all defs before uses, any single isNarrowInstruction() call only needs to check its immediate operands - it doesn't need to go crawling through a tree. This removes the recursion and makes for a more elegant algorithm.

[mzolotukhin]

Hi Sam,

Some initial comments from me inline:

lib/Transforms/Vectorize/LoopVectorize.cpp

952–953

Please add a comment that the key in this map is VectorizationFactor.

2601–2602

Should it be if(Clamped != *II) ? Since Clamped originally is just an operand of I, this condition is almost always true, or am I missing something?

2612

Is it used anywhere?

4149

Please remove this unneeded change.

4478–4480

Please reword the comment so that it doesn't refer to the previous version: e.g. instead of "This has been reversed.." use something like "iterate in reverse order because..".
In the current form the comment makes sense in the context of the patch, but it would look a bit strange when you don't see the context.

4481

Maybe use auto here?

4484

This change looks strange. Is it correct at all?

4850–4851

else if should be on the same line as }.
Actually, you could just run clang-format on the patch to avoid such issues.

[samparker]

I have changed the algorithms so that they are not recursive. The first pass checks all the instructions top-down and assigns a potential (TBC) narrow type. The second pass then searches bottom up from truncs to confirm, or adjust, the narrow type. I've also added support for sub, ashr and lshr instructions, but would really appreciate my logic being confirmed.

[sbaranga]

Hi Sam,

Some comments from me inline.

Cheers,
Silviu

lib/Transforms/Vectorize/LoopVectorize.cpp

1212

I think the name "TBCNarrowInstrs" is potentially confusing. Maybe TBC -> Candidate?

5236

Why use inline here? I would normally trust the compiler to do the right thing.

5298

The check for sub could potentially be removed, but it depends on exactly what we're checking for.
It would be interesting to have an example where sub is an issue that would prevent the narrowing.

5309

The comment says "logical shifts" but the code also allows ashr? Is this correct?

5386

It would be a good idea to have a comment that explains how these were chosen, and why some of them need extra checking.

5420

Why consider here only narrowing to i8 or i16? Would narrowing from i64 to i32 also make sense?

[samparker]

Hi Silviu,

So i've added some comments for clarification and also removed the sub operands from the chains for simplicity as I didn't notice any performance difference in the tests I was looking at. I've also added support for 64-bit > 32-bit operations and updated the test file to reflect this.

cheers,

[sbaranga]

In D9822#201852, @samparker wrote:

Hi Silviu,

So i've added some comments for clarification and also removed the sub operands from the chains for simplicity as I didn't notice any performance difference in the tests I was looking at. I've also added support for 64-bit > 32-bit operations and updated the test file to reflect this.

cheers,

Thanks Sam!

Some further comments:

Subtraction is a very common operation, it would be much nicer to get it now. wrt performance numbers this would only show up in a benchmark if it would affect the hot loop _and_ the loop would end up being vectorized.

Looking at what bits we don't care about seems like the right approach to me. I think an easier way to reason about these is to have a bitmask for each value in the chain that we're looking at, indicating what bits we care about. Different operations would do different things on this bitmask, and we would compute the value of the bitmasks starting from the trunc operations.

For example:

b = add a, c means that a and c have the same bitmask as b

The same would be true for mul, left shift, all bitwise operators, and sub (since sub can be written with and add and a not).

b = shr a, 2,  and b has a bitmask of 0b00011 ( where 1 means we care, 0 don't care) means a has a bitmask of 0b01111 (technically it would be 0b01100, but this is an approximation).

This can probably be done for most operators.

Also, if you have an operation that takes a constant and you know what bits you care about it should be perfectly legal to truncate the constant and get rid of some of the bits that you don't care about.

Technically, we could set the mask values on the truncate operations and iterate using a work list until all bitmasks have converged, but that is best left for future work.

What would be your opinion on this?

Cheers,
Silviu

[samparker]

In D9822#202874, @sbaranga wrote:

In D9822#201852, @samparker wrote:

Hi Silviu,

So i've added some comments for clarification and also removed the sub operands from the chains for simplicity as I didn't notice any performance difference in the tests I was looking at. I've also added support for 64-bit > 32-bit operations and updated the test file to reflect this.

cheers,

Thanks Sam!

Some further comments:

Subtraction is a very common operation, it would be much nicer to get it now. wrt performance numbers this would only show up in a benchmark if it would affect the hot loop _and_ the loop would end up being vectorized.

Looking at what bits we don't care about seems like the right approach to me. I think an easier way to reason about these is to have a bitmask for each value in the chain that we're looking at, indicating what bits we care about. Different operations would do different things on this bitmask, and we would compute the value of the bitmasks starting from the trunc operations.

For example:

b = add a, c means that a and c have the same bitmask as b

The same would be true for mul, left shift, all bitwise operators, and sub (since sub can be written with and add and a not).

b = shr a, 2,  and b has a bitmask of 0b00011 ( where 1 means we care, 0 don't care) means a has a bitmask of 0b01111 (technically it would be 0b01100, but this is an approximation).

This can probably be done for most operators.

Also, if you have an operation that takes a constant and you know what bits you care about it should be perfectly legal to truncate the constant and get rid of some of the bits that you don't care about.

Technically, we could set the mask values on the truncate operations and iterate using a work list until all bitmasks have converged, but that is best left for future work.

What would be your opinion on this?

Cheers,
Silviu

Hey Silviu,

I believe this is the technique that James had told me about and mentioned that it had already been implemented somewhere in the code base, but without an interface. I didn't go for it originally because I didn't what the ramp up time of trying to understand, refactor and modify two separate passes and I'm still concerned about that time factor! The bitmask idea does sound like a much more useful and reusable approach, however I really can't commit the time to implement it, unless you believe it can slot into the current structure of my analysis.

Cheers,

[samparker]

Rebased and corrected some typos. Also removed sext and zext from being nodes that are searched as they will get searched from their users anyway.

[jmolloy]

Hi Sam,

I've got a bunch of typographical changes, but the biggest problem is still the unbounded recursion.

Cheers,

James

lib/Transforms/Vectorize/LoopVectorize.cpp

1170

All these functions should start with a lowercase letter.

3559

I'm confused as to why we need ->getScalarType() here - surely this can't be a vector type by definition, as it hasn't yet been vectorized?

5110

In what case can you get here and one of the types not be an integer?

5122

I think it'd be easier if you just did:

CandidateNarrowInstrs[VF][I] = Largest;

To remove a bunch of useless code.

5125

Braces around else.

5137

Again, use std::map::operator[] rather than ::erase and ::insert.

5198

You're not actually grabbing any value here.

5199

Here and elsewhere: if statements should either be one-liners or multi-liners. Please don't mix one-liners and braces.

if (a)
  b;
else
  c;  // GOOD

if (a) {
  b; c;
} else
  d; // BAD

5203

This is unboundedly recursive.

5245

Please use a switch here.

5264

Capital letter.

[samparker]

lib/Transforms/Vectorize/LoopVectorize.cpp

5203

But isn't the recursion bound by the size of CandiateNarrowInstrs, which is defined during the first pass?

[hfinkel]

lib/Transforms/Vectorize/LoopVectorize.cpp

1182

Line is too long.

5203

What bounds that size?

[samparker]

lib/Transforms/Vectorize/LoopVectorize.cpp

5203

The number of instructions in the loop body, so do I need to add a further more explicit limit?

[hfinkel]

lib/Transforms/Vectorize/LoopVectorize.cpp

5203

Yes, you'd need a more-explicit limit. We can't have a recursion bounded only by the number of instructions in a block, loop, etc.

lib/Transforms/Vectorize/LoopVectorize.cpp

 /// checks, and relies on the caller to check for the different legality
 /// aspects. The InnerLoopVectorizer relies on the
 /// LoopVectorizationLegality class to provide information about the induction
 /// and reduction variables that were found to a given vectorization factor.
 class InnerLoopVectorizer {
 public:
   InnerLoopVectorizer(Loop *OrigLoop, ScalarEvolution *SE, LoopInfo *LI,
                       DominatorTree *DT, const TargetLibraryInfo *TLI,
-                      const TargetTransformInfo *TTI, unsigned VecWidth,
+                      const TargetTransformInfo *TTI,
+                      LoopVectorizationCostModel *CostModel, unsigned VecWidth,
                       unsigned UnrollFactor)
       : OrigLoop(OrigLoop), SE(SE), LI(LI), DT(DT), TLI(TLI), TTI(TTI),
         VF(VecWidth), UF(UnrollFactor), Builder(SE->getContext()),
         Induction(nullptr), OldInduction(nullptr), WidenMap(UnrollFactor),
-        Legal(nullptr), AddedSafetyChecks(false) {}
+        Legal(nullptr), AddedSafetyChecks(false), CM(CostModel) {}
 
   // Perform the actual loop widening (vectorization).
   void vectorize(LoopVectorizationLegality *L) {
     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.
protected:
   /// that the header block of the loop is set to True. It returns the *entry*
   /// mask for the block BB.
   VectorParts createBlockInMask(BasicBlock *BB);
   /// A helper function that computes the predicate of the edge between SRC
   /// and DST.
   VectorParts createEdgeMask(BasicBlock *Src, BasicBlock *Dst);
 
   /// A helper function to vectorize a single BB within the innermost loop.
-  void vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV);
+  void vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV,
+                            LoopVectorizationCostModel *CM, unsigned VF);
 
   /// Vectorize a single PHINode in a block. This method handles the induction
   /// variable canonicalization. It supports both VF = 1 for unrolled loops and
   /// arbitrary length vectors.
   void widenPHIInstruction(Instruction *PN, VectorParts &Entry,
                            unsigned UF, unsigned VF, PhiVector *PV);
 
   /// Insert the new loop to the loop hierarchy and pass manager
protected:
   /// Maps scalars to widened vectors.
   ValueMap WidenMap;
   EdgeMaskCache MaskCache;
 
   LoopVectorizationLegality *Legal;
 
   // Record whether runtime check is added.
   bool AddedSafetyChecks;
+
+  LoopVectorizationCostModel *CM;
 };
 
 class InnerLoopUnroller : public InnerLoopVectorizer {
 public:
   InnerLoopUnroller(Loop *OrigLoop, ScalarEvolution *SE, LoopInfo *LI,
                     DominatorTree *DT, const TargetLibraryInfo *TLI,
-                    const TargetTransformInfo *TTI, unsigned UnrollFactor)
-      : InnerLoopVectorizer(OrigLoop, SE, LI, DT, TLI, TTI, 1, UnrollFactor) {}
+                    const TargetTransformInfo *TTI,
+                    LoopVectorizationCostModel *CostModel,
+                    unsigned UnrollFactor)
+      : InnerLoopVectorizer(OrigLoop, SE, LI, DT, TLI, TTI, CostModel, 1,
+                            UnrollFactor) {}
 
 private:
   void scalarizeInstruction(Instruction *Instr,
                             bool IfPredicateStore = false) override;
   void vectorizeMemoryInstruction(Instruction *Instr) override;
   Value *getBroadcastInstrs(Value *V) override;
   Value *getStepVector(Value *Val, int StartIdx, Value *Step) override;
   Value *reverseVector(Value *Vec) override;
public:
   };
 
   /// ReductionList contains the reduction descriptors for all
   /// of the reductions that were found in the loop.
   typedef DenseMap<PHINode *, RecurrenceDescriptor> ReductionList;
 
   /// InductionList saves induction variables and maps them to the
   /// induction descriptor.
   typedef MapVector<PHINode*, InductionInfo> InductionList;
 
   /// Returns true if it is legal to vectorize this loop.
   /// This does not mean that it is profitable to vectorize this
   /// loop, only that it is legal to do so.
   bool canVectorize();
 
   /// Returns the Induction variable.
   PHINode *getInduction() { return Induction; }
 
   /// Returns the reduction variables found in the loop.
   ReductionList *getReductionVars() { return &Reductions; }
 
bool isAccessInterleaved(Instruction *Instr) {
     return InterleaveInfo.isInterleaved(Instr);
   }
 
   /// \brief Get the interleaved access group that \p Instr belongs to.
   const InterleaveGroup *getInterleavedAccessGroup(Instruction *Instr) {
     return InterleaveInfo.getInterleaveGroup(Instr);
   }
 
   unsigned getMaxSafeDepDistBytes() { return LAI->getMaxSafeDepDistBytes(); }
 
   bool hasStride(Value *V) { return StrideSet.count(V); }
   bool mustCheckStrides() { return !StrideSet.empty(); }
   SmallPtrSet<Value *, 8>::iterator strides_begin() {
     return StrideSet.begin();
   }
   SmallPtrSet<Value *, 8>::iterator strides_end() { return StrideSet.end(); }
 
   /// Returns true if the target machine supports masked store operation
struct RegisterUsage {
     unsigned MaxLocalUsers;
     /// Holds the number of instructions in the loop.
     unsigned NumInstructions;
   };
 
   /// \return  information about the register usage of the loop.
   RegisterUsage calculateRegisterUsage();
 
+  /// \return A map of instructions that can be used with smaller types.
+  std::map<Instruction*, Type*>& getNarrowInstrs(unsigned VF) {
+    return NarrowInstrs[VF];
+  }
+
 private:
   /// Returns the expected execution cost. The unit of the cost does
   /// not matter because we use the 'cost' units to compare different
   /// vector widths. The cost that is returned is *not* normalized by
   /// the factor width.
   unsigned expectedCost(unsigned VF);
 
+  /// Return the vectorized type or a clamped type that may have been
+  /// previously identified.
+  Type* getClampedVectorTy(Instruction *I, unsigned VF);
+
+  /// Expects a CastInst, returns the destination type that may have been
+  /// calculated to be smaller than before. The cast is free if the function
+  /// returns a nullptr.
+  Type* getAdjustedCastType(Instruction *I, unsigned VF);
+
+  /// Create a pair from I and NarrowTy and insert it into the NarrowInstrs
+  /// map for VF. If a value already exists, the larger NarrowTy remains or is
+  /// inserted in its place.
+  void InsertConfirmedNarrow(Instruction *I, Type *NarrowTy, unsigned VF);
+
+  /// Create a pair from I and NarrowTy and insert it into the CandidateNarrowInstrs
+  /// map for VF. If a value already exists, the larger NarrowTy remains or is
+  /// inserted in its place. Returns false if VectorType::get(NarrowTy, VF) is
+  /// not a legal type.
+  bool TryInsertCandidateNarrow(Instruction *I, Type *NarrowTy, unsigned VF);
+
+  /// Adds I to a map with a smaller type if it is all that it needs. This is
+  /// later confirmed.
+  void MapNarrowInstruction(Instruction *I, unsigned VF);
+
+  /// Use the map of CandidateNarrowInstrs to confirm the usability of smaller types
+  /// for chains of instructions.
+  bool ConfirmNarrowChain(Instruction *I, unsigned VF, Type *NarrowTy);
+
   /// Returns the execution time cost of an instruction for a given vector
   /// width. Vector width of one means scalar.
   unsigned getInstructionCost(Instruction *I, unsigned VF);
 
   /// Returns whether the instruction is a load or store and will be a emitted
   /// as a vector operation.
   bool isConsecutiveLoadOrStore(Instruction *I);
 
private:
 
   /// The loop that we evaluate.
   Loop *TheLoop;
   /// Scev analysis.
   ScalarEvolution *SE;
   /// Loop Info analysis.
   LoopInfo *LI;
   /// Vectorization legality.
   LoopVectorizationLegality *Legal;
   /// Vector target information.
   const TargetTransformInfo &TTI;
   /// Target Library Info.
   const TargetLibraryInfo *TLI;
   const Function *TheFunction;
   // Loop Vectorize Hint.
   const LoopVectorizeHints *Hints;
+
+  // While searching from truncs, we store instructions which can use
+  // smaller types when vectorized.
+  std::map<unsigned, std::map<Instruction*, Type*>> NarrowInstrs;
+  std::map<unsigned, std::map<Instruction*, Type*>> CandidateNarrowInstrs;
 };
 
 /// Utility class for getting and setting loop vectorizer hints in the form
 /// of loop metadata.
 /// This class keeps a number of loop annotations locally (as member variables)
 /// and can, upon request, write them back as metadata on the loop. It will
 /// initially scan the loop for existing metadata, and will update the local
 /// values based on information in the loop.
if (VF.Width == 1) {
       }
       DEBUG(dbgs() << "LV: Trying to at least unroll the loops.\n");
 
       // Report the unrolling decision.
       emitOptimizationRemark(F->getContext(), DEBUG_TYPE, *F, L->getStartLoc(),
                              Twine("interleaved by " + Twine(IC) +
                                    " (vectorization not beneficial)"));
 
-      InnerLoopUnroller Unroller(L, SE, LI, DT, TLI, TTI, IC);
+      InnerLoopUnroller Unroller(L, SE, LI, DT, TLI, TTI, &CM, IC);
       Unroller.vectorize(&LVL);
     } else {
       // If we decided that it is *legal* to vectorize the loop then do it.
-      InnerLoopVectorizer LB(L, SE, LI, DT, TLI, TTI, VF.Width, IC);
+      InnerLoopVectorizer LB(L, SE, LI, DT, TLI, TTI, &CM, VF.Width, IC);
       LB.vectorize(&LVL);
       ++LoopsVectorized;
 
       // Add metadata to disable runtime unrolling scalar loop when there's no
       // runtime check about strides and memory. Because at this situation,
       // scalar loop is rarely used not worthy to be unrolled.
       if (!LB.IsSafetyChecksAdded())
         AddRuntimeUnrollDisableMetaData(L);
void InnerLoopVectorizer::scalarizeInstruction(Instruction *Instr, bool IfPredicateStore) {
 
   assert(Params.size() == Instr->getNumOperands() &&
          "Invalid number of operands");
 
   // Does this instruction return a value ?
   bool IsVoidRetTy = Instr->getType()->isVoidTy();
 
   Value *UndefVec = IsVoidRetTy ? nullptr :
-    UndefValue::get(VectorType::get(Instr->getType(), VF));
   // Create a new entry in the WidenMap and initialize it to Undef or Null.
   VectorParts &VecResults = WidenMap.splat(Instr, UndefVec);
 
   Instruction *InsertPt = Builder.GetInsertPoint();
   BasicBlock *IfBlock = Builder.GetInsertBlock();
   BasicBlock *CondBlock = nullptr;
 
   VectorParts Cond;
void InnerLoopVectorizer::createEmptyLoop() {
   Value *StartIdx = ExtendedIdx =
       OldInduction
           ? Builder.CreateZExt(OldInduction->getIncomingValueForBlock(VectorPH),
                                IdxTy)
           : ConstantInt::get(IdxTy, 0);
 
   // Count holds the overall loop count (N).
   Value *Count = Exp.expandCodeFor(ExitCount, ExitCount->getType(),
                                    VectorPH->getTerminator());
 
   LoopBypassBlocks.push_back(VectorPH);
 
   // Split the single block loop into the two loop structure described above.
   BasicBlock *VecBody =
       VectorPH->splitBasicBlock(VectorPH->getTerminator(), "vector.body");
   BasicBlock *MiddleBlock =
   VecBody->splitBasicBlock(VecBody->getTerminator(), "middle.block");
   BasicBlock *ScalarPH =
   MiddleBlock->splitBasicBlock(MiddleBlock->getTerminator(), "scalar.ph");
 
   // Create and register the new vector loop.
   Loop* Lp = new Loop();
   Loop *ParentLoop = OrigLoop->getParentLoop();
 
   // Insert the new loop into the loop nest and register the new basic blocks
   // before calling any utilities such as SCEV that require valid LoopInfo.
   if (ParentLoop) {
     ParentLoop->addChildLoop(Lp);
void InnerLoopVectorizer::createEmptyLoop() {
 
   // Generate the induction variable.
   setDebugLocFromInst(Builder, getDebugLocFromInstOrOperands(OldInduction));
   Induction = Builder.CreatePHI(IdxTy, 2, "index");
   // The loop step is equal to the vectorization factor (num of SIMD elements)
   // times the unroll factor (num of SIMD instructions).
   Constant *Step = ConstantInt::get(IdxTy, VF * UF);
 
   // Generate code to check that the loop's trip count that we computed by
   // adding one to the backedge-taken count will not overflow.
   BasicBlock *NewVectorPH =
       VectorPH->splitBasicBlock(VectorPH->getTerminator(), "overflow.checked");
   if (ParentLoop)
     ParentLoop->addBasicBlockToLoop(NewVectorPH, *LI);
   ReplaceInstWithInst(
       VectorPH->getTerminator(),
       BranchInst::Create(ScalarPH, NewVectorPH, CheckBCOverflow));
void InnerLoopVectorizer::vectorizeLoop() {
 
   // Scan the loop in a topological order to ensure that defs are vectorized
   // before users.
   LoopBlocksDFS DFS(OrigLoop);
   DFS.perform(LI);
 
   // Vectorize all of the blocks in the original loop.
   for (LoopBlocksDFS::RPOIterator bb = DFS.beginRPO(),
-       be = DFS.endRPO(); bb != be; ++bb)
-    vectorizeBlockInLoop(*bb, &RdxPHIsToFix);
+       be = DFS.endRPO(); bb != be; ++bb) {
+    vectorizeBlockInLoop(*bb, &RdxPHIsToFix, CM, VF);
+  }
 
   // At this point every instruction in the original loop is widened to
   // a vector form. We are almost done. Now, we need to fix the PHI nodes
   // that we vectorized. The PHI nodes are currently empty because we did
   // not want to introduce cycles. Notice that the remaining PHI nodes
   // that we need to fix are reduction variables.
 
   // Create the 'reduced' values for each of the induction vars.
case LoopVectorizationLegality::IK_PtrInduction:
                                                "insert.gep");
         }
         Entry[part] = VecVal;
       }
       return;
   }
 }
 
-void InnerLoopVectorizer::vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV) {
+void InnerLoopVectorizer::vectorizeBlockInLoop(BasicBlock *BB, PhiVector *PV,
+                                               LoopVectorizationCostModel *CM,
+                                               unsigned VF) {
+  auto &ClampedVecTys = CM->getNarrowInstrs(VF);
   // For each instruction in the old loop.
   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
     VectorParts &Entry = WidenMap.get(it);
     switch (it->getOpcode()) {
     case Instruction::Br:
       // Nothing to do for PHIs and BR, since we already took care of the
       // loop control flow instructions.
       continue;
case Instruction::Xor: {
       // Just widen binops.
       BinaryOperator *BinOp = dyn_cast<BinaryOperator>(it);
       setDebugLocFromInst(Builder, BinOp);
       VectorParts &A = getVectorValue(it->getOperand(0));
       VectorParts &B = getVectorValue(it->getOperand(1));
 
       // Use this vector value for all users of the original instruction.
       for (unsigned Part = 0; Part < UF; ++Part) {
-        Value *V = Builder.CreateBinOp(BinOp->getOpcode(), A[Part], B[Part]);
+        Value *APart = A[Part];
+        Value *BPart = B[Part];
+
+        // The CostModel may have identified operations that could be executed
+        // using smaller types, so convert those operations to use them. We do
+        // this by truncating the operands to the binary operations that are
+        // part of a chain of operations that can use smaller types.
+        if (ClampedVecTys.count(it)) {
+          assert(it->getType()->isIntegerTy() &&
+                 "Should not be clamping floats!");
+
+          Type *Ty = ClampedVecTys[it]->getScalarType();
+          VectorType *VecTy = VectorType::get(Ty, VF);
+          APart = Builder.CreateTrunc(APart, VecTy);
+          BPart = Builder.CreateTrunc(BPart, VecTy);
+        }
+        Value *V = Builder.CreateBinOp(BinOp->getOpcode(), APart, BPart);
 
         if (BinaryOperator *VecOp = dyn_cast<BinaryOperator>(V))
           VecOp->copyIRFlags(BinOp);
 
+        // If the instruction has had its inputs clamped, we need to then
+        // extend the value back to its original size.
+        if (ClampedVecTys.count(it))
+          V = Builder.CreateZExt(V, VectorType::get(it->getType(), VF));
+
         Entry[Part] = V;
       }
 
       propagateMetadata(Entry, it);
       break;
     }
     case Instruction::Select: {
       // Widen selects.
for (BasicBlock::iterator it = (*bb)->begin(), e = (*bb)->end(); it != e;
       if (StoreInst *ST = dyn_cast<StoreInst>(it)) {
         Type *T = ST->getValueOperand()->getType();
         if (!VectorType::isValidElementType(T)) {
           emitAnalysis(VectorizationReport(ST) <<
                        "store instruction cannot be vectorized");
           return false;
         }
         if (EnableMemAccessVersioning)
           collectStridedAccess(ST);
       }
 
       if (EnableMemAccessVersioning)
         if (LoadInst *LI = dyn_cast<LoadInst>(it))
           collectStridedAccess(LI);
 
       // Reduction instructions are allowed to have exit users.
       // All other instructions must not have external users.
for (auto &I : *BB) {
       // FIXME: Currently we can't handle mixed accesses and predicated accesses
       if (IsPred)
         return;
 
       AccessList.push_back(&I);
     }
   }
 
   if (AccessList.empty())
     return;
 
   auto &DL = TheLoop->getHeader()->getModule()->getDataLayout();
   for (auto I : AccessList) {
     LoadInst *LI = dyn_cast<LoadInst>(I);
     StoreInst *SI = dyn_cast<StoreInst>(I);
 
     Value *Ptr = LI ? LI->getPointerOperand() : SI->getPointerOperand();
     int Stride = isStridedPtr(SE, Ptr, TheLoop, Strides);
 
     // The factor of the corresponding interleave group.
     unsigned Factor = std::abs(Stride);
 
     // Ignore the access if the factor is too small or too large.
     if (Factor < 2 || Factor > MaxInterleaveGroupFactor)
       continue;
for (auto I = StrideAccesses.rbegin(), E = StrideAccesses.rend(); I != E;
 
     for (auto II = std::next(I); II != E; ++II) {
       Instruction *B = II->first;
       StrideDescriptor DesB = II->second;
 
       // Ignore if B is already in a group or B is a different memory operation.
       if (isInterleaved(B) || A->mayReadFromMemory() != B->mayReadFromMemory())
         continue;
 
       // Check the rule 1 and 2.
       if (DesB.Stride != DesA.Stride || DesB.Size != DesA.Size)
         continue;
 
       // Calculate the distance and prepare for the rule 3.
       const SCEVConstant *DistToA =
           dyn_cast<SCEVConstant>(SE->getMinusSCEV(DesB.Scev, DesA.Scev));
       if (!DistToA)
         continue;
 
       int DistanceToA = DistToA->getValue()->getValue().getSExtValue();
 
       // Skip if the distance is not multiple of size as they are not in the
       // same group.
       if (DistanceToA % static_cast<int>(DesA.Size))
         continue;
 
       // The index of B is the index of A plus the related index to A.
       int IndexB =
           Group->getIndex(A) + DistanceToA / static_cast<int>(DesA.Size);
 
       // Try to insert B into the group.
       if (Group->insertMember(B, IndexB, DesB.Align)) {
         DEBUG(dbgs() << "LV: Inserted:" << *B << '\n'
                      << "    into the interleave group with" << *A << '\n');
         InterleaveGroupMap[B] = Group;
 
         // Set the first load in program order as the insert position.
         if (B->mayReadFromMemory())
           Group->setInsertPos(B);
       }
     } // Iteration on instruction B
   }   // Iteration on instruction A
 
   // Remove interleaved store groups with gaps.
   for (InterleaveGroup *Group : StoreGroups)
     if (Group->getNumMembers() != Group->getFactor())
       releaseGroup(Group);
 }
 
 LoopVectorizationCostModel::VectorizationFactor
 LoopVectorizationCostModel::selectVectorizationFactor(bool OptForSize) {
   // Width 1 means no vectorize
   VectorizationFactor Factor = { 1U, 0U };
   if (OptForSize && Legal->getRuntimePointerChecking()->Need) {
     emitAnalysis(VectorizationReport() <<
                  "runtime pointer checks needed. Enable vectorization of this "
                  "loop with '#pragma clang loop vectorize(enable)' when "
                  "compiling with -Os");
if (TC < 2) {
       return Factor;
     }
 
     // Find the maximum SIMD width that can fit within the trip count.
     VF = TC % MaxVectorSize;
 
     if (VF == 0)
       VF = MaxVectorSize;
     else {
       // If the trip count that we found modulo the vectorization factor is not
       // zero then we require a tail.
       emitAnalysis(VectorizationReport() <<
                    "cannot optimize for size and vectorize at the "
                    "same time. Enable vectorization of this loop "
                    "with '#pragma clang loop vectorize(enable)' "
                    "when compiling with -Os");
       DEBUG(dbgs() << "LV: Aborting. A tail loop is required in Os.\n");

 LoopVectorizationCostModel::calculateRegisterUsage() {
   // This function calculates the register usage by measuring the highest number
   // of values that are alive at a single location. Obviously, this is a very
   // rough estimation. We scan the loop in a topological order in order and
   // assign a number to each instruction. We use RPO to ensure that defs are
   // met before their users. We assume that each instruction that has in-loop
   // users starts an interval. We record every time that an in-loop value is
   // used, so we have a list of the first and last occurrences of each
   // instruction. Next, we transpose this data structure into a multi map that
   // holds the list of intervals that *end* at a specific location. This multi
   // map allows us to perform a linear search. We scan the instructions linearly
   // and record each time that a new interval starts, by placing it in a set.
   // If we find this value in the multi-map then we remove it from the set.
   // The max register usage is the maximum size of the set.
   // We also search for instructions that are defined outside the loop, but are
   // used inside the loop. We need this number separately from the max-interval
   // usage number because when we unroll, loop-invariant values do not take
   // more register.
LoopVectorizationCostModel::calculateRegisterUsage() {
   R.LoopInvariantRegs = Invariant;
   R.MaxLocalUsers = MaxUsage;
   return R;
 }
 
 unsigned LoopVectorizationCostModel::expectedCost(unsigned VF) {
   unsigned Cost = 0;
 
+  NarrowInstrs.insert(std::make_pair(VF, std::map<Instruction*, Type*>()));
+
   // For each block.
   for (Loop::block_iterator bb = TheLoop->block_begin(),
        be = TheLoop->block_end(); bb != be; ++bb) {
     unsigned BlockCost = 0;
     BasicBlock *BB = *bb;
 
-    // For each instruction in the old loop.
+    // For each instruction in the old loop, scan across them to identify
+    // instructions that could use more narrow types.
     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
       // Skip dbg intrinsics.
-      if (isa<DbgInfoIntrinsic>(it))
+      if (isa<DbgInfoIntrinsic>(*it))
         continue;
 
       // Ignore ephemeral values.
-      if (EphValues.count(it))
+      if (EphValues.count(&*it))
+        continue;
+
+      MapNarrowInstruction(it, VF);
+    }
+
+    // For each instruction in the old loop. Iterate in reverse order so that
+    // so that narrow typed instructions chains can be confirmed from searching
+    // bottom-up from trunc instructions.
+    for (auto it = BB->rbegin(), e = BB->rend(); it != e; ++it) {
+      // Skip dbg intrinsics.
+      if (isa<DbgInfoIntrinsic>(*it))
+        continue;
+
+      // Ignore ephemeral values.
+      if (EphValues.count(&*it))
         continue;
 
-      unsigned C = getInstructionCost(it, VF);
+      unsigned C = getInstructionCost(&*it, VF);
 
       // Check if we should override the cost.
       if (ForceTargetInstructionCost.getNumOccurrences() > 0)
         C = ForceTargetInstructionCost;
 
       BlockCost += C;
       DEBUG(dbgs() << "LV: Found an estimated cost of " << C << " for VF " <<
             VF << " For instruction: " << *it << '\n');

 }
 
 static bool isStrideMul(Instruction *I, LoopVectorizationLegality *Legal) {
   if (Legal->hasStride(I->getOperand(0)) || Legal->hasStride(I->getOperand(1)))
     return true;
   return false;
 }
 
+// The search for free casts and smaller types begins from truncs towards the
+// possible extend instructions and during the search, the extend instructions
+// are saved.
+Type* LoopVectorizationCostModel::getAdjustedCastType(Instruction *I,
+                                                      unsigned VF) {
+  if (NarrowInstrs[VF].count(I)) {
+    Type *NarrowTy = nullptr;
+    if (CastInst *CI = dyn_cast<CastInst>(I)) {
+      if (TruncInst *TI = dyn_cast<TruncInst>(I))
+        NarrowTy = TI->getDestTy();
+      else
+        NarrowTy = CI->getSrcTy();
+
+      if (NarrowTy == NarrowInstrs[VF][I]) {
+        DEBUG(dbgs() << "LV: This cast is free: " << CI->getName() << "\n");
+        return nullptr;
+      }
+      else
+        return NarrowInstrs[VF][I];
+    }
+  }
+  return I->getType();
+}
+
+Type *getLargestType(Type *T0, Type *T1) {
+  if (T0->isIntegerTy()) {
+    if (T1->isIntegerTy())
+      return T0->getIntegerBitWidth() > T1->getIntegerBitWidth() ? T0 : T1;
+    else
+      return T0;
+  } else if (T1->isIntegerTy())
+    return T1;
+
+  llvm_unreachable("one type should be integer!");
+  return T0;
+}
+
+bool LoopVectorizationCostModel::TryInsertCandidateNarrow(Instruction *I,
+                                                   Type *NarrowTy,
+                                                   unsigned VF) {
+  // We do not allow illegal types to be inserted.
+  if (TTI.isTypeLegal(VectorType::get(NarrowTy, VF))) {
+    if (CandidateNarrowInstrs[VF].count(I)) {
+      Type *Largest = getLargestType(CandidateNarrowInstrs[VF][I], NarrowTy);
+      if (Largest == NarrowTy) {
+        CandidateNarrowInstrs[VF].erase(I);
+        CandidateNarrowInstrs[VF].insert(std::make_pair(I, NarrowTy));
+      }
+    } else
+      CandidateNarrowInstrs[VF].insert(std::make_pair(I, NarrowTy));
+    return true;
+  }
+  return false;
+}
+
+void LoopVectorizationCostModel::InsertConfirmedNarrow(Instruction *I, Type *NarrowTy,
+                                              unsigned VF) {
+  if (NarrowInstrs[VF].count(I)) {
+    Type *Largest = getLargestType(NarrowInstrs[VF][I], NarrowTy);
+    if (Largest == NarrowTy) {
+      NarrowInstrs[VF].erase(I);
+      NarrowInstrs[VF].insert(std::make_pair(I, NarrowTy));
+    }
+  } else
+    NarrowInstrs[VF].insert(std::make_pair(I, NarrowTy));
+}
+
+Type*
+LoopVectorizationCostModel::getClampedVectorTy(Instruction *I, unsigned VF) {
+  if (NarrowInstrs[VF].count(I))
+    return ToVectorTy(NarrowInstrs[VF][I], VF);
+  else
+    return ToVectorTy(I->getType(), VF);
+}
+
+bool LoopVectorizationCostModel::ConfirmNarrowChain(Instruction *I,
+                                                    unsigned VF,
+                                                    Type *NarrowTy) {
+  LLVMContext &Context = TheLoop->getHeader()->getContext();
+  // If a narrow type has already been suggested for this instruction, update
+  // NarrowTy to be the larger of these types.
+  if (CandidateNarrowInstrs[VF].count(I))
+    NarrowTy = getLargestType(NarrowTy, CandidateNarrowInstrs[VF][I]);
+
+  // Extend instructions now use NarrowTy, this would have either been deduced
+  // in the first top-down phase, or it has now be recalculated by the value
+  // required by its single user.
+  if (CastInst *CI = dyn_cast<CastInst>(I)) {
+    if (!isa<TruncInst>(CI)) {
+      InsertConfirmedNarrow(CI, NarrowTy, VF);
+      return true;
+    }
+    return false;
+  }
+
+  // Right shifts can be allowed if the size reduction does not prevent the
+  // necessary high bits from being calculated. This is true when the shift
+  // value is less or equal to the suggested narrow type - this narrow type
+  // is then doubled in size so not to lose the calculated high bits.
+  if (I->getOpcode() == Instruction::LShr ||
+      I->getOpcode() == Instruction::AShr) {
+    unsigned ShiftVal = cast<ConstantInt>(I->getOperand(1))->getZExtValue();
+    if (ShiftVal <= 8 && NarrowTy == Type::getInt8Ty(Context))
+      NarrowTy = Type::getInt16Ty(Context);
+    else if (ShiftVal <= 16 && I->getType() == Type::getInt64Ty(Context) &&
+             NarrowTy == Type::getInt16Ty(Context))
+      NarrowTy = Type::getInt32Ty(Context);
+    else
+      return false;
+  }
+
+  // To confirm instruction I:
+  // For all the operands, Opr
+  // - if its confirmed, continue
+  // - if its TBC, perform confirmation of Opr
+  // - if its a cast, the type may be adjusted and needs to be saved
+  // - if its a constant - continue
+  // - if not any of the above, this isn't a narrow inst.
+  unsigned NumConfirmed = 0;
+  for (Value *Opr : I->operands()) {
+    if (Instruction *NextOp = dyn_cast<Instruction>(Opr)) {
+      // If we find an already confirmed operand, grab its value.
+      if (NarrowInstrs[VF].count(NextOp))
+        ++NumConfirmed;
+      else if (CandidateNarrowInstrs[VF].count(NextOp)) {
+        // Need to confirm the type of this operand
+        if (ConfirmNarrowChain(NextOp, VF, NarrowTy))
+          ++NumConfirmed;
+        else
+          break;
+      } else if (isa<CastInst>(NextOp)) {
+        // Visit any new CastInsts using this narrow type.
+        if (ConfirmNarrowChain(NextOp, VF, NarrowTy))
+          ++NumConfirmed;
+      }
+    } else if (isa<ConstantInt>(Opr))
+      // We do not have to check as this has previously done, NarrowTy may
+      // have changed, but it only grows.
+      ++NumConfirmed;
+  }
+
+  if (I->getNumOperands() != NumConfirmed) {
+    CandidateNarrowInstrs[VF].erase(I);
+    return false;
+  } else {
+    // If a value already exists for I, the larger type will be kept
+    InsertConfirmedNarrow(I, NarrowTy, VF);
+    return true;
+  }
+}
+
+void LoopVectorizationCostModel::MapNarrowInstruction(Instruction *I,
+                                                      unsigned VF) {
+  if (isa<PHINode>(I))
+    return;
+
+  // We only care about integer operations.
+  Type *DstTy = I->getType();
+  if (!DstTy->isIntegerTy())
+    return;
+
+  // The following opcodes have been selected as if the same values will
+  // be calculated for them even with truncated types. They do not require
+  // the high bits that will be ultimately removed at the finally truncation.
+  // This is not true for the shift right operations, but these can be included
+  // if the shift value is an immediate equal or less than half of the bitwidth
+  // of the resulting type. The extend and trunc ops are also included as they
+  // bound the chains of operations.
+  unsigned Opc = I->getOpcode();
+  if (Opc != Instruction::Mul &&
+      Opc != Instruction::Add &&
+      Opc != Instruction::Sub &&
+      Opc != Instruction::And &&
+      Opc != Instruction::Or &&
+      Opc != Instruction::Xor &&
+      Opc != Instruction::Shl &&
+      Opc != Instruction::LShr &&
+      Opc != Instruction::AShr)
+    return;
+
+  // We can later analyse and validate shift right operations only with an
+  // immediate shift value.
+  if (Opc == Instruction::LShr ||
+      Opc == Instruction::AShr)
+    if (!isa<ConstantInt>(I->getOperand(1)))
+      return;
+
+  const APInt i8MaxValue = APInt::getMaxValue(8);
+  const APInt i16MaxValue = APInt::getMaxValue(16);
+  const APInt i32MaxValue = APInt::getMaxValue(32);
+  SmallVector<Type*, 2> NarrowOpTys;
+  LLVMContext &Context = TheLoop->getHeader()->getContext();
+
+  // Search the operands of the instruction and look for operands that have
+  // already been added, constants within the size limit or sext/zext.
+  for (Value *Opr : I->operands()) {
+    if (Instruction *NextOp = dyn_cast<Instruction>(Opr)) {
+      // If the operand is an instruction, it needs to have already been added
+      // to CandidateNarrowInstrs or a CastInst that may not be in the loop body.
+      if (CandidateNarrowInstrs[VF].count(NextOp))
+        NarrowOpTys.push_back(CandidateNarrowInstrs[VF][NextOp]);
+      else if (auto *CI = dyn_cast<CastInst>(NextOp)) {
+        if (auto *TI = dyn_cast<TruncInst>(I)) {
+          if (TryInsertCandidateNarrow(TI, TI->getDestTy(), VF))
+            NarrowOpTys.push_back(TI->getDestTy());
+        } else if (TryInsertCandidateNarrow(CI, CI->getSrcTy(), VF))
+            NarrowOpTys.push_back(CI->getSrcTy());
+      } else
+        return;
+    } else if (auto *ConstInt = dyn_cast<ConstantInt>(Opr)) {
+      // If the operand is a constant, calculate the smallest type that it
+      // can be. Isn't counted as a narrow operand if its larger than 16-bits,
+      // unless the original value is an i64.
+      unsigned BitWidth = ConstInt->getValue().getBitWidth();
+      const APInt ConstVal = ConstInt->getValue();
+      APInt MaskValue = ConstVal & (i8MaxValue.zextOrSelf(BitWidth));
+      if (ConstVal.eq(MaskValue))
+        NarrowOpTys.push_back(Type::getInt8Ty(Context));
+      else if (ConstVal.eq(ConstVal & (i16MaxValue.zextOrSelf(BitWidth))))
+        NarrowOpTys.push_back(Type::getInt16Ty(Context));
+      else if (I->getType() == Type::getInt64Ty(Context) &&
+               ConstVal.eq(ConstVal & (i32MaxValue.zextOrSelf(BitWidth))))
+        NarrowOpTys.push_back(Type::getInt32Ty(Context));
+      else
+        return;
+    }
+  }
+  if (NarrowOpTys.size() == I->getNumOperands()) {
+    // If narrow operands are found, we need to map the new narrow type. This is
+    // either the larger type of the two operands if their differ in size.
+    if (NarrowOpTys[0] == NarrowOpTys[1]) {
+      TryInsertCandidateNarrow(I, NarrowOpTys[0], VF);
+    }
+    else {
+      Type *LargerType = getLargestType(NarrowOpTys[0], NarrowOpTys[1]);
+      TryInsertCandidateNarrow(I, LargerType, VF);
+    }
+  }
+}
+
 unsigned
 LoopVectorizationCostModel::getInstructionCost(Instruction *I, unsigned VF) {
   // If we know that this instruction will remain uniform, check the cost of
   // the scalar version.
   if (Legal->isUniformAfterVectorization(I))
     VF = 1;
 
   Type *RetTy = I->getType();
-  Type *VectorTy = ToVectorTy(RetTy, VF);
+  Type *VectorTy = getClampedVectorTy(I, VF);
 
   // TODO: We need to estimate the cost of intrinsic calls.
   switch (I->getOpcode()) {
   case Instruction::GetElementPtr:
     // We mark this instruction as zero-cost because the cost of GEPs in
     // vectorized code depends on whether the corresponding memory instruction
     // is scalarized or not. Therefore, we handle GEPs with the memory
     // instruction cost.
if (isa<ConstantInt>(Op2)) {
         Op2VP = TargetTransformInfo::OP_PowerOf2;
       Op2VK = TargetTransformInfo::OK_UniformConstantValue;
     } else if (isa<ConstantVector>(Op2) || isa<ConstantDataVector>(Op2)) {
       Op2VK = TargetTransformInfo::OK_NonUniformConstantValue;
       Constant *SplatValue = cast<Constant>(Op2)->getSplatValue();
       if (SplatValue) {
         ConstantInt *CInt = dyn_cast<ConstantInt>(SplatValue);
         if (CInt && CInt->getValue().isPowerOf2())
           Op2VP = TargetTransformInfo::OP_PowerOf2;
         Op2VK = TargetTransformInfo::OK_UniformConstantValue;
       }
     }
 
     return TTI.getArithmeticInstrCost(I->getOpcode(), VectorTy, Op1VK, Op2VK,
                                       Op1VP, Op2VP);
   }
   case Instruction::Select: {
case Instruction::Load: {
     StoreInst *SI = dyn_cast<StoreInst>(I);
     LoadInst *LI = dyn_cast<LoadInst>(I);
     Type *ValTy = (SI ? SI->getValueOperand()->getType() :
                    LI->getType());
     VectorTy = ToVectorTy(ValTy, VF);
 
     unsigned Alignment = SI ? SI->getAlignment() : LI->getAlignment();
     unsigned AS = SI ? SI->getPointerAddressSpace() :
       LI->getPointerAddressSpace();
     Value *Ptr = SI ? SI->getPointerOperand() : LI->getPointerOperand();
     // We add the cost of address computation here instead of with the gep
     // instruction because only here we know whether the operation is
     // scalarized.
     if (VF == 1)
       return TTI.getAddressComputationCost(VectorTy) +
         TTI.getMemoryOpCost(I->getOpcode(), VectorTy, Alignment, AS);
 
LoopVectorizationCostModel::getInstructionCost(Instruction *I, unsigned VF) {
   case Instruction::FPExt:
   case Instruction::PtrToInt:
   case Instruction::IntToPtr:
   case Instruction::SIToFP:
   case Instruction::UIToFP:
   case Instruction::Trunc:
   case Instruction::FPTrunc:
   case Instruction::BitCast: {
+    Type *SrcTy = I->getOperand(0)->getType();
+    Type *SrcVecTy = ToVectorTy(SrcTy, VF);
+    unsigned Opcode = I->getOpcode();
     // We optimize the truncation of induction variable.
     // The cost of these is the same as the scalar operation.
-    if (I->getOpcode() == Instruction::Trunc &&
+    if (Opcode == Instruction::Trunc &&
         Legal->isInductionVariable(I->getOperand(0)))
-      return TTI.getCastInstrCost(I->getOpcode(), I->getType(),
-                                  I->getOperand(0)->getType());
+      return TTI.getCastInstrCost(Opcode, I->getType(), SrcTy);
+    else if (Opcode == Instruction::Trunc) {
+      // First, check whether the truncation destination size would be a legal
+      // vector type.
+      if (TTI.isTypeLegal(VectorTy)) {
+        Instruction *ChainOp = cast<Instruction>(I->getOperand(0));
+        if (ConfirmNarrowChain(ChainOp, VF, RetTy)) {
+          DEBUG(dbgs() << "LV: Found a chain of narrow instructions\n");
+          Type *NarrowTy = NarrowInstrs[VF][ChainOp];
+          InsertConfirmedNarrow(I, NarrowTy, VF);
+        }
+      }
+    }
+    // If AdjustedType is nullptr, it is a free cast, otherwise use the adjusted
+    // type for either the source or destination.
+    Type *AdjustedType = getAdjustedCastType(I, VF);
+    if (AdjustedType == nullptr)
+      return 0;
+    else if (Instruction::Trunc == Opcode)
+      SrcTy = ToVectorTy(AdjustedType, VF);
+    else if (Instruction::ZExt == Opcode ||
+             Instruction::SExt == Opcode)
+      VectorTy = ToVectorTy(AdjustedType, VF);
 
-    Type *SrcVecTy = ToVectorTy(I->getOperand(0)->getType(), VF);
-    return TTI.getCastInstrCost(I->getOpcode(), VectorTy, SrcVecTy);
+    return TTI.getCastInstrCost(Opcode, VectorTy, SrcVecTy);
   }
   case Instruction::Call: {
     bool NeedToScalarize;
     CallInst *CI = cast<CallInst>(I);
     unsigned CallCost = getVectorCallCost(CI, VF, TTI, TLI, NeedToScalarize);
     if (getIntrinsicIDForCall(CI, TLI))
       return std::min(CallCost, getVectorIntrinsicCost(CI, VF, TTI, TLI));
     return CallCost;
void InnerLoopUnroller::scalarizeInstruction(Instruction *Instr,
 
   assert(Params.size() == Instr->getNumOperands() &&
          "Invalid number of operands");
 
   // Does this instruction return a value ?
   bool IsVoidRetTy = Instr->getType()->isVoidTy();
 
   Value *UndefVec = IsVoidRetTy ? nullptr :
-  UndefValue::get(Instr->getType());
+    UndefValue::get(VectorType::get(Instr->getType(), VF));
   // Create a new entry in the WidenMap and initialize it to Undef or Null.
   VectorParts &VecResults = WidenMap.splat(Instr, UndefVec);
 
   Instruction *InsertPt = Builder.GetInsertPoint();
   BasicBlock *IfBlock = Builder.GetInsertBlock();
   BasicBlock *CondBlock = nullptr;
 
   VectorParts Cond;

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

+; RUN: opt -S < %s -basicaa -loop-vectorize -simplifycfg -instsimplify -instcombine -licm  2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64"
+
+; CHECK-LABEL: @add_a(
+; COST: cost of 2 {{.*}} load <16 x i8>
+; CHECK: load <16 x i8>, <16 x i8>*
+; CHECK: load <16 x i8>, <16 x i8>*
+; COST: cost of 1 for instruction: {{.*}} add <16 x i8>
+; CHECK: add nuw nsw <16 x i8>
+; CHECK: add nuw nsw <16 x i8>
+; COST: cost of 2 for instruction: {{.*}} store <16 x i8>
+; CHECK: store <16 x i8>
+; CHECK: store <16 x i8>
+; Function Attrs: nounwind
+define void @add_a(i8* noalias nocapture readonly %p, i8* noalias nocapture %q, i32 %len) #0 {
+entry:
+  %cmp8 = icmp sgt i32 %len, 0
+  br i1 %cmp8, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i8, i8* %p, i64 %indvars.iv
+  %0 = load i8, i8* %arrayidx
+  %conv = zext i8 %0 to i32
+  %add = add nuw nsw i32 %conv, 2
+  %conv1 = trunc i32 %add to i8
+  %arrayidx3 = getelementptr inbounds i8, i8* %q, i64 %indvars.iv
+  store i8 %conv1, i8* %arrayidx3
+  %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, %len
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+; CHECK-LABEL: @add_b(
+; COST: cost of 2 for instruction: {{.*}} load <16 x i8>
+; CHECK: load <8 x i16>, <8 x i16>*
+; CHECK: load <8 x i16>, <8 x i16>*
+; COST: cost of 1 for instruction: {{.*}} add <16 x i8>
+; CHECK: add nuw nsw <8 x i16>
+; CHECK: add nuw nsw <8 x i16>
+; COST: cost of 2 for instruction: {{.*}} store <16 x i8>
+; CHECK: store <8 x i16>
+; CHECK: store <8 x i16>
+; Function Attrs: nounwind
+define void @add_b(i16* noalias nocapture readonly %p, i16* noalias nocapture %q, i32 %len) #0 {
+entry:
+  %cmp9 = icmp sgt i32 %len, 0
+  br i1 %cmp9, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i16, i16* %p, i64 %indvars.iv
+  %0 = load i16, i16* %arrayidx
+  %conv8 = zext i16 %0 to i32
+  %add = add nuw nsw i32 %conv8, 2
+  %conv1 = trunc i32 %add to i16
+  %arrayidx3 = getelementptr inbounds i16, i16* %q, i64 %indvars.iv
+  store i16 %conv1, i16* %arrayidx3
+  %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, %len
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+; CHECK-LABEL: @add_c(
+; CHECK: load <8 x i8>, <8 x i8>*
+; CHECK: add nuw nsw <8 x i16>
+; CHECK: store <8 x i16>
+; Function Attrs: nounwind
+define void @add_c(i8* noalias nocapture readonly %p, i16* noalias nocapture %q, i32 %len) #0 {
+entry:
+  %cmp8 = icmp sgt i32 %len, 0
+  br i1 %cmp8, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i8, i8* %p, i64 %indvars.iv
+  %0 = load i8, i8* %arrayidx
+  %conv = zext i8 %0 to i32
+  %add = add nuw nsw i32 %conv, 2
+  %conv1 = trunc i32 %add to i16
+  %arrayidx3 = getelementptr inbounds i16, i16* %q, i64 %indvars.iv
+  store i16 %conv1, i16* %arrayidx3
+  %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, %len
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+; CHECK-LABEL: @add_d(
+; COST: cost of 2 for instruction: {{.*}} load <4 x i16>
+; CHECK: load <4 x i16>
+; CHECK: load <4 x i16>
+; COST: cost of 1 for instruction: {{.*}} add <4 x i32>
+; CHECK: add nsw <4 x i32>
+; CHECK: add nsw <4 x i32>
+; COST: cost of 2 for instruction: {{.*}} store <4 x i32>
+; CHECK: store <4 x i32>
+; CHECK: store <4 x i32>
+define void @add_d(i16* noalias nocapture readonly %p, i32* noalias nocapture %q, i32 %len) #0 {
+entry:
+  %cmp7 = icmp sgt i32 %len, 0
+  br i1 %cmp7, label %for.body, label %for.cond.cleanup
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %entry, %for.body
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.body ], [ 0, %entry ]
+  %arrayidx = getelementptr inbounds i16, i16* %p, i64 %indvars.iv
+  %0 = load i16, i16* %arrayidx
+  %conv = sext i16 %0 to i32
+  %add = add nsw i32 %conv, 2
+  %arrayidx2 = getelementptr inbounds i32, i32* %q, i64 %indvars.iv
+  store i32 %add, i32* %arrayidx2
+  %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, %len
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+; CHECK-LABEL: @add_e(
+; COST: cost of 2 for instruction: {{.*}} load <16 x i8>
+; CHECK: load <16 x i8>
+; CHECK: load <16 x i8>
+; COST: cost of 2 for instruction: {{.*}} shl <16 x i8>
+; CHECK: shl nuw nsw <16 x i8>
+; CHECK: shl nuw nsw <16 x i8>
+; COST: cost of 1 for instruction: {{.*}} add <16 x i8>
+; CHECK: add nuw nsw <16 x i8>
+; CHECK: add nuw nsw <16 x i8>
+; COST: cost of 1 for instruction: {{.*}} or <16 x i8>
+; CHECK: or <16 x i8>
+; CHECK: or <16 x i8>
+; COST: cost of 1 for instruction: {{.*}} mul <16 x i8>
+; CHECK: mul nuw nsw <16 x i8>
+; CHECK: mul nuw nsw <16 x i8>
+; COST: cost of 1 for instruction: {{.*}} and <16 x i8>
+; CHECK: and <16 x i8>
+; CHECK: and <16 x i8>
+; COST: cost of 1 for instruction: {{.*}} xor <16 x i8>
+; CHECK: xor <16 x i8>
+; CHECK: xor <16 x i8>
+; COST: cost of 1 for instruction: {{.*}} mul <16 x i8>
+; CHECK: mul nuw nsw <16 x i8>
+; CHECK: mul nuw nsw <16 x i8>
+; COST: cost of 2 for instruction: {{.*}} store <16 x i8>
+; CHECK: store <16 x i8>
+; CHECK: store <16 x i8>
+define void @add_e(i8* noalias nocapture readonly %p, i8* noalias nocapture %q, i8 %arg1, i8 %arg2, i32 %len) #0 {
+entry:
+  %cmp.32 = icmp sgt i32 %len, 0
+  br i1 %cmp.32, label %for.body.lr.ph, label %for.cond.cleanup
+
+for.body.lr.ph:                                   ; preds = %entry
+  %conv11 = zext i8 %arg2 to i32
+  %conv13 = zext i8 %arg1 to i32
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %for.body, %for.body.lr.ph
+  %indvars.iv = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i8, i8* %p, i64 %indvars.iv
+  %0 = load i8, i8* %arrayidx
+  %conv = zext i8 %0 to i32
+  %add = shl nuw nsw i32 %conv, 4
+  %conv2 = add nuw nsw i32 %add, 32
+  %or = or i32 %conv, 51
+  %mul = mul nuw nsw i32 %or, 60
+  %and = and i32 %conv2, %conv13
+  %mul.masked = and i32 %mul, 252
+  %conv17 = xor i32 %mul.masked, %conv11
+  %mul18 = mul nuw nsw i32 %conv17, %and
+  %conv19 = trunc i32 %mul18 to i8
+  %arrayidx21 = getelementptr inbounds i8, i8* %q, i64 %indvars.iv
+  store i8 %conv19, i8* %arrayidx21
+  %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, %len
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+; COST: cost of 2 for instruction: {{.*}} load <8 x i16>
+; CHECK: load <8 x i16>
+; COST: cost of 2 for instruction: {{.*}} shl <8 x i16>
+; CHECK: shl nsw <8 x i16>
+; COST: cost of 1 for instruction: {{.*}} add <8 x i16>
+; CHECK: add nsw <8 x i16>
+; COST: cost of 1 for instruction: {{.*}} and <8 x i16>
+; CHECK: and <8 x i16>
+; COST: cost of 1 for instruction: {{.*}} or <8 x i16>
+; CHECK: or <8 x i16>
+; COST: cost of 1 for instruction: {{.*}} mul <8 x i16>
+; CHECK: mul nuw nsw <8 x i16>
+; COST: cost of 1 for instruction: {{.*}} and <8 x i16>
+; CHECK: and <8 x i16>
+; CHECK: and <8 x i16>
+; COST: cost of 1 for instruction: {{.*}} xor <8 x i16>
+; CHECK: xor <8 x i16>
+; COST: cost of 1 for instruction: {{.*}} mul <8 x i16>
+; CHECK: mul nuw nsw <8 x i16>
+; COST: cost 28 for instruction: {{.*}} trunc <8 x i16>
+; CHECK trunc <8 x i16>
+; COST: cost of 2 for instruction: {{.*}} store <8 x i8>
+; CHECK: store <8 x i8>
+define void @add_f(i16* noalias nocapture readonly %p, i8* noalias nocapture %q, i8 %arg1, i8 %arg2, i32 %len) #0 {
+entry:
+  %cmp.32 = icmp sgt i32 %len, 0
+  br i1 %cmp.32, label %for.body.lr.ph, label %for.cond.cleanup
+
+for.body.lr.ph:                                   ; preds = %entry
+  %conv11 = zext i8 %arg2 to i32
+  %conv13 = zext i8 %arg1 to i32
+  br label %for.body
+
+for.cond.cleanup:                                 ; preds = %for.body, %entry
+  ret void
+
+for.body:                                         ; preds = %for.body, %for.body.lr.ph
+  %indvars.iv = phi i64 [ 0, %for.body.lr.ph ], [ %indvars.iv.next, %for.body ]
+  %arrayidx = getelementptr inbounds i16, i16* %p, i64 %indvars.iv
+  %0 = load i16, i16* %arrayidx
+  %conv = sext i16 %0 to i32
+  %add = shl nsw i32 %conv, 4
+  %conv2 = add nsw i32 %add, 32
+  %or = and i32 %conv, 204
+  %conv8 = or i32 %or, 51
+  %mul = mul nuw nsw i32 %conv8, 60
+  %and = and i32 %conv2, %conv13
+  %mul.masked = and i32 %mul, 252
+  %conv17 = xor i32 %mul.masked, %conv11
+  %mul18 = mul nuw nsw i32 %conv17, %and
+  %conv19 = trunc i32 %mul18 to i8
+  %arrayidx21 = getelementptr inbounds i8, i8* %q, i64 %indvars.iv
+  store i8 %conv19, i8* %arrayidx21
+  %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, %len
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+}
+
+; CHECK: load <4 x i16>
+; CHECK: load <4 x i16>
+; CHECK: shl nsw <4 x i32>
+; CHECK: mul nsw <4 x i32>
+; CHECK: add <4 x i32>
+; CHECK: and <4 x i32>
+; CHECK: lshr <4 x i32>
+define void @add_g(i16* noalias nocapture readonly %p, i16* noalias nocapture readonly %q, i16* noalias nocapture %r, i16 %arg1, i32 %len) #0 {
+  %1 = icmp sgt i32 %len, 0
+  br i1 %1, label %.lr.ph, label %._crit_edge
+
+.lr.ph:                                           ; preds = %0
+  %2 = sext i16 %arg1 to i64
+  br label %3
+
+._crit_edge:                                      ; preds = %3, %0
+  ret void
+
+; <label>:3                                       ; preds = %3, %.lr.ph
+  %indvars.iv = phi i64 [ 0, %.lr.ph ], [ %indvars.iv.next, %3 ]
+  %4 = getelementptr inbounds i16, i16* %p, i64 %indvars.iv
+  %5 = load i16, i16* %4
+  %6 = sext i16 %5 to i64
+  %7 = getelementptr inbounds i16, i16* %q, i64 %indvars.iv
+  %8 = load i16, i16* %7
+  %9 = sext i16 %8 to i64
+  %10 = shl nsw i64 %6, 4
+  %11 = mul nsw i64 %10, %9
+  %12 = add i64 %11, 16384
+  %13 = and i64 %12, %2
+  %14 = lshr i64 %13, 15
+  %15 = trunc i64 %14 to i16
+  %16 = getelementptr inbounds i16, i16* %r, i64 %indvars.iv
+  store i16 %15, i16* %16
+  %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, %len
+  br i1 %exitcond, label %._crit_edge, label %3
+}
+
+attributes #0 = { nounwind }
+
+