llvm dev - Oct 2006 - [LLVMdev] Questions about instruction selection and instruction definitions

Hi,

Few more questions that I found while trying to develop a new backend.
And sorry if I ask too many questions.

1) My target (embedded processor, which is a "not so direct" successor
of Z80 family of processors) does not support SELECT, so I was looking
for a workaround. 

First I was thinking about expanding it into conditional flow with
branching, but then I have found that there exists a pass called
LowerSelect already. 

I added in the getAnalysisUsage of my DAGtoDAGSel class (derived from
SelectionDAGSel) as a required analysis. After that, there are no more
SELECT instructions passed to my code selector, which is what I wanted.
Is it a correct to do it this way?

Anyhow, I have a very strong impression that after I did it, something
goes wrong with the code generations of copies from PHI nodes.
Sometimes this code is not generated at all. Can it be that LowerSelect
breaks some information like PHIs or some CFG information and this is
the reason why I see these side-effects? May be I have to call some
other pass after LowerSelect to recompute some properties and to bring
the code again into the correct form? Any ideas?

BTW, which pass(es) does transformation of PHIs into copies during code
selection?

2) In the X86 target, I've seen the special register classes GR16_ and
GR32_, which are subsclasses of GR16 and GR32. These two classes are
used just in a few places inside the instructions definition file.
There they are only used to define the fact that normal regs from GR32
can be moved into GR32_ regs. This is not quite obvious for me why this
classes are introduced at all, if they are almost not used anywhere in
the descriptions ...

On my target, there are many instructions that have certain constraints
using register subclasses, for example:
  loads from memory are only allowed to the GR_ regs
  copies between GR and GR_ regs are allowed
  stores to memory are only possible from GR_ regs

How this can be expressed in the definitions of instructions? I tried
to use GR_ register classes at appropriate places, when describing
instructions operands. Is it a right method?  So far I was not very
successful, since after I did it as I described, tblgen started to
produce errors like "Pattern x is impossible to select". Why do I have
it and what should it mean? May be I'm doing something wrong.  

Besides what I described, my target has additionally support for banks
if registers. Access to the registers in the non-current bank is more
expensive than access to regs from the current bank. And many
operations cannot have such regs from other banks as first operand. How
something like this can be expressed? Is there any support for such
kind of constraints. I can roughly imagine how instruction descriptions
could look like. But I guess also a register allocator should take this
into account. Otherwise too many copies between regs from current bank
and other banks will be generated (e.g. virtual reg was allocated to a
physical register from another bank, but later it is required in an
instruction that cannot take this register as operand. So, it must be
copied into a register in the current bank...). And decisions of
register allocator need to be based on minimization of total costs,
probably. Sounds very complex. I just wonder if LLVM already supports
something like this in any form.

3) My target has only 2 addr instructions, i.e. each instruction has at
most 2 operands. Do I still need to use 3 operands for such operations
like OR, AND, ADD, SUB in my instruction descriptions, but mark them as
isTwoAddrress=1??? Or do I need to call a special pass that converts
everything into 2-operand instructions?

4) Following Chris advice regarding multiclasses, I defined several
multiclasses, each containing 6 defs. But I noticed that I cannot use
"let isTwoAddress=1" or "let isCommutable=1" inside the
multiclass
definition, which would be very handy. Is it really impossible or may
be there is a special syntax to be used? As a workaround, I can use
"let ..." with defm definitions using this multiclass.

5) Can definitionss inside a multiclass use another multiclass? I.e. is
it possible to use defm inside multiclass definitions?

Thanks,
 Roman
 

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com

On 10/3/06, Roman Levenstein <romixlev at yahoo.com>
wrote:
> Hi,
>
> Few more questions that I found while trying to develop a new backend.
> And sorry if I ask too many questions.
I only have answers to some of them:
> 1) My target (embedded processor, which is a "not so direct"
successor
> of Z80 family of processors) does not support SELECT, so I was looking
> for a workaround.
>
> First I was thinking about expanding it into conditional flow with
> branching, but then I have found that there exists a pass called
> LowerSelect already.
>
> I added in the getAnalysisUsage of my DAGtoDAGSel class (derived from
> SelectionDAGSel) as a required analysis. After that, there are no more
> SELECT instructions passed to my code selector, which is what I wanted.
> Is it a correct to do it this way?
You can add the line
setOperationAction(ISD::SELECT, MVT::i32, Expand);
to the constructor of you TargetLowering class. See the current
backend for an example.

....
> On my target, there are many instructions that have certain constraints
> using register subclasses, for example:
>   loads from memory are only allowed to the GR_ regs
>   copies between GR and GR_ regs are allowed
>   stores to memory are only possible from GR_ regs
>
> How this can be expressed in the definitions of instructions? I tried
> to use GR_ register classes at appropriate places, when describing
> instructions operands. Is it a right method?  So far I was not very
> successful, since after I did it as I described, tblgen started to
> produce errors like "Pattern x is impossible to select". Why do I
have
> it and what should it mean? May be I'm doing something wrong.
I think that using register classes is the right solution. I don't
know what is causing the problem.
> Besides what I described, my target has additionally support for banks
> if registers. Access to the registers in the non-current bank is more
> expensive than access to regs from the current bank. And many
> operations cannot have such regs from other banks as first operand. How
> something like this can be expressed? Is there any support for such
> kind of constraints. I can roughly imagine how instruction descriptions
> could look like. But I guess also a register allocator should take this
> into account. Otherwise too many copies between regs from current bank
> and other banks will be generated (e.g. virtual reg was allocated to a
> physical register from another bank, but later it is required in an
> instruction that cannot take this register as operand. So, it must be
> copied into a register in the current bank...). And decisions of
> register allocator need to be based on minimization of total costs,
> probably. Sounds very complex. I just wonder if LLVM already supports
> something like this in any form.
I don't know, but you can implement a register allocator that is
specific to this problem.
> 3) My target has only 2 addr instructions, i.e. each instruction has at
> most 2 operands. Do I still need to use 3 operands for such operations
> like OR, AND, ADD, SUB in my instruction descriptions, but mark them as
> isTwoAddrress=1??? Or do I need to call a special pass that converts
> everything into 2-operand instructions?
Using isTwoAddrress=1 should do it.
> Thanks,
>  Roman
Best Regards,
Rafael

Hi Rafael,

Thanks for the answers.
> > 1) My target (embedded processor, which is a "not so direct"
> successor
> > of Z80 family of processors) does not support SELECT, so I was
> looking
> > for a workaround.
> >
> > First I was thinking about expanding it into conditional flow with
> > branching, but then I have found that there exists a pass called
> > LowerSelect already.
> >
> > I added in the getAnalysisUsage of my DAGtoDAGSel class (derived
> from
> > SelectionDAGSel) as a required analysis. After that, there are no
> more
> > SELECT instructions passed to my code selector, which is what I
> wanted.
> > Is it a correct to do it this way?
> You can add the line
> setOperationAction(ISD::SELECT, MVT::i32, Expand);
> to the constructor of you TargetLowering class. See the current
> backend for an example.
I actually tried it first. But then if, I remember correctly, SELECT
nodes were expanded into something using SELECT_CC, which is also not
supported on my target. Basically, only conditional branches are
supported. Therefore I thought about using the LowerSelect pass. But
I'll try again this evening. May be I was doing something wrong. 

What should be the result of expanding SELECT?  Some sort of
IF-THEN-ELSE flow?
> > On my target, there are many instructions that have certain
> constraints
> > using register subclasses, for example:
> >   loads from memory are only allowed to the GR_ regs
> >   copies between GR and GR_ regs are allowed
> >   stores to memory are only possible from GR_ regs
> >
> > How this can be expressed in the definitions of instructions? I
> tried
> > to use GR_ register classes at appropriate places, when describing
> > instructions operands. Is it a right method?  So far I was not very
> > successful, since after I did it as I described, tblgen started to
> > produce errors like "Pattern x is impossible to select". Why
do I
> have
> > it and what should it mean? May be I'm doing something wrong.
> I think that using register classes is the right solution. I don't
> know what is causing the problem.
I also think so. But when you get such a message like described above,
it is rather difficult to guess the reason. I even extended the tblgen
tool to print a whole set of conflicting patterns in this case. But
they all looked OK for me, i.e. I could not see any clear reason why a
given pattern  would not be selected. I'll try to dig deeper into this
issue. 
 
> > Besides what I described, my target has additionally support for
> banks
> > if registers. Access to the registers in the non-current bank is
> more
> > expensive than access to regs from the current bank. And many
> > operations cannot have such regs from other banks as first operand.
> How
> > something like this can be expressed? Is there any support for such
> > kind of constraints. I can roughly imagine how instruction
> descriptions
> > could look like. But I guess also a register allocator should take
> this
> > into account. Otherwise too many copies between regs from current
> bank
> > and other banks will be generated (e.g. virtual reg was allocated
> to a
> > physical register from another bank, but later it is required in an
> > instruction that cannot take this register as operand. So, it must
> be
> > copied into a register in the current bank...). And decisions of
> > register allocator need to be based on minimization of total costs,
> > probably. Sounds very complex. I just wonder if LLVM already
> supports
> > something like this in any form.
> I don't know, but you can implement a register allocator that is
> specific to this problem.
Sure. I just thought that there may be some sort of initial support for
that kind of issues.
 
Best regards,
 Roman

__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com