The Key Technology Research, Instruction-level Parallelism Compiled

Instruction-level parallel processing is the key technology to promoting the performance of current processor, and compiler plays a very important role in it. In the past 20 years, a lot of work has been done in this area. But there are still problems remaining unresolved. This paper discusses in depth the key techniques of instruction-level parallelizing compiler design, including: design of intermediate representation, register allocation, global instruction scheduling, etc. We applied the results in the development of a prototype C compiler for a VLIW-like processor, and acquired fairly good effect.The main contributions of this paper are: Present the multi-view intermediate representation: we introduce the concept of view in the design of intermediate representation (IR). With multiple discretely defined views of a single object, we can satisfy the different requirements to IR of algorithms of different passes. We separate the physical view and logic view of IR, and make algorithms work on the high-level logic view, and map the high-level algorithms into low-level IR through view transformations. With this technique we can simplify the formulation of algorithms and reduce the development cost, promote the abstract level and reusability. Present the hierarchical coloring register allocation: aim at partitioned register file with explicit parallel characteristics, we present hierarchical coloring register allocation. This method divides the coloring process into inter-group coloring and inner-group coloring. By processing the allocation of group and the allocation of register separately, we simplify the interference graph and reduce the complexity of register allocation. Present a new optimization - software forwarding: forwarding (also called bypassing) has been widely used in hardware design to avoid pipeline stalls caused by data hazard for a long time. In this paper, it was shown that the same thing could be done statically by compiler for new explicit parallel processors, and this approach can not only reduce the pipeline stalls, but also alleviate the register pressure. Present the cooperative instruction scheduling: aim at the phase-ordering problem of instruction scheduling and register allocation. we present a cooperative instruction scheduling method. By performing immediate register allocation in the same time of instruction scheduling, we avoid the problems caused by the separation in time of these two phases. Because we take the history of allocation into consideration and delay the insertion of spilling code, we get effect comparable to graph coloring register allocation. In addition, this method can deal with general resources and operations. Present the analysis of danger-operations: with this analysis performed ahead, we extend the EPS method of software pipelining to deal with multi-cycle operation,...