Inline initOffsetMap

[• espindola]

Summary

In the lld perf builder 328686 had a negative impact in stalled-cycles-frontend. Somehow that stat is not showing on my machine, but the attached patch shows an improvement on cache-misses, which is probably a reasonable proxy.

My working theory is that given a large input the pieces vector is out of cache by the time initOffsetMap runs.

Both finalizeContents implementation have a convenient location for initializing the OffsetMap, so this seems the best solution.

[ruiu]

ELF/SyntheticSections.cpp

2445

Shouldn't this line be in the following if?

[• espindola]

ELF/SyntheticSections.cpp

2445

No, we want the map to include dead pieces so that we can find that they are dead without a binary search.

That was the case before this patch too.

[ruiu]

LGTM

[• espindola]

329117

ELF/InputSection.h

public:
 
   // Translate an offset in the input section to an offset
   // in the output section.
   uint64_t getOffset(uint64_t Offset) const;
 
   // Splittable sections are handled as a sequence of data
   // rather than a single large blob of data.
   std::vector<SectionPiece> Pieces;
+  llvm::DenseMap<uint32_t, uint32_t> OffsetMap;
 
   // Returns I'th piece's data. This function is very hot when
   // string merging is enabled, so we want to inline.
   LLVM_ATTRIBUTE_ALWAYS_INLINE
   llvm::CachedHashStringRef getData(size_t I) const {
     size_t Begin = Pieces[I].InputOff;
     size_t End =
         (Pieces.size() - 1 == I) ? Data.size() : Pieces[I + 1].InputOff;
     return {toStringRef(Data.slice(Begin, End - Begin)), Pieces[I].Hash};
   }
 
   // Returns the SectionPiece at a given input section offset.
   SectionPiece *getSectionPiece(uint64_t Offset);
   const SectionPiece *getSectionPiece(uint64_t Offset) const {
     return const_cast<MergeInputSection *>(this)->getSectionPiece(Offset);
   }
 
   SyntheticSection *getParent() const;
-  void initOffsetMap();
 
 private:
   void splitStrings(ArrayRef<uint8_t> A, size_t Size);
   void splitNonStrings(ArrayRef<uint8_t> A, size_t Size);
 
-  llvm::DenseMap<uint32_t, uint32_t> OffsetMap;
-
   llvm::DenseSet<uint32_t> LiveOffsets;
 };
 
 struct EhSectionPiece {
   EhSectionPiece(size_t Off, InputSectionBase *Sec, uint32_t Size,
                  unsigned FirstRelocation)
       : InputOff(Off), Sec(Sec), Size(Size), FirstRelocation(FirstRelocation) {}
 

ELF/InputSection.cpp

const SectionPiece &Piece =
       *findSectionPiece(const_cast<MergeInputSection *>(this), Offset);
   if (!Piece.Live)
     return 0;
 
   uint64_t Addend = Offset - Piece.InputOff;
   return Piece.OutputOff + Addend;
 }
 
-void MergeInputSection::initOffsetMap() {
-  OffsetMap.reserve(Pieces.size());
-  for (size_t I = 0; I < Pieces.size(); ++I)
-    OffsetMap[Pieces[I].InputOff] = I;
-}
-
 template InputSection::InputSection(ObjFile<ELF32LE> &, const ELF32LE::Shdr &,
                                     StringRef);
 template InputSection::InputSection(ObjFile<ELF32BE> &, const ELF32BE::Shdr &,
                                     StringRef);
 template InputSection::InputSection(ObjFile<ELF64LE> &, const ELF64LE::Shdr &,
                                     StringRef);
 template InputSection::InputSection(ObjFile<ELF64BE> &, const ELF64BE::Shdr &,
                                     StringRef);

ELF/SyntheticSections.cpp

for (size_t I = 0, E = Sec->Pieces.size(); I != E; ++I)
         Builder.add(Sec->getData(I));
 
   // Fix the string table content. After this, the contents will never change.
   Builder.finalize();
 
   // finalize() fixed tail-optimized strings, so we can now get
   // offsets of strings. Get an offset for each string and save it
   // to a corresponding StringPiece for easy access.
-  for (MergeInputSection *Sec : Sections)
-    for (size_t I = 0, E = Sec->Pieces.size(); I != E; ++I)
-      if (Sec->Pieces[I].Live)
-        Sec->Pieces[I].OutputOff = Builder.getOffset(Sec->getData(I));
+  for (MergeInputSection *Sec : Sections) {
+    Sec->OffsetMap.reserve(Sec->Pieces.size());
+    for (size_t I = 0, E = Sec->Pieces.size(); I != E; ++I) {
+      SectionPiece &P = Sec->Pieces[I];
+      Sec->OffsetMap[P.InputOff] = I;
+      if (P.Live)
+        P.OutputOff = Builder.getOffset(Sec->getData(I));
+    }
+  }
 }
 
 void MergeNoTailSection::writeTo(uint8_t *Buf) {
   for (size_t I = 0; I < NumShards; ++I)
     Shards[I].write(Buf + ShardOffsets[I]);
 }
 
 // This function is very hot (i.e. it can take several seconds to finish)
for (size_t I = 0; I < NumShards; ++I) {
     ShardOffsets[I] = Off;
     Off += Shards[I].getSize();
   }
   Size = Off;
 
   // So far, section pieces have offsets from beginning of shards, but
   // we want offsets from beginning of the whole section. Fix them.
   parallelForEach(Sections, [&](MergeInputSection *Sec) {
-    for (size_t I = 0, E = Sec->Pieces.size(); I != E; ++I)
-      if (Sec->Pieces[I].Live)
-        Sec->Pieces[I].OutputOff +=
-            ShardOffsets[getShardId(Sec->Pieces[I].Hash)];
+    Sec->OffsetMap.reserve(Sec->Pieces.size());
+    for (size_t I = 0, E = Sec->Pieces.size(); I != E; ++I) {
+      SectionPiece &P = Sec->Pieces[I];
+      Sec->OffsetMap[P.InputOff] = I;
+      if (P.Live)
+        P.OutputOff += ShardOffsets[getShardId(P.Hash)];
+    }
   });
 }
 
 static MergeSyntheticSection *createMergeSynthetic(StringRef Name,
                                                    uint32_t Type,
                                                    uint64_t Flags,
                                                    uint32_t Alignment) {
   bool ShouldTailMerge = (Flags & SHF_STRINGS) && Config->Optimize >= 2;
if (I == MergeSections.end()) {
       I = std::prev(MergeSections.end());
       S = Syn;
       Syn->Entsize = MS->Entsize;
     } else {
       S = nullptr;
     }
     (*I)->addSection(MS);
   }
-  for (auto *MS : MergeSections) {
+  for (auto *MS : MergeSections)
     MS->finalizeContents();
-    parallelForEach(MS->Sections,
-                    [](MergeInputSection *Sec) { Sec->initOffsetMap(); });
-  }
 
   std::vector<InputSectionBase *> &V = InputSections;
   V.erase(std::remove(V.begin(), V.end(), nullptr), V.end());
 }
 
 MipsRldMapSection::MipsRldMapSection()
     : SyntheticSection(SHF_ALLOC | SHF_WRITE, SHT_PROGBITS, Config->Wordsize,
                        ".rld_map") {}