contrib/llvm/lib/Target/X86/X86InterleavedAccess.cpp

   1 //===--------- X86InterleavedAccess.cpp ----------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===--------------------------------------------------------------------===//
   9 ///
  10 /// \file
  11 /// This file contains the X86 implementation of the interleaved accesses
  12 /// optimization generating X86-specific instructions/intrinsics for
  13 /// interleaved access groups.
  14 ///
  15 //===--------------------------------------------------------------------===//
  16
  17 #include "X86ISelLowering.h"
  18 #include "X86TargetMachine.h"
  19
  20 using namespace llvm;
  21
  22 /// \brief This class holds necessary information to represent an interleaved
  23 /// access group and supports utilities to lower the group into
  24 /// X86-specific instructions/intrinsics.
  25 ///  E.g. A group of interleaving access loads (Factor = 2; accessing every
  26 ///       other element)
  27 ///        %wide.vec = load <8 x i32>, <8 x i32>* %ptr
  28 ///        %v0 = shuffle <8 x i32> %wide.vec, <8 x i32> undef, <0, 2, 4, 6>
  29 ///        %v1 = shuffle <8 x i32> %wide.vec, <8 x i32> undef, <1, 3, 5, 7>
  30
  31 class X86InterleavedAccessGroup {
  32   /// \brief Reference to the wide-load instruction of an interleaved access
  33   /// group.
  34   Instruction *const Inst;
  35
  36   /// \brief Reference to the shuffle(s), consumer(s) of the (load) 'Inst'.
  37   ArrayRef<ShuffleVectorInst *> Shuffles;
  38
  39   /// \brief Reference to the starting index of each user-shuffle.
  40   ArrayRef<unsigned> Indices;
  41
  42   /// \brief Reference to the interleaving stride in terms of elements.
  43   const unsigned Factor;
  44
  45   /// \brief Reference to the underlying target.
  46   const X86Subtarget &Subtarget;
  47
  48   const DataLayout &DL;
  49
  50   IRBuilder<> &Builder;
  51
  52   /// \brief Breaks down a vector \p 'Inst' of N elements into \p NumSubVectors
  53   /// sub vectors of type \p T. Returns true and the sub-vectors in
  54   /// \p DecomposedVectors if it decomposes the Inst, returns false otherwise.
  55   bool decompose(Instruction *Inst, unsigned NumSubVectors, VectorType *T,
  56                  SmallVectorImpl<Instruction *> &DecomposedVectors);
  57
  58   /// \brief Performs matrix transposition on a 4x4 matrix \p InputVectors and
  59   /// returns the transposed-vectors in \p TransposedVectors.
  60   /// E.g.
  61   /// InputVectors:
  62   ///   In-V0 = p1, p2, p3, p4
  63   ///   In-V1 = q1, q2, q3, q4
  64   ///   In-V2 = r1, r2, r3, r4
  65   ///   In-V3 = s1, s2, s3, s4
  66   /// OutputVectors:
  67   ///   Out-V0 = p1, q1, r1, s1
  68   ///   Out-V1 = p2, q2, r2, s2
  69   ///   Out-V2 = p3, q3, r3, s3
  70   ///   Out-V3 = P4, q4, r4, s4
  71   void transpose_4x4(ArrayRef<Instruction *> InputVectors,
  72                      SmallVectorImpl<Value *> &TrasposedVectors);
  73
  74 public:
  75   /// In order to form an interleaved access group X86InterleavedAccessGroup
  76   /// requires a wide-load instruction \p 'I', a group of interleaved-vectors
  77   /// \p Shuffs, reference to the first indices of each interleaved-vector
  78   /// \p 'Ind' and the interleaving stride factor \p F. In order to generate
  79   /// X86-specific instructions/intrinsics it also requires the underlying
  80   /// target information \p STarget.
  81   explicit X86InterleavedAccessGroup(Instruction *I,
  82                                      ArrayRef<ShuffleVectorInst *> Shuffs,
  83                                      ArrayRef<unsigned> Ind,
  84                                      const unsigned F,
  85                                      const X86Subtarget &STarget,
  86                                      IRBuilder<> &B)
  87       : Inst(I), Shuffles(Shuffs), Indices(Ind), Factor(F), Subtarget(STarget),
  88         DL(Inst->getModule()->getDataLayout()), Builder(B) {}
  89
  90   /// \brief Returns true if this interleaved access group can be lowered into
  91   /// x86-specific instructions/intrinsics, false otherwise.
  92   bool isSupported() const;
  93
  94   /// \brief Lowers this interleaved access group into X86-specific
  95   /// instructions/intrinsics.
  96   bool lowerIntoOptimizedSequence();
  97 };
  98
  99 bool X86InterleavedAccessGroup::isSupported() const {
 100   VectorType *ShuffleVecTy = Shuffles[0]->getType();
 101   uint64_t ShuffleVecSize = DL.getTypeSizeInBits(ShuffleVecTy);
 102   Type *ShuffleEltTy = ShuffleVecTy->getVectorElementType();
 103
 104   if (DL.getTypeSizeInBits(Inst->getType()) < Factor * ShuffleVecSize)
 105     return false;
 106
 107   // Currently, lowering is supported for 64 bits on AVX.
 108   if (!Subtarget.hasAVX() || ShuffleVecSize != 256 ||
 109       DL.getTypeSizeInBits(ShuffleEltTy) != 64 || Factor != 4)
 110     return false;
 111
 112   return true;
 113 }
 114
 115 bool X86InterleavedAccessGroup::decompose(
 116     Instruction *VecInst, unsigned NumSubVectors, VectorType *SubVecTy,
 117     SmallVectorImpl<Instruction *> &DecomposedVectors) {
 118   Type *VecTy = VecInst->getType();
 119   (void)VecTy;
 120   assert(VecTy->isVectorTy() &&
 121          DL.getTypeSizeInBits(VecTy) >=
 122              DL.getTypeSizeInBits(SubVecTy) * NumSubVectors &&
 123          "Invalid Inst-size!!!");
 124   assert(VecTy->getVectorElementType() == SubVecTy->getVectorElementType() &&
 125          "Element type mismatched!!!");
 126
 127   if (!isa<LoadInst>(VecInst))
 128     return false;
 129
 130   LoadInst *LI = cast<LoadInst>(VecInst);
 131   Type *VecBasePtrTy = SubVecTy->getPointerTo(LI->getPointerAddressSpace());
 132
 133   Value *VecBasePtr =
 134       Builder.CreateBitCast(LI->getPointerOperand(), VecBasePtrTy);
 135
 136   // Generate N loads of T type
 137   for (unsigned i = 0; i < NumSubVectors; i++) {
 138     // TODO: Support inbounds GEP
 139     Value *NewBasePtr = Builder.CreateGEP(VecBasePtr, Builder.getInt32(i));
 140     Instruction *NewLoad =
 141         Builder.CreateAlignedLoad(NewBasePtr, LI->getAlignment());
 142     DecomposedVectors.push_back(NewLoad);
 143   }
 144
 145   return true;
 146 }
 147
 148 void X86InterleavedAccessGroup::transpose_4x4(
 149     ArrayRef<Instruction *> Matrix,
 150     SmallVectorImpl<Value *> &TransposedMatrix) {
 151   assert(Matrix.size() == 4 && "Invalid matrix size");
 152   TransposedMatrix.resize(4);
 153
 154   // dst = src1[0,1],src2[0,1]
 155   uint32_t IntMask1[] = {0, 1, 4, 5};
 156   ArrayRef<uint32_t> Mask = makeArrayRef(IntMask1, 4);
 157   Value *IntrVec1 = Builder.CreateShuffleVector(Matrix[0], Matrix[2], Mask);
 158   Value *IntrVec2 = Builder.CreateShuffleVector(Matrix[1], Matrix[3], Mask);
 159
 160   // dst = src1[2,3],src2[2,3]
 161   uint32_t IntMask2[] = {2, 3, 6, 7};
 162   Mask = makeArrayRef(IntMask2, 4);
 163   Value *IntrVec3 = Builder.CreateShuffleVector(Matrix[0], Matrix[2], Mask);
 164   Value *IntrVec4 = Builder.CreateShuffleVector(Matrix[1], Matrix[3], Mask);
 165
 166   // dst = src1[0],src2[0],src1[2],src2[2]
 167   uint32_t IntMask3[] = {0, 4, 2, 6};
 168   Mask = makeArrayRef(IntMask3, 4);
 169   TransposedMatrix[0] = Builder.CreateShuffleVector(IntrVec1, IntrVec2, Mask);
 170   TransposedMatrix[2] = Builder.CreateShuffleVector(IntrVec3, IntrVec4, Mask);
 171
 172   // dst = src1[1],src2[1],src1[3],src2[3]
 173   uint32_t IntMask4[] = {1, 5, 3, 7};
 174   Mask = makeArrayRef(IntMask4, 4);
 175   TransposedMatrix[1] = Builder.CreateShuffleVector(IntrVec1, IntrVec2, Mask);
 176   TransposedMatrix[3] = Builder.CreateShuffleVector(IntrVec3, IntrVec4, Mask);
 177 }
 178
 179 // Lowers this interleaved access group into X86-specific
 180 // instructions/intrinsics.
 181 bool X86InterleavedAccessGroup::lowerIntoOptimizedSequence() {
 182   SmallVector<Instruction *, 4> DecomposedVectors;
 183   VectorType *VecTy = Shuffles[0]->getType();
 184   // Try to generate target-sized register(/instruction).
 185   if (!decompose(Inst, Factor, VecTy, DecomposedVectors))
 186     return false;
 187
 188   SmallVector<Value *, 4> TransposedVectors;
 189   // Perform matrix-transposition in order to compute interleaved
 190   // results by generating some sort of (optimized) target-specific
 191   // instructions.
 192   transpose_4x4(DecomposedVectors, TransposedVectors);
 193
 194   // Now replace the unoptimized-interleaved-vectors with the
 195   // transposed-interleaved vectors.
 196   for (unsigned i = 0; i < Shuffles.size(); i++)
 197     Shuffles[i]->replaceAllUsesWith(TransposedVectors[Indices[i]]);
 198
 199   return true;
 200 }
 201
 202 // Lower interleaved load(s) into target specific instructions/
 203 // intrinsics. Lowering sequence varies depending on the vector-types, factor,
 204 // number of shuffles and ISA.
 205 // Currently, lowering is supported for 4x64 bits with Factor = 4 on AVX.
 206 bool X86TargetLowering::lowerInterleavedLoad(
 207     LoadInst *LI, ArrayRef<ShuffleVectorInst *> Shuffles,
 208     ArrayRef<unsigned> Indices, unsigned Factor) const {
 209   assert(Factor >= 2 && Factor <= getMaxSupportedInterleaveFactor() &&
 210          "Invalid interleave factor");
 211   assert(!Shuffles.empty() && "Empty shufflevector input");
 212   assert(Shuffles.size() == Indices.size() &&
 213          "Unmatched number of shufflevectors and indices");
 214
 215   // Create an interleaved access group.
 216   IRBuilder<> Builder(LI);
 217   X86InterleavedAccessGroup Grp(LI, Shuffles, Indices, Factor, Subtarget,
 218                                 Builder);
 219
 220   return Grp.isSupported() && Grp.lowerIntoOptimizedSequence();
 221 }