Efficient Backtracking Instruction Schedulers
Santosh G. Abraham, Waleed M. Meleis, Ivan D. Baev · 2000
Current schedulers for acyclic regions schedule operations in dependence order and never revisit or undo a scheduling decision on any operation. In contrast, backtracking schedulers may unschedule already scheduled operations, in order to make space for the operation currently being scheduled. Backtracking schedulers have the potential for generating better schedules, e.g. more effectively filling branch delay slots, but are more compile-time intensive and therefore, not considered practical for production use. In this report, we first describe...