Lifetime-sensitive instruction scheduling mechanism and method
First Claim
Patent Images
1. An apparatus comprising:
- at least one processor that includes at least one fixed register;
a memory coupled to the at least one processor;
a computer program residing in the memory that includes a selected instruction that defines at least one fixed register; and
an instruction scheduler residing in the memory and executed by the at least one processor, the instruction scheduler scheduling the selected instruction in a scheduling window, determining the lifetime in the scheduling window of the at least one fixed register defined in the selected instruction, and scheduling at least one other instruction within the lifetime of the at least one fixed register before scheduling any instruction that is in a different lifetime of the fixed register in the scheduling window.
1 Assignment
0 Petitions
Accused Products
Abstract
An instruction scheduler in an optimizing compiler schedules instructions in a computer program by determining the lifetimes of fixed registers in the computer program. By determining the lifetimes of fixed registers, the instruction scheduler can achieve a schedule that has a higher degree of parallelism by relaxing dependences between instructions in independent lifetimes of a fixed register so that instructions can be scheduled earlier than would otherwise be possible if those dependences were precisely honored.
98 Citations
20 Claims
-
1. An apparatus comprising:
-
at least one processor that includes at least one fixed register;
a memory coupled to the at least one processor;
a computer program residing in the memory that includes a selected instruction that defines at least one fixed register; and
an instruction scheduler residing in the memory and executed by the at least one processor, the instruction scheduler scheduling the selected instruction in a scheduling window, determining the lifetime in the scheduling window of the at least one fixed register defined in the selected instruction, and scheduling at least one other instruction within the lifetime of the at least one fixed register before scheduling any instruction that is in a different lifetime of the fixed register in the scheduling window. - View Dependent Claims (2, 3, 4, 5)
-
-
6. An apparatus comprising:
-
at least one processor that includes at least one fixed register;
a memory coupled to the at least one processor;
a computer program residing in the memory that includes a selected instruction within a scheduling window, wherein the selected instruction defines at least one fixed register;
means for scheduling the selected instruction in the scheduling window;
means for determining the lifetime in the scheduling window of the at least one fixed register defined in the selected instruction; and
means for scheduling at least one other instruction within the lifetime of the at least one fixed register before scheduling any instruction that is in a different lifetime of the fixed register in the scheduling window.
-
-
7. A method for scheduling a plurality of instructions within a scheduling window in a computer program, the method comprising the steps of:
-
scheduling a selected instruction in the scheduling window;
determining the lifetime in the scheduling window of at least one fixed register defined in the selected instruction, wherein the at least one fixed register comprises a physical register in a processor that executes the computer program; and
scheduling at least one other instruction within the lifetime of the at least one fixed register before scheduling any instruction that is in a different lifetime of the fixed register in the scheduling window. - View Dependent Claims (8)
-
-
9. A method for scheduling a plurality of instructions in a computer program, the method comprising the steps of:
-
(A) building a conditional dependence graph from the plurality of instructions;
(B) seeding a ready list with at least one of the plurality of instructions based on the information in the conditional dependence graph;
(C) scheduling at least one instruction on the ready list;
(D) modifying the conditional dependence graph;
(E) updating the ready list from the modified conditional dependence graph;
(F) repeating steps (C) through (E) until the ready list is empty, signifying that all of the plurality of instructions have been scheduled. - View Dependent Claims (10, 11, 12, 13)
for each instruction scheduled in step (C);
removing the instruction from the conditional dependence graph; and
removing dependences that point to the instruction.
-
-
13. The method of claim 9 wherein the step of seeding the ready list includes the step of placing on the ready list all instructions that:
-
have no dependences on other instructions in the conditional dependence graph; and
have only conditional dependences on other instructions in the conditional dependence graph.
-
-
14. A program product comprising:
-
(A) an instruction scheduler that schedules a selected instruction in a scheduling window of a computer program, determines the lifetime in the scheduling window of at least one fixed register defined in the selected instruction, wherein the at least one fixed register comprises a physical register in a processor that executes the computer program, and schedules at least one other instruction within the lifetime of the at least one fixed register before scheduling any instruction that is in a different lifetime of the fixed register in the scheduling window; and
(B) signal bearing media bearing the instruction scheduler. - View Dependent Claims (15, 16, 17, 18, 19, 20)
-
Specification