LLVM源码浅析-1

前言

作为一个优秀的开源编译器框架，llvm的代码比gcc代码的可读性更好。因此无论是学习c++，还是学习编译原理、设计模式、数据结构，都是一个很好的学习目标。

这篇文章是受侯捷老师《STL源码剖析》的启发，希望对llvm中的数据结构进行一些解读，因为llvm中有许多类似于STL中的数据。例如 map-like containner、set-like container、sequential container、string container、bit container等容器。

原创不易，您的关注就是我最大的动力。希望看到的朋友能点个关注，后续会把这个llvm数据结构系列持续更新下去。

本文将对llvm中源码进行分析，主要是了解其中一个类似于std::vector的数据结构。并与之进行对比。

1.SmallVector概述

SmallVector是llvm中自定义的一种通用数据结构，在llvm的各层次间都可以使用。SmallVector与std::Vector非常类似 ，支持迭代、push_back、pop_back，以及随机存取元素。

但是SmallVector对于元素较少的情况时性能是优于std::vector的。这是因为SmallVector使用了一种比较通用的局部缓存设计模式，减少了malloc/free的巨大开销。接下来会以SmallVecotor为载体，一步步揭开局部缓存设计模式的神秘面纱。同时我们还可以从中学到一些设计类的技巧。

这篇文章需要一点c++基础，需要c++资料的同学可以在我的公众号[程序芯世界]回复c++即可获取Modern C++的学习资料。里面有一本讲c++ 设计模式的书个人感觉不错，并且提到了本文中的局部缓存设计模式，有兴趣的可以看看（因为觉得不错，当初还花了我30块买的这本电子书）。

2.局部缓存设计模式

在详细了解SmallVector之前先来回顾一下std::vector和std::array，对比之后更容易了解SmallVector的优势。

std::vector会调用malloc函数申请一块内存用于放置元素 std::array是对内置数组的一个封装，因此其存放元素的数组会与std::array放置在同一个位置。如果std::array是在栈上声明的，那么其存放元素的数组也位于栈上。

内存的位置不同导致了std::array与std::vector效率的不同。因为std::vector是通过malloc申请的堆内存，而std::array是栈内存。

堆内存的申请需要调用系统函数分配内存，这个开销是巨大的。相比之下，栈内存几乎是零开销，因为只需要调整栈指针。当然std::array也并不总是在栈上的，取决于你分配它的方式。但是任然会比std::vector少分配一次堆内存。

stackoverflow上有一个很好的关于两者的对比。std::vector versus std::array in C++

smallvector的本质就是当元素个数少的时候像std::array一样将存储元素的内存放在类里面，当元素个数多的时候像std::vector一样分配堆内存。这样就兼具了两者的优点。这种操作被称为局部缓存设计模式，在llvm很多地方都有体现。

下一节会对SmallVector进行详细介绍，主要是关注类之间的抽象。

2.SmallVector的继承关系

为了减少代码冗余和提高代码的可复用性，llvm对SmallVecotr这个类进行了多个层次的抽象。本节主要介绍与SmallVecotr有继承关系的六个类。

由于这几个类之间本身的关系并不复杂，因此没有使用UML图，而是简单的画出了继承关系。

SmallVector继承关系图

2.1 SmallVector

其中SmallVector继承自SmallVectorImpl和SmallVectorStorage。

template

首先来看SmallVector，它继承了SmallVectorImpl和SmallVectorStorage。SmallVector本身只有一系列构造函数（拷贝构造、赋值构造等），没有成员变量，具体的一些成员函数放在SmallVectorImpl中，存储元素的数组放在SmallVectorStorage中。需要注意的是SmallVectorStorage类中直接声明了一个数组。

2.2 SmallVectorStorage

template <typename T, unsigned N>
struct SmallVectorStorage {
  alignas(T) char InlineElts[N * sizeof(T)];
};

这个数组会和对象放在同一块内存，当需要存放的元素较少时就可以放在这个数组中，避免了调用malloc产生巨大的开销。

2.3 SmallVectorImpl

template <typename T>
class SmallVectorImpl : public SmallVectorTemplateBase

上面提到SmallVector中之定义了一些构造函数，而其他的一些具体的操作函数则定义在SmallVectorImpl。这样做的原因是什么呢？看明白下面这个小例子就理解为啥这样设计了。

// DISCOURAGED: Clients cannot pass e.g. SmallVector
hardcodedSmallSize(SmallVector

从上述的例子可以看出，hardcodedSmallSize函数接受的参数是SmallVector，如果传入的参数是SmallVector肯定是类型不匹配。此时SmallVectorImpl就起作用了，因为SmallVectorImpl是SmallVector的父类，可以向上隐式转换，同时也不用传递参数N。这就是设计SmallVectorImpl的妙处。

2.4 SmallVectorTemplateBase

下面两个都是SmallVectorTemplateBase类，不同的是第二个模板参数不同。针对元素是否为POD类型进行了偏特化。

template

以grow函数为例，来看是否为POD类型时不同的处理方式。下面为类型为非POD类型时grow函数的实现方式

template <typename T, bool TriviallyCopyable>
void SmallVectorTemplateBase

可以看到，非POD类型时，会调用moveElementsForGrow函数对每一个元素进行移动。同时会调用takeAllocationForGrow，如果是在堆上分配的内存takeAllocationForGrow会调用free释放之前分配的内存。

template <typename T>
class SmallVectorTemplateBase<T, true> : public SmallVectorTemplateCommon

下面是POD类型时grow函数的实现方式。

template <class Size_T>
void SmallVectorBase

与非POD类型的grow函数对比可以发现，这儿移动元素是调用memcpy直接对整体的内存进行拷贝。同时也没有对每一个元素的内存进行释放。

2.5 SmallVectorTemplateCommon

template <typename T, typename = void>
class SmallVectorTemplateCommon
    : public SmallVectorBase

SmallVectorTemplateCommon是不依赖于是否为POD类型的公共部分，冗余的模版参数T是为了给ArrayRef使用。ArrayRef可以是SmallVector或者std::Vector的引用，后续会写文章介绍ArrayRef。

2.6 SmallVectorBase

SmallVectorBase是SmallVector所有的公共部分

template <class Size_T> class SmallVectorBase {
protected:
  void *BeginX;
  Size_T Size = 0, Capacity;
  ...
}

其中BeginX表示目前使用空间的头部，Size表示已经使用的空间大小，Capacity表示目前空间的容量。需要注意的是BeginX的初始化。前面已经提到过，当元素数量较少时是存储在SmallVectorStorage定义的数组中。因此BeginX的初始值应该是InlineElts的地址。如下所示是SmallVectorTemplateCommon的构造函数

SmallVectorTemplateCommon(size_t Size) : Base(getFirstEl(), Size) {}

调用该构造函数时会首先对SmallVectorBase的构造函数，此时会对BeginX进行初始化，上面的Base就代表SmallVectorBase。可以看到BeginX是调用getFirstEl()进行初始化的。在来看看getFirstEl()，该函数会通过this指针的地址加上一个偏移量来得到。这个偏移量是通过一个SmallVectorAlignmentAndSize的struct得到。

void *getFirstEl() const {
    return const_cast<void *>(reinterpret_cast<const void *>(
        reinterpret_cast<const char *>(this) +
        offsetof(SmallVectorAlignmentAndSize

再来看看SmallVectorAlignmentAndSize这个结构体，是由SmallVectorBase和FirstEl组成，正好SmallVector中SmallVectorBase占有内存后就是SmallVectorStorage中InlineElts占有的内存，因此FirstEl的偏移量也是InlineElts的偏移量。

template <class T, typename = void> struct SmallVectorAlignmentAndSize {
  alignas(SmallVectorBase

3.SmallVector迭代器

同std::Vector一样，SmallVector维护的是一个连续的线性空间普通的指针都可以作为SmallVector的迭代器满足所有的必要条件，例如operator*，operator++，operator--等。不需要额外的对这些操作符进行重载。

需要注意的是SmallVector同Vector一样，当发生扩容时其迭代器会失效。

4总结

• SmallVector只定义了一系列构造函数，具体实现在SmallVectorImpl
• SmallVectorStorage定义了存储元素的数组
• SmallVectorTemplateBase对是否为POD类型进行了偏特化
• SmallVectorTemplateCommon是不依赖于是否为POD类型的公共部分
• 元素的首地址通过getFirstEl()计算一个偏移量得到
• SmallVector是std::array与std::vector的结合体，因此具备两者共同的优点。
• SmallVector迭代器在发生扩容时会失效。

文章到这儿已经结束啦，如果想要更深入的了解可以结合这篇文章深入了解一下源码，这样收获会更大，没有涉及到的地方欢迎留言讨论。