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/AliasAnalysis.h"
  29 #include "llvm/Analysis/TargetTransformInfo.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 namespace {
  53
  54 static const unsigned MinVecRegSize = 128;
  55
  56 static const unsigned RecursionMaxDepth = 12;
  57
  58 /// RAII pattern to save the insertion point of the IR builder.
  59 class BuilderLocGuard {
  60 public:
  61   BuilderLocGuard(IRBuilder<> &B) : Builder(B), Loc(B.GetInsertPoint()) {}
  62   ~BuilderLocGuard() { if (Loc) Builder.SetInsertPoint(Loc); }
  63
  64 private:
  65   // Prevent copying.
  66   BuilderLocGuard(const BuilderLocGuard &);
  67   BuilderLocGuard &operator=(const BuilderLocGuard &);
  68   IRBuilder<> &Builder;
  69   BasicBlock::iterator Loc;
  70 };
  71
  72 /// A helper class for numbering instructions in multible blocks.
  73 /// Numbers starts at zero for each basic block.
  74 struct BlockNumbering {
  75
  76   BlockNumbering(BasicBlock *Bb) : BB(Bb), Valid(false) {}
  77
  78   BlockNumbering() : BB(0), Valid(false) {}
  79
  80   void numberInstructions() {
  81     unsigned Loc = 0;
  82     InstrIdx.clear();
  83     InstrVec.clear();
  84     // Number the instructions in the block.
  85     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
  86       InstrIdx[it] = Loc++;
  87       InstrVec.push_back(it);
  88       assert(InstrVec[InstrIdx[it]] == it && "Invalid allocation");
  89     }
  90     Valid = true;
  91   }
  92
  93   int getIndex(Instruction *I) {
  94     assert(I->getParent() == BB && "Invalid instruction");
  95     if (!Valid)
  96       numberInstructions();
  97     assert(InstrIdx.count(I) && "Unknown instruction");
  98     return InstrIdx[I];
  99   }
 100
 101   Instruction *getInstruction(unsigned loc) {
 102     if (!Valid)
 103       numberInstructions();
 104     assert(InstrVec.size() > loc && "Invalid Index");
 105     return InstrVec[loc];
 106   }
 107
 108   void forget() { Valid = false; }
 109
 110 private:
 111   /// The block we are numbering.
 112   BasicBlock *BB;
 113   /// Is the block numbered.
 114   bool Valid;
 115   /// Maps instructions to numbers and back.
 116   SmallDenseMap<Instruction *, int> InstrIdx;
 117   /// Maps integers to Instructions.
 118   std::vector<Instruction *> InstrVec;
 119 };
 120
 121 /// \returns the parent basic block if all of the instructions in \p VL
 122 /// are in the same block or null otherwise.
 123 static BasicBlock *getSameBlock(ArrayRef<Value *> VL) {
 124   Instruction *I0 = dyn_cast<Instruction>(VL[0]);
 125   if (!I0)
 126     return 0;
 127   BasicBlock *BB = I0->getParent();
 128   for (int i = 1, e = VL.size(); i < e; i++) {
 129     Instruction *I = dyn_cast<Instruction>(VL[i]);
 130     if (!I)
 131       return 0;
 132
 133     if (BB != I->getParent())
 134       return 0;
 135   }
 136   return BB;
 137 }
 138
 139 /// \returns True if all of the values in \p VL are constants.
 140 static bool allConstant(ArrayRef<Value *> VL) {
 141   for (unsigned i = 0, e = VL.size(); i < e; ++i)
 142     if (!isa<Constant>(VL[i]))
 143       return false;
 144   return true;
 145 }
 146
 147 /// \returns True if all of the values in \p VL are identical.
 148 static bool isSplat(ArrayRef<Value *> VL) {
 149   for (unsigned i = 1, e = VL.size(); i < e; ++i)
 150     if (VL[i] != VL[0])
 151       return false;
 152   return true;
 153 }
 154
 155 /// \returns The opcode if all of the Instructions in \p VL have the same
 156 /// opcode, or zero.
 157 static unsigned getSameOpcode(ArrayRef<Value *> VL) {
 158   Instruction *I0 = dyn_cast<Instruction>(VL[0]);
 159   if (!I0)
 160     return 0;
 161   unsigned Opcode = I0->getOpcode();
 162   for (int i = 1, e = VL.size(); i < e; i++) {
 163     Instruction *I = dyn_cast<Instruction>(VL[i]);
 164     if (!I || Opcode != I->getOpcode())
 165       return 0;
 166   }
 167   return Opcode;
 168 }
 169
 170 /// \returns The type that all of the values in \p VL have or null if there
 171 /// are different types.
 172 static Type* getSameType(ArrayRef<Value *> VL) {
 173   Type *Ty = VL[0]->getType();
 174   for (int i = 1, e = VL.size(); i < e; i++)
 175     if (VL[0]->getType() != Ty)
 176       return 0;
 177
 178   return Ty;
 179 }
 180
 181 /// \returns True if the ExtractElement instructions in VL can be vectorized
 182 /// to use the original vector.
 183 static bool CanReuseExtract(ArrayRef<Value *> VL) {
 184   assert(Instruction::ExtractElement == getSameOpcode(VL) && "Invalid opcode");
 185   // Check if all of the extracts come from the same vector and from the
 186   // correct offset.
 187   Value *VL0 = VL[0];
 188   ExtractElementInst *E0 = cast<ExtractElementInst>(VL0);
 189   Value *Vec = E0->getOperand(0);
 190
 191   // We have to extract from the same vector type.
 192   unsigned NElts = Vec->getType()->getVectorNumElements();
 193
 194   if (NElts != VL.size())
 195     return false;
 196
 197   // Check that all of the indices extract from the correct offset.
 198   ConstantInt *CI = dyn_cast<ConstantInt>(E0->getOperand(1));
 199   if (!CI || CI->getZExtValue())
 200     return false;
 201
 202   for (unsigned i = 1, e = VL.size(); i < e; ++i) {
 203     ExtractElementInst *E = cast<ExtractElementInst>(VL[i]);
 204     ConstantInt *CI = dyn_cast<ConstantInt>(E->getOperand(1));
 205
 206     if (!CI || CI->getZExtValue() != i || E->getOperand(0) != Vec)
 207       return false;
 208   }
 209
 210   return true;
 211 }
 212
 213 /// Bottom Up SLP Vectorizer.
 214 class BoUpSLP {
 215 public:
 216   typedef SmallVector<Value *, 8> ValueList;
 217   typedef SmallVector<Instruction *, 16> InstrList;
 218   typedef SmallPtrSet<Value *, 16> ValueSet;
 219   typedef SmallVector<StoreInst *, 8> StoreList;
 220
 221   BoUpSLP(Function *Func, ScalarEvolution *Se, DataLayout *Dl,
 222           TargetTransformInfo *Tti, AliasAnalysis *Aa, LoopInfo *Li,
 223           DominatorTree *Dt) :
 224     F(Func), SE(Se), DL(Dl), TTI(Tti), AA(Aa), LI(Li), DT(Dt),
 225     Builder(Se->getContext()) {
 226       // Setup the block numbering utility for all of the blocks in the
 227       // function.
 228       for (Function::iterator it = F->begin(), e = F->end(); it != e; ++it) {
 229         BasicBlock *BB = it;
 230         BlocksNumbers[BB] = BlockNumbering(BB);
 231       }
 232     }
 233
 234   /// \brief Vectorize the tree that starts with the elements in \p VL.
 235   void vectorizeTree();
 236
 237   /// \returns the vectorization cost of the subtree that starts at \p VL.
 238   /// A negative number means that this is profitable.
 239   int getTreeCost();
 240
 241   /// Construct a vectorizable tree that starts at \p Roots.
 242   void buildTree(ArrayRef<Value *> Roots);
 243
 244   /// Clear the internal data structures that are created by 'buildTree'.
 245   void deleteTree() {
 246     VectorizableTree.clear();
 247     ScalarToTreeEntry.clear();
 248     MustGather.clear();
 249     MemBarrierIgnoreList.clear();
 250   }
 251
 252   /// \returns the scalarization cost for this list of values. Assuming that
 253   /// this subtree gets vectorized, we may need to extract the values from the
 254   /// roots. This method calculates the cost of extracting the values.
 255   int getGatherCost(ArrayRef<Value *> VL);
 256
 257   /// \returns true if the memory operations A and B are consecutive.
 258   bool isConsecutiveAccess(Value *A, Value *B);
 259
 260   /// \brief Perform LICM and CSE on the newly generated gather sequences.
 261   void optimizeGatherSequence();
 262 private:
 263   struct TreeEntry;
 264
 265   /// \returns the cost of the vectorizable entry.
 266   int getEntryCost(TreeEntry *E);
 267
 268   /// This is the recursive part of buildTree.
 269   void buildTree_rec(ArrayRef<Value *> Roots, unsigned Depth);
 270
 271   /// Vectorizer a single entry in the tree.
 272   Value *vectorizeTree(TreeEntry *E);
 273
 274   /// Vectorizer a single entry in the tree, starting in \p VL.
 275   Value *vectorizeTree(ArrayRef<Value *> VL);
 276
 277   /// \brief Take the pointer operand from the Load/Store instruction.
 278   /// \returns NULL if this is not a valid Load/Store instruction.
 279   static Value *getPointerOperand(Value *I);
 280
 281   /// \brief Take the address space operand from the Load/Store instruction.
 282   /// \returns -1 if this is not a valid Load/Store instruction.
 283   static unsigned getAddressSpaceOperand(Value *I);
 284
 285   /// \returns the scalarization cost for this type. Scalarization in this
 286   /// context means the creation of vectors from a group of scalars.
 287   int getGatherCost(Type *Ty);
 288
 289   /// \returns the AA location that is being access by the instruction.
 290   AliasAnalysis::Location getLocation(Instruction *I);
 291
 292   /// \brief Checks if it is possible to sink an instruction from
 293   /// \p Src to \p Dst.
 294   /// \returns the pointer to the barrier instruction if we can't sink.
 295   Value *getSinkBarrier(Instruction *Src, Instruction *Dst);
 296
 297   /// \returns the index of the last instrucion in the BB from \p VL.
 298   int getLastIndex(ArrayRef<Value *> VL);
 299
 300   /// \returns the Instrucion in the bundle \p VL.
 301   Instruction *getLastInstruction(ArrayRef<Value *> VL);
 302
 303   /// \returns the Instruction at index \p Index which is in Block \p BB.
 304   Instruction *getInstructionForIndex(unsigned Index, BasicBlock *BB);
 305
 306   /// \returns the index of the first User of \p VL.
 307   int getFirstUserIndex(ArrayRef<Value *> VL);
 308
 309   /// \returns a vector from a collection of scalars in \p VL.
 310   Value *Gather(ArrayRef<Value *> VL, VectorType *Ty);
 311
 312   struct TreeEntry {
 313     TreeEntry() : Scalars(), VectorizedValue(0), LastScalarIndex(0),
 314     NeedToGather(0) {}
 315
 316     /// \returns true if the scalars in VL are equal to this entry.
 317     bool isSame(ArrayRef<Value *> VL) {
 318       assert(VL.size() == Scalars.size() && "Invalid size");
 319       for (int i = 0, e = VL.size(); i != e; ++i)
 320         if (VL[i] != Scalars[i])
 321           return false;
 322       return true;
 323     }
 324
 325     /// A vector of scalars.
 326     ValueList Scalars;
 327
 328     /// The Scalars are vectorized into this value. It is initialized to Null.
 329     Value *VectorizedValue;
 330
 331     /// The index in the basic block of the last scalar.
 332     int LastScalarIndex;
 333
 334     /// Do we need to gather this sequence ?
 335     bool NeedToGather;
 336   };
 337
 338   /// Create a new VectorizableTree entry.
 339   TreeEntry *newTreeEntry(ArrayRef<Value *> VL, bool Vectorized) {
 340     VectorizableTree.push_back(TreeEntry());
 341     int idx = VectorizableTree.size() - 1;
 342     TreeEntry *Last = &VectorizableTree[idx];
 343     Last->Scalars.insert(Last->Scalars.begin(), VL.begin(), VL.end());
 344     Last->NeedToGather = !Vectorized;
 345     if (Vectorized) {
 346       Last->LastScalarIndex = getLastIndex(VL);
 347       for (int i = 0, e = VL.size(); i != e; ++i) {
 348         assert(!ScalarToTreeEntry.count(VL[i]) && "Scalar already in tree!");
 349         ScalarToTreeEntry[VL[i]] = idx;
 350       }
 351     } else {
 352       Last->LastScalarIndex = 0;
 353       MustGather.insert(VL.begin(), VL.end());
 354     }
 355     return Last;
 356   }
 357
 358   /// -- Vectorization State --
 359   /// Holds all of the tree entries.
 360   std::vector<TreeEntry> VectorizableTree;
 361
 362   /// Maps a specific scalar to its tree entry.
 363   SmallDenseMap<Value*, int> ScalarToTreeEntry;
 364
 365   /// A list of scalars that we found that we need to keep as scalars.
 366   ValueSet MustGather;
 367
 368   /// A list of instructions to ignore while sinking
 369   /// memory instructions. This map must be reset between runs of getCost.
 370   ValueSet MemBarrierIgnoreList;
 371
 372   /// Holds all of the instructions that we gathered.
 373   SetVector<Instruction *> GatherSeq;
 374
 375   /// Numbers instructions in different blocks.
 376   std::map<BasicBlock *, BlockNumbering> BlocksNumbers;
 377
 378   // Analysis and block reference.
 379   Function *F;
 380   ScalarEvolution *SE;
 381   DataLayout *DL;
 382   TargetTransformInfo *TTI;
 383   AliasAnalysis *AA;
 384   LoopInfo *LI;
 385   DominatorTree *DT;
 386   /// Instruction builder to construct the vectorized tree.
 387   IRBuilder<> Builder;
 388 };
 389
 390 void BoUpSLP::buildTree(ArrayRef<Value *> Roots) {
 391   deleteTree();
 392   buildTree_rec(Roots, 0);
 393 }
 394
 395
 396 void BoUpSLP::buildTree_rec(ArrayRef<Value *> VL, unsigned Depth) {
 397   bool SameTy = getSameType(VL); (void)SameTy;
 398   assert(SameTy && "Invalid types!");
 399
 400   if (Depth == RecursionMaxDepth) {
 401     DEBUG(dbgs() << "SLP: Gathering due to max recursion depth.\n");
 402     newTreeEntry(VL, false);
 403     return;
 404   }
 405
 406   // Don't handle vectors.
 407   if (VL[0]->getType()->isVectorTy()) {
 408     DEBUG(dbgs() << "SLP: Gathering due to vector type.\n");
 409     newTreeEntry(VL, false);
 410     return;
 411   }
 412
 413   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
 414     if (SI->getValueOperand()->getType()->isVectorTy()) {
 415       DEBUG(dbgs() << "SLP: Gathering due to store vector type.\n");
 416       newTreeEntry(VL, false);
 417       return;
 418     }
 419
 420   // If all of the operands are identical or constant we have a simple solution.
 421   if (allConstant(VL) || isSplat(VL) || !getSameBlock(VL) ||
 422       !getSameOpcode(VL)) {
 423     DEBUG(dbgs() << "SLP: Gathering due to C,S,B,O. \n");
 424     newTreeEntry(VL, false);
 425     return;
 426   }
 427
 428   // We now know that this is a vector of instructions of the same type from
 429   // the same block.
 430
 431   // Check if this is a duplicate of another entry.
 432   if (ScalarToTreeEntry.count(VL[0])) {
 433     int Idx = ScalarToTreeEntry[VL[0]];
 434     TreeEntry *E = &VectorizableTree[Idx];
 435     for (unsigned i = 0, e = VL.size(); i != e; ++i) {
 436       DEBUG(dbgs() << "SLP: \tChecking bundle: " << *VL[i] << ".\n");
 437       if (E->Scalars[i] != VL[i]) {
 438         DEBUG(dbgs() << "SLP: Gathering due to partial overlap.\n");
 439         newTreeEntry(VL, false);
 440         return;
 441       }
 442     }
 443     DEBUG(dbgs() << "SLP: Perfect diamond merge at " << *VL[0] << ".\n");
 444     return;
 445   }
 446
 447   // Check that none of the instructions in the bundle are already in the tree.
 448   for (unsigned i = 0, e = VL.size(); i != e; ++i) {
 449     if (ScalarToTreeEntry.count(VL[i])) {
 450       DEBUG(dbgs() << "SLP: The instruction (" << *VL[i] <<
 451             ") is already in tree.\n");
 452       newTreeEntry(VL, false);
 453       return;
 454     }
 455   }
 456
 457   // If any of the scalars appears in the table OR it is marked as a value that
 458   // needs to stat scalar then we need to gather the scalars.
 459   for (unsigned i = 0, e = VL.size(); i != e; ++i) {
 460     if (ScalarToTreeEntry.count(VL[i]) || MustGather.count(VL[i])) {
 461       DEBUG(dbgs() << "SLP: Gathering due to gathered scalar. \n");
 462       newTreeEntry(VL, false);
 463       return;
 464     }
 465   }
 466
 467   // Check that all of the users of the scalars that we want to vectorize are
 468   // schedulable.
 469   Instruction *VL0 = cast<Instruction>(VL[0]);
 470   int MyLastIndex = getLastIndex(VL);
 471   BasicBlock *BB = cast<Instruction>(VL0)->getParent();
 472
 473   for (unsigned i = 0, e = VL.size(); i != e; ++i) {
 474     Instruction *Scalar = cast<Instruction>(VL[i]);
 475     DEBUG(dbgs() << "SLP: Checking users of  " << *Scalar << ". \n");
 476     for (Value::use_iterator U = Scalar->use_begin(), UE = Scalar->use_end();
 477          U != UE; ++U) {
 478       DEBUG(dbgs() << "SLP: \tUser " << **U << ". \n");
 479       Instruction *User = dyn_cast<Instruction>(*U);
 480       if (!User) {
 481         DEBUG(dbgs() << "SLP: Gathering due unknown user. \n");
 482         newTreeEntry(VL, false);
 483         return;
 484       }
 485
 486       // We don't care if the user is in a different basic block.
 487       BasicBlock *UserBlock = User->getParent();
 488       if (UserBlock != BB) {
 489         DEBUG(dbgs() << "SLP: User from a different basic block "
 490               << *User << ". \n");
 491         continue;
 492       }
 493
 494       // If this is a PHINode within this basic block then we can place the
 495       // extract wherever we want.
 496       if (isa<PHINode>(*User)) {
 497         DEBUG(dbgs() << "SLP: \tWe can schedule PHIs:" << *User << ". \n");
 498         continue;
 499       }
 500
 501       // Check if this is a safe in-tree user.
 502       if (ScalarToTreeEntry.count(User)) {
 503         int Idx = ScalarToTreeEntry[User];
 504         int VecLocation = VectorizableTree[Idx].LastScalarIndex;
 505         if (VecLocation <= MyLastIndex) {
 506           DEBUG(dbgs() << "SLP: Gathering due to unschedulable vector. \n");
 507           newTreeEntry(VL, false);
 508           return;
 509         }
 510         DEBUG(dbgs() << "SLP: In-tree user (" << *User << ") at #" <<
 511               VecLocation << " vector value (" << *Scalar << ") at #"
 512               << MyLastIndex << ".\n");
 513         continue;
 514       }
 515
 516       // Make sure that we can schedule this unknown user.
 517       BlockNumbering &BN = BlocksNumbers[BB];
 518       int UserIndex = BN.getIndex(User);
 519       if (UserIndex < MyLastIndex) {
 520
 521         DEBUG(dbgs() << "SLP: Can't schedule extractelement for "
 522               << *User << ". \n");
 523         newTreeEntry(VL, false);
 524         return;
 525       }
 526     }
 527   }
 528
 529   // Check that every instructions appears once in this bundle.
 530   for (unsigned i = 0, e = VL.size(); i < e; ++i)
 531     for (unsigned j = i+1; j < e; ++j)
 532       if (VL[i] == VL[j]) {
 533         DEBUG(dbgs() << "SLP: Scalar used twice in bundle.\n");
 534         newTreeEntry(VL, false);
 535         return;
 536       }
 537
 538   // Check that instructions in this bundle don't reference other instructions.
 539   // The runtime of this check is O(N * N-1 * uses(N)) and a typical N is 4.
 540   for (unsigned i = 0, e = VL.size(); i < e; ++i) {
 541     for (Value::use_iterator U = VL[i]->use_begin(), UE = VL[i]->use_end();
 542          U != UE; ++U) {
 543       for (unsigned j = 0; j < e; ++j) {
 544         if (i != j && *U == VL[j]) {
 545           DEBUG(dbgs() << "SLP: Intra-bundle dependencies!" << **U << ". \n");
 546           newTreeEntry(VL, false);
 547           return;
 548         }
 549       }
 550     }
 551   }
 552
 553   DEBUG(dbgs() << "SLP: We are able to schedule this bundle.\n");
 554
 555   unsigned Opcode = getSameOpcode(VL);
 556
 557   // Check if it is safe to sink the loads or the stores.
 558   if (Opcode == Instruction::Load || Opcode == Instruction::Store) {
 559     Instruction *Last = getLastInstruction(VL);
 560
 561     for (unsigned i = 0, e = VL.size(); i < e; ++i) {
 562       if (VL[i] == Last)
 563         continue;
 564       Value *Barrier = getSinkBarrier(cast<Instruction>(VL[i]), Last);
 565       if (Barrier) {
 566         DEBUG(dbgs() << "SLP: Can't sink " << *VL[i] << "\n down to " << *Last
 567               << "\n because of " << *Barrier << ".  Gathering.\n");
 568         newTreeEntry(VL, false);
 569         return;
 570       }
 571     }
 572   }
 573
 574   switch (Opcode) {
 575     case Instruction::PHI: {
 576       PHINode *PH = dyn_cast<PHINode>(VL0);
 577       newTreeEntry(VL, true);
 578       DEBUG(dbgs() << "SLP: added a vector of PHINodes.\n");
 579
 580       for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
 581         ValueList Operands;
 582         // Prepare the operand vector.
 583         for (unsigned j = 0; j < VL.size(); ++j)
 584           Operands.push_back(cast<PHINode>(VL[j])->getIncomingValue(i));
 585
 586         buildTree_rec(Operands, Depth + 1);
 587       }
 588       return;
 589     }
 590     case Instruction::ExtractElement: {
 591       bool Reuse = CanReuseExtract(VL);
 592       if (Reuse) {
 593         DEBUG(dbgs() << "SLP: Reusing extract sequence.\n");
 594       }
 595       newTreeEntry(VL, Reuse);
 596       return;
 597     }
 598     case Instruction::Load: {
 599       // Check if the loads are consecutive or of we need to swizzle them.
 600       for (unsigned i = 0, e = VL.size() - 1; i < e; ++i)
 601         if (!isConsecutiveAccess(VL[i], VL[i + 1])) {
 602           newTreeEntry(VL, false);
 603           DEBUG(dbgs() << "SLP: Need to swizzle loads.\n");
 604           return;
 605         }
 606
 607       newTreeEntry(VL, true);
 608       DEBUG(dbgs() << "SLP: added a vector of loads.\n");
 609       return;
 610     }
 611     case Instruction::ZExt:
 612     case Instruction::SExt:
 613     case Instruction::FPToUI:
 614     case Instruction::FPToSI:
 615     case Instruction::FPExt:
 616     case Instruction::PtrToInt:
 617     case Instruction::IntToPtr:
 618     case Instruction::SIToFP:
 619     case Instruction::UIToFP:
 620     case Instruction::Trunc:
 621     case Instruction::FPTrunc:
 622     case Instruction::BitCast: {
 623       Type *SrcTy = VL0->getOperand(0)->getType();
 624       for (unsigned i = 0; i < VL.size(); ++i) {
 625         Type *Ty = cast<Instruction>(VL[i])->getOperand(0)->getType();
 626         if (Ty != SrcTy || Ty->isAggregateType() || Ty->isVectorTy()) {
 627           newTreeEntry(VL, false);
 628           DEBUG(dbgs() << "SLP: Gathering casts with different src types.\n");
 629           return;
 630         }
 631       }
 632       newTreeEntry(VL, true);
 633       DEBUG(dbgs() << "SLP: added a vector of casts.\n");
 634
 635       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
 636         ValueList Operands;
 637         // Prepare the operand vector.
 638         for (unsigned j = 0; j < VL.size(); ++j)
 639           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
 640
 641         buildTree_rec(Operands, Depth+1);
 642       }
 643       return;
 644     }
 645     case Instruction::ICmp:
 646     case Instruction::FCmp: {
 647       // Check that all of the compares have the same predicate.
 648       CmpInst::Predicate P0 = dyn_cast<CmpInst>(VL0)->getPredicate();
 649       for (unsigned i = 1, e = VL.size(); i < e; ++i) {
 650         CmpInst *Cmp = cast<CmpInst>(VL[i]);
 651         if (Cmp->getPredicate() != P0) {
 652           newTreeEntry(VL, false);
 653           DEBUG(dbgs() << "SLP: Gathering cmp with different predicate.\n");
 654           return;
 655         }
 656       }
 657
 658       newTreeEntry(VL, true);
 659       DEBUG(dbgs() << "SLP: added a vector of compares.\n");
 660
 661       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
 662         ValueList Operands;
 663         // Prepare the operand vector.
 664         for (unsigned j = 0; j < VL.size(); ++j)
 665           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
 666
 667         buildTree_rec(Operands, Depth+1);
 668       }
 669       return;
 670     }
 671     case Instruction::Select:
 672     case Instruction::Add:
 673     case Instruction::FAdd:
 674     case Instruction::Sub:
 675     case Instruction::FSub:
 676     case Instruction::Mul:
 677     case Instruction::FMul:
 678     case Instruction::UDiv:
 679     case Instruction::SDiv:
 680     case Instruction::FDiv:
 681     case Instruction::URem:
 682     case Instruction::SRem:
 683     case Instruction::FRem:
 684     case Instruction::Shl:
 685     case Instruction::LShr:
 686     case Instruction::AShr:
 687     case Instruction::And:
 688     case Instruction::Or:
 689     case Instruction::Xor: {
 690       newTreeEntry(VL, true);
 691       DEBUG(dbgs() << "SLP: added a vector of bin op.\n");
 692
 693       for (unsigned i = 0, e = VL0->getNumOperands(); i < e; ++i) {
 694         ValueList Operands;
 695         // Prepare the operand vector.
 696         for (unsigned j = 0; j < VL.size(); ++j)
 697           Operands.push_back(cast<Instruction>(VL[j])->getOperand(i));
 698
 699         buildTree_rec(Operands, Depth+1);
 700       }
 701       return;
 702     }
 703     case Instruction::Store: {
 704       // Check if the stores are consecutive or of we need to swizzle them.
 705       for (unsigned i = 0, e = VL.size() - 1; i < e; ++i)
 706         if (!isConsecutiveAccess(VL[i], VL[i + 1])) {
 707           newTreeEntry(VL, false);
 708           DEBUG(dbgs() << "SLP: Non consecutive store.\n");
 709           return;
 710         }
 711
 712       newTreeEntry(VL, true);
 713       DEBUG(dbgs() << "SLP: added a vector of stores.\n");
 714
 715       ValueList Operands;
 716       for (unsigned j = 0; j < VL.size(); ++j)
 717         Operands.push_back(cast<Instruction>(VL[j])->getOperand(0));
 718
 719       // We can ignore these values because we are sinking them down.
 720       MemBarrierIgnoreList.insert(VL.begin(), VL.end());
 721       buildTree_rec(Operands, Depth + 1);
 722       return;
 723     }
 724     default:
 725       newTreeEntry(VL, false);
 726       DEBUG(dbgs() << "SLP: Gathering unknown instruction.\n");
 727       return;
 728   }
 729 }
 730
 731 int BoUpSLP::getEntryCost(TreeEntry *E) {
 732   ArrayRef<Value*> VL = E->Scalars;
 733
 734   Type *ScalarTy = VL[0]->getType();
 735   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
 736     ScalarTy = SI->getValueOperand()->getType();
 737   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
 738
 739   if (E->NeedToGather) {
 740     if (allConstant(VL))
 741       return 0;
 742     if (isSplat(VL)) {
 743       return TTI->getShuffleCost(TargetTransformInfo::SK_Broadcast, VecTy, 0);
 744     }
 745     return getGatherCost(E->Scalars);
 746   }
 747
 748   assert(getSameOpcode(VL) && getSameType(VL) && getSameBlock(VL) &&
 749          "Invalid VL");
 750   Instruction *VL0 = cast<Instruction>(VL[0]);
 751   unsigned Opcode = VL0->getOpcode();
 752   switch (Opcode) {
 753     case Instruction::PHI: {
 754       return 0;
 755     }
 756     case Instruction::ExtractElement: {
 757       if (CanReuseExtract(VL))
 758         return 0;
 759       return getGatherCost(VecTy);
 760     }
 761     case Instruction::ZExt:
 762     case Instruction::SExt:
 763     case Instruction::FPToUI:
 764     case Instruction::FPToSI:
 765     case Instruction::FPExt:
 766     case Instruction::PtrToInt:
 767     case Instruction::IntToPtr:
 768     case Instruction::SIToFP:
 769     case Instruction::UIToFP:
 770     case Instruction::Trunc:
 771     case Instruction::FPTrunc:
 772     case Instruction::BitCast: {
 773       Type *SrcTy = VL0->getOperand(0)->getType();
 774
 775       // Calculate the cost of this instruction.
 776       int ScalarCost = VL.size() * TTI->getCastInstrCost(VL0->getOpcode(),
 777                                                          VL0->getType(), SrcTy);
 778
 779       VectorType *SrcVecTy = VectorType::get(SrcTy, VL.size());
 780       int VecCost = TTI->getCastInstrCost(VL0->getOpcode(), VecTy, SrcVecTy);
 781       return VecCost - ScalarCost;
 782     }
 783     case Instruction::FCmp:
 784     case Instruction::ICmp:
 785     case Instruction::Select:
 786     case Instruction::Add:
 787     case Instruction::FAdd:
 788     case Instruction::Sub:
 789     case Instruction::FSub:
 790     case Instruction::Mul:
 791     case Instruction::FMul:
 792     case Instruction::UDiv:
 793     case Instruction::SDiv:
 794     case Instruction::FDiv:
 795     case Instruction::URem:
 796     case Instruction::SRem:
 797     case Instruction::FRem:
 798     case Instruction::Shl:
 799     case Instruction::LShr:
 800     case Instruction::AShr:
 801     case Instruction::And:
 802     case Instruction::Or:
 803     case Instruction::Xor: {
 804       // Calculate the cost of this instruction.
 805       int ScalarCost = 0;
 806       int VecCost = 0;
 807       if (Opcode == Instruction::FCmp || Opcode == Instruction::ICmp ||
 808           Opcode == Instruction::Select) {
 809         VectorType *MaskTy = VectorType::get(Builder.getInt1Ty(), VL.size());
 810         ScalarCost = VecTy->getNumElements() *
 811         TTI->getCmpSelInstrCost(Opcode, ScalarTy, Builder.getInt1Ty());
 812         VecCost = TTI->getCmpSelInstrCost(Opcode, VecTy, MaskTy);
 813       } else {
 814         ScalarCost = VecTy->getNumElements() *
 815         TTI->getArithmeticInstrCost(Opcode, ScalarTy);
 816         VecCost = TTI->getArithmeticInstrCost(Opcode, VecTy);
 817       }
 818       return VecCost - ScalarCost;
 819     }
 820     case Instruction::Load: {
 821       // Cost of wide load - cost of scalar loads.
 822       int ScalarLdCost = VecTy->getNumElements() *
 823       TTI->getMemoryOpCost(Instruction::Load, ScalarTy, 1, 0);
 824       int VecLdCost = TTI->getMemoryOpCost(Instruction::Load, ScalarTy, 1, 0);
 825       return VecLdCost - ScalarLdCost;
 826     }
 827     case Instruction::Store: {
 828       // We know that we can merge the stores. Calculate the cost.
 829       int ScalarStCost = VecTy->getNumElements() *
 830       TTI->getMemoryOpCost(Instruction::Store, ScalarTy, 1, 0);
 831       int VecStCost = TTI->getMemoryOpCost(Instruction::Store, ScalarTy, 1, 0);
 832       return VecStCost - ScalarStCost;
 833     }
 834     default:
 835       llvm_unreachable("Unknown instruction");
 836   }
 837 }
 838
 839 int BoUpSLP::getTreeCost() {
 840   int Cost = 0;
 841   DEBUG(dbgs() << "SLP: Calculating cost for tree of size " <<
 842         VectorizableTree.size() << ".\n");
 843
 844   for (unsigned i = 0, e = VectorizableTree.size(); i != e; ++i) {
 845     int C = getEntryCost(&VectorizableTree[i]);
 846     DEBUG(dbgs() << "SLP: Adding cost " << C << " for bundle that starts with "
 847           << *VectorizableTree[i].Scalars[0] << " .\n");
 848     Cost += C;
 849   }
 850   DEBUG(dbgs() << "SLP: Total Cost " << Cost << ".\n");
 851   return  Cost;
 852 }
 853
 854 int BoUpSLP::getGatherCost(Type *Ty) {
 855   int Cost = 0;
 856   for (unsigned i = 0, e = cast<VectorType>(Ty)->getNumElements(); i < e; ++i)
 857     Cost += TTI->getVectorInstrCost(Instruction::InsertElement, Ty, i);
 858   return Cost;
 859 }
 860
 861 int BoUpSLP::getGatherCost(ArrayRef<Value *> VL) {
 862   // Find the type of the operands in VL.
 863   Type *ScalarTy = VL[0]->getType();
 864   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
 865     ScalarTy = SI->getValueOperand()->getType();
 866   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
 867   // Find the cost of inserting/extracting values from the vector.
 868   return getGatherCost(VecTy);
 869 }
 870
 871 AliasAnalysis::Location BoUpSLP::getLocation(Instruction *I) {
 872   if (StoreInst *SI = dyn_cast<StoreInst>(I))
 873     return AA->getLocation(SI);
 874   if (LoadInst *LI = dyn_cast<LoadInst>(I))
 875     return AA->getLocation(LI);
 876   return AliasAnalysis::Location();
 877 }
 878
 879 Value *BoUpSLP::getPointerOperand(Value *I) {
 880   if (LoadInst *LI = dyn_cast<LoadInst>(I))
 881     return LI->getPointerOperand();
 882   if (StoreInst *SI = dyn_cast<StoreInst>(I))
 883     return SI->getPointerOperand();
 884   return 0;
 885 }
 886
 887 unsigned BoUpSLP::getAddressSpaceOperand(Value *I) {
 888   if (LoadInst *L = dyn_cast<LoadInst>(I))
 889     return L->getPointerAddressSpace();
 890   if (StoreInst *S = dyn_cast<StoreInst>(I))
 891     return S->getPointerAddressSpace();
 892   return -1;
 893 }
 894
 895 bool BoUpSLP::isConsecutiveAccess(Value *A, Value *B) {
 896   Value *PtrA = getPointerOperand(A);
 897   Value *PtrB = getPointerOperand(B);
 898   unsigned ASA = getAddressSpaceOperand(A);
 899   unsigned ASB = getAddressSpaceOperand(B);
 900
 901   // Check that the address spaces match and that the pointers are valid.
 902   if (!PtrA || !PtrB || (ASA != ASB))
 903     return false;
 904
 905   // Check that A and B are of the same type.
 906   if (PtrA->getType() != PtrB->getType())
 907     return false;
 908
 909   // Calculate the distance.
 910   const SCEV *PtrSCEVA = SE->getSCEV(PtrA);
 911   const SCEV *PtrSCEVB = SE->getSCEV(PtrB);
 912   const SCEV *OffsetSCEV = SE->getMinusSCEV(PtrSCEVA, PtrSCEVB);
 913   const SCEVConstant *ConstOffSCEV = dyn_cast<SCEVConstant>(OffsetSCEV);
 914
 915   // Non constant distance.
 916   if (!ConstOffSCEV)
 917     return false;
 918
 919   int64_t Offset = ConstOffSCEV->getValue()->getSExtValue();
 920   Type *Ty = cast<PointerType>(PtrA->getType())->getElementType();
 921   // The Instructions are connsecutive if the size of the first load/store is
 922   // the same as the offset.
 923   int64_t Sz = DL->getTypeStoreSize(Ty);
 924   return ((-Offset) == Sz);
 925 }
 926
 927 Value *BoUpSLP::getSinkBarrier(Instruction *Src, Instruction *Dst) {
 928   assert(Src->getParent() == Dst->getParent() && "Not the same BB");
 929   BasicBlock::iterator I = Src, E = Dst;
 930   /// Scan all of the instruction from SRC to DST and check if
 931   /// the source may alias.
 932   for (++I; I != E; ++I) {
 933     // Ignore store instructions that are marked as 'ignore'.
 934     if (MemBarrierIgnoreList.count(I))
 935       continue;
 936     if (Src->mayWriteToMemory()) /* Write */ {
 937       if (!I->mayReadOrWriteMemory())
 938         continue;
 939     } else /* Read */ {
 940       if (!I->mayWriteToMemory())
 941         continue;
 942     }
 943     AliasAnalysis::Location A = getLocation(&*I);
 944     AliasAnalysis::Location B = getLocation(Src);
 945
 946     if (!A.Ptr || !B.Ptr || AA->alias(A, B))
 947       return I;
 948   }
 949   return 0;
 950 }
 951
 952 int BoUpSLP::getLastIndex(ArrayRef<Value *> VL) {
 953   BasicBlock *BB = cast<Instruction>(VL[0])->getParent();
 954   assert(BB == getSameBlock(VL) && BlocksNumbers.count(BB) && "Invalid block");
 955   BlockNumbering &BN = BlocksNumbers[BB];
 956
 957   int MaxIdx = BN.getIndex(BB->getFirstNonPHI());
 958   for (unsigned i = 0, e = VL.size(); i < e; ++i)
 959     MaxIdx = std::max(MaxIdx, BN.getIndex(cast<Instruction>(VL[i])));
 960   return MaxIdx;
 961 }
 962
 963 Instruction *BoUpSLP::getLastInstruction(ArrayRef<Value *> VL) {
 964   BasicBlock *BB = cast<Instruction>(VL[0])->getParent();
 965   assert(BB == getSameBlock(VL) && BlocksNumbers.count(BB) && "Invalid block");
 966   BlockNumbering &BN = BlocksNumbers[BB];
 967
 968   int MaxIdx = BN.getIndex(cast<Instruction>(VL[0]));
 969   for (unsigned i = 1, e = VL.size(); i < e; ++i)
 970     MaxIdx = std::max(MaxIdx, BN.getIndex(cast<Instruction>(VL[i])));
 971   Instruction *I = BN.getInstruction(MaxIdx);
 972   assert(I && "bad location");
 973   return I;
 974 }
 975
 976 Instruction *BoUpSLP::getInstructionForIndex(unsigned Index, BasicBlock *BB) {
 977   BlockNumbering &BN = BlocksNumbers[BB];
 978   return BN.getInstruction(Index);
 979 }
 980
 981 int BoUpSLP::getFirstUserIndex(ArrayRef<Value *> VL) {
 982   BasicBlock *BB = getSameBlock(VL);
 983   assert(BB && "All instructions must come from the same block");
 984   BlockNumbering &BN = BlocksNumbers[BB];
 985
 986   // Find the first user of the values.
 987   int FirstUser = BN.getIndex(BB->getTerminator());
 988   for (unsigned i = 0, e = VL.size(); i < e; ++i) {
 989     for (Value::use_iterator U = VL[i]->use_begin(), UE = VL[i]->use_end();
 990          U != UE; ++U) {
 991       Instruction *Instr = dyn_cast<Instruction>(*U);
 992
 993       if (!Instr || Instr->getParent() != BB)
 994         continue;
 995
 996       FirstUser = std::min(FirstUser, BN.getIndex(Instr));
 997     }
 998   }
 999   return FirstUser;
1000 }
1001
1002 Value *BoUpSLP::Gather(ArrayRef<Value *> VL, VectorType *Ty) {
1003   Value *Vec = UndefValue::get(Ty);
1004   // Generate the 'InsertElement' instruction.
1005   for (unsigned i = 0; i < Ty->getNumElements(); ++i) {
1006     Vec = Builder.CreateInsertElement(Vec, VL[i], Builder.getInt32(i));
1007     if (Instruction *I = dyn_cast<Instruction>(Vec))
1008       GatherSeq.insert(I);
1009   }
1010
1011   return Vec;
1012 }
1013
1014 Value *BoUpSLP::vectorizeTree(ArrayRef<Value *> VL) {
1015   if (ScalarToTreeEntry.count(VL[0])) {
1016     int Idx = ScalarToTreeEntry[VL[0]];
1017     TreeEntry *E = &VectorizableTree[Idx];
1018     if (E->isSame(VL))
1019       return vectorizeTree(E);
1020   }
1021
1022   Type *ScalarTy = VL[0]->getType();
1023   if (StoreInst *SI = dyn_cast<StoreInst>(VL[0]))
1024     ScalarTy = SI->getValueOperand()->getType();
1025   VectorType *VecTy = VectorType::get(ScalarTy, VL.size());
1026
1027   return Gather(VL, VecTy);
1028 }
1029
1030 Value *BoUpSLP::vectorizeTree(TreeEntry *E) {
1031   BuilderLocGuard Guard(Builder);
1032
1033   if (E->VectorizedValue) {
1034     DEBUG(dbgs() << "SLP: Diamond merged for " << *E->Scalars[0] << ".\n");
1035     return E->VectorizedValue;
1036   }
1037
1038   Type *ScalarTy = E->Scalars[0]->getType();
1039   if (StoreInst *SI = dyn_cast<StoreInst>(E->Scalars[0]))
1040     ScalarTy = SI->getValueOperand()->getType();
1041   VectorType *VecTy = VectorType::get(ScalarTy, E->Scalars.size());
1042
1043   if (E->NeedToGather) {
1044     return Gather(E->Scalars, VecTy);
1045   }
1046
1047   Instruction *VL0 = cast<Instruction>(E->Scalars[0]);
1048   unsigned Opcode = VL0->getOpcode();
1049   assert(Opcode == getSameOpcode(E->Scalars) && "Invalid opcode");
1050
1051   switch (Opcode) {
1052     case Instruction::PHI: {
1053       PHINode *PH = dyn_cast<PHINode>(VL0);
1054       Builder.SetInsertPoint(PH->getParent()->getFirstInsertionPt());
1055       PHINode *NewPhi = Builder.CreatePHI(VecTy, PH->getNumIncomingValues());
1056       E->VectorizedValue = NewPhi;
1057
1058       for (unsigned i = 0, e = PH->getNumIncomingValues(); i < e; ++i) {
1059         ValueList Operands;
1060         BasicBlock *IBB = PH->getIncomingBlock(i);
1061
1062         // Prepare the operand vector.
1063         for (unsigned j = 0; j < E->Scalars.size(); ++j)
1064           Operands.push_back(cast<PHINode>(E->Scalars[j])->
1065                              getIncomingValueForBlock(IBB));
1066
1067         Builder.SetInsertPoint(IBB->getTerminator());
1068         Value *Vec = vectorizeTree(Operands);
1069         NewPhi->addIncoming(Vec, IBB);
1070       }
1071
1072       assert(NewPhi->getNumIncomingValues() == PH->getNumIncomingValues() &&
1073              "Invalid number of incoming values");
1074       return NewPhi;
1075     }
1076
1077     case Instruction::ExtractElement: {
1078       if (CanReuseExtract(E->Scalars)) {
1079         Value *V = VL0->getOperand(0);
1080         E->VectorizedValue = V;
1081         return V;
1082       }
1083       return Gather(E->Scalars, VecTy);
1084     }
1085     case Instruction::ZExt:
1086     case Instruction::SExt:
1087     case Instruction::FPToUI:
1088     case Instruction::FPToSI:
1089     case Instruction::FPExt:
1090     case Instruction::PtrToInt:
1091     case Instruction::IntToPtr:
1092     case Instruction::SIToFP:
1093     case Instruction::UIToFP:
1094     case Instruction::Trunc:
1095     case Instruction::FPTrunc:
1096     case Instruction::BitCast: {
1097       ValueList INVL;
1098       for (int i = 0, e = E->Scalars.size(); i < e; ++i)
1099         INVL.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0));
1100
1101       Builder.SetInsertPoint(getLastInstruction(E->Scalars));
1102       Value *InVec = vectorizeTree(INVL);
1103       CastInst *CI = dyn_cast<CastInst>(VL0);
1104       Value *V = Builder.CreateCast(CI->getOpcode(), InVec, VecTy);
1105       E->VectorizedValue = V;
1106       return V;
1107     }
1108     case Instruction::FCmp:
1109     case Instruction::ICmp: {
1110       ValueList LHSV, RHSV;
1111       for (int i = 0, e = E->Scalars.size(); i < e; ++i) {
1112         LHSV.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0));
1113         RHSV.push_back(cast<Instruction>(E->Scalars[i])->getOperand(1));
1114       }
1115
1116       Builder.SetInsertPoint(getLastInstruction(E->Scalars));
1117       Value *L = vectorizeTree(LHSV);
1118       Value *R = vectorizeTree(RHSV);
1119       Value *V;
1120
1121       CmpInst::Predicate P0 = dyn_cast<CmpInst>(VL0)->getPredicate();
1122       if (Opcode == Instruction::FCmp)
1123         V = Builder.CreateFCmp(P0, L, R);
1124       else
1125         V = Builder.CreateICmp(P0, L, R);
1126
1127       E->VectorizedValue = V;
1128       return V;
1129     }
1130     case Instruction::Select: {
1131       ValueList TrueVec, FalseVec, CondVec;
1132       for (int i = 0, e = E->Scalars.size(); i < e; ++i) {
1133         CondVec.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0));
1134         TrueVec.push_back(cast<Instruction>(E->Scalars[i])->getOperand(1));
1135         FalseVec.push_back(cast<Instruction>(E->Scalars[i])->getOperand(2));
1136       }
1137
1138       Builder.SetInsertPoint(getLastInstruction(E->Scalars));
1139       Value *Cond = vectorizeTree(CondVec);
1140       Value *True = vectorizeTree(TrueVec);
1141       Value *False = vectorizeTree(FalseVec);
1142       Value *V = Builder.CreateSelect(Cond, True, False);
1143       E->VectorizedValue = V;
1144       return V;
1145     }
1146     case Instruction::Add:
1147     case Instruction::FAdd:
1148     case Instruction::Sub:
1149     case Instruction::FSub:
1150     case Instruction::Mul:
1151     case Instruction::FMul:
1152     case Instruction::UDiv:
1153     case Instruction::SDiv:
1154     case Instruction::FDiv:
1155     case Instruction::URem:
1156     case Instruction::SRem:
1157     case Instruction::FRem:
1158     case Instruction::Shl:
1159     case Instruction::LShr:
1160     case Instruction::AShr:
1161     case Instruction::And:
1162     case Instruction::Or:
1163     case Instruction::Xor: {
1164       ValueList LHSVL, RHSVL;
1165       for (int i = 0, e = E->Scalars.size(); i < e; ++i) {
1166         LHSVL.push_back(cast<Instruction>(E->Scalars[i])->getOperand(0));
1167         RHSVL.push_back(cast<Instruction>(E->Scalars[i])->getOperand(1));
1168       }
1169
1170       Builder.SetInsertPoint(getLastInstruction(E->Scalars));
1171       Value *LHS = vectorizeTree(LHSVL);
1172       Value *RHS = vectorizeTree(RHSVL);
1173
1174       if (LHS == RHS && isa<Instruction>(LHS)) {
1175         assert((VL0->getOperand(0) == VL0->getOperand(1)) && "Invalid order");
1176       }
1177
1178       BinaryOperator *BinOp = cast<BinaryOperator>(VL0);
1179       Value *V = Builder.CreateBinOp(BinOp->getOpcode(), LHS, RHS);
1180       E->VectorizedValue = V;
1181       return V;
1182     }
1183     case Instruction::Load: {
1184       // Loads are inserted at the head of the tree because we don't want to
1185       // sink them all the way down past store instructions.
1186       Builder.SetInsertPoint(getLastInstruction(E->Scalars));
1187       LoadInst *LI = cast<LoadInst>(VL0);
1188       Value *VecPtr =
1189       Builder.CreateBitCast(LI->getPointerOperand(), VecTy->getPointerTo());
1190       unsigned Alignment = LI->getAlignment();
1191       LI = Builder.CreateLoad(VecPtr);
1192       LI->setAlignment(Alignment);
1193       E->VectorizedValue = LI;
1194       return LI;
1195     }
1196     case Instruction::Store: {
1197       StoreInst *SI = cast<StoreInst>(VL0);
1198       unsigned Alignment = SI->getAlignment();
1199
1200       ValueList ValueOp;
1201       for (int i = 0, e = E->Scalars.size(); i < e; ++i)
1202         ValueOp.push_back(cast<StoreInst>(E->Scalars[i])->getValueOperand());
1203
1204       Builder.SetInsertPoint(getLastInstruction(E->Scalars));
1205       Value *VecValue = vectorizeTree(ValueOp);
1206       Value *VecPtr =
1207       Builder.CreateBitCast(SI->getPointerOperand(), VecTy->getPointerTo());
1208       StoreInst *S = Builder.CreateStore(VecValue, VecPtr);
1209       S->setAlignment(Alignment);
1210       E->VectorizedValue = S;
1211       return S;
1212     }
1213     default:
1214     llvm_unreachable("unknown inst");
1215   }
1216   return 0;
1217 }
1218
1219 void BoUpSLP::vectorizeTree() {
1220   vectorizeTree(&VectorizableTree[0]);
1221
1222   // For each vectorized value:
1223   for (int EIdx = 0, EE = VectorizableTree.size(); EIdx < EE; ++EIdx) {
1224     TreeEntry *Entry = &VectorizableTree[EIdx];
1225
1226     // For each lane:
1227     for (int Lane = 0, LE = Entry->Scalars.size(); Lane != LE; ++Lane) {
1228       Value *Scalar = Entry->Scalars[Lane];
1229
1230       // No need to handle users of gathered values.
1231       if (Entry->NeedToGather)
1232         continue;
1233
1234       Value *Vec = Entry->VectorizedValue;
1235       assert(Vec && "Can't find vectorizable value");
1236
1237       SmallVector<User*, 16> Users(Scalar->use_begin(), Scalar->use_end());
1238
1239       for (SmallVector<User*, 16>::iterator User = Users.begin(),
1240            UE = Users.end(); User != UE; ++User) {
1241         DEBUG(dbgs() << "SLP: \tupdating user  " << **User << ".\n");
1242
1243         bool Gathered = MustGather.count(*User);
1244
1245         // Skip in-tree scalars that become vectors.
1246         if (ScalarToTreeEntry.count(*User) && !Gathered) {
1247           DEBUG(dbgs() << "SLP: \tUser will be removed soon:" <<
1248                 **User << ".\n");
1249           int Idx = ScalarToTreeEntry[*User]; (void) Idx;
1250           assert(!VectorizableTree[Idx].NeedToGather && "bad state ?");
1251           continue;
1252         }
1253
1254         if (!isa<Instruction>(*User))
1255           continue;
1256
1257         // Generate extracts for out-of-tree users.
1258         // Find the insertion point for the extractelement lane.
1259         Instruction *Loc = 0;
1260         if (PHINode *PN = dyn_cast<PHINode>(Vec)) {
1261           Loc = PN->getParent()->getFirstInsertionPt();
1262         } else if (Instruction *Iv = dyn_cast<Instruction>(Vec)){
1263           Loc = ++((BasicBlock::iterator)*Iv);
1264         } else {
1265           Loc = F->getEntryBlock().begin();
1266         }
1267
1268         Builder.SetInsertPoint(Loc);
1269         Value *Ex = Builder.CreateExtractElement(Vec, Builder.getInt32(Lane));
1270         (*User)->replaceUsesOfWith(Scalar, Ex);
1271         DEBUG(dbgs() << "SLP: \tupdated user:" << **User << ".\n");
1272       }
1273
1274       Type *Ty = Scalar->getType();
1275       if (!Ty->isVoidTy()) {
1276         for (Value::use_iterator User = Scalar->use_begin(), UE = Scalar->use_end();
1277              User != UE; ++User) {
1278           DEBUG(dbgs() << "SLP: \tvalidating user:" << **User << ".\n");
1279           assert(!MustGather.count(*User) &&
1280                  "Replacing gathered value with undef");
1281           assert(ScalarToTreeEntry.count(*User) &&
1282                  "Replacing out-of-tree value with undef");
1283         }
1284         Value *Undef = UndefValue::get(Ty);
1285         Scalar->replaceAllUsesWith(Undef);
1286       }
1287       DEBUG(dbgs() << "SLP: \tErasing scalar:" << *Scalar << ".\n");
1288       cast<Instruction>(Scalar)->eraseFromParent();
1289     }
1290   }
1291
1292   for (Function::iterator it = F->begin(), e = F->end(); it != e; ++it) {
1293     BlocksNumbers[it].forget();
1294   }
1295 }
1296
1297 void BoUpSLP::optimizeGatherSequence() {
1298   DEBUG(dbgs() << "SLP: Optimizing " << GatherSeq.size()
1299         << " gather sequences instructions.\n");
1300   // LICM InsertElementInst sequences.
1301   for (SetVector<Instruction *>::iterator it = GatherSeq.begin(),
1302        e = GatherSeq.end(); it != e; ++it) {
1303     InsertElementInst *Insert = dyn_cast<InsertElementInst>(*it);
1304
1305     if (!Insert)
1306       continue;
1307
1308     // Check if this block is inside a loop.
1309     Loop *L = LI->getLoopFor(Insert->getParent());
1310     if (!L)
1311       continue;
1312
1313     // Check if it has a preheader.
1314     BasicBlock *PreHeader = L->getLoopPreheader();
1315     if (!PreHeader)
1316       continue;
1317
1318     // If the vector or the element that we insert into it are
1319     // instructions that are defined in this basic block then we can't
1320     // hoist this instruction.
1321     Instruction *CurrVec = dyn_cast<Instruction>(Insert->getOperand(0));
1322     Instruction *NewElem = dyn_cast<Instruction>(Insert->getOperand(1));
1323     if (CurrVec && L->contains(CurrVec))
1324       continue;
1325     if (NewElem && L->contains(NewElem))
1326       continue;
1327
1328     // We can hoist this instruction. Move it to the pre-header.
1329     Insert->moveBefore(PreHeader->getTerminator());
1330   }
1331
1332   // Perform O(N^2) search over the gather sequences and merge identical
1333   // instructions. TODO: We can further optimize this scan if we split the
1334   // instructions into different buckets based on the insert lane.
1335   SmallPtrSet<Instruction*, 16> Visited;
1336   SmallVector<Instruction*, 16> ToRemove;
1337   ReversePostOrderTraversal<Function*> RPOT(F);
1338   for (ReversePostOrderTraversal<Function*>::rpo_iterator I = RPOT.begin(),
1339        E = RPOT.end(); I != E; ++I) {
1340     BasicBlock *BB = *I;
1341     // For all instructions in the function:
1342     for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
1343       InsertElementInst *Insert = dyn_cast<InsertElementInst>(it);
1344       if (!Insert || !GatherSeq.count(Insert))
1345         continue;
1346
1347       // Check if we can replace this instruction with any of the
1348       // visited instructions.
1349       for (SmallPtrSet<Instruction*, 16>::iterator v = Visited.begin(),
1350            ve = Visited.end(); v != ve; ++v) {
1351         if (Insert->isIdenticalTo(*v) &&
1352             DT->dominates((*v)->getParent(), Insert->getParent())) {
1353           Insert->replaceAllUsesWith(*v);
1354           ToRemove.push_back(Insert);
1355           Insert = 0;
1356           break;
1357         }
1358       }
1359       if (Insert)
1360         Visited.insert(Insert);
1361     }
1362   }
1363
1364   // Erase all of the instructions that we RAUWed.
1365   for (SmallVectorImpl<Instruction *>::iterator v = ToRemove.begin(),
1366        ve = ToRemove.end(); v != ve; ++v) {
1367     assert((*v)->getNumUses() == 0 && "Can't remove instructions with uses");
1368     (*v)->eraseFromParent();
1369   }
1370 }
1371
1372 /// The SLPVectorizer Pass.
1373 struct SLPVectorizer : public FunctionPass {
1374   typedef SmallVector<StoreInst *, 8> StoreList;
1375   typedef MapVector<Value *, StoreList> StoreListMap;
1376
1377   /// Pass identification, replacement for typeid
1378   static char ID;
1379
1380   explicit SLPVectorizer() : FunctionPass(ID) {
1381     initializeSLPVectorizerPass(*PassRegistry::getPassRegistry());
1382   }
1383
1384   ScalarEvolution *SE;
1385   DataLayout *DL;
1386   TargetTransformInfo *TTI;
1387   AliasAnalysis *AA;
1388   LoopInfo *LI;
1389   DominatorTree *DT;
1390
1391   virtual bool runOnFunction(Function &F) {
1392     SE = &getAnalysis<ScalarEvolution>();
1393     DL = getAnalysisIfAvailable<DataLayout>();
1394     TTI = &getAnalysis<TargetTransformInfo>();
1395     AA = &getAnalysis<AliasAnalysis>();
1396     LI = &getAnalysis<LoopInfo>();
1397     DT = &getAnalysis<DominatorTree>();
1398
1399     StoreRefs.clear();
1400     bool Changed = false;
1401
1402     // Must have DataLayout. We can't require it because some tests run w/o
1403     // triple.
1404     if (!DL)
1405       return false;
1406
1407     DEBUG(dbgs() << "SLP: Analyzing blocks in " << F.getName() << ".\n");
1408
1409     // Use the bollom up slp vectorizer to construct chains that start with
1410     // he store instructions.
1411     BoUpSLP R(&F, SE, DL, TTI, AA, LI, DT);
1412
1413     // Scan the blocks in the function in post order.
1414     for (po_iterator<BasicBlock*> it = po_begin(&F.getEntryBlock()),
1415          e = po_end(&F.getEntryBlock()); it != e; ++it) {
1416       BasicBlock *BB = *it;
1417
1418       // Vectorize trees that end at reductions.
1419       Changed |= vectorizeChainsInBlock(BB, R);
1420
1421       // Vectorize trees that end at stores.
1422       if (unsigned count = collectStores(BB, R)) {
1423         (void)count;
1424         DEBUG(dbgs() << "SLP: Found " << count << " stores to vectorize.\n");
1425         Changed |= vectorizeStoreChains(R);
1426       }
1427     }
1428
1429     if (Changed) {
1430       R.optimizeGatherSequence();
1431       DEBUG(dbgs() << "SLP: vectorized \"" << F.getName() << "\"\n");
1432       DEBUG(verifyFunction(F));
1433     }
1434     return Changed;
1435   }
1436
1437   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
1438     FunctionPass::getAnalysisUsage(AU);
1439     AU.addRequired<ScalarEvolution>();
1440     AU.addRequired<AliasAnalysis>();
1441     AU.addRequired<TargetTransformInfo>();
1442     AU.addRequired<LoopInfo>();
1443     AU.addRequired<DominatorTree>();
1444     AU.addPreserved<LoopInfo>();
1445     AU.addPreserved<DominatorTree>();
1446     AU.setPreservesCFG();
1447   }
1448
1449 private:
1450
1451   /// \brief Collect memory references and sort them according to their base
1452   /// object. We sort the stores to their base objects to reduce the cost of the
1453   /// quadratic search on the stores. TODO: We can further reduce this cost
1454   /// if we flush the chain creation every time we run into a memory barrier.
1455   unsigned collectStores(BasicBlock *BB, BoUpSLP &R);
1456
1457   /// \brief Try to vectorize a chain that starts at two arithmetic instrs.
1458   bool tryToVectorizePair(Value *A, Value *B, BoUpSLP &R);
1459
1460   /// \brief Try to vectorize a list of operands. If \p NeedExtracts is true
1461   /// then we calculate the cost of extracting the scalars from the vector.
1462   /// \returns true if a value was vectorized.
1463   bool tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R, bool NeedExtracts);
1464
1465   /// \brief Try to vectorize a chain that may start at the operands of \V;
1466   bool tryToVectorize(BinaryOperator *V, BoUpSLP &R);
1467
1468   /// \brief Vectorize the stores that were collected in StoreRefs.
1469   bool vectorizeStoreChains(BoUpSLP &R);
1470
1471   /// \brief Scan the basic block and look for patterns that are likely to start
1472   /// a vectorization chain.
1473   bool vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R);
1474
1475   bool vectorizeStoreChain(ArrayRef<Value *> Chain, int CostThreshold,
1476                            BoUpSLP &R);
1477
1478   bool vectorizeStores(ArrayRef<StoreInst *> Stores, int costThreshold,
1479                        BoUpSLP &R);
1480 private:
1481   StoreListMap StoreRefs;
1482 };
1483
1484 bool SLPVectorizer::vectorizeStoreChain(ArrayRef<Value *> Chain,
1485                                           int CostThreshold, BoUpSLP &R) {
1486   unsigned ChainLen = Chain.size();
1487   DEBUG(dbgs() << "SLP: Analyzing a store chain of length " << ChainLen
1488         << "\n");
1489   Type *StoreTy = cast<StoreInst>(Chain[0])->getValueOperand()->getType();
1490   unsigned Sz = DL->getTypeSizeInBits(StoreTy);
1491   unsigned VF = MinVecRegSize / Sz;
1492
1493   if (!isPowerOf2_32(Sz) || VF < 2)
1494     return false;
1495
1496   bool Changed = false;
1497   // Look for profitable vectorizable trees at all offsets, starting at zero.
1498   for (unsigned i = 0, e = ChainLen; i < e; ++i) {
1499     if (i + VF > e)
1500       break;
1501     DEBUG(dbgs() << "SLP: Analyzing " << VF << " stores at offset " << i
1502           << "\n");
1503     ArrayRef<Value *> Operands = Chain.slice(i, VF);
1504
1505     R.buildTree(Operands);
1506
1507     int Cost = R.getTreeCost();
1508
1509     DEBUG(dbgs() << "SLP: Found cost=" << Cost << " for VF=" << VF << "\n");
1510     if (Cost < CostThreshold) {
1511       DEBUG(dbgs() << "SLP: Decided to vectorize cost=" << Cost << "\n");
1512       R.vectorizeTree();
1513
1514       // Move to the next bundle.
1515       i += VF - 1;
1516       Changed = true;
1517     }
1518   }
1519
1520   if (Changed || ChainLen > VF)
1521     return Changed;
1522
1523   // Handle short chains. This helps us catch types such as <3 x float> that
1524   // are smaller than vector size.
1525   R.buildTree(Chain);
1526
1527   int Cost = R.getTreeCost();
1528
1529   if (Cost < CostThreshold) {
1530     DEBUG(dbgs() << "SLP: Found store chain cost = " << Cost
1531           << " for size = " << ChainLen << "\n");
1532     R.vectorizeTree();
1533     return true;
1534   }
1535
1536   return false;
1537 }
1538
1539 bool SLPVectorizer::vectorizeStores(ArrayRef<StoreInst *> Stores,
1540                                       int costThreshold, BoUpSLP &R) {
1541   SetVector<Value *> Heads, Tails;
1542   SmallDenseMap<Value *, Value *> ConsecutiveChain;
1543
1544   // We may run into multiple chains that merge into a single chain. We mark the
1545   // stores that we vectorized so that we don't visit the same store twice.
1546   BoUpSLP::ValueSet VectorizedStores;
1547   bool Changed = false;
1548
1549   // Do a quadratic search on all of the given stores and find
1550   // all of the pairs of loads that follow each other.
1551   for (unsigned i = 0, e = Stores.size(); i < e; ++i)
1552     for (unsigned j = 0; j < e; ++j) {
1553       if (i == j)
1554         continue;
1555
1556       if (R.isConsecutiveAccess(Stores[i], Stores[j])) {
1557         Tails.insert(Stores[j]);
1558         Heads.insert(Stores[i]);
1559         ConsecutiveChain[Stores[i]] = Stores[j];
1560       }
1561     }
1562
1563   // For stores that start but don't end a link in the chain:
1564   for (SetVector<Value *>::iterator it = Heads.begin(), e = Heads.end();
1565        it != e; ++it) {
1566     if (Tails.count(*it))
1567       continue;
1568
1569     // We found a store instr that starts a chain. Now follow the chain and try
1570     // to vectorize it.
1571     BoUpSLP::ValueList Operands;
1572     Value *I = *it;
1573     // Collect the chain into a list.
1574     while (Tails.count(I) || Heads.count(I)) {
1575       if (VectorizedStores.count(I))
1576         break;
1577       Operands.push_back(I);
1578       // Move to the next value in the chain.
1579       I = ConsecutiveChain[I];
1580     }
1581
1582     bool Vectorized = vectorizeStoreChain(Operands, costThreshold, R);
1583
1584     // Mark the vectorized stores so that we don't vectorize them again.
1585     if (Vectorized)
1586       VectorizedStores.insert(Operands.begin(), Operands.end());
1587     Changed |= Vectorized;
1588   }
1589
1590   return Changed;
1591 }
1592
1593
1594 unsigned SLPVectorizer::collectStores(BasicBlock *BB, BoUpSLP &R) {
1595   unsigned count = 0;
1596   StoreRefs.clear();
1597   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
1598     StoreInst *SI = dyn_cast<StoreInst>(it);
1599     if (!SI)
1600       continue;
1601
1602     // Check that the pointer points to scalars.
1603     Type *Ty = SI->getValueOperand()->getType();
1604     if (Ty->isAggregateType() || Ty->isVectorTy())
1605       return 0;
1606
1607     // Find the base of the GEP.
1608     Value *Ptr = SI->getPointerOperand();
1609     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr))
1610       Ptr = GEP->getPointerOperand();
1611
1612     // Save the store locations.
1613     StoreRefs[Ptr].push_back(SI);
1614     count++;
1615   }
1616   return count;
1617 }
1618
1619 bool SLPVectorizer::tryToVectorizePair(Value *A, Value *B, BoUpSLP &R) {
1620   if (!A || !B)
1621     return false;
1622   Value *VL[] = { A, B };
1623   return tryToVectorizeList(VL, R, true);
1624 }
1625
1626 bool SLPVectorizer::tryToVectorizeList(ArrayRef<Value *> VL, BoUpSLP &R,
1627                                        bool NeedExtracts) {
1628   if (VL.size() < 2)
1629     return false;
1630
1631   DEBUG(dbgs() << "SLP: Vectorizing a list of length = " << VL.size() << ".\n");
1632
1633   // Check that all of the parts are scalar instructions of the same type.
1634   Instruction *I0 = dyn_cast<Instruction>(VL[0]);
1635   if (!I0)
1636     return 0;
1637
1638   unsigned Opcode0 = I0->getOpcode();
1639
1640   for (int i = 0, e = VL.size(); i < e; ++i) {
1641     Type *Ty = VL[i]->getType();
1642     if (Ty->isAggregateType() || Ty->isVectorTy())
1643       return 0;
1644     Instruction *Inst = dyn_cast<Instruction>(VL[i]);
1645     if (!Inst || Inst->getOpcode() != Opcode0)
1646       return 0;
1647   }
1648
1649   R.buildTree(VL);
1650   int Cost = R.getTreeCost();
1651
1652   int ExtrCost = NeedExtracts ? R.getGatherCost(VL) : 0;
1653   DEBUG(dbgs() << "SLP: Cost of pair:" << Cost
1654                << " Cost of extract:" << ExtrCost << ".\n");
1655   if ((Cost + ExtrCost) >= -SLPCostThreshold)
1656     return false;
1657   DEBUG(dbgs() << "SLP: Vectorizing pair.\n");
1658   R.vectorizeTree();
1659   return true;
1660 }
1661
1662 bool SLPVectorizer::tryToVectorize(BinaryOperator *V, BoUpSLP &R) {
1663   if (!V)
1664     return false;
1665
1666   // Try to vectorize V.
1667   if (tryToVectorizePair(V->getOperand(0), V->getOperand(1), R))
1668     return true;
1669
1670   BinaryOperator *A = dyn_cast<BinaryOperator>(V->getOperand(0));
1671   BinaryOperator *B = dyn_cast<BinaryOperator>(V->getOperand(1));
1672   // Try to skip B.
1673   if (B && B->hasOneUse()) {
1674     BinaryOperator *B0 = dyn_cast<BinaryOperator>(B->getOperand(0));
1675     BinaryOperator *B1 = dyn_cast<BinaryOperator>(B->getOperand(1));
1676     if (tryToVectorizePair(A, B0, R)) {
1677       B->moveBefore(V);
1678       return true;
1679     }
1680     if (tryToVectorizePair(A, B1, R)) {
1681       B->moveBefore(V);
1682       return true;
1683     }
1684   }
1685
1686   // Try to skip A.
1687   if (A && A->hasOneUse()) {
1688     BinaryOperator *A0 = dyn_cast<BinaryOperator>(A->getOperand(0));
1689     BinaryOperator *A1 = dyn_cast<BinaryOperator>(A->getOperand(1));
1690     if (tryToVectorizePair(A0, B, R)) {
1691       A->moveBefore(V);
1692       return true;
1693     }
1694     if (tryToVectorizePair(A1, B, R)) {
1695       A->moveBefore(V);
1696       return true;
1697     }
1698   }
1699   return 0;
1700 }
1701
1702 bool SLPVectorizer::vectorizeChainsInBlock(BasicBlock *BB, BoUpSLP &R) {
1703   bool Changed = false;
1704   for (BasicBlock::iterator it = BB->begin(), e = BB->end(); it != e; ++it) {
1705     if (isa<DbgInfoIntrinsic>(it))
1706       continue;
1707
1708     // Try to vectorize reductions that use PHINodes.
1709     if (PHINode *P = dyn_cast<PHINode>(it)) {
1710       // Check that the PHI is a reduction PHI.
1711       if (P->getNumIncomingValues() != 2)
1712         return Changed;
1713       Value *Rdx =
1714           (P->getIncomingBlock(0) == BB
1715                ? (P->getIncomingValue(0))
1716                : (P->getIncomingBlock(1) == BB ? P->getIncomingValue(1) : 0));
1717       // Check if this is a Binary Operator.
1718       BinaryOperator *BI = dyn_cast_or_null<BinaryOperator>(Rdx);
1719       if (!BI)
1720         continue;
1721
1722       Value *Inst = BI->getOperand(0);
1723       if (Inst == P)
1724         Inst = BI->getOperand(1);
1725
1726       Changed |= tryToVectorize(dyn_cast<BinaryOperator>(Inst), R);
1727       continue;
1728     }
1729
1730     // Try to vectorize trees that start at compare instructions.
1731     if (CmpInst *CI = dyn_cast<CmpInst>(it)) {
1732       if (tryToVectorizePair(CI->getOperand(0), CI->getOperand(1), R)) {
1733         Changed |= true;
1734         continue;
1735       }
1736       for (int i = 0; i < 2; ++i)
1737         if (BinaryOperator *BI = dyn_cast<BinaryOperator>(CI->getOperand(i)))
1738           Changed |=
1739               tryToVectorizePair(BI->getOperand(0), BI->getOperand(1), R);
1740       continue;
1741     }
1742   }
1743
1744   // Scan the PHINodes in our successors in search for pairing hints.
1745   for (succ_iterator it = succ_begin(BB), e = succ_end(BB); it != e; ++it) {
1746     BasicBlock *Succ = *it;
1747     SmallVector<Value *, 4> Incoming;
1748
1749     // Collect the incoming values from the PHIs.
1750     for (BasicBlock::iterator instr = Succ->begin(), ie = Succ->end();
1751          instr != ie; ++instr) {
1752       PHINode *P = dyn_cast<PHINode>(instr);
1753
1754       if (!P)
1755         break;
1756
1757       Value *V = P->getIncomingValueForBlock(BB);
1758       if (Instruction *I = dyn_cast<Instruction>(V))
1759         if (I->getParent() == BB)
1760           Incoming.push_back(I);
1761     }
1762
1763     if (Incoming.size() > 1)
1764       Changed |= tryToVectorizeList(Incoming, R, true);
1765   }
1766
1767   return Changed;
1768 }
1769
1770 bool SLPVectorizer::vectorizeStoreChains(BoUpSLP &R) {
1771   bool Changed = false;
1772   // Attempt to sort and vectorize each of the store-groups.
1773   for (StoreListMap::iterator it = StoreRefs.begin(), e = StoreRefs.end();
1774        it != e; ++it) {
1775     if (it->second.size() < 2)
1776       continue;
1777
1778     DEBUG(dbgs() << "SLP: Analyzing a store chain of length "
1779                  << it->second.size() << ".\n");
1780
1781     Changed |= vectorizeStores(it->second, -SLPCostThreshold, R);
1782   }
1783   return Changed;
1784 }
1785
1786 } // end anonymous namespace
1787
1788 char SLPVectorizer::ID = 0;
1789 static const char lv_name[] = "SLP Vectorizer";
1790 INITIALIZE_PASS_BEGIN(SLPVectorizer, SV_NAME, lv_name, false, false)
1791 INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
1792 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
1793 INITIALIZE_PASS_DEPENDENCY(ScalarEvolution)
1794 INITIALIZE_PASS_DEPENDENCY(LoopSimplify)
1795 INITIALIZE_PASS_END(SLPVectorizer, SV_NAME, lv_name, false, false)
1796
1797 namespace llvm {
1798 Pass *createSLPVectorizerPass() { return new SLPVectorizer(); }
1799 }