Natural Semantics-Directed Generation of Compilers and Abstract Machines

In this paper we present the motivation, theory and transformations of our semantics-directed compiler generator. The main novelty of our generator is that it generates compilers and abstract machines. The execution times of the abstract machine programs produced by our generated compiler compare well to those of target programs produced by compilers generated by other semantics-directed generators. The generated specifications of compilers and abstract machines are suitable as a starting point for handwriting compilers and abstract machines. Our generator is fully automated and its core transformations are proved correct. Received May 1997 / Accepted in revised form May 2000     

基于类库的可重定向编译器后端设计与实现

该文在对几种可重定向编译器进行分析的基础上,提出了一种基于类库的可重定向编译器后端设计技术。该技术通过恰当定义机器描述与代码生成之间的接口,抽象不同硬件平台共有的操作与功能,隔离中间表示和不同硬件平台汇编语言代码的差异。根据不同硬件平台特点,利用面向对象技术实现接口,构成重定向支持类库。代码生成器通过对接口的调用,将中间表示转化为相应平台的汇编语言,完成编译器后端的重定向工作。     

P3 L: A structured high-level parallel language,and its structured support

The paper presents a parallel programming methodology that ensures easy programming, efficiency and portability of programs to different machines belonging to the class of the general-purpose, distributed-memory, MIMD architectures. The methodology is based on the definition of a new, high-level, explicitly parallel language, called P³ L, and of a set of static tools that automatically adapt the program features for each target architecture. P³ L does not require programmers to specify process activations, the actual parallelism degree, scheduling, or interprocess communications, i.e. all those features that need to be adjusted to harness each specific target machine. Parallelism is, on the other hand, expressed in a structured and qualitative way, by hierarchical composition of a restricted set of language constructs, corresponding to those forms of parallelism that are frequently encountered in parallel applications, and that can be efficiently implemented. The efficient portability of P³ L applications is guaranteed by the compiler along with the novel structure of the support. The compiler automatically adapts the program features for each specific architecture, using the costs (in terms of performance) of the low-level mechanisms exported by the architecture itself. In our methodology, these costs, along with other features of the architecture, are viewed through an abstract machine, whose interface is used by the compiler to produce the final object code.     

Designing an adaptable heterogeneous abstract machine by means of reflection

The concepts of abstract and virtual machines have been used for many different purposes to obtain diverse benefits such as code portability, compiler simplification, interoperability, distribution and direct support of specific paradigms. Despite of these benefits, the main drawback of virtual machines has always been execution performance. Consequently, there has been considerable research aimed at improving the performance of virtual machine's application execution compared to its native counterparts. Techniques like adaptive Just In Time compilation or efficient and complex garbage collection algorithms have reached such a point that Microsoft and Sun Microsystems identify this kind of platforms as appropriate to implement commercial applications.What we have noticed in our research work is that these platforms have heterogeneity, extensibility, platform porting and adaptability limitations caused by their monolithic designs. Most designs of common abstract machines are focused on supporting a fixed programming language and the computation model they offer is set to the one employed by the specific language. We have identified reflection as a basis for designing an abstract machine, capable of overcoming the previously mentioned limitations. Reflection is a mechanism that gives our platform the capability to adapt the abstract machine to different computation models and heterogeneous computing environments, not needing to modify its implementation. In this paper we present the reflective design of our abstract machine, example code extending the platform, a reference implementation, and a comparison between our implementation and other well-known platforms.     

A portable virtual machine for Ada

A portable compiler can be constructed by letting it generate code for a virtual machine, which is then implemented on the real target machines. The design of a virtual machine which is especially suitable as a target machine for compiled Ada programs is described. The main design goals, implementability on mini-computers and portability, are discussed and the resulting design is described in some detail. Some implementation strategies for the machine are proposed and the feasibility of the virtual machine approach is discussed.     

基于GCC的VLIW编译系统研究

VLIW机器在单个机器周期中同时发射并执行多个的并行操作,从而获得较高的指令级并行度,这些操作之间的依赖分析和调度工作则被完全交给相应的编译器执行,因此VLIW的并行性能能否充分发挥取决于VLIW体系结构相关编译器的质量。GNU开发的GCC是被最广泛使用的编译系统之一,它具有多语言、多平台支持的能力和开放的结构,能够运用各种成熟的常规编译优化技术生成高效的代码。文章分析了VLIW及GCC的结构特点,提出了一种基于GCC的VLIW编译系统设计方案,利用GCC进行RTL中间代码一级的体系结构无关优化和少量体系结构相关优化,在汇编代码一级针对VLIW结构进行体系结构相关的优化,从而充分利用GCC的成熟编译技术快速开发高效的VLIW多语言编译系统。     

An Object-Oriented Framework for Loop Parallelization

Generation of efficient parallel code is a major goal of a well-designed and developed parallelizing compiler. Another important goal is portability of both compiler system and the resulting output source codes. The various choices of current and future parallel computer architectures as well as the cost of developing a parallelizing compiler make portability a very important design goal. Since the design of parallelizing compilers is considerably move complex than designing conventional compilers, it is very important to achieve both efficiency and portability. To meet this dual goal, we have investigated the application of object oriented design to parallelizing compilers. Our parallelizing compiler design is based on abstractions of intermediate representations of loops and their class definitions. In this paper, we address the problem of loop parallelization and propose a framework where the loop parallelization process is divided into three phases and the optimization of loops is performed via a cyclic application of these three phases. The class of each phase is hierarchically derived from intermediate representations of loops. This facilitates the portability of the resulting parallelizing compilers. Furthermore, one of the phases uses a reservation table of hardware resources in order to obtain optimized parallel programs for given hardware resources. The validation of the proposed framework is given through the application of the object oriented design on an example program which is then parallelized efficiently.     

Automatic detection and diagnosis of faults in generated code for procedure calls

In this paper, we present a compiler testing technique that closes the gap between existing compiler implementations and correct compilers. Using formal specifications of procedure-calling conventions, we have built a target-sensitive test suite generator that builds test cases for a specific aspect of compiler code generators: the procedure-calling sequence generator. By exercising compilers with these specification-derived target-specific test suites, our automated testing tool has exposed bugs in every compiler tested on the MIPS and one compiler on the SPARC. These compilers include some that have been in heavy use for many years. Once a fault has been detected, the system can often suggest the nature of the problem. The testing system is an invaluable tool for detecting, isolating, and correcting faults in today's compilers.     

A portable lisp compiler

The programming language LISP is usually implemented via an interpreter, and a compiler is added later as a LISP program. However, all such production compilers known to the authors produce explicit instructions for the given computer being used. This paper describes the development of a portable LISP compiler in the sense that only Standard LISP functions are used in its definition and the output is a sequence of abstract machine codes, easily mapped to instruction sequences on current computers. The resulting code is quite efficient, demonstrating once again the maxim that most compiler optimization is largely machine independent.     

An optimizing compiler for the icon programming language

Compiling code for the Icon programming language presents several challenges, particularly in dealing with types and goal-directed expression evaluation. In order to produce optimized code, it is necessary for the compiler to know much more about operations than is necessary for the compilation of most programming languages. This paper describes the organization of the Icon compiler and the way it acquires and maintains information about operations. The Icon compiler generates C code, which makes it portable to a wide variety of platforms and also allows the use of existing C compilers for performing routine optimizations on the final code. A specially designed implementation language, which is a superset of C, is used for writing Icon's run-time system. This language allows the inclusion of information about the abstract semantics of Icon operations and their type-checking and conversion requirements. A translator converts code written in the run-time language to C code to provide an object library for linking with the code produced by the Icon compiler. The translation process also automatically produces a database that contains the information the Icon compiler needs to generate and optimize code. This approach allows easy extension of Icon's computational repertoire, alternate computational extensions, and cross compilation.     

The portability of the BCPL compiler

Methods of achieving program portability are discussed, with particular reference to the mobility of compilers. The method of transferring the BCPL compiler is then described including the specification of OCODE which is the language used as an interface between the machine independent and machine dependent parts of the compiler.     

Tuning Compiler Optimizations for Simultaneous Multithreading

Simultaneous Multithreading (SMT) is a processor architectural technique that promises to significantly improve the utilization and performance of modern wide-issue superscalar processors. An SM T processor is capable of issuing multiple instructions from multiple threads to a processor's functional units each cycle. Unlike shared-memory multiprocessors, SMT provides and benefits from fine-grained sharing of processor and memory system resources; unlike current uniprocessors, SMT exposes and benefits from inter-thread instruction-level parallelism when hiding long-latency operations. Compiler optimizations are often driven by specific assumptions about the underlying architecture and implementation of the target machine, particularly for parallel processors. For example, when targeting shared-memory multiprocessors, parallel programs are compiled to minimize sharing, in order to decrease high-cost inter-processor communication. Therefore, optimizations that are appropriate for these conventional machines may be inappropriate for SMT, which can benefit from finegrained resource sharing within the processor. This paper reexamines several compiler optimizations in the context of simultaneous multithreading. We revisit three optimizations in this light: loop-iteration scheduling, software speculative execution, and loop tiling. Our results show that all three optimizations should be applied differently in the context of SMT architectures: threads should be parallelized with a cyclic, rather than a blocked algorithm; non-loop programs should not be software speculated, and compilers no longer need to be concerned about precisely sizing tiles to match cache sizes. By following these new guidelines, compilers can generate code that improves the performance of programs executing on SMT machines.     

Machine structure oriented control code logic

Control code is a concept that is closely related to a frequently occurring practitioner’s view on what is a program: code that is capable of controlling the behaviour of some machine. We present a logical approach to explain issues concerning control codes that are independent of the details of the behaviours that are controlled. Using this approach, such issues can be explained at a very abstract level. We illustrate this among other things by means of an example about the production of a new compiler from an existing one. The approach is based on abstract machine models, called machine structures. We introduce a model of systems that provide execution environments for the executable codes of machine structures and use it to go into portability of control codes.     

The portable compiling systems of MUSS

Portability of MUSS compilers is achieved by using an abstract machine model concept. Two different abstract models, both suited for multi-language multi-machine usage, have been developed and evaluated. These models differ mainly in the level of interface to the compiler. The form of these models and the performance of two compilers, each using both models, are presented.     

Mix: A self-applicable partial evaluator for experiments in compiler generation

The program transformation principle called partial evaluation has interesting applications in compilation and compiler generation. Self-applicable partial evaluators may be used for transforming interpreters into corresponding compilers and even for the generation of compiler generators. This is useful because interpreters are significantly easier to write than compilers, but run much slower than compiled code. A major difficulty in writing compilers (and compiler generators) is the thinking in terms of distinct binding times: run time and compile time (and compiler generation time). The paper gives an introduction to partial evaluation and describes a fully automatic though experimental partial evaluator, called mix, able to generate stand-alone compilers as well as a compiler generator. Mix partially evaluates programs written in Mixwell, essentially a first-order subset of statically scoped pure Lisp. For compiler generation purposes it is necessary that the partial evaluator be self-applicable. Even though the potential utility of a self-applicable partial evaluator has been recognized since 1971, a 1984 version of mix appears to be the first successful implementation. The overall structure of mix and the basic ideas behind its way of working are sketched. Finally, some results of using a version of mix are reported.     

Horizon: a retargetable compiler for horizontal microarchitectures

The vertical migration of complex application code into horizontal microcode makes traditional methods of handwritten and hand-optimized microcode with primitive assembly languages impractical. Higher-level languages that permit abstraction from low-level timing and concurrency details are considered a major step toward alleviating the problem. This approach is feasible only if compilers for these languages exist that can produce high-quality microcode and that can be targeted to new machines with modest effort and high reliability. An overview is provided of the Horizon retargetable microcode compiler, which facilitates the production of highly optimized microcode and the targeting of the compiler to specific machines     

面向嵌入式系统的优化编译器生成器设计

构造嵌入式系统是一个硬件软件的协同设计问题 .嵌入式软件的有效开发需要相应编译器的支持 .由于嵌入式系统存储空间有限 ,所以编译器生成的机器代码必须非常紧凑 .我们可以使用编译器的生成器来提高编译器的开发效率 .本文给出了一种编译器生成器的设计原理 ,利用该编译器生成器可以迅速生成面向某种指令系统和机器特征 ,并且能够对输出代码进行自动紧凑的编译器     

Making a compiler easily portable

The authors describe a technique for porting a modern language that makes it possible to port the language quickly and still get fast execution. They relate the practical experience they gained when porting the compiler to different environments. They concentrate on transportation problems of compilers that generate machine code rather than those that generate interpreter code. The authors' approach is based on the definition of a universal operating-system interface that must be implemented on the target machine to install the compiler. They ported the Modula-2/68K compiler, which was developed at their institute and has successfully been installed at external sites. Of the two porting procedures they offered-source-code cross development and object-code transportation-the external sites preferred the latter because it requires less effort     

面向申威异构架构的并行代码自动生成

异构架构逐渐成为高性能计算领域的主流架构,但相较于同构多核架构,其硬件结构及存储层次更为复杂,程序编写更为困难.先进的优化编译器可以协助程序开发人员实现更为高效的代码,降低程序开发复杂度.多面体编译模型通过抽象分析将程序抽象成空间多面体表示形式,能够将多种循环变换与硬件映射相结合,并面向特定体系结构生成相应的代码.设计实现了一个面向国产申威异构架构的并行代码自动生成系统,采用“源-源”编译模式,基于多面体编译模型实现.系统针对申威异构架构特点将程序计算过程进行硬件部署,同时实现数据传输与内存空间的自动管理.实验基于Polybench测试集中线性代数相关用例进行测试.结果表明,利用代码自动生成系统生成的异构并行代码能够在申威异构平台上正确运行,并能够有效发挥申威异构平台的性能,基于申威异构平台利用64线程加速计算的平均加速比达到了539.16倍.     

Exploiting machine-specific pointer operations in abstract machines

Increasingly powerful machine instructions complicate abstract machine design for portability. Abstract machine instructions must be “larger” than the target machine instructions that they are to exploit, but they must not grow so large as to complicate the realization of the abstract machine on real machines. This paper presents related techniques for low-level yet machine-independent access to typical stack and string-processing instructions.