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   if (!DT->isReachableFromEntry(BB)) {
 980     // Don't go into unreachable blocks. They may contain instructions with
 981     // dependency cycles which confuse the final scheduling.
 982     DEBUG(dbgs() << "SLP: bundle in unreachable block.\n");
 983     newTreeEntry(VL, false);
 984     return;
 985   }
 986
 987   // Check that every instructions appears once in this bundle.
 988   for (unsigned i = 0, e = VL.size(); i < e; ++i)
 989     for (unsigned j = i+1; j < e; ++j)
 990       if (VL[i] == VL[j]) {
 991         DEBUG(dbgs() << "SLP: Scalar used twice in bundle.\n");
 992         newTreeEntry(VL, false);
 993         return;
 994       }
 995
 996   auto &BSRef = BlocksSchedules[BB];
 997   if (!BSRef) {
 998     BSRef = llvm::make_unique<BlockScheduling>(BB);
 999   }
1000   BlockScheduling &BS = *BSRef.get();
1001
1002   if (!BS.tryScheduleBundle(VL, AA)) {
1003     DEBUG(dbgs() << "SLP: We are not able to schedule this bundle!\n");
1004     BS.cancelScheduling(VL);
1005     newTreeEntry(VL, false);
1006     return;
1007   }
1008   DEBUG(dbgs() << "SLP: We are able to schedule this bundle.\n");
1009
1010   switch (Opcode) {
1011     case Instruction::PHI: {
1012       PHINode *PH = dyn_cast<PHINode>(VL0);
1013
1014       // Check for terminator values (e.g. invoke).
1015       for (unsigned j = 0; j < VL.size(); ++j)
1016         for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
1017           TerminatorInst *Term = dyn_cast<TerminatorInst>(
1018               cast<PHINode>(VL[j])->getIncomingValueForBlock(PH->getIncomingBlock(i)));
1019           if (Term) {
1020             DEBUG(dbgs() << "SLP: Need to swizzle PHINodes (TerminatorInst use).\n");
1021             BS.cancelScheduling(VL);
1022             newTreeEntry(VL, false);
1023             return;
1024           }
1025         }
1026
1027       newTreeEntry(VL, true);
1028       DEBUG(dbgs() << "SLP: added a vector of PHINodes.\n");
1029
1030       for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
1031         ValueList Operands;
1032         // Prepare the operand vector.
1033         for (unsigned j = 0; j < VL.size(); ++j)
1034           Operands.push_back(cast<PHINode>(VL[j])->getIncomingValueForBlock(
1035               PH->getIncomingBlock(i)));
1036
1037         buildTree_rec(Operands, Depth + 1);
1038       }
1039       return;
1040     }
1041     case Instruction::ExtractElement: {
1042       bool Reuse = CanReuseExtract(VL);
1043       if (Reuse) {
1044         DEBUG(dbgs() << "SLP: Reusing extract sequence.\n");
1045       } else {
1046         BS.cancelScheduling(VL);
1047       }
1048       newTreeEntry(VL, Reuse);
1049       return;
1050     }
1051     case Instruction::Load: {
1052       // Check if the loads are consecutive or of we need to swizzle them.
1053       for (unsigned i = 0, e = VL.size() - 1; i < e; ++i) {
1054         LoadInst *L = cast<LoadInst>(VL[i]);
1055         if (!L->isSimple()) {
1056           BS.cancelScheduling(VL);
1057           newTreeEntry(VL, false);
1058           DEBUG(dbgs() << "SLP: Gathering non-simple loads.\n");
1059           return;
1060         }
1061         if (!isConsecutiveAccess(VL[i], VL[i + 1])) {
1062           if (VL.size() == 2 && isConsecutiveAccess(VL[1], VL[0])) {
1063             ++NumLoadsWantToChangeOrder;
1064           }
1065           BS.cancelScheduling(VL);
1066           newTreeEntry(VL, false);
1067           DEBUG(dbgs() << "SLP: Gathering non-consecutive loads.\n");
1068           return;
1069         }
1070       }
1071       ++NumLoadsWantToKeepOrder;
1072       newTreeEntry(VL, true);
1073       DEBUG(dbgs() << "SLP: added a vector of loads.\n");
1074       return;
1075     }
1076     case Instruction::ZExt:
1077     case Instruction::SExt:
1078     case Instruction::FPToUI:
1079     case Instruction::FPToSI:
1080     case Instruction::FPExt:
1081     case Instruction::PtrToInt:
1082     case Instruction::IntToPtr:
1083     case Instruction::SIToFP:
1084     case Instruction::UIToFP:
1085     case Instruction::Trunc:
1086     case Instruction::FPTrunc:
1087     case Instruction::BitCast: {
1088       Type *SrcTy = VL0->getOperand(0)->getType();
1089       for (unsigned i = 0; i < VL.size(); ++i) {
1090         Type *Ty = cast<Instruction>(VL[i])->getOperand(0)->getType();
1091         if (Ty != SrcTy || Ty->isAggregateType() || Ty->isVectorTy()) {
1092           BS.cancelScheduling(VL);
1093           newTreeEntry(VL, false);
1094           DEBUG(dbgs() << "SLP: Gathering casts with different src types.\n");
1095           return;
1096         }
1097       }
1098       newTreeEntry(VL, true);
1099       DEBUG(dbgs() << "SLP: added a vector of casts.\n");
1100
1101       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
1102         ValueList Operands;
1103         // Prepare the operand vector.
1104         for (unsigned j = 0; j < VL.size(); ++j)
1105           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
1106
1107         buildTree_rec(Operands, Depth+1);
1108       }
1109       return;
1110     }
1111     case Instruction::ICmp:
1112     case Instruction::FCmp: {
1113       // Check that all of the compares have the same predicate.
1114       CmpInst::Predicate P0 = dyn_cast<CmpInst>(VL0)->getPredicate();
1115       Type *ComparedTy = cast<Instruction>(VL[0])->getOperand(0)->getType();
1116       for (unsigned i = 1, e = VL.size(); i < e; ++i) {
1117         CmpInst *Cmp = cast<CmpInst>(VL[i]);
1118         if (Cmp->getPredicate() != P0 ||
1119             Cmp->getOperand(0)->getType() != ComparedTy) {
1120           BS.cancelScheduling(VL);
1121           newTreeEntry(VL, false);
1122           DEBUG(dbgs() << "SLP: Gathering cmp with different predicate.\n");
1123           return;
1124         }
1125       }
1126
1127       newTreeEntry(VL, true);
1128       DEBUG(dbgs() << "SLP: added a vector of compares.\n");
1129
1130       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
1131         ValueList Operands;
1132         // Prepare the operand vector.
1133         for (unsigned j = 0; j < VL.size(); ++j)
1134           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
1135
1136         buildTree_rec(Operands, Depth+1);
1137       }
1138       return;
1139     }
1140     case Instruction::Select:
1141     case Instruction::Add:
1142     case Instruction::FAdd:
1143     case Instruction::Sub:
1144     case Instruction::FSub:
1145     case Instruction::Mul:
1146     case Instruction::FMul:
1147     case Instruction::UDiv:
1148     case Instruction::SDiv:
1149     case Instruction::FDiv:
1150     case Instruction::URem:
1151     case Instruction::SRem:
1152     case Instruction::FRem:
1153     case Instruction::Shl:
1154     case Instruction::LShr:
1155     case Instruction::AShr:
1156     case Instruction::And:
1157     case Instruction::Or:
1158     case Instruction::Xor: {
1159       newTreeEntry(VL, true);
1160       DEBUG(dbgs() << "SLP: added a vector of bin op.\n");
1161
1162       // Sort operands of the instructions so that each side is more likely to
1163       // have the same opcode.
1164       if (isa<BinaryOperator>(VL0) && VL0->isCommutative()) {
1165         ValueList Left, Right;
1166         reorderInputsAccordingToOpcode(VL, Left, Right);
1167         buildTree_rec(Left, Depth + 1);
1168         buildTree_rec(Right, Depth + 1);
1169         return;
1170       }
1171
1172       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
1173         ValueList Operands;
1174         // Prepare the operand vector.
1175         for (unsigned j = 0; j < VL.size(); ++j)
1176           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
1177
1178         buildTree_rec(Operands, Depth+1);
1179       }
1180       return;
1181     }
1182     case Instruction::GetElementPtr: {
1183       // We don't combine GEPs with complicated (nested) indexing.
1184       for (unsigned j = 0; j < VL.size(); ++j) {
1185         if (cast<Instruction>(VL[j])->getNumOperands() != 2) {
1186           DEBUG(dbgs() << "SLP: not-vectorizable GEP (nested indexes).\n");
1187           BS.cancelScheduling(VL);
1188           newTreeEntry(VL, false);
1189           return;
1190         }
1191       }
1192
1193       // We can't combine several GEPs into one vector if they operate on
1194       // different types.
1195       Type *Ty0 = cast<Instruction>(VL0)->getOperand(0)->getType();
1196       for (unsigned j = 0; j < VL.size(); ++j) {
1197         Type *CurTy = cast<Instruction>(VL[j])->getOperand(0)->getType();
1198         if (Ty0 != CurTy) {
1199           DEBUG(dbgs() << "SLP: not-vectorizable GEP (different types).\n");
1200           BS.cancelScheduling(VL);
1201           newTreeEntry(VL, false);
1202           return;
1203         }
1204       }
1205
1206       // We don't combine GEPs with non-constant indexes.
1207       for (unsigned j = 0; j < VL.size(); ++j) {
1208         auto Op = cast<Instruction>(VL[j])->getOperand(1);
1209         if (!isa<ConstantInt>(Op)) {
1210           DEBUG(
1211               dbgs() << "SLP: not-vectorizable GEP (non-constant indexes).\n");
1212           BS.cancelScheduling(VL);
1213           newTreeEntry(VL, false);
1214           return;
1215         }
1216       }
1217
1218       newTreeEntry(VL, true);
1219       DEBUG(dbgs() << "SLP: added a vector of GEPs.\n");
1220       for (unsigned i = 0, e = 2; i < e; ++i) {
1221         ValueList Operands;
1222         // Prepare the operand vector.
1223         for (unsigned j = 0; j < VL.size(); ++j)
1224           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
1225
1226         buildTree_rec(Operands, Depth + 1);
1227       }
1228       return;
1229     }
1230     case Instruction::Store: {
1231       // Check if the stores are consecutive or of we need to swizzle them.
1232       for (unsigned i = 0, e = VL.size() - 1; i < e; ++i)
1233         if (!isConsecutiveAccess(VL[i], VL[i + 1])) {
1234           BS.cancelScheduling(VL);
1235           newTreeEntry(VL, false);
1236           DEBUG(dbgs() << "SLP: Non-consecutive store.\n");
1237           return;
1238         }
1239
1240       newTreeEntry(VL, true);
1241       DEBUG(dbgs() << "SLP: added a vector of stores.\n");
1242
1243       ValueList Operands;
1244       for (unsigned j = 0; j < VL.size(); ++j)
1245         Operands.push_back(cast<Instruction>(VL[j])->getOperand(0));
1246
1247       buildTree_rec(Operands, Depth + 1);
1248       return;
1249     }
1250     case Instruction::Call: {
1251       // Check if the calls are all to the same vectorizable intrinsic.
1252       CallInst *CI = cast<CallInst>(VL[0]);
1253       // Check if this is an Intrinsic call or something that can be
1254       // represented by an intrinsic call
1255       Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
1256       if (!isTriviallyVectorizable(ID)) {
1257         BS.cancelScheduling(VL);
1258         newTreeEntry(VL, false);
1259         DEBUG(dbgs() << "SLP: Non-vectorizable call.\n");
1260         return;
1261       }
1262       Function *Int = CI->getCalledFunction();
1263       Value *A1I = nullptr;
1264       if (hasVectorInstrinsicScalarOpd(ID, 1))
1265         A1I = CI->getArgOperand(1);
1266       for (unsigned i = 1, e = VL.size(); i != e; ++i) {
1267         CallInst *CI2 = dyn_cast<CallInst>(VL[i]);
1268         if (!CI2 || CI2->getCalledFunction() != Int ||
1269             getIntrinsicIDForCall(CI2, TLI) != ID) {
1270           BS.cancelScheduling(VL);
1271           newTreeEntry(VL, false);
1272           DEBUG(dbgs() << "SLP: mismatched calls:" << *CI << "!=" << *VL[i]
1273                        << "\n");
1274           return;
1275         }
1276         // ctlz,cttz and powi are special intrinsics whose second argument
1277         // should be same in order for them to be vectorized.
1278         if (hasVectorInstrinsicScalarOpd(ID, 1)) {
1279           Value *A1J = CI2->getArgOperand(1);
1280           if (A1I != A1J) {
1281             BS.cancelScheduling(VL);
1282             newTreeEntry(VL, false);
1283             DEBUG(dbgs() << "SLP: mismatched arguments in call:" << *CI
1284                          << " argument "<< A1I<<"!=" << A1J
1285                          << "\n");
1286             return;
1287           }
1288         }
1289       }
1290
1291       newTreeEntry(VL, true);
1292       for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) {
1293         ValueList Operands;
1294         // Prepare the operand vector.
1295         for (unsigned j = 0; j < VL.size(); ++j) {
1296           CallInst *CI2 = dyn_cast<CallInst>(VL[j]);
1297           Operands.push_back(CI2->getArgOperand(i));
1298         }
1299         buildTree_rec(Operands, Depth + 1);
1300       }
1301       return;
1302     }
1303     case Instruction::ShuffleVector: {
1304       // If this is not an alternate sequence of opcode like add-sub
1305       // then do not vectorize this instruction.
1306       if (!isAltShuffle) {
1307         BS.cancelScheduling(VL);
1308         newTreeEntry(VL, false);
1309         DEBUG(dbgs() << "SLP: ShuffleVector are not vectorized.\n");
1310         return;
1311       }
1312       newTreeEntry(VL, true);
1313       DEBUG(dbgs() << "SLP: added a ShuffleVector op.\n");
1314       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
1315         ValueList Operands;
1316         // Prepare the operand vector.
1317         for (unsigned j = 0; j < VL.size(); ++j)
1318           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
1319
1320         buildTree_rec(Operands, Depth + 1);
1321       }
1322       return;
1323     }
1324     default:
1325       BS.cancelScheduling(VL);
1326       newTreeEntry(VL, false);
1327       DEBUG(dbgs() << "SLP: Gathering unknown instruction.\n");
1328       return;
1329   }
1330 }
1331
1332 int BoUpSLP::getEntryCost(TreeEntry *E) {
1333   ArrayRef<Value*> VL = E->Scalars;
1334
1335   Type *ScalarTy = VL[0]->getType();
1336   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
1337     ScalarTy = SI->getValueOperand()->getType();
1338   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
1339
1340   if (E->NeedToGather) {
1341     if (allConstant(VL))
1342       return 0;
1343     if (isSplat(VL)) {
1344       return TTI->getShuffleCost(TargetTransformInfo::SK_Broadcast, VecTy, 0);
1345     }
1346     return getGatherCost(E->Scalars);
1347   }
1348   unsigned Opcode = getSameOpcode(VL);
1349   assert(Opcode && getSameType(VL) && getSameBlock(VL) && "Invalid VL");
1350   Instruction *VL0 = cast<Instruction>(VL[0]);
1351   switch (Opcode) {
1352     case Instruction::PHI: {
1353       return 0;
1354     }
1355     case Instruction::ExtractElement: {
1356       if (CanReuseExtract(VL)) {
1357         int DeadCost = 0;
1358         for (unsigned i = 0, e = VL.size(); i < e; ++i) {
1359           ExtractElementInst *E = cast<ExtractElementInst>(VL[i]);
1360           if (E->hasOneUse())
1361             // Take credit for instruction that will become dead.
1362             DeadCost +=
1363                 TTI->getVectorInstrCost(Instruction::ExtractElement, VecTy, i);
1364         }
1365         return -DeadCost;
1366       }
1367       return getGatherCost(VecTy);
1368     }
1369     case Instruction::ZExt:
1370     case Instruction::SExt:
1371     case Instruction::FPToUI:
1372     case Instruction::FPToSI:
1373     case Instruction::FPExt:
1374     case Instruction::PtrToInt:
1375     case Instruction::IntToPtr:
1376     case Instruction::SIToFP:
1377     case Instruction::UIToFP:
1378     case Instruction::Trunc:
1379     case Instruction::FPTrunc:
1380     case Instruction::BitCast: {
1381       Type *SrcTy = VL0->getOperand(0)->getType();
1382
1383       // Calculate the cost of this instruction.
1384       int ScalarCost = VL.size() * TTI->getCastInstrCost(VL0->getOpcode(),
1385                                                          VL0->getType(), SrcTy);
1386
1387       VectorType *SrcVecTy = VectorType::get(SrcTy, VL.size());
1388       int VecCost = TTI->getCastInstrCost(VL0->getOpcode(), VecTy, SrcVecTy);
1389       return VecCost - ScalarCost;
1390     }
1391     case Instruction::FCmp:
1392     case Instruction::ICmp:
1393     case Instruction::Select:
1394     case Instruction::Add:
1395     case Instruction::FAdd:
1396     case Instruction::Sub:
1397     case Instruction::FSub:
1398     case Instruction::Mul:
1399     case Instruction::FMul:
1400     case Instruction::UDiv:
1401     case Instruction::SDiv:
1402     case Instruction::FDiv:
1403     case Instruction::URem:
1404     case Instruction::SRem:
1405     case Instruction::FRem:
1406     case Instruction::Shl:
1407     case Instruction::LShr:
1408     case Instruction::AShr:
1409     case Instruction::And:
1410     case Instruction::Or:
1411     case Instruction::Xor: {
1412       // Calculate the cost of this instruction.
1413       int ScalarCost = 0;
1414       int VecCost = 0;
1415       if (Opcode == Instruction::FCmp || Opcode == Instruction::ICmp ||
1416           Opcode == Instruction::Select) {
1417         VectorType *MaskTy = VectorType::get(Builder.getInt1Ty(), VL.size());
1418         ScalarCost = VecTy->getNumElements() *
1419         TTI->getCmpSelInstrCost(Opcode, ScalarTy, Builder.getInt1Ty());
1420         VecCost = TTI->getCmpSelInstrCost(Opcode, VecTy, MaskTy);
1421       } else {
1422         // Certain instructions can be cheaper to vectorize if they have a
1423         // constant second vector operand.
1424         TargetTransformInfo::OperandValueKind Op1VK =
1425             TargetTransformInfo::OK_AnyValue;
1426         TargetTransformInfo::OperandValueKind Op2VK =
1427             TargetTransformInfo::OK_UniformConstantValue;
1428         TargetTransformInfo::OperandValueProperties Op1VP =
1429             TargetTransformInfo::OP_None;
1430         TargetTransformInfo::OperandValueProperties Op2VP =
1431             TargetTransformInfo::OP_None;
1432
1433         // If all operands are exactly the same ConstantInt then set the
1434         // operand kind to OK_UniformConstantValue.
1435         // If instead not all operands are constants, then set the operand kind
1436         // to OK_AnyValue. If all operands are constants but not the same,
1437         // then set the operand kind to OK_NonUniformConstantValue.
1438         ConstantInt *CInt = nullptr;
1439         for (unsigned i = 0; i < VL.size(); ++i) {
1440           const Instruction *I = cast<Instruction>(VL[i]);
1441           if (!isa<ConstantInt>(I->getOperand(1))) {
1442             Op2VK = TargetTransformInfo::OK_AnyValue;
1443             break;
1444           }
1445           if (i == 0) {
1446             CInt = cast<ConstantInt>(I->getOperand(1));
1447             continue;
1448           }
1449           if (Op2VK == TargetTransformInfo::OK_UniformConstantValue &&
1450               CInt != cast<ConstantInt>(I->getOperand(1)))
1451             Op2VK = TargetTransformInfo::OK_NonUniformConstantValue;
1452         }
1453         // FIXME: Currently cost of model modification for division by
1454         // power of 2 is handled only for X86. Add support for other targets.
1455         if (Op2VK == TargetTransformInfo::OK_UniformConstantValue && CInt &&
1456             CInt->getValue().isPowerOf2())
1457           Op2VP = TargetTransformInfo::OP_PowerOf2;
1458
1459         ScalarCost = VecTy->getNumElements() *
1460                      TTI->getArithmeticInstrCost(Opcode, ScalarTy, Op1VK, Op2VK,
1461                                                  Op1VP, Op2VP);
1462         VecCost = TTI->getArithmeticInstrCost(Opcode, VecTy, Op1VK, Op2VK,
1463                                               Op1VP, Op2VP);
1464       }
1465       return VecCost - ScalarCost;
1466     }
1467     case Instruction::GetElementPtr: {
1468       TargetTransformInfo::OperandValueKind Op1VK =
1469           TargetTransformInfo::OK_AnyValue;
1470       TargetTransformInfo::OperandValueKind Op2VK =
1471           TargetTransformInfo::OK_UniformConstantValue;
1472
1473       int ScalarCost =
1474           VecTy->getNumElements() *
1475           TTI->getArithmeticInstrCost(Instruction::Add, ScalarTy, Op1VK, Op2VK);
1476       int VecCost =
1477           TTI->getArithmeticInstrCost(Instruction::Add, VecTy, Op1VK, Op2VK);
1478
1479       return VecCost - ScalarCost;
1480     }
1481     case Instruction::Load: {
1482       // Cost of wide load - cost of scalar loads.
1483       int ScalarLdCost = VecTy->getNumElements() *
1484       TTI->getMemoryOpCost(Instruction::Load, ScalarTy, 1, 0);
1485       int VecLdCost = TTI->getMemoryOpCost(Instruction::Load, VecTy, 1, 0);
1486       return VecLdCost - ScalarLdCost;
1487     }
1488     case Instruction::Store: {
1489       // We know that we can merge the stores. Calculate the cost.
1490       int ScalarStCost = VecTy->getNumElements() *
1491       TTI->getMemoryOpCost(Instruction::Store, ScalarTy, 1, 0);
1492       int VecStCost = TTI->getMemoryOpCost(Instruction::Store, VecTy, 1, 0);
1493       return VecStCost - ScalarStCost;
1494     }
1495     case Instruction::Call: {
1496       CallInst *CI = cast<CallInst>(VL0);
1497       Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
1498
1499       // Calculate the cost of the scalar and vector calls.
1500       SmallVector<Type*, 4> ScalarTys, VecTys;
1501       for (unsigned op = 0, opc = CI->getNumArgOperands(); op!= opc; ++op) {
1502         ScalarTys.push_back(CI->getArgOperand(op)->getType());
1503         VecTys.push_back(VectorType::get(CI->getArgOperand(op)->getType(),
1504                                          VecTy->getNumElements()));
1505       }
1506
1507       int ScalarCallCost = VecTy->getNumElements() *
1508           TTI->getIntrinsicInstrCost(ID, ScalarTy, ScalarTys);
1509
1510       int VecCallCost = TTI->getIntrinsicInstrCost(ID, VecTy, VecTys);
1511
1512       DEBUG(dbgs() << "SLP: Call cost "<< VecCallCost - ScalarCallCost
1513             << " (" << VecCallCost  << "-" <<  ScalarCallCost << ")"
1514             << " for " << *CI << "\n");
1515
1516       return VecCallCost - ScalarCallCost;
1517     }
1518     case Instruction::ShuffleVector: {
1519       TargetTransformInfo::OperandValueKind Op1VK =
1520           TargetTransformInfo::OK_AnyValue;
1521       TargetTransformInfo::OperandValueKind Op2VK =
1522           TargetTransformInfo::OK_AnyValue;
1523       int ScalarCost = 0;
1524       int VecCost = 0;
1525       for (unsigned i = 0; i < VL.size(); ++i) {
1526         Instruction *I = cast<Instruction>(VL[i]);
1527         if (!I)
1528           break;
1529         ScalarCost +=
1530             TTI->getArithmeticInstrCost(I->getOpcode(), ScalarTy, Op1VK, Op2VK);
1531       }
1532       // VecCost is equal to sum of the cost of creating 2 vectors
1533       // and the cost of creating shuffle.
1534       Instruction *I0 = cast<Instruction>(VL[0]);
1535       VecCost =
1536           TTI->getArithmeticInstrCost(I0->getOpcode(), VecTy, Op1VK, Op2VK);
1537       Instruction *I1 = cast<Instruction>(VL[1]);
1538       VecCost +=
1539           TTI->getArithmeticInstrCost(I1->getOpcode(), VecTy, Op1VK, Op2VK);
1540       VecCost +=
1541           TTI->getShuffleCost(TargetTransformInfo::SK_Alternate, VecTy, 0);
1542       return VecCost - ScalarCost;
1543     }
1544     default:
1545       llvm_unreachable("Unknown instruction");
1546   }
1547 }
1548
1549 bool BoUpSLP::isFullyVectorizableTinyTree() {
1550   DEBUG(dbgs() << "SLP: Check whether the tree with height " <<
1551         VectorizableTree.size() << " is fully vectorizable .\n");
1552
1553   // We only handle trees of height 2.
1554   if (VectorizableTree.size() != 2)
1555     return false;
1556
1557   // Handle splat stores.
1558   if (!VectorizableTree[0].NeedToGather && isSplat(VectorizableTree[1].Scalars))
1559     return true;
1560
1561   // Gathering cost would be too much for tiny trees.
1562   if (VectorizableTree[0].NeedToGather || VectorizableTree[1].NeedToGather)
1563     return false;
1564
1565   return true;
1566 }
1567
1568 int BoUpSLP::getSpillCost() {
1569   // Walk from the bottom of the tree to the top, tracking which values are
1570   // live. When we see a call instruction that is not part of our tree,
1571   // query TTI to see if there is a cost to keeping values live over it
1572   // (for example, if spills and fills are required).
1573   unsigned BundleWidth = VectorizableTree.front().Scalars.size();
1574   int Cost = 0;
1575
1576   SmallPtrSet<Instruction*, 4> LiveValues;
1577   Instruction *PrevInst = nullptr;
1578
1579   for (unsigned N = 0; N < VectorizableTree.size(); ++N) {
1580     Instruction *Inst = dyn_cast<Instruction>(VectorizableTree[N].Scalars[0]);
1581     if (!Inst)
1582       continue;
1583
1584     if (!PrevInst) {
1585       PrevInst = Inst;
1586       continue;
1587     }
1588
1589     DEBUG(
1590       dbgs() << "SLP: #LV: " << LiveValues.size();
1591       for (auto *X : LiveValues)
1592         dbgs() << " " << X->getName();
1593       dbgs() << ", Looking at ";
1594       Inst->dump();
1595       );
1596
1597     // Update LiveValues.
1598     LiveValues.erase(PrevInst);
1599     for (auto &J : PrevInst->operands()) {
1600       if (isa<Instruction>(&*J) && ScalarToTreeEntry.count(&*J))
1601         LiveValues.insert(cast<Instruction>(&*J));
1602     }
1603
1604     // Now find the sequence of instructions between PrevInst and Inst.
1605     BasicBlock::reverse_iterator InstIt(Inst), PrevInstIt(PrevInst);
1606     --PrevInstIt;
1607     while (InstIt != PrevInstIt) {
1608       if (PrevInstIt == PrevInst->getParent()->rend()) {
1609         PrevInstIt = Inst->getParent()->rbegin();
1610         continue;
1611       }
1612
1613       if (isa<CallInst>(&*PrevInstIt) && &*PrevInstIt != PrevInst) {
1614         SmallVector<Type*, 4> V;
1615         for (auto *II : LiveValues)
1616           V.push_back(VectorType::get(II->getType(), BundleWidth));
1617         Cost += TTI->getCostOfKeepingLiveOverCall(V);
1618       }
1619
1620       ++PrevInstIt;
1621     }
1622
1623     PrevInst = Inst;
1624   }
1625
1626   DEBUG(dbgs() << "SLP: SpillCost=" << Cost << "\n");
1627   return Cost;
1628 }
1629
1630 int BoUpSLP::getTreeCost() {
1631   int Cost = 0;
1632   DEBUG(dbgs() << "SLP: Calculating cost for tree of size " <<
1633         VectorizableTree.size() << ".\n");
1634
1635   // We only vectorize tiny trees if it is fully vectorizable.
1636   if (VectorizableTree.size() < 3 && !isFullyVectorizableTinyTree()) {
1637     if (!VectorizableTree.size()) {
1638       assert(!ExternalUses.size() && "We should not have any external users");
1639     }
1640     return INT_MAX;
1641   }
1642
1643   unsigned BundleWidth = VectorizableTree[0].Scalars.size();
1644
1645   for (unsigned i = 0, e = VectorizableTree.size(); i != e; ++i) {
1646     int C = getEntryCost(&VectorizableTree[i]);
1647     DEBUG(dbgs() << "SLP: Adding cost " << C << " for bundle that starts with "
1648           << *VectorizableTree[i].Scalars[0] << " .\n");
1649     Cost += C;
1650   }
1651
1652   SmallSet<Value *, 16> ExtractCostCalculated;
1653   int ExtractCost = 0;
1654   for (UserList::iterator I = ExternalUses.begin(), E = ExternalUses.end();
1655        I != E; ++I) {
1656     // We only add extract cost once for the same scalar.
1657     if (!ExtractCostCalculated.insert(I->Scalar))
1658       continue;
1659
1660     VectorType *VecTy = VectorType::get(I->Scalar->getType(), BundleWidth);
1661     ExtractCost += TTI->getVectorInstrCost(Instruction::ExtractElement, VecTy,
1662                                            I->Lane);
1663   }
1664
1665   Cost += getSpillCost();
1666
1667   DEBUG(dbgs() << "SLP: Total Cost " << Cost + ExtractCost<< ".\n");
1668   return  Cost + ExtractCost;
1669 }
1670
1671 int BoUpSLP::getGatherCost(Type *Ty) {
1672   int Cost = 0;
1673   for (unsigned i = 0, e = cast<VectorType>(Ty)->getNumElements(); i < e; ++i)
1674     Cost += TTI->getVectorInstrCost(Instruction::InsertElement, Ty, i);
1675   return Cost;
1676 }
1677
1678 int BoUpSLP::getGatherCost(ArrayRef<Value *> VL) {
1679   // Find the type of the operands in VL.
1680   Type *ScalarTy = VL[0]->getType();
1681   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
1682     ScalarTy = SI->getValueOperand()->getType();
1683   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
1684   // Find the cost of inserting/extracting values from the vector.
1685   return getGatherCost(VecTy);
1686 }
1687
1688 Value *BoUpSLP::getPointerOperand(Value *I) {
1689   if (LoadInst *LI = dyn_cast<LoadInst>(I))
1690     return LI->getPointerOperand();
1691   if (StoreInst *SI = dyn_cast<StoreInst>(I))
1692     return SI->getPointerOperand();
1693   return nullptr;
1694 }
1695
1696 unsigned BoUpSLP::getAddressSpaceOperand(Value *I) {
1697   if (LoadInst *L = dyn_cast<LoadInst>(I))
1698     return L->getPointerAddressSpace();
1699   if (StoreInst *S = dyn_cast<StoreInst>(I))
1700     return S->getPointerAddressSpace();
1701   return -1;
1702 }
1703
1704 bool BoUpSLP::isConsecutiveAccess(Value *A, Value *B) {
1705   Value *PtrA = getPointerOperand(A);
1706   Value *PtrB = getPointerOperand(B);
1707   unsigned ASA = getAddressSpaceOperand(A);
1708   unsigned ASB = getAddressSpaceOperand(B);
1709
1710   // Check that the address spaces match and that the pointers are valid.
1711   if (!PtrA || !PtrB || (ASA != ASB))
1712     return false;
1713
1714   // Make sure that A and B are different pointers of the same type.
1715   if (PtrA == PtrB || PtrA->getType() != PtrB->getType())
1716     return false;
1717
1718   unsigned PtrBitWidth = DL->getPointerSizeInBits(ASA);
1719   Type *Ty = cast<PointerType>(PtrA->getType())->getElementType();
1720   APInt Size(PtrBitWidth, DL->getTypeStoreSize(Ty));
1721
1722   APInt OffsetA(PtrBitWidth, 0), OffsetB(PtrBitWidth, 0);
1723   PtrA = PtrA->stripAndAccumulateInBoundsConstantOffsets(*DL, OffsetA);
1724   PtrB = PtrB->stripAndAccumulateInBoundsConstantOffsets(*DL, OffsetB);
1725
1726   APInt OffsetDelta = OffsetB - OffsetA;
1727
1728   // Check if they are based on the same pointer. That makes the offsets
1729   // sufficient.
1730   if (PtrA == PtrB)
1731     return OffsetDelta == Size;
1732
1733   // Compute the necessary base pointer delta to have the necessary final delta
1734   // equal to the size.
1735   APInt BaseDelta = Size - OffsetDelta;
1736
1737   // Otherwise compute the distance with SCEV between the base pointers.
1738   const SCEV *PtrSCEVA = SE->getSCEV(PtrA);
1739   const SCEV *PtrSCEVB = SE->getSCEV(PtrB);
1740   const SCEV *C = SE->getConstant(BaseDelta);
1741   const SCEV *X = SE->getAddExpr(PtrSCEVA, C);
1742   return X == PtrSCEVB;
1743 }
1744
1745 void BoUpSLP::setInsertPointAfterBundle(ArrayRef<Value *> VL) {
1746   Instruction *VL0 = cast<Instruction>(VL[0]);
1747   BasicBlock::iterator NextInst = VL0;
1748   ++NextInst;
1749   Builder.SetInsertPoint(VL0->getParent(), NextInst);
1750   Builder.SetCurrentDebugLocation(VL0->getDebugLoc());
1751 }
1752
1753 Value *BoUpSLP::Gather(ArrayRef<Value *> VL, VectorType *Ty) {
1754   Value *Vec = UndefValue::get(Ty);
1755   // Generate the 'InsertElement' instruction.
1756   for (unsigned i = 0; i < Ty->getNumElements(); ++i) {
1757     Vec = Builder.CreateInsertElement(Vec, VL[i], Builder.getInt32(i));
1758     if (Instruction *Insrt = dyn_cast<Instruction>(Vec)) {
1759       GatherSeq.insert(Insrt);
1760       CSEBlocks.insert(Insrt->getParent());
1761
1762       // Add to our 'need-to-extract' list.
1763       if (ScalarToTreeEntry.count(VL[i])) {
1764         int Idx = ScalarToTreeEntry[VL[i]];
1765         TreeEntry *E = &VectorizableTree[Idx];
1766         // Find which lane we need to extract.
1767         int FoundLane = -1;
1768         for (unsigned Lane = 0, LE = VL.size(); Lane != LE; ++Lane) {
1769           // Is this the lane of the scalar that we are looking for ?
1770           if (E->Scalars[Lane] == VL[i]) {
1771             FoundLane = Lane;
1772             break;
1773           }
1774         }
1775         assert(FoundLane >= 0 && "Could not find the correct lane");
1776         ExternalUses.push_back(ExternalUser(VL[i], Insrt, FoundLane));
1777       }
1778     }
1779   }
1780
1781   return Vec;
1782 }
1783
1784 Value *BoUpSLP::alreadyVectorized(ArrayRef<Value *> VL) const {
1785   SmallDenseMap<Value*, int>::const_iterator Entry
1786     = ScalarToTreeEntry.find(VL[0]);
1787   if (Entry != ScalarToTreeEntry.end()) {
1788     int Idx = Entry->second;
1789     const TreeEntry *En = &VectorizableTree[Idx];
1790     if (En->isSame(VL) && En->VectorizedValue)
1791       return En->VectorizedValue;
1792   }
1793   return nullptr;
1794 }
1795
1796 Value *BoUpSLP::vectorizeTree(ArrayRef<Value *> VL) {
1797   if (ScalarToTreeEntry.count(VL[0])) {
1798     int Idx = ScalarToTreeEntry[VL[0]];
1799     TreeEntry *E = &VectorizableTree[Idx];
1800     if (E->isSame(VL))
1801       return vectorizeTree(E);
1802   }
1803
1804   Type *ScalarTy = VL[0]->getType();
1805   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
1806     ScalarTy = SI->getValueOperand()->getType();
1807   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
1808
1809   return Gather(VL, VecTy);
1810 }
1811
1812 Value *BoUpSLP::vectorizeTree(TreeEntry *E) {
1813   IRBuilder<>::InsertPointGuard Guard(Builder);
1814
1815   if (E->VectorizedValue) {
1816     DEBUG(dbgs() << "SLP: Diamond merged for " << *E->Scalars[0] << ".\n");
1817     return E->VectorizedValue;
1818   }
1819
1820   Instruction *VL0 = cast<Instruction>(E->Scalars[0]);
1821   Type *ScalarTy = VL0->getType();
1822   if (StoreInst *SI = dyn_cast<StoreInst>(VL0))
1823     ScalarTy = SI->getValueOperand()->getType();
1824   VectorType *VecTy = VectorType::get(ScalarTy, E->Scalars.size());
1825
1826   if (E->NeedToGather) {
1827     setInsertPointAfterBundle(E->Scalars);
1828     return Gather(E->Scalars, VecTy);
1829   }
1830
1831   unsigned Opcode = getSameOpcode(E->Scalars);
1832
1833   switch (Opcode) {
1834     case Instruction::PHI: {
1835       PHINode *PH = dyn_cast<PHINode>(VL0);
1836       Builder.SetInsertPoint(PH->getParent()->getFirstNonPHI());
1837       Builder.SetCurrentDebugLocation(PH->getDebugLoc());
1838       PHINode *NewPhi = Builder.CreatePHI(VecTy, PH->getNumIncomingValues());
1839       E->VectorizedValue = NewPhi;
1840
1841       // PHINodes may have multiple entries from the same block. We want to
1842       // visit every block once.
1843       SmallSet<BasicBlock*, 4> VisitedBBs;
1844
1845       for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
1846         ValueList Operands;
1847         BasicBlock *IBB = PH->getIncomingBlock(i);
1848
1849         if (!VisitedBBs.insert(IBB)) {
1850           NewPhi->addIncoming(NewPhi->getIncomingValueForBlock(IBB), IBB);
1851           continue;
1852         }
1853
1854         // Prepare the operand vector.
1855         for (unsigned j = 0; j < E->Scalars.size(); ++j)
1856           Operands.push_back(cast<PHINode>(E->Scalars[j])->
1857                              getIncomingValueForBlock(IBB));
1858
1859         Builder.SetInsertPoint(IBB->getTerminator());
1860         Builder.SetCurrentDebugLocation(PH->getDebugLoc());
1861         Value *Vec = vectorizeTree(Operands);
1862         NewPhi->addIncoming(Vec, IBB);
1863       }
1864
1865       assert(NewPhi->getNumIncomingValues() == PH->getNumIncomingValues() &&
1866              "Invalid number of incoming values");
1867       return NewPhi;
1868     }
1869
1870     case Instruction::ExtractElement: {
1871       if (CanReuseExtract(E->Scalars)) {
1872         Value *V = VL0->getOperand(0);
1873         E->VectorizedValue = V;
1874         return V;
1875       }
1876       return Gather(E->Scalars, VecTy);
1877     }
1878     case Instruction::ZExt:
1879     case Instruction::SExt:
1880     case Instruction::FPToUI:
1881     case Instruction::FPToSI:
1882     case Instruction::FPExt:
1883     case Instruction::PtrToInt:
1884     case Instruction::IntToPtr:
1885     case Instruction::SIToFP:
1886     case Instruction::UIToFP:
1887     case Instruction::Trunc:
1888     case Instruction::FPTrunc:
1889     case Instruction::BitCast: {
1890       ValueList INVL;
1891       for (int i = 0, e = E->Scalars.size(); i < e; ++i)
1892         INVL.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0));
1893
1894       setInsertPointAfterBundle(E->Scalars);
1895
1896       Value *InVec = vectorizeTree(INVL);
1897
1898       if (Value *V = alreadyVectorized(E->Scalars))
1899         return V;
1900
1901       CastInst *CI = dyn_cast<CastInst>(VL0);
1902       Value *V = Builder.CreateCast(CI->getOpcode(), InVec, VecTy);
1903       E->VectorizedValue = V;
1904       ++NumVectorInstructions;
1905       return V;
1906     }
1907     case Instruction::FCmp:
1908     case Instruction::ICmp: {
1909       ValueList LHSV, RHSV;
1910       for (int i = 0, e = E->Scalars.size(); i < e; ++i) {
1911         LHSV.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0));
1912         RHSV.push_back(cast<Instruction>(E->Scalars[i])->getOperand(1));
1913       }
1914
1915       setInsertPointAfterBundle(E->Scalars);
1916
1917       Value *L = vectorizeTree(LHSV);
1918       Value *R = vectorizeTree(RHSV);
1919
1920       if (Value *V = alreadyVectorized(E->Scalars))
1921         return V;
1922
1923       CmpInst::Predicate P0 = dyn_cast<CmpInst>(VL0)->getPredicate();
1924       Value *V;
1925       if (Opcode == Instruction::FCmp)
1926         V = Builder.CreateFCmp(P0, L, R);
1927       else
1928         V = Builder.CreateICmp(P0, L, R);
1929
1930       E->VectorizedValue = V;
1931       ++NumVectorInstructions;
1932       return V;
1933     }
1934     case Instruction::Select: {
1935       ValueList TrueVec, FalseVec, CondVec;
1936       for (int i = 0, e = E->Scalars.size(); i < e; ++i) {
1937         CondVec.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0));
1938         TrueVec.push_back(cast<Instruction>(E->Scalars[i])->getOperand(1));
1939         FalseVec.push_back(cast<Instruction>(E->Scalars[i])->getOperand(2));
1940       }
1941
1942       setInsertPointAfterBundle(E->Scalars);
1943
1944       Value *Cond = vectorizeTree(CondVec);
1945       Value *True = vectorizeTree(TrueVec);
1946       Value *False = vectorizeTree(FalseVec);
1947
1948       if (Value *V = alreadyVectorized(E->Scalars))
1949         return V;
1950
1951       Value *V = Builder.CreateSelect(Cond, True, False);
1952       E->VectorizedValue = V;
1953       ++NumVectorInstructions;
1954       return V;
1955     }
1956     case Instruction::Add:
1957     case Instruction::FAdd:
1958     case Instruction::Sub:
1959     case Instruction::FSub:
1960     case Instruction::Mul:
1961     case Instruction::FMul:
1962     case Instruction::UDiv:
1963     case Instruction::SDiv:
1964     case Instruction::FDiv:
1965     case Instruction::URem:
1966     case Instruction::SRem:
1967     case Instruction::FRem:
1968     case Instruction::Shl:
1969     case Instruction::LShr:
1970     case Instruction::AShr:
1971     case Instruction::And:
1972     case Instruction::Or:
1973     case Instruction::Xor: {
1974       ValueList LHSVL, RHSVL;
1975       if (isa<BinaryOperator>(VL0) && VL0->isCommutative())
1976         reorderInputsAccordingToOpcode(E->Scalars, LHSVL, RHSVL);
1977       else
1978         for (int i = 0, e = E->Scalars.size(); i < e; ++i) {
1979           LHSVL.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0));
1980           RHSVL.push_back(cast<Instruction>(E->Scalars[i])->getOperand(1));
1981         }
1982
1983       setInsertPointAfterBundle(E->Scalars);
1984
1985       Value *LHS = vectorizeTree(LHSVL);
1986       Value *RHS = vectorizeTree(RHSVL);
1987
1988       if (LHS == RHS && isa<Instruction>(LHS)) {
1989         assert((VL0->getOperand(0) == VL0->getOperand(1)) && "Invalid order");
1990       }
1991
1992       if (Value *V = alreadyVectorized(E->Scalars))
1993         return V;
1994
1995       BinaryOperator *BinOp = cast<BinaryOperator>(VL0);
1996       Value *V = Builder.CreateBinOp(BinOp->getOpcode(), LHS, RHS);
1997       E->VectorizedValue = V;
1998       ++NumVectorInstructions;
1999
2000       if (Instruction *I = dyn_cast<Instruction>(V))
2001         return propagateMetadata(I, E->Scalars);
2002
2003       return V;
2004     }
2005     case Instruction::Load: {
2006       // Loads are inserted at the head of the tree because we don't want to
2007       // sink them all the way down past store instructions.
2008       setInsertPointAfterBundle(E->Scalars);
2009
2010       LoadInst *LI = cast<LoadInst>(VL0);
2011       Type *ScalarLoadTy = LI->getType();
2012       unsigned AS = LI->getPointerAddressSpace();
2013
2014       Value *VecPtr = Builder.CreateBitCast(LI->getPointerOperand(),
2015                                             VecTy->getPointerTo(AS));
2016       unsigned Alignment = LI->getAlignment();
2017       LI = Builder.CreateLoad(VecPtr);
2018       if (!Alignment)
2019         Alignment = DL->getABITypeAlignment(ScalarLoadTy);
2020       LI->setAlignment(Alignment);
2021       E->VectorizedValue = LI;
2022       ++NumVectorInstructions;
2023       return propagateMetadata(LI, E->Scalars);
2024     }
2025     case Instruction::Store: {
2026       StoreInst *SI = cast<StoreInst>(VL0);
2027       unsigned Alignment = SI->getAlignment();
2028       unsigned AS = SI->getPointerAddressSpace();
2029
2030       ValueList ValueOp;
2031       for (int i = 0, e = E->Scalars.size(); i < e; ++i)
2032         ValueOp.push_back(cast<StoreInst>(E->Scalars[i])->getValueOperand());
2033
2034       setInsertPointAfterBundle(E->Scalars);
2035
2036       Value *VecValue = vectorizeTree(ValueOp);
2037       Value *VecPtr = Builder.CreateBitCast(SI->getPointerOperand(),
2038                                             VecTy->getPointerTo(AS));
2039       StoreInst *S = Builder.CreateStore(VecValue, VecPtr);
2040       if (!Alignment)
2041         Alignment = DL->getABITypeAlignment(SI->getValueOperand()->getType());
2042       S->setAlignment(Alignment);
2043       E->VectorizedValue = S;
2044       ++NumVectorInstructions;
2045       return propagateMetadata(S, E->Scalars);
2046     }
2047     case Instruction::GetElementPtr: {
2048       setInsertPointAfterBundle(E->Scalars);
2049
2050       ValueList Op0VL;
2051       for (int i = 0, e = E->Scalars.size(); i < e; ++i)
2052         Op0VL.push_back(cast<GetElementPtrInst>(E->Scalars[i])->getOperand(0));
2053
2054       Value *Op0 = vectorizeTree(Op0VL);
2055
2056       std::vector<Value *> OpVecs;
2057       for (int j = 1, e = cast<GetElementPtrInst>(VL0)->getNumOperands(); j < e;
2058            ++j) {
2059         ValueList OpVL;
2060         for (int i = 0, e = E->Scalars.size(); i < e; ++i)
2061           OpVL.push_back(cast<GetElementPtrInst>(E->Scalars[i])->getOperand(j));
2062
2063         Value *OpVec = vectorizeTree(OpVL);
2064         OpVecs.push_back(OpVec);
2065       }
2066
2067       Value *V = Builder.CreateGEP(Op0, OpVecs);
2068       E->VectorizedValue = V;
2069       ++NumVectorInstructions;
2070
2071       if (Instruction *I = dyn_cast<Instruction>(V))
2072         return propagateMetadata(I, E->Scalars);
2073
2074       return V;
2075     }
2076     case Instruction::Call: {
2077       CallInst *CI = cast<CallInst>(VL0);
2078       setInsertPointAfterBundle(E->Scalars);
2079       Function *FI;
2080       Intrinsic::ID IID  = Intrinsic::not_intrinsic;
2081       if (CI && (FI = CI->getCalledFunction())) {
2082         IID = (Intrinsic::ID) FI->getIntrinsicID();
2083       }
2084       std::vector<Value *> OpVecs;
2085       for (int j = 0, e = CI->getNumArgOperands(); j < e; ++j) {
2086         ValueList OpVL;
2087         // ctlz,cttz and powi are special intrinsics whose second argument is
2088         // a scalar. This argument should not be vectorized.
2089         if (hasVectorInstrinsicScalarOpd(IID, 1) && j == 1) {
2090           CallInst *CEI = cast<CallInst>(E->Scalars[0]);
2091           OpVecs.push_back(CEI->getArgOperand(j));
2092           continue;
2093         }
2094         for (int i = 0, e = E->Scalars.size(); i < e; ++i) {
2095           CallInst *CEI = cast<CallInst>(E->Scalars[i]);
2096           OpVL.push_back(CEI->getArgOperand(j));
2097         }
2098
2099         Value *OpVec = vectorizeTree(OpVL);
2100         DEBUG(dbgs() << "SLP: OpVec[" << j << "]: " << *OpVec << "\n");
2101         OpVecs.push_back(OpVec);
2102       }
2103
2104       Module *M = F->getParent();
2105       Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
2106       Type *Tys[] = { VectorType::get(CI->getType(), E->Scalars.size()) };
2107       Function *CF = Intrinsic::getDeclaration(M, ID, Tys);
2108       Value *V = Builder.CreateCall(CF, OpVecs);
2109       E->VectorizedValue = V;
2110       ++NumVectorInstructions;
2111       return V;
2112     }
2113     case Instruction::ShuffleVector: {
2114       ValueList LHSVL, RHSVL;
2115       for (int i = 0, e = E->Scalars.size(); i < e; ++i) {
2116         LHSVL.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0));
2117         RHSVL.push_back(cast<Instruction>(E->Scalars[i])->getOperand(1));
2118       }
2119       setInsertPointAfterBundle(E->Scalars);
2120
2121       Value *LHS = vectorizeTree(LHSVL);
2122       Value *RHS = vectorizeTree(RHSVL);
2123
2124       if (Value *V = alreadyVectorized(E->Scalars))
2125         return V;
2126
2127       // Create a vector of LHS op1 RHS
2128       BinaryOperator *BinOp0 = cast<BinaryOperator>(VL0);
2129       Value *V0 = Builder.CreateBinOp(BinOp0->getOpcode(), LHS, RHS);
2130
2131       // Create a vector of LHS op2 RHS
2132       Instruction *VL1 = cast<Instruction>(E->Scalars[1]);
2133       BinaryOperator *BinOp1 = cast<BinaryOperator>(VL1);
2134       Value *V1 = Builder.CreateBinOp(BinOp1->getOpcode(), LHS, RHS);
2135
2136       // Create appropriate shuffle to take alternative operations from
2137       // the vector.
2138       std::vector<Constant *> Mask(E->Scalars.size());
2139       unsigned e = E->Scalars.size();
2140       for (unsigned i = 0; i < e; ++i) {
2141         if (i & 1)
2142           Mask[i] = Builder.getInt32(e + i);
2143         else
2144           Mask[i] = Builder.getInt32(i);
2145       }
2146
2147       Value *ShuffleMask = ConstantVector::get(Mask);
2148
2149       Value *V = Builder.CreateShuffleVector(V0, V1, ShuffleMask);
2150       E->VectorizedValue = V;
2151       ++NumVectorInstructions;
2152       if (Instruction *I = dyn_cast<Instruction>(V))
2153         return propagateMetadata(I, E->Scalars);
2154
2155       return V;
2156     }
2157     default:
2158     llvm_unreachable("unknown inst");
2159   }
2160   return nullptr;
2161 }
2162
2163 Value *BoUpSLP::vectorizeTree() {
2164
2165   // All blocks must be scheduled before any instructions are inserted.
2166   for (auto &BSIter : BlocksSchedules) {
2167     scheduleBlock(BSIter.second.get());
2168   }
2169
2170   Builder.SetInsertPoint(F->getEntryBlock().begin());
2171   vectorizeTree(&VectorizableTree[0]);
2172
2173   DEBUG(dbgs() << "SLP: Extracting " << ExternalUses.size() << " values .\n");
2174
2175   // Extract all of the elements with the external uses.
2176   for (UserList::iterator it = ExternalUses.begin(), e = ExternalUses.end();
2177        it != e; ++it) {
2178     Value *Scalar = it->Scalar;
2179     llvm::User *User = it->User;
2180
2181     // Skip users that we already RAUW. This happens when one instruction
2182     // has multiple uses of the same value.
2183     if (std::find(Scalar->user_begin(), Scalar->user_end(), User) ==
2184         Scalar->user_end())
2185       continue;
2186     assert(ScalarToTreeEntry.count(Scalar) && "Invalid scalar");
2187
2188     int Idx = ScalarToTreeEntry[Scalar];
2189     TreeEntry *E = &VectorizableTree[Idx];
2190     assert(!E->NeedToGather && "Extracting from a gather list");
2191
2192     Value *Vec = E->VectorizedValue;
2193     assert(Vec && "Can't find vectorizable value");
2194
2195     Value *Lane = Builder.getInt32(it->Lane);
2196     // Generate extracts for out-of-tree users.
2197     // Find the insertion point for the extractelement lane.
2198     if (isa<Instruction>(Vec)){
2199       if (PHINode *PH = dyn_cast<PHINode>(User)) {
2200         for (int i = 0, e = PH->getNumIncomingValues(); i != e; ++i) {
2201           if (PH->getIncomingValue(i) == Scalar) {
2202             Builder.SetInsertPoint(PH->getIncomingBlock(i)->getTerminator());
2203             Value *Ex = Builder.CreateExtractElement(Vec, Lane);
2204             CSEBlocks.insert(PH->getIncomingBlock(i));
2205             PH->setOperand(i, Ex);
2206           }
2207         }
2208       } else {
2209         Builder.SetInsertPoint(cast<Instruction>(User));
2210         Value *Ex = Builder.CreateExtractElement(Vec, Lane);
2211         CSEBlocks.insert(cast<Instruction>(User)->getParent());
2212         User->replaceUsesOfWith(Scalar, Ex);
2213      }
2214     } else {
2215       Builder.SetInsertPoint(F->getEntryBlock().begin());
2216       Value *Ex = Builder.CreateExtractElement(Vec, Lane);
2217       CSEBlocks.insert(&F->getEntryBlock());
2218       User->replaceUsesOfWith(Scalar, Ex);
2219     }
2220
2221     DEBUG(dbgs() << "SLP: Replaced:" << *User << ".\n");
2222   }
2223
2224   // For each vectorized value:
2225   for (int EIdx = 0, EE = VectorizableTree.size(); EIdx < EE; ++EIdx) {
2226     TreeEntry *Entry = &VectorizableTree[EIdx];
2227
2228     // For each lane:
2229     for (int Lane = 0, LE = Entry->Scalars.size(); Lane != LE; ++Lane) {
2230       Value *Scalar = Entry->Scalars[Lane];
2231       // No need to handle users of gathered values.
2232       if (Entry->NeedToGather)
2233         continue;
2234
2235       assert(Entry->VectorizedValue && "Can't find vectorizable value");
2236
2237       Type *Ty = Scalar->getType();
2238       if (!Ty->isVoidTy()) {
2239 #ifndef NDEBUG
2240         for (User *U : Scalar->users()) {
2241           DEBUG(dbgs() << "SLP: \tvalidating user:" << *U << ".\n");
2242
2243           assert((ScalarToTreeEntry.count(U) ||
2244                   // It is legal to replace users in the ignorelist by undef.
2245                   (std::find(UserIgnoreList.begin(), UserIgnoreList.end(), U) !=
2246                    UserIgnoreList.end())) &&
2247                  "Replacing out-of-tree value with undef");
2248         }
2249 #endif
2250         Value *Undef = UndefValue::get(Ty);
2251         Scalar->replaceAllUsesWith(Undef);
2252       }
2253       DEBUG(dbgs() << "SLP: \tErasing scalar:" << *Scalar << ".\n");
2254       cast<Instruction>(Scalar)->eraseFromParent();
2255     }
2256   }
2257
2258   Builder.ClearInsertionPoint();
2259
2260   return VectorizableTree[0].VectorizedValue;
2261 }
2262
2263 void BoUpSLP::optimizeGatherSequence() {
2264   DEBUG(dbgs() << "SLP: Optimizing " << GatherSeq.size()
2265         << " gather sequences instructions.\n");
2266   // LICM InsertElementInst sequences.
2267   for (SetVector<Instruction *>::iterator it = GatherSeq.begin(),
2268        e = GatherSeq.end(); it != e; ++it) {
2269     InsertElementInst *Insert = dyn_cast<InsertElementInst>(*it);
2270
2271     if (!Insert)
2272       continue;
2273
2274     // Check if this block is inside a loop.
2275     Loop *L = LI->getLoopFor(Insert->getParent());
2276     if (!L)
2277       continue;
2278
2279     // Check if it has a preheader.
2280     BasicBlock *PreHeader = L->getLoopPreheader();
2281     if (!PreHeader)
2282       continue;
2283
2284     // If the vector or the element that we insert into it are
2285     // instructions that are defined in this basic block then we can't
2286     // hoist this instruction.
2287     Instruction *CurrVec = dyn_cast<Instruction>(Insert->getOperand(0));
2288     Instruction *NewElem = dyn_cast<Instruction>(Insert->getOperand(1));
2289     if (CurrVec && L->contains(CurrVec))
2290       continue;
2291     if (NewElem && L->contains(NewElem))
2292       continue;
2293
2294     // We can hoist this instruction. Move it to the pre-header.
2295     Insert->moveBefore(PreHeader->getTerminator());
2296   }
2297
2298   // Make a list of all reachable blocks in our CSE queue.
2299   SmallVector<const DomTreeNode *, 8> CSEWorkList;
2300   CSEWorkList.reserve(CSEBlocks.size());
2301   for (BasicBlock *BB : CSEBlocks)
2302     if (DomTreeNode *N = DT->getNode(BB)) {
2303       assert(DT->isReachableFromEntry(N));
2304       CSEWorkList.push_back(N);
2305     }
2306
2307   // Sort blocks by domination. This ensures we visit a block after all blocks
2308   // dominating it are visited.
2309   std::stable_sort(CSEWorkList.begin(), CSEWorkList.end(),
2310                    [this](const DomTreeNode *A, const DomTreeNode *B) {
2311     return DT->properlyDominates(A, B);
2312   });
2313
2314   // Perform O(N^2) search over the gather sequences and merge identical
2315   // instructions. TODO: We can further optimize this scan if we split the
2316   // instructions into different buckets based on the insert lane.
2317   SmallVector<Instruction *, 16> Visited;
2318   for (auto I = CSEWorkList.begin(), E = CSEWorkList.end(); I != E; ++I) {
2319     assert((I == CSEWorkList.begin() || !DT->dominates(*I, *std::prev(I))) &&
2320            "Worklist not sorted properly!");
2321     BasicBlock *BB = (*I)->getBlock();
2322     // For all instructions in blocks containing gather sequences:
2323     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e;) {
2324       Instruction *In = it++;
2325       if (!isa<InsertElementInst>(In) && !isa<ExtractElementInst>(In))
2326         continue;
2327
2328       // Check if we can replace this instruction with any of the
2329       // visited instructions.
2330       for (SmallVectorImpl<Instruction *>::iterator v = Visited.begin(),
2331                                                     ve = Visited.end();
2332            v != ve; ++v) {
2333         if (In->isIdenticalTo(*v) &&
2334             DT->dominates((*v)->getParent(), In->getParent())) {
2335           In->replaceAllUsesWith(*v);
2336           In->eraseFromParent();
2337           In = nullptr;
2338           break;
2339         }
2340       }
2341       if (In) {
2342         assert(std::find(Visited.begin(), Visited.end(), In) == Visited.end());
2343         Visited.push_back(In);
2344       }
2345     }
2346   }
2347   CSEBlocks.clear();
2348   GatherSeq.clear();
2349 }
2350
2351 // Groups the instructions to a bundle (which is then a single scheduling entity)
2352 // and schedules instructions until the bundle gets ready.
2353 bool BoUpSLP::BlockScheduling::tryScheduleBundle(ArrayRef<Value *> VL,
2354                                                  AliasAnalysis *AA) {
2355   if (isa<PHINode>(VL[0]))
2356     return true;
2357
2358   // Initialize the instruction bundle.
2359   Instruction *OldScheduleEnd = ScheduleEnd;
2360   ScheduleData *PrevInBundle = nullptr;
2361   ScheduleData *Bundle = nullptr;
2362   bool ReSchedule = false;
2363   DEBUG(dbgs() << "SLP:  bundle: " << *VL[0] << "\n");
2364   for (Value *V : VL) {
2365     extendSchedulingRegion(V);
2366     ScheduleData *BundleMember = getScheduleData(V);
2367     assert(BundleMember &&
2368            "no ScheduleData for bundle member (maybe not in same basic block)");
2369     if (BundleMember->IsScheduled) {
2370       // A bundle member was scheduled as single instruction before and now
2371       // needs to be scheduled as part of the bundle. We just get rid of the
2372       // existing schedule.
2373       DEBUG(dbgs() << "SLP:  reset schedule because " << *BundleMember
2374                    << " was already scheduled\n");
2375       ReSchedule = true;
2376     }
2377     assert(BundleMember->isSchedulingEntity() &&
2378            "bundle member already part of other bundle");
2379     if (PrevInBundle) {
2380       PrevInBundle->NextInBundle = BundleMember;
2381     } else {
2382       Bundle = BundleMember;
2383     }
2384     BundleMember->UnscheduledDepsInBundle = 0;
2385     Bundle->UnscheduledDepsInBundle += BundleMember->UnscheduledDeps;
2386
2387     // Group the instructions to a bundle.
2388     BundleMember->FirstInBundle = Bundle;
2389     PrevInBundle = BundleMember;
2390   }
2391   if (ScheduleEnd != OldScheduleEnd) {
2392     // The scheduling region got new instructions at the lower end (or it is a
2393     // new region for the first bundle). This makes it necessary to
2394     // recalculate all dependencies.
2395     // It is seldom that this needs to be done a second time after adding the
2396     // initial bundle to the region.
2397     for (auto *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) {
2398       ScheduleData *SD = getScheduleData(I);
2399       SD->clearDependencies();
2400     }
2401     ReSchedule = true;
2402   }
2403   if (ReSchedule) {
2404     resetSchedule();
2405     initialFillReadyList(ReadyInsts);
2406   }
2407
2408   DEBUG(dbgs() << "SLP: try schedule bundle " << *Bundle << " in block "
2409                << BB->getName() << "\n");
2410
2411   calculateDependencies(Bundle, true, AA);
2412
2413   // Now try to schedule the new bundle. As soon as the bundle is "ready" it
2414   // means that there are no cyclic dependencies and we can schedule it.
2415   // Note that's important that we don't "schedule" the bundle yet (see
2416   // cancelScheduling).
2417   while (!Bundle->isReady() && !ReadyInsts.empty()) {
2418
2419     ScheduleData *pickedSD = ReadyInsts.back();
2420     ReadyInsts.pop_back();
2421
2422     if (pickedSD->isSchedulingEntity() && pickedSD->isReady()) {
2423       schedule(pickedSD, ReadyInsts);
2424     }
2425   }
2426   return Bundle->isReady();
2427 }
2428
2429 void BoUpSLP::BlockScheduling::cancelScheduling(ArrayRef<Value *> VL) {
2430   if (isa<PHINode>(VL[0]))
2431     return;
2432
2433   ScheduleData *Bundle = getScheduleData(VL[0]);
2434   DEBUG(dbgs() << "SLP:  cancel scheduling of " << *Bundle << "\n");
2435   assert(!Bundle->IsScheduled &&
2436          "Can't cancel bundle which is already scheduled");
2437   assert(Bundle->isSchedulingEntity() && Bundle->isPartOfBundle() &&
2438          "tried to unbundle something which is not a bundle");
2439
2440   // Un-bundle: make single instructions out of the bundle.
2441   ScheduleData *BundleMember = Bundle;
2442   while (BundleMember) {
2443     assert(BundleMember->FirstInBundle == Bundle && "corrupt bundle links");
2444     BundleMember->FirstInBundle = BundleMember;
2445     ScheduleData *Next = BundleMember->NextInBundle;
2446     BundleMember->NextInBundle = nullptr;
2447     BundleMember->UnscheduledDepsInBundle = BundleMember->UnscheduledDeps;
2448     if (BundleMember->UnscheduledDepsInBundle == 0) {
2449       ReadyInsts.insert(BundleMember);
2450     }
2451     BundleMember = Next;
2452   }
2453 }
2454
2455 void BoUpSLP::BlockScheduling::extendSchedulingRegion(Value *V) {
2456   if (getScheduleData(V))
2457     return;
2458   Instruction *I = dyn_cast<Instruction>(V);
2459   assert(I && "bundle member must be an instruction");
2460   assert(!isa<PHINode>(I) && "phi nodes don't need to be scheduled");
2461   if (!ScheduleStart) {
2462     // It's the first instruction in the new region.
2463     initScheduleData(I, I->getNextNode(), nullptr, nullptr);
2464     ScheduleStart = I;
2465     ScheduleEnd = I->getNextNode();
2466     assert(ScheduleEnd && "tried to vectorize a TerminatorInst?");
2467     DEBUG(dbgs() << "SLP:  initialize schedule region to " << *I << "\n");
2468     return;
2469   }
2470   // Search up and down at the same time, because we don't know if the new
2471   // instruction is above or below the existing scheduling region.
2472   BasicBlock::reverse_iterator UpIter(ScheduleStart);
2473   BasicBlock::reverse_iterator UpperEnd = BB->rend();
2474   BasicBlock::iterator DownIter(ScheduleEnd);
2475   BasicBlock::iterator LowerEnd = BB->end();
2476   for (;;) {
2477     if (UpIter != UpperEnd) {
2478       if (&*UpIter == I) {
2479         initScheduleData(I, ScheduleStart, nullptr, FirstLoadStoreInRegion);
2480         ScheduleStart = I;
2481         DEBUG(dbgs() << "SLP:  extend schedule region start to " << *I << "\n");
2482         return;
2483       }
2484       UpIter++;
2485     }
2486     if (DownIter != LowerEnd) {
2487       if (&*DownIter == I) {
2488         initScheduleData(ScheduleEnd, I->getNextNode(), LastLoadStoreInRegion,
2489                          nullptr);
2490         ScheduleEnd = I->getNextNode();
2491         assert(ScheduleEnd && "tried to vectorize a TerminatorInst?");
2492         DEBUG(dbgs() << "SLP:  extend schedule region end to " << *I << "\n");
2493         return;
2494       }
2495       DownIter++;
2496     }
2497     assert((UpIter != UpperEnd || DownIter != LowerEnd) &&
2498            "instruction not found in block");
2499   }
2500 }
2501
2502 void BoUpSLP::BlockScheduling::initScheduleData(Instruction *FromI,
2503                                                 Instruction *ToI,
2504                                                 ScheduleData *PrevLoadStore,
2505                                                 ScheduleData *NextLoadStore) {
2506   ScheduleData *CurrentLoadStore = PrevLoadStore;
2507   for (Instruction *I = FromI; I != ToI; I = I->getNextNode()) {
2508     ScheduleData *SD = ScheduleDataMap[I];
2509     if (!SD) {
2510       // Allocate a new ScheduleData for the instruction.
2511       if (ChunkPos >= ChunkSize) {
2512         ScheduleDataChunks.push_back(
2513             llvm::make_unique<ScheduleData[]>(ChunkSize));
2514         ChunkPos = 0;
2515       }
2516       SD = &(ScheduleDataChunks.back()[ChunkPos++]);
2517       ScheduleDataMap[I] = SD;
2518       SD->Inst = I;
2519     }
2520     assert(!isInSchedulingRegion(SD) &&
2521            "new ScheduleData already in scheduling region");
2522     SD->init(SchedulingRegionID);
2523
2524     if (I->mayReadOrWriteMemory()) {
2525       // Update the linked list of memory accessing instructions.
2526       if (CurrentLoadStore) {
2527         CurrentLoadStore->NextLoadStore = SD;
2528       } else {
2529         FirstLoadStoreInRegion = SD;
2530       }
2531       CurrentLoadStore = SD;
2532     }
2533   }
2534   if (NextLoadStore) {
2535     if (CurrentLoadStore)
2536       CurrentLoadStore->NextLoadStore = NextLoadStore;
2537   } else {
2538     LastLoadStoreInRegion = CurrentLoadStore;
2539   }
2540 }
2541
2542 /// \returns the AA location that is being access by the instruction.
2543 static AliasAnalysis::Location getLocation(Instruction *I, AliasAnalysis *AA) {
2544   if (StoreInst *SI = dyn_cast<StoreInst>(I))
2545     return AA->getLocation(SI);
2546   if (LoadInst *LI = dyn_cast<LoadInst>(I))
2547     return AA->getLocation(LI);
2548   return AliasAnalysis::Location();
2549 }
2550
2551 void BoUpSLP::BlockScheduling::calculateDependencies(ScheduleData *SD,
2552                                                      bool InsertInReadyList,
2553                                                      AliasAnalysis *AA) {
2554   assert(SD->isSchedulingEntity());
2555
2556   SmallVector<ScheduleData *, 10> WorkList;
2557   WorkList.push_back(SD);
2558
2559   while (!WorkList.empty()) {
2560     ScheduleData *SD = WorkList.back();
2561     WorkList.pop_back();
2562
2563     ScheduleData *BundleMember = SD;
2564     while (BundleMember) {
2565       assert(isInSchedulingRegion(BundleMember));
2566       if (!BundleMember->hasValidDependencies()) {
2567
2568         DEBUG(dbgs() << "SLP:       update deps of " << *BundleMember << "\n");
2569         BundleMember->Dependencies = 0;
2570         BundleMember->resetUnscheduledDeps();
2571
2572         // Handle def-use chain dependencies.
2573         for (User *U : BundleMember->Inst->users()) {
2574           if (isa<Instruction>(U)) {
2575             ScheduleData *UseSD = getScheduleData(U);
2576             if (UseSD && isInSchedulingRegion(UseSD->FirstInBundle)) {
2577               BundleMember->Dependencies++;
2578               ScheduleData *DestBundle = UseSD->FirstInBundle;
2579               if (!DestBundle->IsScheduled) {
2580                 BundleMember->incrementUnscheduledDeps(1);
2581               }
2582               if (!DestBundle->hasValidDependencies()) {
2583                 WorkList.push_back(DestBundle);
2584               }
2585             }
2586           } else {
2587             // I'm not sure if this can ever happen. But we need to be safe.
2588             // This lets the instruction/bundle never be scheduled and eventally
2589             // disable vectorization.
2590             BundleMember->Dependencies++;
2591             BundleMember->incrementUnscheduledDeps(1);
2592           }
2593         }
2594
2595         // Handle the memory dependencies.
2596         ScheduleData *DepDest = BundleMember->NextLoadStore;
2597         if (DepDest) {
2598           AliasAnalysis::Location SrcLoc = getLocation(BundleMember->Inst, AA);
2599           bool SrcMayWrite = BundleMember->Inst->mayWriteToMemory();
2600
2601           while (DepDest) {
2602             assert(isInSchedulingRegion(DepDest));
2603             if (SrcMayWrite || DepDest->Inst->mayWriteToMemory()) {
2604               AliasAnalysis::Location DstLoc = getLocation(DepDest->Inst, AA);
2605               if (!SrcLoc.Ptr || !DstLoc.Ptr || AA->alias(SrcLoc, DstLoc)) {
2606                 DepDest->MemoryDependencies.push_back(BundleMember);
2607                 BundleMember->Dependencies++;
2608                 ScheduleData *DestBundle = DepDest->FirstInBundle;
2609                 if (!DestBundle->IsScheduled) {
2610                   BundleMember->incrementUnscheduledDeps(1);
2611                 }
2612                 if (!DestBundle->hasValidDependencies()) {
2613                   WorkList.push_back(DestBundle);
2614                 }
2615               }
2616             }
2617             DepDest = DepDest->NextLoadStore;
2618           }
2619         }
2620       }
2621       BundleMember = BundleMember->NextInBundle;
2622     }
2623     if (InsertInReadyList && SD->isReady()) {
2624       ReadyInsts.push_back(SD);
2625       DEBUG(dbgs() << "SLP:     gets ready on update: " << *SD->Inst << "\n");
2626     }
2627   }
2628 }
2629
2630 void BoUpSLP::BlockScheduling::resetSchedule() {
2631   assert(ScheduleStart &&
2632          "tried to reset schedule on block which has not been scheduled");
2633   for (Instruction *I = ScheduleStart; I != ScheduleEnd; I = I->getNextNode()) {
2634     ScheduleData *SD = getScheduleData(I);
2635     assert(isInSchedulingRegion(SD));
2636     SD->IsScheduled = false;
2637     SD->resetUnscheduledDeps();
2638   }
2639   ReadyInsts.clear();
2640 }
2641
2642 void BoUpSLP::scheduleBlock(BlockScheduling *BS) {
2643
2644   if (!BS->ScheduleStart)
2645     return;
2646
2647   DEBUG(dbgs() << "SLP: schedule block " << BS->BB->getName() << "\n");
2648
2649   BS->resetSchedule();
2650
2651   // For the real scheduling we use a more sophisticated ready-list: it is
2652   // sorted by the original instruction location. This lets the final schedule
2653   // be as  close as possible to the original instruction order.
2654   struct ScheduleDataCompare {
2655     bool operator()(ScheduleData *SD1, ScheduleData *SD2) {
2656       return SD2->SchedulingPriority < SD1->SchedulingPriority;
2657     }
2658   };
2659   std::set<ScheduleData *, ScheduleDataCompare> ReadyInsts;
2660
2661   // Ensure that all depencency data is updated and fill the ready-list with
2662   // initial instructions.
2663   int Idx = 0;
2664   int NumToSchedule = 0;
2665   for (auto *I = BS->ScheduleStart; I != BS->ScheduleEnd;
2666        I = I->getNextNode()) {
2667     ScheduleData *SD = BS->getScheduleData(I);
2668     assert(
2669         SD->isPartOfBundle() == (ScalarToTreeEntry.count(SD->Inst) != 0) &&
2670         "scheduler and vectorizer have different opinion on what is a bundle");
2671     SD->FirstInBundle->SchedulingPriority = Idx++;
2672     if (SD->isSchedulingEntity()) {
2673       BS->calculateDependencies(SD, false, AA);
2674       NumToSchedule++;
2675     }
2676   }
2677   BS->initialFillReadyList(ReadyInsts);
2678
2679   Instruction *LastScheduledInst = BS->ScheduleEnd;
2680
2681   // Do the "real" scheduling.
2682   while (!ReadyInsts.empty()) {
2683     ScheduleData *picked = *ReadyInsts.begin();
2684     ReadyInsts.erase(ReadyInsts.begin());
2685
2686     // Move the scheduled instruction(s) to their dedicated places, if not
2687     // there yet.
2688     ScheduleData *BundleMember = picked;
2689     while (BundleMember) {
2690       Instruction *pickedInst = BundleMember->Inst;
2691       if (LastScheduledInst->getNextNode() != pickedInst) {
2692         BS->BB->getInstList().remove(pickedInst);
2693         BS->BB->getInstList().insert(LastScheduledInst, pickedInst);
2694       }
2695       LastScheduledInst = pickedInst;
2696       BundleMember = BundleMember->NextInBundle;
2697     }
2698
2699     BS->schedule(picked, ReadyInsts);
2700     NumToSchedule--;
2701   }
2702   assert(NumToSchedule == 0 && "could not schedule all instructions");
2703
2704   // Avoid duplicate scheduling of the block.
2705   BS->ScheduleStart = nullptr;
2706 }
2707
2708 /// The SLPVectorizer Pass.
2709 struct SLPVectorizer : public FunctionPass {
2710   typedef SmallVector<StoreInst *, 8> StoreList;
2711   typedef MapVector<Value *, StoreList> StoreListMap;
2712
2713   /// Pass identification, replacement for typeid
2714   static char ID;
2715
2716   explicit SLPVectorizer() : FunctionPass(ID) {
2717     initializeSLPVectorizerPass(*PassRegistry::getPassRegistry());
2718   }
2719
2720   ScalarEvolution *SE;
2721   const DataLayout *DL;
2722   TargetTransformInfo *TTI;
2723   TargetLibraryInfo *TLI;
2724   AliasAnalysis *AA;
2725   LoopInfo *LI;
2726   DominatorTree *DT;
2727
2728   bool runOnFunction(Function &F) override {
2729     if (skipOptnoneFunction(F))
2730       return false;
2731
2732     SE = &getAnalysis<ScalarEvolution>();
2733     DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
2734     DL = DLP ? &DLP->getDataLayout() : nullptr;
2735     TTI = &getAnalysis<TargetTransformInfo>();
2736     TLI = getAnalysisIfAvailable<TargetLibraryInfo>();
2737     AA = &getAnalysis<AliasAnalysis>();
2738     LI = &getAnalysis<LoopInfo>();
2739     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2740
2741     StoreRefs.clear();
2742     bool Changed = false;
2743
2744     // If the target claims to have no vector registers don't attempt
2745     // vectorization.
2746     if (!TTI->getNumberOfRegisters(true))
2747       return false;
2748
2749     // Must have DataLayout. We can't require it because some tests run w/o
2750     // triple.
2751     if (!DL)
2752       return false;
2753
2754     // Don't vectorize when the attribute NoImplicitFloat is used.
2755     if (F.hasFnAttribute(Attribute::NoImplicitFloat))
2756       return false;
2757
2758     DEBUG(dbgs() << "SLP: Analyzing blocks in " << F.getName() << ".\n");
2759
2760     // Use the bottom up slp vectorizer to construct chains that start with
2761     // store instructions.
2762     BoUpSLP R(&F, SE, DL, TTI, TLI, AA, LI, DT);
2763
2764     // Scan the blocks in the function in post order.
2765     for (po_iterator<BasicBlock*> it = po_begin(&F.getEntryBlock()),
2766          e = po_end(&F.getEntryBlock()); it != e; ++it) {
2767       BasicBlock *BB = *it;
2768       // Vectorize trees that end at stores.
2769       if (unsigned count = collectStores(BB, R)) {
2770         (void)count;
2771         DEBUG(dbgs() << "SLP: Found " << count << " stores to vectorize.\n");
2772         Changed |= vectorizeStoreChains(R);
2773       }
2774
2775       // Vectorize trees that end at reductions.
2776       Changed |= vectorizeChainsInBlock(BB, R);
2777     }
2778
2779     if (Changed) {
2780       R.optimizeGatherSequence();
2781       DEBUG(dbgs() << "SLP: vectorized \"" << F.getName() << "\"\n");
2782       DEBUG(verifyFunction(F));
2783     }
2784     return Changed;
2785   }
2786
2787   void getAnalysisUsage(AnalysisUsage &AU) const override {
2788     FunctionPass::getAnalysisUsage(AU);
2789     AU.addRequired<ScalarEvolution>();
2790     AU.addRequired<AliasAnalysis>();
2791     AU.addRequired<TargetTransformInfo>();
2792     AU.addRequired<LoopInfo>();
2793     AU.addRequired<DominatorTreeWrapperPass>();
2794     AU.addPreserved<LoopInfo>();
2795     AU.addPreserved<DominatorTreeWrapperPass>();
2796     AU.setPreservesCFG();
2797   }
2798
2799 private:
2800
2801   /// \brief Collect memory references and sort them according to their base
2802   /// object. We sort the stores to their base objects to reduce the cost of the
2803   /// quadratic search on the stores. TODO: We can further reduce this cost
2804   /// if we flush the chain creation every time we run into a memory barrier.
2805   unsigned collectStores(BasicBlock *BB, BoUpSLP &R);
2806
2807   /// \brief Try to vectorize a chain that starts at two arithmetic instrs.
2808   bool tryToVectorizePair(Value *A, Value *B, BoUpSLP &R);
2809
2810   /// \brief Try to vectorize a list of operands.
2811   /// \@param BuildVector A list of users to ignore for the purpose of
2812   ///                     scheduling and that don't need extracting.
2813   /// \returns true if a value was vectorized.
2814   bool tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R,
2815                           ArrayRef<Value *> BuildVector = None,
2816                           bool allowReorder = false);
2817
2818   /// \brief Try to vectorize a chain that may start at the operands of \V;
2819   bool tryToVectorize(BinaryOperator *V, BoUpSLP &R);
2820
2821   /// \brief Vectorize the stores that were collected in StoreRefs.
2822   bool vectorizeStoreChains(BoUpSLP &R);
2823
2824   /// \brief Scan the basic block and look for patterns that are likely to start
2825   /// a vectorization chain.
2826   bool vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R);
2827
2828   bool vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold,
2829                            BoUpSLP &R);
2830
2831   bool vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold,
2832                        BoUpSLP &R);
2833 private:
2834   StoreListMap StoreRefs;
2835 };
2836
2837 /// \brief Check that the Values in the slice in VL array are still existent in
2838 /// the WeakVH array.
2839 /// Vectorization of part of the VL array may cause later values in the VL array
2840 /// to become invalid. We track when this has happened in the WeakVH array.
2841 static bool hasValueBeenRAUWed(ArrayRef<Value *> &VL,
2842                                SmallVectorImpl<WeakVH> &VH,
2843                                unsigned SliceBegin,
2844                                unsigned SliceSize) {
2845   for (unsigned i = SliceBegin; i < SliceBegin + SliceSize; ++i)
2846     if (VH[i] != VL[i])
2847       return true;
2848
2849   return false;
2850 }
2851
2852 bool SLPVectorizer::vectorizeStoreChain(ArrayRef<Value *> Chain,
2853                                           int CostThreshold, BoUpSLP &R) {
2854   unsigned ChainLen = Chain.size();
2855   DEBUG(dbgs() << "SLP: Analyzing a store chain of length " << ChainLen
2856         << "\n");
2857   Type *StoreTy = cast<StoreInst>(Chain[0])->getValueOperand()->getType();
2858   unsigned Sz = DL->getTypeSizeInBits(StoreTy);
2859   unsigned VF = MinVecRegSize / Sz;
2860
2861   if (!isPowerOf2_32(Sz) || VF < 2)
2862     return false;
2863
2864   // Keep track of values that were deleted by vectorizing in the loop below.
2865   SmallVector<WeakVH, 8> TrackValues(Chain.begin(), Chain.end());
2866
2867   bool Changed = false;
2868   // Look for profitable vectorizable trees at all offsets, starting at zero.
2869   for (unsigned i = 0, e = ChainLen; i < e; ++i) {
2870     if (i + VF > e)
2871       break;
2872
2873     // Check that a previous iteration of this loop did not delete the Value.
2874     if (hasValueBeenRAUWed(Chain, TrackValues, i, VF))
2875       continue;
2876
2877     DEBUG(dbgs() << "SLP: Analyzing " << VF << " stores at offset " << i
2878           << "\n");
2879     ArrayRef<Value *> Operands = Chain.slice(i, VF);
2880
2881     R.buildTree(Operands);
2882
2883     int Cost = R.getTreeCost();
2884
2885     DEBUG(dbgs() << "SLP: Found cost=" << Cost << " for VF=" << VF << "\n");
2886     if (Cost < CostThreshold) {
2887       DEBUG(dbgs() << "SLP: Decided to vectorize cost=" << Cost << "\n");
2888       R.vectorizeTree();
2889
2890       // Move to the next bundle.
2891       i += VF - 1;
2892       Changed = true;
2893     }
2894   }
2895
2896   return Changed;
2897 }
2898
2899 bool SLPVectorizer::vectorizeStores(ArrayRef<StoreInst *> Stores,
2900                                     int costThreshold, BoUpSLP &R) {
2901   SetVector<Value *> Heads, Tails;
2902   SmallDenseMap<Value *, Value *> ConsecutiveChain;
2903
2904   // We may run into multiple chains that merge into a single chain. We mark the
2905   // stores that we vectorized so that we don't visit the same store twice.
2906   BoUpSLP::ValueSet VectorizedStores;
2907   bool Changed = false;
2908
2909   // Do a quadratic search on all of the given stores and find
2910   // all of the pairs of stores that follow each other.
2911   for (unsigned i = 0, e = Stores.size(); i < e; ++i) {
2912     for (unsigned j = 0; j < e; ++j) {
2913       if (i == j)
2914         continue;
2915
2916       if (R.isConsecutiveAccess(Stores[i], Stores[j])) {
2917         Tails.insert(Stores[j]);
2918         Heads.insert(Stores[i]);
2919         ConsecutiveChain[Stores[i]] = Stores[j];
2920       }
2921     }
2922   }
2923
2924   // For stores that start but don't end a link in the chain:
2925   for (SetVector<Value *>::iterator it = Heads.begin(), e = Heads.end();
2926        it != e; ++it) {
2927     if (Tails.count(*it))
2928       continue;
2929
2930     // We found a store instr that starts a chain. Now follow the chain and try
2931     // to vectorize it.
2932     BoUpSLP::ValueList Operands;
2933     Value *I = *it;
2934     // Collect the chain into a list.
2935     while (Tails.count(I) || Heads.count(I)) {
2936       if (VectorizedStores.count(I))
2937         break;
2938       Operands.push_back(I);
2939       // Move to the next value in the chain.
2940       I = ConsecutiveChain[I];
2941     }
2942
2943     bool Vectorized = vectorizeStoreChain(Operands, costThreshold, R);
2944
2945     // Mark the vectorized stores so that we don't vectorize them again.
2946     if (Vectorized)
2947       VectorizedStores.insert(Operands.begin(), Operands.end());
2948     Changed |= Vectorized;
2949   }
2950
2951   return Changed;
2952 }
2953
2954
2955 unsigned SLPVectorizer::collectStores(BasicBlock *BB, BoUpSLP &R) {
2956   unsigned count = 0;
2957   StoreRefs.clear();
2958   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
2959     StoreInst *SI = dyn_cast<StoreInst>(it);
2960     if (!SI)
2961       continue;
2962
2963     // Don't touch volatile stores.
2964     if (!SI->isSimple())
2965       continue;
2966
2967     // Check that the pointer points to scalars.
2968     Type *Ty = SI->getValueOperand()->getType();
2969     if (Ty->isAggregateType() || Ty->isVectorTy())
2970       continue;
2971
2972     // Find the base pointer.
2973     Value *Ptr = GetUnderlyingObject(SI->getPointerOperand(), DL);
2974
2975     // Save the store locations.
2976     StoreRefs[Ptr].push_back(SI);
2977     count++;
2978   }
2979   return count;
2980 }
2981
2982 bool SLPVectorizer::tryToVectorizePair(Value *A, Value *B, BoUpSLP &R) {
2983   if (!A || !B)
2984     return false;
2985   Value *VL[] = { A, B };
2986   return tryToVectorizeList(VL, R, None, true);
2987 }
2988
2989 bool SLPVectorizer::tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R,
2990                                        ArrayRef<Value *> BuildVector,
2991                                        bool allowReorder) {
2992   if (VL.size() < 2)
2993     return false;
2994
2995   DEBUG(dbgs() << "SLP: Vectorizing a list of length = " << VL.size() << ".\n");
2996
2997   // Check that all of the parts are scalar instructions of the same type.
2998   Instruction *I0 = dyn_cast<Instruction>(VL[0]);
2999   if (!I0)
3000     return false;
3001
3002   unsigned Opcode0 = I0->getOpcode();
3003
3004   Type *Ty0 = I0->getType();
3005   unsigned Sz = DL->getTypeSizeInBits(Ty0);
3006   unsigned VF = MinVecRegSize / Sz;
3007
3008   for (int i = 0, e = VL.size(); i < e; ++i) {
3009     Type *Ty = VL[i]->getType();
3010     if (Ty->isAggregateType() || Ty->isVectorTy())
3011       return false;
3012     Instruction *Inst = dyn_cast<Instruction>(VL[i]);
3013     if (!Inst || Inst->getOpcode() != Opcode0)
3014       return false;
3015   }
3016
3017   bool Changed = false;
3018
3019   // Keep track of values that were deleted by vectorizing in the loop below.
3020   SmallVector<WeakVH, 8> TrackValues(VL.begin(), VL.end());
3021
3022   for (unsigned i = 0, e = VL.size(); i < e; ++i) {
3023     unsigned OpsWidth = 0;
3024
3025     if (i + VF > e)
3026       OpsWidth = e - i;
3027     else
3028       OpsWidth = VF;
3029
3030     if (!isPowerOf2_32(OpsWidth) || OpsWidth < 2)
3031       break;
3032
3033     // Check that a previous iteration of this loop did not delete the Value.
3034     if (hasValueBeenRAUWed(VL, TrackValues, i, OpsWidth))
3035       continue;
3036
3037     DEBUG(dbgs() << "SLP: Analyzing " << OpsWidth << " operations "
3038                  << "\n");
3039     ArrayRef<Value *> Ops = VL.slice(i, OpsWidth);
3040
3041     ArrayRef<Value *> BuildVectorSlice;
3042     if (!BuildVector.empty())
3043       BuildVectorSlice = BuildVector.slice(i, OpsWidth);
3044
3045     R.buildTree(Ops, BuildVectorSlice);
3046     // TODO: check if we can allow reordering also for other cases than
3047     // tryToVectorizePair()
3048     if (allowReorder && R.shouldReorder()) {
3049       assert(Ops.size() == 2);
3050       assert(BuildVectorSlice.empty());
3051       Value *ReorderedOps[] = { Ops[1], Ops[0] };
3052       R.buildTree(ReorderedOps, None);
3053     }
3054     int Cost = R.getTreeCost();
3055
3056     if (Cost < -SLPCostThreshold) {
3057       DEBUG(dbgs() << "SLP: Vectorizing list at cost:" << Cost << ".\n");
3058       Value *VectorizedRoot = R.vectorizeTree();
3059
3060       // Reconstruct the build vector by extracting the vectorized root. This
3061       // way we handle the case where some elements of the vector are undefined.
3062       //  (return (inserelt <4 xi32> (insertelt undef (opd0) 0) (opd1) 2))
3063       if (!BuildVectorSlice.empty()) {
3064         // The insert point is the last build vector instruction. The vectorized
3065         // root will precede it. This guarantees that we get an instruction. The
3066         // vectorized tree could have been constant folded.
3067         Instruction *InsertAfter = cast<Instruction>(BuildVectorSlice.back());
3068         unsigned VecIdx = 0;
3069         for (auto &V : BuildVectorSlice) {
3070           IRBuilder<true, NoFolder> Builder(
3071               ++BasicBlock::iterator(InsertAfter));
3072           InsertElementInst *IE = cast<InsertElementInst>(V);
3073           Instruction *Extract = cast<Instruction>(Builder.CreateExtractElement(
3074               VectorizedRoot, Builder.getInt32(VecIdx++)));
3075           IE->setOperand(1, Extract);
3076           IE->removeFromParent();
3077           IE->insertAfter(Extract);
3078           InsertAfter = IE;
3079         }
3080       }
3081       // Move to the next bundle.
3082       i += VF - 1;
3083       Changed = true;
3084     }
3085   }
3086
3087   return Changed;
3088 }
3089
3090 bool SLPVectorizer::tryToVectorize(BinaryOperator *V, BoUpSLP &R) {
3091   if (!V)
3092     return false;
3093
3094   // Try to vectorize V.
3095   if (tryToVectorizePair(V->getOperand(0), V->getOperand(1), R))
3096     return true;
3097
3098   BinaryOperator *A = dyn_cast<BinaryOperator>(V->getOperand(0));
3099   BinaryOperator *B = dyn_cast<BinaryOperator>(V->getOperand(1));
3100   // Try to skip B.
3101   if (B && B->hasOneUse()) {
3102     BinaryOperator *B0 = dyn_cast<BinaryOperator>(B->getOperand(0));
3103     BinaryOperator *B1 = dyn_cast<BinaryOperator>(B->getOperand(1));
3104     if (tryToVectorizePair(A, B0, R)) {
3105       B->moveBefore(V);
3106       return true;
3107     }
3108     if (tryToVectorizePair(A, B1, R)) {
3109       B->moveBefore(V);
3110       return true;
3111     }
3112   }
3113
3114   // Try to skip A.
3115   if (A && A->hasOneUse()) {
3116     BinaryOperator *A0 = dyn_cast<BinaryOperator>(A->getOperand(0));
3117     BinaryOperator *A1 = dyn_cast<BinaryOperator>(A->getOperand(1));
3118     if (tryToVectorizePair(A0, B, R)) {
3119       A->moveBefore(V);
3120       return true;
3121     }
3122     if (tryToVectorizePair(A1, B, R)) {
3123       A->moveBefore(V);
3124       return true;
3125     }
3126   }
3127   return 0;
3128 }
3129
3130 /// \brief Generate a shuffle mask to be used in a reduction tree.
3131 ///
3132 /// \param VecLen The length of the vector to be reduced.
3133 /// \param NumEltsToRdx The number of elements that should be reduced in the
3134 ///        vector.
3135 /// \param IsPairwise Whether the reduction is a pairwise or splitting
3136 ///        reduction. A pairwise reduction will generate a mask of
3137 ///        <0,2,...> or <1,3,..> while a splitting reduction will generate
3138 ///        <2,3, undef,undef> for a vector of 4 and NumElts = 2.
3139 /// \param IsLeft True will generate a mask of even elements, odd otherwise.
3140 static Value *createRdxShuffleMask(unsigned VecLen, unsigned NumEltsToRdx,
3141                                    bool IsPairwise, bool IsLeft,
3142                                    IRBuilder<> &Builder) {
3143   assert((IsPairwise || !IsLeft) && "Don't support a <0,1,undef,...> mask");
3144
3145   SmallVector<Constant *, 32> ShuffleMask(
3146       VecLen, UndefValue::get(Builder.getInt32Ty()));
3147
3148   if (IsPairwise)
3149     // Build a mask of 0, 2, ... (left) or 1, 3, ... (right).
3150     for (unsigned i = 0; i != NumEltsToRdx; ++i)
3151       ShuffleMask[i] = Builder.getInt32(2 * i + !IsLeft);
3152   else
3153     // Move the upper half of the vector to the lower half.
3154     for (unsigned i = 0; i != NumEltsToRdx; ++i)
3155       ShuffleMask[i] = Builder.getInt32(NumEltsToRdx + i);
3156
3157   return ConstantVector::get(ShuffleMask);
3158 }
3159
3160
3161 /// Model horizontal reductions.
3162 ///
3163 /// A horizontal reduction is a tree of reduction operations (currently add and
3164 /// fadd) that has operations that can be put into a vector as its leaf.
3165 /// For example, this tree:
3166 ///
3167 /// mul mul mul mul
3168 ///  \  /    \  /
3169 ///   +       +
3170 ///    \     /
3171 ///       +
3172 /// This tree has "mul" as its reduced values and "+" as its reduction
3173 /// operations. A reduction might be feeding into a store or a binary operation
3174 /// feeding a phi.
3175 ///    ...
3176 ///    \  /
3177 ///     +
3178 ///     |
3179 ///  phi +=
3180 ///
3181 ///  Or:
3182 ///    ...
3183 ///    \  /
3184 ///     +
3185 ///     |
3186 ///   *p =
3187 ///
3188 class HorizontalReduction {
3189   SmallVector<Value *, 16> ReductionOps;
3190   SmallVector<Value *, 32> ReducedVals;
3191
3192   BinaryOperator *ReductionRoot;
3193   PHINode *ReductionPHI;
3194
3195   /// The opcode of the reduction.
3196   unsigned ReductionOpcode;
3197   /// The opcode of the values we perform a reduction on.
3198   unsigned ReducedValueOpcode;
3199   /// The width of one full horizontal reduction operation.
3200   unsigned ReduxWidth;
3201   /// Should we model this reduction as a pairwise reduction tree or a tree that
3202   /// splits the vector in halves and adds those halves.
3203   bool IsPairwiseReduction;
3204
3205 public:
3206   HorizontalReduction()
3207     : ReductionRoot(nullptr), ReductionPHI(nullptr), ReductionOpcode(0),
3208     ReducedValueOpcode(0), ReduxWidth(0), IsPairwiseReduction(false) {}
3209
3210   /// \brief Try to find a reduction tree.
3211   bool matchAssociativeReduction(PHINode *Phi, BinaryOperator *B,
3212                                  const DataLayout *DL) {
3213     assert((!Phi ||
3214             std::find(Phi->op_begin(), Phi->op_end(), B) != Phi->op_end()) &&
3215            "Thi phi needs to use the binary operator");
3216
3217     // We could have a initial reductions that is not an add.
3218     //  r *= v1 + v2 + v3 + v4
3219     // In such a case start looking for a tree rooted in the first '+'.
3220     if (Phi) {
3221       if (B->getOperand(0) == Phi) {
3222         Phi = nullptr;
3223         B = dyn_cast<BinaryOperator>(B->getOperand(1));
3224       } else if (B->getOperand(1) == Phi) {
3225         Phi = nullptr;
3226         B = dyn_cast<BinaryOperator>(B->getOperand(0));
3227       }
3228     }
3229
3230     if (!B)
3231       return false;
3232
3233     Type *Ty = B->getType();
3234     if (Ty->isVectorTy())
3235       return false;
3236
3237     ReductionOpcode = B->getOpcode();
3238     ReducedValueOpcode = 0;
3239     ReduxWidth = MinVecRegSize / DL->getTypeSizeInBits(Ty);
3240     ReductionRoot = B;
3241     ReductionPHI = Phi;
3242
3243     if (ReduxWidth < 4)
3244       return false;
3245
3246     // We currently only support adds.
3247     if (ReductionOpcode != Instruction::Add &&
3248         ReductionOpcode != Instruction::FAdd)
3249       return false;
3250
3251     // Post order traverse the reduction tree starting at B. We only handle true
3252     // trees containing only binary operators.
3253     SmallVector<std::pair<BinaryOperator *, unsigned>, 32> Stack;
3254     Stack.push_back(std::make_pair(B, 0));
3255     while (!Stack.empty()) {
3256       BinaryOperator *TreeN = Stack.back().first;
3257       unsigned EdgeToVist = Stack.back().second++;
3258       bool IsReducedValue = TreeN->getOpcode() != ReductionOpcode;
3259
3260       // Only handle trees in the current basic block.
3261       if (TreeN->getParent() != B->getParent())
3262         return false;
3263
3264       // Each tree node needs to have one user except for the ultimate
3265       // reduction.
3266       if (!TreeN->hasOneUse() && TreeN != B)
3267         return false;
3268
3269       // Postorder vist.
3270       if (EdgeToVist == 2 || IsReducedValue) {
3271         if (IsReducedValue) {
3272           // Make sure that the opcodes of the operations that we are going to
3273           // reduce match.
3274           if (!ReducedValueOpcode)
3275             ReducedValueOpcode = TreeN->getOpcode();
3276           else if (ReducedValueOpcode != TreeN->getOpcode())
3277             return false;
3278           ReducedVals.push_back(TreeN);
3279         } else {
3280           // We need to be able to reassociate the adds.
3281           if (!TreeN->isAssociative())
3282             return false;
3283           ReductionOps.push_back(TreeN);
3284         }
3285         // Retract.
3286         Stack.pop_back();
3287         continue;
3288       }
3289
3290       // Visit left or right.
3291       Value *NextV = TreeN->getOperand(EdgeToVist);
3292       BinaryOperator *Next = dyn_cast<BinaryOperator>(NextV);
3293       if (Next)
3294         Stack.push_back(std::make_pair(Next, 0));
3295       else if (NextV != Phi)
3296         return false;
3297     }
3298     return true;
3299   }
3300
3301   /// \brief Attempt to vectorize the tree found by
3302   /// matchAssociativeReduction.
3303   bool tryToReduce(BoUpSLP &V, TargetTransformInfo *TTI) {
3304     if (ReducedVals.empty())
3305       return false;
3306
3307     unsigned NumReducedVals = ReducedVals.size();
3308     if (NumReducedVals < ReduxWidth)
3309       return false;
3310
3311     Value *VectorizedTree = nullptr;
3312     IRBuilder<> Builder(ReductionRoot);
3313     FastMathFlags Unsafe;
3314     Unsafe.setUnsafeAlgebra();
3315     Builder.SetFastMathFlags(Unsafe);
3316     unsigned i = 0;
3317
3318     for (; i < NumReducedVals - ReduxWidth + 1; i += ReduxWidth) {
3319       ArrayRef<Value *> ValsToReduce(&ReducedVals[i], ReduxWidth);
3320       V.buildTree(ValsToReduce, ReductionOps);
3321
3322       // Estimate cost.
3323       int Cost = V.getTreeCost() + getReductionCost(TTI, ReducedVals[i]);
3324       if (Cost >= -SLPCostThreshold)
3325         break;
3326
3327       DEBUG(dbgs() << "SLP: Vectorizing horizontal reduction at cost:" << Cost
3328                    << ". (HorRdx)\n");
3329
3330       // Vectorize a tree.
3331       DebugLoc Loc = cast<Instruction>(ReducedVals[i])->getDebugLoc();
3332       Value *VectorizedRoot = V.vectorizeTree();
3333
3334       // Emit a reduction.
3335       Value *ReducedSubTree = emitReduction(VectorizedRoot, Builder);
3336       if (VectorizedTree) {
3337         Builder.SetCurrentDebugLocation(Loc);
3338         VectorizedTree = createBinOp(Builder, ReductionOpcode, VectorizedTree,
3339                                      ReducedSubTree, "bin.rdx");
3340       } else
3341         VectorizedTree = ReducedSubTree;
3342     }
3343
3344     if (VectorizedTree) {
3345       // Finish the reduction.
3346       for (; i < NumReducedVals; ++i) {
3347         Builder.SetCurrentDebugLocation(
3348           cast<Instruction>(ReducedVals[i])->getDebugLoc());
3349         VectorizedTree = createBinOp(Builder, ReductionOpcode, VectorizedTree,
3350                                      ReducedVals[i]);
3351       }
3352       // Update users.
3353       if (ReductionPHI) {
3354         assert(ReductionRoot && "Need a reduction operation");
3355         ReductionRoot->setOperand(0, VectorizedTree);
3356         ReductionRoot->setOperand(1, ReductionPHI);
3357       } else
3358         ReductionRoot->replaceAllUsesWith(VectorizedTree);
3359     }
3360     return VectorizedTree != nullptr;
3361   }
3362
3363 private:
3364
3365   /// \brief Calcuate the cost of a reduction.
3366   int getReductionCost(TargetTransformInfo *TTI, Value *FirstReducedVal) {
3367     Type *ScalarTy = FirstReducedVal->getType();
3368     Type *VecTy = VectorType::get(ScalarTy, ReduxWidth);
3369
3370     int PairwiseRdxCost = TTI->getReductionCost(ReductionOpcode, VecTy, true);
3371     int SplittingRdxCost = TTI->getReductionCost(ReductionOpcode, VecTy, false);
3372
3373     IsPairwiseReduction = PairwiseRdxCost < SplittingRdxCost;
3374     int VecReduxCost = IsPairwiseReduction ? PairwiseRdxCost : SplittingRdxCost;
3375
3376     int ScalarReduxCost =
3377         ReduxWidth * TTI->getArithmeticInstrCost(ReductionOpcode, VecTy);
3378
3379     DEBUG(dbgs() << "SLP: Adding cost " << VecReduxCost - ScalarReduxCost
3380                  << " for reduction that starts with " << *FirstReducedVal
3381                  << " (It is a "
3382                  << (IsPairwiseReduction ? "pairwise" : "splitting")
3383                  << " reduction)\n");
3384
3385     return VecReduxCost - ScalarReduxCost;
3386   }
3387
3388   static Value *createBinOp(IRBuilder<> &Builder, unsigned Opcode, Value *L,
3389                             Value *R, const Twine &Name = "") {
3390     if (Opcode == Instruction::FAdd)
3391       return Builder.CreateFAdd(L, R, Name);
3392     return Builder.CreateBinOp((Instruction::BinaryOps)Opcode, L, R, Name);
3393   }
3394
3395   /// \brief Emit a horizontal reduction of the vectorized value.
3396   Value *emitReduction(Value *VectorizedValue, IRBuilder<> &Builder) {
3397     assert(VectorizedValue && "Need to have a vectorized tree node");
3398     Instruction *ValToReduce = dyn_cast<Instruction>(VectorizedValue);
3399     assert(isPowerOf2_32(ReduxWidth) &&
3400            "We only handle power-of-two reductions for now");
3401
3402     Value *TmpVec = ValToReduce;
3403     for (unsigned i = ReduxWidth / 2; i != 0; i >>= 1) {
3404       if (IsPairwiseReduction) {
3405         Value *LeftMask =
3406           createRdxShuffleMask(ReduxWidth, i, true, true, Builder);
3407         Value *RightMask =
3408           createRdxShuffleMask(ReduxWidth, i, true, false, Builder);
3409
3410         Value *LeftShuf = Builder.CreateShuffleVector(
3411           TmpVec, UndefValue::get(TmpVec->getType()), LeftMask, "rdx.shuf.l");
3412         Value *RightShuf = Builder.CreateShuffleVector(
3413           TmpVec, UndefValue::get(TmpVec->getType()), (RightMask),
3414           "rdx.shuf.r");
3415         TmpVec = createBinOp(Builder, ReductionOpcode, LeftShuf, RightShuf,
3416                              "bin.rdx");
3417       } else {
3418         Value *UpperHalf =
3419           createRdxShuffleMask(ReduxWidth, i, false, false, Builder);
3420         Value *Shuf = Builder.CreateShuffleVector(
3421           TmpVec, UndefValue::get(TmpVec->getType()), UpperHalf, "rdx.shuf");
3422         TmpVec = createBinOp(Builder, ReductionOpcode, TmpVec, Shuf, "bin.rdx");
3423       }
3424     }
3425
3426     // The result is in the first element of the vector.
3427     return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
3428   }
3429 };
3430
3431 /// \brief Recognize construction of vectors like
3432 ///  %ra = insertelement <4 x float> undef, float %s0, i32 0
3433 ///  %rb = insertelement <4 x float> %ra, float %s1, i32 1
3434 ///  %rc = insertelement <4 x float> %rb, float %s2, i32 2
3435 ///  %rd = insertelement <4 x float> %rc, float %s3, i32 3
3436 ///
3437 /// Returns true if it matches
3438 ///
3439 static bool findBuildVector(InsertElementInst *FirstInsertElem,
3440                             SmallVectorImpl<Value *> &BuildVector,
3441                             SmallVectorImpl<Value *> &BuildVectorOpds) {
3442   if (!isa<UndefValue>(FirstInsertElem->getOperand(0)))
3443     return false;
3444
3445   InsertElementInst *IE = FirstInsertElem;
3446   while (true) {
3447     BuildVector.push_back(IE);
3448     BuildVectorOpds.push_back(IE->getOperand(1));
3449
3450     if (IE->use_empty())
3451       return false;
3452
3453     InsertElementInst *NextUse = dyn_cast<InsertElementInst>(IE->user_back());
3454     if (!NextUse)
3455       return true;
3456
3457     // If this isn't the final use, make sure the next insertelement is the only
3458     // use. It's OK if the final constructed vector is used multiple times
3459     if (!IE->hasOneUse())
3460       return false;
3461
3462     IE = NextUse;
3463   }
3464
3465   return false;
3466 }
3467
3468 static bool PhiTypeSorterFunc(Value *V, Value *V2) {
3469   return V->getType() < V2->getType();
3470 }
3471
3472 bool SLPVectorizer::vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R) {
3473   bool Changed = false;
3474   SmallVector<Value *, 4> Incoming;
3475   SmallSet<Value *, 16> VisitedInstrs;
3476
3477   bool HaveVectorizedPhiNodes = true;
3478   while (HaveVectorizedPhiNodes) {
3479     HaveVectorizedPhiNodes = false;
3480
3481     // Collect the incoming values from the PHIs.
3482     Incoming.clear();
3483     for (BasicBlock::iterator instr = BB->begin(), ie = BB->end(); instr != ie;
3484          ++instr) {
3485       PHINode *P = dyn_cast<PHINode>(instr);
3486       if (!P)
3487         break;
3488
3489       if (!VisitedInstrs.count(P))
3490         Incoming.push_back(P);
3491     }
3492
3493     // Sort by type.
3494     std::stable_sort(Incoming.begin(), Incoming.end(), PhiTypeSorterFunc);
3495
3496     // Try to vectorize elements base on their type.
3497     for (SmallVector<Value *, 4>::iterator IncIt = Incoming.begin(),
3498                                            E = Incoming.end();
3499          IncIt != E;) {
3500
3501       // Look for the next elements with the same type.
3502       SmallVector<Value *, 4>::iterator SameTypeIt = IncIt;
3503       while (SameTypeIt != E &&
3504              (*SameTypeIt)->getType() == (*IncIt)->getType()) {
3505         VisitedInstrs.insert(*SameTypeIt);
3506         ++SameTypeIt;
3507       }
3508
3509       // Try to vectorize them.
3510       unsigned NumElts = (SameTypeIt - IncIt);
3511       DEBUG(errs() << "SLP: Trying to vectorize starting at PHIs (" << NumElts << ")\n");
3512       if (NumElts > 1 &&
3513           tryToVectorizeList(ArrayRef<Value *>(IncIt, NumElts), R)) {
3514         // Success start over because instructions might have been changed.
3515         HaveVectorizedPhiNodes = true;
3516         Changed = true;
3517         break;
3518       }
3519
3520       // Start over at the next instruction of a different type (or the end).
3521       IncIt = SameTypeIt;
3522     }
3523   }
3524
3525   VisitedInstrs.clear();
3526
3527   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; it++) {
3528     // We may go through BB multiple times so skip the one we have checked.
3529     if (!VisitedInstrs.insert(it))
3530       continue;
3531
3532     if (isa<DbgInfoIntrinsic>(it))
3533       continue;
3534
3535     // Try to vectorize reductions that use PHINodes.
3536     if (PHINode *P = dyn_cast<PHINode>(it)) {
3537       // Check that the PHI is a reduction PHI.
3538       if (P->getNumIncomingValues() != 2)
3539         return Changed;
3540       Value *Rdx =
3541           (P->getIncomingBlock(0) == BB
3542                ? (P->getIncomingValue(0))
3543                : (P->getIncomingBlock(1) == BB ? P->getIncomingValue(1)
3544                                                : nullptr));
3545       // Check if this is a Binary Operator.
3546       BinaryOperator *BI = dyn_cast_or_null<BinaryOperator>(Rdx);
3547       if (!BI)
3548         continue;
3549
3550       // Try to match and vectorize a horizontal reduction.
3551       HorizontalReduction HorRdx;
3552       if (ShouldVectorizeHor &&
3553           HorRdx.matchAssociativeReduction(P, BI, DL) &&
3554           HorRdx.tryToReduce(R, TTI)) {
3555         Changed = true;
3556         it = BB->begin();
3557         e = BB->end();
3558         continue;
3559       }
3560
3561      Value *Inst = BI->getOperand(0);
3562       if (Inst == P)
3563         Inst = BI->getOperand(1);
3564
3565       if (tryToVectorize(dyn_cast<BinaryOperator>(Inst), R)) {
3566         // We would like to start over since some instructions are deleted
3567         // and the iterator may become invalid value.
3568         Changed = true;
3569         it = BB->begin();
3570         e = BB->end();
3571         continue;
3572       }
3573
3574       continue;
3575     }
3576
3577     // Try to vectorize horizontal reductions feeding into a store.
3578     if (ShouldStartVectorizeHorAtStore)
3579       if (StoreInst *SI = dyn_cast<StoreInst>(it))
3580         if (BinaryOperator *BinOp =
3581                 dyn_cast<BinaryOperator>(SI->getValueOperand())) {
3582           HorizontalReduction HorRdx;
3583           if (((HorRdx.matchAssociativeReduction(nullptr, BinOp, DL) &&
3584                 HorRdx.tryToReduce(R, TTI)) ||
3585                tryToVectorize(BinOp, R))) {
3586             Changed = true;
3587             it = BB->begin();
3588             e = BB->end();
3589             continue;
3590           }
3591         }
3592
3593     // Try to vectorize trees that start at compare instructions.
3594     if (CmpInst *CI = dyn_cast<CmpInst>(it)) {
3595       if (tryToVectorizePair(CI->getOperand(0), CI->getOperand(1), R)) {
3596         Changed = true;
3597         // We would like to start over since some instructions are deleted
3598         // and the iterator may become invalid value.
3599         it = BB->begin();
3600         e = BB->end();
3601         continue;
3602       }
3603
3604       for (int i = 0; i < 2; ++i) {
3605         if (BinaryOperator *BI = dyn_cast<BinaryOperator>(CI->getOperand(i))) {
3606           if (tryToVectorizePair(BI->getOperand(0), BI->getOperand(1), R)) {
3607             Changed = true;
3608             // We would like to start over since some instructions are deleted
3609             // and the iterator may become invalid value.
3610             it = BB->begin();
3611             e = BB->end();
3612           }
3613         }
3614       }
3615       continue;
3616     }
3617
3618     // Try to vectorize trees that start at insertelement instructions.
3619     if (InsertElementInst *FirstInsertElem = dyn_cast<InsertElementInst>(it)) {
3620       SmallVector<Value *, 16> BuildVector;
3621       SmallVector<Value *, 16> BuildVectorOpds;
3622       if (!findBuildVector(FirstInsertElem, BuildVector, BuildVectorOpds))
3623         continue;
3624
3625       // Vectorize starting with the build vector operands ignoring the
3626       // BuildVector instructions for the purpose of scheduling and user
3627       // extraction.
3628       if (tryToVectorizeList(BuildVectorOpds, R, BuildVector)) {
3629         Changed = true;
3630         it = BB->begin();
3631         e = BB->end();
3632       }
3633
3634       continue;
3635     }
3636   }
3637
3638   return Changed;
3639 }
3640
3641 bool SLPVectorizer::vectorizeStoreChains(BoUpSLP &R) {
3642   bool Changed = false;
3643   // Attempt to sort and vectorize each of the store-groups.
3644   for (StoreListMap::iterator it = StoreRefs.begin(), e = StoreRefs.end();
3645        it != e; ++it) {
3646     if (it->second.size() < 2)
3647       continue;
3648
3649     DEBUG(dbgs() << "SLP: Analyzing a store chain of length "
3650           << it->second.size() << ".\n");
3651
3652     // Process the stores in chunks of 16.
3653     for (unsigned CI = 0, CE = it->second.size(); CI < CE; CI+=16) {
3654       unsigned Len = std::min<unsigned>(CE - CI, 16);
3655       ArrayRef<StoreInst *> Chunk(&it->second[CI], Len);
3656       Changed |= vectorizeStores(Chunk, -SLPCostThreshold, R);
3657     }
3658   }
3659   return Changed;
3660 }
3661
3662 } // end anonymous namespace
3663
3664 char SLPVectorizer::ID = 0;
3665 static const char lv_name[] = "SLP Vectorizer";
3666 INITIALIZE_PASS_BEGIN(SLPVectorizer, SV_NAME, lv_name, false, false)
3667 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
3668 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
3669 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
3670 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
3671 INITIALIZE_PASS_END(SLPVectorizer, SV_NAME, lv_name, false, false)
3672
3673 namespace llvm {
3674 Pass *createSLPVectorizerPass() { return new SLPVectorizer(); }
3675 }