对LLVM之类的编译器是如何实现以布局SSA形式的IR的时，算出def-use链？

1. 在创建SSA形式的LLVM IR时，SSA value之间的def-use信息是如何建立的？
   
2. 在把alloca/load/store表达的局部变量提升为SSA value时，LLVM是如何分析出def-use关系的？

• V8 TurboFan：v8/node.h at master · v8/v8 · GitHub
• Halfmoon：avmplus/hm-instrgraph.h at master · adobe/avmplus · GitHub

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);}

  Op<0>() = S1;  Op<1>() = S2;

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

int foo(int x, bool cond) {  int inc;  if (cond) {    inc = 1;  } else {    inc = -1;  }  return x + inc;}

; Function Attrs: nounwind uwtabledefine 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.elseif.then:                                          ; preds = %entry  store i32 1, i32* %inc, align 4  br label %if.endif.else:                                          ; preds = %entry  store i32 -1, i32* %inc, align 4  br label %if.endif.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}

; Function Attrs: nounwind uwtabledefine 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.elseif.then:                                          ; preds = %entry  br label %if.endif.else:                                          ; preds = %entry  br label %if.endif.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}

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.