Video decoding and image processing in embedded systems are subject to strong resource constraints, particularly in terms of memory. List-scheduling heuristics with static priorities (HEFT, SDC, etc.) being the often-cited solutions due to both their good performance and their low complexity, we propose a method aimed at introducing the notion of memory into them. Moreover, we show that through appropriate adjustment of task priorities and judicious resort to insertion-based policy, speedups up to 20% can be achieved. Lastly, we show that our technique allows to prevent deadlock and to substantially reduce the required memory footprint compared to classic list-scheduling heuristics.

We present a framework that allows translation of predicated code into the static single assignment (SSA) form, and simplifies application of the SSA-based optimizations to predicated code. In particular we represent predicate join points in the program by the /spl Psi/-functions similar to the /spl Phi/-functions of the basic SSA. The SSA-based optimizations (such as constant propagation) can be applied to predicated code by simply specifying additional rules for processing the /spl Psi/-functions. We present efficient algorithms for constructing, and then for removing the /spl Psi/-functions at the end of SSA processing. Our algorithm for translating out of the /spl Psi/-SSA splits predicated live ranges into smaller live ranges active under disjoint predicates. The experimental evaluation on a set of predicated benchmarks demonstrates efficiency of our approach.

The ST120 Digital Signal Processor -Micro-Controller Unit (DSP{MCU) core was designed by STMicroelectronics in order to meet the ever-increasing digital signal processing requirements of portable and consumer applications.Like other recent high-end DSP{MCU cores, the ST120 blends traditional DSP features with modern Instruction-Level Parallelism (ILP) capabilities.Compiler management o f the ST120 features presents a unique challenge to the code generation.The ST120 Linear Assembly Optimizer (LAO) eectively exploits instructionlevel parallelism, while enabling compact code size.In this paper, we focus on the LAO implementation of the SSA representation, the IF-conversion, the SLIW scheduling, and the LAO i m p r o vements to register allocation.This includes solutions to problems that arise when compiler optimizations are applied to assembly-level, already predicated code.Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page.To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific

This paper is a scientific comparison of two code generation techniques with identical goals --- generation of the best possible software pipelined code for computers with instruction level parallelism. Both are variants of modulo scheduling, a framework for generation of software pipelines pioneered by Rau and Glaser [RaG181], but are otherwise quite dissimilar.One technique was developed at Silicon Graphics and is used in the MIPSpro compiler. This is the production compiler for SGI's systems which are based on the MIPS R8000 processor [Hsu94]. It is essentially a branch--and--bound enumeration of possible schedules with extensive pruning. This method is heuristic because of the way it prunes and also because of the interaction between register allocation and scheduling.The second technique aims to produce optimal results by formulating the scheduling and register allocation problem as an integrated integer linear programming (ILP1) problem. This idea has received much recent exposure in the literature [AlGoGa95, Feautrier94, GoAlGa94a, GoAlGa94b, Eichenberger95], but to our knowledge all previous implementations have been too preliminary for detailed measurement and evaluation. In particular, we believe this to be the first published measurement of runtime performance for ILP based generation of software pipelines.A particularly valuable result of this study was evaluation of the heuristic pipelining technology in the SGI compiler. One of the motivations behind the McGill research was the hope that optimal software pipelining, while not in itself practical for use in production compilers, would be useful for their evaluation and validation. Our comparison has indeed provided a quantitative validation of the SGI compiler's pipeliner, leading us to increased confidence in both techniques.