对于LLVM之类的编译器是如何实现在构造SSA形式的IR的时候,计算出def-use链?

在做基于SSA形式的优化的时候,发现def-use链和use-def是基本的问题,我找到的资料基本上都仅仅只是采用传统的数据流方法——扩展的liveness analysis算法,cs.rice.edu/~keith/512/,而我想要知道的是如何从AST构造SSA形式的中间代码的时候,计算出指令的def-use链。 —————————————————————————————————— 麻烦各位了!!!,如果内容多,只需要给个LLVM中的文件名或者论文即可,谢谢! ————…
关注者
150
被浏览
4,292

4 个回答

题主的问题其实是两个问题。或者说我知道题主关心的其实是后者,但这问题的表述方式看起来像前者:
  1. 在创建SSA形式的LLVM IR时,SSA value之间的def-use信息是如何建立的?
  2. 在把alloca/load/store表达的局部变量提升为SSA value时,LLVM是如何分析出def-use关系的?

1. 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”。LLVM官方文档对其有很不错的介绍:LLVM Programmer's Manual: The User and owned Use classes' memory layout
请读完这块文档再继续读下文。
有趣的是,这种“Use”结构在V8 TurboFan和Adobe Flash VM的Halfmoon编译器里都有应用:

举例来说,假如我们要创建一个Add指令,BinaryOperator::CreateAdd(Value *V1, Value *V2, const Twine &Name),这条新创建的Add(BinaryOperator)指令是如何跟它的两个输入(V1、V2)建立起def-use/use-def联系的呢?请看下面的代码:
class Value {
  void addUse(Use &U) { U.addToList(&UseList); }

  // ...
};

class Use {
  Value *Val;
  Use *Next;
  PointerIntPair<Use **, 2, PrevPtrTag> Prev;

  // ...
};

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

Value *Use::operator=(Value *RHS) {
  set(RHS);
  return RHS;
}

class User : public Value {
  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];
  }
  template <int Idx> Use &Op() {
    return OpFrom<Idx>(this);
  }
  template <int Idx> const Use &Op() const {
    return OpFrom<Idx>(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);
}
从BinaryOperator的构造器开始看,会看到里面有:
  Op<0>() = S1;
  Op<1>() = S2;
的看起来很有趣的代码。追溯源头会来到Use::set(Value *V),这里就借助Use对象来把def与use的双向引用给联系起来了。

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

关键词:mem2reg pass
源码:
lib/Transforms/Utils/Mem2Reg.cpp
lib/Transforms/Utils/PromoteMemoryToRegister.cpp

这个第二部分的本质其实是:假定我们的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就是这样把生成SSA形式的任务交给LLVM处理的:Clang的前端只会把某些临时值生成为SSA value;对显式的局部变量,Clang前端都只是生成alloca/load/store形式的LLVM IR。
交给LLVM之后,经过mem2reg pass,IR才真正进入了普通的SSA形式。
LLVM Tutorial也提到了这点:7. Kaleidoscope: Extending the Language: Mutable Variables

例如说这样的函数:
int foo(int x, bool cond) {
  int inc;
  if (cond) {
    inc = 1;
  } else {
    inc = -1;
  }
  return x + inc;
}
Clang的前端生成的LLVM IR是:
; Function Attrs: nounwind uwtable
define i32 @_Z3fooib(i32 %x, i1 zeroext %cond) #0 {
entry:
  %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
  %0 = load i8, i8* %cond.addr, align 1
  %tobool = trunc i8 %0 to i1
  br i1 %tobool, label %if.then, label %if.else

if.then:                                          ; preds = %entry
  store i32 1, i32* %inc, align 4
  br label %if.end

if.else:                                          ; preds = %entry
  store i32 -1, i32* %inc, align 4
  br label %if.end

if.end:                                           ; preds = %if.else, %if.then
  %1 = load i32, i32* %x.addr, align 4
  %2 = load i32, i32* %inc, align 4
  %add = add nsw i32 %1, %2
  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了。

LLVM的mem2reg pass本质上就是识别“局部变量”的模式,并对它们构建SSA形式。
它用的算法也很常规——经典的Lengauer-Tarjan的iterated dominance frontier算法。
mem2reg的算法有同学写过简介,我懒就不重复了:cs.rice.edu/~mc29/Milin
  1. LLVM assumes that all locals are introduced in the entry basic block of a function with an alloca instruction. LLVM also assumes that all allocas appear at the start of the entry block continuously. This assumption could be easily violated by the front-end, but it is a reasonable assumption to make.
  2. For each alloca seen in step 1, LLVM checks if it is promotable based on the use of this local. It is deemed promotable iff:
    1. (a) It is not used in a volatile instruction.
    2. (b) It is loaded or stored directly, i.e, its address is not taken.
  3. For each local selected for promotion in step 2, a list of blocks which use it, and a list of block which define it are maintained by making a linear sweep over each instruction of each block.
  4. Some basic optimizations are performed:
    1. (a) Unused allocas are removed.
    2. (b) If there is only one defining block for an alloca, all loads which are dominated by the definition are replaced with the value.
    3. (c) allocas which are read and written only in a block can avoid traversing CFG, and PHI-node insertion by simply inserting each load with the value from nearest store.
  5. A dominator tree is constructed.
  6. For each candidate for promotion, points to insert PHI nodes is computed as follows:
    1. (a) A list of blocks which use it without defining it (live-in blocks or upward exposed blocks) are determined with the help of using and defining blocks created in Step 3.
    2. (b) A priority queue keyed on dominator tree level is maintained so that inserted nodes corresponding to defining blocks are handled from the bottom of the dominator tree upwards. This is done by giving each block a level based on its position in the dominator tree.
    3. (c) For each node — root, in the priority queue:
      1. i. Iterated dominance frontier of a definition is computed by walking all dominator tree children of root, inspecting their CFG edges with targets elsewhere on the dominator tree. Only targets whose level is at most root level are added to the iterated dominance frontier.
      2. ii. PHI-nodes are inserted at the beginning in each block in the iterated dominance frontier computed in the previous step. There will be predecessor number of dummy argument to the PHI function at this point.
  7. Once all PHI-nodes are prepared, a rename phase start with a worklist containing just entry block as follows:
    1. (a) A hash table of IncomingVals which is a map from a alloca to its most recent name is created. Most recent name of each alloca is an undef value to start with.
    2. (b) While (worklist != NULL)
      1. i. Remove block B from worklist and mark B as visited.
      2. ii. For each instruction in B:
        1. A. If instruction is a load instruction from location L (where L is a promotable candidate) to value V, delete load instruction, replace all uses of V with most recent value of L i.e, IncomingVals[L].
        2. B. If instruction is a store instruction to location L (where L is a promotable candidate) with value V, delete store instruction, set most recent name of L i.e, IncomingVals[L] = V.
        3. C. For each PHI-node corresponding to a alloca — L , in each successor of B, fill the corresponding PHI-node argument with most recent name for that location i.e, IncomingVals[L].
      3. iii. Add each unvisited successor of B to worklist.
嗯先就写这么多。
我就接着R大的部分粗浅的补充下,LLVM IR的def-use链,是通过Use对象来管理的,R大说的是最新的LLVM IR中def-use链的构造情况,我先补充一下早期的LLVM IR中def-use的构造方式,然后再补充下最新的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 "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;"
%start = alloca i32, align 4              ; <i32*> [#uses=2]
%end = alloca i32, align 4                ; <i32*> [#uses=2]
store i32 10, i32* %start                 ; use %start
store i32 10, i32* %end                   ; use %end
%tmp = load i32* %start                   ; use %start
%tmp1 = load i32* %end                    ; use %end
%add = add nsw i32 %tmp, %tmp1
在遍历到“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
R大已经给出了如今LLVM的def-use的构造方式,也给出了LLVM Programmer’s Manual 这个网址,这里面有两幅图示描述了User与Use之间的关系。
...---.---.---.---.-------...
  | P | P | P | P | User
'''---'---'---'---'-------'''
第一种 "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对象的前面,是固定长度的。为了实现这样的形式,就需要重载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对象存放方式如下:
.------.------.-------...
| P, 0 | P, 1 | User
'------'------'-------'''
下面分析 "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对象的头部,如下图所示:
.------.------.-------...
| S1   |  S2  | User
'------'------'-------'''
在执行 "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>()等。无聊的代码已经很多了,就不再贴了。。。