Instruction selector internals

Hi there

first of all, many thanks to some people out there for their advice on building
LLVM on Cygwin (this would be Aaron Gray, Reid Spencer, Tanya and Chris Lattner
i suppose).

LLVM 2.1 seems to build in debug mode on my "old" Cygwin (1.5.15). At least
everything except tblgen is build. For tblgen i use the supplied mingw
binaries, many thanks for that!

I would like now to ask you a few questions regarding the instruction selector.

For my processor architecture, multi-input multi-output operations are under
software control and would like to take advantage of them in LLVM. It looks
like that the instruction selector operates on actual DAGs, no unDAGing to
trees seems to occur at any point.

1. Is the SelectionDAG selection phase restricted to matching single-output
patterns?

2. Could we add in the current instruction selector an non-optimal pattern
selector for multi-output patterns? I have done this for my own custom set of
tools and what it basically needs is a graph-subgraph isomorphism engine
operating on intermediate code.

3. Are there (right now) any ideas on an non-optimal pattern matcher working on
DAGs and accepting DAG patterns?

4. Is the machine description language (that is understood by tablegen) able to
handle such patterns? (i think it is, but i'm just asking to verify this)

5. Which are the instruction selection algorithms currently available?

I recall a similar discussion on this subject a few months ago.

Kind regards
Nikolaos Kavvadias

Hi there

first of all, many thanks to some people out there for their advice on building
LLVM on Cygwin (this would be Aaron Gray, Reid Spencer, Tanya and Chris Lattner
i suppose).

LLVM 2.1 seems to build in debug mode on my "old" Cygwin (1.5.15). At least
everything except tblgen is build. For tblgen i use the supplied mingw
binaries, many thanks for that!

I would like now to ask you a few questions regarding the instruction selector.

For my processor architecture, multi-input multi-output operations are under
software control and would like to take advantage of them in LLVM. 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.

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.

2. Could we add in the current instruction selector an non-optimal pattern
selector for multi-output patterns? I have done this for my own custom set of
tools and what it basically needs is a graph-subgraph isomorphism engine
operating on intermediate code.
3. Are there (right now) any ideas on an non-optimal pattern matcher working on
DAGs and accepting DAG patterns?

The current selector is non-optimal. It seems like you have something else in mind?

4. Is the machine description language (that is understood by tablegen) able to
handle such patterns? (i think it is, but i'm just asking to verify this)

Multi-output patterns? It has to be taught. Or do you mean something else?

5. Which are the instruction selection algorithms currently available?

It's just a bottom up tree matching selector. We'd like to do a burg style selector but haven't had the time.

Evan