LLVM常用数据结构与API

前言

LLVM 作为现代编译器基础设施的代表，其模块化设计和强大的中间表示（LLVM IR）使其在编译优化、程序分析、语言实现、JIT 运行时等多个领域广泛应用。然而，想要高效地在 LLVM 上构建工具或开发新功能，必须深入理解其内部的数据结构与接口体系。
本笔记旨在为 LLVM 的使用者，尤其是希望在 C++ 层面编写 Pass、分析器或后端工具的开发者，提供一份实用的接口速查与设计参考。相比于官方文档的厚重和散乱，这里更注重常用 API 的结构化梳理、配套示例的直观呈现，以及开发过程中易踩的坑与实践建议。

Support 层

容器

LLVM 容器	分类	STL 类比	Small 版本优化	关键特性 / 适用场景	典型复杂度*	头文件
SmallVector<T,N>	顺序	`std::vector`	✅	栈上预留 N 元素，溢出再堆分配；最常用 IR 构造容器	push O(1) 均摊	`SmallVector.h`
TinyPtrVector	顺序	`std::vector<T*>`	部分	0/1 个元素时放指针本身，极致小数据	O(1)	`TinyPtrVector.h`
SmallString	字符串	`std::string`	✅	小字符串避免堆；可与 `StringRef` 零拷贝互转	O(1) append	`SmallString.h`
StringRef	视图	`std::string_view`	—	仅指针+长度，不拥有存储；不可变、零拷贝	O(1) 子串	`StringRef.h`
SmallBitVector / BitVector	位集	`std::vector<bool>`	可选	高效位图；数据流分析、CFG 标记	O(n/word) scan	`BitVector.h`
DenseMap<K,V>	哈希表	`std::unordered_map`	—	开放寻址 + 特殊哨值；比 STL 更快更紧凑	查找 O(1) 平均	`DenseMap.h`
SmallDenseMap<K,V,N>	哈希表	—	✅	DenseMap 带栈内 N 桶；小映射首选	O(1)	`DenseMap.h`
StringMap	哈希表	`unordered_map<string>`	—	Key 存储在表中一次分配；常用于符号表	O(1)	`StringMap.h`
MapVector<K,V>	复合	—	—	保序字典：`DenseMap` + `SmallVector` 组合	O(1) 查，顺序遍历 O(n)	`MapVector.h`
SetVector	复合	—	—	有序集合：`DenseSet` + `SmallVector`	O(1)+顺序	`SetVector.h`
SmallSetVector<T,N>	复合	—	✅	SetVector + 栈预留	同上	`SetVector.h`
DenseSet	集合	`unordered_set`	—	基于 DenseMap 的高效集合	O(1)	`DenseSet.h`
SmallDenseSet<K,N>	集合	—	✅	DenseSet + 栈 N 桶	O(1)	`DenseSet.h`
SmallPtrSet<T,N>	集合	`unordered_set<void*>`	✅	针对指针，哈希=位变换，无额外 Key 拷贝	O(1)	`SmallPtrSet.h`
SmallSet<T,N>	集合	`std::set`	✅	N 以内线性查，超出用 `std::set`	插入 O(N) / O(log n)	`SmallSet.h`
ArrayRef / MutableArrayRef	视图	`span<T>`	—	轻量数组片段视图；零拷贝参数传递	O(1)	`ArrayRef.h`
Optional	包装	`std::optional`	—	C++17 前实现，可空单值容器	O(1)	`Optional.h`
SmallVectorImpl	基类	—	—	`SmallVector` 抽象基类；接口复用	—	`SmallVector.h`
PointerIntPair / PointerUnion	压缩	—	—	利用指针空闲位存 tag，节约内存	O(1)	`PointerIntPair.h`
ScopedHashTable<K,V>	作用域表	—	—	嵌套作用域符号表；常用于解析器	O(1)	`ScopedHashTable.h`
FoldingSet	结构共享	—	—	结构同值唯一；LLVM IR 去重	查找 O(1)	`FoldingSet.h`
EquivalenceClasses	并查集	—	—	快速合并/判等；类型合并、别名分析	近 O(α(n))	`EquivalenceClasses.h`

SmallVector. h

llvm:: SmallVector 是 LLVM 中一个高性能的容器类，类似于 std::vector，但在栈上预分配一段空间，避免频繁堆分配，在性能关键场合（如编译器 IR 构建）被广泛使用。
引入方式：

#include "llvm/ADT/SmallVector.h"

使用方法：

// 定义
llvm::SmallVector<T, N>
// 例子
llvm::SmallVector<int, 4> Vec;
// 添加元素
Vec.push_back(42);
Vec.emplace_back(99);  // 就地构造
Vec.append({1, 2, 3}); // 批量添加
Vec.insert(Vec.begin() + 1, 77);
// 删除元素
Vec.pop_back();              // 移除最后一个
Vec.erase(Vec.begin() + 1);  // 移除某一项
Vec.clear();                 // 清空全部
// 访问元素
int x = Vec[0];       // 不做边界检查
int y = Vec.front();  // 第一个
int z = Vec.back();   // 最后一个
// 遍历
for (int v : Vec) {
    llvm::outs() << v << "\n";
}
// 大小与容量
size_t sz = Vec.size();
bool empty = Vec.empty();
Vec.reserve(10); // 手动扩容