We were seeing occasional test failures with expensive checks enabled.
The issue was tracked down to a `sort` which should instead be a
`stable_sort` to ensure determinism. Checked locally and the
non-determinism went away.

Previously, the test
`llvm/test/tools/llvm-gsymutil/ARM_AArch64/macho-gsym-merged-callsites-dsym.yaml`
[was disabled](https://github.com/llvm/llvm-project/pull/119957/files)
due to failing on Linux.

The issue is that the merged functions appear in a different order in
the final produced `gSYM`.
To ensure deterministic ordering of merged functions, we change the
sorting of functions to use the `stable_sort` algorithm. Before merged
functions, this was not an issue as the address is used as a comparator
in the sorting algorithm so there was no chance of two functions testing
as identical according to the comparator.

Confirmed that test now passes locally with
`-DLLVM_ENABLE_EXPENSIVE_CHECKS=ON`.

This PR adds support in the gSYM format for call site information and
adds support for loading call sites from a YAML file. The support for
YAML input is mostly for testing purposes - so we have a way to test the
functionality.

Note that this data is not currently used in the gSYM tooling - the
logic to use call sites will be added in a later PR.

The reason why we need call site information in gSYM files is so that we
can support better call stack function disambiguation in the case where
multiple functions have been merged due to optimization (linker ICF).
When resolving a merged function on the callstack, we can use the call
site information of the calling function to narrow down the actual
function that is being called, from the set of all merged functions.

See [this
RFC](https://discourse.llvm.org/t/rfc-extending-gsym-format-with-call-site-information-for-merged-function-disambiguation/80682)
for more details on this change.

This patch introduces support for storing debug info for merged
functions in the GSYM debug info. It allows GSYM to represent multiple
functions that share the same address range, which occur when multiple
functions are merged during linker ICF.

The core of this functionality is the new `MergedFunctionsInfo` class,
which is integrated into the existing `FunctionInfo` structure. During
GSYM creation, functions with identical address ranges are now grouped
together, with one function serving as the "master" and the others
becoming "merged" functions. This organization is preserved in the GSYM
format and can be read back and displayed when dumping GSYM information.

Old readers will only see the master function, and ther "merged"
functions will not be processed.

Note: This patch just adds the functionality to the gSYM format -
additional changes to the gsym format and algorithmic changes to logic
existing tooling are needed to take advantage of this data.

Exact output of `llvm-gsymutil --verify --verbose` for the included
test:
[gist](https://gist.github.com/alx32/b9c104d7f87c0b3e7b4171399fc2dca3)

GsymUtil, like DwarfDump --verify, spews a *lot* of data necessary to
understand/diagnose issues with DWARF data. The trouble is that the kind
of information necessary to make the messages useful also makes them
nearly impossible to easily categorize. I put together a similar output
categorizer (https://github.com/llvm/llvm-project/pull/79648) that will
emit a summary of issues identified at the bottom of the (very verbose)
output, enabling easier tracking of issues as they arise or are
addressed.

There's a single output change, where a message "warning: Unable to
retrieve DWO .debug_info section for some object files. (Remove the
--quiet flag for full output)" was being dumped the first time it was
encountered (in what looks like an attempt to make something easily
grep-able), but rather than keep the output in the same order, that
message is now a 'category' so gets emitted at the end of the output.
The test 'tools/llvm-gsymutil/X86/elf-dwo.yaml' was changed to reflect
this difference.

---------

Co-authored-by: Kevin Frei <freik@meta.com>

Summary:
FileEntry.Dir can be empty if debug info only contains relative path.
This caused an assertion failure when gsym segmentation is trying to
copy a file entry with empty dir. As the fitst entry of StringTable is
always empty (and is preserved), `StringOffsetMap` doesn't have key 0.
Hence, `find(0)` returns `End` and `operator->()` fails the assertion

Test Plan:
./bin/llvm-lit -sv llvm/test/tools/llvm-gsymutil/X86/elf-empty-dir.yaml

Now that llvm::support::endianness has been renamed to
llvm::endianness, we can use the shorter form.  This patch replaces
llvm::support::endianness with llvm::endianness.

This patch removes two log messages that were causing noisy output:
- when we have a zero sized symbol that gets removed in favor of something with a size or with debug info
- when an inlined function's address range has the same high and low pc, don't emit an error message as this is a common technique to indicate a function has been stripped or is no longer present.

Differential Revision: https://reviews.llvm.org/D156834

llvm-gsymutil was maintaining an address ranges collection behind a mutex and having the multi-threaded code access this and hold the mutex was causing slowdown when converting DWARF to GSYM. This patch does the following:
- removes the "Ranges" variable from the GsymCreator and any functions and places that used it
- clients don't try to detect if a function has been added for an address range, we now remove any inferior copies of information in the GsymCreator::finalize() routine as was done before, we just have more items to remove, though performance is greator due to less mutex thread locking
- after I started adding all of the inferior funtion info objects the previous patch that tried to remove infrior debug info had bugs in it, so I replace the removeIfBinary() function in GsymCreator with a more efficient and easier to debug way to do things which copies items from the GsymCreator::Funcs into a new vector of FunctionInfo objects and then replaces GsymCreator::Funcs at the end.
- Sorting of FunctionInfo objects has been modified to also compare InlineInfo objects. We found cases where LTO was ruining inline function address ranges and we ended up with a variety of FunctionInfo objects for the same range that had varying amounts of valid debug info. This patch now ensure that two function info objects with different inline info for the same function address range, the best one will be picked to ensure the greatest fidelity.
- If we detect that a DW_TAG_subprogram has inline functions and after parsing it, we don't end up with any valid inline information, we set the optional to std::nullopt to avoid emitting empty inline information and wasting space.

My tests show a 200% perf increase on M1 macs and a 100% performance increase on linux machines for the same complex large DWARF input binary.

Differential Revision: https://reviews.llvm.org/D156773