sparse code motion
In this article, we add a third dimension to partial redundancy elimination by considering code size as a further optimization goal in addition to the more classical consideration of computation costs and register pressure. This results in a family of sparse code motion algorithms coming as modular extensions of the algorithms for busy and lazy code motion . Each of them optimally captures a predefined choice of priority between these three optimization goals, e.g. code size can be minimized while (1) guaranteeing at least the performance of the argument program, or (2) even computational optimality. Each of them can further be refined to simultaneously reduce the lifetimes of temporaries to a minimum. These algorithms are well-suited for size-critical application areas like smart cards and embedded systems, as they provide a handle to control the code replication problem of classical code motion techniques. In fact, we believe that our systematic, priority-based treatment of trade-offs between optimization goals may substantially decrease development costs of size-critical applications: users may play with the priorities until the algorithm automatically delivers a satisfactory solution.
code motion partial redundancy elimination code size lazy code motion compuational optimality busy code motion space optimality expression motion embedded processors and systems life-time optimality