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 //===----------------------------------------------------------------------===//
  11
  12 #include "llvm/ADT/MapVector.h"
  13 #include "llvm/ADT/PostOrderIterator.h"
  14 #include "llvm/ADT/SetVector.h"
  15 #include "llvm/ADT/Statistic.h"
  16 #include "llvm/ADT/Triple.h"
  17 #include "llvm/Analysis/AliasAnalysis.h"
  18 #include "llvm/Analysis/ScalarEvolution.h"
  19 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
  20 #include "llvm/Analysis/TargetTransformInfo.h"
  21 #include "llvm/Analysis/ValueTracking.h"
  22 #include "llvm/Analysis/VectorUtils.h"
  23 #include "llvm/IR/DataLayout.h"
  24 #include "llvm/IR/Dominators.h"
  25 #include "llvm/IR/IRBuilder.h"
  26 #include "llvm/IR/Instructions.h"
  27 #include "llvm/IR/Module.h"
  28 #include "llvm/IR/Type.h"
  29 #include "llvm/IR/Value.h"
  30 #include "llvm/Support/CommandLine.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/raw_ostream.h"
  33 #include "llvm/Transforms/Vectorize.h"
  34
  35 using namespace llvm;
  36
  37 #define DEBUG_TYPE "load-store-vectorizer"
  38 STATISTIC(NumVectorInstructions, "Number of vector accesses generated");
  39 STATISTIC(NumScalarsVectorized, "Number of scalar accesses vectorized");
  40
  41 namespace {
  42
  43 // TODO: Remove this
  44 static const unsigned TargetBaseAlign = 4;
  45
  46 class Vectorizer {
  47   typedef SmallVector<Value *, 8> ValueList;
  48   typedef MapVector<Value *, ValueList> ValueListMap;
  49
  50   Function &F;
  51   AliasAnalysis &AA;
  52   DominatorTree &DT;
  53   ScalarEvolution &SE;
  54   TargetTransformInfo &TTI;
  55   const DataLayout &DL;
  56   IRBuilder<> Builder;
  57   ValueListMap StoreRefs;
  58   ValueListMap LoadRefs;
  59
  60 public:
  61   Vectorizer(Function &F, AliasAnalysis &AA, DominatorTree &DT,
  62              ScalarEvolution &SE, TargetTransformInfo &TTI)
  63       : F(F), AA(AA), DT(DT), SE(SE), TTI(TTI),
  64         DL(F.getParent()->getDataLayout()), Builder(SE.getContext()) {}
  65
  66   bool run();
  67
  68 private:
  69   Value *getPointerOperand(Value *I);
  70
  71   unsigned getPointerAddressSpace(Value *I);
  72
  73   unsigned getAlignment(LoadInst *LI) const {
  74     unsigned Align = LI->getAlignment();
  75     if (Align != 0)
  76       return Align;
  77
  78     return DL.getABITypeAlignment(LI->getType());
  79   }
  80
  81   unsigned getAlignment(StoreInst *SI) const {
  82     unsigned Align = SI->getAlignment();
  83     if (Align != 0)
  84       return Align;
  85
  86     return DL.getABITypeAlignment(SI->getValueOperand()->getType());
  87   }
  88
  89   bool isConsecutiveAccess(Value *A, Value *B);
  90
  91   /// After vectorization, reorder the instructions that I depends on
  92   /// (the instructions defining its operands), to ensure they dominate I.
  93   void reorder(Instruction *I);
  94
  95   /// Returns the first and the last instructions in Chain.
  96   std::pair<BasicBlock::iterator, BasicBlock::iterator>
  97   getBoundaryInstrs(ArrayRef<Value *> Chain);
  98
  99   /// Erases the original instructions after vectorizing.
 100   void eraseInstructions(ArrayRef<Value *> Chain);
 101
 102   /// "Legalize" the vector type that would be produced by combining \p
 103   /// ElementSizeBits elements in \p Chain. Break into two pieces such that the
 104   /// total size of each piece is 1, 2 or a multiple of 4 bytes. \p Chain is
 105   /// expected to have more than 4 elements.
 106   std::pair<ArrayRef<Value *>, ArrayRef<Value *>>
 107   splitOddVectorElts(ArrayRef<Value *> Chain, unsigned ElementSizeBits);
 108
 109   /// Checks for instructions which may affect the memory accessed
 110   /// in the chain between \p From and \p To. Returns Index, where
 111   /// \p Chain[0, Index) is the largest vectorizable chain prefix.
 112   /// The elements of \p Chain should be all loads or all stores.
 113   unsigned getVectorizablePrefixEndIdx(ArrayRef<Value *> Chain,
 114                                        BasicBlock::iterator From,
 115                                        BasicBlock::iterator To);
 116
 117   /// Collects load and store instructions to vectorize.
 118   void collectInstructions(BasicBlock *BB);
 119
 120   /// Processes the collected instructions, the \p Map. The elements of \p Map
 121   /// should be all loads or all stores.
 122   bool vectorizeChains(ValueListMap &Map);
 123
 124   /// Finds the load/stores to consecutive memory addresses and vectorizes them.
 125   bool vectorizeInstructions(ArrayRef<Value *> Instrs);
 126
 127   /// Vectorizes the load instructions in Chain.
 128   bool vectorizeLoadChain(ArrayRef<Value *> Chain,
 129                           SmallPtrSet<Value *, 16> *InstructionsProcessed);
 130
 131   /// Vectorizes the store instructions in Chain.
 132   bool vectorizeStoreChain(ArrayRef<Value *> Chain,
 133                            SmallPtrSet<Value *, 16> *InstructionsProcessed);
 134
 135   /// Check if this load/store access is misaligned accesses
 136   bool accessIsMisaligned(unsigned SzInBytes, unsigned AddressSpace,
 137                           unsigned Alignment);
 138 };
 139
 140 class LoadStoreVectorizer : public FunctionPass {
 141 public:
 142   static char ID;
 143
 144   LoadStoreVectorizer() : FunctionPass(ID) {
 145     initializeLoadStoreVectorizerPass(*PassRegistry::getPassRegistry());
 146   }
 147
 148   bool runOnFunction(Function &F) override;
 149
 150   const char *getPassName() const override {
 151     return "GPU Load and Store Vectorizer";
 152   }
 153
 154   void getAnalysisUsage(AnalysisUsage &AU) const override {
 155     AU.addRequired<AAResultsWrapperPass>();
 156     AU.addRequired<ScalarEvolutionWrapperPass>();
 157     AU.addRequired<DominatorTreeWrapperPass>();
 158     AU.addRequired<TargetTransformInfoWrapperPass>();
 159     AU.setPreservesCFG();
 160   }
 161 };
 162 }
 163
 164 INITIALIZE_PASS_BEGIN(LoadStoreVectorizer, DEBUG_TYPE,
 165                       "Vectorize load and Store instructions", false, false)
 166 INITIALIZE_PASS_DEPENDENCY(SCEVAAWrapperPass)
 167 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 168 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
 169 INITIALIZE_PASS_DEPENDENCY(GlobalsAAWrapperPass)
 170 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
 171 INITIALIZE_PASS_END(LoadStoreVectorizer, DEBUG_TYPE,
 172                     "Vectorize load and store instructions", false, false)
 173
 174 char LoadStoreVectorizer::ID = 0;
 175
 176 Pass *llvm::createLoadStoreVectorizerPass() {
 177   return new LoadStoreVectorizer();
 178 }
 179
 180 bool LoadStoreVectorizer::runOnFunction(Function &F) {
 181   // Don't vectorize when the attribute NoImplicitFloat is used.
 182   if (skipFunction(F) || F.hasFnAttribute(Attribute::NoImplicitFloat))
 183     return false;
 184
 185   AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
 186   DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 187   ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 188   TargetTransformInfo &TTI =
 189       getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 190
 191   Vectorizer V(F, AA, DT, SE, TTI);
 192   return V.run();
 193 }
 194
 195 // Vectorizer Implementation
 196 bool Vectorizer::run() {
 197   bool Changed = false;
 198
 199   // Scan the blocks in the function in post order.
 200   for (BasicBlock *BB : post_order(&F)) {
 201     collectInstructions(BB);
 202     Changed |= vectorizeChains(LoadRefs);
 203     Changed |= vectorizeChains(StoreRefs);
 204   }
 205
 206   return Changed;
 207 }
 208
 209 Value *Vectorizer::getPointerOperand(Value *I) {
 210   if (LoadInst *LI = dyn_cast<LoadInst>(I))
 211     return LI->getPointerOperand();
 212   if (StoreInst *SI = dyn_cast<StoreInst>(I))
 213     return SI->getPointerOperand();
 214   return nullptr;
 215 }
 216
 217 unsigned Vectorizer::getPointerAddressSpace(Value *I) {
 218   if (LoadInst *L = dyn_cast<LoadInst>(I))
 219     return L->getPointerAddressSpace();
 220   if (StoreInst *S = dyn_cast<StoreInst>(I))
 221     return S->getPointerAddressSpace();
 222   return -1;
 223 }
 224
 225 // FIXME: Merge with llvm::isConsecutiveAccess
 226 bool Vectorizer::isConsecutiveAccess(Value *A, Value *B) {
 227   Value *PtrA = getPointerOperand(A);
 228   Value *PtrB = getPointerOperand(B);
 229   unsigned ASA = getPointerAddressSpace(A);
 230   unsigned ASB = getPointerAddressSpace(B);
 231
 232   // Check that the address spaces match and that the pointers are valid.
 233   if (!PtrA || !PtrB || (ASA != ASB))
 234     return false;
 235
 236   // Make sure that A and B are different pointers of the same size type.
 237   unsigned PtrBitWidth = DL.getPointerSizeInBits(ASA);
 238   Type *PtrATy = PtrA->getType()->getPointerElementType();
 239   Type *PtrBTy = PtrB->getType()->getPointerElementType();
 240   if (PtrA == PtrB ||
 241       DL.getTypeStoreSize(PtrATy) != DL.getTypeStoreSize(PtrBTy) ||
 242       DL.getTypeStoreSize(PtrATy->getScalarType()) !=
 243           DL.getTypeStoreSize(PtrBTy->getScalarType()))
 244     return false;
 245
 246   APInt Size(PtrBitWidth, DL.getTypeStoreSize(PtrATy));
 247
 248   APInt OffsetA(PtrBitWidth, 0), OffsetB(PtrBitWidth, 0);
 249   PtrA = PtrA->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetA);
 250   PtrB = PtrB->stripAndAccumulateInBoundsConstantOffsets(DL, OffsetB);
 251
 252   APInt OffsetDelta = OffsetB - OffsetA;
 253
 254   // Check if they are based on the same pointer. That makes the offsets
 255   // sufficient.
 256   if (PtrA == PtrB)
 257     return OffsetDelta == Size;
 258
 259   // Compute the necessary base pointer delta to have the necessary final delta
 260   // equal to the size.
 261   APInt BaseDelta = Size - OffsetDelta;
 262
 263   // Compute the distance with SCEV between the base pointers.
 264   const SCEV *PtrSCEVA = SE.getSCEV(PtrA);
 265   const SCEV *PtrSCEVB = SE.getSCEV(PtrB);
 266   const SCEV *C = SE.getConstant(BaseDelta);
 267   const SCEV *X = SE.getAddExpr(PtrSCEVA, C);
 268   if (X == PtrSCEVB)
 269     return true;
 270
 271   // Sometimes even this doesn't work, because SCEV can't always see through
 272   // patterns that look like (gep (ext (add (shl X, C1), C2))). Try checking
 273   // things the hard way.
 274
 275   // Look through GEPs after checking they're the same except for the last
 276   // index.
 277   GetElementPtrInst *GEPA = dyn_cast<GetElementPtrInst>(getPointerOperand(A));
 278   GetElementPtrInst *GEPB = dyn_cast<GetElementPtrInst>(getPointerOperand(B));
 279   if (!GEPA || !GEPB || GEPA->getNumOperands() != GEPB->getNumOperands())
 280     return false;
 281   unsigned FinalIndex = GEPA->getNumOperands() - 1;
 282   for (unsigned i = 0; i < FinalIndex; i++)
 283     if (GEPA->getOperand(i) != GEPB->getOperand(i))
 284       return false;
 285
 286   Instruction *OpA = dyn_cast<Instruction>(GEPA->getOperand(FinalIndex));
 287   Instruction *OpB = dyn_cast<Instruction>(GEPB->getOperand(FinalIndex));
 288   if (!OpA || !OpB || OpA->getOpcode() != OpB->getOpcode() ||
 289       OpA->getType() != OpB->getType())
 290     return false;
 291
 292   // Only look through a ZExt/SExt.
 293   if (!isa<SExtInst>(OpA) && !isa<ZExtInst>(OpA))
 294     return false;
 295
 296   bool Signed = isa<SExtInst>(OpA);
 297
 298   OpA = dyn_cast<Instruction>(OpA->getOperand(0));
 299   OpB = dyn_cast<Instruction>(OpB->getOperand(0));
 300   if (!OpA || !OpB || OpA->getType() != OpB->getType())
 301     return false;
 302
 303   // Now we need to prove that adding 1 to OpA won't overflow.
 304   bool Safe = false;
 305   // First attempt: if OpB is an add with NSW/NUW, and OpB is 1 added to OpA,
 306   // we're okay.
 307   if (OpB->getOpcode() == Instruction::Add &&
 308       isa<ConstantInt>(OpB->getOperand(1)) &&
 309       cast<ConstantInt>(OpB->getOperand(1))->getSExtValue() > 0) {
 310     if (Signed)
 311       Safe = cast<BinaryOperator>(OpB)->hasNoSignedWrap();
 312     else
 313       Safe = cast<BinaryOperator>(OpB)->hasNoUnsignedWrap();
 314   }
 315
 316   unsigned BitWidth = OpA->getType()->getScalarSizeInBits();
 317
 318   // Second attempt:
 319   // If any bits are known to be zero other than the sign bit in OpA, we can
 320   // add 1 to it while guaranteeing no overflow of any sort.
 321   if (!Safe) {
 322     APInt KnownZero(BitWidth, 0);
 323     APInt KnownOne(BitWidth, 0);
 324     computeKnownBits(OpA, KnownZero, KnownOne, DL, 0, nullptr, OpA, &DT);
 325     KnownZero &= ~APInt::getHighBitsSet(BitWidth, 1);
 326     if (KnownZero != 0)
 327       Safe = true;
 328   }
 329
 330   if (!Safe)
 331     return false;
 332
 333   const SCEV *OffsetSCEVA = SE.getSCEV(OpA);
 334   const SCEV *OffsetSCEVB = SE.getSCEV(OpB);
 335   const SCEV *One = SE.getConstant(APInt(BitWidth, 1));
 336   const SCEV *X2 = SE.getAddExpr(OffsetSCEVA, One);
 337   return X2 == OffsetSCEVB;
 338 }
 339
 340 void Vectorizer::reorder(Instruction *I) {
 341   SmallPtrSet<Instruction *, 16> InstructionsToMove;
 342   SmallVector<Instruction *, 16> Worklist;
 343
 344   Worklist.push_back(I);
 345   while (!Worklist.empty()) {
 346     Instruction *IW = Worklist.pop_back_val();
 347     int NumOperands = IW->getNumOperands();
 348     for (int i = 0; i < NumOperands; i++) {
 349       Instruction *IM = dyn_cast<Instruction>(IW->getOperand(i));
 350       if (!IM || IM->getOpcode() == Instruction::PHI)
 351         continue;
 352
 353       if (!DT.dominates(IM, I)) {
 354         InstructionsToMove.insert(IM);
 355         Worklist.push_back(IM);
 356         assert(IM->getParent() == IW->getParent() &&
 357                "Instructions to move should be in the same basic block");
 358       }
 359     }
 360   }
 361
 362   // All instructions to move should follow I. Start from I, not from begin().
 363   for (auto BBI = I->getIterator(), E = I->getParent()->end(); BBI != E;
 364        ++BBI) {
 365     if (!is_contained(InstructionsToMove, &*BBI))
 366       continue;
 367     Instruction *IM = &*BBI;
 368     --BBI;
 369     IM->removeFromParent();
 370     IM->insertBefore(I);
 371   }
 372 }
 373
 374 std::pair<BasicBlock::iterator, BasicBlock::iterator>
 375 Vectorizer::getBoundaryInstrs(ArrayRef<Value *> Chain) {
 376   Instruction *C0 = cast<Instruction>(Chain[0]);
 377   BasicBlock::iterator FirstInstr = C0->getIterator();
 378   BasicBlock::iterator LastInstr = C0->getIterator();
 379
 380   BasicBlock *BB = C0->getParent();
 381   unsigned NumFound = 0;
 382   for (Instruction &I : *BB) {
 383     if (!is_contained(Chain, &I))
 384       continue;
 385
 386     ++NumFound;
 387     if (NumFound == 1) {
 388       FirstInstr = I.getIterator();
 389     }
 390     if (NumFound == Chain.size()) {
 391       LastInstr = I.getIterator();
 392       break;
 393     }
 394   }
 395
 396   // Range is [first, last).
 397   return std::make_pair(FirstInstr, ++LastInstr);
 398 }
 399
 400 void Vectorizer::eraseInstructions(ArrayRef<Value *> Chain) {
 401   SmallVector<Instruction *, 16> Instrs;
 402   for (Value *V : Chain) {
 403     Value *PtrOperand = getPointerOperand(V);
 404     assert(PtrOperand && "Instruction must have a pointer operand.");
 405     Instrs.push_back(cast<Instruction>(V));
 406     if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(PtrOperand))
 407       Instrs.push_back(GEP);
 408   }
 409
 410   // Erase instructions.
 411   for (Value *V : Instrs) {
 412     Instruction *Instr = cast<Instruction>(V);
 413     if (Instr->use_empty())
 414       Instr->eraseFromParent();
 415   }
 416 }
 417
 418 std::pair<ArrayRef<Value *>, ArrayRef<Value *>>
 419 Vectorizer::splitOddVectorElts(ArrayRef<Value *> Chain,
 420                                unsigned ElementSizeBits) {
 421   unsigned ElemSizeInBytes = ElementSizeBits / 8;
 422   unsigned SizeInBytes = ElemSizeInBytes * Chain.size();
 423   unsigned NumRight = (SizeInBytes % 4) / ElemSizeInBytes;
 424   unsigned NumLeft = Chain.size() - NumRight;
 425   return std::make_pair(Chain.slice(0, NumLeft), Chain.slice(NumLeft));
 426 }
 427
 428 unsigned Vectorizer::getVectorizablePrefixEndIdx(ArrayRef<Value *> Chain,
 429                                                  BasicBlock::iterator From,
 430                                                  BasicBlock::iterator To) {
 431   SmallVector<std::pair<Value *, unsigned>, 16> MemoryInstrs;
 432   SmallVector<std::pair<Value *, unsigned>, 16> ChainInstrs;
 433
 434   unsigned InstrIdx = 0;
 435   for (auto I = From; I != To; ++I, ++InstrIdx) {
 436     if (isa<LoadInst>(I) || isa<StoreInst>(I)) {
 437       if (!is_contained(Chain, &*I))
 438         MemoryInstrs.push_back({&*I, InstrIdx});
 439       else
 440         ChainInstrs.push_back({&*I, InstrIdx});
 441     } else if (I->mayHaveSideEffects()) {
 442       DEBUG(dbgs() << "LSV: Found side-effecting operation: " << *I << '\n');
 443       return 0;
 444     }
 445   }
 446
 447   assert(Chain.size() == ChainInstrs.size() &&
 448          "All instructions in the Chain must exist in [From, To).");
 449
 450   unsigned ChainIdx = 0;
 451   for (auto EntryChain : ChainInstrs) {
 452     Value *ChainInstrValue = EntryChain.first;
 453     unsigned ChainInstrIdx = EntryChain.second;
 454     for (auto EntryMem : MemoryInstrs) {
 455       Value *MemInstrValue = EntryMem.first;
 456       unsigned MemInstrIdx = EntryMem.second;
 457       if (isa<LoadInst>(MemInstrValue) && isa<LoadInst>(ChainInstrValue))
 458         continue;
 459
 460       // We can ignore the alias as long as the load comes before the store,
 461       // because that means we won't be moving the load past the store to
 462       // vectorize it (the vectorized load is inserted at the location of the
 463       // first load in the chain).
 464       if (isa<StoreInst>(MemInstrValue) && isa<LoadInst>(ChainInstrValue) &&
 465           ChainInstrIdx < MemInstrIdx)
 466         continue;
 467
 468       // Same case, but in reverse.
 469       if (isa<LoadInst>(MemInstrValue) && isa<StoreInst>(ChainInstrValue) &&
 470           ChainInstrIdx > MemInstrIdx)
 471         continue;
 472
 473       Instruction *M0 = cast<Instruction>(MemInstrValue);
 474       Instruction *M1 = cast<Instruction>(ChainInstrValue);
 475
 476       if (!AA.isNoAlias(MemoryLocation::get(M0), MemoryLocation::get(M1))) {
 477         DEBUG({
 478           Value *Ptr0 = getPointerOperand(M0);
 479           Value *Ptr1 = getPointerOperand(M1);
 480
 481           dbgs() << "LSV: Found alias.\n"
 482                     "        Aliasing instruction and pointer:\n"
 483                  << *MemInstrValue << " aliases " << *Ptr0 << '\n'
 484                  << "        Aliased instruction and pointer:\n"
 485                  << *ChainInstrValue << " aliases " << *Ptr1 << '\n';
 486         });
 487
 488         return ChainIdx;
 489       }
 490     }
 491     ChainIdx++;
 492   }
 493   return Chain.size();
 494 }
 495
 496 void Vectorizer::collectInstructions(BasicBlock *BB) {
 497   LoadRefs.clear();
 498   StoreRefs.clear();
 499
 500   for (Instruction &I : *BB) {
 501     if (!I.mayReadOrWriteMemory())
 502       continue;
 503
 504     if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
 505       if (!LI->isSimple())
 506         continue;
 507
 508       Type *Ty = LI->getType();
 509       if (!VectorType::isValidElementType(Ty->getScalarType()))
 510         continue;
 511
 512       // Skip weird non-byte sizes. They probably aren't worth the effort of
 513       // handling correctly.
 514       unsigned TySize = DL.getTypeSizeInBits(Ty);
 515       if (TySize < 8)
 516         continue;
 517
 518       Value *Ptr = LI->getPointerOperand();
 519       unsigned AS = Ptr->getType()->getPointerAddressSpace();
 520       unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
 521
 522       // No point in looking at these if they're too big to vectorize.
 523       if (TySize > VecRegSize / 2)
 524         continue;
 525
 526       // Make sure all the users of a vector are constant-index extracts.
 527       if (isa<VectorType>(Ty) && !all_of(LI->users(), [LI](const User *U) {
 528             const Instruction *UI = cast<Instruction>(U);
 529             return isa<ExtractElementInst>(UI) &&
 530                    isa<ConstantInt>(UI->getOperand(1));
 531           }))
 532         continue;
 533
 534       // TODO: Target hook to filter types.
 535
 536       // Save the load locations.
 537       Value *ObjPtr = GetUnderlyingObject(Ptr, DL);
 538       LoadRefs[ObjPtr].push_back(LI);
 539
 540     } else if (StoreInst *SI = dyn_cast<StoreInst>(&I)) {
 541       if (!SI->isSimple())
 542         continue;
 543
 544       Type *Ty = SI->getValueOperand()->getType();
 545       if (!VectorType::isValidElementType(Ty->getScalarType()))
 546         continue;
 547
 548       // Skip weird non-byte sizes. They probably aren't worth the effort of
 549       // handling correctly.
 550       unsigned TySize = DL.getTypeSizeInBits(Ty);
 551       if (TySize < 8)
 552         continue;
 553
 554       Value *Ptr = SI->getPointerOperand();
 555       unsigned AS = Ptr->getType()->getPointerAddressSpace();
 556       unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
 557       if (TySize > VecRegSize / 2)
 558         continue;
 559
 560       if (isa<VectorType>(Ty) && !all_of(SI->users(), [SI](const User *U) {
 561             const Instruction *UI = cast<Instruction>(U);
 562             return isa<ExtractElementInst>(UI) &&
 563                    isa<ConstantInt>(UI->getOperand(1));
 564           }))
 565         continue;
 566
 567       // Save store location.
 568       Value *ObjPtr = GetUnderlyingObject(Ptr, DL);
 569       StoreRefs[ObjPtr].push_back(SI);
 570     }
 571   }
 572 }
 573
 574 bool Vectorizer::vectorizeChains(ValueListMap &Map) {
 575   bool Changed = false;
 576
 577   for (const std::pair<Value *, ValueList> &Chain : Map) {
 578     unsigned Size = Chain.second.size();
 579     if (Size < 2)
 580       continue;
 581
 582     DEBUG(dbgs() << "LSV: Analyzing a chain of length " << Size << ".\n");
 583
 584     // Process the stores in chunks of 64.
 585     for (unsigned CI = 0, CE = Size; CI < CE; CI += 64) {
 586       unsigned Len = std::min<unsigned>(CE - CI, 64);
 587       ArrayRef<Value *> Chunk(&Chain.second[CI], Len);
 588       Changed |= vectorizeInstructions(Chunk);
 589     }
 590   }
 591
 592   return Changed;
 593 }
 594
 595 bool Vectorizer::vectorizeInstructions(ArrayRef<Value *> Instrs) {
 596   DEBUG(dbgs() << "LSV: Vectorizing " << Instrs.size() << " instructions.\n");
 597   SmallSetVector<int, 16> Heads, Tails;
 598   int ConsecutiveChain[64];
 599
 600   // Do a quadratic search on all of the given stores and find all of the pairs
 601   // of stores that follow each other.
 602   for (int i = 0, e = Instrs.size(); i < e; ++i) {
 603     ConsecutiveChain[i] = -1;
 604     for (int j = e - 1; j >= 0; --j) {
 605       if (i == j)
 606         continue;
 607
 608       if (isConsecutiveAccess(Instrs[i], Instrs[j])) {
 609         if (ConsecutiveChain[i] != -1) {
 610           int CurDistance = std::abs(ConsecutiveChain[i] - i);
 611           int NewDistance = std::abs(ConsecutiveChain[i] - j);
 612           if (j < i || NewDistance > CurDistance)
 613             continue; // Should not insert.
 614         }
 615
 616         Tails.insert(j);
 617         Heads.insert(i);
 618         ConsecutiveChain[i] = j;
 619       }
 620     }
 621   }
 622
 623   bool Changed = false;
 624   SmallPtrSet<Value *, 16> InstructionsProcessed;
 625
 626   for (int Head : Heads) {
 627     if (InstructionsProcessed.count(Instrs[Head]))
 628       continue;
 629     bool longerChainExists = false;
 630     for (unsigned TIt = 0; TIt < Tails.size(); TIt++)
 631       if (Head == Tails[TIt] &&
 632           !InstructionsProcessed.count(Instrs[Heads[TIt]])) {
 633         longerChainExists = true;
 634         break;
 635       }
 636     if (longerChainExists)
 637       continue;
 638
 639     // We found an instr that starts a chain. Now follow the chain and try to
 640     // vectorize it.
 641     SmallVector<Value *, 16> Operands;
 642     int I = Head;
 643     while (I != -1 && (Tails.count(I) || Heads.count(I))) {
 644       if (InstructionsProcessed.count(Instrs[I]))
 645         break;
 646
 647       Operands.push_back(Instrs[I]);
 648       I = ConsecutiveChain[I];
 649     }
 650
 651     bool Vectorized = false;
 652     if (isa<LoadInst>(*Operands.begin()))
 653       Vectorized = vectorizeLoadChain(Operands, &InstructionsProcessed);
 654     else
 655       Vectorized = vectorizeStoreChain(Operands, &InstructionsProcessed);
 656
 657     Changed |= Vectorized;
 658   }
 659
 660   return Changed;
 661 }
 662
 663 bool Vectorizer::vectorizeStoreChain(
 664     ArrayRef<Value *> Chain, SmallPtrSet<Value *, 16> *InstructionsProcessed) {
 665   StoreInst *S0 = cast<StoreInst>(Chain[0]);
 666
 667   // If the vector has an int element, default to int for the whole load.
 668   Type *StoreTy;
 669   for (const auto &V : Chain) {
 670     StoreTy = cast<StoreInst>(V)->getValueOperand()->getType();
 671     if (StoreTy->isIntOrIntVectorTy())
 672       break;
 673
 674     if (StoreTy->isPtrOrPtrVectorTy()) {
 675       StoreTy = Type::getIntNTy(F.getParent()->getContext(),
 676                                 DL.getTypeSizeInBits(StoreTy));
 677       break;
 678     }
 679   }
 680
 681   unsigned Sz = DL.getTypeSizeInBits(StoreTy);
 682   unsigned AS = S0->getPointerAddressSpace();
 683   unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
 684   unsigned VF = VecRegSize / Sz;
 685   unsigned ChainSize = Chain.size();
 686
 687   if (!isPowerOf2_32(Sz) || VF < 2 || ChainSize < 2) {
 688     InstructionsProcessed->insert(Chain.begin(), Chain.end());
 689     return false;
 690   }
 691
 692   BasicBlock::iterator First, Last;
 693   std::tie(First, Last) = getBoundaryInstrs(Chain);
 694   unsigned StopChain = getVectorizablePrefixEndIdx(Chain, First, Last);
 695   if (StopChain == 0) {
 696     // There exists a side effect instruction, no vectorization possible.
 697     InstructionsProcessed->insert(Chain.begin(), Chain.end());
 698     return false;
 699   }
 700   if (StopChain == 1) {
 701     // Failed after the first instruction. Discard it and try the smaller chain.
 702     InstructionsProcessed->insert(Chain.front());
 703     return false;
 704   }
 705
 706   // Update Chain to the valid vectorizable subchain.
 707   Chain = Chain.slice(0, StopChain);
 708   ChainSize = Chain.size();
 709
 710   // Store size should be 1B, 2B or multiple of 4B.
 711   // TODO: Target hook for size constraint?
 712   unsigned SzInBytes = (Sz / 8) * ChainSize;
 713   if (SzInBytes > 2 && SzInBytes % 4 != 0) {
 714     DEBUG(dbgs() << "LSV: Size should be 1B, 2B "
 715                     "or multiple of 4B. Splitting.\n");
 716     if (SzInBytes == 3)
 717       return vectorizeStoreChain(Chain.slice(0, ChainSize - 1),
 718                                  InstructionsProcessed);
 719
 720     auto Chains = splitOddVectorElts(Chain, Sz);
 721     return vectorizeStoreChain(Chains.first, InstructionsProcessed) |
 722            vectorizeStoreChain(Chains.second, InstructionsProcessed);
 723   }
 724
 725   VectorType *VecTy;
 726   VectorType *VecStoreTy = dyn_cast<VectorType>(StoreTy);
 727   if (VecStoreTy)
 728     VecTy = VectorType::get(StoreTy->getScalarType(),
 729                             Chain.size() * VecStoreTy->getNumElements());
 730   else
 731     VecTy = VectorType::get(StoreTy, Chain.size());
 732
 733   // If it's more than the max vector size, break it into two pieces.
 734   // TODO: Target hook to control types to split to.
 735   if (ChainSize > VF) {
 736     DEBUG(dbgs() << "LSV: Vector factor is too big."
 737                     " Creating two separate arrays.\n");
 738     return vectorizeStoreChain(Chain.slice(0, VF), InstructionsProcessed) |
 739            vectorizeStoreChain(Chain.slice(VF), InstructionsProcessed);
 740   }
 741
 742   DEBUG({
 743     dbgs() << "LSV: Stores to vectorize:\n";
 744     for (Value *V : Chain)
 745       V->dump();
 746   });
 747
 748   // We won't try again to vectorize the elements of the chain, regardless of
 749   // whether we succeed below.
 750   InstructionsProcessed->insert(Chain.begin(), Chain.end());
 751
 752   // Check alignment restrictions.
 753   unsigned Alignment = getAlignment(S0);
 754
 755   // If the store is going to be misaligned, don't vectorize it.
 756   if (accessIsMisaligned(SzInBytes, AS, Alignment)) {
 757     if (S0->getPointerAddressSpace() != 0)
 758       return false;
 759
 760     // If we're storing to an object on the stack, we control its alignment,
 761     // so we can cheat and change it!
 762     Value *V = GetUnderlyingObject(S0->getPointerOperand(), DL);
 763     if (AllocaInst *AI = dyn_cast_or_null<AllocaInst>(V)) {
 764       AI->setAlignment(TargetBaseAlign);
 765       Alignment = TargetBaseAlign;
 766     } else {
 767       return false;
 768     }
 769   }
 770
 771   // Set insert point.
 772   Builder.SetInsertPoint(&*Last);
 773
 774   Value *Vec = UndefValue::get(VecTy);
 775
 776   if (VecStoreTy) {
 777     unsigned VecWidth = VecStoreTy->getNumElements();
 778     for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
 779       StoreInst *Store = cast<StoreInst>(Chain[I]);
 780       for (unsigned J = 0, NE = VecStoreTy->getNumElements(); J != NE; ++J) {
 781         unsigned NewIdx = J + I * VecWidth;
 782         Value *Extract = Builder.CreateExtractElement(Store->getValueOperand(),
 783                                                       Builder.getInt32(J));
 784         if (Extract->getType() != StoreTy->getScalarType())
 785           Extract = Builder.CreateBitCast(Extract, StoreTy->getScalarType());
 786
 787         Value *Insert =
 788             Builder.CreateInsertElement(Vec, Extract, Builder.getInt32(NewIdx));
 789         Vec = Insert;
 790       }
 791     }
 792   } else {
 793     for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
 794       StoreInst *Store = cast<StoreInst>(Chain[I]);
 795       Value *Extract = Store->getValueOperand();
 796       if (Extract->getType() != StoreTy->getScalarType())
 797         Extract =
 798             Builder.CreateBitOrPointerCast(Extract, StoreTy->getScalarType());
 799
 800       Value *Insert =
 801           Builder.CreateInsertElement(Vec, Extract, Builder.getInt32(I));
 802       Vec = Insert;
 803     }
 804   }
 805
 806   Value *Bitcast =
 807       Builder.CreateBitCast(S0->getPointerOperand(), VecTy->getPointerTo(AS));
 808   StoreInst *SI = cast<StoreInst>(Builder.CreateStore(Vec, Bitcast));
 809   propagateMetadata(SI, Chain);
 810   SI->setAlignment(Alignment);
 811
 812   eraseInstructions(Chain);
 813   ++NumVectorInstructions;
 814   NumScalarsVectorized += Chain.size();
 815   return true;
 816 }
 817
 818 bool Vectorizer::vectorizeLoadChain(
 819     ArrayRef<Value *> Chain, SmallPtrSet<Value *, 16> *InstructionsProcessed) {
 820   LoadInst *L0 = cast<LoadInst>(Chain[0]);
 821
 822   // If the vector has an int element, default to int for the whole load.
 823   Type *LoadTy;
 824   for (const auto &V : Chain) {
 825     LoadTy = cast<LoadInst>(V)->getType();
 826     if (LoadTy->isIntOrIntVectorTy())
 827       break;
 828
 829     if (LoadTy->isPtrOrPtrVectorTy()) {
 830       LoadTy = Type::getIntNTy(F.getParent()->getContext(),
 831                                DL.getTypeSizeInBits(LoadTy));
 832       break;
 833     }
 834   }
 835
 836   unsigned Sz = DL.getTypeSizeInBits(LoadTy);
 837   unsigned AS = L0->getPointerAddressSpace();
 838   unsigned VecRegSize = TTI.getLoadStoreVecRegBitWidth(AS);
 839   unsigned VF = VecRegSize / Sz;
 840   unsigned ChainSize = Chain.size();
 841
 842   if (!isPowerOf2_32(Sz) || VF < 2 || ChainSize < 2) {
 843     InstructionsProcessed->insert(Chain.begin(), Chain.end());
 844     return false;
 845   }
 846
 847   BasicBlock::iterator First, Last;
 848   std::tie(First, Last) = getBoundaryInstrs(Chain);
 849   unsigned StopChain = getVectorizablePrefixEndIdx(Chain, First, Last);
 850   if (StopChain == 0) {
 851     // There exists a side effect instruction, no vectorization possible.
 852     InstructionsProcessed->insert(Chain.begin(), Chain.end());
 853     return false;
 854   }
 855   if (StopChain == 1) {
 856     // Failed after the first instruction. Discard it and try the smaller chain.
 857     InstructionsProcessed->insert(Chain.front());
 858     return false;
 859   }
 860
 861   // Update Chain to the valid vectorizable subchain.
 862   Chain = Chain.slice(0, StopChain);
 863   ChainSize = Chain.size();
 864
 865   // Load size should be 1B, 2B or multiple of 4B.
 866   // TODO: Should size constraint be a target hook?
 867   unsigned SzInBytes = (Sz / 8) * ChainSize;
 868   if (SzInBytes > 2 && SzInBytes % 4 != 0) {
 869     DEBUG(dbgs() << "LSV: Size should be 1B, 2B "
 870                     "or multiple of 4B. Splitting.\n");
 871     if (SzInBytes == 3)
 872       return vectorizeLoadChain(Chain.slice(0, ChainSize - 1),
 873                                 InstructionsProcessed);
 874     auto Chains = splitOddVectorElts(Chain, Sz);
 875     return vectorizeLoadChain(Chains.first, InstructionsProcessed) |
 876            vectorizeLoadChain(Chains.second, InstructionsProcessed);
 877   }
 878
 879   VectorType *VecTy;
 880   VectorType *VecLoadTy = dyn_cast<VectorType>(LoadTy);
 881   if (VecLoadTy)
 882     VecTy = VectorType::get(LoadTy->getScalarType(),
 883                             Chain.size() * VecLoadTy->getNumElements());
 884   else
 885     VecTy = VectorType::get(LoadTy, Chain.size());
 886
 887   // If it's more than the max vector size, break it into two pieces.
 888   // TODO: Target hook to control types to split to.
 889   if (ChainSize > VF) {
 890     DEBUG(dbgs() << "LSV: Vector factor is too big. "
 891                     "Creating two separate arrays.\n");
 892     return vectorizeLoadChain(Chain.slice(0, VF), InstructionsProcessed) |
 893            vectorizeLoadChain(Chain.slice(VF), InstructionsProcessed);
 894   }
 895
 896   // We won't try again to vectorize the elements of the chain, regardless of
 897   // whether we succeed below.
 898   InstructionsProcessed->insert(Chain.begin(), Chain.end());
 899
 900   // Check alignment restrictions.
 901   unsigned Alignment = getAlignment(L0);
 902
 903   // If the load is going to be misaligned, don't vectorize it.
 904   if (accessIsMisaligned(SzInBytes, AS, Alignment)) {
 905     if (L0->getPointerAddressSpace() != 0)
 906       return false;
 907
 908     // If we're loading from an object on the stack, we control its alignment,
 909     // so we can cheat and change it!
 910     Value *V = GetUnderlyingObject(L0->getPointerOperand(), DL);
 911     if (AllocaInst *AI = dyn_cast_or_null<AllocaInst>(V)) {
 912       AI->setAlignment(TargetBaseAlign);
 913       Alignment = TargetBaseAlign;
 914     } else {
 915       return false;
 916     }
 917   }
 918
 919   DEBUG({
 920     dbgs() << "LSV: Loads to vectorize:\n";
 921     for (Value *V : Chain)
 922       V->dump();
 923   });
 924
 925   // Set insert point.
 926   Builder.SetInsertPoint(&*First);
 927
 928   Value *Bitcast =
 929       Builder.CreateBitCast(L0->getPointerOperand(), VecTy->getPointerTo(AS));
 930
 931   LoadInst *LI = cast<LoadInst>(Builder.CreateLoad(Bitcast));
 932   propagateMetadata(LI, Chain);
 933   LI->setAlignment(Alignment);
 934
 935   if (VecLoadTy) {
 936     SmallVector<Instruction *, 16> InstrsToErase;
 937     SmallVector<Instruction *, 16> InstrsToReorder;
 938     InstrsToReorder.push_back(cast<Instruction>(Bitcast));
 939
 940     unsigned VecWidth = VecLoadTy->getNumElements();
 941     for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
 942       for (auto Use : Chain[I]->users()) {
 943         Instruction *UI = cast<Instruction>(Use);
 944         unsigned Idx = cast<ConstantInt>(UI->getOperand(1))->getZExtValue();
 945         unsigned NewIdx = Idx + I * VecWidth;
 946         Value *V = Builder.CreateExtractElement(LI, Builder.getInt32(NewIdx));
 947         Instruction *Extracted = cast<Instruction>(V);
 948         if (Extracted->getType() != UI->getType())
 949           Extracted = cast<Instruction>(
 950               Builder.CreateBitCast(Extracted, UI->getType()));
 951
 952         // Replace the old instruction.
 953         UI->replaceAllUsesWith(Extracted);
 954         InstrsToErase.push_back(UI);
 955       }
 956     }
 957
 958     for (Instruction *ModUser : InstrsToReorder)
 959       reorder(ModUser);
 960
 961     for (auto I : InstrsToErase)
 962       I->eraseFromParent();
 963   } else {
 964     SmallVector<Instruction *, 16> InstrsToReorder;
 965     InstrsToReorder.push_back(cast<Instruction>(Bitcast));
 966
 967     for (unsigned I = 0, E = Chain.size(); I != E; ++I) {
 968       Value *V = Builder.CreateExtractElement(LI, Builder.getInt32(I));
 969       Instruction *Extracted = cast<Instruction>(V);
 970       Instruction *UI = cast<Instruction>(Chain[I]);
 971       if (Extracted->getType() != UI->getType()) {
 972         Extracted = cast<Instruction>(
 973             Builder.CreateBitOrPointerCast(Extracted, UI->getType()));
 974       }
 975
 976       // Replace the old instruction.
 977       UI->replaceAllUsesWith(Extracted);
 978     }
 979
 980     for (Instruction *ModUser : InstrsToReorder)
 981       reorder(ModUser);
 982   }
 983
 984   eraseInstructions(Chain);
 985
 986   ++NumVectorInstructions;
 987   NumScalarsVectorized += Chain.size();
 988   return true;
 989 }
 990
 991 bool Vectorizer::accessIsMisaligned(unsigned SzInBytes, unsigned AddressSpace,
 992                                     unsigned Alignment) {
 993   bool Fast = false;
 994   bool Allows = TTI.allowsMisalignedMemoryAccesses(SzInBytes * 8, AddressSpace,
 995                                                    Alignment, &Fast);
 996   // TODO: Remove TargetBaseAlign
 997   return !(Allows && Fast) && (Alignment % SzInBytes) != 0 &&
 998          (Alignment % TargetBaseAlign) != 0;
 999 }