• 起源：工作里用c搓了个ir库，ssa形式，但在实现方面遇到了问题（replaceAllUsesWith) 。所以看看工业级的llvm怎么处理的
  • 参考llvm18版本源码

我的设计：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
enum ClassID{
   BasicBlock,
   Instruction,
   ...
};
struct Value{
    char* name;
    ClassID id;
    Type* ty;
    Use* use_list;
};

struct Use{
   Value* user;
   Use* next;
};

struct Instruction{
    Value base;
    Value* arr[];
};

Instruction即User，只储存了Value*数组
以下面的IR为例：

1
2
%add = add %a, %b  
%mul = mul %add, %b

![[/static/images/use_graph.png]]

看起来很简单，那实现replaceAllUsesWith是怎么实现呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// replace all Use of self to other
// example: 
//   %add = add %a, %b
//   %mul = mul %add, %b
// => after replaceAllUsesWith(%add, %a)
//   %mul = mul %a, %b
void replaceAllUsesWith(Value* self, Value* other) {
	while(NULL != self.use_list){
		Use* iter = self.use_list.pop();
		Value *user = iter.val;
		for(int i =0; i < user.get_operands_num();i++){
			Value* op = user.operand[i];
			if(op == self){
				other.add_use(user);
				user.operand[i] = other;
			}
		}
	}
}

这里发现几个问题

  1. replace 需要扫描operands
  2. 需要注意Use节点内存释放
  3. 遇到%add = add %a, %a 容易出现double free

那llvm如何处理呢？

先看看llvm ir的继承体系:

https://llvm.org/doxygen/classllvm_1_1Value.html
Value是基类，User继承自Value。

然后查看源码，看看User实现方式：

内联User分配，以2为例
![[static/images/3e1c4416af8a2d18537664396f222e86b1d756d4_2_690x386.jpeg]]

外挂Usee分配
![[static/images/b60afe1c4150d5e7b1b71c3ebbf3a428305a103d_2_690x290.png]]

仍以这段代码为例子：

1
2
%add = add %a, %b  
%mul = mul %add, %b

对应图：

![[/static/images/llvm-ir-use.jpeg]]

对应实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// 双链表，头插法插入

void User::setOperand(unsigned i, Value *Val) {
  assert(i < NumUserOperands && "setOperand() out of range!");
  assert((!isa<Constant>((const Value*)this) ||
        isa<GlobalValue>((const Value*)this)) &&
        "Cannot mutate a constant with setOperand!");
  getOperandList()[i] = Val; // 调用Use::operator=(Value *RHS)
}

Value *Use::operator=(Value *RHS) {
  set(RHS);  // 调用Use::set(Value *V)
  return RHS;
}

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

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

void Value::addUse(Use &U) { U.addToList(&UseList); } // 调用Use::addToList(Use **List)

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

Use *User::getOperandList() {...}

那replaceAllUsesWith实现就比较简单了：

1
2
3
4
while (UseList) {
  Use &U = *UseList;
  U.set(New);
}

一些特殊指令

  • branch指令:

    这里还需要提到BasicBlock如何获取前驱和后缀

    • 前驱：
      变量UseList可以得到Inst，然后搜集inst.parent即可
    • 后继：
      遍历最后一条指令的Use，搜集类型是BasicBlock的变量即可
      注：这里的前驱和后缀都是CFG里面的概念
      然后我们还看到，Function中有遍历Block的方法，其实遍历的是Block的存储结构。
      即BasicBlock有两种遍历方式
    1. CFG遍历，通过前驱/后缀。包括了RPO，DFS等遍历方式。
    2. 存储结构遍历，通过ilist的next/prev

  • phi指令：
    basicblock是额外存储的，所以很容易出现basicblock未更新导致错误。新版本的llvm好像更新了。

  • switch指令。会把cond，default，case都作为Use内联进来。

绘图：exlicdraw
![[static/images/llvm_value_use_layout.excalidraw]]