LCOV - code coverage report
Current view: top level - lib/MC - StringTableBuilder.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 88 88 100.0 %
Date: 2018-06-17 00:07:59 Functions: 11 11 100.0 %
Legend: Lines: hit not hit

          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       94271 : void StringTableBuilder::initSize() {
      30             :   // Account for leading bytes in table so that offsets returned from add are
      31             :   // correct.
      32       94271 :   switch (K) {
      33       72809 :   case RAW:
      34             :   case DWARF:
      35       72809 :     Size = 0;
      36       72809 :     break;
      37       20147 :   case MachO:
      38             :   case ELF:
      39             :     // Start the table with a NUL byte.
      40       20147 :     Size = 1;
      41       20147 :     break;
      42        1315 :   case WinCOFF:
      43             :     // Make room to write the table size later.
      44        1315 :     Size = 4;
      45        1315 :     break;
      46             :   }
      47       94271 : }
      48             : 
      49       85147 : StringTableBuilder::StringTableBuilder(Kind K, unsigned Alignment)
      50      170294 :     : K(K), Alignment(Alignment) {
      51       85147 :   initSize();
      52       85147 : }
      53             : 
      54        8618 : void StringTableBuilder::write(raw_ostream &OS) const {
      55             :   assert(isFinalized());
      56             :   SmallString<0> Data;
      57        8618 :   Data.resize(getSize());
      58        8618 :   write((uint8_t *)Data.data());
      59             :   OS << Data;
      60        8618 : }
      61             : 
      62             : using StringPair = std::pair<CachedHashStringRef, size_t>;
      63             : 
      64       77185 : void StringTableBuilder::write(uint8_t *Buf) const {
      65             :   assert(isFinalized());
      66      861710 :   for (const StringPair &P : StringIndexMap) {
      67      707340 :     StringRef Data = P.first.val();
      68      707340 :     if (!Data.empty())
      69      703324 :       memcpy(Buf + P.second, Data.data(), Data.size());
      70             :   }
      71       77185 :   if (K != WinCOFF)
      72             :     return;
      73         375 :   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    29067224 :   StringRef S = P->first.val();
      79    29067224 :   if (Pos >= S.size())
      80             :     return -1;
      81    57890654 :   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    11368052 : static void multikeySort(MutableArrayRef<StringPair *> Vec, int Pos) {
      87    16992647 : tailcall:
      88    16992647 :   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     5679464 :   int Pivot = charTailAt(Vec[0], Pos);
      95             :   size_t I = 0;
      96             :   size_t J = Vec.size();
      97    29067224 :   for (size_t K = 1; K < J;) {
      98    23387760 :     int C = charTailAt(Vec[K], Pos);
      99    23387760 :     if (C > Pivot)
     100     2186298 :       std::swap(Vec[I++], Vec[K++]);
     101    21201462 :     else if (C < Pivot)
     102     2670608 :       std::swap(Vec[--J], Vec[K]);
     103             :     else
     104    18530854 :       K++;
     105             :   }
     106             : 
     107     5679464 :   multikeySort(Vec.slice(0, I), Pos);
     108     5679464 :   multikeySort(Vec.slice(J), Pos);
     109             : 
     110             :   // multikeySort(Vec.slice(I, J - I), Pos + 1), but with
     111             :   // tail call optimization.
     112     5679464 :   if (Pivot != -1) {
     113     5624595 :     Vec = Vec.slice(I, J - I);
     114     5624595 :     ++Pos;
     115     5624595 :     goto tailcall;
     116             :   }
     117             : }
     118             : 
     119        9124 : void StringTableBuilder::finalize() {
     120             :   assert(K != DWARF);
     121        9124 :   finalizeStringTable(/*Optimize=*/true);
     122        9124 : }
     123             : 
     124       72753 : void StringTableBuilder::finalizeInOrder() {
     125       72753 :   finalizeStringTable(/*Optimize=*/false);
     126       72753 : }
     127             : 
     128       81877 : void StringTableBuilder::finalizeStringTable(bool Optimize) {
     129       81877 :   Finalized = true;
     130             : 
     131       81877 :   if (Optimize) {
     132             :     std::vector<StringPair *> Strings;
     133        9124 :     Strings.reserve(StringIndexMap.size());
     134      681771 :     for (StringPair &P : StringIndexMap)
     135     1327046 :       Strings.push_back(&P);
     136             : 
     137        9124 :     multikeySort(Strings, 0);
     138        9124 :     initSize();
     139             : 
     140             :     StringRef Previous;
     141      672647 :     for (StringPair *P : Strings) {
     142      663523 :       StringRef S = P->first.val();
     143             :       if (Previous.endswith(S)) {
     144      121783 :         size_t Pos = Size - S.size() - (K != RAW);
     145      243565 :         if (!(Pos & (Alignment - 1))) {
     146      121782 :           P->second = Pos;
     147             :           continue;
     148             :         }
     149             :       }
     150             : 
     151      541741 :       Size = alignTo(Size, Alignment);
     152      541741 :       P->second = Size;
     153             : 
     154      541741 :       Size += S.size();
     155      541741 :       if (K != RAW)
     156      541725 :         ++Size;
     157             :       Previous = S;
     158             :     }
     159             :   }
     160             : 
     161       81877 :   if (K == MachO)
     162        1196 :     Size = alignTo(Size, 4); // Pad to multiple of 4.
     163       81877 : }
     164             : 
     165         472 : void StringTableBuilder::clear() {
     166         472 :   Finalized = false;
     167         472 :   StringIndexMap.clear();
     168         472 : }
     169             : 
     170      704189 : size_t StringTableBuilder::getOffset(CachedHashStringRef S) const {
     171             :   assert(isFinalized());
     172      704189 :   auto I = StringIndexMap.find(S);
     173             :   assert(I != StringIndexMap.end() && "String is not in table!");
     174      704189 :   return I->second;
     175             : }
     176             : 
     177      790168 : 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     1580336 :   auto P = StringIndexMap.insert(std::make_pair(S, 0));
     183      790168 :   if (P.second) {
     184      707507 :     size_t Start = alignTo(Size, Alignment);
     185      707507 :     P.first->second = Start;
     186      707507 :     Size = Start + S.size() + (K != RAW);
     187             :   }
     188      790168 :   return P.first->second;
     189             : }

Generated by: LCOV version 1.13