[PATCH] D52268: [AST] Squeeze some bits in LinkageComputer
This revision was automatically updated to reflect the committed changes.
Closed by commit rL342973: [AST] Squeeze some bits in
LinkageComputer::QueryType (authored by brunoricci, committed by ).
Herald added a subscriber: llvm-commits.
Changed prior to commit:
https://reviews.llvm.org/D52268?vs=166264=166875#toc
Repository:
rL LLVM
https://reviews.llvm.org/D52268
Files:
cfe/trunk/lib/AST/Linkage.h
Index: cfe/trunk/lib/AST/Linkage.h
===
--- cfe/trunk/lib/AST/Linkage.h
+++ cfe/trunk/lib/AST/Linkage.h
@@ -20,6 +20,7 @@
#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
@@ -36,6 +37,8 @@
/// in computing linkage.
unsigned IgnoreAllVisibility : 1;
+ enum { NumLVComputationKindBits = 3 };
+
explicit LVComputationKind(NamedDecl::ExplicitVisibilityKind EK)
: ExplicitKind(EK), IgnoreExplicitVisibility(false),
IgnoreAllVisibility(false) {}
@@ -78,12 +81,14 @@
// using C = Foo;
// using D = Foo;
//
- // The unsigned represents an LVComputationKind.
- using QueryType = std::pair;
+ // The integer represents an LVComputationKind.
+ using QueryType =
+ llvm::PointerIntPair;
llvm::SmallDenseMap CachedLinkageInfo;
static QueryType makeCacheKey(const NamedDecl *ND, LVComputationKind Kind) {
-return std::make_pair(ND, Kind.toBits());
+return QueryType(ND, Kind.toBits());
}
llvm::Optional lookup(const NamedDecl *ND,
Index: cfe/trunk/lib/AST/Linkage.h
===
--- cfe/trunk/lib/AST/Linkage.h
+++ cfe/trunk/lib/AST/Linkage.h
@@ -20,6 +20,7 @@
#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
@@ -36,6 +37,8 @@
/// in computing linkage.
unsigned IgnoreAllVisibility : 1;
+ enum { NumLVComputationKindBits = 3 };
+
explicit LVComputationKind(NamedDecl::ExplicitVisibilityKind EK)
: ExplicitKind(EK), IgnoreExplicitVisibility(false),
IgnoreAllVisibility(false) {}
@@ -78,12 +81,14 @@
// using C = Foo;
// using D = Foo;
//
- // The unsigned represents an LVComputationKind.
- using QueryType = std::pair;
+ // The integer represents an LVComputationKind.
+ using QueryType =
+ llvm::PointerIntPair;
llvm::SmallDenseMap CachedLinkageInfo;
static QueryType makeCacheKey(const NamedDecl *ND, LVComputationKind Kind) {
-return std::make_pair(ND, Kind.toBits());
+return QueryType(ND, Kind.toBits());
}
llvm::Optional lookup(const NamedDecl *ND,
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D52268: [AST] Squeeze some bits in LinkageComputer
george.burgess.iv accepted this revision. george.burgess.iv added a comment. LGTM too. Thanks again! Repository: rC Clang https://reviews.llvm.org/D52268 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D52268: [AST] Squeeze some bits in LinkageComputer
rjmccall accepted this revision. rjmccall added a comment. This revision is now accepted and ready to land. In https://reviews.llvm.org/D52268#1241793, @riccibruno wrote: > In https://reviews.llvm.org/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. Repository: rC Clang https://reviews.llvm.org/D52268 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D52268: [AST] Squeeze some bits in LinkageComputer
riccibruno added a comment. In https://reviews.llvm.org/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. Repository: rC Clang https://reviews.llvm.org/D52268 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D52268: [AST] Squeeze some bits in LinkageComputer
rjmccall added a comment. `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. Repository: rC Clang https://reviews.llvm.org/D52268 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D52268: [AST] Squeeze some bits in LinkageComputer
riccibruno updated this revision to Diff 166264.
riccibruno marked 3 inline comments as done.
riccibruno added a comment.
Removed the superfluous static_assert.
Repository:
rC Clang
https://reviews.llvm.org/D52268
Files:
lib/AST/Linkage.h
Index: lib/AST/Linkage.h
===
--- lib/AST/Linkage.h
+++ lib/AST/Linkage.h
@@ -20,6 +20,7 @@
#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
@@ -36,6 +37,8 @@
/// in computing linkage.
unsigned IgnoreAllVisibility : 1;
+ enum { NumLVComputationKindBits = 3 };
+
explicit LVComputationKind(NamedDecl::ExplicitVisibilityKind EK)
: ExplicitKind(EK), IgnoreExplicitVisibility(false),
IgnoreAllVisibility(false) {}
@@ -78,12 +81,14 @@
// using C = Foo;
// using D = Foo;
//
- // The unsigned represents an LVComputationKind.
- using QueryType = std::pair;
+ // The integer represents an LVComputationKind.
+ using QueryType =
+ llvm::PointerIntPair;
llvm::SmallDenseMap CachedLinkageInfo;
static QueryType makeCacheKey(const NamedDecl *ND, LVComputationKind Kind) {
-return std::make_pair(ND, Kind.toBits());
+return QueryType(ND, Kind.toBits());
}
llvm::Optional lookup(const NamedDecl *ND,
Index: lib/AST/Linkage.h
===
--- lib/AST/Linkage.h
+++ lib/AST/Linkage.h
@@ -20,6 +20,7 @@
#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
@@ -36,6 +37,8 @@
/// in computing linkage.
unsigned IgnoreAllVisibility : 1;
+ enum { NumLVComputationKindBits = 3 };
+
explicit LVComputationKind(NamedDecl::ExplicitVisibilityKind EK)
: ExplicitKind(EK), IgnoreExplicitVisibility(false),
IgnoreAllVisibility(false) {}
@@ -78,12 +81,14 @@
// using C = Foo;
// using D = Foo;
//
- // The unsigned represents an LVComputationKind.
- using QueryType = std::pair;
+ // The integer represents an LVComputationKind.
+ using QueryType =
+ llvm::PointerIntPair;
llvm::SmallDenseMap CachedLinkageInfo;
static QueryType makeCacheKey(const NamedDecl *ND, LVComputationKind Kind) {
-return std::make_pair(ND, Kind.toBits());
+return QueryType(ND, Kind.toBits());
}
llvm::Optional lookup(const NamedDecl *ND,
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D52268: [AST] Squeeze some bits in LinkageComputer
george.burgess.iv added a comment.
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.
Comment at: lib/AST/Linkage.h:93
static QueryType makeCacheKey(const NamedDecl *ND, LVComputationKind Kind) {
-return std::make_pair(ND, Kind.toBits());
+return QueryType(ND, Kind.toBits());
}
(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 :) )
Repository:
rC Clang
https://reviews.llvm.org/D52268
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D52268: [AST] Squeeze some bits in LinkageComputer
erichkeane added subscribers: gbiv, george.burgess.iv. erichkeane added a comment. In https://reviews.llvm.org/D52268#1239557, @riccibruno wrote: > In https://reviews.llvm.org/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. Repository: rC Clang https://reviews.llvm.org/D52268 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D52268: [AST] Squeeze some bits in LinkageComputer
riccibruno added a comment. In https://reviews.llvm.org/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. Repository: rC Clang https://reviews.llvm.org/D52268 ___ cfe-commits mailing list cfe-commits@lists.llvm.org http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D52268: [AST] Squeeze some bits in LinkageComputer
erichkeane added a comment.
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?
Comment at: lib/AST/Linkage.h:40
+ enum { NumLVComputationKindBits = 3 };
+
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.
Comment at: lib/AST/Linkage.h:89
llvm::SmallDenseMap CachedLinkageInfo;
+ static_assert(alignof(NamedDecl) >= 8,
+"LinkageComputer assumes that NamedDecl is aligned to >= 8!");
Is this not guaranteed by the static-assert in pointerintpair?
Repository:
rC Clang
https://reviews.llvm.org/D52268
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
[PATCH] D52268: [AST] Squeeze some bits in LinkageComputer
riccibruno created this revision.
riccibruno added reviewers: erichkeane, rjmccall.
riccibruno added a project: clang.
Herald added a subscriber: cfe-commits.
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.
Repository:
rC Clang
https://reviews.llvm.org/D52268
Files:
lib/AST/Linkage.h
Index: lib/AST/Linkage.h
===
--- lib/AST/Linkage.h
+++ lib/AST/Linkage.h
@@ -20,6 +20,7 @@
#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
@@ -36,6 +37,8 @@
/// in computing linkage.
unsigned IgnoreAllVisibility : 1;
+ enum { NumLVComputationKindBits = 3 };
+
explicit LVComputationKind(NamedDecl::ExplicitVisibilityKind EK)
: ExplicitKind(EK), IgnoreExplicitVisibility(false),
IgnoreAllVisibility(false) {}
@@ -78,12 +81,16 @@
// using C = Foo;
// using D = Foo;
//
- // The unsigned represents an LVComputationKind.
- using QueryType = std::pair;
+ // The integer represents an LVComputationKind.
+ using QueryType =
+ llvm::PointerIntPair;
llvm::SmallDenseMap CachedLinkageInfo;
+ static_assert(alignof(NamedDecl) >= 8,
+"LinkageComputer assumes that NamedDecl is aligned to >= 8!");
static QueryType makeCacheKey(const NamedDecl *ND, LVComputationKind Kind) {
-return std::make_pair(ND, Kind.toBits());
+return QueryType(ND, Kind.toBits());
}
llvm::Optional lookup(const NamedDecl *ND,
Index: lib/AST/Linkage.h
===
--- lib/AST/Linkage.h
+++ lib/AST/Linkage.h
@@ -20,6 +20,7 @@
#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
@@ -36,6 +37,8 @@
/// in computing linkage.
unsigned IgnoreAllVisibility : 1;
+ enum { NumLVComputationKindBits = 3 };
+
explicit LVComputationKind(NamedDecl::ExplicitVisibilityKind EK)
: ExplicitKind(EK), IgnoreExplicitVisibility(false),
IgnoreAllVisibility(false) {}
@@ -78,12 +81,16 @@
// using C = Foo;
// using D = Foo;
//
- // The unsigned represents an LVComputationKind.
- using QueryType = std::pair;
+ // The integer represents an LVComputationKind.
+ using QueryType =
+ llvm::PointerIntPair;
llvm::SmallDenseMap CachedLinkageInfo;
+ static_assert(alignof(NamedDecl) >= 8,
+"LinkageComputer assumes that NamedDecl is aligned to >= 8!");
static QueryType makeCacheKey(const NamedDecl *ND, LVComputationKind Kind) {
-return std::make_pair(ND, Kind.toBits());
+return QueryType(ND, Kind.toBits());
}
llvm::Optional lookup(const NamedDecl *ND,
___
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
