Even though impressive progress has been made in the area of optimizing and parallelizing scientific programs with arrays, the application of similar techniques to programs with general (cyclic) pointer data structures has remained difficult. In this paper we introduce a new approach that leads to improved analysis and transformation of programs with recursively-defined pointer data structures.

Our approach is based on providing a mechanism for the abstract description of data structures (ADDS), which makes explicit the important properties, such a dimensionality, of pointer data structures. As illustrated with numerous examples, the ADDS definitions are both natural to specify, and general enough to handle both simple and complex pointer data structures.

We illustrate how an abstract data structure description can improve analysis by presenting an alias analysis approach that combines an alias analysis technique, path matrix analysis, with information available from an ADDS declaration. Given this improved alias analysis technique, we provide a concrete example of applying a software pipelining transformation to loops involving pointer data structures.

High-performance architectures rely upon powerful optimizing and parallelizing compilers to maximize performance. Such compilers need accurate program analysis to enable their performance-enhancing transformations. In the domain of program analysis for parallelization, pointer analysis is a difficult and increasingly common problem. When faced with dynamic, pointer-based data structures, existing solutions are either too limited in the types of data structures they can analyze, or require too much effort on the part of the programmer.

Recently we proposed a compromising approach, in which the programmer supplies some small amount of information, and the compiler performs the remaining analysis [HHN92a]. However, the language for conveying this information is unable to accurately describe a number of important data structures, and does not easily support the compiler's underlying alias analysis. In this paper we present a more powerful description language that also directly supports alias analysis. Ultimately, this will lead to more accurate program analysis for a larger class of programs, and hence the increased application of performance-enhancing transformations on these programs.

A general theoretical framework is developed for the study of branch speculation. The framework yields a systematic way to select the schedule in a given set that, for any (estimated) bias of the branch, minimizes the expected execution time. Among other things, it is shown that in some cases the optimal schedule is neither of those resulting from aggressively speculating on any given outcome of the conditional. Our results can be useful in either static or dynamic approaches. We propose a simple run-time estimator for the bias and discuss how to combine it with schedule selection. A number of examples motivate and illustrate the techniques, and show that our approach yields better performance in the case of highly unpredictable branches.

Even though impressive progress has been made in the area of optimizing and parallelizing array-based programs, the application of similar techniques to programs using pointer data structures has remained difficult. Unlike arrays which have a small number of well-defined properties, pointers can be used to implement a wide variety of structures which exhibit a much larger set of properties. The diversity of these structures implies that programs with pointer data structures cannot be effectively analyzed by traditional optimizing and parallelizing compilers.

In this paper we present a new approach that leads to the improved analysis and transformation of programs with recursively-defined pointer data structures. Our approach is based on a mechanism for the Abstract Description of Data Structures (ADDS). ADDS is a simple extension to existing imperative languages (such as C) that allows the programmer to explicitly describe the important properties of a large class of data structures. These abstract descriptions may be used by the compiler to achieve more accurate program analysis in the presence of pointers, which in turn enables and improves the application of numerous optimizing and parallelizing transformations.

We present ADDS by describing various data structures, we discuss how such descriptions can be used to improve analysis and debugging, and we supply three important transformations enabled by ADDS.

Even though impressive progress has been made in the area of parallelizing scientific programs with arrays, the application of similar techniques to programs with pointer data structures has remained difficult. Unlike arrays which have a small number of well-defined properties that can be utilized by a parallelizing compiler, pointer data structures are used to implement a wide variety of structures that exhibit a much more diverse set of properties. The complexity and diversity of such properties means that, in general, scientific programs with pointer data structures cannot be effectively analyzed by an optimizing and parallelizing compiler.

In order to provide a system in which the compiler can fully utilize the properties of different types of pointer data structures, we have developed a mechanism for the Abstract Description of Data Structures (ADDS). With our approach, the programmer can explicitly describe important properties such as dimensionality of the pointer data structure, independence of dimensions, and direction of traversal. These abstract descriptions of pointer data structures are then used by the compiler to guide analysis, optimization, and parallelization.

In this paper we summarize the ADDS approach through the use of numerous examples of data structures used in scientific computations, we illustrate how such declarations are natural and non-tedious to specify, and we show how the ADDS declarations can be used to improve compile-time analysis. In order to demonstrate the viability of our approach, we show how such techniques can be used to parallelize an important class of scientific codes which naturally use recursive pointer data structures. In particular, we use our approach to develop the parallelization of an N-body simulation that is based on a relatively complicated pointer data structure, and we report the speedup results for a Sequent multiprocessor.

The efficient execution of Java programs presents a challenge to hardware and software designers alike. The difficulty however lies with the Java bytecodes. Their model of a simplistic, platform-independent stack machine is well-suited for portability, though at the expense of execution speed. Various approaches are being proposed to increase the speed of Java bytecode programs, including: (1) on-the-fly compilation to native code (also known as JIT or "just-in-time" compilation); (2) traditional ("ahead-of-time") compilation of bytecodes to some higher-level intermediate form and then to native code; and (3) translation of bytecodes to a higher-level language and then use of an existing compiler to produce native code. Speedups on the order of 50 over standard bytecode interpretation have been claimed.

All of these approaches rely upon bytecode analysis (of varying sophistication) to extract information about the program, which is then used to optimize the native code during the translation process. However, extracting information from a bytecode representation is expensive, and in general does not collect all the information originally available at the source-level.

In this paper we propose an optimization approach based on bytecode annotations. The bytecodes are annotated during the original source code to bytecode translation, allowing both traditional interpretation by a JVM and aggressive optimization by an annotation-aware bytecode compiler. Annotations do not hinder portability nor compatibility, while preserving optimization information that is (1) expensive to recompute and (2) sometimes impossible to recompute. Preliminary results yield bytecode with C-like performance using JIT technology.