llvm dev - Jun 2016 - Question about Instruction Selection

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?

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160628/54268863/attachment.html>

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
>

Thanks for swift reply
> Ahmed Bougacha <ahmed.bougacha at gmail.com> 於 2016年6月28日 下午8:11 寫道：
> 
> On Tue, Jun 28, 2016 at 4:42 AM, Bekket McClane via llvm-dev
> <llvm-dev at lists.llvm.org <mailto: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.
> 
Sorry that I didn’t state the question clear: “cost” I’m asking is the hardware
instruction(or operation) cost.
Or is it possible that backend developers express the cost model by mean of
TableGen patterns?
E.g. If there is an fmadd instruction and consume less cycle, developers need to
add a pattern which map fmul + fadd into fmadd. So one doesn’t need to provide
numeric cost values for tablegen to select optimized instruction.

Cheers

McClane
> 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 <mailto:llvm-dev at lists.llvm.org>
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
<http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160628/ecb31a60/attachment.html>