The paper describes the design and implementation of a median filter for graphics images on the Motorola AltiVec architecture. The filter utilizes 16-way SIMD parallelism to filter images at rates of 1.15 cycles/pixel for 3/spl times/3 squares and 6.6 cycles/pixel for 5/spl times/5 squares. The median filter is based on a new sorting network which sorts N/sup 2/ numbers (arranged in an N/spl times/N square) by sorting all columns, rows, and diagonal lines in the square. The paper also describes a scheme for efficient testing of the sorting network.

This paper presents a compiler optimization algorithm to reduce the run time overhead of array subscript range checks in programs without compromising safety. The algorithm is based on partial redundancy elimination and it incorporates previously developed algorithms for range check optimization. We implemented the algorithm in our research compiler, Nascent, and conducted experiments on a suite of 10 benchmark programs to obtain four results: (1) the execution overhead of naive range checking is high enough to merit optimization, (2) there are substantial differences between various optimizations, (3) loop-based optimizations that hoist checks out of loops are effective in eliminating about 98% of the range checks, and (4) more sophisticated analysis and optimization algorithms produce very marginal benefits.

Live range splitting techniques divide the live ranges of variables into live range segments to improve global register allocation. We present a new technique for live range splitting called load/store range analysis. This analysis localizes the profits and the register requirements of every access to every variable to provide a fine granularity of candidates for register allocation. Load/Store range analysis is based on the data flow analysis algorithm for def-use chaining. Experiments on a small suite of C and FORTRAN benchmark programs show that a graph coloring register allocator operating on load/store ranges often provides better allocations than the same allocator operating on live ranges. Experimental results also show that the computational cost of using load/store ranges for register allocation is moderately more than the cost of using live ranges. 1 Introduction The goal of register allocation is to map variables in an intermediate language program to either registers or mem...