llvm dev - Oct 2007 - [LLVMdev] Instruction selector internals

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).
> > 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?

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.


Kind regards
Nikolaos Kavvadias

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