Vector promotion broken for <2 x [i8|i16]>

Vector promotion which is new in LLVM 3.1 is broken for sub32 bit types. The problem is in the VectorLegalizer::PromoteVectorOp.

The function getTypeToPromoteTo will return a <2 x i32> for a <2 x i8>, <2 x i16> or <4 x i8>. The problem is that there are no vectors of size 1 defined for i32 or i16. The attached patch fixes these issues.

This can be reproduced by setting in any target:

setOperationAction(ISD::AND, MVT::i8, Promote);

setOperationAction(ISD::AND, MVT::v2i8, Promote);

setOperationAction(ISD::AND, MVT::i16, Promote);

Let me know if this is good,

Micah

codegen_new_vec1_types.patch (10.3 KB)

I think that you attached the wrong patch. The attached patch is the one which adds the new MVT types.

No, that is correct. I am adding the new types so that I can bitcast v2i8 into a v1i16 and then perform the ‘and’ operation and have legalize types turn the v1i16 into a scalar.

Though I am having trouble in understanding how x86 supports the <1 x i64> type. Based on looking at the code, it should fail because v1i64 is not supported on the x86 platform as far as I can tell.

Micah

Though I am having trouble in understanding how x86 supports the <1 x i64> type. Based on looking at the code, it should fail because v1i64 is not supported on the x86 platform as >far as I can tell.

The Type-Legalizer can handle vector types in the following ways:
1. Split - this splits vectors into two halves. For example on SSE4, <4 x i64> is split to <2 x i64>
2. Widen - this methods adds additional vector elements, but keeps the element type. For example <3 x float> is legalized to <4 x float>
3. Promote - this method widens each element in the vector. For example SSE masks are promoted from <4 x i1> to <4 x i32>
4. Scalarize - this method coverts vectors with a single element into a scalar. For example, <1 x i64> into i64.

The function getTypeToPromoteTo will return a <2 x i32> for a <2 x i8>, <2 x i16> or <4 x i8>.

The first two conversions look correct, and I assume that your target declares v2i32 as a legal type. I am not sure how <4 x i8> got there. Maybe it was first split, and after that promoted ?

Sorry, <4 x i8> should convert to a <1 x i32>. What currently is happening is that it is returning a <2 x i32> because <1 x i32> does not exist.

Micah

I don't know how your target architecture looks like, but I suspect that <4 x i8> should not be legalized to <1 x i32>. I think that what you are seeing is that <4 x i8> is first split into <2 x i8>, and later promoted to <2 x i32>. At the moment different targets can only affect type-legalization by declaring different legal types. A number of us discussed the possibility of allowing different targets to override the decisions for different types. But at the moment this is only a plan.

Hrmm.... PromoteVectorOp doesn't seem to follow this at all.
http://llvm.org/svn/llvm-project/llvm/trunk/lib/CodeGen/SelectionDAG/LegalizeVectorOps.cpp
SDValue VectorLegalizer::PromoteVectorOp(SDValue Op) {
  // Vector "promotion" is basically just bitcasting and doing the operation
  // in a different type. For example, x86 promotes ISD::AND on v2i32 to
  // v1i64.
  EVT VT = Op.getValueType();
  assert(Op.getNode()->getNumValues() == 1 &&
         "Can't promote a vector with multiple results!");
  EVT NVT = TLI.getTypeToPromoteTo(Op.getOpcode(), VT);
  DebugLoc dl = Op.getDebugLoc();
  SmallVector<SDValue, 4> Operands(Op.getNumOperands());

  for (unsigned j = 0; j != Op.getNumOperands(); ++j) {
    if (Op.getOperand(j).getValueType().isVector())
      Operands[j] = DAG.getNode(ISD::BITCAST, dl, NVT, Op.getOperand(j));
    else
      Operands[j] = Op.getOperand(j);
  }

  Op = DAG.getNode(Op.getOpcode(), dl, NVT, &Operands[0], Operands.size());

  return DAG.getNode(ISD::BITCAST, dl, VT, Op);
}

The input Op is <4 x i8> = and <4 x i8>, <4 x i8>.
The result of TLI.getTypeToPromoteTo(ISD::AND, MVT::v4i8) is MVT::v2i32;

The reason why this occurs is:
// See if this has an explicit type specified.
    std::map<std::pair<unsigned, MVT::SimpleValueType>,
             MVT::SimpleValueType>::const_iterator PTTI =
      PromoteToType.find(std::make_pair(Op, VT.getSimpleVT().SimpleTy));
    if (PTTI != PromoteToType.end()) return PTTI->second;

    assert((VT.isInteger() || VT.isFloatingPoint()) &&
           "Cannot autopromote this type, add it with AddPromotedToType.");

    EVT NVT = VT;
    do {
      NVT = (MVT::SimpleValueType)(NVT.getSimpleVT().SimpleTy+1);
      assert(NVT.isInteger() == VT.isInteger() && NVT != MVT::isVoid &&
             "Didn't find type to promote to!");
    } while (!isTypeLegal(NVT) ||
              getOperationAction(Op, NVT) == Promote);

The first line in the do while loop is important, it just increments the type, starting at MVT::v4i8 until it hits a legal type.

This seems broken to me.
Here is what TOT LLVM has for its MVT list:
v4i8 = 14, // 4 x i8
      v8i8 = 15, // 8 x i8
      v16i8 = 16, // 16 x i8
      v32i8 = 17, // 32 x i8
      v2i16 = 18, // 2 x i16
      v4i16 = 19, // 4 x i16
      v8i16 = 20, // 8 x i16
      v16i16 = 21, // 16 x i16
      v2i32 = 22, // 2 x i32

So, for my platform with the 'and' I promote all i8 and i16 types, so the first type that is legal is v2i32.

If I add the v1i32 then it works, however, it breaks when I added v1i16(which I need for the v2i8 case).

So I set AddPromotedType(ISD::AND, MVT::v4i8, MVT::v1i32) to get around it. So it seems in this case someone has
hit this issue before and added the ability to override promotion rules.

Notice that PromoteVectorOp is called after the type legalization legalized all of the types in the program. It legalizes the *operations*, not the types. So, you should only see legal types (Legal types are types that fit into your registers). So, if your target has v2i32, I suspect that v4i8 is an illegal because it has a different size.

v4i8 itself is a legal type, just not on the 'AND' operation.

So there seems to be multiple problems here.
1) PromoteVectorOp doesn't handle the case where the types are not the same size, this occurs because #2
2) getTypeToPromoteTo doesn't actual check to see if the type it should promote to makes any sense.
3) PromoteVectorOp also doesn't handle the case where getTypeToPromoteTo returns an invalid type.

Micah

If v4i8 is a legal type then getTypeToPromoteTo should return the pair v4i8 and 'legal'. This looks like the root of the problem.

I'm not so sure, the code never checks if v4i8 is legal and it shouldn't as that is the type we want to convert away from. The problem here is v4i8 is legal, but v4i8 on an ISD::AND node is not and I want v4i8 on ISD::AND to be promoted to anything larger. Currently the code doesn't seem to do what it should based on our email chain.

So to summarize, what the code should do is find the smallest vector type that is larger than the current type and perform the operation on that type with the proper extension/truncation afterwards. What the code currently does is find the next value type that is legal and performs a bitcast to that type, performs the operand on the type and then bitcasts back. This doesn't work if the two types are of different sizes. Since this occurs after legalize type, my approach about adding v1xi[16|32] won't work since those types are illegal.

What would you think is the best way to fix this?

Micah

"Villmow, Micah" <Micah.Villmow@amd.com> writes:

Sorry, <4 x i8> should convert to a <1 x i32>.

Why? I'm really confused.

Shouldn't this converts to a <4 x i32>?

                               -Dave

The comments in the code state it should do bitcast, op, then bitcast, not extend, op and truncate.

"SDValue VectorLegalizer::PromoteVectorOp(SDValue Op) {
  // Vector "promotion" is basically just bitcasting and doing the operation
  // in a different type. For example, x86 promotes ISD::AND on v2i32 to
  // v1i64."

So following the same logic <4 x i8> bitcasts into a <1 x i32> and then does the ISD::AND and then bitcasts back to <1 x i32>.

Micah

"Villmow, Micah" <Micah.Villmow@amd.com> writes:

The comments in the code state it should do bitcast, op, then bitcast,
not extend, op and truncate.

"SDValue VectorLegalizer::PromoteVectorOp(SDValue Op) {
  // Vector "promotion" is basically just bitcasting and doing the operation
  // in a different type. For example, x86 promotes ISD::AND on v2i32 to
  // v1i64."

So following the same logic <4 x i8> bitcasts into a <1 x i32> and
then does the ISD::AND and then bitcasts back to <1 x i32>.

Ok, I thought we were talking about type promotion during legalization.
Nadav explained it well too.

These names are really confusing. :frowning: I would find it helpful to have
different names for bitcasting vs. true promotion as legalize defines
it. Maybe "coercion" for the bitcast meaning?

                             -Dave

Micah,

I think that your patch is missing the necessary modifications in
lib/VMCore/ValueTypes.cpp to EVT::getEVTString() and
EVT::getTypeForEVT.

-Hal

Ahh yep, thanks for catching that, new patch attached.

codegen_new_vec1_types.patch (11.7 KB)

Micah,

One more thing :wink: -- llvm::getEnumName
in utils/TableGen/CodeGenTarget.cpp

-Hal

Ok will resubmit it tomorrow, the patch is on my other machine. I'll fix this location for the <16x[i32|i64> also since I missed this spot with my last patch. Way too many locations for this information.

Micah

Updated patch attached.

codegen_new_vec1_types.patch (12.9 KB)