LLVM中的Value

This is a very important LLVM class. It is the base class of all values
computed by a program that may be used as operands to other values. Value is
the super class of other important classes such as Instruction and Function.
All Values have a Type. Type is not a subclass of Value. Some values can
have a name and they belong to some Module. Setting the name on the Value
automatically updates the module’s symbol table.Every value has a “use list” that keeps
track of which other Values are using this Value.

LLVM中的User

This class defines the interface that one who uses a Value must implement.
Each instance of the Value class keeps track of what User's have handles to it.

• Instructions are the largest class of Users.
• Constants may be users of other constants (think arrays and stuff)

LLVM中的Use

A Use represents the edge between a Value definition and its users.

This is notionally a two-dimensional linked list. It supports traversing all of the uses for a particular value definition. It also supports jumping directly to the used value when we arrive from the User's operands, and jumping directly to the User when we arrive from the Value's uses.

The pointer to the used Value is explicit, and the pointer to the User is implicit. The implicit pointer is found via a waymarking algorithm described in the programmer’s manual. This is essentially the single most memory intensive object in LLVM because of the number of uses in the system. At the same time, the constant time operations it allows are essential to many optimizations having reasonable time complexity.

The Use class represents the operand of an instruction or some other User instance
which refers to a Value. The Useclass keeps the “use list” of the referenced value up
to date.
///
Pointer tagging is used to efficiently find the User corresponding to a Use
without having to store a User pointer in every Use. A User is preceded in
memory by all the Uses corresponding to its operands, and the low bits of
one of the fields (Prev) of the Use class are used to encode offsets to be
able to find that User given a pointer to any Use.

在穿件SSA形式的LLVM IR时，SSA value之间的def-use信息是如何建立的？

假设现在的IR已经是SSA形式，则只需要建立SSA value之间的def-use/use-def关系即可。

LLVM IR的SSA value的def-use和use-def信息其实是用一套双向引用来维护的。即只要A use了B，A与B之间的use-def和def-use关系就同时建立好了。这个维护双向引用的数据结构叫做“Use”。

User与拥有的Use类的memory layout

User类为其他Value实例提供了表示User的ownership的功能。使用Use这个辅助类进行record，并有利于addition和removal（时间复杂度为O(1)）。

User与Use objects之间的关系

User的子类可以通过选择合并（incorporate）其Use对象或者通过指针引用它们。

现在对于User（子）类有两种不同的layouts：

1. Use对象位于User对象的内部（相应于fixed offset），并且有固定数量的对象。
2. Use对象由User对象中指向数组的指针进行引用，并且可能有可变数量的对象。

对于LLVM 2.4，每个layout仍然拥有一个指向Uses数组起始位置的指针。虽然layout 1）不是强制性的，但为了简便期间，可以忍受这种redundancy。User对象还存储其所拥有的Use对象的数量。

特殊形式的allocation operators（operator new）强制执行以下的内存布局：

• layout 1）通过Use[]数组前置User对象来进行modeling（即将User放置在Use[]数组的起始位置）
  • 
• layout 2）通过指向Use[]数组来进行modeling
  • 

【注】：上图中的P代表Use**，存储在Use对象的成员Use::Prev之中。

The waymarking algorithm（标记算法）

由于Use对象被剥夺了指向User对象的direct(back) pointer，因此必须有一种快速而准确的方法去recover它。

Use::Prev的2个LSBits（least significant bits，最低有效位）中的bit-encoding允许查找User对象的起始位置：

• 00 — binary digit 0
• 01 — binary digit 1
• 10 — stop and calculate (s)
• 11 — full stop (S)

给定一个Use*，所要做的就是walk till get a stop。此外，我们要么立即有一个User，要么必须walk to the next stop，然后pick up数字并计算offset。

【注】：在stops之间只需要存储大量的bits，因此当一个User与1000个Use对象关联时，最坏的情况也只需要进行20次memory accesses。

LLVM IR最新形式的def-use链的构造

举例言之，假设需要创建一个Add指令：BinaryOperator::CreateAdd(Value* V1, Value* V2, const Twine& Name)，这条新创建的Add(BinaryOperator)指令是跟它的两个输入(V1, V2)建立起def-use/use-def联系的方式如下所示：

class Vaule {
    void addUse(Use& u) { u.addToList(&UseList); }
    //...
};

class Use {
    Value* val;
    Use* next;
    PointerIntPair<Use**, 2, PrePtrTag> prev;

    //...
};

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


Value* Use::operator=(Value* rhs) {
    ser(rhs);
    return rhs;
}

class User : public Value {
    template<int index, typename U>
    static Use& OpFrom(const U* that) {
        return index < 0 
            ? OperandTraits<U>::op_end(const_cast<U*>(that))[index]
            : OperandTraits<U>::op_begin(const_cast<U*>(that))[index];
    }

    template<int index>
    Use& Op() {
        return OpFrom<index>(this);
    }

    template<int index>
    Use& Op() const {
        return OpFrom<index>(this);
    }

    //...
};

class Instruction : public User, 
                             public ilist_node_with_parent<Instruction, BasicBlock> {
    //...
};

class BinaryOperator : public Instruction {
/// Construct a binary instruction, given the opcode and the two
  /// operands.  Optionally (if InstBefore is specified) insert the instruction
  /// into a BasicBlock right before the specified instruction.  The specified
  /// Instruction is allowed to be a dereferenced end iterator.
  ///
    static BinaryOperator *Create(BinaryOps Op, Value *S1, Value *S2,
                                const Twine &Name = Twine(),
                                Instruction *InsertBefore = nullptr);

  // ...
};

BinaryOperator::BinaryOperator(BinaryOps iType, Value *S1, Value *S2,
                               Type *Ty, const Twine &Name,
                               Instruction *InsertBefore)
  : Instruction(Ty, iType,
                OperandTraits<BinaryOperator>::op_begin(this),
                OperandTraits<BinaryOperator>::operands(this),
                InsertBefore) {
  Op<0>() = S1;
  Op<1>() = S2;
  init(iType);
  setName(Name);
}

BinaryOperator *BinaryOperator::Create(BinaryOps Op, Value *S1, Value *S2,
                                       const Twine &Name,
                                       Instruction *InsertBefore) {
  assert(S1->getType() == S2->getType() &&
         "Cannot create binary operator with two operands of differing type!");
  return new BinaryOperator(Op, S1, S2, S1->getType(), Name, InsertBefore);
}

早期LLVM IR中的def-use的构造

1. LLVM 1.3中def-use的构造

以BinaryOperator为例，下面是LLVM 1.3中class Value的源码：

class Value;
class User;
class Use {
  Value *Val;
  User *U;
  Use *Prev, *Next;
public:
  Value *get() const { return Val; }
  User *getUser() const { return U; }
};
// 每次创建一个新的Use对象时，就会将Use对象挂载到Value的Uses链表上
// 由于每次Use对象的创建都是在User端进行的，所以User端创建Use对象时，就会将该对象挂载到
// Value的User链表上。
Use::Use(Value *v, User *user) : Val(v), U(user) {
  if (Val) Val->addUse(*this);
}

~Use::~Use() {
  if (Val) Val->killUse(*this);
}

从上述代码中可以看出，Use对象一头连接着 User(所有Instruction都继承自User)，一头连接着Value，然后这些Use对象以链表的形式组织起来。每次创建一个新的Use对象时，就会调用构造函数将当前的Use对象挂在到Val的Uses链表上。如图所示：

指令%add = add nsw i32 %tmp, 10用到了值 %tmp，所以两者可以使用Use对象连接起来。下面是Use对象在User和Value中的存在形式。

struct Value {
private:
  PATypeHolder Ty;
  // 每个Value都有可能被其他User用到，使用iplist来组织Use Object
  iplist<Use> Uses;
  std::string Name;
public:
  // addUse/killUse - These two methods should only used by the Use class.
  void addUse(Use &U) { Uses.push_back(&U); }
  void killUse(Use &U) { Uses.remove(&U); }
  User *use_back() { return Uses.back().getUser(); }
  // ...
};

struct User : public Value {
  // 相对应的，User使用vector来组织Use Object
  std::vector<Use> Operands;
public:
  typedef std::vector<Use>::iterator op_iterator;
  unsigned getNumOperands() const { return Operands.size(); }
  void op_reserve(unsigned NumElements) { Operands.reserve(NumElements); }
  op_iterator op_begin() { return Operands.begin(); }
  // ...
};

class Instruction : public User {
  BasicBlock *Parent;
  Instruction *Prev, *Next;
  // ...
};

class BinaryOperator : public Instruction {
protected:
  void init(BinaryOps iTyps, Value *S1, Value* S2);

  BinaryOperator(BinaryOperator(BinaryOps iType, Value *S1, Value *S2, 
             const Type *Ty, const std::string &Name, Instruction *InsertBefore)
    : Instruction(Ty, iType, Name, InsertBefore) {
    init(iType, S1, S2);
  }
  BinaryOperator(BinaryOps iType, Value *S1, Value *S2, const Type *Ty,
                 const std::string &Name, BasicBlock *InsertAtEnd)
    : Instruction(Ty, iType, Name, InsertAtEnd) {
    init(iType, S1, S2);
  }
};

//===-----------------------------------------------------------------===//
//                        BinaryOperator class
//===-----------------------------------------------------------------===//
void BinaryOperator::int(BinaryOps iType, Value *S1, Value *S2)
{
  Operands.reserve(2);
  Operands.push_back(Use(S1, this));
  Operands.push_back(Use(S2, this));
  // ...
}

下图是LLVM 1.3中BinaryOperator对象的内存布局：

BinaryOperator既有可能被别的User用到，也会用到别的Value。BinaryOperator通过使用 Uses链表来维护有可能会被哪些User用到，通过vector<Use> Operands来维护用到的Value值。

需要注意是，BinaryOperator会被哪些User用到是未知不确定的，所以用节点数量灵活的链表来组织比较合适。相对应的，BianaryOperator需要用到的Value对象数量是确定的，所以使用可以手动设定size值的vector实现。注意这一点在代码中也有体现，例如：BinaryOperator中的init函数中调用了Operands.reserve(2)来设置Operands的capacity为2。

关于如何在IR build时建立起这种def-use关系，是在BinaryOperator初始化函数中实现的。通过以下方式进行实现：

Operands.push_back(Use(S1, this));
Operands.push_back(Use(S1, this));

在创建一个新的BinaryOperator指令的时候，Create() -> BinaryOperator() -> init()，在init()函数中构造一个新的Use对象来维护def-use关系。前面曾经提到过，每次创建一个新的Use对象时，就通过Use的构造函数将Use对象挂载到Value的Uses链表上。

如下示例代码：

int add()
{
  int start = 10;
  int end = 10;
  return start + end;
}

%start会被用到两次，一次是赋值int start = 10;，一次是加法操作return start + end;。产生的LLVM IR为：

  %start = alloca i32, align 4            ; <i32*>[#uses=2]
  %end = alloca i32, align 4            ; <i32*>[#uses=2]
  store i32 10, i32* %start, align 4    ; use %start
  store i32 10, i32* %end, align 4        ; use %end
  %1 = load i32, i32* %start, align 4    ; use %start
  %2 = load i32, i32* %end, align 4        ; use %end
  %add = add nsw i32 %1, %2                
  ret i32 %add

在遍历到int start = 10;时，首先会创建一个alloca指令，然后判断是否有init expression。如果有init expression，则EmitExpr(InitE)得到一个Value，最后创建一个Store指令，将Value值存储到alloca指令指定的位置。在创建store指令的时候，会创建一个新的Use对象（在创建的同时，将该Use对象挂载到Alloca指令的Uses链表中），然后将该Use对象push到自己的Operands vector中。如图所示：

Use对象中的Prev、Next是以Val为主线来索引的。例如我们从 %start = alloca i32, allign 4的Uses数据成员，就可以索引到所有的使用%start = alloca i32, align 4。而Operands直接遍历vector就可获得use的Value。

LLVM 1.3中的def-use很简单，但是现在的LLVM 3.7的实现已经很复杂了，主要区别在于Use对象是否包括User *U数据成员以及在User中的放置方式。

2. LLVM 3.6中def-use的构造

第一种：The Use object(s) are inside (resp. at fixed offset) of the User object and there are a fixed number of them.

也就是说，User中的Operands不像LLVM 1.3中那样，将Operands作为数据成员放在User对象中，而是直接放在User对象的前面，是固定长度的（fixed）。为了实现这样的形式，就需要重载new运算符，来手动修改内存分配的方式。

class User : public Value {
protected:
  Use *OperandList;
  // 以User首地址为基准，来获取下标Idx的操作数
  template <int Idx, typename U> static Use &OpFrom(const U *that) {
    return Idx < 0 ? OperandTraits<U>::op_end(const_cast<U*>(that))[Idx] :
                     OperandTraits<U>::op_begin(const_cast<U*>(that))[Idx];
  }
  // Op<>()是Instruction获取Operand的通用接口
  template <int Idx> Use &Op(){
    return OpFrom<Idx>(this);
  }
}
void *User::operator new(size_t s, unsigned Us) {
  // 除了分配User大小的内存空间以外，还分配了固定个数Use大小的内存空间
  void *Storage = ::operator new(s + sizeof(Use) * Us);
  // Operands 头部
  Use *Start = static_cast<Use*>(Storage);
  // Operands 尾部
  Use *End = Start + Us;
  // Operands 尾部作为User首地址（this）
  User *Obj = reinterpret_cast<User*>(End);
  Obj->OperandList = Start;
  Obj->NumOperands = Us;
  Use::initTags(Start, End);
  return Obj;
}

在创建一个新的User对象的时候，会调用重载的new()函数，来分配内存空间。以BinaryOperator为例：

class BinaryOperator : public Instruction {
// ...
public:
  void *operator new(size_t s) {
    return User::operator new(s, 2);
  }
};

BinaryOperator::BinaryOperator(BinaryOps iType, Value *S1, Value *S2, Type *Ty,
        const Twine &Name, Instruction *InsertBefore)
    : Instruction (Ty, iType, OperandTraits<BinaryOperator>::op_begin(this),
                   OperandTraits<BinaryOperator>::operands(this), InsertBefore) {
  Op<0>() = S1;
  Op<1>() = S2;
  // ...
}

BinaryOperator中的operator new()调用User::new(s, 2)，分配内存时，分配BinaryOperator对象的大小加上2个Use对象大小的内存。后面在BinaryOperator的构造函数中，使用了Op<0>() = S1;以及Op<1>() = S2;来将Value存放到Operands中。

BinaryOperator中Use对象存放方式如下：

下面分析Op<0>以及Op<1>，先给出OperandTraits的定义：

template <typename SubClass, unsigned ARITY>
struct FixedNumOperandTraits {
  //上面的User::OpFrom()就是通过op_begin()获取Operands的首地址，然后通过
  //下标运算符[Idx]，来获取操作数，而固定长度Operands的首地址就是 SubClass首地址
  //减去 ARITY 个Use对象长度的地址（例如BinaryOperator中ARITY就是2）。
  static Use *op_begin(SubClass* U) {
    return reinterpret_cast<Use*>(U) - ARITY;
  }

  static Use *op_end(SubClass* U) {
    return reinterpret_cast<Use*>(U);
  }
}

template<>
struct OperandTraits<BinaryOperator> :
  public FixedNumOperandTraits<BinaryOperator, 2> {
};

可以看到OperandTraits<BinaryOperator>继承的是FixedNumOperandTraits，就是第一种固定长度的形式，Operand begin就是BinaryOperator首地址减去2个Use对象大小的位置。

在创建BinaryOperator时，会首先调用new()分配一块内存空间，然后调用BinaryOperator构造函数。在函数中通过Op<0>() = S1;以及Op<1> = S2;来将Value放置在BinaryOperator对象的头部。如下图所示：

在执行Op<0> = S1时，会调用Use::operator=()函数：

class Use {  
  Value *operator=(Value *RHS) {
    set(RHS);
    return RHS;
  }
  // 类似于LLVM1.3，set()函数也会把该Use对象挂载到Value的Uses链表上
  set(Value *V)
  {
    if (Val) removeFromList();
    Val = V;
    if (V) V->addUse(*this);
  }
  private:
  Value *Val;
  Use *Next;
  PointerIntPair<Use **, 2, PrevPtrTag> Prev;
};

也就是每次初始化一个新的Use对象时（也就是调用operator=()时），都会将该Use对象挂载在Value的链表上。同样，Use中的Next和Prev是以Value为主线来进行连接的，也就是说如果两个Use对象使用了同一个Value值，那么这两个Use对象肯定都在同一条链表上。如下图所示：

Use对象放在User对象的头部，Value可以通过UseList来索引所有的Use对象，也可以通过Use对象来索引到User对象。由于Use对象没有存放指向User的数据成员，不能直接获得，但是由于Use对象存放在User对象的头部，因此还是可以获取到User地址的。

关于第二种方式，就是变长Operands方式，这种方式通过在调用User::new()时，传递不同的参数，来分配出不同的内存，内存分配函数和第一种方式相同，Use对象也是分配在User对象的头部。只是在通过Op<Idx>()来获取Use对象的时候是通过Use Array[]的尾部来获取的，例如：Op<-1>()或者Op<-3>()等。

alloca/load/store形式的局部变量是如何进入SSA形式的？

其实主要是依靠mem2reg pass来完成的，它的本质是：假定我们的IR还不是SSA形式的，如何将它转换为SSA形式的IR。这包括计算Phi节点的安插位置（PHi insertion），以及计算变量版本和变量重命名（variable renaming）。

LLVM IR虽然是SSA形式的，但如果所有生成LLVM IR的前端都要自己计算好如何生成SSA形式，对前端来说也是件麻烦事。所以LLVM IR借助memory不是SSA value的特点开了个后门来妥协：前端在生成LLVM IR时，可以选择不生成真正的SSA形式，而是把局部变量生成为alloca/load/store形式：

• 用alloca来“声明”变量，得到一个指向该变量的指针
• 用store来把值存进变量里
• 用load来把值读出为SSA value

这样，对局部变量的读写就跟对普通内存的读写一样，不需要是SSA形式的。然后，LLVM在mem2reg pass中，会识别出这种模式的alloca，并把它提升为SSA value（并消除掉store与load，改为普通的SSA层面的def-use/use-def关系，并且在合适的位置安插Phi和变量重命名）。

Clang（LLVM的前端）生成的LLVM IR是：

; Function Attrs: nounwind
define i32 @_Z3fooib(i32 %x, i1 zeroext %cond) #0 {
  %x.addr = alloca i32, align 4
  %cond.addr = alloca i8, align 1
  %inc = alloca i32, align 4
  store i32 %x, i32* %x.addr, align 4
  %frombool = zext i1 %cond to i8
  store i8 %frombool, i8* %cond.addr, align 1
  %1 = load i8, i8* %cond.addr, align 1
  %tobool = trunc i8 %1 to i1
  br i1 %tobool, label %2, label %3

; <label>:2:                                      ; preds = %0
  store i32 1, i32* %inc, align 4
  br label %4

; <label>:3:                                      ; preds = %0
  store i32 -1, i32* %inc, align 4
  br label %4

; <label>:4:                                      ; preds = %3, %2
  %5 = load i32, i32* %x.addr, align 4
  %6 = load i32, i32* %inc, align 4
  %add = add nsw i32 %5, %6
  ret i32 %add
}

可以看到局部变量都在函数的最开头（entry block）有对应的alloca来“声明”它们——申请栈上空间。后面赋值的地方用store、取值的地方用load指令，就跟操作普通内存一样。

而经过mem2reg之后它才真正进入了SSA形式：

; Function Attrs: nounwind uwtable
define i32 @_Z3fooib(i32 %x, i1 zeroext %cond) #0 {
entry:
  %frombool = zext i1 %cond to i8
  %tobool = trunc i8 %frombool to i1
  br i1 %tobool, label %if.then, label %if.else

if.then:                                          ; preds = %entry
  br label %if.end

if.else:                                          ; preds = %entry
  br label %if.end

if.end:                                           ; preds = %if.else, %if.then
  %inc.0 = phi i32 [ 1, %if.then ], [ -1, %if.else ]
  %add = add nsw i32 %x, %inc.0
  ret i32 %add
}

可以看到进入SSA形式后的LLVM IR里，那些局部变量就变成了普通的SSA value，而不再需要alloca/load/store了。

为什么需要visitor pattern

在静态分析阶段，需要将源程序表示为一个AST，编译器需要在AST的基础上进行操作，从而完成静态语义分析。整个过程需要定义许多操作来进行类型检查、代码优化、流程分析以及检查变量是否在使用前被赋值等等。

对于上述的需求，要求对不同的node进行不同的处理。常规的处理方法是：不同的node封装不同的操作。但这样做的缺点很明显：会导致节点的类型过多， 将操作分散在各个节点类中会导致整个系统难以理解、维护和修改。增加新的操作要修改和重新编译所有的类。

改进：节点类独立于作用于其上的操作。

1. 将相关操作封装在一个独立的对象（Visitor）中，并在遍历抽象语法树时将此对象传递给当前访问的元素。
2. 当一个节点接受一个访问者时，该元素向访问者发送一个包含自身类信息的请求。该请求同时也将该元素本身作为一个参数。
3. 访问者将对该元素执行该操作。