[LLVMdev] Instruction descriptions question

[Chris Lattner]

On Mon, 2 Oct 2006, Roman Levenstein wrote:
>>> Wouldn't it be possible and even more clean to have just one
>>> description like (I use a pseudo-description here):
>>>
>>> def MOVrr  : I<0x88, MRMDestReg, (ops (GR8|GR16|GR32) :$dst,
>>> (i8mem|i16mem|i32mem):$src),
>>>                "mov{b} {$src, $dst|$dst, $src}", []>,
> isSameSize($dst,
>>> $src);
>>
>> We already have something like this, but it's a little more general.
>> The X86 backend hasn't been converted to use it.
>
> Any plans to do it, to make things simpler?

It would be nice, but noone has stepped up to do it yet.  It's a mostly 
mechanical change, so it should be straight-forward.

>> Sure.  It would be straight-forward to define a multiclass for your
> arch,
>> in which each use of defm makes three instructions: one for each
> width.
>
> Beautiful! This saved my day! Multiclass is an extremely useful 
> construct. Thanks a lot for explanations. Multiclasses seem to provide 
> almost everything (if not all) of the features that I was asking for. 
> I'll try to use it for writing a short and concise definition of 
> instructions for my target.

Yay :)

>> shouldn't need to do this, except in extreme cases.  Are you seeing
> cases
>> where the selector is missing an optimal match, or are you just used
> to
>> other tools which aren't as smart at inferring cost as tblgen?
>
> I guess, I'm just used to other more BURG-like tools. And yes, they are
> not too intelligent compared to tblgen;)

ok.

> So far, I haven't seen a real case where an optimal match is missed by
> tblgen. But I have not completely converted the old BURG-spec into
> tblgen yet. When I'm ready, I'll try to compare the results and check
> some corner cases (for example, I was using tree grammar to
> automatically select a best addressing mode, which tblgen doesn't
> support yet as far as I understand from the documentation;

Right.  Currently we end up handling this with ComplexPattern matchers, 
which are written in C++.  In practice, I found that this was simpler than 
writing patterns in the .td files anyway, at least for architectures with 
really complex addressing modes (x86).  For example, on x86, we want to 
match "(A+1)*8"  as  "A*8 + 8" and many other similar things.  Handling 
these with patterns is quite difficult when there are many orthogonal 
cases that need to be handled.

> there were also interesting tree patterns for C operations of the form X 
> OP= Y and increment operators) - let's see how tblgen will perform.

tblgen treats "updating" or "two-address" instructions as if they were 
three-address instructions, then uses the register allocator to pin the 
first two operands to the same register.  See use of 'isTwoAddress' in the 
X86 or PPC backends for examples.

>>> Why? As far as I understand, LLVM uses BURG/IBURG for instruction
>>> selection and both of these tools support costs, AFAIK.
>>
>> Nope, it uses neither.  It uses custom code built into tblgen.
>
> OK. Now I understand. Probably I thought that tblgen is BURG-based
> because there is a Burg subdirectory in the llvm/utils. And in older
> versions of llvm it was even non-empty, giving the impression that it
> is used.

Yep, it used to be used for the SparcV9 backend.

> BTW, does it use the same theory as BURG/IBURG when it generates the
> selector? I.e. dynamic programming + precomputed costs,etc?  Does it
> implicitly build a tree grammar or something like that?

Currently it uses a very simple greedy bottom-up iterative matcher.  We've 
found that most of the complexity of instruction selection is providing 
the DAG in a form that can easily be matched, rather than having really 
aggressive matching techniques.  That said, we hope to move to a dynamic 
programming two pass matcher at some point.

> Does it try to merge/share patterns as much as possible to speedup the 
> recognition phase as it is done by BURMs?

Yes.  This is also important to reduce code size.

> I have the impression (by looking at the produced C++ selector code) 
> that tblgen-based selectors are not as "precomputed" and optimal as 
> BURG-based ones. Do you have an idea or figures about how it compares to 
> BURG/IBURG selectors?

No measurements have been made, because noone has adapted burg/iburg to 
work with the LLVM DAGs.  It would be an interesting project if you're 
interested though!  Given a choice, I'd prefer that the matcher allow 
dynamic costs to be associated with the pattern.  This is really important 
when subtargets need to be supported (e.g. pentium vs athlon vs core vs 
...)

-Chris

-- 
http://nondot.org/sabre/
http://llvm.org/