Re-factorization of X86InterleaveAccess into a class

[Farhana]

Summary

This change-set support re-factorization of X86InterleaveAccess pass into a class without any functional changes in order to allow better code sharing.

[zvi]

lib/Target/X86/X86InterleavedAccess.cpp

69

Not related to this patch, but is setting the original vector load's alignment for all 'decomposed' loads correct?

lib/Target/X86/X86InterleavedAccess.h

18

No need to include in the header. forward declaration is sufficient:
class X86Subtarget;

19

Probably same as above, LLVM convention is to use forward declarations if reasonable.

53

Consider documenting this c-tor's arguments.

66

Does this method need to be public?

77

Does this method need to be public?

[RKSimon]

lib/Target/X86/X86InterleavedAccess.cpp

152

Isn't this a leak? Where is this deleted?

[Farhana]

Thanks Simon and Zvi.

Here is the updated change-set that addresses your comments.

[zvi]

lib/Target/X86/X86InterleavedAccess.cpp

152

It would better to instantiate as a function-local variable. If you do want to allocate on the heap, please use std::unique_ptr or something similar to manage the object.

[Farhana]

The update addresses Zvi's comment about declaring Grp as a functional local variable.

[DavidKreitzer]

lib/Target/X86/X86InterleavedAccess.cpp

27

elements --> element

44

Why are you passing VecInst, NumSubVectors, & SubVecTy as arguments to decompose? These are all easily accessible from the class members.

47

VecSize --> SubVecSize would be clearer

54

This reads funny. Did you mean "into \p NumSubVectors sub vectors of type \p T."?

56

Please describe the return value in the comment. I assume it is supposed to indicate success? It seems odd to me that that would be necessary. I would expect isSupported() == true to imply that the transform is expected to succeed. Should this just return void instead?

65

It would be slightly clearer if you used the variable names here, i.e.

Input-Vectors --> InputVectors
OutputVectors --> TransposedVectors

69

Is this method really supposed to be restricted to 4x4 transpose? If so, your example should be a 4x4 transpose, not a 2x2 one. (Did you mean for the comment at the method definition to be here?)

Trasposed --> Transposed

96

Don't duplicate the comments from the class definition unless they contain additional value (e.g. notes about the low level implementation).

[Farhana]

Thanks Dave, the update addresses your comment.

lib/Target/X86/X86InterleavedAccess.cpp

44

So the intent is to use this function in a general way and use it to break down any kind of instruction. Currently, it is used for load instruction, but it will also be used to break down the long shuffle instruction in the strided-store pattern.

56

So the intent is to use it for breaking down any kind of instruction such as load, shuffle. Currently, load is only supported. Also there might be some other challenges where we were not able to create the dummy vectors and break-down the instruction evenly.

69

Yes.

[RKSimon]

Please can you replace the uses of uint32_t with unsigned?

[Farhana]

In D25986#590381, @RKSimon wrote:

Please can you replace the uses of uint32_t with unsigned?

Hi Simon,

I would think uint32_t would be preferred over unsigned because unsigned could lead to an incorrect result. Though I agree it will be safe to use unsigned here.

But in general is there a reason for wanting the size to change with the underlying architecture?

[Farhana]

Replaces uint32_t with unsigned.

[delena]

lib/Target/X86/X86InterleavedAccess.cpp

34

const LoadInst* Inst;

50

Do you need to keep Builder inside? I assume it may be a local var inside function.

81

const Instruction *I

151

Why do you need to pass an empty builder here?

155

return Grp.isSupported() && Grp.lowerIntoOptimizedSequence();

[Farhana]

This change-set addresses Elena's comments.

lib/Target/X86/X86InterleavedAccess.cpp

34

Inst cannot be a constant pointer because we are bit-casting its pointer operand. Inst can be a both load/store, that's why I declared it as an Instruction instead of LoadInst.

50

Yes, because Builder is used in different member functions and the different member functions might not have any idea about the insertion point. Having it as a member variable helps updating the insertion point automatically after each new instruction creation.

81

I think it's covered by my previous comment.

151

We are using this builder with insertionpoint set to load instruction in multiple member functions where the member functions have no idea about the central insertion point. Therefore, we need to have it as a member variable set to the central insertion point for the other member functions.

[delena]

lib/Target/X86/X86InterleavedAccess.cpp

34

so "Instruction* Inst" is enough. The "const" is redundant here.

55

It is always "load" or you are thinking about any general case? You can call the function decomposeLoad.

69

Zvi is right. And fix indentation, please.

[Farhana]

lib/Target/X86/X86InterleavedAccess.cpp

55

Yes, that's the plan to use it in a general way, for decomposing any kind of instructions such as load, store, shuffle.

69

Sorry Zvi, I missed this comment earlier. Yes, that's correct.

69

"And fix indentation, please"

Instruction *NewLoad =
      Builder.CreateAlignedLoad(NewBasePtr, LI->getAlignment());

Are you talking about this? Indentation is not off here. I reran clang-format, everything remained as it is.

[RKSimon]

In D25986#590787, @Farhana wrote:

In D25986#590381, @RKSimon wrote:

Please can you replace the uses of uint32_t with unsigned?

I would think uint32_t would be preferred over unsigned because unsigned could lead to an incorrect result. Though I agree it will be safe to use unsigned here.

But in general is there a reason for wanting the size to change with the underlying architecture?

In general we should match whatever the original return values was - Type::getVectorNumElements() returns unsigned so the NumSubVectors should probably match that.

I'm sorry but I messed up on the types of a couple of the other instances - CreateShuffleVector should take an ArrayRef<uint32_t> and DataLayout::getTypeSizeInBits returns a uint64_t

lib/Target/X86/X86InterleavedAccess.cpp

132

for (unsigned i = 0, e = Shuffles.size(); i != e ; ++i)

[Farhana]

Hi Guys,

Is there anything else you want me to fix/clarify?

Farhana

[zvi]

LGTM. Thanks, Farhana!

X86InterleavedAccess.cpp

71 ↗

(On Diff #77650)

Minor comment: AFAIU you can pass an ArrayRef object by value efficiently, but i did see several occurrences in LLVM's source code with ArrayRef's passed by reference. Whatever you choose, maybe make this entire file consistent (line 82, for example is inconsistent with line 71).
I see that the overriden methods such as TargetLowering::lowerInterleavedLoad pass ArrayRef objects by value, so maybe this would be a tie-breaker for following this convention?

[Farhana]

ArrayRefs are passed by value.

[zvi]

Thanks, Farhana! LGTM.

[RKSimon]

LGTM

[DavidKreitzer]

Hi Farhana,
I have no further comments. This LGTM too.
-Dave

lib/Target/X86/X86InterleavedAccess.h

+//===---- X86InterleavedAccess.h - Define X86InterleavedAccessGroup class-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===---------------------------------------------------------------------===//
+//
+// This file declares the X86InterleavedAccessGroup that represents/manipulates
+// a set of interleaved accesses.
+//
+//===---------------------------------------------------------------------===//
+
+#ifndef LLVM_LIB_TARGET_X86_X86INTERLEAVEDACCESS_H
+#define LLVM_LIB_TARGET_X86_X86INTERLEAVEDACCESS_H
+
+#include "X86Subtarget.h"
+#include "llvm/IR/Instructions.h"
+
+using namespace llvm;
+
+/// This class holds necessary information to represent an interleaved
+/// access group and supports utilities to lower the group into
+/// X86-specific instructions/intrinsics.
+//  E.g. A group of interleaving access loads (Factor = 2; accessing every
+// other elements)
+//        %wide.vec = load <8 x i32>, <8 x i32>* %ptr
+//        %v0 = shuffle <8 x i32> %wide.vec, <8 x i32> undef, <0, 2, 4, 6>
+//        %v1 = shuffle <8 x i32> %wide.vec, <8 x i32> undef, <1, 3, 5, 7>
+
+class X86InterleavedAccessGroup {
+  /// Reference to the wide-load instruction of an interleaved access
+  /// group.
+  Instruction *const Inst;
+
+  /// Reference to the shuffle(s), consumer(s) of the (load) 'Inst'.
+  const ArrayRef<ShuffleVectorInst *> Shuffles;
+
+  /// Reference to the starting index of each user-shuffle.
+  const ArrayRef<unsigned> Indices;
+
+  /// Reference to the interleaving stride in terms of elements.
+  const unsigned Factor;
+
+  const X86Subtarget &Subtarget;
+
+  const DataLayout &DL;
+
+  IRBuilder<> &Builder;
+
+public:
+  X86InterleavedAccessGroup(Instruction *I,
+                            const ArrayRef<ShuffleVectorInst *> Shuffs,
+                            const ArrayRef<unsigned> Ind, const unsigned F,
+                            const X86Subtarget &STarget, IRBuilder<> &B)
+      : Inst(I), Shuffles(Shuffs), Indices(Ind), Factor(F), Subtarget(STarget),
+        DL(Inst->getModule()->getDataLayout()), Builder(B) {}
+
+  /// Returns true if this interleaved access group can be lowered into
+  /// x86-specific instructions/intrinsics, false otherwise.
+  bool isSupported() const;
+
+  /// Breaks down a vector 'Inst' of N elements into NumSubVectors sub vectors
+  /// of sub-vector of type T.
+  bool decompose(Instruction *Inst, uint32_t NumSubVectors, VectorType *T,
+                 SmallVectorImpl<Instruction *> &DecomposedVectors);
+
+  /// Performs matrix transposition and returns the transposed-vectors.
+  /// E.g.
+  /// Input-Vectors:
+  ///   In-V0 = p1, p2
+  ///   In-V1 = q1, q2
+  /// Output-Vectors:
+  ///   Out-V0 = p1, q1
+  ///   Out-V1 = p2, q2
+  void transpose(const ArrayRef<Instruction *> &InputVectors,
+                 SmallVectorImpl<Value *> &TrasposedVectors);
+
+  /// Lowers this interleaved access group into X86-specific
+  /// instructions/intrinsics.
+  bool lowerIntoOptimizedSequence();
+};
+
+#endif

lib/Target/X86/X86InterleavedAccess.cpp

 //===------- X86InterleavedAccess.cpp --------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file contains the X86 implementation of the interleaved accesses
 // optimization generating X86-specific instructions/intrinsics for interleaved
 // access groups.
 //
 //===----------------------------------------------------------------------===//
 
+#include "X86InterleavedAccess.h"
 #include "X86ISelLowering.h"
 #include "X86TargetMachine.h"
+#include "llvm/IR/IRBuilder.h"
 
 using namespace llvm;
 
-/// Returns true if the interleaved access group represented by the shuffles
-/// is supported for the subtarget. Returns false otherwise.
-static bool isSupported(const X86Subtarget &SubTarget,
-                        const LoadInst *LI,
-                        const ArrayRef<ShuffleVectorInst *> &Shuffles,
-                        unsigned Factor) {
-
-  const DataLayout &DL = Shuffles[0]->getModule()->getDataLayout();
+/// Returns true if this interleaved access group is supported for the
+/// subtarget. Returns false otherwise.
+bool X86InterleavedAccessGroup::isSupported() const {
   VectorType *ShuffleVecTy = Shuffles[0]->getType();
   unsigned ShuffleVecSize = DL.getTypeSizeInBits(ShuffleVecTy);
   Type *ShuffleEltTy = ShuffleVecTy->getVectorElementType();
 
-  if (DL.getTypeSizeInBits(LI->getType()) < Factor * ShuffleVecSize)
+  if (DL.getTypeSizeInBits(Inst->getType()) < Factor * ShuffleVecSize)
     return false;
 
   // Currently, lowering is supported for 64 bits on AVX.
-  if (!SubTarget.hasAVX() || ShuffleVecSize != 256 ||
-      DL.getTypeSizeInBits(ShuffleEltTy) != 64 ||
-      Factor != 4)
+  if (!Subtarget.hasAVX() || ShuffleVecSize != 256 ||
+      DL.getTypeSizeInBits(ShuffleEltTy) != 64 || Factor != 4)
     return false;
 
   return true;
 }
 
-/// \brief Lower interleaved load(s) into target specific instructions/
-/// intrinsics. Lowering sequence varies depending on the vector-types, factor,
-/// number of shuffles and ISA.
-/// Currently, lowering is supported for 4x64 bits with Factor = 4 on AVX.
-bool X86TargetLowering::lowerInterleavedLoad(
-    LoadInst *LI, ArrayRef<ShuffleVectorInst *> Shuffles,
-    ArrayRef<unsigned> Indices, unsigned Factor) const {
-  assert(Factor >= 2 && Factor <= getMaxSupportedInterleaveFactor() &&
-         "Invalid interleave factor");
-  assert(!Shuffles.empty() && "Empty shufflevector input");
-  assert(Shuffles.size() == Indices.size() &&
-         "Unmatched number of shufflevectors and indices");
+/// Breaks down a vector 'VecInst' of N elements into NumSubVectors sub vectors;
+/// where each sub-vector of type VecTy.
+bool X86InterleavedAccessGroup::decompose(
+    Instruction *VecInst, uint32_t NumSubVectors, VectorType *SubVecTy,
+    SmallVectorImpl<Instruction *> &DecomposedVectors) {
+  Type *VecTy = VecInst->getType();
+  uint32_t VecSize = DL.getTypeSizeInBits(SubVecTy);
+
+  assert(VecTy->isVectorTy() &&
+         DL.getTypeSizeInBits(VecTy) >= VecSize * NumSubVectors &&
+         "Invalid Inst-size!!!");
+  assert(VecTy->getVectorElementType() == SubVecTy->getVectorElementType() &&
+         "Element type mismatched!!!");
 
-  if (!isSupported(Subtarget, LI, Shuffles, Factor))
+  if (!isa<LoadInst>(VecInst))
     return false;
 
-  VectorType *ShuffleVecTy = Shuffles[0]->getType();
-
-  Type *VecBasePtrTy = ShuffleVecTy->getPointerTo(LI->getPointerAddressSpace());
-
-  IRBuilder<> Builder(LI);
-  SmallVector<Instruction *, 4> NewLoads;
-  SmallVector<Value *, 4> NewShuffles;
-  NewShuffles.resize(Factor);
+  LoadInst *LI = cast<LoadInst>(VecInst);
+  Type *VecBasePtrTy = SubVecTy->getPointerTo(LI->getPointerAddressSpace());
 
   Value *VecBasePtr =
       Builder.CreateBitCast(LI->getPointerOperand(), VecBasePtrTy);
 
-  // Generate 4 loads of type v4xT64
-  for (unsigned Part = 0; Part < Factor; Part++) {
+  // Generate N loads of T type
+  for (uint32_t i = 0; i < NumSubVectors; i++) {
     // TODO: Support inbounds GEP
-    Value *NewBasePtr =
-        Builder.CreateGEP(VecBasePtr, Builder.getInt32(Part));
+    Value *NewBasePtr = Builder.CreateGEP(VecBasePtr, Builder.getInt32(i));
     Instruction *NewLoad =
         Builder.CreateAlignedLoad(NewBasePtr, LI->getAlignment());
-    NewLoads.push_back(NewLoad);
+    DecomposedVectors.push_back(NewLoad);
   }
 
+  return true;
+}
+
+/// Performs matrix transposition and returns the transposed-vectors.
+/// E.g.
+/// Input-Vectors:
+///   In-V0 = p1, p2
+///   In-V1 = q1, q2
+/// Output-Vectors:
+///   Out-V0 = p1, q1
+///   Out-V1 = p2, q2
+
+void X86InterleavedAccessGroup::transpose(
+    const ArrayRef<Instruction *> &Matrix,
+    SmallVectorImpl<Value *> &TransposedMatrix) {
+  TransposedMatrix.resize(4);
   // dst = src1[0,1],src2[0,1]
   uint32_t IntMask1[] = {0, 1, 4, 5};
-  ArrayRef<unsigned int> ShuffleMask = makeArrayRef(IntMask1, 4);
-  Value *IntrVec1 =
-      Builder.CreateShuffleVector(NewLoads[0], NewLoads[2], ShuffleMask);
-  Value *IntrVec2 =
-      Builder.CreateShuffleVector(NewLoads[1], NewLoads[3], ShuffleMask);
+  ArrayRef<unsigned int> Mask = makeArrayRef(IntMask1, 4);
+  Value *IntrVec1 = Builder.CreateShuffleVector(Matrix[0], Matrix[2], Mask);
+  Value *IntrVec2 = Builder.CreateShuffleVector(Matrix[1], Matrix[3], Mask);
 
   // dst = src1[2,3],src2[2,3]
   uint32_t IntMask2[] = {2, 3, 6, 7};
-  ShuffleMask = makeArrayRef(IntMask2, 4);
-  Value *IntrVec3 =
-      Builder.CreateShuffleVector(NewLoads[0], NewLoads[2], ShuffleMask);
-  Value *IntrVec4 =
-      Builder.CreateShuffleVector(NewLoads[1], NewLoads[3], ShuffleMask);
+  Mask = makeArrayRef(IntMask2, 4);
+  Value *IntrVec3 = Builder.CreateShuffleVector(Matrix[0], Matrix[2], Mask);
+  Value *IntrVec4 = Builder.CreateShuffleVector(Matrix[1], Matrix[3], Mask);
 
   // dst = src1[0],src2[0],src1[2],src2[2]
   uint32_t IntMask3[] = {0, 4, 2, 6};
-  ShuffleMask = makeArrayRef(IntMask3, 4);
-  NewShuffles[0] = Builder.CreateShuffleVector(IntrVec1, IntrVec2, ShuffleMask);
-  NewShuffles[2] = Builder.CreateShuffleVector(IntrVec3, IntrVec4, ShuffleMask);
+  Mask = makeArrayRef(IntMask3, 4);
+  TransposedMatrix[0] = Builder.CreateShuffleVector(IntrVec1, IntrVec2, Mask);
+  TransposedMatrix[2] = Builder.CreateShuffleVector(IntrVec3, IntrVec4, Mask);
 
   // dst = src1[1],src2[1],src1[3],src2[3]
   uint32_t IntMask4[] = {1, 5, 3, 7};
-  ShuffleMask = makeArrayRef(IntMask4, 4);
-  NewShuffles[1] = Builder.CreateShuffleVector(IntrVec1, IntrVec2, ShuffleMask);
-  NewShuffles[3] = Builder.CreateShuffleVector(IntrVec3, IntrVec4, ShuffleMask);
-
-  for (unsigned i = 0; i < Shuffles.size(); i++) {
-    unsigned Index = Indices[i];
-    Shuffles[i]->replaceAllUsesWith(NewShuffles[Index]);
-  }
+  Mask = makeArrayRef(IntMask4, 4);
+  TransposedMatrix[1] = Builder.CreateShuffleVector(IntrVec1, IntrVec2, Mask);
+  TransposedMatrix[3] = Builder.CreateShuffleVector(IntrVec3, IntrVec4, Mask);
 
+/// Lowers this interleaved access group into X86-specific
+/// instructions/intrinsics.
+bool X86InterleavedAccessGroup::lowerIntoOptimizedSequence() {
+  SmallVector<Instruction *, 4> DecomposedVectors;
+  VectorType *VecTy = Shuffles[0]->getType();
+  // Try to generate target-sized register(/instruction).
+  if (!decompose(Inst, Factor, VecTy, DecomposedVectors))
+    return false;
+
+  SmallVector<Value *, 4> TransposedVectors;
+  // Perform matrix-transposition in order to compute interleaved
+  // results by generating some sort of (optimized) target-specific
+  // instructions.
+  transpose(DecomposedVectors, TransposedVectors);
+
+  // Now replace the unoptimized-interleaved-vectors with the
+  // transposed-interleaved vectors.
+  for (unsigned i = 0; i < Shuffles.size(); i++)
+    Shuffles[i]->replaceAllUsesWith(TransposedVectors[Indices[i]]);
+
   return true;
 }
+
+/// \brief Lower interleaved load(s) into target specific instructions/
+/// intrinsics. Lowering sequence varies depending on the vector-types, factor,
+/// number of shuffles and ISA.
+/// Currently, lowering is supported for 4x64 bits with Factor = 4 on AVX.
+bool X86TargetLowering::lowerInterleavedLoad(
+    LoadInst *LI, ArrayRef<ShuffleVectorInst *> Shuffles,
+    ArrayRef<unsigned> Indices, unsigned Factor) const {
+  assert(Factor >= 2 && Factor <= getMaxSupportedInterleaveFactor() &&
+         "Invalid interleave factor");
+  assert(!Shuffles.empty() && "Empty shufflevector input");
+  assert(Shuffles.size() == Indices.size() &&
+         "Unmatched number of shufflevectors and indices");
+
+  // Create an interleaved access group.
+  IRBuilder<> Builder(LI);
+  X86InterleavedAccessGroup *Grp = new X86InterleavedAccessGroup(
+      LI, Shuffles, Indices, Factor, Subtarget, Builder);
+
+  if (!Grp->isSupported())
+    return false;
+
+  if (Grp->lowerIntoOptimizedSequence())
+    return true;
+
+  return false;
+}