Vectorize: Remove implicit ilist iterator conversions, NFC
[oota-llvm.git] / lib / Transforms / Vectorize / SLPVectorizer.cpp
1 //===- SLPVectorizer.cpp - A bottom up SLP Vectorizer ---------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 // This pass implements the Bottom Up SLP vectorizer. It detects consecutive
10 // stores that can be put together into vector-stores. Next, it attempts to
11 // construct vectorizable tree using the use-def chains. If a profitable tree
12 // was found, the SLP vectorizer performs vectorization on the tree.
13 //
14 // The pass is inspired by the work described in the paper:
15 //  "Loop-Aware SLP in GCC" by Ira Rosen, Dorit Nuzman, Ayal Zaks.
16 //
17 //===----------------------------------------------------------------------===//
18 #include "llvm/Transforms/Vectorize.h"
19 #include "llvm/ADT/MapVector.h"
20 #include "llvm/ADT/Optional.h"
21 #include "llvm/ADT/PostOrderIterator.h"
22 #include "llvm/ADT/SetVector.h"
23 #include "llvm/ADT/Statistic.h"
24 #include "llvm/Analysis/AliasAnalysis.h"
25 #include "llvm/Analysis/AssumptionCache.h"
26 #include "llvm/Analysis/CodeMetrics.h"
27 #include "llvm/Analysis/LoopInfo.h"
28 #include "llvm/Analysis/ScalarEvolution.h"
29 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
30 #include "llvm/Analysis/TargetTransformInfo.h"
31 #include "llvm/Analysis/ValueTracking.h"
32 #include "llvm/IR/DataLayout.h"
33 #include "llvm/IR/Dominators.h"
34 #include "llvm/IR/IRBuilder.h"
35 #include "llvm/IR/Instructions.h"
36 #include "llvm/IR/IntrinsicInst.h"
37 #include "llvm/IR/Module.h"
38 #include "llvm/IR/NoFolder.h"
39 #include "llvm/IR/Type.h"
40 #include "llvm/IR/Value.h"
41 #include "llvm/IR/Verifier.h"
42 #include "llvm/Pass.h"
43 #include "llvm/Support/CommandLine.h"
44 #include "llvm/Support/Debug.h"
45 #include "llvm/Support/raw_ostream.h"
46 #include "llvm/Analysis/VectorUtils.h"
47 #include <algorithm>
48 #include <map>
49 #include <memory>
50
51 using namespace llvm;
52
53 #define SV_NAME "slp-vectorizer"
54 #define DEBUG_TYPE "SLP"
55
56 STATISTIC(NumVectorInstructions, "Number of vector instructions generated");
57
58 static cl::opt<int>
59     SLPCostThreshold("slp-threshold", cl::init(0), cl::Hidden,
60                      cl::desc("Only vectorize if you gain more than this "
61                               "number "));
62
63 static cl::opt<bool>
64 ShouldVectorizeHor("slp-vectorize-hor", cl::init(false), cl::Hidden,
65                    cl::desc("Attempt to vectorize horizontal reductions"));
66
67 static cl::opt<bool> ShouldStartVectorizeHorAtStore(
68     "slp-vectorize-hor-store", cl::init(false), cl::Hidden,
69     cl::desc(
70         "Attempt to vectorize horizontal reductions feeding into a store"));
71
72 static cl::opt<int>
73 MaxVectorRegSizeOption("slp-max-reg-size", cl::init(128), cl::Hidden,
74     cl::desc("Attempt to vectorize for this register size in bits"));
75
76 /// Limits the size of scheduling regions in a block.
77 /// It avoid long compile times for _very_ large blocks where vector
78 /// instructions are spread over a wide range.
79 /// This limit is way higher than needed by real-world functions.
80 static cl::opt<int>
81 ScheduleRegionSizeBudget("slp-schedule-budget", cl::init(100000), cl::Hidden,
82     cl::desc("Limit the size of the SLP scheduling region per block"));
83
84 namespace {
85
86 // FIXME: Set this via cl::opt to allow overriding.
87 static const unsigned MinVecRegSize = 128;
88
89 static const unsigned RecursionMaxDepth = 12;
90
91 // Limit the number of alias checks. The limit is chosen so that
92 // it has no negative effect on the llvm benchmarks.
93 static const unsigned AliasedCheckLimit = 10;
94
95 // Another limit for the alias checks: The maximum distance between load/store
96 // instructions where alias checks are done.
97 // This limit is useful for very large basic blocks.
98 static const unsigned MaxMemDepDistance = 160;
99
100 /// If the ScheduleRegionSizeBudget is exhausted, we allow small scheduling
101 /// regions to be handled.
102 static const int MinScheduleRegionSize = 16;
103
104 /// \brief Predicate for the element types that the SLP vectorizer supports.
105 ///
106 /// The most important thing to filter here are types which are invalid in LLVM
107 /// vectors. We also filter target specific types which have absolutely no
108 /// meaningful vectorization path such as x86_fp80 and ppc_f128. This just
109 /// avoids spending time checking the cost model and realizing that they will
110 /// be inevitably scalarized.
111 static bool isValidElementType(Type *Ty) {
112   return VectorType::isValidElementType(Ty) && !Ty->isX86_FP80Ty() &&
113          !Ty->isPPC_FP128Ty();
114 }
115
116 /// \returns the parent basic block if all of the instructions in \p VL
117 /// are in the same block or null otherwise.
118 static BasicBlock *getSameBlock(ArrayRef<Value *> VL) {
119   Instruction *I0 = dyn_cast<Instruction>(VL[0]);
120   if (!I0)
121     return nullptr;
122   BasicBlock *BB = I0->getParent();
123   for (int i = 1, e = VL.size(); i < e; i++) {
124     Instruction *I = dyn_cast<Instruction>(VL[i]);
125     if (!I)
126       return nullptr;
127
128     if (BB != I->getParent())
129       return nullptr;
130   }
131   return BB;
132 }
133
134 /// \returns True if all of the values in \p VL are constants.
135 static bool allConstant(ArrayRef<Value *> VL) {
136   for (unsigned i = 0, e = VL.size(); i < e; ++i)
137     if (!isa<Constant>(VL[i]))
138       return false;
139   return true;
140 }
141
142 /// \returns True if all of the values in \p VL are identical.
143 static bool isSplat(ArrayRef<Value *> VL) {
144   for (unsigned i = 1, e = VL.size(); i < e; ++i)
145     if (VL[i] != VL[0])
146       return false;
147   return true;
148 }
149
150 ///\returns Opcode that can be clubbed with \p Op to create an alternate
151 /// sequence which can later be merged as a ShuffleVector instruction.
152 static unsigned getAltOpcode(unsigned Op) {
153   switch (Op) {
154   case Instruction::FAdd:
155     return Instruction::FSub;
156   case Instruction::FSub:
157     return Instruction::FAdd;
158   case Instruction::Add:
159     return Instruction::Sub;
160   case Instruction::Sub:
161     return Instruction::Add;
162   default:
163     return 0;
164   }
165 }
166
167 ///\returns bool representing if Opcode \p Op can be part
168 /// of an alternate sequence which can later be merged as
169 /// a ShuffleVector instruction.
170 static bool canCombineAsAltInst(unsigned Op) {
171   if (Op == Instruction::FAdd || Op == Instruction::FSub ||
172       Op == Instruction::Sub || Op == Instruction::Add)
173     return true;
174   return false;
175 }
176
177 /// \returns ShuffleVector instruction if instructions in \p VL have
178 ///  alternate fadd,fsub / fsub,fadd/add,sub/sub,add sequence.
179 /// (i.e. e.g. opcodes of fadd,fsub,fadd,fsub...)
180 static unsigned isAltInst(ArrayRef<Value *> VL) {
181   Instruction *I0 = dyn_cast<Instruction>(VL[0]);
182   unsigned Opcode = I0->getOpcode();
183   unsigned AltOpcode = getAltOpcode(Opcode);
184   for (int i = 1, e = VL.size(); i < e; i++) {
185     Instruction *I = dyn_cast<Instruction>(VL[i]);
186     if (!I || I->getOpcode() != ((i & 1) ? AltOpcode : Opcode))
187       return 0;
188   }
189   return Instruction::ShuffleVector;
190 }
191
192 /// \returns The opcode if all of the Instructions in \p VL have the same
193 /// opcode, or zero.
194 static unsigned getSameOpcode(ArrayRef<Value *> VL) {
195   Instruction *I0 = dyn_cast<Instruction>(VL[0]);
196   if (!I0)
197     return 0;
198   unsigned Opcode = I0->getOpcode();
199   for (int i = 1, e = VL.size(); i < e; i++) {
200     Instruction *I = dyn_cast<Instruction>(VL[i]);
201     if (!I || Opcode != I->getOpcode()) {
202       if (canCombineAsAltInst(Opcode) && i == 1)
203         return isAltInst(VL);
204       return 0;
205     }
206   }
207   return Opcode;
208 }
209
210 /// Get the intersection (logical and) of all of the potential IR flags
211 /// of each scalar operation (VL) that will be converted into a vector (I).
212 /// Flag set: NSW, NUW, exact, and all of fast-math.
213 static void propagateIRFlags(Value *I, ArrayRef<Value *> VL) {
214   if (auto *VecOp = dyn_cast<BinaryOperator>(I)) {
215     if (auto *Intersection = dyn_cast<BinaryOperator>(VL[0])) {
216       // Intersection is initialized to the 0th scalar,
217       // so start counting from index '1'.
218       for (int i = 1, e = VL.size(); i < e; ++i) {
219         if (auto *Scalar = dyn_cast<BinaryOperator>(VL[i]))
220           Intersection->andIRFlags(Scalar);
221       }
222       VecOp->copyIRFlags(Intersection);
223     }
224   }
225 }
226   
227 /// \returns \p I after propagating metadata from \p VL.
228 static Instruction *propagateMetadata(Instruction *I, ArrayRef<Value *> VL) {
229   Instruction *I0 = cast<Instruction>(VL[0]);
230   SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
231   I0->getAllMetadataOtherThanDebugLoc(Metadata);
232
233   for (unsigned i = 0, n = Metadata.size(); i != n; ++i) {
234     unsigned Kind = Metadata[i].first;
235     MDNode *MD = Metadata[i].second;
236
237     for (int i = 1, e = VL.size(); MD && i != e; i++) {
238       Instruction *I = cast<Instruction>(VL[i]);
239       MDNode *IMD = I->getMetadata(Kind);
240
241       switch (Kind) {
242       default:
243         MD = nullptr; // Remove unknown metadata
244         break;
245       case LLVMContext::MD_tbaa:
246         MD = MDNode::getMostGenericTBAA(MD, IMD);
247         break;
248       case LLVMContext::MD_alias_scope:
249         MD = MDNode::getMostGenericAliasScope(MD, IMD);
250         break;
251       case LLVMContext::MD_noalias:
252         MD = MDNode::intersect(MD, IMD);
253         break;
254       case LLVMContext::MD_fpmath:
255         MD = MDNode::getMostGenericFPMath(MD, IMD);
256         break;
257       case LLVMContext::MD_nontemporal:
258         MD = MDNode::intersect(MD, IMD);
259         break;
260       }
261     }
262     I->setMetadata(Kind, MD);
263   }
264   return I;
265 }
266
267 /// \returns The type that all of the values in \p VL have or null if there
268 /// are different types.
269 static Type* getSameType(ArrayRef<Value *> VL) {
270   Type *Ty = VL[0]->getType();
271   for (int i = 1, e = VL.size(); i < e; i++)
272     if (VL[i]->getType() != Ty)
273       return nullptr;
274
275   return Ty;
276 }
277
278 /// \returns True if the ExtractElement instructions in VL can be vectorized
279 /// to use the original vector.
280 static bool CanReuseExtract(ArrayRef<Value *> VL) {
281   assert(Instruction::ExtractElement == getSameOpcode(VL) && "Invalid opcode");
282   // Check if all of the extracts come from the same vector and from the
283   // correct offset.
284   Value *VL0 = VL[0];
285   ExtractElementInst *E0 = cast<ExtractElementInst>(VL0);
286   Value *Vec = E0->getOperand(0);
287
288   // We have to extract from the same vector type.
289   unsigned NElts = Vec->getType()->getVectorNumElements();
290
291   if (NElts != VL.size())
292     return false;
293
294   // Check that all of the indices extract from the correct offset.
295   ConstantInt *CI = dyn_cast<ConstantInt>(E0->getOperand(1));
296   if (!CI || CI->getZExtValue())
297     return false;
298
299   for (unsigned i = 1, e = VL.size(); i < e; ++i) {
300     ExtractElementInst *E = cast<ExtractElementInst>(VL[i]);
301     ConstantInt *CI = dyn_cast<ConstantInt>(E->getOperand(1));
302
303     if (!CI || CI->getZExtValue() != i || E->getOperand(0) != Vec)
304       return false;
305   }
306
307   return true;
308 }
309
310 /// \returns True if in-tree use also needs extract. This refers to
311 /// possible scalar operand in vectorized instruction.
312 static bool InTreeUserNeedToExtract(Value *Scalar, Instruction *UserInst,
313                                     TargetLibraryInfo *TLI) {
314
315   unsigned Opcode = UserInst->getOpcode();
316   switch (Opcode) {
317   case Instruction::Load: {
318     LoadInst *LI = cast<LoadInst>(UserInst);
319     return (LI->getPointerOperand() == Scalar);
320   }
321   case Instruction::Store: {
322     StoreInst *SI = cast<StoreInst>(UserInst);
323     return (SI->getPointerOperand() == Scalar);
324   }
325   case Instruction::Call: {
326     CallInst *CI = cast<CallInst>(UserInst);
327     Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
328     if (hasVectorInstrinsicScalarOpd(ID, 1)) {
329       return (CI->getArgOperand(1) == Scalar);
330     }
331   }
332   default:
333     return false;
334   }
335 }
336
337 /// \returns the AA location that is being access by the instruction.
338 static MemoryLocation getLocation(Instruction *I, AliasAnalysis *AA) {
339   if (StoreInst *SI = dyn_cast<StoreInst>(I))
340     return MemoryLocation::get(SI);
341   if (LoadInst *LI = dyn_cast<LoadInst>(I))
342     return MemoryLocation::get(LI);
343   return MemoryLocation();
344 }
345
346 /// \returns True if the instruction is not a volatile or atomic load/store.
347 static bool isSimple(Instruction *I) {
348   if (LoadInst *LI = dyn_cast<LoadInst>(I))
349     return LI->isSimple();
350   if (StoreInst *SI = dyn_cast<StoreInst>(I))
351     return SI->isSimple();
352   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I))
353     return !MI->isVolatile();
354   return true;
355 }
356
357 /// Bottom Up SLP Vectorizer.
358 class BoUpSLP {
359 public:
360   typedef SmallVector<Value *, 8> ValueList;
361   typedef SmallVector<Instruction *, 16> InstrList;
362   typedef SmallPtrSet<Value *, 16> ValueSet;
363   typedef SmallVector<StoreInst *, 8> StoreList;
364
365   BoUpSLP(Function *Func, ScalarEvolution *Se, TargetTransformInfo *Tti,
366           TargetLibraryInfo *TLi, AliasAnalysis *Aa, LoopInfo *Li,
367           DominatorTree *Dt, AssumptionCache *AC)
368       : NumLoadsWantToKeepOrder(0), NumLoadsWantToChangeOrder(0), F(Func),
369         SE(Se), TTI(Tti), TLI(TLi), AA(Aa), LI(Li), DT(Dt),
370         Builder(Se->getContext()) {
371     CodeMetrics::collectEphemeralValues(F, AC, EphValues);
372   }
373
374   /// \brief Vectorize the tree that starts with the elements in \p VL.
375   /// Returns the vectorized root.
376   Value *vectorizeTree();
377
378   /// \returns the cost incurred by unwanted spills and fills, caused by
379   /// holding live values over call sites.
380   int getSpillCost();
381
382   /// \returns the vectorization cost of the subtree that starts at \p VL.
383   /// A negative number means that this is profitable.
384   int getTreeCost();
385
386   /// Construct a vectorizable tree that starts at \p Roots, ignoring users for
387   /// the purpose of scheduling and extraction in the \p UserIgnoreLst.
388   void buildTree(ArrayRef<Value *> Roots,
389                  ArrayRef<Value *> UserIgnoreLst = None);
390
391   /// Clear the internal data structures that are created by 'buildTree'.
392   void deleteTree() {
393     VectorizableTree.clear();
394     ScalarToTreeEntry.clear();
395     MustGather.clear();
396     ExternalUses.clear();
397     NumLoadsWantToKeepOrder = 0;
398     NumLoadsWantToChangeOrder = 0;
399     for (auto &Iter : BlocksSchedules) {
400       BlockScheduling *BS = Iter.second.get();
401       BS->clear();
402     }
403   }
404
405   /// \returns true if the memory operations A and B are consecutive.
406   bool isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL);
407
408   /// \brief Perform LICM and CSE on the newly generated gather sequences.
409   void optimizeGatherSequence();
410
411   /// \returns true if it is beneficial to reverse the vector order.
412   bool shouldReorder() const {
413     return NumLoadsWantToChangeOrder > NumLoadsWantToKeepOrder;
414   }
415
416 private:
417   struct TreeEntry;
418
419   /// \returns the cost of the vectorizable entry.
420   int getEntryCost(TreeEntry *E);
421
422   /// This is the recursive part of buildTree.
423   void buildTree_rec(ArrayRef<Value *> Roots, unsigned Depth);
424
425   /// Vectorize a single entry in the tree.
426   Value *vectorizeTree(TreeEntry *E);
427
428   /// Vectorize a single entry in the tree, starting in \p VL.
429   Value *vectorizeTree(ArrayRef<Value *> VL);
430
431   /// \returns the pointer to the vectorized value if \p VL is already
432   /// vectorized, or NULL. They may happen in cycles.
433   Value *alreadyVectorized(ArrayRef<Value *> VL) const;
434
435   /// \brief Take the pointer operand from the Load/Store instruction.
436   /// \returns NULL if this is not a valid Load/Store instruction.
437   static Value *getPointerOperand(Value *I);
438
439   /// \brief Take the address space operand from the Load/Store instruction.
440   /// \returns -1 if this is not a valid Load/Store instruction.
441   static unsigned getAddressSpaceOperand(Value *I);
442
443   /// \returns the scalarization cost for this type. Scalarization in this
444   /// context means the creation of vectors from a group of scalars.
445   int getGatherCost(Type *Ty);
446
447   /// \returns the scalarization cost for this list of values. Assuming that
448   /// this subtree gets vectorized, we may need to extract the values from the
449   /// roots. This method calculates the cost of extracting the values.
450   int getGatherCost(ArrayRef<Value *> VL);
451
452   /// \brief Set the Builder insert point to one after the last instruction in
453   /// the bundle
454   void setInsertPointAfterBundle(ArrayRef<Value *> VL);
455
456   /// \returns a vector from a collection of scalars in \p VL.
457   Value *Gather(ArrayRef<Value *> VL, VectorType *Ty);
458
459   /// \returns whether the VectorizableTree is fully vectorizable and will
460   /// be beneficial even the tree height is tiny.
461   bool isFullyVectorizableTinyTree();
462
463   /// \reorder commutative operands in alt shuffle if they result in
464   ///  vectorized code.
465   void reorderAltShuffleOperands(ArrayRef<Value *> VL,
466                                  SmallVectorImpl<Value *> &Left,
467                                  SmallVectorImpl<Value *> &Right);
468   /// \reorder commutative operands to get better probability of
469   /// generating vectorized code.
470   void reorderInputsAccordingToOpcode(ArrayRef<Value *> VL,
471                                       SmallVectorImpl<Value *> &Left,
472                                       SmallVectorImpl<Value *> &Right);
473   struct TreeEntry {
474     TreeEntry() : Scalars(), VectorizedValue(nullptr),
475     NeedToGather(0) {}
476
477     /// \returns true if the scalars in VL are equal to this entry.
478     bool isSame(ArrayRef<Value *> VL) const {
479       assert(VL.size() == Scalars.size() && "Invalid size");
480       return std::equal(VL.begin(), VL.end(), Scalars.begin());
481     }
482
483     /// A vector of scalars.
484     ValueList Scalars;
485
486     /// The Scalars are vectorized into this value. It is initialized to Null.
487     Value *VectorizedValue;
488
489     /// Do we need to gather this sequence ?
490     bool NeedToGather;
491   };
492
493   /// Create a new VectorizableTree entry.
494   TreeEntry *newTreeEntry(ArrayRef<Value *> VL, bool Vectorized) {
495     VectorizableTree.emplace_back();
496     int idx = VectorizableTree.size() - 1;
497     TreeEntry *Last = &VectorizableTree[idx];
498     Last->Scalars.insert(Last->Scalars.begin(), VL.begin(), VL.end());
499     Last->NeedToGather = !Vectorized;
500     if (Vectorized) {
501       for (int i = 0, e = VL.size(); i != e; ++i) {
502         assert(!ScalarToTreeEntry.count(VL[i]) && "Scalar already in tree!");
503         ScalarToTreeEntry[VL[i]] = idx;
504       }
505     } else {
506       MustGather.insert(VL.begin(), VL.end());
507     }
508     return Last;
509   }
510   
511   /// -- Vectorization State --
512   /// Holds all of the tree entries.
513   std::vector<TreeEntry> VectorizableTree;
514
515   /// Maps a specific scalar to its tree entry.
516   SmallDenseMap<Value*, int> ScalarToTreeEntry;
517
518   /// A list of scalars that we found that we need to keep as scalars.
519   ValueSet MustGather;
520
521   /// This POD struct describes one external user in the vectorized tree.
522   struct ExternalUser {
523     ExternalUser (Value *S, llvm::User *U, int L) :
524       Scalar(S), User(U), Lane(L){}
525     // Which scalar in our function.
526     Value *Scalar;
527     // Which user that uses the scalar.
528     llvm::User *User;
529     // Which lane does the scalar belong to.
530     int Lane;
531   };
532   typedef SmallVector<ExternalUser, 16> UserList;
533
534   /// Checks if two instructions may access the same memory.
535   ///
536   /// \p Loc1 is the location of \p Inst1. It is passed explicitly because it
537   /// is invariant in the calling loop.
538   bool isAliased(const MemoryLocation &Loc1, Instruction *Inst1,
539                  Instruction *Inst2) {
540
541     // First check if the result is already in the cache.
542     AliasCacheKey key = std::make_pair(Inst1, Inst2);
543     Optional<bool> &result = AliasCache[key];
544     if (result.hasValue()) {
545       return result.getValue();
546     }
547     MemoryLocation Loc2 = getLocation(Inst2, AA);
548     bool aliased = true;
549     if (Loc1.Ptr && Loc2.Ptr && isSimple(Inst1) && isSimple(Inst2)) {
550       // Do the alias check.
551       aliased = AA->alias(Loc1, Loc2);
552     }
553     // Store the result in the cache.
554     result = aliased;
555     return aliased;
556   }
557
558   typedef std::pair<Instruction *, Instruction *> AliasCacheKey;
559
560   /// Cache for alias results.
561   /// TODO: consider moving this to the AliasAnalysis itself.
562   DenseMap<AliasCacheKey, Optional<bool>> AliasCache;
563
564   /// Removes an instruction from its block and eventually deletes it.
565   /// It's like Instruction::eraseFromParent() except that the actual deletion
566   /// is delayed until BoUpSLP is destructed.
567   /// This is required to ensure that there are no incorrect collisions in the
568   /// AliasCache, which can happen if a new instruction is allocated at the
569   /// same address as a previously deleted instruction.
570   void eraseInstruction(Instruction *I) {
571     I->removeFromParent();
572     I->dropAllReferences();
573     DeletedInstructions.push_back(std::unique_ptr<Instruction>(I));
574   }
575
576   /// Temporary store for deleted instructions. Instructions will be deleted
577   /// eventually when the BoUpSLP is destructed.
578   SmallVector<std::unique_ptr<Instruction>, 8> DeletedInstructions;
579
580   /// A list of values that need to extracted out of the tree.
581   /// This list holds pairs of (Internal Scalar : External User).
582   UserList ExternalUses;
583
584   /// Values used only by @llvm.assume calls.
585   SmallPtrSet<const Value *, 32> EphValues;
586
587   /// Holds all of the instructions that we gathered.
588   SetVector<Instruction *> GatherSeq;
589   /// A list of blocks that we are going to CSE.
590   SetVector<BasicBlock *> CSEBlocks;
591
592   /// Contains all scheduling relevant data for an instruction.
593   /// A ScheduleData either represents a single instruction or a member of an
594   /// instruction bundle (= a group of instructions which is combined into a
595   /// vector instruction).
596   struct ScheduleData {
597
598     // The initial value for the dependency counters. It means that the
599     // dependencies are not calculated yet.
600     enum { InvalidDeps = -1 };
601
602     ScheduleData()
603         : Inst(nullptr), FirstInBundle(nullptr), NextInBundle(nullptr),
604           NextLoadStore(nullptr), SchedulingRegionID(0), SchedulingPriority(0),
605           Dependencies(InvalidDeps), UnscheduledDeps(InvalidDeps),
606           UnscheduledDepsInBundle(InvalidDeps), IsScheduled(false) {}
607
608     void init(int BlockSchedulingRegionID) {
609       FirstInBundle = this;
610       NextInBundle = nullptr;
611       NextLoadStore = nullptr;
612       IsScheduled = false;
613       SchedulingRegionID = BlockSchedulingRegionID;
614       UnscheduledDepsInBundle = UnscheduledDeps;
615       clearDependencies();
616     }
617
618     /// Returns true if the dependency information has been calculated.
619     bool hasValidDependencies() const { return Dependencies != InvalidDeps; }
620
621     /// Returns true for single instructions and for bundle representatives
622     /// (= the head of a bundle).
623     bool isSchedulingEntity() const { return FirstInBundle == this; }
624
625     /// Returns true if it represents an instruction bundle and not only a
626     /// single instruction.
627     bool isPartOfBundle() const {
628       return NextInBundle != nullptr || FirstInBundle != this;
629     }
630
631     /// Returns true if it is ready for scheduling, i.e. it has no more
632     /// unscheduled depending instructions/bundles.
633     bool isReady() const {
634       assert(isSchedulingEntity() &&
635              "can't consider non-scheduling entity for ready list");
636       return UnscheduledDepsInBundle == 0 && !IsScheduled;
637     }
638
639     /// Modifies the number of unscheduled dependencies, also updating it for
640     /// the whole bundle.
641     int incrementUnscheduledDeps(int Incr) {
642       UnscheduledDeps += Incr;
643       return FirstInBundle->UnscheduledDepsInBundle += Incr;
644     }
645
646     /// Sets the number of unscheduled dependencies to the number of
647     /// dependencies.
648     void resetUnscheduledDeps() {
649       incrementUnscheduledDeps(Dependencies - UnscheduledDeps);
650     }
651
652     /// Clears all dependency information.
653     void clearDependencies() {
654       Dependencies = InvalidDeps;
655       resetUnscheduledDeps();
656       MemoryDependencies.clear();
657     }
658
659     void dump(raw_ostream &os) const {
660       if (!isSchedulingEntity()) {
661         os << "/ " << *Inst;
662       } else if (NextInBundle) {
663         os << '[' << *Inst;
664         ScheduleData *SD = NextInBundle;
665         while (SD) {
666           os << ';' << *SD->Inst;
667           SD = SD->NextInBundle;
668         }
669         os << ']';
670       } else {
671         os << *Inst;
672       }
673     }
674
675     Instruction *Inst;
676
677     /// Points to the head in an instruction bundle (and always to this for
678     /// single instructions).
679     ScheduleData *FirstInBundle;
680
681     /// Single linked list of all instructions in a bundle. Null if it is a
682     /// single instruction.
683     ScheduleData *NextInBundle;
684
685     /// Single linked list of all memory instructions (e.g. load, store, call)
686     /// in the block - until the end of the scheduling region.
687     ScheduleData *NextLoadStore;
688
689     /// The dependent memory instructions.
690     /// This list is derived on demand in calculateDependencies().
691     SmallVector<ScheduleData *, 4> MemoryDependencies;
692
693     /// This ScheduleData is in the current scheduling region if this matches
694     /// the current SchedulingRegionID of BlockScheduling.
695     int SchedulingRegionID;
696
697     /// Used for getting a "good" final ordering of instructions.
698     int SchedulingPriority;
699
700     /// The number of dependencies. Constitutes of the number of users of the
701     /// instruction plus the number of dependent memory instructions (if any).
702     /// This value is calculated on demand.
703     /// If InvalidDeps, the number of dependencies is not calculated yet.
704     ///
705     int Dependencies;
706
707     /// The number of dependencies minus the number of dependencies of scheduled
708     /// instructions. As soon as this is zero, the instruction/bundle gets ready
709     /// for scheduling.
710     /// Note that this is negative as long as Dependencies is not calculated.
711     int UnscheduledDeps;
712
713     /// The sum of UnscheduledDeps in a bundle. Equals to UnscheduledDeps for
714     /// single instructions.
715     int UnscheduledDepsInBundle;
716
717     /// True if this instruction is scheduled (or considered as scheduled in the
718     /// dry-run).
719     bool IsScheduled;
720   };
721
722 #ifndef NDEBUG
723   friend raw_ostream &operator<<(raw_ostream &os,
724                                  const BoUpSLP::ScheduleData &SD);
725 #endif
726
727   /// Contains all scheduling data for a basic block.
728   ///
729   struct BlockScheduling {
730
731     BlockScheduling(BasicBlock *BB)
732         : BB(BB), ChunkSize(BB->size()), ChunkPos(ChunkSize),
733           ScheduleStart(nullptr), ScheduleEnd(nullptr),
734           FirstLoadStoreInRegion(nullptr), LastLoadStoreInRegion(nullptr),
735           ScheduleRegionSize(0),
736           ScheduleRegionSizeLimit(ScheduleRegionSizeBudget),
737           // Make sure that the initial SchedulingRegionID is greater than the
738           // initial SchedulingRegionID in ScheduleData (which is 0).
739           SchedulingRegionID(1) {}
740
741     void clear() {
742       ReadyInsts.clear();
743       ScheduleStart = nullptr;
744       ScheduleEnd = nullptr;
745       FirstLoadStoreInRegion = nullptr;
746       LastLoadStoreInRegion = nullptr;
747
748       // Reduce the maximum schedule region size by the size of the
749       // previous scheduling run.
750       ScheduleRegionSizeLimit -= ScheduleRegionSize;
751       if (ScheduleRegionSizeLimit < MinScheduleRegionSize)
752         ScheduleRegionSizeLimit = MinScheduleRegionSize;
753       ScheduleRegionSize = 0;
754
755       // Make a new scheduling region, i.e. all existing ScheduleData is not
756       // in the new region yet.
757       ++SchedulingRegionID;
758     }
759
760     ScheduleData *getScheduleData(Value *V) {
761       ScheduleData *SD = ScheduleDataMap[V];
762       if (SD && SD->SchedulingRegionID == SchedulingRegionID)
763         return SD;
764       return nullptr;
765     }
766
767     bool isInSchedulingRegion(ScheduleData *SD) {
768       return SD->SchedulingRegionID == SchedulingRegionID;
769     }
770
771     /// Marks an instruction as scheduled and puts all dependent ready
772     /// instructions into the ready-list.
773     template <typename ReadyListType>
774     void schedule(ScheduleData *SD, ReadyListType &ReadyList) {
775       SD->IsScheduled = true;
776       DEBUG(dbgs() << "SLP:   schedule " << *SD << "\n");
777
778       ScheduleData *BundleMember = SD;
779       while (BundleMember) {
780         // Handle the def-use chain dependencies.
781         for (Use &U : BundleMember->Inst->operands()) {
782           ScheduleData *OpDef = getScheduleData(U.get());
783           if (OpDef && OpDef->hasValidDependencies() &&
784               OpDef->incrementUnscheduledDeps(-1) == 0) {
785             // There are no more unscheduled dependencies after decrementing,
786             // so we can put the dependent instruction into the ready list.
787             ScheduleData *DepBundle = OpDef->FirstInBundle;
788             assert(!DepBundle->IsScheduled &&
789                    "already scheduled bundle gets ready");
790             ReadyList.insert(DepBundle);
791             DEBUG(dbgs() << "SLP:    gets ready (def): " << *DepBundle << "\n");
792           }
793         }
794         // Handle the memory dependencies.
795         for (ScheduleData *MemoryDepSD : BundleMember->MemoryDependencies) {
796           if (MemoryDepSD->incrementUnscheduledDeps(-1) == 0) {
797             // There are no more unscheduled dependencies after decrementing,
798             // so we can put the dependent instruction into the ready list.
799             ScheduleData *DepBundle = MemoryDepSD->FirstInBundle;
800             assert(!DepBundle->IsScheduled &&
801                    "already scheduled bundle gets ready");
802             ReadyList.insert(DepBundle);
803             DEBUG(dbgs() << "SLP:    gets ready (mem): " << *DepBundle << "\n");
804           }
805         }
806         BundleMember = BundleMember->NextInBundle;
807       }
808     }
809
810     /// Put all instructions into the ReadyList which are ready for scheduling.
811     template <typename ReadyListType>
812     void initialFillReadyList(ReadyListType &ReadyList) {
813       for (auto *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) {
814         ScheduleData *SD = getScheduleData(I);
815         if (SD->isSchedulingEntity() && SD->isReady()) {
816           ReadyList.insert(SD);
817           DEBUG(dbgs() << "SLP:    initially in ready list: " << *I << "\n");
818         }
819       }
820     }
821
822     /// Checks if a bundle of instructions can be scheduled, i.e. has no
823     /// cyclic dependencies. This is only a dry-run, no instructions are
824     /// actually moved at this stage.
825     bool tryScheduleBundle(ArrayRef<Value *> VL, BoUpSLP *SLP);
826
827     /// Un-bundles a group of instructions.
828     void cancelScheduling(ArrayRef<Value *> VL);
829
830     /// Extends the scheduling region so that V is inside the region.
831     /// \returns true if the region size is within the limit.
832     bool extendSchedulingRegion(Value *V);
833
834     /// Initialize the ScheduleData structures for new instructions in the
835     /// scheduling region.
836     void initScheduleData(Instruction *FromI, Instruction *ToI,
837                           ScheduleData *PrevLoadStore,
838                           ScheduleData *NextLoadStore);
839
840     /// Updates the dependency information of a bundle and of all instructions/
841     /// bundles which depend on the original bundle.
842     void calculateDependencies(ScheduleData *SD, bool InsertInReadyList,
843                                BoUpSLP *SLP);
844
845     /// Sets all instruction in the scheduling region to un-scheduled.
846     void resetSchedule();
847
848     BasicBlock *BB;
849
850     /// Simple memory allocation for ScheduleData.
851     std::vector<std::unique_ptr<ScheduleData[]>> ScheduleDataChunks;
852
853     /// The size of a ScheduleData array in ScheduleDataChunks.
854     int ChunkSize;
855
856     /// The allocator position in the current chunk, which is the last entry
857     /// of ScheduleDataChunks.
858     int ChunkPos;
859
860     /// Attaches ScheduleData to Instruction.
861     /// Note that the mapping survives during all vectorization iterations, i.e.
862     /// ScheduleData structures are recycled.
863     DenseMap<Value *, ScheduleData *> ScheduleDataMap;
864
865     struct ReadyList : SmallVector<ScheduleData *, 8> {
866       void insert(ScheduleData *SD) { push_back(SD); }
867     };
868
869     /// The ready-list for scheduling (only used for the dry-run).
870     ReadyList ReadyInsts;
871
872     /// The first instruction of the scheduling region.
873     Instruction *ScheduleStart;
874
875     /// The first instruction _after_ the scheduling region.
876     Instruction *ScheduleEnd;
877
878     /// The first memory accessing instruction in the scheduling region
879     /// (can be null).
880     ScheduleData *FirstLoadStoreInRegion;
881
882     /// The last memory accessing instruction in the scheduling region
883     /// (can be null).
884     ScheduleData *LastLoadStoreInRegion;
885
886     /// The current size of the scheduling region.
887     int ScheduleRegionSize;
888     
889     /// The maximum size allowed for the scheduling region.
890     int ScheduleRegionSizeLimit;
891
892     /// The ID of the scheduling region. For a new vectorization iteration this
893     /// is incremented which "removes" all ScheduleData from the region.
894     int SchedulingRegionID;
895   };
896
897   /// Attaches the BlockScheduling structures to basic blocks.
898   MapVector<BasicBlock *, std::unique_ptr<BlockScheduling>> BlocksSchedules;
899
900   /// Performs the "real" scheduling. Done before vectorization is actually
901   /// performed in a basic block.
902   void scheduleBlock(BlockScheduling *BS);
903
904   /// List of users to ignore during scheduling and that don't need extracting.
905   ArrayRef<Value *> UserIgnoreList;
906
907   // Number of load-bundles, which contain consecutive loads.
908   int NumLoadsWantToKeepOrder;
909
910   // Number of load-bundles of size 2, which are consecutive loads if reversed.
911   int NumLoadsWantToChangeOrder;
912
913   // Analysis and block reference.
914   Function *F;
915   ScalarEvolution *SE;
916   TargetTransformInfo *TTI;
917   TargetLibraryInfo *TLI;
918   AliasAnalysis *AA;
919   LoopInfo *LI;
920   DominatorTree *DT;
921   /// Instruction builder to construct the vectorized tree.
922   IRBuilder<> Builder;
923 };
924
925 #ifndef NDEBUG
926 raw_ostream &operator<<(raw_ostream &os, const BoUpSLP::ScheduleData &SD) {
927   SD.dump(os);
928   return os;
929 }
930 #endif
931
932 void BoUpSLP::buildTree(ArrayRef<Value *> Roots,
933                         ArrayRef<Value *> UserIgnoreLst) {
934   deleteTree();
935   UserIgnoreList = UserIgnoreLst;
936   if (!getSameType(Roots))
937     return;
938   buildTree_rec(Roots, 0);
939
940   // Collect the values that we need to extract from the tree.
941   for (int EIdx = 0, EE = VectorizableTree.size(); EIdx < EE; ++EIdx) {
942     TreeEntry *Entry = &VectorizableTree[EIdx];
943
944     // For each lane:
945     for (int Lane = 0, LE = Entry->Scalars.size(); Lane != LE; ++Lane) {
946       Value *Scalar = Entry->Scalars[Lane];
947
948       // No need to handle users of gathered values.
949       if (Entry->NeedToGather)
950         continue;
951
952       for (User *U : Scalar->users()) {
953         DEBUG(dbgs() << "SLP: Checking user:" << *U << ".\n");
954
955         Instruction *UserInst = dyn_cast<Instruction>(U);
956         if (!UserInst)
957           continue;
958
959         // Skip in-tree scalars that become vectors
960         if (ScalarToTreeEntry.count(U)) {
961           int Idx = ScalarToTreeEntry[U];
962           TreeEntry *UseEntry = &VectorizableTree[Idx];
963           Value *UseScalar = UseEntry->Scalars[0];
964           // Some in-tree scalars will remain as scalar in vectorized
965           // instructions. If that is the case, the one in Lane 0 will
966           // be used.
967           if (UseScalar != U ||
968               !InTreeUserNeedToExtract(Scalar, UserInst, TLI)) {
969             DEBUG(dbgs() << "SLP: \tInternal user will be removed:" << *U
970                          << ".\n");
971             assert(!VectorizableTree[Idx].NeedToGather && "Bad state");
972             continue;
973           }
974         }
975
976         // Ignore users in the user ignore list.
977         if (std::find(UserIgnoreList.begin(), UserIgnoreList.end(), UserInst) !=
978             UserIgnoreList.end())
979           continue;
980
981         DEBUG(dbgs() << "SLP: Need to extract:" << *U << " from lane " <<
982               Lane << " from " << *Scalar << ".\n");
983         ExternalUses.push_back(ExternalUser(Scalar, U, Lane));
984       }
985     }
986   }
987 }
988
989
990 void BoUpSLP::buildTree_rec(ArrayRef<Value *> VL, unsigned Depth) {
991   bool SameTy = getSameType(VL); (void)SameTy;
992   bool isAltShuffle = false;
993   assert(SameTy && "Invalid types!");
994
995   if (Depth == RecursionMaxDepth) {
996     DEBUG(dbgs() << "SLP: Gathering due to max recursion depth.\n");
997     newTreeEntry(VL, false);
998     return;
999   }
1000
1001   // Don't handle vectors.
1002   if (VL[0]->getType()->isVectorTy()) {
1003     DEBUG(dbgs() << "SLP: Gathering due to vector type.\n");
1004     newTreeEntry(VL, false);
1005     return;
1006   }
1007
1008   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
1009     if (SI->getValueOperand()->getType()->isVectorTy()) {
1010       DEBUG(dbgs() << "SLP: Gathering due to store vector type.\n");
1011       newTreeEntry(VL, false);
1012       return;
1013     }
1014   unsigned Opcode = getSameOpcode(VL);
1015
1016   // Check that this shuffle vector refers to the alternate
1017   // sequence of opcodes.
1018   if (Opcode == Instruction::ShuffleVector) {
1019     Instruction *I0 = dyn_cast<Instruction>(VL[0]);
1020     unsigned Op = I0->getOpcode();
1021     if (Op != Instruction::ShuffleVector)
1022       isAltShuffle = true;
1023   }
1024
1025   // If all of the operands are identical or constant we have a simple solution.
1026   if (allConstant(VL) || isSplat(VL) || !getSameBlock(VL) || !Opcode) {
1027     DEBUG(dbgs() << "SLP: Gathering due to C,S,B,O. \n");
1028     newTreeEntry(VL, false);
1029     return;
1030   }
1031
1032   // We now know that this is a vector of instructions of the same type from
1033   // the same block.
1034
1035   // Don't vectorize ephemeral values.
1036   for (unsigned i = 0, e = VL.size(); i != e; ++i) {
1037     if (EphValues.count(VL[i])) {
1038       DEBUG(dbgs() << "SLP: The instruction (" << *VL[i] <<
1039             ") is ephemeral.\n");
1040       newTreeEntry(VL, false);
1041       return;
1042     }
1043   }
1044
1045   // Check if this is a duplicate of another entry.
1046   if (ScalarToTreeEntry.count(VL[0])) {
1047     int Idx = ScalarToTreeEntry[VL[0]];
1048     TreeEntry *E = &VectorizableTree[Idx];
1049     for (unsigned i = 0, e = VL.size(); i != e; ++i) {
1050       DEBUG(dbgs() << "SLP: \tChecking bundle: " << *VL[i] << ".\n");
1051       if (E->Scalars[i] != VL[i]) {
1052         DEBUG(dbgs() << "SLP: Gathering due to partial overlap.\n");
1053         newTreeEntry(VL, false);
1054         return;
1055       }
1056     }
1057     DEBUG(dbgs() << "SLP: Perfect diamond merge at " << *VL[0] << ".\n");
1058     return;
1059   }
1060
1061   // Check that none of the instructions in the bundle are already in the tree.
1062   for (unsigned i = 0, e = VL.size(); i != e; ++i) {
1063     if (ScalarToTreeEntry.count(VL[i])) {
1064       DEBUG(dbgs() << "SLP: The instruction (" << *VL[i] <<
1065             ") is already in tree.\n");
1066       newTreeEntry(VL, false);
1067       return;
1068     }
1069   }
1070
1071   // If any of the scalars is marked as a value that needs to stay scalar then
1072   // we need to gather the scalars.
1073   for (unsigned i = 0, e = VL.size(); i != e; ++i) {
1074     if (MustGather.count(VL[i])) {
1075       DEBUG(dbgs() << "SLP: Gathering due to gathered scalar.\n");
1076       newTreeEntry(VL, false);
1077       return;
1078     }
1079   }
1080
1081   // Check that all of the users of the scalars that we want to vectorize are
1082   // schedulable.
1083   Instruction *VL0 = cast<Instruction>(VL[0]);
1084   BasicBlock *BB = cast<Instruction>(VL0)->getParent();
1085
1086   if (!DT->isReachableFromEntry(BB)) {
1087     // Don't go into unreachable blocks. They may contain instructions with
1088     // dependency cycles which confuse the final scheduling.
1089     DEBUG(dbgs() << "SLP: bundle in unreachable block.\n");
1090     newTreeEntry(VL, false);
1091     return;
1092   }
1093   
1094   // Check that every instructions appears once in this bundle.
1095   for (unsigned i = 0, e = VL.size(); i < e; ++i)
1096     for (unsigned j = i+1; j < e; ++j)
1097       if (VL[i] == VL[j]) {
1098         DEBUG(dbgs() << "SLP: Scalar used twice in bundle.\n");
1099         newTreeEntry(VL, false);
1100         return;
1101       }
1102
1103   auto &BSRef = BlocksSchedules[BB];
1104   if (!BSRef) {
1105     BSRef = llvm::make_unique<BlockScheduling>(BB);
1106   }
1107   BlockScheduling &BS = *BSRef.get();
1108
1109   if (!BS.tryScheduleBundle(VL, this)) {
1110     DEBUG(dbgs() << "SLP: We are not able to schedule this bundle!\n");
1111     assert((!BS.getScheduleData(VL[0]) ||
1112             !BS.getScheduleData(VL[0])->isPartOfBundle()) &&
1113            "tryScheduleBundle should cancelScheduling on failure");
1114     newTreeEntry(VL, false);
1115     return;
1116   }
1117   DEBUG(dbgs() << "SLP: We are able to schedule this bundle.\n");
1118
1119   switch (Opcode) {
1120     case Instruction::PHI: {
1121       PHINode *PH = dyn_cast<PHINode>(VL0);
1122
1123       // Check for terminator values (e.g. invoke).
1124       for (unsigned j = 0; j < VL.size(); ++j)
1125         for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
1126           TerminatorInst *Term = dyn_cast<TerminatorInst>(
1127               cast<PHINode>(VL[j])->getIncomingValueForBlock(PH->getIncomingBlock(i)));
1128           if (Term) {
1129             DEBUG(dbgs() << "SLP: Need to swizzle PHINodes (TerminatorInst use).\n");
1130             BS.cancelScheduling(VL);
1131             newTreeEntry(VL, false);
1132             return;
1133           }
1134         }
1135
1136       newTreeEntry(VL, true);
1137       DEBUG(dbgs() << "SLP: added a vector of PHINodes.\n");
1138
1139       for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
1140         ValueList Operands;
1141         // Prepare the operand vector.
1142         for (unsigned j = 0; j < VL.size(); ++j)
1143           Operands.push_back(cast<PHINode>(VL[j])->getIncomingValueForBlock(
1144               PH->getIncomingBlock(i)));
1145
1146         buildTree_rec(Operands, Depth + 1);
1147       }
1148       return;
1149     }
1150     case Instruction::ExtractElement: {
1151       bool Reuse = CanReuseExtract(VL);
1152       if (Reuse) {
1153         DEBUG(dbgs() << "SLP: Reusing extract sequence.\n");
1154       } else {
1155         BS.cancelScheduling(VL);
1156       }
1157       newTreeEntry(VL, Reuse);
1158       return;
1159     }
1160     case Instruction::Load: {
1161       // Check that a vectorized load would load the same memory as a scalar
1162       // load.
1163       // For example we don't want vectorize loads that are smaller than 8 bit.
1164       // Even though we have a packed struct {<i2, i2, i2, i2>} LLVM treats
1165       // loading/storing it as an i8 struct. If we vectorize loads/stores from
1166       // such a struct we read/write packed bits disagreeing with the
1167       // unvectorized version.
1168       const DataLayout &DL = F->getParent()->getDataLayout();
1169       Type *ScalarTy = VL[0]->getType();
1170
1171       if (DL.getTypeSizeInBits(ScalarTy) !=
1172           DL.getTypeAllocSizeInBits(ScalarTy)) {
1173         BS.cancelScheduling(VL);
1174         newTreeEntry(VL, false);
1175         DEBUG(dbgs() << "SLP: Gathering loads of non-packed type.\n");
1176         return;
1177       }
1178       // Check if the loads are consecutive or of we need to swizzle them.
1179       for (unsigned i = 0, e = VL.size() - 1; i < e; ++i) {
1180         LoadInst *L = cast<LoadInst>(VL[i]);
1181         if (!L->isSimple()) {
1182           BS.cancelScheduling(VL);
1183           newTreeEntry(VL, false);
1184           DEBUG(dbgs() << "SLP: Gathering non-simple loads.\n");
1185           return;
1186         }
1187
1188         if (!isConsecutiveAccess(VL[i], VL[i + 1], DL)) {
1189           if (VL.size() == 2 && isConsecutiveAccess(VL[1], VL[0], DL)) {
1190             ++NumLoadsWantToChangeOrder;
1191           }
1192           BS.cancelScheduling(VL);
1193           newTreeEntry(VL, false);
1194           DEBUG(dbgs() << "SLP: Gathering non-consecutive loads.\n");
1195           return;
1196         }
1197       }
1198       ++NumLoadsWantToKeepOrder;
1199       newTreeEntry(VL, true);
1200       DEBUG(dbgs() << "SLP: added a vector of loads.\n");
1201       return;
1202     }
1203     case Instruction::ZExt:
1204     case Instruction::SExt:
1205     case Instruction::FPToUI:
1206     case Instruction::FPToSI:
1207     case Instruction::FPExt:
1208     case Instruction::PtrToInt:
1209     case Instruction::IntToPtr:
1210     case Instruction::SIToFP:
1211     case Instruction::UIToFP:
1212     case Instruction::Trunc:
1213     case Instruction::FPTrunc:
1214     case Instruction::BitCast: {
1215       Type *SrcTy = VL0->getOperand(0)->getType();
1216       for (unsigned i = 0; i < VL.size(); ++i) {
1217         Type *Ty = cast<Instruction>(VL[i])->getOperand(0)->getType();
1218         if (Ty != SrcTy || !isValidElementType(Ty)) {
1219           BS.cancelScheduling(VL);
1220           newTreeEntry(VL, false);
1221           DEBUG(dbgs() << "SLP: Gathering casts with different src types.\n");
1222           return;
1223         }
1224       }
1225       newTreeEntry(VL, true);
1226       DEBUG(dbgs() << "SLP: added a vector of casts.\n");
1227
1228       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
1229         ValueList Operands;
1230         // Prepare the operand vector.
1231         for (unsigned j = 0; j < VL.size(); ++j)
1232           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
1233
1234         buildTree_rec(Operands, Depth+1);
1235       }
1236       return;
1237     }
1238     case Instruction::ICmp:
1239     case Instruction::FCmp: {
1240       // Check that all of the compares have the same predicate.
1241       CmpInst::Predicate P0 = cast<CmpInst>(VL0)->getPredicate();
1242       Type *ComparedTy = cast<Instruction>(VL[0])->getOperand(0)->getType();
1243       for (unsigned i = 1, e = VL.size(); i < e; ++i) {
1244         CmpInst *Cmp = cast<CmpInst>(VL[i]);
1245         if (Cmp->getPredicate() != P0 ||
1246             Cmp->getOperand(0)->getType() != ComparedTy) {
1247           BS.cancelScheduling(VL);
1248           newTreeEntry(VL, false);
1249           DEBUG(dbgs() << "SLP: Gathering cmp with different predicate.\n");
1250           return;
1251         }
1252       }
1253
1254       newTreeEntry(VL, true);
1255       DEBUG(dbgs() << "SLP: added a vector of compares.\n");
1256
1257       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
1258         ValueList Operands;
1259         // Prepare the operand vector.
1260         for (unsigned j = 0; j < VL.size(); ++j)
1261           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
1262
1263         buildTree_rec(Operands, Depth+1);
1264       }
1265       return;
1266     }
1267     case Instruction::Select:
1268     case Instruction::Add:
1269     case Instruction::FAdd:
1270     case Instruction::Sub:
1271     case Instruction::FSub:
1272     case Instruction::Mul:
1273     case Instruction::FMul:
1274     case Instruction::UDiv:
1275     case Instruction::SDiv:
1276     case Instruction::FDiv:
1277     case Instruction::URem:
1278     case Instruction::SRem:
1279     case Instruction::FRem:
1280     case Instruction::Shl:
1281     case Instruction::LShr:
1282     case Instruction::AShr:
1283     case Instruction::And:
1284     case Instruction::Or:
1285     case Instruction::Xor: {
1286       newTreeEntry(VL, true);
1287       DEBUG(dbgs() << "SLP: added a vector of bin op.\n");
1288
1289       // Sort operands of the instructions so that each side is more likely to
1290       // have the same opcode.
1291       if (isa<BinaryOperator>(VL0) && VL0->isCommutative()) {
1292         ValueList Left, Right;
1293         reorderInputsAccordingToOpcode(VL, Left, Right);
1294         buildTree_rec(Left, Depth + 1);
1295         buildTree_rec(Right, Depth + 1);
1296         return;
1297       }
1298
1299       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
1300         ValueList Operands;
1301         // Prepare the operand vector.
1302         for (unsigned j = 0; j < VL.size(); ++j)
1303           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
1304
1305         buildTree_rec(Operands, Depth+1);
1306       }
1307       return;
1308     }
1309     case Instruction::GetElementPtr: {
1310       // We don't combine GEPs with complicated (nested) indexing.
1311       for (unsigned j = 0; j < VL.size(); ++j) {
1312         if (cast<Instruction>(VL[j])->getNumOperands() != 2) {
1313           DEBUG(dbgs() << "SLP: not-vectorizable GEP (nested indexes).\n");
1314           BS.cancelScheduling(VL);
1315           newTreeEntry(VL, false);
1316           return;
1317         }
1318       }
1319
1320       // We can't combine several GEPs into one vector if they operate on
1321       // different types.
1322       Type *Ty0 = cast<Instruction>(VL0)->getOperand(0)->getType();
1323       for (unsigned j = 0; j < VL.size(); ++j) {
1324         Type *CurTy = cast<Instruction>(VL[j])->getOperand(0)->getType();
1325         if (Ty0 != CurTy) {
1326           DEBUG(dbgs() << "SLP: not-vectorizable GEP (different types).\n");
1327           BS.cancelScheduling(VL);
1328           newTreeEntry(VL, false);
1329           return;
1330         }
1331       }
1332
1333       // We don't combine GEPs with non-constant indexes.
1334       for (unsigned j = 0; j < VL.size(); ++j) {
1335         auto Op = cast<Instruction>(VL[j])->getOperand(1);
1336         if (!isa<ConstantInt>(Op)) {
1337           DEBUG(
1338               dbgs() << "SLP: not-vectorizable GEP (non-constant indexes).\n");
1339           BS.cancelScheduling(VL);
1340           newTreeEntry(VL, false);
1341           return;
1342         }
1343       }
1344
1345       newTreeEntry(VL, true);
1346       DEBUG(dbgs() << "SLP: added a vector of GEPs.\n");
1347       for (unsigned i = 0, e = 2; i < e; ++i) {
1348         ValueList Operands;
1349         // Prepare the operand vector.
1350         for (unsigned j = 0; j < VL.size(); ++j)
1351           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
1352
1353         buildTree_rec(Operands, Depth + 1);
1354       }
1355       return;
1356     }
1357     case Instruction::Store: {
1358       const DataLayout &DL = F->getParent()->getDataLayout();
1359       // Check if the stores are consecutive or of we need to swizzle them.
1360       for (unsigned i = 0, e = VL.size() - 1; i < e; ++i)
1361         if (!isConsecutiveAccess(VL[i], VL[i + 1], DL)) {
1362           BS.cancelScheduling(VL);
1363           newTreeEntry(VL, false);
1364           DEBUG(dbgs() << "SLP: Non-consecutive store.\n");
1365           return;
1366         }
1367
1368       newTreeEntry(VL, true);
1369       DEBUG(dbgs() << "SLP: added a vector of stores.\n");
1370
1371       ValueList Operands;
1372       for (unsigned j = 0; j < VL.size(); ++j)
1373         Operands.push_back(cast<Instruction>(VL[j])->getOperand(0));
1374
1375       buildTree_rec(Operands, Depth + 1);
1376       return;
1377     }
1378     case Instruction::Call: {
1379       // Check if the calls are all to the same vectorizable intrinsic.
1380       CallInst *CI = cast<CallInst>(VL[0]);
1381       // Check if this is an Intrinsic call or something that can be
1382       // represented by an intrinsic call
1383       Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
1384       if (!isTriviallyVectorizable(ID)) {
1385         BS.cancelScheduling(VL);
1386         newTreeEntry(VL, false);
1387         DEBUG(dbgs() << "SLP: Non-vectorizable call.\n");
1388         return;
1389       }
1390       Function *Int = CI->getCalledFunction();
1391       Value *A1I = nullptr;
1392       if (hasVectorInstrinsicScalarOpd(ID, 1))
1393         A1I = CI->getArgOperand(1);
1394       for (unsigned i = 1, e = VL.size(); i != e; ++i) {
1395         CallInst *CI2 = dyn_cast<CallInst>(VL[i]);
1396         if (!CI2 || CI2->getCalledFunction() != Int ||
1397             getIntrinsicIDForCall(CI2, TLI) != ID) {
1398           BS.cancelScheduling(VL);
1399           newTreeEntry(VL, false);
1400           DEBUG(dbgs() << "SLP: mismatched calls:" << *CI << "!=" << *VL[i]
1401                        << "\n");
1402           return;
1403         }
1404         // ctlz,cttz and powi are special intrinsics whose second argument
1405         // should be same in order for them to be vectorized.
1406         if (hasVectorInstrinsicScalarOpd(ID, 1)) {
1407           Value *A1J = CI2->getArgOperand(1);
1408           if (A1I != A1J) {
1409             BS.cancelScheduling(VL);
1410             newTreeEntry(VL, false);
1411             DEBUG(dbgs() << "SLP: mismatched arguments in call:" << *CI
1412                          << " argument "<< A1I<<"!=" << A1J
1413                          << "\n");
1414             return;
1415           }
1416         }
1417       }
1418
1419       newTreeEntry(VL, true);
1420       for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) {
1421         ValueList Operands;
1422         // Prepare the operand vector.
1423         for (unsigned j = 0; j < VL.size(); ++j) {
1424           CallInst *CI2 = dyn_cast<CallInst>(VL[j]);
1425           Operands.push_back(CI2->getArgOperand(i));
1426         }
1427         buildTree_rec(Operands, Depth + 1);
1428       }
1429       return;
1430     }
1431     case Instruction::ShuffleVector: {
1432       // If this is not an alternate sequence of opcode like add-sub
1433       // then do not vectorize this instruction.
1434       if (!isAltShuffle) {
1435         BS.cancelScheduling(VL);
1436         newTreeEntry(VL, false);
1437         DEBUG(dbgs() << "SLP: ShuffleVector are not vectorized.\n");
1438         return;
1439       }
1440       newTreeEntry(VL, true);
1441       DEBUG(dbgs() << "SLP: added a ShuffleVector op.\n");
1442
1443       // Reorder operands if reordering would enable vectorization.
1444       if (isa<BinaryOperator>(VL0)) {
1445         ValueList Left, Right;
1446         reorderAltShuffleOperands(VL, Left, Right);
1447         buildTree_rec(Left, Depth + 1);
1448         buildTree_rec(Right, Depth + 1);
1449         return;
1450       }
1451
1452       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
1453         ValueList Operands;
1454         // Prepare the operand vector.
1455         for (unsigned j = 0; j < VL.size(); ++j)
1456           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
1457
1458         buildTree_rec(Operands, Depth + 1);
1459       }
1460       return;
1461     }
1462     default:
1463       BS.cancelScheduling(VL);
1464       newTreeEntry(VL, false);
1465       DEBUG(dbgs() << "SLP: Gathering unknown instruction.\n");
1466       return;
1467   }
1468 }
1469
1470 int BoUpSLP::getEntryCost(TreeEntry *E) {
1471   ArrayRef<Value*> VL = E->Scalars;
1472
1473   Type *ScalarTy = VL[0]->getType();
1474   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
1475     ScalarTy = SI->getValueOperand()->getType();
1476   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
1477
1478   if (E->NeedToGather) {
1479     if (allConstant(VL))
1480       return 0;
1481     if (isSplat(VL)) {
1482       return TTI->getShuffleCost(TargetTransformInfo::SK_Broadcast, VecTy, 0);
1483     }
1484     return getGatherCost(E->Scalars);
1485   }
1486   unsigned Opcode = getSameOpcode(VL);
1487   assert(Opcode && getSameType(VL) && getSameBlock(VL) && "Invalid VL");
1488   Instruction *VL0 = cast<Instruction>(VL[0]);
1489   switch (Opcode) {
1490     case Instruction::PHI: {
1491       return 0;
1492     }
1493     case Instruction::ExtractElement: {
1494       if (CanReuseExtract(VL)) {
1495         int DeadCost = 0;
1496         for (unsigned i = 0, e = VL.size(); i < e; ++i) {
1497           ExtractElementInst *E = cast<ExtractElementInst>(VL[i]);
1498           if (E->hasOneUse())
1499             // Take credit for instruction that will become dead.
1500             DeadCost +=
1501                 TTI->getVectorInstrCost(Instruction::ExtractElement, VecTy, i);
1502         }
1503         return -DeadCost;
1504       }
1505       return getGatherCost(VecTy);
1506     }
1507     case Instruction::ZExt:
1508     case Instruction::SExt:
1509     case Instruction::FPToUI:
1510     case Instruction::FPToSI:
1511     case Instruction::FPExt:
1512     case Instruction::PtrToInt:
1513     case Instruction::IntToPtr:
1514     case Instruction::SIToFP:
1515     case Instruction::UIToFP:
1516     case Instruction::Trunc:
1517     case Instruction::FPTrunc:
1518     case Instruction::BitCast: {
1519       Type *SrcTy = VL0->getOperand(0)->getType();
1520
1521       // Calculate the cost of this instruction.
1522       int ScalarCost = VL.size() * TTI->getCastInstrCost(VL0->getOpcode(),
1523                                                          VL0->getType(), SrcTy);
1524
1525       VectorType *SrcVecTy = VectorType::get(SrcTy, VL.size());
1526       int VecCost = TTI->getCastInstrCost(VL0->getOpcode(), VecTy, SrcVecTy);
1527       return VecCost - ScalarCost;
1528     }
1529     case Instruction::FCmp:
1530     case Instruction::ICmp:
1531     case Instruction::Select:
1532     case Instruction::Add:
1533     case Instruction::FAdd:
1534     case Instruction::Sub:
1535     case Instruction::FSub:
1536     case Instruction::Mul:
1537     case Instruction::FMul:
1538     case Instruction::UDiv:
1539     case Instruction::SDiv:
1540     case Instruction::FDiv:
1541     case Instruction::URem:
1542     case Instruction::SRem:
1543     case Instruction::FRem:
1544     case Instruction::Shl:
1545     case Instruction::LShr:
1546     case Instruction::AShr:
1547     case Instruction::And:
1548     case Instruction::Or:
1549     case Instruction::Xor: {
1550       // Calculate the cost of this instruction.
1551       int ScalarCost = 0;
1552       int VecCost = 0;
1553       if (Opcode == Instruction::FCmp || Opcode == Instruction::ICmp ||
1554           Opcode == Instruction::Select) {
1555         VectorType *MaskTy = VectorType::get(Builder.getInt1Ty(), VL.size());
1556         ScalarCost = VecTy->getNumElements() *
1557         TTI->getCmpSelInstrCost(Opcode, ScalarTy, Builder.getInt1Ty());
1558         VecCost = TTI->getCmpSelInstrCost(Opcode, VecTy, MaskTy);
1559       } else {
1560         // Certain instructions can be cheaper to vectorize if they have a
1561         // constant second vector operand.
1562         TargetTransformInfo::OperandValueKind Op1VK =
1563             TargetTransformInfo::OK_AnyValue;
1564         TargetTransformInfo::OperandValueKind Op2VK =
1565             TargetTransformInfo::OK_UniformConstantValue;
1566         TargetTransformInfo::OperandValueProperties Op1VP =
1567             TargetTransformInfo::OP_None;
1568         TargetTransformInfo::OperandValueProperties Op2VP =
1569             TargetTransformInfo::OP_None;
1570
1571         // If all operands are exactly the same ConstantInt then set the
1572         // operand kind to OK_UniformConstantValue.
1573         // If instead not all operands are constants, then set the operand kind
1574         // to OK_AnyValue. If all operands are constants but not the same,
1575         // then set the operand kind to OK_NonUniformConstantValue.
1576         ConstantInt *CInt = nullptr;
1577         for (unsigned i = 0; i < VL.size(); ++i) {
1578           const Instruction *I = cast<Instruction>(VL[i]);
1579           if (!isa<ConstantInt>(I->getOperand(1))) {
1580             Op2VK = TargetTransformInfo::OK_AnyValue;
1581             break;
1582           }
1583           if (i == 0) {
1584             CInt = cast<ConstantInt>(I->getOperand(1));
1585             continue;
1586           }
1587           if (Op2VK == TargetTransformInfo::OK_UniformConstantValue &&
1588               CInt != cast<ConstantInt>(I->getOperand(1)))
1589             Op2VK = TargetTransformInfo::OK_NonUniformConstantValue;
1590         }
1591         // FIXME: Currently cost of model modification for division by
1592         // power of 2 is handled only for X86. Add support for other targets.
1593         if (Op2VK == TargetTransformInfo::OK_UniformConstantValue && CInt &&
1594             CInt->getValue().isPowerOf2())
1595           Op2VP = TargetTransformInfo::OP_PowerOf2;
1596
1597         ScalarCost = VecTy->getNumElements() *
1598                      TTI->getArithmeticInstrCost(Opcode, ScalarTy, Op1VK, Op2VK,
1599                                                  Op1VP, Op2VP);
1600         VecCost = TTI->getArithmeticInstrCost(Opcode, VecTy, Op1VK, Op2VK,
1601                                               Op1VP, Op2VP);
1602       }
1603       return VecCost - ScalarCost;
1604     }
1605     case Instruction::GetElementPtr: {
1606       TargetTransformInfo::OperandValueKind Op1VK =
1607           TargetTransformInfo::OK_AnyValue;
1608       TargetTransformInfo::OperandValueKind Op2VK =
1609           TargetTransformInfo::OK_UniformConstantValue;
1610
1611       int ScalarCost =
1612           VecTy->getNumElements() *
1613           TTI->getArithmeticInstrCost(Instruction::Add, ScalarTy, Op1VK, Op2VK);
1614       int VecCost =
1615           TTI->getArithmeticInstrCost(Instruction::Add, VecTy, Op1VK, Op2VK);
1616
1617       return VecCost - ScalarCost;
1618     }
1619     case Instruction::Load: {
1620       // Cost of wide load - cost of scalar loads.
1621       int ScalarLdCost = VecTy->getNumElements() *
1622       TTI->getMemoryOpCost(Instruction::Load, ScalarTy, 1, 0);
1623       int VecLdCost = TTI->getMemoryOpCost(Instruction::Load, VecTy, 1, 0);
1624       return VecLdCost - ScalarLdCost;
1625     }
1626     case Instruction::Store: {
1627       // We know that we can merge the stores. Calculate the cost.
1628       int ScalarStCost = VecTy->getNumElements() *
1629       TTI->getMemoryOpCost(Instruction::Store, ScalarTy, 1, 0);
1630       int VecStCost = TTI->getMemoryOpCost(Instruction::Store, VecTy, 1, 0);
1631       return VecStCost - ScalarStCost;
1632     }
1633     case Instruction::Call: {
1634       CallInst *CI = cast<CallInst>(VL0);
1635       Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
1636
1637       // Calculate the cost of the scalar and vector calls.
1638       SmallVector<Type*, 4> ScalarTys, VecTys;
1639       for (unsigned op = 0, opc = CI->getNumArgOperands(); op!= opc; ++op) {
1640         ScalarTys.push_back(CI->getArgOperand(op)->getType());
1641         VecTys.push_back(VectorType::get(CI->getArgOperand(op)->getType(),
1642                                          VecTy->getNumElements()));
1643       }
1644
1645       int ScalarCallCost = VecTy->getNumElements() *
1646           TTI->getIntrinsicInstrCost(ID, ScalarTy, ScalarTys);
1647
1648       int VecCallCost = TTI->getIntrinsicInstrCost(ID, VecTy, VecTys);
1649
1650       DEBUG(dbgs() << "SLP: Call cost "<< VecCallCost - ScalarCallCost
1651             << " (" << VecCallCost  << "-" <<  ScalarCallCost << ")"
1652             << " for " << *CI << "\n");
1653
1654       return VecCallCost - ScalarCallCost;
1655     }
1656     case Instruction::ShuffleVector: {
1657       TargetTransformInfo::OperandValueKind Op1VK =
1658           TargetTransformInfo::OK_AnyValue;
1659       TargetTransformInfo::OperandValueKind Op2VK =
1660           TargetTransformInfo::OK_AnyValue;
1661       int ScalarCost = 0;
1662       int VecCost = 0;
1663       for (unsigned i = 0; i < VL.size(); ++i) {
1664         Instruction *I = cast<Instruction>(VL[i]);
1665         if (!I)
1666           break;
1667         ScalarCost +=
1668             TTI->getArithmeticInstrCost(I->getOpcode(), ScalarTy, Op1VK, Op2VK);
1669       }
1670       // VecCost is equal to sum of the cost of creating 2 vectors
1671       // and the cost of creating shuffle.
1672       Instruction *I0 = cast<Instruction>(VL[0]);
1673       VecCost =
1674           TTI->getArithmeticInstrCost(I0->getOpcode(), VecTy, Op1VK, Op2VK);
1675       Instruction *I1 = cast<Instruction>(VL[1]);
1676       VecCost +=
1677           TTI->getArithmeticInstrCost(I1->getOpcode(), VecTy, Op1VK, Op2VK);
1678       VecCost +=
1679           TTI->getShuffleCost(TargetTransformInfo::SK_Alternate, VecTy, 0);
1680       return VecCost - ScalarCost;
1681     }
1682     default:
1683       llvm_unreachable("Unknown instruction");
1684   }
1685 }
1686
1687 bool BoUpSLP::isFullyVectorizableTinyTree() {
1688   DEBUG(dbgs() << "SLP: Check whether the tree with height " <<
1689         VectorizableTree.size() << " is fully vectorizable .\n");
1690
1691   // We only handle trees of height 2.
1692   if (VectorizableTree.size() != 2)
1693     return false;
1694
1695   // Handle splat and all-constants stores.
1696   if (!VectorizableTree[0].NeedToGather &&
1697       (allConstant(VectorizableTree[1].Scalars) ||
1698        isSplat(VectorizableTree[1].Scalars)))
1699     return true;
1700
1701   // Gathering cost would be too much for tiny trees.
1702   if (VectorizableTree[0].NeedToGather || VectorizableTree[1].NeedToGather)
1703     return false;
1704
1705   return true;
1706 }
1707
1708 int BoUpSLP::getSpillCost() {
1709   // Walk from the bottom of the tree to the top, tracking which values are
1710   // live. When we see a call instruction that is not part of our tree,
1711   // query TTI to see if there is a cost to keeping values live over it
1712   // (for example, if spills and fills are required).
1713   unsigned BundleWidth = VectorizableTree.front().Scalars.size();
1714   int Cost = 0;
1715
1716   SmallPtrSet<Instruction*, 4> LiveValues;
1717   Instruction *PrevInst = nullptr; 
1718
1719   for (unsigned N = 0; N < VectorizableTree.size(); ++N) {
1720     Instruction *Inst = dyn_cast<Instruction>(VectorizableTree[N].Scalars[0]);
1721     if (!Inst)
1722       continue;
1723
1724     if (!PrevInst) {
1725       PrevInst = Inst;
1726       continue;
1727     }
1728
1729     DEBUG(
1730       dbgs() << "SLP: #LV: " << LiveValues.size();
1731       for (auto *X : LiveValues)
1732         dbgs() << " " << X->getName();
1733       dbgs() << ", Looking at ";
1734       Inst->dump();
1735       );
1736
1737     // Update LiveValues.
1738     LiveValues.erase(PrevInst);
1739     for (auto &J : PrevInst->operands()) {
1740       if (isa<Instruction>(&*J) && ScalarToTreeEntry.count(&*J))
1741         LiveValues.insert(cast<Instruction>(&*J));
1742     }    
1743
1744     // Now find the sequence of instructions between PrevInst and Inst.
1745     BasicBlock::reverse_iterator InstIt(Inst->getIterator()),
1746         PrevInstIt(PrevInst->getIterator());
1747     --PrevInstIt;
1748     while (InstIt != PrevInstIt) {
1749       if (PrevInstIt == PrevInst->getParent()->rend()) {
1750         PrevInstIt = Inst->getParent()->rbegin();
1751         continue;
1752       }
1753
1754       if (isa<CallInst>(&*PrevInstIt) && &*PrevInstIt != PrevInst) {
1755         SmallVector<Type*, 4> V;
1756         for (auto *II : LiveValues)
1757           V.push_back(VectorType::get(II->getType(), BundleWidth));
1758         Cost += TTI->getCostOfKeepingLiveOverCall(V);
1759       }
1760
1761       ++PrevInstIt;
1762     }
1763
1764     PrevInst = Inst;
1765   }
1766
1767   DEBUG(dbgs() << "SLP: SpillCost=" << Cost << "\n");
1768   return Cost;
1769 }
1770
1771 int BoUpSLP::getTreeCost() {
1772   int Cost = 0;
1773   DEBUG(dbgs() << "SLP: Calculating cost for tree of size " <<
1774         VectorizableTree.size() << ".\n");
1775
1776   // We only vectorize tiny trees if it is fully vectorizable.
1777   if (VectorizableTree.size() < 3 && !isFullyVectorizableTinyTree()) {
1778     if (VectorizableTree.empty()) {
1779       assert(!ExternalUses.size() && "We should not have any external users");
1780     }
1781     return INT_MAX;
1782   }
1783
1784   unsigned BundleWidth = VectorizableTree[0].Scalars.size();
1785
1786   for (unsigned i = 0, e = VectorizableTree.size(); i != e; ++i) {
1787     int C = getEntryCost(&VectorizableTree[i]);
1788     DEBUG(dbgs() << "SLP: Adding cost " << C << " for bundle that starts with "
1789           << *VectorizableTree[i].Scalars[0] << " .\n");
1790     Cost += C;
1791   }
1792
1793   SmallSet<Value *, 16> ExtractCostCalculated;
1794   int ExtractCost = 0;
1795   for (UserList::iterator I = ExternalUses.begin(), E = ExternalUses.end();
1796        I != E; ++I) {
1797     // We only add extract cost once for the same scalar.
1798     if (!ExtractCostCalculated.insert(I->Scalar).second)
1799       continue;
1800
1801     // Uses by ephemeral values are free (because the ephemeral value will be
1802     // removed prior to code generation, and so the extraction will be
1803     // removed as well).
1804     if (EphValues.count(I->User))
1805       continue;
1806
1807     VectorType *VecTy = VectorType::get(I->Scalar->getType(), BundleWidth);
1808     ExtractCost += TTI->getVectorInstrCost(Instruction::ExtractElement, VecTy,
1809                                            I->Lane);
1810   }
1811
1812   Cost += getSpillCost();
1813
1814   DEBUG(dbgs() << "SLP: Total Cost " << Cost + ExtractCost<< ".\n");
1815   return  Cost + ExtractCost;
1816 }
1817
1818 int BoUpSLP::getGatherCost(Type *Ty) {
1819   int Cost = 0;
1820   for (unsigned i = 0, e = cast<VectorType>(Ty)->getNumElements(); i < e; ++i)
1821     Cost += TTI->getVectorInstrCost(Instruction::InsertElement, Ty, i);
1822   return Cost;
1823 }
1824
1825 int BoUpSLP::getGatherCost(ArrayRef<Value *> VL) {
1826   // Find the type of the operands in VL.
1827   Type *ScalarTy = VL[0]->getType();
1828   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
1829     ScalarTy = SI->getValueOperand()->getType();
1830   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
1831   // Find the cost of inserting/extracting values from the vector.
1832   return getGatherCost(VecTy);
1833 }
1834
1835 Value *BoUpSLP::getPointerOperand(Value *I) {
1836   if (LoadInst *LI = dyn_cast<LoadInst>(I))
1837     return LI->getPointerOperand();
1838   if (StoreInst *SI = dyn_cast<StoreInst>(I))
1839     return SI->getPointerOperand();
1840   return nullptr;
1841 }
1842
1843 unsigned BoUpSLP::getAddressSpaceOperand(Value *I) {
1844   if (LoadInst *L = dyn_cast<LoadInst>(I))
1845     return L->getPointerAddressSpace();
1846   if (StoreInst *S = dyn_cast<StoreInst>(I))
1847     return S->getPointerAddressSpace();
1848   return -1;
1849 }
1850
1851 bool BoUpSLP::isConsecutiveAccess(Value *A, Value *B, const DataLayout &DL) {
1852   Value *PtrA = getPointerOperand(A);
1853   Value *PtrB = getPointerOperand(B);
1854   unsigned ASA = getAddressSpaceOperand(A);
1855   unsigned ASB = getAddressSpaceOperand(B);
1856
1857   // Check that the address spaces match and that the pointers are valid.
1858   if (!PtrA || !PtrB || (ASA != ASB))
1859     return false;
1860
1861   // Make sure that A and B are different pointers of the same type.
1862   if (PtrA == PtrB || PtrA->getType() != PtrB->getType())
1863     return false;
1864
1865   unsigned PtrBitWidth = DL.getPointerSizeInBits(ASA);
1866   Type *Ty = cast<PointerType>(PtrA->getType())->getElementType();
1867   APInt Size(PtrBitWidth, DL.getTypeStoreSize(Ty));
1868
1869   APInt OffsetA(PtrBitWidth, 0), OffsetB(PtrBitWidth, 0);
1870   PtrA = PtrA->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetA);
1871   PtrB = PtrB->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetB);
1872
1873   APInt OffsetDelta = OffsetB - OffsetA;
1874
1875   // Check if they are based on the same pointer. That makes the offsets
1876   // sufficient.
1877   if (PtrA == PtrB)
1878     return OffsetDelta == Size;
1879
1880   // Compute the necessary base pointer delta to have the necessary final delta
1881   // equal to the size.
1882   APInt BaseDelta = Size - OffsetDelta;
1883
1884   // Otherwise compute the distance with SCEV between the base pointers.
1885   const SCEV *PtrSCEVA = SE->getSCEV(PtrA);
1886   const SCEV *PtrSCEVB = SE->getSCEV(PtrB);
1887   const SCEV *C = SE->getConstant(BaseDelta);
1888   const SCEV *X = SE->getAddExpr(PtrSCEVA, C);
1889   return X == PtrSCEVB;
1890 }
1891
1892 // Reorder commutative operations in alternate shuffle if the resulting vectors
1893 // are consecutive loads. This would allow us to vectorize the tree.
1894 // If we have something like-
1895 // load a[0] - load b[0]
1896 // load b[1] + load a[1]
1897 // load a[2] - load b[2]
1898 // load a[3] + load b[3]
1899 // Reordering the second load b[1]  load a[1] would allow us to vectorize this
1900 // code.
1901 void BoUpSLP::reorderAltShuffleOperands(ArrayRef<Value *> VL,
1902                                         SmallVectorImpl<Value *> &Left,
1903                                         SmallVectorImpl<Value *> &Right) {
1904   const DataLayout &DL = F->getParent()->getDataLayout();
1905
1906   // Push left and right operands of binary operation into Left and Right
1907   for (unsigned i = 0, e = VL.size(); i < e; ++i) {
1908     Left.push_back(cast<Instruction>(VL[i])->getOperand(0));
1909     Right.push_back(cast<Instruction>(VL[i])->getOperand(1));
1910   }
1911
1912   // Reorder if we have a commutative operation and consecutive access
1913   // are on either side of the alternate instructions.
1914   for (unsigned j = 0; j < VL.size() - 1; ++j) {
1915     if (LoadInst *L = dyn_cast<LoadInst>(Left[j])) {
1916       if (LoadInst *L1 = dyn_cast<LoadInst>(Right[j + 1])) {
1917         Instruction *VL1 = cast<Instruction>(VL[j]);
1918         Instruction *VL2 = cast<Instruction>(VL[j + 1]);
1919         if (isConsecutiveAccess(L, L1, DL) && VL1->isCommutative()) {
1920           std::swap(Left[j], Right[j]);
1921           continue;
1922         } else if (isConsecutiveAccess(L, L1, DL) && VL2->isCommutative()) {
1923           std::swap(Left[j + 1], Right[j + 1]);
1924           continue;
1925         }
1926         // else unchanged
1927       }
1928     }
1929     if (LoadInst *L = dyn_cast<LoadInst>(Right[j])) {
1930       if (LoadInst *L1 = dyn_cast<LoadInst>(Left[j + 1])) {
1931         Instruction *VL1 = cast<Instruction>(VL[j]);
1932         Instruction *VL2 = cast<Instruction>(VL[j + 1]);
1933         if (isConsecutiveAccess(L, L1, DL) && VL1->isCommutative()) {
1934           std::swap(Left[j], Right[j]);
1935           continue;
1936         } else if (isConsecutiveAccess(L, L1, DL) && VL2->isCommutative()) {
1937           std::swap(Left[j + 1], Right[j + 1]);
1938           continue;
1939         }
1940         // else unchanged
1941       }
1942     }
1943   }
1944 }
1945
1946 void BoUpSLP::reorderInputsAccordingToOpcode(ArrayRef<Value *> VL,
1947                                              SmallVectorImpl<Value *> &Left,
1948                                              SmallVectorImpl<Value *> &Right) {
1949
1950   SmallVector<Value *, 16> OrigLeft, OrigRight;
1951
1952   bool AllSameOpcodeLeft = true;
1953   bool AllSameOpcodeRight = true;
1954   for (unsigned i = 0, e = VL.size(); i != e; ++i) {
1955     Instruction *I = cast<Instruction>(VL[i]);
1956     Value *VLeft = I->getOperand(0);
1957     Value *VRight = I->getOperand(1);
1958
1959     OrigLeft.push_back(VLeft);
1960     OrigRight.push_back(VRight);
1961
1962     Instruction *ILeft = dyn_cast<Instruction>(VLeft);
1963     Instruction *IRight = dyn_cast<Instruction>(VRight);
1964
1965     // Check whether all operands on one side have the same opcode. In this case
1966     // we want to preserve the original order and not make things worse by
1967     // reordering.
1968     if (i && AllSameOpcodeLeft && ILeft) {
1969       if (Instruction *PLeft = dyn_cast<Instruction>(OrigLeft[i - 1])) {
1970         if (PLeft->getOpcode() != ILeft->getOpcode())
1971           AllSameOpcodeLeft = false;
1972       } else
1973         AllSameOpcodeLeft = false;
1974     }
1975     if (i && AllSameOpcodeRight && IRight) {
1976       if (Instruction *PRight = dyn_cast<Instruction>(OrigRight[i - 1])) {
1977         if (PRight->getOpcode() != IRight->getOpcode())
1978           AllSameOpcodeRight = false;
1979       } else
1980         AllSameOpcodeRight = false;
1981     }
1982
1983     // Sort two opcodes. In the code below we try to preserve the ability to use
1984     // broadcast of values instead of individual inserts.
1985     // vl1 = load
1986     // vl2 = phi
1987     // vr1 = load
1988     // vr2 = vr2
1989     //    = vl1 x vr1
1990     //    = vl2 x vr2
1991     // If we just sorted according to opcode we would leave the first line in
1992     // tact but we would swap vl2 with vr2 because opcode(phi) > opcode(load).
1993     //    = vl1 x vr1
1994     //    = vr2 x vl2
1995     // Because vr2 and vr1 are from the same load we loose the opportunity of a
1996     // broadcast for the packed right side in the backend: we have [vr1, vl2]
1997     // instead of [vr1, vr2=vr1].
1998     if (ILeft && IRight) {
1999       if (!i && ILeft->getOpcode() > IRight->getOpcode()) {
2000         Left.push_back(IRight);
2001         Right.push_back(ILeft);
2002       } else if (i && ILeft->getOpcode() > IRight->getOpcode() &&
2003                  Right[i - 1] != IRight) {
2004         // Try not to destroy a broad cast for no apparent benefit.
2005         Left.push_back(IRight);
2006         Right.push_back(ILeft);
2007       } else if (i && ILeft->getOpcode() == IRight->getOpcode() &&
2008                  Right[i - 1] == ILeft) {
2009         // Try preserve broadcasts.
2010         Left.push_back(IRight);
2011         Right.push_back(ILeft);
2012       } else if (i && ILeft->getOpcode() == IRight->getOpcode() &&
2013                  Left[i - 1] == IRight) {
2014         // Try preserve broadcasts.
2015         Left.push_back(IRight);
2016         Right.push_back(ILeft);
2017       } else {
2018         Left.push_back(ILeft);
2019         Right.push_back(IRight);
2020       }
2021       continue;
2022     }
2023     // One opcode, put the instruction on the right.
2024     if (ILeft) {
2025       Left.push_back(VRight);
2026       Right.push_back(ILeft);
2027       continue;
2028     }
2029     Left.push_back(VLeft);
2030     Right.push_back(VRight);
2031   }
2032
2033   bool LeftBroadcast = isSplat(Left);
2034   bool RightBroadcast = isSplat(Right);
2035
2036   // If operands end up being broadcast return this operand order.
2037   if (LeftBroadcast || RightBroadcast)
2038     return;
2039
2040   // Don't reorder if the operands where good to begin.
2041   if (AllSameOpcodeRight || AllSameOpcodeLeft) {
2042     Left = OrigLeft;
2043     Right = OrigRight;
2044   }
2045
2046   const DataLayout &DL = F->getParent()->getDataLayout();
2047
2048   // Finally check if we can get longer vectorizable chain by reordering
2049   // without breaking the good operand order detected above.
2050   // E.g. If we have something like-
2051   // load a[0]  load b[0]
2052   // load b[1]  load a[1]
2053   // load a[2]  load b[2]
2054   // load a[3]  load b[3]
2055   // Reordering the second load b[1]  load a[1] would allow us to vectorize
2056   // this code and we still retain AllSameOpcode property.
2057   // FIXME: This load reordering might break AllSameOpcode in some rare cases
2058   // such as-
2059   // add a[0],c[0]  load b[0]
2060   // add a[1],c[2]  load b[1]
2061   // b[2]           load b[2]
2062   // add a[3],c[3]  load b[3]
2063   for (unsigned j = 0; j < VL.size() - 1; ++j) {
2064     if (LoadInst *L = dyn_cast<LoadInst>(Left[j])) {
2065       if (LoadInst *L1 = dyn_cast<LoadInst>(Right[j + 1])) {
2066         if (isConsecutiveAccess(L, L1, DL)) {
2067           std::swap(Left[j + 1], Right[j + 1]);
2068           continue;
2069         }
2070       }
2071     }
2072     if (LoadInst *L = dyn_cast<LoadInst>(Right[j])) {
2073       if (LoadInst *L1 = dyn_cast<LoadInst>(Left[j + 1])) {
2074         if (isConsecutiveAccess(L, L1, DL)) {
2075           std::swap(Left[j + 1], Right[j + 1]);
2076           continue;
2077         }
2078       }
2079     }
2080     // else unchanged
2081   }
2082 }
2083
2084 void BoUpSLP::setInsertPointAfterBundle(ArrayRef<Value *> VL) {
2085   Instruction *VL0 = cast<Instruction>(VL[0]);
2086   BasicBlock::iterator NextInst(VL0);
2087   ++NextInst;
2088   Builder.SetInsertPoint(VL0->getParent(), NextInst);
2089   Builder.SetCurrentDebugLocation(VL0->getDebugLoc());
2090 }
2091
2092 Value *BoUpSLP::Gather(ArrayRef<Value *> VL, VectorType *Ty) {
2093   Value *Vec = UndefValue::get(Ty);
2094   // Generate the 'InsertElement' instruction.
2095   for (unsigned i = 0; i < Ty->getNumElements(); ++i) {
2096     Vec = Builder.CreateInsertElement(Vec, VL[i], Builder.getInt32(i));
2097     if (Instruction *Insrt = dyn_cast<Instruction>(Vec)) {
2098       GatherSeq.insert(Insrt);
2099       CSEBlocks.insert(Insrt->getParent());
2100
2101       // Add to our 'need-to-extract' list.
2102       if (ScalarToTreeEntry.count(VL[i])) {
2103         int Idx = ScalarToTreeEntry[VL[i]];
2104         TreeEntry *E = &VectorizableTree[Idx];
2105         // Find which lane we need to extract.
2106         int FoundLane = -1;
2107         for (unsigned Lane = 0, LE = VL.size(); Lane != LE; ++Lane) {
2108           // Is this the lane of the scalar that we are looking for ?
2109           if (E->Scalars[Lane] == VL[i]) {
2110             FoundLane = Lane;
2111             break;
2112           }
2113         }
2114         assert(FoundLane >= 0 && "Could not find the correct lane");
2115         ExternalUses.push_back(ExternalUser(VL[i], Insrt, FoundLane));
2116       }
2117     }
2118   }
2119
2120   return Vec;
2121 }
2122
2123 Value *BoUpSLP::alreadyVectorized(ArrayRef<Value *> VL) const {
2124   SmallDenseMap<Value*, int>::const_iterator Entry
2125     = ScalarToTreeEntry.find(VL[0]);
2126   if (Entry != ScalarToTreeEntry.end()) {
2127     int Idx = Entry->second;
2128     const TreeEntry *En = &VectorizableTree[Idx];
2129     if (En->isSame(VL) && En->VectorizedValue)
2130       return En->VectorizedValue;
2131   }
2132   return nullptr;
2133 }
2134
2135 Value *BoUpSLP::vectorizeTree(ArrayRef<Value *> VL) {
2136   if (ScalarToTreeEntry.count(VL[0])) {
2137     int Idx = ScalarToTreeEntry[VL[0]];
2138     TreeEntry *E = &VectorizableTree[Idx];
2139     if (E->isSame(VL))
2140       return vectorizeTree(E);
2141   }
2142
2143   Type *ScalarTy = VL[0]->getType();
2144   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
2145     ScalarTy = SI->getValueOperand()->getType();
2146   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
2147
2148   return Gather(VL, VecTy);
2149 }
2150
2151 Value *BoUpSLP::vectorizeTree(TreeEntry *E) {
2152   IRBuilder<>::InsertPointGuard Guard(Builder);
2153
2154   if (E->VectorizedValue) {
2155     DEBUG(dbgs() << "SLP: Diamond merged for " << *E->Scalars[0] << ".\n");
2156     return E->VectorizedValue;
2157   }
2158
2159   Instruction *VL0 = cast<Instruction>(E->Scalars[0]);
2160   Type *ScalarTy = VL0->getType();
2161   if (StoreInst *SI = dyn_cast<StoreInst>(VL0))
2162     ScalarTy = SI->getValueOperand()->getType();
2163   VectorType *VecTy = VectorType::get(ScalarTy, E->Scalars.size());
2164
2165   if (E->NeedToGather) {
2166     setInsertPointAfterBundle(E->Scalars);
2167     return Gather(E->Scalars, VecTy);
2168   }
2169
2170   const DataLayout &DL = F->getParent()->getDataLayout();
2171   unsigned Opcode = getSameOpcode(E->Scalars);
2172
2173   switch (Opcode) {
2174     case Instruction::PHI: {
2175       PHINode *PH = dyn_cast<PHINode>(VL0);
2176       Builder.SetInsertPoint(PH->getParent()->getFirstNonPHI());
2177       Builder.SetCurrentDebugLocation(PH->getDebugLoc());
2178       PHINode *NewPhi = Builder.CreatePHI(VecTy, PH->getNumIncomingValues());
2179       E->VectorizedValue = NewPhi;
2180
2181       // PHINodes may have multiple entries from the same block. We want to
2182       // visit every block once.
2183       SmallSet<BasicBlock*, 4> VisitedBBs;
2184
2185       for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
2186         ValueList Operands;
2187         BasicBlock *IBB = PH->getIncomingBlock(i);
2188
2189         if (!VisitedBBs.insert(IBB).second) {
2190           NewPhi->addIncoming(NewPhi->getIncomingValueForBlock(IBB), IBB);
2191           continue;
2192         }
2193
2194         // Prepare the operand vector.
2195         for (Value *V : E->Scalars)
2196           Operands.push_back(cast<PHINode>(V)->getIncomingValueForBlock(IBB));
2197
2198         Builder.SetInsertPoint(IBB->getTerminator());
2199         Builder.SetCurrentDebugLocation(PH->getDebugLoc());
2200         Value *Vec = vectorizeTree(Operands);
2201         NewPhi->addIncoming(Vec, IBB);
2202       }
2203
2204       assert(NewPhi->getNumIncomingValues() == PH->getNumIncomingValues() &&
2205              "Invalid number of incoming values");
2206       return NewPhi;
2207     }
2208
2209     case Instruction::ExtractElement: {
2210       if (CanReuseExtract(E->Scalars)) {
2211         Value *V = VL0->getOperand(0);
2212         E->VectorizedValue = V;
2213         return V;
2214       }
2215       return Gather(E->Scalars, VecTy);
2216     }
2217     case Instruction::ZExt:
2218     case Instruction::SExt:
2219     case Instruction::FPToUI:
2220     case Instruction::FPToSI:
2221     case Instruction::FPExt:
2222     case Instruction::PtrToInt:
2223     case Instruction::IntToPtr:
2224     case Instruction::SIToFP:
2225     case Instruction::UIToFP:
2226     case Instruction::Trunc:
2227     case Instruction::FPTrunc:
2228     case Instruction::BitCast: {
2229       ValueList INVL;
2230       for (Value *V : E->Scalars)
2231         INVL.push_back(cast<Instruction>(V)->getOperand(0));
2232
2233       setInsertPointAfterBundle(E->Scalars);
2234
2235       Value *InVec = vectorizeTree(INVL);
2236
2237       if (Value *V = alreadyVectorized(E->Scalars))
2238         return V;
2239
2240       CastInst *CI = dyn_cast<CastInst>(VL0);
2241       Value *V = Builder.CreateCast(CI->getOpcode(), InVec, VecTy);
2242       E->VectorizedValue = V;
2243       ++NumVectorInstructions;
2244       return V;
2245     }
2246     case Instruction::FCmp:
2247     case Instruction::ICmp: {
2248       ValueList LHSV, RHSV;
2249       for (Value *V : E->Scalars) {
2250         LHSV.push_back(cast<Instruction>(V)->getOperand(0));
2251         RHSV.push_back(cast<Instruction>(V)->getOperand(1));
2252       }
2253
2254       setInsertPointAfterBundle(E->Scalars);
2255
2256       Value *L = vectorizeTree(LHSV);
2257       Value *R = vectorizeTree(RHSV);
2258
2259       if (Value *V = alreadyVectorized(E->Scalars))
2260         return V;
2261
2262       CmpInst::Predicate P0 = cast<CmpInst>(VL0)->getPredicate();
2263       Value *V;
2264       if (Opcode == Instruction::FCmp)
2265         V = Builder.CreateFCmp(P0, L, R);
2266       else
2267         V = Builder.CreateICmp(P0, L, R);
2268
2269       E->VectorizedValue = V;
2270       ++NumVectorInstructions;
2271       return V;
2272     }
2273     case Instruction::Select: {
2274       ValueList TrueVec, FalseVec, CondVec;
2275       for (Value *V : E->Scalars) {
2276         CondVec.push_back(cast<Instruction>(V)->getOperand(0));
2277         TrueVec.push_back(cast<Instruction>(V)->getOperand(1));
2278         FalseVec.push_back(cast<Instruction>(V)->getOperand(2));
2279       }
2280
2281       setInsertPointAfterBundle(E->Scalars);
2282
2283       Value *Cond = vectorizeTree(CondVec);
2284       Value *True = vectorizeTree(TrueVec);
2285       Value *False = vectorizeTree(FalseVec);
2286
2287       if (Value *V = alreadyVectorized(E->Scalars))
2288         return V;
2289
2290       Value *V = Builder.CreateSelect(Cond, True, False);
2291       E->VectorizedValue = V;
2292       ++NumVectorInstructions;
2293       return V;
2294     }
2295     case Instruction::Add:
2296     case Instruction::FAdd:
2297     case Instruction::Sub:
2298     case Instruction::FSub:
2299     case Instruction::Mul:
2300     case Instruction::FMul:
2301     case Instruction::UDiv:
2302     case Instruction::SDiv:
2303     case Instruction::FDiv:
2304     case Instruction::URem:
2305     case Instruction::SRem:
2306     case Instruction::FRem:
2307     case Instruction::Shl:
2308     case Instruction::LShr:
2309     case Instruction::AShr:
2310     case Instruction::And:
2311     case Instruction::Or:
2312     case Instruction::Xor: {
2313       ValueList LHSVL, RHSVL;
2314       if (isa<BinaryOperator>(VL0) && VL0->isCommutative())
2315         reorderInputsAccordingToOpcode(E->Scalars, LHSVL, RHSVL);
2316       else
2317         for (Value *V : E->Scalars) {
2318           LHSVL.push_back(cast<Instruction>(V)->getOperand(0));
2319           RHSVL.push_back(cast<Instruction>(V)->getOperand(1));
2320         }
2321
2322       setInsertPointAfterBundle(E->Scalars);
2323
2324       Value *LHS = vectorizeTree(LHSVL);
2325       Value *RHS = vectorizeTree(RHSVL);
2326
2327       if (LHS == RHS && isa<Instruction>(LHS)) {
2328         assert((VL0->getOperand(0) == VL0->getOperand(1)) && "Invalid order");
2329       }
2330
2331       if (Value *V = alreadyVectorized(E->Scalars))
2332         return V;
2333
2334       BinaryOperator *BinOp = cast<BinaryOperator>(VL0);
2335       Value *V = Builder.CreateBinOp(BinOp->getOpcode(), LHS, RHS);
2336       E->VectorizedValue = V;
2337       propagateIRFlags(E->VectorizedValue, E->Scalars);
2338       ++NumVectorInstructions;
2339
2340       if (Instruction *I = dyn_cast<Instruction>(V))
2341         return propagateMetadata(I, E->Scalars);
2342
2343       return V;
2344     }
2345     case Instruction::Load: {
2346       // Loads are inserted at the head of the tree because we don't want to
2347       // sink them all the way down past store instructions.
2348       setInsertPointAfterBundle(E->Scalars);
2349
2350       LoadInst *LI = cast<LoadInst>(VL0);
2351       Type *ScalarLoadTy = LI->getType();
2352       unsigned AS = LI->getPointerAddressSpace();
2353
2354       Value *VecPtr = Builder.CreateBitCast(LI->getPointerOperand(),
2355                                             VecTy->getPointerTo(AS));
2356
2357       // The pointer operand uses an in-tree scalar so we add the new BitCast to
2358       // ExternalUses list to make sure that an extract will be generated in the
2359       // future.
2360       if (ScalarToTreeEntry.count(LI->getPointerOperand()))
2361         ExternalUses.push_back(
2362             ExternalUser(LI->getPointerOperand(), cast<User>(VecPtr), 0));
2363
2364       unsigned Alignment = LI->getAlignment();
2365       LI = Builder.CreateLoad(VecPtr);
2366       if (!Alignment) {
2367         Alignment = DL.getABITypeAlignment(ScalarLoadTy);
2368       }
2369       LI->setAlignment(Alignment);
2370       E->VectorizedValue = LI;
2371       ++NumVectorInstructions;
2372       return propagateMetadata(LI, E->Scalars);
2373     }
2374     case Instruction::Store: {
2375       StoreInst *SI = cast<StoreInst>(VL0);
2376       unsigned Alignment = SI->getAlignment();
2377       unsigned AS = SI->getPointerAddressSpace();
2378
2379       ValueList ValueOp;
2380       for (Value *V : E->Scalars)
2381         ValueOp.push_back(cast<StoreInst>(V)->getValueOperand());
2382
2383       setInsertPointAfterBundle(E->Scalars);
2384
2385       Value *VecValue = vectorizeTree(ValueOp);
2386       Value *VecPtr = Builder.CreateBitCast(SI->getPointerOperand(),
2387                                             VecTy->getPointerTo(AS));
2388       StoreInst *S = Builder.CreateStore(VecValue, VecPtr);
2389
2390       // The pointer operand uses an in-tree scalar so we add the new BitCast to
2391       // ExternalUses list to make sure that an extract will be generated in the
2392       // future.
2393       if (ScalarToTreeEntry.count(SI->getPointerOperand()))
2394         ExternalUses.push_back(
2395             ExternalUser(SI->getPointerOperand(), cast<User>(VecPtr), 0));
2396
2397       if (!Alignment) {
2398         Alignment = DL.getABITypeAlignment(SI->getValueOperand()->getType());
2399       }
2400       S->setAlignment(Alignment);
2401       E->VectorizedValue = S;
2402       ++NumVectorInstructions;
2403       return propagateMetadata(S, E->Scalars);
2404     }
2405     case Instruction::GetElementPtr: {
2406       setInsertPointAfterBundle(E->Scalars);
2407
2408       ValueList Op0VL;
2409       for (Value *V : E->Scalars)
2410         Op0VL.push_back(cast<GetElementPtrInst>(V)->getOperand(0));
2411
2412       Value *Op0 = vectorizeTree(Op0VL);
2413
2414       std::vector<Value *> OpVecs;
2415       for (int j = 1, e = cast<GetElementPtrInst>(VL0)->getNumOperands(); j < e;
2416            ++j) {
2417         ValueList OpVL;
2418         for (Value *V : E->Scalars)
2419           OpVL.push_back(cast<GetElementPtrInst>(V)->getOperand(j));
2420
2421         Value *OpVec = vectorizeTree(OpVL);
2422         OpVecs.push_back(OpVec);
2423       }
2424
2425       Value *V = Builder.CreateGEP(
2426           cast<GetElementPtrInst>(VL0)->getSourceElementType(), Op0, OpVecs);
2427       E->VectorizedValue = V;
2428       ++NumVectorInstructions;
2429
2430       if (Instruction *I = dyn_cast<Instruction>(V))
2431         return propagateMetadata(I, E->Scalars);
2432
2433       return V;
2434     }
2435     case Instruction::Call: {
2436       CallInst *CI = cast<CallInst>(VL0);
2437       setInsertPointAfterBundle(E->Scalars);
2438       Function *FI;
2439       Intrinsic::ID IID  = Intrinsic::not_intrinsic;
2440       Value *ScalarArg = nullptr;
2441       if (CI && (FI = CI->getCalledFunction())) {
2442         IID = FI->getIntrinsicID();
2443       }
2444       std::vector<Value *> OpVecs;
2445       for (int j = 0, e = CI->getNumArgOperands(); j < e; ++j) {
2446         ValueList OpVL;
2447         // ctlz,cttz and powi are special intrinsics whose second argument is
2448         // a scalar. This argument should not be vectorized.
2449         if (hasVectorInstrinsicScalarOpd(IID, 1) && j == 1) {
2450           CallInst *CEI = cast<CallInst>(E->Scalars[0]);
2451           ScalarArg = CEI->getArgOperand(j);
2452           OpVecs.push_back(CEI->getArgOperand(j));
2453           continue;
2454         }
2455         for (Value *V : E->Scalars) {
2456           CallInst *CEI = cast<CallInst>(V);
2457           OpVL.push_back(CEI->getArgOperand(j));
2458         }
2459
2460         Value *OpVec = vectorizeTree(OpVL);
2461         DEBUG(dbgs() << "SLP: OpVec[" << j << "]: " << *OpVec << "\n");
2462         OpVecs.push_back(OpVec);
2463       }
2464
2465       Module *M = F->getParent();
2466       Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
2467       Type *Tys[] = { VectorType::get(CI->getType(), E->Scalars.size()) };
2468       Function *CF = Intrinsic::getDeclaration(M, ID, Tys);
2469       Value *V = Builder.CreateCall(CF, OpVecs);
2470
2471       // The scalar argument uses an in-tree scalar so we add the new vectorized
2472       // call to ExternalUses list to make sure that an extract will be
2473       // generated in the future.
2474       if (ScalarArg && ScalarToTreeEntry.count(ScalarArg))
2475         ExternalUses.push_back(ExternalUser(ScalarArg, cast<User>(V), 0));
2476
2477       E->VectorizedValue = V;
2478       ++NumVectorInstructions;
2479       return V;
2480     }
2481     case Instruction::ShuffleVector: {
2482       ValueList LHSVL, RHSVL;
2483       assert(isa<BinaryOperator>(VL0) && "Invalid Shuffle Vector Operand");
2484       reorderAltShuffleOperands(E->Scalars, LHSVL, RHSVL);
2485       setInsertPointAfterBundle(E->Scalars);
2486
2487       Value *LHS = vectorizeTree(LHSVL);
2488       Value *RHS = vectorizeTree(RHSVL);
2489
2490       if (Value *V = alreadyVectorized(E->Scalars))
2491         return V;
2492
2493       // Create a vector of LHS op1 RHS
2494       BinaryOperator *BinOp0 = cast<BinaryOperator>(VL0);
2495       Value *V0 = Builder.CreateBinOp(BinOp0->getOpcode(), LHS, RHS);
2496
2497       // Create a vector of LHS op2 RHS
2498       Instruction *VL1 = cast<Instruction>(E->Scalars[1]);
2499       BinaryOperator *BinOp1 = cast<BinaryOperator>(VL1);
2500       Value *V1 = Builder.CreateBinOp(BinOp1->getOpcode(), LHS, RHS);
2501
2502       // Create shuffle to take alternate operations from the vector.
2503       // Also, gather up odd and even scalar ops to propagate IR flags to
2504       // each vector operation.
2505       ValueList OddScalars, EvenScalars;
2506       unsigned e = E->Scalars.size();
2507       SmallVector<Constant *, 8> Mask(e);
2508       for (unsigned i = 0; i < e; ++i) {
2509         if (i & 1) {
2510           Mask[i] = Builder.getInt32(e + i);
2511           OddScalars.push_back(E->Scalars[i]);
2512         } else {
2513           Mask[i] = Builder.getInt32(i);
2514           EvenScalars.push_back(E->Scalars[i]);
2515         }
2516       }
2517
2518       Value *ShuffleMask = ConstantVector::get(Mask);
2519       propagateIRFlags(V0, EvenScalars);
2520       propagateIRFlags(V1, OddScalars);
2521
2522       Value *V = Builder.CreateShuffleVector(V0, V1, ShuffleMask);
2523       E->VectorizedValue = V;
2524       ++NumVectorInstructions;
2525       if (Instruction *I = dyn_cast<Instruction>(V))
2526         return propagateMetadata(I, E->Scalars);
2527
2528       return V;
2529     }
2530     default:
2531     llvm_unreachable("unknown inst");
2532   }
2533   return nullptr;
2534 }
2535
2536 Value *BoUpSLP::vectorizeTree() {
2537   
2538   // All blocks must be scheduled before any instructions are inserted.
2539   for (auto &BSIter : BlocksSchedules) {
2540     scheduleBlock(BSIter.second.get());
2541   }
2542
2543   Builder.SetInsertPoint(&F->getEntryBlock().front());
2544   vectorizeTree(&VectorizableTree[0]);
2545
2546   DEBUG(dbgs() << "SLP: Extracting " << ExternalUses.size() << " values .\n");
2547
2548   // Extract all of the elements with the external uses.
2549   for (UserList::iterator it = ExternalUses.begin(), e = ExternalUses.end();
2550        it != e; ++it) {
2551     Value *Scalar = it->Scalar;
2552     llvm::User *User = it->User;
2553
2554     // Skip users that we already RAUW. This happens when one instruction
2555     // has multiple uses of the same value.
2556     if (std::find(Scalar->user_begin(), Scalar->user_end(), User) ==
2557         Scalar->user_end())
2558       continue;
2559     assert(ScalarToTreeEntry.count(Scalar) && "Invalid scalar");
2560
2561     int Idx = ScalarToTreeEntry[Scalar];
2562     TreeEntry *E = &VectorizableTree[Idx];
2563     assert(!E->NeedToGather && "Extracting from a gather list");
2564
2565     Value *Vec = E->VectorizedValue;
2566     assert(Vec && "Can't find vectorizable value");
2567
2568     Value *Lane = Builder.getInt32(it->Lane);
2569     // Generate extracts for out-of-tree users.
2570     // Find the insertion point for the extractelement lane.
2571     if (isa<Instruction>(Vec)){
2572       if (PHINode *PH = dyn_cast<PHINode>(User)) {
2573         for (int i = 0, e = PH->getNumIncomingValues(); i != e; ++i) {
2574           if (PH->getIncomingValue(i) == Scalar) {
2575             Builder.SetInsertPoint(PH->getIncomingBlock(i)->getTerminator());
2576             Value *Ex = Builder.CreateExtractElement(Vec, Lane);
2577             CSEBlocks.insert(PH->getIncomingBlock(i));
2578             PH->setOperand(i, Ex);
2579           }
2580         }
2581       } else {
2582         Builder.SetInsertPoint(cast<Instruction>(User));
2583         Value *Ex = Builder.CreateExtractElement(Vec, Lane);
2584         CSEBlocks.insert(cast<Instruction>(User)->getParent());
2585         User->replaceUsesOfWith(Scalar, Ex);
2586      }
2587     } else {
2588       Builder.SetInsertPoint(&F->getEntryBlock().front());
2589       Value *Ex = Builder.CreateExtractElement(Vec, Lane);
2590       CSEBlocks.insert(&F->getEntryBlock());
2591       User->replaceUsesOfWith(Scalar, Ex);
2592     }
2593
2594     DEBUG(dbgs() << "SLP: Replaced:" << *User << ".\n");
2595   }
2596
2597   // For each vectorized value:
2598   for (int EIdx = 0, EE = VectorizableTree.size(); EIdx < EE; ++EIdx) {
2599     TreeEntry *Entry = &VectorizableTree[EIdx];
2600
2601     // For each lane:
2602     for (int Lane = 0, LE = Entry->Scalars.size(); Lane != LE; ++Lane) {
2603       Value *Scalar = Entry->Scalars[Lane];
2604       // No need to handle users of gathered values.
2605       if (Entry->NeedToGather)
2606         continue;
2607
2608       assert(Entry->VectorizedValue && "Can't find vectorizable value");
2609
2610       Type *Ty = Scalar->getType();
2611       if (!Ty->isVoidTy()) {
2612 #ifndef NDEBUG
2613         for (User *U : Scalar->users()) {
2614           DEBUG(dbgs() << "SLP: \tvalidating user:" << *U << ".\n");
2615
2616           assert((ScalarToTreeEntry.count(U) ||
2617                   // It is legal to replace users in the ignorelist by undef.
2618                   (std::find(UserIgnoreList.begin(), UserIgnoreList.end(), U) !=
2619                    UserIgnoreList.end())) &&
2620                  "Replacing out-of-tree value with undef");
2621         }
2622 #endif
2623         Value *Undef = UndefValue::get(Ty);
2624         Scalar->replaceAllUsesWith(Undef);
2625       }
2626       DEBUG(dbgs() << "SLP: \tErasing scalar:" << *Scalar << ".\n");
2627       eraseInstruction(cast<Instruction>(Scalar));
2628     }
2629   }
2630
2631   Builder.ClearInsertionPoint();
2632
2633   return VectorizableTree[0].VectorizedValue;
2634 }
2635
2636 void BoUpSLP::optimizeGatherSequence() {
2637   DEBUG(dbgs() << "SLP: Optimizing " << GatherSeq.size()
2638         << " gather sequences instructions.\n");
2639   // LICM InsertElementInst sequences.
2640   for (SetVector<Instruction *>::iterator it = GatherSeq.begin(),
2641        e = GatherSeq.end(); it != e; ++it) {
2642     InsertElementInst *Insert = dyn_cast<InsertElementInst>(*it);
2643
2644     if (!Insert)
2645       continue;
2646
2647     // Check if this block is inside a loop.
2648     Loop *L = LI->getLoopFor(Insert->getParent());
2649     if (!L)
2650       continue;
2651
2652     // Check if it has a preheader.
2653     BasicBlock *PreHeader = L->getLoopPreheader();
2654     if (!PreHeader)
2655       continue;
2656
2657     // If the vector or the element that we insert into it are
2658     // instructions that are defined in this basic block then we can't
2659     // hoist this instruction.
2660     Instruction *CurrVec = dyn_cast<Instruction>(Insert->getOperand(0));
2661     Instruction *NewElem = dyn_cast<Instruction>(Insert->getOperand(1));
2662     if (CurrVec && L->contains(CurrVec))
2663       continue;
2664     if (NewElem && L->contains(NewElem))
2665       continue;
2666
2667     // We can hoist this instruction. Move it to the pre-header.
2668     Insert->moveBefore(PreHeader->getTerminator());
2669   }
2670
2671   // Make a list of all reachable blocks in our CSE queue.
2672   SmallVector<const DomTreeNode *, 8> CSEWorkList;
2673   CSEWorkList.reserve(CSEBlocks.size());
2674   for (BasicBlock *BB : CSEBlocks)
2675     if (DomTreeNode *N = DT->getNode(BB)) {
2676       assert(DT->isReachableFromEntry(N));
2677       CSEWorkList.push_back(N);
2678     }
2679
2680   // Sort blocks by domination. This ensures we visit a block after all blocks
2681   // dominating it are visited.
2682   std::stable_sort(CSEWorkList.begin(), CSEWorkList.end(),
2683                    [this](const DomTreeNode *A, const DomTreeNode *B) {
2684     return DT->properlyDominates(A, B);
2685   });
2686
2687   // Perform O(N^2) search over the gather sequences and merge identical
2688   // instructions. TODO: We can further optimize this scan if we split the
2689   // instructions into different buckets based on the insert lane.
2690   SmallVector<Instruction *, 16> Visited;
2691   for (auto I = CSEWorkList.begin(), E = CSEWorkList.end(); I != E; ++I) {
2692     assert((I == CSEWorkList.begin() || !DT->dominates(*I, *std::prev(I))) &&
2693            "Worklist not sorted properly!");
2694     BasicBlock *BB = (*I)->getBlock();
2695     // For all instructions in blocks containing gather sequences:
2696     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e;) {
2697       Instruction *In = &*it++;
2698       if (!isa<InsertElementInst>(In) && !isa<ExtractElementInst>(In))
2699         continue;
2700
2701       // Check if we can replace this instruction with any of the
2702       // visited instructions.
2703       for (SmallVectorImpl<Instruction *>::iterator v = Visited.begin(),
2704                                                     ve = Visited.end();
2705            v != ve; ++v) {
2706         if (In->isIdenticalTo(*v) &&
2707             DT->dominates((*v)->getParent(), In->getParent())) {
2708           In->replaceAllUsesWith(*v);
2709           eraseInstruction(In);
2710           In = nullptr;
2711           break;
2712         }
2713       }
2714       if (In) {
2715         assert(std::find(Visited.begin(), Visited.end(), In) == Visited.end());
2716         Visited.push_back(In);
2717       }
2718     }
2719   }
2720   CSEBlocks.clear();
2721   GatherSeq.clear();
2722 }
2723
2724 // Groups the instructions to a bundle (which is then a single scheduling entity)
2725 // and schedules instructions until the bundle gets ready.
2726 bool BoUpSLP::BlockScheduling::tryScheduleBundle(ArrayRef<Value *> VL,
2727                                                  BoUpSLP *SLP) {
2728   if (isa<PHINode>(VL[0]))
2729     return true;
2730
2731   // Initialize the instruction bundle.
2732   Instruction *OldScheduleEnd = ScheduleEnd;
2733   ScheduleData *PrevInBundle = nullptr;
2734   ScheduleData *Bundle = nullptr;
2735   bool ReSchedule = false;
2736   DEBUG(dbgs() << "SLP:  bundle: " << *VL[0] << "\n");
2737
2738   // Make sure that the scheduling region contains all
2739   // instructions of the bundle.
2740   for (Value *V : VL) {
2741     if (!extendSchedulingRegion(V))
2742       return false;
2743   }
2744
2745   for (Value *V : VL) {
2746     ScheduleData *BundleMember = getScheduleData(V);
2747     assert(BundleMember &&
2748            "no ScheduleData for bundle member (maybe not in same basic block)");
2749     if (BundleMember->IsScheduled) {
2750       // A bundle member was scheduled as single instruction before and now
2751       // needs to be scheduled as part of the bundle. We just get rid of the
2752       // existing schedule.
2753       DEBUG(dbgs() << "SLP:  reset schedule because " << *BundleMember
2754                    << " was already scheduled\n");
2755       ReSchedule = true;
2756     }
2757     assert(BundleMember->isSchedulingEntity() &&
2758            "bundle member already part of other bundle");
2759     if (PrevInBundle) {
2760       PrevInBundle->NextInBundle = BundleMember;
2761     } else {
2762       Bundle = BundleMember;
2763     }
2764     BundleMember->UnscheduledDepsInBundle = 0;
2765     Bundle->UnscheduledDepsInBundle += BundleMember->UnscheduledDeps;
2766
2767     // Group the instructions to a bundle.
2768     BundleMember->FirstInBundle = Bundle;
2769     PrevInBundle = BundleMember;
2770   }
2771   if (ScheduleEnd != OldScheduleEnd) {
2772     // The scheduling region got new instructions at the lower end (or it is a
2773     // new region for the first bundle). This makes it necessary to
2774     // recalculate all dependencies.
2775     // It is seldom that this needs to be done a second time after adding the
2776     // initial bundle to the region.
2777     for (auto *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) {
2778       ScheduleData *SD = getScheduleData(I);
2779       SD->clearDependencies();
2780     }
2781     ReSchedule = true;
2782   }
2783   if (ReSchedule) {
2784     resetSchedule();
2785     initialFillReadyList(ReadyInsts);
2786   }
2787
2788   DEBUG(dbgs() << "SLP: try schedule bundle " << *Bundle << " in block "
2789                << BB->getName() << "\n");
2790
2791   calculateDependencies(Bundle, true, SLP);
2792
2793   // Now try to schedule the new bundle. As soon as the bundle is "ready" it
2794   // means that there are no cyclic dependencies and we can schedule it.
2795   // Note that's important that we don't "schedule" the bundle yet (see
2796   // cancelScheduling).
2797   while (!Bundle->isReady() && !ReadyInsts.empty()) {
2798
2799     ScheduleData *pickedSD = ReadyInsts.back();
2800     ReadyInsts.pop_back();
2801
2802     if (pickedSD->isSchedulingEntity() && pickedSD->isReady()) {
2803       schedule(pickedSD, ReadyInsts);
2804     }
2805   }
2806   if (!Bundle->isReady()) {
2807     cancelScheduling(VL);
2808     return false;
2809   }
2810   return true;
2811 }
2812
2813 void BoUpSLP::BlockScheduling::cancelScheduling(ArrayRef<Value *> VL) {
2814   if (isa<PHINode>(VL[0]))
2815     return;
2816
2817   ScheduleData *Bundle = getScheduleData(VL[0]);
2818   DEBUG(dbgs() << "SLP:  cancel scheduling of " << *Bundle << "\n");
2819   assert(!Bundle->IsScheduled &&
2820          "Can't cancel bundle which is already scheduled");
2821   assert(Bundle->isSchedulingEntity() && Bundle->isPartOfBundle() &&
2822          "tried to unbundle something which is not a bundle");
2823
2824   // Un-bundle: make single instructions out of the bundle.
2825   ScheduleData *BundleMember = Bundle;
2826   while (BundleMember) {
2827     assert(BundleMember->FirstInBundle == Bundle && "corrupt bundle links");
2828     BundleMember->FirstInBundle = BundleMember;
2829     ScheduleData *Next = BundleMember->NextInBundle;
2830     BundleMember->NextInBundle = nullptr;
2831     BundleMember->UnscheduledDepsInBundle = BundleMember->UnscheduledDeps;
2832     if (BundleMember->UnscheduledDepsInBundle == 0) {
2833       ReadyInsts.insert(BundleMember);
2834     }
2835     BundleMember = Next;
2836   }
2837 }
2838
2839 bool BoUpSLP::BlockScheduling::extendSchedulingRegion(Value *V) {
2840   if (getScheduleData(V))
2841     return true;
2842   Instruction *I = dyn_cast<Instruction>(V);
2843   assert(I && "bundle member must be an instruction");
2844   assert(!isa<PHINode>(I) && "phi nodes don't need to be scheduled");
2845   if (!ScheduleStart) {
2846     // It's the first instruction in the new region.
2847     initScheduleData(I, I->getNextNode(), nullptr, nullptr);
2848     ScheduleStart = I;
2849     ScheduleEnd = I->getNextNode();
2850     assert(ScheduleEnd && "tried to vectorize a TerminatorInst?");
2851     DEBUG(dbgs() << "SLP:  initialize schedule region to " << *I << "\n");
2852     return true;
2853   }
2854   // Search up and down at the same time, because we don't know if the new
2855   // instruction is above or below the existing scheduling region.
2856   BasicBlock::reverse_iterator UpIter(ScheduleStart->getIterator());
2857   BasicBlock::reverse_iterator UpperEnd = BB->rend();
2858   BasicBlock::iterator DownIter(ScheduleEnd);
2859   BasicBlock::iterator LowerEnd = BB->end();
2860   for (;;) {
2861     if (++ScheduleRegionSize > ScheduleRegionSizeLimit) {
2862       DEBUG(dbgs() << "SLP:  exceeded schedule region size limit\n");
2863       return false;
2864     }
2865
2866     if (UpIter != UpperEnd) {
2867       if (&*UpIter == I) {
2868         initScheduleData(I, ScheduleStart, nullptr, FirstLoadStoreInRegion);
2869         ScheduleStart = I;
2870         DEBUG(dbgs() << "SLP:  extend schedule region start to " << *I << "\n");
2871         return true;
2872       }
2873       UpIter++;
2874     }
2875     if (DownIter != LowerEnd) {
2876       if (&*DownIter == I) {
2877         initScheduleData(ScheduleEnd, I->getNextNode(), LastLoadStoreInRegion,
2878                          nullptr);
2879         ScheduleEnd = I->getNextNode();
2880         assert(ScheduleEnd && "tried to vectorize a TerminatorInst?");
2881         DEBUG(dbgs() << "SLP:  extend schedule region end to " << *I << "\n");
2882         return true;
2883       }
2884       DownIter++;
2885     }
2886     assert((UpIter != UpperEnd || DownIter != LowerEnd) &&
2887            "instruction not found in block");
2888   }
2889   return true;
2890 }
2891
2892 void BoUpSLP::BlockScheduling::initScheduleData(Instruction *FromI,
2893                                                 Instruction *ToI,
2894                                                 ScheduleData *PrevLoadStore,
2895                                                 ScheduleData *NextLoadStore) {
2896   ScheduleData *CurrentLoadStore = PrevLoadStore;
2897   for (Instruction *I = FromI; I != ToI; I = I->getNextNode()) {
2898     ScheduleData *SD = ScheduleDataMap[I];
2899     if (!SD) {
2900       // Allocate a new ScheduleData for the instruction.
2901       if (ChunkPos >= ChunkSize) {
2902         ScheduleDataChunks.push_back(
2903             llvm::make_unique<ScheduleData[]>(ChunkSize));
2904         ChunkPos = 0;
2905       }
2906       SD = &(ScheduleDataChunks.back()[ChunkPos++]);
2907       ScheduleDataMap[I] = SD;
2908       SD->Inst = I;
2909     }
2910     assert(!isInSchedulingRegion(SD) &&
2911            "new ScheduleData already in scheduling region");
2912     SD->init(SchedulingRegionID);
2913
2914     if (I->mayReadOrWriteMemory()) {
2915       // Update the linked list of memory accessing instructions.
2916       if (CurrentLoadStore) {
2917         CurrentLoadStore->NextLoadStore = SD;
2918       } else {
2919         FirstLoadStoreInRegion = SD;
2920       }
2921       CurrentLoadStore = SD;
2922     }
2923   }
2924   if (NextLoadStore) {
2925     if (CurrentLoadStore)
2926       CurrentLoadStore->NextLoadStore = NextLoadStore;
2927   } else {
2928     LastLoadStoreInRegion = CurrentLoadStore;
2929   }
2930 }
2931
2932 void BoUpSLP::BlockScheduling::calculateDependencies(ScheduleData *SD,
2933                                                      bool InsertInReadyList,
2934                                                      BoUpSLP *SLP) {
2935   assert(SD->isSchedulingEntity());
2936
2937   SmallVector<ScheduleData *, 10> WorkList;
2938   WorkList.push_back(SD);
2939
2940   while (!WorkList.empty()) {
2941     ScheduleData *SD = WorkList.back();
2942     WorkList.pop_back();
2943
2944     ScheduleData *BundleMember = SD;
2945     while (BundleMember) {
2946       assert(isInSchedulingRegion(BundleMember));
2947       if (!BundleMember->hasValidDependencies()) {
2948
2949         DEBUG(dbgs() << "SLP:       update deps of " << *BundleMember << "\n");
2950         BundleMember->Dependencies = 0;
2951         BundleMember->resetUnscheduledDeps();
2952
2953         // Handle def-use chain dependencies.
2954         for (User *U : BundleMember->Inst->users()) {
2955           if (isa<Instruction>(U)) {
2956             ScheduleData *UseSD = getScheduleData(U);
2957             if (UseSD && isInSchedulingRegion(UseSD->FirstInBundle)) {
2958               BundleMember->Dependencies++;
2959               ScheduleData *DestBundle = UseSD->FirstInBundle;
2960               if (!DestBundle->IsScheduled) {
2961                 BundleMember->incrementUnscheduledDeps(1);
2962               }
2963               if (!DestBundle->hasValidDependencies()) {
2964                 WorkList.push_back(DestBundle);
2965               }
2966             }
2967           } else {
2968             // I'm not sure if this can ever happen. But we need to be safe.
2969             // This lets the instruction/bundle never be scheduled and
2970             // eventually disable vectorization.
2971             BundleMember->Dependencies++;
2972             BundleMember->incrementUnscheduledDeps(1);
2973           }
2974         }
2975
2976         // Handle the memory dependencies.
2977         ScheduleData *DepDest = BundleMember->NextLoadStore;
2978         if (DepDest) {
2979           Instruction *SrcInst = BundleMember->Inst;
2980           MemoryLocation SrcLoc = getLocation(SrcInst, SLP->AA);
2981           bool SrcMayWrite = BundleMember->Inst->mayWriteToMemory();
2982           unsigned numAliased = 0;
2983           unsigned DistToSrc = 1;
2984
2985           while (DepDest) {
2986             assert(isInSchedulingRegion(DepDest));
2987
2988             // We have two limits to reduce the complexity:
2989             // 1) AliasedCheckLimit: It's a small limit to reduce calls to
2990             //    SLP->isAliased (which is the expensive part in this loop).
2991             // 2) MaxMemDepDistance: It's for very large blocks and it aborts
2992             //    the whole loop (even if the loop is fast, it's quadratic).
2993             //    It's important for the loop break condition (see below) to
2994             //    check this limit even between two read-only instructions.
2995             if (DistToSrc >= MaxMemDepDistance ||
2996                     ((SrcMayWrite || DepDest->Inst->mayWriteToMemory()) &&
2997                      (numAliased >= AliasedCheckLimit ||
2998                       SLP->isAliased(SrcLoc, SrcInst, DepDest->Inst)))) {
2999
3000               // We increment the counter only if the locations are aliased
3001               // (instead of counting all alias checks). This gives a better
3002               // balance between reduced runtime and accurate dependencies.
3003               numAliased++;
3004
3005               DepDest->MemoryDependencies.push_back(BundleMember);
3006               BundleMember->Dependencies++;
3007               ScheduleData *DestBundle = DepDest->FirstInBundle;
3008               if (!DestBundle->IsScheduled) {
3009                 BundleMember->incrementUnscheduledDeps(1);
3010               }
3011               if (!DestBundle->hasValidDependencies()) {
3012                 WorkList.push_back(DestBundle);
3013               }
3014             }
3015             DepDest = DepDest->NextLoadStore;
3016
3017             // Example, explaining the loop break condition: Let's assume our
3018             // starting instruction is i0 and MaxMemDepDistance = 3.
3019             //
3020             //                      +--------v--v--v
3021             //             i0,i1,i2,i3,i4,i5,i6,i7,i8
3022             //             +--------^--^--^
3023             //
3024             // MaxMemDepDistance let us stop alias-checking at i3 and we add
3025             // dependencies from i0 to i3,i4,.. (even if they are not aliased).
3026             // Previously we already added dependencies from i3 to i6,i7,i8
3027             // (because of MaxMemDepDistance). As we added a dependency from
3028             // i0 to i3, we have transitive dependencies from i0 to i6,i7,i8
3029             // and we can abort this loop at i6.
3030             if (DistToSrc >= 2 * MaxMemDepDistance)
3031                 break;
3032             DistToSrc++;
3033           }
3034         }
3035       }
3036       BundleMember = BundleMember->NextInBundle;
3037     }
3038     if (InsertInReadyList && SD->isReady()) {
3039       ReadyInsts.push_back(SD);
3040       DEBUG(dbgs() << "SLP:     gets ready on update: " << *SD->Inst << "\n");
3041     }
3042   }
3043 }
3044
3045 void BoUpSLP::BlockScheduling::resetSchedule() {
3046   assert(ScheduleStart &&
3047          "tried to reset schedule on block which has not been scheduled");
3048   for (Instruction *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) {
3049     ScheduleData *SD = getScheduleData(I);
3050     assert(isInSchedulingRegion(SD));
3051     SD->IsScheduled = false;
3052     SD->resetUnscheduledDeps();
3053   }
3054   ReadyInsts.clear();
3055 }
3056
3057 void BoUpSLP::scheduleBlock(BlockScheduling *BS) {
3058   
3059   if (!BS->ScheduleStart)
3060     return;
3061   
3062   DEBUG(dbgs() << "SLP: schedule block " << BS->BB->getName() << "\n");
3063
3064   BS->resetSchedule();
3065
3066   // For the real scheduling we use a more sophisticated ready-list: it is
3067   // sorted by the original instruction location. This lets the final schedule
3068   // be as  close as possible to the original instruction order.
3069   struct ScheduleDataCompare {
3070     bool operator()(ScheduleData *SD1, ScheduleData *SD2) {
3071       return SD2->SchedulingPriority < SD1->SchedulingPriority;
3072     }
3073   };
3074   std::set<ScheduleData *, ScheduleDataCompare> ReadyInsts;
3075
3076   // Ensure that all dependency data is updated and fill the ready-list with
3077   // initial instructions.
3078   int Idx = 0;
3079   int NumToSchedule = 0;
3080   for (auto *I = BS->ScheduleStart; I != BS->ScheduleEnd;
3081        I = I->getNextNode()) {
3082     ScheduleData *SD = BS->getScheduleData(I);
3083     assert(
3084         SD->isPartOfBundle() == (ScalarToTreeEntry.count(SD->Inst) != 0) &&
3085         "scheduler and vectorizer have different opinion on what is a bundle");
3086     SD->FirstInBundle->SchedulingPriority = Idx++;
3087     if (SD->isSchedulingEntity()) {
3088       BS->calculateDependencies(SD, false, this);
3089       NumToSchedule++;
3090     }
3091   }
3092   BS->initialFillReadyList(ReadyInsts);
3093
3094   Instruction *LastScheduledInst = BS->ScheduleEnd;
3095
3096   // Do the "real" scheduling.
3097   while (!ReadyInsts.empty()) {
3098     ScheduleData *picked = *ReadyInsts.begin();
3099     ReadyInsts.erase(ReadyInsts.begin());
3100
3101     // Move the scheduled instruction(s) to their dedicated places, if not
3102     // there yet.
3103     ScheduleData *BundleMember = picked;
3104     while (BundleMember) {
3105       Instruction *pickedInst = BundleMember->Inst;
3106       if (LastScheduledInst->getNextNode() != pickedInst) {
3107         BS->BB->getInstList().remove(pickedInst);
3108         BS->BB->getInstList().insert(LastScheduledInst->getIterator(),
3109                                      pickedInst);
3110       }
3111       LastScheduledInst = pickedInst;
3112       BundleMember = BundleMember->NextInBundle;
3113     }
3114
3115     BS->schedule(picked, ReadyInsts);
3116     NumToSchedule--;
3117   }
3118   assert(NumToSchedule == 0 && "could not schedule all instructions");
3119
3120   // Avoid duplicate scheduling of the block.
3121   BS->ScheduleStart = nullptr;
3122 }
3123
3124 /// The SLPVectorizer Pass.
3125 struct SLPVectorizer : public FunctionPass {
3126   typedef SmallVector<StoreInst *, 8> StoreList;
3127   typedef MapVector<Value *, StoreList> StoreListMap;
3128
3129   /// Pass identification, replacement for typeid
3130   static char ID;
3131
3132   explicit SLPVectorizer() : FunctionPass(ID) {
3133     initializeSLPVectorizerPass(*PassRegistry::getPassRegistry());
3134   }
3135
3136   ScalarEvolution *SE;
3137   TargetTransformInfo *TTI;
3138   TargetLibraryInfo *TLI;
3139   AliasAnalysis *AA;
3140   LoopInfo *LI;
3141   DominatorTree *DT;
3142   AssumptionCache *AC;
3143
3144   bool runOnFunction(Function &F) override {
3145     if (skipOptnoneFunction(F))
3146       return false;
3147
3148     SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
3149     TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
3150     auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
3151     TLI = TLIP ? &TLIP->getTLI() : nullptr;
3152     AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
3153     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
3154     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
3155     AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
3156
3157     StoreRefs.clear();
3158     bool Changed = false;
3159
3160     // If the target claims to have no vector registers don't attempt
3161     // vectorization.
3162     if (!TTI->getNumberOfRegisters(true))
3163       return false;
3164
3165     // Use the vector register size specified by the target unless overridden
3166     // by a command-line option.
3167     // TODO: It would be better to limit the vectorization factor based on
3168     //       data type rather than just register size. For example, x86 AVX has
3169     //       256-bit registers, but it does not support integer operations
3170     //       at that width (that requires AVX2).
3171     if (MaxVectorRegSizeOption.getNumOccurrences())
3172       MaxVecRegSize = MaxVectorRegSizeOption;
3173     else
3174       MaxVecRegSize = TTI->getRegisterBitWidth(true);
3175
3176     // Don't vectorize when the attribute NoImplicitFloat is used.
3177     if (F.hasFnAttribute(Attribute::NoImplicitFloat))
3178       return false;
3179
3180     DEBUG(dbgs() << "SLP: Analyzing blocks in " << F.getName() << ".\n");
3181
3182     // Use the bottom up slp vectorizer to construct chains that start with
3183     // store instructions.
3184     BoUpSLP R(&F, SE, TTI, TLI, AA, LI, DT, AC);
3185
3186     // A general note: the vectorizer must use BoUpSLP::eraseInstruction() to
3187     // delete instructions.
3188
3189     // Scan the blocks in the function in post order.
3190     for (auto BB : post_order(&F.getEntryBlock())) {
3191       // Vectorize trees that end at stores.
3192       if (unsigned count = collectStores(BB, R)) {
3193         (void)count;
3194         DEBUG(dbgs() << "SLP: Found " << count << " stores to vectorize.\n");
3195         Changed |= vectorizeStoreChains(R);
3196       }
3197
3198       // Vectorize trees that end at reductions.
3199       Changed |= vectorizeChainsInBlock(BB, R);
3200     }
3201
3202     if (Changed) {
3203       R.optimizeGatherSequence();
3204       DEBUG(dbgs() << "SLP: vectorized \"" << F.getName() << "\"\n");
3205       DEBUG(verifyFunction(F));
3206     }
3207     return Changed;
3208   }
3209
3210   void getAnalysisUsage(AnalysisUsage &AU) const override {
3211     FunctionPass::getAnalysisUsage(AU);
3212     AU.addRequired<AssumptionCacheTracker>();
3213     AU.addRequired<ScalarEvolutionWrapperPass>();
3214     AU.addRequired<AAResultsWrapperPass>();
3215     AU.addRequired<TargetTransformInfoWrapperPass>();
3216     AU.addRequired<LoopInfoWrapperPass>();
3217     AU.addRequired<DominatorTreeWrapperPass>();
3218     AU.addPreserved<LoopInfoWrapperPass>();
3219     AU.addPreserved<DominatorTreeWrapperPass>();
3220     AU.setPreservesCFG();
3221   }
3222
3223 private:
3224
3225   /// \brief Collect memory references and sort them according to their base
3226   /// object. We sort the stores to their base objects to reduce the cost of the
3227   /// quadratic search on the stores. TODO: We can further reduce this cost
3228   /// if we flush the chain creation every time we run into a memory barrier.
3229   unsigned collectStores(BasicBlock *BB, BoUpSLP &R);
3230
3231   /// \brief Try to vectorize a chain that starts at two arithmetic instrs.
3232   bool tryToVectorizePair(Value *A, Value *B, BoUpSLP &R);
3233
3234   /// \brief Try to vectorize a list of operands.
3235   /// \@param BuildVector A list of users to ignore for the purpose of
3236   ///                     scheduling and that don't need extracting.
3237   /// \returns true if a value was vectorized.
3238   bool tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R,
3239                           ArrayRef<Value *> BuildVector = None,
3240                           bool allowReorder = false);
3241
3242   /// \brief Try to vectorize a chain that may start at the operands of \V;
3243   bool tryToVectorize(BinaryOperator *V, BoUpSLP &R);
3244
3245   /// \brief Vectorize the stores that were collected in StoreRefs.
3246   bool vectorizeStoreChains(BoUpSLP &R);
3247
3248   /// \brief Scan the basic block and look for patterns that are likely to start
3249   /// a vectorization chain.
3250   bool vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R);
3251
3252   bool vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold,
3253                            BoUpSLP &R, unsigned VecRegSize);
3254
3255   bool vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold,
3256                        BoUpSLP &R);
3257 private:
3258   StoreListMap StoreRefs;
3259   unsigned MaxVecRegSize; // This is set by TTI or overridden by cl::opt.
3260 };
3261
3262 /// \brief Check that the Values in the slice in VL array are still existent in
3263 /// the WeakVH array.
3264 /// Vectorization of part of the VL array may cause later values in the VL array
3265 /// to become invalid. We track when this has happened in the WeakVH array.
3266 static bool hasValueBeenRAUWed(ArrayRef<Value *> VL, ArrayRef<WeakVH> VH,
3267                                unsigned SliceBegin, unsigned SliceSize) {
3268   VL = VL.slice(SliceBegin, SliceSize);
3269   VH = VH.slice(SliceBegin, SliceSize);
3270   return !std::equal(VL.begin(), VL.end(), VH.begin());
3271 }
3272
3273 bool SLPVectorizer::vectorizeStoreChain(ArrayRef<Value *> Chain,
3274                                         int CostThreshold, BoUpSLP &R,
3275                                         unsigned VecRegSize) {
3276   unsigned ChainLen = Chain.size();
3277   DEBUG(dbgs() << "SLP: Analyzing a store chain of length " << ChainLen
3278         << "\n");
3279   Type *StoreTy = cast<StoreInst>(Chain[0])->getValueOperand()->getType();
3280   auto &DL = cast<StoreInst>(Chain[0])->getModule()->getDataLayout();
3281   unsigned Sz = DL.getTypeSizeInBits(StoreTy);
3282   unsigned VF = VecRegSize / Sz;
3283
3284   if (!isPowerOf2_32(Sz) || VF < 2)
3285     return false;
3286
3287   // Keep track of values that were deleted by vectorizing in the loop below.
3288   SmallVector<WeakVH, 8> TrackValues(Chain.begin(), Chain.end());
3289
3290   bool Changed = false;
3291   // Look for profitable vectorizable trees at all offsets, starting at zero.
3292   for (unsigned i = 0, e = ChainLen; i < e; ++i) {
3293     if (i + VF > e)
3294       break;
3295
3296     // Check that a previous iteration of this loop did not delete the Value.
3297     if (hasValueBeenRAUWed(Chain, TrackValues, i, VF))
3298       continue;
3299
3300     DEBUG(dbgs() << "SLP: Analyzing " << VF << " stores at offset " << i
3301           << "\n");
3302     ArrayRef<Value *> Operands = Chain.slice(i, VF);
3303
3304     R.buildTree(Operands);
3305
3306     int Cost = R.getTreeCost();
3307
3308     DEBUG(dbgs() << "SLP: Found cost=" << Cost << " for VF=" << VF << "\n");
3309     if (Cost < CostThreshold) {
3310       DEBUG(dbgs() << "SLP: Decided to vectorize cost=" << Cost << "\n");
3311       R.vectorizeTree();
3312
3313       // Move to the next bundle.
3314       i += VF - 1;
3315       Changed = true;
3316     }
3317   }
3318
3319   return Changed;
3320 }
3321
3322 bool SLPVectorizer::vectorizeStores(ArrayRef<StoreInst *> Stores,
3323                                     int costThreshold, BoUpSLP &R) {
3324   SetVector<StoreInst *> Heads, Tails;
3325   SmallDenseMap<StoreInst *, StoreInst *> ConsecutiveChain;
3326
3327   // We may run into multiple chains that merge into a single chain. We mark the
3328   // stores that we vectorized so that we don't visit the same store twice.
3329   BoUpSLP::ValueSet VectorizedStores;
3330   bool Changed = false;
3331
3332   // Do a quadratic search on all of the given stores and find
3333   // all of the pairs of stores that follow each other.
3334   SmallVector<unsigned, 16> IndexQueue;
3335   for (unsigned i = 0, e = Stores.size(); i < e; ++i) {
3336     const DataLayout &DL = Stores[i]->getModule()->getDataLayout();
3337     IndexQueue.clear();
3338     // If a store has multiple consecutive store candidates, search Stores
3339     // array according to the sequence: from i+1 to e, then from i-1 to 0.
3340     // This is because usually pairing with immediate succeeding or preceding
3341     // candidate create the best chance to find slp vectorization opportunity.
3342     unsigned j = 0;
3343     for (j = i + 1; j < e; ++j)
3344       IndexQueue.push_back(j);
3345     for (j = i; j > 0; --j)
3346       IndexQueue.push_back(j - 1);
3347
3348     for (auto &k : IndexQueue) {
3349       if (R.isConsecutiveAccess(Stores[i], Stores[k], DL)) {
3350         Tails.insert(Stores[k]);
3351         Heads.insert(Stores[i]);
3352         ConsecutiveChain[Stores[i]] = Stores[k];
3353         break;
3354       }
3355     }
3356   }
3357
3358   // For stores that start but don't end a link in the chain:
3359   for (SetVector<StoreInst *>::iterator it = Heads.begin(), e = Heads.end();
3360        it != e; ++it) {
3361     if (Tails.count(*it))
3362       continue;
3363
3364     // We found a store instr that starts a chain. Now follow the chain and try
3365     // to vectorize it.
3366     BoUpSLP::ValueList Operands;
3367     StoreInst *I = *it;
3368     // Collect the chain into a list.
3369     while (Tails.count(I) || Heads.count(I)) {
3370       if (VectorizedStores.count(I))
3371         break;
3372       Operands.push_back(I);
3373       // Move to the next value in the chain.
3374       I = ConsecutiveChain[I];
3375     }
3376
3377     // FIXME: Is division-by-2 the correct step? Should we assert that the
3378     // register size is a power-of-2?
3379     for (unsigned Size = MaxVecRegSize; Size >= MinVecRegSize; Size /= 2) {
3380       if (vectorizeStoreChain(Operands, costThreshold, R, Size)) {
3381         // Mark the vectorized stores so that we don't vectorize them again.
3382         VectorizedStores.insert(Operands.begin(), Operands.end());
3383         Changed = true;
3384         break;
3385       }
3386     }
3387   }
3388
3389   return Changed;
3390 }
3391
3392
3393 unsigned SLPVectorizer::collectStores(BasicBlock *BB, BoUpSLP &R) {
3394   unsigned count = 0;
3395   StoreRefs.clear();
3396   const DataLayout &DL = BB->getModule()->getDataLayout();
3397   for (Instruction &I : *BB) {
3398     StoreInst *SI = dyn_cast<StoreInst>(&I);
3399     if (!SI)
3400       continue;
3401
3402     // Don't touch volatile stores.
3403     if (!SI->isSimple())
3404       continue;
3405
3406     // Check that the pointer points to scalars.
3407     Type *Ty = SI->getValueOperand()->getType();
3408     if (!isValidElementType(Ty))
3409       continue;
3410
3411     // Find the base pointer.
3412     Value *Ptr = GetUnderlyingObject(SI->getPointerOperand(), DL);
3413
3414     // Save the store locations.
3415     StoreRefs[Ptr].push_back(SI);
3416     count++;
3417   }
3418   return count;
3419 }
3420
3421 bool SLPVectorizer::tryToVectorizePair(Value *A, Value *B, BoUpSLP &R) {
3422   if (!A || !B)
3423     return false;
3424   Value *VL[] = { A, B };
3425   return tryToVectorizeList(VL, R, None, true);
3426 }
3427
3428 bool SLPVectorizer::tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R,
3429                                        ArrayRef<Value *> BuildVector,
3430                                        bool allowReorder) {
3431   if (VL.size() < 2)
3432     return false;
3433
3434   DEBUG(dbgs() << "SLP: Vectorizing a list of length = " << VL.size() << ".\n");
3435
3436   // Check that all of the parts are scalar instructions of the same type.
3437   Instruction *I0 = dyn_cast<Instruction>(VL[0]);
3438   if (!I0)
3439     return false;
3440
3441   unsigned Opcode0 = I0->getOpcode();
3442   const DataLayout &DL = I0->getModule()->getDataLayout();
3443
3444   Type *Ty0 = I0->getType();
3445   unsigned Sz = DL.getTypeSizeInBits(Ty0);
3446   // FIXME: Register size should be a parameter to this function, so we can
3447   // try different vectorization factors.
3448   unsigned VF = MinVecRegSize / Sz;
3449
3450   for (Value *V : VL) {
3451     Type *Ty = V->getType();
3452     if (!isValidElementType(Ty))
3453       return false;
3454     Instruction *Inst = dyn_cast<Instruction>(V);
3455     if (!Inst || Inst->getOpcode() != Opcode0)
3456       return false;
3457   }
3458
3459   bool Changed = false;
3460
3461   // Keep track of values that were deleted by vectorizing in the loop below.
3462   SmallVector<WeakVH, 8> TrackValues(VL.begin(), VL.end());
3463
3464   for (unsigned i = 0, e = VL.size(); i < e; ++i) {
3465     unsigned OpsWidth = 0;
3466
3467     if (i + VF > e)
3468       OpsWidth = e - i;
3469     else
3470       OpsWidth = VF;
3471
3472     if (!isPowerOf2_32(OpsWidth) || OpsWidth < 2)
3473       break;
3474
3475     // Check that a previous iteration of this loop did not delete the Value.
3476     if (hasValueBeenRAUWed(VL, TrackValues, i, OpsWidth))
3477       continue;
3478
3479     DEBUG(dbgs() << "SLP: Analyzing " << OpsWidth << " operations "
3480                  << "\n");
3481     ArrayRef<Value *> Ops = VL.slice(i, OpsWidth);
3482
3483     ArrayRef<Value *> BuildVectorSlice;
3484     if (!BuildVector.empty())
3485       BuildVectorSlice = BuildVector.slice(i, OpsWidth);
3486
3487     R.buildTree(Ops, BuildVectorSlice);
3488     // TODO: check if we can allow reordering also for other cases than
3489     // tryToVectorizePair()
3490     if (allowReorder && R.shouldReorder()) {
3491       assert(Ops.size() == 2);
3492       assert(BuildVectorSlice.empty());
3493       Value *ReorderedOps[] = { Ops[1], Ops[0] };
3494       R.buildTree(ReorderedOps, None);
3495     }
3496     int Cost = R.getTreeCost();
3497
3498     if (Cost < -SLPCostThreshold) {
3499       DEBUG(dbgs() << "SLP: Vectorizing list at cost:" << Cost << ".\n");
3500       Value *VectorizedRoot = R.vectorizeTree();
3501
3502       // Reconstruct the build vector by extracting the vectorized root. This
3503       // way we handle the case where some elements of the vector are undefined.
3504       //  (return (inserelt <4 xi32> (insertelt undef (opd0) 0) (opd1) 2))
3505       if (!BuildVectorSlice.empty()) {
3506         // The insert point is the last build vector instruction. The vectorized
3507         // root will precede it. This guarantees that we get an instruction. The
3508         // vectorized tree could have been constant folded.
3509         Instruction *InsertAfter = cast<Instruction>(BuildVectorSlice.back());
3510         unsigned VecIdx = 0;
3511         for (auto &V : BuildVectorSlice) {
3512           IRBuilder<true, NoFolder> Builder(
3513               InsertAfter->getParent(), ++BasicBlock::iterator(InsertAfter));
3514           InsertElementInst *IE = cast<InsertElementInst>(V);
3515           Instruction *Extract = cast<Instruction>(Builder.CreateExtractElement(
3516               VectorizedRoot, Builder.getInt32(VecIdx++)));
3517           IE->setOperand(1, Extract);
3518           IE->removeFromParent();
3519           IE->insertAfter(Extract);
3520           InsertAfter = IE;
3521         }
3522       }
3523       // Move to the next bundle.
3524       i += VF - 1;
3525       Changed = true;
3526     }
3527   }
3528
3529   return Changed;
3530 }
3531
3532 bool SLPVectorizer::tryToVectorize(BinaryOperator *V, BoUpSLP &R) {
3533   if (!V)
3534     return false;
3535
3536   // Try to vectorize V.
3537   if (tryToVectorizePair(V->getOperand(0), V->getOperand(1), R))
3538     return true;
3539
3540   BinaryOperator *A = dyn_cast<BinaryOperator>(V->getOperand(0));
3541   BinaryOperator *B = dyn_cast<BinaryOperator>(V->getOperand(1));
3542   // Try to skip B.
3543   if (B && B->hasOneUse()) {
3544     BinaryOperator *B0 = dyn_cast<BinaryOperator>(B->getOperand(0));
3545     BinaryOperator *B1 = dyn_cast<BinaryOperator>(B->getOperand(1));
3546     if (tryToVectorizePair(A, B0, R)) {
3547       return true;
3548     }
3549     if (tryToVectorizePair(A, B1, R)) {
3550       return true;
3551     }
3552   }
3553
3554   // Try to skip A.
3555   if (A && A->hasOneUse()) {
3556     BinaryOperator *A0 = dyn_cast<BinaryOperator>(A->getOperand(0));
3557     BinaryOperator *A1 = dyn_cast<BinaryOperator>(A->getOperand(1));
3558     if (tryToVectorizePair(A0, B, R)) {
3559       return true;
3560     }
3561     if (tryToVectorizePair(A1, B, R)) {
3562       return true;
3563     }
3564   }
3565   return 0;
3566 }
3567
3568 /// \brief Generate a shuffle mask to be used in a reduction tree.
3569 ///
3570 /// \param VecLen The length of the vector to be reduced.
3571 /// \param NumEltsToRdx The number of elements that should be reduced in the
3572 ///        vector.
3573 /// \param IsPairwise Whether the reduction is a pairwise or splitting
3574 ///        reduction. A pairwise reduction will generate a mask of 
3575 ///        <0,2,...> or <1,3,..> while a splitting reduction will generate
3576 ///        <2,3, undef,undef> for a vector of 4 and NumElts = 2.
3577 /// \param IsLeft True will generate a mask of even elements, odd otherwise.
3578 static Value *createRdxShuffleMask(unsigned VecLen, unsigned NumEltsToRdx,
3579                                    bool IsPairwise, bool IsLeft,
3580                                    IRBuilder<> &Builder) {
3581   assert((IsPairwise || !IsLeft) && "Don't support a <0,1,undef,...> mask");
3582
3583   SmallVector<Constant *, 32> ShuffleMask(
3584       VecLen, UndefValue::get(Builder.getInt32Ty()));
3585
3586   if (IsPairwise)
3587     // Build a mask of 0, 2, ... (left) or 1, 3, ... (right).
3588     for (unsigned i = 0; i != NumEltsToRdx; ++i)
3589       ShuffleMask[i] = Builder.getInt32(2 * i + !IsLeft);
3590   else
3591     // Move the upper half of the vector to the lower half.
3592     for (unsigned i = 0; i != NumEltsToRdx; ++i)
3593       ShuffleMask[i] = Builder.getInt32(NumEltsToRdx + i);
3594
3595   return ConstantVector::get(ShuffleMask);
3596 }
3597
3598
3599 /// Model horizontal reductions.
3600 ///
3601 /// A horizontal reduction is a tree of reduction operations (currently add and
3602 /// fadd) that has operations that can be put into a vector as its leaf.
3603 /// For example, this tree:
3604 ///
3605 /// mul mul mul mul
3606 ///  \  /    \  /
3607 ///   +       +
3608 ///    \     /
3609 ///       +
3610 /// This tree has "mul" as its reduced values and "+" as its reduction
3611 /// operations. A reduction might be feeding into a store or a binary operation
3612 /// feeding a phi.
3613 ///    ...
3614 ///    \  /
3615 ///     +
3616 ///     |
3617 ///  phi +=
3618 ///
3619 ///  Or:
3620 ///    ...
3621 ///    \  /
3622 ///     +
3623 ///     |
3624 ///   *p =
3625 ///
3626 class HorizontalReduction {
3627   SmallVector<Value *, 16> ReductionOps;
3628   SmallVector<Value *, 32> ReducedVals;
3629
3630   BinaryOperator *ReductionRoot;
3631   PHINode *ReductionPHI;
3632
3633   /// The opcode of the reduction.
3634   unsigned ReductionOpcode;
3635   /// The opcode of the values we perform a reduction on.
3636   unsigned ReducedValueOpcode;
3637   /// The width of one full horizontal reduction operation.
3638   unsigned ReduxWidth;
3639   /// Should we model this reduction as a pairwise reduction tree or a tree that
3640   /// splits the vector in halves and adds those halves.
3641   bool IsPairwiseReduction;
3642
3643 public:
3644   HorizontalReduction()
3645     : ReductionRoot(nullptr), ReductionPHI(nullptr), ReductionOpcode(0),
3646     ReducedValueOpcode(0), ReduxWidth(0), IsPairwiseReduction(false) {}
3647
3648   /// \brief Try to find a reduction tree.
3649   bool matchAssociativeReduction(PHINode *Phi, BinaryOperator *B) {
3650     assert((!Phi ||
3651             std::find(Phi->op_begin(), Phi->op_end(), B) != Phi->op_end()) &&
3652            "Thi phi needs to use the binary operator");
3653
3654     // We could have a initial reductions that is not an add.
3655     //  r *= v1 + v2 + v3 + v4
3656     // In such a case start looking for a tree rooted in the first '+'.
3657     if (Phi) {
3658       if (B->getOperand(0) == Phi) {
3659         Phi = nullptr;
3660         B = dyn_cast<BinaryOperator>(B->getOperand(1));
3661       } else if (B->getOperand(1) == Phi) {
3662         Phi = nullptr;
3663         B = dyn_cast<BinaryOperator>(B->getOperand(0));
3664       }
3665     }
3666
3667     if (!B)
3668       return false;
3669
3670     Type *Ty = B->getType();
3671     if (!isValidElementType(Ty))
3672       return false;
3673
3674     const DataLayout &DL = B->getModule()->getDataLayout();
3675     ReductionOpcode = B->getOpcode();
3676     ReducedValueOpcode = 0;
3677     // FIXME: Register size should be a parameter to this function, so we can
3678     // try different vectorization factors.
3679     ReduxWidth = MinVecRegSize / DL.getTypeSizeInBits(Ty);
3680     ReductionRoot = B;
3681     ReductionPHI = Phi;
3682
3683     if (ReduxWidth < 4)
3684       return false;
3685
3686     // We currently only support adds.
3687     if (ReductionOpcode != Instruction::Add &&
3688         ReductionOpcode != Instruction::FAdd)
3689       return false;
3690
3691     // Post order traverse the reduction tree starting at B. We only handle true
3692     // trees containing only binary operators.
3693     SmallVector<std::pair<BinaryOperator *, unsigned>, 32> Stack;
3694     Stack.push_back(std::make_pair(B, 0));
3695     while (!Stack.empty()) {
3696       BinaryOperator *TreeN = Stack.back().first;
3697       unsigned EdgeToVist = Stack.back().second++;
3698       bool IsReducedValue = TreeN->getOpcode() != ReductionOpcode;
3699
3700       // Only handle trees in the current basic block.
3701       if (TreeN->getParent() != B->getParent())
3702         return false;
3703
3704       // Each tree node needs to have one user except for the ultimate
3705       // reduction.
3706       if (!TreeN->hasOneUse() && TreeN != B)
3707         return false;
3708
3709       // Postorder vist.
3710       if (EdgeToVist == 2 || IsReducedValue) {
3711         if (IsReducedValue) {
3712           // Make sure that the opcodes of the operations that we are going to
3713           // reduce match.
3714           if (!ReducedValueOpcode)
3715             ReducedValueOpcode = TreeN->getOpcode();
3716           else if (ReducedValueOpcode != TreeN->getOpcode())
3717             return false;
3718           ReducedVals.push_back(TreeN);
3719         } else {
3720           // We need to be able to reassociate the adds.
3721           if (!TreeN->isAssociative())
3722             return false;
3723           ReductionOps.push_back(TreeN);
3724         }
3725         // Retract.
3726         Stack.pop_back();
3727         continue;
3728       }
3729
3730       // Visit left or right.
3731       Value *NextV = TreeN->getOperand(EdgeToVist);
3732       BinaryOperator *Next = dyn_cast<BinaryOperator>(NextV);
3733       if (Next)
3734         Stack.push_back(std::make_pair(Next, 0));
3735       else if (NextV != Phi)
3736         return false;
3737     }
3738     return true;
3739   }
3740
3741   /// \brief Attempt to vectorize the tree found by
3742   /// matchAssociativeReduction.
3743   bool tryToReduce(BoUpSLP &V, TargetTransformInfo *TTI) {
3744     if (ReducedVals.empty())
3745       return false;
3746
3747     unsigned NumReducedVals = ReducedVals.size();
3748     if (NumReducedVals < ReduxWidth)
3749       return false;
3750
3751     Value *VectorizedTree = nullptr;
3752     IRBuilder<> Builder(ReductionRoot);
3753     FastMathFlags Unsafe;
3754     Unsafe.setUnsafeAlgebra();
3755     Builder.SetFastMathFlags(Unsafe);
3756     unsigned i = 0;
3757
3758     for (; i < NumReducedVals - ReduxWidth + 1; i += ReduxWidth) {
3759       V.buildTree(makeArrayRef(&ReducedVals[i], ReduxWidth), ReductionOps);
3760
3761       // Estimate cost.
3762       int Cost = V.getTreeCost() + getReductionCost(TTI, ReducedVals[i]);
3763       if (Cost >= -SLPCostThreshold)
3764         break;
3765
3766       DEBUG(dbgs() << "SLP: Vectorizing horizontal reduction at cost:" << Cost
3767                    << ". (HorRdx)\n");
3768
3769       // Vectorize a tree.
3770       DebugLoc Loc = cast<Instruction>(ReducedVals[i])->getDebugLoc();
3771       Value *VectorizedRoot = V.vectorizeTree();
3772
3773       // Emit a reduction.
3774       Value *ReducedSubTree = emitReduction(VectorizedRoot, Builder);
3775       if (VectorizedTree) {
3776         Builder.SetCurrentDebugLocation(Loc);
3777         VectorizedTree = createBinOp(Builder, ReductionOpcode, VectorizedTree,
3778                                      ReducedSubTree, "bin.rdx");
3779       } else
3780         VectorizedTree = ReducedSubTree;
3781     }
3782
3783     if (VectorizedTree) {
3784       // Finish the reduction.
3785       for (; i < NumReducedVals; ++i) {
3786         Builder.SetCurrentDebugLocation(
3787           cast<Instruction>(ReducedVals[i])->getDebugLoc());
3788         VectorizedTree = createBinOp(Builder, ReductionOpcode, VectorizedTree,
3789                                      ReducedVals[i]);
3790       }
3791       // Update users.
3792       if (ReductionPHI) {
3793         assert(ReductionRoot && "Need a reduction operation");
3794         ReductionRoot->setOperand(0, VectorizedTree);
3795         ReductionRoot->setOperand(1, ReductionPHI);
3796       } else
3797         ReductionRoot->replaceAllUsesWith(VectorizedTree);
3798     }
3799     return VectorizedTree != nullptr;
3800   }
3801
3802 private:
3803
3804   /// \brief Calculate the cost of a reduction.
3805   int getReductionCost(TargetTransformInfo *TTI, Value *FirstReducedVal) {
3806     Type *ScalarTy = FirstReducedVal->getType();
3807     Type *VecTy = VectorType::get(ScalarTy, ReduxWidth);
3808
3809     int PairwiseRdxCost = TTI->getReductionCost(ReductionOpcode, VecTy, true);
3810     int SplittingRdxCost = TTI->getReductionCost(ReductionOpcode, VecTy, false);
3811
3812     IsPairwiseReduction = PairwiseRdxCost < SplittingRdxCost;
3813     int VecReduxCost = IsPairwiseReduction ? PairwiseRdxCost : SplittingRdxCost;
3814
3815     int ScalarReduxCost =
3816         ReduxWidth * TTI->getArithmeticInstrCost(ReductionOpcode, VecTy);
3817
3818     DEBUG(dbgs() << "SLP: Adding cost " << VecReduxCost - ScalarReduxCost
3819                  << " for reduction that starts with " << *FirstReducedVal
3820                  << " (It is a "
3821                  << (IsPairwiseReduction ? "pairwise" : "splitting")
3822                  << " reduction)\n");
3823
3824     return VecReduxCost - ScalarReduxCost;
3825   }
3826
3827   static Value *createBinOp(IRBuilder<> &Builder, unsigned Opcode, Value *L,
3828                             Value *R, const Twine &Name = "") {
3829     if (Opcode == Instruction::FAdd)
3830       return Builder.CreateFAdd(L, R, Name);
3831     return Builder.CreateBinOp((Instruction::BinaryOps)Opcode, L, R, Name);
3832   }
3833
3834   /// \brief Emit a horizontal reduction of the vectorized value.
3835   Value *emitReduction(Value *VectorizedValue, IRBuilder<> &Builder) {
3836     assert(VectorizedValue && "Need to have a vectorized tree node");
3837     assert(isPowerOf2_32(ReduxWidth) &&
3838            "We only handle power-of-two reductions for now");
3839
3840     Value *TmpVec = VectorizedValue;
3841     for (unsigned i = ReduxWidth / 2; i != 0; i >>= 1) {
3842       if (IsPairwiseReduction) {
3843         Value *LeftMask =
3844           createRdxShuffleMask(ReduxWidth, i, true, true, Builder);
3845         Value *RightMask =
3846           createRdxShuffleMask(ReduxWidth, i, true, false, Builder);
3847
3848         Value *LeftShuf = Builder.CreateShuffleVector(
3849           TmpVec, UndefValue::get(TmpVec->getType()), LeftMask, "rdx.shuf.l");
3850         Value *RightShuf = Builder.CreateShuffleVector(
3851           TmpVec, UndefValue::get(TmpVec->getType()), (RightMask),
3852           "rdx.shuf.r");
3853         TmpVec = createBinOp(Builder, ReductionOpcode, LeftShuf, RightShuf,
3854                              "bin.rdx");
3855       } else {
3856         Value *UpperHalf =
3857           createRdxShuffleMask(ReduxWidth, i, false, false, Builder);
3858         Value *Shuf = Builder.CreateShuffleVector(
3859           TmpVec, UndefValue::get(TmpVec->getType()), UpperHalf, "rdx.shuf");
3860         TmpVec = createBinOp(Builder, ReductionOpcode, TmpVec, Shuf, "bin.rdx");
3861       }
3862     }
3863
3864     // The result is in the first element of the vector.
3865     return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
3866   }
3867 };
3868
3869 /// \brief Recognize construction of vectors like
3870 ///  %ra = insertelement <4 x float> undef, float %s0, i32 0
3871 ///  %rb = insertelement <4 x float> %ra, float %s1, i32 1
3872 ///  %rc = insertelement <4 x float> %rb, float %s2, i32 2
3873 ///  %rd = insertelement <4 x float> %rc, float %s3, i32 3
3874 ///
3875 /// Returns true if it matches
3876 ///
3877 static bool findBuildVector(InsertElementInst *FirstInsertElem,
3878                             SmallVectorImpl<Value *> &BuildVector,
3879                             SmallVectorImpl<Value *> &BuildVectorOpds) {
3880   if (!isa<UndefValue>(FirstInsertElem->getOperand(0)))
3881     return false;
3882
3883   InsertElementInst *IE = FirstInsertElem;
3884   while (true) {
3885     BuildVector.push_back(IE);
3886     BuildVectorOpds.push_back(IE->getOperand(1));
3887
3888     if (IE->use_empty())
3889       return false;
3890
3891     InsertElementInst *NextUse = dyn_cast<InsertElementInst>(IE->user_back());
3892     if (!NextUse)
3893       return true;
3894
3895     // If this isn't the final use, make sure the next insertelement is the only
3896     // use. It's OK if the final constructed vector is used multiple times
3897     if (!IE->hasOneUse())
3898       return false;
3899
3900     IE = NextUse;
3901   }
3902
3903   return false;
3904 }
3905
3906 static bool PhiTypeSorterFunc(Value *V, Value *V2) {
3907   return V->getType() < V2->getType();
3908 }
3909
3910 bool SLPVectorizer::vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R) {
3911   bool Changed = false;
3912   SmallVector<Value *, 4> Incoming;
3913   SmallSet<Value *, 16> VisitedInstrs;
3914
3915   bool HaveVectorizedPhiNodes = true;
3916   while (HaveVectorizedPhiNodes) {
3917     HaveVectorizedPhiNodes = false;
3918
3919     // Collect the incoming values from the PHIs.
3920     Incoming.clear();
3921     for (BasicBlock::iterator instr = BB->begin(), ie = BB->end(); instr != ie;
3922          ++instr) {
3923       PHINode *P = dyn_cast<PHINode>(instr);
3924       if (!P)
3925         break;
3926
3927       if (!VisitedInstrs.count(P))
3928         Incoming.push_back(P);
3929     }
3930
3931     // Sort by type.
3932     std::stable_sort(Incoming.begin(), Incoming.end(), PhiTypeSorterFunc);
3933
3934     // Try to vectorize elements base on their type.
3935     for (SmallVector<Value *, 4>::iterator IncIt = Incoming.begin(),
3936                                            E = Incoming.end();
3937          IncIt != E;) {
3938
3939       // Look for the next elements with the same type.
3940       SmallVector<Value *, 4>::iterator SameTypeIt = IncIt;
3941       while (SameTypeIt != E &&
3942              (*SameTypeIt)->getType() == (*IncIt)->getType()) {
3943         VisitedInstrs.insert(*SameTypeIt);
3944         ++SameTypeIt;
3945       }
3946
3947       // Try to vectorize them.
3948       unsigned NumElts = (SameTypeIt - IncIt);
3949       DEBUG(errs() << "SLP: Trying to vectorize starting at PHIs (" << NumElts << ")\n");
3950       if (NumElts > 1 && tryToVectorizeList(makeArrayRef(IncIt, NumElts), R)) {
3951         // Success start over because instructions might have been changed.
3952         HaveVectorizedPhiNodes = true;
3953         Changed = true;
3954         break;
3955       }
3956
3957       // Start over at the next instruction of a different type (or the end).
3958       IncIt = SameTypeIt;
3959     }
3960   }
3961
3962   VisitedInstrs.clear();
3963
3964   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; it++) {
3965     // We may go through BB multiple times so skip the one we have checked.
3966     if (!VisitedInstrs.insert(&*it).second)
3967       continue;
3968
3969     if (isa<DbgInfoIntrinsic>(it))
3970       continue;
3971
3972     // Try to vectorize reductions that use PHINodes.
3973     if (PHINode *P = dyn_cast<PHINode>(it)) {
3974       // Check that the PHI is a reduction PHI.
3975       if (P->getNumIncomingValues() != 2)
3976         return Changed;
3977       Value *Rdx =
3978           (P->getIncomingBlock(0) == BB
3979                ? (P->getIncomingValue(0))
3980                : (P->getIncomingBlock(1) == BB ? P->getIncomingValue(1)
3981                                                : nullptr));
3982       // Check if this is a Binary Operator.
3983       BinaryOperator *BI = dyn_cast_or_null<BinaryOperator>(Rdx);
3984       if (!BI)
3985         continue;
3986
3987       // Try to match and vectorize a horizontal reduction.
3988       HorizontalReduction HorRdx;
3989       if (ShouldVectorizeHor && HorRdx.matchAssociativeReduction(P, BI) &&
3990           HorRdx.tryToReduce(R, TTI)) {
3991         Changed = true;
3992         it = BB->begin();
3993         e = BB->end();
3994         continue;
3995       }
3996
3997      Value *Inst = BI->getOperand(0);
3998       if (Inst == P)
3999         Inst = BI->getOperand(1);
4000
4001       if (tryToVectorize(dyn_cast<BinaryOperator>(Inst), R)) {
4002         // We would like to start over since some instructions are deleted
4003         // and the iterator may become invalid value.
4004         Changed = true;
4005         it = BB->begin();
4006         e = BB->end();
4007         continue;
4008       }
4009
4010       continue;
4011     }
4012
4013     // Try to vectorize horizontal reductions feeding into a store.
4014     if (ShouldStartVectorizeHorAtStore)
4015       if (StoreInst *SI = dyn_cast<StoreInst>(it))
4016         if (BinaryOperator *BinOp =
4017                 dyn_cast<BinaryOperator>(SI->getValueOperand())) {
4018           HorizontalReduction HorRdx;
4019           if (((HorRdx.matchAssociativeReduction(nullptr, BinOp) &&
4020                 HorRdx.tryToReduce(R, TTI)) ||
4021                tryToVectorize(BinOp, R))) {
4022             Changed = true;
4023             it = BB->begin();
4024             e = BB->end();
4025             continue;
4026           }
4027         }
4028
4029     // Try to vectorize horizontal reductions feeding into a return.
4030     if (ReturnInst *RI = dyn_cast<ReturnInst>(it))
4031       if (RI->getNumOperands() != 0)
4032         if (BinaryOperator *BinOp =
4033                 dyn_cast<BinaryOperator>(RI->getOperand(0))) {
4034           DEBUG(dbgs() << "SLP: Found a return to vectorize.\n");
4035           if (tryToVectorizePair(BinOp->getOperand(0),
4036                                  BinOp->getOperand(1), R)) {
4037             Changed = true;
4038             it = BB->begin();
4039             e = BB->end();
4040             continue;
4041           }
4042         }
4043
4044     // Try to vectorize trees that start at compare instructions.
4045     if (CmpInst *CI = dyn_cast<CmpInst>(it)) {
4046       if (tryToVectorizePair(CI->getOperand(0), CI->getOperand(1), R)) {
4047         Changed = true;
4048         // We would like to start over since some instructions are deleted
4049         // and the iterator may become invalid value.
4050         it = BB->begin();
4051         e = BB->end();
4052         continue;
4053       }
4054
4055       for (int i = 0; i < 2; ++i) {
4056         if (BinaryOperator *BI = dyn_cast<BinaryOperator>(CI->getOperand(i))) {
4057           if (tryToVectorizePair(BI->getOperand(0), BI->getOperand(1), R)) {
4058             Changed = true;
4059             // We would like to start over since some instructions are deleted
4060             // and the iterator may become invalid value.
4061             it = BB->begin();
4062             e = BB->end();
4063             break;
4064           }
4065         }
4066       }
4067       continue;
4068     }
4069
4070     // Try to vectorize trees that start at insertelement instructions.
4071     if (InsertElementInst *FirstInsertElem = dyn_cast<InsertElementInst>(it)) {
4072       SmallVector<Value *, 16> BuildVector;
4073       SmallVector<Value *, 16> BuildVectorOpds;
4074       if (!findBuildVector(FirstInsertElem, BuildVector, BuildVectorOpds))
4075         continue;
4076
4077       // Vectorize starting with the build vector operands ignoring the
4078       // BuildVector instructions for the purpose of scheduling and user
4079       // extraction.
4080       if (tryToVectorizeList(BuildVectorOpds, R, BuildVector)) {
4081         Changed = true;
4082         it = BB->begin();
4083         e = BB->end();
4084       }
4085
4086       continue;
4087     }
4088   }
4089
4090   return Changed;
4091 }
4092
4093 bool SLPVectorizer::vectorizeStoreChains(BoUpSLP &R) {
4094   bool Changed = false;
4095   // Attempt to sort and vectorize each of the store-groups.
4096   for (StoreListMap::iterator it = StoreRefs.begin(), e = StoreRefs.end();
4097        it != e; ++it) {
4098     if (it->second.size() < 2)
4099       continue;
4100
4101     DEBUG(dbgs() << "SLP: Analyzing a store chain of length "
4102           << it->second.size() << ".\n");
4103
4104     // Process the stores in chunks of 16.
4105     // TODO: The limit of 16 inhibits greater vectorization factors.
4106     //       For example, AVX2 supports v32i8. Increasing this limit, however,
4107     //       may cause a significant compile-time increase.
4108     for (unsigned CI = 0, CE = it->second.size(); CI < CE; CI+=16) {
4109       unsigned Len = std::min<unsigned>(CE - CI, 16);
4110       Changed |= vectorizeStores(makeArrayRef(&it->second[CI], Len),
4111                                  -SLPCostThreshold, R);
4112     }
4113   }
4114   return Changed;
4115 }
4116
4117 } // end anonymous namespace
4118
4119 char SLPVectorizer::ID = 0;
4120 static const char lv_name[] = "SLP Vectorizer";
4121 INITIALIZE_PASS_BEGIN(SLPVectorizer, SV_NAME, lv_name, false, false)
4122 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
4123 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
4124 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
4125 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
4126 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
4127 INITIALIZE_PASS_END(SLPVectorizer, SV_NAME, lv_name, false, false)
4128
4129 namespace llvm {
4130 Pass *createSLPVectorizerPass() { return new SLPVectorizer(); }
4131 }