Improved software pipelining for superscalar architectures

Although instruction scheduling is an scNP-complete problem (27), many techniques have been developed to improve pipelining efficiency. Among them, several were proposed for scVLIW machines, and were shown to be efficient and extendible to superscalar architectures. However the available resources on a superscalar can vary significantly. Our goal for this thesis is to improve the effectiveness of software pipelining scheduling for modern superscalar architectures. (I) We explore ways to improve compile time performance by producing more accurate lower bounds for $II\sb{min}.$ Our new scheme accounts for register use and lets the scheduler provide guidance to the allocator. The scheduling process of the loops that benefited from this technique was 18% to 30% faster. (II) We explore new techniques for improving the schedules of loops that contain complex control flow. Our proposed techniques do not require the addition of specialized hardware. The initiation intervals for those loops were reduced by 25% to 36%