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