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/Analysis/AliasAnalysis.h"
  23 #include "llvm/Analysis/LoopInfo.h"
  24 #include "llvm/Analysis/ScalarEvolution.h"
  25 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  26 #include "llvm/Analysis/TargetTransformInfo.h"
  27 #include "llvm/Analysis/ValueTracking.h"
  28 #include "llvm/IR/DataLayout.h"
  29 #include "llvm/IR/Dominators.h"
  30 #include "llvm/IR/IRBuilder.h"
  31 #include "llvm/IR/Instructions.h"
  32 #include "llvm/IR/IntrinsicInst.h"
  33 #include "llvm/IR/Module.h"
  34 #include "llvm/IR/Type.h"
  35 #include "llvm/IR/Value.h"
  36 #include "llvm/IR/Verifier.h"
  37 #include "llvm/Pass.h"
  38 #include "llvm/Support/CommandLine.h"
  39 #include "llvm/Support/Debug.h"
  40 #include "llvm/Support/raw_ostream.h"
  41 #include "llvm/Transforms/Utils/VectorUtils.h"
  42 #include <algorithm>
  43 #include <map>
  44
  45 using namespace llvm;
  46
  47 #define SV_NAME "slp-vectorizer"
  48 #define DEBUG_TYPE "SLP"
  49
  50 static cl::opt<int>
  51     SLPCostThreshold("slp-threshold", cl::init(0), cl::Hidden,
  52                      cl::desc("Only vectorize if you gain more than this "
  53                               "number "));
  54
  55 static cl::opt<bool>
  56 ShouldVectorizeHor("slp-vectorize-hor", cl::init(false), cl::Hidden,
  57                    cl::desc("Attempt to vectorize horizontal reductions"));
  58
  59 static cl::opt<bool> ShouldStartVectorizeHorAtStore(
  60     "slp-vectorize-hor-store", cl::init(false), cl::Hidden,
  61     cl::desc(
  62         "Attempt to vectorize horizontal reductions feeding into a store"));
  63
  64 namespace {
  65
  66 static const unsigned MinVecRegSize = 128;
  67
  68 static const unsigned RecursionMaxDepth = 12;
  69
  70 /// A helper class for numbering instructions in multiple blocks.
  71 /// Numbers start at zero for each basic block.
  72 struct BlockNumbering {
  73
  74   BlockNumbering(BasicBlock *Bb) : BB(Bb), Valid(false) {}
  75
  76   BlockNumbering() : BB(nullptr), Valid(false) {}
  77
  78   void numberInstructions() {
  79     unsigned Loc = 0;
  80     InstrIdx.clear();
  81     InstrVec.clear();
  82     // Number the instructions in the block.
  83     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
  84       InstrIdx[it] = Loc++;
  85       InstrVec.push_back(it);
  86       assert(InstrVec[InstrIdx[it]] == it && "Invalid allocation");
  87     }
  88     Valid = true;
  89   }
  90
  91   int getIndex(Instruction *I) {
  92     assert(I->getParent() == BB && "Invalid instruction");
  93     if (!Valid)
  94       numberInstructions();
  95     assert(InstrIdx.count(I) && "Unknown instruction");
  96     return InstrIdx[I];
  97   }
  98
  99   Instruction *getInstruction(unsigned loc) {
 100     if (!Valid)
 101       numberInstructions();
 102     assert(InstrVec.size() > loc && "Invalid Index");
 103     return InstrVec[loc];
 104   }
 105
 106   void forget() { Valid = false; }
 107
 108 private:
 109   /// The block we are numbering.
 110   BasicBlock *BB;
 111   /// Is the block numbered.
 112   bool Valid;
 113   /// Maps instructions to numbers and back.
 114   SmallDenseMap<Instruction *, int> InstrIdx;
 115   /// Maps integers to Instructions.
 116   SmallVector<Instruction *, 32> InstrVec;
 117 };
 118
 119 /// \returns the parent basic block if all of the instructions in \p VL
 120 /// are in the same block or null otherwise.
 121 static BasicBlock *getSameBlock(ArrayRef<Value *> VL) {
 122   Instruction *I0 = dyn_cast<Instruction>(VL[0]);
 123   if (!I0)
 124     return nullptr;
 125   BasicBlock *BB = I0->getParent();
 126   for (int i = 1, e = VL.size(); i < e; i++) {
 127     Instruction *I = dyn_cast<Instruction>(VL[i]);
 128     if (!I)
 129       return nullptr;
 130
 131     if (BB != I->getParent())
 132       return nullptr;
 133   }
 134   return BB;
 135 }
 136
 137 /// \returns True if all of the values in \p VL are constants.
 138 static bool allConstant(ArrayRef<Value *> VL) {
 139   for (unsigned i = 0, e = VL.size(); i < e; ++i)
 140     if (!isa<Constant>(VL[i]))
 141       return false;
 142   return true;
 143 }
 144
 145 /// \returns True if all of the values in \p VL are identical.
 146 static bool isSplat(ArrayRef<Value *> VL) {
 147   for (unsigned i = 1, e = VL.size(); i < e; ++i)
 148     if (VL[i] != VL[0])
 149       return false;
 150   return true;
 151 }
 152
 153 /// \returns The opcode if all of the Instructions in \p VL have the same
 154 /// opcode, or zero.
 155 static unsigned getSameOpcode(ArrayRef<Value *> VL) {
 156   Instruction *I0 = dyn_cast<Instruction>(VL[0]);
 157   if (!I0)
 158     return 0;
 159   unsigned Opcode = I0->getOpcode();
 160   for (int i = 1, e = VL.size(); i < e; i++) {
 161     Instruction *I = dyn_cast<Instruction>(VL[i]);
 162     if (!I || Opcode != I->getOpcode())
 163       return 0;
 164   }
 165   return Opcode;
 166 }
 167
 168 /// \returns \p I after propagating metadata from \p VL.
 169 static Instruction *propagateMetadata(Instruction *I, ArrayRef<Value *> VL) {
 170   Instruction *I0 = cast<Instruction>(VL[0]);
 171   SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
 172   I0->getAllMetadataOtherThanDebugLoc(Metadata);
 173
 174   for (unsigned i = 0, n = Metadata.size(); i != n; ++i) {
 175     unsigned Kind = Metadata[i].first;
 176     MDNode *MD = Metadata[i].second;
 177
 178     for (int i = 1, e = VL.size(); MD && i != e; i++) {
 179       Instruction *I = cast<Instruction>(VL[i]);
 180       MDNode *IMD = I->getMetadata(Kind);
 181
 182       switch (Kind) {
 183       default:
 184         MD = nullptr; // Remove unknown metadata
 185         break;
 186       case LLVMContext::MD_tbaa:
 187         MD = MDNode::getMostGenericTBAA(MD, IMD);
 188         break;
 189       case LLVMContext::MD_fpmath:
 190         MD = MDNode::getMostGenericFPMath(MD, IMD);
 191         break;
 192       }
 193     }
 194     I->setMetadata(Kind, MD);
 195   }
 196   return I;
 197 }
 198
 199 /// \returns The type that all of the values in \p VL have or null if there
 200 /// are different types.
 201 static Type* getSameType(ArrayRef<Value *> VL) {
 202   Type *Ty = VL[0]->getType();
 203   for (int i = 1, e = VL.size(); i < e; i++)
 204     if (VL[i]->getType() != Ty)
 205       return nullptr;
 206
 207   return Ty;
 208 }
 209
 210 /// \returns True if the ExtractElement instructions in VL can be vectorized
 211 /// to use the original vector.
 212 static bool CanReuseExtract(ArrayRef<Value *> VL) {
 213   assert(Instruction::ExtractElement == getSameOpcode(VL) && "Invalid opcode");
 214   // Check if all of the extracts come from the same vector and from the
 215   // correct offset.
 216   Value *VL0 = VL[0];
 217   ExtractElementInst *E0 = cast<ExtractElementInst>(VL0);
 218   Value *Vec = E0->getOperand(0);
 219
 220   // We have to extract from the same vector type.
 221   unsigned NElts = Vec->getType()->getVectorNumElements();
 222
 223   if (NElts != VL.size())
 224     return false;
 225
 226   // Check that all of the indices extract from the correct offset.
 227   ConstantInt *CI = dyn_cast<ConstantInt>(E0->getOperand(1));
 228   if (!CI || CI->getZExtValue())
 229     return false;
 230
 231   for (unsigned i = 1, e = VL.size(); i < e; ++i) {
 232     ExtractElementInst *E = cast<ExtractElementInst>(VL[i]);
 233     ConstantInt *CI = dyn_cast<ConstantInt>(E->getOperand(1));
 234
 235     if (!CI || CI->getZExtValue() != i || E->getOperand(0) != Vec)
 236       return false;
 237   }
 238
 239   return true;
 240 }
 241
 242 static void reorderInputsAccordingToOpcode(ArrayRef<Value *> VL,
 243                                            SmallVectorImpl<Value *> &Left,
 244                                            SmallVectorImpl<Value *> &Right) {
 245
 246   SmallVector<Value *, 16> OrigLeft, OrigRight;
 247
 248   bool AllSameOpcodeLeft = true;
 249   bool AllSameOpcodeRight = true;
 250   for (unsigned i = 0, e = VL.size(); i != e; ++i) {
 251     Instruction *I = cast<Instruction>(VL[i]);
 252     Value *V0 = I->getOperand(0);
 253     Value *V1 = I->getOperand(1);
 254
 255     OrigLeft.push_back(V0);
 256     OrigRight.push_back(V1);
 257
 258     Instruction *I0 = dyn_cast<Instruction>(V0);
 259     Instruction *I1 = dyn_cast<Instruction>(V1);
 260
 261     // Check whether all operands on one side have the same opcode. In this case
 262     // we want to preserve the original order and not make things worse by
 263     // reordering.
 264     AllSameOpcodeLeft = I0;
 265     AllSameOpcodeRight = I1;
 266
 267     if (i && AllSameOpcodeLeft) {
 268       if(Instruction *P0 = dyn_cast<Instruction>(OrigLeft[i-1])) {
 269         if(P0->getOpcode() != I0->getOpcode())
 270           AllSameOpcodeLeft = false;
 271       } else
 272         AllSameOpcodeLeft = false;
 273     }
 274     if (i && AllSameOpcodeRight) {
 275       if(Instruction *P1 = dyn_cast<Instruction>(OrigRight[i-1])) {
 276         if(P1->getOpcode() != I1->getOpcode())
 277           AllSameOpcodeRight = false;
 278       } else
 279         AllSameOpcodeRight = false;
 280     }
 281
 282     // Sort two opcodes. In the code below we try to preserve the ability to use
 283     // broadcast of values instead of individual inserts.
 284     // vl1 = load
 285     // vl2 = phi
 286     // vr1 = load
 287     // vr2 = vr2
 288     //    = vl1 x vr1
 289     //    = vl2 x vr2
 290     // If we just sorted according to opcode we would leave the first line in
 291     // tact but we would swap vl2 with vr2 because opcode(phi) > opcode(load).
 292     //    = vl1 x vr1
 293     //    = vr2 x vl2
 294     // Because vr2 and vr1 are from the same load we loose the opportunity of a
 295     // broadcast for the packed right side in the backend: we have [vr1, vl2]
 296     // instead of [vr1, vr2=vr1].
 297     if (I0 && I1) {
 298        if(!i && I0->getOpcode() > I1->getOpcode()) {
 299          Left.push_back(I1);
 300          Right.push_back(I0);
 301        } else if (i && I0->getOpcode() > I1->getOpcode() && Right[i-1] != I1) {
 302          // Try not to destroy a broad cast for no apparent benefit.
 303          Left.push_back(I1);
 304          Right.push_back(I0);
 305        } else if (i && I0->getOpcode() == I1->getOpcode() && Right[i-1] ==  I0) {
 306          // Try preserve broadcasts.
 307          Left.push_back(I1);
 308          Right.push_back(I0);
 309        } else if (i && I0->getOpcode() == I1->getOpcode() && Left[i-1] == I1) {
 310          // Try preserve broadcasts.
 311          Left.push_back(I1);
 312          Right.push_back(I0);
 313        } else {
 314          Left.push_back(I0);
 315          Right.push_back(I1);
 316        }
 317        continue;
 318     }
 319     // One opcode, put the instruction on the right.
 320     if (I0) {
 321       Left.push_back(V1);
 322       Right.push_back(I0);
 323       continue;
 324     }
 325     Left.push_back(V0);
 326     Right.push_back(V1);
 327   }
 328
 329   bool LeftBroadcast = isSplat(Left);
 330   bool RightBroadcast = isSplat(Right);
 331
 332   // Don't reorder if the operands where good to begin with.
 333   if (!(LeftBroadcast || RightBroadcast) &&
 334       (AllSameOpcodeRight || AllSameOpcodeLeft)) {
 335     Left = OrigLeft;
 336     Right = OrigRight;
 337   }
 338 }
 339
 340 /// Bottom Up SLP Vectorizer.
 341 class BoUpSLP {
 342 public:
 343   typedef SmallVector<Value *, 8> ValueList;
 344   typedef SmallVector<Instruction *, 16> InstrList;
 345   typedef SmallPtrSet<Value *, 16> ValueSet;
 346   typedef SmallVector<StoreInst *, 8> StoreList;
 347
 348   BoUpSLP(Function *Func, ScalarEvolution *Se, const DataLayout *Dl,
 349           TargetTransformInfo *Tti, TargetLibraryInfo *TLi, AliasAnalysis *Aa, LoopInfo *Li,
 350           DominatorTree *Dt) :
 351       F(Func), SE(Se), DL(Dl), TTI(Tti), TLI(TLi), AA(Aa), LI(Li), DT(Dt),
 352     Builder(Se->getContext()) {
 353       // Setup the block numbering utility for all of the blocks in the
 354       // function.
 355       for (Function::iterator it = F->begin(), e = F->end(); it != e; ++it) {
 356         BasicBlock *BB = it;
 357         BlocksNumbers[BB] = BlockNumbering(BB);
 358       }
 359     }
 360
 361   /// \brief Vectorize the tree that starts with the elements in \p VL.
 362   /// Returns the vectorized root.
 363   Value *vectorizeTree();
 364
 365   /// \returns the vectorization cost of the subtree that starts at \p VL.
 366   /// A negative number means that this is profitable.
 367   int getTreeCost();
 368
 369   /// Construct a vectorizable tree that starts at \p Roots and is possibly
 370   /// used by a reduction of \p RdxOps.
 371   void buildTree(ArrayRef<Value *> Roots, ValueSet *RdxOps = 0);
 372
 373   /// Clear the internal data structures that are created by 'buildTree'.
 374   void deleteTree() {
 375     RdxOps = 0;
 376     VectorizableTree.clear();
 377     ScalarToTreeEntry.clear();
 378     MustGather.clear();
 379     ExternalUses.clear();
 380     MemBarrierIgnoreList.clear();
 381   }
 382
 383   /// \returns true if the memory operations A and B are consecutive.
 384   bool isConsecutiveAccess(Value *A, Value *B);
 385
 386   /// \brief Perform LICM and CSE on the newly generated gather sequences.
 387   void optimizeGatherSequence();
 388 private:
 389   struct TreeEntry;
 390
 391   /// \returns the cost of the vectorizable entry.
 392   int getEntryCost(TreeEntry *E);
 393
 394   /// This is the recursive part of buildTree.
 395   void buildTree_rec(ArrayRef<Value *> Roots, unsigned Depth);
 396
 397   /// Vectorize a single entry in the tree.
 398   Value *vectorizeTree(TreeEntry *E);
 399
 400   /// Vectorize a single entry in the tree, starting in \p VL.
 401   Value *vectorizeTree(ArrayRef<Value *> VL);
 402
 403   /// \returns the pointer to the vectorized value if \p VL is already
 404   /// vectorized, or NULL. They may happen in cycles.
 405   Value *alreadyVectorized(ArrayRef<Value *> VL) const;
 406
 407   /// \brief Take the pointer operand from the Load/Store instruction.
 408   /// \returns NULL if this is not a valid Load/Store instruction.
 409   static Value *getPointerOperand(Value *I);
 410
 411   /// \brief Take the address space operand from the Load/Store instruction.
 412   /// \returns -1 if this is not a valid Load/Store instruction.
 413   static unsigned getAddressSpaceOperand(Value *I);
 414
 415   /// \returns the scalarization cost for this type. Scalarization in this
 416   /// context means the creation of vectors from a group of scalars.
 417   int getGatherCost(Type *Ty);
 418
 419   /// \returns the scalarization cost for this list of values. Assuming that
 420   /// this subtree gets vectorized, we may need to extract the values from the
 421   /// roots. This method calculates the cost of extracting the values.
 422   int getGatherCost(ArrayRef<Value *> VL);
 423
 424   /// \returns the AA location that is being access by the instruction.
 425   AliasAnalysis::Location getLocation(Instruction *I);
 426
 427   /// \brief Checks if it is possible to sink an instruction from
 428   /// \p Src to \p Dst.
 429   /// \returns the pointer to the barrier instruction if we can't sink.
 430   Value *getSinkBarrier(Instruction *Src, Instruction *Dst);
 431
 432   /// \returns the index of the last instruction in the BB from \p VL.
 433   int getLastIndex(ArrayRef<Value *> VL);
 434
 435   /// \returns the Instruction in the bundle \p VL.
 436   Instruction *getLastInstruction(ArrayRef<Value *> VL);
 437
 438   /// \brief Set the Builder insert point to one after the last instruction in
 439   /// the bundle
 440   void setInsertPointAfterBundle(ArrayRef<Value *> VL);
 441
 442   /// \returns a vector from a collection of scalars in \p VL.
 443   Value *Gather(ArrayRef<Value *> VL, VectorType *Ty);
 444
 445   /// \returns whether the VectorizableTree is fully vectoriable and will
 446   /// be beneficial even the tree height is tiny.
 447   bool isFullyVectorizableTinyTree();
 448
 449   struct TreeEntry {
 450     TreeEntry() : Scalars(), VectorizedValue(nullptr), LastScalarIndex(0),
 451     NeedToGather(0) {}
 452
 453     /// \returns true if the scalars in VL are equal to this entry.
 454     bool isSame(ArrayRef<Value *> VL) const {
 455       assert(VL.size() == Scalars.size() && "Invalid size");
 456       return std::equal(VL.begin(), VL.end(), Scalars.begin());
 457     }
 458
 459     /// A vector of scalars.
 460     ValueList Scalars;
 461
 462     /// The Scalars are vectorized into this value. It is initialized to Null.
 463     Value *VectorizedValue;
 464
 465     /// The index in the basic block of the last scalar.
 466     int LastScalarIndex;
 467
 468     /// Do we need to gather this sequence ?
 469     bool NeedToGather;
 470   };
 471
 472   /// Create a new VectorizableTree entry.
 473   TreeEntry *newTreeEntry(ArrayRef<Value *> VL, bool Vectorized) {
 474     VectorizableTree.push_back(TreeEntry());
 475     int idx = VectorizableTree.size() - 1;
 476     TreeEntry *Last = &VectorizableTree[idx];
 477     Last->Scalars.insert(Last->Scalars.begin(), VL.begin(), VL.end());
 478     Last->NeedToGather = !Vectorized;
 479     if (Vectorized) {
 480       Last->LastScalarIndex = getLastIndex(VL);
 481       for (int i = 0, e = VL.size(); i != e; ++i) {
 482         assert(!ScalarToTreeEntry.count(VL[i]) && "Scalar already in tree!");
 483         ScalarToTreeEntry[VL[i]] = idx;
 484       }
 485     } else {
 486       Last->LastScalarIndex = 0;
 487       MustGather.insert(VL.begin(), VL.end());
 488     }
 489     return Last;
 490   }
 491
 492   /// -- Vectorization State --
 493   /// Holds all of the tree entries.
 494   std::vector<TreeEntry> VectorizableTree;
 495
 496   /// Maps a specific scalar to its tree entry.
 497   SmallDenseMap<Value*, int> ScalarToTreeEntry;
 498
 499   /// A list of scalars that we found that we need to keep as scalars.
 500   ValueSet MustGather;
 501
 502   /// This POD struct describes one external user in the vectorized tree.
 503   struct ExternalUser {
 504     ExternalUser (Value *S, llvm::User *U, int L) :
 505       Scalar(S), User(U), Lane(L){};
 506     // Which scalar in our function.
 507     Value *Scalar;
 508     // Which user that uses the scalar.
 509     llvm::User *User;
 510     // Which lane does the scalar belong to.
 511     int Lane;
 512   };
 513   typedef SmallVector<ExternalUser, 16> UserList;
 514
 515   /// A list of values that need to extracted out of the tree.
 516   /// This list holds pairs of (Internal Scalar : External User).
 517   UserList ExternalUses;
 518
 519   /// A list of instructions to ignore while sinking
 520   /// memory instructions. This map must be reset between runs of getCost.
 521   ValueSet MemBarrierIgnoreList;
 522
 523   /// Holds all of the instructions that we gathered.
 524   SetVector<Instruction *> GatherSeq;
 525   /// A list of blocks that we are going to CSE.
 526   SetVector<BasicBlock *> CSEBlocks;
 527
 528   /// Numbers instructions in different blocks.
 529   DenseMap<BasicBlock *, BlockNumbering> BlocksNumbers;
 530
 531   /// Reduction operators.
 532   ValueSet *RdxOps;
 533
 534   // Analysis and block reference.
 535   Function *F;
 536   ScalarEvolution *SE;
 537   const DataLayout *DL;
 538   TargetTransformInfo *TTI;
 539   TargetLibraryInfo *TLI;
 540   AliasAnalysis *AA;
 541   LoopInfo *LI;
 542   DominatorTree *DT;
 543   /// Instruction builder to construct the vectorized tree.
 544   IRBuilder<> Builder;
 545 };
 546
 547 void BoUpSLP::buildTree(ArrayRef<Value *> Roots, ValueSet *Rdx) {
 548   deleteTree();
 549   RdxOps = Rdx;
 550   if (!getSameType(Roots))
 551     return;
 552   buildTree_rec(Roots, 0);
 553
 554   // Collect the values that we need to extract from the tree.
 555   for (int EIdx = 0, EE = VectorizableTree.size(); EIdx < EE; ++EIdx) {
 556     TreeEntry *Entry = &VectorizableTree[EIdx];
 557
 558     // For each lane:
 559     for (int Lane = 0, LE = Entry->Scalars.size(); Lane != LE; ++Lane) {
 560       Value *Scalar = Entry->Scalars[Lane];
 561
 562       // No need to handle users of gathered values.
 563       if (Entry->NeedToGather)
 564         continue;
 565
 566       for (User *U : Scalar->users()) {
 567         DEBUG(dbgs() << "SLP: Checking user:" << *U << ".\n");
 568
 569         // Skip in-tree scalars that become vectors.
 570         if (ScalarToTreeEntry.count(U)) {
 571           DEBUG(dbgs() << "SLP: \tInternal user will be removed:" <<
 572                 *U << ".\n");
 573           int Idx = ScalarToTreeEntry[U]; (void) Idx;
 574           assert(!VectorizableTree[Idx].NeedToGather && "Bad state");
 575           continue;
 576         }
 577         Instruction *UserInst = dyn_cast<Instruction>(U);
 578         if (!UserInst)
 579           continue;
 580
 581         // Ignore uses that are part of the reduction.
 582         if (Rdx && std::find(Rdx->begin(), Rdx->end(), UserInst) != Rdx->end())
 583           continue;
 584
 585         DEBUG(dbgs() << "SLP: Need to extract:" << *U << " from lane " <<
 586               Lane << " from " << *Scalar << ".\n");
 587         ExternalUses.push_back(ExternalUser(Scalar, U, Lane));
 588       }
 589     }
 590   }
 591 }
 592
 593
 594 void BoUpSLP::buildTree_rec(ArrayRef<Value *> VL, unsigned Depth) {
 595   bool SameTy = getSameType(VL); (void)SameTy;
 596   assert(SameTy && "Invalid types!");
 597
 598   if (Depth == RecursionMaxDepth) {
 599     DEBUG(dbgs() << "SLP: Gathering due to max recursion depth.\n");
 600     newTreeEntry(VL, false);
 601     return;
 602   }
 603
 604   // Don't handle vectors.
 605   if (VL[0]->getType()->isVectorTy()) {
 606     DEBUG(dbgs() << "SLP: Gathering due to vector type.\n");
 607     newTreeEntry(VL, false);
 608     return;
 609   }
 610
 611   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
 612     if (SI->getValueOperand()->getType()->isVectorTy()) {
 613       DEBUG(dbgs() << "SLP: Gathering due to store vector type.\n");
 614       newTreeEntry(VL, false);
 615       return;
 616     }
 617
 618   // If all of the operands are identical or constant we have a simple solution.
 619   if (allConstant(VL) || isSplat(VL) || !getSameBlock(VL) ||
 620       !getSameOpcode(VL)) {
 621     DEBUG(dbgs() << "SLP: Gathering due to C,S,B,O. \n");
 622     newTreeEntry(VL, false);
 623     return;
 624   }
 625
 626   // We now know that this is a vector of instructions of the same type from
 627   // the same block.
 628
 629   // Check if this is a duplicate of another entry.
 630   if (ScalarToTreeEntry.count(VL[0])) {
 631     int Idx = ScalarToTreeEntry[VL[0]];
 632     TreeEntry *E = &VectorizableTree[Idx];
 633     for (unsigned i = 0, e = VL.size(); i != e; ++i) {
 634       DEBUG(dbgs() << "SLP: \tChecking bundle: " << *VL[i] << ".\n");
 635       if (E->Scalars[i] != VL[i]) {
 636         DEBUG(dbgs() << "SLP: Gathering due to partial overlap.\n");
 637         newTreeEntry(VL, false);
 638         return;
 639       }
 640     }
 641     DEBUG(dbgs() << "SLP: Perfect diamond merge at " << *VL[0] << ".\n");
 642     return;
 643   }
 644
 645   // Check that none of the instructions in the bundle are already in the tree.
 646   for (unsigned i = 0, e = VL.size(); i != e; ++i) {
 647     if (ScalarToTreeEntry.count(VL[i])) {
 648       DEBUG(dbgs() << "SLP: The instruction (" << *VL[i] <<
 649             ") is already in tree.\n");
 650       newTreeEntry(VL, false);
 651       return;
 652     }
 653   }
 654
 655   // If any of the scalars appears in the table OR it is marked as a value that
 656   // needs to stat scalar then we need to gather the scalars.
 657   for (unsigned i = 0, e = VL.size(); i != e; ++i) {
 658     if (ScalarToTreeEntry.count(VL[i]) || MustGather.count(VL[i])) {
 659       DEBUG(dbgs() << "SLP: Gathering due to gathered scalar. \n");
 660       newTreeEntry(VL, false);
 661       return;
 662     }
 663   }
 664
 665   // Check that all of the users of the scalars that we want to vectorize are
 666   // schedulable.
 667   Instruction *VL0 = cast<Instruction>(VL[0]);
 668   int MyLastIndex = getLastIndex(VL);
 669   BasicBlock *BB = cast<Instruction>(VL0)->getParent();
 670
 671   for (unsigned i = 0, e = VL.size(); i != e; ++i) {
 672     Instruction *Scalar = cast<Instruction>(VL[i]);
 673     DEBUG(dbgs() << "SLP: Checking users of  " << *Scalar << ". \n");
 674     for (User *U : Scalar->users()) {
 675       DEBUG(dbgs() << "SLP: \tUser " << *U << ". \n");
 676       Instruction *UI = dyn_cast<Instruction>(U);
 677       if (!UI) {
 678         DEBUG(dbgs() << "SLP: Gathering due unknown user. \n");
 679         newTreeEntry(VL, false);
 680         return;
 681       }
 682
 683       // We don't care if the user is in a different basic block.
 684       BasicBlock *UserBlock = UI->getParent();
 685       if (UserBlock != BB) {
 686         DEBUG(dbgs() << "SLP: User from a different basic block "
 687               << *UI << ". \n");
 688         continue;
 689       }
 690
 691       // If this is a PHINode within this basic block then we can place the
 692       // extract wherever we want.
 693       if (isa<PHINode>(*UI)) {
 694         DEBUG(dbgs() << "SLP: \tWe can schedule PHIs:" << *UI << ". \n");
 695         continue;
 696       }
 697
 698       // Check if this is a safe in-tree user.
 699       if (ScalarToTreeEntry.count(UI)) {
 700         int Idx = ScalarToTreeEntry[UI];
 701         int VecLocation = VectorizableTree[Idx].LastScalarIndex;
 702         if (VecLocation <= MyLastIndex) {
 703           DEBUG(dbgs() << "SLP: Gathering due to unschedulable vector. \n");
 704           newTreeEntry(VL, false);
 705           return;
 706         }
 707         DEBUG(dbgs() << "SLP: In-tree user (" << *UI << ") at #" <<
 708               VecLocation << " vector value (" << *Scalar << ") at #"
 709               << MyLastIndex << ".\n");
 710         continue;
 711       }
 712
 713       // This user is part of the reduction.
 714       if (RdxOps && RdxOps->count(UI))
 715         continue;
 716
 717       // Make sure that we can schedule this unknown user.
 718       BlockNumbering &BN = BlocksNumbers[BB];
 719       int UserIndex = BN.getIndex(UI);
 720       if (UserIndex < MyLastIndex) {
 721
 722         DEBUG(dbgs() << "SLP: Can't schedule extractelement for "
 723               << *UI << ". \n");
 724         newTreeEntry(VL, false);
 725         return;
 726       }
 727     }
 728   }
 729
 730   // Check that every instructions appears once in this bundle.
 731   for (unsigned i = 0, e = VL.size(); i < e; ++i)
 732     for (unsigned j = i+1; j < e; ++j)
 733       if (VL[i] == VL[j]) {
 734         DEBUG(dbgs() << "SLP: Scalar used twice in bundle.\n");
 735         newTreeEntry(VL, false);
 736         return;
 737       }
 738
 739   // Check that instructions in this bundle don't reference other instructions.
 740   // The runtime of this check is O(N * N-1 * uses(N)) and a typical N is 4.
 741   for (unsigned i = 0, e = VL.size(); i < e; ++i) {
 742     for (User *U : VL[i]->users()) {
 743       for (unsigned j = 0; j < e; ++j) {
 744         if (i != j && U == VL[j]) {
 745           DEBUG(dbgs() << "SLP: Intra-bundle dependencies!" << *U << ". \n");
 746           newTreeEntry(VL, false);
 747           return;
 748         }
 749       }
 750     }
 751   }
 752
 753   DEBUG(dbgs() << "SLP: We are able to schedule this bundle.\n");
 754
 755   unsigned Opcode = getSameOpcode(VL);
 756
 757   // Check if it is safe to sink the loads or the stores.
 758   if (Opcode == Instruction::Load || Opcode == Instruction::Store) {
 759     Instruction *Last = getLastInstruction(VL);
 760
 761     for (unsigned i = 0, e = VL.size(); i < e; ++i) {
 762       if (VL[i] == Last)
 763         continue;
 764       Value *Barrier = getSinkBarrier(cast<Instruction>(VL[i]), Last);
 765       if (Barrier) {
 766         DEBUG(dbgs() << "SLP: Can't sink " << *VL[i] << "\n down to " << *Last
 767               << "\n because of " << *Barrier << ".  Gathering.\n");
 768         newTreeEntry(VL, false);
 769         return;
 770       }
 771     }
 772   }
 773
 774   switch (Opcode) {
 775     case Instruction::PHI: {
 776       PHINode *PH = dyn_cast<PHINode>(VL0);
 777
 778       // Check for terminator values (e.g. invoke).
 779       for (unsigned j = 0; j < VL.size(); ++j)
 780         for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
 781           TerminatorInst *Term = dyn_cast<TerminatorInst>(
 782               cast<PHINode>(VL[j])->getIncomingValueForBlock(PH->getIncomingBlock(i)));
 783           if (Term) {
 784             DEBUG(dbgs() << "SLP: Need to swizzle PHINodes (TerminatorInst use).\n");
 785             newTreeEntry(VL, false);
 786             return;
 787           }
 788         }
 789
 790       newTreeEntry(VL, true);
 791       DEBUG(dbgs() << "SLP: added a vector of PHINodes.\n");
 792
 793       for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
 794         ValueList Operands;
 795         // Prepare the operand vector.
 796         for (unsigned j = 0; j < VL.size(); ++j)
 797           Operands.push_back(cast<PHINode>(VL[j])->getIncomingValueForBlock(
 798               PH->getIncomingBlock(i)));
 799
 800         buildTree_rec(Operands, Depth + 1);
 801       }
 802       return;
 803     }
 804     case Instruction::ExtractElement: {
 805       bool Reuse = CanReuseExtract(VL);
 806       if (Reuse) {
 807         DEBUG(dbgs() << "SLP: Reusing extract sequence.\n");
 808       }
 809       newTreeEntry(VL, Reuse);
 810       return;
 811     }
 812     case Instruction::Load: {
 813       // Check if the loads are consecutive or of we need to swizzle them.
 814       for (unsigned i = 0, e = VL.size() - 1; i < e; ++i) {
 815         LoadInst *L = cast<LoadInst>(VL[i]);
 816         if (!L->isSimple() || !isConsecutiveAccess(VL[i], VL[i + 1])) {
 817           newTreeEntry(VL, false);
 818           DEBUG(dbgs() << "SLP: Need to swizzle loads.\n");
 819           return;
 820         }
 821       }
 822       newTreeEntry(VL, true);
 823       DEBUG(dbgs() << "SLP: added a vector of loads.\n");
 824       return;
 825     }
 826     case Instruction::ZExt:
 827     case Instruction::SExt:
 828     case Instruction::FPToUI:
 829     case Instruction::FPToSI:
 830     case Instruction::FPExt:
 831     case Instruction::PtrToInt:
 832     case Instruction::IntToPtr:
 833     case Instruction::SIToFP:
 834     case Instruction::UIToFP:
 835     case Instruction::Trunc:
 836     case Instruction::FPTrunc:
 837     case Instruction::BitCast: {
 838       Type *SrcTy = VL0->getOperand(0)->getType();
 839       for (unsigned i = 0; i < VL.size(); ++i) {
 840         Type *Ty = cast<Instruction>(VL[i])->getOperand(0)->getType();
 841         if (Ty != SrcTy || Ty->isAggregateType() || Ty->isVectorTy()) {
 842           newTreeEntry(VL, false);
 843           DEBUG(dbgs() << "SLP: Gathering casts with different src types.\n");
 844           return;
 845         }
 846       }
 847       newTreeEntry(VL, true);
 848       DEBUG(dbgs() << "SLP: added a vector of casts.\n");
 849
 850       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
 851         ValueList Operands;
 852         // Prepare the operand vector.
 853         for (unsigned j = 0; j < VL.size(); ++j)
 854           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
 855
 856         buildTree_rec(Operands, Depth+1);
 857       }
 858       return;
 859     }
 860     case Instruction::ICmp:
 861     case Instruction::FCmp: {
 862       // Check that all of the compares have the same predicate.
 863       CmpInst::Predicate P0 = dyn_cast<CmpInst>(VL0)->getPredicate();
 864       Type *ComparedTy = cast<Instruction>(VL[0])->getOperand(0)->getType();
 865       for (unsigned i = 1, e = VL.size(); i < e; ++i) {
 866         CmpInst *Cmp = cast<CmpInst>(VL[i]);
 867         if (Cmp->getPredicate() != P0 ||
 868             Cmp->getOperand(0)->getType() != ComparedTy) {
 869           newTreeEntry(VL, false);
 870           DEBUG(dbgs() << "SLP: Gathering cmp with different predicate.\n");
 871           return;
 872         }
 873       }
 874
 875       newTreeEntry(VL, true);
 876       DEBUG(dbgs() << "SLP: added a vector of compares.\n");
 877
 878       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
 879         ValueList Operands;
 880         // Prepare the operand vector.
 881         for (unsigned j = 0; j < VL.size(); ++j)
 882           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
 883
 884         buildTree_rec(Operands, Depth+1);
 885       }
 886       return;
 887     }
 888     case Instruction::Select:
 889     case Instruction::Add:
 890     case Instruction::FAdd:
 891     case Instruction::Sub:
 892     case Instruction::FSub:
 893     case Instruction::Mul:
 894     case Instruction::FMul:
 895     case Instruction::UDiv:
 896     case Instruction::SDiv:
 897     case Instruction::FDiv:
 898     case Instruction::URem:
 899     case Instruction::SRem:
 900     case Instruction::FRem:
 901     case Instruction::Shl:
 902     case Instruction::LShr:
 903     case Instruction::AShr:
 904     case Instruction::And:
 905     case Instruction::Or:
 906     case Instruction::Xor: {
 907       newTreeEntry(VL, true);
 908       DEBUG(dbgs() << "SLP: added a vector of bin op.\n");
 909
 910       // Sort operands of the instructions so that each side is more likely to
 911       // have the same opcode.
 912       if (isa<BinaryOperator>(VL0) && VL0->isCommutative()) {
 913         ValueList Left, Right;
 914         reorderInputsAccordingToOpcode(VL, Left, Right);
 915         buildTree_rec(Left, Depth + 1);
 916         buildTree_rec(Right, Depth + 1);
 917         return;
 918       }
 919
 920       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
 921         ValueList Operands;
 922         // Prepare the operand vector.
 923         for (unsigned j = 0; j < VL.size(); ++j)
 924           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
 925
 926         buildTree_rec(Operands, Depth+1);
 927       }
 928       return;
 929     }
 930     case Instruction::Store: {
 931       // Check if the stores are consecutive or of we need to swizzle them.
 932       for (unsigned i = 0, e = VL.size() - 1; i < e; ++i)
 933         if (!isConsecutiveAccess(VL[i], VL[i + 1])) {
 934           newTreeEntry(VL, false);
 935           DEBUG(dbgs() << "SLP: Non-consecutive store.\n");
 936           return;
 937         }
 938
 939       newTreeEntry(VL, true);
 940       DEBUG(dbgs() << "SLP: added a vector of stores.\n");
 941
 942       ValueList Operands;
 943       for (unsigned j = 0; j < VL.size(); ++j)
 944         Operands.push_back(cast<Instruction>(VL[j])->getOperand(0));
 945
 946       // We can ignore these values because we are sinking them down.
 947       MemBarrierIgnoreList.insert(VL.begin(), VL.end());
 948       buildTree_rec(Operands, Depth + 1);
 949       return;
 950     }
 951     case Instruction::Call: {
 952       // Check if the calls are all to the same vectorizable intrinsic.
 953       CallInst *CI = cast<CallInst>(VL[0]);
 954       // Check if this is an Intrinsic call or something that can be
 955       // represented by an intrinsic call
 956       Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
 957       if (!isTriviallyVectorizable(ID)) {
 958         newTreeEntry(VL, false);
 959         DEBUG(dbgs() << "SLP: Non-vectorizable call.\n");
 960         return;
 961       }
 962
 963       Function *Int = CI->getCalledFunction();
 964
 965       for (unsigned i = 1, e = VL.size(); i != e; ++i) {
 966         CallInst *CI2 = dyn_cast<CallInst>(VL[i]);
 967         if (!CI2 || CI2->getCalledFunction() != Int ||
 968             getIntrinsicIDForCall(CI2, TLI) != ID) {
 969           newTreeEntry(VL, false);
 970           DEBUG(dbgs() << "SLP: mismatched calls:" << *CI << "!=" << *VL[i]
 971                        << "\n");
 972           return;
 973         }
 974       }
 975
 976       newTreeEntry(VL, true);
 977       for (unsigned i = 0, e = CI->getNumArgOperands(); i != e; ++i) {
 978         ValueList Operands;
 979         // Prepare the operand vector.
 980         for (unsigned j = 0; j < VL.size(); ++j) {
 981           CallInst *CI2 = dyn_cast<CallInst>(VL[j]);
 982           Operands.push_back(CI2->getArgOperand(i));
 983         }
 984         buildTree_rec(Operands, Depth + 1);
 985       }
 986       return;
 987     }
 988     default:
 989       newTreeEntry(VL, false);
 990       DEBUG(dbgs() << "SLP: Gathering unknown instruction.\n");
 991       return;
 992   }
 993 }
 994
 995 int BoUpSLP::getEntryCost(TreeEntry *E) {
 996   ArrayRef<Value*> VL = E->Scalars;
 997
 998   Type *ScalarTy = VL[0]->getType();
 999   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
1000     ScalarTy = SI->getValueOperand()->getType();
1001   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
1002
1003   if (E->NeedToGather) {
1004     if (allConstant(VL))
1005       return 0;
1006     if (isSplat(VL)) {
1007       return TTI->getShuffleCost(TargetTransformInfo::SK_Broadcast, VecTy, 0);
1008     }
1009     return getGatherCost(E->Scalars);
1010   }
1011
1012   assert(getSameOpcode(VL) && getSameType(VL) && getSameBlock(VL) &&
1013          "Invalid VL");
1014   Instruction *VL0 = cast<Instruction>(VL[0]);
1015   unsigned Opcode = VL0->getOpcode();
1016   switch (Opcode) {
1017     case Instruction::PHI: {
1018       return 0;
1019     }
1020     case Instruction::ExtractElement: {
1021       if (CanReuseExtract(VL)) {
1022         int DeadCost = 0;
1023         for (unsigned i = 0, e = VL.size(); i < e; ++i) {
1024           ExtractElementInst *E = cast<ExtractElementInst>(VL[i]);
1025           if (E->hasOneUse())
1026             // Take credit for instruction that will become dead.
1027             DeadCost +=
1028                 TTI->getVectorInstrCost(Instruction::ExtractElement, VecTy, i);
1029         }
1030         return -DeadCost;
1031       }
1032       return getGatherCost(VecTy);
1033     }
1034     case Instruction::ZExt:
1035     case Instruction::SExt:
1036     case Instruction::FPToUI:
1037     case Instruction::FPToSI:
1038     case Instruction::FPExt:
1039     case Instruction::PtrToInt:
1040     case Instruction::IntToPtr:
1041     case Instruction::SIToFP:
1042     case Instruction::UIToFP:
1043     case Instruction::Trunc:
1044     case Instruction::FPTrunc:
1045     case Instruction::BitCast: {
1046       Type *SrcTy = VL0->getOperand(0)->getType();
1047
1048       // Calculate the cost of this instruction.
1049       int ScalarCost = VL.size() * TTI->getCastInstrCost(VL0->getOpcode(),
1050                                                          VL0->getType(), SrcTy);
1051
1052       VectorType *SrcVecTy = VectorType::get(SrcTy, VL.size());
1053       int VecCost = TTI->getCastInstrCost(VL0->getOpcode(), VecTy, SrcVecTy);
1054       return VecCost - ScalarCost;
1055     }
1056     case Instruction::FCmp:
1057     case Instruction::ICmp:
1058     case Instruction::Select:
1059     case Instruction::Add:
1060     case Instruction::FAdd:
1061     case Instruction::Sub:
1062     case Instruction::FSub:
1063     case Instruction::Mul:
1064     case Instruction::FMul:
1065     case Instruction::UDiv:
1066     case Instruction::SDiv:
1067     case Instruction::FDiv:
1068     case Instruction::URem:
1069     case Instruction::SRem:
1070     case Instruction::FRem:
1071     case Instruction::Shl:
1072     case Instruction::LShr:
1073     case Instruction::AShr:
1074     case Instruction::And:
1075     case Instruction::Or:
1076     case Instruction::Xor: {
1077       // Calculate the cost of this instruction.
1078       int ScalarCost = 0;
1079       int VecCost = 0;
1080       if (Opcode == Instruction::FCmp || Opcode == Instruction::ICmp ||
1081           Opcode == Instruction::Select) {
1082         VectorType *MaskTy = VectorType::get(Builder.getInt1Ty(), VL.size());
1083         ScalarCost = VecTy->getNumElements() *
1084         TTI->getCmpSelInstrCost(Opcode, ScalarTy, Builder.getInt1Ty());
1085         VecCost = TTI->getCmpSelInstrCost(Opcode, VecTy, MaskTy);
1086       } else {
1087         // Certain instructions can be cheaper to vectorize if they have a
1088         // constant second vector operand.
1089         TargetTransformInfo::OperandValueKind Op1VK =
1090             TargetTransformInfo::OK_AnyValue;
1091         TargetTransformInfo::OperandValueKind Op2VK =
1092             TargetTransformInfo::OK_UniformConstantValue;
1093
1094         // If all operands are exactly the same ConstantInt then set the
1095         // operand kind to OK_UniformConstantValue.
1096         // If instead not all operands are constants, then set the operand kind
1097         // to OK_AnyValue. If all operands are constants but not the same,
1098         // then set the operand kind to OK_NonUniformConstantValue.
1099         ConstantInt *CInt = nullptr;
1100         for (unsigned i = 0; i < VL.size(); ++i) {
1101           const Instruction *I = cast<Instruction>(VL[i]);
1102           if (!isa<ConstantInt>(I->getOperand(1))) {
1103             Op2VK = TargetTransformInfo::OK_AnyValue;
1104             break;
1105           }
1106           if (i == 0) {
1107             CInt = cast<ConstantInt>(I->getOperand(1));
1108             continue;
1109           }
1110           if (Op2VK == TargetTransformInfo::OK_UniformConstantValue &&
1111               CInt != cast<ConstantInt>(I->getOperand(1)))
1112             Op2VK = TargetTransformInfo::OK_NonUniformConstantValue;
1113         }
1114
1115         ScalarCost =
1116             VecTy->getNumElements() *
1117             TTI->getArithmeticInstrCost(Opcode, ScalarTy, Op1VK, Op2VK);
1118         VecCost = TTI->getArithmeticInstrCost(Opcode, VecTy, Op1VK, Op2VK);
1119       }
1120       return VecCost - ScalarCost;
1121     }
1122     case Instruction::Load: {
1123       // Cost of wide load - cost of scalar loads.
1124       int ScalarLdCost = VecTy->getNumElements() *
1125       TTI->getMemoryOpCost(Instruction::Load, ScalarTy, 1, 0);
1126       int VecLdCost = TTI->getMemoryOpCost(Instruction::Load, VecTy, 1, 0);
1127       return VecLdCost - ScalarLdCost;
1128     }
1129     case Instruction::Store: {
1130       // We know that we can merge the stores. Calculate the cost.
1131       int ScalarStCost = VecTy->getNumElements() *
1132       TTI->getMemoryOpCost(Instruction::Store, ScalarTy, 1, 0);
1133       int VecStCost = TTI->getMemoryOpCost(Instruction::Store, VecTy, 1, 0);
1134       return VecStCost - ScalarStCost;
1135     }
1136     case Instruction::Call: {
1137       CallInst *CI = cast<CallInst>(VL0);
1138       Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
1139
1140       // Calculate the cost of the scalar and vector calls.
1141       SmallVector<Type*, 4> ScalarTys, VecTys;
1142       for (unsigned op = 0, opc = CI->getNumArgOperands(); op!= opc; ++op) {
1143         ScalarTys.push_back(CI->getArgOperand(op)->getType());
1144         VecTys.push_back(VectorType::get(CI->getArgOperand(op)->getType(),
1145                                          VecTy->getNumElements()));
1146       }
1147
1148       int ScalarCallCost = VecTy->getNumElements() *
1149           TTI->getIntrinsicInstrCost(ID, ScalarTy, ScalarTys);
1150
1151       int VecCallCost = TTI->getIntrinsicInstrCost(ID, VecTy, VecTys);
1152
1153       DEBUG(dbgs() << "SLP: Call cost "<< VecCallCost - ScalarCallCost
1154             << " (" << VecCallCost  << "-" <<  ScalarCallCost << ")"
1155             << " for " << *CI << "\n");
1156
1157       return VecCallCost - ScalarCallCost;
1158     }
1159     default:
1160       llvm_unreachable("Unknown instruction");
1161   }
1162 }
1163
1164 bool BoUpSLP::isFullyVectorizableTinyTree() {
1165   DEBUG(dbgs() << "SLP: Check whether the tree with height " <<
1166         VectorizableTree.size() << " is fully vectorizable .\n");
1167
1168   // We only handle trees of height 2.
1169   if (VectorizableTree.size() != 2)
1170     return false;
1171
1172   // Handle splat stores.
1173   if (!VectorizableTree[0].NeedToGather && isSplat(VectorizableTree[1].Scalars))
1174     return true;
1175
1176   // Gathering cost would be too much for tiny trees.
1177   if (VectorizableTree[0].NeedToGather || VectorizableTree[1].NeedToGather)
1178     return false;
1179
1180   return true;
1181 }
1182
1183 int BoUpSLP::getTreeCost() {
1184   int Cost = 0;
1185   DEBUG(dbgs() << "SLP: Calculating cost for tree of size " <<
1186         VectorizableTree.size() << ".\n");
1187
1188   // We only vectorize tiny trees if it is fully vectorizable.
1189   if (VectorizableTree.size() < 3 && !isFullyVectorizableTinyTree()) {
1190     if (!VectorizableTree.size()) {
1191       assert(!ExternalUses.size() && "We should not have any external users");
1192     }
1193     return INT_MAX;
1194   }
1195
1196   unsigned BundleWidth = VectorizableTree[0].Scalars.size();
1197
1198   for (unsigned i = 0, e = VectorizableTree.size(); i != e; ++i) {
1199     int C = getEntryCost(&VectorizableTree[i]);
1200     DEBUG(dbgs() << "SLP: Adding cost " << C << " for bundle that starts with "
1201           << *VectorizableTree[i].Scalars[0] << " .\n");
1202     Cost += C;
1203   }
1204
1205   SmallSet<Value *, 16> ExtractCostCalculated;
1206   int ExtractCost = 0;
1207   for (UserList::iterator I = ExternalUses.begin(), E = ExternalUses.end();
1208        I != E; ++I) {
1209     // We only add extract cost once for the same scalar.
1210     if (!ExtractCostCalculated.insert(I->Scalar))
1211       continue;
1212
1213     VectorType *VecTy = VectorType::get(I->Scalar->getType(), BundleWidth);
1214     ExtractCost += TTI->getVectorInstrCost(Instruction::ExtractElement, VecTy,
1215                                            I->Lane);
1216   }
1217
1218   DEBUG(dbgs() << "SLP: Total Cost " << Cost + ExtractCost<< ".\n");
1219   return  Cost + ExtractCost;
1220 }
1221
1222 int BoUpSLP::getGatherCost(Type *Ty) {
1223   int Cost = 0;
1224   for (unsigned i = 0, e = cast<VectorType>(Ty)->getNumElements(); i < e; ++i)
1225     Cost += TTI->getVectorInstrCost(Instruction::InsertElement, Ty, i);
1226   return Cost;
1227 }
1228
1229 int BoUpSLP::getGatherCost(ArrayRef<Value *> VL) {
1230   // Find the type of the operands in VL.
1231   Type *ScalarTy = VL[0]->getType();
1232   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
1233     ScalarTy = SI->getValueOperand()->getType();
1234   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
1235   // Find the cost of inserting/extracting values from the vector.
1236   return getGatherCost(VecTy);
1237 }
1238
1239 AliasAnalysis::Location BoUpSLP::getLocation(Instruction *I) {
1240   if (StoreInst *SI = dyn_cast<StoreInst>(I))
1241     return AA->getLocation(SI);
1242   if (LoadInst *LI = dyn_cast<LoadInst>(I))
1243     return AA->getLocation(LI);
1244   return AliasAnalysis::Location();
1245 }
1246
1247 Value *BoUpSLP::getPointerOperand(Value *I) {
1248   if (LoadInst *LI = dyn_cast<LoadInst>(I))
1249     return LI->getPointerOperand();
1250   if (StoreInst *SI = dyn_cast<StoreInst>(I))
1251     return SI->getPointerOperand();
1252   return nullptr;
1253 }
1254
1255 unsigned BoUpSLP::getAddressSpaceOperand(Value *I) {
1256   if (LoadInst *L = dyn_cast<LoadInst>(I))
1257     return L->getPointerAddressSpace();
1258   if (StoreInst *S = dyn_cast<StoreInst>(I))
1259     return S->getPointerAddressSpace();
1260   return -1;
1261 }
1262
1263 bool BoUpSLP::isConsecutiveAccess(Value *A, Value *B) {
1264   Value *PtrA = getPointerOperand(A);
1265   Value *PtrB = getPointerOperand(B);
1266   unsigned ASA = getAddressSpaceOperand(A);
1267   unsigned ASB = getAddressSpaceOperand(B);
1268
1269   // Check that the address spaces match and that the pointers are valid.
1270   if (!PtrA || !PtrB || (ASA != ASB))
1271     return false;
1272
1273   // Make sure that A and B are different pointers of the same type.
1274   if (PtrA == PtrB || PtrA->getType() != PtrB->getType())
1275     return false;
1276
1277   unsigned PtrBitWidth = DL->getPointerSizeInBits(ASA);
1278   Type *Ty = cast<PointerType>(PtrA->getType())->getElementType();
1279   APInt Size(PtrBitWidth, DL->getTypeStoreSize(Ty));
1280
1281   APInt OffsetA(PtrBitWidth, 0), OffsetB(PtrBitWidth, 0);
1282   PtrA = PtrA->stripAndAccumulateInBoundsConstantOffsets(*DL, OffsetA);
1283   PtrB = PtrB->stripAndAccumulateInBoundsConstantOffsets(*DL, OffsetB);
1284
1285   APInt OffsetDelta = OffsetB - OffsetA;
1286
1287   // Check if they are based on the same pointer. That makes the offsets
1288   // sufficient.
1289   if (PtrA == PtrB)
1290     return OffsetDelta == Size;
1291
1292   // Compute the necessary base pointer delta to have the necessary final delta
1293   // equal to the size.
1294   APInt BaseDelta = Size - OffsetDelta;
1295
1296   // Otherwise compute the distance with SCEV between the base pointers.
1297   const SCEV *PtrSCEVA = SE->getSCEV(PtrA);
1298   const SCEV *PtrSCEVB = SE->getSCEV(PtrB);
1299   const SCEV *C = SE->getConstant(BaseDelta);
1300   const SCEV *X = SE->getAddExpr(PtrSCEVA, C);
1301   return X == PtrSCEVB;
1302 }
1303
1304 Value *BoUpSLP::getSinkBarrier(Instruction *Src, Instruction *Dst) {
1305   assert(Src->getParent() == Dst->getParent() && "Not the same BB");
1306   BasicBlock::iterator I = Src, E = Dst;
1307   /// Scan all of the instruction from SRC to DST and check if
1308   /// the source may alias.
1309   for (++I; I != E; ++I) {
1310     // Ignore store instructions that are marked as 'ignore'.
1311     if (MemBarrierIgnoreList.count(I))
1312       continue;
1313     if (Src->mayWriteToMemory()) /* Write */ {
1314       if (!I->mayReadOrWriteMemory())
1315         continue;
1316     } else /* Read */ {
1317       if (!I->mayWriteToMemory())
1318         continue;
1319     }
1320     AliasAnalysis::Location A = getLocation(&*I);
1321     AliasAnalysis::Location B = getLocation(Src);
1322
1323     if (!A.Ptr || !B.Ptr || AA->alias(A, B))
1324       return I;
1325   }
1326   return nullptr;
1327 }
1328
1329 int BoUpSLP::getLastIndex(ArrayRef<Value *> VL) {
1330   BasicBlock *BB = cast<Instruction>(VL[0])->getParent();
1331   assert(BB == getSameBlock(VL) && BlocksNumbers.count(BB) && "Invalid block");
1332   BlockNumbering &BN = BlocksNumbers[BB];
1333
1334   int MaxIdx = BN.getIndex(BB->getFirstNonPHI());
1335   for (unsigned i = 0, e = VL.size(); i < e; ++i)
1336     MaxIdx = std::max(MaxIdx, BN.getIndex(cast<Instruction>(VL[i])));
1337   return MaxIdx;
1338 }
1339
1340 Instruction *BoUpSLP::getLastInstruction(ArrayRef<Value *> VL) {
1341   BasicBlock *BB = cast<Instruction>(VL[0])->getParent();
1342   assert(BB == getSameBlock(VL) && BlocksNumbers.count(BB) && "Invalid block");
1343   BlockNumbering &BN = BlocksNumbers[BB];
1344
1345   int MaxIdx = BN.getIndex(cast<Instruction>(VL[0]));
1346   for (unsigned i = 1, e = VL.size(); i < e; ++i)
1347     MaxIdx = std::max(MaxIdx, BN.getIndex(cast<Instruction>(VL[i])));
1348   Instruction *I = BN.getInstruction(MaxIdx);
1349   assert(I && "bad location");
1350   return I;
1351 }
1352
1353 void BoUpSLP::setInsertPointAfterBundle(ArrayRef<Value *> VL) {
1354   Instruction *VL0 = cast<Instruction>(VL[0]);
1355   Instruction *LastInst = getLastInstruction(VL);
1356   BasicBlock::iterator NextInst = LastInst;
1357   ++NextInst;
1358   Builder.SetInsertPoint(VL0->getParent(), NextInst);
1359   Builder.SetCurrentDebugLocation(VL0->getDebugLoc());
1360 }
1361
1362 Value *BoUpSLP::Gather(ArrayRef<Value *> VL, VectorType *Ty) {
1363   Value *Vec = UndefValue::get(Ty);
1364   // Generate the 'InsertElement' instruction.
1365   for (unsigned i = 0; i < Ty->getNumElements(); ++i) {
1366     Vec = Builder.CreateInsertElement(Vec, VL[i], Builder.getInt32(i));
1367     if (Instruction *Insrt = dyn_cast<Instruction>(Vec)) {
1368       GatherSeq.insert(Insrt);
1369       CSEBlocks.insert(Insrt->getParent());
1370
1371       // Add to our 'need-to-extract' list.
1372       if (ScalarToTreeEntry.count(VL[i])) {
1373         int Idx = ScalarToTreeEntry[VL[i]];
1374         TreeEntry *E = &VectorizableTree[Idx];
1375         // Find which lane we need to extract.
1376         int FoundLane = -1;
1377         for (unsigned Lane = 0, LE = VL.size(); Lane != LE; ++Lane) {
1378           // Is this the lane of the scalar that we are looking for ?
1379           if (E->Scalars[Lane] == VL[i]) {
1380             FoundLane = Lane;
1381             break;
1382           }
1383         }
1384         assert(FoundLane >= 0 && "Could not find the correct lane");
1385         ExternalUses.push_back(ExternalUser(VL[i], Insrt, FoundLane));
1386       }
1387     }
1388   }
1389
1390   return Vec;
1391 }
1392
1393 Value *BoUpSLP::alreadyVectorized(ArrayRef<Value *> VL) const {
1394   SmallDenseMap<Value*, int>::const_iterator Entry
1395     = ScalarToTreeEntry.find(VL[0]);
1396   if (Entry != ScalarToTreeEntry.end()) {
1397     int Idx = Entry->second;
1398     const TreeEntry *En = &VectorizableTree[Idx];
1399     if (En->isSame(VL) && En->VectorizedValue)
1400       return En->VectorizedValue;
1401   }
1402   return nullptr;
1403 }
1404
1405 Value *BoUpSLP::vectorizeTree(ArrayRef<Value *> VL) {
1406   if (ScalarToTreeEntry.count(VL[0])) {
1407     int Idx = ScalarToTreeEntry[VL[0]];
1408     TreeEntry *E = &VectorizableTree[Idx];
1409     if (E->isSame(VL))
1410       return vectorizeTree(E);
1411   }
1412
1413   Type *ScalarTy = VL[0]->getType();
1414   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
1415     ScalarTy = SI->getValueOperand()->getType();
1416   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
1417
1418   return Gather(VL, VecTy);
1419 }
1420
1421 Value *BoUpSLP::vectorizeTree(TreeEntry *E) {
1422   IRBuilder<>::InsertPointGuard Guard(Builder);
1423
1424   if (E->VectorizedValue) {
1425     DEBUG(dbgs() << "SLP: Diamond merged for " << *E->Scalars[0] << ".\n");
1426     return E->VectorizedValue;
1427   }
1428
1429   Instruction *VL0 = cast<Instruction>(E->Scalars[0]);
1430   Type *ScalarTy = VL0->getType();
1431   if (StoreInst *SI = dyn_cast<StoreInst>(VL0))
1432     ScalarTy = SI->getValueOperand()->getType();
1433   VectorType *VecTy = VectorType::get(ScalarTy, E->Scalars.size());
1434
1435   if (E->NeedToGather) {
1436     setInsertPointAfterBundle(E->Scalars);
1437     return Gather(E->Scalars, VecTy);
1438   }
1439
1440   unsigned Opcode = VL0->getOpcode();
1441   assert(Opcode == getSameOpcode(E->Scalars) && "Invalid opcode");
1442
1443   switch (Opcode) {
1444     case Instruction::PHI: {
1445       PHINode *PH = dyn_cast<PHINode>(VL0);
1446       Builder.SetInsertPoint(PH->getParent()->getFirstNonPHI());
1447       Builder.SetCurrentDebugLocation(PH->getDebugLoc());
1448       PHINode *NewPhi = Builder.CreatePHI(VecTy, PH->getNumIncomingValues());
1449       E->VectorizedValue = NewPhi;
1450
1451       // PHINodes may have multiple entries from the same block. We want to
1452       // visit every block once.
1453       SmallSet<BasicBlock*, 4> VisitedBBs;
1454
1455       for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
1456         ValueList Operands;
1457         BasicBlock *IBB = PH->getIncomingBlock(i);
1458
1459         if (!VisitedBBs.insert(IBB)) {
1460           NewPhi->addIncoming(NewPhi->getIncomingValueForBlock(IBB), IBB);
1461           continue;
1462         }
1463
1464         // Prepare the operand vector.
1465         for (unsigned j = 0; j < E->Scalars.size(); ++j)
1466           Operands.push_back(cast<PHINode>(E->Scalars[j])->
1467                              getIncomingValueForBlock(IBB));
1468
1469         Builder.SetInsertPoint(IBB->getTerminator());
1470         Builder.SetCurrentDebugLocation(PH->getDebugLoc());
1471         Value *Vec = vectorizeTree(Operands);
1472         NewPhi->addIncoming(Vec, IBB);
1473       }
1474
1475       assert(NewPhi->getNumIncomingValues() == PH->getNumIncomingValues() &&
1476              "Invalid number of incoming values");
1477       return NewPhi;
1478     }
1479
1480     case Instruction::ExtractElement: {
1481       if (CanReuseExtract(E->Scalars)) {
1482         Value *V = VL0->getOperand(0);
1483         E->VectorizedValue = V;
1484         return V;
1485       }
1486       return Gather(E->Scalars, VecTy);
1487     }
1488     case Instruction::ZExt:
1489     case Instruction::SExt:
1490     case Instruction::FPToUI:
1491     case Instruction::FPToSI:
1492     case Instruction::FPExt:
1493     case Instruction::PtrToInt:
1494     case Instruction::IntToPtr:
1495     case Instruction::SIToFP:
1496     case Instruction::UIToFP:
1497     case Instruction::Trunc:
1498     case Instruction::FPTrunc:
1499     case Instruction::BitCast: {
1500       ValueList INVL;
1501       for (int i = 0, e = E->Scalars.size(); i < e; ++i)
1502         INVL.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0));
1503
1504       setInsertPointAfterBundle(E->Scalars);
1505
1506       Value *InVec = vectorizeTree(INVL);
1507
1508       if (Value *V = alreadyVectorized(E->Scalars))
1509         return V;
1510
1511       CastInst *CI = dyn_cast<CastInst>(VL0);
1512       Value *V = Builder.CreateCast(CI->getOpcode(), InVec, VecTy);
1513       E->VectorizedValue = V;
1514       return V;
1515     }
1516     case Instruction::FCmp:
1517     case Instruction::ICmp: {
1518       ValueList LHSV, RHSV;
1519       for (int i = 0, e = E->Scalars.size(); i < e; ++i) {
1520         LHSV.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0));
1521         RHSV.push_back(cast<Instruction>(E->Scalars[i])->getOperand(1));
1522       }
1523
1524       setInsertPointAfterBundle(E->Scalars);
1525
1526       Value *L = vectorizeTree(LHSV);
1527       Value *R = vectorizeTree(RHSV);
1528
1529       if (Value *V = alreadyVectorized(E->Scalars))
1530         return V;
1531
1532       CmpInst::Predicate P0 = dyn_cast<CmpInst>(VL0)->getPredicate();
1533       Value *V;
1534       if (Opcode == Instruction::FCmp)
1535         V = Builder.CreateFCmp(P0, L, R);
1536       else
1537         V = Builder.CreateICmp(P0, L, R);
1538
1539       E->VectorizedValue = V;
1540       return V;
1541     }
1542     case Instruction::Select: {
1543       ValueList TrueVec, FalseVec, CondVec;
1544       for (int i = 0, e = E->Scalars.size(); i < e; ++i) {
1545         CondVec.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0));
1546         TrueVec.push_back(cast<Instruction>(E->Scalars[i])->getOperand(1));
1547         FalseVec.push_back(cast<Instruction>(E->Scalars[i])->getOperand(2));
1548       }
1549
1550       setInsertPointAfterBundle(E->Scalars);
1551
1552       Value *Cond = vectorizeTree(CondVec);
1553       Value *True = vectorizeTree(TrueVec);
1554       Value *False = vectorizeTree(FalseVec);
1555
1556       if (Value *V = alreadyVectorized(E->Scalars))
1557         return V;
1558
1559       Value *V = Builder.CreateSelect(Cond, True, False);
1560       E->VectorizedValue = V;
1561       return V;
1562     }
1563     case Instruction::Add:
1564     case Instruction::FAdd:
1565     case Instruction::Sub:
1566     case Instruction::FSub:
1567     case Instruction::Mul:
1568     case Instruction::FMul:
1569     case Instruction::UDiv:
1570     case Instruction::SDiv:
1571     case Instruction::FDiv:
1572     case Instruction::URem:
1573     case Instruction::SRem:
1574     case Instruction::FRem:
1575     case Instruction::Shl:
1576     case Instruction::LShr:
1577     case Instruction::AShr:
1578     case Instruction::And:
1579     case Instruction::Or:
1580     case Instruction::Xor: {
1581       ValueList LHSVL, RHSVL;
1582       if (isa<BinaryOperator>(VL0) && VL0->isCommutative())
1583         reorderInputsAccordingToOpcode(E->Scalars, LHSVL, RHSVL);
1584       else
1585         for (int i = 0, e = E->Scalars.size(); i < e; ++i) {
1586           LHSVL.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0));
1587           RHSVL.push_back(cast<Instruction>(E->Scalars[i])->getOperand(1));
1588         }
1589
1590       setInsertPointAfterBundle(E->Scalars);
1591
1592       Value *LHS = vectorizeTree(LHSVL);
1593       Value *RHS = vectorizeTree(RHSVL);
1594
1595       if (LHS == RHS && isa<Instruction>(LHS)) {
1596         assert((VL0->getOperand(0) == VL0->getOperand(1)) && "Invalid order");
1597       }
1598
1599       if (Value *V = alreadyVectorized(E->Scalars))
1600         return V;
1601
1602       BinaryOperator *BinOp = cast<BinaryOperator>(VL0);
1603       Value *V = Builder.CreateBinOp(BinOp->getOpcode(), LHS, RHS);
1604       E->VectorizedValue = V;
1605
1606       if (Instruction *I = dyn_cast<Instruction>(V))
1607         return propagateMetadata(I, E->Scalars);
1608
1609       return V;
1610     }
1611     case Instruction::Load: {
1612       // Loads are inserted at the head of the tree because we don't want to
1613       // sink them all the way down past store instructions.
1614       setInsertPointAfterBundle(E->Scalars);
1615
1616       LoadInst *LI = cast<LoadInst>(VL0);
1617       unsigned AS = LI->getPointerAddressSpace();
1618
1619       Value *VecPtr = Builder.CreateBitCast(LI->getPointerOperand(),
1620                                             VecTy->getPointerTo(AS));
1621       unsigned Alignment = LI->getAlignment();
1622       LI = Builder.CreateLoad(VecPtr);
1623       LI->setAlignment(Alignment);
1624       E->VectorizedValue = LI;
1625       return propagateMetadata(LI, E->Scalars);
1626     }
1627     case Instruction::Store: {
1628       StoreInst *SI = cast<StoreInst>(VL0);
1629       unsigned Alignment = SI->getAlignment();
1630       unsigned AS = SI->getPointerAddressSpace();
1631
1632       ValueList ValueOp;
1633       for (int i = 0, e = E->Scalars.size(); i < e; ++i)
1634         ValueOp.push_back(cast<StoreInst>(E->Scalars[i])->getValueOperand());
1635
1636       setInsertPointAfterBundle(E->Scalars);
1637
1638       Value *VecValue = vectorizeTree(ValueOp);
1639       Value *VecPtr = Builder.CreateBitCast(SI->getPointerOperand(),
1640                                             VecTy->getPointerTo(AS));
1641       StoreInst *S = Builder.CreateStore(VecValue, VecPtr);
1642       S->setAlignment(Alignment);
1643       E->VectorizedValue = S;
1644       return propagateMetadata(S, E->Scalars);
1645     }
1646     case Instruction::Call: {
1647       CallInst *CI = cast<CallInst>(VL0);
1648       setInsertPointAfterBundle(E->Scalars);
1649       std::vector<Value *> OpVecs;
1650       for (int j = 0, e = CI->getNumArgOperands(); j < e; ++j) {
1651         ValueList OpVL;
1652         for (int i = 0, e = E->Scalars.size(); i < e; ++i) {
1653           CallInst *CEI = cast<CallInst>(E->Scalars[i]);
1654           OpVL.push_back(CEI->getArgOperand(j));
1655         }
1656
1657         Value *OpVec = vectorizeTree(OpVL);
1658         DEBUG(dbgs() << "SLP: OpVec[" << j << "]: " << *OpVec << "\n");
1659         OpVecs.push_back(OpVec);
1660       }
1661
1662       Module *M = F->getParent();
1663       Intrinsic::ID ID = getIntrinsicIDForCall(CI, TLI);
1664       Type *Tys[] = { VectorType::get(CI->getType(), E->Scalars.size()) };
1665       Function *CF = Intrinsic::getDeclaration(M, ID, Tys);
1666       Value *V = Builder.CreateCall(CF, OpVecs);
1667       E->VectorizedValue = V;
1668       return V;
1669     }
1670     default:
1671     llvm_unreachable("unknown inst");
1672   }
1673   return nullptr;
1674 }
1675
1676 Value *BoUpSLP::vectorizeTree() {
1677   Builder.SetInsertPoint(F->getEntryBlock().begin());
1678   vectorizeTree(&VectorizableTree[0]);
1679
1680   DEBUG(dbgs() << "SLP: Extracting " << ExternalUses.size() << " values .\n");
1681
1682   // Extract all of the elements with the external uses.
1683   for (UserList::iterator it = ExternalUses.begin(), e = ExternalUses.end();
1684        it != e; ++it) {
1685     Value *Scalar = it->Scalar;
1686     llvm::User *User = it->User;
1687
1688     // Skip users that we already RAUW. This happens when one instruction
1689     // has multiple uses of the same value.
1690     if (std::find(Scalar->user_begin(), Scalar->user_end(), User) ==
1691         Scalar->user_end())
1692       continue;
1693     assert(ScalarToTreeEntry.count(Scalar) && "Invalid scalar");
1694
1695     int Idx = ScalarToTreeEntry[Scalar];
1696     TreeEntry *E = &VectorizableTree[Idx];
1697     assert(!E->NeedToGather && "Extracting from a gather list");
1698
1699     Value *Vec = E->VectorizedValue;
1700     assert(Vec && "Can't find vectorizable value");
1701
1702     Value *Lane = Builder.getInt32(it->Lane);
1703     // Generate extracts for out-of-tree users.
1704     // Find the insertion point for the extractelement lane.
1705     if (isa<Instruction>(Vec)){
1706       if (PHINode *PH = dyn_cast<PHINode>(User)) {
1707         for (int i = 0, e = PH->getNumIncomingValues(); i != e; ++i) {
1708           if (PH->getIncomingValue(i) == Scalar) {
1709             Builder.SetInsertPoint(PH->getIncomingBlock(i)->getTerminator());
1710             Value *Ex = Builder.CreateExtractElement(Vec, Lane);
1711             CSEBlocks.insert(PH->getIncomingBlock(i));
1712             PH->setOperand(i, Ex);
1713           }
1714         }
1715       } else {
1716         Builder.SetInsertPoint(cast<Instruction>(User));
1717         Value *Ex = Builder.CreateExtractElement(Vec, Lane);
1718         CSEBlocks.insert(cast<Instruction>(User)->getParent());
1719         User->replaceUsesOfWith(Scalar, Ex);
1720      }
1721     } else {
1722       Builder.SetInsertPoint(F->getEntryBlock().begin());
1723       Value *Ex = Builder.CreateExtractElement(Vec, Lane);
1724       CSEBlocks.insert(&F->getEntryBlock());
1725       User->replaceUsesOfWith(Scalar, Ex);
1726     }
1727
1728     DEBUG(dbgs() << "SLP: Replaced:" << *User << ".\n");
1729   }
1730
1731   // For each vectorized value:
1732   for (int EIdx = 0, EE = VectorizableTree.size(); EIdx < EE; ++EIdx) {
1733     TreeEntry *Entry = &VectorizableTree[EIdx];
1734
1735     // For each lane:
1736     for (int Lane = 0, LE = Entry->Scalars.size(); Lane != LE; ++Lane) {
1737       Value *Scalar = Entry->Scalars[Lane];
1738
1739       // No need to handle users of gathered values.
1740       if (Entry->NeedToGather)
1741         continue;
1742
1743       assert(Entry->VectorizedValue && "Can't find vectorizable value");
1744
1745       Type *Ty = Scalar->getType();
1746       if (!Ty->isVoidTy()) {
1747 #ifndef NDEBUG
1748         for (User *U : Scalar->users()) {
1749           DEBUG(dbgs() << "SLP: \tvalidating user:" << *U << ".\n");
1750
1751           assert((ScalarToTreeEntry.count(U) ||
1752                   // It is legal to replace the reduction users by undef.
1753                   (RdxOps && RdxOps->count(U))) &&
1754                  "Replacing out-of-tree value with undef");
1755         }
1756 #endif
1757         Value *Undef = UndefValue::get(Ty);
1758         Scalar->replaceAllUsesWith(Undef);
1759       }
1760       DEBUG(dbgs() << "SLP: \tErasing scalar:" << *Scalar << ".\n");
1761       cast<Instruction>(Scalar)->eraseFromParent();
1762     }
1763   }
1764
1765   for (Function::iterator it = F->begin(), e = F->end(); it != e; ++it) {
1766     BlocksNumbers[it].forget();
1767   }
1768   Builder.ClearInsertionPoint();
1769
1770   return VectorizableTree[0].VectorizedValue;
1771 }
1772
1773 void BoUpSLP::optimizeGatherSequence() {
1774   DEBUG(dbgs() << "SLP: Optimizing " << GatherSeq.size()
1775         << " gather sequences instructions.\n");
1776   // LICM InsertElementInst sequences.
1777   for (SetVector<Instruction *>::iterator it = GatherSeq.begin(),
1778        e = GatherSeq.end(); it != e; ++it) {
1779     InsertElementInst *Insert = dyn_cast<InsertElementInst>(*it);
1780
1781     if (!Insert)
1782       continue;
1783
1784     // Check if this block is inside a loop.
1785     Loop *L = LI->getLoopFor(Insert->getParent());
1786     if (!L)
1787       continue;
1788
1789     // Check if it has a preheader.
1790     BasicBlock *PreHeader = L->getLoopPreheader();
1791     if (!PreHeader)
1792       continue;
1793
1794     // If the vector or the element that we insert into it are
1795     // instructions that are defined in this basic block then we can't
1796     // hoist this instruction.
1797     Instruction *CurrVec = dyn_cast<Instruction>(Insert->getOperand(0));
1798     Instruction *NewElem = dyn_cast<Instruction>(Insert->getOperand(1));
1799     if (CurrVec && L->contains(CurrVec))
1800       continue;
1801     if (NewElem && L->contains(NewElem))
1802       continue;
1803
1804     // We can hoist this instruction. Move it to the pre-header.
1805     Insert->moveBefore(PreHeader->getTerminator());
1806   }
1807
1808   // Sort blocks by domination. This ensures we visit a block after all blocks
1809   // dominating it are visited.
1810   SmallVector<BasicBlock *, 8> CSEWorkList(CSEBlocks.begin(), CSEBlocks.end());
1811   std::stable_sort(CSEWorkList.begin(), CSEWorkList.end(),
1812                    [this](const BasicBlock *A, const BasicBlock *B) {
1813     return DT->properlyDominates(A, B);
1814   });
1815
1816   // Perform O(N^2) search over the gather sequences and merge identical
1817   // instructions. TODO: We can further optimize this scan if we split the
1818   // instructions into different buckets based on the insert lane.
1819   SmallVector<Instruction *, 16> Visited;
1820   for (SmallVectorImpl<BasicBlock *>::iterator I = CSEWorkList.begin(),
1821                                                E = CSEWorkList.end();
1822        I != E; ++I) {
1823     assert((I == CSEWorkList.begin() || !DT->dominates(*I, *std::prev(I))) &&
1824            "Worklist not sorted properly!");
1825     BasicBlock *BB = *I;
1826     // For all instructions in blocks containing gather sequences:
1827     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e;) {
1828       Instruction *In = it++;
1829       if (!isa<InsertElementInst>(In) && !isa<ExtractElementInst>(In))
1830         continue;
1831
1832       // Check if we can replace this instruction with any of the
1833       // visited instructions.
1834       for (SmallVectorImpl<Instruction *>::iterator v = Visited.begin(),
1835                                                     ve = Visited.end();
1836            v != ve; ++v) {
1837         if (In->isIdenticalTo(*v) &&
1838             DT->dominates((*v)->getParent(), In->getParent())) {
1839           In->replaceAllUsesWith(*v);
1840           In->eraseFromParent();
1841           In = nullptr;
1842           break;
1843         }
1844       }
1845       if (In) {
1846         assert(std::find(Visited.begin(), Visited.end(), In) == Visited.end());
1847         Visited.push_back(In);
1848       }
1849     }
1850   }
1851   CSEBlocks.clear();
1852   GatherSeq.clear();
1853 }
1854
1855 /// The SLPVectorizer Pass.
1856 struct SLPVectorizer : public FunctionPass {
1857   typedef SmallVector<StoreInst *, 8> StoreList;
1858   typedef MapVector<Value *, StoreList> StoreListMap;
1859
1860   /// Pass identification, replacement for typeid
1861   static char ID;
1862
1863   explicit SLPVectorizer() : FunctionPass(ID) {
1864     initializeSLPVectorizerPass(*PassRegistry::getPassRegistry());
1865   }
1866
1867   ScalarEvolution *SE;
1868   const DataLayout *DL;
1869   TargetTransformInfo *TTI;
1870   TargetLibraryInfo *TLI;
1871   AliasAnalysis *AA;
1872   LoopInfo *LI;
1873   DominatorTree *DT;
1874
1875   bool runOnFunction(Function &F) override {
1876     if (skipOptnoneFunction(F))
1877       return false;
1878
1879     SE = &getAnalysis<ScalarEvolution>();
1880     DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
1881     DL = DLP ? &DLP->getDataLayout() : nullptr;
1882     TTI = &getAnalysis<TargetTransformInfo>();
1883     TLI = getAnalysisIfAvailable<TargetLibraryInfo>();
1884     AA = &getAnalysis<AliasAnalysis>();
1885     LI = &getAnalysis<LoopInfo>();
1886     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1887
1888     StoreRefs.clear();
1889     bool Changed = false;
1890
1891     // If the target claims to have no vector registers don't attempt
1892     // vectorization.
1893     if (!TTI->getNumberOfRegisters(true))
1894       return false;
1895
1896     // Must have DataLayout. We can't require it because some tests run w/o
1897     // triple.
1898     if (!DL)
1899       return false;
1900
1901     // Don't vectorize when the attribute NoImplicitFloat is used.
1902     if (F.hasFnAttribute(Attribute::NoImplicitFloat))
1903       return false;
1904
1905     DEBUG(dbgs() << "SLP: Analyzing blocks in " << F.getName() << ".\n");
1906
1907     // Use the bottom up slp vectorizer to construct chains that start with
1908     // he store instructions.
1909     BoUpSLP R(&F, SE, DL, TTI, TLI, AA, LI, DT);
1910
1911     // Scan the blocks in the function in post order.
1912     for (po_iterator<BasicBlock*> it = po_begin(&F.getEntryBlock()),
1913          e = po_end(&F.getEntryBlock()); it != e; ++it) {
1914       BasicBlock *BB = *it;
1915
1916       // Vectorize trees that end at stores.
1917       if (unsigned count = collectStores(BB, R)) {
1918         (void)count;
1919         DEBUG(dbgs() << "SLP: Found " << count << " stores to vectorize.\n");
1920         Changed |= vectorizeStoreChains(R);
1921       }
1922
1923       // Vectorize trees that end at reductions.
1924       Changed |= vectorizeChainsInBlock(BB, R);
1925     }
1926
1927     if (Changed) {
1928       R.optimizeGatherSequence();
1929       DEBUG(dbgs() << "SLP: vectorized \"" << F.getName() << "\"\n");
1930       DEBUG(verifyFunction(F));
1931     }
1932     return Changed;
1933   }
1934
1935   void getAnalysisUsage(AnalysisUsage &AU) const override {
1936     FunctionPass::getAnalysisUsage(AU);
1937     AU.addRequired<ScalarEvolution>();
1938     AU.addRequired<AliasAnalysis>();
1939     AU.addRequired<TargetTransformInfo>();
1940     AU.addRequired<LoopInfo>();
1941     AU.addRequired<DominatorTreeWrapperPass>();
1942     AU.addPreserved<LoopInfo>();
1943     AU.addPreserved<DominatorTreeWrapperPass>();
1944     AU.setPreservesCFG();
1945   }
1946
1947 private:
1948
1949   /// \brief Collect memory references and sort them according to their base
1950   /// object. We sort the stores to their base objects to reduce the cost of the
1951   /// quadratic search on the stores. TODO: We can further reduce this cost
1952   /// if we flush the chain creation every time we run into a memory barrier.
1953   unsigned collectStores(BasicBlock *BB, BoUpSLP &R);
1954
1955   /// \brief Try to vectorize a chain that starts at two arithmetic instrs.
1956   bool tryToVectorizePair(Value *A, Value *B, BoUpSLP &R);
1957
1958   /// \brief Try to vectorize a list of operands.
1959   /// \returns true if a value was vectorized.
1960   bool tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R);
1961
1962   /// \brief Try to vectorize a chain that may start at the operands of \V;
1963   bool tryToVectorize(BinaryOperator *V, BoUpSLP &R);
1964
1965   /// \brief Vectorize the stores that were collected in StoreRefs.
1966   bool vectorizeStoreChains(BoUpSLP &R);
1967
1968   /// \brief Scan the basic block and look for patterns that are likely to start
1969   /// a vectorization chain.
1970   bool vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R);
1971
1972   bool vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold,
1973                            BoUpSLP &R);
1974
1975   bool vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold,
1976                        BoUpSLP &R);
1977 private:
1978   StoreListMap StoreRefs;
1979 };
1980
1981 /// \brief Check that the Values in the slice in VL array are still existent in
1982 /// the WeakVH array.
1983 /// Vectorization of part of the VL array may cause later values in the VL array
1984 /// to become invalid. We track when this has happened in the WeakVH array.
1985 static bool hasValueBeenRAUWed(ArrayRef<Value *> &VL,
1986                                SmallVectorImpl<WeakVH> &VH,
1987                                unsigned SliceBegin,
1988                                unsigned SliceSize) {
1989   for (unsigned i = SliceBegin; i < SliceBegin + SliceSize; ++i)
1990     if (VH[i] != VL[i])
1991       return true;
1992
1993   return false;
1994 }
1995
1996 bool SLPVectorizer::vectorizeStoreChain(ArrayRef<Value *> Chain,
1997                                           int CostThreshold, BoUpSLP &R) {
1998   unsigned ChainLen = Chain.size();
1999   DEBUG(dbgs() << "SLP: Analyzing a store chain of length " << ChainLen
2000         << "\n");
2001   Type *StoreTy = cast<StoreInst>(Chain[0])->getValueOperand()->getType();
2002   unsigned Sz = DL->getTypeSizeInBits(StoreTy);
2003   unsigned VF = MinVecRegSize / Sz;
2004
2005   if (!isPowerOf2_32(Sz) || VF < 2)
2006     return false;
2007
2008   // Keep track of values that were deleted by vectorizing in the loop below.
2009   SmallVector<WeakVH, 8> TrackValues(Chain.begin(), Chain.end());
2010
2011   bool Changed = false;
2012   // Look for profitable vectorizable trees at all offsets, starting at zero.
2013   for (unsigned i = 0, e = ChainLen; i < e; ++i) {
2014     if (i + VF > e)
2015       break;
2016
2017     // Check that a previous iteration of this loop did not delete the Value.
2018     if (hasValueBeenRAUWed(Chain, TrackValues, i, VF))
2019       continue;
2020
2021     DEBUG(dbgs() << "SLP: Analyzing " << VF << " stores at offset " << i
2022           << "\n");
2023     ArrayRef<Value *> Operands = Chain.slice(i, VF);
2024
2025     R.buildTree(Operands);
2026
2027     int Cost = R.getTreeCost();
2028
2029     DEBUG(dbgs() << "SLP: Found cost=" << Cost << " for VF=" << VF << "\n");
2030     if (Cost < CostThreshold) {
2031       DEBUG(dbgs() << "SLP: Decided to vectorize cost=" << Cost << "\n");
2032       R.vectorizeTree();
2033
2034       // Move to the next bundle.
2035       i += VF - 1;
2036       Changed = true;
2037     }
2038   }
2039
2040   return Changed;
2041 }
2042
2043 bool SLPVectorizer::vectorizeStores(ArrayRef<StoreInst *> Stores,
2044                                     int costThreshold, BoUpSLP &R) {
2045   SetVector<Value *> Heads, Tails;
2046   SmallDenseMap<Value *, Value *> ConsecutiveChain;
2047
2048   // We may run into multiple chains that merge into a single chain. We mark the
2049   // stores that we vectorized so that we don't visit the same store twice.
2050   BoUpSLP::ValueSet VectorizedStores;
2051   bool Changed = false;
2052
2053   // Do a quadratic search on all of the given stores and find
2054   // all of the pairs of stores that follow each other.
2055   for (unsigned i = 0, e = Stores.size(); i < e; ++i) {
2056     for (unsigned j = 0; j < e; ++j) {
2057       if (i == j)
2058         continue;
2059
2060       if (R.isConsecutiveAccess(Stores[i], Stores[j])) {
2061         Tails.insert(Stores[j]);
2062         Heads.insert(Stores[i]);
2063         ConsecutiveChain[Stores[i]] = Stores[j];
2064       }
2065     }
2066   }
2067
2068   // For stores that start but don't end a link in the chain:
2069   for (SetVector<Value *>::iterator it = Heads.begin(), e = Heads.end();
2070        it != e; ++it) {
2071     if (Tails.count(*it))
2072       continue;
2073
2074     // We found a store instr that starts a chain. Now follow the chain and try
2075     // to vectorize it.
2076     BoUpSLP::ValueList Operands;
2077     Value *I = *it;
2078     // Collect the chain into a list.
2079     while (Tails.count(I) || Heads.count(I)) {
2080       if (VectorizedStores.count(I))
2081         break;
2082       Operands.push_back(I);
2083       // Move to the next value in the chain.
2084       I = ConsecutiveChain[I];
2085     }
2086
2087     bool Vectorized = vectorizeStoreChain(Operands, costThreshold, R);
2088
2089     // Mark the vectorized stores so that we don't vectorize them again.
2090     if (Vectorized)
2091       VectorizedStores.insert(Operands.begin(), Operands.end());
2092     Changed |= Vectorized;
2093   }
2094
2095   return Changed;
2096 }
2097
2098
2099 unsigned SLPVectorizer::collectStores(BasicBlock *BB, BoUpSLP &R) {
2100   unsigned count = 0;
2101   StoreRefs.clear();
2102   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
2103     StoreInst *SI = dyn_cast<StoreInst>(it);
2104     if (!SI)
2105       continue;
2106
2107     // Don't touch volatile stores.
2108     if (!SI->isSimple())
2109       continue;
2110
2111     // Check that the pointer points to scalars.
2112     Type *Ty = SI->getValueOperand()->getType();
2113     if (Ty->isAggregateType() || Ty->isVectorTy())
2114       continue;
2115
2116     // Find the base pointer.
2117     Value *Ptr = GetUnderlyingObject(SI->getPointerOperand(), DL);
2118
2119     // Save the store locations.
2120     StoreRefs[Ptr].push_back(SI);
2121     count++;
2122   }
2123   return count;
2124 }
2125
2126 bool SLPVectorizer::tryToVectorizePair(Value *A, Value *B, BoUpSLP &R) {
2127   if (!A || !B)
2128     return false;
2129   Value *VL[] = { A, B };
2130   return tryToVectorizeList(VL, R);
2131 }
2132
2133 bool SLPVectorizer::tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R) {
2134   if (VL.size() < 2)
2135     return false;
2136
2137   DEBUG(dbgs() << "SLP: Vectorizing a list of length = " << VL.size() << ".\n");
2138
2139   // Check that all of the parts are scalar instructions of the same type.
2140   Instruction *I0 = dyn_cast<Instruction>(VL[0]);
2141   if (!I0)
2142     return false;
2143
2144   unsigned Opcode0 = I0->getOpcode();
2145
2146   Type *Ty0 = I0->getType();
2147   unsigned Sz = DL->getTypeSizeInBits(Ty0);
2148   unsigned VF = MinVecRegSize / Sz;
2149
2150   for (int i = 0, e = VL.size(); i < e; ++i) {
2151     Type *Ty = VL[i]->getType();
2152     if (Ty->isAggregateType() || Ty->isVectorTy())
2153       return false;
2154     Instruction *Inst = dyn_cast<Instruction>(VL[i]);
2155     if (!Inst || Inst->getOpcode() != Opcode0)
2156       return false;
2157   }
2158
2159   bool Changed = false;
2160
2161   // Keep track of values that were deleted by vectorizing in the loop below.
2162   SmallVector<WeakVH, 8> TrackValues(VL.begin(), VL.end());
2163
2164   for (unsigned i = 0, e = VL.size(); i < e; ++i) {
2165     unsigned OpsWidth = 0;
2166
2167     if (i + VF > e)
2168       OpsWidth = e - i;
2169     else
2170       OpsWidth = VF;
2171
2172     if (!isPowerOf2_32(OpsWidth) || OpsWidth < 2)
2173       break;
2174
2175     // Check that a previous iteration of this loop did not delete the Value.
2176     if (hasValueBeenRAUWed(VL, TrackValues, i, OpsWidth))
2177       continue;
2178
2179     DEBUG(dbgs() << "SLP: Analyzing " << OpsWidth << " operations "
2180                  << "\n");
2181     ArrayRef<Value *> Ops = VL.slice(i, OpsWidth);
2182
2183     R.buildTree(Ops);
2184     int Cost = R.getTreeCost();
2185
2186     if (Cost < -SLPCostThreshold) {
2187       DEBUG(dbgs() << "SLP: Vectorizing list at cost:" << Cost << ".\n");
2188       R.vectorizeTree();
2189
2190       // Move to the next bundle.
2191       i += VF - 1;
2192       Changed = true;
2193     }
2194   }
2195
2196   return Changed;
2197 }
2198
2199 bool SLPVectorizer::tryToVectorize(BinaryOperator *V, BoUpSLP &R) {
2200   if (!V)
2201     return false;
2202
2203   // Try to vectorize V.
2204   if (tryToVectorizePair(V->getOperand(0), V->getOperand(1), R))
2205     return true;
2206
2207   BinaryOperator *A = dyn_cast<BinaryOperator>(V->getOperand(0));
2208   BinaryOperator *B = dyn_cast<BinaryOperator>(V->getOperand(1));
2209   // Try to skip B.
2210   if (B && B->hasOneUse()) {
2211     BinaryOperator *B0 = dyn_cast<BinaryOperator>(B->getOperand(0));
2212     BinaryOperator *B1 = dyn_cast<BinaryOperator>(B->getOperand(1));
2213     if (tryToVectorizePair(A, B0, R)) {
2214       B->moveBefore(V);
2215       return true;
2216     }
2217     if (tryToVectorizePair(A, B1, R)) {
2218       B->moveBefore(V);
2219       return true;
2220     }
2221   }
2222
2223   // Try to skip A.
2224   if (A && A->hasOneUse()) {
2225     BinaryOperator *A0 = dyn_cast<BinaryOperator>(A->getOperand(0));
2226     BinaryOperator *A1 = dyn_cast<BinaryOperator>(A->getOperand(1));
2227     if (tryToVectorizePair(A0, B, R)) {
2228       A->moveBefore(V);
2229       return true;
2230     }
2231     if (tryToVectorizePair(A1, B, R)) {
2232       A->moveBefore(V);
2233       return true;
2234     }
2235   }
2236   return 0;
2237 }
2238
2239 /// \brief Generate a shuffle mask to be used in a reduction tree.
2240 ///
2241 /// \param VecLen The length of the vector to be reduced.
2242 /// \param NumEltsToRdx The number of elements that should be reduced in the
2243 ///        vector.
2244 /// \param IsPairwise Whether the reduction is a pairwise or splitting
2245 ///        reduction. A pairwise reduction will generate a mask of
2246 ///        <0,2,...> or <1,3,..> while a splitting reduction will generate
2247 ///        <2,3, undef,undef> for a vector of 4 and NumElts = 2.
2248 /// \param IsLeft True will generate a mask of even elements, odd otherwise.
2249 static Value *createRdxShuffleMask(unsigned VecLen, unsigned NumEltsToRdx,
2250                                    bool IsPairwise, bool IsLeft,
2251                                    IRBuilder<> &Builder) {
2252   assert((IsPairwise || !IsLeft) && "Don't support a <0,1,undef,...> mask");
2253
2254   SmallVector<Constant *, 32> ShuffleMask(
2255       VecLen, UndefValue::get(Builder.getInt32Ty()));
2256
2257   if (IsPairwise)
2258     // Build a mask of 0, 2, ... (left) or 1, 3, ... (right).
2259     for (unsigned i = 0; i != NumEltsToRdx; ++i)
2260       ShuffleMask[i] = Builder.getInt32(2 * i + !IsLeft);
2261   else
2262     // Move the upper half of the vector to the lower half.
2263     for (unsigned i = 0; i != NumEltsToRdx; ++i)
2264       ShuffleMask[i] = Builder.getInt32(NumEltsToRdx + i);
2265
2266   return ConstantVector::get(ShuffleMask);
2267 }
2268
2269
2270 /// Model horizontal reductions.
2271 ///
2272 /// A horizontal reduction is a tree of reduction operations (currently add and
2273 /// fadd) that has operations that can be put into a vector as its leaf.
2274 /// For example, this tree:
2275 ///
2276 /// mul mul mul mul
2277 ///  \  /    \  /
2278 ///   +       +
2279 ///    \     /
2280 ///       +
2281 /// This tree has "mul" as its reduced values and "+" as its reduction
2282 /// operations. A reduction might be feeding into a store or a binary operation
2283 /// feeding a phi.
2284 ///    ...
2285 ///    \  /
2286 ///     +
2287 ///     |
2288 ///  phi +=
2289 ///
2290 ///  Or:
2291 ///    ...
2292 ///    \  /
2293 ///     +
2294 ///     |
2295 ///   *p =
2296 ///
2297 class HorizontalReduction {
2298   SmallPtrSet<Value *, 16> ReductionOps;
2299   SmallVector<Value *, 32> ReducedVals;
2300
2301   BinaryOperator *ReductionRoot;
2302   PHINode *ReductionPHI;
2303
2304   /// The opcode of the reduction.
2305   unsigned ReductionOpcode;
2306   /// The opcode of the values we perform a reduction on.
2307   unsigned ReducedValueOpcode;
2308   /// The width of one full horizontal reduction operation.
2309   unsigned ReduxWidth;
2310   /// Should we model this reduction as a pairwise reduction tree or a tree that
2311   /// splits the vector in halves and adds those halves.
2312   bool IsPairwiseReduction;
2313
2314 public:
2315   HorizontalReduction()
2316     : ReductionRoot(nullptr), ReductionPHI(nullptr), ReductionOpcode(0),
2317     ReducedValueOpcode(0), ReduxWidth(0), IsPairwiseReduction(false) {}
2318
2319   /// \brief Try to find a reduction tree.
2320   bool matchAssociativeReduction(PHINode *Phi, BinaryOperator *B,
2321                                  const DataLayout *DL) {
2322     assert((!Phi ||
2323             std::find(Phi->op_begin(), Phi->op_end(), B) != Phi->op_end()) &&
2324            "Thi phi needs to use the binary operator");
2325
2326     // We could have a initial reductions that is not an add.
2327     //  r *= v1 + v2 + v3 + v4
2328     // In such a case start looking for a tree rooted in the first '+'.
2329     if (Phi) {
2330       if (B->getOperand(0) == Phi) {
2331         Phi = nullptr;
2332         B = dyn_cast<BinaryOperator>(B->getOperand(1));
2333       } else if (B->getOperand(1) == Phi) {
2334         Phi = nullptr;
2335         B = dyn_cast<BinaryOperator>(B->getOperand(0));
2336       }
2337     }
2338
2339     if (!B)
2340       return false;
2341
2342     Type *Ty = B->getType();
2343     if (Ty->isVectorTy())
2344       return false;
2345
2346     ReductionOpcode = B->getOpcode();
2347     ReducedValueOpcode = 0;
2348     ReduxWidth = MinVecRegSize / DL->getTypeSizeInBits(Ty);
2349     ReductionRoot = B;
2350     ReductionPHI = Phi;
2351
2352     if (ReduxWidth < 4)
2353       return false;
2354
2355     // We currently only support adds.
2356     if (ReductionOpcode != Instruction::Add &&
2357         ReductionOpcode != Instruction::FAdd)
2358       return false;
2359
2360     // Post order traverse the reduction tree starting at B. We only handle true
2361     // trees containing only binary operators.
2362     SmallVector<std::pair<BinaryOperator *, unsigned>, 32> Stack;
2363     Stack.push_back(std::make_pair(B, 0));
2364     while (!Stack.empty()) {
2365       BinaryOperator *TreeN = Stack.back().first;
2366       unsigned EdgeToVist = Stack.back().second++;
2367       bool IsReducedValue = TreeN->getOpcode() != ReductionOpcode;
2368
2369       // Only handle trees in the current basic block.
2370       if (TreeN->getParent() != B->getParent())
2371         return false;
2372
2373       // Each tree node needs to have one user except for the ultimate
2374       // reduction.
2375       if (!TreeN->hasOneUse() && TreeN != B)
2376         return false;
2377
2378       // Postorder vist.
2379       if (EdgeToVist == 2 || IsReducedValue) {
2380         if (IsReducedValue) {
2381           // Make sure that the opcodes of the operations that we are going to
2382           // reduce match.
2383           if (!ReducedValueOpcode)
2384             ReducedValueOpcode = TreeN->getOpcode();
2385           else if (ReducedValueOpcode != TreeN->getOpcode())
2386             return false;
2387           ReducedVals.push_back(TreeN);
2388         } else {
2389           // We need to be able to reassociate the adds.
2390           if (!TreeN->isAssociative())
2391             return false;
2392           ReductionOps.insert(TreeN);
2393         }
2394         // Retract.
2395         Stack.pop_back();
2396         continue;
2397       }
2398
2399       // Visit left or right.
2400       Value *NextV = TreeN->getOperand(EdgeToVist);
2401       BinaryOperator *Next = dyn_cast<BinaryOperator>(NextV);
2402       if (Next)
2403         Stack.push_back(std::make_pair(Next, 0));
2404       else if (NextV != Phi)
2405         return false;
2406     }
2407     return true;
2408   }
2409
2410   /// \brief Attempt to vectorize the tree found by
2411   /// matchAssociativeReduction.
2412   bool tryToReduce(BoUpSLP &V, TargetTransformInfo *TTI) {
2413     if (ReducedVals.empty())
2414       return false;
2415
2416     unsigned NumReducedVals = ReducedVals.size();
2417     if (NumReducedVals < ReduxWidth)
2418       return false;
2419
2420     Value *VectorizedTree = nullptr;
2421     IRBuilder<> Builder(ReductionRoot);
2422     FastMathFlags Unsafe;
2423     Unsafe.setUnsafeAlgebra();
2424     Builder.SetFastMathFlags(Unsafe);
2425     unsigned i = 0;
2426
2427     for (; i < NumReducedVals - ReduxWidth + 1; i += ReduxWidth) {
2428       ArrayRef<Value *> ValsToReduce(&ReducedVals[i], ReduxWidth);
2429       V.buildTree(ValsToReduce, &ReductionOps);
2430
2431       // Estimate cost.
2432       int Cost = V.getTreeCost() + getReductionCost(TTI, ReducedVals[i]);
2433       if (Cost >= -SLPCostThreshold)
2434         break;
2435
2436       DEBUG(dbgs() << "SLP: Vectorizing horizontal reduction at cost:" << Cost
2437                    << ". (HorRdx)\n");
2438
2439       // Vectorize a tree.
2440       DebugLoc Loc = cast<Instruction>(ReducedVals[i])->getDebugLoc();
2441       Value *VectorizedRoot = V.vectorizeTree();
2442
2443       // Emit a reduction.
2444       Value *ReducedSubTree = emitReduction(VectorizedRoot, Builder);
2445       if (VectorizedTree) {
2446         Builder.SetCurrentDebugLocation(Loc);
2447         VectorizedTree = createBinOp(Builder, ReductionOpcode, VectorizedTree,
2448                                      ReducedSubTree, "bin.rdx");
2449       } else
2450         VectorizedTree = ReducedSubTree;
2451     }
2452
2453     if (VectorizedTree) {
2454       // Finish the reduction.
2455       for (; i < NumReducedVals; ++i) {
2456         Builder.SetCurrentDebugLocation(
2457           cast<Instruction>(ReducedVals[i])->getDebugLoc());
2458         VectorizedTree = createBinOp(Builder, ReductionOpcode, VectorizedTree,
2459                                      ReducedVals[i]);
2460       }
2461       // Update users.
2462       if (ReductionPHI) {
2463         assert(ReductionRoot && "Need a reduction operation");
2464         ReductionRoot->setOperand(0, VectorizedTree);
2465         ReductionRoot->setOperand(1, ReductionPHI);
2466       } else
2467         ReductionRoot->replaceAllUsesWith(VectorizedTree);
2468     }
2469     return VectorizedTree != nullptr;
2470   }
2471
2472 private:
2473
2474   /// \brief Calcuate the cost of a reduction.
2475   int getReductionCost(TargetTransformInfo *TTI, Value *FirstReducedVal) {
2476     Type *ScalarTy = FirstReducedVal->getType();
2477     Type *VecTy = VectorType::get(ScalarTy, ReduxWidth);
2478
2479     int PairwiseRdxCost = TTI->getReductionCost(ReductionOpcode, VecTy, true);
2480     int SplittingRdxCost = TTI->getReductionCost(ReductionOpcode, VecTy, false);
2481
2482     IsPairwiseReduction = PairwiseRdxCost < SplittingRdxCost;
2483     int VecReduxCost = IsPairwiseReduction ? PairwiseRdxCost : SplittingRdxCost;
2484
2485     int ScalarReduxCost =
2486         ReduxWidth * TTI->getArithmeticInstrCost(ReductionOpcode, VecTy);
2487
2488     DEBUG(dbgs() << "SLP: Adding cost " << VecReduxCost - ScalarReduxCost
2489                  << " for reduction that starts with " << *FirstReducedVal
2490                  << " (It is a "
2491                  << (IsPairwiseReduction ? "pairwise" : "splitting")
2492                  << " reduction)\n");
2493
2494     return VecReduxCost - ScalarReduxCost;
2495   }
2496
2497   static Value *createBinOp(IRBuilder<> &Builder, unsigned Opcode, Value *L,
2498                             Value *R, const Twine &Name = "") {
2499     if (Opcode == Instruction::FAdd)
2500       return Builder.CreateFAdd(L, R, Name);
2501     return Builder.CreateBinOp((Instruction::BinaryOps)Opcode, L, R, Name);
2502   }
2503
2504   /// \brief Emit a horizontal reduction of the vectorized value.
2505   Value *emitReduction(Value *VectorizedValue, IRBuilder<> &Builder) {
2506     assert(VectorizedValue && "Need to have a vectorized tree node");
2507     Instruction *ValToReduce = dyn_cast<Instruction>(VectorizedValue);
2508     assert(isPowerOf2_32(ReduxWidth) &&
2509            "We only handle power-of-two reductions for now");
2510
2511     Value *TmpVec = ValToReduce;
2512     for (unsigned i = ReduxWidth / 2; i != 0; i >>= 1) {
2513       if (IsPairwiseReduction) {
2514         Value *LeftMask =
2515           createRdxShuffleMask(ReduxWidth, i, true, true, Builder);
2516         Value *RightMask =
2517           createRdxShuffleMask(ReduxWidth, i, true, false, Builder);
2518
2519         Value *LeftShuf = Builder.CreateShuffleVector(
2520           TmpVec, UndefValue::get(TmpVec->getType()), LeftMask, "rdx.shuf.l");
2521         Value *RightShuf = Builder.CreateShuffleVector(
2522           TmpVec, UndefValue::get(TmpVec->getType()), (RightMask),
2523           "rdx.shuf.r");
2524         TmpVec = createBinOp(Builder, ReductionOpcode, LeftShuf, RightShuf,
2525                              "bin.rdx");
2526       } else {
2527         Value *UpperHalf =
2528           createRdxShuffleMask(ReduxWidth, i, false, false, Builder);
2529         Value *Shuf = Builder.CreateShuffleVector(
2530           TmpVec, UndefValue::get(TmpVec->getType()), UpperHalf, "rdx.shuf");
2531         TmpVec = createBinOp(Builder, ReductionOpcode, TmpVec, Shuf, "bin.rdx");
2532       }
2533     }
2534
2535     // The result is in the first element of the vector.
2536     return Builder.CreateExtractElement(TmpVec, Builder.getInt32(0));
2537   }
2538 };
2539
2540 /// \brief Recognize construction of vectors like
2541 ///  %ra = insertelement <4 x float> undef, float %s0, i32 0
2542 ///  %rb = insertelement <4 x float> %ra, float %s1, i32 1
2543 ///  %rc = insertelement <4 x float> %rb, float %s2, i32 2
2544 ///  %rd = insertelement <4 x float> %rc, float %s3, i32 3
2545 ///
2546 /// Returns true if it matches
2547 ///
2548 static bool findBuildVector(InsertElementInst *IE,
2549                             SmallVectorImpl<Value *> &Ops) {
2550   if (!isa<UndefValue>(IE->getOperand(0)))
2551     return false;
2552
2553   while (true) {
2554     Ops.push_back(IE->getOperand(1));
2555
2556     if (IE->use_empty())
2557       return false;
2558
2559     InsertElementInst *NextUse = dyn_cast<InsertElementInst>(IE->user_back());
2560     if (!NextUse)
2561       return true;
2562
2563     // If this isn't the final use, make sure the next insertelement is the only
2564     // use. It's OK if the final constructed vector is used multiple times
2565     if (!IE->hasOneUse())
2566       return false;
2567
2568     IE = NextUse;
2569   }
2570
2571   return false;
2572 }
2573
2574 static bool PhiTypeSorterFunc(Value *V, Value *V2) {
2575   return V->getType() < V2->getType();
2576 }
2577
2578 bool SLPVectorizer::vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R) {
2579   bool Changed = false;
2580   SmallVector<Value *, 4> Incoming;
2581   SmallSet<Value *, 16> VisitedInstrs;
2582
2583   bool HaveVectorizedPhiNodes = true;
2584   while (HaveVectorizedPhiNodes) {
2585     HaveVectorizedPhiNodes = false;
2586
2587     // Collect the incoming values from the PHIs.
2588     Incoming.clear();
2589     for (BasicBlock::iterator instr = BB->begin(), ie = BB->end(); instr != ie;
2590          ++instr) {
2591       PHINode *P = dyn_cast<PHINode>(instr);
2592       if (!P)
2593         break;
2594
2595       if (!VisitedInstrs.count(P))
2596         Incoming.push_back(P);
2597     }
2598
2599     // Sort by type.
2600     std::stable_sort(Incoming.begin(), Incoming.end(), PhiTypeSorterFunc);
2601
2602     // Try to vectorize elements base on their type.
2603     for (SmallVector<Value *, 4>::iterator IncIt = Incoming.begin(),
2604                                            E = Incoming.end();
2605          IncIt != E;) {
2606
2607       // Look for the next elements with the same type.
2608       SmallVector<Value *, 4>::iterator SameTypeIt = IncIt;
2609       while (SameTypeIt != E &&
2610              (*SameTypeIt)->getType() == (*IncIt)->getType()) {
2611         VisitedInstrs.insert(*SameTypeIt);
2612         ++SameTypeIt;
2613       }
2614
2615       // Try to vectorize them.
2616       unsigned NumElts = (SameTypeIt - IncIt);
2617       DEBUG(errs() << "SLP: Trying to vectorize starting at PHIs (" << NumElts << ")\n");
2618       if (NumElts > 1 &&
2619           tryToVectorizeList(ArrayRef<Value *>(IncIt, NumElts), R)) {
2620         // Success start over because instructions might have been changed.
2621         HaveVectorizedPhiNodes = true;
2622         Changed = true;
2623         break;
2624       }
2625
2626       // Start over at the next instruction of a different type (or the end).
2627       IncIt = SameTypeIt;
2628     }
2629   }
2630
2631   VisitedInstrs.clear();
2632
2633   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; it++) {
2634     // We may go through BB multiple times so skip the one we have checked.
2635     if (!VisitedInstrs.insert(it))
2636       continue;
2637
2638     if (isa<DbgInfoIntrinsic>(it))
2639       continue;
2640
2641     // Try to vectorize reductions that use PHINodes.
2642     if (PHINode *P = dyn_cast<PHINode>(it)) {
2643       // Check that the PHI is a reduction PHI.
2644       if (P->getNumIncomingValues() != 2)
2645         return Changed;
2646       Value *Rdx =
2647           (P->getIncomingBlock(0) == BB
2648                ? (P->getIncomingValue(0))
2649                : (P->getIncomingBlock(1) == BB ? P->getIncomingValue(1)
2650                                                : nullptr));
2651       // Check if this is a Binary Operator.
2652       BinaryOperator *BI = dyn_cast_or_null<BinaryOperator>(Rdx);
2653       if (!BI)
2654         continue;
2655
2656       // Try to match and vectorize a horizontal reduction.
2657       HorizontalReduction HorRdx;
2658       if (ShouldVectorizeHor &&
2659           HorRdx.matchAssociativeReduction(P, BI, DL) &&
2660           HorRdx.tryToReduce(R, TTI)) {
2661         Changed = true;
2662         it = BB->begin();
2663         e = BB->end();
2664         continue;
2665       }
2666
2667      Value *Inst = BI->getOperand(0);
2668       if (Inst == P)
2669         Inst = BI->getOperand(1);
2670
2671       if (tryToVectorize(dyn_cast<BinaryOperator>(Inst), R)) {
2672         // We would like to start over since some instructions are deleted
2673         // and the iterator may become invalid value.
2674         Changed = true;
2675         it = BB->begin();
2676         e = BB->end();
2677         continue;
2678       }
2679
2680       continue;
2681     }
2682
2683     // Try to vectorize horizontal reductions feeding into a store.
2684     if (ShouldStartVectorizeHorAtStore)
2685       if (StoreInst *SI = dyn_cast<StoreInst>(it))
2686         if (BinaryOperator *BinOp =
2687                 dyn_cast<BinaryOperator>(SI->getValueOperand())) {
2688           HorizontalReduction HorRdx;
2689           if (((HorRdx.matchAssociativeReduction(nullptr, BinOp, DL) &&
2690                 HorRdx.tryToReduce(R, TTI)) ||
2691                tryToVectorize(BinOp, R))) {
2692             Changed = true;
2693             it = BB->begin();
2694             e = BB->end();
2695             continue;
2696           }
2697         }
2698
2699     // Try to vectorize trees that start at compare instructions.
2700     if (CmpInst *CI = dyn_cast<CmpInst>(it)) {
2701       if (tryToVectorizePair(CI->getOperand(0), CI->getOperand(1), R)) {
2702         Changed = true;
2703         // We would like to start over since some instructions are deleted
2704         // and the iterator may become invalid value.
2705         it = BB->begin();
2706         e = BB->end();
2707         continue;
2708       }
2709
2710       for (int i = 0; i < 2; ++i) {
2711          if (BinaryOperator *BI = dyn_cast<BinaryOperator>(CI->getOperand(i))) {
2712             if (tryToVectorizePair(BI->getOperand(0), BI->getOperand(1), R)) {
2713               Changed = true;
2714               // We would like to start over since some instructions are deleted
2715               // and the iterator may become invalid value.
2716               it = BB->begin();
2717               e = BB->end();
2718             }
2719          }
2720       }
2721       continue;
2722     }
2723
2724     // Try to vectorize trees that start at insertelement instructions.
2725     if (InsertElementInst *IE = dyn_cast<InsertElementInst>(it)) {
2726       SmallVector<Value *, 8> Ops;
2727       if (!findBuildVector(IE, Ops))
2728         continue;
2729
2730       if (tryToVectorizeList(Ops, R)) {
2731         Changed = true;
2732         it = BB->begin();
2733         e = BB->end();
2734       }
2735
2736       continue;
2737     }
2738   }
2739
2740   return Changed;
2741 }
2742
2743 bool SLPVectorizer::vectorizeStoreChains(BoUpSLP &R) {
2744   bool Changed = false;
2745   // Attempt to sort and vectorize each of the store-groups.
2746   for (StoreListMap::iterator it = StoreRefs.begin(), e = StoreRefs.end();
2747        it != e; ++it) {
2748     if (it->second.size() < 2)
2749       continue;
2750
2751     DEBUG(dbgs() << "SLP: Analyzing a store chain of length "
2752           << it->second.size() << ".\n");
2753
2754     // Process the stores in chunks of 16.
2755     for (unsigned CI = 0, CE = it->second.size(); CI < CE; CI+=16) {
2756       unsigned Len = std::min<unsigned>(CE - CI, 16);
2757       ArrayRef<StoreInst *> Chunk(&it->second[CI], Len);
2758       Changed |= vectorizeStores(Chunk, -SLPCostThreshold, R);
2759     }
2760   }
2761   return Changed;
2762 }
2763
2764 } // end anonymous namespace
2765
2766 char SLPVectorizer::ID = 0;
2767 static const char lv_name[] = "SLP Vectorizer";
2768 INITIALIZE_PASS_BEGIN(SLPVectorizer, SV_NAME, lv_name, false, false)
2769 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
2770 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
2771 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
2772 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
2773 INITIALIZE_PASS_END(SLPVectorizer, SV_NAME, lv_name, false, false)
2774
2775 namespace llvm {
2776 Pass *createSLPVectorizerPass() { return new SLPVectorizer(); }
2777 }