Types inference in tblgen: Multiple exceptions

Hi all,

I am writing a back-end for a processor that has complex type registers. It has two functional units to perform complex multiplications.
From clang, I emulate a complex multiplication using vectors and, at the IR, I got this tblgen-friendly pattern (real component) :

(set RARegs:$dst, (insertelt RARegs:$src,
           (i16 (trunc (add
            (ncmul
             (sext (i16 (extractelt RARegs:$a, imm))),
             (sext (i16 (extractelt RARegs:$b, imm)))
             ),
            (ncmul
             (sext (i16 (extractelt RARegs:$a, imm))),
             (sext (i16 (extractelt RARegs:$b, imm)))
            )
            ))),
           imm) )

where RARegs is a register class of type [i32, v2i16]. I want to match that pattern in order to have one instruction which takes 2 vectors (complex numbers) and gives me another vector. Unfortunately, I am running into multiple tblgen type inference exceptions. I am new to llvm codegen.

First of all, I realized that I need to explicitly cast intermediate i16 type results because they are not supported by the architecture, is it right?
For example, if I do not cast extractelt's node type I get the following error when I run tblgen with -gen-instr-info:

llvm[3]: Building Meph.td instruction information with tblgen
llvm-tblgen: llvm/include/llvm/ADT/SmallVector.h:150: T& llvm::SmallVectorTemplateCommon<T>::operator[](unsigned int) [with T = llvm::MVT::SimpleValueType]: Assertion `begin() + idx < end()' failed.

which comes from utils/TableGen/CodeGenDAGPatterns.cpp:450:

   for (unsigned i = 1, e = Other.TypeVec.size(); i != e; ++i)
     if (isInteger(Other.TypeVec[i]) && Other.TypeVec[i] > LargestInt)
       LargestInt = Other.TypeVec[i];

but Other.TypeVec is empty throwing an exception when accessing Other.TypeVec[1].

As far as I know, tblgen analyzes sext node and tries to infer operand types by applying the specified type constraints of the node. The 2nd type constraint of sext enforces extractelt to be scalar and extractelt gets i32:v2i16 types (legal types or RARegs types). After that, it tries to apply the 3rd type constraint (SDTCisOpSmallerThanOp) and it reaches the abnormal condition I shown.

I presume this is a bug in tblgen, should not it verify that TypeVec is empty before entering the loop ?

Casting intermediate i16 type results, I manage to generate instruction information but it throws another exception when generating the instruction selector :-(.

vtInt: (vt:Other)<<P:Predicate_vtInt>>
Type constraint application shouldn't fail!

Looking again into the code, tblgen does not take into account the explicit casts when generating the instruction selector (RemoveAllTypes -> InferPossibleTypes) so it gets stuck earlier into the pattern (insertelt-trunc). insertelt enforces trunc to be scalar and I have the same situation as before. Do you know how can I solve this problem ?
If it is either not possible or too hard, how should I proceed to detect the pattern ?

Ivan

Hi all,

I am writing a back-end for a processor that has complex type registers.
It has two functional units to perform complex multiplications.
From clang, I emulate a complex multiplication using vectors and, at
the IR, I got this tblgen-friendly pattern (real component) :

(set RARegs:$dst, (insertelt RARegs:$src,
(i16 (trunc (add
(ncmul
(sext (i16 (extractelt RARegs:$a, imm))),
(sext (i16 (extractelt RARegs:$b, imm)))
),
(ncmul
(sext (i16 (extractelt RARegs:$a, imm))),
(sext (i16 (extractelt RARegs:$b, imm)))
)
))),
imm) )

where RARegs is a register class of type [i32, v2i16]. I want to match
that pattern in order to have one instruction which takes 2 vectors
(complex numbers) and gives me another vector. Unfortunately, I am
running into multiple tblgen type inference exceptions. I am new to llvm
codegen.

First of all, I realized that I need to explicitly cast intermediate i16
type results because they are not supported by the architecture, is it
right?
For example, if I do not cast extractelt's node type I get the following
error when I run tblgen with -gen-instr-info:

llvm[3]: Building Meph.td instruction information with tblgen
llvm-tblgen: llvm/include/llvm/ADT/SmallVector.h:150: T&
llvm::SmallVectorTemplateCommon<T>::operator[](unsigned int) [with T =
llvm::MVT::SimpleValueType]: Assertion `begin() + idx < end()' failed.

which comes from utils/TableGen/CodeGenDAGPatterns.cpp:450:

for (unsigned i = 1, e = Other.TypeVec.size(); i != e; ++i)
if (isInteger(Other.TypeVec[i]) && Other.TypeVec[i] > LargestInt)
LargestInt = Other.TypeVec[i];

but Other.TypeVec is empty throwing an exception when accessing
Other.TypeVec[1].

As far as I know, tblgen analyzes sext node and tries to infer operand
types by applying the specified type constraints of the node. The 2nd
type constraint of sext enforces extractelt to be scalar and extractelt
gets i32:v2i16 types (legal types or RARegs types). After that, it tries
to apply the 3rd type constraint (SDTCisOpSmallerThanOp) and it reaches
the abnormal condition I shown.

I presume this is a bug in tblgen, should not it verify that TypeVec is
empty before entering the loop ?

If TableGen crashes, it's a bug.

Casting intermediate i16 type results, I manage to generate instruction
information but it throws another exception when generating the
instruction selector :-(.

vtInt: (vt:Other)<<P:Predicate_vtInt>>
Type constraint application shouldn't fail!

Looking again into the code, tblgen does not take into account the
explicit casts when generating the instruction selector (RemoveAllTypes
-> InferPossibleTypes) so it gets stuck earlier into the pattern
(insertelt-trunc). insertelt enforces trunc to be scalar and I have the
same situation as before. Do you know how can I solve this problem ?
If it is either not possible or too hard, how should I proceed to detect
the pattern ?

Your email doesn't really make one thing clear: does your architecture
have i16 registers?

-Eli

Hi Eli,
Thanks for your response. Please see my responses below.

Hi all,

I am writing a back-end for a processor that has complex type registers.
It has two functional units to perform complex multiplications.
  From clang, I emulate a complex multiplication using vectors and, at
the IR, I got this tblgen-friendly pattern (real component) :

(set RARegs:$dst, (insertelt RARegs:$src,
           (i16 (trunc (add
            (ncmul
             (sext (i16 (extractelt RARegs:$a, imm))),
             (sext (i16 (extractelt RARegs:$b, imm)))
             ),
            (ncmul
             (sext (i16 (extractelt RARegs:$a, imm))),
             (sext (i16 (extractelt RARegs:$b, imm)))
            )
            ))),
           imm) )

where RARegs is a register class of type [i32, v2i16]. I want to match
that pattern in order to have one instruction which takes 2 vectors
(complex numbers) and gives me another vector. Unfortunately, I am
running into multiple tblgen type inference exceptions. I am new to llvm
codegen.

First of all, I realized that I need to explicitly cast intermediate i16
type results because they are not supported by the architecture, is it
right?
For example, if I do not cast extractelt's node type I get the following
error when I run tblgen with -gen-instr-info:

llvm[3]: Building Meph.td instruction information with tblgen
llvm-tblgen: llvm/include/llvm/ADT/SmallVector.h:150: T&
llvm::SmallVectorTemplateCommon<T>::operator[](unsigned int) [with T =
llvm::MVT::SimpleValueType]: Assertion `begin() + idx< end()' failed.

which comes from utils/TableGen/CodeGenDAGPatterns.cpp:450:

   for (unsigned i = 1, e = Other.TypeVec.size(); i != e; ++i)
     if (isInteger(Other.TypeVec[i])&& Other.TypeVec[i]> LargestInt)
       LargestInt = Other.TypeVec[i];

but Other.TypeVec is empty throwing an exception when accessing
Other.TypeVec[1].

As far as I know, tblgen analyzes sext node and tries to infer operand
types by applying the specified type constraints of the node. The 2nd
type constraint of sext enforces extractelt to be scalar and extractelt
gets i32:v2i16 types (legal types or RARegs types). After that, it tries
to apply the 3rd type constraint (SDTCisOpSmallerThanOp) and it reaches
the abnormal condition I shown.

I presume this is a bug in tblgen, should not it verify that TypeVec is
empty before entering the loop ?

If TableGen crashes, it's a bug.

Yes, it crashes.

Casting intermediate i16 type results, I manage to generate instruction
information but it throws another exception when generating the
instruction selector :-(.

vtInt: (vt:Other)<<P:Predicate_vtInt>>
Type constraint application shouldn't fail!

Looking again into the code, tblgen does not take into account the
explicit casts when generating the instruction selector (RemoveAllTypes
-> InferPossibleTypes) so it gets stuck earlier into the pattern
(insertelt-trunc). insertelt enforces trunc to be scalar and I have the
same situation as before. Do you know how can I solve this problem ?
If it is either not possible or too hard, how should I proceed to detect
the pattern ?

Your email doesn't really make one thing clear: does your architecture
have i16 registers?

No, my architecture does not support i16 type.

Hi Eli,
Thanks for your response. Please see my responses below.

Hi all,

I am writing a back-end for a processor that has complex type registers.
It has two functional units to perform complex multiplications.
From clang, I emulate a complex multiplication using vectors and, at
the IR, I got this tblgen-friendly pattern (real component) :

(set RARegs:$dst, (insertelt RARegs:$src,
          (i16 (trunc (add
           (ncmul
            (sext (i16 (extractelt RARegs:$a, imm))),
            (sext (i16 (extractelt RARegs:$b, imm)))
            ),
           (ncmul
            (sext (i16 (extractelt RARegs:$a, imm))),
            (sext (i16 (extractelt RARegs:$b, imm)))
           )
           ))),
          imm) )

where RARegs is a register class of type [i32, v2i16]. I want to match
that pattern in order to have one instruction which takes 2 vectors
(complex numbers) and gives me another vector. Unfortunately, I am
running into multiple tblgen type inference exceptions. I am new to llvm
codegen.

First of all, I realized that I need to explicitly cast intermediate i16
type results because they are not supported by the architecture, is it
right?
For example, if I do not cast extractelt's node type I get the following
error when I run tblgen with -gen-instr-info:

llvm[3]: Building Meph.td instruction information with tblgen
llvm-tblgen: llvm/include/llvm/ADT/SmallVector.h:150: T&
llvm::SmallVectorTemplateCommon<T>::operator[](unsigned int) [with T =
llvm::MVT::SimpleValueType]: Assertion `begin() + idx< end()' failed.

which comes from utils/TableGen/CodeGenDAGPatterns.cpp:450:

  for (unsigned i = 1, e = Other.TypeVec.size(); i != e; ++i)
    if (isInteger(Other.TypeVec[i])&& Other.TypeVec[i]> LargestInt)
      LargestInt = Other.TypeVec[i];

but Other.TypeVec is empty throwing an exception when accessing
Other.TypeVec[1].

As far as I know, tblgen analyzes sext node and tries to infer operand
types by applying the specified type constraints of the node. The 2nd
type constraint of sext enforces extractelt to be scalar and extractelt
gets i32:v2i16 types (legal types or RARegs types). After that, it tries
to apply the 3rd type constraint (SDTCisOpSmallerThanOp) and it reaches
the abnormal condition I shown.

I presume this is a bug in tblgen, should not it verify that TypeVec is
empty before entering the loop ?

If TableGen crashes, it's a bug.

Yes, it crashes.

There are an unfortunately large number of places in tablegen where assert() has been used when a user level diagnostic was appropriate. We've been fixing them, but haven't gotten them all yet. Can you file a bugzilla? Obviously a small testcase would be great, but if it's indeed an assertion failure, even just the backtrace from that would be very helpful.

Thanks!
  Jim

Strictly speaking, tblgen will crash in release builds because it triggers an assertion failure.

Then I don't think this pattern will ever match anyway; there won't be
any nodes of i16 type to match.

You might be able to fix the error by writing "(set RARegs:$dst,
(v2i16 (insertelt RARegs:$src," to explicitly note the result type of
the insertelt. TableGen generally isn't very smart about figuring out
types, so explicitly writing out the types of every node can help.

-Eli

Hi Eli,
Thanks for your response. Please see my responses below.

Hi all,

I am writing a back-end for a processor that has complex type registers.
It has two functional units to perform complex multiplications.
  From clang, I emulate a complex multiplication using vectors and, at
the IR, I got this tblgen-friendly pattern (real component) :

(set RARegs:$dst, (insertelt RARegs:$src,
           (i16 (trunc (add
            (ncmul
             (sext (i16 (extractelt RARegs:$a, imm))),
             (sext (i16 (extractelt RARegs:$b, imm)))
             ),
            (ncmul
             (sext (i16 (extractelt RARegs:$a, imm))),
             (sext (i16 (extractelt RARegs:$b, imm)))
            )
            ))),
           imm) )

where RARegs is a register class of type [i32, v2i16]. I want to match
that pattern in order to have one instruction which takes 2 vectors
(complex numbers) and gives me another vector. Unfortunately, I am
running into multiple tblgen type inference exceptions. I am new to llvm
codegen.

First of all, I realized that I need to explicitly cast intermediate i16
type results because they are not supported by the architecture, is it
right?
For example, if I do not cast extractelt's node type I get the following
error when I run tblgen with -gen-instr-info:

llvm[3]: Building Meph.td instruction information with tblgen
llvm-tblgen: llvm/include/llvm/ADT/SmallVector.h:150: T&
llvm::SmallVectorTemplateCommon<T>::operator[](unsigned int) [with T =
llvm::MVT::SimpleValueType]: Assertion `begin() + idx< end()' failed.

which comes from utils/TableGen/CodeGenDAGPatterns.cpp:450:

   for (unsigned i = 1, e = Other.TypeVec.size(); i != e; ++i)
     if (isInteger(Other.TypeVec[i])&& Other.TypeVec[i]> LargestInt)
       LargestInt = Other.TypeVec[i];

but Other.TypeVec is empty throwing an exception when accessing
Other.TypeVec[1].

As far as I know, tblgen analyzes sext node and tries to infer operand
types by applying the specified type constraints of the node. The 2nd
type constraint of sext enforces extractelt to be scalar and extractelt
gets i32:v2i16 types (legal types or RARegs types). After that, it tries
to apply the 3rd type constraint (SDTCisOpSmallerThanOp) and it reaches
the abnormal condition I shown.

I presume this is a bug in tblgen, should not it verify that TypeVec is
empty before entering the loop ?

If TableGen crashes, it's a bug.

Yes, it crashes.

There are an unfortunately large number of places in tablegen where assert() has been used when a user level diagnostic was appropriate. We've been fixing them, but haven't gotten them all yet. Can you file a bugzilla? Obviously a small testcase would be great, but if it's indeed an assertion failure, even just the backtrace from that would be very helpful.

Thanks!
   Jim

Hello Jim,

I've submitted the bug, its ID is 11529.

Hi Eli,
Thanks for your response. Please see my responses below.

Hi all,

I am writing a back-end for a processor that has complex type registers.
It has two functional units to perform complex multiplications.
  From clang, I emulate a complex multiplication using vectors and, at
the IR, I got this tblgen-friendly pattern (real component) :

(set RARegs:$dst, (insertelt RARegs:$src,
           (i16 (trunc (add
            (ncmul
             (sext (i16 (extractelt RARegs:$a, imm))),
             (sext (i16 (extractelt RARegs:$b, imm)))
             ),
            (ncmul
             (sext (i16 (extractelt RARegs:$a, imm))),
             (sext (i16 (extractelt RARegs:$b, imm)))
            )
            ))),
           imm) )

where RARegs is a register class of type [i32, v2i16]. I want to match
that pattern in order to have one instruction which takes 2 vectors
(complex numbers) and gives me another vector. Unfortunately, I am
running into multiple tblgen type inference exceptions. I am new to llvm
codegen.

First of all, I realized that I need to explicitly cast intermediate i16
type results because they are not supported by the architecture, is it
right?
For example, if I do not cast extractelt's node type I get the following
error when I run tblgen with -gen-instr-info:

llvm[3]: Building Meph.td instruction information with tblgen
llvm-tblgen: llvm/include/llvm/ADT/SmallVector.h:150: T&
llvm::SmallVectorTemplateCommon<T>::operator[](unsigned int) [with T =
llvm::MVT::SimpleValueType]: Assertion `begin() + idx< end()' failed.

which comes from utils/TableGen/CodeGenDAGPatterns.cpp:450:

   for (unsigned i = 1, e = Other.TypeVec.size(); i != e; ++i)
     if (isInteger(Other.TypeVec[i])&& Other.TypeVec[i]> LargestInt)

       LargestInt = Other.TypeVec[i];

but Other.TypeVec is empty throwing an exception when accessing
Other.TypeVec[1].

As far as I know, tblgen analyzes sext node and tries to infer operand
types by applying the specified type constraints of the node. The 2nd
type constraint of sext enforces extractelt to be scalar and extractelt
gets i32:v2i16 types (legal types or RARegs types). After that, it tries
to apply the 3rd type constraint (SDTCisOpSmallerThanOp) and it reaches
the abnormal condition I shown.

I presume this is a bug in tblgen, should not it verify that TypeVec is
empty before entering the loop ?

If TableGen crashes, it's a bug.

Yes, it crashes.

Casting intermediate i16 type results, I manage to generate instruction
information but it throws another exception when generating the
instruction selector :-(.

vtInt: (vt:Other)<<P:Predicate_vtInt>>
Type constraint application shouldn't fail!

Looking again into the code, tblgen does not take into account the
explicit casts when generating the instruction selector (RemoveAllTypes
-> InferPossibleTypes) so it gets stuck earlier into the pattern
(insertelt-trunc). insertelt enforces trunc to be scalar and I have the
same situation as before. Do you know how can I solve this problem ?
If it is either not possible or too hard, how should I proceed to detect
the pattern ?

Your email doesn't really make one thing clear: does your architecture
have i16 registers?

No, my architecture does not support i16 type.

Then I don't think this pattern will ever match anyway; there won't be
any nodes of i16 type to match.

The fact is that those i16 nodes are intermediate results that I wanted to mask into one machine instruction. No operand is needed for them.

You might be able to fix the error by writing "(set RARegs:$dst,
(v2i16 (insertelt RARegs:$src," to explicitly note the result type of
the insertelt. TableGen generally isn't very smart about figuring out
types, so explicitly writing out the types of every node can help.

It is exactly what I did for i16 results. But it seems that, in order to generate the ISel, tblgen removes all types in patterns (even those that I explicitly enforced by casting) and then tries to re-infer them. This does not happen in the process of instr-info generation.
I think I am missing something regarding the general idea of tblgen pattern matching but if I am not wrong, all patterns with intermediate type results that are not supported by the architecture are forbidden. Is it correct?

Hi Eli,
Thanks for your response. Please see my responses below.

Hi all,

I am writing a back-end for a processor that has complex type
registers.
It has two functional units to perform complex multiplications.
From clang, I emulate a complex multiplication using vectors and, at
the IR, I got this tblgen-friendly pattern (real component) :

(set RARegs:$dst, (insertelt RARegs:$src,
(i16 (trunc (add
(ncmul
(sext (i16 (extractelt RARegs:$a, imm))),
(sext (i16 (extractelt RARegs:$b, imm)))
),
(ncmul
(sext (i16 (extractelt RARegs:$a, imm))),
(sext (i16 (extractelt RARegs:$b, imm)))
)
))),
imm) )

where RARegs is a register class of type [i32, v2i16]. I want to match
that pattern in order to have one instruction which takes 2 vectors
(complex numbers) and gives me another vector. Unfortunately, I am
running into multiple tblgen type inference exceptions. I am new to
llvm
codegen.

First of all, I realized that I need to explicitly cast intermediate
i16
type results because they are not supported by the architecture, is it
right?
For example, if I do not cast extractelt's node type I get the
following
error when I run tblgen with -gen-instr-info:

llvm[3]: Building Meph.td instruction information with tblgen
llvm-tblgen: llvm/include/llvm/ADT/SmallVector.h:150: T&
llvm::SmallVectorTemplateCommon<T>::operator[](unsigned int) [with T =
llvm::MVT::SimpleValueType]: Assertion `begin() + idx< end()'
failed.

which comes from utils/TableGen/CodeGenDAGPatterns.cpp:450:

for (unsigned i = 1, e = Other.TypeVec.size(); i != e; ++i)
if (isInteger(Other.TypeVec[i])&& Other.TypeVec[i]>
LargestInt)

  LargestInt = Other\.TypeVec\[i\];

but Other.TypeVec is empty throwing an exception when accessing
Other.TypeVec[1].

As far as I know, tblgen analyzes sext node and tries to infer operand
types by applying the specified type constraints of the node. The 2nd
type constraint of sext enforces extractelt to be scalar and extractelt
gets i32:v2i16 types (legal types or RARegs types). After that, it
tries
to apply the 3rd type constraint (SDTCisOpSmallerThanOp) and it reaches
the abnormal condition I shown.

I presume this is a bug in tblgen, should not it verify that TypeVec is
empty before entering the loop ?

If TableGen crashes, it's a bug.

Yes, it crashes.

Casting intermediate i16 type results, I manage to generate instruction
information but it throws another exception when generating the
instruction selector :-(.

vtInt: (vt:Other)<<P:Predicate_vtInt>>
Type constraint application shouldn't fail!

Looking again into the code, tblgen does not take into account the
explicit casts when generating the instruction selector (RemoveAllTypes
-> InferPossibleTypes) so it gets stuck earlier into the pattern
(insertelt-trunc). insertelt enforces trunc to be scalar and I have the
same situation as before. Do you know how can I solve this problem ?
If it is either not possible or too hard, how should I proceed to
detect
the pattern ?

Your email doesn't really make one thing clear: does your architecture
have i16 registers?

No, my architecture does not support i16 type.

Then I don't think this pattern will ever match anyway; there won't be
any nodes of i16 type to match.

The fact is that those i16 nodes are intermediate results that I wanted to
mask into one machine instruction. No operand is needed for them.

You might be able to fix the error by writing "(set RARegs:$dst,
(v2i16 (insertelt RARegs:$src," to explicitly note the result type of
the insertelt. TableGen generally isn't very smart about figuring out
types, so explicitly writing out the types of every node can help.

It is exactly what I did for i16 results. But it seems that, in order to
generate the ISel, tblgen removes all types in patterns (even those that I
explicitly enforced by casting) and then tries to re-infer them. This does
not happen in the process of instr-info generation.

Okay; I'm not really an expert on this stuff.

I think I am missing something regarding the general idea of tblgen pattern
matching but if I am not wrong, all patterns with intermediate type results
that are not supported by the architecture are forbidden. Is it correct?

Fundamentally ISel does matching after legalization, which will
transform an EXTRACT_VECTOR_ELT with an illegal result (like i16, for
your architecture) into one with a legal result (like i32, for your
architecture). Therefore the pattern won't match. Not sure whether
that would cause a TableGen error, though.

-Eli