Enhanced trace instruction scheduler with code optimizations

Abstract

Instruction scheduling is an important compiler technique for exploiting instruction-level parallelism (ILP) in modern, high-performance microprocessors. Among scheduling techniques, trace scheduling is an optimization technique that performes instruction scheduling across basic blocks. The trace scheduler selects a group of instructions from a sequence of basic blocks and schedules these instructions as if they were in a single basic block. So If operations are moved across basic block boundaries, the compensation copies are inserted into off-traces in order to preserve program``s semantics. But insertion of compensation copies penalizes the off-trace code. The goal of this thesis is to reduce the penalty of off-traces and to overcome the risk from misprediction of branch target especially in control-intensive programs. It deals with the problem of compensation copy codes and presents optimization techniques to enhance the trace scheduling, related to the paths including off-traces. And the effectiveness is evaluated by using SPEC95 benchmark programs. The result shows the feasibility of improvement of trace scheduling with compensation code optimization techniques proposed in this paper.