← Tiled Thoughts
·8 min read

Data Structure and Iterator Kung Fu in LLVM

Contents
  1. Why LLVM ships its own containers
  2. Core Value Types (which own nothing)
  3. StringRef
  4. ArrayRef / MutableArrayRef
  5. Twine
  6. Small-Size Optimized Containers
  7. SmallVector<T, N>
  8. SmallString
  9. SmallPtrSet<T*, N>
  10. “Hashy” Workhorses
  11. DenseMap<KeyT, ValueT> / DenseSet
  12. StringMap
  13. Arenas, Uniquing, and more
  14. BumpPtrAllocator
  15. FoldingSet
  16. Error handling the LLVM way
  17. IR-Centric Must-Knows
  18. Traversal Idioms
  19. Mutation Safety
  20. CFG Helpers
  21. Range and Iterator (Halloween!) Candy
  22. Choosing the Right Data Structure (A Decision Matrix)
  23. Common “Shooting Yourself in the Foot” Pitfalls
  24. Micro-Benchmarks
  25. Compile and Run
  26. Conclusion

Practical patterns, zero-copy views, and safe mutation loops for faster LLVM passes.

When to use SmallVector vs std::vector, why DenseMap feels like cheating, how StringRef & ArrayRef avoid copies, and the iterator tricks that make LLVM code elegant and fast.

Why LLVM ships its own containers

LLVM’s Abstract Data Types (ADT) exist to minimize allocations, avoid unnecessary copies, and keep hot paths fast. They are battle-tested for compiler workloads: small objects, pointer-heavy graphs, predictable iteration patterns, stable string handling, and more.

Core Value Types (which own nothing)

StringRef

ArrayRef / MutableArrayRef

Twine

Small-Size Optimized Containers

SmallVector<T, N>

SmallVector<Value*, 4> WorkList; // Inline storage for 4 pointers
WorkList.push_back(NewValue); // No heap allocation until size > 4
while (!WorkList.empty()) {
    Value *V = WorkList.pop_back_val(); // Pops the last element
    // Process V...
}

SmallString

SmallPtrSet<T*, N>

SmallPtrSet<BasicBlock*, 8> Visited;
for (BasicBlock &BB : Function) {
    if (Visited.insert(&BB).second) {
        // First time visiting BB
    }
}

“Hashy” Workhorses

DenseMap<KeyT, ValueT> / DenseSet

DenseMap<Value*, unsigned> rank;
for (auto &I : instructions(F)) {
    rank.try_emplace(&I, rank.size()); // Assign unique rank if not present
}

Custom Keys providing DenseMapInfo<Key> with:

struct MyKey {int a; int b;};
template<> struct DenseMapInfo<MyKey> {
  static MyKey getEmptyKey() { return {INT_MIN, INT_MIN}; } // Use unlikely values
  static MyKey getTombstoneKey() { return {INT_MIN + 1, INT_MIN + 1}; } 
  static unsigned getHashValue(const MyKey &K) {
    return hash_combine(K.a, K.b); // Combine fields for hash
  }
  static bool isEqual(const MyKey &LHS, const MyKey &RHS) {
    return LHS.a == RHS.a && LHS.b == RHS.b;
  }
};

StringMap

StringMap<unsigned> NameToID;
NameToID["foo"]++; // Increment count for "foo"

Erasing While Iterating

When erasing elements from DenseMap or StringMap during iteration, use the following pattern to avoid invalidating the iterator:

for (auto It = Map.begin(); It != Map.end(); ) {
    if (it->second == 0) it = Map.erase(It); // erase returns the next valid iterator
    else ++It; // only increment if not erasing
}

Arenas, Uniquing, and more

BumpPtrAllocator

BumpPtrAllocator arena;
StringSaver saver(arena);
StringRef name = saver.save("temporary_name"); // Owned by arena

FoldingSet


struct Key : public FoldingSetNode {
    int a;
    StringRef b;
    void Profile(FoldingSetNodeID &ID) const {
        ID.AddInteger(a);
        ID.AddString(b);
    }
};

FoldingSet<Key> KeySet;
void insertOrGet(int a, StringRef b, BumpPtrAllocator &arena) {
    Key Temp{a, b};
    void *InsertPos;
    if (Key *Existing = KeySet.FindNodeOrInsertPos(Temp, InsertPos)) { // hash-consed
        // Use Existing
    } else {
        Key *NewKey = new (arena.Allocate<Key>()) Key{a, saver.save(b)};
        KeySet.InsertNode(NewKey, InsertPos);
    }
}

Error handling the LLVM way

LLVM provides a rich set of utilities for error handling, including Error, Expected<T>, and handleErrors. These abstractions allow for expressive and type-safe error propagation without relying on exceptions.

Expected<std::unique_ptr<Module>> loadModule(StringRef Path, LLVMContext &Ctx) {
    SMDiagnostic Err;
    std::unique_ptr<Module> M = parseIRFile(Path, Err, Ctx);
    if (!M) return createStringError(inconvertibleErrorCode(), "Failed to parse IR file");
    return std::move(M);
}

IR-Centric Must-Knows

Traversal Idioms

for (Function &F : M) { // Look at all functions in Module M.
    for (BasicBlock &BB : F) { // Look at all basic blocks in Function F.
        for (Instruction &I : BB) { // Look at all instructions in BasicBlock BB.
            // Process instruction I
        }
    }
}

for (Use &U : V->uses()) { // Look at all uses of Value v.
    if (auto *I = dyn_cast<Instruction>(U.getUser())) {
        // Process instruction I that uses V
    }
}

for (Value *op : I.operands()) { // Look at all operands of Instruction I.
    // Process operand op
}
for(Use &U : I.operands()) { // Mutable access to operands
    // Mutate operand U
}

Mutation Safety

for (Instruction &I : make_early_inc_range(BB)) { // Safe to mutate BB while iterating
    I.eraseFromParent(); // Safe to erase while iterating
}

CFG Helpers

for (BasicBlock *Pred : predecessors(&BB)) {
    // Process predecessor Pred
}

for (BasicBlock *BB : ReversePostOrderTraversal(&F)) {
    // Process BB in RPO
}

Range and Iterator (Halloween!) Candy

Choosing the Right Data Structure (A Decision Matrix)

Need Pick Why
≤ N typical, latency-sensitive SmallVector<T,N> avoids heap
Pointer membership/visited SmallPtrSet<T*,N> inline + hash
Many lookups, pointer/int keys DenseMap/Set cache-friendly
String keys, own them StringMap<T> single alloc
Non-owning string/array view StringRef / ArrayRef zero copy
Thousands of short-lived nodes BumpPtrAllocator linear alloc
Structural dedup FoldingSet<T> profile-based hashcons

Common “Shooting Yourself in the Foot” Pitfalls

Micro-Benchmarks

Let’s look at a simple harness comparing DenseMap vs std::unordered_map for pointer keys.

#include "llvm/ADT/DenseMap.h"
#include <unordered_map>
#include <chrono>
#include <random>

using namespace llvm;

int main() {
  constexpr size_t N = 100000;
  std::vector<void*> keys(N);
  for (size_t i=0;i<N;++i) keys[i] = reinterpret_cast<void*>((i+1)*16);

  DenseMap<void*, int> dm; dm.reserve(N);
  auto t0 = std::chrono::high_resolution_clock::now();
  for (size_t i=0;i<N;++i) dm.try_emplace(keys[i], (int)i);
  auto t1 = std::chrono::high_resolution_clock::now();

  std::unordered_map<void*, int> um; um.reserve(N);
  for (size_t i=0;i<N;++i) um.emplace(keys[i], (int)i);
  auto t2 = std::chrono::high_resolution_clock::now();

  auto ns1 = std::chrono::duration_cast<std::chrono::nanoseconds>(t1-t0).count();
  auto ns2 = std::chrono::duration_cast<std::chrono::nanoseconds>(t2-t1).count();

  printf("DenseMap insert: %lld ns, unordered_map insert: %lld ns\n",
         (long long)ns1, (long long)ns2);
}

When run, you should see DenseMap outperforming std::unordered_map significantly for pointer keys due to its cache-friendly design and lower overhead.

Compile and Run

clang++ bench.cpp -O3 -I/path/to/llvm/include -o bench
./bench

DenseMap insert: 298833 ns, unordered_map insert: 50096584 ns

From this simple benchmark, we observe that DenseMap is orders of magnitude faster than std::unordered_map for pointer keys, highlighting its efficiency for compiler workloads. Do more extensive benchmarking using perf!

Conclusion

LLVM’s ADT library provides a rich set of data structures and iterator patterns optimized for compiler workloads. By leveraging these tools effectively, you can write passes that are both efficient and maintainable. Understanding when and how to use these structures is key to mastering LLVM development. Happy coding!