Storage constraint satisfaction for embedded processor compilers

Increasing interest in the high-volume high-performance embedded processor market motivates the stand-alone processor world to consider issues like design flexibility (synthesizable processor core), energy consumption, and silicon efficiency. Implications for embedded processor architectures and compilers are the exploitation of hardware acceleration, instruction-level parallelism (ILP), and distributed storage files. In that scope, VLIW architectures have been acclaimed for their parallelism in the architecture while orthogonality of the associated instruction sets is maintained. Code generation methods for such processors will be pressured towards an efficient use of scarce resources while satisfying tight real-time constraints imposed by DSP and multimedia applications. Limited storage (e.g. registers) availability poses a problem for traditional methods that perform code generation in separate stages, e.g. operation scheduling followed by register allocation. This is because the objectives of scheduling and register allocation cause conflicts in code generation in several ways. Firstly, register reuse can create dependencies that did not exist in the original code, but can also save spilling values to memory. Secondly, while a particular ordering of instructions may increase the potential for ILP, the reordering due to instruction scheduling may also extend the lifetime of certain values, which can increase the register requirement. Furthermore, the instruction scheduler requires an adequate number of local registers to avoid register reuse (since reuse limits the opportunity for ILP), while the register allocator would prefer sufficient global registers in order to avoid spills. Finally, an effective scheduler can lose its achieved degree of instruction-level parallelism when spill code is inserted afterwards. Without any communication of information and cooperation between scheduling and storage allocation phases, the compiler writer faces the problem of determining which of these phases should run first to generate the most efficient final code. The lack of communication and cooperation between the instruction scheduling and storage allocation can result in code that contains excess of register spills and/or lower degree of ILP than actually achievable. This problem called phase coupling cannot be ignored when constraints are tight and efficient solutions are desired. Traditional methods that perform code generation in separate stages are often not able to find an efficient or even a feasible solution. Therefore, those methods need an increasing amount of help from the programmer (or designer) to arrive at a feasible solution. Because this requires an excessive amount of design time and extensive knowledge of the processor architecture, there is a need for automated techniques that can cope with the different kinds of constraints during scheduling. This thesis proposes an approach for instruction scheduling and storage allocation that makes an extensive use of timing, resource and storage constraints to prune the search space for scheduling. The method in this approach supports VLIW architectures with (distributed) storage files containing random-access registers, rotating registers to exploit the available ILP in loops, stacks or fifos to exploit larger storage capacities with lower addressing costs. Potential access conflicts between values are analyzed before and during scheduling, according to the type of storage they are assigned to. Using constraint analysis techniques and properties of colored conflict graphs essential information is obtained to identify the bottlenecks for satisfying the storage file constraints. To reduce the identified bottlenecks, this method performs partial scheduling by ordering value accesses such that to allow a better reuse of storage. Without enforcing any specific storage assignment of values, the method continues until it can guarantee that any completion of the partial schedule will also result in a feasible storage allocation. Therefore, the scheduling freedom is exploited for satisfaction of storage, resource, and timing constraints in one phase