[SLP] remove opcode identifier for reduction; NFC
[lldb.git] / llvm / lib / Transforms / Vectorize / SLPVectorizer.cpp
1 //===- SLPVectorizer.cpp - A bottom up SLP Vectorizer ---------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
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
19 #include "llvm/Transforms/Vectorize/SLPVectorizer.h"
20 #include "llvm/ADT/DenseMap.h"
21 #include "llvm/ADT/DenseSet.h"
22 #include "llvm/ADT/Optional.h"
23 #include "llvm/ADT/PostOrderIterator.h"
24 #include "llvm/ADT/STLExtras.h"
25 #include "llvm/ADT/SetVector.h"
26 #include "llvm/ADT/SmallBitVector.h"
27 #include "llvm/ADT/SmallPtrSet.h"
28 #include "llvm/ADT/SmallSet.h"
29 #include "llvm/ADT/SmallString.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/ADT/iterator.h"
32 #include "llvm/ADT/iterator_range.h"
33 #include "llvm/Analysis/AliasAnalysis.h"
34 #include "llvm/Analysis/AssumptionCache.h"
35 #include "llvm/Analysis/CodeMetrics.h"
36 #include "llvm/Analysis/DemandedBits.h"
37 #include "llvm/Analysis/GlobalsModRef.h"
38 #include "llvm/Analysis/IVDescriptors.h"
39 #include "llvm/Analysis/LoopAccessAnalysis.h"
40 #include "llvm/Analysis/LoopInfo.h"
41 #include "llvm/Analysis/MemoryLocation.h"
42 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
43 #include "llvm/Analysis/ScalarEvolution.h"
44 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
45 #include "llvm/Analysis/TargetLibraryInfo.h"
46 #include "llvm/Analysis/TargetTransformInfo.h"
47 #include "llvm/Analysis/ValueTracking.h"
48 #include "llvm/Analysis/VectorUtils.h"
49 #include "llvm/IR/Attributes.h"
50 #include "llvm/IR/BasicBlock.h"
51 #include "llvm/IR/Constant.h"
52 #include "llvm/IR/Constants.h"
53 #include "llvm/IR/DataLayout.h"
54 #include "llvm/IR/DebugLoc.h"
55 #include "llvm/IR/DerivedTypes.h"
56 #include "llvm/IR/Dominators.h"
57 #include "llvm/IR/Function.h"
58 #include "llvm/IR/IRBuilder.h"
59 #include "llvm/IR/InstrTypes.h"
60 #include "llvm/IR/Instruction.h"
61 #include "llvm/IR/Instructions.h"
62 #include "llvm/IR/IntrinsicInst.h"
63 #include "llvm/IR/Intrinsics.h"
64 #include "llvm/IR/Module.h"
65 #include "llvm/IR/NoFolder.h"
66 #include "llvm/IR/Operator.h"
67 #include "llvm/IR/PatternMatch.h"
68 #include "llvm/IR/Type.h"
69 #include "llvm/IR/Use.h"
70 #include "llvm/IR/User.h"
71 #include "llvm/IR/Value.h"
72 #include "llvm/IR/ValueHandle.h"
73 #include "llvm/IR/Verifier.h"
74 #include "llvm/InitializePasses.h"
75 #include "llvm/Pass.h"
76 #include "llvm/Support/Casting.h"
77 #include "llvm/Support/CommandLine.h"
78 #include "llvm/Support/Compiler.h"
79 #include "llvm/Support/DOTGraphTraits.h"
80 #include "llvm/Support/Debug.h"
81 #include "llvm/Support/ErrorHandling.h"
82 #include "llvm/Support/GraphWriter.h"
83 #include "llvm/Support/InstructionCost.h"
84 #include "llvm/Support/KnownBits.h"
85 #include "llvm/Support/MathExtras.h"
86 #include "llvm/Support/raw_ostream.h"
87 #include "llvm/Transforms/Utils/InjectTLIMappings.h"
88 #include "llvm/Transforms/Utils/LoopUtils.h"
89 #include "llvm/Transforms/Vectorize.h"
90 #include <algorithm>
91 #include <cassert>
92 #include <cstdint>
93 #include <iterator>
94 #include <memory>
95 #include <set>
96 #include <string>
97 #include <tuple>
98 #include <utility>
99 #include <vector>
100
101 using namespace llvm;
102 using namespace llvm::PatternMatch;
103 using namespace slpvectorizer;
104
105 #define SV_NAME "slp-vectorizer"
106 #define DEBUG_TYPE "SLP"
107
108 STATISTIC(NumVectorInstructions, "Number of vector instructions generated");
109
110 cl::opt<bool> RunSLPVectorization("vectorize-slp", cl::init(true), cl::Hidden,
111                                   cl::desc("Run the SLP vectorization passes"));
112
113 static cl::opt<int>
114     SLPCostThreshold("slp-threshold", cl::init(0), cl::Hidden,
115                      cl::desc("Only vectorize if you gain more than this "
116                               "number "));
117
118 static cl::opt<bool>
119 ShouldVectorizeHor("slp-vectorize-hor", cl::init(true), cl::Hidden,
120                    cl::desc("Attempt to vectorize horizontal reductions"));
121
122 static cl::opt<bool> ShouldStartVectorizeHorAtStore(
123     "slp-vectorize-hor-store", cl::init(false), cl::Hidden,
124     cl::desc(
125         "Attempt to vectorize horizontal reductions feeding into a store"));
126
127 static cl::opt<int>
128 MaxVectorRegSizeOption("slp-max-reg-size", cl::init(128), cl::Hidden,
129     cl::desc("Attempt to vectorize for this register size in bits"));
130
131 static cl::opt<unsigned>
132 MaxVFOption("slp-max-vf", cl::init(0), cl::Hidden,
133     cl::desc("Maximum SLP vectorization factor (0=unlimited)"));
134
135 static cl::opt<int>
136 MaxStoreLookup("slp-max-store-lookup", cl::init(32), cl::Hidden,
137     cl::desc("Maximum depth of the lookup for consecutive stores."));
138
139 /// Limits the size of scheduling regions in a block.
140 /// It avoid long compile times for _very_ large blocks where vector
141 /// instructions are spread over a wide range.
142 /// This limit is way higher than needed by real-world functions.
143 static cl::opt<int>
144 ScheduleRegionSizeBudget("slp-schedule-budget", cl::init(100000), cl::Hidden,
145     cl::desc("Limit the size of the SLP scheduling region per block"));
146
147 static cl::opt<int> MinVectorRegSizeOption(
148     "slp-min-reg-size", cl::init(128), cl::Hidden,
149     cl::desc("Attempt to vectorize for this register size in bits"));
150
151 static cl::opt<unsigned> RecursionMaxDepth(
152     "slp-recursion-max-depth", cl::init(12), cl::Hidden,
153     cl::desc("Limit the recursion depth when building a vectorizable tree"));
154
155 static cl::opt<unsigned> MinTreeSize(
156     "slp-min-tree-size", cl::init(3), cl::Hidden,
157     cl::desc("Only vectorize small trees if they are fully vectorizable"));
158
159 // The maximum depth that the look-ahead score heuristic will explore.
160 // The higher this value, the higher the compilation time overhead.
161 static cl::opt<int> LookAheadMaxDepth(
162     "slp-max-look-ahead-depth", cl::init(2), cl::Hidden,
163     cl::desc("The maximum look-ahead depth for operand reordering scores"));
164
165 // The Look-ahead heuristic goes through the users of the bundle to calculate
166 // the users cost in getExternalUsesCost(). To avoid compilation time increase
167 // we limit the number of users visited to this value.
168 static cl::opt<unsigned> LookAheadUsersBudget(
169     "slp-look-ahead-users-budget", cl::init(2), cl::Hidden,
170     cl::desc("The maximum number of users to visit while visiting the "
171              "predecessors. This prevents compilation time increase."));
172
173 static cl::opt<bool>
174     ViewSLPTree("view-slp-tree", cl::Hidden,
175                 cl::desc("Display the SLP trees with Graphviz"));
176
177 // Limit the number of alias checks. The limit is chosen so that
178 // it has no negative effect on the llvm benchmarks.
179 static const unsigned AliasedCheckLimit = 10;
180
181 // Another limit for the alias checks: The maximum distance between load/store
182 // instructions where alias checks are done.
183 // This limit is useful for very large basic blocks.
184 static const unsigned MaxMemDepDistance = 160;
185
186 /// If the ScheduleRegionSizeBudget is exhausted, we allow small scheduling
187 /// regions to be handled.
188 static const int MinScheduleRegionSize = 16;
189
190 /// Predicate for the element types that the SLP vectorizer supports.
191 ///
192 /// The most important thing to filter here are types which are invalid in LLVM
193 /// vectors. We also filter target specific types which have absolutely no
194 /// meaningful vectorization path such as x86_fp80 and ppc_f128. This just
195 /// avoids spending time checking the cost model and realizing that they will
196 /// be inevitably scalarized.
197 static bool isValidElementType(Type *Ty) {
198   return VectorType::isValidElementType(Ty) && !Ty->isX86_FP80Ty() &&
199          !Ty->isPPC_FP128Ty();
200 }
201
202 /// \returns true if all of the instructions in \p VL are in the same block or
203 /// false otherwise.
204 static bool allSameBlock(ArrayRef<Value *> VL) {
205   Instruction *I0 = dyn_cast<Instruction>(VL[0]);
206   if (!I0)
207     return false;
208   BasicBlock *BB = I0->getParent();
209   for (int I = 1, E = VL.size(); I < E; I++) {
210     auto *II = dyn_cast<Instruction>(VL[I]);
211     if (!II)
212       return false;
213
214     if (BB != II->getParent())
215       return false;
216   }
217   return true;
218 }
219
220 /// \returns True if all of the values in \p VL are constants (but not
221 /// globals/constant expressions).
222 static bool allConstant(ArrayRef<Value *> VL) {
223   // Constant expressions and globals can't be vectorized like normal integer/FP
224   // constants.
225   for (Value *i : VL)
226     if (!isa<Constant>(i) || isa<ConstantExpr>(i) || isa<GlobalValue>(i))
227       return false;
228   return true;
229 }
230
231 /// \returns True if all of the values in \p VL are identical.
232 static bool isSplat(ArrayRef<Value *> VL) {
233   for (unsigned i = 1, e = VL.size(); i < e; ++i)
234     if (VL[i] != VL[0])
235       return false;
236   return true;
237 }
238
239 /// \returns True if \p I is commutative, handles CmpInst and BinaryOperator.
240 static bool isCommutative(Instruction *I) {
241   if (auto *Cmp = dyn_cast<CmpInst>(I))
242     return Cmp->isCommutative();
243   if (auto *BO = dyn_cast<BinaryOperator>(I))
244     return BO->isCommutative();
245   // TODO: This should check for generic Instruction::isCommutative(), but
246   //       we need to confirm that the caller code correctly handles Intrinsics
247   //       for example (does not have 2 operands).
248   return false;
249 }
250
251 /// Checks if the vector of instructions can be represented as a shuffle, like:
252 /// %x0 = extractelement <4 x i8> %x, i32 0
253 /// %x3 = extractelement <4 x i8> %x, i32 3
254 /// %y1 = extractelement <4 x i8> %y, i32 1
255 /// %y2 = extractelement <4 x i8> %y, i32 2
256 /// %x0x0 = mul i8 %x0, %x0
257 /// %x3x3 = mul i8 %x3, %x3
258 /// %y1y1 = mul i8 %y1, %y1
259 /// %y2y2 = mul i8 %y2, %y2
260 /// %ins1 = insertelement <4 x i8> poison, i8 %x0x0, i32 0
261 /// %ins2 = insertelement <4 x i8> %ins1, i8 %x3x3, i32 1
262 /// %ins3 = insertelement <4 x i8> %ins2, i8 %y1y1, i32 2
263 /// %ins4 = insertelement <4 x i8> %ins3, i8 %y2y2, i32 3
264 /// ret <4 x i8> %ins4
265 /// can be transformed into:
266 /// %1 = shufflevector <4 x i8> %x, <4 x i8> %y, <4 x i32> <i32 0, i32 3, i32 5,
267 ///                                                         i32 6>
268 /// %2 = mul <4 x i8> %1, %1
269 /// ret <4 x i8> %2
270 /// We convert this initially to something like:
271 /// %x0 = extractelement <4 x i8> %x, i32 0
272 /// %x3 = extractelement <4 x i8> %x, i32 3
273 /// %y1 = extractelement <4 x i8> %y, i32 1
274 /// %y2 = extractelement <4 x i8> %y, i32 2
275 /// %1 = insertelement <4 x i8> poison, i8 %x0, i32 0
276 /// %2 = insertelement <4 x i8> %1, i8 %x3, i32 1
277 /// %3 = insertelement <4 x i8> %2, i8 %y1, i32 2
278 /// %4 = insertelement <4 x i8> %3, i8 %y2, i32 3
279 /// %5 = mul <4 x i8> %4, %4
280 /// %6 = extractelement <4 x i8> %5, i32 0
281 /// %ins1 = insertelement <4 x i8> poison, i8 %6, i32 0
282 /// %7 = extractelement <4 x i8> %5, i32 1
283 /// %ins2 = insertelement <4 x i8> %ins1, i8 %7, i32 1
284 /// %8 = extractelement <4 x i8> %5, i32 2
285 /// %ins3 = insertelement <4 x i8> %ins2, i8 %8, i32 2
286 /// %9 = extractelement <4 x i8> %5, i32 3
287 /// %ins4 = insertelement <4 x i8> %ins3, i8 %9, i32 3
288 /// ret <4 x i8> %ins4
289 /// InstCombiner transforms this into a shuffle and vector mul
290 /// TODO: Can we split off and reuse the shuffle mask detection from
291 /// TargetTransformInfo::getInstructionThroughput?
292 static Optional<TargetTransformInfo::ShuffleKind>
293 isShuffle(ArrayRef<Value *> VL) {
294   auto *EI0 = cast<ExtractElementInst>(VL[0]);
295   unsigned Size =
296       cast<FixedVectorType>(EI0->getVectorOperandType())->getNumElements();
297   Value *Vec1 = nullptr;
298   Value *Vec2 = nullptr;
299   enum ShuffleMode { Unknown, Select, Permute };
300   ShuffleMode CommonShuffleMode = Unknown;
301   for (unsigned I = 0, E = VL.size(); I < E; ++I) {
302     auto *EI = cast<ExtractElementInst>(VL[I]);
303     auto *Vec = EI->getVectorOperand();
304     // All vector operands must have the same number of vector elements.
305     if (cast<FixedVectorType>(Vec->getType())->getNumElements() != Size)
306       return None;
307     auto *Idx = dyn_cast<ConstantInt>(EI->getIndexOperand());
308     if (!Idx)
309       return None;
310     // Undefined behavior if Idx is negative or >= Size.
311     if (Idx->getValue().uge(Size))
312       continue;
313     unsigned IntIdx = Idx->getValue().getZExtValue();
314     // We can extractelement from undef or poison vector.
315     if (isa<UndefValue>(Vec))
316       continue;
317     // For correct shuffling we have to have at most 2 different vector operands
318     // in all extractelement instructions.
319     if (!Vec1 || Vec1 == Vec)
320       Vec1 = Vec;
321     else if (!Vec2 || Vec2 == Vec)
322       Vec2 = Vec;
323     else
324       return None;
325     if (CommonShuffleMode == Permute)
326       continue;
327     // If the extract index is not the same as the operation number, it is a
328     // permutation.
329     if (IntIdx != I) {
330       CommonShuffleMode = Permute;
331       continue;
332     }
333     CommonShuffleMode = Select;
334   }
335   // If we're not crossing lanes in different vectors, consider it as blending.
336   if (CommonShuffleMode == Select && Vec2)
337     return TargetTransformInfo::SK_Select;
338   // If Vec2 was never used, we have a permutation of a single vector, otherwise
339   // we have permutation of 2 vectors.
340   return Vec2 ? TargetTransformInfo::SK_PermuteTwoSrc
341               : TargetTransformInfo::SK_PermuteSingleSrc;
342 }
343
344 namespace {
345
346 /// Main data required for vectorization of instructions.
347 struct InstructionsState {
348   /// The very first instruction in the list with the main opcode.
349   Value *OpValue = nullptr;
350
351   /// The main/alternate instruction.
352   Instruction *MainOp = nullptr;
353   Instruction *AltOp = nullptr;
354
355   /// The main/alternate opcodes for the list of instructions.
356   unsigned getOpcode() const {
357     return MainOp ? MainOp->getOpcode() : 0;
358   }
359
360   unsigned getAltOpcode() const {
361     return AltOp ? AltOp->getOpcode() : 0;
362   }
363
364   /// Some of the instructions in the list have alternate opcodes.
365   bool isAltShuffle() const { return getOpcode() != getAltOpcode(); }
366
367   bool isOpcodeOrAlt(Instruction *I) const {
368     unsigned CheckedOpcode = I->getOpcode();
369     return getOpcode() == CheckedOpcode || getAltOpcode() == CheckedOpcode;
370   }
371
372   InstructionsState() = delete;
373   InstructionsState(Value *OpValue, Instruction *MainOp, Instruction *AltOp)
374       : OpValue(OpValue), MainOp(MainOp), AltOp(AltOp) {}
375 };
376
377 } // end anonymous namespace
378
379 /// Chooses the correct key for scheduling data. If \p Op has the same (or
380 /// alternate) opcode as \p OpValue, the key is \p Op. Otherwise the key is \p
381 /// OpValue.
382 static Value *isOneOf(const InstructionsState &S, Value *Op) {
383   auto *I = dyn_cast<Instruction>(Op);
384   if (I && S.isOpcodeOrAlt(I))
385     return Op;
386   return S.OpValue;
387 }
388
389 /// \returns true if \p Opcode is allowed as part of of the main/alternate
390 /// instruction for SLP vectorization.
391 ///
392 /// Example of unsupported opcode is SDIV that can potentially cause UB if the
393 /// "shuffled out" lane would result in division by zero.
394 static bool isValidForAlternation(unsigned Opcode) {
395   if (Instruction::isIntDivRem(Opcode))
396     return false;
397
398   return true;
399 }
400
401 /// \returns analysis of the Instructions in \p VL described in
402 /// InstructionsState, the Opcode that we suppose the whole list
403 /// could be vectorized even if its structure is diverse.
404 static InstructionsState getSameOpcode(ArrayRef<Value *> VL,
405                                        unsigned BaseIndex = 0) {
406   // Make sure these are all Instructions.
407   if (llvm::any_of(VL, [](Value *V) { return !isa<Instruction>(V); }))
408     return InstructionsState(VL[BaseIndex], nullptr, nullptr);
409
410   bool IsCastOp = isa<CastInst>(VL[BaseIndex]);
411   bool IsBinOp = isa<BinaryOperator>(VL[BaseIndex]);
412   unsigned Opcode = cast<Instruction>(VL[BaseIndex])->getOpcode();
413   unsigned AltOpcode = Opcode;
414   unsigned AltIndex = BaseIndex;
415
416   // Check for one alternate opcode from another BinaryOperator.
417   // TODO - generalize to support all operators (types, calls etc.).
418   for (int Cnt = 0, E = VL.size(); Cnt < E; Cnt++) {
419     unsigned InstOpcode = cast<Instruction>(VL[Cnt])->getOpcode();
420     if (IsBinOp && isa<BinaryOperator>(VL[Cnt])) {
421       if (InstOpcode == Opcode || InstOpcode == AltOpcode)
422         continue;
423       if (Opcode == AltOpcode && isValidForAlternation(InstOpcode) &&
424           isValidForAlternation(Opcode)) {
425         AltOpcode = InstOpcode;
426         AltIndex = Cnt;
427         continue;
428       }
429     } else if (IsCastOp && isa<CastInst>(VL[Cnt])) {
430       Type *Ty0 = cast<Instruction>(VL[BaseIndex])->getOperand(0)->getType();
431       Type *Ty1 = cast<Instruction>(VL[Cnt])->getOperand(0)->getType();
432       if (Ty0 == Ty1) {
433         if (InstOpcode == Opcode || InstOpcode == AltOpcode)
434           continue;
435         if (Opcode == AltOpcode) {
436           assert(isValidForAlternation(Opcode) &&
437                  isValidForAlternation(InstOpcode) &&
438                  "Cast isn't safe for alternation, logic needs to be updated!");
439           AltOpcode = InstOpcode;
440           AltIndex = Cnt;
441           continue;
442         }
443       }
444     } else if (InstOpcode == Opcode || InstOpcode == AltOpcode)
445       continue;
446     return InstructionsState(VL[BaseIndex], nullptr, nullptr);
447   }
448
449   return InstructionsState(VL[BaseIndex], cast<Instruction>(VL[BaseIndex]),
450                            cast<Instruction>(VL[AltIndex]));
451 }
452
453 /// \returns true if all of the values in \p VL have the same type or false
454 /// otherwise.
455 static bool allSameType(ArrayRef<Value *> VL) {
456   Type *Ty = VL[0]->getType();
457   for (int i = 1, e = VL.size(); i < e; i++)
458     if (VL[i]->getType() != Ty)
459       return false;
460
461   return true;
462 }
463
464 /// \returns True if Extract{Value,Element} instruction extracts element Idx.
465 static Optional<unsigned> getExtractIndex(Instruction *E) {
466   unsigned Opcode = E->getOpcode();
467   assert((Opcode == Instruction::ExtractElement ||
468           Opcode == Instruction::ExtractValue) &&
469          "Expected extractelement or extractvalue instruction.");
470   if (Opcode == Instruction::ExtractElement) {
471     auto *CI = dyn_cast<ConstantInt>(E->getOperand(1));
472     if (!CI)
473       return None;
474     return CI->getZExtValue();
475   }
476   ExtractValueInst *EI = cast<ExtractValueInst>(E);
477   if (EI->getNumIndices() != 1)
478     return None;
479   return *EI->idx_begin();
480 }
481
482 /// \returns True if in-tree use also needs extract. This refers to
483 /// possible scalar operand in vectorized instruction.
484 static bool InTreeUserNeedToExtract(Value *Scalar, Instruction *UserInst,
485                                     TargetLibraryInfo *TLI) {
486   unsigned Opcode = UserInst->getOpcode();
487   switch (Opcode) {
488   case Instruction::Load: {
489     LoadInst *LI = cast<LoadInst>(UserInst);
490     return (LI->getPointerOperand() == Scalar);
491   }
492   case Instruction::Store: {
493     StoreInst *SI = cast<StoreInst>(UserInst);
494     return (SI->getPointerOperand() == Scalar);
495   }
496   case Instruction::Call: {
497     CallInst *CI = cast<CallInst>(UserInst);
498     Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI);
499     for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) {
500       if (hasVectorInstrinsicScalarOpd(ID, i))
501         return (CI->getArgOperand(i) == Scalar);
502     }
503     LLVM_FALLTHROUGH;
504   }
505   default:
506     return false;
507   }
508 }
509
510 /// \returns the AA location that is being access by the instruction.
511 static MemoryLocation getLocation(Instruction *I, AAResults *AA) {
512   if (StoreInst *SI = dyn_cast<StoreInst>(I))
513     return MemoryLocation::get(SI);
514   if (LoadInst *LI = dyn_cast<LoadInst>(I))
515     return MemoryLocation::get(LI);
516   return MemoryLocation();
517 }
518
519 /// \returns True if the instruction is not a volatile or atomic load/store.
520 static bool isSimple(Instruction *I) {
521   if (LoadInst *LI = dyn_cast<LoadInst>(I))
522     return LI->isSimple();
523   if (StoreInst *SI = dyn_cast<StoreInst>(I))
524     return SI->isSimple();
525   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(I))
526     return !MI->isVolatile();
527   return true;
528 }
529
530 namespace llvm {
531
532 static void inversePermutation(ArrayRef<unsigned> Indices,
533                                SmallVectorImpl<int> &Mask) {
534   Mask.clear();
535   const unsigned E = Indices.size();
536   Mask.resize(E, E + 1);
537   for (unsigned I = 0; I < E; ++I)
538     Mask[Indices[I]] = I;
539 }
540
541 namespace slpvectorizer {
542
543 /// Bottom Up SLP Vectorizer.
544 class BoUpSLP {
545   struct TreeEntry;
546   struct ScheduleData;
547
548 public:
549   using ValueList = SmallVector<Value *, 8>;
550   using InstrList = SmallVector<Instruction *, 16>;
551   using ValueSet = SmallPtrSet<Value *, 16>;
552   using StoreList = SmallVector<StoreInst *, 8>;
553   using ExtraValueToDebugLocsMap =
554       MapVector<Value *, SmallVector<Instruction *, 2>>;
555   using OrdersType = SmallVector<unsigned, 4>;
556
557   BoUpSLP(Function *Func, ScalarEvolution *Se, TargetTransformInfo *Tti,
558           TargetLibraryInfo *TLi, AAResults *Aa, LoopInfo *Li,
559           DominatorTree *Dt, AssumptionCache *AC, DemandedBits *DB,
560           const DataLayout *DL, OptimizationRemarkEmitter *ORE)
561       : F(Func), SE(Se), TTI(Tti), TLI(TLi), AA(Aa), LI(Li), DT(Dt), AC(AC),
562         DB(DB), DL(DL), ORE(ORE), Builder(Se->getContext()) {
563     CodeMetrics::collectEphemeralValues(F, AC, EphValues);
564     // Use the vector register size specified by the target unless overridden
565     // by a command-line option.
566     // TODO: It would be better to limit the vectorization factor based on
567     //       data type rather than just register size. For example, x86 AVX has
568     //       256-bit registers, but it does not support integer operations
569     //       at that width (that requires AVX2).
570     if (MaxVectorRegSizeOption.getNumOccurrences())
571       MaxVecRegSize = MaxVectorRegSizeOption;
572     else
573       MaxVecRegSize = TTI->getRegisterBitWidth(true);
574
575     if (MinVectorRegSizeOption.getNumOccurrences())
576       MinVecRegSize = MinVectorRegSizeOption;
577     else
578       MinVecRegSize = TTI->getMinVectorRegisterBitWidth();
579   }
580
581   /// Vectorize the tree that starts with the elements in \p VL.
582   /// Returns the vectorized root.
583   Value *vectorizeTree();
584
585   /// Vectorize the tree but with the list of externally used values \p
586   /// ExternallyUsedValues. Values in this MapVector can be replaced but the
587   /// generated extractvalue instructions.
588   Value *vectorizeTree(ExtraValueToDebugLocsMap &ExternallyUsedValues);
589
590   /// \returns the cost incurred by unwanted spills and fills, caused by
591   /// holding live values over call sites.
592   InstructionCost getSpillCost() const;
593
594   /// \returns the vectorization cost of the subtree that starts at \p VL.
595   /// A negative number means that this is profitable.
596   InstructionCost getTreeCost();
597
598   /// Construct a vectorizable tree that starts at \p Roots, ignoring users for
599   /// the purpose of scheduling and extraction in the \p UserIgnoreLst.
600   void buildTree(ArrayRef<Value *> Roots,
601                  ArrayRef<Value *> UserIgnoreLst = None);
602
603   /// Construct a vectorizable tree that starts at \p Roots, ignoring users for
604   /// the purpose of scheduling and extraction in the \p UserIgnoreLst taking
605   /// into account (and updating it, if required) list of externally used
606   /// values stored in \p ExternallyUsedValues.
607   void buildTree(ArrayRef<Value *> Roots,
608                  ExtraValueToDebugLocsMap &ExternallyUsedValues,
609                  ArrayRef<Value *> UserIgnoreLst = None);
610
611   /// Clear the internal data structures that are created by 'buildTree'.
612   void deleteTree() {
613     VectorizableTree.clear();
614     ScalarToTreeEntry.clear();
615     MustGather.clear();
616     ExternalUses.clear();
617     NumOpsWantToKeepOrder.clear();
618     NumOpsWantToKeepOriginalOrder = 0;
619     for (auto &Iter : BlocksSchedules) {
620       BlockScheduling *BS = Iter.second.get();
621       BS->clear();
622     }
623     MinBWs.clear();
624   }
625
626   unsigned getTreeSize() const { return VectorizableTree.size(); }
627
628   /// Perform LICM and CSE on the newly generated gather sequences.
629   void optimizeGatherSequence();
630
631   /// \returns The best order of instructions for vectorization.
632   Optional<ArrayRef<unsigned>> bestOrder() const {
633     assert(llvm::all_of(
634                NumOpsWantToKeepOrder,
635                [this](const decltype(NumOpsWantToKeepOrder)::value_type &D) {
636                  return D.getFirst().size() ==
637                         VectorizableTree[0]->Scalars.size();
638                }) &&
639            "All orders must have the same size as number of instructions in "
640            "tree node.");
641     auto I = std::max_element(
642         NumOpsWantToKeepOrder.begin(), NumOpsWantToKeepOrder.end(),
643         [](const decltype(NumOpsWantToKeepOrder)::value_type &D1,
644            const decltype(NumOpsWantToKeepOrder)::value_type &D2) {
645           return D1.second < D2.second;
646         });
647     if (I == NumOpsWantToKeepOrder.end() ||
648         I->getSecond() <= NumOpsWantToKeepOriginalOrder)
649       return None;
650
651     return makeArrayRef(I->getFirst());
652   }
653
654   /// Builds the correct order for root instructions.
655   /// If some leaves have the same instructions to be vectorized, we may
656   /// incorrectly evaluate the best order for the root node (it is built for the
657   /// vector of instructions without repeated instructions and, thus, has less
658   /// elements than the root node). This function builds the correct order for
659   /// the root node.
660   /// For example, if the root node is \<a+b, a+c, a+d, f+e\>, then the leaves
661   /// are \<a, a, a, f\> and \<b, c, d, e\>. When we try to vectorize the first
662   /// leaf, it will be shrink to \<a, b\>. If instructions in this leaf should
663   /// be reordered, the best order will be \<1, 0\>. We need to extend this
664   /// order for the root node. For the root node this order should look like
665   /// \<3, 0, 1, 2\>. This function extends the order for the reused
666   /// instructions.
667   void findRootOrder(OrdersType &Order) {
668     // If the leaf has the same number of instructions to vectorize as the root
669     // - order must be set already.
670     unsigned RootSize = VectorizableTree[0]->Scalars.size();
671     if (Order.size() == RootSize)
672       return;
673     SmallVector<unsigned, 4> RealOrder(Order.size());
674     std::swap(Order, RealOrder);
675     SmallVector<int, 4> Mask;
676     inversePermutation(RealOrder, Mask);
677     Order.assign(Mask.begin(), Mask.end());
678     // The leaf has less number of instructions - need to find the true order of
679     // the root.
680     // Scan the nodes starting from the leaf back to the root.
681     const TreeEntry *PNode = VectorizableTree.back().get();
682     SmallVector<const TreeEntry *, 4> Nodes(1, PNode);
683     SmallPtrSet<const TreeEntry *, 4> Visited;
684     while (!Nodes.empty() && Order.size() != RootSize) {
685       const TreeEntry *PNode = Nodes.pop_back_val();
686       if (!Visited.insert(PNode).second)
687         continue;
688       const TreeEntry &Node = *PNode;
689       for (const EdgeInfo &EI : Node.UserTreeIndices)
690         if (EI.UserTE)
691           Nodes.push_back(EI.UserTE);
692       if (Node.ReuseShuffleIndices.empty())
693         continue;
694       // Build the order for the parent node.
695       OrdersType NewOrder(Node.ReuseShuffleIndices.size(), RootSize);
696       SmallVector<unsigned, 4> OrderCounter(Order.size(), 0);
697       // The algorithm of the order extension is:
698       // 1. Calculate the number of the same instructions for the order.
699       // 2. Calculate the index of the new order: total number of instructions
700       // with order less than the order of the current instruction + reuse
701       // number of the current instruction.
702       // 3. The new order is just the index of the instruction in the original
703       // vector of the instructions.
704       for (unsigned I : Node.ReuseShuffleIndices)
705         ++OrderCounter[Order[I]];
706       SmallVector<unsigned, 4> CurrentCounter(Order.size(), 0);
707       for (unsigned I = 0, E = Node.ReuseShuffleIndices.size(); I < E; ++I) {
708         unsigned ReusedIdx = Node.ReuseShuffleIndices[I];
709         unsigned OrderIdx = Order[ReusedIdx];
710         unsigned NewIdx = 0;
711         for (unsigned J = 0; J < OrderIdx; ++J)
712           NewIdx += OrderCounter[J];
713         NewIdx += CurrentCounter[OrderIdx];
714         ++CurrentCounter[OrderIdx];
715         assert(NewOrder[NewIdx] == RootSize &&
716                "The order index should not be written already.");
717         NewOrder[NewIdx] = I;
718       }
719       std::swap(Order, NewOrder);
720     }
721     assert(Order.size() == RootSize &&
722            "Root node is expected or the size of the order must be the same as "
723            "the number of elements in the root node.");
724     assert(llvm::all_of(Order,
725                         [RootSize](unsigned Val) { return Val != RootSize; }) &&
726            "All indices must be initialized");
727   }
728
729   /// \return The vector element size in bits to use when vectorizing the
730   /// expression tree ending at \p V. If V is a store, the size is the width of
731   /// the stored value. Otherwise, the size is the width of the largest loaded
732   /// value reaching V. This method is used by the vectorizer to calculate
733   /// vectorization factors.
734   unsigned getVectorElementSize(Value *V);
735
736   /// Compute the minimum type sizes required to represent the entries in a
737   /// vectorizable tree.
738   void computeMinimumValueSizes();
739
740   // \returns maximum vector register size as set by TTI or overridden by cl::opt.
741   unsigned getMaxVecRegSize() const {
742     return MaxVecRegSize;
743   }
744
745   // \returns minimum vector register size as set by cl::opt.
746   unsigned getMinVecRegSize() const {
747     return MinVecRegSize;
748   }
749
750   unsigned getMaximumVF(unsigned ElemWidth, unsigned Opcode) const {
751     unsigned MaxVF = MaxVFOption.getNumOccurrences() ?
752       MaxVFOption : TTI->getMaximumVF(ElemWidth, Opcode);
753     return MaxVF ? MaxVF : UINT_MAX;
754   }
755
756   /// Check if homogeneous aggregate is isomorphic to some VectorType.
757   /// Accepts homogeneous multidimensional aggregate of scalars/vectors like
758   /// {[4 x i16], [4 x i16]}, { <2 x float>, <2 x float> },
759   /// {{{i16, i16}, {i16, i16}}, {{i16, i16}, {i16, i16}}} and so on.
760   ///
761   /// \returns number of elements in vector if isomorphism exists, 0 otherwise.
762   unsigned canMapToVector(Type *T, const DataLayout &DL) const;
763
764   /// \returns True if the VectorizableTree is both tiny and not fully
765   /// vectorizable. We do not vectorize such trees.
766   bool isTreeTinyAndNotFullyVectorizable() const;
767
768   /// Assume that a legal-sized 'or'-reduction of shifted/zexted loaded values
769   /// can be load combined in the backend. Load combining may not be allowed in
770   /// the IR optimizer, so we do not want to alter the pattern. For example,
771   /// partially transforming a scalar bswap() pattern into vector code is
772   /// effectively impossible for the backend to undo.
773   /// TODO: If load combining is allowed in the IR optimizer, this analysis
774   ///       may not be necessary.
775   bool isLoadCombineReductionCandidate(RecurKind RdxKind) const;
776
777   /// Assume that a vector of stores of bitwise-or/shifted/zexted loaded values
778   /// can be load combined in the backend. Load combining may not be allowed in
779   /// the IR optimizer, so we do not want to alter the pattern. For example,
780   /// partially transforming a scalar bswap() pattern into vector code is
781   /// effectively impossible for the backend to undo.
782   /// TODO: If load combining is allowed in the IR optimizer, this analysis
783   ///       may not be necessary.
784   bool isLoadCombineCandidate() const;
785
786   OptimizationRemarkEmitter *getORE() { return ORE; }
787
788   /// This structure holds any data we need about the edges being traversed
789   /// during buildTree_rec(). We keep track of:
790   /// (i) the user TreeEntry index, and
791   /// (ii) the index of the edge.
792   struct EdgeInfo {
793     EdgeInfo() = default;
794     EdgeInfo(TreeEntry *UserTE, unsigned EdgeIdx)
795         : UserTE(UserTE), EdgeIdx(EdgeIdx) {}
796     /// The user TreeEntry.
797     TreeEntry *UserTE = nullptr;
798     /// The operand index of the use.
799     unsigned EdgeIdx = UINT_MAX;
800 #ifndef NDEBUG
801     friend inline raw_ostream &operator<<(raw_ostream &OS,
802                                           const BoUpSLP::EdgeInfo &EI) {
803       EI.dump(OS);
804       return OS;
805     }
806     /// Debug print.
807     void dump(raw_ostream &OS) const {
808       OS << "{User:" << (UserTE ? std::to_string(UserTE->Idx) : "null")
809          << " EdgeIdx:" << EdgeIdx << "}";
810     }
811     LLVM_DUMP_METHOD void dump() const { dump(dbgs()); }
812 #endif
813   };
814
815   /// A helper data structure to hold the operands of a vector of instructions.
816   /// This supports a fixed vector length for all operand vectors.
817   class VLOperands {
818     /// For each operand we need (i) the value, and (ii) the opcode that it
819     /// would be attached to if the expression was in a left-linearized form.
820     /// This is required to avoid illegal operand reordering.
821     /// For example:
822     /// \verbatim
823     ///                         0 Op1
824     ///                         |/
825     /// Op1 Op2   Linearized    + Op2
826     ///   \ /     ---------->   |/
827     ///    -                    -
828     ///
829     /// Op1 - Op2            (0 + Op1) - Op2
830     /// \endverbatim
831     ///
832     /// Value Op1 is attached to a '+' operation, and Op2 to a '-'.
833     ///
834     /// Another way to think of this is to track all the operations across the
835     /// path from the operand all the way to the root of the tree and to
836     /// calculate the operation that corresponds to this path. For example, the
837     /// path from Op2 to the root crosses the RHS of the '-', therefore the
838     /// corresponding operation is a '-' (which matches the one in the
839     /// linearized tree, as shown above).
840     ///
841     /// For lack of a better term, we refer to this operation as Accumulated
842     /// Path Operation (APO).
843     struct OperandData {
844       OperandData() = default;
845       OperandData(Value *V, bool APO, bool IsUsed)
846           : V(V), APO(APO), IsUsed(IsUsed) {}
847       /// The operand value.
848       Value *V = nullptr;
849       /// TreeEntries only allow a single opcode, or an alternate sequence of
850       /// them (e.g, +, -). Therefore, we can safely use a boolean value for the
851       /// APO. It is set to 'true' if 'V' is attached to an inverse operation
852       /// in the left-linearized form (e.g., Sub/Div), and 'false' otherwise
853       /// (e.g., Add/Mul)
854       bool APO = false;
855       /// Helper data for the reordering function.
856       bool IsUsed = false;
857     };
858
859     /// During operand reordering, we are trying to select the operand at lane
860     /// that matches best with the operand at the neighboring lane. Our
861     /// selection is based on the type of value we are looking for. For example,
862     /// if the neighboring lane has a load, we need to look for a load that is
863     /// accessing a consecutive address. These strategies are summarized in the
864     /// 'ReorderingMode' enumerator.
865     enum class ReorderingMode {
866       Load,     ///< Matching loads to consecutive memory addresses
867       Opcode,   ///< Matching instructions based on opcode (same or alternate)
868       Constant, ///< Matching constants
869       Splat,    ///< Matching the same instruction multiple times (broadcast)
870       Failed,   ///< We failed to create a vectorizable group
871     };
872
873     using OperandDataVec = SmallVector<OperandData, 2>;
874
875     /// A vector of operand vectors.
876     SmallVector<OperandDataVec, 4> OpsVec;
877
878     const DataLayout &DL;
879     ScalarEvolution &SE;
880     const BoUpSLP &R;
881
882     /// \returns the operand data at \p OpIdx and \p Lane.
883     OperandData &getData(unsigned OpIdx, unsigned Lane) {
884       return OpsVec[OpIdx][Lane];
885     }
886
887     /// \returns the operand data at \p OpIdx and \p Lane. Const version.
888     const OperandData &getData(unsigned OpIdx, unsigned Lane) const {
889       return OpsVec[OpIdx][Lane];
890     }
891
892     /// Clears the used flag for all entries.
893     void clearUsed() {
894       for (unsigned OpIdx = 0, NumOperands = getNumOperands();
895            OpIdx != NumOperands; ++OpIdx)
896         for (unsigned Lane = 0, NumLanes = getNumLanes(); Lane != NumLanes;
897              ++Lane)
898           OpsVec[OpIdx][Lane].IsUsed = false;
899     }
900
901     /// Swap the operand at \p OpIdx1 with that one at \p OpIdx2.
902     void swap(unsigned OpIdx1, unsigned OpIdx2, unsigned Lane) {
903       std::swap(OpsVec[OpIdx1][Lane], OpsVec[OpIdx2][Lane]);
904     }
905
906     // The hard-coded scores listed here are not very important. When computing
907     // the scores of matching one sub-tree with another, we are basically
908     // counting the number of values that are matching. So even if all scores
909     // are set to 1, we would still get a decent matching result.
910     // However, sometimes we have to break ties. For example we may have to
911     // choose between matching loads vs matching opcodes. This is what these
912     // scores are helping us with: they provide the order of preference.
913
914     /// Loads from consecutive memory addresses, e.g. load(A[i]), load(A[i+1]).
915     static const int ScoreConsecutiveLoads = 3;
916     /// ExtractElementInst from same vector and consecutive indexes.
917     static const int ScoreConsecutiveExtracts = 3;
918     /// Constants.
919     static const int ScoreConstants = 2;
920     /// Instructions with the same opcode.
921     static const int ScoreSameOpcode = 2;
922     /// Instructions with alt opcodes (e.g, add + sub).
923     static const int ScoreAltOpcodes = 1;
924     /// Identical instructions (a.k.a. splat or broadcast).
925     static const int ScoreSplat = 1;
926     /// Matching with an undef is preferable to failing.
927     static const int ScoreUndef = 1;
928     /// Score for failing to find a decent match.
929     static const int ScoreFail = 0;
930     /// User exteranl to the vectorized code.
931     static const int ExternalUseCost = 1;
932     /// The user is internal but in a different lane.
933     static const int UserInDiffLaneCost = ExternalUseCost;
934
935     /// \returns the score of placing \p V1 and \p V2 in consecutive lanes.
936     static int getShallowScore(Value *V1, Value *V2, const DataLayout &DL,
937                                ScalarEvolution &SE) {
938       auto *LI1 = dyn_cast<LoadInst>(V1);
939       auto *LI2 = dyn_cast<LoadInst>(V2);
940       if (LI1 && LI2)
941         return isConsecutiveAccess(LI1, LI2, DL, SE)
942                    ? VLOperands::ScoreConsecutiveLoads
943                    : VLOperands::ScoreFail;
944
945       auto *C1 = dyn_cast<Constant>(V1);
946       auto *C2 = dyn_cast<Constant>(V2);
947       if (C1 && C2)
948         return VLOperands::ScoreConstants;
949
950       // Extracts from consecutive indexes of the same vector better score as
951       // the extracts could be optimized away.
952       Value *EV;
953       ConstantInt *Ex1Idx, *Ex2Idx;
954       if (match(V1, m_ExtractElt(m_Value(EV), m_ConstantInt(Ex1Idx))) &&
955           match(V2, m_ExtractElt(m_Deferred(EV), m_ConstantInt(Ex2Idx))) &&
956           Ex1Idx->getZExtValue() + 1 == Ex2Idx->getZExtValue())
957         return VLOperands::ScoreConsecutiveExtracts;
958
959       auto *I1 = dyn_cast<Instruction>(V1);
960       auto *I2 = dyn_cast<Instruction>(V2);
961       if (I1 && I2) {
962         if (I1 == I2)
963           return VLOperands::ScoreSplat;
964         InstructionsState S = getSameOpcode({I1, I2});
965         // Note: Only consider instructions with <= 2 operands to avoid
966         // complexity explosion.
967         if (S.getOpcode() && S.MainOp->getNumOperands() <= 2)
968           return S.isAltShuffle() ? VLOperands::ScoreAltOpcodes
969                                   : VLOperands::ScoreSameOpcode;
970       }
971
972       if (isa<UndefValue>(V2))
973         return VLOperands::ScoreUndef;
974
975       return VLOperands::ScoreFail;
976     }
977
978     /// Holds the values and their lane that are taking part in the look-ahead
979     /// score calculation. This is used in the external uses cost calculation.
980     SmallDenseMap<Value *, int> InLookAheadValues;
981
982     /// \Returns the additinal cost due to uses of \p LHS and \p RHS that are
983     /// either external to the vectorized code, or require shuffling.
984     int getExternalUsesCost(const std::pair<Value *, int> &LHS,
985                             const std::pair<Value *, int> &RHS) {
986       int Cost = 0;
987       std::array<std::pair<Value *, int>, 2> Values = {{LHS, RHS}};
988       for (int Idx = 0, IdxE = Values.size(); Idx != IdxE; ++Idx) {
989         Value *V = Values[Idx].first;
990         // Calculate the absolute lane, using the minimum relative lane of LHS
991         // and RHS as base and Idx as the offset.
992         int Ln = std::min(LHS.second, RHS.second) + Idx;
993         assert(Ln >= 0 && "Bad lane calculation");
994         unsigned UsersBudget = LookAheadUsersBudget;
995         for (User *U : V->users()) {
996           if (const TreeEntry *UserTE = R.getTreeEntry(U)) {
997             // The user is in the VectorizableTree. Check if we need to insert.
998             auto It = llvm::find(UserTE->Scalars, U);
999             assert(It != UserTE->Scalars.end() && "U is in UserTE");
1000             int UserLn = std::distance(UserTE->Scalars.begin(), It);
1001             assert(UserLn >= 0 && "Bad lane");
1002             if (UserLn != Ln)
1003               Cost += UserInDiffLaneCost;
1004           } else {
1005             // Check if the user is in the look-ahead code.
1006             auto It2 = InLookAheadValues.find(U);
1007             if (It2 != InLookAheadValues.end()) {
1008               // The user is in the look-ahead code. Check the lane.
1009               if (It2->second != Ln)
1010                 Cost += UserInDiffLaneCost;
1011             } else {
1012               // The user is neither in SLP tree nor in the look-ahead code.
1013               Cost += ExternalUseCost;
1014             }
1015           }
1016           // Limit the number of visited uses to cap compilation time.
1017           if (--UsersBudget == 0)
1018             break;
1019         }
1020       }
1021       return Cost;
1022     }
1023
1024     /// Go through the operands of \p LHS and \p RHS recursively until \p
1025     /// MaxLevel, and return the cummulative score. For example:
1026     /// \verbatim
1027     ///  A[0]  B[0]  A[1]  B[1]  C[0] D[0]  B[1] A[1]
1028     ///     \ /         \ /         \ /        \ /
1029     ///      +           +           +          +
1030     ///     G1          G2          G3         G4
1031     /// \endverbatim
1032     /// The getScoreAtLevelRec(G1, G2) function will try to match the nodes at
1033     /// each level recursively, accumulating the score. It starts from matching
1034     /// the additions at level 0, then moves on to the loads (level 1). The
1035     /// score of G1 and G2 is higher than G1 and G3, because {A[0],A[1]} and
1036     /// {B[0],B[1]} match with VLOperands::ScoreConsecutiveLoads, while
1037     /// {A[0],C[0]} has a score of VLOperands::ScoreFail.
1038     /// Please note that the order of the operands does not matter, as we
1039     /// evaluate the score of all profitable combinations of operands. In
1040     /// other words the score of G1 and G4 is the same as G1 and G2. This
1041     /// heuristic is based on ideas described in:
1042     ///   Look-ahead SLP: Auto-vectorization in the presence of commutative
1043     ///   operations, CGO 2018 by Vasileios Porpodas, Rodrigo C. O. Rocha,
1044     ///   Luís F. W. Góes
1045     int getScoreAtLevelRec(const std::pair<Value *, int> &LHS,
1046                            const std::pair<Value *, int> &RHS, int CurrLevel,
1047                            int MaxLevel) {
1048
1049       Value *V1 = LHS.first;
1050       Value *V2 = RHS.first;
1051       // Get the shallow score of V1 and V2.
1052       int ShallowScoreAtThisLevel =
1053           std::max((int)ScoreFail, getShallowScore(V1, V2, DL, SE) -
1054                                        getExternalUsesCost(LHS, RHS));
1055       int Lane1 = LHS.second;
1056       int Lane2 = RHS.second;
1057
1058       // If reached MaxLevel,
1059       //  or if V1 and V2 are not instructions,
1060       //  or if they are SPLAT,
1061       //  or if they are not consecutive, early return the current cost.
1062       auto *I1 = dyn_cast<Instruction>(V1);
1063       auto *I2 = dyn_cast<Instruction>(V2);
1064       if (CurrLevel == MaxLevel || !(I1 && I2) || I1 == I2 ||
1065           ShallowScoreAtThisLevel == VLOperands::ScoreFail ||
1066           (isa<LoadInst>(I1) && isa<LoadInst>(I2) && ShallowScoreAtThisLevel))
1067         return ShallowScoreAtThisLevel;
1068       assert(I1 && I2 && "Should have early exited.");
1069
1070       // Keep track of in-tree values for determining the external-use cost.
1071       InLookAheadValues[V1] = Lane1;
1072       InLookAheadValues[V2] = Lane2;
1073
1074       // Contains the I2 operand indexes that got matched with I1 operands.
1075       SmallSet<unsigned, 4> Op2Used;
1076
1077       // Recursion towards the operands of I1 and I2. We are trying all possbile
1078       // operand pairs, and keeping track of the best score.
1079       for (unsigned OpIdx1 = 0, NumOperands1 = I1->getNumOperands();
1080            OpIdx1 != NumOperands1; ++OpIdx1) {
1081         // Try to pair op1I with the best operand of I2.
1082         int MaxTmpScore = 0;
1083         unsigned MaxOpIdx2 = 0;
1084         bool FoundBest = false;
1085         // If I2 is commutative try all combinations.
1086         unsigned FromIdx = isCommutative(I2) ? 0 : OpIdx1;
1087         unsigned ToIdx = isCommutative(I2)
1088                              ? I2->getNumOperands()
1089                              : std::min(I2->getNumOperands(), OpIdx1 + 1);
1090         assert(FromIdx <= ToIdx && "Bad index");
1091         for (unsigned OpIdx2 = FromIdx; OpIdx2 != ToIdx; ++OpIdx2) {
1092           // Skip operands already paired with OpIdx1.
1093           if (Op2Used.count(OpIdx2))
1094             continue;
1095           // Recursively calculate the cost at each level
1096           int TmpScore = getScoreAtLevelRec({I1->getOperand(OpIdx1), Lane1},
1097                                             {I2->getOperand(OpIdx2), Lane2},
1098                                             CurrLevel + 1, MaxLevel);
1099           // Look for the best score.
1100           if (TmpScore > VLOperands::ScoreFail && TmpScore > MaxTmpScore) {
1101             MaxTmpScore = TmpScore;
1102             MaxOpIdx2 = OpIdx2;
1103             FoundBest = true;
1104           }
1105         }
1106         if (FoundBest) {
1107           // Pair {OpIdx1, MaxOpIdx2} was found to be best. Never revisit it.
1108           Op2Used.insert(MaxOpIdx2);
1109           ShallowScoreAtThisLevel += MaxTmpScore;
1110         }
1111       }
1112       return ShallowScoreAtThisLevel;
1113     }
1114
1115     /// \Returns the look-ahead score, which tells us how much the sub-trees
1116     /// rooted at \p LHS and \p RHS match, the more they match the higher the
1117     /// score. This helps break ties in an informed way when we cannot decide on
1118     /// the order of the operands by just considering the immediate
1119     /// predecessors.
1120     int getLookAheadScore(const std::pair<Value *, int> &LHS,
1121                           const std::pair<Value *, int> &RHS) {
1122       InLookAheadValues.clear();
1123       return getScoreAtLevelRec(LHS, RHS, 1, LookAheadMaxDepth);
1124     }
1125
1126     // Search all operands in Ops[*][Lane] for the one that matches best
1127     // Ops[OpIdx][LastLane] and return its opreand index.
1128     // If no good match can be found, return None.
1129     Optional<unsigned>
1130     getBestOperand(unsigned OpIdx, int Lane, int LastLane,
1131                    ArrayRef<ReorderingMode> ReorderingModes) {
1132       unsigned NumOperands = getNumOperands();
1133
1134       // The operand of the previous lane at OpIdx.
1135       Value *OpLastLane = getData(OpIdx, LastLane).V;
1136
1137       // Our strategy mode for OpIdx.
1138       ReorderingMode RMode = ReorderingModes[OpIdx];
1139
1140       // The linearized opcode of the operand at OpIdx, Lane.
1141       bool OpIdxAPO = getData(OpIdx, Lane).APO;
1142
1143       // The best operand index and its score.
1144       // Sometimes we have more than one option (e.g., Opcode and Undefs), so we
1145       // are using the score to differentiate between the two.
1146       struct BestOpData {
1147         Optional<unsigned> Idx = None;
1148         unsigned Score = 0;
1149       } BestOp;
1150
1151       // Iterate through all unused operands and look for the best.
1152       for (unsigned Idx = 0; Idx != NumOperands; ++Idx) {
1153         // Get the operand at Idx and Lane.
1154         OperandData &OpData = getData(Idx, Lane);
1155         Value *Op = OpData.V;
1156         bool OpAPO = OpData.APO;
1157
1158         // Skip already selected operands.
1159         if (OpData.IsUsed)
1160           continue;
1161
1162         // Skip if we are trying to move the operand to a position with a
1163         // different opcode in the linearized tree form. This would break the
1164         // semantics.
1165         if (OpAPO != OpIdxAPO)
1166           continue;
1167
1168         // Look for an operand that matches the current mode.
1169         switch (RMode) {
1170         case ReorderingMode::Load:
1171         case ReorderingMode::Constant:
1172         case ReorderingMode::Opcode: {
1173           bool LeftToRight = Lane > LastLane;
1174           Value *OpLeft = (LeftToRight) ? OpLastLane : Op;
1175           Value *OpRight = (LeftToRight) ? Op : OpLastLane;
1176           unsigned Score =
1177               getLookAheadScore({OpLeft, LastLane}, {OpRight, Lane});
1178           if (Score > BestOp.Score) {
1179             BestOp.Idx = Idx;
1180             BestOp.Score = Score;
1181           }
1182           break;
1183         }
1184         case ReorderingMode::Splat:
1185           if (Op == OpLastLane)
1186             BestOp.Idx = Idx;
1187           break;
1188         case ReorderingMode::Failed:
1189           return None;
1190         }
1191       }
1192
1193       if (BestOp.Idx) {
1194         getData(BestOp.Idx.getValue(), Lane).IsUsed = true;
1195         return BestOp.Idx;
1196       }
1197       // If we could not find a good match return None.
1198       return None;
1199     }
1200
1201     /// Helper for reorderOperandVecs. \Returns the lane that we should start
1202     /// reordering from. This is the one which has the least number of operands
1203     /// that can freely move about.
1204     unsigned getBestLaneToStartReordering() const {
1205       unsigned BestLane = 0;
1206       unsigned Min = UINT_MAX;
1207       for (unsigned Lane = 0, NumLanes = getNumLanes(); Lane != NumLanes;
1208            ++Lane) {
1209         unsigned NumFreeOps = getMaxNumOperandsThatCanBeReordered(Lane);
1210         if (NumFreeOps < Min) {
1211           Min = NumFreeOps;
1212           BestLane = Lane;
1213         }
1214       }
1215       return BestLane;
1216     }
1217
1218     /// \Returns the maximum number of operands that are allowed to be reordered
1219     /// for \p Lane. This is used as a heuristic for selecting the first lane to
1220     /// start operand reordering.
1221     unsigned getMaxNumOperandsThatCanBeReordered(unsigned Lane) const {
1222       unsigned CntTrue = 0;
1223       unsigned NumOperands = getNumOperands();
1224       // Operands with the same APO can be reordered. We therefore need to count
1225       // how many of them we have for each APO, like this: Cnt[APO] = x.
1226       // Since we only have two APOs, namely true and false, we can avoid using
1227       // a map. Instead we can simply count the number of operands that
1228       // correspond to one of them (in this case the 'true' APO), and calculate
1229       // the other by subtracting it from the total number of operands.
1230       for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx)
1231         if (getData(OpIdx, Lane).APO)
1232           ++CntTrue;
1233       unsigned CntFalse = NumOperands - CntTrue;
1234       return std::max(CntTrue, CntFalse);
1235     }
1236
1237     /// Go through the instructions in VL and append their operands.
1238     void appendOperandsOfVL(ArrayRef<Value *> VL) {
1239       assert(!VL.empty() && "Bad VL");
1240       assert((empty() || VL.size() == getNumLanes()) &&
1241              "Expected same number of lanes");
1242       assert(isa<Instruction>(VL[0]) && "Expected instruction");
1243       unsigned NumOperands = cast<Instruction>(VL[0])->getNumOperands();
1244       OpsVec.resize(NumOperands);
1245       unsigned NumLanes = VL.size();
1246       for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) {
1247         OpsVec[OpIdx].resize(NumLanes);
1248         for (unsigned Lane = 0; Lane != NumLanes; ++Lane) {
1249           assert(isa<Instruction>(VL[Lane]) && "Expected instruction");
1250           // Our tree has just 3 nodes: the root and two operands.
1251           // It is therefore trivial to get the APO. We only need to check the
1252           // opcode of VL[Lane] and whether the operand at OpIdx is the LHS or
1253           // RHS operand. The LHS operand of both add and sub is never attached
1254           // to an inversese operation in the linearized form, therefore its APO
1255           // is false. The RHS is true only if VL[Lane] is an inverse operation.
1256
1257           // Since operand reordering is performed on groups of commutative
1258           // operations or alternating sequences (e.g., +, -), we can safely
1259           // tell the inverse operations by checking commutativity.
1260           bool IsInverseOperation = !isCommutative(cast<Instruction>(VL[Lane]));
1261           bool APO = (OpIdx == 0) ? false : IsInverseOperation;
1262           OpsVec[OpIdx][Lane] = {cast<Instruction>(VL[Lane])->getOperand(OpIdx),
1263                                  APO, false};
1264         }
1265       }
1266     }
1267
1268     /// \returns the number of operands.
1269     unsigned getNumOperands() const { return OpsVec.size(); }
1270
1271     /// \returns the number of lanes.
1272     unsigned getNumLanes() const { return OpsVec[0].size(); }
1273
1274     /// \returns the operand value at \p OpIdx and \p Lane.
1275     Value *getValue(unsigned OpIdx, unsigned Lane) const {
1276       return getData(OpIdx, Lane).V;
1277     }
1278
1279     /// \returns true if the data structure is empty.
1280     bool empty() const { return OpsVec.empty(); }
1281
1282     /// Clears the data.
1283     void clear() { OpsVec.clear(); }
1284
1285     /// \Returns true if there are enough operands identical to \p Op to fill
1286     /// the whole vector.
1287     /// Note: This modifies the 'IsUsed' flag, so a cleanUsed() must follow.
1288     bool shouldBroadcast(Value *Op, unsigned OpIdx, unsigned Lane) {
1289       bool OpAPO = getData(OpIdx, Lane).APO;
1290       for (unsigned Ln = 0, Lns = getNumLanes(); Ln != Lns; ++Ln) {
1291         if (Ln == Lane)
1292           continue;
1293         // This is set to true if we found a candidate for broadcast at Lane.
1294         bool FoundCandidate = false;
1295         for (unsigned OpI = 0, OpE = getNumOperands(); OpI != OpE; ++OpI) {
1296           OperandData &Data = getData(OpI, Ln);
1297           if (Data.APO != OpAPO || Data.IsUsed)
1298             continue;
1299           if (Data.V == Op) {
1300             FoundCandidate = true;
1301             Data.IsUsed = true;
1302             break;
1303           }
1304         }
1305         if (!FoundCandidate)
1306           return false;
1307       }
1308       return true;
1309     }
1310
1311   public:
1312     /// Initialize with all the operands of the instruction vector \p RootVL.
1313     VLOperands(ArrayRef<Value *> RootVL, const DataLayout &DL,
1314                ScalarEvolution &SE, const BoUpSLP &R)
1315         : DL(DL), SE(SE), R(R) {
1316       // Append all the operands of RootVL.
1317       appendOperandsOfVL(RootVL);
1318     }
1319
1320     /// \Returns a value vector with the operands across all lanes for the
1321     /// opearnd at \p OpIdx.
1322     ValueList getVL(unsigned OpIdx) const {
1323       ValueList OpVL(OpsVec[OpIdx].size());
1324       assert(OpsVec[OpIdx].size() == getNumLanes() &&
1325              "Expected same num of lanes across all operands");
1326       for (unsigned Lane = 0, Lanes = getNumLanes(); Lane != Lanes; ++Lane)
1327         OpVL[Lane] = OpsVec[OpIdx][Lane].V;
1328       return OpVL;
1329     }
1330
1331     // Performs operand reordering for 2 or more operands.
1332     // The original operands are in OrigOps[OpIdx][Lane].
1333     // The reordered operands are returned in 'SortedOps[OpIdx][Lane]'.
1334     void reorder() {
1335       unsigned NumOperands = getNumOperands();
1336       unsigned NumLanes = getNumLanes();
1337       // Each operand has its own mode. We are using this mode to help us select
1338       // the instructions for each lane, so that they match best with the ones
1339       // we have selected so far.
1340       SmallVector<ReorderingMode, 2> ReorderingModes(NumOperands);
1341
1342       // This is a greedy single-pass algorithm. We are going over each lane
1343       // once and deciding on the best order right away with no back-tracking.
1344       // However, in order to increase its effectiveness, we start with the lane
1345       // that has operands that can move the least. For example, given the
1346       // following lanes:
1347       //  Lane 0 : A[0] = B[0] + C[0]   // Visited 3rd
1348       //  Lane 1 : A[1] = C[1] - B[1]   // Visited 1st
1349       //  Lane 2 : A[2] = B[2] + C[2]   // Visited 2nd
1350       //  Lane 3 : A[3] = C[3] - B[3]   // Visited 4th
1351       // we will start at Lane 1, since the operands of the subtraction cannot
1352       // be reordered. Then we will visit the rest of the lanes in a circular
1353       // fashion. That is, Lanes 2, then Lane 0, and finally Lane 3.
1354
1355       // Find the first lane that we will start our search from.
1356       unsigned FirstLane = getBestLaneToStartReordering();
1357
1358       // Initialize the modes.
1359       for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) {
1360         Value *OpLane0 = getValue(OpIdx, FirstLane);
1361         // Keep track if we have instructions with all the same opcode on one
1362         // side.
1363         if (isa<LoadInst>(OpLane0))
1364           ReorderingModes[OpIdx] = ReorderingMode::Load;
1365         else if (isa<Instruction>(OpLane0)) {
1366           // Check if OpLane0 should be broadcast.
1367           if (shouldBroadcast(OpLane0, OpIdx, FirstLane))
1368             ReorderingModes[OpIdx] = ReorderingMode::Splat;
1369           else
1370             ReorderingModes[OpIdx] = ReorderingMode::Opcode;
1371         }
1372         else if (isa<Constant>(OpLane0))
1373           ReorderingModes[OpIdx] = ReorderingMode::Constant;
1374         else if (isa<Argument>(OpLane0))
1375           // Our best hope is a Splat. It may save some cost in some cases.
1376           ReorderingModes[OpIdx] = ReorderingMode::Splat;
1377         else
1378           // NOTE: This should be unreachable.
1379           ReorderingModes[OpIdx] = ReorderingMode::Failed;
1380       }
1381
1382       // If the initial strategy fails for any of the operand indexes, then we
1383       // perform reordering again in a second pass. This helps avoid assigning
1384       // high priority to the failed strategy, and should improve reordering for
1385       // the non-failed operand indexes.
1386       for (int Pass = 0; Pass != 2; ++Pass) {
1387         // Skip the second pass if the first pass did not fail.
1388         bool StrategyFailed = false;
1389         // Mark all operand data as free to use.
1390         clearUsed();
1391         // We keep the original operand order for the FirstLane, so reorder the
1392         // rest of the lanes. We are visiting the nodes in a circular fashion,
1393         // using FirstLane as the center point and increasing the radius
1394         // distance.
1395         for (unsigned Distance = 1; Distance != NumLanes; ++Distance) {
1396           // Visit the lane on the right and then the lane on the left.
1397           for (int Direction : {+1, -1}) {
1398             int Lane = FirstLane + Direction * Distance;
1399             if (Lane < 0 || Lane >= (int)NumLanes)
1400               continue;
1401             int LastLane = Lane - Direction;
1402             assert(LastLane >= 0 && LastLane < (int)NumLanes &&
1403                    "Out of bounds");
1404             // Look for a good match for each operand.
1405             for (unsigned OpIdx = 0; OpIdx != NumOperands; ++OpIdx) {
1406               // Search for the operand that matches SortedOps[OpIdx][Lane-1].
1407               Optional<unsigned> BestIdx =
1408                   getBestOperand(OpIdx, Lane, LastLane, ReorderingModes);
1409               // By not selecting a value, we allow the operands that follow to
1410               // select a better matching value. We will get a non-null value in
1411               // the next run of getBestOperand().
1412               if (BestIdx) {
1413                 // Swap the current operand with the one returned by
1414                 // getBestOperand().
1415                 swap(OpIdx, BestIdx.getValue(), Lane);
1416               } else {
1417                 // We failed to find a best operand, set mode to 'Failed'.
1418                 ReorderingModes[OpIdx] = ReorderingMode::Failed;
1419                 // Enable the second pass.
1420                 StrategyFailed = true;
1421               }
1422             }
1423           }
1424         }
1425         // Skip second pass if the strategy did not fail.
1426         if (!StrategyFailed)
1427           break;
1428       }
1429     }
1430
1431 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1432     LLVM_DUMP_METHOD static StringRef getModeStr(ReorderingMode RMode) {
1433       switch (RMode) {
1434       case ReorderingMode::Load:
1435         return "Load";
1436       case ReorderingMode::Opcode:
1437         return "Opcode";
1438       case ReorderingMode::Constant:
1439         return "Constant";
1440       case ReorderingMode::Splat:
1441         return "Splat";
1442       case ReorderingMode::Failed:
1443         return "Failed";
1444       }
1445       llvm_unreachable("Unimplemented Reordering Type");
1446     }
1447
1448     LLVM_DUMP_METHOD static raw_ostream &printMode(ReorderingMode RMode,
1449                                                    raw_ostream &OS) {
1450       return OS << getModeStr(RMode);
1451     }
1452
1453     /// Debug print.
1454     LLVM_DUMP_METHOD static void dumpMode(ReorderingMode RMode) {
1455       printMode(RMode, dbgs());
1456     }
1457
1458     friend raw_ostream &operator<<(raw_ostream &OS, ReorderingMode RMode) {
1459       return printMode(RMode, OS);
1460     }
1461
1462     LLVM_DUMP_METHOD raw_ostream &print(raw_ostream &OS) const {
1463       const unsigned Indent = 2;
1464       unsigned Cnt = 0;
1465       for (const OperandDataVec &OpDataVec : OpsVec) {
1466         OS << "Operand " << Cnt++ << "\n";
1467         for (const OperandData &OpData : OpDataVec) {
1468           OS.indent(Indent) << "{";
1469           if (Value *V = OpData.V)
1470             OS << *V;
1471           else
1472             OS << "null";
1473           OS << ", APO:" << OpData.APO << "}\n";
1474         }
1475         OS << "\n";
1476       }
1477       return OS;
1478     }
1479
1480     /// Debug print.
1481     LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
1482 #endif
1483   };
1484
1485   /// Checks if the instruction is marked for deletion.
1486   bool isDeleted(Instruction *I) const { return DeletedInstructions.count(I); }
1487
1488   /// Marks values operands for later deletion by replacing them with Undefs.
1489   void eraseInstructions(ArrayRef<Value *> AV);
1490
1491   ~BoUpSLP();
1492
1493 private:
1494   /// Checks if all users of \p I are the part of the vectorization tree.
1495   bool areAllUsersVectorized(Instruction *I) const;
1496
1497   /// \returns the cost of the vectorizable entry.
1498   InstructionCost getEntryCost(TreeEntry *E);
1499
1500   /// This is the recursive part of buildTree.
1501   void buildTree_rec(ArrayRef<Value *> Roots, unsigned Depth,
1502                      const EdgeInfo &EI);
1503
1504   /// \returns true if the ExtractElement/ExtractValue instructions in \p VL can
1505   /// be vectorized to use the original vector (or aggregate "bitcast" to a
1506   /// vector) and sets \p CurrentOrder to the identity permutation; otherwise
1507   /// returns false, setting \p CurrentOrder to either an empty vector or a
1508   /// non-identity permutation that allows to reuse extract instructions.
1509   bool canReuseExtract(ArrayRef<Value *> VL, Value *OpValue,
1510                        SmallVectorImpl<unsigned> &CurrentOrder) const;
1511
1512   /// Vectorize a single entry in the tree.
1513   Value *vectorizeTree(TreeEntry *E);
1514
1515   /// Vectorize a single entry in the tree, starting in \p VL.
1516   Value *vectorizeTree(ArrayRef<Value *> VL);
1517
1518   /// \returns the scalarization cost for this type. Scalarization in this
1519   /// context means the creation of vectors from a group of scalars.
1520   InstructionCost
1521   getGatherCost(FixedVectorType *Ty,
1522                 const DenseSet<unsigned> &ShuffledIndices) const;
1523
1524   /// \returns the scalarization cost for this list of values. Assuming that
1525   /// this subtree gets vectorized, we may need to extract the values from the
1526   /// roots. This method calculates the cost of extracting the values.
1527   InstructionCost getGatherCost(ArrayRef<Value *> VL) const;
1528
1529   /// Set the Builder insert point to one after the last instruction in
1530   /// the bundle
1531   void setInsertPointAfterBundle(TreeEntry *E);
1532
1533   /// \returns a vector from a collection of scalars in \p VL.
1534   Value *gather(ArrayRef<Value *> VL);
1535
1536   /// \returns whether the VectorizableTree is fully vectorizable and will
1537   /// be beneficial even the tree height is tiny.
1538   bool isFullyVectorizableTinyTree() const;
1539
1540   /// Reorder commutative or alt operands to get better probability of
1541   /// generating vectorized code.
1542   static void reorderInputsAccordingToOpcode(ArrayRef<Value *> VL,
1543                                              SmallVectorImpl<Value *> &Left,
1544                                              SmallVectorImpl<Value *> &Right,
1545                                              const DataLayout &DL,
1546                                              ScalarEvolution &SE,
1547                                              const BoUpSLP &R);
1548   struct TreeEntry {
1549     using VecTreeTy = SmallVector<std::unique_ptr<TreeEntry>, 8>;
1550     TreeEntry(VecTreeTy &Container) : Container(Container) {}
1551
1552     /// \returns true if the scalars in VL are equal to this entry.
1553     bool isSame(ArrayRef<Value *> VL) const {
1554       if (VL.size() == Scalars.size())
1555         return std::equal(VL.begin(), VL.end(), Scalars.begin());
1556       return VL.size() == ReuseShuffleIndices.size() &&
1557              std::equal(
1558                  VL.begin(), VL.end(), ReuseShuffleIndices.begin(),
1559                  [this](Value *V, int Idx) { return V == Scalars[Idx]; });
1560     }
1561
1562     /// A vector of scalars.
1563     ValueList Scalars;
1564
1565     /// The Scalars are vectorized into this value. It is initialized to Null.
1566     Value *VectorizedValue = nullptr;
1567
1568     /// Do we need to gather this sequence or vectorize it
1569     /// (either with vector instruction or with scatter/gather
1570     /// intrinsics for store/load)?
1571     enum EntryState { Vectorize, ScatterVectorize, NeedToGather };
1572     EntryState State;
1573
1574     /// Does this sequence require some shuffling?
1575     SmallVector<int, 4> ReuseShuffleIndices;
1576
1577     /// Does this entry require reordering?
1578     SmallVector<unsigned, 4> ReorderIndices;
1579
1580     /// Points back to the VectorizableTree.
1581     ///
1582     /// Only used for Graphviz right now.  Unfortunately GraphTrait::NodeRef has
1583     /// to be a pointer and needs to be able to initialize the child iterator.
1584     /// Thus we need a reference back to the container to translate the indices
1585     /// to entries.
1586     VecTreeTy &Container;
1587
1588     /// The TreeEntry index containing the user of this entry.  We can actually
1589     /// have multiple users so the data structure is not truly a tree.
1590     SmallVector<EdgeInfo, 1> UserTreeIndices;
1591
1592     /// The index of this treeEntry in VectorizableTree.
1593     int Idx = -1;
1594
1595   private:
1596     /// The operands of each instruction in each lane Operands[op_index][lane].
1597     /// Note: This helps avoid the replication of the code that performs the
1598     /// reordering of operands during buildTree_rec() and vectorizeTree().
1599     SmallVector<ValueList, 2> Operands;
1600
1601     /// The main/alternate instruction.
1602     Instruction *MainOp = nullptr;
1603     Instruction *AltOp = nullptr;
1604
1605   public:
1606     /// Set this bundle's \p OpIdx'th operand to \p OpVL.
1607     void setOperand(unsigned OpIdx, ArrayRef<Value *> OpVL) {
1608       if (Operands.size() < OpIdx + 1)
1609         Operands.resize(OpIdx + 1);
1610       assert(Operands[OpIdx].size() == 0 && "Already resized?");
1611       Operands[OpIdx].resize(Scalars.size());
1612       for (unsigned Lane = 0, E = Scalars.size(); Lane != E; ++Lane)
1613         Operands[OpIdx][Lane] = OpVL[Lane];
1614     }
1615
1616     /// Set the operands of this bundle in their original order.
1617     void setOperandsInOrder() {
1618       assert(Operands.empty() && "Already initialized?");
1619       auto *I0 = cast<Instruction>(Scalars[0]);
1620       Operands.resize(I0->getNumOperands());
1621       unsigned NumLanes = Scalars.size();
1622       for (unsigned OpIdx = 0, NumOperands = I0->getNumOperands();
1623            OpIdx != NumOperands; ++OpIdx) {
1624         Operands[OpIdx].resize(NumLanes);
1625         for (unsigned Lane = 0; Lane != NumLanes; ++Lane) {
1626           auto *I = cast<Instruction>(Scalars[Lane]);
1627           assert(I->getNumOperands() == NumOperands &&
1628                  "Expected same number of operands");
1629           Operands[OpIdx][Lane] = I->getOperand(OpIdx);
1630         }
1631       }
1632     }
1633
1634     /// \returns the \p OpIdx operand of this TreeEntry.
1635     ValueList &getOperand(unsigned OpIdx) {
1636       assert(OpIdx < Operands.size() && "Off bounds");
1637       return Operands[OpIdx];
1638     }
1639
1640     /// \returns the number of operands.
1641     unsigned getNumOperands() const { return Operands.size(); }
1642
1643     /// \return the single \p OpIdx operand.
1644     Value *getSingleOperand(unsigned OpIdx) const {
1645       assert(OpIdx < Operands.size() && "Off bounds");
1646       assert(!Operands[OpIdx].empty() && "No operand available");
1647       return Operands[OpIdx][0];
1648     }
1649
1650     /// Some of the instructions in the list have alternate opcodes.
1651     bool isAltShuffle() const {
1652       return getOpcode() != getAltOpcode();
1653     }
1654
1655     bool isOpcodeOrAlt(Instruction *I) const {
1656       unsigned CheckedOpcode = I->getOpcode();
1657       return (getOpcode() == CheckedOpcode ||
1658               getAltOpcode() == CheckedOpcode);
1659     }
1660
1661     /// Chooses the correct key for scheduling data. If \p Op has the same (or
1662     /// alternate) opcode as \p OpValue, the key is \p Op. Otherwise the key is
1663     /// \p OpValue.
1664     Value *isOneOf(Value *Op) const {
1665       auto *I = dyn_cast<Instruction>(Op);
1666       if (I && isOpcodeOrAlt(I))
1667         return Op;
1668       return MainOp;
1669     }
1670
1671     void setOperations(const InstructionsState &S) {
1672       MainOp = S.MainOp;
1673       AltOp = S.AltOp;
1674     }
1675
1676     Instruction *getMainOp() const {
1677       return MainOp;
1678     }
1679
1680     Instruction *getAltOp() const {
1681       return AltOp;
1682     }
1683
1684     /// The main/alternate opcodes for the list of instructions.
1685     unsigned getOpcode() const {
1686       return MainOp ? MainOp->getOpcode() : 0;
1687     }
1688
1689     unsigned getAltOpcode() const {
1690       return AltOp ? AltOp->getOpcode() : 0;
1691     }
1692
1693     /// Update operations state of this entry if reorder occurred.
1694     bool updateStateIfReorder() {
1695       if (ReorderIndices.empty())
1696         return false;
1697       InstructionsState S = getSameOpcode(Scalars, ReorderIndices.front());
1698       setOperations(S);
1699       return true;
1700     }
1701
1702 #ifndef NDEBUG
1703     /// Debug printer.
1704     LLVM_DUMP_METHOD void dump() const {
1705       dbgs() << Idx << ".\n";
1706       for (unsigned OpI = 0, OpE = Operands.size(); OpI != OpE; ++OpI) {
1707         dbgs() << "Operand " << OpI << ":\n";
1708         for (const Value *V : Operands[OpI])
1709           dbgs().indent(2) << *V << "\n";
1710       }
1711       dbgs() << "Scalars: \n";
1712       for (Value *V : Scalars)
1713         dbgs().indent(2) << *V << "\n";
1714       dbgs() << "State: ";
1715       switch (State) {
1716       case Vectorize:
1717         dbgs() << "Vectorize\n";
1718         break;
1719       case ScatterVectorize:
1720         dbgs() << "ScatterVectorize\n";
1721         break;
1722       case NeedToGather:
1723         dbgs() << "NeedToGather\n";
1724         break;
1725       }
1726       dbgs() << "MainOp: ";
1727       if (MainOp)
1728         dbgs() << *MainOp << "\n";
1729       else
1730         dbgs() << "NULL\n";
1731       dbgs() << "AltOp: ";
1732       if (AltOp)
1733         dbgs() << *AltOp << "\n";
1734       else
1735         dbgs() << "NULL\n";
1736       dbgs() << "VectorizedValue: ";
1737       if (VectorizedValue)
1738         dbgs() << *VectorizedValue << "\n";
1739       else
1740         dbgs() << "NULL\n";
1741       dbgs() << "ReuseShuffleIndices: ";
1742       if (ReuseShuffleIndices.empty())
1743         dbgs() << "Empty";
1744       else
1745         for (unsigned ReuseIdx : ReuseShuffleIndices)
1746           dbgs() << ReuseIdx << ", ";
1747       dbgs() << "\n";
1748       dbgs() << "ReorderIndices: ";
1749       for (unsigned ReorderIdx : ReorderIndices)
1750         dbgs() << ReorderIdx << ", ";
1751       dbgs() << "\n";
1752       dbgs() << "UserTreeIndices: ";
1753       for (const auto &EInfo : UserTreeIndices)
1754         dbgs() << EInfo << ", ";
1755       dbgs() << "\n";
1756     }
1757 #endif
1758   };
1759
1760 #ifndef NDEBUG
1761   void dumpTreeCosts(TreeEntry *E, InstructionCost ReuseShuffleCost,
1762                      InstructionCost VecCost,
1763                      InstructionCost ScalarCost) const {
1764     dbgs() << "SLP: Calculated costs for Tree:\n"; E->dump();
1765     dbgs() << "SLP: Costs:\n";
1766     dbgs() << "SLP:     ReuseShuffleCost = " << ReuseShuffleCost << "\n";
1767     dbgs() << "SLP:     VectorCost = " << VecCost << "\n";
1768     dbgs() << "SLP:     ScalarCost = " << ScalarCost << "\n";
1769     dbgs() << "SLP:     ReuseShuffleCost + VecCost - ScalarCost = " <<
1770                ReuseShuffleCost + VecCost - ScalarCost << "\n";
1771   }
1772 #endif
1773
1774   /// Create a new VectorizableTree entry.
1775   TreeEntry *newTreeEntry(ArrayRef<Value *> VL, Optional<ScheduleData *> Bundle,
1776                           const InstructionsState &S,
1777                           const EdgeInfo &UserTreeIdx,
1778                           ArrayRef<unsigned> ReuseShuffleIndices = None,
1779                           ArrayRef<unsigned> ReorderIndices = None) {
1780     TreeEntry::EntryState EntryState =
1781         Bundle ? TreeEntry::Vectorize : TreeEntry::NeedToGather;
1782     return newTreeEntry(VL, EntryState, Bundle, S, UserTreeIdx,
1783                         ReuseShuffleIndices, ReorderIndices);
1784   }
1785
1786   TreeEntry *newTreeEntry(ArrayRef<Value *> VL,
1787                           TreeEntry::EntryState EntryState,
1788                           Optional<ScheduleData *> Bundle,
1789                           const InstructionsState &S,
1790                           const EdgeInfo &UserTreeIdx,
1791                           ArrayRef<unsigned> ReuseShuffleIndices = None,
1792                           ArrayRef<unsigned> ReorderIndices = None) {
1793     assert(((!Bundle && EntryState == TreeEntry::NeedToGather) ||
1794             (Bundle && EntryState != TreeEntry::NeedToGather)) &&
1795            "Need to vectorize gather entry?");
1796     VectorizableTree.push_back(std::make_unique<TreeEntry>(VectorizableTree));
1797     TreeEntry *Last = VectorizableTree.back().get();
1798     Last->Idx = VectorizableTree.size() - 1;
1799     Last->Scalars.insert(Last->Scalars.begin(), VL.begin(), VL.end());
1800     Last->State = EntryState;
1801     Last->ReuseShuffleIndices.append(ReuseShuffleIndices.begin(),
1802                                      ReuseShuffleIndices.end());
1803     Last->ReorderIndices.append(ReorderIndices.begin(), ReorderIndices.end());
1804     Last->setOperations(S);
1805     if (Last->State != TreeEntry::NeedToGather) {
1806       for (Value *V : VL) {
1807         assert(!getTreeEntry(V) && "Scalar already in tree!");
1808         ScalarToTreeEntry[V] = Last;
1809       }
1810       // Update the scheduler bundle to point to this TreeEntry.
1811       unsigned Lane = 0;
1812       for (ScheduleData *BundleMember = Bundle.getValue(); BundleMember;
1813            BundleMember = BundleMember->NextInBundle) {
1814         BundleMember->TE = Last;
1815         BundleMember->Lane = Lane;
1816         ++Lane;
1817       }
1818       assert((!Bundle.getValue() || Lane == VL.size()) &&
1819              "Bundle and VL out of sync");
1820     } else {
1821       MustGather.insert(VL.begin(), VL.end());
1822     }
1823
1824     if (UserTreeIdx.UserTE)
1825       Last->UserTreeIndices.push_back(UserTreeIdx);
1826
1827     return Last;
1828   }
1829
1830   /// -- Vectorization State --
1831   /// Holds all of the tree entries.
1832   TreeEntry::VecTreeTy VectorizableTree;
1833
1834 #ifndef NDEBUG
1835   /// Debug printer.
1836   LLVM_DUMP_METHOD void dumpVectorizableTree() const {
1837     for (unsigned Id = 0, IdE = VectorizableTree.size(); Id != IdE; ++Id) {
1838       VectorizableTree[Id]->dump();
1839       dbgs() << "\n";
1840     }
1841   }
1842 #endif
1843
1844   TreeEntry *getTreeEntry(Value *V) { return ScalarToTreeEntry.lookup(V); }
1845
1846   const TreeEntry *getTreeEntry(Value *V) const {
1847     return ScalarToTreeEntry.lookup(V);
1848   }
1849
1850   /// Maps a specific scalar to its tree entry.
1851   SmallDenseMap<Value*, TreeEntry *> ScalarToTreeEntry;
1852
1853   /// Maps a value to the proposed vectorizable size.
1854   SmallDenseMap<Value *, unsigned> InstrElementSize;
1855
1856   /// A list of scalars that we found that we need to keep as scalars.
1857   ValueSet MustGather;
1858
1859   /// This POD struct describes one external user in the vectorized tree.
1860   struct ExternalUser {
1861     ExternalUser(Value *S, llvm::User *U, int L)
1862         : Scalar(S), User(U), Lane(L) {}
1863
1864     // Which scalar in our function.
1865     Value *Scalar;
1866
1867     // Which user that uses the scalar.
1868     llvm::User *User;
1869
1870     // Which lane does the scalar belong to.
1871     int Lane;
1872   };
1873   using UserList = SmallVector<ExternalUser, 16>;
1874
1875   /// Checks if two instructions may access the same memory.
1876   ///
1877   /// \p Loc1 is the location of \p Inst1. It is passed explicitly because it
1878   /// is invariant in the calling loop.
1879   bool isAliased(const MemoryLocation &Loc1, Instruction *Inst1,
1880                  Instruction *Inst2) {
1881     // First check if the result is already in the cache.
1882     AliasCacheKey key = std::make_pair(Inst1, Inst2);
1883     Optional<bool> &result = AliasCache[key];
1884     if (result.hasValue()) {
1885       return result.getValue();
1886     }
1887     MemoryLocation Loc2 = getLocation(Inst2, AA);
1888     bool aliased = true;
1889     if (Loc1.Ptr && Loc2.Ptr && isSimple(Inst1) && isSimple(Inst2)) {
1890       // Do the alias check.
1891       aliased = AA->alias(Loc1, Loc2);
1892     }
1893     // Store the result in the cache.
1894     result = aliased;
1895     return aliased;
1896   }
1897
1898   using AliasCacheKey = std::pair<Instruction *, Instruction *>;
1899
1900   /// Cache for alias results.
1901   /// TODO: consider moving this to the AliasAnalysis itself.
1902   DenseMap<AliasCacheKey, Optional<bool>> AliasCache;
1903
1904   /// Removes an instruction from its block and eventually deletes it.
1905   /// It's like Instruction::eraseFromParent() except that the actual deletion
1906   /// is delayed until BoUpSLP is destructed.
1907   /// This is required to ensure that there are no incorrect collisions in the
1908   /// AliasCache, which can happen if a new instruction is allocated at the
1909   /// same address as a previously deleted instruction.
1910   void eraseInstruction(Instruction *I, bool ReplaceOpsWithUndef = false) {
1911     auto It = DeletedInstructions.try_emplace(I, ReplaceOpsWithUndef).first;
1912     It->getSecond() = It->getSecond() && ReplaceOpsWithUndef;
1913   }
1914
1915   /// Temporary store for deleted instructions. Instructions will be deleted
1916   /// eventually when the BoUpSLP is destructed.
1917   DenseMap<Instruction *, bool> DeletedInstructions;
1918
1919   /// A list of values that need to extracted out of the tree.
1920   /// This list holds pairs of (Internal Scalar : External User). External User
1921   /// can be nullptr, it means that this Internal Scalar will be used later,
1922   /// after vectorization.
1923   UserList ExternalUses;
1924
1925   /// Values used only by @llvm.assume calls.
1926   SmallPtrSet<const Value *, 32> EphValues;
1927
1928   /// Holds all of the instructions that we gathered.
1929   SetVector<Instruction *> GatherSeq;
1930
1931   /// A list of blocks that we are going to CSE.
1932   SetVector<BasicBlock *> CSEBlocks;
1933
1934   /// Contains all scheduling relevant data for an instruction.
1935   /// A ScheduleData either represents a single instruction or a member of an
1936   /// instruction bundle (= a group of instructions which is combined into a
1937   /// vector instruction).
1938   struct ScheduleData {
1939     // The initial value for the dependency counters. It means that the
1940     // dependencies are not calculated yet.
1941     enum { InvalidDeps = -1 };
1942
1943     ScheduleData() = default;
1944
1945     void init(int BlockSchedulingRegionID, Value *OpVal) {
1946       FirstInBundle = this;
1947       NextInBundle = nullptr;
1948       NextLoadStore = nullptr;
1949       IsScheduled = false;
1950       SchedulingRegionID = BlockSchedulingRegionID;
1951       UnscheduledDepsInBundle = UnscheduledDeps;
1952       clearDependencies();
1953       OpValue = OpVal;
1954       TE = nullptr;
1955       Lane = -1;
1956     }
1957
1958     /// Returns true if the dependency information has been calculated.
1959     bool hasValidDependencies() const { return Dependencies != InvalidDeps; }
1960
1961     /// Returns true for single instructions and for bundle representatives
1962     /// (= the head of a bundle).
1963     bool isSchedulingEntity() const { return FirstInBundle == this; }
1964
1965     /// Returns true if it represents an instruction bundle and not only a
1966     /// single instruction.
1967     bool isPartOfBundle() const {
1968       return NextInBundle != nullptr || FirstInBundle != this;
1969     }
1970
1971     /// Returns true if it is ready for scheduling, i.e. it has no more
1972     /// unscheduled depending instructions/bundles.
1973     bool isReady() const {
1974       assert(isSchedulingEntity() &&
1975              "can't consider non-scheduling entity for ready list");
1976       return UnscheduledDepsInBundle == 0 && !IsScheduled;
1977     }
1978
1979     /// Modifies the number of unscheduled dependencies, also updating it for
1980     /// the whole bundle.
1981     int incrementUnscheduledDeps(int Incr) {
1982       UnscheduledDeps += Incr;
1983       return FirstInBundle->UnscheduledDepsInBundle += Incr;
1984     }
1985
1986     /// Sets the number of unscheduled dependencies to the number of
1987     /// dependencies.
1988     void resetUnscheduledDeps() {
1989       incrementUnscheduledDeps(Dependencies - UnscheduledDeps);
1990     }
1991
1992     /// Clears all dependency information.
1993     void clearDependencies() {
1994       Dependencies = InvalidDeps;
1995       resetUnscheduledDeps();
1996       MemoryDependencies.clear();
1997     }
1998
1999     void dump(raw_ostream &os) const {
2000       if (!isSchedulingEntity()) {
2001         os << "/ " << *Inst;
2002       } else if (NextInBundle) {
2003         os << '[' << *Inst;
2004         ScheduleData *SD = NextInBundle;
2005         while (SD) {
2006           os << ';' << *SD->Inst;
2007           SD = SD->NextInBundle;
2008         }
2009         os << ']';
2010       } else {
2011         os << *Inst;
2012       }
2013     }
2014
2015     Instruction *Inst = nullptr;
2016
2017     /// Points to the head in an instruction bundle (and always to this for
2018     /// single instructions).
2019     ScheduleData *FirstInBundle = nullptr;
2020
2021     /// Single linked list of all instructions in a bundle. Null if it is a
2022     /// single instruction.
2023     ScheduleData *NextInBundle = nullptr;
2024
2025     /// Single linked list of all memory instructions (e.g. load, store, call)
2026     /// in the block - until the end of the scheduling region.
2027     ScheduleData *NextLoadStore = nullptr;
2028
2029     /// The dependent memory instructions.
2030     /// This list is derived on demand in calculateDependencies().
2031     SmallVector<ScheduleData *, 4> MemoryDependencies;
2032
2033     /// This ScheduleData is in the current scheduling region if this matches
2034     /// the current SchedulingRegionID of BlockScheduling.
2035     int SchedulingRegionID = 0;
2036
2037     /// Used for getting a "good" final ordering of instructions.
2038     int SchedulingPriority = 0;
2039
2040     /// The number of dependencies. Constitutes of the number of users of the
2041     /// instruction plus the number of dependent memory instructions (if any).
2042     /// This value is calculated on demand.
2043     /// If InvalidDeps, the number of dependencies is not calculated yet.
2044     int Dependencies = InvalidDeps;
2045
2046     /// The number of dependencies minus the number of dependencies of scheduled
2047     /// instructions. As soon as this is zero, the instruction/bundle gets ready
2048     /// for scheduling.
2049     /// Note that this is negative as long as Dependencies is not calculated.
2050     int UnscheduledDeps = InvalidDeps;
2051
2052     /// The sum of UnscheduledDeps in a bundle. Equals to UnscheduledDeps for
2053     /// single instructions.
2054     int UnscheduledDepsInBundle = InvalidDeps;
2055
2056     /// True if this instruction is scheduled (or considered as scheduled in the
2057     /// dry-run).
2058     bool IsScheduled = false;
2059
2060     /// Opcode of the current instruction in the schedule data.
2061     Value *OpValue = nullptr;
2062
2063     /// The TreeEntry that this instruction corresponds to.
2064     TreeEntry *TE = nullptr;
2065
2066     /// The lane of this node in the TreeEntry.
2067     int Lane = -1;
2068   };
2069
2070 #ifndef NDEBUG
2071   friend inline raw_ostream &operator<<(raw_ostream &os,
2072                                         const BoUpSLP::ScheduleData &SD) {
2073     SD.dump(os);
2074     return os;
2075   }
2076 #endif
2077
2078   friend struct GraphTraits<BoUpSLP *>;
2079   friend struct DOTGraphTraits<BoUpSLP *>;
2080
2081   /// Contains all scheduling data for a basic block.
2082   struct BlockScheduling {
2083     BlockScheduling(BasicBlock *BB)
2084         : BB(BB), ChunkSize(BB->size()), ChunkPos(ChunkSize) {}
2085
2086     void clear() {
2087       ReadyInsts.clear();
2088       ScheduleStart = nullptr;
2089       ScheduleEnd = nullptr;
2090       FirstLoadStoreInRegion = nullptr;
2091       LastLoadStoreInRegion = nullptr;
2092
2093       // Reduce the maximum schedule region size by the size of the
2094       // previous scheduling run.
2095       ScheduleRegionSizeLimit -= ScheduleRegionSize;
2096       if (ScheduleRegionSizeLimit < MinScheduleRegionSize)
2097         ScheduleRegionSizeLimit = MinScheduleRegionSize;
2098       ScheduleRegionSize = 0;
2099
2100       // Make a new scheduling region, i.e. all existing ScheduleData is not
2101       // in the new region yet.
2102       ++SchedulingRegionID;
2103     }
2104
2105     ScheduleData *getScheduleData(Value *V) {
2106       ScheduleData *SD = ScheduleDataMap[V];
2107       if (SD && SD->SchedulingRegionID == SchedulingRegionID)
2108         return SD;
2109       return nullptr;
2110     }
2111
2112     ScheduleData *getScheduleData(Value *V, Value *Key) {
2113       if (V == Key)
2114         return getScheduleData(V);
2115       auto I = ExtraScheduleDataMap.find(V);
2116       if (I != ExtraScheduleDataMap.end()) {
2117         ScheduleData *SD = I->second[Key];
2118         if (SD && SD->SchedulingRegionID == SchedulingRegionID)
2119           return SD;
2120       }
2121       return nullptr;
2122     }
2123
2124     bool isInSchedulingRegion(ScheduleData *SD) const {
2125       return SD->SchedulingRegionID == SchedulingRegionID;
2126     }
2127
2128     /// Marks an instruction as scheduled and puts all dependent ready
2129     /// instructions into the ready-list.
2130     template <typename ReadyListType>
2131     void schedule(ScheduleData *SD, ReadyListType &ReadyList) {
2132       SD->IsScheduled = true;
2133       LLVM_DEBUG(dbgs() << "SLP:   schedule " << *SD << "\n");
2134
2135       ScheduleData *BundleMember = SD;
2136       while (BundleMember) {
2137         if (BundleMember->Inst != BundleMember->OpValue) {
2138           BundleMember = BundleMember->NextInBundle;
2139           continue;
2140         }
2141         // Handle the def-use chain dependencies.
2142
2143         // Decrement the unscheduled counter and insert to ready list if ready.
2144         auto &&DecrUnsched = [this, &ReadyList](Instruction *I) {
2145           doForAllOpcodes(I, [&ReadyList](ScheduleData *OpDef) {
2146             if (OpDef && OpDef->hasValidDependencies() &&
2147                 OpDef->incrementUnscheduledDeps(-1) == 0) {
2148               // There are no more unscheduled dependencies after
2149               // decrementing, so we can put the dependent instruction
2150               // into the ready list.
2151               ScheduleData *DepBundle = OpDef->FirstInBundle;
2152               assert(!DepBundle->IsScheduled &&
2153                      "already scheduled bundle gets ready");
2154               ReadyList.insert(DepBundle);
2155               LLVM_DEBUG(dbgs()
2156                          << "SLP:    gets ready (def): " << *DepBundle << "\n");
2157             }
2158           });
2159         };
2160
2161         // If BundleMember is a vector bundle, its operands may have been
2162         // reordered duiring buildTree(). We therefore need to get its operands
2163         // through the TreeEntry.
2164         if (TreeEntry *TE = BundleMember->TE) {
2165           int Lane = BundleMember->Lane;
2166           assert(Lane >= 0 && "Lane not set");
2167
2168           // Since vectorization tree is being built recursively this assertion
2169           // ensures that the tree entry has all operands set before reaching
2170           // this code. Couple of exceptions known at the moment are extracts
2171           // where their second (immediate) operand is not added. Since
2172           // immediates do not affect scheduler behavior this is considered
2173           // okay.
2174           auto *In = TE->getMainOp();
2175           assert(In &&
2176                  (isa<ExtractValueInst>(In) || isa<ExtractElementInst>(In) ||
2177                   In->getNumOperands() == TE->getNumOperands()) &&
2178                  "Missed TreeEntry operands?");
2179           (void)In; // fake use to avoid build failure when assertions disabled
2180
2181           for (unsigned OpIdx = 0, NumOperands = TE->getNumOperands();
2182                OpIdx != NumOperands; ++OpIdx)
2183             if (auto *I = dyn_cast<Instruction>(TE->getOperand(OpIdx)[Lane]))
2184               DecrUnsched(I);
2185         } else {
2186           // If BundleMember is a stand-alone instruction, no operand reordering
2187           // has taken place, so we directly access its operands.
2188           for (Use &U : BundleMember->Inst->operands())
2189             if (auto *I = dyn_cast<Instruction>(U.get()))
2190               DecrUnsched(I);
2191         }
2192         // Handle the memory dependencies.
2193         for (ScheduleData *MemoryDepSD : BundleMember->MemoryDependencies) {
2194           if (MemoryDepSD->incrementUnscheduledDeps(-1) == 0) {
2195             // There are no more unscheduled dependencies after decrementing,
2196             // so we can put the dependent instruction into the ready list.
2197             ScheduleData *DepBundle = MemoryDepSD->FirstInBundle;
2198             assert(!DepBundle->IsScheduled &&
2199                    "already scheduled bundle gets ready");
2200             ReadyList.insert(DepBundle);
2201             LLVM_DEBUG(dbgs()
2202                        << "SLP:    gets ready (mem): " << *DepBundle << "\n");
2203           }
2204         }
2205         BundleMember = BundleMember->NextInBundle;
2206       }
2207     }
2208
2209     void doForAllOpcodes(Value *V,
2210                          function_ref<void(ScheduleData *SD)> Action) {
2211       if (ScheduleData *SD = getScheduleData(V))
2212         Action(SD);
2213       auto I = ExtraScheduleDataMap.find(V);
2214       if (I != ExtraScheduleDataMap.end())
2215         for (auto &P : I->second)
2216           if (P.second->SchedulingRegionID == SchedulingRegionID)
2217             Action(P.second);
2218     }
2219
2220     /// Put all instructions into the ReadyList which are ready for scheduling.
2221     template <typename ReadyListType>
2222     void initialFillReadyList(ReadyListType &ReadyList) {
2223       for (auto *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) {
2224         doForAllOpcodes(I, [&](ScheduleData *SD) {
2225           if (SD->isSchedulingEntity() && SD->isReady()) {
2226             ReadyList.insert(SD);
2227             LLVM_DEBUG(dbgs()
2228                        << "SLP:    initially in ready list: " << *I << "\n");
2229           }
2230         });
2231       }
2232     }
2233
2234     /// Checks if a bundle of instructions can be scheduled, i.e. has no
2235     /// cyclic dependencies. This is only a dry-run, no instructions are
2236     /// actually moved at this stage.
2237     /// \returns the scheduling bundle. The returned Optional value is non-None
2238     /// if \p VL is allowed to be scheduled.
2239     Optional<ScheduleData *>
2240     tryScheduleBundle(ArrayRef<Value *> VL, BoUpSLP *SLP,
2241                       const InstructionsState &S);
2242
2243     /// Un-bundles a group of instructions.
2244     void cancelScheduling(ArrayRef<Value *> VL, Value *OpValue);
2245
2246     /// Allocates schedule data chunk.
2247     ScheduleData *allocateScheduleDataChunks();
2248
2249     /// Extends the scheduling region so that V is inside the region.
2250     /// \returns true if the region size is within the limit.
2251     bool extendSchedulingRegion(Value *V, const InstructionsState &S);
2252
2253     /// Initialize the ScheduleData structures for new instructions in the
2254     /// scheduling region.
2255     void initScheduleData(Instruction *FromI, Instruction *ToI,
2256                           ScheduleData *PrevLoadStore,
2257                           ScheduleData *NextLoadStore);
2258
2259     /// Updates the dependency information of a bundle and of all instructions/
2260     /// bundles which depend on the original bundle.
2261     void calculateDependencies(ScheduleData *SD, bool InsertInReadyList,
2262                                BoUpSLP *SLP);
2263
2264     /// Sets all instruction in the scheduling region to un-scheduled.
2265     void resetSchedule();
2266
2267     BasicBlock *BB;
2268
2269     /// Simple memory allocation for ScheduleData.
2270     std::vector<std::unique_ptr<ScheduleData[]>> ScheduleDataChunks;
2271
2272     /// The size of a ScheduleData array in ScheduleDataChunks.
2273     int ChunkSize;
2274
2275     /// The allocator position in the current chunk, which is the last entry
2276     /// of ScheduleDataChunks.
2277     int ChunkPos;
2278
2279     /// Attaches ScheduleData to Instruction.
2280     /// Note that the mapping survives during all vectorization iterations, i.e.
2281     /// ScheduleData structures are recycled.
2282     DenseMap<Value *, ScheduleData *> ScheduleDataMap;
2283
2284     /// Attaches ScheduleData to Instruction with the leading key.
2285     DenseMap<Value *, SmallDenseMap<Value *, ScheduleData *>>
2286         ExtraScheduleDataMap;
2287
2288     struct ReadyList : SmallVector<ScheduleData *, 8> {
2289       void insert(ScheduleData *SD) { push_back(SD); }
2290     };
2291
2292     /// The ready-list for scheduling (only used for the dry-run).
2293     ReadyList ReadyInsts;
2294
2295     /// The first instruction of the scheduling region.
2296     Instruction *ScheduleStart = nullptr;
2297
2298     /// The first instruction _after_ the scheduling region.
2299     Instruction *ScheduleEnd = nullptr;
2300
2301     /// The first memory accessing instruction in the scheduling region
2302     /// (can be null).
2303     ScheduleData *FirstLoadStoreInRegion = nullptr;
2304
2305     /// The last memory accessing instruction in the scheduling region
2306     /// (can be null).
2307     ScheduleData *LastLoadStoreInRegion = nullptr;
2308
2309     /// The current size of the scheduling region.
2310     int ScheduleRegionSize = 0;
2311
2312     /// The maximum size allowed for the scheduling region.
2313     int ScheduleRegionSizeLimit = ScheduleRegionSizeBudget;
2314
2315     /// The ID of the scheduling region. For a new vectorization iteration this
2316     /// is incremented which "removes" all ScheduleData from the region.
2317     // Make sure that the initial SchedulingRegionID is greater than the
2318     // initial SchedulingRegionID in ScheduleData (which is 0).
2319     int SchedulingRegionID = 1;
2320   };
2321
2322   /// Attaches the BlockScheduling structures to basic blocks.
2323   MapVector<BasicBlock *, std::unique_ptr<BlockScheduling>> BlocksSchedules;
2324
2325   /// Performs the "real" scheduling. Done before vectorization is actually
2326   /// performed in a basic block.
2327   void scheduleBlock(BlockScheduling *BS);
2328
2329   /// List of users to ignore during scheduling and that don't need extracting.
2330   ArrayRef<Value *> UserIgnoreList;
2331
2332   /// A DenseMapInfo implementation for holding DenseMaps and DenseSets of
2333   /// sorted SmallVectors of unsigned.
2334   struct OrdersTypeDenseMapInfo {
2335     static OrdersType getEmptyKey() {
2336       OrdersType V;
2337       V.push_back(~1U);
2338       return V;
2339     }
2340
2341     static OrdersType getTombstoneKey() {
2342       OrdersType V;
2343       V.push_back(~2U);
2344       return V;
2345     }
2346
2347     static unsigned getHashValue(const OrdersType &V) {
2348       return static_cast<unsigned>(hash_combine_range(V.begin(), V.end()));
2349     }
2350
2351     static bool isEqual(const OrdersType &LHS, const OrdersType &RHS) {
2352       return LHS == RHS;
2353     }
2354   };
2355
2356   /// Contains orders of operations along with the number of bundles that have
2357   /// operations in this order. It stores only those orders that require
2358   /// reordering, if reordering is not required it is counted using \a
2359   /// NumOpsWantToKeepOriginalOrder.
2360   DenseMap<OrdersType, unsigned, OrdersTypeDenseMapInfo> NumOpsWantToKeepOrder;
2361   /// Number of bundles that do not require reordering.
2362   unsigned NumOpsWantToKeepOriginalOrder = 0;
2363
2364   // Analysis and block reference.
2365   Function *F;
2366   ScalarEvolution *SE;
2367   TargetTransformInfo *TTI;
2368   TargetLibraryInfo *TLI;
2369   AAResults *AA;
2370   LoopInfo *LI;
2371   DominatorTree *DT;
2372   AssumptionCache *AC;
2373   DemandedBits *DB;
2374   const DataLayout *DL;
2375   OptimizationRemarkEmitter *ORE;
2376
2377   unsigned MaxVecRegSize; // This is set by TTI or overridden by cl::opt.
2378   unsigned MinVecRegSize; // Set by cl::opt (default: 128).
2379
2380   /// Instruction builder to construct the vectorized tree.
2381   IRBuilder<> Builder;
2382
2383   /// A map of scalar integer values to the smallest bit width with which they
2384   /// can legally be represented. The values map to (width, signed) pairs,
2385   /// where "width" indicates the minimum bit width and "signed" is True if the
2386   /// value must be signed-extended, rather than zero-extended, back to its
2387   /// original width.
2388   MapVector<Value *, std::pair<uint64_t, bool>> MinBWs;
2389 };
2390
2391 } // end namespace slpvectorizer
2392
2393 template <> struct GraphTraits<BoUpSLP *> {
2394   using TreeEntry = BoUpSLP::TreeEntry;
2395
2396   /// NodeRef has to be a pointer per the GraphWriter.
2397   using NodeRef = TreeEntry *;
2398
2399   using ContainerTy = BoUpSLP::TreeEntry::VecTreeTy;
2400
2401   /// Add the VectorizableTree to the index iterator to be able to return
2402   /// TreeEntry pointers.
2403   struct ChildIteratorType
2404       : public iterator_adaptor_base<
2405             ChildIteratorType, SmallVector<BoUpSLP::EdgeInfo, 1>::iterator> {
2406     ContainerTy &VectorizableTree;
2407
2408     ChildIteratorType(SmallVector<BoUpSLP::EdgeInfo, 1>::iterator W,
2409                       ContainerTy &VT)
2410         : ChildIteratorType::iterator_adaptor_base(W), VectorizableTree(VT) {}
2411
2412     NodeRef operator*() { return I->UserTE; }
2413   };
2414
2415   static NodeRef getEntryNode(BoUpSLP &R) {
2416     return R.VectorizableTree[0].get();
2417   }
2418
2419   static ChildIteratorType child_begin(NodeRef N) {
2420     return {N->UserTreeIndices.begin(), N->Container};
2421   }
2422
2423   static ChildIteratorType child_end(NodeRef N) {
2424     return {N->UserTreeIndices.end(), N->Container};
2425   }
2426
2427   /// For the node iterator we just need to turn the TreeEntry iterator into a
2428   /// TreeEntry* iterator so that it dereferences to NodeRef.
2429   class nodes_iterator {
2430     using ItTy = ContainerTy::iterator;
2431     ItTy It;
2432
2433   public:
2434     nodes_iterator(const ItTy &It2) : It(It2) {}
2435     NodeRef operator*() { return It->get(); }
2436     nodes_iterator operator++() {
2437       ++It;
2438       return *this;
2439     }
2440     bool operator!=(const nodes_iterator &N2) const { return N2.It != It; }
2441   };
2442
2443   static nodes_iterator nodes_begin(BoUpSLP *R) {
2444     return nodes_iterator(R->VectorizableTree.begin());
2445   }
2446
2447   static nodes_iterator nodes_end(BoUpSLP *R) {
2448     return nodes_iterator(R->VectorizableTree.end());
2449   }
2450
2451   static unsigned size(BoUpSLP *R) { return R->VectorizableTree.size(); }
2452 };
2453
2454 template <> struct DOTGraphTraits<BoUpSLP *> : public DefaultDOTGraphTraits {
2455   using TreeEntry = BoUpSLP::TreeEntry;
2456
2457   DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
2458
2459   std::string getNodeLabel(const TreeEntry *Entry, const BoUpSLP *R) {
2460     std::string Str;
2461     raw_string_ostream OS(Str);
2462     if (isSplat(Entry->Scalars)) {
2463       OS << "<splat> " << *Entry->Scalars[0];
2464       return Str;
2465     }
2466     for (auto V : Entry->Scalars) {
2467       OS << *V;
2468       if (llvm::any_of(R->ExternalUses, [&](const BoUpSLP::ExternalUser &EU) {
2469             return EU.Scalar == V;
2470           }))
2471         OS << " <extract>";
2472       OS << "\n";
2473     }
2474     return Str;
2475   }
2476
2477   static std::string getNodeAttributes(const TreeEntry *Entry,
2478                                        const BoUpSLP *) {
2479     if (Entry->State == TreeEntry::NeedToGather)
2480       return "color=red";
2481     return "";
2482   }
2483 };
2484
2485 } // end namespace llvm
2486
2487 BoUpSLP::~BoUpSLP() {
2488   for (const auto &Pair : DeletedInstructions) {
2489     // Replace operands of ignored instructions with Undefs in case if they were
2490     // marked for deletion.
2491     if (Pair.getSecond()) {
2492       Value *Undef = UndefValue::get(Pair.getFirst()->getType());
2493       Pair.getFirst()->replaceAllUsesWith(Undef);
2494     }
2495     Pair.getFirst()->dropAllReferences();
2496   }
2497   for (const auto &Pair : DeletedInstructions) {
2498     assert(Pair.getFirst()->use_empty() &&
2499            "trying to erase instruction with users.");
2500     Pair.getFirst()->eraseFromParent();
2501   }
2502   assert(!verifyFunction(*F, &dbgs()));
2503 }
2504
2505 void BoUpSLP::eraseInstructions(ArrayRef<Value *> AV) {
2506   for (auto *V : AV) {
2507     if (auto *I = dyn_cast<Instruction>(V))
2508       eraseInstruction(I, /*ReplaceOpsWithUndef=*/true);
2509   };
2510 }
2511
2512 void BoUpSLP::buildTree(ArrayRef<Value *> Roots,
2513                         ArrayRef<Value *> UserIgnoreLst) {
2514   ExtraValueToDebugLocsMap ExternallyUsedValues;
2515   buildTree(Roots, ExternallyUsedValues, UserIgnoreLst);
2516 }
2517
2518 void BoUpSLP::buildTree(ArrayRef<Value *> Roots,
2519                         ExtraValueToDebugLocsMap &ExternallyUsedValues,
2520                         ArrayRef<Value *> UserIgnoreLst) {
2521   deleteTree();
2522   UserIgnoreList = UserIgnoreLst;
2523   if (!allSameType(Roots))
2524     return;
2525   buildTree_rec(Roots, 0, EdgeInfo());
2526
2527   // Collect the values that we need to extract from the tree.
2528   for (auto &TEPtr : VectorizableTree) {
2529     TreeEntry *Entry = TEPtr.get();
2530
2531     // No need to handle users of gathered values.
2532     if (Entry->State == TreeEntry::NeedToGather)
2533       continue;
2534
2535     // For each lane:
2536     for (int Lane = 0, LE = Entry->Scalars.size(); Lane != LE; ++Lane) {
2537       Value *Scalar = Entry->Scalars[Lane];
2538       int FoundLane = Lane;
2539       if (!Entry->ReuseShuffleIndices.empty()) {
2540         FoundLane =
2541             std::distance(Entry->ReuseShuffleIndices.begin(),
2542                           llvm::find(Entry->ReuseShuffleIndices, FoundLane));
2543       }
2544
2545       // Check if the scalar is externally used as an extra arg.
2546       auto ExtI = ExternallyUsedValues.find(Scalar);
2547       if (ExtI != ExternallyUsedValues.end()) {
2548         LLVM_DEBUG(dbgs() << "SLP: Need to extract: Extra arg from lane "
2549                           << Lane << " from " << *Scalar << ".\n");
2550         ExternalUses.emplace_back(Scalar, nullptr, FoundLane);
2551       }
2552       for (User *U : Scalar->users()) {
2553         LLVM_DEBUG(dbgs() << "SLP: Checking user:" << *U << ".\n");
2554
2555         Instruction *UserInst = dyn_cast<Instruction>(U);
2556         if (!UserInst)
2557           continue;
2558
2559         // Skip in-tree scalars that become vectors
2560         if (TreeEntry *UseEntry = getTreeEntry(U)) {
2561           Value *UseScalar = UseEntry->Scalars[0];
2562           // Some in-tree scalars will remain as scalar in vectorized
2563           // instructions. If that is the case, the one in Lane 0 will
2564           // be used.
2565           if (UseScalar != U ||
2566               !InTreeUserNeedToExtract(Scalar, UserInst, TLI)) {
2567             LLVM_DEBUG(dbgs() << "SLP: \tInternal user will be removed:" << *U
2568                               << ".\n");
2569             assert(UseEntry->State != TreeEntry::NeedToGather && "Bad state");
2570             continue;
2571           }
2572         }
2573
2574         // Ignore users in the user ignore list.
2575         if (is_contained(UserIgnoreList, UserInst))
2576           continue;
2577
2578         LLVM_DEBUG(dbgs() << "SLP: Need to extract:" << *U << " from lane "
2579                           << Lane << " from " << *Scalar << ".\n");
2580         ExternalUses.push_back(ExternalUser(Scalar, U, FoundLane));
2581       }
2582     }
2583   }
2584 }
2585
2586 void BoUpSLP::buildTree_rec(ArrayRef<Value *> VL, unsigned Depth,
2587                             const EdgeInfo &UserTreeIdx) {
2588   assert((allConstant(VL) || allSameType(VL)) && "Invalid types!");
2589
2590   InstructionsState S = getSameOpcode(VL);
2591   if (Depth == RecursionMaxDepth) {
2592     LLVM_DEBUG(dbgs() << "SLP: Gathering due to max recursion depth.\n");
2593     newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
2594     return;
2595   }
2596
2597   // Don't handle vectors.
2598   if (S.OpValue->getType()->isVectorTy()) {
2599     LLVM_DEBUG(dbgs() << "SLP: Gathering due to vector type.\n");
2600     newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
2601     return;
2602   }
2603
2604   if (StoreInst *SI = dyn_cast<StoreInst>(S.OpValue))
2605     if (SI->getValueOperand()->getType()->isVectorTy()) {
2606       LLVM_DEBUG(dbgs() << "SLP: Gathering due to store vector type.\n");
2607       newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
2608       return;
2609     }
2610
2611   // If all of the operands are identical or constant we have a simple solution.
2612   if (allConstant(VL) || isSplat(VL) || !allSameBlock(VL) || !S.getOpcode()) {
2613     LLVM_DEBUG(dbgs() << "SLP: Gathering due to C,S,B,O. \n");
2614     newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
2615     return;
2616   }
2617
2618   // We now know that this is a vector of instructions of the same type from
2619   // the same block.
2620
2621   // Don't vectorize ephemeral values.
2622   for (Value *V : VL) {
2623     if (EphValues.count(V)) {
2624       LLVM_DEBUG(dbgs() << "SLP: The instruction (" << *V
2625                         << ") is ephemeral.\n");
2626       newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
2627       return;
2628     }
2629   }
2630
2631   // Check if this is a duplicate of another entry.
2632   if (TreeEntry *E = getTreeEntry(S.OpValue)) {
2633     LLVM_DEBUG(dbgs() << "SLP: \tChecking bundle: " << *S.OpValue << ".\n");
2634     if (!E->isSame(VL)) {
2635       LLVM_DEBUG(dbgs() << "SLP: Gathering due to partial overlap.\n");
2636       newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
2637       return;
2638     }
2639     // Record the reuse of the tree node.  FIXME, currently this is only used to
2640     // properly draw the graph rather than for the actual vectorization.
2641     E->UserTreeIndices.push_back(UserTreeIdx);
2642     LLVM_DEBUG(dbgs() << "SLP: Perfect diamond merge at " << *S.OpValue
2643                       << ".\n");
2644     return;
2645   }
2646
2647   // Check that none of the instructions in the bundle are already in the tree.
2648   for (Value *V : VL) {
2649     auto *I = dyn_cast<Instruction>(V);
2650     if (!I)
2651       continue;
2652     if (getTreeEntry(I)) {
2653       LLVM_DEBUG(dbgs() << "SLP: The instruction (" << *V
2654                         << ") is already in tree.\n");
2655       newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
2656       return;
2657     }
2658   }
2659
2660   // If any of the scalars is marked as a value that needs to stay scalar, then
2661   // we need to gather the scalars.
2662   // The reduction nodes (stored in UserIgnoreList) also should stay scalar.
2663   for (Value *V : VL) {
2664     if (MustGather.count(V) || is_contained(UserIgnoreList, V)) {
2665       LLVM_DEBUG(dbgs() << "SLP: Gathering due to gathered scalar.\n");
2666       newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
2667       return;
2668     }
2669   }
2670
2671   // Check that all of the users of the scalars that we want to vectorize are
2672   // schedulable.
2673   auto *VL0 = cast<Instruction>(S.OpValue);
2674   BasicBlock *BB = VL0->getParent();
2675
2676   if (!DT->isReachableFromEntry(BB)) {
2677     // Don't go into unreachable blocks. They may contain instructions with
2678     // dependency cycles which confuse the final scheduling.
2679     LLVM_DEBUG(dbgs() << "SLP: bundle in unreachable block.\n");
2680     newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
2681     return;
2682   }
2683
2684   // Check that every instruction appears once in this bundle.
2685   SmallVector<unsigned, 4> ReuseShuffleIndicies;
2686   SmallVector<Value *, 4> UniqueValues;
2687   DenseMap<Value *, unsigned> UniquePositions;
2688   for (Value *V : VL) {
2689     auto Res = UniquePositions.try_emplace(V, UniqueValues.size());
2690     ReuseShuffleIndicies.emplace_back(Res.first->second);
2691     if (Res.second)
2692       UniqueValues.emplace_back(V);
2693   }
2694   size_t NumUniqueScalarValues = UniqueValues.size();
2695   if (NumUniqueScalarValues == VL.size()) {
2696     ReuseShuffleIndicies.clear();
2697   } else {
2698     LLVM_DEBUG(dbgs() << "SLP: Shuffle for reused scalars.\n");
2699     if (NumUniqueScalarValues <= 1 ||
2700         !llvm::isPowerOf2_32(NumUniqueScalarValues)) {
2701       LLVM_DEBUG(dbgs() << "SLP: Scalar used twice in bundle.\n");
2702       newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx);
2703       return;
2704     }
2705     VL = UniqueValues;
2706   }
2707
2708   auto &BSRef = BlocksSchedules[BB];
2709   if (!BSRef)
2710     BSRef = std::make_unique<BlockScheduling>(BB);
2711
2712   BlockScheduling &BS = *BSRef.get();
2713
2714   Optional<ScheduleData *> Bundle = BS.tryScheduleBundle(VL, this, S);
2715   if (!Bundle) {
2716     LLVM_DEBUG(dbgs() << "SLP: We are not able to schedule this bundle!\n");
2717     assert((!BS.getScheduleData(VL0) ||
2718             !BS.getScheduleData(VL0)->isPartOfBundle()) &&
2719            "tryScheduleBundle should cancelScheduling on failure");
2720     newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
2721                  ReuseShuffleIndicies);
2722     return;
2723   }
2724   LLVM_DEBUG(dbgs() << "SLP: We are able to schedule this bundle.\n");
2725
2726   unsigned ShuffleOrOp = S.isAltShuffle() ?
2727                 (unsigned) Instruction::ShuffleVector : S.getOpcode();
2728   switch (ShuffleOrOp) {
2729     case Instruction::PHI: {
2730       auto *PH = cast<PHINode>(VL0);
2731
2732       // Check for terminator values (e.g. invoke).
2733       for (Value *V : VL)
2734         for (unsigned I = 0, E = PH->getNumIncomingValues(); I < E; ++I) {
2735           Instruction *Term = dyn_cast<Instruction>(
2736               cast<PHINode>(V)->getIncomingValueForBlock(
2737                   PH->getIncomingBlock(I)));
2738           if (Term && Term->isTerminator()) {
2739             LLVM_DEBUG(dbgs()
2740                        << "SLP: Need to swizzle PHINodes (terminator use).\n");
2741             BS.cancelScheduling(VL, VL0);
2742             newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
2743                          ReuseShuffleIndicies);
2744             return;
2745           }
2746         }
2747
2748       TreeEntry *TE =
2749           newTreeEntry(VL, Bundle, S, UserTreeIdx, ReuseShuffleIndicies);
2750       LLVM_DEBUG(dbgs() << "SLP: added a vector of PHINodes.\n");
2751
2752       // Keeps the reordered operands to avoid code duplication.
2753       SmallVector<ValueList, 2> OperandsVec;
2754       for (unsigned I = 0, E = PH->getNumIncomingValues(); I < E; ++I) {
2755         ValueList Operands;
2756         // Prepare the operand vector.
2757         for (Value *V : VL)
2758           Operands.push_back(cast<PHINode>(V)->getIncomingValueForBlock(
2759               PH->getIncomingBlock(I)));
2760         TE->setOperand(I, Operands);
2761         OperandsVec.push_back(Operands);
2762       }
2763       for (unsigned OpIdx = 0, OpE = OperandsVec.size(); OpIdx != OpE; ++OpIdx)
2764         buildTree_rec(OperandsVec[OpIdx], Depth + 1, {TE, OpIdx});
2765       return;
2766     }
2767     case Instruction::ExtractValue:
2768     case Instruction::ExtractElement: {
2769       OrdersType CurrentOrder;
2770       bool Reuse = canReuseExtract(VL, VL0, CurrentOrder);
2771       if (Reuse) {
2772         LLVM_DEBUG(dbgs() << "SLP: Reusing or shuffling extract sequence.\n");
2773         ++NumOpsWantToKeepOriginalOrder;
2774         newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
2775                      ReuseShuffleIndicies);
2776         // This is a special case, as it does not gather, but at the same time
2777         // we are not extending buildTree_rec() towards the operands.
2778         ValueList Op0;
2779         Op0.assign(VL.size(), VL0->getOperand(0));
2780         VectorizableTree.back()->setOperand(0, Op0);
2781         return;
2782       }
2783       if (!CurrentOrder.empty()) {
2784         LLVM_DEBUG({
2785           dbgs() << "SLP: Reusing or shuffling of reordered extract sequence "
2786                     "with order";
2787           for (unsigned Idx : CurrentOrder)
2788             dbgs() << " " << Idx;
2789           dbgs() << "\n";
2790         });
2791         // Insert new order with initial value 0, if it does not exist,
2792         // otherwise return the iterator to the existing one.
2793         newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
2794                      ReuseShuffleIndicies, CurrentOrder);
2795         findRootOrder(CurrentOrder);
2796         ++NumOpsWantToKeepOrder[CurrentOrder];
2797         // This is a special case, as it does not gather, but at the same time
2798         // we are not extending buildTree_rec() towards the operands.
2799         ValueList Op0;
2800         Op0.assign(VL.size(), VL0->getOperand(0));
2801         VectorizableTree.back()->setOperand(0, Op0);
2802         return;
2803       }
2804       LLVM_DEBUG(dbgs() << "SLP: Gather extract sequence.\n");
2805       newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
2806                    ReuseShuffleIndicies);
2807       BS.cancelScheduling(VL, VL0);
2808       return;
2809     }
2810     case Instruction::Load: {
2811       // Check that a vectorized load would load the same memory as a scalar
2812       // load. For example, we don't want to vectorize loads that are smaller
2813       // than 8-bit. Even though we have a packed struct {<i2, i2, i2, i2>} LLVM
2814       // treats loading/storing it as an i8 struct. If we vectorize loads/stores
2815       // from such a struct, we read/write packed bits disagreeing with the
2816       // unvectorized version.
2817       Type *ScalarTy = VL0->getType();
2818
2819       if (DL->getTypeSizeInBits(ScalarTy) !=
2820           DL->getTypeAllocSizeInBits(ScalarTy)) {
2821         BS.cancelScheduling(VL, VL0);
2822         newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
2823                      ReuseShuffleIndicies);
2824         LLVM_DEBUG(dbgs() << "SLP: Gathering loads of non-packed type.\n");
2825         return;
2826       }
2827
2828       // Make sure all loads in the bundle are simple - we can't vectorize
2829       // atomic or volatile loads.
2830       SmallVector<Value *, 4> PointerOps(VL.size());
2831       auto POIter = PointerOps.begin();
2832       for (Value *V : VL) {
2833         auto *L = cast<LoadInst>(V);
2834         if (!L->isSimple()) {
2835           BS.cancelScheduling(VL, VL0);
2836           newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
2837                        ReuseShuffleIndicies);
2838           LLVM_DEBUG(dbgs() << "SLP: Gathering non-simple loads.\n");
2839           return;
2840         }
2841         *POIter = L->getPointerOperand();
2842         ++POIter;
2843       }
2844
2845       OrdersType CurrentOrder;
2846       // Check the order of pointer operands.
2847       if (llvm::sortPtrAccesses(PointerOps, *DL, *SE, CurrentOrder)) {
2848         Value *Ptr0;
2849         Value *PtrN;
2850         if (CurrentOrder.empty()) {
2851           Ptr0 = PointerOps.front();
2852           PtrN = PointerOps.back();
2853         } else {
2854           Ptr0 = PointerOps[CurrentOrder.front()];
2855           PtrN = PointerOps[CurrentOrder.back()];
2856         }
2857         const SCEV *Scev0 = SE->getSCEV(Ptr0);
2858         const SCEV *ScevN = SE->getSCEV(PtrN);
2859         const auto *Diff =
2860             dyn_cast<SCEVConstant>(SE->getMinusSCEV(ScevN, Scev0));
2861         uint64_t Size = DL->getTypeAllocSize(ScalarTy);
2862         // Check that the sorted loads are consecutive.
2863         if (Diff && Diff->getAPInt() == (VL.size() - 1) * Size) {
2864           if (CurrentOrder.empty()) {
2865             // Original loads are consecutive and does not require reordering.
2866             ++NumOpsWantToKeepOriginalOrder;
2867             TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S,
2868                                          UserTreeIdx, ReuseShuffleIndicies);
2869             TE->setOperandsInOrder();
2870             LLVM_DEBUG(dbgs() << "SLP: added a vector of loads.\n");
2871           } else {
2872             // Need to reorder.
2873             TreeEntry *TE =
2874                 newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
2875                              ReuseShuffleIndicies, CurrentOrder);
2876             TE->setOperandsInOrder();
2877             LLVM_DEBUG(dbgs() << "SLP: added a vector of jumbled loads.\n");
2878             findRootOrder(CurrentOrder);
2879             ++NumOpsWantToKeepOrder[CurrentOrder];
2880           }
2881           return;
2882         }
2883         // Vectorizing non-consecutive loads with `llvm.masked.gather`.
2884         TreeEntry *TE = newTreeEntry(VL, TreeEntry::ScatterVectorize, Bundle, S,
2885                                      UserTreeIdx, ReuseShuffleIndicies);
2886         TE->setOperandsInOrder();
2887         buildTree_rec(PointerOps, Depth + 1, {TE, 0});
2888         LLVM_DEBUG(dbgs() << "SLP: added a vector of non-consecutive loads.\n");
2889         return;
2890       }
2891
2892       LLVM_DEBUG(dbgs() << "SLP: Gathering non-consecutive loads.\n");
2893       BS.cancelScheduling(VL, VL0);
2894       newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
2895                    ReuseShuffleIndicies);
2896       return;
2897     }
2898     case Instruction::ZExt:
2899     case Instruction::SExt:
2900     case Instruction::FPToUI:
2901     case Instruction::FPToSI:
2902     case Instruction::FPExt:
2903     case Instruction::PtrToInt:
2904     case Instruction::IntToPtr:
2905     case Instruction::SIToFP:
2906     case Instruction::UIToFP:
2907     case Instruction::Trunc:
2908     case Instruction::FPTrunc:
2909     case Instruction::BitCast: {
2910       Type *SrcTy = VL0->getOperand(0)->getType();
2911       for (Value *V : VL) {
2912         Type *Ty = cast<Instruction>(V)->getOperand(0)->getType();
2913         if (Ty != SrcTy || !isValidElementType(Ty)) {
2914           BS.cancelScheduling(VL, VL0);
2915           newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
2916                        ReuseShuffleIndicies);
2917           LLVM_DEBUG(dbgs()
2918                      << "SLP: Gathering casts with different src types.\n");
2919           return;
2920         }
2921       }
2922       TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
2923                                    ReuseShuffleIndicies);
2924       LLVM_DEBUG(dbgs() << "SLP: added a vector of casts.\n");
2925
2926       TE->setOperandsInOrder();
2927       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
2928         ValueList Operands;
2929         // Prepare the operand vector.
2930         for (Value *V : VL)
2931           Operands.push_back(cast<Instruction>(V)->getOperand(i));
2932
2933         buildTree_rec(Operands, Depth + 1, {TE, i});
2934       }
2935       return;
2936     }
2937     case Instruction::ICmp:
2938     case Instruction::FCmp: {
2939       // Check that all of the compares have the same predicate.
2940       CmpInst::Predicate P0 = cast<CmpInst>(VL0)->getPredicate();
2941       CmpInst::Predicate SwapP0 = CmpInst::getSwappedPredicate(P0);
2942       Type *ComparedTy = VL0->getOperand(0)->getType();
2943       for (Value *V : VL) {
2944         CmpInst *Cmp = cast<CmpInst>(V);
2945         if ((Cmp->getPredicate() != P0 && Cmp->getPredicate() != SwapP0) ||
2946             Cmp->getOperand(0)->getType() != ComparedTy) {
2947           BS.cancelScheduling(VL, VL0);
2948           newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
2949                        ReuseShuffleIndicies);
2950           LLVM_DEBUG(dbgs()
2951                      << "SLP: Gathering cmp with different predicate.\n");
2952           return;
2953         }
2954       }
2955
2956       TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
2957                                    ReuseShuffleIndicies);
2958       LLVM_DEBUG(dbgs() << "SLP: added a vector of compares.\n");
2959
2960       ValueList Left, Right;
2961       if (cast<CmpInst>(VL0)->isCommutative()) {
2962         // Commutative predicate - collect + sort operands of the instructions
2963         // so that each side is more likely to have the same opcode.
2964         assert(P0 == SwapP0 && "Commutative Predicate mismatch");
2965         reorderInputsAccordingToOpcode(VL, Left, Right, *DL, *SE, *this);
2966       } else {
2967         // Collect operands - commute if it uses the swapped predicate.
2968         for (Value *V : VL) {
2969           auto *Cmp = cast<CmpInst>(V);
2970           Value *LHS = Cmp->getOperand(0);
2971           Value *RHS = Cmp->getOperand(1);
2972           if (Cmp->getPredicate() != P0)
2973             std::swap(LHS, RHS);
2974           Left.push_back(LHS);
2975           Right.push_back(RHS);
2976         }
2977       }
2978       TE->setOperand(0, Left);
2979       TE->setOperand(1, Right);
2980       buildTree_rec(Left, Depth + 1, {TE, 0});
2981       buildTree_rec(Right, Depth + 1, {TE, 1});
2982       return;
2983     }
2984     case Instruction::Select:
2985     case Instruction::FNeg:
2986     case Instruction::Add:
2987     case Instruction::FAdd:
2988     case Instruction::Sub:
2989     case Instruction::FSub:
2990     case Instruction::Mul:
2991     case Instruction::FMul:
2992     case Instruction::UDiv:
2993     case Instruction::SDiv:
2994     case Instruction::FDiv:
2995     case Instruction::URem:
2996     case Instruction::SRem:
2997     case Instruction::FRem:
2998     case Instruction::Shl:
2999     case Instruction::LShr:
3000     case Instruction::AShr:
3001     case Instruction::And:
3002     case Instruction::Or:
3003     case Instruction::Xor: {
3004       TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
3005                                    ReuseShuffleIndicies);
3006       LLVM_DEBUG(dbgs() << "SLP: added a vector of un/bin op.\n");
3007
3008       // Sort operands of the instructions so that each side is more likely to
3009       // have the same opcode.
3010       if (isa<BinaryOperator>(VL0) && VL0->isCommutative()) {
3011         ValueList Left, Right;
3012         reorderInputsAccordingToOpcode(VL, Left, Right, *DL, *SE, *this);
3013         TE->setOperand(0, Left);
3014         TE->setOperand(1, Right);
3015         buildTree_rec(Left, Depth + 1, {TE, 0});
3016         buildTree_rec(Right, Depth + 1, {TE, 1});
3017         return;
3018       }
3019
3020       TE->setOperandsInOrder();
3021       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
3022         ValueList Operands;
3023         // Prepare the operand vector.
3024         for (Value *V : VL)
3025           Operands.push_back(cast<Instruction>(V)->getOperand(i));
3026
3027         buildTree_rec(Operands, Depth + 1, {TE, i});
3028       }
3029       return;
3030     }
3031     case Instruction::GetElementPtr: {
3032       // We don't combine GEPs with complicated (nested) indexing.
3033       for (Value *V : VL) {
3034         if (cast<Instruction>(V)->getNumOperands() != 2) {
3035           LLVM_DEBUG(dbgs() << "SLP: not-vectorizable GEP (nested indexes).\n");
3036           BS.cancelScheduling(VL, VL0);
3037           newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
3038                        ReuseShuffleIndicies);
3039           return;
3040         }
3041       }
3042
3043       // We can't combine several GEPs into one vector if they operate on
3044       // different types.
3045       Type *Ty0 = VL0->getOperand(0)->getType();
3046       for (Value *V : VL) {
3047         Type *CurTy = cast<Instruction>(V)->getOperand(0)->getType();
3048         if (Ty0 != CurTy) {
3049           LLVM_DEBUG(dbgs()
3050                      << "SLP: not-vectorizable GEP (different types).\n");
3051           BS.cancelScheduling(VL, VL0);
3052           newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
3053                        ReuseShuffleIndicies);
3054           return;
3055         }
3056       }
3057
3058       // We don't combine GEPs with non-constant indexes.
3059       Type *Ty1 = VL0->getOperand(1)->getType();
3060       for (Value *V : VL) {
3061         auto Op = cast<Instruction>(V)->getOperand(1);
3062         if (!isa<ConstantInt>(Op) ||
3063             (Op->getType() != Ty1 &&
3064              Op->getType()->getScalarSizeInBits() >
3065                  DL->getIndexSizeInBits(
3066                      V->getType()->getPointerAddressSpace()))) {
3067           LLVM_DEBUG(dbgs()
3068                      << "SLP: not-vectorizable GEP (non-constant indexes).\n");
3069           BS.cancelScheduling(VL, VL0);
3070           newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
3071                        ReuseShuffleIndicies);
3072           return;
3073         }
3074       }
3075
3076       TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
3077                                    ReuseShuffleIndicies);
3078       LLVM_DEBUG(dbgs() << "SLP: added a vector of GEPs.\n");
3079       TE->setOperandsInOrder();
3080       for (unsigned i = 0, e = 2; i < e; ++i) {
3081         ValueList Operands;
3082         // Prepare the operand vector.
3083         for (Value *V : VL)
3084           Operands.push_back(cast<Instruction>(V)->getOperand(i));
3085
3086         buildTree_rec(Operands, Depth + 1, {TE, i});
3087       }
3088       return;
3089     }
3090     case Instruction::Store: {
3091       // Check if the stores are consecutive or if we need to swizzle them.
3092       llvm::Type *ScalarTy = cast<StoreInst>(VL0)->getValueOperand()->getType();
3093       // Make sure all stores in the bundle are simple - we can't vectorize
3094       // atomic or volatile stores.
3095       SmallVector<Value *, 4> PointerOps(VL.size());
3096       ValueList Operands(VL.size());
3097       auto POIter = PointerOps.begin();
3098       auto OIter = Operands.begin();
3099       for (Value *V : VL) {
3100         auto *SI = cast<StoreInst>(V);
3101         if (!SI->isSimple()) {
3102           BS.cancelScheduling(VL, VL0);
3103           newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
3104                        ReuseShuffleIndicies);
3105           LLVM_DEBUG(dbgs() << "SLP: Gathering non-simple stores.\n");
3106           return;
3107         }
3108         *POIter = SI->getPointerOperand();
3109         *OIter = SI->getValueOperand();
3110         ++POIter;
3111         ++OIter;
3112       }
3113
3114       OrdersType CurrentOrder;
3115       // Check the order of pointer operands.
3116       if (llvm::sortPtrAccesses(PointerOps, *DL, *SE, CurrentOrder)) {
3117         Value *Ptr0;
3118         Value *PtrN;
3119         if (CurrentOrder.empty()) {
3120           Ptr0 = PointerOps.front();
3121           PtrN = PointerOps.back();
3122         } else {
3123           Ptr0 = PointerOps[CurrentOrder.front()];
3124           PtrN = PointerOps[CurrentOrder.back()];
3125         }
3126         const SCEV *Scev0 = SE->getSCEV(Ptr0);
3127         const SCEV *ScevN = SE->getSCEV(PtrN);
3128         const auto *Diff =
3129             dyn_cast<SCEVConstant>(SE->getMinusSCEV(ScevN, Scev0));
3130         uint64_t Size = DL->getTypeAllocSize(ScalarTy);
3131         // Check that the sorted pointer operands are consecutive.
3132         if (Diff && Diff->getAPInt() == (VL.size() - 1) * Size) {
3133           if (CurrentOrder.empty()) {
3134             // Original stores are consecutive and does not require reordering.
3135             ++NumOpsWantToKeepOriginalOrder;
3136             TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S,
3137                                          UserTreeIdx, ReuseShuffleIndicies);
3138             TE->setOperandsInOrder();
3139             buildTree_rec(Operands, Depth + 1, {TE, 0});
3140             LLVM_DEBUG(dbgs() << "SLP: added a vector of stores.\n");
3141           } else {
3142             TreeEntry *TE =
3143                 newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
3144                              ReuseShuffleIndicies, CurrentOrder);
3145             TE->setOperandsInOrder();
3146             buildTree_rec(Operands, Depth + 1, {TE, 0});
3147             LLVM_DEBUG(dbgs() << "SLP: added a vector of jumbled stores.\n");
3148             findRootOrder(CurrentOrder);
3149             ++NumOpsWantToKeepOrder[CurrentOrder];
3150           }
3151           return;
3152         }
3153       }
3154
3155       BS.cancelScheduling(VL, VL0);
3156       newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
3157                    ReuseShuffleIndicies);
3158       LLVM_DEBUG(dbgs() << "SLP: Non-consecutive store.\n");
3159       return;
3160     }
3161     case Instruction::Call: {
3162       // Check if the calls are all to the same vectorizable intrinsic or
3163       // library function.
3164       CallInst *CI = cast<CallInst>(VL0);
3165       Intrinsic::ID ID = getVectorIntrinsicIDForCall(CI, TLI);
3166
3167       VFShape Shape = VFShape::get(
3168           *CI, ElementCount::getFixed(static_cast<unsigned int>(VL.size())),
3169           false /*HasGlobalPred*/);
3170       Function *VecFunc = VFDatabase(*CI).getVectorizedFunction(Shape);
3171
3172       if (!VecFunc && !isTriviallyVectorizable(ID)) {
3173         BS.cancelScheduling(VL, VL0);
3174         newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
3175                      ReuseShuffleIndicies);
3176         LLVM_DEBUG(dbgs() << "SLP: Non-vectorizable call.\n");
3177         return;
3178       }
3179       Function *F = CI->getCalledFunction();
3180       unsigned NumArgs = CI->getNumArgOperands();
3181       SmallVector<Value*, 4> ScalarArgs(NumArgs, nullptr);
3182       for (unsigned j = 0; j != NumArgs; ++j)
3183         if (hasVectorInstrinsicScalarOpd(ID, j))
3184           ScalarArgs[j] = CI->getArgOperand(j);
3185       for (Value *V : VL) {
3186         CallInst *CI2 = dyn_cast<CallInst>(V);
3187         if (!CI2 || CI2->getCalledFunction() != F ||
3188             getVectorIntrinsicIDForCall(CI2, TLI) != ID ||
3189             (VecFunc &&
3190              VecFunc != VFDatabase(*CI2).getVectorizedFunction(Shape)) ||
3191             !CI->hasIdenticalOperandBundleSchema(*CI2)) {
3192           BS.cancelScheduling(VL, VL0);
3193           newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
3194                        ReuseShuffleIndicies);
3195           LLVM_DEBUG(dbgs() << "SLP: mismatched calls:" << *CI << "!=" << *V
3196                             << "\n");
3197           return;
3198         }
3199         // Some intrinsics have scalar arguments and should be same in order for
3200         // them to be vectorized.
3201         for (unsigned j = 0; j != NumArgs; ++j) {
3202           if (hasVectorInstrinsicScalarOpd(ID, j)) {
3203             Value *A1J = CI2->getArgOperand(j);
3204             if (ScalarArgs[j] != A1J) {
3205               BS.cancelScheduling(VL, VL0);
3206               newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
3207                            ReuseShuffleIndicies);
3208               LLVM_DEBUG(dbgs() << "SLP: mismatched arguments in call:" << *CI
3209                                 << " argument " << ScalarArgs[j] << "!=" << A1J
3210                                 << "\n");
3211               return;
3212             }
3213           }
3214         }
3215         // Verify that the bundle operands are identical between the two calls.
3216         if (CI->hasOperandBundles() &&
3217             !std::equal(CI->op_begin() + CI->getBundleOperandsStartIndex(),
3218                         CI->op_begin() + CI->getBundleOperandsEndIndex(),
3219                         CI2->op_begin() + CI2->getBundleOperandsStartIndex())) {
3220           BS.cancelScheduling(VL, VL0);
3221           newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
3222                        ReuseShuffleIndicies);
3223           LLVM_DEBUG(dbgs() << "SLP: mismatched bundle operands in calls:"
3224                             << *CI << "!=" << *V << '\n');
3225           return;
3226         }
3227       }
3228
3229       TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
3230                                    ReuseShuffleIndicies);
3231       TE->setOperandsInOrder();
3232       for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) {
3233         ValueList Operands;
3234         // Prepare the operand vector.
3235         for (Value *V : VL) {
3236           auto *CI2 = cast<CallInst>(V);
3237           Operands.push_back(CI2->getArgOperand(i));
3238         }
3239         buildTree_rec(Operands, Depth + 1, {TE, i});
3240       }
3241       return;
3242     }
3243     case Instruction::ShuffleVector: {
3244       // If this is not an alternate sequence of opcode like add-sub
3245       // then do not vectorize this instruction.
3246       if (!S.isAltShuffle()) {
3247         BS.cancelScheduling(VL, VL0);
3248         newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
3249                      ReuseShuffleIndicies);
3250         LLVM_DEBUG(dbgs() << "SLP: ShuffleVector are not vectorized.\n");
3251         return;
3252       }
3253       TreeEntry *TE = newTreeEntry(VL, Bundle /*vectorized*/, S, UserTreeIdx,
3254                                    ReuseShuffleIndicies);
3255       LLVM_DEBUG(dbgs() << "SLP: added a ShuffleVector op.\n");
3256
3257       // Reorder operands if reordering would enable vectorization.
3258       if (isa<BinaryOperator>(VL0)) {
3259         ValueList Left, Right;
3260         reorderInputsAccordingToOpcode(VL, Left, Right, *DL, *SE, *this);
3261         TE->setOperand(0, Left);
3262         TE->setOperand(1, Right);
3263         buildTree_rec(Left, Depth + 1, {TE, 0});
3264         buildTree_rec(Right, Depth + 1, {TE, 1});
3265         return;
3266       }
3267
3268       TE->setOperandsInOrder();
3269       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
3270         ValueList Operands;
3271         // Prepare the operand vector.
3272         for (Value *V : VL)
3273           Operands.push_back(cast<Instruction>(V)->getOperand(i));
3274
3275         buildTree_rec(Operands, Depth + 1, {TE, i});
3276       }
3277       return;
3278     }
3279     default:
3280       BS.cancelScheduling(VL, VL0);
3281       newTreeEntry(VL, None /*not vectorized*/, S, UserTreeIdx,
3282                    ReuseShuffleIndicies);
3283       LLVM_DEBUG(dbgs() << "SLP: Gathering unknown instruction.\n");
3284      &n