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.