A graph-based algorithm of operation binding for compilers targeting heterogeneous datapath

This paper presents a graph-based binding algorithm for a retargetable compiler which can deal with "heterogeneous" Or "non-orthogonal" datapath architectures. In compilation of programs for such architectures, binding of operations to functional units becomes a hard task because a certain assignment of an operation to a functional unit may make the execution of succeeding operations impossible. In our previous work [Yam98], we proposed a BDD-based algorithm to solve the operation binding problem completely, but it is applicable to a limited size of DFGs because it requires large number of Boolean variables. As a remedy to this problem, we propose in this paper a new algorithm which is based on transformations of a graph representing the solution space. The time complexity remains exponential but the new algorithm is better in that it is applicable to larger instances.