From 5fc2b1d2feb023ceb4d60dc5bff63e88cf0c246c Mon Sep 17 00:00:00 2001
From: Rafael Espindola <rafael.espindola@gmail.com>
Date: Wed, 5 Oct 2016 19:36:02 +0000
Subject: [PATCH] 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
---
 lld/ELF/InputSection.cpp   | 3 ++-
 lld/ELF/InputSection.h     | 9 +++++++--
 lld/ELF/OutputSections.cpp | 6 ++++--
 lld/ELF/OutputSections.h   | 2 +-
 4 files changed, 14 insertions(+), 6 deletions(-)

diff --git a/lld/ELF/InputSection.cpp b/lld/ELF/InputSection.cpp
index 1e9e96e..d709626 100644
--- 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
index b5ff603..b3c7f68 100644
--- 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 @@ private:
 
 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
index 683c15c..c2d736d 100644
--- 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
index 5dd6c46..a405934 100644
--- a/lld/ELF/OutputSections.h
+++ b/lld/ELF/OutputSections.h
@@ -427,7 +427,7 @@ public:
                      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;
-- 
2.7.4