Optimize objdump -objc-meta-data

[kastiglione]

Summary

Running a Debug build of objdump -objc-meta-data with a large Mach-O file is currently unnecessarily slow.

With some local test input, this change reduces the run time from 75-85s down to 15-20s.

The two changes are:

1. Assert on pointer equality not array equality
2. Replace vector<pair<address, symbol>> with DenseMap<address, symbol>

[compnerd]

I dont understand the changes to the assertion, could you please explain that?

tools/llvm-objdump/MachODump.cpp

1796

Please use a std::unique_ptr to avoid the leak.

[kastiglione]

I dont understand the changes to the assertion, could you please explain that?

Checking pointer equality first, before falling back on a more costly ArrayRef content equality.

[kastiglione]

Better answer:

The reason the assertion is so costly is that each iteration (of bind table entries) calls MachOBindEntry::operator==, which in turn does a member-wise equality check of the full array of bind opcodes. For a large Mach-O file, this can become time consuming and can be mitigated by a pointer equality check first.

[kastiglione]

Use unique_ptr

[compnerd]

lib/Object/MachOObjectFile.cpp

3079

These changes are technically introducing UB. Comparing iterators across containers is UB. So, we need a member-wise comparison. You can put this under expensive checks if you want though.

[kastiglione]

Compare .data() instead of .begin()

[compnerd]

lib/Object/MachOObjectFile.cpp

2827

Why not just change this to:

assert(Opcodes.data() == Other.Opcodes.data() && Opcodes.size() == Other.Opcodes.size() && "comparing differing opcodes");

[kastiglione]

lib/Object/MachOObjectFile.cpp

2827

The current assertion has value semantics, this change would switch the assertion to allow reference equality only. I'm not sure why the assertion is currently constructed the way it is. I don't think any of llvm would break, but some external code could in theory. If you think it's best to change, I'll go with it.

[compnerd]

lib/Object/MachOObjectFile.cpp

2827

Except that after your change, you are short-circuiting the check to pointer equality rather than value equality. So, changing it entirely to pointer equality might be the best approach. Are expensive asserts enabled by default? We could just demote this to an expensive check and leave it as a full value comparison as well.

[kastiglione]

Make the assertion depend on EXPENSIVE_CHECKS

[kastiglione]

Thanks @compnerd. If you are able to commit this too, I'd appreciate it.

[compnerd]

SVN r291398.

lib/Object/MachOObjectFile.cpp

case MachO::REBASE_TYPE_TEXT_ABSOLUTE32:
     return "text abs32";
   case MachO::REBASE_TYPE_TEXT_PCREL32:
     return "text rel32";
   }
   return "unknown";
 }
 
 bool MachORebaseEntry::operator==(const MachORebaseEntry &Other) const {
-  assert(Opcodes == Other.Opcodes && "compare iterators of different files");
+  assert(
+      (Opcodes.begin() == Other.Opcodes.begin() || Opcodes == Other.Opcodes) &&
+      "compare iterators of different files");
   return (Ptr == Other.Ptr) &&
          (RemainingLoopCount == Other.RemainingLoopCount) &&
          (Done == Other.Done);
 }
 
 iterator_range<rebase_iterator>
 MachOObjectFile::rebaseTable(ArrayRef<uint8_t> Opcodes, bool is64) {
   MachORebaseEntry Start(Opcodes, is64);

 
 int64_t MachOBindEntry::addend() const { return Addend; }
 
 uint32_t MachOBindEntry::flags() const { return Flags; }
 
 int MachOBindEntry::ordinal() const { return Ordinal; }
 
 bool MachOBindEntry::operator==(const MachOBindEntry &Other) const {
-  assert(Opcodes == Other.Opcodes && "compare iterators of different files");
+  assert(
+      (Opcodes.begin() == Other.Opcodes.begin() || Opcodes == Other.Opcodes) &&
+      "compare iterators of different files");
   return (Ptr == Other.Ptr) &&
          (RemainingLoopCount == Other.RemainingLoopCount) &&
          (Done == Other.Done);
 }
 
 iterator_range<bind_iterator>
 MachOObjectFile::bindTable(ArrayRef<uint8_t> Opcodes, bool is64,
                            MachOBindEntry::Kind BKind) {

tools/llvm-objdump/MachODump.cpp

if (ObjectFile *O = dyn_cast<ObjectFile>(&Bin)) {
     } else
       errs() << "llvm-objdump: '" << Filename << "': "
              << "Object is not a Mach-O file type.\n";
     return;
   }
   llvm_unreachable("Input object can't be invalid at this point");
 }
 
-typedef std::pair<uint64_t, const char *> BindInfoEntry;
-typedef std::vector<BindInfoEntry> BindTable;
-typedef BindTable::iterator bind_table_iterator;
-
 // The block of info used by the Symbolizer call backs.
 struct DisassembleInfo {
   bool verbose;
   MachOObjectFile *O;
   SectionRef S;
   SymbolAddressMap *AddrMap;
   std::vector<SectionRef> *Sections;
   const char *class_name;
   const char *selector_name;
   char *method;
   char *demangled_name;
   uint64_t adrp_addr;
   uint32_t adrp_inst;
-  BindTable *bindtable;
+  std::unique_ptr<SymbolAddressMap> bindtable;
   uint32_t depth;
 };
 
 // SymbolizerGetOpInfo() is the operand information call back function.
 // This is called to get the symbolic information for operand(s) of an
 // instruction when it is being done.  This routine does this from
 // the relocation information, symbol table, etc. That block of information
 // is a pointer to the struct DisassembleInfo that was passed when the
static void printObjc2_64bit_MetaData(MachOObjectFile *O, bool verbose) {
   info.S = MR;
   print_message_refs64(MR, &info);
 
   SectionRef II = get_section(O, "__OBJC2", "__image_info");
   if (II == SectionRef())
     II = get_section(O, "__DATA", "__objc_imageinfo");
   info.S = II;
   print_image_info64(II, &info);
-
-  if (info.bindtable != nullptr)
-    delete info.bindtable;
 }
 
 static void printObjc2_32bit_MetaData(MachOObjectFile *O, bool verbose) {
   SymbolAddressMap AddrMap;
   if (verbose)
     CreateSymbolAddressMap(O, &AddrMap);
 
   std::vector<SectionRef> Sections;
for (unsigned SectIdx = 0; SectIdx != Sections.size(); SectIdx++) {
     // archtecture.
     TripleName = "";
     ThumbTripleName = "";
 
     if (SymbolizerInfo.method != nullptr)
       free(SymbolizerInfo.method);
     if (SymbolizerInfo.demangled_name != nullptr)
       free(SymbolizerInfo.demangled_name);
-    if (SymbolizerInfo.bindtable != nullptr)
-      delete SymbolizerInfo.bindtable;
     if (ThumbSymbolizerInfo.method != nullptr)
       free(ThumbSymbolizerInfo.method);
     if (ThumbSymbolizerInfo.demangled_name != nullptr)
       free(ThumbSymbolizerInfo.demangled_name);
-    if (ThumbSymbolizerInfo.bindtable != nullptr)
-      delete ThumbSymbolizerInfo.bindtable;
   }
 }
 
 //===----------------------------------------------------------------------===//
 // __compact_unwind section dumping
 //===----------------------------------------------------------------------===//
 
 namespace {

 
 // get_dyld_bind_info_symbolname() is used for disassembly and passed an
 // address, ReferenceValue, in the Mach-O file and looks in the dyld bind
 // information for that address. If the address is found its binding symbol
 // name is returned.  If not nullptr is returned.
 static const char *get_dyld_bind_info_symbolname(uint64_t ReferenceValue,
                                                  struct DisassembleInfo *info) {
   if (info->bindtable == nullptr) {
-    info->bindtable = new (BindTable);
+    info->bindtable = llvm::make_unique<SymbolAddressMap>();
     SegInfo sectionTable(info->O);
     for (const llvm::object::MachOBindEntry &Entry : info->O->bindTable()) {
       uint32_t SegIndex = Entry.segmentIndex();
       uint64_t OffsetInSeg = Entry.segmentOffset();
       if (!sectionTable.isValidSegIndexAndOffset(SegIndex, OffsetInSeg))
         continue;
       uint64_t Address = sectionTable.address(SegIndex, OffsetInSeg);
-      const char *SymbolName = nullptr;
       StringRef name = Entry.symbolName();
       if (!name.empty())
-        SymbolName = name.data();
-      info->bindtable->push_back(std::make_pair(Address, SymbolName));
+        (*info->bindtable)[Address] = name;
     }
   }
-  for (bind_table_iterator BI = info->bindtable->begin(),
-                           BE = info->bindtable->end();
-       BI != BE; ++BI) {
-    uint64_t Address = BI->first;
-    if (ReferenceValue == Address) {
-      const char *SymbolName = BI->second;
-      return SymbolName;
-    }
-  }
-  return nullptr;
+  auto name = info->bindtable->lookup(ReferenceValue);
+  return !name.empty() ? name.data() : nullptr;
 }