在LLVM中输入程序流以IR的形式呈现, 之前培训过如何打印与阅读文本形式的IR, 这次简要介绍一下在内存中IR的组织形式, 以及处理/转换IR时需要注意点.
本节主要介绍IR组织中最底层的数据结构(Value), 它们是如何组织的(有向图)以及如何修改它们之间的联系.

一切皆Value

当在提及Linux有一个说法是一切皆文件, 即Linux把一切设备/IO都虚拟化为文件来看待, 便于底层管理.
非常巧合的是在LLVM中也有类似的概念: 一切皆Value. Value类是LLVM中非常重要的基类, 输入程序流中的变量/常量/表达式/符号都可以被视作一个Value.
举例而言:

[03:02:36] hansy@hansy:~/source/1.llvm/llvm (master)$ clang -emit-llvm -S --target=riscv32 -O2 2.c && cat 2.ll 
; ModuleID = '2.c'
source_filename = "2.c"
target datalayout = "e-m:e-p:32:32-i64:64-n32-S128"
target triple = "riscv32"

; Function Attrs: norecurse nounwind readnone
define dso_local i32 @test(i32 %a, i32 %b) local_unnamed_addr #0 {
entry:
  %add = add nsw i32 %b, %a
  ret i32 %add
}

attributes #0 = { norecurse nounwind readnone "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-frame-pointer-elim"="false" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-features"="+relax" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0}
!llvm.ident = !{!1}

!0 = !{i32 1, !"wchar_size", i32 4}
!1 = !{!"clang version 9.0.0 (https://github.com/llvm-mirror/clang.git 8a55120a7d72bed6c93749e0a6dbd0a2fcd873dd) (https://github.com/llvm-mirror/llvm.git ff5f64e4c8e72159f06487684037dcd3eca2cd8e)"}

上述例子中寄存器%a, %b是Value, 运算结果%add也是Value, basic block符号entry也是Value, function符号test也是Value, !0, !1这样的metadata也是Value.
让我们先来看下Value的构成, Value类(defined in include/llvm/IR/Value.h)定义见下.

class Value {
  Type *VTy;
  Use *UseList;
  const unsigned char SubclassID;

  // ......

  enum ValueTy {
#define HANDLE_VALUE(Name) Name##Val,
#include "llvm/IR/Value.def"

#define HANDLE_CONSTANT_MARKER(Marker, Constant) Marker = Constant##Val,
#include "llvm/IR/Value.def"
  };
};

Value类包含多个成员, 这里先介绍最重要的三个成员VTy, UseList以及SubclassID.

1. 一个值(Value)必然具有一个类型(Type), VTy用来记录这个Value的Type. 任何Value都具有一个类型, 哪怕它没有类型(void).
2. LLVM引入了Use类并在Value中添加一个UseList用来跟踪并记录Value的使用者. 虽然名为UseList但只是一个Use类的指针, 之后会看到LLVM是如何关联这些对象的.
3. 另外一个重要的成员是SubclassID, 这是一个const值, 用来指示这个Value的子类型. 其用于isa<>与dyn_cast<>的判断.

注意SubclassID的定义比较古怪, 对于基类类型其值定义见枚举ValueTy(该枚举由Value.def宏展开生成), 而继承类的值的定义则需见继承类中的枚举定义. 更多细节参见这里.

跟踪Value与RAUW操作

一如我们之前讨论过那样, IR中指令是顺序组织的. 然而在替换指令时我们又需要高效的更新手段, 顺序容器不满足这种需求, 所以LLVM又引入了Use类.
如果一个Value使用到了另一个Value即产生一条有向边, Use类(defined in include/llvm/IR/Use.h)被用来描述这种边.

class Use {
public:
  friend class Value;
  friend class User;

  operator Value *() const { return Val; }
  Value *get() const { return Val; }
  User *getUser() const { return Parent; };
  inline void set(Value *Val);
  inline Value *operator=(Value *RHS);
  inline const Use &operator=(const Use &RHS);
  Value *operator->() { return Val; }
  const Value *operator->() const { return Val; }
  Use *getNext() const { return Next; }
  unsigned getOperandNo() const;
  static void zap(Use *Start, const Use *Stop, bool del = false);

private:
  Value *Val = nullptr;
  Use *Next = nullptr;
  Use **Prev = nullptr;
  User *Parent = nullptr;

  // ......
};

Use类的设计是一个经典的双链表结构, 一共包含4个成员, 分别是:

1. Val - 指向被使用的Value对象.
2. Next - 下一个指向同一Value的边.
3. Prev - 上一个指向同一Value的边, 注意是双向链表的设计, 这里用的二层指针.
4. Parent - 使用该Value的User(边的源节点).

阅读代码时的注意点:

1. Use重载了->与=操作符, 其返回的都是被使用的Value本身.
2. 调用getUser()获取使用者(与第一点返回值做区分).
3. Use声明了友元以供Value与User访问其成员, 因此Value/User可以调用Use的成员函数.

Use类有几个重要的成员函数, 我们之后将会遇到.

void Use::addToList(Use **List) {
  Next = *List;
  if (Next)
    Next->Prev = &Next;
  Prev = List;
  *Prev = this;
}

void Use::removeFromList() {
  *Prev = Next;
  if (Next)
    Next->Prev = Prev;
}

void Use::set(Value *V) {
  if (Val) removeFromList();
  Val = V;
  if (V) V->addUse(*this);
}

void Value::addUse(Use &U) { U.addToList(&UseList); }

Use::addToList(Use **List)与Use::removeFromList()是基础的双向链表操作, 分别用来将本Use对象挂入/移出链表.
Use::set(Value *V)是对外暴露的接口, 用来修改本Use对象所使用的Value(修改边的目的端点).

再来看下用来描述使用者的User类, 相比于Value与Use它稍稍有些复杂. 让我们思考一下三者的关系:

1. 首先从抽象的角度User必须继承自Value, 因为从直观上来讲一个Value可以同时是一个Value的Usee且又是另一个Value的User.
2. 另一方面Use是依赖于User存在的(只有User知道它需要多少依赖以及依赖指向哪个Value), 因此User负责对Use的管理(申请与释放).
3. 由于User是一个通用的基础类, 而不同指令的操作数个数又不同, 导致Use不能作为User的成员存在(容器方式存储可以, 但是效率降低).
   让我们来看下User类(defined in include/llvm/IR/User.h)的定义.

class User : public Value {
protected:
  User(Type *ty, unsigned vty, Use *, unsigned NumOps)
      : Value(ty, vty) {
    assert(NumOps < (1u << NumUserOperandsBits) && "Too many operands");
    NumUserOperands = NumOps;
    // If we have hung off uses, then the operand list should initially be
    // null.
    assert((!HasHungOffUses || !getOperandList()) &&
           "Error in initializing hung off uses for User");
  }
};

可以看到User并没有扩展额外的成员, 那么Use存储在哪里呢? 奥妙在新建User对象的时候.

void *User::allocateFixedOperandUser(size_t Size, unsigned Us,
                                     unsigned DescBytes) {
  assert(Us < (1u << NumUserOperandsBits) && "Too many operands");

  static_assert(sizeof(DescriptorInfo) % sizeof(void *) == 0, "Required below");

  unsigned DescBytesToAllocate =
      DescBytes == 0 ? 0 : (DescBytes + sizeof(DescriptorInfo));
  assert(DescBytesToAllocate % sizeof(void *) == 0 &&
         "We need this to satisfy alignment constraints for Uses");

  uint8_t *Storage = static_cast<uint8_t *>(
      ::operator new(Size + sizeof(Use) * Us + DescBytesToAllocate));
  Use *Start = reinterpret_cast<Use *>(Storage + DescBytesToAllocate);
  Use *End = Start + Us;
  User *Obj = reinterpret_cast<User*>(End);
  Obj->NumUserOperands = Us;
  Obj->HasHungOffUses = false;
  Obj->HasDescriptor = DescBytes != 0;
  for (; Start != End; Start++)
    new (Start) Use(Obj);

  if (DescBytes != 0) {
    auto *DescInfo = reinterpret_cast<DescriptorInfo *>(Storage + DescBytes);
    DescInfo->SizeInBytes = DescBytes;
  }

  return Obj;
}

void *User::operator new(size_t Size, unsigned Us) {
  return allocateFixedOperandUser(Size, Us, 0);
}

void *User::operator new(size_t Size, unsigned Us, unsigned DescBytes) {
  return allocateFixedOperandUser(Size, Us, DescBytes);
}

void *User::operator new(size_t Size) {
  // Allocate space for a single Use*
  void *Storage = ::operator new(Size + sizeof(Use *));
  Use **HungOffOperandList = static_cast<Use **>(Storage);
  User *Obj = reinterpret_cast<User *>(HungOffOperandList + 1);
  Obj->NumUserOperands = 0;
  Obj->HasHungOffUses = true;
  Obj->HasDescriptor = false;
  *HungOffOperandList = nullptr;
  return Obj;
}

User重载了三个版本的new操作符, 我们先来看最下面的实现, 其在给定大小Size的基础上又增加了一个Use指针大小的空间进行内存申请. 然后将返回地址的起始作为Use指针并置空, 之后的地址作为User对象的地址初始化并返回. 即在每个User对象之前有一个Use指针大小的空间保存了一个默认为空的Use指针. 有点意思, huhhh ?
再来看下另外两个版本的实现均调用了void *User::allocateFixedOperandUser(size_t Size, unsigned Us, unsigned DescBytes). 有趣的是申请的内存空间是传入的Size加上Us个Use对象的空间(以及DescriptInfo的大小, 可选项, 暂时忽略). 而在初始化时又将DescriptInfo放在最前, 然后是Us个Use, 最后是User对象.
现在可以理解User是如何管理Use对象的了:

1. 第一种是独立分配, 在构造User对象时额外分配一个指针用来保存Use数组, 这种情况下HasHungOffUses为true.
   对于这种情况如需分配Use对象时可以调用void User::allocHungoffUses(unsigned N, bool IsPhi = false)与void User::growHungoffUses(unsigned N, bool IsPhi = false).
2. 另一种是co-allocated, 在构造User对象时传入边的数量并分配连续内存同时保存User与Use, 这种情况下HasHungOffUses为false.

再来看下User如何访问Use对象.

class User : public Value {
private:
  const Use *getHungOffOperands() const {
    return *(reinterpret_cast<const Use *const *>(this) - 1);
  }

  Use *&getHungOffOperands() { return *(reinterpret_cast<Use **>(this) - 1); }

  const Use *getIntrusiveOperands() const {
    return reinterpret_cast<const Use *>(this) - NumUserOperands;
  }

  Use *getIntrusiveOperands() {
    return reinterpret_cast<Use *>(this) - NumUserOperands;
  }

public:
  const Use *getOperandList() const {
    return HasHungOffUses ? getHungOffOperands() : getIntrusiveOperands();
  }
  Use *getOperandList() {
    return const_cast<Use *>(static_cast<const User *>(this)->getOperandList());
  }

  Value *getOperand(unsigned i) const {
    assert(i < NumUserOperands && "getOperand() out of range!");
    return getOperandList()[i];
  }
};

在将来我们会看到Value *User::getOperand(unsigned i)是一个非常常用的接口, 我们在编写IR变换的代码时访问IR的操作数就通过这个接口实现.
这个接口返回了一个给定下标的数组的对象, 而这个数组的地址是由Use *User::getOperandList()返回的, 后者根据HasHungOffUses标记位决定从何处返回地址.
若HasHungOffUses为true则访问User对象之前的地址, 否则直接计算偏移.

用框图来展示一下其逻辑.

回到最初的问题: 如何高效的替换/删除Value对象? 如果仅仅简单的修改IR中的operand指针是不能起到修改/替换的作用的, 严重的会导致底层处理时错误计算def-use关系导致coredump.
因此我们必须使用LLVM提供的被称为RAUW(replace all uses with)的操作(这类技巧在LLVM代码框架中随处可见), 其接口定义见Value类.

class Value {
private:
  void doRAUW(Value *New, ReplaceMetadataUses);
public:
  void replaceAllUsesWith(Value *V);
};

void Value::doRAUW(Value *New, ReplaceMetadataUses ReplaceMetaUses) {
  assert(New && "Value::replaceAllUsesWith(<null>) is invalid!");
  assert(!contains(New, this) &&
         "this->replaceAllUsesWith(expr(this)) is NOT valid!");
  assert(New->getType() == getType() &&
         "replaceAllUses of value with new value of different type!");

  // Notify all ValueHandles (if present) that this value is going away.
  if (HasValueHandle)
    ValueHandleBase::ValueIsRAUWd(this, New);
  if (ReplaceMetaUses == ReplaceMetadataUses::Yes && isUsedByMetadata())
    ValueAsMetadata::handleRAUW(this, New);

  while (!materialized_use_empty()) {
    Use &U = *UseList;
    // Must handle Constants specially, we cannot call replaceUsesOfWith on a
    // constant because they are uniqued.
    if (auto *C = dyn_cast<Constant>(U.getUser())) {
      if (!isa<GlobalValue>(C)) {
        C->handleOperandChange(this, New);
        continue;
      }
    }

    U.set(New);
  }

  if (BasicBlock *BB = dyn_cast<BasicBlock>(this))
    BB->replaceSuccessorsPhiUsesWith(cast<BasicBlock>(New));
}

void Value::replaceAllUsesWith(Value *New) {
  doRAUW(New, ReplaceMetadataUses::Yes);
}

注意到Value::replaceAllUsesWith(Value *New)是一个非常重要的接口, 以后我们会看到对IR的变换都会调用这个接口. 其仅仅调用了Value::doRAUW(Value *New, ReplaceMetadataUses ReplaceMetaUses).
后者的实现也很简单, 除去对constant与phi节点的特殊操作(constant在IR中是unique的, 即多个constant使用同一Value, phi节点操作数中incoming block不是简单通过Use来引用的, 因此两者需要特殊处理), 就是遍历Value本身的边(Use)并将其指向的目的替换为新值.

跟踪与同步

有了RAUW支持, 我们可以随心所欲的修改IR而不用担心正确性以及性能问题了. 然而编译器开发实在是太复杂了, 一不小心就踩到坑里. 举个例子:
我现在有一个特定的优化, 它会先搜索一些Value将其指针存在一个容器里然后依次处理. 然而不幸的是这些Value之间相互关联, 可能我修改一个Value以后另一个Value就不再需要处理了, 甚至可能被删除了. 然而我怎么才能知道这点呢? 简单的想法是在处理每个Value时都去检索一遍当前处理的对象指针是否在容器中, 然而这会带来巨大的性能开销.
在这种情况下LLVM设计了另一个神兵利器: ValueHandle.
// TODO 太困了明天再补充

设计思考

补充一些阅读代码时候的思考, 个人理解仅限参考.

1. Use类的设计: 没有拷贝构造函数, 私有的析构函数, 使用替换边(Use::set())而非删除重建边的方式.
   因为Use是依赖与User存在的, 一条指令定义了必然就存在固定数量的操作数, 即存在对应数量的边, 所以替换一定比删除重建更快. 同理公有的析构函数也没有意义, 因为Use一定是在User被析构时一起被析构(见void User::operator delete(void *Usr)).
2. Value类的设计: 保护的构造函数与析构函数, 析构函数非虚, use迭代器设计.
   类似Use, Value也不能离开继承类(指令/符号或其它)单独存在, 因此没有公有的必要. 虚函数带来虚表的开销, 对于Value这样底层的又常见的结构尽量节省空间. 如何将双向链表封装成迭代器访问(见use_iterator_impl).