[LLVMdev] Instruction selector internals
evan.cheng at apple.com
Fri Oct 5 02:10:44 CDT 2007
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
> 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
It's right after instruction selection and before the various
register allocation related passes.
>>> 1. Is the SelectionDAG selection phase restricted to matching
>> No such restriction. It's just tablgen syntax doesn't support multi-
>> output nodes. It can be extended if needed.
>> 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
> 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
> 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. :-)
> Kind regards
> Nikolaos Kavvadias
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
More information about the LLVMdev