Instruction Scheduling for Complex Pipelines

M. Anton Ertl and Andreas Krall
Institut für Computersprachen
Technische Universität Wien
Argentinierstraße 8
A-1040 Wien, Austria
{anton,andi}@complang.tuwien.ac.at

Abstract

We designed heuristics for applying the list scheduling algorithm to processors with complex pipelines. On these processors the pipeline can stall due to resource contention (structural hazards) in addition to the usual data hazards. Conventional heuristics consider only data hazards. Our heuristics reduce structural hazards, too. Code with much instruction-level parallelism is optimized to avoid structural hazards, sequential code is scheduled for reducing data hazards. Embedded in a postpass strategy our scheduler removes 60%-100% of the removable stalls from conventionally scheduled code.