Quick compiler construction using uniform code generators

This paper describes our experience in using a common set of code generating subroutines as the basis for compilers of ALGOL W, ALGOL 60 and subsets of PL/I and COBOL. The advantages of using a common set of primitives for implementing more than one compiler include: (1) greatly reduced effort to implement additional languages; (2) simplified maintenance of the generated compilers; (3) standardized diagnostic messages for all compilers implemented using this system; and (4) simplified documentation of the compilers.     

A portable compiler-integrated approach to permanent checking

Program checking is now a mature technology, but is not yet used on a large scale. We identify one cause of this gap in the decoupling of checking tools from the everyday development tools. To radically change the situation, we explore the integration of simple user-defined checks into the core of every development process: the compiler. The checks we implement express constrained reachability queries in the control flow graph taking the form “from x to y avoiding z”, where x, y, and z are native code patterns containing a blend of syntactic, semantic and dataflow information. Compiler integration enables continuous checking throughout development, but also a pervasive propagation of checking technology. This integration poses some interesting challenges, including tight bounds on the acceptable overhead, but in turn opens up new perspectives. Factorizing analyses between checking and compiling improves both the efficiency and the expressiveness of the checks.     

A sentence generator for a compiler for PT,a pascal subset

An implementation of a sentence generator system for a compiler for PT, a subset of Pascal, is discussed. Using the syntax definition of PT, the system automatically produces leftmost generations in a pseudorandom fashion. Syntactically correct as well as compile-time correct programs can be generated. In the generation of compile-time correct programs, only those statements that satisfy the contextual constraints imposed by the declarative part of the generated program are generated. The system also provides the facility of producing programs that have lexical or syntactic errors. All the generated programs are printed with appropriate indentations to show structural properties. Furthermore, the number of procedures in the generated program, the number of statements, identifier length and the number of generations can be controlled. The implementation has been successfully used for testing an error recovery parser as well as an intermediate code generator for PT.     

The structure of the MARY/2 compiler

The MARY12 language implemented at Penobscot Research Center contains language differences from previous MARY implementations. These differences significantly increase the difficulty of implementing a compiler. Similar constructs have appeared in recent language proposals such as those for ADA. The methods of the MARY/2 compiler should be useful in compilers for these and other future languages. This paper discusses the language constructs which are the source of the difficulty; the implementation methods actually used; possible trade used; and the character of the programs which these constructs facilitate.     

Compilers — some good,some bad!

The paper examines the code produced by three compilers on a DEC-20 together with the effects of some compiler switches on this code. Some very surprising results are found.     

Practical testing of a C99 compiler using output comparison

A simple technique is presented for testing a C99 compiler, by comparing its output with the output from pre‐existing tools. The advantage to this approach is that new test cases can be added in bulk from existing sources, reducing the need for in‐depth investigation of correctness issues and for creating new test code by hand. This technique was used in testing the PalmSource Palm OS® Cobalt ARM C/C++ cross‐compiler for Palm‐Powered® personal digital assistants, primarily for standards compliance and the correct execution of generated code. The technique described here found several hundred bugs, mostly in our in‐house code, but also in longstanding high‐quality front‐ and back‐end code from Edison Design Group and Apogee Software. It also found 18 bugs in the GNU C compiler, as well as a bug specific to the Apple version of GCC, a bug specific to the Suse version of GCC, and a dozen bugs in versions of GCC for the ARM processor, several of which were critical. Copyright © 2007 John Wiley & Sons, Ltd.     

Efficient compiler and run-time support for parallel irregular reductions

Many scientific applications are comprised of irregular reductions on large data sets. In shared-memory parallel programs, these irregular reductions are typically computed in parallel using replicated buffers, then combined using synchronization. We develop L W , a new technique which partitions irregular reductions so that each processor computes values only for locally assigned data, eliminating the need for buffers or synchronized writes. Computation is replicated if its results are needed on multiple processors. We experimentally evaluate its performance for three irregular codes on a software DSM running on a distributed-memory multiprocessor and two shared-memory multiprocessors while varying connectivity, locality, and adaptivity. Results show L W improves performance significantly compared to using replicated buffers, and can match or exceed explicit message-passing gather/scatter for applications with low locality or high adaptivity.     

Simple register spilling in a retargetable compiler

This paper describes the management of register spills in a retargetable C compiler. Spills are rare, which means that testing is a bigger problem than performance. The trade-offs have been arranged so that the common case (no spills) generates respectable code quickly and the uncommon case (spills) is less efficient but as simple as possible. The technique has proven practical and is in production use on VAX, Motorola 68020, SPARC and MIPS machines.     

Deriving a compiler from an operational semantics written in VDL

This paper addresses the issue of compiler correctness. The approach taken is to systematically construct a correct compiler for a language from a formal semantic definition of the language. For this purpose, an operational semantics of a language is chosen as the basis for the approach. That is, the compiler for a language is derived from an interpreter of the language. The derivation process uses the notion of mixed computation proposed by Ershov. Briefly stated, one begins interpreting and when a primitive state changing instruction is about to be executed, the instruction is emitted as code instead. The correctness of all compilers produced by the method is guaranteed by proving the derivation rules correct. This proof is a one-time task for each specification language. The specification language studied in this paper is the Vienna Definition Language (VDL). The object code generated by the compiler is in an intermediate language close to an assembly language. Therefore, the translation from the intermediate language into the assembly language should be straightforward.     

A MATLAB subset to C compiler targeting embedded systems

This paper describes MATISSE, a compiler able to translate a MATLAB subset to C targeting embedded systems. MATISSE uses LARA, an aspect‐oriented programming language, to specify additional information and transformations to the input MATLAB code, for example, insertion of code for initialization of variables, and specification of types and shapes of variables. The compiler is being developed bearing in mind flexibility, multitarget and multitoolchain support, allowing for the generation of several implementations in C from the same reference code in MATLAB. In this paper, we also present a number of techniques being employed in MATLAB to C compilation, such as element‐wise mapping operations, matrix views, weak types, and intrinsics. We validate these techniques using MATISSE and a set of representative benchmarks. More specifically, we evaluate the compiler with a set of 31 benchmarks using an embedded system board and a desktop computer. The results show speedups up to 1.8× by employing information provided by LARA aspects, when compared with C code generated without additional user information. When compared with the execution time of the original code running on MATLAB, the execution time of the generated C code achieved a geometric mean speedup of 13×. Copyright © 2016 John Wiley & Sons, Ltd.     

Compiler support for floating-point computation

Predictability is a basic requirement for compilers of floating-point code—it must be possible to determine the exact floating-point operations that will be executed for a particular source-level construction. Experience shows that many compilers fail to provide predictability, either because of an inadequate understanding of its importance or from an attempt to produce locally better code. Predictability can be attained through careful attention to code generation and a knowledge of the common pitfalls. Most language standards do not completely define the precision of floating-point operations, and so a good compiler must also make a good choice in assigning precisions of subexpression computation. Choosing the widest precision that will be used in the expression usually gives the best trade-off between efficiency and accuracy. Finally, certain optimizations are particularly useful for floating-point and should be included in a compiler aimed at scientific computation. But predictability is more important than efficiency; obtaining incorrect answers fast helps no one.     

A pascal compiler for PDP 11 minicomputers

In this paper the development of a cross-compiler running on the central computing facility is described. The compiler transforms PASCAL source code into object code for the PDP 11 family. The arguments for higher level languages on minicomputers and the choice made for PASCAL are discussed. It is shown that only a minor effort in terms of manpower is required if such a development is based on an existing compiler that is suited to the purpose of adaptation. Even without large amounts of optimization the code produced is both compact and efficient. Some attention is paid to requirements that should be fulfilled in portable compilers. The paper ends with a discussion of some strong points and weak points of the PDP 11 architecture.     

Implementing an embedded compiler using program transformation rules

Domain‐specific languages (DSLs) are well‐recognized to ease programming and improve robustness for a specific domain, by providing high‐level domain‐specific notations and checks of domain‐specific properties. The compiler of a DSL, however, is often difficult to develop and maintain, because of the need to define a specific treatment for a large and potentially increasing number of language constructs. To address this issue, we propose an approach for specifying a DSL compiler using control‐flow sensitive concrete‐syntax based matching rules. These rules either collect information about the source code to carry out checks or perform transformations to carry out compilation. Because rules only mention the relevant constructs, using their concrete syntax, and hide the complexity of control‐flow graph traversal, it is easy to understand the purpose of each rule. Furthermore, new compilation steps can be added using only a small number of lines of code. We explore this approach in the context of the z2z DSL for network gateway development and show that it is beneficial to implement the core of its compiler in this manner.Copyright © 2013 John Wiley & Sons, Ltd.     

Experience acquiring and retargeting a portable Ada compiler

A technique for implementing Ada with reasonable effort on a piece of non-standard hardware is described. The target machine is a single processing element in an experimental multiprocessor based on NS32000. A portable Ada front-end compiler was used for retargeting, and the process of acquiring and evaluating the front end is described. Based on this experience, comments on the validation, quality and efficiency of Ada compilers are given, along with a detailed overview of the resultant system. The Ada system was built from scratch on the bare hardware. It has three main components: a code generator, a run-time system and an Ada kernel. The code generator is table driven and generates symbolic NS32000 assembler. This code is then assembled and linked by commercially available components. The run-time system and the kernel are implemented in assembly language and Concurrent Euclid and handle tasking, exceptions and scheduling. The result is a complete Ada implementation.     

Converting a portable Pascal p-code interpreter to a code generator

This is a technical note that assumes reader familiarity with Pagan's paper on converting scaled down Pascal p-code programming language interpreters into simple compilers.¹ This note discusses the extension of Pagan's methods to a full-scale Pascal-to-C translator. In order to make procedure calls and typed function calls work properly for such a translator, it was found necessary to add type information to one of the p-code calling instructions (and alter the Pascal-to-p-code translator accordingly). A table of execution times for Pagan's ‘50 primes’ bench-mark program shows the improvements obtained as a result of successive refinements in the Pascal-to-C translator, until the present version that uses C ‘register variables’ for integer arithmetic.² Programs compiled using this system can also be linked into C programs as functions or procedures and can be debugged using standard C debuggers.     

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.     

A simple system for generating efficient lexical scans

A language for specifying lexical scans is described.The language uses the model of a finite state automation with a limited back-up facility.It is efficiently implementable and is machine independent except for one statement which depends on the machine's character set.