How to interpret Selection DAG error output

Rail_Shafigulin · February 18, 2016, 6:43pm

I recently had to change some DAG patterns for my target. Conceptually I understand what DAG patterns are and what is their purpose, however given that I have quite vague understanding about how to LLVM implements and specifies them, naturally I got an error. Here it is

Here is the error:

LLVM ERROR: Cannot select: 0x3284268: glue = EsenciaISD::SET_FLAG 0x3283608, 0x3283710, 0x3283e48 [ORD=3] [ID=11]
0x3283608: i32,ch = CopyFromReg 0x3257980, 0x3283500 [ORD=1] [ID=9]
0x3283500: i32 = Register %vreg5 [ID=1]
0x3283710: i32 = Constant<3> [ID=2]
0x3283e48: i32 = Constant<20> [ID=8]
In function: fib

As far as I can understand LLVM cannot select it because the pattern is not specified. Unfortunately for me, I can’t understand how to interpret this output. Would anybody be able to help me out?

Any help is appreciated.

Krzysztof_Parzyszek · February 18, 2016, 6:50pm

The DAG node that has failed selection is "SET_FLAG %vreg5, 3, 20", the type of the node is "glue" and all 3 arguments are i32.

The top line shows the node that caused the failure. The hex numbers on that line are the addresses of the arguments. These arguments are then listed below.

Newer versions of LLVM show node ids instead of addresses, but AFAIK it was dependent on some configuration option.

-Krzysztof

Rail_Shafigulin · February 18, 2016, 7:10pm

Thanks for the explanation. Do you know what ORD and ID mean?

Rail_Shafigulin · February 18, 2016, 7:19pm

LLVM ERROR: Cannot select: 0x3284268: glue = EsenciaISD::SET_FLAG
0x3283608, 0x3283710, 0x3283e48 [ORD=3] [ID=11]
   0x3283608: i32,ch = CopyFromReg 0x3257980, 0x3283500 [ORD=1] [ID=9]
     0x3283500: i32 = Register %vreg5 [ID=1]
   0x3283710: i32 = Constant<3> [ID=2]
   0x3283e48: i32 = Constant<20> [ID=8]
In function: fib

As far as I can understand LLVM cannot select it because the pattern is
not specified. Unfortunately for me, I can't understand how to interpret
this output. Would anybody be able to help me out?

The DAG node that has failed selection is "SET_FLAG %vreg5, 3, 20", the
type of the node is "glue" and all 3 arguments are i32.

I understand where SET_FLAG, 3 and 20 come from, but how did you arrive the
conclusion that %vreg5 should be part of the pattern?

jroelofs · February 18, 2016, 7:22pm

        LLVM ERROR: Cannot select: 0x3284268: glue = EsenciaISD::SET_FLAG
        0x3283608, 0x3283710, 0x3283e48 [ORD=3] [ID=11]
            0x3283608: i32,ch = CopyFromReg 0x3257980, 0x3283500 [ORD=1]
        [ID=9]
              0x3283500: i32 = Register %vreg5 [ID=1]
            0x3283710: i32 = Constant<3> [ID=2]
            0x3283e48: i32 = Constant<20> [ID=8]
        In function: fib

        As far as I can understand LLVM cannot select it because the
        pattern is
        not specified. Unfortunately for me, I can't understand how to
        interpret
        this output. Would anybody be able to help me out?

    The DAG node that has failed selection is "SET_FLAG %vreg5, 3, 20",
    the type of the node is "glue" and all 3 arguments are i32.

I understand where SET_FLAG, 3 and 20 come from, but how did you arrive
the conclusion that %vreg5 should be part of the pattern?

The hex numbers are pointers. You can see the Use of 0x3283500 in the CopyFromReg inst, and the def is here:

0x3283500: i32 = Register %vreg5 [ID=1]

It's /just/ a dag.

Jon

Krzysztof_Parzyszek · February 18, 2016, 7:29pm

ID is a node id. ORD is related to the original instruction ordering, but I don't know what the implications of these numbers are. SDNode scheduling most likely uses them, but I don't know the details.

-Krzysztof

Krzysztof_Parzyszek · February 18, 2016, 7:30pm

The vreg5 is an argument to the CopyFromReg, which is an argument to the original SET_FLAG.

-Krzysztof

Rail_Shafigulin · February 18, 2016, 7:32pm

        LLVM ERROR: Cannot select: 0x3284268: glue = EsenciaISD::SET_FLAG
        0x3283608, 0x3283710, 0x3283e48 [ORD=3] [ID=11]
            0x3283608: i32,ch = CopyFromReg 0x3257980, 0x3283500 [ORD=1]
        [ID=9]
              0x3283500: i32 = Register %vreg5 [ID=1]
            0x3283710: i32 = Constant<3> [ID=2]
            0x3283e48: i32 = Constant<20> [ID=8]
        In function: fib

        As far as I can understand LLVM cannot select it because the
        pattern is
        not specified. Unfortunately for me, I can't understand how to
        interpret
        this output. Would anybody be able to help me out?

    The DAG node that has failed selection is "SET_FLAG %vreg5, 3, 20",
    the type of the node is "glue" and all 3 arguments are i32.

I understand where SET_FLAG, 3 and 20 come from, but how did you arrive
the conclusion that %vreg5 should be part of the pattern?

The hex numbers are pointers. You can see the Use of 0x3283500 in the
CopyFromReg inst, and the def is here:

0x3283500: i32 = Register %vreg5 [ID=1]

I think this is where I'm loosing the "thread". Based on what I'm seeing
SET_FLAG has three operands, the first of which is a CopyFromReg. So how
come the pattern is SET_FLAG %vreg5, 3, 20 and not SET_FLAG CopyFromReg, 3,
20? In other words how do we go from CopyFromReg to %vreg5?

Krzysztof_Parzyszek · February 18, 2016, 7:34pm

CopyFromReg is a "helper" instruction meaning "use the value from this vreg". Values that are live across basic blocks are remembered in vregs, and CopyToReg and CopyFromReg are opcodes used to express it.

-Krzysztof

Rail_Shafigulin · February 18, 2016, 7:40pm

I think this is where I'm loosing the "thread". Based on what I'm seeing
SET_FLAG has three operands, the first of which is a CopyFromReg. So how
come the pattern is SET_FLAG %vreg5, 3, 20 and not SET_FLAG CopyFromReg,
3, 20? In other words how do we go from CopyFromReg to %vreg5?

CopyFromReg is a "helper" instruction meaning "use the value from this
vreg". Values that are live across basic blocks are remembered in vregs,
and CopyToReg and CopyFromReg are opcodes used to express it.

I see. Thanks.

          0x3283608: i32,ch = CopyFromReg 0x3257980, 0x3283500 [ORD=1]
        [ID=9]
              0x3283500: i32 = Register %vreg5 [ID=1]

Based on the code above, CopyFromReg is a node at address 0x3283608,
returns i32, is of type chain and takes two inputs, the second of which is
a %vreg5. So what is the first parameter? In fact where can I find the
definition of CopyFromReg method?

jroelofs · February 18, 2016, 7:42pm

                 LLVM ERROR: Cannot select: 0x3284268: glue =
        EsenciaISD::SET_FLAG
                 0x3283608, 0x3283710, 0x3283e48 [ORD=3] [ID=11]
                     0x3283608: i32,ch = CopyFromReg 0x3257980,
        0x3283500 [ORD=1]
                 [ID=9]
                       0x3283500: i32 = Register %vreg5 [ID=1]
                     0x3283710: i32 = Constant<3> [ID=2]
                     0x3283e48: i32 = Constant<20> [ID=8]
                 In function: fib

                 As far as I can understand LLVM cannot select it
        because the
                 pattern is
                 not specified. Unfortunately for me, I can't understand
        how to
                 interpret
                 this output. Would anybody be able to help me out?

             The DAG node that has failed selection is "SET_FLAG %vreg5,
        3, 20",
             the type of the node is "glue" and all 3 arguments are i32.

        I understand where SET_FLAG, 3 and 20 come from, but how did you
        arrive
        the conclusion that %vreg5 should be part of the pattern?

    The hex numbers are pointers. You can see the Use of 0x3283500 in
    the CopyFromReg inst, and the def is here:

    0x3283500: i32 = Register %vreg5 [ID=1]

I think this is where I'm loosing the "thread". Based on what I'm seeing
SET_FLAG has three operands, the first of which is a CopyFromReg.

Yes.

So how come the pattern is SET_FLAG %vreg5, 3, 20 and not SET_FLAG
CopyFromReg, 3, 20?

Because it's not... the latter is a better way of understanding it. The former is incorrect.

In other words how do we go from CopyFromReg to %vreg5?

Written imperatively, the DAG from the dump you pasted is:

  something = dunno
  reg = i32 Register %vreg5 [ID=1]
  cpy = i32,ch CopyFromReg something, reg [ORD=1]
  c1 = i32 Constant<3> [ID=2]
  c2 = i32 Constant<20> [ID=8]
  foo = EsenciaISD::SET_FLAG cpy, c1, c2 [ORD=3] [ID=11]

where:

  something is 0x3257980
  reg is 0x3283500
  c1 is 0x3283710
  c2 is 0x3283e48
  foo is 0x3283608

These are just names I made up... the names don't actually exist as I've written them, but maybe that'll help your understanding?

This imperative order doesn't really exist either. Because it's a DAG, and the DAG isn't necessarily flattened like that... could be flattened in many different ways.

Jon

Krzysztof_Parzyszek · February 18, 2016, 7:48pm

The first parameter is a chain.

Here are some comments from include/llvm/CodeGen/ISDOpcodes.h:

     /// CopyToReg - This node has three operands: a chain, a register number to
     /// set to this value, and a value.
     CopyToReg,

     /// CopyFromReg - This node indicates that the input value is a virtual or
     /// physical register that is defined outside of the scope of this
     /// SelectionDAG. The register is available from the RegisterSDNode object.
     CopyFromReg,

I usually grep the sources if I want to find out about something. I'm not sure if there is a better documentation about ISD nodes.

-Krzysztof

Rail_Shafigulin · February 18, 2016, 8:18pm

           0x3283608: i32,ch = CopyFromReg 0x3257980, 0x3283500 [ORD=1]
         [ID=9]
               0x3283500: i32 = Register %vreg5 [ID=1]

Based on the code above, CopyFromReg is a node at address 0x3283608,
returns i32, is of type chain and takes two inputs, the second of which
is a %vreg5. So what is the first parameter? In fact where can I find
the definition of CopyFromReg method?

The first parameter is a chain.

Here are some comments from include/llvm/CodeGen/ISDOpcodes.h:

    /// CopyToReg - This node has three operands: a chain, a register
number to
    /// set to this value, and a value.
    CopyToReg,

    /// CopyFromReg - This node indicates that the input value is a
virtual or
    /// physical register that is defined outside of the scope of this
    /// SelectionDAG. The register is available from the RegisterSDNode
object.
    CopyFromReg,

I usually grep the sources if I want to find out about something. I'm not
sure if there is a better documentation about ISD nodes.

Thanks. I keep forgetting that I have grep at my disposal What I'm not
clear about is the first parameter in CopyFromReg node. 0x3283608: i32,ch
= CopyFromReg 0x3257980, 0x3283500 [ORD=1]. Based on the comments for
CopyFromReg, if I understand it correctly, there should be 1 input, virtual
or physical register, which is what is given in the pattern as a second
argument. So what is the first one. What does it do?

Krzysztof_Parzyszek · February 18, 2016, 8:20pm

It's a chain, it's used to maintain relative ordering between nodes. Both CopyToReg and CopyFromReg have the same arguments. I agree, it's not clear from the comments.

-Krzysztof

Rail_Shafigulin · February 18, 2016, 9:30pm

Thanks. I keep forgetting that I have grep at my disposal What I'm
not clear about is the first parameter in CopyFromReg node. 0x3283608:
i32,ch = CopyFromReg 0x3257980, 0x3283500 [ORD=1]. Based on the comments
for CopyFromReg, if I understand it correctly, there should be 1 input,
virtual or physical register, which is what is given in the pattern as a
second argument. So what is the first one. What does it do?

It's a chain, it's used to maintain relative ordering between nodes. Both
CopyToReg and CopyFromReg have the same arguments. I agree, it's not clear
from the comments.

Thanks for the explanation.

David_Chisnall3 · February 19, 2016, 12:26pm

You’ve had a few answers already, but just to add one more:

SelectionDAG has a viewGraph family of methods, that will dump a .dot file and open it with GraphViz. These can be run from the debugger and produce *much* more readable output. When I’m debugging, I generally stick a breakpoint on the code that’s triggering this error and get the pretty picture to try to figure out what’s going on. It’s a lot easier to understand for nontrivial examples.

David