[LLVMdev] Instruction selector internals

[nkavv at physics.auth.gr]

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