LCOV - code coverage report
Current view: top level - lib/MC - StringTableBuilder.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 97 97 100.0 %
Date: 2017-09-14 15:23:50 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       13989 : void StringTableBuilder::initSize() {
      30             :   // Account for leading bytes in table so that offsets returned from add are
      31             :   // correct.
      32       13989 :   switch (K) {
      33        5367 :   case RAW:
      34        5367 :     Size = 0;
      35        5367 :     break;
      36        8061 :   case MachO:
      37             :   case ELF:
      38             :     // Start the table with a NUL byte.
      39        8061 :     Size = 1;
      40        8061 :     break;
      41         561 :   case WinCOFF:
      42             :     // Make room to write the table size later.
      43         561 :     Size = 4;
      44         561 :     break;
      45             :   }
      46       13989 : }
      47             : 
      48        9724 : StringTableBuilder::StringTableBuilder(Kind K, unsigned Alignment)
      49       19448 :     : K(K), Alignment(Alignment) {
      50        9724 :   initSize();
      51        9724 : }
      52             : 
      53        4140 : void StringTableBuilder::write(raw_ostream &OS) const {
      54             :   assert(isFinalized());
      55        8280 :   SmallString<0> Data;
      56        4140 :   Data.resize(getSize());
      57        8280 :   write((uint8_t *)Data.data());
      58        4140 :   OS << Data;
      59        4140 : }
      60             : 
      61             : using StringPair = std::pair<CachedHashStringRef, size_t>;
      62             : 
      63        9408 : void StringTableBuilder::write(uint8_t *Buf) const {
      64             :   assert(isFinalized());
      65       18816 :   for (const StringPair &P : StringIndexMap) {
      66     1006604 :     StringRef Data = P.first.val();
      67      503302 :     if (!Data.empty())
      68      499997 :       memcpy(Buf + P.second, Data.data(), Data.size());
      69             :   }
      70        9408 :   if (K != WinCOFF)
      71             :     return;
      72         277 :   support::endian::write32le(Buf, Size);
      73             : }
      74             : 
      75             : // Returns the character at Pos from end of a string.
      76             : static int charTailAt(StringPair *P, size_t Pos) {
      77    42914404 :   StringRef S = P->first.val();
      78    21457202 :   if (Pos >= S.size())
      79             :     return -1;
      80    42820780 :   return (unsigned char)S[S.size() - Pos - 1];
      81             : }
      82             : 
      83             : // Three-way radix quicksort. This is much faster than std::sort with strcmp
      84             : // because it does not compare characters that we already know the same.
      85     6886791 : static void multikey_qsort(StringPair **Begin, StringPair **End, int Pos) {
      86    10306651 : tailcall:
      87    10306651 :   if (End - Begin <= 1)
      88             :     return;
      89             : 
      90             :   // Partition items. Items in [Begin, P) are greater than the pivot,
      91             :   // [P, Q) are the same as the pivot, and [Q, End) are less than the pivot.
      92     6882806 :   int Pivot = charTailAt(*Begin, Pos);
      93     3441403 :   StringPair **P = Begin;
      94     3441403 :   StringPair **Q = End;
      95     3441403 :   for (StringPair **R = Begin + 1; R < Q;) {
      96    36031598 :     int C = charTailAt(*R, Pos);
      97    18015799 :     if (C > Pivot)
      98     1756614 :       std::swap(*P++, *R++);
      99    16259185 :     else if (C < Pivot)
     100     2230661 :       std::swap(*--Q, *R);
     101             :     else
     102    14028524 :       R++;
     103             :   }
     104             : 
     105     3441403 :   multikey_qsort(Begin, P, Pos);
     106     3441402 :   multikey_qsort(Q, End, Pos);
     107     3441399 :   if (Pivot != -1) {
     108             :     // qsort(P, Q, Pos + 1), but with tail call optimization.
     109     3419860 :     Begin = P;
     110     3419860 :     End = Q;
     111     3419860 :     ++Pos;
     112     3419860 :     goto tailcall;
     113             :   }
     114             : }
     115             : 
     116        4264 : void StringTableBuilder::finalize() {
     117        4264 :   finalizeStringTable(/*Optimize=*/true);
     118        4265 : }
     119             : 
     120        5330 : void StringTableBuilder::finalizeInOrder() {
     121        5330 :   finalizeStringTable(/*Optimize=*/false);
     122        5330 : }
     123             : 
     124        9595 : void StringTableBuilder::finalizeStringTable(bool Optimize) {
     125        9595 :   Finalized = true;
     126             : 
     127        9595 :   if (Optimize) {
     128        8530 :     std::vector<StringPair *> Strings;
     129        8530 :     Strings.reserve(StringIndexMap.size());
     130      485392 :     for (StringPair &P : StringIndexMap)
     131      945198 :       Strings.push_back(&P);
     132             : 
     133        4265 :     if (!Strings.empty()) {
     134             :       // If we're optimizing, sort by name. If not, sort by previously assigned
     135             :       // offset.
     136        3989 :       multikey_qsort(&Strings[0], &Strings[0] + Strings.size(), 0);
     137             :     }
     138             : 
     139        4265 :     initSize();
     140             : 
     141        4265 :     StringRef Previous;
     142      489657 :     for (StringPair *P : Strings) {
     143      945194 :       StringRef S = P->first.val();
     144             :       if (Previous.endswith(S)) {
     145       46675 :         size_t Pos = Size - S.size() - (K != RAW);
     146       93349 :         if (!(Pos & (Alignment - 1))) {
     147       46674 :           P->second = Pos;
     148       46674 :           continue;
     149             :         }
     150             :       }
     151             : 
     152      851846 :       Size = alignTo(Size, Alignment);
     153      425923 :       P->second = Size;
     154             : 
     155      425923 :       Size += S.size();
     156      425923 :       if (K != RAW)
     157      425915 :         ++Size;
     158             :       Previous = S;
     159             :     }
     160             :   }
     161             : 
     162        9595 :   if (K == MachO)
     163         996 :     Size = alignTo(Size, 4); // Pad to multiple of 4.
     164        9595 : }
     165             : 
     166        1582 : void StringTableBuilder::clear() {
     167        1582 :   Finalized = false;
     168        1582 :   StringIndexMap.clear();
     169        1581 : }
     170             : 
     171      482022 : size_t StringTableBuilder::getOffset(CachedHashStringRef S) const {
     172             :   assert(isFinalized());
     173      482022 :   auto I = StringIndexMap.find(S);
     174             :   assert(I != StringIndexMap.end() && "String is not in table!");
     175      482022 :   return I->second;
     176             : }
     177             : 
     178      530539 : size_t StringTableBuilder::add(CachedHashStringRef S) {
     179             :   if (K == WinCOFF)
     180             :     assert(S.size() > COFF::NameSize && "Short string in COFF string table!");
     181             : 
     182             :   assert(!isFinalized());
     183     2122156 :   auto P = StringIndexMap.insert(std::make_pair(S, 0));
     184      530539 :   if (P.second) {
     185     1006822 :     size_t Start = alignTo(Size, Alignment);
     186      503411 :     P.first->second = Start;
     187      503411 :     Size = Start + S.size() + (K != RAW);
     188             :   }
     189      530539 :   return P.first->second;
     190             : }

Generated by: LCOV version 1.13