Automatic Instruction Scheduler Retargeting by Reverse-Engineering [abstract] (ACM DL, PDF)
Matthew J. Bridges, Neil Vachharajani, Guilherme Ottoni, and David I. August
Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), June 2006.
In order to generate high-quality code for modern processors, a
compiler must aggressively schedule instructions, maximizing resource
utilization for execution efficiency. For a compiler to produce such
code, it must avoid structural hazards by being aware of the
processor's available resources and of how these resources are
utilized by each instruction. Unfortunately, the most prevalent
approach to constructing such a scheduler, manually discovering and
specifying this information, is both tedious and error-prone.
This paper presents a new approach which, when given a processor or
processor model, automatically determines this information. After
establishing that the problem of perfectly determining a processor's
structural hazards through probing is not solvable, this paper
proposes a heuristic algorithm that discovers most of this information
in practice. This can be used either to alleviate the problems
associated with manual creation or to verify an existing
specification. Scheduling with these automatically derived structural
hazards yields almost all of the performance gain achieved using
perfect hazard information.