[LLVMdev] Instruction selector internals

[Evan Cheng]

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