流敏感的跨过程指针别名分析

对指针别名及其表示方式进行了阐述。描述了跨过程指针别名分析的框架,通过在分析时创建PCG(程序调用图)来处理函数指针。研究了基于此框架的一个流敏感的跨过程指针别名分析算法,算法是跨过程阶段和过程内阶段交叉进行的。最后对算法进行了实例分析和验证。     

流敏感按需指针别名分析算法

为了提高交互环境下指针别名查询的响应效率,近期研究提出通过只分析与目标相关指针的按需分析策略来降低浪费在与目标无关的指针分析的额外开销。典型的代表是基于上下文无关文法的按需别名分析算法。但是,该算法的精度只局限于控制流不敏感。控制流不敏感的别名关系将约束上层分析的精度。针对该不足,提出了具有流敏感精度的按需别名分析算法。首先采用不完全静态单赋值语句形式来区分指针变量赋值实例,然后通过层次线性化编码方法来表达控制流图中的流敏感信息以构建赋值流图,最后将别名关系查询问题转换为在赋值流图上搜索目标结点间在控制流可达条件下赋值路径的可达性问题,进而实现流敏感的按需别名分析。实验表明,与流不敏感的按需别名分析相比,该方法可以在保证查询效率的前提下,有效提高按需别名分析的精度。     

需求驱动的流敏感别名检查

别名分析的精度影响着很多其他编译优化的效果。在对展开后的循环体做指令调度的时候,不精确的别名分析结果会导致冗余数据依赖的产生,从而限制了调度。流敏感的别名分析因为代价过高而扩展性不好。在流不敏感别名信息的基础上,提出了一种需求驱动的流敏感别名检查方法,能够以流敏感的方式判断两个表达式在某程序点上是否为别名。该方法假设两个表达式之间具有别名关系,从而获取初始的数据流事实。用数据流分析技术计算逆向程序点上的数据流事实。如果在所有逆向路径上的数据流事实中都产生了矛盾,则认为别名关系不成立。实验结果表明,该方法能较好地提高别名分析的精度。     

基于静态分析技术的源代码安全检测模型*

介绍了当前主流的静态代码分析技术,在分析讨论其优缺点的基础上提出了一种新的静态代码检测模型。该模型结合了当前成熟的静态分析技术,并借鉴了编译器中数据流和控制流分析的思想,获取上下文关联的数据信息,从而更加准确地分析代码中存在的安全问题。     

基于流分析的可执行程序结构化表示工具

直接面向可执行程序进行安全漏洞分析时,首先需要得到二进制代码的中间语言表示。探讨了流分析技术在汇编代码理解中的应用,并在Linux平台上实现了一个轻量级汇编代码结构化表示工具BESTAR。该系统利用控制流和数据流分析技术识别通用控制结构,分析程序执行流,重构表达式和函数,发现数据依赖关系,将汇编代码转换成一个结构化、易理解的中间语言程序,为进一步进行安全分析打下了基础。     

指针数组的过程内别名分析

指针别名分析在C语言的并行优化中占有重要的地位,但已有的指针别名分析只能处理指针标量的情况.文章在介绍已有指针别名信息表示法的不足的基础上,提出了一种能够表示指针数组别名信息的表示方法,它可以更加准确地表示指针别名信息.在此表示法的基础上,提出了指针数组的过程内别名分析算法.此算法完全包含了指针标量的别名分析,对现有的指针别名分析算法所不能解决的一些问题能进行有效地处理.     

过程间分析中别名变量对的检测与处理

在程序的过程间分析中,为保证程序语义上的正确,需要对列名变量对进行检测和处理。在本文中,我们详细地讨论了别名变量的引入及其传播方式,同时给出了一个有效的检测与处理算法。     

面向Java的实用别名分析技术

别名分析对程序分析起着十分重要的作用,不进行别名分析或分析 算法选择不当,可能会影响分析结果的可信度,甚至会导致分析析完全不正确,因此给出了一种适用于Ｊａｖａ程序的别名分析技术,并给出了分析算法的形式化描述。     

带有异常结构程序的数据流分析

以数据流分析为基础的程序理解是软件工程重要研究领域之一.现在大多数的程序设计语言提供了异常处理机制,但程序中的异常结构会影响数据流分析.如果不考虑这种影响,把得到的数据流分析信息用于程序理解中,会产生严重的后果.文中以Java语言程序为例,提出了一种数据流分析方法,该方法充分考虑了异常结构对数据流分析的影响,从而保证数据流分析信息的正确性与准确性.     

函数库中过程间数据流预分析

过程间数据流分析在软件优化,软件维护,软件测试中均有大量的应用。在编写使用可重用组件的软件时,对整个程序进行数据流分析的方法效率低下甚至由于没有库的源代码而不能直接分析。本文是在已有的组件库上构建新组件时进行数据流分析,通过计算新建库的概要信息,并使用这些概要信息分析新的组件,这样使用库中预先计算的概要函数能够在较小的分析成本下构建可扩展的大的库组件。     

Alias verification for Fortran code optimization

Alias analysis for Fortran is less complicated than for programming languages with pointers but many real Fortran programs violate the standard: a formal parameter or a common variable that is aliased with another formal parameter is modified. Compilers, assuming standard-conforming programs, consider that an assignment to one variable will not change the value of any other variable, allowing optimizations involving the aliased variables. Higher performance results but anything may happen: the program may appear to run normally, or may produce incorrect answers, or may behave unpredictably. The results may depend on the compiler and the optimization level.To guarantee the standard conformance of programs and to maintain the referential transparency in order to make program analyses exact and program optimizations safe, precise alias information retrieval at a reasonable cost, especially the determination of overlaps between arrays are studied in this paper. Static analyses and code instrumentation are used to find all violations of the prohibitions against aliasing in Fortran code. Alias violation tests are inserted only at places where it cannot be proved statically that they are useless in order to reduce the number of dynamic checks at run-time. A specific memory location naming technique is used to compact representation and enhance the precision of alias analysis. Modifications on the dependence graph created by aliasing are also studied to show the impact of aliases on some program optimizing transformations. Experimental results on SPEC95 benchmark are presented and some related issues are also discussed.     

上下文敏感的过程间指针分析

提出了一种新的指针指向信息的过程间传播方法 ,对过程间指针分析所必须解决的若干重要问题给出了详尽的算法 ,从而形成了一种实用的上下文敏感的过程间指针分析框架 .该方法已在 C程序分析工具 Agassiz系统中实现 ,实验数据说明这些方法是行之有效的 .     

Interprocedural optimization: Experimental results

The problem of tracking data flow across procedure boundaries has a long history of theoretical study by people who believed that such information would be useful for code optimization. Building upon previous work, an algorithm for interprocedural data flow analysis has been implemented. The algorithm produces three flow-insensitive summary sets: MOD, USE and ALIASES. The utility of the resulting information was investigated using an optimizing Pascal compiler. Over a sampling of 27 bench-marks, new optimizations performed as a result of interprocedural summary information contributed almost nothing to program execution speed. Finally, related optimization techniques of possibly greater potential are discussed.     

C语言的别名分析方法研究

别名分析对于数据流分析、程序优化和分析工具的实现非常重要.文章提出了一种需求驱动,流非敏感的分析算法来解决指针别名问题.通过构造程序表达式图(PEG)把指针别名问题转化成判断两个指针节点是否是联通的问题,它不同于传统的别名分析方法,它不需要构造别名集合和对其求交集,所以提高了分析指针别名的效率.     

Transformational Derivation of an Improved Alias Analysis Algorithm

In this paper we use a program transformational approach to obtain an asymptotically improved may-alias analysis algorithm. We derive an O(N³) time algorithm for computing an intra-procedural flow sensitive may-alias analysis, where N denotes the number of edges in the program control flow graph (CFG). Our algorithm improves the previous O(N⁵) time algorithm by Hind et al. [19]. Our time complexity improvement comes without any deterioration in space complexity. We also show that for a large subclass of programs in which the in-degree and out-degree of all CFG nodes is bounded by a constant, our algorithm is linear in the sum of the number of edges in the CFG of the program and the size of the output, i.e., the size of the computed alias information, and is therefore asymptotically optimal. Our transformational algorithm derivation technique also leads to a simplified yet precise analysis of time complexity.The work in this paper was done when the author was a graduate student at New York University. This paper was originally submitted when the author was a Research Staff Member at the IBM T.J. Watson Research Center.     

Type systems equivalent to data-flow analyses for imperative languages

We show that a large class of data-flow analyses for imperative languages are describable as type systems in the following technical sense: possible results of an analysis can be described in a language of types so that a program checks with a type if and only if this type is a supertype of the result of applying the analysis. Type-checking is easy with the help of a certificate that records the “eureka”-bits of a typing derivation. Certificate-assisted type-checking amounts to a form of lightweight analysis à la Rose. For secure information flow, we obtain a type system that is considerably more precise than that of Volpano et al., but not more sophisticated. Importantly, our type systems are compositional.     

一种面向向量化的动态指针别名分析框架

指针别名分析是数据流分析中的关键性技术,其分析结果是编译优化和程序变换的基础.在向量化方法和动态指针别名分析相关研究的基础上,设计了一种面向向量化的动态指针别名分析框架.该框架通过动态插桩和试运行提取指针别名信息,并反馈到向量化阶段指导向量化代码生成.从提取候选别名分析集、插桩及试运行和反馈优化3个方面对整体框架进行分析和研究.该框架基于Open64实现,并以通用测试集GCC-VECT和典型应用进行了实验评估,结果表明,该框架相比静态指针别名分析具有更精确的别名分析结果,该结果能够有效改进向量化程序的加速比.