具有可适应性的程序分析技术

【作者】 连瑞琦；

【导师】 张兆庆；

【作者基本信息】 中国科学院研究生院（计算技术研究所） ， 计算机系统结构， 2000， 博士

【摘要】 编译器在发掘高性能计算机系统并行性的过程中起着非常重要的作用，而其中程序分析又是编译器开发并行性的关键步骤之一。然而，对编译器精度和功能的要求的逐步提高，导致程序分析日益复杂，难于编写、移植和维护。因此，程序分析部分的可适应性问题成为编译领域的研究热点之一。本文在对程序分析算法本身及程序分析对不同并行体系结构的支持方式进行了较为深入的研究后，得到了一个能解决程序分析可适应性问题的整体方案，该方案通过运用多视图的编程范式、过程间分析优化程序自动生成和增量式分析算法等手段，取到了比较好的效果。 本文的主要贡献有： 1．提出一个能适用于所有过程间数据流分析问题的模型。这个模型中过程间分析问题完全是过程内分析问题的扩展，克服了以前其它模型把过程间和过程内分析问题割裂开来的缺点。通过这种模型，我们可以采用统一的、相互协作的过程间和过程内算法解决数据流分析问题，并得到较为精确的上下文敏感的分析结果。 2．根据以上问题模型，提出并实现了一个过程间分析优化程序生成器——IGEN。在IGEN中，我们主要解决了用户描述方法，算法框架选择等问题。由于以上问题的很好解决，IGEN可以生成过程间分析程序和优化程序，并且，它生成的程序具有独立于中间表示，可在一定范围内拼装、选择算法，可增量式维护信息等特点。所以，IGEN既能大幅度减轻程序员的劳动，又能大大提高过程间分析优化部分的可适应性。 3．提出了用多视图的编程范式编制程序分析部分的方案。这里，我们主要解决了视图的划分和定义，算法抽象层次的确定等问题，该方案的运用使程序分析部分从多个方面具备了较高程度的可适应性。 4．提出了一种增量式分析算法。该算法可以适用于所有类型的流图——包括可归约流图和不可归约流图。另外，它实现也比较简单，能方便地运用于分析程序自动生成器中。 5．根据以上算法和设计，实现了一个具有可适应性的程序分析高层模块，并将这个模块分别运用在几个不同的编译系统中，对该模块从正确性、效率和可适应性等几方面进行了验证。更多还原

【Abstract】 Compiler is very critical to exploit the parallelism for all kinds of parallel processing systems. Program analysis is the most important way to find the parallelism among all phases of a compiler. But the increasing requirement on the aspects of accuracy and functionality causes that the program analysis phase become more and more complicated to be developed, ported and maintained. So, the research on the flexibility of the program analysis has become a hotspot on the compilation field. After the deeply study of the algorithm and the way to support different parallel architectures of the program analysis, this paper presents an integral approach to improve the flexibility of the program analysis phase. By using many useful techniques, such as multi-view programming paradigm, automatic generation of the interprocedural analyzer and optimizer and incremental analysis, the approach can acquire fairly good effect.The main contributions of this paper are listed below. Present an interprocedural model, which can describe all data flow problem. In the model, each interprocedural problem is the extension of its corresponding intraprocedural problem, which can avoid solving the interprocedural problems and the intraprocedural problems completely separately. By using this model, we can solve an interprocedural problem by applying an algorithm consisting of two cooperative parts— the interprocedural part and the intraprocedural part and can get context-sensitive analysis result. Present and implement an automatic generator of analyzers and optimizers — IGEN. In the design, we provide a proper description method to users and select the compatible frameworks for the interprocedural part and the intraprocedural part. IGEN can generate interprocedural analyzers and optimizers and the features of its products are: they are independent of intermediate representation; they can maintain the analysis information incrementally; they provide several selections to users to select algorithms. Generally, IGEN can not only save a lot of developing work of programmers, but also improve the flexibility of the program analysis phase greatly. Present an approach of using multi-view programming paradigm to construct the program analysis phase, which mainly solve such problems as the decision of the size of views, the division of views and the abstractive level of algorithms.更多还原