Page MenuHomePhabricator

[TableGen] CodeGenDAGPatterns::GenerateVariants - basic caching of matching predicates
ClosedPublic

Authored by RKSimon on Aug 21 2018, 7:09 AM.

Details

Summary

CodeGenDAGPatterns::GenerateVariants is a costly function in many tblgen commands (33.87% of the total runtime of x86 -gen-dag-isel), and due to the O(N^2) nature of the function, there are a lot of repeated comparisons of the pattern's vector<Predicate> (19.9% of the total runtime of x86 -gen-dag-isel).

This initial patch at least avoids repeating these comparisons for every Variant per pattern. I began investigating caching all the matches before entering the loop but hit issues with how best to store the data and how to update the cache as patterns were added - until thats solved, this is at least an improvement.

Also, its not clear to me if the inner loop over PatternsToMatch needs to compare against the extra patterns generated in the function or not - if not it should be possible to split these loops and reduce its quadratic nature. @kparzysz can you confirm please?

Saves around 15secs in debug builds of x86 -gen-dag-isel.

Diff Detail

Repository
rL LLVM

Event Timeline

RKSimon created this revision.Aug 21 2018, 7:09 AM

It should be possible to move this loop out of the nest and only have it iterate over the preexisting patterns. Could you see if that generates different .inc files (it shouldn't)?

It should be possible to move this loop out of the nest and only have it iterate over the preexisting patterns. Could you see if that generates different .inc files (it shouldn't)?

Definitely, but to do it properly requires quite a bit of refactoring - the O(N^2) nature of this loop needs addressing properly - I'd prefer to get this initial patch in first please.

kparzysz accepted this revision.Aug 28 2018, 6:37 AM
This revision is now accepted and ready to land.Aug 28 2018, 6:37 AM
This revision was automatically updated to reflect the committed changes.