[llvm-dev] Instruction selection algorithm

[Jatin Bhateja via llvm-dev]

Hi Ivan,

Matcher table generation which is implemented in utils/DAGISelEmitter.cpp
does use heusiristics like number of instructions which a pattern will
cover, latency (not the one which Targets scheduling defines) while
emitting the candidate patterns for a give dag node.

Current implications may not be implication of algorithm in toto though.

Thanks,
Jatin

On Wednesday, March 28, 2018, Ivan Kulagin via llvm-dev <
llvm-dev at lists.llvm.org> wrote:

> Is the algorithm described in the article "Near-Optimal Instruction
> Selection on DAGs
> (https://llvm.org/pubs/2008-CGO-DagISel.html)" really used in llvm
> instruction selection?
> I've studied implementation (SelectionDAGISel.cpp) and I see that
> instructions are selected
> by target specific MatcherTable generated by llvm-tblgen. In the
> implementation the first
> matching pattern from MatcherTable is selected but in the paper all
> matching patterns (in paper
> named tiles) are selected for each DAG node and cost estimation is
> performed for every tile and
> node. Then the best tiles are selected by dynamic programming.
>
> Could you please explain me how llvm instruction selection relates to
> the NOLTIS algorithm
> in the paper?
>
> Does it make sense to use dynamic programming for instruction
> selection based on MatcherTable?
>
> --
> With best regards,
> Ivan Kulagin.
> _______________________________________________
> 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/20180406/b8beaa46/attachment.html>