+/// \brief Try to lower a vector shuffle as a bit shift (shifts in zeros).
+///
+/// Attempts to match a shuffle mask against the PSRL(W/D/Q) and PSLL(W/D/Q)
+/// SSE2 and AVX2 logical bit-shift instructions. The function matches
+/// elements from one of the input vectors shuffled to the left or right
+/// with zeroable elements 'shifted in'.
+static SDValue lowerVectorShuffleAsBitShift(SDLoc DL, MVT VT, SDValue V1,
+ SDValue V2, ArrayRef<int> Mask,
+ SelectionDAG &DAG) {
+ SmallBitVector Zeroable = computeZeroableShuffleElements(Mask, V1, V2);
+
+ int Size = Mask.size();
+ assert(Size == (int)VT.getVectorNumElements() && "Unexpected mask size");
+
+ // PSRL : (little-endian) right bit shift.
+ // [ 1, zz, 3, zz]
+ // [ -1, -1, 7, zz]
+ // PSHL : (little-endian) left bit shift.
+ // [ zz, 0, zz, 2 ]
+ // [ -1, 4, zz, -1 ]
+ auto MatchBitShift = [&](int Shift, int Scale) -> SDValue {
+ MVT ShiftSVT = MVT::getIntegerVT(VT.getScalarSizeInBits() * Scale);
+ MVT ShiftVT = MVT::getVectorVT(ShiftSVT, Size / Scale);
+ assert(DAG.getTargetLoweringInfo().isTypeLegal(ShiftVT) &&
+ "Illegal integer vector type");
+
+ bool MatchLeft = true, MatchRight = true;
+ for (int i = 0; i != Size; i += Scale) {
+ for (int j = 0; j != Shift; j++) {
+ MatchLeft &= Zeroable[i + j];
+ }
+ for (int j = Scale - Shift; j != Scale; j++) {
+ MatchRight &= Zeroable[i + j];
+ }
+ }
+ if (!(MatchLeft || MatchRight))
+ return SDValue();
+
+ bool MatchV1 = true, MatchV2 = true;
+ for (int i = 0; i != Size; i += Scale) {
+ unsigned Pos = MatchLeft ? i + Shift : i;
+ unsigned Low = MatchLeft ? i : i + Shift;
+ unsigned Len = Scale - Shift;
+ MatchV1 &= isSequentialOrUndefInRange(Mask, Pos, Len, Low);
+ MatchV2 &= isSequentialOrUndefInRange(Mask, Pos, Len, Low + Size);
+ }
+ if (!(MatchV1 || MatchV2))
+ return SDValue();
+
+ // Cast the inputs to ShiftVT to match VSRLI/VSHLI and back again.
+ unsigned OpCode = MatchLeft ? X86ISD::VSHLI : X86ISD::VSRLI;
+ int ShiftAmt = Shift * VT.getScalarSizeInBits();
+ SDValue V = MatchV1 ? V1 : V2;
+ V = DAG.getNode(ISD::BITCAST, DL, ShiftVT, V);
+ V = DAG.getNode(OpCode, DL, ShiftVT, V, DAG.getConstant(ShiftAmt, MVT::i8));
+ return DAG.getNode(ISD::BITCAST, DL, VT, V);
+ };
+
+ // SSE/AVX supports logical shifts up to 64-bit integers - so we can just
+ // keep doubling the size of the integer elements up to that. We can
+ // then shift the elements of the integer vector by whole multiples of
+ // their width within the elements of the larger integer vector. Test each
+ // multiple to see if we can find a match with the moved element indices
+ // and that the shifted in elements are all zeroable.
+ for (int Scale = 2; Scale * VT.getScalarSizeInBits() <= 64; Scale *= 2)
+ for (int Shift = 1; Shift != Scale; Shift++)
+ if (SDValue BitShift = MatchBitShift(Shift, Scale))
+ return BitShift;
+
+ // no match
+ return SDValue();
+}
+