[llvm-dev] Question about Instruction Selection

[Ahmed Bougacha via llvm-dev]

On Tue, Jun 28, 2016 at 4:42 AM, Bekket McClane via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> Hi,
> 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?

There is a cost of sorts used to generate the matchers: it's usually
the size (complexity) of the pattern to match.  Patterns can then
override it using the "AddedComplexity" field.

There is also a cost model for the output patterns, based on the
number of selected instructions and estimates of their encoded sizes.
It's used as a tie-breaker when the input complexity is equal.

TableGen then uses that cost to order the matching tables;  I'm not
aware of additional cost models used in SelectionDAGISel itself;  it's
a "simple" interpreter for the generated matcher, so all the cost
decisions are made statically, in tblgen, at compile-compile time.

If you haven't already, you should look at the generated tables, which
show the computed complexity of individual patterns.

Does that help?
-Ahmed

> 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.
>
> Cheers,
>
> --
> Bekket McClane
> Department of Computer Science,
> National Tsing Hua University
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>