[dsymutil] Fix O(n^2) behavior when running on ld64.lld's current ICF output

[thakis]

Summary

STABS information consists of a list of records in the linked binary
that look like this:

OSO: path/to/some.o
SO: path/to/some.c
FUN: sym1
FUN: sym2
...

The linked binary has one such set of records for every .o file linked
into it.

When dsymutil processes the binary's STABS information, it:

1. Reads the .o file mentioned in the OSO line
2. For each FUN entry after it in the main executable's STABS info:
   1. it looks up that symbol in the symbol of that .o file
   2. if it doesn't find it there, it goes through all symbols in the main binary at the same address and sees if any of those match

With ICF, ld64.lld's STABS output claims that all identical functions
that were folded are in the .o file of the one that's deemed the
canonical one. Many small functions might be folded into a single
function, so there are .o OSO entries that end up with many FUN lines,
but almost none of them exist in the .o file's symbol table.

Previously, dsymutil would do a full scan of all symbols in the main
executable _for every of these entries_.

This patch instead scans all aliases once and remembers them per name.
This reduces the alias resolution complexity from
O(number_of_aliases_in_o_file * number_of_symbols_in_main_executable) to
O(number_of_aliases_in_o_file * log(number_of_aliases_in_o_file)).

In practice, it reduces the time spent to run dsymutil on
Chromium Framework from 26 min (after https://reviews.llvm.org/D89444)
or 12 min (before https://reviews.llvm.org/D89444) to ~8m20s.

We probably want to change how ld64.lld writes STABS entries when ICF
is enabled, but making dsymutil not have pathological performance for
this input seems like a good change as well.

No expected behavior change (other than it's faster). I verified that
for Chromium Framework, the generated .dSYM is identical with and
without this patch.

[thakis]

(Note to self: Upstream bug is https://crbug.com/1280965)

[thakis]

Didn't see the LLVM.tools/dsymutil/ARM::extern-alias.test failure locally since I'm building with only X86 and Aarch64 enabled. Looking…

[thakis]

This fixes the test. It found a problem, I had confused main binary and object file values.

Need to re-run numbers since we do some more work now – but the improvement in O() complexity remains, so hopefully it's still a good improvement.

[JDevlieghere]

Thanks Nico. LGTM modulo the inline nit.

llvm/tools/dsymutil/MachODebugMapParser.cpp

68

SeenValues sounds a bit generic. Maybe something like SeenAliasValues would make it more obvious that this is specific to aliases?

[thakis]

Thanks!

I re-ran the numbers. With the tweaked patch, needed 9m30s on the first run and 8m30s on the second run (warmer disk cache), so doing this correctly didn't cost a lot of performance. Still way over 2x faster than HEAD, and still 25% faster than HEAD with D89444 reverted.

llvm/tools/dsymutil/MachODebugMapParser.cpp

 //===- tools/dsymutil/MachODebugMapParser.cpp - Parse STABS debug maps ----===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "BinaryHolder.h"
 #include "DebugMap.h"
 #include "MachOUtils.h"
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallSet.h"
 #include "llvm/Object/MachO.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/WithColor.h"
 #include "llvm/Support/raw_ostream.h"
 #include <vector>
 
 namespace {
 using namespace llvm;
private:
   StringRef MainBinaryStrings;
   /// The constructed DebugMap.
   std::unique_ptr<DebugMap> Result;
   /// List of common symbols that need to be added to the debug map.
   std::vector<std::string> CommonSymbols;
 
   /// Map of the currently processed object file symbol addresses.
   StringMap<Optional<uint64_t>> CurrentObjectAddresses;
+
+  /// Lazily computed map of symbols aliased to the processed object file.
+  StringMap<Optional<uint64_t>> CurrentObjectAliasMap;
+
+  /// If CurrentObjectAliasMap has been computed for a given address.
+  SmallSet<uint64_t, 4> SeenValues;
+
   /// Element of the debug map corresponding to the current object file.
   DebugMapObject *CurrentDebugMapObject;
 
   /// Holds function info while function scope processing.
   const char *CurrentFunctionName;
   uint64_t CurrentFunctionAddress;
 
   std::unique_ptr<DebugMap> parseOneBinary(const MachOObjectFile &MainBinary,

 } // anonymous namespace
 
 /// Reset the parser state corresponding to the current object
 /// file. This is to be called after an object file is finished
 /// processing.
 void MachODebugMapParser::resetParserState() {
   CommonSymbols.clear();
   CurrentObjectAddresses.clear();
+  CurrentObjectAliasMap.clear();
+  SeenValues.clear();
   CurrentDebugMapObject = nullptr;
 }
 
 /// Commons symbols won't show up in the symbol map but might need to be
 /// relocated. We can add them to the symbol table ourselves by combining the
 /// information in the object file (the symbol name) and the main binary (the
 /// address).
 void MachODebugMapParser::addCommonSymbols() {
default:
     return;
   }
 
   auto ObjectSymIt = CurrentObjectAddresses.find(Name);
 
   // If the name of a (non-static) symbol is not in the current object, we
   // check all its aliases from the main binary.
   if (ObjectSymIt == CurrentObjectAddresses.end() && Type != MachO::N_STSYM) {
-    for (const auto &Alias : getMainBinarySymbolNames(Value)) {
-      ObjectSymIt = CurrentObjectAddresses.find(Alias);
-      if (ObjectSymIt != CurrentObjectAddresses.end())
+    if (SeenValues.count(Value) == 0) {
+      auto Aliases = getMainBinarySymbolNames(Value);
+      for (const auto &Alias : Aliases) {
+        auto It = CurrentObjectAddresses.find(Alias);
+        if (It != CurrentObjectAddresses.end()) {
+          auto AliasValue = It->getValue();
+          for (const auto &Alias : Aliases)
+            CurrentObjectAliasMap[Alias] = AliasValue;
           break;
         }
       }
+      SeenValues.insert(Value);
+    }
+
+    auto AliasIt = CurrentObjectAliasMap.find(Name);
+    if (AliasIt != CurrentObjectAliasMap.end())
+      ObjectSymIt = AliasIt;
+  }
 
   // ThinLTO adds a unique suffix to exported private symbols.
   if (ObjectSymIt == CurrentObjectAddresses.end()) {
     for (auto Iter = CurrentObjectAddresses.begin();
          Iter != CurrentObjectAddresses.end(); ++Iter) {
       llvm::StringRef SymbolName = Iter->getKey();
       auto Pos = SymbolName.rfind(".llvm.");
       if (Pos != llvm::StringRef::npos && SymbolName.substr(0, Pos) == Name) {