Subzero. X86. Lowers shufflevector using xmm instructions.

src/IceTargetLoweringX86BaseImpl.h

 //===- subzero/src/IceTargetLoweringX86BaseImpl.h - x86 lowering -*- C++ -*-==//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
@@ skipping 5552 matching lines @@
   }
   // Add a ret instruction even if sandboxing is enabled, because addEpilog
   // explicitly looks for a ret instruction as a marker for where to insert the
   // frame removal instructions.
   _ret(Reg);
   // Add a fake use of esp to make sure esp stays alive for the entire
   // function. Otherwise post-call esp adjustments get dead-code eliminated.
   keepEspLiveAtExit();
 }
 
+inline int32_t makePshufdMask(SizeT Index0, SizeT Index1, SizeT Index2,

[Jim Stichnoth, 2016/04/25 21:23:45]

I'm wondering whether these SizeT should be explicit uint32_t.

Usually SizeT is meant for values that would normally be size_t, but the PNaCl
bitcode constraints make it safe to limit to 32-bits even when the translator is
built for a 64-bit environment.

[John, 2016/04/25 22:38:39]

These stem from SizeT values -- i.e., operand indexes. I think this is a
reasonable use for SizeT. Thoughts?

[Jim Stichnoth, 2016/04/25 23:09:03]

I should have added more to my description above of SizeT.  The other aspect is
that if we were to extend PNaCl to be 64-bit, and needed to change SizeT to
uint64_t to allow a function to have a bazillion
variables/instructions/blocks/whatever, we still would not need vector indexes
to be 64-bit.

That said, SizeT is really there so that object fields can be 32-bit instead of
64-bit, and I don't think these indexes are actually stored in objects, so it's
probably a moot point.

[John, 2016/04/26 11:14:13]

Acknowledged.

+                              SizeT Index3) {
+  const SizeT Mask = (Index0 & 0x3) | ((Index1 & 0x3) << 2) |
+                     ((Index2 & 0x3) << 4) | ((Index3 & 0x3) << 6);
+  assert(Mask < 256);
+  return Mask;

[Jim Stichnoth, 2016/04/25 21:23:45]

Mask is unsigned, but the function returns a signed value.  Fix this?

[John, 2016/04/25 22:38:39]

Mixing signed and unsigned integer types... what could possibly go wrong? Done.

+}
+
+template <typename TraitsType>
+Variable *TargetX86Base<TraitsType>::lowerShuffleVector_AllFromSameSrc(
+    Variable *Src, SizeT Index0, SizeT Index1, SizeT Index2, SizeT Index3) {
+  constexpr SizeT SrcBit = 1 << 2;
+  assert((Index0 & SrcBit) == (Index1 & SrcBit));
+  assert((Index0 & SrcBit) == (Index2 & SrcBit));
+  assert((Index0 & SrcBit) == (Index3 & SrcBit));
+  (void)SrcBit;
+
+  const Type SrcTy = Src->getType();
+  auto *T = makeReg(SrcTy);
+  auto *SrcRM = legalize(Src, Legal_Reg | Legal_Mem);
+  auto *Mask =
+      Ctx->getConstantInt32(makePshufdMask(Index0, Index1, Index2, Index3));
+  _pshufd(T, SrcRM, Mask);
+  return T;
+}
+
+template <typename TraitsType>
+Variable *TargetX86Base<TraitsType>::lowerShuffleVector_TwoFromSameSrc(
+    Variable *Src0, SizeT Index0, SizeT Index1, Variable *Src1, SizeT Index2,
+    SizeT Index3) {
+  constexpr SizeT SrcBit = 1 << 2;
+  assert((Index0 & SrcBit) == (Index1 & SrcBit) || (Index1 == IGNORE_INDEX));
+  assert((Index2 & SrcBit) == (Index3 & SrcBit) || (Index3 == IGNORE_INDEX));
+  (void)SrcBit;
+
+  const Type SrcTy = Src0->getType();
+  assert(Src1->getType() == SrcTy);
+  auto *T = makeReg(SrcTy);
+  auto *Src0R = legalizeToReg(Src0);
+  auto *Src1RM = legalize(Src1, Legal_Reg | Legal_Mem);
+  auto *Mask =
+      Ctx->getConstantInt32(makePshufdMask(Index0, Index1, Index2, Index3));
+  _movp(T, Src0R);
+  _shufps(T, Src1RM, Mask);
+  return T;
+}
+
+template <typename TraitsType>
+Variable *TargetX86Base<TraitsType>::lowerShuffleVector_UnifyFromDifferentSrcs(
+    Variable *Src0, SizeT Index0, Variable *Src1, SizeT Index1) {
+  return lowerShuffleVector_TwoFromSameSrc(Src0, Index0, IGNORE_INDEX, Src1,
+                                           Index1, IGNORE_INDEX);
+}
+
+inline SizeT makeSrcSwitchMask(SizeT Index0, SizeT Index1, SizeT Index2,
+                               SizeT Index3) {
+  constexpr SizeT SrcBit = 1 << 2;
+  const SizeT Index0Bits = ((Index0 & SrcBit) == 0) ? 0 : (1 << 0);
+  const SizeT Index1Bits = ((Index1 & SrcBit) == 0) ? 0 : (1 << 1);
+  const SizeT Index2Bits = ((Index2 & SrcBit) == 0) ? 0 : (1 << 2);
+  const SizeT Index3Bits = ((Index3 & SrcBit) == 0) ? 0 : (1 << 3);
+  return Index0Bits | Index1Bits | Index2Bits | Index3Bits;
+}
+
 template <typename TraitsType>
 void TargetX86Base<TraitsType>::lowerShuffleVector(
     const InstShuffleVector *Instr) {
   auto *Dest = Instr->getDest();
   const Type DestTy = Dest->getType();
+  auto *Src0 = llvm::cast<Variable>(Instr->getSrc(0));
+  auto *Src1 = llvm::cast<Variable>(Instr->getSrc(1));
+  const SizeT NumElements = typeNumElements(DestTy);
 
   auto *T = makeReg(DestTy);
 
   switch (DestTy) {
   default:
     break;
-    // TODO(jpp): figure out how to properly lower this without scalarization.
+  // TODO(jpp): figure out how to properly lower the remaining cases without
+  // scalarization.
+  case IceType_v4i1:
+  case IceType_v4i32:
+  case IceType_v4f32: {
+    static constexpr SizeT ExpectedNumElements = 4;
+    assert(ExpectedNumElements == Instr->getNumIndexes());
+    const SizeT Index0 = Instr->getIndex(0)->getValue();
+    const SizeT Index1 = Instr->getIndex(1)->getValue();
+    const SizeT Index2 = Instr->getIndex(2)->getValue();
+    const SizeT Index3 = Instr->getIndex(3)->getValue();
+    Variable *T = nullptr;
+    switch (makeSrcSwitchMask(Index0, Index1, Index2, Index3)) {
+#define CASE_SRCS_IN(S0, S1, S2, S3)                                           \
+  case (((S0) << 0) | ((S1) << 1) | ((S2) << 2) | ((S3) << 3))
+      CASE_SRCS_IN(0, 0, 0, 0) : {
+        T = lowerShuffleVector_AllFromSameSrc(Src0, Index0, Index1, Index2,
+                                              Index3);
+      }
+      break;
+      CASE_SRCS_IN(0, 0, 0, 1) : {
+        auto *Unified = lowerShuffleVector_UnifyFromDifferentSrcs(Src0, Index2,
+                                                                  Src1, Index3);
+        T = lowerShuffleVector_TwoFromSameSrc(Src0, Index0, Index1, Unified,
+                                              UNIFIED_INDEX_0, UNIFIED_INDEX_1);
+      }
+      break;
+      CASE_SRCS_IN(0, 0, 1, 0) : {
+        auto *Unified = lowerShuffleVector_UnifyFromDifferentSrcs(Src1, Index2,
+                                                                  Src0, Index3);
+        T = lowerShuffleVector_TwoFromSameSrc(Src0, Index0, Index1, Unified,
+                                              UNIFIED_INDEX_0, UNIFIED_INDEX_1);
+      }
+      break;
+      CASE_SRCS_IN(0, 0, 1, 1) : {
+        T = lowerShuffleVector_TwoFromSameSrc(Src0, Index0, Index1, Src1,
+                                              Index2, Index3);
+      }
+      break;
+      CASE_SRCS_IN(0, 1, 0, 0) : {
+        auto *Unified = lowerShuffleVector_UnifyFromDifferentSrcs(Src0, Index0,
+                                                                  Src1, Index1);
+        T = lowerShuffleVector_TwoFromSameSrc(
+            Unified, UNIFIED_INDEX_0, UNIFIED_INDEX_1, Src0, Index2, Index3);
+      }
+      break;
+      CASE_SRCS_IN(0, 1, 0, 1) : {
+        if (Index0 == 0 && (Index1 - ExpectedNumElements) == 0 && Index2 == 1 &&
+            (Index3 - ExpectedNumElements) == 1) {
+          auto *Src1RM = legalize(Src1, Legal_Reg | Legal_Mem);
+          auto *Src0R = legalizeToReg(Src0);
+          T = makeReg(DestTy);
+          _movp(T, Src0R);
+          _punpckl(T, Src1RM);
+          assert(false);

[Jim Stichnoth, 2016/04/25 21:23:45]

???  Is something got getting tested that ought to be?

[John, 2016/04/25 22:38:39]

Discussed offline.

For posterity: none of the CASE_SRCS_IN(?, ?, ?, 1) will trigger with the
current implementation -- the first element in a shufflevector instructions
always comes from src0.

+        } else if (Index0 == Index2 && Index1 == Index3) {
+          auto *Unified = lowerShuffleVector_UnifyFromDifferentSrcs(
+              Src0, Index0, Src1, Index1);
+          T = lowerShuffleVector_AllFromSameSrc(
+              Unified, UNIFIED_INDEX_0, UNIFIED_INDEX_1, UNIFIED_INDEX_0,
+              UNIFIED_INDEX_1);
+        } else {
+          auto *Unified0 = lowerShuffleVector_UnifyFromDifferentSrcs(
+              Src0, Index0, Src1, Index1);
+          auto *Unified1 = lowerShuffleVector_UnifyFromDifferentSrcs(
+              Src0, Index2, Src1, Index3);
+          T = lowerShuffleVector_TwoFromSameSrc(
+              Unified0, UNIFIED_INDEX_0, UNIFIED_INDEX_1, Unified1,
+              UNIFIED_INDEX_0, UNIFIED_INDEX_1);
+        }
+      }
+      break;
+      CASE_SRCS_IN(0, 1, 1, 0) : {
+        if (Index0 == Index3 && Index1 == Index2) {
+          auto *Unified = lowerShuffleVector_UnifyFromDifferentSrcs(
+              Src0, Index0, Src1, Index1);
+          T = lowerShuffleVector_AllFromSameSrc(
+              Unified, UNIFIED_INDEX_0, UNIFIED_INDEX_1, UNIFIED_INDEX_1,
+              UNIFIED_INDEX_0);
+        } else {
+          auto *Unified0 = lowerShuffleVector_UnifyFromDifferentSrcs(
+              Src0, Index0, Src1, Index1);
+          auto *Unified1 = lowerShuffleVector_UnifyFromDifferentSrcs(
+              Src1, Index2, Src0, Index3);
+          T = lowerShuffleVector_TwoFromSameSrc(
+              Unified0, UNIFIED_INDEX_0, UNIFIED_INDEX_1, Unified1,
+              UNIFIED_INDEX_0, UNIFIED_INDEX_1);
+        }
+      }
+      break;
+      CASE_SRCS_IN(0, 1, 1, 1) : {
+        auto *Unified = lowerShuffleVector_UnifyFromDifferentSrcs(Src0, Index0,
+                                                                  Src1, Index1);
+        T = lowerShuffleVector_TwoFromSameSrc(
+            Unified, UNIFIED_INDEX_0, UNIFIED_INDEX_1, Src1, Index2, Index3);
+      }
+      break;
+      CASE_SRCS_IN(1, 0, 0, 0) : {
+        auto *Unified = lowerShuffleVector_UnifyFromDifferentSrcs(Src1, Index0,
+                                                                  Src0, Index1);
+        T = lowerShuffleVector_TwoFromSameSrc(
+            Unified, UNIFIED_INDEX_0, UNIFIED_INDEX_1, Src0, Index2, Index3);
+      }
+      break;
+      CASE_SRCS_IN(1, 0, 0, 1) : {
+        if (Index0 == Index3 && Index1 == Index2) {
+          auto *Unified = lowerShuffleVector_UnifyFromDifferentSrcs(
+              Src1, Index0, Src0, Index1);
+          T = lowerShuffleVector_AllFromSameSrc(
+              Unified, UNIFIED_INDEX_0, UNIFIED_INDEX_1, UNIFIED_INDEX_1,
+              UNIFIED_INDEX_0);
+        } else {
+          auto *Unified0 = lowerShuffleVector_UnifyFromDifferentSrcs(
+              Src1, Index0, Src0, Index1);
+          auto *Unified1 = lowerShuffleVector_UnifyFromDifferentSrcs(
+              Src0, Index2, Src1, Index3);
+          T = lowerShuffleVector_TwoFromSameSrc(
+              Unified0, UNIFIED_INDEX_0, UNIFIED_INDEX_1, Unified1,
+              UNIFIED_INDEX_0, UNIFIED_INDEX_1);
+        }
+      }
+      break;
+      CASE_SRCS_IN(1, 0, 1, 0) : {
+        if ((Index0 - ExpectedNumElements) == 0 && Index1 == 0 &&
+            (Index2 - ExpectedNumElements) == 1 && Index3 == 1) {
+          auto *Src1RM = legalize(Src0, Legal_Reg | Legal_Mem);
+          auto *Src0R = legalizeToReg(Src1);
+          T = makeReg(DestTy);
+          _movp(T, Src0R);
+          _punpckl(T, Src1RM);
+        } else if (Index0 == Index2 && Index1 == Index3) {
+          auto *Unified = lowerShuffleVector_UnifyFromDifferentSrcs(
+              Src1, Index0, Src0, Index1);
+          T = lowerShuffleVector_AllFromSameSrc(
+              Unified, UNIFIED_INDEX_0, UNIFIED_INDEX_1, UNIFIED_INDEX_0,
+              UNIFIED_INDEX_1);
+        } else {
+          auto *Unified0 = lowerShuffleVector_UnifyFromDifferentSrcs(
+              Src1, Index0, Src0, Index1);
+          auto *Unified1 = lowerShuffleVector_UnifyFromDifferentSrcs(
+              Src1, Index2, Src0, Index3);
+          T = lowerShuffleVector_TwoFromSameSrc(
+              Unified0, UNIFIED_INDEX_0, UNIFIED_INDEX_1, Unified1,
+              UNIFIED_INDEX_0, UNIFIED_INDEX_1);
+        }
+      }
+      break;
+      CASE_SRCS_IN(1, 0, 1, 1) : {
+        auto *Unified = lowerShuffleVector_UnifyFromDifferentSrcs(Src1, Index0,
+                                                                  Src0, Index1);
+        T = lowerShuffleVector_TwoFromSameSrc(
+            Unified, UNIFIED_INDEX_0, UNIFIED_INDEX_1, Src1, Index2, Index3);
+      }
+      break;
+      CASE_SRCS_IN(1, 1, 0, 0) : {
+        T = lowerShuffleVector_TwoFromSameSrc(Src1, Index0, Index1, Src0,
+                                              Index2, Index3);
+      }
+      break;
+      CASE_SRCS_IN(1, 1, 0, 1) : {
+        auto *Unified = lowerShuffleVector_UnifyFromDifferentSrcs(Src0, Index2,
+                                                                  Src1, Index3);
+        T = lowerShuffleVector_TwoFromSameSrc(Src1, Index0, Index1, Unified,
+                                              UNIFIED_INDEX_0, UNIFIED_INDEX_1);
+      }
+      break;
+      CASE_SRCS_IN(1, 1, 1, 0) : {
+        auto *Unified = lowerShuffleVector_UnifyFromDifferentSrcs(Src1, Index2,
+                                                                  Src0, Index3);
+        T = lowerShuffleVector_TwoFromSameSrc(Src1, Index0, Index1, Unified,
+                                              UNIFIED_INDEX_0, UNIFIED_INDEX_1);
+      }
+      break;
+      CASE_SRCS_IN(1, 1, 1, 1) : {
+        T = lowerShuffleVector_AllFromSameSrc(Src1, Index0, Index1, Index2,
+                                              Index3);
+      }
+      break;
+#undef CASE_SRCS_IN
+    }
+
+    assert(T != nullptr);
+    assert(T->getType() == DestTy);
+    _movp(Dest, T);
+    return;
+  } break;
   }
 
   // Unoptimized shuffle. Perform a series of inserts and extracts.
   Context.insert<InstFakeDef>(T);
-  auto *Src0 = llvm::cast<Variable>(Instr->getSrc(0));
-  auto *Src1 = llvm::cast<Variable>(Instr->getSrc(1));
-  const SizeT NumElements = typeNumElements(DestTy);
   const Type ElementType = typeElementType(DestTy);
   for (SizeT I = 0; I < Instr->getNumIndexes(); ++I) {
     auto *Index = Instr->getIndex(I);
     const SizeT Elem = Index->getValue();
     auto *ExtElmt = makeReg(ElementType);
     if (Elem < NumElements) {
       lowerExtractElement(
           InstExtractElement::create(Func, ExtElmt, Src0, Index));
     } else {
       lowerExtractElement(InstExtractElement::create(
@@ skipping 1878 matching lines @@
         emitGlobal(*Var, SectionSuffix);
       }
     }
   } break;
   }
 }
 } // end of namespace X86NAMESPACE
 } // end of namespace Ice
 
 #endif // SUBZERO_SRC_ICETARGETLOWERINGX86BASEIMPL_H