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-09-23 13:06:45 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      110762 : void StringTableBuilder::initSize() {
      30             :   // Account for leading bytes in table so that offsets returned from add are
      31             :   // correct.
      32      110762 :   switch (K) {
      33       77353 :   case RAW:
      34             :   case DWARF:
      35       77353 :     Size = 0;
      36       77353 :     break;
      37       31983 :   case MachO:
      38             :   case ELF:
      39             :     // Start the table with a NUL byte.
      40       31983 :     Size = 1;
      41       31983 :     break;
      42        1426 :   case WinCOFF:
      43             :     // Make room to write the table size later.
      44        1426 :     Size = 4;
      45        1426 :     break;
      46             :   }
      47      110762 : }
      48             : 
      49       95574 : StringTableBuilder::StringTableBuilder(Kind K, unsigned Alignment)
      50       95574 :     : K(K), Alignment(Alignment) {
      51       95574 :   initSize();
      52       95573 : }
      53             : 
      54       14367 : void StringTableBuilder::write(raw_ostream &OS) const {
      55             :   assert(isFinalized());
      56             :   SmallString<0> Data;
      57       14367 :   Data.resize(getSize());
      58       14367 :   write((uint8_t *)Data.data());
      59             :   OS << Data;
      60       14367 : }
      61             : 
      62             : using StringPair = std::pair<CachedHashStringRef, size_t>;
      63             : 
      64       87304 : void StringTableBuilder::write(uint8_t *Buf) const {
      65             :   assert(isFinalized());
      66     1768288 :   for (const StringPair &P : StringIndexMap) {
      67     1593680 :     StringRef Data = P.first.val();
      68     1593680 :     if (!Data.empty())
      69     1589403 :       memcpy(Buf + P.second, Data.data(), Data.size());
      70             :   }
      71       87304 :   if (K != WinCOFF)
      72             :     return;
      73         420 :   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    80955700 :   StringRef S = P->first.val();
      79    80955700 :   if (Pos >= S.size())
      80             :     return -1;
      81   160970520 :   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    36122219 : static void multikeySort(MutableArrayRef<StringPair *> Vec, int Pos) {
      87    53970690 : tailcall:
      88    53970690 :   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    18053514 :   int Pivot = charTailAt(Vec[0], Pos);
      95             :   size_t I = 0;
      96             :   size_t J = Vec.size();
      97    80955700 :   for (size_t K = 1; K < J;) {
      98    62902186 :     int C = charTailAt(Vec[K], Pos);
      99    62902186 :     if (C > Pivot)
     100     4834571 :       std::swap(Vec[I++], Vec[K++]);
     101    58067615 :     else if (C < Pivot)
     102     5268103 :       std::swap(Vec[--J], Vec[K]);
     103             :     else
     104    52799512 :       K++;
     105             :   }
     106             : 
     107    18053514 :   multikeySort(Vec.slice(0, I), Pos);
     108    18053515 :   multikeySort(Vec.slice(J), Pos);
     109             : 
     110             :   // multikeySort(Vec.slice(I, J - I), Pos + 1), but with
     111             :   // tail call optimization.
     112    18053515 :   if (Pivot != -1) {
     113    17848471 :     Vec = Vec.slice(I, J - I);
     114    17848471 :     ++Pos;
     115    17848471 :     goto tailcall;
     116             :   }
     117             : }
     118             : 
     119       15189 : void StringTableBuilder::finalize() {
     120             :   assert(K != DWARF);
     121       15189 :   finalizeStringTable(/*Optimize=*/true);
     122       15189 : }
     123             : 
     124       77297 : void StringTableBuilder::finalizeInOrder() {
     125       77297 :   finalizeStringTable(/*Optimize=*/false);
     126       77297 : }
     127             : 
     128       92486 : void StringTableBuilder::finalizeStringTable(bool Optimize) {
     129       92486 :   Finalized = true;
     130             : 
     131       92486 :   if (Optimize) {
     132             :     std::vector<StringPair *> Strings;
     133       15189 :     Strings.reserve(StringIndexMap.size());
     134     1578073 :     for (StringPair &P : StringIndexMap)
     135     1547695 :       Strings.push_back(&P);
     136             : 
     137       15189 :     multikeySort(Strings, 0);
     138       15189 :     initSize();
     139             : 
     140             :     StringRef Previous;
     141     1562885 :     for (StringPair *P : Strings) {
     142     1547696 :       StringRef S = P->first.val();
     143             :       if (Previous.endswith(S)) {
     144      470348 :         size_t Pos = Size - S.size() - (K != RAW);
     145      470348 :         if (!(Pos & (Alignment - 1))) {
     146      470347 :           P->second = Pos;
     147             :           continue;
     148             :         }
     149             :       }
     150             : 
     151     1077349 :       Size = alignTo(Size, Alignment);
     152     1077349 :       P->second = Size;
     153             : 
     154     1077349 :       Size += S.size();
     155     1077349 :       if (K != RAW)
     156     1077333 :         ++Size;
     157             :       Previous = S;
     158             :     }
     159             :   }
     160             : 
     161       92486 :   if (K == MachO)
     162        1238 :     Size = alignTo(Size, 4); // Pad to multiple of 4.
     163       92486 : }
     164             : 
     165         489 : void StringTableBuilder::clear() {
     166         489 :   Finalized = false;
     167         489 :   StringIndexMap.clear();
     168         489 : }
     169             : 
     170     2437698 : size_t StringTableBuilder::getOffset(CachedHashStringRef S) const {
     171             :   assert(isFinalized());
     172     2437698 :   auto I = StringIndexMap.find(S);
     173             :   assert(I != StringIndexMap.end() && "String is not in table!");
     174     2437698 :   return I->second;
     175             : }
     176             : 
     177     2531928 : 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     2531928 :   auto P = StringIndexMap.insert(std::make_pair(S, 0));
     183     2531926 :   if (P.second) {
     184     1593859 :     size_t Start = alignTo(Size, Alignment);
     185     1593859 :     P.first->second = Start;
     186     1593859 :     Size = Start + S.size() + (K != RAW);
     187             :   }
     188     2531926 :   return P.first->second;
     189             : }

Generated by: LCOV version 1.13