llvm Value Use User内存布局

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

我的设计：

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为例：

%add = add %a, %b  
%mul = mul %add, %b

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

// 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

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

内联User分配，以2为例

外挂Usee分配

仍以这段代码为例子：

%add = add %a, %b  
%mul = mul %add, %b

对应图：

有点复杂的图。。。

对应实现：

双链表，头插法插入

那replaceAllUsesWith实现就比较简单了：

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指令：

• switch指令

绘图：exlicdraw