Optimal code generation for embedded memory non-homogeneous register architectures

Abstract

This paper examines the problem of code-generation for expression trees on non-homogeneous register set architectures. It proposes and proves the optimality of an O(n) algorithm for the tasks of instruction selection, register allocation and scheduling on a class of architectures defined as the [1; 1] Model. Optimality is guaranteed by sufficient conditions derived from the Register Transfer Graph (RTG), a structural representation of the architecture which depends exclusively on the processor Instruction Set Architecture (ISA). Experimental results using the TMS320C25 as the target processor show the efficacy of the approach. 1 Introduction Non-homogeneous register architectures are frequently encountered in Application Specific Instruction Set Processors (ASIPs). These processors usually have a set of very specialized functional units, and associated registers, that are used to efficiently implement operations with hard performance requirements which frequently occur in the applica...