Refactor VariantMatcher::MatcherOps to reduce the amount of generated code.

[sbenza]

Summary

Refactor VariantMatcher::MatcherOps to reduce the amount of generated code.

• Make some code type agnostic and move it to the cpp file.
• Return a DynTypedMatcher instead of storing the object in MatcherOps.

This change reduces the number of symbols generated in Registry.cpp by
~19%, the object byte size by ~17% and the compilation time (in non-release mode) by ~20%.

[klimek]

1. Using /bigobj doesn't seem to be controversial
2. Can we make the compiler faster on this code?

I'm still not sure this is worth it. It seems to make the code harder to maintain.

[klimek]

"Needlessly". I don't think making code more complex is worth it. If we can
make the code simpler, I'd be all into it...

[sbenza]

What is exactly the objection?
If it is the manual vtable, I can revert that part and still get most of the benefit. The big savings are from moving a bunch of code to the .cpp and making some methods non-virtual by using ASTNodeKind.

[klimek]

Yes, the manual vtable is the biggest issue.
Just for my curiosity - wouldn't it be much simpler to split up the registration into multiple files?

[sbenza]

Simpler? I don't know.
What metric do we use for splitting them?

I'll update the diff without the vtable.

[klimek]

Split it up into 5 files should make each file 1/5th the size and 1/5th compile time? Split up more whenever we need? Generate the split TUs? That seems a better long term strategy than poking at the code (that is already borderline complex for my taste ;)

[sbenza]

Bring back the virtual functions.

[sbenza]

Updated the numbers also.

[klimek]

If you really think this is the right change, by all means, check it in. I'd just be excited if we found a different way to address the problem.

include/clang/ASTMatchers/Dynamic/VariantValue.h

125–126

Is there a chance to get something out of this without handing around void*'s?

Have you tried splitting the registration up into multiple TUs, and what effect that has?

[sbenza]

I did try splitting it up. It doesn't scale much.
Each part contains duplicate template instantiations, so splitting in N pieces will not make each one 1/Nth of the total.
Tried 1-5 pieces. These are the results:

parts | # symbols | total

    |  per part | symbols
1   |    ~19k   |  ~19k
2   |    ~13k   |  ~26k
3   |    ~10k   |  ~30k
4   |    ~9k    |  ~36k
5   |    ~8k    |  ~40k

Note that I did not try to group similar matchers together (which would be a maintenance nightmare), so each part ends up instantiating most of the common templates for a lot (most?) of the node types.

[klimek]

+chandler

19k sounds like so little; why does it take so much time =[
Can we fix the compiler to make this fast then?

[sbenza]

Get rid of the void* arguments/return values. Use DynTypedMatcher instead.

[sbenza]

Replaced the void* with DynTypedMatcher and it simplified the interface even more (and improved the numbers).
Updated the numbers in the description.

include/clang/ASTMatchers/Dynamic/VariantValue.h

125–126

Removed the void* passing. Moved a little more logic to DynTypedMatcher instead.

[klimek]

... and I still think we should fix the compiler...

lib/ASTMatchers/ASTMatchersInternal.cpp

29–37

This needs a comment or two :)

[sbenza]

Added comment and fixed up the variable names.

[rnk]

In D5124#20, @klimek wrote:

+chandler

19k sounds like so little; why does it take so much time =[
Can we fix the compiler to make this fast then?

We can make it fast in release mode by optimizing away lots of cruft, but probably not in debug mode. You've asked the compiler to make many thousands of functions, and that's fundamentally really expensive.

[sbenza]

I am not opposed to making the compiler faster, but I am not in a position to do that.

lib/ASTMatchers/ASTMatchersInternal.cpp

29–37

Done.

[sbenza]

Closed by commit rL217152 (authored by @sbenza).

include/clang/ASTMatchers/ASTMatchersInternal.h

public:
   /// \brief Construct from a \c Matcher<T>. Copies the matcher.
   template <typename T> inline DynTypedMatcher(const Matcher<T> &M);
 
   /// \brief Construct from a bindable \c Matcher<T>. Copies the matcher.
   ///
   /// This version enables \c tryBind() on the \c DynTypedMatcher.
   template <typename T> inline DynTypedMatcher(const BindableMatcher<T> &M);
 
+  /// \brief Construct from a variadic function.
+  typedef bool (*VariadicOperatorFunction)(
+      const ast_type_traits::DynTypedNode DynNode, ASTMatchFinder *Finder,
+      BoundNodesTreeBuilder *Builder, ArrayRef<DynTypedMatcher> InnerMatchers);
+  static DynTypedMatcher
+  constructVariadic(VariadicOperatorFunction Func,
+                    ArrayRef<DynTypedMatcher> InnerMatchers) {
+    assert(InnerMatchers.size() > 0 && "Array must not be empty.");
+    return DynTypedMatcher(new VariadicStorage(Func, InnerMatchers));
+  }
+
   /// \brief Returns true if the matcher matches the given \c DynNode.
   bool matches(const ast_type_traits::DynTypedNode DynNode,
                ASTMatchFinder *Finder, BoundNodesTreeBuilder *Builder) const {
     return Storage->matches(DynNode, Finder, Builder);
   }
 
   /// \brief Bind the specified \p ID to the matcher.
   /// \return A new matcher with the \p ID bound to it if this matcher supports
public:
   }
 
   /// \brief Returns \c true if the passed \c DynTypedMatcher can be converted
   ///   to a \c Matcher<T>.
   ///
   /// This method verifies that the underlying matcher in \c Other can process
   /// nodes of types T.
   template <typename T> bool canConvertTo() const {
-    return getSupportedKind().isBaseOf(
-        ast_type_traits::ASTNodeKind::getFromNodeKind<T>());
+    return canConvertTo(ast_type_traits::ASTNodeKind::getFromNodeKind<T>());
   }
+  bool canConvertTo(ast_type_traits::ASTNodeKind To) const;
 
   /// \brief Construct a \c Matcher<T> interface around the dynamic matcher.
   ///
   /// This method asserts that \c canConvertTo() is \c true. Callers
   /// should call \c canConvertTo() first to make sure that \c this is
   /// compatible with T.
   template <typename T> Matcher<T> convertTo() const {
     assert(canConvertTo<T>());
public:
 
     uint64_t getID() const { return ID; }
 
   private:
     const ast_type_traits::ASTNodeKind SupportedKind;
     const uint64_t ID;
   };
 
+  class VariadicStorage : public MatcherStorage {
+  public:
+    VariadicStorage(VariadicOperatorFunction Func,
+                    ArrayRef<DynTypedMatcher> InnerMatchers)
+        : MatcherStorage(InnerMatchers[0].getSupportedKind(),
+                         reinterpret_cast<uint64_t>(this)),
+          Func(Func), InnerMatchers(InnerMatchers) {}
+
+    bool matches(const ast_type_traits::DynTypedNode DynNode,
+                 ASTMatchFinder *Finder,
+                 BoundNodesTreeBuilder *Builder) const override {
+      return Func(DynNode, Finder, Builder, InnerMatchers);
+    }
+
+    llvm::Optional<DynTypedMatcher> tryBind(StringRef ID) const override {
+      return llvm::None;
+    }
+
+  private:
+    VariadicOperatorFunction Func;
+    std::vector<DynTypedMatcher> InnerMatchers;
+  };
+
   /// \brief Typed implementation of \c MatcherStorage.
   template <typename T> class TypedMatcherStorage;
 
+  /// \brief Internal constructor for \c constructVariadic.
+  DynTypedMatcher(MatcherStorage *Storage) : Storage(Storage) {}
+
   IntrusiveRefCntPtr<const MatcherStorage> Storage;
 };
 
 template <typename T>
 class DynTypedMatcher::TypedMatcherStorage : public MatcherStorage {
 public:
   TypedMatcherStorage(const Matcher<T> &Other, bool AllowBind)
       : MatcherStorage(ast_type_traits::ASTNodeKind::getFromNodeKind<T>(),
inline DynTypedMatcher::DynTypedMatcher(const Matcher<T> &M)
     : Storage(new TypedMatcherStorage<T>(M, false)) {}
 
 template <typename T>
 inline DynTypedMatcher::DynTypedMatcher(const BindableMatcher<T> &M)
     : Storage(new TypedMatcherStorage<T>(M, true)) {}
 
 /// \brief Specialization of the conversion functions for QualType.
 ///
-/// These specializations provide the Matcher<Type>->Matcher<QualType>
+/// This specialization provides the Matcher<Type>->Matcher<QualType>
 /// conversion that the static API does.
-template <> inline bool DynTypedMatcher::canConvertTo<QualType>() const {
-  const ast_type_traits::ASTNodeKind SourceKind = getSupportedKind();
-  return SourceKind.isSame(
-             ast_type_traits::ASTNodeKind::getFromNodeKind<Type>()) ||
-         SourceKind.isSame(
-             ast_type_traits::ASTNodeKind::getFromNodeKind<QualType>());
-}
-
 template <>
 inline Matcher<QualType> DynTypedMatcher::convertTo<QualType>() const {
   assert(canConvertTo<QualType>());
   const ast_type_traits::ASTNodeKind SourceKind = getSupportedKind();
   if (SourceKind.isSame(
           ast_type_traits::ASTNodeKind::getFromNodeKind<Type>())) {
     // We support implicit conversion from Matcher<Type> to Matcher<QualType>
     return unconditionalConvertTo<Type>();

include/clang/ASTMatchers/Dynamic/VariantValue.h

 ///    to decide which matcher to return. Eg. it contains only a single
 ///    matcher, or a polymorphic one with only one overload.
 ///  - hasTypedMatcher<T>()/getTypedMatcher<T>(): These calls will determine if
 ///    the underlying matcher(s) can unambiguously return a Matcher<T>.
 class VariantMatcher {
   /// \brief Methods that depend on T from hasTypedMatcher/getTypedMatcher.
   class MatcherOps {
   public:
-    virtual ~MatcherOps();
-    virtual bool canConstructFrom(const DynTypedMatcher &Matcher,
-                                  bool &IsExactMatch) const = 0;
-    virtual void constructFrom(const DynTypedMatcher &Matcher) = 0;
-    virtual void constructVariadicOperator(
+    MatcherOps(ast_type_traits::ASTNodeKind NodeKind) : NodeKind(NodeKind) {}
+
+    bool canConstructFrom(const DynTypedMatcher &Matcher,
+                          bool &IsExactMatch) const;
+
+    /// \brief Convert \p Matcher the destination type and return it as a new
+    /// DynTypedMatcher.
+    virtual DynTypedMatcher
+    convertMatcher(const DynTypedMatcher &Matcher) const = 0;
+
+    /// \brief Constructs a variadic typed matcher from \p InnerMatchers.
+    /// Will try to convert each inner matcher to the destination type and
+    /// return llvm::None if it fails to do so.
+    llvm::Optional<DynTypedMatcher> constructVariadicOperator(
         ast_matchers::internal::VariadicOperatorFunction Func,
-        ArrayRef<VariantMatcher> InnerMatchers) = 0;
+        ArrayRef<VariantMatcher> InnerMatchers) const;
+
+  private:
+    ast_type_traits::ASTNodeKind NodeKind;
   };
 
   /// \brief Payload interface to be specialized by each matcher type.
   ///
   /// It follows a similar interface as VariantMatcher itself.
   class Payload : public RefCountedBaseVPTR {
   public:
     virtual ~Payload();
     virtual llvm::Optional<DynTypedMatcher> getSingleMatcher() const = 0;
     virtual std::string getTypeAsString() const = 0;
-    virtual void makeTypedMatcher(MatcherOps &Ops) const = 0;
+    virtual llvm::Optional<DynTypedMatcher>
+    getTypedMatcher(const MatcherOps &Ops) const = 0;
     virtual bool isConvertibleTo(ast_type_traits::ASTNodeKind Kind,
                                  unsigned *Specificity) const = 0;
   };
 
 public:
   /// \brief A null matcher.
   VariantMatcher();
 
public:
   ///
   /// For the Single case, it returns true if it can be converted to
   /// \c Matcher<T>.
   /// For the Polymorphic case, it returns true if one, and only one, of the
   /// overloads can be converted to \c Matcher<T>. If there are more than one
   /// that can, the result would be ambiguous and false is returned.
   template <class T>
   bool hasTypedMatcher() const {
-    TypedMatcherOps<T> Ops;
-    if (Value) Value->makeTypedMatcher(Ops);
-    return Ops.hasMatcher();
+    if (!Value) return false;
+    return Value->getTypedMatcher(TypedMatcherOps<T>()).hasValue();
   }
 
   /// \brief Determines if the contained matcher can be converted to \p Kind.
   ///
   /// \param Kind the requested destination type.
   ///
   /// \param Specificity value corresponding to the "specificity" of the
   ///   convertion.
   bool isConvertibleTo(ast_type_traits::ASTNodeKind Kind,
                        unsigned *Specificity) const {
     if (Value)
       return Value->isConvertibleTo(Kind, Specificity);
     return false;
   }
 
   /// \brief Return this matcher as a \c Matcher<T>.
   ///
   /// Handles the different types (Single, Polymorphic) accordingly.
   /// Asserts that \c hasTypedMatcher<T>() is true.
   template <class T>
   ast_matchers::internal::Matcher<T> getTypedMatcher() const {
-    TypedMatcherOps<T> Ops;
-    Value->makeTypedMatcher(Ops);
-    assert(Ops.hasMatcher() && "hasTypedMatcher<T>() == false");
-    return Ops.matcher();
+    assert(hasTypedMatcher<T>() && "hasTypedMatcher<T>() == false");
+    return Value->getTypedMatcher(TypedMatcherOps<T>())
+        ->template convertTo<T>();
   }
 
   /// \brief String representation of the type of the value.
   ///
   /// If the underlying matcher is a polymorphic one, the string will show all
   /// the types.
   std::string getTypeAsString() const;
 
 private:
   explicit VariantMatcher(Payload *Value) : Value(Value) {}
 
+  template <typename T> struct TypedMatcherOps;
+
   class SinglePayload;
   class PolymorphicPayload;
   class VariadicOpPayload;
 
-  template <typename T>
-  class TypedMatcherOps : public MatcherOps {
-  public:
-    typedef ast_matchers::internal::Matcher<T> MatcherT;
+  IntrusiveRefCntPtr<const Payload> Value;
+};
+
+struct VariantMatcher::TypedMatcherOps : VariantMatcher::MatcherOps {
+  TypedMatcherOps()
+      : MatcherOps(ast_type_traits::ASTNodeKind::getFromNodeKind<T>()) {}
 
-    virtual bool canConstructFrom(const DynTypedMatcher &Matcher,
-                                  bool &IsExactMatch) const {
-      IsExactMatch = Matcher.getSupportedKind().isSame(
-          ast_type_traits::ASTNodeKind::getFromNodeKind<T>());
-      return Matcher.canConvertTo<T>();
-    }
-
-    virtual void constructFrom(const DynTypedMatcher& Matcher) {
-      Out.reset(new MatcherT(Matcher.convertTo<T>()));
-    }
-
-    virtual void constructVariadicOperator(
-        ast_matchers::internal::VariadicOperatorFunction Func,
-        ArrayRef<VariantMatcher> InnerMatchers) {
-      std::vector<DynTypedMatcher> DynMatchers;
-      for (size_t i = 0, e = InnerMatchers.size(); i != e; ++i) {
-        // Abort if any of the inner matchers can't be converted to
-        // Matcher<T>.
-        if (!InnerMatchers[i].hasTypedMatcher<T>()) {
-          return;
-        }
-        DynMatchers.push_back(InnerMatchers[i].getTypedMatcher<T>());
-      }
-      Out.reset(new MatcherT(
-          new ast_matchers::internal::VariadicOperatorMatcherInterface<T>(
-              Func, DynMatchers)));
-    }
-
-    bool hasMatcher() const { return Out.get() != nullptr; }
-    const MatcherT &matcher() const { return *Out; }
-
-  private:
-    std::unique_ptr<MatcherT> Out;
-  };
-
-  IntrusiveRefCntPtr<const Payload> Value;
+  DynTypedMatcher
+  convertMatcher(const DynTypedMatcher &Matcher) const override {
+    return DynTypedMatcher(Matcher.convertTo<T>());
 };
 
 /// \brief Variant value class.
 ///
 /// Basically, a tagged union with value type semantics.
 /// It is used by the registry as the return value and argument type for the
 /// matcher factory methods.
 /// It can be constructed from any of the supported types. It supports

lib/ASTMatchers/ASTMatchersInternal.cpp

 void BoundNodesTreeBuilder::visitMatches(Visitor *ResultVisitor) {
   if (Bindings.empty())
     Bindings.push_back(BoundNodesMap());
   for (unsigned i = 0, e = Bindings.size(); i != e; ++i) {
     ResultVisitor->visitMatch(BoundNodes(Bindings[i]));
   }
 }
 
+bool DynTypedMatcher::canConvertTo(ast_type_traits::ASTNodeKind To) const {
+  const auto SourceKind = getSupportedKind();
+  auto QualKind = ast_type_traits::ASTNodeKind::getFromNodeKind<QualType>();
+  auto TypeKind = ast_type_traits::ASTNodeKind::getFromNodeKind<Type>();
+  if (To.isSame(QualKind)) {
+    return SourceKind.isSame(TypeKind) || SourceKind.isSame(QualKind);
+  }
+  return SourceKind.isBaseOf(To);
+}
+
 DynTypedMatcher::MatcherStorage::~MatcherStorage() {}
 
 void BoundNodesTreeBuilder::addMatch(const BoundNodesTreeBuilder &Other) {
   for (unsigned i = 0, e = Other.Bindings.size(); i != e; ++i) {
     Bindings.push_back(Other.Bindings[i]);
   }
 }
 

lib/ASTMatchers/Dynamic/VariantValue.cpp

bool ArgKind::isConvertibleTo(ArgKind To, unsigned *Specificity) const {
   if (!MatcherKind.isBaseOf(To.MatcherKind, &Distance))
     return false;
 
   if (Specificity)
     *Specificity = 100 - Distance;
   return true;
 }
 
-VariantMatcher::MatcherOps::~MatcherOps() {}
+bool
+VariantMatcher::MatcherOps::canConstructFrom(const DynTypedMatcher &Matcher,
+                                             bool &IsExactMatch) const {
+  IsExactMatch = Matcher.getSupportedKind().isSame(NodeKind);
+  return Matcher.canConvertTo(NodeKind);
+}
+
+llvm::Optional<DynTypedMatcher>
+VariantMatcher::MatcherOps::constructVariadicOperator(
+    ast_matchers::internal::VariadicOperatorFunction Func,
+    ArrayRef<VariantMatcher> InnerMatchers) const {
+  std::vector<DynTypedMatcher> DynMatchers;
+  for (const auto &InnerMatcher : InnerMatchers) {
+    // Abort if any of the inner matchers can't be converted to
+    // Matcher<T>.
+    if (!InnerMatcher.Value)
+      return llvm::None;
+    llvm::Optional<DynTypedMatcher> Inner =
+        InnerMatcher.Value->getTypedMatcher(*this);
+    if (!Inner)
+      return llvm::None;
+    DynMatchers.push_back(*Inner);
+  }
+  return DynTypedMatcher::constructVariadic(Func, DynMatchers);
+}
+
 VariantMatcher::Payload::~Payload() {}
 
 class VariantMatcher::SinglePayload : public VariantMatcher::Payload {
 public:
   SinglePayload(const DynTypedMatcher &Matcher) : Matcher(Matcher) {}
 
   llvm::Optional<DynTypedMatcher> getSingleMatcher() const override {
     return Matcher;
   }
 
   std::string getTypeAsString() const override {
     return (Twine("Matcher<") + Matcher.getSupportedKind().asStringRef() + ">")
         .str();
   }
 
-  void makeTypedMatcher(MatcherOps &Ops) const override {
+  llvm::Optional<DynTypedMatcher>
+  getTypedMatcher(const MatcherOps &Ops) const override {
     bool Ignore;
     if (Ops.canConstructFrom(Matcher, Ignore))
-      Ops.constructFrom(Matcher);
+      return Matcher;
+    return llvm::None;
   }
 
   bool isConvertibleTo(ast_type_traits::ASTNodeKind Kind,
                        unsigned *Specificity) const override {
     return ArgKind(Matcher.getSupportedKind())
         .isConvertibleTo(Kind, Specificity);
   }
 
std::string getTypeAsString() const override {
     for (size_t i = 0, e = Matchers.size(); i != e; ++i) {
       if (i != 0)
         Inner += "|";
       Inner += Matchers[i].getSupportedKind().asStringRef();
     }
     return (Twine("Matcher<") + Inner + ">").str();
   }
 
-  void makeTypedMatcher(MatcherOps &Ops) const override {
+  llvm::Optional<DynTypedMatcher>
+  getTypedMatcher(const MatcherOps &Ops) const override {
     bool FoundIsExact = false;
     const DynTypedMatcher *Found = nullptr;
     int NumFound = 0;
     for (size_t i = 0, e = Matchers.size(); i != e; ++i) {
       bool IsExactMatch;
       if (Ops.canConstructFrom(Matchers[i], IsExactMatch)) {
         if (Found) {
           if (FoundIsExact) {
             assert(!IsExactMatch && "We should not have two exact matches.");
             continue;
           }
         }
         Found = &Matchers[i];
         FoundIsExact = IsExactMatch;
         ++NumFound;
       }
     }
     // We only succeed if we found exactly one, or if we found an exact match.
     if (Found && (FoundIsExact || NumFound == 1))
-      Ops.constructFrom(*Found);
+      return *Found;
+    return llvm::None;
   }
 
   bool isConvertibleTo(ast_type_traits::ASTNodeKind Kind,
                        unsigned *Specificity) const override {
     unsigned MaxSpecificity = 0;
     for (const DynTypedMatcher &Matcher : Matchers) {
       unsigned ThisSpecificity;
       if (ArgKind(Matcher.getSupportedKind())
std::string getTypeAsString() const override {
     for (size_t i = 0, e = Args.size(); i != e; ++i) {
       if (i != 0)
         Inner += "&";
       Inner += Args[i].getTypeAsString();
     }
     return Inner;
   }
 
-  void makeTypedMatcher(MatcherOps &Ops) const override {
-    Ops.constructVariadicOperator(Func, Args);
+  llvm::Optional<DynTypedMatcher>
+  getTypedMatcher(const MatcherOps &Ops) const override {
+    return Ops.constructVariadicOperator(Func, Args);
   }
 
   bool isConvertibleTo(ast_type_traits::ASTNodeKind Kind,
                        unsigned *Specificity) const override {
     for (const VariantMatcher &Matcher : Args) {
       if (!Matcher.isConvertibleTo(Kind, Specificity))
         return false;
     }