SLPVectorizer: AllSameOpcode* starts "true" only for instructions
[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
1947 // Return true if I should be commuted before adding it's left and right
1948 // operands to the arrays Left and Right.
1949 //
1950 // The vectorizer is trying to either have all elements one side being
1951 // instruction with the same opcode to enable further vectorization, or having
1952 // a splat to lower the vectorizing cost.
1953 static bool shouldReorderOperands(int i, Instruction &I,
1954                                   SmallVectorImpl<Value *> &Left,
1955                                   SmallVectorImpl<Value *> &Right) {
1956   Value *VLeft = I.getOperand(0);
1957   Value *VRight = I.getOperand(1);
1958   Instruction *ILeft = dyn_cast<Instruction>(VLeft);
1959   Instruction *IRight = dyn_cast<Instruction>(VRight);
1960
1961   // Sort two opcodes. In the code below we try to preserve the ability to use
1962   // broadcast of values instead of individual inserts.
1963   // vl1 = load
1964   // vl2 = phi
1965   // vr1 = load
1966   // vr2 = vr2
1967   //    = vl1 x vr1
1968   //    = vl2 x vr2
1969   // If we just sorted according to opcode we would leave the first line in
1970   // tact but we would swap vl2 with vr2 because opcode(phi) > opcode(load).
1971   //    = vl1 x vr1
1972   //    = vr2 x vl2
1973   // Because vr2 and vr1 are from the same load we loose the opportunity of a
1974   // broadcast for the packed right side in the backend: we have [vr1, vl2]
1975   // instead of [vr1, vr2=vr1].
1976   if (ILeft && IRight) {
1977     if (ILeft->getOpcode() > IRight->getOpcode() &&
1978                Right[i - 1] != IRight) {
1979       // Try not to destroy a broad cast for no apparent benefit.
1980       return true;
1981     } else if (ILeft->getOpcode() == IRight->getOpcode() &&
1982                Right[i - 1] == ILeft) {
1983       // Try preserve broadcasts.
1984       return true;
1985     } else if (ILeft->getOpcode() == IRight->getOpcode() &&
1986                Left[i - 1] == IRight) {
1987       // Try preserve broadcasts.
1988       return true;
1989     }
1990     return false;
1991   }
1992   // One opcode, put the instruction on the right.
1993   if (ILeft) {
1994     return true;
1995   }
1996   return false;
1997 }
1998
1999 void BoUpSLP::reorderInputsAccordingToOpcode(ArrayRef<Value *> VL,
2000                                              SmallVectorImpl<Value *> &Left,
2001                                              SmallVectorImpl<Value *> &Right) {
2002
2003   SmallVector<Value *, 16> OrigLeft, OrigRight;
2004
2005   if (VL.size()) {
2006     // Peel the first iteration out of the loop since there's nothing
2007     // interesting to do anyway and it simplifies the checks
2008     auto VLeft = cast<Instruction>(VL[0])->getOperand(0);
2009     auto VRight = cast<Instruction>(VL[0])->getOperand(1);
2010     OrigLeft.push_back(VLeft);
2011     OrigRight.push_back(VRight);
2012     if (!isa<Instruction>(VRight) && isa<Instruction>(VLeft))
2013       // Favor having instruction to the right. FIXME: why?
2014       std::swap(VLeft, VRight);
2015     Left.push_back(VLeft);
2016     Right.push_back(VRight);
2017   }
2018
2019   // Keep track if we have instructions with all the same opcode on one side.
2020   bool AllSameOpcodeLeft = isa<Instruction>(Left[0]);
2021   bool AllSameOpcodeRight = isa<Instruction>(Right[0]);
2022
2023   for (unsigned i = 1, e = VL.size(); i != e; ++i) {
2024     Instruction *I = cast<Instruction>(VL[i]);
2025
2026     Value *VLeft = I->getOperand(0);
2027     Value *VRight = I->getOperand(1);
2028     OrigLeft.push_back(VLeft);
2029     OrigRight.push_back(VRight);
2030     Instruction *ILeft = dyn_cast<Instruction>(VLeft);
2031     Instruction *IRight = dyn_cast<Instruction>(VRight);
2032
2033     // Check whether all operands on one side have the same opcode. In this case
2034     // we want to preserve the original order and not make things worse by
2035     // reordering.
2036     if (AllSameOpcodeLeft && ILeft) {
2037       if (Instruction *PLeft = dyn_cast<Instruction>(OrigLeft[i - 1])) {
2038         if (PLeft->getOpcode() != ILeft->getOpcode())
2039           AllSameOpcodeLeft = false;
2040       } else
2041         AllSameOpcodeLeft = false;
2042     }
2043     if (AllSameOpcodeRight && IRight) {
2044       if (Instruction *PRight = dyn_cast<Instruction>(OrigRight[i - 1])) {
2045         if (PRight->getOpcode() != IRight->getOpcode())
2046           AllSameOpcodeRight = false;
2047       } else
2048         AllSameOpcodeRight = false;
2049     }
2050
2051
2052     // Commute to favor either a splat or maximizing having the same opcodes on
2053     // one side.
2054     if (shouldReorderOperands(i, *I, Left, Right)) {
2055       Left.push_back(I->getOperand(1));
2056       Right.push_back(I->getOperand(0));
2057     } else {
2058       Left.push_back(I->getOperand(0));
2059       Right.push_back(I->getOperand(1));
2060     }
2061   }
2062
2063   bool LeftBroadcast = isSplat(Left);
2064   bool RightBroadcast = isSplat(Right);
2065
2066   // If operands end up being broadcast return this operand order.
2067   if (LeftBroadcast || RightBroadcast)
2068     return;
2069
2070   // Don't reorder if the operands where good to begin.
2071   if (AllSameOpcodeRight || AllSameOpcodeLeft) {
2072     Left = OrigLeft;
2073     Right = OrigRight;
2074   }
2075
2076   const DataLayout &DL = F->getParent()->getDataLayout();
2077
2078   // Finally check if we can get longer vectorizable chain by reordering
2079   // without breaking the good operand order detected above.
2080   // E.g. If we have something like-
2081   // load a[0]  load b[0]
2082   // load b[1]  load a[1]
2083   // load a[2]  load b[2]
2084   // load a[3]  load b[3]
2085   // Reordering the second load b[1]  load a[1] would allow us to vectorize
2086   // this code and we still retain AllSameOpcode property.
2087   // FIXME: This load reordering might break AllSameOpcode in some rare cases
2088   // such as-
2089   // add a[0],c[0]  load b[0]
2090   // add a[1],c[2]  load b[1]
2091   // b[2]           load b[2]
2092   // add a[3],c[3]  load b[3]
2093   for (unsigned j = 0; j < VL.size() - 1; ++j) {
2094     if (LoadInst *L = dyn_cast<LoadInst>(Left[j])) {
2095       if (LoadInst *L1 = dyn_cast<LoadInst>(Right[j + 1])) {
2096         if (isConsecutiveAccess(L, L1, DL)) {
2097           std::swap(Left[j + 1], Right[j + 1]);
2098           continue;
2099         }
2100       }
2101     }
2102     if (LoadInst *L = dyn_cast<LoadInst>(Right[j])) {
2103       if (LoadInst *L1 = dyn_cast<LoadInst>(Left[j + 1])) {
2104         if (isConsecutiveAccess(L, L1, DL)) {
2105           std::swap(Left[j + 1], Right[j + 1]);
2106           continue;
2107         }
2108       }
2109     }
2110     // else unchanged
2111   }
2112 }
2113
2114 void BoUpSLP::setInsertPointAfterBundle(ArrayRef<Value *> VL) {
2115   Instruction *VL0 = cast<Instruction>(VL[0]);
2116   BasicBlock::iterator NextInst(VL0);
2117   ++NextInst;
2118   Builder.SetInsertPoint(VL0->getParent(), NextInst);
2119   Builder.SetCurrentDebugLocation(VL0->getDebugLoc());
2120 }
2121
2122 Value *BoUpSLP::Gather(ArrayRef<Value *> VL, VectorType *Ty) {
2123   Value *Vec = UndefValue::get(Ty);
2124   // Generate the 'InsertElement' instruction.
2125   for (unsigned i = 0; i < Ty->getNumElements(); ++i) {
2126     Vec = Builder.CreateInsertElement(Vec, VL[i], Builder.getInt32(i));
2127     if (Instruction *Insrt = dyn_cast<Instruction>(Vec)) {
2128       GatherSeq.insert(Insrt);
2129       CSEBlocks.insert(Insrt->getParent());
2130
2131       // Add to our 'need-to-extract' list.
2132       if (ScalarToTreeEntry.count(VL[i])) {
2133         int Idx = ScalarToTreeEntry[VL[i]];
2134         TreeEntry *E = &VectorizableTree[Idx];
2135         // Find which lane we need to extract.
2136         int FoundLane = -1;
2137         for (unsigned Lane = 0, LE = VL.size(); Lane != LE; ++Lane) {
2138           // Is this the lane of the scalar that we are looking for ?
2139           if (E->Scalars[Lane] == VL[i]) {
2140             FoundLane = Lane;
2141             break;
2142           }
2143         }
2144         assert(FoundLane >= 0 && "Could not find the correct lane");
2145         ExternalUses.push_back(ExternalUser(VL[i], Insrt, FoundLane));
2146       }
2147     }
2148   }
2149
2150   return Vec;
2151 }
2152
2153 Value *BoUpSLP::alreadyVectorized(ArrayRef<Value *> VL) const {
2154   SmallDenseMap<Value*, int>::const_iterator Entry
2155     = ScalarToTreeEntry.find(VL[0]);
2156   if (Entry != ScalarToTreeEntry.end()) {
2157     int Idx = Entry->second;
2158     const TreeEntry *En = &VectorizableTree[Idx];
2159     if (En->isSame(VL) && En->VectorizedValue)
2160       return En->VectorizedValue;
2161   }
2162   return nullptr;
2163 }
2164
2165 Value *BoUpSLP::vectorizeTree(ArrayRef<Value *> VL) {
2166   if (ScalarToTreeEntry.count(VL[0])) {
2167     int Idx = ScalarToTreeEntry[VL[0]];
2168     TreeEntry *E = &VectorizableTree[Idx];
2169     if (E->isSame(VL))
2170       return vectorizeTree(E);
2171   }
2172
2173   Type *ScalarTy = VL[0]->getType();
2174   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
2175     ScalarTy = SI->getValueOperand()->getType();
2176   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
2177
2178   return Gather(VL, VecTy);
2179 }
2180
2181 Value *BoUpSLP::vectorizeTree(TreeEntry *E) {
2182   IRBuilder<>::InsertPointGuard Guard(Builder);
2183
2184   if (E->VectorizedValue) {
2185     DEBUG(dbgs() << "SLP: Diamond merged for " << *E->Scalars[0] << ".\n");
2186     return E->VectorizedValue;
2187   }
2188
2189   Instruction *VL0 = cast<Instruction>(E->Scalars[0]);
2190   Type *ScalarTy = VL0->getType();
2191   if (StoreInst *SI = dyn_cast<StoreInst>(VL0))
2192     ScalarTy = SI->getValueOperand()->getType();
2193   VectorType *VecTy = VectorType::get(ScalarTy, E->Scalars.size());
2194
2195   if (E->NeedToGather) {
2196     setInsertPointAfterBundle(E->Scalars);
2197     return Gather(E->Scalars, VecTy);
2198   }
2199
2200   const DataLayout &DL = F->getParent()->getDataLayout();
2201   unsigned Opcode = getSameOpcode(E->Scalars);
2202
2203   switch (Opcode) {
2204     case Instruction::PHI: {
2205       PHINode *PH = dyn_cast<PHINode>(VL0);
2206       Builder.SetInsertPoint(PH->getParent()->getFirstNonPHI());
2207       Builder.SetCurrentDebugLocation(PH->getDebugLoc());
2208       PHINode *NewPhi = Builder.CreatePHI(VecTy, PH->getNumIncomingValues());
2209       E->VectorizedValue = NewPhi;
2210
2211       // PHINodes may have multiple entries from the same block. We want to
2212       // visit every block once.
2213       SmallSet<BasicBlock*, 4> VisitedBBs;
2214
2215       for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
2216         ValueList Operands;
2217         BasicBlock *IBB = PH->getIncomingBlock(i);
2218
2219         if (!VisitedBBs.insert(IBB).second) {
2220           NewPhi->addIncoming(NewPhi->getIncomingValueForBlock(IBB), IBB);
2221           continue;
2222         }
2223
2224         // Prepare the operand vector.
2225         for (Value *V : E->Scalars)
2226           Operands.push_back(cast<PHINode>(V)->getIncomingValueForBlock(IBB));
2227
2228         Builder.SetInsertPoint(IBB->getTerminator());
2229         Builder.SetCurrentDebugLocation(PH->getDebugLoc());
2230         Value *Vec = vectorizeTree(Operands);
2231         NewPhi->addIncoming(Vec, IBB);
2232       }
2233
2234       assert(NewPhi->getNumIncomingValues() == PH->getNumIncomingValues() &&
2235              "Invalid number of incoming values");
2236       return NewPhi;
2237     }
2238
2239     case Instruction::ExtractElement: {
2240       if (CanReuseExtract(E->Scalars)) {
2241         Value *V = VL0->getOperand(0);
2242         E->VectorizedValue = V;
2243         return V;
2244       }
2245       return Gather(E->Scalars, VecTy);
2246     }
2247     case Instruction::ZExt:
2248     case Instruction::SExt:
2249     case Instruction::FPToUI:
2250     case Instruction::FPToSI:
2251     case Instruction::FPExt:
2252     case Instruction::PtrToInt:
2253     case Instruction::IntToPtr:
2254     case Instruction::SIToFP:
2255     case Instruction::UIToFP:
2256     case Instruction::Trunc:
2257     case Instruction::FPTrunc:
2258     case Instruction::BitCast: {
2259       ValueList INVL;
2260       for (Value *V : E->Scalars)
2261         INVL.push_back(cast<Instruction>(V)->getOperand(0));
2262
2263       setInsertPointAfterBundle(E->Scalars);
2264
2265       Value *InVec = vectorizeTree(INVL);
2266
2267       if (Value *V = alreadyVectorized(E->Scalars))
2268         return V;
2269
2270       CastInst *CI = dyn_cast<CastInst>(VL0);
2271       Value *V = Builder.CreateCast(CI->getOpcode(), InVec, VecTy);
2272       E->VectorizedValue = V;
2273       ++NumVectorInstructions;
2274       return V;
2275     }
2276     case Instruction::FCmp:
2277     case Instruction::ICmp: {
2278       ValueList LHSV, RHSV;
2279       for (Value *V : E->Scalars) {
2280         LHSV.push_back(cast<Instruction>(V)->getOperand(0));
2281         RHSV.push_back(cast<Instruction>(V)->getOperand(1));
2282       }
2283
2284       setInsertPointAfterBundle(E->Scalars);
2285
2286       Value *L = vectorizeTree(LHSV);
2287       Value *R = vectorizeTree(RHSV);
2288
2289       if (Value *V = alreadyVectorized(E->Scalars))
2290         return V;
2291
2292       CmpInst::Predicate P0 = cast<CmpInst>(VL0)->getPredicate();
2293       Value *V;
2294       if (Opcode == Instruction::FCmp)
2295         V = Builder.CreateFCmp(P0, L, R);
2296       else
2297         V = Builder.CreateICmp(P0, L, R);
2298
2299       E->VectorizedValue = V;
2300       ++NumVectorInstructions;
2301       return V;
2302     }
2303     case Instruction::Select: {
2304       ValueList TrueVec, FalseVec, CondVec;
2305       for (Value *V : E->Scalars) {
2306         CondVec.push_back(cast<Instruction>(V)->getOperand(0));
2307         TrueVec.push_back(cast<Instruction>(V)->getOperand(1));
2308         FalseVec.push_back(cast<Instruction>(V)->getOperand(2));
2309       }
2310
2311       setInsertPointAfterBundle(E->Scalars);
2312
2313       Value *Cond = vectorizeTree(CondVec);
2314       Value *True = vectorizeTree(TrueVec);
2315       Value *False = vectorizeTree(FalseVec);
2316
2317       if (Value *V = alreadyVectorized(E->Scalars))
2318         return V;
2319
2320       Value *V = Builder.CreateSelect(Cond, True, False);
2321       E->VectorizedValue = V;
2322       ++NumVectorInstructions;
2323       return V;
2324     }
2325     case Instruction::Add:
2326     case Instruction::FAdd:
2327     case Instruction::Sub:
2328     case Instruction::FSub:
2329     case Instruction::Mul:
2330     case Instruction::FMul:
2331     case Instruction::UDiv:
2332     case Instruction::SDiv:
2333     case Instruction::FDiv:
2334     case Instruction::URem:
2335     case Instruction::SRem:
2336     case Instruction::FRem:
2337     case Instruction::Shl:
2338     case Instruction::LShr:
2339     case Instruction::AShr:
2340     case Instruction::And:
2341     case Instruction::Or:
2342     case Instruction::Xor: {
2343       ValueList LHSVL, RHSVL;
2344       if (isa<BinaryOperator>(VL0) && VL0->isCommutative())
2345         reorderInputsAccordingToOpcode(E->Scalars, LHSVL, RHSVL);
2346       else
2347         for (Value *V : E->Scalars) {
2348           LHSVL.push_back(cast<Instruction>(V)->getOperand(0));
2349           RHSVL.push_back(cast<Instruction>(V)->getOperand(1));
2350         }
2351
2352       setInsertPointAfterBundle(E->Scalars);
2353
2354       Value *LHS = vectorizeTree(LHSVL);
2355       Value *RHS = vectorizeTree(RHSVL);
2356
2357       if (LHS == RHS && isa<Instruction>(LHS)) {
2358         assert((VL0->getOperand(0) == VL0->getOperand(1)) && "Invalid order");
2359       }
2360
2361       if (Value *V = alreadyVectorized(E->Scalars))
2362         return V;
2363
2364       BinaryOperator *BinOp = cast<BinaryOperator>(VL0);
2365       Value *V = Builder.CreateBinOp(BinOp->getOpcode(), LHS, RHS);
2366       E->VectorizedValue = V;
2367       propagateIRFlags(E->VectorizedValue, E->Scalars);
2368       ++NumVectorInstructions;
2369
2370       if (Instruction *I = dyn_cast<Instruction>(V))
2371         return propagateMetadata(I, E->Scalars);
2372
2373       return V;
2374     }
2375     case Instruction::Load: {
2376       // Loads are inserted at the head of the tree because we don't want to
2377       // sink them all the way down past store instructions.
2378       setInsertPointAfterBundle(E->Scalars);
2379
2380       LoadInst *LI = cast<LoadInst>(VL0);
2381       Type *ScalarLoadTy = LI->getType();
2382       unsigned AS = LI->getPointerAddressSpace();
2383
2384       Value *VecPtr = Builder.CreateBitCast(LI->getPointerOperand(),
2385                                             VecTy->getPointerTo(AS));
2386
2387       // The pointer operand uses an in-tree scalar so we add the new BitCast to
2388       // ExternalUses list to make sure that an extract will be generated in the
2389       // future.
2390       if (ScalarToTreeEntry.count(LI->getPointerOperand()))
2391         ExternalUses.push_back(
2392             ExternalUser(LI->getPointerOperand(), cast<User>(VecPtr), 0));
2393
2394       unsigned Alignment = LI->getAlignment();
2395       LI = Builder.CreateLoad(VecPtr);
2396       if (!Alignment) {
2397         Alignment = DL.getABITypeAlignment(ScalarLoadTy);
2398       }
2399       LI->setAlignment(Alignment);
2400       E->VectorizedValue = LI;
2401       ++NumVectorInstructions;
2402       return propagateMetadata(LI, E->Scalars);
2403     }
2404     case Instruction::Store: {
2405       StoreInst *SI = cast<StoreInst>(VL0);
2406       unsigned Alignment = SI->getAlignment();
2407       unsigned AS = SI->getPointerAddressSpace();
2408
2409       ValueList ValueOp;
2410       for (Value *V : E->Scalars)
2411         ValueOp.push_back(cast<StoreInst>(V)->getValueOperand());
2412
2413       setInsertPointAfterBundle(E->Scalars);
2414
2415       Value *VecValue = vectorizeTree(ValueOp);
2416       Value *VecPtr = Builder.CreateBitCast(SI->getPointerOperand(),
2417                                             VecTy->getPointerTo(AS));
2418       StoreInst *S = Builder.CreateStore(VecValue, VecPtr);
2419
2420       // The pointer operand uses an in-tree scalar so we add the new BitCast to
2421       // ExternalUses list to make sure that an extract will be generated in the
2422       // future.
2423       if (ScalarToTreeEntry.count(SI->getPointerOperand()))
2424         ExternalUses.push_back(
2425             ExternalUser(SI->getPointerOperand(), cast<User>(VecPtr), 0));
2426
2427       if (!Alignment) {
2428         Alignment = DL.getABITypeAlignment(SI->getValueOperand()->getType());
2429       }
2430       S->setAlignment(Alignment);
2431       E->VectorizedValue = S;
2432       ++NumVectorInstructions;
2433       return propagateMetadata(S, E->Scalars);
2434     }
2435     case Instruction::GetElementPtr: {
2436       setInsertPointAfterBundle(E->Scalars);
2437
2438       ValueList Op0VL;
2439       for (Value *V : E->Scalars)
2440         Op0VL.push_back(cast<GetElementPtrInst>(V)->getOperand(0));
2441
2442       Value *Op0 = vectorizeTree(Op0VL);
2443
2444       std::vector<Value *> OpVecs;
2445       for (int j = 1, e = cast<GetElementPtrInst>(VL0)->getNumOperands(); j < e;
2446            ++j) {
2447         ValueList OpVL;
2448         for (Value *V : E->Scalars)
2449           OpVL.push_back(cast<GetElementPtrInst>(V)->getOperand(j));
2450
2451         Value *OpVec = vectorizeTree(OpVL);
2452         OpVecs.push_back(OpVec);
2453       }
2454
2455       Value *V = Builder.CreateGEP(
2456           cast<GetElementPtrInst>(VL0)->getSourceElementType(), Op0, OpVecs);
2457       E->VectorizedValue = V;
2458       ++NumVectorInstructions;
2459
2460       if (Instruction *I = dyn_cast<Instruction>(V))
2461         return propagateMetadata(I, E->Scalars);
2462
2463       return V;
2464     }
2465     case Instruction::Call: {
2466       CallInst *CI = cast<CallInst>(VL0);
2467       setInsertPointAfterBundle(E->Scalars);
2468       Function *FI;
2469       Intrinsic::ID IID  = Intrinsic::not_intrinsic;
2470       Value *ScalarArg = nullptr;
2471       if (CI && (FI = CI->getCalledFunction())) {
2472         IID = FI->getIntrinsicID();
2473       }
2474       std::vector<Value *> OpVecs;
2475       for (int j = 0, e = CI->getNumArgOperands(); j < e; ++j) {
2476         ValueList OpVL;
2477         // ctlz,cttz and powi are special intrinsics whose second argument is
2478         // a scalar. This argument should not be vectorized.
2479         if (hasVectorInstrinsicScalarOpd(IID, 1) && j == 1) {
2480           CallInst *CEI = cast<CallInst>(E->Scalars[0]);
2481           ScalarArg = CEI->getArgOperand(j);
2482           OpVecs.push_back(CEI->getArgOperand(j));
2483           continue;
2484         }
2485         for (Value *V : E->Scalars) {
2486           CallInst *CEI = cast<CallInst>(V);
2487           OpVL.push_back(CEI->getArgOperand(j));
2488         }
2489
2490         Value *OpVec = vectorizeTree(OpVL);
2491         DEBUG(dbgs() << "SLP: OpVec[" << j << "]: " << *OpVec << "\n");
2492         OpVecs.push_back(OpVec);
2493       }
2494
2495       Module *M = F->getParent();
2496       Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
2497       Type *Tys[] = { VectorType::get(CI->getType(), E->Scalars.size()) };
2498       Function *CF = Intrinsic::getDeclaration(M, ID, Tys);
2499       Value *V = Builder.CreateCall(CF, OpVecs);
2500
2501       // The scalar argument uses an in-tree scalar so we add the new vectorized
2502       // call to ExternalUses list to make sure that an extract will be
2503       // generated in the future.
2504       if (ScalarArg && ScalarToTreeEntry.count(ScalarArg))
2505         ExternalUses.push_back(ExternalUser(ScalarArg, cast<User>(V), 0));
2506
2507       E->VectorizedValue = V;
2508       ++NumVectorInstructions;
2509       return V;
2510     }
2511     case Instruction::ShuffleVector: {
2512       ValueList LHSVL, RHSVL;
2513       assert(isa<BinaryOperator>(VL0) && "Invalid Shuffle Vector Operand");
2514       reorderAltShuffleOperands(E->Scalars, LHSVL, RHSVL);
2515       setInsertPointAfterBundle(E->Scalars);
2516
2517       Value *LHS = vectorizeTree(LHSVL);
2518       Value *RHS = vectorizeTree(RHSVL);
2519
2520       if (Value *V = alreadyVectorized(E->Scalars))
2521         return V;
2522
2523       // Create a vector of LHS op1 RHS
2524       BinaryOperator *BinOp0 = cast<BinaryOperator>(VL0);
2525       Value *V0 = Builder.CreateBinOp(BinOp0->getOpcode(), LHS, RHS);
2526
2527       // Create a vector of LHS op2 RHS
2528       Instruction *VL1 = cast<Instruction>(E->Scalars[1]);
2529       BinaryOperator *BinOp1 = cast<BinaryOperator>(VL1);
2530       Value *V1 = Builder.CreateBinOp(BinOp1->getOpcode(), LHS, RHS);
2531
2532       // Create shuffle to take alternate operations from the vector.
2533       // Also, gather up odd and even scalar ops to propagate IR flags to
2534       // each vector operation.
2535       ValueList OddScalars, EvenScalars;
2536       unsigned e = E->Scalars.size();
2537       SmallVector<Constant *, 8> Mask(e);
2538       for (unsigned i = 0; i < e; ++i) {
2539         if (i & 1) {
2540           Mask[i] = Builder.getInt32(e + i);
2541           OddScalars.push_back(E->Scalars[i]);
2542         } else {
2543           Mask[i] = Builder.getInt32(i);
2544           EvenScalars.push_back(E->Scalars[i]);
2545         }
2546       }
2547
2548       Value *ShuffleMask = ConstantVector::get(Mask);
2549       propagateIRFlags(V0, EvenScalars);
2550       propagateIRFlags(V1, OddScalars);
2551
2552       Value *V = Builder.CreateShuffleVector(V0, V1, ShuffleMask);
2553       E->VectorizedValue = V;
2554       ++NumVectorInstructions;
2555       if (Instruction *I = dyn_cast<Instruction>(V))
2556         return propagateMetadata(I, E->Scalars);
2557
2558       return V;
2559     }
2560     default:
2561     llvm_unreachable("unknown inst");
2562   }
2563   return nullptr;
2564 }
2565
2566 Value *BoUpSLP::vectorizeTree() {
2567   
2568   // All blocks must be scheduled before any instructions are inserted.
2569   for (auto &BSIter : BlocksSchedules) {
2570     scheduleBlock(BSIter.second.get());
2571   }
2572
2573   Builder.SetInsertPoint(&F->getEntryBlock().front());
2574   vectorizeTree(&VectorizableTree[0]);
2575
2576   DEBUG(dbgs() << "SLP: Extracting " << ExternalUses.size() << " values .\n");
2577
2578   // Extract all of the elements with the external uses.
2579   for (UserList::iterator it = ExternalUses.begin(), e = ExternalUses.end();
2580        it != e; ++it) {
2581     Value *Scalar = it->Scalar;
2582     llvm::User *User = it->User;
2583
2584     // Skip users that we already RAUW. This happens when one instruction
2585     // has multiple uses of the same value.
2586     if (std::find(Scalar->user_begin(), Scalar->user_end(), User) ==
2587         Scalar->user_end())
2588       continue;
2589     assert(ScalarToTreeEntry.count(Scalar) && "Invalid scalar");
2590
2591     int Idx = ScalarToTreeEntry[Scalar];
2592     TreeEntry *E = &VectorizableTree[Idx];
2593     assert(!E->NeedToGather && "Extracting from a gather list");
2594
2595     Value *Vec = E->VectorizedValue;
2596     assert(Vec && "Can't find vectorizable value");
2597
2598     Value *Lane = Builder.getInt32(it->Lane);
2599     // Generate extracts for out-of-tree users.
2600     // Find the insertion point for the extractelement lane.
2601     if (isa<Instruction>(Vec)){
2602       if (PHINode *PH = dyn_cast<PHINode>(User)) {
2603         for (int i = 0, e = PH->getNumIncomingValues(); i != e; ++i) {
2604           if (PH->getIncomingValue(i) == Scalar) {
2605             Builder.SetInsertPoint(PH->getIncomingBlock(i)->getTerminator());
2606             Value *Ex = Builder.CreateExtractElement(Vec, Lane);
2607             CSEBlocks.insert(PH->getIncomingBlock(i));
2608             PH->setOperand(i, Ex);
2609           }
2610         }
2611       } else {
2612         Builder.SetInsertPoint(cast<Instruction>(User));
2613         Value *Ex = Builder.CreateExtractElement(Vec, Lane);
2614         CSEBlocks.insert(cast<Instruction>(User)->getParent());
2615         User->replaceUsesOfWith(Scalar, Ex);
2616      }
2617     } else {
2618       Builder.SetInsertPoint(&F->getEntryBlock().front());
2619       Value *Ex = Builder.CreateExtractElement(Vec, Lane);
2620       CSEBlocks.insert(&F->getEntryBlock());
2621       User->replaceUsesOfWith(Scalar, Ex);
2622     }
2623
2624     DEBUG(dbgs() << "SLP: Replaced:" << *User << ".\n");
2625   }
2626
2627   // For each vectorized value:
2628   for (int EIdx = 0, EE = VectorizableTree.size(); EIdx < EE; ++EIdx) {
2629     TreeEntry *Entry = &VectorizableTree[EIdx];
2630
2631     // For each lane:
2632     for (int Lane = 0, LE = Entry->Scalars.size(); Lane != LE; ++Lane) {
2633       Value *Scalar = Entry->Scalars[Lane];
2634       // No need to handle users of gathered values.
2635       if (Entry->NeedToGather)
2636         continue;
2637
2638       assert(Entry->VectorizedValue && "Can't find vectorizable value");
2639
2640       Type *Ty = Scalar->getType();
2641       if (!Ty->isVoidTy()) {
2642 #ifndef NDEBUG
2643         for (User *U : Scalar->users()) {
2644           DEBUG(dbgs() << "SLP: \tvalidating user:" << *U << ".\n");
2645
2646           assert((ScalarToTreeEntry.count(U) ||
2647                   // It is legal to replace users in the ignorelist by undef.
2648                   (std::find(UserIgnoreList.begin(), UserIgnoreList.end(), U) !=
2649                    UserIgnoreList.end())) &&
2650                  "Replacing out-of-tree value with undef");
2651         }
2652 #endif
2653         Value *Undef = UndefValue::get(Ty);
2654         Scalar->replaceAllUsesWith(Undef);
2655       }
2656       DEBUG(dbgs() << "SLP: \tErasing scalar:" << *Scalar << ".\n");
2657       eraseInstruction(cast<Instruction>(Scalar));
2658     }
2659   }
2660
2661   Builder.ClearInsertionPoint();
2662
2663   return VectorizableTree[0].VectorizedValue;
2664 }
2665
2666 void BoUpSLP::optimizeGatherSequence() {
2667   DEBUG(dbgs() << "SLP: Optimizing " << GatherSeq.size()
2668         << " gather sequences instructions.\n");
2669   // LICM InsertElementInst sequences.
2670   for (SetVector<Instruction *>::iterator it = GatherSeq.begin(),
2671        e = GatherSeq.end(); it != e; ++it) {
2672     InsertElementInst *Insert = dyn_cast<InsertElementInst>(*it);
2673
2674     if (!Insert)
2675       continue;
2676
2677     // Check if this block is inside a loop.
2678     Loop *L = LI->getLoopFor(Insert->getParent());
2679     if (!L)
2680       continue;
2681
2682     // Check if it has a preheader.
2683     BasicBlock *PreHeader = L->getLoopPreheader();
2684     if (!PreHeader)
2685       continue;
2686
2687     // If the vector or the element that we insert into it are
2688     // instructions that are defined in this basic block then we can't
2689     // hoist this instruction.
2690     Instruction *CurrVec = dyn_cast<Instruction>(Insert->getOperand(0));
2691     Instruction *NewElem = dyn_cast<Instruction>(Insert->getOperand(1));
2692     if (CurrVec && L->contains(CurrVec))
2693       continue;
2694     if (NewElem && L->contains(NewElem))
2695       continue;
2696
2697     // We can hoist this instruction. Move it to the pre-header.
2698     Insert->moveBefore(PreHeader->getTerminator());
2699   }
2700
2701   // Make a list of all reachable blocks in our CSE queue.
2702   SmallVector<const DomTreeNode *, 8> CSEWorkList;
2703   CSEWorkList.reserve(CSEBlocks.size());
2704   for (BasicBlock *BB : CSEBlocks)
2705     if (DomTreeNode *N = DT->getNode(BB)) {
2706       assert(DT->isReachableFromEntry(N));
2707       CSEWorkList.push_back(N);
2708     }
2709
2710   // Sort blocks by domination. This ensures we visit a block after all blocks
2711   // dominating it are visited.
2712   std::stable_sort(CSEWorkList.begin(), CSEWorkList.end(),
2713                    [this](const DomTreeNode *A, const DomTreeNode *B) {
2714     return DT->properlyDominates(A, B);
2715   });
2716
2717   // Perform O(N^2) search over the gather sequences and merge identical
2718   // instructions. TODO: We can further optimize this scan if we split the
2719   // instructions into different buckets based on the insert lane.
2720   SmallVector<Instruction *, 16> Visited;
2721   for (auto I = CSEWorkList.begin(), E = CSEWorkList.end(); I != E; ++I) {
2722     assert((I == CSEWorkList.begin() || !DT->dominates(*I, *std::prev(I))) &&
2723            "Worklist not sorted properly!");
2724     BasicBlock *BB = (*I)->getBlock();
2725     // For all instructions in blocks containing gather sequences:
2726     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e;) {
2727       Instruction *In = &*it++;
2728       if (!isa<InsertElementInst>(In) && !isa<ExtractElementInst>(In))
2729         continue;
2730
2731       // Check if we can replace this instruction with any of the
2732       // visited instructions.
2733       for (SmallVectorImpl<Instruction *>::iterator v = Visited.begin(),
2734                                                     ve = Visited.end();
2735            v != ve; ++v) {
2736         if (In->isIdenticalTo(*v) &&
2737             DT->dominates((*v)->getParent(), In->getParent())) {
2738           In->replaceAllUsesWith(*v);
2739           eraseInstruction(In);
2740           In = nullptr;
2741           break;
2742         }
2743       }
2744       if (In) {
2745         assert(std::find(Visited.begin(), Visited.end(), In) == Visited.end());
2746         Visited.push_back(In);
2747       }
2748     }
2749   }
2750   CSEBlocks.clear();
2751   GatherSeq.clear();
2752 }
2753
2754 // Groups the instructions to a bundle (which is then a single scheduling entity)
2755 // and schedules instructions until the bundle gets ready.
2756 bool BoUpSLP::BlockScheduling::tryScheduleBundle(ArrayRef<Value *> VL,
2757                                                  BoUpSLP *SLP) {
2758   if (isa<PHINode>(VL[0]))
2759     return true;
2760
2761   // Initialize the instruction bundle.
2762   Instruction *OldScheduleEnd = ScheduleEnd;
2763   ScheduleData *PrevInBundle = nullptr;
2764   ScheduleData *Bundle = nullptr;
2765   bool ReSchedule = false;
2766   DEBUG(dbgs() << "SLP:  bundle: " << *VL[0] << "\n");
2767
2768   // Make sure that the scheduling region contains all
2769   // instructions of the bundle.
2770   for (Value *V : VL) {
2771     if (!extendSchedulingRegion(V))
2772       return false;
2773   }
2774
2775   for (Value *V : VL) {
2776     ScheduleData *BundleMember = getScheduleData(V);
2777     assert(BundleMember &&
2778            "no ScheduleData for bundle member (maybe not in same basic block)");
2779     if (BundleMember->IsScheduled) {
2780       // A bundle member was scheduled as single instruction before and now
2781       // needs to be scheduled as part of the bundle. We just get rid of the
2782       // existing schedule.
2783       DEBUG(dbgs() << "SLP:  reset schedule because " << *BundleMember
2784                    << " was already scheduled\n");
2785       ReSchedule = true;
2786     }
2787     assert(BundleMember->isSchedulingEntity() &&
2788            "bundle member already part of other bundle");
2789     if (PrevInBundle) {
2790       PrevInBundle->NextInBundle = BundleMember;
2791     } else {
2792       Bundle = BundleMember;
2793     }
2794     BundleMember->UnscheduledDepsInBundle = 0;
2795     Bundle->UnscheduledDepsInBundle += BundleMember->UnscheduledDeps;
2796
2797     // Group the instructions to a bundle.
2798     BundleMember->FirstInBundle = Bundle;
2799     PrevInBundle = BundleMember;
2800   }
2801   if (ScheduleEnd != OldScheduleEnd) {
2802     // The scheduling region got new instructions at the lower end (or it is a
2803     // new region for the first bundle). This makes it necessary to
2804     // recalculate all dependencies.
2805     // It is seldom that this needs to be done a second time after adding the
2806     // initial bundle to the region.
2807     for (auto *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) {
2808       ScheduleData *SD = getScheduleData(I);
2809       SD->clearDependencies();
2810     }
2811     ReSchedule = true;
2812   }
2813   if (ReSchedule) {
2814     resetSchedule();
2815     initialFillReadyList(ReadyInsts);
2816   }
2817
2818   DEBUG(dbgs() << "SLP: try schedule bundle " << *Bundle << " in block "
2819                << BB->getName() << "\n");
2820
2821   calculateDependencies(Bundle, true, SLP);
2822
2823   // Now try to schedule the new bundle. As soon as the bundle is "ready" it
2824   // means that there are no cyclic dependencies and we can schedule it.
2825   // Note that's important that we don't "schedule" the bundle yet (see
2826   // cancelScheduling).
2827   while (!Bundle->isReady() && !ReadyInsts.empty()) {
2828
2829     ScheduleData *pickedSD = ReadyInsts.back();
2830     ReadyInsts.pop_back();
2831
2832     if (pickedSD->isSchedulingEntity() && pickedSD->isReady()) {
2833       schedule(pickedSD, ReadyInsts);
2834     }
2835   }
2836   if (!Bundle->isReady()) {
2837     cancelScheduling(VL);
2838     return false;
2839   }
2840   return true;
2841 }
2842
2843 void BoUpSLP::BlockScheduling::cancelScheduling(ArrayRef<Value *> VL) {
2844   if (isa<PHINode>(VL[0]))
2845     return;
2846
2847   ScheduleData *Bundle = getScheduleData(VL[0]);
2848   DEBUG(dbgs() << "SLP:  cancel scheduling of " << *Bundle << "\n");
2849   assert(!Bundle->IsScheduled &&
2850          "Can't cancel bundle which is already scheduled");
2851   assert(Bundle->isSchedulingEntity() && Bundle->isPartOfBundle() &&
2852          "tried to unbundle something which is not a bundle");
2853
2854   // Un-bundle: make single instructions out of the bundle.
2855   ScheduleData *BundleMember = Bundle;
2856   while (BundleMember) {
2857     assert(BundleMember->FirstInBundle == Bundle && "corrupt bundle links");
2858     BundleMember->FirstInBundle = BundleMember;
2859     ScheduleData *Next = BundleMember->NextInBundle;
2860     BundleMember->NextInBundle = nullptr;
2861     BundleMember->UnscheduledDepsInBundle = BundleMember->UnscheduledDeps;
2862     if (BundleMember->UnscheduledDepsInBundle == 0) {
2863       ReadyInsts.insert(BundleMember);
2864     }
2865     BundleMember = Next;
2866   }
2867 }
2868
2869 bool BoUpSLP::BlockScheduling::extendSchedulingRegion(Value *V) {
2870   if (getScheduleData(V))
2871     return true;
2872   Instruction *I = dyn_cast<Instruction>(V);
2873   assert(I && "bundle member must be an instruction");
2874   assert(!isa<PHINode>(I) && "phi nodes don't need to be scheduled");
2875   if (!ScheduleStart) {
2876     // It's the first instruction in the new region.
2877     initScheduleData(I, I->getNextNode(), nullptr, nullptr);
2878     ScheduleStart = I;
2879     ScheduleEnd = I->getNextNode();
2880     assert(ScheduleEnd && "tried to vectorize a TerminatorInst?");
2881     DEBUG(dbgs() << "SLP:  initialize schedule region to " << *I << "\n");
2882     return true;
2883   }
2884   // Search up and down at the same time, because we don't know if the new
2885   // instruction is above or below the existing scheduling region.
2886   BasicBlock::reverse_iterator UpIter(ScheduleStart->getIterator());
2887   BasicBlock::reverse_iterator UpperEnd = BB->rend();
2888   BasicBlock::iterator DownIter(ScheduleEnd);
2889   BasicBlock::iterator LowerEnd = BB->end();
2890   for (;;) {
2891     if (++ScheduleRegionSize > ScheduleRegionSizeLimit) {
2892       DEBUG(dbgs() << "SLP:  exceeded schedule region size limit\n");
2893       return false;
2894     }
2895
2896     if (UpIter != UpperEnd) {
2897       if (&*UpIter == I) {
2898         initScheduleData(I, ScheduleStart, nullptr, FirstLoadStoreInRegion);
2899         ScheduleStart = I;
2900         DEBUG(dbgs() << "SLP:  extend schedule region start to " << *I << "\n");
2901         return true;
2902       }
2903       UpIter++;
2904     }
2905     if (DownIter != LowerEnd) {
2906       if (&*DownIter == I) {
2907         initScheduleData(ScheduleEnd, I->getNextNode(), LastLoadStoreInRegion,
2908                          nullptr);
2909         ScheduleEnd = I->getNextNode();
2910         assert(ScheduleEnd && "tried to vectorize a TerminatorInst?");
2911         DEBUG(dbgs() << "SLP:  extend schedule region end to " << *I << "\n");
2912         return true;
2913       }
2914       DownIter++;
2915     }
2916     assert((UpIter != UpperEnd || DownIter != LowerEnd) &&
2917            "instruction not found in block");
2918   }
2919   return true;
2920 }
2921
2922 void BoUpSLP::BlockScheduling::initScheduleData(Instruction *FromI,
2923                                                 Instruction *ToI,
2924                                                 ScheduleData *PrevLoadStore,
2925                                                 ScheduleData *NextLoadStore) {
2926   ScheduleData *CurrentLoadStore = PrevLoadStore;
2927   for (Instruction *I = FromI; I != ToI; I = I->getNextNode()) {
2928     ScheduleData *SD = ScheduleDataMap[I];
2929     if (!SD) {
2930       // Allocate a new ScheduleData for the instruction.
2931       if (ChunkPos >= ChunkSize) {
2932         ScheduleDataChunks.push_back(
2933             llvm::make_unique<ScheduleData[]>(ChunkSize));
2934         ChunkPos = 0;
2935       }
2936       SD = &(ScheduleDataChunks.back()[ChunkPos++]);
2937       ScheduleDataMap[I] = SD;
2938       SD->Inst = I;
2939     }
2940     assert(!isInSchedulingRegion(SD) &&
2941            "new ScheduleData already in scheduling region");
2942     SD->init(SchedulingRegionID);
2943
2944     if (I->mayReadOrWriteMemory()) {
2945       // Update the linked list of memory accessing instructions.
2946       if (CurrentLoadStore) {
2947         CurrentLoadStore->NextLoadStore = SD;
2948       } else {
2949         FirstLoadStoreInRegion = SD;
2950       }
2951       CurrentLoadStore = SD;
2952     }
2953   }
2954   if (NextLoadStore) {
2955     if (CurrentLoadStore)
2956       CurrentLoadStore->NextLoadStore = NextLoadStore;
2957   } else {
2958     LastLoadStoreInRegion = CurrentLoadStore;
2959   }
2960 }
2961
2962 void BoUpSLP::BlockScheduling::calculateDependencies(ScheduleData *SD,
2963                                                      bool InsertInReadyList,
2964                                                      BoUpSLP *SLP) {
2965   assert(SD->isSchedulingEntity());
2966
2967   SmallVector<ScheduleData *, 10> WorkList;
2968   WorkList.push_back(SD);
2969
2970   while (!WorkList.empty()) {
2971     ScheduleData *SD = WorkList.back();
2972     WorkList.pop_back();
2973
2974     ScheduleData *BundleMember = SD;
2975     while (BundleMember) {
2976       assert(isInSchedulingRegion(BundleMember));
2977       if (!BundleMember->hasValidDependencies()) {
2978
2979         DEBUG(dbgs() << "SLP:       update deps of " << *BundleMember << "\n");
2980         BundleMember->Dependencies = 0;
2981         BundleMember->resetUnscheduledDeps();
2982
2983         // Handle def-use chain dependencies.
2984         for (User *U : BundleMember->Inst->users()) {
2985           if (isa<Instruction>(U)) {
2986             ScheduleData *UseSD = getScheduleData(U);
2987             if (UseSD && isInSchedulingRegion(UseSD->FirstInBundle)) {
2988               BundleMember->Dependencies++;
2989               ScheduleData *DestBundle = UseSD->FirstInBundle;
2990               if (!DestBundle->IsScheduled) {
2991                 BundleMember->incrementUnscheduledDeps(1);
2992               }
2993               if (!DestBundle->hasValidDependencies()) {
2994                 WorkList.push_back(DestBundle);
2995               }
2996             }
2997           } else {
2998             // I'm not sure if this can ever happen. But we need to be safe.
2999             // This lets the instruction/bundle never be scheduled and
3000             // eventually disable vectorization.
3001             BundleMember->Dependencies++;
3002             BundleMember->incrementUnscheduledDeps(1);
3003           }
3004         }
3005
3006         // Handle the memory dependencies.
3007         ScheduleData *DepDest = BundleMember->NextLoadStore;
3008         if (DepDest) {
3009           Instruction *SrcInst = BundleMember->Inst;
3010           MemoryLocation SrcLoc = getLocation(SrcInst, SLP->AA);
3011           bool SrcMayWrite = BundleMember->Inst->mayWriteToMemory();
3012           unsigned numAliased = 0;
3013           unsigned DistToSrc = 1;
3014
3015           while (DepDest) {
3016             assert(isInSchedulingRegion(DepDest));
3017
3018             // We have two limits to reduce the complexity:
3019             // 1) AliasedCheckLimit: It's a small limit to reduce calls to
3020             //    SLP->isAliased (which is the expensive part in this loop).
3021             // 2) MaxMemDepDistance: It's for very large blocks and it aborts
3022             //    the whole loop (even if the loop is fast, it's quadratic).
3023             //    It's important for the loop break condition (see below) to
3024             //    check this limit even between two read-only instructions.
3025             if (DistToSrc >= MaxMemDepDistance ||
3026                     ((SrcMayWrite || DepDest->Inst->mayWriteToMemory()) &&
3027                      (numAliased >= AliasedCheckLimit ||
3028                       SLP->isAliased(SrcLoc, SrcInst, DepDest->Inst)))) {
3029
3030               // We increment the counter only if the locations are aliased
3031               // (instead of counting all alias checks). This gives a better
3032               // balance between reduced runtime and accurate dependencies.
3033               numAliased++;
3034
3035               DepDest->MemoryDependencies.push_back(BundleMember);
3036               BundleMember->Dependencies++;
3037               ScheduleData *DestBundle = DepDest->FirstInBundle;
3038               if (!DestBundle->IsScheduled) {
3039                 BundleMember->incrementUnscheduledDeps(1);
3040               }
3041               if (!DestBundle->hasValidDependencies()) {
3042                 WorkList.push_back(DestBundle);
3043               }
3044             }
3045             DepDest = DepDest->NextLoadStore;
3046
3047             // Example, explaining the loop break condition: Let's assume our
3048             // starting instruction is i0 and MaxMemDepDistance = 3.
3049             //
3050             //                      +--------v--v--v
3051             //             i0,i1,i2,i3,i4,i5,i6,i7,i8
3052             //             +--------^--^--^
3053             //
3054             // MaxMemDepDistance let us stop alias-checking at i3 and we add
3055             // dependencies from i0 to i3,i4,.. (even if they are not aliased).
3056             // Previously we already added dependencies from i3 to i6,i7,i8
3057             // (because of MaxMemDepDistance). As we added a dependency from
3058             // i0 to i3, we have transitive dependencies from i0 to i6,i7,i8
3059             // and we can abort this loop at i6.
3060             if (DistToSrc >= 2 * MaxMemDepDistance)
3061                 break;
3062             DistToSrc++;
3063           }
3064         }
3065       }
3066       BundleMember = BundleMember->NextInBundle;
3067     }
3068     if (InsertInReadyList && SD->isReady()) {
3069       ReadyInsts.push_back(SD);
3070       DEBUG(dbgs() << "SLP:     gets ready on update: " << *SD->Inst << "\n");
3071     }
3072   }
3073 }
3074
3075 void BoUpSLP::BlockScheduling::resetSchedule() {
3076   assert(ScheduleStart &&
3077          "tried to reset schedule on block which has not been scheduled");
3078   for (Instruction *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) {
3079     ScheduleData *SD = getScheduleData(I);
3080     assert(isInSchedulingRegion(SD));
3081     SD->IsScheduled = false;
3082     SD->resetUnscheduledDeps();
3083   }
3084   ReadyInsts.clear();
3085 }
3086
3087 void BoUpSLP::scheduleBlock(BlockScheduling *BS) {
3088   
3089   if (!BS->ScheduleStart)
3090     return;
3091   
3092   DEBUG(dbgs() << "SLP: schedule block " << BS->BB->getName() << "\n");
3093
3094   BS->resetSchedule();
3095
3096   // For the real scheduling we use a more sophisticated ready-list: it is
3097   // sorted by the original instruction location. This lets the final schedule
3098   // be as  close as possible to the original instruction order.
3099   struct ScheduleDataCompare {
3100     bool operator()(ScheduleData *SD1, ScheduleData *SD2) {
3101       return SD2->SchedulingPriority < SD1->SchedulingPriority;
3102     }
3103   };
3104   std::set<ScheduleData *, ScheduleDataCompare> ReadyInsts;
3105
3106   // Ensure that all dependency data is updated and fill the ready-list with
3107   // initial instructions.
3108   int Idx = 0;
3109   int NumToSchedule = 0;
3110   for (auto *I = BS->ScheduleStart; I != BS->ScheduleEnd;
3111        I = I->getNextNode()) {
3112     ScheduleData *SD = BS->getScheduleData(I);
3113     assert(
3114         SD->isPartOfBundle() == (ScalarToTreeEntry.count(SD->Inst) != 0) &&
3115         "scheduler and vectorizer have different opinion on what is a bundle");
3116     SD->FirstInBundle->SchedulingPriority = Idx++;
3117     if (SD->isSchedulingEntity()) {
3118       BS->calculateDependencies(SD, false, this);
3119       NumToSchedule++;
3120     }
3121   }
3122   BS->initialFillReadyList(ReadyInsts);
3123
3124   Instruction *LastScheduledInst = BS->ScheduleEnd;
3125
3126   // Do the "real" scheduling.
3127   while (!ReadyInsts.empty()) {
3128     ScheduleData *picked = *ReadyInsts.begin();
3129     ReadyInsts.erase(ReadyInsts.begin());
3130
3131     // Move the scheduled instruction(s) to their dedicated places, if not
3132     // there yet.
3133     ScheduleData *BundleMember = picked;
3134     while (BundleMember) {
3135       Instruction *pickedInst = BundleMember->Inst;
3136       if (LastScheduledInst->getNextNode() != pickedInst) {
3137         BS->BB->getInstList().remove(pickedInst);
3138         BS->BB->getInstList().insert(LastScheduledInst->getIterator(),
3139                                      pickedInst);
3140       }
3141       LastScheduledInst = pickedInst;
3142       BundleMember = BundleMember->NextInBundle;
3143     }
3144
3145     BS->schedule(picked, ReadyInsts);
3146     NumToSchedule--;
3147   }
3148   assert(NumToSchedule == 0 && "could not schedule all instructions");
3149
3150   // Avoid duplicate scheduling of the block.
3151   BS->ScheduleStart = nullptr;
3152 }
3153
3154 /// The SLPVectorizer Pass.
3155 struct SLPVectorizer : public FunctionPass {
3156   typedef SmallVector<StoreInst *, 8> StoreList;
3157   typedef MapVector<Value *, StoreList> StoreListMap;
3158
3159   /// Pass identification, replacement for typeid
3160   static char ID;
3161
3162   explicit SLPVectorizer() : FunctionPass(ID) {
3163     initializeSLPVectorizerPass(*PassRegistry::getPassRegistry());
3164   }
3165
3166   ScalarEvolution *SE;
3167   TargetTransformInfo *TTI;
3168   TargetLibraryInfo *TLI;
3169   AliasAnalysis *AA;
3170   LoopInfo *LI;
3171   DominatorTree *DT;
3172   AssumptionCache *AC;
3173
3174   bool runOnFunction(Function &F) override {
3175     if (skipOptnoneFunction(F))
3176       return false;
3177
3178     SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
3179     TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
3180     auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
3181     TLI = TLIP ? &TLIP->getTLI() : nullptr;
3182     AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
3183     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
3184     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
3185     AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
3186
3187     StoreRefs.clear();
3188     bool Changed = false;
3189
3190     // If the target claims to have no vector registers don't attempt
3191     // vectorization.
3192     if (!TTI->getNumberOfRegisters(true))
3193       return false;
3194
3195     // Use the vector register size specified by the target unless overridden
3196     // by a command-line option.
3197     // TODO: It would be better to limit the vectorization factor based on
3198     //       data type rather than just register size. For example, x86 AVX has
3199     //       256-bit registers, but it does not support integer operations
3200     //       at that width (that requires AVX2).
3201     if (MaxVectorRegSizeOption.getNumOccurrences())
3202       MaxVecRegSize = MaxVectorRegSizeOption;
3203     else
3204       MaxVecRegSize = TTI->getRegisterBitWidth(true);
3205
3206     // Don't vectorize when the attribute NoImplicitFloat is used.
3207     if (F.hasFnAttribute(Attribute::NoImplicitFloat))
3208       return false;
3209
3210     DEBUG(dbgs() << "SLP: Analyzing blocks in " << F.getName() << ".\n");
3211
3212     // Use the bottom up slp vectorizer to construct chains that start with
3213     // store instructions.
3214     BoUpSLP R(&F, SE, TTI, TLI, AA, LI, DT, AC);
3215
3216     // A general note: the vectorizer must use BoUpSLP::eraseInstruction() to
3217     // delete instructions.
3218
3219     // Scan the blocks in the function in post order.
3220     for (auto BB : post_order(&F.getEntryBlock())) {
3221       // Vectorize trees that end at stores.
3222       if (unsigned count = collectStores(BB, R)) {
3223         (void)count;
3224         DEBUG(dbgs() << "SLP: Found " << count << " stores to vectorize.\n");
3225         Changed |= vectorizeStoreChains(R);
3226       }
3227
3228       // Vectorize trees that end at reductions.
3229       Changed |= vectorizeChainsInBlock(BB, R);
3230     }
3231
3232     if (Changed) {
3233       R.optimizeGatherSequence();
3234       DEBUG(dbgs() << "SLP: vectorized \"" << F.getName() << "\"\n");
3235       DEBUG(verifyFunction(F));
3236     }
3237     return Changed;
3238   }
3239
3240   void getAnalysisUsage(AnalysisUsage &AU) const override {
3241     FunctionPass::getAnalysisUsage(AU);
3242     AU.addRequired<AssumptionCacheTracker>();
3243     AU.addRequired<ScalarEvolutionWrapperPass>();
3244     AU.addRequired<AAResultsWrapperPass>();
3245     AU.addRequired<TargetTransformInfoWrapperPass>();
3246     AU.addRequired<LoopInfoWrapperPass>();
3247     AU.addRequired<DominatorTreeWrapperPass>();
3248     AU.addPreserved<LoopInfoWrapperPass>();
3249     AU.addPreserved<DominatorTreeWrapperPass>();
3250     AU.setPreservesCFG();
3251   }
3252
3253 private:
3254
3255   /// \brief Collect memory references and sort them according to their base
3256   /// object. We sort the stores to their base objects to reduce the cost of the
3257   /// quadratic search on the stores. TODO: We can further reduce this cost
3258   /// if we flush the chain creation every time we run into a memory barrier.
3259   unsigned collectStores(BasicBlock *BB, BoUpSLP &R);
3260
3261   /// \brief Try to vectorize a chain that starts at two arithmetic instrs.
3262   bool tryToVectorizePair(Value *A, Value *B, BoUpSLP &R);
3263
3264   /// \brief Try to vectorize a list of operands.
3265   /// \@param BuildVector A list of users to ignore for the purpose of
3266   ///                     scheduling and that don't need extracting.
3267   /// \returns true if a value was vectorized.
3268   bool tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R,
3269                           ArrayRef<Value *> BuildVector = None,
3270                           bool allowReorder = false);
3271
3272   /// \brief Try to vectorize a chain that may start at the operands of \V;
3273   bool tryToVectorize(BinaryOperator *V, BoUpSLP &R);
3274
3275   /// \brief Vectorize the stores that were collected in StoreRefs.
3276   bool vectorizeStoreChains(BoUpSLP &R);
3277
3278   /// \brief Scan the basic block and look for patterns that are likely to start
3279   /// a vectorization chain.
3280   bool vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R);
3281
3282   bool vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold,
3283                            BoUpSLP &R, unsigned VecRegSize);
3284
3285   bool vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold,
3286                        BoUpSLP &R);
3287 private:
3288   StoreListMap StoreRefs;
3289   unsigned MaxVecRegSize; // This is set by TTI or overridden by cl::opt.
3290 };
3291
3292 /// \brief Check that the Values in the slice in VL array are still existent in
3293 /// the WeakVH array.
3294 /// Vectorization of part of the VL array may cause later values in the VL array
3295 /// to become invalid. We track when this has happened in the WeakVH array.
3296 static bool hasValueBeenRAUWed(ArrayRef<Value *> VL, ArrayRef<WeakVH> VH,
3297                                unsigned SliceBegin, unsigned SliceSize) {
3298   VL = VL.slice(SliceBegin, SliceSize);
3299   VH = VH.slice(SliceBegin, SliceSize);
3300   return !std::equal(VL.begin(), VL.end(), VH.begin());
3301 }
3302
3303 bool SLPVectorizer::vectorizeStoreChain(ArrayRef<Value *> Chain,
3304                                         int CostThreshold, BoUpSLP &R,
3305                                         unsigned VecRegSize) {
3306   unsigned ChainLen = Chain.size();
3307   DEBUG(dbgs() << "SLP: Analyzing a store chain of length " << ChainLen
3308         << "\n");
3309   Type *StoreTy = cast<StoreInst>(Chain[0])->getValueOperand()->getType();
3310   auto &DL = cast<StoreInst>(Chain[0])->getModule()->getDataLayout();
3311   unsigned Sz = DL.getTypeSizeInBits(StoreTy);
3312   unsigned VF = VecRegSize / Sz;
3313
3314   if (!isPowerOf2_32(Sz) || VF < 2)
3315     return false;
3316
3317   // Keep track of values that were deleted by vectorizing in the loop below.
3318   SmallVector<WeakVH, 8> TrackValues(Chain.begin(), Chain.end());
3319
3320   bool Changed = false;
3321   // Look for profitable vectorizable trees at all offsets, starting at zero.
3322   for (unsigned i = 0, e = ChainLen; i < e; ++i) {
3323     if (i + VF > e)
3324       break;
3325
3326     // Check that a previous iteration of this loop did not delete the Value.
3327     if (hasValueBeenRAUWed(Chain, TrackValues, i, VF))
3328       continue;
3329
3330     DEBUG(dbgs() << "SLP: Analyzing " << VF << " stores at offset " << i
3331           << "\n");
3332     ArrayRef<Value *> Operands = Chain.slice(i, VF);
3333
3334     R.buildTree(Operands);
3335
3336     int Cost = R.getTreeCost();
3337
3338     DEBUG(dbgs() << "SLP: Found cost=" << Cost << " for VF=" << VF << "\n");
3339     if (Cost < CostThreshold) {
3340       DEBUG(dbgs() << "SLP: Decided to vectorize cost=" << Cost << "\n");
3341       R.vectorizeTree();
3342
3343       // Move to the next bundle.
3344       i += VF - 1;
3345       Changed = true;
3346     }
3347   }
3348
3349   return Changed;
3350 }
3351
3352 bool SLPVectorizer::vectorizeStores(ArrayRef<StoreInst *> Stores,
3353                                     int costThreshold, BoUpSLP &R) {