Combining Instruction Selection and Scheduling in Software Pipelining

N. I. V'jukova, Senior Research Fellow, e-mail: e-mail: niva@niisi.msk.ru, V. A. Galatenko, Head of Department, e-mail: galat@niisi.msk.ru, S. V. Samborskij, Senior Research Fellow, e-mail: sambor@niisi.msk.ru, Federal State Institution "Scientific Research Institute for System Analysis of the Russian Academy of Science", Moscow

The traditional code generation scheme involves three major passes: instruction selection, instruction scheduling, and register allocation. Separation of these tasks and use of heuristic algorithms for their implementation is quite acceptable in compilers for modern universal architectures. Still such an approach may provide insufficient code efficiency for peculiar architectures used in embedded systems.

The paper presents a method of software pipelining of loops by means of exact joint solution of the in struction selection and instruction scheduling tasks for cyclic blocks of program code. We propose an approach of treating the above tasks as a single Integer Linear Programming (ILP) task. This allows taking into account interdependences between the three code generation passes. The method being proposed provides a unified approach to various code generation and optimization problems including automatic use of complex instructions (with multiple results), common subexpression elimination, automatic generation and scheduling of spill code, instruction selection with respect to available instruction-level parallelism and data dependencies including interloop ones.

Complexity of implementation and heavy use of computing resources makes this approach hardly usable in commonly used compilers. Therefore the method is intended mostly for development of hardware accelerators and generation of high performance code for embedded systems.

Possible directions for further enhancement of the method include restrictions on energy consumption in formulations of ILP tasks and use of mathematical equalities in the process of code generation. One more perspective research direction is use of constraints programming for specification of code generation tasks.

Keywords: code generation, software pipelining, modulo scheduling, instruction selection, Integer Linear Programming (ILP)

pp. 3–10