[LLVMdev] question on instruction selection

[Nuno Lopes]

Hi,

I was wondering how exactly instruction selection works in LLVM. As I'm not 
aware of any document describing it, I'll ask here :)

So, the tablegen files that each backend implements describe the mapping 
between selection DAG nodes and assembly instructions (and optionally? their 
binary encoding). The selection DAG (one per basic block) is produced "by 
hand" directly from the LLVM IR. This pass is independent of the target 
architecture. Therefore, implementing a new backend is "just" about 
specifying patterns that convert selection DAG nodes to the target's 
assembly.

Is my understanding correct? Also, is there any document describing the 
selection DAG nodes that one needs to match against? And what's the 
algorithm behind this selection DAG?

I'm also wondering what would be the possible improvement of the approach 
presented last Friday at POPL 
(http://portal.acm.org/citation.cfm?doid=1706299.1706346 or 
http://www.eecs.tufts.edu/~dias/gentileset.pdf) for LLVM. Any insight?  The 
approach seems similar to what gcc does or did at least (IR->RTL->ASM), so 
I'm not entirely sure there would be something to gain here for LLVM. It 
would be nice to generate the selection dag from LLVM IR automatically, 
though.

Thanks,
Nuno