Adapting a Constraint-Based Compiler Tool to a New VLIW Architecture

Sammanfattning: he compiler tool Unison uses combinatorial optimisation to perform integrated register allocation and instruction scheduling, and is designed to be possible to adapt to different processor architectures. Black Arrow is a VLIW (very long instruction word) architecture designed for signal processing within the field of mobile communication technology. Black Arrow has structural traits that complicate the register allocation and instruction scheduling process. Most important of these is that functionally equivalent execution units within the processor are not topologically equivalent, since their distances to other execution units vary. This means that an instruction schedule must indicate not only in what cycle each instruction is to be executed, but also the execution unit that will execute it. This thesis presents and evaluates a version of Unison that has been adapted to Black Arrow. A central point in the adaptation is how the problem of assigning each Black Arrow instruction to a specific execution unit is solved through the use of Unison’s ability to choose between several alternative instructions implementing the same operation. The evaluation shows that the Black Arrow version of Unison, when optimising for minimal execution time and a variant of minimal code size, is able to find optimal solutions to the register allocation and instruction scheduling problems for several common integer algorithms, within reasonable time.