Global Acyclic Instruction Scheduling Research

Instruction scheduling is kind of instruction level parallelism (ILP) technology. It is both a microarchitecture technology and a compilation technology. To be the later, Instruction scheduling refers to technology that exploits the ILP of pipelined or multiissued processors by reordering the instructions under the constraints of preserving the semantics. With the development of microarchitecture, state of art processors normally has ample resources. To get the full utilization of these resources, instruction scheduling should be performed across basic block's boundary, viz. global instruction scheduling. This thesis performs a intensive study on acyclic global instruction scheduling — a branch of global instruction scheduling technology. Our contributions includes following aspects:1. Propose a global instruction scheduling framework oriented to IA-64 architecture. Our work is based upon D.Bernstein's work which is oriented to superscalar.2. Based on D.Bernstein work, we propose a global instruction scheduling framework on hierarchically structured region(HSR). The scheduling scope for traditional global instruction scheduling is flat structured. A flat structured region is normally very small due to the fact that scheduler pose special requirements on the shape of scheduling region. On the other hand, a flat structured region can sometimes very large if the control flow is simple.HSR region has no such flaws, hence it deserve our effort to perform instruction scheduling on HSR.3. Integrate P-ready instruction scheduling to D.Bernstein's instruction scheduling framework.4. Improve the heuristic of D.Bernstein's global instruction scheduling. We are trying to improve the following 2 defects:(1)favor control equivalent code motion over speculative code motion, therefore suppress speculation;(2)Over estimate the cost of code duplication, and hence lost some optimization opportunities;(3)The code on critical path will be delayed due to the priority mechanism weighs Delaysum() more than DepHeight() .5. Propose a novel spanning tree scheduling (STS) algorithm, including 2 aspects: scheduling framework as well as its heuristic. If the control flow is non-linear, traditional global scheduling will confine themselves within a block in the evaluation of instruction's priority. STS can evaluate instructions' priority on a maximum spanning tree of the scheduling region. Because the scope is larger, the evaluation of STS is more...