企业网站建设价格,上传wordpress到服务器,上海建定建设工程信息网,wordpress唯美主题数据流分析之def-use链分析引言1 相关概念2 算法2.1 算法规则2.2 算法流程2.3 算法优化3 举例引言
编译过程中#xff0c;知道函数中每个指令引用的变量(或虚拟寄存器)来自于前面的哪一次赋值是很有必要的。例如llvm中对store/load转phi优化#xff0c;就需要准确知道该信息…
数据流分析之def-use链分析引言1 相关概念2 算法2.1 算法规则2.2 算法流程2.3 算法优化3 举例引言
编译过程中知道函数中每个指令引用的变量(或虚拟寄存器)来自于前面的哪一次赋值是很有必要的。例如llvm中对store/load转phi优化就需要准确知道该信息。def-use链分析(也叫定值分析)能帮助我们准确地建立这些信息。
1 相关概念 入口定值列表 指每条指令执行前的相关变量的可能值。指令n的入口定值集合表示为in[n]n为指令序号、元素为寄存器赋值指令序号的二元组 出口定值列表 指每条指令执行后的相关变量的可能值。指令n的出口定值集合表示为out[n]n为指令序号、元素为寄存器赋值指令序号的二元组 生成定值 指令操作中对寄存器的修改又称为生成定值。指令n的生成定值集合表示为gen[n]n为指令序号、元素为寄存器赋值指令序号的二元组(一般有0个或1个元素) 杀死定值 若一条指令对寄存器R生成了定值其他指令对R的生成定值称为对该条指令关于R的杀死定值。指令n的杀死定值集合表示为kill[n]n为指令序号、元素为寄存器赋值指令序号的二元组
注定值分析就是分析每条指令执行前后的入口定值列表和出口定值列表。另外对于对于llvm IR这种SSA类型指令上述集合元素可以直接是指令序号或指令指针(因为指令序号/指针与定值寄存器是等价的)。
2 算法
2.1 算法规则
整个算法其核心思想是如下三条规则
若变量属于gen[n]必属于out[n]。即用每个指令结点的gen初始化其out若变量属于out[n]必属于n的后继结点e的out[e]。即沿着有向图正向求并集传播若变量属于in[n]且不属于kill[n]必属于out[n]。即kill会阻止正向传播
2.2 算法流程
首先将函数的指令按执行顺序(包括跳转顺序)串成一个有向图每个结点对应一条指令将每个指令结点n的 gen[n] 添加到 out[n] 中添加前 out[n] 为空集合反复执行如下操作直到所有结点的 in 和 out 没有变化 将每个结点n的 out[n] 添加到其后继结点e的 in[e] 中 将每个结点n的 in[n] 中、且不在 kill[n] 中的变量添加到out[n]中
2.3 算法优化
3 举例
