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