ADT(advanced data type)是LLVM针对其业务逻辑自定义的高性能抽象类型, 其定义见include/llvm/ADT目录.
ADT目录下既包含了DenseMap/SmallVector这类容器封装, 也包含了APInt等大数运算支持, 还有triple这类从编译器业务抽象出来的类型.
了解ADT可以帮助我们更高效的阅读与修改编译器代码, 减轻开发工作量, 另一方面更好建立对编译器的抽象认知. 本节将要介绍的是ilist, 一个LLVM自定义链表实现.

ilist简介

ilist(intrusive list)是LLVM自定义的链表实现, 相比于std::list最主要的区别是其侵入式链表设计. 所谓侵入式(instrusive)设计是指链表节点本身作为其指向对象的一部分存在.
由于STL将容器与算法分离, 为兼容标准的迭代器设计, std::list采用单独分配内存保存链表节点的方式, 链表节点本身与其指向对象相互独立. 其优点是修改链表(insert或remove操作)时可以保持迭代器的合法性, 缺点是额外的内存开销/较差的局部性.
LLVM提供的ilist是侵入式的双向链表, 与STL链表类似它也提供常量时间的操作接口(insert/remove/splice), 使用该链表的数据类型通过继承链表基类实现统一的生命周期管理, 因而具有更好的局部性与更高效的访问效率等特点, 恰恰适用于LLVM某些场景.
关于更多的ilist使用背景介绍可以看官方文档.

从实现角度来看, 实现intrusive list与non-intrusive list的区别在于:

1. 链表节点基类只需提供操作接口, 无需设计容器.
2. 额外的链表类封装, 用于对外提供容器方式的访问.
3. 迭代器设计.

以下从这三点入手简要窥探一下ilist的实现.

链表节点定义

对于instrusive list node而言只需定义其前驱与后驱指针即可, 使用时由具体数据类型继承该基类即可, 类似以下代码:

struct A {
  A *prev;
  A *next;
};

class B : A {
  // real data structure
};

LLVM的实现也不例外, ilist支持多种链表节点(ilist_node/ilist_node_with_parent), 它们均为ilist_node_base的封装. 基类ilist_node_base(defined in include/llvm/ADT/ilist_node_base.h)定义见下.

template <bool EnableSentinelTracking> class ilist_node_base;

template <> class ilist_node_base<false> {
  ilist_node_base *Prev = nullptr;
  ilist_node_base *Next = nullptr;

public:
  void setPrev(ilist_node_base *Prev) { this->Prev = Prev; }
  void setNext(ilist_node_base *Next) { this->Next = Next; }
  ilist_node_base *getPrev() const { return Prev; }
  ilist_node_base *getNext() const { return Next; }

  bool isKnownSentinel() const { return false; }
  void initializeSentinel() {}
};

template <> class ilist_node_base<true> {
  PointerIntPair<ilist_node_base *, 1> PrevAndSentinel;
  ilist_node_base *Next = nullptr;

public:
  void setPrev(ilist_node_base *Prev) { PrevAndSentinel.setPointer(Prev); }
  void setNext(ilist_node_base *Next) { this->Next = Next; }
  ilist_node_base *getPrev() const { return PrevAndSentinel.getPointer(); }
  ilist_node_base *getNext() const { return Next; }

  bool isSentinel() const { return PrevAndSentinel.getInt(); }
  bool isKnownSentinel() const { return isSentinel(); }
  void initializeSentinel() { PrevAndSentinel.setInt(true); }
};

注意到ilist_node_base包含了前驱(Prev/PrevAndSentinel)与后驱(Next)指针, 以及实现了对应的set/get操作.
另外ilist_node_base的模板参数EnableSentinelTracking指明了是否使能边界检查, 其作用是使能ilist迭代器(ilist_iterator)对边界的检查(后文会提到).
如果该值为true则将前驱的LSB位作为标记指明当前链表节点是否为sentinel元素(即一个ilist_sentinel类的实例), 若为false则isSentinel()永远返回false(即检查一直pass).
通过打开LLVM_ENABLE_ABI_BREAKING_CHECKS选项使能EnableSentinelTracking, 这在调试链表问题时可以提供帮助.

回到ilist_node(defined in include/llvm/ADT/ilist_node.h), 其继承自ilist_node_impl, 其主要作用是提供静态类型检查与提供迭代器接口.
ilist_node提供了私有的获取前驱/后驱指针的方法(用于实现迭代器操作), 其本身通过迭代器访问成员.

template <class OptionsT> class ilist_node_impl : OptionsT::node_base_type {
  using node_base_type = typename OptionsT::node_base_type;

  friend struct ilist_detail::NodeAccess;

protected:
  using self_iterator = ilist_iterator<OptionsT, false, false>;
  using const_self_iterator = ilist_iterator<OptionsT, false, true>;
  using reverse_self_iterator = ilist_iterator<OptionsT, true, false>;
  using const_reverse_self_iterator = ilist_iterator<OptionsT, true, true>;

  ilist_node_impl() = default;

private:
  ilist_node_impl *getPrev() {
    return static_cast<ilist_node_impl *>(node_base_type::getPrev());
  }

  ilist_node_impl *getNext() {
    return static_cast<ilist_node_impl *>(node_base_type::getNext());
  }

  const ilist_node_impl *getPrev() const {
    return static_cast<ilist_node_impl *>(node_base_type::getPrev());
  }

  const ilist_node_impl *getNext() const {
    return static_cast<ilist_node_impl *>(node_base_type::getNext());
  }

  void setPrev(ilist_node_impl *N) { node_base_type::setPrev(N); }
  void setNext(ilist_node_impl *N) { node_base_type::setNext(N); }

public:
  self_iterator getIterator() { return self_iterator(*this); }
  const_self_iterator getIterator() const { return const_self_iterator(*this); }

  reverse_self_iterator getReverseIterator() {
    return reverse_self_iterator(*this);
  }

  const_reverse_self_iterator getReverseIterator() const {
    return const_reverse_self_iterator(*this);
  }

  using node_base_type::isKnownSentinel;

  bool isSentinel() const {
    return node_base_type::isSentinel();
  }
};

template <class T, class... Options>
class ilist_node : public ilist_node_impl<typename ilist_detail::compute_node_options<T, Options...>::type> {
  static_assert(ilist_detail::check_options<Options...>::value, "Unrecognized node option!");
};

注意这里ilist_node_impl的模板参数OptionsT, 其接受的参数compute_node_options(defined in include/llvm/ADT/ilist_node_options.h)作用是特化模板.
因此ilist_node_impl中的node_base_type类型被推导为ilist_node_base<enable_sentinel_tracking>, 即ilist_node_impl继承自ilist_node_base.

template <class T, bool EnableSentinelTracking, bool IsSentinelTrackingExplicit, class TagT>
struct node_options {
  typedef T value_type;
  typedef T *pointer;
  typedef T &reference;
  typedef const T *const_pointer;
  typedef const T &const_reference;

  static const bool enable_sentinel_tracking = EnableSentinelTracking;
  static const bool is_sentinel_tracking_explicit = IsSentinelTrackingExplicit;
  typedef TagT tag;
  typedef ilist_node_base<enable_sentinel_tracking> node_base_type;
  typedef ilist_base<enable_sentinel_tracking> list_base_type;
};

template <class T, class... Options> struct compute_node_options {
  typedef node_options<T, extract_sentinel_tracking<Options...>::value,
                       extract_sentinel_tracking<Options...>::is_explicit,
                       typename extract_tag<Options...>::type>
      type;
};

在LLVM中有存在许多相互依赖的数据结构: 比如函数与基本块. 它们具有以下特点:

1. 一个函数包含多个基本块, 因此函数需要能够具有迭代访问基本块的能力.
2. 因为基本块经常被修改, 需要高效的新增/删除操作, 因此基本块在物理排布上并不连续.
3. 另一方面前一个基本块可能越过后一个基本块跳转到第三个基本块(通过有向图实现), 因此额外实现基本块本身迭代的场景较少.

对于这类情况LLVM提供了另一个特殊的链表节点ilist_node_with_parent, 其接受一个ParentTy参数作为(业务逻辑上的)父类节点. 链表节点之间通过访问父类的数据结构获取其下一个节点的指针.

template <typename NodeTy, typename ParentTy, class... Options>
class ilist_node_with_parent : public ilist_node<NodeTy, Options...> {
protected:
  ilist_node_with_parent() = default;

private:
  const ParentTy *getNodeParent() const {
    return static_cast<const NodeTy *>(this)->getParent();
  }

public:
  NodeTy *getPrevNode() {
    const auto &List =
        getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
    return List.getPrevNode(*static_cast<NodeTy *>(this));
  }

  const NodeTy *getPrevNode() const {
    return const_cast<ilist_node_with_parent *>(this)->getPrevNode();
  }

  NodeTy *getNextNode() {
    const auto &List =
        getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
    return List.getNextNode(*static_cast<NodeTy *>(this));
  }

  const NodeTy *getNextNode() const {
    return const_cast<ilist_node_with_parent *>(this)->getNextNode();
  }
};

由于(业务逻辑上的)子节点通过父节点访问其相邻的节点, 在使用此链表时需要实现以下接口:

1. 子节点(NodeTy)需要实现getParent()方法获取对应的父节点对象指针.
2. 父节点(ParentTy)必须实现getSublistAccess()方法获取子节点链表.

最后再看一个特殊的链表节点ilist_sentinel, 其作为链表的边界元素存在.
注意其构造函数会先调用initializeSentinel()初始化sentinel标记, 在EnableSentinelTracking为true时会将标记位设true.

template <class OptionsT>
class ilist_sentinel : public ilist_node_impl<OptionsT> {
public:
  ilist_sentinel() {
    this->initializeSentinel();
    reset();
  }

  void reset() {
    this->setPrev(this);
    this->setNext(this);
  }

  bool empty() const { return this == this->getPrev(); }
};

链表容器封装

有了ilist_node与ilist_node_with_parent即可使用链表, 但我们更希望以标准容器的方式去访问它们.
LLVM也提供了容器封装的链表ilist/iplist(defined in include/llvm/ADT/ilist.h), 其继承自iplist_impl, 后者实现了与标准链表容器兼容的接口的封装.

template <class IntrusiveListT, class TraitsT>
class iplist_impl : public TraitsT, IntrusiveListT {
  typedef IntrusiveListT base_list_type;

public:
  iplist_impl() = default;

  iplist_impl(const iplist_impl &) = delete;
  iplist_impl &operator=(const iplist_impl &) = delete;

  iplist_impl(iplist_impl &&X)
      : TraitsT(std::move(static_cast<TraitsT &>(X))),
        IntrusiveListT(std::move(static_cast<IntrusiveListT &>(X))) {}
  iplist_impl &operator=(iplist_impl &&X) {
    *static_cast<TraitsT *>(this) = std::move(static_cast<TraitsT &>(X));
    *static_cast<IntrusiveListT *>(this) =
        std::move(static_cast<IntrusiveListT &>(X));
    return *this;
  }

  ~iplist_impl() { clear(); }

  pointer remove(iterator &IT) {
    pointer Node = &*IT++;
    this->removeNodeFromList(Node); // Notify traits that we removed a node...
    base_list_type::remove(*Node);
    return Node;
  }

  // erase - remove a node from the controlled sequence... and delete it.
  iterator erase(iterator where) {
    this->deleteNode(remove(where));
    return where;
  }

  ......
};

template <class T, class... Options>
class iplist
    : public iplist_impl<simple_ilist<T, Options...>, ilist_traits<T>> {
  using iplist_impl_type = typename iplist::iplistiplist继承自iplist_impl, 后者实现了与标准链表容器兼容的接口的封装._impl;

public:
  iplist() = default;

  iplist(const iplist &X) = delete;
  iplist &operator=(const iplist &X) = delete;

  iplist(iplist &&X) : iplist_impl_type(std::move(X)) {}
  iplist &operator=(iplist &&X) {
    *static_cast<iplist_impl_type *>(this) = std::move(X);
    return *this;
  }
};

template <class T, class... Options> using ilist = iplist<T, Options...>;

iplist_impl提供了许多标准容器的接口, 这里就不一一介绍, 注意到它接受两个模板参数TraitsT与IntrusiveListT, 前者接受一个萃取器用于控制所有权语义, 后者接受一个intrusive list作为底层实现.
先来看下萃取器ilist_traits(defined in include/llvm/ADT/ilist.h)如何决定所有权语义.
LLVM定义了两种ilist_traits(ilist_alloc_traits/ilist_noalloc_traits), 前者在删除节点时(注意到iplist_impl::erase()中调用了deleteNode())会析构对象V, 而后者是空实现.
注意iplist将TraitsT实例化为ilist_traits, 而ilist_traits继承自ilist_alloc_traits, 即iplist链表控制节点的所有权.

template <typename NodeTy> struct ilist_alloc_traits {
  static void deleteNode(NodeTy *V) { delete V; }
};

template <typename NodeTy> struct ilist_noalloc_traits {
  static void deleteNode(NodeTy *V) {}
};

template <typename NodeTy> struct ilist_callback_traits {
  void addNodeToList(NodeTy *) {}
  void removeNodeFromList(NodeTy *) {}

  template <class Iterator>
  void transferNodesFromList(ilist_callback_traits &OldList, Iterator /*first*/,
                             Iterator /*last*/) {
    (void)OldList;
  }
};

template <typename NodeTy> struct ilist_node_traits : ilist_alloc_traits<NodeTy>, ilist_callback_traits<NodeTy> {};

template <typename NodeTy> struct ilist_traits : public ilist_node_traits<NodeTy> {};

template <typename Ty> struct ilist_traits<const Ty> {};

再来看下IntrusiveListT的底层实现simple_ilist(defined in include/llvm/ADT/simple_ilist.h), 正如名字所见simple_ilist实现了一个基础的instrusive list, 它有几个特点:

1. simple_ilist继承自ilist_node.
2. simple_ilist不会分配/释放所管理的对象, 插入/删除节点也不会转移对象所有权.
3. 由于第2点, 插入节点的操作push_front()/push_back()/insert()只接受对象的引用而非指针.
4. 类似的, 删除节点的操作remove()/erase()/clear()也不会真正删除对象, 而是仅将其移出链表.

simple_list唯一拥有的成员是一个链表头节点(list_sentinel), 迭代器begin()从list_sentinel后驱开始, end()则指向list_sentinel本身.

template <typename T, class... Options>
class simple_ilist
    : ilist_detail::compute_node_options<T, Options...>::type::list_base_type,
      ilist_detail::SpecificNodeAccess<typename ilist_detail::compute_node_options<T, Options...>::type> {
  static_assert(ilist_detail::check_options<Options...>::value,
                "Unrecognized node option!");
  using OptionsT =
      typename ilist_detail::compute_node_options<T, Options...>::type;
  using list_base_type = typename OptionsT::list_base_type;
  ilist_sentinel<OptionsT> Sentinel;

public:
  simple_ilist() = default;
  ~simple_ilist() = default;

  // No copy constructors.
  simple_ilist(const simple_ilist &) = delete;
  simple_ilist &operator=(const simple_ilist &) = delete;

  // Move constructors.
  simple_ilist(simple_ilist &&X) { splice(end(), X); }
  simple_ilist &operator=(simple_ilist &&X) {
    clear();
    splice(end(), X);
    return *this;
  }

  iterator begin() { return ++iterator(Sentinel); }
  const_iterator begin() const { return ++const_iterator(Sentinel); }
  iterator end() { return iterator(Sentinel); }
  const_iterator end() const { return const_iterator(Sentinel); }
  reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); }
  const_reverse_iterator rbegin() const {
    return ++const_reverse_iterator(Sentinel);
  }
  reverse_iterator rend() { return reverse_iterator(Sentinel); }
  const_reverse_iterator rend() const {
    return const_reverse_iterator(Sentinel);
  }

  /// Check if the list is empty in constant time.
  LLVM_NODISCARD bool empty() const { return Sentinel.empty(); }

  /// Calculate the size of the list in linear time.
  LLVM_NODISCARD size_type size() const {
    return std::distance(begin(), end());
  }

  reference front() { return *begin(); }
  const_reference front() const { return *begin(); }
  reference back() { return *rbegin(); }
  const_reference back() const { return *rbegin(); }

  /// Insert a node at the front; never copies.
  void push_front(reference Node) { insert(begin(), Node); }

  /// Insert a node at the back; never copies.
  void push_back(reference Node) { insert(end(), Node); }

  /// Remove the node at the front; never deletes.
  void pop_front() { erase(begin()); }

  /// Remove the node at the back; never deletes.
  void pop_back() { erase(--end()); }

  /// Swap with another list in place using std::swap.
  void swap(simple_ilist &X) { std::swap(*this, X); }

  /// Insert a node by reference; never copies.
  iterator insert(iterator I, reference Node) {
    list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node));
    return iterator(&Node);
  }

  /// Insert a range of nodes; never copies.
  template <class Iterator>
  void insert(iterator I, Iterator First, Iterator Last) {
    for (; First != Last; ++First)
      insert(I, *First);
  }

  /// Clone another list.
  template <class Cloner, class Disposer>
  void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) {
    clearAndDispose(dispose);
    for (const_reference V : L2)
      push_back(*clone(V));
  }

  /// Remove a node by reference; never deletes.
  ///
  /// \see \a erase() for removing by iterator.
  /// \see \a removeAndDispose() if the node should be deleted.
  void remove(reference N) { list_base_type::remove(*this->getNodePtr(&N)); }

  /// Remove a node by iterator; never deletes.
  ///
  /// \see \a remove() for removing by reference.
  /// \see \a eraseAndDispose() it the node should be deleted.
  iterator erase(iterator I) {
    assert(I != end() && "Cannot remove end of list!");
    remove(*I++);
    return I;
  }

  /// Remove a range of nodes; never deletes.
  ///
  /// \see \a eraseAndDispose() if the nodes should be deleted.
  iterator erase(iterator First, iterator Last) {
    list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr());
    return Last;
  }

  /// Clear the list; never deletes.
  ///
  /// \see \a clearAndDispose() if the nodes should be deleted.
  void clear() { Sentinel.reset(); }

  ......
};

注意到以上代码中出现了两个工具类compute_node_options(上文提到过用于特化模板参数)与SpecificNodeAccess(defined in include/llvm/ADT/ilist_node.h), 后者作用是提供公有API访问ilist_node的私有方法.

struct NodeAccess {
protected:
  template <class OptionsT>
  static ilist_node_impl<OptionsT> *getNodePtr(typename OptionsT::pointer N) {
    return N;
  }
  template <class OptionsT>
  static const ilist_node_impl<OptionsT> *
  getNodePtr(typename OptionsT::const_pointer N) {
    return N;
  }
  template <class OptionsT>
  static typename OptionsT::pointer getValuePtr(ilist_node_impl<OptionsT> *N) {
    return static_cast<typename OptionsT::pointer>(N);
  }
  template <class OptionsT>
  static typename OptionsT::const_pointer
  getValuePtr(const ilist_node_impl<OptionsT> *N) {
    return static_cast<typename OptionsT::const_pointer>(N);
  }
  template <class OptionsT>
  static ilist_node_impl<OptionsT> *getPrev(ilist_node_impl<OptionsT> &N) {
    return N.getPrev();
  }
  template <class OptionsT>
  static ilist_node_impl<OptionsT> *getNext(ilist_node_impl<OptionsT> &N) {
    return N.getNext();
  }
  template <class OptionsT>
  static const ilist_node_impl<OptionsT> *
  getPrev(const ilist_node_impl<OptionsT> &N) {
    return N.getPrev();
  }
  template <class OptionsT>
  static const ilist_node_impl<OptionsT> *
  getNext(const ilist_node_impl<OptionsT> &N) {
    return N.getNext();
  }
};

template <class OptionsT> struct SpecificNodeAccess : NodeAccess {
protected:
  using pointer = typename OptionsT::pointer;
  using const_pointer = typename OptionsT::const_pointer;
  using node_type = ilist_node_impl<OptionsT>;

  static node_type *getNodePtr(pointer N) {
    return NodeAccess::getNodePtr<OptionsT>(N);
  }
  static const node_type *getNodePtr(const_pointer N) {
    return NodeAccess::getNodePtr<OptionsT>(N);
  }
  static pointer getValuePtr(node_type *N) {
    return NodeAccess::getValuePtr<OptionsT>(N);
  }
  static const_pointer getValuePtr(const node_type *N) {
    return NodeAccess::getValuePtr<OptionsT>(N);
  }
};

迭代器支持

ilist允许用户以以迭代器方式访问数据, 其迭代器ilist_iterator(defined in include/llvm/ADT/ilist_iterator.h)见下.

template <class OptionsT, bool IsReverse, bool IsConst>
class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT> {
private:
  node_pointer NodePtr = nullptr;

public:
  /// Create from an ilist_node.
  explicit ilist_iterator(node_reference N) : NodePtr(&N) {}
  explicit ilist_iterator(pointer NP) : NodePtr(Access::getNodePtr(NP)) {}
  explicit ilist_iterator(reference NR) : NodePtr(Access::getNodePtr(&NR)) {}
  ilist_iterator() = default;

  // Accessors...
  reference operator*() const {
    assert(!NodePtr->isKnownSentinel());
    return *Access::getValuePtr(NodePtr);
  }
  pointer operator->() const { return &operator*(); }

  // Comparison operators
  friend bool operator==(const ilist_iterator &LHS, const ilist_iterator &RHS) {
    return LHS.NodePtr == RHS.NodePtr;
  }
  friend bool operator!=(const ilist_iterator &LHS, const ilist_iterator &RHS) {
    return LHS.NodePtr != RHS.NodePtr;
  }

  // Increment and decrement operators...
  ilist_iterator &operator--() {
    NodePtr = IsReverse ? NodePtr->getNext() : NodePtr->getPrev();
    return *this;
  }
  ilist_iterator &operator++() {
    NodePtr = IsReverse ? NodePtr->getPrev() : NodePtr->getNext();
    return *this;
  }
  ilist_iterator operator--(int) {
    ilist_iterator tmp = *this;
    --*this;
    return tmp;
  }
  ilist_iterator operator++(int) {
    ilist_iterator tmp = *this;
    ++*this;
    return tmp;
  }

  /// Get the underlying ilist_node.
  node_pointer getNodePtr() const { return static_cast<node_pointer>(NodePtr); }
  /// Check for end.  Only valid if ilist_sentinel_tracking<true>.
  bool isEnd() const { return NodePtr ? NodePtr->isSentinel() : false; }
};

ilist_iterator接受对象/对象指针初始化成员NodePtr, 其自增/自减操作通过访问NodePtr的前驱/后驱实现. 若开启sentinel检查, 对迭代器做解引用操作时会首先检查迭代器的合法性.

小结

ilist具有更好的内存局部性, 同时访问效率更高, 因此是LLVM代码中常见的数据结构. 在使用上需要注意的是:

1. 链表节点可以选择ilist_node或ilist_node_with_parent(亦或基于ilist_node_base扩展), 具体选择哪种结构视业务逻辑决定.
2. 链表容器可以选择simple_list或ilist, 注意其主要区别是是否拥有对象的所有权, 前者在删除节点时需要手动释放对象, 后者则会自动析构.
3. 开启编译选项EnableSentinelTracking可以帮助调试链表问题.