[llvm-dev] Instruction selection algorithm

[via llvm-dev]

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