Minimizing Register Requirement in Loops Data Dependence Graphs.

International audienceWe presented during the last CPC workshop (2001) a new framework for doing an early register allocation in simple innermost loops, before any software pipelining pass. This was done by inserting some anti-dependence edges labeled with reuse distances, directly on the data dependence graph. In this new graph, we were able to guarantee the register pressure, counted as the number of simultaneously alive variables in any schedule. The determination of register and distance reuse is controlled by the critical cycle ratio (MII) desired as well as by the register pressure constraints - either can be minimized while the other one is fixed. In this paper, we present our new results. Since the compilation time for computing an optimal register allocation is intractable in real codes, we focus on our polynomial and "semi"-polynomial methods for register allocation. This is done by "fixing" the reuse edges in the graph before minimizing the register requirement. We will see how to apply an early register allocation on machines with multiple register sets, with rotating register files, or on those with buffers. Our method is a generalization to the Ning-Gao buffer minimization heuristics