erik.pilkington created this revision.
This patch changes the demangler so that it represents substitutions/templates
more linearly. Previously, substitions were represented by a
`vector<vector<Node*>>` and template parameter substitutions by a
`vector<vector<vector<Node*>>>`! I wrote a comment in SubTable describing how
this is done.
This patch gives a 20%-25% time reduction to demangle the symbols in LLVM, a
25% reduction in code size for the demangler on my machine, and makes the
demangler a lot easier to read, IMO.
Thanks for taking a look!
Erik
https://reviews.llvm.org/D36427
Files:
src/cxa_demangle.cpp
Index: src/cxa_demangle.cpp
===================================================================
--- src/cxa_demangle.cpp
+++ src/cxa_demangle.cpp
@@ -1407,117 +1407,6 @@
}
};
-template <std::size_t N>
-class arena
-{
- static const std::size_t alignment = 16;
- alignas(alignment) char buf_[N];
- char* ptr_;
-
- std::size_t
- align_up(std::size_t n) noexcept
- {return (n + (alignment-1)) & ~(alignment-1);}
-
- bool
- pointer_in_buffer(char* p) noexcept
- {return buf_ <= p && p <= buf_ + N;}
-
-public:
- arena() noexcept : ptr_(buf_) {}
- ~arena() {ptr_ = nullptr;}
- arena(const arena&) = delete;
- arena& operator=(const arena&) = delete;
-
- char* allocate(std::size_t n);
- void deallocate(char* p, std::size_t n) noexcept;
-
- static constexpr std::size_t size() {return N;}
- std::size_t used() const {return static_cast<std::size_t>(ptr_ - buf_);}
- void reset() {ptr_ = buf_;}
-};
-
-template <std::size_t N>
-char*
-arena<N>::allocate(std::size_t n)
-{
- n = align_up(n);
- if (static_cast<std::size_t>(buf_ + N - ptr_) >= n)
- {
- char* r = ptr_;
- ptr_ += n;
- return r;
- }
- return static_cast<char*>(std::malloc(n));
-}
-
-template <std::size_t N>
-void
-arena<N>::deallocate(char* p, std::size_t n) noexcept
-{
- if (pointer_in_buffer(p))
- {
- n = align_up(n);
- if (p + n == ptr_)
- ptr_ = p;
- }
- else
- std::free(p);
-}
-
-template <class T, std::size_t N>
-class short_alloc
-{
- arena<N>& a_;
-public:
- typedef T value_type;
-
-public:
- template <class _Up> struct rebind {typedef short_alloc<_Up, N> other;};
-
- short_alloc(arena<N>& a) noexcept : a_(a) {}
- template <class U>
- short_alloc(const short_alloc<U, N>& a) noexcept
- : a_(a.a_) {}
- short_alloc(const short_alloc&) = default;
- short_alloc& operator=(const short_alloc&) = delete;
-
- T* allocate(std::size_t n)
- {
- return reinterpret_cast<T*>(a_.allocate(n*sizeof(T)));
- }
- void deallocate(T* p, std::size_t n) noexcept
- {
- a_.deallocate(reinterpret_cast<char*>(p), n*sizeof(T));
- }
-
- template <class T1, std::size_t N1, class U, std::size_t M>
- friend
- bool
- operator==(const short_alloc<T1, N1>& x, const short_alloc<U, M>& y) noexcept;
-
- template <class U, std::size_t M> friend class short_alloc;
-};
-
-template <class T, std::size_t N, class U, std::size_t M>
-inline
-bool
-operator==(const short_alloc<T, N>& x, const short_alloc<U, M>& y) noexcept
-{
- return N == M && &x.a_ == &y.a_;
-}
-
-template <class T, std::size_t N, class U, std::size_t M>
-inline
-bool
-operator!=(const short_alloc<T, N>& x, const short_alloc<U, M>& y) noexcept
-{
- return !(x == y);
-}
-
-const size_t bs = 4 * 1024;
-template <class T> using Alloc = short_alloc<T, bs>;
-template <class T> using Vector = std::vector<T, Alloc<T>>;
-
class BumpPointerAllocator {
struct BlockMeta {
BlockMeta* Next;
@@ -1568,13 +1457,179 @@
}
};
+template <class T, size_t N>
+class PODSmallVector {
+ static_assert(std::is_pod<T>::value, "");
+
+ T *First;
+ T *Last;
+ T *Cap;
+ T Inline[N];
+
+ bool isInline() const { return First == Inline; }
+
+public:
+ PODSmallVector() : First(Inline), Last(First), Cap(Inline + N) {}
+
+ PODSmallVector(const PODSmallVector &) = delete;
+ PODSmallVector& operator=(const PODSmallVector&) = delete;
+
+ PODSmallVector(PODSmallVector&& Other) {
+ if (Other.isInline()) {
+ std::copy(Other.begin(), Other.end(), Inline);
+ First = Inline;
+ Last = First + Other.size();
+ Cap = Inline + N;
+ Other.clear();
+ return;
+ }
+
+ First = Other.First;
+ Last = Other.Last;
+ Cap = Other.Cap;
+ Other.First = Other.Inline;
+ Other.Last = Other.Inline;
+ Other.Cap = Other.Inline + N;
+ }
+
+ PODSmallVector& operator=(PODSmallVector&& Other) {
+ if (Other.isInline()) {
+ if (!isInline()) {
+ std::free(First);
+ First = Inline;
+ Last = Inline;
+ Cap = Inline + N;
+ }
+ std::copy(Other.begin(), Other.end(), begin());
+ Last = First + Other.size();
+ return *this;
+ }
+
+ if (!isInline())
+ std::free(First);
+
+ First = Other.First;
+ Last = Other.Last;
+ Cap = Other.Cap;
+
+ Other.First = Other.Inline;
+ Other.Last = Other.Inline;
+ Other.Cap = Other.Inline + N;
+ return *this;
+ }
+
+ void push_back(const T &Elem) {
+ if (Last != Cap) {
+ *Last++ = Elem;
+ return;
+ }
+
+ size_t S = size();
+ if (!isInline()) {
+ First = static_cast<T*>(std::realloc(First, sizeof(T) * S * 2));
+ } else {
+ First = static_cast<T*>(std::malloc(sizeof(T) * S * 2));
+ std::copy(std::begin(Inline), std::end(Inline), First);
+ }
+ Last = First + S;
+ Cap = First + S * 2;
+ *Last++ = Elem;
+ return;
+ }
+
+ void pop_back() { --Last; }
+
+ void dropBack(size_t Index) { Last = First + Index; }
+
+ T *begin() { return First; }
+ T *end() { return Last; }
+
+ bool empty() const { return First == Last; }
+ size_t size() const { return static_cast<size_t>(Last - First); }
+ T& back() { return *(Last - 1); }
+ T& operator[](size_t Index) { return *(begin() + Index); }
+ void clear() { Last = First; }
+
+ ~PODSmallVector() {
+ if (!isInline())
+ std::free(First);
+ }
+};
+
+// Substitution table. This type is used to track the substitutions that are
+// known by the parser.
+template<size_t Size>
+class SubTable {
+ // Subs hold the actual entries in the table, and PackIndices tells us which
+ // entries are members of which pack. For example, if the substitutions we're
+ // tracking are: {int, {float, FooBar}, char}, with {float, FooBar} being a
+ // parameter pack, we represent the substitutions as:
+ // Subs: int, float, FooBar, char
+ // PackIndices: 0, 1, 3
+ // So, PackIndicies[I] holds the offset of the begin of the Ith pack, and
+ // PackIndices[I + 1] holds the offset of the end.
+ PODSmallVector<Node*, Size> Subs;
+ PODSmallVector<unsigned, Size> PackIndices;
+
+public:
+ // Add a substitution that represents a single name to the table. This is
+ // modeled as a parameter pack with just one element.
+ void pushSub(Node* Entry) {
+ PackIndices.push_back(static_cast<unsigned>(Subs.size()));
+ Subs.push_back(Entry);
+ }
+
+ // Add a new empty pack to the table. Subsequent calls to pushSubIntoPack()
+ // will add to this pack.
+ void pushPack() { PackIndices.push_back(static_cast<unsigned>(Subs.size())); }
+ void pushSubIntoPack(Node* Entry) { Subs.push_back(Entry); }
+
+ // Remove the last pack from the table.
+ void popPack() {
+ unsigned Last = PackIndices.back();
+ PackIndices.pop_back();
+ Subs.dropBack(Last);
+ }
+
+ // For use in a range-for loop.
+ struct NodePair {
+ Node **First;
+ Node **Last;
+ Node **begin() { return First; }
+ Node **end() { return Last; }
+ };
+
+ NodePair nthSub(size_t N) {
+ assert(N < PackIndices.size());
+ Node **Begin = Subs.begin() + PackIndices[N];
+ Node **End = (N + 1 == PackIndices.size())
+ ? Subs.end()
+ : Subs.begin() + PackIndices[N + 1];
+ return NodePair{Begin, End};
+ }
+
+ size_t size() const { return PackIndices.size(); }
+ bool empty() const { return PackIndices.empty(); }
+ void clear() {
+ Subs.clear();
+ PackIndices.clear();
+ }
+};
+
struct Db
{
- typedef Vector<Node*> sub_type;
- typedef Vector<sub_type> template_param_type;
- sub_type names;
- template_param_type subs;
- Vector<template_param_type> template_param;
+ // Name stack, this is used by the parser to hold temporary names that were
+ // parsed. The parser colapses multiple names into new nodes to construct
+ // the AST. Once the parser is finished, names.size() == 1.
+ PODSmallVector<Node*, 32> names;
+
+ // Substitution table. Itanium supports name substitutions as a means of
+ // compression. The string "S42_" refers to the 42nd entry in this table.
+ SubTable<32> Subs;
+
+ // Template parameter table. Like the above, but referenced like "T42_".
+ SubTable<4> TemplateParams;
+
Qualifiers cv = QualNone;
FunctionRefQual ref = FrefQualNone;
unsigned encoding_depth = 0;
@@ -1585,13 +1640,6 @@
BumpPointerAllocator ASTAllocator;
- template <size_t N>
- Db(arena<N>& ar) :
- names(ar),
- subs(0, names, ar),
- template_param(0, subs, ar)
- {}
-
template <class T, class... Args> T* make(Args&& ...args)
{
return new (ASTAllocator.allocate(sizeof(T)))
@@ -1612,7 +1660,7 @@
assert(FromPosition <= names.size());
NodeArray res = makeNodeArray(
names.begin() + (long)FromPosition, names.end());
- names.erase(names.begin() + (long)FromPosition, names.end());
+ names.dropBack(FromPosition);
return res;
}
};
@@ -1799,9 +1847,9 @@
first += 2;
break;
case '_':
- if (!db.subs.empty())
+ if (!db.Subs.empty())
{
- for (const auto& n : db.subs.front())
+ for (Node* n : db.Subs.nthSub(0))
db.names.push_back(n);
first += 2;
}
@@ -1826,9 +1874,9 @@
if (t == last || *t != '_')
return first;
++sub;
- if (sub < db.subs.size())
+ if (sub < db.Subs.size())
{
- for (const auto& n : db.subs[sub])
+ for (Node* n : db.Subs.nthSub(sub))
db.names.push_back(n);
first = t+1;
}
@@ -2058,11 +2106,9 @@
{
if (first[1] == '_')
{
- if (db.template_param.empty())
- return first;
- if (!db.template_param.back().empty())
+ if (!db.TemplateParams.empty())
{
- for (auto& t : db.template_param.back().front())
+ for (Node* t : db.TemplateParams.nthSub(0))
db.names.push_back(t);
first += 2;
}
@@ -2082,12 +2128,12 @@
sub *= 10;
sub += static_cast<size_t>(*t - '0');
}
- if (t == last || *t != '_' || db.template_param.empty())
+ if (t == last || *t != '_')
return first;
++sub;
- if (sub < db.template_param.back().size())
+ if (sub < db.TemplateParams.size())
{
- for (auto& temp : db.template_param.back()[sub])
+ for (Node* temp : db.TemplateParams.nthSub(sub))
db.names.push_back(temp);
first = t+1;
}
@@ -2469,7 +2515,7 @@
size_t k1 = db.names.size();
if (t != first && k1 == k0 + 1)
{
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
first = t;
}
else
@@ -2485,7 +2531,7 @@
{
if (db.names.empty())
return first;
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
first = t;
}
break;
@@ -2504,7 +2550,7 @@
return first;
db.names.back() =
db.make<StdQualifiedName>(db.names.back());
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
first = t;
}
}
@@ -2959,8 +3005,7 @@
db.names.begin() + (long)expr_list_begin);
auto* conv_expr = db.make<ConversionExpr>(
types, expressions);
- db.names.erase(
- db.names.begin() + (long)type_begin, db.names.end());
+ db.names.dropBack(type_begin);
db.names.push_back(conv_expr);
first = t;
}
@@ -3313,8 +3358,8 @@
if (t1 != t)
{
if (is_function)
- db.subs.pop_back();
- db.subs.emplace_back(db.names.get_allocator());
+ db.Subs.popPack();
+ db.Subs.pushPack();
for (size_t k = k0; k < k1; ++k)
{
if (cv) {
@@ -3325,7 +3370,7 @@
db.names[k] =
db.make<QualType>(db.names[k], cv);
}
- db.subs.back().push_back(db.names[k]);
+ db.Subs.pushSubIntoPack(db.names[k]);
}
first = t1;
}
@@ -3350,7 +3395,7 @@
if (db.names.empty())
return first;
first = t;
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
}
break;
case 'C':
@@ -3362,7 +3407,7 @@
db.names.back() = db.make<PostfixQualifiedType>(
db.names.back(), " complex");
first = t;
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
}
break;
case 'F':
@@ -3372,7 +3417,7 @@
if (db.names.empty())
return first;
first = t;
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
}
break;
case 'G':
@@ -3384,7 +3429,7 @@
db.names.back() = db.make<PostfixQualifiedType>(
db.names.back(), " imaginary");
first = t;
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
}
break;
case 'M':
@@ -3394,7 +3439,7 @@
if (db.names.empty())
return first;
first = t;
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
}
break;
case 'O':
@@ -3404,12 +3449,12 @@
size_t k1 = db.names.size();
if (t != first+1)
{
- db.subs.emplace_back(db.names.get_allocator());
+ db.Subs.pushPack();
for (size_t k = k0; k < k1; ++k)
{
db.names[k] =
db.make<RValueReferenceType>(db.names[k]);
- db.subs.back().push_back(db.names[k]);
+ db.Subs.pushSubIntoPack(db.names[k]);
}
first = t;
}
@@ -3422,11 +3467,11 @@
size_t k1 = db.names.size();
if (t != first+1)
{
- db.subs.emplace_back(db.names.get_allocator());
+ db.Subs.pushPack();
for (size_t k = k0; k < k1; ++k)
{
db.names[k] = db.make<PointerType>(db.names[k]);
- db.subs.back().push_back(db.names[k]);
+ db.Subs.pushSubIntoPack(db.names[k]);
}
first = t;
}
@@ -3439,12 +3484,12 @@
size_t k1 = db.names.size();
if (t != first+1)
{
- db.subs.emplace_back(db.names.get_allocator());
+ db.Subs.pushPack();
for (size_t k = k0; k < k1; ++k)
{
db.names[k] =
db.make<LValueReferenceType>(db.names[k]);
- db.subs.back().push_back(db.names[k]);
+ db.Subs.pushSubIntoPack(db.names[k]);
}
first = t;
}
@@ -3457,9 +3502,9 @@
size_t k1 = db.names.size();
if (t != first)
{
- db.subs.emplace_back(db.names.get_allocator());
+ db.Subs.pushPack();
for (size_t k = k0; k < k1; ++k)
- db.subs.back().push_back(db.names[k]);
+ db.Subs.pushSubIntoPack(db.names[k]);
if (db.try_to_parse_template_args && k1 == k0+1)
{
const char* t1 = parse_template_args(t, last, db);
@@ -3470,9 +3515,7 @@
db.names.back() = db.make<
NameWithTemplateArgs>(
db.names.back(), args);
- db.subs.push_back(Db::sub_type(
- 1, db.names.back(),
- db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
t = t1;
}
}
@@ -3512,7 +3555,7 @@
db.names.push_back(db.make<VendorExtQualType>(type, proto));
}
}
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
first = t2;
}
}
@@ -3526,7 +3569,7 @@
{
if (db.names.empty())
return first;
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
first = t;
}
}
@@ -3551,7 +3594,7 @@
NameWithTemplateArgs>(
db.names.back(), template_args);
// Need to create substitution for <template-template-param> <template-args>
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
first = t;
}
}
@@ -3570,9 +3613,9 @@
size_t k1 = db.names.size();
if (t != first+2)
{
- db.subs.emplace_back(db.names.get_allocator());
+ db.Subs.pushPack();
for (size_t k = k0; k < k1; ++k)
- db.subs.back().push_back(db.names[k]);
+ db.Subs.pushSubIntoPack(db.names[k]);
first = t;
return first;
}
@@ -3585,7 +3628,7 @@
{
if (db.names.empty())
return first;
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
first = t;
return first;
}
@@ -3596,7 +3639,7 @@
{
if (db.names.empty())
return first;
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
first = t;
return first;
}
@@ -3619,7 +3662,7 @@
{
if (db.names.empty())
return first;
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
first = t;
}
}
@@ -5119,27 +5162,35 @@
if (last - first >= 2 && *first == 'I')
{
if (db.tag_templates)
- db.template_param.back().clear();
+ db.TemplateParams.clear();
const char* t = first+1;
size_t begin_idx = db.names.size();
while (*t != 'E')
{
if (db.tag_templates)
- db.template_param.emplace_back(db.names.get_allocator());
- size_t k0 = db.names.size();
- const char* t1 = parse_template_arg(t, last, db);
- size_t k1 = db.names.size();
- if (db.tag_templates)
- db.template_param.pop_back();
- if (t1 == t || t1 == last || k0 > k1)
- return first;
- if (db.tag_templates)
{
- db.template_param.back().emplace_back(db.names.get_allocator());
+ auto TmpParams = std::move(db.TemplateParams);
+ size_t k0 = db.names.size();
+ const char* t1 = parse_template_arg(t, last, db);
+ size_t k1 = db.names.size();
+ db.TemplateParams = std::move(TmpParams);
+
+ if (t1 == t || t1 == last || k0 > k1)
+ return first;
+ db.TemplateParams.pushPack();
for (size_t k = k0; k < k1; ++k)
- db.template_param.back().back().push_back(db.names[k]);
+ db.TemplateParams.pushSubIntoPack(db.names[k]);
+ t = t1;
+ }
+ else
+ {
+ size_t k0 = db.names.size();
+ const char* t1 = parse_template_arg(t, last, db);
+ size_t k1 = db.names.size();
+ if (t1 == t || t1 == last || k0 > k1)
+ return first;
+ t = t1;
}
- t = t1;
}
if (begin_idx > db.names.size())
return first;
@@ -5218,9 +5269,7 @@
{
db.names.back() = db.make<QualifiedName>(
db.names.back(), name);
- db.subs.push_back(
- Db::sub_type(1, db.names.back(),
- db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
}
else
db.names.back() = name;
@@ -5243,7 +5292,7 @@
db.make<QualifiedName>(db.names.back(), name);
else
db.names.back() = name;
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
pop_subs = true;
t0 = t1;
}
@@ -5265,7 +5314,7 @@
db.make<QualifiedName>(db.names.back(), name);
else
db.names.back() = name;
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
pop_subs = true;
t0 = t1;
}
@@ -5282,8 +5331,7 @@
db.names.pop_back();
db.names.back() = db.make<NameWithTemplateArgs>(
db.names.back(), name);
- db.subs.push_back(Db::sub_type(
- 1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
t0 = t1;
component_ends_with_template_args = true;
}
@@ -5308,7 +5356,7 @@
db.make<QualifiedName>(db.names.back(), name);
else
db.names.back() = name;
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
pop_subs = true;
t0 = t1;
}
@@ -5318,8 +5366,8 @@
}
first = t0 + 1;
db.cv = cv;
- if (pop_subs && !db.subs.empty())
- db.subs.pop_back();
+ if (pop_subs && !db.Subs.empty())
+ db.Subs.popPack();
if (ends_with_template_args)
*ends_with_template_args = component_ends_with_template_args;
}
@@ -5484,7 +5532,7 @@
{
if (db.names.empty())
return first;
- db.subs.push_back(Db::sub_type(1, db.names.back(), db.names.get_allocator()));
+ db.Subs.pushSub(db.names.back());
t0 = t1;
t1 = parse_template_args(t0, last, db);
if (t1 != t0)
@@ -6035,21 +6083,19 @@
}
size_t internal_size = buf != nullptr ? *n : 0;
- arena<bs> a;
- Db db(a);
- db.template_param.emplace_back(a);
+ Db db;
int internal_status = success;
size_t len = std::strlen(mangled_name);
demangle(mangled_name, mangled_name + len, db,
internal_status);
if (internal_status == success && db.fix_forward_references &&
- !db.template_param.empty() && !db.template_param.front().empty())
+ !db.TemplateParams.empty())
{
db.fix_forward_references = false;
db.tag_templates = false;
db.names.clear();
- db.subs.clear();
+ db.Subs.clear();
demangle(mangled_name, mangled_name + len, db, internal_status);
if (db.fix_forward_references)
internal_status = invalid_mangled_name;
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
