A Code-Generator Generator for Multi-Output Instructions

We address the problem of instruction selection for Multi-Output Instructions (MOIs), producing more than one result. Such inherently parallel hardware instructions are very common in the area of Application Specific Instruction Set Processors (ASIPs) and Digital Signal Processors (DSPs) which are frequently used in Systemon-Chips as programmable cores. In order to provide high-level programmability, and consequently guarantee widespread acceptance, sophisticated compiler support for these programmable cores is of high importance. Since it is not possible to model Multi-Output Instructions as trees in the compiler’s Intermediate Representation (IR), traditional approaches for code selection are not sufficient. Extending traditional code-generation approaches for MOI-selection is essentially a graph covering problem, which is known to be NP-complete. We present a new heuristic algorithm incorporated in a retargetable code-generator generator capable of exploiting arbitrary inherently parallel MOIs. We prove the concept by integrating the tool into the LCC compiler which has been targeted towards different Instruction Set Architectures based on the MIPS architecture. Several network applications as well as some DSP benchmarks were compiled and evaluated to obtain results