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

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

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

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

点间确定别名及其在Java程序数据依赖分析中的应用

堆内存的大量使用使得Java程序上数据依赖关系的精确提取仍存在许多困难.对于堆空间上的依赖提取,通常的做法是先对堆上空间进行命名,再据此分析依赖关系.然而该方法不能在多个定义间进行强更新,故分析精度不够理想.针对此问题,该文首先提出了一种点间确定别名的概念,然后用它生成强更新和相对更新来精化数据依赖分析.实验表明,与不进行强更新和相对更新的数据依赖分析方法相比,新算法能够在相对较少的额外时间消耗内,有效地提高堆空间上依赖分析的精度.     

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

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

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

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

高效而精确的锁别名分析方法

锁别名分析能够得到锁指针变量的指向信息,有效的锁别名分析可以更好地辅助数据竞争分析和死锁分析.现有锁别名分析往往采用保守的方式处理,进而影响分析结果的准确性.针对这一问题,提出了一种锁别名分析方法,该方法首先使用GCC插件获取SSA形式的中间代码,然后对中间代码进行预处理以获得与锁、函数指针操作相关的语句,最后对预处理后的程序使用本文提出的FP_LOCK算法进行准确的流敏感、上下文敏感分析.实验结果表明该方法能精确地确定锁别名,并且经过预处理后的FP_LOCK算法对分析大程序平均有9.95倍的加速比.     

在C++Builder中动态创建ODBC和BDE别名

本文详细介绍了在C++Builder5中,如何动态创建常用数据库(ACCESS、SQL Server和ORACLE)的ODBC和BDE数据库连接别名,并提供了相应的程序片段.     

别名集切片与并行化研究

针对复杂程序的分析问题,提出基于别名集切片的切片级并行技术与并行程序分析技术。利用传统分析算法,在每个切片上并行地进行复杂程序分析,从而实现复杂程序分析的并行化,加快复杂程序分析速度。以SPEC CPU2000/CPU2006中的部分C程序为测试用例进行实验,结果表明,利用别名集切片技术可在4个进程并行情况下,获得3.42的加速比。     

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

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

Alias Analysis in Java with Reference-Set Representation for High-Performance Computing

In this paper, a flow-sensitive, context-insensitive alias analysis in Java is proposed. It is more efficient and precise than previous analyses for C++, and it does not negatively affect the safety of aliased references. To this end, we first present a reference-set alias representation. Second, data-flow equations based on the propagation rules for the reference-set alias representation are introduced. The equations compute alias information more efficiently and precisely than previous analyses for C++. Third, for the constant time complexity of the type determination, a type table is introduced with reference variables and all possible types for each reference variable. Fourth, an alias analysis algorithm is proposed, which uses a popular iterative loop method for an alias analysis. Finally, running times of benchmark codes are compared for reference-set and existing object-pair representation.     

Demand-Driven Memory Leak Detection Based on Flow- and Context-Sensitive Pointer Analysis

We present a demand-driven approach to memory leak detection algorithm based on flow- and context-sensitive pointer analysis. The detection algorithm firstly assumes the presence of a memory leak at some program point and then runs a backward analysis to see if this assumption can be disproved. Our algorithm computes the memory abstraction of programs based on points-to graph resulting from flow- and context-sensitive pointer analysis. We have implemented the algorithm in the SUIF2 compiler infrastructure and used the implementation to analyze a set of C benchmark programs. The experimental results show that the approach has better precision with satisfied scalability as expected. This work is supported by the National Natural Science Foundation of China under Grant Nos. 60725206, 60673118, and 90612009, the National High-Tech Research and Development 863 Program of China under Grant No. 2006AA01Z429, the National Basic Research 973 Program of China under Grant No. 2005CB321802, the Program for New Century Excellent Talents in University under Grant No. NCET-04-0996, and the Hunan Natural Science Foundation under Grant No. 07JJ1011.     

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.     

一种新的路由器多址综合方法

网络中路由器拓扑发现是研究网络结构和行为的重要基础。路由器多址综合问题是拓扑发现中的一个难题。在总结现有的路由器多址综合解决方法后提出一种新的方法——邻居-子网综合法。与以往方法相比,该方法可信度提高、效率变快,效果更加明显,较好地解决了路由器多址综合问题。