llvm dev - Oct 2007 - [LLVMdev] 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

On Oct 4, 2007, at 7:50 PM, nkavv at physics.auth.gr wrote:
> 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
>
>
>
> I recall a similar discussion on this subject a few months ago.
>
> 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