[lldb] Speed up SymbolContextList::AppendIfUnique (#181952)

d7fb086668dff68 changed some calls from SymbolContextList::Append to
SymbolContextList::AppendIfUnique. This has unfortunately caused a huge
slow down in operations involving a large amount of symbol contexts (for
example, trying to autocomplete from an empty input "b <TAB>" will add
every function to the list), since AppendIfUnique scans the entire
symbol context list. Speed this up by adding a hash set to quickly
answer whether a symbol context is on the list or not.

This takes the time from running "b <TAB>" when debugging yaml2obj on my
machine from 600 seconds down to 13, which is about the same as before
d7fb086668dff68.

Note that AppendIfUnique has a logic error, which has been present since
its introduction. This has to do with the behavior controlled by
"merge_symbol_into_function", which will try to merge symbols with
symbol context containing the equivalent function to that symbol.

The previous patch tried to correct this by adding
CompareConsideringPossiblyNullSymbol(), which is not quite correct.

With CompareConsideringPossiblyNullSymbol(), if symbols are added in
this order:

- Symbol context without symbol.
- Equivalent symbol context with symbol.

The list will have only one symbol context WITHOUT the symbol.

If we stop using CompareConsideringPossiblyNullSymbol() and instead go
back to the == operator which d7fb086668dff68 introduced, with symbols
added in this order, the following will happen:

- Symbol context without symbol.
- Equivalent symbol context with symbol.
- The bare symbol, with "merge_symbol_into_function = true", the list
will have the same symbol twice.

This patch does not attempt to solve this, and instead focuses on the
performance issue d7fb086668dff68 introduced.

rdar://170477680
3 files changed
tree: 8f78fa540d4f46637fad8b32cbdeffb9116ad580
  1. .ci/
  2. .github/
  3. bolt/
  4. clang/
  5. clang-tools-extra/
  6. cmake/
  7. compiler-rt/
  8. cross-project-tests/
  9. flang/
  10. flang-rt/
  11. libc/
  12. libclc/
  13. libcxx/
  14. libcxxabi/
  15. libsycl/
  16. libunwind/
  17. lld/
  18. lldb/
  19. llvm/
  20. llvm-libgcc/
  21. mlir/
  22. offload/
  23. openmp/
  24. orc-rt/
  25. polly/
  26. runtimes/
  27. third-party/
  28. utils/
  29. .clang-format
  30. .clang-format-ignore
  31. .clang-tidy
  32. .git-blame-ignore-revs
  33. .gitattributes
  34. .gitignore
  35. .mailmap
  36. CODE_OF_CONDUCT.md
  37. CONTRIBUTING.md
  38. LICENSE.TXT
  39. pyproject.toml
  40. README.md
  41. SECURITY.md
README.md

The LLVM Compiler Infrastructure

OpenSSF Scorecard OpenSSF Best Practices libc++

Welcome to the LLVM project!

This repository contains the source code for LLVM, a toolkit for the construction of highly optimized compilers, optimizers, and run-time environments.

The LLVM project has multiple components. The core of the project is itself called “LLVM”. This contains all of the tools, libraries, and header files needed to process intermediate representations and convert them into object files. Tools include an assembler, disassembler, bitcode analyzer, and bitcode optimizer.

C-like languages use the Clang frontend. This component compiles C, C++, Objective-C, and Objective-C++ code into LLVM bitcode -- and from there into object files, using LLVM.

Other components include: the libc++ C++ standard library, the LLD linker, and more.

Getting the Source Code and Building LLVM

Consult the Getting Started with LLVM page for information on building and running LLVM.

For information on how to contribute to the LLVM project, please take a look at the Contributing to LLVM guide.

Getting in touch

Join the LLVM Discourse forums, Discord chat, LLVM Office Hours or Regular sync-ups.

The LLVM project has adopted a code of conduct for participants to all modes of communication within the project.