Advanced Backend Optimization

2

Instruction Scheduling Problems and Overview

Instruction scheduling is a critical performance optimization that takes place when compiling applications for instruction-level parallel processors such as very long instruction word (VLIW) processors. An instruction scheduling problem is defined by a set of operations¹ to schedule, a set of dependences between these operations and a target processor micro-architecture. The objective of instruction scheduling is to build an operation sequence of minimum length (block instruction scheduling) or maximum throughput (software pipeline instruction scheduling) on the target processor.

2.1. VLIW instruction scheduling problems

2.1.1. Instruction scheduling and register allocation in a code generator

In a compiler, instruction scheduling is applied to the last stages of optimizations before assembly language output, inside the so-called code generator. The code generator has four major tasks: code selection, control optimizations, register allocation and instruction scheduling [DIN 00]. Code selection translates the computations from the upper stage of the compiler into efficient target processor operation sequences. Control optimizations reduce the runtime penalty of branches by predicating code [MAH 95] and by reordering the basic blocks [PET 90]. The register allocator maps the operation operands to the processor registers or memory locations. The instruction scheduler reorders the operations to reduce the runtime processor stalls. In ...