Advanced Backend Optimization

10

Exploiting the Register Access Delays Before Instruction Scheduling

Usual periodic scheduling problems deal with precedence constraints having non-negative latencies. This seems a natural way for modeling scheduling problems, since task or instruction delays are generally non-negative quantities. However, in some cases, we need to consider edge latencies that not only model instruction latencies, but also model other precedence constraints. For instance, in register optimization problems devoted to optimizing compilation, a generic machine or processor model can allow considering access delays into/from registers. Edge latencies may be then non-positive, leading to a difficult scheduling problem in the presence of resource constraints.

This chapter is related to the problem of periodic scheduling with register requirement optimization; its aim is to solve the practical problem of register optimization in optimizing compilation. We show that preconditioning a data dependence graph (DDG) to satisfy register constraints before periodic scheduling under resources constraints may create circuits with non-positive distances, resulting from the acceptance of non-positive edge latencies. As a compiler construction strategy, it is forbidden to allow the creation of circuits with non-positive distances during the compilation flow because such DDG circuits do not guarantee the existence of a valid instruction schedule under resource constraints. We study two solutions to avoid the creation ...