llvm dev - Mar 2018 - Instruction selection algorithm

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.

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>

LLVM performs a greedy, bottom-up instruction selection. At each step, it
selects the pattern that will absorb the most nodes (roughly: the order can be
tweaked by the target using AddedComplexity, which is often used to model the
idea that a particular pattern is more profitable than it would otherwise
appear).

I don’t personally think there is that much to gain from an algorithm
significantly better than greedy; in practice most optimization goals seem to be
representable through heuristics on the regular selection algorithm, at least
for real machines. Additionally, I kind of suspect that there is far more to
gain from better transformations during instruction lowering (e.g. in
Combine1/Legalize/Combine2) than from better ordering in Select().

—escha
> On Mar 28, 2018, at 3:31 AM, 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