llvm:Data Flow Graph

Posted on | Edited on | In

Data Flow Graph

基本概念

Data Flow Graph又叫数据流程图，表示在一个函数中的数据流动的方向。比如一个指令1定义了一个新变量%a,而另一个指令2用到了变量%a，此时就存在从指令1到指令2的边。llvm IR的表示形式是SSA，简单的来说SSA表示形式就是一个变量只能定义一次。

1
2
3
x = y + 1;
x = y + 2;
y = 3;

上面的形式就不是SSA的表示形式，因为x被定义（赋值）了两次，可以通过修改使其变成SSA的表示形式：

1
2
3
x1 = y + 1;
x2 = y + 2;
y = 3;

实验过程

在具体的实验中，我们遍历函数中的每一个指令，判断该指令是否为load，store指令，把load和store指令与其他指令区别开来是因为在IR中只有store和load指令直接与内存直接接触。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
                  case llvm::Instruction::Load:
{
	LoadInst* linst = dyn_cast<LoadInst>(curII);
	Value* loadValPtr = linst->getPointerOperand();
	edges.push_back(edge(node(loadValPtr, getValueName(loadValPtr)), node(curII, getValueName(curII))));
	break;
}
case llvm::Instruction::Store: {
	StoreInst* sinst = dyn_cast<StoreInst>(curII);
	Value* storeValPtr = sinst->getPointerOperand();
	Value* storeVal = sinst->getValueOperand();
	edges.push_back(edge(node(storeVal, getValueName(storeVal)), node(curII, getValueName(curII))));
	edges.push_back(edge(node(curII, getValueName(curII)), node(storeValPtr, getValueName(storeValPtr))));
	break;
}

对于其余的指令，遍历每一个指令的操作数，判断其是不是一个指令，如果是指令的话，就添加相应的边。

1
2
3
4
5
6
7
8
for (Instruction::op_iterator op = curII->op_begin(), opEnd = curII->op_end(); op != opEnd; ++op)
							{
								Instruction* tempIns;
								if (dyn_cast<Instruction>(*op))
								{
									edges.push_back(edge(node(op->get(), getValueName(op->get())), node(curII, getValueName(curII))));
								}
							}

具体代码请参考我的github