[llvm-dev] Question about Instruction Selection

[Bekket McClane via llvm-dev]

> Ahmed Bougacha <ahmed.bougacha at gmail.com> 於 2016年6月28日 下午9:15 寫道：
> 
> On Tue, Jun 28, 2016 at 5:49 AM, Bekket McClane
> <bekket.mcclane at gmail.com <mailto:bekket.mcclane at gmail.com>> wrote:
>> 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> 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.
> 
> Yes, the general thinking is that number of instructions (and also the
> size of each instruction, for targets where that changes) is a good
> enough estimate, and backend developers fix it up using
> AddedComplexity when it isn't: for your fmul+fadd example, we'd prefer
> the fmadd pattern instead of a separate fmul (and later fadd) simply
> because it is larger.
> 
> So far we haven't really needed to model the instruction cost in a
> finer way, and I don't think it's obvious how (you mention latency; is
> it really the best heuristic on OoO cores?).
I think that’s another big area in instruction scheduling.

> IIRC there's a FIXME
> somewhere in tablegen about modeling this, but I can't find it right
> now.

Thanks for your clear explanation Ahmed : )

> 
> HTH,
> -Ahmed
> 
>> 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
>> 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/3a67faae/attachment.html>