Optimal Dual-issue Instruction Scheduling with Spills for Binary Expression Trees
Date de publication : 1995
Éditeur : University of Michigan, Computer Science and Engineering Division, Department of Electrical Engineering and Computer Science
Nombre de pages : 14
Résumé du livre
Abstract: "We describe an algorithm that produces code, with spills, for a register-constrained machine that can issue up to one arithmetic operation and one memory access operation per time slot, under the restrictions that the code's dependence graph is represented as a binary tree with no unary operations, and the latency of the operations is 1. We prove that the algorithm produces a minimum cost schedule, and show that its complexity is O(nk) where n is the number of operations to be scheduled and k is the number of spills in the schedule. The number of issue slots in the minimum length schedule is p + 2k + [absolute value A] where p is the number of registers used, k is the number of spills and [absolute value of A] is the number of arithmetic operations in the tree. We show this is the cost of any schedule that is in 'contiguous form'."