| Instruction set architects and compiler writers often have conflicting requirements on the design of an instruction set. The architects are driven by potential micro-architecture complexity and possibly by code size considerations, while the compiler developers prefer clean orthogonal instruction sets amenable to regular compiler algorithms. While this struggle has stabilized with an uneasy boundary between RISC and CISC architectural styles in general-purpose computing, in the embedded computing world with domain specific processors like Digital Signal Processors (DSPs), it still continues. This has resulted in irregular architectures that are hard to compile for and need special optimization techniques to exploit their full potential. In order to balance the different embedded processing constraints like performance, code size, power and area, Instruction Set Architectures (ISAs) of low-end DSPs have a narrow instruction width, yet they use a Very Long Instruction Word (VLIW) style architecture. Such a design results in irregular ISAs that are non-orthogonal and have restricted Instruction Level Parallelism (ILP). This irregular ISA presents a significant problem for compilers. Traditional schedulers that work with physical resources to determine scheduling conflicts and popular graph coloring based register allocators cannot be employed directly. This dissertation makes the following two contributions: first it shows how the irregular ILP of ISAs can be mapped to regular resource based constraints requirement of classic VLIW schedulers by generating a set of artificial resources. These resources may not correspond to any real physical resources, but are created to provide a specification that is familiar to schedulers, thereby leveraging the large body of work done in VLIW compilation. Next, it presents a fast and optimal Integer Linear Programming based register allocator for architectures with irregular constraints which builds upon the work done by Appel and George [10]. The different constraints posed by irregular DSP architectures are captured in the model. In addition, it augments the original model by a more accurate consideration of memory spills. Finally, the retargetability, an important design feature, of the algorithms presented in this dissertation is demonstrated by extracting their inputs for two case studies, the Fujitsu Hiperion and IMPACT EPIC architectures from an Architecture Description Language (ADL). |
