[DWARF] - Speedup handling of relocations in DWARFContextInMemory.

[grimar]

Summary

I am working on a LLD bug "Bug 32228 - -gdb-index is too slow".

One of place I want to start from is a proccessing of relocations. It is usually
a hot place. I noticed that relocations that are proccessed in DWARFContextInMemory often uses
the same symbol in a row.

I took debug LLC binary objects configured with -ggnu-pubnames and linked it using LLD.

1. Link time without --gdb-index is about 4,45s.
2. Link time with --gdb-index: a) Without patch: 19,16s b) With patch: 15,52s

That means time spent on --gdb-index in this configuration is
19,16s - 4,45s = 14,71s vs 15,52s - 4,45s = 11,07s.

Total time change spent on building index then is 11,07s/14,71 = 0,7525

[dblaikie]

Could you dump the relevant relocations in some object files you're testing?

I'd be curious to understand/see why so many relocations to the same symbol appear in a row - and wonder if it'd be good to consider caching all the results, not only the previous/most recent one.

[aprantl]

DebugInfo/DWARF/DWARFContext.cpp

627 ↗

(On Diff #92339)

Please add comments describing the purpose of the new static helper functions.

641 ↗

(On Diff #92339)

We typically spell this as ~1ULL. But, is there a better way of passing the error? Should we use optional<uint64_t> here?

641 ↗

(On Diff #92339)

~0(!)ULL of course.

[grimar]

In D31136#705394, @dblaikie wrote:

Could you dump the relevant relocations in some object files you're testing?

I'd be curious to understand/see why so many relocations to the same symbol appear in a row - and wonder if it'd be good to consider caching all the results, not only the previous/most recent one.

llc.cpp.o.zip788 KBDownload

Uploaded "readelf -a" dump of llc.cpp.o,
notice ".rela.debug_info" sections contains tons of relocations against ".debug_str" section symbol in a row.
Also relocations against other symbols are often grouped as well.

I cached only the last relocation in this patch because I knew dynamic linkers do that.
I can try to experiment with caching more results tomorrow to see what will happen.

[grimar]

• Addressed review comments.
• Performed cleanup of error reporting for new getSymbolAddress() method.

DebugInfo/DWARF/DWARFContext.cpp

627 ↗

(On Diff #92339)

Done.

641 ↗

(On Diff #92339)

I used Expected<>, it was used for SymbolRef::getAddress(), so is it looks consistent to use it here too.

[grimar]

Ping. (not sure we will use this change in LLD, since D31424 looks better, but it still looks like a good cleanup and speedup for other users. If no I'll abandon this).

[grimar]

• Reimplemented to use std::map instead of "is last symbol the same" optimization.

[grimar]

Ping.

FWIW, found one more place where it useful in LLD. It creates DWARFContextInMemory for error reporting for each object (when there are any errors of course).
Since this speedups relocation handling, it should speedup thing a bit. It is not very important probably, because we have default linit for errors amount (20)
and it is not a regular linker path. But anyways all users that creates context for something can have benefit from speedup this patch do.

[dblaikie]

Still curious to hear back from Adrian - but can revisit this post-commit if he's got any particular perspective to add :)

lib/DebugInfo/DWARF/DWARFContext.cpp

1052 ↗

(On Diff #97658)

Probably an llvm::DenseMap here?

[grimar]

lib/DebugInfo/DWARF/DWARFContext.cpp

1052 ↗

(On Diff #97658)

I'll do benchmarks at monday for this change then and commit fastest solution then.
Sounds fine ?

[dblaikie]

lib/DebugInfo/DWARF/DWARFContext.cpp

1052 ↗

(On Diff #97658)

Sure

[aprantl]

I don't have an informed opinion at the moment, besides "let's benchmark it", so please go ahead for now. Once we switch over LLDB to use the LLVM DWARF parser I will likely revisit this in more depth.

[grimar]

lib/DebugInfo/DWARF/DWARFContext.cpp

1052 ↗

(On Diff #97658)

Ah, I just faced it again and now I remember. I already tried to use DenseMap initially, but it would require DenseMapInfo<SymbolRef> specialization, when std::map just wants only operator< which SymbolRef already has.
I would probably don't add this specialization to reduce amount of code for start. I don't expect significant perfomance difference here, so less code is better probably. So I am going to commit std::map version then..

llvm/trunk/lib/DebugInfo/DWARF/DWARFContext.cpp

 static Error createError(const Twine &Reason, llvm::Error E) {
   return make_error<StringError>(Reason + toString(std::move(E)),
                                  inconvertibleErrorCode());
 }
 
 /// Returns the address of symbol relocation used against. Used for futher
 /// relocations computation. Symbol's section load address is taken in account if
 /// LoadedObjectInfo interface is provided.
-static Expected<uint64_t> getSymbolAddress(const object::ObjectFile &Obj,
-                                           const RelocationRef &Reloc,
-                                           const LoadedObjectInfo *L) {
+static Expected<uint64_t>
+getSymbolAddress(const object::ObjectFile &Obj, const RelocationRef &Reloc,
+                 const LoadedObjectInfo *L,
+                 std::map<SymbolRef, uint64_t> &Cache) {
   uint64_t Ret = 0;
   object::section_iterator RSec = Obj.section_end();
   object::symbol_iterator Sym = Reloc.getSymbol();
 
+  std::map<SymbolRef, uint64_t>::iterator CacheIt = Cache.end();
   // First calculate the address of the symbol or section as it appears
   // in the object file
   if (Sym != Obj.symbol_end()) {
+    bool New;
+    std::tie(CacheIt, New) = Cache.insert({*Sym, 0});
+    if (!New)
+      return CacheIt->second;
+
     Expected<uint64_t> SymAddrOrErr = Sym->getAddress();
     if (!SymAddrOrErr)
       return createError("error: failed to compute symbol address: ",
                          SymAddrOrErr.takeError());
 
     // Also remember what section this symbol is in for later
     auto SectOrErr = Sym->getSection();
     if (!SectOrErr)
getSymbolAddress(const object::ObjectFile &Obj, const RelocationRef &Reloc,
   //           (Address of Section in File) +
   //           (Load Address of Section)
   // RSec is now either the section being targeted or the section
   // containing the symbol being targeted. In either case,
   // we need to perform the same computation.
   if (L && RSec != Obj.section_end())
     if (uint64_t SectionLoadAddress = L->getSectionLoadAddress(*RSec))
       Ret += SectionLoadAddress - RSec->getAddress();
+
+  if (CacheIt != Cache.end())
+    CacheIt->second = Ret;
+
   return Ret;
 }
 
 static bool isRelocScattered(const object::ObjectFile &Obj,
                              const RelocationRef &Reloc) {
   const MachOObjectFile *MachObj = dyn_cast<MachOObjectFile>(&Obj);
   if (!MachObj)
     return false;
if (!Map) {
       if (RelSecName == "debug_types")
         Map = &TypesSections[*RelocatedSection].Relocs;
       else if (RelSecName == "debug_types.dwo")
         Map = &TypesDWOSections[*RelocatedSection].Relocs;
       else
         continue;
     }
 
+    std::map<SymbolRef, uint64_t> AddrCache;
     if (Section.relocation_begin() != Section.relocation_end()) {
       uint64_t SectionSize = RelocatedSection->getSize();
       for (const RelocationRef &Reloc : Section.relocations()) {
         // FIXME: it's not clear how to correctly handle scattered
         // relocations.
         if (isRelocScattered(Obj, Reloc))
           continue;
 
-        Expected<uint64_t> SymAddrOrErr = getSymbolAddress(Obj, Reloc, L);
+        Expected<uint64_t> SymAddrOrErr =
+            getSymbolAddress(Obj, Reloc, L, AddrCache);
         if (!SymAddrOrErr) {
           errs() << toString(SymAddrOrErr.takeError()) << '\n';
           continue;
         }
 
         object::RelocVisitor V(Obj);
         object::RelocToApply R(V.visit(Reloc.getType(), Reloc, *SymAddrOrErr));
         if (V.error()) {