[ADT] Fix a bug in EquivalenceClasses::erase (#161121)

This patch fixes a bug in EquivalenceClasses::erase, where we lose a
leader bit in a certain scenario.

Here is some background.  In EquivalenceClasses, each equivalence
class is maintained as a singly linked list over its members.  When we
join two classes, we concatenate the two singly linked lists.  To
support path compression, each member points to the leader (through
lazy updates).  This is implemented with the two members:

  class ECValue {
    mutable const ECValue *Leader, *Next;
    :
  };

Each member stores its leader in Leader and its sibling in Next.  Now,
the leader uses the Leader field to to point the last element of the
singly linked list to accommodate the list concatenation.  We use the
LSB of the Next field to indicate whether a given member is a leader
or not.

Now, imagine we have an equivalence class:

  Elem 1 -> Elem 2 -> nullptr
  Leader

and wish to remove Elem 2.  We would like to end up with:

  Elem 1 -> nullptr
  Leader

but we mistakenly drop the leader bit when we update the Next field of
Elem 1 with:

  Pre->Next = nullptr;

This makes Elem 1 the end of the singly linked list, as intended, but
mistakenly clears its leader bit stored in the LSB of Next, so we end
up with an equivalence class with no leader.

This patch fixes the problem by preserving the leader bit:

  Pre->Next = reinterpret_cast<const ECValue *>(
      static_cast<intptr_t>(Pre->isLeader()));

The unit test closely follows the scenario above.
2 files changed
tree: 0b1e11d5a511db5114d80a18c9abff8485af196b
  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.