9.1.3　数据依赖分析

9.1.3　数据依赖分析

本书中介绍的不少算法都与代码的排列顺序有关。比如wm ASB算法就是通过重排基本块中各条指令的出现顺序来嵌入水印的。而在OBFCF算法中又是通过重排指令来破坏程序中的一些信息的!当然我们这里所说的重排指令,并不是说要把所有指令都拿来乱排,我们是有选择、有目的地对指令进行重排的。比如说指令A中计算的一个变量在接下来的指令B中会被用到,那么在重排时,B就必须放在A后面。

这就是所谓的“流依赖”,它是4种数据依赖关系——流依赖(flow dependence)、反依赖(antin dependence)、输出依赖(output dependence)和控制依赖(control dependence)之一。如果在A、B两句顺序出现的语句中,A给某个变量赋值,而B使用了该变量,则称这两条语句之间存在流依赖。如果是B给变量赋值,而A使用了该变量时,则称这两条语句之间存在反依赖。如果A、B两条语句都给某个变量赋值,则称这两条语句之间存在输出依赖。而如果语句B是否会被执行是取决于语句A的,则称这两条语句之间存在控制依赖。下面给出依赖关系的概览表(表9.2)。

表9.2　依赖关系概览表

只有当两条指令之间不存在依赖关系时,我们才能放心地调整它们的顺序。

依赖图中的每个结点都代表程序中的一条语句,如果在代码中,语句A必须出现在语句B之前,则会出现一条由A到B的边。图9.19给出的是模n取幂函数的依赖图。

图9.19　模n取幂函数的依赖图

用黑色的边表示流依赖关系,浅灰色的边表示反依赖关系,深灰色的边表示输出依赖关系,虚线边表示控制依赖关系。由于S0和S1之间没有边,所以这两条语句的顺序可以改变,同样,语句S6、S7和S8之间也不存在任何依赖关系,所以这三条语句的顺序也可以任意调整。