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.