Meta RFC: ADTs without C++ runtime dependency

LLVM Project
1

This is not (yet) an RFC, but rather a discussion that might lead to one or multiple RFCs. It started within the openmp project, but potentially affects the whole llvm-project, depending on the outcome :slight_smile:

There are projects such as libc, openmp, or flang-rt that may be written in C++ but want to avoid linking against the C++ STL. This requires them to sometimes reinvent the wheel and create helper/utility classes that would already exist in the STL. Sanitizers, too, apparently have that restriction and supply their own implementations of certain data structures
Some, like openmp, also want to avoid linking against LLVM to stay more independent and compatible for use with other compilers.

These projects currently cannot use “advanced data types”, such as llvm::StringRef (defined in llvm/include/llvm/ADT/StringRef.h), or llvm::SmallVector (defined in llvm/include/llvm/ADT/SmallVector.h), or even plain STL data types such as std::vector.

As a result, they either have to fall back to the traditional C-style programming (manual memory and string management etc.) or define their own utility classes.

While we (as in: people working on openmp) discussed our situation for openmp, we wondered if it may make sense to create a common and independent resource for advanced data types, that does not require linking against the C++ STL.

Some of our discussion points (see also the first of my linked PRs):

  • Why no C++ STL dependency?
    • “Many users rely on the fact that you can compile different parts of the code with different OpenMP compilers, link it all together and it still works. Pulling in a libc++ dependency will brick this workflow for users.” [1] @jprotze
    • “Having a dependency of libomp to libstdc++ is highly undesirable. That would create a C++ dependency for C-only compilers and, worse, create the same for Fortran codes.” [2] @mjklemm
    • “We have customers that use gcc and other compilers with this runtime.” [3] @TerryLWilmarth
  • Why avoid the C++ STL if it’s already pulled in by offload?
    The fact that offload depends on the C++ runtime is not much appreciated by some openmp people, so they would rather prefer offload lose that dependency than the other way around. (Nobody aims for removing the C++ STL from offload, that’s not the point here.)
  • Suggestion working around the issue (by @jprotze): use C++ STL, but with all names inside of some namespace to avoid mismatches with names from different C++ STL implementations.
Revisitting code duplication between compiler-rt and llvm/
LLVM Weekly - #640, April 6th 2026
[RFC] Top-level ADT resource without C++ runtime dependency
2

Something related, though it may not be directly relevant: it would be great if LLVM’s ADT could be moved out of llvm and made a top-level project. That would make it easier for other components to use it.

3 Likes
3

I don’t think this would be directly relevant given it’s not an explicit goal of the LLVM ADT library to not have a c++ runtime dependency, although I have no idea how hard it would be to tease them apart.

Also, what exact case do you have in mind where this would be easier? Most projects that could take advantage of the ADT library already depend on LLVM in one way or another so it’s easy enough to just include the headers and link against the library.

4

Do you have a concrete example of two libraries that could share the same implementation? I would be somewhat concerned that the sorts of things each project would need might look different enough that it’s not worth the effort to provide a generic solution.

5
6

ADT/Support depends on the C++ standard library by design. For instance SmallVector.h alone includes these C++ headers:

#include <algorithm>
#include <functional>
#include <initializer_list>
#include <iterator>
#include <limits>
#include <memory>
#include <new>
#include <type_traits>
#include <utility>

It needs to do so since it has to work with standard library features that are used in LLVM. When moving to the next C++ version, we even replace an Support/ADT feature with the C++ library one, e.g. llvm::Optional with std::optional. We could not do that if Support/ADT had to be shared with -nostdlib runtimes[1].

On the other side, it would be nice to have a (separate) shared Support/ADT library for runtimes, like there exists already for libc/libc++ code sharing: [RFC] Project Hand In Hand (LLVM-libc/libc++ code sharing).

  1. std::optional is header-only so would not require linking, but other features might. ↩︎

7

That’s a very good question. Examples I noticed so far:

  • flang-rt’s dynamic array implementation that I mentioned above could be merged with the proposed kmp_vector for openmp. The fact that libomp likes to use custom dynamic allocation routines could be solved by subclassing and overwriting private allocation wrappers.
  • libc’s string_view could be used in the implementation of the proposed kmp_str_ref for openmp which currently uses std::string_view internally (which probably isn’t much of an issue because it’s likely that std::string_view stays header-only)
  • libc’s string implementation could be useful for other (existing) code in openmp

Maybe people familiar with other projects can also contribute interesting examples.

I had AI search for some more and it found the following overlaps. I shortened the output so that it’s easier to skim and also because it sometimes did not interpret the overlap correctly imho. For example, it mentioned that libc’s string_view and and the proposed kmp_str_ref are “functionally equivalent — non-owning views over character data”, which is a weird definition of “functionally equivalent”, because they are not (in the current form). But, anyway, it might give a first impression of the scope.

BEGIN AI CONTENT

1. There are at least five independent implementations of the same concept — a growable, heap-backed array that avoids std::vector:

Library Type File Growth Strategy
flang-rt DynamicArray<T> flang-rt/lib/runtime/array.h Doubles capacity (starts at 4); AllocateMemoryOrCrash + move + free
libomp (proposed) kmp_vector<T,N> PR #176163 SmallVector-style: N inline elements, then heap; doubles on growth
libomp (existing) kmp_stats_event_vector openmp/runtime/src/kmp_stats.h:658 Doubles capacity (starts at 1024); __kmp_allocate + copy + __kmp_free
sanitizers __sanitizer::Vector<T> compiler-rt/lib/sanitizer_common/sanitizer_vector.h 25% growth; InternalAlloc + memcpy + InternalFree
scudo scudo::Vector<T,N> compiler-rt/lib/scudo/standalone/vector.h SmallVector-style: N inline elements, then mmap-backed; power-of-two growth

2. String View / String Reference

Library Type File
libc LIBC_NAMESPACE::cpp::string_view libc/src/__support/CPP/string_view.h
libomp (proposed) kmp_str_ref PR #176162
sanitizers (use raw const char * + length) scattered across sanitizer code
LLVM ADT llvm::StringRef llvm/include/llvm/ADT/StringRef.h

3. ArrayRef / Non-owning Array View

Library Type File
sanitizers __sanitizer::ArrayRef<T> compiler-rt/lib/sanitizer_common/sanitizer_array_ref.h
libc LIBC_NAMESPACE::cpp::span<T> libc/src/__support/CPP/span.h
LLVM ADT llvm::ArrayRef<T> llvm/include/llvm/ADT/ArrayRef.h

4. DenseMap / Hash Map

Library Type File
sanitizers __sanitizer::DenseMap compiler-rt/lib/sanitizer_common/sanitizer_dense_map.h
libc LIBC_NAMESPACE::internal::HashTable libc/src/__support/HashTable/table.h
libomp common_table / KMP_HASH macros openmp/runtime/src/kmp.h
LLVM ADT llvm::DenseMap llvm/include/llvm/ADT/DenseMap.h

5. Optional

Library Type File
libc LIBC_NAMESPACE::cpp::optional<T> libc/src/__support/CPP/optional.h
LLVM ADT (uses std::optional now) —

6. Small Fixed-size Buffer + Heap Fallback (SmallVector / SimpleVLA pattern)

Library Type File
libomp (existing) SimpleVLA<T,N> openmp/runtime/src/kmp_utils.h
libomp kmp_str_buf_t (512-byte inline bulk[]) openmp/runtime/src/kmp_str.h
scudo scudo::Vector<T,N> compiler-rt/lib/scudo/standalone/vector.h
libomp (proposed) kmp_vector<T,N> PR #176163
LLVM ADT llvm::SmallVector<T,N> llvm/include/llvm/ADT/SmallVector.h

7. Intrusive Linked Lists

Library Type File
sanitizers __sanitizer::IntrusiveList<T> compiler-rt/lib/sanitizer_common/sanitizer_list.h
libomp kmp_depnode_list_t, kmp_stats_list openmp/runtime/src/kmp.h, kmp_stats.h
flang-rt WorkQueue::TicketList flang-rt/include/flang-rt/runtime/work-queue.h

Summary Table of Best Sharing Candidates

ADT Concept Libraries That Duplicate It Sharing Potential
Growable vector flang-rt, libomp, sanitizers, scudo Very high — nearly identical logic, only allocator differs
String view libc, libomp (proposed), (sanitizers use raw ptrs) High — libc’s string_view could be reused by OpenMP
ArrayRef / span sanitizers, libc High — sanitizer version is a known fork of LLVM’s
Optional libc Medium — only libc has a standalone one so far
DenseMap sanitizers (fork of LLVM’s) Medium — very specialized, sanitizer version is already a fork
SmallVector libomp (SimpleVLA, proposed kmp_vector), scudo High — same pattern, different allocators

END AI CONTENT

8

those still depend on linking against the C++ STL, tho. As already mentioned by @boomanaiden154-1, it’s an open question, if/how/to what extend we can decouple existing llvm ADTs from linking against the C++ STL.

9

Having a separate (entirely unrelated to llvm/ADT) library that is independent of the C++ STL for shared use by our numerous runtimes sounds reasonable to me.

How would this library be used? Would the goal here be a header-only library, or something that gets statically linked into each runtime? (I assume the latter is not possible, as we have runtimes that are statically linked, esp. various sanitizer runtimes. Or it would require that the library supports symbol prefixing.)

10

I think header-only would be a reasonable starting point. Probably using what we have in libc/src/__support/CPP as a starting point.
As soon as / if there is a consensus that we want to go this way, I guess the best way forward would be that I create a dedicated RFC for that where we can figure out the details.

11
Library Type File
flang-rt Fortran::common::optional llvm-project/flang/include/flang/Common/optional.h at main · llvm/llvm-project · GitHub

flang and flang-rt share the same “Common” library[1] located in flang/include/flang/Common which is why your AI may not have considered it.

  1. I don’t think this is a good idea for the reasons already mentioned in this thread, but also because it requires additional annotations when compiling flang-rt with FLANG_RT_EXPERIMENTAL_OFFLOAD_SUPPORT=CUDA that flang doesn’t. ↩︎

12

what we might want to discuss in this thread is this:
Assuming we have such a library, let’s call it penguin for now.
I would think that it might make sense to then define subdirectories penguin/stl and penguin/adt, containing subsets of what we find in the C++ STL (e.g. vector) and the llvm ADTs (e.g. StringRef). I guess that this semantic split would make it easier to reason about the functionality.

13

This seems like it has significant overlap with the desire on the part of the C++ Standard to define a useful subset of the headers that are usable in a “Freestanding” implementation. I haven’t been following that work, but I see on cppreference that a bunch of new stuff was added in C++26. (Now string_view and array, but not vector.)

While AFAICT libc++ doesn’t implement this yet, it seems like a freestanding C++ stdlib would be a very useful starting-point for these use-cases. Maybe some effort should be put into making that work?

14

Thanks for the input!
In the “Notes” section in your link, it says: “Regardless, containers like vector, list, deque, and map will never be freestanding due to their dependencies on exceptions and heap.”
As a result, it seems to me like we would have three pieces to think about if we want to use that overlap:

  1. C++ headers for a “freestanding” implementation, such as type_traits. Could be shared with or be a part of libc++.
  2. header-only implementations for C++ STL entities that would not be suitable for a “freestanding” implementation from a C++ standard POV, such as vector. Would be based on 1), but probably not part of libc++.
  3. header-only implementations for ADTs, such as StringRef. Would be based on 1) and 2) and could serve as a base for the llvm ADTs by providing a subset of their functionality which could then be extended by them.
15

I think you’re missing an important part of what “freestanding” is in this context. The freestanding subset of the standard library as defined by the standard is (supposed to be) the set of utilities that work on any platform. However, freestanding implementations are free to (and usually do) provide more than that. If your freestanding environment supports dynamic memory allocation and exceptions, there is no reason for an implementation not to provide them, which libc++ does. libc++ can be configured to remove certain parts that can’t be supported instead of only providing the bare minimum a freestanding implementation has to provide.

FWIW I also don’t understand the fixation of header-only implementations in freestanding environments. You can still link libraries, it’s not that complicated.

16

Hm, thanks for the explanation of the “freestanding” concept, I guess that makes sense.

Shall we then proceed with an RFC discussing a top-level directory containing

  1. implementations for C++ STL entities, such as vector
  2. implementations for ADTs, such as StringRef. Would be based on 1) and could serve as a base for the llvm ADTs by providing a subset of their functionality which could then be extended by the llvm ADTs (which are not restricted by link dependency issues)

?

Header-only or not is probably just an implementation detail. (It might also be something that can be adapted later if volume / usage grows.)

17

Just wanted to give this a gentle ping to see if there are any question, comments, or concerns. Otherwise, I’ll go ahead and create the RFC to discuss the details.