Store the hash in SectionPiece.

This spreads out computing the hash and using it in a hash table. The speedups are: firefox master 6.811232891 patch 6.559280249 1.03841162939x faster chromium master 4.369323666 patch 4.33171853 1.00868134338x faster chromium fast master 1.856679971 patch 1.850617741 1.00327578725x faster the gold plugin master 0.32917962 patch 0.325711944 1.01064645023x faster clang master 0.558015452 patch 0.550284165 1.01404962652x faster llvm-as master 0.032563515 patch 0.032152077 1.01279662275x faster the gold plugin fsds master 0.356221362 patch 0.352772162 1.00977741549x faster clang fsds master 0.635096494 patch 0.627249229 1.01251060127x faster llvm-as fsds master 0.030183188 patch 0.029889544 1.00982430511x faster scylla master 3.071448906 patch 2.938484138 1.04524944215x faster This seems to be because we don't stall as much. When linking firefox stalled-cycles-frontend goes from 57.56% to 55.55%. With -O2 the difference is even more significant since we avoid recomputing the hash. For firefox we go from 9.990295265 to 9.149627521 seconds (1.09x faster). llvm-svn: 283367
llvm · Oct 5, 2016 · 5fc2b1d · 5fc2b1d
1 parent d799d28
commit 5fc2b1d
Showing 4 changed files with 14 additions and 6 deletions.
diff --git a/lld/ELF/InputSection.cpp b/lld/ELF/InputSection.cpp
@@ -644,7 +644,8 @@ template <class ELFT> void  MergeInputSection<ELFT>::finalizePieces() {
       auto *OutSec = static_cast<MergeOutputSection<ELFT> *>(this->OutSec);
       ArrayRef<uint8_t> D = this->getData(Piece);
       StringRef S((const char *)D.data(), D.size());
-      Piece.OutputOff = OutSec->getOffset(S);
+      CachedHashString V(S, Piece.Hash);
+      Piece.OutputOff = OutSec->getOffset(V);
     }
     OffsetMap[Piece.InputOff] = Piece.OutputOff;
   }

diff --git a/lld/ELF/InputSection.h b/lld/ELF/InputSection.h
@@ -124,14 +124,19 @@ template <class ELFT> InputSectionBase<ELFT> InputSectionBase<ELFT>::Discarded;
 
 // SectionPiece represents a piece of splittable section contents.
 struct SectionPiece {
+  SectionPiece(size_t Off, ArrayRef<uint8_t> Data, uint32_t Hash, bool Live)
+      : InputOff(Off), Hash(Hash), Size(Data.size()),
+        Live(Live || !Config->GcSections) {}
   SectionPiece(size_t Off, ArrayRef<uint8_t> Data, bool Live = false)
-      : InputOff(Off), Size(Data.size()), Live(Live || !Config->GcSections) {}
+      : SectionPiece(Off, Data, hash_value(Data), Live) {}
 
   size_t size() const { return Size; }
 
   size_t InputOff;
   size_t OutputOff = -1;
 
+  uint32_t Hash;
+
 private:
   // We use bitfields because SplitInputSection is accessed by
   // std::upper_bound very often.
@@ -181,7 +186,7 @@ template <class ELFT> class MergeInputSection : public InputSectionBase<ELFT> {
 
 struct EhSectionPiece : public SectionPiece {
   EhSectionPiece(size_t Off, ArrayRef<uint8_t> Data, unsigned FirstRelocation)
-      : SectionPiece(Off, Data), Data(Data.data()),
+      : SectionPiece(Off, Data, 0, false), Data(Data.data()),
         FirstRelocation(FirstRelocation) {}
   const uint8_t *Data;
   ArrayRef<uint8_t> data() { return {Data, size()}; }

diff --git a/lld/ELF/OutputSections.cpp b/lld/ELF/OutputSections.cpp
@@ -1244,14 +1244,16 @@ void MergeOutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
   for (SectionPiece &Piece : Sec->Pieces) {
     if (!Piece.Live)
       continue;
-    uintX_t OutputOffset = Builder.add(toStringRef(Sec->getData(Piece)));
+    StringRef Data = toStringRef(Sec->getData(Piece));
+    CachedHashString V(Data, Piece.Hash);
+    uintX_t OutputOffset = Builder.add(V);
     if (!shouldTailMerge())
       Piece.OutputOff = OutputOffset;
   }
 }
 
 template <class ELFT>
-unsigned MergeOutputSection<ELFT>::getOffset(StringRef Val) {
+unsigned MergeOutputSection<ELFT>::getOffset(CachedHashString Val) {
   return Builder.getOffset(Val);
 }
 

diff --git a/lld/ELF/OutputSections.h b/lld/ELF/OutputSections.h
@@ -427,7 +427,7 @@ class MergeOutputSection final : public OutputSectionBase<ELFT> {
                      uintX_t Alignment);
   void addSection(InputSectionBase<ELFT> *S) override;
   void writeTo(uint8_t *Buf) override;
-  unsigned getOffset(StringRef Val);
+  unsigned getOffset(llvm::CachedHashString Val);
   void finalize() override;
   void finalizePieces() override;
   bool shouldTailMerge() const;