Doubts

Hello sir,

I'm having some problems understading how llvm works. I'm following a concrete example and visualizing the DAG and the .s output and some stuff doesn´t seem to match.

I sorry to bother you but I don´t know where I can expose my doubts and I wonder if you could redirect me to some discussion place where someone might help me.

Thanks,
Patosga

Hi Patosga,

Most of the documentation for LLVM is here: http://llvm.org/docs/

I'm not sure exactly where the problem is, so it's hard to know what
you're looking for, but two documents that can shed some light are:

http://llvm.org/docs/WritingAnLLVMBackend.html#instruction-selector

http://llvm.org/docs/CodeGenerator.html

Maybe you'll be able to progress after reading them, and if you have
more concrete problems, trying to describe them in more details can
help people help you. :slight_smile:

cheers,
--renato

Hi Patosga,

You are on the right place to ask your questions and get help!

Try to be more specific with your problem. We need some details to help you =)

Pierre

Sorry, glad I’m in the right place.

Before I start, I want to state that I’m a beginer and I’m trying to develop a backend by adapting an existent target to my platform.

My first doubt is about the SelectionDAG and the TargetLowering class. When I use, for example:

setOperationAction(ISD::ADD, MVT::i1, Promote);

Is it correct to say that I’m promoting any operand used by the ISD::ADD node to a larger type? If so, what would that value type be?

If I use the same function with the expand as the third argument like below:
setOperationAction(ISD::FSIN, MVT::f32, Expand);
What will the expansion look like, since I don´t provide any custom implementation of the node? Also, what is the meaning of the MVT::f32 in this case?

Thanks,

Patosga``

Hi Patosga,

you can control what type the operands are promoted to as follows:
AddPromotedToType (ISD::ADD, MVT::i1, MVT::i64);

Thanks, indeed it was on the LegalizeDAG.cpp and the information proved very useful.

I also realized that the customization, promotion or expansion will occur whenever any operand, with the same type as the type specified on the second argument (MVT) of setOperationAction function, appears. (Correct me if I’m wrong).

The second doubt I have regards instruction matching.

When I define a pattern such as:
[(set i32:$dst, (add (mul i32:$src1, i32:$src2), i32:$src3))]>

What is the meaning of the word “set” or “store” which appear quite often?

From what I can understand this pattern is only interest in an add node with a mul node as one operator and an immediate as the other.

Does the “set” (keyword?) translates to an output of the add node, or just another node?

Thanks,

Patosga

It is not a keyword. It is a node defined in include/llvm/Target/TargetSelectionDAG.td. You can likely find most of the definitions you’re wondering about there.

In terms of its purpose, perhaps someone can elaborate on that a bit more, but there is no corresponding ISD node for this and the way I look at it is that its purpose is to help Tbl-gen infer the result type of the node (in this case the “add” node). For example, you may have an instruction that adds two i32’s and produces an i64 and then another one that produces an i32 (I know this is kind of contrived in the case of addition, but you get the point). The DAGs would look identical except that the set node would have a different type.
However, I may be wrong about this.

Of course, “store” is quite different. That is a full fledged node and has fairly straightforward semantics - it’s a store node. So for example a DAG that looks like:
(store i64:$src, addr:$dst)

actually says store the 64-bit integer $src at address $dst.

Nemanja

It is not a keyword. It is a node defined in
include/llvm/Target/TargetSelectionDAG.td. You can likely find most of the
definitions you're wondering about there.
In terms of its purpose, perhaps someone can elaborate on that a bit more,
but there is no corresponding ISD node for this and the way I look at it is
that its purpose is to help Tbl-gen infer the result type of the node (in
this case the "add" node). For example, you may have an instruction that
adds two i32's and produces an i64 and then another one that produces an i32
(I know this is kind of contrived in the case of addition, but you get the
point). The DAGs would look identical except that the set node would have a
different type.
However, I may be wrong about this.

To elaborate a little: "set" is for more than just type inference.

It's the operator used to "set" registers (the first operands) to
given values (the last operand, usually a DAG).
It's a special node that doesn't map to an ISD opcode because it
represents something that isn't in the SelectionDAG: instruction-level
(as opposed to block live-ins/-outs) virtual registers.

Another way to think about it is that, roughly, each SDValue maps to a
vreg, and "set" does the association between SDValues produced by an
SDNode, and vregs produced by the selected instruction.

It can set multiple registers (if the last operand produces multiple
values). For instance, X86 has things like "[(set GR32:$dst, EFLAGS,
(X86add_flag GR32:$src1, GR32:$src2))]"

Patterns can't have a root node with a non-void return, because, how
would we decide where the return value goes?
So, you can basically write two kinds of patterns:
- (set <register class>:$dst, <operand>)
- (<void-typed operator> <operands>)

"store" is really just the most common case of the second kind: since
it's an operator that doesn't produce any value and has type "void",
it can be used to form a root node in the pattern DAG.

The third most common kind of root operator is probably void-returning
intrinsics (look for "[(int_").
There's also another special operator, "implicit", which is necessary
because a pattern for an instruction X should define all registers
that X defines, even if the definition isn't something we're matching
in the SelectionDAG (that's what makes it implicit).

HTH,
-Ahmed

Hello Ahmed,

Thanks for your explanation. While very clarifying, your response created a lot of questions in my mind.

I could not understand what you meant by:

“It’s the operator used to “set” registers (the first operands) to
given values (the last operand, usually a DAG).”

Should I be thinking in terms of basic blocks where multiple operands create a SelectionDAG and produce a result for example? Or maybe think about the union of SDNodes to form MachineInstr by pattern matching?

When you presented the following pattern: “[(set GR32:$dst, EFLAGS, (X86add_flag GR32:$src1, GR32:$src2))]” you made me realize that maybe I don’t fully understand pattern matching. I know that pattern matching uses the SelectionDAG with SDNodes and produces a SelectionDAG of MachineInstr, but when you use registers as operands in a pattern what does it mean? I believe the first DAG, before instruction selection, is kind of register agnostic exept for the RegisterSDNode. By that logic, you only could VTs and not Registers, although they are widely used.

Regarding pattern’s syntax, you can have various outputs, which number depend on the last operand being matched, but only one operand, I’m I correct?

Thanks a lot for the detailed explanation.

(Also, if you could redirect me to more information about block live-ins/-outs I would be most grateful.)

Hello Ahmed,

Thanks for your explanation. While very clarifying, your response created a
lot of questions in my mind.

I could not understand what you meant by:

"It's the operator used to "set" registers (the first operands) to
given values (the last operand, usually a DAG)."

Should I be thinking in terms of basic blocks where multiple operands create
a SelectionDAG and produce a result for example? Or maybe think about the
union of SDNodes to form MachineInstr by pattern matching?

Oh, no, sorry: here, "DAG" refers to the TableGen "dag" construct, the
stuff you write in parentheses. The "operator" is the first part of a
dag.

What I mean by "usually a DAG" is that it's obviously more common to
have a dag child:
  (set GR32:$dst, (add ...))
instead of a leaf child like:
  (set GR32:$dst, 123)
or:
  (set GR32:$dst, GR32:$src)

When you presented the following pattern: "[(set GR32:$dst, EFLAGS,
(X86add_flag GR32:$src1, GR32:$src2))]" you made me realize that maybe I
don't fully understand pattern matching. I know that pattern matching uses
the SelectionDAG with SDNodes and produces a SelectionDAG of MachineInstr,
but when you use registers as operands in a pattern what does it mean? I
believe the first DAG, before instruction selection, is kind of register
agnostic exept for the RegisterSDNode. By that logic, you only could VTs and
not Registers, although they are widely used.

Yes, we're not matching registers, only VTs. But the pattern is used
for more than matching, it's also used for transforming one
representation (SDNodes) into another (MachineInstr) via an
intermediate (MachineSDNode).

"GR32" is actually redundant in that example. The interesting part is
the name of each operand ("$dst"), which is what determines the order
of the MachineOperands on the final MachineInstr (it also determines
the order of the results/operands (for ops in "outs" and "ins") of the
MachineSDNode).

In theory, I think even the types are unnecessary, and you should be
able to write patterns with just operand names ("(set $dst, ...)"),
but that's not currently accepted by tablegen.

Regarding pattern's syntax, you can have various outputs, which number
depend on the last operand being matched, but only one operand, I'm I
correct?

Correct.

Thanks a lot for the detailed explanation.

(Also, if you could redirect me to more information about block
live-ins/-outs I would be most grateful.)

Eh, unfortunately, none of this is very well documented; you might
have some luck with the comments and code in SelectionDAGBuilder,
FunctionLoweringInfo, and MachineBasicBlock.

-Ahmed