lib/Transforms/Vectorize/SLPVectorizer.cpp

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