跳转到内容

定义可达性

维基百科,自由的百科全书

在编译器理论中,一个指令的定义可达性(Reaching Definition)必然是另外一个指令,而这个指令则是一个没有交错赋值指令的目标变数,举例来说:

d1 : y := 3
d2 : x := y

d2中,d1为定义可达性,而在下列的范例中:

d1 : y := 3
d2 : y := 4
d3 : x := y

d1d3不再是定义可达性,因为d2使它不再可能被到达。

作为分析用途

定义可达性也可称为数据流分析,它静态的决定在程式码当中哪些定义可以被到达,由于他相当简单,它在教课书当中通常被使用作数据分析的经典范例。数据流汇流运算(data-flow confluence operator)则是使用联集,而他的分析则是正向流动。定义可达性被使用在计算UD链以及DU链

资料流方程式,给定一个基本区块 在定义可达性:

换句话说,定义可达性的集合为的前身,在控制流程图(Control flow graph)中,包含所有在区块前的基本区块。定义可达性出来的,为所有定义可达性自己前身减掉那些被剃除掉的变数,再加上产生的新的定义。

我们定义通用的指令如下:

为所有赋值给变数定义的集合,是一个独立的标签附加在赋值的指令,那么定义可达性的值域就是这些指令标签。

延伸阅读

另见