0930d580363e84022629632d9bda75194f728348
[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   bool AllSameOpcodeLeft = true;
2006   bool AllSameOpcodeRight = true;
2007
2008   if (VL.size()) {
2009     // Peel the first iteration out of the loop since there's nothing
2010     // interesting to do anyway and it simplifies the checks
2011     auto VLeft = cast<Instruction>(VL[0])->getOperand(0);
2012     auto VRight = cast<Instruction>(VL[0])->getOperand(1);
2013     OrigLeft.push_back(VLeft);
2014     OrigRight.push_back(VRight);
2015     if (!isa<Instruction>(VRight) && isa<Instruction>(VLeft))
2016       // Favor having instruction to the right. FIXME: why?
2017       std::swap(VLeft, VRight);
2018     Left.push_back(VLeft);
2019     Right.push_back(VRight);
2020   }
2021
2022   for (unsigned i = 1, e = VL.size(); i != e; ++i) {
2023     Instruction *I = cast<Instruction>(VL[i]);
2024
2025     Value *VLeft = I->getOperand(0);
2026     Value *VRight = I->getOperand(1);
2027     OrigLeft.push_back(VLeft);
2028     OrigRight.push_back(VRight);
2029     Instruction *ILeft = dyn_cast<Instruction>(VLeft);
2030     Instruction *IRight = dyn_cast<Instruction>(VRight);
2031
2032     // Check whether all operands on one side have the same opcode. In this case
2033     // we want to preserve the original order and not make things worse by
2034     // reordering.
2035     if (AllSameOpcodeLeft && ILeft) {
2036       if (Instruction *PLeft = dyn_cast<Instruction>(OrigLeft[i - 1])) {
2037         if (PLeft->getOpcode() != ILeft->getOpcode())
2038           AllSameOpcodeLeft = false;
2039       } else
2040         AllSameOpcodeLeft = false;
2041     }
2042     if (AllSameOpcodeRight && IRight) {
2043       if (Instruction *PRight = dyn_cast<Instruction>(OrigRight[i - 1])) {
2044         if (PRight->getOpcode() != IRight->getOpcode())
2045           AllSameOpcodeRight = false;
2046       } else
2047         AllSameOpcodeRight = false;
2048     }
2049
2050
2051     // Commute to favor either a splat or maximizing having the same opcodes on
2052     // one side.
2053     if (shouldReorderOperands(i, *I, Left, Right)) {
2054       Left.push_back(I->getOperand(1));
2055       Right.push_back(I->getOperand(0));
2056     } else {
2057       Left.push_back(I->getOperand(0));
2058       Right.push_back(I->getOperand(1));
2059     }
2060   }
2061
2062   bool LeftBroadcast = isSplat(Left);
2063   bool RightBroadcast = isSplat(Right);
2064
2065   // If operands end up being broadcast return this operand order.
2066   if (LeftBroadcast || RightBroadcast)
2067     return;
2068
2069   // Don't reorder if the operands where good to begin.
2070   if (AllSameOpcodeRight || AllSameOpcodeLeft) {
2071     Left = OrigLeft;
2072     Right = OrigRight;
2073   }
2074
2075   const DataLayout &DL = F->getParent()->getDataLayout();
2076
2077   // Finally check if we can get longer vectorizable chain by reordering
2078   // without breaking the good operand order detected above.
2079   // E.g. If we have something like-
2080   // load a[0]  load b[0]
2081   // load b[1]  load a[1]
2082   // load a[2]  load b[2]
2083   // load a[3]  load b[3]
2084   // Reordering the second load b[1]  load a[1] would allow us to vectorize
2085   // this code and we still retain AllSameOpcode property.
2086   // FIXME: This load reordering might break AllSameOpcode in some rare cases
2087   // such as-
2088   // add a[0],c[0]  load b[0]
2089   // add a[1],c[2]  load b[1]
2090   // b[2]           load b[2]
2091   // add a[3],c[3]  load b[3]
2092   for (unsigned j = 0; j < VL.size() - 1; ++j) {
2093     if (LoadInst *L = dyn_cast<LoadInst>(Left[j])) {
2094       if (LoadInst *L1 = dyn_cast<LoadInst>(Right[j + 1])) {
2095         if (isConsecutiveAccess(L, L1, DL)) {
2096           std::swap(Left[j + 1], Right[j + 1]);
2097           continue;
2098         }
2099       }
2100     }
2101     if (LoadInst *L = dyn_cast<LoadInst>(Right[j])) {
2102       if (LoadInst *L1 = dyn_cast<LoadInst>(Left[j + 1])) {
2103         if (isConsecutiveAccess(L, L1, DL)) {
2104           std::swap(Left[j + 1], Right[j + 1]);
2105           continue;
2106         }
2107       }
2108     }
2109     // else unchanged
2110   }
2111 }
2112
2113 void BoUpSLP::setInsertPointAfterBundle(ArrayRef<Value *> VL) {
2114   Instruction *VL0 = cast<Instruction>(VL[0]);
2115   BasicBlock::iterator NextInst(VL0);
2116   ++NextInst;
2117   Builder.SetInsertPoint(VL0->getParent(), NextInst);
2118   Builder.SetCurrentDebugLocation(VL0->getDebugLoc());
2119 }
2120
2121 Value *BoUpSLP::Gather(ArrayRef<Value *> VL, VectorType *Ty) {
2122   Value *Vec = UndefValue::get(Ty);
2123   // Generate the 'InsertElement' instruction.
2124   for (unsigned i = 0; i < Ty->getNumElements(); ++i) {
2125     Vec = Builder.CreateInsertElement(Vec, VL[i], Builder.getInt32(i));
2126     if (Instruction *Insrt = dyn_cast<Instruction>(Vec)) {
2127       GatherSeq.insert(Insrt);
2128       CSEBlocks.insert(Insrt->getParent());
2129
2130       // Add to our 'need-to-extract' list.
2131       if (ScalarToTreeEntry.count(VL[i])) {
2132         int Idx = ScalarToTreeEntry[VL[i]];
2133         TreeEntry *E = &VectorizableTree[Idx];
2134         // Find which lane we need to extract.
2135         int FoundLane = -1;
2136         for (unsigned Lane = 0, LE = VL.size(); Lane != LE; ++Lane) {
2137           // Is this the lane of the scalar that we are looking for ?
2138           if (E->Scalars[Lane] == VL[i]) {
2139             FoundLane = Lane;
2140             break;
2141           }
2142         }
2143         assert(FoundLane >= 0 && "Could not find the correct lane");
2144         ExternalUses.push_back(ExternalUser(VL[i], Insrt, FoundLane));
2145       }
2146     }
2147   }
2148
2149   return Vec;
2150 }
2151
2152 Value *BoUpSLP::alreadyVectorized(ArrayRef<Value *> VL) const {
2153   SmallDenseMap<Value*, int>::const_iterator Entry
2154     = ScalarToTreeEntry.find(VL[0]);
2155   if (Entry != ScalarToTreeEntry.end()) {
2156     int Idx = Entry->second;
2157     const TreeEntry *En = &VectorizableTree[Idx];
2158     if (En->isSame(VL) && En->VectorizedValue)
2159       return En->VectorizedValue;
2160   }
2161   return nullptr;
2162 }
2163
2164 Value *BoUpSLP::vectorizeTree(ArrayRef<Value *> VL) {
2165   if (ScalarToTreeEntry.count(VL[0])) {
2166     int Idx = ScalarToTreeEntry[VL[0]];
2167     TreeEntry *E = &VectorizableTree[Idx];
2168     if (E->isSame(VL))
2169       return vectorizeTree(E);
2170   }
2171
2172   Type *ScalarTy = VL[0]->getType();
2173   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
2174     ScalarTy = SI->getValueOperand()->getType();
2175   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
2176
2177   return Gather(VL, VecTy);
2178 }
2179
2180 Value *BoUpSLP::vectorizeTree(TreeEntry *E) {
2181   IRBuilder<>::InsertPointGuard Guard(Builder);
2182
2183   if (E->VectorizedValue) {
2184     DEBUG(dbgs() << "SLP: Diamond merged for " << *E->Scalars[0] << ".\n");
2185     return E->VectorizedValue;
2186   }
2187
2188   Instruction *VL0 = cast<Instruction>(E->Scalars[0]);
2189   Type *ScalarTy = VL0->getType();
2190   if (StoreInst *SI = dyn_cast<StoreInst>(VL0))
2191     ScalarTy = SI->getValueOperand()->getType();
2192   VectorType *VecTy = VectorType::get(ScalarTy, E->Scalars.size());
2193
2194   if (E->NeedToGather) {
2195     setInsertPointAfterBundle(E->Scalars);
2196     return Gather(E->Scalars, VecTy);
2197   }
2198
2199   const DataLayout &DL = F->getParent()->getDataLayout();
2200   unsigned Opcode = getSameOpcode(E->Scalars);
2201
2202   switch (Opcode) {
2203     case Instruction::PHI: {
2204       PHINode *PH = dyn_cast<PHINode>(VL0);
2205       Builder.SetInsertPoint(PH->getParent()->getFirstNonPHI());
2206       Builder.SetCurrentDebugLocation(PH->getDebugLoc());
2207       PHINode *NewPhi = Builder.CreatePHI(VecTy, PH->getNumIncomingValues());
2208       E->VectorizedValue = NewPhi;
2209
2210       // PHINodes may have multiple entries from the same block. We want to
2211       // visit every block once.
2212       SmallSet<BasicBlock*, 4> VisitedBBs;
2213
2214       for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
2215         ValueList Operands;
2216         BasicBlock *IBB = PH->getIncomingBlock(i);
2217
2218         if (!VisitedBBs.insert(IBB).second) {
2219           NewPhi->addIncoming(NewPhi->getIncomingValueForBlock(IBB), IBB);
2220           continue;
2221         }
2222
2223         // Prepare the operand vector.
2224         for (Value *V : E->Scalars)
2225           Operands.push_back(cast<PHINode>(V)->getIncomingValueForBlock(IBB));
2226
2227         Builder.SetInsertPoint(IBB->getTerminator());
2228         Builder.SetCurrentDebugLocation(PH->getDebugLoc());
2229         Value *Vec = vectorizeTree(Operands);
2230         NewPhi->addIncoming(Vec, IBB);
2231       }
2232
2233       assert(NewPhi->getNumIncomingValues() == PH->getNumIncomingValues() &&
2234              "Invalid number of incoming values");
2235       return NewPhi;
2236     }
2237
2238     case Instruction::ExtractElement: {
2239       if (CanReuseExtract(E->Scalars)) {
2240         Value *V = VL0->getOperand(0);
2241         E->VectorizedValue = V;
2242         return V;
2243       }
2244       return Gather(E->Scalars, VecTy);
2245     }
2246     case Instruction::ZExt:
2247     case Instruction::SExt:
2248     case Instruction::FPToUI:
2249     case Instruction::FPToSI:
2250     case Instruction::FPExt:
2251     case Instruction::PtrToInt:
2252     case Instruction::IntToPtr:
2253     case Instruction::SIToFP:
2254     case Instruction::UIToFP:
2255     case Instruction::Trunc:
2256     case Instruction::FPTrunc:
2257     case Instruction::BitCast: {
2258       ValueList INVL;
2259       for (Value *V : E->Scalars)
2260         INVL.push_back(cast<Instruction>(V)->getOperand(0));
2261
2262       setInsertPointAfterBundle(E->Scalars);
2263
2264       Value *InVec = vectorizeTree(INVL);
2265
2266       if (Value *V = alreadyVectorized(E->Scalars))
2267         return V;
2268
2269       CastInst *CI = dyn_cast<CastInst>(VL0);
2270       Value *V = Builder.CreateCast(CI->getOpcode(), InVec, VecTy);
2271       E->VectorizedValue = V;
2272       ++NumVectorInstructions;
2273       return V;
2274     }
2275     case Instruction::FCmp:
2276     case Instruction::ICmp: {
2277       ValueList LHSV, RHSV;
2278       for (Value *V : E->Scalars) {
2279         LHSV.push_back(cast<Instruction>(V)->getOperand(0));
2280         RHSV.push_back(cast<Instruction>(V)->getOperand(1));
2281       }
2282
2283       setInsertPointAfterBundle(E->Scalars);
2284
2285       Value *L = vectorizeTree(LHSV);
2286       Value *R = vectorizeTree(RHSV);
2287
2288       if (Value *V = alreadyVectorized(E->Scalars))
2289         return V;
2290
2291       CmpInst::Predicate P0 = cast<CmpInst>(VL0)->getPredicate();
2292       Value *V;
2293       if (Opcode == Instruction::FCmp)
2294         V = Builder.CreateFCmp(P0, L, R);
2295       else
2296         V = Builder.CreateICmp(P0, L, R);
2297
2298       E->VectorizedValue = V;
2299       ++NumVectorInstructions;
2300       return V;
2301     }
2302     case Instruction::Select: {
2303       ValueList TrueVec, FalseVec, CondVec;
2304       for (Value *V : E->Scalars) {
2305         CondVec.push_back(cast<Instruction>(V)->getOperand(0));
2306         TrueVec.push_back(cast<Instruction>(V)->getOperand(1));
2307         FalseVec.push_back(cast<Instruction>(V)->getOperand(2));
2308       }
2309
2310       setInsertPointAfterBundle(E->Scalars);
2311
2312       Value *Cond = vectorizeTree(CondVec);
2313       Value *True = vectorizeTree(TrueVec);
2314       Value *False = vectorizeTree(FalseVec);
2315
2316       if (Value *V = alreadyVectorized(E->Scalars))
2317         return V;
2318
2319       Value *V = Builder.CreateSelect(Cond, True, False);
2320       E->VectorizedValue = V;
2321       ++NumVectorInstructions;
2322       return V;
2323     }
2324     case Instruction::Add:
2325     case Instruction::FAdd:
2326     case Instruction::Sub:
2327     case Instruction::FSub:
2328     case Instruction::Mul:
2329     case Instruction::FMul:
2330     case Instruction::UDiv:
2331     case Instruction::SDiv:
2332     case Instruction::FDiv:
2333     case Instruction::URem:
2334     case Instruction::SRem:
2335     case Instruction::FRem:
2336     case Instruction::Shl:
2337     case Instruction::LShr:
2338     case Instruction::AShr:
2339     case Instruction::And:
2340     case Instruction::Or:
2341     case Instruction::Xor: {
2342       ValueList LHSVL, RHSVL;
2343       if (isa<BinaryOperator>(VL0) && VL0->isCommutative())
2344         reorderInputsAccordingToOpcode(E->Scalars, LHSVL, RHSVL);
2345       else
2346         for (Value *V : E->Scalars) {
2347           LHSVL.push_back(cast<Instruction>(V)->getOperand(0));
2348           RHSVL.push_back(cast<Instruction>(V)->getOperand(1));
2349         }
2350
2351       setInsertPointAfterBundle(E->Scalars);
2352
2353       Value *LHS = vectorizeTree(LHSVL);
2354       Value *RHS = vectorizeTree(RHSVL);
2355
2356       if (LHS == RHS && isa<Instruction>(LHS)) {
2357         assert((VL0->getOperand(0) == VL0->getOperand(1)) && "Invalid order");
2358       }
2359
2360       if (Value *V = alreadyVectorized(E->Scalars))
2361         return V;
2362
2363       BinaryOperator *BinOp = cast<BinaryOperator>(VL0);
2364       Value *V = Builder.CreateBinOp(BinOp->getOpcode(), LHS, RHS);
2365       E->VectorizedValue = V;
2366       propagateIRFlags(E->VectorizedValue, E->Scalars);
2367       ++NumVectorInstructions;
2368
2369       if (Instruction *I = dyn_cast<Instruction>(V))
2370         return propagateMetadata(I, E->Scalars);
2371
2372       return V;
2373     }
2374     case Instruction::Load: {
2375       // Loads are inserted at the head of the tree because we don't want to
2376       // sink them all the way down past store instructions.
2377       setInsertPointAfterBundle(E->Scalars);
2378
2379       LoadInst *LI = cast<LoadInst>(VL0);
2380       Type *ScalarLoadTy = LI->getType();
2381       unsigned AS = LI->getPointerAddressSpace();
2382
2383       Value *VecPtr = Builder.CreateBitCast(LI->getPointerOperand(),
2384                                             VecTy->getPointerTo(AS));
2385
2386       // The pointer operand uses an in-tree scalar so we add the new BitCast to
2387       // ExternalUses list to make sure that an extract will be generated in the
2388       // future.
2389       if (ScalarToTreeEntry.count(LI->getPointerOperand()))
2390         ExternalUses.push_back(
2391             ExternalUser(LI->getPointerOperand(), cast<User>(VecPtr), 0));
2392
2393       unsigned Alignment = LI->getAlignment();
2394       LI = Builder.CreateLoad(VecPtr);
2395       if (!Alignment) {
2396         Alignment = DL.getABITypeAlignment(ScalarLoadTy);
2397       }
2398       LI->setAlignment(Alignment);
2399       E->VectorizedValue = LI;
2400       ++NumVectorInstructions;
2401       return propagateMetadata(LI, E->Scalars);
2402     }
2403     case Instruction::Store: {
2404       StoreInst *SI = cast<StoreInst>(VL0);
2405       unsigned Alignment = SI->getAlignment();
2406       unsigned AS = SI->getPointerAddressSpace();
2407
2408       ValueList ValueOp;
2409       for (Value *V : E->Scalars)
2410         ValueOp.push_back(cast<StoreInst>(V)->getValueOperand());
2411
2412       setInsertPointAfterBundle(E->Scalars);
2413
2414       Value *VecValue = vectorizeTree(ValueOp);
2415       Value *VecPtr = Builder.CreateBitCast(SI->getPointerOperand(),
2416                                             VecTy->getPointerTo(AS));
2417       StoreInst *S = Builder.CreateStore(VecValue, VecPtr);
2418
2419       // The pointer operand uses an in-tree scalar so we add the new BitCast to
2420       // ExternalUses list to make sure that an extract will be generated in the
2421       // future.
2422       if (ScalarToTreeEntry.count(SI->getPointerOperand()))
2423         ExternalUses.push_back(
2424             ExternalUser(SI->getPointerOperand(), cast<User>(VecPtr), 0));
2425
2426       if (!Alignment) {
2427         Alignment = DL.getABITypeAlignment(SI->getValueOperand()->getType());
2428       }
2429       S->setAlignment(Alignment);
2430       E->VectorizedValue = S;
2431       ++NumVectorInstructions;
2432       return propagateMetadata(S, E->Scalars);
2433     }
2434     case Instruction::GetElementPtr: {
2435       setInsertPointAfterBundle(E->Scalars);
2436
2437       ValueList Op0VL;
2438       for (Value *V : E->Scalars)
2439         Op0VL.push_back(cast<GetElementPtrInst>(V)->getOperand(0));
2440
2441       Value *Op0 = vectorizeTree(Op0VL);
2442
2443       std::vector<Value *> OpVecs;
2444       for (int j = 1, e = cast<GetElementPtrInst>(VL0)->getNumOperands(); j < e;
2445            ++j) {
2446         ValueList OpVL;
2447         for (Value *V : E->Scalars)
2448           OpVL.push_back(cast<GetElementPtrInst>(V)->getOperand(j));
2449
2450         Value *OpVec = vectorizeTree(OpVL);
2451         OpVecs.push_back(OpVec);
2452       }
2453
2454       Value *V = Builder.CreateGEP(
2455           cast<GetElementPtrInst>(VL0)->getSourceElementType(), Op0, OpVecs);
2456       E->VectorizedValue = V;
2457       ++NumVectorInstructions;
2458
2459       if (Instruction *I = dyn_cast<Instruction>(V))
2460         return propagateMetadata(I, E->Scalars);
2461
2462       return V;
2463     }
2464     case Instruction::Call: {
2465       CallInst *CI = cast<CallInst>(VL0);
2466       setInsertPointAfterBundle(E->Scalars);
2467       Function *FI;
2468       Intrinsic::ID IID  = Intrinsic::not_intrinsic;
2469       Value *ScalarArg = nullptr;
2470       if (CI && (FI = CI->getCalledFunction())) {
2471         IID = FI->getIntrinsicID();
2472       }
2473       std::vector<Value *> OpVecs;
2474       for (int j = 0, e = CI->getNumArgOperands(); j < e; ++j) {
2475         ValueList OpVL;
2476         // ctlz,cttz and powi are special intrinsics whose second argument is
2477         // a scalar. This argument should not be vectorized.
2478         if (hasVectorInstrinsicScalarOpd(IID, 1) && j == 1) {
2479           CallInst *CEI = cast<CallInst>(E->Scalars[0]);
2480           ScalarArg = CEI->getArgOperand(j);
2481           OpVecs.push_back(CEI->getArgOperand(j));
2482           continue;
2483         }
2484         for (Value *V : E->Scalars) {
2485           CallInst *CEI = cast<CallInst>(V);
2486           OpVL.push_back(CEI->getArgOperand(j));
2487         }
2488
2489         Value *OpVec = vectorizeTree(OpVL);
2490         DEBUG(dbgs() << "SLP: OpVec[" << j << "]: " << *OpVec << "\n");
2491         OpVecs.push_back(OpVec);
2492       }
2493
2494       Module *M = F->getParent();
2495       Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
2496       Type *Tys[] = { VectorType::get(CI->getType(), E->Scalars.size()) };
2497       Function *CF = Intrinsic::getDeclaration(M, ID, Tys);
2498       Value *V = Builder.CreateCall(CF, OpVecs);
2499
2500       // The scalar argument uses an in-tree scalar so we add the new vectorized
2501       // call to ExternalUses list to make sure that an extract will be
2502       // generated in the future.
2503       if (ScalarArg && ScalarToTreeEntry.count(ScalarArg))
2504         ExternalUses.push_back(ExternalUser(ScalarArg, cast<User>(V), 0));
2505
2506       E->VectorizedValue = V;
2507       ++NumVectorInstructions;
2508       return V;
2509     }
2510     case Instruction::ShuffleVector: {
2511       ValueList LHSVL, RHSVL;
2512       assert(isa<BinaryOperator>(VL0) && "Invalid Shuffle Vector Operand");
2513       reorderAltShuffleOperands(E->Scalars, LHSVL, RHSVL);
2514       setInsertPointAfterBundle(E->Scalars);
2515
2516       Value *LHS = vectorizeTree(LHSVL);
2517       Value *RHS = vectorizeTree(RHSVL);
2518
2519       if (Value *V = alreadyVectorized(E->Scalars))
2520         return V;
2521
2522       // Create a vector of LHS op1 RHS
2523       BinaryOperator *BinOp0 = cast<BinaryOperator>(VL0);
2524       Value *V0 = Builder.CreateBinOp(BinOp0->getOpcode(), LHS, RHS);
2525
2526       // Create a vector of LHS op2 RHS
2527       Instruction *VL1 = cast<Instruction>(E->Scalars[1]);
2528       BinaryOperator *BinOp1 = cast<BinaryOperator>(VL1);
2529       Value *V1 = Builder.CreateBinOp(BinOp1->getOpcode(), LHS, RHS);
2530
2531       // Create shuffle to take alternate operations from the vector.
2532       // Also, gather up odd and even scalar ops to propagate IR flags to
2533       // each vector operation.
2534       ValueList OddScalars, EvenScalars;
2535       unsigned e = E->Scalars.size();
2536       SmallVector<Constant *, 8> Mask(e);
2537       for (unsigned i = 0; i < e; ++i) {
2538         if (i & 1) {
2539           Mask[i] = Builder.getInt32(e + i);
2540           OddScalars.push_back(E->Scalars[i]);
2541         } else {
2542           Mask[i] = Builder.getInt32(i);
2543           EvenScalars.push_back(E->Scalars[i]);
2544         }
2545       }
2546
2547       Value *ShuffleMask = ConstantVector::get(Mask);
2548       propagateIRFlags(V0, EvenScalars);
2549       propagateIRFlags(V1, OddScalars);
2550
2551       Value *V = Builder.CreateShuffleVector(V0, V1, ShuffleMask);
2552       E->VectorizedValue = V;
2553       ++NumVectorInstructions;
2554       if (Instruction *I = dyn_cast<Instruction>(V))
2555         return propagateMetadata(I, E->Scalars);
2556
2557       return V;
2558     }
2559     default:
2560     llvm_unreachable("unknown inst");
2561   }
2562   return nullptr;
2563 }
2564
2565 Value *BoUpSLP::vectorizeTree() {
2566   
2567   // All blocks must be scheduled before any instructions are inserted.
2568   for (auto &BSIter : BlocksSchedules) {
2569     scheduleBlock(BSIter.second.get());
2570   }
2571
2572   Builder.SetInsertPoint(&F->getEntryBlock().front());
2573   vectorizeTree(&VectorizableTree[0]);
2574
2575   DEBUG(dbgs() << "SLP: Extracting " << ExternalUses.size() << " values .\n");
2576
2577   // Extract all of the elements with the external uses.
2578   for (UserList::iterator it = ExternalUses.begin(), e = ExternalUses.end();
2579        it != e; ++it) {
2580     Value *Scalar = it->Scalar;
2581     llvm::User *User = it->User;
2582
2583     // Skip users that we already RAUW. This happens when one instruction
2584     // has multiple uses of the same value.
2585     if (std::find(Scalar->user_begin(), Scalar->user_end(), User) ==
2586         Scalar->user_end())
2587       continue;
2588     assert(ScalarToTreeEntry.count(Scalar) && "Invalid scalar");
2589
2590     int Idx = ScalarToTreeEntry[Scalar];
2591     TreeEntry *E = &VectorizableTree[Idx];
2592     assert(!E->NeedToGather && "Extracting from a gather list");
2593
2594     Value *Vec = E->VectorizedValue;
2595     assert(Vec && "Can't find vectorizable value");
2596
2597     Value *Lane = Builder.getInt32(it->Lane);
2598     // Generate extracts for out-of-tree users.
2599     // Find the insertion point for the extractelement lane.
2600     if (isa<Instruction>(Vec)){
2601       if (PHINode *PH = dyn_cast<PHINode>(User)) {
2602         for (int i = 0, e = PH->getNumIncomingValues(); i != e; ++i) {
2603           if (PH->getIncomingValue(i) == Scalar) {
2604             Builder.SetInsertPoint(PH->getIncomingBlock(i)->getTerminator());
2605             Value *Ex = Builder.CreateExtractElement(Vec, Lane);
2606             CSEBlocks.insert(PH->getIncomingBlock(i));
2607             PH->setOperand(i, Ex);
2608           }
2609         }
2610       } else {
2611         Builder.SetInsertPoint(cast<Instruction>(User));
2612         Value *Ex = Builder.CreateExtractElement(Vec, Lane);
2613         CSEBlocks.insert(cast<Instruction>(User)->getParent());
2614         User->replaceUsesOfWith(Scalar, Ex);
2615      }
2616     } else {
2617       Builder.SetInsertPoint(&F->getEntryBlock().front());
2618       Value *Ex = Builder.CreateExtractElement(Vec, Lane);
2619       CSEBlocks.insert(&F->getEntryBlock());
2620       User->replaceUsesOfWith(Scalar, Ex);
2621     }
2622
2623     DEBUG(dbgs() << "SLP: Replaced:" << *User << ".\n");
2624   }
2625
2626   // For each vectorized value:
2627   for (int EIdx = 0, EE = VectorizableTree.size(); EIdx < EE; ++EIdx) {
2628     TreeEntry *Entry = &VectorizableTree[EIdx];
2629
2630     // For each lane:
2631     for (int Lane = 0, LE = Entry->Scalars.size(); Lane != LE; ++Lane) {
2632       Value *Scalar = Entry->Scalars[Lane];
2633       // No need to handle users of gathered values.
2634       if (Entry->NeedToGather)
2635         continue;
2636
2637       assert(Entry->VectorizedValue && "Can't find vectorizable value");
2638
2639       Type *Ty = Scalar->getType();
2640       if (!Ty->isVoidTy()) {
2641 #ifndef NDEBUG
2642         for (User *U : Scalar->users()) {
2643           DEBUG(dbgs() << "SLP: \tvalidating user:" << *U << ".\n");
2644
2645           assert((ScalarToTreeEntry.count(U) ||
2646                   // It is legal to replace users in the ignorelist by undef.
2647                   (std::find(UserIgnoreList.begin(), UserIgnoreList.end(), U) !=
2648                    UserIgnoreList.end())) &&
2649                  "Replacing out-of-tree value with undef");
2650         }
2651 #endif
2652         Value *Undef = UndefValue::get(Ty);
2653         Scalar->replaceAllUsesWith(Undef);
2654       }
2655       DEBUG(dbgs() << "SLP: \tErasing scalar:" << *Scalar << ".\n");
2656       eraseInstruction(cast<Instruction>(Scalar));
2657     }
2658   }
2659
2660   Builder.ClearInsertionPoint();
2661
2662   return VectorizableTree[0].VectorizedValue;
2663 }
2664
2665 void BoUpSLP::optimizeGatherSequence() {
2666   DEBUG(dbgs() << "SLP: Optimizing " << GatherSeq.size()
2667         << " gather sequences instructions.\n");
2668   // LICM InsertElementInst sequences.
2669   for (SetVector<Instruction *>::iterator it = GatherSeq.begin(),
2670        e = GatherSeq.end(); it != e; ++it) {
2671     InsertElementInst *Insert = dyn_cast<InsertElementInst>(*it);
2672
2673     if (!Insert)
2674       continue;
2675
2676     // Check if this block is inside a loop.
2677     Loop *L = LI->getLoopFor(Insert->getParent());
2678     if (!L)
2679       continue;
2680
2681     // Check if it has a preheader.
2682     BasicBlock *PreHeader = L->getLoopPreheader();
2683     if (!PreHeader)
2684       continue;
2685
2686     // If the vector or the element that we insert into it are
2687     // instructions that are defined in this basic block then we can't
2688     // hoist this instruction.
2689     Instruction *CurrVec = dyn_cast<Instruction>(Insert->getOperand(0));
2690     Instruction *NewElem = dyn_cast<Instruction>(Insert->getOperand(1));
2691     if (CurrVec && L->contains(CurrVec))
2692       continue;
2693     if (NewElem && L->contains(NewElem))
2694       continue;
2695
2696     // We can hoist this instruction. Move it to the pre-header.
2697     Insert->moveBefore(PreHeader->getTerminator());
2698   }
2699
2700   // Make a list of all reachable blocks in our CSE queue.
2701   SmallVector<const DomTreeNode *, 8> CSEWorkList;
2702   CSEWorkList.reserve(CSEBlocks.size());
2703   for (BasicBlock *BB : CSEBlocks)
2704     if (DomTreeNode *N = DT->getNode(BB)) {
2705       assert(DT->isReachableFromEntry(N));
2706       CSEWorkList.push_back(N);
2707     }
2708
2709   // Sort blocks by domination. This ensures we visit a block after all blocks
2710   // dominating it are visited.
2711   std::stable_sort(CSEWorkList.begin(), CSEWorkList.end(),
2712                    [this](const DomTreeNode *A, const DomTreeNode *B) {
2713     return DT->properlyDominates(A, B);
2714   });
2715
2716   // Perform O(N^2) search over the gather sequences and merge identical
2717   // instructions. TODO: We can further optimize this scan if we split the
2718   // instructions into different buckets based on the insert lane.
2719   SmallVector<Instruction *, 16> Visited;
2720   for (auto I = CSEWorkList.begin(), E = CSEWorkList.end(); I != E; ++I) {
2721     assert((I == CSEWorkList.begin() || !DT->dominates(*I, *std::prev(I))) &&
2722            "Worklist not sorted properly!");
2723     BasicBlock *BB = (*I)->getBlock();
2724     // For all instructions in blocks containing gather sequences:
2725     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e;) {
2726       Instruction *In = &*it++;
2727       if (!isa<InsertElementInst>(In) && !isa<ExtractElementInst>(In))
2728         continue;
2729
2730       // Check if we can replace this instruction with any of the
2731       // visited instructions.
2732       for (SmallVectorImpl<Instruction *>::iterator v = Visited.begin(),
2733                                                     ve = Visited.end();
2734            v != ve; ++v) {
2735         if (In->isIdenticalTo(*v) &&
2736             DT->dominates((*v)->getParent(), In->getParent())) {
2737           In->replaceAllUsesWith(*v);
2738           eraseInstruction(In);
2739           In = nullptr;
2740           break;
2741         }
2742       }
2743       if (In) {
2744         assert(std::find(Visited.begin(), Visited.end(), In) == Visited.end());
2745         Visited.push_back(In);
2746       }
2747     }
2748   }
2749   CSEBlocks.clear();
2750   GatherSeq.clear();
2751 }
2752
2753 // Groups the instructions to a bundle (which is then a single scheduling entity)
2754 // and schedules instructions until the bundle gets ready.
2755 bool BoUpSLP::BlockScheduling::tryScheduleBundle(ArrayRef<Value *> VL,
2756                                                  BoUpSLP *SLP) {
2757   if (isa<PHINode>(VL[0]))
2758     return true;
2759
2760   // Initialize the instruction bundle.
2761   Instruction *OldScheduleEnd = ScheduleEnd;
2762   ScheduleData *PrevInBundle = nullptr;
2763   ScheduleData *Bundle = nullptr;
2764   bool ReSchedule = false;
2765   DEBUG(dbgs() << "SLP:  bundle: " << *VL[0] << "\n");
2766
2767   // Make sure that the scheduling region contains all
2768   // instructions of the bundle.
2769   for (Value *V : VL) {
2770     if (!extendSchedulingRegion(V))
2771       return false;
2772   }
2773
2774   for (Value *V : VL) {
2775     ScheduleData *BundleMember = getScheduleData(V);
2776     assert(BundleMember &&
2777            "no ScheduleData for bundle member (maybe not in same basic block)");
2778     if (BundleMember->IsScheduled) {
2779       // A bundle member was scheduled as single instruction before and now
2780       // needs to be scheduled as part of the bundle. We just get rid of the
2781       // existing schedule.
2782       DEBUG(dbgs() << "SLP:  reset schedule because " << *BundleMember
2783                    << " was already scheduled\n");
2784       ReSchedule = true;
2785     }
2786     assert(BundleMember->isSchedulingEntity() &&
2787            "bundle member already part of other bundle");
2788     if (PrevInBundle) {
2789       PrevInBundle->NextInBundle = BundleMember;
2790     } else {
2791       Bundle = BundleMember;
2792     }
2793     BundleMember->UnscheduledDepsInBundle = 0;
2794     Bundle->UnscheduledDepsInBundle += BundleMember->UnscheduledDeps;
2795
2796     // Group the instructions to a bundle.
2797     BundleMember->FirstInBundle = Bundle;
2798     PrevInBundle = BundleMember;
2799   }
2800   if (ScheduleEnd != OldScheduleEnd) {
2801     // The scheduling region got new instructions at the lower end (or it is a
2802     // new region for the first bundle). This makes it necessary to
2803     // recalculate all dependencies.
2804     // It is seldom that this needs to be done a second time after adding the
2805     // initial bundle to the region.
2806     for (auto *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) {
2807       ScheduleData *SD = getScheduleData(I);
2808       SD->clearDependencies();
2809     }
2810     ReSchedule = true;
2811   }
2812   if (ReSchedule) {
2813     resetSchedule();
2814     initialFillReadyList(ReadyInsts);
2815   }
2816
2817   DEBUG(dbgs() << "SLP: try schedule bundle " << *Bundle << " in block "
2818                << BB->getName() << "\n");
2819
2820   calculateDependencies(Bundle, true, SLP);
2821
2822   // Now try to schedule the new bundle. As soon as the bundle is "ready" it
2823   // means that there are no cyclic dependencies and we can schedule it.
2824   // Note that's important that we don't "schedule" the bundle yet (see
2825   // cancelScheduling).
2826   while (!Bundle->isReady() && !ReadyInsts.empty()) {
2827
2828     ScheduleData *pickedSD = ReadyInsts.back();
2829     ReadyInsts.pop_back();
2830
2831     if (pickedSD->isSchedulingEntity() && pickedSD->isReady()) {
2832       schedule(pickedSD, ReadyInsts);
2833     }
2834   }
2835   if (!Bundle->isReady()) {
2836     cancelScheduling(VL);
2837     return false;
2838   }
2839   return true;
2840 }
2841
2842 void BoUpSLP::BlockScheduling::cancelScheduling(ArrayRef<Value *> VL) {
2843   if (isa<PHINode>(VL[0]))
2844     return;
2845
2846   ScheduleData *Bundle = getScheduleData(VL[0]);
2847   DEBUG(dbgs() << "SLP:  cancel scheduling of " << *Bundle << "\n");
2848   assert(!Bundle->IsScheduled &&
2849          "Can't cancel bundle which is already scheduled");
2850   assert(Bundle->isSchedulingEntity() && Bundle->isPartOfBundle() &&
2851          "tried to unbundle something which is not a bundle");
2852
2853   // Un-bundle: make single instructions out of the bundle.
2854   ScheduleData *BundleMember = Bundle;
2855   while (BundleMember) {
2856     assert(BundleMember->FirstInBundle == Bundle && "corrupt bundle links");
2857     BundleMember->FirstInBundle = BundleMember;
2858     ScheduleData *Next = BundleMember->NextInBundle;
2859     BundleMember->NextInBundle = nullptr;
2860     BundleMember->UnscheduledDepsInBundle = BundleMember->UnscheduledDeps;
2861     if (BundleMember->UnscheduledDepsInBundle == 0) {
2862       ReadyInsts.insert(BundleMember);
2863     }
2864     BundleMember = Next;
2865   }
2866 }
2867
2868 bool BoUpSLP::BlockScheduling::extendSchedulingRegion(Value *V) {
2869   if (getScheduleData(V))
2870     return true;
2871   Instruction *I = dyn_cast<Instruction>(V);
2872   assert(I && "bundle member must be an instruction");
2873   assert(!isa<PHINode>(I) && "phi nodes don't need to be scheduled");
2874   if (!ScheduleStart) {
2875     // It's the first instruction in the new region.
2876     initScheduleData(I, I->getNextNode(), nullptr, nullptr);
2877     ScheduleStart = I;
2878     ScheduleEnd = I->getNextNode();
2879     assert(ScheduleEnd && "tried to vectorize a TerminatorInst?");
2880     DEBUG(dbgs() << "SLP:  initialize schedule region to " << *I << "\n");
2881     return true;
2882   }
2883   // Search up and down at the same time, because we don't know if the new
2884   // instruction is above or below the existing scheduling region.
2885   BasicBlock::reverse_iterator UpIter(ScheduleStart->getIterator());
2886   BasicBlock::reverse_iterator UpperEnd = BB->rend();
2887   BasicBlock::iterator DownIter(ScheduleEnd);
2888   BasicBlock::iterator LowerEnd = BB->end();
2889   for (;;) {
2890     if (++ScheduleRegionSize > ScheduleRegionSizeLimit) {
2891       DEBUG(dbgs() << "SLP:  exceeded schedule region size limit\n");
2892       return false;
2893     }
2894
2895     if (UpIter != UpperEnd) {
2896       if (&*UpIter == I) {
2897         initScheduleData(I, ScheduleStart, nullptr, FirstLoadStoreInRegion);
2898         ScheduleStart = I;
2899         DEBUG(dbgs() << "SLP:  extend schedule region start to " << *I << "\n");
2900         return true;
2901       }
2902       UpIter++;
2903     }
2904     if (DownIter != LowerEnd) {
2905       if (&*DownIter == I) {
2906         initScheduleData(ScheduleEnd, I->getNextNode(), LastLoadStoreInRegion,
2907                          nullptr);
2908         ScheduleEnd = I->getNextNode();
2909         assert(ScheduleEnd && "tried to vectorize a TerminatorInst?");
2910         DEBUG(dbgs() << "SLP:  extend schedule region end to " << *I << "\n");
2911         return true;
2912       }
2913       DownIter++;
2914     }
2915     assert((UpIter != UpperEnd || DownIter != LowerEnd) &&
2916            "instruction not found in block");
2917   }
2918   return true;
2919 }
2920
2921 void BoUpSLP::BlockScheduling::initScheduleData(Instruction *FromI,
2922                                                 Instruction *ToI,
2923                                                 ScheduleData *PrevLoadStore,
2924                                                 ScheduleData *NextLoadStore) {
2925   ScheduleData *CurrentLoadStore = PrevLoadStore;
2926   for (Instruction *I = FromI; I != ToI; I = I->getNextNode()) {
2927     ScheduleData *SD = ScheduleDataMap[I];
2928     if (!SD) {
2929       // Allocate a new ScheduleData for the instruction.
2930       if (ChunkPos >= ChunkSize) {
2931         ScheduleDataChunks.push_back(
2932             llvm::make_unique<ScheduleData[]>(ChunkSize));
2933         ChunkPos = 0;
2934       }
2935       SD = &(ScheduleDataChunks.back()[ChunkPos++]);
2936       ScheduleDataMap[I] = SD;
2937       SD->Inst = I;
2938     }
2939     assert(!isInSchedulingRegion(SD) &&
2940            "new ScheduleData already in scheduling region");
2941     SD->init(SchedulingRegionID);
2942
2943     if (I->mayReadOrWriteMemory()) {
2944       // Update the linked list of memory accessing instructions.
2945       if (CurrentLoadStore) {
2946         CurrentLoadStore->NextLoadStore = SD;
2947       } else {
2948         FirstLoadStoreInRegion = SD;
2949       }
2950       CurrentLoadStore = SD;
2951     }
2952   }
2953   if (NextLoadStore) {
2954     if (CurrentLoadStore)
2955       CurrentLoadStore->NextLoadStore = NextLoadStore;
2956   } else {
2957     LastLoadStoreInRegion = CurrentLoadStore;
2958   }
2959 }
2960
2961 void BoUpSLP::BlockScheduling::calculateDependencies(ScheduleData *SD,
2962                                                      bool InsertInReadyList,
2963                                                      BoUpSLP *SLP) {
2964   assert(SD->isSchedulingEntity());
2965
2966   SmallVector<ScheduleData *, 10> WorkList;
2967   WorkList.push_back(SD);
2968
2969   while (!WorkList.empty()) {
2970     ScheduleData *SD = WorkList.back();
2971     WorkList.pop_back();
2972
2973     ScheduleData *BundleMember = SD;
2974     while (BundleMember) {
2975       assert(isInSchedulingRegion(BundleMember));
2976       if (!BundleMember->hasValidDependencies()) {
2977
2978         DEBUG(dbgs() << "SLP:       update deps of " << *BundleMember << "\n");
2979         BundleMember->Dependencies = 0;
2980         BundleMember->resetUnscheduledDeps();
2981
2982         // Handle def-use chain dependencies.
2983         for (User *U : BundleMember->Inst->users()) {
2984           if (isa<Instruction>(U)) {
2985             ScheduleData *UseSD = getScheduleData(U);
2986             if (UseSD && isInSchedulingRegion(UseSD->FirstInBundle)) {
2987               BundleMember->Dependencies++;
2988               ScheduleData *DestBundle = UseSD->FirstInBundle;
2989               if (!DestBundle->IsScheduled) {
2990                 BundleMember->incrementUnscheduledDeps(1);
2991               }
2992               if (!DestBundle->hasValidDependencies()) {
2993                 WorkList.push_back(DestBundle);
2994               }
2995             }
2996           } else {
2997             // I'm not sure if this can ever happen. But we need to be safe.
2998             // This lets the instruction/bundle never be scheduled and
2999             // eventually disable vectorization.
3000             BundleMember->Dependencies++;
3001             BundleMember->incrementUnscheduledDeps(1);
3002           }
3003         }
3004
3005         // Handle the memory dependencies.
3006         ScheduleData *DepDest = BundleMember->NextLoadStore;
3007         if (DepDest) {
3008           Instruction *SrcInst = BundleMember->Inst;
3009           MemoryLocation SrcLoc = getLocation(SrcInst, SLP->AA);
3010           bool SrcMayWrite = BundleMember->Inst->mayWriteToMemory();
3011           unsigned numAliased = 0;
3012           unsigned DistToSrc = 1;
3013
3014           while (DepDest) {
3015             assert(isInSchedulingRegion(DepDest));
3016
3017             // We have two limits to reduce the complexity:
3018             // 1) AliasedCheckLimit: It's a small limit to reduce calls to
3019             //    SLP->isAliased (which is the expensive part in this loop).
3020             // 2) MaxMemDepDistance: It's for very large blocks and it aborts
3021             //    the whole loop (even if the loop is fast, it's quadratic).
3022             //    It's important for the loop break condition (see below) to
3023             //    check this limit even between two read-only instructions.
3024             if (DistToSrc >= MaxMemDepDistance ||
3025                     ((SrcMayWrite || DepDest->Inst->mayWriteToMemory()) &&
3026                      (numAliased >= AliasedCheckLimit ||
3027                       SLP->isAliased(SrcLoc, SrcInst, DepDest->Inst)))) {
3028
3029               // We increment the counter only if the locations are aliased
3030               // (instead of counting all alias checks). This gives a better
3031               // balance between reduced runtime and accurate dependencies.
3032               numAliased++;
3033
3034               DepDest->MemoryDependencies.push_back(BundleMember);
3035               BundleMember->Dependencies++;
3036               ScheduleData *DestBundle = DepDest->FirstInBundle;
3037               if (!DestBundle->IsScheduled) {
3038                 BundleMember->incrementUnscheduledDeps(1);
3039               }
3040               if (!DestBundle->hasValidDependencies()) {
3041                 WorkList.push_back(DestBundle);
3042               }
3043             }
3044             DepDest = DepDest->NextLoadStore;
3045
3046             // Example, explaining the loop break condition: Let's assume our
3047             // starting instruction is i0 and MaxMemDepDistance = 3.
3048             //
3049             //                      +--------v--v--v
3050             //             i0,i1,i2,i3,i4,i5,i6,i7,i8
3051             //             +--------^--^--^
3052             //
3053             // MaxMemDepDistance let us stop alias-checking at i3 and we add
3054             // dependencies from i0 to i3,i4,.. (even if they are not aliased).
3055             // Previously we already added dependencies from i3 to i6,i7,i8
3056             // (because of MaxMemDepDistance). As we added a dependency from
3057             // i0 to i3, we have transitive dependencies from i0 to i6,i7,i8
3058             // and we can abort this loop at i6.
3059             if (DistToSrc >= 2 * MaxMemDepDistance)
3060                 break;
3061             DistToSrc++;
3062           }
3063         }
3064       }
3065       BundleMember = BundleMember->NextInBundle;
3066     }
3067     if (InsertInReadyList && SD->isReady()) {
3068       ReadyInsts.push_back(SD);
3069       DEBUG(dbgs() << "SLP:     gets ready on update: " << *SD->Inst << "\n");
3070     }
3071   }
3072 }
3073
3074 void BoUpSLP::BlockScheduling::resetSchedule() {
3075   assert(ScheduleStart &&
3076          "tried to reset schedule on block which has not been scheduled");
3077   for (Instruction *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) {
3078     ScheduleData *SD = getScheduleData(I);
3079     assert(isInSchedulingRegion(SD));
3080     SD->IsScheduled = false;
3081     SD->resetUnscheduledDeps();
3082   }
3083   ReadyInsts.clear();
3084 }
3085
3086 void BoUpSLP::scheduleBlock(BlockScheduling *BS) {
3087   
3088   if (!BS->ScheduleStart)
3089     return;
3090   
3091   DEBUG(dbgs() << "SLP: schedule block " << BS->BB->getName() << "\n");
3092
3093   BS->resetSchedule();
3094
3095   // For the real scheduling we use a more sophisticated ready-list: it is
3096   // sorted by the original instruction location. This lets the final schedule
3097   // be as  close as possible to the original instruction order.
3098   struct ScheduleDataCompare {
3099     bool operator()(ScheduleData *SD1, ScheduleData *SD2) {
3100       return SD2->SchedulingPriority < SD1->SchedulingPriority;
3101     }
3102   };
3103   std::set<ScheduleData *, ScheduleDataCompare> ReadyInsts;
3104
3105   // Ensure that all dependency data is updated and fill the ready-list with
3106   // initial instructions.
3107   int Idx = 0;
3108   int NumToSchedule = 0;
3109   for (auto *I = BS->ScheduleStart; I != BS->ScheduleEnd;
3110        I = I->getNextNode()) {
3111     ScheduleData *SD = BS->getScheduleData(I);
3112     assert(
3113         SD->isPartOfBundle() == (ScalarToTreeEntry.count(SD->Inst) != 0) &&
3114         "scheduler and vectorizer have different opinion on what is a bundle");
3115     SD->FirstInBundle->SchedulingPriority = Idx++;
3116     if (SD->isSchedulingEntity()) {
3117       BS->calculateDependencies(SD, false, this);
3118       NumToSchedule++;
3119     }
3120   }
3121   BS->initialFillReadyList(ReadyInsts);
3122
3123   Instruction *LastScheduledInst = BS->ScheduleEnd;
3124
3125   // Do the "real" scheduling.
3126   while (!ReadyInsts.empty()) {
3127     ScheduleData *picked = *ReadyInsts.begin();
3128     ReadyInsts.erase(ReadyInsts.begin());
3129
3130     // Move the scheduled instruction(s) to their dedicated places, if not
3131     // there yet.
3132     ScheduleData *BundleMember = picked;
3133     while (BundleMember) {
3134       Instruction *pickedInst = BundleMember->Inst;
3135       if (LastScheduledInst->getNextNode() != pickedInst) {
3136         BS->BB->getInstList().remove(pickedInst);
3137         BS->BB->getInstList().insert(LastScheduledInst->getIterator(),
3138                                      pickedInst);
3139       }
3140       LastScheduledInst = pickedInst;
3141       BundleMember = BundleMember->NextInBundle;
3142     }
3143
3144     BS->schedule(picked, ReadyInsts);
3145     NumToSchedule--;
3146   }
3147   assert(NumToSchedule == 0 && "could not schedule all instructions");
3148
3149   // Avoid duplicate scheduling of the block.
3150   BS->ScheduleStart = nullptr;
3151 }
3152
3153 /// The SLPVectorizer Pass.
3154 struct SLPVectorizer : public FunctionPass {
3155   typedef SmallVector<StoreInst *, 8> StoreList;
3156   typedef MapVector<Value *, StoreList> StoreListMap;
3157
3158   /// Pass identification, replacement for typeid
3159   static char ID;
3160
3161   explicit SLPVectorizer() : FunctionPass(ID) {
3162     initializeSLPVectorizerPass(*PassRegistry::getPassRegistry());
3163   }
3164
3165   ScalarEvolution *SE;
3166   TargetTransformInfo *TTI;
3167   TargetLibraryInfo *TLI;
3168   AliasAnalysis *AA;
3169   LoopInfo *LI;
3170   DominatorTree *DT;
3171   AssumptionCache *AC;
3172
3173   bool runOnFunction(Function &F) override {
3174     if (skipOptnoneFunction(F))
3175       return false;
3176
3177     SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
3178     TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
3179     auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
3180     TLI = TLIP ? &TLIP->getTLI() : nullptr;
3181     AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
3182     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
3183     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
3184     AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
3185
3186     StoreRefs.clear();
3187     bool Changed = false;
3188
3189     // If the target claims to have no vector registers don't attempt
3190     // vectorization.
3191     if (!TTI->getNumberOfRegisters(true))
3192       return false;
3193
3194     // Use the vector register size specified by the target unless overridden
3195     // by a command-line option.
3196     // TODO: It would be better to limit the vectorization factor based on
3197     //       data type rather than just register size. For example, x86 AVX has
3198     //       256-bit registers, but it does not support integer operations
3199     //       at that width (that requires AVX2).
3200     if (MaxVectorRegSizeOption.getNumOccurrences())
3201       MaxVecRegSize = MaxVectorRegSizeOption;
3202     else
3203       MaxVecRegSize = TTI->getRegisterBitWidth(true);
3204
3205     // Don't vectorize when the attribute NoImplicitFloat is used.
3206     if (F.hasFnAttribute(Attribute::NoImplicitFloat))
3207       return false;
3208
3209     DEBUG(dbgs() << "SLP: Analyzing blocks in " << F.getName() << ".\n");
3210
3211     // Use the bottom up slp vectorizer to construct chains that start with
3212     // store instructions.
3213     BoUpSLP R(&F, SE, TTI, TLI, AA, LI, DT, AC);
3214
3215     // A general note: the vectorizer must use BoUpSLP::eraseInstruction() to
3216     // delete instructions.
3217
3218     // Scan the blocks in the function in post order.
3219     for (auto BB : post_order(&F.getEntryBlock())) {
3220       // Vectorize trees that end at stores.
3221       if (unsigned count = collectStores(BB, R)) {
3222         (void)count;
3223         DEBUG(dbgs() << "SLP: Found " << count << " stores to vectorize.\n");
3224         Changed |= vectorizeStoreChains(R);
3225       }
3226
3227       // Vectorize trees that end at reductions.
3228       Changed |= vectorizeChainsInBlock(BB, R);
3229     }
3230
3231     if (Changed) {
3232       R.optimizeGatherSequence();
3233       DEBUG(dbgs() << "SLP: vectorized \"" << F.getName() << "\"\n");
3234       DEBUG(verifyFunction(F));
3235     }
3236     return Changed;
3237   }
3238
3239   void getAnalysisUsage(AnalysisUsage &AU) const override {
3240     FunctionPass::getAnalysisUsage(AU);
3241     AU.addRequired<AssumptionCacheTracker>();
3242     AU.addRequired<ScalarEvolutionWrapperPass>();
3243     AU.addRequired<AAResultsWrapperPass>();
3244     AU.addRequired<TargetTransformInfoWrapperPass>();
3245     AU.addRequired<LoopInfoWrapperPass>();
3246     AU.addRequired<DominatorTreeWrapperPass>();
3247     AU.addPreserved<LoopInfoWrapperPass>();
3248     AU.addPreserved<DominatorTreeWrapperPass>();
3249     AU.setPreservesCFG();
3250   }
3251
3252 private:
3253
3254   /// \brief Collect memory references and sort them according to their base
3255   /// object. We sort the stores to their base objects to reduce the cost of the
3256   /// quadratic search on the stores. TODO: We can further reduce this cost
3257   /// if we flush the chain creation every time we run into a memory barrier.
3258   unsigned collectStores(BasicBlock *BB, BoUpSLP &R);
3259
3260   /// \brief Try to vectorize a chain that starts at two arithmetic instrs.
3261   bool tryToVectorizePair(Value *A, Value *B, BoUpSLP &R);
3262
3263   /// \brief Try to vectorize a list of operands.
3264   /// \@param BuildVector A list of users to ignore for the purpose of
3265   ///                     scheduling and that don't need extracting.
3266   /// \returns true if a value was vectorized.
3267   bool tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R,
3268                           ArrayRef<Value *> BuildVector = None,
3269                           bool allowReorder = false);
3270
3271   /// \brief Try to vectorize a chain that may start at the operands of \V;
3272   bool tryToVectorize(BinaryOperator *V, BoUpSLP &R);
3273
3274   /// \brief Vectorize the stores that were collected in StoreRefs.
3275   bool vectorizeStoreChains(BoUpSLP &R);
3276
3277   /// \brief Scan the basic block and look for patterns that are likely to start
3278   /// a vectorization chain.
3279   bool vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R);
3280
3281   bool vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold,
3282                            BoUpSLP &R, unsigned VecRegSize);
3283
3284   bool vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold,
3285                        BoUpSLP &R);
3286 private:
3287   StoreListMap StoreRefs;
3288   unsigned MaxVecRegSize; // This is set by TTI or overridden by cl::opt.
3289 };
3290
3291 /// \brief Check that the Values in the slice in VL array are still existent in
3292 /// the WeakVH array.
3293 /// Vectorization of part of the VL array may cause later values in the VL array
3294 /// to become invalid. We track when this has happened in the WeakVH array.
3295 static bool hasValueBeenRAUWed(ArrayRef<Value *> VL, ArrayRef<WeakVH> VH,
3296                                unsigned SliceBegin, unsigned SliceSize) {
3297   VL = VL.slice(SliceBegin, SliceSize);
3298   VH = VH.slice(SliceBegin, SliceSize);
3299   return !std::equal(VL.begin(), VL.end(), VH.begin());
3300 }
3301
3302 bool SLPVectorizer::vectorizeStoreChain(ArrayRef<Value *> Chain,
3303                                         int CostThreshold, BoUpSLP &R,
3304                                         unsigned VecRegSize) {
3305   unsigned ChainLen = Chain.size();
3306   DEBUG(dbgs() << "SLP: Analyzing a store chain of length " << ChainLen
3307         << "\n");
3308   Type *StoreTy = cast<StoreInst>(Chain[0])->getValueOperand()->getType();
3309   auto &DL = cast<StoreInst>(Chain[0])->getModule()->getDataLayout();
3310   unsigned Sz = DL.getTypeSizeInBits(StoreTy);
3311   unsigned VF = VecRegSize / Sz;
3312
3313   if (!isPowerOf2_32(Sz) || VF < 2)
3314     return false;
3315
3316   // Keep track of values that were deleted by vectorizing in the loop below.
3317   SmallVector<WeakVH, 8> TrackValues(Chain.begin(), Chain.end());
3318
3319   bool Changed = false;
3320   // Look for profitable vectorizable trees at all offsets, starting at zero.
3321   for (unsigned i = 0, e = ChainLen; i < e; ++i) {
3322     if (i + VF > e)
3323       break;
3324
3325     // Check that a previous iteration of this loop did not delete the Value.
3326     if (hasValueBeenRAUWed(Chain, TrackValues, i, VF))
3327       continue;
3328
3329     DEBUG(dbgs() << "SLP: Analyzing " << VF << " stores at offset " << i
3330           << "\n");
3331     ArrayRef<Value *> Operands = Chain.slice(i, VF);
3332
3333     R.buildTree(Operands);
3334
3335     int Cost = R.getTreeCost();
3336
3337     DEBUG(dbgs() << "SLP: Found cost=" << Cost << " for VF=" << VF << "\n");
3338     if (Cost < CostThreshold) {
3339       DEBUG(dbgs() << "SLP: Decided to vectorize cost=" << Cost << "\n");
3340       R.vectorizeTree();
3341
3342       // Move to the next bundle.
3343       i += VF - 1;
3344       Changed = true;
3345     }
3346   }
3347
3348   return Changed;
3349 }
3350
3351 bool SLPVectorizer::vectorizeStores(ArrayRef<StoreInst *> Stores,
3352                                     int costThreshold, BoUpSLP &R) {
3353   SetVector<StoreInst *> Heads, Tails;
3354   SmallDenseMap<StoreInst *, StoreInst *> ConsecutiveChain;
3355
3356   // We may run into multiple chains that merge into a single chain. We mark the
3357   // stores that we vectorized so that we don't visit the same store twice.
3358   BoUpSLP::ValueSet VectorizedStores;
3359   bool Changed = false;
3360
3361   // Do a quadratic search on all of the given stores and find
3362   // all of the pairs of stores that follow each other.
3363   SmallVector<unsigned, 16> IndexQueue;
3364   for (unsigned i = 0, e = Stores.size(); i < e; ++i) {
3365     const DataLayout &DL = Stores[i]->getModule()->getDataLayout();
3366     IndexQueue.clear();
3367     // If a store has multiple consecutive store candidates, search Stores
3368     // array according to the sequence: from i+1 to e, then from i-1 to 0.
3369     // This is because usually pairing with immediate succeeding or preceding
3370     // candidate create the best chance to find slp vectorization opportunity.
3371     unsigned j = 0;
3372     for (j = i + 1; j < e; ++j)
3373       IndexQueue.push_back(j);
3374     for (j = i; j > 0; --j)
3375       IndexQueue.push_back(j - 1);
3376
3377     for (auto &k : IndexQueue) {
3378       if (R.isConsecutiveAccess(Stores[i], Stores[k], DL)) {
3379         Tails.insert(Stores[k]);
3380         Heads.insert(Stores[i]);
3381         ConsecutiveChain[Stores[i]] = Stores[k];
3382         break;
3383       }
3384     }
3385   }
3386
3387   // For stores that start but don't end a link in the chain:
3388   for (SetVector<StoreInst *>::iterator it = Heads.begin(), e = Heads.end();
3389        it != e; ++it) {
3390     if (Tails.count(*it))
3391       continue;
3392
3393     // We found a store instr that starts a chain. Now follow the chain and try
3394     // to vectorize it.
3395     BoUpSLP::ValueList Operands;
3396     StoreInst *I = *it;
3397     // Collect the chain into a list.
3398     while (Tails.count(I) || Heads.count(I)) {
3399       if (VectorizedStores.count(I))
3400         break;
3401       Operands.push_back(I);
3402       // Move to the next value in the chain.
3403       I = ConsecutiveChain[I];
3404     }
3405
3406     // FIXME: Is division-by-2 the correct step? Should we assert that the
3407     // register size is a power-of-2?
3408     for (unsigned Size = MaxVecRegSize; Size >= MinVecRegSize; Size /= 2) {
3409       if (vectorizeStoreChain(Operands, costThreshold, R, Size)) {
3410         // Mark the vectorized stores so that we don't vectorize them again.
3411         VectorizedStores.insert(Operands.begin(), Operands.end());
3412         Changed = true;
3413         break;
3414       }
3415     }
3416   }
3417
3418   return Changed;
3419 }
3420
3421
3422 unsigned SLPVectorizer::collectStores(BasicBlock *BB, BoUpSLP &R) {
3423   unsigned count = 0;
3424   StoreRefs.clear();
3425   const DataLayout &DL = BB->getModule()->getDataLayout();
3426   for (Instruction &I : *BB) {
3427     StoreInst *SI = dyn_cast<StoreInst>(&I);
3428     if (!SI)
3429       continue;
3430
3431     // Don't touch volatile stores.
3432     if (!SI->isSimple())
3433       continue;
3434
3435     // Check that the pointer points to scalars.
3436     Type *Ty = SI->getValueOperand()->getType();
3437     if (!isValidElementType(Ty))
3438       continue;
3439
3440     // Find the base pointer.
3441     Value *Ptr = GetUnderlyingObject(SI->getPointerOperand(), DL);
3442
3443     // Save the store locations.
3444     StoreRefs[Ptr].push_back(SI);
3445     count++;
3446   }
3447   return count;
3448 }
3449
3450 bool SLPVectorizer::tryToVectorizePair(Value *A, Value *B, BoUpSLP &R) {
3451   if (!A || !B)
3452     return false;
3453   Value *VL[] = { A, B };
3454   return tryToVectorizeList(VL, R, None, true);
3455 }
3456
3457 bool SLPVectorizer::tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R,
3458                                        ArrayRef<Value *> BuildVector,
3459                                        bool allowReorder) {
3460   if (VL.size() < 2)
3461     return false;
3462
3463   DEBUG(dbgs() << "SLP: Vectorizing a list of length = " << VL.size() << ".\n");
3464
3465   // Check that all of the parts are scalar instructions of the same type.
3466   Instruction *I0 = dyn_cast<Instruction>(VL[0]);
3467   if (!I0)
3468     return false;
3469
3470   unsigned Opcode0 = I0->getOpcode();
3471   const DataLayout &DL = I0->getModule()->getDataLayout();
3472
3473   Type *Ty0 = I0->getType();
3474   unsigned Sz = DL.getTypeSizeInBits(Ty0);
3475   // FIXME: Register size should be a parameter to this function, so we can
3476   // try different vectorization factors.
3477   unsigned VF = MinVecRegSize / Sz;
3478
3479   for (Value *V : VL) {
3480     Type *Ty = V->getType();
3481     if (!isValidElementType(Ty))
3482       return false;
3483     Instruction *Inst = dyn_cast<Instruction>(V);
3484     if (!Inst || Inst->getOpcode() != Opcode0)
3485       return false;
3486   }
3487
3488   bool Changed = false;
3489
3490   // Keep track of values that were deleted by vectorizing in the loop below.
3491   SmallVector<WeakVH, 8> TrackValues(VL.begin(), VL.end());
3492
3493   for (unsigned i = 0, e = VL.size(); i < e; ++i) {
3494     unsigned OpsWidth = 0;
3495
3496     if (i + VF > e)
3497       OpsWidth = e - i;
3498     else
3499       OpsWidth = VF;
3500
3501     if (!isPowerOf2_32(OpsWidth) || OpsWidth < 2)
3502       break;
3503
3504     // Check that a previous iteration of this loop did not delete the Value.
3505     if (hasValueBeenRAUWed(VL, TrackValues, i, OpsWidth))
3506       continue;
3507
3508     DEBUG(dbgs() << "SLP: Analyzing " << OpsWidth << " operations "
3509                  << "\n");
3510     ArrayRef<Value *> Ops = VL.slice(i, OpsWidth);
3511
3512     ArrayRef<Value *> BuildVectorSlice;
3513     if (!BuildVector.empty())
3514       BuildVectorSlice = BuildVector.slice(i, OpsWidth);
3515
3516     R.buildTree(Ops, BuildVectorSlice);
3517     // TODO: check if we can allow reordering also for other cases than
3518     // tryToVectorizePair()
3519     if (allowReorder && R.shouldReorder()) {
3520       assert(Ops.size() == 2);
3521       assert(BuildVectorSlice.empty());
3522       Value *ReorderedOps[] = { Ops[1], Ops[0] };
3523       R.buildTree(ReorderedOps, None);
3524     }
3525     int Cost = R.getTreeCost();
3526
3527     if (Cost < -SLPCostThreshold) {
3528       DEBUG(dbgs() << "SLP: Vectorizing list at cost:" << Cost << ".\n");
3529       Value *VectorizedRoot = R.vectorizeTree();
3530
3531       // Reconstruct the build vector by extracting the vectorized root. This
3532       // way we handle the case where some elements of the vector are undefined.
3533       //  (return (inserelt <4 xi32> (insertelt undef (opd0) 0) (opd1) 2))
3534       if (!BuildVectorSlice.empty()) {
3535         // The insert point is the last build vector instruction. The vectorized
3536         // root will precede it. This guarantees that we get an instruction. The
3537         // vectorized tree could have been constant folded.
3538         Instruction *InsertAfter = cast<Instruction>(BuildVectorSlice.back());
3539         unsigned VecIdx = 0;
3540         for (auto &V : BuildVectorSlice) {
3541           IRBuilder<true, NoFolder> Builder(
3542               InsertAfter->getParent(), ++BasicBlock::iterator(InsertAfter));
3543           InsertElementInst *IE = cast<InsertElementInst>(V);
3544           Instruction *Extract = cast<Instruction>(Builder.CreateExtractElement(
3545               VectorizedRoot, Builder.getInt32(VecIdx++)));
3546           IE->setOperand(1, Extract);
3547           IE->removeFromParent();
3548           IE->insertAfter(Extract);
3549           InsertAfter = IE;
3550         }
3551       }
3552       // Move to the next bundle.
3553       i += VF - 1;
3554       Changed = true;
3555     }
3556   }
3557
3558   return Changed;
3559 }
3560
3561 bool SLPVectorizer::tryToVectorize(BinaryOperator *V, BoUpSLP &R) {
3562   if (!V)
3563     return false;
3564
3565   // Try to vectorize V.
3566   if (tryToVectorizePair(V->getOperand(0), V->getOperand(1), R))
3567     return true;
3568
3569   BinaryOperator *A = dyn_cast<BinaryOperator>(V->getOperand(0));
3570   BinaryOperator *B = dyn_cast<BinaryOperator>(V->getOperand(1));
3571   // Try to skip B.
3572   if (B && B->hasOneUse()) {
3573     BinaryOperator *B0 = dyn_cast<BinaryOperator>(B->getOperand(0));
3574     BinaryOperator *B1 = dyn_cast<BinaryOperator>(B->getOperand(1));
3575     if (tryToVectorizePair(A, B0, R)) {
3576       return true;
3577     }
3578     if (tryToVectorizePair(A, B1, R)) {
3579       return true;
3580     }
3581   }
3582
3583   // Try to skip A.
3584   if (A && A->hasOneUse()) {
3585     BinaryOperator *A0 = dyn_cast<BinaryOperator>(A->getOperand(0));
3586     BinaryOperator *A1 = dyn_cast<BinaryOperator>(A->getOperand(1));
3587     if (tryToVectorizePair(A0, B, R)) {
3588       return true;
3589     }
3590     if (tryToVectorizePair(A1, B, R)) {
3591       return true;
3592     }
3593   }
3594   return 0;
3595 }
3596
3597 /// \brief Generate a shuffle mask to be used in a reduction tree.
3598 ///
3599 /// \param VecLen The length of the vector to be reduced.
3600 /// \param NumEltsToRdx The number of elements that should be reduced in the
3601 ///        vector.
3602 /// \param IsPairwise Whether the reduction is a pairwise or splitting
3603 ///        reduction. A pairwise reduction will generate a mask of 
3604 ///        <0,2,...> or <1,3,..> while a splitting reduction will generate
3605 ///        <2,3, undef,undef> for a vector of 4 and NumElts = 2.
3606 /// \param IsLeft True will generate a mask of even elements, odd otherwise.
3607 static Value *createRdxShuffleMask(unsigned VecLen, unsigned NumEltsToRdx,
3608                                    bool IsPairwise, bool IsLeft,
3609                                    IRBuilder<> &Builder) {
3610   assert((IsPairwise || !IsLeft) && "Don't support a <0,1,undef,...> mask");
3611
3612   SmallVector<Constant *, 32> ShuffleMask(
3613       VecLen, UndefValue::get(Builder.getInt32Ty()));
3614
3615   if (IsPairwise)
3616     // Build a mask of 0, 2, ... (left) or 1, 3, ... (right).
3617     for (unsigned i = 0; i != NumEltsToRdx; ++i)
3618       ShuffleMask[i] = Builder.getInt32(2 * i + !IsLeft);
3619   else
3620     // Move the upper half of the vector to the lower half.
3621     for (unsigned i = 0; i != NumEltsToRdx; ++i)
3622       ShuffleMask[i] = Builder.getInt32(NumEltsToRdx + i);
3623
3624   return ConstantVector::get(ShuffleMask);
3625 }
3626
3627
3628 /// Model horizontal reductions.
3629 ///
3630 /// A horizontal reduction is a tree of reduction operations (currently add and
3631 /// fadd) that has operations that can be put into a vector as its leaf.
3632 /// For example, this tree:
3633 ///
3634 /// mul mul mul mul
3635 ///  \  /    \  /
3636 ///   +       +
3637 ///    \     /
3638 ///       +
3639 /// This tree has "mul" as its reduced values and "+" as its reduction
3640 /// operations. A reduction might be feeding into a store or a binary operation
3641 /// feeding a phi.
3642 ///    ...
3643 ///    \  /
3644 ///     +
3645 ///     |
3646 ///  phi +=
3647 ///
3648 ///  Or:
3649 ///    ...
3650 ///    \  /
3651 ///     +
3652 ///     |
3653 ///   *p =
3654 ///
3655 class HorizontalReduction {
3656   SmallVector<Value *, 16> ReductionOps;
3657   SmallVector<Value *, 32> ReducedVals;
3658
3659   BinaryOperator *ReductionRoot;
3660   PHINode *ReductionPHI;
3661
3662   /// The opcode of the reduction.
3663   unsigned ReductionOpcode;
3664   /// The opcode of the values we perform a reduction on.
3665   unsigned ReducedValueOpcode;
3666   /// The width of one full horizontal reduction operation.
3667   unsigned ReduxWidth;
3668   /// Should we model this reduction as a pairwise reduction tree or a tree that
3669   /// splits the vector in halves and adds those halves.
3670   bool IsPairwiseReduction;
3671
3672 public:
3673   HorizontalReduction()
3674     : ReductionRoot(nullptr), ReductionPHI(nullptr), ReductionOpcode(0),
3675     ReducedValueOpcode(0), ReduxWidth(0), IsPairwiseReduction(false) {}
3676
3677   /// \brief Try to find a reduction tree.
3678   bool matchAssociativeReduction(PHINode *Phi, BinaryOperator *B) {
3679     assert((!Phi ||
3680             std::find(Phi->op_begin(), Phi->op_end(), B) != Phi->op_end()) &&
3681            "Thi phi needs to use the binary operator");
3682
3683     // We could have a initial reductions that is not an add.
3684     //  r *= v1 + v2 + v3 + v4
3685     // In such a case start looking for a tree rooted in the first '+'.
3686     if (Phi) {
3687       if (B->getOperand(0) == Phi) {
3688         Phi = nullptr;
3689         B = dyn_cast<BinaryOperator>(B->getOperand(1));
3690       } else if (B->getOperand(1) == Phi) {
3691         Phi = nullptr;
3692         B = dyn_cast<BinaryOperator>(B->getOperand(0));
3693       }
3694     }
3695
3696     if (!B)
3697       return false;
3698
3699     Type *Ty = B->getType();
3700     if (!isValidElementType(Ty))
3701       return false;
3702
3703     const DataLayout &DL = B->getModule()->getDataLayout();
3704     ReductionOpcode = B->getOpcode();
3705     ReducedValueOpcode = 0;
3706     // FIXME: Register size should be a parameter to this function, so we can
3707     // try different vectorization factors.
3708     ReduxWidth = MinVecRegSize / DL.getTypeSizeInBits(Ty);
3709     ReductionRoot = B;
3710     ReductionPHI = Phi;
3711
3712     if (ReduxWidth < 4)
3713       return false;
3714
3715     // We currently only support adds.
3716     if (ReductionOpcode != Instruction::Add &&
3717         ReductionOpcode != Instruction::FAdd)
3718       return false;
3719
3720     // Post order traverse the reduction tree starting at B. We only handle true
3721     // trees containing only binary operators.
3722     SmallVector<std::pair<BinaryOperator *, unsigned>, 32> Stack;
3723     Stack.push_back(std::make_pair(B, 0));
3724     while (!Stack.empty()) {
3725       BinaryOperator *TreeN = Stack.back().first;
3726       unsigned EdgeToVist = Stack.back().second++;
3727       bool IsReducedValue = TreeN->getOpcode() != ReductionOpcode;
3728
3729       // Only handle trees in the current basic block.
3730       if (TreeN->getParent() != B->getParent())
3731         return false;
3732
3733       // Each tree node needs to have one user except for the ultimate
3734       // reduction.
3735       if (!TreeN->hasOneUse() && TreeN != B)
3736         return false;
3737
3738       // Postorder vist.
3739       if (EdgeToVist == 2 || IsReducedValue) {
3740         if (IsReducedValue) {
3741           // Make sure that the opcodes of the operations that we are going to
3742           // reduce match.
3743           if (!ReducedValueOpcode)
3744             ReducedValueOpcode = TreeN->getOpcode();
3745           else if (ReducedValueOpcode != TreeN->getOpcode())
3746             return false;
3747           ReducedVals.push_back(TreeN);
3748         } else {
3749           // We need to be able to reassociate the adds.
3750           if (!TreeN->isAssociative())
3751             return false;
3752           ReductionOps.push_back(TreeN);
3753         }
3754         // Retract.
3755         Stack.pop_back();
3756         continue;
3757       }
3758
3759       // Visit left or right.
3760       Value *NextV = TreeN->getOperand(EdgeToVist);
3761       BinaryOperator *Next = dyn_cast<BinaryOperator>(NextV);
3762       if (Next)
3763         Stack.push_back(std::make_pair(Next, 0));
3764       else if (NextV != Phi)
3765         return false;
3766     }
3767     return true;
3768   }
3769
3770   /// \brief Attempt to vectorize the tree found by
3771   /// matchAssociativeReduction.
3772   bool tryToReduce(BoUpSLP &V, TargetTransformInfo *TTI) {
3773     if (ReducedVals.empty())
3774       return false;
3775
3776     unsigned NumReducedVals = ReducedVals.size();
3777     if (NumReducedVals < ReduxWidth)
3778       return false;
3779
3780     Value *VectorizedTree = nullptr;
3781     IRBuilder<> Builder(ReductionRoot);
3782     FastMathFlags Unsafe;
3783     Unsafe.setUnsafeAlgebra();
3784     Builder.SetFastMathFlags(Unsafe);
3785     unsigned i = 0;
3786
3787     for (; i < NumReducedVals - ReduxWidth + 1; i += ReduxWidth) {
3788       V.buildTree(makeArrayRef(&ReducedVals[i], ReduxWidth), ReductionOps);
3789
3790       // Estimate cost.
3791       int Cost = V.getTreeCost() + getReductionCost(TTI, ReducedVals[i]);
3792       if (Cost >= -SLPCostThreshold)
3793         break;
3794
3795       DEBUG(dbgs() << "SLP: Vectorizing horizontal reduction at cost:" << Cost
3796                    << ". (HorRdx)\n");
3797
3798       // Vectorize a tree.
3799       DebugLoc Loc = cast<Instruction>(ReducedVals[i])->getDebugLoc();
3800       Value *VectorizedRoot = V.vectorizeTree();
3801
3802       // Emit a reduction.
3803       Value *ReducedSubTree = emitReduction(VectorizedRoot, Builder);
3804       if (VectorizedTree) {
3805         Builder.SetCurrentDebugLocation(Loc);
3806         VectorizedTree = createBinOp(Builder, ReductionOpcode, VectorizedTree,
3807                                      ReducedSubTree, "bin.rdx");
3808       } else
3809         VectorizedTree = ReducedSubTree;
3810     }
3811
3812     if (VectorizedTree) {
3813       // Finish the reduction.
3814       for (; i < NumReducedVals; ++i) {
3815         Builder.SetCurrentDebugLocation(
3816           cast<Instruction>(ReducedVals[i])->getDebugLoc());
3817         VectorizedTree = createBinOp(Builder, ReductionOpcode, VectorizedTree,
3818                                      ReducedVals[i]);
3819       }
3820       // Update users.
3821       if (ReductionPHI) {
3822         assert(ReductionRoot && "Need a reduction operation");
3823         ReductionRoot->setOperand(0, VectorizedTree);
3824         ReductionRoot->setOperand(1, ReductionPHI);
3825       } else
3826         ReductionRoot->replaceAllUsesWith(VectorizedTree);
3827     }
3828     return VectorizedTree != nullptr;
3829   }
3830
3831 private:
3832
3833   /// \brief Calculate the cost of a reduction.
3834   int getReductionCost(TargetTransformInfo *TTI, Value *FirstReducedVal) {
3835     Type *ScalarTy = FirstReducedVal->getType();
3836     Type *VecTy = VectorType::get(ScalarTy, ReduxWidth);
3837
3838     int PairwiseRdxCost = TTI->getReductionCost(ReductionOpcode, VecTy, true);
3839     int SplittingRdxCost = TTI->getReductionCost(ReductionOpcode, VecTy, false);
3840
3841     IsPairwiseReduction = PairwiseRdxCost < SplittingRdxCost;
3842     int VecReduxCost = IsPairwiseReduction ? PairwiseRdxCost : SplittingRdxCost;
3843
3844     int ScalarReduxCost =
3845         ReduxWidth * TTI->getArithmeticInstrCost(ReductionOpcode, VecTy);
3846
3847     DEBUG(dbgs() << "SLP: Adding cost " << VecReduxCost - ScalarReduxCost
3848                  << " for reduction that starts with " << *FirstReducedVal
3849                  << " (It is a "
3850                  << (IsPairwiseReduction ? "pairwise" : "splitting")
3851                  << " reduction)\n");
3852
3853     return VecReduxCost - ScalarReduxCost;
3854   }
3855
3856   static Value *createBinOp(IRBuilder<> &Builder, unsigned Opcode, Value *L,
3857                             Value *R, const Twine &Name = "") {
3858     if (Opcode == Instruction::FAdd)
3859       return Builder.CreateFAdd(L, R, Name);
3860     return Builder.CreateBinOp((Instruction::BinaryOps)Opcode, L, R, Name);
3861   }
3862
3863   /// \brief Emit a horizontal reduction of the vectorized value.
3864   Value *emitReduction(Value *VectorizedValue, IRBuilder<> &Builder) {
3865     assert(VectorizedValue && "Need to have a vectorized tree node");
3866     assert(isPowerOf2_32(ReduxWidth) &&
3867            "We only handle power-of-two reductions for now");
3868
3869     Value *TmpVec = VectorizedValue;
3870     for (unsigned i = ReduxWidth / 2; i != 0; i >>= 1) {
3871       if (IsPairwiseReduction) {
3872         Value *LeftMask =
3873           createRdxShuffleMask(ReduxWidth, i, true, true, Builder);
3874         Value *RightMask =
3875           createRdxShuffleMask(ReduxWidth, i, true, false, Builder);
3876
3877         Value *LeftShuf = Builder.CreateShuffleVector(
3878           TmpVec, UndefValue::get(TmpVec->getType()), LeftMask, "rdx.shuf.l");
3879         Value *RightShuf = Builder.CreateShuffleVector(
3880           TmpVec, UndefValue::get(TmpVec->getType()), (RightMask),
3881           "rdx.shuf.r");
3882         TmpVec = createBinOp(Builder, ReductionOpcode, LeftShuf, RightShuf,
3883                              "bin.rdx");
3884       } else {
3885         Value *UpperHalf =
3886           createRdxShuffleMask(ReduxWidth, i, false, false, Builder);
3887         Value *Shuf = Builder.CreateShuffleVector(
3888           TmpVec, UndefValue::get(TmpVec->getType()), UpperHalf, "rdx.shuf");
3889         TmpVec = createBinOp(Builder, ReductionOpcode, TmpVec, Shuf, "bin.rdx");
3890       }
3891     }
3892
3893     // The result is in the first element of the vector.
3894     return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
3895   }
3896 };
3897
3898 /// \brief Recognize construction of vectors like
3899 ///  %ra = insertelement <4 x float> undef, float %s0, i32 0
3900 ///  %rb = insertelement <4 x float> %ra, float %s1, i32 1
3901 ///  %rc = insertelement <4 x float> %rb, float %s2, i32 2
3902 ///  %rd = insertelement <4 x float> %rc, float %s3, i32 3
3903 ///
3904 /// Returns true if it matches
3905 ///
3906 static bool findBuildVector(InsertElementInst *FirstInsertElem,
3907                             SmallVectorImpl<Value *> &BuildVector,
3908                             SmallVectorImpl<Value *> &BuildVectorOpds) {
3909   if (!isa<UndefValue>(FirstInsertElem->getOperand(0)))
3910     return false;
3911
3912   InsertElementInst *IE = FirstInsertElem;
3913   while (true) {
3914     BuildVector.push_back(IE);
3915     BuildVectorOpds.push_back(IE->getOperand(1));
<