Line data Source code
1 : //===- StringTableBuilder.cpp - String table building utility -------------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 :
10 : #include "llvm/MC/StringTableBuilder.h"
11 : #include "llvm/ADT/CachedHashString.h"
12 : #include "llvm/ADT/SmallString.h"
13 : #include "llvm/ADT/StringRef.h"
14 : #include "llvm/BinaryFormat/COFF.h"
15 : #include "llvm/Support/Endian.h"
16 : #include "llvm/Support/MathExtras.h"
17 : #include "llvm/Support/raw_ostream.h"
18 : #include <cassert>
19 : #include <cstddef>
20 : #include <cstdint>
21 : #include <cstring>
22 : #include <utility>
23 : #include <vector>
24 :
25 : using namespace llvm;
26 :
27 : StringTableBuilder::~StringTableBuilder() = default;
28 :
29 109153 : void StringTableBuilder::initSize() {
30 : // Account for leading bytes in table so that offsets returned from add are
31 : // correct.
32 109153 : switch (K) {
33 79154 : case RAW:
34 : case DWARF:
35 79154 : Size = 0;
36 79154 : break;
37 28519 : case MachO:
38 : case ELF:
39 : // Start the table with a NUL byte.
40 28519 : Size = 1;
41 28519 : break;
42 1480 : case WinCOFF:
43 : // Make room to write the table size later.
44 1480 : Size = 4;
45 1480 : break;
46 : }
47 109153 : }
48 :
49 95661 : StringTableBuilder::StringTableBuilder(Kind K, unsigned Alignment)
50 95661 : : K(K), Alignment(Alignment) {
51 95661 : initSize();
52 95661 : }
53 :
54 12659 : void StringTableBuilder::write(raw_ostream &OS) const {
55 : assert(isFinalized());
56 : SmallString<0> Data;
57 12659 : Data.resize(getSize());
58 12659 : write((uint8_t *)Data.data());
59 : OS << Data;
60 12658 : }
61 :
62 : using StringPair = std::pair<CachedHashStringRef, size_t>;
63 :
64 87274 : void StringTableBuilder::write(uint8_t *Buf) const {
65 : assert(isFinalized());
66 1594653 : for (const StringPair &P : StringIndexMap) {
67 1420105 : StringRef Data = P.first.val();
68 1420105 : if (!Data.empty())
69 1415793 : memcpy(Buf + P.second, Data.data(), Data.size());
70 : }
71 87274 : if (K != WinCOFF)
72 : return;
73 446 : support::endian::write32le(Buf, Size);
74 : }
75 :
76 : // Returns the character at Pos from end of a string.
77 : static int charTailAt(StringPair *P, size_t Pos) {
78 74737542 : StringRef S = P->first.val();
79 74737542 : if (Pos >= S.size())
80 : return -1;
81 148629876 : return (unsigned char)S[S.size() - Pos - 1];
82 : }
83 :
84 : // Three-way radix quicksort. This is much faster than std::sort with strcmp
85 : // because it does not compare characters that we already know the same.
86 33010109 : static void multikeySort(MutableArrayRef<StringPair *> Vec, int Pos) {
87 49324278 : tailcall:
88 49324278 : if (Vec.size() <= 1)
89 : return;
90 :
91 : // Partition items so that items in [0, I) are greater than the pivot,
92 : // [I, J) are the same as the pivot, and [J, Vec.size()) are less than
93 : // the pivot.
94 16498300 : int Pivot = charTailAt(Vec[0], Pos);
95 : size_t I = 0;
96 : size_t J = Vec.size();
97 74737542 : for (size_t K = 1; K < J;) {
98 58239242 : int C = charTailAt(Vec[K], Pos);
99 58239242 : if (C > Pivot)
100 4269542 : std::swap(Vec[I++], Vec[K++]);
101 53969700 : else if (C < Pivot)
102 4687462 : std::swap(Vec[--J], Vec[K]);
103 : else
104 49282238 : K++;
105 : }
106 :
107 16498300 : multikeySort(Vec.slice(0, I), Pos);
108 16498310 : multikeySort(Vec.slice(J), Pos);
109 :
110 : // multikeySort(Vec.slice(I, J - I), Pos + 1), but with
111 : // tail call optimization.
112 16498310 : if (Pivot != -1) {
113 16314169 : Vec = Vec.slice(I, J - I);
114 16314169 : ++Pos;
115 16314169 : goto tailcall;
116 : }
117 : }
118 :
119 13491 : void StringTableBuilder::finalize() {
120 : assert(K != DWARF);
121 13491 : finalizeStringTable(/*Optimize=*/true);
122 13492 : }
123 :
124 79096 : void StringTableBuilder::finalizeInOrder() {
125 79096 : finalizeStringTable(/*Optimize=*/false);
126 79096 : }
127 :
128 92588 : void StringTableBuilder::finalizeStringTable(bool Optimize) {
129 92588 : Finalized = true;
130 :
131 92588 : if (Optimize) {
132 : std::vector<StringPair *> Strings;
133 13492 : Strings.reserve(StringIndexMap.size());
134 1400653 : for (StringPair &P : StringIndexMap)
135 1373669 : Strings.push_back(&P);
136 :
137 13492 : multikeySort(Strings, 0);
138 13492 : initSize();
139 :
140 : StringRef Previous;
141 1387164 : for (StringPair *P : Strings) {
142 1373672 : StringRef S = P->first.val();
143 : if (Previous.endswith(S)) {
144 422566 : size_t Pos = Size - S.size() - (K != RAW);
145 422566 : if (!(Pos & (Alignment - 1))) {
146 422565 : P->second = Pos;
147 : continue;
148 : }
149 : }
150 :
151 951107 : Size = alignTo(Size, Alignment);
152 951107 : P->second = Size;
153 :
154 951107 : Size += S.size();
155 951107 : if (K != RAW)
156 951090 : ++Size;
157 : Previous = S;
158 : }
159 : }
160 :
161 92588 : if (K == MachO)
162 1224 : Size = alignTo(Size, 4); // Pad to multiple of 4.
163 92588 : }
164 :
165 493 : void StringTableBuilder::clear() {
166 493 : Finalized = false;
167 493 : StringIndexMap.clear();
168 493 : }
169 :
170 2240770 : size_t StringTableBuilder::getOffset(CachedHashStringRef S) const {
171 : assert(isFinalized());
172 2240770 : auto I = StringIndexMap.find(S);
173 : assert(I != StringIndexMap.end() && "String is not in table!");
174 2240771 : return I->second;
175 : }
176 :
177 2335687 : size_t StringTableBuilder::add(CachedHashStringRef S) {
178 : if (K == WinCOFF)
179 : assert(S.size() > COFF::NameSize && "Short string in COFF string table!");
180 :
181 : assert(!isFinalized());
182 2335687 : auto P = StringIndexMap.insert(std::make_pair(S, 0));
183 2335687 : if (P.second) {
184 1420291 : size_t Start = alignTo(Size, Alignment);
185 1420291 : P.first->second = Start;
186 1420291 : Size = Start + S.size() + (K != RAW);
187 : }
188 2335687 : return P.first->second;
189 : }
|
