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