[AST] Squeeze some bits in LinkageComputer

[riccibruno]

Summary

Since Decls are already aligned explicitly to 8 bytes, stash the
3 bits representing an LVComputationKind into the lower 3 bits
of the NamedDecl * in LinkageComputer.

[erichkeane]

Does this still work with 32 bit hosts? Does PointerIntPair have 3 bits in that case? Is the alignof static_assert valid in that case?

lib/AST/Linkage.h

40 ↗

(On Diff #166137)

I'm not sure how often this ever gets modified, but it is a touch scary to me that we've already maxed out the size of this struct.

89 ↗

(On Diff #166137)

Is this not guaranteed by the static-assert in pointerintpair?

[riccibruno]

In D52268#1239538, @erichkeane wrote:

Does this still work with 32 bit hosts? Does PointerIntPair have 3 bits in that case? Is the alignof static_assert valid in that case?

I think it does since Decl is manually over-aligned to 8 bytes. But you are right that the static_assert is probably not needed
here since llvm::PointerIntPair checks that the low bits are available.

I'm not sure how often this ever gets modified, but it is a touch scary to me that we've already maxed out the size of this struct.

I am not sure either... It was just a quick change I spotted and this is borderline not worth doing. If you think that we ought to keep
some space left I will abandon this revision.

[erichkeane]

In D52268#1239557, @riccibruno wrote:

In D52268#1239538, @erichkeane wrote:

Does this still work with 32 bit hosts? Does PointerIntPair have 3 bits in that case? Is the alignof static_assert valid in that case?

I think it does since Decl is manually over-aligned to 8 bytes. But you are right that the static_assert is probably not needed
here since llvm::PointerIntPair checks that the low bits are available.

I'm not sure how often this ever gets modified, but it is a touch scary to me that we've already maxed out the size of this struct.

I am not sure either... It was just a quick change I spotted and this is borderline not worth doing. If you think that we ought to keep
some space left I will abandon this revision.

I did a little digging on this, and it seems to be to keep track of a declarations linkage for caching sake. Unless the committees change linkage at all, I guess I don't see this changing much. I think my concerns are assuaged.

That said, I'm adding @george.burgess.iv (or @gbiv ?) to the review, since he's the original author.

[george.burgess.iv]

Thanks for this! LGTM after erichkeane's comments are resolved.

I did a little digging on this, and it seems to be to keep track of a declarations linkage for caching sake

Yeah, otherwise, we get exponential behavior on some pathological template-y patterns.

lib/AST/Linkage.h

93 ↗

(On Diff #166137)

(FWIW, it looks like PointerIntPairInfo::UpdateInt asserts that Kind.toBits() fits nicely in NumLVComputationKindBits. So if anything gets added, it'll yell and we can just revert to the current way of doing this :) )

[riccibruno]

Removed the superfluous static_assert.

[rjmccall]

LinkageComputer isn't actually persisted anywhere, right? And there's maybe one computer active at once? So this compression is theoretically saving one pointer of stack space but forcing a bunch of bit-manipulation every time these fields are accessed.

[riccibruno]

In D52268#1241033, @rjmccall wrote:

LinkageComputer isn't actually persisted anywhere, right? And there's maybe one computer active at once? So this compression is theoretically saving one pointer of stack space but forcing a bunch of bit-manipulation every time these fields are accessed.

It is not persisted but this saves one pointer per entry in the map. Another factor is that hashing a pair involves hashing
each component and then combining the result, which is comparatively much more expansive than just hashing a PointerIntPair,
which involves only a shift and a xor. The field storing the LVComputationKind is never directly read but only used to differentiate
various kinds of computations in the map. I went back and instrumented the lookup function LinkageComputer::lookup with rdtsc,
and (with all the usual caveats about microbenchmarks and rdtsc) I get that this cuts the number of ticks spent inside lookup
from about 8e6 to 3.5e6. Now of course taking a step back this represent only milliseconds and is firmly in the category of
"way to small to bother", but now we might as well do it.

[rjmccall]

In D52268#1241793, @riccibruno wrote:

In D52268#1241033, @rjmccall wrote:

LinkageComputer isn't actually persisted anywhere, right? And there's maybe one computer active at once? So this compression is theoretically saving one pointer of stack space but forcing a bunch of bit-manipulation every time these fields are accessed.

It is not persisted but this saves one pointer per entry in the map. Another factor is that hashing a pair involves hashing
each component and then combining the result, which is comparatively much more expansive than just hashing a PointerIntPair,
which involves only a shift and a xor. The field storing the LVComputationKind is never directly read but only used to differentiate
various kinds of computations in the map. I went back and instrumented the lookup function LinkageComputer::lookup with rdtsc,
and (with all the usual caveats about microbenchmarks and rdtsc) I get that this cuts the number of ticks spent inside lookup
from about 8e6 to 3.5e6. Now of course taking a step back this represent only milliseconds and is firmly in the category of
"way to small to bother", but now we might as well do it.

Oh, I see, the commit summary is wrong. You're not compressing LinkageComputer, you're compressing a lookup key type. LGTM.

[george.burgess.iv]

LGTM too.

Thanks again!

cfe/trunk/lib/AST/Linkage.h

 #ifndef LLVM_CLANG_LIB_AST_LINKAGE_H
 #define LLVM_CLANG_LIB_AST_LINKAGE_H
 
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/Type.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/PointerIntPair.h"
 
 namespace clang {
 /// Kinds of LV computation.  The linkage side of the computation is
 /// always the same, but different things can change how visibility is
 /// computed.
 struct LVComputationKind {
   /// The kind of entity whose visibility is ultimately being computed;
   /// visibility computations for types and non-types follow different rules.
   unsigned ExplicitKind : 1;
   /// Whether explicit visibility attributes should be ignored. When set,
   /// visibility may only be restricted by the visibility of template arguments.
   unsigned IgnoreExplicitVisibility : 1;
   /// Whether all visibility should be ignored. When set, we're only interested
   /// in computing linkage.
   unsigned IgnoreAllVisibility : 1;
 
+  enum { NumLVComputationKindBits = 3 };
+
   explicit LVComputationKind(NamedDecl::ExplicitVisibilityKind EK)
       : ExplicitKind(EK), IgnoreExplicitVisibility(false),
         IgnoreAllVisibility(false) {}
 
   NamedDecl::ExplicitVisibilityKind getExplicitVisibilityKind() const {
     return static_cast<NamedDecl::ExplicitVisibilityKind>(ExplicitKind);
   }
 
class LinkageComputer {
   // from exponential behavior in heavily templated code, such as:
   //
   // template <typename T, typename V> struct {};
   // using A = int;
   // using B = Foo<A, A>;
   // using C = Foo<B, B>;
   // using D = Foo<C, C>;
   //
-  // The unsigned represents an LVComputationKind.
-  using QueryType = std::pair<const NamedDecl *, unsigned>;
+  // The integer represents an LVComputationKind.
+  using QueryType =
+      llvm::PointerIntPair<const NamedDecl *,
+                           LVComputationKind::NumLVComputationKindBits>;
   llvm::SmallDenseMap<QueryType, LinkageInfo, 8> CachedLinkageInfo;
 
   static QueryType makeCacheKey(const NamedDecl *ND, LVComputationKind Kind) {
-    return std::make_pair(ND, Kind.toBits());
+    return QueryType(ND, Kind.toBits());
   }
 
   llvm::Optional<LinkageInfo> lookup(const NamedDecl *ND,
                                      LVComputationKind Kind) const {
     auto Iter = CachedLinkageInfo.find(makeCacheKey(ND, Kind));
     if (Iter == CachedLinkageInfo.end())
       return None;
     return Iter->second;