基于程序流程图的数据例化与程序例化  

Data Specialization and Program Specialization Based on Control Flow Graph

作　　者：廖湖声[1] 

机构地区：[1]北京工业大学计算机学院,北京100022

出　　处：《计算机学报》2001年第9期985-990,共6页Chinese Journal of Computers

基　　金：北京市自然科学基金 ( 4 982 0 0 2 )资助

摘　　要：提出了一种基于程序流程图的部分求值方法 ,通过采用基于程序流程图的数据例化和面向程序基本块的程序例化 ,能够在例化阶段进行程序基本块例化的同时 ,完成控制转移的优化 ,并生成既可用于编译时刻例化 ,又可用于运行时刻例化的滞留程序 ;基于这种方式的部分求值系统采用离线工作方式 ,利用了绑定时间分析 ,提高了滞留程序的效率 ;同时避免了例化阶段的代码复制与拼接 ,有效地简化了运行时刻例化系统的实现难度 .Data specialization is a technique for improving the performance of program by splitting its execution into two phases. The first phase performs the early computations and stores their results in a cache. A program is generated for performing the second phase. It consists of the late computation and is parameterized with respect to the cache. In this paper, we present an alternative approach to implement specialization. It extends the traditional data specialization by storing specialized control flow graphs in the cache. Unlike traditional data specialization, our approach not only optimizes the control flow transfers, but also does not cause code explosion, which is also different with traditional program specialization.We have implemented a prototype of an offline data specializer with binding time analysis, which was used for program specialization. A specializer for individual program, which is produced in advance, is used to generate a specialized control flow graph with results of the early computation. A residual program is also generated at compile-time, which is composed of specialized blocks and a control flow graph interpreter, and it can be used in both compile-time specialization and run-time specialization. A cache including specialized control flow graph with early computation's results as their block parameters is produced at specialization-time. Performance of program is improved by using the results and the specialized control flow graph in the cache.The approach optimizes the control flow transfers and makes data specialization to be effective for programs whose bottlenecks are limited to control decisions. As a consequence, as the size of the specialization problem increases, only the cache increases, not the program. Although it achieves a somewhat lower degree of optimization than program specialization, very low overhead in time and space makes it attractive in applications where lightweight run-time specialization is needed. By avoiding dynamic code manipulation, implementation complexity

关 键 词：数据例化 程序流程图 程序例化 软件自动化 

分 类 号：TP311.51[自动化与计算机技术—计算机软件与理论]