Scheduling Register-Allocated Codes in User-Guided High-Level Synthesis

In high-level synthesis, as for compilers, an important question is when register assignment should take place. Unlike compilers for which the processor architecture is given, synthesizers can, in principle, perform scheduling before register assignment by instantiating, after scheduling, the adequate number of registers (thus with no spilling) and the right connections between operators. However, this approach may sometimes lead to suboptimal data paths. An alternate solution is to let the designer have some control on the compilation process so as to force desirable data paths and resource sharing. For example, in UGH, a public-domain user-guided high-level synthesis tool, the designer interacts with the synthesizer by providing an early allocation of scalar variables to registers and a draft data path that describes some or all connections between registers and operators. The well-known drawback of early register assignment is that it over-constrains the scheduler with false dependences. The UGH scheduler first removes these dependences and adds them on the fly during scheduling. It has been noticed that, although this approach can achieve good results in practice for suitable user designs, some rare deadlock situations can arise in the scheduler. We analyze the reason for such deadlocks and improve UGH strategy with a new implementation. We show how to avoid the deadlocks as much as possible and how, with some register duplication, they can be circumvented otherwise. We also show that, unless P=NP, there is no hope to design a polynomial test that decides which operation to schedule first so as to avoid a deadlock, therefore a duplication.