Loop scheduler
First Claim
1. A method of generating a schedule for executing in a target computer loops of instructions contained in a computer program, comprising the steps of:
- (1) searching for an optimal loop schedule for executing a particular instruction loop in the target computer;
(2) identifying loop overhead instructions and non-loop overhead instructions in said particular instruction loop;
(3) generating a replicated loop schedule by replicating said non-loop overhead instructions in said loop schedule by a replication factor such that overlap of each operation instance in said optimal loop schedule with itself is prevented;
(4) inserting said loop overhead instructions into said replicated loop schedule to generate a modified loop schedule; and
(5) allocating registers of the target computer to said modified loop schedule.
7 Assignments
0 Petitions
Accused Products
Abstract
A loop scheduler in a software compiler system for generating a schedule for executing in a target computer loops of instructions contained in a computer program is described. The loop scheduler operates by searching for an optimal loop schedule for executing a particular instruction loop in the target computer. The loop scheduler then identifies loop overhead instructions and non-loop overhead instructions in the particular instruction loop. A replicated loop schedule is generated by the loop scheduler by replicating the non-loop overhead instructions in the loop schedule by a replication factor such that overlap of each operation instance in the optimal loop schedule with itself is prevented. The loop scheduler inserts the loop overhead instructions into the replicated loop schedule to generate a modified loop schedule, and then allocates registers of the target computer to the modified loop schedule.
-
Citations
16 Claims
-
1. A method of generating a schedule for executing in a target computer loops of instructions contained in a computer program, comprising the steps of:
-
(1) searching for an optimal loop schedule for executing a particular instruction loop in the target computer; (2) identifying loop overhead instructions and non-loop overhead instructions in said particular instruction loop; (3) generating a replicated loop schedule by replicating said non-loop overhead instructions in said loop schedule by a replication factor such that overlap of each operation instance in said optimal loop schedule with itself is prevented; (4) inserting said loop overhead instructions into said replicated loop schedule to generate a modified loop schedule; and (5) allocating registers of the target computer to said modified loop schedule. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
-
8. A method of generating a schedule for executing in a target computer loops of instructions contained in a computer program, comprising the steps of:
-
(1) searching for an optimal loop schedule for executing a particular instruction loop in the target computer, said search including; enumerating all possible schedules of said particular instruction loop using a predetermined exponential search procedure; ordering said all possible schedules in a search list according to complexity of operation scheduling; and pruning said predetermined exponential search procedure to expedite back searching in said search list; (2) identifying loop overhead instructions and non-loop overhead-instructions in said particular instruction loop, said identifying including; classifying an instruction of said particular instruction loop as a loop overhead instruction if said instruction operates to increment an induction variable; and classifying said instruction as a loop overhead instruction if said instruction operates to perform a logical test of an induction variable; (3) generating a replicated loop schedule by replicating said non-loop overhead instructions in said loop schedule by a replication factor such that overlap of each operation instance in said optimal loop schedule with itself is prevented, said generating including; determining a total number of instructions value corresponding to the number of instructions in said particular instruction loop; determining a lifetime of each operation instance in said optimal loop schedule; generating a set of potential replication factors, each element of said set being equal to a lifetime value for an operation instance divided by said total number of instructions value; and setting said replication factor equal to a maximum value in said set; (4) inserting said loop overhead instructions into said replicated loop schedule to generate a modified loop schedule, said inserting including; using loop overhead information and an iteration number of a memory reference operation in said optimal loop schedule to calculate effective address information of said memory reference operation; and inserting said effective address information into said replicated loop schedule; and (5) allocating registers of the target computer to said modified loop schedule, said allocating including; calculating an applicable executable range of clock cycles for an operation instance of said modified loop schedule according to any scheduled data predecessors and any schedules data successors of said operation instance; performing a forward search of said modified loop schedule to schedule any unscheduled data predecessors of said operation instance; and performing a backward search of said modified loop schedule to schedule any unscheduled data successors of said operation instance.
-
-
9. A system for generating a schedule for executing in a target computer loops of instructions contained in a computer program, comprising:
-
optimal loop searching means for searching for an optimal loop schedule for executing a particular instruction loop in the target computer; instruction identifying means for identifying loop overhead instructions and non-loop overhead instructions in said particular instruction loop; replicating means for generating a replicated loop schedule by replicating said non-loop overhead instructions in said loop schedule by a replication factor such that overlap of each operation instance in said optimal loop schedule with itself is prevented; loop overhead means for inserting said loop overhead instructions into said replicated loop schedule to generate a modified loop schedule; and register allocating means for allocating registers of the target computer to said modified loop schedule. - View Dependent Claims (10, 11, 12, 13, 14, 15)
-
-
16. A system for generating a schedule for executing in a target computer loops of instructions contained in a computer program, comprising:
-
optimal loop searching means for searching for an optimal loop schedule for executing a particular instruction loop in the target computer, wherein said optimal loop searching means includes; means for enumerating all possible schedules of said particular instruction loop using a predetermined exponential searching procedure; means for ordering said all possible schedules in a search list according to complexity of operating scheduling; and means for pruning said predetermined exponential search procedure to expedite back searching in said search list; instruction identifying means for identifying loop overhead instructions and non-loop overhead instructions in said particular instruction loop, wherein said instruction identifying means includes; means for classifying an instruction of said particular instruction loop as a loop overhead instruction if said instruction operates to increment an induction variable; and means for classifying said instruction as a loop overhead instruction if said instruction operates to perform a logical test of an induction variable; replicating means for generating a replicated loop schedule by replicating said non-loop overhead instructions in said loop schedule by a replication factor such that overlap of each operation instance in said optimal loop schedule with itself is prevented, wherein said replicating means includes; means for determining a total number of instructions value corresponding to the number of instructions in said particular instruction loop; means for determining a lifetime of each operation instance in said optimal loop schedule; means for generating a set of potential replication factors, each element of said set being equal to a lifetime value for an operation instance divided by said total number of instructions value; and means for setting said replication factor equal to a maximum value in said set; loop overhead means for inserting said loop overhead instructions into said replicated loop schedule to generate a modified loop schedule, wherein said loop overhead means includes; means for using loop overhead information and an iteration number of a memory reference operation in said optimal loop schedule to calculate effective address information of said memory reference operation; and means for inserting said effective address information into said replicated loop schedule; and register allocating means for allocating registers of the target computer to said modified loop schedule, wherein said register allocating means comprises; means for calculating an applicable executable range of clock cycles for an operation instance of said modified loop schedule according to any scheduled data predecessors and any scheduled data successors of said operation instance; means for performing a forward search of said modified loop schedule to schedule any unscheduled data predecessors of said operation instance; and means for performing a backward search of said modified loop schedule to schedule any unscheduled data successors of said operation instance.
-
Specification