[lld-macho][nfc] Minor clean up

[oontvoo]

Summary

• change the vector of relocs to std::list for ptr stability. (This field does not need to have fast access per index anyway. This should also make the remove/erase ops faster)
• when checking for entry existance use, .find() rather than the [] operator, which would actually create a new entry in the map.

[smeenai]

I'm wary about using linked lists, especially for relocations ... could you measure the perf and memory usage difference from that? (Maybe each subsection has few enough relocations that it doesn't make a massive difference, but I'm still curious.)

If pointer stability is the main motivation, would std::deque work?

[int3]

The list change is def a bit more controversial. I would split out the map changes into its own diff :)

Also, could you elaborate on where you anticipate needing pointer stability?

Finally, if we really need a list, we might want to use LLVM's ilist for better locality.

[int3]

clearing my queue

lld/MachO/Driver.cpp

static InputFile *addFile(StringRef path, ForceLoad forceLoadArchive,
   switch (magic) {
   case file_magic::archive: {
     // Avoid loading archives twice. If the archives are being force-loaded,
     // loading them twice would create duplicate symbol errors. In the
     // non-force-loading case, this is just a minor performance optimization.
     // We don't take a reference to cachedFile here because the
     // loadArchiveMember() call below may recursively call addFile() and
     // invalidate this reference.
-    if (ArchiveFile *cachedFile = loadedArchives[path])
-      return cachedFile;
+    auto entry = loadedArchives.find(path);
+    if (entry != loadedArchives.end())
+      return entry->second;
 
     std::unique_ptr<object::Archive> archive = CHECK(
         object::Archive::create(mbref), path + ": failed to parse archive");
 
     if (!archive->isEmpty() && !archive->hasSymbolTable())
       error(path + ": archive has no index; run ranlib to add one");
 
     auto *file = make<ArchiveFile>(std::move(archive));

lld/MachO/InputSection.h

 #include "lld/Common/LLVM.h"
 #include "lld/Common/Memory.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/CachedHashString.h"
 #include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/BinaryFormat/MachO.h"
 
+#include <list>
+
 namespace lld {
 namespace macho {
 
 class InputFile;
 class OutputSection;
 
 class InputSection {
 public:
public:
 
   OutputSection *parent = nullptr;
 
   uint32_t align = 1;
   // is address assigned?
   bool isFinal = false;
 
   ArrayRef<uint8_t> data;
-  std::vector<Reloc> relocs;
+  std::list<Reloc> relocs;
   // The symbols that belong to this InputSection, sorted by value. With
   // .subsections_via_symbols, there is typically only one element here.
   llvm::TinyPtrVector<Defined *> symbols;
 
 protected:
   // The fields in this struct are immutable. Since we create a lot of
   // InputSections with identical values for them (due to
   // .subsections_via_symbols), factoring them out into a shared struct reduces

lld/MachO/InputSection.cpp

 void ConcatInputSection::writeTo(uint8_t *buf) {
   assert(!shouldOmitFromOutput());
 
   if (getFileSize() == 0)
     return;
 
   memcpy(buf, data.data(), data.size());
 
-  for (size_t i = 0; i < relocs.size(); i++) {
-    const Reloc &r = relocs[i];
+  for (auto it = relocs.begin(); it != relocs.end(); ++it) {
+    const Reloc &r = *it;
     uint8_t *loc = buf + r.offset;
     uint64_t referentVA = 0;
     if (target->hasAttr(r.type, RelocAttrBits::SUBTRAHEND)) {
       const Symbol *fromSym = r.referent.get<Symbol *>();
-      const Reloc &minuend = relocs[++i];
+      ++it;
+      const Reloc &minuend = *it;
       uint64_t minuendVA;
       if (const Symbol *toSym = minuend.referent.dyn_cast<Symbol *>())
         minuendVA = toSym->getVA() + minuend.addend;
       else {
         auto *referentIsec = minuend.referent.get<InputSection *>();
         assert(!::shouldOmitFromOutput(referentIsec));
         minuendVA = referentIsec->getVA(minuend.addend);
       }

lld/MachO/UnwindInfoSection.cpp

void UnwindInfoSectionImpl<Ptr>::prepareRelocations(ConcatInputSection *isec) {
   assert(!isec->shouldOmitFromOutput() &&
          "__compact_unwind section should not be omitted");
 
   // FIXME: Make this skip relocations for CompactUnwindEntries that
   // point to dead-stripped functions. That might save some amount of
   // work. But since there are usually just few personality functions
   // that are referenced from many places, at least some of them likely
   // live, it wouldn't reduce number of got entries.
-  for (size_t i = 0; i < isec->relocs.size(); ++i) {
-    Reloc &r = isec->relocs[i];
+  for (Reloc &r : isec->relocs) {
     assert(target->hasAttr(r.type, RelocAttrBits::UNSIGNED));
 
     // Functions and LSDA entries always reside in the same object file as the
     // compact unwind entries that references them, and thus appear as section
     // relocs. There is no need to prepare them. We only prepare relocs for
     // personality functions.
     if (r.offset % sizeof(CompactUnwindEntry<Ptr>) !=
         offsetof(CompactUnwindEntry<Ptr>, personality))