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 "X86Subtarget.h"
  19 #include "llvm/ADT/ArrayRef.h"
  20 #include "llvm/ADT/SmallVector.h"
  21 #include "llvm/Analysis/VectorUtils.h"
  22 #include "llvm/CodeGen/MachineValueType.h"
  23 #include "llvm/IR/Constants.h"
  24 #include "llvm/IR/DataLayout.h"
  25 #include "llvm/IR/DerivedTypes.h"
  26 #include "llvm/IR/IRBuilder.h"
  27 #include "llvm/IR/Instruction.h"
  28 #include "llvm/IR/Instructions.h"
  29 #include "llvm/IR/Module.h"
  30 #include "llvm/IR/Type.h"
  31 #include "llvm/IR/Value.h"
  32 #include "llvm/Support/Casting.h"
  33 #include <algorithm>
  34 #include <cassert>
  35 #include <cmath>
  36 #include <cstdint>
  37
  38 using namespace llvm;
  39
  40 namespace {
  41
  42 /// \brief This class holds necessary information to represent an interleaved
  43 /// access group and supports utilities to lower the group into
  44 /// X86-specific instructions/intrinsics.
  45 ///  E.g. A group of interleaving access loads (Factor = 2; accessing every
  46 ///       other element)
  47 ///        %wide.vec = load <8 x i32>, <8 x i32>* %ptr
  48 ///        %v0 = shuffle <8 x i32> %wide.vec, <8 x i32> undef, <0, 2, 4, 6>
  49 ///        %v1 = shuffle <8 x i32> %wide.vec, <8 x i32> undef, <1, 3, 5, 7>
  50 class X86InterleavedAccessGroup {
  51   /// \brief Reference to the wide-load instruction of an interleaved access
  52   /// group.
  53   Instruction *const Inst;
  54
  55   /// \brief Reference to the shuffle(s), consumer(s) of the (load) 'Inst'.
  56   ArrayRef<ShuffleVectorInst *> Shuffles;
  57
  58   /// \brief Reference to the starting index of each user-shuffle.
  59   ArrayRef<unsigned> Indices;
  60
  61   /// \brief Reference to the interleaving stride in terms of elements.
  62   const unsigned Factor;
  63
  64   /// \brief Reference to the underlying target.
  65   const X86Subtarget &Subtarget;
  66
  67   const DataLayout &DL;
  68
  69   IRBuilder<> &Builder;
  70
  71   /// \brief Breaks down a vector \p 'Inst' of N elements into \p NumSubVectors
  72   /// sub vectors of type \p T. Returns the sub-vectors in \p DecomposedVectors.
  73   void decompose(Instruction *Inst, unsigned NumSubVectors, VectorType *T,
  74                  SmallVectorImpl<Instruction *> &DecomposedVectors);
  75
  76   /// \brief Performs matrix transposition on a 4x4 matrix \p InputVectors and
  77   /// returns the transposed-vectors in \p TransposedVectors.
  78   /// E.g.
  79   /// InputVectors:
  80   ///   In-V0 = p1, p2, p3, p4
  81   ///   In-V1 = q1, q2, q3, q4
  82   ///   In-V2 = r1, r2, r3, r4
  83   ///   In-V3 = s1, s2, s3, s4
  84   /// OutputVectors:
  85   ///   Out-V0 = p1, q1, r1, s1
  86   ///   Out-V1 = p2, q2, r2, s2
  87   ///   Out-V2 = p3, q3, r3, s3
  88   ///   Out-V3 = P4, q4, r4, s4
  89   void transpose_4x4(ArrayRef<Instruction *> InputVectors,
  90                      SmallVectorImpl<Value *> &TransposedMatrix);
  91   void interleave8bitStride4(ArrayRef<Instruction *> InputVectors,
  92                              SmallVectorImpl<Value *> &TransposedMatrix,
  93                              unsigned NumSubVecElems);
  94   void interleave8bitStride4VF8(ArrayRef<Instruction *> InputVectors,
  95                                 SmallVectorImpl<Value *> &TransposedMatrix);
  96   void interleave8bitStride3(ArrayRef<Instruction *> InputVectors,
  97                              SmallVectorImpl<Value *> &TransposedMatrix,
  98                              unsigned NumSubVecElems);
  99   void deinterleave8bitStride3(ArrayRef<Instruction *> InputVectors,
 100                                SmallVectorImpl<Value *> &TransposedMatrix,
 101                                unsigned NumSubVecElems);
 102
 103 public:
 104   /// In order to form an interleaved access group X86InterleavedAccessGroup
 105   /// requires a wide-load instruction \p 'I', a group of interleaved-vectors
 106   /// \p Shuffs, reference to the first indices of each interleaved-vector
 107   /// \p 'Ind' and the interleaving stride factor \p F. In order to generate
 108   /// X86-specific instructions/intrinsics it also requires the underlying
 109   /// target information \p STarget.
 110   explicit X86InterleavedAccessGroup(Instruction *I,
 111                                      ArrayRef<ShuffleVectorInst *> Shuffs,
 112                                      ArrayRef<unsigned> Ind, const unsigned F,
 113                                      const X86Subtarget &STarget,
 114                                      IRBuilder<> &B)
 115       : Inst(I), Shuffles(Shuffs), Indices(Ind), Factor(F), Subtarget(STarget),
 116         DL(Inst->getModule()->getDataLayout()), Builder(B) {}
 117
 118   /// \brief Returns true if this interleaved access group can be lowered into
 119   /// x86-specific instructions/intrinsics, false otherwise.
 120   bool isSupported() const;
 121
 122   /// \brief Lowers this interleaved access group into X86-specific
 123   /// instructions/intrinsics.
 124   bool lowerIntoOptimizedSequence();
 125 };
 126
 127 } // end anonymous namespace
 128
 129 bool X86InterleavedAccessGroup::isSupported() const {
 130   VectorType *ShuffleVecTy = Shuffles[0]->getType();
 131   Type *ShuffleEltTy = ShuffleVecTy->getVectorElementType();
 132   unsigned ShuffleElemSize = DL.getTypeSizeInBits(ShuffleEltTy);
 133   unsigned WideInstSize;
 134
 135   // Currently, lowering is supported for the following vectors:
 136   // Stride 4:
 137   //    1. Store and load of 4-element vectors of 64 bits on AVX.
 138   //    2. Store of 16/32-element vectors of 8 bits on AVX.
 139   // Stride 3:
 140   //    1. Load of 16/32-element vectors of 8 bits on AVX.
 141   if (!Subtarget.hasAVX() || (Factor != 4 && Factor != 3))
 142     return false;
 143
 144   if (isa<LoadInst>(Inst)) {
 145     WideInstSize = DL.getTypeSizeInBits(Inst->getType());
 146     if (cast<LoadInst>(Inst)->getPointerAddressSpace())
 147       return false;
 148   } else
 149     WideInstSize = DL.getTypeSizeInBits(Shuffles[0]->getType());
 150
 151   // We support shuffle represents stride 4 for byte type with size of
 152   // WideInstSize.
 153   if (ShuffleElemSize == 64 && WideInstSize == 1024 && Factor == 4)
 154      return true;
 155
 156   if (ShuffleElemSize == 8 && isa<StoreInst>(Inst) && Factor == 4 &&
 157       (WideInstSize == 256 || WideInstSize == 512 || WideInstSize == 1024 ||
 158        WideInstSize == 2048))
 159     return true;
 160
 161   if (ShuffleElemSize == 8 && Factor == 3 &&
 162       (WideInstSize == 384 || WideInstSize == 768 || WideInstSize == 1536))
 163     return true;
 164
 165   return false;
 166 }
 167
 168 void X86InterleavedAccessGroup::decompose(
 169     Instruction *VecInst, unsigned NumSubVectors, VectorType *SubVecTy,
 170     SmallVectorImpl<Instruction *> &DecomposedVectors) {
 171   assert((isa<LoadInst>(VecInst) || isa<ShuffleVectorInst>(VecInst)) &&
 172          "Expected Load or Shuffle");
 173
 174   Type *VecWidth = VecInst->getType();
 175   (void)VecWidth;
 176   assert(VecWidth->isVectorTy() &&
 177          DL.getTypeSizeInBits(VecWidth) >=
 178              DL.getTypeSizeInBits(SubVecTy) * NumSubVectors &&
 179          "Invalid Inst-size!!!");
 180
 181   if (auto *SVI = dyn_cast<ShuffleVectorInst>(VecInst)) {
 182     Value *Op0 = SVI->getOperand(0);
 183     Value *Op1 = SVI->getOperand(1);
 184
 185     // Generate N(= NumSubVectors) shuffles of T(= SubVecTy) type.
 186     for (unsigned i = 0; i < NumSubVectors; ++i)
 187       DecomposedVectors.push_back(
 188           cast<ShuffleVectorInst>(Builder.CreateShuffleVector(
 189               Op0, Op1,
 190               createSequentialMask(Builder, Indices[i],
 191                                    SubVecTy->getVectorNumElements(), 0))));
 192     return;
 193   }
 194
 195   // Decompose the load instruction.
 196   LoadInst *LI = cast<LoadInst>(VecInst);
 197   Type *VecBasePtrTy = SubVecTy->getPointerTo(LI->getPointerAddressSpace());
 198   Value *VecBasePtr;
 199   unsigned int NumLoads = NumSubVectors;
 200   // In the case of stride 3 with a vector of 32 elements load the information
 201   // in the following way:
 202   // [0,1...,VF/2-1,VF/2+VF,VF/2+VF+1,...,2VF-1]
 203   unsigned VecLength = DL.getTypeSizeInBits(VecWidth);
 204   if (VecLength == 768 || VecLength == 1536) {
 205     Type *VecTran =
 206         VectorType::get(Type::getInt8Ty(LI->getContext()), 16)->getPointerTo();
 207     VecBasePtr = Builder.CreateBitCast(LI->getPointerOperand(), VecTran);
 208     NumLoads = NumSubVectors * (VecLength / 384);
 209   } else
 210     VecBasePtr = Builder.CreateBitCast(LI->getPointerOperand(), VecBasePtrTy);
 211   // Generate N loads of T type.
 212   for (unsigned i = 0; i < NumLoads; i++) {
 213     // TODO: Support inbounds GEP.
 214     Value *NewBasePtr = Builder.CreateGEP(VecBasePtr, Builder.getInt32(i));
 215     Instruction *NewLoad =
 216         Builder.CreateAlignedLoad(NewBasePtr, LI->getAlignment());
 217     DecomposedVectors.push_back(NewLoad);
 218   }
 219 }
 220
 221 // Changing the scale of the vector type by reducing the number of elements and
 222 // doubling the scalar size.
 223 static MVT scaleVectorType(MVT VT) {
 224   unsigned ScalarSize = VT.getVectorElementType().getScalarSizeInBits() * 2;
 225   return MVT::getVectorVT(MVT::getIntegerVT(ScalarSize),
 226                           VT.getVectorNumElements() / 2);
 227 }
 228
 229 static uint32_t Concat[] = {
 230   0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  10, 11, 12, 13, 14, 15,
 231   16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31,
 232   32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47,
 233   48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63 };
 234
 235 // genShuffleBland - Creates shuffle according to two vectors.This function is
 236 // only works on instructions with lane inside 256 registers. According to
 237 // the mask 'Mask' creates a new Mask 'Out' by the offset of the mask. The
 238 // offset amount depends on the two integer, 'LowOffset' and 'HighOffset'.
 239 // Where the 'LowOffset' refers to the first vector and the highOffset refers to
 240 // the second vector.
 241 // |a0....a5,b0....b4,c0....c4|a16..a21,b16..b20,c16..c20|
 242 // |c5...c10,a5....a9,b5....b9|c21..c26,a22..a26,b21..b25|
 243 // |b10..b15,c11..c15,a10..a15|b26..b31,c27..c31,a27..a31|
 244 // For the sequence to work as a mirror to the load.
 245 // We must consider the elements order as above.
 246 // In this function we are combining two types of shuffles.
 247 // The first one is vpshufed and the second is a type of "blend" shuffle.
 248 // By computing the shuffle on a sequence of 16 elements(one lane) and add the
 249 // correct offset. We are creating a vpsuffed + blend sequence between two
 250 // shuffles.
 251 static void genShuffleBland(MVT VT, ArrayRef<uint32_t> Mask,
 252   SmallVectorImpl<uint32_t> &Out, int LowOffset,
 253   int HighOffset) {
 254   assert(VT.getSizeInBits() >= 256 &&
 255     "This function doesn't accept width smaller then 256");
 256   unsigned NumOfElm = VT.getVectorNumElements();
 257   for (unsigned i = 0; i < Mask.size(); i++)
 258     Out.push_back(Mask[i] + LowOffset);
 259   for (unsigned i = 0; i < Mask.size(); i++)
 260     Out.push_back(Mask[i] + HighOffset + NumOfElm);
 261 }
 262
 263 // reorderSubVector returns the data to is the original state. And de-facto is
 264 // the opposite of  the function concatSubVector.
 265
 266 // For VecElems = 16
 267 // Invec[0] -  |0|      TransposedMatrix[0] - |0|
 268 // Invec[1] -  |1|  =>  TransposedMatrix[1] - |1|
 269 // Invec[2] -  |2|      TransposedMatrix[2] - |2|
 270
 271 // For VecElems = 32
 272 // Invec[0] -  |0|3|      TransposedMatrix[0] - |0|1|
 273 // Invec[1] -  |1|4|  =>  TransposedMatrix[1] - |2|3|
 274 // Invec[2] -  |2|5|      TransposedMatrix[2] - |4|5|
 275
 276 // For VecElems = 64
 277 // Invec[0] -  |0|3|6|9 |     TransposedMatrix[0] - |0|1|2 |3 |
 278 // Invec[1] -  |1|4|7|10| =>  TransposedMatrix[1] - |4|5|6 |7 |
 279 // Invec[2] -  |2|5|8|11|     TransposedMatrix[2] - |8|9|10|11|
 280
 281 static void reorderSubVector(MVT VT, SmallVectorImpl<Value *> &TransposedMatrix,
 282   ArrayRef<Value *> Vec, ArrayRef<uint32_t> VPShuf,
 283   unsigned VecElems, unsigned Stride,
 284   IRBuilder<> Builder) {
 285
 286   if (VecElems == 16) {
 287     for (unsigned i = 0; i < Stride; i++)
 288       TransposedMatrix[i] = Builder.CreateShuffleVector(
 289         Vec[i], UndefValue::get(Vec[i]->getType()), VPShuf);
 290     return;
 291   }
 292
 293   SmallVector<uint32_t, 32> OptimizeShuf;
 294   Value *Temp[8];
 295
 296   for (unsigned i = 0; i < (VecElems / 16) * Stride; i += 2) {
 297     genShuffleBland(VT, VPShuf, OptimizeShuf, (i / Stride) * 16,
 298       (i + 1) / Stride * 16);
 299     Temp[i / 2] = Builder.CreateShuffleVector(
 300       Vec[i % Stride], Vec[(i + 1) % Stride], OptimizeShuf);
 301     OptimizeShuf.clear();
 302   }
 303
 304   if (VecElems == 32) {
 305     std::copy(Temp, Temp + Stride, TransposedMatrix.begin());
 306     return;
 307   }
 308   else
 309     for (unsigned i = 0; i < Stride; i++)
 310       TransposedMatrix[i] =
 311       Builder.CreateShuffleVector(Temp[2 * i], Temp[2 * i + 1], Concat);
 312 }
 313
 314 void X86InterleavedAccessGroup::interleave8bitStride4VF8(
 315     ArrayRef<Instruction *> Matrix,
 316     SmallVectorImpl<Value *> &TransposedMatrix) {
 317   // Assuming we start from the following vectors:
 318   // Matrix[0]= c0 c1 c2 c3 c4 ... c7
 319   // Matrix[1]= m0 m1 m2 m3 m4 ... m7
 320   // Matrix[2]= y0 y1 y2 y3 y4 ... y7
 321   // Matrix[3]= k0 k1 k2 k3 k4 ... k7
 322
 323   MVT VT = MVT::v8i16;
 324   TransposedMatrix.resize(2);
 325   SmallVector<uint32_t, 16> MaskLow;
 326   SmallVector<uint32_t, 32> MaskLowTemp1, MaskLowWord;
 327   SmallVector<uint32_t, 32> MaskHighTemp1, MaskHighWord;
 328
 329   for (unsigned i = 0; i < 8; ++i) {
 330     MaskLow.push_back(i);
 331     MaskLow.push_back(i + 8);
 332   }
 333
 334   createUnpackShuffleMask<uint32_t>(VT, MaskLowTemp1, true, false);
 335   createUnpackShuffleMask<uint32_t>(VT, MaskHighTemp1, false, false);
 336   scaleShuffleMask<uint32_t>(2, MaskHighTemp1, MaskHighWord);
 337   scaleShuffleMask<uint32_t>(2, MaskLowTemp1, MaskLowWord);
 338   // IntrVec1Low = c0 m0 c1 m1 c2 m2 c3 m3 c4 m4 c5 m5 c6 m6 c7 m7
 339   // IntrVec2Low = y0 k0 y1 k1 y2 k2 y3 k3 y4 k4 y5 k5 y6 k6 y7 k7
 340   Value *IntrVec1Low =
 341       Builder.CreateShuffleVector(Matrix[0], Matrix[1], MaskLow);
 342   Value *IntrVec2Low =
 343       Builder.CreateShuffleVector(Matrix[2], Matrix[3], MaskLow);
 344
 345   // TransposedMatrix[0] = c0 m0 y0 k0 c1 m1 y1 k1 c2 m2 y2 k2 c3 m3 y3 k3
 346   // TransposedMatrix[1] = c4 m4 y4 k4 c5 m5 y5 k5 c6 m6 y6 k6 c7 m7 y7 k7
 347
 348   TransposedMatrix[0] =
 349       Builder.CreateShuffleVector(IntrVec1Low, IntrVec2Low, MaskLowWord);
 350   TransposedMatrix[1] =
 351       Builder.CreateShuffleVector(IntrVec1Low, IntrVec2Low, MaskHighWord);
 352 }
 353
 354 void X86InterleavedAccessGroup::interleave8bitStride4(
 355     ArrayRef<Instruction *> Matrix, SmallVectorImpl<Value *> &TransposedMatrix,
 356     unsigned NumOfElm) {
 357   // Example: Assuming we start from the following vectors:
 358   // Matrix[0]= c0 c1 c2 c3 c4 ... c31
 359   // Matrix[1]= m0 m1 m2 m3 m4 ... m31
 360   // Matrix[2]= y0 y1 y2 y3 y4 ... y31
 361   // Matrix[3]= k0 k1 k2 k3 k4 ... k31
 362
 363   MVT VT = MVT::getVectorVT(MVT::i8, NumOfElm);
 364   MVT HalfVT = scaleVectorType(VT);
 365
 366   TransposedMatrix.resize(4);
 367   SmallVector<uint32_t, 32> MaskHigh;
 368   SmallVector<uint32_t, 32> MaskLow;
 369   SmallVector<uint32_t, 32> LowHighMask[2];
 370   SmallVector<uint32_t, 32> MaskHighTemp;
 371   SmallVector<uint32_t, 32> MaskLowTemp;
 372
 373   // MaskHighTemp and MaskLowTemp built in the vpunpckhbw and vpunpcklbw X86
 374   // shuffle pattern.
 375
 376   createUnpackShuffleMask<uint32_t>(VT, MaskLow, true, false);
 377   createUnpackShuffleMask<uint32_t>(VT, MaskHigh, false, false);
 378
 379   // MaskHighTemp1 and MaskLowTemp1 built in the vpunpckhdw and vpunpckldw X86
 380   // shuffle pattern.
 381
 382   createUnpackShuffleMask<uint32_t>(HalfVT, MaskLowTemp, true, false);
 383   createUnpackShuffleMask<uint32_t>(HalfVT, MaskHighTemp, false, false);
 384   scaleShuffleMask<uint32_t>(2, MaskLowTemp, LowHighMask[0]);
 385   scaleShuffleMask<uint32_t>(2, MaskHighTemp, LowHighMask[1]);
 386
 387   // IntrVec1Low  = c0  m0  c1  m1 ... c7  m7  | c16 m16 c17 m17 ... c23 m23
 388   // IntrVec1High = c8  m8  c9  m9 ... c15 m15 | c24 m24 c25 m25 ... c31 m31
 389   // IntrVec2Low  = y0  k0  y1  k1 ... y7  k7  | y16 k16 y17 k17 ... y23 k23
 390   // IntrVec2High = y8  k8  y9  k9 ... y15 k15 | y24 k24 y25 k25 ... y31 k31
 391   Value *IntrVec[4];
 392
 393   IntrVec[0] = Builder.CreateShuffleVector(Matrix[0], Matrix[1], MaskLow);
 394   IntrVec[1] = Builder.CreateShuffleVector(Matrix[0], Matrix[1], MaskHigh);
 395   IntrVec[2] = Builder.CreateShuffleVector(Matrix[2], Matrix[3], MaskLow);
 396   IntrVec[3] = Builder.CreateShuffleVector(Matrix[2], Matrix[3], MaskHigh);
 397
 398   // cmyk4  cmyk5  cmyk6   cmyk7  | cmyk20 cmyk21 cmyk22 cmyk23
 399   // cmyk12 cmyk13 cmyk14  cmyk15 | cmyk28 cmyk29 cmyk30 cmyk31
 400   // cmyk0  cmyk1  cmyk2   cmyk3  | cmyk16 cmyk17 cmyk18 cmyk19
 401   // cmyk8  cmyk9  cmyk10  cmyk11 | cmyk24 cmyk25 cmyk26 cmyk27
 402
 403   Value *VecOut[4];
 404   for (int i = 0; i < 4; i++)
 405     VecOut[i] = Builder.CreateShuffleVector(IntrVec[i / 2], IntrVec[i / 2 + 2],
 406                                             LowHighMask[i % 2]);
 407
 408   // cmyk0  cmyk1  cmyk2  cmyk3   | cmyk4  cmyk5  cmyk6  cmyk7
 409   // cmyk8  cmyk9  cmyk10 cmyk11  | cmyk12 cmyk13 cmyk14 cmyk15
 410   // cmyk16 cmyk17 cmyk18 cmyk19  | cmyk20 cmyk21 cmyk22 cmyk23
 411   // cmyk24 cmyk25 cmyk26 cmyk27  | cmyk28 cmyk29 cmyk30 cmyk31
 412
 413   if (VT == MVT::v16i8) {
 414     std::copy(VecOut, VecOut + 4, TransposedMatrix.begin());
 415     return;
 416   }
 417
 418   reorderSubVector(VT, TransposedMatrix, VecOut, makeArrayRef(Concat, 16),
 419                    NumOfElm, 4, Builder);
 420 }
 421
 422 //  createShuffleStride returns shuffle mask of size N.
 423 //  The shuffle pattern is as following :
 424 //  {0, Stride%(VF/Lane), (2*Stride%(VF/Lane))...(VF*Stride/Lane)%(VF/Lane),
 425 //  (VF/ Lane) ,(VF / Lane)+Stride%(VF/Lane),...,
 426 //  (VF / Lane)+(VF*Stride/Lane)%(VF/Lane)}
 427 //  Where Lane is the # of lanes in a register:
 428 //  VectorSize = 128 => Lane = 1
 429 //  VectorSize = 256 => Lane = 2
 430 //  For example shuffle pattern for VF 16 register size 256 -> lanes = 2
 431 //  {<[0|3|6|1|4|7|2|5]-[8|11|14|9|12|15|10|13]>}
 432 static void createShuffleStride(MVT VT, int Stride,
 433                                 SmallVectorImpl<uint32_t> &Mask) {
 434   int VectorSize = VT.getSizeInBits();
 435   int VF = VT.getVectorNumElements();
 436   int LaneCount = std::max(VectorSize / 128, 1);
 437   for (int Lane = 0; Lane < LaneCount; Lane++)
 438     for (int i = 0, LaneSize = VF / LaneCount; i != LaneSize; ++i)
 439       Mask.push_back((i * Stride) % LaneSize + LaneSize * Lane);
 440 }
 441
 442 //  setGroupSize sets 'SizeInfo' to the size(number of elements) of group
 443 //  inside mask a shuffleMask. A mask contains exactly 3 groups, where
 444 //  each group is a monotonically increasing sequence with stride 3.
 445 //  For example shuffleMask {0,3,6,1,4,7,2,5} => {3,3,2}
 446 static void setGroupSize(MVT VT, SmallVectorImpl<uint32_t> &SizeInfo) {
 447   int VectorSize = VT.getSizeInBits();
 448   int VF = VT.getVectorNumElements() / std::max(VectorSize / 128, 1);
 449   for (int i = 0, FirstGroupElement = 0; i < 3; i++) {
 450     int GroupSize = std::ceil((VF - FirstGroupElement) / 3.0);
 451     SizeInfo.push_back(GroupSize);
 452     FirstGroupElement = ((GroupSize)*3 + FirstGroupElement) % VF;
 453   }
 454 }
 455
 456 //  DecodePALIGNRMask returns the shuffle mask of vpalign instruction.
 457 //  vpalign works according to lanes
 458 //  Where Lane is the # of lanes in a register:
 459 //  VectorWide = 128 => Lane = 1
 460 //  VectorWide = 256 => Lane = 2
 461 //  For Lane = 1 shuffle pattern is: {DiffToJump,...,DiffToJump+VF-1}.
 462 //  For Lane = 2 shuffle pattern is:
 463 //  {DiffToJump,...,VF/2-1,VF,...,DiffToJump+VF-1}.
 464 //  Imm variable sets the offset amount. The result of the
 465 //  function is stored inside ShuffleMask vector and it built as described in
 466 //  the begin of the description. AlignDirection is a boolean that indecat the
 467 //  direction of the alignment. (false - align to the "right" side while true -
 468 //  align to the "left" side)
 469 static void DecodePALIGNRMask(MVT VT, unsigned Imm,
 470                               SmallVectorImpl<uint32_t> &ShuffleMask,
 471                               bool AlignDirection = true, bool Unary = false) {
 472   unsigned NumElts = VT.getVectorNumElements();
 473   unsigned NumLanes = std::max((int)VT.getSizeInBits() / 128, 1);
 474   unsigned NumLaneElts = NumElts / NumLanes;
 475
 476   Imm = AlignDirection ? Imm : (NumLaneElts - Imm);
 477   unsigned Offset = Imm * (VT.getScalarSizeInBits() / 8);
 478
 479   for (unsigned l = 0; l != NumElts; l += NumLaneElts) {
 480     for (unsigned i = 0; i != NumLaneElts; ++i) {
 481       unsigned Base = i + Offset;
 482       // if i+offset is out of this lane then we actually need the other source
 483       // If Unary the other source is the first source.
 484       if (Base >= NumLaneElts)
 485         Base = Unary ? Base % NumLaneElts : Base + NumElts - NumLaneElts;
 486       ShuffleMask.push_back(Base + l);
 487     }
 488   }
 489 }
 490
 491 // concatSubVector - The function rebuilds the data to a correct expected
 492 // order. An assumption(The shape of the matrix) was taken for the
 493 // deinterleaved to work with lane's instructions like 'vpalign' or 'vphuf'.
 494 // This function ensures that the data is built in correct way for the lane
 495 // instructions. Each lane inside the vector is a 128-bit length.
 496 //
 497 // The 'InVec' argument contains the data in increasing order. In InVec[0] You
 498 // can find the first 128 bit data. The number of different lanes inside a
 499 // vector depends on the 'VecElems'.In general, the formula is
 500 // VecElems * type / 128. The size of the array 'InVec' depends and equal to
 501 // 'VecElems'.
 502
 503 // For VecElems = 16
 504 // Invec[0] - |0|      Vec[0] - |0|
 505 // Invec[1] - |1|  =>  Vec[1] - |1|
 506 // Invec[2] - |2|      Vec[2] - |2|
 507
 508 // For VecElems = 32
 509 // Invec[0] - |0|1|      Vec[0] - |0|3|
 510 // Invec[1] - |2|3|  =>  Vec[1] - |1|4|
 511 // Invec[2] - |4|5|      Vec[2] - |2|5|
 512
 513 // For VecElems = 64
 514 // Invec[0] - |0|1|2 |3 |      Vec[0] - |0|3|6|9 |
 515 // Invec[1] - |4|5|6 |7 |  =>  Vec[1] - |1|4|7|10|
 516 // Invec[2] - |8|9|10|11|      Vec[2] - |2|5|8|11|
 517
 518 static void concatSubVector(Value **Vec, ArrayRef<Instruction *> InVec,
 519                             unsigned VecElems, IRBuilder<> Builder) {
 520   if (VecElems == 16) {
 521     for (int i = 0; i < 3; i++)
 522       Vec[i] = InVec[i];
 523     return;
 524   }
 525
 526   for (unsigned j = 0; j < VecElems / 32; j++)
 527     for (int i = 0; i < 3; i++)
 528       Vec[i + j * 3] = Builder.CreateShuffleVector(
 529           InVec[j * 6 + i], InVec[j * 6 + i + 3], makeArrayRef(Concat, 32));
 530
 531   if (VecElems == 32)
 532     return;
 533
 534   for (int i = 0; i < 3; i++)
 535     Vec[i] = Builder.CreateShuffleVector(Vec[i], Vec[i + 3], Concat);
 536 }
 537
 538 void X86InterleavedAccessGroup::deinterleave8bitStride3(
 539     ArrayRef<Instruction *> InVec, SmallVectorImpl<Value *> &TransposedMatrix,
 540     unsigned VecElems) {
 541   // Example: Assuming we start from the following vectors:
 542   // Matrix[0]= a0 b0 c0 a1 b1 c1 a2 b2
 543   // Matrix[1]= c2 a3 b3 c3 a4 b4 c4 a5
 544   // Matrix[2]= b5 c5 a6 b6 c6 a7 b7 c7
 545
 546   TransposedMatrix.resize(3);
 547   SmallVector<uint32_t, 32> VPShuf;
 548   SmallVector<uint32_t, 32> VPAlign[2];
 549   SmallVector<uint32_t, 32> VPAlign2;
 550   SmallVector<uint32_t, 32> VPAlign3;
 551   SmallVector<uint32_t, 3> GroupSize;
 552   Value *Vec[6], *TempVector[3];
 553
 554   MVT VT = MVT::getVT(Shuffles[0]->getType());
 555
 556   createShuffleStride(VT, 3, VPShuf);
 557   setGroupSize(VT, GroupSize);
 558
 559   for (int i = 0; i < 2; i++)
 560     DecodePALIGNRMask(VT, GroupSize[2 - i], VPAlign[i], false);
 561
 562   DecodePALIGNRMask(VT, GroupSize[2] + GroupSize[1], VPAlign2, true, true);
 563   DecodePALIGNRMask(VT, GroupSize[1], VPAlign3, true, true);
 564
 565   concatSubVector(Vec, InVec, VecElems, Builder);
 566   // Vec[0]= a0 a1 a2 b0 b1 b2 c0 c1
 567   // Vec[1]= c2 c3 c4 a3 a4 a5 b3 b4
 568   // Vec[2]= b5 b6 b7 c5 c6 c7 a6 a7
 569
 570   for (int i = 0; i < 3; i++)
 571     Vec[i] = Builder.CreateShuffleVector(
 572         Vec[i], UndefValue::get(Vec[0]->getType()), VPShuf);
 573
 574   // TempVector[0]= a6 a7 a0 a1 a2 b0 b1 b2
 575   // TempVector[1]= c0 c1 c2 c3 c4 a3 a4 a5
 576   // TempVector[2]= b3 b4 b5 b6 b7 c5 c6 c7
 577
 578   for (int i = 0; i < 3; i++)
 579     TempVector[i] =
 580         Builder.CreateShuffleVector(Vec[(i + 2) % 3], Vec[i], VPAlign[0]);
 581
 582   // Vec[0]= a3 a4 a5 a6 a7 a0 a1 a2
 583   // Vec[1]= c5 c6 c7 c0 c1 c2 c3 c4
 584   // Vec[2]= b0 b1 b2 b3 b4 b5 b6 b7
 585
 586   for (int i = 0; i < 3; i++)
 587     Vec[i] = Builder.CreateShuffleVector(TempVector[(i + 1) % 3], TempVector[i],
 588                                          VPAlign[1]);
 589
 590   // TransposedMatrix[0]= a0 a1 a2 a3 a4 a5 a6 a7
 591   // TransposedMatrix[1]= b0 b1 b2 b3 b4 b5 b6 b7
 592   // TransposedMatrix[2]= c0 c1 c2 c3 c4 c5 c6 c7
 593
 594   Value *TempVec = Builder.CreateShuffleVector(
 595       Vec[1], UndefValue::get(Vec[1]->getType()), VPAlign3);
 596   TransposedMatrix[0] = Builder.CreateShuffleVector(
 597       Vec[0], UndefValue::get(Vec[1]->getType()), VPAlign2);
 598   TransposedMatrix[1] = VecElems == 8 ? Vec[2] : TempVec;
 599   TransposedMatrix[2] = VecElems == 8 ? TempVec : Vec[2];
 600 }
 601
 602 // group2Shuffle reorder the shuffle stride back into continuous order.
 603 // For example For VF16 with Mask1 = {0,3,6,9,12,15,2,5,8,11,14,1,4,7,10,13} =>
 604 // MaskResult = {0,11,6,1,12,7,2,13,8,3,14,9,4,15,10,5}.
 605 static void group2Shuffle(MVT VT, SmallVectorImpl<uint32_t> &Mask,
 606                           SmallVectorImpl<uint32_t> &Output) {
 607   int IndexGroup[3] = {0, 0, 0};
 608   int Index = 0;
 609   int VectorWidth = VT.getSizeInBits();
 610   int VF = VT.getVectorNumElements();
 611   // Find the index of the different groups.
 612   int Lane = (VectorWidth / 128 > 0) ? VectorWidth / 128 : 1;
 613   for (int i = 0; i < 3; i++) {
 614     IndexGroup[(Index * 3) % (VF / Lane)] = Index;
 615     Index += Mask[i];
 616   }
 617   // According to the index compute the convert mask.
 618   for (int i = 0; i < VF / Lane; i++) {
 619     Output.push_back(IndexGroup[i % 3]);
 620     IndexGroup[i % 3]++;
 621   }
 622 }
 623
 624 void X86InterleavedAccessGroup::interleave8bitStride3(
 625     ArrayRef<Instruction *> InVec, SmallVectorImpl<Value *> &TransposedMatrix,
 626     unsigned VecElems) {
 627   // Example: Assuming we start from the following vectors:
 628   // Matrix[0]= a0 a1 a2 a3 a4 a5 a6 a7
 629   // Matrix[1]= b0 b1 b2 b3 b4 b5 b6 b7
 630   // Matrix[2]= c0 c1 c2 c3 c3 a7 b7 c7
 631
 632   TransposedMatrix.resize(3);
 633   SmallVector<uint32_t, 3> GroupSize;
 634   SmallVector<uint32_t, 32> VPShuf;
 635   SmallVector<uint32_t, 32> VPAlign[3];
 636   SmallVector<uint32_t, 32> VPAlign2;
 637   SmallVector<uint32_t, 32> VPAlign3;
 638
 639   Value *Vec[3], *TempVector[3];
 640   MVT VT = MVT::getVectorVT(MVT::i8, VecElems);
 641
 642   setGroupSize(VT, GroupSize);
 643
 644   for (int i = 0; i < 3; i++)
 645     DecodePALIGNRMask(VT, GroupSize[i], VPAlign[i]);
 646
 647   DecodePALIGNRMask(VT, GroupSize[1] + GroupSize[2], VPAlign2, false, true);
 648   DecodePALIGNRMask(VT, GroupSize[1], VPAlign3, false, true);
 649
 650   // Vec[0]= a3 a4 a5 a6 a7 a0 a1 a2
 651   // Vec[1]= c5 c6 c7 c0 c1 c2 c3 c4
 652   // Vec[2]= b0 b1 b2 b3 b4 b5 b6 b7
 653
 654   Vec[0] = Builder.CreateShuffleVector(
 655       InVec[0], UndefValue::get(InVec[0]->getType()), VPAlign2);
 656   Vec[1] = Builder.CreateShuffleVector(
 657       InVec[1], UndefValue::get(InVec[1]->getType()), VPAlign3);
 658   Vec[2] = InVec[2];
 659
 660   // Vec[0]= a6 a7 a0 a1 a2 b0 b1 b2
 661   // Vec[1]= c0 c1 c2 c3 c4 a3 a4 a5
 662   // Vec[2]= b3 b4 b5 b6 b7 c5 c6 c7
 663
 664   for (int i = 0; i < 3; i++)
 665     TempVector[i] =
 666         Builder.CreateShuffleVector(Vec[i], Vec[(i + 2) % 3], VPAlign[1]);
 667
 668   // Vec[0]= a0 a1 a2 b0 b1 b2 c0 c1
 669   // Vec[1]= c2 c3 c4 a3 a4 a5 b3 b4
 670   // Vec[2]= b5 b6 b7 c5 c6 c7 a6 a7
 671
 672   for (int i = 0; i < 3; i++)
 673     Vec[i] = Builder.CreateShuffleVector(TempVector[i], TempVector[(i + 1) % 3],
 674                                          VPAlign[2]);
 675
 676   // TransposedMatrix[0] = a0 b0 c0 a1 b1 c1 a2 b2
 677   // TransposedMatrix[1] = c2 a3 b3 c3 a4 b4 c4 a5
 678   // TransposedMatrix[2] = b5 c5 a6 b6 c6 a7 b7 c7
 679
 680   unsigned NumOfElm = VT.getVectorNumElements();
 681   group2Shuffle(VT, GroupSize, VPShuf);
 682   reorderSubVector(VT, TransposedMatrix, Vec, VPShuf, NumOfElm,3, Builder);
 683 }
 684
 685 void X86InterleavedAccessGroup::transpose_4x4(
 686     ArrayRef<Instruction *> Matrix,
 687     SmallVectorImpl<Value *> &TransposedMatrix) {
 688   assert(Matrix.size() == 4 && "Invalid matrix size");
 689   TransposedMatrix.resize(4);
 690
 691   // dst = src1[0,1],src2[0,1]
 692   uint32_t IntMask1[] = {0, 1, 4, 5};
 693   ArrayRef<uint32_t> Mask = makeArrayRef(IntMask1, 4);
 694   Value *IntrVec1 = Builder.CreateShuffleVector(Matrix[0], Matrix[2], Mask);
 695   Value *IntrVec2 = Builder.CreateShuffleVector(Matrix[1], Matrix[3], Mask);
 696
 697   // dst = src1[2,3],src2[2,3]
 698   uint32_t IntMask2[] = {2, 3, 6, 7};
 699   Mask = makeArrayRef(IntMask2, 4);
 700   Value *IntrVec3 = Builder.CreateShuffleVector(Matrix[0], Matrix[2], Mask);
 701   Value *IntrVec4 = Builder.CreateShuffleVector(Matrix[1], Matrix[3], Mask);
 702
 703   // dst = src1[0],src2[0],src1[2],src2[2]
 704   uint32_t IntMask3[] = {0, 4, 2, 6};
 705   Mask = makeArrayRef(IntMask3, 4);
 706   TransposedMatrix[0] = Builder.CreateShuffleVector(IntrVec1, IntrVec2, Mask);
 707   TransposedMatrix[2] = Builder.CreateShuffleVector(IntrVec3, IntrVec4, Mask);
 708
 709   // dst = src1[1],src2[1],src1[3],src2[3]
 710   uint32_t IntMask4[] = {1, 5, 3, 7};
 711   Mask = makeArrayRef(IntMask4, 4);
 712   TransposedMatrix[1] = Builder.CreateShuffleVector(IntrVec1, IntrVec2, Mask);
 713   TransposedMatrix[3] = Builder.CreateShuffleVector(IntrVec3, IntrVec4, Mask);
 714 }
 715
 716 // Lowers this interleaved access group into X86-specific
 717 // instructions/intrinsics.
 718 bool X86InterleavedAccessGroup::lowerIntoOptimizedSequence() {
 719   SmallVector<Instruction *, 4> DecomposedVectors;
 720   SmallVector<Value *, 4> TransposedVectors;
 721   VectorType *ShuffleTy = Shuffles[0]->getType();
 722
 723   if (isa<LoadInst>(Inst)) {
 724     // Try to generate target-sized register(/instruction).
 725     decompose(Inst, Factor, ShuffleTy, DecomposedVectors);
 726
 727     Type *ShuffleEltTy = Inst->getType();
 728     unsigned NumSubVecElems = ShuffleEltTy->getVectorNumElements() / Factor;
 729     // Perform matrix-transposition in order to compute interleaved
 730     // results by generating some sort of (optimized) target-specific
 731     // instructions.
 732
 733     switch (NumSubVecElems) {
 734     default:
 735       return false;
 736     case 4:
 737       transpose_4x4(DecomposedVectors, TransposedVectors);
 738       break;
 739     case 8:
 740     case 16:
 741     case 32:
 742     case 64:
 743       deinterleave8bitStride3(DecomposedVectors, TransposedVectors,
 744                               NumSubVecElems);
 745       break;
 746     }
 747
 748     // Now replace the unoptimized-interleaved-vectors with the
 749     // transposed-interleaved vectors.
 750     for (unsigned i = 0, e = Shuffles.size(); i < e; ++i)
 751       Shuffles[i]->replaceAllUsesWith(TransposedVectors[Indices[i]]);
 752
 753     return true;
 754   }
 755
 756   Type *ShuffleEltTy = ShuffleTy->getVectorElementType();
 757   unsigned NumSubVecElems = ShuffleTy->getVectorNumElements() / Factor;
 758
 759   // Lower the interleaved stores:
 760   //   1. Decompose the interleaved wide shuffle into individual shuffle
 761   //   vectors.
 762   decompose(Shuffles[0], Factor, VectorType::get(ShuffleEltTy, NumSubVecElems),
 763             DecomposedVectors);
 764
 765   //   2. Transpose the interleaved-vectors into vectors of contiguous
 766   //      elements.
 767   switch (NumSubVecElems) {
 768   case 4:
 769     transpose_4x4(DecomposedVectors, TransposedVectors);
 770     break;
 771   case 8:
 772     interleave8bitStride4VF8(DecomposedVectors, TransposedVectors);
 773     break;
 774   case 16:
 775   case 32:
 776   case 64:
 777     if (Factor == 4)
 778       interleave8bitStride4(DecomposedVectors, TransposedVectors,
 779                             NumSubVecElems);
 780     if (Factor == 3)
 781       interleave8bitStride3(DecomposedVectors, TransposedVectors,
 782                             NumSubVecElems);
 783     break;
 784   default:
 785     return false;
 786   }
 787
 788   //   3. Concatenate the contiguous-vectors back into a wide vector.
 789   Value *WideVec = concatenateVectors(Builder, TransposedVectors);
 790
 791   //   4. Generate a store instruction for wide-vec.
 792   StoreInst *SI = cast<StoreInst>(Inst);
 793   Builder.CreateAlignedStore(WideVec, SI->getPointerOperand(),
 794                              SI->getAlignment());
 795
 796   return true;
 797 }
 798
 799 // Lower interleaved load(s) into target specific instructions/
 800 // intrinsics. Lowering sequence varies depending on the vector-types, factor,
 801 // number of shuffles and ISA.
 802 // Currently, lowering is supported for 4x64 bits with Factor = 4 on AVX.
 803 bool X86TargetLowering::lowerInterleavedLoad(
 804     LoadInst *LI, ArrayRef<ShuffleVectorInst *> Shuffles,
 805     ArrayRef<unsigned> Indices, unsigned Factor) const {
 806   assert(Factor >= 2 && Factor <= getMaxSupportedInterleaveFactor() &&
 807          "Invalid interleave factor");
 808   assert(!Shuffles.empty() && "Empty shufflevector input");
 809   assert(Shuffles.size() == Indices.size() &&
 810          "Unmatched number of shufflevectors and indices");
 811
 812   // Create an interleaved access group.
 813   IRBuilder<> Builder(LI);
 814   X86InterleavedAccessGroup Grp(LI, Shuffles, Indices, Factor, Subtarget,
 815                                 Builder);
 816
 817   return Grp.isSupported() && Grp.lowerIntoOptimizedSequence();
 818 }
 819
 820 bool X86TargetLowering::lowerInterleavedStore(StoreInst *SI,
 821                                               ShuffleVectorInst *SVI,
 822                                               unsigned Factor) const {
 823   assert(Factor >= 2 && Factor <= getMaxSupportedInterleaveFactor() &&
 824          "Invalid interleave factor");
 825
 826   assert(SVI->getType()->getVectorNumElements() % Factor == 0 &&
 827          "Invalid interleaved store");
 828
 829   // Holds the indices of SVI that correspond to the starting index of each
 830   // interleaved shuffle.
 831   SmallVector<unsigned, 4> Indices;
 832   auto Mask = SVI->getShuffleMask();
 833   for (unsigned i = 0; i < Factor; i++)
 834     Indices.push_back(Mask[i]);
 835
 836   ArrayRef<ShuffleVectorInst *> Shuffles = makeArrayRef(SVI);
 837
 838   // Create an interleaved access group.
 839   IRBuilder<> Builder(SI);
 840   X86InterleavedAccessGroup Grp(SI, Shuffles, Indices, Factor, Subtarget,
 841                                 Builder);
 842
 843   return Grp.isSupported() && Grp.lowerIntoOptimizedSequence();
 844 }