[x86] Add a ZERO_EXTEND_VECTOR_INREG DAG node and use it when widening vector types to be legal and a ZERO_EXTEND node is encountered.

[chandlerc]

Summary

When we use widening to legalize vector types, extend nodes are a real
challenge. Either the input or output is likely to be legal, but in many
cases not both. As a consequence, we don't really have any way to
represent this situation and the prior code in the widening legalization
framework would just scalarize the extend operation completely.

This patch introduces a new DAG node to represent doing a zero extend of
a vector "in register". The core of the idea is to allow legal but
different vector types in the input and output. The output vector must
have fewer lanes but wider elements. The operation is defined to zero
extend the low elements of the input to the size of the output elements,
and drop all of the high elements which don't have a corresponding lane
in the output vector.

It also includes generic expansion of this node in terms of blending
a zero vector into the high elements of the vector and bitcasting
across. This in turn yields extremely nice code for x86 SSE2 when we use
the new widening legalization logic in conjunction with the new shuffle
lowering logic.

There is still more to do here. We need to support sign extension, any
extension, and potentially int-to-float conversions. My current plan is
to continue using similar synthetic nodes to model each of these
transitions with generic lowering code for each one.

However, with this patch LLVM already reaches performance parity with
GCC for the core C loops of the x264 code (assuming you disable the
hand-written assembly versions) when compiling for SSE2 and SSE3
architectures and enabling the new widening and lowering logic for
vectors.

[bkramer]

lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp

750 ↗

(On Diff #11113)

Can we get away with creating illegal shuffles here or should we ask the backend if the mask is legal first?

[arsenm]

lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp

750 ↗

(On Diff #11113)

I'm pretty sure this needs to be checked. I fixed a similar issue in http://reviews.llvm.org/D4320

[chandlerc]

lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp

750 ↗

(On Diff #11113)

I believe we can get away with this, but it's a bit dicey I agree.

First, to Matt's point -- we can *definitely* create illegal types here, i don't know whot D4320 is talking about. If you look at SelectionDAGISel::CodeGenAndEmitDAG, you'll see that we re-type-legalize after the vector operation legalization. There are also specific comments around the vector operation legalization that it is expected to at times produce illegal types.

What we can't do here is produce an illegal *vector* type which could then result in an illegal vector operation, which could then result in scalarization with an illegal scalar type. We won't get a chance to fix the scalarized version unless we produce it in this pass of the legalizer.

So the risk in the current approach is that I don't know if the legalizer correctly recurses on the newly created VECTOR_SHUFFLE node to legalize that operation. If it doesn't then we would need to recurse on it within VectorLegalizer. I'll check that.

[filcab]

LGTM after the legality check gets taken care of (either because we already check the resulting node or by recursing manually).

lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

2420 ↗

(On Diff #11113)

s/in the/is the/?

[grosbach]

LGTM too.

[nadav]

LGTM.

[hfinkel]

lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp

745 ↗

(On Diff #11113)

Is the big-endian case covered by one of the existing regression tests?

[chandlerc]

lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp

750 ↗

(On Diff #11113)

Just to close the loop, in LegalizeVectorOps.cpp:307-311 the code recurses over any legalized result node which differs from the original node, so returning an illegal VECTOR_SHUFFLE node (or even a bitcast of a VECTOR_SHUFFLE node, as LegalizeOp always recurses across operands) should always re-enter the vector operation legalization framework before we finish the phase of legalization. So essentially, this does appear to be a valid way of recursively delegating legalization from one node to another provided we don't end up with a cycle. If we do, it will show up as an infinite loop immediately, so I'm not too worried.

[chandlerc]

lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp

745 ↗

(On Diff #11113)

No, I'm not aware of any way to write a big-endian test case that even produces a ZERO_EXTEND_VECTOR_INREG node. Until there is wider usage of widening legalization on big-endian targets, it isn't really possible to test this code.

I'm going to commit this for now (as it is dead code on BE targets) and let me know if you'd rather turn this into an assert that BE isn't implemented so we remember to add a test, or any other approach for big-endian. Writing a test that covers it is trivial, its just the challenge of even reaching the code.

lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

2420 ↗

(On Diff #11113)

Done when committed.

[chandlerc]

Closed by commit rL212610 (authored by @chandlerc).

llvm/trunk/include/llvm/CodeGen/ISDOpcodes.h

enum NodeType {
 
     /// SIGN_EXTEND_INREG - This operator atomically performs a SHL/SRA pair to
     /// sign extend a small value in a large integer register (e.g. sign
     /// extending the low 8 bits of a 32-bit register to fill the top 24 bits
     /// with the 7th bit).  The size of the smaller type is indicated by the 1th
     /// operand, a ValueType node.
     SIGN_EXTEND_INREG,
 
+    /// ZERO_EXTEND_VECTOR_INREG(Vector) - This operator represents an
+    /// in-register zero-extension of the low lanes of an integer vector. The
+    /// result type must have fewer elements than the operand type, and those
+    /// elements must be larger integer types such that the total size of the
+    /// operand type and the result type match. Each of the low operand
+    /// elements is zero-extended into the corresponding, wider result
+    /// elements.
+    ZERO_EXTEND_VECTOR_INREG,
+
     /// FP_TO_[US]INT - Convert a floating point value to a signed or unsigned
     /// integer.
     FP_TO_SINT,
     FP_TO_UINT,
 
     /// X = FP_ROUND(Y, TRUNC) - Rounding 'Y' from a larger floating point type
     /// down to the precision of the destination VT.  TRUNC is a flag, which is
     /// always an integer that is zero or one.  If TRUNC is 0, this is a

llvm/trunk/include/llvm/CodeGen/SelectionDAG.h

#endif
   /// getZExtOrTrunc - Convert Op, which must be of integer type, to the
   /// integer type VT, by either zero-extending or truncating it.
   SDValue getZExtOrTrunc(SDValue Op, SDLoc DL, EVT VT);
 
   /// getZeroExtendInReg - Return the expression required to zero extend the Op
   /// value assuming it was the smaller SrcTy value.
   SDValue getZeroExtendInReg(SDValue Op, SDLoc DL, EVT SrcTy);
 
+  /// getZeroExtendVectorInReg - Return an operation which will zero extend the
+  /// low lanes of the operand into the specified vector type. For example,
+  /// this can convert a v16i8 into a v4i32 by zero extending the low four
+  /// lanes of the operand from i8 to i32.
+  SDValue getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT);
+
   /// getBoolExtOrTrunc - Convert Op, which must be of integer type, to the
   /// integer type VT, by using an extension appropriate for the target's
   /// BooleanContent or truncating it.
   SDValue getBoolExtOrTrunc(SDValue Op, SDLoc SL, EVT VT);
 
   /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
   SDValue getNOT(SDLoc DL, SDValue Val, EVT VT);
 

llvm/trunk/lib/CodeGen/SelectionDAG/LegalizeTypes.h

private:
   // Widen Vector Operand.
   bool WidenVectorOperand(SDNode *N, unsigned OpNo);
   SDValue WidenVecOp_BITCAST(SDNode *N);
   SDValue WidenVecOp_CONCAT_VECTORS(SDNode *N);
   SDValue WidenVecOp_EXTRACT_VECTOR_ELT(SDNode *N);
   SDValue WidenVecOp_EXTRACT_SUBVECTOR(SDNode *N);
   SDValue WidenVecOp_STORE(SDNode* N);
   SDValue WidenVecOp_SETCC(SDNode* N);
+  SDValue WidenVecOp_ZERO_EXTEND(SDNode *N);
 
   SDValue WidenVecOp_Convert(SDNode *N);
 
   //===--------------------------------------------------------------------===//
   // Vector Widening Utilities Support: LegalizeVectorTypes.cpp
   //===--------------------------------------------------------------------===//
 
   /// Helper GenWidenVectorLoads - Helper function to generate a set of

llvm/trunk/lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp

class VectorLegalizer {
   ///
   /// Implements expansion for UINT_TO_FLOAT; falls back to UnrollVectorOp if
   /// SINT_TO_FLOAT and SHR on vectors isn't legal.
   SDValue ExpandUINT_TO_FLOAT(SDValue Op);
 
   /// \brief Implement expansion for SIGN_EXTEND_INREG using SRL and SRA.
   SDValue ExpandSEXTINREG(SDValue Op);
 
+  /// \brief Implement expansion for ZERO_EXTEND_VECTOR_INREG.
+  ///
+  /// Shuffles the low lanes of the operand into place and blends zeros into
+  /// the remaining lanes, finally bitcasting to the proper type.
+  SDValue ExpandZERO_EXTEND_VECTOR_INREG(SDValue Op);
+
   /// \brief Expand bswap of vectors into a shuffle if legal.
   SDValue ExpandBSWAP(SDValue Op);
 
   /// \brief Implement vselect in terms of XOR, AND, OR when blend is not
   /// supported by the target.
   SDValue ExpandVSELECT(SDValue Op);
   SDValue ExpandSELECT(SDValue Op);
   SDValue ExpandLoad(SDValue Op);
SDValue VectorLegalizer::LegalizeOp(SDValue Op) {
   case ISD::FRINT:
   case ISD::FNEARBYINT:
   case ISD::FROUND:
   case ISD::FFLOOR:
   case ISD::FP_ROUND:
   case ISD::FP_EXTEND:
   case ISD::FMA:
   case ISD::SIGN_EXTEND_INREG:
+  case ISD::ZERO_EXTEND_VECTOR_INREG:
     QueryType = Node->getValueType(0);
     break;
   case ISD::FP_ROUND_INREG:
     QueryType = cast<VTSDNode>(Node->getOperand(1))->getVT();
     break;
   case ISD::SINT_TO_FP:
   case ISD::UINT_TO_FP:
     QueryType = Node->getOperand(0).getValueType();
SDValue VectorLegalizer::ExpandStore(SDValue Op) {
   AddLegalizedOperand(Op, TF);
   return TF;
 }
 
 SDValue VectorLegalizer::Expand(SDValue Op) {
   switch (Op->getOpcode()) {
   case ISD::SIGN_EXTEND_INREG:
     return ExpandSEXTINREG(Op);
+  case ISD::ZERO_EXTEND_VECTOR_INREG:
+    return ExpandZERO_EXTEND_VECTOR_INREG(Op);
   case ISD::BSWAP:
     return ExpandBSWAP(Op);
   case ISD::VSELECT:
     return ExpandVSELECT(Op);
   case ISD::SELECT:
     return ExpandSELECT(Op);
   case ISD::UINT_TO_FP:
     return ExpandUINT_TO_FLOAT(Op);
SDValue VectorLegalizer::ExpandSEXTINREG(SDValue Op) {
   unsigned OrigBW = OrigTy.getScalarType().getSizeInBits();
   SDValue ShiftSz = DAG.getConstant(BW - OrigBW, VT);
 
   Op = Op.getOperand(0);
   Op =   DAG.getNode(ISD::SHL, DL, VT, Op, ShiftSz);
   return DAG.getNode(ISD::SRA, DL, VT, Op, ShiftSz);
 }
 
+// Generically expand a vector zext in register to a shuffle of the relevant
+// lanes into the appropriate locations, a blend of zero into the high bits,
+// and a bitcast to the wider element type.
+SDValue VectorLegalizer::ExpandZERO_EXTEND_VECTOR_INREG(SDValue Op) {
+  SDLoc DL(Op);
+  EVT VT = Op.getValueType();
+  int NumElements = VT.getVectorNumElements();
+  SDValue Src = Op.getOperand(0);
+  EVT SrcVT = Src.getValueType();
+  int NumSrcElements = SrcVT.getVectorNumElements();
+
+  // Build up a zero vector to blend into this one.
+  EVT SrcScalarVT = SrcVT.getScalarType();
+  SDValue ScalarZero = DAG.getTargetConstant(0, SrcScalarVT);
+  SmallVector<SDValue, 4> BuildVectorOperands(NumSrcElements, ScalarZero);
+  SDValue Zero = DAG.getNode(ISD::BUILD_VECTOR, DL, SrcVT, BuildVectorOperands);
+
+  // Shuffle the incoming lanes into the correct position, and pull all other
+  // lanes from the zero vector.
+  SmallVector<int, 16> ShuffleMask;
+  ShuffleMask.reserve(NumSrcElements);
+  for (int i = 0; i < NumSrcElements; ++i)
+    ShuffleMask.push_back(i);
+
+  int ExtLaneScale = NumSrcElements / NumElements;
+  int EndianOffset = TLI.isBigEndian() ? ExtLaneScale - 1 : 0;
+  for (int i = 0; i < NumElements; ++i)
+    ShuffleMask[i * ExtLaneScale + EndianOffset] = NumSrcElements + i;
+
+  return DAG.getNode(ISD::BITCAST, DL, VT,
+                     DAG.getVectorShuffle(SrcVT, DL, Zero, Src, ShuffleMask));
+}
+
 SDValue VectorLegalizer::ExpandBSWAP(SDValue Op) {
   EVT VT = Op.getValueType();
 
   // Generate a byte wise shuffle mask for the BSWAP.
   SmallVector<int, 16> ShuffleMask;
   int ScalarSizeInBytes = VT.getScalarSizeInBits() / 8;
   for (int I = 0, E = VT.getVectorNumElements(); I != E; ++I)
     for (int J = ScalarSizeInBytes - 1; J >= 0; --J)

llvm/trunk/lib/CodeGen/SelectionDAG/LegalizeVectorTypes.cpp

#endif
     llvm_unreachable("Do not know how to widen this operator's operand!");
 
   case ISD::BITCAST:            Res = WidenVecOp_BITCAST(N); break;
   case ISD::CONCAT_VECTORS:     Res = WidenVecOp_CONCAT_VECTORS(N); break;
   case ISD::EXTRACT_SUBVECTOR:  Res = WidenVecOp_EXTRACT_SUBVECTOR(N); break;
   case ISD::EXTRACT_VECTOR_ELT: Res = WidenVecOp_EXTRACT_VECTOR_ELT(N); break;
   case ISD::STORE:              Res = WidenVecOp_STORE(N); break;
   case ISD::SETCC:              Res = WidenVecOp_SETCC(N); break;
+  case ISD::ZERO_EXTEND:        Res = WidenVecOp_ZERO_EXTEND(N); break;
 
   case ISD::FP_EXTEND:
   case ISD::FP_TO_SINT:
   case ISD::FP_TO_UINT:
   case ISD::SINT_TO_FP:
   case ISD::UINT_TO_FP:
   case ISD::TRUNCATE:
   case ISD::SIGN_EXTEND:
-  case ISD::ZERO_EXTEND:
   case ISD::ANY_EXTEND:
     Res = WidenVecOp_Convert(N);
     break;
   }
 
   // If Res is null, the sub-method took care of registering the result.
   if (!Res.getNode()) return false;
 
   // If the result is N, the sub-method updated N in place.  Tell the legalizer
   // core about this.
   if (Res.getNode() == N)
     return true;
 
 
   assert(Res.getValueType() == N->getValueType(0) && N->getNumValues() == 1 &&
          "Invalid operand expansion");
 
   ReplaceValueWith(SDValue(N, 0), Res);
   return false;
 }
 
+SDValue DAGTypeLegalizer::WidenVecOp_ZERO_EXTEND(SDNode *N) {
+  SDLoc DL(N);
+  EVT VT = N->getValueType(0);
+  unsigned NumElts = VT.getVectorNumElements();
+
+  SDValue InOp = N->getOperand(0);
+  // If some legalization strategy other than widening is used on the operand,
+  // we can't safely assume that just zero-extending the low lanes is the
+  // correct transformation.
+  if (getTypeAction(InOp.getValueType()) != TargetLowering::TypeWidenVector)
+    return WidenVecOp_Convert(N);
+  InOp = GetWidenedVector(InOp);
+  EVT InVT = InOp.getValueType();
+  assert(NumElts < InVT.getVectorNumElements() && "Input wasn't widened!");
+
+  // Use a special DAG node to represent the operation of zero extending the
+  // low lanes.
+  return DAG.getZeroExtendVectorInReg(InOp, DL, VT);
+}
+
 SDValue DAGTypeLegalizer::WidenVecOp_Convert(SDNode *N) {
   // Since the result is legal and the input is illegal, it is unlikely
   // that we can fix the input to a legal type so unroll the convert
   // into some scalar code and create a nasty build vector.
   EVT VT = N->getValueType(0);
   EVT EltVT = VT.getVectorElementType();
   SDLoc dl(N);
   unsigned NumElts = VT.getVectorNumElements();

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAG.cpp

SDValue SelectionDAG::getZeroExtendInReg(SDValue Op, SDLoc DL, EVT VT) {
   if (Op.getValueType() == VT) return Op;
   unsigned BitWidth = Op.getValueType().getScalarType().getSizeInBits();
   APInt Imm = APInt::getLowBitsSet(BitWidth,
                                    VT.getSizeInBits());
   return getNode(ISD::AND, DL, Op.getValueType(), Op,
                  getConstant(Imm, Op.getValueType()));
 }
 
+SDValue SelectionDAG::getZeroExtendVectorInReg(SDValue Op, SDLoc DL, EVT VT) {
+  assert(VT.isVector() && "This DAG node is restricted to vector types.");
+  assert(VT.getVectorNumElements() < Op.getValueType().getVectorNumElements() &&
+         "The destination vector type must have fewer lanes than the input.");
+  return getNode(ISD::ZERO_EXTEND_VECTOR_INREG, DL, VT, Op);
+}
+
 /// getNOT - Create a bitwise NOT operation as (XOR Val, -1).
 ///
 SDValue SelectionDAG::getNOT(SDLoc DL, SDValue Val, EVT VT) {
   EVT EltVT = VT.getScalarType();
   SDValue NegOne =
     getConstant(APInt::getAllOnesValue(EltVT.getSizeInBits()), VT);
   return getNode(ISD::XOR, DL, VT, Val, NegOne);
 }

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGDumper.cpp

#endif
   case ISD::SRA_PARTS:                  return "sra_parts";
   case ISD::SRL_PARTS:                  return "srl_parts";
 
   // Conversion operators.
   case ISD::SIGN_EXTEND:                return "sign_extend";
   case ISD::ZERO_EXTEND:                return "zero_extend";
   case ISD::ANY_EXTEND:                 return "any_extend";
   case ISD::SIGN_EXTEND_INREG:          return "sign_extend_inreg";
+  case ISD::ZERO_EXTEND_VECTOR_INREG:   return "zero_extend_vector_inreg";
   case ISD::TRUNCATE:                   return "truncate";
   case ISD::FP_ROUND:                   return "fp_round";
   case ISD::FLT_ROUNDS_:                return "flt_rounds";
   case ISD::FP_ROUND_INREG:             return "fp_round_inreg";
   case ISD::FP_EXTEND:                  return "fp_extend";
 
   case ISD::SINT_TO_FP:                 return "sint_to_fp";
   case ISD::UINT_TO_FP:                 return "uint_to_fp";

llvm/trunk/lib/Target/X86/X86ISelLowering.cpp

for (int i = MVT::FIRST_VECTOR_VALUETYPE;
     setOperationAction(ISD::FP_TO_UINT, VT, Expand);
     setOperationAction(ISD::FP_TO_SINT, VT, Expand);
     setOperationAction(ISD::UINT_TO_FP, VT, Expand);
     setOperationAction(ISD::SINT_TO_FP, VT, Expand);
     setOperationAction(ISD::SIGN_EXTEND_INREG, VT,Expand);
     setOperationAction(ISD::TRUNCATE, VT, Expand);
     setOperationAction(ISD::SIGN_EXTEND, VT, Expand);
     setOperationAction(ISD::ZERO_EXTEND, VT, Expand);
+    setOperationAction(ISD::ZERO_EXTEND_VECTOR_INREG, VT, Expand);
     setOperationAction(ISD::ANY_EXTEND, VT, Expand);
     setOperationAction(ISD::VSELECT, VT, Expand);
     setOperationAction(ISD::SELECT_CC, VT, Expand);
     for (int InnerVT = MVT::FIRST_VECTOR_VALUETYPE;
              InnerVT <= MVT::LAST_VECTOR_VALUETYPE; ++InnerVT)
       setTruncStoreAction(VT,
                           (MVT::SimpleValueType)InnerVT, Expand);
     setLoadExtAction(ISD::SEXTLOAD, VT, Expand);

llvm/trunk/test/CodeGen/X86/widen_conversions.ll

+; RUN: llc < %s -mcpu=x86-64 -x86-experimental-vector-widening-legalization -x86-experimental-vector-shuffle-lowering | FileCheck %s
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-unknown"
+
+define <4 x i32> @zext_v4i8_to_v4i32(<4 x i8>* %ptr) {
+; CHECK-LABEL: zext_v4i8_to_v4i32:
+; 
+; CHECK:      movd (%{{.*}}), %[[X:xmm[0-9]+]]
+; CHECK-NEXT: pxor %[[Z:xmm[0-9]+]], %[[Z]]
+; CHECK-NEXT: punpcklbw %[[Z]], %[[X]]
+; CHECK-NEXT: punpcklbw %[[Z]], %[[X]]
+; CHECK-NEXT: ret
+
+  %val = load <4 x i8>* %ptr
+  %ext = zext <4 x i8> %val to <4 x i32>
+  ret <4 x i32> %ext
+}