contrib/llvm/lib/Transforms/Vectorize/LoadStoreVectorizer.cpp

   1 //===- LoadStoreVectorizer.cpp - GPU Load & Store 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 //
  10 // This pass merges loads/stores to/from sequential memory addresses into vector
  11 // loads/stores.  Although there's nothing GPU-specific in here, this pass is
  12 // motivated by the microarchitectural quirks of nVidia and AMD GPUs.
  13 //
  14 // (For simplicity below we talk about loads only, but everything also applies
  15 // to stores.)
  16 //
  17 // This pass is intended to be run late in the pipeline, after other
  18 // vectorization opportunities have been exploited.  So the assumption here is
  19 // that immediately following our new vector load we'll need to extract out the
  20 // individual elements of the load, so we can operate on them individually.
  21 //
  22 // On CPUs this transformation is usually not beneficial, because extracting the
  23 // elements of a vector register is expensive on most architectures.  It's
  24 // usually better just to load each element individually into its own scalar
  25 // register.
  26 //
  27 // However, nVidia and AMD GPUs don't have proper vector registers.  Instead, a
  28 // "vector load" loads directly into a series of scalar registers.  In effect,
  29 // extracting the elements of the vector is free.  It's therefore always
  30 // beneficial to vectorize a sequence of loads on these architectures.
  31 //
  32 // Vectorizing (perhaps a better name might be "coalescing") loads can have
  33 // large performance impacts on GPU kernels, and opportunities for vectorizing
  34 // are common in GPU code.  This pass tries very hard to find such
  35 // opportunities; its runtime is quadratic in the number of loads in a BB.
  36 //
  37 // Some CPU architectures, such as ARM, have instructions that load into
  38 // multiple scalar registers, similar to a GPU vectorized load.  In theory ARM
  39 // could use this pass (with some modifications), but currently it implements
  40 // its own pass to do something similar to what we do here.
  41
  42 #include "llvm/ADT/APInt.h"
  43 #include "llvm/ADT/ArrayRef.h"
  44 #include "llvm/ADT/MapVector.h"
  45 #include "llvm/ADT/PostOrderIterator.h"
  46 #include "llvm/ADT/STLExtras.h"
  47 #include "llvm/ADT/SmallPtrSet.h"
  48 #include "llvm/ADT/SmallVector.h"
  49 #include "llvm/ADT/Statistic.h"
  50 #include "llvm/ADT/iterator_range.h"
  51 #include "llvm/Analysis/AliasAnalysis.h"
  52 #include "llvm/Analysis/MemoryLocation.h"
  53 #include "llvm/Analysis/OrderedBasicBlock.h"
  54 #include "llvm/Analysis/ScalarEvolution.h"
  55 #include "llvm/Analysis/TargetTransformInfo.h"
  56 #include "llvm/Transforms/Utils/Local.h"
  57 #include "llvm/Analysis/ValueTracking.h"
  58 #include "llvm/Analysis/VectorUtils.h"
  59 #include "llvm/IR/Attributes.h"
  60 #include "llvm/IR/BasicBlock.h"
  61 #include "llvm/IR/Constants.h"
  62 #include "llvm/IR/DataLayout.h"
  63 #include "llvm/IR/DerivedTypes.h"
  64 #include "llvm/IR/Dominators.h"
  65 #include "llvm/IR/Function.h"
  66 #include "llvm/IR/IRBuilder.h"
  67 #include "llvm/IR/InstrTypes.h"
  68 #include "llvm/IR/Instruction.h"
  69 #include "llvm/IR/Instructions.h"
  70 #include "llvm/IR/IntrinsicInst.h"
  71 #include "llvm/IR/Module.h"
  72 #include "llvm/IR/Type.h"
  73 #include "llvm/IR/User.h"
  74 #include "llvm/IR/Value.h"
  75 #include "llvm/Pass.h"
  76 #include "llvm/Support/Casting.h"
  77 #include "llvm/Support/Debug.h"
  78 #include "llvm/Support/KnownBits.h"
  79 #include "llvm/Support/MathExtras.h"
  80 #include "llvm/Support/raw_ostream.h"
  81 #include "llvm/Transforms/Vectorize.h"
  82 #include <algorithm>
  83 #include <cassert>
  84 #include <cstdlib>
  85 #include <tuple>
  86 #include <utility>
  87
  88 using namespace llvm;
  89
  90 #define DEBUG_TYPE "load-store-vectorizer"
  91
  92 STATISTIC(NumVectorInstructions, "Number of vector accesses generated");
  93 STATISTIC(NumScalarsVectorized, "Number of scalar accesses vectorized");
  94
  95 // FIXME: Assuming stack alignment of 4 is always good enough
  96 static const unsigned StackAdjustedAlignment = 4;
  97
  98 namespace {
  99
 100 /// ChainID is an arbitrary token that is allowed to be different only for the
 101 /// accesses that are guaranteed to be considered non-consecutive by
 102 /// Vectorizer::isConsecutiveAccess. It's used for grouping instructions
 103 /// together and reducing the number of instructions the main search operates on
 104 /// at a time, i.e. this is to reduce compile time and nothing else as the main
 105 /// search has O(n^2) time complexity. The underlying type of ChainID should not
 106 /// be relied upon.
 107 using ChainID = const Value *;
 108 using InstrList = SmallVector<Instruction *, 8>;
 109 using InstrListMap = MapVector<ChainID, InstrList>;
 110
 111 class Vectorizer {
 112   Function &F;
 113   AliasAnalysis &AA;
 114   DominatorTree &DT;
 115   ScalarEvolution &SE;
 116   TargetTransformInfo &TTI;
 117   const DataLayout &DL;
 118   IRBuilder<> Builder;
 119
 120 public:
 121   Vectorizer(Function &F, AliasAnalysis &AA, DominatorTree &DT,
 122              ScalarEvolution &SE, TargetTransformInfo &TTI)
 123       : F(F), AA(AA), DT(DT), SE(SE), TTI(TTI),
 124         DL(F.getParent()->getDataLayout()), Builder(SE.getContext()) {}
 125
 126   bool run();
 127
 128 private:
 129   unsigned getPointerAddressSpace(Value *I);
 130
 131   unsigned getAlignment(LoadInst *LI) const {
 132     unsigned Align = LI->getAlignment();
 133     if (Align != 0)
 134       return Align;
 135
 136     return DL.getABITypeAlignment(LI->getType());
 137   }
 138
 139   unsigned getAlignment(StoreInst *SI) const {
 140     unsigned Align = SI->getAlignment();
 141     if (Align != 0)
 142       return Align;
 143
 144     return DL.getABITypeAlignment(SI->getValueOperand()->getType());
 145   }
 146
 147   static const unsigned MaxDepth = 3;
 148
 149   bool isConsecutiveAccess(Value *A, Value *B);
 150   bool areConsecutivePointers(Value *PtrA, Value *PtrB, const APInt &PtrDelta,
 151                               unsigned Depth = 0) const;
 152   bool lookThroughComplexAddresses(Value *PtrA, Value *PtrB, APInt PtrDelta,
 153                                    unsigned Depth) const;
 154   bool lookThroughSelects(Value *PtrA, Value *PtrB, const APInt &PtrDelta,
 155                           unsigned Depth) const;
 156
 157   /// After vectorization, reorder the instructions that I depends on
 158   /// (the instructions defining its operands), to ensure they dominate I.
 159   void reorder(Instruction *I);
 160
 161   /// Returns the first and the last instructions in Chain.
 162   std::pair<BasicBlock::iterator, BasicBlock::iterator>
 163   getBoundaryInstrs(ArrayRef<Instruction *> Chain);
 164
 165   /// Erases the original instructions after vectorizing.
 166   void eraseInstructions(ArrayRef<Instruction *> Chain);
 167
 168   /// "Legalize" the vector type that would be produced by combining \p
 169   /// ElementSizeBits elements in \p Chain. Break into two pieces such that the
 170   /// total size of each piece is 1, 2 or a multiple of 4 bytes. \p Chain is
 171   /// expected to have more than 4 elements.
 172   std::pair<ArrayRef<Instruction *>, ArrayRef<Instruction *>>
 173   splitOddVectorElts(ArrayRef<Instruction *> Chain, unsigned ElementSizeBits);
 174
 175   /// Finds the largest prefix of Chain that's vectorizable, checking for
 176   /// intervening instructions which may affect the memory accessed by the
 177   /// instructions within Chain.
 178   ///
 179   /// The elements of \p Chain must be all loads or all stores and must be in
 180   /// address order.
 181   ArrayRef<Instruction *> getVectorizablePrefix(ArrayRef<Instruction *> Chain);
 182
 183   /// Collects load and store instructions to vectorize.
 184   std::pair<InstrListMap, InstrListMap> collectInstructions(BasicBlock *BB);
 185
 186   /// Processes the collected instructions, the \p Map. The values of \p Map
 187   /// should be all loads or all stores.
 188   bool vectorizeChains(InstrListMap &Map);
 189
 190   /// Finds the load/stores to consecutive memory addresses and vectorizes them.
 191   bool vectorizeInstructions(ArrayRef<Instruction *> Instrs);
 192
 193   /// Vectorizes the load instructions in Chain.
 194   bool
 195   vectorizeLoadChain(ArrayRef<Instruction *> Chain,
 196                      SmallPtrSet<Instruction *, 16> *InstructionsProcessed);
 197
 198   /// Vectorizes the store instructions in Chain.
 199   bool
 200   vectorizeStoreChain(ArrayRef<Instruction *> Chain,
 201                       SmallPtrSet<Instruction *, 16> *InstructionsProcessed);
 202
 203   /// Check if this load/store access is misaligned accesses.
 204   bool accessIsMisaligned(unsigned SzInBytes, unsigned AddressSpace,
 205                           unsigned Alignment);
 206 };
 207
 208 class LoadStoreVectorizer : public FunctionPass {
 209 public:
 210   static char ID;
 211
 212   LoadStoreVectorizer() : FunctionPass(ID) {
 213     initializeLoadStoreVectorizerPass(*PassRegistry::getPassRegistry());
 214   }
 215
 216   bool runOnFunction(Function &F) override;
 217
 218   StringRef getPassName() const override {
 219     return "GPU Load and Store Vectorizer";
 220   }
 221
 222   void getAnalysisUsage(AnalysisUsage &AU) const override {
 223     AU.addRequired<AAResultsWrapperPass>();
 224     AU.addRequired<ScalarEvolutionWrapperPass>();
 225     AU.addRequired<DominatorTreeWrapperPass>();
 226     AU.addRequired<TargetTransformInfoWrapperPass>();
 227     AU.setPreservesCFG();
 228   }
 229 };
 230
 231 } // end anonymous namespace
 232
 233 char LoadStoreVectorizer::ID = 0;
 234
 235 INITIALIZE_PASS_BEGIN(LoadStoreVectorizer, DEBUG_TYPE,
 236                       "Vectorize load and Store instructions", false, false)
 237 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
 238 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 239 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 240 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 241 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 242 INITIALIZE_PASS_END(LoadStoreVectorizer, DEBUG_TYPE,
 243                     "Vectorize load and store instructions", false, false)
 244
 245 Pass *llvm::createLoadStoreVectorizerPass() {
 246   return new LoadStoreVectorizer();
 247 }
 248
 249 // The real propagateMetadata expects a SmallVector<Value*>, but we deal in
 250 // vectors of Instructions.
 251 static void propagateMetadata(Instruction *I, ArrayRef<Instruction *> IL) {
 252   SmallVector<Value *, 8> VL(IL.begin(), IL.end());
 253   propagateMetadata(I, VL);
 254 }
 255
 256 bool LoadStoreVectorizer::runOnFunction(Function &F) {
 257   // Don't vectorize when the attribute NoImplicitFloat is used.
 258   if (skipFunction(F) || F.hasFnAttribute(Attribute::NoImplicitFloat))
 259     return false;
 260
 261   AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
 262   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 263   ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 264   TargetTransformInfo &TTI =
 265       getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 266
 267   Vectorizer V(F, AA, DT, SE, TTI);
 268   return V.run();
 269 }
 270
 271 // Vectorizer Implementation
 272 bool Vectorizer::run() {
 273   bool Changed = false;
 274
 275   // Scan the blocks in the function in post order.
 276   for (BasicBlock *BB : post_order(&F)) {
 277     InstrListMap LoadRefs, StoreRefs;
 278     std::tie(LoadRefs, StoreRefs) = collectInstructions(BB);
 279     Changed |= vectorizeChains(LoadRefs);
 280     Changed |= vectorizeChains(StoreRefs);
 281   }
 282
 283   return Changed;
 284 }
 285
 286 unsigned Vectorizer::getPointerAddressSpace(Value *I) {
 287   if (LoadInst *L = dyn_cast<LoadInst>(I))
 288     return L->getPointerAddressSpace();
 289   if (StoreInst *S = dyn_cast<StoreInst>(I))
 290     return S->getPointerAddressSpace();
 291   return -1;
 292 }
 293
 294 // FIXME: Merge with llvm::isConsecutiveAccess
 295 bool Vectorizer::isConsecutiveAccess(Value *A, Value *B) {
 296   Value *PtrA = getLoadStorePointerOperand(A);
 297   Value *PtrB = getLoadStorePointerOperand(B);
 298   unsigned ASA = getPointerAddressSpace(A);
 299   unsigned ASB = getPointerAddressSpace(B);
 300
 301   // Check that the address spaces match and that the pointers are valid.
 302   if (!PtrA || !PtrB || (ASA != ASB))
 303     return false;
 304
 305   // Make sure that A and B are different pointers of the same size type.
 306   Type *PtrATy = PtrA->getType()->getPointerElementType();
 307   Type *PtrBTy = PtrB->getType()->getPointerElementType();
 308   if (PtrA == PtrB ||
 309       PtrATy->isVectorTy() != PtrBTy->isVectorTy() ||
 310       DL.getTypeStoreSize(PtrATy) != DL.getTypeStoreSize(PtrBTy) ||
 311       DL.getTypeStoreSize(PtrATy->getScalarType()) !=
 312           DL.getTypeStoreSize(PtrBTy->getScalarType()))
 313     return false;
 314
 315   unsigned PtrBitWidth = DL.getPointerSizeInBits(ASA);
 316   APInt Size(PtrBitWidth, DL.getTypeStoreSize(PtrATy));
 317
 318   return areConsecutivePointers(PtrA, PtrB, Size);
 319 }
 320
 321 bool Vectorizer::areConsecutivePointers(Value *PtrA, Value *PtrB,
 322                                         const APInt &PtrDelta,
 323                                         unsigned Depth) const {
 324   unsigned PtrBitWidth = DL.getPointerTypeSizeInBits(PtrA->getType());
 325   APInt OffsetA(PtrBitWidth, 0);
 326   APInt OffsetB(PtrBitWidth, 0);
 327   PtrA = PtrA->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetA);
 328   PtrB = PtrB->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetB);
 329
 330   APInt OffsetDelta = OffsetB - OffsetA;
 331
 332   // Check if they are based on the same pointer. That makes the offsets
 333   // sufficient.
 334   if (PtrA == PtrB)
 335     return OffsetDelta == PtrDelta;
 336
 337   // Compute the necessary base pointer delta to have the necessary final delta
 338   // equal to the pointer delta requested.
 339   APInt BaseDelta = PtrDelta - OffsetDelta;
 340
 341   // Compute the distance with SCEV between the base pointers.
 342   const SCEV *PtrSCEVA = SE.getSCEV(PtrA);
 343   const SCEV *PtrSCEVB = SE.getSCEV(PtrB);
 344   const SCEV *C = SE.getConstant(BaseDelta);
 345   const SCEV *X = SE.getAddExpr(PtrSCEVA, C);
 346   if (X == PtrSCEVB)
 347     return true;
 348
 349   // The above check will not catch the cases where one of the pointers is
 350   // factorized but the other one is not, such as (C + (S * (A + B))) vs
 351   // (AS + BS). Get the minus scev. That will allow re-combining the expresions
 352   // and getting the simplified difference.
 353   const SCEV *Dist = SE.getMinusSCEV(PtrSCEVB, PtrSCEVA);
 354   if (C == Dist)
 355     return true;
 356
 357   // Sometimes even this doesn't work, because SCEV can't always see through
 358   // patterns that look like (gep (ext (add (shl X, C1), C2))). Try checking
 359   // things the hard way.
 360   return lookThroughComplexAddresses(PtrA, PtrB, BaseDelta, Depth);
 361 }
 362
 363 bool Vectorizer::lookThroughComplexAddresses(Value *PtrA, Value *PtrB,
 364                                              APInt PtrDelta,
 365                                              unsigned Depth) const {
 366   auto *GEPA = dyn_cast<GetElementPtrInst>(PtrA);
 367   auto *GEPB = dyn_cast<GetElementPtrInst>(PtrB);
 368   if (!GEPA || !GEPB)
 369     return lookThroughSelects(PtrA, PtrB, PtrDelta, Depth);
 370
 371   // Look through GEPs after checking they're the same except for the last
 372   // index.
 373   if (GEPA->getNumOperands() != GEPB->getNumOperands() ||
 374       GEPA->getPointerOperand() != GEPB->getPointerOperand())
 375     return false;
 376   gep_type_iterator GTIA = gep_type_begin(GEPA);
 377   gep_type_iterator GTIB = gep_type_begin(GEPB);
 378   for (unsigned I = 0, E = GEPA->getNumIndices() - 1; I < E; ++I) {
 379     if (GTIA.getOperand() != GTIB.getOperand())
 380       return false;
 381     ++GTIA;
 382     ++GTIB;
 383   }
 384
 385   Instruction *OpA = dyn_cast<Instruction>(GTIA.getOperand());
 386   Instruction *OpB = dyn_cast<Instruction>(GTIB.getOperand());
 387   if (!OpA || !OpB || OpA->getOpcode() != OpB->getOpcode() ||
 388       OpA->getType() != OpB->getType())
 389     return false;
 390
 391   if (PtrDelta.isNegative()) {
 392     if (PtrDelta.isMinSignedValue())
 393       return false;
 394     PtrDelta.negate();
 395     std::swap(OpA, OpB);
 396   }
 397   uint64_t Stride = DL.getTypeAllocSize(GTIA.getIndexedType());
 398   if (PtrDelta.urem(Stride) != 0)
 399     return false;
 400   unsigned IdxBitWidth = OpA->getType()->getScalarSizeInBits();
 401   APInt IdxDiff = PtrDelta.udiv(Stride).zextOrSelf(IdxBitWidth);
 402
 403   // Only look through a ZExt/SExt.
 404   if (!isa<SExtInst>(OpA) && !isa<ZExtInst>(OpA))
 405     return false;
 406
 407   bool Signed = isa<SExtInst>(OpA);
 408
 409   // At this point A could be a function parameter, i.e. not an instruction
 410   Value *ValA = OpA->getOperand(0);
 411   OpB = dyn_cast<Instruction>(OpB->getOperand(0));
 412   if (!OpB || ValA->getType() != OpB->getType())
 413     return false;
 414
 415   // Now we need to prove that adding IdxDiff to ValA won't overflow.
 416   bool Safe = false;
 417   // First attempt: if OpB is an add with NSW/NUW, and OpB is IdxDiff added to
 418   // ValA, we're okay.
 419   if (OpB->getOpcode() == Instruction::Add &&
 420       isa<ConstantInt>(OpB->getOperand(1)) &&
 421       IdxDiff.sle(cast<ConstantInt>(OpB->getOperand(1))->getSExtValue())) {
 422     if (Signed)
 423       Safe = cast<BinaryOperator>(OpB)->hasNoSignedWrap();
 424     else
 425       Safe = cast<BinaryOperator>(OpB)->hasNoUnsignedWrap();
 426   }
 427
 428   unsigned BitWidth = ValA->getType()->getScalarSizeInBits();
 429
 430   // Second attempt:
 431   // If all set bits of IdxDiff or any higher order bit other than the sign bit
 432   // are known to be zero in ValA, we can add Diff to it while guaranteeing no
 433   // overflow of any sort.
 434   if (!Safe) {
 435     OpA = dyn_cast<Instruction>(ValA);
 436     if (!OpA)
 437       return false;
 438     KnownBits Known(BitWidth);
 439     computeKnownBits(OpA, Known, DL, 0, nullptr, OpA, &DT);
 440     APInt BitsAllowedToBeSet = Known.Zero.zext(IdxDiff.getBitWidth());
 441     if (Signed)
 442       BitsAllowedToBeSet.clearBit(BitWidth - 1);
 443     if (BitsAllowedToBeSet.ult(IdxDiff))
 444       return false;
 445   }
 446
 447   const SCEV *OffsetSCEVA = SE.getSCEV(ValA);
 448   const SCEV *OffsetSCEVB = SE.getSCEV(OpB);
 449   const SCEV *C = SE.getConstant(IdxDiff.trunc(BitWidth));
 450   const SCEV *X = SE.getAddExpr(OffsetSCEVA, C);
 451   return X == OffsetSCEVB;
 452 }
 453
 454 bool Vectorizer::lookThroughSelects(Value *PtrA, Value *PtrB,
 455                                     const APInt &PtrDelta,
 456                                     unsigned Depth) const {
 457   if (Depth++ == MaxDepth)
 458     return false;
 459
 460   if (auto *SelectA = dyn_cast<SelectInst>(PtrA)) {
 461     if (auto *SelectB = dyn_cast<SelectInst>(PtrB)) {
 462       return SelectA->getCondition() == SelectB->getCondition() &&
 463              areConsecutivePointers(SelectA->getTrueValue(),
 464                                     SelectB->getTrueValue(), PtrDelta, Depth) &&
 465              areConsecutivePointers(SelectA->getFalseValue(),
 466                                     SelectB->getFalseValue(), PtrDelta, Depth);
 467     }
 468   }
 469   return false;
 470 }
 471
 472 void Vectorizer::reorder(Instruction *I) {
 473   OrderedBasicBlock OBB(I->getParent());
 474   SmallPtrSet<Instruction *, 16> InstructionsToMove;
 475   SmallVector<Instruction *, 16> Worklist;
 476
 477   Worklist.push_back(I);
 478   while (!Worklist.empty()) {
 479     Instruction *IW = Worklist.pop_back_val();
 480     int NumOperands = IW->getNumOperands();
 481     for (int i = 0; i < NumOperands; i++) {
 482       Instruction *IM = dyn_cast<Instruction>(IW->getOperand(i));
 483       if (!IM || IM->getOpcode() == Instruction::PHI)
 484         continue;
 485
 486       // If IM is in another BB, no need to move it, because this pass only
 487       // vectorizes instructions within one BB.
 488       if (IM->getParent() != I->getParent())
 489         continue;
 490
 491       if (!OBB.dominates(IM, I)) {
 492         InstructionsToMove.insert(IM);
 493         Worklist.push_back(IM);
 494       }
 495     }
 496   }
 497
 498   // All instructions to move should follow I. Start from I, not from begin().
 499   for (auto BBI = I->getIterator(), E = I->getParent()->end(); BBI != E;
 500        ++BBI) {
 501     if (!InstructionsToMove.count(&*BBI))
 502       continue;
 503     Instruction *IM = &*BBI;
 504     --BBI;
 505     IM->removeFromParent();
 506     IM->insertBefore(I);
 507   }
 508 }
 509
 510 std::pair<BasicBlock::iterator, BasicBlock::iterator>
 511 Vectorizer::getBoundaryInstrs(ArrayRef<Instruction *> Chain) {
 512   Instruction *C0 = Chain[0];
 513   BasicBlock::iterator FirstInstr = C0->getIterator();
 514   BasicBlock::iterator LastInstr = C0->getIterator();
 515
 516   BasicBlock *BB = C0->getParent();
 517   unsigned NumFound = 0;
 518   for (Instruction &I : *BB) {
 519     if (!is_contained(Chain, &I))
 520       continue;
 521
 522     ++NumFound;
 523     if (NumFound == 1) {
 524       FirstInstr = I.getIterator();
 525     }
 526     if (NumFound == Chain.size()) {
 527       LastInstr = I.getIterator();
 528       break;
 529     }
 530   }
 531
 532   // Range is [first, last).
 533   return std::make_pair(FirstInstr, ++LastInstr);
 534 }
 535
 536 void Vectorizer::eraseInstructions(ArrayRef<Instruction *> Chain) {
 537   SmallVector<Instruction *, 16> Instrs;
 538   for (Instruction *I : Chain) {
 539     Value *PtrOperand = getLoadStorePointerOperand(I);
 540     assert(PtrOperand && "Instruction must have a pointer operand.");
 541     Instrs.push_back(I);
 542     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(PtrOperand))
 543       Instrs.push_back(GEP);
 544   }
 545
 546   // Erase instructions.
 547   for (Instruction *I : Instrs)
 548     if (I->use_empty())
 549       I->eraseFromParent();
 550 }
 551
 552 std::pair<ArrayRef<Instruction *>, ArrayRef<Instruction *>>
 553 Vectorizer::splitOddVectorElts(ArrayRef<Instruction *> Chain,
 554                                unsigned ElementSizeBits) {
 555   unsigned ElementSizeBytes = ElementSizeBits / 8;
 556   unsigned SizeBytes = ElementSizeBytes * Chain.size();
 557   unsigned NumLeft = (SizeBytes - (SizeBytes % 4)) / ElementSizeBytes;
 558   if (NumLeft == Chain.size()) {
 559     if ((NumLeft & 1) == 0)
 560       NumLeft /= 2; // Split even in half
 561     else
 562       --NumLeft;    // Split off last element
 563   } else if (NumLeft == 0)
 564     NumLeft = 1;
 565   return std::make_pair(Chain.slice(0, NumLeft), Chain.slice(NumLeft));
 566 }
 567
 568 ArrayRef<Instruction *>
 569 Vectorizer::getVectorizablePrefix(ArrayRef<Instruction *> Chain) {
 570   // These are in BB order, unlike Chain, which is in address order.
 571   SmallVector<Instruction *, 16> MemoryInstrs;
 572   SmallVector<Instruction *, 16> ChainInstrs;
 573
 574   bool IsLoadChain = isa<LoadInst>(Chain[0]);
 575   LLVM_DEBUG({
 576     for (Instruction *I : Chain) {
 577       if (IsLoadChain)
 578         assert(isa<LoadInst>(I) &&
 579                "All elements of Chain must be loads, or all must be stores.");
 580       else
 581         assert(isa<StoreInst>(I) &&
 582                "All elements of Chain must be loads, or all must be stores.");
 583     }
 584   });
 585
 586   for (Instruction &I : make_range(getBoundaryInstrs(Chain))) {
 587     if (isa<LoadInst>(I) || isa<StoreInst>(I)) {
 588       if (!is_contained(Chain, &I))
 589         MemoryInstrs.push_back(&I);
 590       else
 591         ChainInstrs.push_back(&I);
 592     } else if (isa<IntrinsicInst>(&I) &&
 593                cast<IntrinsicInst>(&I)->getIntrinsicID() ==
 594                    Intrinsic::sideeffect) {
 595       // Ignore llvm.sideeffect calls.
 596     } else if (IsLoadChain && (I.mayWriteToMemory() || I.mayThrow())) {
 597       LLVM_DEBUG(dbgs() << "LSV: Found may-write/throw operation: " << I
 598                         << '\n');
 599       break;
 600     } else if (!IsLoadChain && (I.mayReadOrWriteMemory() || I.mayThrow())) {
 601       LLVM_DEBUG(dbgs() << "LSV: Found may-read/write/throw operation: " << I
 602                         << '\n');
 603       break;
 604     }
 605   }
 606
 607   OrderedBasicBlock OBB(Chain[0]->getParent());
 608
 609   // Loop until we find an instruction in ChainInstrs that we can't vectorize.
 610   unsigned ChainInstrIdx = 0;
 611   Instruction *BarrierMemoryInstr = nullptr;
 612
 613   for (unsigned E = ChainInstrs.size(); ChainInstrIdx < E; ++ChainInstrIdx) {
 614     Instruction *ChainInstr = ChainInstrs[ChainInstrIdx];
 615
 616     // If a barrier memory instruction was found, chain instructions that follow
 617     // will not be added to the valid prefix.
 618     if (BarrierMemoryInstr && OBB.dominates(BarrierMemoryInstr, ChainInstr))
 619       break;
 620
 621     // Check (in BB order) if any instruction prevents ChainInstr from being
 622     // vectorized. Find and store the first such "conflicting" instruction.
 623     for (Instruction *MemInstr : MemoryInstrs) {
 624       // If a barrier memory instruction was found, do not check past it.
 625       if (BarrierMemoryInstr && OBB.dominates(BarrierMemoryInstr, MemInstr))
 626         break;
 627
 628       auto *MemLoad = dyn_cast<LoadInst>(MemInstr);
 629       auto *ChainLoad = dyn_cast<LoadInst>(ChainInstr);
 630       if (MemLoad && ChainLoad)
 631         continue;
 632
 633       // We can ignore the alias if the we have a load store pair and the load
 634       // is known to be invariant. The load cannot be clobbered by the store.
 635       auto IsInvariantLoad = [](const LoadInst *LI) -> bool {
 636         return LI->getMetadata(LLVMContext::MD_invariant_load);
 637       };
 638
 639       // We can ignore the alias as long as the load comes before the store,
 640       // because that means we won't be moving the load past the store to
 641       // vectorize it (the vectorized load is inserted at the location of the
 642       // first load in the chain).
 643       if (isa<StoreInst>(MemInstr) && ChainLoad &&
 644           (IsInvariantLoad(ChainLoad) || OBB.dominates(ChainLoad, MemInstr)))
 645         continue;
 646
 647       // Same case, but in reverse.
 648       if (MemLoad && isa<StoreInst>(ChainInstr) &&
 649           (IsInvariantLoad(MemLoad) || OBB.dominates(MemLoad, ChainInstr)))
 650         continue;
 651
 652       if (!AA.isNoAlias(MemoryLocation::get(MemInstr),
 653                         MemoryLocation::get(ChainInstr))) {
 654         LLVM_DEBUG({
 655           dbgs() << "LSV: Found alias:\n"
 656                     "  Aliasing instruction and pointer:\n"
 657                  << "  " << *MemInstr << '\n'
 658                  << "  " << *getLoadStorePointerOperand(MemInstr) << '\n'
 659                  << "  Aliased instruction and pointer:\n"
 660                  << "  " << *ChainInstr << '\n'
 661                  << "  " << *getLoadStorePointerOperand(ChainInstr) << '\n';
 662         });
 663         // Save this aliasing memory instruction as a barrier, but allow other
 664         // instructions that precede the barrier to be vectorized with this one.
 665         BarrierMemoryInstr = MemInstr;
 666         break;
 667       }
 668     }
 669     // Continue the search only for store chains, since vectorizing stores that
 670     // precede an aliasing load is valid. Conversely, vectorizing loads is valid
 671     // up to an aliasing store, but should not pull loads from further down in
 672     // the basic block.
 673     if (IsLoadChain && BarrierMemoryInstr) {
 674       // The BarrierMemoryInstr is a store that precedes ChainInstr.
 675       assert(OBB.dominates(BarrierMemoryInstr, ChainInstr));
 676       break;
 677     }
 678   }
 679
 680   // Find the largest prefix of Chain whose elements are all in
 681   // ChainInstrs[0, ChainInstrIdx).  This is the largest vectorizable prefix of
 682   // Chain.  (Recall that Chain is in address order, but ChainInstrs is in BB
 683   // order.)
 684   SmallPtrSet<Instruction *, 8> VectorizableChainInstrs(
 685       ChainInstrs.begin(), ChainInstrs.begin() + ChainInstrIdx);
 686   unsigned ChainIdx = 0;
 687   for (unsigned ChainLen = Chain.size(); ChainIdx < ChainLen; ++ChainIdx) {
 688     if (!VectorizableChainInstrs.count(Chain[ChainIdx]))
 689       break;
 690   }
 691   return Chain.slice(0, ChainIdx);
 692 }
 693
 694 static ChainID getChainID(const Value *Ptr, const DataLayout &DL) {
 695   const Value *ObjPtr = GetUnderlyingObject(Ptr, DL);
 696   if (const auto *Sel = dyn_cast<SelectInst>(ObjPtr)) {
 697     // The select's themselves are distinct instructions even if they share the
 698     // same condition and evaluate to consecutive pointers for true and false
 699     // values of the condition. Therefore using the select's themselves for
 700     // grouping instructions would put consecutive accesses into different lists
 701     // and they won't be even checked for being consecutive, and won't be
 702     // vectorized.
 703     return Sel->getCondition();
 704   }
 705   return ObjPtr;
 706 }
 707
 708 std::pair<InstrListMap, InstrListMap>
 709 Vectorizer::collectInstructions(BasicBlock *BB) {
 710   InstrListMap LoadRefs;
 711   InstrListMap StoreRefs;
 712
 713   for (Instruction &I : *BB) {
 714     if (!I.mayReadOrWriteMemory())
 715       continue;
 716
 717     if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
 718       if (!LI->isSimple())
 719         continue;
 720
 721       // Skip if it's not legal.
 722       if (!TTI.isLegalToVectorizeLoad(LI))
 723         continue;
 724
 725       Type *Ty = LI->getType();
 726       if (!VectorType::isValidElementType(Ty->getScalarType()))
 727         continue;
 728
 729       // Skip weird non-byte sizes. They probably aren't worth the effort of
 730       // handling correctly.
 731       unsigned TySize = DL.getTypeSizeInBits(Ty);
 732       if ((TySize % 8) != 0)
 733         continue;
 734
 735       // Skip vectors of pointers. The vectorizeLoadChain/vectorizeStoreChain
 736       // functions are currently using an integer type for the vectorized
 737       // load/store, and does not support casting between the integer type and a
 738       // vector of pointers (e.g. i64 to <2 x i16*>)
 739       if (Ty->isVectorTy() && Ty->isPtrOrPtrVectorTy())
 740         continue;
 741
 742       Value *Ptr = LI->getPointerOperand();
 743       unsigned AS = Ptr->getType()->getPointerAddressSpace();
 744       unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
 745
 746       unsigned VF = VecRegSize / TySize;
 747       VectorType *VecTy = dyn_cast<VectorType>(Ty);
 748
 749       // No point in looking at these if they're too big to vectorize.
 750       if (TySize > VecRegSize / 2 ||
 751           (VecTy && TTI.getLoadVectorFactor(VF, TySize, TySize / 8, VecTy) == 0))
 752         continue;
 753
 754       // Make sure all the users of a vector are constant-index extracts.
 755       if (isa<VectorType>(Ty) && !llvm::all_of(LI->users(), [](const User *U) {
 756             const ExtractElementInst *EEI = dyn_cast<ExtractElementInst>(U);
 757             return EEI && isa<ConstantInt>(EEI->getOperand(1));
 758           }))
 759         continue;
 760
 761       // Save the load locations.
 762       const ChainID ID = getChainID(Ptr, DL);
 763       LoadRefs[ID].push_back(LI);
 764     } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
 765       if (!SI->isSimple())
 766         continue;
 767
 768       // Skip if it's not legal.
 769       if (!TTI.isLegalToVectorizeStore(SI))
 770         continue;
 771
 772       Type *Ty = SI->getValueOperand()->getType();
 773       if (!VectorType::isValidElementType(Ty->getScalarType()))
 774         continue;
 775
 776       // Skip vectors of pointers. The vectorizeLoadChain/vectorizeStoreChain
 777       // functions are currently using an integer type for the vectorized
 778       // load/store, and does not support casting between the integer type and a
 779       // vector of pointers (e.g. i64 to <2 x i16*>)
 780       if (Ty->isVectorTy() && Ty->isPtrOrPtrVectorTy())
 781         continue;
 782
 783       // Skip weird non-byte sizes. They probably aren't worth the effort of
 784       // handling correctly.
 785       unsigned TySize = DL.getTypeSizeInBits(Ty);
 786       if ((TySize % 8) != 0)
 787         continue;
 788
 789       Value *Ptr = SI->getPointerOperand();
 790       unsigned AS = Ptr->getType()->getPointerAddressSpace();
 791       unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
 792
 793       unsigned VF = VecRegSize / TySize;
 794       VectorType *VecTy = dyn_cast<VectorType>(Ty);
 795
 796       // No point in looking at these if they're too big to vectorize.
 797       if (TySize > VecRegSize / 2 ||
 798           (VecTy && TTI.getStoreVectorFactor(VF, TySize, TySize / 8, VecTy) == 0))
 799         continue;
 800
 801       if (isa<VectorType>(Ty) && !llvm::all_of(SI->users(), [](const User *U) {
 802             const ExtractElementInst *EEI = dyn_cast<ExtractElementInst>(U);
 803             return EEI && isa<ConstantInt>(EEI->getOperand(1));
 804           }))
 805         continue;
 806
 807       // Save store location.
 808       const ChainID ID = getChainID(Ptr, DL);
 809       StoreRefs[ID].push_back(SI);
 810     }
 811   }
 812
 813   return {LoadRefs, StoreRefs};
 814 }
 815
 816 bool Vectorizer::vectorizeChains(InstrListMap &Map) {
 817   bool Changed = false;
 818
 819   for (const std::pair<ChainID, InstrList> &Chain : Map) {
 820     unsigned Size = Chain.second.size();
 821     if (Size < 2)
 822       continue;
 823
 824     LLVM_DEBUG(dbgs() << "LSV: Analyzing a chain of length " << Size << ".\n");
 825
 826     // Process the stores in chunks of 64.
 827     for (unsigned CI = 0, CE = Size; CI < CE; CI += 64) {
 828       unsigned Len = std::min<unsigned>(CE - CI, 64);
 829       ArrayRef<Instruction *> Chunk(&Chain.second[CI], Len);
 830       Changed |= vectorizeInstructions(Chunk);
 831     }
 832   }
 833
 834   return Changed;
 835 }
 836
 837 bool Vectorizer::vectorizeInstructions(ArrayRef<Instruction *> Instrs) {
 838   LLVM_DEBUG(dbgs() << "LSV: Vectorizing " << Instrs.size()
 839                     << " instructions.\n");
 840   SmallVector<int, 16> Heads, Tails;
 841   int ConsecutiveChain[64];
 842
 843   // Do a quadratic search on all of the given loads/stores and find all of the
 844   // pairs of loads/stores that follow each other.
 845   for (int i = 0, e = Instrs.size(); i < e; ++i) {
 846     ConsecutiveChain[i] = -1;
 847     for (int j = e - 1; j >= 0; --j) {
 848       if (i == j)
 849         continue;
 850
 851       if (isConsecutiveAccess(Instrs[i], Instrs[j])) {
 852         if (ConsecutiveChain[i] != -1) {
 853           int CurDistance = std::abs(ConsecutiveChain[i] - i);
 854           int NewDistance = std::abs(ConsecutiveChain[i] - j);
 855           if (j < i || NewDistance > CurDistance)
 856             continue; // Should not insert.
 857         }
 858
 859         Tails.push_back(j);
 860         Heads.push_back(i);
 861         ConsecutiveChain[i] = j;
 862       }
 863     }
 864   }
 865
 866   bool Changed = false;
 867   SmallPtrSet<Instruction *, 16> InstructionsProcessed;
 868
 869   for (int Head : Heads) {
 870     if (InstructionsProcessed.count(Instrs[Head]))
 871       continue;
 872     bool LongerChainExists = false;
 873     for (unsigned TIt = 0; TIt < Tails.size(); TIt++)
 874       if (Head == Tails[TIt] &&
 875           !InstructionsProcessed.count(Instrs[Heads[TIt]])) {
 876         LongerChainExists = true;
 877         break;
 878       }
 879     if (LongerChainExists)
 880       continue;
 881
 882     // We found an instr that starts a chain. Now follow the chain and try to
 883     // vectorize it.
 884     SmallVector<Instruction *, 16> Operands;
 885     int I = Head;
 886     while (I != -1 && (is_contained(Tails, I) || is_contained(Heads, I))) {
 887       if (InstructionsProcessed.count(Instrs[I]))
 888         break;
 889
 890       Operands.push_back(Instrs[I]);
 891       I = ConsecutiveChain[I];
 892     }
 893
 894     bool Vectorized = false;
 895     if (isa<LoadInst>(*Operands.begin()))
 896       Vectorized = vectorizeLoadChain(Operands, &InstructionsProcessed);
 897     else
 898       Vectorized = vectorizeStoreChain(Operands, &InstructionsProcessed);
 899
 900     Changed |= Vectorized;
 901   }
 902
 903   return Changed;
 904 }
 905
 906 bool Vectorizer::vectorizeStoreChain(
 907     ArrayRef<Instruction *> Chain,
 908     SmallPtrSet<Instruction *, 16> *InstructionsProcessed) {
 909   StoreInst *S0 = cast<StoreInst>(Chain[0]);
 910
 911   // If the vector has an int element, default to int for the whole store.
 912   Type *StoreTy;
 913   for (Instruction *I : Chain) {
 914     StoreTy = cast<StoreInst>(I)->getValueOperand()->getType();
 915     if (StoreTy->isIntOrIntVectorTy())
 916       break;
 917
 918     if (StoreTy->isPtrOrPtrVectorTy()) {
 919       StoreTy = Type::getIntNTy(F.getParent()->getContext(),
 920                                 DL.getTypeSizeInBits(StoreTy));
 921       break;
 922     }
 923   }
 924
 925   unsigned Sz = DL.getTypeSizeInBits(StoreTy);
 926   unsigned AS = S0->getPointerAddressSpace();
 927   unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
 928   unsigned VF = VecRegSize / Sz;
 929   unsigned ChainSize = Chain.size();
 930   unsigned Alignment = getAlignment(S0);
 931
 932   if (!isPowerOf2_32(Sz) || VF < 2 || ChainSize < 2) {
 933     InstructionsProcessed->insert(Chain.begin(), Chain.end());
 934     return false;
 935   }
 936
 937   ArrayRef<Instruction *> NewChain = getVectorizablePrefix(Chain);
 938   if (NewChain.empty()) {
 939     // No vectorization possible.
 940     InstructionsProcessed->insert(Chain.begin(), Chain.end());
 941     return false;
 942   }
 943   if (NewChain.size() == 1) {
 944     // Failed after the first instruction. Discard it and try the smaller chain.
 945     InstructionsProcessed->insert(NewChain.front());
 946     return false;
 947   }
 948
 949   // Update Chain to the valid vectorizable subchain.
 950   Chain = NewChain;
 951   ChainSize = Chain.size();
 952
 953   // Check if it's legal to vectorize this chain. If not, split the chain and
 954   // try again.
 955   unsigned EltSzInBytes = Sz / 8;
 956   unsigned SzInBytes = EltSzInBytes * ChainSize;
 957   if (!TTI.isLegalToVectorizeStoreChain(SzInBytes, Alignment, AS)) {
 958     auto Chains = splitOddVectorElts(Chain, Sz);
 959     return vectorizeStoreChain(Chains.first, InstructionsProcessed) |
 960            vectorizeStoreChain(Chains.second, InstructionsProcessed);
 961   }
 962
 963   VectorType *VecTy;
 964   VectorType *VecStoreTy = dyn_cast<VectorType>(StoreTy);
 965   if (VecStoreTy)
 966     VecTy = VectorType::get(StoreTy->getScalarType(),
 967                             Chain.size() * VecStoreTy->getNumElements());
 968   else
 969     VecTy = VectorType::get(StoreTy, Chain.size());
 970
 971   // If it's more than the max vector size or the target has a better
 972   // vector factor, break it into two pieces.
 973   unsigned TargetVF = TTI.getStoreVectorFactor(VF, Sz, SzInBytes, VecTy);
 974   if (ChainSize > VF || (VF != TargetVF && TargetVF < ChainSize)) {
 975     LLVM_DEBUG(dbgs() << "LSV: Chain doesn't match with the vector factor."
 976                          " Creating two separate arrays.\n");
 977     return vectorizeStoreChain(Chain.slice(0, TargetVF),
 978                                InstructionsProcessed) |
 979            vectorizeStoreChain(Chain.slice(TargetVF), InstructionsProcessed);
 980   }
 981
 982   LLVM_DEBUG({
 983     dbgs() << "LSV: Stores to vectorize:\n";
 984     for (Instruction *I : Chain)
 985       dbgs() << "  " << *I << "\n";
 986   });
 987
 988   // We won't try again to vectorize the elements of the chain, regardless of
 989   // whether we succeed below.
 990   InstructionsProcessed->insert(Chain.begin(), Chain.end());
 991
 992   // If the store is going to be misaligned, don't vectorize it.
 993   if (accessIsMisaligned(SzInBytes, AS, Alignment)) {
 994     if (S0->getPointerAddressSpace() != 0)
 995       return false;
 996
 997     unsigned NewAlign = getOrEnforceKnownAlignment(S0->getPointerOperand(),
 998                                                    StackAdjustedAlignment,
 999                                                    DL, S0, nullptr, &DT);
1000     if (NewAlign < StackAdjustedAlignment)
1001       return false;
1002   }
1003
1004   BasicBlock::iterator First, Last;
1005   std::tie(First, Last) = getBoundaryInstrs(Chain);
1006   Builder.SetInsertPoint(&*Last);
1007
1008   Value *Vec = UndefValue::get(VecTy);
1009
1010   if (VecStoreTy) {
1011     unsigned VecWidth = VecStoreTy->getNumElements();
1012     for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
1013       StoreInst *Store = cast<StoreInst>(Chain[I]);
1014       for (unsigned J = 0, NE = VecStoreTy->getNumElements(); J != NE; ++J) {
1015         unsigned NewIdx = J + I * VecWidth;
1016         Value *Extract = Builder.CreateExtractElement(Store->getValueOperand(),
1017                                                       Builder.getInt32(J));
1018         if (Extract->getType() != StoreTy->getScalarType())
1019           Extract = Builder.CreateBitCast(Extract, StoreTy->getScalarType());
1020
1021         Value *Insert =
1022             Builder.CreateInsertElement(Vec, Extract, Builder.getInt32(NewIdx));
1023         Vec = Insert;
1024       }
1025     }
1026   } else {
1027     for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
1028       StoreInst *Store = cast<StoreInst>(Chain[I]);
1029       Value *Extract = Store->getValueOperand();
1030       if (Extract->getType() != StoreTy->getScalarType())
1031         Extract =
1032             Builder.CreateBitOrPointerCast(Extract, StoreTy->getScalarType());
1033
1034       Value *Insert =
1035           Builder.CreateInsertElement(Vec, Extract, Builder.getInt32(I));
1036       Vec = Insert;
1037     }
1038   }
1039
1040   // This cast is safe because Builder.CreateStore() always creates a bona fide
1041   // StoreInst.
1042   StoreInst *SI = cast<StoreInst>(
1043       Builder.CreateStore(Vec, Builder.CreateBitCast(S0->getPointerOperand(),
1044                                                      VecTy->getPointerTo(AS))));
1045   propagateMetadata(SI, Chain);
1046   SI->setAlignment(Alignment);
1047
1048   eraseInstructions(Chain);
1049   ++NumVectorInstructions;
1050   NumScalarsVectorized += Chain.size();
1051   return true;
1052 }
1053
1054 bool Vectorizer::vectorizeLoadChain(
1055     ArrayRef<Instruction *> Chain,
1056     SmallPtrSet<Instruction *, 16> *InstructionsProcessed) {
1057   LoadInst *L0 = cast<LoadInst>(Chain[0]);
1058
1059   // If the vector has an int element, default to int for the whole load.
1060   Type *LoadTy;
1061   for (const auto &V : Chain) {
1062     LoadTy = cast<LoadInst>(V)->getType();
1063     if (LoadTy->isIntOrIntVectorTy())
1064       break;
1065
1066     if (LoadTy->isPtrOrPtrVectorTy()) {
1067       LoadTy = Type::getIntNTy(F.getParent()->getContext(),
1068                                DL.getTypeSizeInBits(LoadTy));
1069       break;
1070     }
1071   }
1072
1073   unsigned Sz = DL.getTypeSizeInBits(LoadTy);
1074   unsigned AS = L0->getPointerAddressSpace();
1075   unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
1076   unsigned VF = VecRegSize / Sz;
1077   unsigned ChainSize = Chain.size();
1078   unsigned Alignment = getAlignment(L0);
1079
1080   if (!isPowerOf2_32(Sz) || VF < 2 || ChainSize < 2) {
1081     InstructionsProcessed->insert(Chain.begin(), Chain.end());
1082     return false;
1083   }
1084
1085   ArrayRef<Instruction *> NewChain = getVectorizablePrefix(Chain);
1086   if (NewChain.empty()) {
1087     // No vectorization possible.
1088     InstructionsProcessed->insert(Chain.begin(), Chain.end());
1089     return false;
1090   }
1091   if (NewChain.size() == 1) {
1092     // Failed after the first instruction. Discard it and try the smaller chain.
1093     InstructionsProcessed->insert(NewChain.front());
1094     return false;
1095   }
1096
1097   // Update Chain to the valid vectorizable subchain.
1098   Chain = NewChain;
1099   ChainSize = Chain.size();
1100
1101   // Check if it's legal to vectorize this chain. If not, split the chain and
1102   // try again.
1103   unsigned EltSzInBytes = Sz / 8;
1104   unsigned SzInBytes = EltSzInBytes * ChainSize;
1105   if (!TTI.isLegalToVectorizeLoadChain(SzInBytes, Alignment, AS)) {
1106     auto Chains = splitOddVectorElts(Chain, Sz);
1107     return vectorizeLoadChain(Chains.first, InstructionsProcessed) |
1108            vectorizeLoadChain(Chains.second, InstructionsProcessed);
1109   }
1110
1111   VectorType *VecTy;
1112   VectorType *VecLoadTy = dyn_cast<VectorType>(LoadTy);
1113   if (VecLoadTy)
1114     VecTy = VectorType::get(LoadTy->getScalarType(),
1115                             Chain.size() * VecLoadTy->getNumElements());
1116   else
1117     VecTy = VectorType::get(LoadTy, Chain.size());
1118
1119   // If it's more than the max vector size or the target has a better
1120   // vector factor, break it into two pieces.
1121   unsigned TargetVF = TTI.getLoadVectorFactor(VF, Sz, SzInBytes, VecTy);
1122   if (ChainSize > VF || (VF != TargetVF && TargetVF < ChainSize)) {
1123     LLVM_DEBUG(dbgs() << "LSV: Chain doesn't match with the vector factor."
1124                          " Creating two separate arrays.\n");
1125     return vectorizeLoadChain(Chain.slice(0, TargetVF), InstructionsProcessed) |
1126            vectorizeLoadChain(Chain.slice(TargetVF), InstructionsProcessed);
1127   }
1128
1129   // We won't try again to vectorize the elements of the chain, regardless of
1130   // whether we succeed below.
1131   InstructionsProcessed->insert(Chain.begin(), Chain.end());
1132
1133   // If the load is going to be misaligned, don't vectorize it.
1134   if (accessIsMisaligned(SzInBytes, AS, Alignment)) {
1135     if (L0->getPointerAddressSpace() != 0)
1136       return false;
1137
1138     unsigned NewAlign = getOrEnforceKnownAlignment(L0->getPointerOperand(),
1139                                                    StackAdjustedAlignment,
1140                                                    DL, L0, nullptr, &DT);
1141     if (NewAlign < StackAdjustedAlignment)
1142       return false;
1143
1144     Alignment = NewAlign;
1145   }
1146
1147   LLVM_DEBUG({
1148     dbgs() << "LSV: Loads to vectorize:\n";
1149     for (Instruction *I : Chain)
1150       I->dump();
1151   });
1152
1153   // getVectorizablePrefix already computed getBoundaryInstrs.  The value of
1154   // Last may have changed since then, but the value of First won't have.  If it
1155   // matters, we could compute getBoundaryInstrs only once and reuse it here.
1156   BasicBlock::iterator First, Last;
1157   std::tie(First, Last) = getBoundaryInstrs(Chain);
1158   Builder.SetInsertPoint(&*First);
1159
1160   Value *Bitcast =
1161       Builder.CreateBitCast(L0->getPointerOperand(), VecTy->getPointerTo(AS));
1162   // This cast is safe because Builder.CreateLoad always creates a bona fide
1163   // LoadInst.
1164   LoadInst *LI = cast<LoadInst>(Builder.CreateLoad(Bitcast));
1165   propagateMetadata(LI, Chain);
1166   LI->setAlignment(Alignment);
1167
1168   if (VecLoadTy) {
1169     SmallVector<Instruction *, 16> InstrsToErase;
1170
1171     unsigned VecWidth = VecLoadTy->getNumElements();
1172     for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
1173       for (auto Use : Chain[I]->users()) {
1174         // All users of vector loads are ExtractElement instructions with
1175         // constant indices, otherwise we would have bailed before now.
1176         Instruction *UI = cast<Instruction>(Use);
1177         unsigned Idx = cast<ConstantInt>(UI->getOperand(1))->getZExtValue();
1178         unsigned NewIdx = Idx + I * VecWidth;
1179         Value *V = Builder.CreateExtractElement(LI, Builder.getInt32(NewIdx),
1180                                                 UI->getName());
1181         if (V->getType() != UI->getType())
1182           V = Builder.CreateBitCast(V, UI->getType());
1183
1184         // Replace the old instruction.
1185         UI->replaceAllUsesWith(V);
1186         InstrsToErase.push_back(UI);
1187       }
1188     }
1189
1190     // Bitcast might not be an Instruction, if the value being loaded is a
1191     // constant.  In that case, no need to reorder anything.
1192     if (Instruction *BitcastInst = dyn_cast<Instruction>(Bitcast))
1193       reorder(BitcastInst);
1194
1195     for (auto I : InstrsToErase)
1196       I->eraseFromParent();
1197   } else {
1198     for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
1199       Value *CV = Chain[I];
1200       Value *V =
1201           Builder.CreateExtractElement(LI, Builder.getInt32(I), CV->getName());
1202       if (V->getType() != CV->getType()) {
1203         V = Builder.CreateBitOrPointerCast(V, CV->getType());
1204       }
1205
1206       // Replace the old instruction.
1207       CV->replaceAllUsesWith(V);
1208     }
1209
1210     if (Instruction *BitcastInst = dyn_cast<Instruction>(Bitcast))
1211       reorder(BitcastInst);
1212   }
1213
1214   eraseInstructions(Chain);
1215
1216   ++NumVectorInstructions;
1217   NumScalarsVectorized += Chain.size();
1218   return true;
1219 }
1220
1221 bool Vectorizer::accessIsMisaligned(unsigned SzInBytes, unsigned AddressSpace,
1222                                     unsigned Alignment) {
1223   if (Alignment % SzInBytes == 0)
1224     return false;
1225
1226   bool Fast = false;
1227   bool Allows = TTI.allowsMisalignedMemoryAccesses(F.getParent()->getContext(),
1228                                                    SzInBytes * 8, AddressSpace,
1229                                                    Alignment, &Fast);
1230   LLVM_DEBUG(dbgs() << "LSV: Target said misaligned is allowed? " << Allows
1231                     << " and fast? " << Fast << "\n";);
1232   return !Allows || !Fast;
1233 }