From 6a92b5e1e2a608cfb726bdcd5b043aee2cc350c5 Mon Sep 17 00:00:00 2001 From: Simon Pilgrim Date: Tue, 28 Aug 2018 15:42:08 +0000 Subject: [TableGen] CodeGenDAGPatterns::GenerateVariants - basic caching of matching predicates 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 high number of repeated comparisons of the pattern's vector. This initial patch at least avoids repeating these comparisons for every Variant in a 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. Saves around 15secs in debug builds of x86 -gen-dag-isel. Differential Revision: https://reviews.llvm.org/D51035 llvm-svn: 340837 --- llvm/utils/TableGen/CodeGenDAGPatterns.cpp | 16 ++++++++++++++-- 1 file changed, 14 insertions(+), 2 deletions(-) (limited to 'llvm/utils/TableGen/CodeGenDAGPatterns.cpp') diff --git a/llvm/utils/TableGen/CodeGenDAGPatterns.cpp b/llvm/utils/TableGen/CodeGenDAGPatterns.cpp index dc88da220e8..e6bcca2b7a5 100644 --- a/llvm/utils/TableGen/CodeGenDAGPatterns.cpp +++ b/llvm/utils/TableGen/CodeGenDAGPatterns.cpp @@ -13,6 +13,7 @@ //===----------------------------------------------------------------------===// #include "CodeGenDAGPatterns.h" +#include "llvm/ADT/BitVector.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SmallSet.h" @@ -4477,6 +4478,16 @@ void CodeGenDAGPatterns::GenerateVariants() { LLVM_DEBUG(errs() << "FOUND VARIANTS OF: "; PatternsToMatch[i].getSrcPattern()->dump(); errs() << "\n"); + // Cache matching predicates. + // TODO: Is it performant to pull this out of the loop entirely? + BitVector MatchedPredicates(PatternsToMatch.size(), false); + for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) + MatchedPredicates[p] = (i == p) || (PatternsToMatch[i].getPredicates() == + PatternsToMatch[p].getPredicates()); + + unsigned NumMatches = MatchedPredicates.count(); + (void)NumMatches; + for (unsigned v = 0, e = Variants.size(); v != e; ++v) { TreePatternNodePtr Variant = Variants[v]; @@ -4487,8 +4498,7 @@ void CodeGenDAGPatterns::GenerateVariants() { bool AlreadyExists = false; for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) { // Skip if the top level predicates do not match. - if ((i != p) && (PatternsToMatch[i].getPredicates() != - PatternsToMatch[p].getPredicates())) + if (!MatchedPredicates[p]) continue; // Check to see if this variant already exists. if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern(), @@ -4507,6 +4517,8 @@ void CodeGenDAGPatterns::GenerateVariants() { Variant, PatternsToMatch[i].getDstPatternShared(), PatternsToMatch[i].getDstRegs(), PatternsToMatch[i].getAddedComplexity(), Record::getNewUID())); + MatchedPredicates.resize(PatternsToMatch.size()); + MatchedPredicates[PatternsToMatch.size() - 1] = true; } LLVM_DEBUG(errs() << "\n"); -- cgit v1.2.3