Inserting nodes into SelectionDAG (X86)

Project Infrastructure LLVM Dev List Archives
1

Greetings,

I am rather new to LLVM, so please excuse my limited knowledge about it.

Currently I am trying to modify the X86TargetLowering::LowerCALL method by
inserting additional instructions before the call.
As far as I understand, nodes are created by calling the getNode method on
the DAG. If, for example, I insert the following code

  Ops.push_back(Chain);
  Chain = DAG.getNode(ISD::TRAP, DAG.getVTList(MVT::Other), &Ops[0],
Ops.size());

then an X86 instruction (namely ud2) appears in the output files compiled by
llc.
So, is my understanding correct that
1) the Chain determines the ordering of the nodes?
2) the second parameter is a set of return types, i. e. in my example,
MVT::Other says that a Chain object will be returned?

Now, as soon as I try to generate more complex instructions, I get lost.
Say, I want to insert the following instruction

  mov eax, 42

then the best I can come up with is

  Ops.push_back(Chain);
  Ops.push_back(DAG.getRegister(X86::EAX, MVT::i32));
  Ops.push_back(DAG.getConstant(42, MVT::i32));
  Chain = DAG.getNode(X86::MOV32ri, DAG.getVTList(MVT::Other), &Ops[0],
Ops.size());

But there are a few problems:
3) It seems I am not allowed to use concrete X86 instructions here (at least
that's what I think llc's error message "cannot yet select" could mean). Is
there an appropriate instruction in ISD? I can't find it...
4) Do I get the parameter passing right? Fooling around with other
expressions suggests that I get it wrong.
5) What exactly is the meaning of further result types? If I get the new
Chain object back, are the other results inside?

Could you help me out?

Sincerely,
Artjom Kochtchi

2

Greetings,

I am rather new to LLVM, so please excuse my limited knowledge about it.

Currently I am trying to modify the X86TargetLowering::LowerCALL method by
inserting additional instructions before the call.
As far as I understand, nodes are created by calling the getNode method on
the DAG. If, for example, I insert the following code

Ops.push_back(Chain);
Chain = DAG.getNode(ISD::TRAP, DAG.getVTList(MVT::Other), &Ops[0],
Ops.size());

then an X86 instruction (namely ud2) appears in the output files compiled by
llc.
So, is my understanding correct that
1) the Chain determines the ordering of the nodes?

Yes.

2) the second parameter is a set of return types, i. e. in my example,
MVT::Other says that a Chain object will be returned?'

Yes.

Now, as soon as I try to generate more complex instructions, I get lost.
Say, I want to insert the following instruction

mov eax, 42

then the best I can come up with is

Ops.push_back(Chain);
Ops.push_back(DAG.getRegister(X86::EAX, MVT::i32));
Ops.push_back(DAG.getConstant(42, MVT::i32));
Chain = DAG.getNode(X86::MOV32ri, DAG.getVTList(MVT::Other), &Ops[0],
Ops.size());

But there are a few problems:
3) It seems I am not allowed to use concrete X86 instructions here (at least
that's what I think llc's error message "cannot yet select" could mean). Is
there an appropriate instruction in ISD? I can't find it...

Yes. It seems the opcode you want here is ISD::CopyToReg.

4) Do I get the parameter passing right? Fooling around with other
expressions suggests that I get it wrong.

It looks like you have the right idea. For CopyToReg nodes,
there's a special getCopyToReg accessor for convenience.

5) What exactly is the meaning of further result types? If I get the new
Chain object back, are the other results inside?

SDNodes may have multiple results. For example, a LOAD node
has two results: the Chain that indicates ordering with
respect to other operations which may modify memory, and
the actual loaded value. Individual results of an SDNode
are identified with SDValue objects.

Dan

3

Thank you for your help.

I think I managed to create the instruction I wanted:

  // mov eax, 41
  Chain = DAG.getCopyToReg(Chain, DAG.getRegister(X86::EAX, MVT::i32),
DAG.getConstant(41, MVT::i32), InFlag);
  InFlag = Chain.getValue(1);

I don't understand though what InFlag is for. As I read the code, it even
remains uninitialized when first passed to some node creation method.

Unfortunately I still don't manage to create more sophisticated error free
instructions that actually appear in the assembly generated by llc. For
example after the CopyToReg instruction, I want to increase eax by 1. In X86
'inc eax' would probably be the way to go, which I try to model by ISD 'addc
eax, eax, 1' or something of that sort (it's probably rather 'addc eax, 1').

I've tried all sorts of combinations and ordering of operands I could come
up with, but I seem to be missing the point. This is the most complete
version:

  // inc eax
  Ops.push_back(Chain);
  Ops.push_back(DAG.getRegister(X86::EAX, MVT::i32)); // rather without
target register?
  Ops.push_back(DAG.getRegister(X86::EAX, MVT::i32));
  Ops.push_back(DAG.getConstant(1, MVT::i32));
  Ops.push_back(InFlag);
  Chain = DAG.getNode(ISD::ADDC, DAG.getVTList(MVT::Other, MVT::Flag),
&Ops[0], Ops.size());
  InFlag = Chain.getValue(1);

Usually, llc quits with the error message
llc: SelectionDAG.cpp:4417: llvm::SDValue
llvm::SelectionDAG::UpdateNodeOperands(llvm::SDValue, llvm::SDValue,
llvm::SDValue): Assertion `N->getNumOperands() == 2 && "Update with wrong
number of operands"' failed.
Omiting the target register or switching operand order seems not to change
anything.

I'd really appreciate your help on this.
Artjom

4

Thank you for your help.

I think I managed to create the instruction I wanted:

// mov eax, 41
Chain = DAG.getCopyToReg(Chain, DAG.getRegister(X86::EAX, MVT::i32),
DAG.getConstant(41, MVT::i32), InFlag);
InFlag = Chain.getValue(1);

I don't understand though what InFlag is for. As I read the code, it even
remains uninitialized when first passed to some node creation method.

Flag operands in SelectionDAG are special. SelectionDAG currently
requires Flag operands for copies to and from physical registers,
though not for virtual registers.

Unfortunately I still don't manage to create more sophisticated error free
instructions that actually appear in the assembly generated by llc. For
example after the CopyToReg instruction, I want to increase eax by 1. In X86
'inc eax' would probably be the way to go, which I try to model by ISD 'addc
eax, eax, 1' or something of that sort (it's probably rather 'addc eax, 1').

ADDC is add-with-carry. If you just want to add 1 to EAX and don't care
about the carry result, ADD is easier. The result type of ADD is just
MVT::i32 (assuming you're working with i32 operands).

Dan

5

Sorry to ask again, but I still can't get it right.

The following code compiles and runs, but produces no instructions:
  Ops.push_back(DAG.getRegister(X86::EAX, MVT::i32));
  Ops.push_back(DAG.getConstant(1, MVT::i32));
  DAG.getNode(ISD::ADD, DAG.getVTList(MVT::i32), &Ops[0], Ops.size());

I reckon that has something to do with the fact that I am not using the
Chain object. But as soon as I try to chain that node, llc tells me that I
have the wrong number of operands:
  Ops.push_back(Chain);
  Ops.push_back(DAG.getRegister(X86::EAX, MVT::i32));
  Ops.push_back(DAG.getConstant(1, MVT::i32));
  Chain = DAG.getNode(ISD::ADD, DAG.getVTList(MVT::Other, MVT::i32),
&Ops[0], Ops.size());

Isn't that the way how it is supposed to work?

Artjom

6

Sorry to ask again, but I still can't get it right.

The following code compiles and runs, but produces no instructions:
Ops.push_back(DAG.getRegister(X86::EAX, MVT::i32));
Ops.push_back(DAG.getConstant(1, MVT::i32));
DAG.getNode(ISD::ADD, DAG.getVTList(MVT::i32), &Ops[0], Ops.size());

To read the value of a physical register, a CopyFromReg node is
needed.

I reckon that has something to do with the fact that I am not using the
Chain object. But as soon as I try to chain that node, llc tells me that I
have the wrong number of operands:
Ops.push_back(Chain);
Ops.push_back(DAG.getRegister(X86::EAX, MVT::i32));
Ops.push_back(DAG.getConstant(1, MVT::i32));
Chain = DAG.getNode(ISD::ADD, DAG.getVTList(MVT::Other, MVT::i32),
&Ops[0], Ops.size());

Isn't that the way how it is supposed to work?

ADD does not use a chain, so there's no chain operand, or
MVT::Other result for it in an ADD node.

Dan

7

You might want to look at SelectionDAGNodes.h, that has some (informal) description of what operands and results the nodes have.

8

Thanks to your help I've actually made some progress... Especially the
SelectionDAGNodes.h was a good hint.

But there are still some things that I can't figure out:
  // 'mov eax, 41'
  Chain = DAG.getCopyToReg(Chain, DAG.getRegister(X86::EAX, MVT::i32),
DAG.getConstant(41, MVT::i32), InFlag);
  InFlag = Chain.getValue(1);

  // 'inc eax'
  SDValue eaxVal = DAG.getCopyFromReg(Chain, X86::EAX, MVT::i32);
  SDValue inc = DAG.getNode(ISD::ADD, MVT::i32, eaxVal, DAG.getConstant(1,
MVT::i32));
  InFlag = SDValue();
  Chain = DAG.getCopyToReg(Chain, DAG.getRegister(X86::EAX, MVT::i32), inc,
InFlag);
  InFlag = Chain.getValue(1);

This code produces the following assembly instructions:
  movl $41, %eax
  movl $41, %eax
  incl %eax

I guess that's because what I want to become 'incl %eax' actually becomes
'movl $41, %eax' for the first parameter for the ADD-node and 'incl %eax'
for the second.

So in order to fix this problem, I tried:
  SDValue inc = DAG.getNode(ISD::ADD, MVT::i32, DAG.getConstant(41,
MVT::i32) DAG.getConstant(1, MVT::i32));
  InFlag = SDValue();
  Chain = DAG.getCopyToReg(Chain, DAG.getRegister(X86::EAX, MVT::i32), inc,
InFlag);
  InFlag = Chain.getValue(1);

Unfortunately, this becomes
  movl $42, %eax

1) That is, the ADD-operation is being folded. Is there a way to prevent
this from happening? I tried creating the constants wit
DAG::getTargetConstant, but it didn't help.

2) The second thing in this code is that InFlag. If I don't place InFlag =
SDValue(); there, llc complains about wrong topological ordering. What's
that about? Related to that: If I recover the Flag-result from the Chain by
InFlag = Chain.getValue(1);, what is it good for?

The last thing is that for the runtime check I want to insert I need to
compare the contents of eax with the parameter of the first instruction of
the call-target. If they are unequal, I want to jump to an error label. So,
the assembly to produce should look something like this (where callee is the
call destination):
  cmp eax, 4(callee)
  jne error

So what I've produced is:
  // expected (from eax)
  SDValue lhs = DAG.getCopyFromReg(Chain, X86::EAX, MVT::i32);
  // operand of first callee instruction
  SDValue rhs = DAG.getNode(ISD::ADD, MVT::i32, Callee, DAG.getConstant(4,
MVT::i32));
  Ops.push_back(Chain);
  Ops.push_back(DAG.getCondCode(ISD::SETEQ));
  Ops.push_back(lhs);
  Ops.push_back(rhs);
  MachineBasicBlock *error_block;
  Ops.push_back(DAG.getBasicBlock(error_block));
  Chain = DAG.getNode(ISD::BR_CC, MVT::Other, &Ops[0], Ops.size());

Now, there are, I guess, basically two things here:

3) How to access the value at address [callee + 4]? I guess, Callee won't
work as a parameter for add, and the result of the add in the cmp
instruction wont be interpreted as a memory location (but as a constant).

4) The ISD::BR_CC instruction requires to be passed a MachineBasicBlock.
Obviously, the uninitialized pointer in my example won't work. Is there any
way to access any MBB in the Program from X86ISelLowering::LowerCALL?

- Artjom

9

Artjom Kochtchi wrote:

4) The ISD::BR_CC instruction requires to be passed a MachineBasicBlock.
Obviously, the uninitialized pointer in my example won't work. Is there
any way to access any MBB in the Program from X86ISelLowering::LowerCALL?

Well, okay, I could create it somewhere and put it into some static variable
to access from everywhere. But is there some more elegant way to access
basic blocks?

10

Thanks to your help I've actually made some progress... Especially the
SelectionDAGNodes.h was a good hint.

But there are still some things that I can't figure out:
// 'mov eax, 41'
Chain = DAG.getCopyToReg(Chain, DAG.getRegister(X86::EAX, MVT::i32),
DAG.getConstant(41, MVT::i32), InFlag);
InFlag = Chain.getValue(1);

// 'inc eax'
SDValue eaxVal = DAG.getCopyFromReg(Chain, X86::EAX, MVT::i32);
SDValue inc = DAG.getNode(ISD::ADD, MVT::i32, eaxVal, DAG.getConstant(1,
MVT::i32));
InFlag = SDValue();
Chain = DAG.getCopyToReg(Chain, DAG.getRegister(X86::EAX, MVT::i32), inc,
InFlag);
InFlag = Chain.getValue(1);

This code produces the following assembly instructions:
movl $41, %eax
incl %eax

I guess that's because what I want to become 'incl %eax' actually becomes
'movl $41, %eax' for the first parameter for the ADD-node and 'incl %eax'
for the second.

So in order to fix this problem, I tried:
SDValue inc = DAG.getNode(ISD::ADD, MVT::i32, DAG.getConstant(41,
MVT::i32) DAG.getConstant(1, MVT::i32));
InFlag = SDValue();
Chain = DAG.getCopyToReg(Chain, DAG.getRegister(X86::EAX, MVT::i32), inc,
InFlag);
InFlag = Chain.getValue(1);

Unfortunately, this becomes
movl $42, %eax

1) That is, the ADD-operation is being folded. Is there a way to prevent
this from happening? I tried creating the constants wit
DAG::getTargetConstant, but it didn't help.

The code you're showing here is presumably just experimental code
that you'll eventually replace with something more interesting.
Unfortunately, it's difficult to see what you're actually
trying to do. For example, do you really need %eax, or do you
just need some register which isn't potentially used as an
argument register? If the latter, all this code could be a lot
simpler.

One thing to keep in mind is that the pre-isel SelectionDAG is still
somewhat high-level, and it can be somewhat awkward to think about
it in terms of x86 instructions.

2) The second thing in this code is that InFlag. If I don't place InFlag =
SDValue(); there, llc complains about wrong topological ordering. What's
that about? Related to that: If I recover the Flag-result from the Chain by
InFlag = Chain.getValue(1);, what is it good for?

Physical register lifetimes are not fully modeled in the SelectionDAG.
Flags are used to glue nodes together to protect them. If a node needs
input values in multiple physical registers, the CopyToReg nodes are
attached via flag operand to each other in a sequence, and finally to
the node itself. The first node in the sequence does not use a flag
operand. In your case, there's only one physical register, so the
CopyToReg node doesn't need a Flag input.

The last thing is that for the runtime check I want to insert I need to
compare the contents of eax with the parameter of the first instruction of
the call-target. If they are unequal, I want to jump to an error label. So,
the assembly to produce should look something like this (where callee is the
call destination):
cmp eax, 4(callee)
jne error

So what I've produced is:
// expected (from eax)
SDValue lhs = DAG.getCopyFromReg(Chain, X86::EAX, MVT::i32);
// operand of first callee instruction
SDValue rhs = DAG.getNode(ISD::ADD, MVT::i32, Callee, DAG.getConstant(4,
MVT::i32));
Ops.push_back(Chain);
Ops.push_back(DAG.getCondCode(ISD::SETEQ));
Ops.push_back(lhs);
Ops.push_back(rhs);
MachineBasicBlock *error_block;
Ops.push_back(DAG.getBasicBlock(error_block));
Chain = DAG.getNode(ISD::BR_CC, MVT::Other, &Ops[0], Ops.size());

Now, there are, I guess, basically two things here:

3) How to access the value at address [callee + 4]? I guess, Callee won't
work as a parameter for add, and the result of the add in the cmp
instruction wont be interpreted as a memory location (but as a constant).

At pre-isel SelectionDAG time, the arguments aren't yet on the stack. They're
just the operands to the ISD::CALL node.

4) The ISD::BR_CC instruction requires to be passed a MachineBasicBlock.
Obviously, the uninitialized pointer in my example won't work. Is there any
way to access any MBB in the Program from X86ISelLowering::LowerCALL?

The SelectionDAG framework currently only supports a single basic block
at a time, and it isn't possible to introduce new control flow from
within a block. This can perhaps be done by creating a new operator
which isn't lowered until later, or earlier, in LLVM IR, depending on
what you're trying to do.

Dan