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