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-10-20 13:21:21 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      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             : }

Generated by: LCOV version 1.13