Optimal register allocation in high level synthesis

A methodology for the register allocation problem in high-level synthesis based on the scanline sweep algorithm is introduced. The algorithm is computationally efficient and easy to understand and to implement, and it guarantees an optimal number of registers for nonpipelined designs. In this method, a set of registers is available from which the best one can be chosen by the allocator for variable binding. The method has proved to be useful in constructive allocation strategies in which the operators and variables are simultaneously considered for binding for interconnect cost optimization. The allocation program is written in C and it is integrated into the DAGAR high-level synthesis system