HomeArchiveBlog


Original contents are licensed under CC BY-NC 4.0. All rights reserved © 2026 Kai.
Back to Archives
LLVM ADT Library Overview

An introduction to the LLVM ADT (Abstract Data Types) library, covering its key data structures and their usage in compiler development.

Sun Nov 02 2025
Wed Dec 31 2025
LLVMADTData StructuresCompiler
On this page
  • LLVM ADT Library Overview
    • llvm::SmallVector
    • llvm::DenseMap/llvm::DenseSet
    • llvm::SetVector
    • llvm::TypeSwitch
    • llvm::YAML
    • llvm::StringRef

LLVM ADT Library Overview

在 MLIR/LLVM 中, 为了便捷开发以及性能需要, LLVM 提供了大量标准库中没有的数据结构和算法. 这些数据结构和算法被统称为 LLVM ADT 库. 这一章介绍一些常用的 LLVM ADT.

llvm::SmallVector

llvm::SmallVector 是一个类似于 std::vector 的容器, 但它做了小规模数据优化, 允许在栈上分配一定数量的元素, 以避免频繁的堆内存分配.

类型签名:

template<typename T, unsigned N = 16>
class SmallVector;

其中 N 就是要在栈上分配的元素数量. 在实际使用中, 函数定义中的临时 std::vector 类型变量几乎都可以替换为 llvm::SmallVector, 以提高性能. 例如:

#include "llvm/ADT/SmallVector.h"
void foo(Block *block) {
    // collect all affine.for ops in the block
    llvm::SmallVector<affine::AffineForOp, 4> loops;
    block.walk([&](affine::AffineForOp forOp) {
        loops.push_back(forOp);
    });
}

SmallVector 是一个标准的容器, 可以和标准库中的 std::vector 一样使用各种迭代器. 这种栈分配优化很多地方都能见到, Google的 absl::InlinedVector 也是类似的.

另外, 由于每一种不同的 N 创建出来的 SmallVector 都是一个不同的类型, LLVM 提供了 SmallVectorImpl<> 用来简化将 SmallVector 类型用作函数参数类型时的情形, 例如:

void processVector(llvm::SmallVectorImpl<int> &vec) {
    // process the vector
}
llvm::SmallVector<int, 8> myVec8 = {1, 2, 3};
llvm::SmallVector<int, 4> myVec4 = {4, 5, 6};
processVector(myVec8); // OK
processVector(myVec4); // OK

llvm::DenseMap/llvm::DenseSet

llvm::DenseMap 是一个类似于 std::unordered_map 的哈希表容器, 但它在内存使用和性能上做了优化. 它使用开放地址法解决哈希冲突, 并且在内部使用一个连续的数组来存储元素, 以提高缓存命中率.

类型签名:

template<typename KeyT, typename ValueT, typename KeyInfoT = DenseMapInfo<KeyT>>
class DenseMap;

其中 KeyInfoT 用来定义键类型的哈希函数和相等比较函数. 如果你的类型没有定义 std::hash 或者 llvm::hash_value 函数, 那么你需要自己定义一个 DenseMapInfo<> 特化类, 并提供需要的API实现. 例如:

#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/DenseMapInfo.h"
#include "llvm/ADT/Hashing.h"

namespace llvm {
template<>
struct DenseMapInfo<MyType> {
    static inline MyType getEmptyKey() { return MyType::getEmptyKey(); }
    static inline MyType getTombstoneKey() { return MyType::getTombstoneKey(); }
    static unsigned getHashValue(const MyType &val) {
        return llvm::hash_value(val.someField);
    }
    static bool isEqual(const MyType &lhs, const MyType &rhs) {
        return lhs == rhs;
    }
};
}

namespace my_namespace {
llvm::DenseMap<MyType, int> myMap; // then you can use it
}

对于 llvm::DenseSet, 它和 std::unordered_set 类似, 用法和 llvm::DenseMap 也类似.

llvm::SetVector

llvm::SetVector 是一个结合了集合和向量特性的容器. 它既保证元素的唯一性, 又保持元素的插入顺序. 例如:

#include "llvm/ADT/SetVector.h"
llvm::SetVector<int> mySetVector;
mySetVector.insert(1);
mySetVector.insert(2);
mySetVector.insert(1); // duplicate, will be ignored
for (int v : mySetVector) {
    std::cout << v << " "; // prints "1 2"
}

实际上一个 SetVector 对象就是同时维护了一个 SmallVector 和一个 DenseSet, 以实现它的功能, 根据它的类型定义可见一斑:

template<typename T, typename Vector = SmallVector<T, 0>, 
        typename Set = DenseSet<T>, unsigned N = 0>
class SetVector;

它既提供了一个集合应该有的接口(insert, count, contains), 也提供了一个向量应该有的接口. 可以使用向量的迭代器来遍历元素, 也可以使用集合的接口来检查元素是否存在.

#include "llvm/ADT/SetVector.h"
llvm::SetVector<int> mySetVector;
for (int i = 0; i < 10; ++i) {
    mySetVector.insert(i % 3); // insert some duplicates
}
for (int v : mySetVector) {
    std::cout << v << " "; // prints "0 1 2"
}

一些比较特别的API是 set_union()/set_subtract(), 用来原地计算两个集合的并集和差集. 例如:

llvm::SetVector<int> setA = {1, 2, 3};
llvm::SetVector<int> setB = {3, 4, 5};
setA.set_union(setB); // now setA contains {1, 2, 3, 4, 5}
setA.set_subtract(setB); // now setA contains {1, 2}

另一个API是 getArrayRef(), 返回一个 ArrayRef<value_type> 对象, 包含了所有元素的引用, 也是一个容器.

最后一个特别的API是 takeVector(), 它会清空 SetVector 中的 Set 对象, 然后将 Vector 对象的所有权转移出去, 返回一个 Vector 对象. 实现类似:

Vector takeVector() {
    set_.clear(); // clear the set
    return std::move(vector_); // move the vector out
}

所以一旦调用了这个API, 就不应该再访问原来的 SetVector 对象了. 例如可能上来就干出这种事:

llvm::SetVector<int> mySetVector = ...;
for (auto v : mySetVector.takeVector()) {
    std::cout << v << " "; // prints all elements
}
mySetVector.insert(42); // ERROR: mySetVector is now in an invalid state

为了遍历元素, 直接使用 for (auto v : mySetVector) 就可以了.

llvm::TypeSwitch

llvm::TypeSwitch 是一个类似于 switch 语句的模板类, 用来根据对象的动态类型执行不同的代码. 可以用来替代一系列的 if-else 语句, 使代码更简洁. 例如:

#include "llvm/ADT/TypeSwitch.h"
unsigned getInstructionCycle(Operation *op) {
    return llvm::TypeSwitch<Operation *, unsigned>(op)
        .Case<arith::AddFOp>([](arith::AddFOp) { return 1; })
        .Case<arith::MulFOp>([](arith::MulFOp) { return 2; })
        .Case<arith::DivFOp>([](arith::DivFOp divOp) { divOp->dumpPretty(); return 3; })
        .Default([](Operation *) { return 0; });
}

每个 .Case 分支都接受一个类型和 lambda 函数, 允许对该特定类型的对象进行特定的操作. 如果没有匹配的类型, 则执行 .Default 分支. 它的签名类似于

template<typename T, typename ResultT = void>
class TypeSwitch;

但需要注意的是, TypeSwitch 一般用在 LLVM/MLIR 自身就定义好的类型上, 如果要用在自己的类型上, 一般情况下是非常麻烦的.

细说起来是因为 LLVM 默认是禁用 RTTI 的, 不支持 dynamic_cast, 因为众所周知的 RTTI 开销. 于是 LLVM 内部自己实现了 llvm::isa<>, llvm::dyn_cast<>, llvm::TypeSwitch 这些用来处理动态类型的模版类. 它们依赖于 LLVM 内部为每个类型定义的 getKind() 和 getOpcode() 方法提供运行时类型信息, 同时每个类型必须提供静态 classof() 方法, 用来判断某个基类指针是否实际上指向该类型的对象.

于是问题就来了, LLVM 只为自己的类型定义了这些方法, 为了加入用户自己的类型, 必须继承自 LLVM 的某个基类, 并且为自己的类型实现上面要求的这些方法. 很多情况下这是很麻烦的. 不过对于 LLVM 开发, 很多时候只和 LLVM 自身的类型打交道就够了.

llvm::YAML

为了保证 LLVM 自身的独立性, LLVM 自己实现了一套 YAML 解析器, 用来解析类似 .clang-format, .clang-tidy 这样的配置文件. 如果想要复用这套解析器解析自己的配置, 只需要提供对应的 MappingTraits 即可. 也可以提供 ScalarEnumerationTraits 来解析枚举类型. 例如:

#include "llvm/ADT/YAMLTraits.h"

enum class MyEnum {
    Value1,
    Value2,
    Value3
};

struct MyConfig {
    unsigned int param1;
    std::vector<int> param2;
    MyEnum myEnumValue;
};

namespace llvm {
namespace yaml {
template<>
struct ScalarEnumerationTraits<MyEnum> {
    static void enumeration(IO &io, MyEnum &value) {
        io.enumCase(value, "Value1", MyEnum::Value1);
        io.enumCase(value, "Value2", MyEnum::Value2);
        io.enumCase(value, "Value3", MyEnum::Value3);
    }
};
}
}

template<>
struct llvm::yaml::MappingTraits<MyConfig> {
    static void mapping(IO &io, MyConfig &config) {
        // implement the mapping logic
        io.mapRequired("param1", config.param1);
        io.mapOptional("param2", config.param2, std::vector<int>{});
        io.mapRequired("myEnumValue", config.myEnumValue);
    }
};

需要注意的是, MappingTraits 的定义必须在 llvm::yaml 命名空间之外, 而 ScalarEnumerationTraits 的定义必须在 llvm::yaml 命名空间之内. 这个是因为ADL(Argument Dependent Lookup)规则, ScalarEnumerationTraits 只能在 llvm::yaml 命名空间中被查找到, 而 MappingTraits 可以在任何命名空间中被查找到.

接着可以使用 llvm::yaml::Input 来读取 YAML 文件.

#include "llvm/ADT/YAMLParser.h"
#include "llvm/ADT/YAMLTraits.h"

void parseYAML(llvm::StringRef filename) {
    llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> fileOrErr = llvm::MemoryBuffer::getFile(filename);
    if (std::error_code ec = fileOrErr.getError()) {
        llvm::errs() << "Failed to open file: " << ec.message() << "\n";
        return;
    }
    std::unique_ptr<llvm::MemoryBuffer> buffer = std::move(fileOrErr.get());
    llvm::yaml::Input yin(buffer->getBuffer());
    MyConfig config;
    yin >> config; // Parse the YAML into config object
    if (yin.error()) {
        llvm::errs() << "YAML parsing error: " << yin.error().message << "\n";
        return;
    }
}

llvm::StringRef

llvm::StringRef 是一个轻量级的字符串视图类, 用来表示不可变的字符串片段. 类似于在 C++17 中引入的 std::string_view. 它不持有字符串数据的所有权, 只是一个指向字符串数据的指针和长度. 这样可以避免不必要的字符串拷贝, 提高性能.

StringRef 提供了很多常用的字符串操作方法, 类似于在 Python 中能看到的很多字符串方法在这都能找到. 例如:

#include "llvm/ADT/StringRef.h"
llvm::StringRef str(" Hello, LLVM! ");
llvm::StringRef trimmedStr = str.trim(); // "Hello, LLVM!"
llvm::StringRef substr = str.substr(7, 4); // "LLVM"
bool startsWithHello = str.startswith("Hello"); // true
bool endsWithExclamation = str.endswith("!"); // true
llvm::StringRef lowerStr = str.lower(); // "hello, llvm!"
llvm::StringRef upperStr = str.upper(); // "HELLO, LLVM!"

使用方法基本类似其它语言中提供的字符串处理函数. 这个类算是对标准库中残缺的 std::string 的补充. 只需要注意 StringRef 不持有字符串数据的所有权, 因此在使用时要确保字符串数据的生命周期长于 StringRef 对象的生命周期.