[AArch64] Match interleaved memory accesses into ldN/stN instructions.

[• HaoLiu]

Summary

Hi,

The Loop Vectorizor can identify and generate interleaved memory access in the middle end.

E.g. for (i = 0; i < N; i+=2) {
       a = A[i];         // load of even element
       b = A[i+1];       // load of odd element
       ...               // operations on a, b, c, d
       A[i] = c;         // store of even element
       A[i+1] = d;       // store of odd element
     }
  
  The loads of even and odd elements are identified as an interleave load group, which will be transfered into
     %wide.vec = load <8 x i32>, <8 x i32>* %ptr
     %vec.even = shufflevector <8 x i32> %wide.vec, <8 x i32> undef, <4 x i32> <i32 0, i32 2, i32 4, i32 6>
     %vec.odd = shufflevector <8 x i32> %wide.vec, <8 x i32> undef, <4 x i32> <i32 1, i32 3, i32 5, i32 7>
  
  The stores of even and odd elements are identified as an interleave store group, which will be transfered in
     %interleaved.vec = shufflevector <4 x i32> %vec.even, %vec.odd, <8 x i32> <i32 0, i32 4, i32 1, i32 5, i3
     store <8 x i32> %interleaved.vec, <8 x i32>* %ptr

This patch try to identify such interleaved load/store and match them into AArch64 ldN/stN intrinsics in the backend. Such intrinsics can be directly selected into ldN/stN instructions in the CodeGen phase.
A new function pass AArch64InterleavedAccess is added. I don't implement such functionality in the CodeGen phase, because:

The DAG node VECTOR_SHUFFLE requires the result type is the same as the operand type. One shufflevector IR maybe transfered into several nodes on DAG and the mask is changed as well. It's more difficult to identify such pattern.
Another reason is CodeGen can only see one basic block.

This pass is default to be disabled as the Loop Vectorize currently disables optimization on interleaved accesses by default. We can enable them in the future after fully test.

Also, I have a similar patch for ARM backend. I'll send it out if this patch is approved. Otherwise it is unnecessary to review that patch.

Review please.

Thanks,
-Hao

[• HaoLiu]

Update a patch fixes a typo.

[jmolloy]

Hi Hao,

I have some comments below. I think it would have been nicer if we'd managed to get this into CodeGen, but I do see the difficulties there. It's hard enough to match at the IR level!

My larger concern is how we're going to do this for ARM32 too without duplicating the entire pass... If there were somewhere we could put a templated version of this pass that ARM could use too, that would be great. I'm not a fan of copy-paste on this scale.

Cheers,

James

lib/Target/AArch64/AArch64InterleavedAccess.cpp

61

This would probably be easier simply as two const ints. Enum is overkill.

162

I would expect here you to check whether SVI is in DeadInsts, as we may have identified it earlier. If you don't, I'd expect we'd create multiple LDN instructions unnecessarily!

173

The order of these checks doesn't seem the most efficient to me. You have a load that has at least one ShuffleVector using it. You're checking the ShuffleVector is a valid mask first, then checking all other Load users.

I'd expect the code would be simpler if:

1. Check the illegal vector type size.
2. Check the load only had ShuffleVector users.
3. Check each ShuffleVector is a strided index.

I guess what I think is strange is that this function takes a ShuffleVector as its argument, rather than a LoadInst.

237

This is weird - surely you should just put it into DeadInsts?

251

Please move this static function up to where all the other static functions are.

I got confused initially how this function was different to isStridedMask above. The difference is that this function checks for a mask that RE-interleaves, whereas isStridedMask checks for a mask that DE-interleaves. Please make that more clear in the function name / comments.

lib/Target/AArch64/AArch64TargetTransformInfo.cpp

416

Why does a ld2 have a different cost to a ld3 here?

[• HaoLiu]

Hi James,

Thanks for your comments. I've updated a new patch.

About your concern, the ARM32 patch is similar to this patch. I agree with you that we'd better share the code. But I couldn't find a place for sharing such backend code.

Thanks,
-Hao

lib/Target/AArch64/AArch64InterleavedAccess.cpp

61

Reasonable.

162

Reasonable.

173

I've updated the code.

The order is different, I firstly check 2, and then check 1, and 3 (They are all about one shufflevector).

Using a ShuffleVector as argument is to make this pass more efficient. I just think a program should have much more loads/stores than shufflevectors.

237

Done.

251

Renamed and updated the comments.

lib/Target/AArch64/AArch64TargetTransformInfo.cpp

416

This is just a rough cost.

The A57 optimisation guide says ldN instructions with different N and types have different cost, ranging from 6 to 11. But generally larger N means higher cost, so I use the factor as the cost.

I think it needs tuning in the future, but now it can work well. The following cost for N > 4 also needs tuning.

[jmolloy]

Hi Hao,

Thanks for making those changes. With the few typographical comments below corrected, this LGTM.

Thanks!

James

lib/Target/AArch64/AArch64InterleavedAccess.cpp

1

Something weird's gone on with this comment line. It's not in the standard form.

29

You use the word "transfer" but actually the right word is "transform". Could you please find-and-replace?

52

We don't use #defines. Suggest you use a static const int MAX_FACTOR = 2; instead.

195

consists -> consisting

lib/Target/AArch64/AArch64TargetMachine.cpp

72

in -> "in the"

[rengolin]

In D10335#186081, @jmolloy wrote:

I have some comments below. I think it would have been nicer if we'd managed to get this into CodeGen, but I do see the difficulties there. It's hard enough to match at the IR level!

There are two things we should common up: the static methods and AArch64InterleavedAccess.

The first one is easier, but the second one might be more important. I think it should be fine to add an InterleavedAccess.cpp into lib/CodeGen and have only AArch64 for now. Later, when we do ARM, you can rebase the AARch64 into a generic class, once we know more what the similarities are.

Meanwhile, that cpp file will contain the static methods, so when we do have an ARM version, we can easily reuse.

cheers,
--renato

[mzolotukhin]

Hi Hao,

Thanks for the patch. The general idea sounds good to me, but I have some questions regarding some implementation details. To address them, it would actually be helpful to see the ARM32 patch too, since I expect that a lot of the stuff can be reused, as James and Renato have already mentioned.

For instance, functions like isReInterleaveMask look totally target independent. Would it be possible to make a target-independent implementation with a bunch of target hooks (like getInterleavedStoreIntrinsic(Factor, Size))? Then, ARM32 and ARM64 patches would differ only in those hooks, while the rest of the code would be reused.

lib/Target/AArch64/AArch64InterleavedAccess.cpp

146–148

if (Mask.size() < 2)
  return false;

?

247

Is there a need to redeclare Index here?

279

One more redeclaration of Index.

351

Why 5?

[sbaranga]

Hi Hao,

Another comment from me as well.

Thanks,
Silviu

lib/Target/AArch64/AArch64TargetTransformInfo.cpp

415

If we get a a legal type here that cannot be matched by the pass (for example v4i8) this will produce the wrong cost.
I think we also need to check that the type size is either 64 or 128.

[sbaranga]

lib/Target/AArch64/AArch64TargetTransformInfo.cpp

415

I've looked into this some more, and it seems that the issue is that the size of VecTy is the size of the entire interleaved group. So I think what needs to change here is the check to isTypeLegal to something like:

isTypeLegal(VectorType::get(VecTy->getScalarType(), VecTy->getVectorNumElements()/Factor));

[• HaoLiu]

Hi,

I've refactored the patch according to comments from Michael and Silviu.

As the ARM backend code is ready, I also added ARM code in this patch, so that we can compare and figure out how to share code between AArch64 backend and ARM backend.

As you can see, most of the static functions can be shared. But the problem is the code in matchInterleavedLoad()/matchInterleavedStore() can not be shared. The call of ldN and vldN intrinsics are different:

AArch64 backend:
    %vec = tail call { <8 x i8>, <8 x i8> } @llvm.aarch64.neon.ld2.v8i8.p0v8i8(<8 x i8>* %ptr)
    call void @llvm.aarch64.neon.st2.v16i8.p0i8(<16 x i8> %A, <16 x i8> %B, i8* %ptr)
ARM backend:
    %vec = tail call { <8 x i8>, <8 x i8> } @llvm.arm.neon.vld2.v8i8(i8* %ptr, i32 1)
    call void @llvm.arm.neon.vst2.v8i8(i8* %ptr, <8 x i8> %A, <8 x i8> %B, i32 1)

The ldN and vldN have different parameters. So It's hard to share the code about creating intrinsic calls. We can introduce new intrinsics like llvm.neon.ldN for both AArch64 and ARM, but it means we also need to modify all the code related to the old ldN/vldN intrinsics. Do you have any ideas about problem?

About the place, as Renato and James suggested, I think lib/CodeGen is a reasonable place. I think maybe we can put code in the lib/CodeGen/CodeGenPrepare.cpp, which already has a function called CodeGenPrepare::OptimizeShuffleVectorInst(ShuffleVectorInst *SVI). This function currently optimizes BroadcastShuffle for X86.

Thanks,
-Hao

lib/Target/AArch64/AArch64InterleavedAccess.cpp

146–148

Fixed.

247

Removed the re-declaration.

279

Removed re-declaration.

351

We have at most 5 operands for calling ldN intrinsics (The most one: The ld4 call needs 4 vectors and 1 pointer as arguments).

lib/Target/AArch64/AArch64TargetTransformInfo.cpp

415

Silviu, you are right. Fixed in the new patch.

[• HaoLiu]

ping...

Do you guys have any idea about sharing the matchInterleavedLoad()/matchInterleavedStore()?

If we can not share such function, I think we have to use two pass ARMInterleavedAccess and AArch64InterleavedAccess separately for ARM and AArch64 backends.

Thanks,
-Hao

[• HaoLiu]

I've created a new patch to share code between ARM and AArch64 backends. Abondon this patch.

lib/Target/AArch64/AArch64.h

 FunctionPass *createAArch64ISelDag(AArch64TargetMachine &TM,
                                  CodeGenOpt::Level OptLevel);
 FunctionPass *createAArch64StorePairSuppressPass();
 FunctionPass *createAArch64ExpandPseudoPass();
 FunctionPass *createAArch64LoadStoreOptimizationPass();
 ModulePass *createAArch64PromoteConstantPass();
 FunctionPass *createAArch64ConditionOptimizerPass();
 FunctionPass *createAArch64AddressTypePromotionPass();
+FunctionPass *createAArch64InterleavedAccessPass();
 FunctionPass *createAArch64A57FPLoadBalancing();
 FunctionPass *createAArch64A53Fix835769();
 
 FunctionPass *createAArch64CleanupLocalDynamicTLSPass();
 
 FunctionPass *createAArch64CollectLOHPass();
 } // end namespace llvm
 
 #endif

lib/Target/AArch64/AArch64InterleavedAccess.cpp

+//=------------- ------- AArch64InterleavedAccess.cpp --------- ------------==//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements the AArch64InterleavedAccess pass, which identifies
+// interleaved memory accesses and transfers them into an AArch64 ldN/stN
+// intrinsics (N = 2, 3, 4).
+//
+// An interleaved load reads data from memory into several vectors, with
+// DE-interleaving the data on factor. An interleaved store writes several
+// vectors to memory with RE-interleaving the data on factor. The interleave
+// factor is equal to the number of vectors. AArch64 backend supports interleave
+// factor of 2, 3 and 4.
+//
+// E.g. Transfer an interleaved load (Factor = 2):
+//        %wide.vec = load <8 x i32>, <8 x i32>* %ptr
+//        %v0 = shuffle %wide.vec, undef, <0, 2, 4, 6>  ; Extract even elements
+//        %v1 = shuffle %wide.vec, undef, <1, 3, 5, 7>  ; Extract odd elements
+//      Into:
+//        %ld2 = { <4 x i32>, <4 x i32> } call aarch64.neon.ld2(%ptr)
+//        %v0 = extractelement { <4 x i32>, <4 x i32> } %ld2, i32 0
+//        %v1 = extractelement { <4 x i32>, <4 x i32> } %ld2, i32 1
+//
+// E.g. Transfer an interleaved store (Factor = 2):
+//        %i.vec = shuffle %v0, %v1, <0, 4, 1, 5, 2, 6, 3, 7>  ; Interleaved vec
+//        store <8 x i32> %i.vec, <8 x i32>* %ptr
+//      Into:
+//        %v0 = shuffle %i.vec, undef, <0, 1, 2, 3>
+//        %v1 = shuffle %i.vec, undef, <4, 5, 6, 7>
+//        call void aarch64.neon.st2(%v0, %v1, %ptr)
+//
+//===----------------------------------------------------------------------===//
+
+#include "AArch64.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/IRBuilder.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Support/MathExtras.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "aarch64-interleaved-access"
+
+#define MIN_FACTOR 2
+#define MAX_FACTOR 4
+
+namespace llvm {
+static void initializeAArch64InterleavedAccessPass(PassRegistry &);
+}
+
+namespace {
+
+class AArch64InterleavedAccess : public FunctionPass {
+
+public:
+  static char ID;
+  AArch64InterleavedAccess() : FunctionPass(ID) {
+    initializeAArch64InterleavedAccessPass(*PassRegistry::getPassRegistry());
+  }
+
+  const char *getPassName() const override {
+    return "AArch64 Interleaved Access Pass";
+  }
+
+  bool runOnFunction(Function &F) override;
+
+private:
+  const DataLayout *DL;
+  Module *M;
+
+  /// \brief Transfer an interleaved load into ldN intrinsic.
+  bool matchInterleavedLoad(ShuffleVectorInst *SVI,
+                            SmallSetVector<Instruction *, 32> &DeadInsts);
+
+  /// \brief Transfer an interleaved store into stN intrinsic.
+  bool matchInterleavedStore(ShuffleVectorInst *SVI,
+                             SmallSetVector<Instruction *, 32> &DeadInsts);
+};
+} // end anonymous namespace.
+
+char AArch64InterleavedAccess::ID = 0;
+
+INITIALIZE_PASS_BEGIN(AArch64InterleavedAccess, DEBUG_TYPE,
+                      "AArch64 interleaved access Pass", false, false)
+INITIALIZE_PASS_END(AArch64InterleavedAccess, DEBUG_TYPE,
+                    "AArch64 interleaved access Pass", false, false)
+
+FunctionPass *llvm::createAArch64InterleavedAccessPass() {
+  return new AArch64InterleavedAccess();
+}
+
+/// \brief Get a ldN/stN intrinsic according to the Factor (2, 3, or 4).
+static Intrinsic::ID getLdNStNIntrinsic(unsigned Factor, bool IsLoad) {
+  static Intrinsic::ID LoadInt[3] = {Intrinsic::aarch64_neon_ld2,
+                                     Intrinsic::aarch64_neon_ld3,
+                                     Intrinsic::aarch64_neon_ld4};
+  static Intrinsic::ID StoreInt[3] = {Intrinsic::aarch64_neon_st2,
+                                      Intrinsic::aarch64_neon_st3,
+                                      Intrinsic::aarch64_neon_st4};
+
+  assert(Factor >= MIN_FACTOR && Factor <= MAX_FACTOR &&
+         "Invalid interleave factor");
+
+  if (IsLoad)
+    return LoadInt[Factor - 2];
+  else
+    return StoreInt[Factor - 2];
+}
+
+/// \brief Check if the mask is a DE-interleave mask of the given factor
+/// \p Factor like:
+///     <Index, Index+Factor, ..., Index+(NumElts-1)*Factor>
+static bool isDeInterleaveMaskOfFactor(ArrayRef<int> Mask, unsigned Factor,
+                                       unsigned &Index) {
+  // Check all potential start indices from 0 to (Factor - 1).
+  for (Index = 0; Index < Factor; Index++) {
+    unsigned i = 0;
+
+    // Check that elements are in ascending order by Factor.
+    for (; i < Mask.size(); i++)
+      if (Mask[i] >= 0 && static_cast<unsigned>(Mask[i]) != Index + i * Factor)
+        break;
+
+    if (i == Mask.size())
+      return true;
+  }
+
+  return false;
+}
+
+/// \brief Check if the mask is a DE-interleave mask for an interleaved load.
+///
+/// E.g. DE-interleave masks (Factor = 2) could be:
+///     <0, 2, 4, 6>    (mask of index 0 to extract even elements)
+///     <1, 3, 5, 7>    (mask of index 1 to extract odd elements)
+static bool isDeInterleaveMask(ArrayRef<int> Mask, unsigned &Factor,
+                               unsigned &Index) {
+  unsigned NumElts = Mask.size();
+  if (NumElts < 2)
+    return false;
+
+  for (Factor = MIN_FACTOR; Factor <= MAX_FACTOR; Factor++)
+    if (isDeInterleaveMaskOfFactor(Mask, Factor, Index))
+      return true;
+
+  return false;
+}
+
+/// \brief Check if the given mask \p Mask is RE-interleaved mask of the given
+/// factor \p Factor.
+///
+/// I.e. <0, NumSubElts, ... , NumSubElts*(Factor - 1), 1, NumSubElts + 1, ...>
+static bool isReInterleaveMaskOfFactor(ArrayRef<int> Mask, unsigned Factor) {
+  unsigned NumElts = Mask.size();
+  if (NumElts % Factor)
+    return false;
+
+  unsigned NumSubElts = NumElts / Factor;
+  if (!isPowerOf2_32(NumSubElts))
+    return false;
+
+  for (unsigned i = 0; i < NumSubElts; i++)
+    for (unsigned j = 0; j < Factor; j++)
+      if (Mask[i * Factor + j] >= 0 &&
+          static_cast<unsigned>(Mask[i * Factor + j]) != j * NumSubElts + i)
+        return false;
+
+  return true;
+}
+
+/// \brief Check if the mask is RE-interleave mask for an interleaved store.
+///
+/// E.g. The RE-interleave mask (Factor = 2) could be:
+///     <0, 4, 1, 5, 2, 6, 3, 7>
+static bool isReInterleaveMask(ArrayRef<int> Mask, unsigned &Factor) {
+  if (Mask.size() < 4)
+    return false;
+
+  // Check potential Factors and return true if find a factor for the mask.
+  for (Factor = MIN_FACTOR; Factor <= MAX_FACTOR; Factor++)
+    if (isReInterleaveMaskOfFactor(Mask, Factor))
+      return true;
+
+  return false;
+}
+
+/// \brief Get a mask consists of sequential integers starting from \p Start.
+///
+/// I.e. <Start, Start + 1, ..., Start + NumElts - 1>
+static Constant *getSequentialMask(IRBuilder<> &Builder, unsigned Start,
+                                   unsigned NumElts) {
+  SmallVector<Constant *, 16> Mask;
+  for (unsigned i = 0; i < NumElts; i++)
+    Mask.push_back(Builder.getInt32(Start + i));
+
+  return ConstantVector::get(Mask);
+}
+
+bool AArch64InterleavedAccess::matchInterleavedLoad(
+    ShuffleVectorInst *SVI, SmallSetVector<Instruction *, 32> &DeadInsts) {
+  if (DeadInsts.count(SVI))
+    return false;
+
+  LoadInst *LI = dyn_cast<LoadInst>(SVI->getOperand(0));
+  if (!LI || !LI->isSimple() || !isa<UndefValue>(SVI->getOperand(1)))
+    return false;
+
+  SmallVector<ShuffleVectorInst *, 4> Shuffles;
+
+  // Check if all users of this load are shufflevectors.
+  for (auto UI = LI->user_begin(), E = LI->user_end(); UI != E; UI++) {
+    ShuffleVectorInst *SV = dyn_cast<ShuffleVectorInst>(*UI);
+    if (!SV)
+      return false;
+
+    Shuffles.push_back(SV);
+  }
+
+  // Check if the type of the first shuffle is legal.
+  VectorType *VecTy = Shuffles[0]->getType();
+  unsigned TypeSize = DL->getTypeAllocSizeInBits(VecTy);
+  if (TypeSize != 64 && TypeSize != 128)
+    return false;
+
+  // Check if the mask of the first shuffle is strided and get the start index.
+  unsigned Factor, Index;
+  if (!isDeInterleaveMask(Shuffles[0]->getShuffleMask(), Factor, Index))
+    return false;
+
+  // Holds the corresponding index for each strided shuffle.
+  SmallVector<unsigned, 4> Indices;
+  Indices.push_back(Index);
+
+  // Check if other shufflevectors are of the same type and factor
+  for (unsigned i = 1; i < Shuffles.size(); i++) {
+    if (Shuffles[i]->getType() != VecTy)
+      return false;
+
+    unsigned Index;
+    if (!isDeInterleaveMaskOfFactor(Shuffles[i]->getShuffleMask(), Factor,
+                                    Index))
+      return false;
+
+    Indices.push_back(Index);
+  }
+
+  DEBUG(dbgs() << "Found an interleaved load:" << *LI << "\n");
+
+  // A pointer vector can not be the return type of the ldN intrinsics. Need to
+  // load integer vectors first and then convert to pointer vectors.
+  Type *EltTy = VecTy->getVectorElementType();
+  if (EltTy->isPointerTy())
+    VecTy = VectorType::get(DL->getIntPtrType(EltTy),
+                            VecTy->getVectorNumElements());
+
+  Type *PtrTy = VecTy->getPointerTo(LI->getPointerAddressSpace());
+  Type *Tys[2] = {VecTy, PtrTy};
+  Function *LdNFunc =
+      Intrinsic::getDeclaration(M, getLdNStNIntrinsic(Factor, true), Tys);
+
+  IRBuilder<> Builder(LI);
+  Value *Ptr = Builder.CreateBitCast(LI->getPointerOperand(), PtrTy);
+
+  CallInst *LdN = Builder.CreateCall(LdNFunc, Ptr, "ldN");
+  DEBUG(dbgs() << "   Created:" << *LdN << "\n");
+
+  // Replace each strided shufflevector with the corresponding vector loaded
+  // by ldN.
+  for (unsigned i = 0; i < Shuffles.size(); i++) {
+    ShuffleVectorInst *SV = Shuffles[i];
+    unsigned Index = Indices[i];
+
+    Value *SubVec = Builder.CreateExtractValue(LdN, Index);
+
+    // Convert the integer vector to pointer vector if the element is pointer.
+    if (EltTy->isPointerTy())
+      SubVec = Builder.CreateIntToPtr(SubVec, SV->getType());
+
+    SV->replaceAllUsesWith(SubVec);
+
+    DEBUG(dbgs() << "  Replaced:" << *SV << "\n"
+                 << "      With:" << *SubVec << "\n");
+
+    // Avoid analyzing it twice.
+    DeadInsts.insert(SV);
+  }
+
+  // Mark this load as dead.
+  DeadInsts.insert(LI);
+  return true;
+}
+
+bool AArch64InterleavedAccess::matchInterleavedStore(
+    ShuffleVectorInst *SVI, SmallSetVector<Instruction *, 32> &DeadInsts) {
+  if (DeadInsts.count(SVI) || !SVI->hasOneUse())
+    return false;
+
+  StoreInst *SI = dyn_cast<StoreInst>(SVI->user_back());
+  if (!SI || !SI->isSimple())
+    return false;
+
+  // Check if the mask is interleaved and get the interleave factor.
+  unsigned Factor;
+  if (!isReInterleaveMask(SVI->getShuffleMask(), Factor))
+    return false;
+
+  VectorType *VecTy = SVI->getType();
+  unsigned NumSubElts = VecTy->getVectorNumElements() / Factor;
+  Type *EltTy = VecTy->getVectorElementType();
+  VectorType *SubVecTy = VectorType::get(EltTy, NumSubElts);
+
+  // Skip illegal vector types.
+  unsigned TypeSize = DL->getTypeAllocSizeInBits(SubVecTy);
+  if (TypeSize != 64 && TypeSize != 128)
+    return false;
+
+  DEBUG(dbgs() << "Found an interleaved store:" << *SI << "\n");
+
+  Value *Op0 = SVI->getOperand(0);
+  Value *Op1 = SVI->getOperand(1);
+  IRBuilder<> Builder(SI);
+
+  // StN intrinsics don't support pointer vectors as arguments. Convert pointer
+  // vectors to integer vectors.
+  if (EltTy->isPointerTy()) {
+    Type *IntTy = DL->getIntPtrType(EltTy);
+    unsigned NumOpElts =
+        dyn_cast<VectorType>(Op0->getType())->getVectorNumElements();
+
+    // The corresponding integer vector type of the same element size.
+    Type *IntVecTy = VectorType::get(IntTy, NumOpElts);
+
+    Op0 = Builder.CreatePtrToInt(Op0, IntVecTy);
+    Op1 = Builder.CreatePtrToInt(Op1, IntVecTy);
+    SubVecTy = VectorType::get(IntTy, NumSubElts);
+  }
+
+  Type *PtrTy = SubVecTy->getPointerTo(SI->getPointerAddressSpace());
+  Type *Tys[2] = {SubVecTy, PtrTy};
+  Function *StNFunc =
+      Intrinsic::getDeclaration(M, getLdNStNIntrinsic(Factor, false), Tys);
+
+  SmallVector<Value *, 5> Ops;
+
+  // Split the shufflevector operands into sub vectors for the new stN call.
+  for (unsigned i = 0; i < Factor; i++)
+    Ops.push_back(Builder.CreateShuffleVector(
+        Op0, Op1, getSequentialMask(Builder, NumSubElts * i, NumSubElts)));
+
+  Ops.push_back(Builder.CreateBitCast(SI->getPointerOperand(), PtrTy));
+  CallInst *StN = Builder.CreateCall(StNFunc, Ops);
+
+  DEBUG(dbgs() << "  Replaced:" << *SI << "'\n");
+  DEBUG(dbgs() << "      with:" << *StN << "\n");
+
+  // Mark this shufflevector and store as dead.
+  DeadInsts.insert(SI);
+  DeadInsts.insert(SVI);
+  return true;
+}
+
+bool AArch64InterleavedAccess::runOnFunction(Function &F) {
+  DEBUG(dbgs() << "*** " << getPassName() << ": " << F.getName() << "\n");
+
+  M = F.getParent();
+  DL = &M->getDataLayout();
+
+  // Holds dead instructions that will be erased later.
+  SmallSetVector<Instruction *, 32> DeadInsts;
+  bool Changed = false;
+  for (auto &I : inst_range(F)) {
+    if (ShuffleVectorInst *SVI = dyn_cast<ShuffleVectorInst>(&I)) {
+      Changed |= matchInterleavedLoad(SVI, DeadInsts);
+      Changed |= matchInterleavedStore(SVI, DeadInsts);
+    }
+  }
+
+  for (auto I : DeadInsts)
+    I->eraseFromParent();
+
+  return Changed;
+}

lib/Target/AArch64/AArch64TargetMachine.cpp

EnableLoadStoreOpt("aarch64-load-store-opt", cl::desc("Enable the load/store pair"
                    " optimization pass"), cl::init(true), cl::Hidden);
 
 static cl::opt<bool>
 EnableAtomicTidy("aarch64-atomic-cfg-tidy", cl::Hidden,
                  cl::desc("Run SimplifyCFG after expanding atomic operations"
                           " to make use of cmpxchg flow-based information"),
                  cl::init(true));
 
+static cl::opt<bool> AArch64InterleavedAccessOpt(
+    "aarch64-interleaved-access-opt",
+    cl::desc("Optimize interleaved memory accesses in AArch64 backend"),
+    cl::init(false), cl::Hidden);
+
 static cl::opt<bool>
 EnableEarlyIfConversion("aarch64-enable-early-ifcvt", cl::Hidden,
                         cl::desc("Run early if-conversion"),
                         cl::init(true));
 
 static cl::opt<bool>
 EnableCondOpt("aarch64-condopt",
               cl::desc("Enable the condition optimizer pass"),
void AArch64PassConfig::addIRPasses() {
   addPass(createAtomicExpandPass(TM));
 
   // Cmpxchg instructions are often used with a subsequent comparison to
   // determine whether it succeeded. We can exploit existing control-flow in
   // ldrex/strex loops to simplify this, but it needs tidying up.
   if (TM->getOptLevel() != CodeGenOpt::None && EnableAtomicTidy)
     addPass(createCFGSimplificationPass());
 
+  if (TM->getOptLevel() != CodeGenOpt::None && AArch64InterleavedAccessOpt)
+    addPass(createAArch64InterleavedAccessPass());
+
   TargetPassConfig::addIRPasses();
 
   if (TM->getOptLevel() == CodeGenOpt::Aggressive && EnableGEPOpt) {
     // Call SeparateConstOffsetFromGEP pass to extract constants within indices
     // and lower a GEP with multiple indices to either arithmetic operations or
     // multiple GEPs with single index.
     addPass(createSeparateConstOffsetFromGEPPass(TM, true));
     // Call EarlyCSE pass to find and remove subexpressions in the lowered

lib/Target/AArch64/AArch64TargetTransformInfo.h

public:
 
   void getUnrollingPreferences(Loop *L, TTI::UnrollingPreferences &UP);
 
   Value *getOrCreateResultFromMemIntrinsic(IntrinsicInst *Inst,
                                            Type *ExpectedType);
 
   bool getTgtMemIntrinsic(IntrinsicInst *Inst, MemIntrinsicInfo &Info);
 
+  unsigned getInterleavedMemoryOpCost(unsigned Opcode, Type *VecTy,
+                                      unsigned Factor,
+                                      ArrayRef<unsigned> Indices,
+                                      unsigned Alignment,
+                                      unsigned AddressSpace);
   /// @}
 };
 
 } // end namespace llvm
 
 #endif

lib/Target/AArch64/AArch64TargetTransformInfo.cpp

if (Src->isVectorTy() && Src->getVectorElementType()->isIntegerTy(8) &&
     unsigned NumVectorizableInstsToAmortize = NumVecElts * 2;
     // We generate 2 instructions per vector element.
     return NumVectorizableInstsToAmortize * NumVecElts * 2;
   }
 
   return LT.first;
 }
 
+unsigned AArch64TTIImpl::getInterleavedMemoryOpCost(
+    unsigned Opcode, Type *VecTy, unsigned Factor, ArrayRef<unsigned> Indices,
+    unsigned Alignment, unsigned AddressSpace) {
+  assert(isa<VectorType>(VecTy) && "Expect vector types");
+
+  if (Factor > 1 && Factor < 5 && isTypeLegal(VecTy))
+    return Factor;
+
+  return BaseT::getInterleavedMemoryOpCost(Opcode, VecTy, Factor, Indices,
+                                           Alignment, AddressSpace);
+}
+
 unsigned AArch64TTIImpl::getCostOfKeepingLiveOverCall(ArrayRef<Type *> Tys) {
   unsigned Cost = 0;
   for (auto *I : Tys) {
     if (!I->isVectorTy())
       continue;
     if (I->getScalarSizeInBits() * I->getVectorNumElements() == 128)
       Cost += getMemoryOpCost(Instruction::Store, I, 128, 0) +
         getMemoryOpCost(Instruction::Load, I, 128, 0);

lib/Target/AArch64/CMakeLists.txt

add_llvm_target(AArch64CodeGen
   AArch64ISelLowering.cpp
   AArch64InstrInfo.cpp
   AArch64LoadStoreOptimizer.cpp
   AArch64MCInstLower.cpp
   AArch64PromoteConstant.cpp
   AArch64PBQPRegAlloc.cpp
   AArch64RegisterInfo.cpp
   AArch64SelectionDAGInfo.cpp
+  AArch64InterleavedAccess.cpp
   AArch64StorePairSuppress.cpp
   AArch64Subtarget.cpp
   AArch64TargetMachine.cpp
   AArch64TargetObjectFile.cpp
   AArch64TargetTransformInfo.cpp
 )
 
 add_dependencies(LLVMAArch64CodeGen intrinsics_gen)
 
 add_subdirectory(TargetInfo)
 add_subdirectory(AsmParser)
 add_subdirectory(Disassembler)
 add_subdirectory(InstPrinter)
 add_subdirectory(MCTargetDesc)
 add_subdirectory(Utils)

test/CodeGen/AArch64/aarch64-interleaved-accesses.ll

+; RUN: llc -march=aarch64 -aarch64-interleaved-access-opt=true < %s | FileCheck %s
+
+; CHECK-LABEL: load_factor2:
+; CHECK: ld2 { v0.8b, v1.8b }, [x0]
+define <8 x i8> @load_factor2(<16 x i8>* %ptr) {
+  %wide.vec = load <16 x i8>, <16 x i8>* %ptr, align 4
+  %strided.v0 = shufflevector <16 x i8> %wide.vec, <16 x i8> undef, <8 x i32> <i32 0, i32 2, i32 4, i32 6, i32 8, i32 10, i32 12, i32 14>
+  %strided.v1 = shufflevector <16 x i8> %wide.vec, <16 x i8> undef, <8 x i32> <i32 1, i32 3, i32 5, i32 7, i32 9, i32 11, i32 13, i32 15>
+  %add = add nsw <8 x i8> %strided.v0, %strided.v1
+  ret <8 x i8> %add
+}
+
+; CHECK-LABEL: load_delat3:
+; CHECK: ld3 { v0.4s, v1.4s, v2.4s }, [x0]
+define <4 x i32> @load_delat3(i32* %ptr) {
+  %base = bitcast i32* %ptr to <12 x i32>*
+  %wide.vec = load <12 x i32>, <12 x i32>* %base, align 4
+  %strided.v2 = shufflevector <12 x i32> %wide.vec, <12 x i32> undef, <4 x i32> <i32 2, i32 5, i32 8, i32 11>
+  %strided.v1 = shufflevector <12 x i32> %wide.vec, <12 x i32> undef, <4 x i32> <i32 1, i32 4, i32 7, i32 10>
+  %add = add nsw <4 x i32> %strided.v2, %strided.v1
+  ret <4 x i32> %add
+}
+
+; CHECK-LABEL: load_factor4:
+; CHECK: ld4 { v0.4s, v1.4s, v2.4s, v3.4s }, [x0]
+define <4 x i32> @load_factor4(i32* %ptr) {
+  %base = bitcast i32* %ptr to <16 x i32>*
+  %wide.vec = load <16 x i32>, <16 x i32>* %base, align 4
+  %strided.v0 = shufflevector <16 x i32> %wide.vec, <16 x i32> undef, <4 x i32> <i32 0, i32 4, i32 8, i32 12>
+  %strided.v2 = shufflevector <16 x i32> %wide.vec, <16 x i32> undef, <4 x i32> <i32 2, i32 6, i32 10, i32 14>
+  %add = add nsw <4 x i32> %strided.v0, %strided.v2
+  ret <4 x i32> %add
+}
+
+; CHECK-LABEL: store_factor2:
+; CHECK: st2 { v0.8b, v1.8b }, [x0]
+define void @store_factor2(<16 x i8>* %ptr, <8 x i8> %v0, <8 x i8> %v1) {
+  %interleaved.vec = shufflevector <8 x i8> %v0, <8 x i8> %v1, <16 x i32> <i32 0, i32 8, i32 1, i32 9, i32 2, i32 10, i32 3, i32 11, i32 4, i32 12, i32 5, i32 13, i32 6, i32 14, i32 7, i32 15>
+  store <16 x i8> %interleaved.vec, <16 x i8>* %ptr, align 4
+  ret void
+}
+
+; CHECK-LABEL: store_factor3:
+; CHECK: st3 { v0.4s, v1.4s, v2.4s }, [x0]
+define void @store_factor3(i32* %ptr, <4 x i32> %v0, <4 x i32> %v1, <4 x i32> %v2) {
+  %base = bitcast i32* %ptr to <12 x i32>*
+  %v0_v1 = shufflevector <4 x i32> %v0, <4 x i32> %v1, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+  %v2_u = shufflevector <4 x i32> %v2, <4 x i32> undef, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 undef, i32 undef, i32 undef, i32 undef>
+  %interleaved.vec = shufflevector <8 x i32> %v0_v1, <8 x i32> %v2_u, <12 x i32> <i32 0, i32 4, i32 8, i32 1, i32 5, i32 9, i32 2, i32 6, i32 10, i32 3, i32 7, i32 11>
+  store <12 x i32> %interleaved.vec, <12 x i32>* %base, align 4
+  ret void
+}
+
+; CHECK-LABEL: store_factor4:
+; CHECK: st4 { v0.4s, v1.4s, v2.4s, v3.4s }, [x0]
+define void @store_factor4(i32* %ptr, <4 x i32> %v0, <4 x i32> %v1, <4 x i32> %v2, <4 x i32> %v3) {
+  %base = bitcast i32* %ptr to <16 x i32>*
+  %v0_v1 = shufflevector <4 x i32> %v0, <4 x i32> %v1, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+  %v2_v3 = shufflevector <4 x i32> %v2, <4 x i32> %v3, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+  %interleaved.vec = shufflevector <8 x i32> %v0_v1, <8 x i32> %v2_v3, <16 x i32> <i32 0, i32 4, i32 8, i32 12, i32 1, i32 5, i32 9, i32 13, i32 2, i32 6, i32 10, i32 14, i32 3, i32 7, i32 11, i32 15>
+  store <16 x i32> %interleaved.vec, <16 x i32>* %base, align 4
+  ret void
+}
+
+; The following cases test that interleaved access with pointer vectors can be
+; matched to ldN/stN instruction.
+
+; CHECK-LABEL: load_ptrvec_factor2:
+; CHECK: ld2 { v0.2d, v1.2d }, [x0]
+define <2 x i32*> @load_ptrvec_factor2(i32** %ptr) {
+  %base = bitcast i32** %ptr to <4 x i32*>*
+  %wide.vec = load <4 x i32*>, <4 x i32*>* %base, align 4
+  %strided.v0 = shufflevector <4 x i32*> %wide.vec, <4 x i32*> undef, <2 x i32> <i32 0, i32 2>
+  ret <2 x i32*> %strided.v0
+}
+
+; CHECK-LABEL: load_ptrvec_factor3:
+; CHECK: ld3 { v0.2d, v1.2d, v2.2d }, [x0]
+define void @load_ptrvec_factor3(i32** %ptr, <2 x i32*>* %ptr1, <2 x i32*>* %ptr2) {
+  %base = bitcast i32** %ptr to <6 x i32*>*
+  %wide.vec = load <6 x i32*>, <6 x i32*>* %base, align 4
+  %strided.v2 = shufflevector <6 x i32*> %wide.vec, <6 x i32*> undef, <2 x i32> <i32 2, i32 5>
+  store <2 x i32*> %strided.v2, <2 x i32*>* %ptr1
+  %strided.v1 = shufflevector <6 x i32*> %wide.vec, <6 x i32*> undef, <2 x i32> <i32 1, i32 4>
+  store <2 x i32*> %strided.v1, <2 x i32*>* %ptr2
+  ret void
+}
+
+; CHECK-LABEL: load_ptrvec_factor4:
+; CHECK: ld4 { v0.2d, v1.2d, v2.2d, v3.2d }, [x0]
+define void @load_ptrvec_factor4(i32** %ptr, <2 x i32*>* %ptr1, <2 x i32*>* %ptr2) {
+  %base = bitcast i32** %ptr to <8 x i32*>*
+  %wide.vec = load <8 x i32*>, <8 x i32*>* %base, align 4
+  %strided.v1 = shufflevector <8 x i32*> %wide.vec, <8 x i32*> undef, <2 x i32> <i32 1, i32 5>
+  %strided.v3 = shufflevector <8 x i32*> %wide.vec, <8 x i32*> undef, <2 x i32> <i32 3, i32 7>
+  store <2 x i32*> %strided.v1, <2 x i32*>* %ptr1
+  store <2 x i32*> %strided.v3, <2 x i32*>* %ptr2
+  ret void
+}
+
+; CHECK-LABEL: store_ptrvec_factor2:
+; CHECK: st2 { v0.2d, v1.2d }, [x0]
+define void @store_ptrvec_factor2(i32** %ptr, <2 x i32*> %v0, <2 x i32*> %v1) {
+  %base = bitcast i32** %ptr to <4 x i32*>*
+  %interleaved.vec = shufflevector <2 x i32*> %v0, <2 x i32*> %v1, <4 x i32> <i32 0, i32 2, i32 1, i32 3>
+  store <4 x i32*> %interleaved.vec, <4 x i32*>* %base, align 4
+  ret void
+}
+
+; CHECK-LABEL: store_ptrvec_factor3:
+; CHECK: st3 { v0.2d, v1.2d, v2.2d }, [x0]
+define void @store_ptrvec_factor3(i32** %ptr, <2 x i32*> %v0, <2 x i32*> %v1, <2 x i32*> %v2) {
+  %base = bitcast i32** %ptr to <6 x i32*>*
+  %v0_v1 = shufflevector <2 x i32*> %v0, <2 x i32*> %v1, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
+  %v2_u = shufflevector <2 x i32*> %v2, <2 x i32*> undef, <4 x i32> <i32 0, i32 1, i32 undef, i32 undef>
+  %interleaved.vec = shufflevector <4 x i32*> %v0_v1, <4 x i32*> %v2_u, <6 x i32> <i32 0, i32 2, i32 4, i32 1, i32 3, i32 5>
+  store <6 x i32*> %interleaved.vec, <6 x i32*>* %base, align 4
+  ret void
+}
+
+; CHECK-LABEL: store_ptrvec_factor4:
+; CHECK: st4 { v0.2d, v1.2d, v2.2d, v3.2d }, [x0]
+define void @store_ptrvec_factor4(i32* %ptr, <2 x i32*> %v0, <2 x i32*> %v1, <2 x i32*> %v2, <2 x i32*> %v3) {
+  %base = bitcast i32* %ptr to <8 x i32*>*
+  %v0_v1 = shufflevector <2 x i32*> %v0, <2 x i32*> %v1, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
+  %v2_v3 = shufflevector <2 x i32*> %v2, <2 x i32*> %v3, <4 x i32> <i32 0, i32 1, i32 2, i32 3>
+  %interleaved.vec = shufflevector <4 x i32*> %v0_v1, <4 x i32*> %v2_v3, <8 x i32> <i32 0, i32 2, i32 4, i32 6, i32 1, i32 3, i32 5, i32 7>
+  store <8 x i32*> %interleaved.vec, <8 x i32*>* %base, align 4
+  ret void
+}
+
+; Following cases check that shuffle maskes with undef indices can be matched
+; into ldN/stN instruction.
+
+; CHECK-LABEL: load_undef_mask_factor2:
+; CHECK: ld2 { v0.4s, v1.4s }, [x0]
+define <4 x i32> @load_undef_mask_factor2(i32* %ptr) {
+  %base = bitcast i32* %ptr to <8 x i32>*
+  %wide.vec = load <8 x i32>, <8 x i32>* %base, align 4
+  %strided.v0 = shufflevector <8 x i32> %wide.vec, <8 x i32> undef, <4 x i32> <i32 undef, i32 2, i32 undef, i32 6>
+  %strided.v1 = shufflevector <8 x i32> %wide.vec, <8 x i32> undef, <4 x i32> <i32 undef, i32 3, i32 undef, i32 7>
+  %add = add nsw <4 x i32> %strided.v0, %strided.v1
+  ret <4 x i32> %add
+}
+
+; CHECK-LABEL: load_undef_mask_factor3:
+; CHECK: ld3 { v0.4s, v1.4s, v2.4s }, [x0]
+define <4 x i32> @load_undef_mask_factor3(i32* %ptr) {
+  %base = bitcast i32* %ptr to <12 x i32>*
+  %wide.vec = load <12 x i32>, <12 x i32>* %base, align 4
+  %strided.v2 = shufflevector <12 x i32> %wide.vec, <12 x i32> undef, <4 x i32> <i32 2, i32 undef, i32 undef, i32 undef>
+  %strided.v1 = shufflevector <12 x i32> %wide.vec, <12 x i32> undef, <4 x i32> <i32 1, i32 4, i32 7, i32 10>
+  %add = add nsw <4 x i32> %strided.v2, %strided.v1
+  ret <4 x i32> %add
+}
+
+; CHECK-LABEL: load_undef_mask_factor4:
+; CHECK: ld4 { v0.4s, v1.4s, v2.4s, v3.4s }, [x0]
+define <4 x i32> @load_undef_mask_factor4(i32* %ptr) {
+  %base = bitcast i32* %ptr to <16 x i32>*
+  %wide.vec = load <16 x i32>, <16 x i32>* %base, align 4
+  %strided.v0 = shufflevector <16 x i32> %wide.vec, <16 x i32> undef, <4 x i32> <i32 0, i32 4, i32 undef, i32 undef>
+  %strided.v2 = shufflevector <16 x i32> %wide.vec, <16 x i32> undef, <4 x i32> <i32 2, i32 6, i32 undef, i32 undef>
+  %add = add nsw <4 x i32> %strided.v0, %strided.v2
+  ret <4 x i32> %add
+}
+
+; CHECK-LABEL: store_undef_mask_factor2:
+; CHECK: st2 { v0.4s, v1.4s }, [x0]
+define void @store_undef_mask_factor2(i32* %ptr, <4 x i32> %v0, <4 x i32> %v1) {
+  %base = bitcast i32* %ptr to <8 x i32>*
+  %interleaved.vec = shufflevector <4 x i32> %v0, <4 x i32> %v1, <8 x i32> <i32 undef, i32 undef, i32 undef, i32 undef, i32 2, i32 6, i32 3, i32 7>
+  store <8 x i32> %interleaved.vec, <8 x i32>* %base, align 4
+  ret void
+}
+
+; CHECK-LABEL: store_undef_mask_factor3:
+; CHECK: st3 { v0.4s, v1.4s, v2.4s }, [x0]
+define void @store_undef_mask_factor3(i32* %ptr, <4 x i32> %v0, <4 x i32> %v1, <4 x i32> %v2) {
+  %base = bitcast i32* %ptr to <12 x i32>*
+  %v0_v1 = shufflevector <4 x i32> %v0, <4 x i32> %v1, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+  %v2_u = shufflevector <4 x i32> %v2, <4 x i32> undef, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 undef, i32 undef, i32 undef, i32 undef>
+  %interleaved.vec = shufflevector <8 x i32> %v0_v1, <8 x i32> %v2_u, <12 x i32> <i32 0, i32 4, i32 undef, i32 1, i32 undef, i32 9, i32 2, i32 6, i32 10, i32 3, i32 7, i32 11>
+  store <12 x i32> %interleaved.vec, <12 x i32>* %base, align 4
+  ret void
+}
+
+; CHECK-LABEL: store_undef_mask_factor4:
+; CHECK: st4 { v0.4s, v1.4s, v2.4s, v3.4s }, [x0]
+define void @store_undef_mask_factor4(i32* %ptr, <4 x i32> %v0, <4 x i32> %v1, <4 x i32> %v2, <4 x i32> %v3) {
+  %base = bitcast i32* %ptr to <16 x i32>*
+  %v0_v1 = shufflevector <4 x i32> %v0, <4 x i32> %v1, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+  %v2_v3 = shufflevector <4 x i32> %v2, <4 x i32> %v3, <8 x i32> <i32 0, i32 1, i32 2, i32 3, i32 4, i32 5, i32 6, i32 7>
+  %interleaved.vec = shufflevector <8 x i32> %v0_v1, <8 x i32> %v2_v3, <16 x i32> <i32 0, i32 4, i32 8, i32 undef, i32 undef, i32 5, i32 9, i32 13, i32 2, i32 6, i32 10, i32 14, i32 3, i32 7, i32 11, i32 15>
+  store <16 x i32> %interleaved.vec, <16 x i32>* %base, align 4
+  ret void
+}