[clang] Optimized ASTNodeKind::isBaseOf

[alexfh]

Summary

ASTNodeKind::isBaseOf shows in one of the top lines of the profile when running a large clang-tidy benchmark. This rewrite reduces its cumulative time from 6.14% to 3.7%:

<     11.06s  6.14%: clang::ast_type_traits::ASTNodeKind::isBaseOf
>     5.75s  3.70%: clang::ast_type_traits::ASTNodeKind::isBaseOf

[alexfh]

Remove .gitignore from the patch.

[klimek]

lib/AST/ASTTypeTraits.cpp

50

For my sanity: please one side-effect per line.

63

For my sanity: please one side-effect per line.

[alexfh]

One side-effect per line.

[klimek]

lib/AST/ASTTypeTraits.cpp

46

Also, perhaps declare a constant to std::numeric_limits<unsigned>::max()?

60

Not sure whether we care about thread safety here (and VS <= 2013 still not providing it).

[sbenza]

I have been looking up different ways to do this more efficiently.
There are two reasons the current one is slow: while() loop and loading cold memory for AllKindInfo array.

This CL is one of the solutions I looked into. It removes the while() loop, but makes the caching behavior way worse.
At the very least, ParentDistances should be an array of uint8 to reduce the cache pressure here.

Other solutions I was thinking of require no external memory. That is, you can tell whether they are related (and the distance) from the node ids themselves.
I haven't benchmarked them to determine which one is better. I was waiting on it until isBaseOf() is the largest improvement I can make to get a better comparison.

A list of solutions:
1 Caching the solution (something like this CL).

It requires a half matrix of 1-bit per pair cell. ~290 types so ~5k of memory.
Distance can be calculated as the difference of their depths. Can be stored in nodes or external. External is around ~1k.
(The current CL creates a matrix of ~330k!)

2 Something similar to dyn_cast<> where each node knows the range of their descendants.

The 'last' id can be saved in a separate array or inside the node.
The calculation becomes two comparisons.
Distance can be calculated as the difference of their depths. Can also be stored in the nodes.
If all stored in nodes, requires no external memory and no loops.

3 Each node gets a unique sequential ID.

Then the real node id is: NI(X) = NI(Parent(X)) << 8 + UID(X)
These Ids can be easily generated at compile time.
It requires a loop to find the answer, but no external memory.
Distance is calculated in the loop.

4 Each node gets a unique prime.

Then the real node id is: NI(X) = NI(Parent(X)) * Prime(X)
The operation becomes a simple modulo operation. No external memory.
Distance comes from somewhere else.

I do not like (1) because we can solve this without the external memory.
(2) is fine, but was not easy to implement right now. Type class enums do not have firstXXX/lastXXX definitions.
I implemented (3) and it is not complicated. It still has the loop, though.
(4) is cute, but it might require some work to fit all the ids in a uint64. There are some deeply nested hierarchies.

[bkramer]

I wonder if we care about the performance of getting the distance at all, it's only used to create dynamic matchers afaik. Making the non-distance measurement case fast and leaving the case with distances as-is would help clang-tidy and allows a simpler implementation.

[sbenza]

bkramer is right.
However, the distance is not even used to *create* the dynamic matchers. It is only used for the completion used by clang-query.
So a cheap and simple isBaseOf() should do it. The distance could be separate.

[alexfh]

One important thing this patch does, it splits isBaseOf with and without distance to avoid runtime selection.

As for the caching, I believe it doesn't matter much, as on my test (lib/Sema/SemaOverload.cpp) most of the calls were asking one of a small number of table cells. Here's some data:

• total calls: ~39M
• total number of pairs asked: 1646
• 103 mostly asked cells cover 80% of all calls
• 219 mostly asked cells cover 90% of all calls
• 50 mostly asked rows (< 6kB) cover 97% of all calls

The other solutions you've proposed are also interesting (especially #4 which is the most elegant, but requires some care in arranging the primes), but this one is the most straightforward, IMO.

[sbenza]

It is still bad that it allocates more than 300k of heap, and then it doesn't even use most of it.

I have a prototype of (4) at http://reviews.llvm.org/differential/diff/14336/
Haven't benchmarked it yet.

[alexfh]

In D5577#18, @sbenza wrote:

It is still bad that it allocates more than 300k of heap, and then it doesn't even use most of it.

It's ~90k of heap (after changing unsigned to unsigned char). But if you'll manage to get a decent implementation of (4), it would be nice. I'll leave this patch here in case there is no better solution.

I have a prototype of (4) at http://reviews.llvm.org/differential/diff/14336/
Haven't benchmarked it yet.

[alexfh]

Use unsigned char for ParentDistances.

include/clang/AST/ASTTypeTraits.h

public:
   static ASTNodeKind getFromNode(const Stmt &S);
   static ASTNodeKind getFromNode(const Type &T);
   /// \}
 
   /// \brief Returns \c true if \c this and \c Other represent the same kind.
   bool isSame(ASTNodeKind Other) const;
 
   /// \brief Returns \c true if \c this is a base kind of (or same as) \c Other.
+  bool isBaseOf(ASTNodeKind Other) const;
+
+  /// \brief Returns \c true if \c this is a base kind of (or same as) \c Other.
   /// \param Distance If non-null, used to return the distance between \c this
   /// and \c Other in the class hierarchy.
-  bool isBaseOf(ASTNodeKind Other, unsigned *Distance = nullptr) const;
+  bool isBaseOf(ASTNodeKind Other, unsigned &Distance) const;
 
   /// \brief String representation of the kind.
   StringRef asStringRef() const;
 
   /// \brief Strict weak ordering for ASTNodeKind.
   bool operator<(const ASTNodeKind &Other) const {
     return KindId < Other.KindId;
   }

 #define STMT(DERIVED, BASE) NKI_##DERIVED,
 #include "clang/AST/StmtNodes.inc"
     NKI_Type,
 #define TYPE(DERIVED, BASE) NKI_##DERIVED##Type,
 #include "clang/AST/TypeNodes.def"
     NKI_NumberOfKinds
   };
 
+  struct NodeParentMap;
+
   /// \brief Use getFromNodeKind<T>() to construct the kind.
   ASTNodeKind(NodeKindId KindId) : KindId(KindId) {}
 
-  /// \brief Returns \c true if \c Base is a base kind of (or same as) \c
-  ///   Derived.
-  /// \param Distance If non-null, used to return the distance between \c Base
-  /// and \c Derived in the class hierarchy.
-  static bool isBaseOf(NodeKindId Base, NodeKindId Derived, unsigned *Distance);
-
   /// \brief Helper meta-function to convert a kind T to its enum value.
   ///
   /// This struct is specialized below for all known kinds.
   template <class T> struct KindToKindId {
     static const NodeKindId Id = NKI_None;
   };
 
   /// \brief Per kind info.

lib/AST/ASTTypeTraits.cpp

#include "clang/AST/DeclNodes.inc"
   { NKI_None, "Stmt" },
 #define STMT(DERIVED, BASE) { NKI_##BASE, #DERIVED },
 #include "clang/AST/StmtNodes.inc"
   { NKI_None, "Type" },
 #define TYPE(DERIVED, BASE) { NKI_##BASE, #DERIVED "Type" },
 #include "clang/AST/TypeNodes.def"
 };
 
-bool ASTNodeKind::isBaseOf(ASTNodeKind Other, unsigned *Distance) const {
-  return isBaseOf(KindId, Other.KindId, Distance);
+struct ASTNodeKind::NodeParentMap {
+  NodeParentMap() {
+    for (unsigned Node = NKI_None; Node < NKI_NumberOfKinds; ++Node) {
+      for (unsigned Parent = NKI_None; Parent < NKI_NumberOfKinds; ++Parent)
+        ParentDistances[Node][Parent] = NotParent;
+      unsigned Distance = 0;
+      for (unsigned Parent = Node; Parent != NKI_None;
+           Parent = ASTNodeKind::AllKindInfo[Parent].ParentId) {
+        ParentDistances[Node][Parent] = Distance;
+        ++Distance;
+      }
+    }
   }
 
-bool ASTNodeKind::isSame(ASTNodeKind Other) const {
-  return KindId != NKI_None && KindId == Other.KindId;
+  static const unsigned char NotParent = 255;
+  unsigned char ParentDistances[NKI_NumberOfKinds][NKI_NumberOfKinds];
+};
+
+bool ASTNodeKind::isBaseOf(ASTNodeKind Other) const {
+  static const NodeParentMap *Map = new NodeParentMap;
+  return Map->ParentDistances[Other.KindId][KindId] != NodeParentMap::NotParent;
+}
+bool ASTNodeKind::isBaseOf(ASTNodeKind Other, unsigned &Distance) const {
+  static const NodeParentMap *Map = new NodeParentMap;
+  Distance = Map->ParentDistances[Other.KindId][KindId];
+  return Distance != NodeParentMap::NotParent;
 }
 
-bool ASTNodeKind::isBaseOf(NodeKindId Base, NodeKindId Derived,
-                           unsigned *Distance) {
-  if (Base == NKI_None || Derived == NKI_None) return false;
-  unsigned Dist = 0;
-  while (Derived != Base && Derived != NKI_None) {
-    Derived = AllKindInfo[Derived].ParentId;
-    ++Dist;
-  }
-  if (Distance)
-    *Distance = Dist;
-  return Derived == Base;
+bool ASTNodeKind::isSame(ASTNodeKind Other) const {
+  return KindId != NKI_None && KindId == Other.KindId;
 }
 
 StringRef ASTNodeKind::asStringRef() const { return AllKindInfo[KindId].Name; }
 
 ASTNodeKind ASTNodeKind::getFromNode(const Decl &D) {
   switch (D.getKind()) {
 #define DECL(DERIVED, BASE)                                                    \
     case Decl::DERIVED: return ASTNodeKind(NKI_##DERIVED##Decl);

lib/ASTMatchers/Dynamic/VariantValue.cpp

bool ArgKind::isConvertibleTo(ArgKind To, unsigned *Specificity) const {
   if (K != To.K)
     return false;
   if (K != AK_Matcher) {
     if (Specificity)
       *Specificity = 1;
     return true;
   }
   unsigned Distance;
-  if (!MatcherKind.isBaseOf(To.MatcherKind, &Distance))
+  if (!MatcherKind.isBaseOf(To.MatcherKind, Distance))
     return false;
 
   if (Specificity)
     *Specificity = 100 - Distance;
   return true;
 }
 
 bool

unittests/AST/ASTTypeTraitsTest.cpp

TEST(ASTNodeKind, Bases) {
   EXPECT_FALSE(DNT<Decl>().isSame(DNT<VarDecl>()));
   EXPECT_FALSE(DNT<VarDecl>().isBaseOf(DNT<Decl>()));
 
   EXPECT_TRUE(DNT<Decl>().isSame(DNT<Decl>()));
 }
 
 TEST(ASTNodeKind, BaseDistances) {
   unsigned Distance = 1;
-  EXPECT_TRUE(DNT<Expr>().isBaseOf(DNT<Expr>(), &Distance));
+  EXPECT_TRUE(DNT<Expr>().isBaseOf(DNT<Expr>(), Distance));
   EXPECT_EQ(0u, Distance);
 
-  EXPECT_TRUE(DNT<Stmt>().isBaseOf(DNT<IfStmt>(), &Distance));
+  EXPECT_TRUE(DNT<Stmt>().isBaseOf(DNT<IfStmt>(), Distance));
   EXPECT_EQ(1u, Distance);
 
   Distance = 3;
-  EXPECT_TRUE(DNT<DeclaratorDecl>().isBaseOf(DNT<ParmVarDecl>(), &Distance));
+  EXPECT_TRUE(DNT<DeclaratorDecl>().isBaseOf(DNT<ParmVarDecl>(), Distance));
   EXPECT_EQ(2u, Distance);
 }
 
 TEST(ASTNodeKind, SameBase) {
   EXPECT_TRUE(DNT<Expr>().isBaseOf(DNT<CallExpr>()));
   EXPECT_TRUE(DNT<Expr>().isBaseOf(DNT<BinaryOperator>()));
   EXPECT_FALSE(DNT<CallExpr>().isBaseOf(DNT<BinaryOperator>()));
   EXPECT_FALSE(DNT<BinaryOperator>().isBaseOf(DNT<CallExpr>()));