[LLVMdev] Instruction selector internals

[Evan Cheng]

On Oct 4, 2007, at 10:30 PM, nkavv at physics.auth.gr wrote:

> Hi Evan
>
>>> It looks
>>> like that the instruction selector operates on actual DAGs, no
>>> unDAGing to
>>> trees seems to occur at any point.
>> Instruction scheduler is responsible for turning a DAG into a list of
>> instructions.
>
> So unDAGing is applied by the instruction scheduler. At which  
> points in the
> compilation flow is the instruction scheduler run (i'm asking since  
> LLVM is
> modular and it could take place after as well as prior register  
> allocation).

It's right after instruction selection and before the various  
register allocation related passes.

>
>>> 1. Is the SelectionDAG selection phase restricted to matching  
>>> single-
>>> output
>>> patterns?
>> No such restriction. It's just tablgen syntax doesn't support multi-
>> output nodes. It can be extended if needed.
>
> OK.
>
>> The current selector is non-optimal. It seems like you have something
>> else in mind?
>
> Oh, OK, it's not a BURG-style selector, didn't notice that. But it  
> is a tree
> pattern matcher, right? I mean, LLVM as of current (release 2.1)  
> does not
> include a DAG matcher (for acyclic graphs). Am I right?

It's a pattern matcher operating on DAG's. Target independent nodes  
in, target specific nodes out.

>
> I had success with my own selector operating on Machine-SUIF dumps  
> (my format).
> It applies graph matching. Does work but would be much better if i  
> applied
> rewriting rules so that opportunities are not missed. It can match  
> patterns of
> large size (20-30 instruction nodes or more).
>
>> Multi-output patterns? It has to be taught. Or do you mean something
>> else?
>
> Yes, i refer to MIMO (multi-input multi-output) patterns. I recall  
> a Finnish
> engineer/developer creating a thread on MIMO pattern matching. I  
> believe (he
> didn't say) they are designing some form of custom VLIW processor  
> and would
> like to have their backend utilizing such patterns, since it can  
> really affects
> performance. I have done my own estimations for the processor (soft  
> core) i'm
> developing (not a VLIW but exploits intrinsic ILP) and I can 2x or  
> 3x loss
> performance if MIMO patterns can not be matched. Of course this  
> stands for HLL
> application programming for the processor.

The instruction selector *can* handle multi-output DAG nodes. The  
restriction is the TableGen language does not yet support it since we  
have no had a need for it. Patch is welcome. :-)

Evan

>
>
> Kind regards
> Nikolaos Kavvadias
>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev