To derive maximum optimization benefits from partial redundancy elimination (PRE),it is necessary to go beyond its safety constraint. Algorithms for optimal speculative code motion have been developed based on the application of minimum cut to flow networks formed out of the control flow graph. These previous techniques did not take advantage of the SSA form, which is a popular program representation widely used in modern-day compilers. We have developed the MC-SSAPRE algorithm that enables an SSA-based compiler to take full advantage of SSA to perform optimal speculative code motion efficiently when an execution profile is available. Our work shows that it is possible to form flow networks out of SSA graphs, and the min-cut technique can be applied equally well on these flow networks to find the optimal code placement. We provide proofs of the correctness and computational and lifetime optimality of MC-SSAPRE. We analyze its time complexity to show its efficiency advantage. We have implemented MC-SSAPRE in the open-sourced Path64 compiler. Our experimental data based on the full SPEC CPU2006 Benchmark Suite show that MC-SSAPRE can further improve program performance over traditional SSAPRE, and that our sparse approach to the problem does result in smaller problem sizes.

A variable instruction set processor provides a dictionary that enables the compiler to configure the best instruction set to use for executing the program being compiled. This paper describes Cognigine's variable instruction set communication architecture (VISC Architecture) and the implementation of a compiler that provides effective compilation and optimization support for this target. The compiler implementation involves the use of an abstract operation representation that enables the code generator to optimize toward the core architecture of the processor without committing to any specific instruction format. It then uses an enumeration approach to instruction scheduling that determines the final forms of the instructions to be generated while still adhering to the irregular constraints imposed by the architecture. The enumeration approach also allows the incorporation of dictionary reuse functionality to provide trade offs between program performance and dictionary budget. Finally, we provide experimental results to show the effectiveness of these compilation techniques in supporting Cognigine's VISC Architecture.

This paper describes the implementation of an instruction scheduler that produces near-optimal results by efficiently enumerating all possible schedules. The scheduler is implemented in the context of an embedded processor that allows compile-time configuration of the instruction set to use for each program, where the need to adhere to the tight and irregular hardware constraints were the original motivation for using this approach. We present techniques that speed up the enumeration process by coming up with good initial lower bound estimates for the schedules and by pruning off large areas of the search space through implicit enumeration. In the process, we found that taking the hardware constraints into account actually helps in speeding up the enumeration. We provide performance data that show that the enumeration approach is superior to heuristics-based approaches like list scheduling for our target processor. The data also show that the compile-time overhead associated with enumeration can be effectively contained. This justifies the deployment of enumeration-based instruction schedulers in commercial compilers targeting embedded processors with similar tight constraints.

The SSAPRE algorithm for performing partial redundancy elimination based entirely on SSA form is presented. The algorithm is formulated based on a new conceptual framework, the factored redundancy graph, for analyzing redundancy, and representes the first sparse approach to the classical problem and on methods for its solution. With the algorithm description, theorems and their proofs are given showing that the algorithm produces the best possible code by the criteria of computational optimality and lifetime optimality of the introduced temporaries. In addition to the base algorithm, a practical implementation of SSAPRE that exhibits additional compile-time efficiencies is described. In closing, measurement statistics are provided that characterize the instances of the partial redundancy problem from a set of benchmark programs and compare optimization time spent by an implementation of SSAPRE aganist a classical partial redundancy elimination implementation. The data lend insight into the nature of partial redundancy elimination and demonstrate the expediency of this new approach.

An algorithm for register promotion is presented based on the observation that the circumstances for promoting a memory location’s value to register coincide with situations where the program exhibits partial redundancy between ac-cesses to the memory location. The recent SSAPRE al-gorithm for eliminating partial redundancy using a sparse SSA representation forms the foundation for the present al-gorithm to eliminate redundancy among memory accesses, enabling us to achieve both computational and live range op-timality in our register promotion results. We discuss how to effect speculative code motion in the SSAPRE framework. We present two different algorithms for performing specu-lative code motion: the conservative speculation algorithm used in the absence of profile data, and the the profile-driven

A new algorithm, SSAPRE, for performing partial redundancy elimination based entirely on SSA form is presented. It achieves optimal code motion similar to lazy code motion [KRS94a, DS93], but is formulated independently and does not involve iterative data flow analysis and bit vectors in its solution. It not only exhibits the characteristics common to other sparse approaches, but also inherits the advantages shared by other SSA-based optimization techniques. SSAPRE also maintains its output in the same SSA form as its input. In describing the algorithm, we state theorems with proofs giving our claims about SSAPRE. We also give additional description about our practical implementation of SSAPRE, and analyze and compare its performance with a bit-vector-based implementation of PRE. We conclude with some discussion of the implications of this work.

The paper presents a technique called Global Instruction Distribution that globally fine-tunes the code produced for a superscalar processor. The fine-tuning is effected by distributing instructions from one block to other blocks according to the control flow graph of the program. The method does not involve instruction scheduling, but models resource usage to find the best insertion points in the target basic block. We present our implementation of GID in a production compiler, and show how the GID framework allows incorporation of additional functions targeting different optimizations. Performance measurements on the MIPS R8000 are presented to demonstrate the practicality and efficacy of this approach.

Global register allocation plays a major role in determining the efficacy of an optimizing compiler. Graph coloring has been used as the central paradigm for register allocation in modern compilers. A straightforward coloring approach can suffer from several shortcomings. These shortcomings are addressed in this paper by coloring the graph using a priority ordering. A natural method for dealing with the spilling emerges from this approach. The detailed algorithms for a priority-based coloring approach are presented and are contrasted with the basic graph-coloring algorithm. Various extensions to the basic algorithms are also presented. Measurements of large programs are used to determine the effectiveness of the algorithm and its extensions, as well as the causes of an imperfect allocation. Running time of the allocator and the impact of heuristics aimed at reducing that time are also measured.

Inter-procedural register allocation can minimize the register usage penalty at procedure calls by reducing the saving and restoring of registers at procedure boundaries. A one-pass inter-procedural register allocation scheme based on processing the procedures in a depth-first traversal of the call graph is presented. This scheme can be overlaid on top of intra-procedural register allocation via a simple extension to the priority-based coloring algorithm. Using two different usage conventions for the registers, the scheme can distribute register saves/restores throughout the call graph even in the presence of recursion, indirect calls or separate compilation. A natural and efficient way to pass parameters emerges from this scheme. A separate technique uses data flow analysis to optimize the placement of the save/restore code for registers within individual procedures. The techniques described have been implemented in a production compiler suite. Measurements of the effects of these techniques on a set of practical programs are presented and the results analysed.

Programs naturally require a variety of memory-addressing modes. It isn't necessary to provide them in hardware, however, if a compiler can synthesize them from a few primitive modes. This not only simplifies the hardware, but also permits the compiler to use its understanding of the program to economize on the modes which it uses. We present some compilation techniques that allow the compiler to deal effectively with a single addressing mode in a target RISC processor. We also give measurements to show the benefits of such techniques, and to support our assertion that a single addressing mode is adequate for a general purpose processor, provided that mode incorporates both a pointer and an offset.