论文部分内容阅读
摘要：已有的指针分析算法中程序的中间不能充分表示相关程序的语法结构及语义，从而导致不宜应用在程序标准化转换等方面的问题，本文提出基于控制的依赖树的流敏感及上下文的敏感过程间指针的分析算法。因此，把程序表示为控制依赖树，通过改进指向表示法来表示指针别名，并在这个基础之上来定义数据流公式。对于控制依赖树的流敏感与上下文敏感进行指针分析。通过研究与分析，这种算法的准确性比Emami指针分析算法的准确性要高，并且程序标准化的应用可以显著的提高代码多样化的消除率。
关键词：程序标准转化；指针分析；算法
中图分类号：TP311.11 文献标识码：A文章编号：1007-9599 (2011) 19-0000-01
Pointer Analysis Algorithms in Program Standardization Conversion
Wang Haitao
(China Tobacco Shandong Industrial Co.,Ltd.,Qingzhou Cigarette Factory,Qingzhou262500,China)
Abstract:The existing pointer analysis algorithms in the middle of the program procedures can not adequately express the syntax and semantics of the structure,leading to standardization of procedures should not be used in the conversion and other issues,this paper presents the dependence of the tree based on the control flow sensitive and context-sensitive interprocedural pointer analysis algorithm.Therefore,the dependency tree for the control of the program that,by improving the point notation to represent pointer aliasing,and on this basis of the definition of data flows up the formula.Dependency tree for the control flow for sensitive and context-sensitive pointer analysis.Through research and analysis,the accuracy of this algorithm than Emami pointer analysis algorithms to high accuracy,and standardization of procedures can significantly improve the application code to eliminate a variety of rates.
Keywords:Program standards conversion;Pointer analysis;Algorithm
当我们设定的程序中存在指针数据的类型时，同一内存地址可能由多个表达式代表，这时候用别名指称这些表达式。若指针的指向及别名的信息不明确，都会影响到程序数据流的分析，进一步影响其后的有关处理。指针分析的主要目的是为了确定指针变量指向的可能性。从而对数据流的分析更加准确。因此，指针分析通过编译器优化、程序理解等相关领域有着非常重要的研究意义及实用价值。已有的指针分析算法，大部分都应用在编译器中的代码优化及程序并行化之中。实际上，应用在程序标准化中的指针分析算法比较少。程序标准化是指按照一系列的标准化规则来进行程序语义等价的转换过程。程序标准化的目的是为了让语法表示不同，但同时语义等价的程序又具有相同的系统表示以消除代码的多样化。简化程序的分析，程序的标准化要求程序中间的表示不但能够充分的表示程序之间的语法结构，而且能够充分的表示程序的语义。因此，已有的指针分析算法经常把程序转换成越来越低级的表示形式。
一、影响指针分析效果的关键因素
针对各种不同的应用，我们需要权衡其指针分析的精度及时间效率。因此，设计指针分析的算法时要充分考虑以下几个方面：1）程序的中间表示要利用执行别名的分析，并且能够充分的利用指针分析的结果。2）别名表示的方式可以全面、直观地传达指针表达式和其指向的目标间的关系。3）若考虑到控制流信息及程序语句的执行顺序则要算法流敏感，否则，非流敏感，前者分析的精度将比后者高，同时时间的效率比较低。4）若按照同一函数的不同调用点指针的指向模式的不同从而产生不同的分析结果，那么算法则上下文敏感。否则，上下文不敏感，则前者的分析精度比后者高，同时时间的效率比较低。5）区分集合的各个元素比不区分的算法分析精度要高，但是时间的效率比较低。6）分别必然别名和可能别名和不区分的算法相比分析精度比较高，但是时间效率较比较低。
二、程序标准化与指针分析
程序标准化和指针分析程序的标准化的范畴主要指：拆分复合的语句、表达式的标准化、控制结构的标准化、函数调用的标准化、消除产生冗余的代码、变量的重命名、语句的重排序、指针的标准化，其中前三种标准化被称为基本标准化。在执行转换的时候不需要进行数据流和指针别名信息，后五种的标准化被称为高级标准化，需要在转换之前进行指针和数据流分析，来以确保程序的语义不发生变化。
三、程序标准化转换中的指针分析模型分析
第一，要解析源程序，为了让程序中间表示既能便于程序的标准化，又能简化指针的分析，本文采用控制依赖树表示，通过表示语法结构的，并且充分表达语义。其次，对控制依赖树开展基本标准化，由此来消除部分代码的多样化，进而简化随后的指针分析。第三，遍历控制依赖树，计算各个节点的指针别名。程序标准化应该要确保程序语义不发生变化，并且对指针的分析的准确性要求也比较高，因此，本文可采用流敏感与上下文敏感的指针分析方法来进行。第四，我们可以利用指针的别名执行必然别名替换与数据流的分析，进一步来执行高级的标准化。第五，最后生成的标准化的系统依赖图能够直接应用在程序识别领域等。
四、用控制依赖树表达程序的语义和语法结构
我们将系统依赖图的控制依赖子图表示为控制依赖树。我们进行以下的改进。第一，系统依赖图可以把表达式表示成为节点中的token串，将其划分抽象的语法树，同时连接到语句的节点上，让控制依赖树不仅可以表示控制流，还可以表示语法信息，有利于执行指针分析与程序转换。第二，系统依赖图可以把数组元素与指向数组的指针表示成不同的token。我们通过统一的抽象语法树进行表示。
五、总结
本文通过对已有的指针分析算法中程序的中间不能充分表示相关程序的语法结构及语义等问题的分析，因为它们导致不宜应用在程序标准化转换等方面的问题，进一步研究提出基于控制的依赖树的流敏感及上下文的敏感过程间指针的分析算法。把程序表示为控制依赖树，通过改进指向表示法来表示指针别名，并在这个基础之上来定义数据流公式。对此，提出一种适合用于程序标准化的一种指针的分析算法。同时，也把指针分析和程序的标准化转换的过程有机地组合在一起，这样，不但可以利用程序的标准化来简化指针分析，又可以把指针分析结果直接应用在程序标准化中，不断提高程序标准化的代码多样化的消除率。
参考文献：
[1]王甜甜,郭全萍,马培军,苏小红.用指针实现的程序的标准化及其应用[J].哈尔滨工业大学学报,2009,3
[2]王甜甜,苏小红,马培军.程序标准化转换中的指针分析算法研究[J].电子学报,2009,5
关键词：程序标准转化；指针分析；算法
中图分类号：TP311.11 文献标识码：A文章编号：1007-9599 (2011) 19-0000-01
Pointer Analysis Algorithms in Program Standardization Conversion
Wang Haitao
(China Tobacco Shandong Industrial Co.,Ltd.,Qingzhou Cigarette Factory,Qingzhou262500,China)
Abstract:The existing pointer analysis algorithms in the middle of the program procedures can not adequately express the syntax and semantics of the structure,leading to standardization of procedures should not be used in the conversion and other issues,this paper presents the dependence of the tree based on the control flow sensitive and context-sensitive interprocedural pointer analysis algorithm.Therefore,the dependency tree for the control of the program that,by improving the point notation to represent pointer aliasing,and on this basis of the definition of data flows up the formula.Dependency tree for the control flow for sensitive and context-sensitive pointer analysis.Through research and analysis,the accuracy of this algorithm than Emami pointer analysis algorithms to high accuracy,and standardization of procedures can significantly improve the application code to eliminate a variety of rates.
Keywords:Program standards conversion;Pointer analysis;Algorithm
当我们设定的程序中存在指针数据的类型时，同一内存地址可能由多个表达式代表，这时候用别名指称这些表达式。若指针的指向及别名的信息不明确，都会影响到程序数据流的分析，进一步影响其后的有关处理。指针分析的主要目的是为了确定指针变量指向的可能性。从而对数据流的分析更加准确。因此，指针分析通过编译器优化、程序理解等相关领域有着非常重要的研究意义及实用价值。已有的指针分析算法，大部分都应用在编译器中的代码优化及程序并行化之中。实际上，应用在程序标准化中的指针分析算法比较少。程序标准化是指按照一系列的标准化规则来进行程序语义等价的转换过程。程序标准化的目的是为了让语法表示不同，但同时语义等价的程序又具有相同的系统表示以消除代码的多样化。简化程序的分析，程序的标准化要求程序中间的表示不但能够充分的表示程序之间的语法结构，而且能够充分的表示程序的语义。因此，已有的指针分析算法经常把程序转换成越来越低级的表示形式。
一、影响指针分析效果的关键因素
针对各种不同的应用，我们需要权衡其指针分析的精度及时间效率。因此，设计指针分析的算法时要充分考虑以下几个方面：1）程序的中间表示要利用执行别名的分析，并且能够充分的利用指针分析的结果。2）别名表示的方式可以全面、直观地传达指针表达式和其指向的目标间的关系。3）若考虑到控制流信息及程序语句的执行顺序则要算法流敏感，否则，非流敏感，前者分析的精度将比后者高，同时时间的效率比较低。4）若按照同一函数的不同调用点指针的指向模式的不同从而产生不同的分析结果，那么算法则上下文敏感。否则，上下文不敏感，则前者的分析精度比后者高，同时时间的效率比较低。5）区分集合的各个元素比不区分的算法分析精度要高，但是时间的效率比较低。6）分别必然别名和可能别名和不区分的算法相比分析精度比较高，但是时间效率较比较低。
二、程序标准化与指针分析
程序标准化和指针分析程序的标准化的范畴主要指：拆分复合的语句、表达式的标准化、控制结构的标准化、函数调用的标准化、消除产生冗余的代码、变量的重命名、语句的重排序、指针的标准化，其中前三种标准化被称为基本标准化。在执行转换的时候不需要进行数据流和指针别名信息，后五种的标准化被称为高级标准化，需要在转换之前进行指针和数据流分析，来以确保程序的语义不发生变化。
三、程序标准化转换中的指针分析模型分析
第一，要解析源程序，为了让程序中间表示既能便于程序的标准化，又能简化指针的分析，本文采用控制依赖树表示，通过表示语法结构的，并且充分表达语义。其次，对控制依赖树开展基本标准化，由此来消除部分代码的多样化，进而简化随后的指针分析。第三，遍历控制依赖树，计算各个节点的指针别名。程序标准化应该要确保程序语义不发生变化，并且对指针的分析的准确性要求也比较高，因此，本文可采用流敏感与上下文敏感的指针分析方法来进行。第四，我们可以利用指针的别名执行必然别名替换与数据流的分析，进一步来执行高级的标准化。第五，最后生成的标准化的系统依赖图能够直接应用在程序识别领域等。
四、用控制依赖树表达程序的语义和语法结构
我们将系统依赖图的控制依赖子图表示为控制依赖树。我们进行以下的改进。第一，系统依赖图可以把表达式表示成为节点中的token串，将其划分抽象的语法树，同时连接到语句的节点上，让控制依赖树不仅可以表示控制流，还可以表示语法信息，有利于执行指针分析与程序转换。第二，系统依赖图可以把数组元素与指向数组的指针表示成不同的token。我们通过统一的抽象语法树进行表示。
五、总结
本文通过对已有的指针分析算法中程序的中间不能充分表示相关程序的语法结构及语义等问题的分析，因为它们导致不宜应用在程序标准化转换等方面的问题，进一步研究提出基于控制的依赖树的流敏感及上下文的敏感过程间指针的分析算法。把程序表示为控制依赖树，通过改进指向表示法来表示指针别名，并在这个基础之上来定义数据流公式。对此，提出一种适合用于程序标准化的一种指针的分析算法。同时，也把指针分析和程序的标准化转换的过程有机地组合在一起，这样，不但可以利用程序的标准化来简化指针分析，又可以把指针分析结果直接应用在程序标准化中，不断提高程序标准化的代码多样化的消除率。
参考文献：
[1]王甜甜,郭全萍,马培军,苏小红.用指针实现的程序的标准化及其应用[J].哈尔滨工业大学学报,2009,3
[2]王甜甜,苏小红,马培军.程序标准化转换中的指针分析算法研究[J].电子学报,2009,5