[llvm-dev] Question about Instruction Selection

[Bekket McClane via 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>