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

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. :slight_smile:

Evan