contrib/llvm-project/llvm/lib/Analysis/VectorUtils.cpp

   1 //===----------- VectorUtils.cpp - Vectorizer utility functions -----------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file defines vectorizer utilities.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/Analysis/VectorUtils.h"
  14 #include "llvm/ADT/EquivalenceClasses.h"
  15 #include "llvm/Analysis/DemandedBits.h"
  16 #include "llvm/Analysis/LoopInfo.h"
  17 #include "llvm/Analysis/LoopIterator.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/IR/Constants.h"
  23 #include "llvm/IR/GetElementPtrTypeIterator.h"
  24 #include "llvm/IR/IRBuilder.h"
  25 #include "llvm/IR/PatternMatch.h"
  26 #include "llvm/IR/Value.h"
  27
  28 #define DEBUG_TYPE "vectorutils"
  29
  30 using namespace llvm;
  31 using namespace llvm::PatternMatch;
  32
  33 /// Maximum factor for an interleaved memory access.
  34 static cl::opt<unsigned> MaxInterleaveGroupFactor(
  35     "max-interleave-group-factor", cl::Hidden,
  36     cl::desc("Maximum factor for an interleaved access group (default = 8)"),
  37     cl::init(8));
  38
  39 /// Return true if all of the intrinsic's arguments and return type are scalars
  40 /// for the scalar form of the intrinsic, and vectors for the vector form of the
  41 /// intrinsic (except operands that are marked as always being scalar by
  42 /// hasVectorInstrinsicScalarOpd).
  43 bool llvm::isTriviallyVectorizable(Intrinsic::ID ID) {
  44   switch (ID) {
  45   case Intrinsic::bswap: // Begin integer bit-manipulation.
  46   case Intrinsic::bitreverse:
  47   case Intrinsic::ctpop:
  48   case Intrinsic::ctlz:
  49   case Intrinsic::cttz:
  50   case Intrinsic::fshl:
  51   case Intrinsic::fshr:
  52   case Intrinsic::sadd_sat:
  53   case Intrinsic::ssub_sat:
  54   case Intrinsic::uadd_sat:
  55   case Intrinsic::usub_sat:
  56   case Intrinsic::smul_fix:
  57   case Intrinsic::smul_fix_sat:
  58   case Intrinsic::umul_fix:
  59   case Intrinsic::sqrt: // Begin floating-point.
  60   case Intrinsic::sin:
  61   case Intrinsic::cos:
  62   case Intrinsic::exp:
  63   case Intrinsic::exp2:
  64   case Intrinsic::log:
  65   case Intrinsic::log10:
  66   case Intrinsic::log2:
  67   case Intrinsic::fabs:
  68   case Intrinsic::minnum:
  69   case Intrinsic::maxnum:
  70   case Intrinsic::minimum:
  71   case Intrinsic::maximum:
  72   case Intrinsic::copysign:
  73   case Intrinsic::floor:
  74   case Intrinsic::ceil:
  75   case Intrinsic::trunc:
  76   case Intrinsic::rint:
  77   case Intrinsic::nearbyint:
  78   case Intrinsic::round:
  79   case Intrinsic::pow:
  80   case Intrinsic::fma:
  81   case Intrinsic::fmuladd:
  82   case Intrinsic::powi:
  83   case Intrinsic::canonicalize:
  84     return true;
  85   default:
  86     return false;
  87   }
  88 }
  89
  90 /// Identifies if the vector form of the intrinsic has a scalar operand.
  91 bool llvm::hasVectorInstrinsicScalarOpd(Intrinsic::ID ID,
  92                                         unsigned ScalarOpdIdx) {
  93   switch (ID) {
  94   case Intrinsic::ctlz:
  95   case Intrinsic::cttz:
  96   case Intrinsic::powi:
  97     return (ScalarOpdIdx == 1);
  98   case Intrinsic::smul_fix:
  99   case Intrinsic::smul_fix_sat:
 100   case Intrinsic::umul_fix:
 101     return (ScalarOpdIdx == 2);
 102   default:
 103     return false;
 104   }
 105 }
 106
 107 /// Returns intrinsic ID for call.
 108 /// For the input call instruction it finds mapping intrinsic and returns
 109 /// its ID, in case it does not found it return not_intrinsic.
 110 Intrinsic::ID llvm::getVectorIntrinsicIDForCall(const CallInst *CI,
 111                                                 const TargetLibraryInfo *TLI) {
 112   Intrinsic::ID ID = getIntrinsicForCallSite(CI, TLI);
 113   if (ID == Intrinsic::not_intrinsic)
 114     return Intrinsic::not_intrinsic;
 115
 116   if (isTriviallyVectorizable(ID) || ID == Intrinsic::lifetime_start ||
 117       ID == Intrinsic::lifetime_end || ID == Intrinsic::assume ||
 118       ID == Intrinsic::sideeffect)
 119     return ID;
 120   return Intrinsic::not_intrinsic;
 121 }
 122
 123 /// Find the operand of the GEP that should be checked for consecutive
 124 /// stores. This ignores trailing indices that have no effect on the final
 125 /// pointer.
 126 unsigned llvm::getGEPInductionOperand(const GetElementPtrInst *Gep) {
 127   const DataLayout &DL = Gep->getModule()->getDataLayout();
 128   unsigned LastOperand = Gep->getNumOperands() - 1;
 129   unsigned GEPAllocSize = DL.getTypeAllocSize(Gep->getResultElementType());
 130
 131   // Walk backwards and try to peel off zeros.
 132   while (LastOperand > 1 && match(Gep->getOperand(LastOperand), m_Zero())) {
 133     // Find the type we're currently indexing into.
 134     gep_type_iterator GEPTI = gep_type_begin(Gep);
 135     std::advance(GEPTI, LastOperand - 2);
 136
 137     // If it's a type with the same allocation size as the result of the GEP we
 138     // can peel off the zero index.
 139     if (DL.getTypeAllocSize(GEPTI.getIndexedType()) != GEPAllocSize)
 140       break;
 141     --LastOperand;
 142   }
 143
 144   return LastOperand;
 145 }
 146
 147 /// If the argument is a GEP, then returns the operand identified by
 148 /// getGEPInductionOperand. However, if there is some other non-loop-invariant
 149 /// operand, it returns that instead.
 150 Value *llvm::stripGetElementPtr(Value *Ptr, ScalarEvolution *SE, Loop *Lp) {
 151   GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Ptr);
 152   if (!GEP)
 153     return Ptr;
 154
 155   unsigned InductionOperand = getGEPInductionOperand(GEP);
 156
 157   // Check that all of the gep indices are uniform except for our induction
 158   // operand.
 159   for (unsigned i = 0, e = GEP->getNumOperands(); i != e; ++i)
 160     if (i != InductionOperand &&
 161         !SE->isLoopInvariant(SE->getSCEV(GEP->getOperand(i)), Lp))
 162       return Ptr;
 163   return GEP->getOperand(InductionOperand);
 164 }
 165
 166 /// If a value has only one user that is a CastInst, return it.
 167 Value *llvm::getUniqueCastUse(Value *Ptr, Loop *Lp, Type *Ty) {
 168   Value *UniqueCast = nullptr;
 169   for (User *U : Ptr->users()) {
 170     CastInst *CI = dyn_cast<CastInst>(U);
 171     if (CI && CI->getType() == Ty) {
 172       if (!UniqueCast)
 173         UniqueCast = CI;
 174       else
 175         return nullptr;
 176     }
 177   }
 178   return UniqueCast;
 179 }
 180
 181 /// Get the stride of a pointer access in a loop. Looks for symbolic
 182 /// strides "a[i*stride]". Returns the symbolic stride, or null otherwise.
 183 Value *llvm::getStrideFromPointer(Value *Ptr, ScalarEvolution *SE, Loop *Lp) {
 184   auto *PtrTy = dyn_cast<PointerType>(Ptr->getType());
 185   if (!PtrTy || PtrTy->isAggregateType())
 186     return nullptr;
 187
 188   // Try to remove a gep instruction to make the pointer (actually index at this
 189   // point) easier analyzable. If OrigPtr is equal to Ptr we are analyzing the
 190   // pointer, otherwise, we are analyzing the index.
 191   Value *OrigPtr = Ptr;
 192
 193   // The size of the pointer access.
 194   int64_t PtrAccessSize = 1;
 195
 196   Ptr = stripGetElementPtr(Ptr, SE, Lp);
 197   const SCEV *V = SE->getSCEV(Ptr);
 198
 199   if (Ptr != OrigPtr)
 200     // Strip off casts.
 201     while (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V))
 202       V = C->getOperand();
 203
 204   const SCEVAddRecExpr *S = dyn_cast<SCEVAddRecExpr>(V);
 205   if (!S)
 206     return nullptr;
 207
 208   V = S->getStepRecurrence(*SE);
 209   if (!V)
 210     return nullptr;
 211
 212   // Strip off the size of access multiplication if we are still analyzing the
 213   // pointer.
 214   if (OrigPtr == Ptr) {
 215     if (const SCEVMulExpr *M = dyn_cast<SCEVMulExpr>(V)) {
 216       if (M->getOperand(0)->getSCEVType() != scConstant)
 217         return nullptr;
 218
 219       const APInt &APStepVal = cast<SCEVConstant>(M->getOperand(0))->getAPInt();
 220
 221       // Huge step value - give up.
 222       if (APStepVal.getBitWidth() > 64)
 223         return nullptr;
 224
 225       int64_t StepVal = APStepVal.getSExtValue();
 226       if (PtrAccessSize != StepVal)
 227         return nullptr;
 228       V = M->getOperand(1);
 229     }
 230   }
 231
 232   // Strip off casts.
 233   Type *StripedOffRecurrenceCast = nullptr;
 234   if (const SCEVCastExpr *C = dyn_cast<SCEVCastExpr>(V)) {
 235     StripedOffRecurrenceCast = C->getType();
 236     V = C->getOperand();
 237   }
 238
 239   // Look for the loop invariant symbolic value.
 240   const SCEVUnknown *U = dyn_cast<SCEVUnknown>(V);
 241   if (!U)
 242     return nullptr;
 243
 244   Value *Stride = U->getValue();
 245   if (!Lp->isLoopInvariant(Stride))
 246     return nullptr;
 247
 248   // If we have stripped off the recurrence cast we have to make sure that we
 249   // return the value that is used in this loop so that we can replace it later.
 250   if (StripedOffRecurrenceCast)
 251     Stride = getUniqueCastUse(Stride, Lp, StripedOffRecurrenceCast);
 252
 253   return Stride;
 254 }
 255
 256 /// Given a vector and an element number, see if the scalar value is
 257 /// already around as a register, for example if it were inserted then extracted
 258 /// from the vector.
 259 Value *llvm::findScalarElement(Value *V, unsigned EltNo) {
 260   assert(V->getType()->isVectorTy() && "Not looking at a vector?");
 261   VectorType *VTy = cast<VectorType>(V->getType());
 262   unsigned Width = VTy->getNumElements();
 263   if (EltNo >= Width)  // Out of range access.
 264     return UndefValue::get(VTy->getElementType());
 265
 266   if (Constant *C = dyn_cast<Constant>(V))
 267     return C->getAggregateElement(EltNo);
 268
 269   if (InsertElementInst *III = dyn_cast<InsertElementInst>(V)) {
 270     // If this is an insert to a variable element, we don't know what it is.
 271     if (!isa<ConstantInt>(III->getOperand(2)))
 272       return nullptr;
 273     unsigned IIElt = cast<ConstantInt>(III->getOperand(2))->getZExtValue();
 274
 275     // If this is an insert to the element we are looking for, return the
 276     // inserted value.
 277     if (EltNo == IIElt)
 278       return III->getOperand(1);
 279
 280     // Otherwise, the insertelement doesn't modify the value, recurse on its
 281     // vector input.
 282     return findScalarElement(III->getOperand(0), EltNo);
 283   }
 284
 285   if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(V)) {
 286     unsigned LHSWidth = SVI->getOperand(0)->getType()->getVectorNumElements();
 287     int InEl = SVI->getMaskValue(EltNo);
 288     if (InEl < 0)
 289       return UndefValue::get(VTy->getElementType());
 290     if (InEl < (int)LHSWidth)
 291       return findScalarElement(SVI->getOperand(0), InEl);
 292     return findScalarElement(SVI->getOperand(1), InEl - LHSWidth);
 293   }
 294
 295   // Extract a value from a vector add operation with a constant zero.
 296   // TODO: Use getBinOpIdentity() to generalize this.
 297   Value *Val; Constant *C;
 298   if (match(V, m_Add(m_Value(Val), m_Constant(C))))
 299     if (Constant *Elt = C->getAggregateElement(EltNo))
 300       if (Elt->isNullValue())
 301         return findScalarElement(Val, EltNo);
 302
 303   // Otherwise, we don't know.
 304   return nullptr;
 305 }
 306
 307 /// Get splat value if the input is a splat vector or return nullptr.
 308 /// This function is not fully general. It checks only 2 cases:
 309 /// the input value is (1) a splat constant vector or (2) a sequence
 310 /// of instructions that broadcasts a scalar at element 0.
 311 const llvm::Value *llvm::getSplatValue(const Value *V) {
 312   if (isa<VectorType>(V->getType()))
 313     if (auto *C = dyn_cast<Constant>(V))
 314       return C->getSplatValue();
 315
 316   // shuf (inselt ?, Splat, 0), ?, <0, undef, 0, ...>
 317   Value *Splat;
 318   if (match(V, m_ShuffleVector(m_InsertElement(m_Value(), m_Value(Splat),
 319                                                m_ZeroInt()),
 320                                m_Value(), m_ZeroInt())))
 321     return Splat;
 322
 323   return nullptr;
 324 }
 325
 326 // This setting is based on its counterpart in value tracking, but it could be
 327 // adjusted if needed.
 328 const unsigned MaxDepth = 6;
 329
 330 bool llvm::isSplatValue(const Value *V, unsigned Depth) {
 331   assert(Depth <= MaxDepth && "Limit Search Depth");
 332
 333   if (isa<VectorType>(V->getType())) {
 334     if (isa<UndefValue>(V))
 335       return true;
 336     // FIXME: Constant splat analysis does not allow undef elements.
 337     if (auto *C = dyn_cast<Constant>(V))
 338       return C->getSplatValue() != nullptr;
 339   }
 340
 341   // FIXME: Constant splat analysis does not allow undef elements.
 342   Constant *Mask;
 343   if (match(V, m_ShuffleVector(m_Value(), m_Value(), m_Constant(Mask))))
 344     return Mask->getSplatValue() != nullptr;
 345
 346   // The remaining tests are all recursive, so bail out if we hit the limit.
 347   if (Depth++ == MaxDepth)
 348     return false;
 349
 350   // If both operands of a binop are splats, the result is a splat.
 351   Value *X, *Y, *Z;
 352   if (match(V, m_BinOp(m_Value(X), m_Value(Y))))
 353     return isSplatValue(X, Depth) && isSplatValue(Y, Depth);
 354
 355   // If all operands of a select are splats, the result is a splat.
 356   if (match(V, m_Select(m_Value(X), m_Value(Y), m_Value(Z))))
 357     return isSplatValue(X, Depth) && isSplatValue(Y, Depth) &&
 358            isSplatValue(Z, Depth);
 359
 360   // TODO: Add support for unary ops (fneg), casts, intrinsics (overflow ops).
 361
 362   return false;
 363 }
 364
 365 MapVector<Instruction *, uint64_t>
 366 llvm::computeMinimumValueSizes(ArrayRef<BasicBlock *> Blocks, DemandedBits &DB,
 367                                const TargetTransformInfo *TTI) {
 368
 369   // DemandedBits will give us every value's live-out bits. But we want
 370   // to ensure no extra casts would need to be inserted, so every DAG
 371   // of connected values must have the same minimum bitwidth.
 372   EquivalenceClasses<Value *> ECs;
 373   SmallVector<Value *, 16> Worklist;
 374   SmallPtrSet<Value *, 4> Roots;
 375   SmallPtrSet<Value *, 16> Visited;
 376   DenseMap<Value *, uint64_t> DBits;
 377   SmallPtrSet<Instruction *, 4> InstructionSet;
 378   MapVector<Instruction *, uint64_t> MinBWs;
 379
 380   // Determine the roots. We work bottom-up, from truncs or icmps.
 381   bool SeenExtFromIllegalType = false;
 382   for (auto *BB : Blocks)
 383     for (auto &I : *BB) {
 384       InstructionSet.insert(&I);
 385
 386       if (TTI && (isa<ZExtInst>(&I) || isa<SExtInst>(&I)) &&
 387           !TTI->isTypeLegal(I.getOperand(0)->getType()))
 388         SeenExtFromIllegalType = true;
 389
 390       // Only deal with non-vector integers up to 64-bits wide.
 391       if ((isa<TruncInst>(&I) || isa<ICmpInst>(&I)) &&
 392           !I.getType()->isVectorTy() &&
 393           I.getOperand(0)->getType()->getScalarSizeInBits() <= 64) {
 394         // Don't make work for ourselves. If we know the loaded type is legal,
 395         // don't add it to the worklist.
 396         if (TTI && isa<TruncInst>(&I) && TTI->isTypeLegal(I.getType()))
 397           continue;
 398
 399         Worklist.push_back(&I);
 400         Roots.insert(&I);
 401       }
 402     }
 403   // Early exit.
 404   if (Worklist.empty() || (TTI && !SeenExtFromIllegalType))
 405     return MinBWs;
 406
 407   // Now proceed breadth-first, unioning values together.
 408   while (!Worklist.empty()) {
 409     Value *Val = Worklist.pop_back_val();
 410     Value *Leader = ECs.getOrInsertLeaderValue(Val);
 411
 412     if (Visited.count(Val))
 413       continue;
 414     Visited.insert(Val);
 415
 416     // Non-instructions terminate a chain successfully.
 417     if (!isa<Instruction>(Val))
 418       continue;
 419     Instruction *I = cast<Instruction>(Val);
 420
 421     // If we encounter a type that is larger than 64 bits, we can't represent
 422     // it so bail out.
 423     if (DB.getDemandedBits(I).getBitWidth() > 64)
 424       return MapVector<Instruction *, uint64_t>();
 425
 426     uint64_t V = DB.getDemandedBits(I).getZExtValue();
 427     DBits[Leader] |= V;
 428     DBits[I] = V;
 429
 430     // Casts, loads and instructions outside of our range terminate a chain
 431     // successfully.
 432     if (isa<SExtInst>(I) || isa<ZExtInst>(I) || isa<LoadInst>(I) ||
 433         !InstructionSet.count(I))
 434       continue;
 435
 436     // Unsafe casts terminate a chain unsuccessfully. We can't do anything
 437     // useful with bitcasts, ptrtoints or inttoptrs and it'd be unsafe to
 438     // transform anything that relies on them.
 439     if (isa<BitCastInst>(I) || isa<PtrToIntInst>(I) || isa<IntToPtrInst>(I) ||
 440         !I->getType()->isIntegerTy()) {
 441       DBits[Leader] |= ~0ULL;
 442       continue;
 443     }
 444
 445     // We don't modify the types of PHIs. Reductions will already have been
 446     // truncated if possible, and inductions' sizes will have been chosen by
 447     // indvars.
 448     if (isa<PHINode>(I))
 449       continue;
 450
 451     if (DBits[Leader] == ~0ULL)
 452       // All bits demanded, no point continuing.
 453       continue;
 454
 455     for (Value *O : cast<User>(I)->operands()) {
 456       ECs.unionSets(Leader, O);
 457       Worklist.push_back(O);
 458     }
 459   }
 460
 461   // Now we've discovered all values, walk them to see if there are
 462   // any users we didn't see. If there are, we can't optimize that
 463   // chain.
 464   for (auto &I : DBits)
 465     for (auto *U : I.first->users())
 466       if (U->getType()->isIntegerTy() && DBits.count(U) == 0)
 467         DBits[ECs.getOrInsertLeaderValue(I.first)] |= ~0ULL;
 468
 469   for (auto I = ECs.begin(), E = ECs.end(); I != E; ++I) {
 470     uint64_t LeaderDemandedBits = 0;
 471     for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME; ++MI)
 472       LeaderDemandedBits |= DBits[*MI];
 473
 474     uint64_t MinBW = (sizeof(LeaderDemandedBits) * 8) -
 475                      llvm::countLeadingZeros(LeaderDemandedBits);
 476     // Round up to a power of 2
 477     if (!isPowerOf2_64((uint64_t)MinBW))
 478       MinBW = NextPowerOf2(MinBW);
 479
 480     // We don't modify the types of PHIs. Reductions will already have been
 481     // truncated if possible, and inductions' sizes will have been chosen by
 482     // indvars.
 483     // If we are required to shrink a PHI, abandon this entire equivalence class.
 484     bool Abort = false;
 485     for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME; ++MI)
 486       if (isa<PHINode>(*MI) && MinBW < (*MI)->getType()->getScalarSizeInBits()) {
 487         Abort = true;
 488         break;
 489       }
 490     if (Abort)
 491       continue;
 492
 493     for (auto MI = ECs.member_begin(I), ME = ECs.member_end(); MI != ME; ++MI) {
 494       if (!isa<Instruction>(*MI))
 495         continue;
 496       Type *Ty = (*MI)->getType();
 497       if (Roots.count(*MI))
 498         Ty = cast<Instruction>(*MI)->getOperand(0)->getType();
 499       if (MinBW < Ty->getScalarSizeInBits())
 500         MinBWs[cast<Instruction>(*MI)] = MinBW;
 501     }
 502   }
 503
 504   return MinBWs;
 505 }
 506
 507 /// Add all access groups in @p AccGroups to @p List.
 508 template <typename ListT>
 509 static void addToAccessGroupList(ListT &List, MDNode *AccGroups) {
 510   // Interpret an access group as a list containing itself.
 511   if (AccGroups->getNumOperands() == 0) {
 512     assert(isValidAsAccessGroup(AccGroups) && "Node must be an access group");
 513     List.insert(AccGroups);
 514     return;
 515   }
 516
 517   for (auto &AccGroupListOp : AccGroups->operands()) {
 518     auto *Item = cast<MDNode>(AccGroupListOp.get());
 519     assert(isValidAsAccessGroup(Item) && "List item must be an access group");
 520     List.insert(Item);
 521   }
 522 }
 523
 524 MDNode *llvm::uniteAccessGroups(MDNode *AccGroups1, MDNode *AccGroups2) {
 525   if (!AccGroups1)
 526     return AccGroups2;
 527   if (!AccGroups2)
 528     return AccGroups1;
 529   if (AccGroups1 == AccGroups2)
 530     return AccGroups1;
 531
 532   SmallSetVector<Metadata *, 4> Union;
 533   addToAccessGroupList(Union, AccGroups1);
 534   addToAccessGroupList(Union, AccGroups2);
 535
 536   if (Union.size() == 0)
 537     return nullptr;
 538   if (Union.size() == 1)
 539     return cast<MDNode>(Union.front());
 540
 541   LLVMContext &Ctx = AccGroups1->getContext();
 542   return MDNode::get(Ctx, Union.getArrayRef());
 543 }
 544
 545 MDNode *llvm::intersectAccessGroups(const Instruction *Inst1,
 546                                     const Instruction *Inst2) {
 547   bool MayAccessMem1 = Inst1->mayReadOrWriteMemory();
 548   bool MayAccessMem2 = Inst2->mayReadOrWriteMemory();
 549
 550   if (!MayAccessMem1 && !MayAccessMem2)
 551     return nullptr;
 552   if (!MayAccessMem1)
 553     return Inst2->getMetadata(LLVMContext::MD_access_group);
 554   if (!MayAccessMem2)
 555     return Inst1->getMetadata(LLVMContext::MD_access_group);
 556
 557   MDNode *MD1 = Inst1->getMetadata(LLVMContext::MD_access_group);
 558   MDNode *MD2 = Inst2->getMetadata(LLVMContext::MD_access_group);
 559   if (!MD1 || !MD2)
 560     return nullptr;
 561   if (MD1 == MD2)
 562     return MD1;
 563
 564   // Use set for scalable 'contains' check.
 565   SmallPtrSet<Metadata *, 4> AccGroupSet2;
 566   addToAccessGroupList(AccGroupSet2, MD2);
 567
 568   SmallVector<Metadata *, 4> Intersection;
 569   if (MD1->getNumOperands() == 0) {
 570     assert(isValidAsAccessGroup(MD1) && "Node must be an access group");
 571     if (AccGroupSet2.count(MD1))
 572       Intersection.push_back(MD1);
 573   } else {
 574     for (const MDOperand &Node : MD1->operands()) {
 575       auto *Item = cast<MDNode>(Node.get());
 576       assert(isValidAsAccessGroup(Item) && "List item must be an access group");
 577       if (AccGroupSet2.count(Item))
 578         Intersection.push_back(Item);
 579     }
 580   }
 581
 582   if (Intersection.size() == 0)
 583     return nullptr;
 584   if (Intersection.size() == 1)
 585     return cast<MDNode>(Intersection.front());
 586
 587   LLVMContext &Ctx = Inst1->getContext();
 588   return MDNode::get(Ctx, Intersection);
 589 }
 590
 591 /// \returns \p I after propagating metadata from \p VL.
 592 Instruction *llvm::propagateMetadata(Instruction *Inst, ArrayRef<Value *> VL) {
 593   Instruction *I0 = cast<Instruction>(VL[0]);
 594   SmallVector<std::pair<unsigned, MDNode *>, 4> Metadata;
 595   I0->getAllMetadataOtherThanDebugLoc(Metadata);
 596
 597   for (auto Kind : {LLVMContext::MD_tbaa, LLVMContext::MD_alias_scope,
 598                     LLVMContext::MD_noalias, LLVMContext::MD_fpmath,
 599                     LLVMContext::MD_nontemporal, LLVMContext::MD_invariant_load,
 600                     LLVMContext::MD_access_group}) {
 601     MDNode *MD = I0->getMetadata(Kind);
 602
 603     for (int J = 1, E = VL.size(); MD && J != E; ++J) {
 604       const Instruction *IJ = cast<Instruction>(VL[J]);
 605       MDNode *IMD = IJ->getMetadata(Kind);
 606       switch (Kind) {
 607       case LLVMContext::MD_tbaa:
 608         MD = MDNode::getMostGenericTBAA(MD, IMD);
 609         break;
 610       case LLVMContext::MD_alias_scope:
 611         MD = MDNode::getMostGenericAliasScope(MD, IMD);
 612         break;
 613       case LLVMContext::MD_fpmath:
 614         MD = MDNode::getMostGenericFPMath(MD, IMD);
 615         break;
 616       case LLVMContext::MD_noalias:
 617       case LLVMContext::MD_nontemporal:
 618       case LLVMContext::MD_invariant_load:
 619         MD = MDNode::intersect(MD, IMD);
 620         break;
 621       case LLVMContext::MD_access_group:
 622         MD = intersectAccessGroups(Inst, IJ);
 623         break;
 624       default:
 625         llvm_unreachable("unhandled metadata");
 626       }
 627     }
 628
 629     Inst->setMetadata(Kind, MD);
 630   }
 631
 632   return Inst;
 633 }
 634
 635 Constant *
 636 llvm::createBitMaskForGaps(IRBuilder<> &Builder, unsigned VF,
 637                            const InterleaveGroup<Instruction> &Group) {
 638   // All 1's means mask is not needed.
 639   if (Group.getNumMembers() == Group.getFactor())
 640     return nullptr;
 641
 642   // TODO: support reversed access.
 643   assert(!Group.isReverse() && "Reversed group not supported.");
 644
 645   SmallVector<Constant *, 16> Mask;
 646   for (unsigned i = 0; i < VF; i++)
 647     for (unsigned j = 0; j < Group.getFactor(); ++j) {
 648       unsigned HasMember = Group.getMember(j) ? 1 : 0;
 649       Mask.push_back(Builder.getInt1(HasMember));
 650     }
 651
 652   return ConstantVector::get(Mask);
 653 }
 654
 655 Constant *llvm::createReplicatedMask(IRBuilder<> &Builder,
 656                                      unsigned ReplicationFactor, unsigned VF) {
 657   SmallVector<Constant *, 16> MaskVec;
 658   for (unsigned i = 0; i < VF; i++)
 659     for (unsigned j = 0; j < ReplicationFactor; j++)
 660       MaskVec.push_back(Builder.getInt32(i));
 661
 662   return ConstantVector::get(MaskVec);
 663 }
 664
 665 Constant *llvm::createInterleaveMask(IRBuilder<> &Builder, unsigned VF,
 666                                      unsigned NumVecs) {
 667   SmallVector<Constant *, 16> Mask;
 668   for (unsigned i = 0; i < VF; i++)
 669     for (unsigned j = 0; j < NumVecs; j++)
 670       Mask.push_back(Builder.getInt32(j * VF + i));
 671
 672   return ConstantVector::get(Mask);
 673 }
 674
 675 Constant *llvm::createStrideMask(IRBuilder<> &Builder, unsigned Start,
 676                                  unsigned Stride, unsigned VF) {
 677   SmallVector<Constant *, 16> Mask;
 678   for (unsigned i = 0; i < VF; i++)
 679     Mask.push_back(Builder.getInt32(Start + i * Stride));
 680
 681   return ConstantVector::get(Mask);
 682 }
 683
 684 Constant *llvm::createSequentialMask(IRBuilder<> &Builder, unsigned Start,
 685                                      unsigned NumInts, unsigned NumUndefs) {
 686   SmallVector<Constant *, 16> Mask;
 687   for (unsigned i = 0; i < NumInts; i++)
 688     Mask.push_back(Builder.getInt32(Start + i));
 689
 690   Constant *Undef = UndefValue::get(Builder.getInt32Ty());
 691   for (unsigned i = 0; i < NumUndefs; i++)
 692     Mask.push_back(Undef);
 693
 694   return ConstantVector::get(Mask);
 695 }
 696
 697 /// A helper function for concatenating vectors. This function concatenates two
 698 /// vectors having the same element type. If the second vector has fewer
 699 /// elements than the first, it is padded with undefs.
 700 static Value *concatenateTwoVectors(IRBuilder<> &Builder, Value *V1,
 701                                     Value *V2) {
 702   VectorType *VecTy1 = dyn_cast<VectorType>(V1->getType());
 703   VectorType *VecTy2 = dyn_cast<VectorType>(V2->getType());
 704   assert(VecTy1 && VecTy2 &&
 705          VecTy1->getScalarType() == VecTy2->getScalarType() &&
 706          "Expect two vectors with the same element type");
 707
 708   unsigned NumElts1 = VecTy1->getNumElements();
 709   unsigned NumElts2 = VecTy2->getNumElements();
 710   assert(NumElts1 >= NumElts2 && "Unexpect the first vector has less elements");
 711
 712   if (NumElts1 > NumElts2) {
 713     // Extend with UNDEFs.
 714     Constant *ExtMask =
 715         createSequentialMask(Builder, 0, NumElts2, NumElts1 - NumElts2);
 716     V2 = Builder.CreateShuffleVector(V2, UndefValue::get(VecTy2), ExtMask);
 717   }
 718
 719   Constant *Mask = createSequentialMask(Builder, 0, NumElts1 + NumElts2, 0);
 720   return Builder.CreateShuffleVector(V1, V2, Mask);
 721 }
 722
 723 Value *llvm::concatenateVectors(IRBuilder<> &Builder, ArrayRef<Value *> Vecs) {
 724   unsigned NumVecs = Vecs.size();
 725   assert(NumVecs > 1 && "Should be at least two vectors");
 726
 727   SmallVector<Value *, 8> ResList;
 728   ResList.append(Vecs.begin(), Vecs.end());
 729   do {
 730     SmallVector<Value *, 8> TmpList;
 731     for (unsigned i = 0; i < NumVecs - 1; i += 2) {
 732       Value *V0 = ResList[i], *V1 = ResList[i + 1];
 733       assert((V0->getType() == V1->getType() || i == NumVecs - 2) &&
 734              "Only the last vector may have a different type");
 735
 736       TmpList.push_back(concatenateTwoVectors(Builder, V0, V1));
 737     }
 738
 739     // Push the last vector if the total number of vectors is odd.
 740     if (NumVecs % 2 != 0)
 741       TmpList.push_back(ResList[NumVecs - 1]);
 742
 743     ResList = TmpList;
 744     NumVecs = ResList.size();
 745   } while (NumVecs > 1);
 746
 747   return ResList[0];
 748 }
 749
 750 bool llvm::maskIsAllZeroOrUndef(Value *Mask) {
 751   auto *ConstMask = dyn_cast<Constant>(Mask);
 752   if (!ConstMask)
 753     return false;
 754   if (ConstMask->isNullValue() || isa<UndefValue>(ConstMask))
 755     return true;
 756   for (unsigned I = 0, E = ConstMask->getType()->getVectorNumElements(); I != E;
 757        ++I) {
 758     if (auto *MaskElt = ConstMask->getAggregateElement(I))
 759       if (MaskElt->isNullValue() || isa<UndefValue>(MaskElt))
 760         continue;
 761     return false;
 762   }
 763   return true;
 764 }
 765
 766
 767 bool llvm::maskIsAllOneOrUndef(Value *Mask) {
 768   auto *ConstMask = dyn_cast<Constant>(Mask);
 769   if (!ConstMask)
 770     return false;
 771   if (ConstMask->isAllOnesValue() || isa<UndefValue>(ConstMask))
 772     return true;
 773   for (unsigned I = 0, E = ConstMask->getType()->getVectorNumElements(); I != E;
 774        ++I) {
 775     if (auto *MaskElt = ConstMask->getAggregateElement(I))
 776       if (MaskElt->isAllOnesValue() || isa<UndefValue>(MaskElt))
 777         continue;
 778     return false;
 779   }
 780   return true;
 781 }
 782
 783 /// TODO: This is a lot like known bits, but for
 784 /// vectors.  Is there something we can common this with?
 785 APInt llvm::possiblyDemandedEltsInMask(Value *Mask) {
 786
 787   const unsigned VWidth = cast<VectorType>(Mask->getType())->getNumElements();
 788   APInt DemandedElts = APInt::getAllOnesValue(VWidth);
 789   if (auto *CV = dyn_cast<ConstantVector>(Mask))
 790     for (unsigned i = 0; i < VWidth; i++)
 791       if (CV->getAggregateElement(i)->isNullValue())
 792         DemandedElts.clearBit(i);
 793   return DemandedElts;
 794 }
 795
 796 bool InterleavedAccessInfo::isStrided(int Stride) {
 797   unsigned Factor = std::abs(Stride);
 798   return Factor >= 2 && Factor <= MaxInterleaveGroupFactor;
 799 }
 800
 801 void InterleavedAccessInfo::collectConstStrideAccesses(
 802     MapVector<Instruction *, StrideDescriptor> &AccessStrideInfo,
 803     const ValueToValueMap &Strides) {
 804   auto &DL = TheLoop->getHeader()->getModule()->getDataLayout();
 805
 806   // Since it's desired that the load/store instructions be maintained in
 807   // "program order" for the interleaved access analysis, we have to visit the
 808   // blocks in the loop in reverse postorder (i.e., in a topological order).
 809   // Such an ordering will ensure that any load/store that may be executed
 810   // before a second load/store will precede the second load/store in
 811   // AccessStrideInfo.
 812   LoopBlocksDFS DFS(TheLoop);
 813   DFS.perform(LI);
 814   for (BasicBlock *BB : make_range(DFS.beginRPO(), DFS.endRPO()))
 815     for (auto &I : *BB) {
 816       auto *LI = dyn_cast<LoadInst>(&I);
 817       auto *SI = dyn_cast<StoreInst>(&I);
 818       if (!LI && !SI)
 819         continue;
 820
 821       Value *Ptr = getLoadStorePointerOperand(&I);
 822       // We don't check wrapping here because we don't know yet if Ptr will be
 823       // part of a full group or a group with gaps. Checking wrapping for all
 824       // pointers (even those that end up in groups with no gaps) will be overly
 825       // conservative. For full groups, wrapping should be ok since if we would
 826       // wrap around the address space we would do a memory access at nullptr
 827       // even without the transformation. The wrapping checks are therefore
 828       // deferred until after we've formed the interleaved groups.
 829       int64_t Stride = getPtrStride(PSE, Ptr, TheLoop, Strides,
 830                                     /*Assume=*/true, /*ShouldCheckWrap=*/false);
 831
 832       const SCEV *Scev = replaceSymbolicStrideSCEV(PSE, Strides, Ptr);
 833       PointerType *PtrTy = dyn_cast<PointerType>(Ptr->getType());
 834       uint64_t Size = DL.getTypeAllocSize(PtrTy->getElementType());
 835
 836       // An alignment of 0 means target ABI alignment.
 837       unsigned Align = getLoadStoreAlignment(&I);
 838       if (!Align)
 839         Align = DL.getABITypeAlignment(PtrTy->getElementType());
 840
 841       AccessStrideInfo[&I] = StrideDescriptor(Stride, Scev, Size, Align);
 842     }
 843 }
 844
 845 // Analyze interleaved accesses and collect them into interleaved load and
 846 // store groups.
 847 //
 848 // When generating code for an interleaved load group, we effectively hoist all
 849 // loads in the group to the location of the first load in program order. When
 850 // generating code for an interleaved store group, we sink all stores to the
 851 // location of the last store. This code motion can change the order of load
 852 // and store instructions and may break dependences.
 853 //
 854 // The code generation strategy mentioned above ensures that we won't violate
 855 // any write-after-read (WAR) dependences.
 856 //
 857 // E.g., for the WAR dependence:  a = A[i];      // (1)
 858 //                                A[i] = b;      // (2)
 859 //
 860 // The store group of (2) is always inserted at or below (2), and the load
 861 // group of (1) is always inserted at or above (1). Thus, the instructions will
 862 // never be reordered. All other dependences are checked to ensure the
 863 // correctness of the instruction reordering.
 864 //
 865 // The algorithm visits all memory accesses in the loop in bottom-up program
 866 // order. Program order is established by traversing the blocks in the loop in
 867 // reverse postorder when collecting the accesses.
 868 //
 869 // We visit the memory accesses in bottom-up order because it can simplify the
 870 // construction of store groups in the presence of write-after-write (WAW)
 871 // dependences.
 872 //
 873 // E.g., for the WAW dependence:  A[i] = a;      // (1)
 874 //                                A[i] = b;      // (2)
 875 //                                A[i + 1] = c;  // (3)
 876 //
 877 // We will first create a store group with (3) and (2). (1) can't be added to
 878 // this group because it and (2) are dependent. However, (1) can be grouped
 879 // with other accesses that may precede it in program order. Note that a
 880 // bottom-up order does not imply that WAW dependences should not be checked.
 881 void InterleavedAccessInfo::analyzeInterleaving(
 882                                  bool EnablePredicatedInterleavedMemAccesses) {
 883   LLVM_DEBUG(dbgs() << "LV: Analyzing interleaved accesses...\n");
 884   const ValueToValueMap &Strides = LAI->getSymbolicStrides();
 885
 886   // Holds all accesses with a constant stride.
 887   MapVector<Instruction *, StrideDescriptor> AccessStrideInfo;
 888   collectConstStrideAccesses(AccessStrideInfo, Strides);
 889
 890   if (AccessStrideInfo.empty())
 891     return;
 892
 893   // Collect the dependences in the loop.
 894   collectDependences();
 895
 896   // Holds all interleaved store groups temporarily.
 897   SmallSetVector<InterleaveGroup<Instruction> *, 4> StoreGroups;
 898   // Holds all interleaved load groups temporarily.
 899   SmallSetVector<InterleaveGroup<Instruction> *, 4> LoadGroups;
 900
 901   // Search in bottom-up program order for pairs of accesses (A and B) that can
 902   // form interleaved load or store groups. In the algorithm below, access A
 903   // precedes access B in program order. We initialize a group for B in the
 904   // outer loop of the algorithm, and then in the inner loop, we attempt to
 905   // insert each A into B's group if:
 906   //
 907   //  1. A and B have the same stride,
 908   //  2. A and B have the same memory object size, and
 909   //  3. A belongs in B's group according to its distance from B.
 910   //
 911   // Special care is taken to ensure group formation will not break any
 912   // dependences.
 913   for (auto BI = AccessStrideInfo.rbegin(), E = AccessStrideInfo.rend();
 914        BI != E; ++BI) {
 915     Instruction *B = BI->first;
 916     StrideDescriptor DesB = BI->second;
 917
 918     // Initialize a group for B if it has an allowable stride. Even if we don't
 919     // create a group for B, we continue with the bottom-up algorithm to ensure
 920     // we don't break any of B's dependences.
 921     InterleaveGroup<Instruction> *Group = nullptr;
 922     if (isStrided(DesB.Stride) &&
 923         (!isPredicated(B->getParent()) || EnablePredicatedInterleavedMemAccesses)) {
 924       Group = getInterleaveGroup(B);
 925       if (!Group) {
 926         LLVM_DEBUG(dbgs() << "LV: Creating an interleave group with:" << *B
 927                           << '\n');
 928         Group = createInterleaveGroup(B, DesB.Stride, DesB.Align);
 929       }
 930       if (B->mayWriteToMemory())
 931         StoreGroups.insert(Group);
 932       else
 933         LoadGroups.insert(Group);
 934     }
 935
 936     for (auto AI = std::next(BI); AI != E; ++AI) {
 937       Instruction *A = AI->first;
 938       StrideDescriptor DesA = AI->second;
 939
 940       // Our code motion strategy implies that we can't have dependences
 941       // between accesses in an interleaved group and other accesses located
 942       // between the first and last member of the group. Note that this also
 943       // means that a group can't have more than one member at a given offset.
 944       // The accesses in a group can have dependences with other accesses, but
 945       // we must ensure we don't extend the boundaries of the group such that
 946       // we encompass those dependent accesses.
 947       //
 948       // For example, assume we have the sequence of accesses shown below in a
 949       // stride-2 loop:
 950       //
 951       //  (1, 2) is a group | A[i]   = a;  // (1)
 952       //                    | A[i-1] = b;  // (2) |
 953       //                      A[i-3] = c;  // (3)
 954       //                      A[i]   = d;  // (4) | (2, 4) is not a group
 955       //
 956       // Because accesses (2) and (3) are dependent, we can group (2) with (1)
 957       // but not with (4). If we did, the dependent access (3) would be within
 958       // the boundaries of the (2, 4) group.
 959       if (!canReorderMemAccessesForInterleavedGroups(&*AI, &*BI)) {
 960         // If a dependence exists and A is already in a group, we know that A
 961         // must be a store since A precedes B and WAR dependences are allowed.
 962         // Thus, A would be sunk below B. We release A's group to prevent this
 963         // illegal code motion. A will then be free to form another group with
 964         // instructions that precede it.
 965         if (isInterleaved(A)) {
 966           InterleaveGroup<Instruction> *StoreGroup = getInterleaveGroup(A);
 967           StoreGroups.remove(StoreGroup);
 968           releaseGroup(StoreGroup);
 969         }
 970
 971         // If a dependence exists and A is not already in a group (or it was
 972         // and we just released it), B might be hoisted above A (if B is a
 973         // load) or another store might be sunk below A (if B is a store). In
 974         // either case, we can't add additional instructions to B's group. B
 975         // will only form a group with instructions that it precedes.
 976         break;
 977       }
 978
 979       // At this point, we've checked for illegal code motion. If either A or B
 980       // isn't strided, there's nothing left to do.
 981       if (!isStrided(DesA.Stride) || !isStrided(DesB.Stride))
 982         continue;
 983
 984       // Ignore A if it's already in a group or isn't the same kind of memory
 985       // operation as B.
 986       // Note that mayReadFromMemory() isn't mutually exclusive to
 987       // mayWriteToMemory in the case of atomic loads. We shouldn't see those
 988       // here, canVectorizeMemory() should have returned false - except for the
 989       // case we asked for optimization remarks.
 990       if (isInterleaved(A) ||
 991           (A->mayReadFromMemory() != B->mayReadFromMemory()) ||
 992           (A->mayWriteToMemory() != B->mayWriteToMemory()))
 993         continue;
 994
 995       // Check rules 1 and 2. Ignore A if its stride or size is different from
 996       // that of B.
 997       if (DesA.Stride != DesB.Stride || DesA.Size != DesB.Size)
 998         continue;
 999
1000       // Ignore A if the memory object of A and B don't belong to the same
1001       // address space
1002       if (getLoadStoreAddressSpace(A) != getLoadStoreAddressSpace(B))
1003         continue;
1004
1005       // Calculate the distance from A to B.
1006       const SCEVConstant *DistToB = dyn_cast<SCEVConstant>(
1007           PSE.getSE()->getMinusSCEV(DesA.Scev, DesB.Scev));
1008       if (!DistToB)
1009         continue;
1010       int64_t DistanceToB = DistToB->getAPInt().getSExtValue();
1011
1012       // Check rule 3. Ignore A if its distance to B is not a multiple of the
1013       // size.
1014       if (DistanceToB % static_cast<int64_t>(DesB.Size))
1015         continue;
1016
1017       // All members of a predicated interleave-group must have the same predicate,
1018       // and currently must reside in the same BB.
1019       BasicBlock *BlockA = A->getParent();
1020       BasicBlock *BlockB = B->getParent();
1021       if ((isPredicated(BlockA) || isPredicated(BlockB)) &&
1022           (!EnablePredicatedInterleavedMemAccesses || BlockA != BlockB))
1023         continue;
1024
1025       // The index of A is the index of B plus A's distance to B in multiples
1026       // of the size.
1027       int IndexA =
1028           Group->getIndex(B) + DistanceToB / static_cast<int64_t>(DesB.Size);
1029
1030       // Try to insert A into B's group.
1031       if (Group->insertMember(A, IndexA, DesA.Align)) {
1032         LLVM_DEBUG(dbgs() << "LV: Inserted:" << *A << '\n'
1033                           << "    into the interleave group with" << *B
1034                           << '\n');
1035         InterleaveGroupMap[A] = Group;
1036
1037         // Set the first load in program order as the insert position.
1038         if (A->mayReadFromMemory())
1039           Group->setInsertPos(A);
1040       }
1041     } // Iteration over A accesses.
1042   }   // Iteration over B accesses.
1043
1044   // Remove interleaved store groups with gaps.
1045   for (auto *Group : StoreGroups)
1046     if (Group->getNumMembers() != Group->getFactor()) {
1047       LLVM_DEBUG(
1048           dbgs() << "LV: Invalidate candidate interleaved store group due "
1049                     "to gaps.\n");
1050       releaseGroup(Group);
1051     }
1052   // Remove interleaved groups with gaps (currently only loads) whose memory
1053   // accesses may wrap around. We have to revisit the getPtrStride analysis,
1054   // this time with ShouldCheckWrap=true, since collectConstStrideAccesses does
1055   // not check wrapping (see documentation there).
1056   // FORNOW we use Assume=false;
1057   // TODO: Change to Assume=true but making sure we don't exceed the threshold
1058   // of runtime SCEV assumptions checks (thereby potentially failing to
1059   // vectorize altogether).
1060   // Additional optional optimizations:
1061   // TODO: If we are peeling the loop and we know that the first pointer doesn't
1062   // wrap then we can deduce that all pointers in the group don't wrap.
1063   // This means that we can forcefully peel the loop in order to only have to
1064   // check the first pointer for no-wrap. When we'll change to use Assume=true
1065   // we'll only need at most one runtime check per interleaved group.
1066   for (auto *Group : LoadGroups) {
1067     // Case 1: A full group. Can Skip the checks; For full groups, if the wide
1068     // load would wrap around the address space we would do a memory access at
1069     // nullptr even without the transformation.
1070     if (Group->getNumMembers() == Group->getFactor())
1071       continue;
1072
1073     // Case 2: If first and last members of the group don't wrap this implies
1074     // that all the pointers in the group don't wrap.
1075     // So we check only group member 0 (which is always guaranteed to exist),
1076     // and group member Factor - 1; If the latter doesn't exist we rely on
1077     // peeling (if it is a non-reversed accsess -- see Case 3).
1078     Value *FirstMemberPtr = getLoadStorePointerOperand(Group->getMember(0));
1079     if (!getPtrStride(PSE, FirstMemberPtr, TheLoop, Strides, /*Assume=*/false,
1080                       /*ShouldCheckWrap=*/true)) {
1081       LLVM_DEBUG(
1082           dbgs() << "LV: Invalidate candidate interleaved group due to "
1083                     "first group member potentially pointer-wrapping.\n");
1084       releaseGroup(Group);
1085       continue;
1086     }
1087     Instruction *LastMember = Group->getMember(Group->getFactor() - 1);
1088     if (LastMember) {
1089       Value *LastMemberPtr = getLoadStorePointerOperand(LastMember);
1090       if (!getPtrStride(PSE, LastMemberPtr, TheLoop, Strides, /*Assume=*/false,
1091                         /*ShouldCheckWrap=*/true)) {
1092         LLVM_DEBUG(
1093             dbgs() << "LV: Invalidate candidate interleaved group due to "
1094                       "last group member potentially pointer-wrapping.\n");
1095         releaseGroup(Group);
1096       }
1097     } else {
1098       // Case 3: A non-reversed interleaved load group with gaps: We need
1099       // to execute at least one scalar epilogue iteration. This will ensure
1100       // we don't speculatively access memory out-of-bounds. We only need
1101       // to look for a member at index factor - 1, since every group must have
1102       // a member at index zero.
1103       if (Group->isReverse()) {
1104         LLVM_DEBUG(
1105             dbgs() << "LV: Invalidate candidate interleaved group due to "
1106                       "a reverse access with gaps.\n");
1107         releaseGroup(Group);
1108         continue;
1109       }
1110       LLVM_DEBUG(
1111           dbgs() << "LV: Interleaved group requires epilogue iteration.\n");
1112       RequiresScalarEpilogue = true;
1113     }
1114   }
1115 }
1116
1117 void InterleavedAccessInfo::invalidateGroupsRequiringScalarEpilogue() {
1118   // If no group had triggered the requirement to create an epilogue loop,
1119   // there is nothing to do.
1120   if (!requiresScalarEpilogue())
1121     return;
1122
1123   // Avoid releasing a Group twice.
1124   SmallPtrSet<InterleaveGroup<Instruction> *, 4> DelSet;
1125   for (auto &I : InterleaveGroupMap) {
1126     InterleaveGroup<Instruction> *Group = I.second;
1127     if (Group->requiresScalarEpilogue())
1128       DelSet.insert(Group);
1129   }
1130   for (auto *Ptr : DelSet) {
1131     LLVM_DEBUG(
1132         dbgs()
1133         << "LV: Invalidate candidate interleaved group due to gaps that "
1134            "require a scalar epilogue (not allowed under optsize) and cannot "
1135            "be masked (not enabled). \n");
1136     releaseGroup(Ptr);
1137   }
1138
1139   RequiresScalarEpilogue = false;
1140 }
1141
1142 template <typename InstT>
1143 void InterleaveGroup<InstT>::addMetadata(InstT *NewInst) const {
1144   llvm_unreachable("addMetadata can only be used for Instruction");
1145 }
1146
1147 namespace llvm {
1148 template <>
1149 void InterleaveGroup<Instruction>::addMetadata(Instruction *NewInst) const {
1150   SmallVector<Value *, 4> VL;
1151   std::transform(Members.begin(), Members.end(), std::back_inserter(VL),
1152                  [](std::pair<int, Instruction *> p) { return p.second; });
1153   propagateMetadata(NewInst, VL);
1154 }
1155 }