O'Reilly logo

Advanced Backend Optimization by Sid Touati, Benoit de Dinechin

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 operations1 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required