[llvm-dev] Question about Instruction Selection

Bekket McClane via llvm-dev llvm-dev at lists.llvm.org
Tue Jun 28 04:42:54 PDT 2016

I'm new to LLVM and I'm doing research on factors of compilation time,
especially instruction selection and scheduling. One of the academic papers
I read,
https://llvm.org/svn/llvm-project/www-pubs/trunk/2008-CGO-DagISel.pdf (Koes,
David Ryan, and Seth Copen Goldstein. "Near-optimal instruction selection
on dags."), which is also said to be the algorithm LLVM currently
used(Correct me if I'm wrong), introduce an selection algorithm for DAG
instead of tree matching.

My question is, according to the paper, each tile in DAG has a cost value
which is used in dynamic programming process and CSE decisions. But in
TableGen files, I didn't find any field recording cost values or similar
properties. I know that the MatcherTables in generated TableGen include
files act like a byte code interpreter which perform bottom-up selection,
resembles to bottom-up dynamic programming. But if the generated
MatcherTables are really used for performing bottom-up dynamic programming
selection, it still needs a cost model to help it making decisions. So
where is it?

I've read some great articles about part of the platform-independent
instruction selection components. But I'm curious about instruction
selection algorithm currently used.


Bekket McClane
Department of Computer Science,
National Tsing Hua University
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160628/54268863/attachment.html>

More information about the llvm-dev mailing list