Instruction Scheduling for Complex Pipelines

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 heuri-stics reduce structural hazards, too. Code with much instruction-level paral-lelism 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.