Technical note. Approach for register allocation in microprogram generation

A dynamic procedure for the allocation of internal registers of a microprogrammable system is described. The rules of this procedure are developed to yield an optimal allocation that minimises the execution time of the microprogram generated. The method assumes that the control flow of the program to be microcoded is represented by a directed graph. The allocation and deallocation of the variables to the registers is carried out in each edge in the graph. The selection of the variables to be assigned to the registers in each node is performed using integer linear programming.