Ecole Polytechnique Federale de Lausanne
Register allocation for programs in Static Single Assignment (SSA) form has a polynomial-time solution because interference graphs for procedures in this representation are chordal graphs. This paper explores a complementary problem which is NP-complete: the assignment of registers to variables in order to minimize interconnect costs. In particular, the authors attempt to minimize the size of the multiplexers placed on the input to each register. This is particularly important for FPGA-based design flows where multiplexers have a high cost in terms of both area and delay.