Home | History | Annotate | Download | only in MC 
      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/STLExtras.h"
     12 #include "llvm/Support/COFF.h"
     13 #include "llvm/Support/Endian.h"
     14 
     15 #include <vector>
     16 
     17 using namespace llvm;
     18 
     19 StringTableBuilder::StringTableBuilder(Kind K, unsigned Alignment)
     20     : K(K), Alignment(Alignment) {
     21   // Account for leading bytes in table so that offsets returned from add are
     22   // correct.
     23   switch (K) {
     24   case RAW:
     25     Size = 0;
     26     break;
     27   case MachO:
     28   case ELF:
     29     Size = 1;
     30     break;
     31   case WinCOFF:
     32     Size = 4;
     33     break;
     34   }
     35 }
     36 
     37 typedef std::pair<CachedHash<StringRef>, size_t> StringPair;
     38 
     39 // Returns the character at Pos from end of a string.
     40 static int charTailAt(StringPair *P, size_t Pos) {
     41   StringRef S = P->first.Val;
     42   if (Pos >= S.size())
     43     return -1;
     44   return (unsigned char)S[S.size() - Pos - 1];
     45 }
     46 
     47 // Three-way radix quicksort. This is much faster than std::sort with strcmp
     48 // because it does not compare characters that we already know the same.
     49 static void multikey_qsort(StringPair **Begin, StringPair **End, int Pos) {
     50 tailcall:
     51   if (End - Begin <= 1)
     52     return;
     53 
     54   // Partition items. Items in [Begin, P) are greater than the pivot,
     55   // [P, Q) are the same as the pivot, and [Q, End) are less than the pivot.
     56   int Pivot = charTailAt(*Begin, Pos);
     57   StringPair **P = Begin;
     58   StringPair **Q = End;
     59   for (StringPair **R = Begin + 1; R < Q;) {
     60     int C = charTailAt(*R, Pos);
     61     if (C > Pivot)
     62       std::swap(*P++, *R++);
     63     else if (C < Pivot)
     64       std::swap(*--Q, *R);
     65     else
     66       R++;
     67   }
     68 
     69   multikey_qsort(Begin, P, Pos);
     70   multikey_qsort(Q, End, Pos);
     71   if (Pivot != -1) {
     72     // qsort(P, Q, Pos + 1), but with tail call optimization.
     73     Begin = P;
     74     End = Q;
     75     ++Pos;
     76     goto tailcall;
     77   }
     78 }
     79 
     80 void StringTableBuilder::finalize() {
     81   finalizeStringTable(/*Optimize=*/true);
     82 }
     83 
     84 void StringTableBuilder::finalizeInOrder() {
     85   finalizeStringTable(/*Optimize=*/false);
     86 }
     87 
     88 void StringTableBuilder::finalizeStringTable(bool Optimize) {
     89   typedef std::pair<CachedHash<StringRef>, size_t> StringOffsetPair;
     90   std::vector<StringOffsetPair *> Strings;
     91   Strings.reserve(StringIndexMap.size());
     92   for (StringOffsetPair &P : StringIndexMap)
     93     Strings.push_back(&P);
     94 
     95   if (!Strings.empty()) {
     96     // If we're optimizing, sort by name. If not, sort by previously assigned
     97     // offset.
     98     if (Optimize) {
     99       multikey_qsort(&Strings[0], &Strings[0] + Strings.size(), 0);
    100     } else {
    101       std::sort(Strings.begin(), Strings.end(),
    102                 [](const StringOffsetPair *LHS, const StringOffsetPair *RHS) {
    103                   return LHS->second < RHS->second;
    104                 });
    105     }
    106   }
    107 
    108   switch (K) {
    109   case RAW:
    110     break;
    111   case ELF:
    112   case MachO:
    113     // Start the table with a NUL byte.
    114     StringTable += '\x00';
    115     break;
    116   case WinCOFF:
    117     // Make room to write the table size later.
    118     StringTable.append(4, '\x00');
    119     break;
    120   }
    121 
    122   StringRef Previous;
    123   for (StringOffsetPair *P : Strings) {
    124     StringRef S = P->first.Val;
    125     if (K == WinCOFF)
    126       assert(S.size() > COFF::NameSize && "Short string in COFF string table!");
    127 
    128     if (Optimize && Previous.endswith(S)) {
    129       size_t Pos = StringTable.size() - S.size() - (K != RAW);
    130       if (!(Pos & (Alignment - 1))) {
    131         P->second = Pos;
    132         continue;
    133       }
    134     }
    135 
    136     if (Optimize) {
    137       size_t Start = alignTo(StringTable.size(), Alignment);
    138       P->second = Start;
    139       StringTable.append(Start - StringTable.size(), '\0');
    140     } else {
    141       assert(P->second == StringTable.size() &&
    142              "different strtab offset after finalization");
    143     }
    144 
    145     StringTable += S;
    146     if (K != RAW)
    147       StringTable += '\x00';
    148     Previous = S;
    149   }
    150 
    151   switch (K) {
    152   case RAW:
    153   case ELF:
    154     break;
    155   case MachO:
    156     // Pad to multiple of 4.
    157     while (StringTable.size() % 4)
    158       StringTable += '\x00';
    159     break;
    160   case WinCOFF:
    161     // Write the table size in the first word.
    162     assert(StringTable.size() <= std::numeric_limits<uint32_t>::max());
    163     uint32_t Size = static_cast<uint32_t>(StringTable.size());
    164     support::endian::write<uint32_t, support::little, support::unaligned>(
    165         StringTable.data(), Size);
    166     break;
    167   }
    168 
    169   Size = StringTable.size();
    170 }
    171 
    172 void StringTableBuilder::clear() {
    173   StringTable.clear();
    174   StringIndexMap.clear();
    175 }
    176 
    177 size_t StringTableBuilder::getOffset(StringRef S) const {
    178   assert(isFinalized());
    179   auto I = StringIndexMap.find(S);
    180   assert(I != StringIndexMap.end() && "String is not in table!");
    181   return I->second;
    182 }
    183 
    184 size_t StringTableBuilder::add(StringRef S) {
    185   assert(!isFinalized());
    186   size_t Start = alignTo(Size, Alignment);
    187   auto P = StringIndexMap.insert(std::make_pair(S, Start));
    188   if (P.second)
    189     Size = Start + S.size() + (K != RAW);
    190   return P.first->second;
    191 }
    192